(57)【特許請求の範囲】
【請求項１】
所定の符号長を有する符号化が施された受信データのシンドロームを生成するシンドローム生成手段と、
受信データに１ビットの誤りが発生した場合に対応する複数のシンドロームデータを予め記憶するシンドローム記憶手段と、
前記シンドローム生成手段により生成されたシンドロームと、前記シンドローム記憶手段に記憶されている複数のシンドロームデータとに基づいて、受信データの誤り発生位置を特定する誤り特定手段と、
前記誤り特定手段により特定された誤り発生位置のビットを反転して受信データの誤りを訂正する誤り訂正手段と、
受信データのうちの１ビットを反転するビット反転手段と、
前記シンドローム記憶手段に記憶されている２つのシンドロームデータの排他的論理和を求める論理演算手段とを備え、
前記シンドローム生成手段は、前記ビット反転手段により１ビットが反転されたデータのシンドロームを生成し、
前記誤り特定手段は、前記シンドローム生成手段が前記ビット反転手段により１ビットが反転された受信データから生成したシンドロームと、前記論理演算手段が求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した３ビットの誤り発生位置を特定する、
ことを特徴とする誤り訂正装置。
【請求項２】
前記ビット反転手段は、受信データのうちで反転するビットの位置を移動させ、受信データのうちの１ビットを反転したデータを逐次生成する、
ことを特徴とする請求項１に記載の誤り訂正装置。
【請求項３】
前記誤り特定手段は、前記シンドローム生成手段により生成されたシンドロームと、前記シンドローム記憶手段に記憶されている複数のシンドロームデータのうちのいずれか１つとが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した１ビットの誤り発生位置を特定する、
ことを特徴とする請求項１又は２に記載の誤り訂正装置。
【請求項４】
前記誤り特定手段は、前記シンドローム生成手段により生成されたシンドロームと、前記論理演算手段が求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した２ビットの誤り発生位置を特定する、
ことを特徴とする請求項１、２又は３に記載の誤り訂正装置。
【請求項５】
所定の符号長を有する符号化が施された受信データのうちの１ビットを反転するビット反転ステップと、
受信データのシンドロームと、前記ビット反転ステップにて１ビットを反転したデータのシンドロームとを生成するシンドローム生成ステップと、
受信データに１ビットの誤りが発生した場合に対応して予めメモリに記憶された複数のシンドロームデータのうち、２つのシンドロームデータの排他的論理和を求める論理演算ステップと、
前記シンドローム生成ステップにて生成した受信データのシンドロームと、前記メモリに記憶されている複数のシンドロームデータのうちのいずれか１つとが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した１ビットの誤り発生位置を特定し、一致しないと判別した場合に、前記シンドローム生成ステップにて生成した受信データのシンドロームと、前記論理演算ステップにて求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した２ビットの誤り発生位置を特定し、一致しないと判別した場合に、前記シンドローム生成ステップにて生成した前記ビット反転ステップにて１ビットが反転されたデータのシンドロームと、前記論理演算ステップにて求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した３ビットの誤り発生位置を特定する誤り特定ステップと、
前記誤り特定ステップにて特定した誤り発生位置のビットを反転して受信データの誤りを訂正する誤り訂正ステップとを備える、
ことを特徴とする誤り訂正方法。
【請求項６】
コンピュータを、
所定の符号長を有する符号化が施された受信データに１ビットの誤りが発生した場合に対応する複数のシンドロームデータを予め記憶するシンドローム記憶手段と、
受信データのうちの１ビットを反転するビット反転手段と、
受信データのシンドロームと、前記ビット反転手段により１ビットが反転されたデータのシンドロームとを生成するシンドローム生成手段と、
前記シンドローム記憶手段に記憶されている２つのシンドロームデータの排他的論理和を求める論理演算手段と、
前記シンドローム生成手段により生成された受信データのシンドロームと、前記シンドローム記憶手段に記憶されている複数のシンドロームデータのうちのいずれか１つとが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した１ビットの誤り発生位置を特定し、一致しないと判別した場合に、前記シンドローム生成手段により生成された受信データのシンドロームと、前記論理演算手段が求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した２ビットの誤り発生位置を特定し、一致しないと判別した場合に、前記シンドローム生成手段が前記ビット反転手段により１ビットが反転されたデータから生成したシンドロームと、前記論理演算手段が求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した３ビットの誤り発生位置を特定する誤り特定手段と、
前記誤り特定手段により特定された誤り発生位置のビットを反転して受信データの誤りを訂正する誤り訂正手段と、
を備える誤り訂正装置として機能させるプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、符号化が施された受信データの誤りを訂正する誤り訂正装置に係り、特に、簡単な構成で、適切に受信データの誤りを訂正することができる誤り訂正装置に関する。
【０００２】
【従来の技術】
誤り訂正可能な巡回符号の１つとして、Golay符号（２３，１２）が知られている。このGolay符号（２３，１２）は、符号長が２３ビット、且つ情報ビットが１２ビットで、３ビットまでの誤りを検出して訂正することができる符号である。
【０００３】
従来より、このGolay符号（２３，１２）を復号する方法としては、例えば以下のようなものが考えられている。
【０００４】
（例１）図３のフローチャートに示すように、データを受信すると、検査方程式に受信データを代入する計算処理を実行してシンドロームを算出し（ステップＳ１０１）、算出したシンドロームから誤り位置多項式の係数を求める（ステップＳ１０２）。係数を求めることにより特定された誤り位置多項式から誤り位置を推定し（ステップＳ１０３）、推定した誤り位置のビットを反転するなどして誤りを訂正する（ステップＳ１０４）。
【０００５】
（例２）受信データより算出される受信シンドロームと誤り位置との対応関係を示すテーブルデータを予めメモリに記憶しておく。そして、図４のフローチャートに示すように、データを受信すると、検査方程式に受信データを代入する計算処理を実行して受信シンドロームを算出する（ステップＳ１１１）。算出された受信シンドロームとメモリに記憶されているテーブルデータとを照合して誤り位置を推定し（ステップＳ１１２）、推定した誤り位置のビットを反転するなどして誤りを訂正する（ステップＳ１１３）。
【０００６】
（例３）予め正しい受信データが分かっている場合には、図５のフローチャートに示すように、データを受信すると、正しい受信データと比較して（ステップＳ１２１）、正しい受信データと異なるビットが３ビット以下であるか否かを判別する（ステップＳ１２２）。
異なるビットが３ビット以下であると判別した場合（ステップＳ１２２にてＹＥＳ）、正しいデータを受信したとして、上記例１や例２の方法と同様にして誤りを訂正する（ステップＳ１２３）。
一方、異なるビットが３ビットより多いと判別した場合（ステップＳ１２２にてＮＯ）、誤りが訂正できないとして（ステップＳ１２４）、処理を終了する。
【０００７】
【発明が解決しようとする課題】
上記従来の技術では、例１の方法によると、多くの計算を要することから、所要時間や消費電力が増大するという問題がある。
また、例２の方法によると、Golay符号（２３，１２）にて誤りを訂正するためには、２１２、すなわち４０９６個のシンドロームに対応したテーブルデータが必要になる。このため、大きな記憶領域を必要とし、テーブルデータを参照する際に要する時間が増大するという問題がある。
【０００８】
例３の方法は、正しい受信データが予め分かっている場合にしか使用することができないという問題がある。
【０００９】
この発明は、上記実状に鑑みてなされたものであり、簡単な構成で、適切に受信データの誤りを訂正することができる誤り訂正装置を提供することを目的とする。
【００１０】
【課題を解決するための手段】
上記目的を達成するため、この発明の第１の観点に係る誤り訂正装置は、
所定の符号長を有する符号化が施された受信データのシンドロームを生成するシンドローム生成手段と、
受信データに１ビットの誤りが発生した場合に対応する複数のシンドロームデータを予め記憶するシンドローム記憶手段と、
前記シンドローム生成手段により生成されたシンドロームと、前記シンドローム記憶手段に記憶されている複数のシンドロームデータとに基づいて、受信データの誤り発生位置を特定する誤り特定手段と、
前記誤り特定手段により特定された誤り発生位置のビットを反転して受信データの誤りを訂正する誤り訂正手段と、
受信データのうちの１ビットを反転するビット反転手段と、
前記シンドローム記憶手段に記憶されている２つのシンドロームデータの排他的論理和を求める論理演算手段とを備え、
前記シンドローム生成手段は、前記ビット反転手段により１ビットが反転されたデータのシンドロームを生成し、
前記誤り特定手段は、前記シンドローム生成手段が前記ビット反転手段により１ビットが反転された受信データから生成したシンドロームと、前記論理演算手段が求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した３ビットの誤り発生位置を特定する、
ことを特徴とする。
ここで、前記ビット反転手段は、受信データのうちで反転するビットの位置を移動させ、受信データのうちの１ビットを反転したデータを逐次生成することが望ましい。
【００１１】
この発明によれば、シンドローム記憶手段は、受信データに１ビットの誤りが発生した場合に対応する複数のシンドロームデータを予め記憶している。誤り特定手段は、シンドローム生成手段により生成されたシンドロームと、シンドローム記憶手段に記憶されている複数のシンドロームデータに基づいて、受信データの誤り位置を特定する。
これにより、簡単な構成で、適切に受信データの誤りを訂正することができる。
【００１２】
また、前記誤り特定手段は、前記シンドローム生成手段により生成されたシンドロームと、前記シンドローム記憶手段に記憶されている複数のシンドロームデータのうちのいずれか１つとが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した１ビットの誤り発生位置を特定することが望ましい。
【００１３】
また、前記誤り特定手段は、前記シンドローム生成手段により生成されたシンドロームと、前記論理演算手段が求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した２ビットの誤り発生位置を特定することが望ましい。
【００１６】
この発明の第２の観点に係る誤り訂正方法は、
所定の符号長を有する符号化が施された受信データのうちの１ビットを反転するビット反転ステップと、
受信データのシンドロームと、前記ビット反転ステップにて１ビットを反転したデータのシンドロームとを生成するシンドローム生成ステップと、
受信データに１ビットの誤りが発生した場合に対応して予めメモリに記憶された複数のシンドロームデータのうち、２つのシンドロームデータの排他的論理和を求める論理演算ステップと、
前記シンドローム生成ステップにて生成した受信データのシンドロームと、前記メモリに記憶されている複数のシンドロームデータのうちのいずれか１つとが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した１ビットの誤り発生位置を特定し、一致しないと判別した場合に、前記シンドローム生成ステップにて生成した受信データのシンドロームと、前記論理演算ステップにて求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した２ビットの誤り発生位置を特定し、一致しないと判別した場合に、前記シンドローム生成ステップにて生成した前記ビット反転ステップにて１ビットが反転されたデータのシンドロームと、前記論理演算ステップにて求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した３ビットの誤り発生位置を特定する誤り特定ステップと、
前記誤り特定ステップにて特定した誤り発生位置のビットを反転して受信データの誤りを訂正する誤り訂正ステップとを備える、
ことを特徴とする。
【００１７】
また、この発明の第３の観点に係る記録媒体は、
コンピュータを、
所定の符号長を有する符号化が施された受信データに１ビットの誤りが発生した場合に対応する複数のシンドロームデータを予め記憶するシンドローム記憶手段と、
受信データのうちの１ビットを反転するビット反転手段と、
受信データのシンドロームと、前記ビット反転手段により１ビットが反転されたデータのシンドロームとを生成するシンドローム生成手段と、
前記シンドローム記憶手段に記憶されている２つのシンドロームデータの排他的論理和を求める論理演算手段と、
前記シンドローム生成手段により生成された受信データのシンドロームと、前記シンドローム記憶手段に記憶されている複数のシンドロームデータのうちのいずれか１つとが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した１ビットの誤り発生位置を特定し、一致しないと判別した場合に、前記シンドローム生成手段により生成された受信データのシンドロームと、前記論理演算手段が求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した２ビットの誤り発生位置を特定し、一致しないと判別した場合に、前記シンドローム生成手段が前記ビット反転手段により１ビットが反転されたデータから生成したシンドロームと、前記論理演算手段が求めた２つのシンドロームデータの排他的論理和とが一致するか否かを判別し、一致すると判別した場合に、受信データに発生した３ビットの誤り発生位置を特定する誤り特定手段と、
前記誤り特定手段により特定された誤り発生位置のビットを反転して受信データの誤りを訂正する誤り訂正手段と、
を備える誤り訂正装置として機能させるプログラムを記録し、コンピュータ読み取り可能であることを特徴とする。
【００１８】
【発明の実施の形態】
以下に、図面を参照して、この発明の実施の形態に係る誤り訂正装置について詳細に説明する。
【００１９】
図１は、この発明の実施の形態に係る誤り訂正装置１００の論理的構成を示すブロック図である。
この誤り訂正装置１００は、例えばＲＯＭ（Read Only Memory）及びＲＡＭ（Random Access Memory）等を備えたマイクロプロセッサが所定の処理プログラムを実行することにより実現され、図１に示すように、受信データ記憶部１０と、テーブルデータ記憶部１１と、データ合成処理部１２と、シンドローム生成処理部１３と、誤り検出処理部１４と、誤り訂正処理部１５と、ビット反転処理部１６とを備えている。
【００２０】
受信データ記憶部１０は、送信元からの受信データを一時的に記憶するためのものである。例えば受信データ記憶部１０は、Golay符号（２３，１２）により符号化された受信データを、符号ブロック単位で、シンドローム生成処理部１３や誤り訂正処理部１５、ビット反転処理部１６による読み出し可能に記憶する。
【００２１】
テーブルデータ記憶部１１は、例えば符号長が２３ビットで、且つ情報ビットが１２ビットのGolay符号（２３，１２）におけるシンドロームを予め記憶するためのものである。なお、Golay符号（２３，１２）のシンドロームは、受信データにおける誤り発生位置を特定するための１２ビットのデータである。
ここで、テーブルデータ記憶部１１は、受信データに１ビットの誤りが発生した場合にシンドローム生成処理部１３が生成するシンドロームのパターンを示す複数のシンドロームデータを記憶している。すなわち、テーブルデータ記憶部１１は、２３ビットからなる受信データの第ｉビット（ｉ＝０，１，…，２２）に誤りが発生した場合にそれぞれ対応する２３通りのシンドロームデータＴｂ［ｉ］を記憶している。
【００２２】
データ合成処理部１２は、テーブルデータ記憶部１１に記憶されているシンドロームデータＴｂ［ｉ］のうちの２つの和（排他的論理和）を求めるためのものである。
ここで、受信データに２ビットの誤りが発生した場合には、シンドローム生成処理部１３が生成するシンドロームは、各誤り発生位置に１ビットの誤りが発生した場合に対応するシンドロームの和（排他的論理和）に等しくなる。すなわち、２３ビットからなる受信データの第ｊビットと第ｋビット（ｊ，ｋ＝０，１，…，２２）に誤りが発生した場合のシンドロームｓ１は、テーブルデータ記憶部１１に記憶されているシンドロームデータＴｂ［ｉ］と、数式１のような関係を有する。
【数１】
ｓ１＝Ｔｂ［ｊ］＋Ｔｂ［ｋ］
ここで、演算記号＋は、排他的論理和を取ることと同等である。
【００２３】
データ合成処理部１２により求められた２つのシンドロームデータ Ｔｂ［ｉ］の排他的論理和は、誤り検出処理部１４に送られ、シンドローム生成処理部１３との比較の対象となる。
【００２４】
シンドローム生成処理部１３は、受信データ記憶部１０に記憶されている受信データを読み出してシンドロームを生成するためのものである。より具体的には、シンドローム生成処理部１３は、例えば巡回シフトレジスタを実質的に含んだ演算処理部であり、Golay符号（２３，１２）の符号化に用いた生成多項式で受信データを除算した余りを求めることにより、シンドロームを生成する。
この際、シンドローム生成処理部１３は、生成したシンドロームが”０”である場合には、受信データに誤りがない旨を誤り訂正処理部１５に通知する。
【００２５】
さらに、シンドローム生成処理部１３は、誤り検出処理部１４の制御により、ビット反転処理部１６が受信データのうちの１ビットを反転したデータを受け、受信データ記憶部１０から読み出した受信データと同様にしてシンドロームを生成する。
シンドローム生成処理部１３は、生成したシンドロームを誤り検出処理部１４に送る。
【００２６】
誤り検出処理部１４は、シンドローム生成処理部１３により生成されたシンドロームをテーブルデータ記憶部１１に記憶されているシンドロームデータＴｂ［ｉ］と比較して誤り発生位置を特定するためのものである。
この際、誤り検出処理部１４は、テーブルデータ記憶部１１から読み出したシンドロームデータＴｂ［ｉ］と、シンドローム生成処理部１３から受けたシンドロームとが一致した場合には、１ビットの誤りが発生したとして、読み出したシンドロームデータＴｂ［ｉ］に対応する誤り発生位置を誤り訂正処理部１５に通知する。
【００２７】
また、誤り検出処理部１４は、テーブルデータ記憶部１１から読み出したシンドロームデータＴｂ［ｉ］と、シンドローム生成処理部１３により生成されたシンドロームとが一致しない場合には、データ合成処理部１２を制御して、テーブルデータ記憶部１１に記憶されているシンドロームデータＴｂ［ｉ］のうちの２つの和（排他的論理和）を求めさせる。この場合、誤り検出処理部１４は、データ合成処理部１２が求めたシンドロームデータＴｂ［ｉ］の和と、シンドローム生成処理部１３から受けたシンドロームとを比較することにより、２ビットの誤り発生位置を特定することができる。データ合成処理部１２が求めたシンドロームデータＴｂ［ｉ］の和と、シンドローム生成処理部１３から受けたシンドロームとが一致したことを検出すると、誤り検出処理部１４は、誤り訂正処理部１５に２ビットの誤り発生位置を通知する。
【００２８】
さらに、誤り検出処理部１４は、データ合成処理部１２が求めたシンドロームデータＴｂ［ｉ］の和と、シンドローム生成処理部１３から受けたシンドロームとが一致しない場合には、ビット反転処理部１６を制御して、受信データのうちの１ビットを反転させる。この場合、誤り検出処理部１４は、ビット反転処理部１６がビットを反転したデータを用いてシンドローム生成処理部１３が生成したシンドロームを受け、データ合成処理部１２が求めたシンドロームデータＴｂ［ｉ］の和と比較してビットの誤り発生位置を特定する。
【００２９】
誤り訂正処理部１５は、受信データ記憶部１０に記憶されている受信データを読み出し、誤り検出処理部１４から通知された誤り発生位置のビットを反転するなどの誤り訂正処理を実行するためのものである。
【００３０】
ビット反転処理部１６は、誤り検出処理部１４の制御に従って、受信データ記憶部１０に記憶されている受信データを読み出し、読み出した受信データのうちの１ビットを反転するためのものである。ビット反転処理部１６は、１ビットを反転した受信データをシンドローム生成処理部１３に送り、シンドロームの生成に供する。
【００３１】
以下に、この発明の実施の形態に係る誤り訂正装置１００の動作を説明する。
【００３２】
この誤り訂正装置１００は、送信元からのデータを受けると、受信データ記憶部１０に記憶して、図２のフローチャートに示す誤り訂正処理を実行する。
【００３３】
誤り訂正処理を開始すると、シンドローム生成処理部１３は、受信データ記憶部１０に記憶されている受信データからシンドロームを算出し（ステップＳ１）、算出したシンドロームが”０”であるか否かを判別する（ステップＳ２）。
【００３４】
シンドローム生成処理部１３は、算出したシンドロームが”０”であると判別すると（ステップＳ２にてＹＥＳ）、誤りが発生していないとして（ステップＳ３）、誤り訂正処理を終了する。
この場合、シンドローム生成処理部１３は、受信データに誤りが発生していない旨を誤り訂正処理部１５に通知する。誤り訂正処理部１５は、受信データに誤りが発生していない旨の通知を受けると、受信データ記憶部１０に記憶されている受信データを読み出して、そのまま出力することで、誤りのないデータを外部の機器に供給することができる。
【００３５】
一方、シンドローム生成処理部１３は、算出したシンドロームが”０”でないと判別すると（ステップＳ２にてＮＯ）、生成したシンドロームを誤り検出処理部１４に送る。
【００３６】
誤り検出処理部１４は、シンドローム生成処理部１３からシンドロームを受けると、テーブルデータ記憶部１１に記憶されているシンドロームデータＴｂ［ｉ］を読み出す。
この際、誤り検出処理部１４は、テーブルデータ記憶部１１に記憶されているシンドロームデータＴｂ［ｉ］を、添字ｉがインクリメント（又はデクリメント）する順に逐次読み出して、シンドローム生成処理部１３から受けたシンドロームと比較する（ステップＳ４）。
【００３７】
誤り検出処理部１４は、シンドローム生成処理部１３から受けたシンドロームがシンドロームデータＴｂ［ｉ］のうちのいずれかと一致したか否かを判別する（ステップＳ５）。
【００３８】
誤り検出処理部１４は、シンドローム生成処理部１３から受けたシンドロームがシンドロームデータＴｂ［ｉ］のうちのいずれかと一致したと判別すると（ステップＳ５にてＹＥＳ）、受信データに１ビットの誤りが発生したとして（ステップＳ６）、誤り訂正処理部１５に、その誤りを訂正するための処理を実行させる（ステップＳ７）。
【００３９】
この際、誤り検出処理部１４は、例えばシンドローム生成処理部１３から受けたシンドロームと一致したシンドロームデータＴｂ［ｉ］の添字ｉを特定することにより、受信データにおける１ビットの誤り発生位置を特定し、誤り訂正処理部１５に通知する。
誤り訂正処理部１５は、受信データ記憶部１０に記憶されている受信データを読み出し、誤り検出処理部１４が特定した誤り発生位置のビットを反転するなどの誤り訂正処理を実行し、外部の機器に出力する。
これにより、受信データに生じた１ビットの誤りを適切に訂正して出力することができる。
【００４０】
一方、誤り検出処理部１４は、シンドローム生成処理部１３から受けたシンドロームがシンドロームデータＴｂ［ｉ］のうちのいずれにも一致しないと判別すると（ステップＳ５にてＮＯ）、データ合成処理部１２にシンドロームデータＴｂ［ｉ］の和（排他的論理和）を計算させる。
この際、誤り検出処理部１４は、データ合成処理部１２を制御して、テーブルデータ記憶部１１に記憶されているシンドロームデータＴｂ［ｉ］で添字ｉが異なる２つのデータの和（排他的論理和）を計算させる。また、誤り検出処理部１４は、２つのシンドロームデータＴｂ［ｉ］で添字ｉが異なる全ての組み合わせについての和（排他的論理和）を計算させる。
データ合成処理部１２は、誤り検出処理部１４の制御に従って、テーブルデータ記憶部１１に記憶されたシンドロームデータＴｂ［ｉ］を用いた、２３Ｃ２＝２５３通り（Golay符号（２３，１２）の場合）の排他的論理和を求める論理演算処理を実行する。
【００４１】
誤り検出処理部１４は、データ合成処理部１２が計算したシンドロームデータＴｂ［ｉ］の和を、シンドローム生成処理部１３から受けたシンドロームと比較する（ステップＳ８）。
【００４２】
誤り検出処理部１４は、データ合成処理部１２の計算により得られたデータのうちのいずれか１つがシンドローム生成処理部１３から受けたシンドロームと一致したか否かを判別する（ステップＳ９）。
【００４３】
誤り検出処理部１４は、シンドロームデータＴｂ［ｉ］の和のうちのいずれかがシンドローム生成処理部１３から受けたシンドロームと一致したと判別すると（ステップＳ９にてＹＥＳ）、受信データに２ビットの誤りが発生したとして（ステップＳ１０）、誤り訂正処理部１５に、その誤りを訂正するための処理を実行させる（ステップＳ７）。
【００４４】
この際、誤り検出処理部１４は、例えばデータ合成処理部１２が排他的論理和を計算した２つのシンドロームデータＴｂ［ｉ］の添字ｉを特定することにより、受信データにおける２ビットの誤り発生位置を特定し、誤り訂正処理部１５に通知する。
誤り訂正処理部１５は、受信データ記憶部１０に記憶されている受信データを読み出し、誤り検出処理部１４が特定した誤り発生位置のビットを反転させるなどの誤り訂正処理を実行し、得られたデータを外部の機器に出力する。
これにより、受信データに生じた２ビットの誤りを適切に訂正して出力することができる。
【００４５】
一方、誤り検出処理部１４は、シンドロームデータＴｂ［ｉ］の和の全てがシンドローム生成処理部１３から受けたシンドロームと一致しないと判別すると（ステップＳ９にてＮＯ）、ビット反転処理部１６を制御して、受信データのうちの１ビットだけを反転させる（ステップＳ１１）。
ビット反転処理部１６は、誤り検出処理部１４の制御に従って、受信データ記憶部１０に記憶されている受信データを読み出し、第ｎビット（ｎ＝０，１，…，２２）のみを反転させてシンドローム生成処理部１３に送る。
シンドローム生成処理部１３は、ビット反転処理部１６から受けたデータからシンドロームを再び算出して（ステップＳ１２）、誤り検出処理部１４に送る。
【００４６】
誤り検出処理部１４は、データ合成処理部１２が計算したシンドロームデータＴｂ［ｉ］の和（排他的論理和）を、シンドローム生成処理部１３から受けたシンドロームと比較する（ステップＳ１３）。
ここで、シンドローム生成処理部１３がシンドロームを求めたデータは、ビット反転処理部１６により受信データのうちの１つのビットだけが反転されたデータである。従って、受信データ記憶部１０に記憶されている受信データに３ビットの誤りが発生した場合には、３ビットの誤り発生位置のうちのいずれか１ビットが反転されると、２ビットの誤りだけが残存することになる。この際、シンドローム生成処理部１３により生成されたシンドロームは、データ合成処理部１２が計算したシンドロームデータＴｂ［ｉ］の和（排他的論理和）のうちのいずれかと一致する。
【００４７】
誤り検出処理部１４は、シンドローム生成処理部１３から受けたシンドロームがデータ合成処理部１２の計算により得られたデータ（シンドロームデータ）のうちのいずれかと一致したか否かを判別する（ステップＳ１４）。
【００４８】
誤り検出処理部１４は、シンドローム生成処理部１３から受けたシンドロームがシンドロームデータＴｂ［ｉ］の和のうちのいずれかと一致したと判別すると（ステップＳ１４にてＹＥＳ）、受信データに３ビットの誤りが発生したとして（ステップＳ１５）、誤り訂正処理部１５に、その誤りを訂正するための処理を実行させる（ステップＳ７）。
【００４９】
この際、誤り検出処理部１４は、例えばデータ合成処理部１２が排他的論理和を計算した２つのシンドロームデータＴｂ［ｉ］の添字ｉ及びビット反転処理部１６が反転させたビットを示す添字ｎを特定することにより、受信データにおける３ビットの誤り発生位置を特定し、誤り訂正処理部１５に通知する。
誤り訂正処理部１５は、受信データ記憶部１０に記憶されている受信データを読み出し、誤り検出処理部１４が特定した誤り発生位置のビットを反転させるなどの誤り訂正処理を実行し、得られたデータを外部の機器に出力する。
これにより、受信データに生じた３ビットの誤りを適切に訂正して出力することができる。
【００５０】
一方、誤り検出処理部１４は、シンドローム生成処理部１３から受けたシンドロームがシンドロームデータＴｂ［ｉ］の和の全てと一致しないと判別すると（ステップＳ１４にてＮＯ）、受信データの全ビットについて、ビット反転処理部１６により反転されて誤りの検出が行われたか否かを判別する（ステップＳ１６）。
【００５１】
誤り検出処理部１４は、反転して誤りの検出が行われていないビットがあると判別すると（ステップＳ１６にてＮＯ）、ビット反転処理部１６を制御して次のビット（例えば、第ｎ＋１ビット）を反転させ（ステップＳ１７）、処理を上記ステップＳ１２にリターンする。
ビット反転処理部１６は、誤り検出処理部１４の制御に従って、受信データ記憶部１０から読み出したデータのうちで反転するビットの位置を移動させて、受信データのうちの１ビットを反転したデータを逐次生成し、３ビットの誤り発生位置を特定可能とする。
【００５２】
一方、誤り検出処理部１４は、受信データの全てのビットについて、ビット反転処理部１６により反転されて誤りの検出が行われたと判別すると（ステップＳ１６にてＹＥＳ）、３ビットより多くの誤りが発生したため誤り訂正が不可能であるとして（ステップＳ１８）、誤り訂正処理を終了する。
【００５３】
以上説明したように、この発明によれば、テーブルデータ記憶部１１は、受信データの１ビットに誤りが発生した場合に対応するシンドロームデータＴｂ［ｉ］を予め記憶している。誤り検出処理部１４は、テーブルデータ記憶部１１に記憶されているシンドロームデータＴｂ［ｉ］と、シンドローム生成処理部１３により生成されたシンドロームとを比較し、両者が一致するか否かを判別して、１ビットの誤り発生位置を特定することができる。また、誤り検出処理部１４は、データ合成処理部１２の計算により求められたシンドロームデータＴｂ［ｉ］の排他的論理和と、シンドローム生成処理部１３により生成されたシンドロームとを比較し、両者が一致するか否かを判別して、２ビットの誤り発生位置を特定することができる。この際、ビット反転処理部１６により受信データのうちの１ビットだけを反転させたデータからシンドロームを生成し、データ合成処理部１２の計算により求められたシンドロームデータＴｂ［ｉ］の排他的論理和と比較して、両者が一致するか否かを判別することで、３ビットの誤り発生位置を特定することができる。
【００５４】
このように、テーブルデータ記憶部１１に１ビットの誤りに対応したシンドロームデータＴｂ［ｉ］だけを予め記憶しておくことで、３ビットまでの誤りを訂正することができる。
これにより、簡単な構成で、適切に受信データの誤りを訂正することができる。
【００５５】
この発明は、上記実施の形態に限定されず、さまざまな変更及び応用が可能である。
例えば、受信データはGolay符号（２３，１２）に限定されず、ＢＣＨ符号（１５，５）やＢＣＨ（３１，１６）といった、３ビット程度の誤り訂正可能な符号化が施されていてもよい。
この場合、符号化方式に応じた受信データの１ビット誤りに対応したシンドロームデータをテーブルデータ記憶部１１に記憶しておき、このシンドロームデータを利用することで、３ビットまでの誤りを適切に訂正することができる。
【００５６】
この発明の誤り訂正装置は、専用の装置を必要とせず、通常の誤り訂正装置として機能するコンピュータを用いても実現可能である。すなわち、誤り訂正装置として機能するコンピュータに上述の各処理を実行させるためのプログラムを、記録媒体（フロッピーディスク、ＣＤ−ＲＯＭ、ＭＯ、ＲＯＭ等）に記録して配布し、これをコンピュータにインストールして実行させることにより、この発明の誤り訂正装置として機能させることができる。インストールによって、当該プログラムは、コンピュータ内のハードディスク、ＥＥＰＲＯＭ等の媒体に記録されて、実行に供される。
【００５７】
ここで、プログラムを配布する方法は、記録媒体によるものに限らず、例えば、インターネット等の通信ネットワークを使用するものであってもよい。この場合には、例えば、インターネット上に設けたＦＴＰ（File Transfer Protocol）サーバに当該プログラムを登録し、ＦＴＰクライアントにネットワークを介して配信すればよい。また、通信ネットワーク上の電子掲示板（ＢＢＳ；Bulletin Board System）等に当該プログラムを登録し、これをネットワークを介して配信してもよい。
【００５８】
また、この発明の誤り訂正装置は、マイクロプロセッサに処理プログラムを実行させて実現する場合に限定されず、ハードワイアード論理の回路を構成することによっても実現可能である。
【００５９】
【発明の効果】
以上の説明のように、この発明によれば、１ビットの誤りに対応したシンドロームデータを記憶しておくだけで、３ビットの誤り訂正を行うことができ、簡単な構成で、適切に受信データの誤りを訂正することができる。
【図面の簡単な説明】
【図１】この発明の実施の形態に係る誤り訂正装置の論理的構成を示すブロック図である。
【図２】誤り訂正処理を説明するためのフローチャートである。
【図３】従来の技術として考えられる誤り訂正方法について説明するためのフローチャートである。
【図４】従来の技術として考えられる誤り訂正方法について説明するためのフローチャートである。
【図５】従来の技術として考えられる誤り訂正方法について説明するためのフローチャートである。
【符号の説明】
１０    受信データ記憶部
１１    テーブルデータ記憶部
１２    データ合成処理部
１３    シンドローム生成処理部
１４    誤り検出処理部
１５    誤り訂正処理部
１６    ビット反転処理部
１００    誤り訂正装置
【図１】
0003661089.tif 000002
【図２】
0003661089.tif 000003
【図３】
0003661089.tif 000004
【図４】
0003661089.tif 000005
【図５】
0003661089.tif 000006