JPH0582608B2 - - Google Patents

Description

【発明の詳細な説明】

産業上の利用分野 本発明は、演算処理装置および演算処理方法に
係り、特に内部演算に乗算を具え、LSI化に好適
な高速演算処理装置および演算処理方法に関す
る。 従来の技術 従来、高速乗算器については、電子通信学会論
文誌、VoI.J66−Ｄ、No.６（1983年）第683頁から
第690頁に冗長２進加算木を用いた２進乗算器が
論じられている。この冗長２進加算木を用いた乗
算器では、内部計算に各桁が｛−１，０，１｝の
要素である冗長２進表現（一種の符号付きデイジ
ツト表現）を利用している。ｎビツト乗算では、
ｎ個のｎビツト部分積を冗長２進数とみなして２
つずつ２分木状に冗長２進数体系で加え合せてい
き、最後に冗長２進表現で求まつた積を通常の２
進表現に変換する。冗長２進数体系では、２数の
加算を桁上げの伝搬なしに演算数の桁数に無関係
な一定時間で行える。従つて、冗長２進加算木を
用いた乗算器では、ｎビツト乗算を計算時間０
（log ｎ）で高速に行える。計算速度は、
Wallace木を用いた高速乗算器と同程度であり、
従来の配列型乗算器に較べかなり高速である。ま
た、回路構造は配列型乗算器と同様に規則正し
く、Wallace木を用いた乗算器よりレイアウトが
容易である。 また、除算法および開平法を冗長２進乗算器を
もつ算術演算処理装置の内部で実現する方法につ
いては、電子通信学会技術研究報告、AL85−90
（昭和61年３月）第45頁から第50頁に論じられて
いる。この方法では、乗算器で冗長２進数同士の
乗算を行う必要があり、乗算器に冗長２進同士の
乗算を行えるようにすると２進同士の乗算器に較
べハードウエア量が増加する。 発明が解決しようとする問題点 上記従来技術では、２ビツトBoothの方法を適
用し、乗数を４進符号付デイジツト数（各桁が
｛−２，−１，０，１，２｝の要素である４進数）
にリコードすることにより、部分積の数を約半分
にし、計算を高速化とハードウエア量の削減を行
つている。しかし、これらは２進数同士の乗算に
関するものであり、冗長２進数を乗数あるいは被
乗数の少なくとも一方に用いる乗算に関する配慮
がなされておらず、組合せ回路として冗長２進数
を扱う乗算を実現する場合、演算の桁数が大きく
なると、 ２進数同士の乗算に較べ、演算遅延
時間が大きい、 素子数が膨大かつ回路構成が
複雑となる、 演算処理装置をLSI1チツプに
実装が難しい等の問題点がある。 本発明の目的は、このような従来の問題点を改
善し、冗長２進数を扱える乗算器を規則正しい回
路構成で、かつ素子数の少ない組合せ回路として
実現し、内部演算の桁上げの伝播を最小にすると
共に回路構成を簡単化することによつてLSI1チ
ツプに実装が容易である高速な演算処理装置およ
び演算処理方法を提供することにある。 問題点を解決するための手段 上記目的は、乗算処理において、部分積生成を
２桁毎に行うために必要である乗数リコード回路
に、 乗数を２桁ずつのグループに分割し、各
グループの２桁と１つ下位のグループの上位桁と
の３桁から、そのグループにおける中間桁上げ
（中間桁借り）桁を求める中間桁上げ生成手段と、
前記３桁から、そのグループにおける中間結
果桁を求める中間結果生成手段と、 各グルー
プ毎に、そのグループの前記中間結果桁と１つ下
位のグループからの前記中間桁上げ（中間桁借
り）とからリコードされた乗数の桁を求めるリコ
ード数生成手段と中間を設け、第１ステツプでは
前記中間桁上げ生成手段および結果生成手段によ
る演算を行い、第２ステツプでは前記リコード数
生成手段による演算を行い、この２つのステツプ
によつて乗数のリコードを行うことにより、達成
される。 作 用 乗算において、まず、中間桁上げ生成手段によ
つて乗数（符号付きデイジツト表現数）を２桁ず
つのグループに分割し、各グループにおけるリコ
ードされた乗数の中間桁上げC_i（C_iは｛−１，０，
１｝のいずれかの要素である。）を生成し、中間
結果生成手段によつて各グループにおけるリコー
ドされた乗数の中間結果S_i（S_iは｛−２，−１，
０，１，２｝のいずれかの要素である。）を生成
する。次に、リコード数生成手段によつて各グル
ープ毎に、そのグループの前記中間結果S_iと１つ
下位のグループからの中間桁上げC_i-1を加算して
リコードされた乗数の桁B_i（B_iは｛−２，−１，
０，１，２｝のいずれかの要素である。）を生成
することにより、部分積の数を約半分にできるた
め、加算用セルの個数を約半減でき、部分積加算
の高速化とハードウエア量の削減が行える。 実施例 以下、本発明の一実施例を図面により説明す
る。 第２図は、本発明の一実施例を適用した乗算器
の構成図である。第２図の乗算器は、乗数リコー
ド回路１００、部分積生成器１１０、冗長加算器
１２０の木構造、および冗長２進・２進変換器１
３０とから構成されており少なくとも乗数が冗長
２進数である。 乗数リコード回路１００は、冗長２進数である
乗数を２桁ずつのグループ分割し、各グループ毎
に乗数を４進SD数（つまり、符号付デイジツト
数）にリコードする回路である。したがつて、リ
コードされた乗数の桁は｛−２，−１，０，１，
２｝のいずれかの要素である。なお、２進数も特
殊な冗長２進数とみなせるので、乗数が２進数の
場合にも本回路を使用することが可能である。 部分積生成器１１０は、前記乗数リコード回路
１００によつてリコードされた乗数の各桁毎に、
そのリコードされた乗数の桁の値に応じて、被乗
数の２倍と正負の符号反転等を行う回路である。
被乗数の２倍は被乗数の各桁を左へ１桁シフトす
ることにより行える。また、正負の符号反転は、
被乗数の各桁毎に正負の符号反転によつて行え
る。つまり、被乗数の桁が１の場合にその桁を−
１にし、−１の場合には１にする。または、被乗
数が２の補数表示の２進数のときには、２の補数
をとることによつて正負の符号反転を行える。し
たがつて本回路の実現は容易である。 冗長加算器１２０は、加算木を構成しており、
冗長２進数同士の冗長２進体系での加算を行う回
路である。 冗長２進・２進変換器１３０は、積として求ま
つた冗長２進数を２進数に変換する回路であり、
桁上げ先見加算器等で容易に実現できる。 次に、乗数リコード回路１００について説明す
る。 第１図は、本発明の一実施例における乗数リコ
ード回路１００を構成する基本回路の概略ブロツ
ク図である。第１図の基本回路は、中間桁上げ生
成部１、中間結果生成部２およびリコーデイツド
乗数生成部３から構成されており、中間桁上げ生
成部１および中間結果生成部２は共に、乗数の第
2j＋１桁x_2j+111，第2j桁x_2j12および第2j−１桁
x_2j-113を入力し、それぞれ第ｊ番目における中
間桁上げC_j21および中間結果S_j22を出力する。ま
たリコーデイツド乗数生成部３は、第ｊ番目にお
ける中間結果S_j22および第ｊ−１番目からの中間
桁上げC_j-123を入力し、リコードされた乗数の第
ｊ桁B_j31を出力する。つまり、乗数リコードは
２ステツプで行う。第１ステツプでは、乗数（冗
長２進数）を２桁ずつのグループに分割し、その
グループの２桁x_2j+111，x_2j12と１つ下位のグル
ープの上位桁x_2j-113とから、中間桁上げC_j21と
中間結果S_j22を求める。第ステツプでは、そのグ
ループの中間結果S_j22と１つ下位のグループから
の中間桁上げC_j-123とから、リコードされた乗数
の第ｊ桁B_j31を決定する。ただし、乗数の第2j＋
１桁x_2j+111，第2j桁x_2j12および第2j−１桁x_2j-1
13は｛−１，０，１｝のいずれかの値を表す信号
であり、第ｊ番目の中間桁上げC_j21および第ｊ−
１番目からの中間桁上げC_j-123も｛−１，０，
１｝のいずれかの値を表す信号であり、また、第
ｊ番目の中間和S_j22およびリコードされた乗数の
第ｊ桁B_j31は｛−２，−１，０，１，２｝のいず
れかの値を表す信号である。 以下、各グループについて説明する。 中間桁上げ生成部１は、(i)乗数の第2j−１桁
x_2j-113が−１のとき、第３図に示す規則により、
乗数の第2j桁x_2j12および第2j＋１桁x_2j+111から
中間桁上げC_j21を決定し、(ii)乗数の第2j−１桁
x_2j-113が０または１のとき、第４図に示す規則
により、乗数の第2j桁x_2j12および第2j＋１桁
x_2j+111から中間桁上げC_j21を決定する回路であ
る。 例えば、符号付きデイジツト数x_iおよびC_jの２
値信号化を次のように行う。乗数の１桁x_i

【表】 を表１に示す２ビツト２値信号x_i+x_i-で表現し、
中間桁上げ桁C_jを表１と同様の２ビツト２値信号
C_j+C_j-で表現する。このとき、中間桁上げ生成部
１は、 C_j ⁺＝x_2j+1+・x_2j＋x_2j+1+・_2j-・_2j-1-， C_j ^-＝x_2j+1-・x_2j-＋x_2j+1-・x_2j+・x_2j-1- と容易に設計できる。 中間結果生成部２は、(i) 乗数の第2j−１桁
x_2j-113が−１のとき、第５図に示す規則より、
乗数の第2j＋１桁x_2j+111および第2j桁x_2j12から
中間結果S_j22を決定し、(ii) 乗数の第2j−１桁
x_2j-113が０または１のとき、第６図に示す規則
により、乗数の第2j＋１桁x_2j+111および第2j桁
x_2j12から中間結果S_j22を決定する回路である。 例えば、乗数の桁x_iを前記表１に示す２ビツト
２値信号x_i+x_i-で表現し、中間結果S_jを表２に示
す３ビツト２値信号S_j-S_j2S_j1で表現すると、中間
結果生成部２は、 S_j-＝（x_2j+1+＋x_2j+1-）・（x_2j+＋_2j-・_2j-1-
） ＋（_2j+1+＋_2j+1-）・x_2j-， S_j2＝（x_2j+1+＋x_2j+1-）・（_2j+＋_2j-）， S_j1＝x_2j+＋x_2j- と容易に設計できる。

【表】 リコーデイツド乗数生成部３は、第ｊ番目の中
間結果S_jと１つ下位の第ｊ−１番目からの中間桁
上げC_j-1との加算、つまり算術和S_j＋C_j-1を行
い、リコードされた乗数の第ｊ桁を生成する回路
である。 例えば、中間桁上げC_jおよび中間結果S_jを前記
のように２値信号化を行い、リコードされた乗数
の桁B_jを前記中間結果S_jと同様に表２に示すよう
な３ビツト２値信号B_j-B_j2B_j1で表現すると、リ
コーデイツド乗数生成部３は、 B_j-＝S_j-・（_j1・_j-1+＋_j2・_j1・C_j-1-， B_j2＝S_j2・_j-1+・_j-1-＋S_j-・C_j-1-＋_j-・
S_j1・C_j-1+， B_j1＝_j1（C_j-1+＋C_j-1-） と容易に設計できる。ただし、以上の論理式にお
いて、・は論理積（AND），＋は論理積（OR），
は排他的論理和（EX−OR）および−は論理否
定を表す演算子である。 なお、本実施例では、乗数を第2j＋１桁x_2j+1と
第2j桁x_2jとの２桁ずつのグループに分割したが、
第2j桁x_2jと第2j−１桁x_2j-1との２桁からなるグ
ループに分割することも可能である。また、乗数
リコード回路１００は、これらのグループの各グ
ループに対し、各々第１図の基本回路を設けてい
る。 最後に、冗長加算器１２０について説明する。 冗長加算器１２０における加算規則を表３に示
す。

【表】 このとき、第ｉ桁における加算は次の論理式に
よつて決定される。 x_id＝x_i+＋x_i-， y_id＝y_i+＋y_i-， p_i＝_i-・_i-， u_i＝_id・_id・_i-1＋_id・_id・_i-1＋_i+・
_id＋
x_id・y_i+， t_i＝x_id・_id・p_i-1＋_id・y_id・p_i-1 ＋x_id・y_id・_i-1・＋_id・_id・_i-1， z_i+＝_i・_i-1， z_i＝t_i・u_i-1ｏ 第７図は、第２図の冗長加算器１２０を構成す
る加算用セルを示す概略回路図である。同図は特
にNOR／ORによつて加算用セルを実現した一例
である。 ゲート６１１から６２３まではそれぞれ
NOR／OR回路であり、信号x_i+６０２およびx_i-
６０３は被加数の冗長２進数の第ｉ桁x_iを表す２
ビツト信号であり、_i+６０１はx_i+６０２の論理
否定を表す信号であり、y_i+６０５およびy_i-６０
６は加数の冗長２進数の第ｉ桁y_iを表す２ビツト
信号であり、_i+６０４はy_i+６０５の論理否定を
表す信号である。また、信号p_i６３１は第ｉ桁の
被加数x_iおよび加数y_iの両方が非負であるかどう
かを表す信号であり、p_i-1６３３は第ｉ−１桁の
被加数x_i-1および加数y_i-1の両方が非負であるか
どうかを表す信号である。_i６３２，_i-1６３４
はそれぞれp_i６３１，p_i-1６３３の論理否定を表
す信号である。u_i６３５と_i６３６はそれぞれ第
ｉ桁における中間桁上げに関係する信号とその論
理否定を表す信号であり、u_i-1６３７と_i-1６３
８はそれぞれ第ｉ−１桁からの中間桁上げに関係
する信号とその論理否定を表す信号である。ま
た、z_i+６４２よびz_i-６４３は加算結果の第ｉ桁
z_iを表す２ビツト信号であり、_i+６４１はz_i+６
４２の論理否定を表す信号である。 なお、本実施例における回路図はECL回路を
意識しNOR／ORで構成したが、他のテクノロジ
（例えば、CMOS，NMOS，TTL，IIL等）ある
いは多値論理を用いても構成することが可能であ
る。 本実施例によれば、従来の冗長２進数を乗数に
もつ乗算器に較べ、部分積の個数が約半分になる
ので、冗長２進加算器の個数が半減し、冗長２進
加算木の段数も一段減る等の効果がある。 発明の効果 本発明によれば、各桁が負，０，正の値をとり
得る符号付きデイジツト表現数をリコードするこ
とが可能となり、例えば、乗算における部分積の
個数を半数程度にできるので、 (1) 演算処理装置の素子数が削減でき、 (2) 演算処理装置の高速化が図れ、 (3) 回路構成を比較的簡単化でき、 (4) 演算処理装置のLSI化が容易かつ経済的にな
る。 等の効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例における乗数リコー
ド回路を構成する基本回路の概略構成図、第２図
は本発明の一実施例を適用した乗算器の構成図、
第３図，第４図はリコードの際の中間桁上げの決
定規則を示す図、第５図，第６図はリコードの際
の中間結果の決定規則を示す図、第７図は冗長加
算器を構成する加算用セルを示す概略回路図であ
る。 １……中間桁上げ生成部、……中間結果生成
部、３……リコード乗数生成部、１００……乗数
リコード回路、１１０……部分積生成器、１２０
……冗長加算器、１３０……冗長２進・２進変換
器。

Claims (1)

1. 【特許請求の範囲】 １ 演算数を２桁ずつのグループに分割し、符号
   付デイジツト数にリコードするリコード手段を備
   え、 前記リコード手段が、前記各グループ毎に、 (a) 前記各グループの２桁と１つ下位のグループ
   の上位桁との３桁から、該グループにおける中
   間桁上げ桁を求める中間桁上げ生成手段と、 (b) 前記３桁から、該グループにおける中間結果
   桁を求める中間結果生成手段と、 (c) 該グループの前記中間結果桁と１つ下位のグ
   ループからの前記中間桁上げ桁とから、該グル
   ープにおけるリコードされた演算数の桁を求め
   るリコード数生成手段とを有することを特徴と
   する演算処理装置。 ２ 乗数を２桁ずつのグループに分割し、符号付
   デイジツト数にリコードする乗数リコード手段
   と、 前記リコードされた乗数と被乗数とから符号付
   デイジツト表現の部分積を生成する部分積生成手
   段と、 前記部分積を加算して符号付デイジツト表現の
   積を求める加算手段とを備え、 前記乗数リコード手段が、前記各グループ毎
   に、 (a) 前記各グループの２桁と１つ下位のグループ
   の上位桁との３桁から、該グループにおける中
   間桁上げ桁を求める中間桁上げ生成手段と、 (b) 前記３桁から、該グループにおける中間結果
   桁を求める中間結果生成手段と、 (c) 該グループの前記中間結果桁と１つ下位のグ
   ループからの前記中間桁上げ桁とから、該グル
   ープにおけるリコードされた乗数の桁を求める
   リコード数生成手段とを有することを特徴とす
   る演算処理装置。 ３ 乗数を２桁ずつのグループに分割し、符号付
   デイジツト数にリコードする乗数リコード手段
   と、 前記リコードされた乗数と被乗数とから符号付
   デイジツト表現の部分積を生成する部分積生成手
   段と、 前記部分積を加算して符号付デイジツト表現の
   積を求める加算手段と、 前記符号付デイジツト表現の積を２進数に変換
   する２進変換手段とを備え、 前記乗数リコード手段が、前記各グループ毎
   に、 (a) 前記各グループの２桁と１つ下位のグループ
   の上位桁との３桁から、該グループにおける中
   間桁上げ桁を求める中間桁上げ生成手段と、 (b) 前記３桁から、該グループにおける中間結果
   桁を求める中間結果生成手段と、 (c) 該グループの前記中間結果桁と１つ下位のグ
   ループからの前記中間桁上げ桁とから、該グル
   ープにおけるリコードされた乗数の桁を求める
   リコード数生成手段とを有することを特徴とす
   る演算処理装置。 ４ 加算手段を符号付デイジツト加算器の加算木
   として構成してなる特許請求の範囲第２項または
   第３項に記載の演算処理装置。 ５ 基数２の符号付デイジツト数を基数４の符号
   付デイジツト数にリコードすることを特徴とする
   特許請求の範囲第１項、第２項、第３項のいずれ
   かに記載の演算処理装置。 ６ 基数２の符号付デイジツト数を基数４の符号
   付デイジツト数にリコードする機能を備えた演算
   処理装置であつて、 中間桁上げ生成手段と中間結果生成手段への入
   力の一つである該グループの１つ下位のグループ
   の上位桁に関する情報が、前記桁が正か負かを表
   す１ビツト信号であることを特徴とする特許請求
   の範囲第１項、第２項、第３項のいずれかに記載
   の演算処理装置。 ７ 演算数を２桁ずつのグループに分割し、符号
   付デイジツト数にリコードする処理が、 (a) 前記各グループの２桁と１つ下位のグループ
   の上位桁との３桁を含む情報から、中間桁上げ
   生成手段によつて該グループにおける中間桁上
   げ桁を求め、前記情報から、中間結果生成手段
   によつて該グループにおける中間結果桁を求め
   る第１の演算ステツプと、 (b) 該グループの前記中間結果桁と１つ下位のグ
   ループからの前記中間桁上げ桁とから、リコー
   ド数生成手段によつて該グループにおけるリコ
   ードされた演算数の桁を求める第２の演算ステ
   ツプとを有することを特徴とする演算処理方
   法。 ８ 基数２の符号付デイジツト表現である演算数
   を基数４の符号付デイジツト数にリコードするこ
   とを特徴とする特許請求の範囲第７項記載の演算
   処理方法。 ９ 演算数を符号付デイジツト数にリコードする
   処理を含む演算処理方法であつて、 前記符号付デイジツト数の各ｊ番目の桁を、 (a) 前記演算数を前記ｊで識別できる２桁ずつの
   グループに分割し、 (b) 前記各ｊに対してｊ番目のグループの２桁と
   ｊ−１番目のグループの上位桁との３桁を中間
   桁上げ生成手段に供給し、前記中間桁上げ生成
   手段でそれらからｊ番目の中間桁上げ桁を決定
   し、 (c) 前記各ｊに対して前記３桁を中間結果生成手
   段に供給し、前記中間結果生成手段でそれらか
   らｊ番目の中間結果桁を決定し、 (d) 前記各ｊに対して前記符号付デイジツト数の
   ｊ番目の中間結果桁とｊ−１番目の中間桁上げ
   桁をリコード数生成手段に供給し、前記リコー
   ド数生成手段でそれらの和から符号付デイジツ
   ト数にリコードされた演算数のｊ番目の桁を決
   定することを特徴とする演算処理方法。 １０ 演算数を基数４の符号付デイジツト数にリ
   コードする処理を含む演算処理方法であつて、 中間桁上げ桁が基数２の符号付デイジツトで表
   現でき、 中間結果桁が基数４の符号付デイジツトで表現
   できることを特徴とする特許請求の範囲第７項ま
   たは第９項記載の演算処理方法。