JPH0744466B2 - リ−ドソロモン符号・復号方式のシグマ演算回路 - Google Patents
リ−ドソロモン符号・復号方式のシグマ演算回路Info
- Publication number
- JPH0744466B2 JPH0744466B2 JP60113162A JP11316285A JPH0744466B2 JP H0744466 B2 JPH0744466 B2 JP H0744466B2 JP 60113162 A JP60113162 A JP 60113162A JP 11316285 A JP11316285 A JP 11316285A JP H0744466 B2 JPH0744466 B2 JP H0744466B2
- Authority
- JP
- Japan
- Prior art keywords
- circuit
- register
- unit
- input
- timing signal
- 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.)
- Expired - Lifetime
Links
- 238000004364 calculation method Methods 0.000 claims description 13
- 208000011580 syndromic disease Diseases 0.000 claims description 9
- 230000007274 generation of a signal involved in cell-cell signaling Effects 0.000 claims description 7
- 238000000034 method Methods 0.000 claims description 7
- 230000003252 repetitive effect Effects 0.000 claims 1
- 238000006243 chemical reaction Methods 0.000 description 4
- 238000007792 addition Methods 0.000 description 3
- 230000008878 coupling Effects 0.000 description 2
- 238000010168 coupling process Methods 0.000 description 2
- 238000005859 coupling reaction Methods 0.000 description 2
- 238000001514 detection method Methods 0.000 description 2
- 238000010586 diagram Methods 0.000 description 2
- 230000014509 gene expression Effects 0.000 description 2
- 101001106432 Homo sapiens Rod outer segment membrane protein 1 Proteins 0.000 description 1
- 102100021424 Rod outer segment membrane protein 1 Human genes 0.000 description 1
- 230000003111 delayed effect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
Landscapes
- Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、ディジタルオーディオ機器などに用いられる
誤り訂正可能なリードソロモン符号の復号方式、特にそ
の復号方式の一環として誤り位置多項式の係数演算回路
に関する。
誤り訂正可能なリードソロモン符号の復号方式、特にそ
の復号方式の一環として誤り位置多項式の係数演算回路
に関する。
ディジタルオーディオ機器では、記録媒体の情報を作成
する場合に、各種の原因により符号誤りが生ずる。その
ためランダム誤りの対策として、情報を符号化して、誤
り訂正可能な符号とする。誤り訂正可能な符号として
は、BCH符号，リードソロモン符号がよく知られてい
る。リードソロモン符号は非２元BCH符号の一種であ
り、ディジタルオーディオディスクプレーヤなどでは８
ビットの元を１シンボルとして取扱ったC1（32,28）符
号,C2（28,24）符号が実用されている。ここで括弧内第
１項は符号ブロック長のシンボル数，第２項は情報シン
ボル数である。上記C1,C2符号では検査シンボル数は４
個でシンボル間の最小距離は５シンボルとなり、シンド
ローム訂正能力は最大２シンボル訂正が可能である。と
ころで、将来さらに訂正能力を高めようとすると、最小
距離をもっと高めた符号としなければならない。訂正能
力を３シンボル,4シンボルと高めていくと、復号方式が
格段と複雑になる。
する場合に、各種の原因により符号誤りが生ずる。その
ためランダム誤りの対策として、情報を符号化して、誤
り訂正可能な符号とする。誤り訂正可能な符号として
は、BCH符号，リードソロモン符号がよく知られてい
る。リードソロモン符号は非２元BCH符号の一種であ
り、ディジタルオーディオディスクプレーヤなどでは８
ビットの元を１シンボルとして取扱ったC1（32,28）符
号,C2（28,24）符号が実用されている。ここで括弧内第
１項は符号ブロック長のシンボル数，第２項は情報シン
ボル数である。上記C1,C2符号では検査シンボル数は４
個でシンボル間の最小距離は５シンボルとなり、シンド
ローム訂正能力は最大２シンボル訂正が可能である。と
ころで、将来さらに訂正能力を高めようとすると、最小
距離をもっと高めた符号としなければならない。訂正能
力を３シンボル,4シンボルと高めていくと、復号方式が
格段と複雑になる。
復号方式は、いくつかの段階にわけて行なわれ、先ずシ
ンドロームを求めてから、符号ブロック内の誤りのある
シンボルの位置を決める。誤りのあるシンボルの位置は
誤り位置多項式に、原始根αのべき指数aiで表わされる
シンボルを順次投入し誤り位置多項式を零とするｉの値
からきめられる。本発明は誤り位置多項式の係数を求め
ようとするものである。２シンボル誤り訂正能力をもつ
リードソロモン符号の場合には、前記多項式は１＋σ1X
＋σ2X2と表わされ、この係数σ1,σ２はシンドロームS
0〜S3からやや複雑だが、代数式で得られる。
ンドロームを求めてから、符号ブロック内の誤りのある
シンボルの位置を決める。誤りのあるシンボルの位置は
誤り位置多項式に、原始根αのべき指数aiで表わされる
シンボルを順次投入し誤り位置多項式を零とするｉの値
からきめられる。本発明は誤り位置多項式の係数を求め
ようとするものである。２シンボル誤り訂正能力をもつ
リードソロモン符号の場合には、前記多項式は１＋σ1X
＋σ2X2と表わされ、この係数σ1,σ２はシンドロームS
0〜S3からやや複雑だが、代数式で得られる。
しかし、３シンボル以上の誤り訂正能力をもつリードソ
ロモン符号では、係数σ1,σ２…は極めて複雑になり、
最初から特定の代数式から得ることは実際上できない。
ロモン符号では、係数σ1,σ２…は極めて複雑になり、
最初から特定の代数式から得ることは実際上できない。
このような多シンボル誤り訂正能力のあるリードソロモ
ン符号の場合には、いわゆるバーレカンプ・マッシイの
方法が適している。この方法の説明については、符号論
理を取扱った著書、例えば宮川洋・他著「符号理論」昭
晃堂３版257頁以下を参照し、結果のみを記述する。
ン符号の場合には、いわゆるバーレカンプ・マッシイの
方法が適している。この方法の説明については、符号論
理を取扱った著書、例えば宮川洋・他著「符号理論」昭
晃堂３版257頁以下を参照し、結果のみを記述する。
この方法は結合多項式といわれる次式の多項式Cn（Ｘ）
＝１＋Cn,1X＋Cn,2X2＋… （１） が、例えば検査シンボル数が６で、誤り訂正能力が３シ
ンボルの場合には C6（Ｘ）＝１＋C6,1X＋C6,2X2＋C6,3 X3＝σ（Ｘ）＝σ０＋σ1X＋σ2X2＋σ3X3 （２） として誤り位置多項式σ（Ｘ）を各係数をC6,1,C6,2,
C6,3により求めることができる。
＝１＋Cn,1X＋Cn,2X2＋… （１） が、例えば検査シンボル数が６で、誤り訂正能力が３シ
ンボルの場合には C6（Ｘ）＝１＋C6,1X＋C6,2X2＋C6,3 X3＝σ（Ｘ）＝σ０＋σ1X＋σ2X2＋σ3X3 （２） として誤り位置多項式σ（Ｘ）を各係数をC6,1,C6,2,
C6,3により求めることができる。
Cn（Ｘ）は、C0（Ｘ）＝１からスタートし、次の繰返し
アルゴリズムにより求められる。
アルゴリズムにより求められる。
結合多項式は漸化式 Cn+1(X)＝Cｎ(X)-(δn/δk(n))・Xn-k(n)Ck(n)(X)（３） ｎ＝０における初期値C0（Ｘ）＝C-1（Ｘ）＝1,u0＝u-1
＝0,δ-1＝１ （８） で、ｎ＝０から始めｎ＝1,2,…として例えばC6（Ｘ）を
求める。しかし、上記のように計算上求められるが、自
動的に具体的な演算回路で求めた例ば現在周知でない。
＝0,δ-1＝１ （８） で、ｎ＝０から始めｎ＝1,2,…として例えばC6（Ｘ）を
求める。しかし、上記のように計算上求められるが、自
動的に具体的な演算回路で求めた例ば現在周知でない。
本発明の目的は、バーレカンプ・マッシイの方法にもと
づき多シンボル訂正可能なリードソロモン符号の誤り位
置多項式の係数を求める実行回路を提供することにあ
る。この場合、ディジタル回路でいかに回路規模を小さ
く、かつまた処理速度を高速化するかが重要な課題のひ
とつであった。
づき多シンボル訂正可能なリードソロモン符号の誤り位
置多項式の係数を求める実行回路を提供することにあ
る。この場合、ディジタル回路でいかに回路規模を小さ
く、かつまた処理速度を高速化するかが重要な課題のひ
とつであった。
本発明では上記の漸化式による（３）〜（８）式の演算
は、さらに第３図に示すフローチャートにより実行され
ることに着目している。このフローチャートは文献E.R.
BERLEKAMP著「ALGEBRAIC CODING THEORY」，マグローヒ
ル社によるものである。
は、さらに第３図に示すフローチャートにより実行され
ることに着目している。このフローチャートは文献E.R.
BERLEKAMP著「ALGEBRAIC CODING THEORY」，マグローヒ
ル社によるものである。
上記フローチャートは３シンボル訂正の場合で、R1,R2,
R3はレジスタである。R1はCn（Ｘ）であって （ただしCn,0＝１を除く）を示し、また、R2は▲〔Ｓ
（Ｘ）〕ｎ σ▼であって を,R3はXn-k(n)Ck(n)（Ｘ）であって （F0＝０は除く）を示す。
R3はレジスタである。R1はCn（Ｘ）であって （ただしCn,0＝１を除く）を示し、また、R2は▲〔Ｓ
（Ｘ）〕ｎ σ▼であって を,R3はXn-k(n)Ck(n)（Ｘ）であって （F0＝０は除く）を示す。
３シンボル以上であれば各レジスタの桁数を増加すれば
よい。
よい。
したがって、本発明においては、上記フローチャートに
表れる各種の乗算・除算・加算を効果的に行なう計数部
と、レジスタを設け、適切なタイミングによって動作さ
せることにより、ｎ＝０よりスタートして最終的にはR1
レジスタの中に、シグマ係数値をストアするから、その
回路規模は小さくなり、かつ例えば３つのシグマσ1,σ
2,σ３を同時に演算するのでその処理時間も短くするこ
とができる。
表れる各種の乗算・除算・加算を効果的に行なう計数部
と、レジスタを設け、適切なタイミングによって動作さ
せることにより、ｎ＝０よりスタートして最終的にはR1
レジスタの中に、シグマ係数値をストアするから、その
回路規模は小さくなり、かつ例えば３つのシグマσ1,σ
2,σ３を同時に演算するのでその処理時間も短くするこ
とができる。
本発明の演算回路はCn,1,Cn,2…ごとにデータバスとデ
ータバスに接続される計数部および複数個のレジスタ成
分とを含む複数個の演算ブロックと，δn/δk(n)を定め
る演算部と，繰返しアルゴリズムにおける条件フラグを
発生する制御信号発生部およびタイミング信号発生部と
からなっている。
ータバスに接続される計数部および複数個のレジスタ成
分とを含む複数個の演算ブロックと，δn/δk(n)を定め
る演算部と，繰返しアルゴリズムにおける条件フラグを
発生する制御信号発生部およびタイミング信号発生部と
からなっている。
前記演算ブロックにおいて、計数部はデータバスからの
入力ベクトル値をべき指数値に変換しMOD演算後、ベク
トル値に変換して出力する乗算回路と，該乗算回路の出
力とデータバスからの入力とをベクトル加算する加算回
路とからなり、前記レジスタ成分は各演算ブロックにそ
の各成分が配置されてなる３個のレジスタでそれぞれCn
（Ｘ），▲〔Ｓ（Ｘ）〕ｎ σ▼,Xn-k(n)Ck(n)（Ｘ）を
表わすR1,R2,R3レジスタの各成分であり、R2レジスタ,R
3レジスタは各成分が直列に接続されCn,1演算ブロック
側からそれぞれシンドローム，所定データが入力され、
Cn,2,Cn,3…演算ブロック側へシフト可能の結線となっ
ている。
入力ベクトル値をべき指数値に変換しMOD演算後、ベク
トル値に変換して出力する乗算回路と，該乗算回路の出
力とデータバスからの入力とをベクトル加算する加算回
路とからなり、前記レジスタ成分は各演算ブロックにそ
の各成分が配置されてなる３個のレジスタでそれぞれCn
（Ｘ），▲〔Ｓ（Ｘ）〕ｎ σ▼,Xn-k(n)Ck(n)（Ｘ）を
表わすR1,R2,R3レジスタの各成分であり、R2レジスタ,R
3レジスタは各成分が直列に接続されCn,1演算ブロック
側からそれぞれシンドローム，所定データが入力され、
Cn,2,Cn,3…演算ブロック側へシフト可能の結線となっ
ている。
前記δn/δk(n)演算部は、各演算ブロックの乗算回路の
出力Cn,1Sn-1,Cn,2Sn-2,…およびSnを入力して加算し、
べき指数値に変換したδｎについて、MOD演算後ベクト
ル値に変換して各演算ブロックのデータバスに出力する
回路を構成している。
出力Cn,1Sn-1,Cn,2Sn-2,…およびSnを入力して加算し、
べき指数値に変換したδｎについて、MOD演算後ベクト
ル値に変換して各演算ブロックのデータバスに出力する
回路を構成している。
前記条件フラグを発生する制御信号発生部は、前記δn/
δk(n)演算部で求められたδｎにつきδｎ＝０を示すδ
ｎフラグと、n,un,n2unの各フラグを発生する回路か
らなっている。
δk(n)演算部で求められたδｎにつきδｎ＝０を示すδ
ｎフラグと、n,un,n2unの各フラグを発生する回路か
らなっている。
前記タイミング信号発生部は、前記演算ブロック・δn/
δk(n)演算部・制御信号発生部を動作させるタイミング
パルスを発生し、条件フラグによってこのタイミング信
号の発生タイミングを制御するものである。
δk(n)演算部・制御信号発生部を動作させるタイミング
パルスを発生し、条件フラグによってこのタイミング信
号の発生タイミングを制御するものである。
本発明の演算回路は第３図に示すフローチャートの実行
回路で、ｎ＝０から始めてタイミング信号発生部からの
タイミング信号によって各構成部が動作する。ｎ＝ｄ−
２（ｄは最小シンボル間隔）まで繰返すことで、（ｄ−
１）/2の誤り訂正可能なシンボルにつき誤り位置多項式
の各係数の値が求められR1レジスタに係数値が格納され
ることになる。動作の詳細な説明は実施例にて説明す
る。
回路で、ｎ＝０から始めてタイミング信号発生部からの
タイミング信号によって各構成部が動作する。ｎ＝ｄ−
２（ｄは最小シンボル間隔）まで繰返すことで、（ｄ−
１）/2の誤り訂正可能なシンボルにつき誤り位置多項式
の各係数の値が求められR1レジスタに係数値が格納され
ることになる。動作の詳細な説明は実施例にて説明す
る。
図面を参照して、本発明の実施例につき説明する。実施
例はすべて３シンボル訂正可能な符号についての回路と
する。第１図に演算ブロック、第２図にδn/δk(n)演算
部、条件フラグ発生の制御信号発生部およびタイミング
信号発生部とを示す。
例はすべて３シンボル訂正可能な符号についての回路と
する。第１図に演算ブロック、第２図にδn/δk(n)演算
部、条件フラグ発生の制御信号発生部およびタイミング
信号発生部とを示す。
第１図において、10,20,30は演算ブロックで、それぞれ
Cn,1,Cn,2,Cn,3に相当するものである。計数部の内部回
路は同一で計数部11についてのみ図示してある。データ
バス＃1,＃2,＃３に接続されるフリップフロップは＃１
に接続されるフリップフロップ14を除き、エネーブル端
子付きのＤ形のフリップフロップである。フリップフロ
ップ14はバッファとして動作する。上記素子群は図示の
ように横方向にそれぞれR1レジスタ、R2レジスタ、R3レ
ジスタを形成しているが、R1レジスタのフリップフロッ
プ12,22,32はデータバス＃1,＃2,＃３とのみデータの受
渡しを行なうが、R2レジスタ、R3レジスタは右方向にシ
フトできる。そして、R2レジスタにはシンドロームバス
SnからシンドロームS0,S1…が入力され、R3レジスタに
はP6のタイミング信号でP7の状況により“1"または“0"
が入力される。
Cn,1,Cn,2,Cn,3に相当するものである。計数部の内部回
路は同一で計数部11についてのみ図示してある。データ
バス＃1,＃2,＃３に接続されるフリップフロップは＃１
に接続されるフリップフロップ14を除き、エネーブル端
子付きのＤ形のフリップフロップである。フリップフロ
ップ14はバッファとして動作する。上記素子群は図示の
ように横方向にそれぞれR1レジスタ、R2レジスタ、R3レ
ジスタを形成しているが、R1レジスタのフリップフロッ
プ12,22,32はデータバス＃1,＃2,＃３とのみデータの受
渡しを行なうが、R2レジスタ、R3レジスタは右方向にシ
フトできる。そして、R2レジスタにはシンドロームバス
SnからシンドロームS0,S1…が入力され、R3レジスタに
はP6のタイミング信号でP7の状況により“1"または“0"
が入力される。
次に計数部11について、説明する。ベクトル入力がROM1
1によって原始根αのべき指数表示の指数に変換され、
フリップフロップ112,MOD演算回路113,フリップフロッ
プ114で指数の加算をなしROM115でベクトル表示にして
出力する。この部分が乗算回路で、EX−OR回路117,フリ
ップフロップ118がベクトル加算回路を構成する。なお
ゼロ検出回路120,AND回路116はベクトル入力が“0"のと
き乗算の結果は“0"であるから“0"を出力するためであ
る。これはMOD演算が、ベクトル入力が“0"のときは正
しく動作しないからである。計数部11から乗算回路の出
力がフリップフロップ119を介してCn,1Sn-1が、第２図
のδn/δk(n)演算部に導かれる。
1によって原始根αのべき指数表示の指数に変換され、
フリップフロップ112,MOD演算回路113,フリップフロッ
プ114で指数の加算をなしROM115でベクトル表示にして
出力する。この部分が乗算回路で、EX−OR回路117,フリ
ップフロップ118がベクトル加算回路を構成する。なお
ゼロ検出回路120,AND回路116はベクトル入力が“0"のと
き乗算の結果は“0"であるから“0"を出力するためであ
る。これはMOD演算が、ベクトル入力が“0"のときは正
しく動作しないからである。計数部11から乗算回路の出
力がフリップフロップ119を介してCn,1Sn-1が、第２図
のδn/δk(n)演算部に導かれる。
第２図（ａ）にδn/δk(n)演算部40を示す。41はEX−OR
回路でΣCn,i・Sn-iを計算しδｎを求めた後、δn/δ
k(n)を求めるため、ベクトルをべき指数に変換し除算
し、再びベクトルに変換している。すなわちROM42出力
の指数値δｎから、δk(n)を求めるため、フリップフロ
ップ43で遅延してから反転し、MOD演算回路44でσｎと
の差をとっている。δn/δk(n)のベクトル値はフリップ
フロップ47,48,49によって、データバス＃1,＃2,＃３に
分配される。
回路でΣCn,i・Sn-iを計算しδｎを求めた後、δn/δ
k(n)を求めるため、ベクトルをべき指数に変換し除算
し、再びベクトルに変換している。すなわちROM42出力
の指数値δｎから、δk(n)を求めるため、フリップフロ
ップ43で遅延してから反転し、MOD演算回路44でσｎと
の差をとっている。δn/δk(n)のベクトル値はフリップ
フロップ47,48,49によって、データバス＃1,＃2,＃３に
分配される。
第２図（ｂ）は制御信号発生部50を示すもので、カウン
タ51から繰返し回数ｎをｎフラグとして出力する。また
フリップフロップ52,インバータ53,加算回路54,55はun
をｎ−un＋１としてクロック入力P2ごとに更新する回路
であって、フリップフロップ57を介してunフラグを出力
するとともに、コンパレータ56でｎとunとを入力し、対
応する端子の桁を１桁ずらすことでｎ2unを検出しｎ
2unフラグを出力する。
タ51から繰返し回数ｎをｎフラグとして出力する。また
フリップフロップ52,インバータ53,加算回路54,55はun
をｎ−un＋１としてクロック入力P2ごとに更新する回路
であって、フリップフロップ57を介してunフラグを出力
するとともに、コンパレータ56でｎとunとを入力し、対
応する端子の桁を１桁ずらすことでｎ2unを検出しｎ
2unフラグを出力する。
第２図（ｃ）はタイミング信号発生部60を示すもので、
マイクロプログラミング回路によりクロック入力ごとに
所要のタイミング信号P0,P1,…を発生し、フラグ入力を
適当なタインミング時点で入力し、フラグにより、ジャ
ンプする。タイミング信号については第６図に示す。
マイクロプログラミング回路によりクロック入力ごとに
所要のタイミング信号P0,P1,…を発生し、フラグ入力を
適当なタインミング時点で入力し、フラグにより、ジャ
ンプする。タイミング信号については第６図に示す。
この演算回路は第３図のフローチャートに示す演算を行
なうが、第３図に基づき、回路動作を詳細に分解してフ
ローチャート形式で第４図，第５図に示す。このときの
タイミング信号のタイムチャートは第６図である。第６
図上段に示す時間区分T1,T2,…ごとに、第４図，第５図
は記載されている。第４図〜第６図の補完の意味で以
下、時間区分ごとに簡単に説明を加える。以下でフリッ
プフロップはDFFと略称する。
なうが、第３図に基づき、回路動作を詳細に分解してフ
ローチャート形式で第４図，第５図に示す。このときの
タイミング信号のタイムチャートは第６図である。第６
図上段に示す時間区分T1,T2,…ごとに、第４図，第５図
は記載されている。第４図〜第６図の補完の意味で以
下、時間区分ごとに簡単に説明を加える。以下でフリッ
プフロップはDFFと略称する。
T1:カウンタ51,DFF52,43,119（図面にはないが対応する
ものとして219,319以下同様）をリセットする。DFF24,3
4はデータバス＃1,＃２がローで“0"をとりこむ T2:DFF13,23,33が動作し、R3レジスタに（100）セット T3:DFF12,22,32が動作し、R1レジスタ（000）セット T4:δｎ＝０フラグ，δｎ＝０ならば“0",δｎ≠０なら
ば“1" T5:δｎ＝０の場合で、DFF13,23,33が動作、R3レジスタ
のデータがバスに送られ、右側のDFFにストアされる。
ただしDFF13は“0"となる T6:DFF12,DFF112（212,312）動作、後でR1×R3を計算し
δｎを求めるためである T7:n2unフラグ,n2unならば“0",n＜2unならば“1" T8:n2unの場合で、DFF13,23,33が動作し、データバス
＃1,2,3を経て、DFF112,212,312にラッチされる。DFF4
7,48,49にδn/δk(n)ストア T9:DFF47,48,49よりδn/δk(n)を出力しδn/δk(n)×R3
の演算結果をDFF114（214,314）にストア T10:DFF12,22,32のR1レジスタのデータをバスに送りDFF
23,33でR3レジスタにストアする。このときR1レジスタ
のデータをR3レジスタに移し同時にシフトされ、またR3
レジスタの左端DFF13は“1"をストアすることになる またR1レジスタのデータはバスを介して計数部10（20,3
0）のEX−OR回路117（217,317）で加算され、DFF118（2
18,318）に（δn/δk(n)×R3）＋R1をストア T11:DFF118（218,318）から（δn/δk(n)×R3）＋R1を
バスに送出し、乗算回路のDFF112（212,312）および、D
FF12,22,32のR1レジスタにストア また、δn/δk(n)演算部40でDFF43がδk(n)を送出し、
制御信号発生部50でunが計算される T12:R3レジスタのDFF13,23,33のデータをバスに送り乗
算回路のDF112（212,312）にストア同時にDFF13,23のデ
ータが右シフトし、DFF13に“0"がストアされる また、DFF47,48,49にδn/δk(n)ストア T13:T9と同じ T14:R1レジスタDFF12,22,32のデータをバスに送りEX−O
R回路117（217,317）で加算しDFF118（218,318）にスト
ア T15:DF118（218,318）のデータをバスを介してR1レジス
タDFF12,22,32にストアまた新しいR1としてDFF112（21
2,312）にストア T16:カウンタ51を１カウントする。DFF24,34を右シフト
し、DFF14にSn+1をストア このとき乗算回路にR2レジスタのデータがバスを介して
入力しR1×R2の演算結果をDFF114（214,314）にストア T17:計数部11（21,31）のDFF119（219,319）にR1×R2,
すなわちCn,1Sn-1,Cn,2Sn-2,Cn,3Sn-3をストア 同時にδｎが演算される ３シンボル訂正可能な信号では、ｄ＝7,n＝ｄ−２＝５
であるから後４回繰返せば、R1レジスタのDFF12,22,32
にC6,1＝σ1,C6,2＝σ2,C6,3＝σ３がストアされるか
ら、データバス＃1,＃2,＃３から出力することができ
る。
ものとして219,319以下同様）をリセットする。DFF24,3
4はデータバス＃1,＃２がローで“0"をとりこむ T2:DFF13,23,33が動作し、R3レジスタに（100）セット T3:DFF12,22,32が動作し、R1レジスタ（000）セット T4:δｎ＝０フラグ，δｎ＝０ならば“0",δｎ≠０なら
ば“1" T5:δｎ＝０の場合で、DFF13,23,33が動作、R3レジスタ
のデータがバスに送られ、右側のDFFにストアされる。
ただしDFF13は“0"となる T6:DFF12,DFF112（212,312）動作、後でR1×R3を計算し
δｎを求めるためである T7:n2unフラグ,n2unならば“0",n＜2unならば“1" T8:n2unの場合で、DFF13,23,33が動作し、データバス
＃1,2,3を経て、DFF112,212,312にラッチされる。DFF4
7,48,49にδn/δk(n)ストア T9:DFF47,48,49よりδn/δk(n)を出力しδn/δk(n)×R3
の演算結果をDFF114（214,314）にストア T10:DFF12,22,32のR1レジスタのデータをバスに送りDFF
23,33でR3レジスタにストアする。このときR1レジスタ
のデータをR3レジスタに移し同時にシフトされ、またR3
レジスタの左端DFF13は“1"をストアすることになる またR1レジスタのデータはバスを介して計数部10（20,3
0）のEX−OR回路117（217,317）で加算され、DFF118（2
18,318）に（δn/δk(n)×R3）＋R1をストア T11:DFF118（218,318）から（δn/δk(n)×R3）＋R1を
バスに送出し、乗算回路のDFF112（212,312）および、D
FF12,22,32のR1レジスタにストア また、δn/δk(n)演算部40でDFF43がδk(n)を送出し、
制御信号発生部50でunが計算される T12:R3レジスタのDFF13,23,33のデータをバスに送り乗
算回路のDF112（212,312）にストア同時にDFF13,23のデ
ータが右シフトし、DFF13に“0"がストアされる また、DFF47,48,49にδn/δk(n)ストア T13:T9と同じ T14:R1レジスタDFF12,22,32のデータをバスに送りEX−O
R回路117（217,317）で加算しDFF118（218,318）にスト
ア T15:DF118（218,318）のデータをバスを介してR1レジス
タDFF12,22,32にストアまた新しいR1としてDFF112（21
2,312）にストア T16:カウンタ51を１カウントする。DFF24,34を右シフト
し、DFF14にSn+1をストア このとき乗算回路にR2レジスタのデータがバスを介して
入力しR1×R2の演算結果をDFF114（214,314）にストア T17:計数部11（21,31）のDFF119（219,319）にR1×R2,
すなわちCn,1Sn-1,Cn,2Sn-2,Cn,3Sn-3をストア 同時にδｎが演算される ３シンボル訂正可能な信号では、ｄ＝7,n＝ｄ−２＝５
であるから後４回繰返せば、R1レジスタのDFF12,22,32
にC6,1＝σ1,C6,2＝σ2,C6,3＝σ３がストアされるか
ら、データバス＃1,＃2,＃３から出力することができ
る。
以上、詳記したように本発明によって、３シンボル以上
の誤り訂正可能なリードソロモン符号の復号方式におけ
る誤り位置多項式の係数を、バーレカンプ・マッシイの
方法によるアルゴリズムを用い回路規模を小さくすると
ともに、複数個のシグマ係数の同時演算をするので、処
理時間を高速化できる。
の誤り訂正可能なリードソロモン符号の復号方式におけ
る誤り位置多項式の係数を、バーレカンプ・マッシイの
方法によるアルゴリズムを用い回路規模を小さくすると
ともに、複数個のシグマ係数の同時演算をするので、処
理時間を高速化できる。
第１図、第２図は本発明の一実施例の回路ブロック図、
第３図はバーレカンプ・マッシイの方法のアルゴリズム
を示すフローチャート、第４図・第５図は実施例の回路
動作を説明する図、第６図はタイムチャートである。 10,20,30……演算ブロック、 11,21,31……計数部、 12〜14,22〜24,32〜34……フリップフロップ、 111……ROM（Ｖ→Ｉ変換）、 115……ROM（Ｉ→Ｖ変換）、 112,114,118,119……フリップフロップ、 113……MOD演算回路、 116……AND回路、117……EX−OR回路、 120……ゼロ検出回路、 40……δn/δk(n)演算部、 41……EX−OR回路、 42,45……ROM（Ｖ→Ｉ変換,I→Ｖ変換）、 43……フリップフロップ、 44……MOD演算回路、 47〜49……フリップフロップ、 50……制御信号発生部、51……カウンタ、 52,57……フリップフロップ、 54,55……加算回路、56……コンパレータ、 60……タイミング信号発生部。
第３図はバーレカンプ・マッシイの方法のアルゴリズム
を示すフローチャート、第４図・第５図は実施例の回路
動作を説明する図、第６図はタイムチャートである。 10,20,30……演算ブロック、 11,21,31……計数部、 12〜14,22〜24,32〜34……フリップフロップ、 111……ROM（Ｖ→Ｉ変換）、 115……ROM（Ｉ→Ｖ変換）、 112,114,118,119……フリップフロップ、 113……MOD演算回路、 116……AND回路、117……EX−OR回路、 120……ゼロ検出回路、 40……δn/δk(n)演算部、 41……EX−OR回路、 42,45……ROM（Ｖ→Ｉ変換,I→Ｖ変換）、 43……フリップフロップ、 44……MOD演算回路、 47〜49……フリップフロップ、 50……制御信号発生部、51……カウンタ、 52,57……フリップフロップ、 54,55……加算回路、56……コンパレータ、 60……タイミング信号発生部。
Claims (1)
- 【請求項１】多シンボル訂正能力をもつリードソロモン
符号の復合に際し、バーレカンプ・マッシイの方法にも
とづき、シンドロームSnを入力とし、結合多項式C
n（Ｘ）＝１＋Cn,1X＋Cn,2X2＋・・・の漸化式C
n+1（Ｘ）＝Cn（Ｘ）−（δn/δk(n)）Xn-k(n)C
k(n)（Ｘ）を利用し、ｎ＝０から初めて、σ１＝Cn,1,
σ２＝Cn,2・・・として誤り位置多項式の係数σ1,σ２
・・・を定める繰返しアルゴリムズを実行する演算回路
であって、 Cn,1,Cn,2・・・ごとに定められるデータバスと該デー
タバスに接続される計数部および複数個のレジスタ成分
から構成される複数個の演算ブロックと、前記演算ブロ
ックからの出力により前記漸化式の係数δn/δk(n)を定
める演算を行なうδn/δk(n)演算部と、各動作に必要な
タイミング信号を発生するタイミング信号発生部と、前
記タイミング信号発生部からのタイミング信号により、
前記繰返しアルゴリズムにおける条件フラグを発生する
制御信号発生部とから構成され、 前記演算ブロックにおいて、計数部はデータバスからの
入力ベクトル値をべき指数値に変換しMOD演算後、ベク
トル値に変換して出力する乗算回路と、該乗算回路の出
力とデータバスからの入力とをベクトル加算する加算回
路とからなり、前記レジスタ成分は前記各演算ブロック
にその各成分が配置されてなる３個のレジスタでそれぞ
れ前記漸化式のCn（Ｘ），シンドローム入力〔Ｓ
（Ｘ）〕n,前記漸化式のXn-k(n)Ck(n)（Ｘ）を表すR1,R
2,R3レジスタの各成分であり、R2レジスタ、R3レジスタ
は各成分が直列に接続され、Cn,1演算ブロック側からそ
れぞれシンドローム、所定データが入力され、Cn,2,Cn,
3・・・演算ブロック側へシフト可能の結線となってお
り、 前記δn/δk(n)演算部は、前記各演算ブロックの乗算回
路の出力Cn,1Sn-1,Cn,2Sn-2・・・およびSnを入力して
加算し、べき指数値に変換したδｎについて、MOD演算
後ベクトル値に変換して前記各演算ブロックのデータバ
スに出力する回路を構成し、 前記条件フラグを発生する制御信号発生部は、前記δn/
δk(n)演算部で求められたδｎにつきδｎ＝０を示すδ
ｎフラグと、前記繰返しアルゴリズムの繰返し回数を示
すn,前記演算ブロックの演算パラメータを示すun,前記
演算ブロックの演算時における条件を示すｎ2unの各
フラグを発生する回路からなり、 前記タイミング信号発生部は、前記演算ブロック・前記
δn/δk(n)演算部・前記制御信号発生部を動作させるタ
イミング信号を発生し、前記制御信号発生部で発生させ
た条件フラグによって、このタイミング信号の発生タイ
ミングを制御することを特徴とする、リードソロモン符
号・復合方式のシグマ演算回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60113162A JPH0744466B2 (ja) | 1985-05-28 | 1985-05-28 | リ−ドソロモン符号・復号方式のシグマ演算回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60113162A JPH0744466B2 (ja) | 1985-05-28 | 1985-05-28 | リ−ドソロモン符号・復号方式のシグマ演算回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61273018A JPS61273018A (ja) | 1986-12-03 |
| JPH0744466B2 true JPH0744466B2 (ja) | 1995-05-15 |
Family
ID=14605119
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60113162A Expired - Lifetime JPH0744466B2 (ja) | 1985-05-28 | 1985-05-28 | リ−ドソロモン符号・復号方式のシグマ演算回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0744466B2 (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH07112160B2 (ja) * | 1986-04-21 | 1995-11-29 | ソニー株式会社 | 誤り訂正符号の復号方法 |
| JPH06104773A (ja) * | 1992-07-20 | 1994-04-15 | Internatl Business Mach Corp <Ibm> | 線形代数符号のキー式の解を求めるためのプログラム可能な逐次形キー式求解回路及び方法 |
-
1985
- 1985-05-28 JP JP60113162A patent/JPH0744466B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPS61273018A (ja) | 1986-12-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR101616478B1 (ko) | 프로그램가능한 프로세서 상에서의 임의의 갈루아 필드 산술연산의 구현 | |
| EP0329789B1 (en) | Galois field arithmetic unit | |
| WO2000057561A1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| JPS59124011A (ja) | 多数バイトエラ−訂正システム | |
| JPH0728227B2 (ja) | Ｂｃｈ符号の復号装置 | |
| JPS63186338A (ja) | 誤り訂正回路 | |
| CN114942861A (zh) | Crc计算方法、装置、计算机设备及存储介质 | |
| EP0566215A2 (en) | Error correction apparatus | |
| JPH0744466B2 (ja) | リ−ドソロモン符号・復号方式のシグマ演算回路 | |
| EP0329775A4 (en) | High bandwidth reed-solomon encoding, decoding and error correcting circuit | |
| JPH10322226A (ja) | リードソロモン復号方法 | |
| JP2797569B2 (ja) | ユークリッドの互除回路 | |
| JP3850512B2 (ja) | リードソロモン復号装置 | |
| JP2694794B2 (ja) | 誤り訂正処理方法 | |
| JPH04365139A (ja) | 誤り訂正処理用シンドローム演算回路 | |
| JP2797570B2 (ja) | ユークリッドの互除回路 | |
| JP3139499B2 (ja) | 誤り訂正処理装置 | |
| JP2600681B2 (ja) | リード・ソロモン符号の復号方法 | |
| JP3230888B2 (ja) | ユークリッド互除回路 | |
| JP2600683B2 (ja) | リード・ソロモン符号の復号方法 | |
| KR950008485B1 (ko) | 단일에러정정용 리드-솔로몬 복호기 | |
| JP2710176B2 (ja) | 誤り位置及び誤りパターン導出回路 | |
| JP2585361B2 (ja) | リ−ド・ソロモン符号の誤り位置と誤りパタ−ンの抽出装置 | |
| JP2752510B2 (ja) | 誤り訂正復号器 | |
| JPH1065552A (ja) | 誤り訂正の演算処理方法及び処理回路 |