JPS63123231A - 誤り位置検出装置 - Google Patents

誤り位置検出装置

Info

Publication number
JPS63123231A
JPS63123231A JP61270271A JP27027186A JPS63123231A JP S63123231 A JPS63123231 A JP S63123231A JP 61270271 A JP61270271 A JP 61270271A JP 27027186 A JP27027186 A JP 27027186A JP S63123231 A JPS63123231 A JP S63123231A
Authority
JP
Japan
Prior art keywords
register
output
zero
error position
error location
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP61270271A
Other languages
English (en)
Other versions
JPH07114375B2 (ja
Inventor
Kaoru Iwakuni
薫 岩國
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Holdings Corp
Original Assignee
Matsushita Electric Industrial Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Matsushita Electric Industrial Co Ltd filed Critical Matsushita Electric Industrial Co Ltd
Priority to JP61270271A priority Critical patent/JPH07114375B2/ja
Publication of JPS63123231A publication Critical patent/JPS63123231A/ja
Publication of JPH07114375B2 publication Critical patent/JPH07114375B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Landscapes

  • Error Detection And Correction (AREA)

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、ディジタルデータの伝送系や、記録/再生系
における符号誤りを訂正する為の、BCH符号や、リー
ド・ソロモン符号の復号の際に用いられる誤り位置検出
装置に関するものである。
従来の技術 近年、情報伝送・情報記録の分野においては、ディジタ
ル化が急速に進行している。特に、その伝送速度、記録
密度の面で、高速化・高密度化にはめざましいものがあ
る反面、伝送または記録/再生中に発生するディジタル
データの符号誤りは不可避となってきている。この様な
流れの中で、符号誤りを検出・訂正する為の誤り訂正符
号とその符号化/復号化システムは重要なものとなって
きているが、なかでも、BCH符号、リード・ソロモン
符号は実用性の観点から、最も重要な符号と言えよう。
BCH符号、リード・ソロモン符号の復号化の処理にお
いては、一般に、シンドロームから誤す位置多項式を求
め、誤り位置多項式の根から誤り位置を求めるという手
順がとられるが、この誤り位置多項式の係数を入力し誤
り位置多項式の根を求め、誤りの位置を出力する為の誤
り位置検出装置は、上記符号の復号化処理において、最
も重要な要素の一つといえる。
従来、この様な誤り位置検出には、チェノのアルゴリズ
ムが用いられるのが一般的であす、装置化されて広く使
用されている(例えば、宮用、岩垂、今回「符号理論」
(昭48)、昭晃堂、262〜264頁)。
以下、図面を参照しながら、上述したような従来の誤り
位置検出装置について説明を行うが、ここでは−例とし
て3次の誤り位置多項式から3つの誤り位置を求める場
合を考えることにする。また符号は非2元符号を考え、
有限体CF (2q)の元であるとする。
第2図は、従来の誤り位置検出装置の構成を示すブロッ
ク図であって、31〜34は誤り位置多項式の各項の係
数の入力端子、35〜38は入力端子31〜34に接続
された、qビット幅のレジスタ、39はレジスタ360
入力/出力間に接続された定数αを乗じる係数器、4o
はレジスタ37の入力/出力間に接続された定数α を
乗じる係数器、41はレジスタ38の入力/出力間に接
続された定数α を乗じる係数器、42は各レジスタの
出力に接続された加算器、43は加算器42の出力に接
続されたゼロ検出器、44はゼロ検出器43に接続され
た誤り位置レジスタ、45は誤り位置を出力する出力端
子である。
次に、以上のように構成された誤り位置検出装置につい
て、その動作について説明する。
まず、ここで解こうとする3次の誤り位置多項式を σ(x)=x  +σ1x+σ2x+σ5   ・・・
・・・(1)と置く。この誤り位置多項式は3つの誤り
位置を3つの根として持つものであるから、誤り位置を
求める処理は、方程式、 σ(X)=O・・・・・・僻) を解くことに他ならない。この方程式を解く最も単純な
方法は、ゼロを除いた2−1個の元を順次、(1)式に
代入して行き、結果がゼロとなる元を根とするという方
法である。この方法によれば、処理時間が長くなる事を
問題にしなければ、誤り位置多項式がいかに高次なもの
であっても解くことができる。
第2図に示した誤り位置検出装置は、以上述べた方法を
、装置化したものであって、まず、誤り位置多項式の各
項の係数σ3.σ2.σ1、及び1は、それぞれ、入力
端子31〜34を通して、レジスタ36〜38に入力さ
れる。加算器42は、各レジスタの出力の総和をとる為
のものであって、この状態で加算器42の出力には、 1+σ1+σ2+σ5=σ(1) 即ち、(1)式に1を代入したものがあられれることに
なる。
次に、各レジスタ35〜3Bにクロックパルスが1回与
えられると、レジスタ35に関しては、入力と出力が直
結されているので変化はないが、レジスタ36の入力/
出力間には定数αを乗じる係数器39が接続されている
ので、レジスタ36に記憶されている内容は、クロック
パルスが与えられる前の内容にαを乗じたものに変化す
る。同様にして、レジスタ37の内容は係数器4oによ
ってα を乗じたものに、レジスタ38の内容は係数器
41によってα を乗じたものに変化する。
ここで、αは有限体GF(2q)の原始光であり、した
がって有限体G F (2q)の全ての元はαのべき乗
であられされる。さて、この状態で加算器42の出力を
考えてみると、 α+ασ1+ασ2+σ3=σ(α) となり(1)式にαを代入したものがあられれることが
わかる。
以下同様にして、各レジスタにクロックパルスを逐次与
えて行くと、加算器42の出力には順次、(1)式にα
、α、・・・・・・を代入したものがちられれるので、
2q−1個のクロックパルスを与えることによって、加
算器42の出力に、(1)式に全ての元を代入した値を
得ることができるのである。この値がゼロとなる元が、
即ち、(2)式の方程式の根であるので、ゼロ検出器4
3によりて誤り位置を得ることができ、得られた誤り位
置は誤り位置レジスタ44に蓄積された後、出力端子4
6から出力されることとなる。
発明が解決しようとする問題点 しかしながら、上記のような構成では、2−1回のクロ
ックパルス入力が必須であり、しだがってqがある程度
大きくなってくると、処理に要する時間が極めて大きく
なるという重大な問題点を有していた。
本発明は上記問題点に鑑み、必要とされるクロックパル
スを半減し、大幅に処理時間を短縮することができる誤
り位置検出装置を提供するものである。
問題点を解決するための手段 上記問題点を解決するだめに、本発明の誤り位置検出装
置は、レジスタ出力を単純に加えあわせる加算器とゼロ
検出器に加えて、レジスタ出力に定数を乗じるだめの係
数器群と加算器及びゼロ検出器の組を複数組備えること
により、同時に複数の代入演算を行う構成をとるもので
ある。
作用 本発明は、上記した構成によって、1回のクロックパル
ス入力によって、複数個の、誤り位置多項式への元の代
入結果を同時に求めることにより、必要とされるクロッ
クパルス数を大幅に削減し、処理時間を大幅に短縮でき
ることとなる。
実施例 以下、本発明の一実施例の誤り位置検出装置について図
面を参照しながら説明する。
箭1図は本発明の一実施例における誤り位置検出装置の
構成を示したものである。第1図において、1〜4は誤
り位置多項式の各項の係数の入力端子、6〜8は入力端
子1〜4に接続された、qビット幅のレジスタ、9はレ
ジスタ6の入力/出力間に接続された定数α を乗じる
係数器、10はレジスタ7の入力/出力間に接続された
定数α4を乗じる係数器、11はレジスタ8の入力/出
力間に接続された定数α を乗じる係数器、16は各レ
ジスタの出力に接続された加算器、18は加算器15の
出力に接続されたゼロ検出器である。
以上は既に述べた従来の構成と同様のものである。
さらに、12はレジスタ6の出力に接続された定数αを
乗じる係数器、13はレジスタ7の出力に接続された定
数α を乗じる係数器、14はレジスタ8の出力に接続
された定数α を乗じる係数器、16は各係数器出力及
びレジスタの出力に接続された加算器、17は加算器1
6の出力に接続されたゼロ検出器である。また、19は
ゼロ検出器17及びゼロ検出器18に接続された誤り位
置レジスタ、20は誤り位置を出力する出力端子である
以上のように構成された誤り位置検出装置について、以
下その動作を説明する。ここでも3次の誤り位置多項式
の根を求める、即ち、方程式σ(x)=x  +σ1x
 +σ2x+σ5=。
を解いて3つの誤り位置を検出することを考える。
まず、誤り位置多項式の各項の係数σ3.σ2.σ1゜
及び1は、それぞれ、入力端子1〜4を通して、レジス
タ5〜8に入力される。この状態で加算器15の出力を
考えると、従来の構成と同様にσ(X)に1を代入した
もの、即ち、 σ(1)=1+σ1+σ2+σ5 があられれることになる。
同時に加算器16には、レジスタ6の出力と、係数器1
2によってαを乗じられたレジスタ6の出力と、係数器
13によってα を乗じられたレジスタ7の出力と、係
数器14によってα を乗しられたレジスタ8の出力と
が加えられるので、その出力には、σ(X)にαを代入
したもの、即ち、σ(α)=α +ασ1+ασ2+σ
5があられれる。
次に、各レジスタにクロックパルスが1回与えられると
、レジスタ6に関しては、入力と出力が直結されている
ので変化はないが、レジスタ6の入力/出力間には定数
α を乗じる係数器9が接続されているので、レジスタ
6に記憶されている内容は、クロックパルスが与えられ
る前の内容にα を乗じたものに変化する。同様にして
、レジスタ7の内容は係数器1oによってα を乗じた
ものに、レジスタ8の内容は係数器11によってα を
乗じたものに変化する。
しだがって、加算器15の出力にはσ(X)にα2を代
入したものが、同様に、加算器16の出力にばσ(X)
にα を代入したものが、あられれることになる。この
ようにして得られた代入結果はゼ口検出塁17及び18
に入力されて、ゼロを検出する事により根か否か判定し
、得られた根の位置は誤り位置レジスタ19に順次蓄積
され、出力端子2oから出力されることになる。
このように本実施例によれば、1回のクロックパルス入
力によって2つの代入結果が得られるので、従来の半分
のクロックパルス数で処理を行うことができるので、処
理時間の短縮ができるのである。
なお、本実施例においては、2つの代入結果を同時に求
めたが、4つの代入結果を同時にもとめる誤り位置検出
装置も同様にして容易に構成することができる。この場
合には装置規模は大きくなるが、さらに短い時間で処理
を行うことができる。
発明の効果 以上のように本発明は、レジスタ出力を単純に加えあわ
せる加算器とゼロ検出器に加えて、レジスタ出力に定数
を乗じるだめの係数器群と加算器及びゼロ検出器の組を
複数組備え、複数個の、誤り位置多項式への元の代入結
果を同時に求めることにより、必要とされるクロックパ
ルス数を大幅に削減し、処理時間を大幅に短縮した誤り
位置検出装置を実現できるものである。
【図面の簡単な説明】 第1図は本発明の一実施例における誤り位置検出装置の
構成を示すブロック図、第2図は従来の誤り位置検出装
置の構成を示すブロック図である。 5〜8.35〜38・・・・・・レジスタ、9〜11゜
39〜41・・・・・・係数器、15,16.42・・
・・・・加算器、17.18.43・・・・・・ゼロ検
出器、19゜44・・・・・・誤り位置レジスタ。 代理人の氏名 弁理士 中 尾 敏 男 ほか1名第1
図 銑り雄l冷頂六M (53626t     / 第2図

Claims (1)

    【特許請求の範囲】
  1. 誤り位置多項式の各項の係数を入力し、記憶する為のレ
    ジスタ群と、上記レジスタ群の各項に定数を乗じて更新
    するための係数器群とを備えるとともに、上記レジスタ
    群の各項出力を直接もしくは定数を乗じたのちに加えあ
    わせて総和を求める手段と、その総和がゼロか否かを判
    定するゼロ検出手段とを2組以上備え、さらに、上記各
    ゼロ検出手段のゼロ検出出力を誤り位置として記憶する
    ための誤り位置レジスタを具備してなる誤り位置検出装
    置。
JP61270271A 1986-11-13 1986-11-13 誤り位置検出装置 Expired - Fee Related JPH07114375B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP61270271A JPH07114375B2 (ja) 1986-11-13 1986-11-13 誤り位置検出装置

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP61270271A JPH07114375B2 (ja) 1986-11-13 1986-11-13 誤り位置検出装置

Publications (2)

Publication Number Publication Date
JPS63123231A true JPS63123231A (ja) 1988-05-27
JPH07114375B2 JPH07114375B2 (ja) 1995-12-06

Family

ID=17483924

Family Applications (1)

Application Number Title Priority Date Filing Date
JP61270271A Expired - Fee Related JPH07114375B2 (ja) 1986-11-13 1986-11-13 誤り位置検出装置

Country Status (1)

Country Link
JP (1) JPH07114375B2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6647529B2 (en) 2000-01-18 2003-11-11 Matsushita Electric Industrial Co., Ltd. Chien's searching apparatus

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS62122333A (ja) * 1985-11-21 1987-06-03 Mitsubishi Electric Corp シンドロ−ム回路

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS62122333A (ja) * 1985-11-21 1987-06-03 Mitsubishi Electric Corp シンドロ−ム回路

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6647529B2 (en) 2000-01-18 2003-11-11 Matsushita Electric Industrial Co., Ltd. Chien's searching apparatus

Also Published As

Publication number Publication date
JPH07114375B2 (ja) 1995-12-06

Similar Documents

Publication Publication Date Title
EP0318547B1 (en) Real-time bch error correction code decoding mechanism
US5715262A (en) Errors and erasures correcting reed-solomon decoder
US6347389B1 (en) Pipelined high speed reed-solomon error/erasure decoder
EP0114938A2 (en) On-the-fly multibyte error correction
US5805617A (en) Apparatus for computing error correction syndromes
US6725416B2 (en) Forward error correction apparatus and methods
KR19990028201A (ko) 10 비트 리드-솔로몬 에러 정정 모듈을 위한 전용 alu구조
JPH10112659A (ja) 誤り訂正復号装置
JP3245290B2 (ja) 復号方法とその装置
JP2001127645A (ja) 誤り訂正方法および誤り訂正装置
EP0629052B1 (en) Method of and circuit for correcting errors
JP2662472B2 (ja) 誤り訂正処理用シンドローム演算回路
JPS63123231A (ja) 誤り位置検出装置
JP2553565B2 (ja) ガロア体演算装置
JP3252515B2 (ja) 誤り訂正装置
JP2907138B2 (ja) 誤り訂正の演算処理方法及び処理回路
JP2944813B2 (ja) 誤り訂正符号の復号装置
JP2575506B2 (ja) チエンサーチ回路
EP1037148A1 (en) Error coding method
US6446233B1 (en) Forward error correction apparatus and methods
JP3280470B2 (ja) 誤り訂正回路
KR930000220B1 (ko) 리드-솔로몬 코드의 에러위치 정정시스템
KR100246342B1 (ko) 리드솔로몬오류수정장치
JPH05268101A (ja) チェンサーチ回路
JPH09185518A (ja) 原始元αのべき乗生成方式及びその装置

Legal Events

Date Code Title Description
LAPS Cancellation because of no payment of annual fees