(57)【要約】本発明は高速フーリエ変換、例えば複素８点高速フーリエ変換に基づく複素６４点高速フーリエ変換を実施するための方法及び回路装置、並びにこの使用に関する。高速フーリエ変換を実施するための回路装置は、並列または直列に配置された入力バッファ（ＩＢ）、ＦＦＴブロック（ＦＦＴ）、乗算器（Ｍ）及びバッファ（Ｂ１／Ｂ２）から構成されている。ここでＦＦＴブロック（ＦＦＴ）は８点高速フーリエ変換に基づく６４点高速フーリエ変換を基礎とし、加算、減算及びシフトレジスタ演算を用いて乗算を行い、必要な係数は一定でＦＦＴブロックにおいてインプリメントされている。乗算器（Ｍ）は加算、減算及びシフトレジスタ演算からのみ乗算を行う。バッファ（Ｂ１／Ｂ２）はバッファメモリとしてもデータ出力メモリ（ＯＰ）としても使用される。
2004516551.tif 000002
【特許請求の範囲】
【請求項１】
データ信号の高速フーリエ変換を実施する方法において、
データ信号を１つまたは複数の並列に配置された入力バッファ（ＩＢ）において読み取り、
前記データ信号を前記入力バッファ（ＩＢ）の出力側において並列に供給し、
前記入力バッファ（ＩＢ）の出力側において並列に供給されたデータ信号をブロック内で１つのＦＦＴブロック（ＦＦＴ）に伝送し、
前記ＦＦＴブロック（ＦＦＴ）は、６４点高速フーリエ変換の８点高速フーリエ変換への分解に基づき変換を行い、
前記ＦＦＴブロック（ＦＦＴ）は内部において、加算、減算及びシフトレジスタ演算を用いて乗算を行い、
前記ＦＦＴブロック（ＦＦＴ）は、該ＦＦＴブロック（ＦＦＴ）内でインプリメントされた係数を用いて変換を行い、
前記ＦＦＴブロック（ＦＦＴ）から生じる直列のデータ信号は乗算器（Ｍ）を通過し、
該乗算器（Ｍ）の通過後に該データ信号をバッファ（Ｂ１）に一時記憶し、
前記乗算器（Ｍ）において１と乗算すべき、前記ＦＦＴブロック（ＦＦＴ）から生じる直列のデータ信号を、前記乗算器（Ｍ）の迂回により直接に前記バッファ（Ｂ１）に一時記憶し、
前記バッファ（Ｂ１）に一時記憶されたデータ信号を該バッファ（Ｂ１）の出力側において並列に供給し、
前記バッファ（Ｂ１）から並列に供給されたデータ信号を再び前記ＦＦＴブロック（ＦＦＴ）に書き込み、
前記データ信号を前記ＦＦＴブロック（ＦＦＴ）の通過後に、前記乗算器（Ｍ）の迂回により前記バッファ（Ｂ１）に一時記憶し、
前記バッファ（Ｂ１）からのデータ信号を直列に出力側（ＯＰ）において読み出す、
ことを特徴とする、データ信号の高速フーリエ変換を実施する方法。
【請求項２】
前記入力バッファ（ＩＰ）の出力側において並列に供給されるデータ信号をブロック内で１つのＦＦＴブロック（ＦＦＴ）に伝送し、
前記ＦＦＴブロック（ＦＦＴ）から生じる直列のデータ信号は前記乗算器（Ｍ）を通過し、
前記データ信号を前記乗算器（Ｍ）の通過後に前記バッファ（Ｂ１）に一時記憶し、
前記乗算器（Ｍ）において１と乗算すべき、前記ＦＦＴブロック（ＦＦＴ）から生じる直列のデータ信号を、前記乗算器（Ｍ）の迂回により直接に前記バッファ（Ｂ１）に一時記憶し、
前記バッファ（Ｂ１）に一時記憶された前記データ信号を該バッファ（Ｂ１）の出力側において並列に供給し、
前記バッファ（Ｂ１）から並列に供給された前記データ信号を、別のＦＦＴブロック（ＦＦＴ）に書き込み、
前記データ信号を前記別のＦＦＴブロック（ＦＦＴ）の通過後にバッファ（Ｂ２）に一時記憶し、該バッファ（Ｂ２）の出力側に並列に供給し、
前記バッファ（Ｂ２）からの前記データ信号を直列に出力側（ＯＰ）において読み出す、
請求項１記載の方法。
【請求項３】
前記乗算器（Ｍ）は、加算、減算及びシフトレジスタ演算のみから乗算を行い、複数の乗算演算を並行して行う、請求項１または２記載の方法。
【請求項４】
前記入力側（ＩＰ）ならびに前記出力側（ＯＰ）における前記データ信号の虚部と実部を交換することによって逆高速フーリエ変換を行う、請求項１から３のうちのいずれか１項または複数項記載の方法。
【請求項５】
前記乗算器（Ｍ）を迂回または省略し、ＦＦＴブロック内の係数を変えることによって、離散８×８点コサイン及び／又はサイン変換を行う、請求項１から４のうちのいずれか１項または複数項記載の方法。
【請求項６】
請求項１から５記載の方法を実施する回路装置において、
１つまたは複数の並列または直列に配置された入力バッファ（ＩＢ）と、
１つまたは複数のＦＦＴブロック（ＦＦＴ）と、
１つの乗算器（Ｍ）と、
１つまたは複数のバッファ（Ｂ１／Ｂ２）とから構成されており、
前記ＦＦＴブロック（ＦＦＴ）は、８点高速フーリエ変換に基づく６４点高速フーリエ変換の分解を基礎とし、加算、減算及びシフトレジスタ演算を用いて乗算を行い、必要な係数は一定であって前記ＦＦＴブロック（ＦＦＴ）においてインプリメントされており、
前記乗算器（Ｍ）は加算、減算及びシフトレジスタ演算のみから乗算を行い、
前記バッファ（Ｂ１／Ｂ２）はバッファメモリとしても、データ交換メモリ（ＯＰ）としても使用される、
ことを特徴とする、請求項１から５記載の方法を実施する回路装置。
【請求項７】
請求項６記載の回路装置を用いる請求項１から５記載の方法の使用において、
遠隔通信、データ圧縮、光学、確率計算、量子力学、信号理論及び通信技術において使用することを特徴とする、請求項６記載の回路装置を用いる請求項１から５記載の方法の使用。
【発明の詳細な説明】
【０００１】
本発明は請求項１から７記載の特徴による、高速フーリエ変換、例えば複素８点高速フーリエ変換に基づく複素６４点高速フーリエ変換を実施するための方法及び回路装置、並びにこの方法の使用に関する。
【０００２】
高速フーリエ変換は、例えば光学、確率計算、量子力学、信号理論、通信技術のような種々の領域、また他の多くの領域においても使用される。多くの場合、ＦＦＴ／ＩＦＦＴの（処理の意味における）迅速なインプリメンテーションが必要とされる。ＩＥＥＥ８０２．１１ａ及びハイパーＬＡＮ２のような移動無線システムのデータ伝送の場合、これに加えさらにエネルギに関して効率的な解決策が要求される。大部分のインプリメンテーションはＣｏｏｌｙ及びＴｕｋｅｙによって発明された方法によって行われたものであり、例えばＪ．Ｗ．Ｃｏｏｌｙ及びＪ．Ｗ．Ｔｕｋｅｙ、Ｍａｔｈ．Ｃｏｍｐｕｔａｔｉｏｎ、ｖｏｌ１９、１９６５年、２９７から３０１頁に記載されている。これらの方法は乗算の回数が多く、このことは比較的高いエネルギ消費の原因となる。
【０００３】
例えばＦＦＴを下位単位（より小さいＦＦＴ）へと分解し、この下位単位をローテート演算によって再び１つのより大きなＦＦＴへと構成する方法も公知である。１つの例は、Ｇ．Ｄ．Ｂｅｒｇｌａｎｄ、Ｍａｔｈ．Ｃｏｍｐｕｔａｔｉｏｎ、ｖｏｌ２２、１９６８年４月、２７５から２７９頁に記載されている。４点ＦＦＴを用いてＦＦＴを分解する類似の方式は、Ｂ．Ｓｕｔｅｒ、Ｋ．Ｓｔｅｖｅｎｓによるアメリカ合衆国特許明細書第５８３１８８３号、１９９８年１１月３日に記載されている。ここで４点ＦＦＴの乗算は、慣例の（非同期式）逐次乗算器またはブース乗算器によって実現される。
【０００４】
既述した公知のインプリメンテーションの変形では乗算及び加算の演算回数が多くなる。必要な乗算器及び加算器の個数が多く、また方法が複雑であることは比較的高いエネルギ消費の原因となる。このエネルギ消費は処理能力を制限しまた多くのチップ面積を必要とする。
【０００５】
したがって本発明の課題は、従来技術の上述した欠点を克服し、計算時間が短く、エネルギ効率が高くまた記憶スペースに対する要求が少ない装置及び方法を提供することである。
【０００６】
高速フーリエ変換を実施するための本発明による回路装置は、１つまたは複数の直列又は並列に配置された入力バッファＩＢと、１つまたは複数のＦＦＴブロックＦＦＴと、１つの乗算器Ｍと、１つまたは複数のバッファＢ１／Ｂ２とから構成されている。ここでＦＦＴブロックは８点高速フーリエ変換に基づく６４点高速フーリエ変換の分解を基礎としており、加算、減算及びシフトレジスタ演算を使用して乗算を行い、必要な係数は一定でありＦＦＴブロックＦＦＴにおいてインプリメントされている。乗算器Ｍは加算、減算及びシフトレジスタ演算のみから乗算を行う。バッファＢ１／Ｂ２はバッファメモリとしてもデータ出力メモリＯＰとしても使用される。
【０００７】
本発明の方法では、データ信号が１つまたは複数の並列に配置された複数の入力バッファＩＢにおいて読み取られ、入力バッファＩＢの出力側において並列に供給され、ブロック内で１つのＦＦＴブロックＦＦＴに伝送される。ＦＦＴブロックＦＦＴは、６４点高速フーリエ変換の分解に基づく８点高速変換への変換を実行し、内部において加算、減算及びシフトレジスタ演算を使用して乗算を行い、またＦＦＴブロックＦＦＴにおいてインプリメントされた係数を用いて変換を行う。ＦＦＴブロックＦＦＴから生じる直列のデータ信号は乗算器Ｍを通過し、ここでこの乗算器Ｍは加算、減算及びシフトレジスタ演算だけに基づき乗算を行い、次にこのデータ信号はバッファＢ１に一時記憶される。乗算器Ｍにおいて１と乗算すべきＦＦＴブロックＦＦＴから生じた直列のデータ信号は、乗算器Ｍを迂回して直接バッファＢ１に一時記憶される。バッファＢ１の出力側において供給された並列のデータ信号は、再びＦＦＴブロックＦＦＴに書き込まれるか、または別のＦＦＴブロックＦＦＴに書き込まれる。多重式の変形形態では、データ信号はＦＦＴブロックＦＦＴを通過した後に乗算器Ｍを迂回し、バッファＢ１内に一時記憶されて、直列に出力側ＯＰにおいて読み出される。「パイプライン式」の変形形態では、データ信号は別のＦＦＴブロックＦＦＴを通過した後に、乗算器Ｍを迂回し、第２のバッファＢ２内に一時記憶されて、直列に出力側ＯＰにおいて読み出される。
【０００８】
乗算器Ｍは加算、減算及びシフトレジスタ演算のみに基づき乗算を行い、複数の乗算演算を並行して行うことができる。逆高速フーリエ変換は入力側及び出力側におけるデータ信号の虚部と実部を交換することによって行われる。乗算器Ｍを迂回または省略し、ＦＦＴブロックＦＦＴ内の係数を変化させることによって、離散８×８点コサイン及び／又はサイン変換が行われる。
【０００９】
本発明による解決策の利点は以下のことを基礎とする。すなわち、
−計算時間が短く、エネルギ効率が高くまた記憶スペースの要求が少ない、迅速なインプリメンテーション。すなわちこのインプリメンテーションはエネルギを節約し、スペースを取らずかつより迅速である。
【００１０】
−この方式のインプリメンテーションを例えばＣＰＵ、コントローラ、ＤＳＰのような電気回路のための方法として使用できるか、または直接的に電気的に機能する回路としても使用することができる。
【００１１】
−複雑性が低減しているので（僅かな乗算器）、丸め誤差はより少なくなる。
【００１２】
−電気的に機能する回路としてインプリメントする場合には、グローバルメモリを使用しなくても良い。
【００１３】
−ＦＦＴブロックＦＦＴ内の係数は一定でインプリメントされている。
【００１４】
−係数は乗算器Ｍにおいて多くは必要とされない。
【００１５】
本発明の特徴は、請求項以外にも明細書及び図面からも明らかになる。個々の特徴はそれぞれ、それだけまたは複数を組み合わせた形で保護すべき実施形態を表し、これらに対して本発明は保護を請求する。本発明の実施例は図面に図示されており、以下詳細に説明する。ここで図１は、１つの入力バッファＢ１、１つの８点ＦＦＴブロックＦＦＴ、１つのバッファＢを備えたブロック回路図であり、ＦＦＴの多重式の変形実施形態である。図２は、１つの入力バッファＩＢ、２つの８点ＦＦＴブロックＦＦＴ２つのバッファＢ１／Ｂ２を備えたブロック回路図であり、ＦＦＴの「パイプライン式」の変形実施形態である。
【００１６】
例１：
図１に図示したこの実施例においては、処理すべきデータは先ず装置の入力側ＩＰにおいて入力バッファＩＢに記憶され、次いで処理のために８点ＦＦＴの８グループへと供給される。この計算に続いて、複素乗算器Ｍ内でローテート演算が行われ、データはバッファＢ１に記憶される。このプロセスは全ての入力データが処理されるまで繰り返される。すなわち６４ＦＦＴの場合には丁度８回の処理が行われる。その後上述のシェーマに従い、バッファＢ１からのデータの更なる８点ＦＦＴを行う。全ての計算が終了するとデータはバッファＢ１にあり、出力側ＯＰにおいて読み出される。１つの８点ＦＦＴブロックＦＦＴ及び１つのバッファＢ１ならびに１つの乗算器Ｍが必要である。
【００１７】
例２：
図２は、１つの入力バッファＩＢ、２つの８点ＦＦＴブロックＦＦＴ及び２つのメモリを備えた回路装置を示す。この変形実施形態ではデータは先ず入力バッファＩＢを介して８点ＦＦＴブロックＦＦＴに伝送される。出力側では乗算及びバッファＢ１への一時記憶を行う。その後更なる８点ＦＦＴが別の８点ＦＦＴブロックＦＦＴにおいて実施される。次いでデータはバッファＢ２に書き込まれる。このバッファＢ２は出力バッファとして使用される。データは出力側ＯＰにおいて読み出される。２つの８点ＦＦＴブロックＦＦＴ及び２つのバッファＢ１／Ｂ２ならびに１つの乗算器Ｍが必要である。
【００１８】
例３：
例１及び２の変形である別の変形実施形態においては、２つの並列の入力バッファＩＢが使用される。これによってデータ伝送量を高めることができる。目下のＦＦＴ操作が終了する前に、次の６４データのシリアルパラレル変換を開始することができる。
【００１９】
例４：
例１から３の変形であり、入力側ＩＰならびに出力側ＯＰにおけるデータ信号の虚部と実部を交換することによって逆高速フーリエ変換を行う。
【００２０】
例５：
図１から３の変形であり、乗算器Ｍを迂回または省略し、ＦＦＴブロック内の係数を変化させることによって、離散８×８コサイン及び／又はサイン変換が行われる。
【００２１】
例１から５に記載した方法を実施するための回路装置は１つまたは複数の並列に配置された入力バッファＩＢ、１つまたは複数のＦＦＴブロックＦＦＴ、１つの乗算器Ｍ及び１つまたは複数のバッファＢ１／Ｂ２から構成されている。ＦＦＴブロックは、６４点高速フーリエ変換の８点高速フーリエ変換への分解を基礎とし、加算、減算及びシフトレジスタ演算を使用して乗算を行い、必要な係数は一定でありＦＦＴブロックＦＦＴにおいてインプリメントされている。乗算器Ｍは加算、減算及びシフトレジスタ演算のみに基づき乗算を行う。バッファＢ１／Ｂ２はバッファメモリとしてもデータ出力バッファとしても使用される。この回路装置は図１から２に図示されている。
【００２２】
本発明の方法は、例えば遠隔通信、データ圧縮、光学、確率計算、量子力学、信号理論及び通信技術に使用される。
【００２３】
上述の記述においては具体的な実施例に基づいて、高速フーリエ変換、例えば８点高速フーリエ変換に基づく複素６４点高速フーリエ変換を実施するための方法及び回路装置、ならびに本発明の使用を説明した。しかしながら本発明の方法は実施例における説明の詳細に制限されるものではないことを言及しておく。
【図面の簡単な説明】
【図１】
入力バッファＩＢ、８点ＦＦＴブロックＦＦＴ、バッファＢを備えたブロック図であり、ＦＦＴの多重式の変形実施形態である。
【図２】
入力バッファＩＢ、８点ＦＦＴブロックＦＦＴ、２つのバッファＢ１／Ｂ２を備えたブロック図であり、ＦＦＴの「パイプライン式」の変形実施形態である。
【国際公開パンフレット】
2004516551.tif 000003
2004516551.tif 000004
2004516551.tif 000005
2004516551.tif 000006
2004516551.tif 000007
2004516551.tif 000008
2004516551.tif 000009
2004516551.tif 000010
2004516551.tif 000011
2004516551.tif 000012
2004516551.tif 000013
2004516551.tif 000014
2004516551.tif 000015
【国際公開パンフレット（コレクトバージョン）】
2004516551.tif 000016
2004516551.tif 000017
【国際調査報告】
2004516551.tif 000018
2004516551.tif 000019
2004516551.tif 000020
2004516551.tif 000021
2004516551.tif 000022
2004516551.tif 000023
2004516551.tif 000024
2004516551.tif 000025
2004516551.tif 000026
2004516551.tif 000027