WO1994015406A1 - Procede et circuit de correction d'erreurs - Google Patents

Procede et circuit de correction d'erreurs Download PDF

Info

Publication number
WO1994015406A1
WO1994015406A1 PCT/JP1993/001854 JP9301854W WO9415406A1 WO 1994015406 A1 WO1994015406 A1 WO 1994015406A1 JP 9301854 W JP9301854 W JP 9301854W WO 9415406 A1 WO9415406 A1 WO 9415406A1
Authority
WO
WIPO (PCT)
Prior art keywords
registers
syndrome
error
data
value
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.)
Ceased
Application number
PCT/JP1993/001854
Other languages
English (en)
French (fr)
Inventor
Mamoru Akita
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.)
Sony Corp
Original Assignee
Sony Corp
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 Sony Corp filed Critical Sony Corp
Priority to US08/290,886 priority Critical patent/US5541940A/en
Priority to EP94903038A priority patent/EP0629052B1/en
Priority to DE69325900T priority patent/DE69325900T2/de
Publication of WO1994015406A1 publication Critical patent/WO1994015406A1/ja
Anticipated expiration legal-status Critical
Ceased 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
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B5/00—Recording by magnetisation or demagnetisation of a record carrier; Reproducing by magnetic means; Record carriers therefor
    • G11B5/02—Recording, reproducing, or erasing methods; Read, write or erase circuits therefor
    • G11B5/09—Digital recording

Definitions

  • Patent application title Error correction method and error correction circuit
  • the present invention relates to an error correction method and an error correction circuit, and more particularly to an error correction method in a device for processing digital data such as a CD (Compact Disc) or DAT (Digital Audio Tape) playback device.
  • the present invention relates to an error correction method and an error correction circuit suitable for use in the present invention.
  • the error correction code has a form in which a two-stage Reed-Solomon code is connected by an interleave, and is called CIRC (Cross Inter) eaved Reed-Solomon Code).
  • CIRC Cross Inter
  • the two-stage Reed-Solomon code used for CIRC is called C1 and C2, respectively.
  • the data generated in this way is recorded on the disc. Then, when the recorded data on the disc is reproduced, errors are included due to various factors.
  • the processing of this calculation is performed by an adder 41 receiving the received data as one input, a register 42 storing the added data by the adder 41, and a register 42
  • the multiplication can be performed by a circuit composed of the multiplication circuit 43 and the multiplication of the stored data and the other input of the adder 41.
  • the multiplication circuit 43 and the adder 41 can be easily realized by combining exclusive OR (EX-0 R) gates as shown in FIGS. 6 and ⁇ ⁇ due to the properties of the Galois field. .
  • codes used in CD can correct up to two bytes of errors.
  • the reason is that the magnitude of the error e i and the position i of the erroneous received data may be obtained from the syndrome calculated in this way.
  • this calculation is performed on a Galois field.
  • the number to be calculated is transformed into a power of, so that the exponent and R ⁇ ⁇ that stores a logarithmic table must be used, and its peripheral circuits There is a problem that the circuit scale becomes large due to the complicated circuit configuration.
  • the present invention has been made in view of such a problem, and an object thereof is to provide an error correction method and an error correction method capable of realizing error detection and error correction with a very small circuit configuration. It is to provide a correction circuit.
  • the first invention calculates n (n is a positive integer) number of syndromes determined by the number of parity added to the received data from the received data, and when a single error occurs, calculates the error.
  • a single syndrome mouth representing the size is stored in a single syndrome register, and the other syndromes are stored in (n ⁇ 1) number of syndrome registers, respectively.
  • the value of the single syndrome register is stored in the (n ⁇ 1) syndrome registers and the (n ⁇ 1) syndromes are stored in the (n ⁇ 1) syndrome registers.
  • Each value of the stream register is loaded into (n-1) data registers, and the root of the generator polynomial on the Galois field is ", and the (n-1) simpled registers
  • the power operation of ⁇ , ——, “( ⁇ _ ') is calculated using the above ( ⁇ — 1) syndrome registers.
  • the operation is repeated until the coincidence between each value of the star and each value of the ( ⁇ -1) data registers is detected, and the counting operation is performed in synchronization with the exponentiation operation.
  • the point value is set to the data position containing the error
  • the value of the single syndrome register is set to the size of the error
  • error correction is performed based on the data position and the size of the error. It is something to do.
  • the syndrome is calculated by the syndrome registers S0 and S1 to S ( ⁇ -1).
  • the values of the system registers S0 to S ( ⁇ -1) are stored in the system registers S1 to S ( ⁇ -1), and the values of the system registers S] to S ( ⁇ -1) are stored in the data registers. ,,,, ..., (n " n )
  • the exponentiation operation is repeated until each value of the simple register S1 to S (n-1) matches each value of the data register R1 to R (n-1), and the exponentiation is performed.
  • the counter performs the counting operation in synchronization with the calculation, and when the values of the registers S1 to S (n-1) match the values of the registers Rl to R (n-1) are detected.
  • the count value at the time point is the data position containing the error, and the magnitude of the error is the value of the simple register S 0.
  • a second invention is an error correction circuit using the error correction method of the first invention, which calculates a syndrome from received data and indicates the magnitude of the error when there is a single error.
  • a single-register register that stores a syndrome and a group of (n-1) -three register registers that store other syndromes And (n-1) data registers for holding the values stored in the (n-1) syndrome registers and the (n-1) syndromes, respectively.
  • a match detection circuit for detecting that each value of the register matches each value of the (n-1) data registers; performing a count operation in synchronization with the exponentiation operation; Force to stop force point operation in response to circuit detection output ⁇ And error correction is performed based on the count value of the power counter and the value of the single syndrome register.
  • FIG. 1 is a block diagram showing an embodiment of the error correction circuit according to the present invention.
  • FIG. 2 is a flowchart of the error correction algorithm according to the present invention.
  • Figure 3 is a flowchart of the calculation algorithm for syndrome S1.
  • FIG. 4 is a block diagram showing an example of the calculation circuit of the syndrome S1.
  • FIG. 5 is a block diagram illustrating an example of a calculation circuit for the syndromes S0 to S4.
  • FIG. 6 is a block diagram showing an example of the multiplying circuit.
  • FIG. 5 is a block diagram showing an example of an adder on a Galois field. BEST MODE FOR CARRYING OUT THE INVENTION
  • FIG. 1 is a block diagram showing an embodiment of an error correction circuit according to the present invention.
  • received data RD is one input of each of four adders (11) to (14).
  • Each addition data by these adders (11) to (14) is converted into four syndrome registers [S0 to S3] for calculating the syndromes S0 to S3. ] (15) to (18) are stored.
  • the syndrome registers (15) to (18) operate in synchronization with the clock CK.
  • the storage data of each of the storage registers [S1 to S3] (16) to (18) are stored.
  • the "multiplication circuits (1-9), a square circuit (2 0), arsenic cube circuit (2 1) through each adder (1 2), (1 3), and each other input (1 4) are stored in three data registers [R1 to R3] (22) to (24), respectively.
  • the stored data of the data registers [R1 to R3] (22) to (24) are input to one of the three logical gates (25) to (27).
  • These logic gates (25) to (27) use the stored data of the syndrome registers [31 to 53] (16) to (18) as the other inputs. When the logical values of the corresponding bits of the two registers match, the output level becomes logical "1".
  • the outputs of the logic gates (25) to (27) are the inputs of the three-input AND gate (28).
  • the output level of the AND gate 28 becomes logic "1" when both input levels are logic "1", that is, when the logic gates (25 :) to (27) match together.
  • a counter (29) for counting the same clock CK as the four syndrome registers (15)-(18) is provided, and this counter (29)
  • the CPU (30) controls the setting of the initial value and the stop of the count operation by the CPU (30).
  • the counter (29) sets the initial value to This bit is set to "0", and when the AND gate (28) detects a match, the counting operation is stopped.
  • the value of the S0 register (15) at the end of the error calculation is the error size e, and the count value j of the counter (29) is the error data number (position) i. Becomes Then, the reception data at the error location 1 stored in the buffer memory (not shown) is called into the input section of the reception data shown in FIG. 1, and the data of the S0 register (15) is read and stored.
  • the SO register (The error-corrected data remains in 15), and the error-corrected data DT is output to complete the error correction processing.
  • step 24 the data stored in the simple register [S0] (15) is stored in the syndrome register [S1 to S3] (step S2).
  • the S-register and the R-register are all harmful.
  • step S 4 if the above condition is not satisfied, subject to the condition .j ⁇ 31 (step S 5), “'S 1—S l, 2 ⁇ S 2 ⁇ S 2, 3 -S 3 ⁇ S3 is calculated (step S6), and then the count value j of the counter 29 is counted up by one (step S7), and then Return to step S4.
  • step S6 can be realized only by inputting "0" as received data.
  • step S6 This condition is satisfied if the first (X, ') of the received data contains an error. If this condition is not satisfied, the processing of step S6 and step S7 is executed again.
  • step S8 the count value j of the counter (29) is set to the number of the data containing the error, and the magnitude of the error is plotted as a shadow.
  • step S9 The value of the system register [S0] (15) is set (step S9).
  • step S5 if it is determined that the S register and the R register do not match even if the count value j of the counter (29) exceeds 31, two bytes or more are required. It is determined that the data of the data is incorrect and cannot be corrected (step S11).
  • the syndrome is calculated by the simple register S0, S1 to S (n-1), and after the calculation, 1 is calculated.
  • the value of the syndrome register S0 is stored in the syndrome registers S1 to S (n-1) and the values of the syndrome registers S1 to S (n-1) are Each value is loaded to the data registers R1 to R (n-1), respectively, and the sign registers S1 to S (n-1) are used to store the values ⁇ ,. ) Is repeated until the values of the simple register S1 to S (n-1) match the values of the data registers Rl to R (n-1).
  • the count operation is performed in synchronization with the multiplication operation, the force point value at the time of the coincidence detection is set as the data position containing the error, and the value of the syndrome register S0 is set.
  • the error detection and error correction of a single heavy machine can be realized with an extremely small-scale circuit configuration in which only one counter and a coincidence detection circuit are added.
  • the present invention is not limited to this. It can be applied to all devices that process digital data without being affected, for example, if it is applied to a DAT playback device with a signal format that has six simple streams
  • the number of syndromes depends on the number of syndromes. The same can be done by increasing the number of registers and data registers.

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)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)

Description

明 細 書
発明の名称 エラー訂正方法及びエラー訂正回路
技術分野
本発明は、 エラー訂正方法及びエラー訂正回路に関し、 特に C D (コ ンパク トディ スク） や D A T (ディ ジタル · オーディオ ' テープ） の再生装置等の如きディ ジタル · データを処理する装置 におけるェラ一訂正に用いて好適なェラ一訂正方法及びェラー訂 正回路に関する。
背景技術
C Dの場合、 その誤り訂正符号は、 2段の Reed-Solomon符号を イ ンタ リ ーブで結合した形をしており、 C I R C (Cross Inter] eaved Reed-Solomon Cod e)と呼称されている。 そして、 C I R C に用いられている 2段の Reed-Solomon符号はそれぞれ C 1 , C 2 と呼ばれている。
C 1訂正を例にとると、 2 8バイ トのデータに 4バイ トのパリ ティが付加されて 3 2ノ ィ ト単位となっている。 そして、 この 3 2バイ 卜のデータを、 それぞれ X 。 〜 X 3 ,と呼ぶことにする。 ここで、 4バイ トのパリ ティ は、 〔数式 1 〕 の 4つの式の値が 全て " 0 " になるように選ばれる。
〔数式 1 〕
X + X + + X + + X = 0
X + X + + X + + X 3 ,= 0
X + X a 2 + + X « " + + X (X 62= 0
X + X a 3 + + X + X a
このようにして生成されたデータが、 ディ スク上に記録されて いる訳である。 そして、 そのディ スク上の記録データを再生した ときに、 種々の要因によって誤りが含まれることになる。
こ こで、 ディ スクから読み取りかつェラ一訂正回路で受信した データ （誤りを含んだデータ） を、 ディスクに記録したデータ と 区別するためにそれぞれ X 。 ' 〜 χ 3 1' と表記する。
実際に、 エラ一訂正を行うときには、 データを受信すると、 先 ず、 シ ン ドロ ーム S 0〜 S 3を 〔数式 2〕 に基づいて計算する。
〔数式 2〕
' S 0 = X 。 — + I ' + + X + + x
S 1 = X 0 ' + X 1 ' + X 1 + + X
S 2 = X 0 ' + 1 ' oc + + X 2 i + + X a k S 3 = 0 ' -f~ i ' a + + X 3 i + + X a ところで、 ガロア体の理論によると、 2 8 個の要素を持つ有限 体が存在することが証明されている。 これを G F ( 2 8)と表す。
また、 C Dで用いられているものは、 この中でも、 〔数式 3〕 の生成多項式で定義されているものである。
〔数式 3〕
P ( X ) X + X X + X 2 + 1
そして、 P ( X ) = 0 とおいたときの方程式の根を《とする。 〔数式 2〕 から容易にわかるように、 も し、 受信したデータに 誤りが含まれていなければ、 S 0 = S 1 = S 2 = S 3 = 0 となる (そうなるように、 記録時にパリティが付加されている） 。 逆に 、 1 つでも " 0 " でないものが存在すれば、 データの誤りを検出 できたことになる。
以上のように、 エラー訂正前に 〔数式 2〕 にしたがってシ ン ド ロームを求める必要があるが、 この式のまま計算を行うと、 計算 の回数が多く なつてしまう。
そこで、 〔数式 2〕 を 〔数式 4〕 のように変形する。 f S 0 = X o ' 十 X l ' H r
I S 1 = x o ' a (x i ·' 卞 (x 2 ' H or (x 3o' 十 (x si' ))···))
I S 2 = x o ' 十
Figure imgf000005_0001
i ' T o-2(x 2 ' Λ H arz(x so' 十 αζ(Χ3ΐ' ))···))
( S 3 = x o ' 十 3(Χ ι ' + -3(x 2 ' -i 1- ar3(x 3o' 十び3 (χ3ι' ))···)) こ こで、 S 1 を例にとると、 図 3に示すようなアルゴ リ ズムで 計算できる。 他の S O， S 2 , S 3についても、 ひ乗をそれぞれ 変えてやるだけで同様に計算できる。
また、 この計算の処理は、 図 4 に示すように、 受信データを一 入力とする加算器 4 1 と、 この加算器 4 1 による加算データを格 納するレジスタ 4 2 と、 このレジスタ 4 2の格納デ一夕を 乗し て加算器 4 1 の他入力とする《乗回路 4 3 とからなる回路で行う こ とができ る。
図 4 において、 レジス タ 4 2がリ セ ッ ト されている状態から、 X 3 から順に受信したデータを入力していき、 最後に x。 ' を 入力したときのレジスタ 4 2の値が S 1 となる。
実際には、 S 0， S 2， S 3 も必要なので、 図 5に示すように 、 4個のレジス タ 4 2 0 〜 4 2 3 を並べて計算の処理を行ってい る。
なお、 《乗回路 4 3及び加算器 4 1 は、 ガロア体の性質から、 図 6及び図 Ί に示すように、 排他的論理和 （E X— 0 R ) ゲー ト を組み合わせることによって容易に実現できる。
ところで、 一般には、 てラー訂正を行う前に、 どの程度のエラ 一が生じたかを検出することが重要である。 また、 C Dで使用さ れている符号では、 2バイ トまでのエラ一訂正が可能である。
そ こで、 従来は、 シ ン ド ロ ーム計算終了後に、 エラーが何バイ ト （ 0バイ ト 、 1 バイ ト、 2バイ ト以上） 発生したかを判断する ための計算を行つていた。
仮に、 受信したデータ X i ' が大きさ e i だけ誤っていたとす ると、 シ ン ドロ一厶はパリ ティの決め方から容易にわかるように 、 〔数式 5〕 となる。
〔数式 5〕
Figure imgf000006_0001
このようにして計算したシ ン ドロームから、 誤りの大きさ e i と誤っている受信データの位置 i とを求めれば良い訳である。
〔数式 5〕 の 4つの方程式に対して未知数は 2つであるため、 簡単に解く ことができる。 例えば、 〔数式 6〕 に基づいて求めれ ば良いように思われる。
〔数式 6〕
S 1
(X ' =
S 0
e i = S O
しかし、 これだけでは、 受信データに 2バイ ト以上の誤りが存 在した場合に誤訂正をしてしまうので、 〔数式 5〕 から求めた《 1 及び e i を用いて、 e i " 2 iと e i " 3 iを求め、 これが 〔数式 5〕 の S 2 , S 3 とそれぞれ一致することを確認する必要がある このように、 上述したアルゴ リ ズムによる従来のエラ一訂正回 路では、 1 バイ ト訂正に少なく とも 1 回の割り算と 2回の掛け算 を行う必要がある。
また、 この計算はガロア体上の計算であり、 一般に、 ガロア体 上で掛け算、 割り算を行うときは、 計算したい数を のべき乗の 形に変形して行う ことから、 その変換のための指数と対数のテー ブルを格納する R Ο Μを用いなければならず、 又その周辺回路も 複雑な回路構成となるため、 回路規模が大き く なってしまうとい う問題があった。
発明の開示
本発明は、 このような問題点に鑑みてなされたものであり、 そ の目的とするところは、 極めて小規模な回路構成にてエラー検出 及びェラ一訂正が実現できるエラ一訂正方法及びェラ一訂正回路 を提供することにある。
第 1 の発明は、 受信データからこの受信データに付加されるパ リ ティ数で決まる n ( n は正の整数） 個のシ ン ド ロ ームを計算し かつ 1重誤りのときその誤りの大きさを表すシ ン ド口一人を単一 のシ ン ドロ ーム レジス タ に、 それ以外のシ ン ドロ ームを （ n— 1 ) 個のシ ン ドロ 一厶 レジス タ にそれぞれ格納し、 シ ン ド ロ ームの 計算終了後、 前記単一のシ ン ドロ ーム レジスタの値を前記 （ n— 1 ) 個のシ ン ドロ ーム レジスタ に、 前記 （ n— 1 ) 個のシ ン ドロ ームレジスタの各値を （ n — 1 ) 個のデータ レジスタにそれぞれ ロー ドし、 ガロア体上の生成多項式の根を "とするとき、 前記 （ n — 1 ) 個のシ ン ド ロ ーム レジスタを用いて α， ——， " （ η _ ' ) のべき乗演算を前記 （ η — 1 ) 個のシ ン ドロ ーム レジス タの各値 と前記 （ η— 1 ) 個のデータ レジスタの各値の一致を検出するま で繰り返すとともに、 べき乗演算に同期してカ ウ ン ト動作を行い 、 前記一致の検出時点の力ゥ ン ト値を誤りが含まれているデータ 位置とするとともに、 前記単一のシ ン ドロームレジスタ の値を誤 りの大きさと し、 前記データ位置及び前記誤りの大きさに基づい てエラー訂正を行うようにしたものである。 このことによって、 シ ン ド ロ ーム レジス タ S 0， S 1〜 S ( η - 1 ) によ ってシ ン ド ロームを計算し、 その計算終了後、 1重誤りのときシ ン ド ロ ーム レジス タ S 0 の値をシ ン ド ロ ーム レジス タ S 1〜 S ( η - 1 ) に 、 シ ン ド ロームレジスタ S 】 〜 S ( η - 1 ) の各値をデータ レジ ス タ R 1 〜R ( n - 1 ) にそれぞれロ ー ド し、 このシ ン ド ロ ーム レジス タ S 1 〜 S ( n - 1 ) を用いて ， · · · ·， ( n " n のべき 乗演算を、 シ ン ド ロ ーム レジスタ S 1 〜 S ( n - 1 ) の各値とデ ータ レジスタ R 1 〜R ( n - 1 ) の各値を一致するまで繰り返す とともに、 そのべき乗演算に同期してカウ ンタのカウ ン ト動作を 行う。 これによ り、 レジス タ S 1 ~ S ( n - 1 ) と レジスタ R l 〜R ( n - 1 ) の各値の一致を検出した時点のカウ ン ト値が誤り が含まれているデータ位置となり、 その誤りの大きさがシ ン ドロ —ム レジス タ S 0 の値となる。
また第 2の発明は、 第 1 の発明のエラー訂正方法を用いたエラ 一訂正回路であって、 受信データからシン ド口ームを計算しかつ 1重誤りのときその誤りの大きさを表わすシン ド口ームを格納す る単一のシ ン ドローム レジスタ及びそれ以外のシ ン ドロームを格 納する （ n — 1 ) 個のシ ン ド ロ ーム レジスタからなるシ ン ドロー 厶 レジスタ群と、 前記 （ n — 1 ) 個のシ ン ド ロ ーム レジスタ に格 納された各値を保持する （ n — 1 ) 個のデータ レジスタ と、 前記 ( n - 1 ) 個のシ ン ドロ ーム レジスタの各値と前記 （ n — 1 ) 個 のデータ レジスタの各値が一致したことを検出する一致検出回路 と、 前記べき乗演算に同期してカ ウ ン ト動作を行うとともに、 前 記一致検出回路の検出出力に応答して力ゥ ン ト動作を停止する力 ゥ ンタとを具備し、 前記力ゥ ンタのカ ウ ン ト値及び前記単一のシ ン ドローム レジスタ の値に基づいてエラー訂正を行うようにした ものである。 このこ とによ って、 シ ン ドロ ームの計算に絶対に必 要な n個のシ ン ド α —厶 レジスタ に、 （ η _ 1 ) 個のデータ レジ スタ、 1個のカウ ンタ及び一致検出回路を付加するだけの極めて 小規模な回路構成で、 1 重工ラー （ 1 バイ トエラー） のエラー検 出及びエラー訂正を実現できる。
図而の簡単な説明 図 1 は本発明によるエラー訂正回路の一実施例を示すプロ ッ ク 図である。
図 2 は本発明によるエラー訂正了ルゴリズ厶のフ 口 一チ ヤ一 ト である。
図 3はシ ン ドロ ーム S 1 の計算アルゴ リ ズムのフ ロ ーチ ャ ー ト である。
図 4 はシ ン ドローム S 1 の計算回路の一例を示すブロ ッ ク図で ある。
図 5 はシ ン ドロ ーム S 0〜 S 4の計算回路の一例を示すブ口 ッ ク図である。
図 6 は "乗回路の一例を示すブロ ッ ク図である。
図 Ί はガロァ体上での加算器の一例を示すプロ ッ ク図である。 発明を実施するための最良の形態
以下、 本発明の実施例を図面に基づいて詳細に説明する。
図 1 は、 本発明によるエラ一訂正回路の一実施例を示すプロ ッ ク図である。
図 1 において、 受信データ R Dは、 4つの加算器 （ 1 1 ) 〜 （ 1 4 ) の各一入力となる。 これら加算器 （ 1 1 ) 〜 （ 1 4 ) によ る各加算データは、 シ ン ドロ ーム S 0〜 S 3を計算するための 4 つのシ ン ドロ ーム レジス タ 〔 S 0〜 S 3〕 （ 1 5 ) 〜 （ 1 8 ) に 格納される。 シ ン ドロ ーム レジス タ （ 1 5 ) 〜 （ 1 8 ) は、 ク ロ ッ ク C Kに同期して動作する。
4つのシ ン ドロ ーム レジス タ （ 1 5 ) 〜 （ 1 8 ) のうち、 シ ン ド ロ ーム レジスタ 〔 S 1 〜 S 3〕 （ 1 6 ) 〜 （ 1 8 ) の各格納デ 一夕は、 "乗回路 （ 1 9 ) 、 2 乗回路 （ 2 0 ) 、 ひ 3 乗回路 （ 2 1 ) をそれぞれ経て加算器 （ 1 2 ) ， （ 1 3 ) ， （ 1 4 ) の各 他入力となるとともに、 3つのデータ レジス タ 〔 R 1 〜 R 3〕 ( 2 2 ) 〜 （ 2 4 ) にそれぞれ格納される。 データ レジスタ 〔 R 1 〜 R 3〕 ( 2 2 ) ~ ( 2 4 ) の各格納デ —タは、 3つの論理ゲー ト （ 2 5 ) 〜 （ 2 7 ) の各一方の入力と なる。
これら論理ゲ— ト （ 2 5 ) 〜 （ 2 7 ) は、 シ ン ドロ ーム レジス タ 〔 3 1 ~ 5 3〕 （ 1 6 ) 〜 （ 1 8 ) の各格納データを他方の入 力と し、 2組のレジス タ の対応する各ビッ トの論理値が全て一致 したとき出力レベルが論理 " 1 " となる。 論理ゲー ト （ 2 5 ) 〜 ( 2 7 ) の各出力は、 3入力 A N Dゲー ト （ 2 8 ) の各入力とな る。
A N Dゲー ト 2 8は、 各入力レベルが共に論理 " 1 " のとき、 即ち論理ゲー ト （ 2 5：) 〜 （ 2 7 ) が共に一致のとき出力レベル が論理 " 1 " となる。
一方、 4つのシン ドロ ーム レジスタ （ 1 5 ) - ( 1 8 ) と同じ ク ロ ッ ク C Kをカウ ン トするカウ ンタ （ 2 9 ) が設けられており 、 このカ ウ ンタ （ 2 9 ) は C P U ( 3 0 ) によ って初期値のセ ッ ト及びカ ウ ン ト動作の停止の制御が行われる。
すなわち、 求めたシ ン ド ロ ーム S 0 ~ S 3から、 受信データに 含まれる誤りデータの番号 （位置） i とその大きさ e i を求める 際に、 カウ ンタ （ 2 9 ) は初期値を " 0 " にセッ ト され、 A N D ゲー ト （ 2 8 ) がー致を検出した時点でそのカウ ン ト動作が停止 させられる。
ェラ一計算が終了すると、 その終了時点における S 0 レジスタ ( 1 5 ) の値がエラ一の大きさ e 、 カウ ンタ （ 2 9 ) のカウ ン ト値 j が誤りデータの番号 （位置） i となる。 そして、 図 1 の受 信データの入力部に、 図示せぬバッ フ ァメモ リ に格納されている ェラ一位置 i の受信データを呼び出し、 S 0 レジスタ （ 1 5 ) の テ "一夕 と力卩算を ίΐう。
このような処理を計算終了に行う ことにより、 S O レジスタ （ 1 5 ) にエラ一訂正済みのデータが残り、 このエラー訂正済みの データ D Tを出力させてエラー訂正処理が完了することになる。
次に、 本発明のアルゴ リ ズムにっき、 図 2のフ ロ ーチ ャ ー ト に したがって説明する。
先ず、 加算器 （ 1 1 ) 〜 （ 1 4 ) 、 シ ン ド ロ ーム レジスタ 〔 S 0〜 S 3〕 （ 1 5；) 〜 （ 1 8 ) 及び 乗回路 （ 1 9 ) 、 ひ 2 乗回 路 （ 2 0 ) 、 《 3 乗回路 （ 2 1 ) によってシ ン ド σ—ムの計算を 行う （ステップ S 1 ) 。
こ こで、 例えば、 i 番目の受信データが大きさ e i だけ誤って いたと仮定すると、 〔数式 5〕 より、 シ ン ド ロ ームは、 S 0 = e
1 , S 1 - e 4 a 4 , S 2 = e i a 2 i, S S - e i 31となる。 次に、 シ ン ドロ ーム レジス タ 〔 S 1 〜 S 3〕 （ 1 6 ) 〜 （ 1 8
) の各格納データをデータ レジスタ 〔R 1 〜 R 3〕 ( 2 2 ) 〜 （
2 4 ) へ、 シ ン ド ロ ーム レジスタ 〔 S 0〕 ( 1 5 ) の格納データ をシ ン ドロ ーム レジス タ 〔 S 1 〜 S 3〕 へそれぞれ格納する （ス テツプ S 2 ) 。
この結果、 シ ン ドロ ーム レジスタ 〔 S 0〜 S 3〕 ( 1 5 ) 〜 （ 1 8 ) の各値は、 S 0 = S l = S 2 = S 3 = e i ， R 1 = e i 1 , R 2 = e i 2', R 3 = e i " 3 iとなる。
続いて、 カウ ンタ 2 9の初期値を " 0 " にセッ ト し （ステップ S 3 ) 、 シ ン ドロ ーム レジスタ （ 1 6 ) 〜 （ 1 8 ) 、 データ レジ スタ （ 2 2 ) 〜 （ 2 4 ) にぉぃて、 3 1 = 1? 1 ， S 2 = R 2 , S
3 = R 3の条件が成立するか否かを調べる （ステップ S 4 ) 。 こ こで、 も し、 受信したデータの 0審目 （ x。 ' ） が誤ってい る場合は、 S レジス タ と R レジス タは 3つとも一致する害である ο
なお、 受信したデータに誤りがなかったときも、 上記の条件が 成立することになる力 、 それは、 後述するように、 S 0 = 0 とな ることで弁別できる。
ステップ S 4 において、 もし、 上記の条件が成立しないときは . j ≤ 3 1を条件に （ステ ッ プ S 5 ) 、 " ' S 1— S l， 2 · S 2→ S 2 , 3 - S 3→ S 3の計算を行い （ステ ッ プ S 6 ) 、 続いてカ ウ ンタ 2 9のカ ウ ン ト値 j を 1 つカ ウ ン ト ア ッ プし （ス テツプ S 7 ) 、 しかる後ステップ S 4に戻る。
ステツプ S 6 における計算は、 受信データと して " 0 " を入力 してやるだけで実現できる。
この計算の結果、 シ ン ド ロ ーム レジス タ （ 1 6 ) 〜 ( 1 8 ) の 値は、 S l = " e i , S 2 = «r 2 e , , S 3 = 3 e > となる。
こ こで、 再び、 S 1 = R 1， S 2 = R 2 , S 3 = R 3の条件が 成立するか否かを調べる （ステップ S 4 ) 。
も し、 受信したデータのうち 1番目 （ X , ' ) に誤りがあった 場合、 この条件が成立する箬である。 また、 この条件が成立しな かつた場合は、 もう一度、 ステ ッ プ S 6及びステ ッ プ S 7の処理 を実行する。
このようにして、 この計算を j 回行ったとすると、 シ ン ドロ一 厶 レジスタ （ 1 6 ) 〜 （ 1 8 ) の各値は、 S 1 = " j e i , S 2 = « 2 j e i ， S 3 = a 3 J e i となっており、 j が i (誤っている 受信データの番号） と一致したときに、 S 1 = R 1， S 2 = R 2 , S 3 = R 3が成立することがわかる。
つまり、 この計算を何回か繰り返して行い、 ステップ S 4 にお いて、 S 1 = R 1 ， S 2 = R 2 , S 3 = R 3の条件が成立したと 判定し/ことき、 S 1 ≠ 0を条件に （ステ ッ プ S 8 ) 、 カ ウ ンタ （ 2 9 ) のカウ ン ト値 j を誤りが含まれているデータの番号と し、 その誤りの大きさをシ ン ド ロ ーム レジスタ 〔 S 0〕 ( 1 5 ) の値 とする （ステ ッ プ S 9 ) 。
ステップ S 8において、 S 0 = 0 と判定した場合には、 受信デ 一夕に誤りがなかったものとする （ステップ S 1 0 ) 。
また、 ステ ッ プ S 5において、 カ ウ ンタ （ 2 9 ) のカ ウ ン ト値 j が 3 1 を超えても S レジスタ と R レジスタがー致しないと判定 した場合には、 2バイ ト以上のデータが誤っていたとし、 訂正不 能と して処理する （ステップ S 1 1 ) 。
以上詳細に説明したように、 本実施例によれば、 シ ン ド ロ ーム レジスタ S 0， S 1 〜 S ( n— 1 ) によってシ ン ドロ 一厶を計算 し、 その計算終了後、 1重誤りのときシ ン ドロ ーム レジス タ S 0 の値をシ ン ドロ ーム レジス タ S 1 ~ S ( n - 1 ) に、 シ ン ドロ 一 ム レジスタ S 1 〜 S ( n - 1 ) の各値をデータ レジスタ R 1 〜R ( n — 1 ) にそれぞれロ ー ド し、 シ ン ドロ ーム レジス タ S 1 〜 S ( n - 1 ) を用いて《, ·· '·， " -'） のべき乗演算を、 シ ン ド ロ ーム レジスタ S 1 〜 S ( n - 1 ) の各値とデータ レジス タ R l ~ R ( n - 1 ) の各値が一致するまで繰り返すとともに、 そのべ き乗演算に同期してカ ウ ン ト動作を行い、 その一致検出時の力 ゥ ン ト値を誤りが含まれているデータ位置と し、 シ ン ドロ ーム レジ ス タ S 0の値をその誤りの大きさと してエラ一訂正を行うように したので、 シ ン ド 口 一厶の計算に絶対に必要な n個のシ ン ドロ ー 厶 レジス タ に、 （ n— 1 ) 個のデータ レジスタ 、 1個のカ ウ ンタ 及び一致検出回路を付加するだけの極めて小規模な回路構成にて 、 1 重工ラーのエ ラ ー検出及びエラー訂正を実現できることにな る。
なお、 上記実施例では、 シ ン ドロ ームが 4つ （ S 0〜 S 3 ) と なる信号フ ォ ーマツ 卜の C Dの再生装置に適用した場合について 説明したが、 本発明は、 これに限定されることなく、 ディ ジタル • データを処理する装置全般に適用し得るものであり、 例えば、 シ ン ド ロ ームが 6つとなる信号フ ォ ーマ ツ ト の D A Tの再生装置 に適用する場合には、 シ ン ドロ ームの数に応じてシ ン ド ロ ーム レ ジスタ及びデータ レジス タを増やすことで、 同様にして処理でき る o

Claims

請 求 の 範 囲
1. 受信データからこの受信データに付加されるパリティ数で決 まる n ( ri は正の整数） 個のシ ン ドロ ームを計算しかつ 1重誤 りのときその誤りの大きさを表わすシン ドロ 一厶を単一のシン ドロ ーム レジス タ に、 それ以外のシ ン ドロ ームを （ n— 1 ) 個 のシ ン ド ロ 一厶 レジス タ にそれぞれ格納し、
シ ン ド ロ ームの計算終了後、 前記単一のシ ン ドロ 一ム レジス タの値を前記 （ n— 1 ) 個のシ ン ドロ ーム レジスタ に、 前記 （ n - 1 ) 個のシ ン ド ロ ーム レジスタの各値を （ n — 1 ) 個のデ 一夕 レジスタ にそれぞれロー ドし、
ガロア体上の生成多項式の根を"とするとき、 前記 （ n— 1 ) 個のシ ン ドロ ーム レジス タを用いて《， ——， " - 1 ) のべ き乗演算を前記 （ n— 1 ) 個のシ ン ドロ ーム レジスタの各値と 前記 （ n— 1 ) 個のデータ レジスタの各値の一致を検出するま で繰り返すとともに、 べき乗演算に同期してカ ウ ン ト動作を行 い、
前記一致の検出時点のカ ウ ン ト値を誤りが含まれているデー タ位置とするとともに、 前記単一のシ ン ドロ ームレジスタの値 を誤りの大きさと し、
前記データ位置及び前記誤りの大きさに基づいてエラ一訂正 を行う ことを特徴とするエラ一訂正方法。
2. 請求項 1 記載のエラー訂正方法を用いたエラー訂正回路であ つて、
受 i言データからシ ン ド ロ ームを計算しかつ 1重誤りのときそ の誤りの大きさを表わすシ ン ドロ ームを格納する単一のシ ン ド ローム レジス タ及びそれ以外のシ ン ドロームを格納する （ π — 1 ) 個のシ ン ド ロ ーム レジス タ力、らなるシ ン ドロ一厶 レジス タ 群と、 前記 （ n — 1 ) 個のシ ン ド□ —ム レジス夕に格納された各値 を保持する （ η — 1 ) 個のデータ レジスタ と、
前記 （ n — 1 ) 個のシ ン ドロ ーム レジスタの各値と前記 （ η 一 1 ) 個のデータ レジス タの各値が一致したことを検出する一 致検出回路と、
前記べき乗演算に同期してカ ウ ン ト動作を行うとともに、 前 記一致検出回路の検出出力に応答して力ゥ ン ト動作を停止する カウンタとを具備し、
前記力 ゥ ンタのカ ウ ン ト値及び前記単一のシ ン ドロ 一ム レジ ス タの値に基づいてェラ一訂正を行う ことを特徴とするェラ一 訂正回路。
PCT/JP1993/001854 1992-12-25 1993-12-22 Procede et circuit de correction d'erreurs Ceased WO1994015406A1 (fr)

Priority Applications (3)

Application Number Priority Date Filing Date Title
US08/290,886 US5541940A (en) 1992-12-25 1993-12-22 Error correction method and error correction circuit
EP94903038A EP0629052B1 (en) 1992-12-25 1993-12-22 Method of and circuit for correcting errors
DE69325900T DE69325900T2 (de) 1992-12-25 1993-12-22 Verfahren und schaltung zur fehlerkorrektur

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP35825692A JP3170920B2 (ja) 1992-12-25 1992-12-25 エラー訂正方法及び訂正回路
JP4/358256 1992-12-25

Publications (1)

Publication Number Publication Date
WO1994015406A1 true WO1994015406A1 (fr) 1994-07-07

Family

ID=18458349

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP1993/001854 Ceased WO1994015406A1 (fr) 1992-12-25 1993-12-22 Procede et circuit de correction d'erreurs

Country Status (6)

Country Link
US (1) US5541940A (ja)
EP (1) EP0629052B1 (ja)
JP (1) JP3170920B2 (ja)
KR (1) KR100253043B1 (ja)
DE (1) DE69325900T2 (ja)
WO (1) WO1994015406A1 (ja)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100234400B1 (ko) * 1997-01-17 1999-12-15 윤종용 디지탈 비디오 디스크 시스템의 에러 정정 장치 및 방법
US7395468B2 (en) * 2004-03-23 2008-07-01 Broadcom Corporation Methods for debugging scan testing failures of integrated circuits
US7581150B2 (en) 2004-09-28 2009-08-25 Broadcom Corporation Methods and computer program products for debugging clock-related scan testing failures of integrated circuits
US7500165B2 (en) 2004-10-06 2009-03-03 Broadcom Corporation Systems and methods for controlling clock signals during scan testing integrated circuits
US20060080583A1 (en) * 2004-10-07 2006-04-13 International Business Machines Corporation Store scan data in trace arrays for on-board software access
US7627798B2 (en) * 2004-10-08 2009-12-01 Kabushiki Kaisha Toshiba Systems and methods for circuit testing using LBIST
US7804599B2 (en) * 2008-07-24 2010-09-28 MGM Instruments, Inc. Fluid volume verification system
US10601448B2 (en) * 2017-06-16 2020-03-24 International Business Machines Corporation Reduced latency error correction decoding

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS62137924A (ja) * 1985-12-12 1987-06-20 Nec Home Electronics Ltd リ−ドソロモン符号・復号方式の誤り位置決定回路
JPH0429414A (ja) * 1990-05-25 1992-01-31 Natl Sci Council サイクリックコードのステップ・バイ・ステップ型復号方法及び復号器

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4312069A (en) * 1980-02-07 1982-01-19 Bell Telephone Laboratories, Incorporated Serial encoding-decoding for cyclic block codes
CA1196106A (en) * 1982-04-28 1985-10-29 Tsuneo Furuya Method and apparatus for error correction
US4488302A (en) * 1983-02-11 1984-12-11 At&T Bell Laboratories Burst error correction using cyclic block codes
US4555784A (en) * 1984-03-05 1985-11-26 Ampex Corporation Parity and syndrome generation for error detection and correction in digital communication systems
KR910005644B1 (ko) * 1986-09-19 1991-08-01 가부시키가이샤 도시바 디스크재생장치
FR2628862B1 (fr) * 1988-03-17 1993-03-12 Thomson Csf Multiplieur-additionneur parametrable dans les corps de galois, et son utilisation dans un processeur de traitement de signal numerique
EP0341862B1 (en) * 1988-05-12 1996-01-10 Quantum Corporation Error location system
US5099484A (en) * 1989-06-09 1992-03-24 Digital Equipment Corporation Multiple bit error detection and correction system employing a modified Reed-Solomon code incorporating address parity and catastrophic failure detection

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS62137924A (ja) * 1985-12-12 1987-06-20 Nec Home Electronics Ltd リ−ドソロモン符号・復号方式の誤り位置決定回路
JPH0429414A (ja) * 1990-05-25 1992-01-31 Natl Sci Council サイクリックコードのステップ・バイ・ステップ型復号方法及び復号器

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP0629052A4 *

Also Published As

Publication number Publication date
EP0629052B1 (en) 1999-08-04
EP0629052A1 (en) 1994-12-14
JPH06197025A (ja) 1994-07-15
JP3170920B2 (ja) 2001-05-28
KR100253043B1 (ko) 2000-05-01
DE69325900T2 (de) 2000-02-17
KR940015980A (ko) 1994-07-22
US5541940A (en) 1996-07-30
EP0629052A4 (en) 1995-11-29
DE69325900D1 (de) 1999-09-09

Similar Documents

Publication Publication Date Title
US5805799A (en) Data integrity and cross-check code with logical block address
US20080282128A1 (en) Method of Error Correction Code on Solid State Disk to Gain Data Security and Higher Performance
US5778009A (en) Dedicated ALU architecture for 10-bit Reed-Solomon error correction module
JPH0444447B2 (ja)
CN101473308A (zh) 非易失性存储器纠错系统和方法
JPH02211723A (ja) セクタ内の訂正不可能な誤りの発生の信号を送るための装置および方法
JPH0831806B2 (ja) エラー訂正方法
WO1994015406A1 (fr) Procede et circuit de correction d'erreurs
JP2605966B2 (ja) 誤り訂正回路
JPH10322226A (ja) リードソロモン復号方法
JP2691973B2 (ja) 単一誤り訂正および多重誤り検出ｂｃｈ符号の復号装置
JPS6161188B2 (ja)
JPH0344394B2 (ja)
JP3280470B2 (ja) 誤り訂正回路
JP3583905B2 (ja) 誤り訂正装置
JP3135552B2 (ja) リードソロモン符号の誤り検出及び訂正装置
JPH0351008B2 (ja)
RU2007040C1 (ru) Устройство для декодирования кода рида - соломона
KR100246342B1 (ko) 리드솔로몬오류수정장치
JP2553571B2 (ja) ガロア体演算装置
JP2775432B2 (ja) 誤り訂正／誤り検出／消失誤り訂正を同時に行うリード・ソロモン符号の復号装置
JPH07230388A (ja) 誤り訂正方法及び装置
JPH0445015B2 (ja)
JPH0133055B2 (ja)
JPS62250723A (ja) 誤り訂正回路

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE

WWE Wipo information: entry into national phase

Ref document number: 1994903038

Country of ref document: EP

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 08290886

Country of ref document: US

WWP Wipo information: published in national office

Ref document number: 1994903038

Country of ref document: EP

WWG Wipo information: grant in national office

Ref document number: 1994903038

Country of ref document: EP