JP6875661B2 - 誤り検出用冗長ビットの生成方法および装置 - Google Patents

Description

本発明は、ディジタルデータに含まれるビット誤りを検出するための冗長ビットの生成およびそれを用いた誤り検出技術に関する。

ディジタルデータ通信システムおよび記憶システムの運用では、様々な要因によって生じ得るビット誤りへの対策が施されており、なかでも最も一般的な技術として、巡回冗長検査（Cyclic Redundancy Check；ＣＲＣ）によるビット誤り検出方法が良く知られている。ＣＲＣは、ディジタルデータを予め定められた一定のビット長(ｋ ビット)のブロックに区切り、ブロック毎に予め定められたＣＲＣ多項式を用いてＣＲＣ多項式の次数ｒと同数の冗長ビットを付加することで、ビット誤りの検出を可能にする技術である。

周知のように、既存の符号器は、情報ビットを順次入力し、多項式除算回路を用いて冗長ビットを生成して情報ビットに付加する。このような符号器において、ＣＲＣ多項式をｇ（ｘ）＝ｘ^ｒ＋ｇ_ｒ−１ｘ^ｒ−１＋・・・＋ｇ_１ｘ＋１とすれば、その係数ｇ_ｒ−１、・・・ｇ_１によって規定される係数器は０あるいは１を示す開閉スイッチにより構成される。これらの係数（各スイッチの開閉状態）は処理の途中で変化することはなく固定されている。

ビット誤りの検出を目的とした上記ＣＲＣ技術は、ビット誤りの訂正を目的とした誤り訂正技術と併用されることが多い。誤り訂正技術は、データ内に生じたビット誤りを訂正する技術であるが、まれに訂正に失敗し、本来のデータとは異なるデータに訂正する場合がある。そこで、ＣＲＣ技術を併用することによって、訂正結果に誤りが生じても、それを検出することが可能になる。また、一般に誤り訂正処理には多くの演算が必要になるが、ＣＲＣ技術を併用すれば平均的に演算量を削減する効果がある事も知られている。

誤り訂正技術とＣＲＣ技術の併用によって特に大きな効果が見込まれる例として、Ｐｏｌａｒ符号化技術とＣＲＣとの組合せが良く知られている（非特許文献１）。Ｐｏｌａｒ符号化技術による一般的な誤り訂正処理では、訂正処理の結果が必ずしも一つとは限らず、予め定められた数の訂正結果の候補を導出する。そこで、複数の候補の中から正しい訂正結果を効率的に見つける方法としてＣＲＣ技術を活用することができる。ＣＲＣによって誤りが検出されなかった候補が正しい訂正結果と判定されることになる。

また、誤り検出方法の一例として、特許文献１に、複数ブロックで構成された伝送フレームの先頭から各ブロックまでのデータを有効範囲として冗長ビットを生成し、それを各ブロックに付加する方法が開示されている。

特開平６−０２１９２０号公報

IEEE Transactions on Information Theory, vol.61, no.5, pp.2213-2226, May 2015

上述したＣＲＣ技術では、情報部分の全てを復号器に入力した後で初めて誤りの検出が可能になるために、誤りの有無にかかわらず検出処理に一定の時間を必要とする。一般に、誤りが検出されると、それに対して再送要求等の対処が必要となるので、もし誤りが存在するのであれば、できるだけ早い時点で誤り検出の通知を行うことがシステム構成上望ましい。

上述した特許文献１では、伝送フレームの先頭で行った符号器の初期設定を維持することで、当該先頭から各ブロックまでのＣＲＣを付加することができるが、符号器および復号器の装置構成には一切言及されていない。したがって、特許文献１では、上述した既存の多項式除算回路を用いた符号器および復号器が用いられていると考えられる。言い換えれば、特許文献１に開示された方法では、既存の多項式除算回路を設けた符号器を利用するために、一定の長さのブロック毎に、当該ブロックまでのデータに基づいたＣＲＣを付加することしかできない。

そこで、本発明の目的は、検出精度の低下および計算量の大幅な増大を回避でき、情報ビットの一部分を用いた誤り検出可能な冗長ビットを生成することができる、新たな方法および装置を提供することにある。

本発明による冗長ビット生成装置は、巡回冗長検査（ＣＲＣ）多項式により前記情報ビットから所定数の冗長ビットを生成する冗長ビット演算手段と、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記所定数の冗長ビットを前記情報ビット内に分散配置するビット入れ替え手段と、を有することを特徴とする。
本発明による冗長ビット生成装置は、前記情報ビットを入力する、巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ手段と、前記開閉スイッチ手段の各々の出力を個別に累積加算して前記冗長ビットを算出する累積加算手段と、前記入力した情報ビットおよび前記累積加算手段のそれぞれが算出した冗長ビットのいずれかを選択して、前記情報ビットに前記冗長ビットを追加したデータ列を生成する選択手段と、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ手段および前記選択手段を制御する制御手段と、を有することを特徴とする。
本発明による冗長ビット生成方法は、ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する方法であって、冗長ビット演算手段が巡回冗長検査（ＣＲＣ）多項式により前記情報ビットから所定数の冗長ビットを生成し、ビット入れ替え手段が、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記所定数の冗長ビットを前記情報ビット内に分散配置する、ことを特徴とする。
本発明による冗長ビット生成方法は、ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する方法であって、巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ手段が前記情報ビットを入力し、各開閉スイッチ手段を開閉制御する第１制御信号に従って当該情報ビットを通過あるいは遮断し、累積加算手段が、前記開閉スイッチ手段の各々の出力を個別に累積加算して前記冗長ビットを算出し、選択手段が、第２制御信号に従って、前記入力した情報ビットおよび前記累積加算手段のそれぞれが算出した冗長ビットのいずれかを選択し、前記情報ビットに前記冗長ビットを追加したデータ列を生成し、制御手段が、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ手段および前記選択手段を制御する前記第１制御信号および前記第２制御信号を出力する、ことを特徴とする。
本発明による誤り検出装置は、ブロック化された情報ビットに追加された誤り検出を可能にする冗長ビットを用いて誤りを検出する装置であって、受信データの情報ビットを入力する、巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ手段と、前記開閉スイッチ手段の各々の出力を個別に累積加算して前記冗長ビットを算出する累積加算手段と、前記受信データの冗長ビットおよび前記累積加算手段のそれ
ぞれが算出した冗長ビットのいずれかを選択する選択手段と、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ手段の各々の開閉制御および前記選択手段の選択制御を実行する制御手段と、前記受信データの冗長ビットと前記算出した冗長ビットとを比較して誤りの有無を判定する判定手段と、を有することを特徴とする。
本発明によるプログラムは、ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する装置としてコンピュータを機能させるプログラムであって、巡回冗長検査（ＣＲＣ）多項式により前記情報ビットから所定数の冗長ビットを生成する冗長ビット演算機能と、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記所定数の冗長ビットを前記情報ビット内に分散配置するビット入れ替え機能と、を前記コンピュータに実現することを特徴とする。
本発明によるプログラムは、ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する装置としてコンピュータを機能させるプログラムであって、前記情報ビットを入力する、巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ機能と、前記開閉スイッチ機能の各々の出力を個別に累積加算して前記冗長ビットを算出する累積加算機能と、前記入力した情報ビットおよび前記累積加算機能のそれぞれが算出した冗長ビットのいずれかを選択して、前記情報ビットに前記冗長ビットを追加したデータ列を生成する選択機能と、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ機能および前記選択機能を制御する機能と、を前記コンピュータに実現することを特徴とする。
本発明によるプログラムは、ブロック化された情報ビットに追加された誤り検出を可能にする冗長ビットを用いて誤りを検出する装置としてコンピュータを機能させるプログラムであって、受信データの情報ビットを入力する、巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ機能と、前記開閉スイッチ機能の各々の出力を個別に累積加算して前記冗長ビットを算出する累積加算機能と、前記受信データの冗長ビットおよび前記累積加算機能のそれぞれが算出した冗長ビットのいずれかを選択する選択機能と、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ機能の各々の開閉制御および前記選択機能の選択制御を実行する機能と、前記受信データの冗長ビットと前記算出した冗長ビットとを比較して誤りの有無を判定する機能と、を前記コンピュータに実現することを特徴とする。

本発明によれば、検出精度の低下および計算量の大幅な増大を回避でき、情報ビットの一部分を用いた誤り検出可能な冗長ビットを生成することができる。

図１は、本発明の一実施形態により生成されるデータフレームの一例を示すフレーム構成図である。 図２は、本発明の第一実施例による冗長ビット生成方法の概略を説明するための機能構成図である。 図３は、第一実施例による冗長ビット生成装置の一例を示すブロック図である。 図４は、第一実施例による冗長ビット生成装置における置換パターンの生成方法の一例を示すフローチャートである。 図５は、図４における置換パターン生成手順の一例を示すフローチャートである。 図６は、本発明の第二実施例による冗長ビット生成装置の機能的構成を示すブロック図である。 図７は、第二実施例による冗長ビット生成方法を説明するためのタイムチャートである。 図８は、第二実施例による冗長ビット生成方法における長さｎのビット列ｈと置換パターンπの生成手順の一例を示すフローチャートである。 図９は、本発明の第二実施例による冗長ビット生成装置を備えた誤り検出装置の機能的構成を示すブロック図である。 図１０は、上記実施例による冗長ビット生成装置の機能をコンピュータプログラムにより実現する情報処理装置の概略的構成を示すブロック図である。 図１１は、本発明による冗長ビット生成装置を適用したＰｏｌａｒ符号化装置の一例を示すブロック図である。 図１２は本発明による誤り検出装置を用いたＰｏｌａｒ復号装置の一例を示すブロック図である。

＜実施形態の概要＞
本発明の実施形態によれば、巡回冗長検査（ＣＲＣ）多項式から算出された置換パターンを用いて冗長ビットを情報ビット内に分散配置することができる。これにより、冗長ビットが伝送データフレームの途中に配置され、全ての情報ビット部分を入力することなく誤りの検出が可能となり、平均的に少ない時間で誤りの検出を行うことができる。また、伝送データフレームのビット位置を入れ替えることで、ランダムエラーに対する検出精度は既存のＣＲＣ技術と同様であり、検出精度の劣化は伴わない。

以下、図面を参照しながら、本発明の実施形態および実施例について詳細に説明する。ただし、以下の実施の形態に記載されている構成要素は単なる例示であって、本発明の技術範囲をそれらのみに限定する趣旨のものではない。

１．実施形態
本発明の一実施形態による符号器は、ＣＲＣ多項式から得られた置換パターンを用いることで、所定長の情報ビット列の中に複数の冗長ビットが分散配置された伝送フレームを生成することができる。各冗長ビットは、同じＣＲＣ多項式を用いて、当該冗長ビットより前のビット列、すなわち先行する情報ビット列、あるいは先行する情報ビット列および冗長ビット、から生成される。以下、図１を参照しながら、本実施形態による符号化により生成されるデータフレームの一例を詳細に説明する。

図１に例示するように、データフレームはｋビットの情報とｒビットの冗長からなる長さｎビットのデータ列（符号）である。当該データ列は、情報ビット部分１０、１１，１２、１３・・・と冗長ビット部分２０、２１，２２，２３・・・とが交互に配置された構造を有し、情報ビット部分１０、１１，１２、１３・・・のそれぞれの長さ、言い換えれば情報ビット部分に配置される冗長ビットのパターンは、後述するようにＣＲＣ多項式により決定することができる。各冗長ビットは、それよりも先行する（左側に位置する）情報ビット（あるいは情報ビットおよび冗長ビット）に基づいて生成される。

例えば、図１に示すように、データ列のビットは、先頭ビットを０番目として順に（ｎ−１）番目まで付番され、ｒ個の冗長ビットがそれぞれｔ_０、ｔ_１、・・・ｔ_ｒ−１番目のビットに配置されているものとする。この場合、ｔ_０番ビットに位置する第１冗長ビットは、それよりも左に位置する０〜（ｔ_０−１）までの情報ビットによって定まる。同様に、ｔ_１番ビットに位置する２番目の冗長ビットは、それよりも左に位置する０〜（ｔ_１−１）までの全ビット、すなわち０〜（ｔ_０−１）までの情報ビット、ｔ_０番目の第１冗長ビットおよび（ｔ_０−１）〜（ｔ_１−１）までの情報ビット、によって定まる。以下同様に、ｊ番目の冗長ビットは、データ列の左端からｔ_{（ｊ−１）}番目のビットに位置し、それよりも左側に位置する０〜（ｔ_ｊ−１−１）までの全ビットによって定まる。

上述したように冗長ビットを分散配置させたことで、受信側の復号器は、各冗長ビット
を利用して、それよりも左側に位置する受信データに誤りが有るか否かを検査することが可能となる。即ち、受信データ列の全情報ビットを参照することなく、途中の冗長ビットを読み出した時点で誤りの有無を判定することができ、平均して早期の誤り検出が可能となる。

２．第一実施例
上述した図１に例示した冗長ビットの分散配置は、冗長ビットを付加したデータフレームのビットを後述する置換パターンπに基づいて入れ替えることにより実行することができる。以下、この方法を採用した本発明の第一実施例について図２〜図５を参照しながら説明する。

２．１）構成
図２に例示するように、本実施例による符号器は、ＣＲＣ演算機能３０とビット入れ替え機能３１とを有する。まず、ＣＲＣ演算機能３０は、予め与えられたＣＲＣ多項式３２を用いて冗長ビットを算出する。さらに、ビット入れ替え機能３１は、当該ＣＲＣ多項式３２から生成された置換パターン３３を用いて、ＣＲＣ演算３０により得られたビット列のビット入れ替えを実行し、図１に示す冗長ビットが分散配置されたｎビット出力を生成する。以下、図１に示す冗長ビットの分散配置を可能にする置換パターン３３を置換パターンπと呼ぶことにする。

図３に例示するように、本発明の第一実施例による符号器１００は、ＣＲＣ算出部１０１と、その後段に設けられたインターリーバ１０２と、からなる。ＣＲＣ算出部１０１は上述したようにＣＲＣ演算により冗長ビットを算出して情報ビットに追加した伝送フレームＣ１を出力し、インターリーバ１０２は、置換パターンπを用いて、伝送フレームＣ１中のビット位置を並び替え、図１に示すような伝送フレームＣ２を出力する。

２．２）置換パターンπの生成手順
置換パターンπは、冗長ビットを生成するＣＲＣ多項式から次の手順により予め算出され、保存される。

図４に例示するように、まず、ＣＲＣ多項式ｇ（ｘ）の次数をｒ、周期をｐとして、多項式ｘ^p−１をＣＲＣ多項式ｇ（ｘ）によって除算し、商多項式ｑ（ｘ）＝ｑ_０＋ｑ_１ｘ＋・・・＋ｑ_ｍｘ^ｍを算出する（動作Ｓ２０１）。

続いて、商多項式ｑ（ｘ）の係数ｑ_０、ｑ_１、・・・ｑ_ｍから、長さｎのビット列ｈ_０,ｈ_１,…,ｈ_ｎ−１を次式（１）により生成する（動作Ｓ２０２）。

続いて、生成されたビット列ｈ_０,ｈ_１,…,ｈ_ｎ−１から、所定の手順（図５参照）によって、上述した冗長ビットが出力される時点ｔ_０、ｔ_１、・・・ｔ_ｒ−１の計算に必要な置換パターンπ（０）、π（１）、・・・π（ｎ−１）を生成し（動作Ｓ２０３）、メモリに格納される（動作Ｓ２０４）。

こうして生成された置換パターンπに従って、インターリーバ１０２はデータフレームＣ１のビットを入れ替えてデータフレームＣ２を出力する。なお、置換パターンπは、０〜ｎ−１の間のｎ個の整数の順序を他の順序で置き換える操作を示す。例えば、ｎ＝５であれば、０，１，２，３，４の順序を置換パターンπによって並べ替えた結果、１，０，４，２，３になったとすれば、π(０)＝１、π(１)＝０、π(２)＝４、π(３)＝２、π(４)＝３と表記される。

＜置換パターンπ＞
置換パターンπの生成手順の一例を図５に示す。変数ｔ，ｉ，ｊを初期化した後（動作Ｓ３０１，Ｓ３０２）、ｈ_{ｒ−１−ｉ＋ｊ}＝１であり、かつｊが｛π(０)、π(１)、・・・、π(ｔ−１)｝の中に含まれていない場合（動作Ｓ３０３のＹＥＳ）、π（ｔ）をｊとして保存し、ｔを１だけインクリメントする（動作Ｓ３０４）。なお、ｈ_{ｒ−１−ｉ＋ｊ}が１でないか、あるいはｊが｛π(０)、π(１)、・・・、π(ｔ−１)｝の中に含まれる場合には（動作Ｓ３０３のＮＯ）、動作Ｓ３０４は実行されない。

続いて、ｊがｋ＋ｉ未満であるか否かを判断し（動作Ｓ３０５）、ｊ＜ｋ＋ｉであれば（動作Ｓ３０５のＹＥＳ）、ｊを１だけインクリメントして（動作Ｓ３０６）、動作Ｓ３０３へ戻る。以下、ｊをインクリメントしながら、ｊが（ｋ＋ｉ）以上になるまで動作Ｓ３０３〜Ｓ３０６を繰り返す。ｊが（ｋ＋ｉ）以上になると（動作Ｓ３０５のＮＯ）、ｉがｕ−１未満であるか否かを判断し（動作Ｓ３０７）、ｉ＜ｕ−１であれば（動作Ｓ３０７のＹＥＳ）、ｉを１だけインクリメントして（動作Ｓ３０８）、動作Ｓ３０２へ戻ってｊを初期化する。以下、ｉをインクリメントしながら、ｉが（ｕ−１）以上になるまで動作Ｓ３０２〜Ｓ３０８を繰り返す。なお、ｕは冗長ビット数ｒ以下の正の整数であり、動作Ｓ３０７は冗長ビットの前半ｕビット分のみを置換パターンにより分散させることを意味する。

こうしてｉが（ｕ−１）以上になると（動作Ｓ３０７のＮＯ）、ｔが（ｎ−１）を超えているか否かを判断し（動作Ｓ３０９）、ｔが（ｎ−１）以下であれば（動作Ｓ３０９のＮＯ）、ｋの値がｔからｎ−１に到達するまで、以下の演算を順次実行する（動作Ｓ３１０）。

ｔが（ｎ−１）を超えていれば（動作Ｓ３０９のＹＥＳ）、動作Ｓ３１０は実行されない。

こうして、ｔが（ｎ−１）に到達すると、その時点で保持されている｛π(０)、π(１)、・・・、π(ｎ−１)｝を置換パターンπとして出力する（動作Ｓ３１１）。

なお、上述したように、動作Ｓ３０７におけるｕは、冗長ビットの一部分（前半ｕビット分）のみを置換パターンにより分散させるためのパラメータである。したがって、ｕ＝ｒであれば、全ての冗長ビットが図１に例示するように情報ビット部分内に分散する。

一般に、図４における動作Ｓ２０２で導いた長さｎ（＝ｋ＋ｒ）のビット列ｈ_０,ｈ_１,…,ｈ_ｎ−１に関して、当該ビット列の後半ｋ＋１番目以降の系列ｈ_ｒ−１,ｈ_ｒ，…,ｈ_ｎ−１に含まれる１の個数が、置換パターンπによって入れ替えられた系列において最初の冗長ビットが現れる時点に対応する。言い換えれば、後半ｋ＋１番目以降のビット系列
に含まれる１の個数をｗとすれば、最初の冗長ビット（図１における１ｓｔ冗長ビット）が現れる時点ｔ_０がｗ−１に等しい（ｔ_０＝ｗ−１）あるいはｔ_０＜ｗという関係が成立する。以下、具体例を用いて説明する。

２．３）例
図４および図５に示す置換パターンπの生成手順の具体例を挙げる。一例として、情報ビット数ｋ＝３０、冗長ビット数ｒ＝８、ＣＲＣ多項式ｇ（ｘ）＝ｘ^８＋ｘ^２＋ｘ＋１のケースを説明する。なお、多項式ｇ（ｘ）の周期ｐは、多項式ｘ^ｐ−１がｇ（ｘ）で割り切れる最小の整数であり、ここではｐ＝１２７となる。

多項式ｘ^ｐ−１をｇ（ｘ）で割った商多項式ｑ（ｘ）の係数から、図４の動作Ｓ２０２の処理により、次に示す３８ビット（＝ｋ＋ｒ）のビット列：
ｈ_０ｈ_１…ｈ_３７＝00110011010000101011010101000111000001
が得られる。

この３８ビットのビット列から図５の手順により、次の置換パターンπ(0),π(1),…,π(37) が得られる：0 2 7 9 11 12 14 16 18 22 23 24 30 1 3 8 10 13 15 17 19 25 31 4 20 26 32 5 21 27 33 6 28 34 29 35 36 37。

この置換パターンπ(0),π(1),…,π(37)の下線部は冗長ビットが現れる時点ｔ_０，ｔ_１，・・・、ｔ_７となり、それぞれ時点ｔ＝12, 22, 26, 30, 33, 35, 36, 37となる。上記ビット列：ｈ_０ｈ_１…ｈ_３７＝00110011010000101011010101000111000001の中に含まれる１の数は１６であり、後半の３１ビット中に現れる１の数ｗが１３である。したがって、ｔ＝ｗ−１＝１２の時点で最初の冗長ビットが現れる。

以上より、本方式による冗長ビット分散配置を採用することにより、全てのデータを受信する前に、最短で、時点ｔ＝ｗ−１で誤り検出を行うことが可能となり、誤り検出に要する平均時間を短縮する事が可能となる。特に、本実施例による冗長ビット生成装置は、既存のＣＲＣ演算により冗長ビットを算出した後で、同じＣＲＣ多項式から生成された置換パターンにより並び替えを行っているために、簡単な構成で図１に示す冗長ビットを分散配置したデータ列を得ることができる。

３．第二実施例
上述した図１に例示するデータ構成は、上述した第一実施例だけでなく、冗長ビット生成過程で上記置換パターンπを用いることにより生成することもできる。

図６に例示するように、本発明の第二実施例による冗長ビット生成装置４００は、ｋビットの情報ビット列を入力し、図１に示すようなｒ個の冗長ビットを分散させたｎ（＝ｋ＋ｒ）ビットのデータ列を出力する。以下、本実施例による冗長ビット生成装置４００の機能的構成および動作について説明する。

３．１）構成
冗長ビット生成装置４００は、選択スイッチ４０１と、ｒ個のスイッチＳＷ（０）〜ＳＷ（ｒ−１）からなるスイッチ群４０２と、ｒ個の累積加算部（排他的論理和回路ＥＸおよび１ビットレジスタＲの組）と、入力Ｄおよび累積加算部の出力Ｓ（ｉ）から一つを選択するセレクタ４０３と、選択スイッチ４０１、スイッチ群４０２およびセレクタ４０３を制御するコントローラ４０４と、後述する長さｎのビット列ｈと置換パターンπとを格納するメモリ４０５と、を有する。なお、各累積加算部は排他的論理和回路ＥＸ_ｉおよび１ビットレジスタＲ_ｉが直列接続された回路であり、以下、ｉ＝０，１，…，ｒ−１とす
る。

選択スイッチ４０１は、ｋビット情報が入力する端子Ａと、セレクタ４０３の出力が入力する端子Ｂと、端子ＡあるいはＢに選択的に接続する端子Ｃとを有し、端子Ｃはスイッチ群４０２の各スイッチＳＷ及びセレクタ４０３の１つの入力Ｄに接続されている。選択スイッチ４０１は、コントローラ４０４の制御に従って、ｋビット情報あるいはセレクタ４０３の出力のいずれかを選択し、選択されたビットをスイッチ群４０２へ出力する。

スイッチ群４０２のスイッチＳＷ（０）、ＳＷ（１）、・・・ＳＷ（ｒ−１）は、それぞれ、累積加算部の排他的論理和回路ＥＸ_０、ＥＸ_１、・・・ＥＸ_ｒ−１に接続され、コントローラ４０４からの制御信号ｈ_π(t)+r-1、ｈ_π(t)+r-2、・・・ｈ_π(t)により個別にオープン／クローズ制御される。これら制御信号ｈ_π(t)+r-1-iは、後述するように、時点ｔ毎に変化し、スイッチ群４０２の開閉状態を時点毎に変化させる。このようなスイッチＳＷ（ｉ）の開閉制御により、選択スイッチ４０１により選択されたビットを、対応する累積加算部へ出力するか否かが決定される。

各排他的論理和回路ＥＸ_ｘは１ビットレジスタＲ_ｉと直列接続され、対応するスイッチＳＷ（ｉ）の出力ビットと１ビットレジスタＲ_ｉの保持ビットＳ（ｉ）とを入力し、その排他的論理和を新たな保持ビットとして１ビットレジスタＲ_ｉへ出力する。即ち、１ビットレジスタＲ_０〜Ｒ_ｒ−１にはスイッチ群４０２で選択された入力ビットに対する累積加算結果が保持される。

セレクタ４０３は、コントローラ４０４の制御に従って、選択スイッチ４０１の端子Ｃの出力ビットＤおよび１ビットレジスタＲ_０〜Ｒ_ｒ−１のそれぞれの保持ビットＳ（０）〜Ｓ（ｒ−１）から１つを選択し、ｎ（＝ｋ＋ｒ）ビットのデータ列として出力する。尚、後述するように、本装置は送信側で冗長ビットの生成に利用できるだけでなく、受信側で誤り検出を実行する装置としても利用可能である。

３．２）動作
次に、図６および図７を参照しながら、上述した冗長ビット生成装置４００がｋビット入力情報から図１に示した形式のｎビット出力を得る動作を説明する。まず、１ビットレジスタＲ_０〜Ｒ_ｒ−１の保持ビットはそれぞれ０に初期化されているものとする。

図７において、ｋビット入力情報の最初の情報ビット部分１０が入力する間、選択スイッチ４０１は端子Ａを選択して、入力ビットを順次スイッチ群４０２へ出力する。入力ビットは、各スイッチＳＷが開閉制御されたスイッチ群４０２を通して、累積加算部の排他的論理和回路ＥＸ_０〜ＥＸ_ｒ−１へ提供される。排他的論理和回路ＥＸ_０〜ＥＸ_ｒ−１はそれぞれ、入力ビットと１ビットレジスタＲ_０〜Ｒ_ｒ−１の現時点での保持ビットとの排他的論理和を新たな保持ビットとして１ビットレジスタＲ_０〜Ｒ_ｒ−１に格納する。この間、セレクタ４０３は入力Ｄを選択し、ｎビット出力の最初のビット部分０〜ｔ_０−１として出力する。したがって、上述したように、時点０から時点ｔ_０−１までにセレクタ４０３から出力されるビット列は、入力情報ビット部分１０と同一である。

次の時点ｔ_０で、セレクタ４０３は１ビットレジスタＲ_０の保持ビットＳ（０）を選択して第一番目の冗長ビットとして出力し、選択スイッチ４０１は端子Ｂを選択してセレクタ４０３の出力ビット、すなわち第一番目の冗長ビットをスイッチ群４０２へ出力する。第一番目の冗長ビットは、各スイッチＳＷが開閉制御されたスイッチ群４０２を通して、累積加算部の排他的論理和回路ＥＸ_０〜ＥＸ_ｒ−１へ提供され、上述したように第一番目の冗長ビットと１ビットレジスタＲ_０〜Ｒ_ｒ−１の現時点での保持ビットとの排他的論理和によって１ビットレジスタＲ_０〜Ｒ_ｒ−１の保持ビットを更新する。

続く時点ｔ_０＋１〜ｔ_１−１までの間は、上述した時点０〜ｔ_０−１までの動作と同様に、入力ビットがそのまま出力されると共に、１ビットレジスタの保持するデータが更新される。したがって、上述したように、時点ｔ_０＋１〜ｔ_１−１までにセレクタ１０３から出力されるビット列は、入力情報ビット部分１１と同一である。

次の時点ｔ_１で、セレクタ４０３は１ビットレジスタＲ_１の保持ビットＳ（１）を選択して第二番目の冗長ビットとして出力し、選択スイッチ４０１は端子Ｂを選択してセレクタ４０３の出力ビット、すなわち第二番目の冗長ビットをスイッチ群４０２へ出力する。第二番目の冗長ビットは、各スイッチＳＷが開閉制御されたスイッチ群４０２を通して、累積加算部の排他的論理和回路ＥＸ_０〜ＥＸ_ｒ−１へ提供され、上述したように第二番目の冗長ビットと１ビットレジスタＲ_０〜Ｒ_ｒ−１の現時点での保持ビットとの排他的論理和によって１ビットレジスタＲ_０〜Ｒ_ｒ−１の保持ビットを更新する。

続く時点ｔ_１＋１〜ｔ_２−１までの間は、上述した時点０〜ｔ_０−１までの動作と同様に、入力ビットがそのまま出力されると共に、１ビットレジスタの保持するデータが更新される。以下同様に、情報ビットをそのまま出力しながら１ビットレジスタの保持データを更新し、冗長ビットは、対応する１ビットレジスタの保持データをセレクタ４０３によって選択することで出力し、選択スイッチ４０１を通してスイッチ群４０２へ提供する。

３．３）ビット列ｈおよび置換パターンπ
メモリ４０５に格納される長さｎのビット列ｈ_０,ｈ_１,…,ｈ_ｎ−１と置換パターンπとは、上述した第一実施例と同様に、ＣＲＣ多項式から算出される。

図８において、まず、ＣＲＣ多項式ｇ（ｘ）の次数をｒ、周期をｐとして、多項式ｘ^p−１をＣＲＣ多項式ｇ（ｘ）によって除算し、商多項式ｑ（ｘ）＝ｑ_０＋ｑ_１ｘ＋・・・＋ｑ_ｍｘ^ｍを算出する（動作Ｓ５０１）。続いて、商多項式ｑ（ｘ）の係数ｑ_０、ｑ_１、・・・ｑ_ｍから、スイッチ群４０２の開閉制御に必要な長さｎのビット列ｈ_０,ｈ_１,…,ｈ_ｎ−１を、上述した式（１）により生成する（動作Ｓ５０２）。

続いて、生成されたビット列ｈ_０,ｈ_１,…,ｈ_ｎ−１から、所定の手順（図５参照）によって、上述した冗長ビットが出力される時点ｔ_０、ｔ_１、・・・ｔ_ｒ−１の計算に必要な置換パターンπ（０）、π（１）、・・・π（ｎ−１）を生成する（動作Ｓ５０３）。こうして得られたビット列ｈ_０,ｈ_１,…,ｈ_ｎ−１と置換パターンπ（０）、π（１）、・・・π（ｎ−１）とがメモリ４０５に格納される（動作Ｓ５０４）。

コントローラ４０４は、各時点ｔ＝０，１，２，・・・ｎ−１において、置換パターンπとビット列ｈ_０,ｈ_１,…,ｈ_ｎ−１とを用いてスイッチ群４０２の各スイッチＳＷの開閉を決定する。より詳しくは、時点ｔにおいて、スイッチＳＷ（ｉ）は、ｈ_π(t)+r-1-i＝１であれば閉じ、それ以外であれば開く。なお、π(t)+r-1-iの値が０〜ｎ−１の範囲外であれば、各スイッチＳＷ（ｉ）は開状態となる。

また、コントローラ４０４は、セレクタ４０３が時点ｔ＝０，１，２，・・・ｎ−１において選択する信号を変化させ、上述した冗長ビットを選択する時点ｔ_ｉ（ｔ_０、ｔ_１、・・・ｔ_ｒ−１）を次式により決定する。
ｔ_ｉ＝π^-1（ｋ＋ｉ）
ここで、π^-1は、上記置換パターンπの逆変換であり、ｋは情報ビット数、ｉは０〜ｒ−１の間の整数である。すなわち、セレクタ４０３は、時点ｔ_ｉ＝π^-1（ｋ＋ｉ）において、１ビットレジスタＲ_ｉの保持ビットＳ（ｉ）を選択し、ｉ番目の冗長ビットとして出力し、それ以外の時点では入力データＤを選択して出力する。

以上述べたように、本発明の第二実施例による冗長ビット生成装置４００は、ｋビットの情報ビット列を入力し、図１に示すようなｒ個の冗長ビットを分散させたｎ（＝ｋ＋ｒ）ビットのデータ列を出力することができる。

３．４）誤り検出
図６に例示した冗長ビット生成装置４００は、送信側で冗長ビットの生成に利用できるだけでなく、受信側で誤り検出を実行することも可能である。図１に例示したデータが送信され、その受信データに含まれる誤りを検出する場合、符号化とは逆の手順が採用される。

図９に例示するように、受信側の誤り検出装置４００ｒは、図６に示す冗長ビット生成装置と同様の回路構成を有するので、構成要素を図６における参照番号に「ｒ」を付加して区別する。スイッチ群４０２ｒは、選択スイッチ４０１ｒを通して、受信データの情報ビット部分あるいは冗長ビット部分を入力し、コントローラ４０４ｒの制御に従って累積加算部へ出力する。それぞれの累積加算部は冗長ビットＳ（ｉ）を算出し、セレクタ４０３ｒが受信データＤあるいは算出された冗長ビットＳ（ｉ）を選択する。セレクタ４０３ｒが選択したビットは判定部４０６ｒへ出力され、判定部が受信データ中の冗長ビットと算出された冗長ビットとの一致／不一致を判定する。すなわち、受信情報ビットから算出された冗長ビットと受信冗長ビットとが一致すれば誤り無し、不一致であれば誤り有と判定される。したがって、受信側の復号器においても、図６の冗長ビット生成装置の回路構成を適用可能である。

３．５）効果
上述したように、本発明の第二実施例によれば、図１に示すデータ構造を有する分散配置された冗長ビットを利用して、それよりも左側に位置する受信データに誤りが有るか否かを検査することができる。即ち、受信データ列の全情報ビットを参照することなく、途中の冗長ビットを読み出した時点で誤りの有無を判定することができ、誤り検出に要する時間を平均的に短縮することができる。特に、図６に示す冗長ビット生成装置の構成は、そのまま受信側の誤り検出にも利用することができるという利点もある。さらに、本実施例による冗長ビット生成装置４００は、第一実施例におけるインターリーバ１０２が不要となり、それによりインターリーバを経由することにより生じる１フレーム分の遅延を削除できるという利点がある。

４．第三実施例
上述した第一及び第二実施例による装置と同様の機能は、プロセッサ上でプログラムを実行することにより実現することができる。

図１０に例示するように、プロセッサ６０１およびプログラムメモリ６０２からなる情報処理装置において、プロセッサ６０１がプログラムメモリ６０２から必要なプログラムを読み出して実行することにより、図２あるいは図６に例示した回路構成をソフトウエアにより実現することができる。プロセッサ６０１は、ＣＰＵ(Central Processing Unit)あるいはコンピュータとも呼ばれる。プログラムメモリ６０２は、読み出し専用でも読み書き可能メモリであってもよく、装置内に組み込まれたメモリであっても、取り外し可能なメモリであってもよい。

５．適用例
次に、上述した第一あるいは第二実施例による冗長ビット生成装置を誤り訂正技術として知られるＰｏｌａｒ符号の符号化装置および復号装置に適用した例を説明する。

図１１に例示するように、符号化装置７０１は、本発明の上記実施例による誤り検出用冗長ビット生成部１００あるいは４００と、誤り検出用冗長ビット生成部の出力データをＰｏｌａｒ符号の情報ビット位置に割り当てるマッピング部７０２と、マッピングされたデータをＰｏｌａｒ符号化するＰｏｌａｒ符号化部７０３と、を備える。すなわち、誤り検出用冗長ビット生成部１００あるいは４００が、図１に例示するように、入力する情報ビットに対して誤り検出用の冗長ビットを分散配置したデータフレームを出力し、Ｐｏｌａｒ符号化部７０３が符号化処理を行って対応するビット列を出力する。

図１２に例示するように、第一あるいは第二実施例による冗長ビット生成回路を適用した復号装置は、Ｐｏｌａｒ符号に関する通常のリスト復号部８０１の後段に、本発明の上記実施例による誤り検出部４００ｒと判定部８０２とを備えた構成を有する。Ｐｏｌａｒ符号のリスト復号器８０１は、ノイズ等による誤りを含む受信ビット列から、予め定められたリストサイズと同数の送信ビット列の候補を先頭ビットから順次出力する。誤り検出部４００ｒは、出力された各ビット列に対して順次誤りの有無を検査し、判定部８０２は、ＣＲＣによって誤りが検出されなかった候補が正しい訂正結果と判定し、全ての候補について誤りが検出されれば、その時点で処理を終了する。

上述したように、本実施例によれば、受信データ列の全情報ビットを参照することなく、途中の冗長ビットを読み出した時点で誤りの有無を判定することができるので、Ｐｏｌａｒ符号の復号装置に適用することで、誤り検出に要する時間を平均的に短縮することができる。

本発明は、通信システムにおける誤り検出用の冗長ビット生成回路を含む符号器、復号器に適用可能である。

１０−１３ 情報ビット部分
２０−２３ 冗長ビット
３０ ＣＲＣ演算
３１ ＣＲＣ多項式
３２ 置換パターン
３３ ビット入れ替え
１００ 冗長ビット生成装置
１０１ ＣＲＣ演算部
１０２ インターリーバ
４００ 冗長ビット生成装置
４０１ 選択スイッチ
４０２ スイッチ群
４０３ セレクタ
４０４ コントローラ

Claims (26)

1. ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する装置であって、
   巡回冗長検査（ＣＲＣ）多項式により前記情報ビットから所定数の冗長ビットを生成する冗長ビット演算手段と、
   前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記所定数の冗長ビットを前記情報ビット内に分散配置するビット入れ替え手段と、
   を有することを特徴とする装置。
2. 前記置換パターンは出力データ列と同じ長さのビットパターンから生成され、
   前記ビット入れ替え手段が、前記置換パターンを用いて前記ビットパターンの順序を入れ替えることにより前記情報ビット列の中に前記所定数の冗長ビットを分散配置する、
   ことを特徴とする請求項１に記載の装置。
3. 前記置換パターンに従って、前記出力データ列のなかで最初に現れる冗長ビットが、前記ビットパターン中に含まれる１の数より小さい値の時点に配置される、ことを特徴とする請求項２に記載の装置。
4. 前記ビットパターンは、ＣＲＣ多項式ｇ（ｘ）の周期ｐに対する多項式ｘ^ｐ−１をＣＲＣ多項式ｇ（ｘ）により除算して得られる商多項式ｑ（ｘ）の係数から生成され、
   前記置換パターンは、前記ビットパターンのなかの１の位置から生成される、
   ことを特徴とする請求項２または３に記載の装置。
5. ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する装置であって、
   前記情報ビットを入力する、巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ手段と、
   前記開閉スイッチ手段の各々の出力を個別に累積加算して前記冗長ビットを算出する累積加算手段と、
   前記入力した情報ビットおよび前記累積加算手段のそれぞれが算出した冗長ビットのいずれかを選択して、前記情報ビットに前記冗長ビットを追加したデータ列を生成する選択手段と、
   前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ手段および前記選択手段を制御する制御手段と、
   を有することを特徴とする装置。
6. 前記置換パターンは前記データ列と同じ長さの所定ビットパターンから生成され、
   前記制御手段が、前記置換パターンを用いて前記所定ビットパターンを置換した結果に従って前記開閉スイッチ手段の各々を開閉制御し、前記置換パターンに基づいて決定された前記冗長ビットの配置に従って、前記選択手段を選択制御する、
   ことを特徴とする請求項５記載の装置。
7. 前記置換パターンに従って、前記出力データ列のなかで最初に現れる冗長ビットが前記ビットパターン中に含まれる１の数より小さい値の時点に配置されることを特徴とする請求項６に記載の装置。
8. 前記所定ビットパターンは、ＣＲＣ多項式ｇ（ｘ）の周期ｐに対する多項式ｘ^ｐ−１をＣＲＣ多項式ｇ（ｘ）により除算して得られる商多項式ｑ（ｘ）の係数から生成され、前記置換パターンは前記所定ビットパターンのなかの１の位置から生成される、ことを特徴とする請求項６または７に記載の装置。
9. ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する方法であって、
   冗長ビット演算手段が巡回冗長検査（ＣＲＣ）多項式により前記情報ビットから所定数の冗長ビットを生成し、
   ビット入れ替え手段が、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記所定数の冗長ビットを前記情報ビット内に分散配置する、
   ことを特徴とする方法。
10. 前記置換パターンは前記出力データ列と同じ長さのビットパターンから生成され、
    前記ビット入れ替え手段が、前記置換パターンを用いて前記ビットパターンの順序を入れ替えることにより前記情報ビット列の中に前記所定数の冗長ビットを分散配置する、
    ことを特徴とする請求項９に記載の方法。
11. 前記置換パターンに従って、前記出力データ列のなかで最初に現れる冗長ビットを、前記ビットパターン中に含まれる１の数より小さい値の時点に配置する、ことを特徴とする請求項１０に記載の方法。
12. 前記ビットパターンは、ＣＲＣ多項式ｇ（ｘ）の周期ｐに対する多項式ｘ^ｐ−１をＣＲＣ多項式ｇ（ｘ）により除算して得られる商多項式ｑ（ｘ）の係数から生成され、
    前記置換パターンは、前記ビットパターンのなかの１の位置から生成される、
    ことを特徴とする請求項１０または１１に記載の方法。
13. ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する方法であって、
    巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ手段が前記情報ビットを入力し、各開閉スイッチ手段を開閉制御する第１制御信号に従って当該情報ビットを通過あるいは遮断し、
    累積加算手段が、前記開閉スイッチ手段の各々の出力を個別に累積加算して前記冗長ビットを算出し、
    選択手段が、第２制御信号に従って、前記入力した情報ビットおよび前記累積加算手段のそれぞれが算出した冗長ビットのいずれかを選択し、前記情報ビットに前記冗長ビットを追加したデータ列を生成し、
    制御手段が、前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ手段および前記選択手段を制御する前記第１制御信号および前記第２制御信号を出力する、
    ことを特徴とする方法。
14. 前記置換パターンは前記データ列と同じ長さの所定ビットパターンから生成され、
    前記制御手段が、前記置換パターンを用いて前記所定ビットパターンを置換した結果に従って前記第１制御信号を生成し、前記置換パターンに基づいて決定された前記冗長ビットの配置に従って前記第２制御信号を生成する、
    ことを特徴とする請求項１３に記載の方法。
15. 前記置換パターンに従って、前記出力データ列のなかで最初に現れる冗長ビットが、前記ビットパターン中に含まれる１の数より小さい値の時点に配置される、ことを特徴とする請求項１４に記載の方法。
16. 前記所定ビットパターンは、ＣＲＣ多項式ｇ（ｘ）の周期ｐに対する多項式ｘ^ｐ−１をＣＲＣ多項式ｇ（ｘ）により除算して得られる商多項式ｑ（ｘ）の係数から生成され、前
    記置換パターンは前記所定ビットパターンのなかの１の位置から生成される、ことを特徴とする請求項１４または１５に記載の方法。
17. 請求項１−８のいずれか１項に記載の装置と、
    前記装置により生成された前記データ列を入力し、誤り訂正符号を生成する誤り訂正符号化手段と、
    を有する符号器。
18. ブロック化された情報ビットに追加された誤り検出を可能にする冗長ビットを用いて誤りを検出する装置であって、
    受信データの情報ビットを入力する、巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ手段と、
    前記開閉スイッチ手段の各々の出力を個別に累積加算して前記冗長ビットを算出する累積加算手段と、
    前記受信データの冗長ビットおよび前記累積加算手段のそれぞれが算出した冗長ビットのいずれかを選択する選択手段と、
    前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ手段の各々の開閉制御および前記選択手段の選択制御を実行する制御手段と、
    前記受信データの冗長ビットと前記算出した冗長ビットとを比較して誤りの有無を判定する判定手段と、
    を有することを特徴とする装置。
19. 前記置換パターンは前記データ列と同じ長さの所定ビットパターンから生成され、
    前記制御手段が、前記置換パターンを用いて前記所定ビットパターンを置換した結果に従って前記開閉スイッチ手段の各々を開閉制御し、前記置換パターンに基づいて決定された前記冗長ビットの配置に従って前記選択手段を選択制御する、
    ことを特徴とする請求項１８に記載の装置。
20. 前記置換パターンに従って、前記出力データ列のなかで最初に現れる冗長ビットは、前記ビットパターン中に含まれる１の数より小さい値の時点に配置されることを特徴とする請求項１９に記載の装置。
21. 前記所定ビットパターンは、ＣＲＣ多項式ｇ（ｘ）の周期ｐに対する多項式ｘ^ｐ−１をＣＲＣ多項式ｇ（ｘ）により除算して得られる商多項式ｑ（ｘ）の係数から生成され、前記置換パターンは前記所定ビットパターンのなかの１の位置から生成される、ことを特徴とする請求項１９または２０に記載の装置。
22. 受信した誤り訂正符号を復号して受信データを出力する誤り訂正復号手段と、
    前記受信データを入力する請求項１８−２１のいずれか１項に記載の装置と、
    前記装置の判定手段が誤り有りと判定すると、前記誤り訂正復号手段の復号処理を中断することを特徴とする復号器。
23. ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する装置としてコンピュータを機能させるプログラムであって、
    巡回冗長検査（ＣＲＣ）多項式により前記情報ビットから所定数の冗長ビットを生成する冗長ビット演算機能と、
    前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記所定数の冗長ビットを前記情報ビット内に分散配置するビット入れ替え機能と、
    を前記コンピュータに実現することを特徴とするプログラム。
24. ブロック化された情報ビットに追加される誤り検出を可能にする冗長ビットを生成する装置としてコンピュータを機能させるプログラムであって、
    前記情報ビットを入力する、巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ機能と、
    前記開閉スイッチ機能の各々の出力を個別に累積加算して前記冗長ビットを算出する累積加算機能と、
    前記入力した情報ビットおよび前記累積加算機能のそれぞれが算出した冗長ビットのいずれかを選択して、前記情報ビットに前記冗長ビットを追加したデータ列を生成する選択機能と、
    前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ機能および前記選択機能を制御する機能と、
    を前記コンピュータに実現することを特徴とするプログラム。
25. 前記データ列を入力し、誤り訂正符号を生成する誤り訂正符号化機能を前記コンピュータに更に実現することを特徴とする請求項２３または２４に記載のプログラム。
26. ブロック化された情報ビットに追加された誤り検出を可能にする冗長ビットを用いて誤りを検出する装置としてコンピュータを機能させるプログラムであって、
    受信データの情報ビットを入力する、巡回冗長検査（ＣＲＣ）多項式により算出される冗長ビットの数と同数の開閉スイッチ機能と、
    前記開閉スイッチ機能の各々の出力を個別に累積加算して前記冗長ビットを算出する累積加算機能と、
    前記受信データの冗長ビットおよび前記累積加算機能のそれぞれが算出した冗長ビットのいずれかを選択する選択機能と、
    前記ＣＲＣ多項式に対応して定めた置換パターンを用いて前記開閉スイッチ機能の各々の開閉制御および前記選択機能の選択制御を実行する機能と、
    前記受信データの冗長ビットと前記算出した冗長ビットとを比較して誤りの有無を判定する機能と、
    を前記コンピュータに実現することを特徴とするプログラム。

Images