(57)【要約】【課題】ＣＲＣ符号化またはＣＲＣ符号の誤り検出において、部分剰余計算に必要な剰余テーブルのサイズを削減する。【解決手段】記憶手段５１は、複数の単位情報列の値をインデクスとして、対応する剰余情報列の値をそれぞれ保持する複数の剰余テーブルを記憶する。テーブル引き手段５２は、１回のループ処理で処理される対象情報列を複数の単位情報列に分割して、それぞれの単位情報列の値をインデクスとして上記複数の剰余テーブルを参照し、複数の剰余情報列の値を取得する。計算手段５３は、得られた複数の剰余情報列と、入力情報列のうち未処理部分の先頭情報列との排他的論理和を計算する。そして、テーブル引き手段５２は、得られた排他的論理和の情報列を次回のループ処理における対象情報列として用いて、複数の剰余テーブルの参照を所定回数繰り返す。【選択図】図１
2008011025.tif 000002
【特許請求の範囲】
【請求項１】
入力情報列に対応する多項式を生成多項式で除算したときの剰余を計算する剰余計算装置であって、
複数の単位情報列の値をインデクスとして、対応する剰余情報列の値をそれぞれ保持する複数の剰余テーブルを記憶する記憶手段と、
１回のループ処理で処理される対象情報列を複数の単位情報列に分割して、それぞれの単位情報列の値をインデクスとして前記複数の剰余テーブルを参照し、複数の剰余情報列の値を取得するテーブル引き手段と、
得られた複数の剰余情報列と、前記入力情報列のうち未処理部分の先頭情報列との排他的論理和を計算する計算手段とを備え、
前記テーブル引き手段は、得られた排他的論理和の情報列を次回のループ処理における対象情報列として用いて、前記複数の剰余テーブルの参照を所定回数繰り返すことを特徴とする剰余計算装置。
【請求項２】
前記記憶手段は、Ｎ個の剰余テーブルを記憶し、ｉ番目の剰余テーブルは、単位情報列の長さをｓとし、剰余情報列の長さをＭとし、ｘのｓ−１次の多項式をｐ’（ｘ）としたとき、ｐ’（ｘ）・ｘM+(N-i)sを前記生成多項式で除算して得られた剰余多項式のＭ個の係数を、該単位情報列の値に対応する剰余情報列の値として保持することを特徴とする請求項１記載の剰余計算装置。
【請求項３】
前記計算手段により得られた排他的論理和の情報列を記憶するレジスタ手段をさらに備え、該計算手段は、最後のループ処理において得られた複数の剰余情報列の排他的論理和を、前記入力情報列に対する剰余計算結果として該レジスタ手段に格納することを特徴とする請求項１または２記載の剰余計算装置。
【請求項４】
前記複数の剰余情報列の排他的論理和の情報列を記憶するレジスタ手段をさらに備え、前記計算手段は、前記先頭情報列と該レジスタ手段の情報列の排他的論理和を先頭詰めで計算し、最後のループ処理において得られた複数の剰余情報列の排他的論理和を、前記入力情報列に対する剰余計算結果として該レジスタ手段に格納することを特徴とする請求項１または２記載の剰余計算装置。
【請求項５】
入力情報列に対応する多項式を生成多項式で除算したときの剰余を計算するコンピュータのためのプログラムであって、
複数の単位情報列の値をインデクスとして、対応する剰余情報列の値をそれぞれ保持する複数の剰余テーブルを記憶手段に格納し、
１回のループ処理で処理される対象情報列を複数の単位情報列に分割して、それぞれの単位情報列の値をインデクスとして前記複数の剰余テーブルを参照することで、複数の剰余情報列の値を取得し、
得られた複数の剰余情報列と、前記入力情報列のうち未処理部分の先頭情報列との排他的論理和を計算し、
得られた排他的論理和の情報列を次回のループ処理における対象情報列として用いて、前記複数の剰余テーブルの参照を所定回数繰り返す
処理を前記コンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、巡回冗長検査（ＣＲＣ）符号化またはＣＲＣ符号の誤り検出において、入力情報列の剰余を計算する装置に関する。
【背景技術】
【０００２】
従来のＣＲＣ符号化およびＣＲＣ符号の誤り検出においては、入力ビット列に対応する多項式を生成多項式で除算して剰余を求める、剰余計算が行われる（例えば、下記の特許文献１および２を参照）。Ｋビットの符号ビット列Ｐに対して、Ｍ次の生成多項式Ｇ（ｘ）による剰余計算をｔビットずつの多ビット処理で実現する場合、ビット数ｔの任意のビット列ｐに対する剰余を表すＭビットのビット列Ｒを記録した剰余テーブルが用意される。
【０００３】
この場合、ビット列ｐおよびＲに対応する多項式をそれぞれｐ（ｘ）およびＲ（ｘ）とすると、Ｒ（ｘ）は、ｐ（ｘ）・ｘM をＧ（ｘ）で除算したときの剰余を表す。Ｐ、Ｇ（ｘ）、ｐ、ｐ（ｘ）、Ｒ、およびＲ（ｘ）は、それぞれ次式により定義される。
Ｐ＝ｂ0 ，ｂ1 ，ｂ2 ，．．．，ｂK-1                                   （１）
Ｇ（ｘ）＝ａ0 ・ｘM ＋ａ1 ・ｘM-1 ＋・・・＋ａM ・ｘ0                 （２）
ｐ＝ｂ0 ，ｂ1 ，ｂ2 ，．．．，ｂt-1                                   （３）
ｐ（ｘ）＝ｂ0 ・ｘt-1 ＋ｂ1 ・ｘt-2 ＋ｂ2 ・ｘt-3 ＋・・・＋ｂt-1 ・ｘ0 
＝｛ｂ0 ，ｂ1 ，ｂ2 ，．．．，ｂt-1 ｝                        （４）
Ｒ＝ｒ0 ，ｒ1 ，ｒ2 ，．．．，ｒM-1                                   （５）
Ｒ（ｘ）＝ｒ0 ・ｘM-1 ＋ｒ1 ・ｘM-2 ＋ｒ2 ・ｘM-3 ＋・・・＋ｒM-1 ・ｘ0 
＝｛ｒ0 ，ｒ1 ，ｒ2 ，．．．，ｒM-1 ｝                        （６）
これらのビット列の各ビットは、論理“０”または“１”の値をとる。上記剰余テーブルを使用したｔビットずつの順次処理により、入力ビット列Ｐに対する剰余計算が行われる。
【０００４】
図１５は、このような剰余計算を行う剰余計算装置の構成図である。この剰余計算装置は、メモリ１１、１６、ビット列読出し部１２、ビット分離部１３、ビット結合部１４、テーブル引き部１５、排他的論理和（ＥＯＲ）部１７、およびレジスタ１８を備える。
【０００５】
メモリ１１には、剰余計算対象のＫビットの入力ビット列Ｐが格納され、メモリ１６には、ｐ（ｘ）・ｘM の剰余テーブルＲＴａｂｌｅ［］が格納されている。最初に、入力ビット列Ｐの先頭のＭビットが、Ｒ’としてＭビットのレジスタ１８に格納される。
Ｒ’＝ｒ’0，ｒ’1 ，ｒ’2 ，．．．，ｒ’M-1 
←  ｂ0，ｂ1 ，ｂ2 ，．．．，ｂM-1           （７）
以後、所定回数分、以下のｔビット分の部分剰余計算が繰り返される。
【０００６】
まず、ビット分離部１３は、レジスタ１８の先頭のｔビットｒ’0 ，ｒ’1 ，ｒ’2 ，．．．，ｒ’t-1 を取り出し、テーブル引き部１５は、メモリ１６上のＲＴａｂｌｅ［］のテーブル引きを行い、Ｍビットのテーブル引き結果Ｒを得る。
Ｒ  ←  ＲＴａｂｌｅ［ｒ’0 ，ｒ’1 ，ｒ’2 ，．．．，ｒ’t-1 ］      （８）
ビット列読出し部１２は、メモリ１１から入力ビット列Ｐの続きをｔビット読み出し、そのビット列をｐとして、ビット結合部１４に出力する。
ｐ  ←  ｂ(i-1)t+M，ｂ(i-1)t+M+1，．．．，ｂit+M-1  （ｉ＝１，２，．．．）      （９）
ビット結合部１４は、レジスタ１８の末尾の（Ｍ−ｔ）ビットｒ’t ，ｒ’t+1 ，．．．，ｒ’M-1 にｐを接続し、Ｍビットのビット列Ｒ″を生成する。
Ｒ″  ←  ｒ’t ，ｒ’t+1 ，．．．，ｒ’M-1 ，ｐ
＝  ｒ’t ，ｒ’t+1 ，．．．，ｒ’M-1 ，ｂ(i-1)t+M，ｂ(i-1)t+M+1，．．．，ｂit+M-1
（１０）
ＥＯＲ部１７は、Ｒ″とＲのＥＯＲ（“＋”と表記する）を計算し、計算結果をＲ’としてレジスタ１８に格納する。
Ｒ’  ←  Ｒ＋Ｒ″      （１１）
以上の部分剰余計算を所定回数繰り返した後のＲ’が、入力ビット列Ｐに対する剰余計算結果となる。
【０００７】
図１６は、メモリ１６上のＲＴａｂｌｅ［］の作成方法を示している。この例では、ｐ（ｘ）＝｛ｂ0 ，ｂ1 ，ｂ2 ，．．．，ｂt-1 ｝毎にＲ（ｘ）＝｛ｒ0 ，ｒ1 ，ｒ2 ，．．．，ｒM-1 ｝がテーブル化される。
ＲＴａｂｌｅ［ｂ0 ，ｂ1 ，ｂ2 ，．．．，ｂt-1 ］
＝ＭＯＤ（｛ｂ0 ，ｂ1 ，ｂ2 ，．．．，ｂt-1 ｝・ｘM ，Ｇ（ｘ））      （１２）
ＲＴａｂｌｅ［］の１要素のサイズはＭビットで、要素数は２t である。したがって、テーブル全体のサイズはＭ・２t となる。図１６のＱ（ｘ）は、商の多項式を表す。
【０００８】
図１７は、ＲＴａｂｌｅ［］を用いたｔビット分の処理を示している。Ｐ＝ｂ0 ，ｂ1 ，ｂ2 ，．．．，ｂK-1 の先頭ｔビット分の剰余計算により、処理結果Ｒ’が得られる。
Ｒ’＝ｂ’t，ｂ’t+1 ，．．．，ｂ’t+M-1       （１３）
ＭビットのＲ’は、いわゆるＣＲＣ計算時のＣＲＣレジスタに相当する。このＲ’は、ＲＴａｂｌｅ［］のテーブル引きとＥＯＲ計算により簡単に求めることができる。
Ｒ’（ｘ）＝ＭＯＤ（｛ｂ0 ，ｂ1 ，．．．，ｂt+M-1 ｝，Ｇ（ｘ））
＝ＭＯＤ（｛ｂ0 ，ｂ1 ，．．．，ｂt-1 ｝・ｘM ，Ｇ（ｘ））
＋｛ｂt ，ｂt+1 ，．．．，ｂt+M-1 ｝
＝ＲＴａｂｌｅ［ｂ0 ，ｂ1 ，．．．，ｂt-1 ］
＋｛ｂt ，ｂt+1 ，．．．，ｂt+M-1 ｝
＝｛ｒ0 ，ｒ1 ，．．．，ｒM-1 ｝＋｛ｂt ，ｂt+1 ，．．．，ｂt+M-1 ｝
＝｛ｂ’t ，ｂ’t+1 ，．．．，ｂ’t+M-1 ｝                        （１４）
引き続き処理すべきビット列をＰ’とすると、多項式Ｐ’（ｘ）は次式のようになる。
Ｐ’（ｘ）＝Ｒ’（ｘ）・ｘ(K-1)-(t-M-1) ＋｛ｂt+M ，ｂt+M+1 ，．．．，ｂK-1 ｝
＝｛ｂ’t ，ｂ’t+1 ，．．．，ｂ’t+M-1 ，ｂt+M ，ｂt+M+1 ，．．．，ｂK-1 ｝
（１５）
【０００９】
図１８に示すように、Ｐ’を新たなＰとみなして処理を繰り返すことで、ｎ回の繰り返し処理によりｎ・ｔビット分の剰余が計算される。したがって、Ｋ／ｔ回の繰り返し処理により得られたＲ’（ｘ）が、Ｋビットの入力ビット列Ｐに対する剰余計算結果となる。図１８では、３回の繰り返し処理が示されている。
ＣＲＣ符号化の場合、Ｒ’（ｘ）がパリティビットとして使用され、ＣＲＣ符号の誤り検出の場合、Ｒ’（ｘ）が０以外であれば誤りがあることを示している。
【特許文献１】特開２００５−００６１８８号公報
【特許文献２】国際公開第２００３／０９０３６２号パンフレット
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述した従来の剰余計算では、ｔビットずつの処理に必要な剰余テーブルのサイズがＭ・２t ビットとなる。このため、ｔの値に従ってテーブルサイズが指数関数的に増大するため、ｔをあまり大きく設定することができない。
【００１１】
本発明の課題は、ＣＲＣ符号化またはＣＲＣ符号の誤り検出において、部分剰余計算に必要な剰余テーブルのサイズを削減することである。
【課題を解決するための手段】
【００１２】
図１は、本発明の剰余計算装置の原理図である。図１の剰余計算装置は、記憶手段５１、テーブル引き手段５２、および計算手段５３を備え、入力情報列に対応する多項式を生成多項式で除算したときの剰余を計算する。
【００１３】
記憶手段５１は、複数の単位情報列の値をインデクスとして、対応する剰余情報列の値をそれぞれ保持する複数の剰余テーブルを記憶する。テーブル引き手段５２は、１回のループ処理で処理される対象情報列を複数の単位情報列に分割して、それぞれの単位情報列の値をインデクスとして上記複数の剰余テーブルを参照し、複数の剰余情報列の値を取得する。計算手段５３は、得られた複数の剰余情報列と、入力情報列のうち未処理部分の先頭情報列との排他的論理和を計算する。
【００１４】
そして、テーブル引き手段５２は、得られた排他的論理和の情報列を次回のループ処理における対象情報列として用いて、複数の剰余テーブルの参照を所定回数繰り返す。
入力情報列は、先頭から順番に対象情報列と同じ長さで区切られて、計算手段５１に入力され、計算手段５１は、前回のループ処理で得られた複数の剰余情報列と、入力された未処理の情報列との排他的論理和を計算し、それを対象情報列としてテーブル引き手段５２に出力する。テーブル引き手段５２は、受け取った対象情報列を複数の単位情報列に分割し、各単位情報列の値をインデクスとして各剰余テーブルを参照する。得られた複数の剰余情報列は計算手段５１に出力され、次回のループ処理で使用される。
【００１５】
このようなループ処理の繰り返しにより、前記入力情報列に対する剰余計算結果が求められる。
例えば、後述する図１１の剰余計算装置において、記憶手段５１は、メモリ１０４および１０６に対応し、テーブル引き手段５２は、テーブル引き部１０３および１０５に対応し、計算手段５３は、ＥＯＲ部１０７に対応する。
【００１６】
また、図１２の剰余計算装置において、記憶手段５１は、メモリ２０５、２０７、２０９、および２１１に対応し、テーブル引き手段５２は、テーブル引き部２０４、２０６、２０８、および２１０に対応し、計算手段５３は、ＥＯＲ部２０３および２１２に対応する。
【発明の効果】
【００１７】
対象情報列の長さをｔ、剰余情報列の長さをＭ、対象情報列の分割数をＮ、単位情報列の長さをｓ（＝ｔ／Ｎ）とすると、各剰余テーブルの１要素のサイズはＭビットで、要素数は２s となる。したがって、Ｎ個のテーブル全体のサイズはＮ・Ｍ・２sとなる。Ｎ≧２かつｓ≧２とすると、Ｍ・２s ビットのテーブルをＮ個用意した場合とＭ・２t ビットのテーブルを１個用意した場合の全体のサイズの比率は、次式のようになる。
（Ｎ・Ｍ・２s ）／（Ｍ・２t ）＝Ｎ・２s ／２Ns＜１      （２１）
したがって、従来の剰余テーブルと比較すると、全体としてテーブルサイズを削減することができ、１回のループ処理で処理される対象情報列の長さｔを、大きな値に設定することが可能になる。例えば、ｔ＝３２、Ｎ＝４の場合、ｓ＝８となるから、テーブルサイズは（Ｍ・２s ・Ｎ）／（Ｍ・２t ）＝１／２22に削減される。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照しながら、本発明を実施するための最良の形態を詳細に説明する。
本実施形態の剰余計算装置は、例えば、複数の演算器を有するプロセッサや、メモリ参照にレーテンシサイクルを必要とするプロセッサにより実現される。
【００１９】
そして、ビット数ｔの任意のビット列ｐに対応するｐ（ｘ）・ｘM の剰余をテーブルとして用意する代わりに、ｓ＝ｔ／Ｎなるパラメータを導入して、Ｎ個の剰余テーブルを用意する。このとき、ビット数ｓの任意のビット列ｐ’に対応する多項式をｐ’（ｘ）として、ｐ’（ｘ）・ｘM+(N-1)s，ｐ’（ｘ）・ｘM+(N-2)s，．．．，ｐ’（ｘ）・ｘM+s ，ｐ’（ｘ）・ｘM の剰余を、それぞれテーブルＲＴａｂｌｅ１［］，ＲＴａｂｌｅ２［］，．．．，ＲＴａｂｌｅ（Ｎ−１）［］，ＲＴａｂｌｅＮ［］に登録する。ｐ’およびｐ’（ｘ）は、それぞれ次式により定義される。
ｐ’＝ｂ’0，ｂ’1 ，ｂ’2 ，．．．，ｂ’s-1       （２２）
ｐ’（ｘ）＝ｂ’0 ・ｘs-1 ＋ｂ’1 ・ｘs-2 ＋ｂ’2 ・ｘs-3 ＋・・・＋ｂ’s-1 ・ｘ0 
＝｛ｂ’0 ，ｂ’1 ，ｂ’2 ，．．．，ｂ’s-1 ｝                  （２３）
【００２０】
図２、図３、および図４は、それぞれ剰余テーブルＲＴａｂｌｅ１［］、ＲＴａｂｌｅ２［］、およびＲＴａｂｌｅＮ［］の作成方法を示している。この例では、ｐ’（ｘ）＝｛ｂ’0 ，ｂ’1 ，ｂ’2 ，．．．，ｂ’s-1 ｝毎にＲ（ｘ）＝｛ｒ0 ，ｒ1 ，ｒ2 ，．．．，ｒM-1 ｝がテーブル化される。
ＲＴａｂｌｅ１［ｂ’0 ，ｂ’1 ，ｂ’2 ，．．．，ｂ’s-1 ］
＝ＭＯＤ（｛ｂ’0 ，ｂ’1 ，ｂ’2 ，．．．，ｂ’s-1 ｝・ｘM+(N-1)s，Ｇ（ｘ））
（２４）
ＲＴａｂｌｅ２［ｂ’0 ，ｂ’1 ，ｂ’2 ，．．．，ｂ’s-1 ］
＝ＭＯＤ（｛ｂ’0 ，ｂ’1 ，ｂ’2 ，．．．，ｂ’s-1 ｝・ｘM+(N-2)s，Ｇ（ｘ））
（２５）
ＲＴａｂｌｅＮ［ｂ’0 ，ｂ’1 ，ｂ’2 ，．．．，ｂ’s-1 ］
＝ＭＯＤ（｛ｂ’0 ，ｂ’1 ，ｂ’2 ，．．．，ｂ’s-1 ｝・ｘM ，Ｇ（ｘ））
（２６）
各剰余テーブルの１要素のサイズはＭビットで、要素数は２s となる。したがって、Ｎ個のテーブル全体のサイズはＮ・Ｍ・２s である。
【００２１】
図５は、Ｎ個の剰余テーブルによる剰余計算を示しており、図６、図７、および図８は、それぞれＲＴａｂｌｅ１［］、ＲＴａｂｌｅ２［］、およびＲＴａｂｌｅＮ［］のテーブル引きを示している。
【００２２】
ｔビットのビット列ｐの先頭のｓビットのビット列ｐ1 をインデクスとして、ＲＴａｂｌｅ１［］のテーブル引きを行い、Ｒ1 を取得する。続くｓビットのビット列ｐ2 ，．．．，ｐN も同様にインデクスとして、ＲＴａｂｌｅ２［］，．．．，ＲＴａｂｌｅＮ［］のテーブル引きを行い、それぞれＲ2 ，．．．，ＲN を得る。
ｐ（ｘ）＝ｐ1 （ｘ）・ｘ(N-1)s＋ｐ2 （ｘ）・ｘ(N-2)s＋・・・＋ｐN （ｘ）      （２７）
Ｒ1 （ｘ）＝ＲＴａｂｌｅ１［ｐ1 ］
Ｒ2 （ｘ）＝ＲＴａｂｌｅ１［ｐ2 ］
・・・
ＲN （ｘ）＝ＲＴａｂｌｅ１［ｐN ］      （２８）
そして、次式によりｐ（ｘ）・ｘM の剰余Ｒ（ｘ）を得る。
Ｒ（ｘ）＝Ｒ1 （ｘ）＋Ｒ2 （ｘ）＋・・・＋ＲN （ｘ）      （２９）
【００２３】
図９は、Ｎ個の剰余テーブルを用いたｔビット分の処理を示している。Ｐ＝ｂ0 ，ｂ1 ，ｂ2 ，．．．，ｂK-1 の先頭ｔビット分の剰余計算により、処理結果Ｒ’が得られる。
Ｒ’＝ｂ’t，ｂ’t+1 ，．．．，ｂ’t+M-1       （３０）
このＲ’は、ＲＴａｂｌｅ１［］〜ＲＴａｂｌｅＮ［］のテーブル引きとＥＯＲ計算により簡単に求めることができる。
Ｒ’（ｘ）＝ＭＯＤ（｛ｂ0 ，ｂ1 ，．．．，ｂt-1 ｝・ｘM ，Ｇ（ｘ））
＋｛ｂt ，ｂt+1 ，．．．，ｂt+M-1 ｝
＝Ｒ（ｘ）＋｛ｂt ，ｂt+1 ，．．．，ｂt+M-1 ｝
＝ＲＴａｂｌｅ１［ｂ0 ，ｂ1 ，．．．，ｂs-1 ］
＋ＲＴａｂｌｅ２［ｂs ，ｂs+1 ，．．．，ｂ2s-1］＋・・・
＋ＲＴａｂｌｅＮ［ｂ(N-1)s，ｂ(N-1)s+1，．．．，ｂNs-1］
＋｛ｂt ，ｂt+1 ，．．．，ｂt+M-1 ｝                        （３１）
引き続き処理すべきビット列をＰ’とすると、多項式Ｐ’（ｘ）は次式のようになる。
Ｐ’（ｘ）＝Ｒ’（ｘ）・ｘ(K-1)-(t-M-1) ＋｛ｂt+M ，ｂt+M+1 ，．．．，ｂK-1 ｝
＝｛ｂ’t ，ｂ’t+1 ，．．．，ｂ’t+M-1 ，ｂt+M ，ｂt+M+1 ，．．．，ｂK-1 ｝
（３２）
【００２４】
図１０に示すように、Ｐ’を新たなＰとみなして処理を繰り返すことで、ｎ回の繰り返し処理によりｎ・ｔビット分の剰余が計算される。図１０では、３回の繰り返し処理が示されている。
【００２５】
次に、図１１および図１２を参照しながら、このような剰余テーブルを用いた剰余計算装置の構成例について説明する。
図１１は、Ｍ＝１６、ｔ＝１６、Ｎ＝２、ｓ＝８の場合の剰余計算装置の構成例を示している。この剰余計算装置は、メモリ１０１、１０４、１０６、ビット列読出し部１０２、テーブル引き部１０３、１０５、ＥＯＲ部１０７、およびレジスタ１０８を備える。
【００２６】
メモリ１０１には、剰余計算対象のＫビットの入力ビット列Ｐが格納され、メモリ１０４には、ｐ’（ｘ）・ｘM+s の剰余テーブルＲＴａｂｌｅ１［］が格納され、メモリ１０６には、ｐ’（ｘ）・ｘM の剰余テーブルＲＴａｂｌｅ２［］が格納されている。
【００２７】
ビット列読出し部１０２は、メモリ１０１上に格納されたビット列Ｐを、先頭から順番にｔビット（１６ビット）ずつ読み出し、ＥＯＲ部１０７に出力する。テーブル引き部１０３は、Ｍビット（１６ビット）のレジスタ１０８のレジスタ値の先頭ｓビット（８ビット）を用いて、ＲＴａｂｌｅ１［］のテーブル引きにより剰余Ｒ1 （ｘ）のビット列を取得し、ＥＯＲ部１０７に出力する。テーブル引き部１０５は、レジスタ１０８のレジスタ値の残りのｓビット（８ビット）を用いて、ＲＴａｂｌｅ２［］のテーブル引きにより剰余Ｒ2 （ｘ）のビット列を取得し、ＥＯＲ部１０７に出力する。
【００２８】
ＥＯＲ部１０７は、ビット列読出し部１０２から受け取ったビット列と、Ｒ1 （ｘ）およびＲ2 （ｘ）のビット列のＥＯＲを計算し、計算結果をレジスタ１０８に格納する。
レジスタ１０８の初期値をオール０として以上の処理を行うことで、ビット列Ｐの先頭の１６ビットがレジスタ１０８に格納される。その後、ビット列Ｐの残りのビット列について、以上の処理をＫ／ｔ回繰り返すことで、入力ビット列Ｐに対する剰余計算結果がレジスタ１０８に格納される。ただし、最後のループでは、ビット列読出し部１０２からＥＯＲ部１０７に対して、オール０のビット列が出力される。レジスタ１０８の剰余計算結果を用いて、ＣＲＣ符号化またはＣＲＣ符号の誤り検出が行われる。
【００２９】
複数の演算器を有し、１命令サイクル中に２回メモリ参照可能なプロセッサや、メモリ参照にレーテンシサイクルを必要とするプロセッサの場合、テーブル引き部１０３および１０５によるテーブル引き処理を、ｔビット分の１回のループの間に、処理サイクル数の増大なしに行うことも可能である。
【００３０】
また、剰余テーブルに必要なメモリ領域は、従来の２20（＝Ｍ・２t ）ビットから２13（＝Ｍ・２s・Ｎ）ビットに削減される。
図１２は、Ｍ＝１６、ｔ＝３２、Ｎ＝４、ｓ＝８の場合の剰余計算装置の構成例を示している。この剰余計算装置は、メモリ２０１、２０５、２０７、２０９、２１１、ビット列読出し部２０２、ＥＯＲ部２０３、２１２、テーブル引き部２０４、２０６、２０８、２１０、およびレジスタ２１３を備える。
【００３１】
メモリ２０１には、剰余計算対象のＫビットの入力ビット列Ｐが格納され、メモリ２０５には、ｐ’（ｘ）・ｘM+3sの剰余テーブルＲＴａｂｌｅ１［］が格納され、メモリ２０７には、ｐ’（ｘ）・ｘM+2sの剰余テーブルＲＴａｂｌｅ２［］が格納されている。また、メモリ２０９には、ｐ’（ｘ）・ｘM+s の剰余テーブルＲＴａｂｌｅ３［］が格納され、メモリ２１１には、ｐ’（ｘ）・ｘM の剰余テーブルＲＴａｂｌｅ４［］が格納されている。
【００３２】
ビット列読出し部２０２は、メモリ２０１上に格納されたビット列Ｐを、先頭から順番にｔビット（３２ビット）ずつ読み出し、ＥＯＲ部２０３に出力する。ＥＯＲ部２０３は、ビット列読出し部２０２から受け取ったビット列と、Ｍビット（１６ビット）のレジスタ２１３のレジスタ値のＥＯＲを、先頭詰めで計算する。
【００３３】
このとき、１６ビットのレジスタ値の後ろにオール０の１６ビットのビット列が付加されて、３２ビットのビット列が生成され、そのビット列とビット列読出し部２０２からのビット列のＥＯＲが計算される。そして、ＥＯＲ部２０３は、ｔビット（３２ビット）の計算結果をテーブル引き部２０４、２０６、２０８、および２１０に出力する。
【００３４】
テーブル引き部２０４は、ＥＯＲ部２０３から受け取ったビット列の先頭ｓビット（８ビット）を用いて、ＲＴａｂｌｅ１［］のテーブル引きにより剰余Ｒ1 （ｘ）のビット列を取得し、ＥＯＲ部２１２に出力する。テーブル引き部２０６は、次のｓビット（８ビット）を用いて、ＲＴａｂｌｅ２［］のテーブル引きにより剰余Ｒ2 （ｘ）のビット列を取得し、ＥＯＲ部２１２に出力する。
【００３５】
テーブル引き部２０８は、さらに次のｓビット（８ビット）を用いて、ＲＴａｂｌｅ３［］のテーブル引きにより剰余Ｒ3 （ｘ）のビット列を取得し、ＥＯＲ部２１２に出力する。テーブル引き部２１０は、最後のｓビット（８ビット）を用いて、ＲＴａｂｌｅ４［］のテーブル引きにより剰余Ｒ4 （ｘ）のビット列を取得し、ＥＯＲ部２１２に出力する。
【００３６】
ＥＯＲ部２１２は、Ｒ1 （ｘ）、Ｒ2 （ｘ）、Ｒ3 （ｘ）、およびＲ4 （ｘ）のビット列のＥＯＲを計算し、計算結果をレジスタ２１３に格納する。
レジスタ２１３の初期値をオール０として以上の処理をＫ／ｔ回繰り返すことで、入力ビット列Ｐに対する剰余計算結果がレジスタ２１３に格納される。そして、レジスタ２１３の剰余計算結果を用いて、ＣＲＣ符号化またはＣＲＣ符号の誤り検出が行われる。
【００３７】
複数の演算器を有し、１命令サイクル中に複数回メモリ参照可能なプロセッサや、メモリ参照にレーテンシサイクルを必要とするプロセッサの場合、複数のテーブル引き部によるテーブル引き処理を、ｔビット分の１回のループの間に、処理サイクル数の増大なしに行うことも可能である。
【００３８】
また、剰余テーブルに必要なメモリ領域は、従来の２36（＝Ｍ・２t ）ビットから２14（＝Ｍ・２s・Ｎ）ビットに削減される。
図１１および図１２の剰余計算装置は、例えば、図１３に示すような情報処理装置（コンピュータ）を用いて構成される。図１３の情報処理装置は、ＣＰＵ（中央処理装置）３０１、メモリ３０２、入力装置３０３、出力装置３０４、外部記憶装置３０５、媒体駆動装置３０６、およびネットワーク接続装置３０７を備え、それらはバス３０８により互いに接続されている。
【００３９】
メモリ３０２は、例えば、ＲＯＭ（read only memory）、ＲＡＭ（random access memory）等を含み、処理に用いられるプログラムおよびデータを格納する。ＣＰＵ３０１は、メモリ３０２を利用してプログラムを実行することにより、上述した剰余計算を含む様々な処理を行う。
【００４０】
この場合、図１１のメモリ１０１、１０４、１０６、および図１２のメモリ２０１、２０５、２０７、２０９、２１１は、メモリ３０２に対応する。図１１のビット列読出し部１０２、テーブル引き部１０３、１０５、およびＥＯＲ部１０７と、図１２のビット列読出し部２０２、ＥＯＲ部２０３、２１２、およびテーブル引き部２０４、２０６、２０８、２１０は、メモリ３０２に格納されたプログラムに対応する。
【００４１】
入力装置３０３は、例えば、キーボード、ポインティングデバイス等であり、オペレータからの指示や情報の入力に用いられる。出力装置３０４は、例えば、ディスプレイ、プリンタ、スピーカ等であり、オペレータへの問い合わせや処理結果の出力に用いられる。
【００４２】
外部記憶装置３０５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。情報処理装置は、この外部記憶装置３０５に、プログラムおよびデータを格納しておき、必要に応じて、それらをメモリ３０２にロードして使用する。
【００４３】
媒体駆動装置３０６は、可搬記録媒体３０９を駆動し、その記録内容にアクセスする。可搬記録媒体３０９は、メモリカード、フレキシブルディスク、光ディスク、光磁気ディスク等の任意のコンピュータ読み取り可能な記録媒体である。オペレータは、この可搬記録媒体３０９にプログラムおよびデータを格納しておき、必要に応じて、それらをメモリ３０２にロードして使用する。
【００４４】
ネットワーク接続装置３０７は、通信ネットワークに接続され、ＣＲＣ符号を含むビット列の送受信を行う。また、情報処理装置は、必要に応じて、プログラムおよびデータを外部の装置からネットワーク接続装置３０７を介して受け取り、それらをメモリ３０２にロードして使用する。
【００４５】
図１４は、図１３の情報処理装置にプログラムおよびデータを提供する方法を示している。可搬記録媒体３０９やサーバ４０１のデータベース４１１に格納されたプログラムおよびデータは、情報処理装置４０２のメモリ３０２にロードされる。サーバ４０１は、そのプログラムおよびデータを搬送する搬送信号を生成し、通信ネットワーク上の任意の伝送媒体を介して情報処理装置４０２に送信する。ＣＰＵ３０１は、そのデータを用いてそのプログラムを実行し、必要な処理を行う。
【図面の簡単な説明】
【００４６】
【図１】本発明の剰余計算装置の原理図である。
【図２】１番目の剰余テーブルの作成方法を示す図である。
【図３】２番目の剰余テーブルの作成方法を示す図である。
【図４】Ｎ番目の剰余テーブルの作成方法を示す図である。
【図５】Ｎ個の剰余テーブルによる剰余計算を示す図である。
【図６】１番目の剰余テーブルのテーブル引きを示す図である。
【図７】２番目の剰余テーブルのテーブル引きを示す図である。
【図８】Ｎ番目の剰余テーブルのテーブル引きを示す図である。
【図９】ｔビット分の処理を示す図である。
【図１０】繰り返し処理を示す図である。
【図１１】第１の剰余計算装置の構成図である。
【図１２】第２の剰余計算装置の構成図である。
【図１３】情報処理装置の構成図である。
【図１４】プログラムおよびデータの提供方法を示す図である。
【図１５】従来の剰余計算装置の構成図である。
【図１６】従来の剰余テーブル作成方法を示す図である。
【図１７】従来のｔビット分の処理を示す図である。
【図１８】従来の繰り返し処理を示す図である。
【符号の説明】
【００４７】
１１、１６、１０１、１０４、１０６、２０１、２０５、２０７、２０９、２１１、３０２  メモリ
１２、１０２、２０２  ビット列読出し部
１３  ビット分離部
１４  ビット結合部
１５、１０３、１０５、２０４、２０６、２０８、２１０  テーブル引き部
１７、１０７、２０３、２１２  ＥＯＲ部
１８、１０８、２１３  レジスタ
５１  記憶手段
５２  テーブル引き手段
５３  計算手段
３０１  ＣＰＵ
３０３  入力装置
３０４  出力装置
３０５  外部記憶装置
３０６  媒体駆動装置
３０７  ネットワーク接続装置
３０８  バス
３０９  可搬記録媒体
４０１  サーバ
４０２  情報処理装置
４１１  データベース
【図１】
2008011025.tif 000003
【図２】
2008011025.tif 000004
【図３】
2008011025.tif 000005
【図４】
2008011025.tif 000006
【図５】
2008011025.tif 000007
【図６】
2008011025.tif 000008
【図７】
2008011025.tif 000009
【図８】
2008011025.tif 000010
【図９】
2008011025.tif 000011
【図１０】
2008011025.tif 000012
【図１１】
2008011025.tif 000013
【図１２】
2008011025.tif 000014
【図１３】
2008011025.tif 000015
【図１４】
2008011025.tif 000016
【図１５】
2008011025.tif 000017
【図１６】
2008011025.tif 000018
【図１７】
2008011025.tif 000019
【図１８】
2008011025.tif 000020