JPS60143027A - Ｂｃｈ符号の復号装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 「産業上の利用分野」 この発明は、　ＢＣＨ符号の復号方法、特にユークリッ
ドの互除法を用いて、エラーロケーション多項式及びエ
ラーエバリユエーション多項式をめる復号方法に関する
。

「背景技術とその問題点」 ＢＣＨ符号のひとつであるリードソロモン符号の復号方
法の概略について説明する。ここでは、符号長がｎで、
情報／ンボル数がｋで、最小距離ｄが（ｎ−に＋　１−
２　ｔ　＋　１　）となり、生成多項式％式％ 】 符号（を個のシンボルの訂正可能）について説明する。

最初に受信語（ｒ、ｒ、ｒ’、・・ｒｎ−’　）から、
シ０　１　２ ンドロームＳｊ（ｊ＝ｏ　、　１　、・・・ｄ−２）を
める。

Ｓｊ＝　Σ　５αＩＪ １壬Ｏ 次に、シンドロームを用いてエラーロケーション多項式
δ（ｚｌ　及Ｕ工２−エバリユエーション多項式ω（Ｚ
）をめる。この方法のひとつとして、ユークリッドの互
除法を用いたものがある。

求められたエラーロケーション多項式（δ（２）＝０）
を解いてエラーロケーションｘ１　をめる。

ソシテ、エラーロケーションＸｉ　トエラーエバリュエ
ーンヨン多項式ω（ｚ）からエラー値Ｙｉ　をめる。

上述のエラーロケーション多項式δ（Ｚ）及びエラーエ
バリユエーション多項式ω（ｚ）ハ、５（ｚ）ヲンンド
ローム多項式とすると、ｚ、２　ｊ　とＳ　（ｚ）の最
大公約多項式をめるユークリッドの互除法の過程でまる
ことが証明されている。これは、次のアルゴリズムであ
る。

Ｕ　−＋　（ｚ）　−〇　、　＋　ＵＯ（Ｚ）　−１と
設定する。これらの多項式に関して次の演算を行ない、
ｒｉ（ｚ）及びＩＪｉ　（ｚ）をめる。

ｒｌ−ｚ（ｚ）÷ｒ、　−、（ｚ）　＝　ｑｉ　（Ｚ）
　°゛＋　ｒ、（ｚ）ｔＪｉ　（ｚ）　＝　ｔＨ−２（
ｚ）　＋　Ｕｌ−＋（ｚ）　ｑｉ　（ｚ）但し、ｒ（ｚ
）の次数より、ｒ、　、（ｚ）の次数が犬であ１　１− る。この演算を繰り返し、ｒ（ｚ）の次数がｔより小】 さくなったら、演算を止める。この時、エラーロケーシ
ョン多項式δｆＺ）及びエラーエバリユエーション多項
式ω（Ｚ）は、下式のようにめられる。

δ（ｚ）　＝　Ｕｉ　（ｚ）　／　Ｕｉ　（０）ω（ｚ
）　＝　ｒ　ｉ　（ｚｌ　／　Ｕｉ　（０）上述のアル
ゴリズムを実現するための従来の復号器は、レジスタの
シフト動作が必要であった。

シフト動作を行なうハードウェアとしては、データバス
に複数のレジスタを接続し、ソフトしたいレジスタから
データバスにデータを取り出し、隣のレジスタに書込む
構成が知られている。この方法では、シフトするレジス
タの数だけ、ステップが必要となる欠点がある。他のハ
ードウェアとしては、複数のレジスタの段間にデータセ
レクタを挿入し、データバスからのデータと前段のレジ
スタからのデータとをデータセレクタによシ選択できる
ようにし、シフト動作の時は、前段のレジスタからのデ
ータを選択する構成がある。このハードウェアによれば
、シフト動作をトステソゾで行なうことができるが、デ
ータセレクタのためにハードウェアの規模が大きくなる
問題が生じる。これらの理由により、復号器を実現する
うえでは、シフト動作を必要としないことが好ましい。

「発明の目的」 この発明の目的は、レジスタのシフト動作が必要とされ
ないＢＣＨ符号の復号方法の提供を目的とするものであ
る。この発明に依れば、復号器のノ・−ドウエアを簡略
化できると共に、復号速度の向上を図ることができる。

「発明の概要」 この発明は、第１のレジスタに初期値を設定すると共に
、第２のレジスタには、７ントロームを含む初期値を設
定し、第１及び第２のレジスタの内容を被除数及び除数
に対応させ、第１及び第２のレジスタの内容を用いてユ
ークリッドの互除法により、エラーロケーション多項式
及びエラーエバｌ）ユニージョン多項式をめるようにな
し、第１のレジスタの初期値として（１，１００・・・
Ｏ）（但し１．はＵとｒの境界を示す）を設定し、第２
のレジスタの初期値として、（００，５（ｚ））（但し
１．はＵとＳ　（ｚ）の境界を示し、Ｓ　（ｚｌはシン
ドローム多項式を示す。）を設定することを特徴とする
ＢＣＨ符号の復号方法である。

「実施例」 以下、この発明の一実施例について説明する。

この一実施例は、（ｔ＝３）で、ＧＦ（２’）上のリー
ドソロモン符号に対してこの発明を適用したものである
。

第１図において、３１は、各４ビツトの（２ｔ＋２．＝
８）個のレジスタからなるレジスタ群を示し、３２は、
各４ビツトの８個のレジスタからなるレジスタ群を示す
。これらのレジスタ群３１゜３２の各レジスタ゛の内容
は、ノくスノくノファ及びデータバスを介してＧＦ（２
’）の演算回路に供給されると共に、演算結果がデータ
ノくス及びノぐスノくツファを介して各レジスタに供給
される。

第１図Ａは、レジスタ群３１及び３２に初期値がセント
された状態である。αは、（Ｘ４＋ｘ＋１−〇）の根で
、（α１５　＝１　）であり、０及び１は、夫々ＧＦ（
２’）上の学兄及び単位光である。レジスタ群３１には
、初期値として、（Ｕｏ（ｚ）−１＋　ｒ−ｓ（ｚ）　
＝　ｙ、６）即ち（１，１００００００）がセットされ
る。レジスタ群３２には、初期値として、（Ｕ−＋（ｚ
）＝０　、　Ｓ　（ｚ）　）がセットされる。コンマ「
、」は、データの位置情報であって、初期状態では、レ
ジスタ群３１におけるコンマは、Ｕｌｒとの境界を表わ
し、レジスタ群３２におけるコンマは、ＵとＳ　（ｚ）
の境界を表わしている。この第１図に示す例では、ンン
ドローム多項式の一例として下記のものを想定している
。

ｒｏ（ｚ）　＝　Ｓ　（ｚ）−α７ｚ５＋α７ｚ４＋α
目　ｚ３＋　α’１．ｚ２＋　α１４ｚ＋α４ ユークリツドの互除法を用いて、エラーロケーション多
項式δ（２）及びエラーロケーション多項式ω（ｚ）を
めるには、下記のような（ｒ（Ｚ）−ｒｌ−０−２ （ｚ）　−ｑ　ｉ　（ｚ）・・ｒｉ（ｚ））の演算がな
される。

ｒ−１（ｚ）÷ｒｏ（ｚ）　＝　ｑ、（ｚ）　−−ｒ、
　（ｚ）ＣＩ、１（Ｚ）−α８ｚ＋α８ ｒｌ（ｚ）＝αｚ４＋α３ｚ２＋α２ｚ＋α１２ｒｏ（
ｚ）　’−ｒ、（ｚ）　＝　Ｑ２（Ｚ）　−−Ｔ２（ｚ
）％　２（Ｚ）　＝α６２６＋α６ Ｔ２（ｚ）＝α２ｚ３＋　ｚ２＋α２’ｚ　＋　α７ｒ
１（ｚｌ已ｒ、、（ｚ）　＝　ｑ３（ｚ）・・・Ｔ３（
ｚ）ｑ３（ｚ）＝α１４　、Ｚ　＋　（１１２ｒ３（Ｚ
）−α８ｚ２＋Ｚ＋αに の演算は、第２図に示すような計算で表わすことができ
る。Ｔ３（ｚ）の次数が（ｔ＝３　）より小となったの
で、上述の演算は、この段階で終えられる。

捷た、下記に示すように、（Ｕｌ（ｚ）−Ｕｌ−２（ｚ
）＋０１−、（ｚｌ　ｑｉ　（ｚｌ　）の演算が行なわ
れる。

Ｕ、（ｚ）　−〇−＋、　（ｚ）　＋　Ｕｏ（ｚ）　ｑ
＋（ｚ）　＝α８ｚ＋α８Ｕ２（ｚ）−Ｕ。（ｚ）　＋
　ｕ、（ｚ）　ｑ２（Ｚ）−αｌ４ｚ２＋α３Ｕ３（Ｚ
）　＝　ＴＪｔ（ｚ）　＋　Ｕ、、（ｚ）　ｑ３（ｚ）
＝α！３ｚ３＋α”ｚ２＋　ｚ　十（１２そして、 δ（ｚ）　＝　Ｕ、（ｚ）　／　Ｕ３（０）　＝　Ｕ３
（ｚ）　／α２＝（Ｚ　Ｉ　ｌ　ｚ　３　＋（１９ｚ２
　＋（１１３ｚ　４−１ω（ｚ）　−Ｔ３（ｚｌ　／　
Ｕ３（０）　−Ｔ３（ｚ）　／α２＝α６ｚ２＋α１３
ｚ＋α４ によシ、エラーロケーション多項式δｆｚ）及びエラー
エバリユエーション多項式ω（ｚ）がまる。

上述のｒｉ（ｚ）及びＵｉ　（ｚ）をめるために、レジ
スタ群３１及び３２が用いられる。レジスタ群３１の各
レジスタの内容を右側から順にＴｏ　＋　Ｔ＋　＋　Ｔ
２　＋・・・・Ｔ７とし、レジスタ群３２の各レジスタ
の内容を右側から順にＢ。、　Ｂ１＋　Ｂ２’　・・・
Ｂ７とする。第１図Ａに示すように初期値を設定した後
に、レジスタ群３１及び３２のコンマの位置の右側のレ
ジスタの内容Ｔ６及びＢ５の除算を行ないＡの値をめる
。

第１図Ａでは、（Ａ＝１−α７＝α８）となる。このＡ
をレジスタ群３２の各レジスタの内容に乗算し、その乗
算出力にレジスタ群３１の対応するレジスタ（上側のレ
ジスタ）の内容Ｔ１　を加算し、この加算出力をレジス
タ群３１に書込む。第１図Ａの最も右側の１対のレジス
タでは、（α８×α４−１−Ｑ＝＝＝α１２）がめられ
、これが第１図Ｂに示すように、レジスタ群３１の右端
から２番目のレジスタに書き込まれる。即ち、レジスタ
群３１及び３２のコンマの位置の差をａとすると、レジ
スタ群３１には、（Ｔｉ　＋Ａ　ｘ　１３ｉ−ａ）又は
（Ｔｉ　＋　Ａ　Ｘ　Ｂｉ＋ａ）の結果がＴ１　とし書
込まれる。

また、レジスタ群３１の右端側から右側のコンマの位置
まで、（Ｂｉ　十Ａ　Ｘ　Ｔ＋　）の演算がなされ、そ
の出力がレジスタ群３２のレジスタＢｉ　に七ノ゛トさ
れる。第１図Ｂでは、α８がＢ６にセットされる。

この第１図Ｂに示す状態で（Ａ＝１÷α７−α８）がめ
られ、上述と同様の演算及びレジスタの書き替えがなさ
れる。そして、第１図Ｃに示すように、ｒ、（ｚ）及び
ＴＪｔ（ｚ）がめられる。コンマの位置は、コンマの右
側のレジスタの内容がＯでなくなるまでずらされる。

次に、再び、第１図Ｃ２第１図Ｂ、第１図Ｃの順序てな
された除算動作と同様の除算動作が第１図Ｃ２第１図り
、第１図Ｅに示すようになされる。

ここで、第１図Ｃに示すように、レジスタ群３１及び３
２の夫々のコンマの位置が逆転しているので、レジスタ
群３１の各レジスタの内容がＢｉ　とされ、レジスタ群
３２の各レジスタの内容がＴ１とされて処理がなされる
。したがって、第１図Ｃの状態では、（Ａ＝α７÷α＝
α６）となる。第１図Ｅに示す状態で第２回目の除算が
終了し、ｒ２（ｚ）及びＵ２（Ｚ）がまる。レジスタ群
３１及び３２の内容は、第２図に示す演算過程と対応し
ている。

第１図Ｅ、第１図Ｆ及び第１図Ｇは、３回目の除算動作
を行なう時のレジスタ群３１及び３２の内容を示し、第
１図Ｇに示すようにｒ３（ｚ）及びＵ３（Ｚ）が捷る。

この時、レジスタ群３１のコンマの位置から、ｒ３（ｚ
）の次数が（ｔ−３）より小さくなったことが検出され
、レジスタ群３１及び３２の内容から、前述のように、
エラーロケーション多項式及びエラーエバリユエーショ
ン多項式をめることができる。

上述のこの発明の一実施例が適用されたり一トソロモン
符号の復号器の構成を第３図に示す。

第３図において、１，２，３，４，５，６，７゜８は、
夫々４ビツトのレジスタを示し、これらのレジスタ１〜
８によってレジスタ群３１が構成される。同様に、各４
ビツトのレジスタ９，１０゜１１．１２，１３，１４，
１５．１６によってレジスタ群３２が構成される。レジ
スタの各々は、双方向のパスバッファを介してデータバ
ス１γと接続されている。このデータバス１１には、　
ＧＦ（２４）の演算回路１８及びゼロ検出回路１９が接
続される。ゼロ検出回路１９は、コンマの位置をずらす
ための検出データを発生する。

２０は、レジスタ群３１のコンマ位置と対応する出力を
発生するカウンタてあり、２１は、レジスタ群３２のコ
ンマ位置と対応する出力を発生するカウンタである。カ
ウンタ２０及び２１の出力が減算回路２２に供給され、
カウンタ２０及び２１の出力の夫々が比較回路２３及び
２４に供給される。減算回路２２は、２つのレジスタ群
３１及び３２のコンマの位置関係を検出するためのもの
である。比較回路２３及び２４は、レジスタ群３１及び
３２のコンマの位置から剰余ｒ、　（ｚ）の次数がｔよ
り小さくなることを検出するためのものである。

ゼロ検出回路１９、減算回路２２、比較回路２３及び２
４の夫々の出力がジャンプ先指定用のＲＯＭ　２５に供
給される。レジスタ１〜１６、レジスタ１〜１６の夫々
に付加されているノ（スノくソファ、演算回路１８など
の制御を行なうコントロール信号は、プログラムＲＯＭ
　Ｚ　６から読出されるマイクロ命令をコマンドデコー
ダ２７によって解読することで発生する。ゾログラムＲ
ＯＭ　２６には、プログラムカウンタ２８からアドレス
が供給される。プログラムカウンタ２８には、ジャンプ
先指定用のＲＯＭ　２５からのジャンプアドレスが供給
される。ゼロ検出回路１９などの出力がジャンプアドレ
スを発生させるためのフンデインヨンデータとして用い
られる。

「発明の効果」 この発明に依れば、初期値の設定を従来のものと異なら
せることにより、レジスタの／フト動作を行なわずに、
エラーロケーション多項式及びエラーエバリユエーショ
ン多項式をめることができる。したがって、この発明に
依れば、復号器の回路規模が大規模になったシ、復号の
ためのステップ数が増大する問題点を解決することがで
きる。

【図面の簡単な説明】

第１図はこの発明の一実施例の説明に用いるレジスタの
内容の変化を示ず路線図、第２図はこの発明の一実施例
の説明に用いる演算過程を示す路線図、第３図はこの発
明が適用された復号器の一例のブロック図である。１ １７・−・・・・・データバス、１８・　演算回路、２
６−・・・・・・プログラムＲＯＭ、３１．３２　−・
・・・・レジスタ群。 代理人　杉　浦　正　知 −Ｕ＋　（Ｚ）　ｒ　２　（Ｚ）− 第２図

Claims (1)

【特許請求の範囲】
1. 第１のレジスタに初期値を設定すると共に、第２のレジ
   スタには、シンドロームを含む初期値を設定し、上記第
   １及び第２のレジスタの内容を被除数及び除数に対応さ
   せ、上記第１及び第２のレジスタの内容を用いてユーク
   リッドの互除法により、エラーロケーション多項式及び
   エラーエバリユエーション多項式をめるようになし、上
   記第１のレジスタの初期値として（１、１００・・０）
   （但し１．はＵとｒの境界を示す）を設定し、上記第２
   のレジスタの初期値として、（００，５（ｚ））（但し
   １．はＵとＳ　（ｚ）の境界を示し、Ｓ　（ｚ）は７ン
   ドロ一ム多項式を示す。）を設定することを特徴とする
   ＢＣＨ符号の復号方法。