(57)【要約】      （修正有）【課題】ＣＲＣで保護された大きなデータパケットを効率的に検出する方法及び装置を提供する。【解決手段】新たなデータを追加しつつ古いデータの効果を除去することによって、ＣＲＣで保護されたデータパケットのデータストリームから計算された巡回冗長検査符号（ＣＲＣ）のチェックサムを更新し、所定の結果と照合することにより、ＣＲＣで保護されたデータパケットを見付ける装置及び方法。本装置は、データストリームを記憶するための長さｍのメモリと、ＣＲＣチェックサムを計算するための長さｎのアキュムレータと、アキュムレータから出力されるデータを所定のＣＲＣ多項式を用いてアキュムレータへフィードバックさせる剰余回路と、メモリから出力されるデータの効果をアキュムレータから除去するための減算回路とを備える。ＣＲＣチェックサム検証回路はＣＲＣチェックサムをＣＲＣで保護されたデータパケットがあることを示す有効な結果と照合する。【選択図】図３
2005160074.tif 000002
【特許請求の範囲】
【請求項１】
古いデータの効果を除去しつつ新たなデータを加算することによって、巡回冗長検査符号（ＣＲＣ）で保護されたパケットのデータストリームから計算されたＣＲＣチェックサムを更新するステップ（６）と、
前記更新されたＣＲＣチェックサムを所定の結果と照合するステップ（８）と、
からなる方法。
【請求項２】
前記ＣＲＣチェックサムを計算するために、長さｍのバッファ（１０２）及び長さｎのアキュムレータ（１１４）を初期化するステップと、
前記データストリームを前記長さｍのバッファ（１０２）に記憶するステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記新たなデータを加算するステップは、前記アキュムレータ（１１４）と所定のフィードバックＣＲＣ多項式（１１０）との間で排他的論理和演算（１２０）を実施することを含む、請求項２に記載の方法。
【請求項４】
前記古いデータの効果を除去するステップは、前記アキュムレータ（１１４）と、前記長さｍのバッファ（１０２）の最上位ビットに対応するｍ乗まで外挿された所定のＣＲＣ多項式（１０８）との間で排他的論理和演算（１２２）を実施することを含む、請求項２〜３のうちのいずれか一項に記載の方法。
【請求項５】
前記長さｍのバッファ（１０２）及び前記長さｎのアキュムレータ（１１４）が、一回しか初期化されないように構成される、請求項２〜４のうちのいずれか一項に記載の方法。
【請求項６】
長さｍのバッファ（１０２）及び長さｎのアキュムレータ（１１４）を初期化するステップと、
長さｍのデータストリームを前記バッファ（１０２）に記憶するステップと、
前記長さｍのデータの余りをビット単位で前記長さｎのアキュムレータ（１１４）の中に蓄積するステップと、
ｍ乗まで外挿された長さｎの所定のＣＲＣ多項式（１０８）を前記長さｎのアキュムレータ（１１４）に結合するステップと、
前記長さｎの所定のＣＲＣ多項式（１１０）を前記長さｎのアキュムレータ（１１４）に結合するステップと、
前記アキュムレータが所定結果（１１６）になったか否かを検査するステップと、
からなる方法。
【請求項７】
前記長さｎのＣＲＣ多項式（１１０）を結合するステップは、前記長さｎのアキュムレータ（１１４）と、前記長さｎの所定のＣＲＣ多項式（１１０）中の有効ビットに対応する前記長さｎのＣＲＣ多項式（１１０）との間で、排他的論理和演算（１２０）を実施することを含み、
前記ｍ乗まで外挿された長さｎのＣＲＣ多項式（１０８）を前記長さｎのアキュムレータ（１１４）に結合するステップは、前記長さｎのアキュムレータ（１１４）と、前記ｍ乗まで外挿された長さｎのＣＲＣ多項式（１０８）との間で、排他的論理和演算（１２２）を実施すること含む、請求項６に記載の方法。
【請求項８】
ＣＲＣで保護されたデータパケットをスキャンするためのレシーバであって、
データストリームを記憶する為の長さｍのメモリ（１０２）と、
前記データからのＣＲＣチェックサムを蓄積するための長さｎのアキュムレータ（１１４）と、
前記アキュムレータ（１１４）から出力されたデータを所定のＣＲＣ多項式（１１０）に基づいて前記アキュムレータ（１１４）へフィードバックさせるための剰余回路（１２０）と、
前記メモリ（１０２）から出力されたデータの効果を前記アキュムレータ（１１４）から除去するための減算回路（１１２）と、
前記ＣＲＣチェックサムをＣＲＣで保護されたデータパケットが見付かったことを示す結果と照合するためのＣＲＣチェックサム検証回路（１１６）と、
からなるレシーバ。
【請求項９】
前記レシーバに電力が供給されたときに、前記長さｍのメモリ（１０２）及び前記長さｎのアキュムレータ（１１４）が所定の値に初期化（１１８）されるように構成される、請求項８に記載のレシーバ。
【請求項１０】
前記減算回路（１２２）は、第ｍ番目の項まで外挿された所定のＣＲＣ多項式（１０８）を含み、前記外挿されたＣＲＣ多項式（１０８）及び前記アキュムレータ（１１４）を用いて排他的論理和演算（１２２）が実施される、請求項８または請求項９に記載のレシーバ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は誤り訂正及び信号検出に関し、詳しくは、本発明はデータストリームの中から有効な巡回冗長検査符号（ＣＲＣ）で保護されたデータブロックを探し出す方法に関する。
【背景技術】
【０００２】
データストリーム中の誤りの検出及び訂正を容易にするために、データは一般にＣＲＣ符号のような周知の符号で符号化される。例えば、ＡＴＭセルを運ぶデータストリームでは、有効なヘッダＣＲＣを検出することによりＡＴＭセルを識別することができる。
【０００３】
図１は、ｎビットのＣＲＣで保護されたデータパケットを探し出すための従来の方法及び装置を示す図である。ただし、ｎは一般に８、１６、３２等である。レシーバ１０は外部ソースからデータ入力を受ける。外部ソースとは、ネットワーク接続を介して得られるデータストリームであっても、ディスクドライブから読み込んだデータストリームであっても、他の何らかのシリアルデータストリームであっても良い。
【０００４】
ブロック境界が明確であることを前提として、受信された入力データは一般に機械に記憶される。機械とは、例えば受信データをバッファ２４その他の適当な記憶装置に記憶するコンピュータシステム等である。次の処理によって受信データが他の目的のためにディスクその他の記憶装置に記憶される前に、データストリーム中の所定サイズのブロックが特定数だけバッファ２４の中に維持される。
【０００５】
一般に、データがビット単位のストリームとして装置に届くと、ＣＲＣアキュムレータ１２がそのデータの和を計算する。新たなデータブロックを検査して有効なＣＲＣがあるか否かを確かめる度に、アキュムレータ１２が処理１４によってリセットされる。図１に示した各ブロックは説明目的のものであり、それらのブロックを実現する回路は周知であるから、詳しい説明はしないものとする。バイト単位の実施形態の概念はビット単位の実施形態と同様であり、同様の処理が行なわれるので、ここで説明はしない。
【０００６】
データブロックの終わりで、累積された和が処理１６によって検査される。ＣＲＣアキュムレータ１２は各データブロックの入力開始時にクリアすなわちリセットされる。そして、所定サイズのデータブロックの終わりでＣＲＣアキュムレータの値が検査され、その値が用途に応じて異なる有効な値になっているか否かが確認される。
【０００７】
入力されたデータの各ビットがＣＲＣアキュムレータ１２の中でシフトされていくのに従って、長さｎのＣＲＣアキュムレータ１２の右端から新たなデータビットが入力され、アキュムレータ１２の左端から第ｎ番目のビットがシフトアウトされる。シフトアウトされた第ｎ番目のビットは、アキュムレータ１２へフィードバックされる。出力された第ｎ番目のビットは、ＣＲＣアキュムレータＲ（０）〜Ｒ（ｎ−１）においてさらに少数のビットの組み合わせで表現される。これは用途やビット長に応じて選択された長さｎの標準的なＣＲＣ固定多項式２０を用いて実施される。長さｎのＣＲＣ固定多項式２０は、選択された長さｎのＣＲＣ固定多項式２０に応じて異なるビット単位の排他的論理和演算２２により、長さｎのＣＲＣアキュムレータ１２に結合される。選択された長さｎのＣＲＣ固定多項式２０の有効ビットに対応する論理ゲートは、１の補数の加算を実施して、長さｎのＣＲＣ固定多項式２０をＣＲＣアキュムレータ１２に結合する。１の補数の加算はビット単位の排他的論理和演算に等しい。処理１６において有効な累積和が検出されると、システムはスキャンを続行して有効な累積和を持つ他のデータブロックを探す。例えば、非同期転送モード（ＡＴＭ）の場合、ＨＥＣ（ヘッダエラー制御）と呼ばれる有効な５バイトのヘッダが検出されたとき、同期を宣言する前に、ＡＴＭセルのセル長（例えば５３バイト）だけ間隔を空けた所定数（約７個）の予測位置において有効ヘッダをさらに検出しなければならない。その後システムはスキャンを続行して同期の喪失を検出するが、そのときも、同期の喪失を宣言する前に、所定数の無効ＨＥＣコードを検出しなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
標準的なＡＴＭヘッダの長さは５バイトしかないが、従来の方法及び装置は処理の難しい比較的大きなデータブロックすなわちセルを有するため、必要とされる回路が大型化及び複雑化している。したがって、高速データストリームの中からＣＲＣで保護されたもっと大きなデータパケットを効率的に検出する方法及び装置が必要とされている。
【課題を解決するための手段】
【０００９】
本発明の一態様は、ＣＲＣで保護された様々なサイズのデータブロックを効率的に見つけ出す方法及び装置を提供する。
【００１０】
本発明の一態様は、古いデータの効果を除去しつつ新たなデータを加算することにより、ＣＲＣで保護されたパケットのデータストリームから計算された巡回冗長検査符号（ＣＲＣ）のチェックサムを更新し、更新されたＣＲＣチェックサムが所定の結果であるか否かを検査する方法を提供する。
【００１１】
本発明の一態様は、データストリームをスキャンしてＣＲＣで保護されたパケットを探し出す方法を提供する。この方法は、データストリームを受信するステップと、該データストリームを蓄積してＣＲＣチェックサムを計算するステップとを含む。アキュムレータ内のＣＲＣチェックサムは、データがさらに受信されるのに従ってその新たなデータを加算するとともに古いデータを減算し、ＣＲＣチェックサムが所定の結果になったか否かを検査することによって更新される。
【００１２】
本発明の他の態様は、通信に使用されるネットワークに適合する方法を提供する。
【００１３】
本発明の他の態様は、データストリームをスキャンしてＣＲＣで保護されたデータブロックを探し出すシステムを提供する。このシステムは、データストリームを受信し、該データストリームを記憶して該データストリームのＣＲＣチェックサムを蓄積する。ＣＲＣチェックサムは、排他的論理和機能を用いて新たなデータを加算するとともに古いデータを減算することによって調節される。排他的論理和機能をアキュムレータ及びアキュムレータと同じ長さを持つ所定のＣＲＣ固定多項式に適用することによって、新たなデータが加算される。排他的論理和機能をアキュムレータ及び前記所定のＣＲＣ固定多項式を一時的にバッファに記憶された第ｍ番目の項（ｍはＣＲＣで保護されたデータブロックのサイズ）まで外挿したものに適用することにより、ＣＲＣアキュムレータから古いデータの効果が除去される。調節されたＣＲＣチェックサムは所定結果の値と比較され、それが一致すると、有効なＣＲＣで保護されたデータブロックがバッファ内に存在することが分かる。
【００１４】
本発明のさらに他の態様は、ＣＲＣで保護されたデータパケットをスキャンするレシーバを提供する。このレシーバは、データストリームを記憶する長さｍのメモリと、該データから得られたＣＲＣチェックサムを蓄積する長さｎのアキュムレータとを含む。レシーバは、アキュムレータから出力されたデータを所定のＣＲＣ固定多項式を用いてアキュムレータへフィードバックする剰余回路と、メモリから出力されたデータの効果をアキュムレータから除去するための減算回路とを含む。ＣＲＣチェックサム検証回路は、ＣＲＣチェックサムを検査して、ＣＲＣで保護されたデータパケットが見付かったことを示す有効な結果があるか否かを確認する。
【００１５】
上記の態様及び利点、並びに他の態様及び利点は、添付の図面を参照して、以下の説明及び特許請求の範囲に記載する構成及び動作から明らかになるであろう。図面において同じ符号は同じ要素を示している。
【発明を実施するための最良の形態】
【００１６】
図２は、データストリームの中からＣＲＣで保護されたデータを探し出す方法を示すフロー図である。処理６では、受信したデータストリームに基づいてＣＲＣ（巡回冗長検査符号）チェックサムを更新することにより、ＣＲＣチェックサムを維持する。ＣＲＣチェックサムは、新たなデータを加算しつつ古いデータの効果を除去することによって、ＣＲＣで保護されたデータパケットを含むデータストリームから計算される。処理８では、更新されたＣＲＣチェックサムを所定の結果と照合する。ＣＲＣチェックサムが所定の結果に一致すると、ＣＲＣで保護されたデータパケットが見付かったことになり、そのデータパケットを出力して更に処理及び操作を実施する。ＣＲＣは、文脈に応じて、あるいは数学的類似性を優先させて、剰余、係数、シンドローム、又は和（サム）と呼ばれることもある。それらの用語は周知のものであり、本発明ではそれらの用語を代替可能に使用する。同じ意味を持つ用語群としてはその他に、「累乗、ビット、及び項」、「データパケット、データブロック、及びセル」などがある。
【００１７】
図３は、データストリームの中からＣＲＣで保護されたデータパケットを探し出すための本発明の一実施形態による方法及び装置を示すブロック図である。図３において、装置１３０に電力を供給すると、バッファ１０２及びＣＲＣアキュムレータ１１４が処理１１８によって初期値にリセットされ、バッファ１０２およびＣＲＣアキュムレータ１１４が共に作動する。レシーバ１００がシリアルデータストリームを受信すると、長さｍのバッファ１０２はそのデータストリームを後の使用に備えて記憶する。データがバッファ１０２に流れ込むとき、同時に、そのデータはビット単位でＣＲＣアキュムレータ１１４にも入力される。バッファ１０２は、シフトレジスタ、スタック又はＲＡＭといった任意のデータ記憶装置であってよい。
【００１８】
ＣＲＣアキュムレータ１１４は、選択されたＣＲＣの長さに応じてｎビットの長さを有する。例えば、ＣＲＣ−８、ＣＲＣ−１６ａ、またはＣＲＣ−３２といった標準的な固定多項式を選択した場合、その長さはそれぞれ８、１６、３２ビットである。ＣＲＣアキュムレータ１１４から変数Ｘ（ｎ）で示す第ｎ番目のビット１１２がシフトアウトされると、新たなデータビットがＣＲＣアキュムレータ１１４に入力される。第ｎ番目のビット１１２は、第ｎ番目のビットの残りを表す長さｎのＣＲＣ多項式１１０に変換される。長さｎのＣＲＣ多項式１１０は、その長さｎのＣＲＣ多項式１１０に対応する有効ビットを用いて、排他的論理和演算１２０によりアキュムレータ１１４に加算される。長さｎのＣＲＣ多項式１１０は標準的なＣＲＣ固定多項式であり、その長さは、用途に応じて所望の長さにしてよい。
【００１９】
第ｎ番目のビット１１２がシフトアウトされるとき、その第ｎ番目のビット１１２の効果が、排他的論理和ゲート１２０によってアキュムレータ１１４に加えられ、データバッファ１０２から出力された図３に変数Ｘ（ｍ）として示す最上位ビット１０６の効果が、アキュムレータ１１４から除去１２２される。この除去処理は、同じ長さｎのＣＲＣ多項式をｍ乗まで外挿し、外挿したＣＲＣ多項式１０８をＣＲＣアキュムレータ１１４と排他的論理和演算１２２することにより実施される。このようにしてアキュムレータ内の残りを更新すると、データストリーム中の離れた２つのポイント間でデータ表現が維持される。１の補数加算と１の補数減算は、数学的には同じ演算であり、一般的にビット単位の排他的論理和演算と呼ばれる。従って、図３ではプラス演算１２０及びマイナス演算１２２として描かれているが、それらの演算はいずれも、排他的論理和演算として実施される。
【００２０】
データブロックの境界を検出するために、ＣＲＣアキュムレータ１１４は処理１１６において有効なアキュムレータ和定数になっているか否かが常に検査される。例えば、ＡＴＭは剰余類値０ｘ５５（１６進数）を有効和として使用することが多い。データ変数を定数と比較するのに必要なロジックは周知であり、ここでは説明しないものとする。
【００２１】
本発明は、概念的にはたった３つの演算しか実施しない。すなわち、入力されたものを現在の値に加算する演算、出力されるものを現在の値から減算する演算、及び現在の値を維持・更新する演算である。そのため、ロジック・リソースを効率的に利用することができる。例えば、ＡＴＭ  ＨＥＣの場合、従来の方法は、４０ビットをパラレルハードウェアで８ビット和に加算することによってデータストリームをスキャンしているため、ハードウエア実施形態の場合には４０×８のゲートアレイが必要であった。本発明によれば、これを３×８のゲートアレイにまで減らすことができる。本発明をＡＴＭネットワークで実施する場合、本発明はＡＴＭの物理層に配置することができるが、ＡＴＭ層で実施することもできる。
【００２２】
ＣＲＣで保護されるパケットが比較的大きい用途の場合、この利点は劇的に大きくなる。本発明のこの実施形態によれば、データブロックがどのようなサイズであっても、アキュムレータロジックの要件は３×ｎのゲート（ｎはＣＲＣ長）に維持される。データブロックのサイズが大きくなっても、パケットバッファ・メモリのサイズが増大するだけである。本発明を実施してコストを削減すれば、さらに強力なＣＲＣ符号やＦＥＣ符号を使用することが可能になる。
【００２３】
本発明は、ハードウエアで実施してもソフトウエアで実施してもよい。ＣＲＣ符号による符号化のハードウェア実施形態は当該技術分野で周知のものであるから、詳しい説明はしない。例えば、１９９０年１２月１８日にＣｈｅｕｎｇ他に付与された米国特許第４，９７９，１７４号を参照して欲しい。また、ソフトウエアによる符号化も周知であり、図示及び説明した方法をもとにして任意の適当なソフトウエア言語の文法を使用することができるので、具体的な説明は省略する。本発明をソフトウェアで実施することができるシステムには、本発明のプロセス及びデータ構造を記憶させ、配布することが出来る磁気ディスク、光ディスク、ＲＡＭ、ＲＯＭ、ＦＲＯＭ、ＥＥＰＲＯＭ等のような永久（持続性）記憶装置および着脱式記憶装置が含まれる。また、プロセスは、例えばＬＡＮ、ＷＡＮ、ＷＬＡＮ又はインターネット等のネットワークの一部を通じて配信することもできる。
【００２４】
ブロック１００でデータストリームが受信され、そのデータがバッファ１０２に記憶されるとともにアキュムレータ１１４にも蓄積されるものと仮定した場合、バッファ１０２がＣＲＣ付きのデータブロックを受け取ると、ＣＲＣアキュムレータ１１４の値は、有効和（例えばＡＴＭ  ＨＥＣの場合、０ｘ５５）に瞬時に書き替えられる。ＣＲＣアキュムレータ１１４を流れる残りのデータは、フィードバックＣＲＣ多項式によってアキュムレータに結合される。この演算は、ＣＲＣアキュムレータ１１４からシフトアウトされたビット１１２を長さｎの所定のＣＲＣ多項式１１０を介してＣＲＣアキュムレータ１１４へフィードバックする排他的論理和演算として実施される。ＣＲＣアキュムレータ１１４は、ＣＲＣアキュムレータ１１４内を何度か巡回した古いデータのコピーをデータブロックバッファ１０２の中で移動させながら、ＣＲＣアキュムレータ１１４内のその古いデータの効果を除去するために、データバッファ１０２の端部からもう１つの入力を受ける。この古いデータは、ＣＲＣアキュムレータ１１４の中を通ってＣＲＣフィードバック・ループを巡回していたものなので、その効果がＣＲＣアキュムレータ１１４及びバッファ１０２に入力された時点と同じではない。例えば、スキャンの開始時にビット「１」がＣＲＣアキュムレータ１１４及びバッファ１０２に追加され、そのビット「１」が長さｎのＣＲＣ多項式１１０によるフィードバックをｍ回だけ巡回して、バッファ１０２内の最上位ビットが形成された場合、ＣＲＣアキュムレータ１１４の第ｍ番目のビットの効果は、第ｍ番目の項まで外挿された長さｎのＣＲＣ多項式１０８の値に等しい。従って、新たなビットがバッファ１０２に入力されると、バッファ１０２の左端から以前の第ｍ番目のビットが出力され、そのビットが「１」であれば、ｍ乗まで外挿された長さｎの所定のＣＲＣ多項式１０８が、ＣＲＣアキュムレータ１１４から減算１２２される。アキュムレータ１１４に最初に入力された以前の第ｍ番目のビットの効果は、そのビットがバッファ１０２内を通過して出力されるときに無効化される。従って、ＣＲＣアキュムレータ１１４は、バッファ１０２の境界内のデータだけからなる残りを表す状態に維持される。従って、データストリームをビット単位で検査して、有効なＣＲＣで保護されたデータブロックを探し出すことができる。本発明は、アキュムレータの値、古いデータビット、及び新たなデータビットを読み出し、検査中にアキュムレータを次のビットを表すように更新するための入力しか必要としないので、従来の方法に比べて必要とされるロジックが大幅に簡単になる。有効なＣＲＣで保護されたデータブロックが見付かると、その識別されたブロックは、記憶してもよいし、誤り訂正その他の処理を施してもよい。本発明は、ＦＥＣ（順方向誤り訂正）などの他の方法にも適合することが望ましい。
【００２５】
図４は、データストリームの中からＣＲＣで保護されたデータパケットをバイト単位の演算で見付けるための本発明の一実施形態による装置を示すブロック図である。図４において、ＣＲＣおよびデータパケットの長さは、バイト単位のシステムにおける処理効率を考えて、８ビットの倍数が選択される。バイト単位の誤り訂正システムはソフトウエアで実現されることが多いが、必ずしもソフトウェアで実施する必要はない。ＣＲＣレジスタ２１４は、図２に示したシステムにおけるＣＲＣアキュムレータ１１４と同じ機能を実施する。ＣＲＣレジスタ２１４およびバッファ２０２は、システム２３０の電源投入時すなわち使用開始時に処理２１８によってリセットするだけでよく、各データブロックのＣＲＣを検査するたびにリセットする必要はない。レシーバ２００がデータソースからデータを受信すると、そのデータは、メモリバッファ２０２に記憶されるとともに、ＣＲＣレジスタ２１４の中へ流れ込む。ＣＲＣレジスタ２１４から１バイトがシフトアウトされると、その１バイトは、２５６×８Ｎの所定のＣＲＣテーブルから排他的論理和演算２２０によって取得されたＮバイトのＣＲＣ多項式によるフィードバックにより、再びアキュムレータに加算される。同時に、ＣＲＣレジスタ２１４に入力された以前の第ｍ番目のバイトに対応するメモリ２０２内の最上位バイトの効果が、ｍ乗まで外挿された２５６×８Ｎの所定のＣＲＣルックアップテーブルから取得されたＮバイトのＣＲＣ多項式に基づいて、ＣＲＣレジスタ２１４の対応する各バイトに排他的論理和演算２２２を適用することにより、アキュムレータ１１４から除去される。処理２１６において、ＣＲＣレジスタ２１４を連続的にスキャンし、有効なＣＲＣチェックサムを探す。処理２１６においてＣＲＣレジスタ２１４内のＣＲＣチェックサムが所定の結果に一致した場合、ＣＲＣで保護されたデータパケットが見つかったことになり、そのデータパケットを出力して更に処理及び操作を実施する。
【００２６】
ＡＴＭ  ＨＥＣにおける本発明のＶＨＳＩＣハードウエア記述言語（ＶＨＤＬ）試験設定の一例では、Ｉ．４３２規格のＣＲＣ多項式が使用された。入力データは、第１のビットＸ（０）に加算され、Ｉ．４３２多項式Ｘ８＝Ｘ３＋Ｘ＋１を用いて累積される。４０ビットのヘッダ・バッファから出力されるデータは、Ｘ４０＝Ｘ６＋Ｘ５＋Ｘまで外挿された同じ多項式を用いて除去される。試験コードは以下の通りである。
【００２７】
Ｒｅｍａｉｎｄｅｒ（７）＜＝Ｒｅｍａｉｎｄｅｒ（６）
Ｒｅｍａｉｎｄｅｒ（６）＜＝Ｒｅｍａｉｎｄｅｒ（５）  ｘｏｒ  ＳｈｉｆｔＲｅｇ（３９）
Ｒｅｍａｉｎｄｅｒ（５）＜＝Ｒｅｍａｉｎｄｅｒ（４）  ｘｏｒ  ＳｈｉｆｔＲｅｇ（３９）
Ｒａｍａｉｎｄｅｒ（４）＜＝Ｒｅｍａｉｎｄｅｒ（３）
Ｒａｍａｉｎｄｅｒ（３）＜＝Ｒｅｍａｉｎｄｅｒ（２）
Ｒａｍａｉｎｄｅｒ（２）＜＝Ｒｅｍａｉｎｄｅｒ（１）  ｘｏｒ  Ｒｅｍａｉｎｄｅｒ（７）
Ｒａｍａｉｎｄｅｒ（１）＜＝Ｒｅｍａｉｎｄｅｒ（０）  ｘｏｒ  Ｒｅｍａｉｎｄｅｒ（７）ｘｏｒ  ＳｈｉｆｔＲｅｇ（３９）
Ｒａｍａｉｎｄｅｒ（０）＜＝ＤａｔａＩｎｐｕｔ  ｘｏｒ  Ｒｅｍａｉｎｄｅｒ（７）
ＳｈｉｆｔＲｅｇ（３９  ｄｏｗｎｔｏ  ０）＜＝ＳｈｉｆｔＲｅｇ（３８  ｄｏｗｎｔｏ  ０）＆  ＤａｔａＩｎｐｕｔ
【００２８】
この試験ＶＨＤＬコードは、４０ビットのシフトレジスタ中にあるデータが有効ＡＴＭヘッダを表すものである場合、剰余類値（０ｘ５５）に等しい余りを生成する。この例において、Ｒｅｍａｉｎｄｅｒ（  ）はアキュムレータ１１４中の１ビットを表す変数であり、ＳｈｉｆｔＲｅｇ（  ）は４０ビットのシフトレジスタ又はバッファ１０２中にある１ビットを表す変数である。ｘｏｒは排他的論理和演算であり、＜＝は代入演算子である。ステートメント（ｘ２、ｘ１、ｘ０）の右側にある“ｘｏｒ  Ｒｅｍａｉｎｄｅｒ（７）”１１２は、ＣＲＣ多項式に基づくアキュムレータ１１４へのフィードバック１１０を表し、“ｘｏｒ  ＳｈｉｆｔＲｅｇ（３９）”１０６は、外挿されたＣＲＣ多項式（ｘ６、ｘ５、ｘ１）１０８を表す。
【００２９】
上記のように、本発明は、データストリームを検査し、ＣＲＣで保護された任意サイズのデータセルまたはデータブロックを探し出す方法及び装置を提供する。例えば、２８８バイトのデータブロックをスキャンする場合、一回あたりのスキャンに２回の計算しか必要としない。従来の方法であれば、２８８回の計算が必要であった。２０４８バイトのブロックをスキャンする場合でも同様に、一回あたりのスキャンに２回の計算しか必要としない。従来の方法であれば、２０４８回の計算が必要であった。また、本発明は、スキャンのたびに初期化する必要がなく、電源投入時に一回だけ初期化すればよいことから、初期化に必要とされるロジックも単純になっている。本発明は、ハードディスクやテープなどからＣＲＣで保護されたデータブロックまたはセルを探し出すことの他に、ＷＡＮ、ＬＡＮ、またはＷＬＡＮのようなネットワーク通信にも利用することができる。
【００３０】
本発明の多数の特徴および利点は、発明の詳細な説明から明らかであろう。そして、特許請求の範囲に記載した発明は、それらの特徴および利点を本発明の思想および範囲内に収めることを意図している。また、当業者であれば多数の変形および変更を実施することも可能であり、本発明を図示説明した構成および動作に厳密に限定するつもりはない。適当な変形形態および均等はすべて本発明の範囲内である。
【図面の簡単な説明】
【００３１】
【図１】ＣＲＣを計算し、データストリームを検査して有効なＣＲＣを探し出すための従来の方法を示すブロック図である。
【図２】ＣＲＣで保護されたデータパケットを探し出すための本発明の一実施形態による方法の処理を示すフロー図である。
【図３】データストリームの中からＣＲＣで保護されたデータパケットを見付けるための本発明の一実施形態による装置を示すブロック図である。
【図４】バイト単位の処理によりデータストリームの中からＣＲＣで保護されたデータパケットを見付けるための本発明の一実施形態による装置を示すブロック図である。
【符号の説明】
【００３２】
１０２  バッファ
１０８、１１０  ＣＲＣ多項式
１１２  アキュムレータからシフトアウトされたビット
１１４  アキュムレータ
【図１】
2005160074.tif 000003
【図２】
2005160074.tif 000004
【図３】
2005160074.tif 000005
【図４】
2005160074.tif 000006