(57)【要約】【課題】規則性のある回路構成で実現できるガロア体乗算回路を提供する。【解決手段】ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）のｍビットによりベクトル表現される２つの元の乗算を行なうガロア体乗算回路であって、前記乗算の積の要素を演算する要素演算部１０が、前記２つの元のうち一方の元の各ビットと、前記２つの元のうち他方の元の各ビットとまたは各ビットの組み合わせとの論理積演算を並列に行うｍ個の論理積演算部１１と、前記ｍ個の論理演算部の演算結果を排他的論理和演算する加算部１２と、を有する。【選択図】図１１
2014082575.tif 000002
【特許請求の範囲】
【請求項１】
ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）のｍビットによりベクトル表現される２つの元の乗算を行なうガロア体乗算回路であって、
前記乗算の積の要素を演算する要素演算部が、
前記２つの元のうち一方の元の各ビットと、前記２つの元のうち他方の元の各ビットとまたは各ビットの組み合わせとの論理積演算を並列に行うｍ個の論理積演算部と、
前記ｍ個の論理積演算部の演算結果を排他的論理和演算する加算部と、を有することを特徴とするガロア体乗算回路。
【請求項２】
前記２つの元の乗算を行う際、乗算結果のうちの下位ｍビット以外の上位ビットの要素についてそれぞれ排他的論理和演算して求め、その演算結果を予め与えられる原始多項式により、下位ｍビットのベクトル表現に変換し、変換後のｍビットの各要素を、乗算結果のうちの下位ｍビットの要素についてそれぞれ排他的論理和演算して求めた演算結果の各要素と排他的論理和演算して、前記２つの元の乗算結果を前記ｍ個の加算部からそれぞれ出力することを特徴とする請求項１に記載のガロア体乗算回路。
【請求項３】
前記他方の元のビットのうち前記一方の元のビットを同一とするビットを排他的論理和演算して前記各ビットの組み合わせを求めることを特徴とする請求項２に記載のガロア体乗算回路。
【請求項４】
前記要素演算部ｍ個と、前記各ビットの組み合わせを演算する排他的論理和回路から構成される組合せ回路とを一方向に並べ、
前記２つの元のうち一方の元を外部から各要素演算部へ入力するｍ本の第１配線と、
前記２つの元のうち他方の元を外部から各要素演算部、及び前記組合せ回路へ入力するｍ本の第２配線と、
前記他方の元の組み合わせを各要素演算部に対して出力するｍ本の第３配線と、を備え、
前記第１配線、前記第２配線、前記第３配線は、前記要素演算部、及び前記組合せ回路を並べた方向に対して並行に配線され、同じく並べた方向に対して並行に外部へ前記要素演算部ｍ個の乗算結果を出力することを特徴とする請求項１から請求項３いずれか一項に記載のガロア体乗算回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガロア体乗算回路に関する。
【背景技術】
【０００２】
ガロア体ＧＦ（２ｍ）の２つの元の乗算を行う場合、この２つの元を多項式表現（ｘｍ−１×Ｘｍ−１＋ｘｍ−１×Ｘｍ−１＋…＋ｘ０、ｙｍ−１×Ｘｍ−１＋ｙｍ−１×Ｘｍ−１＋…＋ｙ０）を用いてそれぞれ表す。そして、ガロア体乗算回路では、各項（次数）ごとに要素演算部が設けられ、この要素演算部において、一方の元の係数（ベクトル表示の場合の成分）と他方の元の係数との乗算を行い、乗算結果の排他的論理和を求める（特許文献１参照）。
【０００３】
例えば、Ｘ１に対応して設けられる要素演算部では、ｘ０とｙ１との論理積（ｘ０ｙ１；ｘ０×ｙ１とも表す）を求めるアンド回路、ｘ１とｙ０との論理積（ｘ０ｙ１）を求めるアンド回路、２つの論理積の排他的論理和（ｘ０ｙ１＋ｘ０ｙ１；ｘ０ｙ１＾ｘ０ｙ１とも表す）を求めるＥＸＯＲ（Ｅｘｃｌｕｓｉｖｅ−ＯＲ）回路を備える。また、Ｘ２に対応して設けられる要素演算部では、ｘ０ｙ２、ｘ１ｙ１、ｘ２ｙ０をそれぞれ求めるアンド回路、ｘ０ｙ２＾ｘ１ｙ１を求めるＥＸＯＲ回路、（ｘ０ｙ２＾ｘ１ｙ１）＾ｘ２ｙ０を求めるＥＸＯＲ回路を備える。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平６−３１４９７９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述したガロア体乗算回路では、要素演算部が各次数（Ｘのべき乗）に対応して設けられ、この要素演算部において、内部回路を構成する論理ゲート（アンド回路、及びＥＸＯＲ回路）の個数が、要素演算部毎に異なった個数となってしまう。また、要素演算部において、論理ゲートの出力と入力との間の接続点（中間ノード）の個数が異なったものとなってしまう。
そのため、ガロア体乗算回路を、例えば半導体装置上に配置する場合、ガロア体乗算回路を構成する要素演算部毎に回路規模が異なり、要素演算部に対応するレイアウト面積も要素演算部毎に異なった面積となってしまう。これによって、ガロア体乗算回路を半導体装置上に面積効率を上げて効率よく配置することが困難になるという問題がある。
【０００６】
そこで本発明が解決しようとする課題は、ガロア体乗算回路を構成する要素演算部毎に論理ゲートの個数を同一とし、また入力信号の本数を同一とし、規則性のある回路構成により実現できるガロア体乗算回路を提供することにある。
【課題を解決するための手段】
【０００７】
本発明のガロア体乗算回路は、ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）のｍビットによりベクトル表現される２つの元の乗算を行なうガロア体乗算回路であって、前記乗算の積の要素を演算する要素演算部が、前記２つの元のうち一方の元の各ビットと、前記２つの元のうち他方の元の各ビットとまたは各ビットの組み合わせとの論理積演算を並列に行うｍ個の論理積演算部と、前記ｍ個の論理演算部の演算結果を排他的論理和演算する加算部と、を有することを特徴とする。
【０００８】
また、本発明のガロア体乗算回路において、前記２つの元の乗算を行う際、乗算結果のうちの下位ｍビット以外の上位ビットの要素についてそれぞれ排他的論理和演算して求め、その演算結果を予め与えられる原始多項式により、下位ｍビットのベクトル表現に変換し、変換後のｍビットの各要素を、乗算結果のうちの下位ｍビットの要素についてそれぞれ排他的論理和演算して求めた演算結果の各要素と排他的論理和演算して、前記２つの元の乗算結果を前記ｍ個の加算部からそれぞれ出力することを特徴とする。
【０００９】
また、本発明のガロア体乗算回路において、前記他方の元のビットのうち前記一方の元のビットを同一とするビットを排他的論理和演算して前記各ビットの組み合わせを求めることを特徴とする。
【００１０】
また、本発明のガロア体乗算回路において、前記要素演算部ｍ個と、前記各ビットの組み合わせを演算する排他的論理和回路から構成される組合せ回路とを一方向に並べ、前記２つの元のうち一方の元を外部から各要素演算部へ入力するｍ本の第１配線と、前記２つの元のうち他方の元を外部から各要素演算部、及び前記組合せ回路へ入力するｍ本の第２配線と、前記他方の元の組み合わせを各要素演算部に対して出力するｍ本の第３配線と、を備え、前記第１配線、前記第２配線、前記第３配線は、前記要素演算部、及び前記組合せ回路を並べた方向に対して並行に配線され、同じく並べた方向に対して並行に外部へ前記要素演算部ｍ個の乗算結果を出力することを特徴とする。
【発明の効果】
【００１１】
本発明のガロア体乗算回路では、要素演算部において、２つの元のうち一方の元の各ビットと、２つの元のうち他方の元の各ビットとまたは各ビットの組み合わせとの論理積演算を並列に行うｍ個の論理積演算部と、ｍ個の論理演算部の演算結果を排他的論理和演算する加算部とを設けた。そのため、２つの元のうち他方の元の各ビットの組み合わせを要素演算部毎に変えることにより、ガロア体乗算回路に入力する他方の元の各ビットとまたは各ビットの組み合わせとのビット数と、２つの元のうち一方の元のビット数とを同じにすることができる。従って、ガロア体乗算回路における論理積演算を並列に行う論理ゲート（論理積演算部）の個数をｍ個にでき、また、ｍ個の論理演算部の演算結果を排他的論理和演算する加算部の論理ゲートの個数を（ｍ−１）個にできる。すなわち、要素演算部毎に、論理ゲートの個数を同一とし、入力信号の本数を同一とできる。また、内部ノードの個数も同一とできる。これにより、従来に比べて規則性のある回路構成により実現できるガロア体乗算回路を提供することができる。よって、ガロア体乗算回路を、例えば半導体装置上に構築する場合に、面積効率を上げて効率よく配置することが容易になる。
【図面の簡単な説明】
【００１２】
【図１】αｉ＋ｊのベクトル成分を示した図である。
【図２】乗算結果Ｚ［８：０］の各ビットを、ＥＸＯＲ回路を用いてａ０〜ａ１４から演算する場合の論理式を示す。
【図３】Ｚ［０］、及びＺ［１］を演算する要素演算部の構成を示す。
【図４】Ｚ［２］、及びＺ［３］を演算する要素演算部の構成を示す。
【図５】Ｚ［４］を演算する要素演算部の構成を示す。
【図６】Ｚ［５］を演算する要素演算部の構成を示す。
【図７】Ｚ［６］を演算する要素演算部の構成を示す。
【図８】Ｚ［７］、及びＺ［８］を演算する要素演算部の構成を示す。
【図９】Ｘ［８：０］とＹ［８：０］との乗算によりＺ［８：０］を出力するときの条件を示した図である。
【図１０】ｙ［０］〜ｙ［８］の組合せから、ｐ［０］〜ｐ［８］を求める際の論理式である。
【図１１】ガロア体乗算回路における要素演算部１０の回路構成を示す図である。
【図１２】ｐ生成回路２０の回路構成を示す図である。
【図１３】ガロア体乗算回路１００のブロック構成を示す図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して、本発明の実施の形態について説明する。本発明の実施の形態では、ガロア体ＧＦ（２９）の乗算について説明する。ここで、ガロア体ＧＦ（２９）の元として、２つの元αｉ、αｊの乗算を行なう場合について考える。まず、２つの各元のベクトル成分を以下の様にベクトル表現する。
すなわち、αｉのベクトル成分を（ｘ８，ｘ７，ｘ６，ｘ５，ｘ４，ｘ３，ｘ２，ｘ１，ｘ０）と表わし、αｉを以下の様にベクトル表現する。
αｉ＝Ｘ［８：０］＝（ｘ８，ｘ７，ｘ６，ｘ５，ｘ４，ｘ３，ｘ２，ｘ１，ｘ０）
また、αｊのベクトル成分を（ｙ８，ｙ７，ｙ６，ｙ５，ｙ４，ｙ３，ｙ２，ｙ１，ｙ０）と表わし、αｊを以下の様にベクトル表現する。
αｉ＝Ｙ［８：０］＝（ｙ８，ｙ７，ｙ６，ｙ５，ｙ４，ｙ３，ｙ２，ｙ１，ｙ０）
これにより、２つの元αｉ、αｊを、多項式表現する場合、以下の様に表すことができる。
αｉ＝ｘ８×Ｘ８＋ｘ７×Ｘ７＋ｘ６×Ｘ６＋ｘ５×Ｘ５＋ｘ４×Ｘ４＋ｘ３×Ｘ３＋ｘ２×Ｘ２＋ｘ１×Ｘ１＋ｘ０
αｊ＝ｙ８×Ｘ８＋ｙ７×Ｘ７＋ｙ６×Ｘ６＋ｙ５×Ｘ５＋ｙ４×Ｘ４＋ｙ３×Ｘ３＋ｙ２×Ｘ２＋ｙ１×Ｘ１＋ｙ０
なお、上記Ｘ、ｘ０〜ｘ８、ｙ０〜ｙ８は、それぞれ０または１である。
【００１４】
αｉとαｊとの乗算結果、すなわちαｉ＋ｊは下記の様になる。なお、各元の成分の乗算において、乗算記号「×」は省略して示すものとする。
αｉ＋ｊ＝（ｘ８ｙ８）×Ｘ１６
＋（ｘ８ｙ７＋ｘ７ｙ８）×Ｘ１５
＋（ｘ８ｙ６＋ｘ７ｙ７＋ｘ７ｙ８）×Ｘ１４
＋（ｘ８ｙ５＋ｘ７ｙ６＋ｘ６ｙ７＋ｘ５ｙ８）×Ｘ１３
＋（ｘ８ｙ４＋ｘ７ｙ５＋ｘ６ｙ６＋ｘ５ｙ７＋ｘ４ｙ８）×Ｘ１２
＋（ｘ８ｙ３＋ｘ７ｙ４＋ｘ６ｙ５＋ｘ５ｙ６＋ｘ４ｙ７＋ｘ３ｙ８）×Ｘ１１
＋（ｘ８ｙ２＋ｘ７ｙ３＋ｘ６ｙ４＋ｘ５ｙ５＋ｘ４ｙ６＋ｘ３ｙ７＋ｘ２ｙ８）×Ｘ１０
＋（ｘ８ｙ１＋ｘ７ｙ２＋ｘ６ｙ３＋ｘ５ｙ４＋ｘ４ｙ５＋ｘ３ｙ６＋ｘ２ｙ７＋ｘ１ｙ８）×Ｘ９
＋（ｘ８ｙ０＋ｘ７ｙ１＋ｘ６ｙ２＋ｘ５ｙ３＋ｘ４ｙ４＋ｘ３ｙ５＋ｘ２ｙ６＋ｘ１ｙ７＋ｘ０ｙ８）×Ｘ８
＋（ｘ７ｙ０＋ｘ６ｙ１＋ｘ５ｙ２＋ｘ４ｙ３＋ｘ３ｙ４＋ｘ２ｙ５＋ｘ１ｙ６＋ｘ０ｙ７）×Ｘ７
＋（ｘ６ｙ０＋ｘ５ｙ１＋ｘ４ｙ２＋ｘ３ｙ３＋ｘ２ｙ４＋ｘ１ｙ５＋ｘ０ｙ６）×Ｘ６
＋（ｘ５ｙ０＋ｘ４ｙ１＋ｘ３ｙ２＋ｘ２ｙ３＋ｘ１ｙ４＋ｘ０ｙ５）×Ｘ５
＋（ｘ４ｙ０＋ｘ３ｙ１＋ｘ２ｙ２＋ｘ１ｙ３＋ｘ０ｙ４）×Ｘ４
＋（ｘ３ｙ０＋ｘ２ｙ１＋ｘ１ｙ２＋ｘ０ｙ３）×Ｘ３
＋（ｘ２ｙ０＋ｘ１ｙ１＋ｘ０ｙ２）×Ｘ２
＋（ｘ１ｙ０＋ｘ０ｙ１）×Ｘ１
＋（ｘ０ｙ０）
【００１５】
図１は、αｉ＋ｊのベクトル成分を示した図である。図１においては、αｉのベクトル成分とαｊのベクトル成分との積を示しており、各積を図１の縦方向に足し合わせた論理和が、上記多項式表現における各次数の係数となっている。
ここで、αｉ＋ｊの多項式表現における各次数の係数を、図１に示すように、Ｘ１６〜Ｘ０各々に対応してａ１６〜ａ０とする。すなわち、以下の各式が成り立つ。
ａ１６＝ｘ８ｙ８、
ａ１５＝ｘ８ｙ７＋ｘ７ｙ８、
ａ１４＝ｘ８ｙ６＋ｘ７ｙ７＋ｘ７ｙ８、
ａ１３＝ｘ８ｙ５＋ｘ７ｙ６＋ｘ６ｙ７＋ｘ５ｙ８、
ａ１２＝ｘ８ｙ４＋ｘ７ｙ５＋ｘ６ｙ６＋ｘ５ｙ７＋ｘ４ｙ８、
ａ１１＝ｘ８ｙ３＋ｘ７ｙ４＋ｘ６ｙ５＋ｘ５ｙ６＋ｘ４ｙ７＋ｘ３ｙ８、
ａ１０＝ｘ８ｙ２＋ｘ７ｙ３＋ｘ６ｙ４＋ｘ５ｙ５＋ｘ４ｙ６＋ｘ３ｙ７＋ｘ２ｙ８、
ａ９＝ｘ８ｙ１＋ｘ７ｙ２＋ｘ６ｙ３＋ｘ５ｙ４＋ｘ４ｙ５＋ｘ３ｙ６＋ｘ２ｙ７＋ｘ１ｙ８、
ａ８＝ｘ８ｙ０＋ｘ７ｙ１＋ｘ６ｙ２＋ｘ５ｙ３＋ｘ４ｙ４＋ｘ３ｙ５＋ｘ２ｙ６＋ｘ１ｙ７＋ｘ０ｙ８、
ａ７＝ｘ７ｙ０＋ｘ６ｙ１＋ｘ５ｙ２＋ｘ４ｙ３＋ｘ３ｙ４＋ｘ２ｙ５＋ｘ１ｙ６＋ｘ０ｙ７、
ａ６＝ｘ６ｙ０＋ｘ５ｙ１＋ｘ４ｙ２＋ｘ３ｙ３＋ｘ２ｙ４＋ｘ１ｙ５＋ｘ０ｙ６、
ａ５＝ｘ５ｙ０＋ｘ４ｙ１＋ｘ３ｙ２＋ｘ２ｙ３＋ｘ１ｙ４＋ｘ０ｙ５、
ａ４＝ｘ４ｙ０＋ｘ３ｙ１＋ｘ２ｙ２＋ｘ１ｙ３＋ｘ０ｙ４、
ａ３＝ｘ３ｙ０＋ｘ２ｙ１＋ｘ１ｙ２＋ｘ０ｙ３、
ａ２＝ｘ２ｙ０＋ｘ１ｙ１＋ｘ０ｙ２、
ａ１＝ｘ１ｙ０＋ｘ０ｙ１、
ａ０＝ｘ０ｙ０である。
【００１６】
つまり、αｉ＋ｊを、ａ１６〜ａ０を用いて多項式表現すると、以下の式が得られる。
αｉ＋ｊ＝ａ１６×Ｘ１６＋ａ１５×Ｘ１５＋ａ１４×Ｘ１４＋ａ１３×Ｘ１３＋ａ１２×Ｘ１２＋ａ１１×Ｘ１１＋ａ１０×Ｘ１０＋ａ９×Ｘ９＋ａ８×Ｘ８＋ａ７×Ｘ７＋ａ６×Ｘ６＋ａ５×Ｘ５＋ａ４×Ｘ４＋ａ３×Ｘ３＋ａ２×Ｘ２＋ａ１×Ｘ１＋ａ０・・・（１）
【００１７】
ここで、ガロア体ＧＦ（２９）の既約多項式（原始多項式）として、Ｘ９＋Ｘ４＋１を採用した場合、Ｘ９以上の高次の次数は、下記のようにＸ８以下の低次の次数によって表わすことができる。
Ｘ９＝Ｘ４＋１、
Ｘ１０＝Ｘ×Ｘ８＝Ｘ５＋Ｘ、
Ｘ１１＝Ｘ×Ｘ１０＝Ｘ６＋Ｘ２、
Ｘ１２＝Ｘ×Ｘ１１＝Ｘ７＋Ｘ３、
Ｘ１３＝Ｘ×Ｘ１２＝Ｘ８＋Ｘ４、
Ｘ１４＝Ｘ×Ｘ１３＝Ｘ９＋Ｘ５＝Ｘ５＋Ｘ４＋１、
Ｘ１５＝Ｘ×Ｘ１４＝Ｘ６＋Ｘ５＋Ｘ、
Ｘ１６＝Ｘ×Ｘ１５＝Ｘ７＋Ｘ６＋Ｘ２である。
【００１８】
これらの、高次の次数を、上記式（１）に代入し、次数毎にまとめると、すなわち同じＸのべき乗の項を纏めると、αｉ＋ｊは、以下のように多項式表現される。
αｉ＋ｊ＝（ａ８＋ａ１３）×Ｘ８
＋（ａ７＋ａ１２＋ａ１６）×Ｘ７
＋（ａ６＋ａ１１＋ａ１５＋ａ１６）×Ｘ６
＋（ａ５＋ａ１０＋ａ１４＋ａ１５）×Ｘ５
＋（ａ４＋ａ９＋ａ１３＋ａ１４）×Ｘ４
＋（ａ３＋ａ１２）×Ｘ３
＋（ａ２＋ａ１１＋ａ１６）×Ｘ２
＋（ａ１＋ａ１０＋ａ１５）×Ｘ１
＋（ａ０＋ａ９＋ａ１４）・・・（２）
【００１９】
ここで、本実施形態において、乗算結果αｉ＋ｊをベクトル表現する場合、αｉ＋ｊのベクトル成分を（ｚ８，ｚ７，ｚ６，ｚ５，ｚ４，ｚ３，ｚ２，ｚ１，ｚ０）と表わし、αｉ＋ｊを以下の様に表現する。
αｉ＋ｊ＝Ｚ［８：０］＝（ｚ８，ｚ７，ｚ６，ｚ５，ｚ４，ｚ３，ｚ２，ｚ１，ｚ０）これにより、αｉ＋ｊを、多項式表現する場合、以下の様になる。
Ｚ［８：０］＝ｚ８×Ｘ８＋ｚ７×Ｘ７＋ｚ６×Ｘ６＋ｚ５×Ｘ５＋ｚ４×Ｘ４＋ｚ３×Ｘ３＋ｚ２×Ｘ２＋ｚ１×Ｘ１＋ｚ０
【００２０】
これにより、上記式（２）から、Ｚ［８：０］の各ビットＺ［８］〜Ｚ［０］は、それぞれ下記の様に表される。
ｚ８＝ａ８＋ａ１３、
ｚ７＝ａ７＋ａ１２＋ａ１６、
ｚ６＝ａ６＋ａ１１＋ａ１５＋ａ１６、
ｚ５＝ａ５＋ａ１０＋ａ１４＋ａ１５、
ｚ４＝ａ４＋ａ９＋ａ１３＋ａ１４、
ｚ３＝ａ３＋ａ１２、
ｚ２＝ａ２＋ａ１１＋ａ１６、
ｚ１＝ａ１＋ａ１０＋ａ１５、
ｚ０＝ａ０＋ａ９＋ａ１４
【００２１】
つまり、２つの元の乗算を行う際、乗算結果のうちの下位８（＝ｍ）ビット以外の上位ビットの要素についてそれぞれ排他的論理和演算して求め、その演算結果を予め与えられる原始多項式により、下位ｍビットのベクトル表現に変換する。また、変換後のｍビットの各要素を、乗算結果のうちの下位ｍビットの要素についてそれぞれ排他的論理和演算して求めた演算結果の各要素と排他的論理和演算する。
このようにして、乗算結果Ｚ［８：０］の各ビットＺ［０］〜Ｚ［８］は、Ｘ［８：０］の各ビットとＹ［８：０］の各ビットとの乗算結果の和（ａ０〜ａ１４のいずれか）を組み合わせ、これらの組み合せの和を求めた結果で表される。
Ｘ［８：０］の各ビットとＹ［８：０］の各ビットとの乗算結果の和（ａ０〜ａ１４のいずれか）を求めるためには、ＥＸＯＲ回路が用いられる。また、ａ０〜ａ１４のいずれかを組み合わせて乗算結果Ｚ［８：０］の各ビットを求めるために、ＥＸＯＲ回路が用いられる。
図２は、乗算結果Ｚ［８：０］の各ビットを、ＥＸＯＲ回路を用いてａ０〜ａ１４から演算する場合の論理式を示す。なお、図２において、符号「＾」は排他的論理和演算を示し、Ｚ［８：０］の各ビットをＺ［０］〜Ｚ［８］で、αｉ＋ｊの各次数の係数に用いるａ０〜ａ１６をａ［０］〜ａ［１６］で示している。
【００２２】
乗算結果Ｚ［８：０］の各ビットは、Ｘ［８：０］の各ビットとＹ［８：０］の各ビットとの乗算結果を求めるためのアンド回路、乗算結果の和（ａ０〜ａ１４のいずれか）を求めるＥＸＯＲ回路、さらに、図２に示す排他的論理和演算を行うＥＸＯＲ回路により演算される。
このＺ［８：０］を演算する回路の構成は、Ｚ［８：０］の各ビットに対応して、以下に図３〜図８に示す要素演算部の構成となる。図３は、Ｚ［０］、及びＺ［１］を演算する要素演算部の構成を示す。図４は、Ｚ［２］、及びＺ［３］を演算する要素演算部の構成を示す。図５は、Ｚ［４］を演算する要素演算部の構成を示す。図６は、Ｚ［５］を演算する要素演算部の構成を示す。図７は、Ｚ［６］を演算する要素演算部の構成を示す。図８は、Ｚ［７］、及びＺ［８］を演算する要素演算部の構成を示す。
【００２３】
Ｚ［０］について演算する要素演算部３０は、図３に示すように、ａ０演算部３００、ａ９演算部３０９、ａ１４演算部３１４、及びＺ［０］演算部４００から構成される。
【００２４】
ａ０演算部３００は、アンド回路３００＿１から構成され、Ｘ［０］＝ｘ０（一方の元のビット）と、Ｙ［０］＝ｙ０（他方の元のビット）との論理積演算を行い、ａ０（＝ｘ０ｙ０）を出力する。
【００２５】
ａ９演算部３０９は、アンド回路３０９＿１、アンド回路３０９＿２、アンド回路３０９＿３、アンド回路３０９＿４、アンド回路３０９＿５、アンド回路３０９＿６、アンド回路３０９＿７、アンド回路３０９＿８、ＥＸＯＲ回路３０９＿１１、ＥＸＯＲ回路３０９＿１２、ＥＸＯＲ回路３０９＿１３、ＥＸＯＲ回路３０９＿１４、ＥＸＯＲ回路３０９＿１５、ＥＸＯＲ回路３０９＿１６、ＥＸＯＲ回路３０９＿１７から構成される。
アンド回路３０９＿１は、Ｘ［８］＝ｘ８とＹ［１］＝ｙ１との論理積演算を行い、ｘ８ｙ１を出力する。
アンド回路３０９＿２は、Ｘ［７］＝ｘ７とＹ［２］＝ｙ２との論理積演算を行い、ｘ７ｙ２を出力する。
アンド回路３０９＿３は、Ｘ［６］＝ｘ６とＹ［３］＝ｙ３との論理積演算を行い、ｘ６ｙ３を出力する。
アンド回路３０９＿４は、Ｘ［５］＝ｘ５とＹ［４］＝ｙ４との論理積演算を行い、ｘ５ｙ４を出力する。
アンド回路３０９＿５は、Ｘ［４］＝ｘ４とＹ［５］＝ｙ５との論理積演算を行い、ｘ４ｙ５を出力する。
アンド回路３０９＿６は、Ｘ［３］＝ｘ３とＹ［６］＝ｙ６との論理積演算を行い、ｘ３ｙ６を出力する。
アンド回路３０９＿７は、Ｘ［２］＝ｘ２とＹ［７］＝ｙ７との論理積演算を行い、ｘ２ｙ７を出力する。
アンド回路３０９＿８は、Ｘ［１］＝ｘ１とＹ［８］＝ｙ８との論理積演算を行い、ｘ１ｙ８を出力する。
【００２６】
ＥＸＯＲ回路３０９＿１１は、アンド回路３０９＿１の出力信号であるｘ８ｙ１と、アンド回路３０９＿２の出力信号であるｘ７ｙ２との排他的論理和演算を行い、（ｘ８ｙ１＋ｘ７ｙ２）を出力する。
ＥＸＯＲ回路３０９＿１２は、アンド回路３０９＿３の出力信号であるｘ６ｙ３と、アンド回路３０９＿４の出力信号であるｘ５ｙ４との排他的論理和演算を行い、（ｘ６ｙ３＋ｘ５ｙ４）を出力する。
ＥＸＯＲ回路３０９＿１３は、アンド回路３０９＿５の出力信号であるｘ４ｙ５と、アンド回路３０９＿６の出力信号であるｘ３ｙ６との排他的論理和演算を行い、（ｘ４ｙ５＋ｘ３ｙ６）を出力する。
ＥＸＯＲ回路３０９＿１４は、アンド回路３０９＿７の出力信号であるｘ２ｙ７と、アンド回路３０９＿８の出力信号であるｘ１ｙ８との排他的論理和演算を行い、（ｘ２ｙ７＋ｘ１ｙ８）を出力する。
ＥＸＯＲ回路３０９＿１５は、ＥＸＯＲ回路３０９＿１１の出力信号である（ｘ８ｙ１＋ｘ７ｙ２）と、ＥＸＯＲ回路３０９＿１２の出力信号である（ｘ６ｙ３＋ｘ５ｙ４）との排他的論理和演算を行い、（ｘ８ｙ１＋ｘ７ｙ２＋ｘ６ｙ３＋ｘ５ｙ４）を出力する。
ＥＸＯＲ回路３０９＿１６は、ＥＸＯＲ回路３０９＿１３の出力信号である（ｘ４ｙ５＋ｘ３ｙ６）と、ＥＸＯＲ回路３０９＿１４の出力信号である（ｘ２ｙ７＋ｘ１ｙ８）との排他的論理和演算を行い、（ｘ４ｙ５＋ｘ３ｙ６＋ｘ２ｙ７＋ｘ１ｙ８）を出力する。
ＥＸＯＲ回路３０９＿１７は、ＥＸＯＲ回路３０９＿１５の出力信号である（ｘ８ｙ１＋ｘ７ｙ２＋ｘ６ｙ３＋ｘ５ｙ４）と、ＥＸＯＲ回路３０９＿１６の出力信号である（ｘ４ｙ５＋ｘ３ｙ６＋ｘ２ｙ７＋ｘ１ｙ８）との排他的論理和演算を行い、ａ９（＝ｘ８ｙ１＋ｘ７ｙ２＋ｘ６ｙ３＋ｘ５ｙ４＋ｘ４ｙ５＋ｘ３ｙ６＋ｘ２ｙ７＋ｘ１ｙ８）を出力する。
【００２７】
ａ１４演算部３１４は、アンド回路３１４＿１、アンド回路３１４＿２、アンド回路３１４＿３、ＥＸＯＲ回路３１４＿１１、ＥＸＯＲ回路３１４＿１２から構成される。
アンド回路３１４＿１は、Ｘ［８］＝ｘ８とＹ［６］＝ｙ６との論理積演算を行い、ｘ８ｙ６を出力する。
アンド回路３１４＿２は、Ｘ［７］＝ｘ７とＹ［７］＝ｙ７との論理積演算を行い、ｘ７ｙ７を出力する。
アンド回路３１４＿３は、Ｘ［６］＝ｘ６とＹ［８］＝ｙ８との論理積演算を行い、ｘ６ｙ８を出力する。
ＥＸＯＲ回路３１４＿１１は、アンド回路３１４＿１の出力信号であるｘ８ｙ６と、アンド回路３１４＿２の出力信号であるｘ７ｙ７との排他的論理和演算を行い、（ｘ８ｙ６＋ｘ７ｙ７）を出力する。
ＥＸＯＲ回路３１４＿１２は、ＥＸＯＲ回路３１４＿１１の出力信号である（ｘ８ｙ６＋ｘ７ｙ７）と、アンド回路３１４＿３の出力信号であるｘ６ｙ８との排他的論理和演算を行い、ａ１４（＝ｘ８ｙ６＋ｘ７ｙ７＋ｘ６ｙ８）を出力する。
【００２８】
Ｚ［０］演算部４００は、ＥＸＯＲ回路４００＿１、及びＥＸＯＲ回路４００＿２から構成される。
ＥＸＯＲ回路４００＿１は、ａ０演算部３００の出力信号であるａ０（＝ｘ０ｙ０）と、ａ９演算部３０９の出力信号であるａ９（＝ｘ８ｙ１＋ｘ７ｙ２＋ｘ６ｙ３＋ｘ５ｙ４＋ｘ４ｙ５＋ｘ３ｙ６＋ｘ２ｙ７＋ｘ１ｙ８）との排他的論理和演算を行い、（ａ０＋ａ９）を出力する。
ＥＸＯＲ回路４００＿２は、ＥＸＯＲ回路４００＿１の出力信号である（ａ０＋ａ９）と、ａ１演算部３１４の出力信号であるａ１４（＝ｘ８ｙ６＋ｘ７ｙ７＋ｘ６ｙ８）との排他的論理和演算を行い、Ｚ［０］（＝ａ０＋ａ９＋ａ１４）を出力する。
このように、要素演算部３０は、Ｚ［８：０］のうちの１ビットであるＺ［０］を演算して出力するが、その論理ゲートの個数は、アンド回路が１２個、ＥＸＯＲ回路が１１個であり、合計２３個である。また、要素演算部３０の内部ノードの個数は、ＥＸＯＲ回路の入力ノードの個数の２倍と等しく、２２個である。
【００２９】
次に、Ｚ［１］について演算する要素演算部３１は、図３に示すように、ａ１演算部３０１、ａ１０演算部３１０、ａ１５演算部３１５、及びＺ［１］演算部４０１から構成される。
【００３０】
ａ１演算部３０１は、アンド回路３０１＿１、アンド回路３０１＿２、ＥＸＯＲ回路３０１＿１１から構成される。
アンド回路３０１＿１は、Ｘ［１］＝ｘ１とＹ［０］＝ｙ０との論理積演算を行い、ｘ１ｙ０を出力する。
アンド回路３０１＿２は、Ｘ［０］＝ｘ０とＹ［１］＝ｙ１との論理積演算を行い、ｘ０ｙ１を出力する。
ＥＸＯＲ回路３０１＿１１は、アンド回路３０１＿１の出力信号であるｘ１ｙ０と、アンド回路３０１＿２の出力信号であるｘ０ｙ1との排他的論理和演算を行い、ａ１（＝ｘ１ｙ０＋ｘ０ｙ１）を出力する。
【００３１】
ａ１０演算部３１０は、アンド回路３１０＿１、アンド回路３１０＿２、アンド回路３１０＿３、アンド回路３１０＿４、アンド回路３１０＿５、アンド回路３１０＿６、アンド回路３１０＿７、ＥＸＯＲ回路３１０＿１１、ＥＸＯＲ回路３１０＿１２、ＥＸＯＲ回路３１０＿１３、ＥＸＯＲ回路３１０＿１４、ＥＸＯＲ回路３１０＿１５、ＥＸＯＲ回路３１０＿１６から構成される。
アンド回路３１０＿１は、Ｘ［８］＝ｘ８とＹ［２］＝ｙ２との論理積演算を行い、ｘ８ｙ２を出力する。
アンド回路３１０＿２は、Ｘ［７］＝ｘ７とＹ［３］＝ｙ３との論理積演算を行い、ｘ７ｙ３を出力する。
アンド回路３１０＿３は、Ｘ［６］＝ｘ６とＹ［４］＝ｙ４との論理積演算を行い、ｘ６ｙ４を出力する。
アンド回路３１０＿４は、Ｘ［５］＝ｘ５とＹ［５］＝ｙ５との論理積演算を行い、ｘ５ｙ５を出力する。
アンド回路３１０＿５は、Ｘ［４］＝ｘ４とＹ［６］＝ｙ６との論理積演算を行い、ｘ４ｙ６を出力する。
アンド回路３１０＿６は、Ｘ［３］＝ｘ３とＹ［７］＝ｙ７との論理積演算を行い、ｘ３ｙ７を出力する。
アンド回路３１０＿７は、Ｘ［２］＝ｘ２とＹ［８］＝ｙ８との論理積演算を行い、ｘ２ｙ８を出力する。
【００３２】
ＥＸＯＲ回路３１０＿１１は、アンド回路３１０＿１の出力信号であるｘ８ｙ２と、アンド回路３１０＿２の出力信号であるｘ７ｙ３との排他的論理和演算を行い、（ｘ８ｙ２＋ｘ７ｙ３）を出力する。
ＥＸＯＲ回路３１０＿１２は、アンド回路３１０＿３の出力信号であるｘ６ｙ４と、アンド回路３１０＿４の出力信号であるｘ５ｙ５との排他的論理和演算を行い、（ｘ６ｙ４＋ｘ５ｙ５）を出力する。
ＥＸＯＲ回路３１０＿１３は、アンド回路３１０＿５の出力信号であるｘ４ｙ６と、アンド回路３１０＿６の出力信号であるｘ３ｙ７との排他的論理和演算を行い、（ｘ４ｙ６＋ｘ３ｙ７）を出力する。
ＥＸＯＲ回路３１０＿１４は、ＥＸＯＲ回路３１０＿１１の出力信号である（ｘ８ｙ２＋ｘ７ｙ３）と、ＥＸＯＲ回路３１０＿１２の出力信号である（ｘ６ｙ４＋ｘ５ｙ５）との排他的論理和演算を行い、（ｘ８ｙ２＋ｘ７ｙ３＋ｘ６ｙ４＋ｘ５ｙ５）を出力する。
ＥＸＯＲ回路３１０＿１５は、ＥＸＯＲ回路３１０＿１３の出力信号である（ｘ４ｙ６＋ｘ３ｙ７）と、アンド回路３１０＿７の出力信号であるｘ２ｙ８との排他的論理和演算を行い、（ｘ４ｙ６＋ｘ３ｙ７＋ｘ２ｙ８）を出力する。
ＥＸＯＲ回路３１０＿１６は、ＥＸＯＲ回路３１０＿１４の出力信号である（ｘ８ｙ２＋ｘ７ｙ３＋ｘ６ｙ４＋ｘ５ｙ５）と、ＥＸＯＲ回路３０９＿１５の出力信号である（ｘ４ｙ６＋ｘ３ｙ７＋ｘ２ｙ８）との排他的論理和演算を行い、ａ１０（＝ｘ８ｙ２＋ｘ７ｙ３＋ｘ６ｙ４＋ｘ５ｙ５＋ｘ４ｙ６＋ｘ３ｙ７＋ｘ２ｙ８）を出力する。
【００３３】
ａ１５演算部３１５は、アンド回路３１５＿１、アンド回路３１５＿２、ＥＸＯＲ回路３１５＿１１から構成される。
アンド回路３１５＿１は、Ｘ［８］＝ｘ８とＹ［７］＝ｙ７との論理積演算を行い、ｘ８ｙ７を出力する。
アンド回路３１５＿２は、Ｘ［７］＝ｘ７とＹ［８］＝ｙ８との論理積演算を行い、ｘ７ｙ７を出力する。
ＥＸＯＲ回路３１５＿１１は、アンド回路３１５＿１の出力信号であるｘ８ｙ７と、アンド回路３１５＿２の出力信号であるｘ７ｙ８との排他的論理和演算を行い、ａ１５（＝ｘ８ｙ７＋ｘ７ｙ８）を出力する。
【００３４】
Ｚ［１］演算部４０１は、ＥＸＯＲ回路４０１＿１、及びＥＸＯＲ回路４０１＿２から構成される。
ＥＸＯＲ回路４０１＿１は、ａ１演算部３０１の出力信号であるａ１（＝ｘ１ｙ０＋ｘ０ｙ１）と、ａ１０演算部３１０の出力信号であるａ１０（＝ｘ８ｙ２＋ｘ７ｙ３＋ｘ６ｙ４＋ｘ５ｙ５＋ｘ４ｙ６＋ｘ３ｙ７＋ｘ２ｙ８）との排他的論理和演算を行い、（ａ１＋ａ１０）を出力する。
ＥＸＯＲ回路４０１＿２は、ＥＸＯＲ回路４０１＿１の出力信号である（ａ１＋ａ１０）と、ａ１５演算部３１５の出力信号であるａ１５（＝ｘ８ｙ７＋ｘ７ｙ８）との排他的論理和演算を行い、Ｚ［１］（＝ａ１＋ａ１０＋ａ１５）を出力する。
このように、要素演算部３１は、Ｚ［８：０］のうちの１ビットであるＺ［１］を演算して出力するが、その論理ゲートの個数は、アンド回路が１１個、ＥＸＯＲ回路が１０個であり、合計２１個である。また、要素演算部３１の内部ノードの個数は、ＥＸＯＲ回路の入力ノードの個数の２倍と等しく、２０個である。
【００３５】
次に、Ｚ［２］について演算する要素演算部３２は、図４に示すように、ａ２演算部３０２、ａ１１演算部３１１、ａ１６演算部３１６、及びＺ［２］演算部４０２から構成される。
【００３６】
ａ２演算部３０２は、アンド回路３０２＿１、アンド回路３０２＿２、アンド回路３０２＿３、ＥＸＯＲ回路３０２＿１１、ＥＸＯＲ回路３０２＿１２から構成される。
アンド回路３０２＿１は、Ｘ［２］＝ｘ２とＹ［０］＝ｙ０との論理積演算を行い、ｘ２ｙ０を出力する。
アンド回路３０２＿２は、Ｘ［１］＝ｘ１とＹ［１］＝ｙ１との論理積演算を行い、ｘ１ｙ１を出力する。
アンド回路３０２＿３は、Ｘ［０］＝ｘ０とＹ［２］＝ｙ２との論理積演算を行い、ｘ０ｙ２を出力する。
ＥＸＯＲ回路３０２＿１１は、アンド回路３０２＿１の出力信号であるｘ２ｙ０と、アンド回路３０２＿２の出力信号であるｘ１ｙ１との排他的論理和演算を行い、（ｘ２ｙ０＋ｘ１ｙ１）を出力する。
ＥＸＯＲ回路３０２＿１２は、ＥＸＯＲ回路３０２＿１１の出力信号である（ｘ２ｙ０＋ｘ１ｙ１）と、アンド回路３０２＿３の出力信号であるｘ０ｙ２との排他的論理和演算を行い、ａ２（＝ｘ２ｙ０＋ｘ１ｙ１＋ｘ０ｙ２）を出力する。
【００３７】
ａ１１演算部３１１は、アンド回路３１１＿１、アンド回路３１１＿２、アンド回路３１１＿３、アンド回路３１１＿４、アンド回路３１１＿５、アンド回路３１１＿６、ＥＸＯＲ回路３１１＿１１、ＥＸＯＲ回路３１１＿１２、ＥＸＯＲ回路３１１＿１３、ＥＸＯＲ回路３１１＿１４、ＥＸＯＲ回路３１１＿１５から構成される。
アンド回路３１１＿１は、Ｘ［８］＝ｘ８とＹ［３］＝ｙ３との論理積演算を行い、ｘ８ｙ３を出力する。
アンド回路３１１＿２は、Ｘ［７］＝ｘ７とＹ［４］＝ｙ４との論理積演算を行い、ｘ７ｙ４を出力する。
アンド回路３１１＿３は、Ｘ［６］＝ｘ６とＹ［５］＝ｙ５との論理積演算を行い、ｘ６ｙ５を出力する。
アンド回路３１１＿４は、Ｘ［５］＝ｘ５とＹ［６］＝ｙ６との論理積演算を行い、ｘ５ｙ６を出力する。
アンド回路３１１＿５は、Ｘ［４］＝ｘ４とＹ［７］＝ｙ７との論理積演算を行い、ｘ４ｙ７を出力する。
アンド回路３１１＿６は、Ｘ［３］＝ｘ３とＹ［８］＝ｙ８との論理積演算を行い、ｘ３ｙ８を出力する。
【００３８】
ＥＸＯＲ回路３１１＿１１は、アンド回路３１１＿１の出力信号であるｘ８ｙ３と、アンド回路３１１＿２の出力信号であるｘ７ｙ４との排他的論理和演算を行い、（ｘ８ｙ３＋ｘ７ｙ４）を出力する。
ＥＸＯＲ回路３１１＿１２は、アンド回路３１１＿３の出力信号であるｘ６ｙ５と、アンド回路３１１＿４の出力信号であるｘ５ｙ６との排他的論理和演算を行い、（ｘ６ｙ５＋ｘ５ｙ６）を出力する。
ＥＸＯＲ回路３１１＿１３は、アンド回路３１１＿５の出力信号であるｘ４ｙ７と、アンド回路３１１＿６の出力信号であるｘ３ｙ８との排他的論理和演算を行い、（ｘ４ｙ７＋ｘ３ｙ８）を出力する。
ＥＸＯＲ回路３１１＿１４は、ＥＸＯＲ回路３１１＿１１の出力信号である（ｘ８ｙ３＋ｘ７ｙ４）と、ＥＸＯＲ回路３１１＿１２の出力信号である（ｘ６ｙ５＋ｘ５ｙ６）との排他的論理和演算を行い、（ｘ８ｙ３＋ｘ７ｙ４＋ｘ６ｙ５＋ｘ５ｙ６）を出力する。
ＥＸＯＲ回路３１１＿１５は、ＥＸＯＲ回路３１１＿１４の出力信号である（ｘ８ｙ３＋ｘ７ｙ４＋ｘ６ｙ５＋ｘ５ｙ６）と、ＥＸＯＲ回路３０９＿１３の出力信号である（ｘ４ｙ７＋ｘ３ｙ８）との排他的論理和演算を行い、ａ１１（＝ｘ８ｙ３＋ｘ７ｙ４＋ｘ６ｙ５＋ｘ５ｙ６＋ｘ４ｙ７＋ｘ３ｙ８）を出力する。
【００３９】
ａ１６演算部３１６は、アンド回路３１６＿１から構成され、Ｘ［８］＝ｘ８（一方の元のビット）と、Ｙ［８］＝ｙ８（他方の元のビット）との論理積演算を行い、ａ１６（＝ｘ８ｙ８）を出力する。
【００４０】
Ｚ［２］演算部４０２は、ＥＸＯＲ回路４０２＿１、及びＥＸＯＲ回路４０２＿２から構成される。
ＥＸＯＲ回路４０２＿１は、ａ２演算部３０２の出力信号であるａ２（＝ｘ２ｙ０＋ｘ１ｙ１＋ｘ０ｙ２）と、ａ１１演算部３１１の出力信号であるａ１１（＝ｘ８ｙ３＋ｘ７ｙ４＋ｘ６ｙ５＋ｘ５ｙ６＋ｘ４ｙ７＋ｘ３ｙ８）との排他的論理和演算を行い、（ａ２＋ａ１１）を出力する。
ＥＸＯＲ回路４０２＿２は、ＥＸＯＲ回路４０２＿１の出力信号である（ａ２＋ａ１１）と、ａ１６演算部３１６の出力信号であるａ１６（＝ｘ８ｙ８）との排他的論理和演算を行い、Ｚ［２］（＝ａ２＋ａ１１＋ａ１６）を出力する。
このように、要素演算部３２は、Ｚ［８：０］のうちの１ビットであるＺ［２］を演算して出力するが、その論理ゲートの個数は、アンド回路が１０個、ＥＸＯＲ回路が９個であり、合計１９個である。また、要素演算部３２の内部ノードの個数は、ＥＸＯＲ回路の入力ノードの個数の２倍と等しく、１８個である。
【００４１】
次に、Ｚ［３］について演算する要素演算部３３は、図４に示すように、ａ３演算部３０３、ａ１２演算部３１２、及びＺ［３］演算部４０３から構成される。
【００４２】
ａ３演算部３０３は、アンド回路３０３＿１、アンド回路３０３＿２、アンド回路３０３＿３、アンド回路３０３＿４、ＥＸＯＲ回路３０３＿１１、ＥＸＯＲ回路３０３＿１２、ＥＸＯＲ回路３０３＿１３から構成される。
アンド回路３０３＿１は、Ｘ［３］＝ｘ３とＹ［０］＝ｙ０との論理積演算を行い、ｘ３ｙ０を出力する。
アンド回路３０３＿２は、Ｘ［２］＝ｘ２とＹ［１］＝ｙ１との論理積演算を行い、ｘ２ｙ１を出力する。
アンド回路３０３＿３は、Ｘ［１］＝ｘ１とＹ［２］＝ｙ２との論理積演算を行い、ｘ１ｙ２を出力する。
アンド回路３０３＿４は、Ｘ［０］＝ｘ０とＹ［３］＝ｙ３との論理積演算を行い、ｘ０ｙ３を出力する。
ＥＸＯＲ回路３０３＿１１は、アンド回路３０３＿１の出力信号であるｘ３ｙ０と、アンド回路３０３＿２の出力信号であるｘ２ｙ１との排他的論理和演算を行い、（ｘ３ｙ０＋ｘ２ｙ１）を出力する。
ＥＸＯＲ回路３０３＿１２は、アンド回路３０３＿３の出力信号であるｘ１ｙ２と、アンド回路３０３＿４の出力信号であるｘ０ｙ３との排他的論理和演算を行い、（ｘ１ｙ２＋ｘ０ｙ３）を出力する。
ＥＸＯＲ回路３０３＿１２は、ＥＸＯＲ回路３０３＿１１の出力信号である（ｘ３ｙ０＋ｘ２ｙ１）と、ＥＸＯＲ回路３０３＿１２の出力信号である（ｘ１ｙ２＋ｘ０ｙ３）との排他的論理和演算を行い、ａ３（＝ｘ３ｙ０＋ｘ２ｙ１＋ｘ１ｙ２＋ｘ０ｙ３）を出力する。
【００４３】
ａ１２演算部３１２は、アンド回路３１２＿１、アンド回路３１２＿２、アンド回路３１２＿３、アンド回路３１２＿４、アンド回路３１２＿５、ＥＸＯＲ回路３１２＿１１、ＥＸＯＲ回路３１２＿１２、ＥＸＯＲ回路３１２＿１３、ＥＸＯＲ回路３１２＿１４から構成される。
アンド回路３１２＿１は、Ｘ［８］＝ｘ８とＹ［４］＝ｙ４との論理積演算を行い、ｘ８ｙ４を出力する。
アンド回路３１２＿２は、Ｘ［７］＝ｘ７とＹ［５］＝ｙ５との論理積演算を行い、ｘ７ｙ５を出力する。
アンド回路３１２＿３は、Ｘ［６］＝ｘ６とＹ［６］＝ｙ６との論理積演算を行い、ｘ６ｙ６を出力する。
アンド回路３１２＿４は、Ｘ［５］＝ｘ５とＹ［７］＝ｙ７との論理積演算を行い、ｘ５ｙ７を出力する。
アンド回路３１２＿５は、Ｘ［４］＝ｘ４とＹ［８］＝ｙ８との論理積演算を行い、ｘ４ｙ８を出力する。
【００４４】
ＥＸＯＲ回路３１２＿１１は、アンド回路３１２＿１の出力信号であるｘ８ｙ４と、アンド回路３１２＿２の出力信号であるｘ７ｙ５との排他的論理和演算を行い、（ｘ８ｙ４＋ｘ７ｙ５）を出力する。
ＥＸＯＲ回路３１２＿１２は、アンド回路３１２＿３の出力信号であるｘ６ｙ６と、アンド回路３１２＿４の出力信号であるｘ５ｙ７との排他的論理和演算を行い、（ｘ６ｙ６＋ｘ５ｙ７）を出力する。
ＥＸＯＲ回路３１２＿１３は、ＥＸＯＲ回路３１２＿１の出力信号である（ｘ８ｙ４＋ｘ７ｙ５）と、ＥＸＯＲ回路３１２＿１２の出力信号である（ｘ６ｙ６＋ｘ５ｙ７）との排他的論理和演算を行い、（ｘ８ｙ４＋ｘ７ｙ５＋ｘ６ｙ６＋ｘ５ｙ７）を出力する。
ＥＸＯＲ回路３１２＿１４は、ＥＸＯＲ回路３１２＿１３の出力信号である（ｘ８ｙ４＋ｘ７ｙ５＋ｘ６ｙ６＋ｘ５ｙ７）と、アンド回路３１２＿５の出力信号であるｘ４ｙ８との排他的論理和演算を行い、ａ１２（＝ｘ８ｙ４＋ｘ７ｙ５＋ｘ６ｙ６＋ｘ５ｙ７＋ｘ４ｙ８）を出力する。
【００４５】
Ｚ［３］演算部４０３は、ＥＸＯＲ回路４０３＿１から構成される。
ＥＸＯＲ回路４０３＿１は、ａ３演算部３０３の出力信号であるａ３（＝ｘ８ｙ４＋ｘ７ｙ５＋ｘ６ｙ６＋ｘ５ｙ７）と、ａ１２演算部３１２の出力信号であるａ１２（＝ｘ８ｙ４＋ｘ７ｙ５＋ｘ６ｙ６＋ｘ５ｙ７＋ｘ４ｙ８）との排他的論理和演算を行い、（ａ３＋ａ１２）を出力する。
このように、要素演算部３３は、Ｚ［８：０］のうちの１ビットであるＺ［３］を演算して出力するが、その論理ゲートの個数は、アンド回路が９個、ＥＸＯＲ回路が８個であり、合計１７個である。また、要素演算部３３の内部ノードの個数は、ＥＸＯＲ回路の入力ノードの個数の２倍と等しく、１６個である。
【００４６】
次に、Ｚ［４］について演算する要素演算部３４は、図５に示すように、ａ４演算部３０４、ａ９演算部３０９、ａ１３演算部３１３、ａ１４演算部３１４、及びＺ［４］演算部４０４から構成される。このうち、ａ９演算部３０９、及びａ１４演算部３１４は、それぞれ図３に記載の要素演算部３０の回路と同じ回路であり、その説明を省略する。また、ａ９演算部３０９、及びａ１４演算部３１４は、要素演算部３０と兼用することが可能である。
【００４７】
ａ０４演算部３０４は、アンド回路３０４＿１、アンド回路３０４＿２、アンド回路３０４＿３、アンド回路３０４＿４、アンド回路３０４＿５、ＥＸＯＲ回路３０４＿１１、ＥＸＯＲ回路３０４＿１２、ＥＸＯＲ回路３０４＿１３、ＥＸＯＲ回路３０４＿１４から構成される。
アンド回路３０４＿１は、Ｘ［４］＝ｘ４とＹ［０］＝ｙ０との論理積演算を行い、ｘ４ｙ０を出力する。
アンド回路３０４＿２は、Ｘ［３］＝ｘ３とＹ［１］＝ｙ１との論理積演算を行い、ｘ３ｙ１を出力する。
アンド回路３０４＿３は、Ｘ［２］＝ｘ２とＹ［２］＝ｙ２との論理積演算を行い、ｘ２ｙ２を出力する。
アンド回路３０４＿４は、Ｘ［１］＝ｘ１とＹ［３］＝ｙ３との論理積演算を行い、ｘ１ｙ３を出力する。
アンド回路３０４＿５は、Ｘ［０］＝ｘ０とＹ［４］＝ｙ４との論理積演算を行い、ｘ０ｙ４を出力する。
【００４８】
ＥＸＯＲ回路３０４＿１１は、アンド回路３０４＿１の出力信号であるｘ４ｙ０と、アンド回路３０４＿２の出力信号であるｘ３ｙ１との排他的論理和演算を行い、（ｘ４ｙ０＋ｘ３ｙ１）を出力する。
ＥＸＯＲ回路３０４＿１２は、アンド回路３０４＿３の出力信号であるｘ２ｙ２と、アンド回路３０４＿４の出力信号であるｘ１ｙ３との排他的論理和演算を行い、（ｘ２ｙ２＋ｘ１ｙ３）を出力する。
ＥＸＯＲ回路３０４＿１３は、ＥＸＯＲ回路３０４＿１１の出力信号である（ｘ４ｙ０＋ｘ３ｙ１）と、ＥＸＯＲ回路３０４＿１２の出力信号である（ｘ２ｙ２＋ｘ１ｙ３）との排他的論理和演算を行い、（ｘ４ｙ０＋ｘ３ｙ１＋ｘ２ｙ２＋ｘ１ｙ３）を出力する。
ＥＸＯＲ回路３０４＿１４は、ＥＸＯＲ回路３０４＿１３の出力信号である（ｘ４ｙ０＋ｘ３ｙ１＋ｘ２ｙ２＋ｘ１ｙ３）と、アンド回路３０４＿５の出力信号であるｘ０ｙ４との排他的論理和演算を行い、ａ４（＝ｘ４ｙ０＋ｘ３ｙ１＋ｘ２ｙ２＋ｘ１ｙ３＋ｘ０ｙ４）を出力する。
【００４９】
ａ１３演算部３１３は、アンド回路３１３＿１、アンド回路３１３＿２、アンド回路３１３＿３、アンド回路３１３＿４、ＥＸＯＲ回路３１３＿１１、ＥＸＯＲ回路３１３＿１２、ＥＸＯＲ回路３１３＿１３から構成される。
アンド回路３１３＿１は、Ｘ［８］＝ｘ８とＹ［５］＝ｙ５との論理積演算を行い、ｘ８ｙ５を出力する。
アンド回路３１３＿２は、Ｘ［７］＝ｘ７とＹ［６］＝ｙ６との論理積演算を行い、ｘ７ｙ６を出力する。
アンド回路３１３＿３は、Ｘ［６］＝ｘ６とＹ［７］＝ｙ７との論理積演算を行い、ｘ６ｙ７を出力する。
アンド回路３１３＿４は、Ｘ［５］＝ｘ５とＹ［８］＝ｙ８との論理積演算を行い、ｘ５ｙ８を出力する。
ＥＸＯＲ回路３１３＿１１は、アンド回路３１３＿１の出力信号であるｘ８ｙ５と、アンド回路３１３＿２の出力信号であるｘ７ｙ６との排他的論理和演算を行い、（ｘ８ｙ５＋ｘ７ｙ６）を出力する。
ＥＸＯＲ回路３１３＿１２は、アンド回路３１３＿３の出力信号であるｘ６ｙ７と、アンド回路３１３＿４の出力信号であるｘ５ｙ８との排他的論理和演算を行い、（ｘ６ｙ７＋ｘ５ｙ８）を出力する。
ＥＸＯＲ回路３１３＿１３は、ＥＸＯＲ回路３１３＿１１の出力信号である（ｘ８ｙ５＋ｘ７ｙ６）と、ＥＸＯＲ回路３１３＿１２の出力信号である（ｘ６ｙ７＋ｘ５ｙ８）との排他的論理和演算を行い、ａ１３（＝ｘ８ｙ５＋ｘ７ｙ６＋ｘ６ｙ７＋ｘ５ｙ８）を出力する。
【００５０】
Ｚ［４］演算部４０４は、ＥＸＯＲ回路４０４＿１、ＥＸＯＲ回路４０４＿２、ＥＸＯＲ回路４０４＿３から構成される。
ＥＸＯＲ回路４０４＿１は、ａ４演算部３０４の出力信号であるａ４（＝ｘ４ｙ０＋ｘ３ｙ１＋ｘ２ｙ２＋ｘ１ｙ３＋ｘ０ｙ４）と、ａ９演算部３０９の出力信号であるａ９（＝ｘ８ｙ１＋ｘ７ｙ２＋ｘ６ｙ３＋ｘ５ｙ４＋ｘ４ｙ５＋ｘ３ｙ６＋ｘ２ｙ７＋ｘ１ｙ８）との排他的論理和演算を行い、（ａ４＋ａ９）を出力する。
ＥＸＯＲ回路４０４＿２は、ａ１３演算部３１３の出力信号であるａ１３（＝ｘ８ｙ５＋ｘ７ｙ６＋ｘ６ｙ７＋ｘ５ｙ８）と、ａ１４演算部３１４の出力信号であるａ１４（＝ｘ８ｙ６＋ｘ７ｙ７＋ｘ６ｙ８）との排他的論理和演算を行い、（ａ１３＋ａ１４）を出力する。
ＥＸＯＲ回路４０４＿３は、ＥＸＯＲ回路４０４＿１の出力信号である（ａ４＋ａ９）と、ＥＸＯＲ回路４０４＿２の出力信号である（ａ１３＋ａ１４）との排他的論理和演算を行い、（ａ４＋ａ９＋ａ１３＋ａ１４）を出力する。
このように、要素演算部３４は、Ｚ［８：０］のうちの１ビットであるＺ［４］を演算して出力する。その論理ゲートの個数は、ａ９演算部３０９、及びａ１４演算部３１４を他の要素演算部と兼用しない場合、アンド回路が２０個、ＥＸＯＲ回路が１９個であり、合計３９個である。また、要素演算部３３の内部ノードの個数は、ＥＸＯＲ回路の入力ノードの個数の２倍と等しく、１８個である。
一方、ａ９演算部３０９、及びａ１４演算部３１４を他の要素演算部と兼用する場合、追加として必要となるアンド回路が９個、ＥＸＯＲ回路が１０個であり、合計１９個である。また、要素演算部３４の内部ノードの個数の増加数は、ａ４演算部３０４、及びａ１３演算部３１３におけるＥＸＯＲ回路の入力ノードの個数の２倍（１４個）と、Ｚ［４］演算部４０４における３個のＥＸＯＲ回路の入力ノードのうち４個との合計１８個である。
【００５１】
次に、Ｚ［５］について演算する要素演算部３５は、図６に示すように、ａ５演算部３０５、ａ１０演算部３１０、ａ１４演算部３１４、ａ１５演算部３１５、及びＺ［５］演算部４０５から構成される。このうち、ａ１０演算部３１０、ａ１４演算部３１４、及びａ１５演算部３１５は、それぞれ図３に記載の要素演算部３０または要素演算部３１の回路と同じ回路であり、その説明を省略する。また、ａ１０演算部３１０、ａ１４演算部３１４、及びａ１５演算部３１５は、要素演算部３０または要素演算部３１と兼用することが可能である。
【００５２】
ａ５演算部３０５は、アンド回路３０５＿１、アンド回路３０５＿２、アンド回路３０５＿３、アンド回路３０５＿４、アンド回路３０５＿５、アンド回路３０５＿６、ＥＸＯＲ回路３０５＿１１、ＥＸＯＲ回路３０５＿１２、ＥＸＯＲ回路３０５＿１３、ＥＸＯＲ回路３０５＿１４、ＥＸＯＲ回路３０５＿１５から構成される。
アンド回路３０５＿１は、Ｘ［５］＝ｘ５とＹ［０］＝ｙ０との論理積演算を行い、ｘ５ｙ０を出力する。
アンド回路３０５＿２は、Ｘ［４］＝ｘ４とＹ［１］＝ｙ１との論理積演算を行い、ｘ４ｙ１を出力する。
アンド回路３０５＿３は、Ｘ［３］＝ｘ３とＹ［２］＝ｙ２との論理積演算を行い、ｘ３ｙ２を出力する。
アンド回路３０５＿４は、Ｘ［２］＝ｘ２とＹ［３］＝ｙ３との論理積演算を行い、ｘ２ｙ３を出力する。
アンド回路３０５＿５は、Ｘ［１］＝ｘ１とＹ［４］＝ｙ４との論理積演算を行い、ｘ１ｙ４を出力する。
アンド回路３０５＿６は、Ｘ［０］＝ｘ０とＹ［５］＝ｙ５との論理積演算を行い、ｘ０ｙ５を出力する。
【００５３】
ＥＸＯＲ回路３０５＿１１は、アンド回路３０５＿１の出力信号であるｘ５ｙ０と、アンド回路３０５＿２の出力信号であるｘ４ｙ１との排他的論理和演算を行い、（ｘ５ｙ０＋ｘ４ｙ１）を出力する。
ＥＸＯＲ回路３０５＿１２は、アンド回路３０５＿３の出力信号であるｘ３ｙ２と、アンド回路３０５＿４の出力信号であるｘ２ｙ３との排他的論理和演算を行い、（ｘ３ｙ２＋ｘ２ｙ３）を出力する。
ＥＸＯＲ回路３０５＿１３は、アンド回路３０５＿５の出力信号であるｘ１ｙ４と、アンド回路３０５＿６の出力信号であるｘ０ｙ５との排他的論理和演算を行い、（ｘ１ｙ４＋ｘ０ｙ５）を出力する。
ＥＸＯＲ回路３０５＿１４は、ＥＸＯＲ回路３０５＿１１の出力信号である（ｘ５ｙ０＋ｘ４ｙ１）と、ＥＸＯＲ回路３０５＿１２の出力信号である（ｘ３ｙ２＋ｘ２ｙ３）との排他的論理和演算を行い、（ｘ５ｙ０＋ｘ４ｙ１＋ｘ３ｙ２＋ｘ２ｙ３）を出力する。
ＥＸＯＲ回路３０５＿１５は、ＥＸＯＲ回路３０５＿１４の出力信号である（ｘ５ｙ０＋ｘ４ｙ１＋ｘ３ｙ２＋ｘ２ｙ３）と、ＥＸＯＲ回路３０９＿１３の出力信号である（ｘ１ｙ４＋ｘ０ｙ５）との排他的論理和演算を行い、ａ５（＝ｘ５ｙ０＋ｘ４ｙ１＋ｘ３ｙ２＋ｘ２ｙ３＋ｘ１ｙ４＋ｘ０ｙ５）を出力する。
【００５４】
Ｚ［５］演算部４０５は、ＥＸＯＲ回路４０５＿１、ＥＸＯＲ回路４０５＿２、ＥＸＯＲ回路４０５＿３から構成される。
ＥＸＯＲ回路４０５＿１は、ａ５演算部３０５の出力信号であるａ５（＝ｘ５ｙ０＋ｘ４ｙ１＋ｘ３ｙ２＋ｘ２ｙ３＋ｘ１ｙ４＋ｘ０ｙ５）と、ａ１０演算部３１０の出力信号であるａ１０（＝ｘ８ｙ２＋ｘ７ｙ３＋ｘ６ｙ４＋ｘ５ｙ５＋ｘ４ｙ６＋ｘ３ｙ７＋ｘ２ｙ８）との排他的論理和演算を行い、（ａ５＋ａ１０）を出力する。
ＥＸＯＲ回路４０５＿２は、ａ１４演算部３１４の出力信号であるａ１４（＝ｘ８ｙ６＋ｘ７ｙ７＋ｘ６ｙ８）と、ａ１５演算部３１５の出力信号であるａ１５（＝ｘ８ｙ７＋ｘ７ｙ８）との排他的論理和演算を行い、（ａ１４＋ａ１５）を出力する。
ＥＸＯＲ回路４０５＿３は、ＥＸＯＲ回路４０５＿１の出力信号である（ａ５＋ａ１０）と、ＥＸＯＲ回路４０５＿２の出力信号である（ａ１４＋ａ１５）との排他的論理和演算を行い、（ａ５＋ａ１０＋ａ１４＋ａ１５）を出力する。
このように、要素演算部３５は、Ｚ［８：０］のうちの１ビットであるＺ［５］を演算して出力する。その論理ゲートの個数は、ａ１０演算部３１０、ａ１４演算部３１４、及びａ１５演算部３１５を他の要素演算部と兼用しない場合、アンド回路が１８個、ＥＸＯＲ回路が１７個であり、合計３５個である。また、要素演算部３４の内部ノードの個数は、ＥＸＯＲ回路の入力ノードの個数の２倍と等しく、３４個である。
一方、ａ１０演算部３１０、ａ１４演算部３１４、及びａ１５演算部３１５を他の要素演算部と兼用する場合、追加として必要となるアンド回路が６個、ＥＸＯＲ回路が８個であり、合計１４個である。また、要素演算部３５の内部ノードの個数の増加数は、ａ５演算部３０５におけるＥＸＯＲ回路の入力ノードの個数の２倍（１０個）と、Ｚ［５］演算部４０５における３個のＥＸＯＲ回路の入力ノードのうち３個との合計１３個である。
【００５５】
次に、Ｚ［６］について演算する要素演算部３６は、図７に示すように、ａ６演算部３０６、ａ１１演算部３１１、ａ１５演算部３１５、ａ１６演算部３１６、及びＺ［６］演算部４０６から構成される。このうち、ａ１１演算部３１１、ａ１５演算部３１５、及びａ１６演算部３１６は、それぞれ図３、図４に記載の要素演算部３１または要素演算部３２の回路と同じ回路であり、その説明を省略する。また、ａ１１演算部３１１、ａ１５演算部３１５、及びａ１６演算部３１６は、要素演算部３１または要素演算部３２と兼用することが可能である。
【００５６】
ａ６演算部３０６は、アンド回路３０６＿１、アンド回路３０６＿２、アンド回路３０６＿３、アンド回路３０６＿４、アンド回路３０６＿５、アンド回路３０６＿６、アンド回路３０６＿７、ＥＸＯＲ回路３０６＿１１、ＥＸＯＲ回路３０６＿１２、ＥＸＯＲ回路３０６＿１３、ＥＸＯＲ回路３０６＿１４、ＥＸＯＲ回路３０６＿１５、ＥＸＯＲ回路３０６＿１６から構成される。
アンド回路３０６＿１は、Ｘ［６］＝ｘ６とＹ［０］＝ｙ０との論理積演算を行い、ｘ６ｙ０を出力する。
アンド回路３０６＿２は、Ｘ［５］＝ｘ５とＹ［１］＝ｙ１との論理積演算を行い、ｘ５ｙ１を出力する。
アンド回路３０６＿３は、Ｘ［４］＝ｘ４とＹ［２］＝ｙ２との論理積演算を行い、ｘ４ｙ２を出力する。
アンド回路３０６＿４は、Ｘ［３］＝ｘ３とＹ［３］＝ｙ３との論理積演算を行い、ｘ３ｙ３を出力する。
アンド回路３０６＿５は、Ｘ［２］＝ｘ２とＹ［４］＝ｙ４との論理積演算を行い、ｘ２ｙ４を出力する。
アンド回路３０６＿６は、Ｘ［１］＝ｘ１とＹ［５］＝ｙ５との論理積演算を行い、ｘ１ｙ５を出力する。
アンド回路３０６＿７は、Ｘ［０］＝ｘ０とＹ［６］＝ｙ６との論理積演算を行い、ｘ０ｙ６を出力する。
【００５７】
ＥＸＯＲ回路３０６＿１１は、アンド回路３０６＿１の出力信号であるｘ６ｙ０と、アンド回路３０６＿２の出力信号であるｘ５ｙ１との排他的論理和演算を行い、（ｘ６ｙ０＋ｘ５ｙ１）を出力する。
ＥＸＯＲ回路３０６＿１２は、アンド回路３０６＿３の出力信号であるｘ４ｙ２と、アンド回路３０６＿４の出力信号であるｘ３ｙ３との排他的論理和演算を行い、（ｘ４ｙ２＋ｘ３ｙ３）を出力する。
ＥＸＯＲ回路３０６＿１３は、アンド回路３０６＿５の出力信号であるｘ２ｙ４と、アンド回路３０６＿６の出力信号であるｘ１ｙ５との排他的論理和演算を行い、（ｘ２ｙ４＋ｘ１ｙ５）を出力する。
ＥＸＯＲ回路３０６＿１４は、ＥＸＯＲ回路３０６＿１１の出力信号である（ｘ６ｙ０＋ｘ５ｙ１）と、ＥＸＯＲ回路３０６＿１２の出力信号である（ｘ４ｙ２＋ｘ３ｙ３）との排他的論理和演算を行い、（ｘ６ｙ０＋ｘ５ｙ１＋ｘ４ｙ２＋ｘ３ｙ３）を出力する。
ＥＸＯＲ回路３０６＿１５は、ＥＸＯＲ回路３０６＿１３の出力信号である（ｘ２ｙ４＋ｘ１ｙ５）と、アンド回路３０６＿８の出力信号であるｘ０ｙ６との排他的論理和演算を行い、（ｘ２ｙ４＋ｘ１ｙ５＋ｘ０ｙ６）を出力する。
ＥＸＯＲ回路３０６＿１６は、ＥＸＯＲ回路３０６＿１４の出力信号である（ｘ６ｙ０＋ｘ５ｙ１＋ｘ４ｙ２＋ｘ３ｙ３）と、ＥＸＯＲ回路３０９＿１５の出力信号である（ｘ２ｙ４＋ｘ１ｙ５＋ｘ０ｙ６）との排他的論理和演算を行い、ａ６（＝ｘ６ｙ０＋ｘ５ｙ１＋ｘ４ｙ２＋ｘ３ｙ３＋ｘ２ｙ４＋ｘ１ｙ５＋ｘ０ｙ６）を出力する。
【００５８】
Ｚ［６］演算部４０６は、ＥＸＯＲ回路４０６＿１、ＥＸＯＲ回路４０６＿２、ＥＸＯＲ回路４０６＿３から構成される。
ＥＸＯＲ回路４０６＿１は、ａ６演算部３０６の出力信号であるａ６（＝ｘ６ｙ０＋ｘ５ｙ１＋ｘ４ｙ２＋ｘ３ｙ３＋ｘ２ｙ４＋ｘ１ｙ５＋ｘ０ｙ６）と、ａ１１演算部３１１の出力信号であるａ１１（＝ｘ８ｙ３＋ｘ７ｙ４＋ｘ６ｙ５＋ｘ５ｙ６＋ｘ４ｙ７＋ｘ３ｙ８）との排他的論理和演算を行い、（ａ６＋ａ１１）を出力する。
ＥＸＯＲ回路４０６＿２は、ａ１５演算部３１５の出力信号であるａ１５（＝ｘ８ｙ７＋ｘ７ｙ８）と、ａ１６演算部３１６の出力信号であるａ１６（＝ｘ８ｙ８）との排他的論理和演算を行い、（ａ１５＋ａ１６）を出力する。
ＥＸＯＲ回路４０６＿３は、ＥＸＯＲ回路４０６＿１の出力信号である（ａ６＋ａ１１）と、ＥＸＯＲ回路４０６＿２の出力信号である（ａ１５＋ａ１６）との排他的論理和演算を行い、（ａ６＋ａ１１＋ａ１５＋ａ１６）を出力する。
このように、要素演算部３６は、Ｚ［８：０］のうちの１ビットであるＺ［６］を演算して出力する。その論理ゲートの個数は、ａ１１演算部３１１、ａ１５演算部３１５、及びａ１６演算部３１６を他の要素演算部と兼用しない場合、アンド回路が１６個、ＥＸＯＲ回路が１５個であり、合計３１個である。また、要素演算部３６の内部ノードの個数は、ＥＸＯＲ回路の入力ノードの個数の２倍と等しく、３０個である。
一方、ａ１１演算部３１１、ａ１５演算部３１５、及びａ１６演算部３１６を他の要素演算部と兼用する場合、追加として必要となるアンド回路が７、ＥＸＯＲ回路が９であり、合計１６個である。また、要素演算部３６の内部ノードの個数の増加数は、ａ６演算部３０６におけるＥＸＯＲ回路の入力ノードの個数の２倍（１２個）と、Ｚ［６］演算部４０６における３個のＥＸＯＲ回路の入力ノードのうち３個との合計１５個である。
【００５９】
次に、Ｚ［７］について演算する要素演算部３７は、図８に示すように、ａ７演算部３０７、ａ１２演算部３１２、ａ１６演算部３１６、及びＺ［７］演算部４０７から構成される。このうち、ａ１２演算部３１２、及びａ１６演算部３１６は、それぞれ図４に記載の要素演算部３２または要素演算部３３の回路と同じ回路であり、その説明を省略する。また、ａ１２演算部３１２、及びａ１６演算部３１６は、要素演算部３２または要素演算部３３と兼用することが可能である。
【００６０】
ａ７演算部３０７は、アンド回路３０７＿１、アンド回路３０７＿２、アンド回路３０７＿３、アンド回路３０７＿４、アンド回路３０７＿５、アンド回路３０７＿６、アンド回路３０７＿７、アンド回路３０７＿８、ＥＸＯＲ回路３０７＿１１、ＥＸＯＲ回路３０７＿１２、ＥＸＯＲ回路３０７＿１３、ＥＸＯＲ回路３０７＿１４、ＥＸＯＲ回路３０７＿１５、ＥＸＯＲ回路３０７＿１６、ＥＸＯＲ回路３０７＿１７から構成される。
アンド回路３０７＿１は、Ｘ［７］＝ｘ７とＹ［０］＝ｙ０との論理積演算を行い、ｘ７ｙ０を出力する。
アンド回路３０７＿２は、Ｘ［６］＝ｘ６とＹ［１］＝ｙ１との論理積演算を行い、ｘ６ｙ１を出力する。
アンド回路３０７＿３は、Ｘ［５］＝ｘ５とＹ［２］＝ｙ２との論理積演算を行い、ｘ５ｙ２を出力する。
アンド回路３０７＿４は、Ｘ［４］＝ｘ４とＹ［３］＝ｙ３との論理積演算を行い、ｘ４ｙ３を出力する。
アンド回路３０７＿５は、Ｘ［３］＝ｘ３とＹ［４］＝ｙ４との論理積演算を行い、ｘ３ｙ４を出力する。
アンド回路３０７＿６は、Ｘ［２］＝ｘ２とＹ［５］＝ｙ５との論理積演算を行い、ｘ２ｙ５を出力する。
アンド回路３０７＿７は、Ｘ［１］＝ｘ１とＹ［６］＝ｙ６との論理積演算を行い、ｘ１ｙ６を出力する。
アンド回路３０７＿８は、Ｘ［０］＝ｘ０とＹ［７］＝ｙ７との論理積演算を行い、ｘ０ｙ７を出力する。
【００６１】
ＥＸＯＲ回路３０７＿１１は、アンド回路３０７＿１の出力信号であるｘ７ｙ０と、アンド回路３０７＿２の出力信号であるｘ６ｙ１との排他的論理和演算を行い、（ｘ７ｙ０＋ｘ６ｙ１）を出力する。
ＥＸＯＲ回路３０７＿１２は、アンド回路３０７＿３の出力信号であるｘ５ｙ２と、アンド回路３０７＿４の出力信号であるｘ４ｙ３との排他的論理和演算を行い、（ｘ５ｙ２＋ｘ４ｙ３）を出力する。
ＥＸＯＲ回路３０７＿１３は、アンド回路３０７＿５の出力信号であるｘ３ｙ４と、アンド回路３０７＿６の出力信号であるｘ２ｙ５との排他的論理和演算を行い、（ｘ３ｙ４＋ｘ２ｙ５）を出力する。
ＥＸＯＲ回路３０７＿１４は、アンド回路３０７＿７の出力信号であるｘ１ｙ６と、アンド回路３０７＿８の出力信号であるｘ０ｙ７との排他的論理和演算を行い、（ｘ１ｙ６＋ｘ０ｙ７）を出力する。
ＥＸＯＲ回路３０７＿１５は、ＥＸＯＲ回路３０７＿１１の出力信号である（ｘ７ｙ０＋ｘ６ｙ１）と、ＥＸＯＲ回路３０７＿１２の出力信号である（ｘ５ｙ２＋ｘ４ｙ３）との排他的論理和演算を行い、（ｘ７ｙ０＋ｘ６ｙ１＋ｘ５ｙ２＋ｘ４ｙ３）を出力する。
ＥＸＯＲ回路３０７＿１６は、ＥＸＯＲ回路３０７＿１３の出力信号である（ｘ３ｙ４＋ｘ２ｙ５）と、ＥＸＯＲ回路３０７＿１４の出力信号である（ｘ１ｙ６＋ｘ０ｙ７）との排他的論理和演算を行い、（ｘ３ｙ４＋ｘ２ｙ５＋ｘ１ｙ６＋ｘ０ｙ７）を出力する。
ＥＸＯＲ回路３０７＿１７は、ＥＸＯＲ回路３０７＿１５の出力信号である（ｘ７ｙ０＋ｘ６ｙ１＋ｘ５ｙ２＋ｘ４ｙ３）と、ＥＸＯＲ回路３０７＿１６の出力信号である（ｘ３ｙ４＋ｘ２ｙ５＋ｘ１ｙ６＋ｘ０ｙ７）との排他的論理和演算を行い、ａ７（＝ｘｘ７ｙ０＋ｘ６ｙ１＋ｘ５ｙ２＋ｘ４ｙ３＋ｘ３ｙ４＋ｘ２ｙ５＋ｘ１ｙ６＋ｘ０ｙ７）を出力する。
【００６２】
Ｚ［７］演算部４０７は、ＥＸＯＲ回路４０７＿１、ＥＸＯＲ回路４０７＿２から構成される。
ＥＸＯＲ回路４０７＿１は、ａ７演算部３０７の出力信号であるａ７（＝ｘ７ｙ０＋ｘ６ｙ１＋ｘ５ｙ２＋ｘ４ｙ３＋ｘ３ｙ４＋ｘ２ｙ５＋ｘ１ｙ６＋ｘ０ｙ７）と、ａ１２演算部３１２の出力信号であるａ１２（＝ｘ８ｙ４＋ｘ７ｙ５＋ｘ６ｙ６＋ｘ５ｙ７＋ｘ４ｙ８）との排他的論理和演算を行い、（ａ７＋ａ１２）を出力する。
ＥＸＯＲ回路４０７＿２は、ＥＸＯＲ回路４０７＿１の出力信号である（ａ７＋ａ１２）と、ａ１６演算部３１６の出力信号であるａ１６（＝ｘ８ｙ８）との排他的論理和演算を行い、（ａ７＋ａ１２＋ａ１６）を出力する。
このように、要素演算部３７は、Ｚ［８：０］のうちの１ビットであるＺ［７］を演算して出力する。その論理ゲートの個数は、ａ１２演算部３１２、及びａ１６演算部３１６を他の要素演算部と兼用しない場合、アンド回路が１４個、ＥＸＯＲ回路が１３個であり、合計２７個である。また、要素演算部３７の内部ノードの個数は、ＥＸＯＲ回路の入力ノードの個数の２倍と等しく、２６個である。
一方、ａ１２演算部３１２、及びａ１６演算部３１６を他の要素演算部と兼用する場合、追加として必要となるアンド回路が８個、ＥＸＯＲ回路が９個であり、合計１７個である。また、要素演算部３７の内部ノードの個数の増加数は、ａ７演算部３０７におけるＥＸＯＲ回路の入力ノードの個数の２倍（１４個）と、Ｚ［７］演算部４０７における２個のＥＸＯＲ回路の入力ノードのうち２個との合計１６個である。
【００６３】
次に、Ｚ［８］について演算する要素演算部３８は、図８に示すように、ａ８演算部３０８、ａ１３演算部３１３、及びＺ［８］演算部４０８から構成される。このうち、ａ１３演算部３１３は、図５に記載の要素演算部３４の回路と同じ回路であり、その説明を省略する。また、ａ１３演算部３１３は、要素演算部３４と兼用することが可能である。
【００６４】
ａ８演算部３０８は、アンド回路３０８＿１、アンド回路３０８＿２、アンド回路３０８＿３、アンド回路３０８＿４、アンド回路３０８＿５、アンド回路３０８＿６、アンド回路３０８＿７、アンド回路３０８＿８、アンド回路３０８＿９、ＥＸＯＲ回路３０８＿１１、ＥＸＯＲ回路３０８＿１２、ＥＸＯＲ回路３０８＿１３、ＥＸＯＲ回路３０８＿１４、ＥＸＯＲ回路３０８＿１５、ＥＸＯＲ回路３０８＿１６、ＥＸＯＲ回路３０８＿１７、ＥＸＯＲ回路３０８＿１８から構成される。
アンド回路３０８＿１は、Ｘ［８］＝ｘ８とＹ［０］＝ｙ０との論理積演算を行い、ｘ８ｙ０を出力する。
アンド回路３０８＿２は、Ｘ［７］＝ｘ７とＹ［１］＝ｙ１との論理積演算を行い、ｘ７ｙ１を出力する。
アンド回路３０８＿３は、Ｘ［６］＝ｘ６とＹ［２］＝ｙ２との論理積演算を行い、ｘ６ｙ２を出力する。
アンド回路３０８＿４は、Ｘ［５］＝ｘ５とＹ［３］＝ｙ３との論理積演算を行い、ｘ５ｙ３を出力する。
アンド回路３０８＿５は、Ｘ［４］＝ｘ４とＹ［４］＝ｙ４との論理積演算を行い、ｘ４ｙ４を出力する。
アンド回路３０８＿６は、Ｘ［３］＝ｘ３とＹ［５］＝ｙ５との論理積演算を行い、ｘ３ｙ５を出力する。
アンド回路３０８＿７は、Ｘ［２］＝ｘ２とＹ［６］＝ｙ６との論理積演算を行い、ｘ２ｙ６を出力する。
アンド回路３０８＿８は、Ｘ［１］＝ｘ１とＹ［７］＝ｙ７との論理積演算を行い、ｘ１ｙ７を出力する。
アンド回路３０８＿９は、Ｘ［０］＝ｘ０とＹ［８］＝ｙ８との論理積演算を行い、ｘ０ｙ８を出力する。
【００６５】
ＥＸＯＲ回路３０８＿１１は、アンド回路３０８＿１の出力信号であるｘ８ｙ０と、アンド回路３０８＿２の出力信号であるｘ７ｙ１との排他的論理和演算を行い、（ｘ８ｙ０＋ｘ７ｙ１）を出力する。
ＥＸＯＲ回路３０８＿１２は、アンド回路３０８＿３の出力信号であるｘ６ｙ２と、アンド回路３０８＿４の出力信号であるｘ５ｙ３との排他的論理和演算を行い、（ｘ６ｙ２＋ｘ５ｙ３）を出力する。
ＥＸＯＲ回路３０８＿１３は、アンド回路３０８＿５の出力信号であるｘ４ｙ４と、アンド回路３０８＿６の出力信号であるｘ３ｙ６との排他的論理和演算を行い、（ｘ４ｙ４＋ｘ３ｙ５）を出力する。
ＥＸＯＲ回路３０８＿１４は、アンド回路３０８＿７の出力信号であるｘ２ｙ６と、アンド回路３０８＿８の出力信号であるｘ１ｙ７との排他的論理和演算を行い、（ｘ２ｙ６＋ｘ１ｙ７）を出力する。
ＥＸＯＲ回路３０８＿１５は、ＥＸＯＲ回路３０８＿１１の出力信号である（ｘ８ｙ０＋ｘ７ｙ１）と、ＥＸＯＲ回路３０８＿１２の出力信号である（ｘ６ｙ２＋ｘ５ｙ３）との排他的論理和演算を行い、（ｘ８ｙ０＋ｘ７ｙ１＋ｘ６ｙ２＋ｘ５ｙ３）を出力する。
ＥＸＯＲ回路３０８＿１６は、ＥＸＯＲ回路３０８＿１３の出力信号である（ｘ４ｙ４＋ｘ３ｙ５）と、ＥＸＯＲ回路３０８＿１４の出力信号である（ｘ２ｙ６＋ｘ１ｙ７）との排他的論理和演算を行い、（ｘ４ｙ４＋ｘ３ｙ５＋ｘ２ｙ６＋ｘ１ｙ７）を出力する。
ＥＸＯＲ回路３０８＿１７は、ＥＸＯＲ回路３０８＿１５の出力信号である（ｘ８ｙ０＋ｘ７ｙ１＋ｘ６ｙ２＋ｘ５ｙ３）と、ＥＸＯＲ回路３０８＿１６の出力信号である（ｘ４ｙ４＋ｘ３ｙ５＋ｘ２ｙ６＋ｘ１ｙ７）との排他的論理和演算を行い、（ｘ８ｙ０＋ｘ７ｙ１＋ｘ６ｙ２＋ｘ５ｙ３＋ｘ４ｙ４＋ｘ３ｙ５＋ｘ２ｙ６＋ｘ１ｙ７）を出力する。
ＥＸＯＲ回路３０８＿１８は、ＥＸＯＲ回路３０８＿１７の出力信号である（ｘ８ｙ０＋ｘ７ｙ１＋ｘ６ｙ２＋ｘ５ｙ３＋ｘ４ｙ４＋ｘ３ｙ５＋ｘ２ｙ６＋ｘ１ｙ７）と、アンド回路３０８＿９の出力信号であるｘ０ｙ８との排他的論理和演算を行い、ａ８（＝ｘ８ｙ０＋ｘ７ｙ１＋ｘ６ｙ２＋ｘ５ｙ３＋ｘ４ｙ４＋ｘ３ｙ５＋ｘ２ｙ６＋ｘ１ｙ７＋ｘ０ｙ８）を出力する。
【００６６】
Ｚ［８］演算部４０８は、ＥＸＯＲ回路４０８＿１から構成される。
ＥＸＯＲ回路４０８＿１は、ａ８演算部３０８の出力信号であるａ８（＝ｘ８ｙ０＋ｘ７ｙ１＋ｘ６ｙ２＋ｘ５ｙ３＋ｘ４ｙ４＋ｘ３ｙ５＋ｘ２ｙ６＋ｘ１ｙ７＋ｘ０ｙ８）と、ａ１３演算部３１３の出力信号であるａ１３（＝ｘ８ｙ５＋ｘ７ｙ６＋ｘ６ｙ７＋ｘ５ｙ８）との排他的論理和演算を行い、（ａ８＋ａ１３）を出力する。
このように、要素演算部３８は、Ｚ［８：０］のうちの１ビットであるＺ［８］を演算して出力する。その論理ゲートの個数は、ａ１３演算部３１３を他の要素演算部と兼用しない場合、アンド回路が１３個、ＥＸＯＲ回路が１２個であり、合計２５個である。また、要素演算部３８の内部ノードの個数は、ＥＸＯＲ回路の入力ノードの個数の２倍と等しく、２４個である。
一方、ａ１３演算部３１３を他の要素演算部と兼用する場合、追加として必要となるアンド回路が９個、ＥＸＯＲ回路が９個であり、合計１８個である。また、要素演算部３８の内部ノードの個数の増加数は、ａ８演算部３０８におけるＥＸＯＲ回路の入力ノードの個数の２倍（１６個）と、Ｚ［８］演算部４０８における１個のＥＸＯＲ回路の入力ノードのうち１個との合計１７個である。
【００６７】
このように、ガロア体乗算回路における各要素演算部では、入力信号の本数、構成する論理ゲート（アンド回路、ＥＸＯＲ回路）の個数、論理ゲートの出力と次段の論理ゲートとの間の接続点（中間ノード）の個数が、回路毎に相違し、同じレイアウト構成、及び配線レイアウトを取ることが出来ない。そのため、かかるガロア体乗算回路では、ガロア体乗算回路を例えば半導体装置に搭載する際の回路規模を縮小することが困難であった。すなわち、ガロア体乗算回路では、乗算結果であるＺ［８：０］の各成分を演算する要素演算部（要素演算部３０〜要素演算部３８）に規則性がないため、回路規模の縮小を図ることが困難であった。
そこで、本実施形態においては、各要素演算部において入力信号の本数、構成する論理ゲートの個数、中間ノードの個数を全て同じとすることにより、要素演算部間で回路構成に関して規則性を有するガロア体乗算回路について説明する。
【００６８】
［第１の実施形態］
Ｚ［８：０］のうちＺ［０］は、Ｚ［０］＝ａ０＋ａ９＋ａ１４と表されるが（図２参照）、これを、Ｘ［８：０］、及びＹ［８：０］の成分（要素）を用い、更にＸ［８：０］の成分毎に、すなわちｘ０〜ｘ８毎にまとめると、Ｚ［０］は以下の様に表される。
Ｚ［０］＝ｙ０ｘ０＋ｙ８ｘ１＋ｙ７ｘ２＋ｙ６ｘ３＋ｙ５ｘ４＋ｙ４ｘ５＋（ｙ３＋ｙ８）ｘ６＋（ｙ２＋ｙ７）ｘ７＋（ｙ１＋ｙ６）ｘ８
ここで、ｙ３＋ｙ８＝ｐ０、ｙ２＋ｙ７＝ｐ１、ｙ１＋ｙ６＝ｐ２とすれば、Ｚ［０］は、更に、Ｘ［８：０］の各ビット、Ｙ［８：０］の各ビット、Ｙ［８：０］のビットの組合せを用いて下記の様に表される。
Ｚ［０］＝ｙ０ｘ０＋ｙ８ｘ１＋ｙ７ｘ２＋ｙ６ｘ３＋ｙ５ｘ４＋ｙ４ｘ５＋ｐ０ｘ６＋ｐ１ｘ７＋ｐ２ｘ８
【００６９】
次に、Ｚ［８：０］のうちＺ［１］は、Ｚ［１］＝ａ１＋ａ１０＋ａ１５と表されるが（図２参照）、これを、Ｘ［８：０］、及びＹ［８：０］の成分（要素）を用い、更にＸ［８：０］の成分毎に、すなわちｘ０〜ｘ８毎にまとめると、Ｚ［１］は以下の様に表される。
Ｚ［１］＝ｙ１ｘ０＋ｙ０ｘ１＋ｙ８ｘ２＋ｙ７ｘ３＋ｙ６ｘ４＋ｙ５ｘ５＋ｙ４ｘ６＋（ｙ３＋ｙ８）ｘ７＋（ｙ２＋ｙ７）ｘ８
ここで、上述のZ［０］と同様に、ｙ３＋ｙ８＝ｐ０、ｙ２＋ｙ７＝ｐ１とすれば、Ｚ［１］は、更に、Ｘ［８：０］の各ビット、Ｙ［８：０］の各ビット、Ｙ［８：０］のビットの組合せを用いて下記の様に表される。
Ｚ［１］＝ｙ１ｘ０＋ｙ０ｘ１＋ｙ８ｘ２＋ｙ７ｘ３＋ｙ６ｘ４＋ｙ５ｘ５＋ｙ４ｘ６＋ｐ０ｘ７＋ｐ１ｘ８
【００７０】
次に、Ｚ［８：０］のうちＺ［２］は、Ｚ［２］＝ａ２＋ａ１１＋ａ１６と表されるが（図２参照）、これを、Ｘ［８：０］、及びＹ［８：０］の成分（要素）を用い、更にＸ［８：０］の成分毎に、すなわちｘ０〜ｘ８毎にまとめると、Ｚ［２］は以下の様に表される。
Ｚ［２］＝ｙ２ｘ０＋ｙ１ｘ１＋ｙ０ｘ２＋ｙ８ｘ３＋ｙ７ｘ４＋ｙ６ｘ５＋ｙ５ｘ６＋ｙ４ｘ７＋（ｙ３＋ｙ８）ｘ８
ここで、上述のZ［０］、Z［１］と同様に、ｙ３＋ｙ８＝ｐ０とすれば、Ｚ［２］は、更に、Ｘ［８：０］の各ビット、Ｙ［８：０］の各ビット、Ｙ［８：０］のビットの組合せを用いて下記の様に表される。
Ｚ［２］＝ｙ２ｘ０＋ｙ１ｘ１＋ｙ０ｘ２＋ｙ８ｘ３＋ｙ７ｘ４＋ｙ６ｘ５＋ｙ５ｘ６＋ｙ４ｘ７＋ｐ０ｘ８
【００７１】
次に、Ｚ［８：０］のうちＺ［３］は、Ｚ［３］＝ａ３＋ａ１２と表されるが（図２参照）、これを、Ｘ［８：０］、及びＹ［８：０］の成分（要素）を用い、更にＸ［８：０］の成分毎に、すなわちｘ０〜ｘ８毎にまとめると、Ｚ［３］は以下の様に表される。
Ｚ［３］＝ｙ３ｘ０＋ｙ２ｘ１＋ｙ１ｘ２＋ｙ０ｘ３＋ｙ８ｘ４＋ｙ７ｘ５＋ｙ６ｘ６＋ｙ５ｘ７＋ｙ４ｘ８
このように、Ｚ［２］は、Ｘ［８：０］の各ビット、Ｙ［８：０］の各ビットを用いて下記の様に表される。
Ｚ［３］＝ｙ３ｘ０＋ｙ２ｘ１＋ｙ１ｘ２＋ｙ０ｘ３＋ｙ８ｘ４＋ｙ７ｘ５＋ｙ６ｘ６＋ｙ５ｘ７＋ｙ４ｘ８
【００７２】
次に、Ｚ［８：０］のうちＺ［４］は、Ｚ［４］＝ａ４＋ａ９＋ａ１３＋a１４と表されるが（図２参照）、これを、Ｘ［８：０］、及びＹ［８：０］の成分（要素）を用い、更にＸ［８：０］の成分毎に、すなわちｘ０〜ｘ８毎にまとめると、Ｚ［４］は以下の様に表される。
Ｚ［４］＝ｙ４ｘ０＋（ｙ３＋ｙ８）ｘ１＋（ｙ２＋ｙ７）ｘ２＋（ｙ１＋ｙ６）ｘ３＋（ｙ０＋ｙ５）ｘ４＋（ｙ４＋ｙ８）ｘ５＋（ｙ３＋ｙ７＋ｙ８）ｘ６＋（ｙ２＋ｙ６＋ｙ７）ｘ７＋（ｙ１＋ｙ５＋ｙ６）ｘ８
ここで、上述のZ［０］と同様に、ｙ３＋ｙ８＝ｐ０、ｙ２＋ｙ７＝ｐ１、ｙ１＋ｙ６＝ｐ２とし、また、ｙ０＋ｙ５＝ｐ３、ｙ４＋ｙ８＝ｐ４、ｙ３＋ｙ７＋ｙ８＝ｐ５、ｙ２＋ｙ６＋ｙ７＝ｐ６、ｙ１＋ｙ５＋ｙ６＝ｐ７とすれば、Ｚ［４］は、更に、Ｘ［８：０］の各ビット、Ｙ［８：０］の各ビット、Ｙ［８：０］のビットの組合せを用いて下記の様に表される。
Ｚ［４］＝ｙ４ｘ０＋ｐ０ｘ１＋ｐ１ｘ２＋ｐ２ｘ３＋ｐ３ｘ４＋ｐ４ｘ５＋ｐ５ｘ６＋ｐ６ｘ７＋ｐ７ｘ８
【００７３】
次に、Ｚ［８：０］のうちＺ［５］は、Ｚ［５］＝ａ５＋ａ１０＋ａ１４＋a１５と表されるが（図２参照）、これを、Ｘ［８：０］、及びＹ［８：０］の成分（要素）を用い、更にＸ［８：０］の成分毎に、すなわちｘ０〜ｘ８毎にまとめると、Ｚ［５］は以下の様に表される。
Ｚ［５］＝ｙ５ｘ０＋ｙ４ｘ１＋（ｙ３＋ｙ８）ｘ２＋（ｙ２＋ｙ７）ｘ３＋（ｙ１＋ｙ６）ｘ４＋（ｙ０＋ｙ５）ｘ５＋（ｙ４＋ｙ８）ｘ６＋（ｙ３＋ｙ７＋ｙ８）ｘ７＋（ｙ２＋ｙ６＋ｙ７）ｘ８
ここで、上述のZ［４］と同様に、ｙ３＋ｙ８＝ｐ０、ｙ２＋ｙ７＝ｐ１、ｙ１＋ｙ６＝ｐ２、ｙ０＋ｙ５＝ｐ３、ｙ４＋ｙ８＝ｐ４、ｙ３＋ｙ７＋ｙ８＝ｐ５、ｙ２＋ｙ６＋ｙ７＝ｐ６とすれば、Ｚ［５］は、更に、Ｘ［８：０］の各ビット、Ｙ［８：０］の各ビット、Ｙ［８：０］のビットの組合せを用いて下記の様に表される。
Ｚ［５］＝ｙ５ｘ０＋ｙ４ｘ１＋ｐ０ｘ２＋ｐ１ｘ３＋ｐ２ｘ４＋ｐ３ｘ５＋ｐ４ｘ６＋ｐ５ｘ７＋ｐ６ｘ８
【００７４】
次に、Ｚ［８：０］のうちＺ［６］は、Ｚ［６］＝ａ６＋ａ１１＋ａ１５＋a１６と表されるが（図２参照）、これを、Ｘ［８：０］、及びＹ［８：０］の成分（要素）を用い、更にＸ［８：０］の成分毎に、すなわちｘ０〜ｘ８毎にまとめると、Ｚ［６］は以下の様に表される。
Ｚ［６］＝ｙ６ｘ０＋ｙ５ｘ１＋ｙ４ｘ２＋（ｙ３＋ｙ８）ｘ３＋（ｙ２＋ｙ７）ｘ４＋（ｙ１＋ｙ６）ｘ５＋（ｙ０＋ｙ５）ｘ６＋（ｙ４＋ｙ８）ｘ７＋（ｙ３＋ｙ７＋ｙ８）ｘ８
ここで、上述のＺ［４］、Z［５］と同様に、ｙ３＋ｙ８＝ｐ０、ｙ２＋ｙ７＝ｐ１、ｙ１＋ｙ６＝ｐ２、ｙ０＋ｙ５＝ｐ３、ｙ４＋ｙ８＝ｐ４、ｙ３＋ｙ７＋ｙ８＝ｐ５とすれば、Ｚ［６］は、更に、Ｘ［８：０］の各ビット、Ｙ［８：０］の各ビット、Ｙ［８：０］のビットの組合せを用いて下記の様に表される。
Ｚ［６］＝ｙ６ｘ０＋ｙ５ｘ１＋ｙ４ｘ２＋ｐ０ｘ３＋ｐ１ｘ４＋ｐ２ｘ５＋ｐ３ｘ６＋ｐ４ｘ７＋ｐ５ｘ８
【００７５】
次に、Ｚ［８：０］のうちＺ［７］は、Ｚ［７］＝ａ７＋ａ１２＋a１６と表されるが（図２参照）、これを、Ｘ［８：０］、及びＹ［８：０］の成分（要素）を用い、更にＸ［８：０］の成分毎に、すなわちｘ０〜ｘ８毎にまとめると、Ｚ［７］は以下の様に表される。
Ｚ［７］＝ｙ７ｘ０＋ｙ６ｘ１＋ｙ５ｘ２＋ｙ４ｘ３＋（ｙ３＋ｙ８）ｘ４＋（ｙ２＋ｙ７）ｘ５＋（ｙ１＋ｙ６）ｘ６＋（ｙ０＋ｙ５）ｘ７＋（ｙ４＋ｙ８）ｘ８
ここで、上述のＺ［４］、Z［５］、Ｚ［６］と同様に、ｙ３＋ｙ８＝ｐ０、ｙ２＋ｙ７＝ｐ１、ｙ１＋ｙ６＝ｐ２、ｙ０＋ｙ５＝ｐ３、ｙ４＋ｙ８＝ｐ４とすれば、Ｚ［７］は、更に、Ｘ［８：０］の各ビット、Ｙ［８：０］の各ビット、Ｙ［８：０］のビットの組合せを用いて下記の様に表される。
Ｚ［７］＝ｙ７ｘ０＋ｙ６ｘ１＋ｙ５ｘ２＋ｙ４ｘ３＋ｐ０ｘ４＋ｐ１ｘ５＋ｐ２ｘ６＋ｐ３ｘ７＋ｐ４ｘ８
【００７６】
次に、Ｚ［８：０］のうちＺ［８］は、Ｚ［８］＝ａ８＋ａ１３と表されるが（図２参照）、これを、Ｘ［８：０］、及びＹ［８：０］の成分（要素）を用い、更にＸ［８：０］の成分毎に、すなわちｘ０〜ｘ８毎にまとめると、Ｚ［８］は以下の様に表される。
Ｚ［８］＝ｙ８ｘ０＋ｙ７ｘ１＋ｙ６ｘ２＋ｙ５ｘ３＋ｙ４ｘ４＋（ｙ３＋ｙ８）ｘ５＋（ｙ２＋ｙ７）ｘ６＋（ｙ１＋ｙ６）ｘ７＋（ｙ０＋ｙ５）ｘ８
ここで、上述のＺ［４］、Z［５］、Ｚ［６］、Ｚ［７］と同様に、ｙ３＋ｙ８＝ｐ０、ｙ２＋ｙ７＝ｐ１、ｙ１＋ｙ６＝ｐ２、ｙ０＋ｙ５＝ｐ３とすれば、Ｚ［８］は、更に、Ｘ［８：０］の各ビット、Ｙ［８：０］の各ビット、Ｙ［８：０］のビットの組合せを用いて下記の様に表される。
Ｚ［８］＝ｙ８ｘ０＋ｙ７ｘ１＋ｙ６ｘ２＋ｙ５ｘ３＋ｙ４ｘ４＋ｐ０ｘ５＋ｐ１ｘ６＋ｐ２ｘ７＋ｐ３ｘ８
【００７７】
このように、Ｙ［８：０］（他方の元）のビットのうちＸ［８：０］（一方の元）のビットを同一とするビットＹ［８］〜Ｙ［０］を排他的論理和演算してＹ［８：０］の各ビットの組み合わせを求める。
これにより、Ｚ［８：０］のうちの各ビットＺ［０］〜Ｚ［８］は、２つの元のうちＸ［８：０］（一方の元）の各ビットと、Ｙ［８：０］（他方の元）の各ビットとまたは各ビットの組み合わせとの論理積演算を行い、この論理積演算の演算結果を排他的論理和演算することにより得られることになる。この演算の乗算方法をまとめた図が、図９、及び図１０である。図９は、Ｘ［８：０］とＹ［８：０］との乗算によりＺ［８：０］を出力するときの条件を示した図である。また、図１０は、ｙ［０］〜ｙ［８］の組合せから、ｐ［０］〜ｐ［８］を求める際の論理式である。
図９に示すように、Ｚ［８：０］のうちの各ビットは、Ｘ［８：０］の各ビットｘ［０］〜ｘ［８］と、Ｙ［８：０］の各ビットｙ［０］〜ｙ［８］またはｐ［０］〜ｐ［８］（ｙ［０］〜ｙ［８］の組合せ）により求めることができる。つまり、Ｘ［８：０］とＹ［８：０］との乗算によりＺ［８：０］を出力するＺ［８：０］を演算する回路の入力信号のうち、一方の元（Ｘ［８：０］）の入力はＸ［８：０］の９ビットになる。また、他方の元（Ｙ［８：０］）の入力信号は、Ｙ［８：０］の９ビットのうちの複数ビットと、９ビットのうちいくつかを組合せた複数ビットとの併せて９ビットになる。これにより、２つの元を入力する際のビット数を等しくできるため、ガロア体乗算回路における出力信号Ｚ［８：０］の各ビットに対応した９つの要素演算部の入力回路（論理積演算部）を、全て同一構成の回路構成（ナンド回路）とすることが出来る。また、９つの要素演算部において、それぞれの論理積回路の出力信号の和を演算する８（＝９−１）個の回路（論理演算部の演算結果を排他的論理和演算する加算部）を、全て同一構成の回路構成（ＥＸＯＲ回路またはＥＸＮＯＲ回路）とすることができる。すなわち、ガロア体乗算回路における出力信号の各ビットに対応した９個の要素演算部を全て同一の回路構成とすることができる。
【００７８】
図１１は、ガロア体乗算回路における要素演算部１０の回路構成を示す図である。ガロア体乗算回路は、この要素演算部１０を、乗算するビット数（ここでは９ビット）と同じ個数、すなわち本実施形態の場合は９個備える。以下では、Ｚ［０］を演算する場合について、要素演算部１０の回路構成を説明する。なお、図９に示すＸ［０］などを、図１０ではＸ〈０〉などで示している。また、以下では、出力信号ｘ０ｙ０などの論理反転信号を、符号Ｂを用いてＢ（ｘ０ｙ０）と表すものとする。
要素演算部１０は、論理積演算部１１と加算部１２とから構成される。論理積演算部１１は、９個の否定論理積回路（ナンド回路）から構成される。９個のナンド回路は、ナンド回路１１＿０、ナンド回路１１＿１、ナンド回路１１＿２、ナンド回路１１＿３、ナンド回路１１＿４、ナンド回路１１＿５、ナンド回路１１＿６、ナンド回路１１＿７、ナンド回路１１＿８である。
【００７９】
ナンド回路１１＿０は、第１入力にＸ［８：０］のうちの１ビットＸ［０］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［０］が入力され、入力される２信号の否定論理積演算を行い、Ｂ（ｘ０ｙ０）を出力する。
ナンド回路１１＿１は、第１入力にＸ［８：０］のうちの１ビットＸ［１］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［８］が入力され、入力される２信号の否定論理積演算を行い、Ｂ（ｘ１ｙ８）を出力する。
ナンド回路１１＿２は、第１入力にＸ［８：０］のうちの１ビットＸ［２］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［７］が入力され、入力される２信号の否定論理積演算を行い、Ｂ（ｘ２ｙ７）を出力する。
ナンド回路１１＿３は、第１入力にＸ［８：０］のうちの１ビットＸ［３］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［６］が入力され、入力される２信号の否定論理積演算を行い、Ｂ（ｘ３ｙ６）を出力する。
ナンド回路１１＿４は、第１入力にＸ［８：０］のうちの１ビットＸ［４］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［５］が入力され、入力される２信号の否定論理積演算を行い、Ｂ（ｘ４ｙ５）を出力する。
ナンド回路１１＿５は、第１入力にＸ［８：０］のうちの１ビットＸ［５］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［４］が入力され、入力される２信号の否定論理積演算を行い、Ｂ（ｘ５ｙ４）を出力する。
ナンド回路１１＿６は、第１入力にＸ［８：０］のうちの１ビットＸ［６］が入力され、第２入力にＹ［８：０］のうちのビットＹ［３］、及びビットＹ［８］の組み合わせであるｐ［０］が入力され、入力される２信号の否定論理積演算を行い、Ｂ（ｘ６ｐ０）を出力する。
ナンド回路１１＿７は、第１入力にＸ［８：０］のうちの１ビットＸ［７］が入力され、第２入力にＹ［８：０］のうちのビットＹ［２］、及びビットＹ［７］の組み合わせであるｐ［１］が入力され、入力される２信号の否定論理積演算を行い、Ｂ（ｘ７ｐ１）を出力する。
ナンド回路１１＿８は、第１入力にＸ［８：０］のうちの１ビットＸ［８］が入力され、第２入力にＹ［８：０］のうちのビットＹ［１］、及びビットＹ［６］の組み合わせであるｐ［２］が入力され、入力される２信号の否定論理積演算を行い、Ｂ（ｘ８ｐ２）を出力する。
【００８０】
加算部１２は、５個の否定排他的論理和回路（Ｅｘｃｌｕｓｉｖｅ−Ｎｏｒ；ＥＸＮＯＲ回路）と３個のＥＸＯＲ回路から構成される。５個のＥＸＮＯＲ回路は、ＥＸＮＯＲ回路１２＿１、ＥＸＮＯＲ回路１２＿２、ＥＸＮＯＲ回路１２＿３、ＥＸＮＯＲ回路１２＿４、ＥＸＮＯＲ回路１２＿５である。また、３個のＥＸＯＲ回路は、ＥＸＯＲ回路１２＿６、ＥＸＯＲ回路１２＿７、ＥＸＯＲ回路１２＿８である。
ＥＸＮＯＲ回路１２＿１は、ナンド回路１１＿１の出力信号であるＢ（ｘ１ｙ８）と、ナンド回路１１＿２の出力信号であるＢ（ｘ２ｙ７）との否定排他的論理和演算を行い、（ｘ１ｙ８＋ｘ２ｙ７）を出力する。
ＥＸＮＯＲ回路１２＿２は、ナンド回路１１＿３の出力信号であるＢ（ｘ３ｙ６）と、ナンド回路１１＿４の出力信号であるＢ（ｘ４ｙ５）との否定排他的論理和演算を行い、（ｘ３ｙ６＋ｘ４ｙ５）を出力する。
ＥＸＮＯＲ回路１２＿３は、ナンド回路１１＿５の出力信号であるＢ（ｘ５ｙ４）と、ナンド回路１１＿６の出力信号であるＢ（ｘ６ｐ０）との否定排他的論理和演算を行い、（ｘ５ｙ４＋ｘ６ｐ０）を出力する。
ＥＸＮＯＲ回路１２＿４は、ナンド回路１１＿７の出力信号であるＢ（ｘ７ｐ１）と、ナンド回路１１＿８の出力信号であるＢ（ｘ８ｐ２）との否定排他的論理和演算を行い、（ｘ７ｐ１＋ｘ８ｐ２）を出力する。
【００８１】
ＥＸＯＲ回路１２＿６は、ＥＸＮＯＲ回路１２＿１の出力信号である（ｘ１ｙ８＋ｘ２ｙ７）と、ＥＸＮＯＲ回路１２＿２の出力信号である（ｘ３ｙ６＋ｘ４ｙ５）との排他的論理和演算を行い、（ｘ１ｙ８＋ｘ２ｙ７＋ｘ３ｙ６＋ｘ４ｙ５）を出力する。
ＥＸＯＲ回路１２＿７は、ＥＸＮＯＲ回路１２＿３の出力信号である（ｘ５ｙ４＋ｘ６ｐ０）と、ＥＸＮＯＲ回路１２＿４の出力信号である（ｘ７ｐ１＋ｘ８ｐ２）との排他的論理和演算を行い、（ｘ５ｙ４＋ｘ６ｐ０＋ｘ７ｐ１＋ｘ８ｐ２）を出力する。
ＥＸＮＯＲ回路１２＿５は、ＥＸＯＲ回路１２＿６の出力信号である（ｘ１ｙ８＋ｘ２ｙ７＋ｘ３ｙ６＋ｘ４ｙ５）と、ＥＸＯＲ回路１２＿７の出力信号である（ｘ５ｙ４＋ｘ６ｐ０＋ｘ７ｐ１＋ｘ８ｐ２）との否定排他的論理和演算を行い、Ｂ（ｘ１ｙ８＋ｘ２ｙ７＋ｘ３ｙ６＋ｘ４ｙ５＋ｘ５ｙ４＋ｘ６ｐ０＋ｘ７ｐ１＋ｘ８ｐ２）を出力する。
ＥＸＯＲ回路１２＿８は、ＥＸＮＯＲ回路１２＿５の出力信号であるＢ（ｘ１ｙ８＋ｘ２ｙ７＋ｘ３ｙ６＋ｘ４ｙ５＋ｘ５ｙ４＋ｘ６ｐ０＋ｘ７ｐ１＋ｘ８ｐ２）と、ナンド回路１１＿０の出力信号であるＢ（ｘ０ｙ０）との排他的論理和演算を行い、Ｚ［０］（＝ｘ０ｙ０＋ｘ１ｙ８＋ｘ２ｙ７＋ｘ３ｙ６＋ｘ４ｙ５＋ｘ５ｙ４＋ｘ６ｐ０＋ｘ７ｐ１＋ｘ８ｐ２）を出力する（図９参照）。
【００８２】
他のＺ［１］〜Ｚ［８］を演算する要素演算部１０についても、上述した要素演算部１０と同様に、論理積演算部１１において、図９に示すＸ［８：０］のうちの１ビットと、Ｙ［８：０］の９ビットのちのビット、または９ビットのうちのビットを組合せたビットとの併せて９ビットのうちの１ビットとの論理積演算を行う。また、加算部１２において、論理積演算の結果について排他的論理和演算を行い、それぞれ図９に示すＺ［１］〜Ｚ［８］を演算する。
【００８３】
このように、本発明のガロア体乗算回路は、ガロア体ＧＦ（２ｍ）上（ｍは整数、以下同じ）のｍビットによりベクトル表現される２つの元の乗算を行なうガロア体乗算回路であって、乗算の積の要素を演算する要素演算部（要素演算部１０）が、２つの元のうち一方の元（Ｘ［８：０］）の各ビットと、２つの元のうち他方の元（Ｙ［８：０］）の各ビットとまたは各ビットの組み合わせ（Ｐ［８：０］）との論理積演算を並列に行うｍ個の論理積演算部（論理積演算部１１）と、ｍ個の論理積演算部の演算結果を排他的論理和演算する加算部（加算部１２）と、を有する。
【００８４】
本発明のガロア体乗算回路によれば、２つの元のうち他方の元の各ビットの組み合わせの個数を要素演算部毎に変えることにより、ガロア体乗算回路に入力する他方の元の各ビットとまたは各ビットの組み合わせとのビット数と、２つの元のうち一方の元のビット数とを同じにすることができる。従って、ガロア体乗算回路における論理積演算を並列に行う入力回路（論理積演算部）を、全て同一構成の回路であるｍ個の論理ゲート（ナンド回路）にできる。また、ｍ個の論理演算部の演算結果を排他的論理和演算する加算部を、全て同一構成である（ｍ−１）個の論理ゲート（ＥＸＯＲまたはＥＸＮＯＲ）にできる。すなわち、要素演算部毎に論理ゲートの個数を同一とし、また入力信号の本数を同一とできる。また、内部ノードの個数も同一とできる。これにより、規則性のある回路構成で実現できるガロア体乗算回路を提供することができる。よって、ガロア体乗算回路を、例えば半導体装置上に構築する場合に、面積効率を上げて効率よく配置することが容易になる。また、入力信号の本数を要素演算部に同じ本数にできるため、入力信号の配線レイアウトを簡易に行うことができ、例えば自動配線ツールを用いる設計を容易にし、設計効率の低下を抑制することができる。
【００８５】
なお、各要素演算部１０に入力される他方の元のビットの組合せ（ｐ０〜ｐ７）は、それぞれ複数のＥＸＯＲ回路により生成される。
図１２は、ｐ生成回路２０の回路構成を示す図である。
ｐ生成回路２０は、ＥＸＯＲ回路２０＿０、ＥＸＯＲ回路２０＿１、ＥＸＯＲ回路２０＿２、ＥＸＯＲ回路２０＿３、ＥＸＯＲ回路２０＿４、ＥＸＯＲ回路２０＿５１、ＥＸＯＲ回路２０＿５２、ＥＸＯＲ回路２０＿６１、ＥＸＯＲ回路２０＿６２、ＥＸＯＲ回路２０＿７１、ＥＸＯＲ回路２０＿７２から構成される。
【００８６】
ＥＸＯＲ回路２０＿０は、第１入力にＹ［８：０］のうちの１ビットＹ［３］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［８］が入力され、入力される２信号の排他的論理和演算を行い、ｐ０（＝ｙ３＋ｙ８）を出力する。
ＥＸＯＲ回路２０＿１は、第１入力にＹ［８：０］のうちの１ビットＹ［２］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［７］が入力され、入力される２信号の排他的論理和演算を行い、ｐ１（＝ｙ２＋ｙ７）を出力する。
ＥＸＯＲ回路２０＿２は、第１入力にＹ［８：０］のうちの１ビットＹ［１］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［６］が入力され、入力される２信号の排他的論理和演算を行い、ｐ３（＝ｙ１＋ｙ６）を出力する。
ＥＸＯＲ回路２０＿３は、第１入力にＹ［８：０］のうちの１ビットＹ［０］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［５］が入力され、入力される２信号の排他的論理和演算を行い、ｐ４（＝ｙ０＋ｙ５）を出力する。
ＥＸＯＲ回路２０＿４は、第１入力にＹ［８：０］のうちの１ビットＹ［４］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［８］が入力され、入力される２信号の排他的論理和演算を行い、ｐ５（＝ｙ４＋ｙ８）を出力する。
【００８７】
ＥＸＯＲ回路２０＿５１は、第１入力にＹ［８：０］のうちの１ビットＹ［３］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［７］が入力され、入力される２信号の排他的論理和演算を行い、（ｙ３＋ｙ７）を出力する。
ＥＸＯＲ回路２０＿５２は、第１入力にＥＸＯＲ回路２０＿５１の出力信号である（ｙ３＋ｙ７）が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［８］が入力され、入力される２信号の排他的論理和演算を行い、ｐ５（＝ｙ３＋ｙ７＋ｙ８）を出力する。
ＥＸＯＲ回路２０＿６１は、第１入力にＹ［８：０］のうちの１ビットＹ［２］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［６］が入力され、入力される２信号の排他的論理和演算を行い、（ｙ２＋ｙ６）を出力する。
ＥＸＯＲ回路２０＿６２は、第１入力にＥＸＯＲ回路２０＿６１の出力信号である（ｙ２＋ｙ６）が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［７］が入力され、入力される２信号の排他的論理和演算を行い、ｐ６（＝ｙ２＋ｙ６＋ｙ７）を出力する。
ＥＸＯＲ回路２０＿７１は、第１入力にＹ［８：０］のうちの１ビットＹ［１］が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［５］が入力され、入力される２信号の排他的論理和演算を行い、（ｙ１＋ｙ５）を出力する。
ＥＸＯＲ回路２０＿７２は、第１入力にＥＸＯＲ回路２０＿７１の出力信号である（ｙ１＋ｙ５）が入力され、第２入力にＹ［８：０］のうちの１ビットＹ［６］が入力され、入力される２信号の排他的論理和演算を行い、ｐ７（＝ｙ１＋ｙ５＋ｙ６）を出力する。
【００８８】
［第２の実施形態］
第２の実施形態では、上述した各要素演算部１０とｐ生成回路２０とから構成されるガロア体乗算回路について図１３を参照して説明する。
図１３は、ガロア体乗算回路１００のブロック構成を示す図である。
図１３に示すように、ガロア体乗算回路１００は、９個の要素演算部（要素演算部１０＿０、要素演算部１０＿１、要素演算部１０＿２、要素演算部１０＿３、要素演算部１０＿４、要素演算部１０＿５、要素演算部１０＿６、要素演算部１０＿７、要素演算部１０＿８）と、ｐ生成回路２０とから構成される。
要素演算部１０＿ｉ（ｉ＝０〜８）は、図１１に示す要素演算部１０であり、それぞれ図９に示すＸ［８：０］とＹ［８：０］またはＰ［８：０］が入力され、Ｚ［０］〜Ｘ［８］を出力する。ｐ生成回路２０（組合せ回路）は、図１２に示す回路構成を有する回路であり、Ｙ［８：０］からＰ［８：０］を生成する回路である。
図１３に示すように、要素演算部１０＿０〜要素演算部１０＿８、ｐ生成回路２０が同一方向に配列されて、ガロア体乗算回路１００が構成される。また、ガロア体乗算回路１００には、入力信号として一方の元（Ｘ［８：０］）と、他方の元（Ｙ［８：０］）とがそれぞれ外部から入力される。Ｘ［８：０］はそれぞれ９本の信号配線（第１配線）を介して、また、Ｙ［８：０］はそれぞれ９本の信号配線（第２配線）を介して各要素演算部に供給される。また、入力信号のうちＹ［８：０］を伝送する９本の信号配線はｐ生成回路２０に接続され、ｐ生成回路２０には、Ｙ［８：０］が供給され、Ｐ［８：０］を生成する。ｐ生成回路２０は、このＰ［８：０］を９本の信号配線（第３配線）を介して、各要素演算部に供給する。各要素演算部は、Ｘ［８：０］、Ｙ［８：０］、Ｐ［８：０］からＺ［８：０］を生成する。
本実施形態では、入力信号、出力信号、Ｐ信号を伝送する配線を、一方向に並行にレイアウトすることができ、配線の引き回しを減らして、ガロア体乗算回路を構成することができる。例えば、半導体装置上にガロア体乗算回路を搭載する場合、製造プロセスのテクノロジー・ノード（製造技術の世代）にもよるが、かかる構成を有しないガロア体乗算回路に比べて、約５０％程度にまで面積の縮小化を図ることができる。
【００８９】
以上、この発明の実施形態を、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００９０】
１００…ガロア体乗算回路、１０，１０＿０，１０＿１，１０＿２，１０＿３，１０＿４，１０＿５，１０＿６，１０＿７，１０＿８，３０，３１，３２，３３，３４，３５，３６，３７，３８…要素演算部、１１…論理積演算部、１１＿０，１１＿１，１１＿２，１１＿３，１１＿４，１１＿５，１１＿６，１１＿７，１１＿８…ナンド回路、１２…加算部、１２＿１，１２＿２，１２＿３，１２＿４，１２＿５…ＥＸＮＯＲ回路、１２＿６，１２＿６，１２＿８，２０＿０，２０＿１，２０＿２，２０＿３，２０＿４，２０＿５１，２０＿５２，２０＿６１，２０＿６２，２０＿７１，２０＿７２，３０１＿１１，３０２＿１１，３０２＿１２，３０３＿１１，３０３＿１２，３０３＿１３，３０４＿１１，３０４＿１２，３０４＿１３，３０４＿１４，３０５＿１１，３０５＿１２，３０５＿１３，３０５＿１４，３０５＿１５，３０６＿１１，３０６＿１２，３０６＿１３，３０６＿１４，３０６＿１５，３０６＿１６，３０７＿１１，３０７＿１２，３０７＿１３，３０７＿１４，３０７＿１５，３０７＿１６，３０７＿１７，３０８＿１１，３０８＿１２，３０８＿１３，３０８＿１４，３０８＿１５，３０８＿１６，３０８＿１７，３０８＿１８，３０９＿１１，３０９＿１２，３０９＿１３，３０９＿１４，３０９＿１５，３０９＿１６，３０９＿１７，３１０＿１１，３１０＿１２，３１０＿１３，３１０＿１４，３１０＿１５，３１０＿１６，３１１＿１１，３１１＿１２，３１１＿１３，３１１＿１４，３１１＿１５，３１２＿１１，３１２＿１２，３１２＿１３，３１２＿１４，３１３＿１１，３１３＿１２，３１３＿１３，３１４＿１１，３１４＿１２，３１５＿１１，４００＿１，４００＿２，４０１＿１，４０１＿２，４０２＿１，４０２＿２，４０３＿１，４０４＿１，４０４＿２，４０４＿３，４０５＿１，４０５＿２，４０５＿３，４０６＿１，４０６＿２，４０６＿３，４０７＿１，４０７＿２，４０８＿１…ＥＸＯＲ回路、２０…ｐ生成回路、３００…ａ０演算部，３０１…ａ１演算部，３０２…ａ２演算部，３０３…ａ３演算部，３０４…ａ４演算部，３０５…ａ５演算部，３０６…ａ６演算部，３０７…ａ７演算部，３０８…ａ８演算部，３０９…ａ９演算部，３１０…ａ１０演算部，３１１…ａ１１演算部，３１２…ａ１２演算部，３１３…ａ１３演算部，３１４…ａ１４演算部，３１５…ａ１５演算部，３１６…ａ１６演算部、４００…Ｚ［０］演算部，４０１…Ｚ［１］演算部，４０２…Ｚ［２］演算部，４０３…Ｚ［３］演算部，４０４…Ｚ［４］演算部，４０５…Ｚ［５］演算部，４０６…Ｚ［６］演算部，４０７…Ｚ［７］演算部，４０８…Ｚ［８］演算部、３００＿１，３０１＿１，３０１＿２，３０２＿１，３０２＿２，３０２＿３，３０３＿１，３０３＿２，３０３＿３，３０３＿４，３０４＿１，３０４＿２，３０４＿３，３０４＿４，３０４＿５，３０５＿１，３０５＿２，３０５＿３，３０５＿４，３０５＿５，３０５＿６，３０６＿１，３０６＿２，３０６＿３，３０６＿４，３０６＿５，３０６＿６，３０６＿７，３０７＿１，３０７＿２，３０７＿３，３０７＿４，３０７＿５，３０７＿６，３０７＿７，３０７＿８，３０８＿１，３０８＿２，３０８＿３，３０８＿４，３０８＿５，３０８＿６，３０８＿７，３０８＿８，３０８＿９，３０９＿１，３０９＿２，３０９＿３，３０９＿４，３０９＿５，３０９＿６，３０９＿７，３０９＿８，３１０＿１，３１０＿２，３１０＿３，３１０＿４，３１０＿５，３１０＿６，３１０＿７，３１１＿１，３１１＿２，３１１＿３，３１１＿４，３１１＿５，３１１＿６，３１２＿１，３１２＿２，３１２＿３，３１２＿４，３１２＿５，３１３＿１，３１３＿２，３１３＿３，３１３＿４，３１４＿１，３１４＿２，３１４＿３，３１５＿１，３１５＿２，３１６＿１
【図１】
2014082575.tif 000003
【図２】
2014082575.tif 000004
【図３】
2014082575.tif 000005
【図４】
2014082575.tif 000006
【図５】
2014082575.tif 000007
【図６】
2014082575.tif 000008
【図７】
2014082575.tif 000009
【図８】
2014082575.tif 000010
【図９】
2014082575.tif 000011
【図１０】
2014082575.tif 000012
【図１１】
2014082575.tif 000013
【図１２】
2014082575.tif 000014
【図１３】
2014082575.tif 000015