JPH02303221A - リード・ソロモン符号の復号装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の目的］ （産業上の利用分野） この発明は、ディジタル通信システム、ディジタル記憶
装置等で誤り訂正符号として用いられるリード、ソロモ
ン符号の復号装置に関する。

（従来の技術） ディジタル通信システム、ディジタル記憶装置などにお
いては、伝送または記憶されるデータの信頼性を高める
ために、誤り訂正符号が広く用いられている。リード・
ソロモン符号は、ＢＣＨ符号のサブ・クラスであり、検
査シンボル数に対して最小距離を最大にする符号（Ａｔ
大短距離分離符号という意味で理論的に優れた符号であ
る。また、リード・ソロモン符号は多元符号であるため
複数ビットからなるシンボル単位の誤りを訂正すること
が可能であり、代数的に復号を行うことができるため、
実用的にも有効な符号である。

ＣＤ（コンパクトディスク）、ＤＡＴ（ディジタルオー
ディオチーブ）などのオーディオ記録の分野では、最小
距離が比較的小さく高速の復号が可能なリード・ソロモ
ン符号が用いられる。これに対し、光デイスク記憶装置
、ディジタル衛星通信システムなどの高信頼度の要求さ
れるシステムでは、比較的最小距離の大きいリード・ソ
ロモン符号が用いられることが多い。

一般に、最小距離の大きいリード・ソロモン符号の復号
はアルゴリズムが複雑で、装置化が難しい。効率の良い
復号装置として代表的なものに、シンドローム復号装置
と剰余復号装置とがある。

シンドローム復号装置では、受信信号系列からシンドロ
ームと呼ばれる系列を計算し、これを用いて誤りの位置
と大きさを求める。シンドロームから誤りの位置と大き
さを求めるアルゴリズムとして、バーレカンブ争マツシ
一番アルゴリズム、ユークリッド・アルゴリズム等が提
案されている。

一方、剰余復号装置では、シンドロームを計算すること
なく、受信信号系列と生成多項式から剰余多項式を計算
し、これを用いて誤りの位置と大きさを求める。

剰余復号装置は、一般に第２図のように構成され、次の
手順により復号が行われる。ここでは、α−１αｈ＋ｌ
、・・・、α１°１−２を根として持つ生成多項式〇　
（Ｘ）により生成される符号長ｎ、最小距離ｄのＣ；　
Ｆ　（２”　）上のリード・ソロモン符号を考える。第
２図において、入力端子２１がら人力された受信シンボ
ル系列（Ｒｏ　、Ｒ１、−、Ｒ，、−＋　）は、記憶回
路２２および剰余計算回路２３に供給される。剰余計算
回路２３においては、Ｒ（Ｘ）−Σ　Ｒ＋ｘ’　　　　
　　　　　−（１）をＧ　（Ｘ）で割った剰余多項式 ％式％（） が計算される。

剰余多項式「（Ｘ）は、誤り計算回路２４に供給され、
受信シンボル系列中に発生した誤りの位置（αｌ＋、α
Ｎ７．　　・・・、α　）と大きさくＹ、＋　、　　Ｙ
２　。

ｇ・ ・・・、Ｙ、）が計算される。ここで、ｅ（ｅ＜（ｄ−
１）／　２　）は誤りの個数を示す。誤り訂正回路２５
は、こうして計算された誤りの位置 （αｆｐ、αｊ７２．　　・・・、α　）と大きさくＹ
、、Ｙ２゜ｆｌ＃ ・・・、ｙ、）、および記憶回路２２に記憶されている
受信シンボル系列を受入し、受信シンボルの誤りを訂１
して出力端子２６に出力する。

このような剰余復号装置の具体例は、米国特許４．６３
３，４７０号明！ｉｌｌ書に開示されている。この従来
例の剰余復号装置においては、誤り計算回路２４におい
て、まず次の条件を満足する２つの多項式Ｗ　（Ｘ）と
Ｎ　（Ｘ）を求める。

Ｆ　（Ｘ）　−Ｎ　（ｘ）　／　Ｗ　（Ｘ）　　　　　
　　　−（３）ｄｅｇ（Ｎ　）　＜　ｄｅｇ（Ｗ　）　
≦（ｄ−１）／２　　・（４）ここで、Ｗ（ｘ）を誤り
位置多項式、Ｎ　（ｘ）を誤り数値多項式という。次に
、Ｗ（Ｘ）の根、すなわち誤りの位置 （αＮ′、　　αｉ、・・・、αｎ−，を求める。

さらに、Ｎ（ｘ）とＷ　（ｘ）および誤りの位置から、
誤りの大きさく数値） Ｉ Ｙ、−ｆ（α　）Ｎ（α”）／Ｗ’（αｌ　′＞・・・
（５） を計算する。ただし、　（３）式のＦ　（ｘ）は・・・
（６） であり、　（５）式のｆ　（Ｘ）は ｆ（ｘ）−ｘ−’Σ　ｇｌ（Ｘｌｂ＋口’／Ｃａ−’−
ｘ）・・・（７） ｇ　（Ｘ）−Σ　（Ｘ−α′）−止　ｇｌ　Ｘ’・・・
（８） である。この結果、　（３）式は α’　ｇｋＮ　（α”）＝ｒｋＷ（αｋ）　・・・（９
）となる。そこで、誤り計算回路２４では（９）式を満
足するＮ（ｘ）、Ｗ（ｘ）を求め、さらにＮ（ｘ）＝Ｏ
および（４）式から誤りの位置と大きさを求めている。

上述した従来の剰余復号装置においては、復号過程にお
いて剰余多項式と誤り位置多項式および誤り数値多項式
の関係を（９）式の形でしか表現できない。このため復
号手順が一種類に規定されてしまい、その自由度が小さ
い。

このように復号手順の選択に自由度がないことは、復号
装置の高速化、小形化を達成する上で不利である。

（発明が解決しようとする課題） 上述したように、従来の剰余復号装置では復号過程にお
ける剰余多項式と誤り位置多項式および誤り数値多項式
の関係を一種類の形でしか表現できないため、復号手順
の選択に自由度がなく、復号装置の高速化、小形化に限
界があった。

本発明は、このような課題を解決するためになされたも
のであり、剰余多項式から誤り位置多項式および：もり
数値多項式を求める一連の復号手順を種々変更でき、復
号処理の高速化または装置の小形化を達成することがで
きるリード・ソロモン符号の復号装置を提供することを
目的とする。

［発明の構成］ （課題を解決するための手段） 本発明は上記の課題を解決するため、任意の自然数ｂ、
ガロア体Ｇ　Ｆ　（ｑ）の原始元αに対して、α１．α
ｂｌｌ、・・・、α１′−２を根として持つ生成多項式
〇　（Ｘ）より生成される符号長ｎ、最小距離ｄのリー
ド・ソロモン符号により符号化されたデータを復号する
装置において、 受信シンボルＲ０、Ｒ４，・・・＋Ｒ１１−１を記憶す
る受信シンボル記憶手段と、 前記受信シンボルＲ０、Ｒ４、…、Ｒ，−、を受入し、 をＧ　（ｘ）で割ったときの剰余多項式により、剰余「
。、　　１．・・・＋’ｄ−２を求める剰余計算手段と
、 前記剰余「。ｒ　　　Ｉｎ　・・・＋’ｄ−２と、Ｇ　
Ｆ　（ｑ）「 の（Ｉ’　意の非零元の定数Ａに対して、Ｎ（α＆）−
「、ζ、Ｗ（αｋ）　　　・・・（ｌＯ）（ｋ−０，１
，−、ｄ−２） を満足し、かつｄ／２未満の整数ｅに対して、ｄｅｇ（
Ｎ　）　＜　ｄｅｇ（Ｗ）　　＝　ｅ　　　　　　　　
−（１２）を満たす基本多項式Ｎ　（Ｘ）、Ｗ　（Ｘ）
を計算する基本多項式演算手段と、 前記基本多項式Ｗ　（ｘ）の根を前記受信シンボルの誤
り位置Ｚｌ＋Ｚ２＋　・・・、Ｚ、として計算する誤り
位置計算手段と、 前記誤り位置２．．２．、・・・、Ｚ、から、前記受信
シンボルＲｏ、Ｒ，，・・・＋Ｒａ−１の誤り数値Ｙ、
−ξ　Ｎ　（Ｚ　＋　）　／Ｗ’（Ｚ　＋　）　　　・
・・（１３）（ｊ−１，２、…、ｅ） （ｚ、−α４７　ｒ　＞ をλ１算する誤り数値計算手段と、 前記受信シンボル記憶手段に記憶されている受信シンボ
ルＲ６，Ｒ１、…、Ｒｏ−１を受入し、前：Ｃ！誤り位
置２．．２２．・・・、Ｚ、により規定される位置の受
信シンボルに発生している、前記誤り数値Ｙｌ＋Ｙ２＋
　・・・、Ｙ、に示される大きさの誤りを訂正する誤り
訂正手段と を備えたことを特徴とする。

（作用） 本発明では、（１０）式、　（１４）式における非零元
の定数Ａを任意に選択することができる。因みに、上述
した本発明に関する記述に対応させて前記公知例の剰余
復号装置を表現すると、Ａは次式により一意に決定され
る定数となる。

従って、本発明では剰余多項式と誤り位置多項式および
誤り数値多項式の関係を複数の形で表現することが可能
になる。この結果、設計の際の復号手順選択の自由度が
増し、処理速度や装置の小形化に関して最適化ができる
。

具体的には、例えばζ０．ξ、はそれぞれ（１１）式お
よび（１４）式により計算されるが、これらの値を復号
時に求める場合には、Ａ−１とすることにより乗算回数
が最小限で済む。

また、復号時に随時ξ１を計算する場合には、（１４）
式を用いてＺ、からξｊを求めることにより、全体とし
ての計算量が減少する。一方、ξ）−ξ、−１α−ゝ（
ｌ−α１−ｄ″２）　／（１−α″″ｌ）の関係を用い
てξ、−１からξ、を順次計算した場合、全体の計算量
は増えるが、単位時間当りの計算回数が削減されるため
、演算回路を時分割で異なる演算に使用する場合の多重
化効率が高くなり、それだけ装置の小形化が達成される
。

また、ζ、やξ、を記憶回路に記憶しておけば、基本多
項式演算回路および誤り数値計算回路におけるこれらの
値の計算が不必要になり、高速な復号が可能になる。

更に、ξ１を記憶回路に記憶する場合において、ｄが奇
数のときは ｂ　−（２ｎ−ｄ＋１）　／２ とすることにより、 ξｌ（ｓ＋４−２１．’２１−１−ξｌ（＊＋４−２１
．’２１＋Ｊとなって、記憶すべきξ１の個数が約半分
で済む。

同様に、ｄが偶数のときは ｂ　−（ｎ　−ｄ　＋　１　）　／　２とすることより
、 ξ　Ｉｔｓ中−−３）　７２しｊ　−ξ　ＩＴａ＋４−
３）、’２１＋Ｉ◆１となるから、やはり記憶すべきξ
）の個数が約半分となる。

（実施例） 以下、この発明によるリード・ソロモン符号の復号装置
の一実施例を説明する。本実施例では符号長１５．最小
圧Ｍ７　、　ＣＰ（２’　）上の（１５，９）リード・
ソロモン符号を考える。

ただし、この符号は次式の生成多項式 ｍ　Ｘ　’　＋　αＩ　ｌ　ｘ　′＋αＸ’　＋ａ７ｘ
’＋α１０Ｘ２＋α１４Ｘ゛＋α′２　　　　　　　　
・・・（１６）により生成される組織符号で、符号語を
（Ｃｏ　。

Ｃ＋　、　”’、　　Ｃ＋４）とすると、Ｃｎ　、　川
、　　Ｃｓが検査シンボル、Ｃ６１・・・、Ｃ３４が情
報シンボルとなる。

ここで、αはＧ　Ｆ　（２）上の多項式Ｘ４＋Ｘ＋１の
原始元とする。復号中、扱われるシンボルはすべてＧ　
Ｆ　（２’　）の元であり、４ビツトで表現され、シン
ボル中位に処理されるものとする。また、ここでは適当
に選択可能な定数Ａ（ＣＦ（２４）の元）は１とする。

第１図は、このようなリード・ソロモン符号の剰余復号
装置の本発明に基づく概略的構成図である。

受信シンボルＲ，，，Ｒ，、…、Ｒ１４は、入力端子１
から人力され、剰余計算回路２と記憶回路３に供給され
る。剰余計算回路２においては、をＧ　（ｘ）で割った
ときの剰余多項式％式％（） の６個の剰余（係数）ｒｏ＋　　’ｌ＋　・・・、「、
が計算される。この剰余計算回路２は、リード・ソロモ
ン符号化器と同様に、フィードバック・シフトレジスタ
により構成することができる。

基本方程式演算回路４は、剰余計算回路２により求めら
れた剰余ｒ。、　　ｌ、・・・、Ｃ５を受入し、「 次式の条件を満足する２つの多項式Ｗ　（Ｘ）　、　Ｎ
　（ｘ）の係数Ｗ。＋　Ｗ　＋　１　・・・、　ＷＪ＊
ｇＮおよびＮ。、Ｎ１゜・・・ｒ　ＦＪ、ｅｔＮを求め
る。

Ｎ　　（α’　　）　　−ｒ、　　ζ、Ｗ　　Ｃａ”　
　）　　　　＝ｉ１８）（ｋ−０，１、・・・、５） ｄｅｇ（Ｎ）　＜ｄｅｇ（Ｗ）　−ｅ≦３ただし、 ζ０１α７１　Ｃ１−Ｃ７，ζ２Ｍ　（Ｚ　’ｌζ１″
α８．ζ４−α４．ζ、ヨａ＋２は、計算回路１１によ
り予め計算され、記憶回路９に保持されている。〈１８
）式は逆行列または多項式補間のアルゴリズムを用いて
、解くことができる。

基本方程式演算回路４で計算されたＷ（ｘ）の係数Ｗｏ
　、Ｗ＋　、・・・、Ｗ、は、誤り位置計算回路５に供
給される。誤り位置計算回路５は、αＯ１・・・。

α′４のなかでＷ（ｘ）の根となるもの、すなわちＺ、
−α　、Ｚ２−αｆｉ２．・・・、Ｚ、−０ｇ０を求め
ＩＩ る。ここで％　ｊ！　ｌ　Ｔ　１２　＋　・・・１ｇ、
は誤りの位置である。なお、誤り位置計算回路５は例え
ばチェノ・サーチ回路により構成される。

誤り位置計算回路５によって計算されたＺ、。

Ｚ２．・・・ＩＺｅは、誤り数値計算回路６と誤り訂正
回路７に供給される。

誤り数値計算回路６は、２．．２２．・・・、Ｚ。

と、Ｉｌｌ、Ｉ２．−．１−と、ＮＯ，Ｎ、、　　　。

Ｎ　ａｍｚｐｔｓおよびＷ、、Ｗ、、−、Ｗ、を受入し
、次式に示す誤りの大きさＹ、−Ｙ、、Ｙ、、・・・。

Ｙ、を求める。

Ｙ＋　−Ｅ、、、Ｎ　　（Ｚｒ　）　／Ｗ’（Ｚｒ　）
　　−（Ｉ９）（ｊ−１，２、…、ｅ） ここで、Ｗ’（ｘ）はＷ（ｘ）の形式的微分である。ま
た、 ξ・＝ａ′３．ξ７−（Ｚ　６ｒ　　ξ、＝α１０゜ξ
　９−ｊ！、　　　　　　　ξ　、０−　α　９　　、
　　　ξ　１１　−　α　５　　。

ξ１２−α５Ｉ　ξ目−α６．ξ１４’″α３は計算回
路１２によって予め計算され、記憶回路１０に記憶され
ている。記憶回路１０からは、ＩＩ Ｚ」−α　に対応するξｆｉ％Ｊ”１．２．・・・、ｅ
）が読み出され、誤り数値計算回路６に供給される。

ここで、扱われるリード・ソロモン符号がα１２゜α１
３．　α１４．　　ｌ、α、α２を根とする生成多項式
により生成されている場合、すなわちｂ−１２の場合、
記憶回路１０に保持するデータを次の５個に減らすこと
ができる。

ξ０−α１１．ξ７−α１１．ξ８−α５゜ξ、−ｇ、
　　ξ１ｏ−α１４ このとき、ξ。−ξ１４．ξ７−ξ、３．ξ８−ξ１２
゜ξ、−ξ１１となっている。

誤り訂正回路７は、誤り位置計算回路うで計算された情
報シンボル上の誤り位置１１　＋　１’　２　＋　・・
・。

Ｎ　１１　、誤り数値計算回路６で＝１算された誤りの
大きさＹ、、Ｙ２．・・・、Ｙｏ、および記憶回路２に
Ｊ己憶されている受信シンボルＲ０、・・・、Ｒ，、の
系列を受入し、受信系列の誤りを訂正して出力端子８に
出力する。

本発明は上記実施例に限られず、種々変形して実施する
ことが可能である。例えば記憶回路１０を設ける代わり
に、誤り位置計算回路６から誤り位置２．．２２．・・
・、Ｚ、を受入し、Ｚ、−ａ” を計算する回路を用いてもよい。このような計算回路を
設けると、ｎが大きい場合には、記憶回路１０を設ける
場合と比較して回路が小形となる。

また、ξ６．を初期値として持ち、 ξ８９．＝ξ１−Ｉα−’（１−α’−”２）　／（１
−α」ｌ）・・・（２１） の漸化式により、ξ、からξｊゆ１を順次生成する計算
回路を設けてもよい。この計算回路は（２０）式の計算
を行う計算回路より計算回数は増えるが、単位時間当た
りの計算数が減少することにより、さらに小型の回路と
なる。

［発明の効果］ 以上説明したように、本発明によるリード・ソロモン符
号の復号装置では、剰余多項式と誤り位置多項式および
誤り数値多項式の関係を示す非零元の定数Ａを適切に選
択することにより、従来の剰余復号装置と比べて、計算
回数の削減による復号処理の高速化または回路の小形化
を図ることができる。

また、ζ１．ξ、を記憶する回路を設けることにより、
復号の高速化が可能になるが、このとき生成多項式にお
けるｂを適当に設定することにより、記憶すべきξ、の
個数をほぼ半分に低減することができ、記憶回路の容量
を最小限にとどめることがｎ１能となる。

【図面の簡単な説明】

第１図はこの発明の一実施例に係るリード・ソロモン符
号の復号装置の概略的構成図、第２図は一般の剰余復号
装置の概略的構成図である。 ］　・・・入力端子 ２　・・・記憶回路 ３　・・・剰余演算回路 ４　・・・基本多項式演算回路 ５　・・・誤り位置計算回路 ６　・・・誤り数値計算回路 ７　・・・誤り訂正回路 ８　・・・出力端子 ９　・・・記憶回路 １０・・・記憶回路 １１・・・ζ計算回路 １２・・・ζ計算回路

Claims (6)

【特許請求の範囲】
1. （１）任意の自然数ｂ、ガロア体ＧＦ（ｑ）の原始元α
   に対して、α＾ｂ、α＾ｂ＾＋＾１、…、α＾ｂ＾＋＾
   ｄ＾−＾２を根として持つ生成多項式Ｇ（ｘ）より生成
   される符号長ｎ、最小距離ｄのリード・ソロモン符号に
   より符号化されたデータを復号する装置において、受信
   シンボルＲ＿０、Ｒ＿１、…、Ｒ＿ｎ＿−＿１を記憶す
   る受信シンボル記憶手段と、 前記受信シンボルＲ＿０、Ｒ＿１、…、Ｒ＿ｎ＿−＿１
   を受入し、 Ｒ（ｘ）＝Σ＾ｎ＾−＾１＿ｉ＿＝＿０Ｒ＿ｉｘ＾ｉを
   Ｇ（ｘ）で割ったときの剰余多項式 ｒ（ｘ）＝Σ＾ｄ＾−＾２＿ｉ＿＝＿０＿，＿ｉ＿≠＿
   ｋｒ＿ｉｘ＾ｉにより、剰余ｒ＿０、ｒ＿１、…、ｒ＿
   ｄ＿−＿２を求める剰余計算手段と、 前記剰余ｒ＿０、ｒ＿１、…、ｒ＿ｄ＿−＿２と、ＧＦ
   （ｑ）の任意の非零元の定数Ａに対して、 Ｎ（α＾ｋ）＝ｒ＿ｋζ＿ｋＷ（α＾ｋ）（ｋ＝０、１
   、…、ｄ−２） ζ＿ｋ＝Ａ＾−＾１α＾ｂ＾ｋ■＾ｄ＾−＾２＿ｉ＿＝
   ＿０＿，＿ｉ＿≠＿ｋ（α＾ｉ−α＾ｋ）を満足し、か
   つｄ／２未満の整数ｅに対して、ｄｅｇ（Ｎ）＜ｄｅｇ
   （Ｗ）＝ｅ を満たす基本多項式Ｎ（ｘ）、Ｗ（ｘ）を計算する基本
   多項式演算手段と、 前記基本多項式Ｗ（ｘ）の根を前記受信シンボルの誤り
   位置Ｚ＿１、Ｚ＿２、…、Ｚ＿ｅとして計算する誤り位
   置計算手段と、 前記誤り位置Ｚ＿１、Ｚ＿２、…、Ｚ＿ｅから、前記受
   信シンボルＲ＿０、Ｒ＿１、…、Ｒ＿ｎ＿−＿１の誤り
   数値Ｙ＿ｊ＝ξ＿ｌ＿＿ｊＮ（Ｚ＿ｊ）／Ｗ’（Ｚ＿ｊ
   ）（ｊ＝１、２、…、ｅ） ξ＿ｌ＿＿ｊ＝Ａ／｛Ｚ＿ｊ＾ｂ■＾ｄ＾−＾２＿ｉ＿
   ＝＿０（α＾ｉ−Ｚ＿ｊ）｝（Ｚ＿ｊ＝α＾ｌ＾＿＾ｊ
   ） を計算する誤り数値計算手段と、 前記受信シンボル記憶手段に記憶されている受信シンボ
   ルＲ＿０、Ｒ＿１、…、Ｒ＿ｎ＿−＿１を受入し、前記
   誤り位置Ｚ＿１、Ｚ＿２、…、Ｚ＿ｅにより規定される
   位置の受信シンボルに発生している、前記誤り数値Ｙ＿
   １、Ｙ＿２、…、Ｙ＿ｅに示される大きさの誤りを訂正
   する誤り訂正手段と を備えたことを特徴とするリード・ソロモン符号の復号
   装置。
2. （２）前記ξ＿ｊ（ｊ＝２、３、…）を求めるために、
   ξ＿ｊ＝ξ＿ｊ＿−＿１α＾−＾ｂ（１−α＾ｊ＾−＾
   ｄ＾＋＾２）／（１−α＾ｊ＾＋＾１）を順次計算する
   手段を更に備えたことを特徴とする請求項１に記載のリ
   ード・ソロモン符号の復号装置。
3. （３）前記の定数Ａに対して、予め計算されたζ＿ｋ＝
   Ａ＾−＾１α＾ｂ＾ｋ■＾ｄ＾−＾２＿ｉ＿＝＿０＿，
   ＿ｉ＿≠＿ｋ（α＾ｉ−α＾ｋ）を記憶する手段を更に
   備えたことを特徴とする請求項１または２に記載のリー
   ド・ソロモン符号の復号装置。
4. （４）前記定数Ａに対して、予め計算されたξ＿ｊ＝Ａ
   ／α＾ｊ＾ｂ■＾ｄ＾−＾２＿ｉ＿＝＿０（α＾ｉ−α
   ＾ｊ）を記憶する手段を更に備えたことを特徴とする請
   求項１、２または３に記載のリード・ソロモン符号の復
   号装置。
5. （５）前記定数Ａに対して、予め計算されたξ＿ｊ＝Ａ
   ／α＾ｊ＾ｂ■＾ｄ＾−＾２＿ｉ＿＝＿０（α＾ｉ−α
   ＾ｊ）を記憶する手段を更に備え、かつｄを奇数とし、
   ｂを（２ｎ−ｄ＋１）／２としたことを特徴とする請求
   項１、２または３に記載のリード・ソロモン符号の復号
   装置。
6. （６）前記定数Ａに対して、予め計算されたξ＿ｊ＝Ａ
   ／α＾ｊ＾ｂ■＾ｄ＾−＾２＿ｉ＿＝＿０（α＾ｉ−α
   ＾ｊ）を記憶する手段を更に備え、かつｄを偶数とし、
   ｂを（ｎ−ｄ＋１）／２としたことを特徴とする請求項
   １、２または３に記載のリード・ソロモン符号の復号装
   置。