(57)【要約】  本発明は、安価かつ容易に製造でき、相互作用モデルにおける計算のため必要な多数決関数を処理することができる多数決回路を提供することを目的とする。本発明に係る多数決回路は、バイトニックソート回路を用いて、入力信号の総和を２のべき乗の値に丸めることにより、多数決関数の処理を簡易化する。
2017090122.tif 000002
【特許請求の範囲】
【請求項１】
２値のいずれかを有する複数の入力信号の多数決をとる多数決回路であって、
前記入力信号として第１入力信号を複数受け取り、前記第１入力信号が有する値の降順または昇順に各前記第１入力信号を並び替えて出力する、第１ソート回路、
前記第１入力信号の個数の２倍の個数の信号を受け取って前記第１ソート回路による並び替えと同じ順序で並び替えるとともに、その並び替えた信号のうち偶数番目の全てまたは奇数番目の全てを選択して出力する、第１選択回路、
前記第１選択回路の各番目の出力のうち前半の最後のものまたは後半の最初のものを前記多数決の結果として出力する端子、
を備えることを特徴とする多数決回路。
【請求項２】
前記多数決回路はさらに、前記第１入力信号と同じ個数の信号を前記第１選択回路に対する入力として受け取る信号供給回路を備え、
前記第１ソート回路は、第１重みを有する前記第１入力信号を受け取って並び替えるように構成されており、
前記第１選択回路は、前記第１重みの２倍の重みを有する信号を出力するように構成されており、
前記信号供給回路は、前記第１重みを有する信号を前記第１選択回路に対して与えるように構成されている
ことを特徴とする請求項１記載の多数決回路。
【請求項３】
前記多数決回路はさらに、前記第１重みの半分の第２重みを有する第２入力信号を前記入力信号として前記第１入力信号と同じ個数受け取り、前記第１ソート回路による並び替えと同じ順序で並び替えて出力する、第２ソート回路を備え、
前記信号供給回路は、前記第２入力信号の個数の２倍の個数の信号を受け取って前記第２ソート回路による並び替えと同じ順序で並び替えるとともに、その並び替えた信号のうち偶数番目の全てまたは奇数番目の全てを選択して出力する、第２選択回路として構成されており、
前記多数決回路はさらに、前記第２重みを有する前記第２入力信号と同じ個数の信号を前記第２選択回路に対して与える第２信号供給回路を備える
ことを特徴とする請求項２記載の多数決回路。
【請求項４】
前記第１入力信号は、絶対値が同じ正負いずれかの値を有し、
前記第１ソート回路は、前記第１入力信号が有する値の昇順に各前記第１入力信号を並び替えて出力し、
前記第１選択回路は、前記第１入力信号の個数の２倍の個数の信号を受け取って昇順に並び替えるとともに、その並び替えた信号のうち奇数番目の全てを選択して出力し、
前記端子は、前記第１選択回路の各番目の出力のうち後半の最初のものを前記多数決の結果として出力する
ことを特徴とする請求項１記載の多数決回路。
【請求項５】
前記第１入力信号は、絶対値が同じ正負いずれかの値を有し、
前記第１ソート回路は、前記第１入力信号が有する値の昇順に各前記第１入力信号を並び替えて出力し、
前記第１選択回路は、前記第１入力信号の個数の２倍の個数の信号を受け取って昇順に並び替えるとともに、その並び替えた信号のうち偶数番目の全てを選択して出力し、
前記端子は、前記第１選択回路の各番目の出力のうち前半の最後のものを前記多数決の結果として出力する
ことを特徴とする請求項１記載の多数決回路。
【請求項６】
前記第１入力信号は、絶対値が同じ正負いずれかの値を有し、
前記第１ソート回路は、前記第１入力信号が有する値の降順に各前記第１入力信号を並び替えて出力し、
前記第１選択回路は、前記第１入力信号の個数の２倍の個数の信号を受け取って降順に並び替えるとともに、その並び替えた信号のうち奇数番目の全てを選択して出力し、
前記端子は、前記第１選択回路の各番目の出力のうち前半の最後のものを前記多数決の結果として出力する
ことを特徴とする請求項１記載の多数決回路。
【請求項７】
前記第１ソート回路は、前記第１入力信号が有する値の降順に各前記第１入力信号を並び替えて出力し、
前記第１選択回路は、前記第１入力信号の個数の２倍の個数の信号を受け取って降順に並び替えるとともに、その並び替えた信号のうち偶数番目の全てを選択して出力し、
前記端子は、前記第１選択回路の各番目の出力のうち後半の最初のものを前記多数決の結果として出力する
ことを特徴とする請求項１記載の多数決回路。
【請求項８】
前記第１ソート回路はさらに、前記第１重みの半分の第２重みを有する第２入力信号を前記入力信号として前記第１入力信号と同じ個数受け取り、
前記多数決回路はさらに、前記第１ソート回路が前記第１入力信号と前記第２入力信号のいずれを受け取るかを選択するセレクタを備え、
前記第１選択回路はさらに、前記第２入力信号を並び替えることにより得られる偶数番目の信号全てまたは奇数番目の信号全てを選択し、前記第１選択回路に対する再帰的入力として出力する
ことを特徴とする請求項２記載の多数決回路。
【請求項９】
前記第１ソート回路は、２のべき乗の前記第１重みを有する前記第１入力信号を受け取って並び替えるように構成され、
前記第１選択回路は、前記第１重みの２倍の重みを有する信号を出力するように構成されている
ことを特徴とする請求項１記載の多数決回路。
【請求項１０】
前記多数決回路は、信号値の総和が０となる複数の信号を初期入力信号として受け取る回路を備える
ことを特徴とする請求項１記載の多数決回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力信号の多数決をとる多数決回路に関する。
【背景技術】
【０００２】
種々の物理現象や社会現象は、相互作用モデルで表現することができる。相互作用モデルとは、モデルを構成する複数個のノードと、ノード間の相互作用、さらに必要であればノード毎のバイアスによって定義されるモデルである。物理学や社会科学において種々のモデルが提案されているが、いずれも相互作用モデルの１形態であると解釈できる。【０００３】
これらの相互作用モデルの多くは、モデル内の演算に多数決関数を含む。下記非特許文献１は、多数決関数の演算を実行するためのアルゴリズムや回路を提案している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】"20k-spin Ising chip for combinational optimization problem with CMOS annealing", ISSCC Dig. Tech. Papers (2015).
【発明の概要】
【発明が解決しようとする課題】
【０００５】
多数決回路は、例えば加算回路と比較器によって実装することができる。しかし、多数決関数に対して与える入力値域や個数が増加するのにともなって、加算回路の実装面積が増加し、スケーラビリティやエネルギー効率が低下する。【０００６】
非特許文献１においては、加算回路を用いずに多数決演算を実現するため、アナログ回路を用いた多数決関数を実現している。この回路は、回路内の２系統間の電圧差を検出して多数決演算を実現する。【０００７】
多数決回路を構成するトランジスタは、全て等しい特性を持つことが理想的である。しかし実際は、素子毎に固有のばらつきが存在する。電流のばらつきは、トランジスタサイズＷ／Ｌが小さくなるにつれて増加する。よって、多数決の結果が反転しないようにばらつきも考慮しなければならない。このように加算回路を用いず、低面積な回路で、多数決関数に対して与える入力値域や個数が増加した場合において、多数決回路を実装することは困難であった。【０００８】
本発明は上記のような課題に鑑みてなされたものであり、安価かつ容易に製造でき、相互作用モデルにおける計算のため必要な多数決関数を処理することができる多数決回路を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明に係る多数決回路は、バイトニックソート回路を用いて、入力信号の総和を２のべき乗の値に丸めることにより、多数決関数の処理を簡易化する。
【発明の効果】
【００１０】
本発明に係る多数決回路は、入力値範囲や個数が多い場合であっても、小さい実装面積で多数決関数を処理することができる。本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【図面の簡単な説明】
【００１１】
【図１】実施形態１に係る多数決回路１の入出力を説明する図である。
【図２Ａ】重み付き入力を演算する回路の構成図である。
【図２Ｂ】多数決回路１に対して重み付き信号を入力する構成を示す図である。
【図３】並び替え回路３の１例を示す図である。
【図４】バイトニックソートに基づいて８本の信号ｘk（１≦ｋ≦８）を並び替える回路の構成例である。
【図５】８ソート回路の構成例である。
【図６】４ソート回路６と８マージ回路７を組み合わせた回路９の構成例を示す図である。
【図７】（Ｄ，Ｌ）＝（２，４）の場合における多数決回路１の構成例である。
【図８】実施形態３に係る多数決回路の回路図である。
【発明を実施するための形態】
【００１２】
＜実施の形態１：多数決回路の入出力＞
図１は、本発明の実施形態１に係る多数決回路１の入出力を説明する図である。多数決回路１は、ｈｉｇｈまたはｌｏｗの電圧が印加された信号を入力信号として受け取る。この入力信号に対してそれぞれ重みが定義される。多数決回路１は、各入力信号の電圧および重みを考慮して、多数決の結果を表す信号を出力する。以下具体的な動作を説明する。
【００１３】
多数決回路１は、重みｗk（整数）の信号ｘk（１≦ｋ≦Ｌ）を受け取る。信号の電圧はｈｉｇｈまたはｌｏｗであり、電圧に応じて値を与える関数ｆ（ｘ）を定義する。ｆ（ｘ）は、信号ｘがｈｉｇｈならばｆ（ｘ）＝＋１、ｌｏｗならばｆ（ｘ）＝−１を返す。
【００１４】
下記式１で定義される値Ｓを導入する。Ｓ≧０ならば多数決回路１は多数決の結果を表す信号ｙとして、ｈｉｇｈ、Ｓ＜０ならばｌｏｗを出力する。
【００１５】
【数１】
2017090122.tif 000003
【００１６】
例えばＬ＝４、（ｘ1，ｗ1）＝（ｈｉｇｈ，１）、（ｘ2，ｗ2）＝（ｌｏｗ，−２）、（ｘ3，ｗ3）＝（ｌｏｗ，３）、（ｘ4，ｗ4）＝（ｈｉｇｈ，４）のときＳ＝＋４である。ゆえに多数決回路１はｈｉｇｈを出力する。
【００１７】
重みｗkに応じて信号ｗk［ｉ］（０≦ｉ≦Ｄ）を以下の通り定義する。説明の簡易のため、重みは奇数とする。ｗk＞０の場合、ｗk［ｉ］（０≦ｉ＜Ｄ）は、（ｗk−１）／２を２進数表記したとき下位ビットから（ｉ＋１）番目の値が１ならばｈｉｇｈ、０ならばｌｏｗと定める。また、ｗk［Ｄ］＝ｈｉｇｈと定める。例えばｗk＝５、Ｄ＝２のとき、ｗk［２］＝ｈｉｇｈである。また（ｗk−１）／２＝２を２進数表記すると（２）10＝（１０）2であるため、ｗk［０］＝ｌｏｗ、ｗk［１］＝ｈｉｇｈとなる。
【００１８】
前述の定義より、下記式２が成り立つ。
【数２】
2017090122.tif 000004
【００１９】
式２を整理すると下記式３を得る。
【数３】
2017090122.tif 000005
【００２０】
ｗk＜０の場合、信号ｗk［ｉ］（０≦ｉ≦Ｄ）は（−ｗk）＞０である場合の各ビットを反転させたものと定義する。例えばｗk＝−５、Ｄ＝２のとき、ｗk［０］＝ｈｉｇｈ、ｗk［１］＝ｗk［２］＝ｌｏｗである。ｗk＜０の場合も、式３は明らかに成り立つ。
【００２１】
図２Ａは、重み付き入力を演算する回路の構成図である。ＸＮＯＲ（排他的論理和の否定）回路２は、信号ｘkとｗk［ｉ］（０≦ｉ≦Ｄ）を受け取り、ｘk［ｉ］を出力する。信号ｘk［ｉ］の重みは２iと定める。ｘk＝ｈｉｇｈのとき、ｆ（ｘk）＝１かつｆ（ｘk［ｉ］）＝ｆ（ｗk［ｉ］）となり、式３と併せて下記式４が成立する。一方、ｘk＝ｌｏｗのとき、ｆ（ｘk）＝−１かつｆ（ｘk［ｉ］）＝−ｆ（ｗk［ｉ］）で、式３と併せて式４が成立する。つまり常に式４が成り立つ。
【００２２】
【数４】
2017090122.tif 000006
【００２３】
図２Ｂは、多数決回路１に対して重み付き信号を入力する構成を示す図である。重みが奇数の場合を説明したが、重みが偶数の場合は、重みを２つの奇数の和として扱えば良い。例えば重みｗk＝４の信号が多数決回路に入力することは、ｗk+＝３およびｗk-＝１なる重みを持つ信号が多数決回路に入力することと捉えられる。よって重みが整数の場合、式４によれば、入力信号の重みは２の冪乗に限定することができる。以降、多数決回路１の入力信号はｘk［ｉ］（１≦ｋ≦Ｌ、０≦ｉ≦Ｄ）、Ｌは偶数とする。
【００２４】
＜実施の形態１：多数決回路１を構成する並び替え回路の構成＞
多数決回路１は、以下に説明する並び替え回路を用いて多数決関数を処理する。並び替え回路とは、複数の信号を受け取り、各信号が有する信号値にしたがって並び替える回路である。並び替え回路の入力信号をｘkと表す。
【００２５】
図３は、並び替え回路３の１例を示す図である。並び替え回路３は、２本の信号ｘ1、ｘ2を受け取り、各信号線の電圧にしたがって並び替え、その並び替えの結果を表す信号ｙ1、ｙ2を出力する。以降、並び替え回路は値が昇順になるよう並び替えるものとする。例えば２本の信号を並び替える回路は、図３に示すようにＡＮＤゲート４とＯＲゲート５を１個ずつ用いて実現される。
【００２６】
図４は、バイトニックソートに基づいて８本の信号ｘk（１≦ｋ≦８）を並び替える回路の構成例である。バイトニックソートは、より多くの本数の信号を並び替えるアルゴリズムとして知られている。回路６は、４本の信号を受け取って並び替える回路である。回路７は、昇順に並び替えられた４本の信号を２組受け取り、計８本の信号を並び替えて出力する。
【００２７】
以降、Ｎ本の信号を受け取って並び替えＮ本の信号を出力する回路をＮソート回路と呼ぶ。また、Ｎ／２本の並び替えられた信号を２組受け取って並び替える回路をＮマージ回路と呼ぶ。回路６は４ソート回路であり、回路７は８マージ回路である。
【００２８】
図４に示した通り、８ソート回路は、２個の４ソート回路および１個の８マージ回路によって構成される。このように、バイトニックソートで並び替えるＮソート回路は、並列に並べた２個の（Ｎ／２）ソート回路の後段に１個のＮマージ回路を配置することによって構成することができる。
【００２９】
図５は、８ソート回路の構成例である。図３に示した回路３（２ソート回路）を用いて、図５のように８ソート回路を構成することができる。領域８に含まれる回路３は、並列に動作することができる。したがって、回路１の処理時間を１段と表すとき、４ソート回路の処理時間は３段、４マージ回路の処理時間は３段である。一般に、Ｎマージ回路はｌｏｇ（Ｎ）、Ｎソート回路はｌｏｇ2（Ｎ）（ｌｏｇ2（Ｎ）＋１）／２の段数を要する。
【００３０】
＜実施の形態１：多数決回路１の動作原理＞
多数決回路１は、重み付き信号の総和Ｓを２のべき乗の数値に丸め込むことにより、バイトニックソート回路を用いて多数決関数を処理できるようにする。具体的には、重み付き入力信号をバイトニックソート回路によって並び替える過程で失われる重み総和がある範囲内に収まるように、ソート回路を構成する。以下、そのための動作原理を説明する。
【００３１】
Ｎソート回路の入力信号ｘkおよび出力信号のｙk（１≦ｋ≦Ｎ）の和に関し、下記式５が成り立つ。
【００３２】
【数５】
2017090122.tif 000007
【００３３】
ｆ（ｙk）＋ｆ（ｙk+1）と２ｙkの大小関係を比較する。｛ｆ（ｙk）、ｆ（ｙk+1）｝＝｛−１、−１｝、｛＋１、＋１｝のときｆ（ｙk）＋ｆ（ｙk+1）＝２ｙkが成り立つ。｛ｆ（ｙk）、ｆ（ｙk+1）｝＝｛−１、＋１｝のとき、ｆ（ｙk）＋ｆ（ｙk+1）−２＝２ｆ（ｙk）である。ｆ（ｙk）≦ｆ（ｙk+1）であるため｛ｆ（ｙk）、ｆ（ｙk+1）｝＝｛＋１、−１｝は有り得ない。また、ソート回路が入力信号を昇順に並び替える場合、出力信号の値が−１から＋１に切り替わる箇所は０箇所または１箇所のみである。したがって、｛ｆ（ｙk）、ｆ（ｙk+1）｝＝｛−１、＋１｝なる自然数ｋは高々１つである。以上から、以下の原則が成り立つ。
【００３４】
（原則１）全ての｛ｆ（ｙk）、ｆ（ｙk+1）｝のペアが｛−１、−１｝または｛＋１、＋１｝のいずれかである場合、例えば出力信号の奇数番目のみを取り出してその総和を２倍すると、出力信号全体の総和と等しくなる。｛ｆ（ｙk）、ｆ（ｙk+1）｝のペアのいずれかに｛−１、＋１｝が含まれている場合、奇数番目の総和の方が小さくなる。したがって奇数番目の総和が出力信号全体の総和を超えることはない。偶数番目を取り出す場合も同様に考えることができるが、説明の簡易のため本実施形態１では奇数番目を取り出すことを前提とする。
【００３５】
（原則２）｛ｆ（ｙk）、ｆ（ｙk+1）｝のペアのなかで｛−１、＋１｝となる可能性があるのは、１組のみである。したがって、奇数番目の総和が出力信号全体の総和よりも小さいとしても、両者の差分はその１組によって生じる−２に過ぎない。
【００３６】
原則１と原則２により、下記式６が成り立つ。原則１は式６の右半分に対応し、原則２は式６の左半分に対応する。なおここでは重みについては考慮していないが、重みがｗである場合の関係については後述する。
【００３７】
【数６】
2017090122.tif 000008
【００３８】
式５と式６から、下記式７が得られる。
【００３９】
【数７】
2017090122.tif 000009
【００４０】
さらに重みｗについて考慮する。Ｎソート回路が受け取る信号の重みをすべてｗとする。このとき入力信号の重みの総和Ｕは下記式８で表される。
【００４１】
【数８】
2017090122.tif 000010
【００４２】
Ｎソート回路が出力する信号において、奇数番目（ｙ1，ｙ3，・・・）のみを取り出してその総和を２倍する。重みｗは共通なので、奇数番目の総和Ｖは下記式９によって求められる。式９は、出力信号の奇数番目のみ取り出して重みを２倍（すなわち２ｗ）に増やした上で加算することに相当する。
【００４３】
【数９】
2017090122.tif 000011
【００４４】
式７、式８、式９より、Ｕ−２ｗ≦Ｖ≦Ｕを得る。つまり重みｗの信号を昇順に並び替え、奇数番目のみを取り出してその総和を２倍した場合、奇数番目の総和の２倍は出力信号の総和よりも増えることはなく、かつ奇数番目の総和の２倍の方が少ないとしても両者の差分は２ｗに過ぎない。
【００４５】
多数決回路１は、以上の原理を利用して、入力信号の総和を２のべき乗の数値に丸め込む。これを実現するため、Ｎ／２本の並び替えられた信号を２組受け取って昇順に並び替え、奇数番目のみを抽出する回路を設ける。以降ではこの回路のことをＮマージ・選択回路と呼ぶ。
【００４６】
図６は、４ソート回路６と８マージ回路７を組み合わせた回路９の構成例を示す図である。回路８の入力信号ｘk（１≦ｋ≦８）の重みをｗ、出力信号ｙk（ｋ＝１、３、５、７）の重みを２ｗとした場合、奇数番目の総和は出力信号全体の総和以下であり、かつその差分は高々２ｗである。
【００４７】
＜実施の形態１：多数決回路１の演算手順＞
図７は、（Ｄ，Ｌ）＝（２，４）の場合における多数決回路１の構成例である。信号ｓk（１≦ｋ≦４）は最初のマージ・選択回路に対する入力として便宜上与えるものであり、本来の入力信号の総和を変えることのないようにセットする。例えばｓ1＝ｓ2＝ｌｏｗ、ｓ3＝ｓ4＝ｈｉｇｈと定め、重みを１とする。
【００４８】
信号ｘk［０］（１≦ｋ≦４）の重みは１である。この信号を入力とする４ソート回路６１は重み１の信号４本を出力する。８マージ・選択回路９１は、昇順に並び替えられた重み１の信号４本を２組受け取り、重み２の信号４本を出力する。回路９１の演算によって失われる信号総和は、高々２である。
【００４９】
信号ｘk［１］の重みは２である。４ソート回路６２は信号ｘk［１］を受け取って昇順に並び替え、重み２の信号４本を出力する。８マージ・選択回路９２は、８マージ・選択回路９１が出力する昇順に並んだ重み２の信号４本と、４ソート回路６２が出力する昇順に並んだ重み２の信号４本を受け取り、重み４の信号４本を出力する。回路９２の演算によって失われる信号総和は、高々４である。以降も同様である。
【００５０】
図７に示す回路構成において、信号総和が失われる箇所は８マージ・選択回路のみである。８マージ・選択回路９１〜９３それぞれによって失われる信号総和は、高々２＋４＋８＝１４である。
【００５１】
８マージ・選択回路９３は、重みが８の信号を出力し、その本数は偶数である。ゆえに、８マージ・選択回路９３の出力信号の総和Ｔは必ず１６の倍数である。
【００５２】
入力信号ｘk［ｉ］（１≦ｋ≦４、０≦ｉ≦２）の総和をＳとすると、下記式１０が成り立つ。
【００５３】
【数１０】
2017090122.tif 000012
【００５４】
符号を表す関数として下記式１１を定義する。
【００５５】
【数１１】
2017090122.tif 000013
【００５６】
Ｓ≧０のとき、Ｔは−１４以上かつ１６の倍数である。よってＴ≧０が成り立ち、ｓｇｎ+（Ｓ）＝ｓｇｎ+（Ｔ）が成り立つ。Ｓ＜０のときＴ＜０となるため、この場合もｓｇｎ+（Ｓ）＝ｓｇｎ+（Ｔ）を満たす。以上より、常にｓｇｎ+（Ｓ）＝ｓｇｎ+（Ｔ）が成り立つので、入力信号の総和Ｓの符号と８マージ・選択回路９３の出力信号の総和Ｔの符号は必ず一致している。すなわち、多数決結果はＴの符号を表すｓｇｎ+（Ｔ）のみによって判定することができる。
【００５７】
８マージ・選択回路９３の出力信号は、昇順に並び替えられている。よってＴ≧０の場合、８マージ・選択回路９３の出力信号４本のうち３番目は必ずｈｉｇｈである。同様にＴ＜０の場合は、３番目の信号が必ずｌｏｗである。よって、８マージ・選択回路９３が出力する信号の３番目をｙとするとき、ｓｇｎ+（Ｔ）＝ｆ（ｙ）となる。すなわち多数決回路１は、８マージ・選択回路９３の３番目の信号を入力信号の多数決の結果として取り出す。例えば当該信号を取り出す端子１００などを設けることができる。
【００５８】
＜実施の形態１：まとめ＞
本実施形態１に係る多数決回路１によれば、安価かつ容易に製造でき、例えばイジングモデルなどのような任意の相互作用モデルの計算が要求する多数決関数の演算を実行することができる。
【００５９】
本実施形態１に係る多数決回路１は、４ソート回路によって入力信号ｘkを並び替え、８マージ・選択回路によって奇数番目のみを取り出す。これにより、入力信号の総和を大きく損なうことなく、最終段において入力信号の多数決を得ることができる。したがって加算回路を用いることなく、比較的少ない実装面積で多数の入力信号の多数決を得ることができる。
【００６０】
＜実施の形態２＞
実施形態１の図７において、（Ｄ，Ｌ）＝（２，４）の回路構成を示した。Ｌが増減しても、同様の回路構成によって多数決関数を処理できることは明らかである。Ｄについても同様に、一般の自然数Ｄにおいて図７と同様の回路構成が成立する。以下このことを具体的な数式により説明する。
【００６１】
Ｄは任意の自然数とする。多数決回路１の入力信号の重みは１、２、４、・・・、２Dであり、入力信号の重み和はＳ’と表す。多数決回路１内にマージ・選択回路は（Ｄ＋１）回現れ、これらによって失われる信号総和の最大Ｗ’は下記式１２により求められる。
【００６２】
【数１２】
2017090122.tif 000014
【００６３】
計算フローの最後に現れるマージ・選択回路の出力信号の重み和Ｔ’は、下記式１３を満たす。
【００６４】
【数１３】
2017090122.tif 000015
【００６５】
計算フローの最後に現れるマージ・選択回路は、重み２D+1の信号を出力し、この本数は偶数である。よって重み和Ｔ’は２D+2の倍数である。また式１０より、Ｗ’＜２D+2が成り立つ。よって下記式１４が成り立つ。
【００６６】
【数１４】
2017090122.tif 000016
【００６７】
つまり重み和Ｔ’は式１３を満たし、かつ２D+2の倍数である。この条件を満たす整数Ｔ’は一意に定まる。そして前述と同様の議論に基づき、ｓｇｎ+（Ｓ’）＝ｓｇｎ+（Ｔ’）が成り立つことが示される。
【００６８】
よって、一般のＤおよびＬにおいて、図７の計算フローを拡張することにより、多数決回路として機能する。このとき、ＤおよびＬの値に応じて多数決回路の構成も変更が必要である。例えばＬ＝８の場合は、マージ・選択回路から出力する８本の信号のうち、５本目の信号（すなわち各番目の出力信号のうち後半の最初）で多数決を判定する。
【００６９】
＜実施の形態３＞
図８は、本発明の実施形態３に係る多数決回路の回路図である。図７は同様の回路構成を繰り返し用いているので、その繰り返し部分について同じ回路を再利用することにより実装面積を抑えることができる。そこで本実施形態３においては、図８に示すように４ソート回路６４を繰り返し用いるとともに、８マージ選択回路９４の出力を入力側へ戻すことにより、再帰的回路構成を形成した。以下図８に示す回路の動作を説明する。
【００７０】
信号線ＩＮＩＴがｈｉｇｈのとき、ＡＮＤゲート１０はｌｏｗ、ＯＲゲート１１はｈｉｇｈを常に出力する。一方、信号線ＩＮＩＴがｌｏｗの場合、ＡＮＤゲート１０とＯＲゲート１１はいずれも、受け取る２本の信号のうち信号線ＩＮＩＴではない信号をそのまま出力する。
【００７１】
複数のマルチプレクサ１２は、信号線ＳＥＬに従って多数決回路１に入力する信号ｘk［ｉ］（１≦ｋ≦Ｌ、０≦ｉ≦Ｄ）から計Ｌ本の信号を選択する。
【００７２】
始めに、マルチプレクサ１２は重み１の信号であるｘk［０］を選択する。すると４ソート回路６４は昇順に並び替えた重み１の信号４本を出力する。同時に、信号線ＩＮＩＴをｈｉｇｈにするタイミングを調節することにより、ＡＮＤゲート１０からｌｏｗ、ＯＲゲート１１からｈｉｇｈを出力し、８マージ・選択回路９４が並び替えられた信号４本を２組受け取ることができる。これは図７に示す計算フローにおける回路９１と同等の演算である。
【００７３】
重み１の信号８本を受け取った回路９４は、重み２の信号４本を出力する。信号線ＩＮＩＴをｌｏｗにすると、回路９４が出力した信号４本は再び回路９４の入力に与えられることとなる。回路９４の出力が昇順に並んでいることは明らかである。
【００７４】
回路９４が論理演算を実行している間に信号線ＳＥＬを制御し、回路６４に対して重み２の信号ｘk［１］を与える。これにより、ゲート１０、１１が出力する重み２の信号４本と、回路６４が出力する重み２の信号４本は、同時に回路９４に入力する。
【００７５】
以降、同様に信号線ＩＮＩＴおよびＳＥＬを制御することにより、図８の回路によって図７と同じ計算を実施することができる。回路９４が出力する４本の信号のうち３番目を得ることにより、多数決の結果を得る。
【００７６】
＜本発明の変形例について＞
以上の実施形態においては、便宜上その必要があるときは、複数のセクションまたは実施の形態に分割して説明したが、特に明示した場合を除き、それらは互いに無関係なものではなく、一方は他方の一部または全部の変形例、詳細、補足説明等の関係にある。また以上の実施形態において、要素の数等（個数、数値、量、範囲等を含む）に言及する場合、特に明示した場合および原理的に明らかに特定の数に限定される場合等を除き、その特定の数に限定されるものではなく、特定の数以上でも以下でもよい。
【００７７】
以上の実施形態において、その構成要素（要素ステップ等も含む）は、特に明示した場合および原理的に明らかに必須であると考えられる場合等を除き、必ずしも必須のものではないことは言うまでもない。同様に以上の実施形態において、構成要素等の形状、位置関係等に言及するときは、特に明示した場合および原理的に明らかにそうでないと考えられる場合等を除き、実質的にその形状等に近似または類似するもの等を含むものとする。このことは、上記数値および範囲についても同様である。
【００７８】
以上の実施形態は、本発明を分かり易く説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施の形態の構成の一部を他の実施の形態の構成に置き換えることが可能であり、また、ある実施の形態の構成に他の実施の形態の構成を加えることも可能である。また、各実施の形態の構成の一部について、他の構成の追加・削除・置換をすることが可能である。例えば以上の実施形態におけるＡＮＤゲート１０およびＯＲゲート１１は、マルチプレクサに置き換えることができる。
【００７９】
以上の実施形態においては、並び替え回路は入力信号を昇順に並び替え、マージ・選択回路は奇数番目を抽出することとした。昇順ではなく例えば降順に並び替えてもよい。この場合はマージ・選択回路によって信号の重み和は増加する。よって多数決回路に対して入力する信号の重み和Ｓと、最後のマージ・選択回路が出力する信号の重み和Ｔに関して、ｓｇｎ-（Ｓ）＝ｓｇｎ-（Ｔ）が成り立つ。ただし、ｓｇｎ-（ｘ）は下記式１５で定義される関数である。
【００８０】
【数１５】
2017090122.tif 000017
【００８１】
このとき、多数決の判定に用いるマージ・選択回路の出力信号は以上の実施形態とは異なる。例えばＬ＝４の場合、マージ・選択回路が出力する４本の信号のうち、２本目の信号ｙ2（すなわち各番目の出力信号のうち前半の最後）を用いる。なぜならばｓｇｎ-（Ｔ）＝ｆ（ｙ2）が成り立つためである。
【００８２】
マージ・選択回路は奇数番目でなく偶数番目を抽出してもよい。並び替え回路が昇順に並び替えるとき、マージ・選択回路が偶数番目を抽出すると信号の重み和は増加する。以降は前述と同様である。
【００８３】
並び替え回路が降順に並び替え、マージ・選択回路が偶数番目を抽出することも考えられる。この場合は信号の重み和は減少するので、多数決回路の構成は実施形態１と同様である。
【符号の説明】
【００８４】
１：多数決回路、２：ＸＮＯＲ回路、３：並び替え回路、６１〜６４：４ソート回路、９１〜９４：８マージ選択回路。
【図１】
2017090122.tif 000018
【図２Ａ】
2017090122.tif 000019
【図２Ｂ】
2017090122.tif 000020
【図３】
2017090122.tif 000021
【図４】
2017090122.tif 000022
【図５】
2017090122.tif 000023
【図６】
2017090122.tif 000024
【図７】
2017090122.tif 000025
【図８】
2017090122.tif 000026
【国際調査報告】
2017090122.tif 000027
2017090122.tif 000028