JPS5829237A - エラ−訂正方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 この発明は、パーストエ２−及びランダムエラーの何れ
に対してもエラー訂正能力が高く、然もエラー検出の見
逃し又は゛誤った訂正を生じるおそれが低減されたエラ
ー訂正方法に関する。

本願出願人は、先にバーストエラーに対して有効なデー
タ伝送方法としてクロスインターリーブと称するものを
Ｉｌ案している。これは、第１の配列状態にある複数チ
ャンネルのＰＣＭデータ系列の条々に含すれる１ワード
を第１のエラー訂正符号１ｍＫ供給することによって第
１のチェックワード系列を発生させ、この第１のチェッ
クワード系列及び複数チャ２ネルのＰＣＭデータ系列を
第２の配列状態とし、夫々に含まれるｌワードを第２の
エラー訂正符漫器に供給することによって第２のチェツ
タワード系列を発生させるもので、ワード単位でもって
二重のインターリーブ（配列の並び費え）を行なうもの
である。インターリーブは、共通のエラー訂正ブロック
に含まれるチェックワード及びＰＣＭデータを分散させ
て伝送し、受償儒において元の配列に戻したとｔｋＫ、
共通のエラー訂正ブロックに含まれる複数ワードのうち
のエフ−ワード数を少なくしようとするものである。つ
壜り。

伝送時にバーストエラーが生じるときに、このバースト
エラーを分散化することができる。かかるインターリー
ブを二重に行なえば、＠１及び第２のチェックワードの
夫々が別々のエラー訂正ブロックを構成することになる
ので、チェックワードの何れか一方でエラーを訂正でき
かいときでも。

その他方を用いてエラーを訂正することができ。

したがってエラー訂正能力を一層向上させることかで亀
る。ところで、ｌワード中の１ビツトでも誤っていると
きには、ｌワード全体が誤っているものとして織り扱わ
れるので、ランダムエラーが比較的多い受信データを扱
う場合には、必ずしもエラー訂正能力が充分であるとは
貫見ない。

そこで１ブロツク内のにワード例えば２ワードエラー１
で訂正でき、エラーロケーションが判っているときには
１Ｍワード例えば４ワードエラー盲でも訂正することが
できる訂正能力の高いエラー訂正符号（隣１ｉ　（ｂ−
ａｄｊａｃｅｎｔ）　：ｌｉ−ドの一種）を上達の多重
インターリーブと組合せることが考えられる。また、こ
のエラー訂正符号は、ｌワードエラーだけを訂正の対象
とする場合には、復号器の構成を頗る簡単とできる％黴
を有している。

また、第２のエラー訂正ブロックに対する初段の復号な
行ない１次に第１の配列状態に戻してから第１のエラー
訂正ブロックに対する次段の復号な行なう場合、初段の
復号でエラーがあるＫも拘らずエラがないと判断するよ
うなエラー検出の見逃し、４ワードエツーを１ワードエ
ラーとして検出し、それによる誤った訂正が生じると、
この莞逃し、誤った訂正が次段の復号において新たな見
逃し、ＷＩＡりた訂正の簀因となり、全体としてみたこ
れらの誤動作の生じるおそれかつよ−くなる。

また、訂正するエラーワード数が多くなると、上述の見
逃し、誤った訂正の生じる確率が一般的に大きくなる。

この発明では、初段の復号の際に１例えば１ワードエラ
ー及び２ワードエラーの訂正を行ない。

これと共に１例えば３ワ一ド以上のワードが哄っている
ことを初段の復号で検出丁するよ５になし。

また、ｌワードエラーとして訂正された場合、２ワード
エツーとして訂正された場合、３ワ一ド以上のエラーと
して検出された場合の各々を区別できる３種類のポイン
タを付加するようＫし１次段の復号でこのポインタ状態
を判別して訂正を行なうことにより１次段の復号での見
逃し、誤った訂正のおそれを防止している。このように
して、エラー検出及び訂正の際の見逃し、誤った訂正の
おそれを軽減し１例えばオーディオＰＣＭ信号を伝送す
る際に、ｌＲつた訂正による異音が発生するような問題
点を解決し【いる。

まず、この発明の一例に用いるエラー訂正符号につ込て
説明する。エラー訂正符号を記述する場合、ベクトル表
現或いは巡回群による表現が用いられる。まず、　ＧＦ
（２）上では、既約なｍ次の多項式Ｆ（２）を考える。

＠Ｏ′″と＠ｌ”の元しか賽在しない体Ｃ３Ｆ（’ｌ）
の上では、既約な多項式Ｆ（ｘ）は、Ｉｌを持たない、
そζで（Ｆｉｘ）−０”）を満足する仮想的な根αを考
える。このと１！、零兄を含むαのべ自乗で表わされる
一儂の相異なる元０．α、α８．α３・・・・♂°１は
、拡大体ＧＦ　（２”）を構成する。ＧＦ　（２−）は
。

ＧＦ（１３の上のｍ次の既約多項式Ｆ（ｘ）を法とする
多項式環であるｅ　ＧＦ（２−）の元ｔｔ、１．α−（
ＸＬα３コ（Ｘ”）　、　１１１１＠１１．　Ｃｇ−−
”　ｗｚ　（ｘ”−”）　（’）線形結合テカきあられ
すことかできる。即ち ａｏ＋α１（ｘ１＋αｓ（ｘ”）十・・・・＋Ｑｖｎ−
ｓ　（Ｘ”“１）婁α０＋α１α＋α３α８＋１−・＋
０ｍ−１（”’−’あるいは（−−１−一、雪、・・１
．α意、αｈＱｏ）ここで。

α０．α１．・・・・、ら−ｘＣＧＦ（ｇｌとなる。

−例として、　ＯＦ（！”）を考えると、　　（ｍｏｄ
、　Ｆ（ｘ）　＝１”＋１’＋Ｉ’＋Ｘ”＋１　）で全
ての８ビツトのデーｐｈｓαｙＸ　＋Ｇ＠Ｎ＋αＢＸ＋
α４ｘ＋α３ｘ十α２ｘ＋ａｌＸ＋αＯ又は（α？ｅ　
’Ｌ＠ｍ　”Ｉｓα４＊ａ３＊α！＊ａｌｅα０）で書
睡あられせるので１例えばα１をＭＯＢ＠、α０をＬ８
Ｂ憫に割り轟てる。α。は、ＧＦ（２）Ｋ属するので、
０又は１である。

また、多項式Ｆｔｘｌから（ｍＸｒｎ）の下記の行列Ｔ
が導かれる。

他の表現としては１巡回群を用いたものがある。

これは、　ｑＦ（２”）から０元を除く、残りの元が位
数２ｍ−１の乗法群をなすことを有用するものである。

Ｇ　Ｆ　（２”）の元を巡回群を用いて表現するとｏ、
　ｌ＜　冨／ｍ°ｌ）、ａｓ　ａｍ、　ａｓ、　、、、
、、、α１ｍ−１となる。

さて、この発明の一例では１ｍビットを１ワードとし、
ｉワードで１ブロツクを構成す゛るとき。

下記のパリティ検査行列ＨＫもとすいてに個のチェツタ
ワードを発生するよ５Ｋしている。

壜た１行列Ｔによっても同様にバリディ検査行列Ｈな表
現することがで勤る。

但し、Ｉは、（ｍＸｍ）の単位行列である。

上述のよ５に、機αを用いた表現と生成行列Ｔを用いた
表現との両者は本質的に同一である。

ｊ！に、４個（ｋ−４）のチェックワードな用いる場合
をＩＪＩＫとると、パリティ検査行列ＨはＶｔ（Ｗ、−
１ｔ　ｗ、、、　ａｍ、Ｗｔｓ　Ｗｏ）　（ｆｆｌ　Ｌ
　Ｗｔ　＝＝＝ｗｌｅｉ。

ｅｉ：エラーバタン）とすると受信側で発生ずる４備の
シンド’　−ム８０＊　Ｓｌｅ　”２ｍ　８ｍはとなる
。このエラー訂正符号は、ひとつのエラー訂正プロッタ
内の２ワードエラー壕でのエラー訂正が可能であり、エ
ラーロケーションがわかっているときには、３ワードエ
ラー又は４ワードエラーの訂正が可能である。

ｌブロック中に４個のチェックワード（ｐ　＝Ｗａ　ｍ
ｑ工Ｗ２．　ｒｚＷ、、　５＝ｘＷＯ）が含まれる。こ
のチェックワードは、下記のようにして求められる。但
し。

計算過１を省略し、結果のみを示すと となる。このようにしてチェックワード９＊　Ｑｍ　’
ｅＳを形成するのが送信側に設けられた符号器の役■で
ある。

次に、上述のように形成されたチェックワードな會むデ
ータが伝送され、受信された場合のエラー訂正の基本的
アルゴリズムについて説明する。

（１）エラーがない場合：　８０ｘ８１＝８，２８１ｍ
Ｑ（２）　１ワードエラー（エラーパターンをｅｌとす
ル）ノ場合：　８６　ｍｅｌ　　Ｊ　＝（Ｘ’ｅｌ　　
８２　＝＋ｇ（Ｘ”ｅｌ　　８３−αｓＩｅ暴 したがって となり、鳳を順次変えたとｔｌＫ、上記の関係が成立す
るかどうかで１ワードエラーかどうかを判定することが
できる。或いは ゑ　　　　。

となり、αのパターンを予めＲＯＭ　Ｋ記憶されている
ものと比較してエラーロケーション量が°分カる。その
ときのシンドローム８ｏカエラーパターンｅｉそのもの
となる。

〔３〕２ワードエラー（ｅゑ、ｅｊ）の場合上式を変形
すると したがって が成立すれば、２ワードエラーと判定され、エラーロケ
ーション量、ｊが分かる。つまり、１及びｊの組合せを
青光て上式の関係が成文するかどうかを関ぺる。そのと
きのエラーパターンは（４）　３　’７−ド！　９−　
（ｅｉ、　ｅｊ、　ｅｋ）　ｆ）場合上式を変形すると したがって 上式から ａ’（ａ’（ａ４ａｌ）＋ａ、）＋（♂８１＋８２）　
）　−（Ｘ’　（−８１１ｇ）＋（（１’　８ｒ４４ｓ
）が成立すれば、３ワードエラーと判定できる。但し、
　（８ｏ”Ｆ−Ｏｘ　８ｔ　’ｒ（Ｌ　８ｚ’ｖＯ）で
あることを条件としている。そのときの各エラーパター
ンはで求められる。実際には、３ワードエラーの訂正の
ための構成が複雑となり、訂正動作に費する時間も長く
なる。そこでポインタによってｉ、　Ｌ　ｋのエラーロ
ケーションが分かつている場合と組合せ、そのと亀のチ
ェック用に上式を用い、エラー訂正動作を行なうことが
実用的である。

（５）　４　”７−ドｚ　ｙ　−（ｅｔ、　ｅ３．　ｅ
ｋ、　ｅｘ　）の場合：上式を変形すると ポインタによってエラーロケーション（ｉ＝　ｊ−’ｅ
慮）が分かつている場合には、上述の演算によってエラ
ー訂正を行なうことができる。

上述のエラー訂正の基本的アルゴリズムは、シンドロー
ム８ｅ〜Ｓｓを用いて第１ステツプでエラーの有無をチ
ェックし、第２ステツプで１ワードエラーかどうかをチ
ェックし、篤３ステップで２ワードエラーかどうかをチ
ェックするもので、２ワードエラー１でも訂正しようと
するときには。

全てのステップを終了するまでに１！する時間が長くな
り１％に２ワードエラーのエラーロケーションを求める
とＩＩＫこのような問題が生じる。そこで、このような
問題を生ぜず、２ワードエラーの訂正を想定する場合に
適用して有効な変形されたアルゴリズムについて以下に
説明する。

２ワードエラー（ｅｉ、ｅｊ）の場合のシンドロームＢ
ｏｗ　８□ｅ　８ｉ１１＊　ｓ、　Ｋ　ＩＩする式は、
前述トｆｉｌｌｉＫこの式を変形すると ゑ　　　　ｌ （α８ｏ十８ｓ）（α８ｇ＋ａｍ）　−（α８ｏ十８ｓ
）”更に変形して下記のエラーロケーション多項式を求
むる。

（８ｏ８ｘ＋８１”）♂’＋（８１８ｇ＋８ｏ８ａ）α
’　＋　（８ｔ　％＋８ｇ”）　率０こむで、４）式の
係数を とおく、上式の各係数Ａ、　Ｂ、　Ｃを用いることによ
り２ワードエラーの場合のエラーロケーションを求める
ことができる。

（１１エラーがない場合：　ＡｍＢｍＣｍＯ、８ｏ’ｌ
ｓＯ。

Ｂｓ１ＩＩＩＯ 〔２〕１ワードエツーの場合：　””Ｂ−Ｃ＝Ｏ＊　８
Ｇ’Ｆ０゜８ｓ〜Ｏ からエラーロケーション轟が分かり、　　（ｅ１＝８ｏ
）を用いてエラー訂正がなされる。

〔３〕２ワードエツーの場合： ２ワ一ド以上のエラーの場合には、（Ａ〜Ｇ、　Ｂ〜Ｏ
０Ｃ〜Ｏ）が成立し、その判定が頗る簡単となる・また
、このと自 Ａα３１十Ｂα’＋Ｃ−０（但し、１−０〜（ｎ−１）
）Ｄ；α轟＋α１．ト１凰・α１ であり （＊”　＋Ｄａ’　十ｌ　＝ｍ　Ｏ となる。ここで、２つのエラーロケーションの差がｔで
ある９１す（ｊ−１＋ｔ）とすると鳳 Ｄ　−α　　（ｌ　十α　　）、　　　　Ｅ、雪　α３
ゑ０と変形される。したがって となる、ＲＯＭに（１口１〜（ロー１））の夫々に関す
る。

致を検出することで１が求まる。もし、この一致関係が
成立しなければ、３ワ一ド以上のエラーである。そこで Ｘ−１＋α１ −１　　Ｄ” Ｙｍｌ＋α　−Ｈ十Ｘ とおくことにより となり、エラーロケーション轟及びｊが求められる。エ
ラーパターンｅ量、ｅｊは と求められ、エラー訂正を行なうことができる。

上述の変形された訂正アルゴリズムは、２ワードエ２−
の訂正まで行なうときに、エラーロケーションを求める
のＫｌ！する時間を、基本的アルゴリズムに比べて頗る
短くすることがで龜る。

なお、チェックワードの数ｋをより増加させれば、エラ
ー訂正能力が一層向上する０例えば（ｋコロ）とすれば
、３ワードエラーまで訂正で亀、エラー−ケージ璽ンが
分かつていると自に、６ワードエツーまで訂正できる。

上述のエラー訂正において、ｌワードエラーの訂正に際
して、４ワ一ド以上のエラーをｌワードエラーとあやま
って検出し、訂正するｌｉｌの可能性があり、ｔた３ワ
一ド以上のエラーを２ワードエラーとあや筐って検出し
、訂正する第２の可能性があり、この嬉２０可能性は、
第１の可能性より大きいが、何れの可能性も比較的小さ
い。

以下、この発明をオーディオＰＣＭ信号の紀−再生に適
用した真体例について図面を参照して説明する。第１図
は、記ｆａ系に設けられる誤り訂正エンコーダを全体と
して示すもので、その入力側にオーディオＰＣＭ信号が
供給される。オーディオＰＣＭ信号は、左右のステレオ
信号の夫々なすンプリング周波数ｆｓ　（例えば４４．
１　（ｋＨｚ）　）でもってサンプリングし、ｌサンプ
ルなｌワード（２を補数とするコードで１６ビツト）に
変換することで形成されている。したがって左チャンネ
ルのオーディオ信号に関しては−（Ｌｏｔ　ｌｉｅ　Ｉ
４　”・・）と各ワードか連続するＰＣＭデータが得ら
れ、右チャンネルのオーディオ信号に関しても（ＲＯｅ
　Ｒｌｅ　Ｒ，・・・）と各ワードが連続するＰＣＭデ
ータが得られる。この左右のチャンネルのＰＣＭデータ
が夫々６チヤンネルずつに分けられ、計１２チャンネル
のＰＣＭデータ系列が入力される。所定のタイミングに
おいては−（ＬＩｋ、φＲ４ｅ　Ｌ６針１　ｍ　”ｓｒ
ｔ＋１ｅ　：Ｌｓ吐冨・Ｒ６針冨―ＬＩＩｌ＋ｌｔ　＠
ｓ、＋ｓｅ　Ｌｓｒｒ＋４ｅ　Ｒ＠Ｅｌ＋４　）の１２
ワードが入力される。この例では、１ワードを上位８ピ
ツ）と下位８ビツトとに分け、　１２チヤンネルを］ｌ
！に２４チヤンネルとして処通している。　ＰＣＭデー
タの１ワードを簡単のためｇ、Ｗｉとして表わし、上位
８ビツトに関しては、Ｗｉ、Ａと人のすフィックスを付
加し、下位８ビツトに関し【は、Ｗｉ、、とＢのすフィ
ックスを付加して区別している０例えばＬ軸がＷ、１．
、Ａ及びＷ１細、Ｂの２つに分割されることになる。

この２４チヤンネルのＰＣＭデータ系列がまず偶奇イン
ターリーバ（１）Ｋ対して供給される。（ａ＝０、１、
２・・・）とすると、Ｌ６ａ（＝Ｗ１２ｎ, ａ、Ｗ１２
ｎ,B)，Ｒ６Ｎ（＝ｗ１２ｎ＋１,A、Ｗ１２ｎ＋１,B)、
Ｌ６ｎ＋２（Ｗ１２ｎ＋４,Ａ、Ｗ１２ｎ,B)、”１１ａ
＋４ｅ　Ｂ　）　＊　Ｒ＠ａ＋２　（−Ｗｔ！＄ＩｅＡ
＊　Ｗ１ｉｔ＄ｉ＊　Ｂ　）。

Ｉ４ａ＋４　　（−Ｗｌ意ａ＋Ｉｅ　Ａ　　、　　Ｗｌ
ｌ（ｐｇ　、、）　　、　　Ｒ＠吐４　　（＝Ｗ１ｘａ
−ｓ−ｓｏ　ム。

Ｗｌｚ＋會、Ｂ）の夫々が偶数番目のワードであり、こ
れ以外が奇数番目のワードである。偶数番目のワードか
らなるＰＣＭデータ系列の夫々が偶奇インターリーバ（
１）の１ワ一ド遅延回路（２Ａ）　（２Ｂ）　（３Ａ）
　（３Ｂ）（４Ａ）　（４Ｂ）　（ＭＡ）　（５Ｂ）　
（６Ａ）　（６Ｂ）　（７Ａ）　（７Ｂ）　Ｋよって１
ワード遅駕される。勿論、ｌｙ−ドより大きい例えば８
ワードを逼駕させるようにしても良い。まり、偶奇イン
ターリーバ（１）では、偶数番目のワードからなる１２
個のデータ系列が第１−第１２１目までの伝送チャンネ
ルを占め、奇数番目のワードからなる１２個のデータ系
列が第１３〜第２４番目までの伝送チャンネルを占める
ように変換される。

偶奇インターリーバ（１）は、左右のステレオ信号の夫
々に関して連続する２ワ一ド以上が誤り、然もこのエラ
ーが訂正不可能となることを防止するためのものである
。例えば（Ｌｔ−１＊　Ｌｔ　ｅ　Ｌｔ＋ｓ　）と連続
する３ワードを考えると、Ｌ条が誤っており。

然もこのエラーが訂正不可能な場合に、Ｌｉ−１又はＬ
ｉ＋ｘが正しいことが望される。それは、誤っているデ
ータＬｉを補正する場合において、前の正しい９−ドＬ
ｉ−５でもってＬｉを補間（前値ホールド）したり、　
Ｌｊ、、及びＬ１＋１の平均値でもって稍を補間するた
めである。偶奇インターリーバ（１）の遅延回路（！Ａ
）（２Ｂ）〜（７ＡＸ７Ｂ）は、隣接するワードが異な
るエラー訂正ブロックに當筐れるようにするために設け
られている。また、偶数Ｉｌ目のワードからなるデータ
系列と奇数番目のワードからなるデータ系列毎とに伝送
チャンネルなオとめているのは、インターリーブしたと
きに、近接する偶数喬■のワードと奇数番目のワードと
の記鐘位置間の距離をなるぺ〈大とするためである。

偶奇インターリーバ（１）の出方には、１ｓ１の配列状
■にある２４チヤンネルのＰＣＭデータ系列が現れ、そ
の夫々から１ワードずつが散り出されて符号器（８）Ｋ
供給され、第１のチェツタワードＱ１ａ□Ｑｌｋ＋ｘ　
ｅ　Ｑｌｌｏ＋ｓｅ　Ｑｌｓｎ＋ｓが形成される。雛！
のチェックワードを含んで構成される第１のエラー訂正
プロッタは （Ｗｔ意ｎ−””　Ａ”　””−”中”１冨ｎ＋１−１
２ｅ　Ａ１１　”１紛１−１１ｅ　３３ｍＷｔｓａ＋ｎ
−ｔｚ　＊）、　ｓ　Ｗｓｚｎ十ａ−１意中Ｗｔ＊ｍｓ
−ｘｓｅ　ｙｘ　＊　Ｗ１ｓｎ＋５−１ｘ＊　Ｂ　５Ｗ
１２ｎ＋４−１鵞讃ム、　”ｌ　！ｏ＋１−１１ｅ　Ｉ
ｌ−ｗｌ＊ｒｌ＋９−１１ｅ　ムｓ　Ｗｌ　２針９−１
１ｅ　ｆ３−Ｗ１２ｎ＋３−Ａｓ％ｙｌ＋ｘ　ｅ　＠　
−Ｗｌ　ｚｆｉ＋ｓ　ｅ　Ａ　−”１意ｎ十葛伊トＷ１
２ｎ＋＠ｅ　Ａ　、　”１１Ｂ幅Ｂ−Ｗｌ　ｌｆｔ＋７
ｅ　ム＊　”１雛１ｅ　３％　＊Ｗ１２０４１０１　Ａ
、ＷｌｍＮｌｏｅ　Ｂ、Ｗｌ！ｏ＋１１−ム亀”ｌｌｏ
＋山１　ｍＱｔｘｎ、　　　ＱｌｌＩｌ＋ｌ　、　　　
Ｑｘ４＋ｚ　、　　　Ｑｌｘｎ＋ｓ　）となる、第１の
符号器（８）では、ｌブロックのワード数：　（ａｍ２
８）、１ワードのビット数：（ｎ−８）。

チェックワード数：（ｋ−４）の符号化がなされている
。

この２４個のＰＣＭデータ系列と、４個のチェックワー
ド系列とがインターリーバ（９１に供給される。

インターリーバ（９）では、偶数Ｉｌ目のワードからな
るＰＣＭデータ系列と奇数番■のワードからなるＰＣＭ
データ系列との間にチェツタワード系列が介在するよう
に伝送チャンネルの位置を変えてから。

インターリーブのための遅駕処場を行なっている。

この遅延処場は、第１Ｉ■の伝送チャンネルを除く他の
２７儂の伝送チャンネルの夫々に対しＣ１ＩＤ、　２Ｄ
、　３Ｄ、　４Ｄ、・・・・、　２６Ｄ、　２７Ｄ　（
但し、Ｄは単位遅蔦量で伺えば４ワード）の遅延量の遅
延回路を挿入することでなされている。

インターリーバ（９）の出力には、第２の配列状態にあ
る２８個のデータ系列が現れ、このデータ系列の夫々か
ら１ワードずつが取り出され【符１ｍ！ＱｌＫ供給され
、第２のチェックワードＰＩ　ＭＱ　ｅ　Ｐｌｋｒ＋ｌ
・’１ｋｌ＋２　Ｉ　Ｐ１ｘｌｙ４−ｓが形成される。

第２のチェックワードを含んで構成される３２ワードか
らなる菖２のエラー訂正ブロックは、下記のものとなる
。

ＣＷｔ　軸−１ｓｔＡ、Ｗｌｍｍ−１諏〉÷ｌｂ、、Ｗ
ｌ！＄？ｌＵＤ＋１）Ａ、Ｗ１ｍトｌｎｏ＋ｔ＞Ｂ。

１ ｑ亀−臘纏ω・喝Ｈ−前ＩＤ）　Ａｘ針ト燻ｌ樽・ｑ２
針ト諏■いＰｓｘｒｓ　　＊　　　　　　ｐｌｆｆｉａ
＋１　　、　　　　　　ＰｌｂｒＨ、Ｐｌ！ｎ＋８　　
）かかる第１及び第２のチェックワードを含む３２個の
データ系列のうちで、偶数番目の伝送チャンネルに対し
てｌワードの遅延回路が挿入されたインターリーバＱυ
が設けられており、１また第２のチェツタワードＭＦＩ
に対してインバータＢ２Ｊ　（１３（１４１ｆ；１！ｊ
が挿入される。インターリーバαυによつ【ブロック同
士の境界Ｋまたがる工２−が訂正不可能となるワード数
のエラーとなり易いことに対処している。

また、インバー！０３〜αＳは、伝送時におけるドロッ
プアウトによつ【ｌプ胃ツク中の全【のデータが＠０”
となり、これを再生系において正しいも、のと判別して
し１誤動作を肪止するため設けられている。同様７の目
的で第１のチェックワード系列。

に対してもインバータを挿入するようＫしても良い。

そして、最終的に得られる２４備のＰＣＭデータ系列と
８個のチェックワード系列との夫々から取り出された３
２ワード毎に直列化され１ｌＥ２ｔＥｌに示すよ５に、
その先頭に１６ビツトの同期信号が付加されて！＠送ズ
ブロックなされて伝送される。

第２図では１５図示の簡単のため第１１の伝送チャンネ
ルから職り出されたｌワードなｕｉとして表示している
。伝送系の具体的な例とし【は、ａｌ気記ａ再生装置１
回転ディスク装置などがあげられる。

上達の符号ａｔ（８）は、前述したようなエラー訂正袴
４＃に関するもので、　　（ｌｓｍ２１１．ｍｍｇ、　
ｊ■４）であり。

同様の符号器α骨は−（ｎ−３２，ｍ５＝ｌｌ、　ｋｘ
４）である。

再生されたデータが１伝送ブロツクの３２ワード毎に第
３１１１ｉＱＫ示す誤り訂正デコーダの入力に細見られ
る。再生データであるために、エラーを含んでいる可能
性がある。エラーがなければ、このデコーダの入力に細
見られる３２ワードは、誤り訂正エンコーダの出力に現
れる３２ワードと一致する。１１Ａり訂正デコーダでは
、エンコーダにおけるインターリーブ逃場と対応するデ
ィンターリーブ処場を行なって、データの順序を元に戻
してからエラー訂正を行なう。

オず、奇数＊Ｓの伝送チャンネルに対してｌワードの逼
ｊＩ崗路が挿入されたディンターリーバａｅが設けられ
、また、チェックリード系列に対してイｙパータ同舖（
１１（２１）が挿入され、初段の復号器Ｑυに供給され
る。復号器ｇυでは、第４図に示す１５に、パリティ検
査行列Ｈｃｌと人力の３８ワード＜ｖ”）とから、シン
ド１１−ム５ｌｅｅ　８ＩＩｓ　８□意、８□１が発生
され、これにもとすいてエラー訂正が行なわれる。

αｔ！（Ｆ（ｘｌ＝＊ｘ”−）ｘ’＋ｘ”＋ｘ”＋ｌ）
のｑＦ（２”）の元である。

復号器Ｑυからは、２４儂のＰＣＭデータ系列と４個の
チェックワード系列とが現れ、このデータ系列の１ワー
ド毎にエラーの有無を示す少なくとも１ビツトのポイン
タ（エラーがある場合には、＠１”。

そう受ないときには、１０′″）が付加されている。

この第４図及び後述の籐５図において、並びに以下の説
明では、受信されたｌワードＷｉを単Ｋ　Ｗｔとして表
わしている。

この復号器なυの出力データ系列がディンターリ−ハ（
１２Ｋ供給される。ディンターリーパロは、誤り訂正エ
ンコーダにおけるインターリーバ（９）でなされる遅延
処場なキャンセルするためのもので。

第１Ｉ目の伝送チャンネルから＠　２７　ＩＨの伝送チ
ャンネル１での夫々Ｋ　（２７Ｄ、　２６Ｄ、　２！Ｓ
Ｄ、・・・・。

２Ｄ、１０）と遅延量が異ならされた遅延回路が挿入ｓ
れている。ディンターリーバ（２）の出力が次段の復号
８ａ＠に４Ｉ＆給される。復号器＠では、第５図に示す
１５に、パリディ検査行列Ｈｃ　ｇと入力の２８ワード
とがら、シンド’　”””　”　Ｓ２０＊　Ｓｉ！ｉｓ
　’！！＊　８２３が発生され、これｋもとずいて工２
−訂正が行なわれる。

かかる次段の復ｖａｎの出力に現れるデータ系列が偶奇
ディンターリーバＣｉ！４ＫＩｉ給される。偶奇ディン
ターリーバ−では、偶数番目のワードからなるＰＣＭデ
ータ系列と奇数番目のワードからなるＰＣＭデータ系列
とが互いちがいの伝送チャンネルに位置するようＫＨさ
れると共に、奇数番目のワードからなるＰＣＭデータ系
列に対してｌワード遅蝿回路が挿入されている。この偶
奇ディンターリーバ−の出力には、誤り訂正エンコーダ
の入力に供給されるのと全く同様の配列と所定番目の伝
送チャンネルとを有するＰＣＭデータ系列が得られるこ
とＫなる・第３ａｉ！では１図示されてないが、偶奇デ
ィンターリーバ（至）の次に補正回路が設けられており
、復号器Ｑυ儲で訂正しきれなかったエラーを目立たな
くするような補正例えば平均値補間が行なわれる。

この発明の一真では、初段の復号器Ｉ２υにおいて。

ｌワードエラー及び２ワードエツーを訂正し、３ワ一ド
以上のエラーを検出するようにしている。

これと共に、これらの訂正及び検出の対象のワードに対
して、エラーがあることを示し、且つ互いに区別される
３種類のポインタを付加する。２ビツトのポインタを例
にとると、ｌワードエラーを訂正した場合には、そのエ
ラー訂正ブロック内の３２ワード又はチェックワードを
除く２８ワードを除く２８ワードの全てのワードに対し
て、　（０１）のポインタを付加し、２ワードエツーを
訂正した場合には、４）ワードに対して（１０）のポイ
ンタを付加し、３ワ一ド以上のエラーが検出された場合
には、　（１１）のポインタを付加する。勿論、エラー
が検出されないときは、ポインタが（００）となされる
。

また、３ビツトのポインタを用いるようにしても良い、
この場合は、エラーが検出されないと龜に（００Ｇ）、
　　１ワードエラーを訂正したと自で（００１）、　　
ｌワードエラーを訂正したと龜で（０１０）。

３ワ一ド以上のエラーを検出したときで（１０Ｇ）のパ
ターンが使用される。

これらのポインタは、各ワード毎に付加され。

ディンターリーバ（至）で逃場されて次段の復号器（至
）に供給される。以下に述べるよ５に、次段の復号器＠
におけるエラー訂正によって、ポインタが付加されたり
、クリアされ、補正回路では、最終的に残りているポイ
ンタをもとに補正動作が行なわれる。

次段の復号器０においては、上述のポインタによって示
される。菖ｌのエラー訂正ブロック内のエラーワードの
個数又はエラーロケーションを用いてエラー訂正を行な
う。第６図は、この次段の復号器−におけるエラー訂正
の一例を示しており。

第６Ｉｌｌ及び以下の説明では、ｌワードエラー訂正の
場合に付加される第１のポインタによるエラーワードの
個数をＮｌで表わし、２ワードエツー訂正の場合に付加
される第２のポインタによるエラーワードの個数なＮ３
で表わし、３ワ一ド以上のエラーを検出した場合に付加
される第３のポインタによるエラーワードの個数をＮ３
で表わす、また、第６図において、Ｙは肯定を表わし、
Ｎは否定を表わす６次段の復号器（至）では、２ワード
エラー１で訂正するので、エラー訂正のアルゴリズムと
しては、変形されたアルゴリズムが好ましい。つ壜り。

第６図に示される７０−チャートの最初において前述の
エラーロケーション多項式（Ａａ”＋Ｂα１＋Ｃ＝Ｏ）
が演算され、この各係数Ａ、　Ｂ、　Ｃとシンドローム
８１０〜８２ｍとを用いたエラー訂正が行なわれる。

これと共に、１ブロツク内に含まれる第１．第２゜ａ１
３のポインタの各々の総数Ｎｌ　＊　Ｎ２　＊　Ｎ３が
数えられる。勿論、シンドロームを用いてエラーがない
ことの検出、ｌワードエラーの検出、２ワードエラーの
検出を段階的に行な５基本的なアルゴリズムを用いても
良い。

（１）　　エラーがないかどうかを調べる。（Ａ−Ｂ＝
Ｃ。

ｏ、　８２Ｇ”（Ｌ　８ｘｓ＝Ｏ）　ノドｌｅ！、　一
応！？−ｒｊＬとする。その場合、　　（Ｎｓ≦ｇｌ）
かどうかを−ベる。（Ｎｓ≦ｇｌ）であれば、エラーな
しと判定し。

そのエラー訂正ブロック内のポインタをクリアするｅ　
　（Ｎｓ＞！ｘ）であれば、シンドロームによる検出が
正しくないと判定し、ポインタをそのま宜としておく。

仁のポインタコピーの際に。

３ワ一ド以上のエラーの検出時に付加される第３のポイ
ンタのみ、或いはこれに加えて、２ワ一ド訂正時に付加
される第２のポインタをコピーの対象とするよ５Ｋして
も＾い、りｔす、ｌワードエラー訂正が誤ったものであ
る確率は。

かなり小さいので、第１のポインタをコピーの対象から
外すようにしても良い。ｚｌの値は、かなり大きく、１
０〜１４程度である。

（２）　ｌワードエラーかどうかを調べる。（ＡまＢ＝
Ｃｍ’ｓ　８２０’ＦＯｓ　８ｓｓ’ＦＯ）のときに１
ワードエラシ冒ン量を求める。このエラーロケーション
ｌが（Ｏ〜２７）の範■Ｋｔｌれるかどうか検出される
。この範囲外のときは、ｌワードエラーの訂正を行なう
ことができない、そして、（Ｎ３≦ｘＢ）が成立するか
どうかが判断される。このｚｓ。

値は、３或いは４である。この条件が成立すると龜は、
ｌワードエラーと誤って検出するＩＩＩＫは、ポインタ
の個数が少なすＶるので、そのエラー訂正ブロック内に
含まれる全てのワードに対して、＃Ｉ３のポインタを付
加する（オールポインタ）　＠　（Ｎｓ＞ｇｓ）のとき
は、ポインタ；ビーの動作が前述と同様になされる。

次に、このエラーロケーションＩＫポインタが宣ってい
るかどうかが検出される。この場合。

２ワード訂正で付加されるポインタ及び３ワ一ド以上の
エラーワードの検出時に付加されるポインタが判断の対
象とされる。エラーロケーションゑにポインタが豆って
いれば１次にＣＮｓ≦ｚりかどうかが調べられる１口は
１例えばｌＯである。（Ｎｓ≦ｇｌ）であれば、ｌワー
ドエラーと判断し＊　　（ｅｔ　＝Ｓｚｏ）を用いてエ
ラー訂正が行なわれる。ポインタが豆っていても、（Ｎ
ｓ＞口）であれば、１ワードエツーの割には、ポインタ
の個数が多すぎるので、ｌワードエラーと判断すること
は危険であると判断し、ポインタをその筐筒とし、てお
く（ポインタコピー）。

エラーロケータ１ンｉに第２及び＠３のポイン夕が立っ
ていない場合には、（Ｎ３≦ｚｌ）かどうかが調べられ
る。第１のポインタがエラーロケーシＨ７ｉｆＣ立って
いても、同様に扱われる。

翼３はかなり小さい数で例えば２である。ＣＮｓ≦匂）
が成立すると自は、シンドロームの演算でもってエラー
ロケーションｉＫついての１”７−ドエラーを訂正する
・ （Ｎ３〉匂）の場合では、更Ｋ（Ｎｓ≦寞４）かどうか
が調べられる。つ宜り、（！３＜Ｎｌ≦！４）のときは
、シンドロームによるｌワードエラーの判定が誤ってい
る＠には、Ｎｓが小さすぎることを意味するから、その
ブロックの全ワードのポインタを立てるようＫする。逆
にＣＮｓ＞ｘａ’）であれば、ポインタをその１１とす
る。

なお、（Ｎ３≦８３）の判断において、第２のポインタ
の個数Ｎ２を考慮しても良い。例えば、第３のポインタ
の個数Ｎｓに比べて１Ｉｉ２のポインタの個数Ｎ８に対
してより小さい重み付けがなされ、そのうえで両者の合
計の数が比較される。

（３）　２ワードエツーかどうかが謁ぺられる。２ワー
ドエラーであれば、演算によってエラーロケ求められる
。このエラーロケーション（１，ｊ）が共に、（０〜２
７）の範囲に含まれるかどうか検出される。この範囲外
のときは、２ワードエラーの訂正を行なうことができな
い。

そして、（Ｎ３≦柿）が成立するかどうかが判断される
。この冨・の値は、２〜３１１度である。

この条件が成立するときは、２ワードエラーと誤って検
出する割には、ポインタの個数が少なすぎるので、その
エラー訂正ブロック内に含まれる全てのワードに対して
、第３のポインタを付加する（オールポインタ）＠　（
Ｎｓ＞！＊）のときは、ポインタコピーの動作が前述と
同様になされる。

また、エラーロケーション（１，３）が共Ｋ。

（Ｏ〜２７）の範■にある場合には、これらに醜３のポ
インタが立っているかどうかが調べられる。この場合、
２ワードエラーの検出そのものが、ｖ４っているおそれ
がｌワードエラーの検出の場合と比べて大急いので、第
３のポインタのみが判断の対象とされる。１．１の何れ
にも、ポインタが立っていないときは、（Ｎ３≦工・）
かどうかが調べられる。ｚ６は例えば２である。これが
成立するときには、ｚ、３の何れにも、ポインタが立っ
ていない割には、ポインタの数が少な丁「るので、その
エラー訂正ブロックの全てのワードに対して第３のポイ
ンタが付加される（オールポインタ）。また、　（Ｎａ
＞ｉｓ）のときには、ポインタコピーがなされる。

エラーロケーション（傷、ｊ）の何れか一方にポインタ
が立っているときは、（Ｎ３≦ｚｙ）　（Ｎｒは例えば
３である）が調べられる。これが成立するとＩＫは、オ
ールポインタとされ、そうでないときは、ポインタコピ
ーが行なわれる。

エラーロケーション（１，Ｊ）の何れにもポインタが立
つズいるときには、　（Ｎｓ≦Ｘａ）（！Ｓは例えば４
である）が調べられる。（Ｎｓ≦Ｚａ）でアｔＬｋｉ、
　エラーロケーション１．１に関する２ワードエラーの
訂正が行なわれる。この訂正は。

エラーパターンｅｉ、ｅｊを前述のように求めることで
なされる。（Ｎｓ＞ｇｓ）のと自は、３ワ一ド以上のエ
ラーを２ワードエラーと−って検出しているおそれが高
いとして訂正を行なわず、ポインタコピーが行なわれる
。

（４）上述の（１）（２バ３）のどの場合にも咳轟しな
い即ち２レードをこえるエラーがある場合には、エラー
訂正が行なわれない。そして（Ｎｓ≦ｆｆ１ｘｏ）かど
うかが謁べられる＊　（Ｎｍ≦Ｊ６）であれば、ボイ／
りの信頼性が低いと判断し、オールポインタが行なわれ
る。（Ｎｍ＞ｇｘｏ）’であれば、ポインタをそのまま
としておく。

第７図及び第８図の夫々は１次段の復号におけるエラー
訂正の部分的変形の説明に用いるフローチャートである
。

第６図では、オールポインタとポインタコピーとの２通
りしかなかったが、第１及び第２のポインタの個数を考
慮することにより、一層細かな処場を行なうことができ
る。第７図に示すように。

まず、ｌｌｌ３のポインタの個数Ｎ３について、　　（
Ｎ３≦ｌ１ｌ）が調べられ、　（Ｎｓ＞ｇｔｔ）のよう
に、エラーワードが多いと自は、第３のポインタだけが
その壇１＊される。また、（Ｎ３≦冨１１）が成！する
ときには＊　（Ｎｓ　十Ｎ＊　十Ｎ３≦！１ｍ）につい
て詞ぺられる。

Ｉｌｌが４１ｊ度の値に対し、ｚ１８は、１０１１１度
の大きい値とされている。この関係が成立するときには
。

ポインタの信頼性が低いと判断され、そのブロックの食
てのワードに対して第３のポインタが付加される＠　　
（Ｎｌ十Ｎｚ＋８１）ｚｌｌ）のときは、ポインタの信
頼性が高いとされ、第１．第２．ｌｌｌ３のポインタが
食てそのオ盲とされる。

また、３ワ一ド以上のエラーが検出される場合において
、ポインタで示されるエラーロケーション（曇、ｊ、ｋ
）又は（１１ｊ、ｋｔＩ）を用いて３ワードエラー或い
は４ワードエツーを訂正するポインタイレージヤを行な
うようにしても良い。１１８図は。

この場合の７０−チャートを示している。３ワ一ド以上
のエラーと判定されたと１には、第１．第２、第３のポ
インタの合計が３又は４であるかどうかが調べられる。

（Ｎｌ　＋Ｎｚ　十ＮＢ　＝　３　（又は４））の場合
には、このポインタによって示されるエラーロケーショ
ン１．　Ｉｓ　ｋ、　（慮）を用いてエラーパターンを
求めるようになされる。上式の関係が成立しないときに
は、第３のポインタの個数Ｎ３が２（又は３）より少な
いかどうかが調べられる。（Ｎ３≦２（又は３））のと
きは、３ワ一ド以上のエラーの割には、ポインタの個数
が少なすぎるので、ポインタの信頼性が低いと判断され
、全てのり−ドに対してポインタが付加される。（Ｎｓ
＞２（又は３））の場合には、第２及び第３又は第３の
ポインタがその１１とされる。このように、ポインタイ
レージヤのときに、＠１のポインタを用いることによっ
て、誤った訂正、訂正不能の確率を減らすことができる
。

上述の第３図に示す誤り訂正デコーダでは、第１のチェ
ックワードＱｘｘｎ＊　Ｑ１ｓｎ＋ｔ　ｅ　Ｑｓｘ（ｔ
＋わＱｌ　ｇｎ＋ｓを用いたエラー訂正と第２のチェッ
クワードＰ１ｍ（ＩｔＰｉｆ！ｎ＋１＊　Ｐ１２ｒｒＨ
＊　Ｐ１１ｒｒ＋１を用いたエラー訂正とを夫＊１回ず
つ行なっている。この各エラー訂正を２回以上（実際的
には、２回１度）ずつ行なう１５にすれば、訂正された
結果のよりエラーが減少されたことを利用できるから、
エラー訂正能力をより増すことがで論る。このように、
更Ｋ１１ｌ＆に復号Ｉ１１を設ける場合には、復号器＋
２１１＠においてチェックワードの訂正も行なっておく
必要がある。

なお、上述の例では、インターリーバ（９）Ｋおける遅
鷺＠場として、遅鷺量をＤずつ異ならせるようにしたが
、このような規則的な遅蔦量の変化と異なり、不規、鋼
的なものとしても良い、また、第２のチェックワードＰ
ｉは、ＰＣＭ：ｙ′−夕のみならず、第１のチェックワ
ードＱｌをも含んで構成される誤り訂正符号である。こ
れと同様に、第１のチェックワードＱｌが第２のチェツ
タワードＰムをも含むようＫすることも可能である。臭
体的には。

＄２のチェックワードＰ１を帰還して第１１）チェック
ワードを形成する符号器に供給すれば良い。

仁のような帰還形の構成は、復号の回数を上述の１５Ｋ
ＩＳ回以上とする場合に対して有効である。

以上の説明から通解されるように、この発明に依ｔｔば
、クロスインターリーブによってバーストエラーを分散
させるよ５Ｋｔ、ているので、ランダムエラー及びバー
ストエラーの何れに対しても有効なエラー訂正を行なう
ことができる。また、２段以上の復号な行なう場合、前
段で複数種拳のポインタを付加しておき１次段では、こ
のポインタを、その償輌度の違いを考慮して利用するこ
とＫより、ｖ４つた訂正のおそれや、訂正不能となるお
それを軽減することができる。

なお、上述の一実施例では、エラー訂正符号として隣接
符号を用いたが、ｌワードエラーを訂正で龜、２ワード
エラー鷹で検出で龜るエラー訂正符号を用いるようにし
ても良い。

【図面の簡単な説明】

第１図はこの発明が適用された誤り訂正エンコーダの一
例のブロック図、ＪＩｇ図は伝送時の配列を示すブロッ
ク図、第３図は誤り訂正デコーダの一例のブロック図、
第４図、第５図及び第６図は誤り訂正デコーダの復号器
の動作の説明に用いる図、第７１！！Ｑ及び第８図の夫
々は誤り訂正デコーダの一部変形された復号器の動作の
説明に用いる図である。 （１）　（９）αυはインターリーバ、（８）α４Ｉは
符号器、　ａｅ（２）−はディンターリーバ、　ｃｌｌ
）＠は復号器である。

Claims (1)

1. 【特許請求の範囲】 １、　第１の配列＄ｌＩＫある複数チャンネルのＰＣＭ
   デー−系列の各々に食まれるｌワードとこれに対する第
   １のチェックワードとからなる第１のエラー訂正ブロッ
   クが形成され、上記複数チャンネルのＰＣＭデータ系列
   と第１のチェックワード系列をチャンネルごとＫＪＩＩ
   なる時間遅蔦させる仁とｋよって第２の配列状態とし、
   この第２の配列状態ＫＴｏｉ複数チャンネルのＰＣＭデ
   ータ系列とｊＩｌのチェックリード系列との各々に會壜
   れるｌワードとこれに対する第２のチェックワードとか
   らなる第２の工２−訂正プ鑓ツクが形成されたもののエ
   ラー訂正方法において、菖２のエラー訂正ブロックに対
   する初段の復号な行ない１次に第２の配列状態にある複
   数チャンネルのＰＣＭデータ系列と第１のチェツタワー
   ド系列とをチャンネルごとＫＪ％なる時間逼延させるこ
   とによって菖ｌの配列状態とし、この後に第１のエラー
   訂正プロッタに対する次段の復号な行なうようになし、
   上記初段の復号では、ＷＮ２のエラー訂正ブロック内の
   少なくともｌワードのエラーを訂正すると共に、２ワ一
   ド以上のエラーを検出し、この１７−ド訂正と２ワ一ド
   以上のエラー検出とを区別できる２種のポインタを各ワ
   ードに対して付加し、上記次段の復号で−は、第１のエ
   ラー訂正ブロック内Ｋｔｔｎるワードに関するエラーを
   訂正し、この訂正の退場で第１のエラー訂正プロッタ内
   に食１れる上記２種のポインタの個数、状態等をｖｌｇ
   ｌＪＬ、このｑ４Ｊ別結果によってエラー検出の見逃し
   、誤った訂正を防止することを特徴とするエラー訂正方
   法。 ２．２種のポインタのうちで、信頼度が高い一方のポイ
   ンタの第１のエラー訂正プａツク内に會筐れる個数を次
   段の復号において比較判別し。 訂正可能かどうかを判断することな特徴とする特許請求
   の範１１１Ｅ１項記載のエラー訂正方法。 ３、次段の復号でエラー訂正が不可能な場合において、
   使用したエラー訂正符号のポインタの信頼度に応じて、
   共通のエラー訂正ブロック内に含オれるワードの食てに
   ポインタを付加するか。 初段の復号で付加されたポインタをそのままとすること
   を特徴とする特許請求の範囲第１項記載のエラー訂正方
   法。