(57)【要約】【課題】ＦＦＴ（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）演算回路による余計な電力消費を削減できるようにする。【解決手段】ステージ演算部１１０は、入力データ１０１に対してフーリエ変換のステージ演算を所定のステージ回数実行し、ステージ演算を実行する毎に演算結果データ１０２を算出する。停止判定部１５０は、ステージ演算毎に、演算結果データ１０２に基づいて最終ステージ後の演算結果データ１０２の最大値（最終ステージ最大値）を予測する。停止判定部１５０は、ステージ演算毎に、最終ステージ最大値が最小値情報１０９の値より小さいか否かを判定する。最終ステージ最大値が最小値情報１０９の値より小さい場合、停止判定部１５０は停止信号１０５を出力し、ステージ演算部１１０とＲＡＭ部１２０との動作を停止させる。停止信号１０５が出力された場合、クリップ部１６０は、所定の出力値「ゼロ」を出力データ１０６として出力する。【選択図】図２
2014002588.tif 000002
【特許請求の範囲】
【請求項１】
所定の値として最小指標値を記憶する最小指標値記憶部と、
入力値が入力される入力部と、
前記入力部に入力された入力値を用いてフーリエ変換のステージ演算を所定のステージ回数実行し、フーリエ変換のステージ演算を実行する毎に演算値を算出すると共に算出した演算値を演算値記憶部に記憶するステージ演算部と、
前記ステージ演算部がフーリエ変換のステージ演算を実行する毎に、前記ステージ演算部によって算出された演算値に基づいて、前記ステージ演算部がフーリエ変換のステージ演算を前記所定のステージ回数実行した場合に算出する演算値の範囲を予測して予測指標値を算出する予測指標値算出部と、
前記ステージ演算部がフーリエ変換のステージ演算を実行する毎に、前記予測指標値算出部によって算出された予測指標値と前記最小指標値記憶部に記憶された最小指標値との関係により前記ステージ演算の停止を判定する予測指標値判定部と、
前記予測指標値判定部の判定結果が前記ステージ演算の停止を示す場合、前記ステージ演算部と前記演算値記憶部との少なくともいずれかを停止させるステージ演算停止部と
を備えることを特徴とするフーリエ変換回路。
【請求項２】
前記フーリエ変換回路は、さらに、
前記予測指標値判定部の判定結果が前記ステージ演算の停止を示す場合、予め決められた出力値を出力する演算結果出力部を備える
ことを特徴とする請求項１記載のフーリエ変換回路。
【請求項３】
前記演算結果出力部は前記出力値としてゼロを出力することを特徴とする請求項２記載のフーリエ変換回路。
【請求項４】
前記予測指標値算出部は、前記ステージ演算部がフーリエ変換のステージ演算を実行した実行回数を前記所定のステージ回数から差し引いた値に相当する残りステージ数と前記ステージ演算部によって算出された演算値とに基づいて前記予測指標値を算出する
ことを特徴とする請求項１から請求項３いずれかに記載のフーリエ変換回路。
【請求項５】
前記フーリエ変換回路は、さらに、ステージ回数と演算値の予測増加量とを対応付けた予測増加量記憶部を備え、
前記予測指標値算出部は、前記残りステージ数と同じステージ回数に対応付けられた演算値の予測増加量を前記予測増加量記憶部から取得し、取得した演算値の予測増加量と前記ステージ演算部によって算出された演算値とに基づいて前記予測指標値を算出する
ことを特徴とする請求項４記載のフーリエ変換回路。
【請求項６】
前記予測増加量記憶部は、前記演算値の予測増加量として増加桁数を記憶し、
前記予測指標値算出部は、前記残りステージ数と同じステージ回数に対応付けられた増加桁数と前記演算値の桁数とに基づいて予測桁数を前記予測指標値として算出する
ことを特徴とする請求項５記載のフーリエ変換回路。
【請求項７】
前記予測増加量記憶部は、１＋√２（√２は２の平方根）をステージ回数だけ累乗した値について、２を底とする対数値の小数点以下を切り上げた値を前記予測増加量として記憶する
ことを特徴とする請求項５または請求項６記載のフーリエ変換回路。
【請求項８】
前記ステージ演算部は、前記予測指標値と前記最小指標値とが所定の大小関係を示す場合に前記ステージ演算を停止させると判定する
ことを特徴とする請求項１から請求項７いずれかに記載のフーリエ変換回路。
【請求項９】
前記ステージ演算部は、基数２のバタフライ演算を行う
ことを特徴とする請求項１から請求項８いずれかに記載のフーリエ変換回路。
【請求項１０】
請求項１から請求項９いずれかに記載のフーリエ変換回路を備えた情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フーリエ変換回路、情報処理装置、フーリエ変換方法およびフーリエ変換プログラムに関するものである。
【背景技術】
【０００２】
従来のＦＦＴ（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）演算回路は、例えば特許文献１に開示されている。
特許文献１が開示する技術は、下位ビットの切り捨てによる演算精度の劣化を抑えるために、バタフライ演算の入力系列の最大値に基づいてバタフライ演算の出力系列をビットシフトし、バタフライ演算のループの最終回において逆のビットシフトを行う、というものである。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−２８８１５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来のＦＦＴ演算回路を様々なシステムに適用する場合、システムによって必要な最小分解能が異なるため、例えばシステムが必要とする最小分解能がＦＦＴ演算回路が演算可能な最小分解能より低い場合も発生することが考えられる。
しかし、従来のＦＦＴ演算回路では、システムの最小分解能において演算結果が全ての０になる場合であっても最終ステージまで演算し続けるため余計な電力を消費してしまう、という課題があった。
【０００５】
本発明は、上記のような課題を解決するためになされたもので、余計な電力消費を削減するＦＦＴ演算回路を実現することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のフーリエ変換回路は、
所定の値として最小指標値を記憶する最小指標値記憶部と、
入力値が入力される入力部と、
前記入力部に入力された入力値を用いてフーリエ変換のステージ演算を所定のステージ回数実行し、フーリエ変換のステージ演算を実行する毎に演算値を算出すると共に算出した演算値を演算値記憶部に記憶するステージ演算部と、
前記ステージ演算部がフーリエ変換のステージ演算を実行する毎に、前記ステージ演算部によって算出された演算値に基づいて、前記ステージ演算部がフーリエ変換のステージ演算を前記所定のステージ回数実行した場合に算出する演算値の範囲を予測して予測指標値を算出する予測指標値算出部と、
前記ステージ演算部がフーリエ変換のステージ演算を実行する毎に、前記予測指標値算出部によって算出された予測指標値と前記最小指標値記憶部に記憶された最小指標値との関係により前記ステージ演算の停止を判定する予測指標値判定部と、
前記予測指標値判定部の判定結果が前記ステージ演算の停止を示す場合、前記ステージ演算部と前記演算値記憶部との少なくともいずれかを停止させるステージ演算停止部とを備える。
【発明の効果】
【０００７】
本発明によれば、例えば、ＦＦＴ演算回路による余計な電力消費を削減することができる。
【図面の簡単な説明】
【０００８】
【図１】実施の形態１における情報処理装置２００の構成図。
【図２】実施の形態１におけるＦＦＴ演算回路１００の機能構成図。
【図３】実施の形態１における停止判定部１５０の機能構成図。
【図４】実施の形態１におけるＦＦＴ演算回路１００のＦＦＴ演算処理を示すフローチャート。
【図５】実施の形態１における停止判定処理（Ｓ１４０）を示すフローチャート。
【図６】実施の形態１における増加ビット数テーブル１０７を示す図。
【図７】実施の形態１における情報処理装置２００のハードウェア資源の一例を示す図。
【発明を実施するための形態】
【０００９】
実施の形態１．
ＦＦＴ（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）演算回路による余計な電力消費を削減する形態について説明する。
【００１０】
図１は、実施の形態１における情報処理装置２００の構成図である。
実施の形態１における情報処理装置２００の構成について、図１に基づいて説明する。
【００１１】
情報処理装置２００は、高速フーリエ変換演算または高速逆フーリエ変換演算（以下、「フーリエ変換」または「ＦＦＴ」という）を含んだ情報処理を実行する装置である。情報処理の種類は問わない。
【００１２】
情報処理装置２００は、情報処理部２１０、フーリエ変換部２２０およびＦＦＴ演算回路１００（フーリエ変換回路の一例）を備える。
情報処理部２１０は、何らかの情報処理を実行するための機能構成である。フーリエ変換を実行する必要がある場合、情報処理部２１０は、フーリエ変換の入力データ（複数の入力値）をフーリエ変換部２２０に出力し、フーリエ変換部２２０から出力されるフーリエ変換の出力データ（複数の出力値）を入力する。
フーリエ変換部２２０は、フーリエ変換を実行するための機能構成である。フーリエ変換部２２０は、情報処理部２１０から出力された入力系列に対するフーリエ変換をＦＦＴ演算回路１００を用いて実行し、ＦＦＴ演算回路１００を用いて得られたフーリエ変換の出力系列を情報処理部２１０に出力する。
ＦＦＴ演算回路１００は、フーリエ変換を実行する電子回路である。ＦＦＴ演算回路１００の詳細については別途説明する。
【００１３】
情報処理部２１０によって処理することが可能な数値の範囲は、ハードウェアまたはソフトウェアによって制限されている。
ＦＦＴ演算回路１００の演算結果が情報処理部２１０によって処理することが可能な最小値（例えば「２−３」）より小さな値（例えば「２−４」）である場合、情報処理部２１０は、演算結果が「０」であるものとして情報処理を行うものとする。
以下、情報処理部２１０によって処理することが可能な最小値（最小分解能）（以下、「システム最小値」という）に関する情報を「最小値情報」という。
【００１４】
図２は、実施の形態１におけるＦＦＴ演算回路１００の機能構成図である。
実施の形態１におけるＦＦＴ演算回路１００の機能構成について、図２に基づいて説明する。
【００１５】
ＦＦＴ演算回路１００（フーリエ変換回路の一例）は、ステージ演算部１１０（ステージ演算部の一例）と、ＲＡＭ部１２０（入力部、演算値記憶部の一例）と、最大桁検出部１３０と、シフト制御部１４０とを備える。
ＦＦＴ演算回路１００は、さらに、停止判定部１５０（最小指標値記憶部、予測指標値算出部、予測指標値判定部、ステージ演算停止部、予測増加量記憶部の一例）と、クリップ部１６０（演算結果出力部の一例）とを備える。
【００１６】
ＲＡＭ部１２０（ＲＡＭ：Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）は、ＦＦＴ演算回路１００に入力される入力データ１０１（入力系列ともいう）を記憶する。入力データ１０１は複数の入力値を含む。
また、ＲＡＭ部１２０は、ステージ演算部１１０から出力される演算結果データ１０２を記憶する。演算結果データ１０２は複数の演算値を含む。
【００１７】
ステージ演算部１１０は、ＲＡＭ部１２０から入力データ１０１または前回の演算結果データ１０２を読み込む。
ステージ演算部１１０は、読み込んだデータに対してフーリエ変換のステージ演算を実行し、ステージ演算の演算結果データ１０２を出力する。このとき、ステージ演算部１１０は、後述する前回のシフト制御情報１０４に応じて各演算値のビットシフトを行う。
【００１８】
最大桁検出部１３０は、ステージ演算部１１０から出力される演算結果データ１０２を入力し、入力した演算結果データ１０２に含まれる複数の演算値それぞれの絶対値の桁数を算出し、算出した桁数のうち最大の桁数を演算結果データ１０２の最大桁１０３として出力する。なお、最大桁の算出は、演算値の絶対値の最大値を算出してから、その桁数を最大桁としてもよい。
【００１９】
シフト制御部１４０は、最大桁検出部１３０から出力される最大桁１０３を入力し、入力した最大桁１０３に基づいて次のステージのシフト制御情報１０４を生成し、生成したシフト制御情報１０４を出力する。
シフト制御情報１０４は、演算値のビット列をシフトするシフト数（以下、「シフトビット数」という）に関する情報を示す。
【００２０】
停止判定部１５０は、最大桁検出部１３０から出力される最大桁１０３、シフト制御部１４０から出力されるシフト制御情報１０４およびＦＦＴ演算回路１００に入力される最小値情報１０９に基づいて、ステージ演算部１１０のステージ演算を停止するか否かを判定する。
ステージ演算部１１０のステージ演算を停止する場合、停止判定部１５０は、停止信号１０５を出力する。
【００２１】
クリップ部１６０は、所定のステージ数だけステージ演算を実行したステージ演算部１１０から出力される演算結果データ１０２を入力する。クリップ部１６０は、入力した演算結果データ１０２を後述するステージ指数（図示省略）に基づいたシフトを行ってから出力データ１０６として出力する。
但し、停止判定部１５０から停止信号１０５が出力された場合、クリップ部１６０は、所定の出力値「０（ゼロ）」を出力データ１０６として出力する。この場合、クリップ部１６０は、情報処理装置２００が出力データ１０６を受け取ることができるように、出力データ１０６の出力タイミングを必要に応じて調整する。
【００２２】
図３は、実施の形態１における停止判定部１５０の機能構成図である。
実施の形態１における停止判定部１５０の機能構成について、図３に基づいて説明する。
【００２３】
停止判定部１５０は、残ステージカウンタ部１５１、増加ビット算出部１５２（予測増加量記憶部の一例）、ステージ指数管理部１５３、最終値予測部１５４（予測指標値算出部の一例）および比較判定部１５５（最小指標値記憶部、予測指標値判定部、ステージ演算停止部の一例）を備える。
【００２４】
残ステージカウンタ部１５１は、ステージ演算部１１０によるステージ演算の実行回数を所定のステージ数から差し引いた値、を残りステージ数として算出する。
【００２５】
増加ビット算出部１５２は、残ステージカウンタ部１５１によって算出された残りステージ数に基づいて、ステージ演算部１１０が所定のステージ数のステージ演算を実行した場合の演算量の増加し得るビット数を算出する。
以下、増加ビット算出部１５２によって算出されるビット数を「増加ビット数」という。
【００２６】
ステージ指数管理部１５３は、シフト制御情報１０４を入力し、入力したシフト制御情報１０４が示すシフトビット数に基づいて演算値の指数値を算出する。
以下、ステージ指数管理部１５３によって算出される指数値を「ステージ指数」という。
【００２７】
最終値予測部１５４は、最大桁１０３を入力し、入力した最大桁１０３と増加ビット算出部１５２によって算出された増加ビット数とステージ指数管理部１５３によって算出されたステージ指数とに基づいて最終ステージ最大値を算出する。
最終ステージ最大値は、ステージ演算部１１０が所定のステージ数のステージ演算を実行した場合に算出される演算値の最大値に関する値である。
【００２８】
比較判定部１５５は、最小値情報１０９を入力し、入力した最小値情報１０９が表すシステム最小値と最終値予測部１５４によって算出された最終ステージ最大値とを比較し、比較結果に基づいてステージ演算を停止するか否かを判定する。
ステージ演算を停止する場合、比較判定部１５５は、停止信号１０５を出力する。
【００２９】
図４は、実施の形態１におけるＦＦＴ演算回路１００のＦＦＴ演算処理を示すフローチャートである。
実施の形態１におけるＦＦＴ演算回路１００のＦＦＴ演算処理（フーリエ変換方法の一例）について、図４に基づいて説明する。
【００３０】
Ｓ１０１において、ＲＡＭ部１２０は、ＦＦＴ演算回路１００に入力された入力データ１０１を記憶する。入力データ１０１は複数の入力値を含む。
Ｓ１０１の後、Ｓ１０２に進む。
【００３１】
Ｓ１０２において、ステージ演算部１１０は、ＲＡＭ部１２０から入力データ１０１を読み込む。
ステージ演算部１１０は、読み込んだ入力データ１０１に含まれる複数の入力値を用いてフーリエ変換のステージ演算を実行して複数の演算値を算出し、算出した複数の演算値を含んだ演算結果データ１０２を出力する。
ＲＡＭ部１２０は、ステージ演算部１１０から出力された演算結果データ１０２を記憶する。
【００３２】
例えば、ステージ演算部１１０は、「２」を基数とするバタフライ演算（以下、「基数「２」のバタフライ演算」という）を行う。
Ｓ１０２の後、Ｓ１１０に進む。
【００３３】
Ｓ１１０において、最大桁検出部１３０は、ステージ演算部１１０から出力された演算結果データ１０２を入力する。
最大桁検出部１３０は、演算結果データ１０２に含まれる複数の演算値それぞれの絶対値の桁数を算出し、算出した桁数のうち最大の桁数を演算結果データ１０２の最大桁１０３として出力する。なお、最大桁の算出は、演算値の絶対値の最大値を算出してから、その桁数を最大桁としてもよい。
例えば、絶対値が最も大きい演算値が「７」である場合、演算値「７」は２進数表現では３ビットの値「１１１」であるため、２進数表現における最大桁１０３は「３」である。
Ｓ１１０の後、Ｓ１２０に進む。
【００３４】
Ｓ１２０において、シフト制御部１４０は、最大桁検出部１３０から出力された最大桁１０３を入力し、入力した最大桁１０３に基づいてシフトビット数を算出する。例えば、シフト制御部１４０は、次回のステージ演算で桁あふれが発生しないようなシフトビット数を算出する。最大桁１０３に基づいてシフトビット数を算出する方法は、例えば、特許文献１に開示されている。
シフト制御部１４０は、算出したシフトビット数を示すシフト制御情報１０４を生成し、生成したシフト制御情報１０４を出力する。
Ｓ１２０の後、Ｓ１３０に進む。
【００３５】
Ｓ１３０において、停止判定部１５０は、最大桁検出部１３０から出力された最大桁１０３を入力する。
停止判定部１５０は、最大桁１０３と最小値情報１０９とに基づいてステージ演算を停止するか否かを判定する。
最小値情報１０９はＦＦＴ演算回路１００に入力され、停止判定部１５０はＦＦＴ演算回路１００に入力された最小値情報１０９を予め記憶しておくものとする。
ステージ演算を停止する場合、停止判定部１５０は停止信号１０５を出力する。
停止判定処理（Ｓ１３０）の詳細については、別途説明する。
Ｓ１３０の後、Ｓ１４０に進む。
【００３６】
Ｓ１４０において、クリップ部１６０は、停止判定部１５０から停止信号１０５が出力されたか否かを判定する。
停止信号１０５が出力された場合（ＹＥＳ）、Ｓ１７０に進む。
停止信号１０５が出力されなかった場合（ＮＯ）、Ｓ１５０に進む。
【００３７】
Ｓ１５０において、クリップ部１６０は、ステージ演算部１１０が所定のステージ数のステージ演算を実行したか否かを判定する。
例えば、クリップ部１６０は、ステージ演算部１１０が演算結果データ１０２を出力した回数をカウントし、カウントした回数を所定のステージ数と比較する。カウントした回数が所定のステージ演算と同じ値である場合、ステージ演算部１１０は所定のステージ数のステージ演算を実行したことになる。
所定のステージ数は、実行するＦＦＴ点数に応じて定められる。所定のステージ数は予め記憶してもよいし、実行するＦＦＴ点数に応じて算出してもよい。
ステージ演算部１１０が所定のステージ数のステージ演算を実行したか否かの判定は、クリップ部１６０の代わりに停止判定部１５０が行ってもよい。
ステージ演算部１１０が所定のステージ数のステージ演算を実行した場合（ＹＥＳ）、Ｓ１８０に進む。
ステージ演算部１１０が所定のステージ数のステージ演算を実行していない場合（ＮＯ）、Ｓ１６０に進む。
【００３８】
Ｓ１６０において、ステージ演算部１１０は、ＲＡＭ部１２０から演算結果データ１０２を読み込む。
ステージ演算部１１０は、読み込んだ演算結果データ１０２に含まれる複数の演算値を用いてフーリエ変換のステージ演算（Ｓ１０２参照）を実行して新たな複数の演算値を算出し、算出した新たな複数の演算値を含んだ演算結果データ１０２を出力する。
ＲＡＭ部１２０は、ステージ演算部１１０から出力された演算結果データ１０２を記憶する。
Ｓ１６０の後、Ｓ１１０に戻る。
【００３９】
Ｓ１７０において、ステージ演算部１１０およびＲＡＭ部１２０は動作を停止する。つまり、ステージ演算部１１０は、所定のステージ数のステージ演算を実行していない場合であってもステージ演算の実行を終了し、以降の残りのステージ演算を実行しない。但し、ステージ演算部１１０とＲＡＭ部１２０とのいずれか一方だけが停止してもよい。また、ＲＡＭ部が複数のＲＡＭを備えている場合、一部のＲＡＭだけが動作を停止してもよい。
クリップ部１６０は、全ての出力値が「０（ゼロ）」である出力データ１０６を出力する。
Ｓ１７０により、ＦＦＴ演算処理は終了する。
【００４０】
Ｓ１８０において、クリップ部１６０は、ステージ演算部１１０から最後に出力された演算結果データ１０２（所定のステージ数のステージ演算が実行されたときの演算結果データ１０２）に対して停止判定部１５０によって最後に算出されたステージ指数に基づいたシフトを行い、シフトした演算結果データ１０２を出力データ１０６として出力する。
Ｓ１８０により、ＦＦＴ演算処理は終了する。
【００４１】
図５は、実施の形態１における停止判定処理（Ｓ１３０）を示すフローチャートである。
実施の形態１における停止判定処理（Ｓ１３０）について、図５に基づいて説明する。
【００４２】
Ｓ１３１において、残ステージカウンタ部１５１は、ステージ演算部１１０によるステージ演算の実行回数を所定のステージ数から差し引いた値、を残りステージ数として算出する。
残ステージカウンタ部１５１は、クリップ部１６０と同様に、所定のステージ数を算出してもよいし、予め記憶してもよい（図４のＳ１５０参照）。
残りステージ数は、所定のステージ数からステージ演算毎に１減ずることで算出してもよい。
Ｓ１３１の後、Ｓ１３２に進む。
【００４３】
Ｓ１３２において、増加ビット算出部１５２は、Ｓ１３１で算出された残りステージ数に対応する増加ビット数を増加ビット数テーブル１０７から取得する。
【００４４】
図６は、実施の形態１における増加ビット数テーブル１０７を示す図である。
増加ビット数テーブル１０７は、残りステージ数と増加ビット数とを対応付けたデータである。
【００４５】
増加ビット数は、残りステージ数に基づいて算出される値である。
例として基数「２」のバタフライ演算を行う場合の増加ビット数の算出例を示す。
【００４６】
まず、基数「２」のバタフライ演算の演算式（１）を示す。式（１）で使用している符号の意味は以下の通りである。
「Ｘ’」「Ｙ’」は、バタフライ演算の出力値（演算値）である。
「Ｘ」「Ｙ」は、バタフライ演算の入力値（または演算値）である。
「Ｎ」は、ＦＦＴの点数である。
「ｋ」は、０から（（Ｎ／２）−１）の整数である。例えば、「Ｎ＝１６」の場合、「ｋ＝０，１，・・・，７」である。
【００４７】
【数１】
2014002588.tif 000003
【００４８】
上記の式（１）の出力値「Ｘ’」「Ｙ’」は実数成分「Ｘ’Ｒ」「Ｙ’Ｒ」と虚数成分「Ｘ’Ｉ」「Ｙ’Ｉ」とを用いて以下の式（２）で表すことができる。
式（２）において「ｊ」は虚数単位である。また、「ＸＲ」「ＹＲ」は入力値の実数成分であり、「ＸＩ」「ＹＩ」は入力値の虚数成分である。
【００４９】
【数２】
2014002588.tif 000004
【００５０】
１回のステージ演算で算出される出力値「Ｘ’」「Ｙ’」（上記式（２）参照）の範囲は、上記式（２ａ）より、ステージ演算の入力値の範囲の（１＋√２）倍と計算できる。「√２」は２の平方根を意味する。
増加ビット数は、（１＋√２）を残りステージ数ｎだけ累乗して（１＋√２）ｎを算出し、「２」を底にした（１＋√２）ｎの対数値「ｌｏｇ２（（１＋√２）ｎ）」を算出し、算出した対数値の小数点以下を切り上げて算出される。
【００５１】
例えば、残りステージ数が「３」である場合、増加ビット数は「４」である（以下の式（３）参照）。
ｃｅｉｌｉｎｇ（Ｘ）はＸの切り上げを意味する。
【００５２】
【数３】
2014002588.tif 000005
【００５３】
増加ビット算出部１５２は、図６に示すような増加ビット数テーブル１０７を記憶する代わりに、増加ビット数を演算で算出してもよい。
【００５４】
図５に戻り、停止判定処理（Ｓ１３０）の説明を続ける。
Ｓ１３２の後、Ｓ１３３に進む。
【００５５】
Ｓ１３３において、最終値予測部１５４は、最大桁１０３を入力し、最大桁１０３と増加ビット数とステージ指数とを用いて最終ステージ最大値を算出する。
最終ステージ最大値Ｍは、例えば「Ｍ＝Ｂ＋ｒ＋Ｃ」で算出する。ここで、「Ｂ」は増加ビット数であり、「ｒ」は最大桁１０３であり、「Ｃ」はステージ指数である。
例えば、増加ビット数Ｂが「４」、最大桁ｒが「２」、ステージ指数Ｃが「−１０」である場合、最終ステージ最大値Ｍは「４（＝４＋２＋（−１０））」となる。
Ｓ１３３の後、Ｓ１３４に進む。
【００５６】
Ｓ１３４において、比較判定部１５５は、最小値情報１０９を入力し、入力した最小値情報１０９が示す値ｍとＳ１４４で算出された最終ステージ最大値Ｍとを比較する。
最小値情報１０９は例えばシステム最小値Ｔに対して「Ｔ＝２ｍ」を満たす値ｍ、つまり、「２」を底とするシステム最小値Ｔの指数値ｍとする。
最終ステージ最大値Ｍが最小値情報１０９の値ｍ以上である場合（ＹＥＳ）、Ｓ１３６に進む。
最終ステージ最大値Ｍが最小値情報１０９の値ｍより小さい場合（ＮＯ）、Ｓ１３５に進む。
【００５７】
Ｓ１３５において、比較判定部１５５は停止信号１０５を出力する。
Ｓ１３５の後、Ｓ１３６に進む。
【００５８】
Ｓ１３６において、ステージ指数管理部１５３は、シフト制御情報１０４を入力し、入力したシフト制御情報１０４が示すシフトビット数に基づいて演算値の指数値（ステージ指数）を算出する。
ステージ指数Ｃは、Ｖ’を演算値の真の値、ＶをＲＡＭ部に格納する値とし、例えば「Ｖ’＝Ｖ＊２Ｃ」で表される数とする。
Ｓ１３６により、停止判定処理（Ｓ１３０）は終了する。
【００５９】
図４および図５においてＦＦＴ演算処理を便宜上、フローチャートの形式で説明したが、各要素の処理タイミングは図４および図５に示したような逐次処理に限定されるものではなく，適宜並列処理を行ってもよい。
【００６０】
ＦＦＴ演算回路１００は、図４および図５に基づいて説明したＦＦＴ演算処理により、途中のステージ演算で以降のステージ演算が不要であること（最終ステージ最大値Ｍ＜最小値情報１０９の値ｍ）を検出し、ステージ演算を停止することができる。
これにより、不要なステージ演算が省略され、消費電力の削減および処理時間の短縮を図ることができる。
【００６１】
図７は、実施の形態１における情報処理装置２００のハードウェア資源の一例を示す図である。
図７において、情報処理装置２００（コンピュータの一例）は、ＣＰＵ９０１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備えている。ＣＰＵ９０１は、バス９０２を介してＲＯＭ９０３、ＲＡＭ９０４、通信ボード９０５（通信装置）、ディスプレイ９１１（表示装置）、キーボード９１２、マウス９１３、ドライブ９１４、磁気ディスク装置９２０などのハードウェアデバイスと接続され、これらのハードウェアデバイスを制御する。ドライブ９１４は、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）などの記憶媒体を読み書きする装置である。
ＲＯＭ９０３、ＲＡＭ９０４、磁気ディスク装置９２０およびドライブ９１４は記憶装置の一例である。キーボード９１２、マウス９１３および通信ボード９０５は入力装置の一例である。ディスプレイ９１１および通信ボード９０５は出力装置の一例である。
【００６２】
通信ボード９０５は、有線または無線で、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、電話回線などの通信網に接続している。
【００６３】
磁気ディスク装置９２０には、ＯＳ９２１（オペレーティングシステム）、プログラム群９２２、ファイル群９２３が記憶されている。
【００６４】
プログラム群９２２には、実施の形態において「〜部」として説明する機能を実行するプログラムが含まれる。プログラム（例えば、フーリエ変換プログラム）は、ＣＰＵ９０１により読み出され実行される。すなわち、プログラムは、「〜部」としてコンピュータを機能させるものであり、また「〜部」の手順や方法をコンピュータに実行させるものである。
【００６５】
ファイル群９２３には、実施の形態において説明する「〜部」で使用される各種データ（入力、出力、判定結果、計算結果、処理結果など）が含まれる。
【００６６】
実施の形態において構成図およびフローチャートに含まれている矢印は主としてデータや信号の入出力を示す。
フローチャートなどに基づいて説明する実施の形態の処理はＣＰＵ９０１、記憶装置、入力装置、出力装置などのハードウェアを用いて実行される。
【００６７】
実施の形態において「〜部」として説明するものは「〜回路」、「〜装置」、「〜機器」であってもよく、また「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ファームウェア、ソフトウェア、ハードウェアまたはこれらの組み合わせのいずれで実装されても構わない。
【００６８】
ＦＦＴ演算回路１００は本実施の形態で説明したものに限らない。
例えば、クリップ部１６０にてシフトを行う際に丸めを行う場合は、クリップ部１６０における丸めによる桁上りの影響を加味し、例えば最終ステージ最大値Ｍを「Ｍ＝Ｂ＋ｒ＋Ｃ＋１」で算出して判定を行ってもよい。
また、本実施の形態では基数２の場合の判定の例を記載したが、基数が２以外のバタフライ演算を行う場合も同様に１ステージの範囲増加分を残りステージ数で累乗することで同様の判定を行うことができる。またクリップ部１６０は、停止信号１０５が出力された場合に「０」以外の値（例えば、システム最小値）を出力しても構わない。
【００６９】
実施の形態１において、例えば、以下のようなフーリエ変換回路（ＦＦＴ演算回路１００）について説明した。括弧内に実施の形態１で用いた要素名を記す。
フーリエ変換回路は、最小指標値記憶部（比較判定部１５５）と、入力部（ＲＡＭ部１２０）と、ステージ演算部（ステージ演算部１１０）と、予測指標値算出部（最終値予測部１５４）と、予測指標値判定部（比較判定部１５５）と、ステージ演算停止部（比較判定部１５５）とを備える。
最小指標値記憶部は、所定の値として最小指標値（最小値情報１０９）を記憶する。
入力部は、入力値（入力データ１０１）が入力される。
ステージ演算部は、前記入力部に入力された入力値を用いてフーリエ変換のステージ演算を所定のステージ回数実行し、フーリエ変換のステージ演算を実行する毎に演算値（演算結果データ１０２）を算出すると共に算出した演算値を演算値記憶部（ＲＡＭ部１２０）に記憶する。
予測指標値算出部は、前記ステージ演算部がフーリエ変換のステージ演算を実行する毎に、前記ステージ演算部によって算出された演算値に基づいて、前記ステージ演算部がフーリエ変換のステージ演算を前記所定のステージ回数実行した場合に算出する演算値の範囲を予測して予測指標値（最終ステージ最大値）を算出する。
予測指標値判定部は、前記ステージ演算部がフーリエ変換のステージ演算を実行する毎に、前記予測指標値算出部によって算出された予測指標値と前記最小指標値記憶部に記憶された最小指標値との関係により前記ステージ演算の停止を判定する。
ステージ演算停止部は、前記予測指標値判定部の判定結果が前記ステージ演算の停止を示す場合、前記ステージ演算部と前記演算値記憶部との少なくともいずれかを停止させる。
【符号の説明】
【００７０】
１００  ＦＦＴ演算回路、１０１  入力データ、１０２  演算結果データ、１０３  最大桁、１０４  シフト制御情報、１０５  停止信号、１０６  出力データ、１０７  増加ビット数テーブル、１０９  最小値情報、１１０  ステージ演算部、１２０  ＲＡＭ部、１３０  最大桁検出部、１４０  シフト制御部、１５０  停止判定部、１５１  残ステージカウンタ部、１５２  増加ビット算出部、１５３  ステージ指数管理部、１５４  最終値予測部、１５５  比較判定部、１６０  クリップ部、２００  情報処理装置、２１０  情報処理部、２２０  フーリエ変換部、９０１  ＣＰＵ、９０２  バス、９０３  ＲＯＭ、９０４  ＲＡＭ、９０５  通信ボード、９１１  ディスプレイ、９１２  キーボード、９１３  マウス、９１４  ドライブ、９２０  磁気ディスク装置、９２１  ＯＳ、９２２  プログラム群、９２３  ファイル群。
【図１】
2014002588.tif 000006
【図２】
2014002588.tif 000007
【図３】
2014002588.tif 000008
【図４】
2014002588.tif 000009
【図５】
2014002588.tif 000010
【図６】
2014002588.tif 000011
【図７】
2014002588.tif 000012