(57)【要約】【課題】記憶手段のサイズを小さく保ったままで、分散算術演算を高速化する。【解決手段】演算装置は、第１のデータ組が入力される分散算術演算手段２５１及び第２の入力データ組に対応したデータの表を記憶した記憶手段２０４を備える。分散算術演算手段２５１は、第１の入力データ組から、Ｔビット幅のデータを生成する変換手段２０２ａ…、変換手段２０２ａ…の最下位から最上位ビットまでの各ビットの内容に従って記憶手段２０４から出力されるデータ組から最適なデータを選ぶ選択手段２０５ａ…、選択手段２０５ａ…より出力されるデータを演算する第１の演算手段２０６の出力データとビットシフトを実行する第３の演算手段２０８の出力との加減算を実行する第２の演算手段２０７、及び第２の演算手段２０７から出力される演算結果を一時的に格納する一時記憶手段２０９を備える。【選択図】  図１
2004171263.tif 000002
【特許請求の範囲】
【請求項１】
第１の入力データ組と、第２の入力データ組とに対して、分散算術演算法を利用して演算処理を行う演算装置において、
前記第１の入力データ組が入力される少なくとも１個の分散算術演算手段と、
前記第２の入力データ組に対応したデータの表を記憶し、前記第２の入力データに応じたデータ組を出力する記憶手段とを備え、
前記分散算術手段は、
前記第１の入力データ組の１番目からＵ番目のデータから、Ｔビット幅のデータをそれぞれ生成する第１から第Ｕの変換手段と、
前記第１から第Ｕの変換手段の最下位から最上位ビットまでの各ビットの内容に従って、前記記憶手段から出力されるデータ組から、それぞれ最適なデータを選ぶ第１から第Ｔの選択手段と、
前記第１から第Ｔの選択手段より出力されるデータを演算する第１の演算手段と、
前記第１の演算手段から出力されるデータと、ビットシフトを実行する第３の演算手段の出力との加減算を実行する第２の演算手段と、
前記第２の演算手段から出力される演算結果を一時的に格納する一時記憶手段と、
前記一時記憶手段から出力されるデータのビットシフトを実行する第３の演算手段とを備えることを特徴とする、演算装置。
【請求項２】
前記第１から第Ｕの変換手段は、前記第１の入力データ組の１番目からＵ番目のデータにおける各ビット位置の値を最下位ビットから順に、０ビットからＴ−１ビットの各ビット位置に割り振り、第１から第Ｔの選択手段に対してＴビットづつ順次出力し、
前記第１の演算手段は、前記第１から第Ｔ−１の選択手段の出力を各々Ｔ−１ビットから１ビットまで１ビットずつ下位側にビットシフトした各結果と、第Ｔの選択手段の出力とを加減算し、
前記第３の演算手段は、前記一時記憶手段の出力をＴビット下位側にビットシフトし、
前記第１の入力データ組として入力されるベクトルと第２の入力データ組として入力されるベクトルの内積を計算することを特徴とする、請求項１に記載の演算装置。
【請求項３】
前記第１の入力データ組は、Ｈ個の複素数であり、ｈ個目の複素数の実部及び虚部はそれぞれ前記第１の入力データ組の２ｈ−１番目及び２ｈ番目に割り当てられ、
前記第１の分散算術演算手段の数は２Ｈ個であり、
前記第１の入力データ組の２ｈ−１番目及び２ｈ番目の入力は、２ｈ−１番目及び２ｈ番目の前記分散算術演算手段にのみ出力され、
前記第１の入力データとして入力される複素数と、前記第２の入力データとして入力される複素数の乗算を行うことを特徴とする、請求項１に記載の演算装置。
【請求項４】
前記記憶手段は、０からＮ／８の整数であるｎに対する｛ｃｏｓ（２πｎ／Ｎ）＋ｓｉｎ（２πｎ／Ｎ）｝／２の値を示す第１の表と、前記０からＮ／８の整数であるｎに対する｛ｃｏｓ（２πｎ／Ｎ）−ｓｉｎ  （２πｎ／Ｎ）｝／２の値を示す第２の表とを格納していることを特徴とする、請求項３に記載の演算装置。
【請求項５】
前記第１の記憶手段が、０からＮ／８の整数であるｎについて｛ｃｏｓ（２πｎ／Ｎ）＋ｓｉｎ（２πｎ／Ｎ）｝／２の値及び｛ｃｏｓ（２πｎ／Ｎ）−ｓｉｎ  （２πｎ／Ｎ）｝／２の値の対を示す第３の表を格納していることを特徴とする、請求項３に記載の演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像信号の符号化、フィルタ処理、離散フーリエ変換などのデジタル信号処理に使用される分散算術演算法（Ｄｉｓｔｒｉｂｕｔｅｄ  Ａｒｉｔｈｍｅｔｉｃ、以下ＤＡ法と表記する。）を利用した内積演算装置、複素数乗算装置等の演算装置に関するものである。
【０００２】
【従来の技術】
ＤＡ法は行列の内積演算をルックアップ表と加算器で実現する周知の方法である。例えば、特許文献１や非特許文献１に、ＤＡ法を利用することにより、内積演算を、乗算器を使って行うことに比べてコンパクトに実現することが記載されている。
【０００３】
ＤＡ法について説明するため、下記の式１で表される要素数Ｋの定数ベクトルＡと入力ベクトルＸの内積演算を考える。
【０００４】
2004171263.tif 000003
【０００５】
Ｘｋを２の補数表現された２進数のＷビット幅固定小数点であるとすると、以下の式２のように表すことができる。
【０００６】
2004171263.tif 000004
【０００７】
この式（２）において、ｂｋ［ｗ］はビット（１又は０）であり、ｂｋ［０］は符号ビット、ｂｋ［Ｗ−１］は最下位ビットである。
【０００８】
また、Ｘｋ＝｛Ｘｋ−（−Ｘｋ）｝／２と表せるので、ｂｋのビット反転をｂ’ｋとおくと、Ｘｋは以下のようになる。
【０００９】
2004171263.tif 000005
2004171263.tif 000006
【００１０】
ただし、この式３でｃｋ［ｗ］は以下のように表される。
【００１１】
2004171263.tif 000007
【００１２】
（式３）を（式１）に代入して、以下の式５が得られる。
【００１３】
2004171263.tif 000008
【００１４】
この式５において、以下の関係がある。
【００１５】
2004171263.tif 000009
【００１６】
（式６）において、Ｑ（ｂｗ）は次式のように変形できる。
【００１７】
2004171263.tif 000010
【００１８】
従って、ｃ１＝−１の場合のＱ（ｂｗ）は、ｃ１＝１の場合のＱ（ｂｗ）で表現できるので、式６の値は、２Ｋ−１通りで全てを表現でき、この値をルックアップ表として記憶しておく。そして、ｗ＝Ｗ−１から０まではそれぞれの値に２−ｗが掛かるので、ｗ＝Ｗ−１から順番に実行し、前記ルックアップ表から参照した値を１桁ずつ右へずらせて加える。以上の手順により、乗算を行うことなくＡＸを得ることができる。
【００１９】
入力ベクトルＸの複数の値について、上記演算を同時に行う場合は、次式の演算を行うことと等価である。
【００２０】
2004171263.tif 000011
【００２１】
ここで、Ｘ（ｉ）は、式（１）におけるＸのｉ番目の縦ベクトル、Ａ（ｉ）はそれに対応する定数の横ベクトル（ｉは０以上の整数）、０は要素値が０の横ベクトルを示す。また、Ａ’  はＡ（ｉ）を含む行列を表し、Ｘ’  はＸ（ｉ）を含むベクトルを表し、Ｂは演算結果を表す。
【００２２】
図６に、例えば、特許文献３、特許文献４等で示された方法を利用した（式８）の演算を行う方法を示す。端子群１０１から入力ベクトルＸ（０）、Ｘ（１）、…の各要素がビットシリアルで同時並列入力される。符号１１０，１１１…は、式１のＡＸを演算するための分散算術演算回路を示し、入力ベクトル数分だけ並列接続される。符号１０３はルックアップ表を記憶している記憶手段を示す。端子群１０１への入力データ（定数ベクトル）に対応したデータが記憶手段１０３から加減算器１０４へ入力される。加減算器１０４は記憶手段１０３の出力データと１ビットシフタ１０６の出力を加減算し、例えばシフトレジスタである一時記憶手段１０７へ入力する。一時記憶手段１０７に一時記憶された加減算器１の出力はビットシフタ１０６へ出力され、適切なタイミングでスイッチ１０８が閉じられ、出力端子１０９から出力Ｂ（０）として出力される。同様に、他のＤＡ回路１１１…の出力Ｂ（１），Ｂ（２）…が出力端子１０９から出力される。
【００２３】
【特許文献１】
米国特許第３，７７７，１３０号
【特許文献２】
米国特許第５，２２６，００２号
【特許文献３】
特開２０００−１４８７３０号公報
【非特許文献】
“Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  ｄｉｓｔｒｉｂｕｔｅｄ  ａｒｉｔｈｍｅｔｉｃ  ｔｏ  ｄｉｇｉｔａｌ  ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｉｎｇ：  ａｔｕｔｏｒｉａｌ  ｒｅｖｉｅｗ，”  Ｓ．Ａ．Ｗｈｉｔｅ，  ＩＥＥＥ  ＡＳＳＰ  ｍａｇａｚｉｎｅ，  ｖｏｌ．６，  ｉｓｓｕｅ  ３，  ｐｐ．４−９，  Ｊｕｌｙ  １９８９
【００２４】
【発明が解決しようとする課題】
しかしながら、図６に示す従来の装置では、各分散算術演算回路１１０，１１１…が、それぞれ記憶手段１０３を内蔵しているので、そのコンパクト性は、記憶手段１０３のコンパクト性に大きな影響を受ける。すなわち、同時処理する入力ベクトルの数が増えれば増えるほど、分散算術演算回路１１０，１１１…の数が増加し、それに従って記憶手段１０３の数も増加する。
【００２５】
また、図６において、入力データは端子群１０１からビットシリアルで入力されるため、１ビットを１クロックで処理すると、出力結果が得られるまでに少なくとも入力データのビット幅分のクロック数が必要となる。一方、クロック周波数を大きくせずに演算時間を短くするために多ビットを同時処理することは、式８におけるベクトルＸ’の要素数を増やすことに相当するので、分散算術演算回路１１０，１１１…の並列処理数が並列処理ビット数の数だけ増加し、従って記憶手段１０３も同数だけ増加する。
【００２６】
このように、分散算術演算により複数データについて内積演算を同時処理すると、同時処理数分だけの記憶手段が必要となり、同時処理数が増すにつれてコンパクト性が悪化するという問題を有している。
【００２７】
本発明は、かかる問題に鑑みてなされたもので、その目的は、記憶手段のサイズを小さく保ったままで、分散算術演算を高速化することにある。
【００２８】
【課題を解決するための手段】
本発明はこうした課題を解決するための手段を提供するもので、各請求項の発明は、以下の技術手段を構成する。
【００２９】
本発明は、第１の入力データ組と、第２の入力データ組とに対して、分散算術演算法を利用して演算処理を行う演算装置において、前記第１の入力データ組が入力される少なくとも１個の分散算術演算手段と、前記第２の入力データ組に対応したデータの表（ルックアップ表）を記憶し、前記第２の入力データに応じたデータ組を出力する記憶手段とを備え、前記分散算術手段は、前記第１の入力データ組の１番目からＵ番目（Ｕは自然数）のデータから、Ｔビット幅（Ｔは自然数）のデータをそれぞれ生成する第１から第Ｕの変換手段と、前記第１から第Ｕの変換手段の最下位から最上位ビットまでの各ビットの内容に従って、前記記憶手段から出力されるデータ組から、それぞれ最適なデータを選ぶ第１から第Ｔの選択手段と、前記第１から第Ｔの選択手段より出力されるデータを演算する第１の演算手段と、前記第１の演算手段から出力されるデータと、ビットシフトを実行する第３の演算手段の出力との加減算を実行する第２の演算手段と、前記第２の演算手段から出力される演算結果を一時的に格納する一時記憶手段と、前記一時記憶手段から出力されるデータのビットシフトを実行する第３の演算手段とを備えることを特徴とする、演算装置を提供する。
【００３０】
上記構成とした本発明の演算装置では、各分散算術演算手段がデータの表を記憶した記憶手段を内蔵する必要がないので、表を記憶するための記憶手段を増加することなく、分散算術演算を利用したＴビット同時処理により処理の高速化を図ることができる。
【００３１】
本発明の演算装置は、内積演算装置として構成することができる。この場合、前記第１から第Ｕの変換手段は、前記第１の入力データ組の１番目からＵ番目のデータにおける各ビット位置（０，１，…，Ｔ−１）の値を最下位ビットから順に、０ビットからＴ−１ビットの各ビット位置（０，１，…，Ｔ−１）に割り振り、第１から第Ｔの選択手段に対してＴビットづつ順次出力し、前記第１の演算手段は、前記第１から第Ｔ−１の選択手段の出力を各々Ｔ−１ビットから１ビットまで１ビットずつ下位側（Ｔ−１，Ｔ−２・・・１ビットずつ下位側）にビットシフトした各結果と、第Ｔの選択手段の出力とを加減算し、前記第３の演算手段は、前記一時記憶手段の出力をＴビット下位側にビットシフトし、前記第１の入力データ組として入力されるベクトルと第２の入力データ組として入力されるベクトルの内積を計算する。かかる構成とすれば、表を記憶するための記憶手段を増加することなく、分散算術演算を利用したＴビット同時処理により内積演算処理の高速化を図ることができる。
【００３２】
また、本発明の演算装置は、複素数乗算装置として構成することができる。この場合、前記第１の入力データ組は、Ｈ個（Ｈは自然数）の複素数であり、ｈ個目（ｈは１からＨまでの整数）の複素数の実部及び虚部はそれぞれ前記第１の入力データ組の２ｈ−１番目及び２ｈ番目に割り当てられ、前記第１の分散算術演算手段の数は２Ｈ個であり、前記第１の入力データ組の２ｈ−１番目及び２ｈ番目の入力は、２ｈ−１番目及び２ｈ番目の前記分散算術演算手段にのみ出力され、前記第１の入力データとして入力される複素数と、前記第２の入力データとして入力される複素数の乗算を行う。かかる構成とすれば、表を記憶するための記憶手段を増加することなく、分散算術演算を利用したＴビット同時処理により複素数乗算演算処理の高速化を図ることができる。
【００３３】
前記記憶手段が、０からＮ／８の整数であるｎに対する｛ｃｏｓ（２πｎ／Ｎ）＋ｓｉｎ（２πｎ／Ｎ）｝／２の値を示す第１の表と、前記０からＮ／８の整数であるｎに対する｛ｃｏｓ（２πｎ／Ｎ）−ｓｉｎ  （２πｎ／Ｎ）｝／２の値を示す第２の表とを格納していれば、記憶手段の容量を増大させることなく、Ｎ点離散フーリエ変換に必要なバタフライ演算を高速処理することができる。
【００３４】
あるいは、前記第１の記憶手段が、０からＮ／８の整数であるｎについて｛ｃｏｓ（２πｎ／Ｎ）＋ｓｉｎ（２πｎ／Ｎ）｝／２の値及び｛ｃｏｓ（２πｎ／Ｎ）−ｓｉｎ  （２πｎ／Ｎ）｝／２の値の対を示す第３の表を格納していもよい。この場合、記憶手段の容量と消費電力をより節約しつつ、Ｎ点離散フーリエ変換に必要なバタフライ演算を高速処理することができる。
【００３５】
【発明の実施の形態】
次に、図面に示す本発明の実施形態について説明する。
【００３６】
（基本構成）
まず、図１に示す本発明の演算装置の基本構成について説明する。この基本構成は後述する第１から第３実施形態の内積演算装置や複素乗算装置の基本となる。図１において、２０１は第１の入力データ組が入力される入力端子郡、２０３第２の入力データ組が入力される設定データ入力端子、２０４はルックアップ表を記憶する記憶手段、２３０は出力端子郡を示す。２５１，２５２，２５３・・・は分散算術演算処理回路を示し、これらはいずれも同一構成である。
【００３７】
入力端子郡３０１は入力端子郡２０１から分散算術演算処理回路２５１に入力されるデータの入力端子郡、端子３０２は記憶手段２０４から分散算術演算処理回路２５１に入力されるデータ組の入力端子である。
【００３８】
入力端子郡２０１から入力される１番目からＵ番目までのＵ個のデータは、それぞれ変換回路２０２の第１から第Ｕの変換手段２０２ａ，２０２ｂ…２０２ｕでＴビットデータに変換される。設定データ入力端子２０３から入力される設定データに対応したデータ組が、記憶手段２０４から出力されて選択回路２０５に入力される。
【００３９】
選択回路２０５は、変換回路２０２から出力されるＴビット幅のデータに対応して、第１から第Ｔの選択手段２０５ａ，２０５ｂ…２０５ｔを備えている。選択回路２０５の第１の選択手段２０５ａでは、記憶手段２０４から出力されたデータ組から、変換回路２０２内の各変換手段２０２ａ〜２０２ｕの出力の最下位ビット組に応じたデータが生成され出力される。また、選択回路２０５の第２の選択手段２０５ｂでは、記憶手段２０４から出力されたデータ組から、変換回路２０２内の各変換手段２０２ａ〜２０２ｕの出力の最下位＋１ビット組に応じたデータが生成され出力される。以下、選択回路２０２の各選択手段２０５ｃ，２０５ｄ…で同様の処理が実行される。選択回路２０５の第Ｔの選択手段２０５ｔでは変換回路２０２内の各変換手段２０２ａ〜２０２ｕの出力の最上位ビット組に応じたデータが出力される。
【００４０】
選択回路２０５から出力された複数のデータは、演算手段（第１の演算手段）２０６で演算され、加減算器２０７に入力される。加減算器（第２の演算手段）２０７は演算手段２０６からのデータとビットシフタ２０８からのデータを加減算する。加減算器２０７からのデータは例えばシフトレジスタである一時記憶手段２０９で一時記憶される。一時記憶手段２０９からのデータはビットシフタ（第３の演算手段）２０８へ出力される。適切なタイミングでスイッチ２１０が閉じられ、スイッチ２１０が閉じると一時記憶木手段２０９から出力端子郡２３０の第１の端子から出力される。
【００４１】
従来例の図６における分散算術演算回路１１０，１１１…は、図１におけるスイッチ２１０、ビットシフタ２０８、一時記憶手段２０９、加減算器２０７、演算手段２０６、選択回路２０５のうちのどれか１つ（例えば、選択手段２０５ａ）及び記憶手段２０４を１つの単位とした回路に相当する。そのため、複数データを同時処理する場合、例えば変換回路２０２で多ビットを同時処理できるように割り振り、分散演算処理回路２５１で１つめの設定データを処理し、以降の設定データをそれぞれ分散演算処理回路２５２，２５３…で処理する、というような場合、同時処理数が増えれば増えるほど、分散算術演算回路の数が増えるが、従来例では、記憶手段の数も同時に増え、その総容量が増加していたが、本発明では、このような構成とすることにより、同時処理数にかかわらず、記憶手段２０４は１つでよいので、必要となる記憶手段の総容量は一定となる。
【００４２】
（第１実施形態）
図２に本発明の第１実施形態である内積演算装置を示す。図１と同一機能のものは同一番号を付して説明を省略する。
【００４３】
変換回路２０２は次のような構成とする。即ち、変換回路２０２内の変換手段３０３において、入力端子郡３０１から入力されるデータの［Ｔｋ］ビット、［Ｔｋ＋１］ビット…［Ｔｋ＋（Ｔ−１）］ビット（ｋは０以上の整数）を、出力の最下位ビットから最上位ビットに向けて割り振り、Ｔビットづつ出力する。変換回路２０２内の他の変換手段２０２ａ，２０２ｂ…も同様の処理を実行する。
【００４４】
演算手段２０６はビットシフタ群３０６と加減算器３０７とからなる。選択回路２０５の出力データはビットシフタ郡３０６に入力され、ビットシフタ郡３０６の出力データは加減算器３０７によって加減算される。ビットシフタ郡３０６は次のような構成とする。即ち、選択回路２０５の第１の選択手段２０５ａからビットシフタ郡３０６に入力されたデータはＴ−１ビットシフトされる。選択回路２０５の第２の選択手段２０５ｂからビットシフタ郡３０６に入力されたデータはＴ−２ビットシフトされる。以下、選択回路２０５の各選択手段からビットシフタ郡３０６に入力されたデータを同様に処理する。選択回路２０５の第Ｔの選択手段２０５ｔからビットシフタ郡３０６に入力されたデータはＴ−Ｔビットシフト、即ちそのまま出力される。
【００４５】
ビットシフタ（２０８）は、Ｔビットシフタ（３０８）によって構成する。
【００４６】
基本構成の項で説明したように、従来は、選択回路２０５を構成する選択手段の数だけ分散算術演算の処理を、高速で行うことができるように、分散算術演算を同時処理しようとすれば、選択回路２０５を構成する選択手段の数だけのルックアップ表の記憶手段の数が必要となる。また、ルックアップ表の記憶手段の数を増やさないように、選択回路２０５を構成する選択手段の数だけの分散算術演算の処理を１つづつ行うと、その数だけ演算時間がかかる。しかし、本発明では、このような構成とすることにより、ルックアップ表の記憶手段を増加することなく、Ｔビット同時処理を実施することができ、処理の高速化を図ることができる。
【００４７】
（第２実施形態）
図３に本発明による複素数乗算装置の第２の実施例を示す。図１と同一機能のものは同一番号を付して説明を省略する。入力端子群２０１の入力１に入力複素数１の実部を割り当て、入力端子群２０１の入力２に入力複素数１の虚部を割り当て、…入力端子群２０１の入力２ｈ−１に入力複素数ｈの実部を割り当て、…入力端子群２０１の入力２Ｈに入力複素数Ｈの虚部を割り当てる。入力されたデータは、各々分散算術演算処理回路群４００で処理される。分散算術演算処理回路群４００を構成する分散算術演算処理回路２５１、２５２…は２Ｈ個ある。なか、以降の本実施形態の説明ではすべての分散算術演算処理回路を符号２５１で示す。
【００４８】
入力１及び２は、１番目及び２番目の分散算術演算処理回路２５１のみに入力する。入力１及び２は、前記以外の分散算術演算処理回路２５１には、影響を与えない場合を考え、入力線の記載を省略する。出力複素数１の実部及び虚部は、１番目及び２番目の分散算術演算処理回路２５１から各々出力され、出力端子郡２３０の出力１及び出力２に割り当てる。それ以外の入力も、同様に処理される。
【００４９】
ここで、複素定数Ｙ及び複数の任意の複素数｛Ｚ｝の乗算Ｙ・｛Ｚ｝を考える。Ｙ＝Ｙｒ−ｊＹｉ、｛Ｚ｝の要素の１つをＺ＝Ｚｒ＋ｊＺｉとおくと（添え字ｒは実部を、添え字ｉは虚部を示す。また、ｊ２＝−１である。）、Ｙ・｛Ｚ｝の要素ＹＺは、下記の式９で表される。
【００５０】
2004171263.tif 000012
【００５１】
従って、式１においてＡ及びＸを以下の式１０ように設定し、要素数２のＤＡ法を適用すればＹＺの実部が求まる。
【００５２】
2004171263.tif 000013
【００５３】
同様に、式１において、Ａ及びＸを以下の式１１のように設定し、要素数２のＤＡ法を適用すれば、ＹＺの実部が求まる。
【００５４】
2004171263.tif 000014
【００５５】
実部、虚部いずれの場合でも、ルックアップ表は｛（Ｙｒ＋Ｙｉ）／２，  （Ｙｒ―Ｙｉ）／２｝であり、同一となる。これは、図３において、入力端子郡２０１の２ｈ−１番目の入力端子にＺｒ、２ｈ番目の入力端子にＺｉをそれぞれ入力し、記憶手段２０４のルックアップ表として｛（Ｙｒ＋Ｙｉ）／２，  （Ｙｒ―Ｙｉ）／２｝を格納すると、出力端子郡２３０の２ｈ−１番目の出力端子及び２ｈ番目の出力端子の出力としてＹＺの実部及び虚部が得られることになる。Ｙ・｛Ｚ｝は、ＹＺを求めるＤＡ法を複数実施することにより求めることができる。これは、図３の入力端子郡（２０１）に｛Ｚ｝を入力すればよい。
【００５６】
このような構成とすることにより、複素数の乗算を分散術演算で実現でき、｛Ｚ｝の要素数、即ち入力端子郡２０１の入力数によらず、また、演算の高速化のため分散算術演算処理回路２５１内で、第１の実施形態に示したように多ビット同時処理を行っても、第１の実施形態の項で説明したように、記憶手段は増加せず一定である。
【００５７】
（第３実施形態）
複素関数ｆ（ｎ）のＮ点離散フーリエ変換（以下、ＤＦＴ）は次式である。
【００５８】
2004171263.tif 000015
【００５９】
ＷＮは回転因子と呼ばれるファクターである。式１２を変形していくと、
【００６０】
2004171263.tif 000016
【００６１】
ｋが偶数の場合と奇数の場合で分けると、
【００６２】
2004171263.tif 000017
【００６３】
ただし、
2004171263.tif 000018
【００６４】
となる。ｆ（ｎ）に関するＮ点ＤＦＴが、ｙ（ｎ）及びｚ（ｎ）に関するＮ／２点ＤＦＴになった。その際式１５の演算をＮ／２点行う必要がある。式１５の演算はバタフライ演算と呼ばれる。これを、ｌｏｇ２Ｎ−１段（Ｎが２のべき乗の場合）、再起的に繰り返していくことで、ＤＦＴ演算結果を得ることができる。これは、基数２の周波数間引きＤＦＴと呼ばれる演算手法である。
【００６５】
この場合、式１５に示す複素乗算を１段あたりＮ／２回を合計ｌｏｇ２Ｎ−１段行う必要があるため、ＤＦＴを高速で行うためには、式１５の演算を高速で行う必要がある。そのため、１段あたりＮ／２個の式１５の演算をいくつかづつ同時並列処理で行いたい。これは、本発明による第２の実施例において、
【００６６】
2004171263.tif 000019
【００６７】
とおくことによって達成することができる。この場合（式６）におけるＱ（ｂｗ）は、
【００６８】
2004171263.tif 000020
【００６９】
である。ところで、三角関数の全ての値は、０〜４５度の三角関数値で表現できるので、式１７のためのルックアップ表は、ｎ＝０〜Ｎ／８での結果のみを格納すればよい。
【００７０】
この場合の記憶手段の構成を図４に示す。図１と同一機能のものは同一番号を付す。記憶手段２０４は、第１の記憶部５０１及び第２の記憶部５０２で構成される。第１の記憶部５０１はＱｐ（ｎ）のルックアップ表（ただし、ｎは０〜Ｎ／８の整数）を格納する。第２の記憶部５０２はＱｍ（ｎ）のルックアップ表（ただし、ｎは０〜Ｎ／８の整数）を格納する。設定２０３から指示されたアドレスに従って、記憶手段１５０１及び記憶手段２５０２のデータ組が端子３０２から出力される。
【００７１】
このような構成とすることにより、ルックアップ表の記憶手段の増大なしに、ＤＦＴに必要となるバタフライ演算を高速で実施することができる。
【００７２】
（第４実施形態）
第３実施形態における記憶手段の別の構成を図５に示す。図４と同一機能のものは同一番号を付す。１つの複素乗算ではｎは固定値なので、単一の記憶部５０４はＱｐ（ｎ）とＱｍ（ｎ）の対を格納した表であれば、アドレスデコーダは１つで済み、低消費電力化できる。
【００７３】
（第５実施形態）
図４又は図５のルックアップ表を使い、第２実施形態に従って複素数乗算をＤＡ法で構成すれば、式１５の演算が実施できる。式１５は前述したように、ｎ＝０…Ｎ／２−１について行う必要があるが、このうちのいくつかを同時処理することで、演算の高速化を図ることができる。その際、第２実施形態で示したように、ルックアップ表を格納するための記憶手段の増大はない。さらに、第１実施形態で示したように、多ビット同時処理による演算高速化を図っても、ルックアップ表を格納するための記憶手段の増大はない。以上の演算をｌｏｇ２Ｎ−１段行うことで、ＤＦＴ演算が達せられる。
【００７４】
このような構成とすることにより、ルックアップ表の記憶手段の増大なしに、ＤＦＴの高速化を図ることができる。
【００７５】
【発明の効果】
以上の説明から明らかなように、本発明の演算装置は、第１の入力データ組が入力され、変換手段、選択手段、及び第１から第３の演算手段を備える少なくとも１個の分散算術演算手段と、前記第２の入力データ組に対応したデータの表を記憶し、前記第２の入力データに応じたデータ組を出力する記憶手段とを備え、分散算術演算手段の選択手段が記憶手段から出力されるデータ組から最適なデータを選ぶので、表を記憶するための記憶手段を増加することなく、分散算術演算を利用したＴビット同時処理により、内積演算処理、複素乗算処理、Ｎ点離散フーリエ変換に必要なバタフライ演算処理等の演算処理の高速化を図ることができる。
【図面の簡単な説明】
【図１】本発明の基本構成を示すブロック図である。
【図２】本発明の第１実施形態を示すブロック図である。
【図３】本発明の第２実施形態を示すブロック図である。
【図４】発明の第３実施形態における記憶手段の構成を示す概略図である。
【図５】本発明の第３実施形態における記憶手段の他の構成を示す概略図である。
【図６】従来の内積演算装置の一例を示すブロック図である。
【符号の説明】
２０１  データ入力端子郡
２３０  データ出力端子郡
２０３  設定データ入力端子
２０４，  ５０１，  ５０２，  ５０３  ルックアップ表を格納する記憶手段
２５１，  ２５２，  ２５３，  ４００  分散算術演算処理回路
２０２  入力データ変換手段
２０５  データの選択手段
２０６  選択されたデータの演算手段
２０７  加減算器
２０８  ビットシフタ
２０９  一時記憶手段
【図１】
2004171263.tif 000021
【図２】
2004171263.tif 000022
【図３】
2004171263.tif 000023
【図４】
2004171263.tif 000024
【図５】
2004171263.tif 000025
【図６】
2004171263.tif 000026