JPH0746776B2 - 誤り訂正回路 - Google Patents

Description

【発明の詳細な説明】 〔技術分野〕 本発明は、短縮リード・ソロモン符号を用いてｔ重誤り
を訂正するようにした誤り訂正回路に関するものであ
る。

〔従来技術〕

従来から、磁気ファイル等におけるファイリング装置の
データ信頼性を向上するために、しばしば単一バイト誤
りを訂正するリード・ソロモン符号や隣接誤り訂正符号
が用いられている。なかでも、磁気媒体よりもエラーレ
ートの悪い媒体（光ディスク等）を用いる場合、あるい
は、データ信頼度をより向上させたい場合には、ランダ
ムな２重バイト誤りを訂正する能力をもつリード・ソロ
モン符号が用いられている。

また、光磁気ディスク等さらにエラーレートの悪い媒体
を用いたり、あるいは、データの信頼度をさらに向上さ
せたい場合には、ランダムな３重バイト誤り以上を訂正
する能力をもつリード・ソロモン符号を用いることが望
ましい。

一般に、ｔ重誤りを訂正するリード・ソロモン符号の復
号法として、バーレカンプ・マッシイの方法およびピー
ターソンの方法が知られている。

しかし、ピーターソンの方法は、次に示すステップを必
要とするので、復号過程が複雑となる。

ステップ1:シンドロームから、Ｍ次の行列式 但し、Ｍ＝t,t−1,…,2,1を各々のＭに対して計算し、
誤りの個数を求める。

ステップ2:ステップ１で求めた誤りの個数に応じた誤り
位置多項式をたて、その係数を求める。

ステップ3:誤り位置多項式のＭ個の根を求める。これら
の根は、誤りの位置を表わす。

ステップ4:求められたＭ個の誤りの位置とシンドローム
とに基づき、各誤り位置に対応する各々の誤りパターン
を求める。

かかる復号過程を避けるために、前記ステップを踏ま
ず、誤り位置および誤りパターンを直接復号するように
した方式として、「GF（2^m）の上の拡大リード・ソロモ
ン符号の一復号方式」（電子通信学会論文誌'83/1Vol.J
66−A,No.1）あるいは、「デジタル信号の誤り検出回
路」（特開昭58−138140号）が知られている。

直接的に復号する方式は前記ステップを踏む必要がない
ので、２重訂正に対しては回路量の少ない復号回路を提
供することができる（第２図に示す特開昭58−144952号
公報の概略ブロック図参照）。

しかし、短縮されたリード・ソロモン符号に対しても、
短縮されていないときと同じクロック数を必要とすると
いう欠点があった。

その理由を、第１図示の短縮符号を用いて説明する。こ
こでは、２重誤り訂正短縮リード・ソロモン符号のｉ番
目のワードW_iに誤りパターンe_iが、またｊ番目のワード
W_jに誤りパターンe_jが生じた場合について説明する。

任意の整数ｍで定義されるガロア体GF（2^m）の原始元α
を用いて構成されるパリティ検査行列を受信符号に乗じ
て得られるシンドロームは、 となり、上記シンドロームS₀，S₁，S₂，S₃は、各々α^０
（＝１），α^１，α^２，α^３をフィードバック係数に持
つシンドローム・レジスタに対してワードW_N，…，W_iを
この順序にて入力することによって生成される。

上述した特開昭58−144952号公報に示される直接復号法
では、この後も更にシンドローム・レジスタをシフトす
る。

ｋ回シフト後のシンドロームS₀，S₁，S₂，S₃は次式で表
わされる。

上記シンドローム間の排他的論理和A₀，A₁，A₂は次式で
表わされる。

ここで、Ｌ＝A₀・A₁＋▲A² ₁▼と定義すれば、 Ｌ＝e_ie_j（１＋α^ｉ＋ｋ）（１＋α^ｉ＋ｋ）（α
^{２（ｉ＋ｋ）}＋α^{２（ｉ＋ｋ）}） …（４） より、ｋ＝Ｍ−ｉまたはｋ＝Ｍ−ｊのときのみＬ＝０と
なる。

従って、１番目のワードに誤りが生じたかをＬの値によ
り調べるためには、ｉ＝１よりｋ＝Ｍ−１回のシフトを
シンドロームに対して施すことが必要となる。これは短
縮していない場合に要するシフト回数と同じであり、１
回のシフトに１クロック必要であるから、短縮していな
い場合と同じクロック数を要することになる。そこで、
このシフト回数を減らすことができれば、それだけ処理
時間を短縮することができる。

〔目的〕

本発明の目的は、上述の点に鑑み、短縮リード・ソロモ
ン符号を直接復号する際に、短縮していない場合よりも
シンドロームに対するシフト演算の回数が少なくて済
み、処理時間の短い高速な誤り訂正回路を提供すること
にある。

かかる目的を達成するために、本発明では、符号長Ｎの
2^m元短縮リード・ソロモン符号（Ｎ＜Ｍ＝2^m−1:mは自
然数）を受信して受信語のｔ重誤りを訂正する誤り訂正
回路において、受信語W_j（ｊ＝1,2,…,N）のそれぞれ
に、α^{ｉ（Ｍ−Ｎ）}・α^ij（αはガロア体GF（2^m）の原
始元）を乗じた和によるシンドロームS_i（ｉ＝0,1,…,2
t−１）を生成する生成手段と、該生成手段により生成
された前記シンドロームS_i（ｉ＝0,1,…,2t−１）の各
々にα^ｉをＮ−１回繰り返し乗じる過程により、シンド
ロームS_i ^(k)＝S_i（α^ｉ）^ｋ（ｋ＝０…,N−１）を順次
求める第１演算手段と、該第１演算手段により順次求め
られた前記シンドロームS_i ^(k)同士の和S_i ^(k)＋S_i+1 ^(k)
（ｉ＝0,1,…,2t−２）をｎ＋１行ｉ−ｎ＋１列（０≦
n,i−ｎ≦ｔ−１）の要素とするｔ次正方行列の行列式
Δ^（ｋ）を順次演算する第２演算手段と、前記第１演算
手段により順次求められた前記シンドロームS_i ^(k)（ｉ
＝0,1,…,2t−１）の値を用いて、受信語W_N-kに誤りが
生じた場合の誤りパターンe_N-kを演算する第３演算手段
と、前記第２演算手段により順次演算された前記行列式
Δ^（ｋ）のそれぞれにつき、値が０か否かを判別する判
別手段と、該判別手段によって前記行列式Δ^（ｋ）の値
が０と判別された場合に、演算された前記誤りパターン
e_N-kにより受信語W_N-kを訂正する訂正手段とを有するこ
とを特徴とする。

また、本発明の好適実施例として、任意の整数ｍで定義
されるガロア体GF（2^m）の原始元αを用いた2t個（ただ
し、ｔは正の整数）の１次多項式の積で得られる生成多
項式から生成される符号長Ｎ（但し、Ｎは2tよりも大き
く、Ｍ＝2^m−１よりも小さい正の整数）の短縮リード・
ソロモン符号を受信して該受信符号に対する2t個のシン
ドロームS₀，S₁，…，S_2t-1を個別に出力するシンドロ
ーム演算手段と、符号の短縮分を考慮したα
^{ｉ（Ｍ−Ｎ）}を各々のシンドロームS_i（ｉ＝0,1,…2t−
１）に乗じ若しくは予め受信信号に乗ずる乗算手段と、
この乗算手段から得られるシンドロームS₀′，S₁′，…
Ｓ_{２′ｔ−１}に対して、 S_i′→S_i′α^ｉ→S_i′α²ⁱ→…→S_i′（α^ｉ）^ｋ＝S_i
^(k) 但し、ｉ＝0,1,…,2t−１ ｋ＝1,2,…,N へと順次交換する手段と、前記シンドロームS_i ^(k)の変
換ごとにシンドローム間の排他的論理和であるS₀ ^(k)S
₁ ^(k)，S₁ ^(k)S₂ ^(k)，…，S_2t-2 ^(k)S_2t-1 ^(k)を演算す
る手段と、前記排他的論理和であるS₀ ^(k)S₁ ^(k)，S₁
^(k)S₂ ^(k)，…，S_2t-2 ^(k)S_2t-1 ^(k)に関する行列式 Δ_１ ^（ｋ）＝｜S₀ ^(k)，S₁ ^(k)｜ を演算する手段と、Δｉ^（ｋ）＝０を検出して誤りの個
数ならびに誤りの位置を同時に求めるｔ重誤り位置検出
回路と、その誤り位置の誤りパターンを求める論理回路
とを備えて誤り訂正回路を構成することも可能である。

以下、図面を参照して本発明を詳細に説明する。

〔実施例〕

第３図は、本発明を適用した短縮符号リアルタイム訂正
回路のブロック図である。

本実施例では、２重誤りを訂正するための回路構成を示
す。

第３図において、１〜３はガロア体GF（2^m）の要素α
^{（Ｍ−Ｎ）}，α^{２（Ｍ−Ｎ）}，α^{３（Ｍ−Ｎ）}を乗算す
る回路、４〜６はα，α^２，α^３を乗算する回路であ
り、ROMまたは排他的論理和回路の組合せによって構成
する。

７〜17は、それぞれｍビットの排他的論理和回路であ
る。

18〜21はそれぞれｍビットのレジスタ（シンドローム・
レジスタ）である。

また、排他的論理和回路７およびレジスタ18はシンドロ
ームS₀の生成回路を構成する。更に、α^{（Ｍ−Ｎ）}乗算
回路１と排他的論理和回路８とα乗算回路４とレジスタ
19とにより、シンドロームS₁の生成回路を構成する。

α^{２（Ｍ−Ｎ）}乗算回路２と排他的論理和回路９とα^２
乗算回路５とレジスタ20とにより、シンドロームS₂の生
成回路を構成する。

α^{３（Ｍ−Ｎ）}乗算回路３と排他的論理和回路10とα^３
乗算回路６とレジスタ21とにより、シンドロームS₃の生
成回路を構成する。

W₁，W₂，…，W_N（W_i（ｉ＝1,2,…,N）はｍビットから構
成される）は、受信された符号長Ｎ（ただし、Ｎは短縮
された符号長でＮ＜Ｍ＝2^m−１）の符号語を表すものと
する。

本実施例を作動させるには、まずスイッチ28を閉じて受
信語W₁，W₂，…，W_Nを信号線ａに順次入力し、信号線ｂ
にはシフトクロックを加える。このとき、
α^{（Ｍ−Ｎ）}，α^{２（Ｍ−Ｎ）}，α^{３（Ｍ−Ｎ）}乗算回
路によって、受信語には予めα^{（Ｍ−Ｎ）}，α
^{２（Ｍ−Ｎ）}，α^{３（Ｍ−Ｎ）}が乗算されてある。

従って、それぞれのシンドロームは、次式のようにな
る。

ここで、従来例と同様に、ｉ番目のワードW_iに誤りパタ
ーンe_i,j番目のワードW_jに誤りパターンe_jが生じた場合
を例にとり説明する。

より、それぞれのシンドロームは、次式のようになる。

次に、スイッチ28を開いて信号線ｂにシフトクロックを
加え続けると、ｋ回シフト後のシンドロームS₀〜S₃は次
式で表される。

排他的論理和回路11〜13によって、上記シンドローム間
の排他的論理和A₀，A₁，A₂をとると、次式で表される。

ここで、Ｌ＝A₀・A₂＋▲A² ₁▼と定義すれば、 Ｌ＝e_i・e_j（１＋α^Ｍ−Ｎ・α^ｉ＋ｋ）・（１＋α
^Ｍ−Ｎ・α^ｊ＋ｋ）（α^{２（ｉ＋ｋ）}＋
α^{２（ｊ＋ｋ）}）・α^{２（Ｍ−Ｎ）} …（10） より、ｋ＝Ｎ−ｉ、またはｋ＝Ｎ−ｊのときのみＬ＝０
となる。

ここで、符号長はＮであるので、１≦ｉ≦N,1≦ｊ≦Ｎ 従って、ｋ＜Ｎとなり、シフトクロックは短縮された符
号長に抑えられる。

また、パターンについても、次式で求められる。

ｅ＝S₀＋▲A² ₀▼（A₀＋A₁）^-1 …（11） なぜならば、ｋ＝Ｎ−ｉのとき、A₀，A₁，S₀は であるので、 再び第３図に戻り、各構成要素について説明する。

22,23はガロア体GF（2^m）上での自乗回路であり、α^ｉ
が入力されるとα²ⁱが出力される。

24はガロア体GF（2^m）上の任意の元α^ｉとα^ｊの乗算結
果α^ｉ＋ｊを出力する回路であり、ｍ≦６のときにはRO
Mで構成することができる。

25はガロア体GF（2^m）上の任意の元α^ｉとα^ｊの割算結
果α^ｉ−ｊを出力する回路であり、ｍ≦６ならばROMに
より構成することができる。

26はゲート回路であり、排他的論理和回路15かからの信
号をゲート信号とし、このゲート信号が“0"のときにゲ
ートを開いて排他的論理和回路16からの出力信号を出力
し、ゲート信号が“0"でなければゲートを閉じて“0"を
出力する。

27はＮワードのデータを貯えるバッファメモリである。

上述の排他的論理和回路11,13から出力されたシンドロ
ーム間の排他的論理和A₀，A₂は乗算回路24に入力され、
A₀・A₂が出力される。

このとき、排他的論理和回路12から出力されたシンドロ
ーム間の排他的論理和A₁は自乗回路23に入力され、▲A²
₁▼が出力される。その結果を排他的論理和回路15に入
力することにより、Ｌ＝A₀・A₂＋▲A² ₁▼が計算され
る。

これと同時に、排他的論理和回路14によってA₀＋A₁が計
算され、自乗回路22により▲A² ₀▼が計算される。この
結果を割算回路25に入力することにより、▲A² ₀▼／（A
₀＋A₁）が出力される。

最後に、排他的論理和回路16から ｅ＝S₀＋▲A² ₀▼／（A₀＋A₁）が出力される。

スイッチ28が閉じられて受信語W_N，…，W₁が信号線ａか
ら入力されている時、メモリバッファ27は受信後W_N，
…，W₁を貯える。そして、スイッチ28が開かれると、シ
フトクロックｂに同期して受信語が出力される。

従って、スイッチ28が閉じられて（Ｎ−ｉ）回目のシフ
トがなされると、排他的論理和回路15からの出力はＬ＝
０となり、また、排他的論理和回路16からの出力はｅ＝
e_iとなる。よって、Ｌ＝０であるのでゲート回路26は開
き、排他的論理和回路16から出力ｅ＝e_iが出力される。
このとき、バッファからはW_iが出力されているので、排
他的論理和回路17において W_i＋e_i＝W_i が計算され、誤りが訂正されて出力される。W_jについて
も同様である。

以上は２重誤りについて説明したが、ｔ重誤りについて
も同様に拡張していくことが可能である。

第３図に示した実施例では、シンドローム生成部と、そ
れぞれのシンドロームを S_i′→S_i′α^ｉ→S_i′α²ⁱ→…→S_i′（α^ｉ）^ｋ （ｉ＝0,1,2,3） に変換する部分とをスイッチ28の開閉によって共有させ
ていたが、第４図に示すように、シンドローム生成部と
シンドローム変換部とを分けることもできる。かかる構
成によれば、シンドローム生成後にスイッチ28を開いて
受信語を空送りする必要がなくなるので、符号ブロック
が連続して送られる場合にも、リアルタイム処理が可能
となる。

また、α^Ｍ−Ｎ，α^{２（Ｍ−Ｎ）}，α^{３（Ｍ−Ｎ）}乗算
回路をROMで構成する場合には第５図に示すように、信
号線ｃに対してワード位置情報を送り、ROM33に対する
ｉ番目のワードW_iの入力によってW_iα^Ｍ−Ｎ・α^ｉを出
力させ、他方、ROM34に対してはW_iα^{２（Ｍ−Ｎ）}・α
²ⁱを、ROM35に対してはW_iα^{３（Ｍ−Ｎ）}・α³ⁱを出力
させることにより、（５）式を計算することができる。
かかる構成により、回路をより簡単化することができ
る。

なお、ｍ≦６ならば、ROM36,37,38（第５図参照）を用
いてＬおよびｅの演算回路を簡単化することができる。
ここで、ROM36はA₀，A₂の入力に対して、A₀・A₂を出力
する。ROM37はA₁，A₀，A₂の入力に対して、A₀・A₂＋A₁
を出力する。ROM38はA₀，A₁の入力に対して、▲A² ₀▼・
（A₀＋A₁）^-1を出力する。

更に、第６図に示すように、シンドローム生成回路およ
びシンドローム変換回路の中間に、α^{（Ｍ−Ｎ）}，α
^{２（Ｍ−Ｎ）}，α^{３（Ｍ−Ｎ）}乗算回路を挿入すること
も可能である。かかる構成は、（５）式を
α^{（Ｍ−Ｎ）}，α^{２（Ｍ−Ｎ）}，α^{３（Ｍ−Ｎ）}でくく
った次式と等価である。

〔効果〕 以上説明したように、本発明によれば、短縮リード・ソ
ロモン符号を直接復号する際に、シンドロームに対して
施す順次演算の回数を符号の短縮分だけ減らすことがで
きるので、復号に要する時間の短い高速な誤り訂正を行
なうことができる。

本発明を実施することにより、ハードウエアの縮小化を
図り得るばかりでなく、宇宙通信をも含む全ての通信技
術、ディジタル画像処理技術など広汎なディジタル技術
分野に応用することができる。

【図面の簡単な説明】 第１図は短縮符号の説明図、 第２図は特開昭58−144952号公報に開示されている誤り
訂正回路のブロック図、 第３図は本発明を適用した短縮符号リアルタイム訂正回
路の一実施例を示すブロック図、 第４図はシンドローム生成部とシンドローム変換部とを
分離して構成した短縮符号リアルタイム訂正回路の別実
施例を示すブロック図、 第５図はROMを用いて簡単化した短縮符号リアルタイム
訂正回路の別実施例を示すブロック図、 第６図はα^Ｍ−Ｎ，α^{２（Ｍ−Ｎ）}，α^{３（Ｍ−Ｎ）}乗
算回路をシンドローム生成部とシンドローム変換部との
中間に挿入して構成した短縮符号リアルタイム訂正回路
の別実施例を示すブロック図である。 １…α^Ｍ−Ｎ乗算回路、２…α^{２（Ｍ−Ｎ）}乗算回路、
３…α^{３（Ｍ−Ｎ）}乗算回路、４…α乗算回路、５…α
^２乗算回路、６…α^３乗算回路、７〜17…排他的論理和
回路、18〜21…ｍビットのレジスタ（シンドローム・レ
ジスタ）、22,23…自乗回路、24…乗算回路、25…割算
回路、26…ゲート回路、27…バッファメモリ、28〜32…
スイッチ、33〜38…ROM、39…誤りパターン解読回路、4
0…誤り位置検出回路。

Claims (1)

【特許請求の範囲】
1. 【請求項１】符号長Ｎの2^m元短縮リード・ソロモン符号
   （Ｎ＜Ｍ＝2^m−1:mは自然数）を受信して受信語のｔ重
   誤りを訂正する誤り訂正回路において、 受信語W_j（ｊ＝1,2,…,N）のそれぞれに、 α^{ｉ（Ｍ−Ｎ）}・α^ij（αはガロア体GF（2^m）の原始
   元）を乗じた和によるシンドロームS_i（ｉ＝0,1,…,2t
   −１）を生成する生成手段と、 該生成手段により生成された前記シンドロームS_i（ｉ＝
   0,1,…,2t−１）の各々にα^ｉをＮ−１回繰り返し乗じ
   る過程により、シンドロームS_i ^(k)＝S_i（α^ｉ）^ｋ（ｋ
   ＝０…,N−１）を順次求める第１演算手段と、 該第１演算手段により順次求められた前記シンドローム
   S_i ^(k)同士の和S_i ^(k)＋S_i+1 ^(k)（ｉ＝0,1,…,2t−２）を
   ｎ＋１行ｉ−ｎ＋１列（０≦n,i−ｎ≦ｔ−１）の要素
   とするｔ次正方行列の行列式Δ^（ｋ）を順次演算する第
   ２演算手段と、 前記第１演算手段により順次求められた前記シンドロー
   ムS_i ^(k)（ｉ＝0,1,…,2t−１）の値を用いて、受信語W
   _N-kに誤りが生じた場合の誤りパターンe_N-kを演算する
   第３演算手段と、 前記第２演算手段により順次演算された前記行列式Δ
   ^（ｋ）のそれぞれにつき、値が０か否かを判別する判別
   手段と、 該判別手段によって前記行列式Δ^（ｋ）の値が０と判別
   された場合に、演算された前記誤りパターンe_N-kにより
   受信語W_N-kを訂正する訂正手段とを有することを特徴と
   する誤り訂正回路。