(57)【要約】【課題】内部バッファ量を削減できる２次元ＦＦＴ演算方法及び装置を提供する。【解決手段】２次元ＦＦＴ演算方法は、演算対象データを縦１ラインずつ順に１次元ＦＦＴ演算して第１の演算結果データを生成し、１ラインの第１の演算結果データが生成される毎に、第１の演算結果データの中の指定位置（Ｍ番目）の第２の演算対象データを内部バッファ１０３に保持させる処理を、１ラインの第２の演算対象データが内部バッファ１０３に保持されるまで実行する縦方向処理実行ステップ（ＳＴ１０２〜ＳＴ１０４）と、内部バッファ１０３に１ラインの第２の演算対象データが保持されたときに、第２の演算対象データを１次元ＦＦＴ演算して第２の演算結果データを生成する、横方向処理実行ステップ（ＳＴ１０６〜ＳＴ１０８）と、指定位置を変更（Ｍをインクリメント）して縦方向処理実行ステップ及び横方向処理実行ステップを繰り返すステップを有する。【選択図】図５
2008117044.tif 000002
【特許請求の範囲】
【請求項１】
内部バッファを有する回路によって、第１及び第２方向に２次元配列された第１の演算対象データを２次元高速フーリエ変換演算する方法であって、
前記第１の演算対象データを第１方向１ラインずつ順に１次元高速フーリエ変換演算して第１の演算結果データを生成し、第１方向１ラインの前記第１の演算結果データが生成される毎に、前記第１の演算結果データの中の指定位置のデータを第２の演算対象データとして前記内部バッファに保持させる処理を、前記第１の演算対象データ全体について実行する、第１方向処理実行ステップと、
保持された前記第２の演算対象データを第２方向１ラインずつ順に１次元高速フーリエ変換演算して第２の演算結果データを生成する、第２方向処理実行ステップと、
前記第１の演算対象データ全体について前記第２の演算結果データが生成されるまで、前記指定位置を変更して前記第１方向処理実行ステップ及び前記第２方向処理実行ステップを繰り返す、処理繰り返しステップと
を有し、
前記内部バッファに保持される前記第２の演算対象データは、第１方向に並ぶ所定数ラインのデータであり、
前記所定数は、前記第１の演算対象データの第１方向に並ぶデータの数よりも少ない値である
ことを特徴とする２次元高速フーリエ変換演算方法。
【請求項２】
前記処理繰り返しステップが終了した後に、前記第１の演算対象データを他の演算対象データに変更して、前記第１方向処理実行ステップ、前記第２方向処理実行ステップ、及び前記処理繰り返しステップを実行することを特徴とする請求項１に記載の２次元高速フーリエ変換演算方法。
【請求項３】
前記所定数は、１であることを特徴とする請求項１又は２に記載の２次元高速フーリエ変換演算方法。
【請求項４】
前記所定数は、２以上の整数であり、且つ、前記第１方向に並ぶデータの数を前記所定数で除算したときに割り切れる値であることを特徴とする請求項１又は２に記載の２次元高速フーリエ変換演算方法。
【請求項５】
前記内部バッファのバッファ量は、前記所定数ラインのデータ量の２倍以上であり、
前記第２方向処理実行ステップの実行中に、次に演算対象となる第１の演算対象データについて前記第１方向処理実行ステップを実行する
ことを特徴とする請求項２に記載の２次元高速フーリエ変換演算方法。
【請求項６】
第１及び第２方向に２次元配列された第１の演算対象データを２次元高速フーリエ変換演算する装置であって、
内部バッファと、
前記第１の演算対象データを第１方向１ラインずつ順に１次元高速フーリエ変換演算して第１の演算結果データを生成し、第１方向１ラインの前記第１の演算結果データが生成される毎に、前記第１の演算結果データの中の指定位置のデータを第２の演算対象データとして前記内部バッファに保持させる処理を、前記第１の演算対象データ全体について実行する、第１の１次元高速フーリエ変換演算回路と、
保持された前記第２の演算対象データを第２方向１ラインずつ順に１次元高速フーリエ変換演算して第２の演算結果データを生成する、第２の１次元高速フーリエ変換演算回路と
を有し、
前記第１の演算対象データ全体について前記第２の演算結果データが生成されるまで、前記指定位置を変更して前記第１の１次元高速フーリエ変換演算回路による処理及び前記第２の１次元高速フーリエ変換演算回路による処理を繰り返し、
前記内部バッファに保持される前記第２の演算対象データは、第１方向に並ぶ所定数ラインのデータであり、
前記所定数は、前記第１の演算対象データの第１方向に並ぶデータの数よりも少ない値である
ことを特徴とする２次元高速フーリエ変換演算装置。
【請求項７】
前記第１の１次元高速フーリエ変換演算回路及び前記第２の１次元高速フーリエ変換演算回路は、前記第１の演算対象データを他の演算対象データに変更して、前記処理を再度実行することを特徴とする請求項６に記載の２次元高速フーリエ変換演算装置。
【請求項８】
前記所定数は、１であることを特徴とする請求項６又は７に記載の２次元高速フーリエ変換演算装置。
【請求項９】
前記所定数は、２以上の整数であり、且つ、前記第１方向に並ぶデータの数を前記所定数で除算したときに割り切れる値であることを特徴とする請求項６又は７に記載の２次元高速フーリエ変換演算装置。
【請求項１０】
前記内部バッファのバッファ量は、前記所定数のラインのデータ量の２倍以上であり、
前記第２の１次元高速フーリエ変換演算回路による処理の実行中に、前記第１の１次元高速フーリエ変換演算回路は、次に演算対象となる第１の演算対象データについての処理を実行する
ことを特徴とする請求項７に記載の２次元高速フーリエ変換演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路における２次元高速フーリエ変換演算方法及び２次元高速フーリエ変換演算装置に関するものである。
【背景技術】
【０００２】
図１１は、メモリ１に記憶される第１の演算対象データに対して２次元高速フーリエ変換（ＦＦＴ）演算を実施する、従来の２次元ＦＦＴ演算装置３００の構成を概略的に示すブロック図であり、図１２は、第１の演算対象データ（小領域）１２を複数含む映像データ（ＦＦＴ演算対象領域）１１を示す説明図である。図１１に示されるように、２次元ＦＦＴ演算装置３００は、縦方向１次元ＦＦＴ演算回路３０１と、横方向１次元ＦＦＴ演算回路３０２と、内部バッファ３０３と、メモリインタフェース３０４，３０７と、中間バッファインタフェース３０５，３０６とを有する。
【０００３】
図１３は、縦方向１次元ＦＦＴ演算回路３０１の構成を概略的に示すブロック図である。図１３に示されるように、縦方向１次元ＦＦＴ演算回路３０１は、メモリインタフェース３０４及び中間バッファインタフェース３０５に接続されたアクセス制御回路３１１と、ＦＦＴ演算回路３１２と、データバス３１３とを有する。縦方向１次元ＦＦＴ演算回路３０１において、アクセス制御回路３１１は、ＦＦＴ演算起動信号Ｓｓを受けると、メモリ１からメモリインタフェース３０４を介して第１の演算対象データの縦１ライン分のデータをリードし、ＦＦＴ演算回路３１２にデータ準備完了信号Ｓｒ３１１を送ると共に、データバス３１３を経由してリードデータＤ３０４を送る。ＦＦＴ演算回路３１２は、リードデータＤ３０４に対して１次元ＦＦＴ演算を実行し、この演算が完了すると１次元ＦＦＴ演算完了信号Ｓｄ３１２をアクセス制御回路３１１に通知する。アクセス制御回路３１１は、１次元ＦＦＴ演算完了信号Ｓｄ３１２を受け取ると、データバス３１３を経由して第１の演算結果データＤ３０５を取り込み、縦１ライン分の第１の演算結果データを内部バッファインタフェース３０５を介して内部バッファ３０３にライトする。縦方向１次元ＦＦＴ演算回路３０１は第１の演算対象データ全体について縦１ラインずつ順に第１の演算結果データＤ３０５を生成し、内部バッファ３０３にライトする。
【０００４】
図１４は、横方向１次元ＦＦＴ演算回路３０２の構成を概略的に示すブロック図である。図１４に示されるように、横方向１次元ＦＦＴ演算回路３０２は、メモリインタフェース３０７及び中間バッファインタフェース３０６に接続されたアクセス制御回路３２１と、ＦＦＴ演算回路３２２と、データバス３２３とを有する。横方向１次元ＦＦＴ演算回路３０２において、アクセス制御回路３２１は、１次元ＦＦＴ演算完了信号Ｓｄを受けると、内部バッファ３０３に保持されている第１の演算結果データ（すなわち、第２の演算対象データ）から中間バッファインタフェース３０６を介して横１ライン分のデータをリードし、ＦＦＴ演算回路３２２にデータ準備完了信号Ｓｒ３２１を送ると共に、データバス３２３を経由してリードデータＤ３０６を送る。ＦＦＴ演算回路３２２は、リードデータＤ３０６に対して１次元ＦＦＴ演算を実行し、この演算が完了すると１次元ＦＦＴ演算完了信号Ｓｄ３２２をアクセス制御回路３２１に通知する。アクセス制御回路３２１は、１次元ＦＦＴ演算完了信号Ｓｄ３２２を受け取ると、データバス３２３を経由して第２の演算結果データＤ３０７を取り込みメモリインタフェース３０７を経由してメモリ１に横１ライン分の第２の演算結果データをライトする。横方向１次元ＦＦＴ演算回路３０２は、横方向全ラインについて順に第２の演算結果データを生成し、メモリ１にライトする。
【０００５】
図１５は、従来の２次元ＦＦＴ演算方法を示すフローチャートであり、図１６は、従来の２次元ＦＦＴ演算方法を示す説明図である。図１５及び図１６に示されるように、２次元ＦＦＴ演算装置３００において、縦方向１次元ＦＦＴ演算回路３０１は、第１の演算対象データの縦１ライン分のデータをメモリ１からリードし（ステップＳＴ３０１）、縦１ラインに対する１次元ＦＦＴ演算を実行し（ステップＳＴ３０２）、第１の演算結果データ全体を内部バッファ３０３にライトする（ステップＳＴ３０３）。縦方向１次元ＦＦＴ演算回路３０１は、この処理を３２回（小領域１２の横方向のデータ数に相当する回数）繰り返す（ステップＳＴ３０４）。その後、横方向１次元ＦＦＴ演算回路３０２は、内部バッファ３０３に保持されている第１の演算結果データ（すなわち、第２の演算対象データ）から横１ライン分のデータをリードし（ステップＳＴ３０５）、横１ラインに対する１次元ＦＦＴ演算を実行し（ステップＳＴ３０６）、第２の演算結果データをメモリ１にライトする（ステップＳＴ３０７）。横方向１次元ＦＦＴ演算回路３０２は、この処理を３２回（小領域１２の縦方向のデータ数に相当する回数）繰り返す（ステップＳＴ３０８）。ステップＳＴ３０１〜ＳＴ３０８の処理によって、３２ライン×３２ラインの１つの小領域１２に対する２次元ＦＦＴ演算を完了し、次に、別の小領域に対して同様の処理を繰り返す。
【０００６】
このように、小領域１２全体に対して２次元ＦＦＴ演算を順に実行する場合、演算処理の高速化のために、横方向１次元ＦＦＴ演算回路３０２が、ある小領域に対して１次元ＦＦＴ演算を実行している間に、縦方向１次元ＦＦＴ演算回路３０１が次の小領域に対する１次元ＦＦＴ演算を先行して開始する（すなわち、縦方向ＦＦＴ演算と横方向ＦＦＴ演算のパイプライン処理を行う）ことで処理時間を短縮する。このようなパイプライン処理を行うためには、横方向１次元ＦＦＴ演算回路３０２が用いる内部バッファとは別に、縦方向１次元ＦＦＴ演算回路３０１がＦＦＴ演算結果を書き込むための内部バッファが必要となり、内部バッファ量は３２ライン（縦）×３２ライン（横）×２面分必要となる。
【０００７】
なお、従来の多次元フーリエ変換に関する技術は、例えば、特許文献１に記載されている。
【０００８】
【特許文献１】特開２００２−１６３２４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記従来の２次元ＦＦＴ演算装置では、内部バッファ３０３のバッファ量が、ＦＦＴ演算対象領域１１の小領域１２と同等以上、例えば、３２ライン×３２ライン×１面分以上必要となる。また、パイプライン処理を行う場合には、３２ライン×３２ライン×２面分以上のバッファ量が必要となり、バッファ量の増大が装置のコストを増大させるという問題があった。
【００１０】
また、ＦＦＴ演算対象領域１１の小領域１２が大きくなればなるほど、必要となるバッファ量が増大するため、ＦＦＴ演算対象領域をあまり大きくすることができず、ＦＦＴ演算を実行できる領域が制限されるという問題もあった。
【００１１】
なお、回路規模を縮小するために、パイプライン処理を行わない構成を採用したとしても、削減できる回路構成は、１つのＦＦＴ演算回路と、小領域１面に対応する内部バッファ１面だけであり、依然として小領域１面に対応する内部バッファは必要であり、バッファ量の増大に起因するコスト増大の問題を十分に解決できなかった。
【００１２】
また、内部バッファ量を削減するために、縦方向１次元ＦＦＴ演算結果を外部メモリに書き出す方法も考えられるが、外部メモリに対するＣＰＵからのアクセスとＦＦＴ演算回路からのアクセスが競合した場合に、特定時間内の処理完了を保証できないという別の問題が生じることになる。
【００１３】
そこで、本発明は、上記従来技術の課題を解決するためになされたものであり、その目的は、内部バッファ量を削減することができる２次元高速フーリエ変換演算方法及び２次元高速フーリエ変換演算装置を提供することである。
【課題を解決するための手段】
【００１４】
本発明の２次元高速フーリエ変換演算方法は、内部バッファを有する回路によって、第１及び第２方向に２次元配列された第１の演算対象データを２次元高速フーリエ変換演算する方法であって、前記第１の演算対象データを第１方向１ラインずつ順に１次元高速フーリエ変換演算して第１の演算結果データを生成し、第１方向１ラインの前記第１の演算結果データが生成される毎に、前記第１の演算結果データの中の指定位置のデータを第２の演算対象データとして前記内部バッファに保持させる処理を、前記第１の演算対象データ全体について実行する、第１方向処理実行ステップと、保持された前記第２の演算対象データを第２方向１ラインずつ順に１次元高速フーリエ変換演算して第２の演算結果データを生成する、第２方向処理実行ステップと、前記第１の演算対象データ全体について前記第２の演算結果データが生成されるまで、前記指定位置を変更して前記第１方向処理実行ステップ及び前記第２方向処理実行ステップを繰り返す、処理繰り返しステップとを有し、前記内部バッファに保持される前記第２の演算対象データは、第１方向に並ぶ所定数ラインのデータであり、前記所定数は、前記第１の演算対象データの第１方向に並ぶデータの数よりも少ない値であることを特徴としている。
【００１５】
また、本発明の２次元高速フーリエ変換演算装置は、第１及び第２方向に２次元配列された第１の演算対象データを２次元高速フーリエ変換演算する装置であって、内部バッファと、前記第１の演算対象データを第１方向１ラインずつ順に１次元高速フーリエ変換演算して第１の演算結果データを生成し、第１方向１ラインの前記第１の演算結果データが生成される毎に、前記第１の演算結果データの中の指定位置のデータを第２の演算対象データとして前記内部バッファに保持させる処理を、前記第１の演算対象データ全体について実行する、第１の１次元高速フーリエ変換演算回路と、保持された前記第２の演算対象データを第２方向１ラインずつ順に１次元高速フーリエ変換演算して第２の演算結果データを生成する、第２の１次元高速フーリエ変換演算回路とを有し、前記第１の演算対象データ全体について前記第２の演算結果データが生成されるまで、前記指定位置を変更して前記第１の１次元高速フーリエ変換演算回路による処理及び前記第２の１次元高速フーリエ変換演算回路による処理を繰り返し、前記内部バッファに保持される前記第２の演算対象データは、第１方向に並ぶ所定数ラインのデータであり、前記所定数は、前記第１の演算対象データの第１方向に並ぶデータの数よりも少ない値であることを特徴としている。
【発明の効果】
【００１６】
以上に説明したように、本発明によれば、内部バッファ量を大幅に削減でき、装置の製造コスト削減を実現することができるという効果がある。
【００１７】
また、本発明によれば、２次元ＦＦＴ演算専用の内部バッファを使用しているので、２次元ＦＦＴ演算を一定時間で完了させることができるという効果がある。
【発明を実施するための最良の形態】
【００１８】
第１の実施形態
図１は、本発明の第１の実施形態に係る２次元高速フーリエ変換（ＦＦＴ）演算装置１００（すなわち、第１の実施形態に係る２次元ＦＦＴ演算方法を実施する装置）の構成を概略的に示すブロック図である。図１に示されるように、第１の実施形態に係る２次元ＦＦＴ演算装置１００は、第１方向（例えば、縦方向）及び第２方向（例えば、横方向）に２次元配列された第１の演算対象データを２次元ＦＦＴ演算する装置である。この第１の演算対象データは、メモリ１に格納されており、前述の図１２に示される小領域１２に相当する。小領域１２は、例えば、縦方向に３２ライン、横方向に３２ラインのデータであるが、縦方向及び横方向のライン数は３２ラインに限定されない。
【００１９】
図１に示されるように、２次元ＦＦＴ演算装置１００は、第１の演算対象データの中の縦方向に並ぶ１ラインのデータ（第１の実施形態においては、３２個のデータ）を１次元ＦＦＴ演算する縦方向１次元ＦＦＴ演算回路１０１と、横方向に１ラインのデータ（第１の実施形態においては、３２個のデータ）を１次元ＦＦＴ演算する横方向１次元ＦＦＴ演算回路１０２と、内部バッファ１０３と、メモリ１に接続されるメモリインタフェース１０４，１０７と、内部バッファ１０３に接続される中間バッファインタフェース１０５，１０６とを有する。第１の実施形態における内部バッファ１０３は、第１の演算対象データである小領域（図１２の符号１２）の横方向のデータの数に等しいバッファ量、例えば、バッファ量として‘３２’（＝３２ライン（横）×１ライン（縦））を有する。また、２次元ＦＦＴ演算装置１００がパイプライン処理を行う場合には、内部バッファ１０３は、バッファ量として‘６４’（＝３２ライン（横）×１ライン（縦）×２面）を有する。
【００２０】
縦方向１次元ＦＦＴ演算回路１０１は、第１の演算対象データを縦１ラインずつ順に１次元ＦＦＴ演算して第１の演算結果データを生成し、縦１ラインの第１の演算結果データが生成される毎に、第１の演算結果データの中の指定位置（縦方向Ｍ番目のライン）のデータを第２の演算対象データとして内部バッファ１０３に保持させる処理を、所定数ラインの第２の演算対象データが内部バッファ１０３に保持されるまで実行する。所定数は、第１の演算対象データの縦方向のデータの数よりも少ない値であり、第１の実施形態においては‘１’である。
【００２１】
縦方向１次元ＦＦＴ演算回路１０１によって横１ラインの第２の演算対象データが内部バッファ１０３に保持されたときに、横方向１次元ＦＦＴ演算回路１０２は、保持された横１ラインの第２の演算対象データを１次元高速フーリエ変換演算して横１ラインの第２の演算結果データを生成し、メモリ１に保持させる。
【００２２】
縦方向１次元ＦＦＴ演算回路１０１及び横方向１次元ＦＦＴ演算回路１０２は、第１の演算対象データ全体についての第２の演算結果データの生成が完了するまで、横１ラインの第２の演算対象データを１次元ＦＦＴ演算する毎に、指定位置を変更して（例えば、指定位置のライン番号Ｍを１インクリメントさせて）、演算結果データを生成するための前記処理を繰り返す。
【００２３】
図２は、図１の縦方向１次元ＦＦＴ演算回路１０１の構成を概略的に示すブロック図である。図２に示されるように、縦方向１次元ＦＦＴ演算回路１０１は、メモリインタフェース１０４及び中間バッファインタフェース１０５に接続されたアクセス制御回路１１１と、ＦＦＴ演算回路１１２と、アクセス制御回路１１１とＦＦＴ演算回路１１２とを接続するデータバス１１３と、Ｎビットカウンタ１１４と、Ｎビットレジスタ１１５と、比較器１１６とを有する。
【００２４】
アクセス制御回路１１１は、ＦＦＴ演算起動信号Ｓｓを受けると、メモリ１からメモリインタフェース１０４を介して第１の演算対象データの縦１ライン分のデータをリードし、ＦＦＴ演算回路１１２にデータ準備完了信号Ｓｒ１１１を送ると共に、データバス１１３を経由してリードデータＤ１０４を送る。
【００２５】
ＦＦＴ演算回路１１２は、リードデータＤ１０４に対して１次元ＦＦＴ演算を実行し、この演算が完了すると１次元ＦＦＴ演算完了信号Ｓｄ１１２をアクセス制御回路１１１に通知する。アクセス制御回路１１１は、１次元ＦＦＴ演算完了信号Ｓｄ１１２を受け取ると、データバス１１３を経由して演算結果データＤ１０５を取り込み、１ライン分の演算結果データの一部を第１の演算結果データとして中間バッファインタフェース１０５を介して内部バッファ１０３にライトする。
【００２６】
Ｎビットカウンタ１１４は、縦方向１次元ＦＦＴ演算完了信号Ｓｄをカウントアップ信号とし、カウント値Ｃ１１４を出力する。
【００２７】
Ｎビットレジスタ１１５は、特定の値Ｃ１１５を格納し、出力する。第１の演算対象データである小領域が、３２ライン（横）×３２ライン（縦）のデータ領域である場合には、縦方向１次元ＦＦＴ演算回路１０１のＮビットレジスタ１１５には、縦方向のデータの数である‘３２’が格納される。
【００２８】
比較器１１６は、Ｎビットカウンタ１１４のカウント値Ｃ１１４とＮビットレジスタ１１５の値Ｃ１１５を比較し、比較データが一致しているときには一致信号Ｓｍ１１６をアサートし、比較データが一致していないときには不一致信号Ｓｎ１１６をアサートする。
【００２９】
アクセス制御回路１１１は、比較器１１６によって一致信号Ｓｍ１１６がアサートされたときは、次の小領域のデータをメモリ１からリードし、縦方向１次元ＦＦＴ演算を制御する。また、アクセス制御回路１１１は、比較器１１６によって不一致信号Ｓｎ１１６がアサートされたときは、前回と同じ小領域のデータをメモリ１からリードし、縦方向１次元ＦＦＴ演算を制御し、縦１ラインのうち指定位置であるＭ番目（Ｍ＝１，２，…，３２）のデータのみを内部バッファ１０３へ書き出す。ここで、Ｍは、不一致信号がアサートされるたびに値が１インクリメントされ、一致信号Ｓｍ１１６がアサートされると０に戻る。
【００３０】
図３は、図１の横方向１次元ＦＦＴ演算回路１０２の構成を概略的に示すブロック図である。図３に示されるように、横方向１次元ＦＦＴ演算回路１０２は、メモリインタフェース１０４及び中間バッファインタフェース１０５に接続されたアクセス制御回路１２１と、ＦＦＴ演算回路１２２と、アクセス制御回路１２１とＦＦＴ演算回路１２２とを接続するデータバス１２３と、Ｎビットカウンタ１２４と、Ｎビットレジスタ１２５と、比較器１２６とを有する。
【００３１】
アクセス制御回路１２１は、縦方向１次元ＦＦＴ演算完了信号Ｓｄを受けると、内部バッファ１０３から内部バッファインタフェース１０６を介して第２の演算対象データの横１ライン分のデータをリードし、ＦＦＴ演算回路１２２にデータ準備完了信号Ｓｒ１２１を送ると共に、データバス１２３を経由してリードデータＤ１０６を送る。
【００３２】
ＦＦＴ演算回路１２２は、内部バッファ１０３からのリードデータＤ１０６に対して横方向１次元ＦＦＴ演算を実行し、この演算が完了すると１次元ＦＦＴ演算完了信号Ｓｄ１２２をアクセス制御回路１２１に通知する。アクセス制御回路１２１は、１次元ＦＦＴ演算完了信号Ｓｄ１２２を受け取ると、データバス１２３を経由して第２の演算結果データＤ１０７を取り込み、１ライン分の演算結果データをメモリインタフェース１０７を介してメモリ１にライトする。
【００３３】
Ｎビットカウンタ１２４は、横方向１次元ＦＦＴ演算完了信号Ｓｄ１２２をカウントアップ信号とし、カウント値Ｃ１２４を出力する。
【００３４】
Ｎビットレジスタ１２５は、特定の値Ｃ１２５を格納し、出力する。第１の演算対象データである小領域が、３２ライン（横）×３２ライン（縦）のデータ領域である場合には、横方向１次元ＦＦＴ演算回路１０２のＮビットレジスタ１２５には、横方向のデータの数である‘３２’が格納される。
【００３５】
比較器１２６は、Ｎビットカウンタ１２４のカウント値Ｃ１２４とＮビットレジスタ１２５の値Ｃ１２５を比較し、比較データが一致しているときには一致信号Ｓｍ１２６をアサートし、比較データが一致していないときには不一致信号Ｓｎ１２６をアサートする。
【００３６】
アクセス制御回路１２１は、比較器１２６によって不一致信号Ｓｎ１２６がアサートされたときは、前回と同じ小領域のデータをメモリ１からリードし、縦方向１次元ＦＦＴ演算を制御し、縦１ラインのうち指定位置であるＭ番目のデータのみを内部バッファ１０３へ書き出す（ステップＳＴ１０２〜ＳＴ１０４）。アクセス制御回路１２１は、比較器１１６によって一致信号Ｓｍ１２６がアサートされたときは、次の小領域のデータをメモリ１からリードし、縦方向１次元ＦＦＴ演算を制御し、縦１ラインのうち指定位置であるＭ番目のデータのみを内部バッファ１０３へ書き出す（ＳＴ１０２〜ＳＴ１０４）。
【００３７】
次に、第１の実施形態に係る２次元ＦＦＴ演算装置１００の動作（すなわち、第１の実施形態に係る２次元ＦＦＴ演算方法）を説明する。図４は、第１の実施形態に係る２次元ＦＦＴ演算装置１００の動作（すなわち、第１の実施形態に係る２次元ＦＦＴ演算方法）を示すフローチャートであり、図５は、第１の実施形態に係る２次元ＦＦＴ演算装置１００の動作（すなわち、第１の実施形態に係る２次元ＦＦＴ演算方法）を示す説明図である。
【００３８】
図４及び図５に示されるように、２次元ＦＦＴ演算装置１００において、縦方向１次元ＦＦＴ演算回路１０１は、第１の演算対象データの横ラインを特定するための番号であるＭを初期値０にし（ステップＳＴ１００）、次に、Ｍを１インクリメントする（ステップＳＴ１０１）。次に、縦第１の演算対象データの方向１ライン分のデータをメモリ１からリードし（ステップＳＴ１０２）、縦１ラインに対する１次元ＦＦＴ演算を実行して第１の演算結果データを生成し（ステップＳＴ１０３）、第１の演算結果データの内のＭ番目（ここでは、Ｍ＝１）のラインのデータを内部バッファ１０３にライトする（ステップＳＴ１０４）。次に、縦方向１次元ＦＦＴ演算回路１０１は、ステップＳＴ１０２〜ＳＴ１０４までの処理を、縦１ライン分のデータを１ラインずつ横方向に移動させて、３２回（小領域１２の横方向のデータ数に相当する。）繰り返す（ステップＳＴ１０５）。この結果、内部バッファ１０３には、１番目のラインの横１ライン分の第１の演算結果データが保持される。
【００３９】
次に、横方向１次元ＦＦＴ演算回路１０２は、内部バッファ１０３から横１ライン分の第１の演算結果データ（すなわち、第２の演算対象データ）をリードし（ステップＳＴ１０６）、横１ラインに対する１次元ＦＦＴ演算を実行し（ステップＳＴ１０７）、１次元ＦＦＴ演算結果である第２の演算結果データをメモリ１にライトする（ステップＳＴ１０８）。
【００４０】
次に、縦方向１次元ＦＦＴ演算回路１０１及び横方向１次元ＦＦＴ演算回路１０２は、ステップＳＴＳ１０１〜ＳＴ１０８の処理を、Ｍ＝１〜３２の各ラインについて、順に繰り返す（合計で、３２回繰り返す）ことによって（ステップＳＴ１０９）、メモリ１に３２ライン×３２ラインの小領域１２に対する２次元ＦＦＴ演算結果データ（第２の演算結果データ）を記憶させる。なお、演算処理の高速化のために、横方向１次元ＦＦＴ演算回路１０２が、ある小領域に対して１次元ＦＦＴ演算を実行している間に、縦方向１次元ＦＦＴ演算回路１０１が次の小領域に対する１次元ＦＦＴ演算を先行して開始する（すなわち、縦方向ＦＦＴ演算と横方向ＦＦＴ演算のパイプライン処理を行う）ことで処理時間を短縮することができる。
【００４１】
以上に説明したように、第１の実施形態に係る２次元ＦＦＴ演算装置１００（又は第１の実施形態に係る２次元ＦＦＴ演算方法）によれば、内部バッファ量を、大幅に削減することができる。具体的には、従来例に比べて、内部バッファ量を１／３２に削減することができる。
【００４２】
また、第１の実施形態に係る２次元ＦＦＴ演算装置１００（又は第１の実施形態に係る２次元ＦＦＴ演算方法）によれば、２次元ＦＦＴ演算専用の内部バッファを使用しているので、２次元ＦＦＴ演算を一定時間で完了させることができる。
【００４３】
第２の実施形態
第２の実施形態に係る２次元ＦＦＴ演算装置及び２次元ＦＦＴ演算方法は、縦方向１ラインＦＦＴ演算データのうちＭ１番目とＭ２番目の２つのデータを内部バッファへ書き出す点が、縦方向１ラインＦＦＴ演算データのうち１つのデータを内部バッファへ書き出す第１の実施形態の２次元ＦＦＴ演算装置及び２次元ＦＦＴ演算方法と相違する。以下に、第２の実施形態に係る２次元ＦＦＴ演算装置及び２次元ＦＦＴ演算方法を説明する。
【００４４】
図６は、本発明の第２の実施形態に係る２次元ＦＦＴ演算装置２００（すなわち、第２の実施形態に係る２次元ＦＦＴ演算方法を実施する装置）の構成を概略的に示すブロック図である。図６に示されるように、２次元ＦＦＴ演算装置２００は、２次元配列された第１の演算対象データを２次元ＦＦＴ演算する装置である。
【００４５】
図６に示されるように、２次元ＦＦＴ演算装置２００は、第１の演算対象データの中の縦方向１ライン（縦１ライン）のデータを１次元ＦＦＴ演算する縦方向１次元ＦＦＴ演算回路２０１と、横１ライン（横１ライン）のデータを１次元ＦＦＴ演算する横方向１次元ＦＦＴ演算回路２０２と、内部バッファ２０３と、メモリ１に接続されるメモリインタフェース２０４，２０７と、内部バッファ２０３に接続される中間バッファインタフェース２０５，２０６とを有する。第２の実施形態における内部バッファ２０３は、第１の演算対象データである小領域の横方向のデータの数の２倍のバッファ量、例えば、バッファ量として‘６４’（＝３２ライン（横）×２ライン（縦））を有する。また、２次元ＦＦＴ演算装置１００がパイプライン処理を行う場合には、内部バッファ２０３は、バッファ量として‘１２８’（＝３２ライン（横）×２ライン（縦）×２面）を有する。
【００４６】
縦方向１次元ＦＦＴ演算回路２０１は、第１の演算対象データを縦１ラインずつ順に１次元ＦＦＴ演算して第１の演算結果データを生成し、縦１ラインの第１の演算結果データが生成される毎に、第１の演算結果データの中の指定位置（縦方向Ｍ１番目のラインと、縦方向Ｍ２番目のライン）のデータを第２の演算対象データとして内部バッファ２０３に保持させる処理を、所定数ラインの第２の演算対象データが内部バッファ２０３に保持されるまで実行する。所定数は、第１の演算対象データの縦方向のデータの数よりも少ない値であり、第２の実施形態においては‘２’である。ただし、所定数は‘２’に限定されず、第１の演算対象データの縦方向に並ぶデータの数を所定数で除算したときに割り切れる値であれば、他の値（例えば、‘４’）とすることもできる。
【００４７】
縦方向１次元ＦＦＴ演算回路２０１によってＭ１番目とＭ２番目の横２ラインの第２の演算対象データが内部バッファ２０３に保持されたときに、横方向１次元ＦＦＴ演算回路２０２は、保持された横１ラインの第２の演算対象データを１次元高速フーリエ変換演算して横２ラインの第２の演算結果データを生成し、メモリ１に保持させる。
【００４８】
縦方向１次元ＦＦＴ演算回路２０１及び横方向１次元ＦＦＴ演算回路２０２は、第１の演算対象データ全体についての第２の演算結果データの生成が完了するまで、横２ラインの第２の演算対象データを１次元ＦＦＴ演算する毎に、指定位置を変更して（例えば、指定位置のライン番号Ｍ１、Ｍ２を１インクリメントさせて）、演算結果データを生成するための前記処理を繰り返す。
【００４９】
図７は、図６の縦方向１次元ＦＦＴ演算回路２０１の構成を概略的に示すブロック図である。図７に示されるように、縦方向１次元ＦＦＴ演算回路２０１は、メモリインタフェース２０４及び中間バッファインタフェース２０５に接続されたアクセス制御回路２１１と、ＦＦＴ演算回路２１２と、アクセス制御回路２１１とＦＦＴ演算回路２１２とを接続するデータバス２１３と、Ｎビットカウンタ２１４と、Ｎビットレジスタ２１５と、比較器２１６とを有する。
【００５０】
アクセス制御回路２１１は、ＦＦＴ演算起動信号Ｓｓを受けると、メモリ１からメモリインタフェース２０４を介して第１の演算対象データの縦１ライン分のデータをリードし、ＦＦＴ演算回路２１２にデータ準備完了信号Ｓｒ２１１を送ると共に、データバス２１３を経由してリードデータＤ２０４を送る。
【００５１】
ＦＦＴ演算回路２１２は、リードデータＤ２０４に対して１次元ＦＦＴ演算を実行し、この演算が完了すると１次元ＦＦＴ演算完了信号Ｓｄ２１２をアクセス制御回路２１１に通知する。アクセス制御回路２１１は、１次元ＦＦＴ演算完了信号Ｓｄ２１２を受け取ると、データバス２１３を経由して演算結果データＤ２０５を取り込み、２ライン分の演算結果データの一部を第１の演算結果データとして中間バッファインタフェース２０５を介して内部バッファ２０３にライトする。
【００５２】
Ｎビットカウンタ２１４は、縦方向１次元ＦＦＴ演算完了信号Ｓｄをカウントアップ信号とし、カウント値Ｃ２１４を出力する。
【００５３】
Ｎビットレジスタ２１５は、特定の値Ｃ２１５を格納し、出力する。第１の演算対象データである小領域が、３２ライン（横）×３２ライン（縦）のデータ領域である場合には、縦方向１次元ＦＦＴ演算回路２０１のＮビットレジスタ２１５には、縦方向のデータの数の１／２である‘１６’が格納される。
【００５４】
比較器２１６は、Ｎビットカウンタ２１４のカウント値Ｃ２１４とＮビットレジスタ２１５の値Ｃ２１５を比較し、比較データが一致しているときには一致信号Ｓｍ２１６をアサートし、比較データが一致していないときには不一致信号Ｓｎ２１６をアサートする。
【００５５】
アクセス制御回路２１１は、比較器２１６によって一致信号Ｓｍ２１６がアサートされたときは、次の小領域のデータをメモリ１からリードし、縦方向１次元ＦＦＴ演算を制御する。また、アクセス制御回路２１１は、比較器２１６によって不一致信号Ｓｎ２１６がアサートされたときは、前回と同じ小領域のデータをメモリ１からリードし、縦方向１次元ＦＦＴ演算を制御し、縦１ラインのうち指定位置であるＭ１番目（Ｍ１＝１，２，…，１６）のデータ、及びＭ２番目（Ｍ１＝１７，１８，…，３２）のデータのみを内部バッファ２０３へ書き出す。ここで、Ｍ１及びＭ２はそれぞれ、不一致信号がアサートされるたびに値が１インクリメントされ、一致信号Ｓｍ２１６がアサートされると初期値０及び１６に戻る。
【００５６】
図８は、図６の横方向１次元ＦＦＴ演算回路２０２の構成を概略的に示すブロック図である。図８に示されるように、横方向１次元ＦＦＴ演算回路２０２は、メモリインタフェース２０４及び中間バッファインタフェース２０５に接続されたアクセス制御回路２２１と、ＦＦＴ演算回路２２２と、アクセス制御回路２２１とＦＦＴ演算回路２２２とを接続するデータバス２２３と、Ｎビットカウンタ２２４と、Ｎビットレジスタ２２５と、比較器２２６とを有する。
【００５７】
アクセス制御回路２２１は、縦方向１次元ＦＦＴ演算完了信号Ｓｄを受けると、内部バッファ２０３から内部バッファインタフェース２０６を介して第２の演算対象データの横方向２ライン分のデータをリードし、ＦＦＴ演算回路２２２にデータ準備完了信号Ｓｒ１２１を送ると共に、データバス２２３を経由してリードデータＤ２０６を送る処理を、Ｍ１番目とＭ２番目の各ラインについて実行する。
【００５８】
ＦＦＴ演算回路２２２は、内部バッファ２０３からのリードデータＤ２０６に対して横方向１次元ＦＦＴ演算を実行し、この演算が完了すると１次元ＦＦＴ演算完了信号Ｓｄ２２２をアクセス制御回路２２１に通知する。アクセス制御回路２２１は、１次元ＦＦＴ演算完了信号Ｓｄ２２２を受け取ると、データバス２２３を経由して第２の演算結果データＤ２０７を取り込み、２ライン分の演第２の演算結果データをメモリインタフェース２０７を介してメモリ１にライトする。
【００５９】
Ｎビットカウンタ２２４は、横方向１次元ＦＦＴ演算完了信号Ｓｄ２１２２をカウントアップ信号とし、カウント値Ｃ２２４を出力する。
【００６０】
Ｎビットレジスタ２２５は、特定の値Ｃ２２５を格納し、出力する。第１の演算対象データである小領域が、３２ライン（横）×３２ライン（縦）のデータ領域である場合には、横方向１次元ＦＦＴ演算回路２０２のＮビットレジスタ２２５には、横方向のデータの数である‘３２’が格納される。
【００６１】
比較器２２６は、Ｎビットカウンタ２２４のカウント値Ｃ２２４とＮビットレジスタ２２５の値Ｃ２２５を比較し、比較データが一致しているときには一致信号Ｓｍ２２６をアサートし、比較データが一致していないときには不一致信号Ｓｎ２２６をアサートする。
【００６２】
アクセス制御回路２２１は、比較器２２６によって不一致信号Ｓｎ２２６がアサートされたときは、前回と同じ小領域のデータをメモリ１からリードし、縦方向１次元ＦＦＴ演算を制御し、縦１ラインのうち指定位置であるＭ１番目及びＭ２番目のデータのみを内部バッファ２０３へ書き出す。アクセス制御回路２２１は、比較器２１６によって一致信号Ｓｍ２２６がアサートされたときは、次の小領域のデータをメモリ１からリードし、縦方向１次元ＦＦＴ演算を制御し、縦１ラインのうち指定位置であるＭ１番目及びＭ２番目のデータのみを内部バッファ２０３へ書き出す。
【００６３】
次に、第２の実施形態に係る２次元ＦＦＴ演算装置２００の動作（すなわち、第２の実施形態に係る２次元ＦＦＴ演算方法）を説明する。図９は、第２の実施形態に係る２次元ＦＦＴ演算装置２００の動作（すなわち、第２の実施形態に係る２次元ＦＦＴ演算方法）を示すフローチャートであり、図１０は、第２の実施形態に係る２次元ＦＦＴ演算装置２００の動作（すなわち、第２の実施形態に係る２次元ＦＦＴ演算方法）を示す説明図である。
【００６４】
図９及び図１０に示されるように、２次元ＦＦＴ演算装置２００において、縦方向１次元ＦＦＴ演算回路２０１は、第１の演算対象データの横ラインを特定するための番号であるＭ１を初期値０にし、Ｍ２を初期値１６にし（ステップＳＴ２００）、次に、Ｍ１及びＭ２を１インクリメントする（ステップＳＴ２０１）。次に、第１の演算対象データの縦１ライン分のデータをメモリ１からリードし（ステップＳＴ２０２）、縦１ラインに対する１次元ＦＦＴ演算を実行して第１の演算結果データを生成し（ステップＳＴ２０３）、第１の演算結果データの内のＭ１番目（ここでは、Ｍ＝１）及びＭ２番目（ここでは、Ｍ＝１７）のラインのデータを内部バッファ２０３にライトする（ステップＳＴ２０４）。次に、縦方向１次元ＦＦＴ演算回路２０１は、ステップＳＴ２０２〜ＳＴ２０４までの処理を、縦１ライン分のデータを１ラインずつ横方向に移動させて、３２回（小領域１２の横方向のデータ数に相当する。）繰り返す（ステップＳＴ２０５）。この結果、内部バッファ２０３には、１番目のラインの横１ライン分及び１７番目のラインの横１ライン分の第１の演算結果データが保持される。
【００６５】
次に、横方向１次元ＦＦＴ演算回路２０２は、内部バッファ２０３から第１の演算結果データ（すなわち、第２の演算対象データ）をリードし（ステップＳＴ２０６）、横２ラインに対する１次元ＦＦＴ演算を実行し（ステップＳＴ２０７）、１次元ＦＦＴ演算結果である第２の演算結果データをメモリ１にライトする（ステップＳＴ２０８）。
【００６６】
次に、縦方向１次元ＦＦＴ演算回路２０１及び横方向１次元ＦＦＴ演算回路２０２は、ステップＳＴＳ２０１〜ＳＴ２０８の処理を、Ｍ１＝１〜１６、Ｍ２＝１７〜３２の各ラインについて、順に繰り返す（合計で、１６回繰り返す）ことによって（ステップＳＴ２０９）、メモリ１に３２ライン×３２ラインの小領域１２に対する２次元ＦＦＴ演算結果データ（第２の演算結果データ）を記憶させる。
【００６７】
以上に説明したように、第２の実施形態に係る２次元ＦＦＴ演算装置２００（又は第２の実施形態に係る２次元ＦＦＴ演算方法）によれば、内部バッファ量を、大幅に削減することができる。具体的には、従来例に比べて、内部バッファ量を１／１６に削減することができる。
【００６８】
また、第２の実施形態に係る２次元ＦＦＴ演算装置２００（又は第２の実施形態に係る２次元ＦＦＴ演算方法）によれば、第１の実施形態の場合に比べて、内部バッファ量は２倍になっているものの、処理回数を１／２にすることができる。
【００６９】
また、第２の実施形態に係る２次元ＦＦＴ演算装置２００（又は第２の実施形態に係る２次元ＦＦＴ演算方法）によれば、２次元ＦＦＴ演算専用の内部バッファを使用しているので、２次元ＦＦＴ演算を一定時間で完了させることができる。
【００７０】
なお、第２の実施形態において、上記以外の点は、上記第１の実施形態の場合と同じである。
【図面の簡単な説明】
【００７１】
【図１】本発明の第１の実施形態に係る２次元ＦＦＴ演算装置（すなわち、第１の実施形態に係る２次元ＦＦＴ演算方法を実施する装置）の構成を概略的に示すブロック図である。
【図２】図１の縦方向１次元ＦＦＴ演算回路の構成を概略的に示すブロック図である。
【図３】図１の横方向１次元ＦＦＴ演算回路の構成を概略的に示すブロック図である。
【図４】第１の実施形態に係る２次元ＦＦＴ演算装置の動作を示すフローチャートである。
【図５】第１の実施形態に係る２次元ＦＦＴ演算装置の処理手順を示す説明図である。
【図６】本発明の第２の実施形態に係る２次元ＦＦＴ演算装置（すなわち、第２の実施形態に係る２次元ＦＦＴ演算方法を実施する装置）の構成を概略的に示すブロック図である。
【図７】図６の縦方向１次元ＦＦＴ演算回路の構成を概略的に示すブロック図である。
【図８】図６の横方向１次元ＦＦＴ演算回路の構成を概略的に示すブロック図である。
【図９】第２の実施形態に係る２次元ＦＦＴ演算装置の動作を示すフローチャートである。
【図１０】第２の実施形態に係る２次元ＦＦＴ演算装置の処理手順を示す説明図である。
【図１１】従来例の２次元ＦＦＴ演算装置の回路構成を概略的に示すブロック図である。
【図１２】ＦＦＴ演算対象領域の説明図である。
【図１３】図１１の縦方向１次元ＦＦＴ演算回路の構成を概略的に示すブロック図である。
【図１４】図１１の横方向１次元ＦＦＴ演算回路の構成を概略的に示すブロック図である。
【図１５】従来例の２次元ＦＦＴ演算装置の動作を示すフローチャートである。
【図１６】従来例の２次元ＦＦＴ演算装置の処理手順を示す説明図である。
【符号の説明】
【００７２】
１  メモリ、
１１  映像データ（ＦＦＴ演算対象領域）、
１２  演算対象データ（小領域）、
１００，２００  ２次元ＦＦＴ演算装置、
１０１，２０１  縦方向１次元ＦＦＴ演算回路、
１０２，２０２  横方向１次元ＦＦＴ演算回路、
１０３，２０３  内部バッファ、
１０４，１０７，２０４，２０７  メモリインタフェース、
１０５，１０６，２０５，２０６  内部バッファインタフェース、
１１１，２１１  縦方向１次元ＦＦＴ演算回路のアクセス制御回路、
１１２，２１２  縦方向１次元ＦＦＴ演算回路のＦＦＴ演算回路、
１１３，２１３  縦方向１次元ＦＦＴ演算回路のデータバス、
１１４，２１４  縦方向１次元ＦＦＴ演算回路のＮビットカウンタ、
１１５，２１５  縦方向１次元ＦＦＴ演算回路のＮビットレジスタ、
１１６，２１６  縦方向１次元ＦＦＴ演算回路の比較器、
１２１，２２１  横方向１次元ＦＦＴ演算回路のアクセス制御回路、
１２２，２２２  横方向１次元ＦＦＴ演算回路のＦＦＴ演算回路、
１２３，２２３  横方向１次元ＦＦＴ演算回路のデータバス、
１２４，２２４  横方向１次元ＦＦＴ演算回路のＮビットカウンタ、
１２５，２２５  横方向１次元ＦＦＴ演算回路のＮビットレジスタ、
１２６，２２６  横方向１次元ＦＦＴ演算回路の比較器、
Ｓｓ  ＦＦＴ演算起動信号、
Ｓｄ  縦方向１次元ＦＦＴ演算完了信号、
Ｓｄｆ  横方向１次元ＦＦＴ演算完了信号、
Ｓｒ１１１，Ｓｒ１２１，Ｓｒ２１１，Ｓｒ２２１  データ準備完了信号、
Ｓｄ１１２，Ｓｄ１２２，Ｓｄ２１２，Ｓｄ２２２  １次元ＦＦＴ演算完了信号、
Ｃ１１４，Ｃ１２４，Ｃ２１４，Ｃ２２４  Ｎビットカウンタのカウント値、
Ｃ１１５，Ｃ１２５，Ｃ２１５，Ｃ２２５  Ｎビットレジスタの設定値、
Ｄ１０４，Ｄ２０４  メモリからのリードデータ（第１の演算対象データ）、
Ｄ１０６，Ｄ２０６  内部バッファからのリードデータ（第２の演算対象データ）、
Ｄ１０５，Ｄ２０５  １次元ＦＦＴ演算結果データ（第１の演算結果データ）、
Ｄ１０７，Ｄ２０７  ２次元ＦＦＴ演算結果データ（第２の演算結果データ）、
Ｓｍ１１６，Ｓｍ１２６，Ｓｍ２１６，Ｓｍ２２６  一致信号、
Ｓｎ１１６，Ｓｎ１２６，Ｓｎ２１６，Ｓｎ２２６  不一致信号。
【図１】
2008117044.tif 000003
【図２】
2008117044.tif 000004
【図３】
2008117044.tif 000005
【図４】
2008117044.tif 000006
【図５】
2008117044.tif 000007
【図６】
2008117044.tif 000008
【図７】
2008117044.tif 000009
【図８】
2008117044.tif 000010
【図９】
2008117044.tif 000011
【図１０】
2008117044.tif 000012
【図１１】
2008117044.tif 000013
【図１２】
2008117044.tif 000014
【図１３】
2008117044.tif 000015
【図１４】
2008117044.tif 000016
【図１５】
2008117044.tif 000017
【図１６】
2008117044.tif 000018