JPH0746777B2 - 符号誤り訂正回路 - Google Patents

Description

【発明の詳細な説明】 〔技術分野〕 本発明はｔ重ワード誤りを訂正する符号誤り訂正回路に
関し、特に、簡略な回路構成にてランダムなｔ重ワード
誤りを高速訂正するようにした符号誤り訂正回路に関す
るものである。

〔従来技術〕

従来から、磁気ファイル等のファイル装置におけるデー
タ信頼性を向上させるために、単一バイト誤りを訂正す
るリード・ソロモン符号や隣接誤り訂正符号等がしばし
ば用いられている。

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

そして冗長度に制限がある場合には、情報点数を増やす
ために拡大リード・ソロモン符号 あるいは が用いられる。

しかし、上記符号の欠点のひとつは、情報点数を増して
いることに起因して、誤り位置多項式を用いて訂正動作
が統一的に行われないという点にあった。

いま、GF（2⁴）上の検査行列として、第（1A）式あるい
は第（1B）式を検査行列にもつ符号を例にとって説明す
る（ｍ＝４）。

従来例では、上式に対応するシンドロームS₀〜S₃を生成
したとき、シンドロームS₀〜S₃を判定することによっ
て、訂正動作を以下のように変更する必要があった。

（Ｉ）S₀＝S₁＝S₂＝S₃＝０→誤りなし （II）S₀≠0,S_i＝S₂＝S₃＝０→ｉ＝15の単一誤りe₁₅＝S
₀ （III）S₀＝0,S₁≠0,S₂≠0,S₃≠０→S₁・S₃＝▲S² ₂▼で
あればｉ＝15を含んだ２重誤り α^ｊ＝S₂／S₁，e_j＝▲S² ₁▼／S₂ e₁₅＝S₀＋e_j （IV）S₀≠0,S₁≠0,S₂≠0,S₃≠０→ S₀・S₂＝S₁・S₂であればｉ≠15の単一誤り α^ｉ＝S₁／S₀，e_j＝S₀ S₁・S₃＝▲S² ₂▼であればｉ＝15を含んだ２重誤り α^ｉ＝S₂／S₁，e_j＝▲S² ₁▼／S₂，e₁₅＝S₀＋e_j 他の場合 σ（Ｘ）＝（▲S² ₂▼＋S₁・S₃）X²＋（S₁・S₂＋S₀・
S₃）Ｘ＋▲S² ₁▼＋S₀・S₂の解が見つかれば より２重誤り 上記以外は訂正不能 第１図に、上記訂正原理による誤り訂正回路のブロック
図を示す。図示したシンドローム生成部22より生成され
たシンドロームをシンドローム判定部23において判定
し、以下、次に示す処理を行う。

（Ｉ）と判定された場合：ブロック０が選択される。

（II）と判定された場合：ブロック１によってS₀が取り
込まれ、ｉ＝15ワード目においてe₁₅＝S₀が出力され
る。

（III）と判定された場合：ブロック２によってS₀〜S₃
が取り込まれ、ｊワード目にe_jが、15ワード目にe₁₅が
出力される。

（IV）と判定された場合：ブロック３によってS₀〜S₃が
取り込まれ、既述の〜に示す動作を行う。

従って、従来例では（Ｉ）〜（IV）の場合に応じて訂正
動作が異るので、ブロック０〜３に示す回路が別個に必
要とされ、訂正動作を統一的に実行し得ず、これがため
に回路構成が増大するという欠点があった。

〔目的〕

本発明の目的は、上述の点に鑑み、必要な回路構成をま
とめて統一的なｔ重ワード誤り訂正処理を行うようにし
た符号誤り訂正回路を提供することにある。

かかる目的を達成するために、本発明では、符号長Ｎの
Ｎ元拡大リード・ソロモン符号を受信して、ｔ重誤りを
訂正可能な符号誤り訂正回路において、受信語W_j（ｊ＝
0,1,…,N−１）を順次高位より入力して、2t個の記憶部
にそれぞれ記憶内容のα^ｉ倍（ｉ＝0,1,…,2t−１。α
はガロア体GF（2^m）の原始元）と加算して再記憶するこ
とにより、2t個のシンドロームを生成する生成手段と、
受信語W_j（ｊ＝Ｎ−１）については、ｉ＝０に対する記
憶部にだけ入力し、他の記憶部には非入力とする制御す
る制御手段と、前記生成手段により生成された前記シン
ドロームS_i（ｉ＝0,1,…,2t−１）の各々にα^ｉをＮ回
繰り返し乗じる過程により、シンドロームS_i ^(k)＝S
_i（α^ｉ）^ｋ（ｋ＝0,1…,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-1に誤りが生じた場合の
誤りパターンe_N-k-1を演算する第３演算手段と、前記第
２演算手段により順次演算された前記行列式Δ^（ｋ）の
それぞれにつき、値が０か否かを判別する判別手段と、
該判別手段によって前記行列式Δ^（ｋ）の値が０と判別
された場合に、演算された前記誤り訂りパターンe_N-k-1
により受信語W_N-k-1を訂正する訂正手段とを有すること
により、受信語W_N-1以外の受信語を訂正して出力するこ
とを特徴とする。

例えば、任意の整数ｍで定義されるガロア体GF（2^m）の
原始元αを用いて構成される２重ワード誤り訂正符号の
パリティ検査行列 に従ってデータを符号化復号化する２重ワード誤り訂正
回路においては、前記符号化データを受信して受信デー
タ・ワードから前記検査行列に対応するシンドロームS_i
（ｉ＝０…３）を生成するシンドローム生成回路と、前
記シンドローム間の排他的論理和であるS₀S₁，S_iS₂
およびS₂S₃を算出する回路と、前記排他的論理和であ
るS₀S₁，S₁S₂およびS₂S₃に関する行列式 を計算し、△＝０を検出して誤りワードの位置および誤
りパターンを求める論理回路とを備えるよう構成するの
が好適である。

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

〔実施例〕

第２図は本発明の一実施例を示すブロック図である。本
実施例では、ガロア体GF（2⁴）を例にとって説明してい
く。

第２図において、１〜３はそれぞれガロア体GF（2^m）の
要素のα，α^２，α^３を乗算する回路であり、GF（2⁴）
とした場合には、第３図（Ａ）に示すα乗算原理、第３
図（Ｂ）に示すα^２乗算原理、第３図（Ｃ）に示すα^３
乗算原理によって達成することができる。

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

８〜15は、それぞれ、４ビットの排他的論理和回路であ
る。

ここで、排他的論理和回路８およびシンドロームレジス
タ４はシンドロームS₀の生成回路を構成する。また、排
他的論理和回路９とレジスタ５とα乗算回路１とによ
り、シンドロームS₁の生成回路を構成する。同様に、排
他的論理和回路10とレジスタ６とα^２乗算回路２とによ
りシンドロームS₂の生成回路を構成し、排他的論理和回
路11とレジスタ７とα^３乗算回路３とによりシンドロー
ムS₃の生成回路を構成する。

Ｗを符号語（各受信語は４ビットで構成される）とし、 Ｗ＝〔W₀，W₁，W₂…，W₁₅〕 Ｅを誤りとすると、 Ｅ＝〔0,0,…，e_i…e_j,0,0〕 受信語 は、排他的論理和演算を行うことによって、 ＝Ｗ＋Ｅ とすることができる。

従って、第（１）式に対応するシンドロームS₀〜S₃を生
成したときには、 Ｓ＝Ｈ・^Ｔ＝Ｈ・E^T によって、シンドロームS₀〜S₃はそれぞれ、 が生成されなければならない。

本実施例を作動させるためには、まずスイッチ16を閉じ
て受信語を信号線ａに入力し、信号線ｂにシフト・クロ
ックを加える。ただし、15ワード目は、信号線ｃからの
制御信号によりスイッチ17が開かれるので、シンドロー
ムS₁，S₂，S₃生成回路には入力されず、受信語入力終了
時には第（２）式に示すシンドロームS₀〜S₃が生成され
ている。

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

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

ここで、Ｌ＝A₀・A₂＋▲A² ₁▼と定義すれば、 Ｌ＝e_i・e_j（１＋α^ｉ＋ｋ）（１＋α^ｊ＋ｋ）（α
^{２（ｉ＋ｋ）}＋α^{２（ｊ＋ｋ）}） ただし、ｊ＝15のときにはα^ｊ＝０となるので、 Ｌ＝e_i・e₁₅（１＋e_i+k）e_2(i+k) より、ｋ＝−ｉまたはｋ＝−ｊ（ｊ≠15）のときのみＬ
＝０となる。

ｋ＝−15のときにはＬ≠０であるが、15ワード目はパリ
ティ・ワードであるので実用上特に訂正の必要はない。

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

ｅ＝S₀＋▲A² ₀▼／（A₀＋A₁） なぜならば ｅ＝S₀＋▲A² ₀▼／（A₀＋A₁） ｋ＝−ｉのとき（１＋α^ｉ＋ｋ）＝０となるので、 ｅ＝（e_i＋e_j）＋e_j＝e_i 一重誤りの場合はe_j＝０と考えると、 18は上述のA₀，A₁，A₂からＬを演算する回路であり、RO
Mにより構成することができる。

19はS₀，A₀，A₁からｅを演算する回路であり、ROMによ
り構成することができる。

20はＬが０のときにｅを出力するゲートであり、NAND回
路により構成することができる。

21は受信語を貯えておくバッファメモリである。

バッファメモリ21に受信語を入力し終った時にはシンド
ロームS₀〜S₃がレジスタ４〜７に生成され、その後スイ
ッチ16を開き、信号線ｂに同期してシフトレジスタS₀〜
S₃を巡回させ、バッファメモリ21からデータを出力する
と、ｉクロック目の時に上記原理よりＬ＝０となり、誤
りパターンe_iがゲートから出力される。また、バッファ
メモリからは_ｉが出力されているので、両出力の排他
的論理和演算を排他的論理和回路15で行うことにより、
誤りが訂正される。ｊについても同様である。

なお、第２図に示した実施例では、スイッチ16の開閉に
よって、シンドローム生成部と、それぞれのシンドロー
ムを S_i→S_iα^ｉ→S_iα²ⁱ→…→S_i（α_ｉ）^k （ｉ＝0,1,2,3） に変換する部分とを共有させているが、その代わりに、
第４図に示すようにシンドローム生成部とシンドローム
変換部とを分離することもできる。

このように、第４図に示すような構成をとることによ
り、シンドローム生成後、スイッチ16を開いて受信語を
空送りする必要がなくなるので、符号ブロックが連続し
て送られる場合にも、リアルタイム処理が可能となる。

〔効果〕

以上説明したように、本発明によれば、従来から統一的
処理がなされていなかった符号を統一的に処理すること
ができるようになるので、誤り訂正回路のハードウェア
を減少させることができるという格別の効果が得られ
る。

殊に、本発明は、宇宙通信をも含む通信系，ディジタル
画像処理装置など広範囲なディジタル技術分野に適用す
ることが可能である。

【図面の簡単な説明】 第１図は従来技術を説明する図、 第２図は本発明の一実施例であって統一的処理を行うよ
うにした誤り訂正回路のブロック図、 第３図（Ａ）〜（Ｃ）は乗算原理を説明する概念図、 第４図は本発明の別実施例であって統一的処理をリアル
タイムにて行うようにした誤り訂正回路のブロック図で
ある。 １…α乗算回路、２…α^２乗算回路、３…α^３乗算回
路、４〜７…ｍビットのレジスタ（シンドローム・レジ
スタ）、８〜15…排他的論理和回路、16,17…スイッ
チ、16,19…ROM、20…ゲート回路、21…バッファメモ
リ、22…シンドローム生成部、23…シンドローム判定
部。

Claims (2)

【特許請求の範囲】
1. 【請求項１】符号長ＮのＮ元拡大リード・ソロモン符号
   を受信して、ｔ重誤りを訂正可能な符号誤り訂正回路に
   おいて、 受信語W_j（ｊ＝0,1,…,N−１）を順次高位より入力し
   て、2t個の記憶部にそれぞれ記憶内容のα^ｉ倍（ｉ＝0,
   1,…,2t−１。αはガロア体GF（2^m）の原始元）と加算
   して再記憶することにより、2t個のシンドロームを生成
   する生成手段と、 受信語W_j（ｊ＝Ｎ−１）については、ｉ＝０に対する記
   憶部にだけ入力し、他の記憶部には非入力とする制御す
   る制御手段と、 前記生成手段により生成された前記シンドロームS_i（ｉ
   ＝0,1,…,2t−１）の各々にα^ｉをＮ回繰り返し乗じる
   過程により、シンドロームS_i ^(k)＝S_i（α^ｉ）^ｋ（ｋ＝
   0,1…,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-1に誤りが生じた場合の誤りパターンe_N-k-1を演算
   する第３演算手段と、 前記第２演算手段により順次演算された前記行列式Δ
   ^（ｋ）のそれぞれにつき、値が０か否かを判別する判別
   手段と、 該判別手段によって前記行列式Δ^（ｋ）の値が０と判別
   された場合に、演算された前記誤りパターンe_N-k-1によ
   り受信語W_N-k-1を訂正する訂正手段とを有することによ
   り、受信語W_N-1以外の受信語を訂正して出力することを
   特徴とする符号誤り訂正回路。
2. 【請求項２】前記生成手段と、前記第１演算手段とを独
   立な回路構成として、当該第１演算手段において先行符
   号ブロックに関するシンドロームの演算中に、前記生成
   手段により、後続符号ブロックのシンドロームの生成を
   可能としたことを特徴とする特許請求の範囲第１項記載
   の符号誤り訂正回路。