JPH07501167A - 一連の積の和を形成する方法および装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 一連の積の和を形成する方法および装置本発明は、順次連続して供給されるそれ ぞれ２つの数値による一連の積の和を形成する方法に関する。この場合、生成相 のそのつどの中間結果が一時記憶されるようにして一連の積の和が形成される。

さらに本発明は、それぞれ第１の値と第２の値の一連の積の和を形成する装置に 関する。この場合、あらかじめ定められた第１のビット数を有する複数個の値を 記憶する記憶装置と、レジスタへの値の書き込みを制御するクロック制御付制御 装置と、互いに乗算すべきそれぞれ２つの値を記憶する第１のレジスタ装置と、 該第１のレジスタ装置と接続された２つの入力側を有する乗算器と、前記の第１ のビット数の２倍のビット数のための出力側を有する後置接続された積レジスタ と、それぞれ前記の第１のビット数のための２つの相入力側を有し該相入力側の 一方は前記積レジスタの出力側と結合可能である加算器と、それぞれ前記の第１ のビット数のための少なくとも２つの部分和レジスタから成る後置接続された和 レジスタとが設けられており、該和レジスタは、前記加算器の他方の入力側と結 合可能な出力側を有するように構成されている。

特表平７−５０１１６７　Ｃ３） この形式の方法は、たとえば信号波形のフィルタ処理のようなディジタル信号処 理でしばしば用いられ、さらにこの形式の装置は多くの多目的シグナルプロセッ サで使用されている。高い周波数での信号シーケンスの処理を可能にするために 各クロック周期ごとに新たな積を形成できるようにする目的で、通常のシグナル プロセッサは２つのデータバスを有している。しかも、この積は２倍のビット数 を有し、つまりワード幅の２倍のビット数を有しているので、加算器もワード幅 の２倍のビット数用に設計されている。しかし、このことによりコストが著しく 高（なる。

本発明の課題は、冒頭で述べた形式の方法において、処理速度がごく僅かに低く なるだけで一連の積の和を僅かなコストで形成できるようにすることにある。

本発明によればこの課題は、それぞれ別個の乗算により形成された積を２つのス テップで中間結果に加算し、当該の加算においてこれらのステップのうち第１の ステップ中、前記の積のＬＳＢの桁値だけを中間結果の相応の桁値に加算し、こ のようにして形成された第１の部分和を一時記憶し、他方、第２のステップ中、 当該の積の比較的高いウェイトの残りの桁値を中間和の相応の残りの桁と前記の 第１の部分和のキャリーに加算し、このようにして形成された第２の部分和を一 時記憶し、各ステップ中、すぐ後に続いて乗算すべき数値のうちの他方の数値を 供給することにより解決される。

さらに本発明の別の課題は、冒頭で述べた形式の装置において、処理速度がごく 僅かに低くなるだけで一連の積の和を僅かなコストで形成できるようにすること にある。

本発明によればこの課題は次の構成により解決される。すなわち、記憶装置は、 前記の第１のビット数のためのただ１つのデータバスを介して第１のレジスタ装 置と接続されており、制御装置は、第１のクロック周期と第２のクロック周期と で交互に異なる動作をするように構成されており、該制御装置により第１のクロ ック周期中、積レジスタの出力側における前記の第１のビット数のＬＳＢビット と第２の部分和レジスタの内容とが、前記加算装置の入力側へ供給され、該第１ のクロック周期の終了時に、前記の第１の値のうちの１つの値がレジスタ装置へ 書き込まれ、かつ前記加算装置の出力側に生じる新たな部分和が第２の部分和レ ジスタへ書き込まれ、前記制御装置により第２のクロック周期中、積レジスタの 出力側における前記第１のビット数のＭＳＢビットと、第１の部分和レジスタの 内容と、一時記憶されていたキャリーとが、加算器へ供給され、該第２のクロッ ク周期の終了時に、第２の値の一方がレジスタ装置へ書き込まれ、前記加算器の 出力側に生じる第２の部分和が第１の部分和レジスタへ書き込まれ、かつ乗算器 により形成された積が積レジスタへ書き込まれることにより解決される。

このように、２つのクロック周期中にそれぞれ完全な部分和が形成されるため、 処理速度は全体的に半減する。しかしながらこのことにより、処理すべき値を順 次連続して伝送するためにただ１つのデータバスしか必要なくなり、しかも、２ つのクロック周期中に部分和を順次連続してめるための１ワ一ド幅用の加算器を 用いれば十分である。まずはじめにＬＳＢから部分和だけが形成されるので、第 １の部分和からのキャリーを第２の部分和の形成のためにそのつと利用できる。

したがって、存在するすべての桁が実際に評価されるので丸めによる誤差が生じ ることはなく、精確な結果を最終的に第２の部分レジスタから取り出すことがで きる。

次に、図面を参照して本発明の詳細な説明する。

第１図は、本発明による装置の最重要部分のブロック図である。

第２図は、第１図に示されたブロック図内の種々異なる位置において発生する個 々の値のタイムチャートである。

第１図の制御装置１０は、リード線８と９に対し２つの制御信号ＴＩおよびＴ２ を発生するにれらの信号は周期的に変化する。さらに制御装置１０は出力側１１ に、記憶装置１２をアドレス指定するアドレスも発生する。接続線路１１は２重 線で示されているが、これは実際に複数個のパラレルなリード線により構成され ているからであって、これらのリード線を介してアドレスを表わす複数個のビッ トがパラレルに伝送される。このことは、やはり２重線で示されており複数個の リード線から成るデータ接続線路についてもあてはまり、これらのリード線を介 してそのつと１つのデータワードを表わす複数個のビットがパラレルに伝送され る。

複数個の別個のメモリにより構成できリードオンリーメモリを含む記憶装置１２ のデータ接続線路は、データバス１４と接続されており、さらにこのデータバス には（図示されていない）プロセッサ装置のほかに２つのレジスタ１６および１ ８が並列接続されている。

これらのレジスタへの書き込み動作は、リード線８と９における制御信号により 制御される。

互いに乗算されるべき因数をそれぞれ格納するレジスタ１６および１８の出力側 １７および１９は、乗算器２０の入力側と接続されており、この乗算器は１つ特 表千７−５０１１６７　（４） のクロック周期内で、接続線路１７と１９を介して供給された２つの値の完全な 積を形成し、出力側２１を介してこの積を出力する。この積はワード幅の２倍の ビット数を有し、つまり供給される因数のビット数の２倍のビット数を有する。

この部分は、図１に示された装置においてワード幅の２倍のビット数が生じる唯 一の個所であり、接続線路２１は、やはりこのようなワード幅の２倍のビット数 のために設計されてし）る積レジスタ２２０入力端と接続されている。

積レジスタ２２の出力側には２つのリード線２３と２９が接続されており、この 場合、リード線２３はＭＳＢビットを転送するのに対し、リード線２９はＬＳＢ ビットを転送する。つまり各リード線は単一のワード幅しか存していない。接続 線路２３および２９はマルチプレクサ２４へ導かれており、このマルチプレクサ はリード線８における制御信号により制御されて、接続線路２３または接続線路 ２９を加算器２６の入力側２５と接続する。この加算器２６の他方の入力側３５ は、第２のマルチプレクサ３４の出力側と接続されている。

加算器２６の和出力側２７は、２つの部分和レジスタ３０と３２の各入力側に並 列接続されており、これらの部分和レジスタは、制御リード線８および９により 制御されて書き込みのために交互に作動される。第２の部分和レジスタ３２には キャリーメモリ２８も設けられており、このメモリへ第２の部分和レジスタ３２ と並列に、加算器２６の出力側２７ａに生じたキャリーが制御リード線８により 制御されて書き込まれる。

部分和レジスタ３０と３２の出力側３１および３３はマルチプレクサ３４の２つ の入力側へ導かれており、このマルチプレクサは制御リード線８により制御され て出力側３１をキャリーメモリ２８の出力側３７とともに、あるいは出力側３３ を、加算器２６の第２の入力端３５と接続する。さらに、出力側３１は一連の積 の処理終了時にめられた和を伝送する。

しかし、レジスタ３２の内容も読み出して他の素子へ供給できるようにすること が好適であることも多い。

次に、第２図のタイムチャートを参照して第１図に示された装置の動作を説明す る。第２図において個々の行の前に記されている番号は、対応する参照番号で示 された接続線路における信号ないし値またはブロックの内容を表わしている。第 １図に示されている装置はスカラー積つまり式 をめるために用いられる。

個々の値Ａ、およびＢ１は記憶されたものとして存在している。それというのは 、これらの値は所定の時点で必要とされるからである。そのつど新たな積Ｐｌ＝ Ａ、・Ｂ１の和が行われた後ごとに生じる中間和は常に一時記憶され、その際に 先行の中間和は消去される（書き換えられる）。最後の積の生成後に形成された 中間和は、同時に最終結果を成す。

第２図のタイムチャートではまず、最初の積はすでに処理され相応の中間和が形 成されていることを前提とする。したがって、第２のクロック周期Ｔ２の終了時 点し。は、一連の積の処理中の任意に選択された時点を表わしている。この時点 ｔ０　において、目下（現時点で）形成すぺぎ積Ｐ、の一方の因数Ａ、がこのク ロック周期下２中に記憶装置１２から読み出されてレジスタ１６へ書き込まれ、 この書き込み動作は、第１のクロック周期Ｔｌ中に高レベルになる線路８上の信 号により行われる。これと同時に、乗算器２０で形成された先行の積Ｐ１−１が 積レジスタ２２へ書き込まれる。部分和レジスタ３０および３２については後で 詳しく説明する。

時点ｔ。に続くクロック周期Ｔｌ中、形成すべき積の第２の値Ｂ、が記憶装置１ ２から読み出され、データバス１４を介してレジスタ１８の入力端へ供給される 。このクロック周期中は低レベルである制御リード線路９上の信号によりマルチ プレクサ２４が制御され、積Ｐ１−４のＬＳＢビットを転送する接続線路２９が 加算器２６の入力端２５と接続され、これと同時に、同じようにして制御される マルチプレクサ３４を介して、部分和レジスタ３２の出力側３３が加算器２６の 入力側３５と接続される。加算器２６はクロック周期ＴＩ終了間際に出力側２７ を介してこの部分和を出力する。

クロック周期ＴＩの終了時、つまり制御リード線８上の信号が低レベルになり制 御リード線９上の信号が高レベルになった時点ｔ１　において、このようにして 形成されたＬＳＢの部分和半部が第２の和レジスタ３２へ書き込まれ、これと同 時に、出力側２７ａを介して出力されたキャリー信号がキャリーメモリ２８へ書 き込まれる。さらに、形成すべき積の第２の因数８１がレジスタ１８へ書き込ま れる。さらに２つのマルチプレクサ２４と３４が切り換えられ、その結果、新た に加算器２６の入力側２５が、同じ内容のまま保持されている積レジスタ２２の 出力側２３における積Ｐ、−３のＭＳＢビットを受け取り、これと同時に、加算 器２６の入力側３５は、第１の部分和レジスタ３０内に記憶された先行の部分和 のＭＳＢビットと、キャリーメモリ２８から出力側３７を介して出力されたキャ リーとを受け取る。その結果、今度は加算器２６において新たな中間和のＭＳＢ 部分が形成され、出力側２７を介して出力される。これと同時に、レジスタ１６ と１８内には両方の値Ａ１およびＢ、が存在しているので乗算器２０は次の積Ｐ １を形成する。さらに、制御特表平？−５０１１６７（５） 装置は次の積Ｐ１ヤ、のための第１の値Ａ、＋、　をアドレス指定し、この値を バス１４を介してとりわけレジスタ１６へ供給する。

クロック周期Ｔ２の終了時つまり時点ｔ、において、リード線８における制御信 号が高レベルになり、その結果、（直ＡＩ＋ｌがレジスタ１６中に書き込まれ、 これと同時に、乗算器２０により出力側２１を介して出方された積Ｐ１が積レジ スタ２２へ書き込まれる。さらレジスタ３０中に書き込まれる。このようにして 積Ｐし１の処理は終了し、次に積レジスタ２２内に記憶されている積Ｐ１　を続 いて処理することができる。

このことは図示された第２のクロック周期ＴＩ中に行われ、この周期中、マルチ プレクサ２４は再び切り換えられ、積レジスタ２２の出力側２９における積Ｐ１ のＬＳＢビットを加算器２６の入力側２５へ供給する。これと同時に、加算器２ ６の他方の入力側３５は、マルチプレクサ３４を介して第２の部分和レジスタ３ が形成され、これはクロック周期ＴＩの終了時つまり時点ｔ、において第２の部 分和レジスタ３２中に書き込まれる。さらにこれと同時に、クロック周期ＴＩ中 に読み出された第２の値Ｂｌ＋、がレジスタ１８に書き込まれる。

図示された第３のクロック周期Ｔ２中、乗算器２゜の出力側２１において次の有 効な積Ｐ　ｌ＋ｌ　が形成され、これと同時に、積レジスタ２２からのＭＳＢビ ットが加算器２６の入力側２５へ供給され、さらに入力側３５は、第１の部分和 レジスタ３ｏがらの先行のＭＳＢの部分和Ｓ　Ｉ−１とキャリーメモリ２８から のキャリー信号とを受け取る。その結果、加算器２６の出カ側２分和は、図示さ れた第３のクロック周期Ｔ２の終了時に再び第１の部分和レジスタ３ｏ中に書き 込まれる。

このプロセスは、連続処理されるすべての積が計算され部分和レジスタで累算処 理されてしまうまで、繰り返し続けられる。第２図に示されているように、この 処理はパイプライン方式（流れ作業式）で行われる。

つまり１つの積を形成している間に同時に先行の部分和が形成され、かつ次の積 の値が供給される。したがってスタートに際しては、つまり最初の積ＰＩ　を形 成するときには、いくつかの準備処理ステップが必要である。

これらのステップは、ｉ＝１であるものと考えれば第２図から明らかである。つ まり、時点ｔ。よりも前にまずはじめに１つの値Ａ１　を読み出し時点ｔ。にお いてレジスタに書き込む必要がある。次に、第２の値Ｂ、が読み出され、時点ｔ １　においてレジスタ１８に書き込まれる。これに続いて第１の積Ｐ、を形成す ることができ、したがってこの積を時点ｔ２　において積レジスタ２２へ書き込 むことができる。積Ｐ１　は既述のようにして処理可能である。もちろんこれら の先行の処理ステップ中、部分和レジスタ３０と３２の内容は消去されていなけ ればならず、つまりこれらのレジスタには値０が格納されていなければならない 。

このようにして連続処理される積の和が形成され、その際、丸めによる誤差が伴 うことなく完璧な精度が維持され、しかもｌワード幅のための加算器しか必要と されない。

国際調査報告 フロントページの続き （７２）発明者　へルヴイヒ、カール ドイツ連邦共和国　８５００　ニュルンベルク９０　リターシュトラーセ　１０ （７２）発明者　ローレンツ、ディートマールドイツ連邦共和国　８５２０　エ アランゲンブッケンホー　ファー　ヴエーク　斜

Claims (3)

【特許請求の範囲】
1. １．順次連続して供給されるそれぞれ２つの数値の一連の積の和を形成する方法 であって、生成和のそれぞれの中間結果が一時記憶されるようにして一連の積の 和を形成する方法において、 それぞれ別個の乗算により形成された積を２つのステップで中間結果に加算し、 当該の加算においてこれらのステップのうち第１のステップ中、前記の積のＬＳ Ｂの桁値だけを中間結果の相応の桁値に加算し、このようにして形成された第１ の部分和を一時記憶し、 他方、第２のステップ中、当該の積の比較的高いウェイトの残りの桁値を中間和 の相応の残りの桁値と前記の第１の部分和のキャリーに加算し、このようにして 形成された第２の部分和を一時記憶し、各ステップ中、すぐ後に続いて乗算すべ き数値のうちの他方の数値を供給することを特徴とする、一連の積の和を形成す る方法。
2. ２．それぞれ第１の値と第２の値の一連の積の和を形成する装置であって、 あらかじめ定められた第１のビット数を有する複数個の値を記憶する記憶装置と 、 レジスタヘの値の書き込みを制御するクロック制御付制御装置と、 互いに乗算すべきそれぞれ２つの値を記憶する第１のレジスタ装置と、 該第１のレジスタ装置と接続された２つの入力側を有する乗算器と、 前記の第１のビット数の２倍のビット数のための出力側を有する後置接続された 積レジスタと、それぞれ前記の第１のビット数のための２つの和入力側を有し該 和入力側の一方は前記積レジスタの出力側と結合可能である加算器と、 それぞれ前記の第１のビット数のための少なくとも２つの部分和レジスタから成 る後置接続された和レジスタとが設けられており、該和レジスタは、前記加算器 の他方の入力側と結合可能な出力側を有するように構成されている、 それぞれ第１の値と第２の値の一連の積の和を形成する装置において、 記憶装置（１２）は、前記の第１のビット数のためのただ１つのデータバス（１ ４）を介して第１のレジスタ装置（１６，１８）と接続されており、制御装置（ １０）は、第１のクロツク周期と第２のクロック周期とで周期的に動作するよう に構成されており、 該制御装置により第１のクロック周期中、積レジスタ（２２）の出力側における 前記の第１のビット数のＬＳＢビットと第２の部分和レジスタ（３２）の内容と が、前記加算装置（２６）の入力側へ供給され、該第１のクロック周期の終了時 に、前記の第１の値のうちの１つ（Ｂｉ）がレジスタ装置（１６）へ書き込まれ 、かつ前記加算装置（２６）の出力側に生じる新たな部分和が第２の部分和レジ スタ（３２）へ書き込まれ、 前記制御装置により第２のクロック周期中、積レジスタ（２２）の出力側におけ る前記第１のビット数のＭＳＢビットと、第１の部分和レジスタの内容と、一時 記憶されていたキャリーとが、加算器（２６）へ供給され、該第２のクロック周 期の終了時に、第２の値の一方（Ａｉ＋１）がレジスタ装置（１６，１８）へ書 き込まれ、前記加算器（２６）の出力側に生じる第２の部分和が第１の部分和レ ジスタへ書き込まれ、かつ乗算器（２０）により形成された積が積レジスタ（２ ２）へ書き込まれることを特徴とする、 それぞれ第１の値と第２の値による一連の積の和を形成する装置。
3. ３．前記積レジスタ（２２）の出力側と前記加算器（２６）の一方の和入力側と の間に第１のマルチプレクサ（２４）が接続されており、 前記部分和レジスタ（３０，３２）の各出力側と前記加算器（２６）の他方の入 力側との間に第２のマルチプレクサ（３４）が接続されており、前記制御装置（ １０）は、各クロック井周期が終了するたびに前記マルチプレクサを切り換える ように構成されている、請求項２記載の装置。