(57)【特許請求の範囲】
【請求項１】
並列ｎビットの信号ＥＮを入力し、ｉビット目（ｉ＝０，・・・，ｎ−１）の信号ＥＮ［ｉ］について、信号ＥＮ［ｉ］＝０のときは０のみで表され、信号ＥＮ［ｉ］＝１のときは当該１のビットの位置が表わされるビットカウント結果ＯＵＴ［ｉ］を求めるとき、
信号ＥＮ［０］では、信号ＥＮ［０］＝０のときは０、信号ＥＮ［０］＝１のときは１のビットカウント結果ＯＵＴ［０］を出力するとともに、１の累算結果ＳＵＭ［０］を出力し、
信号ＥＮ［ｉ］（ｉ≧１）では、信号ＥＮ［０］〜ＥＮ［ｉ−１］の１の累算結果ＳＵＭ［ｉ−１］と前記ＥＮ［ｉ］とを用いて、
信号ＥＮ［ｉ］＝０のときは全ビット０のビットカウント結果ＯＵＴ［ｉ］を出力するとともに、累算結果ＳＵＭ［ｉ］として前記累算結果ＳＵＭ［ｉ−１］を出力し、
信号ＥＮ［ｉ］＝１のときはビットカウント結果ＯＵＴ［ｉ］として前記累算結果ＳＵＭ［ｉ−１］を出力するとともに、累算結果ＳＵＭ［ｉ］として前記累算結果ＳＵＭ［ｉ−１］の値を１ビットをずらして出力することを特徴とするビットカウント方法。
【請求項２】
並列ｎビットの信号ＥＮを入力し、ｉビット目（ｉ＝０，・・・，ｎ−１）の信号ＥＮ［ｉ］について、信号ＥＮ［ｉ］＝０のときは０のみで表され、信号ＥＮ［ｉ］＝１のときは当該１のビットの位置が表わされるビットカウント結果ＯＵＴ［ｉ］を求めるとき、
信号ＥＮ［０］に対応して、ビットカウント結果ＯＵＴ［０］として、信号ＥＮ［０］のビット値を１ビットでそのまま出力するとともに、累算結果ＳＵＭ［０］として、信号ＥＮ［０］のビット値の反転値と信号ＥＮ［０］のビット値とからなる合計２ビットを出力し、
信号ＥＮ［ｉ］（ｉ≧１）に対応して、ビットカウント結果ＯＵＴ［ｉ］として、前段の累算結果ＳＵＭ［ｉ−１］と信号ＥＮ［ｉ］との論理積で求めた値を合計ｉ＋１ビットで出力するとともに、累算結果ＳＵＭ［ｉ］として、０ビット目を信号ＥＮ［ｉ］の反転値と累算結果ＳＵＭ［ｉ−１］の０ビット目との論理積で求め、１〜ｉビット目を信号ＥＮ［ｉ］の反転値と累算結果ＳＵＭ［ｉ−１］の１〜ｉビット目との論理積で求めた値と前記ビットカウント結果ＯＵＴ［ｉ］の０〜ｉ−１ビット目の値との論理和とし、ｉ＋１ビット目をビットカウント結果ＯＵＴ［ｉ］のｉビットとして、合計ｉ＋２ビットを出力する、
ことを特徴とするビットカウント方法。
【請求項３】
請求項２に記載のビットカウント方法において、前記信号ＥＮ［ｉ］（ｉ≧１）に対応する処理を、
ビットカウント結果ＯＵＴ［ｉ］として、累算結果ＳＵＭ［ｉ−１］と信号ＥＮ［ｉ］との否定論理積で求めた値を反転して求めた値を合計ｉ＋１ビットで出力するとともに、累算結果ＳＵＭ［ｉ］として、０ビット目を前記入力信号ＥＮ［ｉ］の反転値と累算結果ＳＵＭ［ｉ−１］の０ビット目との否定論理積で求めた値を反転して求め、１〜ｉビット目を信号ＥＮ［ｉ］の反転値と記累算結果ＳＵＭ［ｉ−１］の１〜ｉビット目との否定論理積で求めた値とビットカウント結果ＯＵＴ［ｉ］の０〜ｉ−１ビット目の値との否定論理積で求め、ｉ＋１ビット目をビットカウント結果ＯＵＴ［ｉ］のｉビットとして、合計ｉ＋２ビットを出力する処理、
に置き換えたことを特徴とするビットカウント方法。
【請求項４】
並列ｎビットの信号ＥＮを入力し、ｉビット目（ｉ＝０，・・・，ｎ−１）の信号ＥＮ［ｉ］について、信号ＥＮ［ｉ］＝０のときは０のみで表され、信号ＥＮ［ｉ］＝１のときは当該１のビット位置が表わされるビットカウント結果ＯＵＴ［ｉ］を求めるビットカウント回路であって、信号ＥＮ［１］を入力する第０ビット用演算部と、信号ＥＮ［ｉ］（ｉ≧１）を入力する第ｉビット用演算部を備え、
前記第０ビット用演算部は、
信号ＥＮ［０］を入力して、信号ＥＮ［０］のビット値をそのままビットカウント結果ＯＵＴ［０］として出力する経路と、信号ＥＮ［０］のビット値を第１反転回路で反転させ累算結果ＳＵＭ［０］［０］として出力する経路と、信号ＥＮ［０］のビット値をそのまま累算結果ＳＵＭ［０］［１］として出力する経路とを有し、
前記第ｉビット用演算部は、
前段の累算結果ＳＵＭ［ｉ−１］と信号ＥＮ［ｉ］との論理積を求めビットカウント結果ＯＵＴ［ｉ］をｉ＋１ビットで出力するｉ＋１個の第１アンド回路と、信号ＥＮ［ｉ］を反転する第２反転回路と、該第２反転回路の出力信号と累算結果ＳＵＭ［ｉ−１］の０ビット目との論理積を求め累算結果ＳＵＭ［ｉ］の０ビット目を出力する１個の第２アンド回路と、前記第２の反転回路３１ｉ−２の出力と累算結果ＳＵＭ［ｉ］の１〜ｉビット目との論理積を求めるｉ個の第３アンド回路と、該ｉ個の第３アンド回路の出力とビットカウント結果ＯＵＴ［ｉ］の０〜ｉ−１ビット目との論理和を求めて累算結果ＳＵＭ［ｉ］の１〜ｉビット目を出力するｉ個のオア回路と、ビットカウント結果ＯＵＴ［ｉ］のｉビット目を累算結果ＳＵＭ［ｉ］の１＋ｉビット目として出力する経路とを有する、
ことを特徴とするビットカウント回路。
【請求項５】
請求項４に記載のビットカウント回路おいて、前記第ｉビット用演算部を、
累算結果ＳＵＭ［ｉ−１］と信号ＥＮ［ｉ］との否定論理積を求めるｉ＋１個の第１ナンド回路と、該第１ナンド回路の各出力を反転させｉ＋１ビットのビットカウント結果ＯＵＴ［ｉ］を出力するｉ＋１個の第３反転回路と、信号ＥＮ［ｉ］の反転値を求める１個の第４反転回路と、累算結果ＳＵＭ［ｉ−１］の０ビット目と前記第４反転回路の出力との否定論理積を求める１個の第２ナンド回路と、該第２ナンド回路の出力を反転させて累算結果ＳＵＭ［ｉ］の０ビット目を出力する１個の第５反転回路と、累算結果ＳＵＭ［ｉ−１］の１〜ｉビット目と前記第４反転回路の出力との否定論理積を求めるｉ個の第２ナンド回路と、該第２ナンド回路の各出力と前記第１ナンド回路の各出力との否定論理積を求めて累算結果ＳＵＭ［ｉ］の１〜ｉビット目を出力するｉ個の第４ナンド回路と、ビットカウント信号ＯＵＴ［ｉ］のｉビット目を記累算結果ＳＵＭ［ｉ］のｉ＋１ビット目として出力する経路とを有する回路、
と置き換えたことを特徴とするビットカウント回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列ｎビットの各ビットの内に１があるとき、それが０ビット目から数えて何個目の１であるかを示す値（ビットカウント結果）を出力するビットカウント方法およびビットカウント回路に関するものである。
【背景技術】
【０００２】
図８に従来の間引き処理回路５０の構成を示す。この間引き処理回路５０は、順番付けされたｎ個（図８はｎ＝４の場合）のデータ入力端子５１と、順番付けされたｎ個のデータ出力端子５２と、ｎ個の制御入力端子５３を有する。そして、制御入力端子５３への通過指示がある入力データのみを、データ入力端子５１の並び順を保持したまま、データ出力端子５２の並びの順番の前（図８で左側）に詰めて出力する。
【０００３】
この間引き処理回路５０は、スイッチ部６０とスイッチ制御部７０で構成される。スイッチ部６０は、データ入力端子５１の各端子に接続されるｎ個の入力線６１、データ出力端子５２の各端子に接続されるｎ個の出力線６２、およびｎ個の入力線６１とｎ個の出力線６２との各交叉部分で入力線６１と出力線６２との接続／接続断を行うｎ×ｎ個のクロスポイント６３で構成される。
【０００４】
また、スイッチ制御部７０は、ｎ個の制御入力端子５３に入力する通過指示信号ＥＮ［ｉ］（ｉ＝０〜ｎ−１）に応じて、出力信号ＯＵＴ［ｉ］を出力するビットカウント回路７１と、その出力信号ＯＵＴ［ｉ］を０パディング（ＭＳＢ側に０を詰めてビット数を調整する）する０パディング回路７２からなり、この０パディング回路７２からスイッチ部６０の各クロスポイント６３の接続／接続断を指示するスイッチ制御信号ＳＷ［ｉ］［ｊ］（ｉ，ｊ＝０〜ｎ−１）を出力する。
【０００５】
入力データＤＩＮ［ｉ］は、入力データ線５１のｉ番目から入力線６１を介してスイッチ部６０に入力し、通過指示信号ＥＮ［ｉ］は、制御入力端子５３のｉ番目からスイッチ制御部７０に入力する。図８では、ｎ＝４であるので、通過指示信号ＥＮ［ｉ］は、たとえば、次の通りである。
【０００６】
ＥＮ［０］＝１
ＥＮ［１］＝１
ＥＮ［２］＝０
ＥＮ［３］＝１
【０００７】
スイッチ制御部７０のビットカウント回路７１を構成する場合、従来では、例えば、ｎ＝４の場合は、図９に示すように、ポピュレーションカウント回路７１１〜７１３が利用される。ポピュレーションカウント回路７１１は、ＥＮ［０］とＥＮ［１］の１の和を計算し、ポピュレーションカウント回路７１２は、ＥＮ［０］とＥＮ［１］とＥＮ［２］の１の和を計算し、ポピュレーションカウント回路７１３は、ＥＮ［０］とＥＮ［１］とＥＮ［２］とＥＮ［３］の１の和を計算する。
【０００８】
そして、ポピュレーションカウント結果Ｐ［ｉ］は、次のように２進数（例では最大３ビット）で表される。｛  ｝内の数字は、左側がＬＳＢ、右側ＭＳＢである。
Ｐ［０］＝１
Ｐ［１〕＝｛０，１｝
Ｐ［２］＝｛０，１｝
Ｐ［３］＝｛１，１，０｝
このように、Ｐ［０］は１０進数の１、Ｐ［１〕は１０進数の２、Ｐ［２］は１０進数の２、Ｐ［３］は１０進数の３を示す。
【０００９】
ポピュレーションカウント結果Ｐ［ｉ］の２進数は、次段の２進数→ビットフラグ変換回路７１４〜７１５でビットフラグ変換され、その変換結果がセレクタ７１６〜７１８でＥＮ［ｉ］の値に応じて選択され、ビットカウント結果ＯＵＴ［ｉ］となる。ここで、「ビットフラグ」とは、ビット列中の最大１ビットが１で他のビットは全て０であり、１のフラグがたっているビットの位置によって数値を表現することを意味する。たとえば、｛０，０，０，０｝は「０」、｛１，０，０，０｝は「１」、｛０，１，０，０｝は「２」、｛０，０，１，０｝は「３」、｛０，０，０，１｝は「４」を表す。セレクタ７１６〜７１８では、ＥＮ［ｉ］＝１のときはビットフラグ変換結果が選択され、０のときは０が選択される。そして、このＯＵＴ［ｉ］が０パディング回路７２で０パディングされて、ｎ（＝４）ビットに揃えられる。０パディング回路７２の出力がスイッチ制御信号ＳＷ［ｉ］［ｊ］となる。
【００１０】
たとえば、図８の例では、ＳＷ［ｉ］は、ビットカウント結果ＯＵＴ［ｉ］のＭＳＢ側（右側）に０を付加して、
ＯＵＴ［０］＝１                  →ＳＷ［０］＝｛１，０，０，０｝
ＯＵＴ［１］＝｛０，１｝          →ＳＷ［１］＝｛０，１，０，０｝
ＯＵＴ［２］＝｛０，０，０｝      →ＳＷ［２］＝｛０，０，０，０｝
ＯＵＴ［３］＝｛０，０，１，０｝  →ＳＷ［３］＝｛０，０，１，０｝
となる。図１０に図９のビットカウント回路７１で行われる処理のフローチャートを示した。ポピュレーションカウント回路に関しては、非特許文献１，２に記載がある。
【００１１】
以上から、スイッチ信号ＳＷ［ｉ］［ｊ］によってスイッチ部６０が制御される。すなわち、ＥＮ［ｉ］＝０に対応する入力データＤＩＮ［ｉ］は間引かれてスイッチ部６０から出力せず、通過指示信号ＥＮ［ｉ］＝１に対応する入力データＤＩＮ［ｉ］はスイッチ部６０を通過して、出力データＤＯＵＴ［ｉ］となる。図８の回路では、
ＤＯＵＴ［０］＝ＤＩＮ［０］
ＤＯＵＴ［１］＝ＤＩＮ［１］
ＤＯＵＴ［２］＝ＤＩＮ［３］
ＤＯＵＴ［３］＝無効
となる。
【００１２】
【非特許文献１】佐藤  他  著、「５４ビット規則化ワラストリー乗算器」、情報処理学会研究報告（計算機アーキテクチャー  ９４−４）、社団法人情報処理学会、情処研報ｖｏ１．９２．Ｎｏ．４８、１９９２年６月１２日、ｐ２５〜３１。
【非特許文献２】鈴木  著、「高速な数値演算回路の設計を考える  第３回」、Design Wave Magazine、2002年8月号、ＣＱ出版、１２７−１２８頁。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
ところが、従来のスイッチ制御部７０のビットカウント回路７１は、ポピュレーションカウント回路を用いるので、次の問題点がある。まず、ポピュレーションカウント結果Ｐ［ｉ］をスイッチ制御信号として使用するには、２進数→ビットフラグ変換回路が必要である。また、通過指示信号ＥＮ［ｉ］＝０の場合、ＯＵＴ［ｉ］＝｛０，０，０，・・・，０｝を選択するセレクタが必要である。さらに、各通過指示信号ＥＮ［ｉ］について、先頭からの１の累算結果をビットフラグとして出力するには、ポピュレーションカウント回路、２進数→ビットフラグ変換回路、セレクタが、通過指示信号ＥＮの個数に応じて必要となり、通過指示信号のビット数ｎが大きくなると、スイッチ制御部７０のゲート数が急激に大きくなる。さらに、通過指示信号ＥＮのビット数ｎの拡張に対して、ポピュレーションカウント回路の構成に規則性（スケーラビリテイ）が乏しく、設計が容易でない。
【００１４】
本発明の目的は、ポピュレーションカウント回路や２進数→ビットフラグ変換回路を用いることなく、通常の論理素子を規則的に組み合わせて、ＥＮ［ｉ］からビットカウント結果ＯＵＴ［ｉ］を生成できるようにし、回路のゲート規模低減、低消費電力化、容易な設計を可能にしたビットカウント回路を提供することである。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、請求項１にかかる発明のビットカウント方法は、並列ｎビットの信号ＥＮを入力し、ｉビット目（ｉ＝０，・・・，ｎ−１）の信号ＥＮ［ｉ］について、信号ＥＮ［ｉ］＝０のときは０のみで表され、信号ＥＮ［ｉ］＝１のときは当該１のビットの位置が表わされるビットカウント結果ＯＵＴ［ｉ］を求めるとき、信号ＥＮ［０］では、信号ＥＮ［０］＝０のときは０、信号ＥＮ［０］＝１のときは１のビットカウント結果ＯＵＴ［０］を出力するとともに、１の累算結果ＳＵＭ［０］を出力し、信号ＥＮ［ｉ］（ｉ≧１）では、信号ＥＮ［０］〜ＥＮ［ｉ−１］の１の累算結果ＳＵＭ［ｉ−１］と前記ＥＮ［ｉ］とを用いて、信号ＥＮ［ｉ］＝０のときは全ビット０のビットカウント結果ＯＵＴ［ｉ］を出力するとともに、累算結果ＳＵＭ［ｉ］として前記累算結果ＳＵＭ［ｉ−１］を出力し、信号ＥＮ［ｉ］＝１のときはビットカウント結果ＯＵＴ［ｉ］として前記累算結果ＳＵＭ［ｉ−１］を出力するとともに、累算結果ＳＵＭ［ｉ］として前記累算結果ＳＵＭ［ｉ−１］の値を１ビットをずらして出力することを特徴とする。
請求項２にかかるビットカウンタ方法は、並列ｎビットの信号ＥＮを入力し、ｉビット目（ｉ＝０，・・・，ｎ−１）の信号ＥＮ［ｉ］について、信号ＥＮ［ｉ］＝０のときは０のみで表され、信号ＥＮ［ｉ］＝１のときは当該１のビットの位置が表わされるビットカウント結果ＯＵＴ［ｉ］を求めるとき、信号ＥＮ［０］に対応して、ビットカウント結果ＯＵＴ［０］として、信号ＥＮ［０］のビット値を１ビットでそのまま出力するとともに、累算結果ＳＵＭ［０］として、信号ＥＮ［０］のビット値の反転値と信号ＥＮ［０］のビット値とからなる合計２ビットを出力し、信号ＥＮ［ｉ］（ｉ≧１）に対応して、ビットカウント結果ＯＵＴ［ｉ］として、前段の累算結果ＳＵＭ［ｉ−１］と信号ＥＮ［ｉ］との論理積で求めた値を合計ｉ＋１ビットで出力するとともに、累算結果ＳＵＭ［ｉ］として、０ビット目を信号ＥＮ［ｉ］の反転値と累算結果ＳＵＭ［ｉ−１］の０ビット目との論理積で求め、１〜ｉビット目を信号ＥＮ［ｉ］の反転値と累算結果ＳＵＭ［ｉ−１］の１〜ｉビット目との論理積で求めた値と前記ビットカウント結果ＯＵＴ［ｉ］の０〜ｉ−１ビット目の値との論理和とし、ｉ＋１ビット目をビットカウント結果ＯＵＴ［ｉ］のｉビットとして、合計ｉ＋２ビットを出力する、ことを特徴とする。
請求項３にかかる発明は、請求項２に記載のビットカウント方法において、前記信号ＥＮ［ｉ］（ｉ≧１）に対応する処理を、ビットカウント結果ＯＵＴ［ｉ］として、累算結果ＳＵＭ［ｉ−１］と信号ＥＮ［ｉ］との否定論理積で求めた値を反転して求めた値を合計ｉ＋１ビットで出力するとともに、累算結果ＳＵＭ［ｉ］として、０ビット目を前記入力信号ＥＮ［ｉ］の反転値と累算結果ＳＵＭ［ｉ−１］の０ビット目との否定論理積で求めた値を反転して求め、１〜ｉビット目を信号ＥＮ［ｉ］の反転値と記累算結果ＳＵＭ［ｉ−１］の１〜ｉビット目との否定論理積で求めた値とビットカウント結果ＯＵＴ［ｉ］の０〜ｉ−１ビット目の値との否定論理積で求め、ｉ＋１ビット目をビットカウント結果ＯＵＴ［ｉ］のｉビットとして、合計ｉ＋２ビットを出力する処理、に置き換えたことを特徴とする。
請求項４にかかる発明のビットカウント回路は、並列ｎビットの信号ＥＮを入力し、ｉビット目（ｉ＝０，・・・，ｎ−１）の信号ＥＮ［ｉ］について、信号ＥＮ［ｉ］＝０のときは０のみで表され、信号ＥＮ［ｉ］＝１のときは当該１のビット位置が表わされるビットカウント結果ＯＵＴ［ｉ］を求めるビットカウント回路であって、信号ＥＮ［１］を入力する第０ビット用演算部と、信号ＥＮ［ｉ］（ｉ≧１）を入力する第ｉビット用演算部を備え、前記第０ビット用演算部は、信号ＥＮ［０］を入力して、信号ＥＮ［０］のビット値をそのままビットカウント結果ＯＵＴ［０］として出力する経路と、信号ＥＮ［０］のビット値を第１反転回路で反転させ累算結果ＳＵＭ［０］［０］として出力する経路と、信号ＥＮ［０］のビット値をそのまま累算結果ＳＵＭ［０］［１］として出力する経路とを有し、前記第ｉビット用演算部は、前段の累算結果ＳＵＭ［ｉ−１］と信号ＥＮ［ｉ］との論理積を求めビットカウント結果ＯＵＴ［ｉ］をｉ＋１ビットで出力するｉ＋１個の第１アンド回路と、信号ＥＮ［ｉ］を反転する第２反転回路と、該第２反転回路の出力信号と累算結果ＳＵＭ［ｉ−１］の０ビット目との論理積を求め累算結果ＳＵＭ［ｉ］の０ビット目を出力する１個の第２アンド回路と、前記第２の反転回路３１ｉ−２の出力と累算結果ＳＵＭ［ｉ］の１〜ｉビット目との論理積を求めるｉ個の第３アンド回路と、該ｉ個の第３アンド回路の出力とビットカウント結果ＯＵＴ［ｉ］の０〜ｉ−１ビット目との論理和を求めて累算結果ＳＵＭ［ｉ］の１〜ｉビット目を出力するｉ個のオア回路と、ビットカウント結果ＯＵＴ［ｉ］のｉビット目を累算結果ＳＵＭ［ｉ］の１＋ｉビット目として出力する経路とを有する、ことを特徴とする。
請求項５にかかる発明は、請求項４に記載のビットカウント回路おいて、前記第ｉビット用演算部を、累算結果ＳＵＭ［ｉ−１］と信号ＥＮ［ｉ］との否定論理積を求めるｉ＋１個の第１ナンド回路と、該第１ナンド回路の各出力を反転させｉ＋１ビットのビットカウント結果ＯＵＴ［ｉ］を出力するｉ＋１個の第３反転回路と、信号ＥＮ［ｉ］の反転値を求める１個の第４反転回路と、累算結果ＳＵＭ［ｉ−１］の０ビット目と前記第４反転回路の出力との否定論理積を求める１個の第２ナンド回路と、該第２ナンド回路の出力を反転させて累算結果ＳＵＭ［ｉ］の０ビット目を出力する１個の第５反転回路と、累算結果ＳＵＭ［ｉ−１］の１〜ｉビット目と前記第４反転回路の出力との否定論理積を求めるｉ個の第２ナンド回路と、該第２ナンド回路の各出力と前記第１ナンド回路の各出力との否定論理積を求めて累算結果ＳＵＭ［ｉ］の１〜ｉビット目を出力するｉ個の第４ナンド回路と、ビットカウント信号ＯＵＴ［ｉ］のｉビット目を記累算結果ＳＵＭ［ｉ］のｉ＋１ビット目として出力する経路とを有する回路、と置き換えたことを特徴とする。
【発明の効果】
【００１６】
本発明のビットカウント方法およびそのビットカウント回路によれば、ビットカウント結果ＯＵＴ［ｉ］がビットフラグの形で直接出力され、かつ、信号ＥＮ［ｉ］＝０に対しては全ビット０のビットカウント結果が直接出力されるので、２進数→ビットフラグ変換やセレクタが不要となる。また、信号ＥＮ［ｉ］のビット数が増えても、ゲート数が急激に大きくなることはない。よって、回路のゲート規模低減、低消費電力化が可能になる。さらに、ＥＮのビット数が増えても、同様の規則で拡張する設計方法で容易にビットカウント結果を得ることができる。
【発明を実施するための最良の形態】
【００１７】
＜第１の実施例＞
図１に本実施例の間引き処理回路１０の構成を示す。この間引き処理回路１０は、順番付けされたｎ個（図１はｎ＝４の場合）のデータ入力端子１１と、順番付けされたｎ個のデータ出力端子１２と、ｎ個の制御入力端子１３を有する。そして、制御入力端子１３への通過指示がある入力データのみを、データ入力端子１１の並び順を保持したまま、データ出力端子１２の並びの順番の前（左側）に詰めて出力する。
【００１８】
この間引き処理回路１０は、スイッチ部２０とスイッチ制御部３０で構成される。スイッチ部２０は、データ入力端子１１の各端子に接続されるｎ個の入力線２１、データ出力端子１２の各端子に接続されるｎ個の出力線２２、およびｎ個の入力線２１とｎ個の出力線２２との各交叉部分で入力線２１と出力線２２との接続／接続断を行うｎ×ｎ個のクロスポイント２３で構成される。
【００１９】
また、スイッチ制御部３０は、ｎ個の制御入力端子１３に入力する通過指示信号ＥＮ［ｉ］（ｉ＝０〜ｎ−１）に応じて、ビットカウント結果ＯＵＴ［ｉ］を出力するビットカウント回路３１と、そのビットカウント結果ＯＵＴ［ｉ］を０バディング（ＭＳＢ側に０を詰めてビット数を調整する）する０パディング回路３２からなり、この０パディング回路３２からスイッチ部２０の各クロスポイント２３の接続／接続断を指示するスイッチ制御信号ＳＷ［ｉ］［ｊ］（ｉ，ｊ＝０〜ｎ−１）が出力する。
【００２０】
入力データＤＩＮ［ｉ］は、入力データ線１１のｉ番目から入力線２１を介してスイッチ部２０に入力し、通過指示信号ＥＮ［ｉ］は、制御入力端子１３のｉ番目からスイッチ制御部３０のビットカウント回路３１に入力する。図１は次の場合を示す。
ＥＮ［０］＝１
ＥＮ［１］＝１
ＥＮ［２］＝０
ＥＮ［３］＝１
【００２１】
スイッチ制御信号ＳＷ［ｉ］［ｊ］は、ｎ行ｎ列の２次元配列で、その各々の値は０又は１であり、スイッチ制御部３０から出力してスイッチ部２０に入力する。スイッチ制御信号ＳＷ［ｉ］［ｊ］のｉ行ｊ列は、クロスポイントスイッチ２３のｉ行ｊ列の接続／接続断を指示する。０のとき接続断、１のとき接続である。
【００２２】
以上から、スイッチ信号ＳＷ［ｉ］［ｊ］によってスイッチ部２０が制御される。すなわち、ＥＮ［ｉ］＝０に対応する入力データＤＩＮ［ｉ］は間引かれてスイッチ部２０から出力せず、通過指示信号ＥＮ［ｉ］＝１に対応する入力データＤＩＮ［ｉ］はスイッチ部２０を通過して、出力データＤＯＵＴ［ｉ］となる。図１の回路では、
ＤＯＵＴ［０］＝ＤＩＮ［０］
ＤＯＵＴ［１］＝ＤＩＮ［１］
ＤＯＵＴ［２］＝ＤＩＮ［３］
ＤＯＵＴ［３］＝無効
となる。
【００２３】
図２にスイッチ制御部３０のビットカウント回路３１の構成を示す。第ｉビット用演算部３１ｉについて説明すると、１ビットの通過指示信号ＥＮ［ｉ］と、前段の第ｉ−１用演算部３１ｉ−１から出力するｉ＋１ビットの累算結果ＳＵＭ［ｉ−１］とを入力して、ｉ＋１ビットのビットカウント結果ＯＵＴ［ｉ］と、ｉ＋２ビットの累算結果ＳＵＭ［ｉ］を出力する。
【００２４】
第ｉビット用演算部３１ｉに入力する累算結果ＳＵＭ［ｉ−１］［ｉ：０］は、通過指示信号ＥＮ［０］〜ＥＮ［ｉ−１］の間に存在する１の総数を表す（なお、［ｉ：０］はビットが０〜ｉビット目まであることを示す）。たとえば、通過指示信号ＥＮ［０］〜ＥＮ［ｉ−１］の間に存在する１の総数がｍ個（ｍ＝０，・・・，ｉ）の場合は、ＥＮ［ｉ−１］までの累算結果のｋビット目（ｋ＝０，・・・，ｉ）は、
ＳＵＭ［ｉ−１］［ｋ］＝１      （ｋ＝ｍ）
ＳＵＭ［ｉ−１］［ｋ］＝０      （ｋ≠ｍ）
となる。ただし、第０ビット用演算部３１０にはこの前段からの累算結果ＳＵＭ［ｉ−１］［ｉ：０］は入力しない。
【００２５】
第ｉビット用演算部３１ｉから出力するビットカウント結果ＯＵＴ［ｉ］［ｉ：０］は、通過指示信号ＥＮ［ｉ］が１のときに、それは先頭の通過指示信号ＥＮ［０］から数えて何個目の１であるかをｉ＋１ビットで表す。たとえば、通過指示信号ＥＮ［ｉ］がｐ個目（ｐ＝１，・・・，ｉ＋１）の１の場合は、ビットカウント結果のｋビット目（ｋ＝０，・・・，ｉ）は、
ＯＵＴ［ｉ］［ｋ］＝１      （ｋ＝ｐ−１）
ＯＵＴ［ｉ］［ｋ］＝０      （ｋ≠ｐ−１）
となる。通過指示信号ＥＮ［ｉ］が０の場合は、ＯＵＴ［ｉ］は全ビットが０となる。
【００２６】
第ｉビット用演算部３１ｉから出力する累算結果ＳＵＭ［ｉ］［ｉ＋１：０］は、通過指示信号ＥＮ［０］〜ＥＮ［ｉ］の間に存在する１の総数を表す（なお、［ｉ＋１：０］はビットが第０ビットから第ｉ＋１ビットまでであることを示す）。たとえば、通過指示信号ＥＮ［０］〜ＥＮ［ｉ］の間に存在する１の総数がｍ個（ｍ＝０，・・・，ｉ＋１）の場合は、ＥＮ［ｉ］ビットまでの累算結果ＳＵＭ［ｉ］のｋビット目（ｋ＝０，・・・，ｉ＋１）は、
ＳＵＭ［ｉ］［ｋ］＝１      （ｋ＝ｍ）
ＳＵＭ［ｉ］［ｋ］＝０      （ｋ≠ｍ）
となる。
【００２７】
ビットカウント結果ＯＵＴ［ｉ］［ｉ：０］の算出方法について説明する。前段の累算結果ＳＵＭ［ｉ−１］［ｉ：０］とビットカウント結果ＯＵＴ［ｉ］［ｉ：０］とは、どちらも１の個数を表すが、ビット数と個数の対応が１ずれる。ＯＵＴ［ｉ］［ｉ：０］は０ビット目が１ならば「１個目」を表す。ＳＵＭ［ｉ−１］［ｉ：０］は０ビット目が１ならば「０個」を表す。
【００２８】
よって、通過指示信号ＥＮ［ｉ］＝１の場合は、ＳＵＭ［ｉ−１］［ｉ：０］の値をそのままＯＵＴ［ｉ］［ｉ：０］に代入すればよく、
ＯＵＴ［ｉ］［ｋ］＝ＳＵＭ［ｉ−１］［ｋ］
となる。ただし、ＥＮ［ｉ］＝０の場合は、
ＯＵＴ［ｉ］［ｋ］＝０
でなければならないので、ＥＮ［ｉ］とＳＵＭ［ｉ−１］［ｋ］の論理積をとる。また、ｉ＝０のときは、前ビットまでの累算結果が存在しないので、ＳＵＭ［ｉ−１］［ｋ］の部分はない。
【００２９】
以上から、
ＯＵＴ［ｉ］［ｋ］＝ＥＮ［ｉ］・ＡＮＤ・ＳＵＭ［ｉ−１］［ｋ］
（ｉ≧１、ｋ＝０，・・・，ｉ）
ＯＵＴ［０］［０］＝ＥＮ［０］
となる。
【００３０】
たとえば、
ＳＵＭ［３］＝｛０，１，０，０，０｝、ＥＮ［４］＝１
のとき、ＥＮ［０］〜ＥＮ［３］の１の個数は１個であるので、
ＯＵＴ［４］＝｛０，１，０，０，０｝
となり、ＥＮ［４］の１は「２個目」の１である、というビットカウント結果が出る。
【００３１】
次に、累算結果ＳＵＭ［ｉ］［ｉ＋１：０］の算出方法について説明する。通過指示信号ＥＮ［ｉ］＝１の場合は、累算結果は通過指示信号ＥＮ［ｉ−１］までの累算結果より１だけ増加するので、ＳＵＭ［ｉ−１］［ｉ：０］の値をＭＳＢ側に１ビットずつずらして（ビットシフト）、ＳＵＭ［ｉ］［ｉ＋１：１］に代入すればよい。ＳＵＭ［ｉ］［０］は０にする。
ＳＵＭ［ｉ］［ｋ］＝ＳＵＭ［ｉ−１］［ｋ−１］
（ｋ＝１，・・・，ｉ＋１）
ＳＵＭ［ｉ］［ｋ］＝０                     （ｋ＝０）
(1)
【００３２】
一方、通過指示信号ＥＮ［ｉ］＝０の場合は、累算結果はＳＵＭ［ｉ−１］［ｉ：０］と同じなので、ＳＵＭ［ｉ−１］［ｉ：０］の値をそのままＳＵＭ［ｉ］［ｉ：０］に代入して、
ＳＵＭ［ｉ］［ｋ］＝ＳＵＭ［ｉ−１］［ｋ］
（ｋ＝０，・・・，ｉ）
ＳＵＭ［ｉ］［ｋ］＝０                   （ｋ＝ｉ＋１）
(2)
とすればよい。
【００３３】
以上から、(1)、(2)式の両方に対応して、ＥＮ［ｉ］の値に応じて(1)、(2)式のどちらか一方の結果を選択するために、ＥＮ［ｉ］と(1)式との論理積、ＥＮ［ｉ］の反転値と(2)式との論理積を求め、その論理和を求める。ただし、ｉ＝０のときは、前ビットまでの累算結果は存在しないので、ｋ＝０のときは、(1)式の部分は存在せず、ｋ＝ｉ＋１のときは、(2)式の部分は存在しない。
【００３４】
以上から、
ＳＵＭ［０］［０］＝ＮＯＴ・ＥＮ［０］
ＳＵＭ［０］［１］＝ＯＵＴ［０］［０］
＝ＥＮ［０］
ＳＵＭ［ｉ］［０］＝（ＮＯＴ・ＥＮ［ｉ］）・ＡＮＤ・（ＳＵＭ［ｉ−１］［０］）
ＳＵＭ［ｉ］［ｋ］＝（（ＮＯＴ・ＥＮ［ｉ］）・ＡＮＤ
・（ＳＵＭ［ｉ−１］［ｋ］））・ＯＲ
・（ＥＮ［ｉ］・ＡＮＤ・（ＳＵＭ［ｉ−１］［ｋ−１］））
（ｉ≧１、ｋ＝１，・・・，ｉ）
ＳＵＭ［ｉ］［ｉ＋１］＝ＯＵＴ［ｉ］［ｉ］
＝ＥＮ［ｉ］・ＡＮＤ・ＳＵＭ［ｉ−１］［ｉ］
となる。
【００３５】
たとえば、ＳＵＭ［３］［４：０］＝｛０，１，０，０，０｝、ＥＮ［４］＝１の場合は、
ＳＵＭ［４］［５：０］＝｛０，０，１，０，０，０｝
となり、ＥＮ［０］〜ＥＮ［４］のうちの１の個数は「２個」である、という累算結果が得られる。
【００３６】
図３に以上の法則にハードウエアで構成した論理回路を示し、また、図４にその処理のフローチャートを示した。
【００３７】
図３(a)は図２の０ビット用演算部３１０の構成を示し、入力信号ＥＮ［０］を入力して、入力信号ＥＮ［０］のビット値をそのままビットカウント結果ＯＵＴ［０］として出力する経路と、入力信号ＥＮ［０］のビット値を第１反転回路３１０−１で反転させ累算結果ＳＵＭ［０］［０］として出力する経路と、入力信号ＥＮ［０］のビット値をそのまま累算結果ＳＵＭ［０］［１］として出力する経路と、からなる。
【００３８】
図３(b)は図２の第ｉビット用演算部３２ｉの構成を示し、前段の累算結果ＳＵＭ［ｉ−１］と前記入力信号ＥＮ［ｉ］との論理積を求めビットカウント結果ＯＵＴ［ｉ］をｉ＋１ビットで出力するｉ＋１個の第１アンド回路３１ｉ−１と、入力信号ＥＮ［ｉ］を反転する第２反転回路３１ｉ−２と、該第２反転回路３１ｉ−２の出力信号と前記累算結果ＳＵＭ［ｉ−１］の０ビット目との論理積を求め累算結果ＳＵＭ［ｉ］の０ビット目を出力する１個の第２アンド回路３１ｉ−３と、前記第２の反転回路３１ｉ−２の出力と前記累算結果ＳＵＭ［ｉ］の１〜ｉビット目との論理積を求めるｉ個の第３アンド回路３１ｉ−４と、該ｉ個の第３アンド回路３１ｉ−４の出力と前記ビットカウント結果ＯＵＴ［ｉ］の０〜ｉ−１ビット目との論理和を求めて累算結果ＳＵＭ［ｉ］の１〜ｉビット目を出力するｉ個のオア回路３１ｉ−５と、前記ビットカウント結果ＯＵＴ［ｉ］のｉビット目を累算結果ＳＵＭ［ｉ］の１＋ｉビット目として出力する経路と、を備える。
【００３９】
図５に４つの通過指示信号ＥＮ［０］＝１、ＥＮ［１］＝１、ＥＮ［２］＝０、ＥＮ［３］＝１を使用する場合のビットカウント結果ＯＵＴ［０］［０］〜ＯＵＴ［３］［３：０］と、累算結果ＳＵＭ［０］［１：０］〜ＳＵＭ［２］［３：０］を示した。０パディング回路３２は、ＯＵＴ［０］［０］の値のＭＳＢ側に０を３個付加して４ビットに揃え、ＯＵＴ［１］［１：０］の値のＭＳＢ側に０を２個付加して４ビットに揃え、ＯＵＴ［２］［２：０］の値のＭＳＢ側に０を１個付加して４ビットに揃え、ＯＵＴ［３］［３：０］の値をそのまま、それぞれ、ＳＷ［０］［３：０］〜ＳＷ［３］［３：０］として出力する。
【００４０】
以上のように、本実施例では、ビットカウント回路３１において、１の累算結果ＳＵＭ［ｉ］が順次次段に伝達され、ビットカウント結果ＯＵＴ［ｉ］がビットフラグの形で直接出力されるので、従来の２進数→ビットフラグ変換が不要である。また、通過指示信号ＥＮ［ｉ］＝０に対しては全ビット０のビットカウント結果ＯＵＴ［ｉ］が直接出力されるので、従来のセレクタが不要である。さらに、各演算部３１０〜３１ｎ−１への通過指示信号ＥＮ［ｉ］は常に１ビットなので、入力ビット数が増えてもゲート数が急激に大きくなることはなく、同様の規則で拡張する設計方法で容易にビットカウント結果を得ることができる。さらに、図３に示したように、演算部３１０〜３１ｎ−１は、反転回路、アンド回路、オア回路の３種類のゲート素子で規則性をもって構成され、しかも、通過指示信号ＥＮがｎビットの場合、ゲート数は（ｎ−１）×２段になり、従来の「ポピュレーション回路＋２進数→ビットフラグ変換回路＋セレクタ」で同様な結果を出力する回路を構成する場合との比較して、総ゲート数は１／４以下、ゲート段数は１／２以下に低下する。図６に、入力ビット数に対するゲート総数とゲート段数の増加程度の比較結果を示した。
【００４１】
＜第２の実施例＞
前記した第１の実施例では、図３に示したように、０ビット用演算部３１０を反転回路のみを使用して構成し、１〜ｎ−１ビット用演算回路３１１〜３１ｎ−１を反転回路とアンド回路とオア回路を使用して構成した。しかし、演算部３１１〜３１ｎ−１については、図７に示すように、反転回路とナンド回路の２種類のゲートで構成することもできる。      
【００４２】
これは、
ＯＵＴ［ｉ］［ｋ］＝ＮＯＴ（ＥＮ［ｉ］・ＮＡＮＤ・ＳＵＭ［ｉ−１］［ｋ］）
ＳＵＭ［ｉ］［０］＝ＮＯＴ（ＮＯＴ・ＥＮ［ｉ］）・ＮＡＮＤ・
（ＳＵＭ［ｉ−１］［０］）
ＳＵＭ［ｉ］［ｋ］＝（（ＮＯＴ・ＥＮ［ｉ］）・ＮＡＮＤ
・（ＳＵＭ［ｉ−１］［ｋ］））・ＮＡＮＤ
・（ＥＮ［ｉ］・ＮＡＮＤ・ＳＵＭ［ｉ−１］［ｋ−１］）
ＳＵＭ［ｉ］［ｉ＋１］＝ＯＵＴ［ｉ］［ｉ］
（ｋ＝０，・・・，ｉ）
の演算式に基づくものである。
【００４３】
図７のｉビット用演算部３１ｉは、前段の累算結果ＳＵＭ［ｉ−１］と前記入力信号ＥＮ［ｉ］との否定論理積を求めるｉ＋１個の第１ナンド回路３１ｉ−１１と、該第１ナンド回路３１ｉ−１１の各出力を反転させｉ＋１ビットのビットカウント結果ＯＵＴ［ｉ］を出力するｉ＋１個の第３反転回路３１ｉ−１２と、前記入力信号ＥＮ［ｉ］の反転値を求める１個の第４反転回路３１ｉ−１３と、前記累算結果ＳＵＭ［ｉ−１］の０ビット目と第４反転回路３１ｉ−１３の出力との否定論理積を求める１個の第２ナンド回路３１ｉ−１４と、該第２ナンド回路３１ｉ−１４の出力を反転させて累算結果ＳＵＭ［ｉ］の０ビット目を出力する１個の第５反転回路３１ｉ−１５と、前記累算結果ＳＵＭ［ｉ−１］の１〜ｉビット目と前記第４反転回路３１ｉ−１３の出力との否定論理積を求めるｉ個の第２ナンド回路３１ｉ−１６と、該第２ナンド回路３１ｉ−１６の各出力と前記第１ナンド回路３１ｉ−１１の各出力との否定論理積を求めて前記累算結果ＳＵＭ［ｉ］の１〜ｉビット目を出力するｉ個の第４ナンド回路３１ｉ−１７と、前記ビットカウント信号ＯＵＴ［ｉ］のｉビット目を前記累算結果ＳＵＭ［ｉ］のｉ＋１ビット目として出力する経路とを備える。
【００４４】
本実施例では、各演算部３１０〜３１ｎ−１を構成するために、全体を反転回路とナンド回路の２種類のゲートを使用できるので、ＥＮ［ｉ］がｎビットの場合、ゲートは「ｎ×２−１」段になる。アンド回路（＝ナンド回路＋反転回路）とオア回路（＝ノア回路＋反転回路）で構成される回路と比較して、同数のナンド回路で構成される回路の方が、最小の素子数で構成されるので一般に占有面積が小さく、低消費電力である。つまり、「（Ａ・ＡＮＤ・Ｂ）ＯＲ（Ｃ・ＡＮＤ・Ｄ）」と「（Ａ・ＮＡＮＤ・Ｂ）ＮＡＮＤ（Ｃ・ＮＡＮＤ・Ｄ）」は、同じ結果が得られるが、ナンド回路のみのほうがＩＣの個数が少なくて済み、基板の占有面積を小さくすることができる。例えば、「ナンド回路が４個入ったＩＣ」、「ノア回路が４個入ったＩＣ」、「反転回路が６個入ったＩＣ」を使用する場合、１個のアンド回路と１個のオア回路の回路は、ナンド回路のＩＣ、ノア回路のＩＣ、反転回路のＩＣの３個が必要だが、２個のナンド回路はナンド回路のＩＣが１個で実現できる。また、実際の論理回路の設計では、アンド回路やオア回路よりもナンド回路やノア回路の方が作りやすい。さらに、遅延時間の蓄積をなるべく小さくするためには、高速性に優れるナンド回路で各段の累算結果の出力を得る構成とすることが望ましい。
【図面の簡単な説明】
【００４５】
【図１】本発明の第１の実施例の間引き処理回路の構成を示すブロック図である。
【図２】図１の間引き処理回路におけるスイッチ制御部のビットカウント回路の構成を示すブロック図である。
【図３】(a)は図２のビットカウント回路の第０ビット用演算部３１０の回路図、(b)は第ｉビット用演算部３１ｉの回路図である。
【図４】図２のビットカウント回路による処理のフローチャートである。
【図５】図１のビットカウント回路３１と０パディング回路３２の回路図である。
【図６】従来と本実施例のビットカウント回路の特性比較図であり、(a)はゲート総数、(b)はゲート段数の特性図である。
【図７】図２(b)の第ｉビット用演算部３１ｉの第２の実施例の回路図である。
【図８】従来の間引き処理回路の構成を示すブロック図である。
【図９】図８の間引き処理回路におけるスイッチ制御部７０のビットカウント回路７１の回路図である。
【図１０】図９のビットカウント回路７１の処理のフローチャートである。
【符号の説明】
【００４６】
１０：間引き処理回路
１１：データ入力端子
１２：データ出力端子
１３：制御入力端子
２０：スイッチ部
２１：入力線
２２：出力線
２３：クロスポイント
３０：スイッチ制御部
３１：ビットフラグ回路
３２：０パディング回路
３１０：第０ビット用演算部
３１０−１：第１反転回路
３１ｉ：第ｉビット用演算部
３１ｉ−１：ｉ＋１個の第１アンド回路
３１ｉ−２：第２反転回路
３１ｉ−３：１個の第２アンド回路
３１ｉ−４：ｉ個の第３アンド回路
３１ｉ−５：ｉ個のオア回路
３１ｉ−１１：ｉ＋１個の第１ナンド回路
３１ｉ−１２：ｉ＋１個の第３反転回路
３１ｉ−１３：１個の第４反転回路
３１ｉ−１４：１個の第２ナンド回路
３１ｉ−１５：１個の第５反転回路
３１ｉ−１６：ｉ個の第３ナンド回路
３１ｉ−１７：ｉ個の第４ナンド回路
【図１】
0004803829.tif 000002
【図２】
0004803829.tif 000003
【図３】
0004803829.tif 000004
【図４】
0004803829.tif 000005
【図５】
0004803829.tif 000006
【図６】
0004803829.tif 000007
【図７】
0004803829.tif 000008
【図８】
0004803829.tif 000009
【図９】
0004803829.tif 000010
【図１０】
0004803829.tif 000011