JPH0434785B2

JPH0434785B2 -

Info

Publication number: JPH0434785B2
Application number: JP58039816A
Authority: JP
Inventors: Hiroichi Okano
Original assignee: Individual
Current assignee: Individual
Priority date: 1983-03-09
Filing date: 1983-03-09
Publication date: 1992-06-09
Also published as: JPS59165153A

Description

【発明の詳細な説明】（産業上の利用分野）本発明は、エラーの訂正、特に４重誤り訂正
BCH符号（リードソロモン符号を含む）の復号
装置に関するものである。

（従来の技術）情報処理システムの高信頼度化の一手法とし
て、誤り訂正符号が実用されている。BCH符号
（リード・ソロモン符号を含む）は特に誤り訂正
能力が高く重要な符号であるが、復号器が複雑と
なる欠点を有する。

BCH符号の復号は、例えば、宮川、岩垂、今
井著「符号理論」（昭晃堂」7.3章に示されてい
る。BCH符号の復号は次の５つの過程からなる。

(1) 受信系列からのシンドロームの算出 (2) 誤り位置多項式の係数および誤りビツト数の
判定ピーターソンの方法、バーレンカンプ・マツシ
イの方法、ユークリツド互除法等の方法がある。
また、誤り訂正数が４以下なら、あらかじめ各係
数をシンドロームで表す式を求めておいて、復号
時にそれにシンドロームを代入する方法も有効で
ある。

(3) 誤り位置多項式の解法チエインの、全ての元を方程式に代入する方法
が一般的であるが、誤り訂正数が４以下なら、
直接、方程式を解くのが効率がよい。

(4) 誤りの大きさの算出（２元BCH符号につい
ては不要） (5) 誤り訂正の実行さて、一般的復号法として、1972年にMITプ
レス社から出版されたピーターソンおよびウエル
ドン共著の「エラー訂正符号」第２版の第９章を
要約する。

BCH符号の生成多項式は最小距離をｄとする
とα^r，α^r+1，…α^r+d-2を根とする多項式であり、
シンドロームは次式で与えられる。

ただし、ｒは任意の整数、αはGF（2^m）上の原
始元である。

S_j＝_t 〓ⁱ⁼¹ Y_iX_i ^j，ｒ≦ｊ≦ｒ＋ｄ−２ (1) ここで、ｔは実際に生じた誤りの数、Y_iは誤り
の大きさX_iは誤り位置数である。最大訂正能力を
t₀（≧ｔ）とすると、ｄ＝2t₀＋１である。２元
BCH符号のときY_iは０か１である。

また、誤り位置多項式の係数σ_iとシンドローム
との関係は次式で与えられる。

S_jσ_t＋S_j+1σ_t-1＋…＋S_j+t-1＋S_j+t＝０ (2) ここで、ｒ≦ｊ≦ｒ＋2t₀−１−ｔである。

式(2)を解いてσ_i（１≦ｉ≦ｔ）を求める。つい
で、誤り位置多項式 X^t＋σ₁X^t-1＋…＋σ_t＝０ (3) を解き、誤り位置数および誤りの大きさを求めて
誤りの訂正を実行する。

さて、４重誤り訂正２元BCH符号の復号につ
いて概説する。リードソロモン符号についても原
理は同様であるのので説明を省く。GF（2^m）の原
始元をαとし、α，α³，α⁵，α⁷を根とする多項式
をm₁（ｘ），m₃（ｘ），m₅（ｘ），m₇（ｘ）とする
と、４重誤り訂正BCH符号の生成多項式は、Ｇ（ｘ）＝m₁（ｘ）m₃（ｘ）m₅（ｘ）m₇（ｘ）
(4) である。このとき、符号長ｎ＝2^m−１である。

シンドロームは受信系列をm₁（ｘ），m₃（ｘ），
m₅（ｘ），m₇（ｘ）で割つたときの剰余をそれぞ
れR₁（ｘ），R₃（ｘ），R₅（ｘ），R₇（ｘ）とすると
次式で表わされる。

S₁＝R₁（α） S₃＝R₃（α³） S₅＝R₅（α⁵） S₇＝R₇（α⁷） (5) シンドロームS₁〜S₇はシフトレジスタ、あるい
は、ソフト的には、シフトレジスタの演算を模擬
した、シフト演算法を用いると容易に算出され
る。なお、ガロア体GF（2^m）上の元はベクトル表
現と指数表現とで表わされる。

誤り位置多項式の係数はバーレカンプーマツシ
イ法あるいはユークリツド互除法等で算出でき
る。また、各係数は、シンドロームを用いて式し
ておくことができるが、それぞれの誤り数に対応
した式が必要となる。

誤り位置多項式の解法のために、４重誤りの場
合はガロア体の４次方程式を解くことになるが、
従来、方程式に全ての元を代入するチエインの解
法によつていた。このため、多くの復号ステツプ
を要した。しかし、古典代数学を応用したガロア
体の４次方程式の解法が発見され、これを用いた
復号法および復号装置が提示された。これによつ
て、４重誤り訂正BCH符号の高速復号が実現し
た（特開昭57−182253号明細書および岡野、“誤
り位置多項式の直接解法による３重および４重誤
り訂正BCH符号の復号”、電子通信学会論文誌、
vol.J64−Ａ No.２、pp.137−144、昭56.2）。この
方法を以下、「岡野の解法」と称す。また、その
ほかにもガロア体の方程式を解法するいくつかの
方法がある（R.T.Chien，B.E.C unningham，
and l.B.Oldham，“Hybrid methods for fiding
roots of apolynomial with application to
BCHdecoding，”IEEE Trans.lnform.Theory，
Vol.IT−15，PP.329−335，1969.）。

ここでは、効率のよい「岡野の方法」の概略を
述べるにとどめる。

まず、ガロア体の４次方程式の直接解法を要約
する。

X⁴＋σ₄₁x³＋σ₄₂x²＋σ₄₃x＋σ₄₄＝０ (6) さて(6)式はガロア体上の方程式なので、古典代数
学の公式はそのまま用いることができない。しか
し、次のようにすると解くことができる。

まず、(6)式の根をxi（ｉ＝１，２，３，４）と
すると、Ｙ＝（x₁＋x₂）（x₃＋x₄）を根とする２次
の補助方程式として次式を得る。

λ³＋ηλ＋δ＝０ (7) ここで、η＝σ₄₂ ²＋σ₄₂σ₄₃， δ＝σ₄₃ ²＋σ₄₁ ²σ₄₄＋σ₄₁σ₄₂σ₄₃ (8) さて、(6)が次式のように固数分解されるとする。

（x²＋px＋ｑ）（x²＋p′x＋q′）＝０ (9) (6)式、(9)式の各係数を比較して、ｐ＋p′＝σ₄₁ (10) ｑ＋q′＋pp′＝σ₄₂ (11) p′q＋pq′＝σ₄₃ (12) qq′＝σ₄₄ (13) さらに、Ｙの定義からＹ＝pp′ (14) したがつて、(7)式の根の一つＹを求め、x²＋
σ₄₁x＋Ｙ＝０を解き、ｐ，p′を求め、x²＋（σ₄₂＋
Ｙ）ｘ＋σ₄₄＝０を解き、ｑ，q′を求める。そし
て、(12)式を満足する（ｐ，ｑ），（p′，q′）の組を
求めれば、x²＋px＋ｑ＝０を解きx₁，x₂が、x²
＋p′x＋q′＝０を解きx₃，x₄が算出される。

なお、２次および３次方程式の解法は、上記、
岡野の文献などに示されている。これらの解法に
ついては後述の実施例で改良した方法を述べるの
でここでは省略する。

さて、上記復号方法および装置では、方程式を
直接解法する方法を用いた場合、４重誤りに対し
ては、４次方程式を解く部分、さらに、３重以下
の誤りに対しては、３次以下の方程式を解く部分
が必要である。

（発明が解決しようとする課題）従来の４重誤り訂正BCH符号の復号装置では、
チエインの全ての元を代入する方法は効率が悪
い。また、直接誤り位置多項式を解法する場合
は、４重誤りに対する訂正部分と３重以下の誤り
に対する訂正部分を別々に必要としたので、復号
装置が複雑になり、ソフトウエア量、ハードウエ
ア量が多い等の難点があつた。

本発明は高速に復号でき、しかも従来よりソフ
トウエア量、ハーウエア量の少ない４重誤り訂正
BCH符号の復号装置を提供することを目的とし
ている。

（課題を解決するための手段）本発明に係る４重誤り訂正BCH符号（リード
ソロモン符号を含む）の復号装置は、受信語を保
持しておくための受信語保持手段と、受信語から
のシンドロームSiを発生させるためのシンドロー
ム生成手段と、Siがすべて零の場合誤り無しとす
る誤り無し判定手段と、誤り位置多項式σ（ｘ）
の係数を算出する誤り位置多項式の係数算出手段
と、３次以下の誤り位置多項式の係数を４次多項
式の係数に変換する係数変換手段と、４次および
３次以下の多項式を、すべて４次式として解法可
能な、ガロア体上の４次方程式解法手段と、４次
方程式の根のうち零元を除く誤り位置数（リード
ソロモン符号のときは、さらに、誤りの大きさを
求めて）をもとに受信語の誤りを訂正する誤り訂
正実行手段とを含むことを特徴とする。また、請
求項２の発明に係る４重誤り訂正BCH符号（リ
ードソロモン符号を含む）の復号装置は、請求項
１の(4)に対応して、ガロア体上の４次方程式σ
（ｘ）＝x⁴＋ σ₄₁x₃＋σ₄₂x²＋σ₄₃x＋σ₄₄＝０を解くための(イ)な
い
し(ニ)の手段を含むことを特徴とする。ただし、以
下の方程式の各係数が零でも根が算出可能であ
る。

(イ) ３次の補助方程式 λ³＋ηλ＋δ＝０を解き、
根Ｙを求めるための３次方程式解法手段。

ここで、 η＝σ₄₂ ²＋σ₄₂σ₄₃， δ＝σ₄₃ ²＋σ₄₁ ²σ₄₄＋σ₄₁σ₄₂σ₄₃ (ロ) x²＋σ₄₁x＋Ｙ＝０を解き、根ｐ，p′を求め、 x²＋（σ₄₂＋Ｙ）ｘ＋σ₄₄＝０を解き、ｑ，q′を
求めるための２次方程式解法手段。

(ハ) p′q＋pq′＝σ₄₃を満たす、（ｐ，ｑ），（p′
，q′）
の組を求めるための２次方程式係数対算出手
段。

(ニ) x²＋px＋ｑ＝０を解き、x₁，x₂を、x²＋p′x
＋q′＝０を解きx₃，x₄を算出する２次方程式解
法手段。

また、請求項３の発明に係る４重誤り訂正
BCH符号の復号装置は、誤り位置多項式の係数
を下記の(イ)，(ロ)によつて算出する誤り位置多項式
の係数算出手段を含むことを特徴とする。

(イ) Ａ＝S₁（S₁ ⁵＋S₅）＋S₃（S₁ ³＋S₃）≠０であれ
ば、３，４ビツト誤りと判定し、誤り位置多項
式σ（ｘ）の係数は次式より求める。

σ₄₁＝S₁， σ₄₂＝｛S₁（S₁ ⁷＋S₇）＋S₃（S₁ ⁵＋S₅）｝／Ａ， σ₄₃＝｛S₁（S₁ ³S₅＋S₁S₇）＋（S₁ ⁶＋S₃ ²）｝／Ａ， σ₄₄＝｛S₁ ³（S₁ ⁷＋S₇）S₃（S₁ ⁷＋S₁S₃ ²＋S₇）＋S₅
（S₁ ⁵＋S₁ ²S₃＋S₅）｝／Ａ， (ロ) Ａ＝０であれば、１，２ビツト誤りと判定
し、誤り位置多項式σ（ｘ）の係数は次式より
求める。

σ₄₁＝σ₂₁＝S₁， σ₄₂＝σ₂₂＝（S₁ ³＋S₃）／S₁ σ₄₃＝０ σ₄₄＝０また、請求項４の発明に係る４重誤り訂正BCH
符号（リードソロモン符号を含む）の復号装置
は、４重誤り以上の訂正能力を持つ符号におい
て、４重誤り以下の誤りが発生したときに本復号
装置を適用することを特徴とする。

（作用）本発明による４重誤り訂正復号装置では、高速
復号のままで、３重以下の誤りも一括４重誤りと
して訂正することを可能としている。したがつ
て、４重以下の誤りと判定された場合は、すべ
て、４重誤りを訂正するアルゴリズムのみで訂正
される。

（実施例）以下、本発明の実施例を図面を参照して具体的
に説明する。

第１図は第１の発明に係る４重誤り訂正BCH
符号（リードソロモン符号を含む）の復号装置の
機能的ブロツク図、第２図は同復号装置の作動の
手順を示すフローチヤートである。第３図ないし
第７図はROM（リードオンリ・メモリ）を用い
た同復号装置の具体的一実施例である。

さて、第１図の４重誤り訂正BCH符号（リー
ドソロモン符号を含む）の復号装置の機能的ブロ
ツク図について説明する。受信語保持手段１に受
信語を保持しておく。シンドローム主成手段は２
は受信語からシンドロームSiを発生させる。つい
ので、誤り無し判定手段３はSiがすべて零の場合
誤り無しとする。誤り位置多項式の係数算出手段
４は誤り位置多項式σ（ｘ）の係数を算出する。
係数変換手段５は３次以下の多項式の係数を４次
多項式の係数に変換する。４次方程式解法手段６
はガロア体上の４次および３次以下の多項式を、
すべて４次方程式として解法する。誤り訂正実行
手段７は４次方程式の根のうち零元を除く誤り位
置数（リードソロモン符号のときは、さらに、誤
りの大きさを求めて）をもとに受信語の誤りを訂
正する。なお、４次方程式の解法にはいくつかの
方法がある。

請求項２に係る発明は、「岡野の４次方程式の
解法」を用いる場合であつて、第１図の４次方程
式σ（ｘ）＝x⁴＋σ₄₁x³＋σ₄₂x²＋σ₄₃x＋σ₄₄＝０の
解
法手段６の構成要素として、次の３つの手段を含
む。ただし、以下の方程式の各係数が零でも根が
算出可能であるように工夫されている。３次方程
式解法手段６１は３次の補助方程式を解く。２次
方程式解法手段６２は、２次方程式を解く。係数
対算出手段６３は２次方程式として解くべき係数
の対を求める。

さて、実施例における復号装置の作動につき、
第１図、第２図を参照して説明する。なお、第２
図のフローチヤートの説明中、Ｓ１，Ｓ２…は処
理手順（ステツプ）の番号を示す。まず、Ｓ１に
おいて受信語保持手段１に受信語を保持してお
く。Ｓ２でシンドローム生成手段２は受信語から
シンドロームSiを発生させる。ついで、Ｓ３で誤
り無し判定手段３はSiがすべて零の場合、Ｓ４で
誤り無しとする。Ｓ５で誤り位置多項式の係数算
出手段４は誤り位置多項式σ（ｘ）の係数を算出
する。Ｓ６で係数変換手段５は３次以下の多項式
の係数を４次多項式の係数に変換する。ついで、
Ｓ７で４次方程式解法手段６はガロア体上の４次
および３次以下の多項式を、すべて４次式として
解法する。Ｓ８で誤り訂正実行手段７は４次方程
式の根のうち零元を除く誤り位置数（リードソロ
モン符号のときは、さらに、誤りの大きさを求め
て）をもとに受信語の誤りを訂正する。

請求項２に係る発明は、「岡野の４次方程式の
解法」を用いる場合であつて、第２図の４次方程
式σ（ｘ）＝x⁴＋σ₄₁x³＋σ₄₂x²＋σ₄₃x＋σ₄₄＝０の
解
法のための処理手順として、次の５つの手順を含
む。ただし、以下の方程式の各係数が零でも根が
算出可能である。まず、３次方程式解法手段６１
はＳ７１でη＝σ₄₂ ²＋σ₄₂σ₄₃，δ＝σ₄₃ ²＋σ₄₁ ²σ_4
4
＋σ₄₁σ₄₂σ₄₃を求め、さらに、Ｓ７２で３次の補助
方程式λ³＋ηλ＋δ＝０を解き、根Ｙを求める。
Ｓ７３で２次方程式解法手段６２は、x²＋σ₄₁x＋
Ｙ＝０を解き、根ｐ，p′を求め、x²＋（σ₄₂＋Ｙ）
ｘ＋σ₄₄＝０を解き、ｑ，q′を求める。Ｓ７４で
係数対算手段６３はp′q＋pq′＝σ₄₃を満たす、
（ｐ，ｑ），（p′，q′）の組を求める。そして、Ｓ
７５で２次方程式解法手段６２はx²＋px＋ｑ＝
０を解き、x₁，x₂を、x²＋p′x＋q′＝０を解きx₃，
x₄を算出するさて、以上で本願発明の実施例の要点を述べ
た。本発明の核となるのはつぎの発想である。つ
まり、例えば、x²＋px＝０を解くとき、（ｘ＋
ｐ）ｘ＝０として解く。通常このように、方程式
の次数を下げることを考える。しかるに本発明で
は、x²＋px＋ｑ＝０を解くとき、x⁴＋px³＋qx²
＋Ox＋Ｏ＝０と４次方程式にし、４次方程式を
直接解法して、根のうち不要な０を除く。数学的
には、これは自明で有用でない思考方法であろ
う。しかし、工学的には有用で本発明において
は、この方法を用いて、４重および３重誤りの訂
正を一括４重誤り訂正装置で訂正可能とし、復号
装置のハードウエア、ソフトウエア量を減少せし
めた。

さて、以上述べた原理の実現方法の一例として
「岡野の４次方程式の解法」を用いた場合につい
て詳述する。まず、本発明の構成要素となる３次
以下のガロア体の方程式の解法について述べる。
４次方程式の解法に適用できるように各係数が０
の場合にも解けるように工夫している。

（一次方程式の場合）ｘ＋σ₁₁＝０ (15) の根はｘ＝σ₁₁である。

（二次方程式の場合） x²＋σ₂₁x＋σ₂₂＝０ (16) (16)式の根はσ₂₁＝０のとき x₁＝x₂＝δ₂₂ ^1/2 もちろん、σ₂₁＝０，σ₂₂＝０のとき根は０，０で
ある。

つぎに、σ₂₁≠０のときｘ＝σ₂₁yとおき y²＋ｙ＋σ₂₂／σ₂₁ ²＝０ (17) (17)式の根をσ₂₂／σ₂₁ ²に対応したテーブルに格
納しておく。根をy₁，y₂とすると、(16)式の根は、 x₁＝σ₂₁y₁，x₂＝σ₂₁y₂＝σ₂₁＋x₁ となる。

なお、σ₂₁≠０かつσ₂₂＝０のとき(17)式の根は
α⁰，０となり、 x₁＝σ₂₁，x₂＝０となる。

（三次方程式の場合）つぎの３次方程式の解法を考える。

y³＋ηy＋δ＝０ (18) (18)式において、 η＝０のとき、ｙ＝δ^1/3 もちろん、η＝０，δ＝０のとき、Ｙ＝０であ
る。

つぎに、η≠０のときｚ＝η^-1/2ｙとおき、 z³＋ｚ＋δ／η^3/2＝０ (19) を得る。(19)式の根をδ／η^3/2に対応したテーブル
に格納しておく。

根をzi（ｉ＝１，２，３）とすると(18)式の根は
Yi＝η^1/2zi（ｉ＝１，２，３）となる。

なお、η≠０かつ、δ＝０のとき(19)式の根ｚ
は、０，α⁰である。

さて、つぎに誤り位置多項式の解法について述
べる。

（４ビツト誤りの場合）誤り位置多項式は、 x⁴＋σ₄₁x³＋σ₄₂x²＋σ₄₃x＋σ₄₄＝０ (6) となるが、この解法は、実施例で述べた。

（３ビツト誤りの場合）誤り位置多項式は、 x₃＋σ₃₁x²＋σ₃₂x＋σ₃₃＝０ (20) となる。(20)式にｘをかけて０を加え、４次方程式
とみなして次式を得る。

x⁴＋σ₃₁x³＋σ₃₂x²＋σ₃₃x＋０＝０ (21) (21)式は(6)式と同様にして解くことができる。

すなわち、(21)式の根をxi（ｉ＝１，２，３），x₄
＝０とすると、Ｙ＝（x₁＋x₂）（x₃＋０）を根とす
る３次の補助方程式として次式を得る。

λ³＋ηλ＋δ＝０ (22) ここで、 η＝σ₃₂ ²＋σ₃₁σ₃₃ δ＝σ₃₃ ²＋σ₃₁σ₃₂σ₃₃ (23) したがつて、(21)式と(6)式と比較して、ｐ＋p′＝σ₃₁ (24) ｑ＋q′＋pp′＝σ₃₂ (25) p′q＋pq′＝σ₃₃ (26) qq′＝０ (27) (6)式を解く場合と同様に、(22)式の根Ｙ＝
pp′と(24)式よりx²＋σ₃₁x＋Ｙ＝０の根として、
ｐ，p′が求まる。

ついで、(25)式、(27)式より、 x²＋（σ₃₂＋Ｙ）ｘ＋０＝０ (28) の根としてｑ，q′を得る。(28)式は(16)式と同様に
して解くいて、（ｑ，q′）＝（σ₃₂＋Ｙ，０））とな
る。ここで、ｐ，q′＋pq′＝σ₃₃の成立する（ｐ，
ｑ）、（p′，q′）の組を求める。

そして、（ｐ，ｑ）＝（ｐ，σ₃₂＋Ｙ），（p′，q′
）＝
（p′，０）より、それぞれ(16)式の解法を用いて、
（２１）式の根x₁，x₂，x₃，x₄＝０を得る。

０＝（零元）は誤り位置を示さないから、根xi
より０を除いておけば良い。

以上述べたように、(20)式もσ₄₁とσ₃₁，σ₄₂とσ₃₂，
σ₄₃とσ₃₃，を対応させσ₄₄＝０とすると、４次方程
式とみなして(6)式の解法を用いて良いことが分か
つた。

（２ビツト誤りの場合）誤り位置多項式は、 x₂＝σ₂₁x＋σ₂₂＝０ (29) となる。

前項と同様にσ₄₁＝σ₂₁，σ₄₂＝σ₂₂，σ₄₃＝σ₄₄＝
０
として４次方程式として解くことができる。

なお、このとき、(7)式に対応する式が λ³＋σ₂₂ ²λ＋Ｏ＝０ (30) となり根はＹ＝０，σ₂₂となるがＹ＝０を用い
る方が効率が良い。以下、前項と同様にして、
x₁，x₂，x₃＝x₄＝０を得る。

（１ビツト誤りの場合）誤り位置多項式はｘ，σ₁₁＝０ (31) となる。同様にσ₄₁＝σ₁₁，σ₄₂＝σ₄₃＝σ₄₄＝０とし
て４次方程式として解くことができる。なお、こ
のとき(7)式に対応する式が λ³＋Oλ＋Ｏ＝０ (32) となるが、根はＹ＝０である。以下、前項と同様
にして、x₁，x₂＝x₃＝x₄＝０を得る。

以上によつて、３ビツト以下の誤り位置多項式
も４ビツトの誤り位置多項式として解法できるこ
とが分つた。

つぎに、誤り位置多項式の係数の算出法につい
てはいろいろな方法がある。請求項３に係る発明
は、誤り位置多項式の係数を下記の(イ)，(ロ)によつ
て算出する。

σ₄₁＝S₁， σ₄₂＝｛S₁（S₁ ⁷＋S₇）＋S₃（S₁ ⁵＋S₅）｝／Ａ， σ₄₃＝｛S₁（S₁ ³S₅＋S₁S₇）＋S₃（S₁ ⁶＋S₃ ²）｝／
Ａ， σ₄₄＝｛S₁ ³（S₁ ⁷＋S₇）＋S₃（S₁ ⁷＋S₁S₃ ²＋S₇）＋
S₅（S₁ ⁵＋S₁ ²S₃＋S₅）｝／Ａ， (33) (ロ) Ａ＝０であれば、１，２ビツト誤りと判定
し、誤り位置多項式σ（ｘ）の係数は次式より
求める。

σ₄₁＝σ₂₁＝S₁， σ₄₂＝σ₂₂＝（S₁ ³＋S₃）／S₁ σ₄₃＝０ σ₄₄＝０ (34) 証明は簡単であるので省略する。

さらに、請求項４に係る発明は、４重誤り訂正
に加えて、それ以上の誤り訂正および検出能力を
持つBCH符号（リードソロモン符号を含む）の
復号において、４重以下の誤りと判定した場合
に、請求項１および請求項２および請求項３の復
号手段を用いることである。現在、５次以上の方
程式の有効な解法はないので、５重誤り以上はチ
エインの方法で全ての元を代入して根を求め、４
重以下の誤りについては本発明の復号装置を用い
れば、効率の良い復号がなされる。

さて、つぎにROM（Read Only Memory）を
用いた４重誤り訂正BCH符号の復号器の具体的
な一実施例について述べる。回路では、元を指数
表現としその指数０，１，…，2^m−２を用い０元
は全て１、つまり、（111…１）で表わすこととす
る。なお、以下の説明で０元は０、他の元はαⁱ
（０≦ｉ≦2^m−２）を用いる。

まず図３に基本回路を示す。(a)は元の乗算、(b)
は元の乗算、(c)は元の加算を表わす。これらの回
路は０元を含んだ演算も可能であるようにする。
これらの回路は既に知られている。

図４はx²＋σ₂₁x＋σ₂₂＝０の解法手段（SV2）
であり、(16)式の解法を実現する手段である。×２
は元の２乗を求める回路、÷２は平方根を求める
回路である。ROM２１は(17)式、y²＋ｙ＋Ci＝０
の根を格納するROMである。係数σ₂₁，σ₂₂が０
でも根を求めることができるようにするために
は、０の平方根を０とし、ROM２１は、入力０
に対して出力を０とα⁰としておけば良い。

なお、SWA２はσ₂₁＝０のとき下側、σ₂₁≠０
のとき上側とする。

つぎに、図５はλ³＋ηλ＋δ＝０の解法手段
（SV３）であり、３根のうち１根を求める手段で
ある。×３は元の３乗を求める回路であり、
ROM３３は(19)式、z³＋ｚ＋Ci＝０の根を求める
ためのROMである。ROMC４は立方根を求める
回路である。係数η，δが０でも根を求めること
ができるようにするためには、０の立方根は０，
ROM３３は入力０に対して出力０を得るように
しておけば良い。なお、SWB５は、η＝０のと
き下側、η≠０のとき上側とする。図６は誤り位
置多項式の係数を算出する手段（CG）である。
（３３）式におけるＡ＝S₁（S₁ ⁵＋S₅）＋S₃（S₁ ³＋S₃）
が、Ａ≠０のときSWC８は下側となり、３また
は４ビツト誤りを判定し、Ａ＝０のときSWC８
は上側となり、１または２ビツト誤りと判定す
る。そして、誤り位置多項式を４次方程式とみな
して係数σ_4i（ｉ＝１，２，３，４）を算出する。

なお、CG１６は(34)式によつて、σ₄₁＝σ₂₁＝
S₁，σ₄₂＝σ₂₂，σ₄₃＝０，σ₄₄＝０を算出する回路
であり、CG２７は(33)式によつて、σ₄₁＝S₁、
σ₄₂，σ₄₃，σ₄₄を算出する回路である。

さて、図７は、４重誤り訂正BCH符号の高速
復号装置のブロツク図である。受信語を保持する
手段は図では省略している。SG９は受信語から
のシンドロームS₁，S₃，S₅，S₇の算出手段。CG
１０は下記の(イ)ないし(ハ)の操作を行つて、誤り位
置多項式σ（ｘ）の係数を算出する手段。

(イ) S₁＝S₃＝S₅＝S₇の場合誤り無しと判定する。

(ロ) Ａ＝S₁（S₁ ⁵＋S₅）＋S₃（S₁ ³（S₁ ³＋S₃）≠０で
あ
れば、３，４ビツト誤りと判定し、誤り位置多
項式σ（ｘ）の係数を(33)式より求める。

(ハ) Ａ＝０であれば、１，２ビツト誤りと判定
し、誤り位置多項式σ（ｘ）の係数を(34)式よ
り求める。

ついで、下記の(イ)ないし(ホ)の操作を行つて、誤り
位置多項式σ（ｘ）＝x⁴＋σ₄₁x³＋σ₄₂x²＋σ₄₃x＋σ_4
4
＝０の根を算出する。ただし、以下の各方程式は
その係数が零でも根が算出可能である。

(イ) CC11はη＝σ₄₂ ²＋σ₄₂σ₄₃，δ＝σ₄₃ ²＋σ₄₁ ²
σ₄₄
＋σ₄₁σ₄₂σ₄₃を算出する。

(ロ) SV3 12は３次の補助方程式λ³＋ηλ＋δ＝０
を解き、根をＹを算出する。

(ハ) SV2 14はx²＋σ₄₁x＋Ｙ＝０を解き、根ｐ，
p′を求め、x²＋（σ₄₂＋Ｙ）ｘ＋σ₄₄＝０を解き、
根ｑ，q′を求める。

(ニ) PC15はp′q＋pq′＝σ₄₃を満たす、（ｐ，ｑ），
（p′，q′）の組を求める。

(ホ) SV2 14はx²＋px＋ｑ＝０を解き、根x₁，x₂
を、x²＋p′x＋q′＝０を解きx₃，x₄を算出する。

さらに、上記σ（ｘ）の根x₁，x₂，x₃，x₄のう
ち、零元を除き訂正を実行するが図では省略して
いる。この第７図のブロツク図はそのままLSI化
して高速な復号器が実現できる。

なお、本発明の４重誤り訂正BCH符号（リー
ドソロモン符号を含む）の復合装置はマイクロコ
ンピユータ等のプログラムによるソフトウエアや
ガロア体シユミレータ等でソフト的に実現でき、
また、LSI・論理回路のようなハードウエアであ
れば超高速復号が実現可能である。光磁気デイス
ク、デイジタル・ビデオなど多くの分野に適用で
きる。

（発明の効果）本発明は、以上詳述したように、４重誤り訂正
BCH符号（リードソロモン符号を含む）の復号
装置において、高速復号のままで、４重および３
重以下の誤りも一括４重誤りとして訂正すること
を可能としている。したがつて、４重以下の誤り
を訂正する復号アルゴリズムを４重誤りを訂正す
るアルゴリズムのみで構成可能となり、３重以下
の誤りを訂正する復号部分が不要となつた。

４次方程式の直接解法としては「岡野の解法」
が有効であるが、その他の４次方程式の解法も本
発明に対して有効である。

なお、請求項３の発明における誤り位置多項式
の係数の算出においても、４，３ビツト誤り、お
よび２，１ビツト誤りの場合が、それぞれ同一の
式で算出される。また、４ビツト誤りと３ビツト
誤りとの区別を判定する部分が不要となつてい
る。

したがつて、本発明は、ソフトウエア量および
ハードウエア量の少ない４重誤り訂正BCH符号
（リードソロモン符号を含む）の復号装置を実現
している。

【図面の簡単な説明】

第１図は第１の発明に係る４重誤り訂正BCH
符号（リードソロモン符号を含む）の復号装置の
機能的ブロツク図。１……受信語保持手段。２……シンドローム生
成手段。３……誤り無し判定手段。４……位置多
項式の係数算出手段。５……係数変換手段。６…
…４次方程式解法手段。６１……３次方程式解法
手段。６２……２次方程式解法手段。６３……係
数対算出手段。７……誤り訂正実行手段。第２図は同復号装置の作動の手順を示すフロー
チヤート。第３図は演算の基本回路。第４図はx²＋σ₂₁x＋σ₂₂＝０の解法手段。１……y²＋ｙ＋C_i＝０の根を求めるROM 第５図はλ³＝ηλ＋δ＝０の解法手段。３……z³＋ｚ＋C_i＝０の根を求めるROM、４
……立方根を求めるROM、第６図は誤り位置多項式の係数を算出する手
段。６……σ₂₂を算出する回路、７……σ₂₂，σ₄₃，
σ₄₄を算出する回路、第７図は４ビツト誤り訂正BCH符号の復号装
置のブロツク図。９……シンドローム生成手段、１０……誤り位
置多項式の係数算出手段、１１……η，δ算出出
手段、１２……λ³＋ηλ＋δ＝０の解法手段、１
３……元の和を求める回路、１４……x²＋σ₂₁x＋
σ₂₂＝０の解法手段、１５……（ｐ，ｑ），（p′，
q′）の組を求める手段。

Claims

【特許請求の範囲】１符号長ｎのBCH符号の受信符号を受取り、
誤り位置多項式の係数を求めて、その根を算出す
ることにより、上記受信語における４重以下の誤
りを訂正する、下記の(1)ないし(7)の手段を含むこ
とを特徴とする４重誤り訂正BCH符号（リード
ソロモン符号を含む）の復号装置。 (1) 上記受信語を保持しておくための受信語保持
手段。 (2) 上記受信語からのシンドロームSiを発生させ
るためのシンドローム生成手段。 (3) Siがすべて零の場合誤り無しとする誤り無し
判定手段。 (4) 誤り位置多項式σ（ｘ）の係数を算出する誤
り位置多項式の係数算出手段。 (5) ３次以下の多項式の係数を４次多項式の係数
に変換する係数変換手段。 (6) ４次および３次以下の多項式を、すべて４次
式として解法可能な、ガロア体上の４次方程式
解法手段。 (7) ４次方程式の根のうち零元を除く誤り位置数
（リードソロモン符号のときは、さらに、誤り
の大きさを求めて）をもとに受信語の誤りを訂
正する誤り訂正実行手段。２請求項１の６項における４次方程式σ（ｘ）＝
x⁴＋σ₄₁x³＋σ₄₂x²＋σ₄₃x＋σ₄₄＝０の解法手段とし
て、(イ)ないし(ニ)の手段を含むことを特徴とする請
求項１記載の４重誤り訂正BCH符号（リードソ
ロモン符号を含む）の復号装置。ただし、以下の方程式の各係数が零でも根が算
出可能である。 (イ) ３次の補助方程式 λ³＋ηλ＋δ＝０を解き、
根Ｙを求めるための３次方程式解法手段。ここで、 η＝σ₄₂ ²＋σ₄₂σ₄₃， δ＝σ₄₃ ²＋σ₄₁ ²σ₄₄＋σ₄₁σ₄₂σ₄₃ (ロ) x²＋σ₄₁x＋Ｙ＝０を解き、根ｐ，p′を求め、 x²＋（σ₄₂＋Ｙ）ｘ＋σ₄₄＝０を解き、ｑ，q′を
求めるための２次方程式解法手段。 (ハ) p′q＋pq′＝σ₄₃を満たす、（ｐ，ｑ），（p′
，q′）
の組を求めるための２次方程式係数対算出手
段。 (ニ) x²＋px＋ｑ＝０を解き、x₁，x₂を、x²＋p′x
＋q′＝０を解きx₃，x₄を算出する２次方程式解
法手段。３請求項１の(4)において、誤り位置多項式の係
数をシンドロームＳ１，Ｓ３，Ｓ５、Ｓ７を用い
て、下記の(イ)，(ロ)によつて算出する誤り位置多項
式の係数算出手段を含むことを特徴とする請求項
１，２記載の４重誤り訂正BCH符号の復号装置。 (イ) Ａ＝S₁（S₁ ⁵＋S₅）＋S₃（S₁ ³＋S₃）≠０であれ
ば、３，４ビツト誤りと判定し、誤り位置多項
式σ（ｘ）の係数は次式より求める。 σ₄₁＝S₁， σ₄₂＝｛S₁（S₁ ⁷＋S₇）＋S₃（S₁ ⁵＋S₅）｝／Ａ， σ₄₃＝｛S₁（S₁ ³S₅＋S₁S₇）＋S₃（S₁ ⁶＋S₃ ²）｝／
Ａ， σ₄₄＝｛S₁ ³（S₁ ⁷＋S₇）＋S₃（S₁ ⁷＋S₁S₃ ²＋S₇）＋
S₅（S₁ ⁵＋S₁ ²S₃＋S₅）｝／Ａ， (ロ) Ａ＝０であれば、１，２ビツト誤りと判定
し、誤り位置多項式σ（ｘ）の係数は次式より
求める。 σ₄₁＝σ₂₁＝S₁， σ₄₂＝σ₂₂＝（S₁ ³＋S₃）／S₁ σ₄₃＝０ σ₄₄＝０４４重誤り訂正に加えて、それ以上の誤り訂正
および検出能力を持つBCH符号（リードソロモ
ン符号を含む）の復号において、４重以下の誤り
と判定した場合に、請求項１および請求項２およ
び請求項３の復号手段を用いることを特徴とする
請求項１および請求項２および請求項３記載の４
重誤り訂正BCH符号（リードソロモン符号を含
む）の復号装置。