JPS61223946A - モジュロ演算装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 技術的分野 本発明は、一般的にはモジュロ演算に関するものであシ
、更に詳しく云うと任意モジュロおよびオフセット値を
有するモジュロ演算を実施する演算装置（ＡＵ）に関す
る。

発明の概要 複数のモジュロネのうちの選択名れた１つにおける２つ
の任意値数の和又は差を与えるモジュロ演算装置が提供
されている。各モジュラスは上限および下限および中間
値範囲を有する。第１加算器および第２加算器が具えら
れておシ、上限又は下限の可能なラップアラウンドに対
して補償されない、又は補償される出力をそれぞれ与え
る。第１および第２加算器の選択的中開けた上げ信号の
値に応じてラップアラウンドが計算中に起きたかどうか
を検出するために制御回路が用いられている。制御回路
に応答して第１および第２加算器の出力のうちの選択名
れた１つとして正しい出力が与えられる。

背景技術 電子回路におけるデータ計算は一般にモジュロ演算によ
って実施される。抽象的な数学的意味では、１モジュロ
Ｍ”演算は基数Ｍに対する数体系を用いる。但し、その
数体系の各けたは０〜（Ｍ−１）の範囲内の所定値によ
って表わされ、Ｍは整数である。＠（Ｎ）モジュロＭ”
の表現は本質的には基数Ｍに対するＮの１剰余”に等し
い。例えば、表現（１２）モジュロ１０は２に等しい。

（Ｒ±Ｎ）モジ５゜口Ｍの計算は、その各々が０〜（Ｍ
−１）の範囲内にある数ＲおよびＮについて行われるの
で、その結果もまた定められた範囲内の数でなければな
らない。もし範囲の下限値りが零に等しくないならば、
算術計算の結果光られるモジュロ値はもはや厳密な意味
では剰余値に等しくない。その結果は下限値乙によって
０からオフセットされ、モジュロ算術計算は下記に等し
くなる。

（（Ｒ±Ｎ−Ｌ）モジュロＭ）　＋Ｉ。

モジュロ演算は普通はアドレス計算を行うために信号処
理およびデータプロセッサに用いられる。

アドレス計算はデータ記憶手段におけるデータにアクセ
スするために整数値について行われる。データ記憶手段
は線形アドレス指定能力を有する従来のメモリ回路によ
って一般に実施される。線形演算はデータプロセッサに
一般に見出される演算形式であり、一般的には従来の２
の補数２進算術演算によって実施される。しかし、線形
演算は循環バッファ、待ち行列又はＦＩＦＯ（先入れ先
田し方式）のようなメモリにおけるデータ構造を直接に
実施するものではない。これは線形演算はアドレスを定
められた範囲内に維持するために１ラツプアラウンド（
循環）”演算を行う能力を提供しないからである。これ
とは対照的に、モジュロ演算はオーバヘッドなしにラッ
プアラウンド演算を提供することによって従来のメモリ
回路においてこれらの種類のデータ構造を実施する。従
って、これらの有用なデータ構造を作るためにはモジュ
ロアドレス指定を用いることが望ましいことがし１、Ｆ
　　Ｉ　　　ｌ、Ｆ　　Ａ　　’１モジエロアドレス指
定は一般的には線形演算を用いるソフトウェアで実施さ
れる。代表的なマイクロプロセッサはモジュロアドレス
指定を実施するために線形アドレス指定を用いる。循環
バッファ又は待ち行列はオフセット値によってアドレス
ポインタを増分させ、連続する各増分値と第１限界値と
を比較する比較器を用いて一般に実施される。第１限界
値に達すると、ラップアラウンド値を表わす第２限界値
が与えられるので、結果（ｒ＠５ｕｌｔａｎｔ　）は所
定範囲内にと％ｉまっている。この種類のアドレス指定
社また文献上１循環バツフアアドレス指定”、１待ち行
列アドレス指定”および“ＦＩＦＯアドレス指定”とし
ても知られる。

しかし、線形演算を用いるモジュロアドレス指定の実施
は一般にデータアクセスあたシ最低４つのソフトウェア
命令を必要とする。従ってそのようなデータ構造をしば
しばアクセスする場合には大量のオーバヘッドが存在す
る。

発明の要約 従って、本発明の目的は任意のオフセットおよびモジュ
ロ値を有する改良されたモジュロ演算装置（ＡＵ）を提
供することである。

本発明のもう１つの目的は、任意のオフセットおよびそ
ジュロ値を有するそジュロ演算を実施し必要とされる回
路量を最小にする改良された電子回路を提供することで
ある。

本発明の更にもう１つの目的は改良された速度特性を有
するモジュロ演算を行う改良されたモジュロＡＵ″Ｉｋ
提供することである。

本発明のこれらの目的およびその他の目的を達成するた
めに、第１および第２の数の和および差を与えるモジュ
ロＭ演算装置が１つの形で提供されている。第１の数は
Ｍに関連した上限と下限を有する所定範囲内にある数値
を有しなければならない。但し、Ｍは複数の所定モジュ
ラスのうちの選択名れた１つである。第２の数はモジュ
ラスＭよ）小さいか又はＭに等しい絶対値を有しなけれ
ばならない。第１加算器は第１および第２の数を選択的
に受けとり、算術演算制御信号に応答して第２の数を加
算又は減算する。第１加算器はランク付けされた複数の
第１けた上げビットおよびランク付けされた複数の第１
出力ビツトを与え、第１出力ビツトは出力値表現がモジ
ュラスによって定められた値の範囲内にあるかどうかに
は関係なく第１および第２の数の算術和又は差を表わす
。

従って、第１出力ビツトはモジュロラップアラウンドが
起きなかったと想定した場合の結果を表わす。第１モジ
ュロ制御手段は第１加算器に結合され、第１けた上げビ
ットおよび複数のモジュラス制御ビットの両方に応答し
て第１けた上げ制御ビットを与える。選択名れたモジュ
ラスＭのビットは復号されてモジュラス制御ビットを与
える。第２加算器は第１出力ビツトおよびモジュラスＭ
のビットを選択的に受けとり、第２の数の符号および算
術演算制御信号に応答して第１出力ビツトにモジュロビ
ットを加算するか、又は第１出力ビツトからモジュロビ
ットを減算する。第２加算器はランク付けされた複数の
第２けた上げビットおよびランク付けされた複数の第２
出力ビツトを与え、第２出力ビツトはモジュロラップア
ラウンドが起きたと想定して第１および第２の数の算術
和および差を表わす。第２モジュロ制御手段は第２加算
器に結合され、第２けた上げビットおよび複数のそジュ
ラス制御ビットの両方に応答して第２けた上げ制御ビッ
トを与える。多重化された制御手段が第１および第２加
算器および第１および第２モジュロ制御手段結合され、
第１および第２けた上げ制御ビットおよび第２の数の符
号に応答して複数の第１および第２出力ビツトのうちの
１つを選択的に与える。上記の、およびその他の目的、
特徴および利点は、添付の図面とともに下記の詳細な説
明から更に明らかになるものと思われる。

発明の詳細な説明 第１図には数学的計算（Ｒ＋Ｎ）モジュロＭを行うため
の技術上知られているモジュロ演算装置１０が示されて
いる。加算器１１は数Ｒを受けとる丸めの第１人力およ
び数Ｎ？、受けとるための第２人力を有する。加算器１
１の和出力は比較器νの第１人力および出力マルチプレ
クサ回路１３の第１人力の両方に５ＳＪＫれイいスーモ
ジュラスＭの所♀のト限は比較器νの第２人力に結合さ
れ、モジュラスＭの所定の下限は出力マルチプレクサ１
３の第２人力に結合されている。比較器νの出力は出力
マルチプレクサ肋の制御入力に接続されている計マルチ
プレクサ１３の出力は（Ｒ＋Ｎ　）モジュロＭの値に等
しい出被値Ａを与える。

動作すると、数Ｒは入力データ値を表わし、ＮはＲに加
算される更新値を表わすかもしれない。

′″Ｒ″　というラベルが付いている加算器１１の出力
値は、和がモジュラスの所定の上限と交差しなかったら
、又はその上限をラップアラウンドしなかったら和の正
しい値を表わす。従って、ラップアラウンドが起きたか
どうかを決定するために、比較器ｎは和の値と所定の上
限とを比較して上限の交差が起きたかどうかを決定する
。電子ハードウェアの立場からみると、和が許容された
モジュロ範囲内にとりまっていたかどうか、を決定する
回路が必要である。比較器ルが和の値がモジュラスの範
囲外にあると決定すると、出力選択回路信号が与えられ
、出力マルチプレクサ１３にモジュラスの範囲外にある
和の値を出力させるのではなく出力和Ａとして下限値を
代用させる。

そジエロ演算装置１０に伴う短所は、図示されていない
複数の記憶レジスタが上限値および下限値を記憶するの
に必要であるということである。この結果、多数のモジ
ュロ範囲が定められると、大量の追加記憶回路が必要に
なる。更に、装置ｌＯのよシ重大な短所は、装置ｌＯは
１の値だけ増分するよう限定されているということであ
る。換言すると、装置１０の出力傭人を正しいものとす
るためには、オフセラ）Ｎの値を常に１に等しくしなけ
ればならない。Ｎの値に関するこの制限は、比較器νに
よってオーバフローが検出された場合出方マルチプレク
サ１３は単一の値しか代用しないかもしれないという事
実によって起きる。モジュロ演算装置におけるオフセッ
ト又は増加量が１の値に制限されると、モジュロアドレ
ス指定およびその他の応用の柔軟性が著しく制限される
０更に、増分ならびに減分するために、上限値および下
限値が装置１０に結合される位置を切換えるために追加
論理が必要となる。従って、モジュロ演算装置１０は任
意のオフセットおよびモジュロ値を与えることができな
い。

第２図には演算（Ｒ±Ｎ）モジュロＭを行い、任意のオ
フセットおよびモジュロ値をもったモジュロ算術演算を
行うモジュロ演算装置が示されている。ｎビット加算器
回路２１（但しｎは整数）は“Ｒ″というラベルが付い
ている第１人力、′±Ｎ”というラベルが付いている第
２人力　ｔ　Ｓ　＃という２ベルが付いている第１出力
、および＠Ｃ”というラベルが付いている第２出力を有
する。加算器２１の第１出力はマルチプレクサ回路ｎの
第１人力およびｎビット加算器回路器の第１人力の両方
に接続されている。加算器回路器の第２人力はモジュラ
スを表わす１±Ｍ１というラベルが付いている２進数に
接続されている。９１８８というラベルが付いている加
算器回路コの第１出力はマルチプレクサ回路ｎの第２人
力に接続され、加算器回路ｎの第２出力には＠Ｃ”とい
うラベルが付いている。加算器回路２１の第２出力はモ
ジュａ／けた上げ制御回路５　　　　・の第１人力に接
続されている。加算器回路器の第２出力はモジュロ／け
た上げ制御回路部の第１人力に接続されている。モジュ
ラスＭの２進表示はモジュロデコーダ回路Ｉの入力に接
続される。デコーダ回路ＩＯ出力はモジュロ／けた上げ
制御回路部の第２人力およびモジュロ／けた上げ制御回
路部の第２人力の両方に接続されている。＠ＣＢｌ＃と
いうラベルが付いているモジュロ／けた上げ制御回路２
５（７＞出力は制御論理回路３１の第１人力に接続され
ている。“ＣＢＲ″というラベルが付いているモジュロ
／けた上げ制御回路部の出力は制御論理回路３１の第２
人力に接続されている。“増分／減分１というラベルが
付いている増分／減分制御信号は制御論理回路３１の第
３人力に接続され、“正／負”というラベルが付いてい
°る正／負制御信号は制御論理回路３１の第４人力に接
続される。制御論理回路３１の出力はマルチプレクサ回
路ｎの第３人力に接続されている。マルチプレクサ回路
２２の出力はＡ″というラベルが付いている結果を与え
、これは（Ｒ±Ｎ）モジュロＭに等しい。

動作すると、モジュロ演算装置器は値（ｆｌＮ　）モジ
ュロＭを計算する。但し、Ｒ，ＮおよびＭは任意に選択
名れた値であシ、変えることができる。

Ｎの値に関する唯一の制約は、Ｎの絶対値がＭよ〕か小
さいか、又はＭに等しくなければならないということだ
けである。しかし、この制約は実際的問題としては制限
的なものではないことを下記に示す。上述したように、
モジュロＭ演算においては、加算および減算演算は下限
から上限まで変化する値の一定範囲で行われる。モジュ
ラスは上限と下限の差に１を加算したものと定義されて
いる。加算器２１は線形演算における（Ｒ＋Ｎ）または
（Ｒ−Ｎ）の演算値を計算するように機能する。

（Ｒ＋Ｎ）ｔたは（Ｒ−Ｎ）の値が上限又は下限におい
てラップアラウンドを起こさないと想定すると、加算器
２１によって与えられる結果は装置器の適当な出力値で
ある。加算器２３はラップアラウンドが存在することを
想定することによって機能し、更にそジュラスを減算又
は加算することによってそれぞれ（（Ｒ＋Ｎ）　−Ｍ）
又は（（Ｒ−Ｎ）＋Ｍ）の値を計算する。モジュロ演算
装置加の残少の回路は、両方の加算器２１および羽が発
生させた所定の中聞けた上げビットに基づいて境界のラ
ップアラウンドが起きたかどうかを決定しマルチプレク
サ４の第１および第２の計算された入力のうちの正しい
１つを出力するように機能する。

図示された形では、所定のモジュロはモジュロ範囲の下
限の許容しうる値に対して制限を加える。

モジュロ範囲の下限はｋＬｓＢｓにおいてすべて零を有
しなければならず（但しｋは整数）、２にはモジュラス
Ｍよシ大きいか、又はＭＫ尋しくなければならない。従
って、下限はＸｌｋに等しくなければならない（但しＸ
は負でない整数である）。下限が零で危いと、下限の２
　ＬＳＢｓは零に等しく、上限の２ｋＬＳＢｓは（Ｍ−
１）に等しい。ｎビット数の残夛のＭｇＨ２は任意であ
シ、各所定モジュロ値Ｍに対して複数のモジュロ範囲を
与える０下限に２のベキの倍数である値をもたせること
によって、境界がいつ交差されるかの決定は最下位けた
上げビットを復号することによって容易に下すことがで
きる。本発明は２進化１０進数（ＢＣＤ）などのような
非２進演算を用いて実施してもよいということが明らか
になるはずである。非２進演算応用では、上記の２のベ
キの倍数と定義された下限の基数（ｂａｓ・）はそれに
応じて変化する。各下限に対する既知の値を用いると、
各計算値と記憶された下限値との追加の比較は避けられ
る。従って、任意のオフセットおよびモジュロ値による
モジュロ演算は上限値および下限値のための記憶手段を
必要としないで行うことができる。

定められた下限値の結果として、加算器２１および器に
よって与えられた２つの出力のうちの正しい出力Ａの選
択の簡単な１組の原則に従う。数Ｎが正のＮだけ増分し
つつある場合には、加算器２１からの出力（Ｒ＋Ｎ）の
ｋＬＳＢｆｉが正の方向にオーツ（フローせず、加算器
幻からの出力（Ｒ＋Ｎ−Ｍ）のｋ　Ｌ８Ｂｇ　が負の方
向にオーバフローすると上限のラップアラウンドは起き
ない。加算器２１からの出力（Ｒ＋Ｎ　）のｋ　ＬＳＢ
ｇが正の方向にオー／（７ＣＩ−するか、又は加算器幻
からの出力（Ｒ＋Ｎ−Ｍ）　　のｋ　ＬＳＢｇが負の方
向にアンダフローしないと、上限のラップアラウンドが
起きる。この状態の決定は加算器２１および羽のｋ　Ｌ
ＳＢｓのけた上げビットを調べることによって容易に下
すことができる。

数Ｒが負のＮだけ減分されつつある場合にも、同じ原則
が上限のラップアラウンドにも適用する。

同様に、数Ｒが正のＮだけ減分されつつある場合には、
加算器２１からの出力（Ｒ−Ｎ）のｋＬＳＢｇが負の方
向にオーバフローしなければ下限のラップアラウンドは
起きない。加算器２１からの出力（Ｒ−Ｎ）のｋ　ＬＳ
ＢＳが負の方向にオーバフローすると下限のラップアラ
ウンドが起きる。数Ｒが負のＮだけ増分されつつある場
合にも同じ原則が下限のラップアラウンドについて適用
する。下限のラップアラウンドを検出するには加算器の
けた上げ出力（ｅａｒｒｙ−ｏｕｔ　）ビットは不必要
であるという点に注目すべきである。正方向のオーバ７
０−はけた上げ出力ビットの存在によって検出されるか
もしれず、負方向のオーバフローは借シを示すけた上げ
出力ビットの存在しないことによって検出されるかもし
れない。

第３図には本発明の原理を更に示すため第２因のモジュ
ロ演算装置田の特定の４ビツト冥施が示されている。本
発明は第３図の点によって示されているように任意のビ
ットサイズを表わす任意の数の全加算器回路を用いて実
施することができる。

しかし、図解のため代表的な数のモジュロを４つの全加
算器に関連して説明する。加算器回路２１は４つのラン
クづけされた全加算器回路４０　、４１　、４２および
４３を含む。全加算器物は加算器２１の最下位加算器回
路である。増分／減分制御信号ＩＮＣ／ＤＥＣは全加算
器回路４０のけた上げ入力端子および複数の排他的オア
ゲー）　４６　、４７　、４８および４９の各第１人力
に結合される。Ｒ（＋、Ｒ１，Ｒ１およびＲｓというラ
ベルが付いている入力数Ｒの４つの最下位ビットのうち
の所定の１つが全加算器４０　、４１　、４２および４
３の１Ａ１というラベルが付いている第１人力にそれぞ
れ接続される。ピッ）　Ｒｅは入力数Ｒの最下位ビット
である。Ｎｏ　、Ｎｓ　、ＮｇおよびＮｓというラベル
が付いている入力オフセット数の４つのビットのうちの
所定の１つが排他的オアゲー）　４６　、４７　、４８
および４９の第２人力に接続される。ピッ）Ｎｏは入力
数Ｎの最下位ビットである。排他的オアゲー）　４６　
、４７　。

槌および４９の各々の所定の出力は全加算器４０　、４
１　。

４２および招の＠Ｂ”というラベルが付いている第２人
力に接続されている。排他的オアゲート４９の出力はＩ
ＮＣ／　ＤＥＣ制御信号と排他的オア結合している数Ｎ
ｍ　Ｎｍの符号ビットであ６、’ｓ”というラベルが付
けられている。信号Ｓは上限値が近づきつつあるか又は
下限値が近づきつつあるかを示す。

モジュロ／けた上げ制御部分部はアンドゲート５１　、
５２　、５３および９およびオアゲート５６を含む。

′ｃｏｉ　’　　というラベルが付いている全加算器４
００けた上げ出力は全加算器４１０けた上げ入力および
モジュロ制御回路部のアンドゲート５１の第１人力の両
方に接続されている。″Ｃ１ｌ”’　というラベルが付
いている全加算器４１のけた上げ出力は全加算器４２の
けた上げ入力およびアンドゲート♀の第１人力の両方に
接続されている。＠Ｃ２１”というラベ・ルが付いてい
る全加算器稔のけた上げ出力は全加算器４３のけた上げ
入力およびアントゲ−）５３の第１人力の両方に接続さ
れている。＠Ｃ３１’というラベルが付いている全加算
器招のけた上げ出力はアンドゲート窮の第１人力に接続
されている。Ｋｏ。

Ｋｌ、に！およびＫｓというラベルが付いている複数の
符号化制御信号のうちの所定の１つはアントゲ−）　５
１　、５２　、５３およびシの第２人力にそれぞれ接続
される。アントゲ−）　５１　、５２　、５３および詞
の各々は出力をオアゲー）５６の複数の入力のうちの所
定の１つに接続させている。アントゲ−）　５１　、５
２　、５３　、５４　。

およびオアゲー）５６は一般に第２図のモジュロ制御回
路部を構成している。オアゲー）５６は−ＣＢＩ’とい
うラベルが付いている出力制御信号を与え、この信号は
制御論理回路３１のノアゲート印の第１人力およびマル
チプレクサ回路６１の＠Ｂ”というラベルが付いている
第１人力の両方に接続される。

加算器回路田は４つの全加算器６５　、６６　、６７お
よび錦を含む。全加算益田は加算器器の最下位加算器回
路である。符号ピッ）Ｓはインバータ回路７００Å力お
よび全加算器団のけた上げ入力に接続される。インバー
タ７０の出力は複数の排他的オアゲー）　７２　、７３
　、７４および７５の第１人力に接続されている。

排他的オアゲー）　７２　、７３　、７４および７５の
各々は第２人カラモジュラスピットＭｅ　＊　Ｍｔ　ｅ
　ＭｌおよびＭｓのそれぞれの１つに接続させる。ピッ
）Ｍ（１は入力数Ｍの最下位ビットである。全加算益田
の第１人力は＠　１ｉｌｉ、　ｌ−というラベルが付い
ている全加算器菊の出力に接続され、全加算益田の第２
人力は排他的オアゲート７２の出力に接続されている。

全加算器６の第１人力は＠Ｒ′１”というラベルが付い
ている全加算器４１の出力に接続され、全加算益田の第
２人力は排他的オアゲートｎの出力に接続されている。

全加算器６７の第１人力は１Ｒ−”というラベルが付い
ている全加算器４２の出力に接続され、全加算器６７の
第２人力は排他的オアゲート７４の出力に接続されてい
る。全加算器部の第１人力は″ｆ１１ｍ”というラベル
が付いている全加算器心の出力に接続され、全加算器団
の第２人力は排他的オアゲート７５の出力に接続されて
いる。′″Ｃｏｍ“というラベルが付いている全加算益
田のけた上げ出力は全加算器６のけた上げ入力およびア
ンドゲート８１の第１人力の両方に接続されている。″
Ｃ１！１というラベルが付いている全加算器６０けた上
げ出力は全加算器６７のけた上げ入力およびアンドゲー
ト８２の第１人力の両方に接続されている。′″ｃｘｓ
”というラベルが付いている全加算器６７のけた上げ出
力は全加算器部のけた上げ入力およびアントゲ、−ト田
の第１人力の両方に接続されている。′″Ｃａ！”とい
うラベルが付いている全加算益田のけた上げ出力はアン
ドゲートあの第１人力に接続されている。アントゲ−）
　８１　、８２　、８３および磨の各々は第２人力を複
数の符号化制御信号Ｋｏ、Ｋｌ、ＫｓおよびＫｌのそれ
ぞれの１つに結合させている０アンドゲート８１　、８
２　、８３およびあの各々は出力をオアゲート８５のそ
れぞれの入力に接続されている。アンドゲート８１〜８
４およびオアゲー）８５は一般に第２図のモジュロ制御
回路を構成する０才アゲート羽の出力は＠ｃｉ＋ｔ”と
いうラベルが付いているけた上げ制御信号を与え、ノア
ゲートωの第２人力に接続されている。ノアゲートωの
出力は＠Ａ′というラベルが付いているマルチプレクサ
回路６１の第２人力に接続されている。

マルチプレクサ回路２２は一般に複数のランク付けされ
たマルチプレクサ８７　、８８　、８９および頭を含む
。

全加算器６５　、６６　、６７および錦の各出力はマル
チプレクサ８７　、８８　、８９および匍の所定の第１
人力にそれぞれ接続されている。全加算器４０　、４１
　、４２および４３の各出力はマルチプレクサ８７　、
８８　、８９および頭の所定の第２人力にそれぞれ接続
されている。マルチプレクサ回路６１は出力信号を与え
、その信号はマルチプレクサ８７　、８８　、８９およ
び美の各々の第３人力に接続される。マルチプレクサ８
７　、８８　、８９および（イ）の各々の出力はＡｏ　
、ＡＩ　、ＡｘおよびＡ１というラベルが付いている出
力Ａの所定のビットを与える。図示されているように、
ピッ）　Ａｏは出力数人の最下位ビットである。

動作すると、加算器４０〜４３は数Ｎの符号および増分
／減分制御信号の値の両方に応じて数値和（ＲＡＭ）又
は数値差（Ｒ−Ｎ）となる出力Ｒ′を計算するように機
能する。増分／減分制御信号が論理零値を有すると、増
分関数（ｆｕｎｃｔｉｏｎ　）がプログラムされ、増分
／減分制御信号が論理１値を有すると、減分関数がプロ
グラムされる。図示するため、増分が最初に増分／減分
制御信号によってプログラムされるものとする。符号ビ
ットＳが論理零であると、加算器４０〜４３の出力は合
計値となる。結果として生じた和の各ビットは直ちにマ
ルチプレクサ回路ｎに結合される。同時に、全加算器４
０〜４３によって計算された和は、′Ｗ＃というラベル
が付いている出力和を計算する全加算器５〜槌のＡ入力
に結合される。Ｗ和出力はモジュロ値によってオフセッ
トされたＲ′和を表わす。同時に、全加算器４０〜４３
が発生させたランク付けされた複数の中間けた上げビッ
トの各々はアンドゲート５１〜５４のそれぞれの１つの
入力に結合される。

第４図にはモジュａ／けた上げ制御回路部および器に結
合されるランク付けされた複数のモジュ　　　−口制御
信号に・〜Ｋｓを与えるデコーダＩＯ多数の可能な実施
例の１つが示されている。モジュロピッ）　Ｍｅ〜Ｍ８
が与えられ、下記に述べるように選択名れたモジュロか
ら１ｔ−差引いた値を定める。

インバータ９１は入力をモジュロピッ）Ｍｅに接続され
、出力をノアゲート９２の第１人力に接続させている。

ノアゲート９２は第２人力をモジュロビットＭ１に接続
させ、第３人力をモジュロビットＭｇに接続させ、第４
人力をモジュロピッ）Ｍｓに接続させている。ノアゲー
ト９２の出力は制御信号ピッ）Ｋ。

を与える。インバータ９３０入力はモジュロビットＭｌ
に接続され、インバータ９３の出力はノアゲート９４の
第１人力に接続されている。ノアゲート９４０′ＷＩ２
人力はモジュロビットＭ！に接続され、ノアゲート９４
の第３人力はモジュロピッ）Ｍｓに接続されている。ノ
アゲート９４の出力は制御信号ピッ）Ｋｌを与える。イ
ンバータ９５は入力をモジュロビット市に接続させ、出
力をノアゲート％の第１人力に接続させている。ノアゲ
ート％の第２人力はモジュロピッ）Ｍｓに接続され、ノ
アゲート９６の出力は制御信号ピッ）Ｋｇを与える。制
御信号ピッ）Ｋｓはモジュロピッ）Ｍｓと全く同一のも
のとして与えられる。

動作すると、モジュロ制御信号Ｋｏ　％　Ｋｇは、加算
器２１および田の各々のどの中間けた上げビットがラッ
プアラウンド状態を決定するために調べられるのかとい
うことを本質的に制御する制御信号である。ラップアラ
ンド検出のために中開けた上げビットを用いることは、
下限が零か、又は所定の基数（ｂａｓ＠）を有する数の
整数倍であることを要求することによって可能となる。

デコーダγを実施する場合に、選択名れたモジュロｔ一
定めるモジュロ人カビットがモジュロから１ｔ−差引い
た値を実際に定めるならば制御論理は最小となる。従っ
て、ランク付けされたビットＭ（１〜Ｍｍは２進法で（
Ｍ−１）を定める。この値はモジュラスにおける最高値
数とモジュロ値との間の正確に１の差によって復号を簡
単にする。付属書類１の第１表を参照すると、最高でモ
ジュロ１６１での応用に対するモジュロデコーダＩを実
施するための真理値表が示されている。特定のモジュラ
スが第１表には示されているが、本発明は任意のモジュ
ラスサイズとともに用いうろことが容易に理解されるは
ずである。Ｍｘ＋１のビットによって定められる特定の
モジュラスに対応する２進法でランク付けされたけた上
げピッ）　Ｃ６〜Ｃｓが示されている。但し、Ｍｘはに
最下位モジュロピッ）Ｍｏ。

Ｍｌなどを表わす０　例えば、モジュロ入力制御ワード
ピッ）　Ｍｏ〜Ｍｓが論理１値を有する最高位ビットが
Ｍｌであるワードを構成する場合には、使用可能なモジ
ュロ値はビットＭｅＯ値に応じて３および４である。同
様に、モジュロ入力制御ワードピッ）　Ｍｏ　％　Ｍｓ
が２進１値を有する最高位ビットがＭｓであるワードを
構成する場合には、可能なモジュロ値は５，６．７およ
び８である。これはＭｅ　、Ｍｌ　。

Ｍ意およびＭｌの２進ビット位置がそれぞれ１，２゜４
および８であるからである。例えばピッ）Ｍｓ。

Ｍｌ、ＭｌおよびＭｏがそれぞれ００１１であると、選
択名れるモジュラスは（３＋１）又は４である。モジュ
ラスが４であると、加算器２１のけた上げビットＣ１１
および加算器器のけた上げビットＣ１！はそれぞれモジ
ュロ／けた上げ制御回路δおよび四によって選択名れる
。制御ビットＳと組合せられてＣ１ｌおよびＣ１！は制
御論理回路３１によって復号され、出力マルチプレクサ
２２を介して正しい出力を選択する選択制御信号を与え
る。

制御論理回路３１は付属書類１の第２表の真理値表によ
って選択制御信号出力を与える。Ｓ制御信号が論理零で
ある場合には、加算器回路２１はモジュロ範囲の上限に
近づきつつある。けた上げ制御ピッ）　ＣＢＳとＣＢＩ
の両方が論理零である場合には、上限のラップアラウン
ドは起きない。けた上げ制御ビットＣＢ１およびＣＢＫ
の両方を調べる必要がある理由は２つあシ、第１表を参
照すると更によく理解されるかもしれない。加算器２１
と詔の両方の高位けた上げビットは多数のモジュラスを
表わす。

このことは、可能な値の範囲は選択名れる実際のモジュ
ロの範囲よシ広いかもしれないことを意味する。例えば
けた上げピッ）Ｃｍｘに関していうと、モジュロ５が選
択名れ結果として生じる和が６であると、ラップアラウ
ンドが起きたことを示すためにＣａｔに対するけた上げ
出力ビットは発生しない。従って、ラップアラウンドが
起きたとしても、けた上げ制御ビットＣＢ１は零である
。しかし、５のモジュラスサイズが加算器２３によって
６から減算されその結果が負の方向にオーバフローしな
いと、けた上げ制御ピッ）Ｃｇｇは論理１でアシ、上限
のラップアラウンドが起電たことを示す。加算器ｎにお
いてモジュラス値を減算する場合には、けた上げは借シ
の逆であ＃）１の中間けた上げ値は上限のｋ　ＬＳＢｓ
によるラップアラウンドが起きたことを示すということ
を忘れてはならない。要約すると、ビットＳによって示
されるように加算の期間中にけた上げ制御ピッ）ＣＢＩ
又はＣＢＩのいづれかが論理１値を有すると、ラップア
ラウンド状態が存在し、マルチプレクサ６１は選択信号
をマルチプレクサ回路２２へ与え、マルチプレクサｎが
正しい出力Ａとして加算器ｎのＷラップアラウンド出力
を与えるようにさせる。

Ｓ制御ビットが論理１であると、加算器回路２１はモジ
ュロ範囲の下限に近づきつつある。ラップアラウンドの
存在を決定するには第１けた上げビットＣＢ１だけを調
べさえすればよい。これはドントケア状態を示す第２表
のＣ８ｌ欄に書かれ九″″Ｘ”によって示されている。

加算器２１の中開けた上げビットを調べるだけでよい理
由は、各けた上げビットに対して複数のモジュロ値が存
在する場合に第１表からどのモジュラス値が選択名れる
かには関係なく下限は既知の定められた値であるからで
ある。この結果、加算器器によって与えられるモジュラ
ス値の加算は追加情報を与えない。

上述の理由によシビツ）　Ｍｏ　ｗ　Ｍ−はモジュラス
値から１を差引いた値を表わすので、加算器２３はモジ
ュラスの全範囲が加算器２１のＲ′出力へ加算されるか
又はそれから減算されるようにするために補償されなけ
ればならない。従って、モジュラスがＲ′から減算され
つつある場合には、減算されつつある値は実際には（Ｍ
ｘ＋ｚ）である。その結果生じる値は（Ｍｘ　　１）で
ある。モジュラスが減算されつつある場合には零〇けた
上げ入力を加算器６５に結合させることによって、（Ｍ
ｘ　”　１　）の全体値が数Ｒ′から減算される。排他
的オアゲート７２〜７５は全加算益田のけた上げ入力ビ
ットと一緒に機能して（Ｍｘ　＋　１　）の２の補数を
作υ、これがＲ′に加算されてその減算を達成する。（
Ｍｘ＋　１　）がＲ′に加算される場合には、この反対
が行われる。１０けた上げ入力が加算益田に結合される
ので、Ｒ′に加算される全体値は（Ｍｘ＋１）となる。

加算演算の簡単な例で装置夏の動作を更に説明する。加
算演算が示されているので、増分／減分制御信号は論理
零である。演算（５＋３）モジュロ６ｆ：計算するもの
とする。正しい答は２である。

この例において、モジュラス６は２又は８の表示の範囲
内であるので数ＲおよびＮの３つのＬＳＢ　ｓの中間け
た上げピッ）　Ｃ１ｌおよびＣａｍを調べなければなら
ない。数Ｒは５．又は２進法の０１０１であシ、数Ｎは
３．又は２進法の００１１であり、モジュラスよシ１少
ない数Ｍｘは５．又は２進法の０１０１である。数Ｎの
符号ビットＮＩは零であシ増分／減分制御信号は零であ
るので、Ｓビットは零となる。加算器ｎｏｗ出力は８．
又は２進法の１０００に等しい。中聞けた上げピッ）　
Ｃａｔ、　ＣＩＩ。

Ｃ１１およびＣｏｓはそれぞれ０１１１である。モジュ
ロ制御ピッ）　Ｋｓ、　Ｋｇ、　ＫｔおよびＫｏはそれ
ぞれ０１００であシ、このことは第３中間けた上げビッ
トｃｘｌおよびＣａｔが調べられることを意味する。

ピッ）　ＫｇおよびＣＩＩはともに２進法の１であるの
で−出力モシュａけた上げビットＣＢ１は２進法の１で
あシ、このことはラップアラウンドが起き九こと、およ
びマルチプレクサ回路ｎのＡ端子を出力に結合してラッ
プアラウンド数Ｗを与えるべきことをマルチプレクサ回
路６１に示す。加算器器においては、Ｒ′数１０００が
全加算器５〜簡のそれぞれのＡ入力において加算益田に
結合される。６゜即ち０１１０の２の補数値、即ち１０
１０を全加算器６〜田のそれぞれのＢ入力に結合するこ
とによって、モジュラス値（Ｍｘ−１−１）がＲ′から
減算される。

その結果生じる加算器器のＷラップアラウンド出力は０
０１０　、又は２であ夛、これはマルチプレクサｎに結
合される。けた上げ制御ビットＣＢ１は１であシＳビッ
トは零で加算を示すので、数Ｗは付属書類１の第２表に
従って出力される。ＣＢＩが１であるという事実によシ
関連はないが、ＣＨ２Ｏ値は零である。Ｋｍが２進法の
１の値を有する唯一のモジュロ制御ビットであシ、加算
器幻の中開けた上げビットＣ！！が論理零であるという
ことによｎ　ｃＢ、の値は決定され虎。従って、オアゲ
ートδの出力は論理零である。上限のラップアラウンド
が起きないと、加算器２１および器のＣＢＩおよびＣＩ
Ｉ。

は両方とも論理零である点に注目すべきである。

上記の説明から任意のモジュラスにおける可変数の和お
よび差を与えるモジュロＭ演算装置が提供されているこ
とが明らかになったはずである。

本発明は例をあげたからといって特定のビットサイズに
限定されるものではない。更に、本発明は、関連する回
路のサイズが適当なものであれば個々の回路のうちの選
択名れた回路は相異なるビットサイズを用いて実施でき
るように本発明を変更してもよい。任意のワードサイズ
を適当な復号技術によって実施してもよく、モジュロ演
算装置に必要な量はビットサイズと正確に縮約関係にあ
る。

本発明は特定の種類の演算に限定されるものではなく、
１例として２進演算で示しであるにすぎない。例えば、
ＢＣＤ（２進化１０進数）などの他の種類の演算も本発
明とともに容易に使用できる。また本発明は整数演算の
ような特定の種類の数表現に限定されるものでもない。

本発明は符号付数又は符号の付いていない数とともに用
いてもよい。

浮動小数点数のような他の数表現を用いてもよい。

更に、本発明の特定の制御部分を実施するために多くの
方法が存在する。本発明の一部を実施するために従来の
ＰＬ人又はＲＯＭ　ｔ−用いてもよい。加算器回路２１
および幻およびモジュロデコーダ回路ｎにおいて速度を
改善し論理を最小にするために従来のけた上げ先見技術
を用いてもよい。

図示した形においては、１つだけのラップアラウンド金
検出する能力に関する制約および許容できる下限の制限
は実際の応用例の大部分にとって制約にならないという
点にも注目すべきである。

一般に、メモリにおける待ち行列、循環バッファおよび
ＦＩＦＯを作るためのアドレス計算はデータ構造へのア
クセスの性質の故に２つ以上のラップアラウンドを有し
ない。例えば、ＦＩＦＯは一時に数個のデータ項目を挿
入し除去することを基礎にして動作する。ＦＩＦＯのモ
ジュロサイズはＦＩＦＯデータ構成からの各挿入又は除
去のサイズよりも一般的にははるかに大きい。一部の大
きなデータプロセッサでは、データは一時に数ワードづ
つメモリへ挿入され、又はメモリから挿入される。代表
的なモジュロサイズの場合には、モジエロラップアラウ
ンドは１つの命令につき２回以上は決して起きない。こ
れは１よシ大きいオフセットを許すことがモジュロ演算
にとって有利な場合のもう１つの例である。

波形発生もまた、記憶された波形の１周期を通してのモ
ジュロアドレス指定の使用に基づいて任意の周波数信号
が発生するモジュロ演算使用の一般的な例である。モジ
ュロＭは波形の１周期に対する記憶の長さに等しい。オ
フセラ）Ｎは発生する波形の角速度である。出力値当た
シ完全な１周期の小数部（ｆｒａｃｔｉｏｎｓ　）を発
生させるためには、オフセットＮはモジュラスＭよシ小
でなければならない。従って、Ｎの絶対値はモジュラス
値よシ小さいか又はモジュラス値に等しくなければなら
ないという上述した制約は波形発生応用例では全く問題
にならない。しかし、任意のオフセットおよびモジュロ
値を用いてモジュロアドレス指定および算術計算を行う
能力によって得られる柔軟性は信号処理応用例において
きわめて貴重である。

付属書類 第１表 制御論理回路 Ｓ　ＣＢＩＣＢＩ　　選択　　　　　注　　釈０００１
（Ｂ）　　　　上限のラップアラウンドなし０ＸＩＯ（
Ａ）　　　　上限のラップアラウンド１．００（Ａ）　
　　　下限のラップアラウンド以下本発明の実施の態様
を説明する。

１、算術演算制御信号に応答し、選択的に第１数に第２
数を加算するか、又は第１数から第２数を減算するステ
ップと、 選択的加算又は減算に応答して少なくとも１つの第１け
た上げ信号と第１中間数を４え、前記第１中間数は第１
および第２入力数の線形演算和又は差を表わすステップ
と、 選択的に第１中間数に選択名れたモジュラス数を加算す
るか又は第１中間数から選択名れたモジュラス数を減算
して第２中間数および少なくとも１つの第２けた上げ信
号を与え、前記第２中間数は第１および第２入力数のモ
ジュロ演算和又は差を表わすステップと、 選択名れたモジュラス数と第１および第２けた上げ信号
の所定の組合せに応答して第１および第２入力数の加算
又は減算が上限又は下限のラップアラウンドを結果とし
て生じさせたかどうかを選択的に検出し、それに応答し
て出刃数として第１又は第２中間数のうちの１つを与え
るステップとを含む、 モジュロ演算における第１および第２入力数の和又は差
として出力数を与えることを目的とし、第１入力数およ
び出力数は複数の所定のモジュラス数のうちの選択名れ
た１つに関連して上限および下限を有する所定範囲内に
あり、第２数は選択名れたモジュラス数よ）小さいか又
はそのモジュラス数に等しい絶対値を有する方法。

【図面の簡単な説明】

第１図は、技術上知られているモジュロ演算回路をブロ
ック図の形で示す。 第２図は、本発明によるモジュロ演算回路の１実施例を
ブロック図の形で示す。 第３図は、第２図のモジュロ演算回路を部分概略図形で
示す。 第４図は、第２図のデコーダの好ましい形を部分概略図
形で示す。 第２図において、 ２１は加算器、ｎはｉルチプレクサ、　２５．２９はモ
ジュロけた上げ制御回路、ｎはデコーダ、３１は制御論
理回路。

Claims (1)

1. 【特許請求の範囲】 第１および第２入力数の和又は差として出力数を与え、
   前記第１入力数および出力数は複数の所定のモジユラス
   数のうちの選択名れた１つに関連して上限および下限を
   有する所定範囲内にあり、前記第２数は選択されたモジ
   ユラス数より小さいか又はそのモジユラス数に等しい絶
   対値を有し、前記和又は差は上限又は下限に近づくか又
   は上限又は下限をラツプアラウンドするモジユロ演算装
   置にして、 第１および第２入力数を選択的に受けとる入力を有して
   いて第１および第２入力数を加算又は減算し、第１和又
   は差数およびランク付けされた複数の第１けた上げ信号
   のうちの少なくとも１つの第１けた上げ信号を与え、前
   記第１和数は第１および第２入力数の線形演算和又は差
   を表わす第１加算器手段と、 第１和又は差数および選択されたモジユラス数を選択的
   に受けとる入力を有していて第１和又は差数からモジユ
   ラス数を減算するか、又は第１和又は差数へモジユラス
   数を加算し、第２和又は差数およびランク付けされた複
   数の第２けた上げ信号のうちの少なくとも１つの第２け
   た上げ信号を与え、前記第２和又は差数は第１および第
   ２入力数のモジユロ演算和又は差を表わす第２加算器手
   段と、 第１および第２加算器手段の両方に結合され、第１およ
   び第２けた上げ信号を選択的に受けとり、選択されたモ
   ジユラス数および第１および第２けた上げ信号に応答し
   て第１および第２入力数の和又は差から生じる上限又は
   下限のラツプアラウンドを選択的に検出し、第１又は第
   ２和又は差の１つを出力数として検出する制御手段と、
   を具えることを特徴とするモジユロ演算装置。