Error correction method and apparatus based on two-dimensional code array with reduced redundancy

• US 5,719,884 A
• Filed: 07/27/1995
• Issued: 02/17/1998
• Est. Priority Date: 07/27/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Roth, Ron M., Seroussi, Gadiel
• Primary Examiner(s): Elmore, Reba I.
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US08/508,019
• Time in Patent Office: 936 Days
• Field of Search: 371/37.1, 371/37.4, 371/37.5, 371/37.7, 365/130, 365/129
• US Class Current: 714/755
• CPC Class Codes: H03M 13/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/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 13/2903 Methods and arrangements specifically for encoding, e.g. parallel encoding of a plurality of constituent codes
• CPC Class Codes: H03M 13/2909 Product codes
• CPC Class Codes: H03M 13/293 with erasure setting

Abstract

An error correction system reduces redundancy of a two-dimensional product code array by eliminating an excess redundancy in prior product codes that provides detection of more corrupted rows than can be corrected. The product code array is formed utilizing a row coding, a column coding, and an intermediate coding, which may each be Reed-Solomon codes. The product code array has a total redundancy of n₁ r₂ +r₁ r₂ symbols, where r₁ is the redundancy of the row coding, r₂ is the redundancy of the column coding, and raw data symbols fill a k₁ by k₂ and a r₁ by (k₂ -r₂) symbol portions of the product code array. A decoder for the product code array is capable of detecting and correcting up to r₂ corrupted rows of the product code array.

Claims

1. A method of reducing redundancy in an error correcting system having a data source, a data sink, and a channel which transfers data from the data source to the data sink, the method comprising:

encoding columns in a first block of raw data symbols at the data source in an n₁ by n₂ symbol product code array, into an array of column code checks;

encoding rows of raw data symbols from the first block combined with rows of a second block of raw data symbols and rows of the column code checks into an array of row code checks;

encoding columns for a first portion of the row code checks into an intermediate column code checks;

combining the intermediate column code checks with a second portion of the row code checks thereby forming a reduced row code checks derived from both first and second raw data block and the column code checks;

forming a reduced redundancy product code array including the first and second block of raw data symbols the column code checks for the first raw data block and the reduced row code checks the reduced redundancy product code array having a redundancy of n₁ r₂ +r₁ r₂ symbols, whereby up to r₂ corrupted rows of the array can be detected and up to r₂ erasures in each column corrected, wherein n₁, n₂, r₁, and r₂ are positive integers and each symbol is taken from an alphabet having an integer number q of symbols;

transmitting the reduced redundancy product code array on the communications channel to the destination; and

decoding the reduced redundancy product code array at the destination to recover the raw data symbols.

2. The method of claim 1 wherein the communications channel is a bursty noise channel.

3. The method of claim 1 wherein the step of decoding comprises:

processing the reduced redundancy product code array and the redundancy to identify corrupted rows of the reduced redundancy product code array whereby a probability of identifying and correcting the corrupted rows is substantially the same as that of a non-reduced redundancy product code array having a redundancy of n₁ r₂ +n₂ r₁ -r₁ r₂ ; and

processing the reduced redundancy product code array and the redundancy to correct those rows of the reduced redundancy product code array identified as corrupted.

4. The method of claim 1 wherein the step of encoding raw data symbols comprises encoding the raw data symbols with a column code of redundancy r₂, a row code of redundancy r₁, and an intermediate code of redundancy 2r₂, where the intermediate code is a subcode of the column code.

5. The method of claim 1 wherein the step of encoding comprises:

filling a first portion and a second portion of the reduced redundancy product code array with raw data symbols, the first and second portions of the reduced redundancy product code array having dimensions k₁ by k₂ symbols and r₁ by k₂ -r₂ symbols, respectively, wherein k₁ and k₂ are integers;

processing columns of the first portion of the reduced redundancy product code array according to a first coding to form first coding checks of length r₂ symbols associated one to one to the columns of the first portion;

filling a third portion of the reduced redundancy product code array with the first coding checks, the third portion of the reduced redundancy product code array having dimensions k₁ and r₂ symbols;

processing rows of a fourth portion of the reduced redundancy product code array according to a second coding to form second coding checks of length r₁ symbols associated one to one to the processed rows of the fourth portion of the reduced redundancy product code array, the fourth portion of the reduced redundancy product code array having dimensions of k₁ by 2r₂ symbols and consisting of the third portion of the reduced redundancy product code array and a first sub-portion of the first portion of the reduced redundancy product code array, the first sub-portion of the first portion of the reduced redundancy product code array having dimensions k₁ by r₂ symbols, the second coding checks forming a second checks array having dimensions r₁ by 2r₂ symbols;

processing rows of a fifth portion of the reduced redundancy product code array according to the second coding to form third coding checks of length r₁ symbols associated one to one to the rows of the fifth portion of the reduced redundancy product code array, the fifth portion of the reduced redundancy product code array having dimensions n₁ by n₂ -2r₂ and consisting of the second potion of the reduced redundancy product code array and a second sub-potion of the first potion of the reduced redundancy product code array, the second sub-portion of the first portion of the reduced redundancy product code array having dimensions k₁ by n₂ -2r₂, the third coding checks forming a third checks array having dimensions r₁ by n₂ -2r₂ ;

processing columns of the third checks array according to a third coding to form fourth coding checks of length 2r₂ associated one to one to the columns of the third checks array, the fourth coding checks forming a fourth checks array having dimensions r₁ by 2r₂ ;

summing the fourth checks array with the second checks array; and

filling a sixth portion of the reduced redundancy product code array with the sum of the fourth cheeks array and the portion of the second checks array.

6. The method of claim 5 wherein the first through fourth coding checks constitute Reed-Solomon codes.

7. The method of claim 5 wherein the third coding is a subcode of the first coding.

8. The method of claim 5 wherein the step of decoding comprises:

processing rows of the reduced redundancy product code array according to the second coding to form a syndrome array of dimensions r₁ by n₂ ;

processing at least one column of the syndrome array according to the third coding to identify up to r₂ corrupted rows of the reduced redundancy product code array for erasure; and

processing columns of the reduced redundancy product code array according to the first coding to correct those rows identified for erasure.

9. The method of claim 1 wherein the step of decoding comprises:

processing rows of the reduced redundancy product code array according to a second coding of redundancy r₁ to form a syndrome array of dimensions r₁ by n₂ symbols;

processing at least one column of the syndrome array according to a third coding of redundancy 2r₂ to identify up to r₂ corrupted rows of the reduced redundancy product code array for erasure; and

processing columns of the reduced redundancy product code array according to a first coding of redundancy r₂ to correct those rows identified for erasure.

10. The method of claim 1 wherein the step of encoding comprises:

in the reduced redundancy product code array, filling columns one through n₁ of rows one through n₂ -2r₂ and columns one through k₁ of rows n₂ -2r₂ +1 through n₂ -r₂ with raw data symbols;

forming first column coding checks for the raw data symbols in rows one through k₂ of columns one through k₁ of the reduced redundancy product code array, wherein the first column checks are associated one-to-one with the columns and each has length r₂ ;

in the reduced redundancy product code array, filling columns one through k₁ of rows n₂ -r₂ +1 through n₂ with the first column coding checks;

forming partial row coding checks for the raw data symbols and first column coding checks in columns one through k₁ of rows n₂ -2r₂ +1 through n₂ of the reduced redundancy product code array, wherein the partial row coding checks are associated one-to-one with the rows and each has length r₁ ;

saving the partial row coding checks associated with rows n₂ -2r₂ +1 through n₂ of the reduced redundancy product code array;

forming complete row coding checks for the raw data symbols in columns one through n₁ of rows one through n₂ -2r₂ of the reduced redundancy product code array, wherein the complete row coding checks are associated one-to-one with the rows and each has length r₁ ;

forming second column coding checks for columns of the complete row coding checks, wherein the second column coding checks are associated one-to-one with the columns and each has length 2r₂ ;

summing the saved partial row coding checks and the second column coding checks; and

in the reduced redundancy product code array, filling columns k₁ +1 through n₁ of rows n₂ -2r₂ +1 through n₂ with the summed partial row coding checks and second column coding checks.

11. The method of claim 10 wherein the coding checks all constitute Reed-Solomon codes.

12. The method of claim 10 wherein the step of decoding comprises:

forming row syndromes for the raw data symbols and checks in columns 1 through n₁ of rows 1 through n₂ of the reduced redundancy product code array, wherein the row syndromes are associated one-to-one with the rows of the reduced redundancy product code array and each has length r₁, the row syndromes forming a row syndrome array having dimensions r₁ by n₂ ;

forming at least one first column syndrome of at least one column of the row syndrome array, wherein the at least one first column syndrome is associated one-to-one to the at least one column of the row syndrome array and each first column syndrome has length 2r₂ ;

using the at least one column syndrome to identify corrupted rows of the reduced redundancy product code array;

forming second column syndromes for the raw data symbols and checks in rows 1 through n₂ of columns 1 through n₁ of the reduced redundancy product code array, wherein the second column syndromes are associated one-to-one to the columns of the reduced redundancy product code array and each has length r₂ ; and

using the second column syndromes to correct erasure of the corrupted rows of the reduced redundancy product code array.

13. The method of claim 1 wherein the step of decoding comprises:

forming row syndromes of columns 1 through n₁ of rows 1 through n₂ of the reduced redundancy product code array, wherein the row syndromes are associated one-to-one with the rows of the reduced redundancy product code array and each has length r₁, the row syndromes forming a row syndrome array having dimensions r₁ by n₂ ;

forming at least one first column syndrome of at least one column of the row syndrome array, wherein the at least one first column syndrome is associated one-to-one to the at least one column of the row syndrome array and each first column syndrome has length 2r₂ ;

using the at least one first column syndrome to identify corrupted rows of the reduced redundancy product code array;

forming second column syndromes for the raw data symbols and checks in rows 1 through n₂ of columns 1 through n₁ of the reduced redundancy product code array, wherein the second column syndromes are associated one-to-one to the columns of the reduced redundancy product code array and each has length r₂ ; and

using the second column syndromes to correct erasure of the corrupted rows of the reduced redundancy product code array.

14. An error correction system utilizing a reduced redundancy product code array, the system comprising:

an array buffer having n₁ columns and n₂ rows for storing raw data symbols in columns one through n₁ of rows one through (k₂ -r₂) and in columns one through k₁ of rows (k₂ -r₂ +1) through k₂, where n₁, n₂, k₁, k₂, r₁, and r₂ are positive integer numbers satisfying relations n₁ =k₁ +r₁ and n₂ =k₂ +r₂ ;

a column encoder for encoding the raw data symbols in columns one through k₁ of the array buffer with a column code to form column checks of length r₂ symbols, the column checks being associated one to one to the columns and stored in rows (k₂ +1) through n₂ of their respective associated columns of the array buffer;

a row encoder for encoding the raw data in rows one through (k₂ -r₂) of the array buffer with a row code to form first row checks of length r₁ symbols, and for encoding the raw data symbols and column cheek symbols in rows (k₂ -r₂ +1) through n₂ of the array buffer with the row code to form second row checks of length r₁ symbols;

a column encoder for encoding columns of the first row checks with an intermediate code to form intermediate checks of length 2r₂ symbols;

an adder for summing the second row checks and the intermediate checks to form a checks array with dimensions r₁ symbols by 2r₂ symbols derived from the raw data symbols in columns one through n₁ of rows one through (k₂ -r₂), the raw data symbols in columns one through k₁ of rows (k₂ -r₂ +1) through k₂ and the column checks in rows (k₂ +1) through n₂, the checks array being stored in columns (k₁ +1) through n₁ of rows (k₂ -r₂ +1) through n₂ of the array buffer, thereby forming a product code array with redundancy of n₁ r₂ +r₁ -r₁ r₂ symbols while maintaining substantially equal error correction capability for a non-reduced redundancy product code array having a redundancy of n₁ r₂ +n₂ r₁ -r₁ r₂.

15. The system of claim 14, comprising:

a row decoder for decoding rows of the product code array with the row code to form syndromes of length r₁ symbols, the syndromes being associated one to one with the rows of the product code array;

a syndrome array buffer having n₂ rows and r₁ columns for storing the syndromes in a syndrome array with each syndrome being stored in a row of the syndrome array buffer;

a syndrome decoder for decoding columns of the syndrome array with the intermediate code to locate any corrupted rows of the product code array; and

a column decoder for decoding columns of the product code array with the column code to correct erasure of the corrupted rows of the product code array.

16. The system of claim 15, comprising:

the syndrome decoder further being operative to decode columns of the syndrome array with the intermediate code to correct any errors in the syndrome array; and

the row decoder further being operative to decode rows of the product code array utilizing the corrected syndrome array to correct any random errors in the product code array.

17. An error correction system utilizing a product code array of raw data symbols comprising:

a column encoder for encoding columns of the product code array with a column code C2 forming check symbols of the column code C2;

a row encoder for encoding rows of the product code array and rows of the check symbols of the column code C2 with a row code C1 forming rows of check symbols of the row code C1, the rows of check symbols of the row code C1 associated one to one with the rows of the product code array and the rows of the check symbols of the column codes C2;

an intermediate column encoder encoding columns for a first portion of rows of the check symbols of the row code C1 into intermediate check symbols for code C1.5; and

a redundancy compressor that combines the intermediate check symbols of the code C1.5 with a remaining second portion of the check symbols of row code C1 into a reduced set of row check symbols having less redundancy than the set of row check symbols while maintaining substantially the same error correction capability for the product code array.

18. The system of claim 17 including the following:

a syndrome generator for processing rows of the product code array with the row code C1 to form syndromes;

a syndrome array buffer for storing the syndromes in a syndrome array, each row in the syndrome array being associated one to one with the rows of the product code array;

a syndrome decoder for decoding columns of the syndrome array with the intermediate code C1.5 to generate a corrupted rows list for the product code array; and

a column decoder performing erasure correction for corrupted rows of the product code array according to the corrupted rows list and the column codes C2.

19. An error correction system according to claim 18 wherein n₁, n₂, r₁, and r₂ are integer numbers, the system including:

a row decoder for decoding rows of the product code array with a row code to form syndromes of length r₁ symbols, the syndromes being associated one to one with the rows of the product code array;

a syndrome array buffer having n₂ rows and r₁ columns for storing the syndromes in a syndrome array with each syndrome being stored in a row of the syndrome array buffer;

a syndrome decoder for decoding columns of the syndrome array with an intermediate code of redundancy 2r₂ to locate any corrupted rows of the product code array; and

a column decoder for decoding columns of the product code array with a column code of redundancy r₂ to correct erasure of the corrupted rows of the product code array.

20. The system of claim 19, comprising:

the syndrome decoder further being operative to decode columns of the syndrome array with the intermediate code to correct any errors in the syndrome array; and

the row decoder further being operative to decode rows of the product code array utilizing the corrected syndrome array to correct any random errors in the product code array.