JPH0834441B2 - 誤り位置算出方法 - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、磁気ディスク等の誤り訂正装置に係り、特
に、リード・ソロモン符号を用いた誤り訂正処理に適し
た誤り位置算出回路に関する。

［従来の技術］ リード・ソロモン符号は、誤り訂正符号の一種として周
知である。リード・ソロモン符号の符号語は、ガロア体
GF（2^m）の元により構成されるBCH（Bose−Chaudhuri−
Hocqenghem）符号である。ガロア体とは、簡単にいえ
ば、四則演算が行なえるような数の集合のうち、元の数
（位数）が有限であるものである。ガロア体は、一般に
元の数をｑ＝2^mとすると、GF（ｑ）またはGF（2^m）で表
わされる。ガロア体GF（ｑ）の非零のすべての元は、あ
る種の既約多項式を選ぶと、その根αのべき数α^０，α
^１，α²，…，α^ｑ−２で表わすことができる。このよ
うな多項式は原始多項式と呼ばれ、その根はGF（ｑ）の
原始元と呼ばれる。

なお、リード・ソロモン符号、ガロア体等の詳細につ
いては、日本工業技術センター編「誤り訂正符号化技術
の要点」1986年３月20日発行、第32〜36頁、および、宮
川洋、原島博、今井秀樹共著「情報と符号の理論」岩波
書店、1985年８月２日発行第118〜123頁、170、171頁を
参照されたい。

従来、リード・ソロモン符号を用いた誤り訂正におけ
る誤り位置の算出については、上記「誤り訂正符号化技
術の要点」第160〜163頁に記載されているように、例え
ば、ガロア体GF（2⁸）上の演算では、GF（2⁸）のあらゆ
る元の指数部分が得られるテーブルが訂正装置に備わっ
ており、このテーブルを参照することにより、行なって
いた。

［発明が解決しようとする問題点］ 上記従来技術によれば、例えば、GF（2⁸）上でリード
ソロモン符号を生成する場合、誤り位置算出のために少
なくとも2⁸＝256バイトのメモリが必要になる。このメ
モリ容量は、元の数の増加に伴ない指数関数的に増大す
る。

本発明の目的は、このような誤り位置算出用テーブル
によるメモリの占有を解消することにある。

［問題点を解決するための手段］ 上記目的を達成するために、本発明は、 原始元をαとするガロア体GF（2^m）（m:正整数）上の
リードソロモン符号を用いた誤り訂正処理における誤り
位置算出回路において、 シフト動作により元に順次αが乗算されるｍビットの
乗算回路と、 ｍビットのデータを設定可能なレジスタと、該レジス
タの出力と上記乗算回路の出力と比較し、両出力の一致
を検出する一致検出回路と、 該一致検出回路により一致が検出されるまで上記乗算
回路のシフト回数を計数するカウンタとを有するもので
ある。

上記乗算回路は、例えば、上記ガロア体GF（2^m）上の
原始多項式の係数が１の項の位置に帰還を掛けたｍ個の
遅延素子を含むフィードバックレジスタにより構成する
ことができる。

また、上記一致検出回路は、例えば、上記レジスタの
第ｋビット（k:1,2.…,m）の出力と上記乗算回路の第ｋ
ビットの出力とを受けるｍ個の排他的論理和ゲートと、
該ｍ個の排他的論理和ゲートの全出力を受ける論理和ゲ
ートとにより構成することができる。

［作用］ ２種類のシンドローム（受信語を生成多項式で割った
剰余）をS₀，S₁とし、そのいずれもがGF（2^m）の元で表
わされるならば、S₀にα^k1（１≦k₁≦2^m−２）を掛ける
と、S₁のパターンに一致する。このことを利用し、両者
が一致するまで乗算回路（シフトレジスタ）のシフト動
作により上記掛け算を行なえば、そのシフト回数k₁から
誤り位置が得られる。

同様に、２種類のシンドロームをS₀，S^-1とし、その
いずれもがGF（2^m）の元で表わされるならばS^-1にα^k2
（１≦k₂≦2^m−２）を掛けると、S₀のパターンに一致す
る。このことを利用し、両者が一致するまで乗算回路
（シフトレジスタ）のシフトにより上記掛け算を行え
ば、そのシフト回数k₂から誤り位置が得られる。

両処理によるシフト回数k₁とk₂とが一致すれば、誤り
が単一シンボル誤りであると判断できる。

シンドロームS₀，S₁，S_-1のパターンとしては、α^１
〜α^2m-1のいずれかをとるため、演算テーブルを用いる
場合、メモリとして2^mバイトが必要となる。ｍ＝８の場
合、2⁸＝256バイトで済むが、ｍ＝16の場合には2¹⁶＝65
Kバイトものメモリが必要となり、実用上問題となる。

これに対し、本発明によれば、後述するように、 誤り位置ｌ≦データ長≦2^m−１ であるので、データ長＝2^m−１であるとすれば ｍ＝16で、ｌ＋１≦65536 であり、誤り算出に要するシフト回数は大きくなるが、
従来の誤り位置算出用テーブルを不要とすることができ
る。また、あくまでも誤り位置、すなわちシフト回数は
データ長以下に限定されるので、データ長を短くすれば
シフト回数も少なくなる。

誤り位置の算出に要する時間としては、テーブルを参
照しソフトウェアで行なった方がシフトレジスタにより
行なうより速いと考えられるが、磁気ディスク装置のよ
うに、リアルタイムで訂正を行なう必要のない場合に
は、本発明は有用である。

［実施例］ 以下、図面を参照して本発明の一実施例を詳細に説明
する。

なお、ここで挙げるガロア体GF（2⁸）の原始多項式
は、 Ｐ（ｘ）＝x⁸＋x⁴＋x³＋x²＋１ であり、原始元をαとする。

データの第ｌシンボルにパターンがα^ｍである単一誤
りが生じたとすると、従来の誤り訂正方式によれば、そ
れぞれｘ＋1,x＋α,x＋α^−１を除数とするとシンドロ
ームをS₀，S₁，S_-1として、以下の関係が得られる。

S₀＝α^ｍ …（１） S₁＝α^m+l+1 …（２） S_-1＝α^m-(l+1) …（３） ここで、一般的手法として、 S₁／S₀＝S₀／S_-1＝α^l+1 …（４） が成り立つことにより、単一誤りであることが判定さ
れ、商α^l+1により、誤り位置がわかる。

第１図に、（４）式にしたがって、２種類のシンドロ
ームから誤り位置ｌを算出する回路を示す。この回路
は、ガロア体GF（2⁸）上の原始多項式の係数が１の項の
位置に帰還を掛けたフィードバックレジスタ（８個の遅
延素子と８個の排他的論理和（EOR）ゲートとからな
る）で構成された、ガロア体GF（2⁸）の元にαを掛ける
乗算回路１と、８ビットのデータを設定可能なレジスタ
２と、それぞれ乗算回路１とレジスタ２の対応する位の
出力を受ける８個のEORゲート５と、これらのゲートの
全出力を受ける論理和（OR）ゲート３と、乗算回路１の
シフト動作を行なうクロック信号を計数するクロックカ
ウンタ４とからなる。

つぎに、第１図の回路により誤り位置算出を行う動作
手順を、第２ないし第４図を参照して説明する。

最初に、第２図のフローチャートに示すように、シン
ドロームS₀，S₁により、誤り位置l₁を求めることを考え
る。

まず、カウンタ４の計数値を初期化（ここでは０にリ
セット）する（ステップ21）。つぎに、８ビットのシン
ドロームS₀は、 S₀＝b₇α^７＋b₆α^６＋b₅α^５＋b₄α^４＋b₃α^３＋b₂α^２
＋b₁α^１＋b₀ …（５） と表わされるので、b₀〜b₇のそれぞれの入力端を通し、
乗算回路１の初期値として、S₀を設定するとともに、レ
ジスタ２には図示しないロード入力端を介してシンドロ
ームS₁を設定する（ステップ22）。その後、乗算回路１
の入力b₀〜b₇を０として、クロック信号により乗算回路
をシフトする（ステップ23）。このとき、同時にカウン
タ４の値も歩進される。そこで、ORゲート３の出力が
“低”になったかどうか、即ち、乗算回路１のパターン
がレジスタ２のパターンに一致したかどうかが判定され
る（ステップ24）。両パターンが一致しなければ、ステ
ップ23に戻り、一致すればステップ25に進み、その時点
のカウンタ４の値（シフト回数）k₁から、誤り位置l₁が
得られる。

この処理を式表現すれば、 S₀＝α^ｍ、 であるから、次式のようになる。

この式により分かるように、乗算回路１のパターンがレ
ジスタ２のパターンに一致するまでのシフト回数k₁はl₁
＋１である。よって、パターン一致までのシフト回数k₁
を計数し、その値から１を引けば誤り位置l₁が求められ
る。

つぎに、第３図のフローチャートを参照して、シンド
ロームS₀，S_-1により誤り位置を求める手順を示す。こ
の手順は先の手順と同様、カウンタ４を初期化（ステッ
プ31）した後、乗算回路１に初期値としてS_-1を、レジ
スタ２にS₀をそれぞれ設定し（ステップ32）、ORゲート
３の出力が“低”になるまで、乗算回路１のシフトを繰
返せば（ステップ33、34）、誤り位置l₂が求められる
（ステップ35）。この処理は次式のように表わされる。

そこで、第３図のフローチャートに示すように、シン
ドロームS₀，S₁から求めた誤り位置l₁と、シンドローム
S₀，S_-1から求めた誤り位置l₂とを比較し（ステップ4
1）、両者が一致したとき、その誤りを単一シンボル誤
りと判定し、誤り位置l₁（またはl₂）がそのまま求める
誤り位置ｌとなる。比較が一致しなかった場合、その誤
りは単一誤りではなかった判定される（ステップ43）。

なお、上記実施例では、カウンタを０に初期化した
が、予め−１に初期化しておけば、最終的なカウンタの
値ｋがそのまま誤り位置ｌになるので、ステップ25（第
２図）、ステップ35（第３図）は不要になる。

本実施例によれば、GF（2⁸）のあらゆる元に対応した
演算表を用いずに上述のように簡単な回路で誤り位置を
求めることができる。また、 誤り位置ｌ≦データ長（シンボル）≦2⁸−１＝255 …
（８） であるから、 ｌ＋１≦256 …（９） となり、最大でも256回のシフトで誤り位置が算出され
る。

さらに、本実施例には以下の特長がある。

上述した文献に記載されたF6420の誤り訂正方式で
は、生成多項式として、 Ｇ（ｘ）＝（ｘ＋α^−１）（ｘ＋１）（ｘ＋α） …（1
0） を用いており、（ｘ＋α）によるデータの除算を行なっ
ている（符号化とシンドローム計算）。ここで、（ｘ＋
α）による除算回路は、第１図の乗算回路と全く同一で
あるため、誤り位置算出にこの除算回路を利用すること
ができ、誤り訂正処理手順によっては、新たに位置算出
用回路を設ける必要がない。

［発明の効果］ 以上説明したように、本発明によれば、ガロア体GF
（2^m）のあらゆる元に対応した演算テーブルを用いず
に、簡単な回路で誤り位置を求めることができ、その結
果、演算テーブル用のメモリを節約することができる。

【図面の簡単な説明】

第１図は本発明の一実施例の回路図、第２図ないし第４
図は第１図の回路の動作の説明に供するフローチャート
である。 １……乗算回路、２……レジスタ ３……ORゲート、４……クロックカウンタ ５……EORゲート

───────────────────────────────────────────────────── フロントページの続き (72)発明者 川村 哲士 神奈川県横浜市戸塚区吉田町292番地 株 式会社日立製作所マイクロエレクトロニク ス機器開発研究所内 (56)参考文献 特開 昭62−60319（ＪＰ，Ａ) 特開 昭63−131623（ＪＰ，Ａ) 特開 昭58−219850（ＪＰ，Ａ) 特開 昭61−60018（ＪＰ，Ａ) 特開 昭57−60753（ＪＰ，Ａ) 特開 昭58−219650（ＪＰ，Ａ)

Claims (1)

【特許請求の範囲】
1. 【請求項１】原子元をαとするガロア体GF（2^m）（m:正
   整数）上のリード・ソロモン符号を用いた誤り訂正処理
   における誤り位置を、前記ガロア体GF（2^m）の元で表わ
   される３種類のシンドロームS₀、S₁、S_-1を用いて算出
   する誤り位置算出方法において、 前記ガロア体GF（2^m）上の原始多項式の計数が１の項の
   位置に帰還を掛けたｍ個の遅延素子を含むフイードバッ
   クレジスタからなるｍビットの乗算回路のシフト動作に
   より、前記乗算回路に初期値として入力された前記シン
   ドロームS₀に順次αを乗算し、 その結果得られたパターンと、ｍビットのレジスタに予
   め設定された前記シンドロームS₁のパターンとの一致
   を、前記レジスタの第ｋビット（k:1、２、…、ｍ）の
   出力と前記乗算回路の第ｋビットの出力とを受けるｍ個
   の排他的論理和ゲート、および、前記ｍ個の排他的論理
   和ゲートの出力を受ける論理和ゲートからなる一致検出
   回路により検出し、 前記一致検出回路により一致が検出されるまでに行なわ
   れた前記乗算回路のシフト回数値k₁をカウンタにより計
   数し、前記シフト回数値k₁から誤り位置を求め、 さらに、前記乗算回路に新たに初期値として前記シンド
   ロームS_-1を入力し、前記乗算回路のシフト動作により
   前記シンドロームS_-1に順次αを乗算し、 その結果得られたパターンと、前記ｍビットのレジスタ
   に新たに設定した前記シンドロームS₀のパターンとの一
   致を、前記一致検出回路により検出し、 前記一致検出回路により一致が検出されるまでに行なわ
   れた前記乗算回路のシフト回数値k₂を前記カウンタによ
   り計数し、前記シフト回数値k₂から誤り位置を求め、 前記得られた２つのシフト回数値k₁、k₂が一致するかど
   うかで、誤りが単一シンボル誤りであるかどうかを判断
   する ことを特徴とする誤り位置算出方法。