(57)【要約】【課題】ＦＩＦＯを通過するデータブロックにおいて発生する様々なタイプのビット誤りを検出する能力の高い誤り検出システムを提供する。【解決手段】上記課題は、ＦＩＦＯメモリから出力されるデータにおける誤りを検出する誤り検出システムであって、インバウンドデータストリームを受信し、前記インバウンドデータストリーム内のデータブロックに基づいて第１ＣＲＣ値を生成する第１ＣＲＣ生成器と、前記第１ＣＲＣ生成器に接続され、前記データブロック及び前記第１ＣＲＣ値を前記ＦＩＦＯに対して選択的に入力する装置と、アウトバウンドデータストリーム内のＦＩＦＯから出力されたデータブロックに基づき、前記データブロックに誤りが含まれているかどうかを示す第２ＣＲＣ値を生成する第２ＣＲＣ生成器と、を有することを特徴とする誤り検出システムにより解決する。【選択図】図１
2004103005.tif 000002
【特許請求の範囲】
【請求項１】
　ＦＩＦＯメモリから出力されるデータにおける誤りを検出する誤り検出システムであって、
　インバウンドデータストリームを受信し、前記インバウンドデータストリーム内のデータブロックに基づいて第１ＣＲＣ値を生成する第１ＣＲＣ生成器と、
　前記第１ＣＲＣ生成器に接続され、前記データブロック及び前記第１ＣＲＣ値を前記ＦＩＦＯに対して選択的に入力する装置と、
　アウトバウンドデータストリーム内のＦＩＦＯから出力されたデータブロックに基づき、前記データブロックに誤りが含まれているかどうかを示す第２ＣＲＣ値を生成する第２ＣＲＣ生成器と、を有することを特徴とする誤り検出システム。
【請求項２】
　前記インバウンドデータストリーム及び前記アウトバウンドデータストリーム内のデータブロックの開始点と終了点を識別する少なくとも１つのコントローラを更に有する請求項１記載の誤り検出システム。
【請求項３】
　前記第１ＣＲＣ生成器は、前記データブロックを生成多項式で除算することによって前記第１ＣＲＣ値を生成するべく構成されており、前記第１ＣＲＣ値は、前記除算の余りを表している請求項１記載の誤り検出システム。
【請求項４】
　前記選択的に入力する装置はマルチプレクサである請求項１記載の誤り検出システム。
【請求項５】
　前記第２ＣＲＣ生成器は、前記データブロック及び前記第１ＣＲＣ値を生成多項式で除算することによって前記第２ＣＲＣ値を生成するべく構成されており、前記第２ＣＲＣ値は、前記除算の余りを表している請求項１記載の誤り検出システム。
【請求項６】
　前記第２ＣＲＣ生成器は、前記データブロックを生成多項式で除算することによって前記第２ＣＲＣ値を生成するべく構成されており、前記第２ＣＲＣ値は前記除算の余りを表している請求項１記載の誤り検出システム。
【請求項７】
　前記第１ＣＲＣ値と前記第２ＣＲＣ値を比較する比較器であって、前記第１ＣＲＣ値が前記第２ＣＲＣ値と等しくない場合に前記データブロックに誤りが含まれていると識別するように構成されている比較器を更に有する請求項６記載の誤り検出システム。
【請求項８】
　複数の異なる生成多項式を保存する少なくとも１つの保存装置であって、前記第１及び第２ＣＲＣ値を生成するべく、前記複数の生成多項式の中の選択した１つを前記第１及び第２ＣＲＣ生成器にロードするべく構成された少なくとも１つの保存装置を更に有する請求項１記載の誤り検出するシステム。
【請求項９】
　インバウンドデータストリームを受信する入力とアウトバウンドデータストリームを出力する出力とを含むＦＩＦＯメモリを通過するデータストリーム内の誤りを検出する方法であって、
　前記インバウンドデータストリーム内のデータブロックを識別する段階と、
　前記識別したデータブロックに基づいて第１ＣＲＣ値を算出する段階と、
　前記データブロックと前記第１ＣＲＣ値を前記ＦＩＦＯに保存する段階と、
　前記アウトバウンドデータストリーム内の前記データブロックを識別する段階と、
　前記アウトバウンドデータストリーム内の前記データブロックに基づいて第２ＣＲＣ値を算出する段階と、
　前記第２ＣＲＣ値に基づき、前記アウトバウンドデータストリーム内のデータブロックに誤りが含まれているかどうかを判定する段階と、を有することを特徴とする方法。
【請求項１０】
　前記データブロック及び前記第１ＣＲＣを保存する段階は、
　前記データブロック及び前記第１ＣＲＣ値をマルチプレクサに入力する段階と、
　前記マルチプレクサから前記ＦＩＦＯに前記データブロックを出力する段階と、
　前記マルチプレクサから前記データブロックが出力された後に、追加信号を前記マルチプレクサに送信する段階と、
　前記追加信号に基づき、前記第１ＣＲＣ値を前記マルチプレクサから前記ＦＩＦＯに出力する段階と、を有する請求項９記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、誤り検出システムに関し、更に詳しくは、ＦＩＦＯ（ファーストインファーストアウト）メモリ用の誤り検出システムに関する。
【背景技術】
【０００２】
　ＦＩＦＯ（ファーストインファーストアウト）メモリでは、入力したデータが同じ順序で出力に表れる。ＦＩＦＯの入力と出力は、通常、２つの別個のクロックによって制御されており、一般的にＦＩＦＯはデータのバッファ処理に使用される。ＦＩＦＯの中には、短期的及び長期的誤りのいずれにも影響を受けやすいＲＡＭ（ランダムアクセスメモリ）技術に基づいたものも存在する。
【０００３】
　ＦＩＦＯメモリ素子を使用する既存のシステムでは、ＦＩＦＯを通過するデータのチェックを行っていないか、或いはワード単位の単純なビットのパリティチェックを使用している。パリティチェックを行っている場合には、データワードがＦＩＦＯから出力された際に、データワードのパリティを予想値（偶数又は奇数）に照らしてチェックする。そして、データワードが予想パリティ値と一致しない場合に、誤りが発生していると判定する。しかし、これは、１ビットの誤りの判定には有効に機能するが、複数ビットの誤りの判定には常に有効に機能する方法ではない。
【０００４】
【非特許文献１】ロス・ウイリアム（Ｒｏｓｓ　Ｎ．　Ｗｉｌｌｉａｍｓ）著、「ア　ペインレス　ガイド　トゥ　ＣＲＣ　エラー　デテクション　アルゴリズム（Ａ　Ｐａｉｎｌｅｓｓ　Ｇｕｉｄｅ　ｔｏ　ＣＲＣ　Ｅｒｒｏｒ　Ｄｅｔｅｃｔｉｏｎ　Ａｌｇｏｒｉｔｈｍｓ）」、（米国）、ＣＲＣ　Ｔｕｔｒｉａｌ、１９９３年８月１９日、ｐ．２９
【非特許文献２】ウェイル（Ｊ．Ｋ．Ｗｅｉｌ）、チュン（Ｄ．Ｃｈｕｎ）共著、「ザ　シングル　バースト　エラー　デテクション　パフォーマンス　オブ　バイナリー　サイクリック　コード（Ｔｈｅ　Ｓｉｎｇｌｅ　Ｂｕｒｓｔ　Ｅｒｒｏｒ　Ｄｅｔｅｃｔｉｏｎ　Ｐａｒｆｏｒｍａｎｃｅ　ｏｆ　Ｂｉｎａｒｙ　Ｃｙｃｌｉｃ　Ｃｏｄｅｓ）」、（米国）、アイトリプルイー・トランザクション・オブ・コミュニケーション４２巻１号（ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ｖｏｌ．４２，Ｎｏ．１）、１９９４年１月、ｐ．１１−１３
【非特許文献３】チュン（Ｄ．Ｃｈｕｎ）、ウェイル（Ｊ．Ｋ．Ｗｅｉｌ）共著、「スペシャル　ハードウェア　フォー　コンピューティング　ザ　プロバビリティ　オブ　アンデテクテッド　エラー　フォー　サーテン　バイナリー　ＣＲＣ　コード　アンド　テスト　リザルト（Ｓｐｅｃｉａｌ　Ｈａｒｄｗａｒｅ　ｆｏｒ　Ｃｏｍｐｕｔｉｎｇ　ｔｈｅ　Ｐｒｏｂａｂｉｌｉｔｙ　ｏｆ　Ｕｎｄｅｔｅｃｔｅｄ　Ｅｒｒｏｒ　ｆｏｒ　Ｃｅｒｔａｉｎ　Ｂｉｎａｒｙ　ＣＲＣ　Ｃｏｄｅｓ　ａｎｄ　Ｔｅｓｔ　Ｒｅｓｕｌｔｓ）」、（米国）、アイトリプルイー・トランザクション・オブ・コミュニケーション４２巻１０号（ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ｖｏｌ．４２，Ｎｏ．１０）、１９９４年１０月、ｐ．２７６９−２７７２
【発明の開示】
【発明が解決しようとする課題】
【０００５】
　従って、ＦＩＦＯメモリ素子を通過するデータストリームにおけるデータ破壊を検出するための更に強力なシステムを提供することが望ましい。
【課題を解決するための手段】
【０００６】
　本発明の一形態は、ＦＩＦＯメモリから出力されたデータの誤りを検出する誤り検出システムを提供する。このシステムは、インバウンドデータストリームを受信し、このインバウンドデータストリーム内のデータブロックに基づいて第１ＣＲＣ値を生成する第１ＣＲＣ生成器を含んでいる。この第１ＣＲＣ生成器に接続されている装置からＦＩＦＯに対してデータブロックと第１ＣＲＣ値が選択的に入力される。そして、第２ＣＲＣ生成器により、アウトバウンドデータストリーム内のＦＩＦＯから出力されたデータブロックに基づき、第２ＣＲＣ値が生成される。この第２ＣＲＣ値は、データブロックに誤りが含まれているかどうかを示すものである。
【発明を実施するための最良の形態】
【０００７】
　好適な実施例に関する以下の詳細な説明において添付の図面を参照するが、本明細書の一部を構成するそれらの図面には、本発明を実施可能な特定の実施例を例示している。本発明の範囲を逸脱することなく、その他の実施例も利用可能であり、且つ構造的又は論理的な変更を加えることができることを理解されたい。従って、以下の詳細な説明は制限を目的としてはおらず、本発明の範囲は、添付の請求項によって定義されるとおりである。
【０００８】
　図１は、ＦＩＦＯ（ファーストインファーストアウト）メモリ１１８及び本発明の一実施例によるＦＩＦＯ１１８から出力されたデータにおける誤りを検出する誤り検出システム１００を示すブロックダイアグラムである。この誤り検出システム１００は、ＣＲＣ（サイクリックリダンダンシーコード）生成器１０４、フレーム制御ロジック１１０、マルチプレクサ（ＭＵＸ）１１４、ＣＲＣ生成器１２４、及びフレーム制御ロジック１３０を含んでいる。一実施例において、この誤り検出システム１００は、マルチプレクサ１１４とＦＩＦＯ１１８を含む保護ドメイン１１９を通過するデータに発生する誤りを検出する。
【０００９】
　インバウンドデータストリーム１０２は、ＣＲＣ生成器１０４及びマルチプレクサ１１４によって受信される。本実施例においては、このインバウンドデータストリーム１０２は２値（例：０又は１）のストリームである。インバウンドデータストリーム１０２のビットを受信すると、ＣＲＣ生成器１０４は、ＣＲＣ値１１２の蓄積を開始する。本実施例においては、このＣＲＣ値１１２は、次の式Ｉに示されている多項式の除算から判定される。
【００１０】
式Ｉ：ＣＲＣ＝Ｍ［ｘ］／Ｇ［ｘ］の余り
【００１１】
　ここで、Ｍ［ｘ］はＣＲＣ生成器１０４に提示されるメッセージブロック（長さｍビット）であり、Ｇ［ｘ］は生成多項式である。
【００１２】
　Ｍ［ｘ］は、インバウンドデータストリーム１０２からのデータブロックを表している。フレーム制御ロジック１１０は、ＣＲＣ生成器１０４が処理するデータの各ブロック（メッセージブロック）のサイズを制御する。ＣＲＣ１１２の蓄積は、フレーム制御ロジック１１０がスタートライン１０６をアサートしたときに開始され、フレーム制御ロジック１１０がストップライン１０８をアサートしたときに終了する。フレーム制御ロジック１１０によって生成されるこれらのスタート及びストップ信号により、チェック対象のデータブロックが区切られるのである。本実施例においては、スタートライン１０６とストップライン１０８をアサートするべきタイミングを示す信号が外部のコントローラ（図示されていない）からフレーム制御ロジック１１０に送信される。
【００１３】
　Ｍ［ｘ］は、メッセージブロックにおけるビットの多項式表現であり、それぞれのビットは多項式の係数である。ｍビットのメッセージブロックは、範囲がｘｍ−１〜ｘ０のｍ個の項を有する多項式用の係数リストと見なされる。このような多項式は、ｍ−１次と称され、メッセージブロック内の最上位ビットは、ｘｍ−１の係数である。例えば、「１１０００１」というメッセージブロックは６つのビットを有しており、このビットストリームのＭ［ｘ］は、１、１、０、０、０、及び１という係数を有する６つの項の多項式ｘ５＋ｘ４＋ｘ０を表すことになる。
【００１４】
　式Ｉの生成多項式Ｇ［ｘ］については、高次及び低次の係数はいずれも１である。生成多項式Ｇ［ｘ］は、ＣＲＣ１１２の望ましいビット長よりも１ビット長い。本実施例においては、Ｇ［ｘ］は国際標準生成多項式である（例：ＣＲＣ−１２＝ｘ１２＋ｘ１１＋ｘ３＋ｘ２＋ｘ１＋１；ＣＲＣ−１６＝ｘ１６＋ｘ１５＋ｘ２＋１；又はＣＲＣ−ＣＣＩＴＴ＝ｘ１６＋ｘ１２＋ｘ５＋１）。いくつかの生成多項式Ｇ［ｘ］の例を提示したが、ＣＲＣ１１２は、特殊な多項式の除数を使用してデータブロックの内容に基づいて独自のシグネチャを生成する標準ＣＲＣアルゴリズムをいくつ使用しても生成可能である。
【００１５】
　本発明においては、「適切な」生成多項式Ｇ［ｘ］は、（１）ビット誤り確率ｐの関数としての見逃し誤り確率は、ｐ＝０．５における見逃し誤り確率を上回ることがない（これは、１−１／２ｎ＊１００％であり、即ち、ｎ＝１６の場合には９９．９９８５％である。ここで、ｎは生成多項式における最大指数であり、例えば、ＣＲＣ−１６多項式の場合には、ｎ＝１６である）、及び（２）単一バースト誤りの検出能力は不適切な多項式に比べて格段に大きく（桁が違う）、従って、ｎは、チェック対象のメッセージブロックＭ［ｘ］のビット数が２ｎを上回らないように選択するべきである（ここで、ｎは生成多項式の最大次数である）、という特性を有している。
【００１６】
　前述のように、Ｍ［ｘ］及びＧ［ｘ］は、２値の係数を有する多項式を表している。ＣＲＣ生成器１０４が実行する多項式の演算は、桁上げなしのＭｏｄｕｌｏ　２で実行される。次の例Ｉは、本実施例によって多項式の除算を実行する方法を示している。
【００１７】
例Ｉ：　メッセージＭ：　　　　　　　　　　　１１０１０１１０１１
　　　　ｗビットを追加した後のメッセージＭ：１１０１０１１０１１００００
　　　　生成多項式Ｇ：　　　　　　　　　　　１００１１（幅ｗ＝４）
【００１８】
【数１】
2004103005.tif 000003
【００１９】
　上記の例Ｉでは、実行時に使用するシード値が考慮されていない。この例Ｉの場合には、メッセージＭにシード値が含まれることを前提としている。例Ｉに示されているように、除算に先立って、４つの２値のゼロがメッセージＭの末尾に追加されている。このメッセージＭに追加するゼロの数は生成多項式の次数と同一であり、この例Ｉにおいては４である。又、追加するゼロの数は、望ましいＣＲＣ１１２の幅とも一致する。ＣＲＣ１１２は、除算Ｍ［ｘ］／Ｇ［ｘ］の余りであって、この例Ｉにおいては１１１０である。
【００２０】
　本実施例においては、データブロックに対するＣＲＣ生成器１０４によるＣＲＣ１１２の算出が完了した後に、ＣＲＣ１１２がマルチプレクサ１１４によってデータブロックに追加される。図１に示すように、マルチプレクサ１１４には、インバウンドデータストリーム１０２を受信する第１入力と、ＣＲＣ生成器１１２からＣＲＣ１１２を受信する第２入力が含まれている。マルチプレクサ１１４は、まず、インバウンドデータストリーム１０２からのメッセージブロックをＦＩＦＯ１１８に出力する。そして、このメッセージブロックを出力した後に、追加信号１１６をフレーム制御ロジック１１０がマルチプレクサ１１４に対して送信し、この信号により、マルチプレクサ１１４がメッセージブロック用のＣＲＣ１１２をＦＩＦＯ１１８に出力する。
【００２１】
　ＦＩＦＯ１１８から出力データストリーム１２０が出力されると、これをＣＲＣ生成器１２４が分析する。ＣＲＣ生成器１２４は、ＦＩＦＯ１１８を通過した出力データストリーム１２０における追加ＣＲＣ１１２を有するメッセージブロックを分析し、メッセージブロックが破壊されているかどうかを判定する。フレーム制御ロジック１３０は、スタートライン１２６をアサートしてメッセージブロックの開始点をＣＲＣ生成器１２４に示すと共に、ストップライン１２８をアサートしてブロックの末尾を示す。ＣＲＣ生成器１２４によるＣＲＣ（例：余り）１３２の蓄積は、フレーム制御ロジック１３０がスタートライン１２６をアサートしたときに開始され、フレーム制御ロジック１３０がストップライン１２８をアサートしたときに終了する。本実施例においては、スタートライン１２６とストップライン１２８をアサートするべきタイミングを示す信号が外部コントローラ（図示されていない）からフレーム制御ロジック１３０に送信される。
【００２２】
　本実施例においては、ＣＲＣ生成器１２４は、次の式ＩＩに表されているように、追加されたＣＲＣ１１２を有する受信データブロックをＣＲＣ１１２の生成に使用したものと同一の生成多項式Ｇ［ｘ］で除算することにより、受信データブロックの完全性を検証する。
【００２３】
式ＩＩ：ＣＲＣ＝（Ｍ［ｘ］＋ＣＲＣ）／Ｇ［ｘ］の余り
【００２４】
　ここで、Ｍ［ｘ］はＣＲＣ生成器１２４に提示されるメッセージブロックであり、Ｇ［ｘ］はＣＲＣ１１２の生成に使用した生成多項式である。
【００２５】
　本実施例においては、システム１００を使用し、ＣＲＣ１１２がそれぞれのデータブロックの末尾に直接追加されたデータブロックの完全性を検証する。この場合、多項式Ｇ［ｘ］は、追加されたＣＲＣ１１２を有するデータブロックの正確な倍数であり、データが破壊されていない場合には、ＣＲＣ生成器１２４が算出したＣＲＣ１３２は定数になる。破壊されておらず、追加されたＣＲＣ１１２が反転していない場合には、ＣＲＣ１３２は０になるが、更なる誤りに対する保護を提供するべくＣＲＣ１１２が反転している場合には、ＣＲＣ１３２は、データ及び埋め込まれたＣＲＣ１１２が破壊されることなくＦＩＦＯ１１８を通過したことを示す特定の定数（マジックナンバー）になる。
【００２６】
　図２は、ＦＩＦＯ１１８と本発明の別の実施例によるＦＩＦＯ１１８から出力されたデータにおける誤りを検出する誤り検出システム２００を表すブロックダイアグラムである。本実施例においては、メッセージブロックにＣＲＣ１１２を埋め込むがその埋め込み位置がちょうどメッセージブロックの末尾ではない場合に、このシステム２００を使用することができる。このようなケースは、ＦＩＦＯ１１８のデータ出力幅がインバウンド側のデータ幅と異なっており、パディングが使用される場合に発生する（パディングビットはＣＲＣには含まれない）。
【００２７】
　本実施例においては、図２のブロック１０４、１１０、１１４、１１８、１２４、及び１３０は、図１を参照して先程説明したものと略同様に動作する。ＦＩＦＯ１１８を通過した出力データストリーム１２０における追加されたＣＲＣ１１２を有するメッセージブロックを分析し、メッセージブロックが破壊されているかどうかを判定する。メッセージブロック内に埋め込まれたＣＲＣ１１２を出力データストリーム１２０から抽出し、ＣＲＣレジスタ２０４に保存する。フレーム制御ロジック１３０（又は外部コントローラ）は、メッセージブロックにおけるＣＲＣ１１２の位置を追跡し、ＣＲＣ１１２を出力データストリーム１２０からレジスタ２０４にロードするべく、「Ｌｏａｄ　ＣＲＣ」信号２０６を適切なタイミングでＣＲＣレジスタ２０４に出力する。
【００２８】
　ＣＲＣ生成器１２４は、ＣＲＣ１１２の生成にＣＲＣ生成器１０４が使用したものと同一の生成多項式Ｇ［ｘ］を使用し、受信したメッセージブロック（埋め込まれたＣＲＣ１１２を除く）に基づいてＣＲＣ２１４を算出する。フレーム制御ロジック１３０は、スタート信号１２６をＣＲＣ生成器１２４に出力してメッセージブロックの開始点を示し、ストップ信号１２８を出力してブロックの末尾を示す。ＣＲＣ２１４の蓄積は、フレーム制御ロジック１３０がスタートライン１２６をアサートしたときに開始され、フレーム制御ロジック１３０がストップライン１２８をアサートしたときに終了する。
【００２９】
　比較器２１０は、抽出したＣＲＣ１１２をＣＲＣレジスタ２０４から受信し、新たに算出したＣＲＣ２１４をＣＲＣ生成器１２４から受信する。２つのＣＲＣ値１１２及び２１４は同一の生成多項式Ｐ［ｘ］を使用して同一のメッセージブロックから生成されているため、ＦＩＦＯ１１８を通過した際にメッセージブロックに誤りが発生していなければ、これら２つの値１１２及び２１４は一致するはずである。比較器２１０は、２つのＣＲＣ１１２及び２１４を比較し、これら２つの値１１２及び２１４が等しくなければ、誤り信号２１２を出力する。又、本実施例においては、システム２００は、データブロックの末尾にＣＲＣ１１２のデータブロックを追加するなど、図１を参照して前述した説明したものと同様にＣＲＣ１３２を生成するようにも構成される。
【００３０】
　図３は、ＦＩＦＯ１１８及び本発明の更に別の実施例によるＦＩＦＯ１１８から出力されたデータにおける誤りを検出する誤り検出システム３００を示すブロックダイアグラムである。このシステム３００は、図２に示すシステム２００と同一のブロック１０４、１１０、１１４、１１８、２０４、２１０、１２４、及び１３０を含んでおり、更に、レジスタ３０２及び３０４も含まれている。本実施例においては、これらのレジスタ３０２及び３０４には、それぞれ複数の異なるタイプの生成多項式Ｇ［ｘ］が保存される。一実施例においては、レジスタ３０２から適切な生成多項式Ｇ［ｘ］がＣＲＣ生成器１０４にロードされ、同一の生成多項式がレジスタ３０４からＣＲＣ生成器１２４にロードされる。そして、前述のように、これらレジスタ３０２及び３０４からロードされた生成多項式を使用してＣＲＣの算出が行われる。
【００３１】
　本実施例においては、可変の誤り検出特性を提供するべく、ＣＲＣ生成器１０４及び１２４が使用する生成多項式Ｇ［ｘ］がシステム３００の動作中に「オンザフライ」で変更される。本実施例においては、レジスタ３０２及び３０４に保存されている様々な生成多項式Ｇ［ｘ］は、様々な属性（例えば、長さが異なる、係数が異なる、など）を有している。特定のタイプの生成多項式は、特定の誤りクラスを検出する能力がその他の生成多項式よりも優れている。又、短いデータブロックの場合には、短い多項式を使用することができるが、長いデータブロックの誤りを正確に検出するには、長い多項式が必要になる。本実施例においては、ＦＩＦＯ１１８を通過するデータブロックの長さに基づくと共に／或いはそのデータブロックの内容又は検出を所望する誤りのタイプに基づき、レジスタ３０２及び３０４からそれぞれＣＲＣ生成器１０４及び１２４に適切な生成多項式Ｇ［ｘ］が自動的にロードされる。
【００３２】
　当業者であれば、システム１００、２００、及び３００が実行する機能は、ハードウェア、ソフトウェア、ファームウェア、又はこれらの組み合わせによって実装可能であることを理解するであろう。本発明は、マイクロプロセッサ、プログラム可能な論理デバイス、又は状態機械によって実現することができる。そして、本発明のコンポーネントは、１つ又は複数のコンピュータ可読媒体上のソフトウェア内に存在するものであってよい。尚、本明細書で使用する「コンピュータ可読媒体」という用語は、フレキシブルディスク、ハードディスク、ＣＤ−ＲＯＭ、フラッシュメモリ、読み出し専用メモリ（ＲＯＭ）、及びランダムアクセスメモリなどの、揮発性又は不揮発性のあらゆる種類のメモリを含むものである。
【００３３】
　本発明においては、データをデータ経路にシフトすることにより、データ経路のインバウンド１０２及びアウトバウンド１２０の両方について、システム１００、２００、及び３００によるＣＲＣの算出が並行して実行される。この結果、レイテンシーペナルティが回避される。
【００３４】
　本発明によれば、ＦＩＦＯを通過するデータストリームにおけるデータ破壊をＣＲＣアルゴリズムを使用して検出する強力なシステムが提供される。パリティに基づいた従来のＦＩＦＯの誤り検出プロセスとは異なり、本発明による実施例は、複数ビットの誤りを検出することが可能であり、且つワード単位でのみ誤りを検出するのではなく、様々なサイズのデータブロックにおける誤りを検出することができる。本発明は、ＦＩＦＯを通過するデータブロックにおいて発生する様々なタイプのビット誤りを検出する能力という観点で、既存のパリティに基づいた誤り検出システムよりも格段に強力である。
【００３５】
　以上、好適な実施例を説明するべく、特定の実施例を示して説明したが、当業者であれば、本発明の範囲を逸脱することなく、図示及び説明した特定の実施例を様々な代替及び／又は等価な実装によって置換可能であることを理解するであろう。化学、機械、電気機械、電気、及びコンピュータの各技術分野の知識を有する者であれば、本発明が様々な実施例で実装可能であることを容易に理解するであろう。本出願は、本明細書において説明した好適な実施例のあらゆる適合や変形を含むことを意図するものである。従って、本発明は、請求項及びその相当物によってのみ限定される。
【００３６】
　最後に、本発明の代表的な実施態様を以下に示す。
（実施態様１）
　ＦＩＦＯメモリ（１１８）から出力されるデータにおける誤りを検出する誤り検出システム（１００、２００、又は３００）であって、インバウンドデータストリーム（１０２）を受信し、前記インバウンドデータストリーム内のデータブロックに基づいて第１ＣＲＣ値（１１２）を生成する第１ＣＲＣ生成器（１０４）と、前記第１ＣＲＣ生成器に接続され、前記データブロック及び前記第１ＣＲＣ値を前記ＦＩＦＯに対して選択的に入力する装置（１１４）と、アウトバウンドデータストリーム（１２０）内のＦＩＦＯから出力されたデータブロックに基づき、前記データブロックに誤りが含まれているかどうかを示す第２ＣＲＣ値（１３２又は２１４）を生成する第２ＣＲＣ生成器（１２４）と、を有することを特徴とする誤り検出システム。
【００３７】
（実施態様２）
　前記インバウンドデータストリーム及び前記アウトバウンドデータストリーム内のデータブロックの開始点と終了点を識別する少なくとも１つのコントローラ（１１０及び１３０）を更に有する実施態様１記載の誤り検出システム。
【００３８】
（実施態様３）
　前記第１ＣＲＣ生成器は、前記データブロックを生成多項式で除算することによって前記第１ＣＲＣ値を生成するべく構成されており、前記第１ＣＲＣ値は、前記除算の余りを表している実施態様１記載の誤り検出システム。
【００３９】
（実施態様４）
　前記選択的に入力する装置はマルチプレクサである実施態様１記載の誤り検出システム。
【００４０】
（実施態様５）
　前記第２ＣＲＣ生成器は、前記データブロック及び前記第１ＣＲＣ値を生成多項式で除算することによって前記第２ＣＲＣ値を生成するべく構成されており、前記第２ＣＲＣ値は、前記除算の余りを表している実施態様１記載の誤り検出システム。
【００４１】
（実施態様６）
　前記第２ＣＲＣ生成器は、前記データブロックを生成多項式で除算することによって前記第２ＣＲＣ値を生成するべく構成されており、前記第２ＣＲＣ値は前記除算の余りを表している実施態様１記載の誤り検出システム。
【００４２】
（実施態様７）
　前記第１ＣＲＣ値と前記第２ＣＲＣ値を比較する比較器（２１０）であって、前記第１ＣＲＣ値が前記第２ＣＲＣ値と等しくない場合に前記データブロックに誤りが含まれていると識別するように構成されている比較器（２１０）を更に有する実施態様６記載の誤り検出システム。
【００４３】
（実施態様８）
　複数の異なる生成多項式を保存する少なくとも１つの保存装置（３０２及び３０４）であって、前記第１及び第２ＣＲＣ値を生成するべく、前記複数の生成多項式の中の選択した１つを前記第１及び第２ＣＲＣ生成器にロードするべく構成された少なくとも１つの保存装置（３０２及び３０４）を更に有する実施態様１記載の誤り検出するシステム。
【００４４】
（実施態様９）
　インバウンドデータストリーム（１０２）を受信する入力とアウトバウンドデータストリーム（１２０）を出力する出力とを含むＦＩＦＯメモリ（１１８）を通過するデータストリーム内の誤りを検出する方法であって、前記インバウンドデータストリーム内のデータブロックを識別する段階と、前記識別したデータブロックに基づいて第１ＣＲＣ値（１１２）を算出する段階と、前記データブロックと前記第１ＣＲＣ値を前記ＦＩＦＯに保存する段階と、前記アウトバウンドデータストリーム内の前記データブロックを識別する段階と、前記アウトバウンドデータストリーム内の前記データブロックに基づいて第２ＣＲＣ値（１３２又は２１４）を算出する段階と、前記第２ＣＲＣ値に基づき、前記アウトバウンドデータストリーム内のデータブロックに誤りが含まれているかどうかを判定する段階と、を有することを特徴とする方法。
【００４５】
（実施態様１０）
　前記データブロック及び前記第１ＣＲＣを保存する段階は、前記データブロック及び前記第１ＣＲＣ値をマルチプレクサ（１１４）に入力する段階と、前記マルチプレクサから前記ＦＩＦＯに前記データブロックを出力する段階と、前記マルチプレクサから前記データブロックが出力された後に、追加信号（１１６）を前記マルチプレクサに送信する段階と、前記追加信号に基づき、前記第１ＣＲＣ値を前記マルチプレクサから前記ＦＩＦＯに出力する段階と、を有する実施態様９記載の方法。
【図面の簡単な説明】
【００４６】
【図１】ＦＩＦＯ及び本発明の一実施例によるＦＩＦＯから出力されたデータにおける誤りを検出する誤り検出システムを示すブロックダイアグラムである。
【図２】ＦＩＦＯ及び本発明の別の実施例によるＦＩＦＯから出力されたデータにおける誤りを検出する誤り検出システムを示すブロックダイアグラムである。
【図３】ＦＩＦＯ及び本発明の更に別の実施例によるＦＩＦＯから出力されたデータにおける誤りを検出する誤り検出システムを示すブロックダイアグラムである。
【符号の説明】
【００４７】
１００、２００、３００　誤り検出システム
１０２　インバウンドデータストリーム
１０４　第１ＣＲＣ生成器
１１０、１３０　コントローラ
１１２　第１ＣＲＣ値
１１４　入力装置、マルチプレクサ
１１６　追加信号
１１８　ＦＩＦＯメモリ
１２０　アウトバウンドデータストリーム
１２４　第２ＣＲＣ生成器
１３２、２１４　第２ＣＲＣ値
２１０　比較器
３０２、３０４　保存装置
【図１】
2004103005.tif 000004
【図２】
2004103005.tif 000005
【図３】
2004103005.tif 000006