(57)【要約】  【課題】  回路規模が増大せず、価格も高騰しないＦＦＴ処理装置を提供する。  【解決手段】  制御部１４は、前段の演算（ h(t,r) ）を行うためのデータをバッファ１３に準備するため、メモリ１１から第１方向のデータを順次読みだしてバッファ１３の第１方向の該当する部分に順次保存する。その後、制御部１４は、バッファ１３から第２方向でデータを読み出し、第２方向のデータの読み出しにより空いた領域に第２方向で新規データを書き込んだ後、第１方向でデータを読み出し、第１方向のデータの読み出しにより空いた領域に第１方向で新規データを書き込む動作を反復する。これにより、ＦＦＴ処理の前段の演算 h(t,r)のためのデータが準備できる。【選択図】  図４
2006155487.tif 000002
【特許請求の範囲】
【請求項１】
高速フーリエ変換（ＦＦＴ）処理対象のデータを保存する第１メモリと、
第１メモリから読みだしたデータを保持し、前記保持したデータを読みだして転置可能な、第２メモリと、
前記第２メモリに保持されたデータを用いて前段の演算処理を行い、得られた前段の演算結果（ h(t,r) ）を用いてＦＦＴ処理を行うＦＦＴ演算手段と、
前記第１メモリの動作、前記第２メモリの動作および前記ＦＦＴ演算手段の動作を制御する制御手段と
を備え、
前記制御手段は、前記前段の演算（ h(t,r) ）を行うためのデータを前記第２メモリに準備するため、
前記前段の演算に必要なデータについて、前記第１メモリから、第１方向のデータを順次読みだして前記第２メモリの第１方向の該当する部分に順次保存する第１制御動作と、  前記前段の演算のため前記第２メモリから第２方向でデータを読み出し、これにより空いた領域に第２方向で新規データを書き込む第２制御動作と、
前記前段の演算のため前記第２メモリから第１方向でデータを読み出し、これにより空いた領域に第１方向で新規データを書き込む第３制御動作と、
前記第２制御動作と前記第３制御動作を必要回数反復する第４制御動作と
を行う、
高速フーリエ変換処理装置。
【請求項２】
前記第２メモリは、
第１メモリより容量が少ないメモリ素子と、
前記メモリ素子に保持されたデータを選択し、転置するセレクタ手段と
を有する
請求項１に記載の高速フーリエ変換処理装置。
【請求項３】
前記第２メモリのメモリ素子はフリップフロップである、
請求項２に記載の高速フーリエ変換処理装置。
【請求項４】
前記第２メモリに準備された前段の演算用データを用いて前段の演算を行い、その結果を用いてＦＦＴ処理を行う、
請求項１〜３のいずれかに記載の高速フーリエ変換処理装置。
【請求項５】
演算処理対象のデータを保存する第１メモリと、
前記第１メモリから読みだしたデータを保持し、前記保持したデータを読みだして転置可能な、第２メモリと、
演算処理手段と、
前記第１メモリの動作、前記第２メモリの動作および前記演算処理手段の動作を制御する制御手段と
を備え、
前記制御手段は、
前記第１メモリから読みだした第１方向の所定の単位のデータを前記第２メモリの第１方向に記憶させ、
下記の動作を所望の数だけ反復する、
（ａ）転置したデータを読みだすため、前記第２メモリから第２方向の所定の単位のデータを読み出し、
（ｂ）該第２方向のデータの読み出しを行った前記第２メモリの部分に、第２方向の次のデータを記憶し、
（ｃ）転置したデータを読みだすため、前記第２メモリから第１方向の所定の単位のデータを読み出し、
（ｄ）該第１方向のデータの読み出しを行った前記第２メモリの部分に、第１方向の次のデータを記憶する、
演算処理用制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＦＦＴ処理を高速で行う高速フーリエ変換（ＦＦＴ：Fast Fourier Transform）処理装置に関する。特に本発明は、ＦＦＴ処理装置におけるメモリの規模を削減する技術に関する。
また本発明は演算処理用制御装置に関する。
【背景技術】
【０００２】
フーリエ変換処理技術は、画像処理、信号分析処理などに広く活用されている。
そのような処理を高速に行うため、フーリエ変換を高速に行うことが求められており、高速フーリエ変換（ＦＦＴ）処理技術は、フーリエ変換処理を高速に行う技術であり、フーリエ変換処理を高速化する技術は多々存在する（非特許文献１）。
また、ＦＦＴ処理回路を小規模に構成する試み、小電力消費化の試みなどが行われている。
【０００３】
そのような技術の１つとして、ＦＦＴ処理を行う際、ＦＦＴ処理装置から演算結果をまとめて出力する必要の無い場合は、処理を分割することにより、使用するメモリを少なくすることが試みられている。
たとえば、６５５３６点ＦＦＴ処理の場合、たとえば、以下に示すように、前段の演算と、１６個の４０９６点ＦＦＴ処理に分けることができる。
１６個の４０９６点ＦＦＴ処理を１つずつ行うのであれば、ＦＦＴ処理装置におけるメモリは、６５５３６点分の容量を必要とせず、４０９６点ＦＦＴを行うのに必要な容量があれば良いことになり、メモリの規模が小さくなり、コスト面でメリットがある。
【０００４】
６５５３６点の離散フーリエ変換（ＤＦＴ：Discrete Fourier Transform) 処理のため計算式は、回転因子ＷＮをＷＮ＝ｅｘｐ（−ｊ２π／Ｎ）とすると、下記式１で表すことができる。
【０００５】
【数１】
2006155487.tif 000003
【０００６】
上記式に、因子（パラメータ）ｋ＝１６ｓ＋ｔを代入すると下記式２に書き表すことができる。ただし、ｓはｓ＝０，１，２，…，４０９５であり、ｔはｔ＝０，１，２，…１５である。
【０００７】
【数２】
2006155487.tif 000004
【０００８】
式２において、鍵括弧（〔  〕）内の内容は前段の演算内容を示し、鍵括弧の外が４０９６点ＤＦＴ処理となる。
ここで、前段の演算結果を下記式で定義する h(t,r) とする。
【０００９】
【数３】
2006155487.tif 000005
【００１０】
図１は前段の演算結果 h(t,r) を算出する信号流れ図であり、図２は算出した演算結果 h(t,r) をＦＦＴ処理してＦＦＴ処理結果Ｆをうるための４０９６点ＦＦＴのデータの流れを示すグラフである。
図１において、ｆはメモリ、たとえば、ＲＡＭのビットを示し、ｆ（ｒ）はｒ番目のビットを示す。○は節（ノードＮ）を示す。矢印はデータの流れを示す。  前段の演算結果 h(t,r) の演算に必要なデータは、データの間隔が４０９６で、次のようになっている。
下記において、たとえば、f(0) , f(4096),  f(8192), f(12288), …, f(61440)は、メモリを構成するビットの番号を示しており、メモリは、たとえば、６５５３６個のデータを保持するため、メモリとして６５５３６個のビットを有する。
【００１１】
（１）h(0,0)の演算に必要なデータ（１６個）：
f(0) , f(4096),  f(8192), f(12288),…, f(61440)
（２）h(0.1)の演算に必要なデータ（１６個）：
f(1) , f(4097),  f(8193), f(12289),…, f(61441)
（３）h(0,2)の演算に必要なデータ（１６個）：
f(2) , f(4098),  f(8194), f(12290),…, f(61442)
以下、同様にして、
（４）h(0,4095) の演算に必要なデータ（１６個）：
(4095), f(8191), f(12287), f(16383), …, f(65535)
【００１２】
データが、メモリの中で、ビットf(0), f(1), f(2), f(3), ・・・の順で保存されていて、メモリの構成（ビット幅）が、たとえば、１６ビットの場合、前段の演算結果h(0,0)の値を算出するためには、図３において、太い黒枠線で例示したように、必要なデータが飛び飛びに保存されているため、メモリからデータを１６回リードする（読みだす）必要がある。
図３はメモリ内のデータの配置例を示す図である。
【００１３】
上記方法では、最初の４０９６点ＦＦＴ処理を行うのに必要な前段の演算結果 h(0,0), h(0,1), h(0,2),…, h(0,4095) を全て算出するには、メモリのリード（読み出し）回数は、１６×４０９６＝６５５３６回となる。１６回の４０９６点ＦＦＴ処理の合計では、メモリのリード回数は、６５５３６×１６＝１０４８５７回にもなる。これは、ＦＦＴ処理装置の処理速度や、ＦＦＴ処理装置の消費電力の点から好ましくない。
【００１４】
メモリのアクセス回数を減らすために、一度リードしたデータをバッファに保持しておき、必要なデータをすぐに取り出せるようにしておくという方法がある。その回路構成例を図４に示す。
図４において、ＦＦＴ処理装置は、メモリ１１と、ＦＦＴ演算部１２と、制御部１４とを有し、メモリ１１とＦＦＴ演算部１２との間にバッファ１３を設けている。制御部１４がメモリ１１からリードしたデータを一旦バッファ１３に保持させている。
【００１５】
図４に図解した装置における制御部１４のバッファ１３のメモリ制御方法を図５（Ａ）〜（Ｄ）、および、図６（Ａ）〜（Ｄ）に示す。
図５（Ａ）〜（Ｄ）はバッファ１３へデータをライトする（書き込む）動作の制御方法を示し、図６（Ａ）〜（Ｄ）はバッファ１３からデータをリードする動作の制御方法を示す。
図５（Ａ）〜（Ｄ）に図解したように、制御部１４は必要となる飛び飛びのデータを、あらかじめバッファ１３に保持しておき、制御部１４は、図６（Ａ）〜（Ｄ）および下記手順で、４０９６ビット間隔のデータをバッファ１３に一度に読み出せるようにしておく。
f(0), f(4096), f(8192), f(12288),…
【００１６】
これにより、制御部１４によるバッファ１３からデータのリードは、１回の４０９６点ＦＦＴ処理当たり４０９６回、１６回の４０９６点ＦＦＴ合計で４０９６×１６＝６５５３６回で済むことになる。
【非特許文献１】「高速フーリエ変換」、Ｅ．ＯＲＡＮ  ＢＲＩＧＨＡＭ著、宮川洋、今井秀樹訳、科学技術出版社、昭和５３年１２月１５日初版
【発明の開示】
【発明が解決しようとする課題】
【００１７】
しかし、上述したバッファ構成では、バッファ１３に新しいデータをライトすると、既存のデータに上書きしてしまうため、バッファ１３から全てのデータのリードが終了しない限り、次のデータをバッファ１３にライトすることはできない。
したがって、ＦＦＴ処理を連続的に行うには、バッファ１３に相当する、たとえば、多数のフリップフロップなどで構成されるバッファを２つ用意し、２つのバッファを交互に使用することになる。その結果、ＦＦＴ処理装置の回路規模が大きくなり、価格も高騰するという欠点があった。
【００１８】
本発明の目的は、回路規模が増大せず、価格も高騰しない高速フーリエ変換（ＦＦＴ）処理装置を提供することにある。
本発明はさらに演算処理用制御装置を提供することにある。
【課題を解決するための手段】
【００１９】
本発明によれば、高速フーリエ変換（ＦＦＴ）処理対象のデータを保存する第１メモリと、該第１メモリから読みだしたデータを保持し、前記保持したデータを読みだして転置可能な、第２メモリと、該第２メモリに保持されたデータを用いて前段の演算処理を行い、得られた前段の演算結果（ h(t,r) ）を用いてＦＦＴ処理を行うＦＦＴ演算手段と、前記第１メモリの動作、前記第２メモリの動作および前記ＦＦＴ演算手段の動作を制御する制御手段とを備え、前記制御手段は、前記前段の演算（ h(t,r) ）を行うためのデータを前記第２メモリに準備するため、前記前段の演算に必要なデータについて、前記第１メモリから、第１方向のデータを順次読みだして前記第２メモリの第１方向の該当する部分に順次保存する第１制御動作と、前記前段の演算のため前記第２メモリから第２方向でデータを読み出し、これにより空いた領域に第２方向で新規データを書き込む第２制御動作と、前記前段の演算のため前記第２メモリから第１方向でデータを読み出し、これにより空いた領域に第１方向で新規データを書き込む第３制御動作と、前記第２制御動作と前記第３制御動作を必要回数反復する第４制御動作とを行う、高速フーリエ変換処理装置が提供される。
【００２０】
また本発明によれば、演算処理対象のデータを保存する第１メモリと、前記第１メモリから読みだしたデータを保持し、前記保持したデータを読みだして転置可能な、第２メモリと、演算処理手段と、前記第１メモリの動作、前記第２メモリの動作および前記演算処理手段の動作を制御する制御手段とを備え、前記制御手段は、前記第１メモリから読みだした第１方向の所定の単位のデータを前記第２メモリの第１方向に記憶させ、下記の動作を所望の数だけ反復する、（ａ）転置したデータを読みだすため、前記第２メモリから第２方向の所定の単位のデータを読み出し、（ｂ）該第２方向のデータの読み出しを行った前記第２メモリの部分に、第２方向の次のデータを記憶し、（ｃ）転置したデータを読みだすため、前記第２メモリから第１方向の所定の単位のデータを読み出し、（ｄ）該第１方向のデータの読み出しを行った前記第２メモリの部分に、第１方向の次のデータを記憶する演算処理用制御装置が提供される。
【発明の効果】
【００２１】
本発明に係る高速フーリエ変換処理装置は、従来に比べて小規模の回路構成となる。特に、第２メモリ（バッファ回路）の容量が縮小できる。
もちろん、本発明に係る高速フーリエ変換処理装置は、従来と同等の機能、速度を実現することができる。
【００２２】
演算処理用制御装置についても第２メモリの容量が縮小できる。
【発明を実施するための最良の形態】
【００２３】
本発明の高速フーリエ変換（ＦＦＴ）処理装置の第１実施の形態について述べる。
本発明の実施の形態のＦＦＴ処理装置の基本装置構成は、図４に図解したものと同じであり、ＦＦＴ処理装置は、ＦＦＴ演算処理対象のデータが入力され、そのデータを保持するメモリ１１と、ＦＦＴ演算部１２と、バッファ１３と、制御部１４とを有する。
しかしながら、本発明のＦＦＴ処理装置は、上述したＦＦＴ処理装置とは、た制御部１４による制御部１４の制御方法が新規であり、バッファ１３のメモリ容量も少ない。
【００２４】
図６（Ｂ）〜（Ｄ）において、リード済みの領域は、上書きしても問題が無い。
たとえば、図６（Ｂ）のリード済の領域は、図６（Ａ）の黒枠線で囲んだバッファ１３におけるデータ部分のリード処理によりリード済の状態になっている。同様、図６（Ｃ）のリード済の領域は、図６（Ａ）および図６（Ｂ）の黒枠線で囲んだバッファ１３におけるデータ部分のリード処理によりリード済の状態になっている。
このため、バッファ１３のリード済みの部分に、次のデータをライトすることにより、処理速度を犠牲にすることなく、バッファ１３を少ないメモリ容量のままで、処理を行うことができる。
本発明は、本願発明者による、上記したＦＦＴ処理とデータ配置に起因するバッファ１３の使用方法の知見に基づく。
【００２５】
本発明者が見いだした上述した知見に基づく、制御部１４によるメモリ１１およびバッファ１３の制御方法の詳細を、図７（Ａ）〜（Ｃ）、図８（Ａ）〜（Ｃ）および図９（Ａ）〜（Ｃ）に示す。
図７（Ａ）〜（Ｃ）は、本発明の実施の形態のＦＦＴ処理装置におけるメモリ１１から読みだしたデータをバッファ１３に書き込むライト動作を示す図である。図７（Ａ）〜（Ｃ）において、上部の小さな矩形の枠で囲んだ部分がメモリ１１から読みだしたデータを示しており、その下部の大きな枠がバッファ１３のメモリ、たとえば、好適には、フリップフロップで構成したメモリの配列を示している。
図８（Ａ）〜（Ｃ）は、本発明の実施の形態のＦＦＴ処理装置におけるバッファ１３からデータを読み出すリード動作とバッファ１３にデータを書き込むライト動作を示す図であり、特に、図８（Ａ）〜（Ｃ）は列（Ｙ）方向にリード動作とライト動作を行う場合を示す図である。
図９（Ａ）〜（Ｃ）は、本発明の実施の形態のＦＦＴ処理装置におけるバッファ１３からデータを読み出すリード動作とバッファ１３にデータを書き込むライト動作を示す図であり、特に、図９（Ａ）〜（Ｃ）は行（Ｘ）方向にリード動作とライト動作を行う場合を示す図である。
【００２６】
制御部１４によるバッファ１３に対するデータのリード動作、および、ライト動作の手順は以下のようになる。
【００２７】
ステップ１：メモリ１１からバッファ１３へのデータ書き込み（転送）
制御部１４は、図７（Ａ）〜（Ｄ）に図解のように、ＦＦＴ演算対象のデータをメモリ１１から行（図の横方向）単位でリードして、行（図の横方向）単位でバッファ１３に順次、ライトする。
たとえば、１回に１６ワードのデータをバッファ１３にライトする。
【００２８】
ステップ２： h(t,r) の演算のためバッファ１３から列単位でデータのリードと、リード済領域への列単位でのデータのライト
制御部１４は、前段の演算結果 h(t,r) 、たとえば、最初の前段の演算結果、 h(0,0), h(0,1), h(0,2),…, h(0,15) を算出するため、制御部１４は、たとえば、図８（Ａ）に例示したように、左から列（図の縦方向）単位でデータ（0,4096,8192,…,61440) をバッファ１３からリードする。
これに合わせ、制御部１４は、たとえば、図８（Ａ）に例示したように、バッファ１３の上記リード済みの部分に、次のデータ(16,17,18,…,31)をバッファ１３にライトする。
【００２９】
ステップ３：行単位でデータのリードとリード済領域への行単位でデータのライト
次いで制御部１４は、前段の演算結果、 h(0,16), h(0,17), h(0,18),…,h(0,31) を算出するため、制御部１４は、たとえば、図９（Ａ）に図解したように、上から行単位でデータ(16,4112, 8208, …,61456) をバッファ１３からリードする。
これに合わせ、制御部１４はバッファ１３の上記リード済みの部分に、次のデータ(32,33,34,…,47)をライトする。
【００３０】
ステップ４、反復処理
その後、，制御部１４は、最後の前段の演算結果h(0,4095) を算出するまで、ステップ２、３を動作を繰り返す。
【００３１】
ＦＦＴ演算部１２は、こうしてバッファ１３から得られたデータを用いて、４０９６点ＦＦＴ処理を実行する。
【００３２】
以上述べた制御部１４によるバッファ１３へのデータライト、および、リード・ライト動作により、メモリ容量２５６の１個のバッファ１３だけで、連続してＦＦＴ処理を行うことができる。
すなわち、本実施の形態においては、１６×１６ビットについて例示しているので、バッファ１３の容量は２５６ビットとなる。バッファ１３の容量がこのように小さくてよいので、バッファ１３として、フリップフロップなどの高速動作のメモリ素子で構成することができる。
【００３３】
バッファの回路構成例
図１０は上述した処理を実現するためのバッファ１３の回路例を示す。図１０には、メモリ１１から読みだされてバッファ１３に書き込まれる１６ビットのデータも図示している。
本例のバッファ１３は、好ましくは、マトリクス状に配置された１６×１６＝２５６個のフリップフロップ（Ｆ／Ｆ）ｆ00〜f0F,f10 〜f1F,f20 〜f2F,…,fF0〜fFF を有する。
他方、ＦＦＴ処理対象のデータを保持するメモリ１１は、たとえば、ＲＡＭである。
【００３４】
本例のバッファ１３は、ビットデータの選択を行う複数のマトリクス状に配置されたマルチプレクサ（または、ビットセレクタ)m01〜m0F,m10 〜m1F,m20 〜m2F,…,mF0〜mFF を有する。ビットデータの選択を行う複数のマトリクス状に配置されたマルチプレクサは、データの行と列とを入れ換える（転置させる）ために配設されている、データ転置用マルチプレクサである。
上述した複数のマトリクス状に配置されたデータ転置用マルチプレクサは、対応するフリップフロップの前段に位置し、２つのビットデータを入力し、制御部１４の制御のもとで、いずれか一方を後段のフリップフロップに出力するが、データの転置が起きない対角部分には、ビットデータ選択用のマルチプレクサは配設されていない。
【００３５】
バッファ１３はさらに、行（Ｘ）データ選択用（または第１）マルチプレクサ m101 と、列（Ｙ）データ選択用（または第２）マルチプレクサm102を有し、各フリップフロップの出力は、行データ選択用マルチプレクサ m101 と、列データ選択用マルチプレクサm102に分岐されて入力されている。
【００３６】
たとえば、１段目のフリップフロップf00 〜f0F の一方の出力は、行データ選択用マルチプレクサ m101 の「０」ビット入力端子に接続されている。他方、１段目のフリップフロップf00 〜f0F の他方の出力はそれぞれ、列データ選択用マルチプレクサ m102 の「０」, 「１」, …、「Ｆ」ビット入力端子に接続されている。
同様に、２段目のフリップフロップf10 〜f1F の一方の出力は、行データ選択用マルチプレクサ m101 の「１」ビット入力端子に接続されており、２段目のフリップフロップf100〜f10Fの他方の出力はそれぞれ、列データ選択用マルチプレクサ m102 の「０」, 「１」, …、「Ｆ」ビット入力端子に接続されている。
制御部１４は、マルチプレクサ m101 、m102に選択信号を印加して、マルチプレクサ m101 、m102のいずれかから、１６ビットのデータを出力させる。
【００３７】
バッファ１３はさらにマルチプレクサ m103 を有しており、マルチプレクサ m103 はマルチプレクサ m101 、m102のいずれかから出力された１６ビットデータのいずれかを、制御部１４の制御のもとで、それぞれ１６ビットのＸデータまたはＹデータとして出力する。
【００３８】
上述した制御部１４によるバッファ１３の制御方法に対応させて説明する。
【００３９】
ステップ１ａ：行単位でメモリ１１から読みだした１６ビットのデータをバッファ１３にライト
制御部１４は、図１０に図示のごとく、行単位でメモリ１１から読みだした１６ビットのデータを、図１０に図解した構成を持つバッファ１３にライトする。
このため、制御部１４は、バッファ１３におけるＸ方向のマルチプレクサ m01, m02, m03, …, mFD, mFEなどＸ（行）方向のものを選択する。
【００４０】
制御部１４によるバッファ１３内のフリップフロップへの行単位でのデータの書き込みは、以下のように行う。
１行目のライト：フリップフロップ f00, f01, f02,…, f0F に対応するビットデータを書き込む。
２行目のライト：フリップフロップ f10, f11, f12,…, f1F に対応するビットデータを書き込む。
３行目のライト：フリップフロップ f20, f21, f22,…, f2F に対応するビットデータを書き込む。
以下同様に行う。
１６行目のライト：フリップフロップ fF0, fF1, fF2,…, fFF に対応するビットデータを書き込む。
【００４１】
ステップ２ａ：列単位でバッファ１３からデータをリード・ライト
制御部１４は、Ｙ方向（列方向）のデータの選択を行う。すなわち、制御部１４は、マルチプレクサm103からＹ方向（列方向）のマルチプレクサ m1020から入力されたデータが出力されるようにする。
また、制御部１４の制御により、マルチプレクサ m01, m02, m03, …, mFD, mFEについて、Ｙ方向（列方向）のデータを選択する。
【００４２】
制御部１４の制御のもとで、リード用セレクタとして機能するマルチプレクサ m103 、Ｆ／Ｆの書き込みは、具体的には、以下のように行う。
【００４３】
１列目のリード：マルチプレクサm102の端子“０”を選択する。
１列目のライト：フリップフロップ f00, f10, f20,…, fF0 にデータを書き込む。
２列目のリード：マルチプレクサm102の端子“１”を選択する。
２列目のライト：フリップフロップ f01, f11, f21,…, fF1 にデータを書き込む。
３列目のリード：マルチプレクサm102の端子“２”を選択する。
３列目のライト：フリップフロップ f02, f12, f22,…, fF2 にデータ書き込む。
以下同様に行う。
１６列目のリード：マルチプレクサm102の端子“Ｆ”を選択する。
１６列目のライト：フリップフロップ f0F, f1F, f2F,…, fFF にデータを書き込む。
【００４４】
ステップ３ａ：行単位でデータをリード／ライト
制御部１４の制御のもとで、マルチプレクサm103はＸ方向（行方向）のデータを選択する。
また、制御部１４の制御のもとで、マルチプレクサ m01, m02, m03, …, mFD, mFEも、Ｘ方向のデータを選択する。
【００４５】
リード用セレクタ（マルチプレクサ）と、フリップフロップの書き込みは、制御部１４の制御のもとで、以下のように行う。
１行目のリード：マルチプレクサm101の端子“０”を選択する。
１行目のライト：フリップフロップ f00, f01, f02,…, f0F にデータを書き込む。
２行目のリード：マルチプレクサm101の端子“１”を選択する。
２行目のライト：フリップフロップ f10, f11, f12,…, f1F にデータを書き込む。
３行目のリード：マルチプレクサm101の端子“２”を選択する。
３行目のライト：フリップフロップ f20, f21, f22,…, f2F にデータを書き込む。
以下同様に行う。
１６列目のリード：マルチプレクサm101の端子“Ｆ”を選択する。
１６行目のライト：フリップフロップ fF0, fF1, fF2,…, fFF にデータを書き込む。
【００４６】
以上により、バッファ１３に前段の演算結果 h(t,r) を刈るためのデータが準備され、そのデータを用いて前段の演算結果 h(t,r) が演算される。
さらに演算された前段の演算結果 h(t,r) を用いて、ＦＦＴ演算部１２においてＦＦＴ処理を行う。
【００４７】
以上述べたように、本発明の実施の形態のＦＦＴ処理装置によれば、バッファ１３を、たとえば、図１０に図解した回路構成にし、制御部１４が上述した制御処理を行うことにより、ＦＦＴ処理における前段の演算結果 h(t,r) の処理に必要なデータをバッファ１３に準備でき、その結果を用いて前段の演算結果 h(t,r) を求めることができる。
さらに求めた前段の演算結果 h(t,r) を用いてＦＦＴ処理を行うことにより、ＦＦＴ演算部１２において最終的なＦＦＴ処理を行うことができる。
このように、本発明の実施の形態のＦＦＴ処理装置は、バッファ１３のメモリ容量、たとえば、マルチプレクサの数およびフリップフロップの数が最小限でよい。したがって、本発明のＦＦＴ処理装置は回路規模が大きくならず、むしろ、従来のＦＦＴ処理装置より回路規模が縮小でき、価格を低減させることができ、電力消費を低減する。
本発明の実施の形態のＦＦＴ処理装置においては、処理速度の低下もない。
【００４８】
第１実施の形態の変形態様
上述した実施の形態においては、６５５３６点ＦＦＴ処理を、前段の演算結果 h(t,r) の演算と、１６個の４０９６点ＦＦＴに分けた場合についての実施の形態を示したが、上記数値は例示であり、もちろん、本発明は、これ以外の点数のＦＦＴ処理にも適用できる。
【００４９】
バッファ１３の好適なメモリ素子として、フリップフロップを用いた例を述べたが、フリップフロップに代えてレジスタを用いることもできる。
上述したメモリ１１からバッファ１３への最初のデータのライトは、上述したように行単位ではなく、列単位で行っても良い。その場合、最初のリードは行単位となり、次のライトも行単位となる。したがって、本発明においては、行方向、列方向をそれぞれ、第１方向、第２方向、または、逆に、行方向、列方向をそれぞれ、第２方向、第１方向という。
【００５０】
第２実施の形態
第１実施の形態は演算処理として、ＦＦＴを行うＦＦＴ処理装置について述べたが、本発明はＦＦＴ処理装置に限らず、第１メモリの外、バッファとして第２メモリを有し、上述したと同様のデータ処理が必要な他の演算処理用制御装置にも適用できる。
すなわち、メモリ１１、バッファ１３、制御部１４、ＦＦＴ演算部１２に代えて他の処理手段を有する演算処理用制御装置における、メモリ１１、バッファ１３のデータ処理を制御部１４が行う場合についても適用できる。
【図面の簡単な説明】
【００５１】
【図１】図１は前段の演算結果 h(t,r) を算出する信号流れ図である。
【図２】図２は算出した演算結果 h(t,r) をＦＦＴ処理してＦＦＴ処理結果Ｆをうるための４０９６点ＦＦＴのデータの流れを示すグラフである。
【図３】図３はメモリ内のデータの配置例を示す図である。
【図４】図４はバッファを用いたＦＦＴ処理装置の構成例を示す図である。
【図５】図５（Ａ）〜（Ｄ）は図４のバッファへデータをライトする動作の制御方法を示す図である。
【図６】図６（Ａ）〜（Ｄ）は図４のバッファからデータをリードする動作の制御方法を示す図である。
【図７】図７（Ａ）〜（Ｄ）は、本発明の実施の形態のＦＦＴ処理装置におけるメモリから読みだしたデータをバッファに書き込むライト動作を示す図である。
【図８】図８（Ａ）〜（Ｄ）は、本発明の実施の形態のＦＦＴ処理装置におけるバッファからデータを読み出すリード動作とバッファにデータを書き込むライト動作を示す図であり、特に、列（Ｙ）方向にリード動作とライト動作を行う場合を示す図である。
【図９】図９（Ａ）〜（Ｄ）は、本発明の実施の形態のＦＦＴ処理装置におけるバッファからデータを読み出すリード動作とバッファにデータを書き込むライト動作を示す図であり、特に、行（Ｘ）方向にリード動作とライト動作を行う場合を示す図である。
【図１０】図１０は本発明のＦＦＴ処理装置におけるバッファの回路例を示す図である。
【符号の説明】
【００５２】
１１…メモリ、１２…ＦＦＴ演算部、１３…バッファ、１４…制御部
m00〜m0F, m10〜m1F, …, mF0〜mFF…転置用マルチプレクサ
m101, m102, m103…データ選択用マルチプレクサ
f00〜f0F, f10〜f1F, …,fF0〜fFF…データ保持用フリップフロップ
【図１】
2006155487.tif 000006
【図２】
2006155487.tif 000007
【図３】
2006155487.tif 000008
【図４】
2006155487.tif 000009
【図５】
2006155487.tif 000010
【図６】
2006155487.tif 000011
【図７】
2006155487.tif 000012
【図８】
2006155487.tif 000013
【図９】
2006155487.tif 000014
【図１０】
2006155487.tif 000015