信号処理方法ならびにデータ処理の方法および装置
信号処理方法、データ処理方法および装置が開示される。時間領域から周波数領域への信号処理方法は、時間領域データを前処理する段階と、前処理されたデータを回転因子
を使用して前回転する段階と、前回転データに対してN/4点の離散フーリエ変換(DFT)を実行する段階と、DFTによって変換されたデータを回転因子
を使用して後回転し、周波数領域データを取得する段階とを含む。周波数領域から時間領域への信号処理方法は、周波数領域データにひねりを施す段階と、ひねりを施したデータを回転因子
を使用して前回転する段階と、前回転データに対してN/4点のDFTを実行する段階と、DFTによって変換されたデータを回転因子
を使用して後回転する段階と、後回転データを後処理して、時間領域データを取得する段階とを含む。本発明は信号処理の効率を高める。
を使用して前回転する段階と、前回転データに対してN/4点の離散フーリエ変換(DFT)を実行する段階と、DFTによって変換されたデータを回転因子
を使用して後回転し、周波数領域データを取得する段階とを含む。周波数領域から時間領域への信号処理方法は、周波数領域データにひねりを施す段階と、ひねりを施したデータを回転因子
を使用して前回転する段階と、前回転データに対してN/4点のDFTを実行する段階と、DFTによって変換されたデータを回転因子
を使用して後回転する段階と、後回転データを後処理して、時間領域データを取得する段階とを含む。本発明は信号処理の効率を高める。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、参照により本明細書に組み込まれている、2009年6月24日に中国特許庁に出願した中国特許出願第200910150720.5号、名称「Signal Processing Method and Data Processing Method and Apparatus」の優先権を主張するものである。
【０００２】
本発明は、デジタル信号処理技術に関するものであり、特に、信号処理方法ならびにデータ処理の方法および装置に関するものである。
【背景技術】
【０００３】
フーリエ変換、離散コサイン変換(DCT)、および離散サイン変換(DST)などの直交変換は、デジタル信号処理、特に、スペクトル分析、画像符号化、および音声符号化において広く使用されている。
【０００４】
DCTは、空間変換であり、DCTベースの符号化システムが適切な圧縮性能を備えるように強いエネルギー集中特性を有する。
【０００５】
修正離散コサイン変換(MDCT)は、DCTベースの改良された変換である。MDCTは、連続するブロック間のブロッキング効果を回避するように設計されている。これは、広帯域および超広帯域デジタルオーディオ符号化において重要な役割を果たす。
【０００６】
変換公式に従って順MDCT(forward MDCT)および逆MDCT(inverse MDCT)を直接適用すると、計算複雑度が高まる。特に、点の数が多い場合には、計算複雑度が高くなるためMDCTをリアルタイムで実行することはできない。MDCTはリアルタイム通信および特にオーディオ符号化において広く応用されるため、高速MDCT法の実現が急務となっている。高速MDCTの実現のために従来技術においてよく使用される方法は、高速フーリエ変換(FFT)に基づくものである。
【０００７】
N点の広く使用されているFFTベースの高速MDCTとして、N/2点FFTに基づく高速MDCTおよびN/4点FFTに基づく高速MDCTが挙げられる。
【０００８】
従来技術の研究および実践において、以下の弱点が見つかっている。
【０００９】
N/4点FFTに基づく高速MDCTアルゴリズムを適用する場合、前回転処理(pre-rotation processing)および後回転処理(post-rotation processing)は、少なくともN/4点のコサイン値およびN/4点のサイン値、合わせてN/2個の値を記憶する必要がする。前回転ステップと後回転ステップが非対称的である場合、N個の値を記憶する必要がある。Nが大きい場合、追加ストレージの容量が大きくなり、したがって、多くのストレージリソースが消費され、変換効率が影響を受ける。
【００１０】
互いに素な因数に基づく高速フーリエ変換アルゴリズムが採用された場合、多数のアドレッシング演算が必要になり、このアルゴリズムは、データ列のシーケンシャルアクセスを考慮しない。変換を通して得られたデータは、最終的な出力データを得るために再配列する必要がある。したがって、計算量がさらに多くなる。
【発明の概要】
【課題を解決するための手段】
【００１１】
本発明の実施形態は、信号処理の効率の改善を支援するための信号処理方法ならびにデータ処理の方法および装置を実現する。
【００１２】
時間領域から周波数領域への信号処理方法は、
時間領域データを前処理するステップと、
前処理されたデータを、回転因子
【００１３】
【数１】
【００１４】
を使用することによって前回転するステップと、
前回転データに対してN/4点の離散フーリエ変換(DFT)を実行するステップと、
DFTによって変換されたデータを、回転因子
【００１５】
【数２】
【００１６】
を使用することによって後回転し、周波数領域データを取得するステップとを含み、
式中、aおよびbは定数であり、Nは時間領域データの長さであり、
【００１７】
【数３】
【００１８】
【数４】
【００１９】
【数５】
【００２０】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００２１】
周波数領域から時間領域への信号処理方法は、
周波数領域データにひねりを施す(twiddling)ステップと、
ひねりを施したデータを、回転因子
【００２２】
【数６】
【００２３】
を使用することによって前回転するステップと、
前回転データに対してN/4点のDFTを実行するステップと、
DFTによって変換されたデータを、回転因子
【００２４】
【数７】
【００２５】
を使用することによって後回転するステップと、
後回転データを後処理して、時間領域データを取得するステップとを含み、
式中、cおよびdは定数であり、Nは周波数領域データの倍長であり、
【００２６】
【数８】
【００２７】
【数９】
【００２８】
【数１０】
【００２９】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００３０】
データ処理方法は、
アドレステーブルに基づきQ回にわたってデータに対しP点DFTを実行するステップと、
アドレステーブルに基づきP回にわたってQ回にわたってP点DFTを実行した後に得られたデータに対してQ点DFTを実行するステップとを含む。
【００３１】
時間領域から周波数領域への信号処理装置は、
時間領域データを前処理するように適合された前処理ユニットと、
回転因子
【００３２】
【数１１】
【００３３】
を使用することによって、前処理ユニットにより得られたデータを前回転するように適合された第1の前回転ユニットと、
第1の前回転ユニットによって処理されたデータに対してN/4点のDFTを実行するように適合された第1のフーリエ変換ユニットと、
回転因子
【００３４】
【数１２】
【００３５】
を使用することによって第1のフーリエ変換ユニットにより変換されたデータを後回転して周波数領域データを取得するように適合された第1の後回転ユニットとを備え、式中、
【００３６】
【数１３】
【００３７】
【数１４】
【００３８】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００３９】
周波数領域から時間領域への信号処理装置は、
周波数領域データにひねりを施すように適合されたひねり処理ユニット(twiddling unit)と、
回転因子
【００４０】
【数１５】
【００４１】
を使用することによって、ひねり処理ユニットにより得られたデータを前回転するように適合された第2の前回転ユニットと、
第2の前回転ユニットによって処理されたデータに対してN/4点のDFTを実行するように適合された第2のフーリエ変換ユニットと、
回転因子
【００４２】
【数１６】
【００４３】
を使用することによって、第2のフーリエ変換ユニットにより得られたデータを後回転するように適合された第3の後回転ユニットと、
第3の後回転ユニットによって処理されたデータを後処理して時間領域データを取得するように適合された後処理ユニットとを備え、式中、
【００４４】
【数１７】
【００４５】
【数１８】
【００４６】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００４７】
データ処理装置は、
アドレステーブルを作成するか、または格納するように適合されたアドレステーブルユニットと、
アドレステーブルユニットによって作成されるか、または格納されているアドレステーブルに基づきQ回にわたってデータに対しP点DFTを実行するように適合された第5の変換ユニットと、
アドレステーブルユニットによって作成されるか、または格納されているアドレステーブルに基づきP回にわたって第5の変換ユニットによって変換されたデータに対しQ点DFTを実行するように適合された第6の変換ユニットとを備える。
【００４８】
上記の技術的解決策では、本発明の実施形態において提供される信号処理方法によって採用されている回転因子は、定数と
【００４９】
【数１９】
【００５０】
との積である。因子
【００５１】
【数２０】
【００５２】
は対称であるため、前回転および後回転を完了させるためにN/4点のデータテーブルを記憶するだけでよい。従来技術に比べて、本発明の実施形態において提供される信号処理方法は、記憶容量を低減し、ストレージリソースの消費を減らし、変換効率を高める。さらに、本発明の実施形態の信号処理方法では後回転を実行するときに正規化因子が不要になるため、関係する処理ステップなしで済ませられ、したがって変換効率がさらに改善される。
【００５３】
本発明または従来技術の技術的な解決策をわかりやすく説明するために、本発明または従来技術の実施形態の説明において必要な図面について簡単に説明する。後述の図面は、本発明の一部の実施形態のみであることは明らかである。当業者であれば、創造的な作業を行うことなくこれらの図面に基づいて他の図面を得ることができる。
【図面の簡単な説明】
【００５４】
【図１】本発明の第1の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。
【図２】本発明の一実施形態におけるFFTの演算に対しアドレステーブルを採用するデータ処理方法の流れ図である。
【図３】本発明の第2の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。
【図４】本発明の第3の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。
【図５】本発明の第4の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。
【図６】本発明の第5の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。
【図７】本発明の第6の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。
【図８】本発明の一実施形態における時間領域から周波数領域への信号処理装置の構造を示す図である。
【図９】本発明の一実施形態における周波数領域から時間領域への信号処理装置の構造を示す図である。
【図１０】本発明の一実施形態におけるデータ処理装置の構造を示す図である。
【発明を実施するための形態】
【００５５】
本発明の技術的解決策は、以下で付属の図面を参照しつつ詳細に説明される。これらの実施形態は例示的なものにすぎず、本発明は、そのような実施形態に限定されないことは明らかである。本発明の実施形態に基づいて当業者が構成する他の実施形態も、本発明の保護の範囲内に入る。
【００５６】
本発明の実施形態は、信号処理の効率の改善を支援するための信号処理方法ならびにデータ処理の方法および装置を実現する。
【００５７】
従来技術では、N/4点のFFTに基づく高速MDCTを実現するために、最初にN点のデータに窓関数を掛け、ひねりを施し、前回転して、N点のMDCTをN/4点のFFTに変える。FFT演算で得られたデータを後回転して、最終的なMDCT係数を得る。
【００５８】
MDCTの定義は
【００５９】
【数２１】
【００６０】
であり、式中、Aは正規化因子であり、定数である。
【００６１】
MDCTの定義によれば、
【００６２】
【数２２】
【００６３】
【数２３】
【００６４】
が得られるが、式中、
【００６５】
【数２４】
【００６６】
である。
【００６７】
これら2つの式を組み合わせて、
【００６８】
【数２５】
【００６９】
を得ることができる。
【００７０】
次いで、N/4点FFTに基づく順MDCTは以下のステップを含む。
【００７１】
1.窓関数を掛ける:
yn=hnxn n=0,...,N-1
hnは、完全な再構成条件を満たす窓関数であるが、必ずしも対称窓ではない。つまり、解析および合成では、解析窓および合成窓が一緒になって完全な再構成を行える限り、異なる窓を使用することができる。xnは入力データである。通常、x0-N/2-1はキャッシュされている前のフレームのデータであり、xN/2-N-1は現在のフレームのデータである。
【００７２】
2.ひねりを施す:
un=(Z2n+jzN/2-1-2n) n=0,...,N/4-1
式中、
【００７３】
【数２６】
【００７４】
または
【００７５】
【数２７】
【００７６】
である。
【００７７】
3.回転因子
【００７８】
【数２８】
【００７９】
を使用することによってunを前回転する。
【００８０】
4.回転データに対してN/4点FFTを実行する。
【００８１】
5.回転因子
【００８２】
【数２９】
【００８３】
および正規化因子Aを使用することによって変換データを後回転する。
【００８４】
6.後回転を通じて得られる複素数の実部はX2kであり、これはMDCTスペクトルの奇数周波数を表し、虚部は-Xn/2-1-2kであり、これはMDCTスペクトルの偶数周波数を表す。
【００８５】
回転因子
【００８６】
【数３０】
【００８７】
は、
【００８８】
【数３１】
【００８９】
に展開することができる。
【００９０】
回転因子
【００９１】
【数３２】
【００９２】
および
【００９３】
【数３３】
【００９４】
は、前回転および後回転の処理に必要であるため、少なくともN/4点のコサイン値およびN/4点のサイン値、合わせてN/2個の値を記憶する必要がある。前回転ステップと後回転ステップが非対称的である場合、N個の値を記憶する必要がある。Nが大きい場合、追加ストレージの容量が大きくなり、したがって、多くのストレージリソースが消費され、変換効率が影響を受ける。
【００９５】
本発明の一実施形態において提供される時間領域から周波数領域への信号処理方法は、以下のステップを含む。
【００９６】
1.時間領域データを前処理する。
【００９７】
2.前処理されたデータを、回転因子
【００９８】
【数３４】
【００９９】
を使用することによって前回転する。
【０１００】
3.前回転データに対してN/4点のDFTを実行する。
【０１０１】
4.DFTの後のデータを、回転因子
【０１０２】
【数３５】
【０１０３】
を使用することによって後回転し、周波数領域データを取得する。
式中、aおよびbは定数であり、Nは時間領域データの長さであり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０１０４】
【数３６】
【０１０５】
である。
【０１０６】
前回転の前のデータに対するすべての処理は、前処理として説明できる。この実施形態では、例えば、前処理は、窓関数を掛けてひねりを施すステップまたはひねりを施すステップのみとしてよい。
【０１０７】
本発明の一実施形態において提供される周波数領域から時間領域への信号処理方法は、以下のステップを含む。
【０１０８】
1.周波数領域データにひねりを施す。
【０１０９】
2.ひねりを施されたデータを、回転因子
【０１１０】
【数３７】
【０１１１】
を使用することによって前回転する。
【０１１２】
3.前回転データに対してN/4点のDFTを実行する。
【０１１３】
4.DFTの後のデータを、回転因子
【０１１４】
【数３８】
【０１１５】
を使用することによって後回転する。
【０１１６】
5.後回転データを後処理して、時間領域データを取得する。
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０１１７】
【数３９】
【０１１８】
である。
【０１１９】
後回転の後のデータに対するすべての処理は、後処理として説明できる。後処理の内容は、対応する時間領域から周波数領域への信号処理方法における前処理の内容に依存する。この実施形態では、例えば、前処理が窓関数を掛けてひねりを施すステップである場合、後処理も窓関数を掛けてひねりを施すステップであり、前処理がひねりを施すステップだけである場合、後処理もひねりを施すステップだけである。
【０１２０】
時間領域から周波数領域への信号処理は、順変換とも称され、周波数領域から時間領域への信号処理は、逆変換とも称されうる。順変換と逆変換においてa×b×c×d=4/Nである場合、順変換の出力データを逆変換の入力データとして使用すると、逆変換の結果が順変換の前のデータを復元できるため、完全な再構成を行うことができる。実際、完全な再構成は必ずしも必要でない。
【０１２１】
本発明の一実施形態において提供される信号処理方法によって採用される回転因子における
【０１２２】
【数４０】
【０１２３】
は、
【０１２４】
【数４１】
【０１２５】
に展開することができ、
式中、
【０１２６】
【数４２】
【０１２７】
【数４３】
【０１２８】
である。
【０１２９】
式
【０１３０】
【数４４】
【０１３１】
から、n+(N/4-1-n)=N/4-1であることがわかり、n=0,...,N/4-1およびk=0,...,N/4-1に対して、(n=0のときの)
【０１３２】
【数４５】
【０１３３】
の第1の値は、(n=N/4-1のときの)
【０１３４】
【数４６】
【０１３５】
の最後の値に等しい。(n=1のときの)
【０１３６】
【数４７】
【０１３７】
の第2の値は、(n=N/4-2のときの)
【０１３８】
【数４８】
【０１３９】
の最後から2番目の値に等しく、以下同様である。
【０１４０】
したがって、
【０１４１】
【数４９】
【０１４２】
は、対称的である。前回転および後回転を完了させるために、
【０１４３】
【数５０】
【０１４４】
または
【０１４５】
【数５１】
【０１４６】
のN/4点データテーブルを記憶するだけでよい。
【０１４７】
従来のMDCTにおいて、MDCTのスペクトル係数を得るために、回転因子
【０１４８】
【数５２】
【０１４９】
および
【０１５０】
【数５３】
【０１５１】
を使用する必要があり、また
【０１５２】
【数５４】
【０１５３】
および
【０１５４】
【数５５】
【０１５５】
は対称的でない。したがって、前回転および後回転において少なくともN/4点のコサイン値およびN/4点のサイン値を記憶する必要がある。本発明の実施形態において提供される信号処理方法によって採用されている回転因子は、定数と
【０１５６】
【数５６】
【０１５７】
との積である。因子
【０１５８】
【数５７】
【０１５９】
は対称であるため、前回転および後回転を完了させるためにN/4点のデータテーブルを記憶するだけでよい。従来技術に比べて、本発明の実施形態の信号処理方法は、記憶容量を著しく低減し、ストレージリソースの消費を減らし、変換効率を高める。さらに、本発明の実施形態の信号処理方法では正規化因子が不要になるため、関係する処理ステップなしで済ませられ、したがって変換効率がさらに改善される。
【０１６０】
本発明の信号処理方法の例示的な実施形態について説明する。図1は、本発明の第1の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。この方法は、以下のステップを含む。
【０１６１】
101.時間領域データを前処理する。
【０１６２】
このステップでは、前処理は、窓関数を掛け、ひねりを施すステップを含む。実際には、他の前処理手段も使用される場合がある。
【０１６３】
時間領域データxnは入力データであると仮定する。通常、x0-N/2-1はキャッシュされている前のフレームデータであり、xN/2-N-1は現在のフレームデータである。Nは時間領域データの長さであり、この実施形態では、1280としてよい。最初にデータに窓関数を掛ける。
yn=hnxn n=0,...,N-1、
hnは、完全な再構成条件を満たす窓関数であり、解析窓関数と称されうる。逆変換で使用される窓関数は、合成窓関数と称されうる。解析窓関数は、解析窓関数と合成窓関数とが完全な再構成を一緒に行える限り合成窓関数と異なっていてもよい。窓関数を掛けたデータはひねりを施され、ひねりを施されたデータunは
un=(z2n+jzN/2-1-2n) n=0,...,N/4-1
を満たすが、
式中、
【０１６４】
【数５８】
【０１６５】
または
【０１６６】
【数５９】
【０１６７】
である。
【０１６８】
102.前処理されたデータを、回転因子
【０１６９】
【数６０】
【０１７０】
を使用することによって前回転する。
【０１７１】
ひねりを施されたデータunは、回転因子
【０１７２】
【数６１】
【０１７３】
n=0,...,N/4-1を使用することによって前回転され、式中、
【０１７４】
【数６２】
【０１７５】
であり、aは定数である。
【０１７６】
回転の後得られるデータは、
【０１７７】
【数６３】
【０１７８】
である。
【０１７９】
この実施形態では、定数は
【０１８０】
【数６４】
【０１８１】
とすることができる。回転因子中の
【０１８２】
【数６５】
【０１８３】
は、
【０１８４】
【数６６】
【０１８５】
の形式で表すことができ、これは
【０１８６】
【数６７】
【０１８７】
および
【０１８８】
【数６８】
【０１８９】
満たすので、N/4点のサインもしくはコサインデータテーブルのみが、この方法の態様において必要である。この実施形態では、N/4点のみのデータテーブルが記憶される。データテーブル内の値は、
【０１９０】
【数６９】
【０１９１】
n=0,...,319で表される。
【０１９２】
103.前回転データに対してN/4点のDFTを実行する。
【０１９３】
このステップでは、N/4点のふつうのDFTが使用されるか、または他のN/4点FFTが使用されうる。
【０１９４】
さらに、ステップ103では、アドレステーブルに基づくFFTは、M=N/4=P×Qのときに使用することができ、PおよびQは正整数であり、PおよびQは互いに素な数であり、アドレステーブルの長さはMである。
【０１９５】
図2は、本発明の一実施形態におけるFFTに対しアドレステーブルを採用するデータ処理方法の流れ図である。この方法は、以下のステップを含む。
【０１９６】
1031.アドレステーブルIを作成する。アドレステーブルIは
I=<K1×n1+K2×n2>M n1=0,...,P-1
n2=0,...,Q-1
を満たす。
【０１９７】
K1およびK2は、<K1K2>M=0を満たす互いに素な正整数であるが、ただし、K1K2=Zおよび<Z>Mは法Mに関するZの剰余を意味し、ZをMで割った余りである。このステップは、より早い段階に実行されうるか、またはステップ101または102との順次的関係を持たない。つまり、アドレステーブルIは、予め計算され格納されうる。データの順序関係を決定するために、アドレステーブルIに格納されているアドレスは0,1,...,M-1と横断して、入力データとの1対1マッピングを形成する必要がある。アドレステーブルIが1対1マッピングの条件を満たす場合、以下の3つの条件が満たされる必要がある。
【０１９８】
(1)K1はQの正整数倍であり、および/またはK2はPの正整数倍である。
【０１９９】
(2)K1およびPは、互いに素な数である。
【０２００】
(3)K2およびQは、互いに素な数である。
【０２０１】
P=64、Q=5、K1=65、K2=256、およびM=N/4=320と仮定すると、アドレステーブルIは、
I=<65n1+256n2>320
で表すことができ、
式中、n1=0,...,63およびn2=0,...,4である。
【０２０２】
アドレステーブルIは、I[n2×n1]の一次元配列またはI[n1][n2]の二次元配列などの配列の形式で1つのテーブルに格納することができる。
【０２０３】
アドレステーブルIがM=320点のアドレステーブルであり、K1=65、K2=256、Q=5、P=64、およびQ×P=5×64点と仮定すると、アドレステーブルIがI[n2×n1]の一次元配列として格納される場合、
Idx[Q×P]=
{0,65,130,195,260,5,70,135,200,265,10,75,140,205,270,15,80,145,210,275,20,85,150,215,280,25,90,155,220,285,30,95,160,225,290,35,100,165,230,295,40,105,170,235,300,45,110,175,240,305,50,115,180,245,310,55,120,185,250,315,60,125,190,255,
256,1,66,131,196,261,6,71,136,201,266,11,76,141,206,271,16,81,146,211,276,21,86,151,216,281,26,91,156,221,286,31,96,161,226,291,36,101,166,231,296,41,106,171,236,301,46,111,176,241,306,51,116,181,246,311,56,121,186,251,316,61,126,191,
192,257,2,67,132,197,262,7,72,137,202,267,12,77,142,207,272,17,82,147,212,277,22,87,152,217,282,27,92,157,222,287,32,97,162,227,292,37,102,167,232,297,42,107,172,237,302,47,112,177,242,307,52,117,182,247,312,57,122,187,252,317,62,127,
128,193,258,3,68,133,198,263,8,73,138,203,268,13,78,143,208,273,18,83,148,213,278,23,88,153,218,283,28,93,158,223,288,33,98,163,228,293,38,103,168,233,298,43,108,173,238,303,48,113,178,243,308,53,118,183,248,313,58,123,188,253,318,63,
64,129,194,259,4,69,134,199,264,9,74,139,204,269,14,79,144,209,274,19,84,149,214,279,24,89,154,219,284,29,94,159,224,289,34,99,164,229,294,39,104,169,234,299,44,109,174,239,304,49,114,179,244,309,54,119,184,249,314,59,124,189,254,319};
となる。
【０２０４】
アドレステーブルIがI[n1][n2]の二次元配列として格納される場合、
Idx[Q][P]=
{{0,65,130,195,260,5,70,135,200,265,10,75,140,205,270,15,80,145,210,275,20,85,150,215,280,25,90,155,220,285,30,95,160,225,290,35,100,165,230,295,40,105,170,235,300,45,110,175,240,305,50,115,180,245,310,55,120,185,250,315,60,125,190,255},
{256,1,66,131,196,261,6,71,136,201,266,11,76,141,206,271,16,81,146,211,276,21,86,151,216,281,26,91,156,221,286,31,96,161,226,291,36,101,166,231,296,41,106,171,236,301,46,111,176,241,306,51,116,181,246,311,56,121,186,251,316,61,126,191},
{192,257,2,67,132,197,262,7,72,137,202,267,12,77,142,207,272,17,82,147,212,277,22,87,152,217,282,27,92,157,222,287,32,97,162,227,292,37,102,167,232,297,42,107,172,237,302,47,112,177,242,307,52,117,182,247,312,57,122,187,252,317,62,127},
{128,193,258,3,68,133,198,263,8,73,138,203,268,13,78,143,208,273,18,83,148,213,278,23,88,153,218,283,28,93,158,223,288,33,98,163,228,293,38,103,168,233,298,43,108,173,238,303,48,113,178,243,308,53,118,183,248,313,58,123,188,253,318,63},
{64,129,194,259,4,69,134,199,264,9,74,139,204,269,14,79,144,209,274,19,84,149,214,279,24,89,154,219,284,29,94,159,224,289,34,99,164,229,294,39,104,169,234,299,44,109,174,239,304,49,114,179,244,309, 54,119,184,249,314,59,124,189,254,319}};
となる。
【０２０５】
1032.アドレステーブルIに基づきQ回にわたってP点DFTを実行する。
【０２０６】
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=iおよびn1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のP点DFTの結果をxのステップの循環シフトで適用する必要がある。
【０２０７】
ここでは、xは、法Pに関する
【０２０８】
【数７０】
【０２０９】
の巡回剰余の逆数であり、
【０２１０】
【数７１】
【０２１１】
を満たす。
【０２１２】
アドレステーブルIがI[n2×n1]の一次元配列の形式で格納される場合、アドレステーブルIに基づくQ回にわたるP点DFTは、
DFT_P(z(I+iP))x i=0,...,Q-1;
で表すことができる。
【０２１３】
それぞれのP点DFTの入力データは、I+iPから始まるP個の連続インデックスに対応するデータである。それぞれのP点DFTの結果は、xのステップの循環シフトで適用される。
【０２１４】
この実施形態では、64点DFTは、5回にわたって実行される。i番目(i=0,...,4)の64点DFTの入力データは、アドレステーブル配列I[64i]から始まる64個の連続するアドレスインデックスに関連付けられているデータである(回転後のデータ)。i番目の64点DFTの結果は、5のステップの循環シフトで適用される。例えば、ベクトルZ=[z0 z1 z2 z3 z4]上の2のステップの循環シフトの結果は、Z=[z0 z2 z4 z1 z3]である。それに加えて、計算の効率をさらに高めるために、DFTの代わりにFFTを使用するとよい。
【０２１５】
1033.アドレステーブルIに基づきP回にわたってQ点DFTを実行する。
【０２１６】
i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=i、n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のQ点DFTの結果をyのステップの循環シフトで適用する必要がある。
【０２１７】
ここでは、yは、法Qに関する
【０２１８】
【数７２】
【０２１９】
の巡回剰余の逆数であり、
【０２２０】
【数７３】
【０２２１】
を満たす。
【０２２２】
アドレステーブルIがI[n2×n1]の一次元配列の形式で格納される場合、アドレステーブルIに基づくP回にわたるQ点DFTは、
DFT_Q(z(I+i))y i=0,...,P-1;
で表すことができる。
【０２２３】
Q点DFTの入力データは、Pのステップでそれぞれ分離されているI+iから始まるQ個のインデックスに対応するデータである。それぞれのQ点DFTの結果は、yのステップの循環シフトで適用される。
【０２２４】
この実施形態では、5点DFTは、64回にわたって実行される。i番目(i=0,...,63)の5点DFTの入力データは、アドレステーブル配列I[i]から始まる5個の連続するアドレスインデックスに関連付けられているデータであり(回転後のデータ)、それぞれ64のステップで分離されている。i番目の5点DFTは、4のステップの循環シフトで適用される。
【０２２５】
従来技術では、互いに素な因子に基づく大半のDFTでは、データ列の順次アクセスを考慮しない。変換を通して得られたデータは、最終的な出力データを得るために再配列する必要がある。したがって、計算量がさらに多くなる。この実施形態では、DFTにアドレステーブルが使用され、アドレッシングはアドレステーブルに基づき、入力データはこのアドレステーブル内の関連付けられているアドレスに従って読み込まれ、出力データはアドレステーブル内の関連付けられているアドレスに従って格納される。変換の後に得られたデータの列は、特別な再配列なしで使用可能である。したがって、計算の複雑度は低減され、計算効率が高まる。
【０２２６】
104.DFTの後のデータを、回転因子
【０２２７】
【数７４】
【０２２８】
を使用することによって後回転し、周波数領域データを取得する。
【０２２９】
変換されたデータは、回転因子
【０２３０】
【数７５】
【０２３１】
k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０２３２】
【数７６】
【０２３３】
であり、bは定数である。この実施形態では、定数は
【０２３４】
【数７７】
【０２３５】
とすることができる。回転因子中の
【０２３６】
【数７８】
【０２３７】
は、
【０２３８】
【数７９】
【０２３９】
の形式で表すことができ、b=aであるため、ステップ102で使用されるN/4点データテーブルは、このステップの態様において再利用することができる。
【０２４０】
周波数領域データ、さらには最終的なスペクトルは、Xk、k=0,...,N/2-1であり、
【０２４１】
【数８０】
【０２４２】
【数８１】
【０２４３】
で表すことができる。
【０２４４】
本発明の第1の実施形態による時間領域から周波数領域への信号処理方法に従って、周波数領域から時間領域への信号処理方法が本発明の第2の実施形態において提供される。順変換が、本発明の第1の実施形態において提供される時間領域から周波数領域への信号処理方法を使用することによって実行される場合、本発明の第2の実施形態において提供される周波数領域から時間領域への信号処理方法を使用することによって実行されうる。
【０２４５】
図3は、本発明の第2の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。この方法は、以下のステップを含む。
【０２４６】
301.周波数領域データにひねりを施す。
【０２４７】
特に、周波数領域データXk、k=0,...,N/2-1にひねりを施す。この実施形態では、N=1280である。
【０２４８】
ひねりを施した後に得られる中間変数は、(X2k+jXN/2-1-2k)、k=0,...,N/4-1である。
【０２４９】
302.ひねりを施されたデータを、回転因子
【０２５０】
【数８２】
【０２５１】
を使用することによって前回転する。
【０２５２】
ひねりを施されたデータは、回転因子
【０２５３】
【数８３】
【０２５４】
k=0,...,N/4-1を使用することによって前回転されるが、式中、
【０２５５】
【数８４】
【０２５６】
であり、cは定数である。
【０２５７】
この実施形態では、定数は
【０２５８】
【数８５】
【０２５９】
とすることができ、したがって、ステップ102および104で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０２６０】
303.前回転データに対してN/4点のDFTを実行する。
【０２６１】
このステップでは、N/4点のふつうのDFTが使用されるか、または他のN/4点FFTが使用されうる。
【０２６２】
このステップでは、図2に示されている320点FFTが実行されうる。
【０２６３】
304.DFTの後のデータを、回転因子
【０２６４】
【数８６】
【０２６５】
を使用することによって後回転する。
【０２６６】
変換されたデータは、回転因子
【０２６７】
【数８７】
【０２６８】
k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０２６９】
【数８８】
【０２７０】
であり、dは定数である。
【０２７１】
この実施形態では、定数は
【０２７２】
【数８９】
【０２７３】
とすることができ、したがって、ステップ102および104で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０２７４】
上記の処理の後得られるデータynは、
【０２７５】
【数９０】
【０２７６】
である。
【０２７７】
305.後回転データを後処理して、時間領域データを取得する。
【０２７８】
このステップでは、後処理は、窓関数を掛け、ひねりを施すステップを含む。実際には、他の後処理手段も使用される場合がある。
【０２７９】
窓関数を掛け、ひねりを施した後、時間領域データ
【０２８０】
【数９１】
【０２８１】
が得られ、
【０２８２】
【数９２】
【０２８３】
であるが、式中、
【０２８４】
【数９３】
【０２８５】
、n=0,...,N/8-1であり、gnは合成窓であり、これは完全な再構成条件を解析窓hn、つまり、hngn+hn+N/2gn+N/2=1、n=0,...,N-N/2-1と一緒に満たす。mnは前のフレームのバッファリングされたデータであり、mnの更新は、
【０２８６】
【数９４】
【０２８７】
を満たす。
【０２８８】
本発明の第1の実施形態において提供される時間領域から周波数領域への信号処理方法および本発明の第2の実施形態において提供される周波数領域から時間領域への信号処理方法が使用される場合、順変換および逆変換中の定数a、b、c、およびdはa×b×c×d=4/Nを満たせば、逆変換の結果は完全な再構成に対し使用可能である。実際、完全な再構成は必ずしも必要でない。
【０２８９】
例えば、
【０２９０】
【数９５】
【０２９１】
を選択することができる。そこで、順変換および逆変換は、前回転および後回転を完了させるために
【０２９２】
【数９６】
【０２９３】
および
【０２９４】
【数９７】
【０２９５】
においてN/4点データテーブルを記憶するだけでよい。定数a、b、c、およびdが等しくない場合、前回転および後回転を完了するために、実用的な条件に従って適切なデータテーブルを格納する必要がある。
【０２９６】
本発明の一実施形態において提供される別の時間領域から周波数領域への信号処理方法は、以下のステップを含む。
【０２９７】
1.時間領域データを前処理する。
【０２９８】
2.前処理されたデータを、回転因子
【０２９９】
【数９８】
【０３００】
を使用することによって前回転する。
【０３０１】
3.前回転データに対してN/4点のDFTを実行する。
【０３０２】
4.DFTの後のデータを、回転因子
【０３０３】
【数９９】
【０３０４】
および正規化因子Aを使用することによって後回転し、周波数領域データを取得するが、
式中、aおよびbは定数であり、Nは時間領域データの長さであり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０３０５】
【数１００】
【０３０６】
である。
【０３０７】
前回転の前のデータに対するすべての処理は、前処理として説明できる。この実施形態では、例えば、前処理は、窓関数を掛けてひねりを施すステップまたはひねりを施すステップのみとしてよい。
【０３０８】
本発明の一実施形態において提供される別の周波数領域から時間領域への信号処理方法は、以下のステップを含む。
【０３０９】
1.周波数領域データにひねりを施す。
【０３１０】
2.ひねりを施されたデータを、回転因子
【０３１１】
【数１０１】
【０３１２】
を使用することによって前回転する。
【０３１３】
3.前回転データに対してN/4点のDFTを実行する。
【０３１４】
4.DFTの後のデータを、回転因子
【０３１５】
【数１０２】
【０３１６】
および正規化因子Bを使用することによって後回転する。
【０３１７】
5.後回転データを後処理して、時間領域データを取得するが、
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０３１８】
【数１０３】
【０３１９】
である。
【０３２０】
後回転の後のデータに対するすべての処理は、後処理として説明できる。後処理の内容は、対応する時間領域から周波数領域への信号処理方法における前処理の内容に依存する。この実施形態では、例えば、前処理が窓関数を掛けてひねりを施すステップである場合、後処理も窓関数を掛けてひねりを施すステップであり、前処理がひねりを施すステップである場合、後処理もひねりを施すステップである。
【０３２１】
時間領域から周波数領域への信号処理は、順変換とも称され、周波数領域から時間領域への信号処理は、逆変換とも称される。順変換と逆変換においてa×b×c×d=4/Nである場合、順変換の出力データを逆変換の入力データとして使用すると、逆変換の結果が順変換の前のデータを復元できるため、完全な再構成を行うことができる。例えば、a=b=c=d=1、A・B=4/N、または
【０３２２】
【数１０４】
【０３２３】
、A=B=1を選択することができる。実際、完全な再構成は必ずしも必要でない。
【０３２４】
この実施形態において提供される信号処理方法によって採用される回転因子における
【０３２５】
【数１０５】
【０３２６】
は、
【０３２７】
【数１０６】
【０３２８】
に展開することができ、
式中、
【０３２９】
【数１０７】
【０３３０】
【数１０８】
【０３３１】
である。
【０３３２】
したがって、
【０３３３】
【数１０９】
【０３３４】
は、対称的である。前回転および後回転を完了させるために、
【０３３５】
【数１１０】
【０３３６】
または
【０３３７】
【数１１１】
【０３３８】
のN/4点データテーブルを記憶するだけでよい。
【０３３９】
従来のMDCTにおいて、MDCTのスペクトル係数を得るために、回転因子
【０３４０】
【数１１２】
【０３４１】
を使用する必要があり、また
【０３４２】
【数１１３】
【０３４３】
は対称的でない。したがって、前回転および後回転において少なくともN/4点のコサイン値およびN/4点のサイン値を記憶する必要がある。本発明の実施形態において提供される信号処理方法によって採用されている回転因子は、定数と
【０３４４】
【数１１４】
【０３４５】
との積である。因子
【０３４６】
【数１１５】
【０３４７】
は対称であるため、前回転および後回転を完了させるためにN/4点のデータテーブルを記憶するだけでよい。従来技術に比べて、この実施形態の信号処理方法は、記憶容量および格納の複雑さを低減し、ストレージリソースの消費を減らし、変換効率を高める。
【０３４８】
本発明の信号処理方法の例示的な実施形態について説明する。
【０３４９】
広帯域オーディオコーデックのサンプリング周波数は16kHzであり、処理されるフレームサイズは20msであると仮定する。1つのフレームは、320個のサンプリング点を含む。本発明の一実施形態において提供される時間領域から周波数領域への信号処理方法を使用して、エンコーダで順変換を実行する。順変換の入力データは、xnであり、x0-N/2-1は前のフレームのキャッシュされている320点データであり、xN/2-N-1は現在のフレームの320点データであり、変換セクション長Nは、点640個分である。図4は、本発明の第3の実施形態において提供される信号処理方法の流れ図である。この方法は、以下を含む。
【０３５０】
401.時間領域入力データを前処理する。
【０３５１】
このステップでは、前処理は、窓関数を掛け、ひねりを施すステップを含む。
【０３５２】
xnが640点時間領域入力データであり、hnが完全な再構成条件を満たす640点窓関数である場合、窓関数を掛けたデータynは、
yn=hnxn n=0,...,N-1、
を満たし、
hnは、完全な再構成条件を満たす窓関数であり、これは解析窓関数として説明することができる。
【０３５３】
窓関数を掛けたデータはひねりを施され、得られたデータunは
【０３５４】
【数１１６】
【０３５５】
を満たすが、
式中、
【０３５６】
【数１１７】
【０３５７】
または
【０３５８】
【数１１８】
【０３５９】
である。
【０３６０】
402.前処理されたデータを、回転因子
【０３６１】
【数１１９】
【０３６２】
を使用することによって前回転する。
【０３６３】
ひねりを施されたデータunは、回転因子
【０３６４】
【数１２０】
【０３６５】
n=0,...,N/4-1を使用することによって前回転され、式中、
【０３６６】
【数１２１】
【０３６７】
であり、aは定数である。
【０３６８】
この実施形態では、a=1であり、回転因子は、
【０３６９】
【数１２２】
【０３７０】
によって表すことができる。
【０３７１】
この式は、
【０３７２】
【数１２３】
【０３７３】
および
【０３７４】
【数１２４】
【０３７５】
を満たす。
【０３７６】
特定の態様では、
【０３７７】
【数１２５】
【０３７８】
または
【０３７９】
【数１２６】
【０３８０】
のN/4点データテーブルを記憶するだけでよい。この実施形態では、N/4点のサインテーブルが記憶される。サインテーブル内の値は、
【０３８１】
【数１２７】
【０３８２】
、n=0,...,159で表される。
【０３８３】
403.前回転データに対してN/4個の入力のDFTを実行する。
【０３８４】
このステップでは、M=N/4=160点のふつうのDFTが使用されるか、またはM=N/4=160点のFFTが使用されうる。
【０３８５】
404.DFTの後のデータを、回転因子
【０３８６】
【数１２８】
【０３８７】
および正規化因子Aを使用することによって後回転し、周波数領域出力データを取得する。
【０３８８】
変換されたデータは、回転因子
【０３８９】
【数１２９】
【０３９０】
、k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０３９１】
【数１３０】
【０３９２】
であり、bは定数である。この実施形態では、b=1であり、回転因子は、
【０３９３】
【数１３１】
【０３９４】
によって表すことができる。
【０３９５】
b=aなので、ステップ402で使用されるN/4点データテーブルは、このステップの態様において使用することができる。
【０３９６】
最終データXk、k=0,...,N/2-1が得られ、これらは
【０３９７】
【数１３２】
【０３９８】
【数１３３】
【０３９９】
であり、式中、Aは正規化因子であり、定数である。
【０４００】
この実施形態では、定数Aは
【０４０１】
【数１３４】
【０４０２】
とすることができる。
【０４０３】
本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法に従って、周波数領域から時間領域への信号処理方法が本発明の第4の実施形態において提供される。本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法を使用して変換を実行する場合、本発明の第4の実施形態において提供される周波数領域から時間領域への信号処理方法を使用して対応する逆変換を実行することができる。
【０４０４】
図5は、本発明の第4の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。この方法は、以下を含む。
【０４０５】
501.周波数領域入力データにひねりを施す。
【０４０６】
この実施形態では、データXk、k=0,...,N/2-1にひねりを施して、中間変数
【０４０７】
【数１３５】
【０４０８】
、k=0,...,N/4-1を得るが、式中、N=640である。
【０４０９】
502.ひねりを施されたデータを、回転因子
【０４１０】
【数１３６】
【０４１１】
を使用することによって前回転する。
【０４１２】
ひねりを施されたデータは、回転因子
【０４１３】
【数１３７】
【０４１４】
、k=0,...,N/4-1を使用することによって前回転され、式中、
【０４１５】
【数１３８】
【０４１６】
であり、cは定数である。この実施形態ではc=1であり、本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ402および404で使用されるN/4点データテーブルも再利用することができる。
【０４１７】
503.前回転データに対してN/4点のDFTを実行する。
【０４１８】
回転データに対してM=N/4=160点のDFTを実行する。このステップでは、160点のふつうのDFTが使用されるか、または他の160点FFTが使用されうる。
【０４１９】
504.DFTの後のデータを、回転因子
【０４２０】
【数１３９】
【０４２１】
および正規化因子Bを使用することによって後回転する。
【０４２２】
変換されたデータは、回転因子
【０４２３】
【数１４０】
【０４２４】
、k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０４２５】
【数１４１】
【０４２６】
であり、dは定数である。上記の処理の後得られるデータynは、
【０４２７】
【数１４２】
【０４２８】
である。
【０４２９】
Bは、正規化因子であり、定数である。この実施形態では、定数Bは
【０４３０】
【数１４３】
【０４３１】
とすることができる。この実施形態ではd=1であり、本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ402および404で使用されるN/4点データテーブルも再利用することができる。
【０４３２】
505.後回転データを後処理して、時間領域出力データを取得する。
【０４３３】
このステップでは、後処理は、窓関数を掛け、ひねりを施すステップを含む。実際には、他の後処理手段も使用される場合がある。
【０４３４】
窓関数を掛けて、ひねりを施した後、出力データ
【０４３５】
【数１４４】
【０４３６】
、n=0,...,N/2-1が得られ、これは、
【０４３７】
【数１４５】
【０４３８】
を満たし、式中、
【０４３９】
【数１４６】
【０４４０】
n=0,...,N/8-1であり、gnは、解析窓hnと一緒に完全な再構成条件を満たす、合成窓である、つまり、
hngn+hn+N/2gn+N/2=1 n=0,...,N-N/2-1
であり、mnは前のフレームのバッファリングされたデータであり、mnの更新は、
【０４４１】
【数１４７】
【０４４２】
を満たす。
【０４４３】
完全な再構成条件を満たすために、順変換、逆変換、または順/逆変換に特定の正規化因子を掛けるとよい。この実施形態では、順変換および逆変換に同じ正規化因子を掛ける。適宜、順変換または逆変換のみに特定の正規化因子を掛けるか、または順変換および逆変換に異なる正規化因子を掛ける。完全な再構成は、a×b×c×d×A×B=4/Nである限り完成させることができる。
【０４４４】
さらに、正規化因子が使用される場合、FFTを実行するためにアドレステーブルも使用することができる。超広帯域オーディオコーデックにおいて、超広帯域オーディオエンコーダのサンプリング周波数は32kHzであり、処理されるフレームサイズは20msであると仮定する。つまり、1つのフレームは、640個のサンプリング点を含む。データに対して、順変換が実行される。xnが順変換の入力データである場合、x0-N/2-1は前のフレームの640点データであり、xN/2-N-1は現在のフレームの640点データである。
【０４４５】
図6は、本発明の第5の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。この方法は、以下のステップを含む。
【０４４６】
601.時間領域データを前処理する。
【０４４７】
前処理は、窓関数を掛け、ひねりを施すステップを含む。
【０４４８】
xnが1280点時間領域入力データであり、hnが完全な再構成条件を満たす1280点窓関数である場合、窓関数を掛けたデータynは、
yn=hnxn n=0,...,N-1,
を満たす。
【０４４９】
窓関数を掛けたデータはひねりを施され、得られたデータunは
un=(z2n+ jzN/2-1-2n) n=0,...,N/4-1
を満たすが、
式中、
【０４５０】
【数１４８】
【０４５１】
または
【０４５２】
【数１４９】
【０４５３】
である。
【０４５４】
窓関数は、このステップの解析窓関数hnおよび逆変換で使用される合成窓関数gnが式
hngn+hn+N/2gn+N/2=1 n=0,...,N-N/2-1
を満たすときに完全な再構成条件を満たす。
【０４５５】
602.前処理されたデータを、回転因子
【０４５６】
【数１５０】
【０４５７】
を使用することによって前回転する。
【０４５８】
ひねりを施されたデータunは、回転因子
【０４５９】
【数１５１】
【０４６０】
を使用することによって前回転される。回転の後得られるデータは、
【０４６１】
【数１５２】
【０４６２】
n=0,...,N/4-1であり、式中、
【０４６３】
【数１５３】
【０４６４】
であり、aは定数である。計算の複雑度をさらに低くするために、正規化因子を回転因子と直接組み合わせるとよい。この実施形態では、定数aは、回転因子において
【０４６５】
【数１５４】
【０４６６】
とすることができ、これは
【０４６７】
【数１５５】
【０４６８】
の形式で表すことができ、また
【０４６９】
【数１５６】
【０４７０】
【数１５７】
【０４７１】
である。
【０４７２】
したがって、N/4点のデータテーブルを記憶するだけでよい。この実施形態では、N/4点のデータテーブルが記憶され、データテーブル内の値は、
【０４７３】
【数１５８】
【０４７４】
、n=0,...,319で表される。
【０４７５】
603.アドレステーブルに基づくFFTを使用して前回転データに対してN/4点のDFTを実行する。
【０４７６】
この実施形態では、PおよびQを互いに素な正整数とするM=N/4=P×Q点のFFTが実行される。FFTは、以下のステップを含む。
【０４７７】
i.P=64、Q=5とし、PおよびQは互いに素であり、M=N/4=P×Q=320を満たすものとし、式
I=<K1xn1+K2xn2>M n1=0,...,P-1
n2=0,...,Q-1
を満たす、アドレステーブルIを作成する。
【０４７８】
K1およびK2は、<K1K2>M=0を満たす互いに素な正整数であるが、ただし、K1K2=Zおよび<Z>Mは法Mに関するZの剰余を意味し、ZをMで割った余りである。
【０４７９】
データの順序関係を決定するために、アドレステーブルIに格納されているアドレスは0,1,...,M-1と横断して、入力データとの1対1マッピングを形成する必要がある。アドレステーブルIが1対1マッピングの条件を満たす場合、以下の3つの条件が満たされる必要がある。
【０４８０】
(1)K1はQの正整数倍であり、および/またはK2はPの正整数倍である。
【０４８１】
(2)K1およびPは、互いに素な数である。
【０４８２】
(3)K2およびQは、互いに素な数である。
【０４８３】
この実施形態では、K1=65、K2=256であり、アドレステーブルIは、
I=<65n1 + 256n2>320
によって表すことができ、
式中、n1=0,...,63およびn2=0,...,4である。
【０４８４】
アドレステーブルIは、予め計算され格納されうる。このステップは、ステップ601および602との順序関係を持たない。実際、アドレステーブルIは、テーブルに格納することができる。この実施形態では、テーブルは、n2×n3の一次元配列として格納される。
【０４８５】
ii.アドレステーブルIに基づきQ回にわたってP点DFTを実行する。
DFT_P(z(I+iP))x i=0,...,Q-1
【０４８６】
それぞれのP点DFTの入力データは、I+iPから始まるP個の連続インデックスに対応するデータである。それぞれのP点DFTは、xのステップの循環シフトで適用される。ここで、xは、法Pに関する
【０４８７】
【数１５９】
【０４８８】
の巡回剰余の逆数であり、
【０４８９】
【数１６０】
【０４９０】
を満たす。この実施形態では、64点DFTは、5回にわたって実行される。i番目(i=0,...,4)の64点DFTの入力データは、アドレステーブル配列I[64i]から始まる64個の連続するアドレスインデックスに関連付けられているデータである(回転後のデータ)。i番目の64点DFTは、5のステップの循環シフトで適用される。例えば、ベクトルZ=[z0 z1 z2 z3 z4]上の2のステップの循環シフトの結果は、Z=[z0 z2 z4 z1 z3]である。それに加えて、計算の効率をさらに高めるために、DFTの代わりにFFTを使用するとよい。
【０４９１】
iii.アドレステーブルIに基づきP回にわたってQ点DFTを実行する。
DFT_Q(z(I+i))y i=0,...,P-1
【０４９２】
Q点DFTの入力データは、Pのステップでそれぞれ分離されているテーブルI内のI+iから始まるQ個のインデックスに対応するデータである。それぞれのQ点DFTの結果は、yのステップの循環シフトで適用される。ここで、yは、法Qに関する
【０４９３】
【数１６１】
【０４９４】
の巡回剰余の逆数であり、
【０４９５】
【数１６２】
【０４９６】
を満たす。この実施形態では、5点DFTは、64回にわたって実行される。i番目(i=0,...,63)の5点DFTの入力データは、アドレステーブル配列I[i]から始まる64個の点の間隔で5つのアドレスインデックスに関連付けられているデータである(回転後のデータ)。i番目の5点DFTは、4のステップの循環シフトで適用される。
【０４９７】
604.DFTの後のデータを、回転因子
【０４９８】
【数１６３】
【０４９９】
および正規化因子Aを使用することによって後回転し、周波数領域データを取得する。
【０５００】
変換されたデータは、回転因子
【０５０１】
【数１６４】
【０５０２】
、k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０５０３】
【数１６５】
【０５０４】
であり、bは定数である。この実施形態では、定数bは
【０５０５】
【数１６６】
【０５０６】
とすることができる。bが
【０５０７】
【数１６７】
【０５０８】
である場合、回転因子中の
【０５０９】
【数１６８】
【０５１０】
は、
【０５１１】
【数１６９】
【０５１２】
の形式で表すことができ、bの値はステップ602のaに等しいので、ステップ602で格納されるN/4点のデータテーブルも、このステップにおいて再利用することができる。
【０５１３】
出力データ、さらには最終的なスペクトルは、Xk、k=0,...,N/2-1であり、
【０５１４】
【数１７０】
【０５１５】
【数１７１】
【０５１６】
で表すことができ、
式中、Bは正規化因子であり、定数である。
【０５１７】
本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法に従って、周波数領域から時間領域への信号処理方法が本発明の第6の実施形態において提供される。本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法を使用して変換を実行する場合、本発明の第6の実施形態において提供される周波数領域から時間領域への信号処理方法を使用して対応する逆変換を実行することができる。
【０５１８】
図7は、本発明の第6の実施形態における周波数領域から時間領域への信号処理方法の流れ図であり、Xk、k=0,...,N/2-1は、逆変換の入力データである。この方法は、以下のステップを含む。
【０５１９】
701.周波数領域データにひねりを施す。
【０５２０】
特に、入力データXk、k=0,...,N/2-1にはひねりが施される。
【０５２１】
ひねりを施した後に得られる中間変数は、(X2k+jXN/2-1-2k)、k=0,...,N/4-1である。
【０５２２】
702.ひねりを施されたデータを、回転因子
【０５２３】
【数１７２】
【０５２４】
、k=0,...,N/4-1を使用することによって前回転する。
【０５２５】
式
【０５２６】
【数１７３】
【０５２７】
が成り立ち、cは定数である。
【０５２８】
この実施形態では、
【０５２９】
【数１７４】
【０５３０】
であり、またcはaまたはbに等しい。したがって、本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ602および604で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０５３１】
703.アドレステーブルに基づくFFTを使用して前回転データに対してN/4点のDFTを実行する。
【０５３２】
M=N/4=P×Qで、PおよびQが互いに素である場合、本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ603のデータ処理方法を使用してこのステップを実行することができる。
【０５３３】
704.変換の後のデータを、回転因子
【０５３４】
【数１７５】
【０５３５】
および正規化因子Bを使用することによって後回転する。
【０５３６】
変換されたデータは、回転因子
【０５３７】
【数１７６】
【０５３８】
、n=0,...,N/4-1を使用することによって後回転されるが、式中、
【０５３９】
【数１７７】
【０５４０】
であり、dは定数である。上記の処理の後得られるデータynは、
【０５４１】
【数１７８】
【０５４２】
である。
【０５４３】
Bは、正規化因子であり、定数である。
【０５４４】
この実施形態では、
【０５４５】
【数１７９】
【０５４６】
であり、またdはa、b、またはcに等しい。したがって、本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ602および604で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０５４７】
705.後回転データに窓関数を掛けてひねりを施し、時間領域データを取得する。
【０５４８】
窓関数を掛けて、ひねりを施した後、出力データ
【０５４９】
【数１８０】
【０５５０】
が得られ、これは、
【０５５１】
【数１８１】
【０５５２】
であり、
式中、
【０５５３】
【数１８２】
【０５５４】
n=0,...,N/4-1であり、gnは、解析窓hnと一緒に完全な再構成条件を満たす、合成窓である、つまり、hngn+hn+N/2gn+N/2=1 n=0,...,N-N/2-1である。mnは前のフレームのバッファリングされたデータであり、mnの更新は、
【０５５５】
【数１８３】
【０５５６】
を満たす。
【０５５７】
従来技術では、互いに素な因子に基づく大半のDFTでは、データ列の順次アクセスを考慮しない。変換を通して得られたデータは、最終的な出力データを得るために再配列する必要がある。したがって、計算量が増大する。本発明の実施形態では、FFTにアドレステーブルが使用され、アドレッシングはアドレステーブルに基づき、入力データはこのアドレステーブル内の関連付けられているアドレスに従って読み込まれ、出力データはアドレステーブル内の関連付けられているアドレスに従って格納される。したがって、変換の後に得られたデータの列は、特別な再配列なしで使用可能である。
【０５５８】
本発明の一実施形態において提供されるデータ処理方法は、以下のステップを含む。
【０５５９】
1.アドレステーブルを作成する。
【０５６０】
2.アドレステーブルに基づき入力データに対してQ回にわたってP点DFTを実行する。
【０５６１】
3.アドレステーブルに基づきQ回にわたってP点DFTを実行した後に得られたデータに対してP回にわたってQ点DFTを実行する。
【０５６２】
PおよびQは、互いに素な正整数であり、Mは、アドレステーブルの長さであり、M=P×Qであり、アドレステーブルに格納されているアドレスは、0,1,...,M-1と横断して、入力データとの1対1マッピングを形成する。
【０５６３】
実際、アドレステーブルは、複数のアプローチで得ることができる。この実施形態では、アドレステーブルは、式<K1×n1+K2×n2>Mを使用することによって得られる。
【０５６４】
アドレステーブルI=<K1xn1+K2xn2>M、n1=0,...,P-1、n2=0,...,Q-1であり、K1およびK2は、<K1K2>M=0を満たす互いに素な正整数である。<Z>Mは法Mに関するZの剰余を意味する。
【０５６５】
アドレステーブルが1対1マッピングの条件を満たす場合、以下の3つの条件が満たされる必要がある。
【０５６６】
(1)K1はQの正整数倍であり、および/またはK2はPの正整数倍である。
【０５６７】
(2)K1およびPは、互いに素な数である。
【０５６８】
(3)K2およびQは、互いに素な数である。
【０５６９】
この実施形態のデータ処理方法は、M=P×Qとし、PおよびQを互いに素な正整数としてFFTに適用可能である。P=64、Q=5とし、PおよびQが互いに素である320点FFTを例にとり、この実施形態において提供されるデータ処理方法の流れ図を図2に示した。この方法は、以下のステップを含む。
【０５７０】
1031.アドレステーブルIを作成する。
【０５７１】
アドレステーブルIは
I=<K1×n1+K2×n2>M n1=0,...,P-1
n2=0,...,Q-1
を満たす。
【０５７２】
K1およびK2は、<K1K2>M=0を満たす互いに素な正整数である。<Z>Mは法Mに関するZの剰余を意味する。
【０５７３】
この実施形態では、K1=5、K1=64であり、アドレステーブルIは、
I=<5n1+64n2>320
で表すことができ、式中、n1=0,...,63およびn2=0,...,4である。
【０５７４】
アドレステーブルIは、予め計算され格納されうる。実際、アドレステーブルIは、テーブルに格納することができる。この実施形態では、テーブルは、I[n1][n2]の二次元配列として格納される。
【０５７５】
1032.アドレステーブルIに従って入力データに対してQ回にわたってP点DFTを実行する。
【０５７６】
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=i、n1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のP点DFTの結果をxのステップの循環シフトで適用する。
【０５７７】
ここでは、xは、法Pに関する
【０５７８】
【数１８４】
【０５７９】
の巡回剰余の逆数であり、
【０５８０】
【数１８５】
【０５８１】
を満たす。
【０５８２】
例えば、アドレステーブルIがI[n1][n2]の二次元配列の形式で格納される場合、i番目のP点DFTの入力データは、アドレステーブルI[n1][i]、n1=0,...,P-1に格納されているP個のアドレスインデックスに関連付けられているデータである。それぞれのP点DFTの結果は、xのステップの循環シフトで適用される。この実施形態では、K1=5、P=64、およびQ=5、x=13だからである。
【０５８３】
1033.アドレステーブルIに従って変換データに対してP回にわたってQ点DFTを実行する。
【０５８４】
i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=i、n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のQ点DFTの結果をyのステップの循環シフトで適用する。
【０５８５】
ここでは、yは、法Qに関する
【０５８６】
【数１８６】
【０５８７】
の巡回剰余の逆数であり、
【０５８８】
【数１８７】
【０５８９】
を満たす。
【０５９０】
例えば、アドレステーブルIがI[n1][n2]の二次元配列の形式で格納される場合、i番目のQ点DFTの入力データは、アドレステーブルI[n1][n2]、n2=0,...,Q-1に格納されているQ個のアドレスインデックスに関連付けられているデータである。それぞれのQ点DFTの結果は、yのステップの循環シフトで適用される。この実施形態では、K2=64、P=64、およびQ=5、x=4だからである。
【０５９１】
本発明の実施形態において提供されるデータ処理方法では、DFTが実行されるときに、アドレステーブルがアドレッシングに使用されるので、入力データはアドレステーブル内の関連付けられているアドレスに従って読み込まれ、出力データはアドレステーブル内の関連付けられているアドレスに従って格納される。変換データは、使用可能な列になっており、逆変換の際に特別な再配列は不要である。したがって、計算におけるアドレッシングコストは低減され、計算効率が増大する。
【０５９２】
当業者は、先行する実施形態における一部または全部のステップが、1つのプログラムの命令に従う関係するハードウェアによって実行されうることを理解する。プログラムは、コンピュータ可読記憶媒体に格納することができる。プログラムの実行は、以下のステップを含む。
【０５９３】
時間領域から周波数領域への信号処理方法は、
時間領域データを前処理するステップと、
前処理されたデータを、回転因子
【０５９４】
【数１８８】
【０５９５】
を使用することによって前回転するステップと、
前回転データに対してN/4点のDFTを実行するステップと、
DFTの後のデータを、回転因子
【０５９６】
【数１８９】
【０５９７】
を使用することによって後回転し、周波数領域データを取得するステップとを含み、
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、
【０５９８】
【数１９０】
【０５９９】
である。
【０６００】
周波数領域から時間領域への信号処理方法は、
周波数領域データにひねりを施すステップと、
ひねりを施したデータを、回転因子
【０６０１】
【数１９１】
【０６０２】
を使用することによって前回転するステップと、
前回転データに対してN/4点のDFTを実行するステップと、
DFTの後のデータを、回転因子
【０６０３】
【数１９２】
【０６０４】
を使用することによって後回転するステップと、
後回転データを後処理して、時間領域データを取得するステップとを含み、
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、
【０６０５】
【数１９３】
【０６０６】
である。
【０６０７】
データ処理方法は、
アドレステーブルに従って入力データに対してQ回にわたってP点DFTを実行するステップと、
アドレステーブルに従ってQ回にわたってP点DFTを実行した後に得られたデータに対してP回にわたってQ点DFTを実行するステップとを含む。
【０６０８】
上述の記憶媒体は、読み出し専用メモリ(ROM)、磁気ディスク、またはコンパクトディスクであってよい。
【０６０９】
図8は、本発明の一実施形態における時間領域から周波数領域への信号処理装置の構造を示す図である。この装置は、
時間領域データを前処理するように適合された前処理ユニット801と、
回転因子
【０６１０】
【数１９４】
【０６１１】
を使用することによって、前処理ユニット801により得られたデータを前回転するように適合された第1の前回転ユニット802と、
第1の前回転ユニット802によって処理されたデータに対してN/4点のDFTを実行するように適合された第1のフーリエ変換ユニット803と、
第1のフーリエ変換ユニット803によってDFTが実行された後にデータを後回転して周波数領域データを取得するように適合された第1の後回転ユニット804とを備え、
aおよびbは定数であり、Nは時間領域データの長さであり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０６１２】
【数１９５】
【０６１３】
である。
【０６１４】
第1の後回転ユニット804は、
DFTが実行された後のデータを、回転因子
【０６１５】
【数１９６】
【０６１６】
および正規化因子Aを使用することによって後回転し、周波数領域データを取得するように適合された第2の後回転ユニットを備える。
【０６１７】
第1のフーリエ変換ユニット803は、
アドレステーブルに従って第1の前回転ユニットによって処理されたデータに対してQ回にわたってP点DFTを実行するように適合された第1の変換ユニットと、
アドレステーブルに従って第1の変換ユニットによって変換されたデータに対してP回にわたってQ点DFTを実行するように適合された第2の変換ユニットとを備える。
【０６１８】
PおよびQは、互いに素な正整数であり、M=N/4=P×Qである。Mは、アドレステーブルの長さである。アドレステーブルは<K1×n1+K2×n2>Mであり、ただし、n1=0,...,P-1およびn2=1,...,Q-1である。K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす。<Z>Mは法Mに関するZの剰余を意味する。
【０６１９】
本発明の実施形態において提供される時間領域から周波数領域への信号処理装置に従って、周波数領域から時間領域への信号処理装置が本発明の一実施形態において提供される。図9は、周波数領域から時間領域への信号処理装置の構造を示している。この装置は、
周波数領域データにひねりを施すように適合されたひねり処理ユニット901と、
回転因子
【０６２０】
【数１９７】
【０６２１】
を使用することによって、ひねり処理ユニット901により得られたデータを前回転するように適合された第2の前回転ユニット902と、
第2の前回転ユニット902によって処理されたデータに対してN/4点のDFTを実行するように適合された第2のフーリエ変換ユニット903と、
第2のフーリエ変換ユニット903によってDFTが実行された後にデータを後回転するように適合された第3の後回転ユニット904と、
第3の後回転ユニット904によって処理されたデータを後処理して時間領域データを取得するように適合された後処理ユニット905とを備え、
cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０６２２】
【数１９８】
【０６２３】
である。
【０６２４】
第3の後回転ユニット904は、
DFTが実行された後のデータを、回転因子
【０６２５】
【数１９９】
【０６２６】
および正規化因子Bを使用することによって後回転するように適合された第4の後回転ユニットを備える。
【０６２７】
第2のフーリエ変換ユニット903は、
アドレステーブルに従って第2の前回転ユニットによって処理されたデータに対してQ回にわたってP点DFTを実行するように適合された第3の変換ユニットと、
アドレステーブルに従って第3の変換ユニットによって変換されたデータに対してP回にわたってQ点DFTを実行するように適合された第4の変換ユニットとを備える。
【０６２８】
PおよびQは、互いに素な正整数であり、M=N/4=P×Qである。Mは、アドレステーブルの長さである。アドレステーブルは<K1×n1+K2×n2>Mであり、ただし、n1=0,...,P-1およびn2=1,...,Q-1である。K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす。<Z>Mは法Mに関するZの剰余を意味する。
【０６２９】
本発明の実施形態において提供される時間領域から周波数領域への信号処理装置および周波数領域から時間領域への信号処理装置の特定の応用に関しては、本発明の実施形態において提供される信号処理方法の説明を参照されたい。
【０６３０】
本発明の実施形態において提供される時間領域から周波数領域への信号処理装置および周波数領域から時間領域への信号処理方法において、回転因子中の
【０６３１】
【数２００】
【０６３２】
は
【０６３３】
【数２０１】
【０６３４】
に展開することができ、しかも条件
【０６３５】
【数２０２】
【０６３６】
および
【０６３７】
【数２０３】
【０６３８】
を満たし、回転因子中の
【０６３９】
【数２０４】
【０６４０】
は同じ対称条件を満たすので、本発明の実施形態において提供される時間領域から周波数領域への信号処理装置および周波数領域から時間領域への信号処理装置はN/4点のデータテーブルを格納するだけでよい。従来技術と比較すると、少なくともN/4点のサインテーブルおよびN/4点のコサインテーブルは、合わせてN/2個の点について、格納する必要がある場合、本発明の実施形態は、格納の複雑さおよび記憶容量を著しく低減し、ストレージリソースの消費を減らし、信号処理の効率を高める。
【０６４１】
本発明の一実施形態において提供されるデータ処理装置では、出力データの使用可能な列を保証し、アドレッシングコストを低減するために、アドレッシングにアドレステーブルを使用する。図10は、この実施形態において提供されるデータ処理装置の構造を示している。装置は、アドレステーブルユニット1001、第5の変換ユニット1002、および第6の変換ユニット1003を備える。
【０６４２】
アドレステーブルユニット1001は、アドレステーブルを作成するか、または格納するように適合される。
【０６４３】
アドレステーブルに格納されているアドレスは、0,1,...,M-1と横断して、入力データとの1対1マッピングを形成する。
【０６４４】
実際、アドレステーブルは、複数のアプローチで得ることができる。この実施形態では、アドレステーブルは、式<K1×n1+K2×n2>Mを使用することによって得られる。
【０６４５】
アドレステーブルはI=<K1×n1+K2×n2>Mであるが、式中、n1=0,...,P-1、n2=0,...,Q-1であり、PおよびQは、互いに素な正整数であり、M=P×Qであり、K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす。<Z>Mは法Mに関するZの剰余を意味する。
【０６４６】
アドレステーブルが1対1マッピングの条件を満たす場合、以下の3つの条件が満たされる必要がある。
【０６４７】
(1)K1はQの正整数倍であり、および/またはK2はPの正整数倍である。
【０６４８】
(2)K1およびPは、互いに素な数である。
【０６４９】
(3)K2およびQは、互いに素な数である。
【０６５０】
第5の変換ユニット1002は、アドレステーブルユニット1001によって作成されるか、または格納されているアドレステーブルに従って入力データに対しQ回にわたってP点DFTを実行するように適合されている。
【０６５１】
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=i、n1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のP点DFTの結果をxのステップの循環シフトで適用する。
【０６５２】
ここでは、xは、法Pに関する
【０６５３】
【数２０５】
【０６５４】
の巡回剰余の逆数であり、
【０６５５】
【数２０６】
【０６５６】
を満たす。
【０６５７】
例えば、アドレステーブルIがI[n1][n2]の二次元配列の形式で格納される場合、i番目のP点DFTの入力データは、アドレステーブルI[n1][n2]、n1=0,...,P-1に格納されているP個のアドレスインデックスに関連付けられているデータである。それぞれのP点DFTの結果は、xのステップの循環シフトで適用される。
【０６５８】
第6の変換ユニット1003は、アドレステーブルユニット1001によって作成されるか、または格納されているアドレステーブルに従って第5の変換ユニット1002によって変換されたデータに対しP回にわたってQ点DFTを実行するように適合されている。
【０６５９】
i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=i、n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のQ点DFTの結果をyのステップの循環シフトで適用する。
【０６６０】
ここでは、yは、法Qに関する
【０６６１】
【数２０７】
【０６６２】
の巡回剰余の逆数であり、
【０６６３】
【数２０８】
【０６６４】
を満たす。
【０６６５】
例えば、アドレステーブルIがI[n1][n2]の二次元配列の形式で格納される場合、i番目のQ点DFTの入力データは、アドレステーブルI[n1][n2]、n2=0,...,Q-1に格納されているQ個のアドレスインデックスに関連付けられているデータである。それぞれのQ点DFTの結果は、yのステップの循環シフトで適用される。
【０６６６】
本発明の実施形態において提供されるデータ処理装置では、FFTが実行されるときに、アドレステーブルがアドレッシングに使用されるので、入力データはアドレステーブル内の関連付けられているアドレスに従って読み込まれ、出力データはアドレステーブル内の関連付けられているアドレスに従って格納される。変換データは、使用可能な列になっており、逆変換の際に特別な再配列は不要である。したがって、計算におけるアドレッシングコストは低減され、計算効率が増大する。
【０６６７】
以下では、アドレステーブルIに基づく変換が、出力データの使用可能な列を保証することを証明する。
【０６６８】
FFTの定義は、
【０６６９】
【数２０９】
【０６７０】
である。
【０６７１】
M=P×Qであり、PおよびQは、互いに素な正整数であり、もし
n=<K1×n1+K2×n2>M n1=0,...,P-1,
n2=0,...,Q-1
k=<K1×k1+K2×k2>M k1=0,...,P-1
k2=0,...,Q-1
ならば、
X(k)はX'(k1,k2)およびX'(k1,k2)=X(<K1×k1+K2×k2>M)と書くことができ、x(n)はx'(n1,n2)およびx'(n1,n2)=X(<K1×n1+K2×n2>M)と書くことができる。
【０６７２】
したがって、FFTの公式は、
【０６７３】
【数２１０】
【０６７４】
に展開することができる。
【０６７５】
<K1K2>M=0の場合
【０６７６】
【数２１１】
【０６７７】
であり、したがって
【０６７８】
【数２１２】
【０６７９】
である。
【０６８０】
なぜなら、
【０６８１】
【数２１３】
【０６８２】
だからである。
【０６８３】
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=i、n1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のP点DFTの結果をxのステップの循環シフトで適用する。
【０６８４】
ここでは、xは、法Pに関する
【０６８５】
【数２１４】
【０６８６】
の巡回剰余の逆数であり、
【０６８７】
【数２１５】
【０６８８】
【数２１６】
【０６８９】
を満たす。n1=0のときに、
【０６９０】
【数２１７】
【０６９１】
であり、n1=1のときに
【０６９２】
【数２１８】
【０６９３】
であり、同様に、n1=xのときに
【０６９４】
【数２１９】
【０６９５】
である。順次出力のFFTの式
【０６９６】
【数２２０】
【０６９７】
では、n1=1のときの回転因子は
【０６９８】
【数２２１】
【０６９９】
である。P点DFTでは、
【０７００】
【数２２２】
【０７０１】
となるのは、n1=xのとき、xが
【０７０２】
【数２２３】
【０７０３】
を満たすときに限る。P点DFTの順次出力を使用可能にするために、xのステップの循環シフトを、n1=0,...,P-1に対応する出力に対して実行する必要がある。
【０７０４】
同様に、i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=i、n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のQ点DFTの結果をyのステップの循環シフトで適用する。
【０７０５】
ここでは、yは、法Qに関する
【０７０６】
【数２２４】
【０７０７】
の巡回剰余の逆数であり、
【０７０８】
【数２２５】
【０７０９】
を満たす。
【０７１０】
本発明は、例示的な実施形態を通じて説明されているけれども、本発明はそのような実施形態に限定されない。当業者であれば本発明の精神および範囲から逸脱することなく、本発明に対しさまざまな修正および変更を加えることができることは、明らかである。請求項およびその等価物により定義された保護の範囲内にある限りそれらの修正および変更も、本発明の対象範囲であることが意図されている。
【符号の説明】
【０７１１】
801 前処理ユニット
802 第1の前回転ユニット
803 第1のフーリエ変換ユニット
804 第1の後回転ユニット
901 ひねり処理ユニット
902 第2の前回転ユニット
903 第2のフーリエ変換ユニット
904 第3の後回転ユニット
905 後処理ユニット
1001 アドレステーブルユニット
1002 第5の変換ユニット
1003 第6の変換ユニット
【技術分野】
【０００１】
本出願は、参照により本明細書に組み込まれている、2009年6月24日に中国特許庁に出願した中国特許出願第200910150720.5号、名称「Signal Processing Method and Data Processing Method and Apparatus」の優先権を主張するものである。
【０００２】
本発明は、デジタル信号処理技術に関するものであり、特に、信号処理方法ならびにデータ処理の方法および装置に関するものである。
【背景技術】
【０００３】
フーリエ変換、離散コサイン変換(DCT)、および離散サイン変換(DST)などの直交変換は、デジタル信号処理、特に、スペクトル分析、画像符号化、および音声符号化において広く使用されている。
【０００４】
DCTは、空間変換であり、DCTベースの符号化システムが適切な圧縮性能を備えるように強いエネルギー集中特性を有する。
【０００５】
修正離散コサイン変換(MDCT)は、DCTベースの改良された変換である。MDCTは、連続するブロック間のブロッキング効果を回避するように設計されている。これは、広帯域および超広帯域デジタルオーディオ符号化において重要な役割を果たす。
【０００６】
変換公式に従って順MDCT(forward MDCT)および逆MDCT(inverse MDCT)を直接適用すると、計算複雑度が高まる。特に、点の数が多い場合には、計算複雑度が高くなるためMDCTをリアルタイムで実行することはできない。MDCTはリアルタイム通信および特にオーディオ符号化において広く応用されるため、高速MDCT法の実現が急務となっている。高速MDCTの実現のために従来技術においてよく使用される方法は、高速フーリエ変換(FFT)に基づくものである。
【０００７】
N点の広く使用されているFFTベースの高速MDCTとして、N/2点FFTに基づく高速MDCTおよびN/4点FFTに基づく高速MDCTが挙げられる。
【０００８】
従来技術の研究および実践において、以下の弱点が見つかっている。
【０００９】
N/4点FFTに基づく高速MDCTアルゴリズムを適用する場合、前回転処理(pre-rotation processing)および後回転処理(post-rotation processing)は、少なくともN/4点のコサイン値およびN/4点のサイン値、合わせてN/2個の値を記憶する必要がする。前回転ステップと後回転ステップが非対称的である場合、N個の値を記憶する必要がある。Nが大きい場合、追加ストレージの容量が大きくなり、したがって、多くのストレージリソースが消費され、変換効率が影響を受ける。
【００１０】
互いに素な因数に基づく高速フーリエ変換アルゴリズムが採用された場合、多数のアドレッシング演算が必要になり、このアルゴリズムは、データ列のシーケンシャルアクセスを考慮しない。変換を通して得られたデータは、最終的な出力データを得るために再配列する必要がある。したがって、計算量がさらに多くなる。
【発明の概要】
【課題を解決するための手段】
【００１１】
本発明の実施形態は、信号処理の効率の改善を支援するための信号処理方法ならびにデータ処理の方法および装置を実現する。
【００１２】
時間領域から周波数領域への信号処理方法は、
時間領域データを前処理するステップと、
前処理されたデータを、回転因子
【００１３】
【数１】
【００１４】
を使用することによって前回転するステップと、
前回転データに対してN/4点の離散フーリエ変換(DFT)を実行するステップと、
DFTによって変換されたデータを、回転因子
【００１５】
【数２】
【００１６】
を使用することによって後回転し、周波数領域データを取得するステップとを含み、
式中、aおよびbは定数であり、Nは時間領域データの長さであり、
【００１７】
【数３】
【００１８】
【数４】
【００１９】
【数５】
【００２０】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００２１】
周波数領域から時間領域への信号処理方法は、
周波数領域データにひねりを施す(twiddling)ステップと、
ひねりを施したデータを、回転因子
【００２２】
【数６】
【００２３】
を使用することによって前回転するステップと、
前回転データに対してN/4点のDFTを実行するステップと、
DFTによって変換されたデータを、回転因子
【００２４】
【数７】
【００２５】
を使用することによって後回転するステップと、
後回転データを後処理して、時間領域データを取得するステップとを含み、
式中、cおよびdは定数であり、Nは周波数領域データの倍長であり、
【００２６】
【数８】
【００２７】
【数９】
【００２８】
【数１０】
【００２９】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００３０】
データ処理方法は、
アドレステーブルに基づきQ回にわたってデータに対しP点DFTを実行するステップと、
アドレステーブルに基づきP回にわたってQ回にわたってP点DFTを実行した後に得られたデータに対してQ点DFTを実行するステップとを含む。
【００３１】
時間領域から周波数領域への信号処理装置は、
時間領域データを前処理するように適合された前処理ユニットと、
回転因子
【００３２】
【数１１】
【００３３】
を使用することによって、前処理ユニットにより得られたデータを前回転するように適合された第1の前回転ユニットと、
第1の前回転ユニットによって処理されたデータに対してN/4点のDFTを実行するように適合された第1のフーリエ変換ユニットと、
回転因子
【００３４】
【数１２】
【００３５】
を使用することによって第1のフーリエ変換ユニットにより変換されたデータを後回転して周波数領域データを取得するように適合された第1の後回転ユニットとを備え、式中、
【００３６】
【数１３】
【００３７】
【数１４】
【００３８】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００３９】
周波数領域から時間領域への信号処理装置は、
周波数領域データにひねりを施すように適合されたひねり処理ユニット(twiddling unit)と、
回転因子
【００４０】
【数１５】
【００４１】
を使用することによって、ひねり処理ユニットにより得られたデータを前回転するように適合された第2の前回転ユニットと、
第2の前回転ユニットによって処理されたデータに対してN/4点のDFTを実行するように適合された第2のフーリエ変換ユニットと、
回転因子
【００４２】
【数１６】
【００４３】
を使用することによって、第2のフーリエ変換ユニットにより得られたデータを後回転するように適合された第3の後回転ユニットと、
第3の後回転ユニットによって処理されたデータを後処理して時間領域データを取得するように適合された後処理ユニットとを備え、式中、
【００４４】
【数１７】
【００４５】
【数１８】
【００４６】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００４７】
データ処理装置は、
アドレステーブルを作成するか、または格納するように適合されたアドレステーブルユニットと、
アドレステーブルユニットによって作成されるか、または格納されているアドレステーブルに基づきQ回にわたってデータに対しP点DFTを実行するように適合された第5の変換ユニットと、
アドレステーブルユニットによって作成されるか、または格納されているアドレステーブルに基づきP回にわたって第5の変換ユニットによって変換されたデータに対しQ点DFTを実行するように適合された第6の変換ユニットとを備える。
【００４８】
上記の技術的解決策では、本発明の実施形態において提供される信号処理方法によって採用されている回転因子は、定数と
【００４９】
【数１９】
【００５０】
との積である。因子
【００５１】
【数２０】
【００５２】
は対称であるため、前回転および後回転を完了させるためにN/4点のデータテーブルを記憶するだけでよい。従来技術に比べて、本発明の実施形態において提供される信号処理方法は、記憶容量を低減し、ストレージリソースの消費を減らし、変換効率を高める。さらに、本発明の実施形態の信号処理方法では後回転を実行するときに正規化因子が不要になるため、関係する処理ステップなしで済ませられ、したがって変換効率がさらに改善される。
【００５３】
本発明または従来技術の技術的な解決策をわかりやすく説明するために、本発明または従来技術の実施形態の説明において必要な図面について簡単に説明する。後述の図面は、本発明の一部の実施形態のみであることは明らかである。当業者であれば、創造的な作業を行うことなくこれらの図面に基づいて他の図面を得ることができる。
【図面の簡単な説明】
【００５４】
【図１】本発明の第1の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。
【図２】本発明の一実施形態におけるFFTの演算に対しアドレステーブルを採用するデータ処理方法の流れ図である。
【図３】本発明の第2の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。
【図４】本発明の第3の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。
【図５】本発明の第4の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。
【図６】本発明の第5の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。
【図７】本発明の第6の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。
【図８】本発明の一実施形態における時間領域から周波数領域への信号処理装置の構造を示す図である。
【図９】本発明の一実施形態における周波数領域から時間領域への信号処理装置の構造を示す図である。
【図１０】本発明の一実施形態におけるデータ処理装置の構造を示す図である。
【発明を実施するための形態】
【００５５】
本発明の技術的解決策は、以下で付属の図面を参照しつつ詳細に説明される。これらの実施形態は例示的なものにすぎず、本発明は、そのような実施形態に限定されないことは明らかである。本発明の実施形態に基づいて当業者が構成する他の実施形態も、本発明の保護の範囲内に入る。
【００５６】
本発明の実施形態は、信号処理の効率の改善を支援するための信号処理方法ならびにデータ処理の方法および装置を実現する。
【００５７】
従来技術では、N/4点のFFTに基づく高速MDCTを実現するために、最初にN点のデータに窓関数を掛け、ひねりを施し、前回転して、N点のMDCTをN/4点のFFTに変える。FFT演算で得られたデータを後回転して、最終的なMDCT係数を得る。
【００５８】
MDCTの定義は
【００５９】
【数２１】
【００６０】
であり、式中、Aは正規化因子であり、定数である。
【００６１】
MDCTの定義によれば、
【００６２】
【数２２】
【００６３】
【数２３】
【００６４】
が得られるが、式中、
【００６５】
【数２４】
【００６６】
である。
【００６７】
これら2つの式を組み合わせて、
【００６８】
【数２５】
【００６９】
を得ることができる。
【００７０】
次いで、N/4点FFTに基づく順MDCTは以下のステップを含む。
【００７１】
1.窓関数を掛ける:
yn=hnxn n=0,...,N-1
hnは、完全な再構成条件を満たす窓関数であるが、必ずしも対称窓ではない。つまり、解析および合成では、解析窓および合成窓が一緒になって完全な再構成を行える限り、異なる窓を使用することができる。xnは入力データである。通常、x0-N/2-1はキャッシュされている前のフレームのデータであり、xN/2-N-1は現在のフレームのデータである。
【００７２】
2.ひねりを施す:
un=(Z2n+jzN/2-1-2n) n=0,...,N/4-1
式中、
【００７３】
【数２６】
【００７４】
または
【００７５】
【数２７】
【００７６】
である。
【００７７】
3.回転因子
【００７８】
【数２８】
【００７９】
を使用することによってunを前回転する。
【００８０】
4.回転データに対してN/4点FFTを実行する。
【００８１】
5.回転因子
【００８２】
【数２９】
【００８３】
および正規化因子Aを使用することによって変換データを後回転する。
【００８４】
6.後回転を通じて得られる複素数の実部はX2kであり、これはMDCTスペクトルの奇数周波数を表し、虚部は-Xn/2-1-2kであり、これはMDCTスペクトルの偶数周波数を表す。
【００８５】
回転因子
【００８６】
【数３０】
【００８７】
は、
【００８８】
【数３１】
【００８９】
に展開することができる。
【００９０】
回転因子
【００９１】
【数３２】
【００９２】
および
【００９３】
【数３３】
【００９４】
は、前回転および後回転の処理に必要であるため、少なくともN/4点のコサイン値およびN/4点のサイン値、合わせてN/2個の値を記憶する必要がある。前回転ステップと後回転ステップが非対称的である場合、N個の値を記憶する必要がある。Nが大きい場合、追加ストレージの容量が大きくなり、したがって、多くのストレージリソースが消費され、変換効率が影響を受ける。
【００９５】
本発明の一実施形態において提供される時間領域から周波数領域への信号処理方法は、以下のステップを含む。
【００９６】
1.時間領域データを前処理する。
【００９７】
2.前処理されたデータを、回転因子
【００９８】
【数３４】
【００９９】
を使用することによって前回転する。
【０１００】
3.前回転データに対してN/4点のDFTを実行する。
【０１０１】
4.DFTの後のデータを、回転因子
【０１０２】
【数３５】
【０１０３】
を使用することによって後回転し、周波数領域データを取得する。
式中、aおよびbは定数であり、Nは時間領域データの長さであり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０１０４】
【数３６】
【０１０５】
である。
【０１０６】
前回転の前のデータに対するすべての処理は、前処理として説明できる。この実施形態では、例えば、前処理は、窓関数を掛けてひねりを施すステップまたはひねりを施すステップのみとしてよい。
【０１０７】
本発明の一実施形態において提供される周波数領域から時間領域への信号処理方法は、以下のステップを含む。
【０１０８】
1.周波数領域データにひねりを施す。
【０１０９】
2.ひねりを施されたデータを、回転因子
【０１１０】
【数３７】
【０１１１】
を使用することによって前回転する。
【０１１２】
3.前回転データに対してN/4点のDFTを実行する。
【０１１３】
4.DFTの後のデータを、回転因子
【０１１４】
【数３８】
【０１１５】
を使用することによって後回転する。
【０１１６】
5.後回転データを後処理して、時間領域データを取得する。
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０１１７】
【数３９】
【０１１８】
である。
【０１１９】
後回転の後のデータに対するすべての処理は、後処理として説明できる。後処理の内容は、対応する時間領域から周波数領域への信号処理方法における前処理の内容に依存する。この実施形態では、例えば、前処理が窓関数を掛けてひねりを施すステップである場合、後処理も窓関数を掛けてひねりを施すステップであり、前処理がひねりを施すステップだけである場合、後処理もひねりを施すステップだけである。
【０１２０】
時間領域から周波数領域への信号処理は、順変換とも称され、周波数領域から時間領域への信号処理は、逆変換とも称されうる。順変換と逆変換においてa×b×c×d=4/Nである場合、順変換の出力データを逆変換の入力データとして使用すると、逆変換の結果が順変換の前のデータを復元できるため、完全な再構成を行うことができる。実際、完全な再構成は必ずしも必要でない。
【０１２１】
本発明の一実施形態において提供される信号処理方法によって採用される回転因子における
【０１２２】
【数４０】
【０１２３】
は、
【０１２４】
【数４１】
【０１２５】
に展開することができ、
式中、
【０１２６】
【数４２】
【０１２７】
【数４３】
【０１２８】
である。
【０１２９】
式
【０１３０】
【数４４】
【０１３１】
から、n+(N/4-1-n)=N/4-1であることがわかり、n=0,...,N/4-1およびk=0,...,N/4-1に対して、(n=0のときの)
【０１３２】
【数４５】
【０１３３】
の第1の値は、(n=N/4-1のときの)
【０１３４】
【数４６】
【０１３５】
の最後の値に等しい。(n=1のときの)
【０１３６】
【数４７】
【０１３７】
の第2の値は、(n=N/4-2のときの)
【０１３８】
【数４８】
【０１３９】
の最後から2番目の値に等しく、以下同様である。
【０１４０】
したがって、
【０１４１】
【数４９】
【０１４２】
は、対称的である。前回転および後回転を完了させるために、
【０１４３】
【数５０】
【０１４４】
または
【０１４５】
【数５１】
【０１４６】
のN/4点データテーブルを記憶するだけでよい。
【０１４７】
従来のMDCTにおいて、MDCTのスペクトル係数を得るために、回転因子
【０１４８】
【数５２】
【０１４９】
および
【０１５０】
【数５３】
【０１５１】
を使用する必要があり、また
【０１５２】
【数５４】
【０１５３】
および
【０１５４】
【数５５】
【０１５５】
は対称的でない。したがって、前回転および後回転において少なくともN/4点のコサイン値およびN/4点のサイン値を記憶する必要がある。本発明の実施形態において提供される信号処理方法によって採用されている回転因子は、定数と
【０１５６】
【数５６】
【０１５７】
との積である。因子
【０１５８】
【数５７】
【０１５９】
は対称であるため、前回転および後回転を完了させるためにN/4点のデータテーブルを記憶するだけでよい。従来技術に比べて、本発明の実施形態の信号処理方法は、記憶容量を著しく低減し、ストレージリソースの消費を減らし、変換効率を高める。さらに、本発明の実施形態の信号処理方法では正規化因子が不要になるため、関係する処理ステップなしで済ませられ、したがって変換効率がさらに改善される。
【０１６０】
本発明の信号処理方法の例示的な実施形態について説明する。図1は、本発明の第1の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。この方法は、以下のステップを含む。
【０１６１】
101.時間領域データを前処理する。
【０１６２】
このステップでは、前処理は、窓関数を掛け、ひねりを施すステップを含む。実際には、他の前処理手段も使用される場合がある。
【０１６３】
時間領域データxnは入力データであると仮定する。通常、x0-N/2-1はキャッシュされている前のフレームデータであり、xN/2-N-1は現在のフレームデータである。Nは時間領域データの長さであり、この実施形態では、1280としてよい。最初にデータに窓関数を掛ける。
yn=hnxn n=0,...,N-1、
hnは、完全な再構成条件を満たす窓関数であり、解析窓関数と称されうる。逆変換で使用される窓関数は、合成窓関数と称されうる。解析窓関数は、解析窓関数と合成窓関数とが完全な再構成を一緒に行える限り合成窓関数と異なっていてもよい。窓関数を掛けたデータはひねりを施され、ひねりを施されたデータunは
un=(z2n+jzN/2-1-2n) n=0,...,N/4-1
を満たすが、
式中、
【０１６４】
【数５８】
【０１６５】
または
【０１６６】
【数５９】
【０１６７】
である。
【０１６８】
102.前処理されたデータを、回転因子
【０１６９】
【数６０】
【０１７０】
を使用することによって前回転する。
【０１７１】
ひねりを施されたデータunは、回転因子
【０１７２】
【数６１】
【０１７３】
n=0,...,N/4-1を使用することによって前回転され、式中、
【０１７４】
【数６２】
【０１７５】
であり、aは定数である。
【０１７６】
回転の後得られるデータは、
【０１７７】
【数６３】
【０１７８】
である。
【０１７９】
この実施形態では、定数は
【０１８０】
【数６４】
【０１８１】
とすることができる。回転因子中の
【０１８２】
【数６５】
【０１８３】
は、
【０１８４】
【数６６】
【０１８５】
の形式で表すことができ、これは
【０１８６】
【数６７】
【０１８７】
および
【０１８８】
【数６８】
【０１８９】
満たすので、N/4点のサインもしくはコサインデータテーブルのみが、この方法の態様において必要である。この実施形態では、N/4点のみのデータテーブルが記憶される。データテーブル内の値は、
【０１９０】
【数６９】
【０１９１】
n=0,...,319で表される。
【０１９２】
103.前回転データに対してN/4点のDFTを実行する。
【０１９３】
このステップでは、N/4点のふつうのDFTが使用されるか、または他のN/4点FFTが使用されうる。
【０１９４】
さらに、ステップ103では、アドレステーブルに基づくFFTは、M=N/4=P×Qのときに使用することができ、PおよびQは正整数であり、PおよびQは互いに素な数であり、アドレステーブルの長さはMである。
【０１９５】
図2は、本発明の一実施形態におけるFFTに対しアドレステーブルを採用するデータ処理方法の流れ図である。この方法は、以下のステップを含む。
【０１９６】
1031.アドレステーブルIを作成する。アドレステーブルIは
I=<K1×n1+K2×n2>M n1=0,...,P-1
n2=0,...,Q-1
を満たす。
【０１９７】
K1およびK2は、<K1K2>M=0を満たす互いに素な正整数であるが、ただし、K1K2=Zおよび<Z>Mは法Mに関するZの剰余を意味し、ZをMで割った余りである。このステップは、より早い段階に実行されうるか、またはステップ101または102との順次的関係を持たない。つまり、アドレステーブルIは、予め計算され格納されうる。データの順序関係を決定するために、アドレステーブルIに格納されているアドレスは0,1,...,M-1と横断して、入力データとの1対1マッピングを形成する必要がある。アドレステーブルIが1対1マッピングの条件を満たす場合、以下の3つの条件が満たされる必要がある。
【０１９８】
(1)K1はQの正整数倍であり、および/またはK2はPの正整数倍である。
【０１９９】
(2)K1およびPは、互いに素な数である。
【０２００】
(3)K2およびQは、互いに素な数である。
【０２０１】
P=64、Q=5、K1=65、K2=256、およびM=N/4=320と仮定すると、アドレステーブルIは、
I=<65n1+256n2>320
で表すことができ、
式中、n1=0,...,63およびn2=0,...,4である。
【０２０２】
アドレステーブルIは、I[n2×n1]の一次元配列またはI[n1][n2]の二次元配列などの配列の形式で1つのテーブルに格納することができる。
【０２０３】
アドレステーブルIがM=320点のアドレステーブルであり、K1=65、K2=256、Q=5、P=64、およびQ×P=5×64点と仮定すると、アドレステーブルIがI[n2×n1]の一次元配列として格納される場合、
Idx[Q×P]=
{0,65,130,195,260,5,70,135,200,265,10,75,140,205,270,15,80,145,210,275,20,85,150,215,280,25,90,155,220,285,30,95,160,225,290,35,100,165,230,295,40,105,170,235,300,45,110,175,240,305,50,115,180,245,310,55,120,185,250,315,60,125,190,255,
256,1,66,131,196,261,6,71,136,201,266,11,76,141,206,271,16,81,146,211,276,21,86,151,216,281,26,91,156,221,286,31,96,161,226,291,36,101,166,231,296,41,106,171,236,301,46,111,176,241,306,51,116,181,246,311,56,121,186,251,316,61,126,191,
192,257,2,67,132,197,262,7,72,137,202,267,12,77,142,207,272,17,82,147,212,277,22,87,152,217,282,27,92,157,222,287,32,97,162,227,292,37,102,167,232,297,42,107,172,237,302,47,112,177,242,307,52,117,182,247,312,57,122,187,252,317,62,127,
128,193,258,3,68,133,198,263,8,73,138,203,268,13,78,143,208,273,18,83,148,213,278,23,88,153,218,283,28,93,158,223,288,33,98,163,228,293,38,103,168,233,298,43,108,173,238,303,48,113,178,243,308,53,118,183,248,313,58,123,188,253,318,63,
64,129,194,259,4,69,134,199,264,9,74,139,204,269,14,79,144,209,274,19,84,149,214,279,24,89,154,219,284,29,94,159,224,289,34,99,164,229,294,39,104,169,234,299,44,109,174,239,304,49,114,179,244,309,54,119,184,249,314,59,124,189,254,319};
となる。
【０２０４】
アドレステーブルIがI[n1][n2]の二次元配列として格納される場合、
Idx[Q][P]=
{{0,65,130,195,260,5,70,135,200,265,10,75,140,205,270,15,80,145,210,275,20,85,150,215,280,25,90,155,220,285,30,95,160,225,290,35,100,165,230,295,40,105,170,235,300,45,110,175,240,305,50,115,180,245,310,55,120,185,250,315,60,125,190,255},
{256,1,66,131,196,261,6,71,136,201,266,11,76,141,206,271,16,81,146,211,276,21,86,151,216,281,26,91,156,221,286,31,96,161,226,291,36,101,166,231,296,41,106,171,236,301,46,111,176,241,306,51,116,181,246,311,56,121,186,251,316,61,126,191},
{192,257,2,67,132,197,262,7,72,137,202,267,12,77,142,207,272,17,82,147,212,277,22,87,152,217,282,27,92,157,222,287,32,97,162,227,292,37,102,167,232,297,42,107,172,237,302,47,112,177,242,307,52,117,182,247,312,57,122,187,252,317,62,127},
{128,193,258,3,68,133,198,263,8,73,138,203,268,13,78,143,208,273,18,83,148,213,278,23,88,153,218,283,28,93,158,223,288,33,98,163,228,293,38,103,168,233,298,43,108,173,238,303,48,113,178,243,308,53,118,183,248,313,58,123,188,253,318,63},
{64,129,194,259,4,69,134,199,264,9,74,139,204,269,14,79,144,209,274,19,84,149,214,279,24,89,154,219,284,29,94,159,224,289,34,99,164,229,294,39,104,169,234,299,44,109,174,239,304,49,114,179,244,309, 54,119,184,249,314,59,124,189,254,319}};
となる。
【０２０５】
1032.アドレステーブルIに基づきQ回にわたってP点DFTを実行する。
【０２０６】
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=iおよびn1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のP点DFTの結果をxのステップの循環シフトで適用する必要がある。
【０２０７】
ここでは、xは、法Pに関する
【０２０８】
【数７０】
【０２０９】
の巡回剰余の逆数であり、
【０２１０】
【数７１】
【０２１１】
を満たす。
【０２１２】
アドレステーブルIがI[n2×n1]の一次元配列の形式で格納される場合、アドレステーブルIに基づくQ回にわたるP点DFTは、
DFT_P(z(I+iP))x i=0,...,Q-1;
で表すことができる。
【０２１３】
それぞれのP点DFTの入力データは、I+iPから始まるP個の連続インデックスに対応するデータである。それぞれのP点DFTの結果は、xのステップの循環シフトで適用される。
【０２１４】
この実施形態では、64点DFTは、5回にわたって実行される。i番目(i=0,...,4)の64点DFTの入力データは、アドレステーブル配列I[64i]から始まる64個の連続するアドレスインデックスに関連付けられているデータである(回転後のデータ)。i番目の64点DFTの結果は、5のステップの循環シフトで適用される。例えば、ベクトルZ=[z0 z1 z2 z3 z4]上の2のステップの循環シフトの結果は、Z=[z0 z2 z4 z1 z3]である。それに加えて、計算の効率をさらに高めるために、DFTの代わりにFFTを使用するとよい。
【０２１５】
1033.アドレステーブルIに基づきP回にわたってQ点DFTを実行する。
【０２１６】
i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=i、n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のQ点DFTの結果をyのステップの循環シフトで適用する必要がある。
【０２１７】
ここでは、yは、法Qに関する
【０２１８】
【数７２】
【０２１９】
の巡回剰余の逆数であり、
【０２２０】
【数７３】
【０２２１】
を満たす。
【０２２２】
アドレステーブルIがI[n2×n1]の一次元配列の形式で格納される場合、アドレステーブルIに基づくP回にわたるQ点DFTは、
DFT_Q(z(I+i))y i=0,...,P-1;
で表すことができる。
【０２２３】
Q点DFTの入力データは、Pのステップでそれぞれ分離されているI+iから始まるQ個のインデックスに対応するデータである。それぞれのQ点DFTの結果は、yのステップの循環シフトで適用される。
【０２２４】
この実施形態では、5点DFTは、64回にわたって実行される。i番目(i=0,...,63)の5点DFTの入力データは、アドレステーブル配列I[i]から始まる5個の連続するアドレスインデックスに関連付けられているデータであり(回転後のデータ)、それぞれ64のステップで分離されている。i番目の5点DFTは、4のステップの循環シフトで適用される。
【０２２５】
従来技術では、互いに素な因子に基づく大半のDFTでは、データ列の順次アクセスを考慮しない。変換を通して得られたデータは、最終的な出力データを得るために再配列する必要がある。したがって、計算量がさらに多くなる。この実施形態では、DFTにアドレステーブルが使用され、アドレッシングはアドレステーブルに基づき、入力データはこのアドレステーブル内の関連付けられているアドレスに従って読み込まれ、出力データはアドレステーブル内の関連付けられているアドレスに従って格納される。変換の後に得られたデータの列は、特別な再配列なしで使用可能である。したがって、計算の複雑度は低減され、計算効率が高まる。
【０２２６】
104.DFTの後のデータを、回転因子
【０２２７】
【数７４】
【０２２８】
を使用することによって後回転し、周波数領域データを取得する。
【０２２９】
変換されたデータは、回転因子
【０２３０】
【数７５】
【０２３１】
k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０２３２】
【数７６】
【０２３３】
であり、bは定数である。この実施形態では、定数は
【０２３４】
【数７７】
【０２３５】
とすることができる。回転因子中の
【０２３６】
【数７８】
【０２３７】
は、
【０２３８】
【数７９】
【０２３９】
の形式で表すことができ、b=aであるため、ステップ102で使用されるN/4点データテーブルは、このステップの態様において再利用することができる。
【０２４０】
周波数領域データ、さらには最終的なスペクトルは、Xk、k=0,...,N/2-1であり、
【０２４１】
【数８０】
【０２４２】
【数８１】
【０２４３】
で表すことができる。
【０２４４】
本発明の第1の実施形態による時間領域から周波数領域への信号処理方法に従って、周波数領域から時間領域への信号処理方法が本発明の第2の実施形態において提供される。順変換が、本発明の第1の実施形態において提供される時間領域から周波数領域への信号処理方法を使用することによって実行される場合、本発明の第2の実施形態において提供される周波数領域から時間領域への信号処理方法を使用することによって実行されうる。
【０２４５】
図3は、本発明の第2の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。この方法は、以下のステップを含む。
【０２４６】
301.周波数領域データにひねりを施す。
【０２４７】
特に、周波数領域データXk、k=0,...,N/2-1にひねりを施す。この実施形態では、N=1280である。
【０２４８】
ひねりを施した後に得られる中間変数は、(X2k+jXN/2-1-2k)、k=0,...,N/4-1である。
【０２４９】
302.ひねりを施されたデータを、回転因子
【０２５０】
【数８２】
【０２５１】
を使用することによって前回転する。
【０２５２】
ひねりを施されたデータは、回転因子
【０２５３】
【数８３】
【０２５４】
k=0,...,N/4-1を使用することによって前回転されるが、式中、
【０２５５】
【数８４】
【０２５６】
であり、cは定数である。
【０２５７】
この実施形態では、定数は
【０２５８】
【数８５】
【０２５９】
とすることができ、したがって、ステップ102および104で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０２６０】
303.前回転データに対してN/4点のDFTを実行する。
【０２６１】
このステップでは、N/4点のふつうのDFTが使用されるか、または他のN/4点FFTが使用されうる。
【０２６２】
このステップでは、図2に示されている320点FFTが実行されうる。
【０２６３】
304.DFTの後のデータを、回転因子
【０２６４】
【数８６】
【０２６５】
を使用することによって後回転する。
【０２６６】
変換されたデータは、回転因子
【０２６７】
【数８７】
【０２６８】
k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０２６９】
【数８８】
【０２７０】
であり、dは定数である。
【０２７１】
この実施形態では、定数は
【０２７２】
【数８９】
【０２７３】
とすることができ、したがって、ステップ102および104で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０２７４】
上記の処理の後得られるデータynは、
【０２７５】
【数９０】
【０２７６】
である。
【０２７７】
305.後回転データを後処理して、時間領域データを取得する。
【０２７８】
このステップでは、後処理は、窓関数を掛け、ひねりを施すステップを含む。実際には、他の後処理手段も使用される場合がある。
【０２７９】
窓関数を掛け、ひねりを施した後、時間領域データ
【０２８０】
【数９１】
【０２８１】
が得られ、
【０２８２】
【数９２】
【０２８３】
であるが、式中、
【０２８４】
【数９３】
【０２８５】
、n=0,...,N/8-1であり、gnは合成窓であり、これは完全な再構成条件を解析窓hn、つまり、hngn+hn+N/2gn+N/2=1、n=0,...,N-N/2-1と一緒に満たす。mnは前のフレームのバッファリングされたデータであり、mnの更新は、
【０２８６】
【数９４】
【０２８７】
を満たす。
【０２８８】
本発明の第1の実施形態において提供される時間領域から周波数領域への信号処理方法および本発明の第2の実施形態において提供される周波数領域から時間領域への信号処理方法が使用される場合、順変換および逆変換中の定数a、b、c、およびdはa×b×c×d=4/Nを満たせば、逆変換の結果は完全な再構成に対し使用可能である。実際、完全な再構成は必ずしも必要でない。
【０２８９】
例えば、
【０２９０】
【数９５】
【０２９１】
を選択することができる。そこで、順変換および逆変換は、前回転および後回転を完了させるために
【０２９２】
【数９６】
【０２９３】
および
【０２９４】
【数９７】
【０２９５】
においてN/4点データテーブルを記憶するだけでよい。定数a、b、c、およびdが等しくない場合、前回転および後回転を完了するために、実用的な条件に従って適切なデータテーブルを格納する必要がある。
【０２９６】
本発明の一実施形態において提供される別の時間領域から周波数領域への信号処理方法は、以下のステップを含む。
【０２９７】
1.時間領域データを前処理する。
【０２９８】
2.前処理されたデータを、回転因子
【０２９９】
【数９８】
【０３００】
を使用することによって前回転する。
【０３０１】
3.前回転データに対してN/4点のDFTを実行する。
【０３０２】
4.DFTの後のデータを、回転因子
【０３０３】
【数９９】
【０３０４】
および正規化因子Aを使用することによって後回転し、周波数領域データを取得するが、
式中、aおよびbは定数であり、Nは時間領域データの長さであり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０３０５】
【数１００】
【０３０６】
である。
【０３０７】
前回転の前のデータに対するすべての処理は、前処理として説明できる。この実施形態では、例えば、前処理は、窓関数を掛けてひねりを施すステップまたはひねりを施すステップのみとしてよい。
【０３０８】
本発明の一実施形態において提供される別の周波数領域から時間領域への信号処理方法は、以下のステップを含む。
【０３０９】
1.周波数領域データにひねりを施す。
【０３１０】
2.ひねりを施されたデータを、回転因子
【０３１１】
【数１０１】
【０３１２】
を使用することによって前回転する。
【０３１３】
3.前回転データに対してN/4点のDFTを実行する。
【０３１４】
4.DFTの後のデータを、回転因子
【０３１５】
【数１０２】
【０３１６】
および正規化因子Bを使用することによって後回転する。
【０３１７】
5.後回転データを後処理して、時間領域データを取得するが、
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０３１８】
【数１０３】
【０３１９】
である。
【０３２０】
後回転の後のデータに対するすべての処理は、後処理として説明できる。後処理の内容は、対応する時間領域から周波数領域への信号処理方法における前処理の内容に依存する。この実施形態では、例えば、前処理が窓関数を掛けてひねりを施すステップである場合、後処理も窓関数を掛けてひねりを施すステップであり、前処理がひねりを施すステップである場合、後処理もひねりを施すステップである。
【０３２１】
時間領域から周波数領域への信号処理は、順変換とも称され、周波数領域から時間領域への信号処理は、逆変換とも称される。順変換と逆変換においてa×b×c×d=4/Nである場合、順変換の出力データを逆変換の入力データとして使用すると、逆変換の結果が順変換の前のデータを復元できるため、完全な再構成を行うことができる。例えば、a=b=c=d=1、A・B=4/N、または
【０３２２】
【数１０４】
【０３２３】
、A=B=1を選択することができる。実際、完全な再構成は必ずしも必要でない。
【０３２４】
この実施形態において提供される信号処理方法によって採用される回転因子における
【０３２５】
【数１０５】
【０３２６】
は、
【０３２７】
【数１０６】
【０３２８】
に展開することができ、
式中、
【０３２９】
【数１０７】
【０３３０】
【数１０８】
【０３３１】
である。
【０３３２】
したがって、
【０３３３】
【数１０９】
【０３３４】
は、対称的である。前回転および後回転を完了させるために、
【０３３５】
【数１１０】
【０３３６】
または
【０３３７】
【数１１１】
【０３３８】
のN/4点データテーブルを記憶するだけでよい。
【０３３９】
従来のMDCTにおいて、MDCTのスペクトル係数を得るために、回転因子
【０３４０】
【数１１２】
【０３４１】
を使用する必要があり、また
【０３４２】
【数１１３】
【０３４３】
は対称的でない。したがって、前回転および後回転において少なくともN/4点のコサイン値およびN/4点のサイン値を記憶する必要がある。本発明の実施形態において提供される信号処理方法によって採用されている回転因子は、定数と
【０３４４】
【数１１４】
【０３４５】
との積である。因子
【０３４６】
【数１１５】
【０３４７】
は対称であるため、前回転および後回転を完了させるためにN/4点のデータテーブルを記憶するだけでよい。従来技術に比べて、この実施形態の信号処理方法は、記憶容量および格納の複雑さを低減し、ストレージリソースの消費を減らし、変換効率を高める。
【０３４８】
本発明の信号処理方法の例示的な実施形態について説明する。
【０３４９】
広帯域オーディオコーデックのサンプリング周波数は16kHzであり、処理されるフレームサイズは20msであると仮定する。1つのフレームは、320個のサンプリング点を含む。本発明の一実施形態において提供される時間領域から周波数領域への信号処理方法を使用して、エンコーダで順変換を実行する。順変換の入力データは、xnであり、x0-N/2-1は前のフレームのキャッシュされている320点データであり、xN/2-N-1は現在のフレームの320点データであり、変換セクション長Nは、点640個分である。図4は、本発明の第3の実施形態において提供される信号処理方法の流れ図である。この方法は、以下を含む。
【０３５０】
401.時間領域入力データを前処理する。
【０３５１】
このステップでは、前処理は、窓関数を掛け、ひねりを施すステップを含む。
【０３５２】
xnが640点時間領域入力データであり、hnが完全な再構成条件を満たす640点窓関数である場合、窓関数を掛けたデータynは、
yn=hnxn n=0,...,N-1、
を満たし、
hnは、完全な再構成条件を満たす窓関数であり、これは解析窓関数として説明することができる。
【０３５３】
窓関数を掛けたデータはひねりを施され、得られたデータunは
【０３５４】
【数１１６】
【０３５５】
を満たすが、
式中、
【０３５６】
【数１１７】
【０３５７】
または
【０３５８】
【数１１８】
【０３５９】
である。
【０３６０】
402.前処理されたデータを、回転因子
【０３６１】
【数１１９】
【０３６２】
を使用することによって前回転する。
【０３６３】
ひねりを施されたデータunは、回転因子
【０３６４】
【数１２０】
【０３６５】
n=0,...,N/4-1を使用することによって前回転され、式中、
【０３６６】
【数１２１】
【０３６７】
であり、aは定数である。
【０３６８】
この実施形態では、a=1であり、回転因子は、
【０３６９】
【数１２２】
【０３７０】
によって表すことができる。
【０３７１】
この式は、
【０３７２】
【数１２３】
【０３７３】
および
【０３７４】
【数１２４】
【０３７５】
を満たす。
【０３７６】
特定の態様では、
【０３７７】
【数１２５】
【０３７８】
または
【０３７９】
【数１２６】
【０３８０】
のN/4点データテーブルを記憶するだけでよい。この実施形態では、N/4点のサインテーブルが記憶される。サインテーブル内の値は、
【０３８１】
【数１２７】
【０３８２】
、n=0,...,159で表される。
【０３８３】
403.前回転データに対してN/4個の入力のDFTを実行する。
【０３８４】
このステップでは、M=N/4=160点のふつうのDFTが使用されるか、またはM=N/4=160点のFFTが使用されうる。
【０３８５】
404.DFTの後のデータを、回転因子
【０３８６】
【数１２８】
【０３８７】
および正規化因子Aを使用することによって後回転し、周波数領域出力データを取得する。
【０３８８】
変換されたデータは、回転因子
【０３８９】
【数１２９】
【０３９０】
、k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０３９１】
【数１３０】
【０３９２】
であり、bは定数である。この実施形態では、b=1であり、回転因子は、
【０３９３】
【数１３１】
【０３９４】
によって表すことができる。
【０３９５】
b=aなので、ステップ402で使用されるN/4点データテーブルは、このステップの態様において使用することができる。
【０３９６】
最終データXk、k=0,...,N/2-1が得られ、これらは
【０３９７】
【数１３２】
【０３９８】
【数１３３】
【０３９９】
であり、式中、Aは正規化因子であり、定数である。
【０４００】
この実施形態では、定数Aは
【０４０１】
【数１３４】
【０４０２】
とすることができる。
【０４０３】
本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法に従って、周波数領域から時間領域への信号処理方法が本発明の第4の実施形態において提供される。本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法を使用して変換を実行する場合、本発明の第4の実施形態において提供される周波数領域から時間領域への信号処理方法を使用して対応する逆変換を実行することができる。
【０４０４】
図5は、本発明の第4の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。この方法は、以下を含む。
【０４０５】
501.周波数領域入力データにひねりを施す。
【０４０６】
この実施形態では、データXk、k=0,...,N/2-1にひねりを施して、中間変数
【０４０７】
【数１３５】
【０４０８】
、k=0,...,N/4-1を得るが、式中、N=640である。
【０４０９】
502.ひねりを施されたデータを、回転因子
【０４１０】
【数１３６】
【０４１１】
を使用することによって前回転する。
【０４１２】
ひねりを施されたデータは、回転因子
【０４１３】
【数１３７】
【０４１４】
、k=0,...,N/4-1を使用することによって前回転され、式中、
【０４１５】
【数１３８】
【０４１６】
であり、cは定数である。この実施形態ではc=1であり、本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ402および404で使用されるN/4点データテーブルも再利用することができる。
【０４１７】
503.前回転データに対してN/4点のDFTを実行する。
【０４１８】
回転データに対してM=N/4=160点のDFTを実行する。このステップでは、160点のふつうのDFTが使用されるか、または他の160点FFTが使用されうる。
【０４１９】
504.DFTの後のデータを、回転因子
【０４２０】
【数１３９】
【０４２１】
および正規化因子Bを使用することによって後回転する。
【０４２２】
変換されたデータは、回転因子
【０４２３】
【数１４０】
【０４２４】
、k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０４２５】
【数１４１】
【０４２６】
であり、dは定数である。上記の処理の後得られるデータynは、
【０４２７】
【数１４２】
【０４２８】
である。
【０４２９】
Bは、正規化因子であり、定数である。この実施形態では、定数Bは
【０４３０】
【数１４３】
【０４３１】
とすることができる。この実施形態ではd=1であり、本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ402および404で使用されるN/4点データテーブルも再利用することができる。
【０４３２】
505.後回転データを後処理して、時間領域出力データを取得する。
【０４３３】
このステップでは、後処理は、窓関数を掛け、ひねりを施すステップを含む。実際には、他の後処理手段も使用される場合がある。
【０４３４】
窓関数を掛けて、ひねりを施した後、出力データ
【０４３５】
【数１４４】
【０４３６】
、n=0,...,N/2-1が得られ、これは、
【０４３７】
【数１４５】
【０４３８】
を満たし、式中、
【０４３９】
【数１４６】
【０４４０】
n=0,...,N/8-1であり、gnは、解析窓hnと一緒に完全な再構成条件を満たす、合成窓である、つまり、
hngn+hn+N/2gn+N/2=1 n=0,...,N-N/2-1
であり、mnは前のフレームのバッファリングされたデータであり、mnの更新は、
【０４４１】
【数１４７】
【０４４２】
を満たす。
【０４４３】
完全な再構成条件を満たすために、順変換、逆変換、または順/逆変換に特定の正規化因子を掛けるとよい。この実施形態では、順変換および逆変換に同じ正規化因子を掛ける。適宜、順変換または逆変換のみに特定の正規化因子を掛けるか、または順変換および逆変換に異なる正規化因子を掛ける。完全な再構成は、a×b×c×d×A×B=4/Nである限り完成させることができる。
【０４４４】
さらに、正規化因子が使用される場合、FFTを実行するためにアドレステーブルも使用することができる。超広帯域オーディオコーデックにおいて、超広帯域オーディオエンコーダのサンプリング周波数は32kHzであり、処理されるフレームサイズは20msであると仮定する。つまり、1つのフレームは、640個のサンプリング点を含む。データに対して、順変換が実行される。xnが順変換の入力データである場合、x0-N/2-1は前のフレームの640点データであり、xN/2-N-1は現在のフレームの640点データである。
【０４４５】
図6は、本発明の第5の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。この方法は、以下のステップを含む。
【０４４６】
601.時間領域データを前処理する。
【０４４７】
前処理は、窓関数を掛け、ひねりを施すステップを含む。
【０４４８】
xnが1280点時間領域入力データであり、hnが完全な再構成条件を満たす1280点窓関数である場合、窓関数を掛けたデータynは、
yn=hnxn n=0,...,N-1,
を満たす。
【０４４９】
窓関数を掛けたデータはひねりを施され、得られたデータunは
un=(z2n+ jzN/2-1-2n) n=0,...,N/4-1
を満たすが、
式中、
【０４５０】
【数１４８】
【０４５１】
または
【０４５２】
【数１４９】
【０４５３】
である。
【０４５４】
窓関数は、このステップの解析窓関数hnおよび逆変換で使用される合成窓関数gnが式
hngn+hn+N/2gn+N/2=1 n=0,...,N-N/2-1
を満たすときに完全な再構成条件を満たす。
【０４５５】
602.前処理されたデータを、回転因子
【０４５６】
【数１５０】
【０４５７】
を使用することによって前回転する。
【０４５８】
ひねりを施されたデータunは、回転因子
【０４５９】
【数１５１】
【０４６０】
を使用することによって前回転される。回転の後得られるデータは、
【０４６１】
【数１５２】
【０４６２】
n=0,...,N/4-1であり、式中、
【０４６３】
【数１５３】
【０４６４】
であり、aは定数である。計算の複雑度をさらに低くするために、正規化因子を回転因子と直接組み合わせるとよい。この実施形態では、定数aは、回転因子において
【０４６５】
【数１５４】
【０４６６】
とすることができ、これは
【０４６７】
【数１５５】
【０４６８】
の形式で表すことができ、また
【０４６９】
【数１５６】
【０４７０】
【数１５７】
【０４７１】
である。
【０４７２】
したがって、N/4点のデータテーブルを記憶するだけでよい。この実施形態では、N/4点のデータテーブルが記憶され、データテーブル内の値は、
【０４７３】
【数１５８】
【０４７４】
、n=0,...,319で表される。
【０４７５】
603.アドレステーブルに基づくFFTを使用して前回転データに対してN/4点のDFTを実行する。
【０４７６】
この実施形態では、PおよびQを互いに素な正整数とするM=N/4=P×Q点のFFTが実行される。FFTは、以下のステップを含む。
【０４７７】
i.P=64、Q=5とし、PおよびQは互いに素であり、M=N/4=P×Q=320を満たすものとし、式
I=<K1xn1+K2xn2>M n1=0,...,P-1
n2=0,...,Q-1
を満たす、アドレステーブルIを作成する。
【０４７８】
K1およびK2は、<K1K2>M=0を満たす互いに素な正整数であるが、ただし、K1K2=Zおよび<Z>Mは法Mに関するZの剰余を意味し、ZをMで割った余りである。
【０４７９】
データの順序関係を決定するために、アドレステーブルIに格納されているアドレスは0,1,...,M-1と横断して、入力データとの1対1マッピングを形成する必要がある。アドレステーブルIが1対1マッピングの条件を満たす場合、以下の3つの条件が満たされる必要がある。
【０４８０】
(1)K1はQの正整数倍であり、および/またはK2はPの正整数倍である。
【０４８１】
(2)K1およびPは、互いに素な数である。
【０４８２】
(3)K2およびQは、互いに素な数である。
【０４８３】
この実施形態では、K1=65、K2=256であり、アドレステーブルIは、
I=<65n1 + 256n2>320
によって表すことができ、
式中、n1=0,...,63およびn2=0,...,4である。
【０４８４】
アドレステーブルIは、予め計算され格納されうる。このステップは、ステップ601および602との順序関係を持たない。実際、アドレステーブルIは、テーブルに格納することができる。この実施形態では、テーブルは、n2×n3の一次元配列として格納される。
【０４８５】
ii.アドレステーブルIに基づきQ回にわたってP点DFTを実行する。
DFT_P(z(I+iP))x i=0,...,Q-1
【０４８６】
それぞれのP点DFTの入力データは、I+iPから始まるP個の連続インデックスに対応するデータである。それぞれのP点DFTは、xのステップの循環シフトで適用される。ここで、xは、法Pに関する
【０４８７】
【数１５９】
【０４８８】
の巡回剰余の逆数であり、
【０４８９】
【数１６０】
【０４９０】
を満たす。この実施形態では、64点DFTは、5回にわたって実行される。i番目(i=0,...,4)の64点DFTの入力データは、アドレステーブル配列I[64i]から始まる64個の連続するアドレスインデックスに関連付けられているデータである(回転後のデータ)。i番目の64点DFTは、5のステップの循環シフトで適用される。例えば、ベクトルZ=[z0 z1 z2 z3 z4]上の2のステップの循環シフトの結果は、Z=[z0 z2 z4 z1 z3]である。それに加えて、計算の効率をさらに高めるために、DFTの代わりにFFTを使用するとよい。
【０４９１】
iii.アドレステーブルIに基づきP回にわたってQ点DFTを実行する。
DFT_Q(z(I+i))y i=0,...,P-1
【０４９２】
Q点DFTの入力データは、Pのステップでそれぞれ分離されているテーブルI内のI+iから始まるQ個のインデックスに対応するデータである。それぞれのQ点DFTの結果は、yのステップの循環シフトで適用される。ここで、yは、法Qに関する
【０４９３】
【数１６１】
【０４９４】
の巡回剰余の逆数であり、
【０４９５】
【数１６２】
【０４９６】
を満たす。この実施形態では、5点DFTは、64回にわたって実行される。i番目(i=0,...,63)の5点DFTの入力データは、アドレステーブル配列I[i]から始まる64個の点の間隔で5つのアドレスインデックスに関連付けられているデータである(回転後のデータ)。i番目の5点DFTは、4のステップの循環シフトで適用される。
【０４９７】
604.DFTの後のデータを、回転因子
【０４９８】
【数１６３】
【０４９９】
および正規化因子Aを使用することによって後回転し、周波数領域データを取得する。
【０５００】
変換されたデータは、回転因子
【０５０１】
【数１６４】
【０５０２】
、k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０５０３】
【数１６５】
【０５０４】
であり、bは定数である。この実施形態では、定数bは
【０５０５】
【数１６６】
【０５０６】
とすることができる。bが
【０５０７】
【数１６７】
【０５０８】
である場合、回転因子中の
【０５０９】
【数１６８】
【０５１０】
は、
【０５１１】
【数１６９】
【０５１２】
の形式で表すことができ、bの値はステップ602のaに等しいので、ステップ602で格納されるN/4点のデータテーブルも、このステップにおいて再利用することができる。
【０５１３】
出力データ、さらには最終的なスペクトルは、Xk、k=0,...,N/2-1であり、
【０５１４】
【数１７０】
【０５１５】
【数１７１】
【０５１６】
で表すことができ、
式中、Bは正規化因子であり、定数である。
【０５１７】
本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法に従って、周波数領域から時間領域への信号処理方法が本発明の第6の実施形態において提供される。本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法を使用して変換を実行する場合、本発明の第6の実施形態において提供される周波数領域から時間領域への信号処理方法を使用して対応する逆変換を実行することができる。
【０５１８】
図7は、本発明の第6の実施形態における周波数領域から時間領域への信号処理方法の流れ図であり、Xk、k=0,...,N/2-1は、逆変換の入力データである。この方法は、以下のステップを含む。
【０５１９】
701.周波数領域データにひねりを施す。
【０５２０】
特に、入力データXk、k=0,...,N/2-1にはひねりが施される。
【０５２１】
ひねりを施した後に得られる中間変数は、(X2k+jXN/2-1-2k)、k=0,...,N/4-1である。
【０５２２】
702.ひねりを施されたデータを、回転因子
【０５２３】
【数１７２】
【０５２４】
、k=0,...,N/4-1を使用することによって前回転する。
【０５２５】
式
【０５２６】
【数１７３】
【０５２７】
が成り立ち、cは定数である。
【０５２８】
この実施形態では、
【０５２９】
【数１７４】
【０５３０】
であり、またcはaまたはbに等しい。したがって、本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ602および604で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０５３１】
703.アドレステーブルに基づくFFTを使用して前回転データに対してN/4点のDFTを実行する。
【０５３２】
M=N/4=P×Qで、PおよびQが互いに素である場合、本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ603のデータ処理方法を使用してこのステップを実行することができる。
【０５３３】
704.変換の後のデータを、回転因子
【０５３４】
【数１７５】
【０５３５】
および正規化因子Bを使用することによって後回転する。
【０５３６】
変換されたデータは、回転因子
【０５３７】
【数１７６】
【０５３８】
、n=0,...,N/4-1を使用することによって後回転されるが、式中、
【０５３９】
【数１７７】
【０５４０】
であり、dは定数である。上記の処理の後得られるデータynは、
【０５４１】
【数１７８】
【０５４２】
である。
【０５４３】
Bは、正規化因子であり、定数である。
【０５４４】
この実施形態では、
【０５４５】
【数１７９】
【０５４６】
であり、またdはa、b、またはcに等しい。したがって、本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ602および604で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０５４７】
705.後回転データに窓関数を掛けてひねりを施し、時間領域データを取得する。
【０５４８】
窓関数を掛けて、ひねりを施した後、出力データ
【０５４９】
【数１８０】
【０５５０】
が得られ、これは、
【０５５１】
【数１８１】
【０５５２】
であり、
式中、
【０５５３】
【数１８２】
【０５５４】
n=0,...,N/4-1であり、gnは、解析窓hnと一緒に完全な再構成条件を満たす、合成窓である、つまり、hngn+hn+N/2gn+N/2=1 n=0,...,N-N/2-1である。mnは前のフレームのバッファリングされたデータであり、mnの更新は、
【０５５５】
【数１８３】
【０５５６】
を満たす。
【０５５７】
従来技術では、互いに素な因子に基づく大半のDFTでは、データ列の順次アクセスを考慮しない。変換を通して得られたデータは、最終的な出力データを得るために再配列する必要がある。したがって、計算量が増大する。本発明の実施形態では、FFTにアドレステーブルが使用され、アドレッシングはアドレステーブルに基づき、入力データはこのアドレステーブル内の関連付けられているアドレスに従って読み込まれ、出力データはアドレステーブル内の関連付けられているアドレスに従って格納される。したがって、変換の後に得られたデータの列は、特別な再配列なしで使用可能である。
【０５５８】
本発明の一実施形態において提供されるデータ処理方法は、以下のステップを含む。
【０５５９】
1.アドレステーブルを作成する。
【０５６０】
2.アドレステーブルに基づき入力データに対してQ回にわたってP点DFTを実行する。
【０５６１】
3.アドレステーブルに基づきQ回にわたってP点DFTを実行した後に得られたデータに対してP回にわたってQ点DFTを実行する。
【０５６２】
PおよびQは、互いに素な正整数であり、Mは、アドレステーブルの長さであり、M=P×Qであり、アドレステーブルに格納されているアドレスは、0,1,...,M-1と横断して、入力データとの1対1マッピングを形成する。
【０５６３】
実際、アドレステーブルは、複数のアプローチで得ることができる。この実施形態では、アドレステーブルは、式<K1×n1+K2×n2>Mを使用することによって得られる。
【０５６４】
アドレステーブルI=<K1xn1+K2xn2>M、n1=0,...,P-1、n2=0,...,Q-1であり、K1およびK2は、<K1K2>M=0を満たす互いに素な正整数である。<Z>Mは法Mに関するZの剰余を意味する。
【０５６５】
アドレステーブルが1対1マッピングの条件を満たす場合、以下の3つの条件が満たされる必要がある。
【０５６６】
(1)K1はQの正整数倍であり、および/またはK2はPの正整数倍である。
【０５６７】
(2)K1およびPは、互いに素な数である。
【０５６８】
(3)K2およびQは、互いに素な数である。
【０５６９】
この実施形態のデータ処理方法は、M=P×Qとし、PおよびQを互いに素な正整数としてFFTに適用可能である。P=64、Q=5とし、PおよびQが互いに素である320点FFTを例にとり、この実施形態において提供されるデータ処理方法の流れ図を図2に示した。この方法は、以下のステップを含む。
【０５７０】
1031.アドレステーブルIを作成する。
【０５７１】
アドレステーブルIは
I=<K1×n1+K2×n2>M n1=0,...,P-1
n2=0,...,Q-1
を満たす。
【０５７２】
K1およびK2は、<K1K2>M=0を満たす互いに素な正整数である。<Z>Mは法Mに関するZの剰余を意味する。
【０５７３】
この実施形態では、K1=5、K1=64であり、アドレステーブルIは、
I=<5n1+64n2>320
で表すことができ、式中、n1=0,...,63およびn2=0,...,4である。
【０５７４】
アドレステーブルIは、予め計算され格納されうる。実際、アドレステーブルIは、テーブルに格納することができる。この実施形態では、テーブルは、I[n1][n2]の二次元配列として格納される。
【０５７５】
1032.アドレステーブルIに従って入力データに対してQ回にわたってP点DFTを実行する。
【０５７６】
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=i、n1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のP点DFTの結果をxのステップの循環シフトで適用する。
【０５７７】
ここでは、xは、法Pに関する
【０５７８】
【数１８４】
【０５７９】
の巡回剰余の逆数であり、
【０５８０】
【数１８５】
【０５８１】
を満たす。
【０５８２】
例えば、アドレステーブルIがI[n1][n2]の二次元配列の形式で格納される場合、i番目のP点DFTの入力データは、アドレステーブルI[n1][i]、n1=0,...,P-1に格納されているP個のアドレスインデックスに関連付けられているデータである。それぞれのP点DFTの結果は、xのステップの循環シフトで適用される。この実施形態では、K1=5、P=64、およびQ=5、x=13だからである。
【０５８３】
1033.アドレステーブルIに従って変換データに対してP回にわたってQ点DFTを実行する。
【０５８４】
i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=i、n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のQ点DFTの結果をyのステップの循環シフトで適用する。
【０５８５】
ここでは、yは、法Qに関する
【０５８６】
【数１８６】
【０５８７】
の巡回剰余の逆数であり、
【０５８８】
【数１８７】
【０５８９】
を満たす。
【０５９０】
例えば、アドレステーブルIがI[n1][n2]の二次元配列の形式で格納される場合、i番目のQ点DFTの入力データは、アドレステーブルI[n1][n2]、n2=0,...,Q-1に格納されているQ個のアドレスインデックスに関連付けられているデータである。それぞれのQ点DFTの結果は、yのステップの循環シフトで適用される。この実施形態では、K2=64、P=64、およびQ=5、x=4だからである。
【０５９１】
本発明の実施形態において提供されるデータ処理方法では、DFTが実行されるときに、アドレステーブルがアドレッシングに使用されるので、入力データはアドレステーブル内の関連付けられているアドレスに従って読み込まれ、出力データはアドレステーブル内の関連付けられているアドレスに従って格納される。変換データは、使用可能な列になっており、逆変換の際に特別な再配列は不要である。したがって、計算におけるアドレッシングコストは低減され、計算効率が増大する。
【０５９２】
当業者は、先行する実施形態における一部または全部のステップが、1つのプログラムの命令に従う関係するハードウェアによって実行されうることを理解する。プログラムは、コンピュータ可読記憶媒体に格納することができる。プログラムの実行は、以下のステップを含む。
【０５９３】
時間領域から周波数領域への信号処理方法は、
時間領域データを前処理するステップと、
前処理されたデータを、回転因子
【０５９４】
【数１８８】
【０５９５】
を使用することによって前回転するステップと、
前回転データに対してN/4点のDFTを実行するステップと、
DFTの後のデータを、回転因子
【０５９６】
【数１８９】
【０５９７】
を使用することによって後回転し、周波数領域データを取得するステップとを含み、
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、
【０５９８】
【数１９０】
【０５９９】
である。
【０６００】
周波数領域から時間領域への信号処理方法は、
周波数領域データにひねりを施すステップと、
ひねりを施したデータを、回転因子
【０６０１】
【数１９１】
【０６０２】
を使用することによって前回転するステップと、
前回転データに対してN/4点のDFTを実行するステップと、
DFTの後のデータを、回転因子
【０６０３】
【数１９２】
【０６０４】
を使用することによって後回転するステップと、
後回転データを後処理して、時間領域データを取得するステップとを含み、
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、
【０６０５】
【数１９３】
【０６０６】
である。
【０６０７】
データ処理方法は、
アドレステーブルに従って入力データに対してQ回にわたってP点DFTを実行するステップと、
アドレステーブルに従ってQ回にわたってP点DFTを実行した後に得られたデータに対してP回にわたってQ点DFTを実行するステップとを含む。
【０６０８】
上述の記憶媒体は、読み出し専用メモリ(ROM)、磁気ディスク、またはコンパクトディスクであってよい。
【０６０９】
図8は、本発明の一実施形態における時間領域から周波数領域への信号処理装置の構造を示す図である。この装置は、
時間領域データを前処理するように適合された前処理ユニット801と、
回転因子
【０６１０】
【数１９４】
【０６１１】
を使用することによって、前処理ユニット801により得られたデータを前回転するように適合された第1の前回転ユニット802と、
第1の前回転ユニット802によって処理されたデータに対してN/4点のDFTを実行するように適合された第1のフーリエ変換ユニット803と、
第1のフーリエ変換ユニット803によってDFTが実行された後にデータを後回転して周波数領域データを取得するように適合された第1の後回転ユニット804とを備え、
aおよびbは定数であり、Nは時間領域データの長さであり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０６１２】
【数１９５】
【０６１３】
である。
【０６１４】
第1の後回転ユニット804は、
DFTが実行された後のデータを、回転因子
【０６１５】
【数１９６】
【０６１６】
および正規化因子Aを使用することによって後回転し、周波数領域データを取得するように適合された第2の後回転ユニットを備える。
【０６１７】
第1のフーリエ変換ユニット803は、
アドレステーブルに従って第1の前回転ユニットによって処理されたデータに対してQ回にわたってP点DFTを実行するように適合された第1の変換ユニットと、
アドレステーブルに従って第1の変換ユニットによって変換されたデータに対してP回にわたってQ点DFTを実行するように適合された第2の変換ユニットとを備える。
【０６１８】
PおよびQは、互いに素な正整数であり、M=N/4=P×Qである。Mは、アドレステーブルの長さである。アドレステーブルは<K1×n1+K2×n2>Mであり、ただし、n1=0,...,P-1およびn2=1,...,Q-1である。K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす。<Z>Mは法Mに関するZの剰余を意味する。
【０６１９】
本発明の実施形態において提供される時間領域から周波数領域への信号処理装置に従って、周波数領域から時間領域への信号処理装置が本発明の一実施形態において提供される。図9は、周波数領域から時間領域への信号処理装置の構造を示している。この装置は、
周波数領域データにひねりを施すように適合されたひねり処理ユニット901と、
回転因子
【０６２０】
【数１９７】
【０６２１】
を使用することによって、ひねり処理ユニット901により得られたデータを前回転するように適合された第2の前回転ユニット902と、
第2の前回転ユニット902によって処理されたデータに対してN/4点のDFTを実行するように適合された第2のフーリエ変換ユニット903と、
第2のフーリエ変換ユニット903によってDFTが実行された後にデータを後回転するように適合された第3の後回転ユニット904と、
第3の後回転ユニット904によって処理されたデータを後処理して時間領域データを取得するように適合された後処理ユニット905とを備え、
cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０６２２】
【数１９８】
【０６２３】
である。
【０６２４】
第3の後回転ユニット904は、
DFTが実行された後のデータを、回転因子
【０６２５】
【数１９９】
【０６２６】
および正規化因子Bを使用することによって後回転するように適合された第4の後回転ユニットを備える。
【０６２７】
第2のフーリエ変換ユニット903は、
アドレステーブルに従って第2の前回転ユニットによって処理されたデータに対してQ回にわたってP点DFTを実行するように適合された第3の変換ユニットと、
アドレステーブルに従って第3の変換ユニットによって変換されたデータに対してP回にわたってQ点DFTを実行するように適合された第4の変換ユニットとを備える。
【０６２８】
PおよびQは、互いに素な正整数であり、M=N/4=P×Qである。Mは、アドレステーブルの長さである。アドレステーブルは<K1×n1+K2×n2>Mであり、ただし、n1=0,...,P-1およびn2=1,...,Q-1である。K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす。<Z>Mは法Mに関するZの剰余を意味する。
【０６２９】
本発明の実施形態において提供される時間領域から周波数領域への信号処理装置および周波数領域から時間領域への信号処理装置の特定の応用に関しては、本発明の実施形態において提供される信号処理方法の説明を参照されたい。
【０６３０】
本発明の実施形態において提供される時間領域から周波数領域への信号処理装置および周波数領域から時間領域への信号処理方法において、回転因子中の
【０６３１】
【数２００】
【０６３２】
は
【０６３３】
【数２０１】
【０６３４】
に展開することができ、しかも条件
【０６３５】
【数２０２】
【０６３６】
および
【０６３７】
【数２０３】
【０６３８】
を満たし、回転因子中の
【０６３９】
【数２０４】
【０６４０】
は同じ対称条件を満たすので、本発明の実施形態において提供される時間領域から周波数領域への信号処理装置および周波数領域から時間領域への信号処理装置はN/4点のデータテーブルを格納するだけでよい。従来技術と比較すると、少なくともN/4点のサインテーブルおよびN/4点のコサインテーブルは、合わせてN/2個の点について、格納する必要がある場合、本発明の実施形態は、格納の複雑さおよび記憶容量を著しく低減し、ストレージリソースの消費を減らし、信号処理の効率を高める。
【０６４１】
本発明の一実施形態において提供されるデータ処理装置では、出力データの使用可能な列を保証し、アドレッシングコストを低減するために、アドレッシングにアドレステーブルを使用する。図10は、この実施形態において提供されるデータ処理装置の構造を示している。装置は、アドレステーブルユニット1001、第5の変換ユニット1002、および第6の変換ユニット1003を備える。
【０６４２】
アドレステーブルユニット1001は、アドレステーブルを作成するか、または格納するように適合される。
【０６４３】
アドレステーブルに格納されているアドレスは、0,1,...,M-1と横断して、入力データとの1対1マッピングを形成する。
【０６４４】
実際、アドレステーブルは、複数のアプローチで得ることができる。この実施形態では、アドレステーブルは、式<K1×n1+K2×n2>Mを使用することによって得られる。
【０６４５】
アドレステーブルはI=<K1×n1+K2×n2>Mであるが、式中、n1=0,...,P-1、n2=0,...,Q-1であり、PおよびQは、互いに素な正整数であり、M=P×Qであり、K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす。<Z>Mは法Mに関するZの剰余を意味する。
【０６４６】
アドレステーブルが1対1マッピングの条件を満たす場合、以下の3つの条件が満たされる必要がある。
【０６４７】
(1)K1はQの正整数倍であり、および/またはK2はPの正整数倍である。
【０６４８】
(2)K1およびPは、互いに素な数である。
【０６４９】
(3)K2およびQは、互いに素な数である。
【０６５０】
第5の変換ユニット1002は、アドレステーブルユニット1001によって作成されるか、または格納されているアドレステーブルに従って入力データに対しQ回にわたってP点DFTを実行するように適合されている。
【０６５１】
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=i、n1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のP点DFTの結果をxのステップの循環シフトで適用する。
【０６５２】
ここでは、xは、法Pに関する
【０６５３】
【数２０５】
【０６５４】
の巡回剰余の逆数であり、
【０６５５】
【数２０６】
【０６５６】
を満たす。
【０６５７】
例えば、アドレステーブルIがI[n1][n2]の二次元配列の形式で格納される場合、i番目のP点DFTの入力データは、アドレステーブルI[n1][n2]、n1=0,...,P-1に格納されているP個のアドレスインデックスに関連付けられているデータである。それぞれのP点DFTの結果は、xのステップの循環シフトで適用される。
【０６５８】
第6の変換ユニット1003は、アドレステーブルユニット1001によって作成されるか、または格納されているアドレステーブルに従って第5の変換ユニット1002によって変換されたデータに対しP回にわたってQ点DFTを実行するように適合されている。
【０６５９】
i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=i、n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のQ点DFTの結果をyのステップの循環シフトで適用する。
【０６６０】
ここでは、yは、法Qに関する
【０６６１】
【数２０７】
【０６６２】
の巡回剰余の逆数であり、
【０６６３】
【数２０８】
【０６６４】
を満たす。
【０６６５】
例えば、アドレステーブルIがI[n1][n2]の二次元配列の形式で格納される場合、i番目のQ点DFTの入力データは、アドレステーブルI[n1][n2]、n2=0,...,Q-1に格納されているQ個のアドレスインデックスに関連付けられているデータである。それぞれのQ点DFTの結果は、yのステップの循環シフトで適用される。
【０６６６】
本発明の実施形態において提供されるデータ処理装置では、FFTが実行されるときに、アドレステーブルがアドレッシングに使用されるので、入力データはアドレステーブル内の関連付けられているアドレスに従って読み込まれ、出力データはアドレステーブル内の関連付けられているアドレスに従って格納される。変換データは、使用可能な列になっており、逆変換の際に特別な再配列は不要である。したがって、計算におけるアドレッシングコストは低減され、計算効率が増大する。
【０６６７】
以下では、アドレステーブルIに基づく変換が、出力データの使用可能な列を保証することを証明する。
【０６６８】
FFTの定義は、
【０６６９】
【数２０９】
【０６７０】
である。
【０６７１】
M=P×Qであり、PおよびQは、互いに素な正整数であり、もし
n=<K1×n1+K2×n2>M n1=0,...,P-1,
n2=0,...,Q-1
k=<K1×k1+K2×k2>M k1=0,...,P-1
k2=0,...,Q-1
ならば、
X(k)はX'(k1,k2)およびX'(k1,k2)=X(<K1×k1+K2×k2>M)と書くことができ、x(n)はx'(n1,n2)およびx'(n1,n2)=X(<K1×n1+K2×n2>M)と書くことができる。
【０６７２】
したがって、FFTの公式は、
【０６７３】
【数２１０】
【０６７４】
に展開することができる。
【０６７５】
<K1K2>M=0の場合
【０６７６】
【数２１１】
【０６７７】
であり、したがって
【０６７８】
【数２１２】
【０６７９】
である。
【０６８０】
なぜなら、
【０６８１】
【数２１３】
【０６８２】
だからである。
【０６８３】
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=i、n1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のP点DFTの結果をxのステップの循環シフトで適用する。
【０６８４】
ここでは、xは、法Pに関する
【０６８５】
【数２１４】
【０６８６】
の巡回剰余の逆数であり、
【０６８７】
【数２１５】
【０６８８】
【数２１６】
【０６８９】
を満たす。n1=0のときに、
【０６９０】
【数２１７】
【０６９１】
であり、n1=1のときに
【０６９２】
【数２１８】
【０６９３】
であり、同様に、n1=xのときに
【０６９４】
【数２１９】
【０６９５】
である。順次出力のFFTの式
【０６９６】
【数２２０】
【０６９７】
では、n1=1のときの回転因子は
【０６９８】
【数２２１】
【０６９９】
である。P点DFTでは、
【０７００】
【数２２２】
【０７０１】
となるのは、n1=xのとき、xが
【０７０２】
【数２２３】
【０７０３】
を満たすときに限る。P点DFTの順次出力を使用可能にするために、xのステップの循環シフトを、n1=0,...,P-1に対応する出力に対して実行する必要がある。
【０７０４】
同様に、i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=i、n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のQ点DFTの結果をyのステップの循環シフトで適用する。
【０７０５】
ここでは、yは、法Qに関する
【０７０６】
【数２２４】
【０７０７】
の巡回剰余の逆数であり、
【０７０８】
【数２２５】
【０７０９】
を満たす。
【０７１０】
本発明は、例示的な実施形態を通じて説明されているけれども、本発明はそのような実施形態に限定されない。当業者であれば本発明の精神および範囲から逸脱することなく、本発明に対しさまざまな修正および変更を加えることができることは、明らかである。請求項およびその等価物により定義された保護の範囲内にある限りそれらの修正および変更も、本発明の対象範囲であることが意図されている。
【符号の説明】
【０７１１】
801 前処理ユニット
802 第1の前回転ユニット
803 第1のフーリエ変換ユニット
804 第1の後回転ユニット
901 ひねり処理ユニット
902 第2の前回転ユニット
903 第2のフーリエ変換ユニット
904 第3の後回転ユニット
905 後処理ユニット
1001 アドレステーブルユニット
1002 第5の変換ユニット
1003 第6の変換ユニット
【特許請求の範囲】
【請求項１】
時間領域から周波数領域への信号処理方法であって、
時間領域データを前処理するステップと、
前記前処理されたデータを、回転因子
【数１】
を使用することによって前回転するステップと、
前記前回転データに対してN/4点の離散フーリエ変換(DFT)を実行するステップと、
前記DFTによって変換された前記データを、回転因子
【数２】
を使用することによって後回転し、周波数領域データを取得するステップとを含み、式中、
aおよびbは定数であり、Nは時間領域データの長さであり、式
【数３】
が成り立ち、式
【数４】
が成り立ち、式
【数５】
が成り立ち、nおよびkはそれぞれすべてN/4以下の非負整数である時間領域から周波数領域への信号処理方法。
【請求項２】
前記前回転データに対してN/4点の前記DFTを実行する前記ステップは、
アドレステーブルに基づき前記前回転データに対しQ回にわたってP点DFTを実行するステップと、
前記アドレステーブルに基づきQ回にわたって前記P点DFTの後に得られた前記データに対しP回にわたってQ点DFTを実行するステップとを含み、式中、
PおよびQは、互いに素な正整数であり、M=N/4=P×Qであり、Mは、前記アドレステーブルの長さであり、前記アドレステーブルは、<K1×n1+K2×n2>Mであり、ただし、n1=0,...,P-1およびn2=1,...,Q-1であり、K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす請求項1に記載の方法。
【請求項３】
前記アドレステーブルは、配列の形式で1つのテーブル内に格納される請求項2に記載の方法。
【請求項４】
前記前処理ステップは、窓関数を掛けてひねりを施すか、またはひねりを施すステップを含む請求項1、2、または3に記載の方法。
【請求項５】
周波数領域から時間領域への信号処理方法であって、
周波数領域データにひねりを施すステップと、
前記ひねりを施したデータを、回転因子
【数６】
を使用することによって前回転するステップと、
前記前回転データに対してN/4点の離散フーリエ変換(DFT)を実行するステップと、
前記DFTによって変換された前記データを、回転因子
【数７】
を使用することによって後回転するステップと、
前記後回転データを後処理して、時間領域データを取得するステップとを含み、式中、
cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、式
【数８】
が成り立ち、式
【数９】
が成り立ち、式
【数１０】
が成り立ち、nおよびkはそれぞれすべてN/4以下の非負整数である周波数領域から時間領域への信号処理方法。
【請求項６】
前記前回転データに対してN/4点の前記DFTを実行する前記ステップは、
アドレステーブルに従って前記前回転データに対しQ回にわたってP点DFTを実行するステップと、
前記アドレステーブルに従ってQ回にわたって前記P点DFTの後に得られた前記データに対してP回にわたってQ点DFTを実行するステップとを含み、式中、
PおよびQは、互いに素な正整数であり、M=N/4=P×Qであり、Mは、前記アドレステーブルの長さであり、前記アドレステーブルは、<K1×n1+K2×n2>Mであり、ただし、n1=0,...,P-1およびn2=1,...,Q-1であり、K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす請求項5記載の方法。
【請求項７】
前記アドレステーブルは、配列の形式で1つのテーブル内に格納される請求項6に記載の方法。
【請求項８】
前記後処理ステップは、窓関数を掛けてひねりを施すか、またはひねりを施すステップを含む請求項6または7に記載の方法。
【請求項９】
データ処理方法であって、
アドレステーブルに基づきデータに対しQ回にわたってP点離散フーリエ変換(DFT)を実行するステップと、
前記アドレステーブルに基づきQ回にわたって前記P点DFTの後に得られた前記データに対しP回にわたってQ点DFTを実行するステップとを含むデータ処理方法。
【請求項１０】
PおよびQは、互いに素な正整数であり、前記アドレステーブルはI=<K1×n1+K2×n2>Mであり、ただし、Mは、前記アドレステーブルの長さであり、M=P×Q、n1=0,...,P-1、n2=0,...,Q-1であり、K1およびK2は、<K1K2>M=0を満たす互いに素な正整数である請求項9に記載の方法。
【請求項１１】
前記アドレステーブルは、配列の形式で1つのテーブル内に格納される請求項9または10に記載の方法。
【請求項１２】
時間領域から周波数領域への信号処理装置であって、
時間領域データを前処理するように適合された前処理ユニットと、
回転因子
【数１１】
を使用することによって、前記前処理ユニットにより得られた前記データを前回転するように適合された第1の前回転ユニットと、
前記第1の前回転ユニットによって処理された前記データに対してN/4点の離散フーリエ変換(DFT)を実行するように適合された第1のフーリエ変換ユニットと、
回転因子
【数１２】
を使用することによって前記第1のフーリエ変換ユニットにより変換された前記データを後回転して周波数領域データを取得するように適合された第1の後回転ユニットとを備え、式中、
【数１３】
、
【数１４】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である時間領域から周波数領域への信号処理装置。
【請求項１３】
前記第1のフーリエ変換ユニットは、
アドレステーブルに基づき前記第1の前回転ユニットによって処理された前記データに対しQ回にわたってP点DFTを実行するように適合された第1の変換ユニットと、
前記アドレステーブルに基づき前記第1の変換ユニットによって変換された前記データに対しP回にわたってQ点DFTを実行するように適合された第2の変換ユニットとを備える請求項12に記載の装置。
【請求項１４】
周波数領域から時間領域への信号処理装置であって、
周波数領域データにひねりを施すように適合されたひねり処理ユニットと、
回転因子
【数１５】
を使用することによって、前記ひねり処理ユニットにより得られた前記データを前回転するように適合された第2の前回転ユニットと、
前記第2の前回転ユニットによって処理された前記データに対してN/4点の離散フーリエ変換(DFT)を実行するように適合された第2のフーリエ変換ユニットと、
回転因子
【数１６】
を使用することによって、前記第2のフーリエ変換ユニットにより得られた前記データを後回転するように適合された第3の後回転ユニットと、
前記第3の後回転ユニットによって処理された前記データを後処理して時間領域データを取得するように適合された後処理ユニットとを備え、式中、
【数１７】
、
【数１８】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である周波数領域から時間領域への信号処理装置。
【請求項１５】
前記第2のフーリエ変換ユニットは、
アドレステーブルに基づき前記第2の前回転ユニットによって処理された前記データに対しQ回にわたってP点DFTを実行するように適合された第3の変換ユニットと、
前記アドレステーブルに基づき前記第3の変換ユニットによって変換された前記データに対しP回にわたってQ点DFTを実行するように適合された第4の変換ユニットとを備える請求項14に記載の装置。
【請求項１６】
データ処理方法であって、
アドレステーブルを作成するか、または格納するように適合されたアドレステーブルユニットと、
前記アドレステーブルユニットによって作成されるか、または格納されている前記アドレステーブルに基づき前記データに対しQ回にわたってP点離散フーリエ変換(DFT)を実行するように適合された第5の変換ユニットと、
前記アドレステーブルユニットによって作成されるか、または格納されている前記アドレステーブルに基づき前記第5の変換ユニットによって変換された前記データに対しP回にわたってQ点DFTを実行するように適合された第6の変換ユニットとを備えるデータ処理方法。
【請求項１】
時間領域から周波数領域への信号処理方法であって、
時間領域データを前処理するステップと、
前記前処理されたデータを、回転因子
【数１】
を使用することによって前回転するステップと、
前記前回転データに対してN/4点の離散フーリエ変換(DFT)を実行するステップと、
前記DFTによって変換された前記データを、回転因子
【数２】
を使用することによって後回転し、周波数領域データを取得するステップとを含み、式中、
aおよびbは定数であり、Nは時間領域データの長さであり、式
【数３】
が成り立ち、式
【数４】
が成り立ち、式
【数５】
が成り立ち、nおよびkはそれぞれすべてN/4以下の非負整数である時間領域から周波数領域への信号処理方法。
【請求項２】
前記前回転データに対してN/4点の前記DFTを実行する前記ステップは、
アドレステーブルに基づき前記前回転データに対しQ回にわたってP点DFTを実行するステップと、
前記アドレステーブルに基づきQ回にわたって前記P点DFTの後に得られた前記データに対しP回にわたってQ点DFTを実行するステップとを含み、式中、
PおよびQは、互いに素な正整数であり、M=N/4=P×Qであり、Mは、前記アドレステーブルの長さであり、前記アドレステーブルは、<K1×n1+K2×n2>Mであり、ただし、n1=0,...,P-1およびn2=1,...,Q-1であり、K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす請求項1に記載の方法。
【請求項３】
前記アドレステーブルは、配列の形式で1つのテーブル内に格納される請求項2に記載の方法。
【請求項４】
前記前処理ステップは、窓関数を掛けてひねりを施すか、またはひねりを施すステップを含む請求項1、2、または3に記載の方法。
【請求項５】
周波数領域から時間領域への信号処理方法であって、
周波数領域データにひねりを施すステップと、
前記ひねりを施したデータを、回転因子
【数６】
を使用することによって前回転するステップと、
前記前回転データに対してN/4点の離散フーリエ変換(DFT)を実行するステップと、
前記DFTによって変換された前記データを、回転因子
【数７】
を使用することによって後回転するステップと、
前記後回転データを後処理して、時間領域データを取得するステップとを含み、式中、
cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、式
【数８】
が成り立ち、式
【数９】
が成り立ち、式
【数１０】
が成り立ち、nおよびkはそれぞれすべてN/4以下の非負整数である周波数領域から時間領域への信号処理方法。
【請求項６】
前記前回転データに対してN/4点の前記DFTを実行する前記ステップは、
アドレステーブルに従って前記前回転データに対しQ回にわたってP点DFTを実行するステップと、
前記アドレステーブルに従ってQ回にわたって前記P点DFTの後に得られた前記データに対してP回にわたってQ点DFTを実行するステップとを含み、式中、
PおよびQは、互いに素な正整数であり、M=N/4=P×Qであり、Mは、前記アドレステーブルの長さであり、前記アドレステーブルは、<K1×n1+K2×n2>Mであり、ただし、n1=0,...,P-1およびn2=1,...,Q-1であり、K1およびK2は、互いに素な正整数であり、<K1K2>M=0を満たす請求項5記載の方法。
【請求項７】
前記アドレステーブルは、配列の形式で1つのテーブル内に格納される請求項6に記載の方法。
【請求項８】
前記後処理ステップは、窓関数を掛けてひねりを施すか、またはひねりを施すステップを含む請求項6または7に記載の方法。
【請求項９】
データ処理方法であって、
アドレステーブルに基づきデータに対しQ回にわたってP点離散フーリエ変換(DFT)を実行するステップと、
前記アドレステーブルに基づきQ回にわたって前記P点DFTの後に得られた前記データに対しP回にわたってQ点DFTを実行するステップとを含むデータ処理方法。
【請求項１０】
PおよびQは、互いに素な正整数であり、前記アドレステーブルはI=<K1×n1+K2×n2>Mであり、ただし、Mは、前記アドレステーブルの長さであり、M=P×Q、n1=0,...,P-1、n2=0,...,Q-1であり、K1およびK2は、<K1K2>M=0を満たす互いに素な正整数である請求項9に記載の方法。
【請求項１１】
前記アドレステーブルは、配列の形式で1つのテーブル内に格納される請求項9または10に記載の方法。
【請求項１２】
時間領域から周波数領域への信号処理装置であって、
時間領域データを前処理するように適合された前処理ユニットと、
回転因子
【数１１】
を使用することによって、前記前処理ユニットにより得られた前記データを前回転するように適合された第1の前回転ユニットと、
前記第1の前回転ユニットによって処理された前記データに対してN/4点の離散フーリエ変換(DFT)を実行するように適合された第1のフーリエ変換ユニットと、
回転因子
【数１２】
を使用することによって前記第1のフーリエ変換ユニットにより変換された前記データを後回転して周波数領域データを取得するように適合された第1の後回転ユニットとを備え、式中、
【数１３】
、
【数１４】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である時間領域から周波数領域への信号処理装置。
【請求項１３】
前記第1のフーリエ変換ユニットは、
アドレステーブルに基づき前記第1の前回転ユニットによって処理された前記データに対しQ回にわたってP点DFTを実行するように適合された第1の変換ユニットと、
前記アドレステーブルに基づき前記第1の変換ユニットによって変換された前記データに対しP回にわたってQ点DFTを実行するように適合された第2の変換ユニットとを備える請求項12に記載の装置。
【請求項１４】
周波数領域から時間領域への信号処理装置であって、
周波数領域データにひねりを施すように適合されたひねり処理ユニットと、
回転因子
【数１５】
を使用することによって、前記ひねり処理ユニットにより得られた前記データを前回転するように適合された第2の前回転ユニットと、
前記第2の前回転ユニットによって処理された前記データに対してN/4点の離散フーリエ変換(DFT)を実行するように適合された第2のフーリエ変換ユニットと、
回転因子
【数１６】
を使用することによって、前記第2のフーリエ変換ユニットにより得られた前記データを後回転するように適合された第3の後回転ユニットと、
前記第3の後回転ユニットによって処理された前記データを後処理して時間領域データを取得するように適合された後処理ユニットとを備え、式中、
【数１７】
、
【数１８】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である周波数領域から時間領域への信号処理装置。
【請求項１５】
前記第2のフーリエ変換ユニットは、
アドレステーブルに基づき前記第2の前回転ユニットによって処理された前記データに対しQ回にわたってP点DFTを実行するように適合された第3の変換ユニットと、
前記アドレステーブルに基づき前記第3の変換ユニットによって変換された前記データに対しP回にわたってQ点DFTを実行するように適合された第4の変換ユニットとを備える請求項14に記載の装置。
【請求項１６】
データ処理方法であって、
アドレステーブルを作成するか、または格納するように適合されたアドレステーブルユニットと、
前記アドレステーブルユニットによって作成されるか、または格納されている前記アドレステーブルに基づき前記データに対しQ回にわたってP点離散フーリエ変換(DFT)を実行するように適合された第5の変換ユニットと、
前記アドレステーブルユニットによって作成されるか、または格納されている前記アドレステーブルに基づき前記第5の変換ユニットによって変換された前記データに対しP回にわたってQ点DFTを実行するように適合された第6の変換ユニットとを備えるデータ処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公表番号】特表２０１２−５２７７０８（Ｐ２０１２−５２７７０８Ａ）
【公表日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願番号】特願２０１２−５１２１８４（Ｐ２０１２−５１２１８４）
【出願日】平成２２年４月２２日（２０１０．４．２２）
【国際出願番号】ＰＣＴ／ＣＮ２０１０／０７２０２９
【国際公開番号】ＷＯ２０１０／１４８７４３
【国際公開日】平成２２年１２月２９日（２０１０．１２．２９）
【出願人】（５０４２７７３８８）▲ホア▼▲ウェイ▼技術有限公司 (220)
【Ｆターム（参考）】
【公表日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願日】平成２２年４月２２日（２０１０．４．２２）
【国際出願番号】ＰＣＴ／ＣＮ２０１０／０７２０２９
【国際公開番号】ＷＯ２０１０／１４８７４３
【国際公開日】平成２２年１２月２９日（２０１０．１２．２９）
【出願人】（５０４２７７３８８）▲ホア▼▲ウェイ▼技術有限公司 (220)
【Ｆターム（参考）】
[ Back to top ]