DFT IPの作成 9

このところ、寝ても覚めても誤差のことで頭がオッパイだ。いや、イッパイだ。

今回のアルゴリズムの式は以下であった。

この式で、簡略化のためにxp-xp-Nをxp、exp(j2πf/N)をkとし、またこの演算で発生する誤差をεp(複素数）として以下のように表す。

すると、この式は以下のように展開できる。

さらに、書き直すと、

となる。したがって、誤差成分は以下のようになる筈だ。

kはexp(j2πf/N)なので値域は-1.0～+1.0だ。　εは浮動小数演算の仮数部で発生する丸め誤差だが、大きさは指数部の値によって決まる。入力信号は16bit整数であり、これまでは、これをそのままの大きさで演算していた。この場合、指数値は2^-15から2^15の範囲となる。これを最大値(32768.0)で正規化すれば、exp()とスケール感が同じになるので誤差も小さくなるかも？と考えた。しかし、これは単に縮尺を変えているだけとも言えそうなのであまり違いはないのかも知れない。そこで、実際どうなるか、単一周波数のスペクトルで見てみた。

以下は正規化していない場合（ログ表示）


以下は正規化した場合
。

やはり、違いはなかった。

では、乗算や加減算で丸めをせずに切り捨てしたらどうなるかを見てみた。coregenで生成する演算器は丸めの有無を選択できないため、この確認の為には乗算器と加減算器を自作する必要がある。

乗算器は以下のようにした。


加算器は以下のようにした。


減算器(y=a-b)は、基本的に加算器のRTLを流用しb入力の符号を反転して使った。

結果としては、乗算器のみ丸め無し版に置き換えた場合は結果にほとんど違いがなかったが、加減算器の場合のはより悪くなり、スペクトル波形が激しく振動したような、無茶苦茶noisyな波形になってしまった。

ということで、誤差対策としては、縮小係数をかける方法と、一定回数毎にアキュムレーションRAMをクリアする方法のどちらかしか出来なさそうだ。他に変数の桁数を広げる（単精度小数を倍精度にする。）というのも考えられるが、回路規模がデカくなる、タイミング的(100MHz動作）に厳しそうだ、桁数を広げたとしても量子化された値での演算である以上は誤差は必ず発生し累積されてくる、等々考えて桁数を広げる案は止めにした。

では、2者の内どちらが妥協できるか？ということで、それぞれの場合の波形を比べてみる。

2048点毎にアキュムレーションRAMをクリアする方式の場合は以下のようであった。


見事に線スペクトルになっているように見えるが、上記はログ表示であり、これを絶対値表示（√r^2 + i^2）にすると以下のようであった。 （ちょっと変だ）


一方、縮小係数をかける方式の場合は以下のようであった。

ログ表示


絶対値表示


と、言うことで今回は縮小係数をかける方式で妥協しちゃおうかと考えている。

学生のときにもっと数学を勉強しとくんだった。 (;_;)

DFT IPの作成 8

RTL全体でシミュレーションしてみたところ、以下のような結果だった。


上記は開始から約10msecの時点での波形だが、右端に小さなピークが見える。
入力信号は上図の左側のスペクトルに対応する単一周波数の正弦波なので、右側のピークはおかしい。　さらに波形とRTLを追って見たところバグっている箇所が分かった。入力信号は1024点の演算実行期間、値を保持していなければならないのだが、それが抜けていた。
（単体シミュレーションではテストベンチ側で値を保持していた。）


上記波形でxpが入力信号であるが、値が保持されていない。
これを以下のように修正した。


xdはxp - xp-Nの結果で、16bit整数値で演算してその結果を32bit浮動小数に変換しているが、この変換器でstb信号を入れて変換結果を保持させるようにした。
この修正の結果、表示されるべきスペクトル（上図の場合は左側）のみが表示されるようになった。

但し、誤差問題は解決していない。
これまで、Cモデルやシミュレーションでは発生せず実機動作で発生すると考えていたのだが、これは誤りで、恐らく、Cモデルやシミュレーションでも誤差は発生している。これが見えなかったのは実行時間が短すぎたためと思われる。シミュレーションの場合、私はIcarus verilogでシミュレーションをしているが、全体シミュレーション環境で10msec程度をシミュレーションするのに１２時間位要している。シミュレーション時間はRTLのノード数・・・というか回路の規模に比例する。浮動小数乗算器や加減算器等はcoregenで生成したモデルを使用しているが、これはネットリスト形式になっているので、演算器の部分はゲートレベルシミュレーションしているようなもので、これもシミュレーション時間が長時間になる要因になっているだろう。しかし、誤差問題はこの演算部分に関わることなので、ビヘイビアモデルを作って置き換えるという訳にもいかない。何れにしてもシミュレーション時間が短すぎる為に、誤差問題を見落としていたのは間違いないだろう。

で、この誤差のキャンセル方法について、これまでに考えたのは次の2つだった。
1. 2048点演算毎にアキュムレーションRAMをクリアする。
2. 縮小係数をかける。

結局、1の方法で普通に2048点毎の演算としたほうがいいのかも知れない。

DFT IPの作成 7

乱れている～、乱れている～、検量線っがー、
おーかしいよとー、言われるけどー、しーかたがない～のー

っていうフレーズが何故か頭の中でリフレインしている今日この頃如何お過ごしでしょうか？
あれは、黒木真由美の感情線だっけか？、懐かしいなぁー、あの頃は俺も若かったぁ、
色んなとこブヒブヒ言わせてさぁー、、、、太ってたからねぇー
それが、今じゃ、こんなに痩せ細っ・・・、あれ？、細ってない。むしろ増えてる！！！　おっかしいなー

なーんて言うおバカキャラはこれぐらいにして、DFT IPのデバッグだ。
いやー、ストレスが溜まってるときはこの位バカして発散しないと、ねぇ?

元々考えていた方式でやると、入力がゼロになってもアキュムレータRAMに値が残り、時間経過と
共に増加していくという問題が出た。以下はその様子だ。

画像では、入力値がゼロになってからのスペクトルの成長が分かり辛いが、じっと眺めてると、
所々で少しずつ成長しているのが分かる。
入力値がゼロになっていく過程で、アキュムレータRAMの値も減少していく筈なので、値が残るという事自体おかしな事なんだが。

やっている事（回路で処理している事）は、


という演算で、入力値ゼロの状態が継続すると、Xp-Xp-Nは0-0になるから、S(f,p)は増えもしなけりゃ、減りもしない筈で、正に何も足さない・何も引かない状態になる筈だ。が、その絶対値であるスペクトルが徐々に成長するってことは、上記演算過程で何らかの要因でプラス方向の誤差が発生していると考えられる。また、S(f,p)は複素数であり、これに複素数の定数が掛かる訳だから、exp(jα) x exp(jβ) = exp(j(α+β))な訳で、複素平面で考えると、ベクトルを常に回転させていることになるが、これが誤差により外側に膨らんでいっていると考えられる。

そこで、S(f,p)に1.0より小さい縮小係数を乗じて見ることにした。但し、その為に態々乗算器を追加するのは回路の無駄なので、正弦波テーブル(exp(j2πf/N)のテーブル）の値を縮小することにした。具体的には以下のプログラムでテーブルを作り直した。

0.9999fが縮小係数だ。 上図の通り、これ以外の値も試してみたが0.9999より大きいと効果が弱かったり、まったく効かなかったりだった。

このテーブルを使って上記と同じデータを再生してみたのが以下の画像だ。

でも、良く良く考えてみると、何かおかしい。 Cモデルでの検証ではこういう現象は出てなかった。
32bit浮動小数点データは仮数部が24bit（省略されている最上位の1を含む）のみであり、位の違う数値同士を演算した場合、当然ながら、その有効桁の範囲外に値が出ることもある。この場合に丸め処理を行う訳であるが、これは「最近点への丸めモード」としてIEEE754で規定されている。っていうことが色んな文献に書いてあるが、CQ出版の「ディジタル数値演算回路の実用設計」という書籍の表6-2がとても解りやすい。　この丸め処理がcoregenで生成した浮動小数演算器と、Cの処理系とで違うのかな？と考えて検証してみたが同等だった。

それではということで、単一正弦波のデータを作って再生させて線スペクトルになるかを見てみた。


その結果が上記画像で、線スペクトルになっているが、右端にも想定外のスペクトルがいる。
DFTは2048点で演算していて、その内の半分の1024点を表示しているので、折り返しは表示されない筈だし、Cモデルによる検証でも、また、DFTモジュールの単体シミュレーションでも表示されていない。
おまえ・・・誰？ (-_-;
ってな感じだ。

どっかバグってんのかな?、全体でシミュレーションやってみるか。

statistics

今日のページビューの中で、これは日本からだが、「dft+面白い」という検索から、このブログに来た方がいるようだ。。。これはウケた。「dft+おばか」だったらもっとウケたのに。


このブログのページビューは今年の夏頃一時的に1000件/月を越え、その後、ブログの更新の停滞と共に減少していたのだが、ここ最近増加傾向にある。不思議なのが、最近はアメリカからのページビューが増えている。日本語で記述している上に、それでも読みづらい文章の筈なのに、不思議だ。インタネットを自動で検索して回るソフトウェアによるページビューかも知れないな。



ちなみに、ブログを開始してから全期間の統計は以下の通りだ。
bloggerのシステムでは国名は上位10迄しか表示されないようだ。
過去、ここにリストされていない国名を見た記憶があるので実際はもう少し多いと思う。


内容としてはYUV422について書いたのがもっとも多く参照されている。

YUV422に関しての情報は意外とネットに転がっていないのかも知れない。
私の文章も大して中身は無いので、その意味では申し訳ない。

そうそう、統計つながりで、dviencのダウンロード数がもうすぐ300に到達しそうだ。
去年の10月に200だったので、１年で100件程の増加だ。


国数は32ヶ国に増えた。




おそらく絶対に有り得ないとは思うが、全大陸制覇したら、俺、興奮しちゃうね。

DFT IPの作成 6

実機で動かしてみた。

現状のSystem Architectureは以下の通り。

AC97コントローラの再生のRchをDFTに入力し、DFTの出力をDRAMを介さず、直接VIF(フレームバッファ)に入れている。  VGAの表示サイズがXGA (1024x768)で横方向がDFTの出力データ数と一致するので、VIFのsyncgenのxadr(水平方向カウンタ）の値をDFTのpramのアドレス入力として与え、その出力をsyngenのyadr（垂直方向カウンタ）の値と比較して、hitした場合に赤、hitしない場合に黒を出力するようにして、スペクトル表示を行うようにした。
以下はDFTの当該部だ。


また、以下はVIFの当該部だ。


この構造で音楽データを再生させながらスペクトル表示させて見たところ、再生終了（音量がゼロ）後もスペクトルが残ったり、また、そのまま放置しておいても、スペクトルが徐々に増加したりといった現象が見られた。どうも、演算誤差の累積が原因のようだ。　そこで、とりあえず、データ入力2048点毎にアキュムレータの値をクリアするようにして、動作確認を進めてみることにした。これは2048点毎にDFTを実行することと同じことになるが、この回路の設計思想からは外れるので、誤魔化しではある。dft_coreの当該部を以下に示す。 165行目のscntでデータをカウントし、2048個に到達するとsclrが1になり、アキュムレータRAMからのリード値を0に置き換えている。(180,181行目)


回路規模だが、現状 dft_core部は以下の通りだ。


dft_core部の中身はDFT演算のみであり、絶対値演算と平方根、対数変換はdft_powerという別のモジュールで行う。この、dft_power部の回路規模は以下のようになった。


現状、浮動小数演算器はハードウェア乗算器(DSP48)を使わない構成で生成しているため、LUTの使用量が大きくなっている。
dft_top (dft_core + dft_power)部としての規模は以下のようになった。


これまでの数値は、論理合成結果なので、マッピング後の結果とは若干違ってくるかも知れない。

また、何とかこれをSpartan3E 250Eにも入れられないかとやってみたのだが、駄目だった。
ムググッ、おのれ250Eめ、今度固定小数方式でリベンジしてやる。
（その前に、誤差問題を対応する必要があるが。）

Spartan6 xc6slx45への、全体の合成・マッピングは出来て、タイミングもMetした。


で、データを再生して表示してみた。

これは、絶対値を平方根した値を表示している。
これの対数変換による表示は以下だが、ちょっとパッとしない。

サイレン音を再生・表示してみた。サイレンの音程の変化に合わせて、スペクトルが移動する様が、ちょっと面白い。

次に、自動車の通過音をやってみた。

音楽をやってみた。

きゃ～～、>_< アレサー、、おしっこチビりそう。

今度はテンポの早いやつをやってみた。

いやー、めでたい。ウチナーンチュ最高！ (俺、ウチナンチュでっす。)

これで、誤差問題が解決すればもっとおめでたい。
DFT演算ではexp(2πf/N)を乗じているので、ベクトルを常時回転させていることに相当するが、入力がゼロでもスペクトル値が増加すると言うことは、演算誤差により回転時に外側に膨らんでいっていると考えられる。だから、内側への補正が出来れば解決出来そうな気がするのだが、、、要検討だ。

げっ！、もうこんな時間だ。寝なきゃ。

DFT IPの作成 5

この土日は色々と野暮用があって作業が捗らなかった。
Nを2048にし、演算はその半分の1024のみを行うようにし、また、対数変換器を作成し
RTLに組み込んでシミュレーション実行までは出来た。
以下、上段は絶対値のスペクトルで、下段が対数でのスペクトルだ。


あ、それと、各種浮動小数演算器のレイテンシーも現実的な値で生成し直した。
具体的には乗算器・加減算器ともに4にした。
もう少しで、実機での動作確認に移れると思っており、AC97コントローラに組み込んで動作させてみるつもりだ。　が、ここで、対数値を20倍すべきか10倍すべきかが心許なくなってきた。。。
表示しようとしているのはパワーか？電圧か？で変わってくるはずだが。
こま～～～～けぇ～～～こたぁ～～～、いいから一度実機で動かしてみようか。
落ち着いて考えよう。

DFT IPの作成 4

今回は位相角は表示するつもりはないのだが、面白いのでちょっと検討してみた。
位相角はDFT出力のsin,cosから以下のように求める

ここで、sinθ,cosθがそれぞれ以下のような指数形式で表せるとすると、

となり、除算がなくせる。
そこで、tan^-1を例によってテーブル方式とする場合、インデックスはα^βになる訳だが、
α^βはβから一意に定まるので、インデックスとしてβを使うようにしても良いはずだ。
即ち、

という訳で、前回検討した対数変換器でsinθとcosθの対数を求め、その差分をインデックスとしてテーブル参照すればθも求められるのではないかと思う。
但し、0°や90°等の特異点は別に判定する必要があり、処理イメージとしては以下のような感じか?

この方式はテーブルの持ち方が肝になるような気がするのと、精度や回路規模、スループット、レイテンシー等の面でどれほど実用性があるかは疑問（ちゃんと考えていない）が、sinθ/cosθの除算をしなくて済むというのは面白い。

DFT IPの作成 3

DFTで求まるのは実数部と虚数部からなる複素数であり、スペクトルとして表示するためにはこれの絶対値(sqrt(r^2 + i^2))に変換する必要がある。  また、通常、対数表示されるので対数変換も必要になる。  この対数変換器について検討した。
まず、対数は以下のように任意の数を指数形式で表した場合の指数部のことであり、a(底)が10の場合を常用対数、ネイピア数の場合を自然対数と言う。スペクトルは常用対数で表す。

今作成しているDFT IPは内部演算を32bit単精度浮動小数形式で行っているが、対数変換を考える場合この浮動小数形式は都合が良い。  32bit単精度浮動小数は数値を±1.M×2^e 形式で表す。構造は以下のようになっている。

sは符号で0が正数、1が負数、exponent(e)は指数部、Mantissa(M)は仮数部である。
指数部は本来は整数で+/-の値を取りえるが、この形式では+127のオフセットが加算され正数となるようになっている。仮数部は整数部（1または0)が省略され小数部23bitのみが含まれる。
また、指数部と仮数部の特定の値の組み合わせに対して以下のような状態が割り当てられている。

このDFT IPでは値が不正規化数や無限大、非数になることは有り得ないので、正規化数に限定して検討を進める。 また、符号は負になることはないので正に限定して考える。

であり、仮数部の対数値(m)とオフセットを引いた指数部の値を加算すれば対数値が求まる。
次にmについて考える。

であり、グラフにすると以下のようになる。

凸型の曲線になっているので、計算して値を求めようとすると多項式か何かでの近似計算となりそうであり、それよりは、テーブル参照方式で求めたほうが良さそうだ。その場合、Mの小数部の上位何bitかをインデックスとして用いることになる。4,6,7,8bitの場合について見てみた。

当然だがbit数が多い程誤差は少いが、今回の用途では6bitでも良さそうな気がする。
つまり、64x32bitのテーブルを作成することにする。  対数変換器への入力は二乗和の平方根だったが、sqrt(x)はx^1/2であるので、開平せず二乗のまま対数変換をしその結果を2で割るという方法も可能で、こうすればsqrt演算器を省略することができる。ここまでの処理で求めた値は2を底とする対数値なので、最後にこれを常用対数に変換する必要がある。これは(log210）^-1をかければいい。ここでもlogが出てきてしまうが、固定値なので定数化できる。
と、言うことで、ここまでの処理イメージをまとめると以下のようになる。

AC'97 Codecを制御してみる 5

AC97コントローラのsnapshot版を以下に公開した。
（今作成中のDFT IPの前にやっていたやつです。）

http://www.hi-ho.ne.jp/bravo-fpga/

DFT IPの作成 2

RTLだが、まずは1024点版を作ってみている。 演算部は当初、整数部16bit、小数部16bitの固定小数方式でやってみたのだが、累積誤差が大きくなるので結局、浮動小数方式でやることにした。

現状のRTLは以下の通りだ。ただし、まだ最終型ではない、シミュレーションでの動作確認用と言ったところだ。

dft_core.v ... ipコアのトップモジュール

5行目はステートマシンで、rst解除後の内部変数（テーブル類）の初期化と、演算回数の処理を行う。　mul_fp32, add_fp32, sub_fp32, は浮動小数演算器で、ISEのCoregenで生成した物を使っている。今回は動作確認の段階なので、レイテンシーは1にしているが、100MHzで動作させる場合は、おそらく、3～4位にする必要があるだろう。従って最終的にはパイプラインの段数が増加する。

dft_dlyline.v ... xp, xp-N用の遅延モジュール


dft_arctbl.v ... sin,cos値のテーブル

1/4周期分のみromに持ち、残りの部分の値はこれを写像して生成している。
romの中身は32bit float形式だが、このデータは以下のようにプログラムを書いて作成した。


dft_spctbl.v ... スペクトル値保持用モジュール


実態は只のRAMだ。

RTLとしては浮動小数演算器を除いては以上で、結構シンプルに出来ていると思う。
但しスペクトル値にする為には、さらに乗算器2個と√演算器、log演算器等が必要になる。

以下はシミュレーションの様子だ。  基本周期の64倍の正弦波を入れている。


上記の拡大


現状1024点としているがスペクトルの折り返しがあるので使えるのは半分になる。
従って、有意な1024点を得るためには計算は2048点で行う必要があるが、DFTの場合、必要な分のみを計算できるので、Nが2048点でありながら計算は1024点のみを行うようにも出来る。
また、スペクトル波形を画面表示することを考えるとこの位の点数で十分な気がしている。


いや～～っっっ、 FPGAって本当に面白いですね !!