(57)【要約】【課題】ガロア拡大体における乗算を小さな回路規模で実現する。【解決手段】乗数に基づいて設定される行列を構成する複数のベクトルの要素Ｔ４１が、積和単位４０１のアンドゲート４１の一方の入力となる。同様に要素Ｔ４２，Ｔ４３，Ｔ４４が、それぞれ積和単位４０２，４０３，４０４のアンドゲート４１の一方の入力となる。いずれの積和単位４０１〜４０４においても、被乗数の１ビットがアンドゲート４１の他方の入力となる。アンドゲート４１の出力がＸＯＲゲート４２の一方の入力に与えられる。レジスタ４３の出力がＸＯＲゲート４２の他方の入力に与えられる。ＸＯＲゲート４２の出力はレジスタ４３に入力する。【選択図】　　　　図３
2004054384.tif 000002
【特許請求の範囲】
【請求項１】
入力端と、前記入力端に与えられた信号を少なくとも一つの単位時間だけ遅延して出力する出力端とを有する遅延器と、
第１端及び第２端、並びに自身の前記第１端及び前記第２端に入力する信号の二値論理についての論理積を出力する出力端を有する第１ゲートと、
前記第１ゲートの出力を入力する第１端と、前記遅延器の出力端に接続された第２端と、並びに自身の前記第１端及び前記第２端に入力する信号の二値論理についての排他的論理和を前記遅延器の前記入力端に出力する出力端とを有する第２ゲートと
を備える積和単位を、少なくとも一つ含む演算器。
【請求項２】
乗数に基づいて設定される行列を構成する複数のベクトルが順次出力される乗数提供部と、
被乗数を１ビットずつ出力する被乗数提供部と
を更に備え、
前記積和単位は前記ベクトルの要素毎に複数設けられて、各々の前記積和単位が自身に対応する前記要素を前記第１ゲートの前記第１端に入力され、
いずれの前記積和単位も、自身の前記第１ゲートの前記第２端には前記被乗数の前記１ビットが入力され、
前記遅延器は一つの単位時間だけ、自身の前記入力端に与えられた信号を遅延させる、請求項１記載の演算器。
【請求項３】
乗数に基づいて設定される行列を構成する複数のベクトルが、要素毎に順次出力される乗数提供部と、
被乗数を１ビットずつ出力する被乗数提供部と
を更に備え、
前記積和単位の前記第１ゲートの前記第１端には前記要素が入力され、
前記積和単位の前記第１ゲートの前記第２端には前記被乗数の前記１ビットが入力され、
前記遅延器は前記ベクトルを構成する要素の数と前記単位時間との積で、自身の前記入力端に与えられた信号を遅延させる、請求項１記載の演算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は演算器に関し、例えばガロア拡大体における乗算に適する。
【０００２】
【従来の技術】
近年、あらゆる分野においてデジタル化、ＩＴ化が進み、デジタルデータ記録や通信に対して注目が集まっている。この、デジタルデータ記録方式や通信方式における誤り訂正方法として、リードソロモン符号やＢＣＨ符号などがよく利用されている。これらの符号はガロア拡大体の性質を利用して作られており、その扱いにはガロア拡大体における演算が必須となる。特にガロア体ＧＦ（２）からガロア拡大体ＧＦ（２ｍ）を得る際に採用されるｍ次の原始既約多項式の根をαとすると、ガロア拡大体における乗算ではａ＝αｉと、ｂ＝αｊとの乗算が必要となる。
【０００３】
図１４は、ガロア拡大体における乗算を行う従来の乗算器の構成を示すブロック図である。被乗数ａ及び乗数ｂはそれぞれ対数変換ブロック１０１，１０２に入力し、各々で指数ｉ，ｊが求められる。指数ｉ，ｊは加算ブロック１０３に与えられ、ここにおいて指数ｉ，ｊの和の（ｑ−１）を法とする剰余として指数ｋが得られる（但し体の位数２ｍをｑとする）。その後指数ｋは逆対数変換ブロック１０４に与えられ、積ｃがαｋとして求められる。
【０００４】
【発明が解決しようとする課題】
上記の乗算器では、対数変換、逆対数変換の際、いずれも変換表を使うのが一般的であった。しかし、リードソロモン符号の符号器に採用される乗算器では、符号を構成するための生成多項式は唯一に決定されて乗数は一定であることが多い。従って、上述の変換表を用いた乗算器をリードソロモン符号の符号器に採用すると、異なる複数の乗数に対応するという不要な機能を果たすので、回路規模が冗長であるという問題点があった。
【０００５】
この発明は上記問題点を解決するためになされたもので、ガロア拡大体における乗算を小さな回路規模で実現する技術を提供することを目的としている。
【０００６】
【課題を解決するための手段】
この発明のうち請求項１にかかるものは演算器であって、入力端と、前記入力端に与えられた信号を少なくとも一つの単位時間だけ遅延して出力する出力端とを有する遅延器と、第１端及び第２端、並びに自身の前記第１端及び前記第２端に入力する信号の二値論理についての論理積を出力する出力端を有する第１ゲートと、前記第１ゲートの出力を入力する第１端と、前記遅延器の出力端に接続された第２端と、並びに自身の前記第１端及び前記第２端に入力する信号の二値論理についての排他的論理和を前記遅延器の前記入力端に出力する出力端とを有する第２ゲートとを備える積和単位を、少なくとも一つ含む。
【０００７】
この発明のうち請求項２にかかるものは、請求項１記載の演算器であって、乗数に基づいて設定される行列を構成する複数のベクトルが順次出力される乗数提供部と、被乗数を１ビットずつ出力する被乗数提供部とを更に備える。そして前記積和単位は前記ベクトルの要素毎に複数設けられて、各々の前記積和単位が自身に対応する前記要素を前記第１ゲートの前記第１端に入力され、いずれの前記積和単位も、自身の前記第１ゲートの前記第２端には前記被乗数の前記１ビットが入力され、前記遅延器は一つの単位時間だけ、自身の前記入力端に与えられた信号を遅延させる。
【０００８】
この発明のうち請求項３にかかるものは、請求項１記載の演算器であって、乗数に基づいて設定される行列を構成する複数のベクトルが、要素毎に順次出力される乗数提供部と、被乗数を１ビットずつ出力する被乗数提供部とを更に備える。そして、前記積和単位の前記第１ゲートの前記第１端には前記要素が入力され、前記積和単位の前記第１ゲートの前記第２端には前記被乗数の前記１ビットが入力され、前記遅延器は前記ベクトルを構成する要素の数と前記単位時間との積で、自身の前記入力端に与えられた信号を遅延させる。
【０００９】
【発明の実施の形態】
実施の形態１．
図１は本発明にかかる乗算器が適用可能な符号器１の構造を示すブロック図であり、（８，４）リードソロモン符号器として公知である。ここでは既約原始多項式及び生成多項式としてそれぞれ式（１），（２）を採用した場合を例示する。
【００１０】
【数１】
2004054384.tif 000003
【００１１】
【数２】
2004054384.tif 000004
【００１２】
符号器１は生成多項式に基づいて入力データの剰余を求めるため、生成多項式の係数に基づいた乗算器２００，２０１，２０２，２０３を備えている。生成多項式の係数は、不定元χの低次から高次へと向かう順にα６，１，α４，α１２，１であるので、乗算器２００，２０１，２０２，２０３はそれぞれ乗数α６，１，α４，α１２を用いてガロア拡大体の乗算を行う。最高次に対応する乗算器は不要である。
【００１３】
ここでは符号化の対象となる入力データＤは４ビット毎に更新され、符号器１は４ビットのレジスタ２０４，２０６，２０８，２１０、４ビットの排他的論理和回路（以下「ＸＯＲゲート」と称す）２０５，２０７，２０９，２１１を備えている。入力データＡは１クロック毎に４ビットずつＸＯＲゲート２１１に入力する。
【００１４】
符号化の際の初期値としてレジスタ２０４，２０６，２０８，２１０には４ビットの値“００００”が格納されている。またＸＯＲゲート２０５，２０７，２０９，２１１はビット毎に対をなす二入力の排他的論理和を求め、ビット毎に出力する。図２はＸＯＲゲート２０５，２０７，２０９，２１１の各々の構成例を示す回路図である。各々４ビットのデータＬ１，Ｌ２を入力し、これらの排他的論理和を採って４ビットのデータＬ３を出力する構成が示されている。二入力のＸＯＲゲート２１，２２，２３，２４が備えられる。
【００１５】
ＸＯＲゲート２１１はレジスタ２１０の出力と入力データＤとの排他的論理和を出力する。排他的論理和は通常の和の２を法とする剰余であり、ガロア拡大体ＧＦ（２ｍ）の加算結果と一致する。ＸＯＲゲート２１１は乗算器２００，２０１，２０２，２０３に与えられ、これらにおいて上述の乗算が行われる。但し、乗算器において採用される乗数は生成多項式に依存する。図１では式（２）で例示された生成多項式Ｇ（χ）に基づいて、それぞれの乗算器の乗数が例示されているが、生成多項式が異なれば、他の構造を採ることができる。乗算器２００，２０１，２０２，２０３から得られた乗算結果たる出力は、それぞれレジスタ２０４，ＸＯＲゲート２０５，２０７，２０９に与えられる。
【００１６】
ＸＯＲゲート２０５はレジスタ２０４の出力と乗算器２０１の出力との排他的論理和を採ってレジスタ２０６へと出力する。ＸＯＲゲート２０７はレジスタ２０６の出力と乗算器２０２の出力との排他的論理和を採ってレジスタ２０８へと出力する。ＸＯＲゲート２０９はレジスタ２０８の出力と乗算器２０３の出力との排他的論理和を採ってレジスタ２１０へと出力する。但し乗算器２０１の乗数は１であるので、これを省略し、ＸＯＲゲート２１１の出力を直接にＸＯＲゲート２０５に与えることができる。
【００１７】
１クロック分の動作が進む毎に、入力データＡは新たな４ビットのデータをＸＯＲゲート２１１に与え、かつレジスタ２０４，２０６，２０８，２１０は、自身に与えられた４ビットのデータをそれぞれＸＯＲゲート２０５，２０７，２０９，２１１へと出力する。これにより、符号語の内の検査ブロックの４ブロックが、それぞれ上位から順にレジスタ２１０，２０８，２０６，２０４の出力として得られる。即ちレジスタ２０４からは検査ブロックの最下位４ビットが、レジスタ２１０からは検査ブロックの最上位４ビットが、それぞれ出力される。
【００１８】
図３は、乗算器２００，２０２，２０３として採用可能な、実施の形態１にかかる乗算器の構成を示す回路図である。
【００１９】
当該乗算器は、被乗数提供部１００と、乗数提供部３００と、積和処理部４００とを備えている。被乗数提供部１００は被乗数Ａの４ビットデータＡ３Ａ２Ａ１Ａ０を最上位ビットから順に、即ちＡ３，Ａ２，Ａ１，Ａ０の順に、１ビットずつ積和処理部４００に入力する。被乗数提供部１００は直列に接続された４つのレジスタ１０５，１０６，１０７，１０８を有しており、これらはこの順に積和処理部４００へと近づく配置がなされている。レジスタ１０５，１０６，１０７，１０８はそれぞれ１クロック分だけ遅延してデータを伝達する。
【００２０】
乗数提供部３００は既約原始多項式に依存した構造を有し、乗数に依存した初期値が設定される。図３では式（１）で示される既約原始多項式ｇ（χ）が採用された場合の構造を例示しており、いずれも自身に入力した信号に対して１クロック分の遅延を与えて出力するレジスタ３０１，３０２，３０３，３０５及びＸＯＲゲート３０４を備えている。式（１）で示される既約原始多項式ｇ（χ）が０に等しくなる根をαとおくと、ガロア拡大体ＧＦ（２４）の元は、αの累乗として表すことができ、指数が増加する順に、ベクトル表現で次の様に表される。即ち（０１００），（００１０），（０００１），（１１００），（０１１０），（００１１），（１１０１），（１０１０），（０１０１），（１１１０），（０１１１），（１１１１），（１０１１），（１００１），（１０００）である。これ以上に指数が増加する場合には上記のベクトル表現が循環して採用される。
【００２１】
上記のベクトル表現を得るため、レジスタ３０１の出力はレジスタ３０２に入力し、レジスタ３０２の出力はレジスタ３０３に入力し、レジスタ３０３の出力はＸＯＲゲート３０４の一方の入力となり、ＸＯＲゲート３０４の出力はレジスタ３０５の入力となり、レジスタ３０５の出力はレジスタ３０１の入力となると共に、ＸＯＲゲート３０４の他方の入力ともなる。乗数提供部３００は１クロック毎にガロア拡大体ＧＦ（２４）の元を、αの指数を１次ずつ低くして出力する。
【００２２】
一般に符号長が４ビットであるガロア拡大体の乗算は、上記公報にも開示されているように、式（３）で表され
【００２３】
【数３】
2004054384.tif 000005
【００２４】
但し係数Ｔ１１，Ｔ１２，Ｔ１３，Ｔ１４は乗数をベクトル表現した値と一致する。また、式（４）〜（６）が成立する。ここで示された乗算記号「×」はガロア拡大体ＧＦ（２ｍ）におけるベクトルの乗算を示す。
【００２５】
【数４】
2004054384.tif 000006
【００２６】
【数５】
2004054384.tif 000007
【００２７】
【数６】
2004054384.tif 000008
【００２８】
つまり（３）式で表された行列は、乗数に基づいた複数のベクトル（Ｔ１１，Ｔ１２，Ｔ１３，Ｔ１４），（Ｔ２１，Ｔ２２，Ｔ２３，Ｔ２４），（Ｔ３１，Ｔ３２，Ｔ３３，Ｔ３４），（Ｔ４１，Ｔ４２，Ｔ４３，Ｔ４４）で構成されている。
【００２９】
さて、上述の通り、乗数提供部３００は１クロック毎にガロア拡大体ＧＦ（２４）の元を、αの指数を１次ずつ低くして出力する。よって乗数Ｎとα３との間でガロア拡大体の乗算を行った結果を、初期値としてレジスタ３０１，３０２，３０３，３０５に与えておく。こうすれば１クロック毎に式（３）の行列の縦ベクトルが右側から順に出力され、これと被乗数Ａとの積和演算が実行される。
【００３０】
積和処理部４００は、それぞれレジスタ３０１，３０２，３０３，３０５の出力を受け、またいずれもがレジスタ１０８の出力を受ける積和単位４０１，４０２，４０３，４０４を有している。つまり積和単位４０１，４０２，４０３，４０４は縦ベクトルの要素毎に複数設けられる。
【００３１】
積和単位４０１，４０２，４０３，４０４はいずれも同一の構成を有している。即ち、積和単位の各々はアンドゲート４１，ＸＯＲゲート４２、レジスタ４３を備えている。レジスタ４３は、入力端と、自身の入力端に与えられた信号を１クロック分遅延して出力する出力端とを有する。アンドゲート４１は、第１端及び第２端、並びに自身の第１端及び前記第２端に入力する信号の二値論理についての論理積を出力する出力端を有する。ＸＯＲゲートは、アンドゲート４１の出力を入力する第１端と、レジスタ４３の出力端に接続された第２端、並びに自身の第１端及び第２端に入力する信号の二値論理についての排他的論理和をレジスタ４３の入力端に出力する出力端とを有する。そしてアンドゲート４１の第１端にはレジスタ１０８の出力が与えられる。またアンドゲート４１の第２端には、乗算提供部３００が有しているレジスタのうちで、このアンドゲート４１が属する積和単位に対応するものの出力が入力される。例えば積和単位４０１について言えば、そのアンドゲート４１の第２端にはレジスタ３０１の出力が与えられる。
【００３２】
以下、図３に示された乗算器を、図１に示された乗算器２０３として採用した場合の動作について説明する。
【００３３】
図３は最初の積和演算を行う状態を示している。いずれの積和単位においても、その備えるレジスタ４３にはデータ“０”が格納されている。また被乗数提供部１００においては、レジスタ１０５，１０６，１０７，１０８からはそれぞれＡ０，Ａ１，Ａ２，Ａ３が出力されている。積和処理部４００が備えるレジスタ乗算器２０３の乗数はα１２であるので積和処理部４００に出力する初期値としてはα１５＝１が採用される。よってこの初期値に対応して、レジスタ３０１，３０２，３０３，３０５からはそれぞれＴ４１，Ｔ４２，Ｔ４３，Ｔ４４に対応する値“０”，“０”，“０”，“１”が出力されている。
【００３４】
積和単位４０１において、アンドゲート４１にはいずれも１ビットのデータＴ４１、Ａ３が入力する。レジスタ４３からその初期値として“０”が出力されているので、ＸＯＲゲート４２はアンドゲート４１の出力をそのまま出力する。これによりレジスタ４３の入力には、被乗数Ａの１ビットＡ３と、乗数α１５の１ビットＴ４１とのガロア拡大体ＧＦ（２ｍ）の乗算結果であるＡ３・Ｔ４１が与えられる。乗算記号「・」はガロア拡大体ＧＦ（２ｍ）における乗算を示す。但し積和単位４０１の出力はレジスタ４３の出力から得られるので、この時点では積和単位４０１の出力は“０”である。
【００３５】
同様にして、積和単位４０２のレジスタ４３の入力にはＡ３・Ｔ４２が与えられ、積和単位４０３のレジスタ４３の入力にはＡ３・Ｔ４３が与えられ、積和単位４０４のレジスタ４３の入力にはＡ３・Ｔ４４が与えられる。そして積和単位４０２，４０３，４０４のいずれの出力も“０”である。
【００３６】
図４は、図３に示された状態から１クロック分の時間が経過した場合の状態を示すブロック図である。被乗数提供部１００においてレジスタ１０６，１０７，１０８からは、それぞれ１ビットのデータＡ０，Ａ１，Ａ２が出力される。一方、乗数提供部３００からはレジスタ３０１，３０２，３０３，３０５においてそれぞれＴ３１，Ｔ３２，Ｔ３３，Ｔ３４に対応する値“１”，“０”，“０”，“１”が出力されている。
【００３７】
積和単位４０１において、レジスタ４３からは１クロック分前の動作で入力されたＡ３・Ｔ４１が出力されている。一方、アンドゲート４１にはいずれも１ビットのデータＴ３１、Ａ２が入力するので、ＸＯＲゲート４２はＡ３・Ｔ４１＋Ａ２・Ｔ３１（但し加算記号「＋」は排他的論理和を示す）を出力する。これによりレジスタ４３の入力にはＡ３・Ｔ４１＋Ａ２・Ｔ３１が与えられる。但し積和単位４０１の出力はＡ３・Ｔ４１である。
【００３８】
同様にして、積和単位４０２のレジスタ４３の入力にはＡ３・Ｔ４２＋Ａ２・Ｔ３２が与えられ、積和単位４０３のレジスタ４３の入力にはＡ３・Ｔ４３＋Ａ２・Ｔ３３が与えられ、積和単位４０４のレジスタ４３の入力にはＡ３・Ｔ４４＋Ａ２・Ｔ３４が与えられる。そして積和単位４０２，４０３，４０４の出力は、それぞれＡ３・Ｔ４２，Ａ３・Ｔ４３，Ａ３・Ｔ４４となる。
【００３９】
図５は、図４に示された状態から１クロック分の時間が経過した場合の状態を示すブロック図である。被乗数提供部１００においてレジスタ１０７，１０８からは、それぞれ１ビットのデータＡ０，Ａ１が出力される。一方、乗数提供部３００ではレジスタ３０１，３０２，３０３，３０５からそれぞれＴ２１，Ｔ２２，Ｔ２３，Ｔ２４に対応する値“１”，“１”，“０”，“１”が出力されている。
【００４０】
積和単位４０１において、レジスタ４３からは１クロック分前の動作で入力されたＡ３・Ｔ４１＋Ａ２・Ｔ３１が格納されている。一方、アンドゲート４１にはいずれも１ビットのデータＴ２１、Ａ１が入力するので、ＸＯＲゲート４２はＡ３・Ｔ４１＋Ａ２・Ｔ３１＋Ａ１・Ｔ２１を出力する。これによりレジスタ４３の入力にはＡ３・Ｔ４１＋Ａ２・Ｔ３１＋Ａ１・Ｔ２１が与えられる。但し積和単位４０１の出力はＡ３・Ｔ４１＋Ａ２・Ｔ３１である。
【００４１】
同様にして、積和単位４０２のレジスタ４３の入力にはＡ３・Ｔ４２＋Ａ２・Ｔ３２＋Ａ１・Ｔ２２が与えられ、積和単位４０３のレジスタ４３の入力にはＡ３・Ｔ４３＋Ａ２・Ｔ３３＋Ａ１・Ｔ２３が与えられ、積和単位４０４のレジスタ４３の入力にはＡ３・Ｔ４４＋Ａ２・Ｔ３４＋Ａ１・Ｔ２４が与えられる。そして積和単位４０２，４０３，４０４の出力は、それぞれＡ３・Ｔ４２＋Ａ２・Ｔ３２，Ａ３・Ｔ４３＋Ａ２・Ｔ３３，Ａ３・Ｔ４４＋Ａ２・Ｔ３４となる。
【００４２】
図６は、図５に示された状態から１クロック分の時間が経過した場合の状態を示すブロック図である。被乗数提供部１００においてレジスタ１０８からは１ビットのデータＡ０が出力される。一方、乗数提供部３００ではレジスタ３０１，３０２，３０３，３０５からはそれぞれＴ１１，Ｔ１２，Ｔ１３，Ｔ１４に対応する値“１”，“１”，“１”，“１”が出力されている。
【００４３】
図３乃至図５に示された場合と同様に動作が進み、積和単位４０１のレジスタ４３の入力にはＡ３・Ｔ４１＋Ａ２・Ｔ３１＋Ａ１・Ｔ２１＋Ａ０・Ｔ１１が与えられ、積和単位４０２のレジスタ４３の入力にはＡ３・Ｔ４２＋Ａ２・Ｔ３２＋Ａ１・Ｔ２２＋Ａ０・Ｔ１２が与えられ、積和単位４０３のレジスタ４３の入力にはＡ３・Ｔ４３＋Ａ２・Ｔ３３＋Ａ１・Ｔ２３＋Ａ０・Ｔ１３が与えられ、積和単位４０４のレジスタ４３の入力にはＡ３・Ｔ４４＋Ａ２・Ｔ３４＋Ａ１・Ｔ２４＋Ａ０・Ｔ１４が与えられる。そして積和単位４０１，４０２，４０３，４０４の出力は、それぞれＡ３・Ｔ４１＋Ａ２・Ｔ３１＋Ａ１・Ｔ２１，Ａ３・Ｔ４２＋Ａ２・Ｔ３２＋Ａ１・Ｔ２２，Ａ３・Ｔ４３＋Ａ２・Ｔ３３＋Ａ１・Ｔ２３，Ａ３・Ｔ４４＋Ａ２・Ｔ３４＋Ａ１・Ｔ２４となる。
【００４４】
図７は、図６に示された状態から１クロック分の時間が経過した場合の状態を示すブロック図である。被乗数提供部１００において積和単位４０１，４０２，４０３，４０４からは、それぞれ１クロック分前においてレジスタ４３に入力していたＡ３・Ｔ４１＋Ａ２・Ｔ３１＋Ａ１・Ｔ２１＋Ａ０・Ｔ１１，Ａ３・Ｔ４２＋Ａ２・Ｔ３２＋Ａ１・Ｔ２２＋Ａ０・Ｔ１２，Ａ３・Ｔ４３＋Ａ２・Ｔ３３＋Ａ１・Ｔ２３＋Ａ０・Ｔ１３，Ａ３・Ｔ４４＋Ａ２・Ｔ３４＋Ａ１・Ｔ２４＋Ａ０・Ｔ１４が出力される。
【００４５】
これにより式（３）が計算されたことになり、被乗数Ａと乗数α１２とのガウス拡大体ＧＦ（２４）における乗算が行われたことになる。ＸＯＲゲート４２の一方の入力端にはアンドゲート４１から得られた乗数の１ビット及び被乗数の１ビットのガロア拡大体ＧＦ（２ｍ）での乗算結果が与えられる。ＸＯＲゲート４２の他方の入力端には、ＸＯＲゲートの出力であって遅延されたものである、乗数の他の１ビット及び被乗数の他の１ビットのガロア拡大体ＧＦ（２ｍ）での乗算結果が与えられる。よってレジスタ４３の遅延時間を適切に（ここでは１クロック分）設定することにより、ベクトル表現した乗数と被乗数との積を得ることができる。
【００４６】
図３に示された乗算器では乗算を計算するのに４クロック分が必要となる。よって符号化器１において本実施の形態に示された乗算器を採用する場合には、入力データＤを与えるタイミングを４倍引き延ばす必要がある。しかしながら乗数が固定されている場合に特に好適であり、生成多項式に基づいて乗数が固定された乗算器として採用されることにより、符号化器の構成の冗長を小さくすることができる。
【００４７】
符号長をｎビットとするならば、乗数αｓを乗算する場合には、乗数提供部３００のレジスタにはαｓ＋（ｎ−１）をベクトル表現した値を初期値として格納すればよい。そして乗数提供部３００は、上述の通り、ガロア拡大体を得るために用いた既約原始多項式に基づいて、レジスタ、ＸＯＲゲートを用いて構成することができる。
【００４８】
但し、乗数提供部３００としては、図３に示されたような１クロック毎にガロア拡大体ＧＦ（２４）の元をαの指数を１次ずつ低くして出力するもの以外に、αの指数を１次ずつ高くして出力するものを採用することができる。図８はこのような乗数提供部３００の構造を例示するブロック図であり、例えば特公平６−８０４９１号公報によって開示されている。乗算器３００においてレジスタ３０１の出力Ｔ１はＸＯＲゲート３０４の一方の入力となると共にレジスタ３０５の入力にもなる。レジスタ３０５の出力Ｔ４はＸＯＲゲート３０４の他方の入力となる。ＸＯＲゲート３０４の出力はレジスタ３０３の入力となる。レジスタ３０３の出力Ｔ３はレジスタ３０２の入力となる。レジスタ３０２の出力Ｔ２はレジスタ３０１の入力となる。レジスタ３０１，３０２，３０３，３０５の初期値として値Ｔ１１，Ｔ１２，Ｔ１３，Ｔ１４を格納しておくことにより、１クロック分の時間が経過する毎に、出力Ｔ１は値Ｔ１１，Ｔ２１，Ｔ３１，Ｔ４１を、出力Ｔ２はＴ１２，Ｔ２２，Ｔ３２，Ｔ４２を、出力Ｔ３はＴ１３，Ｔ２３，Ｔ３３，Ｔ４３を、出力Ｔ４はＴ１４，Ｔ２４，Ｔ３４，Ｔ４４を、それぞれ順次に採ってゆく。
【００４９】
図８の乗数提供部３００を採用する場合に式（３）を計算するためには、被乗数Ａが被乗数提供部１００に入力する順序を図３に示された場合と逆にする。即ち、まずＡ０を入力し、その後順次にＡ１，Ａ２，Ａ３を入力する。
【００５０】
実施の形態２．
図９は、図１に示された符号化器１の乗算器２００，２０２，２０３として採用可能な、実施の形態２にかかる乗算器の構成を示す回路図である。当該乗算器も実施の形態１と同様に、被乗数提供部１００と、乗数提供部３００と、積和処理部４００とを備えている。
【００５１】
実施の形態２の被乗数提供部１００の構造は、実施の形態１と同様に直列に接続された４つのレジスタ１０５，１０６，１０７，１０８を有しており、これらはこの順に積和処理部４００へと近づく配置がなされている。被乗数提供部１００には被乗数Ａの４ビットデータＡ３Ａ２Ａ１Ａ０が最上位ビットから順に、即ちＡ３，Ａ２，Ａ１，Ａ０の順に、１ビットずつ積和処理部４００に入力される。但しレジスタ１０５，１０６，１０７，１０８はそれぞれ後述するクロック信号ＣＫ２の１クロック分だけ遅延してデータを伝達する。
【００５２】
実施の形態２の乗数提供部３００は、実施の形態１に示された乗数提供部３００の構造（図３参照）に対して、マルチプレクサ３０６と、２ビットカウンタ３０７とを追加した構成を有している。マルチプレクサ３０６は２ビットカウンタ３０７の制御に基づいてレジスタ３０１，３０２，３０３，３０５の出力から一つを選択して出力する。２ビットカウンタ３０７はクロック信号ＣＫ１に基づいてカウント動作を行い、クロック信号ＣＫ１の４クロック分でカウント動作は一巡する。これに伴い２ビットカウンタ３０７からはクロック信号ＣＫ１の４クロック分を一周期とするクロック信号ＣＫ２を出力する。即ちクロック信号ＣＫ２の１クロック分はクロック信号ＣＫ１の４クロック分に相当する。そしてレジスタ３０１，３０２，３０３，３０５はそれぞれクロック信号ＣＫ２の１クロック分だけ遅延してデータを伝達する。
【００５３】
実施の形態２の積和処理部４００は、実施の形態１に示された積和単位が一つだけ備えられており、そのレジスタ４３を、ＸＯＲゲート４２の出力から近い方から順に、レジスタ４３ａ，４３ｂ，４３ｃ，４３ｄの直列接続として有する構造を呈している。これらのレジスタはいずれもクロック信号ＣＫ１の１クロック分だけ遅延してデータを伝達する。よってレジスタ４３の全体としては、乗数のベクトルを構成する要素の数４と、クロック信号ＣＫ１の１クロックとの積でデータが遅延して伝達されることになる。
【００５４】
図９は最初の積和演算を行う状態を示している。レジスタ４３ａ，４３ｂ，４３ｃ，４３ｄのいずれからも、データ“０”が出力されている。また被乗数提供部１００においては、レジスタ１０５，１０６，１０７，１０８にはそれぞれＡ０，Ａ１，Ａ２，Ａ３が出力されている。符号化器１が備えるレジスタ乗算器２０３の乗数はα１２であるので積和処理部４００に出力する初期値としてはα１５＝１が採用される。よってこの初期値に対応して、レジスタ３０１，３０２，３０３，３０５からそれぞれＴ４１，Ｔ４２，Ｔ４３，Ｔ４４に対応する値“０”，“０”，“０”，“１”が出力されている。積和処理部４００においてＸＯＲゲート４２からは出力Ａ３・Ｔ４１が得られている。
【００５５】
図１０は図９に示された状態からクロック信号ＣＫ１の１クロック分の時間が経過した場合の状態を示すブロック図である。この状態ではレジスタ１０５，１０６，１０７，１０８，３０１，３０２，３０３，３０５が出力するデータは変化していない。しかしマルチプレクサ３０６は２ビットカウンタ３０７の制御を受けて、データＴ４２を選択して出力する。これによりＸＯＲゲート４２からは出力Ａ３・Ｔ４２が得られている。レジスタ４３ａからは、クロック信号ＣＫ１の１クロック分前に入力したデータＡ３・Ｔ４１が出力されている。
【００５６】
図１１は図１０に示された状態からクロック信号ＣＫ１の２クロック分の時間が経過した場合の状態を示すブロック図である。マルチプレクサ３０６は２ビットカウンタ３０７の制御を受けて、データＴ４４を出力する。これによりＸＯＲゲート４２からは出力Ａ３・Ｔ４４が得られている。レジスタ４３ａ，４３ｂ，４３ｃ，４３ｄからはそれぞれＡ３・Ｔ４３，Ａ３・Ｔ４２，Ａ３・Ｔ４１，“０”が出力されている。
【００５７】
図１２は図１１に示された状態からクロック信号ＣＫ１の１クロック分の時間が経過した場合の状態を示すブロック図である。この状態では、図９に示された状態からクロック信号ＣＫ２の１クロック分の時間が経過している。よってレジスタ１０６，１０７，１０８，３０１，３０２，３０３，３０５が出力するデータがそれぞれＡ０，Ａ１，Ａ２，Ｔ３１，Ｔ３２，Ｔ３３，Ｔ３４に変化する。マルチプレクサ３０６は２ビットカウンタ３０７の制御を受けて、データＴ３１を出力する。
レジスタ４３ａ，４３ｂ，４３ｃ，４３ｄからはそれぞれＡ３・Ｔ４４，Ａ３・Ｔ４３，Ａ３・Ｔ４２，Ａ３・Ｔ４１が出力されている。ＸＯＲゲート４２にはアンドゲート４１の出力Ａ２・Ｔ３１とレジスタ４３ｄの出力Ａ３・Ｔ４１が入力するので、ＸＯＲゲート４２の出力はＡ３・Ｔ４１＋Ａ２・Ｔ３１となる。このようにして、クロック信号ＣＫ１の４クロック分が経過することにより、実施の形態１において図４で示された積和単位４０１のＸＯＲゲート４２の出力が得られることになる。実施の形態２において積和処理部４００のレジスタ４３は、シリアルの４ビットデータをクロック信号ＣＫ１の１クロック分が経過する度に、ビット毎に順次シフトさせる機能を果たすといえる。
【００５８】
図１３は図９に示された状態からクロック信号ＣＫ１の１３クロック分の時間が経過した状態を示すブロック図である。レジスタ３０１，３０２，３０３，３０５からはそれぞれＴ１１，Ｔ１２，Ｔ１３，Ｔ１４が出力されており、マルチプレクサ３０６は２ビットカウンタ３０７の制御によってレジスタ３０１から得られたデータＴ１１を出力している。レジスタ１０８からは乗数Ａの最下位ビットのデータＡ０が出力されており、従ってアンドゲート４１からはデータＡ０・Ｔ１１が出力されている。レジスタ４３ａ，４３ｂ，４３ｃ，４３ｄからはそれぞれＡ３・Ｔ４４＋Ａ２・Ｔ３４＋Ａ１・Ｔ２４，Ａ３・Ｔ４３＋Ａ２・Ｔ３３＋Ａ１・Ｔ２３，Ａ３・Ｔ４２＋Ａ２・Ｔ３２＋Ａ１・Ｔ２２，Ａ３・Ｔ４１＋Ａ２・Ｔ３１＋Ａ１・Ｔ２１が出力されている。よってＸＯＲゲート４２の出力はＡ３・Ｔ４１＋Ａ２・Ｔ３１＋Ａ１・Ｔ２１＋Ａ０・Ｔ１１となる。
【００５９】
図１３に示された状態からクロック信号ＣＫ１の３クロック分の時間が経過することにより、レジスタ４３ａ，４３ｂ，４３ｃ，４３ｄにはそれぞれＡ３・Ｔ４４＋Ａ２・Ｔ３４＋Ａ１・Ｔ２４＋Ａ０・Ｔ１４，Ａ３・Ｔ４３＋Ａ２・Ｔ３３＋Ａ１・Ｔ２３＋Ａ０・Ｔ１３，Ａ３・Ｔ４２＋Ａ２・Ｔ３２＋Ａ１・Ｔ２２＋Ａ０・Ｔ１２，Ａ３・Ｔ４１＋Ａ２・Ｔ３１＋Ａ１・Ｔ２１＋Ａ０・Ｔ１１が入力する。このように、図３に示された状態からクロック信号ＣＫ１の１６クロック分の時間（クロック信号ＣＫ２の４クロック分の時間）が経過して、実施の形態１において図６で示された積和単位４０１〜４０３のＸＯＲゲート４２の出力が得られることになる。
【００６０】
その後、更にクロック信号ＣＫ１の１クロック分ずつ時間が経過する毎に、積和演算処理部４００の出力Ｂは、順次Ａ３・Ｔ４１＋Ａ２・Ｔ３１＋Ａ１・Ｔ２１＋Ａ０・Ｔ１１，Ａ３・Ｔ４２＋Ａ２・Ｔ３２＋Ａ１・Ｔ２２＋Ａ０・Ｔ１２，Ａ３・Ｔ４３＋Ａ２・Ｔ３３＋Ａ１・Ｔ２３＋Ａ０・Ｔ１３，Ａ３・Ｔ４４＋Ａ２・Ｔ３４＋Ａ１・Ｔ２４＋Ａ０・Ｔ１４を出力する。
【００６１】
以上のようにして、本実施の形態によって式（３）の結果を得るまでにはクロック信号ＣＫ１の２０クロック分が必要である。実施の形態１によって同じ結果を得るまでにはクロック信号の５クロック分が必要であった。従って、本実施の形態では実施の形態１と比較して動作が４倍遅くなる。これに伴って符号化器１の動作も４倍遅くなる。しかしながら図３及び図９を比較すると明白なように、本実施の形態の方が、実施の形態１と比較して、アンドゲート３個分、ＸＯＲゲート３個分を省略し、回路規模が小さくなる。
【００６２】
本実施の形態においても、図８に示された乗算提供部３００を採用することができる。この場合、実施の形態１において説明したように、被乗数Ａの各ビットを積和処理部４００に与える順序を逆にする必要がある。
【００６３】
【発明の効果】
この発明のうち請求項１にかかる演算器によれば、第１ゲートの第１端及び第２端に、それぞれ乗数の１ビット及び被乗数の１ビットを与えることにより、両者のガロア拡大体ＧＦ（２ｍ）での乗算結果が第１ゲートから得られる。当該結果は第２ゲートの第１端に与えられる。第２ゲートの第２端には、被乗数の他の１ビットと乗数の他の１ビットとのガロア拡大体ＧＦ（２ｍ）での乗算結果が与えられる。よって第２ゲートの第２端に与えるデータとして、第２ゲートの出力を所定の時間遅延したものを採用することにより、ベクトル表現した乗数と被乗数との積を得ることができる。
【００６４】
この発明のうち請求項２にかかる演算器によれば、積和単位の数を低減して回路規模を小さくして、ガロア拡大体ＧＦ（２ｍ）での乗数と被乗数との積を得ることができる。
【００６５】
この発明のうち請求項３にかかる演算器によれば、積和単位の数を一層低減して回路規模を更に小さくして、ガロア拡大体ＧＦ（２ｍ）での乗数と被乗数との積を得ることができる。
【図面の簡単な説明】
【図１】本発明の実施の形態にかかる乗算器が適用可能な符号器の構造を示すブロック図である。
【図２】ＸＯＲゲートの構成例を示す回路図である。
【図３】本発明の実施の形態１にかかる乗算器の構成を示す回路図である。
【図４】本発明の実施の形態１にかかる乗算器の動作を示す回路図である。
【図５】本発明の実施の形態１にかかる乗算器の動作を示す回路図である。
【図６】本発明の実施の形態１にかかる乗算器の動作を示す回路図である。
【図７】本発明の実施の形態１にかかる乗算器の動作を示す回路図である。
【図８】乗数提供部の構造を例示するブロック図である。
【図９】本発明の実施の形態２にかかる乗算器の動作を示す回路図である。
【図１０】本発明の実施の形態２にかかる乗算器の動作を示す回路図である。
【図１１】本発明の実施の形態２にかかる乗算器の動作を示す回路図である。
【図１２】本発明の実施の形態２にかかる乗算器の動作を示す回路図である。
【図１３】本発明の実施の形態２にかかる乗算器の動作を示す回路図である。
【図１４】従来の技術を示す回路図である。
【符号の説明】
４１　アンドゲート、４２　ＸＯＲゲート、４３，４３ａ〜４３ｄ，１０５〜１０８，３０１〜３０４　レジスタ、１００　被乗数提供部、２００〜２０３　乗算器、３００　乗数提供部、４００　積和処理部、４０１〜４０４　積和単位。
【図１】
2004054384.tif 000009
【図２】
2004054384.tif 000010
【図３】
2004054384.tif 000011
【図４】
2004054384.tif 000012
【図５】
2004054384.tif 000013
【図６】
2004054384.tif 000014
【図７】
2004054384.tif 000015
【図８】
2004054384.tif 000016
【図９】
2004054384.tif 000017
【図１０】
2004054384.tif 000018
【図１１】
2004054384.tif 000019
【図１２】
2004054384.tif 000020
【図１３】
2004054384.tif 000021
【図１４】
2004054384.tif 000022