JPH01245334A - ２つの数の和のパリティビットの計算装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、特にコンピュータのプロセッサで使用される
加算器に関するものである。

さらに詳細には、本発明は、２つの２進数が入力される
加算器によって計算された加算結果である２進数に付属
するパリティビットを計算するための回路に関する。

従来の技術 一般に、ワードまたは２進数に付属するパリティピット
は、これらワードまたは２進数が処理回路で処理された
後にエラーを生じていないかどうかを検出することがで
きるようにするために使用される。

通常は、複数のビットからなる１つのグループのパリテ
ィピットは、このグループを構成するビット全体に対し
て行った「排他的ＯＲＪ演算の組み合わせの結果である
と定義される。従って、パリティピットは、このグルー
プに含まれている「１」の数が奇数の場合には値「１」
をとる。そこで、このグループの中の１つのみのビット
、または奇数個のビットが誤っている場合には、パリテ
ィピットは本来とるべき値とは反対の値をとる。

従って、このグループに基づいて計算した実際のパリテ
ィと、パリティピットの値に対応する予期されるパリテ
ィとを単に比較することによりエラーを検出することが
できる。さらに、ワードは複数のビットグループで形成
することができ、各グループにパリティピットを１つ割
り当てる。従って、１つのワードを複数のパリティピッ
トと関係付けることができる。

１つまたは複数のワードに対して演算を実行するときに
は、この演算の結果がやはり１つまたは複数のパリティ
ピットと関係付けられているのが都合がよい。これは特
に加算演算の場合である。

加算結果のパリティピットは、この加算結果をもとにし
て直接計算することができる。しかし、この方法を用い
ると、結果のパリティピットは、この結果自体が得られ
てからかなり時間が経過した後にしか得ることはできな
い。このため、この結果と、関係するパリティピットと
が次の処理で使用される時期が遅くなる。

さらに、パリティピットは、本来の結果とは独立に計算
できることが望ましい。というのは、このようにすると
加算の正確さをモニタできるからである。

和のパリティピットの予想の問題は多数の論文で取り扱
われており、それぞれの論文には特殊な場合の解決法が
与えられている。この状況が、例えばＩ　ＢＭ（Ｔ）　
Ｔｅｃｈｎｉｃａｌ　Ｄｉｓｃｌｏｓｕｒｅ　Ｂｕｌｌ
ｅｔｉｎ第２３巻、第１２号、１９８１年５月、５４９
８〜５５０２ページに示されている。

発明が解決しようとする課題 しかし、パリティピットを計算しようとするワードが多
数のビットを含んでいるときには、上記の公知の任意の
装置を用いてあらゆる場合に高速演算を行うことができ
るわけではない。

本発明は、２つの数の和のパリティピットをできるだけ
短時間で計算できるようにすることを目的とする。パリ
ティピットを高速で計算できることの利点は、この計算
によって加算器が次の演算を再び実行できるようになる
時期を遅らせることがない点にある。この結果、計算ユ
ニットは高周波数で動作することが可能になる。

和のパリティピットの計算速度が、加算の途中で現れる
キャリービットによって形成されたワードに関係するパ
リティピットの計算速度に影響されることを後述する。

このワードを、以後「キャリーワード」と称する。

加算する数が多数のビットを含んでいる場合には、この
ワードが複数のビットグループの連結体であると考え、
これらグループのそれぞれにパリティピットを対応させ
ることがより望ましい。例えば、６４ビツトのワードに
は８個のパリティピットを対応させることができる。す
なわち、各パリティピットは、このワードの８ビツトか
らなる１つのグループに対応している。この方法を用い
ると、特に、異なるグループにまたがる複数のエラ−が
ある場合にエラー検出が非常に実行しやすくなる。

定義により、キャリーワードから取り出されたグループ
に関係するパリティビットは、原則として加算時に形成
された全キャリービットに依存する。

キャリービットの計算の問題は既に加算器を実現する際
に提起されている。実際、キャリービットは、位が上で
あるほど遅く得られる。このようなわけで、加算器にお
いては、キャリービットをできるだけ速く計算するため
にキャリー予測回路を実現しようとする試みがなされて
いる。

しかし、高性能の回路を用いても、上位のキャリーは常
に加算演算のほぼ最後になって得られる。

課題を解決するための手段 そこで、本発明は、キャリーワードを形成するグループ
に関係するパリティビットを計算するために、キャリー
ビットの計算が実行されるごとにパリティビットの計算
に次に必要とされる時間が最大限短縮される方法を提供
する。この結果は、本発明の装置が、この計算を以下の
２段階、すなわち −加算する数のみに依存する変数を入力変数として利用
する第１段階と、 −キャリービットが介入する高速の第２段階とを利用し
て実行することにより可能になる。

第１段階は、加算器の予測回路によってキャリーの計算
が実行されている間に行われる。この計算が相対的に遅
いことを考慮すると、この第１段階は、予備計算を最大
限に実施し、従ってより高速にされた第２段階を簡単化
できるように構成されている。

より詳細には、本発明により、２つの２進数の加算の際
に現れるキャリーワードから取り出された連続したｍビ
ットからなる少なくとも１つのグループに関係したパリ
ティビットを計算するにあたって、上記の２つの２進数
はそれぞれ、ｍビットからなる少なくとも１つのグルー
プを含み、これらグループは、同じ位のビットでそれぞ
れ構成された上記２進数と上記キャリーワードにそれぞ
れ属しており、上記２進数から取り出された上記グルー
プは、それぞれがビットａｍ−，、、、ａｌｒ−０−Ｃ
２，ａ、　　と、ビットｂ、、９０．．ｂｌ、、−，，
ｂ、、ｂ、で構成されている（添字ｌは対応するピッ）
（ａｉ。

ｂｔ）のグループ内の位を表す）計算装置であって、−
１と（ｍ−１）の間のすべての１に対してｐ＋　＝ａｉ
■ｂ。

ｇＩ＝ａＩ−ｂ。

（■は、「排他的ＯＲ」演算を意味する）を計算する第
１段と、 −１と（ｍ−１）の間のすべての１に対して、以下の再
帰式 ％式％ （ただし、Ｐ　１＝　ｐ＋、Ｇ　ｌ＝　ｇ　＋　）を満
たす値Ｐ＋ならびに値Ｇｊの計算を行う第１の演算器と
、 −Ｙ＝ＧｊｆＥＥ）Ｇ２ｆＢ、、、■ｃｉｅ、、、ｅＧ
ｊ−。

Ｘ　＝　Ｐ　＋　ｅｉ３　Ｐ　２の、、、■ｐｔの、、
、＄Ｐ、−＋を計算するための第２の演算器と、 −ｐｃ＝ｙ６９ｃｌｌｉ・ｘ” （ただし、Ｃ１，、はグループの最下位のキャリービッ
トであり、Ｘ＊はＸの補数である） を計算する第３の演算器とを備えることを特徴とする装
置が提供される。

次に、この装置は、各オペランドのパリティビットを関
与させて和に関係するパリティビットを直接出力できる
ように変更し、しかもこのことで、計算が遅くならない
ようにすることができる。

従って、本発明によればさらに、２つの２進数の和から
取り出されたｍビットからなる少なくとも１つのグルー
プに関係したパリティビットを計算する装置であって、
上記の計算装置と、上記２進数から取り出されたグルー
プのパリティＰＡとＰＢを導入するための［排他的ＯＲ
Ｊの追加回路を備え、 −第１の演算器の任意の１つの出力Ｇｊを、上記追加回
路によって実行された演算ＰＡ■ＰＢｅＧ１の結果で置
換するか、あるいは −第１の演算器の任意の２つの出力ＧｉとＧｊを、それ
ぞれ演算Ｐ　Ａ　ｍ　Ｇ　ｔと演算Ｐ　Ｂ　＠　Ｇ　Ｊ
の結果で置換するように構成されていることを特徴とす
る装置が提供される。

本発明の特徴および利点は、以下に説明する好ましい実
施例において明らかになろう。

実施例 本発明を記述する前に、図面を参照して本発明の理論的
基礎を説明しておくのが好都合である。

Ｎビットの２つの数ＡとＢが、それぞれビットａＮｙ　
ａＭ−ｕ−０，＋　ａｉｎ−−−＋　ａ　２＋　ａｌ　
とビットｂ＊。

ｂや−１＋、、、ｔ　ｂｌ＋１６．＋　ｂ２＋　ｂ、で
構成されている場合にこれら２つの数の加算を実行する
ために現在行われている方法は、加算に関与するキャリ
ービットＣ１で形成されたキャリーワードＣの予測回路
を利用することである。

このタイプの従来の加算器は、２つの数Ａ、　Ｂのビッ
トａ１、ｂｌをもとにして、以下の式９式％ （ｅは、「排他的ＯＲＪ演算を意味する）で計算される
中間変数ｐ１とｇＩを形成する第１段を備えている。

位ｌのキャリーピッ）ａｔがわかっていると仮定すると
、和の位１のビットＳ１は、式９式％ から得られる。

他方、Ｃ，は Ｃム”ｇｔ−＋＋　１ｅｔ−１”　Ｃｔ−＋と定義され
る。

そこで、オペランドのビットａｌＳｂｉのみに依存する
変数ｐｉとｇ、をもとにしての繰り上げ近似により、キ
ャリービットを次々に計算することができる。この計算
は、先に説明したキャリー予測回路により実行される。

加算器は、式５ｔ＝ｐｔｅＣ，によって得られる和Ｓの
ビットＳ１を計算する最終段を備えている。

ここで、数ＡＳＢ、Ｃから連続部分として取り出されて
おり、それぞれがピッ）ａＬｓｂｉ、Ｃ１（ｉは関係す
るビットからなるグループの位を示す）で構成されたビ
ットで形成されたグループを考える。Ｃ１が考えている
グループのうちの１つの中で見出される最下位のキャリ
ービットを表すことにすると、ｑよりも上位のｉでは、
Ｃ８や１＝　Ｇ　、＋　Ｐ　ｉ・Ｃｑ であることを示すことが可能である。ここに、Ｐ。

とＧＩは、以下の再帰式 ％式％ （ただし、Ｐｑ　”　ｐｑ　、Ｇｑ　＝ｇｑ　）で定義
される。

この最後の式を用いると、カスケード式に接続された論
理回路の数を減らしたキャリー予測回路を構成すること
ができる。この回路に関しては第３図を参照してあとで
説明する。

ところでパリティビットの問題に関しては、数が一般に
同じｍビットからなる複数のグループで形成されると考
えることができ、各グループには１つのパリティビット
が関係付けられることを見た。

従って、オペランドＡと８１キヤリーワードＣ１それに
和Ｓは、それぞれ、例えばグループＡ１、Ａ２、Ａ１、
Ａ４、グループＢ５、Ｂ２、Ｂ８、Ｂ４、グループＣ１
、Ｃ２、Ｃ１、Ｃ４、それにグループ５１１Ｓ２、Ｂ５
、Ｓ、で構成されている。各グループ、例えばＡｊには
、対応するパリティビット、例えばＰＡ、を関係付ける
。

以下の説明では、パリティビットに関しては、オペラン
ド、キャリーワード、それに和が同類のグループのみを
考える。すなわち、同じ位のビットで構成されたグルー
プのみを考える。さらに、記述を簡単にするため、グル
ープを同定する添字はもはや使用しない。最後に、１つ
のビットの指数ｉは問題となっているグループに関する
相対的な位であり、従って１とｍの間の値になる。位１
というのは、グループ内の最下位である。

グループＡ、ＢＳＳにそれぞれ関係するパリティビット
をＰＡＳＰＢＳＰｓと表記すると、関係式 ＰＳ＝ＰＡ（Ｅ）ＰＢｅＰＣ （ただし、ＰＣ＝ｃ、、■、、、ｅｃ１！、、−＄ｃ２
＄ｃ、）が得られることが容易にわかる。

従って、ＰＣは、加算の際に関与するキャリービットに
よって形成されたグループのパリティビットである。そ
の結果、上記の式を用いてＰＣを得るためには、すべて
のキャリーを利用する必要がある。

ところで、理論計算により、ＰＣを ＰＣ＝Ｙ■ｃｌｎ’Ｘ” （ただし、ＣＩ！１はＣ２すなわちグループの最下位の
キャリービットであり、ＸｏはＸの補数である）の形に
書けることがわかる。ここで、 Ｙ　＝　Ｇ　１ｅ　Ｇ　２　ｆＥ９．　、　、　ｅｉ３
　Ｇ　ｓ　ｆＥ９．　、　、　ＩＥ９　Ｇ−＋Ｘ　＝　
Ｐ　ｒ■Ｐ２■、、、＄ｐ、■、、、ｔＥ９ｐ、−。

であり、Ｐ、とＧｉは、以下の再帰式 ％式％ （ただし、Ｐ　＋　＝　１）　１、Ｇ＋＝ｇ＋）を満た
す。

もちろん、ワードの最下位ビットで構成されたグループ
に対しては、通常の加算が行われるときにはＣ＋ｈ＝０
である。

以下に、上記の式を実行することによっていかにして求
める結果に到達できるかを記述する。

第１図は、本発明のパリティビット発生器に関係した加
算器の図である。

本発明を説明するため、加算すべき数ＡとＢがそれぞれ
４つのビットグループＡ１、Ａ２、Ａ３、Ａ４とＢ１、
Ｂ２、Ｂ３、Ｂ４で構成されていると仮定する。各グル
ープには対応するパリティピットが関係付けられている
。例えばグループＡＩはパリティピットＰＡ１に関係付
けられ、グループＡ２はパリティＰＡ２に関係付けられ
という具合である。

オペランドＡならびにＢと、これら２つのオペランドに
関係付けられたパリティピットは、それぞれレジスタＲ
Ａ、ＲＢＳＲＰＡ、ＲＰＢに保持される。

例えばオペランドＡ１とＢ１から取り出された同類の２
つのグループをここで考える。グループＡ１はｍピッ）
ａ、、で構成されており、グループＢ１はｂｌｌで構成
されている。同じ位のビットａ目とｂ目は、「排他的Ｏ
ＲＪ回路とｒＡＮＤＪ回路を備えていて、変数 ｐ＋　ｔ　＝　ａ　ｌｔ　Ｂ９　ｂ　＋　＋ｇ＋＋＝ａ
目・ｂ目 を計算する回路１１において組み合わされる。

他のグループに関係する回路１２．１３．１４は回路１
１と同じであり、これら回路の全体が加算器の第１段を
形成している。

キャリー予測回路２０ａは、入力に第１段１０の出力を
受ける。この公知のキャリー予測回路２０ａを用いると
、２つのオペランドの加算に関与するすべてのキャリー
Ｃ口・Ｃ２１％　Ｃ３１％　Ｃ４１を計算することがで
きる。この回路２０ａは、上記のグループにそれぞれ関
係した複数の回路２１ａ、２２ａ、２３ａ、２４ａで構
成されていると考えることができる。

オペランドは、これらグループで形成される。

「排他的ＯＲ」で構成されている最終段３０には、回路
２０Ｈのキャリーと、第１段１０からの変数ｐｈｉ〜Ｉ
）４１が入力される。回路３０は加算結果Ｓのビットｓ
Ｉｉ〜Ｓ４１を出力する。この回路３０も、上記のグル
ープにそれぞれ関係した複数の回路３１．３２．３３．
３４で構成されていると考えることができる。

オペランドは、これらグループで形成される。従って、
回路３１は、式 ％式％ を満たす第１のグループのピッ）Ｓ、、を出力する。

上記の説明は加算器のみに関しているが、以下には、こ
の回路のパリティピット発生器に関する部分を説明する
。

図示の実施例では、オペランドＡとＢならびにその和Ｓ
がｍビットの４つのグループで構成されており、各グル
ープには対応する１つのパリティピットが関係付けられ
ていると仮定する。

ハＩＪティビット発生器は、オペランドの同類クループ
のパリティピットと第１段１０からの変数とをそれぞれ
受ける４つの演算回路４１．４２．４３．４４で構成さ
れたユニットを備えている。

例えば第１のグループと関係付けられた演算回路４１は
パリティＰＡＬ、ＦＢＩと、回路１１からの変数ｐａｔ
、ｇ口を受ける。これらの信号に応じて、演算回路４１
は、添字を取った場合の上に示した式を満たす２つの変
数ｘ１とＹｌを出力する。

同様にして、演算回路４２．４３．４４は、それぞれ変
数Ｘ２とＹ２、Ｘ３とＹ３、Ｘ４とＹ４を出力する。

演算回路５１．５２．５３．５４で構成された最終段は
、対応するグループの変数Ｘ、Ｙと、問題となっている
グループに依存したキャリー信号とを受ける。

さらに詳細には、演算回路５４は、第４のグループの最
下位のキャリービットである回路２３ａから出力された
キヤ！Ｊ−Ｃ３ｍ。１を受ける。演算回路５３は、第３
のグループの最下位のキャリービットであるキヤ！Ｊ　
−０２ｍ＋　１を受け、演算回路５２は第２のグループ
の最下位のキャリービットであるキャリーＣａ１１を受
ける。通常の加算の場合には、演算回路５１はキヤ！Ｊ
−Ｃ＋＝０を受ける。

一般に、Ｃ１ｉで対応する演算回路に人力されるキャリ
ーを表すと、各演算回路は、 Ｐ　Ｓ　＝　Ｙ　ｅｃ　ｓ　ｎ　・Ｘ　”を満たす出力
信号Ｐｓｉ、、、ＰＳ４を出力する。

従って、このようにして得られた変数Ｐ８１〜ＰＳ４は
、和から取り出された各グループに関係付けられたパリ
ティビットである。

上記の装置を一般化して、グループ数とグループ当たり
のビット数を任意にすることができる。

加算器の段１０と３０は、従来の「Ａ　Ｎ　Ｄ　Ｊと「
排他的ＯＲ，のタイプの論理回路で構成される。構成法
は当業者には公知であるので、ここでは詳しく説明しな
い。

これとは異なり、演算回路４１〜４４とキャリー予測回
路２０ａは詳しく説明する価値があるので第２図〜第８
図を参照して以下に記述する。

演算回路４１〜４４は互いに同等であるため、そのうち
の１つ、例えば演算回路４１を説明すれば十分である。

さらに、本明細書の導入部分において、問題となってい
るグループのキャリービットに関係付けられたパリティ
の計算に問題点のあることを説明した。そこで、まず最
初に、第２図を参照して。

パリティビットの計算を行う装置を説明する。次に、第
３図を参照して、この装置を和のパリティビットの発生
器に変えるにはどうしたらよいかを説明する。

第２図は、８ビツトからなるグループのキャリービット
と関係付けられたパリティピットの計算を行う回路の図
である。しかし、以下の説明がこの特定の場合に限定さ
れないのは明らかであり、この回路を任意のビット数に
いかにして一般化するかを示す。

第２図の回路は、先に説明した回路１１または同等な別
の回路によって計算された変数ｐ３、ｇ１〜ｐ７、ｇ、
を受ける第１の演算回路４１ａを備えている。実際には
この回路１１は加算器と共通にすることができるが、回
路の集積度を大きくしたいのであれば、加算器とは独立
な回路１１を使用することが好ましい。というのは、共
通の回路１１を使用すると、この回路で発生するエラー
が隠れてしまう可能性があるからである。

演算回路４１ａは、入力に４つの２進数Ｐイ、ＧＸ％Ｐ
７、Ｇｙを受けて、以下の関係式 ％式％ を満たす２つ２進数変数Ｐ２、Ｇ２を出力する第１のタ
イプの論理モジュールＭ、のみで構成されている。

このようなモジュールを用いて上記の構成にすることに
より、ｌが１〜７の場合に、以下の再帰式 ％式％ （ただし、Ｐ　＋　”　ｐ＋、Ｇ　＋　＝　ｇ　＋　）
で定義される変数ＰｉとＧ１を計算することができる。

出力変数の組Ｐ２、Ｇ２を２組の人力変数Ｐ８、Ｇ８と
ＰｙｌＧｊｆに関係付ける関係式は、結合法則を満たす
という重要な性質をもつ。この性質があるため、この回
路の層の数、すなわちカスケード接続されるモジュール
の数を最大限に減らしてモジュールＭ１に変数Ｐ＋、Ｇ
ｔを計算させること々（できるように構成することが可
能になる。

以下に、再帰法によって第１の演算回路４１ａを構成す
る方法を説明する。指数ｉは、問題となっているビット
の位と、演算回路の対応する列の両方を表す。

ｉ＝１に対しては、直接にＰ１＝ｐ１、Ｇ　＋　＝　ｇ
　＋が得られる。ｉが１または２の場合は、ｐｌ、ｇｌ
にｐ２１．ｇｚを第１のモジュール１においてさらに組
み合わせる。このモジュールは、Ｐ２、Ｇ２を出力する
。ｌが３のときには、第３のモジュール３が第１のモジ
ニール１から出力されたＰ２、Ｇ２にｐ３、ｇ３を組み
合わせる。この第３のモジュール３はＰ３、Ｇ３を出力
する。１が４の場合には、別のモジュール２がｐ３、ｇ
３とｐ４、ｇ４を組み合わせ、このモジュール２の出力
は、別のモジュール４でモジュール１の出力と組み合わ
される。このモジュール４はＰ２、Ｇｊを出力する。こ
の結果が得られるのは、モジュールＭ１により実現され
る結合法則のためである。

１が４よりも大きい場合に演算回路４１ａの構成を完全
なものにするためには、以下の方法に従えばよい。

ｌが１と２″の間の値のときの初期構成が実現されてい
る場合には、ｌが（２°＋１）と２　ｈ＋１の場合の構
成は、この初期構成に従って構成されてはいるが上位の
ほうに２″列ずれたモジュールＭ１を追加することによ
って得られる。このようにして、新しい出力が得られる
。次に、２″個の追加モジュールＭ１を配置して、初期
構成から出力された最上位の出力Ｐ２″、Ｇ２ｒ′と、
これら新しい出力のそれぞれをを組み合わせる。

もちろん、この構成は次数（ｍ−１）で止める。

すると、変数Ｐ＋とＧ１のすべての値が得られる。

従って、本実施例では、第１の演算回路４１ａの出力で
次数７までの変数Ｐ１、Ｃｚが得られる。

次に、演算回路４１ａの出力Ｐ１、ＧＩは第２の演算回
路４１ｂの入力に人力される。

演算回路４１ｂは、単に２つの「排他的ＯＲＪ回路であ
る第２のタイプの論理モジュールＭ２で構成されている
。この演算回路４１ｂは、４人力Ｘ８、Ｙ、、Ｘｙ、Ｙ
ｙであり、 Ｘ、＝Ｘ、■Ｘ。

Ｙ、＝Ｙ、■Ｙ。

を満たす２つの出力Ｘ２、Ｙ２を出力する。

これらモジュールＭ２を複数人力の「排他的ＯＲ」回路
と等価なピラミッド構造に配置するだけで十分であるこ
とが直ちにわかる。従って、この構成にすると、関係式 ％式％ で定義される２つの変数ＸとＹを得ることができる。

変数Ｘ、Ｙと、先に定義したキヤ！Ｊ−Ｃｔｎは、第３
の演算回路５１に人力される。この演算回路５１の出力
ＰＣは、論理式 ％式％ （ただし、Ｃａｎ（ここではＣｌ１Ｉ＝ＣＩ）はグルー
プの最下位のキャリービットであり、ｘｏはＸの補数で
ある）によって入力と関係付けられている。

実際には、ｍは常に２の幕であり、ｍ＝２ｎと書くこと
ができる。この場合、変数Ｐ＋、Ｇｔを得るのに必要な
層の数がｎであることを容易に示すことができる。Ｘと
Ｙを得るのに必要な回路の層の数は２ｎであり、従って
パリティＰＣを得るための層の数は全体で（２ｎ＋　１
）である。従って、ｍ＝８の場合には、パリティ発生器
は７層の回路で構成される。

和から取り出されたグループのうちの１つと関係付けら
れたパリティビットを計算することのできる回路を実現
するためには、上記の回路を変更して、オペランドから
取り出されたグループと関係付けられたパリティピット
を関与させる。

関係式 ％式％ が満たされており、「排他的ＯＲＪ演算は交換法則と結
合法則を満たすことを考慮すると、パリティピットをＹ
の式に代入するだけで十分である。

実際には、例えば「排他的ＯＲＪを用いて第１の演算回
路の任意の１つの出力Ｇｉを式ＰＡ■ＰＢｅＧ１で置換
することができる。別の方法は、第１の演算回路の任意
の２つの出力Ｇ１とＧ」を、それぞれ、演算結果ＰＡｅ
Ｇ１とＰＢ■Ｇｊで置換することである。

第３図は、この結果を得ることのできる第２図の回路の
変形例を示す図である。

この実施例によると、オペランドから取り出されたグル
ープのパリティピットＰＡとＰＢは、「排他的ＯＲ」回
路５で組み合わされる。この回路の出力は別の「排他的
ＯＲＪ回路６で変数Ｇ。

と組み合わされる。この第２の「排他的ＯＲ，回路６は
、変数Ｇ’、＝Ｐ１３ＰＢｅＧｊを出力する。

この回路の他の部分はまったく変えることがなく、演算
回路５１の出力は、今や、問題となっているグループに
対する和のパリテイビットＰＳを表す。

第４図は、キャリービット予測回路２０ａを備える加算
器の実施例の一部を示す図である。この回路そのものは
本発明の対象でないとはいえ、本発明の流れをよりよく
理解するには説明しておくのが有益であろう。

第１のグループのキャリー回路予測回路２１ａは、変数
Ｃ１ｎと第１段１０の出力とを受ける。

変数Ｃ１ｈは、キャリーワードの最下位ピア）ｃ。

に対応する。通常の加算では、Ｃｔｈ＝０である。

しかし、この加算器は減算を実行するのに使用すること
もできる。実際、減算（Ａ−Ｂ）の演算は、（Ａ＋Ｂ”
＋１）（ただし、ＢｏはＢの補数である）を計算するの
と同じことである。

このためには、オペランドとしてＡと８９を用い、Ｃｔ
ｎ＝１である加算器を使用することができる。同様に、
このキャリービット計算装置は、やはりＣｔｈ＝１を第
１のグループの回路５１に導入するという条件で使用す
ることができる。

第４図の回路は、式 ％式％ を適用した構成である。

この回路は、変数Ｐ１とＧ１を計算するための先に定義
した複数のモジュールＭ、を備えている。

この回路はさらに、３人力Ｐ８、ＧｊＳｃ、と、関係式 ％式％ を満たす出力Ｃ２とを有する第３のタイプのモジニール
Ｍ３も備えている。

タイプＭ、とタイプＭ３のモジュールは、加算器の技術
において「再帰解法」として知られる構成に従って配置
される。

この回路は、ヰヤ！７−　Ｃｔを出力し、この出力が次
に回路３１内で同じ位の変数ｐ＋　と組み合わされる。

回路３１は加算結果のピッ）Ｓｔを出力する。

加算器は、第２のグループの回路２２ａと３２のほか、
さらに次のグループの回路（ｒＩ！Ｊ示せず）も備えて
いる。

従って、第２図と第３図に示したパリティ発生器に関与
するキャリーは、加算器に属するキャリー予測回路から
取り出すことができる。しかし、このようにすると、パ
リティ発生器で利用されるキャリービットに関するエラ
ーは完全に隠されてしまう可能性がある。この理由で、
これらパリティビットを計算するための独立した回路を
設けることが好ましい。

このような回路は加算器で使用される回路と同じにする
ことができるが、この回路を簡単化して、パリティピッ
トを発生させる際に関与するキャリービットしかこの回
路が出力しないようにするとよい。

第５図は、パリティ発生器の特別なキャリー予測回路の
図である。この回路は、パリティを関係付けられるグル
ープが８ビツトを含む場合を表している。第１の部分回
路２１はキヤ！Ｊ　　Ｃ９を出力する。このキヤ！Ｊ　
−Ｃｓ　は、第２のグループの回路５２０入力信号とな
る。回路２２は、第３のグループの回路５３の入力とな
るキヤ’Ｊ−（−＋７を出力する。

最後に、回路２３（図示せず）は、第４のグループのた
めのキヤ！Ｊ−Ｃ２Ｓを出力する。

もちろん、当業者であれば、この回路を変形してグルー
プが多数あって任意の長さである場合に適合させること
が可能である。

加算する数がＮビットである（Ｎは２０幕、すなわちＮ
＝２１である）場合には、キャリー予測回路がｒ層を含
むことに注目することが重要である。この結果、加算器
は前部で（ｒ層１）層を含むことになる。この結果は、
パリティ発生器を実現するのに必要とされる（２ｎ＋１
）層と比較される。従って、ｎをｒの関数として選択す
るとよい。

例えばＮ＝６４、ｍ＝８であるとすると、加算器とパリ
ティ発生器に対して正確に同じ数の層が得られる。しか
し、これは、これら２つの回路が正確に同じスピードで
あることを意味しているわけではない。実際、加算器と
パリティ発生器に関与する論理モジニールは互いに同等
ではない。特に、最終層では、演算回路５１が加算器の
最終層３１の「排他的ＯＲ」よりも複雑な演算を実行す
る。この結果、パリティ発生器が加算器からのキャリー
を利用する場合には、パリティビットが得られるのが加
算結果が得られるのよりもわずかに遅くなる。しかし、
加算器の回路と独立なキャリー発生器を用いる場合には
、このハンディキャラフカ相殺される。実際、第４図に
示された回路と第５図に示された回路を比較すると、例
えば回路２１ａの最後から２番目のモジュールＭ３の１
つが複数のモジュールＭ、に出力を行うのに対し、第５
図の回路ではそのようになっていないことがわかる。

この結果としてこの段に入力容量の差が生じ、従って第
５図の回路は第４図の回路よりも高速になる。従って、
パリティ発生器が相対的に複雑であることは、キャリー
予測回路が簡単化されることで相殺される。

以下に、本発明のパリティ発生器をＣＭＯ３技術で実現
するための情報を与える。

モジュールＭ、が、 Ｐ、＝Ｐ、−Ｐ。

Ｇｊ＝Ｇｙ＋Ｐｙ−Ｇ。

を実行することは既に説明した。

しかし、ＣＭＯ３技術では、補機能とその二重機能を得
るのがより簡単になる。

第６図は、Ｇ２の補数である変数Ｇｚ＊を得ることので
きるＣＭＯ３回路の図である。この回路には、Ｐ２の補
数であるＰｒを出力するＮ　Ａ　Ｎ　Ｄゲートを接続す
ることができる。

第７図は、上記の二重機能を得ることのできる回路の図
である。つまり、Ｇ２、Ｇｙ＊、ＰげはそれぞれＧ８、
Ｇｊ、Ｐ、の補数であり、第７図の回路は式 ％式％ を満たすＧ２を出力する。

第７図のこの回路は、ＮＯＲゲートに接続することがで
きる。従って、先に定義したモジニールＭ＋　の代わり
にこれら回路をそれぞれ使用して、最終結果を変えるこ
となく第２図と第３図の回路を実現することができる。

ただし、このためには適当なインバータを設ける必要が
ある。

これら回路はキャリー予測回路のモジュールＭ３を実現
するのに使用することもできる。

これら回路の構成法は当業者には公知であるため、これ
以上説明する必要はない。

第８図は、「排他的ＯＲ４機能を実現するためのＣＭＯ
３回路の一例を示す図である。この回路は、例えば第２
図と第３図のモジュールＭ２と５１を実現するのに使用
することができる。

【図面の簡単な説明】

第１図は、加算器と本発明の装置を含む全体の回路図で
ある。 第２図は、キャリーワードから取り出された８ビツトか
らなるグループに関係するパリティビットの計算装置の
図である。 第３図は、２つの２進数の和から取り出された８個のビ
ットからなるグループに関係するパリティビットを計算
する装置の図である。 第４図は、本発明の装置と組み合わされる加算器の一例
を示す図である。 第５図は、本発明の一実施例によるキャリー予測回路の
図である。 第６図と第７図は、本発明の装置で使用することのでき
る論理モジュールの実施例を示す図である。 第８図は、本発明の装置で使用することのできる別のモ
ジュールの実施例を示す図である。 （主な参照番号） ５．６・・排他的ＯＲ回路、 １０・・第１段、 ２ＯＡ、２１ａ・・キャリー予測回路、３０・・最終段
、 ４１〜４４．４１ａ、４１ｂ１５１〜５４・・演算回路
、ＡＳＢ・・オペランド、 Ａ１−Ａ４、Ｂ１〜Ｂ４・・ビットグループ、ＣＩ　Ｉ
　ＳＣ２１）Ｃ３ｉ　ＳＣ４１・・キャリー）Ｍｌ、Ｍ
２、Ｍ３・・論理モジュール、ＰＡＩ〜ＰＡ４、ＦＢＩ
〜ＰＢ４・・パリティピット、 ＲＡ、ＲＢ、ＲＰＡ、ＲＰＢ・・レジスタ、Ｓ・・和 特許出願人　　ビュル　ニス、アー。

Claims (6)

【特許請求の範囲】
1. （１）２つの２進数（Ａ、Ｂ）の加算の際に現れるキャ
   リーワード（Ｃ）から取り出された連続したｍビットか
   らなる少なくとも１つのグループに関係したパリティビ
   ット（ＰＣ）を計算するにあたって、上記の２つの２進
   数（Ａ、Ｂ）の各々は、ｍビットからなる少なくとも１
   つのグループを含み、これらグループは、同じ位のビッ
   トでそれぞれ構成された上記２進数（Ａ、Ｂ）と上記キ
   ャリーワード（Ｃ）にそれぞれ属しており、上記２進数
   （Ａ、Ｂ）から取り出された上記グループは、それぞれ
   がビットａ＿ｍ、．．．、ａ＿ｉ、．．．、ａ＿２、ａ
   ＿１と、ビットｂ＿ｍ、．．．、ｂ＿ｉ、．．．、ｂ＿
   ２、ｂ＿１で構成されている（添字ｉは対応するビット
   （ａ＿ｉ、ｂ＿ｉ）のグループ内の位を表す）計算装置
   であって、 −１と（ｍ−１）の間のすべてのｉに対してｐ＿ｉ＝ａ
   ＿ｉ■ｂ＿ｉ ｇ＿ｉ＝ａ＿ｉ・ｂ＿ｉ （■は、「排他的ＯＲ」演算を意味する） を計算する第１段（１０）と、 −１と（ｍ−１）の間のすべてのｉに対して、以下の再
   帰式 Ｐ＿ｉ＝ｐ＿ｉ・Ｐ＿ｉ＿−＿１ Ｇ＿ｉ＝ｇ＿ｉ＋ｐ＿ｉ・Ｇ＿ｉ＿−＿１ （ただし、Ｐ＿１＝ｐ＿１、Ｇ＿１＝ｇ＿１）を満たす
   値Ｐ＿ｉならびに値Ｇ＿ｉの計算を行う第１の演算器（
   ４１ａ）と、 −Ｙ＝Ｇ＿１■Ｇ＿２■．．．■Ｇ＿ｉ■．．．■Ｇ＿
   ｍ＿−＿１Ｘ＝Ｐ＿１■Ｐ＿２■．．．■Ｐ＿ｉ■．．
   ．■Ｐ＿ｍ＿−＿１を計算するための第２の演算器（４
   １ｂ）と、−ＰＣ＝Ｙ■ｃ＿ｉ＿ｎ・Ｘ＾＊ （ただし、ｃ＿ｉ＿ｎはグループの最下位のキャリービ
   ットであり、Ｘ＾＊はＸの補数である） を計算する第３の演算器（５１）とを備えることを特徴
   とする装置。
2. （２）上記キャリーｃ＿ｉ＿ｎが、上記装置に関係する
   加算器（１０、２０ａ、３０）とは別の回路によって計
   算されることを特徴とする請求項１に記載の装置。
3. （３）上記第１段（１０）が、上記装置に関係する加算
   器（１０、２０ａ、３０）と共通であることを特徴とす
   る請求項１または２に記載の装置。
4. （４）上記第１の演算器（４１ａ）が、４入力Ｐ＿ｘ、
   Ｇ＿ｘ、Ｐ＿ｙ、Ｇ＿ｙに対して演算を行って、以下の
   関係式 Ｐ＿ｚ＝Ｐ＿ｙ・Ｐ＿ｘ Ｇ＿ｚ＝Ｇ＿ｙ＋Ｐ＿ｙ・Ｇ＿ｘ によってこれら入力と関係付けられた２出力Ｐ＿ｚ、Ｇ
   ＿ｚを供給する第１のタイプの複数の論理モジュール（
   Ｍ＿１）で構成されており、これらモジュールは、以下
   の再帰的操作（ただし、ｉは演算器の対応する列を示す
   ）、すなわち ａ）ｉが１または２である場合には、第１のモジュール
   （１）がｐ＿１、ｇ＿１、ｐ＿２、ｇ＿２に対して演算
   を行ってＰ＿２、Ｇ＿２を出力し、 ｂ）ｉが３または４である場合には、第２のモジュール
   （２）がｐ＿３、ｇ＿３、ｐ＿４、ｇ＿４に対して演算
   を行い、第３のモジュール（３）がＰ＿２、Ｇ＿２、ｐ
   ＿３、ｇ＿３に対して演算を行ってＰ＿３、Ｇ＿３を出
   力し、第４のモジュール（４）がＰ＿２、Ｇ＿２と第２
   のモジュール（２）の出力に対して演算を行ってＰ＿４
   、Ｇ＿４を出力し、 ｃ）ｉが１と２＾ｎの間の値であるときに初期構成が実
   現されている場合には、ｉが（２＾ｎ＋１）と２＾ｎ＾
   ＋＾１の間の値である場合の構成をこの初期構成に従っ
   て配置されているが上位のほうに２＾ｎ列ずらされた複
   数のモジュール（Ｍ＿１）を追加することにより実現し
   、このようにして新しい出力を供給し、２＾ｎ個の第１
   のタイプの追加モジュール（Ｍ＿１）を、上記の初期構
   成から出力された最上位出力（Ｐ＿２＾ｎ、Ｇ＿２＾ｎ
   ）と新しい各出力に対して演算を実行するために配置す
   る操作 に従って接続されていることを特徴とする請求項１〜３
   のいずれか１項に記載の装置。
5. （５）上記第２の演算器（４１ｂ）が、４入力Ｘ＿ｘ、
   Ｙ＿ｘ、Ｘ＿ｙ、Ｙ＿ｙに対して演算を行って、以下の
   関係式 Ｘ＿ｚ＝Ｘ＿ｘ■Ｘ＿ｙ Ｙ＿ｚ＝Ｙ＿ｘ■Ｙ＿ｚ によってこれら入力と関係付けられた２出力Ｘ＿ｚ、Ｙ
   ＿ｚを供給する第２のタイプの複数の論理モジュール（
   Ｍ＿２）で構成され、これら第２のタイプの論理モジュ
   ール（Ｍ＿２）はピラミッド構造に配置されており、そ
   の底辺の入力には、できる限り２つずつ取られて、 Ｙ＝Ｇ＿１■Ｇ＿２■．．．■Ｇ＿ｉ■．．．■Ｇ＿ｍ
   ＿−＿１Ｘ＝Ｐ＿１■Ｐ＿２■．．．■Ｐ＿ｉ■．．．
   ■Ｐ＿ｍ＿−＿１を計算するように配置された第１の演
   算器（４１、４２、４３、４４）からの出力Ｐ＿ｉ、Ｇ
   ＿ｉが入力されることを特徴とする請求項４に記載の装
   置。
6. （６）２つの２進数（Ａ、Ｂ）の和（Ｓ）から取り出さ
   れたｍビットからなる少なくとも１つのグループに関係
   したパリテイビット（ＰＳ）を計算する装置であって、
   請求項１〜５のいずれか１項に記載の計算装置と、上記
   ２進数（Ａ、Ｂ）から取り出されたグループのパリテイ
   ビットＰＡとＰＢを導入するための「排他的ＯＲ」の回
   路（５、６）を備え、−第１の演算器（４１ａ）の任意
   の１つの出力Ｇ＿ｉを、上記追加回路（５、６）によっ
   て実行された演算ＰＡ■ＰＢ■Ｇ＿ｉの結果で置換する
   か、あるいは −第１の演算器（４１ａ）の任意の２つの出力Ｇ＿ｉと
   Ｇ＿ｊを、それぞれ演算ＰＡ■Ｇ＿ｉと演算ＰＢ■Ｇ＿
   ｊの結果で置換するように構成されていることを特徴と
   する装置。（７）上記「排他的ＯＲ」の追加回路（５、
   ６）が、互いにカスケード接続されることになる第１の
   タイプのモジュール（Ｍ＿１）と「排他的ＯＲ」モジュ
   ールの最大数が上記「排他的ＯＲ」の追加回路（５、６
   ）の導入によって増加しないように構成されていること
   を特徴とする請求項６に記載の装置。