JPS6237776A - 高速フ−リエ変換装置 - Google Patents
高速フ−リエ変換装置Info
- Publication number
- JPS6237776A JPS6237776A JP17698285A JP17698285A JPS6237776A JP S6237776 A JPS6237776 A JP S6237776A JP 17698285 A JP17698285 A JP 17698285A JP 17698285 A JP17698285 A JP 17698285A JP S6237776 A JPS6237776 A JP S6237776A
- Authority
- JP
- Japan
- Prior art keywords
- data
- memory
- address
- circuit
- calculation
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Complex Calculations (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は、高速フーリエ変換（Ｆａｓｔ Ｆｏｕｒｉｅ
ｒＴｒａｎｓｆｏｒｍ、以下、ＦＦＴと略す）装置に関
する。
ｒＴｒａｎｓｆｏｒｍ、以下、ＦＦＴと略す）装置に関
する。
従来のＦＦＴ装置は、データか格納されでいるメモリの
アドレスを全ビットリバースしてデータの順序を並べ換
えた後、所定のアルゴリズムに従って、アドレスジェネ
レータで発生されたアドレスでバタフライ演算のデータ
ベアをアクセスして演算を進めていくようになってあり
、この結果、ＦＦＴ演算結果が順序良く並ぶことになる
。
アドレスを全ビットリバースしてデータの順序を並べ換
えた後、所定のアルゴリズムに従って、アドレスジェネ
レータで発生されたアドレスでバタフライ演算のデータ
ベアをアクセスして演算を進めていくようになってあり
、この結果、ＦＦＴ演算結果が順序良く並ぶことになる
。
ここで、バタフライ演算は第３図に示すように次式で与
えられる。
えられる。
Ｘ（ｉ）＝工（ｉ）＋ｗ−”・χ０）
Ｘ（Ｄ＝工（ｉ）−Ｗ−Ｋ・工（Ｄ
ここで、１．ｊ：データ誠
χ（ｉ）、工（ｊ）、Ｘ（ｉ）、Ｙ（ｊ） ：複素数
Ｗ−に二ウェイトベクトル 第４図（ａ）は従来のＦＦＴ装置のアルゴリズムの例（
データ数Ｎ＝２３＝８の場合）を示す図、第４図（ｂ）
はそのウェイトヘクトルＷ′１．Ｗ６゜Ｗ−“・、ｗ”
、ｗ’ｊ、ｗ”７ 、Ｗ” 、ＷＯ、−Ｗｏ。
Ｗ−に二ウェイトベクトル 第４図（ａ）は従来のＦＦＴ装置のアルゴリズムの例（
データ数Ｎ＝２３＝８の場合）を示す図、第４図（ｂ）
はそのウェイトヘクトルＷ′１．Ｗ６゜Ｗ−“・、ｗ”
、ｗ’ｊ、ｗ”７ 、Ｗ” 、ＷＯ、−Ｗｏ。
−Ｗ４ 、−Ｗ゛７、−Ｗ′３のベクトル図である０円
内の数字はデータ遂ヲ示している。
内の数字はデータ遂ヲ示している。
メモリのアドレスを全ビットリバースしてデータの順序
を０．４，２．６，１．５．３．７と並べ換えた後、ス
テップ１．１１．ＩＩＩとアルゴリズムに従っで、アド
レスジェネレータで発生されたアドレスでバタフライ演
算のデータをアクセスして演算を進めでいくと、最終的
に０．１，２．３゜４．５，６．７と順序良く並んだＦ
ＦＴ演算結果が得られる。
を０．４，２．６，１．５．３．７と並べ換えた後、ス
テップ１．１１．ＩＩＩとアルゴリズムに従っで、アド
レスジェネレータで発生されたアドレスでバタフライ演
算のデータをアクセスして演算を進めでいくと、最終的
に０．１，２．３゜４．５，６．７と順序良く並んだＦ
ＦＴ演算結果が得られる。
（発明か解決しようとする問題点）
上述した従来のＦＦＴ装置では、データアドレスの全ビ
ット１ノバースによるデータの並べ換えと演算過程での
アドレスジェネレータによるデータアドレスとウェイト
アドレスの発生、アクセスとに時間かかかつ、回路も摺
雑になるという問題点がある。
ット１ノバースによるデータの並べ換えと演算過程での
アドレスジェネレータによるデータアドレスとウェイト
アドレスの発生、アクセスとに時間かかかつ、回路も摺
雑になるという問題点がある。
本発明の目的は、高速でリアルタイム処理に適したＦＦ
Ｔ装置を提供することである。
Ｔ装置を提供することである。
本発明のＦＦＴ装雷は、データが時系列に格納されでい
る第１のメモリのアドレスの最下位ビットと上位ビット
をリバースして、前記データをアクセスしバタフライ演
算を行なう第１の装置と、第１のメモリの演算結果か、
そのデータの個数に応じて、アドレスか全ビットリバー
スされて格納される第２のメモリを備え、第１、第２の
メモリを介して第１の装置とパイプライン的に接続され
、第２のメモリのデータによりバタフライ演算の次の処
理を行なう第２の装置を有する。
る第１のメモリのアドレスの最下位ビットと上位ビット
をリバースして、前記データをアクセスしバタフライ演
算を行なう第１の装置と、第１のメモリの演算結果か、
そのデータの個数に応じて、アドレスか全ビットリバー
スされて格納される第２のメモリを備え、第１、第２の
メモリを介して第１の装置とパイプライン的に接続され
、第２のメモリのデータによりバタフライ演算の次の処
理を行なう第２の装置を有する。
このように１ビツトリバースを行なうことにより、従来
のように全ビットリバースを行なう場合よりも回路構成
か簡単になって、データアクセス、したがって、演算が
高速になり、また、装Ｍを、バタフライ演算を行なう第
１の装置と、ＩＦＦＴ、絶対値／位相の演算、スペクト
ラムの演算等を行なう第２の装置に分割し、かつこれら
装置をパイプライン的（処理の多重化を指す）に接続す
ることにより、各装置は自分の処理が完了し１こデータ
を他方の装置に渡した後は前処理からのデータを処理す
ることかできるのでリアルタイム処理が寅現される。
のように全ビットリバースを行なう場合よりも回路構成
か簡単になって、データアクセス、したがって、演算が
高速になり、また、装Ｍを、バタフライ演算を行なう第
１の装置と、ＩＦＦＴ、絶対値／位相の演算、スペクト
ラムの演算等を行なう第２の装置に分割し、かつこれら
装置をパイプライン的（処理の多重化を指す）に接続す
ることにより、各装置は自分の処理が完了し１こデータ
を他方の装置に渡した後は前処理からのデータを処理す
ることかできるのでリアルタイム処理が寅現される。
以下、本発明の実施例について図面を参照して説明する
。
。
第１図は本発明のＦＦＴ装雪の一実施例（データ数Ｎ＝
８）を示すブロック図、第２図はそのバタフライ演算の
演算過程を示す図である。
８）を示すブロック図、第２図はそのバタフライ演算の
演算過程を示す図である。
アドレスカウンタ１ （３どットＡＯ，ＡＩ、 Ａ２か
うなる）はデータアクセス毎にインクリメントされる初
段８進カウンタ（バタフライ演算１回で複素数の２つデ
ータをリード／ラインするため）と８進カウンタの桁上
げでインクリメントされていく２進カウンタ（実数部と
虚数部と別々にデータをリード／ライトするため）から
なる、メモリ３にはデータ：１：（ｉ）（ｌ・０．・・
・・・・２７）か、ウェイトテーブル５にはウェイトベ
クトルｗ−３，ｗ−２，Ｗ−１゜Ｗｏ 、 ＷＩ 、
ＶＪ２ 、 Ｗ３がそれぞれ格納されている。１ビツト
リバース回路２はアドレスカウンタ１の出力のビット変
換（ステップエではビットＡＯとＡ２、ステップ１１て
はビットＡＯとＡＩ）を行なう。
うなる）はデータアクセス毎にインクリメントされる初
段８進カウンタ（バタフライ演算１回で複素数の２つデ
ータをリード／ラインするため）と８進カウンタの桁上
げでインクリメントされていく２進カウンタ（実数部と
虚数部と別々にデータをリード／ライトするため）から
なる、メモリ３にはデータ：１：（ｉ）（ｌ・０．・・
・・・・２７）か、ウェイトテーブル５にはウェイトベ
クトルｗ−３，ｗ−２，Ｗ−１゜Ｗｏ 、 ＷＩ 、
ＶＪ２ 、 Ｗ３がそれぞれ格納されている。１ビツト
リバース回路２はアドレスカウンタ１の出力のビット変
換（ステップエではビットＡＯとＡ２、ステップ１１て
はビットＡＯとＡＩ）を行なう。
ウェイトカウンタ４は、アドレスカウンタ１の最下位ビ
ットＡＯてビット交換されるビット（Ａ２゜ＡＩ、 八
〇の順）の立上りでカウントしてウェイトテーブル５の
アドレスを発生する。なお、ウェイトカウンタ４の最下
位ビットがウェイトテーブル５の最上位ビットに接続さ
れており、ウェイトカウンタ４の出力を全ビットリバー
スしたものがウェイトテーブル５のアドレスとなる。こ
のようにして、必要なウェイトベクトルが自動的に得ら
れる。制御・演算回路６はアドレスカウンタ］および１
ビツト・リバース回路２の制御を行なうとともに、メモ
リ３からデータを取出してバタフライ演算を行ない、結
果をメモリ３に格納する。ざらに、制御・演算回路６は
ＦＦＴ演算が終了して、全ビットリバースした順序でメ
モリ３に残っているデータを全ビットリバースして正し
い順序に並へ換えでメモリ８に移す。制御・演算回路９
はメモリ８に移されたデータに対してマルチプレクサ７
を経でアクセスし、ＩＦＦＴ （逆ＦＦＴ 、周波数軸
から峙門軸への変換）、絶対値／位相、スペクトラム（
パワー（ａ）の演算等の処理を行なう。
ットＡＯてビット交換されるビット（Ａ２゜ＡＩ、 八
〇の順）の立上りでカウントしてウェイトテーブル５の
アドレスを発生する。なお、ウェイトカウンタ４の最下
位ビットがウェイトテーブル５の最上位ビットに接続さ
れており、ウェイトカウンタ４の出力を全ビットリバー
スしたものがウェイトテーブル５のアドレスとなる。こ
のようにして、必要なウェイトベクトルが自動的に得ら
れる。制御・演算回路６はアドレスカウンタ］および１
ビツト・リバース回路２の制御を行なうとともに、メモ
リ３からデータを取出してバタフライ演算を行ない、結
果をメモリ３に格納する。ざらに、制御・演算回路６は
ＦＦＴ演算が終了して、全ビットリバースした順序でメ
モリ３に残っているデータを全ビットリバースして正し
い順序に並へ換えでメモリ８に移す。制御・演算回路９
はメモリ８に移されたデータに対してマルチプレクサ７
を経でアクセスし、ＩＦＦＴ （逆ＦＦＴ 、周波数軸
から峙門軸への変換）、絶対値／位相、スペクトラム（
パワー（ａ）の演算等の処理を行なう。
次に、本実施例の動作を説明する。表１、表２、表３は
各ステップ■、ＩＩ、■におけるアドレスカウンタ１．
１ビツトリバース回路２の出力、アクセスされるデータ
届、ウェイトベクトルを表にしたものである。
各ステップ■、ＩＩ、■におけるアドレスカウンタ１．
１ビツトリバース回路２の出力、アクセスされるデータ
届、ウェイトベクトルを表にしたものである。
表１
表２
表３
ステップ■では、アドレスカウンタ１のビットＡＯとＡ
２が１ピツトリパ一ト回路２でリバース（変換）され、
メモリ３のデータペアχ（０）と工（４）、工（２）と
χ（６）、工（１）とχ（５） 、 Ｉ（３）と工（７
）が順にアクセスされ、一方、このときウェイトカウン
タ４によりウェイトテーブル５のウェイトベクトルＷ０
が常にアクセスされで、制御・演算回路６で各データペ
アについでバタフライ演算が行なわれ、結果がメモリ３
に格納される。
２が１ピツトリパ一ト回路２でリバース（変換）され、
メモリ３のデータペアχ（０）と工（４）、工（２）と
χ（６）、工（１）とχ（５） 、 Ｉ（３）と工（７
）が順にアクセスされ、一方、このときウェイトカウン
タ４によりウェイトテーブル５のウェイトベクトルＷ０
が常にアクセスされで、制御・演算回路６で各データペ
アについでバタフライ演算が行なわれ、結果がメモリ３
に格納される。
ステップＩＩては、アドレスカウンタ１のビットＡＯと
Ａ１が１ビ・ントｊノバース回路２でリバースされ、メ
モリ３のデータベアエ（０）とχ（２）、χ（１）とχ
（３）、 ｘ （４）とｘ（６）、χ（５）とχ（７）
が順にアクセスされ、そしてデータエ（３）のアクセス
後にウェイトカウンタ４がインクリメントされてウェイ
トテーブル５のウェイトベクトルＷ“２がアクセスされ
、前と同様にして各データペアについてバタフライ演算
が行なわれ、結果かメモリ３に格納される。
Ａ１が１ビ・ントｊノバース回路２でリバースされ、メ
モリ３のデータベアエ（０）とχ（２）、χ（１）とχ
（３）、 ｘ （４）とｘ（６）、χ（５）とχ（７）
が順にアクセスされ、そしてデータエ（３）のアクセス
後にウェイトカウンタ４がインクリメントされてウェイ
トテーブル５のウェイトベクトルＷ“２がアクセスされ
、前と同様にして各データペアについてバタフライ演算
が行なわれ、結果かメモリ３に格納される。
最終ステップであるステップｍでは、ビットリバースは
行なわれメモリ３の隣同志のデータペアーｔ（０）とχ
（１）、χ（２）と工（３）、 ｘ （５）と工（６）
とχ（７）か順にアクセスされず、一方ウエイトテーブ
ル５のウェイトベクトルは最初にＷＯ、データｘ（１）
のアクセス後にＷ−２、χ（３）のアクセス後にウェイ
トカウンタ４がインクリメントされ、Ｗ゛１、次にＷ−
Ａをと順にアクセスされ、隣同志のデータペアについで
バタフライ演算が行なわれ、結果が全ビット１ノバース
された順序でメモリ３に格納される。
行なわれメモリ３の隣同志のデータペアーｔ（０）とχ
（１）、χ（２）と工（３）、 ｘ （５）と工（６）
とχ（７）か順にアクセスされず、一方ウエイトテーブ
ル５のウェイトベクトルは最初にＷＯ、データｘ（１）
のアクセス後にＷ−２、χ（３）のアクセス後にウェイ
トカウンタ４がインクリメントされ、Ｗ゛１、次にＷ−
Ａをと順にアクセスされ、隣同志のデータペアについで
バタフライ演算が行なわれ、結果が全ビット１ノバース
された順序でメモリ３に格納される。
この後、メモ１ノ３（こあるＦＦＴ演算が終了した結果
は制御・演算回路６により全ビットリバースされで正し
い順序に並べ換えでメモリ８（ご転送され、制御・演算
回路９へ処理か受は渡される。制御・演算回路９はメモ
リ８にあＦＦＴ結果をデータとして、ＩＦＦＴ、絶対値
／位相演算、スペクトル演算等の処理を行なう。
は制御・演算回路６により全ビットリバースされで正し
い順序に並べ換えでメモリ８（ご転送され、制御・演算
回路９へ処理か受は渡される。制御・演算回路９はメモ
リ８にあＦＦＴ結果をデータとして、ＩＦＦＴ、絶対値
／位相演算、スペクトル演算等の処理を行なう。
なあ、データ数Ｎ（＝２Ｌ）が多くなった場合、演算ス
テップでのビット交換は、上位ビットから順番に、２Ｌ
−１、２１−２，・・・２０の順序で１回ステップあり
、それぞれＮ／２回のバタフライ演算を行なうことで完
了する。また、メモリ８へメモリ３のデータを転送する
際のデータのアドレスの全ビットリバースは制御・演算
回路６で行なってもよい。
テップでのビット交換は、上位ビットから順番に、２Ｌ
−１、２１−２，・・・２０の順序で１回ステップあり
、それぞれＮ／２回のバタフライ演算を行なうことで完
了する。また、メモリ８へメモリ３のデータを転送する
際のデータのアドレスの全ビットリバースは制御・演算
回路６で行なってもよい。
以上説明したように本発明は、従来のような事前のデー
タの並べ換えを行なわずにメモリのアドレスを１ビツト
リバースすることにより、データを高速に順序良くアク
セスし、同時にウェイトテーブルも簡単にアクセスしＵ
ＦＦＴ演算を高速行なうことかでき、また、装置をＦ
ＦＴ演四行なう装置として次の処理を行なう装置に分罵
りし、かつ、これらをパイプライン的に接続してデータ
の受は渡しを行なうことにより、高速なリアルタイム処
理が可能となる効果かある。
タの並べ換えを行なわずにメモリのアドレスを１ビツト
リバースすることにより、データを高速に順序良くアク
セスし、同時にウェイトテーブルも簡単にアクセスしＵ
ＦＦＴ演算を高速行なうことかでき、また、装置をＦ
ＦＴ演四行なう装置として次の処理を行なう装置に分罵
りし、かつ、これらをパイプライン的に接続してデータ
の受は渡しを行なうことにより、高速なリアルタイム処
理が可能となる効果かある。
第１図は本発明の高速フーリエ変換装置の一大施例のプ
ロ・ンク図、第２図は第１図の高速ノー１ノ工変換装百
にあけるバタフライ演算の過程を示す図、第３図（よバ
タフライ演算の模式図、第４図（ａ）は従来例の高速フ
ーリエ変換装置にお１ブるバタフライ演算の過程を示す
図、第４図（ｂ）はそのウェイトベクトルのベクトル図
である。 １・・・アドレスカウンタ、 ２・・・］ビットリバース回路、 ３．８・・・メモｌノ、 ４・・・ウェイトカウンタ、 ５・・・ウェイトテーブル、 ６．９・・・制御・演算回路、 ７・・・マルチプレクサ。
ロ・ンク図、第２図は第１図の高速ノー１ノ工変換装百
にあけるバタフライ演算の過程を示す図、第３図（よバ
タフライ演算の模式図、第４図（ａ）は従来例の高速フ
ーリエ変換装置にお１ブるバタフライ演算の過程を示す
図、第４図（ｂ）はそのウェイトベクトルのベクトル図
である。 １・・・アドレスカウンタ、 ２・・・］ビットリバース回路、 ３．８・・・メモｌノ、 ４・・・ウェイトカウンタ、 ５・・・ウェイトテーブル、 ６．９・・・制御・演算回路、 ７・・・マルチプレクサ。
Claims (1)
- 【特許請求の範囲】 データが時系列に格納されている第１のメモリのアドレ
スの最下位ビットと上位ビットをリバースして、前記デ
ータをアクセスしバタフライ演算を行なう第１の装置と
、 第１のメモリの演算結果が、そのデータの個数に応じて
、アドレスが全ビットリバースされて格納される第２の
メモリを備え、第１、第２のメモリを介して第１の装置
とパイプライン的に接続され、第２のメモリのデータに
よりバタフライ演算の次の処理を行なう第２の装置を有
する高速フーリエ変換装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP17698285A JPS6237776A (ja) | 1985-08-13 | 1985-08-13 | 高速フ−リエ変換装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP17698285A JPS6237776A (ja) | 1985-08-13 | 1985-08-13 | 高速フ−リエ変換装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS6237776A true JPS6237776A (ja) | 1987-02-18 |
Family
ID=16023108
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP17698285A Pending JPS6237776A (ja) | 1985-08-13 | 1985-08-13 | 高速フ−リエ変換装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6237776A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02101574A (ja) * | 1988-10-11 | 1990-04-13 | Jeol Ltd | 大容量高速フーリエ変換装置 |
| JPH03282451A (ja) * | 1990-03-30 | 1991-12-12 | Mitsubishi Paper Mills Ltd | 帯電防止されたハロゲン化銀写真感光材料 |
-
1985
- 1985-08-13 JP JP17698285A patent/JPS6237776A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02101574A (ja) * | 1988-10-11 | 1990-04-13 | Jeol Ltd | 大容量高速フーリエ変換装置 |
| JPH03282451A (ja) * | 1990-03-30 | 1991-12-12 | Mitsubishi Paper Mills Ltd | 帯電防止されたハロゲン化銀写真感光材料 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0248906B1 (en) | Multi-port memory system | |
| JP5689282B2 (ja) | 行列をｓｉｍｄマルチコア・プロセッサ・アーキテクチャ上で転置するためのコンピュータ実装方法、コンピュータ可読ストレージ媒体及びシステム | |
| JP3749022B2 (ja) | 高速フーリエ変換を用いて短い待ち時間でアレイ処理を行う並列システム | |
| WO2008103885A2 (en) | Parallel architecture for matrix transposition | |
| US20150006604A1 (en) | Method and apparatus for performing a fft computation | |
| CN112464296B (zh) | 一种用于同态加密技术的大整数乘法器硬件电路 | |
| JPH0479026B2 (ja) | ||
| JPH06274528A (ja) | ベクトル演算処理装置 | |
| JPS6237776A (ja) | 高速フ−リエ変換装置 | |
| JPH04256130A (ja) | ファジィ制御用演算回路 | |
| USH570H (en) | Fast Fourier transform data address pre-scrambler circuit | |
| CN111368250A (zh) | 基于傅里叶变换/逆变换的数据处理系统、方法及设备 | |
| CN114861125A (zh) | 一种快速傅里叶变换和逆变换的实现方法 | |
| US20250173091A1 (en) | Processing architecture supporting an out of order number theoretic transform | |
| CN114116012B (zh) | 基于混洗操作的fft码位反序算法向量化实现方法及装置 | |
| US6772183B1 (en) | Device for converting input data to output data using plural converters | |
| CN118820655B (zh) | 用于数论变换的硬件实现方法、装置及安全芯片 | |
| CN101266594A (zh) | 利用cooley-tukey演算法以完成n点离散傅立叶转换的装置 | |
| JPS61184781A (ja) | アドレス・デコ−ダ | |
| JP3296489B2 (ja) | 連想メモリ装置における演算方法 | |
| JPH03100863A (ja) | Ｆｆｔ演算方式及び装置 | |
| JPS60144876A (ja) | ベクトル要素間演算装置 | |
| CN119556884A (zh) | 一种并发常几何的数论变换结构 | |
| JPS63198144A (ja) | マルチポ−トメモリにおけるダイレクトメモリアクセス制御方式 | |
| CN118051709A (zh) | 一种fft处理器及运算方法 |