(57)【特許請求の範囲】
【請求項１】
ｎビット幅のパリティビット付き加算入力A[0:n-1,P]とB[0:n-1,P]とキャリーインCinとから、予測パリティビット付き加算値S[0:n-1,P]を求める全加算器におけるパリティ予測回路において、
前記予測パリティビットS[P]は、前記加算入力のパリティビットA[P]、B[P]と、各桁へのキャリービットc[ｉ] （但しｉは０〜n-1の整数）の排他的論理和であるキャリーフォーパリティCPnと、の排他的論理和により生成され、
ジェネレーションビットg[ i ]は、前記加算入力A[i]とB[i]の両方が１のとき１になり、いずれかが０のときに０になり、
プロパゲーションビットp [i]は、前記加算入力A[i]とB[i]のいずれかが１のとき１になり、両方が０のときに０になり、
前記キャリーフォーパリティCPnの演算式は、
CPn＝Cin＜cp[n,1], cp[n,0]＞
で表されるものとし（但し、Ｓ＜Ｘ，Ｙ＞は、Ｓ＝１の時はＸを、Ｓ＝０の時はＹを出力するものとし、更に、cp[n,1]は前記キャリーインCin＝１の時のキャリーフォーパリティCPnを、cp[n,0]は前記キャリーインCin＝０の時のキャリーフォーパリティCPnをそれぞれ示すものとする。）、
前記パリティ予測回路は、
前記キャリーインCin＝０及び１の場合のキャリーフォーパリティCP[k-1,0]及びCP[k-1,1]を入力とし（但しｋはｎ以下の整数）、加算入力A[k-1]とB[k-1]とのジェネレーションビットg[k-1]に応じて、前記入力CP[k-1,0]またはCP[k-1,1]のいずれかをキャリーフォーパリティcp[k,0]として出力する第１のセレクタと、前記キャリーフォーパリティCP[k-1,0]及びCP[k-1,1]を入力とし、前記加算入力A[k-1]とB[k-1]とのプロパゲーションビットp[k-1]に応じて、前記入力CP[k-1,0]またはCP[k-1,1]のいずれかをキャリーフォーパリティcp[k,1]の反転信号として出力する第２のセレクタとを有する演算ユニットを有し、
当該演算ユニットが複数段、縦列に接続され、
更に、最終段に、キャリーインCinに応じて、キャリーフォーパリティcp[n,0]またはcp[n,1]のいずれかをキャリーフォーパリティCPnとして出力する最終段セレクタを有することを特徴とするパリティ予測回路。
【請求項２】
請求項１において、
前記演算ユニットの第１及び第２のセレクタの出力が、後段の演算ユニットの入力として供給されるように縦列に接続されることを特徴とするパリティ予測回路。
【請求項３】
請求項２において、
前記各演算ユニットは、前記第２のセレクタの出力に接続されたインバータを有することを特徴とするパリティ予測回路。
【請求項４】
請求項１において、
前記第１、第２及び最終段のセレクタが、前記ジェネレーションビットg[k-1]、プロパゲーションビットp[k-1]、キャリーインビットCinを制御信号とするパストランジスタ回路で構成されていることを特徴とするパリティ予測回路。
【請求項５】
４ビット幅のパリティビット付き入力A[0:3,P]とB[0:3,P]とキャリーインCinとから、予測パリティビット付き加算値S[0:3,P]を求める全加算器におけるパリティ予測回路において、
前記予測パリティビットS[P]は、前記入力のパリティビットA[P]、B[P]と、各桁へのキャリービットc[ｉ] （但しｉは０〜3の整数）の排他的論理和であるキャリーフォーパリティCP4との排他的論理和により生成され、
ジェネレーションビットg[i]は、前記加算入力A[i]とB[i]の両方が１のとき１になり、いずれかが０のときに０になり、
プロパゲーションビットp [i]は、前記加算入力A[i]とB[i]のいずれかが１のとき１になり、両方が０のときに０になり、
前記パリティ予測回路は、前記キャリーフォーパリティCP4を生成する回路を有し、
当該キャリーフォーパリティCP4生成回路は、
前記加算入力A[1]とB[1]のジェネレーションビットg[1]またはプロパゲーションビットp[1]の反転信号のいずれかを、前記加算入力A[2]とB[2]のジェネレーションビットg[2]に応じて選択して出力する第１のセレクタと、
前記ジェネレーションビットg[1]またはプロパゲーションビットp[1] の反転信号のいずれかを、前記加算入力A[2]とB[2]のプロパゲーションビットp[2]に応じて選択して出力する第２のセレクタと、
前記第１のセレクタの出力または前記第２のセレクタの出力の反転信号のいずれかを、前記加算入力A[3]とB[3]のジェネレーションビットg[3]に応じて選択して出力する第３のセレクタと、
前記第１のセレクタの出力または前記第２のセレクタの出力の反転信号のいずれかを、前記加算入力A[3]とB[3]のプロパゲーションビットp[3]に応じて選択して出力する第４のセレクタと、
前記第３のセレクタの出力または前記第４のセレクタの出力の反転信号のいずれかを、前記キャリーインCinに応じて選択して、前記キャリーフォーパリティCP4として出力する最終段セレクタとを有することを特徴とするパリティ予測回路。
【請求項６】
請求項５において、
更に、前記第２及び第４のセレクタの出力に接続されたインバータを有することを特徴とするパリティ予測回路。
【請求項７】
請求項５において、
前記セレクタは、制御信号に応じていずれか一方の入力を通過させるパストランジスタ回路により構成されることを特徴とするパリティ予測回路。
【請求項８】
ｎビット幅のパリティビット付き入力A[0:n-1,P]とB[0:n-1,P]とキャリーインCinとから、予測パリティビット付き加算値S[0:n-1,P]を求める全加算器におけるパリティ予測回路において、
前記予測パリティビットS[P]は、前記入力のパリティビットA[P]、B[P]と、各桁へのキャリービットc[ｉ] （但しｉは０〜n-1の整数）の排他的論理和であるキャリーフォーパリティCPnとの排他的論理和により生成され、
ジェネレーションビットg[i]は、前記加算入力A[i]とB[i]の両方が１のとき１になり、いずれかが０のときに０になり、
プロパゲーションビットp [i]は、前記加算入力A[i]とB[i]のいずれかが１のとき１になり、両方が０のときに０になり、
前記パリティ予測回路は、前記キャリーフォーパリティCPnを生成する回路を有し、
当該キャリーフォーパリティCPn生成回路は、
前記加算入力A[1]とB[1]のジェネレーションビットg[1]またはプロパゲーションビットp[1] の反転信号のいずれかを、前記加算入力A[2]とB[2]のジェネレーションビットg[2]に応じて選択して出力する第５のセレクタと、
前記ジェネレーションビットg[1]またはプロパゲーションビットp[1] の反転信号のいずれかを、前記加算入力A[2]とB[2]のプロパゲーションビットp[2]に応じて選択して出力する第６のセレクタと、
第2k-3（但しｋは４〜nの整数）のセレクタの出力または第2k-2のセレクタの出力の反転信号のいずれかを、前記加算入力A[k-1]とB[k-1]のジェネレーションビットg[k-1]に応じて選択して出力する第2k-1のセレクタと、
前記第2k-3のセレクタの出力または前記第2k-2のセレクタの出力の反転信号のいずれかを、前記加算入力A[k-1]とB[k-1]のプロパゲーションビットp[k-1]に応じて選択して出力する第2kのセレクタとを有し、
前記第2k-1のセレクタと第2kのセレクタとが、ｋ＝４〜nまで繰り返し縦列に接続され、
更に、前記第2n-1のセレクタの出力または前記第2nのセレクタの出力の反転信号のいずれかを、前記キャリーインCinに応じて選択して、前記キャリーフォーパリティCPnとして出力する最終段セレクタを有することを特徴とするパリティ予測回路。
【請求項９】
請求項８において、
更に、前記第2k-2および第2kのセレクタの出力にそれぞれ接続されたインバータを有することを特徴とするパリティ予測回路。
【請求項１０】
請求項８において、
前記第2k-3、2k-2、2k-1、2k（ｋ＝４〜ｎ）のセレクタは、制御信号に応じていずれか一方の入力を通過させるパストランジスタ回路により構成されることを特徴とするパリティ予測回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、全加算器に併設されるパリティ予測回路に関し、特に、入力数や素子数を減らした新規なパリティ予測回路に関する。
【０００２】
【従来の技術】
半導体集積回路の様々な箇所に全加算器が内蔵される。全加算器は、所定ビット（所定桁）の入力Ａ、Ｂと下位からのキャリインCinとから、加算値ＳとキャリアウトCoutを生成する。最も一般的な全加算器は、１つのブロックが４ビットの入力A[0:3]、B[0:3]と１ビットのキャリインCinとから、４ビットの加算値S[0:3]と１ビットのキャリアウトCoutを生成する。本明細書では、説明の都合上、ｎビットの値に対して最上位ビット（ＭＳＢ）を第０ビット（または第０桁）、最下位ビット（ＬＳＢ）を第n-1ビット（または第n-1桁）とする。
【０００３】
更に、例えば、所定のメモリから読み出されたデータA[0:3]、B[0:3]が、所定の伝送路を伝播して全加算器に入力され、加算結果が更に別の伝送路に出力されるなど、入力データが所定の伝送路を伝播し、出力データも別の伝送路を伝播する場合は、入力データにパリティビットが付加される。そして、これらのパリティビットが持つ伝播中のビット反転の有無という情報を、加算出力のパリティビットにもそのまま持たせるために、全加算回路に加えて、パリティ予測回路が設けられる。パリティ予測回路は、２つの入力データのパリティビットと加算演算での各桁でのキャリーとの排他的論理和を求めることにより、予測されたパリティビットを生成する。
【０００４】
全加算器やパリティ予測回路では、入力データA[0:3]、B[0:3]から求められるジェネレーション（generation）ｇと、プロパゲーション（propagation）ｐと、ハーフサム（halfsome）ｈとが前段で生成され、それらｇ、ｐ、ｈから加算値Ｓ[0:3]や予測パリティビットS[P]を生成する論理回路が構成される。
【０００５】
尚、パリティ付きデータ演算回路が、以下の特許文献１に記載されている。
【０００６】
【特許文献１】
特開平４−２８８６２９号公報
【０００７】
【発明が解決しようとする課題】
しかしながら、予測パリティビットを生成するパリティ予測回路は、理論的に求められる予測パリティビットの演算式をそのままNANDやNORの論理ゲートに置き換えた構成を取るため、入力数が多くなり、論理ゲート数も多くなり、回路が大規模化する傾向にある。特に、入力データの桁数が増えると、その回路規模は指数関数的に増大することになり、高集積化の弊害になっている。
【０００８】
そこで、本発明の目的は、少ない回路規模で予測パリティビットを生成するパリティビット予測回路を提供することにある。
【０００９】
【課題を解決するための手段】
上記の目的を達成するために、本発明の一つの側面によれば、ｎビット幅の全加算器に含まれるパリティ予測回路のキャリーフォーパリティCPnを求める回路が、制御信号に応じていずれか一方の入力を選択する複数のセレクタで構成される。
【００１０】
今、ｎビット幅の全加算器が、加算入力A[0:n-1,P]とB[0:n-1,P]と下位からのキャリーインCinとから、加算値S[0:n-1,P]を求めるとすると、その論理式は、
S[0:n-1,P]＝A[0:n-1,P]＋B[0:n-1,P]＋Cin
となる。この場合の予測パリティS[P]を求める論理式は、
S[P]＝A[P]ｖB[P]ｖCPn
CPn＝c[0]ｖc[1]ｖ．．．ｖc[n-1]
但し、A[P]、B[P]は入力Ａ，Ｂのパリティビット、c[i]は第ｉビットの下位ビットからのキャリーイン、CPnはキャリーフォーパリティ、ｖは排他的論理和である。そして、前提としてキャリーフォーパリティCPnは、
CPn＝Cin＜cp[n,1], cp[n,0]＞
で表されるものとする。但し、Ｓ＜Ｘ，Ｙ＞は、（Ｓ・Ｘ）｜（〜Ｓ・Ｙ）を示すものとし、入力Ｘ，Ｙに対して、Ｓ＝１の時はＸを、Ｓ＝０の時はＹを出力するセレクタに対応する。また、cp[n,1]はキャリーインCin＝１の時のｎビットに対するキャリーフォーパリティCPnを、cp[n,0]はキャリーインCin＝０の時のｎビットに対するキャリーフォーパリティCPnをそれぞれ示すものとする。つまり、cp[n,1]、cp[n,0]のｎはビット数を示す。
【００１１】
以上の前提で、演算すると、次の演算式が求められる。
【００１２】
cp[n,0] =  (g[n-1]<cp[n-1,1], cp[n-1,0]>)
cp[n,1] = 〜(p[n-1]<cp[n-1,1], cp[n-1,0]>)
cp[n-1,0] =  (g[n-2]<cp[n-2,1], cp[n-2,0]>)
cp[n-1,1] = 〜(p[n-2]<cp[n-2,1], cp[n-2,0]>)
．．．．．．．．
cp[4,0] = (g[3]<cp[3,1], cp[3,0]>)
cp[4,1] = 〜(p[3]<cp[3,1], cp[3,0]>)
cp[3,0] = (g[2]<cp[2,1], cp[2,0]>)
cp[3,1] = 〜(p[2]<cp[2,1], cp[2,0]>)
cp[2,0] = (g[1]<cp[1,1], cp[1,0]>) = g[1]
cp[2,1] = 〜(p[1]<cp[1,1], cp[1,0]>) = 〜p[1]
cp[1,0] = 0（= Cin）
cp[1,1] = 1（= Cin）
そこで、上記の演算式に従えば、本発明のパリティ予測回路は、キャリーインCin＝０及び１の場合のキャリーフォーパリティCP[k-1,0]及びCP[k-1,1]を入力とし（但しｋはｎ以下の整数）、加算入力A[k-1]とB[k-1]とのジェネレーションビットg[k-1]に応じて、前記入力CP[k-1,0]またはCP[k-1,1]のいずれかをキャリーフォーパリティcp[k,0]として出力する第１のセレクタと、前記キャリーフォーパリティCP[k-1,0]及びCP[k-1,1]を入力とし、前記加算入力A[k-1]とB[k-1]とのプロパゲーションビットp[k-1]に応じて、前記入力CP[k-1,0]またはCP[k-1,1]のいずれかをキャリーフォーパリティcp[k,1]の反転信号として出力する第２のセレクタとを有する演算ユニットを有し、
当該演算ユニットが複数段、縦列に接続され、
最終段に、キャリーインCinに応じて、キャリーフォーパリティcp[n,0]またはcp[n,1]のいずれかをキャリーフォーパリティCPnとして出力する最終段セレクタを更に有することを特徴とするパリティ予測回路である。
【００１３】
上記のパリティ予測回路によれば、２個のセレクタを有する演算ユニットを縦列に接続することで構成されるので、少ない素子数で構成することが可能になる。
【００１４】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態例を説明する。しかしながら、本発明の保護範囲は、以下の実施の形態例に限定されるものではなく、特許請求の範囲に記載された発明とその均等物にまで及ぶものである。
【００１５】
図１は、本実施の形態に適用される全加算器とパリティ予測回路とを示す図である。この例では、パリティビット付きの４ビットの入力A[0:3,P]、B[0:3,P]と、下位からのキャリインCinとから、予測パリティビット付きの４ビットの加算値S[0:3,P]とキャリアウトCoutとが生成される。即ち、この全加算器の演算式は、
S[0:3,P] = A[0:3,P] + B[0:3,P] + Cin
である。
【００１６】
前述したとおり、前提として、４ビットのデータの最下位ビット（ＬＳＢ）は「３」、最上位ビット（ＭＳＢ）は「０」で表される。従って、ｎ＋１ビットのデータの場合は、最下位ビットが「ｎ」で、最上位ビットが「０」で表される。また、本明細書では、反転記号として「〜」を利用する。
【００１７】
前段階として、４ビットの入力A[0:3]、B[0:3]の各ビットに対して、それぞれプロパゲーションp[0:3]と、ジェネレーションg[0:3]と、ハーフサムh[0:3]とが、それぞれプロパゲーション生成回路Ｐ、ジェネレーション生成回路Ｇ、ハーフサム生成回路Ｈとで生成される。ここで、プロパゲーションp[0:3]と、ジェネレーションg[0:3]と、ハーフサムh[0:3]とは、次の論理式により求められる。
【００１８】
p[0:3] = A[0:3] | B[0:3]      （｜は論理和（OR））
g[0:3] = A[0:3] ・ B[0:3]    （・は論理積（AND））
h[0:3] = A[0:3] v B[0:3]      （ｖは排他的論理和（EOR））
即ち、プロパゲーションｐは、入力Ａ，Ｂのいずれかが「１」の時に「１」になり、両方とも「０」の時に「０」になる。つまり、プロパゲーションｐとは、下位ビットからのキャリー（桁上げ）が発生したときは、その桁上げを上位ビットに伝播するか（ｐ＝１）、伝播しないか（ｐ＝０）を示すビットである。例えば、ｎ番目のビットのデータＡ[n]，Ｂ[n]のプロパゲーションp[n]が「１」の場合は、下位のｎ＋１ビットからキャリーがあれば、上位のｎ−１ビットにキャリーが発生するが、プロパゲーションp[n]が「０」の場合は、下位のｎ＋１ビットからキャリーが発生しても、上位のｎ−１ビットにはキャリーは発生しない。
【００１９】
ジェネレーションｇは、入力Ａ，Ｂの両方が「１」の時に「１」になり、いずれかが「０」の時に「０」になる。つまり、ジェネレーションｇとは、下位ビットからのキャリーが発生しなくても、その桁で上位ビットへのキャリーを発生するか（ｇ＝１）、発生しないか（ｇ＝０）を示すビットである。例えば、ｎ番目のビットのデータＡ[n]，Ｂ[n]のジェネレーションg[n]が「１」の場合は、下位のｎ＋１ビットからキャリーなくても、上位のｎ−１ビットにキャリーが発生するが、ジェネレーションg[n]が「０」の場合は、下位のｎ＋１ビットからキャリーがなければ、上位のｎ−１ビットにはキャリーは発生しない。
【００２０】
また、ハーフサムｈは、入力Ａ，Ｂが異なる時に「１」となり、同じ時に「０」になる。つまり、ハーフサムｈとは、入力Ａ，Ｂの加算結果を示すビットである。例えば、ｎ番目のビットにおいて、A[n]とB[n]とが１，０または０，１の時は、ハーフサムh[n]は「１」になり、A[n]とB[n]とが０，０または１，１の時は、ハーフサムh[n]は「０」になる。
【００２１】
従って、加算値生成回路１０は、次の演算式による排他的論理和回路で構成されて、加算値S[0:3]を生成する。
【００２２】
S[0] = h[0] v c[0]
S[1] = h[1] v c[1]
S[2] = h[2] v c[2]
S[3] = h[3] v c[3]
ここで、c[0],c[1],c[2],c[3]は、各ビットへのキャリーイン（桁上げ）のビットであり、これらのキャリービットｃは、キャリー生成回路１６で生成される。キャリー生成回路１６は、次の演算式による論理回路で構成される。
【００２３】
0004230234.tif 000002
即ち、最下位ビット（第３ビット）へのキャリーインc[3]は、下位からのキャリインCinである（式（１））。また、次の第２ビットへのキャリーインc[2]は、最下位ビットのジェネレーションg[3]がg[3]＝１か、プロパゲーションp[3]がp[3]＝１で且つキャリーインCinがCin＝１の時に発生する（式（２））。更に、第１ビットへのキャリーインc[1]は、第２ビットのジェネレーションg[2]がg[2]＝１か、プロパゲーションp[2]がp[2]＝１でありかつ第２ビットへのキャリーインc[2]がc[2]＝１の時に発生する（式（３））。この式（３）に式（２）を代入すると、上記式（４）が求められる。
【００２４】
同様に、第０ビット（最上位ビット）へのキャリーインc[0]は、第１ビットのジェネレーションg[1]がg[1]＝１か、プロパゲーションp[1]がp[1]＝１でありかつ第１ビットへのキャリーインc[1]がc[1]＝１の時に発生する（式（５））。この式（５）に式（４）を代入すると、上記式（６）が求められる。
【００２５】
上記から理解されるとおり、キャリーインの一般式は、次の通りである。
【００２６】
c[n]＝g[n+1] | (p[n+1] ・ c[n+1]))
従って、キャリーアウト生成回路１２は、次の演算式の論理回路で構成される。
【００２７】
Cout＝g[0] | (p[0] ・ c[0]))
さて、加算値とキャリーアウトを求める回路と共に、入力データＡ，Ｂのパリティビットから予測パリティビットを求める回路が設けられる。この回路は、ＣＰ（Carry for Parity）生成回路１８と、予測パリティ生成回路１４とからなる。入力データＡ，ＢのパリティビットA[P]、B[P]の不良の有無を示す情報をそのまま加算値ＳのパリティビットS[P]にも伝播させる予測パリティビットS[P]は、次の演算式で求められることが知られている。
【００２８】
S[P] = A[P] v B[P] v CP4                          (7)
ここで、CP4は、各ビット（各桁）での桁上げによるパリティビットへの影響を示すビットであり、キャリーフォーパリティ（パリティビットのキャリー）と称される。このキャリーフォーパリティCP4は、各ビット（各桁）へのキャリーインc[0],c[1],c[2],c[3]が何回発生したかを示すビットであり、次の一般的に知られた演算式により求められる。
【００２９】
CP4  = c[0] v c[1] v c[2] v c[3]                    (8)
つまり、排他的論理和ｖは、「１」の時反転し、「０」の時反転しないことと等価であるので、結局、キャリフォーパリティCP4は、各桁へのキャリーインの回数が奇数（CP4=0）か偶数（CP4=1)かを示すビットデータである。
【００３０】
上記式（８）に上記式（１）（２）（４）（６）をそれぞれ代入して展開すると、次の通りである。
【００３１】
0004230234.tif 000003
この演算式（９）は、キャリーインCinが「０」の場合と「１」の場合とに区分して構成されているが、それぞれの演算式は、前段階で生成されるジェネレーションｇとプロパゲーションｐの反転、非反転ビットを入力とする論理回路で構成可能である。この演算式は、一般的に知られている。
【００３２】
図２は、キャリーフォーパリティ生成回路１８の論理回路図である。この論理回路図は、演算式（９）をそのまま論理回路に展開している。即ち、NANDゲート２０〜２３とそれらの出力のNANDゲート２４とで、AND回路とＯＲ回路とが生成され、演算式（９）のCin＝０の場合の項が演算される。また、NANDゲート２５〜２８とそれらの出力のNANDゲート２９とで、AND回路とＯＲ回路とが生成され、演算式（９）のCin＝１の場合の項が演算される。そして、セレクタ３０が、ゲート２４，２９の出力を、Cin＝１の時とCin＝０の時とに応じて、選択する。
【００３３】
図２のキャリーフォーパリティ生成回路１８は、演算式（９）をそのまま論理回路に展開した構成になっている。この生成回路１８は、３入力のゲート２０〜２３、２５〜２８を８個、４入力のゲート２４，２９を２個、そして、セレクタ３０を有する。３入力のNANDゲートは、CMOS回路で構成されると６トランジスタを必要とする。また、４入力のNANDゲートは、CMOS回路で構成されると８トランジスタを必要とする。従って、図２の回路では、NANDゲートだけで６４個のトランジスタを必要とし、セレクタ３０が４トランジスタで構成されるとすると、全部で６８個のトランジスタを必要とする。これが６ビット、８ビットと入力データのビット数が大きくなると、そのトランジスタの個数は指数関数的に増大することになり、高集積化を阻害する要因になる。
【００３４】
そこで、本発明者は、パストランジスタ回路のみによるキャリーフォーパリティ生成回路を新たに発明した。パストランジスタとは、逆相のコントロールビットに応じて、２つの入力の一方を選択するセレクタであり、CMOS回路で構成すると、逆相のコントロールビットが使用可能状態であれば、４個のトランジスタで実現できる。
【００３５】
図３は、CMOS回路で構成されたパストランジスタの回路図の一例を示す図である。パストランジスタ回路は、一種のセレクタであり、制御信号Ｓが「１」の時に入力Ａを出力Ｘとして選択し、制御信号Ｓが「０」の時に入力Ｂを出力Ｘとして選択する。第１のトランスファーゲートを構成するＮチャネルトランジスタＮ１とＰチャネルトランジスタＰ１は、制御信号ＳがＨレベル（Ｓ＝１）の時に入力Ａを通過させる。また、第２のトランスファーゲートを構成するＮチャネルトランジスタＮ２とＰチャネルトランジスタＰ２は、制御信号ＳがＬレベル（Ｓ＝０）の時に入力Ｂを通過させる。そこで、このようなパストランジスタ回路で構成されるセレクタＳＥＬを、図３に示されるように表記することにする。
【００３６】
そして、出力Ｘの演算式として、次のような表記を採用することにする。
【００３７】
Ｘ＝（Ｓ・Ａ）｜（〜Ｓ・Ｂ）＝Ｓ＜Ａ，Ｂ＞          （１０）
この演算式は、Ｘが、Ｓ＝１のときにＡ、Ｓ＝０のときにＢであることを示す。この演算式は、入力Ａ，Ｂ、制御信号Ｓからなるセレクタに対応する。
【００３８】
そこで、キャリーフォーパリティＣＰを求める演算式を、上記の演算式（１０）を利用して表記することで、図３のパストランジスタ回路によるセレクタを利用してキャリーフォーパリティ発生回路１８を構成することができる。
【００３９】
更に新たな表記方法として、ｎビットに対するキャリーフォーパリティＣＰｎを、下位からのキャリインCin＝０or１に対して、cp[n,0]、cp[n,1]と表すことにする。こうすることにより、次のように式（１０）の形式で表すことができる。
【００４０】
CPn＝Cin＜cp[n,1]，cp[n,0]＞                          （１１）
この式は、前述の式１０と同等であり、図３のパストランジスタ回路により実現可能である。
【００４１】
図４は、キャリーフォーパリティを説明する図である。図４を参照しながら、１ビット〜４ビット及びｎビットに対するキャリーフォーパリティＣＰ１〜ＣＰ４、ＣＰ４について説明すると共に、その再帰性について説明する。ｎビットに対しては、最上位を第０ビット、最下位を第n-1ビットとしたことに伴い、図４では、ビット数が増加するたびに第１ビット、第２ビット、第３ビット．．．第n-1ビットと最下位ビットが付加されるように表記される。このように表記することで、キャリーフォーパリティの再帰性の説明が容易になる。
【００４２】
図４（１）は１ビット（１桁）の場合であり、１ビットの場合は、前述の式８に示したとおり、キャリーフォーパリティCP1は、下位からのキャリーCinがあるかないかによって決まる。つまり、CP1＝c[0]＝Cinであるので、結局、１桁の場合のキャリーフォーパリティCP1は、次の式群（１２）の通りである。
【００４３】
CP1＝Cin＜cp[1,1]，cp[1,0]＞＝Cin＜１，０＞
cp[1,0] ＝０
cp[1,1] ＝１                                          （１２）
図４（２）は２ビット（２桁）の場合である。２ビットの場合は、１ビットの第０桁に対してキャリーが発生するか否かと考えることにより、２ビットのキャリーフォーパリティCP2を１ビットのキャリーフォーパリティCP1のcp[1,1]，cp[1,0]を利用して表現することができる。つまり、キャリーインCin＝０の場合は、最下位の第１ビットにキャリー（桁上げ）が発生するか否かを示すジェネレーションg[1]が、上位の１ビット（第０ビット）に対するキャリーインCinに対応するので、
cp[2,0]＝g[1]<cp[1,1],cp[1,0]>
更に、キャリーインCin＝１の場合は、そのキャリーインによる最下位の第１ビットでの反転と、最下位の第１ビットのプロパゲーションp[1]が、上位の１ビット（第０ビット）に対するキャリーインCinに対応することとを考慮すると、
cp[2,1]＝〜p[1] <cp[1,1],cp[1,0]>
となる。
【００４４】
以上をまとめると、２桁の場合のキャリーフォーパリティCP2は、以下の式群（１３）の通りである。
【００４５】
CP2＝Cin＜cp[2,1]，cp[2,0]＞
cp[2,0]＝g[1]＜cp[1,1]，cp[1,0]＞＝g[1]
cp[2,1]＝〜（p[1]＜cp[1,1]，cp[1,0]＞）＝〜p[1]              （１３）
図４（３）は３ビット（３桁）の場合である。３ビットの場合は、２ビットの第０、１桁に対してキャリーが発生するか否かと考えることにより、３ビットのキャリーフォーパリティCP3を２ビットのキャリーフォーパリティCP2のcp[2,1]，cp[2,0]を利用して表現することができる。つまり、キャリーインCin＝０の場合は、最下位の第２ビットにキャリー（桁上げ）が発生するか否かを示すジェネレーションg[2]が、上位の２ビット（第０、１ビット）に対するキャリーインCinに対応するので、
cp[3,0]＝g[2]<cp[2,1],cp[2,0]>
更に、キャリーインCin＝１の場合は、そのキャリーインによる最下位の第２ビットでの反転と、最下位の第２ビットのプロパゲーションp[2]が、上位の２ビット（第０、１ビット）に対するキャリーインCinに対応することを考慮すると、
cp[3,1]＝〜p[2] <cp[2,1],cp[2,0]>
となる。
【００４６】
従って、３桁の場合のキャリーフォーパリティCP3は、以下の式群（１４）の通りである。
【００４７】
0004230234.tif 000004
図４（４）は４ビット（４桁）の場合である。４ビットの場合は、２ビットの第０〜２桁に対してキャリーが発生するか否かと考えることにより、４ビットのキャリーフォーパリティCP4を３ビットのキャリーフォーパリティCP3のcp[3,1]，cp[3,0]を利用して表現することができる。つまり、キャリーインCin＝０の場合は、最下位の第３ビットにキャリー（桁上げ）が発生するか否かを示すジェネレーションg[3]が、上位の３ビット（第０〜２ビット）に対するキャリーインCinに対応するので、
cp[4,0]＝g[3]<cp[3,1],cp[3,0]>
更に、キャリーインCin＝１の場合は、そのキャリーインによる最下位の第３ビットでの反転と、最下位の第３ビットのプロパゲーションp[3]が、上位の３ビット（第０〜２ビット）に対するキャリーインCinに対応することを考慮すると、
cp[4,1]＝〜p[3] <cp[3,1],cp[3,0]>
となる。
【００４８】
結局、４桁の場合のキャリーフォーパリティCP4は、以下の式群（１５）の通りである。
【００４９】
CP4＝Cin＜cp[4,1]，cp[4,0]＞
cp[4,0] = (g[3]<cp[3,1], cp[3,0]>)
= g[3]< (p[2]・p[1]｜〜p[2]・〜g[1])，(g[2]・〜p[1]｜〜g[2]・g[1]) >
= (g[3] ・ p[2] ・ p[1])  | (g[3] ・ 〜p[2] ・ 〜g[1]) |
(〜g[3] ・ g[2] ・ 〜p[1]) | (〜g[3] ・ 〜g[2] ・ g[1])  (if Cin = 0)
cp[4,1] = 〜(p[3]<cp[3,1], cp[3,0]>)
= 〜(p[3]< (p[2]・p[1]｜〜p[2]・〜g[1])，(g[2]・〜p[1]｜〜g[2]・g[1])>)
= (p[3] ・ p[2] ・ 〜p[1]) | (p[3] ・ 〜p[2] ・ g[1]) |
(〜p[3]・ g[2] ・ p[1]) | (〜p[3] ・ 〜g[2] ・ 〜g[1])   (if Cin = 1)  （１５）
この展開式は前述の式（９）と一致している。
【００５０】
図４（５）はｎビットに一般化した場合を示し、上記と同様の再帰性を利用すると、ｎビットの全加算器でのキャリーフォーパリティCPnは、
CPn = Cin<cp[n,1], cp[n,0]>
cp[n,0] =  (g[n-1]<cp[n-1,1], cp[n-1,0]>)
cp[n,1] = 〜(p[n-1]<cp[n-1,1], cp[n-1,0]>)                     （１６）
上記の式（１２）〜（１６）を並べて記載すると、再帰的な関係を有していることが理解される。
【００５１】
cp[n,0] =  (g[n-1]<cp[n-1,1], cp[n-1,0]>)
cp[n,1] = 〜(p[n-1]<cp[n-1,1], cp[n-1,0]>)
cp[n-1,0] =  (g[n-2]<cp[n-2,1], cp[n-2,0]>)
cp[n-1,1] = 〜(p[n-2]<cp[n-2,1], cp[n-2,0]>)
．．．．．．．．
cp[4,0] = (g[3]<cp[3,1], cp[3,0]>)
cp[4,1] = 〜(p[3]<cp[3,1], cp[3,0]>)
cp[3,0] = (g[2]<cp[2,1], cp[2,0]>)
cp[3,1] = 〜(p[2]<cp[2,1], cp[2,0]>)
cp[2,0] = (g[1]<cp[1,1], cp[1,0]>) = g[1]
cp[2,1] = 〜(p[1]<cp[1,1], cp[1,0]>) = 〜p[1]
cp[1,0] = Cin = 0
cp[1,1] = Cin = 1                                        （１７）
図５は、キャリーフォーパリティCPnを求める論理回路図である。この論理回路は、上記式群（１６）をセレクタSEL1、SEL2、SELeと、インバータ４０とで構成している。各セレクタは、図３のパストランジスタ回路がそれぞれ利用される。つまり、セレクタSELeが次の式に対応し、
CPn = Cin<cp[n,1], cp[n,0]>
セレクタSEL1が次の式に対応し、
cp[n,0] =  (g[n-1]<cp[n-1,1], cp[n-1,0]>)
セレクタSEL2が次の式に対応する。
【００５２】
cp[n,1] = 〜(p[n-1]<cp[n-1,1], cp[n-1,0]>)
そして、図５の回路からセレクタSELeを除いた部分が、ユニット回路UNITnを構成する。このユニット回路は、ｎを減じて、より前段のユニット回路を構成することができる。
【００５３】
図６は、前段のユニット回路を示す図である。つまり、図５の前段には、ユニット回路UNITn-1が、その前段にはユニット回路UNITn-2が構成される。そして、ｎ＝３のユニット回路まで展開すると、ｎビット幅の全加算器のためのキャリーフォーパリティCPnを求める論理回路が完成する。
【００５４】
図７は、４ビット幅の全加算器用のキャリーフォーパリティCP4を生成する回路１８の論理回路である。この回路では、２段のユニット回路UNIT3、UNIT4と、最終段のキャリーインCinを制御信号とするセレクタSELeとで構成され、前述の式（１７）のcp[4,0],cp[4,1]、cp[3,0],cp[3,1]が、セレクタ１２、１３及び１０、１１により求められる。従って、この論理回路は、各セレクタSEL10〜SEL13、SELeで４個のトランジスタ、各インバータ４１，４２で２個のトランジスタの、合計で２４個のトランジスタで構成可能である。尚、各セレクタの制御信号g[1],g[2],g[3],p[1],p[2],p[3]とその反転信号は、図１のプロパゲーション生成回路Ｐ、ジェネレーション生成回路Ｇでそれぞれ生成されているものとする。
【００５５】
図７の出力であるキャリーフォーパリティ信号CP4は、図１に示されるとおり、予測パリティ生成回路１４に入力され、入力データＡ，ＢのパリティビットA[P]とB[P]との排他的論理和が求められて、加算値の予測パリティS[P]が生成される。つまり、本実施の形態のパリティ予測回路は、ＣＰ生成回路１８と予測パリティ生成回路１４とで構成される。そして、予測パリティ生成回路１４は、排他的論理和演算をすればよいので、この排他的論理和回路も、周知のとおり、セレクタを組み合わせることで構成可能である。
【００５６】
図８は、４ビット幅の全加算器用のキャリーフォーパリティCP4を生成する回路１８の論理回路の変形例である。図７の回路では、セレクタSEL10とSEL12とSELeとが縦列に接続されている。従って、図８の回路では、伝搬信号の波形成形のために、各ユニットUNIT3,4の境界に波形成型用のバッファ４３，４５が設けられる。同様に、セレクタSEL11、SEL13、SELeの信号伝搬経路にも、波形成型用のバッファ４４，４６が設けられる。但し、この経路には、インバータ４１，４２が設けられているので、これらのバッファ４４，４６を省略することもできる。
【００５７】
図９は、図７のキャリーフォーパリティ生成回路をｎビット幅まで拡張した論理回路である。この回路でも複数段のユニット回路UNIT3〜nが縦列に接続される。ユニット回路UNIT1、UNIT2とは、図７のユニット回路UNIT3,4に対応する。つまり、ユニットUNITkが、ｋ＝３〜nまで繰り返され、最終段のセレクタ回路SELeには、ユニットUNITnのセレクタの出力が入力される。
【００５８】
即ち、図９のキャリーフォーパリティ生成回路は、
加算入力A[1]とB[1]のジェネレーションビットg[1]またはプロパゲーションビットp[1] の反転信号のいずれかを、加算入力A[2]とB[2]のジェネレーションビットg[2]に応じて選択して出力する第５のセレクタSEL5と、
ジェネレーションビットg[1]またはプロパゲーションビットp[1] の反転信号のいずれかを、加算入力A[2]とB[2]のプロパゲーションビットp[2]に応じて選択して出力する第６のセレクタSEL6と、を有する第３のユニットUNIT3を有する。
【００５９】
そして、第2k-3（但しｋは１〜n-3の整数）のセレクタの出力または第2k-2のセレクタの出力の反転信号のいずれかを、加算入力A[k-1]とB[k-1]のジェネレーションビットg[k-1]に応じて選択して出力する第2k-1のセレクタと、
前記第2k-3のセレクタの出力または前記第2k-2のセレクタの出力の反転信号のいずれかを、前記加算入力A[k-1]とB[k-1]のプロパゲーションビットp[k-1]に応じて選択して出力する第2kのセレクタと、を有する第kのユニットUNITkが、ｋ＝３〜nまで繰り返し縦列に接続される。即ち、第３のユニットUNIT3〜第nのユニットUNITnが、縦列に接続される。
【００６０】
更に、最終段のユニットUNITnの第2n-1のセレクタの出力または第2nのセレクタの出力の反転信号のいずれかを、キャリーインCinに応じて選択して、キャリーフォーパリティCPnとして出力する最終段セレクタSELeを有する。
【００６１】
図９の論理回路においても、各ユニット間には、図８のようにバッファゲートを設けて、波形成形を行うことが好ましい。また、各セレクタが、パストランジスタで構成されることで、信号伝播を高速化して、キャリーフォーパリティビットCPnの生成を高速化することができる。
【００６２】
以上のとおり、本実施の形態でのキャリーフォーパリティ信号生成回路は、少ない素子数と少ない入力数で構成することができる。従って、全加算器のパリティ予測回路を、少ない入力数、素子数で構成することができる。しかも、セレクタにパストランジスタを利用することで、高速にキャリーフォーパリティ信号を生成することができる。
【００６３】
以上、実施の形態例をまとめると以下の付記の通りである。
【００６４】
（付記１）ｎビット幅のパリティビット付き加算入力A[0:n-1,P]とB[0:n-1,P]とキャリーインCinとから、予測パリティビット付き加算値S[0:n-1,P]を求める全加算器におけるパリティ予測回路において、
前記予測パリティビットS[P]は、前記加算入力のパリティビットA[P]、B[P]と、各桁へのキャリービットc[ｉ] （但しｉは０〜n-1の整数）の排他的論理和であるキャリーフォーパリティCPnと、の排他的論理和により生成され、
前記キャリーフォーパリティCPnの演算式は、
CPn＝Cin＜cp[n,1], cp[n,0]＞
で表されるものとし（但し、Ｓ＜Ｘ，Ｙ＞は、Ｓ＝１の時はＸを、Ｓ＝０の時はＹを出力するものとし、更に、cp[n,1]は前記キャリーインCin＝１の時のキャリーフォーパリティCPnを、cp[n,0]は前記キャリーインCin＝０の時のキャリーフォーパリティCPnをそれぞれ示すものとする。）、
前記パリティ予測回路は、
前記キャリーインCin＝０及び１の場合のキャリーフォーパリティCP[k-1,0]及びCP[k-1,1]を入力とし（但しｋはｎ以下の整数）、加算入力A[k-1]とB[k-1]とのジェネレーションビットg[k-1]に応じて、前記入力CP[k-1,0]またはCP[k-1,1]のいずれかをキャリーフォーパリティcp[k,0]として出力する第１のセレクタと、前記キャリーフォーパリティCP[k-1,0]及びCP[k-1,1]を入力とし、前記加算入力A[k-1]とB[k-1]とのプロパゲーションビットp[k-1]に応じて、前記入力CP[k-1,0]またはCP[k-1,1]のいずれかをキャリーフォーパリティcp[k,1]の反転信号として出力する第２のセレクタとを有する演算ユニットを有し、
当該演算ユニットが複数段、縦列に接続され、
更に、最終段に、キャリーインCinに応じて、キャリーフォーパリティcp[n,0]またはcp[n,1]のいずれかをキャリーフォーパリティCPnとして出力する最終段セレクタを有することを特徴とするパリティ予測回路。
【００６５】
（付記２）付記１において、
前記演算ユニットの第１及び第２のセレクタの出力が、後段の演算ユニットの入力として供給されるように縦列に接続されることを特徴とするパリティ予測回路。
【００６６】
（付記３）付記２において、
前記各演算ユニットは、前記第２のセレクタの出力に接続されたインバータを有することを特徴とするパリティ予測回路。
【００６７】
（付記４）付記２において、
前記各演算ユニットは、後段の演算ユニットとの間に、バッファゲートを有することを特徴とするパリティ予測回路。
【００６８】
（付記５）付記１において、
前記第１、第２及び最終段のセレクタが、前記ジェネレーションビットg[k-1]、プロパゲーションビットp[k-1]、キャリーインビットCinを制御信号とするパストランジスタ回路で構成されていることを特徴とするパリティ予測回路。
【００６９】
（付記６）４ビット幅のパリティビット付き入力A[0:3,P]とB[0:3,P]とキャリーインCinとから、予測パリティビット付き加算値S[0:3,P]を求める全加算器におけるパリティ予測回路において、
前記予測パリティビットS[P]は、前記入力のパリティビットA[P]、B[P]と、各桁へのキャリービットc[ｉ] （但しｉは０〜3の整数）の排他的論理和であるキャリーフォーパリティCP4との排他的論理和により生成され、
前記パリティ予測回路は、前記キャリーフォーパリティCP4を生成する回路を有し、
当該キャリーフォーパリティCP4生成回路は、
前記加算入力A[1]とB[1]のジェネレーションビットg[1]またはプロパゲーションビットp[1]の反転信号のいずれかを、前記加算入力A[2]とB[2]のジェネレーションビットg[2]に応じて選択して出力する第１のセレクタと、
前記ジェネレーションビットg[1]またはプロパゲーションビットp[1] の反転信号のいずれかを、前記加算入力A[2]とB[2]のプロパゲーションビットp[2]に応じて選択して出力する第２のセレクタと、
前記第１のセレクタの出力または前記第２のセレクタの出力の反転信号のいずれかを、前記加算入力A[3]とB[3]のジェネレーションビットg[3]に応じて選択して出力する第３のセレクタと、
前記第１のセレクタの出力または前記第２のセレクタの出力の反転信号のいずれかを、前記加算入力A[3]とB[3]のプロパゲーションビットp[3]に応じて選択して出力する第４のセレクタと、
前記第１のセレクタの出力または前記第２のセレクタの出力の反転信号のいずれかを、前記キャリーインCinに応じて選択して、前記キャリーフォーパリティCP4として出力する最終段セレクタとを有することを特徴とするパリティ予測回路。
【００７０】
（付記７）付記６において、
更に、前記第２及び第４のセレクタの出力に接続されたインバータを有することを特徴とするパリティ予測回路。
【００７１】
（付記８）付記６において、
前記セレクタは、制御信号に応じていずれか一方の入力を通過させるパストランジスタ回路により構成されることを特徴とするパリティ予測回路。
【００７２】
（付記９）ｎビット幅のパリティビット付き入力A[0:n-1,P]とB[0:n-1,P]とキャリーインCinとから、予測パリティビット付き加算値S[0:n-1,P]を求める全加算器におけるパリティ予測回路において、
前記予測パリティビットS[P]は、前記入力のパリティビットA[P]、B[P]と、各桁へのキャリービットc[ｉ] （但しｉは０〜n-1の整数）の排他的論理和であるキャリーフォーパリティCPnとの排他的論理和により生成され、
前記パリティ予測回路は、前記キャリーフォーパリティCPnを生成する回路を有し、
当該キャリーフォーパリティCPn生成回路は、
前記加算入力A[1]とB[1]のジェネレーションビットg[1]またはプロパゲーションビットp[1] の反転信号のいずれかを、前記加算入力A[2]とB[2]のジェネレーションビットg[2]に応じて選択して出力する第５のセレクタと、
前記ジェネレーションビットg[1]またはプロパゲーションビットp[1] の反転信号のいずれかを、前記加算入力A[2]とB[2]のプロパゲーションビットp[2]に応じて選択して出力する第６のセレクタと、
第2k-3（但しｋは４〜nの整数）のセレクタの出力または第2k-2のセレクタの出力の反転信号のいずれかを、前記加算入力A[k-1]とB[k-1]のジェネレーションビットg[k-1]に応じて選択して出力する第2k-1のセレクタと、
前記第2k-3のセレクタの出力または前記第2k-2のセレクタの出力の反転信号のいずれかを、前記加算入力A[k-1]とB[k-1]のプロパゲーションビットp[k-1]に応じて選択して出力する第2kのセレクタとを有し、
前記第2k-1のセレクタと第2kのセレクタとが、ｋ＝４〜nまで繰り返し縦列に接続され、
更に、前記第2n-1のセレクタの出力または前記第2nのセレクタの出力の反転信号のいずれかを、前記キャリーインCinに応じて選択して、前記キャリーフォーパリティCPnとして出力する最終段セレクタを有することを特徴とするパリティ予測回路。
【００７３】
（付記１０）付記９において、
更に、前記第2kのセレクタの出力にそれぞれ接続されたインバータを有することを特徴とするパリティ予測回路。
【００７４】
（付記１１）付記９において、
前記セレクタは、制御信号に応じていずれか一方の入力を通過させるパストランジスタ回路により構成されることを特徴とするパリティ予測回路。
【００７５】
【発明の効果】
以上、本発明によれば、全加算器のパリティ予測回路を、少ない入力数、素子数で構成することができる。
【図面の簡単な説明】
【図１】本実施の形態に適用される全加算器とパリティ予測回路とを示す図である。
【図２】キャリーフォーパリティ生成回路１８の論理回路図である。
【図３】  CMOS回路で構成されたパストランジスタの回路図の一例を示す図である。
【図４】キャリーフォーパリティを説明する図である。
【図５】キャリーフォーパリティCPnを求める論理回路図である。
【図６】前段のユニット回路を示す図である。
【図７】４ビット幅の全加算器用のキャリーフォーパリティCP4を生成する回路１８の論理回路である。
【図８】４ビット幅の全加算器用のキャリーフォーパリティCP4を生成する回路１８の論理回路の変形例である。
【図９】ｎビット幅の全加算器用のキャリーフォーパリティCPｎを生成する回路１８の論理回路である。
【符号の説明】
SEL  セレクタ、UNIT  ユニット、ｇ  ジェネレーションビット、ｐ  プロパゲーションビット、ｈ  ハーフサムビット、Ａ，Ｂ  加算入力、Ｓ  加算値、Cin キャリーイン、CPn  キャリーフォーパリティ
【図１】
0004230234.tif 000005
【図２】
0004230234.tif 000006
【図３】
0004230234.tif 000007
【図４】
0004230234.tif 000008
【図５】
0004230234.tif 000009
【図６】
0004230234.tif 000010
【図７】
0004230234.tif 000011
【図８】
0004230234.tif 000012
【図９】
0004230234.tif 000013