Débordement en utilisant la méthode Chebyshev en virgule fixe

Question

J'ai un algorithme dans un système embarqué qui doit calculer sin (thêta), sin (2 * thêta), sin (3 * thêta), etc.) avec l'arithmétique à virgule fixe Q15. sin (thêta) et cos (thêta) sont générés en utilisant un combo LUT/interpolation, mais je suis en utilisant la méthode Chebyshev pour calculer l'ordre supérieur Sines, qui ressemble à ceci (pseudo-code):

sinN1 = Comes from Q15 LUT/interp algorithm 
cosN1 = Comes from Q15 LUT/interp algorithm 

sinN2 = (cosN1*sinN1)>>14; 
sinN3 = (cosN1*sinN2)>>14 - sinN1; 
sinN4 = (cosN1*sinN3)>>14 - sinN2; 
.... 

Le problème est que dans certaines conditions, cette méthode donne un résultat qui peut déborder d'une variable Q15. Par exemple, permet de considérer lors thêta = 2,61697:

sinN1 (Q15) = int(2**15*sin(2.61697)) = 16413 
cosN1 (Q15) = int(2**15*cos(2.61697)) = -28361 
sinN2 = (-28361*16413)>>14 = -28412   # OK 
sinN3 = (-28361*-28412)>>14 - 16413 = 32768 # OVERFLOW BY 1 
.. 

Je ne semblent jamais déborder de plus d'un bit de poids faible ou deux. Il semble être un artifcat de quantification composée. J'utilise un processeur ARM Cortex M4, donc je peux ajouter une logique de saturation avec relativement peu d'instructions, mais je fais beaucoup de DSP en streaming en temps réel avec des exigences de latence très basses donc je dois économiser autant de CPU que je peux donc je me demande s'il y a une façon plus élégante de gérer ce problème.

Answer 1

Le mathématicien en moi veut suggérer de garder une estimation de l'erreur accumulée et de la corriger d'une manière sigma-delta comme élégante, mais le programmeur pragmatique en moi dit que c'est insensiblement impossible.

L'instruction SSAT va saturer votre résultat à n'importe quelle position que vous voulez, coûte un seul cycle, et devrait être facilement disponible via le __ssat intrinsèque sur tout compilateur non-poubelle. Puisque vous allez inévitablement accumuler des erreurs avec n'importe quel arithmétique non-entier, je ne suis pas sûr qu'il y ait vraiment quelque chose de mieux que de simplement faire le calcul et de passer un cycle supplémentaire en s'assurant qu'il est à portée.

---

Ce que je ne peux pas travailler tout à fait est que si vous pouvez l'obtenir gratuitement tout en barbotant dans un peu d'assemblage (en ligne) pour obtenir au changement facultatif dans ssat que la valeur intrinsèque n'expose pas, sur la base que l'étape de correction de multiplication/PF est la plus grande source d'erreur; quelque chose comme (pseudo-assemblage):

mul tmp, cosN1, sinN2 
ssat tmp, #16, tmp, asr #14 
sub sinN3, tmp, sinN1 

qui vous ne pouvez sans risque vous en sortir avec si vous pouvez garantir à jamais finir avec quelque chose comme sinN3 = 0 - (-32768). QSUB16 est tentant de remplacer le SUB, mais étant une opération parallèle ferait des trucs bizarres avec le demi-mot supérieur des bits de signe, et dès que vous ajoutez un masque ou une instruction de demi-mot-emballage pour corriger cela, vous avez perdu le " Jeu.