JPH047848B2 - - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、バーストエラー及びランダムエラ
ーの何れに対してもエラー訂正能力が高く、然も
エラー検出の見逃し又は誤つた訂正を生ずるおそ
れが低減されたエラー訂正方法に関する。

〔発明の概要〕 この発明は、エラー訂正時に用いるエラーロケ
ーシヨン多項式として、受信されたｎワードのデ
ータの中に２ワードのエラーがあるとして求め
た、 Aα²ⁱ＋Bαⁱ＋Ｃ＝０ 但し、ｉはエラーロケーシヨン を用いるようにしたもので、上式の係数Ａ，Ｂ，
Ｃを用いてエラー数及びエラーロケーシヨン、エ
ラー値を求めることができ、エラー訂正処理作業
の簡易化を図ることができる。

〔従来の技術〕

本願出願人は、先にバーストエラーに対して有
効なデータ伝送方法としてクロスインターリーブ
と称するものを提案している。これは、第１の配
列状態にある複数チヤンネルのPCMデータ系列
の各々に含まれる１ワードを第１のエラー訂正符
号器に供給することによつて第１のチエツクワー
ド系列を発生させ、この第１のチエツクワード系
列及び複数チヤンネルのPCMデータ系列を第２
の配列状態とし、夫々に含まれる１ワードを第２
のエラー訂正符号器に供給することによつて第２
のチエツクワード系列を発生させるもので、ワー
ド単位でもつて二重のインターリーブ（配列の並
び変え）を行なうものである。インターリーブ
は、共通のエラー訂正ブロツクに含まれるチエツ
クワード及びPCMデータを分散させて伝送し、
受信側において元の配列に戻したときに、共通の
エラー訂正ブロツクに含まれる複数ワードのうち
のエラーワード数を少なくしようとするものであ
る。つまり、伝送時にバーストエラーが生じると
きに、このバーストエラーを分散化することがで
きる。かかるインターリーブを二重に行なえば、
第１及び第２のチエツクワードの夫々が別々のエ
ラー訂正ブロツクを構成することになるので、チ
エツクワードの何れか一方でエラーを訂正できな
いときでも、その他方を用いてエラーを訂正する
ことができ、したがつてエラー訂正能力を一層向
上させることができる。

ところで、１ワード中の１ビツトでも誤つてい
るときには、１ワード全体が誤つているものとし
て取り扱われるので、ランダムエラーが比較的多
い受信データを扱う場合には、必ずしもエラー訂
正能力が充分であるとは言えない。

これは、例えば１ブロツク内の所定ワード例え
ば２ワードエラーまで検出訂正でき、エラーロケ
ーシヨンが判つているときには、それ以上の３ワ
ードエラー或いは４ワードエラーも訂正すること
ができる訂正能力の高い誤り訂正符号（隣接（ｂ
−adjacent）コードの一種）を上述の多重インタ
ーリーブと組合せることにより改善することがで
きる。

また、この誤り訂正符号は、１ワードエラーだ
けを訂正の対象とする場合には、復号器の構成を
頗る簡単とできる特徴を有している。

この種の誤り訂正符号について以下説明する。

誤り訂正符号を記述する場合、ベクトル表現或
いは巡回群による表現が用いられる。まず、GF
(2)上では、既約なｍ次の多項式Ｆ（ｘ）を考える。
“０”と“１”の元しか存在しない体GF(2)の上で
は、既約な多項式Ｆ（ｘ）は、根を持たない。そ
こで（Ｆ（ｘ）＝０）を満足する仮想的な根αを考
える。このとき、零元を含むαのべき乗で表わさ
れる2^m個の相異なる元０，α，α²，α³……α^2m-1
は、拡大体GF（2^m）を構成する。GF（2^m）は、
GF(2)の上のｍ次の既約多項式Ｆ（ｘ）を法とする
多項式環である。GF（2^m）の元は、１，α＝
｛ｘ｝，α²＝｛x²｝……α^m-1＝｛x^m-1｝の線形結合で
書き表わすことができる。即ち、 a₀＋a₁{x}＋a₂{x²}＋…＋a_n-1｛x^m-1｝ ＝a₀＋a₁α＋a₂α²＋…＋a_n-1α^m-1 あるいは（a_n-1，a_n-2…a₂，a₁，a₀）ここで、
a₀，a₁……a_n-1∈GF(2)となる。

一例として、GF（2⁸）を考えると、（mod.F
（ｘ）＝x⁸＋x⁴＋x³＋x²＋１）で全ての８ビツトの
データは a₇x⁷＋a₆x⁶＋a₅x⁵＋a₄x⁴＋a₃x³＋a₂x²＋a₁x＋
a₀又は（a₇，a₆，a₅，a₄，a₃，a₂，a₁，a₀）で書
きあらわせるので、例えばa₇をMSB側、a₀を
LSB側に割り当てる。a_oは、GF(2)に属するので、
０又は１である。

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

Ｔ＝０ ０ … ０ a₀ １ ０ … ０ a₁ ０ １ … ０ a₂ 〓 〓 〓 〓 ０ ０ … １ a_n-1 他の表現としては、巡回群を用いたものがあ
る。これは、GF（2^m）から０元を除く、残りの元
が位数2^m-1の乗法群をなすことを利用するもので
ある。GF（2^m）の元の巡回群を用いて表現すると ０，１（＝α^2m-1），α，α²，α³…α^2m-2 となる。

さて、この発明の一例では、ｍビツトを１ワー
ドとし、ｎワードで１ブロツクを構成するとき、
下記のパリテイ検査行列Ｈにもとづいてｋ個のチ
エツクワードを発生するようにしている。

Ｈ＝１ α^n-1 α^2(n-1) 〓 α^(K-1)(n-1) １ α^n-2 α^2(n-2) 〓 α^(K-1)(n-1) … … … … １ α α² 〓 α^K-1 １ １ １ 〓 １ また、行列Ｔによつても同様にパリテイ検査行
列Ｈを表現することができる。

Ｈ＝Ｉ T^n-1 T^2(n-1) 〓 T^(k-1)(n-1) Ｉ T^n-2 T^2(n-2) 〓 T^(k-1)(n-2) … … … … Ｉ Ｔ T² 〓 T^k-1 Ｉ Ｉ Ｉ 〓 Ｉ 但し、Ｉは、（ｍ×ｍ）の単位行列である。

上述のように、根αを用いた表現と生成行列Ｔ
を用いた表現とはお互いに類似している。

例えば、４個（ｋ＝４）のチエツクワードを用
いる場合を例にとると、パリテイ検査行列Ｈは Ｈ＝１ α^n-1 α^2(n-1) α^3(n-1) １ α^n-2 α^2(n-2) α^3(n-2) … … … … １ α α² α³ １ １ １ １ となる。受信データの１ブロツクを列ベクトルＶ
＝（W^^n-1，W^^n-2……W^₁，W^₀）（但しW^_i＝W_i＋e_i、
e_i：エラーパタン）とすると受信側で発生する４
個のシンドロームS₀，S₁，S₂，S₃は S₀ S₁ S₂ S₃＝Ｈ・V^T となる。この誤り訂正符号は、４ワードまでのエ
ラー訂正能力を有している。すなわち、ひとつの
エラー訂正ブロツク内の２ワードエラーまでのエ
ラー検出訂正が可能であり、エラーロケーシヨン
がわかつているときには、３ワードエラー又は４
ワードエラーの訂正が可能である。

１ブロツク中に４個のチエツクワード（ｐ＝
W₃，ｑ＝W₂，ｒ＝W₁，ｓ＝W₀）が含まれる。
このチエツクワードは、下記の４元連立方程式を
解けば求められる。但し、Σは、Σを意味する。

ｐ＋ｑ＋ｒ＋ｓ＝ΣW_i＝ａ α³p＋α²q＋αr＋ｓ＝ΣαⁱW_i＝ｂ α⁶p＋α⁴q＋α²r＋ｓ＝Σα²ⁱW_i＝ｃ α⁹p＋α⁶q＋α³r＋ｓ＝Σα³ⁱW_i＝ｄ 計算過程を省略し、結果のみを示すと、 ｐ ｑ ｒ ｓ＝α²¹² α¹⁵³ α¹⁵² α²⁰⁹ α¹⁵⁶ α² α¹³⁵ α¹⁵² α¹⁵⁸ α¹³⁸ α² α¹⁵³ α²¹⁸ α¹⁵⁸ α¹⁵⁶ α²¹²ａ ｂ ｃ ｄ となる。このようにしてチエツクワードｐ，ｑ，
ｒ，ｓを形成するのが送信側に設けれた符号器の
役目である。

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

〔1〕 エラーがない場合：S₀＝S₁＝S₂＝S₃＝０ 〔2〕 １ワードエラー（エラーロケーシヨンｉに
おけるエラーパターンをe_iとする）の場合：S₀
＝e_i，S₁＝αⁱe_i，S₂＝α²ⁱe_i，S₃＝α³ⁱe_iしたがつて αⁱS₀＝S₁ αⁱS₁＝S₂ αⁱS₂＝S₃ となり、ｉを順次変えたときに、この関係が成
立するかどうかで１ワードエラーかどうかを判
定できる。或いは S₁／S₀＝S₂／S₁＝S₃／S₂＝αⁱ となり、αⁱのパターンを予めROMに記憶され
ている変換テーブルを参照することにより、エ
ラーロケーシヨンｉが分かる。そのときのシン
ドロームS₀がエラーパターンe_iそのものとな
る。

〔3〕 ２ワードエラー（e_i，e_j）の場合 S₀＝e_i＋e_j S₁＝αⁱe_i＋α^je_j S₂＝α²ⁱe_i＋α^2je_j S₃＝α³ⁱe_i＋α^3je_j 上式を変形すると α^jS₀＋S₁＝（αⁱ＋α^j）e_i α^jS₁＋S₂＝αⁱ（αⁱ＋α^j）e_i α^jS₂＋S₃＝α²ⁱ（αⁱ＋α^j）e_i したがつて αⁱ（α^jS₀＋S₁）＝α^jS₁＋S₂ αⁱ（α^jS₁＋S₂）＝α^jS₂＋S₃ が成立すれば、２ワードエラーと判定され、エ
ラーロケーシヨンｉ，ｊが分かる。つまり、ｉ
及びｊの組合せを変えて、上式の関係が成立す
るかどうかを調べる。そのときのエラーパター
ンは e_i＝S₀＋α^-jS₁／１＋α^i-j e_j＝S₀＋α^-iS₁／１＋α^j-i 〔4〕 ３ワードエラー（e_i，e_j，e_k）の場合： S₀＝e_i＋e_j＋e_k S₁＝αⁱe_i＋α^je_j＋α^ke_k S₂＝α²ⁱe_i＋α^2je_j＋α^2ke_k S₃＝α³ⁱe_i＋α^3je_j＋α^3ke_k 上式を変形すると α^kS₀＋S₁＝（αⁱ＋α^k）e_i＋（^j＋α^k）e_j α^kS₁＋S₂ ＝αⁱ（αⁱ＋α^k）e_i＋α^j（α^j＋α^k）e_j α^kS₂＋S₃ ＝α²ⁱ（αⁱ＋α^k）e_i＋α^2j（α^j＋α^k）e_j したがつて α^j（α^kS₀＋S₁）＋（α^kS₁＋S₂） ＝（αⁱ＋α^j）（αⁱ＋α^k）e_i α^j（α^kS₁＋S₂）＋（α^kS₂＋S₃） ＝αⁱ（αⁱ＋α^j）（αⁱ＋α^k）e_i 上式から αⁱ（α^j（α^kS₀＋S₁）＋（α^kS₁＋S₂））＝ α^j（α^kS₁＋S₂）＋（α^kS₂＋S₃） が成立すれば、３ワードエラーと判定できる。
そのときの各エラーパターンは e_i＝S₀＋（α^-j＋α^-k）S₁＋α^-j-kS₂／（１＋α^i-j
（１＋α^i-k） e_j＝S₀＋（α^-k＋α^-i）S₁＋α^-k-iS₂／（１＋α^j-i
）（１＋α^j-k） e_k＝S₀＋（α^-i＋α^-j）S₁＋α^-i-jS₂／（１＋α^k-i
）（１＋α^k-j） で求められる。実際には、３ワードエラーの訂
正のための構成が複雑となり、訂正動作に要す
る時間も長くなる。そこでポインタによつて
ｉ，ｊ，ｋ，ｌのエラーロケーシヨンが分かつ
ている場合と組合せ、そのときのチエツク用に
上式を用い、エラー訂正演算を行なうことが実
用的である。

〔5〕 ４ワードエラー（e_i，e_j，e_k，e_l）の場合： S₀＝e_i＋e_j＋e_k＋e_l S₁＝αⁱe_i＋α^je_j ＋α^ke_k＋α^le_l S₂＝α²ⁱe_i＋α^2je_j ＋α^2ke_k＋α^2le_l S₃＝α³ⁱe_i＋α^3je_j ＋α^3ke_k＋α^3le_l 上式を変形すると e_i＝S₀＋（α^-j＋α^-k＋α^-l）S₁＋（α^-j-k＋α^-k
-l＋α^-l-j）S₂＋α^-j-k-lS₃／（１＋α^i-j）（１＋α^i
-k）（１＋α^i-l） e_j＝S₀＋（α^-k＋α^-l＋α^-i）S₁＋（α^-k-l＋α^-l
-i＋α^-i-k）S₂＋α^-k-l-iS₃／（１＋α^j-i）（１＋α^j
-k）（１＋α^j-l） e_k＝S₀＋（α^-l＋α^-i＋α^-j）S₁＋（α^-l-i＋α^-i
-j＋α^-j-l）S₂＋α^-l-i-jS₃／（１＋α^k-i）（１＋α^k
-j）（１＋α^k-l） e_l＝S₀＋（α^-i＋α^-j＋α^-k）S₁＋（α^-i-j＋α^-j
-k＋α^-k-i）S₂＋α^-i-j-kS₃／（１＋α^l-i）（１＋α^l
-j）（１＋α^l-k） ポインタによつてエラーロケーシヨン（ｉ，
ｊ，ｋ，ｌ）が分かつている場合には、上述の
演算によつてエラー訂正を行なうことができ
る。

また、特公昭56−20575号公報には次のような
エラー訂正方法が記載されている。

すなわち、これはリード・ソロモン符号の符号
語に対し、 σ（ｘ）＝x^e＋σ₁x^e-1＋……＋σ_e（ｅはエラー数）
で表わされるエラーロケーシヨン多項式を求め、
その根を計算することによりエラーの訂正をする
もので、次のステツプからなる。

上記符号語から複数のシンドロームS_iを発生
する。

下記の（ｉ）乃至（ｖ）の操作を行なつて上
記エラー数ｅを調べることにより、上記シンド
ロームS_iと上記エラーロケーシヨン多項式の係
数σ₁乃至σ_eとの関係を示す方程式S_i+e＋
σ₁S_i+e-1＋……＋σ_e-1S_i+1＋σ_eS_i＝０を解いて上
記係数σ₁乃至σ_eを計算する。

(i) すべてのシンドロームS_iが０であればｅ＝
０とする。

(ii) S₀≠０のときにσ＝S₁／S₀を計算して、こ
のときS₂＋σS₁＝S₃＝σS₂＝０であれば、ｅ
＝１とする。

(iii) S₀＝０及びS₁≠０のとき又は(ii)においてS₀
≠０及びS₂＋σS₂≠０のときに、 σ₁＝（S₁S₂＋S₀S₃）／（S₁ ²＋S₀S₂）、 σ₂＝（S₁S₃＋S₂ ²）／（S₁ ²＋S₀S₂）及び Ｄ＝S₄＋σ₁S₃＋σ₂S₂を計算して、Ｄ＝０であ
れば、ｅ＝２とする。

(iv) (ii)においてS₃＋σS₂≠０のとき、(iii)にお
い
てＤ≠０のとき、又はS₀＝S₁＝０及びS²≠０
のときには、ｅ＝３とする。

(v) S₀＝S₁＝S₂＝０であり且つ３ｉ５なる
或るｉについてS_i≠０であればｅ＞３とす
る。

上記エラーロケーシヨン多項式の根を計算し
てエラーロケーシヨン及びエラー値を算出し、
このエラーロケーシヨン及びエラー値を用いて
符号語のエラーを訂正する。

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

上述の従来技術のエラー訂正の基本的アルゴリ
ズムは、シンドロームS₀〜S₃を用いて第１ステツ
プでエラーの有無をチエツクし、第２ステツプで
１ワードエラーかどうかをチエツクし、第３ステ
ツプで２ワードエラーかどうかをチエツクするも
ので、２ワードエラーまでも訂正しようとすると
きには、全てのステツプを終了するまでに要する
時間が長くなり、特に２ワードエラーのエラーロ
ケーシヨンを求めるときにこのような問題が生じ
る。

また、エラーワード数がわかつた後に、エラー
ロケーシヨン多項式の根を計算してエラーロケー
シヨン及びエラー値を算出する処理も必要であ
り、訂正処理ステツプが多数必要で、この点でも
訂正処理時間が長くなる欠点がある。

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

この発明においては、例えば前記従来技術の前
者の例のようなエラー訂正符号を用いるエラー訂
正方法において、受信されたｎワードのデータ中
に２ワードのエラーがあるとして求めたエラーロ
ケーシヨン方程式 Aα²ⁱ＋Bαⁱ＋Ｃ＝０ 但しｉはエラーロケーシヨン の各項の係数Ａ，Ｂ，Ｃを上記夫々のシンドロー
ムから求め、この係数がＡ＝Ｂ＝Ｃ＝０の関係を
満たすときにはエラー無しあるいは１ワードエラ
ーが存在するものと判定し、上記関係を満たさな
いときには２ワード以上のエラーが存在するもの
と判定し、１ワードエラーが存在すると判定され
たときにはこの１ワードエラーを訂正し、２ワー
ド以上のエラーが存在すると判定されたときは上
記各係数Ａ，Ｂ，Ｃを使用して２ワードエラーは
訂正し、それ以上のエラーの存在を検出するよう
にする。

〔作用〕

係数Ａ，Ｂ，Ｃを求め、この係数がＡ＝Ｂ＝Ｃ
＝０を満たすか否かでエラーワード数がチエツク
される。また、この係数が用いられてエラーロケ
ーシヨン及びエラー値が求められる。

したがつて、エラー訂正処理作業が簡易化さ
れ、短時間になる。

〔実施例〕

この発明によるエラー訂正方法の一例を、前記
従来技術の前者のエラー訂正符号の符号語に適用
した場合に例にとつて説明する。

これは２ワードエラーの訂正を想定する場合に
適用して有効なもので、２ワードエラー（e_i，e_j）
の場合のシンドロームS₀，S₁，S₂，S₃に関する式
は、前述と同様に、 S₀＝e_i＋e_j S₁＝αⁱe_i＋α^je_j S₂＝α²ⁱe_i＋α^2je_j S₃＝α³ⁱe_i＋α^3je_j この式を変形すると （αⁱS₀＋S₁）（αⁱS₂＋S₃）＝（αⁱS₁＋S₂）² 更に変形して下記のエラーロケーシヨン方程式を
求める。

（S₀S₂＋S₁ ²）α²ⁱ＋（S₁S₂＋S₀S₃）αⁱ ＋（S₁S₃＋S₂ ²）＝０ ここで、各式の係数を S₀S₂＋S₁ ²＝Ａ S₁S₂＋S₀S₃＝Ｂ S₁S₃＋S₂ ²＝Ｃ とおく。上式の各係数Ａ，Ｂ，Ｃを用いることに
より２ワードエラーの場合のエラーロケーシヨン
を求めることができる。

〔1〕 エラーがない場合： Ａ＝Ｂ＝Ｃ＝０，S₀＝０，S₃＝０ のときにエラーがないと判定される。

〔2〕 １ワードエラーの場合： Ａ＝Ｂ＝Ｃ＝０，S₀≠０，S₃≠０ のときに１ワードエラーと判定される。（αⁱ＝
S₁／S₀）からエラーロケーシヨンｉが分かり、（e_i＝ S₀）を用いてエラー訂正がなされる。

〔3〕 ２ワードエラーの場合、 ２ワード以上のエラーの場合には、（Ａ≠０，
Ｂ≠０，Ｃ≠０）が成立し、その判定が頗る簡単
となる。また、このとき Aα²ⁱ＋Bαⁱ＋Ｃ＝０（但し、ｉ＝０〜（ｎ−１）） が成立している。ここで（Ｂ／Ａ＝Ｄ，Ｃ／Ａ＝Ｅ）と おくと Ｄ＝αⁱ＋α^j，Ｅ＝αⁱ・α^j であり α²ⁱ＋Dαⁱ＋Ｅ＝０ となる。ここで、２つのエラーロケーシヨンの差
がｔである、つまり（ｊ＝ｉ＋ｔ）とすると Ｄ＝αⁱ（１＋α^t），Ｅ＝α^2i+t と変形される。したがつて D²／Ｅ＝（１＋α^t）²／α^t＝α^-t＋α^t となる。ROMに（ｔ＝１〜（ｎ−１））の夫々
に関する、（α^-t＋α^t）の値を予め書込んでおき、
ROMの出力と受信ワードから演算された（D²／Ｅ） の値との一致を検出することでｔが求まる。も
し、この一致関係が成立しなければ、３ワード以
上のエラーである。そこで Ｘ＝１＋α^t Ｙ＝１＋α^-t＝D²／Ｅ＋Ｘ とおくことにより αⁱ＝Ｄ／Ｘ，α^j＝Ｄ／Ｙ となり、エラーロケーシヨンｉ及びｊが求められ
る。エラーパターンe_i，e_jは e_i＝（α^jS₀＋S₁）／Ｄ＝S₀／Ｙ＋S₁／Ｄ e_j＝（αⁱS₀＋S₁）／Ｄ＝S₀／Ｘ＋S₁／Ｄ と求められ、エラー訂正を行なうことができる。

上述の訂正アルゴリズムは、２ワードエラーの
訂正まで行なうときに、エラーロケーシヨンを求
めるのに要する時間を、基本的アルゴリズムに比
べて頗る短くすることができる。

なお、チエツクワードの数ｋをより増加させれ
ば、エラー訂正能力が一層向上する。例えば（ｋ
＝６）とすれば、６ワードまでのエラー訂正能力
を有する。すなわち、３ワードエラーまで検出訂
正でき、エラーロケーシヨンが分かつているとき
に、６ワードエラーまで訂正できる。

次に、この発明をオーデイオPCM信号の記録
再生に適用した具体例について図面を参照して説
明する。

第１図は、記録系に設けられる誤り訂正エンコ
ーダを全体として示すもので、その入力側にオー
デイオPCM信号が供給される。オーデイオPCM
信号は、左右のステレオ信号の夫々をサンプリン
グ周波数_s（例えば44.1〔ｋHz〕）でもつてサンプ
リングし、１サンプルを１ワード（２を補数とす
るコードで16ビツト）に変換することで形成され
ている。したがつて左チヤンネルのオーデイオ信
号に関しては、（L₀，L₁，L₂……）と各ワードが
連続するPCMデータが得られ、右チヤンネルの
オーデイオ信号に関しても（R₀，R₁，R₂……）
と各ワードが連続するPCMデータが得られる。
この左右のチヤンネルのPCMデータが夫々６チ
ヤンネルずつに分けられ、計12チヤンネルの
PCMデータ系列が入力される。所定のタイミン
グにおいては、（L_6o，R_6o，L_6o+1，R_6o+1，L_6o+2，
R_6o+2，L_6o+3，R_6o+3，L_6o+4，R_6o+4）の12ワード
が入力される。この例では、１ワードを上位８ビ
ツトと下位ビツトとに分け、12チヤンネルを更に
24チヤンネルとして処理している。PCMデータ
の１ワードを簡単のために、W_iとして表わし、
上位８ビツトに関しては、W_i，ＡとＡのサフイ
ツクスを付加し、下位８ビツトに関してはW_i，
ＢとＢのサフイツクスを付加して区別している。
例えばL_6oがW_12o，Ａ及びW_12o，Ｂの２つに分割
されることになる。

この24チヤンネルのPCMデータ系列がまず偶
奇インターリーバ(1)に対して供給される。（ｎ＝
０，１，２……）とすると、L_6o（＝W_12o，Ａ、
W_12o，Ｂ）、R_6o（＝W_12o+1，Ａ，W_12o+1，Ｂ）、
L_6o+2（＝W_12o+4，Ａ、W_12o+4，Ｂ）、R_6o+2（＝
W_12o+5，Ａ、W_12o+5Ｂ）、L_6o+4（＝W_12o+8，Ａ，
W_12o+8，Ｂ）、R_6o+4（＝W_12o+9，Ａ，W_12o+9，Ｂ）
の夫々が偶数番目のワードであり、これ以外が奇
数番目のワードである。偶数番目のワードからな
るPCMデータ系列の夫々が偶奇インターリーバ
１の１ワード遅延回路２Ａ，２Ｂ，３Ａ，３Ｂ，
４Ａ，４Ｂ，５Ａ，５Ｂ，６Ａ，６Ｂ，７Ａ，７
Ｂによつて１ワード遅延される。勿論、１ワード
より大きい例えば８ワードを遅延させるようにし
ても良い。また、偶奇インターリーバ１では、偶
数番目のワードからなる12個のデータ系列が第１
〜第12番目までの伝送チヤンネルを占め、奇数番
目のワードからなる12個のデータ系列が第13〜第
24番目までの伝送チヤンネルを占めるように変換
される。

偶奇インターリーバ１は、左右のステレオ信号
の夫々に関して連続する２ワード以上が誤り、然
もこのエラーが訂正不可能となることを防止する
ためのものである。例えば（L_i-1，L_i，L_i+1）と
連続する３ワードを考えると、L_iが誤つており、
然もこのエラーが訂正不可能な場合に、L_i-1又は
L_i+1が正しいことが望まれる。それは、誤つてい
るデータL_iを補正する場合において、前の正しい
ワードL_i-1でもつてL_iを補間（前値ホールド）し
たり、L_i-1及びL_i+1の平均値でもつてL_iを補間す
るためである。偶奇インターリーバ１の遅延回路
２Ａ，２Ｂ〜７Ａ，７Ｂは、隣接するワードが異
なるエラー訂正ブロツクに含まれるようにするた
めに設けられている。また、偶数番目のワードか
らなるデータ系列と奇数番目のワードからなるデ
ータ系列毎とに伝送チヤンネルをまとめているの
は、インターリーバしたときに、近接する偶数番
目のワードと奇数番目のワードとの記録位置間の
距離をなるべく大とするためである。

偶奇インターリーバ１の出力には、第１の配列
状態にある24チヤンネルのPCMデータ系列が現
れ、その夫々から１ワードずつが取り出されて符
号器８に供給され、第１のチエツクワードQ_12o，
Q_12o+1，Q_12o+2，Q_12o+3が形成される。第１のチ
エツクワードを含んで構成される第１のエラー訂
正ブロツクは、 （W_12o-12，Ａ、W_12o-12，Ｂ、W_12o+1-12，Ａ、
W_12o+1-12，Ｂ、W_12o+4-12，Ａ、W_12o+4-12，Ｂ、
W_12o+5-12，Ａ、W_12o+5-12，Ｂ、W_12o+8-12，Ａ、
W_12o+8-12，Ｂ、W_12o+9-12，Ａ、W_12o+9-12，Ｂ、
W_12o+2，Ａ、W_12o+2，Ｂ、W_12o+3，Ａ、W_12o+3，
Ｂ、W_12o+6，Ａ、W_12o+6，Ｂ、W_12o+7，Ａ、
W_12o+7，Ｂ、W_12o+10，Ａ、W_12o+10，Ｂ、
W_12o+11，Ａ、W_12o+11，Ｂ、Q_12o、Q_12o+1、
Q_12o+2、Q_12o+3） となる。第１の符号器８では、１ブロツクのワー
ド数：（ｎ＝28）、１ワードのビツト数：（ｍ＝
８）、チエツクワード数：（ｋ＝４）の符号化がな
されている。

この24個のPCMデータ系列と、４個のチエツ
クワード系列とがインターリーバ９に供給され
る。インターリーバ９では、偶数番目のワードか
らなるPCMデータ系列と奇数番目のワードから
なるPCMデータ系列との間にチエツクワード系
列が介在するように伝送チヤンネルの位置を変え
てから、インターリーブのための遅延処理を行な
つている。この遅延処理は、第１番目の伝送チヤ
ンネルを除く他の27個の伝送チヤンネルの夫々に
対して、1D，2D，3D，4D……26D，27D（但し、
Ｄは単位遅延量で例えば４ワード）の遅延量の遅
延回路を挿入することでなされている。

インターリーバ９の出力には、第２の配列状態
にある28個のデータ系列が現れ、このデータ系列
の夫々から１ワードずつが取り出されて符号器１
０に供給され、第２のチエツクワードP_12o，
P_12o+1，P_12o+2，P_12o+3が形成される。第２のチ
エツクワードを含んで構成される32ワードからな
る第２のエラー訂正ブロツクは、下記のものとな
る。

（W_12o-12，Ａ、W_12o-12(D+1)，Ｂ、
W_{12o+1-12(2D+1)}，Ａ、W_{12o+1-12(3D-1)}，Ｂ、
W_{12o+4-12(4D+1)}，Ａ、W_{12o+4-12(5D+1)}，Ｂ、
W_{12o+5-12(6D+1)}，Ａ、W_{12o+5-12(7D+1)}，Ｂ…
Q_12o-12(12D)、Q_{12o+1-12(13D)}、Q_{12o+2-12(14D)}、
Q_{12o+3-12(15D)}、…W_{12o+10-12(24D)}，Ａ、
W_{12o+10-12(25D)}，Ｂ、W_{12+11-12(26D)}，Ａ、
W_{12o+11-12(27D)}，BP_12o、P_12o+1、P_12o+2、P_12o+3） かかる第１及び第２のチエツクワードを含む32個
のデータ系例のうちで、偶数番目の伝送チヤンネ
ルに対して１ワードの遅延回路が挿入されたイン
ターリーバ１１が設けられており、また第２のチ
エツクワード系列に対してインバータ１２，１
３，１４，１５が挿入される。インターリーバ１
１によつてブロツク同士の境界にまたがるエラー
が訂正不可能となるワード数のエラーとなり易い
ことに対処している。また、インバータ１２〜１
５は、伝送時におけるドロツプアウトによつて１
ブロツク中の全てのデータが“０”となり、これ
を再生系において正しいものと判別してしまう誤
動作を防止するため設けられている。同様の目的
で第１のチエツクワード系列に対してもインバー
タを挿入するようにしても良い。

そして、最終的に得られる24個のPCMデータ
系列と８個のチエツクワード系列との夫々から取
り出された32ワード毎に直列化され、第２図に示
すように、その先頭に16ビツトの同期信号が付加
されて１伝送ブロツクとなされて伝送される。第
２図では、図示の簡単のため第ｉ番目の伝送チヤ
ンネルから取り出された１ワードをu_iとして表示
している。伝送系の具体的な例としては、磁気記
録再生装置、回転デイスク装置などがあげられ
る。

上述の符号器８は、前述したような誤り訂正符
号に関するもので、（ｎ＝28、ｍ＝８、ｋ＝４）
であり、同様の符号器１０は、（ｎ＝32、ｍ＝８、
ｋ＝４）である。

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

まず、奇数番目の伝送チヤンネルに対して１ワ
ードの遅延回路が挿入されたデインターリーバ１
６が設けられ、また、チエツクワード系列に対し
てインバータ１７，１８，１９，２０が挿入さ
れ、初段の復号器２１に供給される。復号器２１
では、第４図に示すように、パリテイ検査行列
H_c1と入力の32ワード（V^T）とから、シンドロー
ムS₁₀，S₁₁，S₁₂，S₁₃が発生され、これにもとづ
いてエラー訂正が行われる。αは（Ｆ（ｘ）＝x⁸＋
x⁴＋x³＋x²＋１）のGF（2⁸）の元である。復号器
２１からは、24個のPCMデータ系列と４個のチ
エツクワード系列とが現れ、このデータ系列の１
ワード毎にエラーの有無を示す少なくとも１ビツ
トのポインタ（エラーを含むときに“１”、そう
でないときに“０”）が付加されている。この第
４図及び後述の第５図において、並びに以下の説
明では、受信された１ワードW^_iを単位にW_iとし
て表わしている。

この復号器２１の出力データ系列がデインター
リーバ２２に供給される。デインターリーバ２２
は、誤り訂正エンコーダにおけるインターリーバ
９でなされる遅延処理をキヤンセルするためのも
ので、第１番目の伝送チヤンネルから第27番目の
伝送チヤンネルまでの夫々に（27D，26D，25D
……2D，1D）と遅延量が異ならされた遅延回路
が挿入されている。デインターリーバ２２の出力
が次段の復号器２３に供給される。復号器２３で
は、第５図に示すように、パリテイ検査行列H_c2
と入力の28ワードとから、シンドロームS₂₀，
S₂₁，S₂₂，S₂₃が発生され、これにもとづいてエ
ラー訂正が行なわれる。

かかる次段の復号器２３の出力に現れるデータ
系列が偶奇デインターリーバ２４に供給される。
偶奇デインターリーバ２４では、偶数番目のワー
ドからなるPCMデータ系列と奇数番目のワード
からなるPCMデータ系列とが互いちがいの伝送
チヤンネルに位置するように戻されると共に、奇
数番目のワードからなるPCMデータ系列に対し
て１ワード遅延回路が挿入されている。この偶奇
デインターリーバ２４の出力には、誤り訂正エン
コーダの入力に供給されるのと全く同様の配列と
所定番目の伝送チヤンネルとを有するPCMデー
タ系列が得られることになる。第３図では、図示
されてないが、偶奇デインターリーバ２４の次に
補正回路が設けられており、復号器２１，２３で
訂正しきれなかつたエラーを目立たなくするよう
な補正例えば平均値補間が行なわれる。

この発明の一例では、初段の復号器２１におい
て１ワードエラーまで訂正するようにしている。
そして、ひとつのエラー訂正ブロツク内において
２ワード以上のエラーがあると検出された場合に
は、このエラー訂正ブロツク内の32ワード又はチ
エツクワードを除く28ワードの全てのワードに対
してエラーがあることを示す少なく共１ビツトの
ポインタを付加する。このポインタは、例えばエ
ラーがあるときには、“１”、そうでないときに
は、“０”とされるものである。なお、初段の復
号の際、上述の所定のワード数を訂正した場合に
おいてもエラーが存在したことを示すポインタを
付加するようにしてもよい。

１ワードが８ビツトの場合には、最上位ビツト
の更に上位の１ビツトとしてポインタが付加さ
れ、１ワードが９ビツトとなされ、デインターリ
ーバ２２で処理されて次段の復号器２３に供給さ
れる。

次段の復号器２３においては、このポインタに
よつて示される第１のエラー訂正ブロツク内のエ
ラーワードの個数又はエラーロケーシヨンを用い
てエラー訂正を行なう。第６図は、この次段の復
号器２３におけるエラー訂正の一例を示してお
り、第６図及び以下の説明では、ポインタによる
エラーワードの個数をN_pで表わし、ポインタに
よるエラーロケーシヨンをE_iで表わす。また、第
６図において、Ｙは肯定を表わし、Ｎは否定を表
わす。

(1) エラーの有無をシンドロームS₂₀〜S₂₃によつ
て調べる。（S₂₀＝S₂₁＝S₂₂＝S₂₃＝０）のとき
は、エラーなしとする。その場合、（N_p≦z₁）
かどうかを調べる。（N_p≦z₁）であれば、エラ
ーなしと判定して、そのエラー訂正ブロツク内
のポインタをクリア（“０”）とする。（N_p＞
z₁）であれば、シンドロームによる検出が誤つ
ているものとしてポインタをそのままとしてお
くか、そのブロツク内の全てのワードのポイン
タを“１”にする。z₁としては、かなり大きく
例えば14とする。

(2) エラーがある場合にシンドロームの演算によ
つて１ワードエラーかどうかを調べる。１ワー
ドエラーの場合に、エラーロケーシヨンｉを求
める。このシンドロームの演算により求められ
たエラーロケーシヨンｉがポインタによるもの
と一致するかどうかが検出される。ポインタに
よるエラーロケーシヨンが複数個あるときは、
その何れかと一致するかどうかが調べられる。
（ｉ＝E_i）であれば、次に（N_p≦z₂）かどうか
が調べられる。z₂は例えば10である。（N_p≦
z₂）であれば、これは１ワードエラーと判断
し、１ワードエラーの訂正を行なう。（N_p＞
z₂）であれば、１ワードエラーと判断すること
は危険なので、ポインタをそのままとしておく
か、又は全てのワードをエラーとみなして各ポ
インタを“１”とする。

（ｉ≠E_i）の場合には、（N_p≦z₃）かどうか
が調べられる。z₃はかなり小さい数で例えば３
である。（N_p≦z₃）が成立するときは、シンド
ロームの演算でもつてエラーロケーシヨンｉに
ついての１ワードエラーを訂正する。

（N_p＞z₃）の場合では、更に（N_p≦z₄）か
どうかが調べられる。つまり、（z₃＜N_p≦z₄）
のときは、シンドロームによる１ワードエラー
の判定が誤つている割には、N_pが小さすぎる
ことを意味するから、そのブロツクの全ワード
のポインタを“１”とする。逆に（N_p＞z₄）
であれば、ポインタをそのままとする。z₄は例
えば５である。

(3) １ワードエラーでもない場合では、（N_p≦
z₅）かどうかが判断され、（N_p≦z₅）のとき
は、ポインタの信頼性が乏しいので、全てのワ
ードのポインタを“１”とする。（N_p＞z₅）の
ときは、ポインタをそのままとする。

(4) 第６図で破線で示すように、ポインタによる
エラーロケーシヨンを用いてＭワードまでの訂
正を行なうようにしても良い。例えば４ワード
エラーまでの訂正が可能である。この場合、ポ
インタによつて示されるエラーロケーシヨンに
基づいてエラーの訂正を行なう。（N_p≠Ｍ）の
場合には、ポインタをそのままとしておくか、
又は全てのワードのポインタを、エラーを示す
ものに変える。

なお、１ブロツク内のエラーを示すポインタの
個数N_pに対する比較値z₁〜z₅の具体的数値は、
あくまで一例である。上述の例におけるエラー訂
正符号は、５ワードエラー以上の場合に、これを
エラーなしと判断するおそれがあり、また４ワー
ドエラー以上の場合にはこれを１ワードエラーと
判断するおそれがあるので、このような見逃し又
は誤つた訂正が生じる確率などを考慮して比較値
を適切な値とすることができる。

この第３図に示す誤り訂正デコーダでは、第１
のチエツクワードQ_12o，Q_12o+1，Q_12o+2，Q_12o+3
を用いてエラー訂正と第２のチエツクワード
P_12o，P_12o+1，P_12o+2，P_12o+3を用いたエラー訂正
とを夫々１回ずつ行なつている。この各エラー訂
正を２回以上（実際的には、２回程度）ずつ行な
うようにすれば、訂正された結果のよりエラーが
減少されたことを利用できるから、エラー訂正能
力をより増すことができる。このように、更に後
段に復号器を設ける場合には、復号器２１，２３
においてチエツクワードの訂正も行なつておく必
要がある。

なお、上述の例では、インターリーバ９におけ
る遅延処理として、遅延量をＤずつ異ならせるよ
うにしたが、このような規則的な遅延量の変化と
異なり、不規則的なものとしても良い。また、第
２のチエツクワードP_iは、PCMデータのみなら
ず、第１のチエツクワードQ_iをも含んで構成され
る誤り訂正符号である。これと同様に、第１のチ
エツクワードQ_iが第２のチエツクワードP_iをも含
むようにすることも可能である。具体的には、第
２のチエツクワードP_iを帰還して第１のチエツク
ワードを形成する符号器に供給すれば良い。

なお、初段の復号器２１において１ワードエラ
ーを訂正したときでも、この訂正された１ワード
が含まれるエラー訂正ブロツク内の全てのワード
のポインタを“１”とすれば、より一層検出ミ
ス、誤つた訂正を行なうおそれを防止できる。

〔発明の効果〕

この発明によれば、エラーロケーシヨン多項式
として受信されたデータの中に２ワードのエラー
があるとして求めた Aα²ⁱ＋Bαⁱ＋Ｃ＝０ を用いるようにしたことにより、この式の係数
Ａ，Ｂ，Ｃを用いてエラー数のチエツクが簡単に
できる。また、この係数Ａ，Ｂ，Ｃはエラーロケ
ーシヨン及びエラー値を求める演算にも使用され
る。したがつて、エラー訂正作業が簡易化され、
処理時間を短くすることができる。

【図面の簡単な説明】

第１図は本発明が適用された誤り訂正エンコー
ダの一例のブロツク図、第２図は伝送時の配列を
示すブロツク図、第３図は誤り訂正デコーダの一
例のブロツク図、第４図，第５図及び第６図は誤
り訂正デコーダの復号器の動作の説明に用いる図
である。 １，９，１１はインターリーバ、８，１０は符
号器、１６，２２，２４はデインターリーバ、２
１，２３は復号器である。

Claims (1)

1. 【特許請求の範囲】 １ ｎワードで１ブロツクを構成し、パリテイ行
   列Ｈを、 Ｈ＝１ α^n-1 α^2(n-1) α^3(n-1) １ α^n-2 α^2(n-2) α^3(n-2) … … … … １ α α² α³ １ １ １ １ 但しαはGF(2)上の既約多項式をＦ（ｘ）とする
   ときにＦ（ｘ）＝０を満足する根である。 と表現したときに、 受信されたｎワードからなる１ブロツクのデー
   タV^Tと上記パリテイ検査行列Ｈとから Ｈ・V^T＝S₀ S₁ S₂ S₃ の演算によつて４個のシンドロームS₀，S₁，S₂，
   S₃を求め、このシンドロームに基づいてエラーを
   訂正する方法において、 上記受信されたｎワードのデータ中に２ワード
   のエラーがあるとして求めたエラーロケーシヨン
   方程式 Aα²ⁱ＋Bαⁱ＋Ｃ＝０ 但しｉはエラーロケーシヨン の各項の係数Ａ，Ｂ，Ｃを上記それぞれのシンド
   ロームから求め、 この係数がＡ＝Ｂ＝Ｃ＝０の関係を満たすとき
   には、上記シンドロームを用いてエラー無しか１
   ワードエラーが存在するかを判定し、１ワードエ
   ラーが存在すると判定されたときには、上記シン
   ドロームを用いてこの１ワードエラーを訂正し、 上記各項の係数が上記関係を満たさないとき
   は、上記各項の係数を用いて２ワードエラーが存
   在するかそれ以上のエラーが存在するかを判定
   し、２ワードエラーが存在すると判定されたとき
   には、上記各項の係数を用いて２ワードエラーを
   訂正するようにしたことを特徴とするエラー訂正
   方法。 ２ エラーロケーシヨン多項式を α²ⁱ＋Dαⁱ＋Ｅ＝０ 但しｉはエラーロケーシヨン としたときの各項の係数Ｄ，Ｅ及びD²／Ｅを上
   記係数Ａ，Ｂ，Ｃを用いて求め、このD²／Ｅと
   ２ワードエラーが存在するとしたときのそのエラ
   ーロケーシヨンの差ｔとの関係式を満たすときに
   は２ワードエラーが存在すると判定するようにし
   た特許請求の範囲第１項記載のエラー訂正方法。 ３ 特許請求の範囲第２項においてD²／Ｅとエ
   ラーロケーシヨンの差ｔとの関係式とは D²／Ｅ＝α^-t＋α^tであるエラー訂正方法。 ４ 特許請求の範囲第２項において、エラーロケ
   ーシヨンの差ｔと係数Ｄに基づいて夫々のエラー
   ロケーシヨンを求め、このエラーロケーシヨンで
   指示されるエラーを訂正するようにしたエラー訂
   正方法。 ５ 夫々のエラーロケーシヨンをｉ，ｊとすると
   きにこのエラーロケーシヨンｉ，ｊは αⁱ＝Ｄ／１＋α^t α^j＝Ｄ／１＋α^-t から求めるようにした特許請求の範囲第４項記載
   のエラー訂正方法。 ６ ２ワードエラーが存在するときの夫々のエラ
   ーロケーシヨンをｉ，ｊとするときに夫々のエラ
   ーパターンe_i，e_jを係数Ｄを用いて求め、このエ
   ラーパターンに基づいてエラー訂正を行なう特許
   請求の範囲第２項記載のエラー訂正方法。 ７ エラーパターンe_iは、 α^jS₀＋S₁／Ｄ あるいはエラーロケーシヨンの差ｔを用いて S₀／Ｙ＋S₁／Ｄ 但しＹ＝１＋α^-t によつて求め、またエラーパターンe_iは αⁱS₀＋S₁／Ｄ あるいはエラーロケーシヨンの差ｔを用いて S₀／Ｘ＋S₁／Ｄ 但しＸ＝１＋α^t によつて求められる特許請求の範囲第６項記載の
   エラー訂正方法。