(57)【特許請求の範囲】
【請求項１】
メッセージビット列にパリティビット列が逆順に付加され、伝わったＣＲＣコードが分割され伝わるよう転換されるスイッチと、
該スイッチを介して伝わった前記メッセージビット列を前記パリティビット列の生成多項式で割って最終剰余値を求め、求められた最終剰余値ビット列を逆順に順次的出力する除算部と、
該除算部から順次に出力される最終剰余値ビット列を前記スイッチ部を介して順次に伝わるパリティビット列とそれぞれビット別に比較する比較部と、
該比較部の比較結果に基づき前記ＣＲＣコードの転送エラーを判定する判定部と、を備え、
前記除算部は、前記メッセージビット列の最終剰余値が求められるまで入力される前記メッセージビット列を順方向シフト動作し、
前記最終剰余値ビット列が前記比較部で順次に比較されうるように逆方向シフト動作を行う、ことを特徴とするＣＲＣコードのエラー検出装置。
【請求項２】
前記除算部は、入力される前記メッセージビット列が前記パリティビット列の生成多項式により割られた演算結果をビット単位で貯蔵できるように直列連結された複数のレジスタと、
前記スイッチから伝わった前記メッセージビット列の最終ビットが前記複数のレジスタに達するまで前記複数のレジスタで順方向シフト動作を行えるようスイッチングされる複数の順方向シフトスイッチと、
該複数のレジスタのそれぞれに貯蔵された最終剰余値ビット列を順次に前記比較部に出力するために前記複数のレジスタで逆方向シフト動作を行えるようにスイッチングされる複数の逆方向シフトスイッチと、を備えることを特徴とする請求項１に記載のＣＲＣコードのエラー検出装置。
【請求項３】
前記比較部は、ＸーＯＲゲートが用いられることを特徴とする請求項１に記載のＣＲＣコードのエラー検出装置。
【請求項４】
前記判定部は、前記比較部の出力が入力されるＯＲゲートと、該ＯＲゲートの出力を伝達され１クロック周期後に前記ＯＲゲートに入力されうるように遅延レジスタと、を備えることを特徴とする請求項１に記載のＣＲＣコードのエラー検出装置。
【請求項５】
メッセージビット列にパリティビット列が逆順に付加され、伝わったＣＲＣコードの前記メッセージビット列を前記パリティビット列の生成多項式で割って最終剰余値を算出して逆順に順次に出力する段階と、
逆順に順次に出力される前記最終剰余値ビット列と順次に入力される前記パリティビット列とを比較する段階と、
該比較段階を通して得た結果に基づき前記ＣＲＣコードの転送エラーを判定する段階と、を備え、
前記最終剰余値を算出して逆順に順次に出力する段階は、前記メッセージビット列の最終剰余値が求められるまで入力される前記メッセージビット列を順方向シフト動作する段階と、
前記最終剰余値ビット列が前記比較段階で順次に比較されうるように逆方向シフト動作を行う段階と、を備える、ことを特徴とするＣＲＣコードのエラー検出方法。
【請求項６】
メッセージビット列にパリティビット列が逆順に付加され、順次に伝わったＣＲＣコードを複数のレジスタでシフト動作を通して順次に受け入れ生成多項式で割って最終剰余値を求め、その演算結果を前記複数のレジスタにビット単位に貯蔵する除算部と、
前記複数のレジスタのそれぞれに貯蔵された最終剰余値ビット列について最外郭ビット１対から内側にそれぞれ対をなすようにして各対を比較する比較部と、
該比較部の比較結果に基づき前記ＣＲＣコードの転送エラーを判定する判定部と、を備えることを特徴とするＣＲＣコードのエラー検出装置。
【請求項７】
前記比較部は、前記レジスタの個数を２で割った値の整数に該当する数のＸーＯＲゲートが備わったことを特徴とする請求項６に記載のＣＲＣコードのエラー検出装置。
【請求項８】
前記レジスタの個数が奇数の場合、前記剰余値のビット列のうち中央のビットを貯蔵するレジスタの出力は直接に前記判定部に入力されることを特徴とする請求項７に記載のＣＲＣコードのエラー検出装置。
【請求項９】
メッセージビット列にパリティビット列が逆順に付加され、順次に伝わったＣＲＣコードを生成多項式で割って最終剰余値を算出する段階と、
該最終剰余値算出段階で算出されたビット列について最外郭ビット１対から内側にそれぞれ対をなすようにして各対を比較する段階と、
該各対比較段階を通して得た結果に基づき前記ＣＲＣコードの転送エラーを判定する段階と、を備えることを特徴とするＣＲＣコードのエラー検出方法。
【請求項１０】
前記ＣＲＣコード転送エラー判定段階は、前記剰余値のビット数が奇数の場合、前記剰余値のビット列のうち中央のビット値及び前記比較段階を通して得た結果に基づき前記ＣＲＣコードの転送エラーを判定することを特徴とする請求項９に記載のＣＲＣコードのエラー検出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパリティビット(Parity bits)が逆順に付加されたＣＲＣコードのエラー検出装置及び方法に係り、さらに詳しくは生成多項式(generator polinomial)を用いて生成されたパリティビット列を、通常の方式とは違って、逆順に配列してメッセージビット列(Message bits)に付加したＣＲＣコードを転送した場合、受信側でＣＲＣコードの転送上のエラー発生有無を検出できる装置及びその方法に関する。
【０００２】
【従来の技術】
デジタル通信システムにおいては、受信端で受信されたデータの転送上のエラーを検出するための方法として、転送対象になるデータを収録したメッセージビットにパリティビットを追加する方式を使用している。受信側ではそのパリティビットを単純に検数したりメッセージビットと共に検数することにより、受信されたデータがエラーなしで転送されたデータであるか否かを判別する。このようなパリティビットの付加によるエラー検出方式のうち最も強力なエラー検出方式の一つがＣＲＣ(Cyclic Redundancy Check)コード方式である。
【０００３】
図１には一般のＣＲＣコードの構造が示されている。
同図を参照すれば、ｎビットのＣＲＣコードはｋビットのメッセージビット（ｍk-1〜ｍ0）とｎ-ｋビットのパリティビット(ｐn-k-1〜ｐ0)で構成されることが分かる。
【０００４】
前述したようなＣＲＣコードは特定な多項式(polinomial)で表現することができ、このうちパリティビットはメッセージビットを表現する多項式を所定の生成多項式で割った剰余(remainder)を用いた多項式で表現することができる。
【０００５】
すなわち、ｋビットのメッセージビットを示す多項式を次のように表現し、
【０００６】
ｍ(Ｘ) = ｍ0 + ｍ1Ｘ1+ ｍ2Ｘ2+ ・・・・ +ｍk-1Ｘk-1
【０００７】
パリティビットを生成するための生成多項式を次のように表現し、
【０００８】
ｇ(Ｘ) = ｇ0+ｇ1Ｘ1+ｇ2Ｘ2+ ・・・・ +ｇn-kＸn-k
【０００９】
ｎ-ｋビットのパリティビットの多項式を次のように表現する場合、
【００１０】
ｐ(Ｘ) = ｐ0+ｐ1Ｘ1+ｐ2Ｘ2+ ・・・・ +ｐn-k-1Ｘn-k-1
【００１１】
ＣＲＣコードは次のような式で表現できる。
【００１２】
c(Ｘ) = Ｘn-kｍ(Ｘ) +ｐ(Ｘ)
【００１３】
ここで、 ｐ(Ｘ) =Ｘn-k-ｋｍ(Ｘ) ｍｏｄ ｇ(Ｘ)である。
【００１４】
かかるＣＲＣコードの転送上のエラー有無を検出する方法は、受信されたＣＲＣコードを生成多項式で再び割ってその剰余が‘０’になることを確認する。これは次のような数式により証明できる。
【００１５】
すなわち、前述した通りｐ(Ｘ)はＸｎ-ｋｍ(Ｘ)をｇ(Ｘ)で割った剰余なので、
【００１６】
Ｘn-kｍ(Ｘ)  = ｇ(Ｘ)Ｑ(Ｘ)+ｐ(Ｘ)
のように表示でき、ここでｐ(Ｘ)を左辺に移項すれば、
【００１７】
Ｘn-kｍ(Ｘ) - ｐ(Ｘ) = ｇ(Ｘ)Ｑ(Ｘ)
のような式になるが、一般の演算とは違って、‘-ｐ(Ｘ)’は二進ガロア(Galois
Field)上の演算では+ｐ(Ｘ)と同様なので、
【００１８】
つまり、
Ｘn-kｍ(Ｘ) + ｐ(Ｘ) = ｇ(Ｘ)Ｑ(Ｘ)
のように表現できる。
【００１９】
上記式において左辺はｃ(Ｘ)と同じなので、結局ｃ(Ｘ)をｇ(Ｘ)で割った値は、商がＱ(Ｘ)になり、剰余が‘０’になる。
【００２０】
このような原理を用いた従来のＣＲＣコードエラー検出装置が図２に示されている。図２を参照すれば、従来のＣＲＣコードエラー検出装置は受信されたＣＲＣコードを生成多項式で割る除算器１１、及び除算器１１の出力を用いてエラー有無を判定する判定器１３とから構成されている。除算器１１はｎ-ｋ個のレジスタ(register)１１ａとｎ-ｋ個の乗算器(Multiplier)１１b、ｎ-ｋ個のＸーＯＲゲート(Exclusive-OR gate)１１ｃとから構成されている。判定器１３は除算器１１内のレジスタ１１ａの出力をＮＯＲ演算するＮＯＲゲート１３ａで構成されている。
【００２１】
前述したような構成でデジタル通信システムの送信端において図１の構造を有するＣＲＣコードのビット列(ｍk-1、ｍk-2、 ・・・・、ｍ0、ｐn-k-1、・・・・、 ｐ0)が転送されれば、チャンネルを通過した入力ビット列がレジスタ１１ａにシフトしつつ順番に入力される。そして入力されるビット列は生成多項式で割るための各信号(ｇ0、ｇ1、ｇ2、 ・・・・、ｇn-k-1)と最右側にシフトされた信号が乗算器１１ｂを通して演算され、その演算された信号と入力し続ける入力ビットがＸーＯＲゲート１１ｃを通して演算される。以上のような過程を通してｎ個のビット列が全て入力されれば、生成多項式による最終剰余がレジスタ１１ａに残り、エラーがなければレジスタ１１ａに存する値は全て'０'になる。従って、このレジスタ１１ａの出力値を判定器１３においてＮＯＲ演算した値が'１'になってこそ、ＣＲＣコードがエラーなしで転送したことと判定する。もし全部ＮＯＲ演算した値が'０'の場合はＣＲＣコードにエラーがあることと判定する。
【００２２】
ところが、最近次世代移動通信と呼ばれるＩＭＴ-２０００におけるデータ送受信方式などに関連してＵＭＴＳ(Universal Mobile Telecommunication System)では、ＣＲＣコード生成時パリティビットを前述したこととは違う方式で付加する方式が提案されている。すなわち、従来とは違って、図３に示した通り、メッセージビットを表現した多項式を生成多項式で割った剰余を逆順に配列したビット列をパリティビットとして使用する方式が採択されている。
【００２３】
これをさらに詳しく説明すれば次の通りである。
パリティビットが逆順に付加されたＣＲＣコードは図３に示した通り構成され、これは(ｍk-1、ｍk-2、・・・・、ｍ0、ｐ0、 ・・・・、ｐn-k-1)のような順序で転送される。この際ＣＲＣコードは次のような多項式で表現される。
【００２４】
c(Ｘ) = Ｘn-kｍ(Ｘ) + ｐ┴(Ｘ)
ここで、ｐ(Ｘ) = Ｘn-kｍ(Ｘ) ｍｏｄ ｇ(Ｘ)とする際、
【００２５】
ｐ┴(Ｘ) = Ｘdeg p(X)ｐ(Ｘ-1)
と定義される。
【００２６】
ところが、前述したような従来のエラー検出装置においてパリティビットは、図１に示した通り、通常の順序に付加された場合はエラーを検出することができるが、パリティビットが図３に示した通り逆順に付加される場合はエラーを検出できないという短所がある。なぜならば、このようなＣＲＣコードの多項式ｃ(Ｘ)を生成多項式ｇ(Ｘ)で割る場合は剰余が'０'にならないからである。従って、図２に示したような従来のエラー検出装置ではＣＲＣコードの転送上のエラー発生有無を検出できなくなる。
【００２７】
【発明が解決しようとする課題】
本発明は前述した問題点を解決するために案出されたもので、その目的は前述したように逆順に付加されたパリティビット列を含むＣＲＣコードに転送エラーが発生されたか否かを判別するためのエラー検出装置及びその方法を提供するところにある。
【００２８】
【課題を解決するための手段】
前述した目的を達成するための本発明に係るＣＲＣコードのエラー検出装置は、メッセージビット列にパリティビット列が逆順に付加され順次に伝わったＣＲＣコードが分割され伝わるように転換されるスイッチと、該スイッチを介して伝わった前記メッセージビット列を前記パリティビット列の生成多項式で割って最終剰余値を求める除算部と、前記スイッチを介して伝わった前記パリティビット列を順次に貯蔵するバッファ部と、前記除算部の最終剰余値ビット列と前記バッファ部に貯蔵されたパリティビット列とをそれぞれ比較する比較部、及び該比較部を介して得た結果に基づき前記ＣＲＣコードの転送エラーを判定する判定部と、を備える。
【００２９】
前記比較部は前記除算部の出力と前記バッファ部内の前記パリティビットをそれぞれのビット別にＸーＯＲ演算する複数のＸーＯＲゲートを含むことが望ましい。
【００３０】
前述した目的を達成するための本発明のＣＲＣコードエラー検出方法は、メッセージビット列にパリティビット列が逆順に付加され、伝わったＣＲＣコードの前記メッセージビット列を前記パリティビット列の生成多項式で割って最終剰余値を算出する段階と、前記パリティビット列を順次に貯蔵する段階と、前記最終剰余値ビット列と順次に貯蔵された前記パリティビット列をそれぞれ比較する段階、及び前記比較段階を通して得た結果に基づき前記ＣＲＣコードの転送エラーを判定する段階と、を備える。
【００３１】
本発明の他の実施形態によるＣＲＣコードのエラー検出装置は、メッセージビット列にパリティビット列が逆順に付加され、伝わったＣＲＣコードが分割され伝達するよう転換されるスイッチと、該スイッチを介して伝わった前記メッセージビット列を前記パリティビット列の生成多項式で割って最終剰余値を求め、求められた最終剰余値ビット列を逆順に順次に出力する除算部と、該除算部から順次に出力される最終剰余値ビット列を前記スイッチ部を介して順次に伝わるパリティビット列とそれぞれビット別に比較する比較部、及び該比較部の比較結果に基づき前記ＣＲＣコードの転送エラーを判定する判定部と、を備える。
【００３２】
ここで、前記除算部は入力される前記メッセージビット列が前記パリティビット列の生成多項式により割られた演算結果をビット単位に貯蔵できるように直列連結された複数のレジスタと、前記スイッチから伝わった前記メッセージビット列の最終ビットが前記複数のレジスタに達するまで前記複数のレジスタで順方向シフト動作を行えるようにスイッチングされる複数の順方向シフトスイッチ及び前記複数のレジスタのそれぞれに貯蔵された最終剰余値ビット列を順次に前記比較部に出力するために前記複数のレジスタで逆方向シフト動作を行えるようにスイッチングされる複数の逆方向シフトスイッチと、を備える。
【００３３】
前述した目的を達成するための本発明の他のＣＲＣコードエラー検出方法は、メッセージビット列にパリティビット列が逆順に付加され、伝わったＣＲＣコードの前記メッセージビット列を前記パリティビット列の生成多項式で割って最終剰余値を算出して逆順に順次に出力する段階と、逆順に順次に出力される前記最終剰余値ビット列と順次に入力される前記パリティビット列とを比較する段階、及び前記比較段階を通して得た結果に基づき前記ＣＲＣコードの転送エラーを判定する段階と、を備える。
【００３４】
本発明のさらに他の実施形態によるＣＲＣコードのエラー検出装置は、メッセージビット列にパリティビット列が逆順に付加され、順次に伝わったＣＲＣコードを複数のレジスタでシフト動作を通して順次に受け入れて生成多項式で割って最終剰余値を求め、その演算結果を前記複数のレジスタにビット単位に貯蔵する除算部と、前記複数のレジスタそれぞれに貯蔵された最終剰余値ビット列について最外郭ビット１対から内側に各対をなすようにして各対を比較する比較部、及び該比較部の比較結果に基づき前記ＣＲＣコードの転送エラーを判定する判定部と、を備える。
【００３５】
ここで、前記比較部は前記レジスタの個数を２で割った値の整数部に該当する個数のＸーＯＲゲートを含み、前記レジスタの個数が奇数の場合は前記剰余値のビット列のうち中央のビットを貯蔵するレジスタの出力は直接に前記判定部に入力される。
【００３６】
前述した目的を達成するための本発明のさらに他のＣＲＣコードエラー検出方法は、メッセージビット列にパリティビット列が逆順に付加され、順次に伝わるＣＲＣコードを生成多項式で割って最終剰余値を算出する段階と、該最終剰余値算出段階において算出されたビット列について最外郭ビット１対から内側に各対をなすようにして各対を比較する段階、該各対比較段階を通して得た結果に基づき前記ＣＲＣコードの転送エラーを判定する段階と、を備える。
【００３７】
【発明の実施の形態】
以下、添付した図面に基づき本発明の実施形態によるＣＲＣコードエラー検出装置を詳述する。本発明を説明する際、各図面の同一構成要素は単一符号を付して説明する。
【００３８】
図３に対する説明において、前述した通り、ＣＲＣコードはメッセージビットとこれに付加されたパリティビットで構成されており、またパリティビットはメッセージビットを特定の生成多項式で割った剰余を逆順に配列したビット列で構成される。
【００３９】
図４は本発明に係るエラー検出装置の一実施形態を示した図である。同図を参照されば、ＣＲＣコードのエラー検出装置は、入力されたメッセージビット列をパリティビット列の生成多項式で割って除算結果の剰余値を貯蔵する除算部４０２、入力されたパリティビット列を貯蔵するバッファ部４０３、入力されるＣＲＣコードを除算部４０２とバッファ部４０３に選択的に入力させるスイッチング部４０１、除算部４０２の出力値とバッファ部４０３内のパリティビット列とを比較する比較部４０４、及び比較部４０４の比較結果に基づきＣＲＣコードの転送エラーを判定する判定部４０５とから構成されている。
【００４０】
スイッチング部４０１はメッセージビット列が入力される区間中にはＣＲＣコードを除算部４０２に入力させ、パリティビット列が入力される区間中はＣＲＣコードをバッファ部４０３に入力させるようスイッチング動作を行う。
【００４１】
除算部４０２は、ｎ-ｋ個のレジスタ４０２ａとｎ-ｋ個の乗算器４０２ｂ、及びｎ-ｋ個のＸーＯＲゲート(Exclusive-OR gate)４０２ｃで構成されている。スイッチング部４０１のスイッチング作動によりＣＲＣコードのうちメッセージビット列が受信される間は、メッセージビット列は除算部４０２に順次に入力され、入力されたビット列はレジスタ４０２ａに順次にシフトされる。
【００４２】
メッセージビット列が除算部４０２に入力される間、除算部４０２ではメッセージビット列を生成多項式で割る除算動作が行われる。すなわち、入力されるメッセージビット列の値は乗算器４０２ｂにより生成多項式とかけられ、それからＸーＯＲゲート４０２ｃによりＸーＯＲ演算され、結局除算が行われる。この際、除算結果の剰余値はレジスタ４０２ａに貯蔵され、剰余値のＭＳＢ(Most Significant Bit)が最右側のレジスタに、そしてＬＳＢ(Least Significant Bit)が最左側のレジスタに貯蔵される。
【００４３】
メッセージビット列が全て除算部４０２に入力されれば、スイッチング部４０１はバッファ部４０３側に切り換られパリティビット列をバッファ部４０３に入力させ、入力されたパリティビット列はバッファ部４０３に入力された順に貯蔵される。バッファ部４０３はパリティビット列のビット数と同一な個数のレジスタで構成され、それぞれパリティビット列をビット単位に貯蔵する。
【００４４】
比較部４０４は、除算部４０２から出力される剰余値とバッファ部４０３内のパリティビット列をそれぞれのビット別にＸーＯＲ演算する複数のＸーＯＲゲート(Exclusive-OR gate)４０４ａで構成されている。この際、ＸーＯＲゲート４０４ａの個数はｎ-ｋ個であって、パリティビット列のビット数と同一である。それぞれのＸーＯＲゲート４０４ａには除算部４０２内の一つのレジスタ４０２ａの値とバッファ部４０３内の一つのレジスタの値が入力される。この際、パリティビット列のうち最初入力されたパリティビットが除算部４０２から出力される剰余値のＬＳＢと比較され、最後に入力されたパリティビットが除算部４０２から出力される剰余値のＭＳＢと比較される。従って、パリティビット列を逆順に配列した値と除算部４０２から出力される剰余値が相互比較される。
【００４５】
ＣＲＣコードの送信側から送信されるパリティビット列はメッセージビット列を生成多項式で割ることにより生成されるため、受信側でも前述したような方式によりメッセージビット列を生成多項式で割った値をパリティビットが逆配列された値と比較することによりエラー有無を検出することができる。すなわち、除算部４０２の出力値とバッファ部４０３内に貯蔵された値を相互逆順に配列してビット別に比較することによりエラー有無を検出することができる。従って、転送エラーがない場合は比較部４０４の全てのＸーＯＲゲート４０４ａの値は全て'０'になる。
【００４６】
判定部４０５は、比較部４０４の全ての出力値が入力されるＮＯＲゲート４０５ａで構成されている。従って、比較部４０４のＸーＯＲゲート４０４ａの出力値が全て'０'の場合、判定部４０５は'１'を出力し、これはＣＲＣコードがエラーなしで転送されたことを意味する。
【００４７】
前述したように本実施形態によれば、メッセージビット列が入力される間はメッセージビット列を生成多項式で割る除算動作を行って剰余値を算出し、パリティビット列が入力される間はパリティビット列を貯蔵した後、パリティビット列を逆順に配列した逆ビット列を算出された剰余値と比較する。これにより両者が同じ場合は転送エラーがないことと判断するので、パリティビットが逆順に配列されたＣＲＣコードの転送エラーを検出することができる。
【００４８】
図５は本発明に係るＣＲＣコードのエラー検出装置の他の実施形態を示した図である。本実施形態においてエラー検出装置は入力されたメッセージビット列をパリティビットの生成多項式で割って除算演算結果の剰余値を出力する除算部５０２と、除算部５０２から順次に出力される剰余値を順次に入力されるパリティビット列とビット別に比較する比較部５０４と、入力されるＣＲＣコードを除算部５０２と比較部５０４に選択的に伝えるスイッチング部５０１、及び比較部５０４の比較結果に基づきＣＲＣコードの転送エラーを判定する判定部５０５と、から構成されている。
【００４９】
除算部５０２は、ｎ-ｋ個のレジスタ５０２ａとｎ-ｋ個の乗算器５０２ｂ、順方向シフトスイッチ５０３ａ、複数の逆方向シフトスイッチ５０３ｂ及びｎ-ｋ個のＸーＯＲゲート５０２ｃとから構成されている。レジスタ５０２ａは除算部５０２の演算結果をビット単位に貯蔵するように直列連結されている。スイッチング部５０１のスイッチング作動により、ＣＲＣコードのうちメッセージビット列が受信される間、メッセージビット列は除算部５０２に入力され、入力されたメッセージビット列はレジスタ５０２ａに順次にシフトされ入力される。
【００５０】
メッセージビット列が除算部５０２に入力される間、除算部５０２ではメッセージビット列を生成多項式で割る除算動作が行われる。この際、除算部５０２の動作は前述した図４の実施形態と同様である。従って、除算結果の剰余値はレジスタ５０２ａに貯蔵され、剰余値のＭＳＢが最右側のレジスタに、そしてＬＳＢが最左側のレジスタに貯蔵される。
【００５１】
一方、前述したような過程を通して複数のレジスタ５０２ａのそれぞれに最終剰余値が貯蔵されれば、各レジスタ５０２ａに貯蔵されたビット値は別の演算が行われずクロック周期毎に順次に左側にシフトされ、シフトされたビット列は比較部５０４に出力される。
【００５２】
スイッチング部５０１は、メッセージビット列が入力される区間ではＣＲＣコードを除算部５０２に入力させ、パリティビット列が入力される区間ではＣＲＣコードを比較部５０４に入力させるようスイッチング動作を行う。
【００５３】
この際、スイッチング部５０１の動作は順方向シフトスイッチ５０３ａ及び逆方向シフトスイッチ５０３ｂの動作と連動される。すなわち、スイッチング部５０１がメッセージビットを除算部５０２に入力する間は順方向シフトスイッチ５０３ａをオン状態にし、逆方向シフトスイッチ５０３ｂはオフ状態になる。一方、スイッチング部５０１がパリティビットを比較部５０４に入力する間、逆方向シフトスイッチ５０３ｂをオン状態にし、順方向シフトスイッチ５０３ａをオフ状態におる。従って、メッセージビット列が除算部５０２に入力される間は除算部５０２は除算を行い、メッセージビット列の入力が完了されれば除算部５０２のレジスタ５０２ａには除算結果の剰余値が貯蔵される。そして、パリティビット列が順次に比較部５０４に入力される間は除算部５０２のレジスタ５０２ａに貯蔵されていた剰余値は逆順に比較部５０４に入力される。これにより、剰余値が逆に配列された逆ビット列とパリティビット列がビット単位に順次に比較される。
【００５４】
比較部５０４は、除算部５０２から最終逆方向シフトスイッチ５０３ｂを介して出力される剰余値とスイッチング部５０１を経て入力されるパリティビット列を入力にするＸーＯＲゲート５０４ａで構成されている。従って、剰余値を逆順に配列した値と順次に入力されるパリティビットがビット単位に相互比較され、両者が同じ場合のみ比較部５０４は'０'を出力する。
【００５５】
判定部５０５は、ＯＲゲート５０５ａと遅延レジスタ５０５ｂとから構成されている。比較部５０４の出力はＯＲゲート５０５ａに入力され、ＯＲゲート５０５ａの出力は遅延レジスタ５０５ｂに貯蔵された後１クロック周期後再びＯＲゲート５０５ａに入力される。従って、比較部５０４内のＸーＯＲゲート５０４ａが常に'０'を出力する場合のみ判定部５０５の出力が'０'になり、この場合ＣＲＣコードの転送エラーがないことと判定される。
【００５６】
以上のように本実施形態によれば、メッセージビット列が入力される間はメッセージビット列を生成多項式で割る除算動作を行って剰余値を算出し、パリティビット列が入力される間は剰余値を逆順に配列した逆ビット列をパリティビット列と順次に比較する。これにより両者が同じ場合は転送エラーがないと判断され、パリティビットが逆順に付加されたＣＲＣコードのエラーを検出できるようになる。
【００５７】
図６は本発明の他の実施形態によるＣＲＣコードのエラー検出装置を示した図である。本実施形態においてエラー検出装置は、入力されたＣＲＣコードを生成多項式で割って剰余値をそれぞれのレジスタ６０１ａに貯蔵する除算部６０１、除算部６０１の各レジスタ６０１ａに貯蔵された最終剰余値ビット列について最外郭ビット１対から内側に各対をなすようにして各対を比較する比較部６０２、及び比較部６０２の比較結果に基づきＣＲＣコードの転送エラー有無を判定する判定部６０３とを備える。
【００５８】
除算部６０１は、図面に示した通り、ｎ-ｋ個のレジスタ６０１ａと、ｎ-ｋ個の乗算器６０１ｂ、及びｎ-ｋ個のＸーＯＲゲート６０１ｃとから構成されている。これらの動作は前述した実施形態と同一である。ただ、本実施形態では除算部６０１にＣＲＣコード全体が入力されるため、除算部６０１はメッセージビットとパリティビットを含んだＣＲＣコード全体を生成多項式で割る演算を行い、その剰余値がビット単位にレジスタ６０１ａに貯蔵される。
【００５９】
比較部６０２は、除算部６０１内のレジスタ６０１cの個数を２で割った値の整数部に該当する個数のＸーＯＲゲート６０２ａを含む。例えば、図７に示した通り、除算部６０１が４個のレジスタ６０１ａを有する場合、比較部６０２は２個のＸーＯＲゲート６０２ａを備え、図８に示した通り、除算部６０１が３個のレジスタ６０１ａを備える場合、比較部６０２は１個のＸーＯＲゲート６０２ａを備える。
【００６０】
比較部６０２内の各ＸーＯＲゲート６０２ａの入力は次のように定まる。すなわち、各レジスタ６０１ａに貯蔵された最終剰余値ビット列について最外郭ビット１対から内側にそれぞれ対をなすようにして各対を比較する。言い換えれば、剰余値の最右側ビットであるＭＳＢは最左側ビットであるＬＳＢと比較され、右側から二番目のビットは左側から二番目のビットと比較される。このような方式により対称に対をなして各対の出力がそれぞれのＸーＯＲゲート６０２ａに入力される。そして比較部６０２の各ＸーＯＲゲート６０２ａの出力は判定部６０３に入力される。
【００６１】
もし、レジスタ６０１ａの個数が奇数の場合は、図８に示した通り、剰余値のビット列のうち中央のビットを貯蔵するレジスタ６０２ａの出力は直接に判定部６０３に入力される。
【００６２】
判定部６０３はＮＯＲゲート６０３ａで構成されており、該ＮＯＲゲート６０３ａには、図７に示した通り、レジスタ６０１ａの個数が偶数の場合は比較部６０２の全てのＸーＯＲゲート６０２ａの出力値が入力され、図８に示した通り、レジスタ６０１ａの個数が奇数の場合は比較部６０２の全てのＸーＯＲゲート６０２ａの出力値及び中央に位置したレジスタ６０１ａの出力値が入力される。判定部６０３の全て入力が'０'の場合、すなわち判定部６０３のＮＯＲゲート６０３ａの出力が'１'の場合、ＣＲＣコードの転送エラーがないことと判定する。
【００６３】
本実施形態によるエラー検出装置の動作原理を数学的に説明すれば次の通りである。
【００６４】
前述した通り、パリティビットが逆順に配列されたＣＲＣコードを示す多項式は次のように表現される。
【００６５】
c(Ｘ) = Ｘn-kｍ(Ｘ) + ｐ┴(Ｘ)
【００６６】
ここで、ｐ(Ｘ) = Ｘn-kｍ(Ｘ) ｍｏｄ ｇ(Ｘ)とする際、
【００６７】
ｐ┴(Ｘ) = Ｘddeg p(X)ｐ(Ｘ-1)
と定義される。
【００６８】
ところが、
Ｘn-kｍ(Ｘ) ｍｏｄ ｇ(Ｘ) = ｐ(Ｘ)であり、
【００６９】
ｐ┴(Ｘ) ｍｏｄ ｇ(Ｘ) = ｐ┴(Ｘ)なので、
【００７０】
( ∵ ｄｅｇ ｐ┴(Ｘ) ＜ ｄｅｇ ｇ(Ｘ))
【００７１】
前記二つの式において、
c(Ｘ) ｍｏｄ ｇ(Ｘ) = ｐ(Ｘ) + ｐ┴(Ｘ)
＝ (ｐ0 + ｐn-k-1) + (ｐ1 + ｐn-k-2)Ｘ + ・・・・・・・ +
+  ・・・・  +   (ｐn-k-2+   ｐ１)Ｘn-k-2 + (ｐn-k-1+ｐ0)Ｘn-k-1
になることが分かる。
【００７２】
上記の最後の式を見れば、ＣＲＣコードの多項式ｃ(Ｘ)を生成多項式ｇ(Ｘ)で割った剰余の多項式はその係数が相互対称に配置されていることが分かる。従って、前述したように剰余値のビット列を半分に区画し、区画された一つのビット列を剰余ビット列が逆順に配列された逆ビット列とビット別に比較すれば、比較される値、すなわちそれぞれのＸーＯＲゲート６０２ａに入力される値は常に同じ値になるため、ＸーＯＲゲート６０２ａの出力は全部'０'になる。従って、 判定部６０３の出力は転送エラーがなければ '１'になる。
【００７３】
一方、図８の場合のように、ｃ(Ｘ)を生成多項式ｇ(Ｘ)で割った剰余の多項式の項の数が奇数の場合は、上記式によれば、中央の項は同じ値を足した値になることが分かる。すなわち、中央の項は
【００７４】
(ｐ(n-k-1)/2 + ｐ(n-k-1)/2)Ｘ(n-k-1)/2  (ここで、ｎ-ｋは奇数)
になり、前述したような二進ガロアフィールド上における演算によれば同じ値を足した値は'０'になるため、上記項の係数は常に'０'になる。従って、ＣＲＣコードの転送エラーがなければ、中央のレジスタに貯蔵される値は常に'０'になるため、ＮＯＲゲート６０３ａに入力される値は全部'０'になって判定部は'１'を出力する。
【００７５】
以上のような本実施形態によれば、メッセージビット列とパリティビット列とを区分してスイッチング動作を行うスイッチング部４０１または５０１が要らなくなるので、図４及び図５に示した実施形態より簡単な構成を有するＣＲＣコードのエラー検出装置を提供することができる。
【００７６】
そして、図４の実施形態と比較する際、比較部６０２が少数のＸーＯＲゲート６０２ａよりなっているのでその構成が一層簡単になる。
【００７７】
また、図５の実施形態と比較する際、スイッチング部５０１と制御部５０３を連動させる必要がなく、また両方向にシフト可能なレジスタ５０２ａを使用する必要がなく通常の除算器６０１を使用するので、その構成が一層簡単になる。また、１ビットずつ順次に比較する図５の実施形態に比べてエラー検出が一層迅速になされる。
【００７８】
【発明の効果】
前述したように本発明に係るＣＲＣコードエラー検出装置及び方法は、メッセージビット列を生成多項式で割った剰余で構成されたパリティビットが、通常の順序とは違って逆順にメッセージビットに付加されたＣＲＣコードを復号する場合、受信端で転送上のエラーを効率よく検出できるようになる。
【００７９】
以上では本発明の望ましい実施形態について示しかつ説明したが、本発明は前記実施形態に限らず、請求の範囲で請求する本発明の要旨を逸脱せず当該発明の属する技術分野において通常の知識を持つものならば誰でも多様な変形実施が可能なことは勿論であり、そのような変形は請求の範囲の記載範囲内にある。
【図面の簡単な説明】
【図１】  一般のＣＲＣコードのビット列の構成を示した図である。
【図２】  図１に示したＣＲＣコードのエラー検出装置を示した図である。
【図３】  パリティビットが逆順に付加されたＣＲＣコードのビット列の構成を示した図である。
【図４】  図３に示した通り、パリティビットが逆順に付加されたＣＲＣコードのエラーを検出する本発明に係るエラー検出装置を示した図である。
【図５】  本発明の他の実施形態を示した図である。
【図６】  本発明のさらに他の実施形態を示した図である。
【図７】  図６の実施形態において除算結果が偶数の場合を示した図である。
【図８】  図６の実施形態において除算結果が奇数の場合を示した図である。
【符号の説明】
４０１、５０１  スイッチング部
４０２、５０２、６０１  除算部
４０３  バッファ部
４０４、５０４、６０２  比較部
４０５、５０５、６０３  判定部
５０３  制御部
【図１】
0004125500.tif 000002
【図２】
0004125500.tif 000003
【図３】
0004125500.tif 000004
【図４】
0004125500.tif 000005
【図５】
0004125500.tif 000006
【図６】
0004125500.tif 000007
【図７】
0004125500.tif 000008
【図８】
0004125500.tif 000009