JPS63316524A - リ−ド・ソロモン符号の復号方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、リード・ソロモン符号の復号方法に関する
。

〔発明の概要〕

この発明では、ユークリッド互除法により、誤り多項式
σ（ｘ）と誤り評価多項式ω（ｘ）を導出するようにし
たリード・ソロモン符号の復号方法において、 シンドローム多項式Ｓ　（ｘ）を求め、シンドローム多
項式Ｓ　（ｘ）と訂正しようとするシンボル数ｔで定ま
る初期多項式ｘ２Ｌとの互いの最高次数を乗算しあいな
がら一つづつ順に次数を減らすことでｆ（ｘ）　−Ｂ　
（ｘ）　＋ｇ（ｘ）　・Ｓ　（ｘ）　＝ｈ（ｘ）（但し
、ｈ　（ｘ）の次数＜　ｇ　（ｘ）の次数≦ｔ）の関係
を満足する多項式ｈ　（ｘ）及びｇ（に）を求め、多項
式ｇ　（ｘ）を誤り位置多項式σ（ｘ）とし、多項式ｈ
　（ｘ）を誤り評価多項式ω（ｘ）とすることにより、
実時間処理が可能なリード・ソロモン符号の復号方法が
実現される。

〔従来の技術〕

リード・ソロモン符号（Ｒｅｅｄ　Ｓｏｌｏｍｌｏｎ　
Ｃｏｄｅ）の復号は、 ｉ）シンドロームの計算 ｉｉ）誤り位置多項式σ（ｘ）、誤り評価多項式ω（ｘ
）の導出 １ｉｉ）誤り位置と誤り値の推定 ｉｖ）誤り訂正の実行 のステップでなされる。従来の方程式の根を利用した解
を用いる復号方法は、５誤り以上の多重誤りの訂正の場
合には、適用できない。この５誤り以上の訂正の場合に
は、ユークリッド互除法を用いたものが知られている。

即ち、ユークリッド互除法を使用して、誤り位置多項式
σ（ｘ）及び誤り評価多項式ω（ｘ）の産出がなされる
。

リード・ソロモン符号のｔ重誤り訂正用のパリティ検査
行列Ｈは、（ｔ：訂正可能数、ｎ：符号長）とすると、 上述のパリティ検査行列Ｈと受信信号の積から下記のよ
うに、シンドロームが発生され、また、シンドローム多
項式が定義される。

上式で発生された値を係数とする次の多項式をシンドロ
ーム多項式と称する。

５（ｘ）　−３ｏ　＋Ｓ、ｘ＋Ｓ、ｘ″＋　−’　＋Ｓ
、ｔ−，ｘ”−’誤り訂正のために種々の多項式がある
が、それらは次の関係式を満足する。

φ（ｘ）　　・ｘ”　＋ａ（ｘ）　　・５（ｘ）　＝ω
（ｘ）但し、 ｋ〜（ ＱＬ 上式の中で、実際の訂正をする場合に必要となるものは
、誤り位置多項式σ（ｘ）と誤り評価多項式ω（×）の
二つである。

上式が常に成り立つとした場合、Ｘ２ｔは当然分かるが
、受信信号から知ることが出来るのは、Ｓ（×）のみで
ある。このｘｚ′−とＳ（χ）からユークリッド互除法
により、σ（ｘ）、ω（ｘ）を求めることができる。こ
こで、良く知られたユークリッド互除法の例として、「
与えられた正の整数ｍとｎに対し、それの最大公約数ｄ
及び（ａｍ＋ｂｎ＝ｄ）となる整数ａ、ｂを計算せよ」
という問題を解（のにユークリッド互除法が使用される
。整数に限らず、多項式の場合も同様である。即ち、（
ｍ→ｘｚｔ−）（ｎ−＋５（ｘ））と対応させれば良い
。

但し、上記の整数の問題は、互除法を最後まで実行して
最大公約数ｄを求めるわけであるが、誤り訂正を実行す
るために、σ（×）、ω（χ）を求める場合は、最後ま
で互除法を実行して最大公約数を求めるわけではない。

途中で次の条件が成立したら、互除法の実行を止める。

ｔ≧ｄｅｇ　ｔｔ　（ｘ）　＞ｄｅｇ　ω（ｘ）（ｄｅ
ｇは、多項式の次数を意味する。）ユークリッド互除法
を用いて、σ（ｘ）、ω（ｘ）を求める具体例について
４サンプル誤り訂正符号の場合について説明する。受信
信号が第４図Ａに示すように、ｎシンボルの場合、誤り
位置多項式σ（ｘ）のＸとして代入される値は、第４図
Ｂに示すように、受信信号の最後から、その最初に向か
って順に（Ｌ　ｅｘ−’、　ｃｘ−”、　　６６．ａ−
”−”・・・α−（ｎ−１１）となる。即ち、Ｐという
番号は、−〇− 受信信号の最後から数えた番号である。

−例として、第５図Ａにおいて、斜線で示すように、受
信信号の最後を０番目とすると、１番目。

２番目、３番目、４番目の各々の位置で、誤りが発生し
、これらの誤りが第５図Ｂに示すように、（α４．α、
α７．α２）の誤りパターンである場合の訂正を考える
。この場合のシンドロームは、下記のものとなる。

Ｓｏ−α４α＋αα２＋α７α３＋α２α４−α５＋α
３＋α１０＋α６＝α８ ＳＬ＝α４α２＋αα４＋α７α６＋α２α８＝ｏｔ”
　＋ｃｘ’　＋α１３＋ａＩｏ＝Ｏ３，＝α’　ａ”　
＋ｏｔａ’　＋ａ７ａｔ’＋α２α１２−α７＋α７＋
α＋α１４−α７ Ｓ、＝α４α４＋αα８＋α７αＩ２＋α２α１６−α
８＋α９＋α４＋α３−α２ ≦４−α４αＳ＋αα１０＋α７αＩｓ＋α２α２０＝
α９＋α目＋α７＋α７−α２ ＳＳ−α４　α６＋αα″十α７αＩ１１＋α２α２４
−α１０十α１３＋α１０＋α■−α４３６−α４　α
７　＋ααＩ４＋αフ　α２Ｉ＋α２　αｔ８−αｌ　
１　＋　１＋α１３＋ｌミα４Ｓ７−　α４　α８　＋
　α　α鳳り＋　α７　αｔ４＋　α２　α３ｔ＝α１
２＋α２＋α十α４−α９ Ｓ　（ｘ）−α９Ｘ７＋α４Ｘ６＋α４ｘＳ十ｏ：２ｘ
’＋αＺ　Ｘ３＋αフｘＺ＋α８上記のシンドローム多
環式Ｓ　（ｘ）とｘ　ｔ　°４とを用い、σ（ｘ）及び
ω（ｘ）を求める。但し、ユークリッド互除法の手続き
は、 ｄｅｇ　　ω（ｘ）　＜ｄｅｇ　ａ　（ｘ）≦４で終了
する。

Ｂ（ｘ）　＝　（α−’ｘ＋ｃｒ）　５（ｘ）　＋Ｒ１
（ｘ）Ｂ（ｘ）−ｘ” Ｒ１（ｘ）＝ｘ’＋α４　ｘ５＋α１３Ｘ４＋αａ　ｘ
３ａ”　Ｘ”＋αＩ４Ｘα２Ｉ ＋α２　＝　（ｃｙ’　ｘ　十ａ”）　Ｒ１（ｘ）　−
ｔ−Ｒ２（ｘ）Ｒ２（ｘ）　＝ｏｔＩ４ｘ’　＋ａ９ｘ
’　十ｏｔ’　ｘ３＋ｃｘＩ３ｘ”　＋ｃｘ”ｘ＋ｃｔ
’ Ｒ１（ｘ）＝（α−目ｘ＋ｔｘ３）Ｒ２（ｘ）＋Ｒ３（
ｘ）Ｒ３（ｘ）−αＺ　ｘ４＋αｌ０Ｘ３＋αｌ４Ｘｚ
十α１１ｘ＋１ Ｒ２（ｘ）＝　（ｃｒ”ｘ＋ｃｒ−”）Ｒ３（ｘ）＋Ｒ
４（ｘ）Ｒ４（ｘ）−α９χ３＋α４　Ｘ２＋α９Ｘ＋
α目上記の演算をまとめると、 Ｒ１＝Ｂ＋ＱＩＳ Ｒ２＝Ｓ＋Ｑ２Ｒ１＝Ｓ＋Ｑ２　（Ｂ＋ＱＩＳ）−Ｑ２
Ｂ＋　（１＋Ｑ２Ｑ１）ｓ Ｒ３＝Ｒ１＋Ｑ３Ｒ２＝Ｂ＋ＱＩＳ ＋Ｑ３　ＣＱ２Ｂ＋　（１＋Ｑ２Ｑｌ）Ｓ）＝　（１＋
Ｑ３Ｑ２）Ｂ＋（Ｑ１＋Ｑ３＋Ｑ３Ｑ２Ｑ１）ＳＲ４＝
Ｒ２＋Ｑ４Ｒ３＝Ｑ２Ｂ＋　（１＋Ｑ２Ｑ１）Ｓ十Ｑ４
　（１＋Ｑ３Ｑ２）Ｂ ＋Ｑ４　（Ｑ１＋Ｑ３＋Ｑ３Ｑ２Ｑｌ）Ｓ、’、Ｒ４＝
　（Ｑ２＋Ｑ４＋Ｑ４Ｑ３Ｑ２）Ｂ＋　（１＋Ｑ２Ｑ１
＋Ｑ４Ｑ１＋Ｑ４Ｑ３＋Ｑ４Ｑ３Ｑ２Ｑ１）Ｓ この式において、Ｒ４がω（に）と対応し、右辺の第１
項が誤り位置多項式φ（に）と対応し、右辺の第２項が
誤り評価多項式ω（ｘ）と対応している。

ここで、 ＱＬ−ａ−’ｘ＋ｔｘ、　　Ｑ２＝ｃｘ’　ｘ＋ｔｘ”
。

Ｑ３＝α−目＋α３．Ｑ４−αＩ　ｔ　ｘ十α−２従っ
て、 ａ（ｘ）　＝ｏ：１３ｘ’＋α６　ｘ３＋α９　ｘ　ｇ
＋αＸ＋α３ω（ｘ）　＝ｒｘ’　ｘ’　＋ｃｘ’　ｘ
”　＋ｒｘ９ｘ＋ｏｔ”ｄｅｇ　σ（ｘ）　＝４．　ｄ
ｅｇ　（１）（ｘ）　−３σ（ｘ）を微分してなるσ′
（ｘ）は、。

σ′（ｘ）＝α″Ｘ２＋α となる。これらの誤り位置多項式及び誤り評価多項式を
用いて、エラー位置及びエラーパターンを求める。

〔Ｘ−αｑ〕のエラー σ（α−′）−α９＋α３＋α７＋１＋α’＝。

従って、エラー位置が分かる。

σ′（α−１）＝α４＋α＝１ ω（α−Ｉ）−α６＋α２＋αＢ十α■−α４、°、エ
ラーパターンｅ−、−ω（α−１）／σ′（α−１）；
α４ 〔Ｘ−α−２〕のエラー σ（ａ−”）　−ｏｔ”　＋１　＋ｏｒ’　＋ａ１４＋
ａ”　＝０従って、エラー位置であることが分る。

σ′（α−２）＝αχ＋α＝α５ ω（α−２）−α３＋１＋α７＋α■−α６、°、エラ
ーパターンｅ−ｚ−ω（α−２）／σ′（α−９＝　α 〔Ｘ−α−３〕のエラー σ（α″３）−α十α−３＋α３＋α−２＋α３＝０従
って、エラー位置であることが分る。

σ′（α−３）−１＋α＝α４ ω（α−３）＝１＋α弓＋α６＋α■−α目、°、エラ
ーパターンｅ−３−ω（α−３／σ′（α−３）＝α７ 〔χ−α−４〕のエラー σ（α−４）＝α−３＋α−６＋α十α−３＋α３−０
従って、エラー位置であることが分る。

σ′（α−４）＝α−２＋α＝α１ ω（α−４）−α−３＋α−４＋α５＋α■−α目、°
、エラーパターンｅ−４＝ω（α−４）／σ′（α−４
）＝α２ 上述のように、σ（ｘ）及びω（χ）により求められた
エラー位置、エラーパターンが最初に設定しておいたも
のと同一であることが分かる。

以上説明したようなユークリッド互除法を用いたリード
・ソロモン符号の復号装置をハードウェア化する場合、
問題となるのは、破除多項式の最高次係数にあわせるよ
うに、α−９などという逆数を計算することである。即
ち、二つの多型式Ｂ（ｘ）とＳ　（ｘ）の最高次数の係
数をす、Ｓとすると、まず、（ｂｘｓ−’）を計算する
必要がある。このためには、Ｓの逆数を求めるＲＯＭ或
いはＲＯＭに相当する回路が必要となり、ハードウェア
量がかなり増大する要因となる。

そこで、例えばｒ　ＩＥＥＥ　ＴＲＡＮＳＡＣＴＩＯＮ
Ｓ　ＯＮ　ＧＯＭＰ−ＵＴＥＲ３，ＶＯＬ、ｃ−３４，
ＮＯ，５，ＭＡＹ　　１９８５　　　：　　頁３９３〜
４０３］には、逆数演算を使用しないユークリッド互除
法が提案されている。この方法について、前出の４誤り
訂正の例と同様の例を用いて説明する。

Ｂ（ｘ）＝ｘ８ Ｓ　（ｘ）−α９　Ｘ？＋α４　ｘｊ＋十α４ｘＳ＋α
８Ｘ４αＺ　ｘ３＋α？　ｘＺ＋α８ −１２＝ 計算は、互いの最高次係数を乗算しあいながら、順次次
数を減らす方式である。

■ ｒ　１　（ｘ） ０　α４α４α２α２α７０　αｌＩＯｄｅｇ　ｒ　１
（ｘ）　＝７ ｒ　１（ｘ）＝ａ’　ｘ７＋α４　Ｘ６＋αｚ　Ｘｓα
２Ｘ４＋α７　Ｘ３＋α８Ｘ ｒ　１　（ｘ）の最高次係数が７であるので、更に５（
ｘ）で割ることができる。

Ｒ１（ｘ） Ｏｃｔ”　α７ａ：　　ｔｘ”ｒｘ”α”　ａ”ｄｅｇ
　Ｒ１（ｘ）　−６ Ｒ１（ｘ）　＝ｃｒ”　ｘｈ＋ｒｘ７ｘ’　＋ｃｒｘ’
α”ｘ”　　＋ａ”ｘ”　　＋α２　Ｘ＋α１ｚｄｅｇ
　Ｒ１（ｘ）　＜ｄｅｇ　Ｓ　（ｘ）であるので、更に
５（ｘ）をＲ１（ｘ）で割る。

■と■をまとめると、 ｒｘ’　Ｂ＝ｘＳ＋ｒ　１ ｃｔ’　　ｒ　１−α’　Ｓ＋Ｒ１ 上式からｒｌを消去すると、 （α’　）　”　Ｂ＝　（ｃｒ９ｘ＋ｃｘ’　）　Ｓ＋
Ｒ１となる。そこで、σ（ｘ）とω（ｘ）の候補が形成
されていく過去をみると、 ｃｒ’　Ｂ＋ｘＳ＝ｒ　１ （α９）”　Ｂ＋　（ｃｒ’　ｘ＋ｏｔ’　）Ｓ＝Ｒよ
この下線を付した項がσ（ｘ）及びω（ｘ）になる部分
である。従って、■のステップ迄では（α９Ｘ＋α４）
の次数がまだ１次であり、Ｒ１の次数がまだ６次である
。本当は、各々が４次及び３次になるまで演算を行う必
要がある。従って、以下、この手順を進める。

■ α３Ｓ（ｘ） ＋α’ｘＲ１（ｘ） ｒ　２　（ｘ） ０　　α１４α６０　０　　αＩ４α６　α目ｄｅｇｒ
２（χ）−６ ｒ２（ｘ）　　−ｒｘ１４ｘ６　＋ｒｘｂ　ｘ’　　＋
ａＩ４ｘ”＋α６ｘ＋α′１ ｒ　２　（ｘ）の最高次係数が６であるので、更にｒ２
は、Ｒ１で割ることができる。

■ Ｒ２（ｘ） ０　α５１　α１０α４α３αｌＯ ｄｅｇＲ２（に）−５ Ｒ２（ｘ）＝αＳ　ｘ’　＋ｘ’　＋ｃｘ１０ｘ３α４
　ｘ２＋α３Ｘ十α１０ （ｄｅｇ　Ｒ２＜ｄｅｇ　Ｒ１）となったので、次にＲ
１をＲ２で割ってゆく。

曲 ｒ３（χ） ０　αｔｏ１　　αＩ４α■α５α２ ｄｅｇ　ｒ　３　（ｘ）　−５ ｒ３（ｘ）　−ａＩＯｘＳ十ｘ’　十αＩ４ｘ”α”ｘ
２＋αＳｘ　　＋α” 面 Ｒ３（ｘ） Ｏｌ　α８α７α９αＩ３ ｄｅｇＲ３（χ）−４ Ｒ３（ｘ）　＝ｘ’　＋ａ”　ｘ”　＋ｔｘ７ｘ”　ｃ
ｘ９ｘ＋ａ１３■ １ｌ− ｒ４（χ） ０　　　α６　　α３　　α９　０　　　α鳳０ｄｅｇ
　　ｒ　４　（ｘ）　　−４ ｒ４（ｘ）＝ｏｔ６ｘ’　十ａ３ｘ３＋ｃｔ’　ｘ”　
＋ｃｘ”■ Ｒ４（ｘ） ０　１　　α１０１　　α２ ｄｅｇ　　Ｒ４（ｘ）　　＝３ Ｒ４（ｘ）　　＝ｘ’　　＋ｔｘ’°ｘ”　　＋Ｘ＋α
”ここで、ω（ｘ）の候補であるＲ　４　（ｘ）が３次
式となったので、以上の手続きを中止する。そして、改
めて、演算の結果をまとめると以下の通りとなる。

α９Ｂ＝ｌ　ｘＳ＋ｒ　ｌ−＋α’　Ｂ＋ｘＳ＝ｒ　１
ｃｘ’　ｒ　ｌ＝α’　Ｓ＋Ｒ１→ ＝１７− ｃｒ３　Ｂ＋　　（α９　ｘ＋ｒｘ’　　）Ｓ＝Ｒ１α
３５−ｃｒ’　　ｘＲ１＋ｒ２−＋ ｒｘ”ｘＢ＋　（α”　ｘ”　＋ａ”ｘ＋ｃｘ３）Ｓ＝
ｒ２ａ″　ｒ２＝ｏｔ”Ｒ１＋Ｒ２− （ｘ＋＆”　）Ｂ＋（α６ｘ”　＋ｒｘ′。ｘ＋ｒｘ”
　）Ｓ＝Ｒ２ｒｘ５ＲＩ−α’　ｘＲ２＋ｒ３−＋ （αＳｘ”＋αｓｘ＋ｔｘ８）Ｂ＋（α９ｘ”　十ａ”
ｘ”　十ｏｔ′ｚｘ＋ａ’　）　Ｓ＝ｒ　３α５　ｒ　
３　＝ｔｘ”Ｒ２＋Ｒ３→ （α”　　ｘ”　　＋α）Ｂ＋　（ｃｒ”ｘ”　　＋ｏ
ｔ’　　ｘ”　　＋αχ十α’　）Ｓ＝Ｒ３ １・　Ｒ２−ｔｘＳ　ｘＲ３＋ｒ４→ （α１３ｘ３　＋α＋　３　ｘ＋α”）Ｂ＋（α４　Ｉ
４　＋ｔｘＩ４ｘ”　　＋ｏｔ”　　）Ｓ＝ｒ４１　−
　　ｒ４＝α６　Ｒ３＋Ｒ４−）（αｌ３ｘ３　＋ｃｘ
１４ｘ”　　＋α”ｘ＋α”）Ｂ＋　　（α’ｘ’　＋
ｃｔＩｚｘ３＋ｘ”　＋ｃｔ’　ｘ＋ｏｔ’　）　５＝
Ｒ４このＲ４が求まった段階ではじめて ｄｅｇ　Ｒ４＜ｄｅｇ　　（α’　ｘ’　＋ａ”ｘ”　
十ｘ２＋α７χ＋α９）≦ｔ　（−４） −１８＝ の関係が成り立ったので、この手続きを中止する。

従って、 σ（ｘ）＝α４　Ｘ４＋α”ｘ”　十ｘ”＋α７Ｘ十α
９（１）（ｘ）＝Ｒ４（ｘ）＝Ｘ３＋ａ１０ｘ”　＋ｘ
＋ｃｘ”となる。これらの式をα９倍すると、前述のα
−９を使用して求めたσ（ｘ）及びω（ｘ）と同一とな
る。

即ち、誤り位置を求めることは当然として、誤りパター
ンを求める式も、分子及び分母の両者をα９倍しても、
誤りパターン自体は、何ら変化せず、正しい答えが得ら
れる。結局、互いの最高次数係数を乗算しながら、１次
づつ除算しても良い。

前述の■〜■の順序でなされる処理を回路化する場合に
考えられる構成は、第１４図に示すものである。

第１４図において、２Ａ〜２Ｈは、演算部を示し、これ
らの８個の演算部２Ａ〜２Ｈは、縦続接続されている。

各演算部は、基本的には、積和演算回路の構成を有して
おり、互いに同一の構成である。即ち、第１の入力信号
が供給される乗算回路１３と乗算回路１３に接続された
レジスタ１４と第２の入力信号が供給される乗算回路１
７と乗算回路１７と接続されたレジスタ１６と第２の入
力信号を１クロツク遅延して出力するレジスタ１８と乗
算回路１３の出力信号と乗算回路１７の出力信号とを加
算する加算回路１５とにより、第１の入力信号及び第２
の入力信号に対する積和回路が構成され、第３の入力信
号が供給される乗算回路２３と乗算回路２３に接続され
たレジスタ２４と第４の入力信号が供給される乗算回路
２７と乗算回路２７と接続されたレジスタ２６と第４の
入力信号を１クロツク遅延して出力するレジスタ２８と
乗算回路２３の出力信号と乗算回路２７の出力信号とを
加算する加算回路２５とにより、第３の人力信号及び第
４の入力信号に対する積和回路が構成される。

この第１４図における回路において、■クロックデータ
を進めることは、その多項式にＸを乗算することであり
、また、１クロツクデータを遅らせることは、その多項
式にｘ　−１を乗算して次数を１次下げることである。

第１４図Ａは、上述の■のステップの処理を行う２０一 時の演算部の入力及び出力を示す。第１４図Ｂは、上述
の■のステップの処理を行う時の演算部の入力及び出力
を示す。第１４図Ｃは１．上述の■のステップの処理を
行う時の演算部の入力及び出力を示す。

第１４図りは、上述の■のステップの処理を行う時の演
算部の人力及び出力を示す。第１４図Ｅは、上述の■の
ステップの処理を行う時の演算部の人力及び出力を示す
。第１４図Ｆは、上述の■のステップの処理を行う時の
演算部の入力及び出力を示す。第１４図Ｇは、上述の■
のステップの処理を行う時の演算部の入力及び出力を示
す。第１４図Ｈは、上述の■のステップの処理を行う時
の演算部の入力及び出力を示す。

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

以上のように、誤り位置多項式σ（ｘ）及び誤り評価多
項式ω（ｘ）を求める構成が考えられる。しかし、第１
４図の構成は、演算部のみの構成であって、第１の入力
信号と第２の入力信号の入れ替え（除多項式と破除多項
式との交換）の制御並びに次数差の関係が（ｄｅｇω（
ｘ）　＜　ｄｅｇσ（に））になることの検出について
は、明らかにされてない。

従って、この発明の目的は、演算部を縦続接続して、実
時間処理により、誤り位置多項式σ（ｘ）及び誤り評価
多項式ω（ｘ）を求めることを実現するための制御方法
が改良されたリード・ソロモン符号の復号方法を提案す
るものである。

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

−この発明では、ユークリッド互除法により、縛り多項
式σ（ｘ）と誤り評価多項式ω（ｘ）を導出するように
したリード・ソロモン符号の復号方法において、 シンドローム多項式Ｓ　（ｘ）を求め、シンドローム多
項式Ｓ　（ｘ）と訂正しようとするシンボル数ｔで定ま
る初期多項式χｇ＋−との互いの最高次数を乗算しあい
ながら一つづつ順に次数を減らすことでｆ（ｘ）　・Ｂ
　（ｘ）　　十ｇ（ｘ）　・Ｓ　（ｘ）　　＝ｈ（ｘ）
（但し、ｈ　（ｘ）の次数＜　ｇ　（ｘ）の次数≦ｔ）
の関係を満足する多項式ｈ　（ｘ）及びｇ　（ｘ）を求
め、多項式ｇ　（ｘ）を誤り位置多項式σ（ｘ）とし、
多項式ｈ（×）を誤り評価多項式ω（×）とする。

〔作用〕

誤り位置多項式σ＜ｘ）及び誤り評価多項式ω（ｘ）を
自動的に求める処理は、 ｆ　（ｘ）　　・Ｂ（ｘ）　＋ｇ（ｘ）　　・５（ｘ）
　−ｈ（ｘ）ｄｅｇ　ｈ　（ｘ）　＜ｄｅｇ　ｇ　（ｘ
）≦ｔを満足する多項式ｇ（χ）及びｈ　（ｘ）を求め
ることに他ならない。別の表現では、多項式Ｂ、Ａを用
いて、 ｆｉ　（ｘ）Ｂ＋ｇ＋　（ｘ）Ａ＝ｈｉ（ｘ）（ｉは、
演算手順の番号） という関係を満足する多項式ｆｔ（χ）　、　　ｇ＝　
（ｘ）を常に出力する回路である。

そして、 ｄｅｇｇ＋　≦ｄｅｇｇ２≦ｄｅｇｇ３≦ｄｅｇｇ４　
・・・ｄｅｇｈ、≦ｄｅｇｈ、≦ｄｅｇｈ３≦ｄｅｇｈ
、・・・となるので、何回かの手続きの後に、 ｄｅｇ　ｈｌ　＜ｄｅｇ　ｇ　ｉ≦ｔ という関係式を満足する時点がくることになる。

〔実施例〕

以下、この発明の一実施例について図面を参照して説明
する。この説明は、下記の順序に従ってなされる。

ａ、基本的構成（制御部及び演算部） ｂ、　　４誤り訂正符号の例 ｃ、５誤り訂正符号の一例 ｄ、５誤り訂正符号の他の例 ｅ、互除演算の具体的回路 ａ、基本的構成（制御部及び演算部） 第１図は、この発明の一実施例の基本的構成を示す。を
誤り訂正符号の場合には、この第１図に示す基本的構成
が所定個数、縦続接続される。

第１図に示すように、４本のデータ伝送ラインと２本の
フラグ伝送ラインとが設けられる。第１のデータライン
には、Ｐ系列のデータが供給され、第２のデータライン
には、Ｑ系列のデータが供給−４Ａ　− され、第３のデータラインには、Ｒ系列のデータが供給
され、第４のデータラインには、Ｓ系列のデータが供給
される。ＣＲ及びＩＸが制御用のフラグであり、フラグ
伝送ラインに各々供給される。

基本的構成は、データ制御部１と演算部２とからなる。

データ制御部ｌには、クロス制御回路３が設けられ、第
１のデータラインと第２のデータラインとをクロスさせ
るかどうかの制御並びに第３のデータラインと第４のデ
ータラインとをクロスさせるかどをかの制御がクロス制
御回路３によりなされる。フラグ伝送ラインと第２のデ
ータ伝送ラインと第４のデータ伝送ラインとの入力端に
は、レジスタ４，５，６．７が各々接続されている。フ
ラグの処理を行うために、ＯＲゲート８及びＡＮＤゲー
ト９とをデータ制御部１が有している。

演算部２には、フラグＩＸの処理のための加算回路１１
とレジスタ１２とデータに対する積和演算回路とが設け
られている。Ｐ系列及びＱ系列に対する積和演算回路は
、乗算回路１３とレジ４タ１４と加算回路１５とレジス
タ１６と乗算回路１７とにより構成されている。同様に
、Ｒ系列及びＳ系列に対する積和演算回路は、乗算回路
２３とレジスタ２４と加算回路２５とレジスタ２６と乗
算回路２７七により構成されている。

Ｐ系列及びＱ系列に対する積和演算回路のみを抜き出す
と第２図に示す構成となる。Ｐ系列として、多項式Ｆ（
ｘ）（最高次係数：ｆ）が供給され、Ｑ系列として多項
式ｘ”Ｇ（ｘ）（最高次係数二ｇ）が供給され、Ｐ系列
の出力として、Ｒ（ｘ）　＝ｇ−Ｆ（ｘ）　＋ｆ−ｘ”
　　・Ｇ（ｘ）が得られる。演算部が正規演算をするた
めの条件は、レジスタ１４及び１６に各々これらの最高
次係数ｆ及びｇが同時にロードできることである。

このことは、（ｄｅｇ　Ｆ（ｘ）　−ｄｅｇ　ｘ’　Ｇ
（ｘ）　）ということと等価である。また、（ｇ≠０）
である。

第２図に示すように、（ｄｅｇ　Ｆ　（ｘ）　＞ｄｅｇ
　Ｇ（ｘ）　）で、ｎ次の次数差がある二つの多項式を
、各々破除多項式及び除多項式とする場合、出力の多項
式Ｒ（ｘ）は、多項式Ｆ（×）より少なくとも次２６一 数が１次減少している。従って、Ｆ　（ｘ）をＧ　（ｘ
）で割れるところまで割るには、（ｎ＋１）個の演算部
を使えば良い。そして、次の新たな互除演算を続けるに
は、最終段出力Ｐ４のＲ（ｘ）とＱ４の出力Ｇ　（ｘ）
の各々が次段のＱ系列及びＰ系列に人力されるように、
クロスさせれば良い。

データ制御部ｌの役目は、次の二つである。

第１には、二つの系列の多項式を何時クロスさせ、除多
項式と破除多項式を交換させるかの制御を行う。

第２には、（ｄｉｇ　ａ＋　（ｘ）　＜ｄｅｇ　ｔｔ　
（ｘ）　）の演算停止条件が成立したことを検出する。

この発明では、第１の制御を行う場合、多項式の係数を
全て格納できるようなバッファメモリを持たずに、実時
間処理を行う。この実時間処理を可能とするために、フ
ラグＩＸ及びＣＲが用いられる。

フラグＩＸは、実際に除算演算を始める前の二つの多項
式の次数差を示す。ガロア体ＧＦ　（２”）では、一般
に８ビツト必要である。

フラグＣＲは、条件が整えば、何時でも、Ｐ系列とＱ系
列並びにＲ系列とＳ系列とをクロスしなさいということ
を示すフラグである。フラグＣＲがハイレベルの時がク
ロスしなさいを意味し、フラグＣＲがローレベルの時が
クロスしなくても良いを意味する。

フラグＣＲに関して、「条件が整えば」という事は、Ｐ
系列とＱ系列の入力多項式の最高次数係数がレジスタ１
４及び１６に同時にロードできるとういう条件である。

また、（Ｉ　Ｘ＝−１）となることは、除多項式（Ｑ４
の出力）の次数が互除演算の結果である余り多項式（Ｐ
４出力）の次数よりも、１次大きいことを意味する。こ
の場合には、Ｐ系列とＱ系列とを交換して、新しい除多
項式で互除演算を続けなければならない事を示している
。ここで、直ぐにＰ系列とＱ系列とを交換して、演算に
入るべきかどうかの判定をすることにより、次段に伝達
するＣＲ４を（Ｌ−＋Ｈ）にすべきか、又はＬのままで
良いかが違ってくる。このように、フラグＣＲ−２’／
　　− とＩＸとは、常に、ペアとして考えるべき信号である。

フラグＩＸ及びＣＲの制御方法は、複雑であるので、第
３図のフローチャートに示す。

第３図の各ステップは、以下のものである。

ステップ■・・・初期条件の設定である。即ち、（ＣＲ
＝Ｈ：ハイレベル）（ＩＸ＝１）とフラグが設定される
。データは、Ｐ系列として、Ｓ（×）が供給され、Ｑ系
列として、ｘ　ｇ　Ｌが供給され、Ｒ系列として、■が
供給され、Ｓ系列として、０が供給される。

ステップ■・・Ｑ系列及びＳ系列の各々に１段の遅延を
入れる。

ステップ■・・・　（ＣＲ＝Ｈ？）の判断。

ステップ■・・・　（ＩＸ−−１？）の判断。即ち、破
除多項式の次数より、除多項式の次数が大きいかどうか
の判断。

ステップ■■・・・最高次数が同時に入力されたかどう
かの判断。

ステップ■■・・・系列をクロスさせる処理。

ステップ■■■・・互除演算の処理。互除演算が＝２９
− ＝　２８− されると、フラグＩＸが（＋１）又は（−１）される。

ステップ［相］・・・互除演算がされず、フラグＩＸが
（＋３）され、フラグＣＲがＨとされる。

ステップ＠・・・互除演算がされず、フラグＩＸが（＋
１）される。

ステップＱ　・・・（ｄｅｇ　ａ＋（ｘ）　＜ｄｅｇ　
ａ　（ｘ）　）の条件が成立したかどうかの判断。この
条件が成立すると、演算が停止される。

ｂ、４誤り訂正符号の例 この発明を４誤りの訂正に通用した例について説明する
。第４図Ａに示すように、ｎ個のシンボルからなる受信
系列の場合、誤り位置多項式σ（ｘ）或いは誤り評価多
項式ω（ｘ）のＸとして代入する値は、第４図Ｂに示す
ように、受信系列の最後から順に、（１，α−１，α−
”、　　ＨＨＨα−（ｐ−富）・・・α−（−１１）と
される。

第５図Ａにおいて、斜線で示す４個の誤りが生じており
、第５図Ｂに示す誤りパターンの場合を考吠る。シンド
ロームの発生が完了し、シンドローム多項式Ｓ（×）が
求められ、このシンドローム多項式Ｓ　（ｘ）が入力さ
れることから、処理が始められる。

まず、ステップ■の初期設定がなされる。次に、ステッ
プ■の段階で、Ｑ系列即ち、Ｂ　（ｘ）のデータ系列に
１クロツクの遅延が入れられるので、Ｐ系列及びＱ系列
の最高次係数１とα９とが同位相となる。

ステップ■では、（ＣＲ＝Ｈ）であるから、ステップ■
へ移行し、更に、同時人力するから、ステップ■へ移行
する。ステップ■により、クロスさせられる処理がなさ
れ、第８図Ａに示す演算部２ＡのＰ系列及びＱ系列とし
て、Ｂ　（ｘ）及びＳ（×）が各々人力される。また、
ステップ■で、データ系列がクロスされたので、（ＣＲ
１＝Ｈ）から（ＣＲ４＝Ｌ）に変える。また、演算部２
Ａでは、互除演算が実際に実行され、出力系列Ｐ４とし
ては、人力多項式Ｐ３（８次）より、次数が１減少した
多項式が出力される。従って、Ｐ系列とＱ系列との相対
的次数差を示すフラグＩＸを１減少させたものが新たな
ＩＸ　（ＩＸ４）とする操作がされる。

上述のように、第８図Ａの処理では、第３図に示すフロ
ーチャートに従って、（■→■→■→■→■→■→０）
のステップの処理がされる。この処理は、演算停止の条
件が満足される迄、繰り返される。

第８図Ｂは、２段目の処理を示している。この２段目で
は、（■→■→■→■→０）の処理がされる。

第８図Ｃは、３段目の処理を示している。この３段目で
は、（■→■→■→■→■→■→０）の処理がされる。

第８図りは、４段目の処理を示している。この４段目で
は、（■→■→■→■→０）の処理がされる。

第８図Ｅは、５段目の処理を示している。この５段目で
は、（■→■→■→■→■→■→０）の処理がされる。

第８図Ｆは、６段目の処理を示している。この６段目で
は、（■→■→■→■→＠ｌ）の処理がされる。

第８図Ｇは、７段目の処理を示している。この７段目で
は、（■→■→■→■→■→■→０）の処理がされる。

第８図Ｈは、８段目の処理を示している。この８段目で
は、（■→■→■→■→０）の処理がされる。この段階
で、ステップ［相］の条件が成立するので、演算の停止
のステップ■に移行し、処理が終了する。

ｃ、　　５誤り訂正符号の一例 第６図Ａにおいて斜線で示すように、５個のシンボルの
誤りが存在し、シンドローム多項式の上位の３個の係数
がＯとなる場合について説明する。

上位の３個の係数がＯとなるのは、第６図Ｂに示すよう
に、α７．α。α２，１．α２の誤りパターンの場合で
ある。シンドローム多項式Ｓ　（ｘ）の係数は、下記の
ものとなる。

Ｓｏ　＝α”　、　　Ｓ、　＝ｃｘ”　、　　Ｓ、　＝
ｃｘ”。

Ｓ３−α１３．　３４−α、Ｓ５＝α＋ｚ、　　３．　
＝　１３７　　、　　Ｓｓ　　、　　Ｓ９　−０上述の
例に対して、この発明を適用した時の制御部１及び演算
部２の動作は、第９図に示すものとなる。第８図と同様
に、第９図Ａから順に第９図８１第９図Ｃ１・・・と処
理が進められる。

第９図Ａの処理では、第３図に示すフローチャートに従
って、（■→■→■→■→＠→０）のステップの処理が
される。

第９図Ｂは、２段目の処理を示している。この２段目で
は、（■→■→■→＠→０）の処理がされる。

第９図Ｃは、３段目の処理を示している。この３段目で
は、（■→■→■→＠→＠））の処理がされる。

第９図りは、４段目の処理を示している。この４段目で
は、（■→■→■→■→■→０）の処理がされる。

第９図Ｅは、５段目の処理を示している。この５段目で
は、（■→■→■→■→０）の処理がされる。

第９図Ｆは、６段目の処理を示している。この６段目で
は、（■→■→■→■→０）の処理がされる。

第９図Ｇは、７段目の処理を示している。この７段目で
は、（■→■→■→■→０）の処理がされる。

第９図Ｈは、８段目の処理を示している。この８段目で
は、（■→■→■→■→０）の処理がされる。

第９図■は、９段目の処理を示している。この８段目で
は、（■→■→■→■→■→■→０）の処理がされる。

第９図Ｊは、１０段目の処理を示している。この１０段
目では、（■→■→■→■→［相］）の処理がされる。

この段階で、ステップ［相］の条件が成立するので、演
算の停止のステップ■に移行し、処理が終了する。

上述の上位の３係数が全て０となる例は、前述の３誤り
訂正符号の例とは異なっている。即ち、上位の３係数が
全てＯであるため、（Ｂ（ｘ）＝ｘ−ｑ　　！１１− １０）の系列を１クロツク遅延させただけでは、Ｐ系列
及びＱ系列の最高次係数を同一タイミングで、レジスタ
にロードできない。シンドローム多項式Ｓ　（ｘ）が６
次であるため、Ｂ（×）を４段遅延する必要がある。こ
の遅延処理を行っているのが、データ制御部ＩＡ、ＩＢ
、ＩＣ，ＩＤである。この時の処理は、第３図のフロー
チャートにおけるステップ■、■、■の処理であり、こ
の遅延処理を３回繰り返し、４回目でデータをクロスさ
せて互除演算がなされる。このクロスがされる迄、フラ
グＣＲは、Ｈである。また、二つの多項式の相対次数差
が４まで増加する。また、演算がされない（Ｎｏ　　Ｏ
Ｐ［！ＲＡＴＩＯＮ　）とは、レジスタ１４，１６゜２
４．２６には、１．０が各々ロードされる。更に、４段
目のデータ制御部ＩＤで実際の演算が開始されてから、
（ＩＸ＝−１）となる８段目までは、データラインがク
ロスされない。

ｄ、５誤り訂正符号の他の例 第７図Ａにおいて斜線で示すように、３個のシンボルの
誤りが存在し、シンドローム多項式の上位の第２番目及
び第３番目の２個の係数がＯとなる場合について説明す
る。上位の２個の係数がＯとなるのは、第７図Ｂに示す
ように、α５，１゜α３の誤りパターンの場合である。

シンドローム多項式Ｓ　（ｘ）の係数は、下記のものと
なる。

Ｓｏ−α、Ｓ１−α１４．　　Ｓ２−α２．Ｓ３−α７
Ｓ４−α１３．　　Ｓ、−α７．Ｓ６−α′４Ｓ７．Ｓ
ｓ　＝Ｏ，Ｓｑ−α２ 上述の例に対して、この発明を適用した時の制御部１及
び演算部２の動作は、第１０図に示すものとなる。第８
図及び第９図と同様に、第１０図Ａから順に第１０図Ｂ
、第１０図０１　・・・と処理が進められる。

第１０図Ａの処理では、第３図に示すフローチャートに
従って、（■→■→■→■→■→■→０）のステップの
処理がされる。

第１Ｏ図Ｂは、２段目の処理を示している。この２段目
では、（■→■→■→■→０）の処理がされる。

第１Ｏ図Ｃは、３段目の処理を示している。この３段目
では、（■→■→■→■→［相］→０）の処理がされる
。

第１Ｏ図りは、４段目の処理を示している。この４段目
では、（■→■→■→■→■→０）の処理がされる。

第１０図Ｅは、５段目の処理を示している。この５段目
では、（■→■→■→■→０）の処理がされる。

第１０図Ｆは、６段目の処理を示している。この６段目
では、（■→■→■→■→０）の処理がされる。この段
階で、ステップ０の条件が成立するので、演算の停止の
ステップ［相］に移行し、処理が終了する。

上述の例で、注意する点は、第１０図Ｃの３段目のデー
タ制御部ＩＣの動作である。（Ｉ　Ｘ＝−１）であるか
ら、データ制御部ＩＣのクロス制御は、ＯＲゲート８へ
の信号をＨとする。これは、（ＣＲ１＝Ｌ）であっても
、この段以降、どこかでデータラインをクロスさせる必
要があることを意味する。そこで、データ制御部ＩＣの
中でクロス可能かどうかを検出する。このために、Ｑ系
列に１クロツクの遅延を入れた多項式系列とＰ系列の多
項式系列とを比較して、最高次係数が同時にレジスタに
ロードされるかどうかを判断する。この例では、Ｑ系列
の最高次次数がα２の時、Ｐ系列は、まだＯである。従
って、このデータ制御部ＩＣでは、クロスできないこと
になるから、ＡＮＤゲート９に対する信号をＨとして、
フラグ（ＣＲ４＝Ｈ）として、次段以降でクロスさせる
ように、フラグを伝達している。また、この時には、演
算処理をしないように、レジスタ１４．２４の内容が１
とされ、レジスタ１６．２６の内容が０とされる。

更に、この３段目の演算部２Ｃでは、フラグＩＸに（＋
３）の処理がなされている。（ＩＸ＝−１）の時にクロ
スを行った時には、通常ＩＸに（＋１）の処理を行えば
良い。また、同時に、最高次係数がロード出来なくて、
演算部を非動作とする時にも、ｔＸに１を加えた。上述
の例の３段目の演算部２Ｃでは、上記の二つのことが同
時に起きているので、ＩＸに対して２を加えれば良いと
考えられるが、実際には、３を加える必要がある。

ｅ、互除演算の具体的回路 第１図に示す基本的構成は１．第１１図に示す回路によ
り具体化できる。第１１図において、ＦＱ○の符号は、
Ｄ型フリップフロップを示し、ＪＱＯは、ＪＫ型ラフリ
ップフロップ示し、Ｔ１〜Ｔ４がクロックイネーブルＤ
型フリップフロップを示す。第１図の基本的構成との対
応関係は、ＯＲゲート８がＯＲ７と対応し、ＡＮＤゲー
ト９がＡＮＤ７と対応する。また、乗算回路１３．１７
がＭＵＬｌ、ＭＵＬ２と対応し、加算回路１５がＡＤＤ
ｌと対応し、レジスタ１４及び１６がＴ１及びＴ２と対
応する。同様に、乗算回路２３．２７がＭＵＬ３．ＭＵ
Ｌ４と対応し、加算回路２５がＡＤＤ２と対応し、レジ
スタ２４及び２６がＴ３及びＴ４と対応する。更に、フ
ラグＣＲは、第１１図においては、ＣＲＯ５Ｓと表され
ている。

第１１図の回路構成の特徴的な点は、フラグＩＸの取り
扱いである。上述の説明では、フラグＩＸは、独立に段
間で受は渡ししていた。しかしながら、フラグＩＸは、
通常でも、５ビット程度を必要とし、符号の最大能力を
持たせる時には、８ビツト必要となる。このため、各段
の構成をＩＣ化した時に、入力及び出力で１６本のビン
が必要となる。このことは、ＩＣ化にとって、コストの
上昇をもたらし、不利である。また、フラグＩＸの加減
算のために、通常の加算回路１１を設けているが、この
加算回路１１を省略できることが好ましい。

上述の理由で、第１１図の構成においては、フラグＩＸ
がＰ系列の先頭に付加されて、入力及び出力のピン数の
削減が図られている。また、ＩＸの加減算が乗算回路Ｍ
ＵＬ　１で行われる構成とし、フラグＩＸ用の加算回路
が省略されている。即ち、ＩＸの加算をαＩＸと考えて
、ＩＸの加減算が指数の加減算に置き換えられている。

この場合、（ＩＸ＝−１）の検出を行うために、８ビツ
トの比較回路ＣＯＭＰが設けられ、α−１が検出された
ら比較回路ＣＯＭＰがＨを出力する。この比較回路ＣＯ
ＭＰの出力信号がクロックイネーブル付のフリップフロ
ップＦ１０２によりラッチされる。これから入力を始め
ているデータ系列の属性を示す信号ＩＮＶが形成され、
この信号ＩＮＶがＯＲ７に入力される。

このＯＲ７には、前段からのＣＲＯ３Ｓ信号がＦ２１゜
Ｆ２２を介して供給される。

第１１図におけるＭＤ倍信号、二つの役目を有している
。その一つは、多項式系列の入力開始を知らせることで
あり、第二には、［（Ｐ、　Ｑ、　Ｒ。

Ｓの最大次数幅）＋（ＩＸ用の１クロツク）〕のパルス
幅を有している。従って、ＭＤ倍信号、基本回路のデー
タ設定、モードリセットが行われる。

次に、Ｊ７２．Ｊ８２．Ｊ９２は、ＪＫフリップフロッ
プであって、Ｐ、　Ｑ、　Ｒ系列に入力してくる多項式
の次数だけＨとなる信号を作っているもので、最高次数
係数の後、途中の係数が“０”になっても、出力がＬと
ならないように、ＪＫフリップフロップが使用されてい
る。この出力を用い、Ｊ７２の否定信号と、Ｊ８２を１
段遅延させたＦ１ａの出力信号とを比較することにより
、Ｐ。

Ｑ系列の最高次係数がレジスタＴ１及びＴ２に同時に人
力させることが可能かどうかが判断されている。これが
ＡＤ７の信号で、一旦Ｊ７４でラッチしている。これが
Ｈだと、クロス禁止（ＣＲＯ３ＳＩＮ旧旧Ｔ）という意
味でＣＲＩＮ＋（と記することにする。これは、第３図
のフローチャートでは、ステップ■及び■の判断ステッ
プに相当しており、（ＣＲＩＮＩＩ　＝　Ｈ）がステッ
プ■及び■では、ＮＯに相当し、（ＣＲＩＮＨ＝Ｌ）が
ステップ■及び■では、ＹＥＳに相当する。

Ｊ７２の否定出力とＪ９２の出力信号とを比較すること
により、フローチャート中のステップ０である演算の停
止の条件を検出している。Ｊ９３の出力信号がＨとなれ
ば、全ての演算が停止され、Ｐ、Ｒ系列も、Ｑ、　　Ｓ
系列に遅延の段数があわせられるようになっている。こ
の制御を行っているのがＭＵＸＩ−ＭＵＸ４．ＭＵＸ８
．ＭＵＸ９である。また、互除演算で、最大次数が１減
少したときのみ、ＭＵＸ７は、Ｏ入力を選択し、ＭＤの
パルス幅が１クロック分小さくなるようにされている。

これらのデータセレクタがどのような選択動作を行うか
を第１２図に示す。この第１２図には、フローチャート
のどのステップに対応するかも示されている。

第１３図は、第１１図の具体回路の動作を示すタイミン
グチャートである。この第１３図の例は、４誤り訂正の
例の場合である。第１３図Ａが一段目の回路の動作を示
し、以下、第１３図Ｂ〜第１３図１まで２段目〜９段目
の各段の動作が示されている。

〔発明の効果〕

この発明によれば、基本回路を縦続接続するだけで、何
重誤りでも、訂正できるリード・ソロモン符号の復号回
路が構成できる。特に、この発明は、バッファメモリを
持たず、実時間で演算が連続的に実行され、ディジタル
ビデオデータのような高速のデータ番二対して有効であ
る。

【図面の簡単な説明】

第１図はこの発明の一実施例の基本的構成のブロック図
、第２図は第１図から取り出された演算部のブロック図
、第３図は制御部の動作説明のためのフローチャート、
第４図、第５図、第６図。 及び第７図は誤りの例を各々示す路線図、第８図。 第９図及び第１０図は基本的回路の動作を説明するため
のブロック図、第１１図はこの発明の一実施例の具体回
路、第１２図は具体回路の動作説明のための路線図、第
１３図は具体回路の動作説明を示すタイミングチャート
、第１４図はこの発明の説明の参考としたリード・ソロ
モン符号の復号回路の一例の説明のための路線図である
。 図面における主要な符号の説明 １、ＬＡ、ＩＢ・・・：データ制御部。 ２．２Ａ、２Ｂ・・・：演算部、３：クロス制御回路、
１１，１５，２５：加算回路、１４，１６゜２４．２６
：レジスタ、１３，１７，２３．２７：乗算回路。

Claims (1)

1. 【特許請求の範囲】 ユークリッド互除法により、誤り多項式σ（ｘ）と誤り
   評価多項式ω（ｘ）を導出するようにしたリード・ソロ
   モン符号の復号方法において、シンドローム多項式Ｓ（
   ｘ）を求め、上記シンドローム多項式Ｓ（ｘ）と訂正し
   ようとするシンボル数ｔで定まる初期多項式ｘ＾２＾ｔ
   との互いの最高次数を乗算しあいながら一つづつ順に次
   数を減らすことで、 ｆ（ｘ）・Ｂ（ｘ）＋ｇ（ｘ）・Ｓ（ｘ）＝ｈ（ｘ）（
   但し、ｈ（ｘ）の次数＜ｇ（ｘ）の次数≦ｔ）の関係を
   満足する多項式ｈ（ｘ）及びｇ（ｘ）を求め、上記多項
   式ｇ（ｘ）を上記誤り位置多項式σ（ｘ）とし、上記多
   項式ｈ（ｘ）を上記誤り評価多項式ω（ｘ）とすること
   を特徴とするリード・ソロモン符号の復号方法。