(57)【要約】【課題】複数の対象データについての誤り検出を簡便な作業で、かつ、高い精度で行う。【解決手段】３組の単位データＤ１，Ｄ２，Ｄ３のそれぞれに、巡回冗長検査法により生成した一次誤り検出コードＣ１，Ｃ２，Ｃ３を付加し、３組の誤り検出コード付き単位データＤ１＊，Ｄ２＊，Ｄ３＊を生成する。これらを順に連結して連結データＬを生成した後、所定の組替位置Ｐで前半部分Ｌ（ａ）と後半部分Ｌ（ｂ）とに切り分け、両者の順序を入れ替えることにより、組み替え後の連結データＬ′を生成する。このデータＬ′の先頭から巡回冗長検査法による演算を行い、データＬ′全体についての二次誤り検出コードＥを生成し、元の連結データＬの末尾に付加し、誤り検出コード付き連結データを生成する。二次誤り検出コードＥについての整合性を確認すれば、３組の単位データＤ１，Ｄ２，Ｄ３全体についての誤り検出を簡便かつ正確に行うことができる。【選択図】図１６
2015135647.tif 000002
【特許請求の範囲】
【請求項１】
与えられたデータに誤り検出コードを付加することにより誤り検出コード付きデータを生成する方法であって、
コンピュータもしくは集積回路が、複数ｍ個の単位データを入力するデータ入力段階と、
コンピュータもしくは集積回路が、前記複数ｍ個の単位データのそれぞれについて、個別に所定のアルゴリズムに基づく演算を行って一次誤り検出コードを求める一次誤り検出コード演算段階と、
コンピュータもしくは集積回路が、前記複数ｍ個の単位データのそれぞれに、前記一次誤り検出コード演算段階で求めた一次誤り検出コードを付加することにより、複数ｍ個の誤り検出コード付き単位データを生成する誤り検出コード付き単位データ生成段階と、
コンピュータもしくは集積回路が、前記複数ｍ個の誤り検出コード付き単位データを順に連結することにより、連結データを生成する連結データ生成段階と、
コンピュータもしくは集積回路が、前記連結データについて、所定のアルゴリズムに基づく演算を行って二次誤り検出コードを求める二次誤り検出コード演算段階と、
コンピュータもしくは集積回路が、前記連結データに前記二次誤り検出コードを付加することにより、誤り検出コード付き連結データを生成する誤り検出コード付き連結データ生成段階と、
を有することを特徴とする誤り検出コード付きデータの生成方法。
【請求項２】
請求項１に記載の誤り検出コード付きデータの生成方法において、
一次誤り検出コード演算段階で一次誤り検出コードを求めるアルゴリズムおよび二次誤り検出コード演算段階で二次誤り検出コードを求めるアルゴリズムとして、巡回冗長検査法に基づく所定の生成多項式を用いた除算アルゴリズムを用い、当該除算アルゴリズムに基づく除算演算で得られた余りを誤り検出コードとして用いることを特徴とする誤り検出コード付きデータの生成方法。
【請求項３】
請求項２に記載の誤り検出コード付きデータの生成方法において、
一次誤り検出コード演算段階で行う除算演算と、二次誤り検出コード演算段階で行う除算演算とで、互いに異なる生成多項式に対応する除数を用いた演算を行うことを特徴とする誤り検出コード付きデータの生成方法。
【請求項４】
請求項２に記載の誤り検出コード付きデータの生成方法において、
一次誤り検出コード演算段階で行う除算演算と、二次誤り検出コード演算段階で行う除算演算とで、同一の生成多項式に対応する除数を用いた演算を行い、
二次誤り検出コード演算段階で、連結データに対して組み替えを行い、組み替え後の連結データについて、除算演算を行って二次誤り検出コードを求めることを特徴とする誤り検出コード付きデータの生成方法。
【請求項５】
請求項４に記載の誤り検出コード付きデータの生成方法において、
二次誤り検出コード演算段階で、連結データを、誤り検出コード付き単位データの境界位置ではない所定位置で前半部分と後半部分とに切り分け、前記前半部分と前記後半部分とを入れ替えることにより、連結データに対する組み替えを行うことを特徴とする誤り検出コード付きデータの生成方法。
【請求項６】
請求項４に記載の誤り検出コード付きデータの生成方法において、
二次誤り検出コード演算段階で、連結データを、所定の方法でｎ分割（但し、ｎ≧３）して、ｎ個の分割データを生成し、この分割データを所定の方法で並び替えることにより、連結データに対する組み替えを行うことを特徴とする誤り検出コード付きデータの生成方法。
【請求項７】
請求項４に記載の誤り検出コード付きデータの生成方法において、
二次誤り検出コード演算段階で、連結データを構成する個々の誤り検出コード付き単位データを、それぞれ所定位置で前半部分と後半部分とに切り分け、個々の誤り検出コード付き単位データごとに、前記前半部分と前記後半部分とを入れ替えることにより、連結データに対する組み替えを行うことを特徴とする誤り検出コード付きデータの生成方法。
【請求項８】
請求項１に記載の誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する方法であって、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データから連結データを抽出し、抽出した連結データに対して、二次誤り検出コード演算段階で行われた演算と同じアルゴリズムに基づく演算を行って二次誤り検出コードを求める二次誤り検出コード再演算段階と、
コンピュータもしくは集積回路が、前記二次誤り検出コード再演算段階によって得られた二次誤り検出コードと、前記検出対象となる誤り検出コード付き連結データに含まれていた二次誤り検出コードと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定を行う一致判定段階と、
を有することを特徴とする誤り検出コード付きデータに対する誤り検出方法。
【請求項９】
請求項２または３に記載の誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する方法であって、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データから連結データを抽出し、抽出した連結データに対して、二次誤り検出コード演算段階で行われた演算と同じ巡回冗長検査法に基づく演算を行って二次誤り検出コードを求める二次誤り検出コード再演算段階と、
コンピュータもしくは集積回路が、前記二次誤り検出コード再演算段階によって得られた二次誤り検出コードと、前記検出対象となる誤り検出コード付き連結データに含まれていた二次誤り検出コードと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定を行う一致判定段階と、
を有することを特徴とする誤り検出コード付きデータに対する誤り検出方法。
【請求項１０】
請求項２または３に記載の誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する方法であって、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データ全体に対して、二次誤り検出コード演算段階で行われた演算と同じ巡回冗長検査法に基づく生成多項式を用いた除算アルゴリズムに基づく演算を行って余りを求める二次誤り検出コード再演算段階と、
コンピュータが、前記二次誤り検出コード再演算段階によって得られた余りが零であった場合は誤り無し、零でなかった場合は誤り有り、との判定を行う一致判定段階と、
を有することを特徴とする誤り検出コード付きデータに対する誤り検出方法。
【請求項１１】
請求項４〜７のいずれかに記載の誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する方法であって、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データから連結データを抽出し、抽出した連結データに対して、二次誤り検出コード演算段階で行われた組み替えと同じ組み替えを行い、組み替え後の連結データに対して、二次誤り検出コード演算段階で行われた演算と同じ巡回冗長検査法に基づく演算を行って二次誤り検出コードを求める二次誤り検出コード再演算段階と、
コンピュータもしくは集積回路が、前記二次誤り検出コード再演算段階によって得られた二次誤り検出コードと、前記検出対象となる誤り検出コード付き連結データに含まれていた二次誤り検出コードと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定を行う一致判定段階と、
を有することを特徴とする誤り検出コード付きデータに対する誤り検出方法。
【請求項１２】
請求項４〜７のいずれかに記載の誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する方法であって、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データから連結データを抽出し、抽出した連結データに対して、二次誤り検出コード演算段階で行われた組み替えと同じ組み替えを行い、組み替え後の連結データに、前記検出対象となる誤り検出コード付き連結データに含まれていた二次誤り検出コードを付加し、得られたデータに対して、二次誤り検出コード演算段階で行われた演算と同じ巡回冗長検査法に基づく演算を行って余りを求める二次誤り検出コード再演算段階と、
コンピュータが、前記二次誤り検出コード再演算段階によって得られた余りが零であった場合は誤り無し、零でなかった場合は誤り有り、との判定を行う一致判定段階と、
を有することを特徴とする誤り検出コード付きデータに対する誤り検出方法。
【請求項１３】
請求項１〜１２のいずれかに記載の誤り検出コード付きデータの生成方法もしくは誤り検出コード付きデータに対する誤り検出方法をコンピュータに実行させるプログラム。
【請求項１４】
請求項１〜１２のいずれかに記載の誤り検出コード付きデータの生成方法もしくは誤り検出コード付きデータに対する誤り検出方法を実行する集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り検出コード付きデータの生成方法および誤り検出方法に関し、特に、巡回冗長検査法を利用して誤り検出コードを生成し、この誤り検出コードを用いて誤り検出を行うのに適した技術に関する。
【背景技術】
【０００２】
デジタルデータに対して、保存、読出、送信、受信といった作業を行うと、様々な要因によってデータに誤りが生じる可能性がある。そこで、従来から、デジタルデータを取り扱う際に、誤りの発生を検出したり、更に、誤りを自動訂正したりする様々な技術が提案され実用化されている。もちろん、理論的には、誤りの検出だけでなく、検出された誤りの自動訂正まで行う技術の方が優れている。ただ、自動訂正の処理を行うには、システムに大きな演算負荷がかかるため、用途によっては、誤り検出だけを行うシステムも広く利用されている。
【０００３】
このような誤り検出を行う方法としては、対象となるデータに誤り検出コードを付加しておき、この誤り検出コードの整合性を確認する手法が一般に利用されている。現在、最も広く普及している誤り検出の手法は、巡回冗長検査（ＣＲＣ：Cyclic Redundancy Check）と呼ばれている手法であり、対象データに対して、所定の生成多項式を用いた除算アルゴリズムを用いた除算演算を施し、得られた余りを誤り検出コードとして元の対象データに付加する方法が採られる。このような方法で、誤り検出コード付きデータを生成しておけば、元の対象データに対する誤り検出コードの整合性を確認することにより、誤りの有無を判定することができる。
【０００４】
たとえば、下記の特許文献１には、対象データをビットストリームとして伝送する際に、効率的な巡回冗長検査を行って誤り検出を行う方法が開示されている。また、特許文献２には、巡回冗長検査に基づく誤り検出演算を高速化することが可能な演算装置が開示されており、特許文献３には、データ送受信用のリンクの初期化処理を改善させることが可能な巡回冗長検査装置が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−００８７５８号公報
【特許文献２】特開２００１−２５１１９４号公報
【特許文献３】特表２００８−５２２４９４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述したように、現在、一般に行われている誤り検出の方法は、対象データについて、巡回冗長検査法などのアルゴリズムを利用して誤り検出コードを付加し、誤り検出コード付きデータを生成しておき、対象となるデータについての誤り検出コードの整合性に基づいて誤りの有無を判定する手法を採用している。このため、個々の対象データが複数にわたる場合、誤り検出作業が煩雑になるという問題がある。たとえば、個々のファイルを対象データとしてそれぞれに誤り検出コードを付加した場合、複数ｍ個のファイルについての誤り検出作業は、個々のファイルごとに誤り検出コードの整合性を確認する作業をｍ回繰り返して行う必要がある。
【０００７】
また、従来の誤り検出の手法には、特定のソフトウエア層では誤り検出が可能であっても、別なソフトウエア層では誤り検出ができない、という問題がある。たとえば、複数のファイルのそれぞれに誤り検出コードを付加した場合を考えてみる。この場合、個々のファイルをそれぞれ区別して認識可能なソフトウエア層であれば誤り検出が可能であるが、当該複数のファイルを一塊のデータ群としてしか把握することができないソフトウエア層では、当該データ群から個々のファイルを抽出することができないので、誤り検出コードを認識することはできない。
【０００８】
そこで本発明は、複数の対象データについての誤り検出を簡便な作業で行うことが可能であり、また、幅広いソフトウエア層に適用可能な誤り検出コード付きデータの生成方法および誤り検出方法を提供することを目的とする。更に、巡回冗長検査法を利用して誤り検出コードを付加する場合については、複数の対象データについての誤り検出を簡便な作業で、かつ、より高い精度で行うことが可能な誤り検出コード付きデータの生成方法および誤り検出方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
(1)   本発明の第１の態様は、与えられたデータに誤り検出コードを付加することにより誤り検出コード付きデータを生成する誤り検出コード付きデータの生成方法において、
コンピュータもしくは集積回路が、複数ｍ個の単位データを入力するデータ入力段階と、
コンピュータもしくは集積回路が、複数ｍ個の単位データのそれぞれについて、個別に所定のアルゴリズムに基づく演算を行って一次誤り検出コードを求める一次誤り検出コード演算段階と、
コンピュータもしくは集積回路が、複数ｍ個の単位データのそれぞれに、一次誤り検出コード演算段階で求めた一次誤り検出コードを付加することにより、複数ｍ個の誤り検出コード付き単位データを生成する誤り検出コード付き単位データ生成段階と、
コンピュータもしくは集積回路が、複数ｍ個の誤り検出コード付き単位データを順に連結することにより、連結データを生成する連結データ生成段階と、
コンピュータもしくは集積回路が、連結データについて、所定のアルゴリズムに基づく演算を行って二次誤り検出コードを求める二次誤り検出コード演算段階と、
コンピュータもしくは集積回路が、連結データに二次誤り検出コードを付加することにより、誤り検出コード付き連結データを生成する誤り検出コード付き連結データ生成段階と、
を行うようにしたものである。
【００１０】
(2)   本発明の第２の態様は、上述した第１の態様に係る誤り検出コード付きデータの生成方法において、
一次誤り検出コード演算段階で一次誤り検出コードを求めるアルゴリズムおよび二次誤り検出コード演算段階で二次誤り検出コードを求めるアルゴリズムとして、巡回冗長検査法に基づく所定の生成多項式を用いた除算アルゴリズムを用い、当該除算アルゴリズムに基づく除算演算で得られた余りを誤り検出コードとして用いるようにしたものである。
【００１１】
(3)   本発明の第３の態様は、上述した第２の態様に係る誤り検出コード付きデータの生成方法において、
一次誤り検出コード演算段階で行う除算演算と、二次誤り検出コード演算段階で行う除算演算とで、互いに異なる生成多項式に対応する除数を用いた演算を行うようにしたものである。
【００１２】
(4)   本発明の第４の態様は、上述した第２の態様に係る誤り検出コード付きデータの生成方法において、
一次誤り検出コード演算段階で行う除算演算と、二次誤り検出コード演算段階で行う除算演算とで、同一の生成多項式に対応する除数を用いた演算を行い、
二次誤り検出コード演算段階で、連結データに対して組み替えを行い、組み替え後の連結データについて、除算演算を行って二次誤り検出コードを求めるようにしたものである。
【００１３】
(5)   本発明の第５の態様は、上述した第４の態様に係る誤り検出コード付きデータの生成方法において、
二次誤り検出コード演算段階で、連結データを、誤り検出コード付き単位データの境界位置ではない所定位置で前半部分と後半部分とに切り分け、前半部分と後半部分とを入れ替えることにより、連結データに対する組み替えを行うようにしたものである。
【００１４】
(6)   本発明の第６の態様は、上述した第４の態様に係る誤り検出コード付きデータの生成方法において、
二次誤り検出コード演算段階で、連結データを、所定の方法でｎ分割（但し、ｎ≧３）して、ｎ個の分割データを生成し、この分割データを所定の方法で並び替えることにより、連結データに対する組み替えを行うようにしたものである。
【００１５】
(7)   本発明の第７の態様は、上述した第４の態様に係る誤り検出コード付きデータの生成方法において、
二次誤り検出コード演算段階で、連結データを構成する個々の誤り検出コード付き単位データを、それぞれ所定位置で前半部分と後半部分とに切り分け、個々の誤り検出コード付き単位データごとに、前半部分と後半部分とを入れ替えることにより、連結データに対する組み替えを行うようにしたものである。
【００１６】
(8)   本発明の第８の態様は、上述した第１の態様に係る誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する、誤り検出コード付きデータに対する誤り検出方法において、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データから連結データを抽出し、抽出した連結データに対して、二次誤り検出コード演算段階で行われた演算と同じアルゴリズムに基づく演算を行って二次誤り検出コードを求める二次誤り検出コード再演算段階と、
コンピュータもしくは集積回路が、二次誤り検出コード再演算段階によって得られた二次誤り検出コードと、検出対象となる誤り検出コード付き連結データに含まれていた二次誤り検出コードと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定を行う一致判定段階と、
を行うようにしたものである。
【００１７】
(9)   本発明の第９の態様は、上述した第２または第３の態様に係る誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する、誤り検出コード付きデータに対する誤り検出方法において、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データから連結データを抽出し、抽出した連結データに対して、二次誤り検出コード演算段階で行われた演算と同じ巡回冗長検査法に基づく演算を行って二次誤り検出コードを求める二次誤り検出コード再演算段階と、
コンピュータもしくは集積回路が、二次誤り検出コード再演算段階によって得られた二次誤り検出コードと、検出対象となる誤り検出コード付き連結データに含まれていた二次誤り検出コードと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定を行う一致判定段階と、
を行うようにしたものである。
【００１８】
(10)  本発明の第１０の態様は、上述した第２または第３の態様に係る誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する、誤り検出コード付きデータに対する誤り検出方法において、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データ全体に対して、二次誤り検出コード演算段階で行われた演算と同じ巡回冗長検査法に基づく生成多項式を用いた除算アルゴリズムに基づく演算を行って余りを求める二次誤り検出コード再演算段階と、
コンピュータが、二次誤り検出コード再演算段階によって得られた余りが零であった場合は誤り無し、零でなかった場合は誤り有り、との判定を行う一致判定段階と、
を行うようにしたものである。
【００１９】
(11)  本発明の第１１の態様は、上述した第４〜第７の態様に係る誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する、誤り検出コード付きデータに対する誤り検出方法において、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データから連結データを抽出し、抽出した連結データに対して、二次誤り検出コード演算段階で行われた組み替えと同じ組み替えを行い、組み替え後の連結データに対して、二次誤り検出コード演算段階で行われた演算と同じ巡回冗長検査法に基づく演算を行って二次誤り検出コードを求める二次誤り検出コード再演算段階と、
コンピュータもしくは集積回路が、二次誤り検出コード再演算段階によって得られた二次誤り検出コードと、検出対象となる誤り検出コード付き連結データに含まれていた二次誤り検出コードと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定を行う一致判定段階と、
を行うようにしたものである。
【００２０】
(12)  本発明の第１２の態様は、上述した第４〜第７の態様に係る誤り検出コード付きデータの生成方法を前提として生成された誤り検出コード付き連結データに対して、誤りの有無を検出する、誤り検出コード付きデータに対する誤り検出方法において、
コンピュータもしくは集積回路が、検出対象となる誤り検出コード付き連結データから連結データを抽出し、抽出した連結データに対して、二次誤り検出コード演算段階で行われた組み替えと同じ組み替えを行い、組み替え後の連結データに、検出対象となる誤り検出コード付き連結データに含まれていた二次誤り検出コードを付加し、得られたデータに対して、二次誤り検出コード演算段階で行われた演算と同じ巡回冗長検査法に基づく演算を行って余りを求める二次誤り検出コード再演算段階と、
コンピュータが、二次誤り検出コード再演算段階によって得られた余りが零であった場合は誤り無し、零でなかった場合は誤り有り、との判定を行う一致判定段階と、
を行うようにしたものである。
【００２１】
(13)  本発明の第１３の態様は、上述した第１〜第１２の態様に係る誤り検出コード付きデータの生成方法もしくは誤り検出コード付きデータに対する誤り検出方法を、コンピュータにプログラムを組み込むことにより実行するようにしたものである。
【００２２】
(14)  本発明の第１４の態様は、上述した第１〜第１２の態様に係る誤り検出コード付きデータの生成方法もしくは誤り検出コード付きデータに対する誤り検出方法を、専用の集積回路により実行するようにしたものである。
【発明の効果】
【００２３】
本発明に係る誤り検出コード付きデータの生成方法および誤り検出方法によれば、複数ｍ個の単位データに対してそれぞれ一次誤り検出コードを付加して誤り検出コード付き単位データを生成した後、これらを連結して得られる連結データ全体に対して二次誤り検出コードを付加して誤り検出コード付き連結データを生成する処理が行われる。このため、二次誤り検出コードの整合性を確認するだけの簡便な作業で、複数ｍ個の単位データ全体についての誤り検出を行うことが可能になる。また、より幅広いソフトウエア層に適用可能な誤り検出の手法を提供することができる。
【００２４】
更に、巡回冗長検査法を利用して誤り検出コードを付加する実施形態の場合は、一次誤り検出コードの生成演算と二次誤り検出コードの生成演算とで異なる生成多項式に対応する除数を用いた演算を行うか、もしくは、連結データに対して組み替えを行った上で二次誤り検出コードを求める演算を行うようにしたため、より高い精度で誤り検出を行うことが可能になる。
【図面の簡単な説明】
【００２５】
【図１】一般的な誤り検出コード付きデータの生成方法の原理を示すブロック図である。
【図２】図１に示す誤り検出コード付きデータに基づく誤り検出方法の原理を示すブロック図である。
【図３】図１に示す誤り検出コード付きデータの具体的な態様を示す図である。
【図４】巡回冗長検査法に基づく誤り検出コード付きデータの生成方法の一例を示すブロック図である。
【図５】図４に示す例についての具体的な除算アルゴリズムを示す図である。
【図６】一般的な巡回冗長検査法の基本原理を示す図である。
【図７】複数の誤り検出コード付き単位データを含むグループデータの一例を示す図である。
【図８】本発明に係る誤り検出コード付きデータの生成方法の基本原理を示すブロック図である。
【図９】本発明に係る誤り検出コード付きデータの生成方法の基本手順を示す流れ図である。
【図１０】本発明に係る誤り検出コード付きデータに対する誤り検出方法の基本手順を示す流れ図である。
【図１１】連結データについての二次誤り検出コードによる誤り検出が失敗する例を示すブロック図である。
【図１２】連結データについての二次誤り検出コードによる誤り検出が失敗する具体例を示す図である。
【図１３】図１２に示す連結データＬについて、二次誤り検出コードＥを求める具体的な除算アルゴリズムを示す図である。
【図１４】巡回冗長検査法で利用されている生成多項式の具体例を示す図である。
【図１５】本発明に係る誤り検出コード付きデータの生成方法の基本手順を示すブロック図である。
【図１６】本発明において、連結データに対して組み替えを行う誤り検出コード付きデータの生成方法の第１の実施形態を示すブロック図である。
【図１７】本発明において、連結データに対して組み替えを行う誤り検出コード付きデータの生成方法の第２の実施形態を示すブロック図である。
【図１８】本発明において、連結データに対して組み替えを行う誤り検出コード付きデータの生成方法の第３の実施形態を示すブロック図である。
【発明を実施するための形態】
【００２６】
以下、本発明を図示する実施形態に基づいて説明する。
【００２７】
＜＜＜  §１．  一般的な誤り検出コードの生成方法  ＞＞＞
はじめに、現在実用化されている一般的な誤り検出コードの生成方法、特に、巡回冗長検査法を利用した誤り検出コードの生成方法を簡単に説明しておく。図１は、一般的な誤り検出コード付きデータの生成方法の原理を示すブロック図である。
【００２８】
図に示す対象データＤは、誤り検出処理の対象となるデジタルデータであり、保存、読出、送信、受信といった作業を行うべき本来のデータということになる。一方、誤り検出コードＣは、対象データＤについて所定のアルゴリズムに基づく演算を行うことにより求められたコードである。この誤り検出コードＣを、元の対象データＤの末尾に付加することにより、図示する誤り検出コード付きデータＤ＊を生成することができる。
【００２９】
こうして、誤り検出コード付きデータＤ＊が生成されたら、対象データＤの代わりに、この誤り検出コード付きデータＤ＊について保存、読出、送信、受信といった作業を行うようにする。このような作業において、データを構成するビットに誤りが発生する可能性を零にすることは非常に困難であるが、作業対象が誤り検出コード付きデータＤ＊であれば、必要に応じて、誤りの有無を検出することができる。
【００３０】
図２は、図１に示す誤り検出コード付きデータＤ＊に基づく誤り検出方法の原理を示すブロック図である。たとえば、何らかの記憶媒体に保存されていたデータを読み出したとき、あるいは、何らかの送信元から送信されてきたデータを受信したとき、得られたデータが図２に示すような誤り検出コード付きデータＤ＊であれば、図２に示す方法により、誤りの有無を検出することができる。
【００３１】
具体的には、まず、誤り検出コード付きデータＤ＊を、対象データＤの部分と誤り検出コードＣの部分とに分離する。これは、図１に示す生成プロセスにおいて、予め「誤り検出コードの部分を４ビットとする」というような取り決めを行っておけば、誤り検出コード付きデータＤ＊の末尾４ビットの部分を誤り検出コードＣとして分離することができる。
【００３２】
続いて、分離した対象データＤについて、図１のプロセスで用いた同一のアルゴリズムに基づく演算を行うことにより、誤り検出コードＣを生成する。そして、誤り検出コード付きデータＤ＊の末尾から分離した誤り検出コードＣと新たに生成した誤り検出コードＣとが一致するか否かを判定すればよい。両者が一致すれば、誤りは無しと判断することができるが、不一致であれば、何らかの誤りが発生していると判断することができる。基本的には、対象データＤおよび誤り検出コードＣのうちの１ビットでもデータ化けを生じていると、上記判定で不一致が生じることになり、誤りが発生していることを検出することができる。
【００３３】
なお、図１のプロセスにおいて、対象データＤから誤り検出コードＣを求める所定の演算アルゴリズムとしては、通常、一方向関数を作用させる一方向演算が用いられている。このため、対象データＤに基づいて誤り検出コードＣを一義的に定めることはできるが、逆に、誤り検出コードＣから対象データＤを復元することはできない。したがって、図２の判定プロセスにおいてコードＣに不一致が生じ、誤りが発生していることが確認できたとしても、誤り検出コードＣに基づいて誤りを訂正することはできない。別言すれば、誤り検出コードＣは、あくまでも誤りの有無を検出するために利用されるコードであり、誤りを訂正する機能は有していない。
【００３４】
もちろん、誤りを訂正する情報が組み込まれた誤り訂正コードＥＣＣ（Error Correction Code）も広く利用されており、機能的には、誤り検出コードＣよりも優れている。しかしながら、誤り訂正コードＥＣＣに関する演算は複雑であり、その情報量（ビット長）も大きなものになるため、簡易的なシステムでは、誤りの有無を検出する機能のみをもった誤り検出コードＣも広く利用されている。本発明は、このような誤り検出コードＣを利用する技術に関するものである。
【００３５】
図３は、図１に示す誤り検出コード付きデータＤ＊の具体的な態様を示す図である。一般に、対象データＤは、任意のデータ長をもったデータであり、たとえば、１つのデータファイルを対象データＤとする場合、その容量は、数ＫＢ〜数ＭＢといった量になる。これに対して、誤り検出コードＣは、たかだか数ビット程度でも十分に機能を果たすことができる。後述する巡回冗長検査法を用いて誤り検出コードＣを生成する例の場合、４ビットの誤り検出コードＣを生成している。これは、対象データＤの容量にかかわらず、誤り検出コードＣは常に４ビットであることを意味する。
【００３６】
４ビットの誤り検出コードＣは、１６通りの状態を表すことができるので、誤り検出コードＣが偶然に一致する確率は１／１６である。より精度の高い誤り検出が必要な場合は、８ビットの誤り検出コードＣ（偶然一致確率１／２５６）や１６ビットの誤り検出コードＣ（偶然一致確率１／６５５３６）を利用すればよい。いずれにしても、対象データＤの容量に比べれば、誤り検出コードＣの容量は微々たるものである。ただ、本願実施例の説明では、便宜上、図１や図２に示す例のように、対象データＤと誤り検出コードＣとをほぼ同じサイズのブロックとして示すことにする。
【００３７】
現在、最も広く普及している誤り検出コードＣの生成方法は、巡回冗長検査（ＣＲＣ：Cyclic Redundancy Check）と呼ばれている手法であり、対象データに対して、所定の生成多項式に基づく除算アルゴリズムを用いた除算演算を施し、得られた余りを誤り検出コードとして利用するものである。
【００３８】
図４は、この巡回冗長検査法に基づく誤り検出コード付きデータの生成方法の原理を示すブロック図である。ここでは、８ビットの対象データＤ「１０００１１０１」について、除数Ｋ＝「１００１１」を用いた巡回冗長検査法に基づく除算演算（通常の算術的な除算とは若干異なる）を行い、得られた余り「１０１０」（通常、巡回冗長検査法の頭文字をとってＣＲＣと表記される）を誤り検出コードＣとする単純な例が示されている。この例の場合、８ビットの対象データＤ「１０００１１０１」に４ビットの誤り検出コードＣ「１０１０」を付加することにより、１２ビットからなる誤り検出コード付きデータＤ＊「１０００１１０１１０１０」が生成されることになる。
【００３９】
対象データＤ「１０００１１０１」に基づいて誤り検出コードＣ「１０１０」を求める演算は、原理的には、巡回冗長検査法に従った多項式の除算演算であり、所定の除数Ｋ（この例では、「１００１１」）に基づく特殊な除算に相当し、当該除算の余りが誤り検出コードＣ「１０１０」になる。一般に、除数Ｋをｎビットの２進数とすると、（ｎ−１）ビットの２進数からなる誤り検出コードＣが得られる。したがって、除数Ｋとして常に「１００１１」なる５ビットの２進数を用いることにすれば、誤り検出コードＣとしては常に４ビットの２進数が得られる。
【００４０】
図５は、図４に示す例についての具体的な除算アルゴリズムを示す図である。図の＜行１＞には、対象データＤ「１０００１１０１」の末尾に、４つのゼロからなる付加ビットＺ「００００」を付加した被除数が示されている。上述のとおり、除数Ｋとして「１００１１」なる５ビットの２進数を用いると、常に４ビットの余り（誤り検出コードＣ）が得られることになる。付加ビットＺ「００００」は、この４ビットの余りに対応する桁を確保するためのものである。
【００４１】
この巡回冗長検査法に基づく除算演算のプロセスでは、自然数の算術的な除算とは異なり、有限体ＧＦ（２）の係数をもつ多項式の計算を行う。すなわち、データのビットを多項式の係数として解釈し、加算及び減算を、係数（ビット）同士の排他的論理和演算（ＸＯＲ演算）で行う。本願における「除算演算」とは、この巡回冗長検査法に基づく除算演算を意味するものである。具体的には、まず、＜行２＞に示すように、除数「１００１１」を被除数の先頭桁に揃えるように配置し、上下のビット間でＸＯＲ演算を行い、その結果を＜行３＞に記載する。そして、被除数の演算に必要な桁（除数と同じになるように全５桁）を＜行３＞に降ろし、＜行４＞に示すように、除数「１００１１」を被除数の零でない先頭桁に揃えるように配置し、上下のビット間でＸＯＲ演算を行い、その結果を＜行５＞に記載する。
【００４２】
同様に、被除数の演算に必要な桁を＜行５＞に降ろし、＜行６＞に示すように、除数「１００１１」を被除数の零でない先頭桁に揃えるように配置し、上下のビット間でＸＯＲ演算を行い、その結果を＜行７＞に記載する。続いて、被除数の演算に必要な桁を＜行７＞に降ろし、＜行８＞に示すように、除数「１００１１」を被除数の零でない先頭桁に揃えるように配置し、上下のビット間でＸＯＲ演算を行い、その結果を＜行９＞に記載する。この段階では、もう被除数の演算に必要な５桁を確保することができないので、ここで演算は終了し、＜行９＞に最後に残った余り「１０１０」が誤り検出コードＣになる。この誤り検出コードＣを元の対象データＤの末尾に付加することにより「１０００１１０１１０１０」なる誤り検出コード付き単位データＤ＊が得られる。
【００４３】
このように、巡回冗長検査法に基づく除算演算のプロセスは、被除数の先頭側のビットから順にＸＯＲを求める演算を行うだけでよいので、システムにとっての演算負担は比較的軽いものになる。このため、通常は、当該除算演算プロセスを実行するための専用の半導体集積回路を設けて高速処理が行われる。
【００４４】
図６は、一般的な巡回冗長検査法の基本原理を示す図である。この巡回冗長検査法は、数学的には、式(1) に示すように、ａ（ｘ）÷ｆ（ｘ）＝ｑ（ｘ）・・・ｒ（ｘ）なる多項式の除算に基づいている。ここで、多項式ａ（ｘ）は、その各係数が対象データＤの各ビットに対応するものになっている。たとえば、式(2) に示す７次の多項式ａ（ｘ）の係数「１０００１１０１」は、図４に示す対象データＤに対応し、式(3) に示す４次の多項式ｆ（ｘ）の係数「１００１１」は、図４に示す除数Ｋに対応する。式(3) を整理すると、式(4) に示すように、「ｆ（ｘ）＝ｘ４＋ｘ＋１」なる式になる。この式(4) は、この巡回冗長検査法に基づく除算演算における生成多項式と呼ばれており、図５に示す演算は、当該生成多項式を用いた除算アルゴリズムに基づく演算ということになる。
【００４５】
式(1) に基づく多項式の演算において、実際には、商ｑ（ｘ）は用いられず、余りｒ（ｘ）の係数が誤り検出コードＣとして用いられることになる。図４に示す誤り検出コードＣは、実際には、式(5) に示す余りｒ（ｘ）に相当する３次多項式の係数ということになり、図５に示す演算は、この余りｒ（ｘ）に相当する多項式の係数を求める演算に他ならない。
【００４６】
ここでは、式(4) に示す生成多項式「ｆ（ｘ）＝ｘ４＋ｘ＋１」を用いた除算演算の例を示したが、実用上は、この他にも様々な生成多項式が利用されている。もちろん、用いる生成多項式が異なれば、得られる誤り検出コードＣも異なったものになる。以上、巡回冗長検査法の基本原理を簡単に説明したが、このような基本原理は公知の技術であるため、ここでは詳しい説明は省略する。
【００４７】
＜＜＜  §２．  本発明の基本概念および基本的な実施形態  ＞＞＞
続いて、本発明の基本概念と基本的な実施形態を述べる。いま、図７に示すように、複数の誤り検出コード付きデータを含むグループデータＧの取扱いを考えてみよう。図示の例の場合、グループデータＧは、３組の誤り検出コード付き単位データＤ１＊，Ｄ２＊，Ｄ３＊の集合体によって構成されている。ここで、単位データＤ１，Ｄ２，Ｄ３は、図１に示す対象データＤに対応するものであり、それぞれ１つのまとまりをもったデータという意味で、ここでは「単位データ」と呼ぶことにする。
【００４８】
§１で述べたように、各単位データＤ１，Ｄ２，Ｄ３に対して、所定のアルゴリズムに基づく演算（たとえば、巡回冗長検査法に基づく除算演算）を行うことにより、それぞれ誤り検出コードＣ１，Ｃ２，Ｃ３が生成される。誤り検出コード付き単位データＤ１＊，Ｄ２＊，Ｄ３＊は、各単位データＤ１，Ｄ２，Ｄ３に、それぞれ誤り検出コードＣ１，Ｃ２，Ｃ３を付加することにより生成されたデータである。
【００４９】
ここでは、説明の便宜上、個々の単位データＤ１，Ｄ２，Ｄ３が、それぞれ独立したデータファイルＦ１，Ｆ２，Ｆ３を構成するデータであるものとしよう。別言すれば、３つのデータファイルＦ１，Ｆ２，Ｆ３が、それぞれ誤り検出コード付きデータＤ１＊，Ｄ２＊，Ｄ３＊の形式で保存されていることになる。そして、この３つのファイルＦ１，Ｆ２，Ｆ３を、グループデータＧという一群のデータとして読み出したり、あるいは受信したりする際に、誤り検出処理を行うことを考えてみる。
【００５０】
§１で述べたとおり、個々の誤り検出コードＣ１，Ｃ２，Ｃ３は、それぞれ個々の単位データＤ１，Ｄ２，Ｄ３に誤りが生じていないかどうかを検証するために利用できる。したがって、グループデータＧという一群のデータを読み出したり、受信したりした後に、誤り検出コードＣ１に基づいて単位データＤ１についての誤り検出作業を行い、誤り検出コードＣ２に基づいて単位データＤ２についての誤り検出作業を行い、誤り検出コードＣ３に基づいて単位データＤ３についての誤り検出作業を行えば、全単位データＤ１，Ｄ２，Ｄ３に対する検証が可能である。
【００５１】
しかしながら、グループデータＧという一群のデータ全体に対して、一括して保存、読出、送信、受信といった作業を行った場合に、その検証を個々の単位データごとに個別に行うのは効率的ではない。
【００５２】
たとえば、１０００人の顧客データがそれぞれ独立したファイルＦ１〜Ｆ１０００の形式で用意されており、これらのファイルＦ１〜Ｆ１０００を単位データＤ１〜Ｄ１０００として取扱うことを考える。ここでは、単位データＤ１〜Ｄ１０００に対してそれぞれ誤り検出コードＣ１〜Ｃ１０００を付加して誤り検出コード付きデータＤ１＊〜Ｄ１０００＊を生成し、これら一群のデータ全体がグループデータＧとして保存されている場合を考えてみよう。この場合、このグループデータＧを読み出し、これを所定の伝送路を介して送信し、受信側において誤り検出を行うには、受信したグループデータＧを１０００組の誤り検出コード付き単位データＤ１＊〜Ｄ１０００＊に分離した後、それぞれについての誤り検出作業を合計１０００回繰り返して行う必要があり、非効率的な作業にならざるを得ない。
【００５３】
また、特定のソフトウエア層では、大きなメモリ領域内に含まれる個々のデータの配置の詳細を把握しきれない場合があり、そのような場合、当該ソフトウエア層では、そもそも個々の単位データについての誤り検出コードを認識できないケースもある。たとえば、上例の場合、顧客データの管理を行うプログラムであれば、個々のファイルＦ１〜Ｆ１０００をそれぞれ単位データＤ１〜Ｄ１０００と認識することができるので、それぞれから誤り検出コードＣ１〜Ｃ１０００を認識することができるが、グループデータＧ全体を一群のデータとして送受信するプログラムの場合、個々の単位データＤ１〜Ｄ１０００を認識することができず、当然、誤り検出コードＣ１〜Ｃ１０００を認識することはできない。
【００５４】
本発明は、このような問題を解決することを目的とするものであり、その基本概念は、入れ子式に二重の誤り検出コードを付加する点にある。図８は、本発明に係る誤り検出コード付きデータの生成方法の基本原理を示すブロック図である。この図の上段に示す連結データＬは、図７に示すグループデータＧに対応するものであり、３組の誤り検出コード付きデータＤ１＊，Ｄ２＊，Ｄ３＊を順に連結したものである。ここでは、便宜上、この誤り検出コード付きデータＤ１＊，Ｄ２＊，Ｄ３＊に含まれている誤り検出コードＣ１，Ｃ２，Ｃ３を「一次誤り検出コード」と呼ぶことにする。
【００５５】
続いて、この連結データＬに対して、所定のアルゴリズムに基づく演算を行って二次誤り検出コードＥを求める。連結データＬは、データＤ１＊，Ｄ２＊，Ｄ３＊を順に連結したビット列から構成されているので、単位データＤ１〜Ｄ３から一次誤り検出コードＣ１〜Ｃ３を生成したのと同じアルゴリズムに基づく演算を行うことにより二次誤り検出コードＥを求めることができる。一次誤り検出コードＣ１〜Ｃ３が、それぞれ個別の単位データＤ１〜Ｄ３についての誤り検出コードであるのに対して、二次誤り検出コードＥは、個々の単位データＤ１〜Ｄ３および一次誤り検出コードＣ１〜Ｃ３をそっくり含めた連結データＬ全体に対する誤り検出コードということになる。
【００５６】
図８の下段に示すように、こうして生成した二次誤り検出コードＥを、元の連結データＬの末尾に付加すれば、誤り検出コード付き連結データＬ＊を生成することができる。そして、図７に示すグループデータＧの代わりに、図８に示す誤り検出コード付き連結データＬ＊を保存しておくようにすれば、これを読み出して送信した場合、受信側において二次誤り検出コードＥの整合性を確認するだけの簡便な作業で、連結データＬ全体についての誤り検出を行うことができる。すなわち、受信した誤り検出コード付き連結データＬ＊に含まれている連結データＬについて、図８に示すアルゴリズムに基づく演算を行うことにより二次誤り検出コードＥを求め、これが、受信した誤り検出コード付き連結データＬ＊に含まれている二次誤り検出コードＥに一致するか否かの判定を行えばよい。
【００５７】
このように、本発明では、個々の単位データＤ１〜Ｄ３について一次誤り検出コードＣ１〜Ｃ３が付加されるとともに、連結データＬ全体に対して二次誤り検出コードＥが付加され、誤り検出コードが入れ子式に二重に付されることになる。したがって、連結データＬ全体についての誤り検出を行うのであれば、二次誤り検出コードＥについての整合性確認を行えば足り、個々の一次誤り検出コードＣ１〜Ｃ３についての整合性確認を行う必要はない。したがって、複数の対象データについての誤り検出を簡便な作業で行うことが可能になる。
【００５８】
また、入れ子式に二重の誤り検出コードを付加しておくようにすれば、個々の単位データＤ１，Ｄ２，Ｄ３や、個々の一次誤り検出コードＣ１，Ｃ２，Ｃ３を認識することができない特定のソフトウエア層であっても、二次誤り検出コードＥを利用した誤り検出を行うことができるので、幅広いソフトウエア層に適用可能な誤り検出の手法を提供することができるようになる。その結果、特定のソフトウエア層の設計や実装の簡素化・簡略化というメリットも得られることになる。
【００５９】
もちろん、二次誤り検出コードＥについての整合性確認によって誤りが検出された場合には、個々の一次誤り検出コードＣ１〜Ｃ３についての整合性確認を行うことにより、どの単位データについて誤りが生じているかを判別することも可能である。また、前述したとおり、誤りが存在する場合でも、誤り検出コードが偶然に一致してしまう場合も所定の確率で起こり得る。したがって、一次誤り検出コードおよび二次誤り検出コードのうち、一方は一致、他方は不一致という結果になるケースが生じ得るが、この場合、両方の誤り検出コードの整合性確認を行うようにすれば、誤りの検出漏れを低減することができる（もちろん、誤りが存在するにもかかわらず、偶然、いずれの誤り検出コードについても整合性が確認されてしまうケースが生じた場合は、誤りの検出漏れが発生することになる）。
【００６０】
図９は、本発明に係る誤り検出コード付きデータの生成方法の基本手順を示す流れ図である。この基本手順は、与えられたデータに誤り検出コードを付加することにより誤り検出コード付きデータを生成する処理を行う手順であり、次のような各ステップによって構成されている。これらの各ステップは、汎用のコンピュータに専用のプログラムを組み込むことによってソフトウエアによる処理として実行することも可能であるが、実用上は、個々の処理を実行するための専用の集積回路を設け、ハードウエアによる処理として実行した方が高速な処理が可能になる。
【００６１】
まず、ステップＳ１のデータ入力段階では、複数ｍ個の単位データの入力が行われる。ここで入力されるｍ個の単位データは、図７に示す例における単位データＤ１〜Ｄ３に相当するものであり、たとえば、それぞれが１ファイルを構成するデータなど、ひとまとまりのデータとして把握されるデータになっている。ステップＳ１では、コンピュータや集積回路によって、合計ｍ個の単位データＤ１〜Ｄｍが取り込まれることになる。
【００６２】
続いて、ステップＳ２において、パラメータｉが１に設定される。このパラメータｉは、取り込んだ単位データの番号を示し、ｉ＝１〜ｍの範囲の値をとる。以下、ステップＳ３〜Ｓ６において、パラメータｉを１ずつ増加させながら、各単位データについて同じ処理が繰り返し実行される。
【００６３】
まず、ステップＳ３の一次誤り検出コード演算段階では、第ｉ番目の単位データＤｉについて、所定のアルゴリズムに基づく演算（たとえば、§１で述べた巡回冗長検査法に基づく除算演算）を行って一次誤り検出コードＣｉを求める処理が行われる。続くステップＳ４の誤り検出コード付き単位データ生成段階では、第ｉ番目の単位データＤｉに、ステップＳ３で求めた一次誤り検出コードＣｉを付加することにより、誤り検出コード付き単位データＤｉ＊を生成する処理、すなわち、Ｄｉ＊＝Ｄｉ＋Ｃｉなるビット列の合成演算が行われる（符号＋は、前後のデータのビット列を連結することを示している。以下同様）。
【００６４】
このステップＳ３およびＳ４の処理は、ステップＳ５およびＳ６を経て、パラメータｉを１ずつ増加させながら、ｉ＝ｍになるまで繰り返し実行される。結局、ステップＳ３では、複数ｍ個の単位データＤ１〜Ｄｍのそれぞれについて、個別に所定のアルゴリズムに基づく演算を行って一次誤り検出コードＣ１〜Ｃｍを求める作業が行われることになり、ステップＳ４では、複数ｍ個の単位データＤ１〜Ｄｍのそれぞれに、ステップＳ３で求めた一次誤り検出コードＣ１〜Ｃｍを付加することにより、複数ｍ個の誤り検出コード付き単位データＤ１＊〜Ｄｍ＊を生成する作業が行われることになる。たとえば、ｍ＝３の場合、図７に示すような３個の誤り検出コード付き単位データＤ１＊〜Ｄ３＊が生成される。
【００６５】
続いて、ステップＳ７の連結データ生成段階では、これら複数ｍ組の誤り検出コード付き単位データＤ１＊〜Ｄｍ＊を順に連結することにより、連結データＬを生成する処理が行われる。すなわち、Ｌ＝Ｄ１＊＋Ｄ２＊＋Ｄ３＊＋・・・＋Ｄｍ＊なる演算によって連結データＬが生成される。ｍ＝３の場合、図８の上段に示すように、３個の誤り検出コード付き単位データＤ１＊，Ｄ２＊，Ｄ３＊のビット列を順に連結することにより、連結データＬが生成される。
【００６６】
そして、ステップＳ８の二次誤り検出コード演算段階では、連結データＬについて、所定のアルゴリズムに基づく演算（たとえば、§１で述べた巡回冗長検査法に基づく除算演算）を行って二次誤り検出コードＥを求める処理が行われ、最後のステップＳ９の誤り検出コード付き連結データ生成段階では、得られた二次誤り検出コードＥを連結データＬに付加することにより、誤り検出コード付き連結データＬ＊が生成される。すなわち、Ｌ＊＝Ｌ＋Ｅなる演算によって、誤り検出コード付き連結データＬ＊が生成される（図８の下段参照）。
【００６７】
一方、図１０は、本発明に係る誤り検出コード付きデータに対する誤り検出方法の基本手順を示す流れ図である。この基本手順は、図９の流れ図に示す基本手順を前提として生成された誤り検出コード付き連結データＬ＊に対して、誤りの有無を検出する処理を行う手順であり、次のような各ステップによって構成されている。これらの各ステップも、汎用のコンピュータに専用のプログラムを組み込むことによってソフトウエアによる処理として実行することも可能であるが、実用上は、個々の処理を実行するための専用の集積回路を設け、ハードウエアによる処理として実行した方が高速な処理が可能になる。
【００６８】
まず、ステップＳ１１の二次誤り検出コード再演算段階では、検出対象となる誤り検出コード付き連結データＬ＊から連結データＬを抽出し、抽出した連結データＬに対して、図９のステップＳ８における二次誤り検出コード演算段階で行われた演算と同じアルゴリズムに基づく演算を行って二次誤り検出コードＥを求める処理が行われる。そして、ステップＳ１２の一致判定段階では、ステップＳ１１の再演算段階で得られた二次誤り検出コードＥと、検出対象となる誤り検出コード付き連結データＬ＊に含まれていた二次誤り検出コードＥと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定が行われる。
【００６９】
このように、図９に示す手順によって、複数ｍ個の単位データＤ１〜Ｄｍに対してそれぞれ一次誤り検出コードＣ１〜Ｃｍを付加して誤り検出コード付き単位データＤ１＊〜Ｄｍ＊を生成した後、これらを連結して得られる連結データＬ全体に対して二次誤り検出コードＥを付加して誤り検出コード付き連結データＬ＊を生成しておけば、当該データＬ＊に対して、保存、読出、送信、受信といった作業を行った場合に、図１０に示す手順によって、二次誤り検出コードＥの整合性を確認するだけの簡便な作業で、複数ｍ個の単位データ全体についての誤り検出を行うことが可能になる。
【００７０】
＜＜＜  §３．  巡回冗長検査法の利用に適した実施形態  ＞＞＞
前掲の§２では、本発明の基本概念および基本的な実施形態を、図９および図１０の流れ図を参照しながら説明した。ここで、図９のステップＳ３における一次誤り検出コード演算段階や、ステップＳ８における二次誤り検出コード演算段階では、所定のアルゴリズムに基づく演算を行って一次誤り検出コードＣｉや二次誤り検出コードＥを生成する処理が行われ、図１０のステップＳ１１における二次誤り検出コード再演算段階においても同様の演算が行われる。
【００７１】
これらの演算としては、一方向関数を作用させる一方向演算であれば、原理的には、どのような演算を採用してもかまわない。また、必ずしも一方向関数を用いた一方向演算に限定されるものではなく、データ量を圧縮することが可能な圧縮関数を用いた圧縮演算を採用してもかまわない。しかしながら、現在のところ、§１で述べたとおり、巡回冗長検査法に基づく除算演算が最も普及している。これは、前述したとおり、巡回冗長検査法に基づく除算演算のプロセスは、被除数の先頭側のビットから順にＸＯＲを求める演算を行うだけでよいので（図５参照）、システムにとっての演算負担は比較的軽く、単純な半導体集積回路による高速処理が可能になるというメリットを有しているためである。したがって、実用上は、本発明における誤り検出コードを生成する演算として、巡回冗長検査法に基づく除算演算を利用するのが最適である。そこで、以下、巡回冗長検査法の利用に適した本発明の実施形態を述べておく。
【００７２】
＜３−１．  問題の所在＞
ここでは、まず、§２で述べた基本的な実施形態において、巡回冗長検査法に基づく除算演算をそのまま適用して入れ子式に二重の誤り検出コードを生成した場合に生じる固有の問題を説明する。図１１は、巡回冗長検査法に基づく除算演算を本発明にそのまま適用した場合に、連結データＬについての二次誤り検出コードＥによる誤り検出が失敗する例を示すブロック図である。
【００７３】
いま、図９の流れ図に示す手順を実行することにより、図１１(a) に示すような誤り検出コード付き連結データＬ１＊が生成され、所定の記憶場所に保存されているものとしよう。この図１１(a) に示すデータＬ１＊は、図８の下段に示すデータＬ＊と同じものであり、もともとは、図７に示すような３組の単位データＤ１〜Ｄ３に基づいて、それぞれ一次誤り検出コードＣ１〜Ｃ３を付加して誤り検出コード付き単位データＤ１＊〜Ｄ３＊を生成し、これらを連結して得られる連結データＬに対して、更に二次誤り検出コードＥを付加したものである。
【００７４】
こうして保存されている誤り検出コード付き連結データＬ１＊を読み出して、これを別なシステムに送信した場合、受信側のシステムで図１０の流れ図に示す手順を実行すれば、誤りの検出が可能である。たとえば、連結データＬ１を構成するビット列の一部にデータ化けが生じていると、二次誤り検出コードＥの整合性が得られなくなり、ステップＳ１２において不一致が生じ、誤り有りとの判定がなされることになる。
【００７５】
ところが、巡回冗長検査法により誤り検出コードを生成すると、誤り検出コード付き単位データがそっくり入れ替わるエラーが生じた場合、誤り検出を行うことができない。たとえば、図１１(b) に示すデータＬ２＊は、図１１(a) に示す誤り検出コード付き単位データＤ１＊をデータＤ４＊に入れ替えたものである。すなわち、図１１(a) に示す連結データＬ１が３組のデータＤ１＊，Ｄ２＊，Ｄ３＊を連結したものであるのに対して、図１１(b) に示す連結データＬ２は、３組のデータＤ４＊，Ｄ２＊，Ｄ３＊を連結したものになっており、図に太線で示す部分のみが置換されている。
【００７６】
このようなデータの取り違えが生じると、本来であれば、二次誤り検出コードＥの整合性が失われるため、図１０に示す検出手順によって誤り有りとの判定がなされるはずである。ところが、一次誤り検出コードＣ１〜Ｃ３および二次誤り検出コードＥの生成に巡回冗長検査法を利用すると、その根源的な性質により、誤り検出を行うことができない。別言すれば、図１１(a) に示す連結データＬ１について生成した二次誤り検出コードＥと、図１１(b) に示す連結データＬ２について生成した二次誤り検出コードＥとは一致してしまうため、図１１(b) に示すデータＬ２＊について誤り検出を行うと、二次誤り検出コードＥに整合性が得られることになり、誤り無しの判定がなされてしまう。
【００７７】
その理由を、具体的なデータを例にとって説明しよう。図１２は、連結データＬについての二次誤り検出コードによる誤り検出が失敗する具体例を示す図である。この例の場合、連結データＬは、図１１(a) に示す連結データＬ１と同様に、３組のデータＤ１＊，Ｄ２＊，Ｄ３＊を連結したものである。ここでは、図示のとおり、データＤ１＊が、「１０００１１０１」なる８ビットからなる単位データＤ１と、「１０１０」なる４ビットからなる一次誤り検出コードＣ１とによって構成されているものとしよう（図４に示す例と同じ）。
【００７８】
同様に、データＤ２＊が、「ＸＸＸＸＸＸＸＸ」なる８ビットからなる単位データＤ２と、「ＸＸＸＸ」なる４ビットからなる一次誤り検出コードＣ２とによって構成され、データＤ３＊が、「ＸＸ・・・」なる８ビットからなる単位データＤ３およびこれに後続する４ビットからなる一次誤り検出コードＣ３とによって構成されているものとしよう。ここで、「Ｘ」は任意の１ビットを示している。
【００７９】
図１３は、図１２に示す連結データＬについて、二次誤り検出コードＥを求める具体的な除算アルゴリズムを示す図である。この図１３に示す除算演算においても、除数Ｋとして「１００１１」を用いており、その基本的な演算プロセスは、図５に示す除算演算とほぼ同じである。ただ、図５に示す例の場合、＜行１＞に記載する被除数として、対象データＤ「１０００１１０１」の末尾に、４つのゼロからなる付加ビットＺ「００００」を付加したデータを用いているが、図１３に示す例の場合、＜行１＞に記載する被除数として、図１２に示す連結データＬ（３組のデータＤ１＊，Ｄ２＊，Ｄ３＊を連結したもの）を構成するビット列の末尾に、４つのゼロからなる付加ビットＺ「００００」を付加したデータが用いられる（図１３には、これらのビット列のうちの先頭部分のみが示されている）。
【００８０】
§１で述べたとおり、巡回冗長検査法に基づく除算演算のプロセスでは、通常の算術的な除算プロセスとは異なり、上下に配置されたビット同士の排他的論理和演算（ＸＯＲ演算）が行われる。図１３に示す例の場合、まず、＜行２＞に示すように、除数「１００１１」を被除数の先頭桁に揃えるように配置し、上下のビット間でＸＯＲ演算を行い、その結果を＜行３＞に記載する。そして、被除数の演算に必要な桁（除数と同じになるように全５桁）を＜行３＞に降ろし、＜行４＞に示すように、除数「１００１１」を被除数の零でない先頭桁に揃えるように配置し、上下のビット間でＸＯＲ演算を行い、その結果を＜行５＞に記載する。
【００８１】
同様に、被除数の演算に必要な桁を＜行５＞に降ろし、＜行６＞に示すように、除数「１００１１」を被除数の零でない先頭桁に揃えるように配置し、上下のビット間でＸＯＲ演算を行い、その結果を＜行７＞に記載する。続いて、被除数の演算に必要な桁を＜行７＞に降ろし、＜行８＞に示すように、除数「１００１１」を被除数の零でない先頭桁に揃えるように配置し、上下のビット間でＸＯＲ演算を行い、その結果を＜行９＞に記載する。
【００８２】
すると、この段階で、＜行９＞におけるビット境界線Ｖの左側の桁は、すべてが零になっていることがわかる。そこで、次のプロセスでは、図示のとおり、単位データＤ２の先頭５ビット「ＸＸＸＸＸ」を＜行９＞に降ろし（先頭のＸが０でない場合の例）、＜行１０＞に示すように、除数「１００１１」を被除数の零でない先頭桁に揃えるように配置し、上下のビット間でＸＯＲ演算を行うことになる。これは、ビット境界線Ｖの右側の桁から新たな除算演算のプロセスが開始されることを意味する。
【００８３】
このように、ビット境界線Ｖの左側に関する演算（誤り検出コード付きデータＤ１＊を構成する各桁に関する演算）が完了した時点で、＜行９＞に示される演算結果が零になるのは、理論的には当然の結果である。すなわち、誤り検出コード付きデータＤ１＊は、そもそも元の単位データＤ１に誤り検出コードＣ１を付加したものであり、誤り検出コードＣ１は、元の単位データＤ１に対して、除数「１００１１」を用いて巡回冗長検査法に基づく除算演算を行うことにより得られた余りに相当する数値である。したがって、この余りに相当する誤り検出コードＣ１を元の単位データＤ１に付加したデータに対して、除数「１００１１」を用いて巡回冗長検査法に基づく除算演算を行えば、余りが零になるのは当然の結果である。別言すれば、図５に示す演算プロセスにおいて、被除数の下４桁を構成する付加ビットＺ「００００」を、余り「１０１０」に置換して除算演算を行えば、当該除算演算の余りが零になるのは当然である。
【００８４】
このように、図１３に示す演算プロセスにおいて、ビット境界線Ｖの左側のデータについての除算演算によって得られる余りは、当該データが誤り検出コード付きデータである限り、必ず零になる。したがって、図１３に示すデータＤ１＊の部分が、別な誤り検出コード付きデータＤ４＊に置き換わったとしても、ビット境界線Ｖの左側のデータについての除算演算によって得られる余りが零であることに変わりはない。
【００８５】
結局、図１１(a) に示す連結データＬ１について巡回冗長検査法に基づく除算演算のプロセスを実行すると、誤り検出コード付きデータＤ１＊，Ｄ２＊，Ｄ３＊についての除算演算がそれぞれ完了するたびに余りは０になり、最終的に得られる二次誤り検出コードＥの値も零になってしまう。同様に、図１１(b) に示す連結データＬ２について巡回冗長検査法に基づく除算演算のプロセスを実行すると、誤り検出コード付きデータＤ４＊，Ｄ２＊，Ｄ３＊についての除算演算がそれぞれ完了するたびに余りは０になり、最終的に得られる二次誤り検出コードＥの値も零になってしまう。その結果、３組のデータＤ１＊，Ｄ２＊，Ｄ３＊を連結して得られる連結データＬ１のうち、たとえば先頭部分のデータＤ１＊が別なデータＤ４＊に置き換わって連結データＬ２に化けてしまっていても、誤りの検出は行われないことになる。
【００８６】
要するに、複数ｍ組の一次誤り検出コード付き単位データＤ１＊〜Ｄｍ＊を連結して得られる連結データＬ全体に対して二次誤り検出コードＥを求める際に、巡回冗長検査法に基づく除算演算のプロセスをそのまま適用すると、得られる二次誤り検出コードＥは必ず零になってしまう。もちろん、その場合でも、いずれかの箇所にデータ化けが生じた場合には、通常、得られる二次誤り検出コードＥは零ではなくなるので、誤り有りとの判定を行うことは可能であるが、図１１に示す例のように、誤り検出コード付き単位データをそっくり取り違えてしまうような誤りが発生した場合は、当該誤りの検出はできないことになる。
【００８７】
たとえば、複数ｍ組の一次誤り検出コード付き単位データＤ１＊〜Ｄｍ＊を、それぞれ独立したファイルとして保存しておき、これらファイルのデータを逐次連結しながら二次誤り検出コードＥを求める演算を行い、得られた二次誤り検出コードＥを別個に保存しておき、これらのデータを送信する際に、再び個々のファイルを連結し、更に二次誤り検出コードＥを付加する処理を行うような形態を採る場合、送信時にファイルの取り違えが生じても、受信側では、これを誤りとして検出することができないことになる。
【００８８】
このように、本発明に係る誤り検出コード付きデータの生成方法および誤り検出方法に、巡回冗長検査法に基づく除算演算をそのまま利用すると、二次誤り検出コードＥによる誤り検出が失敗する可能性がある。そこで、以下、このような問題の解決法を述べておく。
【００８９】
＜３−２．  異なる生成多項式を用いる解決法＞
既に述べたとおり、図９に示す手順における一次誤り検出コード演算段階（ステップＳ３）で一次誤り検出コードを求めるアルゴリズムおよび二次誤り検出コード演算段階（ステップＳ８）で二次誤り検出コードを求めるアルゴリズムとして、巡回冗長検査法に基づく所定の生成多項式を用いた除算アルゴリズムをそのまま適用し、当該除算アルゴリズムに基づく除算演算で得られた余りを誤り検出コードＥとして用いると、得られる誤り検出コードＥは必ず零になる。
【００９０】
この場合、図１０に示す誤りの有無を検出する手順では、まず、検出対象となる誤り検出コード付き連結データＬ＊から連結データＬを抽出し、抽出した連結データＬに対して、二次誤り検出コード演算段階（ステップＳ８）で行われた演算と同じ巡回冗長検査法に基づく演算を行って二次誤り検出コードＥを求める二次誤り検出コード再演算段階（ステップＳ１１）を行い、更に、この二次誤り検出コード再演算段階によって得られた二次誤り検出コードＥと、検出対象となる誤り検出コード付き連結データＬ＊に含まれていた二次誤り検出コードＥと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定を行う一致判定段階（ステップＳ１２）を行うことになる。
【００９１】
しかしながら、前述したように、得られる二次誤り検出コードＥは必ず零になってしまうため、誤り検出コード付きデータをそっくり取り違える誤りが生じても、誤りの検出を行うことはできない。
【００９２】
このような問題に対処するための第１の解決法は、一次誤り検出コード演算段階（ステップＳ３）で行う除算演算と、二次誤り検出コード演算段階（ステップＳ８）で行う除算演算とで、互いに異なる生成多項式に対応する除数を用いた演算を行うようにし、二次誤り検出コード再演算段階（ステップＳ１１）では、検出対象となる誤り検出コード付き連結データＬ＊から連結データＬを抽出し、抽出した連結データＬに対して、二次誤り検出コード演算段階（ステップＳ８）で行われた演算と同じ巡回冗長検査法に基づく演算を行って二次誤り検出コードＥを求めるようにし、一致判定段階（ステップＳ１２）では、二次誤り検出コード再演算段階（ステップＳ１１）によって得られた二次誤り検出コードＥと、検出対象となる誤り検出コード付き連結データＬ＊に含まれていた二次誤り検出コードＥと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定を行うようにすればよい。
【００９３】
§１において図６を参照して説明したとおり、巡回冗長検査法は、数学的には、式(1) に示すように、ａ（ｘ）÷ｆ（ｘ）＝ｑ（ｘ）・・・ｒ（ｘ）なる多項式の除算に基づく演算を行うものであり、これまでの例で用いられている除数Ｋ＝１００１１は、式(3) ，(4) に示すように、生成多項式「ｆ（ｘ）＝ｘ４＋ｘ＋１」の係数「１００１１」に相当する。もちろん、巡回冗長検査法に用いる生成多項式は、上記多項式のみでなく、他にも様々な生成多項式が利用されている。
【００９４】
図１４は、現在、巡回冗長検査法の標準規格で定められているいくつかの生成多項式の具体例を示す図である。たとえば、図１４(a) には、「ＣＲＣ−４−ＩＴＵ」なる規格として定められている「ｆ１（ｘ）＝ｘ４＋ｘ＋１」なる生成多項式が示されている。当該生成多項式は、これまで述べてきた各実施例で利用されている多項式であり、５ビットの除数Ｋ＝１００１１を用いた除算演算を行い、４ビットの余りを誤り検出コードＣとして生成することができる。
【００９５】
一方、図１４(b) に示す「ＣＲＣ−５−ＩＴＵ」なる規格として定められている生成多項式「ｆ２（ｘ）＝ｘ５＋x４＋ｘ２＋１」は、６ビットの除数Ｋ＝１１０１０１を用いた除算演算を行い、５ビットの余りを誤り検出コードＣとして生成する多項式であり、図１４(c) に示す「ＣＲＣ−１６−ＣＣＩＴＴ」なる規格として定められている生成多項式「ｆ３（ｘ）＝ｘ１６＋x１２＋ｘ５＋１」は、１７ビットの除数Ｋ＝１０００１００００００１００００１を用いた除算演算を行い、１６ビットの余りを誤り検出コードＣとして生成する多項式である。
【００９６】
このように、予め２以上の生成多項式を用意しておき、一次誤り検出コードＣを求める除算演算と、二次誤り検出コードＥを求める除算演算とで、それぞれ異なる生成多項式に対応する除数を用いた演算を行うようにすれば、上述した問題を解決することができる。
【００９７】
たとえば、図１３に示す例の場合、一次誤り検出コードＣ１は、図１４(a) に示す「ｆ１（ｘ）＝ｘ４＋ｘ＋１」なる生成多項式を用いて、除数Ｋ＝１００１１を用いた除算演算を行うことにより得られたものである。このため、二次誤り検出コードＥを生成する際にも、同じ生成多項式ｆ１（ｘ）に基づく除数Ｋ＝１００１１を用いた演算を行うと、図示のとおり、ビット境界線Ｖの左側が必ず零になる現象が起こり、上述の問題が生じることになる。
【００９８】
ところが、二次誤り検出コードＥを生成する際に、たとえば、図１４(b) に示す別な生成多項式ｆ２（ｘ）に基づく除数Ｋ＝１１０１０１を用いた演算を行えば、図１３における各偶数行に記載された除数Ｋは、「１００１１」から「１１０１０１」に変更されるため、ビット境界線Ｖの左側が必ず零になる現象は生じない。よって、上述した問題を解決することができる。すなわち、図１１に示すように、誤り検出コード付きデータをそっくり取り違える誤りが生じても、誤りの検出を行うことが可能になり、より高い精度で誤り検出を行うことが可能になる。
【００９９】
もちろん、この場合、二次誤り検出コードＥについての整合性を確認する誤り検出の手順では、除数Ｋ＝１１０１０１を用いた除算演算を行い、一次誤り検出コードＣについての整合性を確認する誤り検出の手順では、除数Ｋ＝１００１１を用いた除算演算を行うことになる。したがって、図９に示す誤り検出コード付きデータの生成手順においても、図１０に示す検出手順においても、２通りの除算演算の実施環境を用意しておく必要がある。このため、これらの処理手順を半導体集積回路で実行する形態を採る場合、ハードウエア構成が複雑になることは否めない。
【０１００】
＜３−３．  連結データを組み替える解決法＞
上述したように、一次誤り検出コードＣを求める除算演算と、二次誤り検出コードＥを求める除算演算とで、それぞれ異なる生成多項式に対応する除数を用いた演算を行う、という第１の解決法を採用すると、２通りの除算演算の実行環境を用意しておく必要があり、半導体集積回路を利用した演算を前提とすると、ハードウエア構成が複雑にならざるを得ない。したがって、実用上は、一次誤り検出コードＣを求める除算演算と、二次誤り検出コードＥを求める除算演算とで、同一の生成多項式に対応する除数を用いた演算を行うのが好ましい。
【０１０１】
ここで述べる第２の解決法は、同一の生成多項式に対応する除数を用いた演算を行いつつ、二次誤り検出コード演算段階（ステップＳ８）で、連結データＬに対して組み替えを行い、組み替え後の連結データＬ′について、除算演算を行って二次誤り検出コードＥを求めるようにするものである。
【０１０２】
この場合、誤りの有無を検出する処理を行う際には、二次誤り検出コード再演算段階（ステップＳ１１）において、検出対象となる誤り検出コード付き連結データＬ＊から連結データＬを抽出し、抽出した連結データＬに対して、二次誤り検出コード演算段階（ステップＳ８）で行われた組み替えと同じ組み替えを行い、組み替え後の連結データＬ′に対して、二次誤り検出コード演算段階（ステップＳ８）で行われた演算と同じ巡回冗長検査法に基づく演算を行って二次誤り検出コードＥを求めるようにすればよい。
【０１０３】
二次誤り検出コード演算段階（ステップＳ８）で行う連結データＬに対する組替処理としては、たとえば、連結データＬを、所定の組替位置Ｐで前半部分と後半部分とに切り分け、前半部分と後半部分とを入れ替える処理を行えばよい。
【０１０４】
たとえば、図１５に示すような連結データＬについての組替処理を考えてみよう。この連結データＬは、図８の上段に示すものと同じデータであり、３組の誤り検出コード付きデータＤ１＊，Ｄ２＊，Ｄ３＊を順に連結したものである。§２で述べた基本的な実施形態の場合、図示のとおり、二次誤り検出コード演算段階（ステップＳ８）において、この連結データＬの先頭ビットから順に、図１３に示すような除算演算を行い、得られた余りを二次誤り検出コードＥとして末尾に付加することにより、誤り検出コード付き連結データＬ＊を生成することになる。
【０１０５】
これに対して、ここで述べる方法を採用した場合、二次誤り検出コード演算段階（ステップＳ８）において、まず、図１６に示すように、連結データＬに対する組替処理が行われる。すなわち、図１６上段に示すように、連結データＬの所定位置（所定のビットと次のビットとの境界位置）を組替位置Ｐに設定し、この組替位置Ｐを境界として、連結データＬを前半部分Ｌ（ａ）と後半部分Ｌ（ｂ）とに切り分け、図１６下段に示すように、前半部分Ｌ（ａ）と後半部分Ｌ（ｂ）とを入れ替える処理を行って組み替え後の連結データＬ′を生成し、この組み替え後の連結データＬ′について巡回冗長検査法に基づく除算演算を行って二次誤り検出コードＥを求めるようにする。
【０１０６】
要するに、二次誤り検出コード演算段階（ステップＳ８）では、連結データＬの先頭ビットから順に除算演算を行う代わりに、組み替え後の連結データＬ′の先頭ビットから順に除算演算が行われることになる。図示の例の場合、組替位置Ｐは、単位データＤ２内の任意の位置に設定されており、単位データＤ２のうち組替位置Ｐよりも前の部分を前半部分Ｄ２１と呼び、単位データＤ２のうち組替位置Ｐよりも後の部分を後半部分Ｄ２２と呼べば、組み替え後の連結データＬ′は、図示のとおり、Ｄ２２、Ｃ２，Ｄ３，Ｃ３，Ｄ１，Ｃ１，Ｄ２１の順に各部分を並べたものになり、この順番で除算演算が行われることになる。実際には、除算演算の開始時に、ポインタを連結データＬの先頭ではなく、組替位置Ｐにセットすればよい。
【０１０７】
もちろん、この除算演算で最終的に得られた余りを、二次誤り検出コードＥとして元の連結データＬの末尾に付加することにより、誤り検出コード付き連結データＬ＊が生成される。
【０１０８】
このように、連結データＬについての組替処理を行った後に除算演算を行うようにすれば、一次誤り検出コードＣを求める除算演算と、二次誤り検出コードＥを求める除算演算とで、同一の生成多項式に対応する除数を用いた演算を行ったとしても、得られる二次誤り検出コードＥが必ず零になる現象は生じなくなる。その理由は、図１３に示す具体的な除算プロセスにおいて、＜行１＞の先頭のｋビットを、行の右側のＣ３のうしろに移動させた場合を考えれば、容易に理解できよう。この場合、＜行２＞に記載された除数「１００１１」の先頭位置は、ｋビットだけ右にシフトすることになるので、＜行９＞においてビット境界線Ｖの左側が必ず零になる現象は生じない。
【０１０９】
ただ、図１６上段に示す組替位置Ｐは、誤り検出コード付き単位データＤ１＊，Ｄ２＊，Ｄ３＊の境界位置ではない所定位置に設定する必要がある。組替位置Ｐを境界位置に設定してしまうと、組替処理は、図１１に示す例のように、誤り検出コード付き単位データをそっくり入れ替える処理と同等になり、組み替えの効果が得られなくなる。したがって、実用上は、個々の誤り検出コード付き単位データＤ１＊，Ｄ２＊，Ｄ３＊を連結して連結データＬを生成する際に、連結位置を記録しておき、組替位置Ｐが当該連結位置に重ならないように調整する方法を採るのが好ましい。
【０１１０】
なお、誤りの有無を検出するための二次誤り検出コード再演算段階（ステップＳ１１）では、二次誤り検出コード演算段階（ステップＳ８）で行われた組み替えと同じ組み替えを行う必要があるので、組替位置Ｐがどこであるかを認識する必要がある。そこで、実用上は、たとえば、二次誤り検出コードＥの末尾に、この組替位置Ｐを示す情報を付加しておくようにするのが好ましい。
【０１１１】
このように、連結データＬを組み替えて連結データＬ′を生成し、この組み替え後の連結データＬ′について巡回冗長検査法に基づく除算演算を行って二次誤り検出コードＥを求めるようにすれば、二次誤り検出コードＥが必ず零になる現象は生じなくなるので、図１１に示すように、誤り検出コード付きデータをそっくり取り違える誤りが生じても、誤りの検出を行うことが可能になり、より高い精度で誤り検出を行うことが可能になる。
【０１１２】
図１６では、連結データＬに対する組替処理の一例として、連結データＬを所定の組替位置Ｐで前半部分と後半部分とに切り分け、両者を入れ替えることにより、組み替え後の連結データＬ′を作成する例を示したが、もちろん、連結データＬに対する組替処理は、このような方法に限定されるものではない。
【０１１３】
図１７は、連結データＬに対する組替処理の別な一例を示すブロック図である。ここに示す例では、二次誤り検出コード演算段階（ステップＳ８）において、連結データＬを、所定の方法でｎ分割（但し、ｎ≧３）して、ｎ個の分割データを生成し、この分割データを所定の方法で並び替えることにより、連結データＬに対する組み替えが行われる。
【０１１４】
具体的には、図示の例の場合、予め所定の分割ビット長ξを定めておき、連結データＬの先頭から、この分割ビット長ξごとにデータを分割してゆき、合計５個の分割データＬ（ａ）〜Ｌ（ｅ）を生成し、これらを逆順に並び替えることにより、組み替え後の連結データＬ′が生成されている。すなわち、連結データＬは、分割データを、Ｌ（ａ），Ｌ（ｂ），Ｌ（ｃ），Ｌ（ｄ），Ｌ（ｅ）の順に並べたものであるのに対して、組み替え後の連結データＬ′は、分割データを、Ｌ（ｅ），Ｌ（ｄ），Ｌ（ｃ），Ｌ（ｂ），Ｌ（ａ）の順に並べたものになっている。ここで、分割データＬ（ａ），Ｌ（ｂ），Ｌ（ｃ），Ｌ（ｄ）のデータ長は、いずれも所定の分割ビット長ξになり、分割データＬ（ｅ）のデータ長は、余りの端数に相当する長さになる。
【０１１５】
もちろん、誤りの有無を検出するための二次誤り検出コード再演算段階（ステップＳ１１）では、当該組替処理と同じ組み替えを行う必要があるので、実用上は、たとえば、二次誤り検出コードＥの末尾に、分割ビット長ξや並べ替え方法に関する情報を付加しておくようにするのが好ましい。
【０１１６】
図１８は、連結データＬに対する組替処理の更に別な一例を示すブロック図である。ここに示す例では、二次誤り検出コード演算段階（ステップＳ８）において、連結データＬを構成する個々の誤り検出コード付き単位データを、それぞれ所定位置で前半部分と後半部分とに切り分け、個々の誤り検出コード付き単位データごとに、前半部分と後半部分とを入れ替えることにより、連結データＬに対する組み替えが行われる。
【０１１７】
具体的には、図示の例の場合、３組の誤り検出コード付き単位データＤ１＊，Ｄ２＊，Ｄ３＊が、それぞれ所定位置で前半部分と後半部分とに切り分けられている。切り分けの位置は、たとえば、先頭からｋビット目のように定めておいてもよいし、全長の１／３の位置のように定めておいてもよい。その結果、データＤ１＊は、前半部分Ｄ１ａと後半部分Ｄ１ｂとに切り分けられ、データＤ２＊は、前半部分Ｄ２ａと後半部分Ｄ２ｂとに切り分けられ、データＤ３＊は、前半部分Ｄ３ａと後半部分Ｄ３ｂとに切り分けられる。
【０１１８】
そして、個々のデータＤ１＊，Ｄ２＊，Ｄ３＊ごとに、それぞれ前半部分と後半部分とを入れ替えることにより、組み替え後の連結データＬ′が生成される。結局、連結データＬ′は、個々の部分データを、Ｄ１ｂ，Ｄ１ａ，Ｄ２ｂ，Ｄ２ａ，Ｄ３ｂ，Ｄ３ａの順に並び替えたものになっている。
【０１１９】
この場合も、誤りの有無を検出するための二次誤り検出コード再演算段階（ステップＳ１１）では、当該組替処理と同じ組み替えを行う必要があるので、実用上は、たとえば、二次誤り検出コードＥの末尾に、分割方法や並替方法に関する情報を付加しておくようにするのが好ましい。
【０１２０】
以上、連結データＬに対する具体的な組替方法をいくつか述べたが、もちろん、組替方法としては、この他にも種々の方法を採用することが可能である。なお、採用する組替方法によっては、必ずしも目的とする組替処理の効果（すなわち、図１１に示すように、誤り検出コード付きデータをそっくり取り違える誤りが生じた場合にも、誤りの検出が可能になる効果）が得られないケースもあるが、本発明を実施する上で、実用上の問題が生じるわけではない。そもそも誤り検出コードの整合性を確認して誤り検出を行う手法自体、１００％の精度で誤り検出が可能になるものではない。
【０１２１】
たとえば、通信経路上のノイズの影響でいくつかのビットがデータ化けを生じたとしても、当該データ化け後のデータにおいても、たまたま誤り検出コードの整合性が確保されてしまう可能性もある。実際、４ビットの誤り検出コードを用いた場合は、でたらめなデータであっても１／１６の確率で整合性が確認できることになる。したがって、連結データＬに対する組替方法としては、必ずしも上記組替処理の効果が１００％得られる方法を採用する必要はない。
【０１２２】
＜３−４．  整合性を確認する誤り検出手順の別法＞
最後に、巡回冗長検査法を採用した場合に有効な誤り検出手順の別法を述べておく。図２に基本原理として示したように、誤り検出コードを用いた誤り検出の手法は、基本的には、対象データＤから新たに生成した誤り検出コードＣと、もともと付加されていた誤り検出コードＣと、が一致するか否かを判定することによって行われる。したがって、図１０の一致判定段階（ステップＳ１２）においても、二次誤り検出コード再演算段階（ステップＳ１１）によって得られた二次誤り検出コードＥと、検出対象となる誤り検出コード付き連結データＬ＊に含まれていた二次誤り検出コードＥと、が一致するか否かを判定し、両者が一致した場合には誤り無し、両者が一致しなかった場合には誤り有り、との判定を行うことになる。
【０１２３】
ただ、巡回冗長検査法を採用した場合、誤り検出コードの一致判定を行う代わりに、誤り検出コード付きデータを被除数とした除算演算の余りが零になるか否かを判定することにより、整合性の確認を行うことも可能である。たとえば、図１３に示す例において、＜行１＞に示すように、誤り検出コード付き単位データＤ１＊「１０００１１０１１０１０」を被除数として、除数「１００１１」を用いた除算演算を行うと、＜行９＞に結果が示されているとおり、余りは零になる。これは、そもそも誤り検出コードＣ１が、単位データＤ１を除数「１００１１」で除した余りに対応する値として求められているので、予め当該余りを付加した値を被除数とした除算演算を行えば、余りが零になるのは当然のことと言える。
【０１２４】
そこで、前掲の§３−１で述べた「異なる生成多項式を用いる解決法」を採用し、図１０の検出手順で誤りの有無を検出する場合には、二次誤り検出コード再演算段階（ステップＳ１１）において、検出対象となる誤り検出コード付き連結データＬ＊全体に対して（すなわち、二次誤り検出コードＥを含む全桁に対して）、二次誤り検出コード演算段階（ステップＳ８）で行われた演算と同じ巡回冗長検査法に基づく生成多項式を用いた除算アルゴリズムに基づく演算を行って余りを求めるようにし、一致判定段階（ステップＳ１２）において、得られた余りが零であった場合は誤り無し、零でなかった場合は誤り有り、との判定を行うようにしてもよい。
【０１２５】
また、前掲の§３−２で述べた「連結データを組み替える解決法」を採用し、図１０の検出手順で誤りの有無を検出する場合には、二次誤り検出コード再演算段階（ステップＳ１１）において、検出対象となる誤り検出コード付き連結データＬ＊から連結データＬを抽出し、抽出した連結データＬに対して、二次誤り検出コード演算段階（ステップＳ８）で行われた組み替えと同じ組み替えを行い、組み替え後の連結データＬ′に、検出対象となる誤り検出コード付き連結データＬ＊に含まれていた二次誤り検出コードＥを付加し、得られたデータに対して、二次誤り検出コード演算段階（ステップＳ８）で行われた演算と同じ巡回冗長検査法に基づく演算を行って余りを求めるようにし、一致判定段階（ステップＳ１２）において、得られた余りが零であった場合は誤り無し、零でなかった場合は誤り有り、との判定を行うようにしてもよい。
【符号の説明】
【０１２６】
ａ（ｘ）：対象データに対応する多項式
Ｃ：誤り検出コード（ＣＲＣ）
Ｃ１〜Ｃ４：（一次）誤り検出コード（ＣＲＣ）
Ｄ：対象データ
Ｄ１〜Ｄ４：対象データ（単位データ）
Ｄ＊：誤り検出コード付きデータ
Ｄ１＊〜Ｄ４＊：誤り検出コード付き単位データ
Ｄ２１：単位データＤ２の前半部分
Ｄ２２：単位データＤ２の後半部分
Ｄ１ａ：誤り検出コード付き単位データＤ１＊の前半部分
Ｄ１ｂ：誤り検出コード付き単位データＤ１＊の後半部分
Ｄ２ａ：誤り検出コード付き単位データＤ２＊の前半部分
Ｄ２ｂ：誤り検出コード付き単位データＤ２＊の後半部分
Ｄ３ａ：誤り検出コード付き単位データＤ３＊の前半部分
Ｄ３ｂ：誤り検出コード付き単位データＤ３＊の後半部分
Ｅ：二次誤り検出コード
ｆ（ｘ）：生成多項式
ｆ１（ｘ）〜ｆ３（ｘ）：生成多項式
Ｇ：グループデータ
ｉ：単位データの番号
Ｋ：生成多項式に対応する除数
Ｌ：連結データ
Ｌ′：組み替え後の連結データ
Ｌ１，Ｌ２：連結データ
Ｌ＊：誤り検出コード付き連結データ
Ｌ１＊，Ｌ２＊：誤り検出コード付き連結データ
Ｌ（ａ）〜Ｌ（ｅ）：連結データの個々の部分
ｍ：単位データの総数
Ｐ：組替位置
ｑ（ｘ）：商に対応する多項式
ｒ（ｘ）：余りに対応する多項式
Ｓ１〜Ｓ１２：
Ｖ：ビット境界線
Ｘ：任意のビット
ｘ：多項式の変数
Ｚ：ゼロの付加ビット
ξ：分割ビット長
【図１】
2015135647.tif 000003
【図２】
2015135647.tif 000004
【図３】
2015135647.tif 000005
【図４】
2015135647.tif 000006
【図５】
2015135647.tif 000007
【図６】
2015135647.tif 000008
【図７】
2015135647.tif 000009
【図８】
2015135647.tif 000010
【図９】
2015135647.tif 000011
【図１０】
2015135647.tif 000012
【図１１】
2015135647.tif 000013
【図１２】
2015135647.tif 000014
【図１３】
2015135647.tif 000015
【図１４】
2015135647.tif 000016
【図１５】
2015135647.tif 000017
【図１６】
2015135647.tif 000018
【図１７】
2015135647.tif 000019
【図１８】
2015135647.tif 000020