JPS62164319A - 誤り訂正方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、ディジタル信号の伝送又はディジタル信号記
録再生装置の誤り訂正方法に関する。

従来の技術 まず、誤り訂正符号としてよく用いられるリードソロモ
ン符号について説明する。誤り訂正符号を記述する場合
、ガロア体ＧＦは既約多項式によるベクトル表現、ある
いは巡回群による表現がある。Ｇ　Ｆ　（２＋上でのｍ
次の既約多項式Ｆ　ｆｘｌを考えた場合　＠　Ｑ　１１
と′１”の元しか存在しないＣＦ　（２＋上ではＦ　（
ｘｌは根を持たないので、今、Ｆ　（ｘ）　＝　ｏを満
足する根αを考える。このとき零元を含むαのべき乗で
表わされる２ｍ　個の相異なる元Ｏ１α。

α２．・・・・・・αｍ−１は拡大ＧＦ（２ｍ）を構成
する。

ＣＦ（２”）ノ元１ｄ　１．　ａ＝　（り　、　ｃｔ２
＝　（ｘ２１　　、　・−−−−−αｍ−”　＝　［ｘ
）　　の線形結合で表現でき次式となる。

ａｏ＋　ａ、［ｘｌ　＋ａ２（ｘ２）＋・・・・・・＋
ａｍ−，（ｘ　　　） あるいは（”ｍ−１’　　ａｍ−２’・・・・・・ａ２
．　ａ、　、　ａｏ）ここで各係数は（、Ｆ　（２１に
属する。

他の表現は巡回群を用いるもので、ＧＦ（２ｍ）から零
元を除く残りの元が大きさ２ｒｒ＋−１の乗法群となる
ことを利用する。従って Ｑ、１（＝α２ｍ−１）、α、α２．α３．・・・・・
・、α２ｍ−２となる。リードソロモン符号の一例とし
て、１シンボルをｍビットとしｎシンボルで１ブロツク
を構成する場合、下記の検査行列Ｈに基づいてに個の検
査シンボルを発生する。

以下、検査シンボルとして４個（Ｋ＝４）の場合を例に
とる。このとき、検査行列Ｈは 受信側での列ベクトルＶとすると △ Ｖ：Ｖ＋Ｅ ただし、Ｅは伝送中に発生した誤りのベクトル表示であ
り、各要素はＷｉ＝Ｗｉ＋ｅ□（ただしｅ。

はエラーパターン）で表わされる。従って、受信側で生
成されるシンドロームｓ。、　Ｓ、　　、　Ｓ２゜Ｓ３
は次式で示される。

［：　Ｓｏ、　Ｓ、、　Ｓ２．　Ｓ３］Ｔ＝＝Ｈ−Ｖ”
ここでＴは転置を示す記号である。この誤り訂正符号は
１ブロツク内の２シンボル誤りまでのエラー訂正が可能
であり、誤り位置が判っていれば４シンボル誤りまで訂
正することができる。

上述のリードソロモン符号にょる復号方法は以下に示す
ステップで行なわれる。

（ａｌ　　受信信号よりシンドロームＳ。、　Ｓｌ、　
Ｓ２．　Ｓ３を求める。

（ｂ）１ブロツク内の誤りシンボルの個数を判別する。

（Ｃ）２個以下の誤りの場合、誤り位置が求められる。

（ｄ）　　誤りパターンを求めて訂正を行なう。

（ａｌのステップでは前述のＨ−９Ｔの演算を行なうこ
とによりシンドロームを求めることができる。郵）以降
のステップについては以下 〔１〕エラーがない場合 ５ｏ＝Ｓ１＝Ｓ２＝Ｓ３＝０ 〔２〕１７ンボルエラーの場合 エラーパターンをｅｉとすると、Ｓｏ　＝ｅｉ　。

Ｓ　＝ａ’ｅ−、Ｓ　＝ｔｘ２ｅ、　、　Ｓ、＝　ｅｘ
　　ｅｉよりＳｏ）Ｏ，Ｓ、（０、ｓ、、）ｏ　、　ｓ
３）。

が成立する。このときα１より誤り位置ｉが小さい。こ
のときのシンドロームＳ。がエラーパターンｅｉそのも
のとなる。

〔３〕２シンボルエラーの場合 エラーパターンを６　ｓ　＊　＠　］とすると上式を変
形して 従って ａ’　（ｔｘ’ｓ　＋Ｓ　）＝　ｃｔ”ｓ　＋Ｓａ’　
（ｔｘ’ｓ　＋Ｓ　）　＝　ａ’ｓ　＋ｓカ成立すれば
２シンボルエラーと判定され、誤り位置ｌ、ｊが分かる
。このときのエラーパターンは よシ求められ、エラー訂正が可能となる。

以上の条件を満たさない場合は３シンボル以上の誤りと
判断され、誤り位置があらかじめ判っていなければ訂正
することはできない。

この復号後、各ワードに１対１に対応したエラーポイン
タ信号（誤りの有無を示す）を発生する。

訂正能力を向上さす手段として、異なるデータ信号系列
より生成した２組の誤り訂正符号を用いて順次復号する
方法が多くとられている。この時、初段の復号で得られ
たエラーポインタ信号を次段の復号の際に参照して誤り
の誤検出を防止して、かつ訂正能力の向上を図っている
。このような誤り訂正方法としては例えば、特開昭５７
−２４Ｌ１４３号公報に示されている。以下そＱ訂正ア
ルゴリズムについて説明する。誤り訂正符号としては前
述したリードソロモン符号（２シンボルまでの誤りを訂
正でき、誤りの位置が判っていれば４シンボルまで訂正
可能なもの）を使用する。初段の復号では、誤りの誤検
出、誤訂正を考慮し、１シンボル誤りまでの訂正を行な
うようにし、１つのブロック内において２シンボル以上
のエラーがあると判断した場合にはそのブロック内のす
べてのシンボルに対応したエラーポインタをエラーを示
す状態（例えば′Ｈ”レベル）にし、それ以外の時はエ
ラーなしを示す状態（例えば°゛Ｌ”レベル）にし、そ
の結果を次段の復号器に送る。次段の復号は、第４図を
参照して説明する。まずシンドロームが計算され、１ブ
ロツク内のシンボルに対応するエラーポインタを調べＩ
Ｉ　Ｈ”の総数Ｎｐが数えられる。ところで、次段の復
号での各ブロックの信号は初段の復号後、信号の並び換
え（インターリーブ処理）を行ない次段の復号のために
ブロックを再構成したものである。シンドロームから１
ブロツク内のエラーの個数が判定された後、（１）エラ
ーなしと判断された場合 Ｎｐと２１　　との大小関係によシ第４図人の操作がな
される。ここで、２．はかなり大きく例えば１ブロツク
２８シンボルの場合で１４、（２）１シンボルエラーと
判断した場合Ｓ１゜ 一αｌ　よりエラーロケーションｉを求め、Ｏ エラーロケーションｉのポインタを調べ、エラーの状態
（ｉ＝Ｅｉ）であれば次にＮｐ≦２２かどうかを調べ第
４図Ｂの操作がなされる。エラーロケーションｉとポイ
ンタの状態が異なれば（１％　Ｅｌ）第４図Ｃの操作が
なされる。

以下、第４図のフローチャートに示すように１シンボル
エラー、２シンボルエラーとシンドロームの結果より判
定した場合でも、ブロック内のエラーポインタの状態と
、求められたエラーロケーションのシンボルに対応する
エラーポインタがエラーの状態を示しているかどうかに
より１シンボルエラー訂正、２シンボルエラー訂正を行
なわないものである。

発明が解決しようとする問題点 しかしながら上記のような構成では、初段の復号におい
て、１つのブロック内に２シンボル以上のエラーがある
と判定した場合に、そのブロック内のすべてのシンボル
に対応したエラーポインタをエラーを示す状態としてい
るために、エラーでないシンボルもエラー状態となり、
次段以降の復号においてエラー訂正が不能になる状態に
なる確率が高くなり、訂正可能なエラーが訂正されなか
っタリ、エラーでないシンボルがエラー状態として残る
という問題点を有していた。

本発明はかかる点に鑑み、ブロック内のエラーポインタ
信号を全シンボル−律に設定する場合に比べ、エラー訂
正不能になる状態を少なくシ、エラー訂正能力を向上し
た誤り訂正方法を提供することを目的とする。

問題点を解決するための手段 本発明は、誤り検出結果にもとづきシンボルごとに誤り
フラッグを設けることと、誤り訂正を行う誤り訂正ブロ
ックのシンボルの誤りフラッグの数を計数することと、
誤り訂正ブロック内での誤り位置を求め、その誤り位置
のシンボルの誤りフラッグを判定することとを用いた誤
り訂正方法である。

作用 本発明は前記シンボルごとの誤りフラッグにより各シン
ボルがエラーなし、エラー状態、エラー状態の可能性等
の各状態であること知ることができ、誤り位置結果と併
せてエラー訂正の制御を行なうために、エラー訂正可能
なエラーが訂正されなかったり、エラーでないシンボル
がエラー状態として残る状態が非常に少なくなり、エラ
ー訂正能力が向上する。

実施例 誤り訂正符号として誤り訂正符号生成ブロック内の２シ
ンボルエラーまでを訂正することができ、あらかじめエ
ラーロケーションが判っていれば４ンンボルエラー訂正
まで可能な第」のリードソロモン符号と誤り訂正符号生
成ブロック内の１シンボルエラーまでを訂正することが
でき、あらかじめエラーロケーションが判っていれば２
シンボルエラー訂正まで可能な第２のリードソロモン符
号とを用いた例により説明する。

まず送信側において初期の状態にあるディジタル信号系
列をインターリーブ処理し第１のブロックを形成し、ブ
ロック内の各ワードよシ第１の誤り訂正符号である第１
のリードソロモン符号を生成する。更にインターリーブ
処理を行ない第２のブロックを構成して、第２の誤り訂
正符号である第２のリードソロモン符号を生成する。こ
の時第１の誤り訂正符号と第２のブロックのブロックア
ドレス信号とは第２の誤り訂正符号生成のためのデータ
に一含めるようにする。更に第２のブロックについて、
ブロック同期信号を付加する。そして第０ブロツクより
順に伝送を行なう。第２図にブロック構成した例を示す
。

第３図に受信装置のブロック図を示す。本実施例では、
第２の誤り訂正符号である第２のリードソロモン符号は
ブロックアドレスを含むデータの誤り検出に用いる。１
は第２の誤り訂正符号による誤り検出回路、２は誤り検
出結果をシンボルごとに記憶するための誤りフラグメモ
リ、３はブロック内のデータ及び誤り訂正符号を記憶す
るためのメモリ、４は誤りの訂正を行なう誤り訂正回路
、５はシンボルのエラーポインタ信号を記憶するだめの
エラーポインタ用メモリである。

受信側では、誤り検出回路１によってブロックアドレス
信号を含めた誤り検出を行ない、メモリ３及び誤りフラ
グメモリ２への書込みを以下のように行なう。誤り検出
回路１では、誤りの検出と誤り位置の判定を第１図Ａに
従って行なう。シンドロームの計算を行ないエラー個数
の判定を行なう。エラーなしであれば、ブロックアドレ
スが示すメモリ３の場所にブロック内のデータを書込み
、対応する誤りフラグメモリの場所にはエラーフラグを
立てないでおく。１シンボルエラーであれば、誤り位置
を算出し、それがブロックアドレスになければ再生ブロ
ックアドレスにもとづきメモリ３にデータを書込むと同
時に、対応する誤りフラグメモリの場所には、誤り位置
のシンボルに対応する所にはエラーフラグ■、それ以外
のシンボルに対応する所にはエラーフラグ■を立てる。

１シンボルエラーがブロックアドレスであれば、再生ブ
ロックアドレスではなく、他の手段で補間されたブロッ
クアドレスを用いて、メモリ３にデータを書込むと同時
に、対応する誤りフラグメモリの場所には、エラーフラ
グ■を全てのシンボルに対して立てる。２シンボル以上
エラーの場合には、メモリ３へはデータのかわりに例え
ば全て°゛ＨＨパシンボル８ビツトであれば”　Ｆ　Ｆ
”（１６進表現）を書込み、対応する誤りフラグメモリ
の場所には、エラーフラグ■を全てのシンボルに対して
立てる。メモリ３及び誤りフラグメモリ２はそれぞれ２
つに分かれており、一方に一定の長さのデータ及び誤り
フラグが書込まれている間、他方からはすでに記憶され
ている同じ長さ分のデータ及び誤りフラグを順次読み出
し誤り訂正が行なわれる。これらメモリ３、誤りフラグ
メモリ２のアドレス、書込み読出し制御は誤り検出回路
、誤り訂正回路内に設けた制御回路により行なう。次に
誤り訂正方法について説明する。

本実施例では、誤り訂正動作は第１の誤り訂正符号の第
１のリードソロモン符号の復号により行なう。第１図Ｂ
、Ｃに復号アルゴリズムを示す。

まず、メモリ３よシ第２図に示す第１のブロックを構成
していたデータをブロック毎に順に読み出し、誤り訂正
回路４によりシンドロームの計算が行なわれ、次にブロ
ック内の誤りの個数が判定される。次に誤り位置の算出
を行なう。この時、誤りフラグメモリ２より各７ンボル
に対応した誤りフラグが同時に読み出され、誤り訂正の
条件判定忙使用する。

（１）エラーが０と判定した場合 ブロック内の各データに対応した誤りフラグをクリアし
て誤りなしの状態にする。更にブロック内の各データに
対応したエラーポインタ用メモリのエラーポインタ信号
を誤りなしを示す状態忙する。（例えば”Ｌ”レベル） （２）１シンボルエラーと判定した場合誤り位置の算出
であらかじめ求められたシンボルの誤り訂正を行ない、
対応する誤りフラグ及びエラーポインタ信号をクリアし
て誤りなしの状態にする。

（３）２シンボルエラーと判定した場合ブロック内の各
データに対応した誤りフラグメモリを読出し、誤りフラ
グの計数を行う。フラグ■、■、■の合計数Ｍに応じて
以下のように動作する。

ここでＭ　＝　Ｎ　（ａｌ＋　Ｎ　（ｂｌ十Ｎ　（ｃ）
Ｎ（ａｌ；フラグ■のシンボル数 Ｎ（ｂ）；フラグ■のシンボル数 Ｎ（ｄ；フラグ■のシンボル数 （３−１）’Ｍ≦１の場合 誤り位置の算出で求められたシンボルを２シンボル誤り
訂正を行ない、対応するシンボルの誤りフラグ及びエラ
ーポインタ信号をクリアして誤りなしの状態にする。

（３−２”ｌ　Ｍ：２の場合 以下の３条件の条件判定を行う。

条件１；求めた２つの誤り位置に共にフラグが立ってい
ない。

条件２；求めた２つの誤り位置の一方に７ラグが立って
いる。

条件３；求めた２つの誤り位置の両方にフラグが立って
いる。

条件判定の結果、条件１を満足し、フラグが共に■のと
きは、２シンボル誤り訂正を行ない、対応するシンボル
の誤りフラグ及びエラーポインタ信号をクリアして誤り
なしの状態にする。

条件１を満足し、フラグが共に０である場合以外は、誤
り訂正を行なわずブロック内のすべてのシンボルに対す
るエラーポインタ信号を誤りありを示す状態にする。（
例えばＩＩ　Ｈ”レベル）条件２．３を満足した場合、
２シンボル誤り訂正を行なう。そして、対応するシンボ
ルの誤りフラグ及びエラーポインタ信号をクリアして誤
りなしの状態にする。

（３−３）Ｍ＝３の場合 条件判定の結果、条件１を満足する時は、誤りフラグの
立っているシンボルを消失訂正し、対応するシンボルの
誤りフラグ及びエラーボイ／り信号をクリアして誤りな
しの状態にする。

条件２を満足する場合は、誤りフラグがすべて■のとき
はブロック内のすべてのシンボルに対するエラーポイン
タ信号を誤りありを示す状態にする。誤りフラグがすべ
て■ではないときは２シンボル誤り訂正を行なう。そし
て、対応するシンボルの誤りフラグ及びエラーポインタ
信号をクリアして誤りなしの状態にする。以下。

誤り訂正を実行した場合は誤りフラグ、エラーポインタ
信号のクリアが同時に行なわれるので説明は省略する。

条件３を満足する場合は、２シンボル誤り訂正を行なう
。

（３−ａ）Ｍ＝４の場合 条件判定の結果１条件１を満足する時は、誤りフラグの
たっているシンボルを消失訂正を行なう。条件２を満足
する時は、誤り位置で示すシンボルがフラグ■、他がフ
ラグ■のとき、２シンボル誤り訂正を行ない、それ以外
の場合はフラグの立っているシンボルを消失訂正を行な
う。条件３を満足する時は、２シンボル誤り訂正を行な
う。

（３−ｓ）Ｍ２Ｓの場合 誤りフラグの計数で、フラグ■、フラグ■の数の和を求
め以下の４つの場合に分ける。

（３−５−１）　Ｎ　（ａｌ　＋　Ｎ　（ｃｌ≦１の場
合条件判定の結果、条件３を満足する時は２シンボル誤
り訂正を行なう。条件２を満足する時は、誤り位置で示
すシンボルがフラグ■のときは２シンボル誤り訂正を行
なうが、それ以外の場合はすべてのシンボルのエラーポ
インタ信号を誤りありの状態にする。また条件１を満足
する場合もすべてのシンボルのエラーポインタ信号を誤
りありの状態にする。

（３−６−２）Ｎ　（ａ）　＋　Ｎ　（ｃｌ＝　２の場
合条件判定の結果、条件３を満足し、フラグが共に＠で
なければ２シンボル誤り訂正を行ない、それ以外の場合
及び条件１．２を満足する場合ハスべてのシンボルのエ
ラーポインタ信号を誤りありの状態にする。

（３−５−３）３≦Ｎ　（ａｌ　十Ｎ　［ｃｌ≦４の場
合フラグ■、■のシンボルを消失訂正する。

（３−６−４）　　Ｎ　（ａｌ　十Ｎ　（ｃｌ≧５の場
合フラグ■、■、■のシンボルのエラーポインタ信号を
誤りあシの状態にする。

（４）３シンボル以上と判定した場合 誤りフラグの計数を行ない、フラグ■、■。

■の合計数Ｍに応じて以下のように動作する。

（Ａ−１）Ｍ≦２の場合 ブロック内のすべてのシンボルに対するエラーポインタ
信号を誤りありの状態にする。

（４−２）３≦Ｍ≦４の場合 フラ゛グ■、■、■のシンボルを消失訂正する。

（４−３）Ｍ２Ｓの場合 フラグ■、■、■のシンボルに対するエラーポインタ信
号を誤りありの状態にする。

以上のようにして、誤り訂正を実行し、エラーポインタ
信号をエラーポインタ用メモリに書込み更新する。次に
再度誤り検出回路１により誤り検出を行ない、誤り訂正
回路による訂正を行なっても良い。このように訂正され
たデータはメモリ３より順に読み出されると同時にその
データの対応するエラーポインタ信号もエラーポインタ
用メモリ５より読み出され２以外の信号処理に用いられ
る０ 発明の効果 以上のように本発明によれば、受信側において誤り検出
結果にもとづきシンボルごとに誤りフラグを設け、誤り
訂正を行う誤り訂正ブロックのシンボルの誤りフラグの
数を計数することと、誤り訂正ブロック内の誤り位置を
求め、その誤り位置のシンボルの誤りフラグの種類判定
することとを用いることにより、従来誤り訂正できなか
ったシンボルを訂正することができる。

【図面の簡単な説明】

第１図人は本発明の一実施例の誤り訂正方法の誤り検出
アルゴリズムのフローチャート、第１図Ｂ　、　Ｃハ誤
！７訂正アルゴリズムのフローチャート、第２図は同実
施例の送信信号のブロック構成図、第３図は同実施例の
受信装置のブロック図、第４、図は従来の誤り訂正方法
の訂正アルゴリズムを示すフローチャートである。 １・・・・・・誤り検出回路、２・・・・・・誤りフラ
グメモリ、３・・・・・・メモリ、４・・・・・・誤り
訂正回路、５・川・・エラーポインタ用メモリ。 代理人の氏名　弁理士　中　尾　敏　男　ほか１名第２
図 く り＼ 区　　　　°６

Claims (1)

【特許請求の範囲】
1. ディジタルデータ列を第１の配列状態において一定の長
   さのブロックに分割し、この第１のブロックに対する第
   １の検査シンボルを生成し第１の誤り訂正ブロックを形
   成し、異なる第１の訂正ブロックよりシンボルを取り出
   し第２のブロックを形成し、第２のブロックに対しブロ
   ックアドレス信号を付加し、この第２のブロックに対す
   る第２の検査シンボルを生成し第２の誤り訂正ブロック
   を形成し、第２の誤り訂正ブロックに同期信号を付加し
   てディジタル信号の送信を行ない、受信側では第２の誤
   り訂正ブロックの誤り検出を行ない、誤り検出結果にも
   とづきシンボルごとに誤りフラッグを設け、次段以降の
   復号では誤り訂正を行う誤り訂正ブロックのシンボルの
   誤りフラッグの数を計数した結果と、誤り訂正ブロック
   内での誤り位置を求め、その誤り位置のシンボルの誤り
   フラッグを判定することにより誤り訂正を行なうことを
   特徴とする誤り訂正方法。