(57)【要約】【課題】  バタフライ演算の際の桁あふれ情報を処理するためのメモリ容量や演算回路を削減する。【解決手段】  それぞれがＮ／２個の並列に設けられたバタフライ演算部を含むｌｏｇ２Ｎ段のバタフライ演算部群と、最終段のバタフライ演算部群の演算結果をビットシフトすることにより正規化する正規化部とを備え、バタフライ演算部はそれぞれ、演算結果と外部からの桁あふれ予測値とに基づいて桁あふれ予測値を出力し、一つのバタフライ演算部群においては、順次、次のバタフライ演算部に対して桁あふれ予測値を出力し、Ｎ／２個目のバタフライ演算部からの桁あふれ予測値を、次の段のバタフライ演算部群におけるビットシフトのための制御信号として出力する。【選択図】  図３
2016081356.tif 000002
【特許請求の範囲】
【請求項１】
入力データのビットシフトを行いビットシフトされたデータに対するバタフライ演算を行うバタフライ演算部を有し、Ｎ個（Ｎは２の乗数）のデータに対して高速フーリエ演算処理を行う装置であって、
それぞれがＮ／２個の、並列に設けられた前記バタフライ演算部を含む、ｌｏｇ２Ｎ段のバタフライ演算部群と、
最終段の前記バタフライ演算部群の演算結果をビットシフトすることにより正規化し、前記高速フーリエ演算処理の演算結果として出力する正規化部とを備え、
前記バタフライ演算部はそれぞれ、前記バタフライ演算部における演算結果と外部からの桁あふれ予測値とに基づいて桁あふれ予測値を出力し、
一つの前記バタフライ演算部群においては、一つめの前記バタフライ演算部から、順次、次のバタフライ演算部に対して桁あふれ予測値を出力し、
前記バタフライ演算部群におけるＮ／２個目のバタフライ演算部からの桁あふれ予測値を、次の段のバタフライ演算部群におけるバタフライ演算部それぞれにおけるビットシフトのための制御信号として出力し、
前記正規化部は、１段目の前記バタフライ演算部群からｌｏｇ２Ｎ−１段目の前記バタフライ演算部群までの、それぞれの前記バタフライ演算部群におけるＮ／２個目のバタフライ演算部からの桁あふれ予測値を加算した結果に基づいてビットシフト量を決めることを特徴とするデータ処理装置。
【請求項２】
前記バタフライ演算部は、
入力されたデータのビットシフトを行うビットシフト部と、
前記ビットシフト部からのデータを加算する加算器及び加算結果に係数を乗算する乗算器とを含む演算回路と、
位相係数アドレスの値より前記係数を生成する係数発生部と、
入力された桁あふれ予測値と、演算回路の演算結果とから、新たな桁あふれ予測値を出力する桁あふれ予測部とを有することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前段の前記バタフライ演算部群の演算結果を、高速フーリエ演算を満足するように、後段の前記バタフライ演算部群のバタフライ演算部に出力するデータ移動部を備えたことを特徴とする請求項１に記載のデータ処理装置。
【請求項４】
前記入力データとして音声データが入力されることを特徴とする請求項１に記載のデータ処理装置。
【請求項５】
前記正規化部は、前記加算した結果の値がＭである場合に、Ｍビットのビットシフトを行うことを特徴とする請求項１に記載のデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ処理装置に関し、特に、入力データに対してフーリエ変換処理を施す装置に関する。
【背景技術】
【０００２】
従来、時間領域信号を周波数領域信号に変換する高速フーリエ変換（ＦＦＴ）、及び周波数領域信号を時間領域信号へ変換する高速フーリエ逆変換（ＩＦＦＴ）処理を行う場合、バタフライ演算を複数回実行する。固定小数点演算で行うバタフライ演算では、出力信号のビットレンジは入力信号のビットレンジに対して１ビット増加する可能性がある。バタフライ演算のビットレンジに制限がある場合、演算結果がビットレンジ制限を超えてしまう（いわゆる「桁あふれ」と呼ばれる）ことがあった。桁あふれ発生時にビットシフト量を更新することにより、後続データの演算処理時に桁あふれの発生を抑制することが提案されている（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１１−６０１７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１においては、各バタフライ演算回路で桁あふれを検出し、バタフライ演算毎にシフト量制御部へ信号を出力している。そのため、シフト量制御部では、バタフライ演算回数分の桁あふれ情報を保持するメモリ容量、又は、バタフライ演算回数分の桁あふれ情報を処理する演算回路が必要になる。
【０００５】
そこで本発明では、バタフライ演算を用いて信号処理を行う際に、バタフライ演算の際の桁あふれ情報を処理するためのメモリ容量や演算回路を削減することを目的とする。
【課題を解決するための手段】
【０００６】
データ処理装置は、入力データのビットシフトを行いビットシフトされたデータに対するバタフライ演算を行うバタフライ演算部を有し、Ｎ個（Ｎは２の乗数）のデータに対して高速フーリエ演算処理を行う装置であって、それぞれがＮ／２個の、並列に設けられた前記バタフライ演算部を含む、ｌｏｇ２Ｎ段のバタフライ演算部群と、最終段の前記バタフライ演算部群の演算結果をビットシフトすることにより正規化し、前記高速フーリエ演算処理の演算結果として出力する正規化部とを備え、前記バタフライ演算部はそれぞれ、前記バタフライ演算部における演算結果と外部からの桁あふれ予測値とに基づいて桁あふれ予測値を出力し、一つの前記バタフライ演算部群においては、一つめの前記バタフライ演算部から、順次、次のバタフライ演算部に対して桁あふれ予測値を出力し、前記バタフライ演算部群におけるＮ／２個目のバタフライ演算部からの桁あふれ予測値を、次の段のバタフライ演算部群におけるバタフライ演算部それぞれにおけるビットシフトのための制御信号として出力し、前記正規化部は、１段目の前記バタフライ演算部群からｌｏｇ２Ｎ−１段目の前記バタフライ演算部群までの、それぞれの前記バタフライ演算部群におけるＮ／２個目のバタフライ演算部からの桁あふれ予測値を加算した結果に基づいてビットシフト量を決める。
【発明の効果】
【０００７】
バタフライ演算の際の桁あふれ情報を処理するためのメモリ容量や演算回路を削減することが可能となる。
【図面の簡単な説明】
【０００８】
【図１】バタフライ演算部の構成を示す図である。
【図２】バタフライ演算部の構成を示す図である。
【図３】高速フーリエ変換処理を行うデータ処理装置の構成を示す図である。
【図４】桁あふれ予測部の動作を示すフローチャートである。
【図５】高速フーリエ変換処理を行うデータ処理装置の構成を示す図である。
【図６】高速フーリエ変換処理を示すフローチャートである。
【図７】各バタフライ演算装置におけるデータの入出力の対応を示す図である。
【図８】各バタフライ演算装置におけるデータの入出力の対応を示す図である。
【図９】各バタフライ演算装置におけるデータの入出力の対応を示す図である。
【図１０】入力データ列が記憶されている部分のメモリマップを示す図である。
【発明を実施するための形態】
【０００９】
以下、図面を参照して本発明の実施例を詳細に説明するが、この発明は以下の実施の形態に限定されない。
【００１０】
以下、図面を参照しながら、実施形態について説明する。図１は、本実施形態のデータ処理装置において用いられるバタフライ演算部の構成を示す図である。図１のバタフライ演算部において、入力端子１０１は、前のバタフライ演算部からの桁あふれ予測値を入力する。入力端子１０２、１０３は、バタフライ演算対象となる入力信号データ、例えば４８ＫＨｚでサンプリングされた１６ビットの音声データを入力する。入力端子１０４は、ビットシフト部１１６の制御信号を入力する。入力端子１０５は、位相係数アドレスｋ（ｋ＝０からＮ／２−１、Ｎは入力データ数）を入力する。出力端子１０６、１０７は、バタフライ演算結果の出力信号データを出力する。出力端子１０８は、桁あふれ予測部１１７から桁あふれ予測値を出力する。
【００１１】
図１のバタフライ演算部の動作について説明する。４８ＫＨｚでサンプリングされた１６ビット長の２つの音声データ、Ｓ１、Ｓ２をバタフライ演算するときの図１の動作を説明する。まず、入力信号Ｓ１を入力端子１０２へ、Ｓ２を入力端子１０３へ入力する。信号１０２、１０３の値はビットシフト部１１６へ入力される。ビットシフト部１１６では、入力信号Ｓ１、Ｓ２の値に対し、入力端子１０４からのビットシフト制御信号が０であればビットシフトせず、０以外であれば１ビット右シフトを行う。
【００１２】
ビットシフト部１１６からの出力１１２、出力１１３の値を加算器１０９、１１０で加算する。入力端子１０５の値ｋは位相係数発生部１１８へ入力される。位相係数発生部１１８から位相係数１１９が出力される。加算器１１０の出力１１５と位相係数１１９とが乗算器１１１で乗算される。加算器１０９の出力値は出力端子１０６から出力される。乗算器１１１の出力値は出力端子１０７から出力される。入力端子１０１からの値（０または１）は桁あふれ予測部１１７の入力Ａに入力される。加算器１０９の出力１１４は桁あふれ予測部１１７の入力Ｂへ入力される。加算器１１０の出力１１５は桁あふれ予測部１１７の入力Ｃへ入力される。三つの入力値Ａ、Ｂ、Ｃより、桁あふれ予測部１１７は桁あふれ予測値Ｄ（０または１）を出力する。桁あふれ予測値Ｄは出力端子１０８から出力される。
【００１３】
図４は桁あふれ予測部１１７の動作を示すフローチャートである。
【００１４】
桁あふれ予測部、動作スタート（ＳＴＥＰ０）。入力端子１０１の値が、桁あふれ予測部１１７の入力Ａに入力される。演算結果１１４の値が、桁あふれ予測部１１７の入力Ｂに入力される。演算結果１１５の値が、桁あふれ予測部１１７の入力Ｃに入力される（ＳＴＥＰ１）。入力Ａが０でない場合ＳＴＥＰ５へ進み、Ａが０の場合ＳＴＥＰ３へ進む（ＳＴＥＰ２）。入力｜Ｂ｜≧ＴＨ（｜Ｂ｜はＢの絶対値、ＴＨは閾値）がＹＥＳであればＳＴＥＰ５へ進み、ＮＯであればＳＴＥＰ４へ進む（ＳＴＥＰ３）。入力｜Ｃ｜≧ＴＨ（｜Ｃ｜はＣの絶対値、ＴＨは閾値）がＹＥＳであればＳＴＥＰ５へ進み、ＮＯであればＳＴＥＰ６へ進む（ＳＴＥＰ４）。ＹＥＳであれば桁あふれ予測値Ｄ＝１とし、ＳＴＥＰ７へ進む（ＳＴＥＰ５）。ＮＯであれば桁あふれ予測値Ｄ＝０とし、ＳＴＥＰ７へ進む（ＳＴＥＰ６）。桁あふれ予測部１１７の動作を終了する（ＳＴＥＰ７）。
【００１５】
入出力端子１０２、１０３、１０６、１０７の中で最小となるビット幅上限をＬビットとしたとき、閾値ＴＨは式（１）となる。
ＴＨ＝２＾（Ｌ−２）    （１）
次に、図３のデータ処理装置による高速フーリエ変換処理について説明する。図３において、データ移動部Ａ２５４、又はデータ移動部Ｂ２５５を挟んで接続されたバタフライ演算部の接続数を段と表記する。例えば、図３において、バタフライ演算部２０１とバタフライ演算部２０５は２段接続、バタフライ演算部２０１とバタフライ演算部２０５とバタフライ演算部２０９は３段接続となる。
【００１６】
また、図３において、１段目のバタフライ演算部群と表記した場合は、バタフライ演算部２０１−２０４の４つのバタフライ演算部を指す。２段目のバタフライ演算部群と表記した場合は、バタフライ演算部２０５−２０８の４つのバタフライ演算部を指す。最終段（３段目）のバタフライ演算部群と表記した場合は、バタフライ演算部２０９−２１２の４つのバタフライ演算部を指す。
【００１７】
また図３において、バタフライ演算部２０１の出力端子１０８と、バタフライ演算部２０２の入力端子１０１を接続している数を列と表記する。例えば、バタフライ演算部２０１とバタフライ演算部２０２は２列接続、バタフライ演算部２０１とバタフライ演算部２０２とバタフライ演算部２０３は３列接続となる。バタフライ演算部２０２に対して前列のバタフライ演算部と表記した場合はバタフライ演算部２０１を指し、後列のバタフライ演算部と表記した場合はバタフライ演算部２０３を指す。
【００１８】
図３において、１２個のバタフライ演算部２０１−２１２はそれぞれ、図１のバタフライ演算部と同じ構成を持ち、同様の動作を行う。なお、以下の説明では表記の簡略化のために、例えばバタフライ演算部２０１の入力端子１０２のことを、２０１＿１０２と表記する場合がある。これは、バタフライ演算部の番号と、端子の入出力と番号が変化しても同様に表記する。例えば、バタフライ演算部２１２の出力端子１０６であれば、２１２＿１０６となる。
【００１９】
図３のデータ処理装置は、入力データ数Ｎ＝８としたときの構成である。図３において、図１と同様の動作を行う１２（ｌｏｇ２Ｎ＊（Ｎ／２））個のバタフライ演算部２０１−２１２を有する。即ち、１段を４列（Ｎ／２個）のバタフライ演算部群としたとき、その演算部群が３（ｌｏｇ２Ｎ）段接続された構成となる。
【００２０】
入力端子２３１、２３２、２３４、２３５、２３７、２３８、２４０、２４１の中で最小となるビット幅の上限をＬビットとすると、入力信号系列データＳ（ｎ）のビット幅はＬ−２ビット以下である。
【００２１】
まず、１段目のバタフライ演算部群２０１−２０４に係る動作について説明する。入力端子２５１に初期桁あふれ予測値（ここでは０）を入力する。入力端子２５１の値は、２０１＿１０１へ入力される。また、８個の入力信号系列データＳ（ｎ）を、高速フーリエ変換を満たすように入力する。入力端子２３１にＳ（０）、入力端子２３２にＳ（４）、入力端子２３４にＳ（１）、入力端子２３５にＳ（５）、入力端子２３７にＳ（２）、入力端子２３８にＳ（６）、入力端子２４０にＳ（３）、入力端子２４１にＳ（７）、をそれぞれ入力する。入力端子２３３、２３６、２３９、２４２には、初期ビットシフト制御信号（ここでは０）を入力する。入力端子２３１の値は２０１＿１０２へ入力される。入力端子２３２の値は、２０１＿１０３へ入力される。入力端子２３３の値は、２０１＿１０４へ入力される。このような、入力端子２３１−２４２の値と入力先の関係を図７（ａ）に示す。
【００２２】
位相係数アドレス発生部２７１より、各信号線２１３−２１６を通じて各バタフライ演算部２０１−２０４の入力端子１０５に入力する位相係数アドレスｋを出力する。入力端子と信号線と入力する位相係数アドレスｋの関係を図７（ｂ）に示す。２０１＿１０８の桁あふれ予測値を２０２＿１０１へ入力し、２０２＿１０８の桁あふれ予測値を２０３＿１０１へ入力する。２０３＿１０８の桁あふれ予測値を２０４＿１０１へ入力し、２０４＿１０８の桁あふれ予測値を、信号線２６１を通じて、後段のバタフライ演算部群２０５−２０８の各入力端子１０４と加算器２６３へ入力する。
【００２３】
従来は、バタフライ演算部毎に桁あふれ情報を取り扱っていたため、バタフライ演算部の数だけの桁あふれ情報を記憶する記憶手段、又は、バタフライ演算部の数だけの桁あふれ情報処理回路がシフト量制御部に必要となっていた。
【００２４】
本実施形態では、４個のバタフライ演算部毎に桁あふれ予測値を、加算器へ入力する。そして次段のビットシフト制御部にビットシフト制御信号として入力する。この動作を段毎に繰り返すことにより、桁あふれ情報を記憶する記憶手段等の回路規模を削減することが可能となる。
【００２５】
２０１＿１０６の演算結果は、データ移動部Ａ２５４の入力ａ１へ、２０１＿１０７の演算結果は、データ移動部Ａ２５４の入力２へ、１段目のバタフライ演算部群の演算結果は図７（ｃ）のようにデータ移動部Ａ２５４へ入力される。
【００２６】
次に、データ移動部Ａ２５４の動作について説明する。データ移動部Ａ２５４では、高速フーリエ変換の演算を満足するようなデータ移動を行う。データ移動部Ａ２５４の入力ａ１の値は出力ｂ１へ移動する。入力ａ２の値は出力ｂ５へ移動する。全ての入力ａ１−ａ８に対して、出力ｂ１−ｂ８への移動を行う。入力ａ１−ａ８に対する、出力ｂ１−ｂ８の関係を図７（ｄ）に示す。
【００２７】
データ移動部Ａ２５４の出力ｂ１−ｂ８は、２段目のバタフライ演算部群２０５−２０８の入力端子１０２、１０３へ入力される。データ移動部Ａ２５４の出力ｂ１−ｂ８と２段目のバタフライ演算部群２０５−２０８の入力先端子の対応を図８（ａ）に示す。
【００２８】
次に、２段目のバタフライ演算部群２０５−２０８に係る動作について説明する。入力端子２５２に初期桁あふれ予測値（ここでは０）を入力する。入力端子２５２の値は、２０５＿１０１へ入力される。各バタフライ演算部２０５−２０８の入力端子１０２、１０３へは、図８（ａ）のようにデータ移動部Ａ２５４の出力ｂ１−ｂ８より信号が入力される。
【００２９】
信号線２６１を通り、２段目の各バタフライ演算部２０５−２０８の入力端子１０４に、前段の最終列バタフライ演算部２０４からの桁あふれ予測値が、ビットシフト制御信号として入力される。位相係数アドレス発生部２７１より、各信号線２１７−２２０を通じて各バタフライ演算部２０５−２０８の入力端子１０５に入力する位相係数アドレスｋを出力する。入力端子と信号線と入力する位相係数アドレスｋの関を図８（ｂ）に示す。
【００３０】
２段目の各バタフライ演算部の入力端子１０１−１０５に信号が入力された後、２段目のバタフライ演算部群は１段目のバタフライ演算部群と同様の動作を行う。１段目の同様の動作であるので、以降の動作を簡単に説明する。
【００３１】
図８（ｃ）に示すようにデータ移動部Ｂ２５５の入力ｃ１−ｃ８に対して演算結果を出力する。２段目最終列バタフライ演算部２０８の桁あふれ予測値を、信号線２６２を通じて３段目のバタフライ演算部群の各入力端子１０４と加算器２６３へ入力する。
【００３２】
次にデータ移動部Ｂ２５５の動作について説明する。データ移動部Ｂ２５５では、高速フーリエ変換の演算を満足するようなデータ移動を行う。入力ｃ１の値は出力ｄ１へ移動する。入力ｃ２の値は出力ｄ３へ移動する。全ての入力ｃ１−ｃ８に対して、出力ｄ１−ｄ８への移動を行う。入力ｃ１−ｃ８に対する移動先の出力ｄ１−ｄ８を図８（ｄ）に示す。
【００３３】
データ移動部Ｂ２５５の出力ｄ１−ｄ８は、３段目のバタフライ演算部群２０９−２１２の入力端子１０２、１０３へ入力される。出力ｄ１−ｄ８と３段目のバタフライ演算部群２０９−２１２の力先端子の対応を図９（ａ）に示す。
【００３４】
次に、３段目のバタフライ演算部群２０９−２１２に係る動作について説明する。入力端子２５３に初期桁あふれ予測値（ここでは０）を入力する。入力端子２５３の値は、２０９＿１０１へ入力される。各バタフライ演算部の入力端子１０２、１０３へは、図９（ａ）のようにデータ移動部Ｂ２５５の出力ｄ１−ｄ８より信号が入力される。
【００３５】
信号線２６２を通り、３段目の各バタフライ演算部２０９−２１２の入力端子１０４に前段の最終列バタフライ演算部２０８からの桁あふれ予測値が、ビットシフト制御信号として入力される。位相係数アドレス発生部２７１より、各信号線２２１−２２４を通じてバタフライ演算部２０９−２１２の入力端子１０５に入力する位相係数アドレスｋを出力する。各入力端子と信号線と入力する位相係数アドレスｋの関係を図９（ｂ）に示す。
【００３６】
３段目のバタフライ演算部２０９−２１２の入力端子１０１−１０５に信号が入力された後、３段目のバタフライ演算部群は１段目、及び２段目のバタフライ演算部群と同様の動作を行う。同様の動作であるので、以降の動作を簡単に説明する。
【００３７】
図９（ｃ）のように正規化ビットシフト部２５６の入力ｅ１−ｅ８に対して演算結果を出力する。３段目最終列バタフライ演算部２１２の桁あふれ予測値は使用されない。
【００３８】
次に、正規化ビットシフト部２５６の動作について説明する。入力された信号ｅ１−ｅ８に対して正規化ビットシフトを行い、その結果をｆ１−ｆ８に出力する。加算器２６３は、１段目、２段目のバタフライ演算部群からの桁あふれ予測値を加算し、正規化ビットシフトのシフト量を示すデータとして出力する。正規化ビットシフトのシフト量は、信号線２６４から入力される値をＭとすると、Ｍビット左シフトとなる。入力された信号ｅ１−ｅ８と出力ｆ１−ｆ８の対応を図９（ｄ）に示す。出力ｆ１−ｆ８の値をそれぞれ、出力端子２４３−２５０から出力し、高速フーリエ変換処理結果が得られる。
【００３９】
本実施形態では、入力データ数Ｎ＝８に対して高速フーリエ変換処理を施す構成について説明した。入力データ数Ｎは高速フーリエ変換処理の性質上、２の乗数の値をとる。Ｎが８以外の値を取ったときも、ｎ、ｋをＮの値に伴い変化させることにより、本実施形態と同様の構成で高速フーリエ変換装置を実現可能である。
【００４０】
このように、本実施形態では、入力データのビットシフトを行いビットシフトされたデータに対するバタフライ演算を行うバタフライ演算部を有し、Ｎ個（Ｎは２の乗数）のデータに対して高速フーリエ演算処理を行う装置が提示される。本実施形態では、それぞれがＮ／２個の、並列に設けられた前記バタフライ演算部を含む、ｌｏｇ２Ｎ段のバタフライ演算部群を備える。また、最終段のバタフライ演算部群の演算結果をビットシフトすることにより正規化し、高速フーリエ演算処理の演算結果として出力する正規化部を備える。また、バタフライ演算部はそれぞれ、バタフライ演算部における演算結果と外部からの桁あふれ予測値とに基づいて桁あふれ予測値を出力する。また、一つのバタフライ演算部群においては、一つめのバタフライ演算部から、順次、次のバタフライ演算部に対して桁あふれ予測値を出力する。また、バタフライ演算部群におけるＮ／２個目のバタフライ演算部からの桁あふれ予測値を、次の段のバタフライ演算部群におけるバタフライ演算部それぞれにおけるビットシフトのための制御信号として出力する。また、１段目のバタフライ演算部群からｌｏｇ２Ｎ−１段目のバタフライ演算部群までのバタフライ演算部群におけるＮ／２個目のバタフライ演算部からの桁あふれ予測値を加算した結果に基づいて、正規化部のビットシフト量を決める。
【００４１】
また、各バタフライ演算部は、ビットシフト部と、データを加算する加算器及び加算結果に係数を乗算する乗算器とを含む演算回路と、位相係数アドレスの値より前記係数を生成する係数発生部とを有する。更に、入力された桁あふれ予測値と、演算回路の演算結果とから、新たな桁あふれ予測値を出力する桁あふれ予測部とを有する。
【００４２】
また、データ処理装置は、前段のバタフライ演算部群の演算結果を、高速フーリエ演算を満足するように、後段のバタフライ演算部群のバタフライ演算部に出力するデータ移動部を備える。また、入力データとしては音声データが入力される。また、正規化部では、加算した結果の値がＭである場合に、Ｍビットのビットシフトを行う。
【００４３】
次に、第２の実施形態について説明する。図５はこの発明の第２の実施形態に係るデータ処理装置の構成を示す図である。本実施形態においても、データ処理装置は、Ｎこのデータを入力し、高速フーリエ変換処理を行う。図５において、バタフライ演算部３００は図１、図２と同じ構成を備える。レジスタ部３０１は、バタフライ演算部３００の入力端子１０１に入力する桁あふれ予測値を保持する。レジスタ部３０２、３０３は、バタフライ演算部３００の入力端子１０２、１０３に入力する入力データ、例えば４８ＫＨｚでサンプリングされた１６ビット長の音声データ等を保持する。レジスタ部３０４は、バタフライ演算部３００の入力端子１０４に入力するビットシフト制御信号を保持する。レジスタ部３０５は、バタフライ演算部３００の入力端子１０５に入力する位相係数アドレスｋ（ｋ＝０〜Ｎ／２−１）を保持する。レジスタ部３０６、３０７は、バタフライ演算部３００の入力端子１０６、１０７から出力されるバタフライ演算後の出力データを保持する。レジスタ部３０８は、バタフライ演算部３００の出力端子１０８から出力される桁あふれ予測値を保持する。
【００４４】
また、図５のデータ処理装置は、図５の装置の動作を制御する中央処理装置３０９、入力データを記憶する記憶部３１０、中央演算装置３０９からレジスタ部３０１−３０８へ信号を伝搬するデータメモリバス３１１を備える。
【００４５】
図１０は記憶部３１０において、入力データ列ＤＡＴＡ［ｎ］が記憶されている部分のメモリマップである。ＤＡＴＡ［ｎ］の番地は、基本アドレス値ＡＤＲ＋オフセットアドレスｎ（ｎ＝０〜Ｎ−１）で表される。
【００４６】
図５の装置の動作は、中央演算装置３０９が図６のフローチャートに従いバタフライ演算部３００を繰り返し用いて演算を行うことで実行される。図６のフローチャートについて詳細を説明する。図６のフローチャートにおいて、記号＜＜は左ビットシフトを、記号＞＞は右ビットシフトを表す。
【００４７】
処理が開始されると（ＳＴＥＰ０）、入力データ数Ｎを設定する（ＳＴＥＰ１）。このとき、Ｎは２の乗数である。第１の実施形態で説明したバタフライ演算部の段を表す変数ｓｔａｇｅ、ビットシフト制御信号を表す変数ｓｈｉｆｔ＿ｅｎ（０または１）、正規化ビットシフト量を表す変数ｎｍｌの初期値を入力する（ＳＴＥＰ２）。ここで、ｓｔａｇｅは、１段目は０、２段目は１となる。初期値としては、ｓｔａｇｅ＝０、ｓｈｉｆｔ＿ｅｎ＝０、ｎｍｌ＝０がそれぞれ設定される。
【００４８】
次に、実施形態１で説明した各段の中でバタフライ演算部を繰り返すための変数ｆｌｏｏｒ、桁あふれ予測値を表す変数ｏｖｆｌ＿ｄｅｔ（０または１）の初期値を入力する（ＳＴＥＰ３）。初期値としては、ｆｌｏｏｒ＝０、ｏｖｆｌ＿ｄｅｔ＝０が設定される。
【００４９】
次に、位相係数アドレスｋの初期値０を入力する。また、入力データ列のオフセットアドレスを表す変数ａｄｒ１、ａｄｒ２を以下のように計算する（ＳＴＥＰ４）。
ａｄｒ１＝ｆｌｏｏｒ＊（Ｎ＞＞ｓｔａｇｅ）
ａｄｒ２＝ａｄｒ１＋（Ｎ＞＞（ｓｔａｇｅ＋１））
桁あふれ予測値をレジスタ部３０１に記憶する。また、記憶部３１０に記憶されている入力データ系列ＤＡＴＡ［ａｄｒ１］、ＤＡＴＡ［ａｄｒ２］をレジスタ部３０２、３０３に記憶する。また、ビットシフト制御信号ｓｈｉｆｔ＿ｅｎをレジスタ部３０４に記憶する。また、位相係数アドレスｋをレジスタ部３０５に記憶する（ＳＴＥＰ５）。
【００５０】
次に、バタフライ演算部３００への全ての入力信号が、ＳＴＥＰ５でレジスタ部３０１−３０５に記憶される。レジスタ部３０１−３０５に記憶された値は、バタフライ演算部３００の入力端子１０１−１０５にロードされ、バタフライ演算部３００において演算が行われる（ＳＴＥＰ６）。演算後の結果がバタフライ演算部３００の出力端子１０６−１０８から出力され、レジスタ部３０６−３０８に記憶される。
【００５１】
次に、レジスタ部３０６−３０８に記憶されている値がそれぞれＤＡＴＡ［ａｄｒ１］、ＤＡＴＡ［ａｄｒ２］、ｏｖｆｌ＿ｄｅｔに書き戻される（ＳＴＥＰ７）。
【００５２】
次に、以下の条件式１がＹＥＳならばＳＴＥＰ１３へ、ＮＯならばＳＴＥＰ９へ進む（ＳＴＥＰ８）。
条件式１  ａｄｒ１≦（２＊ｆｌｏｏｒ）＊（Ｎ＞＞（１＋ｓｔａｇｅ））
また、条件式２がＹＥＳならばＳＴＥＰ１６へ、ＮＯならばＳＴＥＰ１０へ進む（ＳＴＥＰ９）。
条件式２  ｆｌｏｏｒ＜（１＜＜ｓｔａｇｅ）
また、以下の条件式３がＹＥＳならばＳＴＥＰ１７へ、ＮＯならばＳＴＥＰ１１へ進む（ＳＴＥＰ１０）。
条件式３  ｓｔａｇｅ＜ｌｏｇ２Ｎ
次に、全ての演算結果（ＤＡＴＡ［０〜Ｎ−１］）に対して正規化ビットシフトを行う（ＳＴＥＰ１１）。
【００５３】
また、ＳＴＥＰ１３では、オフセットアドレスａｄｒ１、ａｄｒ２と位相係数アドレスｋを更新する。次に、以下の条件式４がＹＥＳならばＳＴＥＰ５へ、ＮＯならばＳＴＥＰ１５へ進む（ＳＴＥＰ１４）。
条件式４  ｋ＜（Ｎ＞＞（ｓｔａｇｅ＋１））
次に、ＳＴＥＰ１５では、位相係数アドレスｋを更新し、ＳＴＥＰ５へ進む（ＳＴＥＰ１５）。
【００５４】
また、ＳＴＥＰ１６では、変数ｆｌｏｏｒを更新してＳＴＥＰ４へ進む。また、ＳＴＥＰ１７では、変数ｓｔａｇｅを更新する。また、桁あふれ予測値ｏｖｆｌ＿ｄｅｔをビットシフト制後信号ｓｈｉｆｔ＿ｅｎに格納する。また、正規化ビットシフト量ｎｍｌを更新する。
【００５５】
このような処理に従い、バタフライ演算部３００を繰り返し用いることにより、Ｎ個の入力データに対して高速フーリエ変換処理を行う。このように、桁あふれ予測値を、バタフライ演算毎のループＳＴＥＰ５〜ＳＴＥＰ８ではなく、バタフライ演算部群１段毎のループＳＴＥＰ３〜ＳＴＥＰ１６で記憶する。そのため、桁あふれ予測値を記憶するための記憶部のメモリ容量を削減することができる。
【００５６】
また、本実施形態では、従来のようにバタフライ演算毎に桁あふれ予測値を記憶せず、バタフライ演算Ｎ／２個毎に桁あふれ予測値をビットシフト制御信号とする。そのため、その分の記憶、及びロードの処理負荷も削減することができ、結果として演算速度が向上する。
【図１】
2016081356.tif 000003
【図２】
2016081356.tif 000004
【図３】
2016081356.tif 000005
【図４】
2016081356.tif 000006
【図５】
2016081356.tif 000007
【図６】
2016081356.tif 000008
【図７】
2016081356.tif 000009
【図８】
2016081356.tif 000010
【図９】
2016081356.tif 000011
【図１０】
2016081356.tif 000012