(57)【特許請求の範囲】
【請求項１】
連続する（Ｎ−Ｍ）個の時間領域の入力データ（Ｎは正整数、ＭはＮより小さい正整数）を含む第１の入力ブロックに、前記第１の入力ブロックの直前の連続するＮ個の時間領域の入力データを含む第２の入力ブロックの最後の連続するデータをオーバーラップ量であるＭ個だけ付加し、オーバーラップブロックを生成するオーバーラップ付加手段と、
前記オーバーラップブロック及び前記第２の入力ブロックのそれぞれを、高速フーリエ変換処理により周波数領域の第１の周波数領域ブロック及び第２の周波数領域ブロックに変換するフーリエ変換手段と、
前記第１の周波数領域ブロック及び前記第２の周波数領域ブロックのそれぞれに対してフィルタ処理を行い、第１の処理後ブロック及び第２の処理後ブロックを生成するフィルタ演算手段と、
前記第１の処理後ブロック及び前記第２の処理後ブロックのそれぞれを、逆高速フーリエ変換処理により時間領域の第１の時間領域ブロック及び第２の時間領域ブロックに変換する逆フーリエ変換手段と、
前記第１の時間領域ブロック及び前記第２の時間領域ブロックのそれぞれが時間的にオーバーラップするオーバーラップ部分のうち、前記第１の時間領域ブロックの時間軸の前端のｋ個（ｋはＭより小さい正整数）のデータ及び前記第２の時間領域ブロックの時間軸の後端の（Ｍ−ｋ）個のデータを除去部分データとして除去し、出力データを生成するオーバーラップ除去手段と、
前記第１の時間領域ブロックの前記除去部分データと、前記第２の時間領域ブロックの前記オーバーラップ部分のうちの前記除去部分データ以外の出力部分データとを比較して前記オーバーラップ部分に含まれるデータが発生させる歪み量を検出し、前記歪み量に基づいて前記オーバーラップ量を制御するオーバーラップ誤差検出手段と、
を備えることを特徴とするデジタルフィルタ装置。
【請求項２】
前記オーバーラップ誤差検出手段は、
前記検出した歪み量が規定値よりも大きい場合には、前記オーバーラップ量を増加させ、
前記検出した歪み量が規定値よりも小さい場合には、前記オーバーラップ量を減少させる
ことを特徴とする請求項１に記載のデジタルフィルタ装置。
【請求項３】
前記オーバーラップ誤差検出手段は、
前記第１の時間領域ブロックの前記除去部分データと、前記第２の時間領域ブロックの前記出力部分データとを比較し、前記第１の時間領域ブロックの前記歪み量を検出する第１の誤差比較部と、
前記第１の誤差比較部によって検出された歪み量に基づいて前記オーバーラップ量を決定するオーバーラップ量決定部と、を含む
ことを特徴とする請求項１又は２に記載のデジタルフィルタ装置。
【請求項４】
前記オーバーラップ誤差検出手段は、
前記第２の時間領域ブロックの前記除去部分データと、前記第１の時間領域ブロックの前記出力部分データとを比較し、前記第２の時間領域ブロックの前記歪み量を検出する第２の誤差比較部を含み、
前記オーバーラップ量決定部は、前記第２の誤差比較部によって検出された歪み量に基づいて前記オーバーラップ量を決定する
ことを特徴とする請求項３に記載のデジタルフィルタ装置。
【請求項５】
デジタルフィルタ装置が備えるコンピュータを、
連続する（Ｎ−Ｍ）個の時間領域の入力データ（Ｎは正整数、ＭはＮより小さい正整数）を含む第１の入力ブロックに、前記第１の入力ブロックの直前の連続するＮ個の時間領域の入力データを含む第２の入力ブロックの最後の連続するデータをオーバーラップ量であるＭ個だけ付加し、オーバーラップブロックを生成するオーバーラップ付加手段と、
前記オーバーラップブロック及び前記第２の入力ブロックのそれぞれを、高速フーリエ変換処理により周波数領域の第１の周波数領域ブロック及び第２の周波数領域ブロックに変換するフーリエ変換手段と、
前記第１の周波数領域ブロック及び前記第２の周波数領域ブロックのそれぞれに対してフィルタ処理を行い、第１の処理後ブロック及び第２の処理後ブロックを生成するフィルタ演算手段と、
前記第１の処理後ブロック及び前記第２の処理後ブロックのそれぞれを、逆高速フーリエ変換処理により時間領域の第１の時間領域ブロック及び第２の時間領域ブロックに変換する逆フーリエ変換手段と、
前記第１の時間領域ブロック及び前記第２の時間領域ブロックのそれぞれが時間的にオーバーラップするオーバーラップ部分のうち、前記第１の時間領域ブロックの時間軸の前端のｋ個（ｋはＭより小さい正整数）のデータ及び前記第２の時間領域ブロックの時間軸の後端の（Ｍ−ｋ）個のデータを除去部分データとして除去し、出力データを生成するオーバーラップ除去手段と、
前記第１の時間領域ブロックの前記除去部分データと、前記第２の時間領域ブロックの前記オーバーラップ部分のうちの前記除去部分データ以外の出力部分データとを比較して前記オーバーラップ部分に含まれるデータが発生させる歪み量を検出し、前記歪み量に基づいて前記オーバーラップ量を制御するオーバーラップ誤差検出手段と、
として機能させるためのデジタルフィルタプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル信号処理における演算処理に関し、特にデジタルフィルタ装置、デジタルフィルタ処理方法及びデジタルフィルタプログラムが記憶された記憶媒体に関する。
【背景技術】
【０００２】
デジタル信号処理において重要な処理の１つとして、高速フーリエ変換（Fast Fourier Transform。以降、「ＦＦＴ」という。）処理がある。そして、無線通信や有線通信における信号伝送中の波形歪みを補償する技術の１つとして、例えば、周波数領域等化（Frequency domain equalization（ＦＤＥ））技術が知られている。周波数領域等化では、まず高速フーリエ変換により時間領域の信号データが周波数領域のデータに変換され、次に等化のためのフィルタ処理が行われる。そして、フィルタ処理後のデータは、逆高速フーリエ変換（Inverse ＦＦＴ。以降、「ＩＦＦＴ」という。）により時間領域の信号データに再変換されることによって、元の時間領域の信号の波形歪みが補償される。以降、ＦＦＴとＩＦＦＴを区別しないときは、「ＦＦＴ／ＩＦＦＴ」と表記する。【０００３】
一般に、ＦＦＴ／ＩＦＦＴ処理では、「バタフライ演算」が用いられる。バタフライ演算を用いたＦＦＴ装置については、例えば特許文献１に記載がある。特許文献１には、後述の「ひねり乗算」、すなわち、ひねり係数を用いた乗算についても記載されている。【０００４】
効率的なＦＦＴ／ＩＦＦＴ処理方式としては、例えば非特許文献１に記載されたCooley-Tukeyによるバタフライ演算が有名である。しかし、Cooley-TukeyによるＦＦＴ／ＩＦＦＴ処理方式はポイント数が大きいので、当該処理方式を実現するための回路が複雑になる。そのため、例えば非特許文献２に記載されたPrime Factor法を用いて２つの小さなＦＦＴ／ＩＦＦＴに分解して、ＦＦＴ／ＩＦＦＴ処理が行われる。【０００５】
図７は、例えばPrime Factor法を利用して基数を８とする２段階のバタフライ処理に分解された、６４ポイントＦＦＴのデータフロー５００を示す。データフロー５００は、データ並べ替え処理５０１、バタフライ演算処理５０２、５０３からなる延べ１６回の基数８のバタフライ演算処理、ひねり乗算処理５０４を含む。【０００６】
図７に示すデータフローでは、入力された時間領域のデータｘ(n)（n＝0，1，・・・，63）が、ＦＦＴ処理により、周波数領域の信号Ｘ(k)（k＝0，1，・・・，63）にフーリエ変換される。図７に示す例は、一部のデータフローの図示は省略されている。なお、図７に示すデータフローは、ＩＦＦＴ処理を行う場合についても、基本構成は同じである。【０００７】
ＦＦＴのポイント数が大きい場合、図７に示すデータフローのすべてを回路で実現するためには、膨大な規模の回路を要する。そのため、ＦＦＴのポイント数が大きい場合、必要な処理性能に応じて、データフローの一部分の処理を実現する回路を繰り返し使用することで、ＦＦＴ処理の全体を実現する方法が一般的である。【０００８】
例えば、図７に示すデータフローにおいて、８個のデータに対して並列に（以降、単に「８データ並列で」という。）ＦＦＴ処理を行うＦＦＴ装置を物理的な回路として作成した場合、合計８回の繰り返し処理により６４ポイントＦＦＴ処理を実現することができる。【０００９】
８回の繰り返し処理は、８個のデータに対して行われる部分データフロー５０５ａ〜５０５ｈの、それぞれにあたる処理が順に行われるものであり、具体的には、次のように行われる。すなわち、１回目には、部分データフロー５０５ａに相当する処理が、２回目には、部分データフロー５０５ｂに相当する処理が、３回目には、部分データフロー５０５ｃ（図示せず）に相当する処理が行われる。以降同様に、８回目の部分データフロー５０５ｈに相当する処理までが順に行われる。以上の処理により、６４ポイントＦＦＴ処理が実現される。【００１０】
バタフライ演算では、逐次的な順序に並べられたデータが、所定の規則に従った順序で読み出され、処理される。そのため、バタフライ演算では、データの並べ替えが必要であり、そのためにはＲＡＭ（Random Access Memory）が用いられる。バタフライ演算においてＲＡＭを用いたデータの並べ替えを行うＦＦＴ装置については、例えば特許文献２に記載がある。【００１１】
また、メモリ使用量を削減したＦＦＴ演算装置については、バタフライ演算の並列処理による高速化技術が、例えば特許文献３に記載されている。【００１２】
ところで、ＦＦＴでは、処理対象である、切り出された入力信号の範囲、すなわち連続する入力データの集合（以降、「処理ブロック」という。）と同じデータが周期的に繰り返されることが仮定されている。ところが、実際の信号は必ずしも周期信号ではないため、ＦＦＴ後の処理ブロックの両端付近に演算歪みが発生するという問題がある。【００１３】
この問題を解消する技術として、例えば、「オーバーラップ方式」を挙げることができる。オーバーラップ方式では、隣接する処理ブロック同士が所定のデータ数だけオーバーラップされ、ＦＦＴ処理が行われる。ＦＦＴ処理後のデータはフィルタ処理された上で、ＩＦＦＴ処理により時間領域信号に再変換される。そして、オーバーラップされた処理ブロックにおける、演算歪みが生じた両端の部分データが除去される。以降、処理ブロックのデータのうち、除去される部分を「除去部分」といい、除去されずに出力される部分を「出力部分」という。【００１４】
オーバーラップ方式は、ＦＤＥにも適用されている（例えば、特許文献４、５参照）。オーバーラップ方式がＦＤＥに適用されたオーバーラップＦＤＥ方式について説明する。図８は、オーバーラップＦＤＥ方式によるデジタルフィルタ回路７００の構成例を示すブロック図である。デジタルフィルタ回路７００は、周波数領域でフィルタ処理を行う周波数領域フィルタ回路である。具体的には、入力データとして入力される時間領域の信号は、ＦＦＴにより周波数領域のデータに変換された後にフィルタ処理が実施される。そして、フィルタ処理後の信号は、ＩＦＦＴにより時間領域の信号に再変換されて出力信号として出力される。【００１５】
デジタルフィルタ回路７００は、オーバーラップ付加回路７１０と、ＦＦＴ回路７１１と、フィルタ演算回路７１２と、ＩＦＦＴ回路７１３と、オーバーラップ除去回路７１４と、を備える。【００１６】
オーバーラップ付加回路７１０は、時間領域の入力信号である入力データから、Ｎ個のデータ（Ｎは正整数）からなるブロックを順次生成し、ＦＦＴ回路７１１へ出力する。このとき、オーバーラップ付加回路７１０は、各ブロックに対して、直前のブロックとＭ個のデータ（Ｍは正整数）だけオーバーラップさせる。オーバーラップされるデータ数の個数Ｍを、以降、「オーバーラップ量」という。そして、各ブロックの、オーバーラップされた部分を「オーバーラップ部分」という。【００１７】
オーバーラップ量Ｍは、予め決定された固定値とされることがある。その場合、オーバーラップ値Ｍの値に合わせてオーバーラップ付加回路７１０及びオーバーラップ除去回路７１４が構成される。あるいは、例えば、ＣＰＵ（Central Processing Unit）などの上位回路（図示せず）から与えられるオーバーラップ量Ｍの設定値をオーバーラップ付加回路７１０及びオーバーラップ除去回路７１４が参照し、動作時に設定してもよい。なお、オーバーラップ付加回路７１０は、例えば、２ポートメモリにより構成することができる。【００１８】
ＦＦＴ回路７１１は、オーバーラップ付加回路７１０から出力される、Ｍ個のデータがオーバーラップされた時間領域の入力信号に対して、ＦＦＴを行い、周波数領域の信号に変換して、フィルタ演算回路７１２へ出力する。【００１９】
フィルタ演算回路７１２は、ＦＦＴ回路７１１によって変換された周波数領域の信号に対してフィルタ処理を行い、ＩＦＦＴ回路７１３へ出力する。例えば、デジタルフィルタ回路７００が通信チャネルにおける信号歪みの等化処理を実行する場合、フィルタ演算回路７１２は、複素数乗算器で構成することができる。【００２０】
ＩＦＦＴ回路７１３は、フィルタ演算回路７１２から出力されるフィルタ処理後の周波数領域の信号に対して、ＩＦＦＴを行い、時間領域の信号に再変換して、オーバーラップ除去回路７１４へ出力する。【００２１】
オーバーラップ除去回路７１４は、ＩＦＦＴ回路７１３によって再変換された時間領域の信号であるＮ個のデータからなる各ブロックの両端から合計Ｍ個のデータを除去する。
このとき除去される部分が前述の「除去部分」であり、そのデータの個数はオーバーラップ量Ｍに等しい。そして、オーバーラップ除去回路７１４は、オーバーラップ部分に含まれる「出力部分」とオーバーラップしていないブロックの中央部分のデータとを出力データとして出力する。【００２２】
以下、図８に示すデジタルフィルタ回路７００の動作について、図９を参照して説明する。図９は、図８に示すデジタルフィルタ回路の動作の一例を示す動作図である。以下の説明において、処理ステップ（１）〜（５）は、図９における処理ステップ（１）〜（５）にそれぞれ対応する。【００２３】
（１）オーバーラップ付加処理
オーバーラップ付加回路７１０は、時間領域の入力信号である入力データから、Ｎ個のデータ（Ｎは正整数）からなるブロックを順次生成する。このとき、オーバーラップ付加回路７１０は、直前のブロックとＭ個のデータだけ重複（オーバーラップ）させる。
入力データを
ｘ(i)  （i＝0，1，・・・）
としたとき、Ｎデータのブロックは
ｘ(j)  （j＝m(N−M)−N〜m(N−M)−1，mは正整数）
で表される。ここで、ＮはＦＦＴブロックサイズ、Ｍはオーバーラップ量である。【００２４】
（２）ＦＦＴ処理
ＦＦＴ回路７１１は、時間領域の信号データからなるブロックに対して、ＦＦＴを行い、周波数領域の信号データからなるブロックに変換する。
Ｎ個の時間領域の信号データからなるブロックをあらためて
ｘ(n)  （n＝0，1，・・・，N−1）
とすると、ＦＦＴ処理後の周波数領域のブロックは
Ｘ(k)  （k＝0，1，・・・，N−1）
で与えられる。【００２５】
（３）周波数領域フィルタ処理
フィルタ演算回路７１２は、ＦＦＴ処理後のブロックを構成する周波数領域の各信号データに対して、フィルタ処理を行う。
フィルタ処理前のブロックＸ(k)に対するフィルタ処理後のブロックは
Ｘ'(k)＝Ｈ(k)・Ｘ(k)  （k＝0，1，・・・，N−1）
で与えられる。ここで、Ｈ(k)はフィルタ係数を示す。【００２６】
（４）ＩＦＦＴ処理
ＩＦＦＴ回路７１３は、フィルタ処理後の周波数領域の信号データからなるブロックに対して、ＩＦＦＴを行い、時間領域の信号データからなるブロックに再変換する。
ＩＦＦＴ処理前のブロックＸ'(k)に対するＩＦＦＴ処理後のブロックは、
ｙ(n)  （n＝0，1，・・・，N−1）
で与えられる。【００２７】
（５）オーバーラップ除去処理
オーバーラップ除去回路７１４は、ＩＦＦＴ処理後のＮ個の信号データからなるブロックｙ(n)から、ブロック先頭及び末端からそれぞれＭ／２個のオーバーラップ分のデータ、すなわち除去部分のデータを除いた中央部分を切り出す。
これにより、除去部分のデータが除去され、ブロックｙ(n)のオーバーラップ部分に含まれる出力部分と、オーバーラップしていない中央部とからなる（Ｎ−Ｍ）個の信号データ系列
ｙ'(j)  （j＝M／2〜(N−1)−M／2）
が生成される。【００２８】
処理の内容をＦＤＥ等には限定しない、一般のフィルタ処理にオーバーラップ処理を用いるデジタルフィルタ回路も存在する（例えば、特許文献６参照）。特許文献６のデジタルフィルタ回路も、オーバーラップ付加処理、ＦＦＴ処理、周波数領域フィルタ処理、ＩＦＦＴ処理、及びオーバーラップ除去処理を行う。【００２９】
ところで、オーバーラップ処理を用いるフィルタにおける必要なオーバーラップ量は、実行されるフィルタ処理のインパルス応答長に基づいて決定される。さらに、ＦＦＴの処理ブロックの大きさは、必要なオーバーラップ量よりも大きい必要がある。従って、ＦＦＴの処理ブロックの大きさは、フィルタ処理のインパルス応答長に応じて決定される。【００３０】
サイズが変動するブロックに対してＦＦＴを行う処理装置の、ハードウェア量を減少させる技術もある（例えば、特許文献７参照）。特許文献７の直交変換プロセッサは、ＦＦＴベクトル（「処理ブロック」に相当）の長さに適合して、メモリサイズを決定したり、不要な回路ブロックを無効にしたり、ハードウェアを時分割で動作させたりする。
【先行技術文献】
【特許文献】
【００３１】
【特許文献１】特開平８−１３７８３２号公報  （第３−５頁、図２５）
【特許文献２】特開２００１−５６８０６号公報  （第５頁、図１）
【特許文献３】特開２０１２−２２５００号公報  （第５頁、図１）
【特許文献４】特開２００６−３０４１９２公報  （第４−５頁、図４）
【特許文献５】特開２０１０−１３０３５５公報  （第３−６頁、図６）
【特許文献６】国際公開第２０１２／０８６２６２号  （第３−４頁、図１）
【特許文献７】特表２００８−５０６１９１  （第１１−１２頁、図１１、１２）
【非特許文献】
【００３２】
【非特許文献１】J. W. Cooley, J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series," Mathematics of Computation, US, American Mathematical Society, Apr. 1965, Vol.19, No. 90, pp. 297-301
【非特許文献２】D. P. Kolba, "A Prime Factor FFT Algorithm Using High-Speed Convolution," IEEE Trans. on Acoustics, US, IEEE Signal Processing Society, Aug. 1977, Vol.29, No.4 , pp. 281-294
【発明の概要】
【発明が解決しようとする課題】
【００３３】
上記のように、ＦＦＴの処理ブロックの大きさは、フィルタ処理のインパルス応答長に依存する。従って、インパルス応答長が大きくなると、必要なオーバーラップ量、及びＦＦＴの処理ブロックも大きくなする。その結果、処理に必要な回路規模や消費電力が増大するという問題がある。【００３４】
このように、一般に、ＦＦＴと周波数領域のフィルタ処理とを併用し、さらに、オーバーラップ処理を用いるときには、フィルタのインパルス応答長が長いほど、処理に必要な回路規模や消費電力が大きくなる。従って、フィルタの特性に応じて、動作する回路の規模を最適化し、消費電力を最小限に抑えることが望ましい。【００３５】
しかし、特許文献１−３や非特許文献１、２に記載されたＦＦＴ装置では、処理ブロックの変更に対応した、動作回路の規模の最適化や消費電力制御等の制御は特に行われない。【００３６】
また、特許文献４−６に記載されたオーバーラップを用いるフィルタ方式でも、フィルタのインパルス応答に着目した処理は行われていない。従って、特許文献４−６に記載された方式でも上記の問題を解決することができない。【００３７】
特許文献７の直交変換プロセッサは、メモリサイズを決定したり、不要な回路ブロックを無効にしたり、ハードウェアを時分割で動作させたりするものの、ＦＦＴ／ＩＦＦＴ処理自体における並べ替え処理は必要である。一般に並べ替え処理には、処理ブロックのデータをすべて記憶できるだけの容量をもつメモリが必要である。そのため、フィルタ処理のインパルス応答長が大きく、処理ブロックの大きさが大きいときには大規模のメモリが必要となり、処理に必要な回路規模や消費電力が増大するという問題がある。
（発明の目的）
本発明は、ＦＦＴと周波数領域におけるフィルタ処理を併用する場合に、消費電力を削減することができるデジタルフィルタ装置、デジタルフィルタ処理方法及びデジタルフィルタプログラムが記憶された記憶媒体を提供することを目的とする。
【課題を解決するための手段】
【００３８】
本発明のデジタルフィルタ装置は、連続する（Ｎ−Ｍ）個の時間領域の入力データ（Ｎは正整数、ＭはＮより小さい正整数）を含む第１の入力ブロックに、第１の入力ブロックの直前の連続するＮ個の時間領域の入力データを含む第２の入力ブロックの最後の連続するデータをオーバーラップ量であるＭ個だけ付加し、オーバーラップブロックを生成するオーバーラップ付加手段と、オーバーラップブロック及び第２の入力ブロックのそれぞれを、高速フーリエ変換処理により周波数領域の第１の周波数領域ブロック及び第２の周波数領域ブロックに変換するフーリエ変換手段と、第１の周波数領域ブロック及び第２の周波数領域ブロックのそれぞれに対してフィルタ処理を行い、第１の処理後ブロック及び第２の処理後ブロックを生成するフィルタ演算手段と、第１の処理後ブロック及び第２の処理後ブロックのそれぞれを、逆高速フーリエ変換処理により時間領域の第１の時間領域ブロック及び第２の時間領域ブロックに変換する逆フーリエ変換手段と、第１の時間領域ブロック及び第２の時間領域ブロックのそれぞれが時間的にオーバーラップするオーバーラップ部分のうち、第１の時間領域ブロックの時間軸の前端のｋ個（ｋはＭより小さい正整数）のデータ及び第２の時間領域ブロックの時間軸の後端の（Ｍ−ｋ）個のデータを除去部分データとして除去し、出力データを生成するオーバーラップ除去手段と、第１の時間領域ブロックの除去部分データと、第２の時間領域ブロックのオーバーラップ部分のうちの除去部分データ以外の出力部分データとを比較してオーバーラップ部分に含まれるデータが発生させる歪み量を検出し、歪み量に基づいてオーバーラップ量を制御するオーバーラップ誤差検出手段と、を備えることを特徴とする。【００３９】
本発明のデジタルフィルタ処理方法は、連続する（Ｎ−Ｍ）個の時間領域の入力データ（Ｎは正整数、ＭはＮより小さい正整数）を含む第１の入力ブロックに、第１の入力ブロックの直前の連続するＮ個の時間領域の入力データを含む第２の入力ブロックの最後の連続するデータをオーバーラップ量であるＭ個だけ付加してオーバーラップブロックを生成し、オーバーラップブロック及び第２の入力ブロックのそれぞれを、高速フーリエ変換処理により周波数領域の第１の周波数領域ブロック及び第２の周波数領域ブロックに変換し、第１の周波数領域ブロック及び第２の周波数領域ブロックのそれぞれに対してフィルタ処理を行って第１の処理後ブロック及び第２の処理後ブロックを生成し、第１の処理後ブロック及び第２の処理後ブロックのそれぞれを、逆高速フーリエ変換処理により時間領域の第１の時間領域ブロック及び第２の時間領域ブロックに変換し、第１の時間領域ブロック及び第２の時間領域ブロックのそれぞれが時間的にオーバーラップするオーバーラップ部分のうち、第１の時間領域ブロックの時間軸の前端のｋ個（ｋはＭより小さい正整数）のデータ及び第２の時間領域ブロックの時間軸の後端の（Ｍ−ｋ）個のデータを除去部分データとして除去して出力データを生成し、第１の時間領域ブロックの除去部分データと、第２の時間領域ブロックのオーバーラップ部分のうちの除去部分データ以外の出力部分データとを比較してオーバーラップ部分に含まれるデータが発生させる歪み量を検出し、歪み量に基づいてオーバーラップ量を制御することを特徴とする。【００４０】
本発明の記憶媒体に記憶されているデジタルフィルタプログラムは、デジタルフィルタ装置が備えるコンピュータを、連続する（Ｎ−Ｍ）個の時間領域の入力データ（Ｎは正整数、ＭはＮより小さい正整数）を含む第１の入力ブロックに、第１の入力ブロックの直前の連続するＮ個の時間領域の入力データを含む第２の入力ブロックの最後の連続するデータをオーバーラップ量であるＭ個だけ付加し、オーバーラップブロックを生成するオーバーラップ付加手段と、オーバーラップブロック及び第２の入力ブロックのそれぞれを、高速フーリエ変換処理により周波数領域の第１の周波数領域ブロック及び第２の周波数領域ブロックに変換するフーリエ変換手段と、第１の周波数領域ブロック及び第２の周波数領域ブロックのそれぞれに対してフィルタ処理を行い、第１の処理後ブロック及び第２の処理後ブロックを生成するフィルタ演算手段と、第１の処理後ブロック及び第２の処理後ブロックのそれぞれを、逆高速フーリエ変換処理により時間領域の第１の時間領域ブロック及び第２の時間領域ブロックに変換する逆フーリエ変換手段と、第１の時間領域ブロック及び第２の時間領域ブロックのそれぞれが時間的にオーバーラップするオーバーラップ部分のうち、第１の時間領域ブロックの時間軸の前端のｋ個（ｋはＭより小さい正整数）のデータ及び第２の時間領域ブロックの時間軸の後端の（Ｍ−ｋ）個のデータを除去部分データとして除去し、出力データを生成するオーバーラップ除去手段と、第１の時間領域ブロックの除去部分データと、第２の時間領域ブロックのオーバーラップ部分のうちの除去部分データ以外の出力部分データとを比較してオーバーラップ部分に含まれるデータが発生させる歪み量を検出し、歪み量に基づいてオーバーラップ量を制御するオーバーラップ誤差検出手段と、として機能させることを特徴とする。
【発明の効果】
【００４１】
本発明によれば、ＦＦＴと周波数領域におけるフィルタ処理を併用する場合に、消費電力を削減することができる。
【図面の簡単な説明】
【００４２】
【図１】本発明の実施形態におけるデジタルフィルタ回路２００の構成を示すブロック図である。
【図２】本発明の実施形態におけるＦＦＴ回路２１１の構成を示すブロック図である。
【図３】本発明の実施形態における逐次順序に従うデータ組の配列を示す図である。
【図４】本発明の実施形態におけるビットリバース順序に従うデータ組の配列を示す図である。
【図５】本発明の実施形態におけるデータ並べ替え処理部の構成例１００を示すブロック図である。
【図６】本発明の実施形態におけるオーバーラップ誤差検出部２１５の構成を示すブロック図である。
【図７】２段階のバタフライ演算を用いる６４ポイントＦＦＴ処理のデータフロー５００を示す図である。
【図８】ＦＦＴ回路７００の構成を示すブロック図である。
【図９】オーバーラップＦＤＥ方式による示すデジタルフィルタ回路の動作の一例を示す動作図である。
【発明を実施するための形態】
【００４３】
（第１の実施形態）
次に本発明の実施の形態について図面を参照して詳細に説明する。図１は、本発明の実施形態におけるデジタルフィルタ回路２００の構成例を示すブロック図である。
【００４４】
デジタルフィルタ回路２００は、オーバーラップ方式により、ＦＤＥ等のフィルタ処理を行う。デジタルフィルタ回路２００は、オーバーラップ付加回路２１０と、ＦＦＴ回路２１１と、フィルタ演算回路２１２と、ＩＦＦＴ回路２１３と、オーバーラップ除去回路２１４と、オーバーラップ誤差検出部２１５と、を備える。
【００４５】
オーバーラップ付加回路２１０は、時間領域の入力信号である入力データから、連続するＮ個のデータ（Ｎは正整数）からなる入力ブロックを順次生成し、ＦＦＴ回路２１１へ出力する。このとき、オーバーラップ付加回路２１０は、各入力ブロックに対して、直前のブロックの最後のＭ個のデータ（Ｍは正整数）をオーバーラップさせる。「オーバーラップ」とは、各入力ブロックの先頭の所定のＸ個のデータ（Ｘは正整数）を、直前のブロックの最後のＸ個のデータと同一データとし、２つのブロックに重複したＸ個のデータが含まれるようにすることを意味する。オーバーラップ付加回路２１０は、オーバーラップされたＭ個のデータを含む、連続するＮ個のデータからなる「オーバーラップブロック」を生成する。なお、オーバーラップ付加回路２１０は、例えば、２ポートメモリにより構成することができる。
【００４６】
ＦＦＴ回路２１１は、オーバーラップ付加回路２１０から出力されたオーバーラップブロックに対して、Ｎポイントの高速フーリエ変換（ＦＦＴ）を行い、周波数領域の信号に変換する。そして、ＦＦＴ回路２１１は、Ｎ個の周波数領域のデータからなる「周波数領域ブロック」をフィルタ演算回路２１２へ出力する。
【００４７】
フィルタ演算回路２１２は、ＦＦＴ回路２１１から出力された周波数領域ブロックに対してフィルタ処理を行い、「処理後ブロック」をＩＦＦＴ回路２１３へ出力する。例えば、デジタルフィルタ回路２００が通信チャネルにおける信号歪みの等化処理、すなわちＦＤＥを実行する場合であれば、フィルタ演算回路２１２は、複素数乗算器で構成することができる。
【００４８】
ＩＦＦＴ回路２１３は、フィルタ演算回路２１２から出力された処理後ブロックに対して、Ｎポイントの逆高速フーリエ変換（ＩＦＦＴ）を行い、時間領域の信号に再変換する。そして、ＩＦＦＴ回路２１３は、Ｎ個の時間領域のデータからなる「時間領域ブロック」をオーバーラップ除去回路２１４へ出力する。
【００４９】
オーバーラップ除去回路２１４は、ＩＦＦＴ回路２１３から出力された各時間領域ブロックの時間軸の両端から合計Ｍ個の「除去部分データ」を除去する。そして、オーバーラップ除去回路２１４は、時間領域ブロックのオーバーラップ部分の「出力部分データ」及びオーバーラップしていない中央部分のみを取り出し、「出力データ」として出力する。
【００５０】
オーバーラップ量Ｍは、予め所定の値に設定される。そして、後述のように、オーバーラップ量Ｍは、オーバーラップ量決定部２２２によって適切な値に更新される。オーバーラップ付加回路２１０、およびオーバーラップ除去回路２１４は、それぞれ、その時点のオーバーラップ量Ｍに従って、オーバーラップの付加、または除去を行う。なお、オーバーラップ量Ｍは、ＦＦＴのブロックサイズＮよりも小さい。
【００５１】
オーバーラップ誤差検出部２１５は、連続する２つのＦＦＴブロックのオーバーラップ部分における、最終的には除去される除去部分データ及び除去されずに出力される出力部分データの値を比較することによって、オーバーラップ部分の歪み量を検出する。この比較によってオーバーラップ部分の歪み量が検出される理由は、出力部分のデータは歪みを発生させない正常な値であり、除去部分のデータは歪みを発生させる場合があるからである。
【００５２】
オーバーラップ量決定部２２２は、検出した歪み量が所定の規定値よりも大きい場合にはオーバーラップ量Ｍを増加させる。オーバーラップ量決定部２２２は、検出した歪み量が所定の規定値よりも小さい場合にはオーバーラップ量Ｍを減少させる。そのために、オーバーラップ量決定部２２２は、オーバーラップ量の増加又は減少を指示する制御信号２１６を、オーバーラップ付加回路２１０及びオーバーラップ除去回路２１４へ出力する。
【００５３】
次に、デジタルフィルタ回路２００を構成するＦＦＴ回路２１１の構成を説明する。
【００５４】
図２は、本発明の実施形態におけるＦＦＴ回路２１１の構成例を示すブロック図である。ＦＦＴ回路２１１は、図７に示されたデータフロー５００に従って、基数を８とする２段階のバタフライ処理に分解された６４ポイントＦＦＴを、パイプライン回路方式によって処理する。ＦＦＴ回路２１１は、時間領域のデータｘ(n)（n＝0，1，・・・，63）を入力し、ｘ(n)をＦＦＴ処理によりフーリエ変換して周波数領域の信号Ｘ(k)（k＝0，1，・・・，63）を生成し、出力する。
【００５５】
図７のデータフローに示した６４ポイントＦＦＴ処理、すなわち各々８データを含む、８組のデータの組に対する処理のすべてを、組ごとに個別の回路で実現するためには、膨大な規模の回路を要する。そのため、ＦＦＴ回路２１１は、８データ並列で６４ポイントＦＦＴ処理を行うものとする。この場合、ＦＦＴ回路２１１は、時間領域のデータｘ(n)を入力し、ＦＦＴ処理によりフーリエ変換した周波数領域の信号Ｘ(k)を生成して出力する。このとき、入力データｘ(n)として、８データずつ、８サイクルの期間に、図３に示す順序で、合計で６４個のデータが入力される。なお、ここでは、図３の表の内容として示された、0から63までの数字は、ｘ(n)の添え字nを意味する。
【００５６】
具体的には、１サイクル目に、データ組Ｐ１を構成するｘ(0)，ｘ(1)，・・・，ｘ(7)の８データが入力される。そして、２サイクル目に、データ組Ｐ２を構成するｘ(8)，ｘ(9)，・・・，ｘ(15)の８データが入力される。以降同様に、３サイクル目から８サイクル目まで、データ組Ｐ３〜Ｐ８を構成するデータが入力される。
【００５７】
同様に、出力データＸ(k)として、８データずつ、８サイクルの期間に、図３に示す順序で、６４データが出力される。なお、ここで図３の表の内容として示された、0から63までの数字は、Ｘ(k)の添え字kを意味する。
【００５８】
具体的には、１サイクル目に、データ組Ｐ１を構成するＸ(0)，Ｘ(1)，・・・，Ｘ(7)の８データが出力される。２サイクル目に、データ組Ｐ２を構成するＸ(8)，Ｘ(9)，・・・，Ｘ(15)の８データが出力される。以降同様に、３サイクル目から８サイクル目まで、データ組Ｐ３〜Ｐ８を構成するデータが出力される。
【００５９】
ＦＦＴ回路２１１は、第１のデータ並べ替え処理部１１、第１のバタフライ演算処理部２１、第２のデータ並べ替え処理部１２、ひねり乗算処理部３１、第２のバタフライ演算処理部２２、及び第３のデータ並べ替え処理部１３、を備える。ＦＦＴ回路２１１は、第１のデータ並べ替え処理、第１のバタフライ演算処理、第２のデータ並べ替え処理、ひねり乗算処理、第２のバタフライ演算処理、及び第３のデータ並べ替え処理を、パイプライン処理する。
【００６０】
第１のデータ並べ替え処理部１１、及び第２のデータ並べ替え処理部１２は、データ並べ替えのためのバッファ回路である。第１のデータ並べ替え処理部１１、及び第２のデータ並べ替え処理部１２は、それぞれ、第１のバタフライ演算処理部２１の前と後とで、ＦＦＴ処理のアルゴリズム上のデータの依存関係に基づいた、データシーケンスの並べ替えを行う。
【００６１】
第３のデータ並べ替え処理部１３も、同様に、データ並べ替えのためのバッファ回路である。すなわち、第３のデータ並べ替え処理部１３は、第２のバタフライ演算処理部２２の後で、ＦＦＴ処理のアルゴリズム上のデータの依存関係に基づいた、データシーケンスの並べ替えを行う。
【００６２】
具体的には、第１のデータ並べ替え処理部１１は、入力データｘ(n)の入力順序である図３に示す「逐次順序」を、第１のバタフライ演算処理部２１に入力する順序である図４に示す「ビットリバース順序」に並べ替える。
【００６３】
図４に示すビットリバース順序は、図７に示したデータフロー図における、１段目の基数８のバタフライ処理５０２への入力データ組に対応する。具体的には、１サイクル目に、データ組Ｐ１を構成するｘ(0)，ｘ(8)，・・・，ｘ(56)の８データを入力する。そして、２サイクル目に、データ組Ｐ２を構成するｘ(1)，ｘ(9)，・・・，ｘ(57)の８データを入力する。以降、３サイクル目から８サイクル目まで同様にして、データ組Ｐ３〜Ｐ８を構成するデータを入力する。
【００６４】
ここで、「逐次順序」と「ビットリバース順序」とについて、具体的に説明する。「逐次順序」とは、図３に示された、８つのデータ組Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８の順序をいう。データ組Ｐs（ｓは処理サイクルの順を示す値。s＝1，・・・，8）は、それぞれ、ｐs(0)からｐs(7)まで、順に並んだ８個のデータからなり、ｐs(i)は、
ｐs(i)＝8（s−1）＋i
である。そして、各データ組は、処理のサイクルの進行に対応して、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８の順に並べられている。つまり、逐次順序とは、i×s個のデータを、先頭のデータからｉ個ずつデータ順に並べたデータ組をｓ個作成し、そのデータ組をサイクル順に並べたものである。
【００６５】
「ビットリバース順序」とは、図４に示された、８つのデータ組Ｑ１、Ｑ２、Ｑ３、Ｑ４、Ｑ５、Ｑ６、Ｑ７、Ｑ８の順序をいう。データ組Ｑｓは、それぞれ、ｑs(0)からｑs(7)までの８個のデータからなり、ｑs(i)は、
ｑs(i)＝（s−1）＋8i
である。そして、各データ組は、処理のサイクルの進行に対応して、Ｑ１、Ｑ２、Ｑ３、Ｑ４、Ｑ５、Ｑ６、Ｑ７、Ｑ８の順に並べられている。つまり、ビットリバース順序とは、逐次順序で入力されたi×s個のデータを、先頭のデータからｓ個ずつサイクル順に並べ、同じサイクルのｉ個のデータを１つの組としてデータ順に並べたものである。
【００６６】
以上のように、ビットリバース順序の各データ組は、逐次順序の各組が設定されれば一意に定まる。ビットリバース順序の各データ組Ｑs（s＝1，・・・，8）を構成するデータのｉデータ目は、逐次順序に従ったサイクルｉにおける、ｓデータ目のデータである。すなわち、
Ｑs(i)＝Ｐi(s)
である。このように、Ｑs(i)とＰi(s)とは、各データ組を構成するデータについての、サイクルの進行に対する順序とデータ位置に対する順序が入れ替えられた関係にある。従って、ビットリバース順序で入力されたデータを、ビットリバース順序に従って並べ替えると、逐次順序になる。
【００６７】
図３における各行ｐs(i)、及び図４における８つの行ｑs(i)は、それぞれ、次段のｉデータ目に入力されるデータを示す。各データ組に含まれる８個の数字は、ＦＦＴのポイントのうちの１個を特定する識別情報であり、具体的にはｘ(n)の添え字ｎの値である。
【００６８】
なお、逐次順序及びビットリバース順序は、図３、４に例示されたものに限定されない。すなわち、逐次順序の各データ組は、上記のように、ＦＦＴのポイント数、サイクル数、並列に処理するデータ数に応じて、データが順に並べられて作成されればよい。そして、ビットリバース順序の各データ組は、上記のように、逐次順序で入力されるデータの、サイクルの進行に対する順序とデータ位置に対する順序とが入れ替られて作成されればよい。
【００６９】
第１のバタフライ演算処理部２１は、図７のデータフロー５００において２回行われる基数８のバタフライ演算処理の、１回目のバタフライ演算処理５０２（第１のバタフライ演算処理）を処理するバタフライ回路である。第１のバタフライ演算処理部２１は、バタフライ演算処理の結果を、データｙ(n)（n＝0，1，・・・，63）として、図３に示す逐次順序で出力する。
【００７０】
第２のデータ並べ替え処理部１２は、第１のバタフライ演算処理部２１が逐次順序で出力するデータｙ(n)を、第２のバタフライ演算処理部２２に入力するために、図４に示すビットリバース順序に並べ替える。
【００７１】
ひねり乗算処理部３１は、第１のバタフライ演算処理後に、ＦＦＴ演算における複素平面上の複素回転を処理する回路であり、図７のデータフロー５００における、ひねり乗算処理５０４に対応する。なお、ひねり乗算処理では、データの並べ替えは行われない。
【００７２】
第２のバタフライ演算処理部２２は、図７のデータフロー図における、２回目の基数８のバタフライ処理５０３を処理するバタフライ回路である。第２のバタフライ演算処理部２２は、ビットリバース順序で入力されるひねり乗算処理後のデータｙ'(n)（n＝0，1，・・・，63）に対してバタフライ演算処理を行い、その結果Ｘ(k)（n＝0，1，・・・，63）を、同じくビットリバース順序で出力する。
【００７３】
第３のデータ並べ替え処理部１３は、第２のバタフライ演算処理部２２がビットリバース順序で出力するデータＸ(k)を、図３に示す逐次順序に並べ替える。
【００７４】
データ並べ替え処理部は、入力されたデータを一旦記憶し、記憶したデータの選択及び出力を制御することによって、図２に示す逐次順序、図３に示すビットリバース順序、及び図４に示す逐次順序のそれぞれに従ったデータの並べ替え処理を実現する。以下に、データ並べ替え処理部の具体例を示す。
【００７５】
第１のデータ並べ替え処理部１１、第２のデータ並べ替え処理部１２、及び、第３のデータ並べ替え処理部１３は、例えば図５に示すデータ並べ替え処理部１００で実現することができる。
【００７６】
データ並べ替え処理部１００は、入力情報１０３として入力される８個のデータからなるデータ組Ｄ１〜Ｄ８を、ＦＩＦＯバッファ（First In First Out Buffer。先入れ先出しバッファ）における先入れ順序で入力して、データ記憶位置１０１ａ〜１０１ｈに書き込み、記憶させる。具体的には、データ記憶位置１０１ａ〜１０１ｈのそれぞれに、データ組Ｄ１〜Ｄ８が記憶される。
【００７７】
次に、データ並べ替え処理部１００は、ＦＩＦＯバッファにおける先出し順序で、記憶されているデータを出力する。具体的には、データ並べ替え処理部１００は、データ読み出し位置１０２ａ〜１０２ｈのそれぞれから８個のデータを読み出して１つのデータ組とし、８つのデータ組Ｄ１’〜Ｄ８’を出力情報１０４として出力する。このように、データ組Ｄ１’〜Ｄ８’は、サイクル順に並べられたデータ組Ｄ１〜Ｄ８に含まれるデータを、データ位置の順に並べ替えて１つの組としたものである。
【００７８】
以上説明したように、ＦＦＴ回路２１１において、第１のデータ並べ替え処理部１１、第２のデータ並べ替え処理部１２、及び第３のデータ並べ替え処理部１３によって、図２に示す逐次順序、図３に示すビットリバース順序、及び図４に示す逐次順序のそれぞれに従った３回の並べ替え処理が必要となる。なぜなら、ＦＦＴ回路２１１は、８データ並列で６４ポイントＦＦＴ処理を行うため、ＦＦＴ処理に８サイクルが必要であり、サイクル間をまたがったデータの並べ替えが必要となるからである。
【００７９】
ＩＦＦＴ回路２１３もＦＦＴ回路２１１と同様の構成で実現することができる。
【００８０】
次に、デジタルフィルタ回路２００を構成するオーバーラップ誤差検出部２１５の構成を説明する。
【００８１】
図６は、本発明の実施形態に係るオーバーラップ誤差検出部２１５の構成例を示すブロック図である。オーバーラップ誤差検出部２１５は、第１の誤差比較部２２１ａと、第２の誤差比較部２２１ｂと、オーバーラップ量決定部２２２と、を含む。
【００８２】
オーバーラップ誤差検出部２１５は、２つの連続するＦＦＴブロックであるＦＦＴブロックＦＢ(i)とＦＦＴブロックＦＢ(i＋1)とのそれぞれに含まれる、除去データとオーバーラップ出力データとを比較し、その結果に基づいてオーバーラップ量Ｍを決定する。オーバーラップ誤差検出部２１５の詳細な動作は以下の通りである。
【００８３】
第１の誤差比較部２２１ａは、ＦＢ(i)の除去部分データの値とＦＢ(i＋1)の出力部分データの値との比較によりＦＢ(i)の除去部分データの誤差を検出し、検出した誤差をオーバーラップ量決定部２２２に出力する。
【００８４】
同様に、第２の誤差比較部２２１ｂは、ＦＢ(i)の出力部分データの値とＦＢ(i＋1)の除去部分データの値との比較によりＦＢ(i＋1)の除去部分データの誤差を検出し、検出した誤差をオーバーラップ量決定部２２２に出力する。
【００８５】
オーバーラップ量決定部２２２は、第１の誤差比較部２２１ａから入力されたＦＢ(i)の除去部分データの誤差と、第２の誤差比較部２２１ｂから入力されたＦＢ(i＋1)の除去部分データの誤差とに基づいて、必要なオーバーラップ量を決定する。そして、オーバーラップ量決定部２２２は、オーバーラップ量の増加又は減少を指示する制御信号２１６を、オーバーラップ付加回路２１０及びオーバーラップ除去回路２１４へ出力する。
（実施形態の動作）
オーバーラップ誤差検出部２１５は、連続する２つのＦＦＴブロックのオーバーラップ部分において、除去部分データの値と出力部分データの値とを互いに比較することで、オーバーラップ部分の歪み量を検出する。この比較によってオーバーラップ部分の歪み量が検出される理由は、出力部分のデータは歪みを発生させる場合がない正常な値であり、除去部分のデータは歪みを発生させる場合があるからである。
【００８６】
オーバーラップ誤差検出部２１５は、検出した歪み量が所定の規定値よりも大きい場合には、オーバーラップ量Ｍを増加させる。オーバーラップ量決定部２１５は、検出した歪み量が所定の規定値よりも小さい場合には、オーバーラップ量Ｍを減少させる。そのために、オーバーラップ誤差検出部２１５は、オーバーラップ量の増加又は減少を指示する制御信号２１６を、オーバーラップ付加回路２１０及びオーバーラップ除去回路２１４へ出力する。
【００８７】
オーバーラップ付加回路２１０及びオーバーラップ除去回路２１４は、オーバーラップ量決定部２１５が出力する制御信号２１６が、オーバーラップ量の減少を指示する場合、オーバーラップ量Ｍを減少させる。一方、オーバーラップ付加回路２１０及びオーバーラップ除去回路２１４は、制御信号２１６が、オーバーラップ量の増加を指示する場合、オーバーラップ量Ｍを増加させる。そして、オーバーラップ付加回路２１０、オーバーラップ除去回路２１４は、それぞれ、オーバーラップ量Ｍに従って、オーバーラップの付加、除去を行う
（実施形態の効果）
ＦＦＴ処理されたブロックにおけるオーバーラップ部分の両端付近には、信号に歪みを発生させるデータが含まれる。そして、その歪みの量は、必要なオーバーラップ量に対して、実際のオーバーラップ量Ｍが小さい場合には大きく、オーバーラップ量Ｍが大きい場合には小さい。また、オーバーラップ量Ｍが大きいほど、処理量の合計が増加するので、デジタルフィルタ回路２００の消費電力も増加する。
【００８８】
そこで、以上のように、本実施形態のデジタルフィルタ回路２００は、連続する２つのＦＦＴブロックのオーバーラップ部分のデータを比較することによって、オーバーラップ部分に発生した歪みの量を検出する。そして、デジタルフィルタ回路２００は、検出した歪みの量が所定の規定値よりも大きい場合にはオーバーラップ量Ｍの値を増加させ、検出した歪みの量が小さい場合にはオーバーラップ量Ｍの値を減少させる。すなわち、デジタルフィルタ回路２００は、検出したオーバーラップ部分の歪みの大きさに応じて、オーバーラップ量Ｍを適応的に制御する。
【００８９】
その結果、本実施形態では、デジタルフィルタ回路２００の出力データが発生させる歪み量を適切な量に維持することができる。そして、本実施形態では、適切な歪み量を維持するために必要最小限のオーバーラップ量でフィルタ処理を行うので、フィルタ処理に要する消費電力を小さくすることができる。
【００９０】
なお、本実施形態では、オーバーラップ量決定部２２２は、２つの連続するＦＦＴブロックの前のブロック及び後のブロックのそれぞれの除去部分データの誤差を検出するために２つの誤差比較部を備え、オーバーラップ量を決定する。オーバーラップ量決定部２２２は、前のブロック又は後のブロックのいずれか一方の除去部分データの誤差を検出する誤差比較部のみを備え、その誤差比較部の出力のみから、必要なオーバーラップ量を決定してもよい。
【００９１】
また、本実施形態では、ＦＦＴ、ＩＦＦＴ、フィルタ処理等、各処理は、すべて個別の回路等の構成要素によって処理されることが想定されている。しかし、各実施形態の処理は、所定の装置が備えるコンピュータ、例えば、ＤＳＰ（Digital Signal Processor）等を用いたソフトウェアによって実行されてもよい。すなわち、各処理を行うコンピュータプログラムは、ＤＳＰ（図示なし）によって読み込まれ、実行される。
【００９２】
例えば、データの並べ替え処理を、プログラムを用いて行ってもよい。すなわち、ＤＳＰとメモリを用いて、メモリへのデータの書き込み及びメモリからのデータの読み出しをプログラムによって制御することによって、データの並べ替え処理を行ってもよい。さらに、本実施形態ではＦＦＴ処理を、プログラムを用いて行ってもよい。
【００９３】
以上のように、プログラムを用いて各処理を行っても、上述の実施形態の処理と同内容の処理を行うことができる。
【００９４】
なお、上記の処理プログラムは、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、フラッシュメモリ等の半導体記憶装置、あるいは光ディスク、磁気ディスク、光磁気ディスク等、非一時的な媒体に格納されてもよい。
【００９５】
この出願は、２０１３年１２月１３日に出願された日本出願特願２０１３−２５８２７２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【００９６】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【００９７】
１１    第１のデータ並べ替え処理部
１２    第２のデータ並べ替え処理部
１３    第３のデータ並べ替え処理部
２１    第１のバタフライ演算処理部
２２    第２のバタフライ演算処理部
３１    ひねり乗算処理部
１００    データ並べ替え処理部
１０１ａ〜１０１ｈ    データ記憶位置
１０２ａ〜１０２ｈ    データ読み出し位置
１０３    入力情報
１０４    出力情報
２００    デジタルフィルタ回路
２１０    オーバーラップ付加回路
２１１    ＦＦＴ回路
２１２    フィルタ演算回路
２１３    ＩＦＦＴ回路
２１４    オーバーラップ除去回路
２１５    オーバーラップ誤差検出部
２１６    制御信号
２２１ａ    第１の誤差比較部
２２１ｂ    第２の誤差比較部
２２２    オーバーラップ量決定部
５００    データフロー
５０１    データ並べ替え処理
５０２、５０３    バタフライ演算処理
５０４    ひねり乗算処理
５０５ａ〜５０５ｈ    部分データフロー
７００    デジタルフィルタ回路
７１０    オーバーラップ付加回路
７１１    ＦＦＴ回路
７１２    フィルタ演算回路
７１３    ＩＦＦＴ回路
７１４    オーバーラップ除去回路
【図１】
0006489021.tif 000002
【図２】
0006489021.tif 000003
【図３】
0006489021.tif 000004
【図４】
0006489021.tif 000005
【図５】
0006489021.tif 000006
【図６】
0006489021.tif 000007
【図７】
0006489021.tif 000008
【図８】
0006489021.tif 000009
【図９】
0006489021.tif 000010