(57)【特許請求の範囲】
【請求項１】
データ処理方法であって、
デジタル信号プロセッサが、アドレステーブルに基づきデータに対し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を満たす互いに素な正整数であり、
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=iおよびn1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータであり、
前記デジタル信号プロセッサが、アドレステーブルに基づきデータに対しQ回にわたってP点離散フーリエ変換(DFT)を実行するステップは、最終出力を得るために、xのステップの循環シフトをi番目のP点DFTの結果に適用するステップを具備し、
xは、法Pに関する
【数１】
0005708720.tif 000227
の巡回剰余の逆数であり、
【数２】
0005708720.tif 000228
を満たし、
i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=I, n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータであり、
前記デジタル信号プロセッサが、アドレステーブルに基づきQ回にわたって前記P点DFTの後に得られた前記データに対しP回にわたってQ点DFTを実行する前記ステップは、最終出力を得るために、yのステップの循環シフトをi番目のQ点DFTの結果に適用するステップを具備し、
yは、法Qに関する
【数３】
0005708720.tif 000229
の巡回剰余の逆数であり、
【数４】
0005708720.tif 000230
を満たすことを特徴とするデータ処理方法。
【請求項２】
前記アドレステーブルは、配列の形式で1つのテーブル内に格納されることを特徴とする請求項1に記載の方法。
【請求項３】
データ処理装置であって、
アドレステーブルを作成するか、または格納するように構成されたアドレステーブルユニットと、
前記アドレステーブルユニットによって作成されるか、または格納されている前記アドレステーブルに基づきデータに対しQ回にわたってP点離散フーリエ変換(DFT)を実行するように構成された第1変換ユニットと、
前記アドレステーブルユニットによって作成されるか、または格納されている前記アドレステーブルに基づき前記第1変換ユニットによって変換された前記データに対しP回にわたってQ点DFTを実行するように構成された第2変換ユニットと、
を備え、
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を満たす互いに素な正整数であり、
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=iおよびn1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータであり、
前記アドレステーブルに基づきデータに対しQ回にわたってP点離散フーリエ変換(DFT)を実行することは、最終出力を得るために、xのステップの循環シフトをi番目のP点DFTの結果に適用することを含み、
xは、法Pに関する
【数５】
0005708720.tif 000231
の巡回剰余の逆数であり、
【数６】
0005708720.tif 000232
を満たし、
i番目(i=0,...,P-1)のQ点DFTの入力データは、アドレステーブルI内のn1=I, n2=0,...,Q-1に対応するQ個のアドレスインデックスに関連付けられているデータであり、
前記アドレステーブルに基づきQ回にわたって前記P点DFTの後に得られた前記データに対しP回にわたってQ点DFTを実行することは、最終出力を得るために、yのステップの循環シフトをi番目のQ点DFTの結果に適用することを含み、
yは、法Qに関する
【数７】
0005708720.tif 000233
の巡回剰余の逆数であり、
【数８】
0005708720.tif 000234
を満たすことを特徴とするデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル信号処理技術に関するものであり、特に、信号処理方法ならびにデータ処理の方法および装置に関するものである。
【０００２】
本出願は、参照により本明細書に組み込まれている、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が大きい場合、追加ストレージの容量が大きくなり、したがって、多くのストレージリソースが消費され、変換効率が影響を受ける。
【００１０】
互いに素な因数に基づく高速フーリエ変換アルゴリズムが採用された場合、多数のアドレッシング演算が必要になり、このアルゴリズムは、データ列のシーケンシャルアクセスを考慮しない。変換を通して得られたデータは、最終的な出力データを得るために再配列する必要がある。したがって、計算量がさらに多くなる。
【発明の概要】
【課題を解決するための手段】
【００１１】
本発明の実施形態は、信号処理の効率の改善を支援するための信号処理方法ならびにデータ処理の方法および装置を実現する。
【００１２】
時間領域から周波数領域への信号処理方法は、
時間領域データを前処理するステップと、
前処理されたデータを、回転因子
【００１３】
【数１】
0005708720.tif 000002
【００１４】
を使用することによって前回転するステップと、
前回転データに対してN/4点の離散フーリエ変換(DFT)を実行するステップと、
DFTによって変換されたデータを、回転因子
【００１５】
【数２】
0005708720.tif 000003
【００１６】
を使用することによって後回転し、周波数領域データを取得するステップとを含み、
式中、aおよびbは定数であり、Nは時間領域データの長さであり、
【００１７】
【数３】
0005708720.tif 000004
【００１８】
【数４】
0005708720.tif 000005
【００１９】
【数５】
0005708720.tif 000006
【００２０】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００２１】
周波数領域から時間領域への信号処理方法は、
周波数領域データにひねりを施す(twiddling)ステップと、
ひねりを施したデータを、回転因子
【００２２】
【数６】
0005708720.tif 000007
【００２３】
を使用することによって前回転するステップと、
前回転データに対してN/4点のDFTを実行するステップと、
DFTによって変換されたデータを、回転因子
【００２４】
【数７】
0005708720.tif 000008
【００２５】
を使用することによって後回転するステップと、
後回転データを後処理して、時間領域データを取得するステップとを含み、
式中、cおよびdは定数であり、Nは周波数領域データの倍長であり、
【００２６】
【数８】
0005708720.tif 000009
【００２７】
【数９】
0005708720.tif 000010
【００２８】
【数１０】
0005708720.tif 000011
【００２９】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００３０】
データ処理方法は、
アドレステーブルに基づきQ回にわたってデータに対しP点DFTを実行するステップと、
アドレステーブルに基づきP回にわたってQ回にわたってP点DFTを実行した後に得られたデータに対してQ点DFTを実行するステップとを含む。
【００３１】
時間領域から周波数領域への信号処理装置は、
時間領域データを前処理するように適合された前処理ユニットと、
回転因子
【００３２】
【数１１】
0005708720.tif 000012
【００３３】
を使用することによって、前処理ユニットにより得られたデータを前回転するように適合された第1の前回転ユニットと、
第1の前回転ユニットによって処理されたデータに対してN/4点のDFTを実行するように適合された第1のフーリエ変換ユニットと、
回転因子
【００３４】
【数１２】
0005708720.tif 000013
【００３５】
を使用することによって第1のフーリエ変換ユニットにより変換されたデータを後回転して周波数領域データを取得するように適合された第1の後回転ユニットとを備え、式中、
【００３６】
【数１３】
0005708720.tif 000014
【００３７】
【数１４】
0005708720.tif 000015
【００３８】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００３９】
周波数領域から時間領域への信号処理装置は、
周波数領域データにひねりを施すように適合されたひねり処理ユニット(twiddling unit)と、
回転因子
【００４０】
【数１５】
0005708720.tif 000016
【００４１】
を使用することによって、ひねり処理ユニットにより得られたデータを前回転するように適合された第2の前回転ユニットと、
第2の前回転ユニットによって処理されたデータに対してN/4点のDFTを実行するように適合された第2のフーリエ変換ユニットと、
回転因子
【００４２】
【数１６】
0005708720.tif 000017
【００４３】
を使用することによって、第2のフーリエ変換ユニットにより得られたデータを後回転するように適合された第3の後回転ユニットと、
第3の後回転ユニットによって処理されたデータを後処理して時間領域データを取得するように適合された後処理ユニットとを備え、式中、
【００４４】
【数１７】
0005708720.tif 000018
【００４５】
【数１８】
0005708720.tif 000019
【００４６】
であり、nおよびkはそれぞれすべてN/4以下の非負整数である。
【００４７】
データ処理装置は、
アドレステーブルを作成するか、または格納するように適合されたアドレステーブルユニットと、
アドレステーブルユニットによって作成されるか、または格納されているアドレステーブルに基づきQ回にわたってデータに対しP点DFTを実行するように適合された第5の変換ユニットと、
アドレステーブルユニットによって作成されるか、または格納されているアドレステーブルに基づきP回にわたって第5の変換ユニットによって変換されたデータに対しQ点DFTを実行するように適合された第6の変換ユニットとを備える。
【００４８】
上記の技術的解決策では、本発明の実施形態において提供される信号処理方法によって採用されている回転因子は、定数と
【００４９】
【数１９】
0005708720.tif 000020
【００５０】
との積である。因子
【００５１】
【数２０】
0005708720.tif 000021
【００５２】
は対称であるため、前回転および後回転を完了させるためにN/4点のデータテーブルを記憶するだけでよい。従来技術に比べて、本発明の実施形態において提供される信号処理方法は、記憶容量を低減し、ストレージリソースの消費を減らし、変換効率を高める。さらに、本発明の実施形態の信号処理方法では後回転を実行するときに正規化因子が不要になるため、関係する処理ステップなしで済ませられ、したがって変換効率がさらに改善される。
【００５３】
本発明または従来技術の技術的な解決策をわかりやすく説明するために、本発明または従来技術の実施形態の説明において必要な図面について簡単に説明する。後述の図面は、本発明の一部の実施形態のみであることは明らかである。当業者であれば、創造的な作業を行うことなくこれらの図面に基づいて他の図面を得ることができる。
【図面の簡単な説明】
【００５４】
【図１】本発明の第1の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。
【図２】本発明の一実施形態におけるFFTの演算に対しアドレステーブルを採用するデータ処理方法の流れ図である。
【図３】本発明の第2の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。
【図４】本発明の第3の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。
【図５】本発明の第4の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。
【図６】本発明の第5の実施形態における時間領域から周波数領域への信号処理方法の流れ図である。
【図７】本発明の第6の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。
【図８】本発明の一実施形態における時間領域から周波数領域への信号処理装置の構造を示す図である。
【図９】本発明の一実施形態における周波数領域から時間領域への信号処理装置の構造を示す図である。
【図１０】本発明の一実施形態におけるデータ処理装置の構造を示す図である。
【発明を実施するための形態】
【００５５】
本発明の技術的解決策は、以下で付属の図面を参照しつつ詳細に説明される。これらの実施形態は例示的なものにすぎず、本発明は、そのような実施形態に限定されないことは明らかである。本発明の実施形態に基づいて当業者が構成する他の実施形態も、本発明の保護の範囲内に入る。
【００５６】
本発明の実施形態は、信号処理の効率の改善を支援するための信号処理方法ならびにデータ処理の方法および装置を実現する。
【００５７】
従来技術では、N/4点のFFTに基づく高速MDCTを実現するために、最初にN点のデータに窓関数を掛け、ひねりを施し、前回転して、N点のMDCTをN/4点のFFTに変える。FFT演算で得られたデータを後回転して、最終的なMDCT係数を得る。
【００５８】
MDCTの定義は
【００５９】
【数２１】
0005708720.tif 000022
【００６０】
であり、式中、Aは正規化因子であり、定数である。
【００６１】
MDCTの定義によれば、
【００６２】
【数２２】
0005708720.tif 000023
【００６３】
【数２３】
0005708720.tif 000024
【００６４】
が得られるが、式中、
【００６５】
【数２４】
0005708720.tif 000025
【００６６】
である。
【００６７】
これら2つの式を組み合わせて、
【００６８】
【数２５】
0005708720.tif 000026
【００６９】
を得ることができる。
【００７０】
次いで、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
式中、
【００７３】
【数２６】
0005708720.tif 000027
【００７４】
または
【００７５】
【数２７】
0005708720.tif 000028
【００７６】
である。
【００７７】
3.回転因子
【００７８】
【数２８】
0005708720.tif 000029
【００７９】
を使用することによってunを前回転する。
【００８０】
4.回転データに対してN/4点FFTを実行する。
【００８１】
5.回転因子
【００８２】
【数２９】
0005708720.tif 000030
【００８３】
および正規化因子Aを使用することによって変換データを後回転する。
【００８４】
6.後回転を通じて得られる複素数の実部はX2kであり、これはMDCTスペクトルの奇数周波数を表し、虚部は-Xn/2-1-2kであり、これはMDCTスペクトルの偶数周波数を表す。
【００８５】
回転因子
【００８６】
【数３０】
0005708720.tif 000031
【００８７】
は、
【００８８】
【数３１】
0005708720.tif 000032
【００８９】
に展開することができる。
【００９０】
回転因子
【００９１】
【数３２】
0005708720.tif 000033
【００９２】
および
【００９３】
【数３３】
0005708720.tif 000034
【００９４】
は、前回転および後回転の処理に必要であるため、少なくともN/4点のコサイン値およびN/4点のサイン値、合わせてN/2個の値を記憶する必要がある。前回転ステップと後回転ステップが非対称的である場合、N個の値を記憶する必要がある。Nが大きい場合、追加ストレージの容量が大きくなり、したがって、多くのストレージリソースが消費され、変換効率が影響を受ける。
【００９５】
本発明の一実施形態において提供される時間領域から周波数領域への信号処理方法は、以下のステップを含む。
【００９６】
1.時間領域データを前処理する。
【００９７】
2.前処理されたデータを、回転因子
【００９８】
【数３４】
0005708720.tif 000035
【００９９】
を使用することによって前回転する。
【０１００】
3.前回転データに対してN/4点のDFTを実行する。
【０１０１】
4.DFTの後のデータを、回転因子
【０１０２】
【数３５】
0005708720.tif 000036
【０１０３】
を使用することによって後回転し、周波数領域データを取得する。
式中、aおよびbは定数であり、Nは時間領域データの長さであり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０１０４】
【数３６】
0005708720.tif 000037
【０１０５】
である。
【０１０６】
前回転の前のデータに対するすべての処理は、前処理として説明できる。この実施形態では、例えば、前処理は、窓関数を掛けてひねりを施すステップまたはひねりを施すステップのみとしてよい。
【０１０７】
本発明の一実施形態において提供される周波数領域から時間領域への信号処理方法は、以下のステップを含む。
【０１０８】
1.周波数領域データにひねりを施す。
【０１０９】
2.ひねりを施されたデータを、回転因子
【０１１０】
【数３７】
0005708720.tif 000038
【０１１１】
を使用することによって前回転する。
【０１１２】
3.前回転データに対してN/4点のDFTを実行する。
【０１１３】
4.DFTの後のデータを、回転因子
【０１１４】
【数３８】
0005708720.tif 000039
【０１１５】
を使用することによって後回転する。
【０１１６】
5.後回転データを後処理して、時間領域データを取得する。
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０１１７】
【数３９】
0005708720.tif 000040
【０１１８】
である。
【０１１９】
後回転の後のデータに対するすべての処理は、後処理として説明できる。後処理の内容は、対応する時間領域から周波数領域への信号処理方法における前処理の内容に依存する。この実施形態では、例えば、前処理が窓関数を掛けてひねりを施すステップである場合、後処理も窓関数を掛けてひねりを施すステップであり、前処理がひねりを施すステップだけである場合、後処理もひねりを施すステップだけである。
【０１２０】
時間領域から周波数領域への信号処理は、順変換とも称され、周波数領域から時間領域への信号処理は、逆変換とも称されうる。順変換と逆変換においてa×b×c×d=4/Nである場合、順変換の出力データを逆変換の入力データとして使用すると、逆変換の結果が順変換の前のデータを復元できるため、完全な再構成を行うことができる。実際、完全な再構成は必ずしも必要でない。
【０１２１】
本発明の一実施形態において提供される信号処理方法によって採用される回転因子における
【０１２２】
【数４０】
0005708720.tif 000041
【０１２３】
は、
【０１２４】
【数４１】
0005708720.tif 000042
【０１２５】
に展開することができ、
式中、
【０１２６】
【数４２】
0005708720.tif 000043
【０１２７】
【数４３】
0005708720.tif 000044
【０１２８】
である。
【０１２９】
式
【０１３０】
【数４４】
0005708720.tif 000045
【０１３１】
から、n+(N/4-1-n)=N/4-1であることがわかり、n=0,...,N/4-1およびk=0,...,N/4-1に対して、(n=0のときの)
【０１３２】
【数４５】
0005708720.tif 000046
【０１３３】
の第1の値は、(n=N/4-1のときの)
【０１３４】
【数４６】
0005708720.tif 000047
【０１３５】
の最後の値に等しい。(n=1のときの)
【０１３６】
【数４７】
0005708720.tif 000048
【０１３７】
の第2の値は、(n=N/4-2のときの)
【０１３８】
【数４８】
0005708720.tif 000049
【０１３９】
の最後から2番目の値に等しく、以下同様である。
【０１４０】
したがって、
【０１４１】
【数４９】
0005708720.tif 000050
【０１４２】
は、対称的である。前回転および後回転を完了させるために、
【０１４３】
【数５０】
0005708720.tif 000051
【０１４４】
または
【０１４５】
【数５１】
0005708720.tif 000052
【０１４６】
のN/4点データテーブルを記憶するだけでよい。
【０１４７】
従来のMDCTにおいて、MDCTのスペクトル係数を得るために、回転因子
【０１４８】
【数５２】
0005708720.tif 000053
【０１４９】
および
【０１５０】
【数５３】
0005708720.tif 000054
【０１５１】
を使用する必要があり、また
【０１５２】
【数５４】
0005708720.tif 000055
【０１５３】
および
【０１５４】
【数５５】
0005708720.tif 000056
【０１５５】
は対称的でない。したがって、前回転および後回転において少なくともN/4点のコサイン値およびN/4点のサイン値を記憶する必要がある。本発明の実施形態において提供される信号処理方法によって採用されている回転因子は、定数と
【０１５６】
【数５６】
0005708720.tif 000057
【０１５７】
との積である。因子
【０１５８】
【数５７】
0005708720.tif 000058
【０１５９】
は対称であるため、前回転および後回転を完了させるために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
を満たすが、
式中、
【０１６４】
【数５８】
0005708720.tif 000059
【０１６５】
または
【０１６６】
【数５９】
0005708720.tif 000060
【０１６７】
である。
【０１６８】
102.前処理されたデータを、回転因子
【０１６９】
【数６０】
0005708720.tif 000061
【０１７０】
を使用することによって前回転する。
【０１７１】
ひねりを施されたデータunは、回転因子
【０１７２】
【数６１】
0005708720.tif 000062
【０１７３】
n=0,...,N/4-1を使用することによって前回転され、式中、
【０１７４】
【数６２】
0005708720.tif 000063
【０１７５】
であり、aは定数である。
【０１７６】
回転の後得られるデータは、
【０１７７】
【数６３】
0005708720.tif 000064
【０１７８】
である。
【０１７９】
この実施形態では、定数は
【０１８０】
【数６４】
0005708720.tif 000065
【０１８１】
とすることができる。回転因子中の
【０１８２】
【数６５】
0005708720.tif 000066
【０１８３】
は、
【０１８４】
【数６６】
0005708720.tif 000067
【０１８５】
の形式で表すことができ、これは
【０１８６】
【数６７】
0005708720.tif 000068
【０１８７】
および
【０１８８】
【数６８】
0005708720.tif 000069
【０１８９】
満たすので、N/4点のサインもしくはコサインデータテーブルのみが、この方法の態様において必要である。この実施形態では、N/4点のみのデータテーブルが記憶される。データテーブル内の値は、
【０１９０】
【数６９】
0005708720.tif 000070
【０１９１】
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に関する
【０２０８】
【数７０】
0005708720.tif 000071
【０２０９】
の巡回剰余の逆数であり、
【０２１０】
【数７１】
0005708720.tif 000072
【０２１１】
を満たす。
【０２１２】
アドレステーブル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に関する
【０２１８】
【数７２】
0005708720.tif 000073
【０２１９】
の巡回剰余の逆数であり、
【０２２０】
【数７３】
0005708720.tif 000074
【０２２１】
を満たす。
【０２２２】
アドレステーブル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の後のデータを、回転因子
【０２２７】
【数７４】
0005708720.tif 000075
【０２２８】
を使用することによって後回転し、周波数領域データを取得する。
【０２２９】
変換されたデータは、回転因子
【０２３０】
【数７５】
0005708720.tif 000076
【０２３１】
k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０２３２】
【数７６】
0005708720.tif 000077
【０２３３】
であり、bは定数である。この実施形態では、定数は
【０２３４】
【数７７】
0005708720.tif 000078
【０２３５】
とすることができる。回転因子中の
【０２３６】
【数７８】
0005708720.tif 000079
【０２３７】
は、
【０２３８】
【数７９】
0005708720.tif 000080
【０２３９】
の形式で表すことができ、b=aであるため、ステップ102で使用されるN/4点データテーブルは、このステップの態様において再利用することができる。
【０２４０】
周波数領域データ、さらには最終的なスペクトルは、Xk、k=0,...,N/2-1であり、
【０２４１】
【数８０】
0005708720.tif 000081
【０２４２】
【数８１】
0005708720.tif 000082
【０２４３】
で表すことができる。
【０２４４】
本発明の第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.ひねりを施されたデータを、回転因子
【０２５０】
【数８２】
0005708720.tif 000083
【０２５１】
を使用することによって前回転する。
【０２５２】
ひねりを施されたデータは、回転因子
【０２５３】
【数８３】
0005708720.tif 000084
【０２５４】
k=0,...,N/4-1を使用することによって前回転されるが、式中、
【０２５５】
【数８４】
0005708720.tif 000085
【０２５６】
であり、cは定数である。
【０２５７】
この実施形態では、定数は
【０２５８】
【数８５】
0005708720.tif 000086
【０２５９】
とすることができ、したがって、ステップ102および104で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０２６０】
303.前回転データに対してN/4点のDFTを実行する。
【０２６１】
このステップでは、N/4点のふつうのDFTが使用されるか、または他のN/4点FFTが使用されうる。
【０２６２】
このステップでは、図2に示されている320点FFTが実行されうる。
【０２６３】
304.DFTの後のデータを、回転因子
【０２６４】
【数８６】
0005708720.tif 000087
【０２６５】
を使用することによって後回転する。
【０２６６】
変換されたデータは、回転因子
【０２６７】
【数８７】
0005708720.tif 000088
【０２６８】
k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０２６９】
【数８８】
0005708720.tif 000089
【０２７０】
であり、dは定数である。
【０２７１】
この実施形態では、定数は
【０２７２】
【数８９】
0005708720.tif 000090
【０２７３】
とすることができ、したがって、ステップ102および104で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０２７４】
上記の処理の後得られるデータynは、
【０２７５】
【数９０】
0005708720.tif 000091
【０２７６】
である。
【０２７７】
305.後回転データを後処理して、時間領域データを取得する。
【０２７８】
このステップでは、後処理は、窓関数を掛け、ひねりを施すステップを含む。実際には、他の後処理手段も使用される場合がある。
【０２７９】
窓関数を掛け、ひねりを施した後、時間領域データ
【０２８０】
【数９１】
0005708720.tif 000092
【０２８１】
が得られ、
【０２８２】
【数９２】
0005708720.tif 000093
【０２８３】
であるが、式中、
【０２８４】
【数９３】
0005708720.tif 000094
【０２８５】
、n=0,...,N/8-1であり、gnは合成窓であり、これは完全な再構成条件を解析窓hn、つまり、hngn+hn+N/2gn+N/2=1、n=0,...,N-N/2-1と一緒に満たす。mnは前のフレームのバッファリングされたデータであり、mnの更新は、
【０２８６】
【数９４】
0005708720.tif 000095
【０２８７】
を満たす。
【０２８８】
本発明の第1の実施形態において提供される時間領域から周波数領域への信号処理方法および本発明の第2の実施形態において提供される周波数領域から時間領域への信号処理方法が使用される場合、順変換および逆変換中の定数a、b、c、およびdはa×b×c×d=4/Nを満たせば、逆変換の結果は完全な再構成に対し使用可能である。実際、完全な再構成は必ずしも必要でない。
【０２８９】
例えば、
【０２９０】
【数９５】
0005708720.tif 000096
【０２９１】
を選択することができる。そこで、順変換および逆変換は、前回転および後回転を完了させるために
【０２９２】
【数９６】
0005708720.tif 000097
【０２９３】
および
【０２９４】
【数９７】
0005708720.tif 000098
【０２９５】
においてN/4点データテーブルを記憶するだけでよい。定数a、b、c、およびdが等しくない場合、前回転および後回転を完了するために、実用的な条件に従って適切なデータテーブルを格納する必要がある。
【０２９６】
本発明の一実施形態において提供される別の時間領域から周波数領域への信号処理方法は、以下のステップを含む。
【０２９７】
1.時間領域データを前処理する。
【０２９８】
2.前処理されたデータを、回転因子
【０２９９】
【数９８】
0005708720.tif 000099
【０３００】
を使用することによって前回転する。
【０３０１】
3.前回転データに対してN/4点のDFTを実行する。
【０３０２】
4.DFTの後のデータを、回転因子
【０３０３】
【数９９】
0005708720.tif 000100
【０３０４】
および正規化因子Aを使用することによって後回転し、周波数領域データを取得するが、
式中、aおよびbは定数であり、Nは時間領域データの長さであり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０３０５】
【数１００】
0005708720.tif 000101
【０３０６】
である。
【０３０７】
前回転の前のデータに対するすべての処理は、前処理として説明できる。この実施形態では、例えば、前処理は、窓関数を掛けてひねりを施すステップまたはひねりを施すステップのみとしてよい。
【０３０８】
本発明の一実施形態において提供される別の周波数領域から時間領域への信号処理方法は、以下のステップを含む。
【０３０９】
1.周波数領域データにひねりを施す。
【０３１０】
2.ひねりを施されたデータを、回転因子
【０３１１】
【数１０１】
0005708720.tif 000102
【０３１２】
を使用することによって前回転する。
【０３１３】
3.前回転データに対してN/4点のDFTを実行する。
【０３１４】
4.DFTの後のデータを、回転因子
【０３１５】
【数１０２】
0005708720.tif 000103
【０３１６】
および正規化因子Bを使用することによって後回転する。
【０３１７】
5.後回転データを後処理して、時間領域データを取得するが、
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、n=0,...,N/4-1、k=0,...,N/4-1、および
【０３１８】
【数１０３】
0005708720.tif 000104
【０３１９】
である。
【０３２０】
後回転の後のデータに対するすべての処理は、後処理として説明できる。後処理の内容は、対応する時間領域から周波数領域への信号処理方法における前処理の内容に依存する。この実施形態では、例えば、前処理が窓関数を掛けてひねりを施すステップである場合、後処理も窓関数を掛けてひねりを施すステップであり、前処理がひねりを施すステップである場合、後処理もひねりを施すステップである。
【０３２１】
時間領域から周波数領域への信号処理は、順変換とも称され、周波数領域から時間領域への信号処理は、逆変換とも称される。順変換と逆変換においてa×b×c×d=4/Nである場合、順変換の出力データを逆変換の入力データとして使用すると、逆変換の結果が順変換の前のデータを復元できるため、完全な再構成を行うことができる。例えば、a=b=c=d=1、A・B=4/N、または
【０３２２】
【数１０４】
0005708720.tif 000105
【０３２３】
、A=B=1を選択することができる。実際、完全な再構成は必ずしも必要でない。
【０３２４】
この実施形態において提供される信号処理方法によって採用される回転因子における
【０３２５】
【数１０５】
0005708720.tif 000106
【０３２６】
は、
【０３２７】
【数１０６】
0005708720.tif 000107
【０３２８】
に展開することができ、
式中、
【０３２９】
【数１０７】
0005708720.tif 000108
【０３３０】
【数１０８】
0005708720.tif 000109
【０３３１】
である。
【０３３２】
したがって、
【０３３３】
【数１０９】
0005708720.tif 000110
【０３３４】
は、対称的である。前回転および後回転を完了させるために、
【０３３５】
【数１１０】
0005708720.tif 000111
【０３３６】
または
【０３３７】
【数１１１】
0005708720.tif 000112
【０３３８】
のN/4点データテーブルを記憶するだけでよい。
【０３３９】
従来のMDCTにおいて、MDCTのスペクトル係数を得るために、回転因子
【０３４０】
【数１１２】
0005708720.tif 000113
【０３４１】
を使用する必要があり、また
【０３４２】
【数１１３】
0005708720.tif 000114
【０３４３】
は対称的でない。したがって、前回転および後回転において少なくともN/4点のコサイン値およびN/4点のサイン値を記憶する必要がある。本発明の実施形態において提供される信号処理方法によって採用されている回転因子は、定数と
【０３４４】
【数１１４】
0005708720.tif 000115
【０３４５】
との積である。因子
【０３４６】
【数１１５】
0005708720.tif 000116
【０３４７】
は対称であるため、前回転および後回転を完了させるために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は
【０３５４】
【数１１６】
0005708720.tif 000117
【０３５５】
を満たすが、
式中、
【０３５６】
【数１１７】
0005708720.tif 000118
【０３５７】
または
【０３５８】
【数１１８】
0005708720.tif 000119
【０３５９】
である。
【０３６０】
402.前処理されたデータを、回転因子
【０３６１】
【数１１９】
0005708720.tif 000120
【０３６２】
を使用することによって前回転する。
【０３６３】
ひねりを施されたデータunは、回転因子
【０３６４】
【数１２０】
0005708720.tif 000121
【０３６５】
n=0,...,N/4-1を使用することによって前回転され、式中、
【０３６６】
【数１２１】
0005708720.tif 000122
【０３６７】
であり、aは定数である。
【０３６８】
この実施形態では、a=1であり、回転因子は、
【０３６９】
【数１２２】
0005708720.tif 000123
【０３７０】
によって表すことができる。
【０３７１】
この式は、
【０３７２】
【数１２３】
0005708720.tif 000124
【０３７３】
および
【０３７４】
【数１２４】
0005708720.tif 000125
【０３７５】
を満たす。
【０３７６】
特定の態様では、
【０３７７】
【数１２５】
0005708720.tif 000126
【０３７８】
または
【０３７９】
【数１２６】
0005708720.tif 000127
【０３８０】
のN/4点データテーブルを記憶するだけでよい。この実施形態では、N/4点のサインテーブルが記憶される。サインテーブル内の値は、
【０３８１】
【数１２７】
0005708720.tif 000128
【０３８２】
、n=0,...,159で表される。
【０３８３】
403.前回転データに対してN/4個の入力のDFTを実行する。
【０３８４】
このステップでは、M=N/4=160点のふつうのDFTが使用されるか、またはM=N/4=160点のFFTが使用されうる。
【０３８５】
404.DFTの後のデータを、回転因子
【０３８６】
【数１２８】
0005708720.tif 000129
【０３８７】
および正規化因子Aを使用することによって後回転し、周波数領域出力データを取得する。
【０３８８】
変換されたデータは、回転因子
【０３８９】
【数１２９】
0005708720.tif 000130
【０３９０】
、k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０３９１】
【数１３０】
0005708720.tif 000131
【０３９２】
であり、bは定数である。この実施形態では、b=1であり、回転因子は、
【０３９３】
【数１３１】
0005708720.tif 000132
【０３９４】
によって表すことができる。
【０３９５】
b=aなので、ステップ402で使用されるN/4点データテーブルは、このステップの態様において使用することができる。
【０３９６】
最終データXk、k=0,...,N/2-1が得られ、これらは
【０３９７】
【数１３２】
0005708720.tif 000133
【０３９８】
【数１３３】
0005708720.tif 000134
【０３９９】
であり、式中、Aは正規化因子であり、定数である。
【０４００】
この実施形態では、定数Aは
【０４０１】
【数１３４】
0005708720.tif 000135
【０４０２】
とすることができる。
【０４０３】
本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法に従って、周波数領域から時間領域への信号処理方法が本発明の第4の実施形態において提供される。本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法を使用して変換を実行する場合、本発明の第4の実施形態において提供される周波数領域から時間領域への信号処理方法を使用して対応する逆変換を実行することができる。
【０４０４】
図5は、本発明の第4の実施形態における周波数領域から時間領域への信号処理方法の流れ図である。この方法は、以下を含む。
【０４０５】
501.周波数領域入力データにひねりを施す。
【０４０６】
この実施形態では、データXk、k=0,...,N/2-1にひねりを施して、中間変数
【０４０７】
【数１３５】
0005708720.tif 000136
【０４０８】
、k=0,...,N/4-1を得るが、式中、N=640である。
【０４０９】
502.ひねりを施されたデータを、回転因子
【０４１０】
【数１３６】
0005708720.tif 000137
【０４１１】
を使用することによって前回転する。
【０４１２】
ひねりを施されたデータは、回転因子
【０４１３】
【数１３７】
0005708720.tif 000138
【０４１４】
、k=0,...,N/4-1を使用することによって前回転され、式中、
【０４１５】
【数１３８】
0005708720.tif 000139
【０４１６】
であり、cは定数である。この実施形態ではc=1であり、本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ402および404で使用されるN/4点データテーブルも再利用することができる。
【０４１７】
503.前回転データに対してN/4点のDFTを実行する。
【０４１８】
回転データに対してM=N/4=160点のDFTを実行する。このステップでは、160点のふつうのDFTが使用されるか、または他の160点FFTが使用されうる。
【０４１９】
504.DFTの後のデータを、回転因子
【０４２０】
【数１３９】
0005708720.tif 000140
【０４２１】
および正規化因子Bを使用することによって後回転する。
【０４２２】
変換されたデータは、回転因子
【０４２３】
【数１４０】
0005708720.tif 000141
【０４２４】
、k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０４２５】
【数１４１】
0005708720.tif 000142
【０４２６】
であり、dは定数である。上記の処理の後得られるデータynは、
【０４２７】
【数１４２】
0005708720.tif 000143
【０４２８】
である。
【０４２９】
Bは、正規化因子であり、定数である。この実施形態では、定数Bは
【０４３０】
【数１４３】
0005708720.tif 000144
【０４３１】
とすることができる。この実施形態ではd=1であり、本発明の第3の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ402および404で使用されるN/4点データテーブルも再利用することができる。
【０４３２】
505.後回転データを後処理して、時間領域出力データを取得する。
【０４３３】
このステップでは、後処理は、窓関数を掛け、ひねりを施すステップを含む。実際には、他の後処理手段も使用される場合がある。
【０４３４】
窓関数を掛けて、ひねりを施した後、出力データ
【０４３５】
【数１４４】
0005708720.tif 000145
【０４３６】
、n=0,...,N/2-1が得られ、これは、
【０４３７】
【数１４５】
0005708720.tif 000146
【０４３８】
を満たし、式中、
【０４３９】
【数１４６】
0005708720.tif 000147
【０４４０】
n=0,...,N/8-1であり、gnは、解析窓hnと一緒に完全な再構成条件を満たす、合成窓である、つまり、
hngn+hn+N/2gn+N/2=1  n=0,...,N-N/2-1
であり、mnは前のフレームのバッファリングされたデータであり、mnの更新は、
【０４４１】
【数１４７】
0005708720.tif 000148
【０４４２】
を満たす。
【０４４３】
完全な再構成条件を満たすために、順変換、逆変換、または順/逆変換に特定の正規化因子を掛けるとよい。この実施形態では、順変換および逆変換に同じ正規化因子を掛ける。適宜、順変換または逆変換のみに特定の正規化因子を掛けるか、または順変換および逆変換に異なる正規化因子を掛ける。完全な再構成は、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
を満たすが、
式中、
【０４５０】
【数１４８】
0005708720.tif 000149
【０４５１】
または
【０４５２】
【数１４９】
0005708720.tif 000150
【０４５３】
である。
【０４５４】
窓関数は、このステップの解析窓関数hnおよび逆変換で使用される合成窓関数gnが式
hngn+hn+N/2gn+N/2=1  n=0,...,N-N/2-1
を満たすときに完全な再構成条件を満たす。
【０４５５】
602.前処理されたデータを、回転因子
【０４５６】
【数１５０】
0005708720.tif 000151
【０４５７】
を使用することによって前回転する。
【０４５８】
ひねりを施されたデータunは、回転因子
【０４５９】
【数１５１】
0005708720.tif 000152
【０４６０】
を使用することによって前回転される。回転の後得られるデータは、
【０４６１】
【数１５２】
0005708720.tif 000153
【０４６２】
n=0,...,N/4-1であり、式中、
【０４６３】
【数１５３】
0005708720.tif 000154
【０４６４】
であり、aは定数である。計算の複雑度をさらに低くするために、正規化因子を回転因子と直接組み合わせるとよい。この実施形態では、定数aは、回転因子において
【０４６５】
【数１５４】
0005708720.tif 000155
【０４６６】
とすることができ、これは
【０４６７】
【数１５５】
0005708720.tif 000156
【０４６８】
の形式で表すことができ、また
【０４６９】
【数１５６】
0005708720.tif 000157
【０４７０】
【数１５７】
0005708720.tif 000158
【０４７１】
である。
【０４７２】
したがって、N/4点のデータテーブルを記憶するだけでよい。この実施形態では、N/4点のデータテーブルが記憶され、データテーブル内の値は、
【０４７３】
【数１５８】
0005708720.tif 000159
【０４７４】
、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に関する
【０４８７】
【数１５９】
0005708720.tif 000160
【０４８８】
の巡回剰余の逆数であり、
【０４８９】
【数１６０】
0005708720.tif 000161
【０４９０】
を満たす。この実施形態では、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に関する
【０４９３】
【数１６１】
0005708720.tif 000162
【０４９４】
の巡回剰余の逆数であり、
【０４９５】
【数１６２】
0005708720.tif 000163
【０４９６】
を満たす。この実施形態では、5点DFTは、64回にわたって実行される。i番目(i=0,...,63)の5点DFTの入力データは、アドレステーブル配列I[i]から始まる64個の点の間隔で5つのアドレスインデックスに関連付けられているデータである(回転後のデータ)。i番目の5点DFTは、4のステップの循環シフトで適用される。
【０４９７】
604.DFTの後のデータを、回転因子
【０４９８】
【数１６３】
0005708720.tif 000164
【０４９９】
および正規化因子Aを使用することによって後回転し、周波数領域データを取得する。
【０５００】
変換されたデータは、回転因子
【０５０１】
【数１６４】
0005708720.tif 000165
【０５０２】
、k=0,...,N/4-1を使用することによって後回転されるが、式中、
【０５０３】
【数１６５】
0005708720.tif 000166
【０５０４】
であり、bは定数である。この実施形態では、定数bは
【０５０５】
【数１６６】
0005708720.tif 000167
【０５０６】
とすることができる。bが
【０５０７】
【数１６７】
0005708720.tif 000168
【０５０８】
である場合、回転因子中の
【０５０９】
【数１６８】
0005708720.tif 000169
【０５１０】
は、
【０５１１】
【数１６９】
0005708720.tif 000170
【０５１２】
の形式で表すことができ、bの値はステップ602のaに等しいので、ステップ602で格納されるN/4点のデータテーブルも、このステップにおいて再利用することができる。
【０５１３】
出力データ、さらには最終的なスペクトルは、Xk、k=0,...,N/2-1であり、
【０５１４】
【数１７０】
0005708720.tif 000171
【０５１５】
【数１７１】
0005708720.tif 000172
【０５１６】
で表すことができ、
式中、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.ひねりを施されたデータを、回転因子
【０５２３】
【数１７２】
0005708720.tif 000173
【０５２４】
、k=0,...,N/4-1を使用することによって前回転する。
【０５２５】
式
【０５２６】
【数１７３】
0005708720.tif 000174
【０５２７】
が成り立ち、cは定数である。
【０５２８】
この実施形態では、
【０５２９】
【数１７４】
0005708720.tif 000175
【０５３０】
であり、またcはaまたはbに等しい。したがって、本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ602および604で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０５３１】
703.アドレステーブルに基づくFFTを使用して前回転データに対してN/4点のDFTを実行する。
【０５３２】
M=N/4=P×Qで、PおよびQが互いに素である場合、本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ603のデータ処理方法を使用してこのステップを実行することができる。
【０５３３】
704.変換の後のデータを、回転因子
【０５３４】
【数１７５】
0005708720.tif 000176
【０５３５】
および正規化因子Bを使用することによって後回転する。
【０５３６】
変換されたデータは、回転因子
【０５３７】
【数１７６】
0005708720.tif 000177
【０５３８】
、n=0,...,N/4-1を使用することによって後回転されるが、式中、
【０５３９】
【数１７７】
0005708720.tif 000178
【０５４０】
であり、dは定数である。上記の処理の後得られるデータynは、
【０５４１】
【数１７８】
0005708720.tif 000179
【０５４２】
である。
【０５４３】
Bは、正規化因子であり、定数である。
【０５４４】
この実施形態では、
【０５４５】
【数１７９】
0005708720.tif 000180
【０５４６】
であり、またdはa、b、またはcに等しい。したがって、本発明の第5の実施形態において提供される時間領域から周波数領域への信号処理方法のステップ602および604で使用されるN/4点データテーブルも、このステップで再利用することができる。
【０５４７】
705.後回転データに窓関数を掛けてひねりを施し、時間領域データを取得する。
【０５４８】
窓関数を掛けて、ひねりを施した後、出力データ
【０５４９】
【数１８０】
0005708720.tif 000181
【０５５０】
が得られ、これは、
【０５５１】
【数１８１】
0005708720.tif 000182
【０５５２】
であり、
式中、
【０５５３】
【数１８２】
0005708720.tif 000183
【０５５４】
n=0,...,N/4-1であり、gnは、解析窓hnと一緒に完全な再構成条件を満たす、合成窓である、つまり、hngn+hn+N/2gn+N/2=1  n=0,...,N-N/2-1である。mnは前のフレームのバッファリングされたデータであり、mnの更新は、
【０５５５】
【数１８３】
0005708720.tif 000184
【０５５６】
を満たす。
【０５５７】
従来技術では、互いに素な因子に基づく大半の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に関する
【０５７８】
【数１８４】
0005708720.tif 000185
【０５７９】
の巡回剰余の逆数であり、
【０５８０】
【数１８５】
0005708720.tif 000186
【０５８１】
を満たす。
【０５８２】
例えば、アドレステーブル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に関する
【０５８６】
【数１８６】
0005708720.tif 000187
【０５８７】
の巡回剰余の逆数であり、
【０５８８】
【数１８７】
0005708720.tif 000188
【０５８９】
を満たす。
【０５９０】
例えば、アドレステーブル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つのプログラムの命令に従う関係するハードウェアによって実行されうることを理解する。プログラムは、コンピュータ可読記憶媒体に格納することができる。プログラムの実行は、以下のステップを含む。
【０５９３】
時間領域から周波数領域への信号処理方法は、
時間領域データを前処理するステップと、
前処理されたデータを、回転因子
【０５９４】
【数１８８】
0005708720.tif 000189
【０５９５】
を使用することによって前回転するステップと、
前回転データに対してN/4点のDFTを実行するステップと、
DFTの後のデータを、回転因子
【０５９６】
【数１８９】
0005708720.tif 000190
【０５９７】
を使用することによって後回転し、周波数領域データを取得するステップとを含み、
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、
【０５９８】
【数１９０】
0005708720.tif 000191
【０５９９】
である。
【０６００】
周波数領域から時間領域への信号処理方法は、
周波数領域データにひねりを施すステップと、
ひねりを施したデータを、回転因子
【０６０１】
【数１９１】
0005708720.tif 000192
【０６０２】
を使用することによって前回転するステップと、
前回転データに対してN/4点のDFTを実行するステップと、
DFTの後のデータを、回転因子
【０６０３】
【数１９２】
0005708720.tif 000193
【０６０４】
を使用することによって後回転するステップと、
後回転データを後処理して、時間領域データを取得するステップとを含み、
式中、cおよびdは定数であり、Nは周波数領域データの長さの2倍であり、
【０６０５】
【数１９３】
0005708720.tif 000194
【０６０６】
である。
【０６０７】
データ処理方法は、
アドレステーブルに従って入力データに対してQ回にわたってP点DFTを実行するステップと、
アドレステーブルに従ってQ回にわたってP点DFTを実行した後に得られたデータに対してP回にわたってQ点DFTを実行するステップとを含む。
【０６０８】
上述の記憶媒体は、読み出し専用メモリ(ROM)、磁気ディスク、またはコンパクトディスクであってよい。
【０６０９】
図8は、本発明の一実施形態における時間領域から周波数領域への信号処理装置の構造を示す図である。この装置は、
時間領域データを前処理するように適合された前処理ユニット801と、
回転因子
【０６１０】
【数１９４】
0005708720.tif 000195
【０６１１】
を使用することによって、前処理ユニット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、および
【０６１２】
【数１９５】
0005708720.tif 000196
【０６１３】
である。
【０６１４】
第1の後回転ユニット804は、
DFTが実行された後のデータを、回転因子
【０６１５】
【数１９６】
0005708720.tif 000197
【０６１６】
および正規化因子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と、
回転因子
【０６２０】
【数１９７】
0005708720.tif 000198
【０６２１】
を使用することによって、ひねり処理ユニット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、および
【０６２２】
【数１９８】
0005708720.tif 000199
【０６２３】
である。
【０６２４】
第3の後回転ユニット904は、
DFTが実行された後のデータを、回転因子
【０６２５】
【数１９９】
0005708720.tif 000200
【０６２６】
および正規化因子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の剰余を意味する。
【０６２９】
本発明の実施形態において提供される時間領域から周波数領域への信号処理装置および周波数領域から時間領域への信号処理装置の特定の応用に関しては、本発明の実施形態において提供される信号処理方法の説明を参照されたい。
【０６３０】
本発明の実施形態において提供される時間領域から周波数領域への信号処理装置および周波数領域から時間領域への信号処理方法において、回転因子中の
【０６３１】
【数２００】
0005708720.tif 000201
【０６３２】
は
【０６３３】
【数２０１】
0005708720.tif 000202
【０６３４】
に展開することができ、しかも条件
【０６３５】
【数２０２】
0005708720.tif 000203
【０６３６】
および
【０６３７】
【数２０３】
0005708720.tif 000204
【０６３８】
を満たし、回転因子中の
【０６３９】
【数２０４】
0005708720.tif 000205
【０６４０】
は同じ対称条件を満たすので、本発明の実施形態において提供される時間領域から周波数領域への信号処理装置および周波数領域から時間領域への信号処理装置は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に関する
【０６５３】
【数２０５】
0005708720.tif 000206
【０６５４】
の巡回剰余の逆数であり、
【０６５５】
【数２０６】
0005708720.tif 000207
【０６５６】
を満たす。
【０６５７】
例えば、アドレステーブル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に関する
【０６６１】
【数２０７】
0005708720.tif 000208
【０６６２】
の巡回剰余の逆数であり、
【０６６３】
【数２０８】
0005708720.tif 000209
【０６６４】
を満たす。
【０６６５】
例えば、アドレステーブルIがI[n1][n2]の二次元配列の形式で格納される場合、i番目のQ点DFTの入力データは、アドレステーブルI[n1][n2]、n2=0,...,Q-1に格納されているQ個のアドレスインデックスに関連付けられているデータである。それぞれのQ点DFTの結果は、yのステップの循環シフトで適用される。
【０６６６】
本発明の実施形態において提供されるデータ処理装置では、FFTが実行されるときに、アドレステーブルがアドレッシングに使用されるので、入力データはアドレステーブル内の関連付けられているアドレスに従って読み込まれ、出力データはアドレステーブル内の関連付けられているアドレスに従って格納される。変換データは、使用可能な列になっており、逆変換の際に特別な再配列は不要である。したがって、計算におけるアドレッシングコストは低減され、計算効率が増大する。
【０６６７】
以下では、アドレステーブルIに基づく変換が、出力データの使用可能な列を保証することを証明する。
【０６６８】
FFTの定義は、
【０６６９】
【数２０９】
0005708720.tif 000210
【０６７０】
である。
【０６７１】
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の公式は、
【０６７３】
【数２１０】
0005708720.tif 000211
【０６７４】
に展開することができる。
【０６７５】
<K1K2>M=0の場合
【０６７６】
【数２１１】
0005708720.tif 000212
【０６７７】
であり、したがって
【０６７８】
【数２１２】
0005708720.tif 000213
【０６７９】
である。
【０６８０】
なぜなら、
【０６８１】
【数２１３】
0005708720.tif 000214
【０６８２】
だからである。
【０６８３】
i番目(i=0,...,Q-1)のP点DFTの入力データは、アドレステーブルI内のn2=i、n1=0,...,P-1に対応するP個のアドレスインデックスに関連付けられているデータである。最終出力を得るために、i番目のP点DFTの結果をxのステップの循環シフトで適用する。
【０６８４】
ここでは、xは、法Pに関する
【０６８５】
【数２１４】
0005708720.tif 000215
【０６８６】
の巡回剰余の逆数であり、
【０６８７】
【数２１５】
0005708720.tif 000216
【０６８８】
【数２１６】
0005708720.tif 000217
【０６８９】
を満たす。n1=0のときに、
【０６９０】
【数２１７】
0005708720.tif 000218
【０６９１】
であり、n1=1のときに
【０６９２】
【数２１８】
0005708720.tif 000219
【０６９３】
であり、同様に、n1=xのときに
【０６９４】
【数２１９】
0005708720.tif 000220
【０６９５】
である。順次出力のFFTの式
【０６９６】
【数２２０】
0005708720.tif 000221
【０６９７】
では、n1=1のときの回転因子は
【０６９８】
【数２２１】
0005708720.tif 000222
【０６９９】
である。P点DFTでは、
【０７００】
【数２２２】
0005708720.tif 000223
【０７０１】
となるのは、n1=xのとき、xが
【０７０２】
【数２２３】
0005708720.tif 000224
【０７０３】
を満たすときに限る。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に関する
【０７０６】
【数２２４】
0005708720.tif 000225
【０７０７】
の巡回剰余の逆数であり、
【０７０８】
【数２２５】
0005708720.tif 000226
【０７０９】
を満たす。
【０７１０】
本発明は、例示的な実施形態を通じて説明されているけれども、本発明はそのような実施形態に限定されない。当業者であれば本発明の精神および範囲から逸脱することなく、本発明に対しさまざまな修正および変更を加えることができることは、明らかである。請求項およびその等価物により定義された保護の範囲内にある限りそれらの修正および変更も、本発明の対象範囲であることが意図されている。
【符号の説明】
【０７１１】
801  前処理ユニット
802  第1の前回転ユニット
803  第1のフーリエ変換ユニット
804  第1の後回転ユニット
901  ひねり処理ユニット
902  第2の前回転ユニット
903  第2のフーリエ変換ユニット
904  第3の後回転ユニット
905  後処理ユニット
1001  アドレステーブルユニット
1002  第5の変換ユニット
1003  第6の変換ユニット
【図１】
0005708720.tif 000235
【図２】
0005708720.tif 000236
【図３】
0005708720.tif 000237
【図４】
0005708720.tif 000238
【図５】
0005708720.tif 000239
【図６】
0005708720.tif 000240
【図７】
0005708720.tif 000241
【図８】
0005708720.tif 000242
【図９】
0005708720.tif 000243
【図１０】
0005708720.tif 000244