JP2000040080A

JP2000040080A - 高速フーリエ変換回路

Info

Publication number: JP2000040080A
Application number: JP10205975A
Authority: JP
Inventors: Hideo Mizutani; 秀夫水谷; Kenichi Tsuchida; 健一土田; Shigeki Moriyama; 繁樹森山; Toru Kuroda; 徹黒田
Original assignee: Nippon Hoso Kyokai NHK; Oki Electric Industry Co Ltd; Japan Broadcasting Corp
Current assignee: Oki Electric Industry Co Ltd; Japan Broadcasting Corp
Priority date: 1998-07-22
Filing date: 1998-07-22
Publication date: 2000-02-08

Abstract

(57)【要約】【課題】通常のサンプル数の１／２または１／４でＦ
ＦＴ処理を行う場合に、作業用メモリをデータ入力と演
算処置等で並行使用し、処理効率を向上させる。【解決手段】複素数入力データＩＩ，ＩＱがマルチプ
レクサ４１を介して作業用メモリ４２，４３のセグメン
ト４２ａ，４３ａに入力されている間、セグメント４２
ｂ，４３ｂ内のデータはマルチプレクサ４４，４１を介
してデータパス７０Ａ，７０Ｂに接続されてＦＦＴ演算
処理が施され、演算結果はレジスタ９１，９２を介して
出力データＯＩ，ＯＱとして出力される。セグメント４
２ｂ，４３ｂ内のデータの演算処理が終了すると、マル
チプレクサ４１，４４が切り替えられ、セグメント４２
ａ，４３ａに入力さた入力データＩＩ，ＩＱの演算処理
が行われる。一方、セグメント４２ｂ，４３ｂには、次
の周期の入力データＩＩ，ＩＱが入力される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、周期的に与えられ
る離散的な時系列信号の周期性を利用して周波数成分に
変換する高速フーリエ変換（以下、ＦＦＴという）回
路、特に入力信号のサンプル点数が可変のＦＦＴ回路、
または逆に離散的な周波数成分を時系列信号に変換する
逆変換回路に関するものである。

【０００２】

【従来の技術】図２は、従来のＦＦＴ回路の一例を示す
構成図である。このＦＦＴ回路は、時系列的に与えられ
る複素数入力データＩＩ，ＩＱを、それぞれ一旦保持す
るためのレジスタ１１，１２を有している。レジスタ１
１，１２の出力側は、ぞれぞれセレクタ１３，１４の第
１の入力側に接続されている。セレクタ１３，１４の出
力側は、作業用メモリ１５のデータ入力端子に接続され
ている。作業用メモリ１５は、入力データＩＩ，ＩＱ
や、演算途中の中間結果を一時的に格納するためのもの
である。作業用メモリ１５のデータ出力端子は、ＦＦＴ
演算処理を行うデータパス１６，１７の入力側に接続さ
れている。データパス１６，１７には、またＦＦＴ演算
処理で用いる係数が予め記憶されている係数用メモリ１
８の出力側が接続されている。

【０００３】データパス１６，１７は、作業用メモリ１
５及び係数用メモリ１８から与えられたデータを、ＦＦ
Ｔアルゴリズムに従って計算するものである。データパ
ス１６，１７の出力側は、それぞれセレクタ１３，１４
の第２の入力側に接続されるとともに、レジスタ１９，
２０の入力側に接続されている。レジスタ１９，２０
は、データパス１６，１７による繰り返し演算によって
最終的に得られた複素数出力データＯＩ，ＯＱを出力す
るために保持するものである。

【０００４】更に、ＦＦＴ回路は、動作の基準となるク
ロック信号を生成するクロック生成部２１と、このクロ
ック信号に基づいて各部の動作シーケンスを制御するシ
ーケンス制御部２２と、アドレス生成部２３とを備えて
いる。アドレス生成部２３は、動作シーケンスに応じて
作業用メモリ１５に対する読み書きアドレスと、係数用
メモリ１８に対する読み出しアドレスとを生成するもの
である。このようなＦＦＴ回路において、例えばＦＦＴ
処理の１周期のサンプル点数を１０２４として処理する
場合、まず、セレクタ１３，１４の第１の入力側が選択
される。そして、レジスタ１１，１２を介して離散的に
入力された複素数入力データＩＩ，ＩＱは、サンプル点
数（即ち、１０２４点）だけ作業用メモリ１５に順次格
納される。１０２４点の複素数入力データＩＩ，ＩＱが
作業用メモリ１５に格納された後、セレクタ１３，１４
は第２の入力側に切り替えられる。

【０００５】次に、作業用メモリ１５及び係数用メモリ
１８から、ＦＦＴアルゴリズムに基づいて所定のアドレ
スに格納されたデータが読み出され、データパス１６，
１７の入力側に与えられる。これにより、データパス１
６，１７の出力側には、読み出されたデータに応じた中
間結果が出力される。データパス１６，１７から出力さ
れた中間結果は、セレクタ１３，１４を介して再び作業
用メモリ１５の同一アドレスに書き込まれる。作業用メ
モリ１５及び係数用メモリ１８に対するアドレスは順次
シフトされ、これらの作業用メモリ１５及び係数用メモ
リ１８のデータがデータパス１６，１７によって演算さ
れてＦＦＴ処理が行われる。データパス１６，１７によ
るＦＦＴ処理の中間結果は、逐次更新されて作業用メモ
リ１５に書き込まれる。そして、最終的な演算結果が得
られた時点で、データパス１６，１７の出力データが、
レジスタ１９，２０に格納され、複素数出力データＯ
Ｉ，ＯＱとして出力される。

【０００６】

【発明が解決しようとする課題】しかしながら、従来の
ＦＦＴ回路では、次のような課題があった。例えば、Ｆ
ＦＴ処理の１周期のサンプル点数を１０２４の１／２の
５１２として処理する場合、作業用メモリ１５を半分し
か使用せず、残りの半分は未使用の状態となり、作業用
メモリ１５の有効利用が図られていない。このため、複
素数入力データＩＩ，ＩＱの格納領域と、中間結果の格
納領域とが同一の領域を交互に使用することとなり、Ｆ
ＦＴ処理を複数周期にわたって連続して行う場合に、デ
ータ入力と演算処理等とを並行して行うことができず、
処理効率の向上が困難であるという課題があった。本発
明は、前記従来技術が持っていた課題を解決し、サンプ
ル点数を１／２等に減少させた時に、データ入力と演算
処理等との並行処理を行うことにより、処理効率の向上
が可能なＦＦＴ回路を提供するものである。

【０００７】

【課題を解決するための手段】前記課題を解決するため
に、本発明の内の第１の発明は、一定周期でサンプリン
グされた離散的な入力データを入力する入力手段と、前
記入力手段から逐次入力されたＮ（但し、Ｎは２の冪乗
の値）サンプル分の前記入力データを処理するための記
憶容量を有する作業用記憶手段と、前記入力手段から入
力された入力データの周波数成分を算出するための捻り
係数を予め記憶した係数用記憶手段と、前記捻り係数及
び前記作業用記憶手段に格納された前記入力データに基
づいて中間結果を算出して該作業用記憶手段に再格納す
る演算処理を、所定の手順に従って繰り返えすことによ
り、該入力データの周波数成分を算出する周波数分析手
段とを備えたＦＦＴ回路において、作業用記憶手段を、
それぞれＮ／２サンプル分の前記入力データを処理する
ための記憶領域を有する２個のセグメントで構成してい
る。

【０００８】更に、前記２個のセグメントを、それぞれ
前記入力手段から前記入力データを格納する入力処理、
及び前記入力処理によってそのセグメントに格納された
前記入力データに基づいて前記周波数分析手段によって
周波数成分を算出して出力する算出処理に、順次並行し
て使用するための入力制御部及び出力制御部を設けてい
る。第１の発明によれば、以上のようにＦＦＴ回路を構
成したので、次のような作用が行われる。入力手段から
作業用記憶手段の一方のセグメントにＮ／２サンプル分
の入力データが入力されると、このセグメントに入力さ
れた入力データは、係数用記憶手段に記憶された捻り係
数とともに周波数分析手段に与えられて周波数成分の算
出処理が行われる。このセグメントの算出処理が行われ
ている間には、並行して他のセグメントに対するＮ／２
サンプル分の入力データの入力処理が行われる。

【０００９】第２の発明は、第１の発明と同様のＦＦＴ
回路において、作業用記憶手段を、それぞれＮ／４サン
プル分の前記入力データを処理するための記憶領域を有
する４個のセグメントで構成している。更に、前記４個
のセグメントを、それぞれ前記入力手段から前記入力デ
ータを格納する入力処理、前記入力処理によってそのセ
グメントに格納された前記入力データに基づいて前記周
波数分析手段によって周波数成分を計算する計算処理、
及び前記計算処理による計算結果を出力する出力処理
に、順次並行して使用するための入力制御部及び出力制
御部を設けている。第２の発明によれば、次のような作
用が行われる。入力手段から作業用記憶手段の４個のセ
グメントに、順次Ｎ／４サンプル分の入力データが入力
される。入力処理の完了したセグメントの入力データ
は、係数用記憶手段に記憶された捻り係数とともに周波
数分析手段に与えられて周波数成分の計算処理が行われ
る。更に、計算処理の完了したセグメントに格納された
計算結果は、順次読み出されて出力される。４個のセグ
メントにおけるこれらの入力処理、計算処理、及び出力
処理は、それぞれ入力制御部及び出力制御部の制御に基
づいて、順次並行して行われる。

【００１０】第３の発明は、第１及び第２の発明のＦＦ
Ｔ回路において、前記周波数分析手段における演算処理
毎に、その演算処理で使用されるデータの指数を共通に
して該周波数分析手段に与えるブロック浮動小数点処理
手段を設けている。第３の発明によれば、次のような作
用が行われる。入力手段から入力された各入力データ
は、ブロック浮動小数点処理手段による演算処理におい
て、その演算処理で使用されるデータの指数が共通にさ
れて周波数分析手段に与えられる。

【００１１】

【発明の実施の形態】第１の実施形態図１は、本発明の第１の実施形態を示すＦＦＴ回路の構
成図である。このＦＦＴ回路は、実数部及び虚数部で構
成される時系列的な複素数入力データＩＩ，ＩＱをそれ
ぞれ一旦保持するための入力手段（例えば、レジスタ）
３１，３２と、演算の中間結果等を格納するための作業
用記憶手段（例えば、データ記憶部）４０を有してい
る。データ記憶部４０は、入力側の入力制御部（例え
ば、マルチプレクサ）４１、２つの作業用メモリ４２，
４３、及び出力側の出力制御部（例えば、マルチプレク
サ）４４で構成されている。レジスタ３１，３２の出力
側は、マルチプレクサ４１の入力側に接続されており、
このマルチプレクサ４１の出力側には、作業用メモリ４
２，４３のデータ入力端子が接続されている。マルチプ
レクサ４１は、レジスタ３１，３２から与えられる入力
データや演算の中間結果を、所定の作業用メモリ４２，
４３に書き込むために切り替えて接続する機能を有する
ものである。また、作業用メモリ４２，４３は１周期の
サンプル点数Ｎ（例えば、Ｎ＝１０２４＝２¹⁰）に対応
する記憶領域を有しており、それぞれ入力データＩＩ，
ＩＱや、演算途中の複素数データの実数部及び虚数部を
一時的に格納するためのものである。作業用メモリ４
２，４３のデータ出力端子は、マルチプレクサ４４の入
力側に接続されている。

【００１２】マルチプレクサ４４は、作業用メモリ４
２，４３から読み出されたデータを、ＦＦＴ演算処理ま
たは最終結果出力のために切り替えて接続する機能を有
するものである。このＦＦＴ回路は、係数用記憶手段
（例えば、係数用メモリ）５０、及びブロック浮動小数
点処理手段（例えば、ブロック浮動小数点処理部）６０
を有している。係数用メモリ５０は、ＦＦＴ演算処理で
用いる正弦関数及び余弦関数に基づく捻り係数Ｗ１ｉ，
Ｗ２ｉ，Ｗ３ｉ，Ｗ４ｉ（但し、ｉ＝１〜２５６）を、
予め記憶した読み出し専用のメモリである。ブロック浮
動小数点処理部６０は、各入力データに対して共通な指
数を検出処理するものである。即ち、データが入力され
る毎に、それらの数値の大小を比較し、既に作業用メモ
リ４２，４３に格納されている値よりも大きな数値が入
力されたときには、新しい方の数値に書き換えるように
なっている。また、作業用メモリ４２，４３に格納され
ている値よりも小さな数値が入力されたときには、その
ままの値を残すことにより、最終的に最大値を求めるよ
うになっている。そして、その最大値の指数をそのグル
ープに共通な指数として、計算処理時のシフトデータＳ
ＥＴとして用いるものである。

【００１３】マルチプレクサ４４、係数用メモリ５０、
及び浮動小数点処理部６０の出力側は、周波数分析手段
（例えば、データパス）７０Ａ，７０Ｂの入力側に接続
されている。データパス７０Ａ，７０Ｂは、データ記憶
部４０及び係数用メモリ５０から与えられた捻り係数Ｗ
１ｉ〜Ｗ４ｉと、浮動小数点処理部６０から与えられた
シフトデータＳＦＴを用い、ＦＦＴアルゴリズムに従っ
て繰り返し演算処理を行うことによって入力データの周
波数成分を算出するものである。データパス７０Ａ，７
０Ｂの出力側は、データ記憶部４０のマルチプレクサ４
１の入力側に接続されている。マルチプレクサ４４の出
力側には、更に、データパス７０Ａ，７０Ｂによる繰り
返し演算によって最終的に得られた複素数出力データＯ
Ｉ，ＯＱを出力するために保持するレジスタ９１，９２
が接続されている。また、このＦＦＴ回路は、動作の基
準となるクロック信号ＣＬＫを生成するクロック生成部
９３と、このクロック信号ＣＬＫに基づいて各部の動作
シーケンスを制御するシーケンス制御部９４と、動作シ
ーケンスに応じてデータ記憶部４０及びブロック浮動小
数点処理部６０に対する読み書きアドレス、並びに係数
用メモリ５０に対する読み出しアドレスを生成するアド
レス生成部９５とを備えている。

【００１４】図３は、図１中のデータ記憶部４０の構成
図である。このデータ記憶部４０のマルチプレクサ４１
は、４個のセレクタ４１ａ，４１ｂ，４１ｃ，４１ｄで
構成されている。作業用メモリ４２，４３は、それぞれ
２つに分けられたサンプル点数Ｎ／２（＝５１２）に対
応するセグメント４２ａ，４２ｂ、及びセグメント４３
ａ，４３ｂの記憶領域を有している。また、マルチプレ
クサ４４は、２つのセレクタ４４ａ，４４ｂで構成され
ている。セレクタ４１ａの第１の入力側と、セレクタ４
１ｂの第３の入力側には、レジスタ３１からのデータＩ
Ｉｋ（但し、ｋ＝１〜５１２）が与えられるようになっ
ている。同様に、セレクタ４１ｃの第１の入力側とセレ
クタ４１ｄの第２の入力側には、レジスタ３２からのデ
ータＩＱｋが与えられるようになっている。

【００１５】また、セレクタ４１ａの第３の入力側、セ
レクタ４１ｂの第２の入力側、セレクタ４１ｃの第３の
入力側、及びセレクタ４１ｄの第３の入力側には、デー
タパス７０Ａからのデータａｉ，ｃｉ（但し、ｉ＝１〜
１２８）が与えられる。セレクタ４１ａの第２の入力
側、セレクタ４１ｂの第１の入力側、セレクタ４１ｃの
第２の入力側、及びセレクタ４１ｄの第１の入力側に
は、データパス７０Ｂからのデータｂｉ，ｄｉが与えら
れるようになっている。そして、セレクタ４１ａ，４１
ｂの出力側は、作業用メモリ４２のセグメント４２ａ，
４２ｂのデータ入力端子にそれぞれ接続されている。作
業用メモリ４２のセグメント４２ａ，４２ｂのデータ出
力端子は、セレクタ４４ａの第１及び第２の入力側にそ
れぞれ接続され、このセレクタ４４ａの出力側から複素
数データＡｉ〜Ｄｉの実数部が出力されるようになって
いる。一方、セレクタ４１ｃ，４１ｄの出力側は、作業
用メモリ４３のセグメント４３ａ，４３ｂのデータ入力
端子にそれぞれ接続されている。作業用メモリ４３のセ
グメント４３ａ，４３ｂのデータ出力端子は、セレクタ
４４ｂの第１及び第２の入力側にそれぞれ接続され、こ
のセレクタ４４ｂの出力側から複素数データＡｉ〜Ｄｉ
の虚数部が出力されるようになっている。

【００１６】図４は、図１中のデータパス７０Ａ，７０
Ｂの構成図である。データパス７０Ａは、データ記憶部
４０から出力されたデータＡｉ〜Ｄｉを演算のために一
旦保持するレジスタ７１を有している。レジスタ７１の
出力側には、シフタ７２が接続されている。シフタ７２
は、ブロック浮動小数点処理部６０から与えられるシフ
トデータＳＦＴに基づいて、レジスタ７１に保持された
データＡｉ〜Ｄｉを指定された桁数だけシフトするもの
である。シフタ７２の出力側は、加算器７３Ａとセレク
タ７４の第１の入力側に接続されている。加算器７３Ａ
の出力側は、セレクタ７４の第２の入力側に接続され、
このセレクタ７４の出力側がレジスタ７５の入力側に接
続されている。レジスタ７５の出力側は加減算器７６の
入力側に接続され、この加減算器７６の出力側がレジス
タ７７，７８の入力側に接続されている。

【００１７】データパス７０Ａは、係数用メモリ５０か
ら与えられる捻り係数Ｗ１ｉ，Ｗ３ｉを演算のために、
それぞれ一旦保持するためのレジスタ７９，８０を有し
ている。そして、レジスタ７７，７９の出力側は乗算器
８１の入力側に接続され、この乗算器８１の出力側にレ
ジスタ８２が接続されている。また、レジスタ７８，８
０の出力側は乗算器８３の入力側に接続され、この乗算
器８３の出力側にレジスタ８４が接続されている。レジ
スタ８２，８４の出力側は加減算器８５に接続され、こ
の加減算器８５の出力側に、レジスタ８６が接続されて
いる。そして、レジスタ８６に一旦格納された演算結果
が、データａｉ，ｃｉとして出力されるようになってい
る。データパス７０Ｂの構成は、データパス７０Ａとほ
ぼ同様である。但し、データパス７０Ａにおける加算器
７３Ａに代えて、減算器７３Ｂが設けられている。その
他の構成は、データパス７０Ａと同様であり、レジスタ
８６に一旦格納された演算結果が、データｂｉ，ｄｉと
して出力されるようになっている。

【００１８】このようなデータパス７０Ａ，７０Ｂは、
セレクタ７４の切り替えにより、基数４及び基数２につ
いてのＦＦＴ演算処理が可能な機能を有している。即
ち、基数４のＦＦＴ演算処理を行う場合には、データパ
ス７０Ａ，７０Ｂのレジスタ７１に、データ記憶部４０
から読み出された複素数データＡｉ〜Ｄｉを格納する。
そして、データパス７０Ａのセレクタ７４で加算器７３
Ａの出力側を、データパス７０Ｂのセレクタ７４で減算
器７３Ｂの出力側をそれぞれ選択する。更に、データパ
ス７０Ａのレジスタ７９，８０には、係数用メモリ５０
から読み出された捻り係数Ｗ１ｉ，Ｗ３ｉをそれぞれ格
納する。一方、データパス７０Ｂのレジスタ７９，８０
には、係数用メモリ５０から読み出された捻り係数Ｗ２
ｉ，Ｗ４ｉをそれぞれ格納する。

【００１９】これにより、データパス７０Ａ，７０Ｂの
出力側には、次の式（１）〜（４）に従って算出された
出力信号ａｉ，ｃｉ、及び出力信号ｂｉ，ｄｉが、それ
ぞれ出力されるようになっている。ａｉ＝｛（Ａｉ＋Ｃｉ）＋（Ｂｉ＋Ｄｉ）｝×Ｗ１ｉ・・・（１）ｃｉ＝｛（Ａｉ＋Ｃｉ）−（Ｂｉ＋Ｄｉ）｝×Ｗ３ｉ・・・（２）ｂｉ＝｛（Ａｉ−Ｃｉ）−ｊ（Ｂｉ−Ｄｉ）｝×Ｗ２ｉ・・・（３）ｄｉ＝｛（Ａｉ−Ｃｉ）＋ｊ（Ｂｉ−Ｄｉ）｝×Ｗ４ｉ・・・（４）一方、基数２のＦＦＴ演算処理を行う場合には、データ
パス７０Ａ，７０Ｂのレジスタ７１に、データ記憶部４
０から読み出された複素数データＡｉ〜Ｄｉを格納する
とともに、データパス７０Ａのセレクタ７４で加算器７
３Ａの入力側を、データパス７０Ｂのセレクタ７４で減
算器７３Ｂの入力側を選択する。そして、データパス７
０Ａのレジスタ７９，８０には、係数用メモリ５０から
読み出された捻り係数Ｗ１ｉ，Ｗ３ｉは、位相０゜に対
応する捻り係数Ｗ０（＝１＋ｊ０）を交互に格納する。
一方、データパス７０Ｂのレジスタ７９，８０には、係
数用メモリ５０から読み出された捻り係数Ｗ２，Ｗ４
は、同様に捻り係数Ｗ０を交互に格納する。

【００２０】これにより、データパス７０Ａの出力側に
は、前記式（１），（２）、または次の式（５），
（６）に従って算出された出力信号ａｉ，ｂｉが交互に
出力されるようになっている。ａｉ＝Ａｉ＋Ｂｉ・・・（５）ｂｉ＝Ａｉ−Ｂｉ・・・（６）また、データパス７０Ｂの出力側には、前記式（３），
（４）、または次の式（７），（８）に従って算出され
た出力信号ｃｉ，ｄｉが交互に出力されるようになって
いる。ｃｉ＝Ｃｉ＋Ｄｉ・・・（７）ｄｉ＝Ｃｉ−Ｄｉ・・・（８）

【００２１】図５は、図１のＦＦＴ回路の動作シーケン
スを示す図である。次に、図３〜図５を参照しつつ、図
１のＦＦＴ回路におけるサンプル点数５１２での動作を
説明する。先ず、図５の周期Ｔ１において、図３のデー
タ記憶部４０のマルチプレクサ４１ａ〜４１ｄは第１の
入力側に切り替えられる。これにより、セグメント４２
ａには、外部からの第１周期の複素数入力データの実数
部ＩＩがレジスタ３１を介して書き込まれる。また、セ
グメント４３ａには、外部からの第１周期の複素数入力
データの虚数部ＩＱがレジスタ３２を介して書き込まれ
る。

【００２２】次に、周期Ｔ２において、マルチプレクサ
４１ａ〜４１ｄは第２、第３の入力側に切り替えられ、
また、マルチプレクサ４４ａ，４４ｂは第２の入力側に
切り替えられる。これにより、セグメント４２ｂ，４３
ｂには、外部からの第２周期の複素数入力データＩＩ，
ＩＱがレジスタ３１，３２を介して書き込まれる。一
方、セグメント４２ａ，４３ａに格納された第１周期の
入力データは、マルチプレクサ４４ａ，４４ｂを介して
出力される。そして、データパス７０Ａ，７０Ｂの演算
結果がマルチプレクサ４１ａ，４１ｃを介して、セグメ
ント４２ａ，４３ａに入力され、これらのセグメント４
２ａ，４３ａの内容は、演算途中データで順次置き換え
られる。演算がすべて終了し、演算途中データが最終結
果に置き換えられると、この最終結果は、クロック信号
ＣＬＫ３に同期して出力される。

【００２３】更に、周期Ｔ３において、マルチプレクサ
４１ａ〜４１ｄは、再び第１の入力側に切り替えられ、
マルチプレクサ４４ａ，４４ｂも第１の入力側に切り替
えられる。これにより、セグメント４２ａ，４３ａに
は、外部からの第３周期の複素数入力データＩＩ，ＩＱ
がレジスタ３１，３２を介して書き込まれる。一方、セ
グメント４２ｂ，４３ｂに格納された第２周期の入力デ
ータは、マルチプレクサ４４ａ，４４ｂを介して出力さ
れる。そして、データパス７０Ａ，７０Ｂの演算結果が
マルチプレクサ４１ｂ，４１ｄを介して、セグメント４
２ｂ，４３ｂに入力され、これらのセグメント４２ｂ，
４３ｂの内容は、演算途中データで順次置き換えられ
る。

【００２４】図５中の周期Ｔ３に詳細を例示したよう
に、各周期において、複素数入力データ（ＩＩ１，ＩＱ
１），（ＩＩ２，ＩＱ２），…，（ＩＩ５１２，ＩＱ５
１２）は、データ入力用のクロック信号ＣＬＫ１に同期
して順次入力される。そして、入力された実数部の入力
データＩＩ１，ＩＩ２，…，ＩＩ５１２は、データ記憶
部４０のセグメント４２ａに、データＡ１〜Ｄ１，Ａ２
〜Ｄ２，…，Ａ１２８〜Ｄ１２８の実数部データとして
順次記憶される。また、虚数部の入力データＩＱ１，Ｉ
Ｑ２，…，ＩＱ５１２は、データ記憶部４０のセグメン
ト４３ａに、データＡ１〜Ｄ１，Ａ２〜Ｄ２，…，Ａ１
２８〜Ｄ１２８の虚数部データとして順次記憶される。
一方、データ記憶部４０のセグメント４２ｂ，４３ｂに
一旦格納されたデータは、演算用のクロック信号ＣＬＫ
２に同期して読み出され、データパス７０Ａ，７０Ｂに
おいてＦＦＴ演算処理が行われ、その中間結果は演算途
中データとして、再びセグメント４２ｂ，４３ｂの同じ
記憶領域に再格納される。更に、再格納された中間結果
に所定の手順によるＦＦＴ演算処理が繰り返し施され、
その最終結果はセグメント４２ｂ，４３ｂの同じ記憶領
域に格納される。そして、最終結果は、出力用のクロッ
ク信号ＣＬＫ３に同期して実数成分の出力データＯＩ
１，ＯＩ２，…，ＯＩ５１２、及び虚数成分の出力デー
タＯＱ１，ＯＱ２，…，ＯＱ５１２として、それぞれレ
ジスタ９１，９２を介して出力される。

【００２５】以上のように、この第１の実施形態のＦＦ
Ｔ回路は、それぞれ２つのセグメント４２ａ，４２ｂ、
及びセグメント４３ａ，４３ｂに分割された作業用メモ
リ４２，４３と、一方のセグメントに外部からのデータ
を入力しているときには、他方のセグメントに格納され
たデータを読み出してＦＦＴ演算処理を行うように切り
替えるためのマルチプレクサ４１，４４を有している。
これにより、サンプル点数を１／２に減じてＦＦＴ処理
を行う場合に、作業用メモリ４２，４３の有効利用によ
り、データ入力と演算処理等との並行処理が可能にな
り、処理性能の向上が可能になる。

【００２６】第２の実施形態図６は、本発明の第２の実施形態を示すデータ記憶部４
０Ａの構成図である。このデータ記憶部４０Ａは、図１
中のデータ記憶部４０に代えて設けられるものであり、
入力側の入力制御部（例えば、マルチプレクサ）４５
ａ，４５ｂ、作業用メモリ４６，４７、及び出力側の出
力制御部（例えば、マルチプレクサ）４８ａ，４８ｂで
構成されている。マルチプレクサ４５ａは、３個の入力
側と、４個の出力側とを備え、図示しない制御信号に従
って、入力側と出力側との接続を行うものである。マル
チプレクサ４５ａの入力側に、レジスタ３１からの実数
部の入力データＩＩｋ（但し、ｋ＝１〜２５６）及びデ
ータパス７０Ａ，７０Ｂからのデータａｉ〜ｄｉ（但
し、ｉ＝１〜６４）が与えられるようになっている。作
業用メモリ４６は、それぞれサンプル点数２５６の入力
データＩＩｋに対応する記憶領域を有する４個のセグメ
ント４６ａ，４６ｂ，４６ｃ，４６ｄで構成されてい
る。そして、これらの各セグメント４６ａ〜４６ｄの入
力側が、マルチプレクサ４５ａの４個の出力側にそれぞ
れ接続されている。各セグメント４６ａ〜４６ｄの出力
側は、４入力２出力のマルチプレクサ４８ａの入力側に
それぞれ接続されている。マルチプレクサ４８ａは、図
示しない制御信号に従って、入力側と出力側との接続を
行うものである。

【００２７】同様に、マルチプレクサ４５ｂは、３個の
入力側と、４個の出力側とを備え、図示しない制御信号
に従って、入力側と出力側との接続を行うものである。
マルチプレクサ４５ｂの入力側に、レジスタ３２からの
虚数部の入力データＩＱｋ（但し、ｋ＝１〜２５６）及
びデータパス７０Ａ，７０Ｂからのデータａｉ〜ｄｉ
（但し、ｉ＝１〜６４）が与えられるようになってい
る。作業用メモリ４７は、それぞれサンプル点数２５６
の入力データＩＱｋに対応する記憶領域を有する４個の
セグメント４７ａ，４７ｂ，４７ｃ，４７ｄで構成され
ている。そして、これらの各セグメント４７ａ〜４７ｄ
の入力側が、マルチプレクサ４５ｂの４個の出力側にそ
れぞれ接続されている。各セグメント４７ａ〜４７ｄの
出力側は、４入力２出力のマルチプレクサ４８ｂの入力
側にそれぞれ接続されている。マルチプレクサ４８ｂ
は、図示しない制御信号に従って、入力側と出力側との
接続を行うものである。

【００２８】図７は、図６のデータ記憶部４０Ａの動作
シーケンスを示す図である。次に、図７を参照しつつ、
図６のデータ記憶部４０Ａにおけるサンプル点数２５６
での動作を説明する。先ず、図７の周期Ｔ１において、
図６中のマルチプレクサ４５ａ，４５ｂの第１の入力側
は、それぞれ第１の出力側に接続される。これにより、
セグメント４６ａ，４７ａには、第１周期の入力データ
ＩＩ，ＩＱがそれぞれ格納される。次に、周期Ｔ２にお
いて、各マルチプレクサ４５ａ，４５ｂの第１の入力側
は第２の出力側に接続され、第２の入力側は第１の出力
側に接続される。更に、マルチプレクサ４８ａ，４８ｂ
の第１の入力側は第１の出力側に接続される。これによ
り、セグメント４６ｂ，４７ｂに、第２周期の入力デー
タＩＩ，ＩＱがそれぞれ格納される。一方、セグメント
４６ａ，４７ａに格納された第１周期の入力データＩ
Ｉ，ＩＱは、それぞれデータパス７０Ａ，７０Ｂに与え
られ、ＦＦＴ演算処理が行われて最終的な演算結果に書
き替えられる。

【００２９】周期Ｔ３において、各マルチプレクサ４５
ａ，４５ｂの第１の入力側は第３の出力側に接続され、
第２及び第３の入力側は第２の出力側に接続される。更
に、マルチプレクサ４８ａ，４８ｂの第１の入力側は第
２の出力側に接続され、第２及び第３の入力側は第１の
出力側に接続される。これにより、セグメント４６ｃ，
４７ｃに，第３周期の入力データＩＩ，ＩＱがそれぞれ
格納される。一方、セグメント４６ｂ，４７ｂに格納さ
れた第２周期のデータＩＩ，ＩＱは、それぞれデータパ
ス７０Ａ，７０Ｂに与えられ、ＦＦＴ演算処理が行われ
て最終的な演算結果に書き替えられる。更に、セグメン
ト４６ａ，４７ａに格納された第１周期の入力データＩ
Ｉ，ＩＱに対応するＦＦＴ演算結果は、それぞれレジス
タ９１，９２を介して出力データＯＩ，ＯＱとして出力
される。

【００３０】例えば周期Ｔ４に例示したように、各周期
において、複素数入力データ（ＩＩ１，ＩＱ１），（Ｉ
Ｉ２，ＩＱ２），…，（ＩＩ２５６，ＩＱ２５６）は、
データ入力用のクロック信号ＣＬＫ１に同期して順次入
力される。そして、入力された実数部の入力データＩＩ
１，ＩＩ２，…，ＩＩ２５６は、データ記憶部４０のセ
グメント４６ｄ等に、データＡ１〜Ｄ１，Ａ２〜Ｄ２，
…，Ａ６４〜Ｄ６４の実数部として順次記憶される。ま
た、虚数部の入力データＩＱ１，ＩＱ２，…，ＩＱ２５
６は、データ記憶部４０のセグメント４７ｄ等に、デー
タＡ１〜Ｄ１，Ａ２〜Ｄ２，…，Ａ６４〜Ｄ６４の虚数
部として順次記憶される。一方、セグメント４６ｃ，４
７ｃ等に一旦格納されたデータは、演算用のクロック信
号ＣＬＫ２に同期して読み出され、データパス７０Ａ，
７０ＢにおいてＦＦＴ演算処理が行われ、その中間結果
は演算途中データとして、再びセグメント４６ｃ，４７
ｃ等の同じ記憶領域に再格納される。更に、再格納され
た中間結果に所定の手順によるＦＦＴ演算処理が繰り返
し施され、その最終結果はセグメント４６ｃ，４７ｃ等
の同じ記憶領域に格納される。

【００３１】また、セグメント４６ｂ，４７ｂ等に格納
された最終結果は、出力用のクロック信号ＣＬＫ３に同
期して実数部の出力データＯＩ１，ＯＩ２，…，ＯＩ２
５６、及び虚数部の出力データＯＱ１，ＯＱ２，…，Ｏ
Ｑ２５６として、それぞれレジスタ９１，９２を介して
出力される。以上のように、この第２の実施形態のデー
タ記憶部は、それぞれ４つのセグメント４６ａ〜４６
ｄ、及びセグメント４７ａ〜４７ｄに分割された作業用
メモリ４６，４７と、１つのセグメントに外部からの入
力データを入力しているときには、その前のセグメント
に格納されたデータを読み出してＦＦＴ演算処理を行
い、更にその前のセグメントに格納された演算結果を出
力するように切り替えるためのマルチプレクサ４５ａ，
４５ｂ，４８ａ，４８ｂを有している。これにより、サ
ンプル点数を１／４に減じてＦＦＴ処理を行う場合に、
作業用メモリ４６，４７の有効利用により、データ入
力、演算処理、及びデータ出力の並行処理が可能にな
り、処理性能の向上が可能になる。

【００３２】なお、本発明は、上記実施形態に限定され
ず、種々の変形が可能である。この変形例としては、例
えば、次の（ａ）〜（ｄ）のようなものがある。（ａ）データ記憶部４０，４０Ａは、最大サンプル点
数１０２４に対応する記憶領域を有しているが、最大サ
ンプル点数は１０２４に限定されず、必要な処理精度に
応じたサンプル点数に対応するものであれば良い。（ｂ）データパス７０Ａ，７０Ｂの構成は、図４の構
成に限定されず、ＦＦＴ演算処理を行うことができるも
のであれば、どのような構成でも適用可能である。（ｃ）図１のＦＦＴ回路は、ブロック浮動小数点処理
部６０を備えているが、演算処理精度よりも回路の簡素
化を重視する場合には、省略しても良い。（ｄ）図６のデータ記憶部４０Ａでは、４個のセグメ
ントを順次周期的に入力、演算、出力、無使用の順に割
り当てているが、３個のセグメントを周期的に入力、演
算、出力の順に割り当て、残りの１個のセグメントを無
使用またはその他の目的に使用するように割り当てるこ
ともできる。

【００３３】

【発明の効果】以上詳細に説明したように、第１の発明
によれば、作業用記憶手段をＮ／２サンプル分を処理す
るための２つのセグメントに分割するとともに、これら
のセグメントを、入力データの入力処理と、入力された
データから周波数成分を算出する算出処理に並行して使
用するための入力制御部及び出力制御部を設けている。
このため、通常の１／２のサンプル数でＦＦＴ演算を行
う場合に、作業用記憶手段の有効利用が可能になり、処
理効率を向上することができるという効果がある。

【００３４】第２の発明によれば、作業用記憶手段をＮ
／４サンプル分を処理するための４つのセグメントに分
割するとともに、これらのセグメントを、入力データの
入力処理と、入力されたデータから周波数成分を計算す
る計算処理と、計算結果を出力する出力処理とに並行し
て使用するための入力制御部及び出力制御部を設けてい
る。このため、通常の１／４のサンプル数でＦＦＴ演算
を行う場合に、作業用記憶手段の有効利用が可能にな
り、更に処理効率を向上することができるという効果が
ある。第３の発明によれば、第１及び第２の発明に、ブ
ロック浮動小数点処理手段を設けている。これにより、
入力データの有効桁数を最大にして演算処理を行うこと
が可能になり、第１及び第２の発明の効果に加えて、演
算精度の向上が可能になるという効果がある。

【図面の簡単な説明】

【図１】本発明の第１の実施形態を示すＦＦＴ回路の構
成図である。

【図２】従来のＦＦＴ回路の一例を示す構成図である。

【図３】図１中のデータ記憶部４０の構成図である。

【図４】図１中のデータパス７０Ａ，７０Ｂの構成図で
ある。

【図５】図１のＦＦＴ回路の動作シーケンスを示す図で
ある。

【図６】本発明の第２の実施形態を示すデータ記憶部４
０Ａの構成図である。

【図７】図６のデータ記憶部４０Ａの動作シーケンスを
示す図である。

【符号の説明】

４０，４０Ａデータ記憶部４１，４４，４５ａ，４５ｂ，４８ａ，４８ｂマル
チプレクサ４１ａ〜４１ｄ，４４ａ，４４ｂセレクタ４２，４３作業用メモリ４２ａ，４２ｂ，４３ａ，４３ｂ，４６ａ〜４６ｄ，４
７ａ〜４７ｄセグメント５０係数用メモリ６０ブロック浮動小数点処理部７０Ａ，７０Ｂデータパス９３クロック生成部９４シーケンス制御部９５アドレス生成部

───────────────────────────────────────────────────── フロントページの続き (72)発明者土田健一東京都世田谷区砧１丁目10番11号日本放送協会放送技術研究所内 (72)発明者森山繁樹東京都世田谷区砧１丁目10番11号日本放送協会放送技術研究所内 (72)発明者黒田徹東京都世田谷区砧１丁目10番11号日本放送協会放送技術研究所内Ｆターム(参考） 5B056 AA00 BB13 CC01 CC03 FF05 FF06 FF07 GG00

Claims

【特許請求の範囲】

【請求項１】一定周期でサンプリングされた離散的な
入力データを入力する入力手段と、前記入力手段から逐次入力されたＮ（但し、Ｎは２の冪
乗の値）サンプル分の前記入力データを処理するための
記憶容量を有する作業用記憶手段と、前記入力手段から入力された入力データの周波数成分を
算出するための捻り係数を予め記憶した係数用記憶手段
と、前記捻り係数及び前記作業用記憶手段に格納された前記
入力データに基づいて中間結果を算出して該作業用記憶
手段に再格納する演算処理を、所定の手順に従って繰り
返えすことにより、該入力データの周波数成分を算出す
る周波数分析手段とを備えた高速フーリエ変換回路にお
いて、前記作業用記憶手段を、それぞれＮ／２サンプル分の前
記入力データを処理するための記憶領域を有する２個の
セグメントで構成し、前記２個のセグメントを、それぞれ前記入力手段から前
記入力データを格納する入力処理、及び前記入力処理に
よってそのセグメントに格納された前記入力データに基
づいて前記周波数分析手段によって周波数成分を算出し
て出力する算出処理に、順次並行して使用するための入
力制御部及び出力制御部を設けたことを特徴とする高速
フーリエ変換回路。
【請求項２】一定周期でサンプリングされた離散的な
入力データを入力する入力手段と、前記入力手段から逐次入力されたＮ（但し、Ｎは２の冪
乗の値）サンプル分の前記入力データを処理するための
記憶容量を有する作業用記憶手段と、前記入力手段から入力された入力データの周波数成分を
算出するための捻り係数を予め記憶した係数用記憶手段
と、前記捻り係数及び前記作業用記憶手段に格納された前記
入力データに基づいて中間結果を算出して該作業用記憶
手段に再格納する演算処理を、所定の手順に従って繰り
返えすことにより、該入力データの周波数成分を算出す
る周波数分析手段とを備えた高速フーリエ変換回路にお
いて、前記作業用記憶手段を、それぞれＮ／４サンプル分の前
記入力データを処理するための記憶領域を有する４個の
セグメントで構成し、前記４個のセグメントを、それぞれ前記入力手段から前
記入力データを格納する入力処理、前記入力処理によっ
てそのセグメントに格納された前記入力データに基づい
て前記周波数分析手段によって周波数成分を計算する計
算処理、及び前記計算処理による計算結果を出力する出
力処理に、順次並行して使用するための入力制御部及び
出力制御部を設けたことを特徴とする高速フーリエ変換
回路。
【請求項３】前記周波数分析手段における演算処理毎
に、その演算処理で使用されるデータの指数を共通にし
て該周波数分析手段に与えるブロック浮動小数点処理手
段を設けたことを特徴とする請求項１または２記載の高
速フーリエ変換回路。