(57)【要約】  デジタル信号処理を実行する回路の回路規模を小さくするために、複数の第１のデータを第１の順序で入力とし、複数の第１のデータを第３の順序に並べ替える第１データ並べ替え手段と、複数の第１のデータを第３の順序で入力とし、複数の第１のデータを第２の順序に並べ替える第２データ並べ替え手段とを含むデータ並べ替え処理手段を備える高速フーリエ変換装置とする。第１データ並べ替え手段は、複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として複数の第１のデータを第１の順序から第３の順序に並べ替え、第２データ並べ替え手段は、データ組に含まれる所定数のデータ間で並べ替えを行うことによって複数の第１のデータを第３の順序から第２の順序に並べ替える高速フーリエ変換装置とする。
2019031418.tif 000002
【特許請求の範囲】
【請求項１】
複数の第１のデータを第１の順序で入力とし、前記複数の第１のデータを第３の順序に並べ替える第１データ並べ替え手段と、
前記複数の第１のデータを前記第３の順序で入力とし、前記複数の第１のデータを第２の順序に並べ替える第２データ並べ替え手段とを含むデータ並べ替え処理手段を備え、
前記第１データ並べ替え手段は、
前記複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として前記複数の第１のデータを前記第１の順序から前記第３の順序に並べ替え、
前記第２データ並べ替え手段は、
前記データ組に含まれる前記所定数のデータ間で並べ替えを行うことによって前記複数の第１のデータを前記第３の順序から前記第２の順序に並べ替える高速フーリエ変換装置。
【請求項２】
前記第１データ並べ替え手段は、
第１の記憶回路を含み、
前記第２データ並べ替え手段は、
第２の記憶回路を含み、
前記第２の記憶回路は、
前記第１の記憶回路とは構成および特性が異なり、データの書込み処理および読み出し処理の処理単位に基づいて回路構成が決定される請求項１に記載の高速フーリエ変換装置。
【請求項３】
前記第１の記憶回路は、
複数のデータビットから構成されるワードの単位で書き込み処理および読み出し処理を実行し、
前記第２の記憶回路は、
前記ワードの単位に因らないデータの書き込み処理および読み出し処理を実行する請求項２に記載の高速フーリエ変換装置。
【請求項４】
前記第１データ並べ替え手段は、
連続する複数のサイクルにおいて並列に入力されるデータによって構成される前記データ組を移動単位として前記複数の第１のデータを前記第３の順序に並べ替える請求項２または３に記載の高速フーリエ変換装置。
【請求項５】
前記第１の記憶回路は、
前記第２の記憶回路よりも大きいサイクル数のデータを記憶する請求項４に記載の高速フーリエ変換装置。
【請求項６】
複数の入力データを入力とし、前記複数の入力データにバタフライ演算を実行することによって前記複数の第１のデータを前記第１の順序で前記データ並べ替え処理手段に出力する第１バタフライ演算処理手段と、
前記データ並べ替え処理手段から前記複数の第１のデータを前記第２の順序で入力とし、入力された前記複数の第１のデータに対して複素平面上の複素回転を処理した複数の第２のデータを出力するひねり乗算処理手段と、
前記ひねり乗算処理手段から前記複数の第２のデータを入力とし、入力された前記複数の第２のデータにバタフライ演算を実行して複数の出力データを出力する第２バタフライ演算処理手段とを含む請求項１乃至５のいずれか一項に記載の高速フーリエ変換装置。
【請求項７】
請求項１乃至６のいずれか一項に記載の高速フーリエ変換装置を含むデジタルフィルタ装置。
【請求項８】
複数の第１のデータを第１の順序で入力とし、
前記複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として前記複数の第１のデータを第３の順序に並べ替え、
前記データ組に含まれる前記所定数のデータ間で並べ替えを行うことによって、前記第３の順序に並べ替えられた前記複数の第１のデータを第２の順序に並べ替える第２並べ替え手段とを含むデータ並べ替え処理装置。
【請求項９】
複数の第１のデータを第１の順序で入力し、
前記複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として前記複数の第１のデータを第３の順序に並べ替え、
前記データ組に含まれる前記所定数のデータ間で並べ替えを行うことによって、前記第３の順序に並べ替えられた前記複数の第１のデータを第２の順序に並べ替えるデータ並べ替え処理を含む高速フーリエ変換処理方法。
【請求項１０】
複数の第１のデータを第１の順序で入力する処理と、
前記複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として前記複数の第１のデータを第３の順序に並べ替える処理と、
前記データ組に含まれる前記所定数のデータ間で並べ替えを行うことによって、前記第３の順序に並べ替えられた前記複数の第１のデータを第２の順序に並べ替える処理とを含む高速フーリエ変換処理をコンピュータに実行させるプログラムを記録させたプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル信号処理を行う高速フーリエ変換装置、データ並べ替え処理装置、高速フーリエ変換処理方法およびプログラムに関する。
【背景技術】
【０００２】
高速フーリエ変換（以下、ＦＦＴ：Fast Fourier Transform）処理は、デジタル信号処理における重要な処理の１つである。例えば、ＦＦＴは、伝送中の信号の波形歪みを補償するための周波数領域等化に用いられる。周波数領域等化では、時間領域上の信号データをＦＦＴによって周波数領域上のデータに変換した後に、等化のためのフィルタ処理を行う。そして、フィルタ処理後のデータを逆高速フーリエ変換（以下、ＩＦＦＴ：Inverse FFT）によって時間領域上の信号データに再変換し、元の時間領域上における信号の波形歪みが補償される。これ以降、ＦＦＴとＩＦＦＴとを区別しないときは、「ＦＦＴ／ＩＦＦＴ」と表記する。【０００３】
特許文献１には、バタフライ演算回路を用いて構成される高速フーリエ変換装置について開示されている。特許文献１の装置によれば、通常の離散的フーリエ変換のアルゴリズムが採用された装置に比べて計算量を減少できる。【０００４】
非特許文献１には、Cooley-Tukeyによるバタフライ演算について開示されている。非特許文献１の手法によれば、効率的なＦＦＴ／ＩＦＦＴ処理が可能となる。しかしながら、非特許文献１の手法には、データ点数が大きい場合、ＦＦＴ／ＩＦＦＴの回路が複雑になるという問題点があった。【０００５】
非特許文献２には、ポイント数の大きな演算を２つの小さなＦＦＴ／ＩＦＦＴに分解するPrime Factor法について開示されている。非特許文献２の手法を用いてポイント数の大きな処理を実行する場合、全ての処理を実行するためには膨大な規模の回路が必要となる。そのため、非特許文献２の手法を用いる場合、回路の規模を大きくせずに、ポイント数を分割して処理を繰り返すことが一般的である。【０００６】
バタフライ演算では、逐次的な順序（以下、逐次順序）に並べられたデータが、所定の規則に従った順序で読み出されて処理されるため、データの並べ替えが必要となる。例えば、バタフライ演算においては、逐次順序からビットリバース順序への並べ替えや、その逆のビットリバース順序から逐次順序への並べ替えが行われる。【０００７】
特許文献２には、入出力データおよび中間データをＲＡＭ（Random Access Memory）に格納してＦＦＴ処理を実行する高速フーリエ変換装置について開示されている。特許文献３には、バタフライ演算を並列することによってメモリ使用量を削減したＦＦＴ演算装置が開示されている。特許文献４には、入力データ点数が減少してもＦＦＴを実行できる高速フーリエ変換演算回路について開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平８−１３７８３２号公報
【特許文献２】特開２００１−５６８０６号公報
【特許文献３】特開２０１２−２２５００号公報
【特許文献４】特開平１０−２８３３４１号公報
【非特許文献】
【０００９】
【非特許文献１】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
【発明の概要】
【発明が解決しようとする課題】
【００１０】
逐次順序とビットリバース順序との並べ替えにおいては、あるサイクルで入力した複数のデータのそれぞれを、互いに異なるサイクルで出力する必要がある。したがって、特許文献２に基づいてデータ並べ替え処理回路をＲＡＭ回路で実現する場合、単一のＲＡＭ回路では構成できず、複数のＲＡＭ回路で構成する必要がある。【００１１】
一般に、ＲＡＭ回路は、データを記憶するメモリセル部分と、データの書き込みや読み出しを行うアドレスデコーダ回路やセンスアンプ回路などの周辺回路部分とによって構成される。したがって、同じ記憶容量の記憶装置をＲＡＭ回路で実現する場合であっても、単一のＲＡＭ回路で構成するより、複数のＲＡＭ回路で構成した方が、周辺回路の分だけ回路規模や消費電力が大きくなる。【００１２】
特許文献３の手法によれば、バタフライ演算処理を並列に実行することによってメモリ使用量を削減できる。しかし、バタフライ演算のみならずＦＦＴ処理やデータ並べ替え処理を並列化すると、並列数の増加に伴って必要なＲＡＭ回路の個数が増加し、回路規模や消費電力が大きくなってしまうという問題があった。【００１３】
特許文献４の手法によれば、様々なポイント数のＦＦＴに単一の回路で対応できる。しかしながら、特許文献４の手法には、ＦＦＴのポイント数が固定されている場合、複数のポイント数に対応するための構成が余分になるという問題点があった。【００１４】
本発明の目的は、上述した課題を解決するために、デジタル信号処理を実行する回路の回路規模を小さくすることができる高速フーリエ変換装置を提供することにある。
【課題を解決するための手段】
【００１５】
本発明の一態様の高速フーリエ変換装置は、複数の第１のデータを第１の順序で入力とし、複数の第１のデータを第３の順序に並べ替える第１データ並べ替え手段と、複数の第１のデータを第３の順序で入力とし、複数の第１のデータを第２の順序に並べ替える第２データ並べ替え手段とを含むデータ並べ替え処理手段を備え、第１データ並べ替え手段は、複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として複数の第１のデータを第１の順序から第３の順序に並べ替え、第２データ並べ替え手段は、データ組に含まれる所定数のデータ間で並べ替えを行うことによって複数の第１のデータを第３の順序から第２の順序に並べ替える。【００１６】
本発明の一態様のデータ並べ替え装置は、複数の第１のデータを第１の順序で入力とし、複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として複数の第１のデータを第３の順序に並べ替え、データ組に含まれる所定数のデータ間で並べ替えを行うことによって、第３の順序に並べ替えられた複数の第１のデータを第２の順序に並べ替える第２並べ替え手段とを含む。【００１７】
本発明の一態様の高速フーリエ変換処理方法においては、複数の第１のデータを第１の順序で入力し、複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として複数の第１のデータを第３の順序に並べ替え、データ組に含まれる所定数のデータ間で並べ替えを行うことによって、第３の順序に並べ替えられた複数の第１のデータを第２の順序に並べ替えるデータ並べ替え処理を含む。【００１８】
本発明の一態様のプログラムは、複数の第１のデータを第１の順序で入力する処理と、複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として複数の第１のデータを第３の順序に並べ替える処理と、データ組に含まれる所定数のデータ間で並べ替えを行うことによって、第３の順序に並べ替えられた複数の第１のデータを第２の順序に並べ替える処理とを含む高速フーリエ変換処理をコンピュータに実行させる。
【発明の効果】
【００１９】
本発明によれば、デジタル信号処理を実行する回路の回路規模を小さくすることができる高速フーリエ変換装置を提供することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施形態に係るデータ並べ替え処理装置の構成を示すブロック図である。
【図２】ＦＦＴ（Fast Fourier Transform）処理における逐次順序に従うデータの配列を示す図である。
【図３】ＦＦＴ処理におけるビットリバース順序に従うデータの配列を示す図である。
【図４】本発明の第１の実施形態に係るデータ並べ替え処理装置が逐次順序で入力する複数のデータを中間順序に並べ替える処理について説明するための図である。
【図５】本発明の第１の実施形態に係るデータ並べ替え処理装置が中間順序に並べ替えられた複数のデータをビットリバース順序に並べ替える処理について説明するための図である。
【図６】本発明の第２の実施形態に係るデータ並べ替え処理装置の構成を示すブロック図である。
【図７】本発明の第２の実施形態に係るデータ並べ替え処理装置の第１データ並べ替え部に含まれる第１データ振り分け部の動作について説明するためのタイムチャートである。
【図８】本発明の第２の実施形態に係るデータ並べ替え処理部に含まれる第１データ並べ替え部のＲＡＭ（Random Access Memory）回路の動作について説明するためのタイムチャートである。
【図９】本発明の第２の実施形態に係るデータ並べ替え処理装置の第１データ並べ替え部の第２データ振り分け部の動作について説明するためのタイムチャートである。
【図１０】本発明の第２の実施形態に係るデータ並べ替え処理装置の第２データ並べ替え部の動作について説明するためのタイムチャートである。
【図１１】一般的なデータ並べ替え処理装置の構成を示すブロック図である。
【図１２】本発明の第３の実施形態に係るデータ組内並べ替え装置の構成を示すブロック図である。
【図１３】本発明の第３の実施形態に係るデータ組内並べ替え装置の動作について説明するためのタイムチャートである。
【図１４】本発明の第４の実施形態に係るＦＦＴ装置を含む演算装置の構成を示すブロック図である。
【図１５】２段階のバタフライ演算を用いる６４ポイントＦＦＴ処理のデータフローについて説明するための概念図である。
【図１６】本発明の第５の実施形態に係るデジタルフィルタ装置の構成を示すブロック図である。
【図１７】本発明の第５の実施形態に係るデジタルフィルタ装置を実現するためのハードウェア構成の一例を示すブロック図である。
【発明を実施するための形態】
【００２１】
以下に、本発明を実施するための形態について図面を用いて説明する。ただし、以下に述べる実施形態には、本発明を実施するために技術的に好ましい限定がされているが、発明の範囲を以下に限定するものではない。なお、以下の実施形態の説明に用いる全図においては、特に理由がない限り、同様箇所には同一符号を付す。また、以下の実施形態において、同様の構成・動作に関しては繰り返しの説明を省略する場合がある。また、図面中の矢印の向きは、一例を示すものであり、ブロック間の信号の向きを限定するものではない。
【００２２】
（第１の実施形態）
まず、本発明の第１の実施形態に係るデータ並べ替え処理装置について図面を参照しながら説明する。本実施形態のデータ並べ替え処理装置は、ＦＦＴ（Fast Fourier Transform）処理のバタフライ演算で必要となる逐次順序とビットリバース順序とのデータの並べ替え処理を、中間順序を介した２段階のステップで実現する。以下においては、複数のデータを複数のサイクルに分けて並列処理する例について説明する。
【００２３】
（構成）
図１は、本実施形態に係るデータ並べ替え処理装置１０の構成を示すブロック図である。図１のように、本実施形態のデータ並べ替え処理装置１０（データ並べ替え処理手段とも呼ぶ）は、第１データ並べ替え部１１と、第２データ並べ替え部１２とを備える。
【００２４】
第１データ並べ替え部１１（第１データ並べ替え手段とも呼ぶ）は、複数のデータを第１の順序で入力とし、入力された複数のデータのうち少なくとも二つのデータによって構成されるデータ組を単位として複数のデータを並べ替える。言い換えると、第１データ並べ替え部１１は、複数の第１のデータを第１の順序で入力とし、複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として複数の第１のデータを中間順序（第３の順序とも呼ぶ）に並べ替える。第１データ並べ替え部１１は、中間順序に並べ替えた複数のデータを第２データ並べ替え部１２に出力する。
【００２５】
図１の例において、第１データ並べ替え部１１は、異なる複数の入力端（ｉｎ０〜７）から複数のデータを第１の順序で入力とする。例えば、第１の順序とは、逐次順序やビットリバース順序である。
【００２６】
そして、第１データ並べ替え部１１は、複数のデータを複数のサイクルに分けて入力とする。第１データ並べ替え部１１は、入力される複数のデータを一時的に記憶し、連続したサイクルに入力される複数のデータのうち少なくとも二つによって構成されるデータ組を並べ替えることによって複数のデータを中間順序とする。例えば、第１データ並べ替え部１１は、連続する複数のサイクルにおいて並列に入力されるデータによって構成される複数のデータ（データ組とも呼ぶ）を移動単位として複数の第１のデータを第３の順序に並べ替える。
【００２７】
第２データ並べ替え部１２（第２データ並べ替え手段とも呼ぶ）は、第１データ並べ替え部１１によって並べ替えられた複数のデータを入力とする。第２データ並べ替え部１２は、入力された複数のデータをデータ組内で並べ替えることによって第２の順序にする。言い換えると、第２データ並べ替え部１２は、複数の第１のデータを第３の順序で入力とし、データ組に含まれる所定数のデータ間で並べ替えを行うことによって、複数の第１のデータを第２の順序に並べ替える。第２データ並べ替え部１２は、複数のデータを第２の順序で出力する。
【００２８】
図１の例において、第２データ並べ替え部１２は、異なる複数の出力端（ｏｕｔ０〜７）から複数のデータを第２の順序で出力する。例えば、第２の順序とは、第１の順序が逐次順序の場合にはビットリバース順序、第１の順序がビットリバース順序の場合には逐次順序である。すなわち、本実施形態のデータ並べ替え処理装置１０は、２段階のステップで、逐次順序またはビットリバース順序（第１の順序）で入力された複数のデータをビットリバース順序または逐次順序（第２の順序）に並べ替えて出力する。
【００２９】
すなわち、本実施形態のデータ並べ替え処理装置１０は、２段階のステップで、複数のデータを第１の順序から第２の順序に並べ替える。
【００３０】
〔データ順序〕
ここで、本実施形態のデータ並べ替え処理装置１０の処理対象である複数のデータの順序について、具体例を挙げて説明する。以下においては、０〜６３の番号（以下、データ番号と呼ぶ）を付与した６４個のデータを複数のデータとして入力する例について説明する。
【００３１】
図２は、６４個のデータに対する逐次順序を示す。図２の格子中に示す数字は、データ番号を示す。以下においては、データ番号ｍのデータをデータ番号だけで示す場合がある（ｍは自然数；ｍ＝０〜６３）。
【００３２】
本実施形態において、逐次順序とは、図２に示す８つのデータ列Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８の順序である。なお、各データ列の数字は、処理サイクルの順番を示す値である。データ列Ｐｓは、それぞれｐｓ（０）からｐｓ（７）まで順番に並んだ８個のデータによって構成される（ｓ＝１、・・・、８）。そして、ｐｓ（ｉ）は、以下の式１によって表現される（ｉ＝１、・・・、８）。
ｐｓ（ｉ）＝８（ｓ−１）＋ｉ・・・（１）
逐次順序の各データ列は、処理のサイクルの進行に対応して、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８の順番に並ぶ。すなわち、逐次順序とは、ｉ×ｓ個のデータを、先頭のデータからｉ個ずつデータ順に並べてデータ列をｓ個作成し、そのデータ列をサイクル順に並べたものである。
【００３３】
一方、図３は、図２の逐次順序に対応するビットリバース順序を示す。本実施形態において、ビットリバース順序とは、図３に示す８つのデータ列Ｑ１、Ｑ２、Ｑ３、Ｑ４、Ｑ５、Ｑ６、Ｑ７、Ｑ８の順序である。なお、各データ列の数字は、処理サイクルの順番を示す値である。データ列Ｑｓは、それぞれｑｓ（０）からｑｓ（７）までの８個のデータによって構成される（ｓ＝１、・・・、８）。そして、ｑｓ（ｉ）は、以下の式２によって表現される（ｉ＝１、・・・、８）。
ｑｓ（ｉ）＝（ｓ−１）＋８ｉ・・・（２）
ビットリバース順序の各データ列は、処理のサイクルの進行に対応して、Ｑ１、Ｑ２、Ｑ３、Ｑ４、Ｑ５、Ｑ６、Ｑ７、Ｑ８の順番に並ぶ。すなわち、ビットリバース順序とは、逐次順序で入力されたｉ×ｓ個のデータを、先頭のデータからｓ個ずつサイクル順に並べ、同じサイクルのｉ個のデータを１つの組としてデータ順に並べたものである。
【００３４】
以上のように、ビットリバース順序の各データ列は、逐次順序の各組が設定されれば一意に定まる。ビットリバース順序の各データ列Ｑｓを構成するｉデータ目のデータＱｓ（ｉ）は、逐次順序に従ったサイクルｉにおけるｓデータ目のデータＰｉ（ｓ）である。すなわち、Ｐｉ（ｓ）とＱｓ（ｉ）との間には、以下の式３の関係が成り立つ。
Ｑｓ（ｉ）＝Ｐｉ（ｓ）・・・（３）
Ｑｓ（ｉ）とＰｉ（ｓ）とは、各データ列を構成するデータに関して、サイクルの進行に対する順序とデータ位置に対する順序とが入れ替えられた関係にある。したがって、ビットリバース順序で入力されたデータをビットリバース順序に従って並べ替えると逐次順序になる。
【００３５】
〔並べ替え処理〕
ここで、本実施形態のデータ並べ替え処理装置１０の２段階の並べ替え処理について、図面を参照しながら説明する。図４は、第１データ並べ替え部１１が逐次順序から中間順序への並べ替え処理を行う際に、所定数（４つ）のデータによって構成されるデータ組を単位として複数のデータを並べ替えることについて説明するための図である。図５は、中間順序に並べ替えられた複数のデータについて説明するための図である。以下においては、第１データ並べ替え部１１による並べ替え処理と、第２データ並べ替え部１２による並べ替え処理とを分けて説明する。
【００３６】
〔第１データ並べ替え部〕
第１データ並べ替え部１１は、逐次順序（図４）において点線で囲んだ４つのデータによって構成されるデータ組の単位で、矢印で繋いだデータ組を並べ替えることによって複数のデータを中間順序（図５）にする。すなわち、第１データ並べ替え部１１は、複数の第１のデータを第１の順序で入力とし、複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として複数の第１のデータを中間順序（第３の順序）に並べ替える。具体的には、第１データ並べ替え部２１は、以下の６つの並べ替えを行い、逐次順序（図４）から中間順序（図５）への並べ替え処理を行う。なお、以下のデータ組の単位での並べ替えは、記載された順番通りに実行されなくてもよい。
【００３７】
第１に、第１データ並べ替え部１１は、｛２、３、１０、１１｝によって構成されるデータ組と、｛１６、１７、２４、２５｝によって構成されるデータ組とを並べ替える。
【００３８】
第２に、第１データ並べ替え部１１は、｛４、５、１２、１３｝によって構成されるデータ組と、｛３２、３３、４０、４１｝によって構成されるデータ組とを並べ替える。
【００３９】
第３に、第１データ並べ替え部１１は、｛６、７、１４、１５｝によって構成されるデータ組と、｛４８、４９、５６、５７｝によって構成されるデータ組とを並べ替える。
【００４０】
第４に、第１データ並べ替え部１１は、｛２０、２１、２８、２９｝によって構成されるデータ組と、｛３４、３５、４２、４３｝によって構成されるデータ組とを並べ替える。
【００４１】
第５に、第１データ並べ替え部１１は、｛２２、２３、３０、３１｝によって構成されるデータ組と、｛５０、５１、５８、５９｝によって構成されるデータ組とを並べ替える。
【００４２】
第６に、第１データ並べ替え部１１は、｛３８、３９、４６、４７｝によって構成されるデータ組と、｛５２、５３、６０、６１｝によって構成されるデータ組とを並べ替える。
【００４３】
以上の６つの並べ替えによって、第１データ並べ替え部１１は、複数のデータを逐次順序（図４）から中間順序（図５）に並べ替える。
【００４４】
〔第２データ並べ替え部〕
第２データ並べ替え部１２は、第１データ並べ替え部１１によって中間順序に並べ替えられた複数のデータを中間順序（図５）からビットリバース順序（図３）にする。すなわち、第２データ並べ替え部１２は、複数の第１のデータを中間順序（第３の順序）で入力とし、データ組に含まれる所定数のデータ間で並べ替えを行うことによって、複数の第１のデータを第２の順序に並べ替える。第２データ並べ替え部１２は、中間順序（図５）において点線で示す４つのデータによって構成される各データ組の内部で、矢印で繋いだデータ対を並べ替える。第２データ並べ替え部１２は、各データ組内で以下の１６通りの並べ替えを行い、複数のデータを中間順序（図５）からビットリバース順序（図３）に並べ替える。
【００４５】
第１および第２サイクルにおいて、第２データ並べ替え部１２は、各データ組内で以下のようにデータを並べ替える。
【００４６】
すなわち、第２データ並べ替え部１２は、｛０、１、８、９｝によって構成されるデータ組内において１と８とを並べ替え、｛１６、１７、２４、２５｝によって構成されるデータ組内において１７と２４とを並べ替える。同様に、第２データ並べ替え部１２は、｛３２、３３、４０、４１｝によって構成されるデータ組内において３３と４０とを並べ替え、｛４８、４９、５６、５７｝によって構成されるデータ組内において４９と５６とを並べ替える。
【００４７】
第３および第４サイクルにおいて、第２データ並べ替え部１２は、各データ組内で以下のようにデータを並べ替える。
【００４８】
すなわち、第２データ並べ替え部１２は、｛２、３、１０、１１｝によって構成されるデータ組内において３と１０とを並べ替え、｛１８、１９、２６、２７｝によって構成されるデータ組内において１９と２６とを並べ替える。同様に、第２データ並べ替え部１２は、｛３４、３５、４２、４３｝によって構成されるデータ組内において３５と４２とを並べ替え、｛５０、５１、５８、５９｝によって構成されるデータ組内において５１と５８とを並べ替える。
【００４９】
第５および第６サイクルにおいて、第２データ並べ替え部１２は、各データ組内で以下のようにデータを並べ替える。
【００５０】
すなわち、第２データ並べ替え部１２は、｛４、５、１２、１３｝によって構成されるデータ組内において５と１２とを並べ替え、｛２０、２１、２８、２９｝によって構成されるデータ組内において２１と２８とを並べ替える。同様に、第２データ並べ替え部１２は、｛３６、３７、４４、４５｝によって構成されるデータ組内において３７と４４とを並べ替え、｛５２、５３、６０、６１｝によって構成されるデータ組内において５３と６０とを並べ替える。
【００５１】
第７および第８サイクルにおいて、第２データ並べ替え部１２は、各データ組内で以下のようにデータを並べ替える。
【００５２】
すなわち、第２データ並べ替え部１２は、｛６、７、１４、１５｝によって構成されるデータ組内において７と１４とを並べ替え、｛２２、２３、３０、３１｝によって構成されるデータ組内において２３と３０とを並べ替える。同様に、第２データ並べ替え部１２は、｛３８、３９、４６、４７｝によって構成されるデータ組内において３９と４６とを並べ替え、｛５４、５５、６２、６３｝によって構成されるデータ組内において５５と６２とを並べ替える。
【００５３】
以上の１６通りの並べ替えによって、第２データ並べ替え部１２は、中間順序（図５）からビットリバース順序（図３）への並べ替え処理を行う。
【００５４】
（効果）
以上のように、本実施形態のデータ並べ替え処理装置は、ＦＦＴ処理のバタフライ演算において必要となる逐次順序とビットリバース順序とのデータの並べ替え処理を、中間順序を介した２段階のステップで実現する。
【００５５】
図２および図３に示すように、逐次順序からビットリバース順序への並べ替え処理、または、ビットリバース順序から逐次順序への並べ替え処理においては、あるサイクルで入力された複数のデータのそれぞれを互いに異なるサイクルで出力する必要がある。一般に、これらのデータ並べ替え処理をＲＡＭ（Random Access Memory）回路で実現する場合、単一のＲＡＭ回路では構成できないため、複数のＲＡＭ回路で構成する必要がある。例えば、逐次順序からビットリバース順序へ直接並べ替えを８並列で処理する一般的な技術では、８個のＲＡＭ回路が必要である。
【００５６】
それに対し、本実施形態において、１ステップ目の並べ替えとして行う逐次順序から中間順序への並べ替えは、４個のＲＡＭ回路で実現できる。すなわち、本実施形態によれば、逐次順序からビットリバース順序への並べ替えを処理する回路において、ＲＡＭ回路の数を半分にすることができる。その結果、本実施形態によれば、ＲＡＭ回路の周辺回路部分の分だけ回路規模や消費電力を低減できる。特に、並列で処理するデータ数が多い場合、必要となるＲＡＭ回路の数が多くなるので、回路規模や消費電力を効果的に削減できる。
【００５７】
また、本実施形態の手法では、２ステップ目の並べ替えとして、中間順序からビットリバース順序への並べ替え処理を実行する手段を追加する。本実施形態の手法では、２ステップ目の並べ替えとして隣接するサイクル間の並べ替えを行うため、第２データ並べ替え手段を少数のフリップフロップとセレクタとで構成できる。そのため、本実施形態においては、２ステップ目の並べ替えに必要な回路の回路規模や消費電力は、１ステップ目の並べ替えに必要な回路の回路規模や消費電力に比べて小さくて済む。すなわち、本実施形態によれば、１ステップ目の並べ替えに必要なＲＡＭ回路の数を削減した分だけ、全体の回路規模や消費電力を低減できる。
【００５８】
（第２の実施形態）
次に、本発明の第２の実施形態のデータ並べ替え処理装置について図面を参照しながら説明する。
【００５９】
図６は、本実施形態のデータ並べ替え処理装置２０の構成を示すブロック図である。図６のように、データ並べ替え処理装置２０は、第１データ並べ替え部２１および第２データ並べ替え部２２を有する。以下において、第１データ並べ替え部２１および第２データ並べ替え部２２のそれぞれの構成について詳細に説明する。
【００６０】
〔第１データ並べ替え部〕
第１データ並べ替え部２１は、第１データ振り分け部２１１、ＲＡＭ回路２１３、第２データ振り分け部２１５を有する。
【００６１】
第１データ振り分け部２１１（第１データ振り分け手段とも呼ぶ）は、８つの入力端ｉｎ０〜７から８つの入力データを同時に入力とする。第１データ振り分け部２１１は、８つの入力データを８つの信号線２１２ａ〜ｈに振り分けて出力する。
【００６２】
ＲＡＭ回路２１３（第１の記憶回路とも呼ぶ）は、ＲＡＭ回路２１３ａ、ＲＡＭ回路２１３ｂ、ＲＡＭ回路２１３ｃおよびＲＡＭ回路２１３ｄの４つの回路を含む。ＲＡＭ回路２１３は、複数のデータビットから構成されるワードの単位で書き込み処理および読み出し処理を実行する。
【００６３】
ＲＡＭ回路２１３ａは、第１データ振り分け部２１１が信号線２１２ａおよび信号線２１２ｂに出力した２つのデータを組みにして記憶する。ＲＡＭ回路２１３ａは、組みにして記憶したデータを信号線２１４ａおよび信号線２１４ｂに再び２つのデータとして出力する。
【００６４】
ＲＡＭ回路２１３ｂは、第１データ振り分け部２１１が信号線２１２ｃおよび信号線２１２ｄに出力した２つのデータを組みにして記憶する。ＲＡＭ回路２１３ｂは、組みにして記憶したデータを信号線２１４ｃおよび信号線２１４ｄに再び２つのデータとして出力する。
【００６５】
ＲＡＭ回路２１３ｃは、第１データ振り分け部２１１が信号線２１２ｅおよび信号線２１２ｆに出力した２つのデータを組みにして記憶する。ＲＡＭ回路２１３ｃは、組みにして記憶したデータを信号線２１４ｅおよび信号線２１４ｆに再び２つのデータとして出力する。
【００６６】
ＲＡＭ回路２１３ｄは、第１データ振り分け部２１１が信号線２１２ｇおよび信号線２１２ｈに出力した２つのデータを組みにして記憶する。ＲＡＭ回路２１３ｄは、組みにして記憶したデータを信号線２１４ｇおよび信号線２１４ｈに再び２つのデータとして出力する。
【００６７】
第２データ振り分け部２１５（第２データ振り分け手段とも呼ぶ）は、８つの信号線２１４ａ〜ｈから８つのデータを同時に入力する。第２データ振り分け部２１５は、入力した８つのデータを８つの信号線２２０ａ〜ｈに振り分けて出力する。
【００６８】
〔第２データ並べ替え部〕
第２データ並べ替え部２２は、少なくとも一つのデータ組内並べ替え部２２１を含む。
本実施形態において、第２データ並べ替え部２２は、４つのデータ組内並べ替え部２２１（データ組内並べ替え部２２１ａ、データ組内並べ替え部２２１ｂ、データ組内並べ替え部２２１ｃ、データ組内並べ替え部２２１ｄ）を含む。データ組内並べ替え部２２１は、ワードの単位に因らないデータの書き込み処理および読み出し処理を実行する第２の記憶回路（図示しない）を含む。第２の記憶回路は、第１の記憶回路とは構成および特性が異なり、データの書込み処理および読み出し処理の処理単位に基づいて回路構成が決定される。第２の記憶回路は、第１の記憶回路よりも小さいサイクル数のデータを記憶する。言い換えると、第１の記憶回路は、第２の記憶回路よりも大きいサイクル数のデータを記憶する。
【００６９】
データ組内並べ替え部２２１ａは、２つの信号線２２０ａおよび信号線２２０ｂからデータ組を入力して、４つのデータから構成されるデータ組の内部で並べ替え処理を行う。
データ組内並べ替え部２２１ａは、並べ替え処理を行ったデータを出力端ｏｕｔ０および出力端ｏｕｔ１に出力する。
【００７０】
データ組内並べ替え部２２１ｂは、２つの信号線２２０ｃおよび信号線２２０ｄからデータ組を入力して、４つのデータから構成されるデータ組の内部で並べ替え処理を行う。
データ組内並べ替え部２２１ｂは、並べ替え処理を行ったデータを出力端ｏｕｔ２および出力端ｏｕｔ３に出力する。
【００７１】
データ組内並べ替え部２２１ｃは、２つの信号線２２０ｅおよび信号線２２０ｆからデータ組を入力して、４つのデータから構成されるデータ組の内部で並べ替え処理を行う。
データ組内並べ替え部２２１ｃは、並べ替え処理を行ったデータを出力端ｏｕｔ４および出力端ｏｕｔ５に出力する。
【００７２】
データ組内並べ替え部２２１ｄは、２つの信号線２２０ｇおよび信号線２２０ｈからデータ組を入力して、４つのデータから構成されるデータ組の内部で並べ替え処理を行う。
データ組内並べ替え部２２１ｄは、並べ替え処理を行ったデータを出力端ｏｕｔ６および出力端ｏｕｔ７に出力する。
【００７３】
以上が、データ並べ替え処理装置２０の構成についての説明である。続いて、データ並べ替え処理装置２０の動作について具体的に説明する。
【００７４】
（動作）
図７〜図１０は、データ並べ替え処理装置２０の動作を示すタイムチャートである。データ並べ替え処理装置２０は、ｔ０〜ｔ７の８サイクルにおいて、８並列で０〜６３の６４個のデータを逐次順序で入力とする。そして、データ並べ替え処理装置２０は、ｔ９〜ｔ１５の８サイクルにおいて、８並列で０〜６３の６４個のデータをビットリバース順序で出力する。
【００７５】
〔第１データ並べ替え部〕
まず、図７〜図９を用いて、第１データ並べ替え部２１の動作の詳細を説明する。第１データ並べ替え部２１は、ｔ０〜ｔ７の８サイクルにおいて、８並列で０〜６３の６４個のデータを逐次順序で入力し、ｔ８〜ｔ１５の８サイクルにおいて、８並列で０〜６３の６４個のデータを中間順序で出力する。
【００７６】
〔第１データ振り分け部〕
次に、図７を参照しながら、第１データ振り分け部２１１の動作について説明する。図７は、入力端ｉｎ０〜７から第１データ振り分け部２１１に入力されるデータの順序（上段）と、第１データ振り分け部２１１から信号線２１２ａ〜ｈに出力されるデータの順序（下段）とをまとめたタイムチャートである。
【００７７】
サイクルｔ０およびｔ１において、第１データ振り分け部２１１は、以下のようにデータを入出力する。
【００７８】
すなわち、第１データ振り分け部２１１は、入力端ｉｎ０からの入力データを信号線２１２ａに出力し、入力端ｉｎ１からの入力データを信号線２１２ｂに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ２からの入力データを信号線２１２ｃに出力し、入力端ｉｎ３からの入力データを信号線２１２ｄに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ４からの入力データを信号線２１２ｅに出力し、入力端ｉｎ５からの入力データを信号線２１２ｆに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ６からの入力データを信号線２１２ｇに出力し、入力端ｉｎ７からの入力データを信号線２１２ｈに出力する。
【００７９】
サイクルｔ２およびｔ３において、第１データ振り分け部２１１は、以下のようにデータを入出力する。
【００８０】
すなわち、第１データ振り分け部２１１は、入力端ｉｎ０からの入力データを信号線２１２ｃに出力し、入力端ｉｎ１からの入力データを信号線２１２ｄに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ２からの入力データを信号線２１２ｅに出力し、入力端ｉｎ３からの入力データを信号線２１２ｆに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ４からの入力データを信号線２１２ｇに出力し、入力端ｉｎ５からの入力データを信号線２１２ｈに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ６からの入力データを信号線２１２ａに出力し、入力端ｉｎ７からの入力データを信号線２１２ｂに出力する。
【００８１】
サイクルｔ４およびｔ５において、第１データ振り分け部２１１は、以下のようにデータを入出力する。
【００８２】
すなわち、第１データ振り分け部２１１は、入力端ｉｎ０からの入力データを信号線２１２ｅに出力し、入力端ｉｎ１からの入力データを信号線２１２ｆに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ２からの入力データを信号線２１２ｇに出力し、入力端ｉｎ３からの入力データを信号線２１２ｈに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ４からの入力データを信号線２１２ａに出力し、入力端ｉｎ５からの入力データを信号線２１２ｂに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ６からの入力データを信号線２１２ｃに出力し、入力端ｉｎ７からの入力データを信号線２１２ｄに出力する。
【００８３】
サイクルｔ６およびｔ７において、第１データ振り分け部２１１は、以下のようにデータを入出力する。
【００８４】
すなわち、第１データ振り分け部２１１は、入力端ｉｎ０からの入力データを信号線２１２ｇに出力し、入力端ｉｎ１からの入力データを信号線２１２ｈに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ２からの入力データを信号線２１２ａに出力し、入力端ｉｎ３からの入力データを信号線２１２ｂに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ４からの入力データを信号線２１２ｃに出力し、入力端ｉｎ５からの入力データを信号線２１２ｄに出力する。また、第１データ振り分け部２１１は、入力端ｉｎ６からの入力データを信号線２１２ｅに出力し、入力端ｉｎ７からの入力データを信号線２１２ｆに出力する。
【００８５】
ここで、図７を参照しながら、各サイクルにおいて、第１データ振り分け部２１１が入出力するデータの順序について説明する。図７は、入力端ｉｎ０〜７から第１データ振り分け部２１１に入力されるデータの順序（上段）と、第１データ振り分け部２１１から信号線２１２ａ〜ｈに出力されるデータの順序（下段）とをまとめたタイムチャートである。
【００８６】
まず、サイクルｔ０において、第１データ振り分け部２１１は、入力端ｉｎ０〜７からデータ０〜７をそれぞれ入力とする。第１データ振り分け部２１１は、信号線２１２ａ〜ｈのそれぞれにデータ０〜７を振り分けて出力する。
【００８７】
次に、サイクルｔ１において、第１データ振り分け部２１１は、入力端ｉｎ０〜７からデータ８〜１５をそれぞれ入力とする。第１データ振り分け部２１１は、信号線２１２ａ〜ｈのそれぞれにデータ８〜１５を振り分けて出力する。
【００８８】
次に、サイクルｔ２において、第１データ振り分け部２１１は、入力端ｉｎ０〜７からデータ１６〜２３をそれぞれ入力とする。第１データ振り分け部２１１は、信号線２１２ａ〜ｈのそれぞれにデータ２２、２３、１６〜２１を振り分けて出力する。
【００８９】
次に、サイクルｔ３において、第１データ振り分け部２１１は、入力端ｉｎ０〜７からデータ２４〜３１をそれぞれ入力とする。第１データ振り分け部２１１は、信号線２１２ａ〜ｈのそれぞれにデータ３０、３１、２４〜２９を振り分けて出力する。
【００９０】
次に、サイクルｔ４において、第１データ振り分け部２１１は、入力端ｉｎ０〜７からデータ３２〜３９をそれぞれ入力とする。第１データ振り分け部２１１は、信号線２１２ａ〜ｈにデータ３６〜３９、３２〜３５の８データを振り分けて出力する。
【００９１】
次に、サイクルｔ５において、第１データ振り分け部２１１は、入力端ｉｎ０〜７からデータ４０〜４７をそれぞれ入力とする。第１データ振り分け部２１１は、信号線２１２ａ〜ｈのそれぞれにデータ４４〜４７、４０〜４３を振り分けて出力する。
【００９２】
次に、サイクルｔ６において、第１データ振り分け部２１１は、入力端ｉｎ０〜７からデータ４８〜５５をそれぞれ入力とする。第１データ振り分け部２１１は、信号線２１２ａ〜ｈのそれぞれにデータ５０〜５５、４８、４９を振り分けて出力する。
【００９３】
そして、サイクルｔ７において、第１データ振り分け部２１１は、入力端ｉｎ０〜７からデータ５６〜６３をそれぞれ入力とする。第１データ振り分け部２１１は、信号線２１２ａ〜ｈのそれぞれにデータ５８〜６３、５６、５７を振り分けて出力する。
【００９４】
以上のように、第１データ振り分け部２１１は、並列して同時に入力する８つのデータに対してローテート処理を実行して出力する。例えば、第１データ振り分け部２１１は、シフト回路によって実現できる。言い換えると、第１データ振り分け部２１１は、異なる入力端から複数のデータを入力とし、入力された複数のデータを２サイクルごとに設定される第１の規則に従って振り分けて出力する。第１の規則とは、データ組を単位として、複数のデータを図７のように並べ替える規則である。
【００９５】
〔ＲＡＭ回路〕
次に、図８を参照しながら、ＲＡＭ回路２１３に含まれるＲＡＭ回路２１３ａ、ＲＡＭ回路２１３ｂ、ＲＡＭ回路２１３ｃおよびＲＡＭ回路２１３ｄのそれぞれの動作について説明する。図８は、信号線２１２ａ〜ｈからＲＡＭ回路２１３に入力されるデータの順序（上段）と、ＲＡＭ回路２１３から信号線２１４ａ〜ｈに出力されるデータの順序（下段）とをまとめたタイムチャートである。
【００９６】
〔ＲＡＭ回路ａ〕
ＲＡＭ回路２１３ａは、サイクルｔ０において信号線２１２ａから入力したデータ０をサイクルｔ８において信号線２１４ａに出力し、サイクルｔ０において信号線２１２ｂから入力したデータ１をサイクルｔ８において信号線２１４ｂに出力する。また、ＲＡＭ回路２１３ａは、サイクルｔ１において信号線２１２ａから入力したデータ８をサイクルｔ９において信号線２１４ａに出力し、サイクルｔ１において信号線２１２ｂから入力したデータ９をサイクルｔ９において信号線２１４ｂに出力する。
【００９７】
ＲＡＭ回路２１３ａは、サイクルｔ２において信号線２１２ａから入力したデータ２２をサイクルｔ１４において信号線２１４ａに出力し、サイクルｔ２において信号線２１２ｂから入力したデータ２３をサイクルｔ１４において信号線２１４ｂに出力する。また、ＲＡＭ回路２１３ａは、サイクルｔ３において信号線２１２ａから入力したデータ３０をサイクルｔ１５において信号線２１４ａに出力し、サイクルｔ３において信号線２１２ｂから入力したデータ３１をサイクルｔ１４において信号線２１４ｂに出力する。
【００９８】
ＲＡＭ回路２１３ａは、サイクルｔ４において信号線２１２ａから入力したデータ３６をサイクルｔ１２において信号線２１４ａに出力し、サイクルｔ４において信号線２１２ｂから入力したデータ３７をサイクルｔ１２において信号線２１４ｂに出力する。また、ＲＡＭ回路２１３ａは、サイクルｔ５において信号線２１２ａから入力したデータ４４をサイクルｔ１３において信号線２１４ａに出力し、サイクルｔ５において信号線２１２ｂから入力したデータ４５をサイクルｔ１３において信号線２１４ｂに出力する。
【００９９】
ＲＡＭ回路２１３ａは、サイクルｔ６において信号線２１２ａから入力したデータ５０を、サイクルｔ１０において信号線２１４ａに出力し、サイクルｔ６において信号線２１２ｂから入力したデータ５１をサイクルｔ１０において信号線２１４ｂに出力する。また、ＲＡＭ回路２１３ａは、サイクルｔ７において信号線２１２ａから入力したデータ５８をサイクルｔ１１において信号線２１４ａに出力し、サイクルｔ７において信号線２１２ｂから入力したデータ５９をサイクルｔ１１において信号線２１４ｂに出力する。
【０１００】
〔ＲＡＭ回路ｂ〕
ＲＡＭ回路２１３ｂは、サイクルｔ０において信号線２１２ｃから入力したデータ２をサイクルｔ１０において信号線２１４ｃに出力し、サイクルｔ０において信号線２１２ｄから入力したデータ３をサイクルｔ１０において信号線２１４ｄに出力する。また、ＲＡＭ回路２１３ｂは、サイクルｔ１において信号線２１２ｃから入力したデータ１０をサイクルｔ１１において信号線２１４ｃに出力し、サイクルｔ１において信号線２１２ｄから入力したデータ１１をサイクルｔ１１において信号線２１４ｄに出力する。
【０１０１】
ＲＡＭ回路２１３ｂは、サイクルｔ２において信号線２１２ｃから入力したデータ１６をサイクルｔ８において信号線２１４ｃに出力し、サイクルｔ２において信号線２１２ｄから入力したデータ１７をサイクルｔ８において信号線２１４ｄに出力する。また、ＲＡＭ回路２１３ｂは、サイクルｔ３において信号線２１２ｃから入力したデータ２４をサイクルｔ９において信号線２１４ｃに出力し、サイクルｔ３において信号線２１２ｄから入力したデータ２５をサイクルｔ９において信号線２１４ｄに出力する。
【０１０２】
ＲＡＭ回路２１３ｂは、サイクルｔ４において信号線２１２ｃから入力したデータ３８をサイクルｔ１４において信号線２１４ｃに出力し、サイクルｔ４において信号線２１２ｄから入力したデータ３９をサイクルｔ１４において信号線２１４ｄに出力する。また、ＲＡＭ回路２１３ｂは、サイクルｔ５において信号線２１２ｃから入力したデータ４６をサイクルｔ１５において信号線２１４ｃに出力し、サイクルｔ５において信号線２１２ｄから入力したデータ４７をサイクルｔ１５において信号線２１４ｄに出力する。
【０１０３】
ＲＡＭ回路２１３ｂは、サイクルｔ６において信号線２１２ｃから入力したデータ５２をサイクルｔ１２において信号線２１４ｃに出力し、サイクルｔ６において信号線２１２ｄから入力したデータ５３をサイクルｔ１２において信号線２１４ｄに出力する。また、ＲＡＭ回路２１３ｂは、サイクルｔ７において信号線２１２ｃから入力したデータ６０をサイクルｔ１３において信号線２１４ｃに出力し、サイクルｔ７において信号線２１２ｄから入力したデータ６１をサイクルｔ１３において信号線２１４ｄに出力する。
【０１０４】
〔ＲＡＭ回路ｃ〕
ＲＡＭ回路２１３ｃは、サイクルｔ０において信号線２１２ｅから入力したデータ４をサイクルｔ１２において信号線２１４ｅに出力し、サイクルｔ０において信号線２１２ｆから入力したデータ５をサイクルｔ１２において信号線２１４ｆに出力する。また、ＲＡＭ回路２１３ｃは、サイクルｔ１において信号線２１２ｅから入力したデータ１２をサイクルｔ１３において信号線２１４ｅに出力し、サイクルｔ１において信号線２１２ｆから入力したデータ１３をサイクルｔ１３において信号線２１４ｆに出力する。
【０１０５】
ＲＡＭ回路２１３ｃは、サイクルｔ２において信号線２１２ｅから入力したデータ１８をサイクルｔ１０において信号線２１４ｅに出力し、サイクルｔ２において信号線２１２ｆから入力したデータ１９をサイクルｔ１０において信号線２１４ｆに出力する。また、ＲＡＭ回路２１３ｃは、サイクルｔ３において信号線２１２ｅから入力したデータ２６をサイクルｔ１１において信号線２１４ｅに出力し、サイクルｔ３において信号線２１２ｆから入力したデータ２７をサイクルｔ１１において信号線２１４ｆに出力する。
【０１０６】
ＲＡＭ回路２１３ｃは、サイクルｔ４において信号線２１２ｅから入力したデータ３２をサイクルｔ８において信号線２１４ｅに出力し、サイクルｔ４において信号線２１２ｆから入力したデータ３３をサイクルｔ８において信号線２１４ｆに出力する。ＲＡＭ回路２１３ｃは、サイクルｔ５において信号線２１２ｅから入力したデータ４０をサイクルｔ９において信号線２１４ｅに出力し、サイクルｔ５において信号線２１２ｆから入力したデータ４１をサイクルｔ９において信号線２１４ｆに出力する。
【０１０７】
ＲＡＭ回路２１３ｃは、サイクルｔ６において信号線２１２ｅから入力したデータ５４をサイクルｔ１４において信号線２１４ｅに出力し、サイクルｔ６において信号線２１２ｆから入力したデータ５５をサイクルｔ１４において信号線２１４ｆに出力する。また、ＲＡＭ回路２１３ｃは、サイクルｔ７において信号線２１２ｅから入力したデータ６２をサイクルｔ１５において信号線２１４ｅに出力し、サイクルｔ７において信号線２１２ｆから入力したデータ６３をサイクルｔ１５において信号線２１４ｆに出力する。
【０１０８】
〔ＲＡＭ回路ｄ〕
ＲＡＭ回路２１３ｄは、サイクルｔ０において信号線２１２ｇから入力したデータ６をサイクルｔ１４において信号線２１４ｇに出力し、サイクルｔ０において信号線２１２ｈから入力したデータ７をサイクルｔ１４において信号線２１４ｈに出力する。また、ＲＡＭ回路２１３ｄは、サイクルｔ１において信号線２１２ｇから入力したデータ１４をサイクルｔ１５において信号線２１４ｇに出力し、サイクルｔ１において信号線２１２ｈから入力したデータ１５をサイクルｔ１５において信号線２１４ｈに出力する。
【０１０９】
ＲＡＭ回路２１３ｄは、サイクルｔ２において信号線２１２ｇから入力したデータ２０をサイクルｔ１２において信号線２１４ｇに出力し、サイクルｔ２において信号線２１２ｈから入力したデータ２１をサイクルｔ１２において信号線２１４ｈに出力する。また、ＲＡＭ回路２１３ｄは、サイクルｔ３において信号線２１２ｇから入力したデータ２８をサイクルｔ１３において信号線２１４ｇに出力し、サイクルｔ３において信号線２１２ｈから入力したデータ２９をサイクルｔ１３において信号線２１４ｈに出力する。
【０１１０】
ＲＡＭ回路２１３ｄは、サイクルｔ４において信号線２１２ｇから入力したデータ３４を、サイクルｔ１０において信号線２１４ｇに出力し、サイクルｔ４において信号線２１２ｈから入力したデータ３５をサイクルｔ１０において信号線２１４ｈに出力する。また、ＲＡＭ回路２１３ｄは、サイクルｔ５において信号線２１２ｇから入力したデータ４２をサイクルｔ１１において信号線２１４ｇに出力し、サイクルｔ５において信号線２１２ｈから入力したデータ４３をサイクルｔ１１において信号線２１４ｈに出力する。
【０１１１】
ＲＡＭ回路２１３ｄは、サイクルｔ６において信号線２１２ｇから入力したデータ４８をサイクルｔ８において信号線２１４ｇに出力し、サイクルｔ６において信号線２１２ｈから入力したデータ４９をサイクルｔ８において信号線２１４ｈに出力する。また、ＲＡＭ回路２１３ｄは、サイクルｔ７において信号線２１２ｇから入力したデータ５６をサイクルｔ９において信号線２１４ｇに出力し、サイクルｔ７において信号線２１２ｈから入力したデータ５７をサイクルｔ９において信号線２１４ｈに出力する。
【０１１２】
以上のように、ＲＡＭ回路２１３は、連続する二つのサイクルにおいて隣接し合う二つの入力端から入力される四つのデータによって構成されるデータ組を単位として複数のデータを並べ替える。言い換えると、ＲＡＭ回路２１３は、第１データ振り分け部２１１によって出力された複数のデータをデータ組の単位で記憶し、記憶した複数の前記データをデータ組の単位で並べ替えて出力する。
【０１１３】
〔第２データ振り分け部〕
次に、図９を参照しながら、第２データ振り分け部２１５の動作について説明する。図９は、信号線２１４ａ〜ｈから第２データ振り分け部２１５に入力されるデータの順序（上段）と、第２データ振り分け部２１５から信号線２２０ａ〜ｈに出力されるデータの順序（下段）とをまとめたタイムチャートである。
【０１１４】
サイクルｔ８およびｔ９において、第２データ振り分け部２１５は、以下のようにデータを入出力する。
【０１１５】
すなわち、第２データ振り分け部２１５は、信号線２１４ａからの入力データを信号線２２０ａに出力し、信号線２１４ｂからの入力データを信号線２２０ｂに出力する。また、第２データ振り分け部２１５は、信号線２１４ｃからの入力データを信号線２２０ｃに出力し、信号線２１４ｄからの入力データを信号線２２０ｄに出力する。また、第２データ振り分け部２１５は、信号線２１４ｅからの入力データを信号線２２０ｅに出力し、信号線２１４ｆからの入力データを信号線２２０ｆに出力する。また、第２データ振り分け部２１５は、信号線２１４ｇからの入力データを信号線２２０ｇに出力し、信号線２１４ｈからの入力データを信号線２２０ｈに出力する。
【０１１６】
サイクルｔ１０およびｔ１１において、第２データ振り分け部２１５は、以下のようにデータを入出力する。
【０１１７】
すなわち、第２データ振り分け部２１５は、信号線２１４ａからの入力データを信号線２２０ｇに出力し、信号線２１４ｂからの入力データを信号線２２０ｈに出力する。また、第２データ振り分け部２１５は、信号線２１４ｃからの入力データを信号線２２０ａに出力し、信号線２１４ｄからの入力データを信号線２２０ｂに出力する。また、第２データ振り分け部２１５は、信号線２１４ｅからの入力データを信号線２２０ｃに出力し、信号線２１４ｆからの入力データを信号線２２０ｄに出力する。また、第２データ振り分け部２１５は、信号線２１４ｇからの入力データを信号線２２０ｅに出力し、信号線２１４ｈからの入力データを信号線２２０ｆに出力する。
【０１１８】
サイクルｔ１２およびｔ１３において、第２データ振り分け部２１５は、以下のようにデータを入出力する。
【０１１９】
すなわち、第２データ振り分け部２１５は、信号線２１４ａからの入力データを信号線２２０ｅに出力し、信号線２１４ｂからの入力データを信号線２２０ｆに出力する。また、第２データ振り分け部２１５は、信号線２１４ｃからの入力データを信号線２２０ｇに出力し、信号線２１４ｄからの入力データを信号線２２０ｈに出力する。また、第２データ振り分け部２１５は、信号線２１４ｅからの入力データを信号線２２０ａに出力し、信号線２１４ｆからの入力データを信号線２２０ｂに出力する。また、第２データ振り分け部２１５は、信号線２１４ｇからの入力データを信号線２２０ｃに出力し、信号線２１４ｈからの入力データを信号線２２０ｄに出力する。
【０１２０】
サイクルｔ１４およびｔ１５において、第２データ振り分け部２１５は、以下のようにデータを入出力する。
【０１２１】
すなわち、第２データ振り分け部２１５は、信号線２１４ａからの入力データを信号線２２０ｃに出力し、信号線２１４ｂからの入力データを信号線２２０ｄに出力する。また、第２データ振り分け部２１５は、信号線２１４ｃからの入力データを信号線２２０ｅに出力し、信号線２１４ｄからの入力データを信号線２２０ｆに出力する。また、第２データ振り分け部２１５は、信号線２１４ｅからの入力データを信号線２２０ｇに出力し、信号線２１４ｆからの入力データを信号線２２０ｈに出力する。第２データ振り分け部２１５は、信号線２１４ｇからの入力データを信号線２２０ａに出力し、信号線２１４ｈからの入力データを信号線２２０ｂに出力する。
【０１２２】
具体的には、第２データ振り分け部２１５は、各サイクルにおいて、以下の順番でデータを入出力する。
【０１２３】
まず、サイクルｔ８において、第２データ振り分け部２１５は、信号線２１４ａ〜ｈからデータ０、データ１、データ１６、データ１７、データ３２、データ３３、データ４８、データ４９の８データを入力とする。そして、サイクルｔ８において、第２データ振り分け部２１５は、データ０、データ１、データ１６、データ１７、データ３２、データ３３、データ４８、データ４９の８データを信号線２２０ａ〜ｈにそれぞれ出力する。
【０１２４】
次に、サイクルｔ９において、第２データ振り分け部２１５は、信号線２１４ａ〜ｈからデータ８、データ９、データ２４、データ２５、データ４０、データ４１、データ５６、データ５７の８データを入力とする。そして、サイクルｔ９において、第２データ振り分け部２１５は、データ８、データ９、データ２４、データ２５、データ４０、データ４１、データ５６、データ５７の８データを信号線２２０ａ〜ｈにそれぞれ出力する。
【０１２５】
次に、サイクルｔ１０において、第２データ振り分け部２１５は、信号線２１４ａ〜ｈからデータ５０、データ５１、データ２、データ３、データ１８、データ１９、データ３４、データ３５の８データを入力とする。そして、サイクル１０において、第２データ振り分け部２１５は、データ２、データ３、データ１８、データ１９、データ３４、データ３５、データ５０、データ５１の８データを信号線２２０ａ〜ｈにそれぞれ出力する。
【０１２６】
次に、サイクルｔ１１において、第２データ振り分け部２１５は、信号線２１４ａ〜ｈからデータ５８、データ５９、データ１０、データ１１、データ２６、データ２７、データ４２、データ４３の８データを入力とする。そして、サイクル１１において、第２データ振り分け部２１５は、データ１０、データ１１、データ２６、データ２７、データ４２、データ４３、データ５８、データ５９の８データを信号線２２０ａ〜ｈにそれぞれ出力する。
【０１２７】
次に、サイクルｔ１２において、第２データ振り分け部２１５は、信号線２１４ａ〜ｈからデータ３６、データ３７、データ５２、データ５３、データ４、データ５、データ２０、データ２１の８データを入力とする。そして、サイクルｔ１２において、第２データ振り分け部２１５は、データ４、データ５、データ２０、データ２１、データ３６、データ３７、データ５２、データ５３の８データを信号線２２０ａ〜ｈにそれぞれ出力する。
【０１２８】
次に、サイクルｔ１３において、第２データ振り分け部２１５は、信号線２１４ａ〜ｈからデータ４４、データ４５、データ６０、データ６１、データ１２、データ１３、データ２８、データ２９の８データを入力とする。そして、サイクルｔ１３において、第２データ振り分け部２１５は、データ１２、データ１３、データ２８、データ２９、データ４４、データ４５、データ６０、データ６１の８データを信号線２２０ａ〜ｈにそれぞれ出力する。
【０１２９】
次に、サイクルｔ１４において、第２データ振り分け部２１５は、信号線２１４ａ〜ｈからデータ２２、データ２３、データ３８、データ３９、データ５４、データ５５、データ６、データ７の８データを入力とする。そして、サイクルｔ１４において、第２データ振り分け部２１５は、データ６、データ７、データ２２、データ２３、データ３８、データ３９、データ５４、データ５５の８データを信号線２２０ａ〜ｈにそれぞれ出力する。
【０１３０】
そして、サイクルｔ１５において、第２データ振り分け部２１５は、信号線２１４ａ〜ｈからデータ３０、データ３１、データ４６、データ４７、データ６２、データ６３、データ１４、データ１５の８データを入力とする。そして、第２データ振り分け部２１５は、サイクルｔ１５において、データ１４、データ１５、データ３０、データ３１、データ４６、データ４７、データ６２、データ６３の８データを信号線２２０ａ〜ｈにそれぞれ出力する。
【０１３１】
以上のように、第２データ振り分け部２１５は、並列して同時に入力する８つのデータに対してローテート処理して出力する。例えば、第２データ振り分け部２１５は、シフト回路によって実現できる。言い換えると、第２データ振り分け部２１５は、ＲＡＭ回路２１３から出力される複数のデータを２サイクルごとに設定される第２の規則に従って振り分けて中間順序とする。第２の規則とは、データ組内で複数のデータを図９のように並べ替える規則である。第２データ振り分け部２１５から出力されるデータは、第１データ並べ替え部２１の出力として、信号線２２０ａ〜ｈを経由して第２データ並べ替え部２２に入力される。
【０１３２】
すなわち、第１データ並べ替え部２１は、複数のデータを複数のサイクルに分けて異なる入力端から少なくとも二つずつ入力とする。そして、第１データ並べ替え部２１は、連続する少なくとも二つのサイクルにおいて隣接し合う入力端から入力される少なくとも二つのデータによって構成されるデータ組を単位として複数のデータを中間順序に並べ替える。
【０１３３】
より具体的には、本実施形態において、第１データ並べ替え部２１は、６４個のデータを８サイクルに分けて異なる入力端から８個ずつ入力とする。そして、第１データ並べ替え部２１は、４個のデータによって構成されるデータ組を単位として複数のデータを中間順序に並べ替える。なお、本実施形態において、データ組は、奇数番目のサイクルにおいて入力される２個のデータと、奇数番目のサイクルに連続する偶数番目のサイクルにおいて入力される２個のデータとの４個のデータからなる。
【０１３４】
〔第２データ並べ替え部〕
次に、図１０を用いて、第２データ並べ替え部２２の動作の詳細を説明する。第２データ並べ替え部２２は、ｔ８〜ｔ１５の８サイクルにおいて、８並列で０〜６３の６４個のデータを信号線２２０ａ〜ｈから中間順序で入力とする。第２データ並べ替え部２２は、ｔ９〜ｔ１６の８サイクルにおいて、８並列で０〜６３の６４個のデータをビットリバース順序で出力する。
【０１３５】
図１０は、信号線２２０ａ〜ｈから第２データ並べ替え部２２に入力されるデータの順序（上段）と、第２データ並べ替え部２２から出力端ｏｕｔ０〜７に出力されるデータの順序（下段）とをまとめたタイムチャートである。以下においては、第２データ並べ替え部２２に含まれるデータ組内並べ替え部２２１ａ、データ組内並べ替え部２２１ｂ、データ組内並べ替え部２２１ｃおよびデータ組内並べ替え部２２１ｄのそれぞれの動作について説明する。
【０１３６】
〔データ組内並べ替え部２２１ａ〕
データ組内並べ替え部２２１ａは、サイクルｔ８において、信号線２２０ａからデータ０を入力し、信号線２２０ｂからデータ１を入力し、サイクルｔ９において、信号線２２０ａからデータ８を入力し、信号線２２０ｂからデータ９を入力する。そして、データ組内並べ替え部２２１ａは、サイクルｔ９において、出力端ｏｕｔ０にデータ０を出力し、出力端ｏｕｔ１にデータ８を出力し、サイクルｔ１０において、出力端ｏｕｔ０に１を出力し、出力端ｏｕｔ１にデータ９を出力する。
【０１３７】
データ組内並べ替え部２２１ａは、サイクルｔ１０において、信号線２２０ａからデータ２を入力し、信号線２２０ｂからデータ３を入力し、サイクルｔ１１において、信号線２２０ａからデータ１０を入力し、信号線２２０ｂからデータ１１を入力する。そして、データ組内並べ替え部２２１ａは、サイクルｔ１１において、出力端ｏｕｔ０にデータ２を出力し、出力端ｏｕｔ１にデータ１０を出力し、サイクルｔ１２において、出力端ｏｕｔ０にデータ３を出力し、出力端ｏｕｔ１にデータ１１を出力する。
【０１３８】
データ組内並べ替え部２２１ａは、サイクルｔ１２において、信号線２２０ａからデータ４を入力し、信号線２２０ｂからデータ５を入力し、サイクルｔ１３において、信号線２２０ａからデータ１２を入力し、信号線２２０ｂからデータ１３を入力する。そして、データ組内並べ替え部２２１ａは、サイクルｔ１３において、出力端ｏｕｔ０にデータ４を出力し、出力端ｏｕｔ１にデータ１２を出力し、サイクルｔ１４において、出力端ｏｕｔ０にデータ５を出力し、出力端ｏｕｔ１にデータ１３を出力する。
【０１３９】
データ組内並べ替え部２２１ａは、サイクルｔ１４において、信号線２２０ａからデータ６を入力し、信号線２２０ｂからデータ７を入力し、サイクルｔ１５において、信号線２２０ａからデータ１４を入力し、信号線２２０ｂからデータ１５を入力する。そして、データ組内並べ替え部２２１ａは、サイクルｔ１５において、出力端ｏｕｔ０にデータ６を出力し、出力端ｏｕｔ１にデータ１４を出力し、サイクルｔ１６において、出力端ｏｕｔ０にデータ７を出力し、出力端ｏｕｔ１にデータ１５を出力する。
【０１４０】
〔データ組内並べ替え部２２１ｂ〕
データ組内並べ替え部２２１ｂは、サイクルｔ８において、信号線２２０ｃからデータ１６を入力し、信号線２２０ｄからデータ１７を入力し、サイクルｔ９において、信号線２２０ｃからデータ２４を入力し、信号線２２０ｄからデータ２５を入力する。そして、データ組内並べ替え部２２１ｂは、サイクルｔ９において、出力端ｏｕｔ２にデータ１６を出力し、出力端ｏｕｔ３にデータ２４を出力し、サイクルｔ１０において、出力端ｏｕｔ２に１７を出力し、出力端ｏｕｔ３にデータ２５を出力する。
【０１４１】
データ組内並べ替え部２２１ｂは、サイクルｔ１０において、信号線２２０ｃからデータ１８を入力し、信号線２２０ｄからデータ１９を入力し、サイクルｔ１１において、信号線２２０ｃからデータ２６を入力し、信号線２２０ｄからデータ２７を入力する。そして、データ組内並べ替え部２２１ｂは、サイクルｔ１１において、出力端ｏｕｔ２にデータ１８を出力し、出力端ｏｕｔ３にデータ２６を出力し、サイクルｔ１２において、出力端ｏｕｔ２に１９を出力し、出力端ｏｕｔ３にデータ２７を出力する。
【０１４２】
データ組内並べ替え部２２１ｂは、サイクルｔ１２において、信号線２２０ｃからデータ２０を入力し、信号線２２０ｄからデータ２１を入力し、サイクルｔ１３において、信号線２２０ｃからデータ２８を入力し、信号線２２０ｄからデータ２９を入力する。そして、データ組内並べ替え部２２１ｂは、サイクルｔ１３において、出力端ｏｕｔ２にデータ２０を出力し、出力端ｏｕｔ３にデータ２８を出力し、サイクルｔ１４において、出力端ｏｕｔ２に２１を出力し、出力端ｏｕｔ３にデータ２９を出力する。
【０１４３】
データ組内並べ替え部２２１ｂは、サイクルｔ１４において、信号線２２０ｃからデータ２２を入力し、信号線２２０ｄからデータ２３を入力し、サイクルｔ１５において、信号線２２０ｃからデータ３０を入力し、信号線２２０ｄからデータ３１を入力する。そして、データ組内並べ替え部２２１ｂは、サイクルｔ１５において、出力端ｏｕｔ２にデータ２２を出力し、出力端ｏｕｔ３にデータ３０を出力し、サイクルｔ１６において、出力端ｏｕｔ２に２３を出力し、出力端ｏｕｔ３にデータ３１を出力する。
【０１４４】
〔データ組内並べ替え部２２１ｃ〕
データ組内並べ替え部２２１ｃは、サイクルｔ８において、信号線２２０ｅからデータ３２を入力し、信号線２２０ｆからデータ３３を入力し、サイクルｔ９において、信号線２２０ｅからデータ４０を入力し、信号線２２０ｆからデータ４１を入力する。そして、データ組内並べ替え部２２１ｃは、サイクルｔ９において、出力端ｏｕｔ４にデータ３２を出力し、出力端ｏｕｔ５にデータ４０を出力し、サイクルｔ１０において、出力端ｏｕｔ４に３３を出力し、出力端ｏｕｔ５にデータ４１を出力する。
【０１４５】
データ組内並べ替え部２２１ｃは、サイクルｔ１０において、信号線２２０ｅからデータ３４を入力し、信号線２２０ｆからデータ３５を入力し、サイクルｔ１１において、信号線２２０ｅからデータ４２を入力し、信号線２２０ｆからデータ４３を入力する。そして、データ組内並べ替え部２２１ｃは、サイクルｔ１１において、出力端ｏｕｔ４にデータ３４を出力し、出力端ｏｕｔ５にデータ４２を出力し、サイクルｔ１２において、出力端ｏｕｔ４に３５を出力し、出力端ｏｕｔ５にデータ４３を出力する。
【０１４６】
データ組内並べ替え部２２１ｃは、サイクルｔ１２において、信号線２２０ｅからデータ３６を入力し、信号線２２０ｆからデータ３７を入力し、サイクルｔ１３において、信号線２２０ｅからデータ４４を入力し、信号線２２０ｆからデータ４５を入力する。そして、データ組内並べ替え部２２１ｃは、サイクルｔ１３において、出力端ｏｕｔ４にデータ３６を出力し、出力端ｏｕｔ５にデータ４４を出力し、サイクルｔ１４において、出力端ｏｕｔ４に３７を出力し、出力端ｏｕｔ５にデータ４５を出力する。
【０１４７】
データ組内並べ替え部２２１ｃは、サイクルｔ１４において、信号線２２０ｅからデータ３８を入力し、信号線２２０ｆからデータ３９を入力し、サイクルｔ１５において、信号線２２０ｅからデータ４６を入力し、信号線２２０ｆからデータ４７を入力する。そして、データ組内並べ替え部２２１ｃは、サイクルｔ１５において、出力端ｏｕｔ４にデータ３８を出力し、出力端ｏｕｔ５にデータ４６を出力し、サイクルｔ１６において、出力端ｏｕｔ４に３９を出力し、出力端ｏｕｔ５にデータ４７を出力する。
【０１４８】
〔データ組内並べ替え部２２１ｄ〕
データ組内並べ替え部２２１ｄは、サイクルｔ８において、信号線２２０ｇからデータ４８を入力し、信号線２２０ｈからデータ４９を入力し、サイクルｔ９において、信号線２２０ｇからデータ５６を入力し、信号線２２０ｈからデータ５７を入力する。そして、データ組内並べ替え部２２１ｄは、サイクルｔ９において、出力端ｏｕｔ６にデータ４８を出力し、出力端ｏｕｔ７にデータ５６を出力し、サイクルｔ１０において、出力端ｏｕｔ６に４９を出力し、出力端ｏｕｔ７にデータ５７を出力する。
【０１４９】
データ組内並べ替え部２２１ｄは、サイクルｔ１０において、信号線２２０ｇからデータ５０を入力し、信号線２２０ｈからデータ５１を入力し、サイクルｔ１１において、信号線２２０ｇからデータ５８を入力し、信号線２２０ｈからデータ５９を入力する。そして、データ組内並べ替え部２２１ｄは、サイクルｔ１１において、出力端ｏｕｔ６にデータ５０を出力し、出力端ｏｕｔ７にデータ５８を出力し、サイクルｔ１２において、出力端ｏｕｔ６に５１を出力し、出力端ｏｕｔ７にデータ５９を出力する。
【０１５０】
データ組内並べ替え部２２１ｄは、サイクルｔ１２において、信号線２２０ｇからデータ５２を入力し、信号線２２０ｈからデータ５３を入力し、サイクルｔ１３において、信号線２２０ｇからデータ６０を入力し、信号線２２０ｈからデータ６１を入力する。そして、データ組内並べ替え部２２１ｄは、サイクルｔ１３において、出力端ｏｕｔ６にデータ５２を出力し、出力端ｏｕｔ７にデータ６０を出力し、サイクルｔ１４において、出力端ｏｕｔ６に５３を出力し、出力端ｏｕｔ７にデータ６１を出力する。
【０１５１】
データ組内並べ替え部２２１ｄは、サイクルｔ１４において、信号線２２０ｇからデータ５４を入力し、信号線２２０ｈからデータ５５を入力し、サイクルｔ１５において、信号線２２０ｇからデータ６２を入力し、信号線２２０ｈからデータ６３を入力する。そして、データ組内並べ替え部２２１ｄは、サイクルｔ１５において、出力端ｏｕｔ６にデータ５４を出力し、出力端ｏｕｔ７にデータ６２を出力し、サイクルｔ１６において、出力端ｏｕｔ６に５５を出力し、出力端ｏｕｔ７にデータ６３を出力する。
【０１５２】
すなわち、第２データ並べ替え部２２は、第１データ並べ替え部２１によって中間順序に並べ替えられた複数のデータを、データ組を構成するデータのうち少なくとも二つを並べ替えることによって第２の順序に並べ替える。より具体的には、本実施形態において、第２データ並べ替え部２２は、第１データ並べ替え部２１によって中間順序に並べ替えられた複数のデータを、データ組を構成する４個のデータのうち二つを並べ替えることによって第２の順序に並べ替える。
【０１５３】
以上のように、本実施形態のデータ並べ替え処理装置は、第１データ並べ替え部２１が逐次順序から中間順序への並べ替えを行い、第２データ並べ替え部２２が中間順序からビットリバース順序への並べ替えを行う。すなわち、本実施形態のデータ並べ替え処理装置は、逐次順序からビットリバース順序への並べ替えを２段階で実現する際に、一段階目の並べ替えに用いるＲＡＭ回路の数を半分にするため、一般的な手法と比較して回路規模を小さくすることができる。
【０１５４】
なお、本実施形態においては、逐次順序からビットリバース順序へのデータ並べ替え処理について説明したが、ビットリバース順序から逐次順序への並べ替えについても同様である。すなわち、本実施形態の手法によれば、１ステップ目の並べ替えとしてビットリバース順序から中間順序に並べ替えを行い、２ステップ目の並べ替えとして中間順序から逐次順序に並べ替えを行う２段階のステップによるデータ並べ替え処理も実行できる。
【０１５５】
〔関連技術〕
ここで、本実施形態のデータ並べ替え処理装置の関連技術について説明する。図１１は、複数のＲＡＭ回路で構成された一般的なデータ並べ替え処理装置２００の構成例を示す。データ並べ替え処理装置２００は、第１データ振り分け部２０１、複数のＲＡＭ回路２１０ａ〜ｈ、第２データ振り分け部２０２を有する。
【０１５６】
８個のデータを並列で並べ替え処理する場合、１サイクル目に入力されるデータ組Ｐ１（図２）を構成する８個のデータは、異なるサイクルのそれぞれにおいて出力する必要がある。そのため、図１１のように、データ読み出しのサイクルを個別に設定可能とするためには８個のＲＡＭ回路２１０ａ〜ｈが必要となる。
【０１５７】
一般に、ＲＡＭ回路は、データを記憶するメモリセル部分と、データの書き込みや読み出しを行うアドレスデコーダ回路やセンスアンプ回路などの周辺回路部分から構成される。したがって、同じ記憶容量の記憶装置をＲＡＭ回路で実現する場合であっても、単一のＲＡＭ回路で構成するよりも複数のＲＡＭ回路で構成した方が、周辺回路の分だけ回路規模や消費電力が大きくなる。また、ＦＦＴ処理やデータ並べ替え処理の並列数が増加するほど、必要となるＲＡＭ回路の個数も増加し、回路規模や消費電力が大きくなる。
【０１５８】
それに対し、本実施形態のデータ並べ替え処理装置においては、第１データ並べ替え手段のＲＡＭ回路の数を低減することによって、ＲＡＭ回路の周辺回路を削減できる。すなわち、本実施形態によれば、高速フーリエ変換を用いたデジタル信号処理を実行する回路の回路規模を小さくすることができる。
【０１５９】
（第３の実施形態）
次に、本発明の第３の実施形態に係るデータ組内並べ替え装置について図面を参照しながら説明する。本実施形態のデータ組内並べ替え装置は、第２の実施形態の第２データ並べ替え部２２に含まれるデータ組内並べ替え部２２１ａ〜ｄを実現する構成である。
【０１６０】
（構成）
図１２は、データ組内並べ替え装置３０の回路図である。データ組内並べ替え装置３０は、入力端ｉｎＡおよび入力端ｉｎＢから入力したデータを並べ替え、並べ替えたデータを出力端ｏｕｔＡおよび出力端ｏｕｔＢから出力する。なお、入力端ｉｎＡは、図６の入力端ｉｎ０、入力端ｉｎ２、入力端ｉｎ４および入力端ｉｎ６に対応する。また、入力端ｉｎＢは、図６の入力端ｉｎ１、入力端ｉｎ３および入力端ｉｎ５、入力端ｉｎ７に対応する。
【０１６１】
図１２のように、データ組内並べ替え装置３０は、セレクタ３１、フリップフロップ３２、フリップフロップ３３、セレクタ３４、セレクタ３５を含む。フリップフロップ３２およびフリップフロップ３３は、第２の記憶回路を実現する一例である。
【０１６２】
セレクタ３１（第１のセレクタとも呼ぶ）は、入力端ｉｎＡからのデータ（第１のデータとも呼ぶ）と、入力端ｉｎＢからのデータ（第２のデータとも呼ぶ）とを入力とする。
セレクタ３１は、入力端ｉｎＡおよび入力端ｉｎＢから入力されたデータのうちいずれか一方を選択して出力する。
【０１６３】
フリップフロップ３２（第１のフリップフロップとも呼ぶ）は、セレクタ３１からのデータを入力とし、入力されたデータを記憶する。フリップフロップ３２は、所定のタイミングで記憶するデータを出力する。
【０１６４】
フリップフロップ３３（第２のフリップフロップとも呼ぶ）は、入力端ｉｎＢからのデータを入力とし、入力されたデータを記憶する。フリップフロップ３３は、所定のタイミングで記憶するデータを出力する。
【０１６５】
セレクタ３４（第２のセレクタとも呼ぶ）は、フリップフロップ３２の出力と、フリップフロップ３３の出力とを入力とし、入力されたデータのうちいずれか一方を選択する。
セレクタ３４は、選択したデータを出力端ｏｕｔＡから出力する。
【０１６６】
セレクタ３５（第３のセレクタとも呼ぶ）は、フリップフロップ３２の出力と、入力端ｉｎＡからのデータとを入力とし、入力されたデータのうちいずれか一方を選択する。セレクタ３５は、選択したデータを出力端ｏｕｔＢから出力する。
【０１６７】
（動作）
次に、データ組内並べ替え装置３０の動作について図面を参照しながら説明する。図１３は、データ組内並べ替え装置３０の動作を示すタイムチャートである。なお、以下においては、図５の例のように、データ０、１、８、９を中間順序からビットリバース順序に並べ替える例について説明する。
【０１６８】
図１３において、データ組内並べ替え装置３０は、サイクルｔ０およびサイクルｔ１において、入力端ｉｎＡおよび入力端ｉｎＢから４つのデータ０、１、８、９からなるデータ組を入力する。データ組内並べ替え装置３０は、入力したデータ組に関して、データ組内の並べ替え処理を行う。そして、データ組内並べ替え装置３０は、サイクルｔ１およびサイクルｔ２において、データ組内で並べ替えた４つのデータ０、８、１、９を出力端ｏｕｔＡおよび出力端ｏｕｔＢから出力する。
【０１６９】
具体的には、データ組内並べ替え装置３０は、以下のように動作する。
【０１７０】
サイクルｔ０において、セレクタ３１は、入力端ｉｎＡからデータ０を入力とし、入力端ｉｎＢからデータ１を入力とする。セレクタ３１は、入力端ｉｎＡから入力したデータ０を選択する。フリップフロップ３２は、セレクタ３１が選択したデータ０を記憶する。
また、フリップフロップ３３は、入力端ｉｎＢから入力したデータ１を記憶する。
【０１７１】
サイクルｔ１において、セレクタ３１は、入力端ｉｎＡからデータ８を入力とし、入力端ｉｎＢからデータ９を入力とする。セレクタ３１は、入力端ｉｎＢから入力したデータ９を選択する。フリップフロップ３２は、サイクルｔ０で記憶したデータ０を出力し、入力端ｉｎＢから入力するデータ９を記憶する。フリップフロップ３３は、記憶したデータ１を出力する。セレクタ３４は、フリップフロップ３２が出力するデータ０を選択して出力端ｏｕｔＡに出力する。また、セレクタ３５は、入力端ｉｎＡから入力したデータ８を選択して出力端ｏｕｔＢに出力する。
【０１７２】
サイクルｔ２において、フリップフロップ３２は、記憶した９を出力する。フリップフロップ３３は、記憶した１を出力する。セレクタ３４は、フリップフロップ３３が出力する１を選択して出力端ｏｕｔＡに出力する。セレクタ３５は、フリップフロップ３２が出力する９を選択して出力端ｏｕｔＢに出力する。
【０１７３】
以上のように、本実施形態のデータ並べ替え処理装置においては、ＲＡＭ回路を含む第１データ並べ替え手段と、ＲＡＭ回路を含まない第２並べ替え手段とを組み合わせてデータ並べ替え処理を実行する。本実施形態のデータ組内並べ替え装置を用いれば、複数のデータを、逐次順序からビットリバース順序へ並べ替えたり、ビットリバース順序から逐次順序へ並べ替えたりする際に用いるＲＡＭ回路の数を低減できる。すなわち、本実施形態によれば、高速フーリエ変換を用いたデジタル信号処理を実行する回路の回路規模を小さくすることに加えて、高速フーリエ変換装置の消費電力の低減や小型化に寄与できる。
【０１７４】
（第４の実施形態）
次に、本発明の第４の実施形態に係るＦＦＴ（Fast Fourier Transform）装置について図面を参照しながら説明する。以下においては、本実施形態のＦＦＴ装置を含む演算装置について説明する。
【０１７５】
図１４は、本実施形態のＦＦＴ装置４７を含む演算装置４０の構成例を示すブロック図である。図１４において、ＦＦＴ装置４７は、第１バタフライ演算処理部４２、第２データ並べ替え処理部４３、ひねり乗算処理部４４および第２バタフライ演算処理部４５を含む。演算装置４０は、第１データ並べ替え処理部４１および第３データ並べ替え処理部４６をＦＦＴ装置４７に加えた構成を有する。演算装置４０は、第１データ並べ替え処理、第１バタフライ演算処理、第２データ並べ替え処理、ひねり乗算処理、第２バタフライ演算処理、第３データ並べ替え処理をパイプライン処理する。
【０１７６】
第１データ並べ替え処理部４１、第２データ並べ替え処理部４３および第３データ並べ替え処理部４６のそれぞれは、第１の実施形態のデータ並べ替え処理装置１０の機能を有する。すなわち、第１データ並べ替え処理部４１、第２データ並べ替え処理部４３および第３データ並べ替え処理部４６のそれぞれは、第１データ並べ替え部１１と第２データ並べ替え部１２とを含む。本実施形態では、第１データ並べ替え処理部４１、第２データ並べ替え処理部４３、第３データ並べ替え処理部４６は同様の構成を有するものとして説明する。第２データ並べ替え処理部４３がデータ並べ替え処理装置１０の機能を有しさえすれば、第１データ並べ替え処理部４１および第３データ並べ替え処理部４６はデータ並べ替え処理装置１０の機能を有さなくてもよい。これ以降、第１データ並べ替え処理部４１、第２データ並べ替え処理部４３、第３データ並べ替え処理部４６を区別しない場合は、データ並べ替え処理部と記載することがある。
【０１７７】
第１データ並べ替え処理部４１（第１データ並べ替え処理手段とも呼ぶ）は、データ並べ替えのためのバッファ回路である。第１データ並べ替え処理部４１は、入力データを入力とする。第１データ並べ替え処理部４１は、第１バタフライ演算処理部４２の前段で、入力データに対して、ＦＦＴ処理のアルゴリズム上のデータの依存関係に基づいたデータシーケンスの並べ替えを行う。具体的には、第１データ並べ替え処理部４１は、入力データの入力順序である逐次順序を、第１バタフライ演算処理部４２に入力する順序であるビットリバース順序に並べ替える。
【０１７８】
第１バタフライ演算処理部４２（第１バタフライ演算処理手段とも呼ぶ）は、２段階で行われるバタフライ演算処理のうち１回目のバタフライ演算処理（第１バタフライ演算処理）を実行する。第１バタフライ演算処理部４２は、バタフライ演算処理の結果を逐次順序で出力する。
【０１７９】
第２データ並べ替え処理部４３（第２データ並べ替え処理手段とも呼ぶ）は、データ並べ替えのためのバッファ回路である。第２データ並べ替え処理部４３は、第１バタフライ演算処理部４２の後段で、ＦＦＴ処理のアルゴリズム上のデータの依存関係に基づいたデータシーケンスの並べ替えを行う。第２データ並べ替え処理部４３は、第１バタフライ演算処理部４２が逐次順序で出力するデータを、第２バタフライ演算処理部４５に入力するためのビットリバース順序に並べ替える。
【０１８０】
ひねり乗算処理部４４（ひねり乗算処理手段とも呼ぶ）は、第１バタフライ演算処理後に、ＦＦＴ演算における複素平面上の複素回転を処理する。なお、ひねり乗算処理部４４は、データの並べ替えを実行しない。
【０１８１】
第２バタフライ演算処理部４５（第２バタフライ演算処理手段とも呼ぶ）は、２段階で行われるバタフライ演算処理のうち２回目のバタフライ処理（第２バタフライ演算処理）を実行するバタフライ回路である。第２バタフライ演算処理部４５は、ビットリバース順序で入力されるひねり乗算処理後のデータに対して第２バタフライ演算処理を行い、処理結果をビットリバース順序で出力する。
【０１８２】
第３データ並べ替え処理部４６（第３データ並べ替え処理手段とも呼ぶ）は、データ並べ替えのためのバッファ回路である。第３データ並べ替え処理部４６は、第２バタフライ演算処理部４５の後段で、ＦＦＴ処理のアルゴリズム上のデータの依存関係に基づいたデータシーケンスの並べ替えを行う。第３データ並べ替え処理部４６は、第２バタフライ演算処理部４５がビットリバース順序で出力するデータを逐次順序に並べ替える。第３データ並べ替え処理部４６は、並べ替えたデータを出力データとして出力する。
【０１８３】
以上が、本実施形態のＦＦＴ装置４７を含む演算装置４０についての説明である。なお、演算装置４０は、第１データ並べ替え処理部４１、第２データ並べ替え処理部４３および第３データ並べ替え処理部４６のうち少なくともいずれかが、第１〜第３の実施形態のデータ並べ替え処理装置のいずれかを含めばよい。例えば、第１データ並べ替え処理部４１および第２データ並べ替え処理部４３を含まないＦＦＴ装置４７の場合は、第２データ並べ替え処理部４３が、第１〜第３の実施形態のデータ並べ替え処理装置のいずれかを含めばよい。
【０１８４】
〔データフロー〕
次に、図１５に示すデータフロー４００に従って、一般的なPrime Factor法を用いて、ＦＦＴ装置４７が、２段階の基数８のバタフライ処理に分解された６４ポイントＦＦＴをパイプライン回路方式によって処理する例について説明する。なお、図１５の例では、破線の枠で囲んだ構成（ＦＦＴ装置４７）が、８個のデータに対して並列で６４ポイントＦＦＴ処理を行うものとする。
【０１８５】
図１５のデータフロー４００は、バタフライ演算処理４０２、データ並べ替え処理４０３、ひねり乗算処理４０４、バタフライ演算処理４０５を含む。バタフライ演算処理４０２およびバタフライ演算処理４０５においては、延べ１６回の基数８のバタフライ演算処理が実行される。
【０１８６】
ＦＦＴのポイント数が大きい場合、図１５のデータフロー４００の全てを実現するためには、膨大な規模の回路を要する。そのため、ＦＦＴのポイント数が大きい場合、データフロー４００の全ての処理に対応させて回路を構成させるのではなく、データフロー４００の一部の処理をいずれかの回路に負わせる。すなわち、必要な処理性能に応じて、データフロー４００の一部分の処理を実現する回路を繰り返し使用することによって、ＦＦＴ処理の全体を実現する。図１５の例では、データフロー４００を８つの部分データフロー４１０ａ〜ｈに分割して処理を行う。
【０１８７】
例えば、図１５のデータフロー４００において、８個のデータに対して並列にＦＦＴ処理を行うＦＦＴ装置４７を物理的な回路として作成した場合、合計８回の繰り返し処理によって６４ポイントＦＦＴ処理を実現できる。
【０１８８】
８回の繰り返し処理では、８個のデータに対して行われる部分データフロー４１０ａ〜ｈのそれぞれに相当する処理を順に行う。なお、図１５においては、部分データフロー４１０ｃ、部分データフロー４１０ｄ、部分データフロー４１０ｅ、部分データフロー４１０ｆ、部分データフロー４１０ｇを省略している。
【０１８９】
具体的には、１回目には部分データフロー４１０ａに相当する処理を行い、２回目には部分データフロー４１０ｂに相当する処理を行う。以下同様に、３回目には部分データフロー４１０ｃ、４回目には部分データフロー４１０ｄ、５回目には部分データフロー４１０ｅ、６回目には部分データフロー４１０ｆ、７回目には部分データフロー４１０ｇに相当する処理を順次行う。そして、８回目には、部分データフロー４０５ｈに相当する処理を行う。このような一連の処理により、６４ポイントＦＦＴ処理を実現できる。
【０１９０】
図１５のデータフロー４００において、ＦＦＴブロックサイズをＮ（Ｎ：自然数）で表すと、ＦＦＴ装置４７は、時間領域のデータｘ（ｎ）を入力とする（ｎ＝０、１、・・・、Ｎ−１）。ＦＦＴ装置４７は、入力された時間領域のデータｘ（ｎ）をＦＦＴ処理によりフーリエ変換し、周波数領域の信号Ｘ（ｋ）を生成して出力する（ｋ＝０、１、・・・、Ｎ−１）。なお、図１５のデータフロー４００は、ＩＦＦＴ（Inverse Fast Fourier Transform）処理を行う場合についても、基本構成は同じである。
【０１９１】
このとき、ＦＦＴ装置４７は、入力データｘ（ｎ）として、８サイクルの期間において８データずつ逐次順序（図２）で合計６４個のデータを入力とする。なお、入力データｘ（ｎ）の入力に関しては、図２の格子中の０から６３までの数字はｘ（ｎ）の添え字ｎを意味する。
【０１９２】
具体的には、１サイクル目において、ＦＦＴ装置４７は、データ列Ｐ１を構成するｘ（０）、ｘ（１）、・・・、ｘ（７）の８データを入力とする。２サイクル目において、ＦＦＴ装置４７は、データ列Ｐ２を構成するｘ（８）、ｘ（９）、・・・、ｘ（１５）の８データを入力とする。同様に、３サイクル目から８サイクル目まで、ＦＦＴ装置４７は、データ列Ｐ３〜Ｐ８を構成するデータを入力とする。
【０１９３】
同様に、ＦＦＴ装置４７は、出力データＸ（ｋ）として、８サイクルの期間において８データずつ逐次順序（図２）で６４データを出力する。なお、出力データＸ（ｋ）の出力に関しては、図２の表中の０から６３までの数字はＸ（ｋ）の添え字ｋを意味する。
【０１９４】
具体的には、１サイクル目において、ＦＦＴ装置４７は、データ列Ｐ１を構成するＸ（０）、Ｘ（１）、・・・、Ｘ（７）の８データを出力する。２サイクル目において、ＦＦＴ装置４７は、データ列Ｐ２を構成するＸ（８）、Ｘ（９）、・・・、Ｘ（１５）の８データを出力する。同様に、３サイクル目から８サイクル目まで、ＦＦＴ装置４７は、データ列Ｐ３〜Ｐ８を構成するデータを出力する。
【０１９５】
図３に示すビットリバース順序は、図１５に示したデータフロー図において、１段目の基数８のバタフライ処理５０２への入力データ列に対応する。具体的には、１サイクル目において、ＦＦＴ装置４７は、データ列Ｐ１を構成するｘ（０）、ｘ（８）、・・・、ｘ（５６）の８データを入力とする。そして、２サイクル目において、ＦＦＴ装置４７は、データ列Ｐ２を構成するｘ（１）、ｘ（９）、・・・、ｘ（５７）の８データを入力とする。同様に、ＦＦＴ装置４７は、３サイクル目から８サイクル目まで、データ列Ｐ３〜Ｐ８を構成するデータを入力とする。
【０１９６】
図２における各行ｐｓ（ｉ）および図３における８つの行ｑｓ（ｉ）は、それぞれ、次段のｉデータ目に入力されるデータを示す。各データ列に含まれる８個の数字は、ＦＦＴのポイントのうちの１個を特定する識別情報であり、具体的にはｘ（ｎ）の添え字ｎの値である。
【０１９７】
なお、逐次順序およびビットリバース順序は、図２および図３に例示されたものに限定されない。すなわち、逐次順序の各データ列は、上記のように、ＦＦＴのポイント数やサイクル数、並列に処理するデータ数に応じて、データを順に並べて作成すればよい。そして、ビットリバース順序の各データ列は、上記のように、逐次順序で入力されるデータに関して、サイクルの進行に対する順序とデータ位置に対する順序を入れ替えて作成すればよい。
【０１９８】
（第５の実施形態）
次に、本発明の第５の実施形態に係るデジタルフィルタ装置について図面を参照しながら説明する。
【０１９９】
図１６は、本実施形態のデジタルフィルタ装置５０の構成を示すブロック図である。デジタルフィルタ装置５０は、ＦＦＴ回路５１、フィルタ処理回路５２およびＩＦＦＴ回路５３を備える。ＦＦＴ回路５１およびＩＦＦＴ回路５３のうち少なくとも一方は、本発明の各実施形態において説明したデータ並べ替え処理装置を含む。
【０２００】
ＦＦＴ回路５１は、時間領域における複素数信号ｘ（ｎ）を入力とする。なお、本実施形態において、ｎは、時間領域上の信号サンプル番号を示す０≦ｎ≦Ｎ−１の整数であり、ＮはＦＦＴの変換サンプル数（ＦＦＴブロックサイズ）を示す自然数である。複素数信号ｘ（ｎ）は、実部ｒ（ｎ）、虚部ｓ（ｎ）および虚数単位ｊを用いて、以下の式４のように表される。
ｘ（ｎ）＝ｒ（ｎ）＋ｊｓ（ｎ）・・・（４）
ＦＦＴ回路５１は、入力された複素数信号ｘ（ｎ）を、ＦＦＴによって周波数領域の複素数信号Ｘ（ｋ）に変換する。なお、本実施形態において、ｋは、周波数領域上の周波数番号を示す０≦ｋ≦Ｎ−１の整数である。複素数信号Ｘ（ｋ）は、実部Ａ（ｋ）、虚部Ｂ（ｋ）および虚数単位ｊを用いて、以下の式５のように表される。
Ｘ（ｋ）＝Ａ（ｋ）＋ｊＢ（ｋ）・・・（５）
ＦＦＴ回路５１は、複素数信号Ｘ（ｋ）をフィルタ処理回路５２に出力する。
【０２０１】
フィルタ処理回路５２は、ＦＦＴ回路５１から入力される複素数信号Ｘ（ｋ）に対して、フィルタ係数Ｃ（ｋ）を用いて複素数乗算による複素数フィルタ処理を実行し、複素数信号Ｘ’（ｋ）を算出する。複素数信号Ｘ’（ｋ）は、以下の式６によって算出される。
Ｘ’（ｋ）＝Ｘ（ｋ）×Ｃ（ｋ）・・・（６）
フィルタ処理回路５２は、算出した複素数信号Ｘ’（ｋ）をＩＦＦＴ回路５３に出力する。
【０２０２】
ＩＦＦＴ回路５３は、入力された複素数信号Ｘ’（ｋ）に対して、ＩＦＦＴによって時間領域の複素数信号ｘ’’（ｎ）を生成する。ＩＦＦＴ回路５３は、生成した複素数信号ｘ’’（ｎ）を出力する。
【０２０３】
以上のように、本実施形態のデジタルフィルタ装置によれば、各実施形態のデータ並べ替え装置を含む高速フーリエ変換装置または逆フーリエ変換装置を用いることによって、フィルタ処理を実行する回路の回路規模を一般的な回路と比べて小さくできる。
【０２０４】
（ハードウェア）
ここで、本発明の第５の実施形態に係るデジタルフィルタ装置のハードウェア構成について、図１７の情報処理装置９０を一例として挙げて説明する。なお、図１７の情報処理装置９０は、本発明の第５の実施形態に係るデジタルフィルタ装置を実現するための構成例であって、本発明の範囲を限定するものではない。
【０２０５】
図１７のように、情報処理装置９０は、プロセッサ９１、主記憶装置９２、補助記憶装置９３、入出力インターフェース９５および通信インターフェース９６を備える。なお、図１７においては、インターフェースをＩ／Ｆ（Interface）と略して表記する。プロセッサ９１、主記憶装置９２、補助記憶装置９３、入出力インターフェース９５および通信インターフェース９６は、バス９９を介して互いにデータ通信可能に接続される。また、プロセッサ９１、主記憶装置９２、補助記憶装置９３および入出力インターフェース９５は、通信インターフェース９６を介して、インターネットやイントラネットなどのネットワークに接続される。
【０２０６】
プロセッサ９１は、補助記憶装置９３等に格納されたプログラムを主記憶装置９２に展開し、展開されたプログラムを実行する。本実施形態においては、情報処理装置９０にインストールされたソフトウェアプログラムを用いる構成とすればよい。プロセッサ９１は、本実施形態に係る高速フーリエ変換装置による処理を実行する。
【０２０７】
主記憶装置９２は、プログラムが展開される領域を有する。主記憶装置９２は、例えばＤＲＡＭ（Dynamic Random Access Memory）などの揮発性メモリとすればよい。また、ＭＲＡＭ（Magnetoresistive Random Access Memory）などの不揮発性メモリを主記憶装置９２として構成・追加してもよい。
【０２０８】
補助記憶装置９３は、種々のデータを記憶する。補助記憶装置９３は、ハードディスクやフラッシュメモリなどのローカルディスクによって構成される。なお、種々のデータを主記憶装置９２に記憶させる構成とし、補助記憶装置９３を省略することも可能である。
【０２０９】
入出力インターフェース９５は、情報処理装置９０と周辺機器とを接続するためのインターフェースである。通信インターフェース９６は、規格や仕様に基づいて、インターネットやイントラネットなどのネットワークを通じて、外部のシステムや装置に接続するためのインターフェースである。入出力インターフェース９５および通信インターフェース９６は、外部機器と接続するインターフェースとして共通化してもよい。
【０２１０】
情報処理装置９０には、必要に応じて、キーボードやマウス、タッチパネルなどの入力機器を接続するように構成してもよい。それらの入力機器は、情報や設定の入力に使用される。なお、タッチパネルを入力機器として用いる場合は、表示機器の表示画面が入力機器のインターフェースを兼ねる構成とすればよい。プロセッサ９１と入力機器との間のデータ通信は、入出力インターフェース９５に仲介させればよい。
【０２１１】
また、情報処理装置９０には、情報を表示するための表示機器を備え付けてもよい。表示機器を備え付ける場合、情報処理装置９０には、表示機器の表示を制御するための表示制御装置（図示しない）が備えられていることが好ましい。表示機器は、入出力インターフェース９５を介して情報処理装置９０に接続すればよい。
【０２１２】
また、情報処理装置９０には、必要に応じて、ディスクドライブを備え付けてもよい。
ディスクドライブは、バス９９に接続される。ディスクドライブは、プロセッサ９１と図示しない記録媒体（プログラム記録媒体）との間で、記録媒体からのデータ・プログラムの読み出し、情報処理装置９０の処理結果の記録媒体への書き込みなどを仲介する。記録媒体は、例えば、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光学記録媒体で実現できる。また、記録媒体は、ＵＳＢ（Universal Serial Bus）メモリやＳＤ（Secure Digital）カードなどの半導体記録媒体や、フレキシブルディスクなどの磁気記録媒体、その他の記録媒体によって実現してもよい。
【０２１３】
以上が、本発明の第５の実施形態に係るデジタルフィルタ装置を可能とするためのハードウェア構成の一例である。なお、図１７のハードウェア構成は、本発明の第５の実施形態に係るデジタルフィルタ装置のハードウェア構成の一例であって、本発明の範囲を限定するものではない。また、本発明の第５の実施形態に係るデジタルフィルタ装置に関する処理をコンピュータに実行させるプログラムも本発明の範囲に含まれる。さらに、本発明の第５の実施形態に係るデジタルフィルタ処理に関するプログラムを記録したプログラム記録媒体も本発明の範囲に含まれる。
【０２１４】
以上の各実施形態の高速フーリエ変換装置の構成要素は、任意に組み合わせることができる。また、各実施形態の高速フーリエ変換装置の構成要素は、ソフトウェアによって実現してもよい。また、各実施形態の高速フーリエ変換装置は、回路として実現してもよい。
【０２１５】
以上、実施形態を参照して本発明を説明してきたが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０２１６】
この出願は、２０１７年８月７日に出願された日本出願特願２０１７−１５２６５８を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０２１７】
１０    データ並べ替え処理装置
１１    第１データ並べ替え部
１２    第２データ並べ替え部
２０    データ並べ替え処理装置
２１    第１データ並べ替え部
２２    第２データ並べ替え部
３０    データ組内並べ替え装置
３１、３４、３５    セレクタ
３２、３３    フリップフロップ
４０    演算装置
４１    第１データ並べ替え処理部
４２    第１バタフライ演算処理部
４３    第２データ並べ替え処理部
４４    ひねり乗算処理部
４５    第２バタフライ演算処理部
４６    第３データ並べ替え処理部
４７    ＦＦＴ装置
５０    デジタルフィルタ装置
５１    ＦＦＴ回路
５２    フィルタ処理回路
５３    ＩＦＦＴ回路
２１１    第１データ振り分け部
２１３    ＲＡＭ回路
２１５    第２データ振り分け部
２２１    データ組内並べ替え部
【図１】
2019031418.tif 000003
【図２】
2019031418.tif 000004
【図３】
2019031418.tif 000005
【図４】
2019031418.tif 000006
【図５】
2019031418.tif 000007
【図６】
2019031418.tif 000008
【図７】
2019031418.tif 000009
【図８】
2019031418.tif 000010
【図９】
2019031418.tif 000011
【図１０】
2019031418.tif 000012
【図１１】
2019031418.tif 000013
【図１２】
2019031418.tif 000014
【図１３】
2019031418.tif 000015
【図１４】
2019031418.tif 000016
【図１５】
2019031418.tif 000017
【図１６】
2019031418.tif 000018
【図１７】
2019031418.tif 000019
【手続補正書】
【提出日】令和2年1月23日(2020.1.23)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
複数の第１のデータを第１の順序で入力する処理と、
前記複数の第１のデータに含まれる所定数のデータによって構成されるデータ組を移動単位として前記複数の第１のデータを第３の順序に並べ替える処理と、
前記データ組に含まれる前記所定数のデータ間で並べ替えを行うことによって、前記第３の順序に並べ替えられた前記複数の第１のデータを第２の順序に並べ替える処理とを含む高速フーリエ変換処理をコンピュータに実行させるプログラム。
【国際調査報告】
2019031418.tif 000020
2019031418.tif 000021