EP0129849A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Error correction method and system
Assignee: Hitachi Ltd
•
Filing: 1984-06-20
•
Granted: —
•
Expires: 2004-06-20
Abstract
Abstract This invention relates to an error correction upon reproduction of digital signals. The error correction is performed by decoding code words such as cross-interleaved Reed Solomon codes, in which first code blocks are formed by a plurality of information words which are in the first arrangement state and a plurality of first check words which are produced by codes associated with the plurality of information words with a Hamming distance of d,, and second code blocks are formed by a plurality of information words and a plurality of first check words which are in the second arrangement state and which consist of the said plurality of information words and the said plurality of first check words which are respectively included in the different first code blocks, and by a plurality of second check words which are produced by codes associated with the plurality of information words and the plurality of first check words with a Hamming distance of d 2 . At the first decoding stage, at least errors are detected and at the same time the flags indicative of the decoding states are i added with respect to the second code blocks. At the second decoding stage, in accordance with the contents of the flags and on the basis of a combination of p 2 and q selected from their combinations satisfying 2p 2 +q≤d 1 -1, errors are detected and errors of p 2 words are corrected and erasures of q words to which the flags were added are corrected with respect to the first code blocks.
Inventors
- 👤 Hiroo Okamoto
- 👤 Masaharu Hitachi-Hachimanyama Kobayashi
- 👤 Keizo Nishimura
- 👤 Takaharu Noguchi
- 👤 Takao Arai
- 👤 Toshifumi Shibuya
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 16:23
CPC Classifications
G; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1806; G11B20/1809
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
215 words
An error correcting method of decoding code words, wherein first code blocks are formed by a plurality of information words in a first arrangement state and a plurality of first check words produced by codes associated with said plurality of information words with a Hamming distance of d 1 , and second code blocks are formed by a plurality of information words and a plurality of first check words in a second arrangement state and including said plurality of information words and said plurality of first check words which are respectively included in the different first code blocks and by a plurality of second check words which are produced by codes associated with said plurality of information words and said plurality of first check words with a Hamming distance of d 2 , comprising the steps of: (a) as a first decoding, at least detecting errors and at the same time adding flags indicative of the decoding states; and (b) as a second decoding, detecting errors and correcting, on the basis of a combination of p 2 and q selected from their combinations satisfying 2P 2 + q S d 1 - 1, errors of P2 words and erasures of q words to which said flags were added with respect to said first code blocks.
Claim 2
Dependent Claim
215 words
An error correcting method of decoding code words, wherein first code blocks are formed by a plurality of information words in a first arrangement state and a plurality of first check words produced by codes associated with said plurality of information words with a Hamming distance of d 1 , and second code blocks are formed by a plurality of information words and a plurality of first check words in a second arrangement state and including said plurality of information words and said plurality of first check words which are respectively included in the different first code blocks and by a plurality of second check words which are produced by codes associated with said plurality of information words and said plurality of first check words with a Hamming distance of d 2 , comprising the steps of: (a) as a first decoding, at least detecting errors and at the same time adding flags indicative of the decoding states; and (b) as a second decoding, detecting errors and correcting, on the basis of a combination of p 2 and q selected from their combinations satisfying 2P 2 + q S d 1 - 1, errors of P2 words and erasures of q words to which said flags were added with respect to said first code blocks.
Claim 3
Dependent Claim
29 words
An error correcting method according to claim 1, wherein said at least detecting errors includes detecting errors and correcting p 1 words satisfying 2p 1 ≦ d 2 -1.
Claim 4
Dependent Claim
45 words
An error correcting method according to claim 1, wherein the number q of said correction words to which said flags were added is varied in accordance with the number of said flags included in said first code blocks which are subjected to said second decoding.
Claim 5
Dependent Claim
286 words
A system for correcting errors by the error correcting method according to claim 1, comprising: (a) a syndrome generating circuit (20, 133) for producing syndromes in response to an input signal; (b) an arithmetic logic circuit (24, 135) for performing the multiplication, division and addition over the Galois field using values of said syndromes produced by said syndrome generating circuit (20, 133) or using the values of said syndromes and the locations of the words to which said flags were added; (c) converters (136, 137, 138) for obtaining i from α i and/or obtaining α i from i with respect to arbitrary elements a i over the Galois field; (d) a counter (26, 140) for counting the numbers of said plurality of kinds of flags which were added to the respective words input; (e) memories (116, 118, 134, 139, 141, 143) for storing the values of said syndromes, the result of the arithmetic operation by said arithmetic logic circuit (24, 135), the result of the conversion by said converters (136, 137, 138), the numbers of flags counted by the location counter (26, 140) for the input words to which said flags were added, and the flags added to said input signal; (f) a program memory (31, 146) in which a program has been stored, by which program said arithmetic logic circuit (24, 135), said converters (136, 137, 138) and said memories (116, 118, 134, 139, 141, 143) are controlled, thereby to perform the error correcting operation and addition of flags in said first decoding; and (g) a control circuit (121, 144) for controlling the address of said program memory (31, 146) in accordance with said program and the states of said flags added, and the like.
Claim 6
Dependent Claim
381 words
An error correcting system for decoding error correcting codes produced over the Galois field GF (2 m ) in which the code length is n words and the number of information words is (n - k) and the number of check words is k, comprising: (a) a syndrome generating circuit (133) for producing k syndromes in response to an input signal; (b) an arithmetic logic circuit (135) for performing the multiplication, division and addition over the Galois field using values of said syndromes produced by said syndrome generating circuit (133) or using the values of the syndromes and the locations of the words to which flags were added; (c) converters (136, 137, 138) for obtaining i from α i and/or obtaining a i from i with respect to arbitrary elements a i over the Galois field; (d) a counter (140) for counting the numbers of a plurality of kinds of flags which were added to the respective words input; (e) a plurality of memories (134, 139, 141, 143) for storing the values of said syndromes, the result of the arithmetic operation by said arithmetic logic circuit (135), the result of the conversion by said converters (136, 137, 138), the numbers of flags counted by said counter (140), and the flags added to said input signal; (f) a comparator (142) for comparing the numbers of flags counted by said counter (140), the result of the arithmetic operation by said arithmetic logic circuit (135) and the result of the conversion by said converters (136, 137, 138) with predetermined numbers; (g) a program memory (146) in which a program has been stored, by which program said arithmetic logic circuit (135), said converters (136, 137, 138), said memories (134, 139, 141, 143), and said comparator (142) are controlled, thereby to perform the error correcting operation and addition of flags; (h) a control circuit (145, 147, 148) for controlling the address of said program memory (146) in accordance with said program and the states of said flags added, and the like; and (i) a control circuit (144) which controls said syndrome generating circuit (133), said counter (140) and said memories (139, 143) for storing the flags added to said input signal and which performs the operation to input the data independently of the error correcting operation.
Claim 7
Dependent Claim
381 words
An error correcting system for decoding error correcting codes produced over the Galois field GF (2 m ) in which the code length is n words and the number of information words is (n - k) and the number of check words is k, comprising: (a) a syndrome generating circuit (133) for producing k syndromes in response to an input signal; (b) an arithmetic logic circuit (135) for performing the multiplication, division and addition over the Galois field using values of said syndromes produced by said syndrome generating circuit (133) or using the values of the syndromes and the locations of the words to which flags were added; (c) converters (136, 137, 138) for obtaining i from α i and/or obtaining a i from i with respect to arbitrary elements a i over the Galois field; (d) a counter (140) for counting the numbers of a plurality of kinds of flags which were added to the respective words input; (e) a plurality of memories (134, 139, 141, 143) for storing the values of said syndromes, the result of the arithmetic operation by said arithmetic logic circuit (135), the result of the conversion by said converters (136, 137, 138), the numbers of flags counted by said counter (140), and the flags added to said input signal; (f) a comparator (142) for comparing the numbers of flags counted by said counter (140), the result of the arithmetic operation by said arithmetic logic circuit (135) and the result of the conversion by said converters (136, 137, 138) with predetermined numbers; (g) a program memory (146) in which a program has been stored, by which program said arithmetic logic circuit (135), said converters (136, 137, 138), said memories (134, 139, 141, 143), and said comparator (142) are controlled, thereby to perform the error correcting operation and addition of flags; (h) a control circuit (145, 147, 148) for controlling the address of said program memory (146) in accordance with said program and the states of said flags added, and the like; and (i) a control circuit (144) which controls said syndrome generating circuit (133), said counter (140) and said memories (139, 143) for storing the flags added to said input signal and which performs the operation to input the data independently of the error correcting operation.
Claim 8
Dependent Claim
78 words
An arithmetic logic circuit for performing the division of dividend X by divisor Y over the Galois field GF (2 m ) , comprising: a converter (211) for outputting the reciprocal number of Y over the Galois field GF (2 m ) when Y is inputted and a multiplier (212) for performing the multiplication over the Galois field GF (2 m ) of X and the reciprocal number of Y which is outputted from said converter (211) .
Claim 9
Dependent Claim
78 words
An arithmetic logic circuit for performing the division of dividend X by divisor Y over the Galois field GF (2 m ) , comprising: a converter (211) for outputting the reciprocal number of Y over the Galois field GF (2 m ) when Y is inputted and a multiplier (212) for performing the multiplication over the Galois field GF (2 m ) of X and the reciprocal number of Y which is outputted from said converter (211) .
Claim 10
Dependent Claim
154 words
An arithmetic logic circuit for performing the arithmetic operation over the Galois field GF (2 m ), comprising: a converter (211) to obtain the reciprocal number of an input Y over the Galois field GF (2 m ); an MPX circuit (214) to select either one of the input Y and the reciprocal number of Y which is the output of said converter (211); a multiplier (212) to perform the multiplication over the Galois field GF (2 m ) of the input X and the output of said MPX circuit (214), said multiplier (212) performing the multiplication of X and Y when Y is selected by the MPX circuit (214) and the division of dividend X by divisor Y when the reciprocal number of Y is selected; and an adder (215) for performing the addition over the Galois field GF (2 m ) of the output of said multiplier (212) and an input Z.
Claim 11
Dependent Claim
154 words
An arithmetic logic circuit for performing the arithmetic operation over the Galois field GF (2 m ), comprising: a converter (211) to obtain the reciprocal number of an input Y over the Galois field GF (2 m ); an MPX circuit (214) to select either one of the input Y and the reciprocal number of Y which is the output of said converter (211); a multiplier (212) to perform the multiplication over the Galois field GF (2 m ) of the input X and the output of said MPX circuit (214), said multiplier (212) performing the multiplication of X and Y when Y is selected by the MPX circuit (214) and the division of dividend X by divisor Y when the reciprocal number of Y is selected; and an adder (215) for performing the addition over the Galois field GF (2 m ) of the output of said multiplier (212) and an input Z.
Claim 12
Dependent Claim
42 words
An arithmetic logic circuit over the Galois field according to claim 6, further comprising an ROM or PLA which outputs the reciprocal number of Y over the Galois field GF (2 m ) when the input Y is used as the address.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.