JPH03190326A - 誤り訂正演算用多項式生成回路 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、情報記録再生装置の符号誤り訂正装〔従来の
技術〕 情報記録再生装置において、データの誤りに対する信頼
性を向上させるため、リード・ソロモン符号等の誤り訂
正符号による誤り訂正が実行されている。この誤り訂正
の方法として、ポインタにより示されるエラー位置情報
を用いるイレージヤ訂正方法がある。この方法について
は、特開昭６４−１３３２号公報に記載されており、以
下のようになっている。

リード・ソロモン符号の復号方法は、 （１）シンドローム（多項式）の計算 （２）誤り位置多項式、誤り評価多項式の導出 （３）誤り位置と誤り値の演算 （４）誤り訂正の実行 の手順で実行される。

イレージヤ訂正（ポインタで示されたエラー位置以外に
誤りがない）の場合、エラー位置が既知ことより、イレ
ージヤ訂正の場合、以下の手順で復号が実行される。

（１）シンドローム（多項式）、誤り位置多項式の計算 （２）誤り評価多項式の導出 （３）誤り値の演算 （４）誤り訂正の実行 リード・ソロモン符号のｔ重誤り訂正用パリティ生成多
項式〇　（ｚ）を以下に示す。ここでαは、ｍ次（ｍ＝
１．２、…）の法多項式を満たすガロア体ＧＦ　（２”
）の原始光であり、乗算、加算は、このガロア体上で実
行される。

Ｇ　（ｚ）＝ｎ　　（ｚ＋α１） この誤り訂正用パリティ生成多項式〇　（ｚ）の根α’
　　（ｉ＝１．２．・・−，２ｔ）と受信信号Ｄａ。

Ｉ）ｆｉ−、、＋＋＋　　Ｄａｙ　Ｄｔ　＜符号長ｎ）
より、以下に示すシンドローム８０〜５ｉｔ−ｔが生成
される。

Ｓａｇ−Ｌ＝Ｄ１１　・（ｚ”””−”＋Ｄ、−＋＃α
ｌｔ−Ｉｎ−１７＋、、。

＋Ｄ、・α　　　＋ＤＩ・α ＝ΣＤ、・α！ｔ゛ｌｌ−１１ ｉｓ＋＋ｔ ＳＪ＝ΣＤ、・ａＣ川）　−ｆｌ−１１ｍ１ （Ｏ≦ｊ　（２ｔ　） ｓ、　＝＝　Ｘ　ｐ、　、　αに’　ｆｌ−１１誤り訂
正演算用には１種々の多項式があり、それらは次式を満
足する。

φ（ｚ）・Ｘ２ｔ＋σ（ｚ）・５（ｚ）＝ω（ｚ）これ
より次式が成り立つ。

σ（ｚ）・５（ｚ）ミｔ＋＞（ｚ）　　　（ｍｏｄ　　
ｚ”）但し、 ５（ｚ）：Ｓｏ＋Ｓｔ　’　Ｚ”””５ｉｔ−Ｌ　ｊ　
ｚ”　−１＝　Σ　Ｓ＋−ｚ’ −０ ：シンドローム多項式 ％式％） ：誤り位置多項式 ω　（Ｚ）＝　Σ　Ｅｌ−ＩＴ　　　　（ｚ−ｘｋ）・
ｉεＥ　　　　　　ａｍεＥ、ａｋ≠＠ｉ：誤り評価多
項式 ここでＥは誤りの場合、Ｅｌはエラー位置ｅｔにお番）
誤り値、Ｘｉは以・下に示すとおりエラー位１ｉｓｔに
対応する値（エラー位置情報）である。

ｘ１＝　ａ−ｆ＠ｌ−１１［ｃｒ　（ｘυ＝Ｏ］シンド
ローム多項式Ｓ　（ｚ）は、シンドロームを係数とする
多項式であり、誤り位置多項式σ（ｚ）は、エラー位置
情報を根とする多項式である。これら２式を乗算し、ｘ
ｚｔで除算した余り（積多項式の２を次未満の項）が、
誤り評価多項式ω（Ｚ）となるに の誤り位置多項式〇（Ｚ）と誤り評価多項式ω（ｚ）よ
り、以下のように誤り値が演算される。

（エラー位置は、ポインタにより示されており既知であ
る） 誤り値の演算には、誤り位置多項式σ（ｚ）を形式微分
したσ′　（２）が用いられる。σ′　（２）を以下に
示す。

（以下、余白） ＝２ｔ°σ２．・Ｚｉｔ−＋ ＋　（２ｔ−１）　　・σ２．−４・ｚＩｔ−１＋２・
σ２・２＋σ１ ＝（７！ｔ−、°２１ｃｍ１＋σ見ｔ−ａ　、　ｚＩｔ
−４＋・・・＋σ３Ｈ２２＋σ、 ＝Σσ□−１・Ｚ！＋４ ｘｌ （”、−２・α１＝α１＋α’＝Ｏ：ｉは任意の値）但
しσ。は、誤り位置多項式σ（ｚ）のｉ次の項の係数で
ある。

エラー位置情報ｘｔを誤り位置多項式の形式微分σ’（
ｚ）、誤り評価多項式ω（Ｚ）に代入すると以下のよう
になる。

σ　　（Ｘ、）＝　　　ｒＩ　　　（Ｘ、−Ｘ、）６に
εＥ、ａｋ≠６ｉ ω（ｘｔ）　＝Ｅ＋　・ｎ　　　　（ｘｔ　　ｘｋ）ａ
ｍεＥ、ａｋ≠ａｉ これらよりエラー位置ｅ、における誤り値Ｅｌは以下の
ように求められる。

を重誤り訂正用リード・ソロモン符号の場合、２を個の
シンドロームが生成され、最大２を個のデータの訂正が
可能である。また誤り位置多項式の次数は最大２ｔであ
り、誤り評価多項式の次数は最大２ｔ−１である。

以下に、従来の誤り訂正演算用多項式（シンドローム多
項式／誤り位置多項式／誤り評価多項式）の生成回路に
ついて示す（ｔ＝４の場合）。

第２図は、従来のシンドローム多項式生成回路を示すブ
ロック図である。第２図において、２゜Ｏ〜２０７はレ
ジスタ、２１０〜２１７はガロア体の加算器、２２０〜
２２７はガロア体の乗算器である。レジスタ、加算器、
及び乗算器よりなる単位構成が８段接続されており、各
乗算器には誤り訂正用パリティ生成多項式の根α１〜α
９が供給されている。入力端子より受信データＤｎ＋Ｄ
ａ−Ｌ？・・・Ｄ２．　Ｄｌを１＠次入力し、入力終了
時のレジスタの値がシンドローム（シンドローム多項式
の係数）となる。

第３図は、従来の誤り位置多項式生成回路を示すブロッ
ク図である。第３図において、３００〜３０８．３１０
〜３１７はレジスタ、３２０〜３２７はガロア体の加算
器、３３０〜３３７はガロア体の乗算器である。２個の
レジスタ、加算器、及び乗算器よりなる単位構成が８段
接続されており、各乗算器にはポインタで示されるエラ
ー位置に対応する値Ｘ□〜Ｘ、が供給されている。入力
端子より１．Ｏ，Ｏ，・・・を順次入力することにより
、出力端子よりσ８．σ７．・・・、σ０．σ。が順次
出力される（σｉ：誤り位置多項式σ（ｚ）のｉ次の項
の係数）。

第４図は、従来の誤り評価多項式生成回路（多項式の乗
算回路）を示すブロック図である。第４図において、４
００，４１０〜４１７はレジスタ、４２１〜４２７はガ
ロア体の加算器、４３０〜４３７はガロア体の乗算器で
ある。レジスタ、加算器、及び乗算器よりなる単位構成
が８段接続されており、各乗算器にはシンドローム８７
〜Ｓ０が−供給されている。入力端子より誤り位置多項
式の係数σ、、σ７．・・・　σ□、σ。を順次入力し
、入力終了時の各レジスタの値が誤り評価多項式の係数
となる。更に入力端子よりＯ２・・・を入力することに
より、出力端子より、誤り評価多項式の係数ω７．ω８
．・・・、ω１．ω。がｊ順次出力される。

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

しかしながら、上記のように誤り訂正演算用多項式生成
回路を、シンドローム多項式生成回路、誤り位置多項式
生成回路、誤り評価多項式生成回路より成る回路構成と
すると、ガロア体の乗算器を多数使用することとなり、
回路規模が大きくなるという問題点を有していた。例え
ば、ガロア体ＧＦ（２”）の乗算器の規模は、約５００
ゲートであり、を重誤り訂正用リード・ソロモン符号の
場合、乗算器を６を個必要とし、この乗算器のみで３０
００・ｔゲートとなり、訂正能力の増大にともない回路
規模も増大する。

本発明の目的は、演算の高速性を損なうことなく、回路
規模を削減することが可能な誤り訂正演算用多項式生成
回路を提供することにある。

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

上記した目的を達成するために、本発明では、入力デー
タと誤り訂正用パリティ生成多項式の根または特定のデ
ータとを入力し、いずれが一方を選択して出力する第１
の選択回路と、該第１の選択回路からの出力とレジスタ
からの出力とを乗算し、その乗算結果を出力するガロア
体の乗算器と、入力データまたは特定データと出力デー
タとを入力し、いずれか一方を選択して出力する第２の
選択回路と、該第２の選択回路からの出力と前記乗算器
からの出力とを加算し、その加算結果を出力するガロア
体の加算器と、該加算器からの出力を一旦蓄え、その後
、出力する前記レジスタと、で稙成される演算手段を、
上位から下位に向かって２ｔ＋１段並べ、各演算手段の
前記レジスタの出力を、それぞれ、１段下位の演算手段
の前記第２の選択回路に前記出力データとして入力する
と共に、共通のデータを各演算手段の前記第１及び第２
の選択回路に前記入力データとして入力し、各・、献立
手段の前記′シフタの出力からそれぞれ・前記シンドロ
ーム多項式、誤り位置多項式及び誤り評価多項式の各多
項式の係数を得るようにした。

〔作用〕

本発明では、第１及び第２の選択回路を用いることによ
り、シンドローム多項式、誤り位置多項式及び誤り評価
多項式の３種類の多項式の生成演算において、ガロア体
の加算器、乗算器を共用して使用している。このことに
より、使用するガロア体の乗算器の個数を減少させるこ
とができ、回路規模の削減が可能となる。

また、レジスタ、ガロア体の加算器、乗算器、第１及び
第２の選択回路から成る前記演算手段を２ｔ＋１段並べ
接続することにより、多項式の生成演算を高速に実行す
ることが可能となる。

〔実施例〕

以下、本発明の一実施例について図面を参照しながら説
明する。

第１図は、本発明の一実施例としての誤り訂正演算用多
項式（シンドローム多項式／誤り位置多項式／誤り評価
多項式）生成回路を示すブロック図であり、４重誤り訂
正用リード・ソロモン符号の場合を示すものである。

第１図において、１００〜１０８はレジスタ、１１０〜
１１８はガロア体の加算器、１２０〜１２８はガロア体
の乗算器、１３０〜１３８゜１４０〜１４８は２人力１
出力選択回路である。

なお、レジスタのクロック信号は、図示していないが、
入力端子からの入力毎に発せられる。

またαはガロア体の原始元であり、誤り訂正用パリティ
生成多項式〇　（ｚ）は次式とする。

Ｇ（ｚ）＝（ｚ＋α１）・（ｚ＋α２）・（Ｚ＋α３）
・・・・・（２＋α７）・（２＋αＳ） 以下、下記の順序にしたがって説明する。

ａ）シンドローム（多項式）の生成 り）誤り位置多項式の生成 Ｃ）誤り評価多項式の生成 １４０〜１４８の選択をＢとする。これにより、第２図
に示す回路と同様になる。乗算器にはレジスタの出力と
誤り訂正用パリティ生成多項式の根α’　　（ｉ＝１．
２．・・・８）が供給され、加算器には乗算器の出力と
入力端子からの受信データが供給される（加算器１１０
には０が供給される）。

そして、この加算器の出力を再びレジスタに入力する。

この動作を符号長（ｎ）分繰り返す。全ての受信データ
の入力が終了した時点のレジスタ１０１〜１０８の出力
がシンドローム（多項式の係数）Ｓ７〜Ｓ、となる。

例として、入力端子より受信データＤヶ、Ｄ。−４゜・
・・＋ＤｘｔＤｘが入力された場合のレジスタ１０１の
出力を以下に示す。

（以下、余白） ａ）シンドローム（多項式）の生成 まず初期設定としてレジスタ１００〜１０８をクリアし
、２人力１出力選択回路１３０〜１３８゜給され、加算
器には、乗算器の出力と、１段下位のレジスタの出力が
供給される（加算器１０８には、Ｏが供給される）。そ
して、この加算器の出力をレジスタに入力する。この動
作をポインタの個数だけ繰り返す。全てのエラー位置情
報の入力が終了した時点のレジスタ１００〜１０８の出
力が誤り位置多項式の各項に対応する係数σ、〜σ。

どなる。

例としてエラー位置情報Ｘ工、ｘ２．Ｘ、が与えられた
場合のレジスタ１００〜１０８の出力を多項式表現で示
す。

（以下、余白） ｂ）誤り位置多項式の生成 まず初期設定としてレジスタ１００〜１０７をクリアし
、レジスタ１０８には、α０＝１を入力し、２人力１出
力選択回路１３０〜１３８゜１４０〜１４８の選択をＡ
とする。乗算器には、レジスタの出力と入力端子からの
エラー位置情報（Ｘｌｙ　Ｘ２１　ｘ３ｔ　”’ＨＸ（
＝１は２を以下）が供ドローム多項式５（ｚ）と誤り位
置多項式σ（Ｚ）の積の８次未満の項）の各項に対応す
る係数ω７〜ω。どなる。

例としてシンドローム８７〜Ｓ、（シンドローム多項式
５（Ｚ））、エラー位置情報ＸｘＨＸｚｙ　Ｘ３が与え
られた場合のレジスタ１０１〜１０８の出力を多項式表
現で示す。

Ｃ）誤り評価多項式の生成 まず初期設定として、レジスタ１０１〜１０８にシンド
ローム８１〜Ｓ８を人力し、２人力１出力選択回路１３
０〜１３８，１４０〜１４８の選択をＡとする。これに
対し誤り位置多項式生成のときと同様の動作を実行する
ことにより、レジスタ１０１〜１０８の出力が、誤り評
価多項式（シンまた、誤り評価多項式は、ａ）、ｂ）の
動作を連続して実行することによっても求めることがで
きる。

まず初期設定としてレジスタ１００〜１０８をクリアし
、２人力１出力選択回路１３０〜１３８・１４０〜１４
８の選択をＢとし、入力端子より受信データＤ。、Ｄ。

−４，・・・、Ｄ２．Ｄ□を順次入力する。全ての受信
データを入力し終わった時点の、レジスタ１０１〜１０
８の値がシンドローム８７〜Ｓｏとなり、続いて２人力
１出力選択回路１３０〜１３８，１４０〜１４８の選択
をＡとし、入力端子よりエラー位置情報Ｘ工、　ｘ２．
　ｘ、、　　・を入力する。全てのエラー位置情報の入
力が終了した時点のレジスタ１０１〜１０８の値が誤り
評価多項式の各項に対応する係数ω７〜ω。どなる。

このように、本実施例の様な構成とすることにより、誤
り訂正演算用多項式の生成に使用するガロア体の乗算器
の個数を減少させることができ、回路規模を削減するこ
とができる。

〔発明の効果〕

本発明によれば、リード・ソロモン符号のイレージヤ訂
正における誤り訂正演算用多項式（シンドローム多項式
／誤り位置多項式／誤り評価多項式）の生成を２人力１
出力選択回路の選択を変え実行することにより、使用す
るガロア体の乗算器の個数を減少させ、回路規模の削減
が可能となる。

また、レジスタ、ガロア体の加算器、乗算器、及び２個
の２人力１出力選択回路より成る演算手段を２ｔ＋１段
並べ接続することにより、多項式の生成演算を高速に実
行することができる。

【図面の簡単な説明】

第１図は本発明の一実施例としての誤り訂正演算用多項
式生成回路を示すブロック図、第２図は従来のシンドロ
ーム多項式生成回路を示すブロック図、第３図は従来の
誤り位置多項式生成回路を示すブロック図、第４図は従
来の誤り評価多項式生成回路を示すブロック図である。 １ｏＯ〜１０８，２００〜２０７，３００〜３０８．３
１０〜３１７・・・・・・レジスタ、１１０〜１１８，
２１０〜２１７，３２０〜３２７．４２１〜４２７・・
・・・・ガロア体の加算器、１２０〜１２８，２２０〜
２２７，３３０〜３３７．４３０〜４３７・・・・・・
ガロア体の乗算器、１３０〜１３８，１４０〜１４８・
・・・・・２人力１出力選択回路。 篤　　１ 図

Claims (1)

1. 【特許請求の範囲】 １、符号語がｍ（ｍ＝１、２、…）の法多項式を満足す
   るガロア体ＧＦ（２＾ｍ）の元から構成されるｔ重誤り
   訂正用リード・ソロモン符号の復号をあらかじめ誤りで
   あると思われるデータの位置を示すポインタを利用した
   イレージャ訂正方法を用いて行う際に、シンドローム多
   項式、誤り位置多項式及び誤り評価多項式の各多項式の
   係数をそれぞれ生成する誤り訂正演算用多項式生成回路
   において、 入力データと誤り訂正用パリテイ生成多項式の根または
   特定のデータとを入力し、いずれか一方を選択して出力
   する第１の選択回路と、該第１の選択回路からの出力と
   レジスタからの出力とを乗算し、その乗算結果を出力す
   るガロア体の乗算器と、入力データまたは特定データと
   出力データとを入力し、いずれか一方を選択して出力す
   る第２の選択回路と、該第２の選択回路からの出力と前
   記乗算器からの出力とを加算し、その加算結果を出力す
   るガロア体の加算器と、該加算器からの出力を一旦蓄え
   、その後、出力する前記レジスタと、で構成される演算
   手段を、上位から下位に向かって２ｔ＋１段並べ、各演
   算手段の前記レジスタの出力を、それぞれ、１段下位の
   演算手段の前記第２の選択回路に前記出力データとして
   入力すると共に、共通のデータを各演算手段の前記第１
   及び第２の選択回路に前記入力データとして入力し、各
   演算手段の前記レジスタの出力からそれぞれ、前記シン
   ドローム多項式、誤り位置多項式及び誤り評価多項式の
   各多項式の係数を得ることを特徴とする誤り訂正演算用
   多項式生成回路。