JPS61258536A - ２重誤り証正復号器 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、リード・ソロモン符号（以下Ｒ３符号と記
す）の復号器に関するものであり、特に２市誤り位置の
算出を簡単、かつ高速に行なうようにしたものである。

〔従来の技術〕

以下、第２図の符号フローチャーｌ−に従って、Ｒ３符
号の復号法について述べる。２重誤りまでを訂正できる
Ｒ３符号として、下記の様なパリティ検査マＩ−リソク
スＨを用いるものが知られている。

・・・（１１ ここで、αは例えばｃＦ　（２８）の原始多項式の根で
ある。又ｎは符号長である。

復号を行なうには、まずステップ３０にてエラーシンド
ロームＳが計算される。これは符号しｎの受信データＲ
の転置行列ＲＴとパリティ検査マｌ−リノクスＩ−［と
の債で求められる。つまり、Ｖ　ｆＺｌを送信符号ベク
トル Ｖ　（Ｚｌ　＝　Ｖ　Ｑ■ｖ１ｚ■Ｖ２　Ｚ２■Ｖ３　
Ｚ３■・・・・・・■Ｖ　ｎ−＋ｚ　ｎ−１・・・（３
）Ｒ（７，１を受信ベクトル Ｒｆｚｌ−ｒＯＣ＋ｒ１　ｚ■ｒ２Ｚ２■ｒ３Ｚ３■・
・・・・・■ｒ　ｙｌ−ＩＺｎ’　　　・・・（４）と
する時、雑音のある通信路で加算される誤りパターンは
、 ｅ　（ｚ）　＝　ｒ　（Ｚ）■Ｖ　（Ｚｌ−ｅＱ■ｅＩ
Ｚ■ｅ２Ｚ２ ■・・・・・・■ｅｎ−ＩＺ”　　　・・・（５）で表
わせる。式（２）より、 ５Ｋ＝ｒＯ■ｒ１　’ｃｔ　Ｋ■ｒ２（αＫ）２■ｒ３
　　（αＫ）３■・・・・・・ ■ｒ　ｎ−１’　（αＫ）ｎ−’ ・・・（６） なので、式（５）と式（６）より ５Ｋ−Ｖ　（αＫ）■ｅ　（αＫ）　　　　　　・（７
１となる。一方、αＯ９α１．α２．α３は符号多項式
Ｖ　（Ｚ）の根だから、■（αＫ）−〇となる。従って
、 ５Ｈ＝ｅ　　（αＫ）　　　　　　　　　　　　　・・
・（８）ｅ　（ｚｌが２個の誤りをもつ誤りパターンと
すると、シンドロームは式（９）のようになる。

誤り訂正は、このｅｌ、ｅＪ＋　　α１．αｊに関する
方程式を解くことに基づいて行なわれる。ｙｌ。

αｊが求まると、べきｉ、ｊがｅ　（ｚｌの誤り位置を
示し、ｅｌ、ｅＪが求まるとｅ　（ｚｌの誤り数値を示
していることになる。そこで、シンドローム成分Ｓｌか
らｅｉ、ｅｊ、　　αｉ、αｊを求める手法を説明する
。

誤り位置多項式を次のように定義する。

σ（Ｚ）−（Ｚ■αｊ）（Ｚ■αｊ） ＝ａｏＺ２■σＩＺ■ｔｙ２　　　＝（１０）ここで、 式（９）１式（１１）は、べき相対称式と呼ばれるもの
で、次の関係を導くことができる。

式（１２）によりシンドローム成分Ｓｉより誤り位置多
項式σ１．σ２を求めることができる（ステップ３１．
３２）。ここで式（１０）の誤り位置多項式の根（αｉ
、α３）が何らかの方法で求めることができたとすると
、誤り数値ｅｉ、ｅＪは次のように求めることができる
（ステップ３３）。

以上のように、誤り位置多項式の根が求まれば、式（１
３）により誤り位置、誤り数値が求まり、式（５）によ
り復号を完了させることができる（ステップ３４）。

ここで、σｆＺｌの根を求めるために考案されたデータ
（Ｃｈｉｅｎ）の方法〔文献：　　Ｒ，Ｔ、Ｃｈｉｅｎ
　；　ＣｙｃｌｉｃＤａｃｏｒｄｉｎｇ　Ｐｒｏｃｅｄ
ｕｒｅ　ｆｏｒ　ｔｈｅ　Ｂｏｓｅ−Ｃｈａｕｄｈｕｒ
ｉＨｏｃｑｕｅｎｇｈｅｍ　Ｃｏｄｅｓ、　ＩＥＩＥＥ
　Ｔｒａｎｓ、　ｏｎ　ＩｎｆｏｒｍａｔｉｏｎＴｈｅ
ｏｒｙ＋　Ｉ↑−１０，ＰＰ　３５７−３６８．　Ｏｃ
ｔ、１９６４　）について説明する。

式００）において、σ１／σ２−η１．σＯ／σ２−η
２とすると１ ．７　ｔｚ＋　＝　１■η１ｚ■η２Ｚ２　　　　　−
（１４）と変形できる。

α／　　（０≦β≦ｎ−１）が誤り位置であるとすると
、次式が成り立つ。

σ（α７１）＝１■η１αｌ■η２α２ｐ−０・・・（
１５） この式より、復号器では、η１αｌ、η２α２！ｌを作
成し、和 η１αｐ■η２α２１　　　　　　　・・・（１６）を
計算する。もしこの和が１になれば、αＲはσ（７，１
の根であり誤り位置を示す。従ってデータの方法は誤り
位置として考えられる値（α０．αｌ。

α２．・・・、αｎ−１）をすべてσ（２１に代入し、
σ（Ｚｌ＝０を満たせば、その時代入した値が誤り位置
であることが判るという方法である。

第３図にデータの方法による誤り位置の算出を実行する
ハードウェアを示す。図中、１はデータの人出力、デー
タ処理、及び制御等を行なうマイクコプロセッサ、２は
マイクロプロセンサーのデータバス、３はマイクロプロ
センサーのコントロールバス、４．５は２人力セレクタ
、６．７はレジスタ、８はα乗算器、１３はα２乗算器
、１゜は３人力排他的論理加算器、１１ば零検出器であ
る。

動作を順に説明すると、 １）マイクロプロセッサ１よりの制御信号でセレクタ４
，５をＡ副入力にセットする。

２）マイクロプロセンサーよりデータバス２を介して前
述のη１をセレクタ４のＡ副入力からレジスタ６に入力
し、マイクロプロセンサーからのコントロール信号でη
１をレジスタ６にホールドする。

３）マイクロプロセッサ−よりデータバス２を介して前
述のη２をセレクタ５のＡ副入力からレジスタ７に入力
し、マイクロプロセンサーからのコントロール信号でη
２をレジスタ７にホールドする。

４）マイクロプロセンサーからの制御信号でセレクタ４
，５をＢ副入力にセットする。

５〉レジスタ６の出力とレジスタ７の出力と、さらに“
１”との排他的論理和を排他的論理加算器１０で計算す
る。

６）排他的論理加算器１０の出力を零検出器１１に入力
し、零であるか否かを判定し、その結果をコントロール
バス３を介してマイクロプロセッサ１に知らせる。

７）レジスタ６の出力をα乗算器８でα倍し、これをセ
レクタ４のＢ副入力を介してレジスタ６にマイクロプロ
セッサ１のコントロール信号によりホールドする。同時
にレジスタ７の出力をα２乗算器１３でα２倍し、これ
をセレクタ５のＢ副入力を介してレノスタフにマイクロ
プロセッサ１のコントロール信号によりホールドする。

この過程を、５→６−７−５−６→７→・・・・・・−
５−６と、符号長ｎ回繰り返し実行する。マイクロプロ
セッサｌ内では、繰り返し数とその時の零検出器１１か
らの信号を監視し、零検出された時の繰り返し数を誤り
位置と判断する。

〔発明が解決しようとする問題点〕

従来のデーンの方法を用いた復号器は以」−のように構
成されているので、誤り位Ｍを算出するのに符号長ｎ回
の繰り返し演算を実行しなければならず、復号時間等に
余裕がない場合にはこの繰り返し演算の回数を削減する
ことが必要で、また、ただ単にこの繰り返し演算の回数
を削減しようとすればハードウェアの規模が大きくなっ
てしまうなどの問題点があった。

この発明は上記のような問題点を解消するためになされ
たもので、誤り位置を算出するのにハードウェアの規模
は全く同じで、繰り返し演算回数を符号長の半分の回数
（ｎが偶数の場合ｎ／２゜奇数の場合（ｎ−１）／２　
　）で実行できる２重誤り訂正復号器を（Ｍることを目
的とする。

〔問題点を解決するための手段〕

この発明に係る２重誤り訂正復号器は、誤り位置多項式
の根を求める際、該多項式の係数σ２の値により簡単な
前処理を施して上記多項式の根として考えられる値を半
分に削減する前処理演算子段と、該演算手段により得ら
れた各値に乗算を繰り返して実行するとともに、各値の
排他的論理加算を施して該加算結果が零か否かを検出し
、零になるまでの繰り返し数により２重誤り位置を求め
る誤り位置検出手段とを設けたものである。

〔作用〕

この発明においては、前処理により誤り位置多項式の根
として考えられる値をほぼ半分に削減したから、誤り位
置を求めるのに従来の半分の繰り返し演算で実行可佳と
なり、復号時間は大幅に短縮される。

〔実施例〕

ここで、本発明の詳細な説明する前にその原理について
説明する。

符号長はｎであるので、ｉ、ｊ、ｎの間には次の関係が
ある。

０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−１・・・（１７）第４図
はこの関係を基にしたｉとｊの全ての＃Ｈｅ７ｊ合わせ
表を示す図である。１とｊの交点にはｉ→−ｊの値を示
しである。誤り位置多項式の係数σ２は式（１１）より
次のように考えられる。

σ２−α１・αｊ−αｉ＋３　　　　　　・・・（１８
）つまりσ２からｉ＋ｊを求めることができる。ここで
第４図のｉとｊの組み合わせ表の意味は、ｉ＋ｊが゛与
えられることにより、ｉとｊの存在範囲を明確にしよう
というものである。ところで、前にも説明したようにα
１．αｊは誤り位置多項式（］０）の異なる２根である
ので、ｉ−ｊの範囲ばｉ。

ｊの範囲の対象外である。またｉとｊの組み合わせは、
ｉの値とｊの値が入れ替っても差支えない。

従って第４図において三角形の斜線を引いた部分が、実
際の’＋　　Ｊの組み合わせの範囲となる。

例えば、ｉ＋ｊが１の場合（ｔ、ｊ）の組み合わせは（
１，０）の１組、ｉ＋ｊが２の場合（２゜０）の１組、
・・・・・・、ｊ→−ｊが５の場合（５，０）。

（４，１）（３，２＞の３組、・・・・・・というよう
に、’＋　　Ｊの組み合わせが定まる。この中で一番多
くの組み合わせが存在するのばｉ＋ｊがｎ−１の場合で
ある。その組み合わせの数は以下のようになる。

これらのことから、σ２が与えられると（ｉ。

ｊ）の組み合わせの数は最大（１９）式で示される値に
まで絞ることができる。

では次に、これらの組み合わせの中から１組を選びだす
方法について述べる。原理的には先に説明したデーンの
方法と同じで、（ｔ、　　ｊ）の組み合わせを全て代入
し、次式を満たせばそのときの（ｉ、ｊ）が根となる。

σ１−αｌ■αｊ　　　　　　　　　・・・（１１）　
’式（１１）　’　を変形して αｊ　　　αｊ １−□＋□　　　　　　・・・（２０）σ　１　　　　
　　　σ　１ の式を満たしても同様である。但し本発明では考えられ
る最大の組み合わせ数は式（１９）となり、デーンの方
法と比べると半分に減っている。

この処理方法を、第５図の前処理のフロー図と第６図の
原理図と用いて説明する。

ます、ステップ３５にてｉ＋ｊがｎ−１より大きいか小
さいかで場合分りを行ない、Ｌｌ、Ｌｊの値を決定する
。このＬｌ、Ｊは第６図の繰り返し演算の初期値となる
ものである。例えばｊ＋ｊがｎ−１より小さく、５の場
合、ステップ３７にてＬｉ　＝５．　１−３　＝０とな
る。またｊ→＝Ｊがｎの場合、ステップ３６にてＬｉ　
＝ｎ−１，，Ｌｊ　−１となる。Ｌｉ、Ｌｊが求まると
αＬｉ、　　αＬ　ｊ変換を行ない、さらにσ１で割り
算し、αＬｉ／σ１．αｌ・ｊ／σ１を出力する。

第６図において、１３．１４はレジスタ、１５はα乗算
器、１６は１／α乗算器、１７は排他的論理加算器、１
８は零比較器である。この回路は、考えられる（ｉ、ｊ
）の組み合わせにおいて、式（２０）を順番に計算する
回路である。まず、了、零でなければ、αＬｉを１／α
倍、αＬ　Ｉをα倍し、 を計算する。零ならば計算終了、零でなければ、さらに
繰り返し演算を続ける。この繰り返し回数をＣｏとする
と、 ・・・（２３） なるＣＯを見つけるわけである。この繰り返し演算の回
数は最高式（１９）で示される値である。ＣＯが求まる
と、次式により誤りの位置ｉ、ｊを求めることができる
。

表　　１ 表１は横軸にｉ、縦軸にｊをとった場合のｉ　−１−ｊ
の値を示す。また表２は同じく横軸にｉ、縦軸にｊをと
った場合のαｌ■αｊの値を示す。さらに表３及び表４
に、計算に必要なＸ−αＸ変換テーブル、αＸ−Ｘ変換
テーブルを示している。ここで、αはＣＦ　（２Ｂ）の
原始元であり、Ｘ８■Ｘ４■Ｘ３■Ｘ２■１を生成多項
式とし、αｏ＝１からα、α２．α３．・・・・・・　
を表現したものである。

表４において、零元には該当する対数表現（αＸ→Ｘ）
は存在しないので、２５５で便宜上表現している。

ここで、符号長ｎ−１６の２重誤り訂正可能なリード・
ソロモン符号を考える。誤り位置が３番目と１２番目と
すると、誤り位置多項式は以下のようになる。

（Ｚ＋α３）（Ｚ＋α１２） −Ｚ２■（α３■α１２）Ｚ■α３・α１２−Ｚ２■１
９７Ｚ■３８ ＝Ｚ２■σＩＺ■σ２ 実際の復号器でば、このσ１とσ２が与えられるわけで
ある。そこで本発明の原理に基づいて誤り位置を求めて
いく。

σ２−３８より、３８−αｉ＋ｌ、故に１−１−ｊ＝１
５第５図の前処理フロー回通りに計算すると、ｎ−１６
より、　　Ｌｉ　＝１５　　、ＬＪ　＝０となる。次に
第６図に従って繰り返し演算を行なう　（表２参照）。

最　　初　α１−　■αＩ昨　■１＝１４５■１≠０第
１回目　α１明−１■αレコ４■１　＝　２４７■１≠
０第２回目　α１１−２■αｔ３１“λ■１＝１５１■
１≠０第１＝目　α四ｑ−３■α１３１３■１−１■１
−０繰り返し数Ｇｏ＝３の場合、式（２３）を満たずこ
とがわかる。これより、各数値を式（２４）に代入して ｉ　＝１５−３　＝１２ ｊ　＝　Ｏ＋　３　＝　３ となり、誤り位置３．１２を求めることができる。

第１図に上記本発明の原理に基づいて構成された復号器
の具体的なハードウェアの一実施例を示す。図中、第３
図と同一符号は同−又は相当部う〕を示し、９は１ｉＵ
乗算器である。

この実施例の動作を簡単に説明すると、１）マイクロプ
ロセッサ１よりの制御信号でセレクタ４，５をＡ側入力
にセットする。

２）マイクロプロセンサ１よりデータバス２を介して前
述の（αＬ　１　）　／σ１をセレクタ４のＡ側入力か
らレジスタ６に入力し、マイクロプロセッサ１からのコ
ンＩ・ロール信号で（αＬｉ）／σ１をレジスタ６にポ
ールｌ”する。

３）マイクロプロセッサ１よりデータバス２を介して前
述の（αＬｉ）／σ１をセレクタ５のＡ側入力からレジ
スタ７に入力し、マイクロプロセッサ１からのコントロ
ール信号で（αＬ　ｌ　）　／σ１をレジスタ７にホー
ルドする。

４）マイクロプロセッサ１からの制御信号でセレクタ４
，５をＢ側入力にセン１−する。

５〉レジスタ６の出力とレジスタ７の出力と、ざらに“
１”との排他的論理和を排他的論理加算器１０で求める
。

６）抽伯的論理加算器１０出力を零検出器１１に入力し
てこれが零であるか否かを判定し、その結果ヲコントロ
ールハス３を介してマイクロプロセッサ１に知らせる。

７）レジスタ６の出力をα乗算器８でα倍し、これをセ
レクタ４のＢ　ｆｆ１ｌ＋入力を介してレジスタ６にマ
イクロプロセッサ１のコントロール信号によりホールド
する。同時にレジスタ７の出力を１ｉＵ乗算器９で１ｉ
Ｕ倍し、これをセレクタ５のＢ側入力を介してレジスタ
７にマイクロプロセッサ１のコントロール信号によりホ
ールドする。

この過程を５→６→７−１５→６→７→・・・・・・→
５−６と式（１９）で示した回数分繰り返し実行する。

さらにマイクロプロセッサ１内では繰り返し数と、その
時の零検出器１１からの信号を監視し、零検出された時
の繰り返し数より式（２２）を用いて誤り位置を算出す
る。

このような本実施例では、誤り位置多項式の根を求める
際、簡単な前処理を施して根として考えられる値を半分
に削減し、これにより繰り返し演算を実行するようにし
たので、従来と同様の構成で、大幅な復号時間の短縮を
図ることができる。

なお、」−記実施例では、マイクロプロセッサを用いて
データの入出力制御を行なった場合について説明したが
、データの入出力制御を専用のハードウェアで行なって
もよ（、上記実施例と同様の効果を奏する。

〔発明の効果〕

以」二のように、この発明によれば、２重誤り位置を求
める際、誤り位置多項式の根として考えられるｎ個の値
を全て代入するのではなく、該多項式の係数σ２を用い
て簡単な前処理を施し、根として考えられる値を半分の
ｎ／２１固（ｎ：偶数。

ｎが奇数の場合は（ｎ−１）／２（１ｉＵ）に削減し、
従来の半分の繰り返し演算で実行できるようにしたので
、復号時間の大幅な短縮が図れる効果がある。

【図面の簡単な説明】

第１図はこの発明の一実施例による２重誤り訂正復号器
を示すブロック図、第２図は一般の）夏号の手順を示す
フローチャート図、第３図は従来の復号器を示すブロッ
ク図、第４図は本発明の詳細な説明するだめの誤り位置
の組み合わせを示す図、第５図は本発明の前処理部分を
示すフローチャート図、第６図は本発明の詳細な説明す
るためのブロック構成図である。 １・・・マイクロプロセッサ、２・・・データバス、３
・・・コントロールバス、４．５・・・セレクタ、６．
７・・・レジスタ、８・・・α乗算器、９・・・１ｉＵ
乗算器、１０・・・排他的論理加算器、１１・・・零検
出器。 なお図中同一符号は同−又は相当部分を示す。

Claims (1)

【特許請求の範囲】
1. （１）２重誤り訂正可能な符号長ｎのリード・ソロモン
   符号の復号器において、ガロア体上の演算機能を有し２
   次の誤り位置多項式であるＺ＾２■σ＿１Ｚ■σ＿２（
   ■は排他的論理和）の係数σ＿２よりｉ＋ｊを演算する
   とともに、 ［ｉ＋ｊ≧ｎ−１の場合 Ｌｉ＝ｎ−１、Ｌｊ＝ｉ＋ｊ−（ｎ−１） ｉ＋ｊ＜ｎ−１の場合 Ｌｉ＝ｉ＋ｊ、Ｌｊ＝０ ｒ＿１＝αＬｉ／σ＿１、ｒ＿２＝αＬｊ／σ＿２］但
   し、αｉ＋ｊ＝σ＿２、αｉ■αｊ＝σ＿１ｉ、ｊ：誤
   り位置、α：原始多項式の根 なる演算を行なう前処理演算手段と、上記演算結果ｒ＿
   １、ｒ＿２を格納する第１、第２のレジスタ、この第１
   のレジスタの値を１／α倍する第１の乗算器、上記第２
   のレジスタの値をα倍する第２の乗算器、上記第１、第
   ２のレジスタの内容及び数値１の３つの値の排他的論理
   和を計算する加算器、及び該加算結果が零か否かを判別
   する零検出器を有し、 ［ｒ＿１■ｒ＿２■１ ｒ＿１／α→ｒ＿１、ｒ＿２・α→ｒ＿２］の演算を繰
   り返し実行して（ｒ＿１■ｒ＿２■１）が零になるまで
   の繰り返し数Ｃｏより２重誤り位置ｉ＝Ｌｉ−Ｃｏ ｊ＝Ｌｊ＋Ｃｏ を求める誤り位置検出手段とを備えたことを特徴とする
   ２重誤り訂正復号器。