JPS6284336A

JPS6284336A - モジユロ３剰余発生器

Info

Publication number: JPS6284336A
Application number: JP22525185A
Authority: JP
Inventors: Masayuki Tanaka; 昌幸田中
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1985-10-08
Filing date: 1985-10-08
Publication date: 1987-04-17

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は情報処理装置におけるモジュロ３剰余発生器に
関し、特に与えられた２進データに対するモジュロ３剰
余を発生するモジュロ３剰余発生器に関する。

〔従来の技術〕

従来、この種のモジュロ３剰余発生器としては、メモリ
を用い、あらかじめ各メモリアドレスに既アドレスのモ
ジュロ３剰余を記憶させておき、データを既メモリのア
ドレスに入力することにより所望のモジュロ３剰余を得
るものや、特公昭５４−７５９５８号公報に開示されて
いるように、データビット列を重みが２の偶数束のビッ
トと２の奇数束のビットとのいくつかの対に分割し、そ
れぞれのモジュロ３剰余を発生させた後にさらにそれら
を加え合わせたときの値のモジュロ３剰余を発生するも
のなどがあった。

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

上述した従来のモジュロ３剰余発生器は、メモリを用い
るものについては対象とするデータのビット数が増すに
つれて必要とするメモリ容量が指数関数的に増加するの
で、データのビット数が大である場合には実用性をはる
かに逸したものになるという欠点がある。

また、特公昭５４−７５９５８号公報に開示されている
もののように、論理回路を用いるものについては、供給
されるデータのビット重みが２の偶数束のものと２の奇
数束のものとが混在していることが前提となっており、
近年顕著になりつつある論理回路のＬＳＩ化等で、例え
ば２の偶数束もくしは奇数束の重みのビットのみを扱う
ようなＬＳＩ化を試みる場合などは、モジュロ３剰余の
発生がＬＳＩ内部でできず、必ずしも論理回路の自由な
ＬＳＩ化を常に提供できるとは限らないという欠点があ
る。

本発明の目的は、上述の点に鑑み、実用的でかつ論理回
路の自由なＬＳＩ化を保証するモジュロ３剰余発生器を
提供することにある。

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

本発明のモジュロ３剰余発生器は、２進データのモジュ
ロ３剰余を出力するモジュロ３剰余発生器において、入
力ラインＸ１０＋　　Ｘ＋＋＋　　Ｘ＋ｚおよび出力ラ
インｙ、、、Ｙ＋＋＋　Ｙ＋ｔ＋　Ｙｅｓを有し、前記
入力ラインＸ１０＋　　Ｘｚ＋　Ｘ＋ｚより入力される
２進データｘ１゜＋　　”ｌｌ＋　　ｘ、工に対し３’
＋ａ−３Ｅ１００Ｘ＋＋°に自ｚ＋Ｘ１０°３Ｅ＋＋・
ｘＩＩ”Ｘ１６　　’　　”　ＩＩ　　’　　Ｘ　Ｉ！
１５’　Ｉ１１＋）’＋＋−Ｗｈｏ　’　Ｗ＋＋　・ｘＢ＋　５Ｅ、ｏ　
ＨＸ＋ｔ　・Ｘ＋ｚ＋ｘ　ＩＩ　　’　　ｘＩＩ　　’
　　Ｘ　＋！＋Ｙ　＋＋をそれぞれ前記出力ラインＹ　Ｉｏ　ｒ　Ｙ　＋＋　＊
　Ｙ　＋　ｔ　＋Ｙ１３より出力する１個以上のモジュ
ロ３剰余発生手段と、入力ラインＸ２゜ｒ　　Ｘｔｈｒ
　　Ｘｔｈｒ　　Ｘｔｓ＋Ｘ業４＋　Ｘ□＋　　Ｘｔｈ
ｒ　　Ｘｚｙおよび出力ラインＹ２゜。

ｙ、、Ｙｚｘ＋　Ｙ！３を有し、前記入力ラインＸ２゜
。

Ｘｔｈｒ　　Ｘｔｈｒ　　Ｘｔｈｒ　　Ｘｔｈｒ　　Ｘ
ｔｈｒ　　Ｘ！４１　　Ｘｔ？より入力されるモジュロ
３データｘ工Ｉｎ　　Ｘ□、ｘｏ。

Ｘ　茸３＋　　ｘ寡４１Ｘ　！５ｌ）Ｃｔｈ＋　　Ｘ　
ｔ’ｌに対し）’ｔｏ”　　Ｘｔｚ　　’　　Ｘｔｈｒ
　　Ｘ　寡ａ　　０　Ｘｔｓ　　゛　ＸｔｈｒＸ　寞１
　　’　　Ｘ　！３　　’　　ｘ＊４＋７　！？Ｙ＊Ｉ−）Ｃｕｅ　’　Ｘｔｈｒ　Ｘｚ＋　’　Ｘｚｓ
　’　ｘｉ、＋Ｘ　１１　　’　　Ｘ　２Ｓ　’　　ｘ
！？＋ｙｇ＋をそれぞれ前記出力ラインＹ７゜ｒ　Ｙｚ＋＋　　Ｙｔ
ｉ＋Ｙｔ３より出力する１個以上のモジュロ３加算手段
と、前記２進データｘ１゜＋　　ｘｌｌ＋　　ｘ、□を
前記１個以上のモジュロ３剰余発生手段の入力ラインＸ
１゜。

Ｘｌｌ＋　Ｘ１１に入力する第１の接続手段と、前記１
個以上のモジュロ３剰余発生手段の出力ラインＹｌｉ　
Ｙ＋＋＋　Ｙ、、、ＹＩ３からの出力される前記モジュ
ロ３データＸｔｌｌ＋　　Ｘ！Ｉ＋　　Ｘｔｚ、Ｘ！！
＋　　ｘ１４＋ｘ２Ｓ＋　　ｘＺ＆＋　　ｘｌ？を前記
１個以上のモジュロ３加算手段の入力ラインＸ　ＺＯ＋
　　Ｘ　ＺＩ＋　　Ｘ　ｚｚ、　　Ｘ　ｚ＊＋Ｘ　２４
１　　Ｘ　ｉｓ、　　Ｘ　ｆｆ１６＋　　Ｘ　ｔｔに入
力するための第２の接続手段とを有する。

〔実施例〕

次に、本発明について図面を参照して説明する。

第１図は本発明の一実施例を示すモジュロ３剰余発生器
のブロック図である０本実施例のモジュロ３剰余発生器
は、１２ビツトの符号なし２進数のモジュロ３剰余を発
生させるものである。２進数１１０は１２ビツトの符号
なし２進整数を表しており、重み２°〜２目までの各ビ
ットのデータが信号線１１１〜１２２にそれぞれ入力さ
れるものとする。

Ａモジュール１３０．１４０．１５０および１６０は、
２の偶数乗の重みのビットまたは２の奇数束の重みのビ
ットのデータｘ１゜＋　　ｘＩＩ＋　　Ｘ１ｇを入力ラ
インＸｌＯ＋　Ｘ＋＋＋　Ｘ＋ｘに入力すると、全入力
データを加え合わせた値のモジュロ３剰余Ｙ１０＝Ｍ１０’　！＋＋　’　ｘｌｔ＋ｘ１６’　５
ＥＩＩ　’　ｘ、ｔ＋ｘ＋ｅ　’　Ｘ目’　ＸＩ！＋ｙ＋＋”Ｘ１０・　５Ｅｚ　’　　Ｘ＋ｚ＋Ｘ＋＋’　
　Ｘ＋＋　’　　Ｍａｔ＋ＸＩｅ’ＸＩＩ’ｘＩコニ９を出力ラインＹ１０、ＹＢにそれぞれ重み１２、Ｙ１３
２で出力し、また、出力ラインＹｌｌ＋　　Ｙ１２には
それぞれ出力ラインＹ１゜、Ｙ、２の論理否定ｙ１゜。

を出力する。

Ｂモジュール１７０，１８０および１９０は、入力ライ
ンＸ２゜、Ｘ、およびＸ　、、、　　Ｘ　ｔ＆よりそれ
ぞれ重み２．１のモジュロ３データｘｔａｒ　　ｘ！ｌ
＋　　Ｘア１０ｘ！ｔｈを受け、入力ラインＸｚ＋＋　
　Ｘｔｓ＋　　Ｘｔｓ＋　　Ｘｔｑにはそれぞれ入力ラ
インＸ　ｆｆ１Ｏ＋　　Ｘ　ｚｔ、　　Ｘ　ｔａｒ　Ｘ
　ｚｂの論理否定Ｘ□＋　　Ｘ！！＋　　Ｘ！Ｓｒ　　
ｘｔ’Ｊを入力することにより、入力された２つのモジ
ュロ３データのモジュロ３加算結果 ”！ｔｏ−Ｘｚｏ　’　　Ｘｔｂ＋　　Ｘｚｏ　　’　
　Ｘｚｓ　　’　　ｘ　意？＋Ｘ　２Ｉ　’　　ｘ１２
　　’　　ｘ！４＋７ｇ＋−Ｘｚｏ’　Ｘｔａ＋Ｘｚ＋
’　Ｘｘ３°ｘｚｈ＋”　ＩＲ’　　Ｘ　＠Ｓ　　’　
　ｘ１？＋をそれぞれ重み２．１で出力ラインＹｚｏ、
　　Ｙｚｚニ出力する。また、出力ラインＹ、、、Ｙ、
、には出力ラインＹ２゜、Ｙｔｔの論理否定ｙ２゜。

Ｖｚ＋を出力するものである。

Ａモジュールは、例えば第２図に示すように、また、Ｂ
モジュールは例えば第３図に示すように容易に構成可能
である。

次に、このように構成された本実施例のモジュロ３剰余
発生器の動作について説明する。ここでは、２進数１１
０が°１０１１０１１０１１１０’である場合について
考える。まず、２進数１１０の各ビットが信号線１１１
〜１２２を介してＡモジュール１３０．１４０．１５０
および１６０に入力されると、Ａモジュール１６０は２
進数“１０１０００００００００’　のモジュロ３剰余
である°０１゛を出力ラインＹ１□、Ｙ＋。に出力し、
同時に出力ラインＹ　ｌ！、　　Ｙ　＋　Ｉにその論理
否定を出力する。

また、同様にＡモジュール１４０も２進数’ｏｏｏｏ。

０１０１０１０”のモジュロ３剰余゛００°およびその
論理否定を出力ラインＹ１０〜ＹＩｆｆに出力する。

さらに、Ａモジュール１５０は、２進数’０００１０１
０ｏｏｏｏｏ°のモジュロ３剰余である１０゛を出力ラ
インＹ１゜、Ｙ、、に出力し、同時に出力ラインＹ１０
Ｙｌ３にその論理否定を出力する。

同様に、Ａモジュール１３０も、２進数’ｏｏｏｏｏｏ
。

００１００’のモジュロ３剰余゛０１°およびその論理
否定をＹｌ。〜Ｙｌｆｆに出力する。

次に、Ｂモジュール１８０は、信号線１６１〜１６４を
介してモジュロ３データおよびその論理否定データであ
る°０１１０°を、信号線１５１〜１５４を介してモジ
ュロ３デークおよびその論理否定データである１００１
”をそれぞれ受け、２つのモジュロ３デーク゛０１°、
°１０°のモジェロ加算結果である“００゛を出力ライ
ンＹ１０、Ｙｅｔに出力し、出力ラインＹ２．。

Ｙｏにはその論理否定である“１１゛を出力する。

同様に、Ｂモジュール１７０も信号線１４１〜１４４お
よび信号ｖＡ１３１〜１３４を介して２つのモジュロ３
データおよびその論理否定”０１０１’　、　’０１１
０’　を受け、モジュロ３データ゛００°、“０１’　
のモジュロ加算結果である°０１゛を出力ラインＹ２゜
、ＹＨに出力し、出力ラインＹ、、、Ｙ、ｆｆにはその
論理否定である“１０゛を出力する。

最後に、Ｂモジュール１９０は、信号線１８１〜１８４
、１７１〜１７４を介してＢモジュール１８０および１
７０より２つのモジュロ３データおよびその論理否定’
０１０１″、　’０１１０”を受け、モジュロ３デーダ
００°、　’０１’　のモジュロ３加算結果゛０１゛を
２進数°１０１０１０１１０００１°のモジュロ３剰余
として出力ラインＹ１□、Ｙｌｏに出力し、信号線１９
１２、Ｙ１３１９２より所望の値として得ることができ
る。

次に、本実施例のモジュロ３剰余発生器を、指数の基数
が１６で仮数がビット＃Ｏ〜３１（＃はビット位置を示
す。以下同様）の浮動小数点データの加算を行うイコラ
イズシフタ付の加算器をいくつかのＬＳＩに分割して構
成した場合についての誤り検査回路に応用した例を第４
図に示す。

Ｌ　Ｓ　Ｉ　Ａ　４１０，４２０，４３０および４４０
は、全体で４ピント単位の算術右シフトの機能を有する
イコライズシフタを構成するためのもので、信号線４１
１にはビット＃０．４．８．　　・・・、２８、信号線
４２１にはビット＃ｌ　　５，９．　　・・・、２９、
信号線４３１にはビット＃２．　６．１０．　　・・・
、３０、信号線４４１にはビット＃３．　７．１１２、
Ｙ１３　　・・・、３１の各仮数ビットが入力され、信
号線４０５よりビット＃Ｏと同一の真理値を持つ信号が
符号として入力され、信号線４０６より入力されるシフ
トカウントに従い、信号線４１４，４２４，４３４，４
４４にシフト後のデータを出力するものである。

ＬＳＩＢ４６０は、予測される加算結果のモジュロ３剰
余と加算結果より発生したモジュロ３剰余とを比較し、
誤りを検出するものである。

Ｌ　Ｓ　Ｉ　Ｃ４５０は、被加算データとイコライズシ
フタより出力される加算データとを加算し、その結果お
よび結果のモジュロ３刹余を発生するためのものである
。

シフタ５００は、信号線４０６より入力されるシフトカ
ウントに従い１ビット単位の算術右シフトを行うもので
ある。

Ｃモジュール６００は、シフタ５００が動作することに
よりＬＳＩ側よりシフトアウトされるデータを全て重み
が２の偶数乗のデータとした場合のモジュロ３剰余を発
生させ、それぞれ信号線４１２゜４１３と信号線４２２
，４２３と信号線４３２，４３３と信号線４２２、４４
３とに３の補数の形で出力するものである。

加算器４５５は、信号線４５１より被加算データを受け
、信号線４１４，４２４，４３４，４４４より加算デー
タを受けて加算を行い、結果を信号線４５２に出力する
ものである。

Ｄモジュール４５６は、信号線４５２より加算結果を受
け、信号線４５３にそのモジュロ３剰余を出力するもの
である。

モジュロ３加算器４６５は、信号線４０１，４０２より
信号線４５１に入力される被加算データのモジュロ３剰
余を入力し、信号線４０３．４０４より信号４１１゜４
２１２、Ｙ１３４３１，４４１を介しイコライズシフタ
に入力される加算データのモジュロ３剰余を入力し、信
号線４１２．４１３と信号線４２２，４２３と信号線４
３２．４３３と信号線４４２，４４３よりイコライズシ
フタによりＬＳＩＢ４６０からシフトアウトされるデー
タのモジュロ３剰余の３の補数を入力し、全てをモジュ
ロ３加算することにより加算器４５５の加算結果のモジ
ュロ３剰余を予測し結果を信号線４６１に出力するもの
である。

比較器４６６は、信号線４５３から加算結果のモジュロ
３剰余を受け、信号線４６１より予測される加算結果の
モジュロ３剰余を受け、両者を比較し一致していなけれ
ば誤りが生じたことを信号線４６２に出力するものであ
る。

〔発明の効果〕

以上説明したように本発明は、モジュロ３剰余を発生さ
せる際、２つの偶数乗の重みのビットおよび２つの全数
乗の重みのビットの存在する比率等に全く影響を受けず
、また、小規模かつ単純な回路の繰返しによりいかなる
多数桁の２進数のモジュロ３剰余も求めることが可能で
あるため、近年顕著になりつつある論理回路のＬＳＩ化
等でより自由な構成を保証し得るという効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例のモジュロ３剰余発土器のブ
ロック図、第２図は第１図中に示したＡモジエールの一例を示す回
路図、第３図は第１図中に示したＢモジュールの一例を示す回
路図、第４図は本発明のモジュロ３剰余発生器を誤り検査回路
に応用した一例を示すブロック図である。図において、１３０、１４０．１５０．１６０　・・・Ａモジュール
、１７０、１８０，１９０　・・・Ｂモジエール、４５
５　　・・・加算器、４５６　　・・・Ｄモジュール、４６５　・・・モジュロ３加算器、４６６　　・・・比較器、５００　　・・・シック、６００　　・・・Ｃモジュールである。第１図第２図第３図第４図

Claims

【特許請求の範囲】２進データのモジュロ３剰余を出力するモジュロ３剰余
発生器において、入力ラインＸ＿１＿０、Ｘ＿１＿１、Ｘ＿１＿２および
出力ラインＹ＿１＿０、Ｙ＿１＿１、Ｙ＿１＿２、Ｙ＿
１＿３を有し、前記入力ラインＸ＿１＿０、Ｘ＿１＿１
、Ｘ＿１＿２より入力される２進データｘ＿１＿０、ｘ
＿１＿１、ｘ＿１＿２に対しｙ＿１＿０＝＠ｘ＠＿１＿０・ｘ＿１＿１・ｘ＿１＿２
＋ｘ＿１＿０・＠ｘ＠＿１＿１・ｘ＿１＿２＋ｘ＿１＿
０・ｘ＿１＿１・＠ｘ＠＿１＿２、＠ｙ＠＿１＿０、ｙ＿１＿１＝＠ｘ＠＿１＿０・＠ｘ＠＿１＿１・ｘ＿１
＿２＋＠ｘ＠＿１＿０・ｘ＿１＿１・＠ｘ＠＿１＿２＋
ｘ＿１＿０・＠ｘ＠＿１＿１・＠ｘ＠＿１＿２、＠ｙ＠
＿１＿１をそれぞれ前記出力ラインＹ＿１＿０、Ｙ＿１＿１、Ｙ
＿１＿２、Ｙ＿１＿３より出力する１個以上のモジュロ
３剰余発生手段と、入力ラインＸ＿２＿０、Ｘ＿２＿１、Ｘ＿２＿２、Ｘ＿
２＿３、Ｘ＿２＿４、Ｘ＿２＿５、Ｘ＿２＿６、Ｘ＿２
＿７および出力ラインＹ＿２＿０、Ｙ＿２＿１、Ｙ＿２
＿２、Ｙ＿２＿３を有し、前記入力ラインＸ＿２＿０、
Ｘ＿２＿１、Ｘ＿２＿２、Ｘ＿２＿３、Ｘ＿２＿４、Ｘ
＿２＿５、Ｘ＿２＿６、Ｘ＿２＿７より入力されるモジ
ュロ３データｘ＿２＿０、ｘ＿２＿１、ｘ＿２＿２、ｘ
＿２＿３、ｘ＿２＿４、ｘ＿２＿５、ｘ＿２＿６、ｘ＿
２＿７に対しｙ＿２＿０＝ｘ＿２＿２・ｘ＿２＿６＋ｘ
＿２＿０・ｘ＿２＿５・ｘ＿２＿７＋ｘ＿２＿１・ｘ＿
２＿３・ｘ＿２＿４、＠ｙ＠＿２＿０、ｙ＿２＿１＝ｘ＿２＿０・ｘ＿２＿４＋ｘ＿２＿１・ｘ
＿２＿３・ｘ＿２＿６＋ｘ＿２＿２・ｘ＿２＿５・ｘ＿
２＿７、＠ｙ＠＿２＿１をそれぞれ前記出力ラインＹ＿２＿０、Ｙ＿２＿１、Ｙ
＿２＿２、Ｙ＿２＿３より出力する１個以上のモジュロ
３加算手段と、前記２進データｘ＿１＿０、ｘ＿１＿１、ｘ＿１＿２を
前記１個以上のモジュロ３剰余発生手段の入力ラインＸ
＿１＿０、Ｘ＿１＿１、Ｘ＿１＿２に入力する第１の接
続手段と、前記１個以上のモジュロ３剰余発生手段の出
力ラインＹ＿１＿０、Ｙ＿１＿１、Ｙ＿１＿２、Ｙ＿１
＿３からの出力される前記モジュロ３データｘ＿２＿０
、ｘ＿２＿１、ｘ＿２＿２、ｘ＿２＿３、ｘ＿２＿４、
ｘ＿２＿５、ｘ＿２＿６、ｘ＿２＿７を前記１個以上の
モジュロ３加算手段の入力ラインＸ＿２＿０、Ｘ＿２＿
１、Ｘ＿２＿２、Ｘ＿２＿３、Ｘ＿２＿４、Ｘ＿２＿５
、Ｘ＿２＿６、Ｘ＿２＿７に入力するための第２の接続
手段と、を有することを特徴とするモジュロ３剰余発生器。