EP0426657A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus for decoding error correction code
Assignee: Sony Corp
•
Filing: 1984-12-19
•
Granted: —
•
Expires: 2004-12-19
Abstract
Abstract In method for decoding error correction code in which a first correction code of (ni, ki) (where n 1 denotes the code length) is encoded for every k, information symbols arranged in each column and a second error correction code of (n 2 , k 2 ) (where n 2 denotes the code length) are encoded for every k 2 information symbols arranged in each row of a two dimentional arrangement of (k 1 X k 2 ), a first pointer formed by decoding the first error correction code is stored in a memory having n 2 bits, a second pointer formed by decoding the second error correction code is stored in a memory having k 2 bits. When the second error correction code is decoded, an erasure correction is made with respect to each of the code series of the second error correction code by employing the first pointer and a part of the calculation for obtaining an error value in this erasure correction may be carried out only once with respect to each of the code series of the second error correction code.
Inventors
- 👤 Shinya Ozaki
- 👤 Kentaro Odaka
- 👤 Tadashi Fukami
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 10:17
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151; H03M13/158; H03M13/1525; H03M13/29; H03M13/2903; H03M13/2906; H03M13/2909; H03M13/2927; H03M13/293; H03M13/1515
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
301 words
A method for decoding error correction code in which respective first error correction codes of (ni, ki) (where n, denotes the code length) are encoded for every k 1 information symbols arranged in respective columns of a two dimensional arrangement of (ki x k 2 ) and respective second error correction codes of (n 2 , k 2 ) (where n 2 denotes the code length) are encoded for every k 2 information symbols arranged in respective rows of the two dimensional arrangements the method comprising the steps of: receiving at least the respective first error correction codes; first decoding the respective first error correction codes; generating respective first pointers for indicating error detection or correction status of respective first error correction codes; storing the respective first pointers in memory means (13) having at least n 2 bits; second decoding the respective second error correction codes by implementing an erasure correction for each code series of the second error correction codes by employing the respective first pointers; and outputting the information symbols; characterised in that the step of second decoding includes a step of calculating error values of erasure symbols by an algebraic expression consisting of a first term to be a common value and a second term to be individually independent values with respect to the erasure error corrections of the respective second error correction codes and the step of calculating error values includes implementing a first calculation of the first term only once corresponding to each of the respective first pointers; storing the result of the first calculation of the first term; and implementing each of the calculations for obtaining error values corresponding to the respective second error correction codes by each of second calculations of the second term and by using the stored result of the first calculation.
Claim 2
Independent Claim
301 words
A method for decoding error correction code in which respective first error correction codes of (ni, ki) (where n, denotes the code length) are encoded for every k 1 information symbols arranged in respective columns of a two dimensional arrangement of (ki x k 2 ) and respective second error correction codes of (n 2 , k 2 ) (where n 2 denotes the code length) are encoded for every k 2 information symbols arranged in respective rows of the two dimensional arrangements the method comprising the steps of: receiving at least the respective first error correction codes; first decoding the respective first error correction codes; generating respective first pointers for indicating error detection or correction status of respective first error correction codes; storing the respective first pointers in memory means (13) having at least n 2 bits; second decoding the respective second error correction codes by implementing an erasure correction for each code series of the second error correction codes by employing the respective first pointers; and outputting the information symbols; characterised in that the step of second decoding includes a step of calculating error values of erasure symbols by an algebraic expression consisting of a first term to be a common value and a second term to be individually independent values with respect to the erasure error corrections of the respective second error correction codes and the step of calculating error values includes implementing a first calculation of the first term only once corresponding to each of the respective first pointers; storing the result of the first calculation of the first term; and implementing each of the calculations for obtaining error values corresponding to the respective second error correction codes by each of second calculations of the second term and by using the stored result of the first calculation.
Claim 3
Independent Claim
354 words
An apparatus for decoding error correction code in which respective first error correction codes of (ni, k i ) (where n1 denotes the code length) are encoded for every k, information symbols arranged in respective columns of a two dimensional arrangement of (k, x k 2 ) and respective second error correction codes of (n 2 , k 2 ) (where n 2 denotes the code length) are encoded for every k 2 information symbols arranged in respective rows of the two dimensional arrangement, the apparatus comprising: receiving and output means (28) for receiving at least the respective first error correction codes and for deriving the information symbols; decoding means (12, 14, 16, 29, 33, 34, 35, 36, 37) connected to said receiving and output means (28) and for first decoding the respective first error correction codes and for generating respective first pointers for indicating error correction or detection status of respective first error correction codes and for second decoding the respective second error correction codes by implementing an erasure correction for each code series of the respective second error correction codes by employing the respective first pointers; and memory means (13) connected to said decoding means (29, 33 - 37) and having a capacity of at least n 2 bits for storing the respective first pointers; characterised in that said decoding means (12, 14, 16, 29, 33-37) calculates in said second decoding error values of erasure symbols by an algebraic expression consisting of a first term to be a common value and a second term to be individually independent values with respect to the erasure error corrections of the respective second error correction codes and said decoding means (12, 13, 16; 29, 33, 34, 35, 36, 37) implements a first calculation of the first term only once corresponding to each of the respective first pointers, stores the result of the first calculation of the first term and implements each of the calculations for obtaining error values corresponding to the respective second error correction codes by each of second calculations of the second term and by using the stored result of the first calculation.
Claim 4
Independent Claim
354 words
An apparatus for decoding error correction code in which respective first error correction codes of (ni, k i ) (where n1 denotes the code length) are encoded for every k, information symbols arranged in respective columns of a two dimensional arrangement of (k, x k 2 ) and respective second error correction codes of (n 2 , k 2 ) (where n 2 denotes the code length) are encoded for every k 2 information symbols arranged in respective rows of the two dimensional arrangement, the apparatus comprising: receiving and output means (28) for receiving at least the respective first error correction codes and for deriving the information symbols; decoding means (12, 14, 16, 29, 33, 34, 35, 36, 37) connected to said receiving and output means (28) and for first decoding the respective first error correction codes and for generating respective first pointers for indicating error correction or detection status of respective first error correction codes and for second decoding the respective second error correction codes by implementing an erasure correction for each code series of the respective second error correction codes by employing the respective first pointers; and memory means (13) connected to said decoding means (29, 33 - 37) and having a capacity of at least n 2 bits for storing the respective first pointers; characterised in that said decoding means (12, 14, 16, 29, 33-37) calculates in said second decoding error values of erasure symbols by an algebraic expression consisting of a first term to be a common value and a second term to be individually independent values with respect to the erasure error corrections of the respective second error correction codes and said decoding means (12, 13, 16; 29, 33, 34, 35, 36, 37) implements a first calculation of the first term only once corresponding to each of the respective first pointers, stores the result of the first calculation of the first term and implements each of the calculations for obtaining error values corresponding to the respective second error correction codes by each of second calculations of the second term and by using the stored result of the first calculation.
Claim 5
Dependent Claim
111 words
An apparatus according to claim 2 wherein said decoding means (12, 14, 16, 29, 33-37) comprises first decoding means (12, 14) connected to said receiving means (11) for said first decoding, and second decoding means (16, 14) connected to said first decoding means (12, 14) and said memory means (13) for said second decoding, and said apparatus further comprises store means for storing the result of the first calculation of the said first term and implements each of the calculations for obtaining error values corresponding to the respective second error correction codes by each of second calculations of the second term and by using the stored result of the first calculation.
Claim 6
Dependent Claim
233 words
Apparatus according to claim 2 or 3, for decoding a non-dualistic error correction code in which one of a plurality of syndromes is a result of an addition of a series of received symbols in (mod. 2) and by which errors of a plurality of symbols in the series of received symbols, can be corrected, wherein the decoding means (12, 16, 14; 28, 29, 33, 34, 35, 36, 37) further comprises input means (21, 22; 28), syndrome generation means (23; 36, 37) for generating the syndromes, error location and error value calculation means (24, 29, 36, 37) connected to said syndrome generation means (23; 36, 37) and for generating error locations and error values according to the syndromes, error correction means (25; 37) connected to said input means (21, 22; 28) and error location and error value calculation means (24; 29, 36, 37) and for correcting an erroneous symbol by adding the error value and output means (26, 27; 28) connected to said error correction means (25; 37), said error location and error value calculation means (24; 29, 36, 37) including a syndrome register (29) for storing the syndromes, and exclusive-OR gate (31) connected to said syndrome register (29) and supplied with the syndrome and error values and for adding error values to the syndrome so as to generate an error value stored in said syndrome register (29) for correcting an erroneous symbol.
Claim 7
Dependent Claim
126 words
A method according to claim 1 further comprising the steps, for decoding and correcting Reed = Solomon code of: solving the expression where, ν = 0 to d - 2 n : Number of erasure X k : Location of kth element S ν : Syndrome Y k : Magnitude of error in the erasure of kth element d : Minimum distance of code to obtain roots of the expression; making erasure correction of errors encoded in the Reed = Solomon code in accordance with the roots, characterized in that; the roots are obtained by solving the expression where A nij : Coefficient of Z j of t : Any integer more than or equal to 0 which satisfies t < d - n - 1.
Claim 8
Dependent Claim
224 words
Apparatus according claims 2, 3 or 4 for decoding and correcting erasure in Reed-Solomon code in accordance with the roots of where, ν = 0 to d - 2 n : Number of erasure X k : Location of kth element S ν : Syndrome Y k : Magnitude of error in the erasure of kth element d : Minimum distance of the code wherein said decoding means (12, 14, 16; 28, 29, 33-37) further comprises syndrome register means (29) for storing syndrome S ν ; and operating logic means (37) for obtaining the roots Y i by solving the expression: where A nij : Coefficient of Z j of ℓ : Any integer more than or equal to 0 which satisfies ℓ ≦ d - n - 1 said operating logic means (37) including register means (38) for storing syndrome S ν ; register means (39) for storing X 1 ν Y i ; register means (40) for storing X i ; adder means (41) for adding S ν and X i ν Y i and for supplying said register means (38) and syndrome register means (29) with S ν +X i ν Y i ; multiplyer means (42) for multiplying X i and X i " Y i and for supplying said register means (3) with X i ν Y i .
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.