６４点高速フーリエ変換回路

## ６４点高速フーリエ変換回路　設計仕様書 (Ver
1.0)

2006/8/30　ver 1.0作成

琉球大学工学部情報工学科　和田　知久

#### [０]　はじめに

「LSIデザインコンテストin沖縄」も早いもので、今回で１０年目を迎えることになりました。１９９８年に第一回のLSIデザインコンテストが開始された時は、琉球大学工学部情報工学科内部での学生コンテストでしたが、回を重ねるごとに、学外、国外と参加者の枠が広がりました。最近数年には、約１００名の学生の参加があり、３月の沖縄での発表会では１０件前後の優秀デザインの発表会を行い、みんなで大いに盛り上がっています。２００1年度よりCQ出版社と協力を開始し、デザインウエーブ設計コンテストとしては第7回となります。

そして設計するテーマも時代を反映した内容を努めて出題するように心がけてきました。第１回の「LSIデザインコンテストin沖縄」を立ち上げてくださったのは、当時、琉球大学工学部情報工学科学科長の翁長健治教授（現琉球大学名誉教授）であり、LSI関連教育担当の尾知博教授（現九州工業大学教授）でした。当時、和田は三菱電機の社員であり１９９９年５月に琉球大学に転職してから、このコンテストを引き継ぎ運営させていただいています。今回１０年目ということで、以下表１に過去の「LSIデザインコンテストin沖縄」設計課題を示します。

#### 表１．過去のLSIデザインコンテストin沖縄　設計テーマ

回 西暦 設計テーマ 応用
第１回 １９９８年 KUE-チップ マイクロプロセッサ
第２回 １９９９年 RSA暗号デコーダ 暗号
第３回 ２０００年 リードソロモンCODEC演算エンジン CD、デジタル通信／放送用エラー訂正
第４回 ２００１年 デジタルCDMAレシーバー 携帯電話、無線LAN
第５回 ２００２年 差集合巡回符号エラー訂正回路 TVの文字放送、地上デジタル放送
第６回 ２００３年 静的ハフマン符号用可変長デコーダ 音声圧縮、画像圧縮、動画圧縮
第７回 ２００４年 共通鍵暗号AES用SubByte変換回路 無線LAN、通信暗号化
第８回 ２００５年 デジタルFMレシーバー 無線通信・放送
第９回 ２００６年 ２次元積符号繰り返しデコーダ 広域無線LAN
第１０回 ２００7年 ６４点高速フーリエ変換回路 信号解析、OFDM通信、無線LAN

さて、第１０回の設計テーマですが、デジタル信号処理では必ず登場する高速フーリエ変換回路（Fast
Fourier Transform Circuit）の設計です。高速フーリエ変換は離散フーリエ変換（DFT)を高速に計算する手法であり、計算式自体は単純であり、以下に示す式になります。今回は802.11a/g/nなどのワイヤレスLANでよく使われているサイズということで、６４点のFFTすなわち、以下の式でN=64の場合になります。

離散フーリエ変換の定義式は単純ですが、入力となるx(n)信号は、６４点あり、またすべて複素数であり、出力X(k)も６４点の複素数ということになります。このコンテストは学生対象のコンテストですので、学生対象対象としては６４点は丁度良いサイズと考えています。以下にFFTについての詳細や、デジタル回路での実現方法を丁寧に説明しますので、これまで、上記式は知っていても物理的イメージが湧かなかった学生にも良い教材になると思います。要求されている設計はHDL（VHDLもしくはVerilogHDL）による設計と論理合成です。特にシノプシス社の合成ツールを使用する必要はなく、FPGA等の合成ツールでも参加できます。HDL設計に興味のある学生はどしどし参加してください。また、余裕のある方はFPGA等で実装すれば、努力を認めて高い評価が得られると思います。FPGA等での実装もぜひトライしてみてください。

図１　システム図

図１に今回想定するシステムのブロック図を示します。システムは大きく分けて、送信信号生成部（Sender）、そのSenderの出力信号を高速フーリエ変換するFFT部から構成されます。複素数の信号はそれぞれ、実数部分をIポート、虚数部分をQポートを使用します。６４ポイントの信号入力が必要で、図に示すように６４点がシリアルに入力されることを想定し、FFTされた出力信号もシリアルに出力されます。

図１では、示されていませんが、６４点の先頭の信号を示すフラグ信号も与えられ、64点の先頭位置をFFT回路は把握することができます。

#### [１]　離散フーリエ変換と逆変換

離散フーリエ変換は通常スペクトル解析に使用されます。イメージとしては以下のようになります。x(n)は解析するN点の区間で、ほぼ１周期の正弦波となっています。これを離散フーリエ変換（DFT）を行うと、右の図のようにk=1に大きな成分が現れ、元信号x(n)にはk=1の周波数成分が多く含まれることがわかります。このような解析をスペクトラム解析と呼びます。よく見るとk=N-1の部分にも大きな成分があります。DFTでは、N点の点が周期的に繋がっている関係にあり、k=N-1は実はk=-1の周波数を示すことになります。負の周波数とは理解が困難かも知れませんが、x(n)の１周期の波形は、K=-1の周波数とK=1の周波数成分からできていると考えることができます。

図２　DFTによるスペクトラム解析

以下に離散フーリエ変換（DFT）とその逆変換である逆離散フーリエ変換（IDFT）の式を示しておきます。N点のx(n)信号をN点のX(k)信号に変換するのが、DFTであり、その逆がIDFTです。DFTを高速に演算する方式がFFTであり、IDFTを高速に演算する方法がIFFTですので、以下、DFTをすべてFFT、IDFTのことをすべてIFFTと呼ぶことにします。ただし、FFTではNは２の指数乗である制約があります。

２つの式をよく見ると以下の２つの違いがあります。

１）　最初に1/Nがあるかないか

２）　指数のjの前の符号

したがって、２つの変換は非常に良く似たものであり、以下の図に示すように、FFT回路があれば、IFFTを簡単に実現することができます。

図３　FFT（DFT)によるIFFT（IDFT)の実現

#### [２]　FFT演算の中味

さて、今回設計するFFTの式を見て行くことにしましょう。ここでは式をTwiddle
Factor WNを用いて変形しています。

Twiddleとは指でぐるぐる回すという意味ですので、回転を示すものです。ここで２次元平面を用いて、このTwiddle
Factor WNを説明します。

Eulerの公式より以下が成立します。これをX軸を実数(Real)軸、Y軸を虚数(Imaginary)軸とする２次元平面に示すと以下のようになります。

図４　Eulerの法則と２次元複素平面での表示

すなわち、ejθという関数はθを変化させることによって、半径１の円周を回転する点を示すことになります。フーリエ変換ではこの複素平面での回転を使って、波を解析します。したがって、半時計回りの回転は正の周波数に対応し、時計回りの回転は負の周波数に対応することになります。

したがって、Twiddle Factor WNを複素平面に示すと図５のようになります。実際FFTの式ではこのTwiddle
Factor WNは指数乗されますので、指数が増加すると、図に示すように、複素平面で時計方向の回転をすることになります。

図５　Twiddle Factorの意味

以下のFFT演算の内容をさらに理解するために、４点FFTを行列表現したものを図６に示します。N=4ですので、行列表現では4X4のTwiddle
Factorが並ぶ行列ができます。Twiddle
Factorは図６右に示すように、W0, W1,....の順で複素平面状の半径１の円周を回転します。

図６　４点FFTの行列表現

このTwiddle
Factorの行列に数値を入れたものを図７に示します。一行目は１が並び、これは同じ値が続く周波数０の回転に対応しています。２行目は、1,
-j, -1,
jとなり、これは複素平面状での負の方向への１回転を示しています。３行目は1,
-1, 1,
-1となり、これは複素平面状での２回転を示しています。３行目は、1,
j, -1,
-jとなり、これは負の方向への３回転ですし、正の方向への１回転と考えることもできます。
すなわち、FFT演算とは複素数による回転を示す波形の周波数の異なるものそれぞれと、入力信号x(n)の内積計算をしていることになります。

図７　４点FFTの行列表現

#### [３]　基底４での　６４点FFT演算アーキテクチャ

通常FFT演算で教科書を見れば、バタフライ演算が使われています。特にRADIX-2バタフライという演算が使用されています。しかしながら、このLSI設計コンテストでは、現実的に実装の観点から効率の良いRADIX-4（基底４）バタフライ演算を前提に、６４点FFT回路の演算方式を紹介します。

64=43であるので、FFTにインデックスを以下のように変数変換します。各Σの加算個数は４個で、3重のΣからなる式に変形できます。この一つのΣが１ステージの処理となり、３段で全体の処理が行えます。

#### （ステージ１）

まず最初にn2に関するΣを展開し、変形ます。ここで、Twiddle
Factor WNの性質、(WN)0=1, (WN)1N/4=-j,
( WN)2N/4=-1, ( WN)3N/4=j
が用いられています。

ここで、以下のようにx1をおくと、以下のようになります。

x1は４つの値に、ｊや-1などを掛けて、加算した後にTwiddle
Factor を乗算しています。このx1の計算が第１ステージの演算となります。次に、このx1を入力として、上記計算を行えばX(k)が求まりますが、これは16点FFTの式となります。ただし、k0=0,
1, 2, 3の場合があり、１６点FFTを４回計算する必要があります。

#### （ステージ２）

さらに上式を同様に変形します。

したがって、第２ステージの計算は上記x2を求めることになりますが、これはステージ１で求めた計算方法と同じであり、これをRADIX-4バタフライ回路と言います。

#### （ステージ３）

さらに上式を変形すると以下のようになり、同様のバタフライ演算になりますが、ただし、Twiddle
Factor の乗算が不要となっています。

#### （リオーダーステージ）

ここでx3(k2+4K1+16K0)が計算されましたが、本来のINDEX値は(k0+4K1+16K2)であり、INDEXの数値が入れ替わっています。したがって、INDEXの正しい出力を求めるためには、

以下で示されるような、関係で数値を並べ替える必要があります。

この計算アーキテクチャを図８に図示します。

図８　RADIX-4　６４点FFTアーキテクチャ

#### MATLABによるRADIX4 64点FFT

以下にここで説明したRADIX4による６４点FFTの処理を行うMATLAB関数ファイルをリンクします。

MATLABによるRADIX4　６４点FFT　：　myfft64.m

このFFT処理を理解するには、MATLABコードを読む方が容易です。また、MATLABでは配列のINDEXが０ではなく、１から始まるので、x,
x1, x2, x3, yの値はINDEX=1が最初であることに注意してください。

今回のデザインコンテストでは、要はこのMATLABコードを回路で実現するので、FFTを完全に理解しなくても、このmyfft64.mを仕様として設計を進めることもできます。

#### SCILABによるRADIX4 64点FFT

以下にSCILABによるRADIX4による６４点FFTの処理を行う関数をリンクします。

SCILABとはフリーの科学技術演算ソフトウエアで、

http://www.scilab.org/

より入手することができます。

SCILABによるRADIX4　６４点FFT　：　myfft64.sce

以下に英語による簡単なマニュアルをリンクしておきます。　：　HowToScilab.pdf

#### [４]　シリアル処理による６４点FFT

６４点FFTのひとつの実装方法として、シフトレジスタを用いるシリアル処理のFFTを説明します。
上記セクションの６４FFTの処理アルゴリズムから、３つのステージで処理し、そしてリオーダーが必要なことは理解されたと思います。
STAGE1では、１６点ずつ離れた４点から、１６点ずつ離れた４点の出力を計算しています。また、STAGE2では４点ずつ離れた４点から、４点ずつ離れた４点の出力を計算し、STAGE3では隣接の４点から隣接の４点を計算します。

#### （STAGE3　４入力シリアルFFT）

このような処理をシフトレジスターを用いた方式で処理することができます。以下の図９はSTAGE３の連続４点のFFT処理を示したものです。左側の正方形はフリップフロップによるシフトレジスタを示しており、計７段のシフトレジスタを構成しています。毎クロックごとにx2入力がシフト入力され、中断の切り替え回路（マルチプレクサ）により、RADIX-4バタフライ回路の入力に４つのx2入力信号が渡されます。RADIX-4バタフライ回路はこの入力に対してステージ３に必要な演算を行います。図中に演算を示していますが、各入力に１、ｊ、－１、－ｊを乗算して加算を行っています。虚数単位ｊの乗算は複素数のReal成分とImaginary成分の交換や符号反転で実現できるので、RADIX-4バタフライ回路には乗算は必要なく加算器などで構成されます。最終出力に複素数のTwiddle
Factorが複素乗算されていますが、STAGE３では実際にはTwiddel
Factorは１なので、乗算の必要はありません。

図９　STAGE3　４入力FFTシリアル処理アーキテクチャ

以下図１０に図９の動作波形を示します。まず、HEAD信号は’１’で入力の開始を示します。黄色で示される４点が最初のFFT処理すべき入力値です。R0からR6はシフトレジスタの値で、値がシフトしていることがわかります。PHASEはHEAD信号から生成され、S1,
S2, S3のスイッチ信号を生成します。結果的に、A, B, C, Dに黄色で示される４点がシフトして現れ、RADIX-4バタフライ回路にて、OUTが計算されます。また、OUT出力の先頭を示すために、OUT_HEADなる信号が示されます。OUT_HEADはHEAD信号をこの処理のレイテンシーのサイクル遅延したものになっています。

図１０　STAGE3　４入力シリアルFFT動作波形

#### （他のステージの処理）

他のステージの処理は、上記STAGE３のシフトレジスタの長さを変更し、やや制御を変更することで実現することができます。また、Twiddle
Factorの複素数を生成して、複素乗算することも必要です。以下に参考までに、STAGE２の場合を示しておきます。これから容易にSTAGE1の処理が類推できます。

STAGE２の場合４点おきの入力点を使用するので、シフトレジスタのR0,
R1, R2, R3, R4, R5, R6間の段数は４段となります。また、連続の４点を処理している間はPHASE同じであり、４入力点ごとにPHASEをカウントUPします。後は､STAGE3と同じですが、最終段にてTwiddle
Factorを乗算します。

図１１　STAGE２　の処理回路

STAGE１では、シフトレジスタのR0, R1, R2, R3, R4, R5,
R6間の段数は１６段となります。

#### （リオーダー）

STAGE３の出力は

のx3(0), x3(1), x3(2), x3(4), ...の順に出力され、これは本来のFFT出力に変換すると、X(0),
X(16), X(32), ...のような出力になります。以下に対応表を示します。このリオーダーを実装するには、FFなどのフリップフロップが必要です。しかしながら、下図表を良く見ると規則性があり、ランダムアクセスメモリやシフトレジスタなどで、リオーダーの実装ができそうなことがわかります。

#### 表２．リーオーダーの順序

x3(k2+4k1+16k0) X(k0+4k1+16k2) x3(k2+4k1+16k0) X(k0+4k1+16k2) x3(k2+4k1+16k0) X(k0+4k1+16k2) x3(k2+4k1+16k0) X(k0+4k1+16k2)
0 0 16 1 32 2 48 3
1 16 17 17 33 18 49 19
2 32 18 33 34 34 50 35
3 48 19 49 35 50 51 51
4 4 20 5 36 6 52 7
5 20 21 21 37 22 53 23
6 36 22 37 38 38 54 39
7 52 23 53 39 54 55 55
8 8 24 9 40 10 56 11
9 24 25 25 41 26 57 27
10 40 26 41 42 42 58 43
11 56 27 57 43 58 59 59
12 12 28 13 44 14 60 15
13 28 29 29 45 30 61 31
14 44 30 45 46 46 62 47
15 60 31 61 47 62 63 63

#### [５]　固定小数点フォーマット

今回の課題では0.0625のような小数点以下の数をデジタル回路で取り扱う必要があります。たとえば４ビットの２進数”０１１１”ですが、小数点をどこの位置に置くかで表す値が変わってきます。たとえば、”０１．１１”ならば１０進数表現では＋１．７５、”０１１１．”ならば、１０進表現では＋７です。

また、４ビットの２進数ですが、それが符号無し数すなわち正または０の数を表しているか、２の補数表現で正または負の数を表しているかを区別する必要があります。”１１．１０”は符号無し数であれば、１０進表現で+3.50となり、２の補数表現であれば、１０進表現で-0.50となります。

すなわち、同じ４ビットの２進数でも、「小数点の位置」と「符号無し表現か２の補数表現か」を明確にしないとまったく異なった数に対応してしまいます。

ここではSignal Processing Workbenchで用いられている固定小数点の属性表記方法を解説し、用います。

<8,2,t>

と表記すると、その信号は

８　：　全体のビット数が８ビット
２　：　整数ビットが２ビット
ｔ　：　two's complement
ということで２の補数表現、すなわち最上位ビットは符号ビットとなる

という意味です。したがって、”０１１０１１１１”なる８ビットの数の属性が<8,2,t>とすると、

0 1 1 0 1 1 1 1
符号ビット 整数部

小数部

ということになり、小数部は５ビットとなり、１０進表現では＋３．４６８７５に対応します。

<8,2,u>

と表記すると、その信号は

８　：　全体のビット数が８ビット
２　：　整数ビットが２ビット
u　：　unsignedということで、符号無し数すなわち負の数を表さない

という意味です。したがって、同じ８ビットの数”０１１０１１１１”の属性が<8,2,u>とすると、

0 1 1 0 1 1 1 1
整数部 小数部

ということになり、小数部は６ビットとなり、１０進表現では＋１．７３４３７５に対応します。

整数部のビット数が多いほど表現できる最大数すなわちレンジが大きくなり、小数部のビット数が多いほど表現できる最小数が小さくなり、解像度が向上します。

以下の表１に４ビットの数が<4,2,u>の属性を持つ場合と<4,1,t>の属性を持つ場合の１０進表現を示します。

表３　属性による値の違い

4ビットの数 属性<4,2,u>の場合の
１０進表現 属性<4,1,ｔ>の場合の
１０進表現
0000 +0.00 +0.00
0001 +0.25 +0.25
0010 +0.50 +0.50
0011 +0.75 +0.75
0100 +1.00 +1.00
0101 +1.25 +1.25
0110 +1.50 +1.50
0111 +1.75 +1.75
1000 +2.00 -2.00
1001 +2.25 -1.75
1010 +2.50 -1.50
1011 +2.75 -1.25
1100 +3.00 -1.00
1101 +3.25 -0.75
1110 +3.50 -0.50
1111 +3.75 -0.25

以下の表２に４ビット長の固定小数点の属性の幾つかの例と、対応する２進数、値のレンジ、解像度を示します。表２からもわかるように同じ４ビット長を用いて多様なレンジと解像度の数値を表現できます。当然のことですが、解像度を悪く大きな値にすると、より広いレンジを表すことができます。

表４　４ビット長の固定小数点の属性の幾つかの例と、対応する２進数、値のレンジ、解像度

属性 ２進数表現
Sは符号ビット
Xはデータビット レンジ 解像度
整数 <1,1,u> X. 0 to 1 1
<4,4,u> XXXX. 0 to 15 1
<4,3,t> SXXX. -8 to 7 1
小数 <4,0,u> .XXXX 0.0 to 0.9375 0.0625 (1/16)
<4,0,t> S.XXX -1.00 to +0.875 0.125 (1/8)
その他 <4,2,u> XX.XX 0.0 to 3.75 0.25 (1/4)
<4,2,t> SXX.X -4.0 to + 3.5 0.5 (1/2)
<4,5,u> XXXX0. 0 to 30 2
<4,5,t> SXXX00. -32 to 28 4
<4,-1,u> .0XXXX 0.0 to 0.46875 0.03125 (1/32)
<4,-1,t> S.SXXX -0.5 to +0.4375 0.0625 (1/16)

#### [６]　複素数の演算

#### （加算）

複素数は２つの実数をa, bとすると　a+jb
で複素数を示すことができます。

であり、虚数単位です。

したがって、２つの複素数 a+jb と c+jd
を加算するのは、実数成分と虚数成分のそれぞれの和になりますので、

となり、２つの実数加算器（通常の加算器）で実現することができます。

（乗算）

２つの複素数 a+jb と c+jd
の乗算は以下のようになります。

したがって、複素乗算は４つの実数乗算と１つの減算と１つの加算で実現できます。

以下に回路構成を図１２に示します。複素数a+jbと示しますが、回路の中では２つの信号a,
bが存在するだけで、複素加算器は２セットの２つの実数が入力され、それぞれが加算されて、２つの実数を出力する組み合わせ回路であり、複素乗算器も同様です。

図１２　複素演算回路

#### [７]　Twiddle Factor ROM

今回以下図１３に示されるW64の0乗から63乗までの値がTwiddle
Factorとして必要です。Real成分はcos関数で、虚数成分は（-sin)関数ですが、それそれ６４種類ですので、アドレスとして６ビットの入力をもつROM２個で実現することができます。

以下に64word X 8bitのROMのデータをリンクします。address=0
～ 63に対応して、一周期分のcosと-sin)の値すなわち、real =
cos (2*π*address/64), imag = -sin (2*π*address/64)
の１０ビットの値が属性<10,0,t>で格納されています。三角関数の値ですので、簡単に生成することもできますが、念のためにリンクしておきます。

- Real成分 (cos) ROM データ：cos.txt
- Imag成分(-sin) ROMデータ：msin.txt

#### 図１３　Twiddle Factor

#### [８]LEVEL1：基本課題

基本課題では図１４に示すように、シリアルにやってくるFFTINとHEAD信号をもとに、FFT出力FFTOUTとその先頭位置を示すOUTHEAD信号を出力します。図中の太い矢印はFFT計算のレイテンシー（遅延）を示していますが、レイテンシーは任意です。

図１４　入出力波形

図１４のように、６４ポイントの入力が休み無く入力され、その先頭位置はHEAD信号で示されます。

表５　基本課題用ピンリスト

FFT

信号名 入出力 ビット幅 説明
CLK IN １ クロック入力
HEAD IN １ ’１’で先頭を示す
FFTIN_I IN ８ 入力のREAL成分、<8,0,t>フォーマットとする
FFTIN_Q IN 8 入力のIMAGINARY成分、<8,0,t>フォーマットとする
OUTHEAD OUT 1 ’１’で先頭を示す
FFTOUT_I OUT 14 出力のREAL成分、<14,6,t>フォーマットとする
FFTOUT_Q OUT 14 出力のIMAGINARY成分、<14,6,t>フォーマットとする

以下に、５種類の入力波形とそのFFT結果を例として示します。

図１５　動作波形例（１）

#### １）　ALL　１　入力

図１５の上から１番目の波形は、入力として
１＋０ｊ を６４点入力した例です。そのFFT出力は２番目の波形であり、INDEX=0番におおよそ64.0の値が出力され、INDEX=2以降は０です。

#### ２）　１周期する複素回転信号　初期値＝１＋０ｊ

３番目の波形は、ちょうど１周期の複素回転波形を入力した場合です。FFT出力はINDEX=1に、おおよそ64.0の値が出力されています。回転の初期値が1+0jですので、FFT出力はこの64倍の値になっています。

#### ３）　１周期する複素回転信号　初期値＝０－１ｊ

５番目の波形も、ちょうど１周期の複素回転波形を入力した場合です。ただし、２）とは初期値が異なっています。FFT出力はINDEX=1に、おおよそ-64.0の値が出力されています。回転の初期値が0-1ｊですので、FFT出力はこの64倍の値になっています。

図１６　動作波形例（２）

#### ４）　１周期するCOS信号

図１６の上から１番目の波形は実数のCOS信号で、虚数成分は０です。

となりますので、１Hzのcos関数は１Hzと-1Hzの成分をもち、それぞれの大きさが0.5である２つの複素の回転の合成と考えることができます。したがって、FFT出力はINDEX=1番とINDEX=６３番にこれまでの半分の大きさの32.0の値が出力されています。

FFTでは周期（＝６４）性より、INDEX=63は-1Hzに対応すると考えることができます。

#### ５）　１５周期する複素回転信号

図１６の上から３番目の波形は、ちょうど１５周期の複素回転波形を入力した場合です。FFT出力はINDEX=１５に、おおよそ64.0の値が出力されています。回転の初期値が1+0jですので、FFT出力はこの64倍の値になっています。

以下に上記５つの入力波形のREAL成分とIMAGINARY成分の値を<8,0,t>フォーマットで以下にリンクします。テスト動作の時に用いてください。

- ALL　１　入力：　REAL成分　FFTIN0REAL.txt　　IMAGINARY成分　FFTIN0IMAG.txt
- １周期する複素回転信号　初期値＝１＋０ｊ
：REAL成分　FFTIN1REAL.txt　　IMAGINARY成分　FFTIN1IMAG.txt
- １周期する複素回転信号　初期値＝０－１ｊ
：REAL成分　FFTIN1JREAL.txt　　IMAGINARY成分　FFTIN1JIMAG.txt
- １周期するCOS信号：REAL成分　FFTIN1COSREAL.txt　　IMAGINARY成分　FFTIN1COSIMAG.txt
- １５周期する複素回転信号：REAL成分　FFTIN15REAL.txt　　IMAGINARY成分　FFTIN15IMAG.txt

#### [９]LEVEL2:自由課題

基本課題では、毎クロックごとに入力信号が与えられていますが、自由課題では、図１４の波形などを自由変更してください。

案としては、

- クロック周波数をあげて、数クロックごとに１データ入力を行い、クロック周波数の高さを利用して、回路削減をする。
- 上記例では、シフトレジスタを用いた設計例を示していますが、RAMを用いて設計する。

などです。要は６４点FFTを実行するユニークな回路を設計してください。

#### [１０]　スピードと面積の単位

琉球大学以外からの参加の場合、同一のシノプシスデザインコンパイラの論理合成用ライブラリを使用することが困難であるので、

２入力EXORゲイト１つの遅延時間を　1UNIT_DELAY
２入力EXORゲイト１つの面積を　１UNIT_AREA

とします。

具体的には、以下のような多段EXOR回路を例に従って合成し最適化し、その１段あたりの遅延時間を単位時間としてスピードの単位とします。

多段EXOR回路のVHDLソース例：５０入力のEXOR回路

合成語の回路図　PDF,　PS

この例では６段のEXOR段が合成され、クリティカルパス遅延はreport_timingコマンドにより７．１７であったので、７．１７/６＝１．１９５を単位（1UNIT_DELAY）とします。

- 例えば、ある遅延が２０ならば、２０/１．１９５＝１７．７４UNIT_DELAYとします。
- 琉大情報のライブラリ使用者は上記値で換算すればよいです。

また、面積はreport_areaコマンドのtotal
cell areaは147.0であり、EXORゲイト数は49個であるので、１４７．０/４９＝３．０を単位（1UNIT_AREA）とします。

たとえばある回路面積が２００ならば、２００/３．０＝６６．６７UNIT_AREAとします。
琉大情報のライブラリ使用者は上記値で換算すればよいです。

#### [１１]　RAM，　ROMを用いる場合の注意事項

FFTでは、やや多めのデータを取り扱いので、RAMを使用する場合が想定されます。RAMは合成可能なHDLで記述し、RAMもFFなどを用いて合成させ、上記面積レポートに含めてください。
FPGAをターゲットとして、RAMを１のように合成では性能が出ないなど、問題がある場合は、FPGA内蔵のRAMマクロを使用してよいですが、レポートにわかりやすく、明示してください。
三角関数出力などで、ROMを使用する場合も、マクロなどは使用せず、すべて合成し、組み合わせ回路で実現し、上記面積レポートに含めてください。

#### [１２]　レポート

レポートには以下の内容を含めるてください。また、ページ数を少なめにコンパクトにまとめてください。

表紙 １ 代表者の氏名、チーム名、大学院修士/大学学部生/高専生の区別
２ 共同設計者全員の名前（最高３名まで）、学籍番号、学年、学校名、住所、電話、email等連絡先
３ 全員のTシャツの希望サイズ（S,M,L,XLのいずれか）
４ 取り組んだ課題（LEVEL1／LEVEL2）
内容 １ 設計した回路ブロックの構成説明（ブロック図と説明）
２ 設計した回路ブロックの動作説明（動作波形図やパイプライン動作等の説明）
３ 工夫した点、オリジナリティを出した点（アピールが重要！）
４ クリティカルパスのスピード、論理合成後の回路規模
５ VHDLもしくはVerilogのコード
６ 正常動作しているVHDL/Verilogシミュレーション波形
７ その他自由意見など

レポートはPDFファイルにて下記にEMAILにて提出すること！

他の形式での提出希望あれば、相談してください。

wada@ie.u-ryukyu.ac.jp

締め切りは２００７年１月２６日（金）必着です。

#### [１３]　審査のポイント

速度、回路規模だけでなく、アーキテクチャのユニークさ、アイデア、面白さを十分考慮して審査します。
（ちゃんとアピールしてね！）
大学院修士、学部生、高専生のレベルに応じて審査をします。
仕様書に従ってまじめに作るのも良いが、オモロイアイデアを歓迎します。他人と違ったことをしよう！
仕様の部分変更など、柔軟に受け付けます。

本LSI設計コンテストの学生部門の企画・実行、および沖縄での発表会は

主催：LSIコンテスト実行委員会
共催：琉球大学工学部情報工学科、株式会社沖縄産業振興センター、九州半導体イノベーション協議会
協賛： ソニーLSIデザイン株式会社

です。

# ENJOY　HDL!　沖縄で会いましょう！