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

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野〕　゛ この発明は、リード・ソロモン符号の復号方法、特に、
イレージヤ訂正方法に関する。

〔発明の概要〕

この発明では、パリティ検査マトリクスと受信語により
、シンドロームを演算し、シンドロームから誤り位置多
項式σ（ｘ）及び誤り評価多項式ω（ｘ）を算出し、誤
り位置多項式σ（ｘ）の形式的一次微分の多項式σ′（
ｘ）及び誤り評価多項式ω（ｘ）を用い、〔ｅｐ＝ω（
α−ｐ）／σ′　（α−ｐ）〕の演算により、エラーパ
ターンｅｐを求め、誤り位置ｐのシンボルを訂正するよ
うにしたリード・ソロモン符号の復号方法において、ポ
インタで示されるエラー位置と対応する値で形成された
誤り位置多項式をσ１（ｘ）とし、誤り位置多項式σ″
″（ｘ）及びシンドローム多項式Ｓ（ｘ）を乗算して求
めたσ＊　（ｘ）　５（ｘ）を多項式ω＊（ｘ）とした
時に ｄｅｇ　σ＊　（ｘ）　＞ｄｅｇ　（１）”　（ｘ）の
条件が成立する時に、ポインタを正しいとしてイレージ
ヤ訂正を行うようにしたもので、ポインタの信頼性を確
実にチエツクすることができるものである。

〔従来の技術〕

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

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

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

Ｓｏ−Σｒ、　　αｊ　−１、、、Σｅｋα（ｋ−１１
ｋ（−＃！ Ｓ、＝Σｒ　ｉ（ｘ””−”　　　＝Ｅ　ｅ　ｋ（ｘ”
　（ト”ｉｔ Ｓ、＝Σｒ、　　α（ｊ＊１）　（＋−１）−Σｅｋα
（Ｊ＋Ｉｌ　（ｋ−１１４Ｅ Ｓ　ｚｃ−＋　＝”、Ｅ　ｒ　１　（ｘ”　”−”　　
＝　Σｅ　ｚ　（ｘ”　”−”に区 上式で発生された値を係数とする次の多項式をシンドロ
ーム多項式と称する。

５（ｘ）　＝ＳＯ＋Ｓ、ｘ＋Ｓｔｘ”　＋　、、−１−
Ｓ、ｔ−、Ｘ２Ｌ−’誤り訂正のために種々の多項式が
あるが、それらは次の関係式を満足する。

φ（ｘ）　　・ｘ”　＋σ（ｘ）　　・５（ｘ）　−（
１１）（ｘ）但し、 ω（ｘ）＝Σｅ　、　　・ｒｌ　（ｘ　−ｃｘ−”−”
）：誤り評価多項式りぐＥ　　　　　糞（Ｌ ｌＬ 上式の中で、実際の訂正をする場合に必要となるものは
、誤り位置多項式σ（ｘ）と誤り評価多項式ω（ｘ）の
二つである。

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

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

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

ｔ≧ｄｅｇ　ａ　（ｘ）　＞ｄｅｇ　ω（ｘ）（ｄｅｇ
は、多項式の次数を意味する。）ユークリッド互除法を
用いて、導出されたσ（ｘ）、ω（ｘ）を用いて、誤り
位置の推定及び誤り値の推定がされ、誤り訂正が実行さ
れる。この処理について４サンプル誤り訂正符号の場合
について説明する。受信信号が第８図Ａに示すように、
ｎシンボルの場合、誤り位置多項式σ（ｘ）のＸとして
代入される値は、第８図Ｂに示すように、受信信号の最
後から、その最初に向かって順に（１゜α−１，α−９
・　　α　　　、　　・・α−（ａ−１１）となる。即
ち、ｐという番号は、受信信号の最後から数えた番号で
ある。

一例として、第９図Ａにおいて、斜線で示すように、受
信信号の最後を０番目とすると、１番目及び４番目の各
々の位置で、誤りが発生し、これらの誤りが第９図Ｂに
示すように、（α■、α３）の誤りパターンである場合
の訂正を考える。この場合のシンドローム多項式は、下
記のものとなる。

５（ｘ）＝ｒｘ”　　ｘフ　＋ａ”　　ｘ”　　−ｚｒ
’　　ｘ’＋αｌｅ′ｘ’　＋ａｘ３＋ａ”　ｘ”　＋
ａ’　ｘ＋ａ”上記のシンドローム多項式Ｓ　（ｘ）と
ｘ２・４とを用い、ユークリッド互除演算により、σ（
ｘ）及びω（ｘ）を求める。その結果を示すと、下記の
ように、誤り位置多項式σ（ｘ）及び誤り評価多項式ω
（ｘ）が求まる。

σ（ｘ）−ｘ”　＋ｃｘ”ｘ＋ｃｒ” ω（ｘ）＝αＳ　ｘ十αＩ８ σ（ｘ）を形式的に１次微分してなるσ′（ｘ）は、σ
′（ｘ）　−αＩ０ となる、これらの誤り位置多項式及び誤り評価多項式を
用いて、誤り位置及び誤りパターンを求める。誤り位置
多項式σ（ｘ）に、順に（１，α−１゜α−３，・・・
）の値を代入し、その時の値がゼロになれば、誤り位置
と推定される。また、誤りパターンｅｐは、 ｅｐ＝ω（α−″′）／σ′　（α一つにより、求めら
れる。

第９図の場合では１ 、　（（ｘ−凰　）　　−ａ−”＋ａ’　　　＋　。　
区０＝０σ（α−４）−α−３＋α６＋α１０＝０とな
り、誤り位置が分る。

誤りパターンｅｌ及びｅ４は、 ｅ　、”＝　６）　（ｆｆ−’）　／　（ｔ　”””　
α”　／　（ｔ　”−（ｘ−’＝α■ ｅ　４　＝６）（ｆｆ−”）　／　（１！ｌ０−（ｘ”
／　（ｘ”＝Ｉ：ｔ”となり、正しい誤りパターンを求
めることができる。誤り訂正の実行は、受信系列に対し
て、上記の誤りパターンを（＋＊ｏｄ、　２　）の加算
することでなされる。

上述のリード・ソロモン符号に関して、１つの誤りは、
２つの未知数を含んでいる。従って、を重誤り訂正の場
合には、２１個のパリティが付加されて、受信側で発生
される２を個のシンドロームがｔ個の誤りの場合には、
２を個の独立な方程式に対応して、結局、を個の誤り位
置と、を個の誤りパターンを解くことが可能になってい
る。

この訂正方法と他に、リード・ソロモン符号では、イレ
ージヤ訂正という方法がある。

前出の下式を再度、とりあげる。

φ（ｘ）　　・ｘ”　＋６（ｘ）　　・５（ｘ）　＝、
ａ＞（ｘ）これより、 σ（ｒ）　　・５（ｘ）ミω（ｘ）　　　（ｓｏｄ、　
ｘ　”）が成り立つ、第９図の例に関して計算する。

５（ｘ）　−ｅｘ”　ｘ’　＋ｃｘ”　ｘ’　＋ｃｘ７
ｘ’＋ｃｒＮ）ｘ４　＋４Ｋ”　十α３Ｘ”　十〇”　
ｘ＋ｃｒ”σ（ｘ）＝ｘ’＋α１＠ｘ＋α１０ １Ｆ（ｘ）Ｓχｘ）　ｍａｒ”　ｘ”　＋ａｘ”　＋ｃ
ｒ’　ｘ＋ａ”＝α″ｘ＋ｃｒ”　　（ｍｏｄ、ｘ”　
）−ω（ｘ−） が成立していることが分る。

イレージヤ訂正の場合に１よ、他の誤り検出符号等を使
用して、ポインタが発生される。ポインタとは、誤りら
しいことを示すもので、ポインタが立ったからといって
、そのシンボルが直ちに誤りであるとは限らないことに
注意する必要がある。

第１Ｏ図八及び第１−０図已に示すように、第９図Ｂと
同様の誤りが発生しており、一方、第１０図Ｃに示す位
置にポインタが立っている場合のイレージヤ訂正につい
て説明する。

最初に、ポインタより、誤り位置多項式σ（ｘ）と対応
する誤り位置多項式σｌ”　（ｘ）を作る。ボインクは
、第１０図Ｃから明らかなように、（ｘ＝１）　（ｘ＝
α−’）（ｘ＝α−”）（ｘ＝α−４）の位置に相当す
るところに立ったので、σＩ”（ｘ）は、次のようにな
る。

σ、“（ｘ）＝　（ｘ＋１）（ｘ＋α−１）（ｘ＋α−
２）（ｘ＋α−４） ＝Ｘ’　＋ｃｘ’　　ｘ”　＋ｒｘ”　　ｘ”　＋ｃｘ
”ｘ＋ｃｘ”次に、この多項式σ、　”　（ｘ）とシン
ドローム多項式Ｓ　（ｘ）とを用いて娯り評価多項式ω
、　”　（ｘ）を求める。

σ１”　（ｘ）　５（ｘ）ミω、　”　（ｘ）実際に計
算すると、 ω　、　　”　　（ｘ）　　　＝ｃｘ　ｓ　　ｘ”　　
＋ｘ”　　＋ｔｘ　ｌｏ　（ｍｏｄ、ｘ’　　）また、 σ、　“　′（ｘ）＝αフ　ｘｇ　　＋α１０従って、
誤りパターンを求めてみると、次のようになる。

ｅｏ＝ω、　”　（１）　／σ、”（１）−〇／α６−
０ 誤りでないところなので、誤りパターンがＯで良い。

Ｘ÷α−１ ｅｐ＝ω、′（α−′）／σ、１　′　（α−’）−α
目／ｌ−α１ Ｘ；α−２ ｅｚ　＝ωｌ　’　（ｃｒ−”）　／　（ＪＩ”　　”
　　（（ｒ−”）−０／α１ｔ＝Ｏ Ｘ＝α−４ （！４　””ωＩ”　（（ｒ−’）　／　（１１”　　
′（（ｒ−’）＝α目／α目−α３ 以上のように、全て正しく誤りパターンが求まり、訂正
できることが分る。

イレージヤ訂正の場合には、ポインタが不正確な場合に
は、誤った訂正を行うおそれがある。例えば第１０図Ａ
及び第１０図Ｂと同様の誤りが第１１図Ａ及び第１１図
Ｂに示すように、発生している場合に、第１１図Ｃに示
すように、誤りを見逃したポインタが発生した場合を考
える。

このポインタにより求められた誤り位置多項式％式％（
） また、σｚ　”　（ｘ）　　５（ｘ）を計算すると、σ
ｘ　”　（ｘ）　５（ｘ）　＝ｔｘｘ’　＋ｃｘＩｚｘ
”　＋ｃｘ”　ｘ’＋ａ’　ｘ’　＋ｘ３＋α”　ｘ”
　＋ａ′４＝ωｔ　”　（ｘ）　　　（ｍｏｄ、ｘ’　
）となることが分かった。この多項式によっては、ポイ
ンタが立っていない位置の誤りの訂正ができない。

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

従来のリード・ソロモン符号の復号方法では、イレージ
ヤ訂正を行う時に、果してポインタが全ての誤り位置を
示しているかどうかを判断することができない問題があ
った。

従って、この発明の目的は、ポインタがエラー位置を全
て示しているかどうかをチエツクすることができ、信頼
性が高いイレージヤ訂正を行うことができるリード・ソ
ロモン符号の復号方法を提供することにある。

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

この発明では、パリティ検査マトリクスと受信語により
、シンドロームを演算し、シンドロームから誤り位置多
項式σ（ｘ）及び誤り評価多項式ω（ｘ）を算出し、誤
り位置多項式σ（ｘ）の形式的一次微分の多項式σ′（
ｘ）及び誤り評価多項式ω（ｘ）を用い、〔ｅｐ＝ω（
α−Ｐ）／σ′　（α−ｐ）〕の演算により、エラーパ
ターンｅｐを求め、誤り位Ｗｐのシンボルを訂正するよ
うにしたリード・ソロモン符号の復号方法において、ポ
インタで示されるエラー位置と対応する値で形成された
誤り位置多項式をσ′″（ｘ）　とし、誤り位置多項式
σ″（ｘ）及びシンドローム多項式５（ｘ）を乗算して
求めたσ’　（ｘ）　５（ｘ）を多項式ω９（ｘ）とし
た時に ｄｅｇ　σ″（ｘ）　＞ｄｅｇ　ω＊　（ｘ）の条件が
成立する時に、ポインタを正しいとしてイレージヤ訂正
がなされる。

〔作用〕

第１０図Ｃに示すように、誤り位置を全て含むポインタ
が立っている場合には、 σＩ＊　（ｘ）＝　（ｘ＋１）（ｘ＋ｃｒ−’）（ｘ＋
α−２）（ｘ＋α−４） ＝ｘ４＋α？　ｘ３＋α２　ｘｇ＋α′。ｘ＋α８ω、
　”　（＊）　＝α’　ｘ３＋ｘ”　＋ｔｘ”　（ｍｏ
ｄｙｘ”　）となる。

一方、第１１図Ｃに示すポインタのように、一つでも、
エラー位置を含まないポインタの場合には、 ａｔ　”　（ｘ）　＝　（ｘ＋１）　　（ｘ＋ｃｒ−’
）　　Ｃｘ＋ｃｒ−２）−ｘ”　＋ｃｘ”　ｘ”　＋ｒ
ｘ”　ｘ”　＋ａ’　ｘ十ａ”また、ａｔ　”　（ｘ）
　５（ｘ）を計算すると、ａｔ　”　（ｘ）　５（ｘ）
　：＝αｘ’　＋α”ｘ”　＋ｏｅ”　ｘ’＋α’　ｘ
’　＋ｘ３＋α３　ｘＺ＋αＩ４＝ωｔ　”　（ｘ）　
　　（ｓｏｄ、ｘ”　）となる、これらのことから下記
のことが分る。

を重誤り訂正符号で、イレージヤ訂正をする場合、 ■２を個以下のポインタが正しい誤り位置を全て含む場
合 ｄｅｇ　ａ”　（ｘ）　＞ｄｅｇ　ω＊　（ｘ）（又は
　ｄｅｇ　ｔｙ”　（ｘ）　−ｄｅｇ　ω＊　（ｘ）　
＋　１　）０２１個以下のポインタが誤り位置をひとつ
でも含まない場合、即ち、正しいポインタとして働かな
い場合 ｄｅｇ　ａ”　（ｘ）≦ｄｅｇ　ω＊　’　（ｘ）とな
ることが分る。

〔実施例〕

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

ａ、復号方法 す、多項式乗算回路 ａ、復号方法 第１図は、この一実施例のリード・ソロモン符号の復号
方法を示すフローチャートである。第１図において、最
初にポインタの数Ｎｐが（Ｎｐ≦２ｔ）かどうかが調べ
られる（ステップ■）、ポインタの数がＮｐ以下であれ
ば、ポインタを使用しないで、誤り訂正が可能なので、
ステップ■に移行し、シンドローム多項式Ｓ　（ｘ）か
ら誤り位置多項式σ（ｘ）及び誤り評価多項式ω（ｘ）
が求められる。この方法としては、ユークリッド互除法
が使用できる。

ステップ■から■に移行し、（ｄｅｇ　σ（ｘ）＜ｔ）
かどうかが調べられる。この条件が成立しないと、エラ
ー訂正が不可能なため、ポインタ位置の全てにエラー修
整フラグがセットされる（ステップ■）、ステップ■の
条件が成立すると、ステップ■に移行し、誤り位置が探
される。即ち、（σ（ｘ）＝Ｏ）となる（ｘ＝α−ｐ凰
）が探される。

この検出されたエラー位置ｐ直が（０≦ｐ１くｎ）かど
うかが調べられる（ステップ■）。このステップ■の条
件が成立する時には、エラー訂正のステップ■に移行し
、ステップ■の条件が成立しない時には、ステップ■の
エラー修整フラグのセットのステップに移行する。

エラー訂正は、エラー位置多項式σ（ｘ）の形式的な１
次微分をσ゛（ｘ）とすると、次式により、エラーパタ
ーンを求め、このエラーパターンを受信語に加算する処
理である。

ｅｐ！”ω（α−ｐ１）／σ′　（α−ｐ″）上述の処
理と異なり、ステップ■において、エラーポインタの数
Ｎｐが２を以上の場合には、イレージヤ訂正がなされる
。イレージヤ訂正の場合、ポインタの位置から誤り位置
多項式σ１（ｘ）が計算される（ステップ■）０次のス
テップ■では、ω＊（ｘ）（＝σ＊　（ｘ）　Ｘ５（ｘ
）　）が計算される。

ここで、ポインタの信頼性の判断がなされる（ステップ
■）　、　　（ｄｅｇ　ａ”　（ｘ）　＞ｄｅｇ　ω＊
　（ｘ））が成立する時には、ポインタの信頼性が高い
と判断され、エラーパターンｅｐｔがステップ■におい
て求められる。

ｅｐＬ＝ω＊　（α−”）／σ０　′　（α−１ｌｌ　
）ポインタの信頼性が低い場合には、イレージヤ訂正が
なされない。

一例として、第１２図Ａにおいて斜線で示すように、（
１，α１．α−２，α−３，α−４）の位置に誤りが発
生しており、各々の誤りが第１２ｌ８に示すように、（
α４．α４．α３．α８．α、）であって、　ポインタ
が第１２図Ｃに示すように、（１，α−１，α−ｇ、α
弓、α−４．α″７）の位置に立っている場合について
説明する。

ポインタより、誤り位置多項式σ“、を求める。

６”　！　（ｘ）＝　（ｘ＋１）（ｘ＋α−’）（ｘ＋
ｃｒ−”）　　（ｘ　＋　α−３）　　（ｘ＋α−４）
（ｘ＋α−７）＝ｘ”　＋ｘ”　＋ｒｘ”　ｘ’　＋ａ
ＩＯｘ３＋ａ’　ｘ”＋　αｌｌｘ＋α１３ 従って、 σＩ、’＝ｘ４　＋αｚ＋Ｘｚ　＋α３受信信号から作
られたシンドローム多項式５（ｘ）は、 ５（ｘ）＝α”Ｘ’　＋ａ’　ｘ６＋α”　ｘ５十αｂ
　ｘＡ＋α”　ｘ’　十Ｘ”　＋ｒｘ’　Ｘ＋ａ’誤り
評価多項式ω“、（ｘ）は、 σ＊　＝　（ｘ）・Ｓ　（ｘ）ミ ａ”ｘＳ＋ｘ’　＋ａ”ｘ”　＋ｃｔ１４ｘ”　＋αＩ
４Ｘ＋（ｘ２＝Ｇ）”　ｓ　（ｘ）　　　（Ｉｌｌｏｄ
、　　ｘ”　）となり、また、 ｄｅｇ　ａ”　３　（ｘ）　＝ｄｅｇ　（１１１ｓ　（
ｘ）　＋　１となる。従って、ポインタが真の誤り位置
を全て含んでいることが分る。即ち、このポインタは、
信頼できるということである。実際に、誤りパターンを
σ　２　（ｘ）　＋　ω“、（ｘ）より求めてみると、
次のようになる。

ｘ＝１ ｅ６＝ω３’″（１）　／　６３　”　　’　（１）＝
α”／α４；α４ Ｘ−α−１ ｅｌ　””（ｄ３　”　（α−’）　／　（ｆ３　”　
　’　　（（ｒ−Ｊ＝１／α目−α４ Ｘ；α−２ ｅｌ　−ω３′″　（α−２）／σ３１　′　（α−２
）＝α４　／α＝α３ Ｘ±α−３ ｅｐ−ω３′（α−３）／σ、１′（α−３）−α１３
／α目＝α２ Ｘ；α−４ ｅ４＝ω３１（α−４）／σ３“　（α−４）工α４／
α３　＝α χ＝α−７ ｅ７−ω３′（α−７）／σ３′″　′　（α−７）＝
０／α１ｔ＝０ この位置は、真のエラーでないので、０となることが正
しい。

ｂ、多項式乗算回路 上述のイレージヤ訂正では、次の２種類の計算を行う必
要がある。

■ポインタ位置に対応するα−１”　（ｉ＝１．２゜・
・・・、２ｔ）を根とする誤り位置多項式σ８（χ）の
係数σ、（ｊ＝１．２．　　・・・２ｔ−１）を求める
。

■得られたσ＊（ｘ）と受信信号のシンドロームより得
られたシンドローム多項式Ｓ　（ｘ）とを乗算して誤り
評価多項式ω９（ｘ）を求める。

ω＊　（ｘ）　＝σ“（ｘ）　　・Ｓ（ｘ）そして、重
要なチエツクとして ｄｅｇ　ｄ”　（ｘ）　＝ｄｅｇ　ω＊　（ｘ）　＋　
１が成立するかどうかを確認する。

第２図は、σ１（ｘ）の計算回路の一例である。

第２図において、ｒは、１クロツタの遅延量を生じさせ
るフリップフロップ、ＡＤは、有限体の加算回路、ＭＬ
は、有限体の乗算回路である。入力端子１には、（１，
α−”、ｏ、ｏ、ｏ・・・）の順序でデータが人力され
る。

２個のフリップフロップｒと乗算回路Ｍ　Ｌと加算回路
ＡＤとからなる単位構成が（２ｔ−１）段、縦続接続さ
れている。各段の乗算回路ＭＬには、。−１１，ｔｌ　
　　、・　α−ｔｘｔが各々供給されてα−・ いる。出力端子２には、最初にσ２ｔが得られ、以下σ
ＫＬ−Ｉｎ　　・・・・σ、が順次得られ、最後にσ。

が得られる。

第２図に示す演算回路について、第３図を参照して説明
する。−船釣に（ｘ＋ａ）（ｘ＋ｂ）（ｘ＋ｃ）（ｘ＋
ｄ）の演算を行うことを考える。

第３図Ａに示すように、１個のフリップフロップと２個
の乗算回路と２個の加算回路とにより、出力として、（
１，ａ＋ｂ、ａｂ）が得られる回路が構成される。第３
図Ａに示すように、この回路の構成は、各１個のフリッ
プフロップｒ、加算回路ＡＤ、乗算回路ＭＬの構成に置
き換えられる。

第３図Ａは、（ｘ＋ａ）（ｘ＋ｂ）の演算を行う回路で
あるので、この結果を第３図Ｂに示すように、（、Ｘ　
＋　Ｃ）の乗算回路に通し、更に、その結果を（ｘ＋ｄ
）の乗算回路に通す構成により、（ｘ＋ａ）（ｘ＋ｂ）
（ｘ＋ｃ）（ｘ＋ｄ）の演算回路が実現される。この場
合、人力は、（１゜ａ、Ｏ，Ｏ，・・・）とされ、出力
には、答えの係数が降べき順に出力される。

第４図は、σ′″（ｘ）の計算回路の他の例である。　
　−入力端子ｌには、（α−”　、１．Ｏ，Ｏ，Ｏ・・
・）の順序でデータが入力される。

２個のフリップフロップｒと乗算回路ＭＬと加算回路Ａ
Ｄとからなる単位構成が（２ｔ−１）段、縦続接続され
ている。各段の乗算回路ＭＬには、α−目、α−Ｌ３　
　・・・　α−Ｌ１が各々供給されている。出力端子２
には、最初にσ。が得られ、以下σ８．・・・・σ２．
−１が順次得られ、最後にσハが得られる。

第４図に示す演算回路について、第５図を参照して説明
する。−船釣に（ｘ＋ａ）（ｘ十ｂ）（ｘ＋ｃ）（ｘ＋
ｄ）の演算を行うことを考える。

第５図Ａに示すように、１個のフリップフロップと２個
の乗算回路と２個の加算回路とにより、出力として、（
１，ａ＋ｂ、ａｂ）が得られる回路が構成される。第５
図Ａに示すように、この回路の構成は、各１個のフリッ
プフロップｒ１加算回路ＡＤ、乗算回路ＭＬの構成に置
き換えられる。

この第５図Ａに示す構成は、乗算回路と加算回路とが分
離されてしまい、形が良くないので、第５図Ｂに示すよ
うに、１とｂを交換するかわりに、入力も１とａとを交
換する。

第５図Ｂは、（ｘ＋ａ）（ｘ＋ｂ）の演算を行う回路で
あるので、この結果を第５図Ｃに示すように、（ｘ＋Ｃ
）の乗算回路に通し、更に、その結果を（ｘ＋ｄ）の乗
算回路に通す構成により、（ｘ＋ａ）（ｘ十ｂ）（ｘ＋
ｃ）（ｘ＋ｄ）の演算回路が実現される。この場合、人
力は、（ａ。

１、Ｏ，Ｏ，・・・）とされ、出力には、答えの係数が
弄べき順に出力される。

第６図及び第７図は、ω０（ｘ）の計算回路の一例及び
他の例を示す。第６図及び第７図における入力端子１１
には、０が供給される。第６図の構成では、出力端子１
２には、降べきの順序の出力が得られる。一方、第７図
の構成では、出力端子１２には、昇べきの順−序の出力
が得られる。

〔発明の効果〕

この発明によれば、イレージヤ訂正時にポインタの信頬
性をチエツクすることができる。この発明を採用すれば
、たとえポインタに誤りがあっても、この誤りを検出し
、イレージヤ訂正を中止して、正規の誤り訂正が可能か
どうかを調べるので、誤り訂正できる場合を増やすこと
ができる。

【図面の簡単な説明】

第１図はこの発明によるリード・ソロモン符号の復号方
法の一実施例の説明のためのフローチャート、第２図は
多項式乗算回路の一例のブロック図、第３図は第２図の
説明のためのブロック図、第４図は多項式乗算回路の他
の例のブロック図、第５図は第４図の説明のためのブロ
ック図、第６図はσ１（ｘ）・Ｓ　（ｘ）の演算回路の
一例のブロック図、第７図はσ′″（ｘ）　　・Ｓ　（
ｘ）の演算回路の他　　　−の例のブロック図、第８図
は誤り位置の値の説明のための路線図、第９図、第１Ｏ
図、第１１図。 第１２図は各々誤りパターンの説明のための路線図であ
る。 図面における主要な符号の説明 ■、■：誤りパターンを求めるステップ、［相］：ポイ
ンタの信頼性をチエツクするステップ。 代理人　弁理士　杉　浦　正　知 Ａ［Ｉ丁７［【Ｔ］タニ］Ｔ豆丁７二Ｎ二二Ｆロ丁石］
宮芸リす立、ト埴 第８図 Ａ　　「１１了彩［＝］二下−弱１丁「二丁二ニニニ口
Ｂ　　　　［ぐ］　　　　　日 謀りｌぐダーン 第９図 Ａ　口下ｍ了可［丁二Ｙ−二口 ＢＥ］　　　囲 τ炙すパターン Ｂ　　国　　凹 吉乳り、１ターン ゛　第１１図 誤すノマターン 第１２図

Claims (1)

1. 【特許請求の範囲】 パリテイ検査マトリクスと受信語により、シンドローム
   を演算し、上記シンドロームから誤り位置多項式σ（ｘ
   ）及び誤り評価多項式ω（ｘ）を算出し、上記誤り位置
   多項式σ（ｘ）の形式的一次微分の多項式σ′（ｘ）及
   び上記誤り評価多項式ω（ｘ）を用い、〔ｅ＿ｐ＝ω（
   α＾−＾ｐ）／σ′（α＾−＾ｐ）〕の演算により、エ
   ラーパターンｅ＿ｐを求め、誤り位置ｐのシンボルを訂
   正するようにしたリード・ソロモン符号の復号方法にお
   いて、 ポインタで示されるエラー位置と対応する値で形成され
   た誤り位置多項式をσ＾＊（ｘ）とし、上記誤り位置多
   項式σ＾＊（ｘ）及びシンドローム多項式Ｓ（ｘ）を乗
   算して求めたσ＾＊（ｘ）Ｓ（ｘ）を多項式ω＾＊（ｘ
   ）とした時に ｄｅｇσ＾＊（ｘ）＞ｄｅｇω＾＊（ｘ） の条件が成立する時に、上記ポインタを正しいとしてイ
   レージャ訂正を行うようにしたことを特徴とするリード
   ・ソロモン符号の復号方法。