(57)【要約】【課題】一部の入力信号のみが固定ビット長を超過しているような場合にも、情報の欠落を抑える。【解決手段】高速フーリエ変換および逆高速フーリエ変換を行うための変換処理を固定ビット長の固定小数点演算で行う高速フーリエ変換装置（１０）において、変換処理を行う際の入力信号に、固定小数点演算を行うための固定ビット長を越えるビット長超過信号が含まれている場合には、入力信号に含まれているビット長超過信号に対して固定ビット長以内に収まるようにビット長の補正を行い、入力信号に含まれているビット長超過信号以外の信号に対してはビット長の補正を行わない部分データ補正部（１１、１２）を備える。【選択図】図１
2012128493.tif 000002
【特許請求の範囲】
【請求項１】
高速フーリエ変換および逆高速フーリエ変換を行うための変換処理を固定ビット長の固定小数点演算で行う高速フーリエ変換装置において、
前記変換処理を行う際の入力信号に、前記固定小数点演算を行うための前記固定ビット長を越えるビット長超過信号が含まれている場合には、前記入力信号に含まれている前記ビット長超過信号に対して前記固定ビット長以内に収まるようにビット長の補正を行い、前記入力信号に含まれている前記ビット長超過信号以外の信号に対してはビット長の補正を行わない部分データ補正部
を備えることを特徴とする高速フーリエ変換装置。
【請求項２】
請求項１に記載の高速フーリエ変換装置において、
前記入力信号に基づいて、バタフライ演算を所定回数繰り返し実施することで前記変換処理を実行するバタフライ演算部を備え、
前記部分データ補正部は、
前記入力信号、あるいは前記バタフライ演算部による各回の演算結果を補正前信号として入力し、前記補正前信号の中に前記ビット長超過信号が含まれているか否かを判断するビット長超過調査部と、
前記ビット長超過調査部により前記ビット長超過信号が検出された場合には、検出された前記ビット長超過信号に対して前記固定ビット長以内に収まるようにビット長を丸める補正を行い、補正後信号を出力する超過ビット長補正部と
を含んで構成され、
前記バタフライ演算部は、前記部分データ補正部から出力される前記補正後信号に基づいて各回のバタフライ演算を実行する
ことを特徴とする高速フーリエ変換装置。
【請求項３】
請求項１に記載の高速フーリエ変換装置において、
前記入力信号に基づいてバタフライ演算を所定回数繰り返し実施することで前記変換処理を実行するバタフライ演算部を含み、入力信号と出力信号でビット長が異なる固定小数点演算を行うことで前記変換処理を実行するＦＦＴ／ＩＦＦＴコアを備え、
前記部分データ補正部は、前記ＦＦＴ／ＩＦＦＴコアの前段に設けられた第１の部分データ補正部と、前記ＦＦＴ／ＩＦＦＴコアの後段に設けられた第２の部分データ補正部とを有し、
前記第１の部分データ補正部は、
前記入力信号を補正前信号として入力し、前記補正前信号の中に前記ビット長超過信号が含まれているか否かを判断する第１のビット長超過調査部と、
前記第１のビット長超過調査部により前記ビット長超過信号が検出された場合には、検出された前記ビット長超過信号に対して前記ＦＦＴ／ＩＦＦＴコアによる入力信号用の固定ビット長以内に収まるようにビット長を丸める補正を行い、補正後信号を出力する第１の超過ビット長補正部と
を含んで構成され、
前記ＦＦＴ／ＩＦＦＴコアは、前記第１の部分データ補正部から出力される前記補正後信号に基づいて前記変換処理を実行し、
前記第２の部分データ補正部は、
前記ＦＦＴ／ＩＦＦＴコアによる処理結果である前記出力信号の中に所定のビット長を超過する信号が含まれているか否かを判断する第２のビット長超過調査部と、
前記第２のビット長超過調査部により前記所定のビット長を超過する信号が検出された場合には、検出された前記所定のビット長を超過する信号に対して前記所定ビット長以内に収まるようにビット長を丸める補正を行い、補正後信号を出力する第２の超過ビット長補正部と
を含んで構成される
ことを特徴とする高速フーリエ変換装置。
【請求項４】
請求項１に記載の高速フーリエ変換装置において、
前記入力信号に基づいてバタフライ演算を所定回数繰り返し実施することで前記変換処理を実行するとともに、前記変換処理による桁あふれの有無を桁あふれ情報として通知するバタフライ演算部を備え、
前記部分データ補正部は、前記入力信号に前記固定小数点演算を行うための前記固定ビット長を越えるビット長超過信号が含まれているか否かを監視する代わりに、バタフライ演算結果の桁あふれを監視するものであり、
前記バタフライ演算部から前記桁あふれ情報を入力し、桁あふれが発生した場合には、桁あふれ発生信号を出力する桁あふれ管理部と、
前記バタフライ演算部による各回の演算結果を補正前信号として入力し、前記桁あふれ管理部により前記桁あふれ発生信号が出力された場合には、桁あふれを考慮して前記固定ビット長以内に収まるようにビット長を丸める補正を行い、補正後信号を出力し、前記桁あふれ管理部により前記桁あふれ発生信号が出力されなかった場合には、前記補正前信号をそのまま補正後信号として出力する桁あふれ補正部と
を含んで構成され、
前記バタフライ演算部は、前記桁あふれ補正部から出力される前記補正後信号に基づいて２回目以降のバタフライ演算を実施する
ことを特徴とする高速フーリエ変換装置。
【請求項５】
請求項１ないし４のいずれか１項に記載の高速フーリエ変換装置において、
前記部分データ補正部は、前記入力信号が複素数の場合には、複素数の実部・虚部の絶対値に対して前記固定ビット長以内に収まるようにビット長の補正を行う
ことを特徴とする高速フーリエ変換装置。
【請求項６】
請求項１ないし５のいずれか１項に記載の高速フーリエ変換装置において、
前記固定ビット長を越える前記ビット長超過信号の数が所定数ｎ（ただし、ｎは２以上の整数）以上の場合には、前記入力信号のすべてについてビット長を丸める補正を行う
ことを特徴とする高速フーリエ変換装置。
【請求項７】
請求項１ないし６のいずれか１項に記載の高速フーリエ変換装置において、
前記部分データ補正部は、バタフライ演算の繰り返し回数に応じて、あらかじめ決められた回数においては、前記入力信号のすべてについてビット長を丸める補正を行うように補正方法の切り替えを行う
ことを特徴とする高速フーリエ変換装置。
【請求項８】
高速フーリエ変換および逆高速フーリエ変換を行うための変換処理を固定ビット長の固定小数点演算で行う高速フーリエ変換装置に用いられるビット長補正方法であって、
前記変換処理を行う際の入力信号に、前記固定小数点演算を行うための前記固定ビット長を越えるビット長超過信号が含まれている場合には、前記入力信号に含まれている前記ビット長超過信号に対して前記固定ビット長以内に収まるようにビット長の補正を行い、前記入力信号に含まれている前記ビット長超過信号以外の信号に対してはビット長の補正を行わない部分データ補正ステップを備えることを特徴とする高速フーリエ変換装置に用いられるビット長補正方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、バタフライ演算を固定小数点演算で実施し、ＦＦＴ（高速フーリエ変換）やＩＦＦＴ（逆高速フーリエ変換）を繰り返し実行し続ける高速フーリエ変換装置および高速フーリエ変換装置に用いられるビット長補正方法に関する。
【背景技術】
【０００２】
固定小数点は、浮動小数点に比べ、演算回路が簡単であり、回路規模を小さくできる反面、扱える数のダイナミックレンジが狭いという問題を抱えている。
【０００３】
このような問題に対し、ＦＦＴやＩＦＦＴを施す際に、ビット長の短い固定小数点形式で処理する従来の高速フーリエ変換装置がある（例えば、特許文献１参照）。この特許文献１では、最大値を検出し、最大値に合わせてビットシフトを行い、最後に、途中で行ったビットシフトと逆方向のビットシフトを実施している。これにより、演算精度の劣化を抑えるものである。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−２８８１５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術には、以下のような課題がある。
従来の高速フーリエ変換装置は、ごく一部の点で値が大きい場合にも、それに合わせてビットシフトが行われる。このため、下位ビットでの桁落ちが多く発生し、演算精度が劣化するという問題がある。
【０００６】
本発明は、前記のような課題を解決するためになされたものであり、一部の入力信号のみが固定ビット長を超過しているような場合にも、情報の欠落を抑えることのできる高速フーリエ変換装置および高速フーリエ変換装置に用いられるビット長補正方法を得ることを目的とする。
【課題を解決するための手段】
【０００７】
本発明における高速フーリエ変換装置は、高速フーリエ変換および逆高速フーリエ変換を行うための変換処理を固定ビット長の固定小数点演算で行う高速フーリエ変換装置において、変換処理を行う際の入力信号に、固定小数点演算を行うための固定ビット長を越えるビット長超過信号が含まれている場合には、入力信号に含まれているビット長超過信号に対して固定ビット長以内に収まるようにビット長の補正を行い、入力信号に含まれているビット長超過信号以外の信号に対してはビット長の補正を行わない部分データ補正部を備えるものである。
【０００８】
また、本発明における高速フーリエ変換装置に用いられるビット長補正方法は、高速フーリエ変換および逆高速フーリエ変換を行うための変換処理を固定ビット長の固定小数点演算で行う高速フーリエ変換装置に用いられるビット長補正方法であって、変換処理を行う際の入力信号に、固定小数点演算を行うための固定ビット長を越えるビット長超過信号が含まれている場合には、入力信号に含まれているビット長超過信号に対して固定ビット長以内に収まるようにビット長の補正を行い、入力信号に含まれているビット長超過信号以外の信号に対してはビット長の補正を行わない部分データ補正ステップを備えるものである。
【発明の効果】
【０００９】
本発明に係る高速フーリエ変換装置および高速フーリエ変換装置に用いられるビット長補正方法によれば、固定小数点演算を行うための固定ビット長を越えるビット長超過信号が入力信号に含まれている場合には、ビット長超過信号に対して固定ビット長以内に収まるようにビット長の補正を行い、他の入力信号に対してはビット長の補正を行わないことにより、一部の入力信号のみが固定ビット長を超過しているような場合にも、情報の欠落を抑えることのできる高速フーリエ変換装置および高速フーリエ変換装置に用いられるビット長補正方法を得ることができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態１に係る高速フーリエ変換装置を示す構成図である。
【図２】従来の高速フーリエ変換装置による補正前後のグラフである。
【図３】本発明の実施の形態１に係る高速フーリエ変換装置の補正内容を示したグラフである。
【図４】本発明の実施の形態３に係る高速フーリエ変換装置を示す構成図である。
【図５】本発明の実施の形態４に係る高速フーリエ変換装置を示す構成図である。
【図６】本発明の実施の形態５に係る高速フーリエ変換装置を示す構成図である。
【発明を実施するための形態】
【００１１】
以下、本発明の高速フーリエ変換装置および高速フーリエ変換装置に用いられるビット長補正方法の実施の形態につき、図面を用いて説明する。各図において同一、または相当する部分については、同一符号を付して説明する。
【００１２】
実施の形態１．
図１は、本発明の実施の形態１に係る高速フーリエ変換装置を示すブロック構成図である。本実施の形態１における高速フーリエ変換装置は、振幅調査部１１、振幅補正部１２、バタフライ演算部１３、およびメモリ１４を有するＦＦＴ／ＩＦＦＴ処理部１０を備えて構成されている。ここで、振幅調査部１１および振幅補正部１２は、部分データ補正部に相当する。また、ＦＦＴ／ＩＦＦＴ処理部１０には、データ入力を行う入力線１、および処理結果を出力する出力線２が接続されている。
【００１３】
以下、図１を参照しながら、各部の機能と動作について説明する。なお、以下の説明においては、ＦＦＴの点数は、一例として１０２４点（２の１０乗）とする。
【００１４】
ＦＦＴ／ＩＦＦＴ処理部１０の基本動作は、以下の３ステップのようになる。
［入力ステップ］入力線１から、処理するデータを受け取る。
［処理ステップ］受け取ったデータに対し、ＦＦＴ（または、ＩＦＦＴ）を実施する。
［出力ステップ］出力線２から、処理結果を送り出す。
【００１５】
この時、ＦＦＴ／ＩＦＦＴ処理部１０の内部での動作は、以下のようになる。
［ステップＳ１］振幅調査部１１が、入力線１からデータを受け取る。これをデータＡとする。
［ステップＳ２］以下のステップＳ２１〜Ｓ２７のループを、９回繰り返す。
［ステップＳ２１］振幅調査部１１が、最大値の振幅と、２番目に大きい振幅を調べる。これを、調査結果Ｚとする。
［ステップＳ２２］振幅調査部１１が、調査結果ＺとデータＡを振幅補正部１２へ送る。
【００１６】
［ステップＳ２３］振幅補正部１２が、調査結果Ｚを元に、データＡを補正する。補正方法の詳細については、図２、図３を用いて後述する。この補正結果をデータＢとする。なお、調査結果Ｚは、データＡの補正開始前に、その受け取りが完了する。
［ステップＳ２４］振幅補正部１２が、データＢをメモリ１４に格納する。
【００１７】
［ステップＳ２５］バタフライ演算部１３が、メモリ１４からデータＢを読み出し、バタフライ演算を実施する。
［ステップＳ２６］バタフライ演算部１３が、バタフライ演算結果を振幅調査部１１へ送る。
［ステップＳ２７］振幅調査部１１が、バタフライ演算部１３からバタフライ演算結果を受け取る。この演算結果を新しいデータＡとする。
この新しいデータＡを新たな入力データとして、ステップＳ２１〜Ｓ２７を繰り返した後、次のステップＳ３に移行する。
【００１８】
［ステップＳ３］振幅調査部１１が、ステップＳ２でのループ処理後の最終のデータＡについて、最大値の振幅と、２番目に大きい振幅を調べる。これを、調査結果Ｚとする。
［ステップＳ４］振幅調査部１１が、データＡとともに、振幅の調査結果Ｚを振幅補正部１２へ送る。
【００１９】
［ステップＳ５］振幅補正部１２が、調査結果Ｚを元に、データＡを補正する。この補正結果をデータＢとする。
［ステップＳ６］振幅補正部１２が、「データＢとデータの補正としてビットシフトを行った回数」を出力線２に、ＦＦＴ結果として出力する。
【００２０】
ここで、ステップＳ６における「データの補正としてビットシフトを行った回数」とは、振幅補正部１２で行う補正に係わる値、補正方法に関する記述のところで詳細に説明する。
【００２１】
以上の基本動作により、ＦＦＴ／ＩＦＦＴ処理部１０は、ブロック浮動小数点のようなＦＦＴ／ＩＦＦＴ処理結果を出力することができる。なお、本実施の形態１では、後述するように、最大値の振幅を削る形の補正方法を採用しているため、ブロック浮動小数点のＦＦＴ／ＩＦＦＴ処理結果とは、値が異なる。
【００２２】
次に、図２と図３を用いて、振幅補正部１２の動作を説明する。図２は、従来の高速フーリエ変換装置による補正前後のグラフであり、本発明の実施の形態１に係る高速フーリエ変換装置の補正内容と比較するために用意したグラフである。また、図３は、本発明の実施の形態１に係る高速フーリエ変換装置の補正内容を示したグラフである。
【００２３】
図２、図３とも、左側の（ａ）が補正前のグラフであり、右側の（ｂ）が補正後のグラフを示している。また、図２、図３の右端に示された「ビット長」は、バタフライ演算部１３でのビット長を示している。なお、ＦＦＴ／ＩＦＦＴの入力は、一般に複素数であることが多いが、振幅で扱った方が、説明が用意であるため、ここでは、振幅を用いて説明する。
【００２４】
図２、図３に示したように、いずれも、補正前の振幅値では、ビット長を超えるものがある状態を例示している。バタフライ演算部１３に与える値は、固定小数点演算を行うビット長に収まっている必要があるため、振幅補正部１２で、ビット長を越えるものを補正することとなる。すなわち、振幅補正部１２では、補正前の入力ビット長をＸ、補正後の出力ビット長をＹとすると、Ｘ≧Ｙの関係が成り立つ。
【００２５】
まず、図２における従来の高速フーリエ変換装置による補正について説明する。図２の補正では、全部の値を半減させることで、全ての振幅をビット長に収めている。これをビットシフトと呼ぶ。従来方式では、すべての振幅に対してこのビットシフトが用いられてきた。
【００２６】
次に、図３における本実施の形態１の高速フーリエ変換装置による補正について説明する。図３の補正では、ビット長を超えている点のみ値を削減することで、全ての振幅をビット長に収めている。
【００２７】
振幅補正部１２は、振幅調査部１１から振幅の最大値と２番目に大きい値を受け取る。この例では、最大値はビット長を超えているが、２番目の値はビット長に収まっている場合を例示している。このため、振幅の最大値のみを補正する。この時、図３に示した本実施の形態１による補正では、「振幅の４分の１」を減算するという方法をとっている。
【００２８】
なお、この説明では、振幅のビット長を例に挙げた。ここで、ＦＦＴの対象となる各値が複素数の場合には、実部と虚部のうち絶対値の大きい方を、前述の説明の振幅と置き換えても問題ない。ただし、補正部分では、「実部なら実部の１／４を減算し、虚部なら虚部の１／４を減算する」というように、実部と虚部それぞれ独立に計算する。
【００２９】
また、ここでは振幅の４分の１を減算するという補正方法を一例として挙げたが、以下のような補正方法を採用することもできる。
・振幅を半減させる。
・ビット長の上限に一致するように、振幅を減らす。
・振幅の１／２の減算結果、１／４の減算結果、１／８の減算結果というように、複数の減算結果を用意し、その中でビット長に収まる最大値のものを選択する。
【００３０】
また、ＦＦＴ／ＩＦＦＴの処理結果として、「データＢとデータの補正としてビットシフトを行った回数」を出力する例を示したが、ビットシフトを行った回数の出力を止め、データのみの出力とする方法もある。この場合には、出力用としてビットシフト量をあらかじめ設定しておく。その上で、振幅補正部１２は、この設定値とビットシフトを行った回数の差分で、データを補正する。
【００３１】
また、振幅補正部１２は、「最大値の振幅と、２番目に大きい振幅を調べる」としたが、ビット長を定め、そのビット長を超える個数を調査結果Ｚとして、振幅補正部１２へ送る方法もある。この場合には、振幅補正部１２は、ビット長を超える個数に応じて、例えば、以下のように動作する。
・個数＝０の場合    値はそのままで補正しない。
・個数＝１の場合    最大の振幅値のみを補正する。
・個数２以上の場合  全部の点の値を半減させる。
【００３２】
図３では、ビット長を超えるものが１点のみの場合を例示した。これに対して、２番目の値もビット長を超えていた場合には、振幅補正部１２は、図２の従来例と同じく、全部の値を半減させる。これにより、振幅補正部１２は、全ての振幅をビット長に収めることになる。
【００３３】
さらに、振幅補正部１２は、このような全部の値を半減させる処理を実施した回数をカウントし、最後に「データの補正としてビットシフトを行った回数」を出力する。逆に、最大値でもビット長を超えてない場合は、各値をそのままとする。
【００３４】
以上のように、実施の形態１に示す高速フーリエ変換装置によれば、単独の点のみの値がビット長を越える大きい値の場合にも、その値に引きずられることなく、下位ビットの切り捨てを抑制することができる。この抑制により、振幅の小さな成分の情報欠落が減り、より情報劣化の少ない演算結果が得られる。
【００３５】
実施の形態２．
先の実施の形態１では、振幅調査部１１において、「最大値の振幅と、２番目に大きい振幅を調べる」とした。これを「最大値の振幅と、ｎ番目に大きい振幅を調べる」とすることで、補正する値（点）の数を複数に増やすことができる。また、「ビット長を超える値（点）の数」とすることでも、同様に補正する値（点）の数を複数に増やすことができる。
【００３６】
以上のように、実施の形態２に示す高速フーリエ変換装置によれば、単独の点に限らず、複数の点の値がビット長を越える大きい値の場合にも、その点数が少数であれば、その値に引きずられることなく、下位ビットの切り捨てを抑制することができる。この抑制により、振幅の小さな成分の情報欠落が減り、より情報劣化の少ない演算結果が得られる。
【００３７】
実施の形態３．
図４は、本発明の実施の形態３に係る高速フーリエ変換装置を示す構成図である。高速フーリエ変換装置の構成を示した図である。本実施の形態３における高速フーリエ変換装置は、振幅調査部１１、振幅補正部１２、およびＦＦＴ／ＩＦＦＴコア１５を有するＦＦＴ／ＩＦＦＴ処理部１０を備えて構成されている。ここで、ＦＦＴ／ＩＦＦＴコア１５は、高速フーリエ変換の中核をなす構成要素である。
【００３８】
先の実施の形態１では、図１に示したように、バタフライ演算部１３を使った構成を示した。これに対して、本実施の形態３では、より一般的なＦＦＴ／ＩＦＦＴコア１５を組み込んだ構成を示している。
【００３９】
ＦＦＴ／ＩＦＦＴコア１５は、「Ｘビット入力、Ｙビット出力」（Ｘ＜Ｙ）となる固定小数点演算ブロックであり、先の実施の形態１で示したバタフライ演算部１３やメモリ１４を内蔵している。振幅調査部１１と振幅補正部１２は、基本的には、先の実施の形態１、２と同じである。
【００４０】
本実施の形態３における振幅調査部１１および振幅補正部１２は、ｎ番目に大きい振幅がＸビットに収まるように、ＦＦＴ／ＩＦＦＴコア１５の出力値をビットシフトする。このように、本実施の形態３に示す高速フーリエ変換装置は、一般的なＦＦＴ／ＩＦＦＴの固定小数点演算ブロックを使って、装置を構成することができる。
【００４１】
以上のように、実施の形態３に示す高速フーリエ変換装置によれば、一般的なＦＦＴ／ＩＦＦＴの固定小数点演算ブロックを使用した上で、振幅調査部および振幅補正部の働きにより、ｎ番目に大きい振幅がＸビットに収まるようにビットシフトすることで、下位ビットの切り捨てを抑制することができる。この抑制により、振幅の小さな成分の情報欠落が減り、より情報劣化の少ない演算結果が得られる。
【００４２】
実施の形態４．
本実施の形態４では、先の実施の形態３の構成の変形例について説明する。図５は、本発明の実施の形態４に係る高速フーリエ変換装置を示す構成図である。本実施の形態４における高速フーリエ変換装置は、振幅調査部１１ａ、１１ｂ、振幅補正部１２ａ、１２ｂ、およびＦＦＴ／ＩＦＦＴコア１５を有するＦＦＴ／ＩＦＦＴ処理部１０を備えて構成されている。
【００４３】
ここで、ＦＦＴ／ＩＦＦＴコア１５は、高速フーリエ変換の中核をなす構成要素である。また、振幅調査部１１ａ、１１ｂ、および振幅補正部１２ａ、１２ｂは、部分データ補正部に相当する。さらに、振幅調査部１１ａおよび振幅補正部１２ａは、第１の部分データ補正部に相当し、振幅調査部１１ｂ、および振幅補正部１２ｂは、第２の部分データ補正部に相当する。
【００４４】
先の実施の形態３では、ＦＦＴ／ＩＦＦＴコア１５の後段に、振幅調査部１１と振幅補正部１２を１台ずつ配置した場合について説明した。これに対して、本実施の形態４では、ＦＦＴ／ＩＦＦＴコア１５の後段に、振幅調査部１１ｂと振幅補正部１２ｂを１台ずつ配置するとともに、ＦＦＴ／ＩＦＦＴコア１５の前段にも同じように、振幅調査部１１ａと振幅補正部１２ａを１台ずつ配置している。
【００４５】
このため、本実施の形態４の構成によれば、ＦＦＴ／ＩＦＦＴコア１５の前段に設けられた振幅調査部１１ａと振幅補正部１２ａの働きによりビットシフトを行えることで、入力線１のビット長をＸビットではなく、Ｙビットまで拡張することができる。さらに、入力線１から入力される値の範囲をさらに拡張し、浮動小数点形式のように、仮数部と指数部のペアによる表現とすることも可能である。
【００４６】
以上のように、実施の形態４に示す高速フーリエ変換装置によれば、ＦＦＴ／ＩＦＦＴの固定小数点演算ブロックの前段にも振幅調査部および振幅補正部を設けることで、先の実施の形態４と同様の効果が得られるとともに、入力値の表現範囲を広げることができる。
【００４７】
実施の形態５．
本実施の形態５では、先の実施の形態４の構成の変形例について説明する。図６は、本発明の実施の形態５に係る高速フーリエ変換装置を示すブロック構成図である。本実施の形態５における高速フーリエ変換装置は、バタフライ演算部１３、メモリ１４、桁あふれ管理部１６、および桁あふれ補正部１７を有するＦＦＴ／ＩＦＦＴ処理部１０を備えて構成されている。ここで、桁あふれ管理部１６および桁あふれ補正部１７は、部分データ補正部に相当する。
【００４８】
本実施の形態５における図６の構成は、先の実施の形態１における図１の構成と比較すると、振幅調査部１１および振幅補正部１２の代わりに、桁あふれを管理する桁あふれ管理部１６、および桁あふれを補正する桁あふれ補正部１７を備えている点が異なっている。
【００４９】
以下、図６を参照しながら、各部の機能と動作について説明する。なお、以下の説明においては、ＦＦＴの点数は、一例として１０２４点（２の１０乗）とする。
【００５０】
ＦＦＴ／ＩＦＦＴ処理部１０の基本動作は、以下の３ステップのようになる。
［入力ステップ］入力線１から、処理するデータを受け取る。
［処理ステップ］受け取ったデータに対し、ＦＦＴ（または、ＩＦＦＴ）を実施する。
［出力ステップ］出力線２から、処理結果を送り出す。
【００５１】
この時、ＦＦＴ／ＩＦＦＴ処理部１０の内部での動作は、以下のようになる。
［ステップＳ１］バタフライ演算部１３が、入力線１からデータを受け取る。これをデータＡとする。
［ステップＳ２］バタフライ演算部１３が、バタフライ演算を実施する。
【００５２】
［ステップＳ３］バタフライ演算部１３が、バタフライ演算結果をメモリ１４に格納する。この時、バタフライ演算部１３は、桁あふれの有無を桁あふれ管理部１６に通知する。
［ステップＳ４］桁あふれ管理部１６は、データＡに対する全てのバタフライ演算結果の桁あふれ有無を保持する。
【００５３】
［ステップＳ５］以下のステップＳ５１〜５４のループを、９回繰り返す。
［ステップＳ５１］桁あふれ管理部１６が、桁あふれ発生件数を桁あふれ補正部１７に通知する。
［ステップＳ５２］桁あふれ補正部１７が、メモリ１４からデータを読み出し、値を補正し、補正結果をバタフライ演算部１３に渡す。
【００５４】
［ステップＳ５３］バタフライ演算部１３が、桁あふれ補正部１７からデータを受け取り、これにバタフライ演算を実施する。
［ステップＳ５４］バタフライ演算部１３が、バタフライ演算結果をメモリ１４に格納する。また、バタフライ演算部１３は、桁あふれの有無を桁あふれ管理部１６に通知する。
この後、ステップＳ５１〜Ｓ５４を繰り返した後、次のステップＳ６に移行する。
【００５５】
［ステップＳ６］桁あふれ管理部１６が、桁あふれ発生件数を桁あふれ補正部１７に通知する。
［ステップＳ７］桁あふれ補正部１７が、メモリ１４からデータを読み出し、値を補正する。
［ステップＳ８］桁あふれ補正部１７が、「補正結果とデータの補正としてビットシフトを行った回数」を出力線２に、ＦＦＴ結果として出力する。
【００５６】
以上の基本動作により、ＦＦＴ／ＩＦＦＴ処理部１０は、ブロック浮動小数点のようなＦＦＴ／ＩＦＦＴ処理結果を出力することができる。
【００５７】
次に、本実施の形態５で新たに採用されている桁あふれ管理部１６と桁あふれ補正部１７の動作を説明する。ＦＦＴ／ＩＦＦＴは、バタフライ演算のループの繰り返しによって実現されるが、その中で、桁あふれ管理部１６は、以下のように動作する。
【００５８】
［動作１］バタフライ演算部１３より、バタフライ演算時の桁あふれの有無を受け取る。
［動作２］桁あふれの有無を、バタフライ演算を行った値の位置とともに記憶する。
［動作３］桁あふれの発生回数を、カウントする。
【００５９】
［動作４］桁あふれ補正部１７が、メモリ１４から値の読み出しを開始する前に、桁あふれ発生回数を桁あふれ補正部１７に送り、発生回数のカウントをクリアする。
［動作５］桁あふれ補正部１７が、メモリ１４から値を読み出す際、その値に対応する桁あふれの有無を、桁あふれ補正部１７に送る。また、これと平行して、バタフライ演算部１３より、バタフライ演算時の桁あふれの有無を受け取る。
【００６０】
一方、桁あふれ補正部１７は、以下のように動作する。
［動作１］桁あふれ管理部１６より、桁あふれ発生回数を受け取る。
［動作２］メモリ１４から値を読み出すとともに、桁あふれ管理部１６より、これに対応する桁あふれの有無を受け取る。
［動作３］メモリ１４から読み出した値がＸビットなら、桁あふれ有無を使い、この値を「Ｘ＋１」ビットの値に拡張する。
【００６１】
［動作４］桁あふれ発生回数がｎ回未満、かつ、読み出した値に対応する桁あふれ有無が「有」なら、値を補正する（なお、補正方法は、先の実施の形態１と同じである）。桁あふれ発生回数がｎ以上なら、読み出した値に対応する桁あふれ有無に関係なく、値を半分にする。
［動作５］ＦＦＴ／ＩＦＦＴのループの途中なら、補正した値をバタフライ演算部１３に渡す。ループを抜けた後なら、「補正結果とデータの補正としてビットシフトを行った回数」を出力線２に出力する。
【００６２】
以上のように、実施の形態５に示す高速フーリエ変換装置によれば、一部の点のみの値がビット長を越える大きい値の場合にも、その値に引きずられることなく、下位ビットの切り捨てを抑制することができる。この抑制により、振幅の小さな成分の情報欠落が減り、より情報劣化の少ない演算結果が得られる。
【００６３】
実施の形態６．
ＦＦＴ／ＩＦＦＴは、バタフライ演算の繰り返しで実現される。基数２の１０２４点ＦＦＴであれば、５１２回のバタフライ演算を１段として、これを１０段繰り返すことになる。
【００６４】
先の実施の形態１〜５では、ＦＦＴ／ＩＦＦＴの繰り返し演算の中で、何段目かに関わらず、同じ補正方法を行う場合について説明した。これに対し、本実施の形態６では、補正方法を段数応じて切り替える場合について説明する。
【００６５】
例えば、バタフライ演算を１０段繰り返す際に、１〜３段までは、先の実施の形態１と同じ補正を行うが、４〜１０段では、最大値がビット長に収まらない場合に値を半減させるように補正方法を切り替えることも考えられる。この場合、４〜１０段では、従来方法での補正を行う形になる。
【００６６】
以上のように、実施の形態５に示す高速フーリエ変換装置によれば、一部の点のみの値がビット長を越える大きい値の場合にも、その値に引きずられることなく、下位ビットの切り捨てを抑制することができる。また、ＦＦＴ／ＩＦＦＴのバタフライ演算の後半において補正方法を切り替えることで、積み上がってきた値に対しては、一部の点のみの値の振幅を補正により削ることがなくなり、より情報劣化の少ない演算結果が得られる。
【符号の説明】
【００６７】
１  入力線、２  出力線、１０  ＦＦＴ／ＩＦＦＴ処理部、１１、１１ａ  振幅調査部、１２、１２ａ  振幅補正部、１３  バタフライ演算部、１４  メモリ、１５  ＦＦＴ／ＩＦＦＴコア、１６  桁あふれ管理部、１７  桁あふれ補正部。
【図１】
2012128493.tif 000003
【図２】
2012128493.tif 000004
【図３】
2012128493.tif 000005
【図４】
2012128493.tif 000006
【図５】
2012128493.tif 000007
【図６】
2012128493.tif 000008