JPS6238938A

JPS6238938A - Ｒｏｍ形乗算器

Info

Publication number: JPS6238938A
Application number: JP60179007A
Authority: JP
Inventors: Kazuhiro Chiba; 千葉　和弘; Noriko Kojima; 小島　典子
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1985-08-14
Filing date: 1985-08-14
Publication date: 1987-02-19

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕この発明は、ＲＯＭ’ｉ使用して乗算器を実現するＲＯ
Ｍ形乗形容算器り、中でもＲＯＭｇ量を大幅に削減した
ＲＯＭ形乗形容算器するものである。

〔従来の技術〕

第４図は最も単純なＲＯＭ形乗形容算器す図である。図
において、２連符号の被乗数Ｘと乗数ＹとがＲＯＭ　（
’１ｏｏ）のアドレス端子に接続され、アドレ　　　゛
ス値に対応する積Ｐが所定のアクセス時間後に出力端子
から得られる。すなわち、ｐ＝ｘ−ｙの積結果がＲＯＭ
　（１１ｏｏ）にデータとして収納されており、被乗数
Ｘと乗数ＹとはＲＯＭのアドレス信号として入力する構
成となっている。

例えば、Ｘ＝２３３＝ゝゝ１１１０１００１”とＹ＝１
９１：＝０１０１１１１１１”との積Ｐを得る場合、Ｙ
を下位アドレスとしｘ全上位アドレスとした合成アドレ
ス＝″１１１０１００１１０１１１１１１“をＲＯＭの
アドレス端子（１６本）に入力する。このとき、ＲＯＭ
にはあらかじめｐ＝ｘ−ｙのすべての乗算結果を１６ビ
ツトで収納してあれば、積Ｐ＝Ｘ−Ｙ＝’ゝ１０１０１
１０１１１０１０１１１″を得ることができる。

これがＲＯＭ形乗形容算器作概要である。

ところで、波乗＆Ｘ及び乗数Ｙが８ビツト（０≦Ｘ≦２
５５．　Ｏ≦Ｙ≦２５５）のとき、出力データは１６ビ
ツトになシ、アドレス数は２１１　×２８　＝＝　２ｔ
６となる。従つで、総ＲＯＭ容量Ｔ、は、Ｔ、　＝　１
６　Ｘ２′６＝１０４８５’７６ビツトとなる。これは
１Ｍビットであり、ＲＯＭ容量としては大きな数値であ
る。次に、Ｘ及びＹが１６ビツトのときのＲＯＭ容量容
量上求めれば、Ｔｂ−３２ビツトＸ２　　Ｘ２　　＝２
　　となる。この数値は実現不可能である。

〔発明が解決しようとする問題点〕

従来のＲＯＭ形乗算器は以上のように構成されているの
で、直観的で使用しやすい回路でありながら、そのＲＯ
Ｍ容量が膨大であるので、実現できないか、もしくは実
現できても実用的でない問題点があった。

この発明は上記のような問題点を解消するためになされ
たもので、ＲＯＭ容量を大幅に削減した実用的なＲＯＭ
形乗算器を得ることを目的とする。

〔問題点を解決するための手段〕

この発明に係るＲＯＭ形乗算器では、被乗数Ｘ及び乗数
Ｙの少なくとも一方の数値を複数個の部分数値に分割し
、Ｘの各部分数値とＹの各部分数値とのすべての組み合
わせによる部分積をそれぞれＲＯＭで求め、これらの部
分積を加算器で合成加算して、積Ｐ＝Ｘ−Ｙｉ求めるよ
うにしたものでおる。

〔作用〕

この発明では被乗数Ｘ及び乗数Ｙの数値をそれぞれ部分
数値に分割し、これらを用いて部分積をＲＯＭで求める
ようにしたので、ＲＯＭに要求されるビット容量は大幅
に減少する。

〔実施例〕

第１図はこの発明の一実施例を示すブロック構成図で、
被乗数Ｘ及び乗数Ｙがともに８ビツトの場合でＸ　”　Ｘ　７　・２　”Ｘａ　・２　＋Ｘ　ｓ　・２
　＋Ｘ　４　・２　’　＋Ｘｓ　・２””）［２・２２
”）ＣＩ’　”　＋Ｘ６＝（ｘ　７１２”＋ｘａ　・２
”＋ｘ６　・２＋Ｘ４）　・２’”（ｘａ　・２３＋Ｘ
２　・２”＋ｘ　１・２＋ＸＱ）＝Ｘ　−２’＋Ｘ　　
の形で表わし、同様にＱ　　　　　　　　ＬＹ−ＹＵ”’　＋ＹＬ　　−ｃ表りす。

そして、積ｐ＝ｘ−ｙはＰ＝Ｘ−Ｙ＝ＸＵ４．・２８＋ＸｔＩ＋ＹＬ−２’＋Ｘ
Ｌ−Ｙ、＋２’＋ＸＬ−ＹＬとなＱ１４つの部分積Ｘ［
１”［１，ＸＣ１”Ｌ＃ＸＬ”’ＩＩ及びＸｌ・Ｙを求
めてそれぞれ所要の桁上げをして加算すればよい。

第１図において、第１のＲＯＭ（以下［ＲＯＭ　ＩＪと
いう。）　（１０１）〜第４のＲＯＭ（ＲＯＭ４）（１
０４）はそれぞれ部分積Ｘ、・Ｙワ、ＸＩＩ−ＹＬ、Ｘ
Ｌ−ＹＵ、ｘ、・ＹＬのデータを収納したＲＯＭであり
、それぞれのＲＯＭアドレス端子には４ビツトのＸＬＩ
、ｘＬ、ＹＵ、ＹＬが図のように合成アドレスとして結
線されている。ＲＯＭ１個当シのアドレス数は２−２５
６であり、部分積出力データはそれぞれ８ビツトである
。これらの部分積出力ブータラｘ。−ＹＵのデータは８
ビツトの桁上げを実行し、Ｘ、・ＹＬ及びＸＬ−ＹＵは
４ビツトの桁上げを実行してｘＬ　’　ＹＬと全加算器
（ｌｉ’ＵＩ、Ｌ　ＡＤＤＥＲ）（１０５）で加算を実
行すれば積Ｐが得られる。

この場合のＲＯＭ容量容量上、４個合計で、’Ｉ’　＝
２’Ｘ２’Ｘ（８ビツト）×４Ｃ個）＝８１９２ピット
となる。これは従来比で、１／（１２Ｂ）の数値であり
、大幅なＲＯＭ容量の削減が達成できる。

次に実際の数値で検証する。

Ｘ＝２３３．　Ｙ−１９１の乗算を仮定すれば、ＸＵ＝
　８（１）＋　４（１）＋　２（１）＋　１　（０）　
＝　１４ＸＬ＝８（１）＋４（０）＋２（０）＋４（１
）＝９ｙＯ＝　８（１）＋　４（ｏ）＋　２（１）＋　
Ｕｔ）＝　１１ＹＬ＝　８（１）　＋４（１）＋　２（
１）＋　１（１）二１５こむで、（１）＝ゝゝＨ″＝ゝ
ゝ３−１／（ｏ）＝１１１／／　にＩｔ□　ｌ／となり、ＸＵ−ＹＵ＝１４Ｘ１１＝１５４　、　ＸＵ−
ＹＬ＝１４Ｘ１５＝２．１０　、Ｘ　−Ｙ　　＝９Ｘ１
１＝９９　、ＸＬ−ＹＬ＝９Ｘ１５＝１３５　　　　　
　・ＵがＲＯＭの出力データとして８ビツトで得られる。

とｔＬら０２進符号’ｉｌｉ’ＵＬ、Ｌ　ＡＤＤＥＲ（
ｌＩ１９テ、／Ｊｌ算スレば、積Ｐが得られる。この課
程を次に示す。

ＸｔＩ−ＹＯ＝　　　　１００１１０１０←８ビツトシ
フト−Ｘ　−Ｙ　　：　　　　　１１０１００１０←２
２．−Ｘ　Ｌ−ＹｔＩ　＝　　　　　　　　　　　　　
　０１１００　０１　１＋−、、ト−ＸＬ−ＹＬ＝＋）
　　　　　　　１００００１１１Ｐ　　　　＝　　　　
１０１０１１０１１１０１０１１１積Ｐの２連符号はＰ　＝　２”　（１）　＋　２　”＠＋　２１３（１）
　＋　２１２（０）　＋　２　”（１）＋２”（１）＋
２’（０）　＋　２８（１）＋　２７（１）＋　２６（
１）＋　２５（ｏ）＋　２’（１）−１−ｚ３（ｏ）＋
　２”（１）＋　２’（１）＋２°（１）となる。これ
は１０進表示でＰ＝４４５０３となシ、Ｐ＝Ｘ−Ｙ＝２
３３Ｘ１９１＝４４５０３と一致する。従って、本発明
のアルゴリズムは成立する。第１図の回路は、同一のＲ
ＯＭ’ｉ４個並列に使用する構成となっているが、ＲＯ
Ｍ’ｉ１個だけ使用し４回のアクセフ、ｆ実行して順次
にｘＵ−ｙＵ、　ｘ、、ｙＬ、　ｘＬ−ｙｆｆ、　ｘＬ
−ｘ。

を求める方式でもＲＯＭ形乗算器が実現できる。第２図
にこの方式によるこの発明の他の実施例を示す。図にお
いて、（１０６）はｘＩＩ・ＹＵｊ　ｘ［１”ＬＩ　Ｘ
Ｌ”ＩＴＩＸＬ−ｘＬの合成アドレスを生成するセレク
ター、（１０７）はＲＯＭ出力データを一時記憶するＤ
ＦＥ’、　　（１０８）はセレクター（１０６）とＤＦ
Ｆ（１０７）とを同期させて順次に４回のＲＯＭアクセ
スを実行させる制御回路である。その動作は、まずれ・
ＹＬの合成アドレス信号がセレクター（１Ｏａ　）の出
力に選択され、このアドレス値に対応したデータが所定
のアクセス時間後にＲＯＭ　ｌ　（ｌｏｌ）から出力さ
れ、この出力データをＤ　Ｆ　Ｆ　（１０’７）のＤ］
ｉ’ｌｉ’ｌに記憶させる。

同様にしてｘＬ”Ｕの値’１ＤＦＦ２に、ｘＵ　’　Ｙ
Ｌの値をＤＦ１ｉ’３に記憶させ、最後にｘＵ・ＹＵの
値を得る。これらのデータをＦＵＬＬ　ＡＤＤＥＲ（１
０５）に入力して合成式に従って加算すれは、求める値
が得られる〇の容量で乗算器が実現できる。このとき、
同一のＲＯＭ１４回アクセスするため、積Ｐ’ｉｌＨ得
るまでの時間は第１図のそれの約４倍だけ必要となる。

今まで、８×８ビット乗算器について説明してきたが、
次に、ｎＸｎビットをそれぞれＮとＭとで分割して部分
積の生成を行い、部分積の合成加算で積Ｐを求める場合
の理論的なＲＯＭ容量について説明する。第３図に分割
の様子を示す。波乗′＃、ＸをＮ分割、乗数Ｙ′ｆ：Ｍ
分割すると仮定する。このときの］分割アドレス空間は
２１　Ｘ　２Ｍのアドレス数で構成され、１アドレス当
シのデータービット数は（−＋−）となる。１分割アド
レス空間のＨ−Ｍ倍Ｍが全空間になるので、必要ＲＯＭ容量Ｔ、は、Ｔ、＝（
２ｉｒｘａＭ）ｘ（−＋−）Ｘ（Ｎ−Ｍ）Ｍとなる。この式に、ｎ＝８．Ｎ＝Ｍ＝２ｆ代入すれは、
Ｔ、＝（２Ｘ２　　）Ｘ（４＋４）Ｘ（４）＝２　　＝
８１９２ビットとなシ、第１図の実施例の説明中の数値
と一致する。

ここで、ｎ＝４６．Ｎ＝Ｍ＝４の条件では、Ｔ、＝（２
Ｘ２　）Ｘ（４＋４）Ｘ１６＝３２７６８ビツトになる
。従って、３２．’７６８キロビットのＲＯＭ容量で１
６Ｘ１６ビツトのＲＯＭ形乗算器が実現できることにな
る。もちろん、２７１１２図に示した回路構成を１６ビ
ツト対応に拡張させれば、２ｋ　ｂｉｔのＲＯＭ容量で
実現できるが、乗算速度が遅くなる欠点をもつ。

以上に説明したように、ｎＸｎビット乗算器を、　　　
　ＲＯＭで実現することができるが、ＲＯＭ容量を増大
させればランダム・ロジック回路を削減できると共に高
速乗算速度を得ることができる。一方、ＲＯＭ容量を減
少させればランダムのロジック回路が増加し乗算速度が
遅くなる特性をもつ。従って、使用目的に応じてＲＯＭ
容量を決定する必要がある。

なお、上記実施例ではアドレス数を４ピット単位で分割
しているが、目的、使用デバイスの特性および回路規模
、乗算速度などを考慮して任意に分割すればよい。

また、第２図の変形としてＤＩ”Ｆ（１０′７）とＦＵ
ＬＬ（９）　　　　　　　　　　　　　、、１ＡＤＤＥ
Ｒ（１０５）とを累積加算器に置換してもよい。

最後に、ｎＸｎビット乗算器に限らず、一般的なα×β
ビット乗算器も本発明の主旨ｅａ用して同様に実現でき
る。

〔発明の効果〕

以上のように、この発明によれば被乗数Ｘおよび乗数Ｙ
の少なくとも一方を複数の数値の和に分解し、分解した
複数の数値の組合せの数だけＲＯＭを用いて部分積を求
め、最後に複数の部分積の合成加算を実行して積ｐ＝ｘ
−ｙを得る構成としたので、ＲＯＭ容量の大幅な削減が
達成でき、実用的な’ＲＯＭＲＯＭ乗算器れる効果があ
る。

【図面の簡単な説明】

第１図はこの発明の一実施例になるＲＯＭ形乗算器を示
すブロック構成図、第２図はこの発明の他の実施例を示
すブロック構成図、第３図はこの発明における部分積へ
の分割の一形態を示す図、第４図は従来のＲＯＭ乗算器
を示すブロック図でおる。図において、（１０１）〜（１０５）はＲＯＭ、　（１
０５）は、、　　　　　　　　　　　　（１０加算器である。なお、図中同一符号は同一または相当部分を示す。

Claims

【特許請求の範囲】

（１）被乗数及び乗数の少なくとも一方の数値を複数の
部分数値の和の形に分解し、上記被乗数の各部分数値と
上記乗数の各部分数値とのすべての組合わせで得られる
データをアドレス信号としてＲＯＭに入力し、あらかじ
め各アドレスデータに対応して収納されている上記アド
レス入力信号たる両部分数値の積を部分積として当該Ｒ
ＯＭの出力データとして求め、これらの部分積を合成加
算して上記被乗数及び乗数の積を求めるようにしたこと
を特徴とするＲＯＭ形乗算器。