JPS6034136B2

JPS6034136B2 - リ−ド・ソロモン符号復号方式

Info

Publication number: JPS6034136B2
Application number: JP56164557A
Authority: JP
Inventors: 勝洋中村; 行弘岡田
Original assignee: NEC Home Electronics Ltd; Nippon Electric Co Ltd
Current assignee: NEC Home Electronics Ltd; NEC Corp
Priority date: 1981-10-15
Filing date: 1981-10-15
Publication date: 1985-08-07
Also published as: JPS5866159A

Description

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

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

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

この符号は、巡回符号の一種であるためにその符号化に
関しては、よう知られた巡回符号の符号器を用いて比較
的簡単に実現できるが、その復号に関しては一般的な従
来の方法を用いると装置が非常に複雑になるという欠点
を有している。

本発明の目的は従来のこのような欠点を除去するにある
。本発明の方式は、Ｍ個（但しＭは正の整数）の１次多
項式の積でできる生成多項式から生成される符号長Ｎ（
但しＮはＭよりも大きい正の整数）のりード・ソロモン
符号を受信して該受信符号に対するＭ個のシンドローム
Ｓｏ，Ｓ，，・・・・・・ＳＭ‐，を演算し該シンドロ
ームをもとに該受信符号内の予め指定されたｍ個（但し
ｍはＭ以下の正の整数）のシンボル位置ｉ，，ｉ２，・
・・・・・ｉｍにおける受信シンボルが誤っていれば訂
正する方式であって、前記シンドロームＳｏ，Ｓ，，・
・…・ＳＭ‐，および前記シンボル位置ｉ，より予め設
定された演算によって定まるＭ−１個の第１中間情報を
演算しかっこれらの各各が“０”か否かを判定する第１
演算手段と、前記第１中間情報を利用しこの情報と前記
シンボル位置ｉ２より予め設定された演算によって定ま
るＭ−２個の第２中間情報を演算しこれらの各各が“０
”か否かを判定する第２演算手段と、以下同様にして次
次に進み第ｍ−２中間情報を利用しこの情報と前記シン
ボル位置ｉｍ−，より予め設定された演算によって定ま
るＭ−ｍ十１個の第ｍ−１中間情報を演算しこれが“０
”か否かを判定する第ｍ−１演算手段と、さらにｍがＭ
よりも小さいときは前記第ｍ−１中間情報と前記シンボ
ル位置ｉｍより予め設定された演算によって定まるＭ−
ｍ個のｍ中間情報を演算しこれが“０”か否かを判定す
る第ｍ演算手段までを含む次次の演算手段と、前記第１
乃至第ｍ−１または第ｍ中間情報と前記シンドロームＳ
ｏと前記シンボル位置ｉ，，ｉ２，・・・・・・ｉｍと
を利用して前記指定された各シンボル位置ｉ，，ｉ２，
・・…・ｉｍに対する誤り訂正に使用すべき訂正情報を
演算し前記各中間情報中に含まれる前記“０”の情況に
応答して前記訂正情報による誤り訂正の実行を制御する
手段とを含む。

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

第１図は本発明の一実施例を示すブロック図である。こ
の実施例はシンドローム演算回路１、エラーフラグ数計
数回路２、誤りシンボル位置生成回路３、第１中間情報
Ｍ，演算回路４、Ｍ，“０“判定回路４′、第１中間情
報Ｍ２演算回路５、Ｍ２“０“判定回路５′、第１中間
情報Ｍ３演算回路６、Ｍ３“０“判定回路６′、第２中
間情報Ｐ，演算回路７、Ｐ，“０“判定回路７′、第２
中間情報Ｐ２演算回路８、Ｐ２“０“判定回路８′、第
３中間情報Ｑ，演算回路９、Ｑ，“０“判定回路９′誤
り訂正情報ＥＩ演算回路１０、誤り訂正情報Ｅｋ演算回
路１１、誤り訂正情報Ｅｊ演算回路１２、誤り訂正情報
Ｅｉ演算回路１３、誤り訂正実行制御論理回路１４、誤
り訂正実行回路１５を有している。本実施例では指定さ
れた４個までのシンボル位置ｉ，ｊ，ｋおよび１におい
て誤りがあればその誤りを訂正するりード・ソロモン復
号方式につき詳述することにする。さて、デーダ入力ラ
イン１０川こは、各シンボルが１バイトの“１”“０”
符号で構成され、Ｎシンボルを１ブロック長とする、リ
ード・ソロモン謀り訂正符号によって符号化された陳情
報がそのまま、もしくは誤りを伴なつて入力されるもの
とする。

そして、あるシンボルに誤りがある可能性が強い場合に
はそのシンボルが入力される時点で、そのシンボルに対
応して、エラーフラグ入力３０川こエラーフラグが入力
される。但し、ヱフーフラグ入力３００にエラーフラグ
が入力されても対応する入力シンボルに必らずしも誤り
があるとはかぎらないものとする。今、受信する１ブロ
ック内の各シンボルそれぞれＢ，Ｂ，・・・・・・ＢＮ
‐，で表わす。

これらの各シンボルは、誤り訂正符号化されてまだ誤り
を含んでいない時点においては、それぞれＢｏ，Ｂ，＆
，……ＢＮ‐，の値をもつものとする。従って、ある１
つのの受信ブロック中の、任意の４個の受信シンボル翁
，亘ｊ，翰ｋ，およびＢＩもこ対する誤りシンボルをそ
れぞれＥｉ，Ｅｉ．ＥｋおよびＥＩとすると、という関
係がある。但し、十は各シンボルを構成するビット対応
ごとの２を法とした加算を表わす。一方、前記＆，Ｂ，
Ｂ２・…・・ＢＮ‐，は、４個までの誤り訂正を可能と
させるためにＢｏ，Ｂ，Ｂ２および＆の４個の検査シン
ボルを含み、これにより、原信号を生成したりード・ソ
ロモン符号化回路において、を満足するように符号化さ
れているものとするのこついては後述する。

さて、第１図のブロック図に従って回路動作説明をさら
に進める前に誤り訂正符号を処理する際に用いられる演
算について先に説明する。

本実施例は、前述の通り、８ビットからなるシンボルが
複数個よりなる答号ブ。ックで構成さるリード・ソロモ
ン符号を復号するものとする。従って、各シンボルは夕
＝２５針固の中の１つの元を表わしている。この２５６
個の中の任意の元Ａ′とＢ′との加算および乗算は次の
ように定義される。加算：第２図に示すように、元Ａ′
およびＢ′を符号ベクトルの形で表示し、各桁（各次元
）ごとの排他的論理和つまり２を法とする和をとった結
果生ずる符号ベクトルをＡ＋Ｂと定義する。

乗算：例えば第３図（１｝に示すような元Ａ′および元
８があると、これをｘの多項式表現Ａ′＝１十×２十〆
十×５Ｂ′＝ｘ２十でとし、この多項式の積ＡＢをＡＢ：（１十×２十ゞ十ゞ）（ｘ２十×４）ニＸ２十（
ぞ十×４）十×５十で十（Ｘ７十×７）十×９のように作る。

この中でｘの同じ寮秦の項は、符号ベクトルの同じ桁（
次元）に対応するので、上述の２を法とする加算の規則
を適用して整理すると上式は・Ａ′Ｂ＝ｘ９十ゞ十ゞ十
×２となる。

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

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

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

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

以上のように８次の既約多項式ｆ（ｘ）を指定すると、
それに応じて２５６個の各元の間で、加算および乗算が
定義され、それらの逆算を含む４則演算が２５餅固の元
の中で矛盾なく行なわれる。

さて、前記既約多項式ｆ（ｘ）を適当に選ぶことにより
、前記２５針固の元の中の“０”（ベクトル表現したと
きに８ビットのすべての桁の分が“０”の元）を除く２
５９固のすべての元を、その中のある１つの元のＱの累
乗の形で表わすことができる。すなわち、１を単位元と
し、これにつぎつぎにＱを乗ずることによって生ずる元
、Ｑ，Ｑ，Ｑ３，・・・……，Ｑ２５５は前記“０”を
除くすべての元を一巡してＱ２５５で再び単位元１に戻
るようにすることができる。実際に、前記既約多項式ｆ
（ｘ）として、ｆ（ｘ）＝ず十ず十×３十×十１を用い、Ｑとして多項式表現のｘを用いると、２５５の
すべての元はＱｊ（但しｉ＝０，１，２，……，２５５
）として表わすことができる。

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

さて情報伝達のために８ビットのシンボルをＮ個集めて
１つの単位の符号ブロックとする。

このときこの１符号ブロックの中に情報伝達用のシンボ
ルの外に、この情報伝達用シンボルと特定の演算関係を
もつ検査用シンボルをＭ個加え、残りのＮ−Ｍ個を実際
の情報伝達用シンボルとして利用する。１例として、Ｎ
＝３２，Ｍ＝４とすると、１符号ブロック内の前記情報
伝達用シンボル数は２８個となる。

これをへ，Ａ５……Ａ３，とする。次にこれに対して特
定の演算関係を満足する４個の検査用シンボルん，Ａ，
，Ａ２，Ａ３を作り、これを前記情報伝達用シンボルに
付加し、全体してＡｏ，Ａ．，Ａ２，・・・・・・，Ａ
３，の３２個のシンボルをもつ１単位の符号ブロックを
構成する。この、２８個の情報伝達用シンボルＡ４〜Ａ
３．から検査用シンボルＡｏ〜Ａ３を生成するには、い
わゆる生成多項式ｇ（ｘ）が用いられる。

４個の１次の多項式の積でできる生成多項式ｇ（ｘ）＝
（ｘ−１）（ｘ−Ｑ）（Ｘ−Ｑ２）（Ｘ一Ｑ３）をとり、これにより検査用シンボルＡｏ〜Ａ３を生成す
るとする。

すなわち任意の情報伝達用シンボル群へ〜Ａ３，を符号
多項式Ｃ（ｘ）＝んｘ４十Ａ５で十……十Ａ３，ｘ３１
の形で表わし、これを前記生成多項式ｇ（ｘ）で割ると
一般に剰余が生ずるが、これはｘの３次以下の多項式と
なるため、この剰余をＲ（ｘ）とするとＲ（ｘ）＝ａ。

十ａ，ｘ＋ａ２×２十ａ３×３で表わせる。本実施例の
リード・ソロモン符号は、かくして得られるも，ａ，，
ａ２およびａ３を、それぞれ検査用シンボルＡｏ，Ａ，
，Ａ２およびＡ３として用いるものである。

従って、１符号ブロック全体の多項式表現はん十Ａ，ｘ
＋Ａが２十……十ふ，ず１＝Ｒ（ｘ）十Ｃ（ｘ）となる。

ところがＲ（ｘ）はＣ（ｘ）をｇ（ｘ）で割った剰余で
あり、従って、前記Ｒ（ｘ）＋Ｃ（ｘ）はｇ（ｘ）で割
りきれることになる。この結果、その商をＫ（ｘ）とす
ると、ん十Ａ，ｘ＋Ａが２十……ん，ゞ１＝Ｋ（ｘ）（ｘ一１）（ｘ−Ｑ）（ｘ−Ｑ２）（Ｘ−以
３）が成立する。

ついで、ｘの値としてそれぞれ１，Ｑ，Ｑ２およびＱ
３代入することにより以下の４式がそれぞれ導かれる。
へ＋Ａ，十Ａ２………十Ａ３，＝０ん十ＱＡ，十Ｑ２Ａ２十……十ＱのＡ３，＝０ん十Ｑ２
Ａ，十ｏ４Ａ２十……十Ｑ６２Ａ３，＝０ん十ｏ３Ａ，
十Ｑ亭Ａ３十……十Ｑ９３Ａ３，＝０前記【２｝式は符
号長にＮを用いて全く同様にして導かれたものである。

なお生成多項式ｇ（ｘ）が与えられると、上述の割算を
実行して実際にへ〜んを生成する巡回符号の符号器の構
成を決定することも容易であるがここでは省略する。さ
て前述の■式のようにして、送信側で生成された信号ブ
ロックを受信側で受信し、受信したブロックに対して‘
２）式の左辺に相当する演算を実行すると、もし受信に
誤りがなければ送信側と同じにすべて“０”になる筈で
ある。

もし受信に誤りがあると■式の各左辺に相当する演算結
果は一般に“０”でないそれぞれ値Ｓｏ，Ｓ，，Ｓ２，
Ｓ３をとることになる。これをシンドロームという。本
実施例は、このシンドロームＳｏ〜Ｓ３を用い、送信側
で−ブロック内のシンボル間に加えた（２ー式の拘束演
算関係から誤り分を求めてこれを訂正する方式で０ある
。従って、以下における種種の演算は前述のＱｉ（ｉ＝
０〜２５５）で表示できる２５５個の元およびそれに“
０”を追加した全部で２５針固の元の間で行なわれる前
述した定義に従う演算であることを断わっておく。さて
、今データ入力からのある１つの符号ブロックを受信し
、シンドローム演算回路１におし、で指定される演算を
行ない、シンドロームＳｏ，Ｓ，，Ｓ２およびＳ３が求
められたとする。

一方、エラーフラグ入力３００により、Ｂｉ，Ｂｉ，Ｂ
ｋおよびＢＩの４個のシンボルに対してのみエラーフラ
グが受信され、他のシンボルにはエラーフラグが受信さ
れなかった仮定する。つまり少くもＢｉ，Ｂｊ，Ｂｋお
よびＢＩ以外には誤りを含んでいないと仮定する。そう
すると、【１｝式■式および糊式の関係より、が導かれ
る。

これを行列を用いて表わすととなる。

従って、で定義される行列Ｘの逆行列Ｘ‐１を求め、こ
れを‘５）式の両辺の左側から乗ずることによりＥｉ，
Ｅｉ，ＥｋおよびＥＩを求めることができて、これらは
それぞれ下記のようになる。

訂正情報、Ｅ１，Ｅｋ，ＥｉおよびＥｉを求めるには、
これらの演算を実行する回路を実現しなければならない
。

しかしながら、｛７）式で指定されるＥ１，Ｅｋ，Ｅｉ
およびＥｉはお互いがそれぞれ異なる項の結合でできて
おり、通に使用できる項を殆んど含んでいない。

そのためにこれらの演算をそのまま実行する回路を実現
しようとすると非常に複雑になるという欠点がある。本
実施例においてはこれを以下に述べるようにして改善し
ている。

表示を簡単にするためにＱＪ三Ａ，Ｑｉ三Ｂ，ＱｋＥＣ，ＱＩ…Ｄ ……｛
８）と書くとまずの式からＥ，＝ＡＢＣＳ。

十（ＡＢ＋ＡＣ＋ＢＢＣ）Ｓ，十（Ａ＋Ｂ＋Ｃ）Ｓ２十
Ｓ３（Ａ十Ｄ）伍十Ｄ）（Ｃ十Ｄ）と表示できる。

つぎに、ＥｋをＥＩを用いて表示するために‘４｝式か
ら次式を導く。これを行列で表わすと、ここで、行列Ｙをで定義し、この逆行列Ｙ−１を求め、これを（１１）式
の両辺の左側から乗ずることによりＥｊ，Ｅｊ，Ｅｋが
求められるが、この中でＥｋはＥｋ＝（Ａ＋Ｄ）（Ｂ＋
Ｄ）ＥＩ＋Ａ既ｏ＋（Ａ＋ＢＳ，十Ｓ２（Ｂ＋Ｃ）（Ａ
＋Ｃ）となる。

次に同様にして、ＥｉをＥＩおよびＥｋを用いて表示す
るために、肌式の最初の２つの式からを導き、さらに、
これを行列を用いてと水、打Ｚで定義し、この逆行列Ｚ‐１を求めこれを（１５）式の
両辺の左側から乗ずることによりＥｉ，Ｅｊが求められ
るが、この中でＥｊはＥｊ＝（Ａ＋Ｃ）Ｅｋ＋（Ａ＋Ｄ
）ＥＩ＋ＡＳ。

十Ｓ，
．．．．．．（１７）Ａ＋Ｂとなる。

最後にＥｉは（１４）式の最初の式を用いてＥｉ＝Ｅｉ
＋Ｅｋ十ＥＩ＋Ｓ。

……（１８）と表わすことができる。以
上の側，（１３），（１７）および（１８）式で求めら
れたＥ１，Ｅｋ，ＥｉおよびＥｉを少し変形して整理す
ると次のようになる。

Ｅｉ＝Ｅｉ＋Ｅｋ＋ＥＩ＋Ｓ。

（１９）Ｅｊ＝（Ａ＋ｃ）Ｅｋ＋（Ａ
＋Ｄ）ＥＩ＋（ＡＳ。十Ｓ，）
・・・・・・（２０）Ａ＋ＢＥ
ｋ＝（Ａ＋Ｄ）（Ｂ＋Ｄ）Ｅー十Ｂ（Ａｓ。

十Ｓ，）＋（ＡＳ，十Ｓ２）
・・・・・・（２１）（Ｂ＋Ｃ）（Ａ
＋Ｃ）Ｅ，＝Ｃ｛Ｂ（ＡＳ。

十Ｓ，）＋（ＡＳ，十Ｓ２）｝十皮ＡＳ，十Ｓ２）十
（ＡＳ２十Ｓ３）．．，．
．．（２２）（Ａ＋Ｄ）（Ｂ＋Ｄ）（Ｃ＋Ｄ）以上の（
１９），（２０），（２１）および（２２）式で表示さ
れるＥｉ，Ｅｊ，ＥｋおよびＥＩのすぐれている点は、
Ｅ１，Ｅｋ，ＥｊおよびＥｉの順序で演算すると、先に
演算した中間結果が次の演算に繰り返し用いることがで
きるためハードウェアが大中に簡単化できるという点で
ある。

これを更に明らかにするために、シンドロームＳｏ，Ｓ
，，Ｓ２およびＳ３とシンボル位置ｉとより定まる３個
の第１の中間演算結果をそれぞれＭＩ己ＡＳ。

十ＳＩ…ＱｉＳ。十ＳＩ …，．，（２３）地
…ＡＳ，十Ｓ２…ＱｉＳ，十Ｓ２ …・・・
（２４）Ｍ３三ＡＳ２十Ｓ３三ＱｉＳ２十Ｓ３
・・・・・・（２５）で定義する。次に上のの第１の
中間演算結果を利用し、この結果と前記シンボル位置ｉ
より定まる２個の第２の中間演算結果をそれぞれＰ，…
ＱｊＭ，十Ｍ２ ……（２６）Ｐ
２…ＱｊＭ２十Ｍ３ ……（２７）
で定義する。

最後に、上の第２の中間演算結果を利用し、この結果と
シンボル位置ｋより定まる１個の第３の中間演算結果を
Ｑ，三ＱｋＰ，十Ｐ２ …・・・
（２８）で定義する。

こうすると指定されたシンボル位置ｉ，ｊ，ｋおよび１
に対する誤り訂正に使用すべき誤り訂正情報Ｅｉ，Ｅｉ
，ＥｋおよびＥＩは、この第１乃至第３の中間演算結果
と前記シンドロームＳｏと前記シンボル位置ｉ，ｉ，ｋ
および１を用いて次のように演算できる。

ＥＩ＝（Ｑｉ＋Ｑ．）（Ｑｊ葦で）（Ｑｋ＋で） ……
（２９）Ｅｋ＝（Ｑｉ＋ＱＩ）（Ｑｊ＋ＱＩ）ＥＩ十Ｐ
． ……（３０）（ＱＪ＋Ｑｋ）（Ｑｉ＋Ｑｋ）
Ｅｊ＝（Ｑｉ＋Ｑｋ）Ｅｋ＋（Ｑｉ＋ＱＩ）ＥＩ＋Ｍ，
……（３，）（ｏｉ＋でＥｉ＝Ｅｉ＋Ｅｋ十ＥＩ＋
Ｓ。

・・・・・・（３２）このような演算
方式をとることによりＥＩを得るために必要としたＭ，
十Ｍ２十Ｍ３の各項をくりかえして用い、またさきに求
めた未知量をあとの未知量を求めるのに利用するとがで
き、この結果｛７ー式を用いてＥＩ〜Ｅｉを演算するよ
りも遥かに簡単なハードウェアでこの演算を実現すると
ができる。さて、以上の説明はエラーフラグの数が４の
場合についてであるが、もしブロック中に受信されるエ
ラーフラグの数が４と異なる場合には次のようになる。

〔エラーフラグの数が３の場合〕一般性を失なうことなくｉ＞ｉ＞ｋ＞１とすればこの場
合にははじめから３番目まで、すなわちｉ，ｊ，ｋまで
指定されて定まり、１は事実上指定されない。

しかしながら実際の回路上では、回路３内の対応するレ
ジス外こ現在残っている値をそのまま１として用いてい
る。従って、Ｅｉ，Ｅｉ，Ｅｋまでの誤りだけが存在し
得てＥＩは０の筈である。またＱＩという量は意味がな
いのでＱＩを含む式をそのまま用いると誤りを招くおそ
れがある。（２９）式のＥＩによると分母にはＱＩを含
むが分子のＱ，には（２３），（２４），（２５），（
２６），（２７）および（２８）式から明らかなように
ＱＩを含まない。もし正しい演算が行なわれている場合
にはＱ．が“０”になる筈である。従って、エラーフラ
グ数が３の場合には、Ｑ，が“０”か否かを判定し、も
しＱ，が“０”の場合にはＥＩを強制的に３“０”にす
ればよい。こうするととなりＱＩを含まない正しい３個
の訂正値を求めることができる（勿論Ｅｋ，Ｅｉ，Ｅｉ
の中に“０”があっても構わない）。

従って、Ｑ，が“０”の場合には、こうして（３３）式
で求められたＥｉ，ＥｊおよびＥｋを３個のエラーフラ
グで指定されるシンボル位置に対する訂正情報とする。
またもしＱ，が“０”でない場合には訂正を行なわない
。〔エラーフラグの数が２の場合〕この場合にはＥＩお
よびＥｋの値が０の筈でありまたＱＩおよびＱｋの値に
は意味がない。

ＥＩ＝０よりＱ，が“０”になる筈であるが、Ｑ，はＱ
ｋを含むのでこれを直接判定に用いることはできない。
こでＱＩおよびＱｋを含まない。Ｐ，およびＰ２が“０
”か否かを判定する。ＥＩおよびＥｋがともに“０”の
場にはＰ，およびＰ２がともに“０”である（この場合
Ｑ，も“０”になる）。従って、エラーフラグの数が２
の場合にはＰ，およびＰ２が“０”か否かを判定し、も
し共に“０’’であればＥＩおよびＥｋの値を強制的に
“０”にするととなり、ＱＩおよびＱｋを含まない正し
い２個の訂正値を求めることができ、これをエラーフラ
グで指定されるシンボル位値に対する訂正情報とする。

もしＰ，＝“０”かつＰ２＝“０”でない場合には訂正
を行なわない。〔エラーフラグの数が１の場合〕この場
合には、Ｅ１，ＥｋおよびＥｉが“０”で、Ｑ１，Ｑｋ
およびＱｊには意味がない。

従ってＱｊ，ＱＩおよびＱｋを含まないＭ，，Ｍ２およ
びＭ３が“０”か否かを判定し、これらがすべて“０”
である場合にかぎりＥ１，Ｅｋ，Ｅｉを強制的に“０”
にしてＥｉ＝Ｓ。

・・・・・・（３５）より
正しい訂正値を求めることができる。これをェラ−フラ
グで指定されるシンボル位置に対する訂正情報とする。
もし、Ｍ，＝“０”，Ｍ２＝“０”かつＭ３＝“０”の
条件が成立しない場合には訂正を行なわない。〔エラー
フラグの数が０の場合〕Ｓ。

＝‘‘０’’，Ｓ，＝“０’’，Ｓ２＝‘‘０”，Ｓ３
＝“０”となる筈である。この場合に訂正は行なわない
。なおエラーフラグの数が０の場合には、Ｓｏ〜Ｓ３が
すべて“０”になる確認はしなくても受信データをその
ままの形で外部に出してもよい。〔エラーフラグの数が
５またはそれ以上の場合〕訂正は行なわない。以上述べ
たように、エラーフラグの数が１〜３の場合には、それ
ぞれの場合に応じて前記各中間演算結果のＭ，，地，Ｍ
３，Ｐ，，Ｐ２およびＱ・が“０”か否かを判定し、そ
れらの結果を用いることが必要となる。

さて次に、以上の説明を基として第１図のブロック図に
よる本実施例の動作の説明に戻る。

回路１は、データ入力１００より｛３ー式で指定された
演算を行い、シンドロームＳｏ，Ｓ，，Ｓ２およびＳ３
を求めてこれらを回路４，５，６および１３に供給する
。一方、回路３は受信ブロックのはじめでＮ−１の値に
プリセットされるカウンタを含んでいて、この力ウンタ
は入力されるシフトパルス２００１こよって１つづっダ
ウンカウントされる。

ある時点でエラーフラグ３００が入力すると、その時点
のカゥン夕の値が内部のレジス夕に登録され、かくして
訂正すべきシンボルの位置が４個まで内部のレジス外こ
登録される。この値は入った順序に従ってｉ，ｊ，ｋ，
１で指定することにする。従って１＞ｊ＞ｋ＞１となっ
ている。このｉ〜１の値は訂正回路１５に供給されて、
訂正すべきシンボルの位置を指定するのに使用される。
一方、また、これらｊ〜１の値は前記中間情報Ｍ，，地
，Ｍ３，Ｐ，，Ｐ２，Ｑ，ならびに誤りシンボルＥｉ，
Ｅｋ，，ＥＩを求める各回路へも供給される。一方、エ
ラーフラグ入力３００とシフトクロック２０川ま、エラ
ーフラグ数計数回路２にも供給され、ここで１ブロック
内に入力したエラーフラグの数が数えられる。

回路１，２および３は、いずれも各データブロックの入
力開始に先立ってまずリセットされ、１っのブロックの
入力が終了した時点で正しいそれぞれの出力を与えるこ
とになる。従って、以下の回路はこの時点で正しい値の
演算を行なうことにある。なお、以上の説明から、例え
ば、エラーフラグの数が２の場合には、ｉ，ｊまでが実
際に登録されたエラーフラグの位置の値で、ｋ，１した
がってＱｋおよびＱＩが全く無意味な値であることが明
らかであろう。従ってエラーフラグの数に応じて前述し
た異なる制御を行なうため、回路２の出力は回路１４に
供給されている。さて、回路４は、前記回路３からｉの
、回路ＩからＳｏおよびＳ，の供給を受け、これを後述
するＲＯＭとＭＯＤ２５５加算器と排他的論理和回路で
構成される演算回路によって前記（２３）式に示す第１
の中間情報Ｍ，を演算し、同時に回路４′において、こ
うして得られたＭ，が“０”か否かの判定を行なう。

回路４の出力は回路７および回路１２に供給され、次の
演算に使用される。また回路４′の出力は回路１４に供
給され訂正実行の制御に利用される。全く同様にして、
回路５，５′で前記（２４）式で示す第１中間情報Ｍ２
が演算され、このＭ２が“０”か否かが判定され、また
回路６，６′で前記（２５）式で示す第１中間情報Ｍ３
が演算され、このＭ３が“０”か否かが判定される。

回路５からの出力Ｍ２は回路７および回路８へ、回路６
からの出力Ｍ３は回路８にそれぞれ供給され、また回路
５′および６′の“０”判定出力はともに回路１４に供
給される。つぎに回路７では、供給された前記誤り位置
ｉ第１中間情報Ｍ，およびＭ２より前記（２６）式で示
す第２中間情報Ｐ，を演算し、同時に回路７′ではこの
Ｐ，が“０”か否かを定する。

回路７の出力Ｐ，は回路９および回路１１に供給され、
回路７′の出力は回路１４に供給される。全く同様にし
て回路８は供給された前記訂り位置ｊ、第１中間情報地
およびＭ３より前記（２７）に示す第２中間情報Ｐ２を
演算し、同時に回路８′でこのＰ２が“０”か否かを判
定する。回路８の出力Ｐ２は回路９に供給され回路８′
の出力は回路１４に供給される。回路９は供給された前
記誤り位置ｉおよび第２中間情報Ｐ，およびＰ２を用い
て前記（２８）式に示す第３中間情報Ｑ，を演算し、同
時に回路９′がＱ，が“０”か否かを判定する。回路９
の出力Ｑ，は回路１川こ供給され回路９′の出力は回路
１４に供給される。さて、回路１川ま、誤り位置ｉ，ｉ
，ｋ，１および第３中間情報Ｑ，の供給を受けて、前記
（２９）式に示すＥＩの演算を行なう。

ＥＩは１の位置のシンボルを訂正すべき誤り訂正情報で
あり、回路１４を介して回路１５に供給される。また、
このＥＩは回路１４を介して回路１１，１２、および１
３に供給される。回路１０の出力ＥＩが回路１４を介し
て下位の回路１１，１２および１３に加えられるのは、
エラーフラグの数が４よりも少ない場合にＥＩの出力を
強制的に“０”にするためのものである。次に、回路１
１は供給された前記誤り位置ｉ，ｊ，ｋ，１と前記誤り
訂正情報ＥＩおよび前記第２中間情報Ｐ，より前記（３
０）式に示すＥｋの演算を行なう。

Ｅｋはｋの位置のシンボルを訂正すべき誤り訂正情報で
あり、回路１４を介して回路１５に供給される。またこ
のＥｋはＥＩと同様に回路１４を介して下位の回路１２
および１３に供給され、エラーフラグの数が３よりも少
ない場合には強制的に“０”にされるようになっている
。同様に、回路１２は供給された誤り位置ｉ，ｊ，ｋ，
１前記誤り訂正情報Ｅｋ，ＥＩおよび第１中間情報Ｍ．
より（３１）式に示すＥｉの演算を行なう。Ｅｉはｊの
位置のシンボルを訂正すべき誤り訂正情報であり、回路
１４を介して回路１５に供給さる。また、このＥｉはＥ
１，Ｅｋ同様に回路１４を介して下位の回路１３に供給
されエラーフラグの数が２よりも少ない場合には強制的
に０にできるようになっている。最後に、回路１３は、
供給された前記誤り訂正情報Ｅｊ，Ｅｋ，ＥＩおよびシ
ンドロームＳｏを用いて（３２）式に示すＥｉの演算を
行なう。

Ｅｉはｉの位置のシンボルを訂正すべき誤り訂正情報で
あり、回路１４を介して回路１５に供給される。さて、
回路１４はエラーフラグの数（以後Ｎｅｆ）と、第１中
間情報Ｍ，，Ｍ２，Ｍ３、第２中間情報Ｐ，，Ｐ２、お
よび第３中間情報Ｑ，の“０”判定結果の供給を受け、
これを制御入力情報として、前記誤り訂正情報Ｅ１，Ｅ
ｋ，ＥｊおよびＥｉの他回路への供給を制御する回路で
ある。

この制御は下記の如きものである。回路２から供給され
るエラーフラグ数Ｎｅｆが５または５以上の場合には、
回路１４から回路１５へ出力されるＥ１，Ｅｋ，Ｅｉお
よびＥｉをすべて“０”とする。

このとき、このデータに誤、りの可能性のあることを明
示するためのエラーフラグ出力１４０を“１”とする。
エラーフラグ数入力Ｎｅｆが４の場合には、各“０”判
定入力とは無関係に、供給されたＥ１，Ｅｋ．Ｅｉおよ
びＥｉをそのま）外部回路に出力する。

エラーフラグ出力１４０を“０”とする。エラーフラグ
数入力Ｎｅｆが３の場合にはＱ．の“０”判定結果に応
じて、“０”の場合にはＥＩの外部回路への出力を強制
的に“０”とし、他のＥｋ，ＥｊおよびＥｉについては
そのまま外部回路へ出力する。

エラーフラグ出力１４０を‘‘０”とする。Ｑ，の“０
”判定結果が“０”でない場合には、回路１４から回路
１５へ出力されるＥ１，Ｅｋ，ＥｉおよびＥｉをすべて
“０”として訂正を行なわず、エラーフラグ出力１４０
を“１”とする。エラーフラグ数入力Ｎｅｆが２の場合
には、Ｐ，およびＰ２の“０”判定結果に応じて、これ
らが共に“０”の場合にはＥＩおよびＥｋの外部回路へ
の出力を強制的に“０”とし、他のＥｊおよびＥｉにつ
いては、そのまま外部回路へ出力する。

エラーフラグ出力１４０を“０”とする。Ｐ，およびＰ
２の０判定結果が上と異なる場合には回路１４から回路
１５へ出力されるＥ１，Ｅｋ，ＥｊおよびＥｉをすべて
“０”として訂正を行なわず、またエラーフラグ出力１
４０を“１”とする。エラーフラグ数入力Ｎｅｆが１の
場合には、Ｍ，，地およびＭ３の“０”判定結果に応じ
、これらが共にすべて“０”の場合にはＥ１，Ｅｋおよ
びＥｊの外部回路への出力を強制的に“０”とし、他の
Ｅｊについてはそのまま外部回路へ出力する。

またェラ−フラグ出力１４０を“０”とする。Ｍ，，Ｍ
２および地の“０”判定結果が上と異なる場合には回路
１４から回路１５へ出力されるＥ１，Ｅｋ，Ｅｉおよび
Ｅｉをすべて“０”として訂正を行なわずエラーフラグ
出力１４０を“１”とする。エラーフラグ数入力Ｎｅｆ
が０の場合にはＥ１，Ｅｋ，ＥｉおよびＥＩの外部回路
への出力を強制的に“０”として訂正を行なずまたエラ
ーフラグ出力１４０を“０”とする。

回路１４は以上の動作を行なう回路であるが、これは静
的な論理素子を組み合せることによって従来の技術で容
易に実現できる。

回路１５は入力データシンボルＢｎ，Ｂｎ‐，一ＢＢｏ
を１ブロック分だけつぎつぎに格納するバッファを有し
、こうして格納された入力データシンボルに対し前述の
回路３から供給される誤りシンボル位置指定情報ｉ，ｉ
，ｋ，１によって指定される４つのシンボル位置にある
データに対し、それぞれ供給された４つの誤り訂正情報
Ｅｉ，Ｅｉ，ＥｋおよびＥＩを排他的論理和による結合
を用し、て訂正し、訂正されたデータを逐次読み出して
出力１５０とする。

次に、以上で用いた諸回路の中の回路１の内部回路例を
第４図に示す。

これは８ビットからなる１段のシフトレジスタ１０１、
読み出し専用メモリ（ＲＯＭ）１０２、および排他的論
理和回路１０３から成っている。シフレレジスタ１０１
および回路１０３は、それぞれ８ビットを並列に処理す
る。またＲＯＭＩ０２はシフレレジスタ１０１の出力の
８ビットでアドレス指定のできる２５６のメモリアドレ
スを有し、各メモリアドレス当り８ビットのデータを格
納できる容量を有する。シフレレジスタ１０１の出力に
よりＲＯＭＩ０２の指定されたメモリアドレスからデー
タが読み出され、回路１０３により入力データとの排他
的論理和がとられ、これがシフレレジスタ１０１に読み
込まれる。任意の８ビットの２進数Ａ″で指定されるＲ
ＯＭＩ０２のメモリアドレスにはＱＡ″（但し第２中間
情報Ｐ２演算回路８Ａ″はこの２進数に対応する符号ベ
クトルＡ′′と原始元ひとの積とする）を書き込んでい
〈とＲＯＭＩ０２はＱ倍の乗算器として動作する。かく
て、最初にシフレレジス夕１０１をリセットし、入力デ
ータをＢＮ‐，，ＢＮ‐２，・…・・，Ｂ，馬の順序で
次々に回路１０３を介して入力すると、Ｂｏが入力され
た時点でシフレレジスタ１０１の内容はＳ．：ＱＮ−・
亘Ｎ−．十ＱＮ−２官Ｎ−２十．．．‐‐．十ＱＢ，十
Ｂ。となりシンドロームＳ，が得られる。

ＲＯＭＩ０２の内容を上述のＱのかわりにＱ２およびは
３に相当するものとすることにより同様な回路を用いて
それぞれシンドロームＳ２およびＳ３を演算する回路が
得られ、またＲＯＭを除きシフレレジスタ１０１の内容
をそのまま回路１０３にフィードブツクすることによっ
てシンドロームＳｏを演算する回路が得られるのでこれ
らを用いて回路１が容易に実現できる。次に、第５図に
回路４の詳細例を示す。

ｉはｉ番目の符号誤りの位置を示す８ビットの２進数と
して、ＳｏおよびＳ，は共に８ビットの符号ベクトルの
形で供給される。まずＳｏは読出し専用メモリＲＯＭ４
０１により指数表現の２進数に変換される。すなわち、
任意のベクトル表現Ｓｏは０を除いて常にＳｏ＝ＱＳｏ
と表わせる（つまりＳｏが与えられるとＳ。が定るが
、ＲＯＭ４０１はアドレスｏにデータＳｏを格納して
おくこゆにぐりＳｏ→Ｓｏの変換を行なう。なおＳｏが
“０”の場合には“０”判定回路４００を介して演算が
バイパスされる。こうして誤り位置およびシンドローム
ＳｏのＱの指数表現としてのｉおよびＳｏは、２５５を
法として加算するＭＯＤ２５５力ｏ算器４０２において
加算され、その出力は読出し専用メモリＲＯＭ４０３に
よりベクトル表現に変換される。ＲＯＭ４０３は任意の
８ビットのデータＡ″に対し、メモリアドレスＡ′にＱ
Ａ″＝Ｂ″で指定される符号ベクトルＢ′′を格納する
ことにより、指数表現Ａ′′から符号ベクトル表現Ｂ″
への変換を行なう。以上の処理により、ＲＯＭ４０３の
出力には、Ｓｏが０の場合を除きばｉＳｏの符号ベクト
ル表現の出力が得られる。Ｓｏが“０”の場合には、前
記回路４００の出力がゲート４０４に供給されＲＯＭ４
０３の出力を“０”とする。ゲート４０４の出力は排他
的論理和回路４０５でベクトル表現のＳ，と合成され、
かくてベクトル表現の出力としてＭ，＝ＱｉＳ。

十Ｓ，が得られる。

全く同様な方法により回路５〜１３も容易に実現するこ
とができる。

なお、例えば回路１０において（２９）式のＥＩを演算
するために（Ｑｉ＋ＱＩ）（Ｑｊ＋ＱＩ）（Ｑｋ＋ＱＩ
）の逆数の指数表現値を求める必要があるが、上述と同
様な方法により（ＱＩ十ＱＩ）（Ｑｊ＋ＱＩ）（Ｑｋ十
ＱＩ）をＱの指数表現で求め、これの相補値（ビットご
とに“１”，“０”を反転したもの）を作ればよい。ま
た、以上の回路で用いた“０”判定回路および回路４′
〜９′の“０”判定回路は、各出力ビットの論理和をと
るそれを反転することで容易に実現することができる。

以上のようにして実現された演算回路４〜１３、判定回
路４′〜９′および制御回路１４はクロックを用いない
静的動作によって迅速に演算結果の出力を得ることがで
きる。

以上述べたように、本実施例の回路は下記のような種類
の特徴と有している。

シンドローム演算回路においては受信シンボルへ
へ〈を官Ｎ心ＢＮ‐２，……Ｂ，，氏の順に入力する
ことによって簡単な回路でシンドロＳｏ〜Ｓ３の演算が
達成される。

専用のエラーフラグ数計数回路を有し、計数したエラー
フラグ数を用いて効率的な誤り訂正制御を行なっている
。

誤り訂正情報を演算するに当り、次次の中間演算結果の
情報を組織的に繰り返して用い、これによりハードウェ
アの大中な簡易化を達成している。

上述の次次の中間演算結果を得るとともに、それらが“
０”か否かを判定する“０”判定回路を有し、これらの
判定回路の出力情況により、誤り訂正情報による訂正の
実行を制御し、シンドローム情報の有効活用を計りこれ
により訂正能力を高めている。

誤り訂正情報を演算するに当り、最初に得られた誤り訂
正情報を第２以下の誤り訂正情報を演算するのに利用し
、第２に得られた誤り訂正情報を第３以下の誤り訂正情
報を演算するのに利用し、このように先に得られた誤り
訂正情報を後で求むべき誤り訂正情報の演算に利用する
ことによってハードウェアの大中な簡易化を達成してい
る。

各種の演算に、ＲＯＭとＭＯＤ２５５の加算器と排他的
論理和回路と“０”判定回路とゲート回路よりなる演算
回路を使用し、積はＱの指数表現による指数のＭＯＤ２
５５加算により行ない、和は符号ベクトル表現による排
他的論理和回路で行ない、指数表現とベクトル表現との
変換にはＲＯＭを用い、指数表現のできない“０”に対
しては“０”判定回路とゲート回路とによるバイパス演
算を行ない、かくしてクロックの不要な迅速確実なスタ
ティック演算回路を達成している。３なお
本実施例においては符号の各シンボルを８ビット構成と
し、また指定される誤りの数を４個までとしたが、これ
らの値はそれに限るものではないことは明らかである。
以上のように本発明を用いると、誤り訂正情報を演算す
るに当り次次の中間演算結果の情報を粗識的に繰り返し
て用いるこれによりハードウェアの大中な簡易化を達成
できる。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック図、第２図は
本実施例で用いる加算の説明をするための図、第３図１
は本実施例で用いる演算の符号多項式を説明するための
図、第３図２は本実施例で用いる積の演算を説明するた
めの図、第４図は本実施例のシンドローム演算回路の内
部回路例を示す図、第５図は本実施例の第１中間情報Ｍ
，演算回路の回路例を示す図である。図において、１・…・・シンドローム演算回路、２・・
・・・・エラーグラフ数計数回路、３・・・・・・誤り
シンボル位置生成回路、４・・・“・第１中間情報Ｍ，
演算回路、４′・・・…Ｍ，“０”判定回路、５・・・
・・・第１中間情報地演算回路、５′・・・・・・Ｍ２
“０”判定回路、６・・・第１中間情報Ｍ３演算回路、
６′・・・・・・Ｍ３“０”判定回路、７…・・・第２
中間情報Ｐ，演算回路、７′・・・・・・ＰＡ“０”判
定回路、８・・・・・・第２中間情報Ｐ２演算回路、８
′・・・…Ｐ２“０”判定回路、９・・・・・・第３中
間情報Ｑ，演算回路、９′…・・・Ｑ，“０”判定回路
、１０・・・・・・誤り訂正情報ＥＩ演算回路、１１・
・・…誤り訂正情報Ｅｋ演算回路、１２・・・・・・誤
り訂正情報Ｅｉ演算回路、１３・・・・・・誤り訂正情
報Ｅｉ演算回路、１４・・・・・・誤り訂正実行制御論
理回路、１５・…・・誤り訂正実行回路、１０１・・・
・・・シフトレジスタ、１０２，４０１，４０３・・・
・・・読出し専用メモリ（ＲＯＭ）、１０３，４０５・
・・・・・排他的論理和回路、４００・・・・・・“０
”判定回路、４０２・・・・・・ＭＯＤ２５５力ロ算器
、４０４・・・・・・ゲート。図斑繁Ｚ図鷺Ｊ図 ★潟４図繁ぶ図

Claims

【特許請求の範囲】

１Ｍ個（但しＭは正の整数）の１次多項式の積ででき
る生成多項式から生成される符号長Ｎ（但しＮはＭより
も大きい正の整数）のリード・ソロモン符号を受信した
該受信符号に対するＭ個のシンドロームＳ＿０，Ｓ＿１
，……Ｓ＿Ｍ＿−＿１を演算して該シンドロームもとに
該受信符号内の予め指定されたｍ個（但しｍはＭ以下の
整数）のシンボル位置ｉ＿１，ｉ＿２，……ｉ＿ｍにお
ける受信シンボルが誤つていれば訂正する方式において
、前記シンドロームＳ＿０，Ｓ＿１，……Ｓ＿Ｍ＿−
＿１および前記シンボル位置ｉ＿１より予め設定された
演算によつて定めるＭ−１個の第１中間情報を演算しか
つこれらの各各が“０”か否かを判定する第１演算手段
と、前記第１中間情報を利用しこの情報と前記シンボ
ル位置ｉ＿２より予め設定された演算によつて定まるＭ
−２個の第２中間情報を演算しこれらの各各が“０”か
否かを判定する第２演算手段と、以下同様にして次次
に進み第ｍ−２中間情報を利用しこの情報と前記シンボ
ル位置ｉ＿ｍ＿−＿１より予め設定された演算によつて
定まるＭ−ｍ＋１個の第ｍ−１中間情報を演算しこれが
“０”か否かを判定する第ｍ−１演算手段と、さらに
ｍがＭよりも小さいときは前記第ｍ−１中間情報と前記
シンボル位置ｉ＿ｍより予め設定された演算によつて定
まるＭ−ｍ個の第ｍ中間情報を演算しこれが“０”か否
かを判定する第ｍ演算手段までを含む次次の演算手段と
、前記第１乃至第ｍ−１または第ｍ中間情報と前記シ
ンドロームＳ＿０と前記シンボル位置ｉ＿１，ｉ＿２，
……ｉ＿ｍとを利用して前記指定された各シンボル位置
ｉ＿１，ｉ＿２，……ｉ＿ｍに対する誤り訂正に使用す
べき訂正情報を演算し前記各中間情報中に含まれる前記
“０”の情況に応答して前記訂正情報による誤り訂正の
実行を制御する手段と、を含むことを特徴とするリード
・ソロモン符号復号方式。