WO1997011530A1

WO1997011530A1 - Procede de decodage d'une grappe d'erreurs du code de reed-solomon et dispositif correspondant

Info

Publication number: WO1997011530A1
Application number: PCT/JP1995/001883
Authority: WO
Inventors: Yasuhiro Hirano
Original assignee: Hitachi, Ltd.
Priority date: 1995-09-20
Filing date: 1995-09-20
Publication date: 1997-03-27

Description

明細書リ一ドソロモン符号のパースト誤りの «号方法及び復号装置技術分野

本発明は誤り訂正符号の復号方法及び復号装置に係リ、特に、リードソロモン符号におけるパースト誤りの訂正を行うに好適な復号方法及び復号装置に関する。背景技術

ディジタル伝送'記緑システムでは、伝送あるいは記録 '再生の過程で親りが発生した場合でも元の情報を復号する符号 isリ訂正技術が採用されている，

一般には、送倌側では、伝送あるいは記錄しょうとする情報に誤リ検出あるいは誤リ盯正のための検査ビットを付加して符号 Sを構成し、伝送あるいは記緑を行う，そして、受信側では、送信側で付加された検査ビットを利用して誤りの検出や Kリの盯正を行う .

かかる誤りの検出あるいは誤りの訂正を行う符号に閟しては、これまで種々の符号が考案されている. このうち、リードソロモン符号（Reed- So lomon code ，以下、「R S符号」と格称する，）は、ノィト单位に誤りの盯正を行う符号で、コンパクトディスク、ディジタル V T R、ディジタル放送等の分野で広く使用されている，

t重淇り盯正 R S符号は、符号語に含まれる t個のパイト誤リまでが盯正できる. したがって、 t重轵リ盯正 R S符号は、符号骐リがランダムに発生するランダム »リでは、 t個のランダム珙り盯正の符号として使用できる. また、 t重 38リ訂正 R S符号は、符号 Kリが一ヶ所に集中して発生するバースト誤リでは長さ tパイ卜のバースト誤リ盯正の符号として使用できる。

しかし、従来技術では、バースト誤り訂正に対してもランダム誤リ訂正の復号手順に従った復号方法で誤リ訂正の助作を行うため、復号処理が複雑になる。そこで、復号処理の簡単なバースト誤りの復号方法が望まれている。特に、コンパクトディスクやディジタル VT R等は、記録媒体の傷などに起因したパースト誤りが頻発するため、パースト誤リの復号処理を如何に簡略なものとするかが極めて重要な課題となっている , 本発明は、上記 SJ8に «みてなされたものであり、 R S符号におけるバースト ISリ訂正の復号処理を極めて ffi单に行うことができる復号方法及び復号装置を提供することを目的とする. 発明の閱示

上 Kの目的を连成するため、本発明においては、 t重バイト asリ盯正 R S符号に対して、第 1図に示す復号手!！によリパースト Kリを訂正する «号方法を採用する，

すなわち、受信符号に対して、第 1のステップでシンドローム； S , ( i = 0 , 1 , 2 , · · · ， 2 t - 1 )を計算する。

第 2のステップでは、このシンドローム S【を用いて、誤リ位 »多項式；ひ - 丄 +ロ！ +ロ： + · · · + σ j Z の j偭（ j ≤ t )の係数 σ , ( i = 0 , 1 , · · · , j )を計算する.

第 3のステップでは、 j 個の整数； 1 , p , q , · · · , r ( 1 < p < q < - · · < r≤ t )の組み合わせで定まるパーストパターン方程式； B P ( α ) = 1 + α + a + · · - + a より、 γ σ ,/Β Ρ α), 力、つ、 σ (γ ) = 0 なる関係を满足するパーストパターン方程式： Β Ρ (α)を探索し、 Β Ρ (ίϊ)· γで j個のバースト淇リ位 Β ; γ · α , · · · , γ · a , γ ·な , yを求める。

第 4のステップでは、この j個のバースト誤り位置； γ ·な , · · · , γ - , γ - a ， ·/と上記第 1 のステップで求めたシンドローム； S【（ i - 0 , 1 , 2， · · · ， 2 t — 1 )とをもとに、誤リ位置に対応する j個の誤りパターン； E . . · ， Ε,, Ερ, を求める，そして、受信符号の上記パースト誤リ位置に対応する位置に上記誤りバタ一ンを加算してパースト誤りの訂正勋作を行う。

なお、この復号手 ΛΒにおける第 1 , 第 2及び第 4のステップは従来技術と同一手法であるが、第 3のステップは従来技術とは全く手法が異なリ、極めて少ない手数でバースト誤りの位置の計算を可能にするものである，

本発明における復号方法の基本は、上述した第 3のステップにおけるバーストバターン方程式； Β Ρ (α)を用いてパースト誤リ位 Βの計算を行うことにある。この屎理および勋作を理解する手助けとして、まず、第 2図に示す 3重淇リ訂正 R S符号を例に、パースト誤りの位置と、リバターンと、シンドロームと、誤リ位置多項式の係数と、バーストパターン方程式との間で成立する関係式を導く .

第 2図は、符号長 η,情報点数 η— 6の 3重誤リ訂正 R S符号の符号語を示し、その生成多項式 G₀(X)は、

σ₀(Χ) = (Χ- 1 ) (Χ-α) (Χ-α²)(Χ-α³)(Χ-α⁴) (Χ-α⁵) …（式 1 ) である。第 2図に示す符号薪中のドット部は符号誤りの発生領域を示し、符号新の i + 2 , i + 1 , i 番目の位置に轵リパターン； E【 ₊ E _{1 +1} , Ε ₍の長さ 3パイトのパースト誤りがある。したがって、受信多項式； Υ (Χ)は、送倌多項式； W(X)にリ多項式 E B (X)を加算したもので、次式となる。

Y (X) = W(X) + E B (X) (式 2)

E B (X) = (E _{i +} ,X + E _{t + 1}X + E【）X

また、本発明では、長さ j バイトのバースト誤リの領域で実際に符号誤りが発生している位 Bを表す多項式として、 X ( i = 0 , 1 , . . . . j 一 1 )の位匿に符号誤りの有る時は 1 を、符号誤リのない時は 0を X の係数とするバーストパターン方程式； B P (X)を新たに導入する。第 2図の 3重誤リ盯正 R S符号の符号 Sでは、このバーストパターン方程式； B P (X)は、

B P (X) = 1 +Χ + X¹ (式 3 )

となる。

さて、シンドローム； S _t ( i = 0 , 1 ， 2 5)は、それぞれ次式で与えられる，

(式 4)

ここで、送信多項式； W(X)は生成多項式； G₀(X)で割り切れるため、このパースト棋リのシンドロームは、以下のものとなる，

(式 5)

次に、式 5を変形して E ,， E E ,を消去し、 γ = α および式 3のパーストパターン方程式； Β Ρ (α) = 1 + α + α²で整理すると以下の関係式を得ることができる。

B P (a) y S ₂ + a B P (a)r^I S ,-l- aⁱ r⁵

B P (a) r S,+ a B P (a) y² S ₂ + a³ Y⁵ (式 6) B P (a)r S4+ a B P (a)r^l S, + ³ r⁵

—方、誤リ位!！多項式； σ (Z)は、

σ (Ζ) = ( 1 - Z) ( 1 - a ' Z) ( 1 - a Z)

(式 Ί ) = 1 + σ , Z + σ , Z + σ , Ζ

となる，ここで、 σ (α ) = 0 ( k = i + 2 , i + 1 , i )である。この関係を式 5に逐次代入すると、以下の周知の関係式を得る，

(式 8)

式 6と式 7より、誤り位!！多項式の係数；と、 γと、バーストパターン方程式； Β Ρ ( a) = 1 + a +な ²との間に

(式 9)

σ (y ) = 0

なる係式を導くことができる，

以上では、 3重 Κリ盯正 R S符号を例として式 9を導いているが、 t 重り訂正 R S符号に対しても式 9はなリたつ，一般に、長さ tバイトのバースト淇リの »リ位置多項式； σ (Ζ)は、

σ (Z) = ( 1 - Z) ( 1 -a Z) - · · ( 1 - Z)

= 1 + ( 1 + a+ · ， - + a +a ) a Z + - · · ·

= 1 + σ , Z + · · · · + ひ _t Z

となり、拱り位置多項式の係数； σ ,は

σ = ( 1 + a + · ' ' + a + a ) a = B P t a ) · γ となる，従って、 t重誤り訂正 R S符号に対しても式 9の関係を導くことができる。

そして、式 9を满足する γとバーストパターン方程式； Β Ρ (α)の積で定義するパースト位置多項式； (a)

/3 (α) = Β Ρ (α) · r (式 1 0 )

が、バースト骐りの発生している位置を示している。

本発明は、パーストりについて新たに導出した式 9の yとパ—ストパターン方程式； Β Ρ (α)の B8係と、式 1 0のパースト位置多項式； β ( α)の 85係とを用いて、極めて少ない手数でパースト誤りの位置の探索を行う .

第 3図は、 t重轵リ盯正 R S符号におけるバーストパターン方程式； B Ρ (α)を示したものである. 図中の »リ偭数は、パースト Κりの領域で実際に符号轵リが発生している個数である。そして、この Sリ個数に対して取り得るバーストパターン方程式； B P (a)を、 t = 2 , 3 , 4， 5のそれぞれについて列挙したものである.

例えば、 t = 4では、ノーストバターン方程式； B Ρ (α)は、誤リ個数が 1 の時は 1 の 1種 ¾、 2の時は 1 + α , 1 + ¹ , 1 + a ³ の 3 種票、 3の時は l + ίΐ十 α² , 1 + a + a³ , 1 + a¹ + a³ の 3種類、 4の時は Ι + α + ίΐ' + α³ の 1種類である，

よって、 t = 4の壜合、第 1図に示す復号手賬の第 3のステップでは、バーストパターン多項式による探索は、リの偭数が 1 の時は 1 回、 2 の時は 3回、 3の時は 3回、 4の時は 1 回でよく、極めて少ない手致でバースト誤りの位置を求めることができる.

第 4図は、バースト誤りの位置を求めるのに必要な探索回数の最悪値を、本発明と従来技術とで比較したものである，

図中の（）内の数值は、従来技術で行われているチェン探索法の場合を示す。従来技術では、誤り個数が 2以上の時はいずれも n— 1 回（ n は符号長。）となる，多くの場合、符号長 nは 1 0 0 〜 2 0 0程度である。したがって、本発明は、従来技術の数分の一から数十分の一と極めて少ない手数で、バースト誤りの位置を効率よく求めることが可能となる。

以上に述べた如く、本発明では、少ない個数のパーストパターン方程式で、バースト誤りに関して新たに導出した式 9を満足するものを探索し、式 1 0のパースト位置多項式でパースト誤りの位置を求めることができる，したがって、従来技術に比較して極めて少ない回数で誤りの位置を計算できる，図面の ffi单な説明

第 1図は、本発明による R S符号のパーストリ訂正の復号手瓶図でぁリ、第 2図は、 R S符号におけるバースト親りの概略図であり、第 3 図は、 t重 Kリ盯正 R S符号におけるバーストパターン方程式であり、第 4図は、 «号手賬の第 3ステツブにおける悪計算量であリ、第 5図は、本発明の第 1 の実施例の全体ブロック構成図であり、第 6図は、生成多項式 G ( X ) - X *十 X + 1 で定義する G F ( 2 * )上の元でぁリ , 第 7図は、第 1 の実施例のシンドローム演算 IBの一構成例図であり、第 8図は、第 1 の実施例の乗箅回路の一構成例図であリ、第 9図は、第 1 の実施例の除算回路の一構成例図でぁリ、第 1 0図は、本発明の R S符号のパースト JSリ訂正の第 2の復号手賬図でぁリ、第 1 1図は、本発明の第 2の実施例の一構成例図である，発明を実施するための最良の形想

本発明の第 1 の実施例について、第 5図に示す全体ブロック構成図によリ説明する。本実施例は、第 1図に示した復号手順によリ R S符号のパース卜誤り訂正を行うに好適なものである。

第 5図中の 1はシンドローム演算部、 2は誤リ位置多項式演算部、 3 はバーストパターン検出部、 4は骐リパターン演算部、 5は遅延部、 6 は加算 ffiである，

t重誤リ盯正 R S符号の受侰符号； Y0は、シンドローム演算部 1と ¾延節 5とに入力する。

シンドローム演算部 1は、 «号手順の第 1ステップであるシンドロームの計算を行う，すなわち、受倌符号； Y0に対して式 4に示す濱算を行い、シンドローム； S i - O , 1 , · . · . 2 t— 1 )を算出する。そして、この S .U - O , 1 , · · · , 2 t— 1 )をシンドローム系列； Sとして出力する，なお、 S, = 0 ( i - 0, 1 , · · · , 2 t— 1 )の時は、棋リ無しと判定して信号； ENに 0を出力する，一方、少なくとも 1つが S ,≠ 0の時は、信号； ENに 1 を出力する，

リ位置多項式濱算 ffi2は、復号手厢の第 2ステップである淇リ位置多項式； σ (Ζ)の係数 _{σ ι}( ί = 1 , 2, · · · , j j ≤ t)を算出する, すなわち、倌号； ENが 1の時に、シンドローム系列； Sに対して式 8 に示す如く用知のシンドローム； S ,と係数； σ ,の §8係式よリ誤リの個数； j と誤り位置多項式の係数 σ ,( i = l， 2 , · · · , j )とを算出する. そして、この Kリの個敗； j と係数； o ,( i = 1. 2 , · · . , j )を係数系列； σとして出力する。

パーストパターン検出 ffi3は、 ffi号手傾の第 3ステップであるパースト誤リ位置を算出する，すなわち、信号； ENが 1の時に、第 3図に示したリの個致； j で規定されるバーストバターン方程式； B P (α)を式 9に逐次代入して γを計算する. そして、 σ )= 0を满足するァが存在する場合は、式 1 0に示すパース卜位置多項式； 3 (a) = Β Ρ (な） ·γで箅出したバースト誤りの位 sを、誤り位 a系列；として出力する，また、信号； EDには 0を出力する。なお、 σ (γ )- 0を满足する Ίが存在しない場合は珙リの位置が不明のため訂正は不可能である，したがって、この場合は淇リ位置系列；にはなにも出力せず、また、侰号； E Dには轵リの検出を示す 1 を出力する。

誤りパターン演算部 4は、復号手順の第 4ステップである誤りバタ— ン； Eiの算出を行う . すなわち、信号； ENが 1 の時に、誤リ位置系列： β ヒシンドローム系列； Sをもとにそれぞれ誤リ位置の誤リパタ一ン； Eiを計箅する，そして、誤りパターン系列； Eを出力する，加算部 6は、運延郎 5で運延させた信号； Y0Dの誤りが発生している位!！に対応する誤りパターンを加箅して誤リの盯正を行い、その出力にバースト 18り訂正の復号処理を行った R S符号； YDを得る。

以下では、 4次の屎始多項式； G(X) = X* + X+ 1で定義する GF ( 2 «)上の元を要衆とする t = 3の 3重誤り訂正（15, 9, 3) R S符号を例に、本実施例の復号勳作を詳述する.

はじめに、この G F (2つ上の元を第 6図に示す. 元の個数は 2*個であリ、各元は 000 0〜 1 1 1 1の 4ビットのベクトルで表現される。また、原始多項式； G(X)の根を αとすると、これらの元はなのべき乗表現で表すこともできる，

G F(2つ上では、元の間の加箅はぺク卜ルの加算で定義する，すなわち、ベクトルの各要素どうしの m o d 2の加算で行う，例えば、第 6 図で α 'とな ⁷との加箅は、

" + α' = 0 1 1 0 + 1 0 1 1 = 1 1 0 I = "

となる，

また、元の間の乗算および除算は、次式で定義する。

a a /a = a

例えば、 it ^s ' a = ii *、な ^ / な，：な'¹となる。

さて、 t = 3の 3重誤リ盯正（15, 9,3) R S符号は、以下の生成多項式 G。（X)、

G₀ (X) = (X- l ) (X-a) (X-aⁱ) (X-a³) (X- ⁴) (X-a^s)

= X* + ct9 X^s + な' ' X' + a Xs + ai Xz + c^ X十 1 で生成される符号である，

つぎに、いくつかの受信符号語に対して、本発明による復号助作を示す，

く例 1 >受信符号語； Y0が Ο Ο Ο Ο Ο Ο Ο Ο Ο Ο Ο Λ Ο Ο Οの場合

(第 1 ステップ〕シンド —ムの計箅

受信符号 S ； Υ0に対して、式 4に示す演算を行い、以下のシンドロームを得る。

S a

S , な a

S a a a '

S a a ¹

S = a a ^{1 2} = a¹³

S = a a ¹ ' = a

[第 2ステップ〕誤リ位置多項式の算出

シンドローム； S i≠ 0、かつ、 S i S ' + So S z- Oであるので、誤リの個数； j は、 j = 1である，よって、誤り位置多項式は σ (Z) = 1 + σ , Ζであり、その係数； a ₁ - S ₁Z S。= a:，となる。

〔第 3ステップ] パーストリ位置の算出

誤り佣数： j = l であるので、第 3図に示すようにバーストパターン方程式； B P ( な） = 1である. これを式 9に代入すれば、 γ = σ ,/Β Ρ (α) = α³/ 1 = a ³

a ( y ) = 1 + σ i γ = 1 + a a = 0

を得る。従って、バースト誤りの位置を示すパースト位 Ϊ多項式； β ( a )は、

β ( ) = B P ( )· γ = a³

となり、符号誤リは受信符号語の右端から 4番目（α³)に存在する„ 〔第 4ステップ〕誤りパターンの算出および盯正

バースト誤リの位置；の Rリパターンをとすれば、式 5より次式を得る。

Ε！ = S = α

従って、受信符号語の右端から 4番目の情報； aにこの誤りパターン； E _{1 =}なを加箅する. そして、符号リを訂正した復号符号 S； YD = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0を復号する.

<例 2 >受信符号語； Y0が 0 0 0 0 0 0 0 0 0 0 0 な 0 な³0の場合 [第 1 ステップ〕シンドロームの計算

受信符号 S ； Y0に対して、式 4に示す浪算を行い、以下のシンドロームを得る，

S 0 = α + ' = a '

S i = α α ⁵ + a¹ = 0

S = ' -- a^{3 1} = a¹³

S j = a a ' + a ³ a ³ = a ⁷

S_A= ^{, l} + ³ a*= a^s

S j = a '* + a^J a* = a'°

(第 2ステップ〕 ISリ位置多項式の算出

シンドローム； S【≠ 0、かつ、 S t S i + S o S , -な⁷、 S , S ₂ S , + ε,ε,εο+Β,ε,ε, + ε,ε,εο θであるので、 ssリの個数； jは、 j = 2である. よって、誤り位置多項式は σ (Z) = 1 + σ , Z + σ ₂ Z² であり、その係数は、

ひ ' -(S t S i+ S s S o)ノ（S i S i + S i S ^ - a⁹

a _I = ( S ₁ S , + S , S ₂)/( S ₁ S ₁ + S ₂ So) = a⁴

となる。

【第 3ステップ〕バースト誤リ位置の箅出

誤リ佣数； j = 2であるので、第 3図に示すようにバーストパターン方程式； B P (a)は、 l + a， 1 + の 2種である。これを式 9に逐次代入すれば、

γ = σ ₁/ Β Ρ (α) = α / ( 1 + a) = 、 σ (a ) = a

γ = σ ι/Β Ρ (α) = α /( 1 + a ) = a , σ ( ) = 0

を得る. 従って、バースト »りの位 itを示すバースト位 31多項式； β ( a )は、

β {a) = ( \ + a¹) a

となり、符号拱りは受信符号語の右靖から 2番目（α)と 4番目（a¹)の位に存在する，

[第 4ステップ〕 |¾リパターンの算出および盯正

パースト誤リの位置； αの »リパターンを Ε ,、位置； α ³の拱リパターンを Ε ₁とすれば、式 5 より次式を得る。

Ε , + Ε ₂ = S = α '

a' E , + a E ₂= S ₁ = 0

この連立方程式を解けば、 E ,= a，を得る。従って、受信符号語の右端から 4番目の情報： aにこのリバターン； E - a , 2 番目の情報； a ³に »リパターン； Ε , = を加算し、符号誤リを訂正した «号符号 R ； YD= 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 を «号する，よって、本発明においては、第 3ステップにおける淇リ位 Bの算出を 2回の演算で行うことができる，一方、従来技術のチェン探索法では、誤り位置多項式に Ζ = α ( i = 1 , 1 3 , · · · ， 1 , 0)を逐次代入し、値が 0を取るものを誤りの位置として算出する。この例では、 i = 3 , 1 で 0となるので 1 4回の演算が必要になる。

<：例 3〉受信符号語： Y0が 0 0 0 0 0 0 0 0 0 0 0 α α^ζ α' 0の壜合

[第 1 ステップ〕シンドロームの計算

受僂符号語； Υ0に対して、式 4に示す演算を行い、以下のシンドロームを得る。

S 0 = α + a ¹ + a ³ a

S 1 = a ³ + ^z a¹ + ^J a a

S j = a a ' + a¹ * -h a ⁵ a ² = 1

S j = a a ' + ² ' + ³ a ³ = a ¹¹

S _t = a' ¹ + a¹ * + a ^J a ⁴ = 1

S 5 = a a ¹⁵ + a ² a ¹⁰ + a ⁵ a:^s =な³

〔第 2ステップ〕拱り位置多項式の算出

シンドローム； S【≠ 0、かつ、 S , S , S ₂+ S , S， S₀+ S« S _l S【 + S* S , S。= aであるので、誤りの個数； j は、 j = 3である。よって、淇リ位置多項式は σ (Ζ) = 1 + σ _ι Ζ + σ ,Ζ^ί + σ， Ζ，であり、その係数は、

σ , = Ν 1 /U = ^{1 1}

σ , = Ν 2 /M = a ¹³

σ， = N 3 /U = a'

N 1 = S, S , S ₂+ S_s S ₁ S ₁ -l- S_< S , So+ S» S_J S o-l- S 4 S _J S ₁

+ s , s _s s ,

N 2 = S_< S , S ₂+ S , S _s S₀+ S _< S _s S , + S « S « So+ S _s S , S ₁ + S _s S , S , N 3 = S 6 S , S _I+ S ₃ S _s S ,+ S _< S « S ₁ + S _< S _s S ₂-i- S 5 S _> S ₁ + S _t S , S ,

M= S , S ₁ S ₂-l- S * S ₁ S ₁ + S ₃ S , S o+ S 4 S _l S o

となる。

〔第 3ステップ] バースト誤り位置の算出

骐リ偭 R ; j = 3であるので、第 3図に示すようにバーストパターン方程式； B P (ct)は、 1 + α + な ²の 1種 Sである，これを式 9に代入すれば、

y = σ _ι/Β Ρ (α) = α /( 1 + α + α ) = α , σ ( α ) = 0 を得る，従って、バースト拱リの位！！を示すパースト位置多項式； β ( α )は、

β (a) = ( I + a + a¹) a

となり、符号 Sリは受信符号 fiの右端から 2番目（な）と 3番目（α¹)と 4番目（αつの位置に存在する，

〔第 4ステップ] Rリバターンの算出および盯正

パースト拱りの位置； αの »リパターンを Ε,、位置； α¹の Κリパターンを E i、位 ϋ； α，の Kりパターンを E _tとすれば、式 5より次式を得る，

E , + E,+ E,= S ο= α"

a³ E i + ^ι E j+ a E _s = S ! = α

a' E _l + a⁴ E ₁+ a^, E ,= S i = 1

この速立方程式を解けば、 E ,= a^z、 E ,= <r'を得る. 従つて、受信符号 Sの右端から 4番目の情報； αにこの誤リバターン； E , = a . 3番目の情報； a'に Kリパターン； E,= a:、 2番目の情報 a こ Kリバターン； E ,= a，を加算し、符号》リを盯正した復号符号 15； YD= 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 を «号する，よって、本発明においては、第 3ステップにおける誤り位置の算出を 1 回の演算で行うことができる。一方、従来技術のチヱン探索法では、誤り位置多項式に Ζ = α ( i = 1 , 1 3 , · · . , 1 , 0)を逐次代入し、値が 0 を取るものを誤りの位置として箅出する„ この例では、 i = 3 , 2 , 1で 0となるので 1 4回の ¾算が必要になる。

く例 4 >受信符号語； Y0が 0 0 0 0 0 0 0 0 0 0 0 な a² な ³ aの場合〔第 1 ステップ〕シンドロームの計算

受信符号語； Υ0に対して、式 4に示す演算を行い、以下のシンドロ —ムを得る，

S 0= α + ¹ + a ³ + a = '

S 1 = α α ³ + な² α^ζ + ³ a + a = I

S 2= a a ' + ¹ * + a ³ a ² + a = ⁴

S 3 = a a ' + a ² a * + ^{3 3} + a = a¹

S = a a¹¹ + a¹ a* + ³ a* + a = a*

S5= a a^{l s} + ¹ a¹⁰+ ^{i s} + a = a'

〔第 2ステップ〕リ位置多項式の算出

シンドローム； S i≠ 0、かつ、 5 , 5 , 52+ 5 , 5 , 50+ 545 , 5 ,+ S^ S i So:な'³であるので、拱リの偭数； j は、 j = 3である，よつて、誤リ位置多項式は o CZ s l + o ! Z + a i Zz + O i Z³であり、その係数は、

σ 1 = N 1 /Μ = a ⁵

σ 2 = N 2 /M = a ³

σ , = N 3 / = a^s

N 1 - S s S j S a+ S s S t S ! + S ^ S i S o+ S i S i So+ S^ S ^ S , + S , S _s S ,

N 2 = S 4 S , S _J+ S , S , So+ S« S , S ₁ + S 4 S 4 S o + S 5 S ₁ S ₁ + S ₃ S , S

N 3 = S . S ₂ S _J + S , S _S S ₃ + S . S 4 S ₁ + S , S ₅ S _I -1- S _S S _J S ₁ + S , S _s S ₂

= S ₂ S ₁ S ₂ + S S _l S , + S _J S _s S o+ S « S _I S o

となる。

[第 3ステップ〕パースト拱リ位置の算出

默リ偭数； j = 3であるので、第 3図に示すようにバーストパターン方程式； B P (a)は、 1 + a + α^ζの 1種類である. これを式 9に代入すれば、

β y = σ , P ( ) = a / { 1 + a + a ) = 、 σ ( a ) = を得る。この場合は、 σ (γ )≠ 0となリ式 9 を潜足しない，よって、この符号誤リは訂正不能であり、これ以後の処理は中止して受信符号 S Υ0をそのまま復号符号 R： YDとして出力する，また、信号； E Dには符号誤りの梭出を示す 1 を出力する，

以上に述べだ復号例からも明らかなように、本発明によれば簡単な復号処理でパースト棋リの訂正を行うことができる.

次に、上述の 4次の原始多項式； G (X) = X* + X + 1で定義する G F ( 2 "上の元を要素とする t = 3の 3重棋リ盯正（15, 9,3) R S符号を例に、本実施例の各部の構成を詳述する.

第 7囡は、復号方法の第 1ステップにおけるシンドローム演算部 1 の —構成例図である， E X O R回路 7とシフトレジスタ回路 8 と係数乗算部 9との組み合わせで、シンドローム； S。〜S _Sの計算を行う . なお、係数乗算部 9は、係数値； 1 , α', · · · , a^sの乗算をそれぞれ行うもので、入力信号を（ a , , a ₂, a , . a ₀)とベクトル表現すると、その各出力は以下の浪算で得ることができる，

係数値 1 の乗箅；（ a，， a , , a a ₀) 係数値 α の乗算；（ a ₂, a , a s₊ a ο , a ,)

係数値 α'の乗算；（ a , a ₃ + a。， a _s+ a₂, a ₂)

係数値な ³の乗算；（ a，十 a。， a ₃+ a ₂, a ₂ + a ! , a ,)

係数値 a *の乗算；（ a， + a : , a ₂ + a , , a !+ a !+ ao, a,+ a₀) 係数黴 a 'の乗算；（ a ₂ + a , , a, + a ₂+ a。， a ₃ + a ₂) 受信符号語の各情報；（ i ,， i ₂. i ！, i 。）に対して、係数乗算部で係数値を乗算し、受信符号商の最後の情報が入力された時点で、各シフトレジスタ回路の出力からぺクトル表現のシンドロームを得る。

第 8図は、復号方法の第 2 , 第 3，第 4ステップにおけるな · a の乗算を行う回路の一構成例図である。 AND回路 1 0と EX O R回路 1 1 との組み合わせで乗算濱算を実行する，入力； a ( i ,， i 2 , i ,, i o). a ( j ,， j _{l t} j j ₀)に対して、 16理演算を行い、出力に乗算結果； α = a ' a (k _s, k ₂, k k₀)を得る。

第 9図は、復号方法の第 2 , 第 3 , 第 4ステップにおける a ' Z ii 'の除算を行う回路の一構成例図である。 R OM回路 1 2と第 8図に示した乗算回路 1 3 とで構成する. R OM回路 1 2は、入力； α ( j j ,,

- J

j ., j 。）に対してテーブルルックアップでな（ j ,, j 1 , j . J― 。）を出力する，乗算回路 1 3は、これとな（ i i 2 , i !, i o)との乗算を行い、出力に演算結果； α ' a '(k，， k k k。）を得る，

以上に述べた如く、本実施例によれば極めて簡单な復号処理で R S符号のパースト誤り訂正を行うことが可能となり、蓄積メディアなどでのバースト誤りの訂正に β著な効果を得ることができる，

次に、本発明の第 2の実施例について、第 1 0乃至 1 1図で説明する，第 1 0図は、本実施例における復号手順を示す. 第 1 0図中の第 1 、第 2、第 3、第 4ステップは、第 1 図に示した復号手順と同一である. そして、第 3ステップのバーストパターン方程式による誤り位置の算出において、バースト誤りの位置を示すバースト位 »多項式；の算出が不可能な場合（図中の不可の場合）は、新たに設けた第 5ステップで従来技術のチェン探索法による誤り位置の算出を行う。この復号処理によリ、受倌符号 Sに含まれるランダム誤りに対してその誤り位置を算出することができる，従って、本実施例による復号手順では、バースト誤リに対しては本発明の ffi号方法、ランダム拱りに対しては従来技術と同棣の盯正を行うことができる，

第 1 1図は、この復号方法を行う一構成例図である. 第 1 1図中、 1 はシンドローム演算郎、 2は轵リ位置多項式演算部、 3はバーストバターン検出部、 4は轵リパターン演算部、 5は運延部、 6は加算部、 1 4 はチェン探索 ffiである，

t重リ盯正 R S符号の受信符号； Y0は、シンドローム澳算部 1と «延郎 5とに入力する，

シンドローム演算部 1は、 «号手順の第 1ステップであるシンドロームの計算を行う . すなわち、受信符号； Y0に対して式 4に示す演算を行い、シンドロ一ム； S ^ i - O , 1 , · · · , 2 t — 1 )を算出する，そして、この S i - O , 1 , · · · ， 2 t— 1 )をシンドローム系列； Sとして出力する。なお、 S , = 0 ( i = 0 , 1， · · · , 2 t— 1 )の時は、》リ無しと判定して信号； ENに 0を出力する，一方、少なくとも 1つが S ,≠ 0の時は、信号； E Nに 1 を出力する。

リ位置多項式浪算郎 2は、復号手順の第 2ステップである誤り位置多項式； σ (Z)の係数； σ , ( i = 1 , 2 , · · · , j j ≤ t )を算出する，すなわち、倌号； E Nが 1の時に、シンドロ—ム系列； Sに対して式 8に示す如く周知のシンドローム； S ,と係数； σ ,の関係式よリ誤リの佃数： j と Κリ位 31多項式の係数； o，（ i = l , 2 , · · · , j )とを算出する。そして、この誤りの個数； j と係数； σ i = 1 , 2 , - · ， j )を係数系列； σとして出力する。

バーストパターン検出部 3は、復号手順の第 3ステップであるバース卜誤リ位置を算出する，すなわち、信号； ΕΝが 1の時に、第 3図に示した誤りの個数 jで規定されるバーストバターン方程式； B P(a)を式 9に逐次代入して γを計算する，そして、 σ (γ )= 0を满足する Υ が存在する場合は、式 1 0に示すバースト位 St多項式； 3 (α) = Β P (α)·γで算出したパースト誤りの位置を、轵リ位置系列； /3として出力する，また、信号； E Dには 0を出力する。なお、 σ ) = 0を满足する γが存在しない場合は Κリの位 Bが不明のため訂正は不可能である。したがって、この場合は誤り位置系列；にはなにも出力せず、また、信号； EDにはりの検出を示す 1 を出力する，

チェン探索部 1 4は、復号手賬の第 5ステツブの復号処理を行い、チェン探索法で誤り位置の検出をする。すなわち、信号； ENが 1、信号 EDが 1の時に、 »リ位置多項式演算部 2の出力である誤りの個数； j と誤り位置多項式の係数； σ >( i = 1 , 2， · · · ， j )の係数系列；口をもとに、チェン探索法により Kリの位 ϋを計算し、誤リ位系列； 3 /3として出力する . なお、誤り位置の検出が不可能な場合は、誤り位置系列； β βにはなにも出力せず、また、信号： EDDには誤りの検出を示す 1 を出力する，

誤リバターン演算部 4は、復号手順の第 4ステップである誤りパターン； Ε の算出を行う，すなわち、信号： ΕΝが 1の時に、棋リ位置系列； β、あるいは /9 /9とシンドローム系列； Sをもとにそれぞれ誤リ位置の誤リバターン； Ε を計算する。そして、誤りパターン系列； Εを出力する，

加算部 6は、遅延部 5で遅延させた信号； Y0Dの誤リが発生している位置に対応する拱リパターンを加算して淇リの盯正を行い、その出力にバースト誤リ訂正の復号処理を行った R S符号； Y Dを得る。

以上に述べた如く、本実施例によれば極めて簡単な復号処理で R S符号のバースト轵リ訂正を行い、かつ、ランダムリも従来技術と同様に盯正することが可能となリ、蓄積メディァなどでのバースト誤りとランダム誤リとが湿在した符号 Kリの訂正に K著な効果を得ることができる, 以上述べたように、本発明によれば、 R S符号におけるバースト誤リを極めて簡単な復号処理で訂正することができるので、蓄積メディアなどで発生するバースト糗リやランダム誤りの符号轵リの訂正に頃著な効果を得ることができる，産業上の利用可能性

以上のように、本発明にかかるリ一ドソロモン符号のパースト誤りの復号方法及び復号装置は、コンパクトディスク、ディジタル V T R等の再生装置における Rリ盯正符号の «号方法，復号装 31として有用であり，特に、 R s符号におけるバースト拱りを極めて簡单な復号処理で r正することができるので、蓄積コンパクトディスク、ディジタル V T R等の蓄積メディァなどで発生するパースト棋リやランダム轵リの符号誤リの盯正に K著な効果を得ることができる，

Claims

請求の範囲

1. 次数； mの原始多項式； G (X)で定義するガロア拡大体； G F(2 ) 上の元を要素とし、上記原始多項式； G (X)= 0の根； αによリ生成多項式； G。（X)が

G₀ (X) = (X - 1 ) (Χ - α) (Χ - α ) · · · (X - α )

で与えられる t重パイト誤り訂正リ一ドソロモン符号の復号方法において、受信符号多項式； Y (X)に対して下記に示す演算処理、

S ₀ = Y (X) mod X— 1

S , = Y (X) mod X- α

S ₂ = Y (X) mod X- α

S ,,-, = Υ (X) mod X— α

でシンドローム； S i s O , 1 , 2 , · . · , 2 t - 1 )を計算する第 1のステップと、上 3Eシンドローム； S ,の少なくとも 1つが非零の時には、上記シンドローム； S , ( i =0 , 1 , 2 , · · · , 2 t - 1 ) をもとに、次式で示す誤リ位置多項式： σ (Ζ)、

σ (Ζ)= 1 + σ , Ζ + σ , Ζ + · · · + σ , Ζ

の j個（ j ≤ t )の係数； σ , ( i = 0， 1， · · ·， j )を計算する第 2 のステップと、上記原始多項式； G (X)の根； aと、 j個の整数； 1 , P , q , · · · , r ( 1 < p < q< · · ' < r ≤ t ) の組み合わせで定まるパーストパターン方程式； Β Ρ ( α)= 1 + α + α + - · - + a より、 γ = σ ,/ Β Ρ (な）、かつ、 σ (γ ) = 0なる関係を满足するバ一ストバターン方程式； Β Ρ ( α)を探索し、 Β Ρ ( α) · γで j個のパースト轵リ位 « ; γ · £ΐ , · · · , Υ - a , γ - a , γを求める第 3のステツブと、上記 j個のパースト ISリ位直； Ύ■ a Γ , · · · , γ - a , r - α ， γと上記シンドローム； S i - O , 1 , 2 , · · · , 2 t - 1 )とをもとに、誤リ位置に対応する j個の誤リバターン； E ,, · · · , Ε ,, Ε_ρ, Ε ,を求める第 4のステップとを備え、上記シンドローム； S ,が S , = 0 ( i = 0， 1 , 2 , · . . , 2 t - 1 )の場合は、誤リなしと判定して訂正助作は行わず受倌符号をそのまま復号倌号として出力し、上記シンドローム； S ,の少なくとも 1つが非零の場合は、上記第 2、第 3、第 4のステップの手) 1によリバースト誤リ位置、および誤リパターンを求め、受信符号の上記パースト誤リ位置に対応する位置に上記誤リバターンを加算してバースト誤リの訂正勋作を行い、上記第 3のステテツブにおいて、 γ = _σ ,/、かつ、 _σ (γ ) = 0なる関係を満足する yが存在しない場合は、訂正動作を中止して受信符号に轵リが有ることを示す织り検出の «号動作を行うことを特«とする、リードソロモン符号のバーストリ復号方法。

2 . 前記第 3のステップにおいて、 γ - σ ,ΖΒ Ρ ίίτ) かつ、 σ (γ ) = 0なる係を満足する yが存在しない場合は、前記 IIリ位置多項式； σ (Ζ) - 1 + σ ₁ Ζ + σ , Ζ + · . · + σ , Ζ = 0を满足する j個の根をチェン探索法により求め、この根をもとに轵リ位 βと誤リパターンを計算し、受信符号の対応する誤り位 atに誤りパターンを加算して訂正動作を行うことを特徴とする請求の範囲第 1項に記載のリードソロモン符号のパースト ISリ復号方法.

3. 次数； mの展始多項式： G (X)で定義するガロア拡大体： G F ( 2 ) 上の元を要衆とし、上記原始多項式； G (X) = 0の根；なにより生成多項式； G。（X)が

G₀(X) = (X - 1 ) (Χ - ) (Χ - ) · · · (X - α )

で与えられる t重バイトり盯正リードソロモン符号の復号装 Bにおいて、符号長； η , 情報点数； n — 2 tの受信符号に基づいてシンドローム； S , ( i = 0 , 1 , 2 , · ' · ， 2 t — 1 )を求めシンドローム系列： S を出力するシンドローム演算手段と、

上記シンドローム系列； Sに基づいて誤りの個数； j ( j ≤ t )と誤り位置多項式； σ (Ζ) = 1 + σ ₁ Ζ + σ , Ζ + · . · + σ , Ζ の係数； σ ₍ ( i = 0 , 1 , · · · , j )とを求め係数系列； σを出力する誤り位多項式演算手段と、

上記誤りの個数； j と同一個数の整数； 1 , p , q , · · · , r ( l < Ρ < q < · · · < Γ ≤ t )の組み合わせで定まる 1以上のバーストパターン方程式； Β Ρ (α = 1 + α'+ α'+ · · · 十な 'と上記係数系列； σとから γ = σ ,ΖΒ Ρ (α)、かつ、 σ (γ )= 0の関係を満たすパ —ストパターン方程式； B P (cr)及び γを探索し、パースト位置多項式；（α) = Β Ρ (な） · γょリ j個のパーストリの位置； γ · α , · · · , γ - a , y - a , γを求め誤り位置系列； βを出力するパーストバターン'演算手段と、

上記誤リ位置系列； βと上記シンドローム系列； Sとから上記 j偭のパーストリ位置に対応する j個の誤リバターン； Ε ,, · · . , Ε,, Ερ, Ε ,を求め轵リパターン系列； Εを出力する誤りパターン演算手段と、

上記受侰符号の上記パーストリ位置に対応する位 atに上記誤リパターン系列； Eをそれぞれ加算して出力する加算手段とを有することを特徴とする t重パイト轵リ盯正リ— ドソ Πモン符号の復号装置。

4. 次数； mの原始多項式； G(X)で定義するガロア拡大体； G F ( 2 ) 上の元を要衆とし、上記展始多項式； G(X)- 0の根； αによリ生成多項式； G。（X)が

G₀(X) = (X - 1 )(Χ- α)(Χ- α ) · · · (X - ) で与えられる t重パイ卜珙リ耵正リ一ドソロモン符号の復号装!！において、

符号長； η , 情報点数； n - 2 tの受倌符号に基づいてシンド□ーム S ■ ( i = 0 , 1， 2 , · · · . 2 t — 1 )を求めシンドローム系列； S を出力するシンドローム演算手段と、

上記シンドローム系列； Sに基づいて誤りの個数； j ( j ≤ t )と誤り位置多項式； σ (Ζ) = 1 + σ ₁ Ζ + σ : Ζ + - · · + σ j Ζ の係数； σ , ( i = 0 , 1 , · ♦ * , j )とを求め係数系列； σ を出力する誤り位置多項式濱算手段と、

上記誤りの個& ; j と同一個数の整数； 1 , P， q . · · ·， r ( 1 < P < q < - · · < r ≤ t )の組み合わせで定まる 1以上のバーストパターン方程式； B P ( a) = l + a + + ♦ · · + α と上記係数系列

； σとから γ - σ ,Ζ Β Ρ ία) かつ、 σ (γ ) = 0の関係を满たすパ一ストバターン方程式； Β Ρ (α)及び yを探索し、パースト位置多項式； β ( a) = B P (α) · γより j個のパースト轵リの位置； γ · α , · ·

· , r - α , γ - a , γを求め第 1の Kリ位置系列；を出力するパーストバタ一ン濱算手段と、

上記 iSリ位置多項式； σ (Ζ) = 1 + σ , Ζ + σ , Ζ + · · ■ + a , Ζ と上記係数系列： σとからチェン探索法によリ j個のリの位置を求め第 2の轵リ位 B系列； 3 /3 を出力するチェン探索手段と、

上記第 1 の誤り位置系列； 3或いは第 2の珙リ位 B系列； 0と上 Ei シンドローム系列； Sとから上記 j個のパースト誤リ位 S或いは上 K j 個の ISリの位置に対応する j個の Sリバターンを求め誤リバターン系列

Eを出力する SSリバターン演算手段と、

上記受儅符号の上記バースト骐リ位齜戒いは上記誤り位 Sに対応する位置に上記 ¾Sリバターン系列； Eをそれぞれ加算して出力する加算手段とを有し、

上記バーストパターン演算手段において、ァ = σ ,ΖΒ Ρ(ίΐ)、かつ、 σ ( γ )= 0の関係を満足する γが存在しなかった場合は、上記誤リバタ一ン演算手段が上記チェン探索手段からの上記第 2の誤り位 S系列 β βに基づいて誤りパターンの算出を行なうことを特徴とする t重バイト誤リ訂正リードソロモン符号の復号装 38。