Linuxを中心とした話題を投稿予定。 使用ディストリビューションであるFedoraが中心になると思われます。http://oedipa.wiki.fc2.com/にてTips Wikiを公開してます。
循環バッファ作成
最近備忘録的なポストばっかだな・・・。
まぁそれだけ研究してるってことですよ。実戦向きかどうかは別として(ぁ
今日は循環バッファを作ってました。C言語版。DSPに搭載するならC言語だし。全力で循環バッファ使うならアセンブラなんだけど^^; DSPアセンブラは追々勉強していこう。せっかく手元にDSPあるんだし、あいつは弄くり倒したい。浮動小数点演算可能ではあるけれど、あえて固定小数で勝負したい。ん~でもFFTとかのライブラリは全部浮動小数だったな・・・。PCでのシミュレーションなら固定小数と浮動小数に実はそこまで(クリティカルな)差は出ないから無理して使う必要もないけど、DSPでは実クロックは遅いからなぁ。その代わり並列処理が半端じゃないが。
だから余計にC言語じゃその真価を引き出せないからアセンブラ勉強する必要があるんだよなっと。勉強しとけば就職には強そうだ。就活に間に合いそうはないが^^; 話のネタに位はなるだろ、うん。
っと、話は逸れたけれど循環バッファ。信号処理では現時点からnサンプル前までのデータ列に対してどーのこーのという処理が多く、配列に対してのランダムアクセスという物はほとんど発生しない。データアクセスはシーケンシャルだし、データの追加、削除というものも先頭と末尾に集中。サンプル長も固定と結構狭い条件で動作します。要は汎用性は気にしなくていいから最適化を掛けやすいという環境といえますかね。
まー大抵実装するときは、nサンプル保存する配列を用意し、サンプルを追加するときはfor文かなんかで値を右ないし左の配列要素にコピーして次のサンプルを配列に書き込むってスタイル。まーシフトレジスタをイメージしたらまさにその通りだし、見やすさも抜群だけれど如何せん無駄が多い。けどシミュレーションではリアルタイム性を考慮してないからこんなコード平気で書いちゃうんだよなぁ・・・。これはすっごくよろしくない。値を1つ捨てて1つ入力するという作業だから大半の値は使い回し。にも関わらずn-1個の値をコピーするからそれだけ無駄に時間を食っちゃう。
で、そんなことするくらいなら捨てる予定だった値のところに新しい値を放り込んでやればいい。つまり、配列が輪になっているとイメージし、末尾まで来たら次は先頭にまた戻る。これが循環バッファ。概念は凄く簡単。アクセス時には先頭をどこにするかという下駄を履かせてやればいい。
配列長が4で、下駄(オフセット)が0ならば通常の配列のアクセスと同じ。この状態で右に要素をシフトしたとイメージする。配列の末尾の値が捨てられ、先頭に空きが出来たというイメージだ。これを下駄だけで表現しようと思ったら、先頭へのアクセスが実際には末尾を指していればよい。配列のある要素を指定した際、下駄を履かせた値が配列の要素数を超えた場合はその合計値から配列の要素数を引いた値が指したい位置になる。例えば、1度右にシフトされ、下駄が配列の末尾を指している(C言語に倣うとオフセット値は3)状態で、3番目の要素にアクセスしたい(C言語では指定する値は2)ときにどうするか。オフセットを合わせた値は3+2=5で要素数を超えている。よって5-4=1番目が本来3番目に用意されていた値、ということになる。
つまり、配列へのアクセス時に毎度毎度要素数を超えていないかのチェックをしなくてはならないと言うことになる。コレはたいそう無駄が多い。コピーは時間が掛かるといって循環バッファにしたのに、アクセスのたびにリミットチェックの条件分岐をしないといけないとなるとパイプラインが生成されず実行効率が悪い。実際そんなコードを書いたらコピーするのと大して処理時間が変わらない。
つまり条件分岐をしなければよいということになる。実はそれは簡単。剰余計算を使えばいい。指したい要素番号とオフセットの合計値を要素数で割ったときの余りが実際に指し示す要素番号となるのだ。例えばさっきの例で言えば、オフセットは3、指定する要素番号は2、要素数は4なので
(3+2)%4=1 (%はCでは剰余を返す演算子)
となる。見事同じ値を返す。アクセスの際にこうして剰余計算を行わせることで条件分岐を行う必要が無くなる。コンパイラによる最適化も掛かりやすくなると言うことなんですな。
が!これでもまだ問題が。剰余計算は基本演算の中ではすこぶる遅い!!! 除算がただでさえ遅いのにさらに余りを返さなくてはいけないと言うことで非常に時間コストがかかるんですな。if分岐に比べればマシですがやっぱり時間が掛かる。
そこでさらなる工夫。配列のサイズを2の冪乗にするという条件はつきますが、剰余計算がビット演算で可能になります。今回の例では配列サイズが4で、見事2の冪乗なので早速やってみましょう。指し示す要素番号とオフセットは同じとしますと
(3+2) & (4-1) = 1 (&はCではビット毎にANDを返す演算子)
となります。AND演算はマスクを掛けるだけなので非常に高速です。これで相当早くなります。信号処理ではFFTの都合などで配列サイズが2の冪乗に揃えられていることが多いですから非常に良く用いられる手法です。
私もこの手法を知ったときには「は~よく出来てるなぁ・・・」と感心しましたねぇ。C/C++ではどうしても関数を作ってそれを通して配列を操作しなくてはいけないため見た目にちょっと野暮ったい印象がありますが、C#ではプロパティのおかげで見た目に配列と全く同じアクセス方法が使えます。これはかなり嬉しいですね。なんせ、コードの書き換えが配列の型を書き換えるだけで済みますからw ん、C++でも[]演算子をオーバーロードしたら同じコトできたっけ・・・? いやでけんか。
まぁ下駄を履かせる方法とかちょっと混乱しそうになりますが、一度作ってしまえば後はそれを使い回すだけですしね。使う側はアクセスしたい要素番号を関数に飲ませればいいだけですし。
つーことで講座の共有にでもおいとくか。ドキュメントまでつけなくても大体分かるだろう・・・つか分かってw

スポンサーサイト



DSPってのは奥が深いな・・・
なんか色々と勘違いしていたことが発覚。畳み込みはあくまで小数同士の積和だから、ゆーても整数部の桁はほとんどいらないんだよな・・・。そんでもって符号付き16bit同士の積だと必要な桁数は31bitだとか。まー符号付きの16bitだと、実際に数値を表現しているのは15bitだから、15bit同士の積を考えればいいはず。必要な桁数は30bit、そんでもって符号ビットの1bitを加えれば31bitになるって計算でいいのかな?けど、DSPでは実際には小数部は30bitしか扱わないんだとか。なんでだ・・・?
最上位ビットを符号部、次のビットを小数第1位として4bit同士の積を考えてみる。
例えば、
0.111 = 0.875
0.010 = 0.25
の積を考えたら、最上位ビットを無視すると
       .111
x      .010
-----------
          0
      1.11
+    00.0
------------
     01.110
これを3bit右シフトした0.001110 = 0.21875ってのが計算結果になる。あとは符号ビットを加えるだけ。小数同士の積では結果は必ず1以下となるから、途中結果はどうあれ最終結果は下位ビット側に乗数の小数部桁数分伸びる(今回は3bit)。小数点の位置が同じ固定小数同士を掛けるなら倍の桁数を用意しておけばその精度同士の積が誤差なしで得られることになる。ただし、途中結果は上位側に結果が伸びるため、そちらがオーバーフローする可能性がある。今回の例でも、右シフトする前の結果は整数部に値が入ってしまっている。これだと右シフトした際に正しい結果が得られない。
ただ、予め小数部に十分な桁数を用意できているとするならば、先にビットシフトをしておいてから演算を実行すれば上位ビットへのオーバーフローは防げる。つまり、
       .000111
x      .010
--------------
             0
      0.00111
+     0.0000
--------------
      0.001110
とすることで同じ結果が得られる。これなら上位にビットが溢れることはない(はず?)。例えば
0111 = 0.875
0111 = 0.875 の積を考えると、
       0111000
x      0111000
--------------
     0111000000
   0111000000
+ 0111
000000
--------------
  110001000000

となり、3bit右シフトすると0.110001000=0.765625となります。予め3bitずつ右シフトしておいたとすると、
      01110000
x     00001110
--------------
       1110000
      1110000
+    111000
0
--------------
   01100010000

となり、0.110001000となるため同じ結果が得られます。どちらの方法をとったにせよ、下位3ビットは確実に0となるため、本来符号bitを除けば7bit確保できるけれど6bitで十分と言うことになります。これを単純に32bitに置き換えて考えると、なるほど確かに小数部は30bitで事足りるという結論が導けてしまう・・・。ほんっと、昔の人は賢いよな・・・。
ところで、実はこれでもまだ具合が悪い。整数と見立てて考えると分かりますが、符号bitを含めて4bit同士の積を考えていますから、その結果は明らかにオーバーフローしています。これは具合が悪い。ならば今度は両方を3bit右シフトしておき、結果を3bit左シフトすることを考えます。
       00001110
x      00001110
---------------
       00001110
       0001110
+      001110

---------------
       01100010

これでオーバーフローの心配がなくなるはずです。というより、溢れた桁の分は捨て置くのでこれで4bit同士の固定小数の演算結果が得られていることになります。取り出すときにはこれの上位4bitを取得すればよいことになります。つまりは0.75となるわけですね。まぁ取り出すときだけ丸め処理を入れればいいと言うことだけ押さえておけば十分でしょう。
が、これは積の場合で、除算はまた違った結果を生むんですよね・・・。被除数の絶対値が除数の絶対値よりも大きければ絶対値が1以下に収まりますから問題になりませんが、そうでない場合、絶対値が1を超えるのでオーバーフローを起こす羽目に。
ん~、今度実装するアルゴリズムは学習同定法がベースだし、どう考えたって絶対値は1超えてくるんだよな・・・。DSPで学習同定法を実装するときってどうやってんだろ・・・? まっさか浮動小数ではないだろうしなぁ・・・。FFTは絶対値を1以下に抑える方法がちゃんとあるからいいけれど、逆フィルタの生成とかだと除算が入ってくるだろうし・・・。調べてみるか。
ふぅむ、実用レベルまで持って行くのはかなりしんどそうだな・・・^^;