JPH0653842A - Ｒｓコードデータ信号を復号化する方法および回路 - Google Patents

Ｒｓコードデータ信号を復号化する方法および回路

Info

Publication number
JPH0653842A
JPH0653842A JP4325812A JP32581292A JPH0653842A JP H0653842 A JPH0653842 A JP H0653842A JP 4325812 A JP4325812 A JP 4325812A JP 32581292 A JP32581292 A JP 32581292A JP H0653842 A JPH0653842 A JP H0653842A
Authority
JP
Japan
Prior art keywords
error
data signal
value
code data
decoding
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.)
Pending
Application number
JP4325812A
Other languages
English (en)
Inventor
Roland Mester
メステル ローランド
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.)
Koninklijke Philips NV
Original Assignee
Philips Gloeilampenfabrieken NV
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 Philips Gloeilampenfabrieken NV filed Critical Philips Gloeilampenfabrieken NV
Publication of JPH0653842A publication Critical patent/JPH0653842A/ja
Pending legal-status Critical Current

Links

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
    • H03M13/1545—Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial
    • 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
    • H03M13/1515—Reed-Solomon codes
    • 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
    • H03M13/1525—Determination and particular use of error location polynomials
    • H03M13/1535—Determination and particular use of error location polynomials using the Euclid algorithm
    • 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
    • H03M13/154—Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
    • 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
    • H03M13/1585—Determination of error values
    • 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/65—Purpose and implementation aspects
    • H03M13/6508—Flexibility, adaptability, parametrability and configurability of the implementation
    • H03M13/6516—Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields

Landscapes

  • Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)

Abstract

(57)【要約】 【目的】 高速データレートで存在するＲＳコードデー
タ信号をリアルタイムで復号化できる方法及び回路を提
供する。 【構成】 コード生成多項式Ｇ（ｘ）＝（ｘ＋α0 ）
（ｘ＋α1 ）・・・（ｘ＋α15）、及びコード生成多項
式Ｇ（ｘ）＝（ｘ＋α120 ）（ｘ＋α121 ）・・・（ｘ
＋α135 ）の双方によってコード化されたＲＳコードデ
ータ信号の復号化方法及び回路であって、これらコード
生成多項式によって、シンドローム発生器中の２つの異
なる定乗算器間でスイッチングを行い、決定されたシン
ドローム及び消去位置に対してユークリッドアルゴリズ
ムを行って、エラ−位置多項式及びエラー値多項式を導
き出す。α0 で始まるコード生成多項式に対するエラー
位置及びエラー値は、チェン・ゼロ検索によって計算さ
れ、並行して、α120 で始まるコード生成多項式に対す
る訂正ファクタが決定される。α0 で始まるコード生成
多項式で計算されたエラー値は、α120 で始まるコード
生成多項式のデータ信号が復号されるときに、この訂正
ファクタと乗算される。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、コード生成多項式 Ｇ（ｘ）＝（ｘ＋α0+b ）（ｘ＋α1+b ）．．．（ｘ＋
α15+b）によってコード化されたＲＳコードデータ信号
を復号する方法であって、ＲＳコードデータ信号のシン
ドローム（Ｓ（ｘ））及び消去位置（Ｌ（ｘ））が決定
され、この決定されたシンドローム（Ｓ（ｘ））及び消
去位置（Ｌ（ｘ））からユークリッドアルゴリズムを用
いてエラー位置多項式Ｔｓ（ｘ）及びエラー値多項式Ｒ
ｓ（ｘ）が導かれ、エラー位置Ｘk 及びエラー値ｙk が
式
【数３】 （ここで、Ｔ′（Ｘk ）はエラー位置Ｘk における１次
微分）によって定義されるチェン・ゼロ検索によって決
定され、ＲＳコードデータ信号のデータワードが、前記
決定されたエラー位置Ｘk 及びエラー値Ｙk に基づいて
訂正されるリード・ソロモン（ＲＳ）コードデータ信号
を復号化する方法及び回路に関するものである。
【０００２】
【従来の技術】ＲＳコードは、長さｎのシステマティッ
ク・フロック・コードであり、ここではｋ個の情報記号
が（ｎ−ｋ）＝ｐ個のチェックワードに加算される。情
報記号はコード化処理によっては変化しない。ＲＳコー
ドはｄ＝ｐ＋１の最小ハミング距離を有し、この最小ハ
ミング距離はエラー認識あるいはエラー訂正の復号化動
作に任意に使用することができる。
【０００３】復号化動作においては、データワードとチ
ェックワードとの間の区別がない。ＲＳコードブロック
はｎ個の記号を具え、記号は１ビットと同じかこれより
大きい幅を有する。通常８ビットの記号幅が使用され
る。エラー位置Ｘi 及びエラー値Ｙi を計算するために
は、記号の各エラ−ｔに対する訂正に２ｔのチェックワ
ードが必要である。誤った記号が消去としてマークされ
ると、エラー位置Ｘｉがわかる。この場合、エラー値を
計算するために単一のチェックワードが必要とされる。
ＲＳコード用には、２ｔ＋ｅ≦ｐ＝ｎ−ｋ＝ｄ−１の関
係式が適用される。ここで、ｅは消去ワード句の数を示
す。磁気テープへ及び／又は磁気テープからのデータ信
号の記録及び再生に関連して、消去とは再生されたデー
タ信号にドロップアウト妨害を含むものと、あるいはデ
ータ伝送チャネルのドロップアウト及び関連するデータ
信号のドロップアウトを含むものと解される。ＲＳコー
ドの詳細は、“IBM Journal RES Develop”誌の“On-th
e-fly decoder for multiplebyte errors”（vol.30,N
o.3,May 1986,pp.259-269）に記載されている。
【０００４】主として、距離ｄのＲＳコードは、コード
生成多項式
【数４】 によって決定される。Ｇ（ｘ）は必ずｐ個の連続したゼ
ロを有する。
【０００５】多くのＲＳコードにおいては、ｂは０にセ
ットされるが、これに代えて、ｂは２mより小さい任意
の定数であってもよい。例えば、Ｄ１標準（カセット内
の磁気テープのデジタルテレビジョン信号を記録するた
めの標準；ヨーロッパ放送協会；Tech 3252-E）におい
ては、ｂ＝０で始まるコード生成多項式は、Ｇ（ｘ）＝
（ｘ＋α0 ）（ｘ＋α1 ）．．．（ｘ＋α15）によって
決められてており、ＩＳＯ標準においては、ｂ＝１２０
で始まるコード生成多項式は、Ｇ（ｘ）＝（ｘ＋
α120 ）（ｘ＋α121 ）．．．（ｘ＋α135 ）によって
決められている。両方のコード生成多項式は、αの指数
における一定のオフセットによってのみ区別される。
【０００６】ＲＳコードデータの復号化回路は、国際刊
行物である“IEEE 1990 Custom Integrated Circuits C
onference”：“A 40MHz Encoder/Decoder Chip genera
tedby a Reed-Solomon Code Compiler”（pp.13.5.1-1
3.5-4,CH 2860-5/90/0000-0065 ）から知られている。
この回路においては、伝送チャネルの受信データワード
シンドロームが、第１段において計算される。次いで、
第２段では、これらのシンドロームのエラー位置及びエ
ラー値の多項式が、ユークリッドアルゴリズムに従って
計算される。これらの多項式は第３段において、チェン
（Ｃｈｉｅｎ）のゼロ検索にかけられる。このようにし
て決定されたエラー位置及びエラー値を用いて、第４段
において存在するデータの実際の訂正が排他的ＯＲゲー
トを用いて行われる。この既知の回路は、コード生成多
項式Ｇ（ｘ）＝（ｘ＋α0 ）（ｘ＋α1 ）．．．（ｘ＋
α15）によって生じるデータ信号のみを復号化すること
ができる。
【０００７】
【発明が解決しようとする課題】本発明の目的は、冒頭
に述べた種類のＲＳコードデータ信号を復号化する方法
および回路であって、高速のデータ速度で（＞100 Mbit
/s）存在し、 Ｇ（ｘ）＝（ｘ＋α0 ）（ｘ＋α1 ）．．．（ｘ＋α15）あるいは Ｇ（ｘ）＝（ｘ＋α120 ）（ｘ＋α121 ）．．．（ｘ＋α135 ） のコード生成多項式に従ってコード化できるデータ信号
を、リアルタイムに復号化できる方法及び回路を提供し
ようとするものである。
【０００８】
【課題を解決するための手段】この課題は、上述のＲＳ
コードデータ信号を復号化する方法において、コード生
成多項式Ｇ（ｘ）＝（ｘ＋α0+b ）（ｘ＋
α1+b ）．．．（ｘ＋α15+b）に基づいてエラー位置Ｘ
k 及びエラー値Ｙk のシンドローム（Ｓ（ｘ））が決定
され、コード生成多項式 Ｇ（ｘ）＝（ｘ＋α0 ）（ｘ＋α1 ）．．．（ｘ＋α15） によるＲＳコードデータ信号を復号化する時に、この決
定されたエラー値がＹkがエラー訂正に直接使用され、
ＲＳコードデータ信号のエラー訂正行われる前に、ゼロ
に等しくないｂを有するコード生成多項式のＲＳコード
データ信号を復号するときに、ファクタＸk bがコード
生成多項式Ｇ（ｘ）＝（ｘ＋α0 ）（ｘ＋α1 ）．．．
（ｘ＋α15）に対して決定されたエラー値Ｙk に与えら
れることによって解決できる。また、このＲＳコードデ
ータ信号を復号化する方法を実行する回路であって、順
次のデータブロックのシンドローム（Ｓ（ｘ））を形成
し、ＲＳコードデータ信号中の消去位置（Ｌ（ｘ））を
決定するデバイス（３）と、 Ｔs （ｘ）＝（Ｑs-1 （ｘ）＋Ｔs-2 （ｘ）） Ｒs （ｘ）＝（Ｑs-1 （ｘ））Ｒs-1 （ｘ）＋Ｒs-2 （ｘ）及び Ｑs-1 （ｘ）＝Ｒs-2 （ｘ）／Ｒs-1 （ｘ） （ここで、Ｔs （ｘ）はエラー位置多項式、Ｒs （ｘ）
はエラー値多項式、及びＱs-1 （ｘ）は中間値多項式）
であるユークリッドアルゴリズムを用いるデバイス
（５）と、
【数５】 （ここで、Ｔ′（Ｘk ）は位置Ｘk における一次微分）
の関係式によって定義されるチェン・ゼロ検索を用いて
エラー位置Ｘk 及びエラー値Ｙk とを決定するデバイス
（６）と、この決定されたエラー位置Ｘk 及びエラー値
Ｙk に基づいてＲＳコードデータブロック中のデータワ
ードを訂正するデバイス（７）とを具えるＲＳコードデ
ータ信号を復号化する回路において、 シンドローム
（Ｓ（ｘ））を決定するデバイス（３）中に配置された
シンドローム発生器（１１）がＲＳコードデータ信号の
入力データワードが並列ビットで印加される第１の排他
的ＯＲステージ（１４）と、前記第１の排他的ＯＲステ
ージ（１４）から供給されるデータワードを記憶するレ
ジスタ（１３）と、前記レジスタ（１３）の出力に生じ
るデータワードに定数αi （ここでｉは０−１５の間で
制御可能な変数）を乗算する第１の乗算器（１５）と、
前記レジスタ（１３）の出力に存在するデータワードに
定数αi+120 を乗算する第２の乗算器（１６）と、α0
で始まるコード生成多項式によるＲＳコードデータ信号
が復号されるときは、前記第１の乗算器（１５）の出力
から前記第１の排他的ＯＲステージ（１４）の他の入力
へデータを通過させ、α120 で始まるコード生成多項式
によるＲＳコードデータ信号を復号するべきときには、
前記第２の乗算器（１６）の出力から前記第１の排他的
ＯＲステージ（１４）の他の入力へデータを通過させる
第１のマルチプレクサ（１７）を具え、エラー位置Ｘk
とエラー値Ｙk とを決定するデバイス（６）が、データ
ブロックに存在するデータワードをアップ計数し、計数
値（ｘ）をチェン・ゼロ検索に供給するアップカウンタ
（４０）と、前記アップカウンタ（４０）から供給され
る計数値（ｘ）が書き込まれる第１のスタックメモリ
（４４）と、前記第１のスタックメモリ（４４）からの
読み取ったデータを各データブロックの最後に書き込む
ことができる第２のスタックメモリ（５６）と、計数値
（ｘk ）が前記第１のスタックメモリ（４４）に書き込
まれると同時にエラー値（Ｙk ）を書き込むことができ
る第３のスタックメモリ（４５）と、前記第３のスタッ
クメモリ（４５）から読み取ったデータをデータブロッ
クの最後に書き込むことができる第４のスタックメモリ
（６０）と、前記アップカウンタ（４０）と並列に動作
し、アップカウンタ（４０）に対してα-120のオフセッ
トを有する反転カウンタ（４６）とを具え、データワー
ドを訂正するデバイス（７）が、データブロック長の値
で始まってダウン計数するダウンカウンタ（５２）と、
前記第２のスタックメモリ（５６）の上側位置に存在す
る計数値と、前記ダウンカウンタ（５２）から供給され
る計数値とを比較して、与えられた値が同じであるとき
に制御信号（Found ）を導き出す回路（５７）と、一の
入力が前記比較回路（５７）の出力に接続されているＡ
ＮＤゲート（５８）と、前記反転カウンタ（４６）で制
御され、１２０のオフセットを有する第２のアップカウ
ンタ（６２）と、前記第４のスタックメモリ（６０）の
上側位置に存在するエラー値（Ｘk ）と前記第２のアッ
プカウンタ（６２）から供給される計数値とを乗算する
第３の乗算器（６１）と、α0 で始まるコード生成多項
式によるＲＳコードデータ信号が復号されるときに、前
記第４のスタックメモリ（６０）の上側位置に存在する
エラー値（Ｙk）を前記ＡＮＤゲート（５８）の他の入
力へ通過させる第２のマルチプレクサであって、α120
で始まるコード生成多項式によるＲＳコードデータ信号
を復号するべきときには、前記第２のマルチプレクサの
（５９）の出力に生じる値（Ｙk）を前記ＡＮＤゲート
（５８）の前記他の入力へ通過させる第２のマルチプレ
クサ（５９）と、第１の入力で前記ＡＮＤゲート（５
８）の出力から生じ得る信号を受け、第２の入力でＲＳ
コードデータ信号のビット並列信号遅延適合データワー
ドを受け、出力からはエラー訂正データワードを生じ得
る第２の排他的ＯＲステージ（６６）とを具えることを
特徴とするＲＳコードデータ信号を復号化する回路によ
って解決することができる。
【０００９】本発明にかかる方法に応じて製造される回
路は、単一の回路配置によって、２つの別個のコード生
成多項式によってコード化されるＲＳコードデータ信号
を任意に復号化できるものであり、これらの信号を複合
化することによって追加される構成要素の数は変わらな
いという利点がある。
【００１０】他の実施例は、前記アップカウンタ（４
０）が、第２のレジスタ（４２）の先段に第３のマルチ
プレクサステージ（４１）を具え、第３のマルチプレク
サの一の入力で、ブロックの開始時点において、値α0
＝１を受け、残りの期間中は、マルチプレクサステージ
（４１）の他の入力端子で、前記レジスタ（４２）から
供給される出力値の、値αi を乗じた値を伝えることを
特徴とするものである。又、前記ダウンカウンタ（５
２）が、レジスタ（５４）に先段に第４のマルチプレク
サステージ（５３）を具え、第４のマルチプレクサステ
ージ（５３）の入力で、ブロックの開始時点で、ブロッ
ク長の値を受け、残りの期間中は、第４のマルチプレク
サステージ（５３）の他の入力で前記レジスタ（５４）
から供給される出力値を伝えることを特徴とするもので
ある。更に、前記反転カウンタ（４６）が、レジスタ
（４８）に先段に第５のマルチプレクサステージ（４
７）を具え、このレジスタがブロックの開始時点におい
て、第５のマルチプレクサステージ（４７）を介して値
α＝−１２０を受け、残りの期間中は、レジスタ（４
８）の出力に存在する値に、乗算ステージ（４９）にお
いてα120 を乗算した値を受けることを特徴とするもの
である。更に、他のアップカウンタ（６２）が第５のレ
ジスタ（６３）に先段に第４のマルチプレクサステージ
（６４）を具え、レジスタ（６３）はブロックの開始時
点において、第４のマルチプレクサステージ（６４）を
介して第４のレジスタ（４８）の出力に存在する値を受
け、残りの期間中は、第５のレジスタ（６３）の出力に
存在する値に、第４の乗算ステージ（６５）においてα
120 を乗算した値を受けることを特徴とするものであ
る。更に、各乗算ステージが、ファクタαi+b （ここで
ｉ＝０〜１５，ｂ＝１２０もしくは０）を乗算する、排
他的ＯＲゲートとして形成されていることを特徴とする
ものである。
【００１１】
【実施例】本発明を、以下に述べる実施例に基づいてよ
り詳細に説明する。
【００１２】定義によれば、各ｍビットの記号はＲＳコ
ードのガロア（Galois）フィールドＧＦ（２m ）の要素
である。有限フィールド演算（finite field arithmeti
cs）の基礎とする２m 個の記号のシーケンスは、フィー
ルドコード生成多項式ｐ（ｘ）によって決定される。フ
ィールドの要素は、ブロック中において、明確な位置数
として要求されるので、この記号の幅は、２m-1 のＲＳ
コードの最大ブロック長を制限する。ゼロは、加算の中
性要素であり、式α0 ＝１は、乗算の中性要素である。
したがって、フィールドは既約フィールドコード生成多
項式を介して決定される。数ｍの基本要素αが決定され
れば、全シーケンス要素はべきαとして表現することが
できる。αはｐ（ｘ）の根であり、更に、ゼロと等しく
ないｍ個の根が存在するため、すべての他の要素に対し
てｐ（ｘ）＝０が満足される。従って、ガロア・フィー
ルドは２m-1 個の要素をもつ有限シーケンスとして定義
することができる。２進成分で表示によってビット的な
排他的ＯＲゲートを介して簡単な加算を行うことができ
るものであり、指数表示によって、指数モジュールｑ＝
２m-1の加算を介して簡単な乗算を行うことができる。
回路変換すると、このことは、桁上げ出力が桁上げ入力
に接続されている２進加算器に対応する。
【００１３】すでに上述した通り、ＲＳコードは一般的
に、コード生成多項式
【数６】 によって決定される。
【００１４】リーガルコードベクトルｃ（ｘ）は、ｐ個
の位置にわたってシフトした情報ベクトルｉ（ｘ）・ｘ
p をＧ（ｘ）で除して、更に、情報ベクトルｉ（ｘ）の
明確な位置での結果のパリティベクトルｐ（ｘ）を加え
ることによって生じる。この結果のコードベクトルｃ
（ｘ）は剰余を残す事なくＧ（ｘ）のすべての根で割り
切れる。単一の多項式及びベクトルは以下のように表わ
される。
【数７】
【００１５】エラーベクトルｅi は、ｔ個の位置の最大
の位置において、ゼロに等しくならない。その他の位置
ではゼロに等しい。これはまた、ｅ個の位置の最大位置
においてゼロに等しくならない消去ベクトルｕi にもい
える。ｅi およびｕi が等しい位置で交差する場合、エ
ラーが消去となる。
【００１６】伝送されたＲＳコード化されたコードブロ
ックｃ（ｘ）は、ｋ個の情報位置を具え、ｐ個のチェッ
クワードがこれを追従する。このコード構成は、エラー
ｅ（ｘ）若しくは消去ｕ（ｘ）が生じない限り、ｃ
（ｘ）が剰余を残す事なくＧ（ｘ）のすべての根で割り
切れる旨を保証するものである。コード生成多項式Ｇ
（ｘ）の根における受信ベクトルｒ（ｘ）の展開は、受
信エラーには依存するが、伝送情報ｉ（ｘ）には依存し
ない値を生じる。これらの値は、シンドロームとして示
されている。ｍ個のシンドロームＳj （ｊ＝０．．．ｄ
−２）は、式
【数８】 に基づいて計算される。
【００１７】受信ベクトル（ｘ）は、多項式を用いて、
以下のように記載することができる。
【数９】
【００１８】この関係式で、ｘは各受信記号ｒi に対す
る多項式内の位置を示すものである。第１の受信（デー
タ）記号はｒn-1 であり、最後の受信記号は（パリテ
ィ）記号ｒ0 である。この多項式を記憶するために、係
数ｒi のみをファイルしなくてはならない。
【００１９】コード生成多項式のゼロの際に、エラーの
ない受信ベクトルｒ（ｘ）を展開すると、その値はゼロ
になるので、シンドロームの値は位置Ｘk において位置
重み付けされたエラ−Ｙk の和とみなすことができる。
このシンドロームはデータストリームｒ（ｘ）を、コー
ド生成多項式のすべてのファクタ（ｘ＋αi ）による除
算した剰余を表している。ここで、
【数１０】 である。
【００２０】Ｘk が生じる位置が、消去位置にあれば、
ｐ個のシンドローム及びｐ個のエラー位置の使用して、
２ｔ＋ｅ≦ｐ（ｔはマークされていないエラーの数）で
あるかぎり、Ｘk を計算してｅ＝ｐ個の消去を得ること
ができる。
【００２１】前述した式によれば、シンドロームは非線
形方程式の記録を構成しており、従って、ｐ個の解を見
いだすことができる。方程式の解は、エラー位置におい
てゼロの値を有するエラー位置多項式の定数である。
【００２２】ユークリッドアルゴリズムによるＲＳコー
ドデータブロックの復号化については、“IEEE Proceed
ings":“Simplified procedure for correcting both e
rrors and erasures of RS code using Euclid's algor
ithm,vol.135,Pt.E,No.6,November 1988 by Truong Eas
tman Reed HSU”に記載されている。ユークリッドアル
ゴリズムは以下のステップに細分化することができる。 １．シンドロームＳj 及び消去位置Ｌ（ｘ）の多項式の
計算及び、ｅ＝ｄｅｇ｛Ｌ（ｘ）｝のセット ２．フォーニィ（Forney）シンドロームの計算 τ（ｘ）＝Ｓ（ｘ）Ｌ（ｘ）ｍｏｄ ｘd-1 ３．ｅ＝ｄ−１＝ｐの場合、Ｔ（ｘ）はＬ（ｘ）にセッ
トされ、Ｒ（ｘ）はτ（ｘ）にセットされる。そうでな
ければ、Ｔ（ｘ）とＲ（ｘ）はユークリッドアルゴリズ
ムを用いて決定される。ユークリッドアルゴリズムは、
以下の帰納的な式を具える。 初期値
【数１１】 をもつ、
【数１２】 ここで、Ｔs （ｘ）はエラー位置多項式であり、Ｒ
s （ｘ）はエラー値多項式、Ｑs-1 （ｘ）は中間値多項
式である。次いで、Ｒs （ｘ）とＴs （ｘ）は、最も低
い係数Ｔs （０）＝δを用いて正規化することができ
る。ここでＲ（ｘ）＝Ｒs （ｘ）／δ，Ｔ（ｘ）＝Ｔs
（ｘ）／δである。Ｒ（ｘ）及びＴ（ｘ）は、度数Ｒs
≦〔外１〕
【外１】 のときの、ユークリッドアルゴリズムの結果であり、こ
こで〔外２〕
【外２】 の記号は整数部分を示す。
【００２３】Ｔ（ｘ）の根は、エラー及び消去Ｘk -1の
反転（ダウンーカウント）位置にある。本発明の実施例
では、単一のエラー位置Ｘk -1は、チェンゼロ検索によ
って見いだされる。同時にエラー値Ｙk は、このプロセ
ス中の関係式
【数１３】 よって決定される。ここで、Ｔ′（Ｘk ）は、位置Ｘk
におけるＴの第１微分である。有限フイールドにおいて
は、多項式の微分が行われ、偶数ｎに対するｎ倍の加算
が結果としてゼロになり、奇数ｎに対してはその要素自
体になる。この手段によって、検索されたエラー位置及
び対応するエラー値が決定される。
【００２４】図中、同じ構成要素については同じ参照符
号を付すものとする。図１はＲＳ復号器のブロック図で
ある。このブロック図中、符号１はデータバスを示し、
これを介してＲＳコード化されたデータ信号の８ビット
幅のデータワードＤinが遅延デバイス２に送られ、信号
遅延時間を保証する。また、このデータワードはシンド
ロームＳ（ｘ）と消去位置Ｌ（ｘ）を決定するために必
らず使用される関数ブロック３に送られる。ＲＳコ−ド
化されたデータ信号と並列に、１ビットワイドのエラー
信号ＥＦinが、遅延デバイス２において遅延される。こ
の信号はドロップアウト検出器（図示せず）から、ある
いは、前段のエラー認識ステージから、供給される。エ
ラー信号ＥＦinも関数ブロック３に供給される。関数ブ
ロック３に関する詳細は図２を参照して述べる。
【００２５】関数ブロック３において導出されるシンド
ロームＳ（ｘ）及び消去位置Ｌ（ｘ）は、ユークリッド
アルゴリズムを行って、エラー位置多項式Ｔ（ｘ）及び
エラー値多項式Ｒ（ｘ）を発生する関数ブロック５へパ
スされる。関数ブロック５に関する詳細は図３を参照し
て述べる。
【００２６】次段の関数ブロック６及び７については、
図４及び図５を参照して詳細を説明するが、これらの関
数ブロックにおいては、多項式Ｔs （ｘ）及びＲ
s （ｘ）のゼロが決定され、得られたエラー値Ｙk 及び
エラー位置Ｘk を用いてエラーデータワードの訂正が行
われる。これらのデータワードはエラー信号と共に、遅
延デバイス２の出力から関数ブロック７へ送られる。４
つの関数ブロック３〜７及び遅延デバイス２は、制御デ
バイス８によって制御される。８ビットワイドのデータ
ワードを有するデータストリームは、関数ブロック７の
出力においてデータバス９から取り出すことができる。
エラーデータワードは、可能な限り復号回路で補正され
る。復号回路で補正できないこれらのデータブロックは
エラー信号ＥＦ out に伴う。このエラー信号は、データ
バス９を介して供給されるデータに並列に、ライン１０
を介して伝送される。
【００２７】図２は関数ブロック３のブロック図であ
る。データ信号ＤinのシンドロームＳ 00からＳ15が、１
６個のシンドローム生成器１１によって計算される。１
６のシンドローム生成器１１のうちのひとつを、破線で
囲んだブロック１２の中に詳細に示す。シンドローム生
成器は、必ずフィードバックレジスタ１３を具える。こ
のフィードバックレジスタは排他的ＯＲゲート１４を介
してデータ信号Ｄinによって制御される。レジスタ１３
のフィードバック枝路は２台の乗算器１６と１５を有し
ており、これらの乗算器の入力端子はレジスタ１３の出
力に接続されている。乗算器１５はαi の乗算に使用さ
れ、乗算器１６はα120+i の乗算に使用される。
【００２８】２台の乗算器１５、１６は既知の方法で排
他的ＯＲゲートを設けることができる（ＥＰ特許明細書
0 147 041 B1）。この場合は、８ビットワ幅のデータワ
ードが、式αi の指数ｉに従って、所定の方法排他的Ｏ
Ｒが合成される。例えば、α i では８本のラインを介し
て伝送される並列の８ビットのデータワードが、以下の
ように排他的ＯＲが合成されて
【数１４】 となる。
【００２９】図６乃至図９に、乗算器１５の排他的ＯＲ
ゲートを、α0 、α1 、・・・α15に対して示してお
り、図１０乃至図１３に乗算器１６の排他的ＯＲゲート
が、α 120 、α121 、・・・α135 に対して示してい
る。
【００３０】乗算器１５及び１６の出力に生じる結果
は、マルチプレクサ１７によって任意に取り出すことが
でき、ＡＮＤゲート１８を介して排他的ＯＲゲート１４
の入力端子に接続することができる。コード生成多項式
Ｇ（ｘ）＝（ｘ＋α120 ）（ｘ＋α121 ）・・・（ｘ＋
α135 ）を復号化する場合、制御信号ＩＳＯで制御され
たマルチプレクサ１７は乗算器１６で生じた結果を排他
的ＯＲゲート１４へ通過させる。一方、コード生成多項
式Ｇ（ｘ）＝（ｘ＋α0 ）（ｘ＋α1 ）・・・（ｘ＋α
15）を復号化する場合、乗算器１５の出力に生じる演算
結果をマルチプレクサ１７によって排他的ＯＲゲート１
４へ通過させる。
【００３１】シンドローム生成器Ｓi （ｉ＝０から１
５）は除算ｃ（ｘ）／（ｘ＋αi ）の剰余で構成する。
このシンドローム生成器はＡＮＤゲートを介してフィー
ドバックさせることによって、ブロックの開始時に始動
する。クロックが与えられると、最後のブロックのシン
ドロームＳ（ｘ）が関数ブロック５を通過し、この関数
ブロックでは上述のユークリッドアルゴリズムに従って
消去が決定される。さらに、消去位置Ｌ（ｘ）が関数ブ
ロック３にて決定される。この目的のために、生成器は
データブロック中の全ての位置にわたって計数する。こ
の生成器は、Ｄレジスタ１９を具えており、このレジス
タは乗算器２０及び２１を介してフィードバックがかけ
られている。消去が生じた時には、その位置がフリーレ
ジスタ２２内に記憶される。このレジスタは消去位置Ｌ
００からＬ１５を生じる。これらのレジスタはまた、ブ
ロックの開始時点においては、ゼロにセットされてい
る。訂正制限によって前もって決められているよりもよ
り多くの消去が生じた場合は、Ｌ（ｘ）はゼロにセット
される。この場合、制限されたエラー訂正は、後に訂正
が試みられる。
【００３２】図１に符号５で示される関数ブロックの詳
細を図３にブロック図で示す。このブロックは、２つの
１６ビット幅のレジスタ２３、２４を具える。レジスタ
２３はシンドローム発生器１１で発生したシンドローム
Ｓ００からＳ１５を受け取る。レジスタ２２から供給さ
れる消去位置Ｌ００−Ｌ１５は、レジスタ２４の入力端
子に現れる。さらに、このブロックは２つの１７ビット
幅のレジスタ２５、２６を具え、これらのレジスタは一
定の初期値０及び１でそれぞれロードされる。前記に定
義したユークリッドアルゴリズムに従ってエラー位置多
項式Ｔｓ（ｘ）及びエラー値多項式Ｒs （ｘ）を計算す
るために、レジスタ２３、２４及び２５、２６の内容を
交互に変換することができる。レジスタ２３〜２６はＲ
０の度数を介して制御手段２７によって制御される。主
に“IEEE 1990 Custom Integrated Circuits Conferenc
e,pp.13.5.1-13.5.4”から知られている、既知のエラー
位置多項式Ｔs （ｘ）及びエラー値多項式Ｒs （Ｘ）の
算出の最終段階で、Ｔの度数を示す信号ｄｅｇ（Ｔ）を
取り出し、従って、この信号は次のチェン検索において
データブロック中にいくつのエラーがあるかを示すもの
である。
【００３３】図１に示す関数ブロック６の詳細を図４に
示す。関連する実施例においては、関数ブロック５から
与えられる多項式がサイクリックデコーダ２８の３３個
のユニットに与えられる。サイクリックデコーダ２８の
詳細を、破線で囲んだブロック２９内に示す。次いで、
現在の多項式信号がブロックの開始時点においてマルチ
プレクサ３０を介してレジスタ３１に導入される。各要
素Ｒi 及びＴi が連続的にかつ巡回的にブロック３２内
で使用可能になる符号α-iに乗算される。この方法でゼ
ロＴ（ｘ）すなわちＴi ＝０の和が発見された場合、ｂ
＝０であれば、エラー値はＹk ＝Ｒ（Ｘk ）／Ｔ′（Ｘ
k ）によって計算することができる。
【００３４】ガロアフィールドの計算ルールに従って微
分し得るＴ′（ｘ）は、偶数の係数Ｔの多項式を生じ
る。このようなサイクリック復号器は、上述の“IBM jo
urnalRES Develop, vol.30,No.3,May 1986,pp259-269”
から既知である。
【００３５】それぞれのサイクリック復号器から供給さ
れる信号は、加算ステージ３３、３４、３５にて加算さ
れる。加算ステージ３３、３４、３５の出力として出て
くる和（Ｖａｌ）、偶数和（Ｅｖｅｎ Ｓｕｍ）、奇数
和（Ｏｄｄ Ｓｕｍ）が、同じレベルの全ビットの排他
的ＯＲ関数をとることによって形成される。この場合
は、例えば、和（Ｖａｌ）の０ビットは、Ｒ０・・・Ｒ
１５のビット０を排他的ＯＲにかけることによって形成
される。除算Ｒ（Ｘk ）／Ｔ′（Ｘk ）は逆の値を乗算
することによって算出される。この計算はガロアフィー
ルドの反転ステージ３６及びガロアフィールドの乗算ス
テージ３６において有効である。次いで、和（Ｖａｌ）
はＲ（ｘk ）に対応し、偶数和（Ｅｖｅｎ Ｓｕｍ）は
Ｔ′（ｘk）に対応する。乗算を基礎にした除算は、ガ
ロアフィールドの乗算ステージ３７の出力に所望のエラ
ー値Ｙk を生じさせる。
【００３６】偶数和及び奇数和が、加算ステージ３８に
て合成され、それをステージ３９においてゼロにする。
ステージ３９の出力信号“Found”がハイレベルであれ
ば、マルチプレクサ４１、レジスタ４２、乗算器４３を
具える位置カウンタ４０の値が、エラー値Ｙk と同時
に、見いだされたエラー位置Ｘk の値としてスタックメ
モリ４４のスタックに記憶される。スタックメモリはレ
ジスタ０〜ＸＶＩから構成されるとする。スタックメモ
リ４４のスタックへの記憶は、レジスタ０において行わ
れる。一方、レジスタ０〜ＸＶＩにこれまでに見いださ
れる値はレジスタＩ〜ＸＶで一位置だけ前進する。従っ
て、レジスタＸＶの内容は失われる。スタックはＬＩＦ
Ｏ（Last In/First Out）の関数を満足する。なぜなら
ば、チェンによる検索アルゴリズムは、バックワードシ
ーケンスにおいて逆エラー位置を算出するからである。
エラー値Ｙi を格納するスタックメモリ４５は、スタッ
クメモリ４４と並列に動作する。
【００３７】エラー位置Ｘk 及びエラー値Ｙk を決定す
る回路６は、更に、反転カウンタ４６を具え、この反転
カウンタはマルチプレクサ４７、レジスタ４８及び乗算
器４９を具えている。しかしながら、位置カウンタ４０
とは逆に、フィードバック回路内に配置されたレジスタ
４８は、データブロックの開始時点において値α-120で
ロードされる。レジスタ４８の出力に現れるデータワー
ド（offset）は乗算器４９において連続的にα-120が乗
算される。
【００３８】図４のブロック図は、カウンタ５０も具え
ており、このカウンタ５０は、信号ｄｅｇ（Ｔ）の値で
ロードし、ステージ３９から供給される信号“Found”
を印加することによってリセットされる。このカウンタ
が、データブロック全体を通して実行の終了時に値０を
残していた場合、これは、期待エラー数に関する表示を
与える多項式Ｔ（度数＝１＋０に等しくない最も高い係
数の指数）の度数が、データブロック中に実際に見いだ
されたゼロの数に対応し、結果的に復号動作が順次行わ
れることを保証するものである。逆の場合は、訂正でき
ないエラーが存在することになる。
【００３９】データブロックのｎクロック後に、ネステ
ィングメモリ４４、４５に集められたエラー位置Ｘk 及
びエラー値Ｙk が、回路７に並列に伝送されて、回路６
を始動することができると共に、順次、チェン検索が可
能となる。
【００４０】図５は、遅延デバイス２の出力に供給され
て、デ−タバス５１に印加された遅延時間に適合するデ
ータ信号を訂正する回路７のブロック図である。
【００４１】このブロック図において、値Ｘk 及びＹk
のシーケンスが、反転位置カウンタ５２によって反転す
る。この反転位置カウンタ５２は、マルチプレクサ５
３、レジスタ５４、ステージ５５を具える。この回路
は、ブロックの開始時点においては、レジスタ５４がマ
ルチプレクサ５３を介してブロック長の最終値“BlkLe
n”でロードされた状態が示されている。レジスタ５４
の出力値は、残りの期間中に、ステージ５５を介して記
号α-1の値と共にフィードバックされ、これらの値が乗
算される。エラー位置Ｘk は、反転位置カウンタ５２か
ら供給されるデータが、レジスタ０の内容及びエラー位
置Ｘk を有するスタックメモリ５６の内容と同じになっ
たときに、見いだされる。この比較は、対応する出力信
号“Found”を出力する比較ステージ５７において行わ
れる。この出力信号“Found”は、ＡＮＤゲート５８の
ゲートパルス信号となる。ＡＮＤゲート５８の他の入力
端子は、マルチプレクサ５９を介してスタックメモリ６
０の出力端子に接続されており、このスタックメモリ６
０にはスタックメモリ４５のエラー値Ｙk が、ｂ＝０の
時に伝送される。従って、コード生成多項式Ｇ（ｘ）＝
（ｘ＋α0 ）（ｘ＋α1 ）・・・（ｘ＋α15）の信号が
復号される。
【００４２】一方で、コード生成多項式Ｇ（ｘ）＝（ｘ
＋α120 ）（ｘ＋α121 ）・・・（ｘ＋α135 ）のデー
タ信号が、復号される（ｂ＝１２０）場合は、ＡＮＤゲ
ート５８の他方の入力端子はマルチプレクサ５９を介し
て乗算器６１に接続される。この乗算器６１の入力端子
はスタックメモリ６０の出力端子に接続されていると共
に、他のアップカウンタ６２の出力端子にも接続されて
いる。上述したカウンタと同様に、カウンタ６２もフィ
ードバックレジスタ６３を有しており、ここには、反転
カウンタ４６によって生成される信号（offset）がマル
チプレクサ６４を介して入力される。レジスタ６３のフ
ィードバック枝路に配置された乗算器６５は、レジスタ
６３の出力値に、値α120 から乗算する。従って、ここ
で見いだされるファクタｘk -bは、スタックメモリ６０
に記憶されているエラー値Ｙk を訂正するのに使用され
る。コード生成多項式Ｇ（ｘ）＝（ｘ＋α120 ）（ｘ＋
α 121 ）・・・（ｘ＋α135 ）に適合された訂正された
エラー値Ｙk は、従って、乗算器６１の出力端子に現れ
る。この値は
【数１５】 に従って導出される。
【００４３】比較ステージ５７の出力端子に出力される
信号“Found”は、２つのスタックメモリ５６及び６０
の制御にも使用される。信号“Found”論理的に高いレ
ベルを有する場合は、上側値はスタックメモリ５６から
除去される。このことは、スタックメモリ５６と６０内
のレジスタＩ−ＸＶがレジスタ位置０からＸＩＶにおい
てコピーされること、及び、レジスタＸＶは論理値０に
なることを意味する。全部のエラーが訂正されたとき
に、論理的ゼロがスタックにあらわれる。この場合、反
転位置カウンタ５２とこれ以上の一致が生じ得ない。
【００４４】ＡＮＤゲート５８の出力に現れるエラー値
Ｙk は論理的には、排他的ＯＲステージ６６において、
遅延デバイス２で遅延されたデータ値Ｄinと合成され、
実際のエラー訂正が行われている。エラー訂正が行われ
たデータ信号Ｄout は出力９に供給される。遅延デバイ
ス２にて遅延されているエラー信号ＥＦinは、ステージ
６７を介して出力バス２０に、印加される。このステー
ジはＲＳ復号器の制御デバイス８に依存する
【００４５】２つのコード生成多項式に体するＲＳコー
ドデータ信号は、本質的には、関連する回路における２
つのステージにおいて復号される。第１のステージで
は、コード生成多項式 Ｇ（ｘ）＝（ｘ＋α0 ）（ｘ＋α1 ）・・・（ｘ＋α15） によるデータ信号に対するエラー値Ｙkが決定され、決
定されたエラー値によってエラー訂正が行われる。コー
ド生成多項式Ｇ（ｘ）＝（ｘ＋α120 ）（ｘ＋α 121 ）
・・・（ｘ＋α135 ）によるデータ信号が復号される場
合は、Ｙk は、第２ステージで並列に導出されるファク
タｘk -bによって訂正されるだけである。この２つのス
テージにおける信号処理モードは、８ビット幅のデータ
ワードに対して約２０ＭＨｚ（１６０ｍｂｉｔ／ｓ）の
動作継続速度が得られる利点がある。データブロックか
らデータブロックへ復号する間、一つのコード生成多項
式から他のコード生成多項式へ切り換えることが可能で
ある。更なる利点は、本発明にかかる回路は、エラー値
Ｙk を計算するための複雑な副回路が不要であるという
点である。関連する回路は、特に、磁気テープで再生さ
れたＲＳコードデータ信号のエラーを認識して訂正する
のに適するものである。本発明にかかる回路の特別な構
成に基づいて、再生したデータ信号中の消去も、例え
ば、マークされていないエラーのトライアルに対しては
無視できる。さらに、後続のデバイスにおける大きなか
つ訂正不可能なビームエラーをマスクするので、信頼で
きるエラー認識のために、本発明の回路に固有のエラー
訂正可能性を減少させるようにしても良い。
【図面の詳細な説明】
【図１】 ＲＳ復号器のブロック図である。
【図２】 ＲＳデータ信号におけるシンドローム形成用
及び消去位置決定用の回路のブロック図である。
【図３】 ユークリッドアルゴリズムに基づいたエラー
位置及びエラー値多項式の計算用の回路のブロック図で
ある。
【図４】 チエン・ゼロ検索によるエラー位置及びエラ
ー値決定用回路のブロック図である。
【図５】 ＲＳコード化されたデータ信号の訂正用の回
路のブロック図である。
【図６】 α0 からα3 の定乗算用の表である。
【図７】 α4 からα7 の定乗算用の表である。
【図８】 α8 からα11の定乗算用の表である。
【図９】 α12からα15の定乗算用の表である。
【図１０】 α120 からα123 の定乗算用の表である。
【図１１】 α124 からα127 の定乗算用の表である。
【図１２】 α128 からα131 の定乗算用の表である。
【図１３】 α132 からα135 の定乗算用の表である。
【符号の説明】 １ データバス ２ 遅延デバイス ３、５、６、７ 関数ブロック ８ 制御デバイス １１ シンドローム生成器 １３ レジスタ １４ 排他的ＯＲステージ １５、１６ 乗算器 １７ マルチプレクサ ４０ アップカウンタ ４１ マルチプレクサステージ ４２ レジスタ ４４、４５ スタックメモリ ４６ 反転カウンタ ４７ マルチプレクサステージ ４８ レジスタ ４９ 乗算ステージ ５２ ダウンカウンタ ５３ マルチプレクサステージ ５４ レジスタ ５７ 比較回路 ５８ ＡＮＤゲート ５６、６０ スタックメモリ ５９ マルチプレクサ、 ６１ 乗算器 ６２ アップカウンタ ６３ レジスタ ６４ マルチプレクサステージ ６６ 排他的ＯＲステージ
─────────────────────────────────────────────────────
【手続補正書】
【提出日】平成５年８月９日
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正内容】
【００４５】２つのコード生成多項式に体するＲＳコー
ドデータ信号は、本質的には、関連する回路における２
つのステージにおいて復号される。第１のステージで
は、コード生成多項式 Ｇ（ｘ）＝（ｘ＋α0 ）（ｘ＋α1 ）・・・（ｘ＋α15） によるデータ信号に対するエラー値Ｙk が決定され、決
定されたエラー値によってエラー訂正が行われる。コー
ド生成多項式Ｇ（ｘ）＝（ｘ＋α120 ）（ｘ＋α 121 ）
・・・（ｘ＋α135 ）によるデータ信号が復号される場
合は、Ｙk は、第２ステージで並列に導出されるファク
タｘk -bによって訂正されるだけである。この２つのス
テージにおける信号処理モードは、８ビット幅のデータ
ワードに対して約２０ＭＨｚ（１６０ｍｂｉｔ／ｓ）の
動作継続速度が得られる利点がある。データブロックか
らデータブロックへ復号する間、一つのコード生成多項
式から他のコード生成多項式へ切り換えることが可能で
ある。更なる利点は、本発明にかかる回路は、エラー値
Ｙk を計算するための複雑な副回路が不要であるという
点である。関連する回路は、特に、磁気テープで再生さ
れたＲＳコードデータ信号のエラーを認識して訂正する
のに適するものである。本発明にかかる回路の特別な構
成に基づいて、再生したデータ信号中の消去も、例え
ば、マークされていないエラーのトライアルに対しては
無視できる。さらに、後続のデバイスにおける大きなか
つ訂正不可能なビームエラーをマスクするので、信頼で
きるエラー認識のために、本発明の回路に固有のエラー
訂正可能性を減少させるようにしても良い。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】図面の簡単な説明
【補正方法】変更
【補正内容】
【図面の簡単な説明】
【図１】 ＲＳ復号器のブロック図である。
【図２】 ＲＳデータ信号におけるシンドローム形成用
及び消去位置決定用の回路のブロック図である。
【図３】 ユークリッドアルゴリズムに基づいたエラー
位置及びエラー値多項式の計算用の回路のブロック図で
ある。
【図４】 チエン・ゼロ検索によるエラー位置及びエラ
ー値決定用回路のブロック図である。
【図５】 ＲＳコード化されたデータ信号の訂正用の回
路のブロック図である。
【図６】 α0 からα3 の定乗算用の図表である。
【図７】 α4 からα7 の定乗算用の図表である。
【図８】 α8 からα11の定乗算用の図表である。
【図９】 α12からα15の定乗算用の図表である。
【図１０】 α120 からα123 の定乗算用の図表であ
る。
【図１１】 α124 からα127 の定乗算用の図表であ
る。
【図１２】 α128 からα131 の定乗算用の図表であ
る。
【図１３】 α132 からα135 の定乗算用の図表であ
る。
【符号の説明】 １ データバス ２ 遅延デバイス ３、５、６、７ 関数ブロック ８ 制御デバイス １１ シンドローム生成器 １３ レジスタ １４ 排他的ＯＲステージ １５、１６ 乗算器 １７ マルチプレクサ ４０ アップカウンタ ４１ マルチプレクサステージ ４２ レジスタ ４４、４５ スタックメモリ ４６ 反転カウンタ ４７ マルチプレクサステージ ４８ レジスタ ４９ 乗算ステージ ５２ ダウンカウンタ ５３ マルチプレクサステージ ５４ レジスタ ５７ 比較回路 ５８ ＡＮＤゲート ５６、６０ スタックメモリ ５９ マルチプレクサ、 ６１ 乗算器 ６２ アップカウンタ ６３ レジスタ ６４ マルチプレクサステージ ６６ 排他的ＯＲステージ

Claims (7)

    【特許請求の範囲】
  1. 【請求項１】 コード生成多項式 Ｇ（ｘ）＝（ｘ＋α0+b ）（ｘ＋α1+b ）．．．（ｘ＋
    α15+b）によってコード化されたＲＳコードデータ信号
    を復号する方法であって、 ＲＳコードデータ信号のシンドローム（Ｓ（ｘ））及び
    消去位置（Ｌ（ｘ））が決定され、この決定されたシン
    ドローム（Ｓ（ｘ））及び消去位置（Ｌ（ｘ））からユ
    ークリッドアルゴリズムを用いてエラー位置多項式Ｔｓ
    （ｘ）及びエラー値多項式Ｒｓ（ｘ）が導かれ、 エラー位置Ｘk 及びエラー値ｙk が式 【数１】 （ここで、Ｔ′（Ｘk ）はエラー位置Ｘk における１次
    微分）によって定義されるチェン・ゼロ検索によって決
    定され、 ＲＳコードデータ信号のデータワードが、前記決定され
    たエラー位置Ｘk 及びエラー値Ｙk に基づいて訂正され
    るＲＳコードデータ信号を復号化する方法において、 コード生成多項式Ｇ（ｘ）＝（ｘ＋α0+b ）（ｘ＋α
    1+b ）．．．（ｘ＋α15 +b）に基づいてエラー位置Ｘk
    及びエラー値Ｙk のシンドローム（Ｓ（ｘ））が決定さ
    れ、 コード生成多項式 Ｇ（ｘ）＝（ｘ＋α0 ）（ｘ＋α1 ）．．．（ｘ＋α15） によるＲＳコードデータ信号を復号化する時に、この決
    定されたエラー値がＹkがエラー訂正に直接使用され、 ＲＳコードデータ信号のエラー訂正行われる前に、ゼロ
    に等しくないｂを有するコード生成多項式のＲＳコード
    データ信号を復号するときに、ファクタＸk bがコード
    生成多項式Ｇ（ｘ）＝（ｘ＋α0 ）（ｘ＋α1 ）．．．
    （ｘ＋α15）に対して決定されたエラー値Ｙk に与えら
    れることを特徴とするＲＳコードデータ信号を復号化す
    る方法。
  2. 【請求項２】 請求項１に記載のＲＳコードデータ信号
    を復号化する方法を実行する回路であって、 順次のデータブロックのシンドローム（Ｓ（ｘ））を形
    成し、ＲＳコードデータ信号中の消去位置（Ｌ（ｘ））
    を決定するデバイス（３）と、 Ｔs （ｘ）＝（Ｑs-1 （ｘ）＋Ｔs-2 （ｘ）） Ｒs （ｘ）＝（Ｑs-1 （ｘ））Ｒs-1 （ｘ）＋Ｒs-2 （ｘ）及び Ｑs-1 （ｘ）＝Ｒs-2 （ｘ）／Ｒs-1 （ｘ） （ここで、Ｔs （ｘ）はエラー位置多項式、Ｒs （ｘ）
    はエラー値多項式、及びＱs-1 （ｘ）は中間値多項式）
    であるユークリッドアルゴリズムを用いるデバイス
    （５）と、 【数２】 （ここで、Ｔ′（Ｘk ）は位置Ｘk における一次微分）
    の関係式によって定義されるチェン・ゼロ検索を用いて
    エラー位置Ｘk 及びエラー値Ｙk とを決定するデバイス
    （６）と、 この決定されたエラー位置Ｘk 及びエラー値Ｙk に基づ
    いてＲＳコードデータブロック中のデータワードを訂正
    するデバイス（７）とを具えるＲＳコードデータ信号を
    復号化する回路において、 シンドローム（Ｓ（ｘ））
    を決定するデバイス（３）中に配置されたシンドローム
    発生器（１１）がＲＳコードデータ信号の入力データワ
    ードが並列ビットで印加される第１の排他的ＯＲステー
    ジ（１４）と、 前記第１の排他的ＯＲステージ（１４）から供給される
    データワードを記憶するレジスタ（１３）と、 前記レジスタ（１３）の出力に生じるデータワードに定
    数αi （ここでｉは０−１５の間で制御可能な変数）を
    乗算する第１の乗算器（１５）と、 前記レジスタ（１３）の出力に存在するデータワードに
    定数αi+120 を乗算する第２の乗算器（１６）と、 α0 で始まるコード生成多項式によるＲＳコードデータ
    信号が復号されるときは、前記第１の乗算器（１５）の
    出力から前記第１の排他的ＯＲステージ（１４）の他の
    入力へデータを通過させ、α120 で始まるコード生成多
    項式によるＲＳコードデータ信号を復号するべきときに
    は、前記第２の乗算器（１６）の出力から前記第１の排
    他的ＯＲステージ（１４）の他の入力へデータを通過さ
    せる第１のマルチプレクサ（１７）を具え、 エラー位置Ｘk とエラー値Ｙk とを決定するデバイス
    （６）が、 データブロックに存在するデータワードをアップ計数
    し、計数値（ｘ）をチェン・ゼロ検索に供給するアップ
    カウンタ（４０）と、 前記アップカウンタ（４０）から供給される計数値
    （ｘ）が書き込まれる第１のスタックメモリ（４４）
    と、 前記第１のスタックメモリ（４４）からの読み取ったデ
    ータを各データブロックの最後に書き込むことができる
    第２のスタックメモリ（５６）と、 計数値（ｘk ）が前記第１のスタックメモリ（４４）に
    書き込まれると同時にエラー値（Ｙk ）を書き込むこと
    ができる第３のスタックメモリ（４５）と、 前記第３のスタックメモリ（４５）から読み取ったデー
    タをデータブロックの最後に書き込むことができる第４
    のスタックメモリ（６０）と、 前記アップカウンタ（４０）と並列に動作し、アップカ
    ウンタ（４０）に対してα-120のオフセットを有する反
    転カウンタ（４６）とを具え、 データワードを訂正するデバイス（７）が、 データブロック長の値で始まってダウン計数するダウン
    カウンタ（５２）と、 前記第２のスタックメモリ（５６）の上側位置に存在す
    る計数値と、前記ダウンカウンタ（５２）から供給され
    る計数値とを比較して、与えられた値が同じであるとき
    に制御信号（Found ）を導き出す回路（５７）と、 一の入力が前記比較回路（５７）の出力に接続されてい
    るＡＮＤゲート（５８）と、 前記反転カウンタ（４６）で制御され、１２０のオフセ
    ットを有する第２のアップカウンタ（６２）と、 前記第４のスタックメモリ（６０）の上側位置に存在す
    るエラー値（Ｘk ）と前記第２のアップカウンタ（６
    ２）から供給される計数値とを乗算する第３の乗算器
    （６１）と、 α0 で始まるコード生成多項式によるＲＳコードデータ
    信号が復号されるときに、前記第４のスタックメモリ
    （６０）の上側位置に存在するエラー値（Ｙk）を前記
    ＡＮＤゲート（５８）の他の入力へ通過させる第２のマ
    ルチプレクサであって、α120 で始まるコード生成多項
    式によるＲＳコードデータ信号を復号するべきときに
    は、前記第２のマルチプレクサの（５９）の出力に生じ
    る値（Ｙk）を前記ＡＮＤゲート（５８）の前記他の入
    力へ通過させる第２のマルチプレクサ（５９）と、 第１の入力で前記ＡＮＤゲート（５８）の出力から生じ
    得る信号を受け、第２の入力でＲＳコードデータ信号の
    ビット並列信号遅延適合データワードを受け、出力から
    はエラー訂正データワードを生じ得る第２の排他的ＯＲ
    ステージ（６６）とを具えることを特徴とするＲＳコー
    ドデータ信号を復号化する回路。
  3. 【請求項３】 請求項２に記載のＲＳコードデータ信号
    を復号化する回路において、前記アップカウンタ（４
    ０）が、第２のレジスタ（４２）の先段に第３のマルチ
    プレクサステージ（４１）を具え、第３のマルチプレク
    サの一の入力で、ブロックの開始時点において、値α0
    ＝１を受け、残りの期間中は、マルチプレクサステージ
    （４１）の他の入力端子で、前記レジスタ（４２）から
    供給される出力値の、値αi を乗じた値を伝えることを
    特徴とするＲＳコードデータ信号を復号化する回路。
  4. 【請求項４】 請求項２に記載のＲＳコードデータ信号
    を復号化する回路において、前記ダウンカウンタ（５
    ２）が、レジスタ（５４）に先段に第４のマルチプレク
    サステージ（５３）を具え、第４のマルチプレクサステ
    ージ（５３）の入力で、ブロックの開始時点で、ブロッ
    ク長の値を受け、残りの期間中は、第４のマルチプレク
    サステージ（５３）の他の入力で前記レジスタ（５４）
    から供給される出力値を伝えることを特徴とするＲＳコ
    ードデータ信号を復号化する回路。
  5. 【請求項５】 請求項２に記載のＲＳコードデータ信号
    を復号化する回路において、前記反転カウンタ（４６）
    が、レジスタ（４８）に先段に第５のマルチプレクサス
    テージ（４７）を具え、このレジスタがブロックの開始
    時点において、第５のマルチプレクサステージ（４７）
    を介して値α＝−１２０を受け、残りの期間中は、レジ
    スタ（４８）の出力に存在する値に、乗算ステージ（４
    ９）においてα120 を乗算した値を受けることを特徴と
    するＲＳコードデータ信号を復号化する回路。
  6. 【請求項６】 請求項５に記載のＲＳコードデータ信号
    を復号化する回路において、他のアップカウンタ（６
    ２）が第５のレジスタ（６３）に先段に第４のマルチプ
    レクサステージ（６４）を具え、レジスタ（６３）はブ
    ロックの開始時点において、第４のマルチプレクサステ
    ージ（６４）を介して第４のレジスタ（４８）の出力に
    存在する値を受け、残りの期間中は、第５のレジスタ
    （６３）の出力に存在する値に、第４の乗算ステージ
    （６５）においてα120 を乗算した値を受けることを特
    徴とするＲＳコードデータ信号を復号化する回路。
  7. 【請求項７】 請求項２乃至６のいずれかに記載のＲＳ
    コードデータ信号を復号化する回路において、各乗算ス
    テージが、ファクタαi+b （ここでｉ＝０〜１５，ｂ＝
    １２０もしくは０）を乗算する、排他的ＯＲゲートとし
    て形成されていることを特徴とするＲＳコードデータ信
    号を復号化する回路。
JP4325812A 1991-12-04 1992-12-04 Ｒｓコードデータ信号を復号化する方法および回路 Pending JPH0653842A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE4140018A DE4140018A1 (de) 1991-12-04 1991-12-04 Verfahren und schaltungsanordnung zum decodieren von rs-codierten datensignalen
DE4140018.6 1991-12-04

Publications (1)

Publication Number Publication Date
JPH0653842A true JPH0653842A (ja) 1994-02-25

Family

ID=6446274

Family Applications (1)

Application Number Title Priority Date Filing Date
JP4325812A Pending JPH0653842A (ja) 1991-12-04 1992-12-04 Ｒｓコードデータ信号を復号化する方法および回路

Country Status (4)

Country Link
US (1) US5490154A (ja)
EP (1) EP0545498B1 (ja)
JP (1) JPH0653842A (ja)
DE (2) DE4140018A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100380788B1 (ko) * 2000-03-29 2003-04-18 가부시끼가이샤 도시바 복호장치 및 복호방법

Families Citing this family (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3176171B2 (ja) * 1993-04-21 2001-06-11 キヤノン株式会社 誤り訂正方法及びその装置
US5483236A (en) * 1993-12-20 1996-01-09 At&T Corp. Method and apparatus for a reduced iteration decoder
KR970004515B1 (ko) * 1993-12-29 1997-03-28 삼성전자 주식회사 리드-솔로몬 복호기의 오류위치다항식 연산방법 및 장치
JPH088760A (ja) * 1994-06-16 1996-01-12 Toshiba Corp 誤り訂正装置
US5715262A (en) * 1995-07-12 1998-02-03 Lsi Logic Corporation Errors and erasures correcting reed-solomon decoder
JP2907138B2 (ja) * 1996-08-15 1999-06-21 日本電気株式会社 誤り訂正の演算処理方法及び処理回路
TW311189B (en) * 1996-09-30 1997-07-21 United Microelectronics Corp The error-corrected decoding method and its apparatus for Reed-Soloman code
JPH10112659A (ja) * 1996-10-08 1998-04-28 Canon Inc 誤り訂正復号装置
JP3710586B2 (ja) * 1997-02-21 2005-10-26 株式会社ルネサステクノロジ 誤り訂正装置
JPH113573A (ja) * 1997-04-15 1999-01-06 Mitsubishi Electric Corp 拡大リードソロモン符号の誤り訂正復号方法と誤り訂正復号装置、１次伸長拡大リードソロモン符号の誤り訂正方法と誤り訂正装置、および２次伸長拡大リードソロモン符号の誤り訂正方法と誤り訂正装置
JPH11136136A (ja) * 1997-10-29 1999-05-21 Nec Corp リードソロモン符号化装置及び方法
US6115837A (en) * 1998-07-29 2000-09-05 Neomagic Corp. Dual-column syndrome generation for DVD error correction using an embedded DRAM
US20080282128A1 (en) * 1999-08-04 2008-11-13 Super Talent Electronics, Inc. Method of Error Correction Code on Solid State Disk to Gain Data Security and Higher Performance
DE19960923B4 (de) * 1999-12-17 2004-08-19 Micronas Gmbh Einrichtung zur Datenumsetzung für einen Reed-Solomon Dekodierer
US20030140302A1 (en) * 2002-01-23 2003-07-24 Litwin, Louis Robert Chien search cell for an error-correcting decoder
KR101678917B1 (ko) * 2010-09-16 2016-11-24 삼성전자주식회사 디코더, 이의 동작방법, 및 이를 포함하는 장치들
US8621331B1 (en) * 2011-06-03 2013-12-31 Altera Corporation Continuous parallel cyclic BCH decoding architecture
US10055159B2 (en) * 2016-06-20 2018-08-21 Samsung Electronics Co., Ltd. Morphic storage device
CN108471315B (zh) * 2017-02-23 2021-08-20 杭州海康威视数字技术股份有限公司 一种纠删译码方法及装置

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS63316524A (ja) * 1987-06-18 1988-12-23 Sony Corp リ−ド・ソロモン符号の復号方法
DE3856035T2 (de) * 1987-08-24 1998-02-26 Quantum Corp Schaltung mit grosser bandbreite und verfahren zur reed-solomon-kodierung, dekodierung und fehlerkorrektur
US5107503A (en) * 1987-08-24 1992-04-21 Digital Equipment Corporation High bandwidth reed-solomon encoding, decoding and error correcting circuit
US4873688A (en) * 1987-10-05 1989-10-10 Idaho Research Foundation High-speed real-time Reed-Solomon decoder
DE3838234A1 (de) * 1988-11-11 1990-05-17 Broadcast Television Syst Verfahren und schaltungsanordnung zur detektion und korrektur von fehlern in datenworten
ATE116081T1 (de) * 1989-08-24 1995-01-15 Philips Nv Verfahren und einrichtung zur decodierung von wortgeschützten codewörtern durch einen nichtbinären bch-code gegen mindestens einen symbolfehler.
US5170399A (en) * 1989-08-30 1992-12-08 Idaho Research Foundation, Inc. Reed-Solomon Euclid algorithm decoder having a process configurable Euclid stack
US5099482A (en) * 1989-08-30 1992-03-24 Idaho Research Foundation, Inc. Apparatus for detecting uncorrectable error patterns when using Euclid's algorithm to decode Reed-Solomon (BCH) codes
US5241546A (en) * 1991-02-01 1993-08-31 Quantum Corporation On-the-fly error correction with embedded digital controller
JP2709536B2 (ja) * 1991-03-15 1998-02-04 株式会社テイエルブイ 熱応動式スチ―ムトラップ

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100380788B1 (ko) * 2000-03-29 2003-04-18 가부시끼가이샤 도시바 복호장치 및 복호방법

Also Published As

Publication number Publication date
EP0545498A3 (ja) 1994-02-23
DE4140018A1 (de) 1993-06-09
US5490154A (en) 1996-02-06
DE59208232D1 (de) 1997-04-24
EP0545498B1 (de) 1997-03-19
EP0545498A2 (de) 1993-06-09

Similar Documents

Publication Publication Date Title
JPH0653842A (ja) Ｒｓコードデータ信号を復号化する方法および回路
US5170399A (en) Reed-Solomon Euclid algorithm decoder having a process configurable Euclid stack
EP0096109B1 (en) Error correcting system
US6058500A (en) High-speed syndrome calculation
US6026420A (en) High-speed evaluation of polynomials
US6725416B2 (en) Forward error correction apparatus and methods
JPH0831803B2 (ja) 誤り訂正のための方法と装置
WO2000057561A1 (en) Pipelined high speed reed-solomon error/erasure decoder
US5805617A (en) Apparatus for computing error correction syndromes
JPH0575479A (ja) データ流における誤りの識別、補正修整回路装置
US4527269A (en) Encoder verifier
KR100970223B1 (ko) 리드-솔로몬 코드의 소프트-결정 디코딩 방법, 리드-솔로몬 코드워드 디코더 및 컴퓨터 프로그램 제품
US5541937A (en) Apparatus for uniformly correcting erasure and error of received word by using a common polynomial
US5107506A (en) Error trapping decoding method and apparatus
US6651214B1 (en) Bi-directional decodable Reed-Solomon codes
US6735737B2 (en) Error correction structures and methods
US20030097632A1 (en) Decoding method and decoder for Reed Solomon code
JPH09505455A (ja) 相互間挿した信号部分のエラー検出装置および方法と該エラー検出を採用した受信機および復号方法
JP3281938B2 (ja) 誤り訂正装置
EP1037148B1 (en) Error coding method
US6446233B1 (en) Forward error correction apparatus and methods
JP2591611B2 (ja) ｔ重誤り訂正符号の符号化復号化回路
JP3230888B2 (ja) ユークリッド互除回路
JP2553571B2 (ja) ガロア体演算装置
JP2006033233A (ja) リード・ソロモン復号方法及び装置