JPS60189543A - 根の導出器 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明はガロア体Ｇ　Ｆ　（２”）上の２次式ｄ（ｘ）
＝ｘ＋σＩｘ＋σ２の根をめる根の導出器に関するもの
であシ、特に、各々がｍ個の２進ビツトから成り、最小
距離が５以上のリードΦンロモン符号の受信語に含まれ
る２つのエラーの位置を根とする２次のエラーロケーシ
ョン多項式の根をめる根の導出器に関するものである。

（従来例の構成と問題点） さて、従来の根の導出器ならびに本発明に係る根の導出
器について述べる前に、説明を容易にするため、以下の
ことを前提としておく。即ち、符号は４個の２進ビツト
からなるシンボルによって構成され、各シンプルはすべ
てａ　Ｆ　（２’）　Ｏ元テｈる。また、リード・ソロ
モン符号は、最小距離が６、情報シンデル数１０、検査
シンぎル数５、符’合長１５である、 今、ＧＦ（２’）の原始光をαとし、α４＋α＋１＝０
を規定すれば、元の表現を第１表に示すようにすること
で、加法ならびに乗法は明らかとなる。ただし、α１５
＝１である。

さて、リード・ソロモン符号の受信語に含まれているエ
ラーは、最小距離が５以上のとき２個まで訂正できるこ
とが知られている。エラーの訂正は、受信語の中のエラ
ーのある位置とその蓋を知るととて行われ得る。これら
をめる一般的解法は、例えは１９７２年にＭＩＴプレス
社から出版されたビーターンン及びウェルトン共著の「
エラー訂正符号」第２版に述べられている。

今、受信語中にあるエラーの位置なＰ１＋Ｐ１になる。

σ（ｘ）＝（ｘ＋Ｐ１　）　（ｘ＋ＰＨ’）−ｘ２＋ａ
ｌｘ＋σ＊　＝・・・・７　（１）ただし、 σ隊＝ｐ、　＋Ｐ、　、σ！　＝ＰＩ　ｐｓ　・・・・
・・・・・・・・・・・・・・・・・（２）リード・ソ
ロモン符号におけるエラー訂正過程では、式（すの係数
σｌおよびσ！は既に得られておシ、従ってこれらから
（１）式の根をめることがエラーの位置を得ることにな
る。

従来ある（１）式の根の導出器の１例は、σｌおよびσ
２をアドレス入力とじ、σ１およびσ黛に対応する根を
データとする記憶手段を設けるものである。この場合、
σｌおよびσ、を入力すれば、出力として根が得られる
ので、構成が簡単となる。

しかし、σ１およびσ寓はそれぞれ４ビツトであるから
、アドレス入力は８ビツトとなシ、σ１．σ２ＮＯから
記憶手段の容量は４５０シンぎル分即ち１８００ビ、ト
必要となる。また、式（１）の１根ＰＩがまれば、式（
２）よシ Ｐ、＝ｐ、＋σ暑　・・・・・・・・・・・・（３）と
な夛、他の根がまる。従って、記憶手段に１根だけ記憶
させ、他機を式（３）Ｋよってめるとすれば、記憶手段
の容量は２２５シンぎル分即ち９００ビ、ト必要となる
。

従来ある（１）式の根の導出器の他の例は、以下に述べ
るように行なわれるものである。即ち、（１）式％式％ とおくと、（０式は ｚ　２＋　ｚ　＋　−！−！−＝　０　・・・・・・・
・・・・・・・（４）σ１２ となる。式（４）の１根ＰＩ′をσ２／σ１２をアドレ
ス入力として記憶手段よシ得れば ｐ２／　＝　Ｐ、’＋　１ 即ち式（１）の根は、 Ｐ、＝σＩＰＩ’　ｐ、＝σ＋　（Ｐｔ’＋１　）＝Ｐ
１十０１これを実現すれば第１図のようになる。１は入
力σ１．２は入力σ２である。３はインバータであシ、
出力１１即ち１／σ１を生成する。４は乗算器で。

あシ、１２はσ冨／σ１．１３はσ２／σ１２　を示し
ている。５は（’ｔ／σ１　よ）式（４）の１根をめる
デープルであシ、１４は１根Ｐ−′である。１５はｐ　
、／　、σ１即ち式（１）のｌ根Ｐ１である。６は加算
器であ如、ＰＩ＋σＩ即ち式（１）の他の根Ｐ２を１６
に出力する。

第１図に示した根の導出器における問題点は、乗算器４
が３個必要であることである。乗算器４を記憶手段で構
成するとすれば、アドレス入力は８ビツトであり、従っ
て２５６シン？ル分の容量が必要となる。

このように、従来の根の導出器は、その構成を簡単にし
ようとすれば、大容量の記憶手段が必要となる問題点を
有している。

（発明の目的） 従って本発明は、簡単な構成でしかも大容量の記憶手段
を必要としない根の導出器を提供することを目的とする
。

（発明の構成） さて、（１）式の根ＰＩ　＋Ｐ！はいずれもＣＦ（２’
）の元であるから、 ｐｌ＝＝α　、Ｐ雪＝αｊ と表わされる。式（２）よシ σ１＝α＋α−α　、σ雪＝α１１１αｊ＝αｔ１ｊエ
　８ ただし、符合長が１５であるから従って、１、ｊり１４
、ｔ＝ｉ＋に；２７ であるから、ｉ、、ｊの組み合わせ（ｉ、ｊ）は（ｌ　
＃ｊ）：（ｔ、θ）、（ｔ−１，１）、・・・　（ｔｉ
２　、早）（１が偶数）（１，０）（ｔ−ｘｓｌ）、・
・・、（−ｒ−乎）（１が奇数）ｔ＋１　ｔ となり、高々１４個の組み合わせがあるだけである。従
って、σ２＝α　をアドレス入力とし、ｏ、ｊ）に対す
る値即ちσ１＝α８をデータとし、σ雪のアドレス入力
に対しすべての考えられる（１．ｊ）の組み合わせに対
するσ１の値を出力する記憶手段を設け、これの出力と
σ１との一致を検出すれば、一致の得られた位置から（
１，ｊ）を知ることができる。

即ち２根Ｐｌ＋Ｐ１を得ることができる。

従って、本発明に係る根の導出器は、式（１）の係数σ
鵞をアドレス入力とし、これに対して決まるσｉをデー
タとする第１の記憶手段と、この第１の記憶手段の出力
とσ１との一致を検出する一致検出手段と、この一致検
出手段の出力を受けて（１）式の一方の根を出力する第
２の記憶手段と、この第２の記憶手段の出力即ち（１）
式の一方の根とσｉから、（１）式の他方の根を得る手
段とを備えている。

（実施例の説明） 第２図に本発明に係る根の導出器の実施例を示す。ただ
し簡略化して示しである。２１はアドレス入力線２０か
ら入力される式（１）の係数σ２をアドレスとし、デー
タ入力線３１から入力される係数σ龜をデータとするＲ
ＯＭ　（読み出し専用記憶手段）であシ、２１ｍはデコ
ーダ、２１ｂはデータ記憶部である。データ記憶部２１
ｂに示しである例えば、左上に４右下に１１のます目は
、α４とα１１の和即ちα　がデータとして記憶されて
いることを示す。２１ｅはデータ記憶部２１ｂ内の各デ
ータ間の境界でオシ、これよシ左のデータは左側へ、境
界２１ｃよシ右のデータは右側へ出力されることを示す
。

２２は一致検出回路であＪ、ＲＯＭ２１よシ出力される
１４個のシンボルのそれぞれとデータ入力線３１からの
データσｉとの一致を検出する０従って、一致検出器２
２の出力は１４有ることになる０ ２３は一致検出器２２の出力を受け、データ入力線３１
からのデータσｉとの一致が成立した位置に対応して、
式（１）の一方の根Ｐ、３２を出力するＲＯＭである。

２４は根ＰＫとσ１から式（１）の他方の根Ｐ２を式（
２）Ｋ基いてめる加算器である０さて、第２図に示した
本発明に係る根の導出器の動作を、式（１）の根がα７
とα４である場合を具体例として説明する。

まず で示される列のデータが出力される。これらは（α０刊
１１鴫１２）、（α１和１０ミ８）、（α２和９蛇１１
）。

（α３＋−ａ８＝ｄ”）　、（α４和７ミ３）、（α５
＋α６ミ２）。

（α１４刊１２づ５） である。次に、これらの出力とσ１とが一致検出器２２
で一致検出されるのであるが、今σ、はα３であるから
矢印２２ｍで示される出力のみが得られる。従ってＲＯ
Ｍ　２は一方の根としてα４をＰ、３２に出力する。他
方の根Ｐ、３３ｉｄ、加算器２４でＰ１＋σ、＝α４＋
α３＝α７ となって得られる。

第２図に示した本発明に係る根の導出器は、１０５シン
？ル分即ち４２０ビツトの容量のＲＯＭ２１と１４シン
がル分即ち５６ビツトの容量のＲＯＭ　２２の合計４７
６ビツトの容量で良い。

（発明の効果） 以上述べてきたことかられかるように、従来に比べて小
容量の記憶手段で、根の導出器が得られる効果を有する
。

【図面の簡単な説明】

第１図は従来の根の導出器の一例を示したブロック図、
第２図は本発明に係る根の導出器を示したブロック図で
ある。 ２１・・・第１のＲＯＭ、２２・・・一致検出器、２３
・・・第２のＲＯＭ、２４・・・加算器、２０・・・係
数０２人力線、３１・・・係数σ□入力線、３２．３３
・・・根の出力線。 良　〔 Ｃ蓼

Claims (1)

【特許請求の範囲】
1. ガロア体Ｇ　Ｆ　（２”）上の２次式〇（ｘ）＝　ｘ　
   ２＋ａ　１　ｘ　＋　ａ　２の根をめるための根の導出
   器でちって、（イ）　前記２次式の係数０２をアドレス
   入力とし、前記係数σ２に対して決まる前記２次式の係
   数σｌをデータとして記憶する第１の記憶手段と、（ロ
   ）第１の記憶手段の出力と、前記２次式の係数０１との
   一致を検出する一致検出手段と、０う　前記一致検出手
   段の出力を受け、前記２次式の１方の根を出力する第２
   の記憶手段と、に）第２の記憶手段の出力と、前記２次
   式の係数σｌとから、前記２次式の他方の根を得る手段
   とを備えたことを特徴とするもの。