(57)【要約】【課題】ＣＲＣ符号器を用いたガロア体の掛け算を行うガロア体掛け算器を提供する。【解決手段】第１シフトレジスタ１１からのビット列Ｓｊは、最上位ビットから順にアンドゲート回路１３に出力される。アンドゲート回路１３はそのビットと入力レジスタ１０に入力されているビット列Ｄｉとの間で掛け算し排他的論理和ゲート回路１４に出力する。排他的論理和ゲート回路１４は、アンドゲート回路１３の掛け算結果と第２シフトレジスタ１２の内容との間で排他的論理和計算を行ないその計算結果を同シフトレジスタ１２に入力する。ＣＲＣ符号器３は第２シフトレジスタ１２の内容を最上位ビットから順番に入力してＣＲＣ演算する。排他的論理和ゲート回路４は、ＣＲＣ符号器３の演算結果の内容と第２シフトレジスタ１２の内容との間で排他的論理和計算を行なう。【選択図】　　　　図１
2004094871.tif 000002
【特許請求の範囲】
【請求項１】
第１レジスタに入力されたガロア体の要素からなるＮビットの第１ビット列と、第２レジスタに入力されたガロア体の要素からなるＮビットの第２ビット列とのガロア体掛け算を行なうガロア体掛け算器において、
Ｎビットの排他的論理和計算の結果を入力しその時の最上位ビットを出力しながら最上位ビット側に１ビットシフトするシフトレジスタと、
前記Ｎビットの第２ビット列の最上位ビットから順番に１ビットずつ、前記Ｎビットの第１ビット列との間で順番に掛け算するアンドゲート回路と、
前記アンドゲート回路からの演算結果と前記シフトレジスタの内容との間で排他的論理和計算を行ないその計算結果を前記シフトレジスタに入力する第１排他的論理和ゲート回路と、
前記シフトレジスタからの最上位ビットを順次入力しＣＲＣ演算するＣＲＣ符号器と、
前記ＣＲＣ符号器の内容と前記シフトレジスタの内容との間で排他的論理和計算を行なう第２排他的論理和ゲート回路と
を備えたことを特徴とするガロア体掛け算器。
【請求項２】
第１レジスタに入力されたガロア体の要素からなるＮビットの第１ビット列と、第２レジスタに入力されたガロア体の要素からなるＮビットの第２ビット列とのガロア体掛け算を行なうガロア体掛け算器において、
前記Ｎビットの第１ビット列に対して、前記第２ビット列の各位のビット毎にそれぞれ掛け算を行なう第１の回路部と、
前記第１の回路部で各位のビット毎に行なった前記Ｎビットの第１ビット列に対する各計算結果について、それぞれ同一の位同士のビットとの間で排他的論理和計算を行ない２Ｎビットの計算結果を生成する第２の回路部と、
前記第２の回路部で行なった、２Ｎビットの計算結果を入力する第３レジスタと、
前記第３レジスタに入力された２Ｎビットの演算結果の上位Ｎビットを順次入力しＣＲＣ計算を行なうＣＲＣ符号器と、
前記ＣＲＣ符号器のＣＲＣ計算結果と、前記第３レジスタに入力された２Ｎビットの演算結果の下位Ｎビットとの間で排他的論理和計算を行なう排他的論理和ゲート回路と
を備えたことを特徴とするガロア体掛け算器。
【請求項３】
請求項１又は２に記載のガロア体掛け算器において、
Ｎビットの第１ビット列は、ＣＲＣ計算で求められたガロア体の要素を示すＮビットのビット列であり、
前記Ｎビットの第２ビット列は、「０」の数の次数のガロア体の要素を示すＮビットのビット列であることを特徴とするガロア体掛け算器。
【請求項４】
請求項３に記載のガロア体掛け算器において、
Ｎビットの第１ビット列は、予め定められたｋ１ビットからｋ２ビットの範囲のデータ列をＣＲＣ計算した結果得られたガロア体の要素を示すＮビットのビット列であり、
前記Ｎビットの第２ビット列は、前記ｋ２ビットの次のビットから最終ビットまでのデータ列を全て「０」とし、その「０」の数の次数のガロア体の要素を示すＮビットのビット列であることを特徴とするガロア体掛け算器。
【請求項５】
請求項１乃至４項のいずれか１つに記載のガロア体掛け算器を実装した通信装置。
【請求項６】
請求項５に記載の通信装置において、
通信装置の信号処理装置に設けられた本来のＣＲＣ計算を行なうためのＣＲＣ符号器を、前記ガロア体掛け算を行なうガロア体掛け算器のＣＲＣ符号器を兼用することを特徴とする通信装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はガロア体掛け算器及び通信装置に関する。
【０００２】
【従来の技術】
通信装置のひとつとして、異なるインターネットワーク同士を相互に接続するルータがある。ルータは、入力したデータ中の接続先のアドレスを抽出し、その抽出したアドレスから次に繋ぐルータをルーティングテーブルから検索する。そして、ルーティングテーブルを使って、前記抽出したアドレスから次に繋ぐルータが見つかると、ルータは、その次のルータにデータを出力する。
【０００３】
ところで、アドレスデータから次に接続するルータをルーティングテーブルから検索する際、一般にハッシュ検索が採用されている。
【０００４】
ハッシュ検索は、各検索データのハッシュ値を予め計算しておく。ハッシュ値とは、検索データを適当な桁数の素数で割り算した時に得られる余りの値をハッシュ値という。異なるデータ系列の検索データにおいてそのハッシュ値が等しくなることがあるので、ハッシュ値ごとに各検索データをグループに分類する。つまり、同一のハッシュ値になる検索データを同一グループに分類しておく。
【０００５】
そして、被検索データについて、ハッシュ値を求める。その求めたハッシュ値からこの被検索データが、前記分類したグループのどのグループに属するかを特定する。その特定したグループ内の検索データ中から被検索データと一致する検索データを検索するようにしたのがハッシュ検索である。
【０００６】
図４は、ハッシュ検索を説明するための説明図である。図４において、検索データテーブルＴＤは、ｍ個のｎバイトからなる検索データＤＳの集合で、予めハッシュ値を計算して、グループ化されたテーブルである。このグループ化は、各検索データブロックＤＢの中のネクストポインタＰによって順次グループ内の次候補をリンクしてリストを構成している。各グループの最後のリストのポインタＰはそれぞれ“０”にする。
【０００７】
各グループの最初の検索データブロックＤＢのポインタＰは、検索タグテーブルＴＴに書き込まれている。検索タグテーブルＴＴには、ハッシュ値ＨＴをインデックス番号（アドレス）としてそのハッシュ値ＨＴに対応する検索データテーブルＴＤの各グループの最初の検索データブロックＤＢのポインタＰが書き込まれている。
【０００８】
そして、入力データとしてｎバイトの被検索データＤＸが入力されると、このｎバイトの被検索データＤＸのハッシュ値ＨＴを計算する。計算して得られたハッシュ値ＨＴを前記検索データテーブルＴＤのインデックスとして、前記検索タグテーブルＴＴから同ハッシュ値ＨＴと一致するグループの検索データＤＳの先頭ポインタＰを獲得する。獲得した先頭のポインタＰに基づいて、そのグループに属する検索データＤＳを検索する。
【０００９】
グループに属する検索データＤＳと、被検索データＤＸとが一致すれば、検索一致となって検索が終了する。
【００１０】
このように、ハッシュ検索は、被検索データＨＴを所定桁数の素数で割り算した余りをハッシュ値としたことから、検索候補を少なくでき、検索回数も減少し検索時間の短縮を図ることができる点で優れている。
【００１１】
ところで、このハッシュ検索において、前記割り算の代わりにＣＲＣ（ＣｙｃｌｉｃＲｅｄｕｎｄａｎｃｙ　Ｃｈｅｃｋ）計算を用いる方法もある。ＣＲＣ計算は、ビット系列の割り算に相当することから、割り算と同じ性質を示すからである。そこで、通信装置においては、誤り訂正のために用いられるＣＲＣ符号器を備えていることから、このＣＲＣ符号器を用いたハッシュ検索が行なわれている。
【００１２】
ところで、実際に、ハッシュ検索する際、被検索データＤＸは、複数のデータフィールドからなる入力データ（通信フレーム）の一部分に含まれている。そのため、その被検索データＤＸの部分のＣＲＣ値（ハッシュ値）を計算する必要がある。
【００１３】
例えば、図５に示すように、ｎビットの入力データＤについて、先頭ビット（ＬＳＢ）から（ｋ１−１）ビット目までの領域のデータＤ１と先頭ビットから数えて（ｋ２＋１）ビット目から最終ビット（ＭＳＢ）までの領域のデータＤ２とを被検索データＤＸとする。この被検索データＤＸのＣＲＣ値（ハッシュ値）を求める場合、ＣＲＣの線形性を利用して、以下のように計算する。
【００１４】
先ず、ｎビットの入力データＤについてのＣＲＣ値（ハッシュ値）を計算する。また、ｋ１ビット目からｋ２ビット目までの領域（マスク領域）のデータＤ３のＣＲＣ値（ハッシュ値）を求める。このとき、ｎビット（全領域）のデータＤのＣＲＣ値をＣＲＣｎとし、ｋ１ビット目からｋ２ビット目までのマスク領域のデータＤ３のＣＲＣ値をＣＲＣｍとし、前記被検索データＤＸのＣＲＣ値（ハッシュ値）をＣＲＣｘとしたとき、以下の計算で求めることができる。
【００１５】
ＣＲＣｘ＝（ＣＲＣｎ）ＸＯＲ（ＣＲＣｍ）
但し、「ＸＯＲ」は排他的論理和
このとき、データＤ３のＣＲＣ値（＝ＣＲＣｍ）の計算は、ＣＲＣ符号器での計算において、先頭ビットから（ｋ１−１）ビット目まではデータが「０」なので、ＣＲＣ計算を行なう必要がなく、直ちにｋ１ビット目のデータを入力してＣＲＣ計算を行なう。しかしながら、ｋ２ビット目までのＣＲＣ計算しても、引き続いて（ｋ２＋１）ビットから最終ビットまでの「０」のデータを入力してＣＲＣ計算を行なう必要がある。「０」のデータであっても通常のデータと同じ演算量が必要なため、ＣＲＣｍの計算に時間がかかるという問題があった。
【００１６】
そこで、ｋ１ビットからｋ２ビットまでの途中のＣＲＣ値に対して（ｋ２＋１）ビット目から最終ビットまでの「０」を入力した時の、値を予め計算しておく。そして、種々の途中までのＣＲＣ値に対して計算した結果をテーブル化し、そのテーブルを使用してマスク領域におけるデータＤ３のＣＲＣ値（＝ＣＲＣｍ）を求める方法が考えられる。しかしながら、この方法では高速化が図れるが、例えば、マスク領域のビット数が大きい場合、パターン数が膨大となり大きなデータテーブルが必要となる。
【００１７】
また、ガロア体の掛け算の原理を利用すること、即ち、ガロア符号器において、一つシフトさせることはガロア体の要素を１つ掛けることと同じあることから、「０」の数の次数のガロア体の要素を積（掛け算）とすることで計算することができること知られている。マスク領域のビット数が固定であって「０」の数も固定の場合、ガロア体の要素を１つ用意しておくだけで対応できる点で有利である。
【００１８】
ガロア体ＧＦ（２ｒ）は、計算法則を持った有限な数の集合体であって、ｒ＝４とすると、そのガロア体の元（素数）の数は、１６（＝２ｒ）個となる。そして、その非零各元は、
α０，α１，α２，α３，…………………，α１４
で表される。そして、前記各元の値は１以上１５以下の整数と１対１に対応している。
【００１９】
ガロア体は、乗除算をはじめとする四則演算も全て完結するようになっている。例えば、α２×α３＝α５、または、α１０×α９＝α１９＝α４となる。なお、α４の４は、１９を１５で割ったときの余りの数である。さらに、加減算は、ベクトル表現の排他的論理和（ＸＯＲ）で行なうことができる。
【００２０】
ガロア体の掛け算の一例を以下に説明する。例えば、ガロア体の元（要素）であるα６とα７の積（掛け算）は、以下のように展開することができる。
【００２１】
2004094871.tif 000003
図６は、そのガロア体掛け算器の一例を示す論理回路を示す。図６に示すガロア体掛け算器は、ビットパターンの組合わせの掛け算、即ち、積（ＡＮＤ）計算を行なう第１の演算部５１と、第１の演算部５１によって得られた演算結果についてそのビット単位の排他的論理和（ＸＯＲ）計算を行なう第２の演算部５２とからなる。
【００２２】
そして、この掛け算器を使って前記図５で示したマスク領域のデータＤ３のＣＲＣ値（＝ＣＲＣｍ）を計算する場合、第１レジスタ５３に、ｋ１ビット目からｋ２ビット目までのデータＤ３について計算した計算途中のＣＲＣ値であるガロア体の要素からなるＮビットのビット列Ｄｉを入力する。一方、第２レジスタ５４に、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットのビット列Ｓｊを入力する。
【００２３】
第１レジスタ５３に入力されたビット列Ｄｉと第２レジスタ５４に入力されたビット列Ｓｊは、第１の演算部５１に出力される。第１の演算部５１に設けられた多数のアンドゲート回路５１ａにおいて、ビット列Ｄｉの各ビット毎に、ビット列Ｓｊの各ビットに対してアンド計算を行なう。この時、各組み合わせの計算が同時に実行できるように、組合わせの数だけアンドゲート回路５１ａが設けられている。第１の演算部５１の各アンドゲート回路５１ａで得られた結果は、第２の演算部５２に出力される。第２の演算部５２は、多数の排他的論理和ゲート回路（ＸＯＲ回路）５２ａからなり、各ＸＯＲ回路５２ａにて全てのビットパターンについて排他的論理和をすることにとって出力レジスタ５５にデータＤ３のＣＲＣ値（＝ＣＲＣｍ）が出力される。
【００２４】
しかしながら、演算速度は高速になるが、アンド計算を行なう際の全ての組み合わせの数（Ｎ２個）だけアンドゲート回路５１ａが必要となり、回路規模が非常に大きくなる。
【００２５】
そこで、回路規模を小さく構成することができるガロア体掛け算器を図７に示す。図７において、このガロア体掛け算器は、入力レジスタ６１、シフトレジスタ６２、アンドゲート回路６３、排他的論理和ゲート回路６４、及び、ガロア符号器６５を備えている。
【００２６】
今、ガロア符号器６５のガロア符号器レジスタ５３ａが「０」に初期化されている状態で、入力レジスタ６１に、前記図５で示したマスク領域のｋ１ビットからｋ２ビットまでのデータＤ３について計算した計算途中のＣＲＣ値であるガロア体の要素からなるＮビットのビット列Ｄｉを入力する。又、シフトレジスタ６２に、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットのビット列Ｓｊを入力する。
【００２７】
そして、シフトレジスタ６２の最上位ビット（ＭＳＢ）が「１」であるとき、排他的論理和ゲート回路６４において、入力レジスタ６１の内容（ビット列Ｄｉ）とガロア符号器レジスタ６５ａの内容ｇとを排他的論理和の計算、すなわち、
ｇ＝ｇＸＯＲ（Ｄｉ×（シフトレジスタ６２のＭＳＢ））
但し、「×」は掛け算（Ｄｉ各ビットとのアンド演算）
を行い、その結果を同ガロア符号器６５に入力する。
【００２８】
そして、ガロア符号器レジスタ６５ａの内容ｇを一回右（最上位側）に１ビットシフトする。又、シフトレジスタ６２の内容（ビット列Ｓｊ）も同様に一回右にシフトする。そして、シフトレジスタ６２の内容を一回右に１ビットシフトすることによって、同シフトレジスタ６２の新たなＭＳＢが「１」であれば、前記入力レジスタ６１の内容と前記ガロア符号器レジスタ６５ａの内容ｇとを排他的論理和の計算、すなわち、
ｇ＝ｇＸＯＲ（Ｄｉ×（シフトレジスタ６２のＭＳＢ））
を行い、その結果を同ガロア符号器６５に入力する。そして、ガロア符号器６５の内容を一回右（最上位側）に１ビットシフトするとともに、シフトレジスタ６２も同様に一回右に１ビットシフトする。
【００２９】
そして、この計算を、シフトレジスタ６２に初期セットした時に最下位ビット（ＬＳＢ）のビットがＭＳＢになって上記計算が行なわれるまで繰り返す。
【００３０】
そして、最後にガロア符号器６５にて得られたガロア符号器レジスタ６５ａの内容ｇ、すなわち、
ｇ＝ｇＸＯＲ（Ｄｊ×（シフトレジスタ６２のＭＳＢ））
がデータＤ３のＣＲＣ値（＝ＣＲＣｍ）となり出力される。
【００３１】
このガロア掛け算器は、図６で説明したガロア掛け算器に比べて最大（Ｎ−１）回のシフト動作が加わる分だけ演算速度は劣るものの、回路規模を大幅に小さくできる。
【００３２】
【発明が解決しようとする課題】
このように、ガロア符号器を用いて、上記ＣＲＣ値（＝ＣＲＣｍ）を求めることができるが、ＣＲＣ符号器は「０」を入力して右に一回シフトさせればガロア符号器と同じになることから、このガロア符号器をＣＲＣ符号器に置き換えて実施することも可能である。
【００３３】
しかしながら、ガロア符号器６５は１ビット右にシフトする毎に、符号器を初期化しなければならない。通常、ＣＲＣ符号器は、一度レジスタを初期化した後は、データを入力しながらＮビット単位（又は８ビット単位）でシフトするのが一般的であるので、そのままでは使用することができなかった。
【００３４】
本発明は、上記問題点を解消するためになされたものであって、その目的はＣＲＣ符号器を使ったガロア掛け算を可能することによって回路規模を小さくできるガロア体掛け算器及び通信装置を提供するにある。
【００３５】
【課題を解決するための手段】
請求項１に記載の発明は、第１レジスタに入力されたガロア体の要素からなるＮビットの第１ビット列と、第２レジスタに入力されたガロア体の要素からなるＮビットの第２ビット列とのガロア体掛け算を行なうガロア体掛け算器において、Ｎビットの排他的論理和計算の結果を入力しその時の最上位ビットを出力しながら最上位ビット側に１ビットシフトするシフトレジスタと、前記Ｎビットの第２ビット列の最上位ビットから順番に１ビットずつ、前記Ｎビットの第１ビット列との間で順番に掛け算するアンドゲート回路と、前記アンドゲート回路からの演算結果と前記シフトレジスタの内容との間で排他的論理和計算を行ないその計算結果を前記シフトレジスタに入力する第１排他的論理和ゲート回路と、前記シフトレジスタからの最上位ビットを順次入力しＣＲＣ演算するＣＲＣ符号器と、前記ＣＲＣ符号器の内容と前記シフトレジスタの内容との間で排他的論理和計算を行なう第２排他的論理和ゲート回路とを備えてことを要旨とする。
【００３６】
請求項２に記載の発明は、第１レジスタに入力されたガロア体の要素からなるＮビットの第１ビット列と、第２レジスタに入力されたガロア体の要素からなるＮビットの第２ビット列とのガロア体掛け算を行なうガロア体掛け算器において、前記Ｎビットの第１ビット列に対して、前記第２ビット列の各位のビット毎にそれぞれ掛け算を行なう第１の回路部と、前記第１の回路部で各位のビット毎に行なった前記Ｎビットの第１ビット列に対する各計算結果について、それぞれ同一の位同士のビットとの間で排他的論理和計算を行ない２Ｎビットの計算結果を生成する第２の回路部と、前記第２の回路部で行なった、２Ｎビットの計算結果を入力する第３レジスタと、前記第３レジスタに入力された２Ｎビットの演算結果の上位Ｎビットを順次入力しＣＲＣ計算を行なうＣＲＣ符号器と、前記ＣＲＣ符号器のＣＲＣ計算結果と、前記第３レジスタに入力された２Ｎビットの演算結果の下位Ｎビットとの間で排他的論理和計算を行なう排他的論理和ゲート回路とを備えたことを要旨とする。
【００３７】
請求項３に記載の発明は、請求項１又は２に記載のガロア体掛け算器において、Ｎビットの第１ビット列は、ＣＲＣ計算で求められたガロア体の要素を示すＮビットのビット列であり、前記Ｎビットの第２ビット列は、「０」の数の次数のガロア体の要素を示すＮビットのビット列であることを要旨とする。
【００３８】
請求項４に記載の発明は、請求項３に記載のガロア体掛け算器において、Ｎビットの第１ビット列は、予め定められたｋ１ビットからｋ２ビットの範囲のデータ列をＣＲＣ計算した結果得られたガロア体の要素を示すＮビットのビット列であり、前記Ｎビットの第２ビット列は、前記ｋ２ビットの次のビットから最終ビットまでのデータ列を全て「０」とし、その「０」の数の次数のガロア体の要素を示すＮビットのビット列であることを要旨とする。
【００３９】
請求項５に記載の発明は、請求項１乃至４項のいずれか１つに記載のガロア体掛け算器を実装した通信装置を要旨とする。
【００４０】
請求項６に記載の発明は、請求項５に記載の通信装置において、通信装置の信号処理装置に設けられた本来のＣＲＣ計算を行なうためのＣＲＣ符号器を、前記ガロア体掛け算を行なうガロア体掛け算器のＣＲＣ符号器を兼用することをその要旨とする。
【００４１】
（作用）
請求項１に記載の発明によれば、第２レジスタからのＮビットの第２ビット列について、最上位ビットから順番に１ビットずつ出力されると、アンドゲート回路はその１ビットと第１レジスタに入力されているＮビットの第１ビット列との間で順番に掛け算し第１排他適論理和ゲート回路に出力する。第１排他的論理和ゲート回路は、前記アンドゲート回路の掛け算結果とシフトレジスタに先に入力した内容との間で排他的論理和計算を行ないその計算結果をシフトレジスタに入力する。シフトレジスタに入力された内容の最上位ビットから順番にＣＲＣ符号器に出力し、ＣＲＣ符号器においてＣＲＣ演算させる。そして、第２排他的論理和ゲート回路が、ＣＲＣ符号器のＣＲＣ演算結果の内容と前記シフトレジスタの内容との間で排他的論理和計算を行なうことにより、ガロア体の要素からなるＮビットの第１ビット列と第２ビット列とのガロア体掛け算の結果が得られる。従って、ＣＲＣ符号器を用いたガロア体掛け算が可能となる。
【００４２】
請求項２に記載の発明によれば、第１の回路部がＮビットの第１ビット列に対して、前記第２ビット列の各位のビット毎にそれぞれ掛け算を行なうと、第２の回路部は各位のビット毎に行なった前記Ｎビットの第１ビット列に対する各計算結果について、それぞれ同一の位同士のビットとの間で排他的論理和計算を行ない２Ｎビットの計算結果を生成して第３レジスタに入力する。第３レジスタに入力された２Ｎビットの演算結果のうち上位Ｎビットが、ＣＲＣ符号器に順次出力され、ＣＲＣ符号器においてＣＲＣ計算が行なわれる。そして、排他的論理和ゲート回路がＣＲＣ符号器のＣＲＣ演算結果の内容と前記第３レジスタに入力された２Ｎビットの演算結果のうち下位Ｎビットとの間で排他的論理和計算を行なうことにより、ガロア体の要素からなるＮビットの第１ビット列と第２ビット列とのガロア体掛け算の結果が得られる。従って、ＣＲＣ符号器を用いたガロア体掛け算が可能となる。
【００４３】
請求項３に記載の発明によれば、ＣＲＣ計算で求められたガロア体の要素を示すＮビットのビット列と、「０」の数の次数のガロア体の要素を示すＮビットのビット列とのガロア体掛け算の結果が得られる。
【００４４】
請求項４に記載の発明によれば、予め定められたｋ１ビットからｋ２ビットの範囲のデータ列をＣＲＣ計算した結果得られたガロア体の要素を示すＮビットのビット列と、ｋ２ビットの次のビットから最終ビットまでのデータ列を全て「０」とし、その「０」の数の次数のガロア体の要素を示すＮビットのビット列とのガロア体掛け算の結果が得られる。
【００４５】
請求項５に記載の発明によれば、ＣＲＣ符号器を用いたガロア体掛け算が可能となる。
【００４６】
請求項６に記載の発明によれば、ＣＲＣ符号器を用いたガロア体掛け算が回路規模を大きくすることなく可能となる。
【００４７】
【発明の実施の形態】
（第１実施形態）
以下、本発明を具体化した第１実施形態を図１に従って説明する。図１はＣＲＣ符号器を使用したガロア体掛け算器１を説明するためのブロック回路図を示す。尚、説明の便宜上、前記図５で示したマスク領域のｋ１ビットからｋ２ビットまでのデータＤ３におけるＣＲＣ値（＝ＣＲＣｍ）を計算する場合を例として説明する。
【００４８】
図１において、ガロア体掛け算器１は、大きく分けて、シフト排他的論理和回路部２、ＣＲＣ符号器３及び第２排他的論理和ゲート回路としての排他的論理和ゲート回路４とから構成されている。シフト排他的論理和回路部２は、第１レジスタとしての入力レジスタ１０、第２レジスタとしての第１シフトレジスタ１１、第２シフトレジスタ１２、アンドゲート回路１３及び第１排他的論理和ゲート回路としての排他的論理和ゲート回路１４を有している。
【００４９】
入力レジスタ１０は、図５で示すマスク領域のｋ１ビット目からｋ２ビット目までのデータＤ３について計算した計算途中のＣＲＣ値であるガロア体の要素からなるビット列Ｄｉが入力される。この第１ビット列としてのビット列Ｄｉは、本実施形態ではＮビットのビット列とする。入力レジスタ１０は、この入力されたビット列Ｄｉをアンドゲート回路１３に出力するようになっている。
【００５０】
第１シフトレジスタ１１は、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットの第２ビット列としてのビット列Ｓｊが入力される。第１シフトレジスタ１１は、その時の最上位ビット（ＭＢＳ）の内容を前記アンドゲート回路１３に出力するようになっている。又、第１シフトレジスタ１１は、最上位ビットの内容をアンドゲート回路１３に出力すると、同シフトレジスタ１１の内容ｓ（ビット列Ｓｊ）を一回右（最上位ビット側）に１ビットシフトし新たな最上位ビット（ＭＳＢ）を生成するようになっている。
【００５１】
アンドゲート回路１３は、前記入力レジスタ１０の内容ｄ（Ｎビットのビット列Ｄｉ）と前記第１シフトレジスタ１１から出力される最上位ビット（ＭＳＢ）の内容との間で掛け算を行なう。この計算は、第１シフトレジスタ１１に初期セットした時に最下位ビット（ＬＳＢ）のビットがＭＳＢになって上記計算が行なわれるまで繰り返す。そして、アンドゲート回路１３は、第１シフトレジスタ１１から出力されたＭＳＢが「１」であるとき、前記入力レジスタ１０の内容を排他的論理和ゲート回路１４に出力する。アンドゲート回路１３は、第１シフトレジスタ１１から出力されたＭＳＢが「０」であるとき、前記入力レジスタ１０の内容ｄを排他的論理和ゲート回路１４に出力しないようになっている。この操作によって掛け算演算を行なっている。
【００５２】
排他的論理和ゲート回路１４は、前記第１シフトレジスタ１１から出力されたＭＳＢが「１」であるとき、入力レジスタ１０の内容ｄと第２シフトレジスタ１２に内容ｙとの間で排他的論理和の演算を行なう。そして、その排他的論理和の演算結果を第２シフトレジスタ１２に出力する。
【００５３】
つまり、第２シフトレジスタ１２には、
ｙ＝ｙＸＯＲ（ｄ×（第１シフトレジスタ１１のＭＳＢ））
が入力されるようになっている。
【００５４】
第２シフトレジスタ１２は、前記排他的論理和ゲート回路１４よる排他的論理和の演算結果ｙを入力すると、その最上位ビットの内容をＣＲＣ符号器３に出力するようになっている。又、第２シフトレジスタ１２は、最上位ビットの内容をＣＲＣ符号器３に出力すると、同シフトレジスタ１２の内容ｙを一回右（最上位ビット側）に１ビットシフトし新たな最上位ビット（ＭＳＢ）を生成するようになっている。
【００５５】
この動作は、前記第１シフトレジスタ１１に初期セットした時の最下位ビット（ＬＳＢ）の１つ上位のビットがＭＳＢになって前記排他的論理和ゲート回路１４よる排他的論理和の演算結果ｙが入力されるまで繰り返される。又、第２シフトレジスタ１２は、シフトした後の内容ｙを前記排他的論理和ゲート回路１４に出力するようになっている。
【００５６】
ＣＲＣ符号器３は、そのＣＲＣ符号器レジスタ３ａに前記第２シフトレジスタ１２の最上位ビット（ＭＳＢ）を入力し、その入力に応答してそのときのＮビットの内容ｇについて１回シフト動作を行なう。従って、ＣＲＣ符号器３は、第２シフトレジスタ１２からＭＳＢが入力される毎に１回シフト動作を繰り返す。
【００５７】
ＣＲＣ符号器レジスタ３ａのＮビットの内容ｇは、排他的論理和ゲート回路４に出力される。排他的論理和ゲート回路４は、ＣＲＣ符号器レジスタ３ａのＮビットの内容ｇと前記第２シフトレジスタ１２の内容ｇとの間で排他的論理和を求め、その演算結果Ｇ（＝ｇＸＯＲｙ）を出力するようになっている。
【００５８】
次に、上記のように構成したガロア体掛け算器１の作用について説明する。
【００５９】
今、ＣＲＣ符号器３のＣＲＣ符号器レジスタ３ａが「０」に初期化されている状態で、入力レジスタ１０に、前記図５で示したマスク領域のｋ１ビットからｋ２ビットまでのデータＤ３について計算した計算途中のＣＲＣ値であるガロア体の要素からなるＮビットのビット列Ｄｉを入力する。又、第１シフトレジスタ１１に、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットのビット列Ｓｊを入力する。さらに、第２シフトレジスタ１２の内容ｙを「０」に初期化する。
【００６０】
この状態において、第１シフトレジスタ１１のＭＢＳがアンドゲート回路１３に出力され、同アンドゲート回路１３において、第１シフトレジスタ１１のＭＢＳと入力レジスタ１０の内容ｄとの間で掛け算が行なわれてその結果（＝ｄ×（第１シフトレジスタ１１のＭＳＢ）が次段の排他的論理和ゲート回路１４に出力される。
【００６１】
このとき、第１シフトレジスタ１１のＭＳＢの内容が「０」の場合には、演算が行なわれない。そして、第１シフトレジスタ１１のＭＳＢの内容が「１」の場合に、掛け算は行なわれその結果が排他的論理和ゲート回路１４において演算に供される。
【００６２】
排他的論理和ゲート回路１４は、このアンドゲート回路１３の演算結果とその時の第２シフトレジスタ１２の内容ｙとの間で排他的論理和を求める。その排他的論理和の結果を第２シフトレジスタ１２に新たな内容ｙとして入力する。
【００６３】
第２シフトレジスタ１２に新たな内容ｙが入力されると、その内容ｙのＭＳＢの内容がＣＲＣ符号器３に出力される。
【００６４】
ＣＲＣ符号器３は、第２シフトレジスタ１２のＭＳＢの内容が入力されると、その入力に応答して１回シフト動作してＣＲＣ符号器レジスタ３ａに新たなＮビットの内容ｇを生成することになる。
【００６５】
ＣＲＣ符号器３のシフト動作が行なわれると、第１及び第２シフトレジスタ１１，１２がそれぞれ右に１ビットシフト動作を行い、アンドゲート回路１３、排他的論理和ゲート回路１４、第２シフトレジスタ１２及びＣＲＣ符号器３等が前記と同様な動作を繰り返す。つまり、第１シフトレジスタ１１に初期セットした時の最下位ビット（ＬＳＢ）の１つ上位のビットがＭＳＢになって前記排他的論理和ゲート回路１４よる排他的論理和の演算結果ｙが入力されるまで繰り返される。従って、ＣＲＣ符号器３は、排他的論理和の演算結果ｙが第２シフトレジスタ１２に入力される毎にそのＭＳＢを入力してシフト動作を繰り返す。
【００６６】
そして、最下位ビット（ＬＳＢ）のビットがＭＳＢになって前記排他的論理和ゲート回路１４よる排他的論理和の演算結果ｙが得られる。その結果ｙが第２シフトレジスタ１２に入力される。第２シフトレジスタ１２の内容ｙは、排他的論理和ゲート回路４に出力される。排他的論理和ゲート回路４は、この第２シフトレジスタ１２の内容ｙとその時のＣＲＣ符号器レジスタ３ａのＮビットの内容ｇとの間で排他的論理和を求める。そして、この演算結果Ｇ（＝ｇＸＯＲｙ）をＣＲＣ値（＝ＣＲＣｍ＝Ｄｉ×Ｓｊ）として出力する。
【００６７】
つまり、第２シフトレジスタ１２を設け、第２シフトレジスタ１２において、その時々で「０」に初期化、即ち、ｙ＝ｙＸＯＲ（ｄ×第１シフトレジスタ１１のＭＢＳ）の演算を第１シフトレジスタ１１の内容ｓをシフトさせながら行ない、第２シフトレジスタ１２のＭＢＳを順次ＣＲＣ符号器３に入力する。その結果、ガロア符号器を用いた掛け算と同じになる。但し、ＣＲＣ符号器３に、直接第２シフトレジスタ１２の内容ｙ（＝ｙＸＯＲ（ｄ×第１シフトレジスタ１１のＭＢＳ））を入力していないため、（Ｎ−１）回のシフト動作を行なった後に、第２シフトレジスタ１２の内容ｙとＣＲＣ符号器レジスタ３ａの内容ｇとの間で排他的論理和をとっている。
【００６８】
このように本実施形態において、ＣＲＣ符号器３の前段にシフト排他的論理和回路部２を設けたことにより、ガロア符号器と同様なガロア体掛け算を行うことができる。従って、回路規模を大きくすることなくＣＲＣ値（＝ＣＲＣｍ＝Ｄｉ×Ｓｊ）を求めることができる。
【００６９】
しかも、第１シフトレジスタ１１に入力されるデータは、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットのビット列Ｓｊが入力される。従って、ＣＲＣ符号器単独で、（ｋ２＋１）ビット目から最終ビットまでの「０」の数だけ、「０」を入力させてシフト動作させてＣＲＣ値（＝ＣＲＣｍ）を求める場合に比べて高速にＣＲＣ値（＝ＣＲＣｍ＝Ｄｉ×Ｓｊ）を求めることができる。
（第２実施形態）
次に、本発明を具体化した第２実施形態を図２に従って説明する。図２はＣＲＣ符号器を使用したガロア体掛け算器２１を説明するためのブロック回路図を示す。尚、説明の便宜上、前記図５で示したマスク領域のｋ１ビットからｋ２ビットまでのデータＤ３におけるＣＲＣ値（＝ＣＲＣｍ）を計算する場合を例として説明する。
【００７０】
図２において、ガロア体掛け算器２１は、大きく分けて、シフト排他的論理和回路部２２、ＣＲＣ符号器２３及び排他的論理和ゲート回路２４とから構成されている。シフト排他的論理和回路部２２は、Ｎビットの第１レジスタ３１、Ｎビットの第２レジスタ３２、２Ｎビットのシフトレジスタ３３、第１の回路部３４及び第２の回路部３５を有している。
【００７１】
第１レジスタ３１は、図５で示すマスク領域のｋ１ビット目からｋ２ビット目までのデータＤ３について計算した計算途中のＣＲＣ値であるガロア体の要素からなるビット列Ｄｉが入力される。この第１ビット列としてのビット列Ｄｉは、本実施形態ではＮビットのビット列とする。第２レジスタ３２は、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットの第２ビット列としてのビット列Ｓｊが入力される。
【００７２】
第１の回路部３４は、前記第２レジスタ３２のビット列Ｓｊのビット数（Ｎビット）と対応するＮ個の組からなり、その各組には前記第１レジスタ３１のビット列Ｄｉのビット数（Ｎビット）に対応してそれぞれＮ個のアンドゲート回路３４ａから構成されている。従って、第１の回路部３４は、Ｎ２個のアンドゲート回路３４ａを有している。
【００７３】
そして、各組のＮ個のアンドゲート回路３４ａは、その組毎に、前記第２レジスタ３２に入力されたＮビットからなるビット列Ｓｊの対応するビットデータがそれぞれ入力される。又、各組のＮ個のアンドゲート回路３４ａは、それぞれ前記第１レジスタ３１のＮビットからなるビット列Ｄｉの対応するビットデータが入力される。
【００７４】
つまり、例えば、第２レジスタ３２に入力されているビット列Ｓｊの最下位ビット（ＬＳＢ）を入力する組（以下、第１組という）のＮ個のアンドゲート回路３４ａは、その最下位ビット（ＬＳＢ）と第１レジスタ３１に入力されているビット列Ｄｉのそれぞれ対応するビットデータとを、それぞれ掛け算することになる。
【００７５】
因みに、第２レジスタ３２に入力されたビット列Ｓｊの最上位ビット（ＭＳＢ）を入力する組（以下、第Ｎ組という）のＮ個のアンドゲート回路３４ａは、その最上位ビット（ＭＳＢ）と前記第１レジスタ３１に入力されているビット列Ｄｉのそれぞれ対応するビットデータとを、それぞれ掛け算することになる。
【００７６】
そして、第１の回路部３４の第１〜第Ｎ組の各アンドゲート回路３４ａが演算した演算結果は、第２の回路部３５に出力される。
【００７７】
第２の回路部３５は、前記シフトレジスタ３３の入力するビット数（２Ｎビット）の数に対応した数の出力端子を有し、その各出力端子はシフトレジスタ３３のビットにそれぞれ接続されている。そして、第２の回路部３５は、シフトレジスタ３３の最下位ビット（ＬＳＢ）に、前記第１組のビット列Ｄｉの最下位ビット（ＬＳＢ）とビット列Ｓｊの最下位ビット（ＬＳＢ）との間で演算を行なうアンドゲート回路３４ａからの演算結果を入力する。又、第２の回路部３５は、シフトレジスタ３３の最上位ビット（ＭＳＢ）に、「０」のデータを入力する。さらに、第２の回路部３５は、シフトレジスタ３３の最上位ビット（ＭＳＢ）より１ビット下位（（２Ｎ−１）ビット目）のビットに対して、前記第Ｎ組のビット列Ｄｉの最上位ビット（ＭＳＢ）とビット列Ｓｊの最上位ビット（ＭＳＢ）との間で演算を行なうアンドゲート回路３４ａからの演算結果を入力する。
【００７８】
又、第２の回路部３５は、シフトレジスタ３３の最下位ビットより１ビット上位（２ビット目）のビットから最上位ビットより２ビット下位（（２Ｎ−２）ビット目）のビットまでの各ビットに対応して、排他的論理和ゲート回路３５ａを有している。そして、各排他的論理和ゲート回路３５ａは、その対応するシフトレジスタ３３の各ビットに演算結果をそれぞれ入力するようになっている。
【００７９】
詳述すると、シフトレジスタ３３の２ビット目に対応する排他的論理和ゲート回路（以下、第１ゲート回路という）３５ａは、前記第１組と第２組のそれぞれ所定のアンドゲート回路３４ａからの演算結果を入力する。シフトレジスタ３３の３ビット目に対応する排他的論理和ゲート回路（以下、第２ゲート回路という）３５ａは、第１組〜第３組のそれぞれ所定のアンドゲート回路３４ａからの演算結果を入力する。シフトレジスタ３３の４ビット目に対応する排他的論理和ゲート回路（以下、第３ゲート回路という）３５ａは、第１組〜第４組のそれぞれ所定のアンドゲート回路３４ａからの演算結果を入力する。
【００８０】
このように、排他的論理和ゲート回路３５ａは、シフトレジスタ３３のビットがＮビットになるまで、排他的論理和の演算を行なう組数が１組ずつ増加し、（Ｎ＋１）ビットから（２Ｎ−２）ビットまで排他的論理和ゲート回路３５ａは、排他的論理和の演算を行なう組数が１組ずつ減少するようになっている。従って、シフトレジスタ３３のＮビットに対応する排他的論理和ゲート回路（第Ｎゲート回路）３５ａが、最も多い第１組〜第Ｎ組からそれぞれ所定のアンドゲート回路３４ａからの演算結果を入力する。
【００８１】
各排他的論理和ゲート回路３５ａは、それぞれの複数組の予め定められたアンドゲート回路３４ａからの演算結果を入力し演算を行なう。
【００８２】
詳述すると、２ビットの排他的論理和ゲート回路３５ａは、第１組の第１レジスタ３１の２ビット目の演算を行なうアンドゲート回路３４ａ、及び、第２組の第１レジスタ３１の最下位ビット（１ビット目）の演算を行なうアンドゲート回路３４ａの演算結果について、排他的論理和の演算を行なう。３ビットの排他的論理和ゲート回路３５ａは、第１組の第１レジスタ３１の３ビット目の演算を行なうアンドゲート回路３４ａ、第２組の第１レジスタ３１の２ビット目の演算を行なうアンドゲート回路３４ａ、及び、第３組の第１レジスタ３１の１ビット目の演算を行なうアンドゲート回路３４ａの演算結果について、排他的論理和の演算を行なう。
【００８３】
４ビットの排他的論理和ゲート回路３５ａは、第１組の第１レジスタ３１の４ビット目の演算を行なうアンドゲート回路３４ａ、第２組の第１レジスタ３１の３ビット目の演算を行なうアンドゲート回路３４ａ、第３組の第１レジスタ３１の２ビット目の演算を行なうアンドゲート回路３４ａ、及び、第４組の第１レジスタ３１の１ビット目の演算を行なうアンドゲート回路３４ａの演算結果について、排他的論理和の演算を行なうようになっている。
【００８４】
つまり、第１及び第２の回路部３４，３５は、第１〜第Ｎ組において各Ｎ個のアンドゲート回路３４ａにて得られたＮビットの演算結果について、それぞれ上位の組みに移るほどその組のＮビットの演算結果を下位の組のＮビットの演算結果より１ビット上位にシフトさせる。すなわち、第１〜第Ｎ組のＮビットの演算結果をそれぞれシフトした後、その各ビット（各桁）ごとに排他的論理和の演算を行なう。そして、第１及び第２の回路部３４，３５は、この得られた２Ｎビットの演算結果を、シフトレジスタ３３に入力するようにしたものである。
【００８５】
シフトレジスタ３３は、第２の回路部３５から２Ｎビットの演算結果ｙを入力すると、最上位ビット側に１ビットずつシフトしながらその時の最上位ビット（ＭＳＢ）をＣＲＣ符号器２３に出力するようになっている。このシフト動作は、Ｎ回行なわれるようになっている。従って、シフトレジスタ３３は、第２の回路部３５から入力された２Ｎビットの演算結果ｙの上位Ｎビットを順番にＣＲＣ符号器２３に出力することになる。又、シフトレジスタ３３は、ＣＲＣ符号器２３に上位Ｎビットを出力した後の残りの下位Ｎビットを排他的論理和ゲート回路２４に出力するようになっている。
【００８６】
ＣＲＣ符号器２３は、前記シフトレジスタ３３からの上位Ｎビットのビットデータを順次入力してシフト動作を行なう。
【００８７】
排他的論理和ゲート回路２４は、前記ＣＲＣ符号器レジスタ２３ａの前記Ｎ回シフト動作を行なって得られた演算結果の内容ｇと、前記シフトレジスタ３３の前記下位Ｎビットの内容ｙを入力する。排他的論理和ゲート回路２４は、両内容ｇ，ｙとの間で排他的論理和を求め、その演算結果Ｇ（＝ｇＸＯＲｙ）を出力する。
【００８８】
次に、上記のように構成したガロア体掛け算器２１の作用について説明する。
【００８９】
今、ＣＲＣ符号器レジスタ２３ａが「０」に初期化されている状態で、第１レジスタ３１に、前記図５で示したマスク領域のｋ１ビットからｋ２ビットまでのデータＤ３について計算した計算途中のＣＲＣ値であるガロア体の要素からなるＮビットのビット列Ｄｉを入力する。又、第２レジスタ３２に、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットのビット列Ｓｊを入力する。さらに、シフトレジスタ３３の内容ｙを「０」に初期化する。Ｎビットの内容ｄとＮビットの内容ｓから２Ｎビットのデータ（内容ｙ）を生成しシフトレジスタ３３に入力する。
【００９０】
シフトレジスタ３３は、Ｎ回シフト動作を行い、２Ｎビットの内容ｙの中の上位Ｎビットのビットデータを順番にＣＲＣ符号器２３に入力する。これによって、ＣＲＣ符号器２３は、その上位Ｎビットのビットデータを入力しＮビット分シフト動作する。そして、排他的論理和ゲート回路２４は、シフトレジスタ３３に残った下位Ｎビットのデータ（内容ｙ）と、その時のＣＲＣ符号器レジスタ２３ａの内容ｇとの間で排他的論理和を求める。つまり、排他的論理和ゲート回路２４の演算結果Ｇ（＝ｇＸＯＲｙ）は、ＣＲＣ値（＝ＣＲＣｍ＝Ｄｉ×Ｓｊ）として出力される。
【００９１】
このように第２実施形態においても、ＣＲＣ符号器２３の前段にシフト排他的論理和回路部２２を設けたことにより、ガロア符号器と同様なガロア体掛け算を行うことができる。従って、回路規模を大きくすることなくＣＲＣ値（＝ＣＲＣｍ＝Ｄｉ×Ｓｊ）を求めることができる。
【００９２】
しかも、第２レジスタ３２に入力されるデータは、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットのビット列Ｓｊが入力される。従って、ＣＲＣ符号器単独で、（ｋ２＋１）ビット目から最終ビットまでの「０」の数だけ、「０」を入力させてシフト動作させてＣＲＣ値（＝ＣＲＣｍ）を求める場合に比べて高速にＣＲＣ値（＝ＣＲＣｍ）を求めることができる。
（第３実施形態）
次に、本発明を具体化した第３実施形態を図３に従って説明する。図３はルータ等の通信装置において、前記第２実施形態で説明したガロア体掛け算器２１のシフト排他的論理和回路部２２を実装した信号処理装置の電気的構成を説明するためのブロック回路図を示す。
【００９３】
図３において、信号処理装置４１は、ＡＬＵ４２、レジスタ群４３、ＣＲＣエンジン４４及びシフト排他的論理和回路部２２とから構成され、これらは互いにバスＢ１，Ｂ２を介して信号の授受が行われる。ＡＬＵ４２は、レジスタ群４３と協働して通信にための各種の信号処理のための演算処理を行う。ＣＲＣエンジン４４は、通信装置に入力されてくる入力信号の誤り訂正のためのＣＲＣの演算を実行するエンジンであって、第２実施形態で説明したＣＲＣ符号器２３及び排他的論理和ゲート回路２４と同じＣＲＣ符号器、排他的論理和ゲート回路（図示せず）を備えている。
【００９４】
シフト排他的論理和回路部２２は、第１レジスタ３１、第２レジスタ３２、シフトレジスタ３３、第１の回路部３４及び第２の回路部３５とから構成されている。第１レジスタ３１は、前記Ｎビットのビット列ＤｉがＣＲＣエンジン４４が演算しているＣＲＣ値が入力される。第２レジスタ３２は、前記Ｎビットのビット列Ｓｊが予め用意されたメモリ４５に記憶された各「０」の数の次数のガロア体の要素を示すデータから読み出されて入力される。従って、「０」の数が固定の場合には、１つのビット列Ｓｊが予め用意されたメモリ４５に記憶される。尚、メモリ４５には、前記図４で示した、被検索データＤＸを検索するための、検索タグデーブルＴＴ及び検索データテーブルＴＤも予め記憶されている。
【００９５】
シフトレジスタ３３は、ビット列Ｄｉ，Ｓｊに基づいて演算された２Ｎビットの演算結果ｙの上位Ｎビットを上位ビットから順番に１ビットずつ前記ＣＲＣエンジン４４に出力する。また、シフトレジスタ３３は、上位Ｎビットを上位ビットから順番に前記ＣＲＣエンジン４４に出力した後に２Ｎビットの演算結果ｙの下位Ｎビットを前記ＣＲＣエンジン４４に出力するようになっている。
【００９６】
次に、上記のように構成した信号処理装置４１の作用について説明する。
【００９７】
説明の便宜上、図５で示す入力データＤについて、データＤ３のＣＲＣ値（＝ＣＲＣｍ＝Ｄｉ×Ｓｊ；但し、×は排他的論理和）を求める場合について説明する。
【００９８】
今、信号処理装置４１に入力データＤが入力されると、ＣＲＣエンジン４４が入力されてくる入力データＤのｋ１ビット目のビットデータからＣＲＣに演算を演算開始する。尚、ＣＲＣエンジン４４はこのＣＲＣの演算とともに、入力データＤ全体にＣＲＣの演算を並行して行っている。そして、ｋ２ビット目のビットデータまでのＣＲＣの演算が完了すると、それまでのＣＲＣ値であるＮビットのビット列Ｄｉをシフト排他的論理和回路部２２の第１レジスタ３１に入力する。これと同時に、第２レジスタ３２は、メモリ４５から（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットのビット列Ｓｊが入力される。そして、ビット列Ｄｉ，Ｓｊに基づいて演算された２Ｎビットの演算結果ｙをシフトレジスタ３３に入力する。
【００９９】
次に、ＣＲＣエンジン４４に備えられているＣＲＣ符号器レジスタ４４ａを「０」に初期化する。続いて、このＣＲＣ符号器レジスタ４４ａに対して、シフトレジスタ３３の上位Ｎビットを最上位ビットから順番に１ビットずつ入力する。この上位Ｎビットのビットデータの入力によって、ＣＲＣエンジン４４のＣＲＣ符号器レジスタ４４ａはＮビット分シフトする。そして、シフトレジスタ３３の下位Ｎビットと、符号器レジスタ４４ａの値とを排他的論理和することによって、ＣＲＣｍ＝Ｄｉ×Ｓｊなるガロア体掛け算の結果が得られる。
【０１００】
そして、この得られたデータＤ３のＣＲＣ値（＝ＣＲＣｍ）と、入力データＤ全体のＣＲＣ値（＝ＣＲＣｎ）とを、排他的論理和することによって、被検索データＤＸのＣＲＣ値（＝ＣＲＣｘ＝ＣＲＣ×ＣＲＣｍ）を求めることができる。この被検索データＤＸのＣＲＣ値（＝ＣＲＣｘ）が求められると、信号処理装置４１は、メモリ４５に記憶されている検索タグデーブルＴＴ及び検索データテーブルＴＤを使って、被検索データＤＸに対する検索データＤＳを検索することになる。
【０１０１】
このように、本実施形態のルータ等の通信装置の信号処理装置４１によれば、シフト排他的論理和回路部２２のみ付加し、ＣＲＣエンジン４４に備えられたＣＲＣ符号器をハッシュ検索ために利用するようにしたので、回路規模を大きくすることなく、ＣＲＣのハッシュ検索を行うことができる。
【０１０２】
しかも、ビット列Ｄｉ，Ｓｊを入力した後に行うシフト排他的論理和回路部２２は、ＡＬＵ４２の演算処理に依存しないため、少ない命令サイクルで演算することができる。また、前記実施形態と同様に、短時間でかつ回路規模を大きくすることなくＣＲＣ値を求めることができる。
【０１０３】
また、本実施形態のルータ等の通信装置の信号処理装置４１によれば、シフト排他的論理和回路部２２のみ付加し、ＣＲＣエンジン４４に備えられたＣＲＣ符号器をハッシュ検索ために利用するようにしたので、回路規模を大きくすることなく、ＣＲＣのハッシュ検索を行うことができる。
【０１０４】
尚、本発明の実施形態は、以下のように変更してもよい。
【０１０５】
○上記第３実施形態の信号処理装置４１は、第２実施形態で説明したシフト排他的論理和回路部２２を付加したものであったが、第１実施形態で説明したシフト排他的論理和回路部２を付加してなる信号処理装置に応用してもよい。
【０１０６】
○上記第３実施形態では、ｋ１ビット目からｋ２ビット目までのデータＤ３についてのＣＲＣ値であるビット列Ｄｉは、その時々でＣＲＣエンジン４４がＣＲＣ演算したものであり、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットのビット列Ｓｊは、予めメモリ４５に記憶されたデーから得られたものであった。
【０１０７】
これを、すでに入力データＤ中に、ｋ１ビット目からｋ２ビット目までのデータＤ３についてのＣＲＣ値であるビット列Ｄｉと、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すＮビットのビット列Ｓｊとを、含ませるようにしておく。そして、入力データＤを入力したとき、入力データＤ中のビット列Ｄｉとビット列Ｓｊとを読み出し、直ちに、ビット列Ｄｉとビット列Ｓｊを使って演算を実行するようにしてもよい。
【０１０８】
この場合、ｋ１ビット目からｋ２ビット目までのＣＲＣ演算は行わなく済むとともに、（ｋ２＋１）ビット目から最終ビットまでの「０」の数の次数のガロア体の要素を示すビット列Ｓｊを記憶しておく記憶手段が不要になる。
【０１０９】
【発明の効果】
以上詳述したように、本発明によれば、ＣＲＣ符号器を用いたガロア体の掛け算を行うことのできる効果を有する
【図面の簡単な説明】
【図１】第１実施形態のＣＲＣ符号器を使用したガロア体掛け算器を説明するためのブロック回路図。
【図２】第２実施形態のＣＲＣ符号器を使用したガロア体掛け算器を説明するためのブロック回路図。
【図３】第３実施形態の通信装置の信号処理装置を説明するためのブロック回路図。
【図４】ハッシュ検索を説明するための説明図。
【図５】ハッシュ検索にための被検索データのデータ構造とその求め方を説明するための説明図。
【図６】従来のガロア符号器を使ったガロア体掛け算器を説明するためのブロック回路図。
【図７】同じく従来のガロア符号器を使ったガロア体掛け算器を説明するためのブロック回路図。
【符号の説明】
１，２１…ガロア体掛け算器
２，２２…シフト排他的論理和回路部
３，２３…ＣＲＣ符号器
４，２４…排他的論理和ゲート回路
１０…入力レジスタ
１１…第１シフトレジスタ
１２…第２シフトレジスタ
１３…アンドゲート回路
１４…排他的論理和ゲート回路
３１…第１レジスタ
３２…第２レジスタ
３３…シフトレジスタ
３４…第１の回路部
３４ａ…アンドゲート回路
３５…第２の回路部
３５ａ…排他的論理和ゲート回路
４１…信号処理装置
４２…ＡＬＵ
４３…レジスタ群
４４…ＣＲＣエンジン
４５…メモリ
Ｄｉ…ビット列
Ｓｊ…ビット列
ＴＤ…検索データテーブル
Ｄ３…データ
ｄ、ｇ、ｓ、ｙ　内容
【図１】
2004094871.tif 000004
【図２】
2004094871.tif 000005
【図３】
2004094871.tif 000006
【図４】
2004094871.tif 000007
【図５】
2004094871.tif 000008
【図６】
2004094871.tif 000009
【図７】
2004094871.tif 000010