(57)【要約】  一態様では、ＦＦＴ回路（１）は、ＳＤＦアーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを含む。第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個のバタフライＰＥ（１０）の各々は、ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えるよう構成されている。ただし、ＮはＦＦＴポイント数であり、Ｓはステージ番号を表す整数であり、ｂＳ（ｉ）はＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する。
2014013726.tif 000002
【特許請求の範囲】
【請求項１】
ＦＦＴ（Fast Fourier Transform）回路であって、
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを備え、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えるよう構成されている、
ただし、ＮはＦＦＴポイント数であり、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数であり、ｂＳ（ｉ）は前記ＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する、
ＦＦＴ回路。
【請求項２】
前記ＬＨＦ個の第１のバタフライ演算要素は、各ステージでの中間結果シーケンスのデータ順序を逐次的に入れ替えることによって、第ＬＨＦステージの第１のバタフライ演算要素から出力される中間結果シーケンスのデータ順序を、ＤＦＧ（Data Flow Graph）インデックスのbit reversed orderに変換するよう動作する、
請求項１に記載のＦＦＴ回路
【請求項３】
前記ＬＨＳ個の第２のバタフライ演算要素は、第ＬＨＦステージの中間結果シーケンスのデータ順序を維持することによって、第Ｌステージの第２のバタフライ演算要素からnatural orderの周波数領域シーケンスを出力するよう構成されている、
請求項１又は２に記載のＦＦＴ回路。
【請求項４】
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、データパス及びフィードバックパスにデータを出力する第１のバタフライプロセッサ、前記フィードバックパスに配置された第１の遅延回路、及びシーケンス変換回路を含み、
前記シーケンス変換回路は、前記第１のバタフライプロセッサの出力及び前記第１の遅延回路の入力の間の前記フィードバックパス上に配置された第２の遅延回路、及び前記第２の遅延回路の出力及び前記１の遅延回路の入力の間の前記フィードバックパスと前記データパスの間で信号経路を切替えるセレクタを含む、
請求項１〜３のいずれか１項に記載のＦＦＴ回路。
【請求項５】
前記第１の遅延回路は遅延量（２Ｌ−Ｓ−２Ｓ−１）を有し、
前記第２の遅延回路は遅延量２Ｓ−１を有する、
請求項４に記載のＦＦＴ回路。
【請求項６】
前記ＬＨＳ個の第２のバタフライ演算要素の各々は、第２のバタフライプロセッサ、及び前記第２のバタフライプロセッサのフィードバックパスに配置された遅延量２Ｓ−１を有する第３の遅延回路を含む、
請求項４又は５に記載のＦＦＴ回路。
【請求項７】
前記パイプラインは、Ｒａｄｉｘ−２パイプライン又はＲａｄｉｘ−２ｎパイプラインである、
請求項１〜６のいずれか１項に記載のＦＦＴ回路。
【請求項８】
ＦＦＴ（Fast Fourier Transform）回路であって、
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを備え、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記ＬＨＦ個の第１のバタフライ演算要素は、各ステージでの中間結果シーケンスのデータ順序を逐次的に入れ替えることによって、第ＬＨＦステージの第１のバタフライ演算要素から出力される中間結果シーケンスのデータ順序を、ＤＦＧ（Data Flow Graph）インデックスのbit reversed orderに変換するよう構成され、
前記ＬＨＳ個の第２のバタフライ演算要素は、第ＬＨＦステージの中間結果シーケンスのデータ順序を維持することによって、第Ｌステージの第２のバタフライ演算要素からnatural orderの周波数領域シーケンスを出力するよう構成されている、
ＦＦＴ回路。
【請求項９】
ＦＦＴ（Fast Fourier Transform）回路であって、
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを備え、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、データパス及びフィードバックパスにデータを出力する第１のバタフライプロセッサ、前記フィードバックパスに配置された第１の遅延回路、及びシーケンス変換回路を含み、
前記シーケンス変換回路は、前記第１のバタフライプロセッサの出力及び前記第１の遅延回路の入力の間の前記フィードバックパス上に配置された第２の遅延回路、及び前記第２の遅延回路の出力及び前記１の遅延回路の入力の間の前記フィードバックパスと前記データパスの間で信号経路を切替えるセレクタを含む、
ただし、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数である、
ＦＦＴ回路。
【請求項１０】
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを用いてＦＦＴ（Fast Fourier Transform）を行う方法であって、
第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個のバタフライ演算要素によって、ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えることを備える、
ただし、ＮはＦＦＴポイント数であり、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数であり、ｂＳ（ｉ）は前記ＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する、
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、FFT (Fast Fourier Transform) 処理を行うパイプライン処理回路に関する。
【背景技術】
【０００２】
FFTは、信号処理分野で広範囲に使用されているアルゴリズムである。FFTは、例えば、OFDM (Orthogonal Frequency Division Multiplexing) 受信機（e.g. LTE（Long Term Evolution）方式の通信端末、無線LAN（Local Area Network）機器、及びデジタルテレビ放送受信機）において受信OFDM信号から複素シンボル列を抽出するために使用される。以下の式(1) 及び式(2) は、NポイントのDFT（Discrete Fourier Transform）を表している。ここでX(n)は時間領域(time domain)シーケンス、Y(k)は周波数領域(frequency domain）シーケンス、Ｗnkは回転子（twiddle factor）と呼ばれる。
【数１】
2014013726.tif 000003
【数２】
2014013726.tif 000004
【０００３】
FFTアルゴリズムは、回転子Ｗnkの周期性を利用しながらNポイントのDFTを基数(radix)ポイントの複数のFFTに分解することを特徴とする。これにより、FFTアルゴリズムは、式(1) 及び式(2)のDFTを直接計算する場合に比べて大幅に演算量を削減できる。FFTアルゴリズムは、広く知られたアルゴリズムであり、例えば" Digital Signal Processing: Principles, Algorithms and Applications"、John G. Proakis, Dimitris K Manolakis, Prentice-Hall(1996)に詳述されている。したがって、ここではFFTアルゴリズムの詳細説明を割愛する。【０００４】
FFTアルゴリズムは、(a)基数 (例えば、Radix-2、Radix4)、(b) 周波数間引き（DIF: Decimation In Frequency）か時間間引き（DIT: Decimation In Time）か、及び(c) データフローグラフ (DFG: Data Flow Graph)の形によって様々バリエーションがある。ここでは、Radix-2 DIF FFTを例にとって説明する。図9は、Radix-2 DIF FFTのバタフライ演算の基本フローグラフを示している。図10は、16ポイント（N = 24 = 16） Radix-2 DIF FFTのデータフローグラフを示している。FFTは、図9に示したようなバタフライ演算の組み合わせで実現され、各ステージでN/2回のバタフライ演算をLステージ行なう。ここでL = log2Nである。図10に示されているように、Radix-2 DIF FFTでは、入力データシーケンス（すなわち時間領域シーケンス）が自然順(natural order)に並んでいるとき、出力データシーケンス（すなわち周波数領域シーケンス）はビット逆順(bit-reversed order)となる。つまり、DFGインデックスiに出力される周波数領域データはY(brL(i))である。DFGインデックスは、データフローグラフにおけるデータ出力の順番を示す。ここで、brL(i)は、自然数iのLビット長の2進表記をMSB（Most significant bit）とLSB(Least Significant Bit)を入れ替えるようにビット反転して表現される自然数である。例えばi=13（10進表記）であるとき、13の4ビット長の2進表記は"1101"であるから、br4(13)の2進表記は"1011"であり、br4(13)の10進表記は"11"となる。また、br5(13) の2進表記は"10110"であり、br5(13)の10進表記は"22"となる。【０００５】
また、FFTアルゴリズムをパイプライン処理するための一実装手法として、SDF (Single-path Delay Feedback) アーキテクチャが知られている。SDFアーキテクチャの詳細は、例えば、非特許文献1に開示されている。図11は、非特許文献１に開示されているRadix-2 DIF SDFアーキテクチャのFFT回路の構成を示している。図11に示されたFFT回路8は、L個のバタフライProcessing Element（以降、バタフライPE）80_1〜80_Lが連結されたパイプライン、及びシーケンス変換部90を含む。なお、Lは、FFTポイント数をNとした場合、log2Nである。【０００６】
バタフライPE 80_1は、natural orderの時間領域シーケンスX(n)を受信し、図10の第1ステージに対応するN/2回のバタフライ演算を行ない、バタフライ演算結果を次ステージのバタフライPE 80_2に出力する。バタフライPE 80_2〜80_Lは、第2ステージから第Lステージのバタフライ演算を行う。これにより、第LステージのバタフライPE 80_Lは、周波数領域シーケンスY(k)をbit reversed orderで出力する。そして、シーケンス変換部90は、bit reversed orderの周波数領域シーケンスY(k)をnatural orderに変換して出力する。説明のために、第SステージのバタフライPE 80_Sによる出力データ（すなわち、中間結果データ又は周波数領域データ）をGS(i)と表現する。整数iは、DFGインデックスを表し、0以上N以下の整数である。整数Sは、ステージ数を表し、1以上L以下の整数である。【０００７】
図12は、第SステージのバタフライPE 80_Sの構成を示すブロック図である。バタフライPE 80_Sは、バタフライプロセッサ810、遅延回路820、及びカウンタ830を含む。バタフライプロセッサ810は、2つの入力ポートIN1及びIN2、並びに2つの出力ポートOUT1及びOUT2を有する。第1の入力ポートIN1は、遅延回路820の出力データを受信する。第2の入力ポートIN2は、前ステージのバタフライPE 80_S-1の出力データシーケンスGS-1(i) を受信する。第1の出力ポートOUT1は、遅延回路820の入力ポートに接続され、遅延回路820にデータを供給する。第2の出力ポートOUT2は、次ステージのバタフライPE 80_S+1又はシーケンス変換部90に出力データシーケンスGS(i)を供給する。【０００８】
遅延回路820は、バタフライプロセッサ810の出力を入力に帰還するためのフィードバックパス（フィードバック経路）に配置されている。遅延回路820は、2L-Sワード分のデータを格納可能なメモリであり、格納したデータをFIFO（First In First Out）順序で出力する。遅延回路820は、例えば、FIFOバッファ、又はシフトレジスタである。カウンタ830は、Lビット・カウンタであり、前ステージのバタフライPE 80_S-1からDFGインデックス"0"の出力データGS-1(0)が入力されるタイミングで0にリセットされる。カウンタ830は、カウンタ値Cをバタフライプロセッサ110に供給する。【０００９】
図13A及び図13Bは、図12に示されたバタフライプロセッサ810の構成を示すブロック図である。図13A及び図13Bのバタフライプロセッサ810は、加算器811、減算器812、乗算器813、回転子選択部814、及びセレクタ（マルチプレクサ）815を含む。上述したように、第1の入力ポートIN1には遅延回路820の出力データが供給され、第2の入力ポートIN2には前ステージのバタフライPE 80_S-1の出力データシーケンスGS-1(i)が供給される。加算器811、減算器812、及び乗算器813は、これらの2つの入力データに対して、図9に示したバタフライ演算を行う。【００１０】
回転子選択部814は、カウンタ830のカウンタ値Cに基づいて選択した回転子WNKを乗算器813に供給する。セレクタ815は、2つのセレクタ素子816及び817を含む。セレクタ素子816は、遅延回路820から供給されるデータ及び加算器811の出力データのいずれか一方をカウンタ値Cに応じて選択し、これを第2の出力ポートOUT2に出力する。また、セレクタ素子817は、前ステージのバタフライPE 80_S-1から供給されるデータGS-1(i)及び乗算器813の出力データのいずれか一方をカウンタ値Cに応じて選択し、これを第1の出力ポートOUT1に出力する。【００１１】
次に、第Sステージ目のバタフライPE 80_Sに着目してその動作を説明する。なお、以下の説明において、自然数qを2進表記したときの最下位（LSB）からP番目のビットをbP(q)と表現する。バタフライPE 80_Sは、1ステージ分のバタフライ演算（すなわちN/2回のバタフライ演算）をデータフローグラフ（例えば図10）の上から順に行う。具体的には、カウンタ値Cを2進表記したときの最下位（LSB）から（L-S+1）番目のビットが0であるとき（すなわち、bL-S+1(C)=0のとき）、セレクタ815のセレクタ素子816及び817は、図13Aに示されているようにポート#0側を選択する。これにより、前ステージのバタフライPE 80_S-1の出力データGS-1(C) は、バタフライ演算を行われること無く遅延回路820へ送られる。【００１２】
一方、bL-S+1(C)=1であるとき、セレクタ815のセレクタ素子816及び817は、図13Bに示されているようにポート#1側を選択する。バタフライプロセッサ810は、前ステージのバタフライPE 80S-1の出力データGS-1(C)と遅延回路820によって2L-Sサイクル遅延されたデータGS-1(C-2L-S)を用いたバタフライ演算を行い、バタフライ演算後のデータGS(C-2L-S)及びGS(C)を生成する。そして、一方のバタフライ演算結果GS(C-2L-S)は、セレクタ素子816を介して次ステージのバタフライPE 80_S+1へ送られる。また、他方のバタフライ演算結果GS(C)は、セレクタ素子817を介して遅延回路820へ送られる。遅延回路820に入力されたバタフライ演算結果GS(C)は、2L-Sサイクル遅延されるとともに、bL-S+1(C)=0であるときに次ステージのバタフライPE 80_S+1へ送られる。【００１３】
図14は、N=16（すなわちL=4）の例において、第2ステージのバタフライPE 80_2に設けられたバタフライプロセッサ810の入出力データを示すテーブルである。参考のために、図14は、カウンタ値Cの10進表記（DEC.）及び2進表記（BIN.）と、セレクタ815の選択ポート（#0又は#1）も示している。図14の例では、b3(C)=1であるとき、すなわちカウンタ値Cの10進表記が4〜6及び12〜15のとき、第2ステージのバタフライ演算の結果G2(C-4)が第3ステージのバタフライPE 80_3へ送られ、G2(C)が遅延回路820へ送られる。また、b3(C)=0であるとき、すなわちカウンタ値Cの10進表記が0〜3及び8〜11のとき、第1ステージのバタフライPE 80_1の出力データG1（C）が遅延回路820に送られるともに、遅延回路820によって4サイクル遅延されたG2（C-4）が第3ステージのバタフライPE 80_3へ送られる。【００１４】
上述したRadix-2 DIF SDFアーキテクチャのパイプラインFFT回路8におけるLステージのバタフライPE 80-1〜80_Lによる遅延量は、以下の式(3）で表される。
【数３】
2014013726.tif 000005
【００１５】
次に、図11に示されたシーケンス変換部90について説明する。既に述べたように、シーケンス変換部90は、第LステージのバタフライPE 80_Lから出力されるbit reversed orderの周波数領域シーケンスY(k)をnatural orderに変換して出力する。図15は、シーケンス変換部90の構成例を示すブロック図である。図15に示されたシーケンス変換部90は、メモリ910、アドレス生成部920、及びカウンタ930を含む。【００１６】
カウンタ930は、Lビット・カウンタであり、Y(0)入力時にカウンタ値が0にリセットされる。カウンタ930は、そのカウンタ値をアドレス生成部920に供給する。また、カウンタ930は、処理FFT回数に従って、モード信号をアドレス生成部920に出力する。具体的には、カウンタ930は、処理FFT回数が奇数の場合にモード信号の値を"0"とし、偶数の場合にモード信号の値を"1"とする。【００１７】
アドレス生成部920は、メモリ910にWrite及びReadアドレスを出力する。具体的に述べると、アドレス生成部920は、モード0のとき、Lビット・カウンタ930のカウンタ値(10進表記で0,……,N-1) をビットリバースした値、すなわち brL(0), …, brL(N-1)、 をWrite及びReadアドレスとして出力する。一方、モード1であるとき、アドレス生成部920は、Lビット・カウンタ930のカウンタ値(10進表記で0,…,N-1)をそのままWrite及びReadアドレスとして出力する。【００１８】
メモリ910は、Nワードのメモリである。メモリ910は、アドレス生成部920で生成されたWrite及びReadアドレスに従って、周波数域シーケンスY(k) を読み書きすることにより、周波数域シーケンスY(k)をbit reversed orderからnatural orderに変換して出力する。【００１９】
図15のシーケンス変換部90の動作は以下の通りである。まず、第1回目の周波数域シーケンスY(k)が入力される時はモード0となる。したがって、bit reversed orderの入力シーケンスY(brL(0)), …, Y(brL(N-1))は、カウンタ930のカウンタ値をビットリバースしたWriteアドレス(brL(0),…, brL(N-1))に従ってメモリ910に書き込まれる。これにより、モード0においてNワードの周波数領域シーケンスY(k)がメモリ910に書き込まれたとき、これらのデータはメモリ910の中にnatural orderで格納された状態となる。モード０においてメモリ910に格納されたNワードの周波数領域シーケンスY(k)は、モード1のときに読み出される。モード1のときのReadアドレスはカウンタ930のカウンタ値そのものであるため、メモリ910は、周波数領域シーケンスY(k)をnatural orderで出力する。なお、モード1において周波数領域シーケンスY(k)が読み出されたアドレスには、すぐに次のFFTで得られる周波数域シーケンスY(k)が書き込まれる。これにより、まだ読み出されていない周波数領域データが上書きされることが回避される。【００２０】
モード1においてNワードの周波数領域シーケンスY(k)がメモリ910に書き込まれたとき、これらのデータはメモリ910の中にbit reversed orderで格納された状態となる。モード1においてメモリ910に格納されたNワードの周波数領域シーケンスY(k)は、モード0のときに読み出される。モード0のときのReadアドレスはカウンタ930のカウンタ値wo
ビットリバースしたものであるため、メモリ910は、周波数領域シーケンスY(k)をnatural orderで出力する。【００２１】
メモリ910はNワードのデータをいったん蓄積するため、シーケンス変換部90による遅延量は、Nサイクルである。したがって、(3)式に示したバタフライPE 80-1〜80_Lによる遅延量と併せて、パイプラインFFT回路8による総遅延量は、以下の(4)式に示すように、2N-1サイクルである。
【数４】
2014013726.tif 000006
【先行技術文献】
【非特許文献】
【００２２】
【非特許文献１】Y.-N. Chang, "An efficient VLSI architecture for normal I/O order pipeline FFT design," IEEE Transactions on Circuits and Systems II, Express Briefs, vol. 55, no. 12, pp. 1234-1238, Dec. 2008.
【発明の概要】
【発明が解決しようとする課題】
【００２３】
上述したパイプラインFFT回路8は、最終段のバタフライPE 80_Lから出力される周波数領域シーケンスがbit reversed orderであるために、これをnatural orderに変換するためのシーケンス変換部90が必要である。このため、総遅延量が2N-1と大きくなる。また、遅延を実現するメモリ又はレジスタ（すなわち、遅延回路820及びメモリ910）のWord数（レジスタサイズ又はメモリサイズ）の増加は、パイプラインFFT回路8の回路規模の増大を招く。【００２４】
本発明は、上述の課題に鑑みて発明されたものであって、その目的は、natural orderの入力シーケンスに基づいてnatural orderの出力シーケンスを出力することができ、かつ総遅延量が小さいFFT回路及びFFTを行う方法を提供することである。
【課題を解決するための手段】
【００２５】
第1の態様では、ＦＦＴ（Fast Fourier Transform）回路は、ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを含む。前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含む。前記ＬＨＦ個の第１のバタフライ演算要素の各々は、ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えるよう構成されている。ただし、ＮはＦＦＴポイント数であり、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数であり、ｂＳ（ｉ）は前記ＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する。【００２６】
第2の態様では、ＦＦＴ（Fast Fourier Transform）回路は、ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを含む。前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含む。前記ＬＨＦ個の第１のバタフライ演算要素は、各ステージでの中間結果シーケンスのデータ順序を逐次的に入れ替えることによって、第ＬＨＦステージの第１のバタフライ演算要素から出力される中間結果シーケンスのデータ順序を、ＤＦＧ（Data Flow Graph）インデックスのbit reversed orderに変換するよう構成されている。さらに、前記ＬＨＳ個の第２のバタフライ演算要素は、第ＬＨＦステージの中間結果シーケンスのデータ順序を維持することによって、第Ｌステージの第２のバタフライ演算要素からnatural orderの周波数領域シーケンスを出力するよう構成されている。【００２７】
第3の態様では、ＦＦＴ（Fast Fourier Transform）回路は、ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを含む。前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含む。前記ＬＨＦ個の第１のバタフライ演算要素の各々は、データパス及びフィードバックパスにデータを出力する第１のバタフライプロセッサ、前記フィードバックパスに配置された第１の遅延回路、及びシーケンス変換回路を含む。さらに、前記シーケンス変換回路は、前記第１のバタフライプロセッサの出力及び前記第１の遅延回路の入力の間の前記フィードバックパス上に配置された第２の遅延回路、及び前記第２の遅延回路の出力及び前記１の遅延回路の入力の間の前記フィードバックパスと前記データパスの間で信号経路を切替えるセレクタを含む。ただし、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数である。【００２８】
第4の態様では、ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを用いてＦＦＴ（Fast Fourier Transform）を行う方法が提供される。前記方法は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個のバタフライ演算要素によって、ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えることを含む。ただし、ＮはＦＦＴポイント数であり、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数であり、ｂＳ（ｉ）は前記ＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する。【００２９】
第5の態様では、ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを用いてＦＦＴ（Fast Fourier Transform）を行う方法が提供される。なお、前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含む。当該第5の態様に係る方法は、
（ａ）前記ＬＨＦ個の第１のバタフライ演算要素によって、各ステージでの中間結果シーケンスのデータ順序を逐次的に入れ替えることによって、第ＬＨＦステージの第１のバタフライ演算要素から出力される中間結果シーケンスのデータ順序を、ＤＦＧ（Data Flow Graph）インデックスのbit reversed orderに変換すること、及び
（ｂ）前記ＬＨＳ個の第２のバタフライ演算要素によって、第ＬＨＦステージの中間結果シーケンスのデータ順序を維持することによって、第Ｌステージの第２のバタフライ演算要素からnatural orderの周波数領域シーケンスを出力すること、
を含む。
【発明の効果】
【００３０】
上述した第1〜第5の態様によれば、natural orderの入力シーケンスに基づいてnatural orderの出力シーケンスを出力することができ、かつ総遅延量が小さいFFT回路及びFFTを行う方法を提供することができる。
【図面の簡単な説明】
【００３１】
【図１】一実施形態に係るFFT回路の構成例を示すブロック図である。
【図２】一実施形態に係るFFT回路に含まれる第1タイプのバタフライPEの構成例を示すブロック図である。
【図３】図２に示された第1タイプのバタフライPEに含まれるバタフライプロセッサ及びシーケンス変換部の構成例を示すブロック図である。
【図４Ａ】N=16（すなわちL=4）の例において、第1ステージのバタフライPE（第1タイプのバタフライPE）に設けられたバタフライプロセッサ及びシーケンス変換部の入出力データを示すテーブルである（一実施形態）。
【図４Ｂ】N=16（すなわちL=4）の例において、第1ステージのバタフライPE（第1タイプのバタフライPE）に設けられたバタフライプロセッサ及びシーケンス変換部の入出力データを示すテーブルである（一実施形態）。
【図５】N=16（すなわちL=4）の例において、第2ステージのバタフライPE（第1タイプのバタフライPE）に設けられたバタフライプロセッサ及びシーケンス変換部の入出力データを示すテーブルである（一実施形態）。
【図６】一実施形態に係るFFT回路に含まれる第2タイプのバタフライPEの構成例を示すブロック図である。
【図７】図５に示された第2タイプのバタフライPEに含まれるバタフライプロセッサの構成例を示すブロック図である。
【図８】N=16（すなわちL=4）の例において、第3ステージのバタフライPE（第2タイプのバタフライPE）に設けられたバタフライプロセッサの入出力データを示すテーブルである（一実施形態）。
【図９】Radix-2 DIF FFTのバタフライ演算の基本フローグラフである（背景技術）。
【図１０】16ポイント（N = 24 = 16） Radix-2 DIF FFTを示すデータフローグラフである（背景技術）。
【図１１】背景技術に係るFFT回路の構成例を示すブロック図である。
【図１２】背景技術に係るFFT回路に含まれるバタフライPEの構成例を示すブロック図である。
【図１３Ａ】背景技術に係るFFT回路に含まれるバタフライPEの構成例を示すブロック図である。
【図１３Ｂ】背景技術に係るFFT回路に含まれるバタフライPEの構成例を示すブロック図である。
【図１４】N=16（すなわちL=4）の例において、第2ステージのバタフライPEに設けられたバタフライプロセッサの入出力データを示すテーブルである（背景技術）。
【図１５】背景技術に係るFFT回路に含まれるシーケンス変換部の構成例を示すブロック図である。
【発明を実施するための形態】
【００３２】
以下では、具体的な実施形態について、図面を参照しながら詳細に説明する。各図面において、同一又は対応する要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略される。
【００３３】
＜第１の実施形態＞
図1は、本実施形態に係るパイプラインFFT回路1の構成例を示すブロック図である。図1に示されたFFT回路1は、Radix-2 DIF SDFアーキテクチャの変形であり、natural orderの入力シーケンス（時間領域シーケンス）に基づいてnatural orderの出力シーケンス（周波数領域シーケンス）を出力する。ここで、説明のために、1以上の整数LHFおよび０以上の整数LHSを以下の(5)式および(6)式により定義する。ここで、NはFFTポイント数であり、Lはlog2Nである。また、(5)式の右辺は天井関数（ceiling function）を示し、(6)式の右辺は床関数（floor function）を示している。
【数５】
2014013726.tif 000007
【数６】
2014013726.tif 000008
【００３４】
FFT回路1は、L個のバタフライPEが連結されたパイプラインを有する。具体的には、図１に示されるように、当該パイプラインは、LHF個の第1タイプのバタフライPE 10_1〜10_LHF、及びLHS個の第2タイプのバタフライPE 11_LHF+1〜11_Lによって構成される。LHF個の第1タイプのバタフライPE 10は、前半の第1ステージから第LHFステージまでに配置されている。一方、LHS個の第2タイプのバタフライPE 11は、後半の第(LHF+1)ステージから第Lステージまでに配置されている。第1ステージに配置された第1タイプのバタフライPE10_1は、natural orderの時間領域シーケンスX(n)を受信し、図10の第1ステージに対応するN/2回のバタフライ演算を行ない、バタフライ演算結果を次ステージのバタフライPE 10_2に出力する。残りの第1タイプのバタフライPE 10_2〜10_LHF、及び第2タイプのバタフライPE 11_LHF+1〜11_Lは、第2ステージから第Lステージのバタフライ演算を行う。
【００３５】
本実施形態のFFT回路1が背景技術に係るFFT回路8と異なる点の１つは、最終の第Lステージに配置された第2タイプのバタフライPE 11_Lが周波数領域シーケンスをbit reversed order ではなくnatural orderで出力する点である。そのために、本実施形態では、第1タイプのバタフライPE 10_1〜10_LHFの各々は、小規模なハードウェアによるシーケンス変換機構を有している。これにより、第1タイプのバタフライPE 10_1〜10_LHFは、中間結果シーケンスGS（k）のデータ順序を逐次的に入れ替えるよう構成されている。具体的には、バタフライPE 10_1〜10_LHFは、第LHFステージのバタフライPE 10_LHFから出力される中間結果シーケンスGLHF（k）のデータ順序が、DFGインデックスのbit reversed orderになるようにデータ順序を変更する。一方、後半の第(LHF+1)ステージから第Lステージまでに配置された第2タイプのバタフライPE 11_LHF+1〜11_Lの各々は、入力データのDFGインデックス順序を保ったまま、すなわちDFGインデックスのbit reversed orderで出力シーケンスGS（k）を出力するよう構成されている。
【００３６】
本実施形態に係るFFT回路1は、FFTの第1〜第LHFステージにて逐次的な出力データ順序（DFGインデックスの出力順序）の変更を行うことによって、natural orderの時間領域シーケンスX(n)に基づいてnatural orderの周波数領域シーケンスY(k)を出力する。これにより、FFT回路1の総遅延量は、背景技術に係るFFT回路8の総遅延量2N-1に比べて小さくできる。以下では、第1及び第2タイプのバタフライPE10及び11の構成及び動作の具体例について説明する。
【００３７】
図2は、第Sステージの第1タイプのバタフライPE 10_Sの構成例を示すブロック図である。ここでは、Sは1以上LHF以下の整数（S=1, …, LHF）である。図2のバタフライPE 10_Sは、バタフライプロセッサ110、遅延回路120、カウンタ130、及びシーケンス変換部140を含む。シーケンス変換部140は、バタフライプロセッサ110と遅延回路120の間に配置されている。
【００３８】
バタフライプロセッサ110の基本構成は、図12に示したバタフライプロセッサ810の構成と同様である。ただし、シーケンス変換部140が追加されたことに伴い、バタフライプロセッサ110の出力データはシーケンス変換部140に送られる。また、バタフライ演算の処理順が変更されるため、バタフライプロセッサ110における回転子の選択順序は、バタフライプロセッサ810における回転子の選択順序と異なる。バタフライプロセッサ110は、2つの入力ポートBIN1及びBIN2、並びに2つの出力ポートBOUT1及びBOUT２を有する。第1の入力ポートBIN1は、遅延回路120の出力データを受信する。第2の入力ポートBIN2は、前ステージのバタフライPE 10_S-1の出力データシーケンスGS-1(k) を受信する。第1の出力ポートSOUT1は、シーケンス変換部140の第1の入力ポートSIN1に接続される。第2の出力ポートSOUT2は、シーケンス変換部140の第2の入力ポートSIN2に接続される。
【００３９】
遅延回路120は、バタフライプロセッサ110の出力を入力に帰還するためのフィードバックパス（フィードバック経路）に配置されている。遅延回路120の遅延量は、図12に示した遅延回路820の遅延量とは異なる。具体的には、遅延回路820の遅延量が2L-Sであるのに対し、本実施形態の遅延回路120の遅延量は、2L-S-2S-1である。これは、後述するシーケンス変換部140に配置された遅延回路141による遅延量2S-1と整合をとるためである。なお、遅延回路120は、例えば、FIFOバッファ、又はシフトレジスタとすればよい。
【００４０】
カウンタ130の構成及び動作は図12に示されたカウンタ830と同様とすればよい。すなわち、カウンタ130は、Lビット・カウンタであり、前ステージのバタフライPEからDFGインデックス"0"の出力データGS-1(0)が入力されるタイミングで0にリセットされる。カウンタ130は、カウンタ値Cをバタフライプロセッサ110に供給する。
【００４１】
図3は、図2に示したバタフライプロセッサ110及びシーケンス変換部140の構成例を示すブロック図である。バタフライプロセッサ110は、加算器111、減算器112、乗算器113、回転子選択部114、及びセレクタ（マルチプレクサ）115を含む。回転子選択部114の動作は、回転子WNKの選択順序が異なる点を除いて、図13A及び図13Bに示された回転子選択部814と同様である。回転子選択部114は、例えば、カウンタ値Cに応じてアドレスを生成するアドレス生成器と、アドレスに応じた回転子を出力する回転子メモリ（LUT（Look Up Table））によって構成することができる。
【００４２】
セレクタ115の構成及び動作は、図13 A及び図13Bに示されたセレクタ815と同様である。すなわち、セレクタ115は、2つのセレクタ素子116及び117を含む。セレクタ素子116は、遅延回路120から供給されるデータ及び加算器111の出力データのいずれか一方をカウンタ値Cに応じて選択し、これを第2の出力ポートBOUT2に出力する。また、セレクタ素子117は、前ステージのバタフライPE 10_S-1から供給されるデータGS-1(i)及び乗算器113の出力データのいずれか一方をカウンタ値Cに応じて選択し、これを第1の出力ポートBOUT1に出力する。
【００４３】
シーケンス変換部140は、遅延回路141及びセレクタ（マルチプレクサ）142を含む。遅延回路141は、第1の入力ポートSIN1に供給されるデータ、すなわちバタフライプロセッサ110の第1の出力データを2s-1サイクル遅延して出力する。遅延回路141は、例えば、FIFOバッファ、又はシフトレジスタとすればよい。セレクタ142は、カウンタ130のカウンタ値Cに応じて動作する2入力2出力のスイッチである。セレクタ142は、遅延回路141の出力データと第2の入力ポートSIN2のデータのうちいずれか一方を遅延回路120に送るために第1の出力ポートSOUT1に出力し、他方を次ステージのバタフライPE 10又は11へ送るために第2の出力ポートSOUT2に出力する。セレクタ142は、2つの入力データをストレートに出力するか、又はクロスして出力する。例えば、セレクタ142は、図3に示されているように、互いに相補的に動作するセレクタ素子143及び144を含む。すなわち、セレクタ素子143は、第1の出力ポートOUT1（すなわち遅延回路120）に送られる一方のデータを選択する。セレクタ素子144は、第2の出力ポートOUT2（すなわち次ステージのバタフライPE）に送られる他方のデータを選択する。
【００４４】
図2及び図3の構成例から理解されるように、本実施形態では、2L-Sサイクル分の総遅延量が、2S-1サイクル分の第1の遅延要素（すなわち遅延回路141）と、2L-S-2S-1サイクル分の第2の遅延要素（すなわち遅延回路120）とに分割して配置されていると言うこともできる。さらに、これら2つの遅延要素の間には、セレクタ142が配置されている。したがって、本実施形態は、SDFアーキテクチャで用いられる遅延フィードバックによる遅延量を2L-S 又は2s-1 に切り替えることができる。また、本実施形態は、バタフライプロセッサ110の第2の出力ポート（BOUT2）に現れる第Sステージでのバタフライ演算結果（中間結果データ）をバタフライプロセッサ110の第1入力ポートSIN1に遅延フィードバック（遅延量2L-S-2S-1）することができる。さらに、本実施形態は、バタフライプロセッサ110の第1の出力ポート（BOUT1）に現れる第Sステージでのバタフライ演算結果データ（中間結果データ）を2s-1サイクル遅延させて次ステージのバタフライプロセッサPE 10又は11に送ることができる。
【００４５】
従って、図2及び図3に示した第1タイプのバタフライPE 10_Sは、簡易な構成であり且つ遅延量の小さいシーケンス変換部140を用いて、第Sステージの中間結果シーケンスGS（k）のデータ順序（DFGインデックスの出力順序）を変更できる。具体的には、第Sステージ（S=1, …, LHF）のバタフライPE 10_Sは、DFG インデックスiを2進表記したときの最下位（LSB）からSビット目が"1"である中間結果データGS(i)が、最下位（LSB）からSビット目が"0"である中間結果データGS(i)よりも後に出力されるように出力データ順序を並び替えればよい。なお、このデータ並び替えは、DFGインデックスが0"である先頭の出力データから順にN/(2S-1)個ずつの出力データを単位として行えばよい。なぜなら、2進表記されたDFG インデックスにおける最下位（LSB）からS-1ビット目までの並び替えは第S-1ステージまでのバタフライPE 10によって完了しているためである。
【００４６】
言い換えると、第Sステージ（S=1, …, LHF）のバタフライPE 10_Sは、DFGインデックスiが"0"である先頭の出力データから順にN/(2S-1)個ずつの出力データを単位として、このN/(2S-1)個の出力データ内においてbS(i)＝1である中間結果データGS(i)は、bS(i)＝0である中間結果データGS(i)より後に出力されるように出力データ順序を並び替えればよい。なお、bS(i)は、DFGインデックスiを2進表記したときの最下位からS番目のビットを示す。これにより、LHF個のバタフライPE 10_1〜10_LHFは、第LHFステージのバタフライPE 10_LHFから出力される中間結果シーケンスGLHF（k）のデータ順序（DFGインデックスの出力順序）を、DFGインデックスのbit reversed orderになるように変換することができる。
【００４７】
次に、第Sステージ（S=1, …, LHF）の第1タイプのバタフライPE 10_Sの動作について説明する。バタフライPE 10_Sは、1ステージ分のバタフライ演算（すなわちN/2回のバタフライ演算）を行う。ただし、特に第2ステージ以降では、前ステージのバタフライPE 10_S-1の出力データ順序の並び替えに従って、ステージ内でのN/2回のバタフライ演算の順序も並び替えられる。具体的には、カウンタ値Cを2進表記したときの最下位（LSB）から（L-S+1）番目のビットが0であるとき（すなわち、bL-S+1(C)=0のとき）、セレクタ115のセレクタ素子116及び117は、図3に示されたポート#0側を選択する。さらに、シーケンス変換部140に配置されたセレクタ142のセレクタ素子143及び144は、bL-S+1(C)=0のとき、図3に示されたポート#A側を選択し、入力データをストレートに出力する。すなわち、セレクタ142は、遅延回路141の出力データを遅延回路120に送り、ポートSIN2に入力されたデータを次ステージのバタフライPE 10_S+1に送る。これにより、前ステージのバタフライPE 10_S-1からCサイクル目に受信された中間結果データGS-1(k) は、バタフライ演算を行われること無くシーケンス変換部140へ送られる。なお、前ステージのバタフライPE 10_S-1による出力データ順序（DFGインデックスの出力順序）の並び替えのために、Cサイクル目に受信された中間結果データGS-1(k) は GS-1(C)であるとは限らない。そして、シーケンス変換部140は、Cサイクル目に受信された中間結果データGS-1(k)を遅延回路141で2S-1サイクルだけ遅延した後に、セレクタ142を介して遅延回路120に出力する。
【００４８】
一方、bL-S+1(C)=1であるとき、セレクタ115のセレクタ素子116及び117は、図3に示されたポート#1側を選択する。バタフライプロセッサ110は、前ステージのバタフライPE 10S-1からCサイクル目に受信された中間結果データGS-1(k)と遅延回路120から出力される2L-Sサイクル前の中間結果データGS-1(k-2L-S)を用いたバタフライ演算を行い、バタフライ演算後のデータGS(k-2L-S)及びGS(k)を生成する。そして、一方のバタフライ演算結果GS(k-2L-S)は、セレクタ素子116を介してシーケンス変換部140の第2入力ポートSIN2に送られる。また、他方のバタフライ演算結果GS(k)は、セレクタ素子117を介してシーケンス変換部140の第1入力ポートSIN1に送られる。
【００４９】
シーケンス変換部140に配置されたセレクタ142のセレクタ素子143及び144は、bL-S+1(C)=1のときはbS(C)が0か1かで動作を変える。すなわち、bL-S+1(C)=1かつbS(C)＝0であるとき、セレクタ素子143及び144は、図3に示されたポート#A側を選択し、入力データをストレートに出力する。そして、bL-S+1(C)=1かつbS(C)＝1であるとき、セレクタ素子143及び144は、図3に示されたポート#B側を選択し、入力データをクロス出力する。したがって、bL-S+1(C)=1かつbS(C)＝0であるとき、シーケンス変換部140は、第2入力ポートSIN2に与えられた中間結果データGS(k-2L-S)を次ステージのバタフライPE 10_S+1に送るとともに、遅延回路141から出力される2S-1サイクル前に得られた中間結果データGS(k)を遅延回路120に送る。bL-S+1(C)=1かつbS(C)＝1であるとき、シーケンス変換部140は、第2入力ポートSIN2に与えられた中間結果データGS(k-2L-S)を遅延回路120に送るとともに、遅延回路141から出力される2S-1サイクル前に得られた中間結果データGS(k)を次ステージのバタフライPE 10_S+1に送る。遅延回路120に入力されたバタフライ演算結果データは、(2L-S-2S-1)サイクル遅延されるとともに、bL-S+1(C)=0であるときに次ステージのバタフライPE 10_S+1へ送られる。
【００５０】
以上に述べたバタフライPE 10_Sの動作は、以下に示す具体例を参照することによってより理解されるであろう。図4A及び4Bは、N=16（すなわちL=4）の例において、第1ステージのバタフライPE 10_1に設けられたバタフライプロセッサ110及びシーケンス変換部140の入出力データを示すテーブルである。参考のために、図4A及びBは、カウンタ値Cの10進表記（DEC.）及び2進表記（BIN.）、セレクタ115の選択ポート（#0又は#1）、並びにセレクタ142の選択ポート（#A又は#B）も示している。図4A及びBの例では、b4(C)=0であるとき、すなわちカウンタ値Cの10進表記が0〜7のとき、遅延回路141によって1サイクル遅延された時間領域シーケンスX（C-1）が遅延回路820に送られる。また、遅延回路120から出力される7サイクル前に計算されていた中間結果データG1（C-7）（又は、G1(C+16-7)）が第2ステージのバタフライPE 10_2へ送られる。
【００５１】
さらに、図4A及びBの例では、b4(C)=1かつb1(C)=0であるとき、すなわちカウンタ値Cの10進表記が8、10、12、14のとき、1サイクル前に遅延回路141に格納されたデータが遅延回路120に送られ、当サイクルで得られた中間結果データG1(C)がシーケンス変換部140の遅延回路141に新たに格納され、当サイクルで得られた中間結果データG1(C-8)が第2ステージのバタフライPE 10_2へ送られる。また、b4(C)=1かつb1(C)=1であるとき、すなわちカウンタ値Cの10進表記が9、11、13、15のとき、遅延回路141から出力される1サイクル前に計算されていた中間結果データG1（C-1）が第2ステージのバタフライPE 10_2へ送られ、当サイクルで得られた中間結果データG1（C）が遅延回路141に新たに格納され、当サイクルで得られた中間結果データG1(C-8)が遅延回路120に送られる。
【００５２】
以上に述べた動作によって、図4A及びBの"SOUT2"の列を見ると明らかであるように、第1ステージのバタフライPE 10_1の出力データ順序は、2進表記されたDFGインデックスiの最下位ビットb1(i)が1である中間結果データG1(i)が、最下位ビットb1(i)が0である中間結果データG1(i)より後に出力されるように変更されている。すなわち、DFGインデックスが奇数である中間結果データG1（2m+1）は、DFGインデックスが偶数である中間結果データG1（2m）よりも後に出力される。
【００５３】
続いて、図5の具体例を説明する。図5は、N=16（すなわちL=4）の例において、第2ステージのバタフライPE 10_2に設けられたバタフライプロセッサ110及びシーケンス変換部140の入出力データを示すテーブルである。したがって、図5の"BIN2"の列に示されているように、第2ステージのバタフライPE 10_2の第2入力ポートBIN2には、図4A及び4Bの"SOUT2"の列に示された順序に従って第1ステージによる中間結果データG1が入力される。
【００５４】
図5の例では、b3(C)=0であるとき、すなわちカウンタ値Cの10進表記が0〜3及び8〜11のとき、遅延回路141によって2サイクル遅延されたデータが遅延回路120に送られ、Cサイクル目に受信された第1ステージの中間結果データG1が遅延回路141に新たに格納され、遅延回路120によって2サイクル遅延されたデータが第3ステージのバタフライPE 10_2へ送られる。
【００５５】
さらに、図5の例では、b3(C)=1かつb2(C)=0であるとき、すなわちカウンタ値Cの10進表記が4、5、12、13のとき、2サイクル前に遅延回路141に格納されたデータが遅延回路120に送られ、当サイクルで得られた中間結果データG2(k)がシーケンス変換部140の遅延回路141に新たに格納され、当サイクルで得られた中間結果データG2(k-4)が第3ステージのバタフライPE 10_3へ送られる。また、b3(C)=1かつb2(C)=1であるとき、すなわちカウンタ値Cの10進表記が6、7、14、15のとき、遅延回路141から出力される2サイクル前に計算されていた中間結果データG2（k）が第3ステージのバタフライPE 10_3へ送られ、当サイクルで得られた中間結果データG2（k）が遅延回路141に新たに格納され、当サイクルで得られた中間結果データG2(k-4)が遅延回路120に送られる。
【００５６】
以上に述べた動作によって、図5の"SOUT2"の列を見ると明らかであるように、第2ステージのバタフライPE 10_2の出力データ順序（DFGインデックスの出力順序）は、DFGインデックスiが"0"である先頭の出力データから順に8個ずつの出力データを単位として、この8個の出力データ内においてb2(i)＝1である中間結果データG2(i)が、b2(i)＝0である中間結果データG2(i)より後に出力されるように変更されている。例えば、b1(i)＝0である8個の中間結果データを見ると、b2(i)＝1である4つのデータG2(2)、G2(10)、G2(6)、及びG2(14)は、b2(i)＝0である4つのデータG2(0)、G2(8)、G2(4)、及びG2(12)よりも後に出力される。また、b1(i)＝1である8個の中間結果データを見ると、b2(i)＝1である4つのデータG2(3)、G2(11)、G2(7)、及びG2(15)は、b2(i)＝0である4つのデータG2(1)、G2(9)、G2(5)、及びG2(13)よりも後に出力される。
【００５７】
なお、N=16のとき、第2ステージは第LHFステージに相当する。したがって、第2ステージのバタフライPE 10_2から出力される中間結果シーケンスG2（k）のデータ順序（DFGインデックスの出力順序）は、2進表記されたDFGインデックスのbit reversed orderになっている。
【００５８】
続いて以下では、パイプラインの後半に配置されたLHS個の第2タイプのバタフライPE 11の構成および動作について説明する。図6は、第Sステージの第2タイプのバタフライPE 11_Sの構成例を示すブロック図である。ここでは、SはLHF+1以上L以下の整数（S=LHF+1, …, L）である。図6に示された第2タイプのバタフライPE 11_Sは、バタフライプロセッサ150、遅延回路160、及びカウンタ170を含む。第2タイプのバタフライPE 11_Sは、シーケンス変換部140に相当する回路ブロックを有していない。したがって、第2タイプのバタフライPE 11_Sの構成は、図12に示したバタフライPE 80_Sの構成と同様とすればよい。ただし、第1〜第LHFステージまでの第1タイプのバタフライPE 10によって生成される中間結果データGLHFの出力順序（DFGインデックス順序）は上述した通り変更されている。したがって、第LHFステージの中間結果データGLHFの出力順序（DFGインデックス順序）に従って第LHF+1ステージ以降のバタフライ演算を正しく行うために、第2タイプのバタフライPE 11_Sが有する遅延フィードバック用の遅延回路160の遅延量は2L-Sから2S-1に変更されている。
【００５９】
バタフライプロセッサ150の基本構成は、図12に示したバタフライプロセッサ810の構成と同様である。図7は、バタフライプロセッサ150の構成例を示すブロック図である。図7に示された加算器151、減算器152、乗算器153、回転子選択部154、及びセレクタ155（セレクタ素子156及び157を含む）は、図13A及び図13Bに示された加算器811、減算器812、乗算器813、回転子選択部814、及びセレクタ815（セレクタ素子816及び817を含む）にそれぞれ対応する。ただし、第Sステージにおけるバタフライ演算の順序が異なることから、回転子選択部154による回転子WNKの選択順序は、必然的に、回転子選択部814によるそれとは異なる。さらに、カウンタ値Cに応じたセレクタ155の動作（選択論理）も、セレクタ815のそれとは異なる。
【００６０】
カウンタ170の構成及び動作は図12に示されたカウンタ830と同様とすればよい。すなわち、カウンタ170は、Lビット・カウンタであり、前ステージのバタフライPEからDFGインデックス"0"の出力データGS-1(0)が入力されるタイミングで0にリセットされる。カウンタ170は、カウンタ値Cをバタフライプロセッサ150に供給する。
【００６１】
次に、第Sステージ（S=LHF+1, …, L）の第2タイプのバタフライPE 11_Sの動作について説明する。バタフライPE 11_Sは、第LHFステージの出力データ順序（DFGインデックスの出力順序）、すなわち2進表記されたDFGインデックスのbit reversed order、に従ってN/2回のバタフライ演算を行い、このDFGインデックス順序のまま出力シーケンスGS（k）を出力する。具体的には、カウンタ値Cを2進表記したときの最下位（LSB）からS番目のビットが0であるとき（すなわち、bS(C)=0のとき）、セレクタ155のセレクタ素子156及び157は、図7に示されたポート#0側を選択する。これにより、前ステージのバタフライPEからCサイクル目に受信された中間結果データGS-1(k) は、バタフライ演算を行われること無く遅延回路160へ送られる。
【００６２】
一方、bS(C)=1であるとき、セレクタ115のセレクタ素子156及び157は、図7に示されたポート#1側を選択する。バタフライプロセッサ150は、前ステージのバタフライPE からCサイクル目に受信された中間結果データGS-1(k)と遅延回路120から出力される2S-1サイクル前の中間結果データGS-1(k-2L-S)を用いたバタフライ演算を行い、バタフライ演算後のデータGS(k-2L-S)及びGS(k)を生成する。そして、一方のバタフライ演算結果GS-1(k-2L-S)は、セレクタ素子156を介して次ステージのバタフライPE 11_S+1へ送られる。また、他方のバタフライ演算結果GS(k)は、セレクタ素子157を介して遅延回路160へ送られる。遅延回路160に入力されたバタフライ演算結果GS(k)は、2S-1サイクル遅延されるとともに、bS(C)=0であるときに次ステージのバタフライPE 11_S+1へ送られる。
【００６３】
図8は、N=16（すなわちL=4）の例において、第3ステージの第2タイプのバタフライPE 11_3に設けられたバタフライプロセッサ150の入出力データを示すテーブルである。したがって、図8の"IN2"の列に示されているように、第3ステージのバタフライPE 11_3の第2入力ポートIN2には、図5の"SOUT2"の列に示された順序（すなわち、DFGインデックスのbit reversed order）に従って第2ステージによる中間結果データG2が入力される。図8の例では、b3(C)=1であるとき、すなわちカウンタ値Cの10進表記が4〜6及び12〜15のとき、当サイクルで得られた中間結果データG3(k)が遅延回路160へ送られ、当サイクルで得られた中間結果データG3(k-4)が第4ステージのバタフライPE 11_4へ送られる。また、b3(C)=0であるとき、すなわちカウンタ値Cの10進表記が0〜3及び8〜11のとき、当サイクルで受信された第2ステージの中間結果データG2が遅延回路160に送られ、遅延回路160から出力される4サイクル前に計算されていた中間結果データG3（k）が第4ステージのバタフライPE 11_4へ送られる。
【００６４】
以上に述べた動作によって、図8の"OUT2"の列を見ると明らかであるように、第3ステージのバタフライPE 11_3の出力データにおけるDFGインデックスの出力順序は、入力データと同じ2進表記されたDFGインデックスのbit reversed orderとなっている。
【００６５】
続いて以下では、本実施形態に係るパイプラインFFT回路1の遅延量について考察する。第1タイプのバタフライPE 10_Sの遅延量は、遅延回路120による遅延量と、シーケンス変換部140内の遅延回路141による遅延量を合わせて以下の式(7)で表される。したがって、LHF個の第1タイプのバタフライPE 10による遅延量の合計は、以下の式(8)で表される。
【数７】
2014013726.tif 000009
【数８】
2014013726.tif 000010
【００６６】
また、LHS個の第2タイプのバタフライPE 11による遅延量の合計は、以下の式(9)で表される。
【数９】
2014013726.tif 000011
【００６７】
したがって、FFT回路1の総遅延量は、式(8)及び(9)の和、つまり以下の式(10)により表される。
【数１０】
2014013726.tif 000012
【００６８】
式(10)で表されるFFT回路1の総遅延量は、式(4)で表されるFFT回路8の総遅延量に比べて小さい。例えば、N=16（L=4）の場合、FFT回路8の総遅延量は31サイクルであるのに対して、本実施形態に係るFFT回路1の総遅延量は24サイクルで済む。
【００６９】
以上に説明したように、本実施形態に係るFFT回路1は、LHF個の第1タイプのバタフライPE 10、及びLHS個の第2タイプのバタフライPE 11が連結されたRadix-2 DIF SDFアーキテクチャのFFT演算パイプラインを有する。そして、第1タイプのバタフライPE 10の各々は、小規模なハードウェアによるシーケンス変換機構を有している。したがって、第1タイプのバタフライPE 10_1〜10_LHFは、中間結果シーケンスGS（k）のデータ順序を逐次的に入れ替えることができる。そして、この逐次的なデータ順序の入れ替えによって、LHF個のバタフライPE 10_は、第LHFステージのバタフライPE 10_LHFから出力される中間結果シーケンスGLHF（k）のデータ順序（DFGインデックスの出力順序）を、2進表記されたDFGインデックスのbit reversed orderに変換するよう構成されている。
【００７０】
より具体的には、第Sステージ（S=1, …, LHF）のバタフライPE 10_Sは、DFGインデックスiが"0"である先頭の出力データから順にN/(2S-1)個ずつの出力データを単位として、このN/(2S-1)個の出力データ内においてbS(i)＝1である中間結果データGS(i)は、bS(i)＝0である中間結果データGS(i)より後に出力されるように出力データ順序を並び替える。
【００７１】
一方、後半の第(LHF+1)ステージから第Lステージまでに配置された第2タイプのバタフライPE 11_の各々は、入力データのDFGインデックス順序を保ったまま、すなわちDFGインデックスのbit reversed orderで出力シーケンスGS（k）を出力するよう構成されている。
【００７２】
以上の構成により、本実施形態に係るFFT回路1は、natural orderの入力シーケンスに基づいてnatural orderの出力シーケンスを出力することができ、かつ式(9)に示したように総遅延量を低減することができる。
【００７３】
＜その他の実施形態＞
第1の実施形態で述べたFFT回路1は、伝送路を介して送信又は受信されるデータ列に対してＦＦＴ処理を行ってもよい。FFT回路1は、例えば、OFDM受信機（e.g. LTE方式の通信端末、無線LAN機器、及びデジタルテレビ放送受信機）に好適である。すなわち、FFT回路1は、OFDM受信機において、受信OFDM信号から複素シンボル列を抽出するためのFFT処理を実行してもよい。
【００７４】
また、第1の実施形態で述べたFFT回路1は、IC（Integrated Circuit）チップに実装されてもよい。FFT回路1は、総遅延量が小さく遅延回路の回路規模を低減できるため、ICチップの回路規模を抑制できる。
【００７５】
また、第1の実施形態は、Radix-2 DIF SDFアーキテクチャのFFT回路1について説明した。しかしながら、第1の実施形態で説明した技術思想は、例えば、他のSDF アーキテクチャのFFT回路にも適用できる。例えば、第1の実施形態で説明した技術思想は、Radix-2 DIT SDF、Radix-22 DIF SDF、又はRadix-2n DIT SDFアーキテクチャのFFT回路に適用されてもよい。Radix-2nは、例えば、Radix-22、Radix-23、Radix-24などである。
【００７６】
さらに、上述した実施形態は本件発明者により得られた技術思想の適用に関する例に過ぎない。すなわち、当該技術思想は、上述した実施形態のみに限定されるものではなく、種々の変更が可能であることは勿論である。
【００７７】
例えば、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
ＦＦＴ（Fast Fourier Transform）回路であって、
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを備え、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えるよう構成されている、
ただし、ＮはＦＦＴポイント数であり、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数であり、ｂＳ（ｉ）は前記ＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する、
ＦＦＴ回路。
（付記２）
前記ＬＨＦ個の第１のバタフライ演算要素は、各ステージでの中間結果シーケンスのデータ順序を逐次的に入れ替えることによって、第ＬＨＦステージの第１のバタフライ演算要素から出力される中間結果シーケンスのデータ順序を、ＤＦＧ（Data Flow Graph）インデックスのbit reversed orderに変換するよう動作する、
付記１に記載のＦＦＴ回路
（付記３）
前記ＬＨＳ個の第２のバタフライ演算要素は、第ＬＨＦステージの中間結果シーケンスのデータ順序を維持することによって、第Ｌステージの第２のバタフライ演算要素からnatural orderの周波数領域シーケンスを出力するよう構成されている、
付記１又は２に記載のＦＦＴ回路。
（付記４）
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、データパス及びフィードバックパスにデータを出力する第１のバタフライプロセッサ、前記フィードバックパスに配置された第１の遅延回路、及びシーケンス変換回路を含み、
前記シーケンス変換回路は、前記第１のバタフライプロセッサの出力及び前記第１の遅延回路の入力の間の前記フィードバックパス上に配置された第２の遅延回路、及び前記第２の遅延回路の出力及び前記１の遅延回路の入力の間の前記フィードバックパスと前記データパスの間で信号経路を切替えるセレクタを含む、
付記１〜３のいずれか１項に記載のＦＦＴ回路。
（付記５）
前記第１の遅延回路は遅延量（２Ｌ−Ｓ−２Ｓ−１）を有し、
前記第２の遅延回路は遅延量２Ｓ−１を有する、
付記４に記載のＦＦＴ回路。
（付記６）
前記ＬＨＳ個の第２のバタフライ演算要素の各々は、第２のバタフライプロセッサ、及び前記第２のバタフライプロセッサのフィードバックパスに配置された遅延量２Ｓ−１を有する第３の遅延回路を含む、
付記４又は５に記載のＦＦＴ回路。
（付記７）
前記パイプラインは、Ｒａｄｉｘ−２パイプライン又はＲａｄｉｘ−２ｎパイプラインである、
付記１〜６のいずれか１項に記載のＦＦＴ回路。
（付記８）
前記ＦＦＴ回路は、伝送路を介して送信又は受信されるデータ列に対してＦＦＴ処理を行う、
付記１〜７のいずれか１項に記載のＦＦＴ回路。
（付記９）
前記ＦＦＴ回路は、受信ＯＦＤＭ（Orthogonal Frequency Division Multiplexing）信号から複素シンボル列を抽出するためのＦＦＴ処理を行う、
付記１〜８のいずれか１項に記載のＦＦＴ回路。
（付記１０）
前記ＦＦＴ回路は、ＩＣ（Integrated Circuit）チップに実装されている、
付記１〜９のいずれか１項に記載のＦＦＴ回路。
（付記１１）
ＦＦＴ（Fast Fourier Transform）回路であって、
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを備え、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記ＬＨＦ個の第１のバタフライ演算要素は、各ステージでの中間結果シーケンスのデータ順序を逐次的に入れ替えることによって、第ＬＨＦステージの第１のバタフライ演算要素から出力される中間結果シーケンスのデータ順序を、ＤＦＧ（Data Flow Graph）インデックスのbit reversed orderに変換するよう構成され、
前記ＬＨＳ個の第２のバタフライ演算要素は、第ＬＨＦステージの中間結果シーケンスのデータ順序を維持することによって、第Ｌステージの第２のバタフライ演算要素からnatural orderの周波数領域シーケンスを出力するよう構成されている、
ＦＦＴ回路。
（付記１２）
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えるよう動作する、
ただし、ＮはＦＦＴポイント数であり、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数であり、ｂＳ（ｉ）は前記ＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する、
付記１１に記載のＦＦＴ回路。
（付記１３）
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、データパス及びフィードバックパスにデータを出力する第１のバタフライプロセッサ、前記フィードバックパスに配置された第１の遅延回路、及びシーケンス変換回路を含み、
前記シーケンス変換回路は、前記第１のバタフライプロセッサの出力及び前記第１の遅延回路の入力の間の前記フィードバックパス上に配置された第２の遅延回路、及び前記第２の遅延回路の出力及び前記１の遅延回路の入力の間の前記フィードバックパスと前記データパスの間で信号経路を切替えるセレクタを含む、
ただし、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数である、
付記１１又は１２に記載のＦＦＴ回路。
（付記１４）
ＦＦＴ（Fast Fourier Transform）回路であって、
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを備え、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、データパス及びフィードバックパスにデータを出力する第１のバタフライプロセッサ、前記フィードバックパスに配置された第１の遅延回路、及びシーケンス変換回路を含み、
前記シーケンス変換回路は、前記第１のバタフライプロセッサの出力及び前記第１の遅延回路の入力の間の前記フィードバックパス上に配置された第２の遅延回路、及び前記第２の遅延回路の出力及び前記１の遅延回路の入力の間の前記フィードバックパスと前記データパスの間で信号経路を切替えるセレクタを含む、
ただし、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数である、
ＦＦＴ回路。
（付記１５）
前記第１の遅延回路は遅延量（２Ｌ−Ｓ−２Ｓ−１）を有し、
前記第２の遅延回路は遅延量２Ｓ−１を有する、
付記１４に記載のＦＦＴ回路。
（付記１６）
前記ＬＨＳ個の第２のバタフライ演算要素の各々は、第２のバタフライプロセッサ、及び前記第２のバタフライプロセッサのフィードバックパスに配置された遅延量２Ｓ−１を有する第３の遅延回路を含む、
付記１４又は１５に記載のＦＦＴ回路。
（付記１７）
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを用いてＦＦＴ（Fast Fourier Transform）を行う方法であって、
第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個のバタフライ演算要素によって、ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えることを備える、
ただし、ＮはＦＦＴポイント数であり、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数であり、ｂＳ（ｉ）は前記ＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する、
方法。
（付記１８）
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを用いてＦＦＴ（Fast Fourier Transform）を行う方法であって、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記方法は、
前記ＬＨＦ個の第１のバタフライ演算要素によって、各ステージでの中間結果シーケンスのデータ順序を逐次的に入れ替えることによって、第ＬＨＦステージの第１のバタフライ演算要素から出力される中間結果シーケンスのデータ順序を、ＤＦＧ（Data Flow Graph）インデックスのbit reversed orderに変換すること、及び
前記ＬＨＳ個の第２のバタフライ演算要素によって、第ＬＨＦステージの中間結果シーケンスのデータ順序を維持することによって、第Ｌステージの第２のバタフライ演算要素からnatural orderの周波数領域シーケンスを出力すること、
を備える、方法。
【００７８】
この出願は、２０１２年７月１８日に出願された日本出願特願２０１２−１５９３５３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００７９】
1  FFT (Fast Fourier Transform) 回路
10  第1タイプのバタフライPE (Processing Element)
11  第2タイプのバタフライ PE (Processing Element)
110  バタフライプロセッサ
111  加算器
112  減算器
113  乗算器
114  回転子選択部
115  セレクタ
116  セレクタ素子
117  セレクタ素子
120  遅延回路
130  カウンタ
140  シーケンス変換部
141  遅延回路
142  セレクタ
143  セレクタ素子
144  セレクタ素子
150  バタフライプロセッサ
151  加算器
152  減算器
153  乗算器
154  回転子選択部
155  セレクタ
156  セレクタ素子
157  セレクタ素子
160  遅延回路
170  カウンタ
【図１】
2014013726.tif 000013
【図２】
2014013726.tif 000014
【図３】
2014013726.tif 000015
【図４Ａ】
2014013726.tif 000016
【図４Ｂ】
2014013726.tif 000017
【図５】
2014013726.tif 000018
【図６】
2014013726.tif 000019
【図７】
2014013726.tif 000020
【図８】
2014013726.tif 000021
【図９】
2014013726.tif 000022
【図１０】
2014013726.tif 000023
【図１１】
2014013726.tif 000024
【図１２】
2014013726.tif 000025
【図１３Ａ】
2014013726.tif 000026
【図１３Ｂ】
2014013726.tif 000027
【図１４】
2014013726.tif 000028
【図１５】
2014013726.tif 000029
【手続補正書】
【提出日】平成28年3月10日(2016.3.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＦＦＴ（Fast Fourier Transform）回路であって、
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを備え、
前記パイプラインは、前記Ｌ個のバタフライ演算要素によるＬステージの演算処理によってＮ個の入力データに対するＮポイントのＤＦＴ（Discrete Fourier Transform）を実行し、ここで、Ｌ＝ｌｏｇ２Ｎであり、
ＤＦＧ（Data Flow Graph）インデックスｉは、natural orderのＮ個の入力シーケンスからbit reversed order のＮ個の出力ＤＦＴシーケンスを生成するためのＬステージから成るデータフローグラフ（ＤＦＧ）上での各ステージの出力データ順序を表す０以上且つＮ−１以下の正数であり、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、前記ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えるよう構成されている、
ただし、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数であり、ｂＳ（ｉ）は前記ＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する、
ＦＦＴ回路。
【請求項２】
前記ＬＨＦ個の第１のバタフライ演算要素は、各ステージでの中間結果シーケンスのデータ順序を逐次的に入れ替えることによって、第ＬＨＦステージの第１のバタフライ演算要素から出力される中間結果シーケンスのデータ順序を、前記ＤＦＧ（Data Flow Graph）インデックスのbit reversed orderに変換するよう動作する、
請求項１に記載のＦＦＴ回路。
【請求項３】
前記ＬＨＳ個の第２のバタフライ演算要素は、第ＬＨＦステージの中間結果シーケンスのデータ順序を維持することによって、第Ｌステージの第２のバタフライ演算要素からnatural orderの周波数領域シーケンスを出力するよう構成されている、
請求項１又は２に記載のＦＦＴ回路。
【請求項４】
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、データパス及びフィードバックパスにデータを出力する第１のバタフライプロセッサ、前記フィードバックパスに配置された第１の遅延回路、及びシーケンス変換回路を含み、
前記シーケンス変換回路は、前記第１のバタフライプロセッサの出力及び前記第１の遅延回路の入力の間の前記フィードバックパス上に配置された第２の遅延回路、並びに前記第２の遅延回路の出力及び前記１の遅延回路の入力の間の前記フィードバックパスと前記データパスとの間で信号経路を切替えるセレクタを含む、
請求項１〜３のいずれか１項に記載のＦＦＴ回路。
【請求項５】
前記第１の遅延回路は、前記第１の遅延回路に入力されるデータを（２Ｌ−Ｓ−２Ｓ−１）サイクル遅延して出力し、
前記第２の遅延回路は、前記第２の遅延回路に入力されるデータを２Ｓ−１サイクル遅延して出力する、
請求項４に記載のＦＦＴ回路。
【請求項６】
前記ＬＨＳ個の第２のバタフライ演算要素の各々は、第２のバタフライプロセッサ、及び前記第２のバタフライプロセッサのフィードバックパスに配置された第３の遅延回路を含み、
前記第３の遅延回路は、前記第３の遅延回路に入力されるデータを２Ｓ−１サイクル遅延して出力する、
請求項４又は５に記載のＦＦＴ回路。
【請求項７】
前記パイプラインは、Ｒａｄｉｘ−２  ＤＩＦ（Decimation In Frequency）  ＦＦＴ、Ｒａｄｉｘ−２２  ＤＩＦ  ＦＦＴ、又はＲａｄｉｘ−２ｎ  ＤＩＴ（Decimation In Time）  ＦＦＴを実行するパイプラインである、
請求項１〜６のいずれか１項に記載のＦＦＴ回路。
【請求項８】
ＦＦＴ（Fast Fourier Transform）回路であって、
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを備え、
前記パイプラインは、前記Ｌ個のバタフライ演算要素によるＬステージの演算処理によってＮ個の入力データに対するＮポイントのＤＦＴ（Discrete Fourier Transform）を実行し、ここで、Ｌ＝ｌｏｇ２Ｎであり、
ＤＦＧ（Data Flow Graph）インデックスｉは、natural orderのＮ個の入力シーケンスからbit reversed order のＮ個の出力ＤＦＴシーケンスを生成するためのＬステージから成るデータフローグラフ（ＤＦＧ）上での各ステージの出力データ順序を表す０以上且つＮ−１以下の正数であり、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記ＬＨＦ個の第１のバタフライ演算要素は、各ステージでの中間結果シーケンスのデータ順序を逐次的に入れ替えることによって、第ＬＨＦステージの第１のバタフライ演算要素から出力される中間結果シーケンスのデータ順序を、前記ＤＦＧ（Data Flow Graph）インデックスのbit reversed orderに変換するよう構成され、
前記ＬＨＳ個の第２のバタフライ演算要素は、第ＬＨＦステージの中間結果シーケンスのデータ順序を維持することによって、第Ｌステージの第２のバタフライ演算要素からnatural orderの周波数領域シーケンスを出力するよう構成されている、
ＦＦＴ回路。
【請求項９】
ＦＦＴ（Fast Fourier Transform）回路であって、
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを備え、
前記Ｌ個のバタフライ演算要素は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個の第１のバタフライ演算要素と、第（ＬＨＦ＋１）ステージ〜第Ｌステージに相当するＬＨＳ個（ただしＬＨＦ＋ＬＨＳ＝Ｌ）の第２のバタフライ演算要素を含み、
前記ＬＨＦ個の第１のバタフライ演算要素の各々は、データパス及びフィードバックパスにデータを出力する第１のバタフライプロセッサ、前記フィードバックパスに配置された第１の遅延回路、及びシーケンス変換回路を含み、
前記シーケンス変換回路は、前記第１のバタフライプロセッサの出力及び前記第１の遅延回路の入力の間の前記フィードバックパス上に配置された第２の遅延回路、及び前記第２の遅延回路の出力及び前記１の遅延回路の入力の間の前記フィードバックパスと前記データパスの間で信号経路を切替えるセレクタを含む、
ＦＦＴ回路。
【請求項１０】
ＳＤＦ（Single-path Delay Feedback）アーキテクチャのＬ個のバタフライ演算要素が連結されたパイプラインを用いてＦＦＴ（Fast Fourier Transform）を行う方法であって、
前記パイプラインは、前記Ｌ個のバタフライ演算要素によるＬステージの演算処理によってＮ個の入力データに対するＮポイントのＤＦＴ（Discrete Fourier Transform）を実行し、ここで、Ｌ＝ｌｏｇ２Ｎであり、
ＤＦＧ（Data Flow Graph）インデックスｉは、natural orderのＮ個の入力シーケンスからbit reversed order のＮ個の出力ＤＦＴシーケンスを生成するためのＬステージから成るデータフローグラフ（ＤＦＧ）上での各ステージの出力データ順序を表す０以上且つＮ−１以下の正数であり、
前記方法は、第１ステージ〜第ＬＨＦステージに相当するＬＨＦ個のバタフライ演算要素によって、前記ＤＦＧ（Data Flow Graph）インデックスｉが"０"である先頭の出力データから順にＮ／（２Ｓ−１）個ずつの出力データを単位として、このＮ／（２Ｓ−１）個の出力データ内においてｂＳ（ｉ）＝１である中間結果データＧＳ（ｉ）はｂＳ（ｉ）＝０である中間結果データＧＳ（ｉ）より後に出力されるように出力データ順序を並び替えることを備える、
ただし、Ｓはステージ番号を表す１以上ＬＨＦ以下の整数であり、ｂＳ（ｉ）は前記ＤＦＧインデックスｉを２進表記したときの最下位からＳ番目のビットを意味する、
方法。
【国際調査報告】
2014013726.tif 000030
2014013726.tif 000031