JP3606443B2

JP3606443B2 - Error detection apparatus, CRC check method, and recording medium

Info

Publication number: JP3606443B2
Application number: JP2000054468A
Authority: JP
Inventors: 知久樋口
Original assignee: Kenwood KK
Current assignee: Kenwood KK
Priority date: 2000-02-29
Filing date: 2000-02-29
Publication date: 2005-01-05
Anticipated expiration: 2020-02-29
Also published as: JP2001244820A

Description

【０００１】
【発明の属する技術分野】
本発明は、取得したデータの誤りをＣＲＣ（ＣｙｃｌｉｃＲｅｄｕｎｄａｎｃｙＣｈｅｃｋ）方式により検出する誤り検出装置に関し、特にＣＲＣチェックを高速に処理することのできる誤り検出装置、ＣＲＣチェック方法及び記録媒体に関する。
【０００２】
【従来の技術】
従来から、送信されたデータや所定の媒体から読み出したデータ等が誤りなく取得できたか否かを判別するために、データの誤り検出が行われている。この誤り検出には、パリティチェック方式やチェックサム方式が用いられてきた。
パリティチェック方式は、例えば、送信側にて、７ないし８ビットで表される１文字分のデータに別の１ビットを付加し、全体の「１」のビット数が常に奇数（又は、偶数）個になるようにしてデータを生成する。そして、受信側にて、取得したデータ（１文字分）の「１」のビット数が、奇数（又は、偶数）個でない場合に、エラーが発生したと判断する。
また、チェックサム方式は、例えば、送信側にて、一定の長さのブロック内のデータ列を足し合わせた総和を求め、求めた合計値の最下桁１バイトをブロックの最後尾に付加したデータを生成する。そして、受信側にて、取得したデータのブロック内の合計値を求め、合計値の最下桁１バイトと最後尾の１バイトとを比較して、一致しない場合に、エラーが発生したと判断する。
【０００３】
近年では、これらパリティチェック方式等よりもエラーの検出能力が高く、状況によってはエラーの訂正も可能という点等の理由により、ＣＲＣ（ＣｙｃｌｉｃＲｅｄｕｎｄａｎｃｙＣｈｅｃｋ）方式が誤り検出に用いられるようになっている。ＣＲＣ方式は、例えば、送信側にて、ブロック単位のデータ毎に所定の生成多項式を使用して巡回符号を求め、求めた巡回符号をそれぞれ付加したデータを生成する。そして、受信側にて、取得したデータをブロック単位に同一の生成多項式にて除算し、割り切れなかった（剰余が生じた）場合に、エラーが発生したと判断する。
【０００４】
以下、このＣＲＣ方式について、伝送すべきデータをデータＤ（Ｄ＝Ｘ^２３＋Ｘ^２１＋Ｘ^１８＋Ｘ^１７＋Ｘ^１４＋Ｘ^１３＋Ｘ^１２＋Ｘ^１１＋Ｘ^１０＋Ｘ^６＋Ｘ^４＋Ｘ^３＋１）とし、生成多項式を多項式Ｇ（Ｇ＝Ｘ^６＋Ｘ^４＋Ｘ^３＋１）とした場合を一例として説明する。
送信側は、データＤに多項式Ｇの最高次の項であるＸ^６を乗じたデータＤＸ（ＤＸ＝Ｘ^２９＋Ｘ^２７＋Ｘ^２４＋Ｘ^２３＋Ｘ^２０＋Ｘ^１９＋Ｘ^１８＋Ｘ^１７＋Ｘ^１６＋Ｘ^１２＋Ｘ^１０＋Ｘ^９＋Ｘ^６）を多項式Ｇで割り、その剰余を巡回符号として求める。
すなわち、送信側は、図９に示すように、データＤＸを多項式Ｇで割り、剰余として、Ｘ^３＋Ｘ^２＋Ｘを求める。このＸ^３＋Ｘ^２＋Ｘが巡回符号となる。
【０００５】
より具体的に説明すると、この場合、データＤＸは、「１０１００１１００１１１１１０００１０１１００１００００００」と表され、また、多項式Ｇは、「１０１１００１」と表される。
そして、データＤＸを多項式Ｇで除算する際において、実際には剰余しか必要としないため（商が不要であるため）、送信側は、図１０に示すように、データＤＸと多項式Ｇとの排他的論理和（ｘｏｒ）を順次演算し、剰余として「１１１０」（すなわち、Ｘ^３＋Ｘ^２＋Ｘ）を求める。
送信側は、この剰余、つまり巡回符号をデータＤＸに付加したデータ（「１０１００１１００１１１１１０００１０１１００１００１１１０」）を生成して受信側に向けて送信する。
【０００６】
受信側は、受信したデータを同一の多項式Ｇで除算し、剰余が生じた場合に、エラーが発生したと判断する。すなわち、受信側は、図１１に示すように、受信したデータ（「１０１００１１００１１１１１０００１０１１００１００１１１０」）と多項式Ｇ（「１０１１００１」）との排他的論理和を順次演算して、剰余の有無を判別する。
このように、受信したデータと多項式Ｇとを使用した演算により剰余の有無を判別し、受信データの誤り検出を精度良く行うことができる。
【０００７】
【発明が解決しようとする課題】
しかし、上述の図１０や図１１を参照して説明したように、多項式Ｇによるデータの除算は、チェック対象データ等の上位ビットが「１」の場合に、ビット配置を合わせた多項式Ｇとの排他的論理和を演算し、また、「０」の場合に、シフトさせて次のビットを参照するという演算処理を繰り返し行う必要がある。
すなわち、ビット単位で演算処理を行っており、排他的論理和等の演算を数多く行う必要があるため、誤り検出のための処理負荷が大きくなり、全体の処理効率の低下を招いていた。
【０００８】
また、例えば、ＣＤ−ＲＯＭ内に記録したデータ等を読み出す際には、１セクタ分のデータ量である２０６０バイトものデータに対して、誤り検出を行う必要がある。この際、生成多項式には、誤り検出の精度の向上から、より高次の多項式、例えば、多項式Ｇ（ｘ）＝Ｘ^３２＋Ｘ^３１＋Ｘ^１６＋Ｘ^１５＋Ｘ^４＋Ｘ^３＋Ｘ＋１が用いられることとなる。
この場合、２０６０バイトものデータのビット毎に排他的論理和等の演算を繰り返し行うため、処理負荷が極めて大きくなり、誤り検出のために長時間に渡って処理を行わなければならないといった問題があった。
【０００９】
本発明は、上記実状に鑑みてなされたもので、ＣＲＣチェックを高速に行うことのできる誤り検出装置、ＣＲＣチェック方法及び記録媒体を提供することを目的とする。
【００１０】
【課題を解決するための手段】
上記目的を達成するため、本発明の第１の観点に係る誤り検出装置は、
複数ビット分のビット配列に従って、所定の生成多項式が合算されて生成された合算生成データを予め記憶する記憶手段と、
ビット列同士の排他的論理和を演算する演算手段と、
ＣＲＣ（ＣｙｃｌｉｃＲｅｄｕｎｄａｎｃｙＣｈｅｃｋ）チェック対象のデータを入力する入力手段と、
前記入力手段が入力したデータ又は、前記演算手段により前回演算されて生じた演算結果データから複数ビット分のビット配列を特定し、特定したビット配列に対応する合算生成データを前記記憶手段から取得する取得手段と、
前記入力手段が入力したデータ又は、前記演算手段により前回演算されて生じた演算結果データと、前記取得手段が取得した合算生成データとの演算を前記演算手段に所定回数行わせる制御手段と、
前記制御手段の制御により前記演算手段にて所定回数繰り返された演算により生じた演算結果に従って、前記入力手段が入力したデータの誤りを検出するエラー検出手段と、
を備えることを特徴とする。
【００１１】
この発明によれば、記憶手段は、複数ビット分のビット配列に従って、所定の生成多項式が合算されて生成された合算生成データを予め記憶する。演算手段は、ビット列同士の排他的論理和を演算する。入力手段は、ＣＲＣチェック対象のデータを入力する。取得手段は、入力手段が入力したデータ又は、演算手段により前回演算されて生じた演算結果データから複数ビット分のビット配列を特定し、特定したビット配列に対応する合算生成データを記憶手段から取得する。制御手段は、入力手段が入力したデータ又は、演算手段により前回演算されて生じた演算結果データと、取得手段が取得した合算生成データとの演算を演算手段に所定回数行わせる。エラー検出手段は、制御手段の制御により演算手段にて所定回数繰り返された演算により生じた演算結果に従って、入力手段が入力したデータの誤りを検出する。このように、チェック対象データと合算生成データとの演算を、チェック対象データの複数ビット単位に繰り返すことにより、チェック対象データの生成多項式による除算を少ない演算処理にて実現できる。この結果、ＣＲＣチェックを高速に行うことができる。
【００１２】
上記目的を達成するため、本発明の第２の観点に係る誤り検出装置は、
１バイト分のビット配列に従って、ビット配置のそれぞれ異なる生成多項式が合算されて生成された合算生成データを予め記憶する記憶手段と、
ビット列同士の排他的論理和を演算する演算手段と、
ＣＲＣチェック対象のデータを入力する入力手段と、
前記入力手段が入力したデータ又は、前記演算手段により前回演算されて生じた演算結果データから１バイト分のビット配列を特定し、特定したビット配列に対応する合算生成データを前記記憶手段から取得する取得手段と、
前記入力手段が入力したデータ又は、前記演算手段により前回演算されて生じた演算結果データと、前記取得手段が取得した合算生成データとの演算を前記演算手段に所定回数行わせる制御手段と、
前記制御手段の制御により前記演算手段にて所定回数繰り返された演算により生じた演算結果に剰余が含まれる場合に、前記入力手段が入力したデータの誤りを検出するエラー検出手段と、
を備えることを特徴とする。
【００１３】
この発明によれば、記憶手段は、１バイト分のビット配列に従って、ビット配置のそれぞれ異なる生成多項式が合算されて生成された合算生成データを予め記憶する。演算手段は、ビット列同士の排他的論理和を演算する。入力手段は、ＣＲＣチェック対象のデータを入力する。取得手段は、入力手段が入力したデータ又は、演算手段により前回演算されて生じた演算結果データから１バイト分のビット配列を特定し、特定したビット配列に対応する合算生成データを記憶手段から取得する。制御手段は、入力手段が入力したデータ又は、演算手段により前回演算されて生じた演算結果データと、取得手段が取得した合算生成データとの演算を演算手段に所定回数行わせる。エラー検出手段は、制御手段の制御により演算手段にて所定回数繰り返された演算により生じた演算結果に剰余が含まれる場合に、入力手段が入力したデータの誤りを検出する。このように、チェック対象データと合算生成データとの演算を、チェック対象データの１バイト単位に繰り返すことにより、チェック対象データの生成多項式による除算を少ない演算処理にて実現できる。この結果、ＣＲＣチェックを高速に行うことができる。
【００１４】
上記目的を達成するため、本発明の第３の観点に係るＣＲＣチェック方法は、
ビット列同士の排他的論理和を演算する演算ステップと、
ＣＲＣチェック対象のデータを入力する入力ステップと、
前記入力ステップにて入力されたデータ又は、前記演算ステップにて前回演算されて生じた演算結果データから複数ビット分のビット配列を特定し、特定したビット配列により定まる生成多項式が合算されて生成された合算生成データを所定の記憶部から取得する取得ステップと、
前記入力ステップにて入力されたデータ又は、前記演算ステップにて前回演算されて生じた演算結果データと、前記取得ステップにて取得された合算生成データとの演算を前記演算ステップにて所定回数行わせる制御ステップと、
前記制御ステップの制御により前記演算ステップにて所定回数繰り返された演算により生じた演算結果に従って、前記入力ステップにて入力されたデータの誤りを検出するエラー検出ステップと、
を備えることを特徴とする。
【００１５】
この発明によれば、演算ステップは、ビット列同士の排他的論理和を演算する。入力ステップは、ＣＲＣチェック対象のデータを入力する。取得ステップは、入力ステップにて入力されたデータ又は、演算ステップにて前回演算されて生じた演算結果データから複数ビット分のビット配列を特定し、特定したビット配列により定まる生成多項式が合算されて生成された合算生成データを所定の記憶部から取得する。制御ステップは、入力ステップにて入力されたデータ又は、演算ステップにて前回演算されて生じた演算結果データと、取得ステップにて取得された合算生成データとの演算を演算ステップにて所定回数行わせる。エラー検出ステップは、制御ステップの制御により演算ステップにて所定回数繰り返された演算により生じた演算結果に従って、入力ステップにて入力されたデータの誤りを検出する。このように、チェック対象データと合算生成データとの演算を、チェック対象データの複数ビット単位に繰り返すことにより、チェック対象データの生成多項式による除算を少ない演算処理にて実現できる。この結果、ＣＲＣチェックを高速に行うことができる。
【００１６】
上記目的を達成するため、本発明の第４の観点に係るＣＲＣチェック方法は、
ビット列同士の排他的論理和を演算する演算ステップと、
ＣＲＣチェック対象のデータを入力する入力ステップと、
前記入力ステップにて入力されたデータ又は、前記演算ステップにて前回演算されて生じた演算結果データから１バイト分のビット配列を特定し、特定したビット配列により定まるビット配置のそれぞれ異なる生成多項式が合算されて生成された合算生成データを所定の記憶部から取得する取得ステップと、
前記入力ステップにて入力されたデータ又は、前記演算ステップにて前回演算されて生じた演算結果データと、前記取得ステップにて取得された合算生成データとの演算を前記演算ステップにて所定回数行わせる制御ステップと、
前記制御ステップの制御により前記演算ステップにて所定回数繰り返された演算により生じた演算結果に剰余が含まれる場合に、前記入力ステップにて入力されたデータの誤りを検出するエラー検出ステップと、
を備えることを特徴とする。
【００１７】
この発明によれば、演算ステップは、ビット列同士の排他的論理和を演算する。入力ステップは、ＣＲＣチェック対象のデータを入力する。取得ステップは、入力ステップにて入力されたデータ又は、演算ステップにて前回演算されて生じた演算結果データから１バイト分のビット配列を特定し、特定したビット配列により定まるビット配置のそれぞれ異なる生成多項式が合算されて生成された合算生成データを所定の記憶部から取得する。制御ステップは、入力ステップにて入力されたデータ又は、演算ステップにて前回演算されて生じた演算結果データと、取得ステップにて取得された合算生成データとの演算を演算ステップにて所定回数行わせる。エラー検出ステップは、制御ステップの制御により演算ステップにて所定回数繰り返された演算により生じた演算結果に剰余が含まれる場合に、入力ステップにて入力されたデータの誤りを検出する。このように、チェック対象データと合算生成データとの演算を、チェック対象データの１バイト単位に繰り返すことにより、チェック対象データの生成多項式による除算を少ない演算処理にて実現できる。この結果、ＣＲＣチェックを高速に行うことができる。
【００１８】
上記目的を達成するため、本発明の第５の観点に係る記録媒体は、
ビット列同士の排他的論理和を演算する演算ステップと、ＣＲＣチェック対象のデータを入力する入力ステップと、前記入力ステップにて入力されたデータ又は、前記演算ステップにて前回演算されて生じた演算結果データから複数ビット分のビット配列を特定し、特定したビット配列により定まる生成多項式が合算されて生成された合算生成データを所定の記憶部から取得する取得ステップと、前記入力ステップにて入力されたデータ又は、前記演算ステップにて前回演算されて生じた演算結果データと、前記取得ステップにて取得された合算生成データとの演算を前記演算ステップにて所定回数行わせる制御ステップと、前記制御ステップの制御により前記演算ステップにて所定回数繰り返された演算により生じた演算結果に従って、前記入力ステップにて入力されたデータの誤りを検出するエラー検出ステップとを有するＣＲＣチェック方法をコンピュータに実行させるためのプログラムを記録する。
【００１９】
【発明の実施の形態】
本発明の実施の形態にかかる誤り検出装置について、以下図面を参照して説明する。
【００２０】
図１は、この発明の実施の形態に適用される誤り検出装置の一例を示すブロック図である。図示するように、誤り検出装置１は、データ入力部１１と、演算処理部１２と、記憶部１３と、エラー出力部１４とを備えて構成される。
データ入力部１１は、チェック対象となるデータを順次入力し、入力したデータを演算処理部１２に供給する。
【００２１】
演算処置部１２は、ＣＰＵ（ＣｅｎｔｒａｌＰｒｏｃｅｓｓｉｎｇＵｎｉｔ）等からなり、データ入力部１１から供給されたチェック対象データを演算処理することにより、データエラーが生じているか否かを判別する。具体的に演算処理部１２は、後述するＣＲＣチェック処理を実行し、チェック対象データ中の例えば、対象４ビットから定まる合算生成データを使用した演算処理の結果に従ってエラーの有無を判別する。なお、合算生成データについては、後述する。
【００２２】
記憶部１３は、ＲＯＭ（ＲｅａｄＯｎｌｙＭｅｍｏｒｙ）等からなり、例えば、図２に示すような生成データテーブル１３１を予め記憶する。
生成データテーブル１３１は、チェック対象データ中の対象４ビットと、合算生成データとの対応関係を規定するテーブルである。すなわち、生成データテーブル１３１は、１６個の対象４ビット（「００００」〜「１１１１」）に対応する合算生成データ（「００００００００００」〜「１１１１１１０１０１」）を規定するテーブルである。
【００２３】
この合算生成データは、排他的論理和の演算に使用される生成多項式を対象４ビットのビット配列に従って合算したデータである。なお、生成多項式には、多項式Ｇ（Ｇ＝Ｘ^６＋Ｘ^４＋Ｘ^３＋１）が用いられる。以下、合算生成データについて、具体的に説明する。
【００２４】
例えば、チェック対象データにおける対象４ビット（上位４ビット）のビット配列が「１１１１」である場合、図３に示すように、多項式Ｇの先頭位置（ビット配置）をずらしたＬ１、Ｌ２及びＬ４がそれぞれ合算され（排他的論理和が演算され）、ΣＬとして合算生成データが求められる。
【００２５】
ところで従来の除算の場合、例えば図４（ａ）に示すように、チェック対象データ（「１１１１・・・」）と多項式Ｇ（「１０１１００１」）との排他的論理和を順次演算する。具体的には、まず対象データとＬ１との排他的論理和を演算し、その演算結果とＬ２との排他的論理和を演算し、そして、更に演算結果とＬ４との排他的論理和を演算する。
すなわち、チェック対象データの対象４ビットが「１１１１」の場合、データに対して、以下の数式１に示すような演算が行われる。なお、数式１中に示される（Ｄ）’は、データＤを１回、多項式Ｇで割った結果を示すものとする。
【００２６】
【数１】
（Ｄ）’ ＝ＤｘｏｒＬ１
（Ｄ）’’ ＝（Ｄ）’ ｘｏｒＬ２
（Ｄ）’’’ ＝（Ｄ）’’ ｘｏｒＬ４
【００２７】
この数式１から、（Ｄ）’’’とＤとの関係を導くと、数式２にて示される関係が成立する。
【００２８】
【数２】

【００２９】
数式２に示すように、データＤと、多項式Ｇのビット配置をずらしたＬ１、Ｌ２及びＬ４の合算（排他的論理和）の演算結果との排他的論理和を演算することにより、数式１と同一となる最終的な演算結果を得ることができる。
つまり、図４（ｂ）に示すチェック対象のデータと、Ｌ１、Ｌ２及びＬ４が合算されたΣＬとの排他的論理和の演算結果（「０００００１１１・・・」）は、図４（ａ）に示す最終的な演算結果と等しくなる。
このことから、数式３が成立することとなる。
【００３０】
【数３】
（Ｄ）’’’ ＝Ｄｘｏｒ ΣＬ
【００３１】
すなわち、排他的論理和に使用される多項式Ｇを合算して生成されるΣＬ、すなわち、合算生成データを使用することにより、図４（ａ）に示すような対象４ビット（「１１１１」）に対して３回必要であった排他的論理和の演算を、図４（ｂ）に示すように１回にまとめて行うことができる。
このような合算生成データが、対象４ビットの１６種類のビット配列（「００００」〜「１１１１」）に応じて予め求められ、それぞれのビット配列に対応づけられた生成データテーブル１３１が記憶部１３に記憶されている。
【００３２】
図１に戻って、エラー出力部１４は、演算処理部１２の演算処理結果に従って、エラーが検出された場合に、データの誤りを検出したことを示す所定のエラー検出情報を出力する。
【００３３】
以下、この誤り検出装置１の動作を、図５を参照して説明する。図５は、誤り検出装置１が行うＣＲＣチェック処理を説明するためのフローチャートである。図５に示すＣＲＣチェック処理は、データ入力部１１にチェック対象のデータが入力された際に、逐次開始される。
【００３４】
まず、演算処理部１２は、データ入力部１１から入力データを取得する（ステップＳ１１）。例えば、演算処理部１２は、チェック対象となる３０ビットのデータを取得する。
【００３５】
演算処理部１２は、変数ｉに初期値の「１」をセットする（ステップＳ１２）。なお、この変数ｉは、チェック対象データと合算生成データとの排他的論理和の回数をカウントするために使用される。
【００３６】
演算処理部１２は、対象４ビットに対応する合算生成データを取得する（ステップＳ１３）。すなわち、演算処理部１２は、チェック対象データ中の対象４ビットを特定し、特定した対象４ビットに対応する合算生成データを記憶部１３に記憶された生成データテーブル１３１から取得する。
例えば、演算処理部１２は、図６（ａ）に示すような３０ビットのチェック対象データから対象４ビット（「１０１０」）を特定し、特定した対象４ビットに対応する合算生成データ（「１０１００１０００１」）を図２に示す生成データテーブル１３１から取得する。
【００３７】
演算処理部１２は、取得した合算生成データと入力データとの排他的論理和を演算する（ステップＳ１４）。例えば、演算処理部１２は、図６（ａ）に示すように、チェック対象データと合算生成データ（「１０１００１０００１」）との排他的論理和を演算する。
【００３８】
演算処理部１２は、変数ｉが「６」より小さいか否かを判別する（ステップＳ１５）。演算処理部１２は、変数ｉが「６」より小さいと判別した場合、変数ｉに「１」を加算して（ステップＳ１６）、上述のステップＳ１３に処理を戻す。そして、演算処理部１２は、前回のステップＳ１４にて演算された結果（演算結果）から次の対象４ビットを特定し、特定した対象４ビットに対応する合算生成データを生成データテーブル１３１から取得する。更に、演算処理部１２は、取得した合算生成データと前回の演算結果との排他的論理和を演算する。
このようなステップＳ１３、Ｓ１４の処理を、演算処理部１２は、変数ｉが「６」となるまで繰り返す。
【００３９】
すなわち、演算処理部１２は、変数ｉが「２」のときに、図６（ｂ）に示すように対象４ビット（「００１０」）に対応する合算生成データ（「００１０１１００１０」）を生成データテーブル１３１から取得し、演算結果と合算生成データとの排他的論理和を演算する。
また、演算処理部１２は、変数ｉが「３」のときに、図６（ｃ）に示すように対象４ビット（「１１１１」）に対応する合算生成データ（「１１１１１１０１０１」）を取得し、排他的論理和を演算する。
以下同様に、演算処理部１２は、変数ｉが「４」のときに、図６（ｄ）に示すように排他的論理和を演算し、変数ｉが「５」のときに、図６（ｅ）に示すように排他的論理和を演算し、そして、変数ｉが「６」のときに、図６（ｆ）に示すように排他的論理和を演算する。
【００４０】
図５に戻って、演算処理部１２は、ステップＳ１５にて、変数ｉが「６」以上である（「６」より小さくない）と判別した場合、剰余が発生しているか否かを判別する（ステップＳ１７）。すなわち、上述の６回にわたるチェック対象データ（前回の演算結果）と合算生成データとの排他的論理和の演算により得られた演算結果に、剰余が含まれているか否かを判別する。
【００４１】
演算処理部１２は、剰余が発生していると判別した場合、所定のエラー検出情報を生成して、エラー出力部１４に供給する（ステップＳ１８）。演算処理部１２は、エラー検出情報をエラー出力部１４に供給すると、ＣＲＣチェック処理を終了する。
【００４２】
一方、剰余が発生していないと判別した場合、演算処理部１２は、全データのＣＲＣチェックが完了したか否かを判別する（ステップＳ１９）。すなわち、データ入力部１１が入力したデータを全て処理したか否かを判別する。
【００４３】
演算処理部１２は、全データの処理が完了していないと判別した場合、ステップＳ１１に処理を戻し、上述のステップＳ１１〜Ｓ１９の処理を繰り返し実行する。一方、全データの処理が完了したと判別した場合、演算処理部１２は、ＣＲＣチェック処理を終了する。
【００４４】
このように、チェック対象データと合算生成データとの演算を、チェック対象データの４ビット単位に繰り返すことにより、チェック対象データの生成多項式による除算を少ない演算処理にて実現できる。この結果、ＣＲＣチェックを高速に行うことができる。
【００４５】
次に、上述した誤り検出装置１を構成に含んだ具体的な機器について、ＣＤ−ＲＯＭ装置を一例として説明する。
図７は、本発明の他の実施の形態に係るＣＤ−ＲＯＭ装置の一例を示す模式図である。図示するように、ＣＤ−ＲＯＭ装置１００は、誤り検出装置１と、処理制御部２と、制御信号入力部３と、信号処理回路４と、トラッキングスレッドサーボ回路５と、光ピックアップ６と、スピンドルサーボ回路７と、データバッファ８とを備えて構成される。
【００４６】
誤り検出装置１は、上述の図１に示したように、データ入力部１１と、演算処理部１２と、記憶部１３と、エラー出力部１４とからなり、信号処理回路４から供給された例えば、２０６０バイトのデータを演算処理し、データエラーが生じているか否かを判別する。
【００４７】
なお、記憶部１３には、上述の図２と異なり、図８（ａ）に示すような生成データテーブル１３２が予め記憶される。この生成データテーブル１３２は、チェック対象データ中の対象１バイトと、合算生成データとの対応関係を規定するテーブルである。すなわち、生成データテーブル１３２は、２５６個の対象１バイト（「００００００００」〜「１１１１１１１１」）に対応する合算生成データを規定するテーブルである。
【００４８】
この合算生成データは、排他的論理和の演算に使用される生成多項式を対象１バイトのビット配列に従って合算したデータである。なお、生成多項式には、多項式Ｇ（ｘ）＝Ｘ^３２＋Ｘ^３１＋Ｘ^１６＋Ｘ^１５＋Ｘ^４＋Ｘ^３＋Ｘ＋１が用いられる。これは、チェック対象のデータが２０６０バイトであることから、誤り検出の精度を向上させるためである。また、対象を１バイトとしたのは、ＣＲＣチェック処理をバイト単位に行うことにより、処理効率を更に高めるためである。
【００４９】
合算生成データについて具体的に説明すると、合算生成データは、例えば、チェック対象データにおける対象１バイト（上位１バイト）のビット配列が「１１１１１１１１」である場合、図８（ｂ）に示すように、多項式Ｇ（ｘ）の先頭位置（ビット配置）をずらしたＬ１、Ｌ３、Ｌ５及びＬ７がそれぞれ合算され（排他的論理和が演算され）、ΣＬとして求められる。同様に他の合算生成データも、対象１バイトのビット配列に応じて予め求めらる。
このような、合算生成データが、対象１バイトの２５６種類のビット配列に応じて予め求められ、それぞれのビット配列に対応づけられた生成データテーブル１３２が記憶部１３に記憶されている。
【００５０】
図７に戻って、処理制御部２は、ＣＰＵ及び周辺ＬＳＩ（ＬａｒｇｅＳｃａｌｅＩｎｔｅｇｒａｔｉｏｎ）を含んだ１チップマイコン等からなり、ＣＤ−ＲＯＭ装置１００全体を制御する。
すなわち、処理制御部２は、信号処理回路４を制御して、信号処理回路４が図示せぬＣＤ−ＲＯＭから光ピックアップ６を介して読み出したデータを誤り検出装置１に供給させる。また、処理制御部２は、誤り検出装置１からエラー検出情報を取得すると、信号処理回路４に対してデータの再読み出しを指示する。
【００５１】
制御信号入力部３は、所定のパーソナルコンピュータ等の機器から送られる制御信号を入力し、処理制御部２に供給する。
【００５２】
信号処理回路４は、トラッキングスレッドサーボ回路５、光ピックアップ６及び、スピンドルサーボ回路７等を制御する。そして、信号処理回路４は、光ピックアップ６を介して、ＣＤ−ＲＯＭに記録されたデータを読み出す。
例えば、信号処理回路４は、１セクタ分となる２０６０バイトのデータをＣＤ−ＲＯＭから読み出し、読み出した情報を誤り検出装置１等に供給する。
【００５３】
トラッキングスレッドサーボ回路５は、光ピックアップ６をＣＤ−ＲＯＭの径方向に平行移動させるための図示せぬスレッドモータを駆動制御し、光ピックアップ６をＣＤ−ＲＯＭの記録面上の所定の位置へ移動させる。
【００５４】
光ピックアップ６は、所定の波長のレーザ光をＣＤ−ＲＯＭの記録面に向けて照射し、その反射光を受けて電気信号に変換する。光ピックアップ６は、変換した電気信号を読み出したデータとして信号処理回路４に供給する。
【００５５】
スピンドルサーボ回路７は、ＣＤ−ＲＯＭを搭載する所定のターンテーブルを回転させるための図示せぬスピンドルモータを駆動制御し、所定の回転速度で回転駆動させる。
【００５６】
データバッファ８は、誤り検出装置１にてＣＲＣチェックがなされたデータを信号処理回路４から取得し、所定のパーソナルコンピュータ等に向けて出力する。
【００５７】
以下、上述のＣＤ−ＲＯＭ装置１００における誤り検出装置１の動作を、簡単に説明する。
誤り検出装置１は、信号処理回路４から送られる２０６０バイトのチェック対象データを取得する。誤り検出装置１は、チェック対象データ中の対象１バイトを特定し、特定した１バイトのビット配列に対応する合算生成データを生成データテーブル１３２から取得する。
誤り検出装置１は、取得した合算生成データとチェック対象データとの排他的論理和を演算する。
そして、誤り検出装置１は、前回の演算結果から次の対象１バイトを特定し、特定した対象１バイトのビット配列に対応する合算生成データを生成データテーブル１３２から取得する。更に、演算処理部１２は、取得した合算生成データと前回の演算結果との排他的論理和を演算する。
このような演算処理を所定回数繰り返した後に、誤り検出装置１は、最終的に得られた演算結果に、剰余が含まれているか否かを判別する。誤り検出装置１は、剰余が含まれていると判別した場合、処理制御部２にエラー検出情報を出力する。
【００５８】
このように、チェック対象データと合算生成データとの演算を、チェック対象データの１バイト単位に繰り返すことにより、チェック対象データの生成多項式による除算を少ない演算処理にて実現できる。この結果、ＣＲＣチェックを高速に行うことができる。
【００５９】
なお、上記の実施の形態では、ＣＤ−ＲＯＭ装置等におけるＣＲＣチェックについて説明したが、ＣＲＣチェックの対象は任意である。例えば、ＦＤドライブ、メモリ、ＭＰＥＧ変換装置、通信装置、及び、ハードディスク等種々の機器にて行われるＣＲＣチェックに適用可能である。
【００６０】
なお、この発明の誤り検出装置は、専用のシステムによらず、通常のコンピュータシステムを用いて実現可能である。例えば、コンピュータに上述のいずれかを実行するためのプログラムを格納した媒体（フロッピーディスク、ＣＤ−ＲＯＭ等）から該プログラムをインストールすることにより、上述の処理を実行する誤り検出装置を構成することができる。
【００６１】
また、コンピュータにプログラムを供給するための手法は、任意である。例えば、通信回線、通信ネットワーク、通信システム等を介して供給してもよい。一例を挙げると、通信ネットワークの掲示板（ＢＢＳ）に当該プログラムを掲示し、これをネットワークを介して配信する。
そして、このプログラムを起動し、ＯＳの制御下で、他のアプリケーションプログラムと同様に実行することにより、上述の処理を実行することができる。
【００６２】
【発明の効果】
以上説明したように、本発明によれば、ＣＲＣチェックを高速に行うことができる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係る誤り検出装置の構成の一例を示すブロック図である。
【図２】記憶部に記憶される生成データテーブルの一例を示す模式図である。
【図３】合算生成データの算出について説明する模式図である。
【図４】（ａ）が従来の多項式を使用して排他的論理和の演算を順次行う様子を説明するための模式図であり、（ｂ）が合算生成データを使用して排他的論理和の演算を行う様子を説明するための模式図である。
【図５】本発明の実施の形態に係るＣＲＣチェック処理を説明するためのフローチャートである。
【図６】ＣＲＣチェック処理により、チェック対象データと合算生成データとの排他的論理和の演算が順次行われる様子を説明するための模式図である。
【図７】誤り検出装置が含まれるＣＤ−ＲＯＭ装置の構成の一例を説明するための模式図である。
【図８】（ａ）が記憶部に記憶される生成データテーブルの一例を示す模式図であり、（ｂ）が合算生成データの算出について説明する模式図である。
【図９】生成多項式にてデータが除算される様子を説明するための模式図である。
【図１０】従来の巡回符号生成処理において演算される対象データと多項式との排他的論理和について説明するための模式図である。
【図１１】従来のＣＲＣチェック処理において演算される対象データと多項式との排他的論理和について説明するための模式図である。
【符号の説明】
１誤り検出装置
２処理制御部
３制御信号入力部
４信号処理回路
５トラッキングスレッドサーボ回路
６光ピックアップ
７スピンドルサーボ回路
８データバッファ
１１データ入力部
１２演算処理部
１３記憶部
１４エラー出力部[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an error detection apparatus that detects an error in acquired data using a CRC (Cyclic Redundancy Check) method, and more particularly to an error detection apparatus, a CRC check method, and a recording medium that can process a CRC check at high speed.
[0002]
[Prior art]
Conventionally, data error detection has been performed in order to determine whether transmitted data, data read from a predetermined medium, and the like have been acquired without error. For this error detection, a parity check method or a checksum method has been used.
In the parity check method, for example, on the transmission side, another 1 bit is added to the data for one character represented by 7 to 8 bits, and the total number of bits of “1” is always odd (or even). Data is generated in such a way that it becomes individual. The receiving side determines that an error has occurred when the number of bits of “1” in the acquired data (for one character) is not an odd number (or an even number).
In the checksum method, for example, on the transmission side, a sum total of data strings in a block of a certain length is obtained, and the lowest digit 1 byte of the obtained total value is added to the end of the block. Generate data. Then, on the receiving side, the total value in the block of the acquired data is obtained, and the lowest digit 1 byte of the total value is compared with the last 1 byte, and if they do not match, it is determined that an error has occurred. To do.
[0003]
In recent years, the CRC (Cyclic Redundancy Check) method has been used for error detection because the error detection capability is higher than those of the parity check method and the like, and the error can be corrected depending on the situation. . In the CRC method, for example, a cyclic code is obtained using a predetermined generation polynomial for each block of data on the transmission side, and data to which the obtained cyclic code is added is generated. Then, the receiving side divides the acquired data by the same generator polynomial for each block, and determines that an error has occurred when it is not divisible (a remainder has occurred).
[0004]
Hereinafter, for this CRC system, data to be transmitted is data D (D = X ²³ + X ²¹ + X ¹⁸ + X ¹⁷ + X ¹⁴ + X ¹³ + X ¹² + X ¹¹ + X ¹⁰ + X ⁶ + X ⁴ + X ³ +1) and the generator polynomial is a polynomial G (G = X ⁶ + X ⁴ + X ³ +1) will be described as an example.
The transmitting side adds X to the data D as the highest order term of the polynomial G ⁶ Data DX multiplied by (DX = X ²⁹ + X ²⁷ + X ²⁴ + X ²³ + X ²⁰ + X ¹⁹ + X ¹⁸ + X ¹⁷ + X ¹⁶ + X ¹² + X ¹⁰ + X ⁹ + X ⁶ ) Is divided by the polynomial G, and the remainder is obtained as a cyclic code.
That is, as shown in FIG. 9, the transmission side divides the data DX by the polynomial G and uses X as the remainder. ³ + X ² Find + X. This X ³ + X ² + X is a cyclic code.
[0005]
More specifically, in this case, the data DX is expressed as “10100110011111000101100100000”, and the polynomial G is expressed as “1011001”.
When the data DX is divided by the polynomial G, only the remainder is actually required (because the quotient is not necessary), so that the transmission side excludes the data DX and the polynomial G as shown in FIG. The logical OR (xor) is sequentially calculated, and “1110” (that is, X ³ + X ² + X).
The transmitting side generates this remainder, that is, data obtained by adding the cyclic code to the data DX (“101001100111110001011001001110”), and transmits it to the receiving side.
[0006]
The receiving side divides the received data by the same polynomial G, and determines that an error has occurred when a remainder occurs. That is, as shown in FIG. 11, the receiving side sequentially calculates an exclusive OR of the received data (“101001100111110001011001001110”) and the polynomial G (“1011001”) to determine whether there is a remainder.
In this way, the presence / absence of the remainder can be determined by the calculation using the received data and the polynomial G, and the error detection of the received data can be performed with high accuracy.
[0007]
[Problems to be solved by the invention]
However, as described with reference to FIG. 10 and FIG. 11 described above, the division of data by the polynomial G is different from the polynomial G combined with the bit arrangement when the upper bit of the check target data or the like is “1”. It is necessary to perform an exclusive OR operation, and in the case of “0”, it is necessary to repeatedly perform an operation process of shifting and referring to the next bit.
In other words, since arithmetic processing is performed in units of bits and it is necessary to perform a large number of operations such as exclusive OR, the processing load for error detection increases and the overall processing efficiency is reduced.
[0008]
Further, for example, when reading data recorded in a CD-ROM, it is necessary to perform error detection on data of 2060 bytes, which is the data amount for one sector. At this time, the generator polynomial has a higher order polynomial, for example, a polynomial G (x) = X because of the improvement in error detection accuracy. ³² + X ³¹ + X ¹⁶ + X ¹⁵ + X ⁴ + X ³ + X + 1 will be used.
In this case, since an operation such as exclusive OR is repeatedly performed for each bit of 2060 bytes of data, the processing load becomes extremely large, and there is a problem that processing must be performed for a long time for error detection. It was.
[0009]
The present invention has been made in view of the above circumstances, and an object thereof is to provide an error detection device, a CRC check method, and a recording medium that can perform a CRC check at high speed.
[0010]
[Means for Solving the Problems]
In order to achieve the above object, an error detection apparatus according to the first aspect of the present invention provides:
Storage means for preliminarily storing sum generation data generated by summing a predetermined generator polynomial according to a bit arrangement for a plurality of bits;
An arithmetic means for calculating an exclusive OR of the bit strings;
Input means for inputting CRC (Cyclic Redundancy Check) check target data;
The bit arrangement for a plurality of bits is specified from the data input by the input means or the calculation result data previously generated by the calculation means, and the sum generation data corresponding to the specified bit arrangement is acquired from the storage means. Acquisition means;
Control means for causing the calculation means to perform a predetermined number of calculations on the data input by the input means or calculation result data generated by the previous calculation by the calculation means and the sum generation data acquired by the acquisition means;
An error detection means for detecting an error in data input by the input means according to a calculation result generated by a calculation repeated a predetermined number of times by the calculation means under the control of the control means;
It is characterized by providing.
[0011]
According to the present invention, the storage unit stores in advance the combined generation data generated by adding the predetermined generation polynomials according to the bit arrangement for a plurality of bits. The computing means computes an exclusive OR of the bit strings. The input means inputs data for CRC check. The acquisition unit specifies a bit array for a plurality of bits from the data input by the input unit or the calculation result data generated by the previous calculation by the calculation unit, and acquires the sum generation data corresponding to the specified bit arrangement from the storage unit. To do. The control unit causes the calculation unit to perform a predetermined number of calculations on the data input by the input unit or the calculation result data generated by the previous calculation by the calculation unit and the sum generation data acquired by the acquisition unit. The error detection means detects an error in the data input by the input means according to the calculation result generated by the calculation repeated a predetermined number of times by the calculation means under the control of the control means. In this way, by repeating the calculation of the check target data and the sum generation data in units of a plurality of bits of the check target data, the division of the check target data by the generating polynomial can be realized with a small number of calculation processes. As a result, the CRC check can be performed at high speed.
[0012]
In order to achieve the above object, an error detection apparatus according to the second aspect of the present invention provides:
Storage means for preliminarily storing the sum generation data generated by summing the generator polynomials having different bit arrangements according to the bit arrangement for 1 byte;
An arithmetic means for calculating an exclusive OR of the bit strings;
An input means for inputting CRC check target data;
The bit arrangement for 1 byte is specified from the data input by the input means or the calculation result data generated by the previous calculation by the calculation means, and the sum generation data corresponding to the specified bit arrangement is acquired from the storage means. Acquisition means;
Control means for causing the calculation means to perform a predetermined number of calculations on the data input by the input means or calculation result data generated by the previous calculation by the calculation means and the sum generation data acquired by the acquisition means;
An error detection means for detecting an error in the data input by the input means when a remainder is included in the calculation result generated by the calculation repeated a predetermined number of times by the control means under the control of the control means;
It is characterized by providing.
[0013]
According to the present invention, the storage means stores in advance the combined generation data generated by adding the generator polynomials having different bit arrangements according to the bit arrangement for 1 byte. The computing means computes an exclusive OR of the bit strings. The input means inputs data for CRC check. The acquisition unit specifies the bit array for one byte from the data input by the input unit or the calculation result data generated by the previous calculation by the calculation unit, and acquires the total generation data corresponding to the specified bit arrangement from the storage unit. To do. The control unit causes the calculation unit to perform a predetermined number of calculations on the data input by the input unit or the calculation result data generated by the previous calculation by the calculation unit and the sum generation data acquired by the acquisition unit. The error detection means detects an error in the data input by the input means when the calculation result generated by the calculation repeated by the calculation means a predetermined number of times under the control of the control means includes a remainder. As described above, by repeating the calculation of the check target data and the sum generation data in units of 1 byte of the check target data, the division of the check target data by the generating polynomial can be realized with a small number of arithmetic processes. As a result, the CRC check can be performed at high speed.
[0014]
In order to achieve the above object, a CRC check method according to a third aspect of the present invention includes:
An operation step of calculating an exclusive OR of the bit strings;
An input step for inputting data subject to CRC check;
A bit array for a plurality of bits is specified from the data input in the input step or the calculation result data generated previously in the calculation step, and a generator polynomial determined by the specified bit array is added and generated. An acquisition step of acquiring the combined generation data from a predetermined storage unit;
The calculation step is performed a predetermined number of times in the calculation step with the data input in the input step or the calculation result data generated by the previous calculation in the calculation step and the sum generation data acquired in the acquisition step. Control steps
An error detection step for detecting an error in the data input in the input step according to a calculation result generated by the calculation repeated a predetermined number of times in the calculation step by the control step;
It is characterized by providing.
[0015]
According to this invention, the operation step calculates an exclusive OR of the bit strings. In the input step, data for CRC check is input. The acquisition step specifies a bit array for a plurality of bits from the data input in the input step or the operation result data generated by the previous operation in the operation step, and the generator polynomial determined by the specified bit array is added together. The generated sum generation data is acquired from a predetermined storage unit. The control step performs a predetermined number of operations in the calculation step on the data input in the input step or the calculation result data generated in the previous calculation step and the sum generation data acquired in the acquisition step. Make it. In the error detection step, an error in the data input in the input step is detected according to the calculation result generated by the calculation repeated a predetermined number of times in the calculation step under the control of the control step. In this way, by repeating the calculation of the check target data and the sum generation data in units of a plurality of bits of the check target data, the division of the check target data by the generating polynomial can be realized with a small number of calculation processes. As a result, the CRC check can be performed at high speed.
[0016]
In order to achieve the above object, a CRC check method according to a fourth aspect of the present invention includes:
An operation step of calculating an exclusive OR of the bit strings;
An input step for inputting data subject to CRC check;
From the data input in the input step or the calculation result data generated by the previous calculation in the calculation step, the bit arrangement for 1 byte is specified, and different generator polynomials having different bit arrangements determined by the specified bit arrangement are provided. An acquisition step of acquiring the combined generation data generated by the addition from a predetermined storage unit;
The calculation step is performed a predetermined number of times in the calculation step with the data input in the input step or the calculation result data generated by the previous calculation in the calculation step and the sum generation data acquired in the acquisition step. Control steps
An error detection step of detecting an error in the data input in the input step when a remainder is included in the calculation result generated by the calculation repeated a predetermined number of times in the calculation step by the control step;
It is characterized by providing.
[0017]
According to this invention, the operation step calculates an exclusive OR of the bit strings. In the input step, data for CRC check is input. The acquisition step specifies the bit arrangement for one byte from the data input in the input step or the calculation result data generated in the previous calculation step, and generates different bit arrangements determined by the specified bit arrangement. The total generation data generated by adding the polynomials is acquired from a predetermined storage unit. The control step performs a predetermined number of operations in the calculation step on the data input in the input step or the calculation result data generated in the previous calculation step and the sum generation data acquired in the acquisition step. Make it. The error detection step detects an error in the data input in the input step when a remainder is included in the calculation result generated by the calculation repeated a predetermined number of times in the calculation step under the control of the control step. As described above, by repeating the calculation of the check target data and the sum generation data in units of 1 byte of the check target data, the division of the check target data by the generating polynomial can be realized with a small number of arithmetic processes. As a result, the CRC check can be performed at high speed.
[0018]
In order to achieve the above object, a recording medium according to the fifth aspect of the present invention provides:
Calculation step for calculating exclusive OR of bit strings, input step for inputting CRC check target data, data input in the input step, or calculation result generated by previous calculation in the calculation step A bit sequence for a plurality of bits is specified from data, an acquisition step for acquiring a total generation data generated by adding a generator polynomial determined by the specified bit sequence from a predetermined storage unit, and input in the input step A control step for causing the calculation step to perform a predetermined number of calculations on the data or the calculation result data generated by the previous calculation in the calculation step and the sum generation data acquired in the acquisition step; and the control step According to the calculation result generated by the calculation repeated a predetermined number of times in the calculation step by the control of Recording a program for executing a CRC checking method having an error detection step of detecting an error in data input by the input step into the computer.
[0019]
DETAILED DESCRIPTION OF THE INVENTION
An error detection apparatus according to an embodiment of the present invention will be described below with reference to the drawings.
[0020]
FIG. 1 is a block diagram showing an example of an error detection apparatus applied to the embodiment of the present invention. As shown in the figure, the error detection device 1 includes a data input unit 11, an arithmetic processing unit 12, a storage unit 13, and an error output unit 14.
The data input unit 11 sequentially inputs data to be checked and supplies the input data to the arithmetic processing unit 12.
[0021]
The arithmetic processing unit 12 includes a CPU (Central Processing Unit) and the like, and determines whether or not a data error has occurred by performing arithmetic processing on the check target data supplied from the data input unit 11. Specifically, the arithmetic processing unit 12 executes a CRC check process, which will be described later, and determines the presence or absence of an error according to the result of the arithmetic process using the sum generation data determined from, for example, the target 4 bits in the check target data. The combined generation data will be described later.
[0022]
The storage unit 13 includes a ROM (Read Only Memory) or the like, and stores a generation data table 131 as illustrated in FIG. 2 in advance, for example.
The generation data table 131 is a table that defines the correspondence between the target 4 bits in the check target data and the combined generation data. That is, the generation data table 131 is a table that defines the total generation data (“0000000” to “1111110101”) corresponding to 16 target 4 bits (“0000” to “1111”).
[0023]
This sum generation data is data obtained by summing the generator polynomial used for the exclusive OR operation according to the target 4-bit bit array. The generator polynomial is a polynomial G (G = X ⁶ + X ⁴ + X ³ +1) is used. Hereinafter, the combined generation data will be specifically described.
[0024]
For example, when the bit arrangement of the target 4 bits (upper 4 bits) in the check target data is “1111”, as shown in FIG. 3, L1, L2, and L4 obtained by shifting the start position (bit arrangement) of the polynomial G are Each is summed (exclusive OR is computed), and summed data is obtained as ΣL.
[0025]
By the way, in the case of the conventional division, for example, as shown in FIG. 4A, exclusive OR of the check target data (“1111...”) And the polynomial G (“1011001”) is sequentially calculated. Specifically, the exclusive OR of the target data and L1 is calculated first, the exclusive OR of the operation result and L2 is calculated, and the exclusive OR of the operation result and L4 is further calculated. To do.
That is, when the target 4 bits of the check target data is “1111”, the calculation shown in the following formula 1 is performed on the data. Note that (D) ′ shown in Equation 1 represents the result of dividing the data D once by the polynomial G.
[0026]
[Expression 1]
(D) '= D xor L1
(D) '' = (D) 'xor L2
(D) '''=(D)''xor L4
[0027]
If the relationship between (D) ″ ′ and D is derived from Equation 1, the relationship represented by Equation 2 is established.
[0028]
[Expression 2]

[0029]
As shown in Equation 2, by calculating the exclusive OR of the data D and the operation result of the addition (exclusive OR) of L1, L2, and L4 with the bit arrangement of the polynomial G shifted, A final calculation result that is the same can be obtained.
That is, the operation result (“00000111...”) Of the exclusive OR of the data to be checked shown in FIG. 4B and ΣL obtained by adding L1, L2, and L4 is shown in FIG. It becomes equal to the final calculation result shown.
From this, Formula 3 is established.
[0030]
[Equation 3]
(D) '''= D xor ΣL
[0031]
That is, by using ΣL generated by adding up the polynomial G used for exclusive OR, that is, by using the generated data, 4 bits (“1111”) as shown in FIG. On the other hand, the exclusive OR operation, which is required three times, can be performed all at once as shown in FIG.
Such combined generation data is obtained in advance according to 16 types of bit arrays (“0000” to “1111”) of the target 4 bits, and a generation data table 131 associated with each bit array is stored in the storage unit 13. Is remembered.
[0032]
Returning to FIG. 1, the error output unit 14 outputs predetermined error detection information indicating that a data error has been detected when an error is detected according to the calculation processing result of the calculation processing unit 12.
[0033]
Hereinafter, the operation of the error detection apparatus 1 will be described with reference to FIG. FIG. 5 is a flowchart for explaining the CRC check process performed by the error detection apparatus 1. The CRC check process illustrated in FIG. 5 is sequentially started when data to be checked is input to the data input unit 11.
[0034]
First, the arithmetic processing unit 12 acquires input data from the data input unit 11 (step S11). For example, the arithmetic processing unit 12 acquires 30-bit data to be checked.
[0035]
The arithmetic processing unit 12 sets an initial value “1” to the variable i (step S12). The variable i is used to count the number of exclusive ORs between the check target data and the sum generation data.
[0036]
The arithmetic processing unit 12 acquires sum generation data corresponding to the target 4 bits (step S13). That is, the arithmetic processing unit 12 specifies the target 4 bits in the check target data, and acquires the total generation data corresponding to the specified target 4 bits from the generation data table 131 stored in the storage unit 13.
For example, the arithmetic processing unit 12 identifies the target 4 bits (“1010”) from the 30-bit check target data as illustrated in FIG. 6A, and adds the sum generation data (“101001001” corresponding to the identified target 4 bits. Is obtained from the generation data table 131 shown in FIG.
[0037]
The arithmetic processing unit 12 calculates an exclusive OR of the acquired sum generation data and the input data (step S14). For example, as illustrated in FIG. 6A, the arithmetic processing unit 12 calculates an exclusive OR of the check target data and the sum generation data (“101001001”).
[0038]
The arithmetic processing unit 12 determines whether or not the variable i is smaller than “6” (step S15). When determining that the variable i is smaller than “6”, the arithmetic processing unit 12 adds “1” to the variable i (step S16), and returns the process to the above-described step S13. Then, the arithmetic processing unit 12 specifies the next target 4 bits from the result (calculation result) calculated in the previous step S <b> 14, and acquires the total generation data corresponding to the specified target 4 bits from the generation data table 131. To do. Further, the arithmetic processing unit 12 calculates an exclusive OR of the acquired sum generation data and the previous calculation result.
The arithmetic processing unit 12 repeats the processes in steps S13 and S14 until the variable i becomes “6”.
[0039]
That is, when the variable i is “2”, the arithmetic processing unit 12 generates the sum generation data (“0010110010”) corresponding to the target 4 bits (“0010110010”) as shown in FIG. 6B. The exclusive OR of the operation result and the sum generation data is calculated.
Further, when the variable i is “3”, the arithmetic processing unit 12 acquires the sum generation data (“1111110101”) corresponding to the target 4 bits (“1111”) as illustrated in FIG. Calculate exclusive OR.
Similarly, when the variable i is “4”, the arithmetic processing unit 12 calculates an exclusive OR as shown in FIG. 6D, and when the variable i is “5”, The exclusive OR is calculated as shown in e), and when the variable i is “6”, the exclusive OR is calculated as shown in FIG.
[0040]
Returning to FIG. 5, when the arithmetic processing unit 12 determines in step S15 that the variable i is “6” or more (not smaller than “6”), the arithmetic processing unit 12 determines whether or not a remainder is generated. (Step S17). That is, it is determined whether or not a remainder is included in the operation result obtained by the exclusive OR operation of the check target data (previous operation result) and the sum generation data as described above.
[0041]
If it is determined that a remainder has occurred, the arithmetic processing unit 12 generates predetermined error detection information and supplies it to the error output unit 14 (step S18). When the arithmetic processing unit 12 supplies the error detection information to the error output unit 14, the arithmetic processing unit 12 ends the CRC check process.
[0042]
On the other hand, if it is determined that no remainder has occurred, the arithmetic processing unit 12 determines whether or not the CRC check of all data has been completed (step S19). That is, it is determined whether or not all data input by the data input unit 11 has been processed.
[0043]
If it is determined that the processing of all data has not been completed, the arithmetic processing unit 12 returns the process to step S11 and repeatedly executes the processes of steps S11 to S19 described above. On the other hand, if it is determined that all data has been processed, the arithmetic processing unit 12 ends the CRC check process.
[0044]
As described above, by repeating the calculation of the check target data and the sum generation data in units of 4 bits of the check target data, division by the generation polynomial of the check target data can be realized with a small number of arithmetic processing. As a result, the CRC check can be performed at high speed.
[0045]
Next, specific devices including the above-described error detection device 1 will be described by taking a CD-ROM device as an example.
FIG. 7 is a schematic diagram showing an example of a CD-ROM device according to another embodiment of the present invention. As shown in the figure, the CD-ROM device 100 includes an error detection device 1, a processing control unit 2, a control signal input unit 3, a signal processing circuit 4, a tracking thread servo circuit 5, an optical pickup 6, and a spindle. A servo circuit 7 and a data buffer 8 are provided.
[0046]
As shown in FIG. 1, the error detection apparatus 1 includes a data input unit 11, an arithmetic processing unit 12, a storage unit 13, and an error output unit 14, and is supplied from the signal processing circuit 4, for example. , 2060 bytes of data are arithmetically processed to determine whether or not a data error has occurred.
[0047]
Note that, unlike the above-described FIG. 2, the storage unit 13 stores in advance a generation data table 132 as shown in FIG. The generated data table 132 is a table that defines the correspondence between the target 1 byte in the check target data and the combined generated data. In other words, the generation data table 132 is a table that defines the total generation data corresponding to 256 target 1 bytes (“00000000” to “11111111”).
[0048]
This sum generation data is data obtained by summing generator polynomials used for exclusive OR operation according to the bit array of the target 1 byte. Note that the generator polynomial is a polynomial G (x) = X ³² + X ³¹ + X ¹⁶ + X ¹⁵ + X ⁴ + X ³ + X + 1 is used. This is to improve the accuracy of error detection because the data to be checked is 2060 bytes. The reason for setting the target to 1 byte is to further improve the processing efficiency by performing the CRC check process in units of bytes.
[0049]
The combined generation data will be specifically described. For example, when the bit array of the target 1 byte (upper 1 byte) in the check target data is “11111111”, as illustrated in FIG. L1, L3, L5, and L7 obtained by shifting the starting position (bit arrangement) of the polynomial G (x) are summed (exclusive OR is calculated) and obtained as ΣL. Similarly, other sum generation data is also obtained in advance according to the bit arrangement of the target 1 byte.
Such combined generation data is obtained in advance according to 256 types of bit arrangements of the target 1 byte, and a generation data table 132 associated with each bit arrangement is stored in the storage unit 13.
[0050]
Returning to FIG. 7, the processing control unit 2 includes a one-chip microcomputer including a CPU and a peripheral LSI (Large Scale Integration), and controls the entire CD-ROM device 100.
That is, the processing control unit 2 controls the signal processing circuit 4 to supply the error detection device 1 with data read from the CD-ROM (not shown) via the optical pickup 6 by the signal processing circuit 4. Further, when acquiring the error detection information from the error detection device 1, the processing control unit 2 instructs the signal processing circuit 4 to reread data.
[0051]
The control signal input unit 3 inputs a control signal sent from a predetermined device such as a personal computer and supplies it to the processing control unit 2.
[0052]
The signal processing circuit 4 controls the tracking thread servo circuit 5, the optical pickup 6, the spindle servo circuit 7, and the like. Then, the signal processing circuit 4 reads out the data recorded on the CD-ROM via the optical pickup 6.
For example, the signal processing circuit 4 reads 2060-byte data corresponding to one sector from the CD-ROM, and supplies the read information to the error detection device 1 or the like.
[0053]
The tracking sled servo circuit 5 drives and controls a thread motor (not shown) for translating the optical pickup 6 in the radial direction of the CD-ROM, and moves the optical pickup 6 to a predetermined position on the recording surface of the CD-ROM. Let
[0054]
The optical pickup 6 irradiates a recording surface of the CD-ROM with laser light having a predetermined wavelength, receives the reflected light, and converts it into an electrical signal. The optical pickup 6 supplies the converted electric signal to the signal processing circuit 4 as read data.
[0055]
The spindle servo circuit 7 drives and controls a spindle motor (not shown) for rotating a predetermined turntable on which the CD-ROM is mounted, and rotates the spindle motor at a predetermined rotation speed.
[0056]
The data buffer 8 acquires the data that has been CRC checked by the error detection device 1 from the signal processing circuit 4 and outputs the data to a predetermined personal computer or the like.
[0057]
Hereinafter, the operation of the error detection device 1 in the CD-ROM device 100 will be briefly described.
The error detection apparatus 1 acquires 2060-byte check target data sent from the signal processing circuit 4. The error detection device 1 specifies one target byte in the check target data, and acquires the total generation data corresponding to the specified one-byte bit array from the generation data table 132.
The error detection apparatus 1 calculates an exclusive OR of the acquired sum generation data and the check target data.
Then, the error detection apparatus 1 specifies the next target 1 byte from the previous calculation result, and acquires the total generation data corresponding to the bit array of the specified target 1 byte from the generation data table 132. Further, the arithmetic processing unit 12 calculates an exclusive OR of the acquired sum generation data and the previous calculation result.
After repeating such arithmetic processing a predetermined number of times, the error detection apparatus 1 determines whether or not a remainder is included in the finally obtained calculation result. When the error detection device 1 determines that the remainder is included, the error detection device 1 outputs error detection information to the processing control unit 2.
[0058]
As described above, by repeating the calculation of the check target data and the sum generation data in units of 1 byte of the check target data, the division of the check target data by the generating polynomial can be realized with a small number of arithmetic processes. As a result, the CRC check can be performed at high speed.
[0059]
In the above embodiment, the CRC check in the CD-ROM device or the like has been described, but the CRC check target is arbitrary. For example, the present invention can be applied to CRC check performed in various devices such as an FD drive, a memory, an MPEG conversion device, a communication device, and a hard disk.
[0060]
Note that the error detection apparatus of the present invention can be realized using a normal computer system, not a dedicated system. For example, by installing the program from a medium (floppy disk, CD-ROM, etc.) storing a program for executing any of the above in a computer, an error detection apparatus that executes the above-described processing may be configured. it can.
[0061]
A method for supplying the program to the computer is arbitrary. For example, you may supply via a communication line, a communication network, a communication system, etc. As an example, the program is posted on a bulletin board (BBS) of a communication network, and is distributed via the network.
Then, the above-described processing can be executed by starting this program and executing it in the same manner as other application programs under the control of the OS.
[0062]
【The invention's effect】
As described above, according to the present invention, the CRC check can be performed at high speed.
[Brief description of the drawings]
FIG. 1 is a block diagram showing an example of the configuration of an error detection apparatus according to an embodiment of the present invention.
FIG. 2 is a schematic diagram illustrating an example of a generated data table stored in a storage unit.
FIG. 3 is a schematic diagram illustrating calculation of sum generation data.
FIG. 4A is a schematic diagram for explaining a state in which exclusive OR operation is sequentially performed using a conventional polynomial, and FIG. 4B is an exclusive OR using sum generation data. It is a schematic diagram for demonstrating a mode that this calculation is performed.
FIG. 5 is a flowchart for explaining CRC check processing according to the embodiment of the present invention;
FIG. 6 is a schematic diagram for explaining a state in which an exclusive OR operation of check target data and sum generation data is sequentially performed by CRC check processing.
FIG. 7 is a schematic diagram for explaining an example of the configuration of a CD-ROM device including an error detection device.
FIG. 8A is a schematic diagram illustrating an example of a generated data table stored in a storage unit, and FIG. 8B is a schematic diagram illustrating calculation of combined generated data.
FIG. 9 is a schematic diagram for explaining how data is divided by a generator polynomial.
FIG. 10 is a schematic diagram for explaining exclusive OR of target data and a polynomial calculated in a conventional cyclic code generation process.
FIG. 11 is a schematic diagram for explaining an exclusive OR of target data and a polynomial calculated in a conventional CRC check process.
[Explanation of symbols]
1 Error detection device
2 Processing control unit
3 Control signal input section
4 signal processing circuit
5 Tracking thread servo circuit
6 Optical pickup
7 Spindle servo circuit
8 Data buffer
11 Data input part
12 Arithmetic processing part
13 Memory unit
14 Error output section

Claims

Storage means for preliminarily storing sum generation data generated by summing a predetermined generator polynomial according to a bit arrangement for a plurality of bits;
An arithmetic means for calculating an exclusive OR of the bit strings;
Input means for inputting CRC (Cyclic Redundancy Check) check target data;
The bit arrangement for a plurality of bits is specified from the data input by the input means or the calculation result data previously generated by the calculation means, and the sum generation data corresponding to the specified bit arrangement is acquired from the storage means. Acquisition means;
Control means for causing the calculation means to perform a predetermined number of calculations on the data input by the input means or calculation result data generated by the previous calculation by the calculation means and the sum generation data acquired by the acquisition means;
An error detection means for detecting an error in data input by the input means according to a calculation result generated by a calculation repeated a predetermined number of times by the calculation means under the control of the control means;
An error detection apparatus comprising:

Storage means for preliminarily storing the sum generation data generated by summing the generator polynomials having different bit arrangements according to the bit arrangement for 1 byte;
An arithmetic means for calculating an exclusive OR of the bit strings;
An input means for inputting CRC check target data;
The bit arrangement for 1 byte is specified from the data input by the input means or the calculation result data generated by the previous calculation by the calculation means, and the sum generation data corresponding to the specified bit arrangement is acquired from the storage means. Acquisition means;
Control means for causing the calculation means to perform a predetermined number of calculations on the data input by the input means or calculation result data generated by the previous calculation by the calculation means and the sum generation data acquired by the acquisition means;
An error detection means for detecting an error in the data input by the input means when a remainder is included in the calculation result generated by the calculation repeated a predetermined number of times by the control means under the control of the control means;
An error detection apparatus comprising:

An operation step of calculating an exclusive OR of the bit strings;
An input step for inputting data subject to CRC check;
A bit array for a plurality of bits is specified from the data input in the input step or the calculation result data generated previously in the calculation step, and a generator polynomial determined by the specified bit array is added and generated. An acquisition step of acquiring the combined generation data from a predetermined storage unit;
The calculation step is performed a predetermined number of times in the calculation step with the data input in the input step or the calculation result data generated by the previous calculation in the calculation step and the sum generation data acquired in the acquisition step. Control steps
An error detection step for detecting an error in the data input in the input step according to a calculation result generated by the calculation repeated a predetermined number of times in the calculation step by the control step;
A CRC check method comprising:

An operation step of calculating an exclusive OR of the bit strings;
An input step for inputting data subject to CRC check;
From the data input in the input step or the calculation result data generated by the previous calculation in the calculation step, the bit array for 1 byte is specified, and different generator polynomials having different bit arrangements determined by the specified bit arrangement are provided. An acquisition step of acquiring the combined generation data generated by the addition from a predetermined storage unit;
The calculation step is performed a predetermined number of times in the calculation step with the data input in the input step or the calculation result data generated by the previous calculation in the calculation step and the sum generation data acquired in the acquisition step. Control steps
An error detection step for detecting an error in the data input in the input step when a remainder is included in the calculation result generated by the calculation repeated a predetermined number of times in the calculation step by the control step;
A CRC check method comprising:

Calculation step for calculating exclusive OR of bit strings, input step for inputting CRC check target data, data input in the input step, or calculation result generated by previous calculation in the calculation step A bit sequence for a plurality of bits is specified from data, an acquisition step for acquiring a total generation data generated by adding a generator polynomial determined by the specified bit sequence from a predetermined storage unit, and input in the input step A control step for causing the calculation step to perform a predetermined number of calculations on the data or the calculation result data generated by the previous calculation in the calculation step and the sum generation data acquired in the acquisition step; and the control step According to the calculation result generated by the calculation repeated a predetermined number of times in the calculation step by the control of A computer-readable recording medium storing a program for executing a CRC checking method in a computer having an error detection step of detecting an error in data input in the input step.