固定小数点演算でオーバーフローが発生する

Question

一部の学習練習として、ホビープロジェクトの一部として、固定小数点演算を使用してAVRでCooley-Tukey FFTアルゴリズムの独自の解釈を実装しています。私は前に固定小数点数学をあまり扱っておらず、実装の一環としてどのように最善を尽くすのかと思っています。私は、この質問の要点は、私が正しく関与している問題について考えていることを確認する要求だと思います。

temp1 = cosine(increment)*dataRealPart[increment1] 
-sine(increment)*dataImaginaryPart[increment1] 

temp2 = cosine(increment)*dataImaginaryPart[increment1] 
+ sine(increment)*dataRealPart[increment1] 

dataRealPart[increment1] = dataRealPart[increment2] - temp1 

etc. 

余弦および正弦データが8ビットの符号付きバイナリ画分であろう。

CTアルゴリズムの中心は（pseduocodeに）次の方法で複素数値データに対して乗算と加算のセットを含みますS.XXX'XXXXの形式の場合、入力データはSXXX.XXXXという形式の8ビット符号付きバイナリ分数になり、乗算は16ビット符号付き分数積を生成します。私が見ているように、正弦と余弦の特に悪い値と、データの実数部と虚数部については、temp1またはtemp2は16ビット符号付き整数の限界にかなり近くなります。
データの実数部と虚数部の両方が、例えばb0111.1111の場合、Wolfram Alphaの小さな作業では、正弦と余弦の値が「悪い」場合、出力は最大で1.4倍大きくなりますサインの最大値と入力の最大値を単純に掛け合わせるものはどれくらいでしょうか。

たとえば、sine引数がb0111.1111で、入力値がb0111.111の場合、出力はb0111111.00000001または16129（10進数）になります。これは符号付き16ビットintの正の範囲をオーバーフローさせませんが、次の行でこれらの積を加算して入力データから減算し、ここでの入力データが16ビットに変換されると仮定しますオーバーフローが発生する可能性があります。

データの内部処理の解像度を上げて処理時間を増やすか、入力データがオーバフローの原因となる振幅よりも低くなるようにして、ノイズ比。それは物事の大きさについてですか？

Answer 1

1つのオプションは、サインとコサインの値をQ6（小数点の右側に6ビット）に減らすことです。これにより+/- 64になります。 1ビット精度を上げると、-1が表現可能ですが+1はない（つまり+128）ことに注意してください。また、乗算した結果、2つの符号ビットが結果になります。つまり、2つの積の合計が問題なく加算される可能性があります。解像度を落とした余分なビットを使用すると、実際にオーバーフローを避けることができます。もう1つのポイント - 複雑な値が1の大きさに制限されている場合（実際の実数+ img * img < = 1）、結果の合計は1を超えません。これは、正弦が1のとき余弦はゼロです。基本的に単位ベクトル（cos、sin）と複素ベクトルの内積を取っています。それ以外にも、16ビット製品を追加する前に数ビット右にシフトすることができます。おそらく丸めを行います。データとトリグ関数の両方が7ビットに丸められているため、実際には16ビットの精度はありません。

最後の1つです。多くの数値を合計して、結果が常にあなたの表現可能な範囲内にあることを知っているなら、中間結果のオーバーフローについて心配する必要はありません。それはすべて最終的にうまくいくでしょう（とにかくすべての和をゼロにするビット）。