(57)【要約】【課題】本発明はポピュレーションカウント回路に関し、動作の高速化、設計の簡易化、専用設計による演算器（ＡＬＵ）以外への転用を容易にして汎用性を持たせることができるようにする。【解決手段】‘１’か‘０’かのいずがれかの状態をとる複数のビット線のうち、それが‘１’になっているものが幾つあるかを計数するのに、４ビット入力、３ビット出力で構成される桁上げ保存加算器である４−３ＣＳＡを用いて構成したポピュレーションカウント回路であって、４−３ＣＳＡを、２の累乗ビットのポピュレーションカウント回路の回路構成の初段で並べて用いた。【選択図】        図１
2005165793.tif 000002
【特許請求の範囲】
【請求項１】
‘１’か‘０’かのいずがれかの状態をとる複数のビット線のうち、それが‘１’になっているものが幾つあるかを計数するのに、４ビット入力、３ビット出力で構成される桁上げ保存加算器である４−３ＣＳＡを用いて構成したポピュレーションカウント回路であって、
前記４−３ＣＳＡを、２の累乗ビットのポピュレーションカウント回路の回路構成の初段で並べて用いることを特徴とするポピュレーションカウント回路。
【請求項２】
前記２の累乗ビットのポピュレーションカウント回路の回路構成は、最上位ビットの生成において、全ビットの論理積を取ることで高速化を図ることを特徴とする請求項１記載のポピュレーションカウント回路。
【請求項３】
前記２の累乗ビットのポピュレーションカウント回路の回路構成は、上位２ビット目の生成においては、上位３ビット目部分和からの、キャリーアウト全ての論理和を取ることで高速化を図ることを特徴とする請求項１記載のポピュレーションカウント回路。
【請求項４】
前記４−３ＣＳＡを、乗算回路の部分和を求める回路に用いたことを特徴とする請求項１記載のポピュレーションカウント回路。
【請求項５】
前記４−３ＣＳＡを、大きなビット構成となる２の累乗ビット（２n ビット，ｎ≧４）のポピュレーションカウント回路の回路構成の２段目で並べて用いることを特徴とする請求項１記載のポピュレーションカウント回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、‘１’か‘０’かのいずがれかの状態をとる複数のビット線のうち、それが‘１’になっているものが幾つあるかを、並列に、かつ高速に計数するポピュレーションカウント（population count）回路（以下、単に「ＰＯＰＣ」とも記す）に関する。
【背景技術】
【０００２】
(1) ：従来例１の説明
以下、非特許文献１を従来例１として説明する。従来例１は、５４ビット規則化ワラストリー（Wallace Tree）乗算器の例であり、該従来例１には、５−３ＣＳＡ（非特許文献１では“４Ｗ”とよばれる回路が示されている）に関する先行技術が開示されている。以下、詳細に説明する。
【０００３】
（規則化乗算器の構造）
図１２は従来例１のワラスツリー乗算器（従来型）を示す図、図１３は従来例１の規則化ワラストリー乗算器を示す図、図１４は従来例１の７Ｄ4 ユニット、図１５は従来例１の乗算器全体ブロック図、図１６は従来例１の４入力加算器（４Ｗ）を示す。
【０００４】
５４ビット乗算器では、ブース（Booth ）のアルゴリズム［１］を用いることにより、２７個の部分積と符号不拡張処理［２］のための項１個、合計２８の項を加算する必要がある。この処理を、従来からあるワラスツリー乗算器［３］で行った例を図１２に示す。これはフルアダー（３Ｗ）のみを使用したものである。
【０００５】
この配線構造には規則性がなく、適当な回路ユニットを単位として全体を構成することができない。このため従来から知られているように、この構造では設計工数が掛かり、特にビット巾の広い乗算器を設計する時には大きな問題となっていた。
【０００６】
今回提案するツリー構造を図１３に示す。ここでは３入力加算器である３Ｗと４入力加算器（４Ｗ）を組み合わせて使っている。このツリーは次のようにして構成されている。先ず、加算すべき項数を２分割し、それをさらに２分割し、というプロセスを経て、最終的に加算すべき項数が３〜５となるようにし、これを最小ユニットとする。
【０００７】
２分割できないときには、最近接する整数に分割するものとする。次に、分割を遡って、各階層を３Ｗ（１ビット全加算器）と４Ｗ（４入力加算器）を用いて構成していく。
【０００８】
図１３の例では、３と４の項が最小ユニットとなり、それぞれを３Ｗと４Ｗで加算し、さらに各ユニットの加算を４Ｗで行っている。この構造は規則性が高く、繰り返しの単位（例えば、図１３の７Ｄ）を見つけ易い。４Ｗを用いた乗算器の例はいくつか報告されているが［４，５］部分積の数が２n の時にのみ最適かつ規則的となる構成であり、一般によく使われる１６、３２、２４、５４、６４ビットの乗算器にブースのアルゴリズムを適用したケースでは、ダミー回路の増加など不利な点がある。今回提案したツリーの分割方式は、任意のビット巾に対して適用可能であり、規則的に回路を構成することが可能である。
【０００９】
次に、４ビット分の７Ｄユニット回路（７Ｄ4 ）を図１４に示す。これは論理の単位になると共に、レイアウト設計をする上でも単位となるものである。バッティングにより回路を構成する時に重要となるのは、ユニットのレイアウト設計において端子を何処に置くかということである。
【００１０】
図１４では、被乗数（ａi ）、ブースデコーダの出力信号（Ｂj ）、４Ｗの中間キャリー（ｄij）、中間サム（ｓij）、キャリー（ｃij）全ての端子がバッティングにより接続できるように考慮されており、横方向のユニット間の配線は必要ない。
【００１１】
この例では、ブースセレクタ（Ｐ）と対応する加算器が縦一列に近接して配置されているが、この配置はツリー全体のネットの混雑度緩和及びクリティカルパスの高速化に効果がある。もしこれらを別々に配置した場合には、Ｐと３Ｗは４Ｗの間のネット数が膨大になり、回路の高速性が減殺されることになる。
【００１２】
従来の乗算器の設計においては、全ツリー部を通じて被乗数信号（ａi ）を上位桁方向（上下）にシフトして桁合わせしていた。このユニットでは、中間サムとキャリーの両方の信号を、左右両方向にシフトさせて桁合わせし、被乗数信号のシフトは同一最小ユニット内でのみ行っている。これは乗算器全体の外形を矩形に近いものにするためである。また、クリティカルパスの配線長をバランスさせる効果もあるので、回路の高速化にも寄与する。
【００１３】
次に、ツリー全体を図１５に示す。７Ｄ4 ユニット４行と、それらの出力を加算するため４Ｗ4 行で全体が構成されており、図１３のツリー構造と対応している。図ではWire Shifterは桁合わせのためのものであるが、同一のシフタの中では、全てのサム信号が同一のシフト量、全てのキャリー信号も同一のシフト量をそれぞれ持つので、この部分も規則的に設計することが出来る。
【００１４】
また、４Ｗに入力される信号は、ユニットの設計の時と同じ思想で、左右両方向にシフトしており、クリティカルパスの高速化を図っている。最後に、今回用いた４Ｗ回路を図１６に示す。この回路のアイディアは既にいくつかの報告がある［３、４］。中間キャリーを用いて、見かけ上４つの数を２つの数の和にする回路である。
【００１５】
この回路はフルアダー２個を直列につなぐことによっても実現できるが、最適化を行うことによってトランジスタ数の削減と高速化が図れる。図１６はその一例である。
【００１６】
(2) ：従来例２の説明
以下、非特許文献２を従来例２として説明する。図１７は従来例２の説明図であり、Ａ図はＲＣＡによる遅延イメージ、Ｂ図はＲＣＡ遅延の改善イメージを示す図である。従来例２は「乗算器を高速化するテクニック」に関する内容である。
【００１７】
(1) ：キャリ信号を待たずに加算するＣＳＡ
では、ＡＳＩＣのように回路構造に制限がなく、動作速度の制約が厳しい場合はどうでしようか。構造の基本的な違いは、partial product を多ビットの数ととらえて加算するのではなく、ビット単位で加算するということです。そして、ここで大事な手法が「キャリ・セーブ・アダー（以下ＣＳＡ）」と言われるものです。
【００１８】
図１７のＡ図に、加算器を４段連結した場合が示されている。２〜４段目の加算器では遅延量がフル・アダー１段分しかないにもかかわらず、初段ではＲＣＡ特有の大きな遅延が存在しています。これをなんとか図１７のＢ図のようにできないか、というのがＣＳＡの考えかたです。
【００１９】
ＲＣＡの速度がなぜ遅いかというと、上位のけたが、下位から順繰りに上がってくるキャリを持たなければならないからです。２項の加算では、キャリが上がってくるのを確認しなければ答えが出たことになりませんし、ＣＬＡであってもその条件は変わりありません。
【００２０】
しかし多項の加算では、加算が繰り返し行われるのが前提となるので、「今結果が出ているものだけを加算し、結果が出ていないものは次回の加算にまわそう」という考え方が適用できます。つまり「キャリを持たない」ということです。これがＣＳＡの名前の由来でもあります。
【００２１】
ＣＳＡは本来、複数項の加算を高速に処理するための回路です。ですから、ここから先は乗算器に話を限定せず、複数項の加算の高速化について述べていきましよう。ＣＳＡについては文献によって表現の内容に差があるようです。筆者がこれまで遭遇した説明は、以下の４通りくらいでしようか。
【００２２】
・多ビットの２項を加算したときのキャリ（最上位）を保存しておくタイプ
・１ビットの加算（フル・アダーなどによる）を行ったときのキャリを保存しておくタイプ
・キャリの保存を、レジスタなどの記憶素子に保存することと解釈するタイプ
・キャリの保存を次段の加算にまわすことと解釈するタイプ
それぞれが相反するタイプというわけではないので、組み合わせた説明も可能ですが、ここでは「フル・アダーなどによる１ビットの加算によって生じたキャリを次段の加算に回し、キャリ伝播時間の節約を図った加算法」をＣＳＡと呼ぶことにします。
【００２３】
そしてこれを実現するために、フル・アダーやハーフ・アダーを木の枝状に接続したのものが、よく知られている「Wallace ツリー」です。以下ではＣＳＡ＝Wallace ツリーとし、これを用いて多項を２項にまとめ、２項をＣＬＡで加算し、１項を出力する構造について説明していきます。
【００２４】
ＣＳＡの適用を「多項を２項にまとめるまで」とした理由は明快で、「２項の加算ではキャリが上がってくることを確認しなければ答えが出たことにならない」という、すでに述べた基本則があるからです。言い換えれば、キャリを先送りしてまでやるべき処理がなくなったということです。
【００２５】
また、２項をＣＬＡで加算する理由は、「代わりにＲＣＡを用いても正しい答えは得られるのだが、ＣＳＡは多項の加算を高速化するためのものなので、わざわざ最後に遅い加算器を使うのでは意味がない」ということからです。
【００２６】
(3) ：従来例３（演算器以外での計数回路の従来技術）の説明
図１８は従来例３のユースドカウンタ例である。また、図１９は従来例３のユースドカウンタの機能説明図である。以下、図１８、図１９に基づき、ＰＯＰＣ（ポピュレーションカウント）命令演算器以外での計数回路の従来技術を従来例３として説明する。
【００２７】
◎：演算器以外での計数回路の説明（図１８参照）
従来、ＰＯＰＣ命令演算器でない他の計数回路においては、計数されるべきビット線の変化情報を抽出し、それを計数する加減算回路付きのカウンタ「以下これをユースドカウンタ（Used-counter）と記す」が知られていた。このユースドカウンタの１例を図１８に示す。
【００２８】
図１８に示したように、ユースドカウンタは、フリップフロップ回路（ＦＦ）からなるカウンタ１と、減算器２と、加算器３とで構成されている。そして、減算器２はカウンタ１のＱ出力と外部からの「解放されたキューの数」との減算を行い、その結果を出力する。加算器３では、減算器２の出力と外部からの「新たに使用されるキューの数」との加算を行い、その結果を出力する。カウンタ１では加算器３の出力を入力して計数を行う。このような動作を順次行い、加算器３の出力をユースドカウンタの出力として取り出す。
【００２９】
図１８のユースドカウンタ（Used-counter）の場合、回路の信頼性に問題があり、ユースドカウンタにビット化けが起こった場合（間欠故障など）の矛盾点を指摘できず、回路が誤動作してしまう可能性があった。例えば、二つの回路ユニットでハンドシェイクを行うこと協調動作を行う場合を説明する。
【００３０】
共用で用いる資源を互いにユースドカウンタによって管理していた場合、片側のユースドカウンタが１つだけ少なくなってしまうような故障が起きた場合、両者の意思が一致しなくなる。しかし、その矛盾が分かるのは、少なくなったカウンタがマイナスになろうとするか、或いは相手のカウントがオーバーフローするかの時に限られてしまう。それを防ぐためには別の保護回路を設けなければならない。
【００３１】
また、ユースドカウンタにしているがために、資源の新規確保／解放ができる数に制限が設けられて、そのために性能が頭打ちになることもあった。例えば、近年のスーパースカラ／アウトオブオーダー方式の計算機では、同時に処理できる能力（Peak性能) が性能の重要な要因であるが、この上限がユースドカウンタで１サイクルで取り扱える能力によって定まってしまうことすらあった。
【００３２】
◎：ユースドカウンタによる従来技術の機能の説明（図１９参照）
図１８の回路の説明を簡単にするため、原始的なキューモデルについて図１９を参照しながら説明する。
【００３３】
図１９のモデルでは、機能ブロックＡが要求を発行する側であり、機能ブロックＢはその要求を受けて処理を行う。受けられるようキュー数は最大で８個などと決まっており、従来技術では、Ａ側で発行する時にユースドカウンタをカウントアップ、また、Ｂ側で処理を終わる毎に、Ａ側に対し終了報告を行い、Ａ側ではそれを受けてユースドカウンタをカウントダウンする。従って、カウンタが８になるまではＡから要求を発行してもよい。このユースドカウンタの問題点は端的に以下の通りである。
【００３４】
・キューの増減数の制約（高速動作とトレードオフ）
一般の制御回路で使用されるため、多くの場合サイクル毎に動作を求められ、ゆえにユースドカウンタ回路は１サイクルで動作することが求められる。すなわち、ユースドカウンタ回路の加算器と減算器を含めて「１サイクル動作」をするように設計されていることが求められる。
【００３５】
従って、特に高クロック動作を要求される回路では、加算／減算可能な入力数を制限することで「１サイクル動作」をさせざるをえない事態がある。つまり、変化量がユースドカウンタの動作制限によって制限されてしまう。これを解決するには、別の手段（本発明にかかるポピュレーションカウント回路）を使用するしかない。
【００３６】
・信頼性の問題
ユースドカウンタが故障した場合を考える。本来ならＡとＢでの思惑は一致し、Ｂで３つのキューを使用している状態ならＡのユースドカウンタも３を指し示すはずである。ところが、ノイズなどでユースドカウンタが化けてしまった場合、Ａのユースドカウンタは３以外を指し示すことがあり得る。ところが、この場合でも互いに思惑が一致していないことに気がつかずにしばらく動作を続けてしまう。
【００３７】
気が付くとすれば、ユースドカウンタが０なのにＢから解放通知がくる場合か、若しくはユースドカウンタが８になっていないのにＢのキューがあふれてしまう場合である。つまり、少なくとも故障は将来的に問題が表面化する。
【００３８】
簡単なモデルでは、思惑が一致せずとも実害が出るまでそのまま放置しても良さそうに思われるが、現実の装置ではこの間に何が起こるか分からない。従って、故障（間欠的なものを含む）はできる限りその瞬間に見つけることが求められる。
【００３９】
(4) ：従来例４（ポピュレーションカウント回路の従来技術）の説明
図２０は従来例４の１６ビットポピュレーションカウント回路例である。以下、図２０を参照しながら従来例４を説明する。
【００４０】
一般的に用いられている３ビットＣＳＡ（３−２ Carry Save Adder ：フルアダーと同じ）の他に、「５ビットＣＳＡ（５−３−ＣＳＡ）」と呼ぶ加算器がある（非特許文献１参照）。特に乗算器では多入力少出力のＣＳＡを用いて演算器を構成する部分積の和を生成するのに効率的であるため、このようなものが考えられていた。
【００４１】
特に、乗算の部分和の入力ビットに比べて出力すべき幅は少ない。例えば、ｎビットの乗算器の場合、ｎ2 ビットの入力に対して２ｎビットの出力を得る（３２ビット乗算器であれば１０２４→６４）。従って、効率良く部分和を集約できるＣＳＡを用いれば高速な回路になると信じられている。
【００４２】
例えば、３ビット→２ビットであれば２／３＝６６．７％に集約できているし、５ビット→３ビットであれば３／５＝６０％に集約できている。実際にキャリー生成など正しい演算を行う都合などで以下の通り数字では実現できないが、全て５−３ＣＳＡを用いれば、１０２４×（３／５）x を解いてｘ＝６（端数切り上げ）となり、６段、５−３ＣＳＡ総数は、
【００４３】
【数１】
2005165793.tif 000003
個で出来る可能性を持つことが分かる。これが３−２ＣＳＡだけの場合は最低でも７段、９６７個のＣＳＡが必要となる。このように集約率が高いＣＳＡは高速かつコンパクトにワラスツリーを構成できることが期待できる。    
【００４４】
ところが、今日の乗算器（又は乗算回路）などでは、その入力ビット長が２n あるいは２の高次巾を因数に含むようなビット数であることが多い。しかし、２n は３や５とは互いに素であるから、３−２ＣＳＡ、５−３ＣＳＡをワラスツリーの構成の初段に用いると、半端が生じてしまいバランスに欠く。
【００４５】
例えば、図２０の１６ビットポピュレーションカウント回路例において、１６ビットの入力があると、初段は５−３ＣＳＡ３個とすると１ビット半端になってしまうので、入力ピンが対称に見えるような回路設計はできない。そのため、従来はワラスツリー回路を構成するのに専門技能を要求されていた。
【００４６】
特に、３−２ＣＳＡ、５−３ＣＳＡのいずれも中間キャリー入力Ｃi は他の入力ピンと比べ、出力までのディレイ（遅延）が短く設計されるので、入力ピン間のディレイバランスの崩れは顕著となる。この中で高速な回路を設計するためには、もっともクリティカルなディレイパスを最適化する、すなわち全入力ピンが同じように高速にするような設計が要求されるのである。
【００４７】
(5) ：従来例５（ポピュレーションカウント演算器の従来技術）の説明
以下、ポピュレーションカウント演算器の従来技術を従来例５として説明する。ところで、乗算器以外、例えばプロセッサのＰＯＰＣ（ポピュレーションカウント）命令の実行においては、ソフトウェア（ファームウェアやマイクロコード等）によるエミュレーションに頼ったり、マルチサイクル動作による解決（Shift やincrement 等）を図っていた。或いは、ＰＯＰＣ演算器を乗算器と共用する方法が知られているが、これを他の一般制御回路に適用しようとすると、演算処理は不要であるから回路の無駄が多い。
【００４８】
前記Shift やincrement 方式による従来技術は次の通りである。すなわち、ｉ［１］〜ｉ［１６］の入力の１６ビットポピュレーションカウントの場合、以下の基本構成になるものを指す。
ｘ＝０；
ｆｏｒ（ｊ＝１；ｊ＜＝１６；ｊ++）  ｘ＝ｘ＋ｉ［ｊ］；  ／／ｉｎｃｒｅｍｅｎｔ  ｏｒ  ｎｏｔ．
なお、応用例として、複数ビットを一度に処理してループ回数を減らすものも公知である。この構成の場合、少なくともループ回数だけの時間が計算に必要であり、速度が要求される場合に適用できない。
【００４９】
また、これをハードウェアで実現する場合には、ループ計算中は、同じ回路を用いて並列に別のポピュレーションカウントはできない（パイプライン実行はできない）ため、遅延時間だけでなく、演算スループットの上でも問題がある。
【００５０】
非特許文献１
情報処理学会研究報告，学術刊行物，情処研報Ｖｏｌ．９２．Ｎｏ．４８，社団法人  情報処理学会発行，１９９２年６月１２日，ＩＰＳＪ  ＳＩＧ  Ｎｏｔｅｓ，９２−ＡＲＣ−９４，Ｐ２５〜Ｐ３１，「５４ビット規則化ワラストリー（Wallace Tree）乗算器」（佐藤他、富士通研究所）の欄を参照
非特許文献２
「Ｄｅｓｉｇｎ  Ｗａｖｅ  Ｍａｇａｚｉｎｅ」，２００２年８月号，ＣＱ出版株式会社発行、Ｐ１２７〜Ｐ１２８，「高速な数値演算回路の設計を考える」第３回，特に、「乗算器を高速化するテクニック」の欄を参照
【発明の開示】
【発明が解決しようとする課題】
【００５１】
(1) ：従来例３では次のような課題がある。
【００５２】
・キューの増減数の制約の問題
前記のように、ユースドカウンタ回路の加算器と減算器を含めて「１サイクル動作」をするように設計されていることが求められる。従って、特に高クロック動作を要求される回路では、加算／減算可能な入力数を制限することで「１サイクル動作」をさせざるを得ない事態がある。つまり、変化量がユースドカウンタの動作制限によって制限されてしまう。これを解決するには、別の手段を使用するしかない。
【００５３】
・信頼性の問題
前記のように、ユースドカウンタが故障した場合、例えば、ノイズなどでユースドカウンタが化けてしまった場合、Ａのユースドカウンタは３以外を指し示すことがあり得る。ところが、この場合でも互いに思惑が一致していないことに気がつかずにしばらく動作を続けてしまう。
【００５４】
気が付くとすれば、ユースドカウンタが０なのにＢから解放通知がくる場合か、若しくはユースドカウンタが８になっていないのにＢのキューがあふれてしまう場合である。つまり、少なくとも故障は将来的に問題が表面化する。
【００５５】
簡単なモデルでは、思惑が一致せずとも実害が出るまでそのまま放置しても良さそうに思われるが、現実の装置ではこの間に何が起こるか分からない。従って、故障（間欠的なものを含む）はできる限りその瞬間に見つけることが求められる。
【００５６】
(2) ：従来例４の場合、集約率が高いＣＳＡは高速かつコンパクトにワラスツリーを構成できることが期待できるが、今日の乗算器などでは、その入力ビット長が２n あるいは２の高次巾を因数に含むようなビット数であることが多い。しかし、２n は３や５とは互いに素であるから、３−２ＣＳＡ、５−３ＣＳＡをワラスツリーの構成の初段に用いると、半端が生じてしまいバランスに欠く。
【００５７】
(3) ：従来例５の場合、乗算器以外、例えばプロセッサのＰＯＰＣ（ポピュレーションカウント）命令の実行においては、ソフトウェア（ファームウェアやマイクロコード等）によるエミュレーションに頼ったり、マルチサイクル動作による解決（Shift やincrement 等）を図っていた。或いは、ＰＯＰＣ演算器を乗算器と共用する方法が知られているが、これを他の一般制御回路に適用しようとすると、演算処理は不要であるから回路の無駄が多い。
【００５８】
前記Shift やincrement 方式による従来技術は少なくともループ回数だけの時間が計算に必要であり、速度が要求される場合に適用できない。また、これをハードウェアで実現する場合には、ループ計算中は、同じ回路を用いて並列に別のポピュレーションカウントはできない（パイプライン実行はできない）ため、遅延時間だけでなく、演算スループットの上でも問題がある。
【００５９】
本発明は前記課題を解決するため、ポピュレーションカウント回路の動作の高速化、設計の簡易化、ポピュレーションカウント回路の専用設計による演算器（ＡＬＵ）以外への転用を容易にして汎用性を持たせることができるようにすることを目的とする。
【課題を解決するための手段】
【００６０】
本発明は前記の目的を達成するため、次のように構成した。
【００６１】
(1) ：‘１’か‘０’かのいずがれかの状態をとる複数のビット線のうち、それが‘１’になっているものが幾つあるかを計数するのに、４ビット入力、３ビット出力で構成される桁上げ保存加算器である４−３ＣＳＡを用いて構成したポピュレーションカウント回路であって、前記４−３ＣＳＡを、２の累乗ビット（２n ｂｉｔ）のポピュレーションカウント回路の回路構成の初段で並べて用いることを特徴とする。
【００６２】
(2) ：前記(1) のポピュレーションカウント回路において、前記２の累乗ビット（２n ｂｉｔ）のポピュレーションカウント回路の回路構成は、最上位ビットの生成において、全ビットの論理積を取ることで高速化を図ることを特徴とする。
【００６３】
(3) ：前記(1) のポピュレーションカウント回路において、前記２の累乗ビット（２n ｂｉｔ）のポピュレーションカウント回路の回路構成は、上位２ビット目の生成においては、上位３ビット目部分和からの、キャリーアウト全ての論理和を取ることで高速化を図ることを特徴とする。
【００６４】
(4) ：前記(1) のポピュレーションカウント回路において、前記４−３ＣＳＡを、乗算回路の部分和を求める回路に用いたことを特徴とする。
【００６５】
(5) ：前記(1) のポピュレーションカウント回路において、前記４−３ＣＳＡを、大きなビット構成となる２の累乗ビット（２n ビット，ｎ≧４）のポピュレーションカウント回路の回路構成の２段目で並べて用いることを特徴とする。
【００６６】
（作用）
図１は本発明の原理説明図である。以下、図１を参照しながら前記構成の作用を説明する。図１に示したように、本発明のポピュレーションカウント回路で使用している４−３ＣＳＡは、２n ビット入力のポピュレーションカウント回路の初段、２段目に組み込むと効果的である。
【００６７】
なぜならば、従来例で使用していた５−３ＣＳＡや３−２ＣＳＡと違い、４−３ＣＳＡだと２n が４で割り切れるため、入力に半端が生じず、全ての入力が対称に見える初段を構成できる。同様の理由で２段目からのツリー途中までのツリー構成にも使い勝手が良い。このような効果が得られるのは、集約率は多少減少する（３／４＝７５％）が、２レベル上のキャリー出力があるため、クリティカルパスになりやすいキャリー伝搬を高速化できるからである。
【００６８】
すなわち、ｎビット乗算器を構成する場合、最悪の場合、下から２ビット目から最上位出力の２ｎビットへキャリーが存在する。しかしながら、５−３ＣＳＡの場合には１レベル上のキャリー出力しか持たないため、２ｎ−１段の５−３ＣＳＡを通過する長いキャリー伝達パスが必ず生じてしまう。
【００６９】
しかし、本発明の４−３ＣＳＡを用いると、２レベル上のキャリー出力を持つため、（２ｎ−１）／２段の４−３ＣＳＡ通過パスが最長のキャリー伝達パスになり、５−３ＣＳＡの半分の長さですんでしまう。言い換えれば、５−３ＣＳＡより４−３ＣＳＡの方が単位性能で劣っていたとしても十分勝ることができることを示している。従って、集約率で勝る５−３ＣＳＡだけでなく、２レベル上のキャリー出力を持つ４−３ＣＳＡを用いることで、高速なポピュレーションカウント回路を構成できるようになる。
【００７０】
また、ポピュレーションカウント回路の動作の高速化だけでなく、設計の簡易化、ポピュレーションカウント回路の専用設計による演算器（ＡＬＵ）以外への転用を容易にして汎用性を持たせることができる。
【発明の効果】
【００７１】
前記請求項１乃至５によれば次のような効果がある。
【００７２】
(a) ：キャリーチェーンの短縮によるクリティカルパスの高速化が達成可能である。すなわち、本発明のように、４−３ＣＳＡを用いると、２レベル上のキャリー出力を持つため、（２ｎ−１）／２段の４−３ＣＳＡ通過パスが最長のキャリー伝達パスになり、従来使用されていた５−３ＣＳＡの半分の長さですんでしまう。
【００７３】
言い換えれば、従来例の５−３ＣＳＡより本発明の４−３ＣＳＡの方が単位性能で劣っていたとしても十分勝ることができることを示している。従って、集約率で勝る５−３ＣＳＡだけでなく、２レベル上のキャリー出力を持つ４−３ＣＳＡを用いることで、高速なポピュレーションカウント回路を構成できるようになる。
【００７４】
(b) ：初段から２段目などの対称性によるディレイ設計の簡素化が可能である。
【００７５】
すなわち、遅延クリティカルパスと、とても高速なパス（レーシングパス）が混在すると演算結果を受けるフリップフロップ回路のセットアップ／ホールド（Setup/Hold）マージンを確保出来ない可能性がある。つまり、レーシングパスはホールドマージンに影響する。対称回路であることで遅延ばらつきが抑えられるため、セットアップ／ホールド（Setup/Hold）マージンの確保が容易になる。
【００７６】
(c) ：初段（又は初段と２段目）が定型化されることにより、回路の簡易化が可能である。また、３段目以降は相変わらず従来技術相当のツリーが主体となるが、当初規模の約半分程度で済むため、熟練した専門職の技術がなくても対処可能なレベルに抑えることができる。
【００７７】
(d) ：専用設計の実現が可能である。すなわち、乗算器（又は乗算回路）の部分回路のような位置づけではなく、純粋なポピュレーションカウント回路として設計することが可能になる。
【００７８】
(e) ：本発明のポピュレーションカウント回路を用いてワラスツリー型乗算器を構成した場合でも、前記(a) 〜(e) の効果と同様な効果が得られる。
【００７９】
(f) ：ポピュレーションカウント回路の動作の高速化、設計の簡易化、ポピュレーションカウント回路の専用設計による演算器（ＡＬＵ）以外への転用を容易にして汎用性を持たせることができる。
【発明を実施するための最良の形態】
【００８０】
§１：用語等の説明
(1) ：本発明の説明で使用する用語の定義
(a) ：「レベル」とは、「桁」と同じ意味で使用する。
【００８１】
(b) ：集約（率）は、ｎビット×ｎビットの乗算器の場合、計数過程でｎ2 個のビットを適切に加算することで最大２ｎビット長の結果を得る。このｎ2 →２ｎへのビット数の低減を「集約」と称する。例えば、ｎビットのポピュレーションカウントはｎ→（log2ｎ＋１）へと「集約」する。また、集約率はこの集約の割合のことである。
【００８２】
(c) ：ここでいう「故障」は、ハードウェアの物理的な故障だけでなく、ノイズや宇宙線などによる偶発的間欠的なデータ化けを含む。
【００８３】
(d) ：「ワラスツリー（wallace tree）」という用語は、乗算器の分野で一般に使用されている用語であり、ポピュレーションカウント回路の乗算器へ応用（又は適用）したものを「ワラスツリー（wallace tree）型乗算器」などと呼ぶ。従って、本明細書中では、乗算器の説明部分を除いて「ポピュレーションカウント回路」という用語を使用する。
【００８４】
(e) ：ＣＳＡ（carry save adder）とは、桁上げ保存加算器のことを言う。
【００８５】
(2) ：本発明に係るポピュレーションカウント回路の特徴等
(a) ：演算器では演算レイテンシは重要な課題であり、高速化されることに越したことはない。また、一般の制御回路に適用する場合（busy制御など）では、１サイクルで処理することに大きな意味があることがあり、楽に１サイクルに納められると設計コスト（労力）が下がる。このため回路動作の高速化を達成できるようにする。
【００８６】
(b) ：ＣＳＡのツリー回路はディレイチューニングに専門的な技術を要求され、大規模な回路になればなるほど難易度は高くなる。難しい専門技能を要求される回路であると、演算器などの専用回路以外である汎用回路に適用するのは工数上困難である。故に、演算器の専門家でない一般の設計者にも簡単に回路を構成できることが重要になる。このため、設計の簡易化を達成することが求められる。
【００８７】
(c) ：ポピュレーションカウント回路の専用設計により演算器（ＡＬＵ）以外への転用を可能にする。
【００８８】
(d) ：もともとポピュレーションカウント回路として設計者に知られておらず、ワラスツリー（wallace tree）として乗算器設計者にのみ知られていて、従来の適用範囲は非常に狭かった。特定の回路にだけしか適用できない専用回路ではなく、ポピュレーションカウント回路、或いはワラスツリーとして広範囲な可能性を見出したい。このため、回路の汎用性を達成することが特徴である。
【００８９】
§２：ポピュレーションカウント回路の基本的な説明
本発明のポピュレーションカウント回路は高速動作を可能にしており、このポピュレーションカウント回路を用いることで、互いに共有資源のそれぞれの有効フラグを持って、資源数はポピュレーションカウントした結果で管理することができる。そうすると、或る有効フラグが故障した場合には、その資源を使おうとする時点で、対応するその資源に問題があることが判明する。つまり、故障の特定がとても精度良く行うことができるようになるし、故障した時点で判別がつくようになることが期待できる。
【００９０】
この高速な回路を構成するために４−３ＣＳＡが重要な役割を果たす。５−３ＣＳＡと同様な４ビット入力型ポピュレーションカウント回路の基本回路であるが、中間キャリー入力がなく、キャリー出力も異なるものである。前述の通り、このような出力ビット数の多いものがワラスツリー構成に有効であると信じられていなかったが、４−３ＣＳＡを効果的に使うことで高速なポピュレーションカウント回路が実現可能となる。
【００９１】
図１に示したように、４−３ＣＳＡとは、４つの入力のうち値が‘１’となっているものの数を３ビットの２進数で出力する回路（ＣＳＡ）である。その構成は、例えば、４入力のハーフアダーであり、論理構成例を論理式で示すと次のようになる。
【００９２】
今、図１に示した各４−３ＣＳＡの入力をｉ１、ｉ２、ｉ３、ｉ４とし、出力をｓ［２：０］とすると、
【００９３】
【数２】
2005165793.tif 000004
で構成される。以上において、ａｎｄは論理積、ｏｒは論理和、ｘｏｒは排他的論理和、ｎｏｔは論理否定の演算である。
【００９４】
このような４入力ＣＳＡは、２n ビット入力のポピュレーションカウント回路の初段、２段目に組み込むと効果的である。なぜならば、５−３ＣＳＡや３−２ＣＳＡと違い、４−３ＣＳＡだと２n が４で割り切れるため、入力に半端が生じず、全ての入力が対称に見える初段を構成できる（上記の論理式を見てもその対称性は自明である）。同様の理由で２段目からのツリー途中までのツリー構成にも使い勝手が良い。このような効果が得られるのは、集約率は多少減少する（３／４＝７５％）が、２レベル上のキャリー出力があるため、クリティカルパスになりやすいキャリー伝搬を高速化できるからである。
【００９５】
すなわち、ｎビット乗算器を構成する場合、最悪の場合、下から２ビット目から最上位出力の２ｎビットへキャリーが存在する。しかしながら、５−３ＣＳＡの場合には１レベル上のキャリー出力しか持たないため、２ｎ−１段の５−３ＣＳＡを通過する長いキャリー伝達パスが必ず生じてしまう。
【００９６】
しかし、４−３ＣＳＡを用いると、２レベル上のキャリー出力を持つため、（２ｎ−１）／２段の４−３ＣＳＡ通過パスが最長のキャリー伝達パスになり、５−３ＣＳＡの半分の長さですんでしまう。言い換えれば、５−３ＣＳＡより４−３ＣＳＡの方が単位性能で劣っていたとしても十分勝ることことができることを示している。従って、集約率で勝る５−３ＣＳＡだけでなく、２レベル上のキャリー出力を持つ４−３ＣＳＡを用いることで、高速なポピュレーションカウント回路を構成できるようになる。
【００９７】
§３：ポピュレーションカウント回路例の説明
(1) ：１６ビットポピュレーションカウント回路例１の詳細な説明
図２は１６ビットポピュレーションカウント回路例１である。以下、図２に基づいて、１６ビットポピュレーションカウント回路例１を詳細に説明する。
【００９８】
図２に示したように、ポピュレーションカウント回は、‘１’か‘０’かのいずがれかの状態をとる複数のビット線のうち、それが‘１’になっているものが幾つあるかを計数するのに、４ビット入力、３ビット出力で構成される桁上げ保存加算器である４−３ＣＳＡを用いており、前記４−３ＣＳＡを、２の累乗ビット（２n ｂｉｔ）のポピュレーションカウント回路の回路構成の初段で並べて用いている。
【００９９】
そして、二段目のＣＳＡである（* Ｌ２−１）、（* Ｌ０）の入力はそれぞれ対称であり、等ディレイであることが分かる。また、３段目のＣＳＡである（* Ｌ１）も、入力Ｃi を除く入力は同様に等ディレイ（例えば、同じトランジスタ段数）に出来ることが分かる。
【０１００】
このように４−３ＣＳＡを初段に使うことにより、２段目をバランス良く構成することが可能であることが分かる。また、従って、２段目も（* Ｌ２−１）、（* Ｌ０）は４−３ＣＳＡを用いることで後段のポピュレーションカウント回路を構成し易くしている。
【０１０１】
図２では、３段目のＣＳＡである（* Ｌ１）は、入力Ｃi が高速であることをうまく利用するために５−３ＣＳＡを用いたが、４−３ＣＳＡを用いるような構成、或いは他の構成であっても構成可能であり、最適な構成方法は、ＣＳＡの構成方法や用いる環境などに依存して自由に決めることが可能である。
【０１０２】
図２のポピュレーションカウント回路において、２の累乗ビットのポピュレーションカウント回路の回路構成は、上位２ビット目の生成においては、上位３ビット目部分和からの、キャリーアウト全ての論理和（ＯＲ）を取るための論理和回路（* Ｌ２−４）を設けて高速化を図ることを特徴としている。
【０１０３】
ＯＲ回路（* Ｌ２−４）の入力のそれぞれはＸ［４］が１になるときはいずれも１にならない（また、複数が同時に１になることもない）。これは一般に言えることである。従って、Ｘ［３］を求めるには論理和回路（* Ｌ２−４）において、３−２ＣＳＡを用いずとも論理和をとるだけで良い（請求項３の実施形態）。
【０１０４】
また、図２のポピュレーションカウント回路において、２の累乗ビットのポピュレーションカウント回路の回路構成は、最上位ビットの生成において、全ビットの論理積（ａｎｄ）を取ることで高速化を図ることを特徴としている。
【０１０５】
この場合、Ｘ［４］＝１になるのは全入力ビット（Ｉｎ１＝ｉ１〜Ｉｎ１６＝ｉ１６）がすべて１になるときであるから、全入力ビットの論理積、すなわち、それと等価な（* Ｌ２−１）のｓ［２］出力を用いれば良く、わざわざポピュレーションカウント回路（ワラスツリー）の従来の構成（すなわち、ＣＳＡの組み合わせ回路）のような方法を採る必要はない（請求項２の実施形態）。なお、図２において、４−３ＣＳＡの出力であるｓ［２］は、ｓ［２］＝（ｉ１）ａｎｄ（ｉ２）ａｎｄ（ｉ３）ａｎｄ（ｉ４）である。
【０１０６】
(2) ：図２の１６ビットポピュレーションカウント回路例１における各部の説明
ａ：２−２ＨＡ（ハーフアダー）
−  入力ｉ１、ｉ２
−  出力ｃ０、ｓ
−  ｃ０＝ｉ１and ｉ２
−  ｓ＝ｉ１xor ｉ２
ｂ：３−２ＣＳＡ（フルアダーと同じ）
−  入力ｉ１、ｉ２、ｃｉ
論理的には３つとも等価であるが、フルアダーという性格上このように非対称の識別子を使用する。
【０１０７】
−  出力ｃ０、ｓ
−  ｃ０＝（ｉ１and ｉ２）ｏｒ（ｉ２and ｃｉ）ｏｒ（ｉ１and ｃｉ）
−  ｓ＝ｉ１xor ｉ２xor ｃｉ
ｃ：５−３ＣＳＡ
−  入力ｉ１、ｉ２、ｉ３、ｉ４、ｃｉ
特にｃｉを入力とするパスの高速化を主目的として、論理的に以下のように非対称に構成することが普通であるため、非対称の識別子を使用する。
【０１０８】
−  出力ｃ０、ｃ、ｓ
−  ｃ０＝not （（（ｉ３xor ｉ４）and （not ｉ２））ｏｒ（（not （ｉ３xor ｉ４））and （not ｉ４）））
−  ｃ＝（ｃｉand （ｉ１xor ｉ２xor ｉ３xor ｉ４））ｏｒ（ｉ１and （not （ｉ１xor ｉ２xor ｉ３xor ｉ４）））
−  ｓ＝（ｉ１xor ｉ２xor ｉ３xor ｉ４）xor ｃｉ
(3) ：図２の回路動作の補足説明
図３は図２の回路の動作説明図であり、図２の回路に対応する１６ビットポピュレーションカウント回路例１の動作説明を筆算の形で図示したものである。
【０１０９】
図３において、記号ｉ1 〜ｉ16が回路の入力、記号ｓ０a 〜ｓ３j が中間出力、記号Ｘ０〜Ｘ４が出力である。いずれも１ビット線であり０若しくは１の値をとる。図２の回路では、図３に示したような演算をしており、理論的におこなっていることと、本発明の原始的構成は図示の通りである。
【０１１０】
ところで、本発明での基本に忠実（原始的）な組み方をすると、図２ではなく、図４に示したように組まれる。
【０１１１】
(4) ：ポピュレーションカウント回路２の説明
図４は１６ビットポピュレーションカウント回路例２を示した図である。図４に示した１６ビットポピュレーションカウント回路例２において、最初の２段（初段の４つのＣＳＡと、２段目の３つのＣＳＡ）と、ＯＲ回路（* Ｌ２−４）部分が基本に忠実な部分であり、残りがＣＳＡのツリー回路である（完全対称の）１６ビット入力だったものが非対称９入力（うち、２ビットは出力に一致であるから、実質非対称７入力）となり、問題が半分に縮小されている。この部分において本発明の特徴が出ている。
【０１１２】
従って、図２の回路は更なる高速化の一例として示される（使用するテクノロジなどによって図２の回路が必ずしも最高速度となるとは限らず、あくまでも応用例の１つ）。専門知識を有する場合は図２などのような最適化を施すことが考えられるし、一般の設計知識を有する設計者であり、問題解決のために極度の最適化を求められないのであれば、図４の回路のように組んで十分な解である。
【０１１３】
§４：ポピュレーションカウント回路によるキュー使用状況管理の説明
図５はポピュレーションカウント回路によるキュー使用状況管理の説明図である。また図６は図５の回路の機能説明図である。なお、図５、６に対応する従来技術は図１８、１９に示した通りである。以下、図１８、１９を参照しながら、図５、６に基づいてポピュレーションカウント回路によるキュー使用状況管理を説明する。
【０１１４】
図５において、ＳＲ−ＦＦはセット・リセット型フリップフロップ回路、ＰＯＰＣは図２のポピュレーションカウント回路全体である。図示のように、複数のＳＲ−ＦＦからそれぞれキュー値（Queue#0-Valid 、 Queue#1-Valid ）がＰＯＰＣへ出力されている。
【０１１５】
また、図６にはポピュレーションカウント回路の機能を説明した図であり、機能ブロックＡ側には、機能ブロックＢのキューそれぞれに対応する有効信号を設け、その出力をＰＯＰＣ回路に通すことで、現在のキュー使用数を知ることができる。また、機能ブロックＡから機能ブロックＢへ要求をするときには、使用するキュー番号を伝えるとともに、当該有効信号をセットする。
【０１１６】
また、解放の際も、解放するキュー番号をＢからＡに伝え、Ａの有効信号を無効化する。こうすると、この有効信号が化けてしまったとする。これに対応するキューが使われなくなる（誤って有効化されてしまった場合）か、既に使用中のキューに対して要求を出してしまうか、である。
【０１１７】
前者の場合は、実行キュー数が減る以外の害はなく、後者の場合には即座に問題が判明する。実際には、相互の通信のために要求側でもある程度のキュー管理をしているのが普通であり、図６から想像されるほどポピュレーションカウント回路であることで複雑になることはない。
【０１１８】
§５：ポピュレーションカウント回路の応用例等の説明
(1) ：応用例１
図７に６４ビットポピュレーションカウント回路例を示してある。この回路は前記図２に示した１６ビットポピュレーションカウント回路を、６４ビット入力のポピュレーションカウント回路に応用した例であり、初段に４−３ＣＳＡが使用されている。また、図示点線内の単位回路は、ＰＯＰＣ１６Ｓｕｂの詳細図であり、初段に４−３ＣＳＡが使用されている。
【０１１９】
(2) ：応用例２
図８は３２ビット乗算器例、図９は乗算器の部分和の計算方法説明図である。この回路では、図２に示した１６ビットポピュレーションカウント回路と同じ構成のポピュレーションカウント回路１１、１２を２つ用い、その出力側に４ビットフルアダー１３を接続すると共に、ＡＮＤ回路１４とＯＲ回路１５、１６を設けて３２ビット乗算器とした例である。
【０１２０】
この場合、乗算器では部分和の計算をする場合、図９のような計算方法により計算する。この例では、１６桁のｘと１６桁のｙとの乗算を行う場合、図示のようにして計算する。この場合、Ｘｎは計算過程で生じたｐを図示縦方向に加算する（図示点線内のｐを図示縦方向に加算してＸｎ＝ａを計算する）ことで部分和を求めている。この場合、部分和Ｘｎは、複数の部分和のそれぞれ（図の左右方向に並んだ全ての部分和）に対して並列に求める。
【０１２１】
この加算はポピュレーションカウント回路１１、１２でそれぞれ計算し、部分和Ｘｎを求める。すなわち、ポピュレーションカウント回路１１、１２では、入力ビット列の中から‘１’になっているビット数を並列に計数することで部分和Ｘｎを計算している。
【０１２２】
なお、前記応用例１、２に示した回路は６４ビット入力（図７）、３２ビット入力（図８）の例であり、それぞれ初段は４−３ＣＳＡを用いており、最終段も請求項２、３の実施形態を示している。特に、３２ビット入力の回路（図８）では２つの１６ビットポピュレーションカウント回路の出力の和を採っているが、ここでも請求項２、３の実施形態となっている。
【０１２３】
(3) ：応用例３
図１０は１６ビット乗算器例である。図１０において、ＣＰＡは桁上げ伝播加算器、ＰＳＵは部分和計数回路を示す。この回路でも図示点線内に示した単位回路は、初段に４つの４−３ＣＳＡを用いている。なお、図示点線内の単位回路は、５つのＰＳＵの内の各１つの部分和計数回路ＰＳＵの単位回路であり、この中でも本発明の４−３ＣＳＡが使用されている。
【０１２４】
(4) ：応用例４
図１１は３２ビット乗算器例である。図１１において、点線内に示した回路は、ＰＳＵ３２内の回路である。また、図１１の点線内の各ＰＳＵは、図１０の点線内に示した単位回路である。
【０１２５】
（乗算の部分和回路の説明）
本発明に係るポピュレーションカウント回路を利用した乗算器の構成例は応用例３の図１０や応用例４の図１１に示されている。ここでも初段は４−３ＣＳＡを用いている。これらの回路では、乗算の部分和回路の例が示されており、この部分和の計算では、図９に示した部分和Ｘｎを計算する。例えば、６４ビット乗算を処理する場合でも３２ビット乗算４分割にして計算する手法がある。
【０１２６】
前記従来例１で示した図１３の回路では、２８ビットの乗算について５−３ＣＳＡが８段＋ＣＰＡはキャリーが図から省略されているが、クリティカルになるのはキャリー伝搬のところとなり、これは図で言うところの４Ｗの８段通過となるパスがクリティカルパスであった。
【０１２７】
これを本発明をベースに置き換えると、３２ビット乗算について、４−３ＣＳＡ３個、２−２ＨＡ１個、５−３ＣＳＡ２個、３−２ＣＳＡ２個、ＣＰＡであり、単位ＣＳＡは同じ８個、その中でも高速な２−２ＨＡが含まれるなど、高速な回路が組めることが分かる。なお、本発明のポピュレーションカウント回路にブース（Booth ）アルゴリズムなどを併用するのも、もちろん可能である。
【０１２８】
(5) ：その他の説明
以上の各例での特に後段の組み方は１例であり、使用されるテクノロジや配置配線などにより、最適な組み方は前記例として図示しているもの以外にも適用可能である。すなわち、本発明で使用している４−３ＣＳＡは色々な組み方を適用可能とするものである。
【０１２９】
このように、ワラスツリーに４−３ＣＳＡを用いることにより、バランスの良い高速なポピュレーションカウント回路や乗算器を実現できる。また、この高速回路の実現により、従来用いるのが困難であった、演算器以外の制御回路への適用が容易になる。
【図面の簡単な説明】
【０１３０】
【図１】本発明の原理説明図である。
【図２】実施の形態における１６ビットポピュレーションカウント回路例１である。
【０１３１】
【図３】図２の回路の動作説明図である。
【図４】実施の形態における１６ビットポピュレーションカウント回路例２である。
【０１３２】
【図５】実施の形態におけるポピュレーションカウント回路によるキュー使用状況管理の説明図である。
【図６】図５の回路の機能説明図である。
【図７】実施の形態における６４ビットポピュレーションカウント回路例である。
【図８】実施の形態における３２ビット乗算器例である。
【図９】実施の形態における乗算器の部分和の計算方法説明図である。
【図１０】実施の形態における１６ビット乗算器例である。
【図１１】実施の形態における３２ビット乗算器例である。
【図１２】従来例１のワラスツリー乗算器（従来型）である。
【図１３】従来例１の規則化ワラスツリー乗算器である。
【図１４】従来例１の７Ｄ4 ユニットである。
【図１５】従来例１の乗算器全体ブロック図である。
【図１６】従来例１の４入力加算器（４Ｗ）である。
【図１７】従来例２の説明図であり、Ａ図はＲＣＡによる遅延イメージ、Ｂ図はＲＣＡ遅延の改善イメージである。
【図１８】従来例３のユースドカウンタ例である。
【図１９】従来例３のユースドカウンタの機能説明図である。
【図２０】従来例４の１６ビットポピュレーションカウント回路例である。
【符号の説明】
【０１３３】
ＣＳＡ  桁上げ保存加算器
ＨＡ  ハーフアダー（半加算器）
ＦＡ  フルアダー（全加算器）
ＰＯＰＣ  ポピュレーションカウント回路
ＳＲ−ＦＦ  セット・リセット型フリップフロップ回路
１１、１２  １６ビットポピュレーションカウント回路
１３  １４ビットフルアダー
１５、１６  ＯＲ回路（論理和回路）
【図１】
2005165793.tif 000005
【図２】
2005165793.tif 000006
【図３】
2005165793.tif 000007
【図４】
2005165793.tif 000008
【図５】
2005165793.tif 000009
【図６】
2005165793.tif 000010
【図７】
2005165793.tif 000011
【図８】
2005165793.tif 000012
【図９】
2005165793.tif 000013
【図１０】
2005165793.tif 000014
【図１１】
2005165793.tif 000015
【図１２】
2005165793.tif 000016
【図１３】
2005165793.tif 000017
【図１４】
2005165793.tif 000018
【図１５】
2005165793.tif 000019
【図１６】
2005165793.tif 000020
【図１７】
2005165793.tif 000021
【図１８】
2005165793.tif 000022
【図１９】
2005165793.tif 000023
【図２０】
2005165793.tif 000024