(57)【特許請求の範囲】
【請求項１】
メモリのポインタを進める方法であって、
前記メモリが、第１のステージがステージ０である高速フーリエ変換（FFT）のステージMの一連のN個のデータポイントを含み、前記N個のデータポイントがN/2個のAデータポイント及びN/2個のBデータポイントを含み、前記N個のデータポイントが前記メモリ内のAデータポイントの２Ｍのグループにストアされ、前記各グループが２(Log2*N)-1-M（Log2*NはLog２Nを表すものとする）のデータポイントを有し、前記各グループに２(Log2*N)-1-MのBデータポイントのグループが続き、
ａ）前記メモリの第１のAデータポイントに対応するデータポイントメモリインデックスの２進数の値にポインタインデックスApを設定するステップと、
ｂ）前記メモリの第１のBデータポイントに対応するデータポイントメモリインデックスの２進数の値にポインタインデックスBpを設定するステップと、
ｃ）第１の２進数マスクビット値R1を２(Log2*N)-1-M+１に設定するステップと、
ｄ）第２の２進数マスクビット値R2を２(Log2*N)-1-Mに設定するステップと、
ｅ）ｅ１）Apポインタインデックス値をR1に加えるステップ、ｅ２）ステップｅ１）の結果とR2との論理和をとるステップ、及びｅ３）前記Bpポインタインデックス値をステップｅ２）の結果に設定するステップとによって、Bpポインタインデックスをメモリの次のBデータポイントに対応するデータポイントメモリインデックスに進めるステップと、
ｆ）ｆ１）Apポインタインデックス値をR1に加えるステップ、ｆ２）ステップｆ１）の結果とR2のビット逆転値との論理積をとるステップと、及びｆ３）Apポインタインデックス値をステップｆ２）の結果に設定するステップとによって、Apポインタインデックスをメモリの次のAデータポイントに対応するデータポイントメモリインデックスに進めるステップとが含まれることを特徴とする方法。
【請求項２】
ステップｅ）及びｆ）を２回以上繰り返すステップを更に含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記Apポインタインデックスが、前記メモリの最後の前記Aデータポイントに対応するデータポイントメモリインデックスに等しくなり、前記Bpポインタインデックスが前記メモリの最後の前記Bデータポイントに対応するデータポイントメモリインデックスに等しくなるまで、ステップｅ）及びｆ）を繰り返すステップを更に含むことを特徴とする請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的にはデジタル信号プロセシング（DSP）に関連し、特に高速フーリエ変換（FFT）の演算のサポートにおける改良された「インプレイス」メモリポインタ管理の方法及び装置に関する。
【０００２】
【従来の技術】
デジタル信号プロセッサ（DSP）は、高速フーリエ変換（FFT）、デジタルフィルタリング、画像処理、及び言語認識などのデジタル信号処理を最適化するように設計された特殊目的のコンピュータである。DSPアプリケーションは、リアルタイムオペレーション、高い割り込み率、及び集中的な数値演算が主な特徴である。更に、DSPアプリケーションは、メモリアクセス動作が頻繁になる傾向があり、大量のデータの入出力が必要である。
【０００３】
FFTデータは一連のＮ個のデータポイントからなり、各データポイントは実数値と虚数値の２つのデータ値を含む。データポイントはN/2個の“A”データポイント及びN/2個の“B”データポイントのグループに分けられ、図１に示される各FFTバタフライ演算は、様々な係数（WR,WI）を用いて１つのAデータポイント（AR,AI）及び１つのBデータポイント（BR,BI）について演算し、FFT演算の次の段階のA及びBデータポイントとなる（XR,XI）及び（YR,YI）が得られる。各FFTバタフライ演算のA及びBのデータポイントとしてのデータポイント選択は、FFTの各ステージによって異なる。
【０００４】
以下に示す表１（FFT（A,B）グループ）は、０から１５までの数字が付された一連の１６個のデータポイントを有するFFTの各ステージに必要な（A,B）データポイントグループを示す。
【０００５】
【表１】
0004159761.tif 000002
【０００６】
以下に示す表２（FFT A／B配置）は、１６個のデータポイントFFTの各ステージにおけるそれぞれのFFTデータポイントのA／B配置を例示する。
【０００７】
【表２】
0004159761.tif 000003
【０００８】
FFTの演算を実行するDSPアーキテクチャでは、データは幾つかのステージでメモリで読み書きされる。DSPアーキテクチャの中には、入力データ及び出力データのそれぞれに異なったメモリ空間を利用するものもある。このようなメモリ構造では、１つのFFTステージの結果が、次の段階のA及びBデータポイントの選択の順に書き込むことができ、A及びBデータポイントメモリアドレスへポインタを増分することができる。以下に示す表３（A/Bソートオーダー）は、１６個のデータポイントFFTの各ステージにおいてポインタが最適化された論理FFTデータポイント順序を例示する。
【０００９】
【表３】
0004159761.tif 000004
【００１０】
FFTに必要なメモリの量を減らすために、FFT入力データメモリスペースがFFT演算の結果で上書きされる「インプレイス」メモリ管理方式が開発され、それによってFFTの各ステージにおける結果をソートする追加のメモリスペースが必要なくなる。残念ながら、このような構造のメモリでは、ステージ０に続く各ステージに、表３に示されるA/Bソートオーダーではなく、表２に示されるデータポイントソートオーダーでメモリにデータポイントがストアされるため、A及びBデータポイントメモリアドレスへポインタが前進しない。メモリアドレスルックアップテーブル或いはハードコードメモリアドレスを用いることができるが、そうすると「インプレイス」FFTのメモリ効率が低下する。
【００１１】
【発明が解決しようとする課題】
本発明は、高速フーリエ変換（FFT）の演算のサポートにおける改良された「インプレイス」メモリポインタ管理の方法及び装置を提供すること。
【００１２】
【課題を解決するための手段】
従って、本発明の好適な実施例に基づいてメモリのポインタを進める方法を提供する。このメモリは、第１のステージがステージ０である高速フーリエ変換（FFT）のステージMの一連のN個のデータポイントを含み、このN個のデータポイントはN/2個のAデータポイント及びN/2個のBデータポイントを含み、N個のデータポイントがメモリ内のAデータポイントの２Ｍのグループにストアされ、それぞれのグループは２(Log2*N)-1-M（Log2*NはLog２Nを表すものとする）のデータポイントを有し、それぞれのグループには２(Log2*N)-1-MのBデータポイントのグループが続く。また、その方法は、ａ）メモリの第１のAデータポイントに対応するデータポイントメモリインデックスの２進数の値にポインタインデックスApを設定するステップと、ｂ）メモリの第１のBデータポイントに対応するデータポイントメモリインデックスの２進数の値にポインタインデックスBpを設定するステップと、ｃ）第１の２進数マスクビット値R1を２(Log2*N)-1-M+１に設定するステップと、ｄ）第２の２進数マスクビット値R2を２(Log2*N)-1-Mに設定するステップと、ｅ）ｅ１）Apポインタインデックス値をR1に加えるステップ、ｅ２）ステップｅ１）の結果とR2との論理和をとるステップ、及びｅ３）Bpポインタインデックス値をステップｅ２）の結果に設定するステップとによって、Bpポインタインデックスをメモリの次のBデータポイントに対応するデータポイントメモリインデックスに進めるステップと、ｆ）ｆ１）Apポインタインデックス値をR1に加えるステップ、ｆ２）ステップｆ１）の結果とR2のビット逆転値との論理積をとるステップ、及びｆ３）Apポインタインデックス値をステップｆ２）の結果に設定するステップによって、Apポインタインデックスをメモリの次のAデータポイントに対応するデータポイントメモリインデックスに進めるステップとが含まれる。
【００１３】
本発明は、本発明の好適な実施例に基づいて、ステップｅ）及びｆ）を２回以上繰り返すステップ更に含む。
【００１４】
この方法は更に、本発明の好適な実施例に基づいて、Apポインタインデックスがメモリの最後のAデータポイントに対応するデータポイントメモリインデックスに等しくなり、Bpポインタインデックスがメモリの最後のBデータポイントに対応するデータポイントメモリインデックスに等しくなるまで、ステップｅ）及びｆ）を繰り返すステップを含む。
【００１５】
本明細書において、用語「データポイント」は実数及び虚数の２つのデータ値の対を指す。
【００１６】
また、本明細書における用語「データポイントメモリインデックス」は、１つのメモリスペース内において１つのデータポイントを別のデータポイントから識別するために必要な最小数のアドレスビットを指す。
【００１７】
【発明の実施の形態】
本発明の好適な実施例に基づいて動作する高速フーリエ変換（FFT）演算の改良されたインプレイスメモリポインタ管理の方法を例示する単純化されたフローチャート図２について説明する。また、本発明の好適な実施例に基づいて作成され動作する、図２に示された方法を理解するのに役立つ単純化された表である図３を説明する。図２の方法において、０からN−1の数字が付された一連のN個のデータポイントが、デジタル信号プロセッサのメモリにストアされる（ステップ１００）。メモリ内のデータポイントの配列は、図３から読み取ることが可能である。０から１５の数字が付された１６個のFFTデータポイントがストアされたメモリ１０の論理表現が図３に示されている。１６個のデータポイントが示されているが、メモリ１０は任意の数Nのデータポイントをストアしてもよい。
【００１８】
データポイントメモリインデックス１２は、各データポイントを１つのメモリスペース内において１つのデータポイントをユニークに識別するために必要な最小数のアドレス指定ビットになるように決定される（ステップ１１０）。従って、FFTが１つのメモリに連続してストアされた１６個のデータポイントを含む場合は、４ビットが必要になる。それぞれのデータポイントは通常、２つの連続するメモリアドレスにストアされた実数値及び虚数値の両方を含むため、任意のデータポイントの開始アドレスは、データポイントに対応するデータポイントメモリインデックスを２倍して、FFTデータポイントストアが開始される基本メモリアドレス１４にその積を加えることによって決定される。従って、例えば図３において、データポイントメモリインデックスが0101であるデータポイント５の開始メモリアドレスは、基本メモリアドレスFB902834に1010を加え、FB902834＋0A＝FB90283Eと求めることができる。
【００１９】
表２に示されているように、インプレイスFFTメモリ管理の特徴は、第１のステージがステージ０であるFFTの任意のステージMの任意の一連のN個のデータポイントにおいて、N/2個のAデータポイント及びN/2個のBデータポイントからなるN個のデータポイントが、Aデータポイントが前記メモリ内の２Ｍのグループにストアされるように配列される。このとき、各グループは２(Log2*N)-1-Mのデータポイントを有し、この各グループには２(Log2*N)-1-MのＢデータポイントグループが続く。従って、例えば１６個のデータポイントFFTのステージ２では、それぞれが２つのデータポイント（２(Log2*N)-1-M）の４つのAデータポイントグループ（２Ｍ）が存在し、それぞれのAデータポイントグループにはそれぞれが２つのデータポイントのBデータポイントグループが続く。
【００２０】
図２の方法では、FFTステージの開始時に、ポインタ及びマスクビットの初期化で始める。ポインタインデックスApを、メモリ１０の第１のAデータポイントに対応するデータポイントメモリインデックスの２進値に設定する。同様にポインタインデックスBpを、メモリ１０の第１のBデータポイントに対応するデータポイントメモリインデックスの２進値に等しくなるように設定する（ステップ１２０）。２進数マスクビット値R1を２(Log2*N)-1-M＋１に設定し、２進数マスクビット値R2を２(Log2*N)-1-Mに設定する（ステップ１３０）。マスクビットR1及びR2は、データポイントメモリインデックスとして同じビット数が好ましい。ステージMの第１のデータポイントグループ（A,B）は、ポインタインデックスAp及びBpをそれぞれメモリ１０のデータポイント０のメモリアドレスに加えて決定することができる。
【００２１】
ポインタインデックスBpは、以下に示すようにメモリ１０の次のBデータポイントに対応するデータポイントメモリインデックスに進めることができる。
【００２２】
１ａ）Apポインタインデックス値をR1に加える（ステップ１４０）、
２ａ）ステップ１ａ）の結果とR2の論理和をとる（ステップ１５０）、
３ａ）Bpポインタインデックス値をステップ２ａ）の結果に設定する（ステップ１６０）。
【００２３】
ポインタインデックスApは、以下に示すようにメモリ１０の次のAデータポイントに対応するデータポイントメモリインデックスに進めることができる。
【００２４】
１ｂ）Apポインタインデックス値をR1に加える（ステップ１７０）、
２ｂ）ステップ１ｂ）の結果とR2のビット逆転値の論理積をとる（ステップ１８０）、
３ｂ）Apポインタインデックス値をステップ２ｂ）の結果に設定する（ステップ１６０）。
【００２５】
次にポインタインデックスAp及びBpをそれぞれ、メモリ１０のそれぞれの次のA及びBデータポイントのデータポイントメモリインデックスに進める。
【００２６】
図２を用いて上述した論理演算は、本発明の好適な実施例に基づいて作成され動作する図２の方法を理解するために役立つ単純化された論理図である図４を参照すると良い。
【００２７】
図２の典型的な演算の方法は、以下の例を用いて説明する。上記表１を参照すると、FFTステージ２の第１の（A,B）データポイントグループは、データポイント０と２からなる。従って、図３のデータポイント０及び２に示されるデータポイントメモリインデックス値に従って、ポインタインデックスApをデータポイントメモリインデックス0000に設定し、ポインタインデックスBpを0010に設定する。２進数マスクビット値R1を、２(Log2*N)-1-M＋1(=24-1-2+1=21+1=0011)に設定し、２進数マスクビット値R2を２(Log2*N)-1-M (=0010) に設定する。
【００２８】
図３に示されるように、FFTステージ２の次の（A,B）データポイントグループは、それぞれがデータポイントメモリインデックス0001及び0011であるデータポイント１及び３からなる。ポインタインデックスBpは以下に示すように0010から0011に増分される。
【００２９】
１ａ）Apポインタインデックス値をR1に加えるステップ（=0000+0011=0011）、
２ａ）ステップ１ａ）の結果とR2の論理和をとるステップ(=0011 OR 0010=0011)、
３ａ）Bpポインタインデックス値をステップ２ａ）の結果に設定するステップ(=0011)。
【００３０】
ポインタインデックスApは以下に示すようにポイント0000から0001に増分される。
【００３１】
１ｂ）Apポインタインデックス値をR1に加えるステップ(=0000+0011=0011)、
２ｂ）ステップ１ｂの結果とR2のビット逆転値との論理積をとるステップ(=0011 AND 1101=0001)、
３ｂ）Apポインタインデックス値をステップ２ｂ）の結果に設定するステップ(=0001)。
【００３２】
図３に示されるように、FFTステージ２の次の（A,B）データポイントグループは、それぞれが0100及び0110のデータポイントメモリインデックスであるデータポイント４及び６からなる。ポインタインデックスBpは以下に示すように0011から0010に増分される。
【００３３】
１ａ）Apポインタインデックス値をR1に加えるステップ（=0001+0011=0100）、
２ａ）ステップ１ａ）の結果とR2の論理和をとるステップ(=0100 OR 0010=0110)、
３ａ）Bpポインタインデックス値をステップ２ａ）の結果に設定するステップ(=0110)。
【００３４】
ポインタインデックスApは以下に示すようにポイント0001から0100に増分される。
【００３５】
１ｂ）Apポインタインデックス値をR1に加えるステップ(=0001+0011=0100)、
２ｂ）ステップ１ｂ）の結果とR2のビット逆転値との論理積をとるステップ(=0100 AND 1101=0100)、
３ｂ）Apポインタインデックス値をステップ２ｂ）の結果に設定するステップ(=0100)。
【００３６】
従って、上記表２に示されているように、FFTの各ステージのA及びBのデータポイントの位置に用いられた方法で、図２の方法を用いてポインタインデックスAp及びBpを、メモリ１０のA及びBのデータポイントのデータポイントメモリインデックスにそれぞれ進めることが可能である。
【００３７】
本発明の別の好適な実施例に基づいて形成され動作する、２つの異なったメモリスペースに用いられるFFT入力データメモリの単純化された表を例示する図５を説明する。０から１５の数字が付された１６個のFFTデータポイントをストアしている第１のメモリスペース１６及び第２のメモリスペース１８の論理表現が図５に示されている。１６個のデータポイントは示されているが、メモリ１６及び１８は、任意の数Ｎのデータポイントを集合的にストアできるという点を理解されたい。２つの異なったメモリスペースが、８個のデータポイントをそれぞれストアするように用いられるため、それぞれのメモリスペース内において１つのデータポイントから別のデータポイントを認識するには、わずか３ビットのメモリインデックス２０で足りる。図２の方法にわずかな変更を加えて用いることができる。その変更点とは、ポインタインデックスAp及びBpをそれぞれメモリ１６及び１８の両方の第１のデータポイントのメモリアドレスに加えることによって、２つのデータポイントグループ（A,B）がポインタインデックスAp及びBpの所定値に決定されることである。従って、上記表１を参照すると、FFTステージ２のデータポイントグループ（0,2）及び（8,10）は、図５に示されるデータポイント0,2,8及び10のデータポイントメモリインデックス値に従い、ポインタインデックスApが000、ポインタインデックスBpが010になる。
【００３８】
ここに記載した装置及び方法は、特定のハードウェア及びソフトウェアを用いずに説明した。実施例の数を減らすことで過度の実験を行わないで従来の技術を用いて本発明を具現可能とし、当業者が市販のハードウェア及びソフトウェアを容易に利用できるように本発明及び装置を詳細に説明した。
【００３９】
本発明は２、３の特定の実施例を用いて説明したが、その説明は本発明の例示目的であり、記載した本発明の実施例を制限するものではないことを理解されたい。特にここには示さないが、同業者には様々な改変が可能であることは明らかであるが、これらの改変は本発明の範囲及び意図に含まれるものである。
【００４０】
【発明の効果】
本発明は、高速フーリエ変換（FFT）の演算のサポートにおける改良された「インプレイス」メモリポインタ管理の方法及び装置が提供できる。
【図面の簡単な説明】
【図１】高速フーリエ変換（FFT）バタフライ演算を簡略化した模式図を例示する。
【図２】本発明の好適な実施例に基づいて動作する、FFT演算の改良されたインプレイスメモリポインタ管理の方法を簡略化したフローチャートを例示する。
【図３】本発明の好適な実施例に基づいて形成され動作する、FFT入力データメモリの簡略化した表を例示する。
【図４】本発明の好適な実施例に基づいて形成され動作する、図２の方法を理解するのに役立つ簡略化した論理図である。
【図５】本発明の別の好適な実施例に基づいて形成され動作する、２つの異なったメモリスペースを用いるFFT入力データメモリの簡略化した表を例示する。
【符号の説明】
１０、１６  メモリ
１２、１８  データポイントメモリインデックス
１４、２０  基本メモリアドレス
【図１】
0004159761.tif 000005
【図２】
0004159761.tif 000006
【図３】
0004159761.tif 000007
【図４】
0004159761.tif 000008
【図５】
0004159761.tif 000009