JPH0374418B2 - - Google Patents

Description

【発明の詳細な説明】

（技術分野） 本発明は２進乗算装置に関する。 （背景技術） ２進乗算の原理はよく知られている。被乗数が
乗数の最も小さい重みのデイジツトと掛合わさ
れ、次いで次に大きい重みのデイジツトと掛合わ
され、こうして最も大きい重みのデイジツトと掛
合わされる。各掛合わせごとに部分積が作成さ
れ、種々の部分積は各部分積と前の部分積との間
の１デイジツトだけ左横にシフトさせて加算され
る。漸次シフトされた全ての部分積の和は乗算の
結果を形成する。 具体的には、部分積はレジスタに格納されるこ
とができ、１ランクだけシフトされた結果は次の
部分積と加算され、その結果が同じレジスタに格
納され、以後同様なことが繰返される。この連続
手順は長い手順となる。 これまでに全部分積が同時に形成されかつ加算
される（組合せであつて連続的論理でない）よう
な乗算装置の設計のためにかなりの努力がなされ
てきた。そして部分積の加算のための時間を低減
させることにより、あるいは部分積の数を低減さ
せることにより演算素度を増加させようとする試
みがなされてきた。 加算時間は次のごとき改良された加算器を用い
て短くすることができる。 −数のデイジツトの基本的加算の桁上げ
（carryover；キヤリ）があるデイジツトから
次のデイジツトには伝播しないが全体としては
加算された状態であるような桁上げ保護を有す
る加算器。 −桁上げの値が、桁上げの伝播を待機する代わり
の入力の関数である予測値であるように予測型
桁上げを有する加算器。 −３つずつ部分積を順次グループ化するウオレス
トリー（Wallace tree）のごとき特別なパタ
ーンに接続された加算器。 加算時間の短縮とは無関係に、加算すべき部分
積の数は乗数のビツトの適当なコード化により減
少させることもできる。 ブース（Booth）のアルゴリズム及びその変形
により、ｎ個のデイジツトを有する乗数のために
ｎ個の部分積に代えてわずか（ｎ＋１）／２個の
部分積が形成され、各部分積４つまたは５つのと
りうる値Ｘ、−Ｘ、2X、−2Xを有し、Ｘが被乗数
となる。しかしながら、この種の技巧は回路の複
雑さを増大させ、その結果大きなスペースが必要
となるという欠点があつた。 （発明の課題） 本発明は、演算速度と回路に要求される複雑さ
及びスペースその間のより良い歩み寄りを与える
２進乗算楝を提供することを目的とする。本発明
はわずか（ｎ＋１）／２個の部分積を形成するご
とき信号処理を用い、これらの部分積の各々は２
つの値０、Ｘ、−Ｘ（Ｘは被乗数）のみをとるもの
とする。これらの部分積は桁上げ伝播なしの加算
により２つずつ加算される。このことは非常に重
要なことである。何故ならば、ｎビツトの加算部
の複数の素加算器間の桁上げの伝播が時間を消費
し、ｎが大きくなるにつれて時間消費が大とな
る。 本発明による２進乗算装置は、被乗数Ｘである
第１の２進数と乗数Ｙである第２の２進数を論理
電気信号（x₀〜x₃、y₀〜y₃）の形で受取り、前記
２数の積を論理電気信号（zi）の形で出力する２
進乗算装置において、前記乗数Ｙのｎ個のデイジ
ツトを表わすｎ個の２進信号y_jを、ｎ個の係数b_j
（ｊ＝０〜ｎ−１）を表わす１組の論理（s₀、v₀
〜s₃、v₃）に変換するコーダを具備し、前記係数
b_jの各々は、 Ｙ＝b_o-12^n-1＋b_o-22^n-2＋…＋b₁2¹＋b₀ の形で表わされる２進数Ｙの２の各べき乗と掛合
わされ、該係数b_j値は０、１または−１のみをと
るものとし、２つの連続する係数b_jとb_j-1の積が
必ず零となり、更に、当該２進乗算装置が、前記
被乗数を表わす信号を受取りかつ前記コーダの出
力により制御されるルーチン回路と、該ルーチン
回路の出力を受取る加算手段とを具備する。 本発明の２進乗算装置は、演算速度とコンパク
トさとの歩み寄りの改善に達するために、前記被
乗数Ｘのｎ個のデイジツトを表わすｍ個の２進信
号xiをｍ個の係数ai（ｉ＝０〜ｍ−１）に変換す
るコーダを具備し、前記係数aiの各々は、 Ｘ＝a_n-12^m-1＋a_n-22^m-2＋…＋a₁2¹＋a₀ の形で表わされる２進数Ｘの２の各べき乗と掛合
わされ、該係数aiは０、１または−１のみをとる
ものとし、２つの連続する係数aiとa_i-1の積が必
ず零となる。 理論によれば、係数xiまたはy_jを指摘した性質
を有する係数ai及びb_jにコード化することは可能
であり、一義的に行なえることが示される。 ３つのとりうる値０、１、−１を有する係数ai
及びb_jは一対の２進論理信号により表わされるの
が好ましく、コーダは被乗数及び乗数のｍ個また
はｎ個の２進デイジツトからｍ組またはｎ組の２
進論理信号を出力する。 これらの組の符号化された論理信号は乗算を実
行するために必要な論理演算の加算及びシフトを
受けるようになる。 本発明の２進乗算装置は、それぞれが被乗数用
コーダからの２組のコード化された論理信号を受
取りかつ前記組と同様にコード化された和及び桁
上げを出力する一連の素加算器より成る少なくと
も１つの加算手段を具備し、これら一連の素加算
器は最初と最後の素加算器の間において桁上げの
伝播を待機することなくこれら全部が同時に動作
するように相互接続されている。換言すれば、該
加算手段の素加算器は、それらが桁上げ入力を有
している場合、それらが実行する加算の桁上げが
前記桁上げ入力に加わる桁上げとは無関係となる
ようになされる。 （発明の構成及び作用） 以下、本発明の乗算装置を４ビツトの被乗数と
４ビツトの乗数との乗算を基にして説明し、更に
適当なところでその一般化につき述べる。 演算は、次の形で書き表わすことのできる、２
の補数でコード化され正負符号が付された入力２
進数により行なわれるものとする。 被乗数：Ｘ＝−x₃・2³＋x₂・2²＋x₁・2¹＋x₀ 乗数：Ｙ＝−y₃・2³＋y₂・2²＋y₁・2¹＋y₀ 最も大きい重みのビツトは符号ビツトである
（０＝正、１＝負）。 第１図にブロツク図が示されている本発明の好
ましい実施例では、被乗数及び乗数は、それらが
示すデイジツトと同じネームx₀〜x₃、y₀〜y₃を有
する２進論理信号により表わされ、被乗数Ｘはコ
ーダ１０に加えられ、乗数Ｙはコーダ１２に加え
られる。 コーダ１２は、乗数Ｙの２進デイジツトy₀，
y₁，y₂，y₃に対応する４つの論理入力レベルを受
取り、これらを４対の論理出力信号（s₀、v₀）、
（s₁、v₁）、（s₂、v₂）、（s₃、v₃）に変換する。これ
らの論理出力信号はそれぞれ係数b₀，b₁，b₂，b₃
を表わす。すなわち、 Ｙ＝b₃・2³＋b₂・2²＋b₁・2¹＋b₀ となる。ここで係数b_jは、３つの値０、１、−１
のみをとることができかつ２つの連続する係数b_j
とb_j-1との積が０となる性質を有している。換言
すれば、２つの連続する０でない係数をとること
はできない。 係数の値とコーダの出力信号対の論理レベルと
の間に対応関係は次のとおりである。 b_j＝０ならばs_j＝０、v_j＝０ b_j＝１ならばs_j＝０、v_j＝１ b_j＝−１ならばs_j＝１、v_j＝１ s_j＝１、v_j＝０の組合せは禁止され、コーダ１
２の出力には現われない。値０、１、−１と対
（s_j、v_j）との間の対応コーデイングはここで選
択されたものと異なるようにしても良い。 コーダ１２はこのようにコード化された形の乗
数Ｙを出力する。ここでv_jは２のべき乗の係数の
絶対値０または１を示し、s_jは該係数の正・負符
号を示す。 乗算は通常、乗数の係数b_jをとりだし、後で適
当なシフトにより互いに加算される部分積を得る
ために前記係数の各々と被乗数との積を作ること
より成る。 b_j＝０ならば部分積は０、 b_j＝１ならば部分積はＸ（被乗数）、 b_j＝−１ならば部分積は−Ｘ、 である。 被乗数Ｘ自身はコーダ１０によりコード化され
る。コーダ１０は、ちようどコーダ１２のよう
に、２進デイジツトx₀，x₁，x₂，x₃に対応する４
つの論理入力レベルを４対の論理出力信号（r₀、
u₀）、（r₁、u₁）、（r₂、u₂）、（r₃、u₃）に変換する
。
この各対の論理出力信号はそれぞれ係数a₀，a₁，
a₂，a₃を表わす。すなわち、 Ｘ＝a₃・2³＋a₂・2²＋a₁・2¹＋a₀ となる。ここで係数aiは、係数b_jと同じ性質を有
しかつ信号b_jが信号（s_j、v_j）によりコード化さ
れるのと同様に信号（ri、ui）によりコード化さ
れる。すなわち、 ai＝０ならばri＝０、ui＝０ ai＝１ならばri＝０、ui＝１ ai＝−１ならばri＝１、ui＝１ となる。 ri＝１、ui＝０の組合せは禁止され、コーダ１
０の出力は現われない。 そしてコーダ１０はこのようにコード化された
形で被乗数Ｘを出力する。ここでuiは２のべき乗
の係数の絶対値０または１を示す、riは該係数の
符号（０＝正、１＝負）を示す。 値０、１、−１と２つの論理レベル（ri、ui）
との間の対応性コーデイングはここで選択された
ものと異なるようにしても良い。 また更に、被乗数用コーダ１０は部分積を形成
するためのものでありかつこれらの部分積は前に
説明したコーデイングにより値０、Ｘ、−Ｘをと
るので、コーダ１０はその出力においてＸ及び−
Ｘ、すなわち値aiとその反対の値−aiの両方の値
を出力するのが好ましい。 これは、コーダ１０の内部もしくは外部に、ri
の補数ri^*を出力するインバータを設けることに
より非常にシンプルに得ることができる。なお、
この補数は、ui＝０のときには禁止された組合
（ri＝１、ui＝０）とならないように強制的に０
となる。 第１図では、被乗数用コーダ１０の出力に、対
をなす出力信号（ri、ui）ではなく、２つの可能
な対（ri、ui）＝ai、（ri^*、ui^*）＝−aiを表わすト
リプレツト（三つ組）（ri、ri^*、ui）が示されて
いる。 第２図は、組合せri^*、ui＝１、０を禁止して、
対（ri、ui）からトリプレツト（ri、ri^*、ui）を
形成するためのインバータ１４と禁止ANDゲー
ト１６を具備した非常にシンプルな論理図を示
す。 第１図において、トリプレツト（ri、ri^*、ui）
が入力信号として論理ルーチン回路１８に加えら
れる。論理ルーチン回路１８はコーダ１２の４つ
の出力信号対（s_j、v_j）により制御され、種々の
入力信号（r₀〜r₃、r₀ ^*〜r₃ ^*、u₀〜u₃）をコーダ
１２からの４つの制御信号対（s_j、v_j）の値の関
数として十分定められた出力にあてがう。 ルーチン回路１８は部分積０、Ｘ、−Ｘを形成
すると共にこれらの部分積を加算する前に部分積
を適当にシフトさせる機能を有する。 ルーチン回路１８の出力は加算部２０の種々の
入力に加えられ、制御信号対（s_j、v_j）の関数と
して十分定められた部分積の加算を行ないかつコ
ード化された形の乗算結果をその出力に得る。デ
コーダ２２を加算部２０の出力に設けて、値x₀，
x₁，x₂，x₃を値（r₀、u₀）、（r₁、u₁）、（r₂、u₂）、
（r₃、u₃）に変化させるために使用されたコード
と逆のコードに従つて、加算部２０の出力信号対
を２進コードに再変換させることができる。 なお、乗数が４ビツト以上、例えば８ビツトも
しくは16ビツトであるときは、後者を４つのグル
ープとし、４つの各グループごとのルーチン回路
及び加算部を設けることが必要となる。これらの
加算部の出力は、２進形に再変換されるにしろさ
れないにしろ、第２の段階で適当なシフトにより
２つずつ加算され、第３の段階で…、というよう
に出力結果が最後の１つの加算部から得られるよ
うになるまでこの操作が続けられる。この結果は
必要があれば２進コードに再変換される。これに
対し、第１図の構成では、被乗数が４ビツト以上
のときは、より多くの入力及び出力を有する、コ
ーダ１０、ルーチン回路１８及び加算部２０を必
要とするのみである。 コーダ１０，１２、ルーチン回路１８及び加算
部２０の詳細を説明する前に、部分積の作成及び
該部分積の加算について数値例を挙げて説明す
る。ここでは乗数Ｙは４ビツトであり、被乗数Ｘ
は４ビツトであるが、この点は演算を理解するた
めにはさほど重要ではなく、ｍビツトへの一般化
はすぐに行なうことができる。 入力２進数は“２の補数”と呼ばれる形式をと
るものであり、これらは最も大きい重みのビツト
が符号ビツトである符号付けされた数である。 Ｘ＝1011（10進法の−５）をＹ＝0110（10進法の
＋６）と掛合わせる。 Ｘ及びＹを前述したような性質を有する係数ai
及びbiにより書き表わす唯一の方法は、 Ｘ＝−2²、−2⁰、すなわち（a₃，a₂，a₁，a₀）＝
（０、−１、０、−１） Ｙ＝2³−2¹、すなわち（b₃，b₂，b₁，b₀）＝
（１、０、−１、０） であることが示される。 ここでコーダ１０は次の論理レベル対、 r₃、u₃＝00（a₃＝０） r₂、u₂＝11（a₂＝−１） r₁、u₁＝00（a₁＝０） r₀、u₀＝11（a₀＝−１） を出力すると共に、次の反対の対、 r₃ ^*、u₃＝00（−a₃＝０） r₂ ^*、u₂＝01（−a₂＝１） r₁ ^*、u₁＝00（−a₁＝０） r₀ ^*、u₀＝01（−a₀＝１） を出力する。 コーダ１２は次の論理レベル対を出力する。 s₃、v₃＝01（b₃＝１） s₂、v₂＝00（b₂＝０） s₁、v₁＝11（b₁＝−１） s₀、v₀＝00（b₀＝０） ＸとＹの乗算は従来の４ビツト乗算として表わ
すことができるが、ここではいくつかのデイジツ
トが負となつている。

【表】 ０ −１ ０ ０ ０ １ ０
結果は０、−１、０、０、０、１、０、すなわ
ち−2⁵＋2¹＝−30となる。 順次書き表わされる４つの部分積はそれぞれ
（重みが増す順）０、−Ｘ、０、Ｘである。４つの
部分積のうちの２つが零でなく、最終的な結果に
寄与する。 この結果は、乗数の係数b_jを得るために使用さ
れる特別なコーテイングの性質から得られるもの
である。２つの連続して零でない係数b_jを得るこ
とはできない。 このために、４ビツト以上の乗数に対しては、
これらのビツトは、適当なシフトにより加算され
る２つの零でない部分積をその都度作成するため
に４つにグループ化される。 加算はデイジツトの縦列で行なわれる。換言す
れば、加算部２０はとりうむ縦列と同じ数の素加
算器を実質的に具備している。すなわち被乗算が
ｍ個のデイジツトを有するとき（ｍ＋３）個とな
る。実際には後述するように（ｍ＋１）個の加算
器で良い。 各素加算器（elementary adder）は、第１の
入力（実際には第１の対をなす入力）において第
１番目もしくは第２番目の部分積から第１のデイ
ジツトを受取り、第２の入力（実際には第２の対
をなす入力）において第３番目もしくは第４番目
の部分積から第２のデイジツトを受取る。 ルーチン回路１８は、コーダ１２の出力におけ
る乗数の係数値b_jに応じて、被乗数のデイジツト
aiを受取る素加算器の適当な入力な該デイジツト
aiを送るようにする。形成すべき部分積が−Ｘの
とき値aiを反転させ、その部分積が０のとき値ai
をキヤンセルする。最終的に、ルーチン回路１８
は加算すべき部分積のデイジツトの適当なシフト
を行なう。 一般にランクｉの素加算器は次の和を計算す
る。 ai・b₀＋a_i-1・b₁＋a_i-2・b₂＋a_i-3・b₃ この加算器の１つの入力には値ai・b₀及び値
a_i-1・b₁（２つのうち１つは必ず零となる）があ
てがわれ、別の入力には値a_i-2・b₂及び値a_i-3・
b₃（２つのうち１つは必ず零となる）があてがわ
れる。 そしてこの加算器はその第１の入力において、 b₀及びb₁がともに零ならば０、 b₀＝１ならばai、 b₀＝−１ならば−ai、 b₁＝１ならばa_i-1、 b₁＝−１ならば−a_i-1、 を受取る。 また、この加算器はその第２の入力において、 b₂及びb₃がともに零ならば０、 b₂＝１ならばa_i-2、 b₂＝−１ならば−a_i-2、 b₃＝１ならばa_i-3、 b₃＝−１ならば−a_i-3、 を受取る。 他の組合せはとることができない。 a_i-kのタイプの係数はｉ−ｋが負ならば当然零
とされる。 前述の論理テーブルにより、各係数aiまたはb_j
が２つの２進論理信号の形にコード化されること
を忘れることなしに、ルーチン回路１８の論理機
能を完全に定めることが可能となる。 第３図は、係数b_jを表わす信号（s_j、v_j）の関
数として所望の符号を有する所望の係数の対を、
ランクｉの素加算器Aiの入力に供給するために、
スイツチ・アレイ（MOSトランジスタ）、NOR
論理ゲート及びインバータを具備するルーチン回
路の一部を示す図である。 加算器Aiは、加算の第１項を形成する一対の
２進信号（すなわち場合に応じて０、ai、−ai、
a_i-1または−a_i-1）を受取る第１の組の入力Ci，
Ci´、及び加算の第２項を形成する一対の２進信号
（すなわち場合に応じて０、a_i-2、−a_i-2、a_i-3、−
a_i-3）を受取る第２の組の入力Di，D′iを有して
いる。 この加算器Aiは、係数ai及びb_jと同じコード化
により加算の２つの項の和を出力する第１の組の
出力Si，Si´を有している。すなわち和が０、１ま
たは−１ならば第１の組の出力はレベル対00、01
または11を出力する。更に、この加算器Aiは、
加算の桁上げ（キヤリ）を出力する第２の組の出
力Ri，Ri′を有している。実際、この桁上げは加
算１＋１（桁上げ１）または（−１）＋（−１）（桁
上げ−１）の場合、零とは異なる。この桁上げは
３つの可能な値を有し、再び係数ai及びb_jと同じ
コーデイングにより表示される。 第３図は全体を記述していないが、当業者にと
つてはこれで十分に明確に理解することができ、
次に示すようなルーチン機能を正しく付与できる
ことが分かる。 v₀＝０ならば、入力Ci，Ci′へのレベルri，ui
またはri^*，uiの伝送は、v₀により制御される
２つのMOSトランジスタにより禁止される。
v₀≠０でイネーブルであるならば、riまたはri^*
が２つのMOSトランジスタ及び１個のインバ
ータにより、s₀＝０またはs₀＝１に応じて伝送
される。 v₁＝０ならば、入力Ci，Ciへのレベルr_i-1，
u_i-1またはr^* _i-1，u_i-1の伝送は、v₁によつて制御
される上記とは別の２つのMOSトランジスタ
により禁止される。v₁≠０でイネーブルである
なばら、s₁により制御される２つのMOSトラ
ンジスタ及びインバータにより、s₁＝０または
s₁＝１に応じて、r_i-1またはr^* _i-1の伝送の選択が
行なわれる。 v₀及びv₁がともに零ならば、伝送が禁止され
ると共Ci及びCi′がv₀及びv₁を受取るNORゲー
トによつて制御される２つのトランジスタによ
り強制的に論理レベル零とされる。 同様な基本回路が、r_i-2、r^* _i-2、u_i-2または
r_i-3r^* _i-3、u_i-3を入力Di、Di′へ伝送するために
使用される。この場合、ルーチンは、v₀、v₁、
s₀、s₁の代わりにv₂、v₃及びs₂、s₃の制御の下
で行なわれる。 第３図は、４ビツトの乗数と掛合わされるｍビ
ツトの被乗数に対して論理的にはｍ＋３回繰返さ
れるパターンの１つを示しているだけである。実
際にはランク０及び１の加算器はなく、この場
合、ルーチン回路はこれらの２つのランクに対し
て部分積のデイジツトの和を直接出力する。何故
ならこれらの和は単一の項になるからである。 第４図はランク０及び１の部分積のデイジツト
の和に関するルーチン回路の一部を示す。この回
路部分は、ｉ＝１及びｉ＝０に対してa_i-3、a_i-2
及びa_i-1を零と考えなくてはならないことを考慮
に入れて第３図の回路を簡単化したものである。 −ランク０に対して；乗算の結果の零ランクのデ
イジツトとして伝送される唯一の部分積はa₀・
b₀であり、b₀＝０ならば（すなわち実際にはv₀
＝０ならば）０、b₀＝１ならば（すなわちs₀＝
０及びv₀＝１ならば）a₀すなわち（r₀、u₀）、s₀
＝１及びv₀＝１ならば−a₀すなわち（r₀ ^*、u₀）
である。第４図に示すルーチン論理回路部分
は、係数ai及びb_jと同じコーデイングにより２
つの論理レベルでa₀・b₀を表わす一対の信号
t₀，w₀を出力する。 −ランク１に対して；唯一の部分積は零でなく、
b₀＝０ならばa₀・b₁となり、b₁＝０ならばa₁・
b₀となる。第４図の回路は常に同じコーデイン
グにより表わされ場合に応じてa₁・b₁または
a₁・b₀を表わす２つの信号t₁，w₁を形成する。 t₀，w₀及びt₁，w₁、４ビツトの乗算の結果の最
も重みの小さい２つのデイジツトの値（０、＋１
または−１）を示す。 その他のデイジツトti，wiは、ルーチン回路１
８の出力を受取る素加算器A₂，A₃等より形成さ
れる。 第５図のブロツク図は、実質的に素加算器A₂
〜A_n+2よりなる加算部２０を示す。各素加算器
は２組の入力Ci，Ci′及びDi，Di′、１組の“和”
出力Si，Si′、並びに１組の“桁上げ”出力Ri，
Ri′を有している。和及び桁上げは、３つの値０、
１、−１をとりうる他の全ての係数と同様に２つ
の論理レベルでコード化される。 ここで非常に重要な点に注意しておく必要があ
る。被乗数は係数aiによつて、aiとa_i-1がともに
零とならないようにコード化されるので、素加算
器に伝送させる乗算の部分積は同じ性質を示す。
そして加算すべきデイジツトの同じ縦列において
偶然２つのデイジツトが１または２つのデイジツ
ト−１となつたならば、これらのデイジツトの
各々はその右側及び左側に確実に零を有する。従
つて、 当該加算は下のランクの加算の桁上げによつ
て乱されない。 当該加算自身は上のランクの加算の結果に加
算されるべき桁上げ１または−を生じせしめ
る。しかし上のランクの加算は零の加算から成
るだけなのでその結果は桁上げ１または−１と
等しくなるが、新しい桁上げは生じせしめな
い。 通常の加算の場合のように、桁上げがいくつか
の連続する加算器に亘つて伝播することはない。 このために、素加算器の配列及び相互接続は、
すべての加算器が前のランクの加算の桁上げを待
機することなしに同時に動作するようになされて
いる。この桁上げは、桁上げが起こる種々の場合
を考慮した論理ゲートにより加算器の出力にてシ
ンプルに加算される。 素加算器Aiの各々は和と桁上げを形成するが、
これらは自身の桁上げ結果をモデイフアイする、
前の段階からの桁上げ対する入力は具備していな
いという意味で、ここでは“半加算器”と言え
る。 第５図から分かるように、各素加算器Aiに対
して２つのORゲート２４及び２６が設けられて
いる。ORゲート２４は素加算器Aiの出力Siと素
加算器Ａの出力Riを受取る。ORゲート２６は出
力Si′及びR^* _i-1を受取る。ORゲート２４及び２６
は演算の全結果を表わす論理レベルti，wi、すな
わち乗算の結果のランクｉのデイジツトの値を出
力する。 素加算器A₂に対してこれらのORゲートは、前
段からの桁上げがないため不用となる。 これらのORゲートにより次のことが分かる。 −素加算器の桁上げは前段の桁上げによつては影
響されない。 −素加算器Ａの桁上げが00であるならば、素加算
器A_jにより出力される和00、01または11はOR
ゲートを介して通過することによつては修正さ
れない。素加算器A_j-1の桁上げが01または11な
らば、素加算器A_jは零を受取りその“和”出
力に一対のレベル00を出力しなければならず、
これは桁上げ01または11のORゲートを介する
通過を修正しない。 第６図は素加算器A_jの詳細に示す。この素加
算器は、値０、１及び−１のみをとる２つのデイ
ジツトの加算に対応する結果、すなわち和及び桁
上げを出力する。次の等式を考えることができ
る。 ０＋０＝和０、桁上げ０ ０＋１または１＋０＝和１、桁上げ０ ０＋(-1)または(-1)＋０＝和１、桁上げ０ １＋(-1)または(-1)＋１＝和０、桁上げ０ １＋１＝和０、桁上げ１ (-1)＋(-1)＝和１、桁上げ−１ これらの等式は、値０、１、−１が素加算器の
入力及び出力において論理レベル対00、01または
11により表わされるとしたときの論理機能を定め
る。 対応する論理図を第６図に示す。入力及び出力
のネームは第４図及び第５図のものと同じであ
る。 素加算器Aiは次の要素を具備する。 −入力Ci，Ci′，Di，Di′のベレルの論理補数Ci^*，
Ci′^*，Di^*，Di′^*を形成する４つのインバータ
２８，３０，３２，３４、 −信号Ci^*，C′i^*，Di^*，Di′^*を受取る４入力OR
ゲート３９及びその後続で加算の桁上げの符号
を出力Riに供給するインバータ３８： −入力Ci，Cii′，Di，Di′を受取るORゲート４
０、及びORゲート３６と４０の出力を受取る
ANDゲート４２；ANDゲート４２の出力は桁
上げの絶対値を出力Ri′に供給する、 −Ci，Ci′，Di^*，Di′^*を受取るORゲート４４、
Ci′^*，Ci，Di，Di^*を受取るORゲート４６、並
びにORゲート４４及び４６の出力を受取り実
行した和の符号を出力Si′に供給するNANDゲ
ート４８、 −Ci及びDiを受取り和の絶対値を出力Siに供給
するイクスクルーシブORゲート５０。 次にコーダ１０及び１２の詳細について説明
し、乗算器の入力に２進形で加えられる数Ｘ及び
Ｙ、値ai及びb_j、１及び−１が零により必要的に
分離されること、並びに前記係数の２つの論理レ
ベル00、01及び11でのコード化及び組合せ１０の
禁止から、前記コーダの役割をみる。 ２進係数xi（ｉ＝０〜ｍ−１）のターナリ係数
aiへのコード化は以下のようにして行なわれる。
数Ｘは、最も重みの大きいビツトが符号ビツトで
あるいわゆる“２の補数”形として書き表わせ
る。 中間論理信号pi及びqiが次のように形成され
る。 piはxi及びx_i-1のイクスクルーシルORの結果
（p₀＝x₀）である。 qiはpiとq_i-1の補数との論理積（q₀＝x₀）であ
る。従つて、ai＝（１−2X_i-1）qi、（（x_n＝x_n-1）
（数Ｘはｍ個のデイジツトx₀〜x_n-1のみを有す
る））となる。 上式が係数aiを計算するためにここで使用され
るアルゴリズムである。 そしてx_i+1＝０ならばai＝qi x_i+1＝１ならばai＝−qi となる。 qiは２つの可能なレベル０または１を有する論
理信号である。aiは３つの値０、１、−１をとる
ことができ、２つの２進信号ri及びuiにより表わ
される。 riはaiの符号を表わす。ri＝０を正の符号、ri
＝１を負の符号として選ぶならびに、x_i+1＝１に
対してai＝−qi、x_i+1＝０に対してai＝qiとなる
ので、ri＝x_i+1となるものとする。 実際には、qi＝０（ri、uiに対して組合せ１、
０は禁止）のときでも正の符号をとるようにri＝
x_i+1・qiとされる。 uiはaiの絶対値を表わし、uiはqiと等しくな
る。 上記より４つの入力２進係数x₀〜x₃に対する第
７図に示す論理コード回路の構造が導かれる。３
つのイクスクルーシブORゲート５２，５４，５
６はレベルp₃，p₂，p₁を形成し、p₀はx₀及びp₀，
u₀と等しい。３つのインバータ５８，６０，６２
はq₂，q₁，q₀よりこれらのレベルの補数q₂ ^*，
q₁ ^*，q₀ ^*を形成する。 ３つの２入力ANDゲート６４，６６，６８の
出力はレベルq₃，q₂，q₁を形成し、これらはレベ
ルu₃，u₂，u₁にもなる。各ANDゲートp₃q^*/2；p₂
及びq^*/1；p₁及びq^*/0をそれぞれ受取る。 ４つのANDゲート７０，７２，７３，７６は
q₃，x₃；q₂，x₃；q₁，x₂；q₀，x₁を受取り、レベ
ルr₃，r₂，r₁，r₀をそれぞれ形成する。 乗数用コーダについても全く同様なことが言
え、上記のxiをyiに置換え、信号ri、uiを信号s_j、
v_jに置換えれば十分である。 乗算の結果は（ｍ＋ｎ−１）個の係数ciので形
で得られる。該係数の各々は２つの２進レベル
ti，wiにより表わされ、ti，wi＝０、０ならばci
＝０となり、ti，wi＝０、１ならばci＝１とな
り、ti，wi＝１、１ならばci＝−１となる。 Ｚ＝c_n+o-22^m+n-2＋…＋Ci₂ ⁱ＋…＋c₀ ３つのとりうる値を有する係数ciを２つの値
０、１を有する２進係数ziに再変換することが好
ましい。 Ｚ＝−z_n+o-12^m+n-1＋…＋Zi₂ ⁱ＋…＋z₀ （いわゆる“２の補数”２進コードにおける数Ｚ
の式） デコーダ化は実際には非常にシンプルである。
正または零の係数Ci（ti＝０）が負または零の係
数Ci（ti＝１またはwi＝０）と分離される。 一連の正の係数は２進形の第１の正数に対応す
る。 一連の負の係数は第２の正数の反対の値に対応
する。 そして、数Ｚは２つの正の２進数の差の形で書
き表わされる。これらの２進数の各々は大きい重
みの符号ビツトを加えかつそれらを加算すること
により“２の補数”形に書き表わすことができ
る。第１の正数に対しては、付加される符号ビツ
トは０であり、第２の正数に対しては、付加され
る符号ビツトは１であり、対応する２の補数は、
第２の正数のビツトを相補しかつ最も重みの小さ
い１を加えることにより形成される。 そして“２の補数”形に書き表わされた２つの
数は、２の補数形の数Ｚを付与するために加算さ
れる。 第８図はデコード回路を示す。 各係数ciから２進係数diが正数い対して形成さ
れる（ci＝０または−１ならばdi＝０であり、ci
＝１ならばdi＝１となる）。diは、ti及びwi、す
なわち係数ciの符号及び絶対値を受取るイクスク
ルーシブORゲート７８の出力にて得られる。 係数eiは負数に対して形成される（ci＝０また
は１ならばei＝０となり、ci＝−１ならばｅとな
る）。eiは係数ciの符号ビツトtiと全く同じであ
る。 符号ビツト０は正数に加えられ、符号ビツト１
は負数に加えられる。 正数と負数の和は、係数diと（インバータ８０
により形成された）係数eiの補数とのビツトごと
の加算及び最も重みの小さい１の付加により与え
られる。 この加算は、（最も重みの小さい１を加える）
ために強制的に１にされる桁上げ入力と、レベル
diを受取る入力と、レベルeiの補数を受取る入力
とを有する、（ｍ＋ｎ）ビツトの従来式の２進加
算器８２により実行される。更に、最も重みの大
きい入力の対は０、１、すなわち正数及び負数の
各符号ビツトを受取る。 この加算の結果は、乗算の結果の２進係数（２
の補数形）を表わす一連の論理レベルz₀〜z_n+o-1
である。 実際には、２の補数形で表わされる乗数及び被
乗数のビツト数ｍ及びｎを考慮して、同じ形式で
表現された乗数の結果は、z_n+o-2である符号ビツ
トを含む（ｍ＋ｎ−１）個の係数z₀〜z_n+o-2から
成ることが示される。 符号０及び１の入力並びに次の理由で不用とな
る出力z_n+o-1を抑制することにより（ｍ＋ｎ−
１）ビツトの加算器８２を設けるので十分である
と結論づけられる。 (a) z_n+o-1は通常z_n+o-2に等しい。 (b) ２の補数形において、２つの最も重みの大き
い、ビツトが等しいならば、これらは同じ値を
有する単一の符号ビツトにより置換えることが
できる。 本発明による乗算装置の記述を終えるために、
４ビツト以上、例えば16ビツトを有する乗算装置
の場合、これらのビツトは４つのグループ化さ
れ、係数ci（論理レベルti，wi）が４つの乗算の
結果として得られることを指摘しておく。これら
のレベルは、桁上げ伝播を有する加算器及び各素
加算器が第６図に示すタイプの２つの半加算器よ
りなる以外は、加算部２０と同じ加算手段に導入
される。４ビツトの乗算の結果を２進形（２つ補
数形）に変換し、従来式の２進加算器で互いに加
算させることも可能である。 上述の記載の全体において、禁止された組合せ
を10とし、値０、１、−１を表わすためにコード
00、01、11を選択することはいくつかの可能な選
択のうちの１つであり、このコードを変化させれ
ば既述した論理回路の論理構造を若干変化させる
必要がでてくることが考えられる。 既述した好ましい実施例は乗数用コーダと被乗
数用コーダを具備している。これらを使用する
と、加算すべき多くの部分積に利点が得られ、加
算部２０は（桁上げ伝播を有する）２進加算器と
し、デコーダ２２はなくとも良い。

【図面の簡単な説明】

第１図は本発明による４ビツト×４ビツト乗算
装置のブロツク図、第２図は上記乗算装置に使用
される詳細回路図、第３図は乗算を実行するため
に必要な部分積の形成及びシフトのための回路の
基本パターンを示す図、第４図は部分積を形成し
かつシフトするための回路の詳細を示し、この詳
細は部分積の最も小さい重みのビツトに関する、
第５図は部分積加算手段を示す図、第６図は２つ
の論理レベル値０、１、−１をとる２つのコード
化されたデイジツトを加算しかつ同様にコード化
された和及び桁上げを出力する、桁上げ入力のな
い素加算器を示す図、第７図は被乗算（乗数）用
コーダを示す図、第８図は乗算の結果を２進形に
再変換するためのデコーダを示す図である。 １０……コーダ、１２……コーダ、１８……ル
ーチン回路、２０……加算部、２２……デコー
ダ。

Claims (1)

1. 【特許請求の範囲】 １ 被乗数Ｘである第１の２進数と乗数Ｙである
   第２の２進数を論理電気信号の形で受取り、前記
   ２数の積を論理電気信号（zi）の形で出力する２
   進乗算装置において、 数値Ｙをあらわすｎ個の２進数y_j（ｊ＝０〜ｎ
   −１）をｎ対の２進数（s_j、v_j）に変換するコー
   ダを具備し、各対はひとつの係数b_j（ｊ＝０〜ｎ
   −１）をあらわし、b_jは０、１又は−１であり、
   各対の一方の信号s_jはb_jの正負をあらわし、各対
   の他方の信号v_jはb_jのモジユロをあらわし、２つ
   の連続する係数b_jとb_j-1の積は０であり、係数b_j
   は次の式を満足し、 Ｙ＝b_o-12^n-1＋b_o-22^n-2＋…＋b₁2¹＋b₀ 前記コーダがｊの各値毎に、y_j及びy_j-1を受け
   取るイクスルーシブORゲートと、該イクスクル
   ーシブORゲートの出力p_j 及びインバータにより
   反転される信号v_j-1を受け取るANDゲートを具
   備し、該ANDゲートの出力が信号v_jを供給し、
   更に信号v_j及びy_j+1（ｊ≠ｎ−１）又はy_j-1（ｊ＝
   ｎ−１）をうけとる別のANDゲートを有し、当
   該別のANDゲートは信号s_jを出力し、前記コー
   ダは２進数s_j及びv_jを供給する出力と、y₀に等し
   い信号v₀及びy₀とy₁の論理積であるs₀を供給する
   出力とを有することを特徴とする２進乗算装置。 ２ Ｘが被乗数であり、Ｙが乗数であり、乗算回
   路がＸを表す２進数を受け取るルーチン回路と２
   進加算ステージを有し、前記ルーチン回路がコー
   ダの出力s_j，v_jにより制御され、前記加算ステー
   ジがルーチン回路の出力を受信することを特徴と
   する、特許請求の範囲第１項記載の２進乗算装
   置。 ３ ３つの値０、１、−１をとる係数ciを表す対
   をなす論理信号（ti、wi）を受取り、前記対によ
   つて表される数Ｚ；Ｚ＝c_n+o-22^m+n-2＋…＋c₁2¹
   ＋c₀を２進論理出力ziにより表される２進数、 Ｚ＝z_n+o-12^m+n-1＋z_n+o-22^m+n-2＋…＋z₁2¹＋z₀ に変換するデコーダを具備することを特徴とする
   特許請求の範囲第１項〜第２項のうちのいずれか
   １項に記載の２進乗算装置。 ４ 被乗数Ｘである第１の２進数と乗数Ｙである
   第２の２進数を論理電気信号の形で受取り、前記
   ２数の積を論理電気信号（zi）の形で出力する２
   進乗算装置において、数値Ｙをあらわすｎ個の２
   進数y_j（ｊ＝０〜ｎ−１）をｎ対の２進数（s_j、
   v_j）に変換するコーダを具備し、各対はひとつの
   係数b_j（ｊ＝０〜ｎ−１）をあらわし、b_jは０、
   １又は−１であり、各対の一方の信号s_jはb_jの正
   負をあらわし、各対の他方の信号v_jはb_jのモジユ
   ロをあらわし、２つの連続する係数b_jとb_j-1の積
   は０であり、係数b_jは次の式を満足し、 Ｙ＝b_o-12^n-1＋b_o-22^n-2＋…＋b₁2¹＋b₀ 前記乗算装置が数値Ｘをあらわすｍ個の２進数
   X_iをｍ対の２進数（r_i、u_i）に変換する第２のコ
   ーダを具備し、各対はひとつの係数a_i（ｉ＝０〜
   ｍ−１）をあらわし、a_iは０、１又は−１であ
   り、各対の一方の信号r_iはa_iの正負を表し、各対
   の他方の信号u_iはa_iのモジユロをあらわし、２つ
   の連続する係数a_iとa_i-1の積は０であり、係数a_i
   は次の式を満足し、 Ｘ＝a_n-12^m-1＋a_n-22^m-2＋…＋a₁2¹＋a₀ 前記乗算装置はルーチン回路と２進加算ステー
   ジを具備し、該ルーチン回路は第２のコーダの出
   力を受信すると共に第１のコーダの出力により制
   御され、前記加算ステージはルーチン回路の出力
   を受信することを特徴とする２進乗算装置。 ５ 前記第２のコーダがｍ個の２進論理信号ri^*
   を出力し、ri^*はui＝１ならばriの補数でありui＝
   ０ならば零であることを特徴とする特許請求の範
   囲第４項に記載の２進乗算装置。 ６ 前記ルーチン回路が、第１及び第２の組の入
   力を有する前記加算ステージの素加算器に、４組
   の制御信号に応じた信号を伝送し、すなわち、 −第１の組の入力（Ci、Ci′）には、 b₀及びb₁がともに零ならば０、 b₀＝１ならばr_i、u_i、 b₀＝−１ならばr_i ^*、u_i、 b₀＝１ならばr_i-1、u_i-1、 b₀＝−１ならばr_i ^* _-1、u_i-1、 を伝送し、 −第２の組の入力（Di、Di′）には、 b₂及びb₃がともに零ならば０、 b₂＝１ならばr_i-2、u_i-2、 b₂＝−１ならばr_i-2 ^*、u_i-2、 b₃＝１ならばr_i-3、u_i-3、 b₃＝−１ならばr_i-3 ^*、u_i-3、 を伝送し、u_i-kまたはr_i-kのタイプの信号はｉ−
   ｋが負ならば論理レベル０となり、ri^*はui＝１
   ならばriの補数、ui＝０ならば０となることを特
   徴とする特許請求の範囲第５項に記載の２進乗算
   装置。 ７ 前記加算器は、係数aiまたはbjの信号（ri、
   ui）または（sj、vj）へのコード化と同じ優位性
   を有するコード化に従つて和及び桁上げの組をそ
   の出力に供給し、加算器の“和”出力は各ORゲ
   ートの入力にそれぞれ供給され、これらのゲート
   はすぐ下のランクの加算器からの桁上げ出力を受
   け取ることを特徴とする特許請求の範囲第６項に
   記載の２進乗算装置。 ８ ３つの値０、１、−１をとる係数ciを表す対
   をなす論理信号（ti、wi）を受取り、前記対によ
   つて表される数Ｚ；Ｚ＝c_n+o-22^m+n-2＋…＋c₁2¹
   ＋c₀を２進論理出力ziにより表される２進数、 Ｚ＝−z_n+o-12^m+n-1＋z_n+o-22^m+n-2＋…＋z₁2¹＋z₀ に変換するデコーダを具備することを特徴とする
   特許請求の範囲第４項〜第７項のうちのいずれか
   １項に記載の２進乗算装置。 ９ 前記デコーダが、信号ti及びwiを受取り信号
   diを出力するイクスクルーシブORゲートと、信
   号tiを受取るインバータと、強制的に論理レベル
   １にされる桁上げ入力及び加算すべき信号のため
   の対をなす入力を有する２進加算器とを有し、該
   加算器の各組の入力が前記イクスルーシブORゲ
   ートの出力及び前記インバータの出力を受取るこ
   とを特徴とする特許請求の範囲第８項に記載の２
   進乗算装置。