JPS62248314A - 誤り訂正符号の復号方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、誤り訂正符号の復号方法に関し、特に、ラン
ダム誤り、バースト誤り共に強力な訂正が可能な誤り訂
正符号の復号方法に関する。

〔発明の概要〕

本発明は、符号間最小距離がｄの誤り訂正符号の復号方
法において、連続するエラーシンボルより成るエラーブ
ロックの個数をｉ、これらのエラーブロックのうちの第
ｊ番目のブロックのエラーシンボル数をａｊ　とすると
き、 ｊ＋Σａよ≦ｄ−ま ただしｊ＝１，２・・・ｉ の不等式を満たす範囲で誤り訂正操作を行うことにより
、ランダム誤り及びバースト誤りの双方に対して強力な
誤り訂正を可能とするものである。

〔従来の技術〕

ディジタルデータのにシンボルに対して、所謂リード・
ソロモン（Ｒｅｅｄ　５ｏｌｏａ＋ｏｎ）符号等の最適
誤り訂正符号を用いた符号化が施されることにょリ、（
ｎ−ｋ）シンボル（ｎＳｋは正の整数）の検査シンボル
が付加されて成る符号系においては、符号間最小距離ｄ
が（ｎ−に＋１＞となっている。

この距＠ｄと、位置のわかっていない誤りを検出し訂正
する誤り検出訂正可能なシンボル数を及び位置のわかっ
ている誤りを訂正する誤り消失訂正（イレージヤ訂正）
可能なシンボル数Ｓとの間には、 ｄ−１≧２ｔ＋ｓ の関係が成立することが一般に知られている。

たとえば、ｋ−２００、ｎ−２１６のリード・ソロモン
符号における検査シンボル（チェックシンボル）の個数
は１６であり、上記距離ｄは１７となるから、最大８シ
ンボルまでの誤り検出訂正が可能であり、又は、最大１
６シンボルまでの誤り消失訂正が可能である。

〔発明が解決しようとする問題点〕

ところで、光磁気ディスク等にデータを記録する場合に
おいて、例えば第２図に示すような２次元配列のデータ
マトリクスをＲＡＭ等のメモリ上に展開し、一方向（図
中横方向）に上記リード・ソロモン符号等による符合化
を行い、これと直行する方向（図中縦方向）に順次読み
出してディスク上に書き込むようなことが行われている
。この第２図の例においては、ディスクの１セクタに対
してオリジナルデータ（冗長データを含まない元のデー
タ）５１２バイトが割り当てられるものとして、図中横
方向に１２８バイトで縦方向に４プロンク（４段）の計
５１２バイトのオリジナルデータによる２次元配列を構
成している。この５１２バイトのデータに対して、４バ
イトのＣＲＣ符号を付加し、さらに上記各ブロックに対
して１６バイト（上記１セクタ当たりでは６４バイト）
のリード・ソロモン符号等によるチェックバイトを付加
している。従って、上記各ブロックのデータ（ｌブロッ
ク１４５バイト）に対して、８バイトまでの誤り検出訂
正が可能となっている。なお、図中の数字はデータ書き
込み順序を示す。

このような記録フォーマットに基づいてデータが記録さ
れたディスクに傷や塵埃の付着等が生じた場合には、連
続的な誤り、所謂バーストエラーが発生し、上記１つの
ブロックの１４５バイトのデータに対して９バイト以上
の誤りが生ずることがある。これは、ディスク上では連
続する３６バイト以上の誤りに対応し、光磁気ディスク
のような極めて高い記録密度の媒体にあっては、僅かの
傷や微小な塵埃でもこの程度のバーストエラーの原因と
なり得るものである。このようなｌブロックに対し９バ
イト以上の、すなわち上記誤り検出訂正能力を越えた誤
りが生ずると、誤り訂正が不可能となってしまう。

ここで、バーストエラーのように誤りが連続している場
合には、連続するエラーバイトの先頭位置等の基準位置
を検出することで全てのエラーバイトの位置を略決定で
きるが、バーストエラーとランダムエラーとが同時に生
じている場合には、上記連続する複数のエラーバイトと
、それぞれ孤立したエラーバイトとが存在することにな
る。

本発明はこのような実情に鑑みてなされたものであり、
ランダムエラーと、連続的な誤り（所謂バーストエラー
）の両方が同時に生じている場合でも、強力な誤り訂正
が可能な、誤り訂正符号の復号方法の提供を目的とする
。

〔問題点を解決するための手段〕

本発明に係る誤り訂正符号の復号方法は、上述の問題点
を解決するために、ディジタルデータに対して誤り訂正
符号の符号化が施されることにより符号間最小距離がｄ
とされた誤り訂正符号の復号方法において、１個のエラ
ーシンボルあるいは２個以上の連続するエラーシンボル
を有して成るエラーブロックの個数を１２これらのエラ
ープロッタのうちの第ｊ番目（１≦ｊ≦ｉ）のブロック
内のエラーシンボルの個数をａ、とするとき、直 の不等式を満たす範囲で誤り訂正操作を行うことを特徴
としている。

〔作　用〕 −殻に、誤り訂正符号系の符号間最小距離がｄのときの
誤り検出訂正可能なシンボル数ｔと誤り消失訂正（イレ
ージヤ訂正）可能なシンボル数Ｓとの間には、 ｄ−１≧２ｔ＋ｓ の不等式が成立するわけであるが、これは、を個のシン
ボルの位置を検出し、（ｔ＋ｓ）個のシンボルの誤り消
失訂正（イレージヤ訂正）を行っているとも考えられる
。ここで、連続するエラーシンボル群より成るエラーブ
ロックについては、該エラーブロックの基準位置（例え
ばブロック内の先頭シンボル位置）がわかれば当該エラ
ーブロック内の全てのエラーシンボル位置が決定される
から、例えばｉ個のエラーブロックについての各基準位
置を検出することで、全てのエラーブロック内の全ての
エラーシンボルに対して上記イレージヤ訂正が可能にな
る。すなわち、 ｉ＋Σａｊ≦ｄ−１ ｊ＊ｌ の条件を満足する範囲で、ｉ個のエラーブロックの各基
準位置を検出し、これらのエラーブロック内の全エラー
シンボルの個数Σａ１をイレージヤ訂正することが可能
となる。

ここで、上記１つのエラーブロックを構成する２個以上
の連続するエラーシンボルについては、現実に１シンボ
ルずつ連続している必要はなく、インターリーブ等との
関連で所定の規則の下に連鎖している場合も含むもので
あり、換言すれば、１つのエラーブロックは、エラーブ
ロックの基準位置（例えばブロック内の先頭シンボル位
置）さえ検出すれば、当該ブロック内の全てのエラーシ
ンボルの位置が自動的に決定されるようなシンボル群に
より構成されている。

〔実施例〕

本発明に係る誤り訂正符号の復号方法を説明するに先立
ち、従来における通常の誤り検出訂正について説明する
。

ここで−例として、第１図に示すようなにシンボルの情
報データに対してｎ−にシンボルの検査シンボル（チェ
ックシンボル）が付加されて成るようなガロア体ＧＦ（
ｑ’）上のリード・ソロモン符号Ｃ（ｎ、ｋ）について
考えると、原始光をαとするとき、生成多項式は、 （ｘ−１）　（Ｘ−α）（トαつ・・・・（トαＬ−１
）ただし、１寓ｎ−に となる、このとき、符号間最小距離ｄはｌ＋１であり、
誤り検出訂正可能なシンボル数ｔの最大値ｔ、Ｉは、 ｔ＊　−（Ｊ／２）−（（ｄ−１）／２）ただし〔〕は
所所謂ガラの記号であり、（ｘ）は実数Ｘを越えない最
大の整数を示すとなる。これは、シンドロームＳｏ、Ｓ
＋　〜３１−１について２個の連立方程式が成立し、元
の数が、誤り位置ｔ、個、大きさｔＨ個となることから
も自明である。

従来においては、誤り訂正に先立って誤り位置（イレー
ジヤのロケ−シラン）が検出されていない限り、上記ｔ
７個までの誤り訂正が可能であるに過ぎず、このｔ０個
より多くの誤りが存在する場合には訂正不可能となって
いた。

これに対して本発明は、上記ｔＮ個より多くの誤りが存
在する場合であっても、見かけ上の誤り検出訂正を可能
とするものである。これは、誤りが比較的多い場合には
、所謂バーストエラーが生じている可能性が高いことを
考慮し、２個以上の連続する誤り（エラーシンボル）を
１つのエラーブロックとして扱うようにしたものであり
、このエラーブロックについては、１つの基準位置（例
えばブロック内の先頭シンボル位置）を検出することに
よって当該ブロック内の全てのエラーシンボルの位置を
決定し、これらの位置決定されたエラーシンボルについ
て誤り消失訂正（イレージヤ訂正）を行い得るようにし
ている０例えば、ｉ個のエラーブロックの上記各基準位
置をそれぞれ検出する場合に、第ｊ番目（１≦３ｓ％）
のエラーブロック内のエラーシンボルの個数をａＪとす
るとき、全てのエラーブロックについての全てのエラー
シンボルの総個数は、 ａｌ＋ａ、十畢拳・＋ａ！零ΣａＪ ｊ＋１ となり、これらのエラーシンボルに対しては上記イレー
ジヤ訂正によって誤り訂正が可能であるから、ｉ個の位
置検出と、Σａ、個のイレージヤ訂正によって、見かけ
上、Σａｊ個のシンボルの誤り検出訂正が行えることに
なる。この場合において、上記エラーブロックの個数ｉ
及び全エラーシンボルの総個数Σａｊと、上記符号間最
小距離ｄとの間には、 ｉ＋Σａ４　≦ｄ−１ の関係が成立すればよい。例えば、上記距離ｄが１７の
場合に、従来の誤り検出訂正可能なシンボル数ｔの最大
値１Ｍが８であるのに対し、全てのエラーシンボルが連
続しているものとする（エラーブロックの個数を１個と
する）ときには、ｉ＝１となって１５個までのエラーシ
ンボルを訂正できる。また、エラーブロックの個数を２
個としたときには、１４個までのエラーシンボルを訂正
でき、例えば１個の独立したエラーシンボルと１３個の
連続するエラーシンボルとを見かけ上誤り検出訂正する
ことができる。この他、上記不等式を満足する範囲でエ
ラーブロック数ｉを任意に設定できるが、現実のディジ
タル演算処理を考慮すれば、ｉは２程度が適当である。

ここで、１つのエラーブロックを構成する上記連続する
誤り　（エラーシンボル）としては、例えば前記第２図
のような記録フォーマットの場合では、１つのブロック
内において略ｊシンボルずつ連続する誤りとなって現れ
るから、先頭エラーシンボル位置Ｘがわかれば順次ｘ＋
１．ｘ＋２　　・・・の位置のシンボルも誤っているこ
とが推定できる。この他、インターリーブ等の関係で、
例えば２シンボルおきとか３シンボルおき等で誤りが生
ずることも考えられ、このような場合も、本発明の上記
エラーブロックを構成する連続するエラーシンボルの概
念に含まれるものである。

次に、上記バーストエラー発生時の連続する複数個のエ
ラーシンボルより成るエラーブロックに対する誤り訂正
についての具体例を説明する。ここで、説明を簡略化す
るために、エラーブロック内の連続するエラーシンボル
の個数を３とした場合の連続誤り訂正を行うものとする
。

このときのエラーブロック内のエラーシンボル群ｔｅｌ
の内の先頭位置のシンボルを８８とし、連続する３個の
シンボル’３　Ｘｌ　８　ｍｌ＋　ｅ　Ｔｔ＊Ｎが誤っ
ているものとするときには、４個のシンドロームＳ０、
Ｓ　＋、Ｓ　ｔ、　Ｓ　ｓについて、Ｓ６＝　　　ｅ、
＋　　　　ｅＸ◆、＋　　　　ｅｘｉｔＳ　　Ｈ＝　　
（Ｘ　Ｘｅ　Ｋ　＋　　　１１　”’　　ｅ　　ｇ＋１
　　＋　　　Ｏｆ　”令”１１ｘ＊意Ｓ、＝ａ”ｅ、＋
ｃｘ”＋″ｅ　ＸＩ＋　＋　α””　ｅ　ｗｅｔＳ　ｚ
−（Ｉｔ　”　＠　Ｘ　＋　（Ｘ　””　６　ｇ＋　１
　＋　（Ｘ　””　ｅ　ｚ６ｇの連立方程式が成立する
ことになる。従って、この連立方程式を解くことによっ
て得られるｃｔ””　（α”’（αＸｓｏ＋ｓ＋）＋（
α”Ｓ１＋１）１＋αｘ＋＋（αＸＳ＋＋Ｓｇ）＋（α
”Ｓ１＋５３）＝０の式を満たすような４個のシンドロ
ームＳｏ、Ｓｔ、Ｓｔ、Ｓｓが存在すれば、上記３個の
連続するシンボルｅ　Ｎ＋　ｅＥ＋Ｉｎ　ｅＸ４！が１
つのエラーブロックを構成していることがわかり、後は
誤り消失訂正（イレージヤ訂正）処理によって、上記連
続する３個のエラーシンボルｅＸ＋　ｅＸ＋ｌ＋　ｅ１
１４２を訂正することができる。

従って、ランダムエラーとバーストエラーとが共存して
いる場合には、バーストエラーによって生じた連続する
複数シンボルの誤りについての各シンボル位置検出が、
１個の基準位置検出で済むことになり、上記誤り検出訂
正可能なシンボル数ｔの最大値ｔ０よりも多くの個数ま
での（見かけ上の）誤り検出訂正を行うことができる。

なお本発明は、上述の例のみに限定されるものではなく
、例えば、誤り訂正符号としては、上記リード・ソロモ
ン符号に限定されず、所謂ＢＣＨ符号等にも通用でき、
二系列以上の多重誤り訂正符号化が施された場合にも容
易に適用できる。また、誤り訂正符号系列の情報シンボ
ル数や検査シンボル数等は上述の例に限定されないこと
は勿論である。さらに、上記誤り検出訂正を行うに先立
って、従来と同様な通常の（ランダムエラーに対する）
誤り検出訂正を行い、この通常の誤り検出訂正が不可能
とされた場合に、ランダムエラー及びバーストエラーに
より生ずる上記エラーブロックに対する上記見かけ上の
誤り検出訂正を行うようにしてもよい。

〔発明の効果〕

本発明の誤り訂正符号の復号方法によれば、ランダムエ
ラーにより生じた１エラーシンボルより成るエラーブロ
ックと、ゲーストエラーにより生じた２以上のエラーシ
ンボルより成るエラーブロックのいずれのエラーブロッ
クに対しても、それぞれ１個ずつの基準位置を検出する
だけで、全てのエラーシンボルに対するイレージヤ訂正
操作により誤り訂正を可能とし、従来の誤り検出訂正可
能なシンボル数を越えた個数の符号誤りが生じた場合で
も、最大限では（エラーブロックの個数を１とした場合
では）略誤り消失訂正（イレージヤ訂正）可能な個数程
度までの誤りについて、見かけ上誤り検出訂正すること
が可能となり、ランダムエラーと同時にバーストエラー
も生じ易い信号伝送系（記録再生系も含む）に対して強
力な誤り訂正を実現することができる。

【図面の簡単な説明】

第１図は本発明の説明に供する誤り訂正符号の一例を示
す図、第２図は光磁気ディスクにおけるデータ記録フォ
ーマットの一例を説明するための図である。

Claims (1)

1. 【特許請求の範囲】 ディジタルデータに対して誤り訂正符号の符号化が施さ
   れることにより符号間最小距離がｄとされた誤り訂正符
   号の復号方法において、 １個のエラーシンボルあるいは２個以上の連続するエラ
   ーシンボルより成るエラーブロックの個数をｉ、これら
   のエラーブロックのうちの第ｊ番目（１≦ｊ≦ｉ）のエ
   ラーブロックのエラーシンボル数をａ＿ｊとするとき、 ｉ＋Σ＾ｉ＿ｊ＿＝＿１ａ＿ｊ≦ｄ−１ の不等式を満たす範囲で誤り訂正操作を行うことを特徴
   とする誤り訂正符号の復号方法。