(57)【要約】【課題】メモリサイズを減少させうる高速フーリエ変換プロセッサ及び高速フーリエ変換方法を提供する。【解決手段】それぞれの演算段階で入力データのインデックス値から得られるパリティ値によって分類されて２個のシングルポートメモリに保存されたＮポイントのデータ対に対して一つのクロックサイクルごとに２回のｒａｄｉｘ−２  バタフライ演算を行ってその演算結果を２個のシングルポートメモリに保存することによって、ＦＦＴ演算を行う高速フーリエ変換（ＦＦＴ）プロセッサ。ＦＦＴプロセッサでは、少数のゲートを有するシングルポートメモリを含むので、ＦＦＴ演算に必要なメモリサイズを減少させうる。【選択図】図５
2006221648.tif 000002
【特許請求の範囲】
【請求項１】
高速フーリエ変換アルゴリズムを行う高速フーリエ変換プロセッサにおいて、
第１パリティ値を有するアップ入力データ対を第１アドレスに保存した後、前記アップ入力データ対に対応する偶数演算段階の出力データ対を前記第１アドレスに再保存する第１アップシングルポートメモリと、
第２パリティ値を有するダウン入力データ対を第２アドレスに保存した後、前記ダウン入力データ対に対応する偶数演算段階の出力データ対を前記第２アドレスに再保存する第１ダウンシングルポートメモリと、
前記アップ入力データ対に対応する奇数演算段階の出力データ対を第３アドレスに保存する第２アップシングルポートメモリと、
前記ダウン入力データ対に対応する奇数演算段階の出力データ対を第４アドレスに保存する第２ダウンシングルポートメモリと、
前記奇数及び偶数演算段階において、前記アップ入力データ対のうち一つに対応する入力データ対及び前記ダウン入力データ対のうち一つに対応する入力データ対に対して、ｒａｄｉｘ−２  バタフライ演算して前記出力データ対のうち一つをそれぞれ生成する第１及び第２バタフライ演算器と、を備えることを特徴とする高速フーリエ変換プロセッサ。
【請求項２】
前記高速フーリエ変換プロセッサは、
前記第１アップ及びダウンシングルポートメモリ、前記第２アップ及びダウンシングルポートメモリ、及び前記第１及び第２バタフライ演算器が前記高速フーリエ変換アルゴリズムのデータ流れを行うように制御する第１及び第２スイッチ回路をさらに備えることを特徴とする請求項１に記載の高速フーリエ変換プロセッサ。
【請求項３】
前記第１及び第２パリティ値は、前記アップ及びダウン入力データ対に含まれた入力データのインデックス値から最下位ビットを除いた残りのビットを用いて計算される奇数パリティ値であることを特徴とする請求項１に記載の高速フーリエ変換プロセッサ。
【請求項４】
前記第１、第２、第３、及び第４アドレスの数はそれぞれ同一であり、前記第１、第２、第３、及び第４アドレスのそれぞれに含まれるアドレスは同じ方式で番号付けられることを特徴とする請求項１に記載の高速フーリエ変換プロセッサ。
【請求項５】
前記アップ入力データ対及び前記ダウン入力データ対の数がそれぞれ４個である場合、前記偶数演算段階の偶数の最大値は４であることを特徴とする請求項１に記載の高速フーリエ変換プロセッサ。
【請求項６】
前記高速フーリエ変換アルゴリズムは、ＤＩＦアルゴリズムとして実現されることを特徴とする請求項１に記載の高速フーリエ変換プロセッサ。
【請求項７】
前記第１及び第２スイッチ回路は、前記高速フーリエ変換プロセッサの全体を制御する高速フーリエ変換コントローラにより制御されることを特徴とする請求項２に記載の高速フーリエ変換プロセッサ。
【請求項８】
入力データに対して高速フーリエ変換を行う方法において、
前記入力データをそれぞれのインデックス値が第１パリティ値を有するアップ入力データ対及びそれぞれのインデックス値が第２パリティ値を有するダウン入力データ対に分離する段階と、
前記アップ入力データ対を第１アップシングルポートメモリの第１アドレスに保存し、前記アップ入力データ対に対応する前記高速フーリエ変換のアルゴリズムの偶数演算段階（ｓｔａｇｅ）の出力データ対を前記第１アップシングルポートメモリの第１アドレスに再保存する段階と、
前記ダウン入力データ対を前記第１ダウンシングルポートメモリの第２アドレスに保存し、前記ダウン入力データ対に対応する偶数演算段階の出力データ対を前記第１ダウンシングルポートメモリの第２アドレスに再保存する段階と、
前記アップ入力データ対に対応する前記高速フーリエ変換のアルゴリズムの奇数演算段階（ｓｔａｇｅ）の出力データ対を第２アップシングルポートメモリの第３アドレスに保存する段階と、
前記ダウン入力データ対に対応する奇数演算段階の出力データ対を第２ダウンシングルポートメモリの第４アドレスに保存する段階と、
前記奇数及び偶数演算段階において、前記アップ入力データ対のうち一つに対応する入力データ対及び前記ダウン入力データ対のうち一つに対応する入力データ対に対して、ｒａｄｉｘ−２  バタフライ演算を行うことにより前記出力データ対を生成する段階と、を含むことを特徴とする高速フーリエ変換方法。
【請求項９】
前記第１及び第２パリティ値は、前記アップ及びダウン入力データ対に含まれた入力データのインデックス値から最下位ビットを除いた残りのビットを用いて計算される奇数パリティ値であることを特徴とする請求項８に記載の高速フーリエ変換方法。
【請求項１０】
前記第１、第２、第３、及び第４アドレスの数はそれぞれ同一であり、前記第１、第２、第３、及び第４アドレスのそれぞれに含まれるアドレスは同じ方式で番号付けられることを特徴とする請求項８に記載の高速フーリエ変換方法。
【請求項１１】
前記高速フーリエ変換のアルゴリズムは、ＤＩＦアルゴリズムとして実現されることを特徴とする請求項８に記載の高速フーリエ変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有無線通信システムに係り、より詳細には、有無線通信のための送受信機内で変調または復調時に用いられる高速フーリエ変換（以下、ＦＦＴという）プロセッサ及び高速フーリエ変換方法に関する。
【背景技術】
【０００２】
無線ＬＡＮ（Ｗｉｒｅｌｅｓｓ  ＬＡＮ）、ＡＤＳＬ（Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅ）、ＶＤＳＬ（Ｖｅｒｙ  Ｈｉｇｈ−ｄａｔａ  Ｒａｔｅ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅ）、ＯＦＤＭ（Ｏｒｔｈｏｇｏｎａｌ  Ｆｒｅｑｕｅｎｃｙ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）、ＤＡＢ（Ｄｉｇｉｔａｌ  Ａｕｄｉｏ  Ｂｒｏａｄｃａｓｔｉｎｇ）、またはＭＣＭ（Ｍｕｌｔｉ−ｃａｒｒｉｅｒ  Ｍｏｄｕｌａｔｉｏｎ）などのシステムのための送受信機内にはＦＦＴを行うプロセッサが備えられる。
【０００３】
ＦＦＴアルゴリズムは、下記の数式１のような離散フーリエ変換（Ｄｉｓｃｒｅｔｅ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ）での反復計算を除去して演算量を減らす方法である。
【０００４】
【数１】
2006221648.tif 000003
【０００５】
数式１で、ｎは時間インデックス、ｋは周波数インデックス、Ｎはデータポイントの数、
【０００６】
【数２】
2006221648.tif 000004
である。
【０００７】
このようなＦＦＴアルゴリズムが適用された装置の一例が特許文献１に開示されている。
【０００８】
一般に、受信機で行われるＦＦＴは、時間領域の信号を周波数領域の信号に変換する。これに対応して送信機で行われる逆ＦＦＴは、周波数領域の信号を時間領域の信号に変換する。
【０００９】
図１は、一般的な１６−ポイントｒａｄｉｘ−２  ＤＩＦ（Ｄｅｃｉｍａｔｉｏｎ  Ｉｎ  Ｆｒｅｑｕｅｎｃｙ）ＦＦＴアルゴリズムの信号フローチャートである。すなわち、図１はデータポイントの数Ｎが１６である場合のＦＦＴ演算を示す。
【００１０】
図１を参照すると、入力データｘ（０）〜ｘ（１５）は、４個（＝ｌｏｇ２１６）の演算段階を通じて順次に処理されて出力データｘ（０）〜ｘ（１５）として出力される。例えば、それぞれの入力データｘ（０）〜ｘ（１５）は、２０ビットの幅を有しうる。それぞれの演算段階ではｒａｄｉｘ−２  バタフライ演算が行われ、第１演算段階では８個の回転因子Ｗ１６０〜Ｗ１６７が、第２演算段階では４個の回転因子Ｗ１６０、Ｗ１６２、Ｗ１６４、Ｗ１６６が、第３演算段階では２個の回転因子Ｗ１６０、Ｗ１６４が必要である。出力データｘ（０）〜ｘ（１５）は、逆デジット順（Ｒｅｖｅｒｓｅ  Ｄｉｇｉｔ  Ｏｒｄｅｒ）に出力され、正常な順序で整列されて等化器に入力されうる。
【００１１】
図２は、従来技術による図１のＦＦＴアルゴリズムを実現するための４個のデュアルポートメモリの配置を示す図である。図２を参照すると、入力データｘ（０）〜ｘ（１５）のうち第１入力データグループｘ（０）〜ｘ（７）は、第１アップデュアルポートメモリＵＰＤ１の第１ないし第８アドレスにそれぞれ保存（または書込み）される。その後、第１入力データグループｘ（０）〜ｘ（７）に対応する第２及び第４演算段階（すなわち、偶数演算段階）の出力データ（すなわち、ｒａｄｉｘ−２  バタフライ演算の結果は、第１アップデュアルポートメモリＵＰＤ１の第１ないし第８アドレスにそれぞれ再保存（または上書き）される。
【００１２】
入力データｘ（０）〜ｘ（１５）のうち第２入力データグループｘ（８）〜ｘ（１５）は、第１ダウンデュアルポートメモリＤＮＤ１の第１ないし第８アドレスにそれぞれ保存される。その後、第２入力データグループｘ（８）〜ｘ（１５）に対応する偶数演算段階の出力データは、第１ダウンデュアルポートメモリＤＮＤ１の第１ないし第８アドレスにそれぞれ再保存される。
【００１３】
第１入力データグループｘ（０）〜ｘ（７）に対応する第１及び第３演算段階（すなわち、奇数演算段階）の出力データは、第２アップデュアルポートメモリＵＰＤ２の第１ないし第８アドレスにそれぞれ再保存される。
【００１４】
第２入力データグループｘ（８）〜ｘ（１５）に対応する奇数演算段階の出力データは、第２ダウンデュアルポートメモリＤＮＤ２の第１ないし第８アドレスにそれぞれ再保存される。
【００１５】
図３は、図２の４個のデュアルポートメモリを含む従来技術によるＦＦＴプロセッサを示すブロック図である。図３を参照すると、従来のＦＦＴプロセッサ１００は、第１アップデュアルポートメモリＵＰＤ１、第１ダウンデュアルポートメモリＤＮＤ１、第２アップデュアルポートメモリＵＰＤ２、第２ダウンデュアルポートメモリＤＮＤ２、第１バタフライ演算器１１０、第２バタフライ演算器１２０、第１スイッチ回路（ＳＷ１）１３０、及び第２スイッチ回路（ＳＷ２）１４０を含む。
【００１６】
ＦＦＴプロセッサ１００は、第１及び第２バタフライ演算器１１０、１２０を用いて１クロックサイクルごとに２回のｒａｄｉｘ−２  バタフライ演算を行う。したがって、入力データの数が１６個である場合、それぞれの演算段階を行うために４クロックサイクルが必要であり、４個の演算段階を行うために全体１６クロックサイクルが必要である。
【００１７】
第１入力データグループｘ（０）〜ｘ（７）のうち２つまたは第１入力データグループｘ（０）〜ｘ（７）に対応する偶数演算段階の出力データのうち２つが第１アップデュアルポートメモリＵＰＤ１の第１及び第２ポートＰＵ１１、ＰＵ２１を通じて同時に入力／出力される（すなわち、書込み／読出しされる）。
【００１８】
第２入力データグループｘ（８）〜ｘ（１５）のうち２つまたは第２入力データグループｘ（８）〜ｘ（１５）に対応する偶数演算段階の出力データのうち２つが第１ダウンデュアルポートメモリＤＮＤ１の第１及び第２ポートＰＤ１１、ＰＤ２１を通じて同時に入力／出力される。
【００１９】
第１入力データグループｘ（０）〜ｘ（７）に対応する奇数演算段階の出力データのうち２つが第２アップデュアルポートメモリＵＰＤ２の第１及び第２ポートＰＵ１２、ＰＵ２２を通じて同時に入力／出力される。
【００２０】
第２入力データグループｘ（８）〜ｘ（１５）に対応する奇数演算段階の出力データのうち２つが第２ダウンデュアルポートメモリＤＮＤ２の第１及び第２ポートＰＤ１２、ＰＤ２２を通じて同時に入力／出力される。
【００２１】
第１バタフライ演算器１１０の第１ないし第４端子Ｔ１１〜Ｔ４１を通じてｒａｄｉｘ−２  バタフライ演算のための入力／出力データが入力／出力される。すなわち、第１及び第２端子Ｔ１１、Ｔ２１は、奇数演算段階で入力端子として使われ、偶数演算段階で出力端子として使われる。そして、第３及び４端子Ｔ３１、Ｔ４１は、偶数演算段階で入力端子として使われ、奇数演算段階で出力端子として使われる。例えば、第１演算段階で、第１入力データであるｘ（０）及びｘ（０）とバタフライ演算が行われる第９入力データであるｘ（８）が第１バタフライ演算器１１０の第１端子Ｔ１１及び第２端子Ｔ２１を通じてそれぞれ入力される。第１ないし第３演算段階で、第１バタフライ演算器１１０にＦＦＴ演算に必要な回転因子（Ｗ16K、Ｋ＝０〜７の整数）が供給される。
【００２２】
第２バタフライ演算器１２０の第１ないし第４端子Ｔ１２〜Ｔ４２を通じてｒａｄｉｘ−２  バタフライ演算のための入力／出力データが入力／出力される。すなわち、第１及び第２端子Ｔ１２、Ｔ２２は、奇数演算段階で入力端子として使われ、偶数演算段階で出力端子として使われる。そして、第３及び４端子Ｔ３２、Ｔ４２は、偶数演算段階で入力端子として使われ、奇数演算段階で出力端子として使われる。例えば、第１演算段階で、第２入力データであるｘ（１）及びｘ（１）とバタフライ演算が行われる第１０入力データであるｘ（９）が第１端子Ｔ１２及び第２端子Ｔ２２を通じてそれぞれ入力される。第１ないし第３演算段階で、第２バタフライ演算器１２０にＦＦＴ演算に必要な回転因子（Ｗ16K、Ｋ＝０〜７の整数）が供給される。
【００２３】
第１及び第２スイッチ回路１３０、１４０は、４個のデュアルポートメモリＵＰＤ１、ＤＮＤ１、ＵＰＤ２、ＤＮＤ２とバタフライ演算器１１０、１２０とが図１に示されたＦＦＴアルゴリズムの信号流れ（またはデータ流れ）を行うように制御する。
【００２４】
第１スイッチ回路１３０の動作を第１演算段階を例えて説明する。第１アップデュアルポートメモリＵＰＤ１の第２ポートＰＵ２１を通じて出力されるデータｘ（１）は、第１スイッチ回路１３０により第２バタフライ演算器１２０の第１端子Ｔ１２に伝えられ、第１ダウンデュアルポートメモリＤＮＤ１の第１ポートＰＤ１１を通じて出力されるデータｘ（８）は、第１スイッチ回路１３０により第１バタフライ演算器１１０の第２端子Ｔ２１に伝えられる。第１演算段階での第２スイッチ回路１４０の動作も前記した第１演算段階における第１スイッチ回路１３０の動作と同様なので、その説明は省略する。
【００２５】
図４は、図３に示された第１または第２バタフライ演算器をさらに詳細に示す図である。図４を参照すると、第１または第２バタフライ演算器１１０、１２０は、複素数加算器１１１、複素数減算器１１２、及び複素数乗算器１１３を含む。
【００２６】
複素数加算器１１１は、入力端子を通じて入力された第１入力データＩＮ１及び第２入力データＩＮ２を加算して出力端子を通じて第１出力データＯＵＴ１を出力する。複素数減算器１１２は、第１入力データＩＮ１から第２入力データＩＮ２を減算して複素数乗算器１１３に出力する。複素数乗算器１１３は、複素数減算器１１２の出力値に対応する回転因子（Ｗ16K、Ｋ＝０〜７の整数）を乗算して出力端子を通じて第２出力データＯＵＴ２を出力する。
【００２７】
図３に示されたデュアルポートメモリ（例えば、デュアルポートＲＡＭは、デュアルポートメモリと同じビット容量（＝ビット幅×ビット深さ）を有するシングルポートメモリ（例えば、シングルポートＲＡＭ）に比較すると、ほとんど２倍のゲートを含む。このようなメモリのポートの数に比例するゲートの数は、メモリのビット容量が増加するだけ増加する。したがって、デュアルポートメモリを用いてＦＦＴアルゴリズムを実現した従来のＦＦＴプロセッサは、ＦＦＴ演算に必要なメモリサイズを増加させうる。
【特許文献１】米国特許第６，３５６，９２６号明細書
【発明の開示】
【発明が解決しようとする課題】
【００２８】
本発明が達成しようとする技術的課題は、ゲート数が相対的に少ないシングルポートメモリを用いることによって、ＦＦＴ演算に必要なメモリサイズを減少させうる高速フーリエ変換（ＦＦＴ）プロセッサ及び高速フーリエ変換（ＦＦＴ）方法を提供することである。
【課題を解決するための手段】
【００２９】
前記技術的課題を達成するために本発明に係る高速フーリエ変換（ＦＦＴ）プロセッサは、高速フーリエ変換（ＦＦＴ）アルゴリズムを行う。
【００３０】
本発明のＦＦＴプロセッサは、第１パリティ値を有するアップ入力データ対を第１アドレスに保存した後、前記アップ入力データ対に対応する偶数演算段階の出力データ対を前記第１アドレスに再保存する第１アップシングルポートメモリと、第２パリティ値を有するダウン入力データ対を第２アドレスに保存した後、前記ダウン入力データ対に対応する偶数演算段階の出力データ対を前記第２アドレスに再保存する第１ダウンシングルポートメモリと、前記アップ入力データ対に対応する奇数演算段階の出力データ対を第３アドレスに保存する第２アップシングルポートメモリと、前記ダウン入力データ対に対応する奇数演算段階の出力データ対を第４アドレスに保存する第２ダウンシングルポートメモリと、前記奇数及び偶数演算段階において、前記アップ入力データ対のうち一つに対応する入力データ対及び前記ダウン入力データ対のうち一つに対応する入力データ対に対して、ｒａｄｉｘ−２  バタフライ演算して前記出力データ対のうち一つをそれぞれ生成する第１及び第２バタフライ演算器と、を備えることを特徴とする。
【００３１】
望ましい実施例によれば、前記ＦＦＴプロセッサは、前記第１アップ及びダウンシングルポートメモリ、前記第２アップ及びダウンシングルポートメモリ、及び前記第１及び第２バタフライ演算器が前記ＦＦＴアルゴリズムのデータ流れを行うように制御する第１及び第２スイッチ回路をさらに備える。
【００３２】
望ましい実施例によれば、前記第１及び第２パリティ値は、前記アップ及びダウン入力データ対に含まれた入力データのインデックス値から最下位ビットを除いた残りのビットを用いて計算される奇数パリティ値である。
【００３３】
望ましい実施例によれば、前記第１、第２、第３、及び第４アドレスの数はそれぞれ同一であり、前記第１、第２、第３、及び第４アドレスのそれぞれに含まれるアドレスは同じ方式で番号付けられる。
【００３４】
望ましい実施例によれば、前記アップ入力データ対及び前記ダウン入力データ対の数がそれぞれ４個である場合、前記偶数演算段階の偶数の最大値は４である。
【００３５】
望ましい実施例によれば、前記ＦＦＴアルゴリズムは、ＤＩＦアルゴリズムとして実現され、前記第１及び第２スイッチ回路は、前記ＦＦＴプロセッサの全体を制御するＦＦＴコントローラにより制御される。
【００３６】
前記技術的課題を達成するために本発明に係る高速フーリエ変換（ＦＦＴ）方法は、入力データに対してＦＦＴを行う。本発明のＦＦＴ方法は、前記入力データをそれぞれのインデックス値が第１パリティ値を有するアップ入力データ対及びそれぞれのインデックス値が第２パリティ値を有するダウン入力データ対に分離する段階と、前記アップ入力データ対を第１アップシングルポートメモリの第１アドレスに保存し、前記アップ入力データ対に対応する前記高速フーリエ変換のアルゴリズムの偶数演算段階の出力データ対を前記第１アップシングルポートメモリの第１アドレスに再保存する段階と、前記ダウン入力データ対を前記第１ダウンシングルポートメモリの第２アドレスに保存し、前記ダウン入力データ対に対応する偶数演算段階の出力データ対を前記第１ダウンシングルポートメモリの第２アドレスに再保存する段階と、前記アップ入力データ対に対応する前記高速フーリエ変換のアルゴリズムの奇数演算段階の出力データ対を第２アップシングルポートメモリの第３アドレスに保存する段階と、前記ダウン入力データ対に対応する奇数演算段階の出力データ対を第２ダウンシングルポートメモリの第４アドレスに保存する段階と、前記奇数及び偶数演算段階において、前記アップ入力データ対のうち一つに対応する入力データ対及び前記ダウン入力データ対のうち一つに対応する入力データ対に対して、ｒａｄｉｘ−２  バタフライ演算を行うことにより前記出力データ対を生成する段階と、を含むことを特徴とする。
【発明の効果】
【００３７】
本発明に係るＦＦＴプロセッサ及びＦＦＴ方法は、相対的に少数のゲートを有するシングルポートメモリを用いてＦＦＴアルゴリズムを行うので、ＦＦＴ演算に必要なメモリサイズを減少させうる。
【発明を実施するための最良の形態】
【００３８】
本発明とその動作上の利点及び本発明の実施によって達成される目的を十分に理解するためには本発明の望ましい実施形態を例示する添付図面及び添付図面に記載された内容を参照しなければならない。
【００３９】
以下、添付した図面に基づき、本発明の望ましい実施形態を説明することにより本発明を詳細に説明する。各図面に付された同一参照符号は同一部材を示す。
【００４０】
図５は、本発明の実施例による図１のＦＦＴアルゴリズムを実現するための４個のシングルポートメモリの配置を示す図である。
【００４１】
１６個の入力データのインデックス値から得られる第１パリティ値を有するアップ入力データ対{ｘ（０）、ｘ（１）}、{ｘ（６）、ｘ（７）}、{ｘ（１０）、ｘ（１１）}、{ｘ（１２）、ｘ（１３）}は、第１アップシングルポートメモリＵＰＳ１の第１アドレスにそれぞれ順次に保存される。その後、アップ入力データ対に対応する第２及び第４演算段階（すなわち、偶数演算段階）の出力データ対は、第１アップシングルポートメモリＵＰＳ１の第１アドレスにそれぞれ順次に再保存される。
【００４２】
１６個の入力データのインデックス値から得られる第２パリティ値を有するダウン入力データ対{ｘ（２）、ｘ（３）}、{ｘ（４）、ｘ（５）}、{ｘ（８）、ｘ（９）}、{ｘ（１４）、ｘ（１５）}は、第１ダウンシングルポートメモリＤＮＳ１の第２アドレスにそれぞれ順次に保存される。その後、ダウン入力データ対に対応する偶数演算段階の出力データ対は、第１ダウンシングルポートメモリＤＮＳ１の第２アドレスにそれぞれ順次に再保存される。
【００４３】
アップ入力データ対に対応する第１及び第３演算段階（すなわち、奇数演算段階）の出力データ対は、第２アップシングルポートメモリＵＰＳ２の第３アドレスにそれぞれ順次に再保存される。
【００４４】
ダウン入力データ対に対応する奇数演算段階の出力データ対は、第２ダウンシングルポートメモリＤＮＳ２の第４アドレスにそれぞれ順次に再保存される。
【００４５】
前記第１、第２、第３、及び第４アドレスの数は、それぞれ同一であり、前記第１、第２、第３、及び第４アドレスのそれぞれに含まれるアドレスは、同じ方式で番号付けられることが望ましい。
【００４６】
図６は、図５の第１アップ及びダウンシングルポートメモリに保存される入力データ対及び入力データ対が保存されるアドレスを示す表である。図６を参照すると、第１アップシングルポートメモリＵＰＳ１の第１アドレス０〜３にアップ入力データ対{ｘ（０）、ｘ（１）}、{ｘ（６）、ｘ（７）}、{ｘ（１０）、ｘ（１１）}、{ｘ（１２）、ｘ（１３）}がそれぞれ保存され、第１ダウンシングルポートメモリＤＮＳ１の第２アドレス０〜３にダウン入力データ対{ｘ（２）、ｘ（３）}、{ｘ（４）、ｘ（５）}、{ｘ（８）、ｘ（９）}、{ｘ（１４）、ｘ（１５）}がそれぞれ保存される。
【００４７】
したがって、本発明に係るＦＦＴプロセッサのシングルポートメモリは、従来のＦＦＴプロセッサ１００のデュアルポートメモリと同じビット容量を有するが、従来のＦＦＴプロセッサ１００のデュアルポートメモリに保存されるデータと比較してビット幅が２倍に増加し、ビット深さが１／２倍に減少したデータを保存できる。したがって、本発明に係るＦＦＴプロセッサのシングルポートメモリは、従来のＦＦＴプロセッサ１００のデュアルポートメモリが有するアドレスの数の１／２のアドレスを有する。
【００４８】
所定の入力データ対が第１アップシングルポートメモリＵＰＳ１に保存されるか、第１ダウンシングルポートメモリＤＮＳ１に保存されるかどうかは、入力データのインデックス値から最下位ビット（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ：ＬＳＢ）を除いた残りのビットを用いて計算される奇数パリティ値により決定される。例えば、入力データ対{ｘ（０）、ｘ（１）}の場合、そのインデックス値がそれぞれ“００００（＝０）”及び“０００１（＝１）”であり、最下位ビット以外のビットがそれぞれ“０００”であり、その奇数パリティ値は第１パリティ値である０であるので、{ｘ（０）、ｘ（１）}は、第１アップシングルポートメモリＵＰＳ１に保存される。一方、入力データ対{ｘ（２）、ｘ（３）}の場合、そのインデックス値がそれぞれ“００１０（＝２）”及び“００１１（＝３）”で最下位ビット以外のビットがそれぞれ"００１"であり、その奇数パリティ値は第２パリティ値である１であるので、{ｘ（２）、ｘ（３）}は、第１ダウンシングルポートメモリＤＮＳ１に保存される。残りの入力データ対にも前記のような方式が適用されて保存されるシングルポートメモリの種類が決定される。一方、本発明の他の実施例では、第１パリティ値を有する入力データ対が第１ダウンシングルポートメモリＤＮＳ１に保存され、第２パリティ値を有する入力データ対が第１アップシングルポートメモリＵＰＳ１に保存されることもある。
【００４９】
図７は、図５の４個のシングルポートメモリを含む本発明の実施例によるＦＦＴプロセッサを示すブロック図である。図７を参照すると、本発明に係るＦＦＴプロセッサ２００は、第１アップシングルポートメモリＵＰＳ１、第１ダウンシングルポートメモリＤＮＳ１、第２アップシングルポートメモリＵＰＳ２、第２ダウンシングルポートメモリＤＮＳ２、第１バタフライ演算器２１０、第２バタフライ演算器２２０、第１スイッチ回路（ＳＷ１）２３０、及び第２スイッチ回路（ＳＷ２）２４０を含む。
【００５０】
ＦＦＴプロセッサ２００は、第１及び第２バタフライ演算器２１０、２２０を用いて１クロックサイクルごとに２回のｒａｄｉｘ−２  バタフライ演算を行う。したがって、入力データの数が１６個である場合、それぞれの演算段階を行うために４クロックサイクルが必要であり、４個の演算段階を行うために全体１６クロックサイクルが必要である。
【００５１】
アップ入力データ対{ｘ（０）、ｘ（１）}、{ｘ（６）、ｘ（７）}、{ｘ（１０）、ｘ（１１）}、{ｘ（１２）、ｘ（１３）}のうち一つまたは前記アップ入力データ対に対応する偶数演算段階の出力データ対のうち一つが第１アップシングルポートメモリＵＰＳ１のポートＰＵ１を通じて同時に入力／出力される。
【００５２】
ダウン入力データ対{ｘ（２）、ｘ（３）}、{ｘ（４）、ｘ（５）}、{ｘ（８）、ｘ（９）}、{ｘ（１４）、ｘ（１５）}のうち一つまたはダウン入力データ対に対応する偶数演算段階の出力データ対のうち一つが第１ダウンシングルポートメモリＤＮＳ１のポートＰＤ１を通じて同時に入力／出力される。
【００５３】
アップ入力データ対に対応する奇数演算段階の出力データ対のうち一つが第２アップシングルポートメモリＵＰＳ２のポートＰＵ２を通じて同時に入力／出力される。
【００５４】
ダウン入力データ対に対応する奇数演算段階の出力データ対のうち一つが第２ダウンシングルポートメモリＤＮＳ２のポートＰＤ２を通じて同時に入力／出力される。
【００５５】
第１バタフライ演算器２１０の第１ないし第４端子Ｔ１１〜Ｔ４１を通じてｒａｄｉｘ−２  バタフライ演算のための入力／出力データが入力／出力される。すなわち、第１及び第２端子Ｔ１１、Ｔ２１は、奇数演算段階で入力端子として使われ、偶数演算段階で出力端子として使われる。そして、第３及び４端子Ｔ３１、Ｔ４１は、偶数演算段階で入力端子として使われ、奇数演算段階で出力端子として使われる。例えば、第１演算段階で、アップ入力データ対のうち第１入力データ対のｘ（０）及びｘ（０）とバタフライ演算が行われるダウン入力データ対のうち第３入力データ対のｘ（８）が第１端子Ｔ１１及び第２端子Ｔ２１を通じてそれぞれ入力される。また、第１演算段階で、アップ入力データ対のうち第３入力データ対のｘ（１１）及びｘ（１１）とバタフライ演算が行われるダウン入力データ対のうち第１入力データ対のｘ（３）が第１端子Ｔ１１及び第２端子Ｔ２１を通じてそれぞれ入力される。第１ないし第３演算段階で、第１バタフライ演算器２１０にＦＦＴ演算に必要な回転因子（Ｗ16K、Ｋ＝０〜７の整数）が供給される。
【００５６】
第２バタフライ演算器２２０の第１ないし第４端子Ｔ１２〜Ｔ４２を通じてｒａｄｉｘ−２  バタフライ演算のための入力／出力データが入力／出力される。すなわち、第１及び第２端子Ｔ１２、Ｔ２２は、奇数演算段階で入力端子として使われ、偶数演算段階で出力端子として使われる。そして、第３及び４端子Ｔ３２、Ｔ４２は、偶数演算段階で入力端子として使われ、奇数演算段階で出力端子として使われる。例えば、第１演算段階で、アップ入力データ対のうち第１入力データ対のｘ（１）及びｘ（１）とバタフライ演算が行われるダウン入力データ対のうち第３入力データ対のｘ（９）が第１端子Ｔ１２及び第２端子Ｔ２２を通じてそれぞれ入力される。また、第１演算段階で、アップ入力データ対のうち第３入力データ対のｘ（１０）及びｘ（１０）とバタフライ演算が行われるダウン入力データ対のうち第１入力データ対のｘ（２）が第１端子Ｔ１２及び第２端子Ｔ２２を通じてそれぞれ入力される。第１ないし第３演算段階で、第２バタフライ演算器２２０にＦＦＴ演算に必要な回転因子（Ｗ16K、Ｋ＝０〜７の整数）が供給される。
【００５７】
第１及び第２スイッチ回路２３０、２４０は、４個のシングルポートメモリＵＰＳ１、ＤＮＳ１、ＵＰＳ２、ＤＮＳ２とバタフライ演算器２１０、２２０とが図５に示されたＦＦＴアルゴリズムの信号流れ（またはデータ流れ）を行うように制御する。第１及び第２スイッチ回路２３０、２４０は、本発明に係るＦＦＴプロセッサ２００全体を制御するＦＦＴコントローラ  （図示せず）により制御される。
【００５８】
第１スイッチ回路２３０の動作を第１演算段階を例えて説明する。第１アップシングルポートメモリＵＰＳ１のポートＰＵ１を通じて出力されるデータｘ（１）は、第１スイッチ回路２３０により第２バタフライ演算器２２０の第１端子Ｔ１２に伝えられ、第１ダウンシングルポートメモリＤＮＳ１のポートＰＤ１を通じて出力されるデータｘ（８）は、第１スイッチ回路２３０により第１バタフライ演算器２１０の第２端子Ｔ２１に伝えられる。そして、第１アップシングルポートメモリＵＰＳ１のポートＰＵ１を通じて出力されるデータｘ（１０）は、第１スイッチ回路２３０により第２バタフライ演算器２２０の第１端子Ｔ１２に伝えられ、第１ダウンシングルポートメモリＤＮＳ１のポートＰＤ１を通じて出力されるデータｘ（３）は、第１スイッチ回路２３０により第１バタフライ演算器２１０の第２端子Ｔ２１に伝えられる。
【００５９】
第２スイッチ回路２４０の動作も前述した第１演算段階における第１スイッチ回路２３０の動作と類似している。また、残りの第２及び第３演算段階における第１及び第２スイッチ回路２３０、２４０の動作と第１演算段階における第１及び第２スイッチ回路２３０、２４０の動作は類似している。ただし、第４演算段階で、第２スイッチ回路２４０により第２アップシングルポートメモリＵＰＳ２に保存された第３演算段階の出力データは、ポートＰＵ２を通じて第１バタフライ演算器２１０の第４端子Ｔ４１に伝えられ、第２スイッチ回路２４０により第２ダウンシングルポートメモリＤＮＳ２に保存された第３演算段階の出力データは、ポートＰＤ２を通じて第２バタフライ演算器２２０の第３端子Ｔ３２に伝えられる。そして、第４演算段階の第１スイッチ回路２３０の動作は、前述した第４演算段階の第２スイッチ回路の動作と類似している。
【００６０】
前記のように、本発明に係るＦＦＴプロセッサ２００は、相対的に少数のゲートを有するシングルポートメモリを用いてＦＦＴアルゴリズムを行うので、ＦＦＴ演算に必要なメモリサイズを減少させることができる。一方、本発明に係るＦＦＴプロセッサ２００は、ＤＩＦアルゴリズムとして実現されたＦＦＴアルゴリズムを行うと説明したが、ＤＩＴ（Ｄｅｃｉｍａｔｉｏｎ  Ｉｎ  Ｔｉｍｅ）アルゴリズムとして実現されたＦＦＴアルゴリズムを行うことも可能である。また、本発明に係るＦＦＴプロセッサ２００は、１６データポイントに対するＦＦＴ演算だけでなく８または３２データポイントに対するＦＦＴ演算も可能である。
【００６１】
図８は、図７に示された第１または第２バタフライ演算器をさらに詳細に示す図である。図８を参照すると、第１または第２バタフライ演算器２１０、２２０は、複素数加算器２１１、複素数減算器２１２、及び複素数乗算器２１３を備える。
【００６２】
複素数加算器２１１は、入力端子を通じて入力された第１入力データＩＮ１及び第２入力データＩＮ２を加算して出力端子を通じて第１出力データＯＵＴ１を出力する。複素数減算器２１２は、第１入力データＩＮ１から第２入力データＩＮ２を減算して複素数乗算器２１３に出力する。複素数乗算器２１３は、複素数減算器２１２の出力値に対応する回転因子（Ｗ16K、Ｋ＝０〜７の整数）を乗算して出力端子を通じて第２出力データＯＵＴ２を出力する。
【００６３】
以上のように、図面と明細書において最適の実施形態が開示された。ここで特定用語が使われたが、これは単に本発明を説明するための目的として使われたものであり、意味限定や特許請求の範囲に記載された本発明の範囲を制限するために使われたものではない。したがって、当業者ならば、これより多様な変形及び均等な他の実施形態の採用が可能であるという点を理解しうる。したがって、本発明の真の技術的保護範囲は特許請求の範囲によってのみ決まるべきである。
【産業上の利用可能性】
【００６４】
本発明は、有無線通信システムのＦＦＴプロセッサに好適に用いられる。
【図面の簡単な説明】
【００６５】
【図１】一般的な１６−ポイントＲａｄｉｘ−２  ＤＩＦ  ＦＦＴアルゴリズムの信号フローチャートである。
【図２】従来技術による図１のＦＦＴアルゴリズムを実現するための４個のデュアルポートメモリの配置を示す図である。
【図３】図２の４個のデュアルポートメモリを含む従来技術によるＦＦＴプロセッサを示すブロック図である。
【図４】図３に示された第１または第２バタフライ演算器をさらに詳細に示す図である。
【図５】本発明の実施例による図１のＦＦＴアルゴリズムを実現するための４個のシングルポートメモリの配置を示す図である。
【図６】図５の第１アップ及びダウンシングルポートメモリに保存される入力データ対及び入力データ対が保存されるアドレスを示す図表である。
【図７】図５の４個のシングルポートメモリを含む本発明の実施例によるＦＦＴプロセッサを示すブロック図である。
【図８】図７に示された第１または第２バタフライ演算器をさらに詳細に示す図である。
【符号の説明】
【００６６】
２００    ＦＦＴプロセッサ
ＵＰＳ１、ＵＰＳ２    第１及び第２アップシングルポートメモリ
ＤＮＳ１、ＤＮＳ２    第１及び第２ダウンシングルポートメモリ
２１０、２２０    第１及び第２バタフライ演算器２１０
２３０、２４０    第１スイッチ回路（ＳＷ１）及び第２スイッチ回路（ＳＷ２）
【図１】
2006221648.tif 000005
【図２】
2006221648.tif 000006
【図３】
2006221648.tif 000007
【図４】
2006221648.tif 000008
【図５】
2006221648.tif 000009
【図６】
2006221648.tif 000010
【図７】
2006221648.tif 000011
【図８】
2006221648.tif 000012