JPH01101742A - 誤り訂正回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、データ通信システム等において使用される符
号の誤り訂正回路に関する。

［従来の技術］ 従来、符号の訂正方式に関して、Ｊ、Ｊ、５ｔｏｎｅの
示した、中国人の剰余定理に基いた誤り訂正符号（以下
、ストーン符号という）かある。

ストーン符号は、かなり広範囲の符号を含み、整数環の
上でも、また多項式環の上でも構成できる。いずれの場
合も、原理は同じであり、以下では、有限体ＧＦ（２ｍ
）　（ｍは１以上の整数）上の多項式を用いて定義され
る符号の構成法を示す。

有限体ＧＦ（２ｍ）の元からなる長さｋＸｄ　（ｋ、ｄ
：整数）の情報記号列を。

（ＩＬ　ｏ、　ＪＬ　ｒ、　ｊＬ、ｔ、…ｐＬｈｄ−＋
）とし、有限体ＧＦ（２’″）上の互いに素なｎ個のｄ
次多項式を、 （ｍ、（ｘ）、　ｍ、（ｘ）、　・・・、ｍｎ（ｘ））
としたとき、 Ｆ（ｘ）＝　ＪＬ　Ｑ＋ＪＬ　＋Ｘ＋　ＪＬ　２Ｘ２＋
−＋ｇ　＠６−、Ｘ”−’に対して、　鳳１（Ｘ）によ
るＦ（ｘ）の剰余ａｔ（Ｘ）　ＥＦ（ｘ）　（ｍｏｏｄ
　ａｔ（ｘ））　　（＋−１，２，−−−、ｎ）を求め
、 Ｖ−（ａｔ（ｘ）、　ａｔ（ｘ）、　−、ａｎ（ｘ）　
）　　　−（１）を符号とする。

復号は１次式によりＦ（ｘ　）を計算することにより行
われる。

Ｆ（ｘ）ミΣ　（閘（ｘ）／１１＋（ｘ））ｔ＋（ｘ）
ａｔ（ｘ）（ｍｏｄ　Ｍ（ｘ））ここに、 Ｍ（ｘ）＝　ｒＩ　ｍｌ（Ｘ） であり、ｔ＋（ｘ）は、 （Ｍ（ｘ）／＋ｗ＋（ｘ））ｔ＋（ｘ）　　Ｅ　　１（
ＩＩｏｄ　　ｍｌ（ｘ））−（ｚ）を満足する最小次数
の有限体ＧＦ（２’″）上の多項式である。

ここで、符号Ｖに誤りか生じた場合についても、次の手
段により正しく復号することかできる。　幾つかのｍ、
（ｘ）の積をＭ’　（ｘ）としたとき、ｄｅｇ［Ｆ（ｘ
）］（ｄｅｇ［Ｍ’（ｘ）］（ｄｅｇ［Ｆ（ｘ）］はＦ
　（ｘ）の次数を表わす）となるすべてのＭ’　（ｘ）
について、上記の式と同様にＦ（ｘ）を求め、多数決を
とる。

これにより、誤り訂正を行うことができる。

［発明か解決しようとする問題点］ 上記のような多数決をとることによる復号法の場合、誤
り訂正能力を高くすると計算量か莫大なものとなり、実
用性に欠けるという問題かあった。

したがって１本発明は、上記問題点の解決を図り、比較
的少ない計算量で誤り訂正を行う誤り訂正回路を提供す
ることを目的とする。

［問題点を解決するための手段］ 上記目的を達成するために、本発明は、中国人の剰余定
理に基いた剰余多項式符号を用いた誤り訂正回路におい
て、 有限体ＧＦ（２ｍ）　（ｍは１以上の整数）上での加算
、乗算および除算を行う演算手段と、多項式の次数を求
めて、予め定めた定数との大小関係を判断する比較手段
と、 最大公約数を求めるユークリッドの互除法の繰返し演算
を行う誤り訂正手段とを備え、エラー位置およびエラー
値を求めることなく復号をおこなうようにしたものであ
る。

Ｃ作用］ このような構成において、上記（１）式て与えられる符
号Ｖに対し、誤りが生じた符号を、Ｖ”（ａ＋’（Ｘ）
、　ａ２°（ｘ）、−、ａｎ’（ｘ）　）として、上記
演算手段により、次式の計算を行う。

Ｆ’　（ｘ） ミΣ（Ｍ（ｘ）／ｍ；（ｘ））ｔ、（ｘ）ａｔ’（ｘ）
（ＩＩｏｄ　Ｍ（ｘ））・・・（３） つぎに、上記比較手段による比較の結果。

ｄｅｇ［Ｆ’（ｘ）］　　＜　　ｋｄ　　　　　　　　
　　　　　　　　　　　　　　　＝（４）ならば、Ｖｏ
には誤りは生じておらず、Ｆ（ｘ）＝Ｆ’　（ｘ） である。逆に、 ｄｅｇ［Ｆ’　（ｘ）］　　≧　ｋｄ　　　　　　　　
　　−（４）ならば、上記誤り訂正手段により、ユーク
リッドの互除法を用いた繰返し演算を行うことによりＶ
。

が（ｎ−ｋ）／２個までの誤りを含む場合の誤りを訂正
することができる。その手順を以下に示す。

■　ｒ−＋（ｘ）＊Ｍ（ｘ）　、　ｒ、（ｘ）＝Ｆ’（
ｘ）。

ｓ−＋（ｘ）Ｊ　、　５ｏ（ｘ）＝１．１Ｉ１１とする
。

を満足するｑｔ（ｘ）および「、（ｘ）を求める。

■　５ｔ（ｘ）＝ｓ＋−ｇ（ｘ）−ｑｔ（ｘ）ｓ＋−＋
（ｘ）　　−（ａ）で与えられるｓ、（ｘ）を求める。

■１）　　ｄｅｇ［ｒ＋（ｘ）］≧　（ｎ−ｔ）ｄのと
き、ｉ麿ｉ＋１ として■に戻る。

２）　　ｄｅｇ［ｒ＋（ｘ）］　　（（ｎ−ｔ）ｄのと
き、Ｆ（ｘ）＝　ｒ＋（ｘ）　／　５ｔ（ｘ）　　　　
　−（７）により、Ｆ（ｘ）を求める。

ここに、ｔはｎとｋにより定まる訂正可能な誤りの個数
であり、 ｎ−に≧２ｔ である。

本発明の誤り訂正回路によれば、エラー位置およびエラ
ー値を求めることなく誤りを訂正することができる。

［実施例］ 以下、図面を参照しながら本発明の実施例について詳細
に説明するっ 〈実施例の構成〉 第１図に、本発明に係る復号装置の基本構成の一例を示
す。

この装置は、符号Ｖ′を受けて上記（３）式て示したＦ
’（ｘ）　　（およびｄｅｇ［Ｆ’　（ｘ）］）を求め
る演算手段１と、上記（４）式で示したように、ｄｅｇ
［Ｆ’　（ｘ）］とｋｄとの大小比較を行う比較手段２
と、この比較手段２により「誤りあり」と判断されたと
き、Ｆ’　（ｘ）を受けて誤りを訂正する誤り訂正手段
３を備える。

第２図に、第１図の誤り訂正手段３の具体的回路構成を
示す。

この回路は、上記（５）式で示されるｑＩ（ｘ）および
ｒ、（ｘ）を求める演算を行う演算回路４　、ｒｌ−□
（×）およびｒ＋−ｇ（Ｘ）を保持するメモリ（または
レジスタ）５、上記（６）式で示されるｓ、（ｘ）を求
める演算を行う演算回路６、ｓ、−＋（Ｘ）およびｓｔ
−ｇ（ｘ）を保持するメモリ（またはレジスタ）７、上
記手順■に示す大小比較を行う比較回路８、および上記
（７）式て示されるＦ（ｘ）を求める演算を行う演算回
路９からなる。

〈実施例の作用〉 まず、第１図の復号装置の動作を説明する。

復号装置は、符号Ｖ′を受けると、演算手段ｌにより、
Ｆ’　（ｘ）および次数ｄｅｇ［Ｆ’（ｘ）］を求める
。この求められた次数ｄｅｇ［Ｆ’（Ｘ月を、比較手段
２により予め定められた数ｋｄと比較する。比較の結果
、上記（４）式のように次数ｄｅｇ［Ｆ’（ｘ）］がｋ
ｄより小であれば、「誤りなし」と判定し、Ｆ’（ｘ）
をそのままＦ（ｘ）とする。上記比較の結果、次数ｄｅ
ｇ［Ｆ’　（ｘ）］がｋｄ以上である場合、「誤りあり
」と判定され、Ｆ’（ｘ）を受ける誤り訂正手段３の出
力を、求めるＦ　（ｘ）とする。

つぎに、誤り訂正手段３の動作を、第２図のブロック図
を参照して説明する。

初期状態として、ｉＪとして、メモリ５には、ｒｏ（ｘ
）−Ｆ’　（ｘ）およびｒ−、（ｘ）−Ｍ（ｘ）を保持
し、メモリ７には、ｓ、（ｘ）＝１およびｓ−、（ｘ）
−０を保持しておく。

そこで、演算回路４は、上記（５）式を満足するｑＩ（
Ｘ）　、　ｒ＋（ｘ）およびｄｅｇ［ｒ＋　（ｘ）］を
求める。演算回路６は、求められたｑＩ（ｘ）に応じて
上記（６）式に従い、ｓ、（ｘ）を求める。比較回路８
は、　ｄｅｇ［ｒ＋（ｘ）ｌ　と　（ｎ−ｔ）ｄとを比
較し、ｄｅｇ［ｒ＋（ｘ月≧　（ｎ−ｔ）ｄ のとき、ｉ＊ｉ＋１とし、上記処理を繰返す。

ｄ＋４［ｒ＋（ｘ）］　　（（ｎ−ｔ）ｄのときは、演
算回路９が、上記（７）式に従いその時点の　ｒ、（ｘ
）およびｓ、（ｘ）に応じて、Ｆ（ｘ）＝　ｒ＋（ｘ）
　／　５１（Ｘ）を求める。

次に具体的な例を挙げて説明する。

原始元α（α３◆α＋１−０）なる有限体ＧＦ（２’）
の元からなるｎ＝８．ｋｍ４．ｔ−２，ｄｗｌの符号を
考える。

情報記号列Ｆ（ｘ）を Ｆ（ｘ）−ａ　’　ｘ’＋　ａ　’ｘ”　＋　ａ　”ｘ
＋　ａとすると、 Ｖ＊（ａ、ｃｘ’、１．ｅｘ”、ａ’、ａ’、ａ’、１
１である。いま、２個の誤りの生じた符号Ｖ′を、Ｖ′
・（α、α５．α６．α３．α４．α４．α３．１）と
すると、 Ｆ’（ｘ）−ｘ’＋　　ａ　６ｘ６＋ａｘ’＋　　ａ’
ｘ’＋ａ”ｘ”＋α６ｘ２＋α２ｘ＋α である。ｄｅｇ［Ｆ’（ｘ）］＝　７　＞　ｋｄ　−４
であるから、ユークリッドの互除法を用いた繰返し演算
を行なうと、 ■　ｒ−、（ｘ）−Ｍ（ｘ）ｍｘ’＋ｘ　、　ｒｏ（ｘ
）−Ｆ’（ｘ）。

ｓ−＋（ｘ）−０、５ｏ（ｘ）−＋ｌ　。

ｉＪｌ ■　ｒ−＋（ｘ）＝ｑ＋（に）ｒＯ（ｘ）＋「Ｉ（ｘ）
より、ｑＩ（に）冨Ｘ◆α６ ｒ、（ｘ）菖ａ　’Ｘ’＋α’Ｘ’＋α’Ｘ’＋（！　
’Ｘ″＋α’ｘ”　＋ｘ　＋１ ■　ｓｔ（ｘ）−Ｓ−１ｃｘ）　−ｑＩ（ｘ）ｓｏ（ｘ
）＝　ｑＩ（に） 謬Ｘ＋α６ ■　１）　　ｄｅｇ［ｒ＋（ｘ）］　”　６≧　（ｎ−
ｔ）ｄ　−［ｉ　。

■　ｒｏ（Ｘ）＝４２（Ｘ）Ｉ’＋　（Ｘ）＋ｒ２（ｘ
）より、ｑ２（Ｘ）ツαＸ ｒｇ（ｘ）＝α５ｘ８＋α２　ｘ　４◆α　ｘ３＋α５
　ｘ　２＋α４　ｘ＋α■　　５２（Ｘ）−５ｏ（ｘ）
−４２（Ｘ）ｓｌ（Ｘ）＝αｘ２◆　　ｘ＋　　１ ■　　２）　　　　ｄｅｇ［ｒｇ（ｘ）］　　　−５＜
　　（ｎ−ｔ）ｄ　　−６。

Ｆ（ｘ）−ｒｚ（ｘ）／５ｚ（ｘ） ｘ　　ｃｃ　’　　Ｘ’＋　　α’ｘ”＋α２ｘ＋　　
αとなり、情報記号列Ｆ（ｘ）が求まる。

［発明の効果］ 以上説明したように、本発明によれば、有限体ＧＦ（２
ｍ）上の多項式を用いて定義されるストーン符号におい
て、 ｎ−に≧２ｔ を満たすｔ個までの誤りが生じた場合に、比較的少ない
演算量により、誤りを訂正することかできる。

また、この符号法において、ｄ＝１とした場合は、リー
ド・ソロモン符号と呼ばれる符号となり、上記（２）式
で示されるＬ＋（Ｘ）は、ｔ＋（ｘ）＝１　　（ｉ−１
，２，・・・、ｎ）となって、さらに容易に復号な行う
ことがてきる。

【図面の簡単な説明】

第１図は本発明に係る誤り訂正回路の構成を示すブロッ
ク図、第２図は第１図の誤り訂正手段の一例のブロック
図である。

Claims (1)

1. 【特許請求の範囲】 中国人の剰余定理に基いた剰余多項式符号を用いた誤り
   訂正回路において、 有限体ＧＦ（２＾ｍ）（ｍは１以上の整数）上での加算
   、乗算および除算を行う演算手段と、 多項式の次数を求めて、予め定めた定数との大小関係を
   判断する比較手段と、 最大公約数を求めるユークリッドの互除法の繰返し演算
   を行う誤り訂正手段とを備え、 エラー位置およびエラー値を求めることなく復号をおこ
   なうことを特徴とする誤り訂正回路。