JPS6034137B2 - リ−ド・ソロモン符号復号方式 - Google Patents

Description

【発明の詳細な説明】 本発明はリード・ソロモン符号を用いた誤り訂正復号方
式に関する。

リード・ソロモン符号はランダム誤りを訂正するための
現在知られている最も強力な誤り訂正符号の１つである
。

リード・ソロモン符号に関しては米国のノース．ホーラ
ンドパブリツシング カンパニイ（ＮＯＲＴＨ
ＨＯＬＬＡＮＤＰＵＢＬＩＳＨＩ
ＮＧＣＯＭＰＡＮＹ）から１９７８年に発行されたエフ
・ジェー・マックウィリアム（Ｆ．Ｊ．ＭＡＣＷＩＬｌ
ＡＭ）ヱヌ・ジエ−・エイ・スローン（Ｎ・Ｊ・Ａ・Ｓ
ＬＯＡＮ）著ザ セオリィ オブエフー コレクテイ
ング コーズ（ＴＨＥＴＨＥＯＲＹ ＯＦ ＥＲ
ＲＯＲ ＣＯＲＲＥＣＴＩＮＣＤＯＤＥＳ）に詳述さ
れている。

この符号は、巡回符号の一種であるためにその符号化に
関しては、よく知られた巡回符号の符号器を用いて比較
的簡単に実現できるが、その復号に関しては一般的な従
来の方法を用いると装置が非常に複雑になり、また符号
自体のもつ誤り検出能力を充分に使いきっていないとい
う欠点を有している。

本発明の目的は従来のこのような欠点を除去するにある
。

本発明の方式は、Ｍ個（但しＭは正の整数）の１次多項
式の積でできる生成多項式から生成される符号長Ｎ（但
しＮ‘まＭよりも大きい正の整数）のりード・ソロモン
符号を受信して該受信符号に対するＭ個のシンドローム
Ｓｏ，Ｓ，，・・・…，ＳＭ‐，を演算し該シンドロ−
ムをもとに該受信符号内に１シンボルだけの誤りが生じ
ていることを検出したらその誤りを訂正し２シンボル以
上の誤りを検出したら誤り検出情報を出力する方式であ
って、前記シンドロームＳｏ，Ｓ，，…・・・，ＳＭ‐
・よりＭ−１個のシンドローム比Ｓ．・Ｓ６１，Ｓ２・
Ｓｔｌ，・・・・・・，ＳＭ‐．・Ｓに２に対応する情
報を演算するシンドローム比情報演算手段と、前記シン
ドローム比に対応する情報がすべて等しいか否かを判定
するシンドローム比情報比較手段と、前シンドロームＳ
ｏ，Ｓ，，・・・・・・，ＳＭ，のすべてが“０”か否
かを判定するシンドロームオールゼロ判定手段と、前記
シンドロームＳｏ，Ｓ，，……，ＳＭ‐，のうちに少く
とも１個の“０”のシンドローム含まれるか否かを判定
するシンドロームオールゼロ判定手段と、前記シンドロ
ーム比情報比較手段の出力と前記シンドロームオールゼ
ロ判定手段の出力と前記シンドロームゼロ検出手段の出
力とに応答して予め定めたアルゴリズムに従って訂正を
実行すべきか否かを決定し訂正を行う場合にはブロック
内の前言己シソドローム比により定まる位置のシンボル
に対し前記シンドロームＳｏを誤り訂正情報として誤り
訂正を実行する誤り訂正手段とを含む。

次に図面を参照して本発明を詳細に説明する。

第１図は本発明の一実施例を示すブロック図である。本
実施例はシンドローム演算回路１、シンドローム比演算
回路２、シンドローム比比較回路３、シンドロームオー
ルゼロ判定回路４、シンドロームオールゼロ検出回路５
、訂正実行制御論理回路６および誤り訂正実行回路７を
有している。さて、このブロック図に従って本実施例の
動作の詳細を説明する前にまずその動作原理を先に説明
する。一般に、リード・ソ。

モン符号においては、Ｎ個のシンボルが１符号ブロック
を構成し、この１符号ブロック中にＭ個の検査用シンボ
ルと、Ｎ−Ｍ個の情報伝達用シンボルとが含まれる。こ
こで用いられる各シンボルには種種あるが、本実施例で
は、一般に広く用いられている８ビットの符号ベクトル
と仮定する。また、説明を具体的にするために、１符号
ブロック中のシンボルの数（符号長）Ｎ＝３２とし、ま
た１符号ブロック中の検査用シンボルの数Ｍ＝４と仮定
する。従って１符号ブロック中の情報伝達データ用シン
ボルの数は、Ｎ一Ｍ＝２８となる。さて、１符号ブロッ
ク中の３２個の各シンボルを氏，Ｂ，．Ｂ２，＆，Ｂ４
，・・・・・・，Ｂ３，で表わすことにする。

任意のＢｊは１バイトの符号であり、従って、ぞ＝２５
６個の元の中の１つの元と表わしている。また、この中
のシンボルＢ４〜＆，の２８個が情報伝達データ用シン
ボルで、残りのＢｏ〜＆がこのＢ４〜Ｂ３，をもとにし
て作られた検査用シンボルであると仮定する。さて、リ
ード・ソロモン符号においては、符号化の過程において
、検査用シンボル恥〜Ｂ３は情報伝達データ用シンボル
Ｂ４〜Ｂのとの間で次の拘束関係を満足するように作ら
れる。

すなわち、この‘１｝式においては、各シンボルの記号
Ｂｊのほかに、記号Ｑが用いられ、また、十で結ばれた
和の演算と、Ｑ同志間の積（Ｑの幕）およびＱの穣とＢ
ｉとの積の演算が用いられている。このＱは特定のシン
ボルを代表し、また上述の和および積も一般の２進数の
和および積とは異なる特別の演算を意味する。以下これ
について説明する。上述のように、本実施例ではＢｊも
Ｑもともに８ビットの“１”，“０”符号でできている
符号ベクトルとする。従って、いずれもぞ＝２５針固の
中の１つの元を表わしている。さて、この２５針固の中
から任意の２つの元ＡとＢとを選び、この２つの元の和
で指定される元Ａ＋Ｂおよび２つの元の積で指定される
元ＡＢのいずれも、もとの２５針固中の１つの元になる
と仮定してその各各を次のように定義する。

天０：第２図に示すように元Ａおよび元Ｂを符号ベクト
ルの形で表示し、各桁（各次元）ごとの排他的論理和を
とった結果生ずる符号ベクトルをＡ＋Ｂと定義する。

和の演算がこのように定義されるために２個の同じ元の
和は常に“０”（各次元の成分がすべて“０”の符号ベ
クトル）となり、また、和の逆算としての差の演算は和
の演算と同じになるという箸るしい結果を生ずる。積：
例えば第３図１に示すような元Ａおよび元Ｂがあると、
これをｘの多項式表現Ａ＝１十×２十ず十×５ Ｂ＝ｘ２十ゞ とし、この多項式の積ＡＢを ＡＢニ（１十×２十×３十×５）（之十×４）ニＸ２（
で＋Ｘ４）十×５十で十（Ｘ７十×７）十でのように作
る。

この中でｘの同じ累乗の項は、符号ベクトルの同じ桁（
次元）に対応するので、上述の排他的論理和の規則を適
用して整理すると上式は、ＡＢ＝だ＋×６十×５十×２ となる。

この多項式はｘの７案以上の項（すなわちゞの項）を含
むので、このままではこれに対応する８ビットの符号ベ
クトルを指定するとができない。そこで、積を定義する
場合には、それに伴って８次のある既約多項式ｆ（ｘ）
を予め定めておき、これを用いて以下のように定義する
。

このｆ（ｘ）を ｆ（ｘ）＝ず十で十×３十×十１ と仮定すると、このｆ（ｘ）を用いて前記ＡＢの多項式
を割算し、その結果生ずる剰余を作る。

こうすると、剰余は必らずｘの７次またはそれ以下の次
数の多項式となるので、これに対応する８ビットの符号
ベクトルが存在する。これを積ＡＢと定義する。今の場
合、上述のＡＢの多項式をｆ（ｘ）で除した商は、ｘと
なり、剰余はゞ十〆十ｘ となる（この演算においても前述の排他的論理和の規則
が適用されていて、引き算と足し算は同じである）。

これよりＡＢ＝ゞ十×４十× となり、これを符号ベクトルで表示すると第３図２に示
すようになる。

以上のように、８次の既約多項式ｆ（ｘ）を指定すると
、それに応じて２５針固の各元の間で、和および積が定
義され、またその逆算としての差および商も定義され、
２５針固の元の中で４則演算が矛盾なく行なわれる。

さて、前記既約多項式ｆ（ｘ）を適当に選ぶことにより
、前記２５軌固の元の中の“０”（すべての桁の成分が
“０”の元）を除く２５６個のすべての元を、ある元Ｑ
の累乗の形で表わすことができる。

すなわち、１を単位元とし、これにつぎつぎにＱ乗ずる
ことによって生ずる元、Ｑ，Ｑ２，Ｑ３ ……Ｑ２５５
は前記“０”を除くすべての元を一巡してＱ２５５で再
び単位元１に戻るようにすることができる。実際に、前
記既約多項式ｆ（ｘ）として、ｆ（ｘ）ニだ十で十×３
十ｘ＋１ を用い、Ｑとして多項式表現のｘを用いると、２５５の
すべての元はＱｊ（但しｉ＝０，１，２，・・・…，２
５５）として表わすことができる。

但しＱ０＝Ｑ２５５＝１である。このＱを原始元と呼び
、またこのような性質を有する多項式ｆ（ｘ）を原始多
項式と呼ぶ。このような性質をもつ８次の原始多項式は
、上述のものを含んで１針固あることが知られている。
本実施例においては、この１６個の中の特定の一つの原
始多項式によって元の間の演算が定義されていると仮定
し、またこれによって定義される前記原始元Ｑを用いる
ことにする。この結果０を除く任意の元は、Ｑｊ（但し
ｊ＝０，１，２，・・・・・・，２５４）で表現され、
従って、任意の元は、指数ｉだけでも指定することがで
きる。これを元の指数表現と呼ぶことにする。この指数
表現を用いると、“０”を除く任意の２つの元の積は、
各各の元の指数表現をとり、この両者を２５５を法とし
て加えることにより両者の積の指数表現として簡単に演
算することができる。もし一方の元に“０”が含まれる
場合には結果の元を“０”とすればよい。また、商を作
る場合には、分母になる元の指数表現の２進数を、その
各桁の“１”“０”を反転してから前述と同様に２５５
を法として加えればよい。勿論、２つの元の和を演算す
る場合には、符号ベクトルの表現を用いると簡単に行な
うことができる。

このように、各元は、Ｑの累乗でも、Ｑの指数表現でも
、符号ベクトル表現としても、また多項式表現としても
指定することができる。

これらの中のいずれの表現を用いるかは、その使用目的
によって最も適当なものを選びことができる。さて、こ
うして‘１ー式の演算は定義されたが、実際に、任意の
情報伝達データ用シンボルＢ４〜＆，から｛１｝式の拘
束条件を満足する検査用シンボル恥〜Ｂ３を生成するに
は次のようにする。今、生成多項式ｇ（Ｘ）として、 ｇ（Ｘ）＝（×−１）（Ｘ−Ｑ）（×−Ｑ２）（Ｘ−Ｑ
３）を定義し、一方符号多項式Ｃ（Ｘ）としてＣ（Ｘ）
二ＢＩＸ３１十Ｂ３〆弧＋……十Ｂ４×４を定義する。

このＣ（Ｘ）をｇ（Ｘ）で除した剰余の多項式をＲ（×
）とすると、Ｒ（×）は×に関する３次またはそれ以下
の多項式となるので、Ｒ（Ｘ）＝はＸ３十ＱＸ２十ｂ，
Ｘ＋ｂｏと表わせる。

こうして定まるｂ３，Ｑ，ｂ，およびｂｏをそれぞれ検
査用シンボルＢ３，Ｂ２，ＢおよびＢｏとして用いると
、これらは次のような理由で【１｝式の拘束条件を満す
検査用シンボルとなっている。今、Ｃ（Ｘ）をｇ（×）
で除した商をＱ（×）と書くと、Ｃ（Ｘ）：ｇ（Ｘ）Ｑ
（Ｘ）＋Ｒ（Ｘ）となり、これから、Ｃ（Ｘ）＋Ｒ（×
）＝ｇ（Ｘ）Ｑ（Ｘ〉が導かれる（この場合もＲ（×）
を引くことはＲ（Ｘ）を加えることと同じである）。従
ってＣ（×）十Ｒ（×）はｇ（×）で割り切れて、＆Ｉ
Ｘ３１十Ｂ３〆柳十……十Ｂ４×４十Ｂ３×３十ＱＸ２
十Ｂ，Ｘ＋Ｂ。

ニ（Ｘ−・）（Ｘ一Ｑ）（Ｘ−Ｑ２）（Ｘ−Ｑ３）Ｑ（
×）が成立する。

上式の両辺のＸに、それぞれ１，Ｑ， Ｑ２およびＱ３
をつぎつぎに代入することによって、‘１｝式の関係が
導かれる。なお、生成多項式ｇ（Ｘ）が与えられると、
上述の割算を実行して、Ｂ４〜Ｂ３，のシンボルからＢ
ｏ〜Ｂ３のシンボルを生成する巡回符号の符号器の構成
を決定することも容易であるがここでは省略する。

さて、上述のようにして送信側で作られた‘１｝式の拘
束条件を満す芙号ブロックＢｏ，Ｂ，Ｂ２，・・・・・
・，Ｂ３，を受信し、それらがＢｏ，Ｂ，Ｂ２，・・…
・＆，として受信されたとする。

そしてこれらの中の１つのシンボルＢｉにだけ誤りが生
じたと仮定する。すなわち、ｊ以外のけこ対しては、Ｂ
ｋ＝Ｂｋ ””“｛２’が成
立し、Ｂｉに対してはＢｊ＝Ｂｊ十Ｅｊ
””“【３’とする。

但し、Ｅｊはｊ番目のシンボルに起った誤りとする。さ
て、今受信側において、受信シンボルＢｏ，Ｂ，Ｂ２，
・・・・・・，＆．を用いて‘１｝式の各式の左辺に相
当する演算を行ない、その結果をそれぞれＳぶ．Ｓ２Ｓ
３とする。

すなわち、とする。

もし、受信に全く誤りがなければ、‘４｝式の左辺はｍ
式の左辺と全く同じになり、従って、Ｓｏ〜Ｓ３はすべ
て“０”になる筈である。受信に誤りがあると‘４｝式
の各左辺に相当する演算結果は一般に０でないそれぞれ
の値Ｓｏ，Ｓ，，Ｓ２，およびＳ３をとることになる。
これをシンドロームという。本実施例は、このシンドロ
ームＳｏ〜Ｓ３を用い、送信側でーブロック内のシンボ
ル間に加えた‘１｝式の拘束演算関係から誤り分を求め
てこれを訂正する方式である。さて、■式、（３｝式の
関係を■式に代入し、ｍの関係を用いると、結果は次の
ようになる。

この■式を変形すると、次の４個の式が導かれる。

さて、上の【６’式および（７｝式を用いてＳｏおよび
Ｓ，だけで誤り訂正を行なうことも可能である。

すなわち、■式よりＳ，およびＳｏを用いて誤りシンボ
ル位置のｉが求まり、また、■式からＳｏを用いて誤り
訂正情報Ｅｊが得られるので、ｉ番目のシンボル位置の
受信シンボルＢｊにＳｏを加えればよい（前述の規則に
従って８ビットシンボルの各桁ごとの排他的論理和をと
る）。しかし、本実施例においては、比較的簡単な回路
構成により、上述のＳｏおよびＳ，ばかりでなく、得ら
れたすべてのシンドローム情報Ｓｏ〜Ｓ３を用いて誤り
訂正を行なうことを可能とし、そのために誤り訂正の信
頼性を一層向上させている。次に第１図を用いて本実施
例の動作の詳細を説明する。

受信された入力信号の符号ブロックは、データ入力ライ
ン１００より、各シンボルがＢ３，，Ｂ３。，・・・・
・・，Ｂの順序で、シンドローム演算回路１に供給され
る。それと共にまた誤り訂正実行回路７に供給される。
回路１において、前認４｝式に対応する演算が実行され
て、シンド。ールＳｏ，Ｓ，，Ｓ２およびＳ３が求めら
れる。この中の、例えばＳ，を求める演算回路例を第４
図に示す。これは１段のシフトレジスタ１０、読出し専
用メモリ（ＲＯＭ）１１、および排他的論理和回路１２
から成っている。シフトレジスター０および回路１２は
それぞれ８ビット分を並列に処理する。またＲＯＭＩＩ
は、シフトレジスタ１０の出力（８ビット）でアドレス
指定のできる２５６のメモリアドレスを有し、各メモリ
アドレス当り８ビットのデータを格納できる容量を有す
る。シフトレジスタ１０の出力により指定されるＲＯＭ
ＩＩのメモリアドレスからデータが読み出され、回路１
２により入力データとの排他的論理和がとられ、これが
シフトレジスタ１川こ読み込まれる。任意の８ビットの
２進数Ａ′で指定されるＲＯＭＩＩのメモリアドレスに
ＱＡ′（但しＱＡ′はこの２進数Ａ′に対応する符号ベ
クトルと原始元Ｑとの積とする）を書き込んでおくと、
ＲＯＭＩ ＩはＱ倍の乗算器として動作する。かくて、
最初にシフトレジスタ１０をリセットし、入力データを
前述のように馬，，Ｂ柳…・・・，Ｂｏの順序で次次に
回路１２を介して入力すると、恥が入力された時点で、
シフトレジスタ１０の内容は、 へ へ（…（（＆
，Ｑ＋＆ｏ）Ｑ＋珍９）Ｑ＋……十Ｂ）Ｑ＋Ｂ。

ニＱのＢの十Ｑ３０氏。

十，．．，．．十ＱＢ十Ｂ。

＝Ｓ，となり、求めるシンドロームＳ，となる。

ＲＯＭＩＩの内容を、上述のＱのかわりにＱ２およびＱ
３に相当するものとすることにより、同様な回路を用い
てそれぞれシンドロームＳ２およびＳ３を演算する回路
が得られ、またＲＯＭＩＩを除きシフトレジスタ１０の
内容をそのまま回路１２にフィードバックすることによ
りシンドロームＳｏを演算する回路が得られる。かくし
て得られたシンドロームＳｏ〜Ｓ３は、シンドローム比
演算回路２、シンドロームゼロ判定回路４、シンドロー
ムゼロ検出回路５に供給され、また、Ｓｏは前記｛６’
式のＥｊとして訂正実行制御論理和回路６を介して訂正
実行回路７に供給される。

さて、シンドローム比演算回路２においては、前認７｝
式、‘８｝式および‘９｝式の演算を行なうことにより
、それぞれの式から別別にＱｊの指数表現ｊを求める。

今‘７｝式、｛８）式および‘９｝式から求められたｉ
をそれぞれｉ′，ｉ″と書くことにする。第５図にシン
ドローム比演算回路２の回路例を示す。供給されたシン
ドロームＳ。は論出し専用メモリＲＯＭ２０によって、
Ｓ６１＝Ｑｋを満足するｋ（‘‘０”以外の任意のＳｏ
はＱを用いてＱｇと表わせるがこのｇを用いて（ｋ＋ｇ
）ＭＯＤ２５５＝０を満足するｋ、すなわちｇの各ビッ
トを反転したもの）に変換される。ＲＯＭ２０は２５６
メモリアドレスを有し、各メモリアドレスごとに１バイ
トの容量を有するが、任意の２進数Ａ″で指定されるメ
モリアドレスには、Ａ′′＝Ｑｂの関係をもつｂの補数
を格納しておくことにより上述のＳｏ→ｋへの変換が実
行される。一方供給されたシンドロームＳ，は、読出し
専用メモリＲＯＭ２２により、Ｓ，＝ＱＩなる関係を満
足する指数表現１に変換される。ＲＯＭ２２はＲＯＭ２
０と同様な容量を有し、任意の８ビットの２進数Ａ″で
指定されるメモリアドレスに、Ａ′＝Ｑｂなる関係を有
するｂを格納しておくことによって、Ｓ，→１の変換を
実行することができる。こうして、Ｓ６１が指数表現に
変換されたｋと、同じくＳ，が指数表現に変換３れた１
とをＭＯＤ２５５加算器２１に供給してＭＯＤ２５５加
算を実行することにより‘７｝式のＳ．・Ｓ；１の指数
表現ｊ′を得ることができる。

【８｝式および■式に相当するＳ２・ＳｔｌおよびＳ３
・Ｓ夏１の指数表現ｉ″およびｊ川も全く同様にして演
算することができる。例えばｉ″を演算する場合にＳ「
１の指数表現が必要になるが、これはＲＯＭ２２で求め
たＳ，の数表現１の各ビットを、ィンバータ２３を用い
て反転すれば容易に得られる。かくしてＲＯＭ２２、イ
ンバー夕２３、ＲＯＭ２５およびＭＯＤ２５５力ｏ算器
２４を用いてＳ２，Ｓ；１の指数麦芽弘″が得られ、ま
たＲＯＭ２５、ィンバータ２６、ＲＯＭ２８およびＭＯ
Ｄ２５５力ｏ算器２７を用いてＳ３・Ｓき１の指数表現
ｉ川が得られる。かくして、回路２のクロツクを全く用
いない静的演算回路によってＳｏ〜Ｓ３から迅速確実に
‘７｝，【８｝，｛９｝式に対する指数表現ｉ′，ｊ″
およびｊＷを得ることができる。これらのシンドローム
比の指数表現に対応するＪ′，ｉ″およびｊ川は、第１
図における回路２からシンドローム比比較回路３に供給
される。また、それと共にｊ′（これはｉ″またはｉ肌
ののいずれでもよい）が訂正実行制御論理和回路６に供
給される。次に、シンドローム比比較回路３は、供給さ
れたｊ′，ｉ″およびｉ…の値がすべて一致するか否か
を検出する回路である。

これは、例えばｊ′およびｉ′′の各桁ごとの排他的論
理和をとる第１の回路と、ｉ″およびｊ川の各桁ごとの
排他的論理和をとる第２の回路と、前記第１および第２
の回路の各出力ビットのすべての（１６ビットの）論理
和否定をとる回路とを用いて容易に構成することができ
る。前記‘７｝，‘８｝，｛９）式より明かなように、
誤りが１個の場合には、上述のようにして求められた誤
りシンボル位置に相当するｉの値画′，ｉ″およびｉ…
はすべて一致する。従って、この場合には、回路３は一
致出力３００を出力し、これを訂正実行制御論理和回路
６に供給することになる。また一方、前述のようにシン
ドロームＳｏ〜Ｓ３は、シンドロームオールゼロ判定回
路４に供給される。

この回路４はＳｏ〜Ｓ３のすべての桁の各ビットのすべ
ての論理天０ととる論理和回路と、その出力を反転する
ィンバータとより構成されていて、すべてのシンドロー
ムが“０”の場合（すなわち誤りが全く無い場合）にか
ぎり“１”論理レベルを発生し、これをライン４００を
介して訂正実行制御論理和回路６に供給する。さらにま
た、シンドロームＳｏ〜Ｓ３は前述のように、シンドロ
ームゼロ検出回路５に供給される。

この回路５は、Ｓｏ〜Ｓ３の中に１個でも“０”のシン
ドロームが含まれると“１”論理レベルを発生し、これ
を訂正実行制御論理回路６に供給する。この回路５もそ
れぞれのシンドロームＳｏ，Ｓ，，Ｓ２およびＳ３の各
桁（８ビット）の論理和否定を作る４個の論理和否定回
路と前記４個の論理和否定回路出力の論理和をとる１個
の論理和回路とにより容易に構成することができる。さ
て、訂正実行制御論理回路６は、以上のようにして供給
された諸入力信号を用い、下記のような論理動作により
誤り訂正の実行を制御する。

まず、回路４の出力４００が“１”の場合、すなわち、
シンドロ−ムＳｏ〜Ｓ３がすべて“０”の場合には、他
の入力信号の如何にか）わらず誤りが無いのとして誤り
訂正を行なわない。また回路６から、下位の回路を供給
するためのエラーフラグ出力６００を“０”としてこの
符号ブロックに誤りが無いことを表示する。シンドロー
ムＳｏ〜Ｓ３がすべて“０”の場合には｛５）式の関係
よりか）る制御を行なえばよいこ．とは明らかである。
次に、回路４の出力４００が“０”の場合には次のよう
になる。

この場合には必らず誤りが存在する筈であるが、もし誤
りが１個の場合には（１｝式から｛４｝式の関係よりＳ
ｏ〜Ｓ３はすべて“０”ではない。また【九【８），ｔ
９｝式より求められるｊはすべて等しい筈である。これ
らの条件が成立したときに、‘６｝式の誤り訂正情報Ｓ
ｏを用いてｊ番目のシンボルに誤り訂正を実行するよう
に制御すればよい。すなわち、前記シンドロ−ムゼロ検
出回路５の出賄５００が“０”で、かつ、シンドローム
比比較回路３の出力３００が“１”の場合にかぎり、供
給されたｊ′で指定されるシンボル位置に、供給された
Ｓｏを誤り訂正情報として誤り訂正を実行するように制
御する。また、この場合には、エラーフラグ出力６００
を“０”としててこの符号ブロックには訂正の結果誤り
が無いことを表示する。上記の関係が成立しない場合、
すなわち少くも出力５００が“１”である（シンドロー
ムＳｏ〜Ｓ３の中のいずれかに“０”が含まれる）か、
または出力３００が“０”である（丁，ｊ″，ｊ川の値
が一致しない）の場合には■，‘７｝，■および｛９）
式の関係より誤りの数が１個であるという条件が成立し
ないことは明らかである。

従ってこの場合には訂正を行なわず、またこのブロック
中に誤りが含まれることを指示するエラーフラグ出力６
００を“１”にする。以上のような制御を行なう論理回
路は、例えば、６図に例示する回路を用いて容易に実現
できる。

但し、第６図の参照数字６０，６１および６２はそれぞ
れ論理積回路、参照数字６３，６４および６４はそれぞ
れィンバータを表わし、また参照数字１０１，３００，
４００，６００，６００および６０１の各入出力ライン
は第１図の対応する参照数字の入出力ラインと同じもの
を表わしている。さて、回路６により、以上のような制
御を受けた誤り訂正情報Ｅｊ（Ｓｏ）は出力６０１とし
て、また誤りシンボル位置情報ｉ′は出力６０２として
ま誤り訂正実行回路７に供給される。

この回路７は、データ入力１００より入力する１ブ。

ツク分のシンボル＆，，Ｂ磯・・・・・・馬をつぎつぎ
のシンボル位置に格納するバッファを有する。このよう
に格納されたシンボルの中の前記誤りシンボル位置指定
情報ｉ′により指定される位置のシンボル官ｊに対し、
供給された前記誤り訂正情報Ｅｊ（Ｓｏ）を排他的論理
和を用いて加算することにより誤り訂正を実行する。か
くして誤り訂正された後各シンボルは出力７００として
前記エアーフラグ出力６００と共に下位の回路に供給さ
れる。以上の実施例においては、説明を具体的にするた
めに、符号長Ｎとして３２、１符号ブロック中の検査用
シンボルの数Ｍとして４、さらに各シンボルのビット数
Ｋとして８で構成されるようなリード・ソロモン符号を
用いる場合について詳述したが、本発明の方式はＮ，Ｍ
およびＫの値がこれらに限られるものでないことは明ら
かである。また、使用した諸回路についての回路例も実
現するための例を示したもので、何もこれに限られるも
のではない。以上のように、本発明を用いると、Ｎシン
ボルで１個のブロックをなすりード・ソロモン符号内に
生じた１個の誤りを訂正し２シンボル以上の誤りを検出
たちエラーフラグを出す方式において、検査用シンボル
の数Ｍ個までのすべてのシンドロームの情報を有効に利
用し、かつ、簡潔な回路構成により目的を達成する信頼
性の高い復号方式を提供することができる。

これにより信頼性、経済性の向上を達成できる。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック図、第２図は
本実施例で用いる和の演算を説明するための図、第３図
１は本実施例で用いる演算の符号多項式を説明するため
の図、第３図２は本実施例で用いる積の演算を説明する
ための図、第４図は本実施例のシンドローム演算回路の
内部回路例を示す図、第５図は本実施例のシンドローム
比比較回路の回路例を示す図および第６図は本実施例の
訂正実行制御論理和回路の中の論理回路例を示す図であ
る。 図において、１・・・・・・シンドローム演算回路、２
・…・・シンドローム比演算回路、３・・・・・・シン
ドローム比比較回路、４……シンド。 ームオールゼｏ判定回路、５・…・・シンドロームゼロ
検出回路、６・・・・・・訂正実行制御論理回路、７・
・・・・・誤り訂正実行回路、１０……シフトレジスタ
、１１，２０，２２，２５，２８・・・・・・読出し専
用メモリ（ＲＯＭ）、１２・・・・・・排他的論理和回
路、２１，２４，２７・・・…２５５を法とする加算器
（ＭＯＤ２５５加算器）、２３，２６，６３，６４，６
５……インバータ、６０，６１，６２・・・・・・論理
積回路。髪′図 多２図 第４図 第３図 多Ｓ図 多６図

Claims (1)

【特許請求の範囲】
1. １ Ｍ個（但しＭは正の整数）の１次多項式の積ででき
   る生成多項式から生成される符号長Ｎ（但しＮはＭより
   も大きい正の整数）のリード・ソロモン符号を受信して
   該受信符号に対するＭ個のシンドロームＳ＿０，Ｓ＿１
   ，……，Ｓ＿Ｍ＿−＿１を演算し該シンドロームをもと
   に該受信符号内に１シンボルだけの誤りが生じているこ
   とを検出したらその誤りを訂正し２シンボル以上の誤り
   を検出したら誤り検出情報を出力する方式において、前
   記シンドロームＳ＿０，Ｓ＿１，……，Ｓ＿Ｍ＿−＿１
   よりＭ−１個のシンドローム比Ｓ＿１・Ｓ＾−＾１＿０
   ，Ｓ＿２・Ｓ＾−＾１＿１，……，Ｓ＿Ｍ＿−＿１・Ｓ
   ＾−＾１＿Ｍ＿−＿２に対応する情報を演算するシンド
   ローム比情報演算手段と、前記シンドローム比に対応す
   る情報がすべて等しいか否かを判定するシンドローム比
   情報比較手段と、前記シンドロームＳ＿０，Ｓ＿１，…
   …，Ｓ＿Ｍ＿−＿１のすべてが“０”か否かを判定する
   シンドロームオールゼロ判定手段と、前記シンドローム
   Ｓ＿０，Ｓ＿１，……，Ｓ＿Ｍ＿−＿１のうちに少くも
   １個の“０”のシンドロームが含まれるか否かを判定す
   るシンドロームゼロ検出手段と、前記シンドローム比情
   報比較手段の出力と前記シンドロームオールゼロ判定手
   段の出力と前記シンドロームゼロ検出手段の出力とに応
   答して予め定めたアルゴリズムに従つて訂正を実行すべ
   きか否かを決定し訂正を行う場合にはブロツク内の前記
   シンドローム比により定まる位置のシンボルに対し前記
   シンドロームＳ＿０を誤り訂正情報として誤り訂正を実
   行する誤り訂正手段とを含むことを特徴とするリード・
   ソロモン符号復号方式。