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
Links
Landscapes
- Error Detection And Correction (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
産業上の利用分野
本発明は、ディジタルデータの伝送系や、記録/再生系
における符号誤りを訂正する為の、BCH符号や、リー
ド・ソロモン符号の復号の際に用いられる誤り位置検出
装置に関するものである。
における符号誤りを訂正する為の、BCH符号や、リー
ド・ソロモン符号の復号の際に用いられる誤り位置検出
装置に関するものである。
従来の技術
近年、情報伝送・情報記録の分野においては、ディジタ
ル化が急速に進行している。特に、その伝送速度、記録
密度の面で、高速化・高密度化にはめざましいものがあ
る反面、伝送または記録/再生中に発生するディジタル
データの符号誤りは不可避となってきている。この様な
流れの中で、符号誤りを検出・訂正する為の誤り訂正符
号とその符号化/復号化システムは重要なものとなって
きているが、なかでも、BCH符号、リード・ソロモン
符号は実用性の観点から、最も重要な符号と言えよう。
ル化が急速に進行している。特に、その伝送速度、記録
密度の面で、高速化・高密度化にはめざましいものがあ
る反面、伝送または記録/再生中に発生するディジタル
データの符号誤りは不可避となってきている。この様な
流れの中で、符号誤りを検出・訂正する為の誤り訂正符
号とその符号化/復号化システムは重要なものとなって
きているが、なかでも、BCH符号、リード・ソロモン
符号は実用性の観点から、最も重要な符号と言えよう。
BCH符号、リード・ソロモン符号の復号化の処理にお
いては、一般に、シンドロームから誤す位置多項式を求
め、誤り位置多項式の根から誤り位置を求めるという手
順がとられるが、この誤り位置多項式の係数を入力し誤
り位置多項式の根を求め、誤りの位置を出力する為の誤
り位置検出装置は、上記符号の復号化処理において、最
も重要な要素の一つといえる。
いては、一般に、シンドロームから誤す位置多項式を求
め、誤り位置多項式の根から誤り位置を求めるという手
順がとられるが、この誤り位置多項式の係数を入力し誤
り位置多項式の根を求め、誤りの位置を出力する為の誤
り位置検出装置は、上記符号の復号化処理において、最
も重要な要素の一つといえる。
従来、この様な誤り位置検出には、チェノのアルゴリズ
ムが用いられるのが一般的であす、装置化されて広く使
用されている(例えば、宮用、岩垂、今回「符号理論」
(昭48)、昭晃堂、262〜264頁)。
ムが用いられるのが一般的であす、装置化されて広く使
用されている(例えば、宮用、岩垂、今回「符号理論」
(昭48)、昭晃堂、262〜264頁)。
以下、図面を参照しながら、上述したような従来の誤り
位置検出装置について説明を行うが、ここでは−例とし
て3次の誤り位置多項式から3つの誤り位置を求める場
合を考えることにする。また符号は非2元符号を考え、
有限体CF (2q)の元であるとする。
位置検出装置について説明を行うが、ここでは−例とし
て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は誤り位置を出力する出力端
子である。
ク図であって、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)式に
代入して行き、結果がゼロとなる元を根とするという方
法である。この方法によれば、処理時間が長くなる事を
問題にしなければ、誤り位置多項式がいかに高次なもの
であっても解くことができる。
・・・(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を代入したものがあられれることに
なる。
、装置化したものであって、まず、誤り位置多項式の各
項の係数σ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によってα を乗じたものに変化する。
えられると、レジスタ35に関しては、入力と出力が直
結されているので変化はないが、レジスタ36の入力/
出力間には定数αを乗じる係数器39が接続されている
ので、レジスタ36に記憶されている内容は、クロック
パルスが与えられる前の内容にαを乗じたものに変化す
る。同様にして、レジスタ37の内容は係数器4oによ
ってα を乗じたものに、レジスタ38の内容は係数器
41によってα を乗じたものに変化する。
ここで、αは有限体GF(2q)の原始光であり、した
がって有限体G F (2q)の全ての元はαのべき乗
であられされる。さて、この状態で加算器42の出力を
考えてみると、 α+ασ1+ασ2+σ3=σ(α) となり(1)式にαを代入したものがあられれることが
わかる。
がって有限体G F (2q)の全ての元はαのべき乗
であられされる。さて、この状態で加算器42の出力を
考えてみると、 α+ασ1+ασ2+σ3=σ(α) となり(1)式にαを代入したものがあられれることが
わかる。
以下同様にして、各レジスタにクロックパルスを逐次与
えて行くと、加算器42の出力には順次、(1)式にα
、α、・・・・・・を代入したものがちられれるので、
2q−1個のクロックパルスを与えることによって、加
算器42の出力に、(1)式に全ての元を代入した値を
得ることができるのである。この値がゼロとなる元が、
即ち、(2)式の方程式の根であるので、ゼロ検出器4
3によりて誤り位置を得ることができ、得られた誤り位
置は誤り位置レジスタ44に蓄積された後、出力端子4
6から出力されることとなる。
えて行くと、加算器42の出力には順次、(1)式にα
、α、・・・・・・を代入したものがちられれるので、
2q−1個のクロックパルスを与えることによって、加
算器42の出力に、(1)式に全ての元を代入した値を
得ることができるのである。この値がゼロとなる元が、
即ち、(2)式の方程式の根であるので、ゼロ検出器4
3によりて誤り位置を得ることができ、得られた誤り位
置は誤り位置レジスタ44に蓄積された後、出力端子4
6から出力されることとなる。
発明が解決しようとする問題点
しかしながら、上記のような構成では、2−1回のクロ
ックパルス入力が必須であり、しだがってqがある程度
大きくなってくると、処理に要する時間が極めて大きく
なるという重大な問題点を有していた。
ックパルス入力が必須であり、しだがってqがある程度
大きくなってくると、処理に要する時間が極めて大きく
なるという重大な問題点を有していた。
本発明は上記問題点に鑑み、必要とされるクロックパル
スを半減し、大幅に処理時間を短縮することができる誤
り位置検出装置を提供するものである。
スを半減し、大幅に処理時間を短縮することができる誤
り位置検出装置を提供するものである。
問題点を解決するための手段
上記問題点を解決するだめに、本発明の誤り位置検出装
置は、レジスタ出力を単純に加えあわせる加算器とゼロ
検出器に加えて、レジスタ出力に定数を乗じるだめの係
数器群と加算器及びゼロ検出器の組を複数組備えること
により、同時に複数の代入演算を行う構成をとるもので
ある。
置は、レジスタ出力を単純に加えあわせる加算器とゼロ
検出器に加えて、レジスタ出力に定数を乗じるだめの係
数器群と加算器及びゼロ検出器の組を複数組備えること
により、同時に複数の代入演算を行う構成をとるもので
ある。
作用
本発明は、上記した構成によって、1回のクロックパル
ス入力によって、複数個の、誤り位置多項式への元の代
入結果を同時に求めることにより、必要とされるクロッ
クパルス数を大幅に削減し、処理時間を大幅に短縮でき
ることとなる。
ス入力によって、複数個の、誤り位置多項式への元の代
入結果を同時に求めることにより、必要とされるクロッ
クパルス数を大幅に削減し、処理時間を大幅に短縮でき
ることとなる。
実施例
以下、本発明の一実施例の誤り位置検出装置について図
面を参照しながら説明する。
面を参照しながら説明する。
箭1図は本発明の一実施例における誤り位置検出装置の
構成を示したものである。第1図において、1〜4は誤
り位置多項式の各項の係数の入力端子、6〜8は入力端
子1〜4に接続された、qビット幅のレジスタ、9はレ
ジスタ6の入力/出力間に接続された定数α を乗じる
係数器、10はレジスタ7の入力/出力間に接続された
定数α4を乗じる係数器、11はレジスタ8の入力/出
力間に接続された定数α を乗じる係数器、16は各レ
ジスタの出力に接続された加算器、18は加算器15の
出力に接続されたゼロ検出器である。
構成を示したものである。第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は誤り位置を出力する出力端子である
。
乗じる係数器、13はレジスタ7の出力に接続された定
数α を乗じる係数器、14はレジスタ8の出力に接続
された定数α を乗じる係数器、16は各係数器出力及
びレジスタの出力に接続された加算器、17は加算器1
6の出力に接続されたゼロ検出器である。また、19は
ゼロ検出器17及びゼロ検出器18に接続された誤り位
置レジスタ、20は誤り位置を出力する出力端子である
。
以上のように構成された誤り位置検出装置について、以
下その動作を説明する。ここでも3次の誤り位置多項式
の根を求める、即ち、方程式σ(x)=x +σ1x
+σ2x+σ5=。
下その動作を説明する。ここでも3次の誤り位置多項式
の根を求める、即ち、方程式σ(x)=x +σ1x
+σ2x+σ5=。
を解いて3つの誤り位置を検出することを考える。
まず、誤り位置多項式の各項の係数σ3.σ2.σ1゜
及び1は、それぞれ、入力端子1〜4を通して、レジス
タ5〜8に入力される。この状態で加算器15の出力を
考えると、従来の構成と同様にσ(X)に1を代入した
もの、即ち、 σ(1)=1+σ1+σ2+σ5 があられれることになる。
及び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があられれる。
2によってαを乗じられたレジスタ6の出力と、係数器
13によってα を乗じられたレジスタ7の出力と、係
数器14によってα を乗しられたレジスタ8の出力と
が加えられるので、その出力には、σ(X)にαを代入
したもの、即ち、σ(α)=α +ασ1+ασ2+σ
5があられれる。
次に、各レジスタにクロックパルスが1回与えられると
、レジスタ6に関しては、入力と出力が直結されている
ので変化はないが、レジスタ6の入力/出力間には定数
α を乗じる係数器9が接続されているので、レジスタ
6に記憶されている内容は、クロックパルスが与えられ
る前の内容にα を乗じたものに変化する。同様にして
、レジスタ7の内容は係数器1oによってα を乗じた
ものに、レジスタ8の内容は係数器11によってα を
乗じたものに変化する。
、レジスタ6に関しては、入力と出力が直結されている
ので変化はないが、レジスタ6の入力/出力間には定数
α を乗じる係数器9が接続されているので、レジスタ
6に記憶されている内容は、クロックパルスが与えられ
る前の内容にα を乗じたものに変化する。同様にして
、レジスタ7の内容は係数器1oによってα を乗じた
ものに、レジスタ8の内容は係数器11によってα を
乗じたものに変化する。
しだがって、加算器15の出力にはσ(X)にα2を代
入したものが、同様に、加算器16の出力にばσ(X)
にα を代入したものが、あられれることになる。この
ようにして得られた代入結果はゼ口検出塁17及び18
に入力されて、ゼロを検出する事により根か否か判定し
、得られた根の位置は誤り位置レジスタ19に順次蓄積
され、出力端子2oから出力されることになる。
入したものが、同様に、加算器16の出力にばσ(X)
にα を代入したものが、あられれることになる。この
ようにして得られた代入結果はゼ口検出塁17及び18
に入力されて、ゼロを検出する事により根か否か判定し
、得られた根の位置は誤り位置レジスタ19に順次蓄積
され、出力端子2oから出力されることになる。
このように本実施例によれば、1回のクロックパルス入
力によって2つの代入結果が得られるので、従来の半分
のクロックパルス数で処理を行うことができるので、処
理時間の短縮ができるのである。
力によって2つの代入結果が得られるので、従来の半分
のクロックパルス数で処理を行うことができるので、処
理時間の短縮ができるのである。
なお、本実施例においては、2つの代入結果を同時に求
めたが、4つの代入結果を同時にもとめる誤り位置検出
装置も同様にして容易に構成することができる。この場
合には装置規模は大きくなるが、さらに短い時間で処理
を行うことができる。
めたが、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図
構成を示すブロック図、第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)
- 誤り位置多項式の各項の係数を入力し、記憶する為のレ
ジスタ群と、上記レジスタ群の各項に定数を乗じて更新
するための係数器群とを備えるとともに、上記レジスタ
群の各項出力を直接もしくは定数を乗じたのちに加えあ
わせて総和を求める手段と、その総和がゼロか否かを判
定するゼロ検出手段とを2組以上備え、さらに、上記各
ゼロ検出手段のゼロ検出出力を誤り位置として記憶する
ための誤り位置レジスタを具備してなる誤り位置検出装
置。
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)
| 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)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS62122333A (ja) * | 1985-11-21 | 1987-06-03 | Mitsubishi Electric Corp | シンドロ−ム回路 |
-
1986
- 1986-11-13 JP JP61270271A patent/JPH07114375B2/ja not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS62122333A (ja) * | 1985-11-21 | 1987-06-03 | Mitsubishi Electric Corp | シンドロ−ム回路 |
Cited By (1)
| 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 |