(57)【要約】【課題】ワード幅のCRC計算を実現し、プロセッサの動作効率を向上させる。【解決手段】本発明の形態の１つによれば、ＣＲＣ値を計算するためのシステムが得られる。このシステムには、データ・メッセージ、現在のＣＲＣ値、及び、複数のルックアップ・テーブルを記憶するための少なくとも１つのメモリが含まれている。データ・メッセージには、複数のワードが含まれており、各ワードには複数のバイトが含まれている。ルックアップ・テーブルには、それぞれ、複数のマルチバイトＣＲＣ値が記憶されている。このシステムには、一度に１ワードずつメッセージを処理するためのプロセッサが含まれている。プロセッサは、ワードと現在のＣＲＣ値のＸＯＲに基づいて、また、ルックアップ・テーブルのそれぞれから検索されたマルチバイトＣＲＣ値に基づいて、各ワードの処理中に現在のＣＲＣ値を更新するように構成されている。【選択図】図３
2005006298.tif 000002
【特許請求の範囲】
【請求項１】
ＣＲＣ値を計算するためのシステムであって、
データ・メッセージ、現在のＣＲＣ値、及び、複数のルックアップ・テーブルを記憶するための少なくとも１つのメモリであって、該データ・メッセージが複数のワードを含んでおり、該ワードの各々が複数のバイトを含んでおり、該ルックアップテーブルの各々が複数のマルチバイトＣＲＣ値を記憶している、少なくとも１つのメモリと、
前記ワードと前記現在のＣＲＣ値のＸＯＲに基づいて、また、前記ルックアップ・テーブルのそれぞれから検索されたマルチバイトＣＲＣ値に基づいて、各ワードの処理中に前記現在のＣＲＣ値を更新するように構成された、一度に１ワードずつメッセージの処理を行うためのプロセッサと、
を有する、ＣＲＣ値を計算するためのシステム。
【請求項２】
前記ワードと前記現在のＣＲＣ値のＸＯＲによって、第１のマルチバイトＸＯＲ結果が得られ、前記検索されるマルチバイトＣＲＣ値のそれぞれが、前記第１のＸＯＲ結果の１バイトに対応する、請求項１に記載のシステム。
【請求項３】
前記プロセッサが、前記検索されたマルチバイトＣＲＣ値のＸＯＲを実施することによって、第２のＸＯＲ結果を生じるように構成され、前記プロセッサが、前記現在のＣＲＣ値を前記第２のＸＯＲ結果に置き換えることによって、前記現在のＣＲＣ値を更新するように構成される、請求項２に記載のシステム。
【請求項４】
前記現在のＣＲＣ値及び前記データ・メッセージの各ワードが、同じバイト数を備える、請求項１に記載のシステム。
【請求項５】
前記現在のＣＲＣ値及び前記データ・メッセージの各ワードが４つの８ビット・バイトを含み、前記複数のルックアップ・テーブルが４つのルックアップ・テーブルを有し、該４つのルックアップ・テーブルのそれぞれが２５６の項目を含み、該項目の各々が４つの８ビット・バイトを含む、請求項４に記載のシステム。
【請求項６】
前記データ・メッセージの各ワードが、前記現在のＣＲＣ値より少ないバイト数を含む、請求項１に記載のシステム。
【請求項７】
複数のマルチバイト値を含むデータ・メッセージに関するＣＲＣ値を計算する方法であって、
（ａ）それぞれ、複数のマルチバイトＣＲＣ値を納めた、複数のルックアップ・テーブルを設けるステップと、
（ｂ）前記データ・メッセージからの前記マルチバイト値のうちの１つおよび現在のＣＲＣ値に対してＸＯＲ演算を実施することによって、第１のマルチバイトＸＯＲ結果を生成するステップと、
（ｃ）前記ルックアップ・テーブルのそれぞれに前記ＸＯＲ結果のうち別々のバイトでアドレス指定することによって、前記ルックアップ・テーブル内の複数のマルチバイトＣＲＣ値を識別するステップと、
（ｄ）前記識別されたマルチバイトＣＲＣ値にＸＯＲ演算を実施することによって、第２のマルチバイトＸＯＲ結果を生成するステップと、
（ｅ）前記第２のマルチバイトＸＯＲ結果に基づいて前記現在のＣＲＣ値を更新するステップと、
を有する方法。
【請求項８】
（ｆ）前記データ・メッセージの各マルチバイト値毎にステップ（ｂ）〜（ｅ）を反復するステップをさらに有する、請求項７に記載の方法。
【請求項９】
ＣＲＣ値を計算するためのシステムであって、
データ・メッセージ、現在のＣＲＣ値、及び、複数のルックアップ・テーブルを記憶するための少なくとも１つのメモリであって、該データ・メッセージが複数のワードを含んでおり、該ワードの各々が前記現在のＣＲＣ値より多くのバイトを含んでおり、前記ルックアップ・テーブルのそれぞれが複数のマルチバイトＣＲＣ値を記憶している、少なくとも１つのメモリと、
前記ワードの第１の部分集合と前記現在のＣＲＣ値のＸＯＲに基づいて、また、前記ルックアップ・テーブルのそれぞれから検索されたマルチバイトＣＲＣ値に基づいて、各ワードの処理中に前記現在のＣＲＣ値を更新するように構成された、一度に１ワードずつメッセージの処理を行うためのプロセッサと、
を有する、ＣＲＣ値を計算するためのシステム。
【請求項１０】
前記プロセッサが、ＸＯＲ結果に基づいて、前記ルックアップ・テーブルの第１の部分集合から前記マルチバイトＣＲＣ値の第１の部分集合を検索するように構成されており、前記プロセッサが、前記ワードの第２の部分集合に基づいて、前記ルックアップ・テーブルの第２の部分集合から前記マルチバイトＣＲＣ値の第２の部分集合を検索するように構成されており、前記プロセッサが、前記ルックアップ・テーブルから検索された前記マルチバイトＣＲＣ値のＸＯＲを実施することによって、更新された現在のＣＲＣ値を生成するように構成されている、請求項９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、ＣＲＣ値を計算するためのシステムに関するものであり、とりわけ、一度に１ワードずつデータ・メッセージを処理することによって、ＣＲＣ値を計算するためのシステムに関するものである。
【背景技術】
【０００２】
巡回冗長符号（ＣＲＣ）に基づく技法のようなエラー検出技法の目的は、ノイズのあるチャネルを介して伝送されるメッセ−ジの受信機が、そのメッセージが損なわれているか否かを判定できるようにすることにある。これを行うため、送信機は、メッセージの関数である値（フレーム・チェック・シーケンスまたはＦＣＳと呼ばれる）を生成し、一般に、メッセージにＦＣＳを付加する。受信機は、従って、受信メッセージのＦＣＳの発生に用いられたのと同じ関数を利用して、メッセージが正しく受信されたか否かを確認することが可能である。
【０００３】
ＣＲＣアルゴリズムの場合、メッセージ・ビットは、ｎビット多項式の２進係数として扱われる。メッセージ多項式にｘｍが掛けられるが、ここで、ｍはＣＲＣ多項式（すなわち、「生成多項式」）の次数である。掛け算の結果は、ＣＲＣ多項式で割られる。大部分の実施例では、ｘｍとの掛け算及びＣＲＣ多項式による割り算を順番に実行するのではなく、これらの演算を同時に実行する方法が用いられる。これらの演算結果は、一般に、補数演算を施されて、メッセージに付加されるＦＣＳである。場合によっては、ＦＣＳは補数演算を施されないこともあり、また、場合によっては、ＦＣＳはヘッダ・フィールドのような別の場所に挿入されることもある。
【０００４】
受信機は、ＣＲＣ多項式によって、ＦＣＳが付加された受信メッセージを割る。ＦＣＳが、メッセージに付加される前に、補数演算を施されたものと仮定すると、また、伝送中にエラーが生じなかったものと仮定すると、受信機における割り算結果は、次数が２ｍの多項式（高位のｍ項に関する係数が１で、下位のｍ項に関する係数が０）をＣＲＣ多項式で割る結果に等しい固定値になる。この固定値は、「マジック数」と呼ばれる場合もある。割り算の結果がマジック数に等しくない場合、これは、エラーの発生を表わしている。
【０００５】
大部分のソフトウェア・ベースのＣＲＣアルゴリズムは、一度に１バイトずつデータ処理を行う。一度に１バイトずつ処理を行う理由が、一度により多くのバイトを処理するには、大規模なテーブルが必要になり、また、とにかく、アライメントのとれないバイトを取り扱うために、一度に１バイト式の回路が一般に利用されており、全てのバイトの処理に同じ回路を利用することができるという点にあると思われる。従来の方法を拡張して、一度に１６ビットの処理を行う場合には、２１６項目のルックアップ・テーブルが利用され、３２ビットＣＲＣのために、２５６キロバイトを消費することになる可能性がある。従来の方法を拡張して、一度に３２ビットの処理を行う場合には、ルックアップ・テーブルは、３２ビットのＣＲＣのために、１６ギガバイトを消費することになる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来の方法を利用した、ソフトウェアによるＣＲＣ計算の問題点は、データ・バイト毎に複数命令が実行され、このために、ソフトウェアによるＣＲＣ計算が極めて重い負担になるという点にある。多くのプロセッサは、ワード幅の計算ができれば、動作効率が向上することになる。
【課題を解決するための手段】
【０００７】
本発明の形態の１つによれば、ＣＲＣ値を計算するためのシステムが得られる。このシステムには、データ・メッセージ、現在のＣＲＣ値、及び、複数のルックアップ・テーブルを記憶するための少なくとも１つのメモリが含まれている。データ・メッセージには、複数のワードが含まれており、各ワードには複数のバイトが含まれている。ルックアップ・テーブルには、それぞれ、複数のマルチバイトＣＲＣ値が記憶されている。このシステムには、一度に１ワードずつメッセージを処理するためのプロセッサが含まれている。プロセッサは、ワードと現在のＣＲＣ値のＸＯＲに基づいて、また、ルックアップ・テーブルのそれぞれから検索されたマルチバイトＣＲＣ値に基づいて、各ワードの処理中に現在のＣＲＣ値を更新するように構成されている。
【発明を実施するための最良の形態】
【０００８】
望ましい実施態様に関する下記の詳細な解説では、その一部をなし、例証のため、本発明を実施することが可能な特定の実施態様が示されている、添付の図面が参照される。もちろん、本発明の範囲を逸脱することなく、他の実施態様を利用することもできるし、構造または論理的変更を加えることも可能である。従って、下記の詳細な説明は、制限の意味にとるべきではなく、本発明の範囲は、付属の請求項によって定義される。
【０００９】
当該技術者には明らかなように、ＣＲＣ計算は、桁上げなしの２進算術演算モジュロ２（modulo-2、ＭＯＤ−２）を利用して実施される。こうした算術演算の場合、加算及び減算は、両方とも、論理演算の排他的ＯＲ（ＸＯＲ）に相当し、乗算は論理演算ＡＮＤに相当する。従って、記号「＋」及び「−」は論理演算ＸＯＲを表わし、記号「＊」は論理演算ＡＮＤを表している。
【００１０】
背景技術のセクションにおいて上述のように、大部分のソフトウェア・ベースのＣＲＣアルゴリズムは、一度に１バイトのデータを処理する。ＣＲＣ剰余レジスタ（CRC remainer register）は、一般に、現在のＣＲＣ剰余を記憶するために用いられる。図１は、一度に１バイトずつデータ・メッセージを処理することによって、ＣＲＣを計算するための先行技術による方法１００を例示したフローチャートである。図１に例示の方法１００の場合、次数が３２のＣＲＣ多項式が用いられており、従って、ＣＲＣ剰余が３２ビットになるものと仮定する。ステップ１０２では、データ・メッセージから次のデータ・バイトdbyteが検索される。ステップ１０４では、ＣＲＣ剰余レジスタcは、レジスタから最上位バイトを得るために右方向にシフトされ、一時的結果tとして記憶される。ステップ１０６では、ステップ１０４からの一時的結果tと、ステップ１０２で検索されたデータ・バイトdbyteに対してＸＯＲ演算が実施される。ＸＯＲの演算の結果は、一時的結果tとして記憶される。ステップ１０８では、ルックアップ・テーブルＴから、ステップ１０６において得られた一時的結果tに対応する位置の値が検索される。従って、ステップ１０６におけるＸＯＲ演算の結果は、ルックアップ・テーブルＴに対する索引の働きをする。図１に示すような、従来の一度に１バイト式のＣＲＣアルゴリズムでは、２５６項目（entry）の単一ルックアップ・テーブルが利用される。ルックアップ・テーブルの各項目は、一般に３２ビットのＣＲＣ幅である。
【００１１】
ステップ１１０では、ＣＲＣ剰余レジスタｃが、左に１バイト分シフトされ、その結果が、ＣＲＣ剰余レジスタｃに記憶される。ステップ１１２では、ＣＲＣ剰余レジスタｃの値と、ステップ１０８でルックアップ・テーブルから得られた値T(t)に対して、ＸＯＲ演算が実施される。ステップ１１２におけるＸＯＲの結果は、ＣＲＣ剰余レジスタｃに記憶される。ステップ１１４では、処理すべきデータがさらに存在するか否かの判定が行われる。さらにデータが存在する場合、この方法１００はステップ１０２に戻り、メッセージの次のデータ・バイトを処理する。処理すべきデータがなければ、ステップ１１６によって示されるように、方法１００は完了する。
【００１２】
下記のコード例Ｉによって、図１に示す方法１００を実施するために利用可能なＣプログラミング言語によるコード例が得られる。コード例Ｉのコードは、従来より、３２ビット幅ＣＲＣに対する一度に１ビットずつのＣＲＣ計算に利用されている。
【００１３】
コード例Ｉ
while(len--)c=(c<<8)^t[(c>>24)^*p++]
ここで、
len=データ・メッセージの長さ、
c=３２ビットＣＲＣ剰余レジスタ、
t=ルックアップ・テーブル、及び、
p=処理すべき次のデータ・バイトの位置を識別するためのポインタまたは索引。
【００１４】
上記コード例Ｉは、ftp://ftp.rocksoft.com/papers/CRC_v3.txtで入手可能な、Williams,Rossによって1993年8月にInternet Pulicationで発表された「A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS」における非折り返しアルゴリズム（non-reflecting algorithm）である。
【００１５】
コード例Ｉの方程式の右側から始めると、コード「＊ｐ」が、ポインタpによって指示されるアドレスの内容を検索する。これは、データ・メッセージから、次のバイトを保持するアドレスである。次のデータ・バイトの検索が済むと、索引ｐは、コード「＋＋」で指示されるように、次の繰り返しで処理すべきデータ・バイトのアドレスに対するポイントにインクリメントされる。コード「ｃ＞＞２４」は、ＣＲＣ剰余レジスタを右に２４ビット（３バイト）分シフトすることを示す。右にシフトしたＣＲＣ剰余レジスタの値と現在のデータ・バイトに対して、ＸＯＲ演算（＾）が施される。ＸＯＲ演算の結果は、ルックアップ・テーブルに対する索引ｔであり、従って、コード「t[(c>>24)^*p++]」によって、ルックアップ・テーブルからＸＯＲ演算結果によって識別される位置にある値が検索されることになる。
【００１６】
コード「ｃ＜＜８」は、ＣＲＣ剰余レジスタを左に８ビット（１バイト）分シフトすることを示す。左にシフトしたＣＲＣ剰余レジスタの値とルックアップ・テーブルから得られた値に対して、ＸＯＲ演算（＾）が施され、ＸＯＲ演算結果は、ＣＲＣ剰余レジスタに記憶される。コード「while(len--)」は、各繰り返し後、データ・メッセージの長さ（len）をデクリメントする（--）することを示すので、上記プロセスは、全メッセージの処理が済むまで、メッセージの各バイト毎に繰り返される。
【００１７】
コード例Ｉの方程式は、ＣＲＣを計算するため、データ・メッセージの各バイト毎に利用される。コード例Ｉのコードは、処理される各バイト毎に多くの命令を実行することを必要とする。各バイト毎に、２つのシフト命令、データ・バイトの読み取り、そのデータ・バイトとシフト操作の結果とのＸＯＲ、テーブル値の読み取り、及び、テーブルからの値と第２のシフト結果とのＸＯＲが実行される。
【００１８】
コード例Ｉの方程式は、ＣＲＣ及び入力の現在の状態の関数としてＣＲＣの次の状態を示すので、「状態遷移方程式（next state equation）」と呼ばれる。下記の方程式Ｉには、行列の形で状態遷移方程式が示されている。
【００１９】
方程式Ｉ
ｃ＝Ａｃ＋Ｂｄ
ここで、
ｃ＝ＣＲＣ剰余レジスタ（ベクトル）、
ｄ＝処理すべき次のデータ・セット（ベクトル）、
Ａ＝用いられるＣＲＣ生成多項式によって決まる値を備えた定数行列
Ｂ＝用いられるＣＲＣ生成多項式によって決まる値を備えた定数行列
ベクトル・サイズは、１サイクルにおいて処理されるデータ・ビット数に等しい。行列Ｂにおける列数は、ベクトルｄのサイズに等しい。
【００２０】
方程式Ｉによって示されるように、定数行列ＡとＣＲＣ剰余ベクトルｃの値との乗算が行われ、定数行列Ｂとデータ・ベクトルｄの乗算が行われる。これら２つの行列乗算のそれぞれによって、新しいベクトルが得られる。２つの新しいベクトルのＸＯＲが実施されて、そのＸＯＲ結果がＣＲＣ剰余レジスタｃに記憶される。
【００２１】
方程式Ｉの計算は、ＭＯＤ−２計算に基づくものである。行列（すなわち、行列Ａ及びＢ）とベクトル（すなわち、ベクトルｃ及びｄ）の要素は、０または１である。プロセッサは、ＭＯＤ−２行列乗算に関する命令を与えないが、ビット操作演算には、一般に、多くの命令が必要になる。これらの演算を効率的に実施するため、一般には、ルックアップ・テーブルが利用される。方程式Ｉの操作には、定数行列と変数ベクトルの乗算が必要になる。その結果、ルックアップ・テーブルと同じ幅のベクトルが得られる。行列Ａ及びＢは、定数行列であるため、可能性のある各入力ベクトルに関する結果ベクトルを含むテーブルをあらかじめ計算しておくことが可能である。
【００２２】
サイクル毎に処理されるデータ・ビット数と、利用されるＣＲＣの幅に基づいて、上記方程式Ｉによって示された状態遷移方程式に操作を施し、さまざまな形式にすることが可能である。４つの事例について後述される。第１の事例（事例１）では、サイクル毎に処理されるデータ・ビット数が、ＣＲＣビット数未満である。第２の事例（事例２）では、サイクル毎に処理されるデータ・ビット数が、ＣＲＣビット数未満であり、入力及び出力の「折り返し（reflection）」が適用される。折り返しについては、事例２に関連してさらに詳細に後述する。第３の事例（事例３）では、サイクル毎に処理されるデータ・ビット数が、ＣＲＣビット数に等しい。第４の事例（事例４）では、サイクル毎に処理されるデータ・ビット数が、ＣＲＣビット数を超える。多項式係数が、非折り返し事例の場合のベクトルとして示されているので、最下位項の係数が、ベクトルの最上位に位置し、最上位項の係数が、ベクトルの最下位に位置するという点に留意されたい。
【００２３】
事例１
事例１の場合、サイクル毎に処理されるデータ・ビット数は、ＣＲＣビット数未満である。この事例の場合、上記方程式Ｉにおいて示された状態遷移方程式は、下記の方程式ＩＩに変換することが可能である。
【００２４】
方程式ＩＩ
ｃ＝Ａｃ＋Ｂ’ｄ’
ここで、
ｃ＝ＣＲＣ剰余レジスタ（ベクトル）、
ｄ’＝ｃと同じサイズになるように、ベクトルの最上位に０を加えて拡大された方程式Ｉからのｄ
Ａ＝利用されるＣＲＣ生成多項式によって値が決まる定数行列
Ｂ’＝Ａと同じサイズになるように、行列の左側に０を加えて拡大された方程式Ｉからの行列Ｂ
上述のようにベクトルｄ及び行列Ｂを拡大することによって、ベクトルｄ’の非０のデータとベクトルｃの最上位バイトのアライメントがとれるという点に留意されたい。このアライメントの目的は、上述のＲｏｓｓ  Ｗｉｌｌｉａｍｓの電子技術的情報に提案されている非折り返しアルゴリズムに関する形式に合わせることにある。方程式ＩＩにおいて、行列Ａ及びＢ’は、複雑な行列である。方程式ＩＩは、行列の一方が単純なシフト行列になり、もう一方の行列が１組の方程式またはテーブルによって実施される、単純な形式に変換することが可能である。こうした形式は、上述のＲｏｓｓ  Ｗｉｌｌｉａｍｓの電子技術的情報に提案されているものである。シフト行列は、「１」の対角線を備えた行列であり、行列における他の値は、「０」である。シフト行列では、ベクトルのビット位置がシフトされる。以下の説明には、方程式ＩＩをＲｏｓｓ  Ｗｉｌｌｉａｍｓの電子技術的情報に提案されている形式に変換する方法が示されている。
【００２５】
方程式ＩＩの右側に＋Ｂ’ｃ項及び−Ｂ’ｃ項を導入し、次に、因数分解すると、下記の方程式ＩＩＩが得られる。
【００２６】
方程式ＩＩＩ
ｃ＝Ａ’ｃ＋Ｂ’（ｃ＋ｄ’）
ここで、
Ａ’＝Ａ−Ｂ’
方程式ＩＩＩにおいて、行列Ａ’は、左シフトする（１バイトずつ）行列である。第２項Ｂ’（ｃ＋ｄ’）は、ルックアップ・テーブルで実施することが可能である。３２ビットＣＲＣの場合、サイクル毎に１バイトずつ処理すると、上記方程式ＩＩＩを用いた結果は、入力または出力が非折り返しの場合に関するＲｏｓｓ  Ｗｉｌｌｉａｍｓの電子技術的情報からのアルゴリズム（すなわち、上記コード例Ｉ）に一致する。方程式ＩＩＩの行列「Ａ’」が１バイトずつ左にシフトし、ベクトルｄからベクトルｄ’を生成する方法によって、方程式ＩＩＩのベクトルｄ’とベクトルｃの最上位バイトのアライメントがとれるので、行列形式をなすコード例Ｉは、方程式ＩＩＩと同じである。
【００２７】
本発明の実施態様の１つでは、方程式ＩＩＩに基づくアルゴリズムを利用して、データ・メッセージの始端及び／または終端における部分ワード（例えば、１、２、または、３バイト）が処理される。本発明の形態の１つでは、方程式ＩＩＩに基づくアルゴリズムを利用して、プロセッサのワード幅がＣＲＣ幅未満の場合についてのデータ・ワードも処理される（例えば、１６ビット・ワード・マシンで３２ビットＣＲＣを計算したり、あるいは、３２ビット・ワード・マシンで６４ビットＣＲＣを計算する）。実施態様の１つでは、第２項Ｂ’（ｃ＋ｄ’）は４つのルックアップ・テーブルで実施する。
【００２８】
事例２
ＣＲＣ計算のためのビットの重み順は、その計算を実施するマシンに固有のビット順と同じにはならない。「折り返し（reflection）」は、マシンに固有のビット順に関係なく、正しいビット重みでＣＲＣを計算できるようにする、ＣＲＣ計算の修正を表わしている。ある値は、そのビットをその中央の周りでスワップすると、折り返される。例えば、０１０１は、１０１０の４ビット折り返しであり、００１１は、１１００の４ビット折り返しである。
【００２９】
事例２の場合、サイクル毎に処理されるデータ・ビット数は、ＣＲＣビット未満であり、入力は折り返され（マシンに所望の順に記憶されていなかったので）、最終ＣＲＣは折り返されることになり（出力折り返し）、「バイト・スワップ」操作が実施されることになるのが望ましい。場合によっては、ＣＲＣ剰余レジスタから出力されるバイト順は、バイトがメッセージに付加されることになる順序とは異なることもある。こうした場合、「バイト・スワップ」操作は、メッセージへの付加前に、バイトの順序を適正に直すために実施される。インターネットプロトコル小型コンピュータシステムインタフェース（ｉＳＣＳＩ）及びストリーム制御伝送プロトコル（ＳＣＴＰ）の規格には、入力を折り返し（データが、ＳＣＴＰ  ＣＲＣアルゴリズムの指定とは異なる順にメモリに記憶されているため）、折り返し出力を生成し、バイト・スワップ操作を実施するＣＲＣアルゴリズムが含まれている。ｉＳＣＳＩ及びＳＣＴＰ用のＣＲＣアルゴリズムに関する情報については、インターネット技術標準化委員会（Internet Engineering Task Force、ＩＥＴＦ）のウェブサイト、http://www.ietf.orgで入手可能である（例えば、Request For Comments（ＲＦＣ） documents ２９６０、３３０９、及び、３３８５参照）。
【００３０】
入力を折り返さなければならない場合、ＣＲＣ計算を効率よく実施するため、一時的（interim）ＣＲＣ結果が、入力ビット順に一致するビット順に保たれ、テーブルは、折り返されるビットの順序付けを補償するように調整される。従って、プロセッサは、ビットの再順序付け（複数サイクルを要するプロセス）をしなくても済む。以下では、マシン命令でビット処理を可能にする方法に関する実施態様の１つの操作が説明される。
【００３１】
事例２の場合、上記方程式Ｉで示された次の状態の方程式は、下記の方程式ＩＶに変換することが可能である。
【００３２】
方程式ＩＶ
ｃ＝Ａｃ＋Ｂ’ｄ’
ここで、
ｃ＝ＣＲＣ剰余レジスタ（ベクトル）、
ｄ’＝ベクトルの最下位に０を加えて拡大された方程式Ｉからのｄ
Ａ＝利用されるＣＲＣ生成多項式によって値が決まる定数行列
Ｂ’＝行列の右側に０を加えて拡大された方程式Ｉからの行列Ｂ
上述のように、ベクトルｄ及び行列Ｂを拡大することによって、ベクトルｄ’の非０データと下記の折り返されたｃベクトルの最上位係数とのアライメントがとれることになる。このアライメントは、事例１とは異なる。このアライメントの目的は、上述のRoss Williamsの電子技術的情報に提案されている折り返しアルゴリズムに関する形式に一致させることにある。下記のコード例ＩＩには、上述のRoss Williamsの電子技術的情報に提案されている非折り返しアルゴリズムに関するコードが示されている。
【００３３】
コード例ＩＩ
while(len--)reflc=(reflc>>8)^t[reflc^*p++]
事例２には、入力折り返しが必要とされるので、方程式ＩＶのベクトルｄ’は、下記の方程式Ｖに示す「ｒｅｆｌｄ」に置き換えられるべきである。
【００３４】
方程式Ｖ
ｃ＝Ａｃ＋Ｂ’ｒｅｆｌｄ’
ここで、
ｒｅｆｌｄ’＝Ｒ８ｄ’、
Ｒ８＝８ビット折り返しを実施する行列。
【００３５】
行列形式で表したｉＳＣＳＩ  ＣＲＣアルゴリズムが、下記の方程式ＶＩによって示される。
【００３６】
方程式ＶＩ
ｒｅｆｌｃ＝Ａ’ ｒｅｆｌｃ＋Ｂ１’（ｒｅｆｌｃ＋ｄ’）
ここで、
ｒｅｆｌｃ＝Ｒ３２ｃ、
Ｒ３２＝バイト折り返し及びバイト・スワップと同等の３２ビット折り返しを実施する行列
方程式ＶＩの行列Ａ’は、８位置分右にシフトする行列である。方程式Ｖを利用すると、方程式ＶＩの行列Ａ’は下記の方程式ＶＩＩによって定義されることが分る。
【００３７】
方程式ＶＩＩ
Ａ’＝Ｒ３２ＡｉｎｖｅｒｓｅＲ３２−Ｒ３２Ｂ’Ｒ８
ここで、
ｉｎｖｅｒｓｅＲ３２＝Ｒ３２の逆行列である行列。
【００３８】
方程式ＶＩにおけるＢ１’項は、テーブルで実施可能である。方程式Ｖを利用すると、方程式ＶＩの行列Ｂ１’は下記の方程式ＶＩＩＩによって定義されることが分る。
【００３９】
方程式ＶＩＩＩ
Ｂ１’＝Ｒ３２Ｂ’Ｒ８
本発明の実施態様の１つでは、入力折り返し、出力折り返し、及び、バイト・スワップ操作が要求される場合に、方程式ＶＩに基づくアルゴリズムを利用して、データ・メッセージの始端及び終端における部分ワードが処理される。
【００４０】
事例３
事例３において、サイクル毎に処理されるデータ・ビット数は、ＣＲＣビット数に等しい。実施態様の１つでは、３２ビット・ワード・サイズのプロセッサで３２ビットＣＲＣを計算する場合のように、データ・ワードがＣＲＣと同じ長さの場合、事例３を利用して、データの全ワードが処理される。事例３の場合、ＣＲＣ計算の特性により、行列Ａは、状態遷移方程式（方程式Ｉ）における行列Ｂに等しくなる。従って、方程式Ｉは、下記の方程式ＩＸによって示される形式で書くことが可能である。
【００４１】
方程式ＩＸ
ｃ＝Ａ（ｃ＋ｄ）
ここで、
ｃ＝ＣＲＣ剰余レジスタ（ベクトル）、
ｄ＝処理すべき次のデータ・セット（ベクトル）、
Ａ＝利用されるＣＲＣ生成多項式によって値が決まる定数行列
方程式ＩＸの右側は、下記のコード例ＩＩＩに例示のように、ルックアップ・テーブルで実施可能である。
【００４２】
コード例ＩＩＩ
ｃ＝ｔ［ｃ＋ｄ］
コード例ＩＩＩに示すように、ベクトルｃ及びｄに対するＸＯＲ演算が実施され、ＸＯＲ結果が、ルックアップ・テーブルｔに対する索引になる。ルックアップ・テーブルから検索される値は、ＣＲＣ剰余レジスタｃに記憶される。コード例ＩＩＩに関するルックアップ・テーブルは、２ｎの項目を備えているが、ここで、ｎはＣＲＣのサイズである。さらに詳細に後述するように、本発明のある形態では、大規模なルックアップ・テーブルの参照を実施するのではなく、ｃ＋ｄの各バイト毎に１回ずつ、４つの小規模なルックアップ・テーブルを４回参照するように、操作が分割される。実施態様の１つでは、４つのテーブルに、それぞれ、２５６項目が含まれている。
【００４３】
入力折り返しが要求される場合、方程式ＩＸは下記の方程式Ｘに変換される。
【００４４】
方程式Ｘ
ｃ＝Ａ（ｃ＋ｒｅｆｌｄ）
ここで、
ｒｅｆｌｄ＝Ｒ８’ｄ、
Ｒ８’＝３２ビット・ベクトルｄの各バイト内のビットのビット反転を個別に実施する３２×３２行列（すなわち、バイト・スワップなし）
バイト・スワップのない、入力折り返し及び出力折り返しの両方が要求される場合、方程式ＩＸは下記の方程式ＸＩに変換される。
【００４５】
方程式ＸＩ
ｒｅｆｌｃ＝Ａ’（ｒｅｆｌｃ＋ｄ）
ここで、
ｒｅｆｌｃ＝Ｒ８’ｃ、
Ｒ８’＝３２ビット・ベクトルｄの各バイト内のビットのビット反転を個別に実施する３２×３２行列（すなわち、バイト・スワップなし）、
Ａ’＝Ｒ８’Ａ  Ｒ８’
事例４
事例４の場合、サイクル毎に処理されるデータ・ビット数は、ＣＲＣビット数を超える。実施態様の１つでは、３２ビット・プロセッサによる１６ビットＣＲＣ計算の場合のように、データ・ワード幅がＣＲＣを超える場合、事例４を利用して、データの全ワードが処理される。ＣＲＣビット数がｎで、データ・ビット数がｍであると仮定すると、方程式Ｉにおける行列の大きさは、ｃがｎ×１、Ａがｎ×ｎ、Ｂがｎ×ｍ、及び、ｄがｍ×１である。状態遷移方程式（方程式Ｉ）は、下記の方程式ＸＩＩに示すように書くことが可能である。
【００４６】
方程式ＸＩＩ
ｃ＝Ａｃ＋Ｂ０ｄ０＋Ｂ１ｄ１
ここで、
Ｂ０＝行列Ｂの左部分（Ｂのｎ列）、
Ｂ１＝行列Ｂの右部分（Ｂのｍ−ｎ列）、
ｄ０＝ベクトルｄの上部（ｎビット）、
ｄ１＝ベクトルｄの下部（ｍ−ｎビット）
方程式ＸＩＩの右側に項＋Ｂ１ｃ及び−Ｂ１ｃを導入し、さらに、因数分解をすると、下記の方程式ＸＩＩＩが得られる。
【００４７】
方程式ＸＩＩＩ
ｃ＝（Ａ＋Ｂ１）ｃ＋Ｂ１（ｄ１−ｃ）＋Ｂ０ｄ０
行列Ａ及びＢ１は同じであり、従って、方程式ＸＩＩＩの項（Ａ＋Ｂ１）はゼロになる。従って、方程式ＸＩＩＩは、下記の方程式ＸＩＶに単純化することが可能である。
【００４８】
方程式ＸＩＶ
ｃ＝Ｂ１（ｄ１−ｃ）＋Ｂ０ｄ０
２つの項Ｂ１（ｄ１−ｃ）及びＢ０ｄ０は、それぞれ、２１６項目の大規模なルックアップ・テーブルで実施可能である。実施態様の１つでは、さらに詳細に後述するように、項Ｂ１（ｄ１−ｃ）及びＢ０ｄ０は、それぞれ、２８項目の２つのテーブルで実施可能である。
【００４９】
実装
事例３の３２ビットＣＲＣの例を利用すると、単一ルックアップ・テーブルは、それぞれ、４バイトからなる２３２の項目を備えることになるが、あまりに大きすぎて、プロセッサのキャッシュに記憶することができず、通常のメモリには重い負担になる。事例３及び事例４において上述のように、本発明の形態の１つでは、１つの大規模なルックアップ・テーブルを用いるのではなく、テーブルを分割して、全体が４つのより小規模なテーブルからなるようにする。まず、事例３の処理が行われ、引き続き事例４の処理が行われる。
【００５０】
事例３の場合、行列Ａを上記方程式ＩＸの行列Ｔに置き換えると、下記の方程式ＸＶが得られる。
【００５１】
方程式ＸＶ
ｃ＝Ｔ（ｃ＋ｄ）
ここで、
ｃ＝ｃ＝ＣＲＣ剰余レジスタ（ベクトル）、
ｄ＝処理すべき次のデータ・セット（ベクトル）、
Ｔ＝行列Ａ（及び、事例３の場合、Ａ＝Ｂのため、行列Ｂ）と同じ値の定数行列
図２Ａは、方程式ＸＶにおける行列の要素及びベクトルを例示したダイアグラムである。図２Ａに示すように、結果ベクトル（ｃ）２０２は、定数行列（Ｔ）２０４に変数ベクトル（ｃ＋ｄ）２０６を掛けた値に等しい。結果ベクトル２０２は、３２の要素ｃｉを含む１×３２ベクトルであり、ここで、ｉは０〜３１の範囲である。定数行列２０４は、１０２４の要素ｔｉ０〜ｔｉ３１を含む３２×３２行列であり、ｉは０〜３１の範囲である。変数ベクトル２０６は、３２の要素（ｃ０＋ｃ０）、（ｃ１＋ｄ１）、（ｃ２＋ｄ２）、．．．（ｃ３１＋ｄ３１）を含む１×３２ベクトルである。記号「＋」がＸＯＲ演算を表わすことを想起されたい。結果ベクトル２０２の各要素ｃｉは、下記の方程式ＸＶＩによって示される。
【００５２】
方程式ＸＶＩ
ｃｉ＝ｔｉ０＊（ｃ０＋ｄ０）＋ｔｉ１＊（ｃ１＋ｄ１）＋ｔｉ２＊（ｃ２＋ｄ２）＋．．．＋ｔｉ３０＊（ｃ３０＋ｄ３０）＋ｔｉ３１＊（ｃ３１＋ｄ３１）
図２Ａに示すように、定数行列２０４は、４つの行列部分Ｔ１〜Ｔ４に分割することが可能である。４つの行列部分Ｔ１〜Ｔ４には、それぞれ、８列と３２行（すなわち、２５６の要素）が含まれている。図２Ｂは、方程式ＸＶの行列の要素及びベクトルを例示したダイアグラムであり、行列部分Ｔ１〜Ｔ４が、それぞれ、独立した８×３２の定数行列２０４Ａ〜２０４Ｄとして示されている。図２Ｂに示すように、変数ベクトル２０６（図２Ａ）は、４つの８ビット変数ベクトル２０６Ａ〜２０６Ｄに分割されている。従って、図２Ａに示すように、１つの行列乗算を実施するのではなく、図２Ｂに示すように、４つの行列乗算が実施される。４つの行列乗算は、定数行列と８ビット変数ベクトルの乗算であり、結果として、４つの３２ビット結果ベクトルが得られる。次に、４つの３２ビット結果ベクトルが加えられる。
【００５３】
４つの３２ビット結果ベクトルは、Ｃａ、Ｃｂ、Ｃｃ、及び、Ｃｄとして識別される。結果ベクトルＣａ、Ｃｂ、Ｃｃ、及び、Ｃｄのそれぞれには、それぞれ、３２の要素Ｃａｉ、Ｃｂｉ、Ｃｃｉ、及び、Ｃｄｉが含まれており、ここで、ｉは０〜３１の範囲である。結果ベクトルＣａに関する要素は、下記の方程式ＸＶＩＩによって示される。
【００５４】
方程式ＸＶＩＩ
Ｃａｉ＝ｔｉ０＊（ｃ０＋ｄ０）＋ｔｉ１＊（ｃ１＋ｄ１）＋．．．ｔｉ７＊（ｃ７＋ｄ７）
結果ベクトルＣｂに関する要素は、下記の方程式ＸＶＩＩＩによって示される。
【００５５】
方程式ＸＶＩＩＩ
Ｃｂｉ＝ｔｉ８＊（ｃ８＋ｄ８）＋ｔｉ９＊（ｃ９＋ｄ９）＋．．．ｔｉ１５＊（ｃ１５＋ｄ１５）
結果ベクトルＣｃに関する要素は、下記の方程式ＸＩＸによって示される。
【００５６】
方程式ＸＩＸ
Ｃｃｉ＝ｔｉ１６＊（ｃ１６＋ｄ１６）＋ｔｉ１７＊（ｃ１７＋ｄ１７）＋．．．ｔｉ２３＊（ｃ２３＋ｄ２３）
結果ベクトルＣｄに関する要素は、下記の方程式ＸＸによって示される。
【００５７】
方程式ＸＸ
Ｃｄｉ＝ｔｉ２４＊（ｃ２４＋ｄ２４）＋ｔｉ２５＊（ｃ２５＋ｄ２５）＋．．．ｔｉ３１＊（ｃ３１＋ｄ３１）
Ｃａｉ＋Ｃｂｉ＋Ｃｃｉ＋Ｃｄｉ（すなわち、方程式ＸＶＩＩ、ＸＶＩＩＩ、ＸＩＸ、及び、ＸＸからの結果の加算）の結果は、Ｃｉ（すなわち、方程式ＸＶＩの結果）に等しい。従って、図２Ｂに示す４つの行列乗算の和は、図２Ａに示す単一定数行列２０４を用いたもとの計算結果と同じになる。
【００５８】
４つの行列乗算のそれぞれは、定数行列に８ビット変数ベクトルを掛けた値であるので、４つの乗算のそれぞれに、あらかじめ計算されたルックアップ・テーブルを利用することが可能である。各ルックアップ・テーブルは、２８の項目（２５６項目）を含んでおり、項目幅は４バイトである。従って、４つのルックアップ・テーブルは、全部で４キロバイトの記憶域を消費する。対照的に、単一ルックアップ・テーブルを用いた場合には、テーブルは、それぞれ４バイトからなる、２３２の項目を含むことになり、１６ギガバイトを消費することになる。
【００５９】
事例４の場合、方程式ＸＩＶの２つの項Ｂ１（ｄ１−ｃ）及びＢ０ｄ０は、それぞれ、２１６の項目からなる大規模なテーブルで実施可能である。実施態様の１つでは、項Ｂ１（ｄ１−ｃ）及びＢ０ｄ０は、全部で４つのルックアップ・テーブルについて、それぞれ、２８の項目からなる２つのテーブルで実施可能である。４つのルックアップ・テーブルで項Ｂ１（ｄ１−ｃ）及びＢ０ｄ０を実施するため、行列Ｂ０及びＢ１は、それぞれ、８列からなる２つの行列に分割され、ベクトル（ｄ１−ｃ）及びｄ０のそれぞれが、２つの８ビット・ベクトルに分割される。
【００６０】
事例４に関するコンピュータ・コードは、ＣＲＣビットと入力データ・ワードの正しいビットとのＸＯＲを必要とする。１６ビットＣＲＣと３２ビット・データ・ワードの事例を取り上げてみることにする。ＣＲＣベクトルは１６ビットであるため、ルックアップ・テーブルは、３２ビットではなく、１６ビット幅にすることが可能であるが、各項目の下位の１６ビットを０にして、３２ビット値をテーブルに保持するのが効率的に有利である可能性がある。例えば、テーブル値が１６ビット幅で、データ・ワードの最上位ビット（ＣＲＣ多項式の観点から）が、データ・ワードの上位ビットにあれば、ＸＯＲの実施前に、ＣＲＣとデータ・ワードの上位バイトのアライメントをとるため、シフトする必要がある。
【００６１】
対照的に、テーブル内の項目が、３２ビット幅で、ＣＲＣ結果ビットが上位の１６ビットをなし、０が下位１６ビットをなしている場合、ＣＲＣ値は、３２ビットワードの右位置とアライメントのとれた状態に保たれるので、シフトは不要になる。事例４のこの実施態様の場合、ＣＲＣレジスタには、１６ビットの現在のＣＲＣ値と１６の０ビットが記憶される。３２ビット・データ・ワードとＣＲＣレジスタの３２ビットに対してＸＯＲが実施される。ＸＯＲ演算の結果に基づいて、ルックアップ・テーブルから値の検索が行われる。次に、ルックアップ・テーブルから検索された値に対してＸＯＲ演算が実施され、その結果をＣＲＣレジスタに記憶することによって、現在の１６ビットＣＲＣ値が更新される。
【００６２】
図３は、本発明の実施態様の１つに従ってＣＲＣを計算するためのシステム３００を例示したブロック図である。本発明の形態の１つにおいて、システム３００は、コンピュータまたは同様の装置である。システム３００には、全て、通信リンク３０４を介して、互いに通信可能に結合された、プロセッサ３０２、入力／出力（Ｉ／Ｏ）インターフェイス３０６、及び、メモリ３０８が含まれている。システム３００は、Ｉ／Ｏインターフェイス３０６を介して、ＣＲＣ保護データ・メッセージ（例えば、データ・メッセージ３１２）の送受信を行う。
【００６３】
メモリ３０８には、揮発性メモリ・コンポーネントと不揮発性メモリ・コンポーネントの両方を含むことが可能である。揮発性コンポーネントは、電力の損失時に、データ値を保存しないものである。不揮発性コンポーネントは、電力の損失時に、データを保存するものである。従って、メモリ３０８には、例えば、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、ハードディスク・ドライブ、関連フロッピ・ディスク・ドライブを介してアクセスされるフロッピ・ディスク、コンパクト・ディスク・ドライブを介してアクセスされるコンパクト・ディスク、適正なテープ駆動機構を介してアクセスされる磁気テープ、及び／または、他のメモリ・コンポーネント、または、これらのメモリ・コンポーネントの任意の２つ以上の組み合わせを含むことが可能である。さらに、ＲＡＭには、例えば、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）、または、磁気ランダム・アクセス・メモリ（ＭＲＡＭ）、及び、他のこうしたデバイスを含むことが可能である。ＲＯＭには、例えば、プログラマブル読み取り専用メモリ（ＰＲＯＭ）、消去可能ＰＲＯＭ（ＥＰＲＯＭ）、電気的に消去可能なＰＲＯＭ（ＥＥＰＲＯＭ）、または、他の同様のメモリ素子を含むことが可能である。
【００６４】
メモリ３０８には、ＣＲＣアルゴリズム３１０、データ・メッセージ３１２、及び、ルックアップ・テーブル３２２Ａ〜３２２Ｄ（ルックアップ・テーブル３２２と総称される）が記憶されている。実施態様の１つでは、ＣＲＣ剰余レジスタ３１８は３２ビット・レジスタである。データ・メッセージ３１２には、複数の８ビット・データ・バイト３１４が含まれており、４つの連続したデータ・バイト３１４からなる各セット毎に、データ・ワード３１６を構成している。プロセッサ３０２には、現在のＣＲＣ剰余を記憶するプロセッサ・レジスタ（ＣＲＣ剰余レジスタ）３１８と、内部プロセッサ・キャッシュ３２０が含まれている。ルックアップ・テーブル３２２は、プロセッサ３０２によって利用される場合には（図３の点線で表示のように）、テーブル情報へのより効率の良いアクセスを可能にし、実行速度を高めるため、キャッシュ３２０にコピーされる。
【００６５】
実施態様の１つでは、ルックアップ・テーブル３２２Ａ〜３２２Ｄは、それぞれ、方程式ＸＶＩＩ〜ＸＸに基づいて生成される。ルックアップ・テーブル３２２Ａ〜３２２Ｄのそれぞれには、各項目が４バイト幅の、２５６の項目が含まれている。４つのルックアップ・テーブル３２２Ａ〜３２２Ｄは、従って、全部で４キロバイトの記憶域を消費する。
【００６６】
プロセッサ３０２は、ＣＲＣアルゴリズム３１０を実行して、データ・メッセージ（例えば、データ・メッセージ３１２）に処理を加え、対応するＣＲＣを生成する。データ・メッセージが、データの部分ワードで始まるか、終了する場合もある。こうした部分ワードにおけるバイトは、ワードのアライメントがとれないバイトまたはアライメントのずれたバイトと呼ばれる。例えば、３２ビット・ワードの場合、メモリの最初のワードまたは最後のワードには、完全なワード（すなわち、４バイト）ではなく、１、２、または、３バイトのデータが含まれる可能性がある。ＣＲＣアルゴリズム３１０の１つの実施態様では、従来の一度に１バイトずつの方法を用いて、アライメントのずれたバイトを処理し、次に、一度に１ワードずつの方法を用いてデータ・メッセージの完全なワードを処理する（例えば、上記事例３及び事例４参照）。大部分のデータ・メッセージは、ワード数が多いので、効率の劣る一度に１バイトずつの方法を利用して、データ・メッセージ毎にわずかなバイトを処理していたのでは、全体効率に及ぼす効果が小さくなる。システム３００については、図４に関連してさらに詳細に後述することにする。
【００６７】
図４は、本発明の実施態様の１つに従って、一度に１ワードずつデータ・メッセージ３１２を処理することによって、ＣＲＣの計算を行うための方法４００を例示した流れ図である。実施態様の１つでは、システム３００は、ＣＲＣアルゴリズム３１０の実行によって方法４００を実施するように構成されている。ステップ４０２では、プロセッサ３０２は、３２ビット・データ・ワードｄｗｏｒｄを検索する。ステップ４０４では、プロセッサ３０２は、検索したデータ・ワードｄｗｏｒｄとＣＲＣ剰余レジスタ（ｃ）３１８の内容に対してＸＯＲ演算を実施する。プロセッサ３０２は、ＸＯＲ演算の結果を一時的結果ｔとして記憶する。例示の実施態様の場合、一時的結果ｔは、４バイト値である。項ｔｎは、一時的結果ｔのｎ番目のバイトを表わすために用いられている。
【００６８】
ステップ４０６では、プロセッサ３０２は、ルックアップ・テーブル（Ｔ１）３２２Ａから、ステップ４０４で得られた一時的結果ｔの最初のバイトｔ１に対応する位置の値を検索する。従って、ステップ４０４におけるＸＯＲ演算結果の最初のバイトは、ルックアップ・テーブル３２２Ａに対する索引の働きをする。ルックアップ・テーブル３２２Ａから検索された値は、ＣＲＣ剰余レジスタ３１８に記憶される。
【００６９】
ステップ４０８では、プロセッサ３０２は、ルックアップ・テーブル（Ｔ２）３２２Ｂから、ステップ４０４で得られた一時的結果ｔの２番目のバイトｔ２に対応する位置の値を検索し、検索した値とＣＲＣ剰余レジスタ３１８の内容に対してＸＯＲ演算を実施する。ＸＯＲ演算結果は、ＣＲＣ剰余レジスタ３１８に記憶される。
【００７０】
ステップ４１０では、プロセッサ３０２は、ルックアップ・テーブル（Ｔ３）３２２Ｃから、ステップ４０４で得られた一時的結果ｔの３番目のバイトｔ３に対応する位置の値を検索し、検索した値とＣＲＣ剰余レジスタ３１８の内容に対してＸＯＲ演算を実施する。ＸＯＲ演算結果は、ＣＲＣ剰余レジスタ３１８に記憶される。
【００７１】
ステップ４１２では、プロセッサ３０２は、ルックアップ・テーブル（Ｔ４）３２２Ｄから、ステップ４０４で得られた一時的結果ｔの４番目のバイトｔ４に対応する位置の値を検索し、検索した値とＣＲＣ剰余レジスタ３１８の内容に対してＸＯＲ演算を実施する。ＸＯＲ演算結果は、ＣＲＣ剰余レジスタ３１８に記憶される。
【００７２】
ステップ４１４では、プロセッサ３０２は、データ・メッセージ３１２に、さらに処理すべきデータが存在するか否かを判定する。さらにデータが存在すれば、方法４００は、ステップ４０２に戻り、メッセージ３１２内の次のデータ・ワード３１６を処理する。それ以上処理すべきデータがなければ、方法４００は、ステップ４１６で示されるように終了する。
【００７３】
従って、方法４００の実施態様の１つを要約すると、この方法の各繰り返し中に、プロセッサ３０２が、データ・ワードとＣＲＣ剰余レジスタ３１８の現在の内容に対してＸＯＲを実施する。プロセッサ３０２は、次に、ＸＯＲ結果の各バイト毎に１つずつ、４つのテーブル値を取り出す。プロセッサ３０２は、４つのテーブル値相互間にＸＯＲを施して、次のＣＲＣ結果が得られるようにする。
【００７４】
通常の当該技術者には明らかなように、本発明のコンポーネントは、１つ以上のコンピュータ可読媒体上にソフトウェアとして存在することが可能である。本明細書において用いられるコンピュータ可読媒体という用語は、フロッピ・ディスク、ハード・ディスク、ＣＤ−ＲＯＭ、フラッシュ・メモリ、読み取り専用メモリ（ＲＯＭ）、及び、ランダム・アクセス・メモリのような、任意の種類の揮発性または不揮発性のメモリを含むものと定義される。
【００７５】
本発明の形態の１つでは、１つの極めて大規模なルックアップ・テーブルを利用して、ＣＲＣ計算のために、一度に２バイト以上の処理を行うのではなく、少数の小規模なルックアップ・テーブルが利用される。実施態様の１つでは、ルックアップ・テーブルは、計算中、プロセッサのキャッシュに保持するのに十分なほど小規模であり、これが、効率の維持にとって重要である。本発明の形態の１つによれば、ＣＲＣ計算に関するソフトウェア実施例の速度が速くなる。本発明の形態の１つによる方法では、ＣＲＣ計算に関するプロセッサの負荷が軽減される。本発明の他の実施態様は、暗号アルゴリズムのいくつかにおけるように、モジュロ２の多項式計算がソフトウェアにおいて利用される他の領域に適用可能である。
【００７６】
本明細書において解説の一度に１ワード式のＣＲＣ方法の実施態様の１つを実施するテスト・コードが開発されている。このテスト・コードは、３２ビットのデータ・ワードを処理し、各項目の幅がＣＲＣと同じ（すなわち、３２ビット）である、２５６の項目を備えた４つのテーブルを利用するものであった。これらのテーブルは、プロセッサのキャッシュに保持するのに十分なほど小規模であった。そして、従来のコードにおいて用いられる多くの操作は、シフト操作、及び、ＸＯＲ演算の半分といった、このテスト・コードにおいて不要のため、このテスト・コードでは、従来の一度に１バイト式の方法に基づくコードで必要とされるサイクルの約半分のサイクルでＣＲＣの計算が行われた。
【００７７】
望ましい実施態様の解説のため、特定の実施態様について例示し、説明してきたが、通常の当該技術者であれば明らかなように、本発明の範囲を逸脱することなく、図示し、解説された特定の実施態様の代わりに、多種多様な代替及び／または同等実施例を用いることも可能である。本出願は、本明細書において論考の望ましい実施態様のいかなる改変または変更をも包含することを意図したものである。従って、本発明が、請求項及びその同等物による制限しか受けないことを意図したものであることは明白である。
【図面の簡単な説明】
【００７８】
【図１】一度に１バイトずつデータ・メッセージを処理することによってＣＲＣを計算するための先行技術による方法を例示した流れ図である。
【図２Ａ】状態遷移方程式の形態の１つで行列及びベクトルの要素を例示したダイアグラムである。
【図２Ｂ】図２Ａに示す行列が４つの個別行列に分割された、状態遷移方程式の形態の１つで行列及びベクトルの要素を例示したダイアグラムである。
【図３】本発明の実施態様の１つに従ってＣＲＣを計算するためのシステムを例示したブロック図である。
【図４】本発明の実施態様の１つに従って、一度に１ワードずつデータ・メッセージを処理することによって、ＣＲＣの計算を行うための方法を例示した流れ図である。
【符号の説明】
【００７９】
３００  計算システム
３０２  プロセッサ
３０８、３２０  メモリ
３１２  データ・メッセージ
３１６  マルチバイト値（ワード）
３１８  現在のＣＲＣ値
３２２Ａ〜Ｄ  ルックアップ・テーブル
【図１】
2005006298.tif 000003
【図２Ａ】
2005006298.tif 000004
【図２Ｂ】
2005006298.tif 000005
【図３】
2005006298.tif 000006
【図４】
2005006298.tif 000007