JPS6130819A - 誤り訂正装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （技術分野〕 不発明ａＰＣＭ符号の誤）訂正装置に関すｚ。

（従来技術） ２重誤り訂正リードソロモンコードによ２誤り訂正は、
誤りが、ブロック中のどのワードに生じてい乙かを示す
誤シ位置数と、誤りが生じたワードにおける誤シの大き
さを示す変数をシンドロームから求めえことによう行わ
ｔ′Ｌｚ０これらは周知の通シ次のステップによって行
われえ。

（Ｉ）シンドローム計算 （６）誤りワード数の算出 （ホ）誤シ位ｌＩ＋￥数を根に持つ誤り位置多項式の算
出（支）上記誤シ位置多項式の根の算出 Ｍ誤りの大きさ會表す変数の算出 （ロ）誤り訂正 上記ステップｔｖ＋ｖ符号長ｍ＋４、情報ワード数ｍの
２重機シ訂正す−ドンロモンコードについて説明す乙。

この様な符号語は ｍ＋３ Ｒ（ト）＝Ｗｒｎ９Ｘ＋モーーＸｍ＋２十−−−−〜−
−９Ｗ□Ｘ＋Ｗｏ　　−一一一一−−−−−−−−（１
）と表わされ、各ワードＷは、ｎビット構成のＣＦ（２
ｎ）上の各元αノである。伝送又は記録再生過程で符号
語の第１桁及び７桁のワードに誤りが生じたときシンド
ローム全基にその誤り位置数α１、αＪを２根とする［
ｌ！４シ位置多項式τに）が次のごとく得られる。

６（ト）−１＋イ、Ｘ＋むｘ”　　　　　−−−−−−
−−−−−−（２）ちなみにシンドロームを で定義す４とき で与えられ２ことは周知の通りである。但しすべての演
算はＧＦ（２”）上で行われる。つま！り　（１１式で
示すＲ（ト）のワードが２語誤ったとき、その誤り位置
がどこであえかけδ（ｘ）＝θを解いて得られ２２根α
′、α！、求めればよい。しかえにイ（２）−〇を解く
方法としては次の２つが知られてい乙。その１つは根が
αｒｒｒ４−’〜α０のいずれかであるはずだから、そ
れらのうちδ（ｘ）−〇を満足す２α１、αｊのみを根
とすえ方法であえ。これは２（ｍ＋４）回の複雑な演算
を要し、符号語が到来する時間間隔内に処理すえことが
難しくな乙ことが多い。２番目の方法は上記の手順ｋ１
１ｆ；’、の種々の値に対してあらかじめ行っておき、
それら？ｌ−ＲＯＭテーブルにおさめ、δ（ｘ）＝０を
満足す４２つの係数ｄ、ヌ全アドレスとして２根全瞬時
に求め乙方法でろえ。

このテーブルは２ｎビツトのアドレスを有し１アドレス
に２ｎビツトのデータを持つ必要かめＺので１’２ｎ）
Ｘ２”ビットを要し巨大なメモリ量に達し実現しがたい
ことが多い。例えばｎ　＝　８のとき、その量は１３１
０７２バイトにも達する。

（目的） 本発明は上記ＲＯＭテーブルのサイズをはＺかに小さく
　＋、て誤り位置多項式の２根を短時間に求めうる誤り
訂正装ｆ’に提供すｚｏ （実施例） 以下不発明を具体的に説明すふ為ｎ　＝　８とし原始多
項式Ｘ”　＋Ｘ’　＋Ｘ″十Ｘ”　＋　１＝　０全満足
す為原始元αを有するＧＦ　（２”）上の符号語を例に
とる。イ（ト）＝０を満足す４２根もＧＦ（２“）上の
元であふからべき表現の元α０〜αｆ０のいずれかに該
当する。各元を多項式表現したべき表現−多項例えば誤
シ位置多項式　に）の一つの係数　、がα６８と得られ
た場合には　（２）＝０管満足す４２根αとαＪは ＝α６＠＝αイ＋αＪ の関係にあ４はずだから表１よりα６“の多項式表現（
α７＋α１＋α“＋１）を、例えば（α７）と（α４＋
α”＋１）、即ちα７とα１Ｇｇの如く１組に分け、こ
うして出来た種々の組のいずれかにα１、αｌは対応す
ｚｏどの組に該当すえか￥′：ｉ　に）のもう一つの係
数　８が ＝αｔ、αｊ＝αｉ＋／ の関係に６．にとから上述の各組のべき表現の積αｉ＋
／のうち　、と一致すｚものを選び出すことによりただ
ちにα１及びα／を決定できる。こうして上記係数　、
及び　、に対応すえ２根α８とα１．求め、各　、及び
　、に対応すえアドレスを有す４８０Ｍテーブルの各対
応位置に２根α“とα／全収納す４０ 上述の組数は、例えば多項式−ｊ９．現の項ｉｊ！、’
に４とすれば、表２のように求められ７とな４゜宍　　
　２ 一般に生じうえ組数は項数ｆ：Ｐとすえと２（１）−１
組となる。次に前記原始多項式に対す２元のべき表現と
多項式表現の対応表の全てにわたって生じ１組のデータ
量は３バイト（α１、αｊ、α“＋／）であるからＲＯ
Ｍテーブルに必要な総メモリ量は３０５７　ｘ　３　＝
　９１７１バイトとなり前述の例に比べ７チとごくわず
かのメモリ量ですみ、短時間で誤）位置多項式の２根を
求め２ことができ２゜根の求め方けざ、、／、？アドレ
スとするＲＯＭテーブル参照によ乙ことは勿論であふ。

更に符号語長ｍ＋４は一般に２ｎ−１に比べ数分の１で
あえことが多いので一つの組の中で積成分を除き一４以
上の元金含む組はＲＯＭテーブルから除外して良いので
上記メモリ量は更に減少させゐことができＺｏ （効　果） 上記のように不発明によれば２重誤り訂正リードソロモ
ンコードの誤り訂正において２語誤り時の誤シ位置多項
式の根を少いメモリｔのＲＯＭテーブル全参照すること
によって短時間で求め４ことが出来る。

Claims (1)

【特許請求の範囲】
1. ｎビットからなるデータワードｍ語と、同じくｎビット
   からなるパリテイワード４語で１ブロックを構成し、ｍ
   ＋４≦２＾ｎ−１としたＧＦ（２＾ｎ）上の２重誤り訂
   正リードソロモン符号について、シンドロームの公知の
   組み合わせ演算により判定されるべき１ブロック中の誤
   りワード数に応じて誤り位置数を根に持つ誤り位置多項
   式δ（ｘ）＝１＋δ＿１ｘ＋δ＿２ｘ＾２から各符号語
   毎にδ＿１及びδ＿２を導出する手段を備えた誤り訂正
   装置において、誤りワード数が２語の符号語毎に求めた
   前記多項式δ（ｘ）の係数δ＿１を、α＾ｋ＋α＾ｌの
   如く２項で表現したｋ及びｌより求めたα＾ｋ＾＋＾ｌ
   のうち、上記係数δ＿２と一致するα＾ｋ＋α＾ｌ又は
   ｋ及びｌを、上記係数δ＿１及びδ＿２に対応するアド
   レス上に収納したＲＯＭテーブルを有し、上記誤りワー
   ドを含む符号語毎に求めた上記係数δ＿１及びδ＿２に
   応じて上記ＲＯＭテーブルより求めたα＾ｋ及びα＾ｌ
   をＧＦ（２＾ｎ）上の誤り位置多項式の根α＾ｉ及びα
   ＾ｊとすることを特徴とする誤り訂正装置。