JPS62221071A - バタフライ演算回路及びそれを用いた高速フ−リエ変換装置 - Google Patents
バタフライ演算回路及びそれを用いた高速フ−リエ変換装置Info
- Publication number
- JPS62221071A JPS62221071A JP61063097A JP6309786A JPS62221071A JP S62221071 A JPS62221071 A JP S62221071A JP 61063097 A JP61063097 A JP 61063097A JP 6309786 A JP6309786 A JP 6309786A JP S62221071 A JPS62221071 A JP S62221071A
- Authority
- JP
- Japan
- Prior art keywords
- circuit
- addition
- butterfly
- fourier transform
- redundant binary
- 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
- 238000004364 calculation method Methods 0.000 claims description 48
- 238000000034 method Methods 0.000 claims description 11
- 230000008569 process Effects 0.000 claims description 5
- 230000001902 propagating effect Effects 0.000 claims description 2
- 238000007792 addition Methods 0.000 description 32
- 230000000295 complement effect Effects 0.000 description 13
- 238000010586 diagram Methods 0.000 description 9
- 238000006243 chemical reaction Methods 0.000 description 6
- 229910002056 binary alloy Inorganic materials 0.000 description 4
- 230000006870 function Effects 0.000 description 4
- 238000005070 sampling Methods 0.000 description 4
- 230000000694 effects Effects 0.000 description 2
- 238000011156 evaluation Methods 0.000 description 2
- 230000008859 change Effects 0.000 description 1
- 230000000737 periodic effect Effects 0.000 description 1
- 230000000644 propagated effect Effects 0.000 description 1
- 230000008707 rearrangement Effects 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
Landscapes
- Complex Calculations (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
本発明は、バタフライ演算回路及びそれを用いた高速フ
ーリエ変換装置に関する。
ーリエ変換装置に関する。
時間領域で定義された関数とそのフーリエ変換によって
得られた周波数領域の関数とが共に周期関数の時は、そ
れらの関数は共に、有限要素の離散的なサンプリング値
系列で表現される。そして、両者の間には、良く知られ
たように、離散的フーリエ変換及び逆変換で定義される
関係が存在する。 高速フーリエ変換（以下ｒＦＦＴＪと言う）は、上記の
離散的フーリエ変換または逆変換を行うに際し、乗算、
加減算の回数を減少させ、変換速度を向上させる方法と
して良く知られている。その演算は、バタフライ演算を
基本演算として多数回繰り返すことにより達成される。 係るバタフライ演算回路をハードウェアとして構成する
ことは知られている。このバタフライ演算回路は、−回
の複素数乗算回路、−回の複素数加算回路及び−回の複
素数減算回路で構成されている。また、係るバタフライ
演算回路を基本回路とするＦＦＴハードウェアも、１つ
のバタフライ演算回路を用いてデータ処理を時系列的に
逐次行う逐次処理型、ｍ役の処理をそれぞれ別のバタフ
ライ演算回路で実行しパイプライン処理が可能なように
縦続接続した縦続処理型、入力点数の半分のバタフライ
演算回路を並列に配し一段分の処理を一度に行うように
した並列処理型及び並列配列と縦続配列とを組合せバタ
フライ演算回路を網目状に構成した２次元並列処理型が
知られている。
得られた周波数領域の関数とが共に周期関数の時は、そ
れらの関数は共に、有限要素の離散的なサンプリング値
系列で表現される。そして、両者の間には、良く知られ
たように、離散的フーリエ変換及び逆変換で定義される
関係が存在する。 高速フーリエ変換（以下ｒＦＦＴＪと言う）は、上記の
離散的フーリエ変換または逆変換を行うに際し、乗算、
加減算の回数を減少させ、変換速度を向上させる方法と
して良く知られている。その演算は、バタフライ演算を
基本演算として多数回繰り返すことにより達成される。 係るバタフライ演算回路をハードウェアとして構成する
ことは知られている。このバタフライ演算回路は、−回
の複素数乗算回路、−回の複素数加算回路及び−回の複
素数減算回路で構成されている。また、係るバタフライ
演算回路を基本回路とするＦＦＴハードウェアも、１つ
のバタフライ演算回路を用いてデータ処理を時系列的に
逐次行う逐次処理型、ｍ役の処理をそれぞれ別のバタフ
ライ演算回路で実行しパイプライン処理が可能なように
縦続接続した縦続処理型、入力点数の半分のバタフライ
演算回路を並列に配し一段分の処理を一度に行うように
した並列処理型及び並列配列と縦続配列とを組合せバタ
フライ演算回路を網目状に構成した２次元並列処理型が
知られている。
上記何れの型のＦＦＴハードウェアであっても、演算方
式には、符号付き２進数または２の補数表現の２進数に
よる方式が採用されている。バタフライ演算回路に於け
る加算器には、リップルキャリア加算器（以下ｒＲＣＡ
Ｊと略記する）、桁上げ先見加算器（以下ｒＣＬＡＪと
略記する）が一般的に使用されそいる。このＲＣＡは各
桁の構成が同一となるので、ＩＣ化のパターン設計が容
易であるが、下位からの桁上げが上位桁に伝搬するため
、計算時間は加算桁数に比例して増加すると言う欠点が
ある。又ＣＬＡは、加算時間は加算桁数の対数に比例し
て増加するが、上位桁程回路構成が複雑となり、ＩＣ化
の際のパターン設計が複雑になると言う欠点がある。係
る欠点は、そのままバタフライ演算回路、ＦＦＴ装置の
欠点として存在している。即ち、高速演算を実現するに
は、回路構成が複雑になると言う欠点が存在する。さら
に、ＦＦＴをよりリアルタイムに行うため、より高速の
ＦＦＴ装置の実現が要望されている。 本発明は上記の観点に立ってなされたものであり、その
目的とするところは、バタフライ演算回路、ＦＦＴ装置
の演算速度を向上させることにある。
式には、符号付き２進数または２の補数表現の２進数に
よる方式が採用されている。バタフライ演算回路に於け
る加算器には、リップルキャリア加算器（以下ｒＲＣＡ
Ｊと略記する）、桁上げ先見加算器（以下ｒＣＬＡＪと
略記する）が一般的に使用されそいる。このＲＣＡは各
桁の構成が同一となるので、ＩＣ化のパターン設計が容
易であるが、下位からの桁上げが上位桁に伝搬するため
、計算時間は加算桁数に比例して増加すると言う欠点が
ある。又ＣＬＡは、加算時間は加算桁数の対数に比例し
て増加するが、上位桁程回路構成が複雑となり、ＩＣ化
の際のパターン設計が複雑になると言う欠点がある。係
る欠点は、そのままバタフライ演算回路、ＦＦＴ装置の
欠点として存在している。即ち、高速演算を実現するに
は、回路構成が複雑になると言う欠点が存在する。さら
に、ＦＦＴをよりリアルタイムに行うため、より高速の
ＦＦＴ装置の実現が要望されている。 本発明は上記の観点に立ってなされたものであり、その
目的とするところは、バタフライ演算回路、ＦＦＴ装置
の演算速度を向上させることにある。
本発明は、入力データに回転因子を掛けたデー夕を出力
する乗算回路と、２つの入力データの和と差を演算して
求められたデータを出力する加減算回路と、からなるバ
タフライ演算回路において、前記乗算回路に於ける部分
積発生回路は、その入力データである被乗数を冗長２進
数として処理し部分積を冗長２進数として出力するもの
であり、５ 前記乗算回路に於ける部分積の和の演算
回路と前記加減算回路とを、冗長２進数による加算演算
により桁上げが上位桁に伝搬しない冗長２進加算回路で
構成したことを特徴とする高速フーリエ変換装置用バタ
フライ演算回路と、該バタフライ演算回路を基本回路と
して含む高速フーリエ変換装置である。
する乗算回路と、２つの入力データの和と差を演算して
求められたデータを出力する加減算回路と、からなるバ
タフライ演算回路において、前記乗算回路に於ける部分
積発生回路は、その入力データである被乗数を冗長２進
数として処理し部分積を冗長２進数として出力するもの
であり、５ 前記乗算回路に於ける部分積の和の演算
回路と前記加減算回路とを、冗長２進数による加算演算
により桁上げが上位桁に伝搬しない冗長２進加算回路で
構成したことを特徴とする高速フーリエ変換装置用バタ
フライ演算回路と、該バタフライ演算回路を基本回路と
して含む高速フーリエ変換装置である。
バタフライ演算回路は、１回の複素数乗算と１回の複素
数加算と１回の複素数減算を行う。複素数演算は、実際
は、実部と虚部に分けて演算されるので、１つの出力デ
ータの実部を得るのに、信号の流れに沿って１段の実数
乗算と２段の実数加減算を必要とする。また、実数乗算
は部分積の和として求められるため、バタフライ演算回
路は、多くの加算回路（減算は、加算回路で実行出来る
ので、以下、減算回路を含めて加算回路とも言う）を必
要とする。本発明は、バタフライ演算回路の入力、出力
データを全て、冗長２進数で取り扱い、実数乗算、実数
加算を全て、冗長２進数による演算で実行している。冗
長２進数演算による加算回路では、下位桁の桁上げが上
位桁に伝搬しないように、各桁の和を表現することが出
来る。 即ち、各桁の和を中間桁上げと中間和の２桁で表現する
第１の演算と、下位桁からの中間桁上げと中間和との加
算を行う第２の演算との２回の演算で加算が終了するよ
うにする事が出来る。この結果、演算時間は、桁数に関
係なく、係る冗長２進加算回路を構成する素子の論理段
数によって決定される。したがって、加算演算の速度が
向上するため、バタフライ演算及び、ＦＦＴの速度が向
上する。また、上記の冗長２進加算回路は、各桁を同一
構成とすることが出来るため、ＩＣ化に適している。
数加算と１回の複素数減算を行う。複素数演算は、実際
は、実部と虚部に分けて演算されるので、１つの出力デ
ータの実部を得るのに、信号の流れに沿って１段の実数
乗算と２段の実数加減算を必要とする。また、実数乗算
は部分積の和として求められるため、バタフライ演算回
路は、多くの加算回路（減算は、加算回路で実行出来る
ので、以下、減算回路を含めて加算回路とも言う）を必
要とする。本発明は、バタフライ演算回路の入力、出力
データを全て、冗長２進数で取り扱い、実数乗算、実数
加算を全て、冗長２進数による演算で実行している。冗
長２進数演算による加算回路では、下位桁の桁上げが上
位桁に伝搬しないように、各桁の和を表現することが出
来る。 即ち、各桁の和を中間桁上げと中間和の２桁で表現する
第１の演算と、下位桁からの中間桁上げと中間和との加
算を行う第２の演算との２回の演算で加算が終了するよ
うにする事が出来る。この結果、演算時間は、桁数に関
係なく、係る冗長２進加算回路を構成する素子の論理段
数によって決定される。したがって、加算演算の速度が
向上するため、バタフライ演算及び、ＦＦＴの速度が向
上する。また、上記の冗長２進加算回路は、各桁を同一
構成とすることが出来るため、ＩＣ化に適している。
以下本発明を具体的な実施例に基づいて説明する。
（１）定義
本実施例のＦＦＴ装置は、入力データとして、Ｎ点のサ
ンプリング値系列（Ｘ、・・・Ｘ、）を入力し、フーリ
エ変換して、Ｎ点のサンプリング値系列（Ｙ ＋・・・
Ｙ、）を出力データとして出力する。 入出力データは、２の補数表現の１桁の２進数で表現さ
れている。２の補数表現の１桁の２進数Ｃａｎ−＋ ａ
ｎ−ｚ −ａｎ ］ ｅ２では、最上位の第１桁は、−
２′−１の重みを、その他の第１桁は２′−１の重みを
有し、ａ、は（０，１）をとる。ＦＦＴ装置の内部では
、冗長２進数が用いられている。 １桁の冗長２進数Ｃａｈ−＋ ａｎ−ｘ ”’ａｏ ）
Ｒ２は、ｉｉ桁が２１−１の重みを有し、ａ、は（−
１，０゜１）をとる数として定義される。又、冗長２進
数を２進化するため、冗長２進数の１桁は、２進数の２
ビツトで表し、 Ｃａ＋ ３１１＝ ［：ａｓ’ｔａｄｌ］ｘ
ンプリング値系列（Ｘ、・・・Ｘ、）を入力し、フーリ
エ変換して、Ｎ点のサンプリング値系列（Ｙ ＋・・・
Ｙ、）を出力データとして出力する。 入出力データは、２の補数表現の１桁の２進数で表現さ
れている。２の補数表現の１桁の２進数Ｃａｎ−＋ ａ
ｎ−ｚ −ａｎ ］ ｅ２では、最上位の第１桁は、−
２′−１の重みを、その他の第１桁は２′−１の重みを
有し、ａ、は（０，１）をとる。ＦＦＴ装置の内部では
、冗長２進数が用いられている。 １桁の冗長２進数Ｃａｈ−＋ ａｎ−ｘ ”’ａｏ ）
Ｒ２は、ｉｉ桁が２１−１の重みを有し、ａ、は（−
１，０゜１）をとる数として定義される。又、冗長２進
数を２進化するため、冗長２進数の１桁は、２進数の２
ビツトで表し、 Ｃａ＋ ３１１＝ ［：ａｓ’ｔａｄｌ］ｘ
〔０〕１＝
〔００〕２
〔１〕 Ｒ□＝［０１）２
（−１） Ｒ，＝ ｌ”ｌ ０１ 。
とする。このように２進数で表された冗長２進数を以下
２進化冗長２進数と言う。 離散的フーリエ変換とその逆変換は、次式で定義される
。 回転因子Ｗを次式で定義する。 Ｗ ＝ ｅｘｐ（−ｊ２π／Ｎ） バタフライ演算回路は、２つの入力Δ、Ｂに対し２つの
出力Ｃ，Ｄを出力するものとし、それらの関係は次式で
定義される。 Ｃ＝Ａ＋Ｂ−ＷＫ Ｄ＝Ａ−Ｂ−ＷＫ 更に、ＡＳＢ、Ｃ，Ｄを複素数とし、それらの実部、虚
部を添字Ｒ１■を付けて表せば、それらには、次の関係
式が成立する。 Ｃ□＝Ａｉ＋Ｂ＋＋ＣＯ３φ＋Ｂ、ＳＩＮφＣ＋ ＝
Ａｔ −Ｂｉ ＳＩＮφ＋ＢＸ ＣＯＳφＤア ＝
Ａ、−ＢＩＩ ＣＯ３φ−Ｂ！ ＳＩＮφＤ、＝Ａ□
十Ｂ、ＳＩＮφ−Ｂ、ＣＯＳφ但し、ｗ’＝ｃｏｓφ−
ｊ ＳＩＮφ である。 （２）全体の構成 第１図は、実施例に係るＦＦＴ装置の構成を示したブロ
ックダイヤグラムである。１は、Ｎ点の入力データを入
力して、所定の並べ換えを行い各データを２進化冗長２
進数に変換してＦＦＴ演算部２に出力するデータ入力部
である。２は、バタフライ演算回路を網目状に配列した
ＦＦＴ演算部である。ＦＦＴ演算部２は、Ｎ点の入力デ
ータからフーリエ変換を行いＮ点の出力データを生成す
る。３は、ＦＦＴ演算部２から出力された２進化冗長２
進数の出力データを２の補数表現の２進数に変換し、Ｎ
点データを順次出力するデータ出力部である。 （３）データ入力部 データ入力部１は、時空間でのアナログ信号をサンプリ
ングしディジタル信号に変換するＡ／Ｄ変換器１１と、
サンプリングのタイミングを付与する入力制御部１４と
、Ｎ点のディジタルデータを順次所定のアドレスに入力
する入力バッファ１２と、入力制御部１４からタイミン
グ信号を入力し順次入力バッファ１２のアドレスを決定
するカウンタ１５と、入力バッファ１３に入力された２
進数を２進化冗長２進数に変換する冗長２進変換部１３
とから戊る。大力バッファ１２は、Ｎ点のデータを記憶
するバッファレジスタＢＸ、〜ＢＸ８を有している。カ
ウンタ１５はＮ進カウンタであり、入力制御部１４から
タイミング信号を入力する毎に更新され、その出力はビ
ットの上位方向を下位方向に逆転して、入力バッファ１
２のアドレス信号とされる。その結果、Ｎ点データは、
所定の順序で並べ換えられて、レジスタＢＸ、−Ｂｘ８
に記憶される。冗長２進変換部１３の１デ一タ単位は、
第２図に示すように構成されている。 ２の補数表現の２進数は、最上位桁が一２″−１の重み
を有した冗長２進数と見ることが出来る。即ち、最上位
桁は、符号を反転し、その他の桁はそのまま出力するこ
とで冗長２進数に変換することが出来る。したがって、
レジスタＢＸ、の最上位桁を除（桁は、その出力を２進
化冗長２進数の各桁の下位ピッ）ａｄｏ〜ａｄ、−２と
し、最上位桁の出力は、上位ビットａｓｎ−１とし、他
のビットａＳＯ〜ａｓａ−２、ａｄＩ、−１は、０とす
れば２進化冗長２進数が得られる。 （４）データ出力部 データ出力部３は、２進化冗長２進数を２の補数表現の
２進数に変換する２進変換部３１と、バッファレジスタ
Ｂ Ｙ ＋〜Ｂ Ｙ Ｈから成る出力バッファ３２と、
出力制御部３３、カウンタ３４とから成る。２進変換部
３１の１デ一タ単位は、第３図に示すように構成されて
いる。冗長２進数を２の補数表現の２進数に変換するに
は、冗長２進数を正の要素から成る２進数と、負の要素
から成る２進数に分割し、それらの２進演算での差を求
めれば良い。２進化冗長２進数の各桁の下位ビット列か
ら成る２進数（ａ ｄｆｉ−１〜ａｄｏ）２は正の要素
から成る２進数を表しており、各桁の上位ビット列から
成る２進数（ａ ｌｌｌ＋−１”” ａ ｍ。）、は、
負の要素から成る２進数を表している。したがって、上
記２進数を減゛算すれば、２進数に変換する事が出来る
。この時、減算は、２の補数表現の２進数の加算として
演算出来るので、２の補数表現の２進数（Ｏａ ｄｒ＋
−１〜ａ ｄｏ） ｃ２と２の補数表現の２進数（ｌａ
ｗｎ−ｔ〜Ｎ５ｌＩ）ｅ２＋ （１） ｃ２の加算によ
り、求める事が出来る。だだし、Ｎｓｉはａ□を反転し
た値である。又、加数と被加数の最上位ビットの、Ｏと
１は、２の補数表現での符号ビットであり、この時得ら
れる和の最上位桁ｂ１は、符号ビットとなる。 変換後のデータは出力バッファ３２に出力され、出力制
御部３３により更新されるカウンタ３４によって出力バ
ッファ３２のアドレスが選択されて、サンプリング値系
列データＹ１〜ＹＮが順次出力される。 （５）ＦＦＴ演算部 （ａ）ＦＦＴ演算部 ＦＦＴ演算部２は、バタフライ演算回路をＮ／２ （＝
ｖ）個並列に配置したステージをｌｏｇ、 Ｎ（＝Ｕ）
段縦続に接続した網目状の構造をしている。その接続関
係は、８点データの場合には、第４図に示すようになる
。この場合には、全体が３ステージで構成され、１ステ
ージ当たり４個のバタフライ演算回路で構成されている
。 （ｂ）バタフライ演算回路 １つのバタフライ演算回路は、第５図に示すように回転
因子Ｗの乗算を行う乗算回路２１と、その出力と入力Ａ
との加算演算を行う加算回路２２と、入力Ａから乗算回
路２１の出力を減する減算回路２３と、で構成されてい
る。その結果、入力に関し所定の関係を有した出力が得
られる。第５図の例は、時間間引きの例であるが、２人
力の和と差を求め、差に回転因子を乗するという周波数
間引きで構成しても良い。 バタフライ演算回路の入力、出力データは、複素数であ
るので、実部と虚部とに分けて演算される。具体的には
、第６図に示すように構成される。 入力Δ、Ｂのデータは、それぞれ、Ａ人カバッファ、Ｂ
人カバッファに入力される。２４は、回転因子に関する
データを記憶したメモリである。Ｂ人カバッファのデー
タと回転因子との乗算の結果、Ｓｌ、Ｓ２、Ｓ３、Ｓ４
には、それぞれ、Ｂ、ＣＯ３−、Ｂ、ＳＩＮφ、ＢｔＣ
Ｏ３φ、Ｂ、ＳＩＮφが出力される。又Ｓ５、Ｓ６には
、加減算結果、Ｂ１ＣＯ３φ十Ｂ＋ＳＩＮφ、Ｂ、ＣＯ
Ｓφ−Ｂ＊ＳＩＮφが出力される。更に、Ｓ７、Ｓ８、
Ｓ９、ＳＩＯには、加減算の結果、 Ａｌｌ＋ＢＲＣＯ３φ＋ＢＩＳＩＮφ Ａｔ−ＢヮＳＩＮφ＋Ｂ、ＣＯＳφ Ａ、−ＢＩＣＯＳφ−ＢｆＳＩＮφ Ａ□十Ｂ、ＳＩＮφ−Ｂ、ＣＯＳφ がそれぞれ、出力され、Ｃ出力バッファとＤ出力バッフ
ァに、Ｃｍ 、Ｃｔ 、ＤＲ、Ｄｔが得られる。 ２５ａ〜２５ｄは、上位桁処理回路である。バタフライ
演算回路の冗長２進数の出力は、また、他のバタフライ
演算回路の冗長２進数の入力となる。したがって、入力
、出力の有効桁数を一致させる必要がある。ところが、
冗長２進数で加算すると桁上げ処理を伴うため、１回の
加算毎に桁数が１増加する。したがって、有効桁数を一
定にするため、増加した上位桁を減縮する操作が必要と
なる。上位桁処理回路は、増加した桁数＋１桁の上位桁
を１桁に減縮する処理を行うものである。 ２６ａ〜２６ｄは、シフタ回路である。入出力の有効桁
数を一致させ演算精度を高めるために、場合により、２
で割った値（１桁下位ヘシフトする）を出力する。係る
場合には、シフタ回路を作動させて１／２のデータを出
力するようにしている。 （ｂ）乗算回路 乗算回路の構成は、第７図に示す様になっている。この
乗算回路は、２ビットブースの方法により、部分積を求
めている。この乗算回路では、被乗数は２進化冗長２進
数で、乗数は２の補数表現の２進数で与えられている。 １２桁演算の場合、６個の部分積が発生゛し、それらは
、第１部分積発生回路４１〜第６部分積発生回路４６で
並列的に発生される。そして、各部分積は、２個づつ３
個の部分積加算回路（５１〜５３）で並列的に一次加算
される。部分積加算回路５１と５２の加算結果は、部分
積加算回路６１で２次加算される。次に、部分積加算回
路５３と６１の出力が部分積加算回路７１で３次加算さ
れる。この時、上位から２桁は、冗長２進数による加算
を行った為に発生した桁であり、上位から３桁が１桁に
変換されて、出力される。 部分積発生回路は、第８図に具体的に示されている。Ａ
は乗数の解読部である。第１部分積では、−２Ｃ２！、
ｌ＋ Ｃｘ□＋Ｃ２１−１が計算される。この結果の採
り得る値は、（−２，−１，０，１，２）である。０の
時は、０の出力、１の時は、被乗数をそのまま出力、２
の時は、被乗数を上位方向に１桁シフトして出力、−１
の時は、被乗数の各ビットのレベルを反転して出力し、
−２の時は、被乗数を上位方向に２桁シフトしてさらに
それを反転して出力する事により部分積が発生される。 図には、第３部分積発生回路が図示されている。乗数の
第５．６．７ビツトＣ，、Ｃｓ 、Ｃ，が解読され、−
２の時は、Ｆ３４が高レベルとなり、被乗数（Ｉ 、、
、 Ｉ 、ｐ）が（Ｐ ｄｐ＋ｌ ＋ Ｐ ｓｐ＋１
）として出力される。２の時は、Ｆ１ａが高レベルとな
り、被乗数（Ｉ ｌｉｐ＋ Ｉ 、、）が（Ｐ ｓｐ＋
Ｉ ｒ Ｐ ｄＰや、）として出力される。また、−
１の時は、Ｆ３２が高レベルとなり、被乗数（Ｉ −Ｐ
、 Ｉ ｄｐ）が（ＰｄＰ、Ｐｓｐ）として出力される
。又、１の時は、Ｆ３１が高レベルとなり、被乗数（Ｉ
−Ｐ、 Ｉ 、−）が（Ｐ、、。 Ｐ、、）として出力される。 各部分積の出力端子は、第７図に示す様に桁合わせを行
い、各桁を横方向に配列した構造になっている。 係る部分積は、冗長２進加算器により、本状に順次加算
される。本例では加算器は３役に構成されている。 （ｃ）加算回路 加算回路は、２進化冗長２進数の加算を行うものであり
、その１桁の構成が第９図、第１０図に示されている。 第１０図は、第９図の論理回路を更に簡約したものであ
る。 冗長２進数による加算では、冗長度を利用して、下位桁
からの桁上げが伝搬しないように構成する事が出来る。 したがって、加算は各桁の和（以下この和を２桁で表し
、上位桁を「中間桁上げ」、下位桁を「中間和」と言う
）を求める第１ステツプと、中間和と下位桁の中間桁上
げとの和を各桁で計算する第２ステツプとの２段階で求
める事が出来る。即ち、第２ステツプの演算の時、さら
に桁上げが生じないように、第１ステツプでの中間和と
中間桁上げの表現を工夫している。発生される中間和と
中間桁上げを第１表に示す。１．３．４．６の場合には
、中間桁上げと中間和の表現方法は一意的であるが、下
位桁からどの様な桁上げがあっても、第２ステツプの演
算で桁上げが発生することはない。２と５の場合は、中
間桁上げと中間和の表現方法は一意的ではないが、表現
方法によっては、第２ステツプの演算で、さらに、桁上
げが発生する場合がある。ところが、下位桁の状態を判
別し、その状態に応じて、表のように表現すれば、第２
ステツプの演算で桁上げが発生することはない。即ち、
２．５の場合、下位桁から−１の桁上げが発生する可能
性がある場合には、中間和を１にしておき、下位桁から
１の桁上げが発生する可能性がある時には、中間和を−
１とすることで、第２ステツプの演算で桁上げが発生し
ないようにすることが出来る。 第９図は、係る演算を実行するための第１桁目の回路で
ある。Ｓ！１は、１桁下位の加数、被加数の状態を示す
ものであり、少なくとも一方が負の時、低レベルとなる
信号である。被加数は（ａｉ１＋ａｄｌ）であり、加数
は、（ｂ＠＋、 ｂｄｔ）であり、加算結果は、（Ｚａ
□＋Ｚｄｆ）である。いずれも、２進化冗長２進数であ
る。又、（’： ａｔ、 ＝ ａ□）は、中間桁上げを
２進化冗長２進数（負論理）で表現したものである。 係る１桁の加算器を第１１図のように接続すれば、Ｎ桁
の冗長２進加算器が構成出来る。 （６）評価 １個のバタフライ演算回路に於けるトランジスタ素子数
と論理段数を２の補数表現の２進数方式と、冗長２進数
方式で対比した結果を第２表に示す。トランジスタはＣ
ＭＯＳで評価し、第６図の回路で評価した。冗長２進方
式は、ビット数が増えても、論理段数が変化しないと言
う特徴があり、ビット数に拘わらず、演算速度を一定に
することが出来る。１０２４点データ入力の場合には、
バタフライ演算回路は１０段必要になり、ＦＦＴ演算部
を３８０段の論理段数で構成出来る。又出力の２進数変
換部の８段を含めて、全体で３８８段で装置を構成出来
る。係る段数は、１６ビツトで２進数方式の１７２以下
にする事が出来、したがって、変換速度を１７２以下に
する事が出来る。 （７）他の実施例 第１２図にその構成が示されている。ＦＦＴ演算部２は
、Ｎ／２個の１段の並列配列のバタフライ演算回路Ｂ、
〜Ｂ Ｈ／２で構成されている。１段の処理の終了後、
Ｎ点の出力データはシフタ回路８、マルチプレクサ９を
介して、ＦＦＴ演算回路に再度入力する。係る演算を所
定段数分実行してＦＦＴが行われる。シフタ回路８は、
各段での演算のための入力データの組合せを制御するた
めの回路であり、その具体的な１ビツトの構成が第１３
図に示されている。図は入力データ点数６４の場合であ
る。バタフライ演算回路の２出力の一方は、必ず、同一
演算回路の一方に入力させることが出来るので、シフタ
回路の入力出力端子数は３２個である。制御信号Ｃ５〜
Ｃ６が、それぞれ、各段の演算の終了後に入力され、そ
の段の出力データが、次の段の入力データとなるように
ゲートを切り換えてデータの流れが制御されている。 係る構成により、バタフライ演算回路数を入力データ点
数の半分に減少させることが出来る。
２進化冗長２進数と言う。 離散的フーリエ変換とその逆変換は、次式で定義される
。 回転因子Ｗを次式で定義する。 Ｗ ＝ ｅｘｐ（−ｊ２π／Ｎ） バタフライ演算回路は、２つの入力Δ、Ｂに対し２つの
出力Ｃ，Ｄを出力するものとし、それらの関係は次式で
定義される。 Ｃ＝Ａ＋Ｂ−ＷＫ Ｄ＝Ａ−Ｂ−ＷＫ 更に、ＡＳＢ、Ｃ，Ｄを複素数とし、それらの実部、虚
部を添字Ｒ１■を付けて表せば、それらには、次の関係
式が成立する。 Ｃ□＝Ａｉ＋Ｂ＋＋ＣＯ３φ＋Ｂ、ＳＩＮφＣ＋ ＝
Ａｔ −Ｂｉ ＳＩＮφ＋ＢＸ ＣＯＳφＤア ＝
Ａ、−ＢＩＩ ＣＯ３φ−Ｂ！ ＳＩＮφＤ、＝Ａ□
十Ｂ、ＳＩＮφ−Ｂ、ＣＯＳφ但し、ｗ’＝ｃｏｓφ−
ｊ ＳＩＮφ である。 （２）全体の構成 第１図は、実施例に係るＦＦＴ装置の構成を示したブロ
ックダイヤグラムである。１は、Ｎ点の入力データを入
力して、所定の並べ換えを行い各データを２進化冗長２
進数に変換してＦＦＴ演算部２に出力するデータ入力部
である。２は、バタフライ演算回路を網目状に配列した
ＦＦＴ演算部である。ＦＦＴ演算部２は、Ｎ点の入力デ
ータからフーリエ変換を行いＮ点の出力データを生成す
る。３は、ＦＦＴ演算部２から出力された２進化冗長２
進数の出力データを２の補数表現の２進数に変換し、Ｎ
点データを順次出力するデータ出力部である。 （３）データ入力部 データ入力部１は、時空間でのアナログ信号をサンプリ
ングしディジタル信号に変換するＡ／Ｄ変換器１１と、
サンプリングのタイミングを付与する入力制御部１４と
、Ｎ点のディジタルデータを順次所定のアドレスに入力
する入力バッファ１２と、入力制御部１４からタイミン
グ信号を入力し順次入力バッファ１２のアドレスを決定
するカウンタ１５と、入力バッファ１３に入力された２
進数を２進化冗長２進数に変換する冗長２進変換部１３
とから戊る。大力バッファ１２は、Ｎ点のデータを記憶
するバッファレジスタＢＸ、〜ＢＸ８を有している。カ
ウンタ１５はＮ進カウンタであり、入力制御部１４から
タイミング信号を入力する毎に更新され、その出力はビ
ットの上位方向を下位方向に逆転して、入力バッファ１
２のアドレス信号とされる。その結果、Ｎ点データは、
所定の順序で並べ換えられて、レジスタＢＸ、−Ｂｘ８
に記憶される。冗長２進変換部１３の１デ一タ単位は、
第２図に示すように構成されている。 ２の補数表現の２進数は、最上位桁が一２″−１の重み
を有した冗長２進数と見ることが出来る。即ち、最上位
桁は、符号を反転し、その他の桁はそのまま出力するこ
とで冗長２進数に変換することが出来る。したがって、
レジスタＢＸ、の最上位桁を除（桁は、その出力を２進
化冗長２進数の各桁の下位ピッ）ａｄｏ〜ａｄ、−２と
し、最上位桁の出力は、上位ビットａｓｎ−１とし、他
のビットａＳＯ〜ａｓａ−２、ａｄＩ、−１は、０とす
れば２進化冗長２進数が得られる。 （４）データ出力部 データ出力部３は、２進化冗長２進数を２の補数表現の
２進数に変換する２進変換部３１と、バッファレジスタ
Ｂ Ｙ ＋〜Ｂ Ｙ Ｈから成る出力バッファ３２と、
出力制御部３３、カウンタ３４とから成る。２進変換部
３１の１デ一タ単位は、第３図に示すように構成されて
いる。冗長２進数を２の補数表現の２進数に変換するに
は、冗長２進数を正の要素から成る２進数と、負の要素
から成る２進数に分割し、それらの２進演算での差を求
めれば良い。２進化冗長２進数の各桁の下位ビット列か
ら成る２進数（ａ ｄｆｉ−１〜ａｄｏ）２は正の要素
から成る２進数を表しており、各桁の上位ビット列から
成る２進数（ａ ｌｌｌ＋−１”” ａ ｍ。）、は、
負の要素から成る２進数を表している。したがって、上
記２進数を減゛算すれば、２進数に変換する事が出来る
。この時、減算は、２の補数表現の２進数の加算として
演算出来るので、２の補数表現の２進数（Ｏａ ｄｒ＋
−１〜ａ ｄｏ） ｃ２と２の補数表現の２進数（ｌａ
ｗｎ−ｔ〜Ｎ５ｌＩ）ｅ２＋ （１） ｃ２の加算によ
り、求める事が出来る。だだし、Ｎｓｉはａ□を反転し
た値である。又、加数と被加数の最上位ビットの、Ｏと
１は、２の補数表現での符号ビットであり、この時得ら
れる和の最上位桁ｂ１は、符号ビットとなる。 変換後のデータは出力バッファ３２に出力され、出力制
御部３３により更新されるカウンタ３４によって出力バ
ッファ３２のアドレスが選択されて、サンプリング値系
列データＹ１〜ＹＮが順次出力される。 （５）ＦＦＴ演算部 （ａ）ＦＦＴ演算部 ＦＦＴ演算部２は、バタフライ演算回路をＮ／２ （＝
ｖ）個並列に配置したステージをｌｏｇ、 Ｎ（＝Ｕ）
段縦続に接続した網目状の構造をしている。その接続関
係は、８点データの場合には、第４図に示すようになる
。この場合には、全体が３ステージで構成され、１ステ
ージ当たり４個のバタフライ演算回路で構成されている
。 （ｂ）バタフライ演算回路 １つのバタフライ演算回路は、第５図に示すように回転
因子Ｗの乗算を行う乗算回路２１と、その出力と入力Ａ
との加算演算を行う加算回路２２と、入力Ａから乗算回
路２１の出力を減する減算回路２３と、で構成されてい
る。その結果、入力に関し所定の関係を有した出力が得
られる。第５図の例は、時間間引きの例であるが、２人
力の和と差を求め、差に回転因子を乗するという周波数
間引きで構成しても良い。 バタフライ演算回路の入力、出力データは、複素数であ
るので、実部と虚部とに分けて演算される。具体的には
、第６図に示すように構成される。 入力Δ、Ｂのデータは、それぞれ、Ａ人カバッファ、Ｂ
人カバッファに入力される。２４は、回転因子に関する
データを記憶したメモリである。Ｂ人カバッファのデー
タと回転因子との乗算の結果、Ｓｌ、Ｓ２、Ｓ３、Ｓ４
には、それぞれ、Ｂ、ＣＯ３−、Ｂ、ＳＩＮφ、ＢｔＣ
Ｏ３φ、Ｂ、ＳＩＮφが出力される。又Ｓ５、Ｓ６には
、加減算結果、Ｂ１ＣＯ３φ十Ｂ＋ＳＩＮφ、Ｂ、ＣＯ
Ｓφ−Ｂ＊ＳＩＮφが出力される。更に、Ｓ７、Ｓ８、
Ｓ９、ＳＩＯには、加減算の結果、 Ａｌｌ＋ＢＲＣＯ３φ＋ＢＩＳＩＮφ Ａｔ−ＢヮＳＩＮφ＋Ｂ、ＣＯＳφ Ａ、−ＢＩＣＯＳφ−ＢｆＳＩＮφ Ａ□十Ｂ、ＳＩＮφ−Ｂ、ＣＯＳφ がそれぞれ、出力され、Ｃ出力バッファとＤ出力バッフ
ァに、Ｃｍ 、Ｃｔ 、ＤＲ、Ｄｔが得られる。 ２５ａ〜２５ｄは、上位桁処理回路である。バタフライ
演算回路の冗長２進数の出力は、また、他のバタフライ
演算回路の冗長２進数の入力となる。したがって、入力
、出力の有効桁数を一致させる必要がある。ところが、
冗長２進数で加算すると桁上げ処理を伴うため、１回の
加算毎に桁数が１増加する。したがって、有効桁数を一
定にするため、増加した上位桁を減縮する操作が必要と
なる。上位桁処理回路は、増加した桁数＋１桁の上位桁
を１桁に減縮する処理を行うものである。 ２６ａ〜２６ｄは、シフタ回路である。入出力の有効桁
数を一致させ演算精度を高めるために、場合により、２
で割った値（１桁下位ヘシフトする）を出力する。係る
場合には、シフタ回路を作動させて１／２のデータを出
力するようにしている。 （ｂ）乗算回路 乗算回路の構成は、第７図に示す様になっている。この
乗算回路は、２ビットブースの方法により、部分積を求
めている。この乗算回路では、被乗数は２進化冗長２進
数で、乗数は２の補数表現の２進数で与えられている。 １２桁演算の場合、６個の部分積が発生゛し、それらは
、第１部分積発生回路４１〜第６部分積発生回路４６で
並列的に発生される。そして、各部分積は、２個づつ３
個の部分積加算回路（５１〜５３）で並列的に一次加算
される。部分積加算回路５１と５２の加算結果は、部分
積加算回路６１で２次加算される。次に、部分積加算回
路５３と６１の出力が部分積加算回路７１で３次加算さ
れる。この時、上位から２桁は、冗長２進数による加算
を行った為に発生した桁であり、上位から３桁が１桁に
変換されて、出力される。 部分積発生回路は、第８図に具体的に示されている。Ａ
は乗数の解読部である。第１部分積では、−２Ｃ２！、
ｌ＋ Ｃｘ□＋Ｃ２１−１が計算される。この結果の採
り得る値は、（−２，−１，０，１，２）である。０の
時は、０の出力、１の時は、被乗数をそのまま出力、２
の時は、被乗数を上位方向に１桁シフトして出力、−１
の時は、被乗数の各ビットのレベルを反転して出力し、
−２の時は、被乗数を上位方向に２桁シフトしてさらに
それを反転して出力する事により部分積が発生される。 図には、第３部分積発生回路が図示されている。乗数の
第５．６．７ビツトＣ，、Ｃｓ 、Ｃ，が解読され、−
２の時は、Ｆ３４が高レベルとなり、被乗数（Ｉ 、、
、 Ｉ 、ｐ）が（Ｐ ｄｐ＋ｌ ＋ Ｐ ｓｐ＋１
）として出力される。２の時は、Ｆ１ａが高レベルとな
り、被乗数（Ｉ ｌｉｐ＋ Ｉ 、、）が（Ｐ ｓｐ＋
Ｉ ｒ Ｐ ｄＰや、）として出力される。また、−
１の時は、Ｆ３２が高レベルとなり、被乗数（Ｉ −Ｐ
、 Ｉ ｄｐ）が（ＰｄＰ、Ｐｓｐ）として出力される
。又、１の時は、Ｆ３１が高レベルとなり、被乗数（Ｉ
−Ｐ、 Ｉ 、−）が（Ｐ、、。 Ｐ、、）として出力される。 各部分積の出力端子は、第７図に示す様に桁合わせを行
い、各桁を横方向に配列した構造になっている。 係る部分積は、冗長２進加算器により、本状に順次加算
される。本例では加算器は３役に構成されている。 （ｃ）加算回路 加算回路は、２進化冗長２進数の加算を行うものであり
、その１桁の構成が第９図、第１０図に示されている。 第１０図は、第９図の論理回路を更に簡約したものであ
る。 冗長２進数による加算では、冗長度を利用して、下位桁
からの桁上げが伝搬しないように構成する事が出来る。 したがって、加算は各桁の和（以下この和を２桁で表し
、上位桁を「中間桁上げ」、下位桁を「中間和」と言う
）を求める第１ステツプと、中間和と下位桁の中間桁上
げとの和を各桁で計算する第２ステツプとの２段階で求
める事が出来る。即ち、第２ステツプの演算の時、さら
に桁上げが生じないように、第１ステツプでの中間和と
中間桁上げの表現を工夫している。発生される中間和と
中間桁上げを第１表に示す。１．３．４．６の場合には
、中間桁上げと中間和の表現方法は一意的であるが、下
位桁からどの様な桁上げがあっても、第２ステツプの演
算で桁上げが発生することはない。２と５の場合は、中
間桁上げと中間和の表現方法は一意的ではないが、表現
方法によっては、第２ステツプの演算で、さらに、桁上
げが発生する場合がある。ところが、下位桁の状態を判
別し、その状態に応じて、表のように表現すれば、第２
ステツプの演算で桁上げが発生することはない。即ち、
２．５の場合、下位桁から−１の桁上げが発生する可能
性がある場合には、中間和を１にしておき、下位桁から
１の桁上げが発生する可能性がある時には、中間和を−
１とすることで、第２ステツプの演算で桁上げが発生し
ないようにすることが出来る。 第９図は、係る演算を実行するための第１桁目の回路で
ある。Ｓ！１は、１桁下位の加数、被加数の状態を示す
ものであり、少なくとも一方が負の時、低レベルとなる
信号である。被加数は（ａｉ１＋ａｄｌ）であり、加数
は、（ｂ＠＋、 ｂｄｔ）であり、加算結果は、（Ｚａ
□＋Ｚｄｆ）である。いずれも、２進化冗長２進数であ
る。又、（’： ａｔ、 ＝ ａ□）は、中間桁上げを
２進化冗長２進数（負論理）で表現したものである。 係る１桁の加算器を第１１図のように接続すれば、Ｎ桁
の冗長２進加算器が構成出来る。 （６）評価 １個のバタフライ演算回路に於けるトランジスタ素子数
と論理段数を２の補数表現の２進数方式と、冗長２進数
方式で対比した結果を第２表に示す。トランジスタはＣ
ＭＯＳで評価し、第６図の回路で評価した。冗長２進方
式は、ビット数が増えても、論理段数が変化しないと言
う特徴があり、ビット数に拘わらず、演算速度を一定に
することが出来る。１０２４点データ入力の場合には、
バタフライ演算回路は１０段必要になり、ＦＦＴ演算部
を３８０段の論理段数で構成出来る。又出力の２進数変
換部の８段を含めて、全体で３８８段で装置を構成出来
る。係る段数は、１６ビツトで２進数方式の１７２以下
にする事が出来、したがって、変換速度を１７２以下に
する事が出来る。 （７）他の実施例 第１２図にその構成が示されている。ＦＦＴ演算部２は
、Ｎ／２個の１段の並列配列のバタフライ演算回路Ｂ、
〜Ｂ Ｈ／２で構成されている。１段の処理の終了後、
Ｎ点の出力データはシフタ回路８、マルチプレクサ９を
介して、ＦＦＴ演算回路に再度入力する。係る演算を所
定段数分実行してＦＦＴが行われる。シフタ回路８は、
各段での演算のための入力データの組合せを制御するた
めの回路であり、その具体的な１ビツトの構成が第１３
図に示されている。図は入力データ点数６４の場合であ
る。バタフライ演算回路の２出力の一方は、必ず、同一
演算回路の一方に入力させることが出来るので、シフタ
回路の入力出力端子数は３２個である。制御信号Ｃ５〜
Ｃ６が、それぞれ、各段の演算の終了後に入力され、そ
の段の出力データが、次の段の入力データとなるように
ゲートを切り換えてデータの流れが制御されている。 係る構成により、バタフライ演算回路数を入力データ点
数の半分に減少させることが出来る。
本発明は、ＦＦＴのバタフライ演算回路における加算回
路を、桁上げが上位に伝搬しない冗長２進数による加算
回路で構成したことを特徴とするものである。したがっ
て、桁数に関係なく、加算時間を一定の値に減少させる
事が出来、バタフライ演算及びＦＦＴを高速化する事が
出来る。
路を、桁上げが上位に伝搬しない冗長２進数による加算
回路で構成したことを特徴とするものである。したがっ
て、桁数に関係なく、加算時間を一定の値に減少させる
事が出来、バタフライ演算及びＦＦＴを高速化する事が
出来る。
第１図は、本発明の具体的な一実施例に係るＦＦＴ装置
の構成を示したブロックダイヤグラム、第２図、第３図
は、それぞれ、冗長２進変換部、２進変換部の構成を示
したブロックダイヤグラム、第４図は、ＦＦＴ演算部の
構成を示したブロックダイヤグラム、第５図、第６図は
、バタフライ演算回路の構成を示したブロックダイヤグ
ラム、第７図は、乗算回路の構成を示したブロックダイ
ヤグラム、第８図は、部分積発生回路の構成を示した電
気回路図、第９図、第１０図は、加算回路の１桁の構成
を示した電気回路図、第１１図は、加算回路の構成を示
したブロックダイヤグラム、第１２図は、他の実施例に
係るＦＦＴ装置の構成を示したブロックダイヤグラム、
第１３図は、その装置で使用されるシフタ回路の構成を
示した電気回路図である。
の構成を示したブロックダイヤグラム、第２図、第３図
は、それぞれ、冗長２進変換部、２進変換部の構成を示
したブロックダイヤグラム、第４図は、ＦＦＴ演算部の
構成を示したブロックダイヤグラム、第５図、第６図は
、バタフライ演算回路の構成を示したブロックダイヤグ
ラム、第７図は、乗算回路の構成を示したブロックダイ
ヤグラム、第８図は、部分積発生回路の構成を示した電
気回路図、第９図、第１０図は、加算回路の１桁の構成
を示した電気回路図、第１１図は、加算回路の構成を示
したブロックダイヤグラム、第１２図は、他の実施例に
係るＦＦＴ装置の構成を示したブロックダイヤグラム、
第１３図は、その装置で使用されるシフタ回路の構成を
示した電気回路図である。
Claims (8)
- （１）入力データに回転因子を掛けたデータを出力する
乗算回路と、２つの入力データの和と差を演算して求め
られたデータを出力する加減算回路と、からなるバタフ
ライ演算回路において、前記乗算回路に於ける部分積発
生回路は、その入力データである被乗数を冗長２進数と
して処理し部分積を冗長２進数として出力するものであ
り、前記乗算回路に於ける部分積の和の演算回路と前記
加減算回路とを、冗長２進数による加算演算により桁上
げが上位桁に伝搬しない冗長２進加算回路で構成したこ
とを特徴とする高速フーリエ変換装置用バタフライ演算
回路。 - （２）前記乗算回路は、各部分積が並列的に求められ、
その部分積の和を２つずつ木状接続により求める冗長２
進加算木を用いた組合せ回路による並列乗算回路で構成
されていることを特徴とする特許請求の範囲第１項記載
の高速フーリエ変換装置用バタフライ演算回路。 - （３）前記乗算回路は、乗数を基数４の拡張ＳＤ（サイ
ンド ディジィト）表現に変換し、その各桁毎に部分積
を求める２ビットブースの方法を用いた乗算回路で構成
されていることを特徴とする特許請求の範囲第２項記載
の高速フーリエ変換装置用バタフライ演算回路。 - （４）入力データに回転因子を掛けたデータを出力する
乗算回路と、２つの入力データの和と差を演算して求め
られたデータを出力する加減算回路と、からなるバタフ
ライ演算回路を基本演算回路とする高速フーリエ変換装
置において、 前記乗算回路に於ける部分積発生回路は、その入力デー
タである被乗数を冗長２進数として処理し部分積を冗長
２進数として出力するものであり、前記乗算回路に於け
る部分積の和の演算回路と前記加減算回路とを、冗長２
進数による加算演算により桁上げが上位桁に伝搬しない
冗長２進加算回路で構成したことを特徴とする高速フー
リエ変換装置。 - （５）バタフライ演算回路の配列は、Ｎ点の入力データ
に対し、Ｎ／２のバタフライ回路を並列に設けた並列処
理回路がｌｏｇ＿２Ｎ段所定の接続関係で縦続に接続さ
れた網目状に構成されていることを特徴とする特許請求
の範囲第４項記載の高速フーリエ変換装置。 - （６）Ｎ点の入力データに対し、Ｎ／２のバタフライ演
算回路を並列に設けた並列処理回路と、該並列処理回路
のＮの出力データを、その順序を各処理ステップ毎に異
なる所定の論理で並べ換えて、前記並列処理回路に入力
する処理をｌｏｇ＿２Ｎステップ数だけ繰り返す制御手
段とを有することを特徴とする特許請求の範囲第４項記
載の高速フーリエ変換装置。 - （７）Ｎ点の入力データを冗長２進数に変換する冗長２
進変換部を有することを特徴とする特許請求の範囲第４
項記載の高速フーリエ変換装置。 - （８）フーリエ変換後のＮ点のデータを２進数に変換す
る２進変換部を有することを特徴とする特許請求の範囲
第４項記載の高速フーリエ変換装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61063097A JPS62221071A (ja) | 1986-03-20 | 1986-03-20 | バタフライ演算回路及びそれを用いた高速フ−リエ変換装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61063097A JPS62221071A (ja) | 1986-03-20 | 1986-03-20 | バタフライ演算回路及びそれを用いた高速フ−リエ変換装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS62221071A true JPS62221071A (ja) | 1987-09-29 |
Family
ID=13219454
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61063097A Pending JPS62221071A (ja) | 1986-03-20 | 1986-03-20 | バタフライ演算回路及びそれを用いた高速フ−リエ変換装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS62221071A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01195574A (ja) * | 1988-01-29 | 1989-08-07 | Nec Corp | ディジタル信号処理装置 |
| JPH01288967A (ja) * | 1988-05-16 | 1989-11-21 | Nec Corp | パイプライン信号処理回路 |
| US11604852B2 (en) | 2017-12-27 | 2023-03-14 | Nec Corporation | Signal processing apparatus, method, program, and recording medium |
-
1986
- 1986-03-20 JP JP61063097A patent/JPS62221071A/ja active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01195574A (ja) * | 1988-01-29 | 1989-08-07 | Nec Corp | ディジタル信号処理装置 |
| JPH01288967A (ja) * | 1988-05-16 | 1989-11-21 | Nec Corp | パイプライン信号処理回路 |
| US11604852B2 (en) | 2017-12-27 | 2023-03-14 | Nec Corporation | Signal processing apparatus, method, program, and recording medium |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Timarchi et al. | Arithmetic circuits of redundant SUT-RNS | |
| Gadakh et al. | Design and optimization of 16× 16 Bit multiplier using Vedic mathematics | |
| Jain et al. | Binary division algorithm and high speed deconvolution algorithm (Based on Ancient Indian Vedic Mathematics) | |
| Dhole et al. | Design and FPGA implementation of 4× 4 Vedic multiplier using different architectures | |
| JPH08161149A (ja) | シフト装置 | |
| Buddhe et al. | Design and verification of dadda algorithm based binary floating point multiplier | |
| JP3660075B2 (ja) | 除算装置 | |
| Putra et al. | Optimized hardware algorithm for integer cube root calculation and its efficient architecture | |
| US4873660A (en) | Arithmetic processor using redundant signed digit arithmetic | |
| JPH01195574A (ja) | ディジタル信号処理装置 | |
| Chugh et al. | Design and implementation of a high-Performance 4-bit vedic multiplier using a novel 5-bit adder in 90nm technology | |
| Gorodecky et al. | Efficient hardware operations for the residue number system by Boolean minimization | |
| White | A fast digital computer method for recursive estimation of the mean | |
| Dhivya et al. | A high speed area efficient FIR filter using floating point dadda algorithm | |
| Abid et al. | Modified operand decomposition multiplication for high performance parallel multipliers | |
| Bashagha et al. | A new digit-serial divider architecture | |
| Kim et al. | Digit-serial modular multiplication using skew-tolerant domino CMOS | |
| Sreelakshmi et al. | Efficient realization of vinculum vedic bcd multipliers for high speed applications | |
| Bello et al. | An Efficient CRT Based Reverse Converter for {2^ 2n+ 1-1, 2^ n-1, 2^ 2n-1} Moduli set | |
| RU2839987C1 (ru) | Умножитель чисел по произвольному модулю | |
| Molahosseini et al. | A new design of reverse converter for a three-moduli set | |
| da Costa et al. | Gray encoded fixed-point LMS adaptive filter architecture for the harmonics power line interference cancelling | |
| Shrivastava et al. | Implementation of Radix-2 Booth Multiplier and Comparison with Radix-4 Encoder Booth Multiplier | |
| Gustafsson et al. | Basic arithmetic circuits | |
| Chaudhary et al. | Design of 64 bit High Speed Vedic Multiplier |