JPH0133055B2

JPH0133055B2 -

Info

Publication number: JPH0133055B2
Application number: JP57114281A
Authority: JP
Inventors: Yukihiro Okada
Original assignee: NEC Home Electronics Ltd
Current assignee: NEC Home Electronics Ltd
Priority date: 1982-06-30
Filing date: 1982-06-30
Publication date: 1989-07-11
Also published as: JPS595759A

Description

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

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

リード・ソロモン符号に関しては米国のノー
ス・ホーランドパブリツシングカンパニイ
（NORTH−HOLLAND PUBLISHING
COMPANY）から1978年に発行されたエフ・ジ
エー・マツクウイリアム（F.J.MACWILIAM）
およびエヌ・ジエー・エイ・スローン（N.J.A.
SLOAN）著ザセオリイオブエラーコレ
クテイングコード（THE THEORY OF
ERROR CORRECTING CODES）に詳述され
ている。

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

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

上述の目的を達成するため、本発明は、Ｍ個
（但しＭは正の整数）の１次多項式の積で得られ
る生成多項式から生成され、Ｎ個のシンボルで構
成された符号長Ｎ（但しＮはＭよりも大きい正の
整数）のリード・ソロモン符号を受信し、Ｎ個の
各々のシンボルを受信する毎に予めメモリに書き
込まれた原始元η_i（但しη_i＝αⁱ、ｉ＝０、……、Ｍ
−１、ｉに対してシンドロームS₀、……S_i、……
S_M-1が与えられる。）を受信シンボルと乗算し、
これと次の受信シンボルとの排他的論理和をとつ
てシフトレジスタに蓄積すると共に、その出力を
分岐して前記メモリに戻し、この操作をＮ個のシ
ンボル全てに対して行い、前記シフトレジスタよ
りシンドローム演算出力を引き出すシンドローム
演算手段と、シンドロームをガロア体GF（2^y）
（但しｙは正の整数）を条件として原子元αの羃
乗で表現してそれぞれの対応した指数を演算する
指数算出手段と、上記演算手段から得られたシン
ドロームに対応する原子元αの羃指数のmod2^y−
１加算を行いこの加算結果が存在するとき、これ
を誤り位置ｊとして検出する誤り位置検出手段
と、上記シンドローム演算手段から得得られたシ
ンドロームと、上記誤り位置検出手段から得られ
た誤り位置ｊとを受けて、誤り訂正を実行する誤
り訂正実行手段とから構成される。

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

第１図は本発明の一実施例を示すブロツク図で
あり、この実施例はシンドロームS₀.S₁、S₂、…
…、S_M-1演算回路２，３，４，……，５と、指数
算出用の読み出し専用メモリ（以下、ROMと略
す）６，７，８，……９と、mod255加算回路１
０，１１，１２，……，１３と、誤り位置(j)比較
判定回路１４と、シンドロームゼロ判定回路１５
と、誤り訂正実行回路１６とを有し、ここではシ
ンドロームS₀、S₁、S₂、……、S_M-1演算回路２，
３，４，……，５がシンドローム演算手段に相当
し、以下同様に、指数算出手段に相当するものは
ROM６，７，８，……９及びmod255加算回路
１０，１１，１２，……，１３、誤り位置検出手
段に相当するものは誤り位置(j)比較判定回路１
４、誤り訂正実行手段に相当するものは誤り訂正
実行回路１６である。

さて、このブロツク図に従つて本実施例の動作
の詳細を説明する前にまずその動作原理を先に説
明する。

一般に、リード・ソロモン符号においては、Ｎ
個のシンボルが１符号ブロツクを構成し、この１
符号ブロツク中にＭ個の検査用シンボルと、Ｎ−
Ｍ個の情報伝達用シンボルとが含まれている。こ
こで用いられる各シンボルには種々あるが、本実
施例では、一般に広く用いられている８ビツトの
符号ベクトルと仮定する。また、説明を具体的に
するために、１符号ブロツク中のシンボルの数
（符号長）をＮとし、また１符号ブロツク中の検
査用シンボルの数をＭと仮定する。従つて１符号
ブロツク中の情報伝達データ用シンボルの数は、
Ｎ−Ｍとなる。

さて、１符号ブロツク中のＮ個の各シンボルを
A₀、A₁、A₂、……A_M-1、A_M、……、Aj、……
A_M-1 で現すことにする。任意のAjは１バイトの符号
であり、従つて、2⁸＝256個の元の中の１つの元
を表わしている。また、この中のシンボルA_M〜
A_N-1のＮ−Ｍ個が情報伝達データ用シンボルで、
残りのA₀〜A_M-1のＭ個がこのA_M〜A_N-1をもとに
して作られた検査用シンボルであると仮定する。

さて、リード・ソロモン符号においては、符号
化の過程において、検査用シンボルA₀〜A_M-1は
情報伝達データ用シンボルA_M〜A_N-1との間で次
の拘束関係を満足するように作られる。すなわ
ち、 A₀＋A₁＋A₂＋……＋Aj＋……＋A_N-1＝０ A₀＋αA₁＋α²A₂＋……＋α^jAj＋…… ＋α^N-1A_N-1＝０ A₀＋α²A₁＋α⁴A₂＋……＋α^2jAj ＋……＋α^2(N-1)A_N-1＝０ A₀＋α³A₁＋α⁶A₂＋……＋α^3jAj ＋……＋α^3(N-1)A_N-1＝０〓〓〓 A₀＋α^M-1A₁＋α^2(M-1)A₂＋……＋α^(M-1)j ×Aj＋……＋α^(M-1)(N-1)A_N-1＝０ (1) この(1)式においては、各シンボルの記号Ajの
ほかに、記号αが用いられ、また、＋で結ばれた
和の演算と、α同志間の積（αの羃）およびαの
羃とAjとの積の演算が用いられている。このα
は特定のシンボルを代表し、また上述の和および
積も一般の２進数の和および積とは異なる特別の
演算を意味する。以下これについて説明する。

上述のように、本実施例ではAjもαもともに
８ビツトの“１”、“０”符号でできている符号ベ
クトルとする。従つて、いずれも2⁸＝256個の元
の中の１つの元を表わしている。

さて、この256個の中から任意の２つの元Ａと
Ｂとを選び、この２つの元の和で指定される元Ａ
＋Ｂおよび２つの元の積で指定される元ABのい
ずれも、もとの256個中の１つの元になると仮定
して各々を次のように定義できる。

和：第２図に示すように元Ａおよび元Ｂを符号
ベクトルの形で表示し、各桁（各次元）ごとの排
他的論理和をとつた結果生ずる符号ベクトルをＡ
＋Ｂと定義する。和の演算がこのように定義され
るために２個の同じ元の和は常に“０”（各次元
の成分がすべて“０”の符号ベクトル）となり、
また、和の逆算としての差の演算は和の演算と同
じになる。

積：例えば第３図１に示すような元Ａおよび元
Ｂがあると、これをχの多項式表現Ａ＝１＋χ²＋χ³＋χ⁵ Ｂ＝χ²＋χ⁴ とし、この多項式の積ABを AB＝（１＋χ²＋χ³＋χ⁵）（χ²＋χ⁴）＝χ²＋（χ⁴＋χ⁴）＋χ⁵＋χ⁶ ＋（χ⁷＋χ⁷）＋χ⁹ のように作る。この中でχの同じ羃乗の項は、符
号ベルトルの同じ桁（次元）に対応するので、上
述の排他的論理和の規則を適用して整理すると上
式は、 AB＝χ⁹＋χ⁶＋χ⁵＋χ² となる。この多項式はχの７乗以上の項（すなわ
ちχ⁹の項）を含むので、このままではこれに対応
する８ビツトの符号ベクトルを指定することがで
きない。

そこで、積を定義する場合には、それに伴つて
８次のある既約多項式ｆ（χ）を予め定めておき、
これを用いて以下のように定義する。

このｆ（χ）をｆ（χ）＝χ⁸＋χ⁵＋χ³＋χ＋１と定義すると、このｆ（χ）を用いて前記ABの
多項式を割算し、その結果生ずる剰余を作る。

こうすると、剰余は必ずχの７次またはそれ以
下の次数の多項式となるので、これに対応する８
ビツトの符号ベクトルが存在する。これを積AB
と定義する。今の場合、上述のABの多項式をｆ
（χ）で除した商は、χとなり、剰余は、 χ⁵＋χ⁴＋χ となる（この演算においても前述の排他的論理和
の規則が適用されていて、引き算と足し算は同じ
である）。これより AB＝χ⁵＋χ⁴＋χ となり、これを符号ベクトルで表示すると第３図
２に示すようになる。

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

さて、前記既約多項式ｆ（χ）を適当に選ぶこ
とにより、前記256個の元の中の“０”（すべての
桁の成分が“０”の元）を除く256個のすべての
元を、ある元αの羃乗の形で表わすことができ
る。すなわち、１を単位元とし、これにつぎつぎ
にαを乗ずることによつて生ずる元、α、α²、
α³、……、α²⁵⁵は前記“０”を除くすべての元を
一巡してα²⁵⁵で再び単位元１に戻るようにするこ
とができる。

実際に、前記既約多項式ｆ（χ）として、ｆ（χ）＝χ⁸＋χ⁵＋χ³＋χ＋１を用い、αとして多項式表現のχを用いると、
255のすべての元はα^j（但しｊ＝０、１、２、……
255）として表わすことができる。但しα⁰＝α²⁵⁵
＝１である。このαを原始元と呼び、またこのよ
うな性質を有する多項式ｆ（χ）を原始多項式と
呼ぶ。このような性質をもつ８次の原始多項式
は、上述のものを含んで16個あることが知られて
いる。本実施例においては、この16個の中の特定
の１つの原始多項式によつて元の間の演算が定義
されていると仮定し、またこれによつて定義され
る前記原始元αを用いることにする。この結果０
を除く任意の元は、α^j（但しｊ＝０、１、２、…
…、255）で表現され、従つて、任意の元は、指
数ｊだけでも指定することができる。これを元の
指数表現と呼ぶことにする。この指数表現を用い
ると、“０”を除く任意の２つの元の積は、各々
の元の指数表現をとり、この両者を255を法とし
て加えることにより両者の積の指数表現として簡
単に演算することができる。もし一方の元に
“０”が含まれる場合には結果の元を“０”とす
ればよい。また、商を作る場合には、分母になる
元の指数表現の２進数を、その各桁の“１”、
“０”を反転してから前述と同様に255を法として
加えればよい。

勿論、２つの元の和を演算する場合には、符号
ベクトルの表現を用いると簡単に行なうことがで
きる。

このように、各元は、αの羃乗でも、αの指数
表現でも、符号ベクトル表現としても、また多項
式表現としても指定することができる。これらの
中のいずれの表現を用いるかは、その使用目的に
よつて最も適当なものを選ぶことができる。

さて、こうして(1)式の演算は定義されたが、実
際に、任意の情報伝達データ用シンボルA_M〜
A_N-1から(1)式の拘束条件を満足する検査用シン
ボルA₀〜A_M-1を生成するには次のようにする。
今、生成多項式ｇ（χ）として、ｇ（χ）＝（χ−
１）（χ−α）（χ−α²）（χ−α³）……（χ−
α^M-1）を定義し、一方符号多項式Ｃ（χ）として
Ｃ（χ）＝A_N-1χ^N-1＋A_N-2χ^N-1＋……＋A_Mχ^Mを定
義する。このＣ（χ）をｇ（χ）で除した剰余の多
項式をＲ（χ）とすると、Ｒ（χ）はχに関するＭ
−１次またはそれ以下の多項式となるので、Ｒ
（χ）＝b_M-1χ^M-1＋b_M-2χ^M-2＋……＋b₃χ³＋b₂χ²＋
b₁χ＋b₀と表わせる。こうして定まるb_M-1、b_M-2、
……b₃、b₂、b₁、b₀、をそれぞれ検査用シンボル
A_M-1、A_M-2、……、A₃、A₂、A₁、A₀として用
いると、これらは次のような理由で(1)式の拘束条
件を満す検査用シンボルとなつている。

今、Ｃ（χ）をｇ（χ）で除した商をＱ（χ）と
書くと、Ｃ（χ）＝ｇ（χ）Ｑ（χ）＋Ｒ（χ）とな
り、これから、Ｃ（χ）＋Ｒ（χ）＝ｇ（χ）Ｑ（χ）
が導かれる（この場合もＲ（χ）を引くことはＲ
（χ）を加えることと同じである）。従つてＣ（χ）
＋Ｒ（χ）はｇ（χ）で割り切れて、A_N-1χ^N-1＋
A_N-2χ^N-2＋……＋A_Mχ^M＋A_M-1χ^M-1＋A_M-2χ^M-2＋
……＋A₃χ³＋A₂χ²＋A₁χ＋A₀＝（χ−２）（χ−
２（χ−α）（χ−α²）（χ−α³）……（χ−α^M-1
）
Ｑ（χ）が成立する。上式の両辺のｘに、それぞ
れ１、α、α²、α³、……α^M-1をつぎつぎに代入す
ることによつて、(1)式の関係が導かれる。

さて、上述のようにして送信側で作られた(1)式
の拘束条件を満す符号ブロツクA₀、A₁、A₂、…
…、A_N-1を送信し、それらがA^₀、A^₁、A^₂、…
…、A^_N-1として受信されたとする。そしてこれ
らの中の１つのシンボルAjにだけ誤りが生じた
と仮定する。すなわち、ｊ以外のｋに対しては、 A^_K＝A_K ……(2) が成立し、Ajに対しては A^j＝Aj＋ej ……(3) とする。但し、ejはｊ番目のシンボルに起つた誤
りとする。

さて、今受信側において、受信シンボルA^₀、
A^₁、A^₂、……、A^_N-1を用いて(1)式の各式の左辺
に相当する演算を行ない、その結果をそれぞれ
S₀、S₁、S₂、……S_M-1とする。すなわち、 S₀＝A^₀＋A^₁＋A^₂……＋A^j＋……＋A^_N-1 S₁＝A^₀＋αA^₁＋α²A^₂＋……＋α^jA^j ＋……＋α^N-1A^_N-1 S₂＝A^₀＋α²A^₁＋α⁴A^₂＋……＋α^2jA^j ＋……＋α^2(N-1)A^_N-1 S₃＝A^₀＋α³A^₁＋α⁶A^₂＋……＋α^3jA^j ＋……＋α^3(N-1)A^_N-1 〓〓〓 S_M-1＝A^₀＋α^M-1A^₁＋α^2(M-1)A^₂＋…… S_M-1＝A^₀＋α^M-1A^₁＋α^2(M-1)A^₂＋…… ＋α^j(M-1)A^j＋……＋α^(M-1)(N-1)A^_N-1(4)
とする。もし、受信に全く誤りがなければ、(4)式
の左辺は(1)式の左辺と全く同じになり、従つて、
S₀〜S_M-1はすべて“０”になる筈である。受信に
誤りがあると(4)式の各左辺に相当する演算結果は
一般に“０”でないそれぞれの値S₀、S₂、……
S_M-1をとることになる。これをシンドロームとい
う。本実施例は、このシンドロームS₀〜S_M-1を用
い、送信側で一ブロツク内のシンボル間に加えた
(1)式の拘束演算関係から誤り分を求めてこれを訂
正する方式である。

さて、(2)式、(3)式の関係を(4)式に代入し、(1)の
関係を用いると、結果は次のようになる。

S₀＝ej S₁＝α^jej S₂＝α^2jej S₃＝α^3jej 〓〓 S_M-1＝α^(M-1)jej ……(5) この(5)式を変形すると、次の式が導かれる。

S₀＝ej (6) α^j＝S₁・S₀ ^- ₁ (7) α^2j＝S₂・S₀ ^-1 (8) α^3j＝S₃・S₀ ^-1 (9) 〓〓〓 α^(M-1)j＝S_M-1・S₀ ^-1 (10) ここにおいて、S₀〜S_M-1をGF（2⁸）の条件でα
の羃乗で表現し、それぞれをα^x0〜α^xn-1とする
と、上記(7)〜(10)式はそれぞれ次式の如くなる。な
お、この条件において、α^-x＝α^255-xである。

ｊ＝（255−χ⁰）＋χ₁ ……(11) 2j＝（255−χ⁰）＋χ₂ ……(12) 3j＝（255−χ⁰）＋χ₃ ……(13) 〓〓〓（Ｍ−１）ｊ＝（255−χ₀）＋χ_M-1 ……(14) これらの式(11)〜（14）における加算は、255を
法とする加算、即ちmod255加算である。そして、
これらの式(11)〜（14）の関係が成立するｊ値が存
在した場合のみ、誤り位置ｊに対し、誤り情報ej
＝S₀を用いて訂正することができるのである。な
お、ここで、誤り情報ejは上記(6)式からS₀として
求まり、また誤り位置ｊは(11)〜（14）式を演算す
ることによつて求まるものである。

以下、その構成および動作を第１図に示す本発
明の実施例により説明する。

送信側より送信されてきたＮ個のシンボルを有
する送信符号ブロツクA_N-1、A_N-2……、A₂、
A₁、A₀は、第１図に示す本発明の回路において、
受信入力端子１にA^_N-1、A^_N-2……A^₂、A^₁、A^₀の
順で入力され、Ｍ個のシンドローム演算回路、即
ちS₀演算回路２、S₁演算回路３、S₂演算回路４、
……、S_M-1演算回路５によつて上記(4)式で示すシ
ンドロームS₀〜S_M-1を演算する。

なお、この中の、例えばS₁を求める演算回路例
を第４図に示す。これは１段のシフトレジスタ１
１０、ROM１１１、および排他的論理和回路１
１２から成つている。シフトレジスタ１１０およ
び排他的論理和回路１１２はそれぞれ８ビツト分
を並列に処理する。またROM１１１は、シフト
レジスタ１１０の出力（８ビツト）でアドレス指
定のできる256のメモリアドレスを有し、各メモ
リアドレス当り８ビツトのデータを格納できる容
量を有する。シフトレジスタ１１０の生力により
指定されるROM１１１のメモリアドレスからデ
ータが読み出され、回路１１２により入力端子１
からの入力データとの排他的論理和がとられ、こ
れがシフトレジスタ１１０に読み込まれる。任意
の８ビツトの２進数A′で指定されるROM１１１
のメモリアドレスにαA′（但し、αA′はこの２進数
A′に対応する符号ベクトルと原始元αとの積と
する）を書き込んでおくと、ROM１１１はα倍
の乗算器として動作する。かくて、最初にシフト
レジスタ１１０をリセツトし、入力データを前述
のようにA^_N-1、A^_N-2、……A^₀の順序で次々に回
路１１２を介して入力すると、A^₀が入力された
時点で、シフトレジスタ１１０の内容は、（……（（A^_N-1α＋A^_N-2）α＋A^_N-3）α＋……＋
A^₁）α＋A^₀＝α^N-1A^_N-1＋α^N-2A^_N-2α^N-3A^_N-3＋…
…＋αA^₁＋A^₀となり、求めるシンドロームS₁と
なる。ROM１１１の内容を、上述のαのかわり
にα²、α³、……α^M-1の相当するものとすることに
より、同様な回路を用いてそれぞれシンドローム
S₂、S₃、……S_M-1を演算する回路が得られ、また
ROM１１１を除きシフトレジスタ１１０の内容
をそのまま回路１１２にフイードバツクすること
によりシンドロームS₀を演算する回路が得られ
る。

このようにして得られたシンドロームS₀〜S_M-1
は、上記ROM６〜９にアドレスとして入力さ
れ、上記(11)〜（14）式で示した指数255−χ₀、χ₁、
χ₂……、χ_M-1をそれぞれ算出する。このROM６
〜９は、一種の変換回路であつて、アドレスとし
て入力されたシンドロームS₀〜S_M-1のメモリロケ
ーシヨンに固定データとして上記指数255−χ₀、
χ₁、χ₂、……χ_M-1に相当するデータが記憶されて
おり、S₀〜S_M-1がアドレスとして入力されること
により上記指数255−χ₀、χ₁、χ₂、……χ_M-1が出
力されるものである。そして、このように出力さ
れた255−χ₀、χ₁、χ₂、……χ_M-1をmod255加算回
路１０〜１３に供給し、上記(11)〜（14）式に示す
mod255加算を行う。即ち、mod255加算回路１０
においては、ROM６からの255−χ₀とROM７か
らのχ₁とを受信して、上記(11)式に示すmod255加
算を行つて、その結果ｊを算出し、このｊを誤り
位置(j)比較判定回路１４に供給し、mod255加算
回路１１においては、ROM６からの255−χ₀と
ROM８からのχ₂とを受信して、上記(12)式に示す
mod255加算を行つて2jを算出し、この2jを上記
誤り位置(j)比較判定回路１４に供給し、以下同様
にして、mod255加算回路１３においては、
ROM６からの255−χ₀とROM９からのχ_M-1とを
受信して、上記（14）式に示すmod255加算を行
つて（Ｍ−１）ｊを算出し、この（Ｍ−１）ｊを
誤り位置(j)比較判定回路１４に供給する。このよ
うにして算出され、上記(11)〜（14）式に対応する
ｊ、2j、3j、……、（Ｍ−１）ｊを供給された誤
り位置(j)比較判定回路１４は、これらの情報から
誤り位置情報ｊを算出する。この回路は単に上記
情報からｊを算出するのみならず、2j、3j、…
…、（Ｍ−１）ｊがそれぞれｊに対して２倍、３
倍、……（Ｍ−１）倍の関係にあつて、それぞれ
が同じ誤り位置ｊを示していることも確認するも
のである。このような回路は通常の論理回路の組
み合せで容易に実現することもできるし、またマ
イクロコンピユータ等を利用しても容易に実現す
ることができるものである。そして、この誤り位
置(j)比較判定回路１４からの誤り位置ｊの出力信
号は誤り訂正実行回路１６に供給され、その誤り
位置を通知する。

上記シンドロームゼロ判定回路１５は、上記
S₀、S₁、S₂、……、S_M-1演算回路２〜５からのシ
ンドロームS₀〜S_M-1を受信し、これらのシンドロ
ームS₀〜S_M-1がすべてゼロであつて受信した符号
ブロツクに全く誤りがないか、S₀〜S_M-1がすべて
ゼロではないが１個でもゼロがあつて受信した符
号ブロツクに２個以上の誤りがあるのかを検出す
る回路であつて、前者、即ちS₀〜S_M-1がすべてゼ
ロであつて受信した符号ブロツクに全く誤りがな
い場合には、一方の出力リード線４００上に誤り
なし信号を出力し、この誤りなし信号を誤り訂正
実行回路１６に伝達し、符号ブロツク中に誤りが
ないことを通知する。また、後者、即ちS₀〜S_M-1
がすべてゼロではないが１個でもゼロがあつて受
信した符号ブロツクの中に２個以上の誤りがある
場合には、他方の出力リード線５００上に誤り２
個以上信号を出力し、この誤り２個以上信号を誤
り訂正実行回路１６に伝達し、符号ブロツク中に
誤りが２個以上あることを通知する。なお、誤り
が１個の場合には、(1)式から(4)式の関係からS₀〜
S_M-1はすべてゼロでなく、それぞれの値を取り(11)
〜（14）式より決められるｊはすべて等しい値と
なり、これは上記誤り位置(j)比較判定回路１４に
よつて比較範囲されるｊ値として算出され、誤り
訂正実行回路１６に供給されて判断されるのであ
る。そして、この時同時に、S₀演算回路２から供
給されるS₀を上記(6)式に示すように誤りejとして
用い、上記誤り位置ｊのシンボルを訂正して、出
力リード線１８上に出力データとして訂正した符
号ブロツクを送出するのである。なお、この時、
他方の出力リード線１７にはエラーフラグは送出
されず、リード線１８から送出された符号ブロツ
クには誤りがないことを示している。また、符号
ブロツクに誤りが全くなく、上記シンドロームゼ
ロ判定回路１５からリード線４００を介して誤り
訂正実行回路１６に誤りなし信号が供給された場
合には、入力端子１から供給された符号ブロツク
は誤り訂正実行回路１６を介して、直接、リード
線１８から出力され、この時にも同時にエラーフ
ラグは送出されない。更に、符号ブロツク中に誤
りが２個以上あつて、上記シンドロームゼロ判定
回路１５からリード線５００を介して誤り訂正実
行回路１６に誤り２個以上信号が供給された場合
には、誤り訂正は行われず、入力端子１から供給
された符号ブロツクは誤りを含んだまま誤り訂正
実行回路１６を介して、直接、リード線１８から
出力されると同時に、シンドロームゼロ判定回路
１５からリード線５００を介して供給される誤り
２個以上信号によつて判定し、エラーフラグをリ
ード線１７に送出し、符号ブロツク中に誤りがあ
ることを知らせる。

以上説明したように、本発明によれば、Ｎ個の
シンボルで１個の符号ブロツクをなすリード・ソ
ロモン符号内に生じた１個の誤りを訂正する方式
において、検査用シンボルの数Ｍ個までのすべて
のシンドロームの情報を有効に利用し、かつ、簡
潔な回路構成により目的を達成する信頼性の高い
復号方式を提供することができる。これにより信
頼性、経済性の向上を達成できる。また、符号ブ
ロツク内に２シンボル以上の誤りを検出したらエ
ラーフラグを送出し、符号ブロツク内に誤りがあ
ることを知らせている。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロツク図、
第２図は本実施例で用いる和の演算を説明するた
めの図、第３図１は本実施例で用いる演算の符号
多項式を説明するための図、第３図２は本実施例
で用いる積の演算を説明するための図、第４図は
本実施例のシンドローム演算回路の内部回路例を
示す図である。２〜５……シンドローム演算手段、６〜９，１
０〜１３……指数算出手段、１４……誤り位置(j)
検出手段、１５……シンドロームゼロ判定回路、
１６……誤り訂正実行手段。

Claims

【特許請求の範囲】１Ｍ個（但しＭは正の整数）の１次多項式の積
で得られる生成多項式から生成され、Ｎ個のシン
ボルで構成された符号長Ｎ（但しＮはＭよりも大
きい正の整数）のリード・ソロモン符号を受信
し、Ｎ個の各々のシンボルを受信する毎に予めメ
モリに書き込まれた原始元η_i（但しη_i＝αⁱ、ｉ＝
０、……、Ｍ−１、ｉに対してシンドロームS₀、
……S_i、……S_M-1が与えられる。）を受信シンボ
ルと乗算し、これと次の受信シンボルとの排他的
論理和をとつてシフトレジスタに蓄積すると共
に、その出力を分岐して前記メモリに戻し、この
操作をＮ個のシンボル全てに対して行い、前記シ
フトレジスタよりシンドローム演算出力を引き出
すシンドローム演算手段と、シンドロームをガロア体GF（2^y）（但しｙは正
の整数）を条件として原子元αの羃乗で表現して
それぞれの対応した指数を演算する指数算出手段
と、上記演算手段から得られたシンドロームに対応
する原子元αの羃指数のmod2^y−１加算を行いこ
の加算結果が存在するとき、これを誤り位置ｊと
して検出する誤り位置検出手段と、上記シンドローム演算手段から得られたシンド
ロームと、上記誤り位置検出手段から得られた誤
り位置ｊとを受けて、誤り訂正を実行する誤り訂
正実行手段と、を有することを特徴とするリード・ソロモン符号
復号方式。