JPS6246893B2 - - Google Patents

Description

【発明の詳細な説明】

本発明は、１ブロツク内の２ワードエラーまで
訂正できる誤り訂正符号（隣接符号の一種）を用
いたエラー訂正方法に関し、特にエラー訂正を高
速に行なうことができるようにしたものである。 まず、本発明に用いる誤り訂正符号について説
明する。誤り訂正符号を記述する場合、ベクトル
表現或いは巡回群による表現が用いられる。ま
ず、GF(2)上では、既約なｍ次の多項式Ｆ_(x)を考
える。 “０”と“１”の元しか存在しない体GF(2)の
上では、既約な多項式Ｆ_(x)は、根を持たない。
そこで（Ｆ_(x)＝０）を満足する仮想的な根αを
考える。このとき、零元を含むαのべき乗で表わ
される２^m個の相異なる元０、α、α^２、α^３…
…α^m-1は、拡大体GF（２^m）を構成する。GF
（２^m）は、GF(2)の上のｍ次の既約多項式Ｆ_(x)を
法とする多項式環であるGF（２^m）の元は、１，
α＝｛ｘ｝，α^２＝｛x²｝，……，α^m-1＝｛ｘ^m-1｝
の線形結合でかきあらわすことができる。即ち a₀＋a₁｛ｘ｝＋a₂｛x²｝＋……＋ａ_n-1｛ｘ^m-1｝ ＝a₀＋a₁α＋a₂α^２＋………＋ａ_n-1α^m-1 あるいは（ａ_n-1，ａ_n-2，……，a₂，a₁，a₀）ここ
で、a₀，a₁，……，ａ_n-1∈GF_(P)となる。 一例として、GF（2⁸）を考えると、（mod.F_(x)
＝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₇をMSB側、a₀をLSB側に割り
当てる。ａ_oは、GF(2)に属するので、０又は１で
ある。 また、多項式Ｆ_(x)から（ｍ×ｍ）の下記の行
列Ｔが導かれる。 他の表現としては、巡回群を用いたものがあ
る。 これは、GF（２^m）から０元を除く、残りの元
が位数２^m−１の乗法群をなすことを利用するも
のである。GF（２^m）の元を巡回群を用いて表現
すると ０，１（＝α^2m-1），α，α^２，α^３，……α^2
ｍ−２ となる。 さて、本発明の一例では、ｍビツトを１ワード
とし、ｎワードで１ブロツクを構成するとき、下
記のパリテイ検査行列Ｈにもとずいてｋ個のチエ
ツクワードを発生するようにしている。 また、行列Ｔによつても同様にパリテイ検査行
列Ｈを表現することができる。 但し、Ｉは、（ｍ×ｍ）の単位行列である。 上述のように、根αを用いた表現と生成行列Ｔ
を用いた表現との両者は本質的に同一である。 更に、４個（ｋ＝４）のチエツクワードを用い
る場合を例にとると、パリテイ検査行列Ｈは となる。受信データの１ブロツクを列ベクトルＶ
＝（Ｗ_o-1，Ｗ_o-2，……，W₁，W₀）（但しWi＝Wi
＋eiei：エラーパターン）とすると受信側で発生
する４個のシンドロームS₀，S₁，S₂，S₃は となる。この誤り訂正符号は、ひとつのエラー訂
正ブロツク内の２ワードエラーまでのエラー訂正
が可能であり、エラーロケーシヨンがわかつてい
るときには、３ワードエラー又は４ワードエラー
の訂正が可能である。 １ブロツク中に４個のチエツクワード（ｐ＝
W₃，ｑ＝W₂，ｒ＝W₁，ｓ＝W₀）が含まれる。こ
のチエツクワードは、下記のようにして求められ
る。但し、Σは、

【式】を意味する。 ｐ＋ｑ＋ｒ＋ｓ＝ΣWi＝ａ α³p＋α²q＋αｒ＋ｓ＝ΣαⁱWi＝ｂ α⁶p＋α⁴q＋α²r＋ｓ＝Σα²ⁱWi＝ｃ α⁹p＋α⁶q＋α³r＋ｓ＝Σα³ⁱWi＝ｄ 計算過程を省略し、結果のみを示すと となる。このようにしてチエツクワードｐ，ｑ，
ｒ，ｓを形成するのが送信側に設けられた符号器
の役目である。 次に、上述のように形成されたチエツクワード
を含むデータが伝送され、受信された場合のエラ
ー訂正の基本的アルゴリズムについて説明する。 〔１〕 エラーがない場合：S₀＝S₁＝S₂＝S₃＝０ 〔２〕 １ワードエラー（エラーパターンをeiと
する）の場合：S₀＝ei S₁＝αⁱei S₂＝α²ⁱei S₃
＝α³ⁱei したがつて αⁱS₀＝S₁ αⁱS₁＝S₂ αⁱS₂＝S₃ となり、ｉを順次変えたときに、上記の関係が成
立するかどうかで１ワードエラーかどうかを判定
することができる。或いは Ｓ_０／Ｓ_１＝Ｓ_２／Ｓ_１＝Ｓ_３／Ｓ_２＝αⁱ となり、αⁱのパターンを予めROMに記憶されて
いるものと比較してエラーロケーシヨンｉが分か
る。そのときのシンドロームS₀がエラーパターン
eiそのものとなる。 〔３〕 ２ワードエラー（ei，ej）の場合 S₀＝ei＋ej S₁＝αⁱei＋α^jej S₂＝α²ⁱei＋α^2jej S₃＝α³ⁱei＋α^3jej 上式を変形すると α^jS₀＋S₁＝（αⁱ＋α^j）ei α^jS₁＋S₂＝αⁱ＋（αⁱ＋α^j）ei α^jS₂＋S₃＝α²ⁱ（αⁱ＋α^j）ei したがつて αⁱ（α^jS₀＋S₁）＝α^jS₁＋S₂ αⁱ（α^jS₁＋S₂）＝α^jS₂＋S₃ が成立すれば、２ワードエラーと判定され、エラ
ーロケーシヨンｉ，ｊが分かる。つまり、ｉ及び
ｊの組合せを変えて上式の関係が成立するかどう
かを調べる。そのときのエラーパターンは ei＝Ｓ_０＋α^−ｊＳ_１／１＋α^ｉ−ｊ ej＝Ｓ_０＋
α^−ｉＳ_１／１＋α^ｊ−ｉ 〔４〕 ３ワードエラー（ei，ej，ek）の場合 S₀＝ei＋ej＋ek S₁＝αⁱei＋α^jei＋α^kek S₂＝α²ⁱei＋α^2jej＋α^2kek S₃＝α³ⁱei＋α^3jej＋α^3kek 上式を変形すると α^kS₀＋S₁＝（αⁱ＋α^k）ei＋（α^j＋α^k）ej α^kS₁＋S₂＝αⁱ（α_i＋α^k）ei＋α^j（α^j＋α^k）ej α^kS₂＋S₃＝α_2i（αⁱ＋α^k）ei＋α^2j（α^j＋α^k）ej したがつて α^j（α^kS₀＋S₁）＋（α^kS₁＋S₂）＝（αⁱ＋α^j）（αⁱ＋α^k）ei α^j（α^kS₁＋S₂）＋（α^kS₂＋S₃）＝αⁱ（αⁱ＋α^j）（αⁱ＋α^k）ei 上式から αⁱ（α^j（α^kS₀＋S₁）＋（α^kS₁＋S₂））＝α^j（α^kS₁＋S₂）＋（α^kS₂＋S₃） が成立すれば、３ワードエラーと判定できる。但
し、（S₀≠０，S₁≠０，S₂≠０）であることを条
件としている。そのときの各エラーパターンは ei＝Ｓ_０＋（α^−ｊ＋α^−ｋ）Ｓ_１＋α^−ｊ＋ｋＳ
_２／（１＋α^ｉ−ｊ）（１＋α^ｉ−ｋ） ej＝Ｓ_０＋（α^−ｋ＋α^−ｉ）Ｓ_１＋α^−ｋ−ｉＳ
_２／（１＋α^ｊ−ｉ）（１＋α^ｊ−ｋ） ek＝Ｓ_０＋（α^−ｉ＋α^−ｊ）Ｓ_１＋α^−ｉ−ｊＳ
_２／（１＋α^ｋ−ｉ）（１＋α^ｋ−ｊ） で求められる。実際には、３ワードエラーの訂正
のための構成が複雑となり、訂正動作に要する時
間も長くなる。そこでポインタによつてｉ，ｊ・
ｋのエラーロケーシヨンが分かつている場合と組
合せ、そのときのチエツク用に上式を用い、エラ
ー訂正動作を行なうことが実用的である。 〔５〕 ４ワードエラー（ei，ej，ek，el）の場
合： S₀＝ei＋ej＋ek＋el S₁＝αⁱei＋α^jej＋α^kek＋α^lel S₂＝α²ⁱei＋α^2jej＋α^2kek＋α^2lel S₃＝α³ⁱei＋α^3jej＋α^3kek＋α^3lel 上式を変形すると ei＝Ｓ_０＋（α^−ｊ＋α^−ｋ＋α^−ｌ）Ｓ_１＋（α^−ｊ−ｋ＋α^−ｋ−ｌ＋α^−ｌ−ｊ）Ｓ_２＋α^{−ｊ−ｋ−ｌ}
Ｓ_３／（１＋α^ｉ−ｊ）（１＋α^ｉ−ｋ）（１＋α^ｉ−ｌ） ej＝Ｓ_０＋（α^−ｋ＋α^−ｌ＋α^−ｉ）Ｓ_１＋（α^−ｋ−ｌ＋α^−ｌ−ｉ＋α^−ｉ−ｋ）Ｓ_２＋α^{−ｋ−ｌ−ｉ}
Ｓ_３／（１＋α^ｊ−ｉ）（１＋α^ｊ−ｋ）（１＋α^ｊ−ｌ） ek＝Ｓ_０＋（α^−ｌ＋α^−ｉ＋α^−ｊ）Ｓ_１＋（α^−ｌ−ｉ＋α^−ｉ−ｊ＋α^−ｊ−ｌ）Ｓ_２＋α^{−ｌ−ｉ−ｊ}
Ｓ_３／（１＋α^ｋ−ｉ）（１＋α^ｋ−ｊ）（１＋α^ｋ−ｌ） el＝Ｓ_０＋（α^−ｉ＋α^−ｊ＋α_−ｋ）Ｓ_１＋（α^−ｉ−ｊ＋α^−ｊ−ｋ＋α^−ｋ−ｉ）Ｓ_２＋α^{−ｉ−ｊ−ｋ}
Ｓ_３／（１＋α^ｌ−ｉ）（１＋α^ｌ−ｊ）（１＋α^ｌ−ｋ） ポインタによつてエラーロケーシヨン（ｉ，
ｊ，ｋ，ｌ）が分かつている場合には、上述の演
算によつてエラー訂正を行なうことができる。 上述のエラー訂正の基本的アルゴリズムは、シ
ンドロームS₀〜S₃を用いて第１ステツプでエラー
の有無をチエツクし、第２ステツプで１ワードエ
ラーかどうかをチエツクし、第３ステツプで２ワ
ードエラーかどうかをチエツクするもので、２ワ
ードエラーまでも訂正しようとするときには、全
てのステツプを終了するまでに要する時間が長く
なり、特に２ワードエラーのエラーロケーシヨン
を求めるときにこのような問題が生じる。 本発明は、かかる問題点が解決され、高速のエ
ラー訂正動作が可能なエラー訂正方法を提案せん
とするものである。 以下、本発明について説明すると、２ワードエ
ラー（ei＋ej）の場合のシンドロームS₀，S₁，
S₂，S₃に関する式は、前述と同様に S₀＝ei＋ej S₁＝αⁱei＋α^jej S₂＝α²ⁱei＋α^2jej S₃＝α³ⁱei＋α^3jej この式を変形すると （αⁱ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₂ ²＝Ｃ とおく。上式の各係数Ａ，Ｂ，Ｃを用いることに
より２ワードエラーの場合のエラーロケーシヨン
を求めることができる。 〔１〕 エラーがない場合： Ａ＝Ｂ＝Ｃ＝０，S₀＝０，S₃＝０ 〔２〕 １ワードエラーの場合： Ａ＝Ｂ＝Ｃ＝０，S₀≠０，S₃≠０ のときに１ワードエラーと判定される。（αⁱ＝
Ｓ_１／Ｓ_０）からエラーロケーシヨンｉが分かり、（ei
＝ S₀）を用いてエラー訂正がなされる。 〔３〕 ２ワードエラーの場合： ２ワード以上のエラーの場合には、（Ａ≠０，
Ｂ≠０，Ｃ≠０）が成立し、その判定が頗る簡単
となる。 また、このとき Ａα²ⁱ＋Ｂαⁱ＋Ｃ＝０
（但し、ｉ＝０〜（ｎ−１）） が成立している。ここで（Ｂ／Ａ＝Ｄ，Ｃ／Ａ＝Ｅ）と
お くと Ｄ＝αⁱ＋α^j，Ｅ＝αⁱ・α^j であり α²ⁱ＋Ｄαⁱ＋Ｅ＝０ となる。ここで、２つのエラーロケーシヨンの差
がｔであるつまり（ｊ＝ｉ＋ｔ）とすると Ｄ＝αⁱ（１＋α^t），Ｅ＝α^2i+t と変形される。したがつて Ｄ^２／Ｅ＝（１＋α^ｔ）^２／α^ｔ＝α^-t＋α^t となる。ROMに（ｔ＝１〜（ｎ−１））の夫々に
関する、α^-t及びα^tの値を予め書込んでおき、
ROMの出力から求められた（α^-t＋α^t）と受信
ワードから演算された（Ｄ^２／Ｅ）の値との一致を検 出することでｔが求まる。もし、この一致関係が
成立しなければ、３ワード以上のエラーである。
そこで Ｘ＝１＋α^t Ｙ＝１＋α^-t＝Ｄ^２／Ｅ＋Ｘ とおくことにより αⁱ＝Ｄ／Ｘ，α^j＝Ｄ／Ｙ となり、エラーロケーシヨンｉ及びｊが求められ
る。エラーパターンei，ejは ei＝（α^ｊＳ_０＋Ｓ_１）／Ｄ＝Ｓ_０／Ｙ＋Ｓ_１／Ｄ ej＝（α^ｉＳ_０＋Ｓ_１）／Ｄ＝Ｓ_０／Ｘ＋Ｓ_１／Ｄ と求められ、エラー訂正を行なうことができる。 図は、本発明が適用されたエラー訂正装置の一
例を示しており、１で示す入力端子に受信された
データが供給され、バツフアメモリ２及びシンド
ローム発生回路３に供給される。バツフアメモリ
２は、エラー検出及びエラーパターンの発生のた
めに必要とする時間、受信データを遅延させるも
ので、バツフアメモリ２の出力がエラー訂正回路
（mod.2の加算器）４に供給される。このエラー
訂正回路４の出力が出力端子５に取り出される。 シンドローム発生回路３にて（Ｈ・Ｖ^T）の演
算が行なわれ、シンドロームS₀〜S₃が形成され、
このシンドロームがGF（２^m）の演算回路６に与
えられる。この演算回路６は、係数Ａ，Ｂ，Ｃ，
Ｄ，Ｅを発生する演算とエラーパターンを発生す
る演算とを行なう。演算回路６からの係数がバツ
フアレジスタ７に貯えられ、エラーパターンがバ
ツフアレジスタ８に貯えられる。このバツフアレ
ジスタ８からのエラーパターンがエラー訂正回路
４に供給されることで、エラー訂正がなされる。
また、エラーロケーシヨンデコーダ９及びROM
１０が設けられており、バツフアレジスタ７から
の係数Ｄ，ＥとROM１０からの出力α^t，α^-tと
を用いることによつてエラーロケーシヨンｉと新
たな係数Ｘ，Ｙとがエラーロケーシヨンデコーダ
９において形成される。この新たな係数Ｘ，Ｙと
バツフアレジスタ７からの係数Ｄとシンドローム
とが演算回路６に供給されることによつてエラー
パターンei，ejが形成され、このエラーパターン
がバツフアレジスタ８に貯えられる。 また、シンドローム発生回路３からのシンドロ
ームS₀，S₃とバツフアレジスタ７からの係数Ａ，
Ｂ，Ｃがエラー判定回路１１に供給され、エラー
の有無、１ワードエラーかどうか、２ワードエラ
ーかどうか、又はそれ以上のエラーかどうかが判
別される。この判定結果がコントローラ１２に与
えられる。コントローラ１２は、各回路に対して
クロツクパルス或いは所定のタイミング関係に規
定された制御信号を供給するものである。 上述の説明から理解されるように、本発明によ
れば、ROMにα^-t，α^t（ｔ＝１〜（ｎ−１））の
値を記憶しておき、このROMの出力とシンドロ
ームの演算で形成された係数との両者を比較する
ことにより、２ワードエラーの検出及びエラーロ
ケーシヨンの検出をなしうるので、エラー検出及
びエラー訂正を高速で行なうことができる。これ
と共に、エラー訂正装置における演算回路その他
のハードウエアの構成を簡単化することができ
る。

【図面の簡単な説明】

図は本発明が適用されたエラー訂正装置の一例
のブロツク図である。 １は入力端子、４はエラー訂正回路、５は出力
端子、６は演算回路、１０はROMである。

Claims (1)

1. 【特許請求の範囲】 １ ｍビツトをデータの１ワードとし、ｎワード
   で１ブロツクを構成し、パリテイ検査行列Ｈとし
   て 又は （但し、αは、GF(2)上の既約多項式をＦ_(x)と
   するときに、（Ｆ_(x)＝０）を満足する根であ
   る。） を用い、受信されたｎワードからなる１ブロツク
   Ｖ^Tと上記パリテイ検査行列Ｈとから の演算によつて、ｋ個のシンドロームS₀〜Ｓ_k-1
   を求め、このシンドロームを用いるエラー訂正方
   法において、上記のシンドロームS₀〜Ｓ_k-1から A₁＝S₀S₂＋S₁ ² B₁＝S₁S₂＋S₀S₃ C₁＝S₁S₃＋S₂ ² A₂＝S₁S₃＋S₂ ² B₂＝S₂S₃＋S₁S₄ C₂＝S₂S₄＋S₃ ² 〓 Ａ_k-3＝Ｓ_k-4Ｓ_k-2＋Ｓ_k-3 ^２ Ｂ_k-3＝Ｓ_k-3Ｓ_k-2＋Ｓ_k-4Ｓ_k-1 Ｃ_k-3＝Ｓ_k-3Ｓ_k-1＋Ｓ_k-2 ^２ の演算によつて、係数Ａ，Ｂ，Ｃを求める第１の
   ステツプと、下記の(a)(b)(c)で示すエラー検出及び
   エラー訂正を上記シンドローム及び係数によつて
   行なう第２のステツプとからなることを特徴とす
   るエラー訂正方法。 (a) （S₀＝S₃＝S₄……＝Ｓ_k-1＝０，A₁＝A₂＝…
   …＝Ａ_k-3＝０，B₁＝B₂＝……＝Ｂ_k-3＝０，Ｃ_{k
   −３}＝０）が成立するときは、エラーワードが無
   いと検出する。 (b) （S₀≠０，S₃≠０，S₄≠０，……，Ｓ_k-1≠
   ０）（Ａ(k)＝０，Ｂ(k)＝０，（但し(k)＝１〜ｋ−
   _３），Ｃ_k-3＝０）が成立するときは、１ワード
   エラーと判断し、上記シンドロームの演算によ
   つてエラー訂正を行なう。 (c) （Ａ(k)≠０，Ｂ(k)≠０，Ｃ_k-3≠０）のとき
   に （Ｂ_１／Ａ_１＝Ｂ_２／Ａ_２＝……＝Ｂ_ｋ−３／Ａ_{ｋ−
   ３}＝Ｄ） （Ｃ_１／Ａ_１＝Ｃ_２／Ａ_２＝……＝Ｃ_ｋ−３／Ａ_{ｋ−
   ３}＝Ｅ） とおき、（α²ⁱ＋Ｄαⁱ＋Ｅ＝０）のエラーロケ
   ーシヨン方程式を解いて、エラーロケーシヨン
   （ｉ，ｊ）を検出して２ワードエラーの訂正を
   行なう。