Decoding method and device for decoding linear code
The present invention relates to a decoding method and a decoder, a program, a recording-and-reproducing apparatus and a method, and a reproducing apparatus and a method that are suitable for decoding encoded data encoded by using a linear code on ring R. A low-density processing unit performs parity-check-matrix low-density processing, performs linear combination for rows of a parity check matrix included in an obtained reception word, and generates a parity check matrix according to the linear-combination result, thereby reducing the density of the parity check matrix used for decoding, at step S 21 . Then, at step S 22 , an LDPC decoding unit performs decoding by using a sum product algorithm (SPA) by using the parity check matrix whose density is reduced through the processing performed at step S 21 . Where the processing at step S 22 is finished, the LDPC decoding unit finishes decoding for the reception word. The present invention can be used for an error-correction system.
1. A method for decoding a linear code, the method being executed by a decoder and comprising:
reducing density of a check matrix of the linear code by generating a new matrix of reduced density based on elements included in the check matrix whose values are determined to be one “1”;
calculating a linear combination of rows of the check matrix;
extracting a subset of lower-weight vectors for forming a complementary space from among a vector set obtained by the linear combination;
including the lower-weight vectors as row elements of the new check matrix; and
decoding the linear code through a sum product algorithm by using the new check matrix, the decoding being performed by the decoder.
2. The decoding method according to claim 1 , wherein the linear code is a finite field including powers of prime numbers, as elements.
3. The decoding method according to claim 2 , wherein the linear code includes a BCH code, or a Reed-Solomon code on the finite field.
4. The decoding method according to claim 1 , wherein reducing the density further includes:
expanding the check matrix by expanding a predetermined subfield of the finite field by a predetermined degree; and
calculating linear combination of the rows of the expanded check matrix.
5. A decoder for decoding a linear code, the decoder comprising:
means for reducing a density of a check matrix of the linear code by generating a new matrix of reduced density based on elements included in the check matrix whose values are determined to be one “1”;
means for calculating a linear combination of rows of the check matrix;
means for extracting a subset of lower-weight vectors for forming a complementary space from among a vector set obtained by the linear combination;
means for including the lower-weight vectors as row elements of the new check matrix; and
means for decoding the linear code through a sum product algorithm by using the new check matrix.
6. The decoder according to claim 5 , wherein the linear code is a finite field including powers of prime numbers, as elements.
7. The decoder according to claim 6 , wherein the linear code includes a BCH code, or a Reed-Solomon code on the finite field.
8. The decoder according to claim 5 further comprising means for expanding the check matrix by expanding a predetermined subfield of the finite field by a predetermined degree, wherein the means for calculating calculates linear combination of rows of the expanded check matrix.
9. The decoder according to claim 5 further including means for performing soft-decision decoding on a linear code subjected to convolutional encoding, wherein the means for reducing reduces the density of a check matrix obtained by decoding the convolutionaly encoded linear code, the reduction being performed by reducing a density of elements included in the obtained check matrix and having values that are determined to be one “1”.
10. The decoder according to claim 9 , wherein the soft-decision decoding, the low-density processing, and the decoding are repetitively performed.
11. A method for decoding a linear code, the decoding method being executed by a decoder and comprising:
inputting a reception value;
reducing density of a check matrix of the linear code by generating a new matrix of reduced density based on elements included in the check matrix whose values are determined to be one “1”;
calculating a linear combination of rows of the check matrix;
extracting a subset of lower-weight vectors for forming a complementary space from among a vector set obtained by the linear combination;
including the lower-weight vectors as row elements of the new check matrix; and
decoding the linear code through a sum product algorithm by using the new check matrix and the reception value, the decoding being performed by the decoder.
12. A decoder for decoding a linear code, the decoder comprising:
means for inputting a reception value;
means for reducing density of a check matrix of the linear code by generating a new matrix of reduced density based on elements included in the check matrix whose values are determined to be one “1”;
means for calculating a linear combination of rows of the check matrix;
means for extracting a subset of lower-weight vectors for forming a complementary space from among a vector set obtained by the linear combination;
means for including the lower-weight vectors as row elements of the new check matrix; and
means for decoding the linear code through a sum product algorithm, by using the new check matrix and the reception value.
13. A computer-readable storage medium storing a program for causing a computer to execute a method of decoding a linear code, the method comprising:
inputting a reception value;
reducing density of a check matrix of the linear code by generating a new matrix of reduced density based on elements included in the check matrix whose values are determined to be one “1”;
calculating a linear combination of rows of the check matrix;
extracting a subset of lower-weight vectors for forming a complementary space from among a vector set obtained by the linear combination;
including the lower-weight vectors as row elements of the new check matrix; and
decoding the linear code through a sum product algorithm by using the new check matrix and the reception value, the decoding being performed by the decoder.