Code generation method, error correction code generation apparatus, and storage medium storing instructions to perform code generation method

Patent metadata

Field	Value
Publication number	US-12413247-B2
Application number	US-202318506336-A
Country	US
Kind code	B2
Filing date	Nov 10, 2023
Priority date	Jun 20, 2023
Publication date	Sep 9, 2025
Grant date	Sep 9, 2025

Abstract

There is provided a code generation method. The method comprises extracting columns corresponding to the number of symbols of a codeword from a parity check matrix of an error correction code; generating a shortened parity check matrix for the error correction code on the basis of the columns corresponding to the number of symbols of the codeword; checking whether the shortened parity check matrix includes an independent nonzero syndrome for each of a single symbol error and a double error; and generating a parity check matrix for a correction of the single symbol error corresponding to the number of bits of the shortened parity check matrix and a correction of the double error corresponding to the number of bits of the shortened parity check matrix if the shortened parity check matrix includes the independent nonzero syndrome for each of the single symbol error and the double error.

First claim

What is claimed is:

1. A processor-implemented code generation method to be performed in an error correction code generation apparatus, the code generation method comprising:
extracting, by an extraction unit, columns corresponding to the number of symbols of a codeword from a parity check matrix of an error correction code;
generating, by a generation unit, a shortened parity check matrix for the error correction code on the basis of the columns corresponding to the number of symbols of the codeword;
checking, by a checking unit, whether the shortened parity check matrix includes an independent nonzero syndrome for each of a single symbol error and a double error; and
in response to the shortened parity check matrix including the independent nonzero syndrome for each of the single symbol error and the double error, further generating, by the generation unit, a parity check matrix for a correction of the single symbol error corresponding to the number of bits of the shortened parity check matrix and a correction of the double error corresponding to the number of bits of the shortened parity check matrix.

2. The code generation method of claim 1 , wherein the generating of the shortened parity check matrix includes setting two rightmost columns of the parity check matrix as a unit matrix.

3. The code generation method of claim 1 , further comprising:
determining, by the extraction unit, the checked result for whether the shortened parity check matrix includes the independent nonzero syndrome for each of the single symbol error and the double error, and repeating the extracting columns until it is checked that the shortened parity check matrix includes the independent nonzero syndrome for each of the single symbol error and the double error.

4. The code generation method of claim 1 , wherein the checking of whether the shortened parity check matrix includes the independent nonzero syndrome for each of the single symbol error and the double error includes converting symbols of each column of the shortened parity check matrix into a binary form.

5. The code generation method of claim 1 , wherein the correction of the double error satisfies a first condition in which all columns of the parity check matrix are nonzero and different from each other and a second condition in which exclusive bit ORs of arbitrary two columns of the parity check matrix are different from each other and are different from all columns of the parity check matrix.

6. The code generation method of claim 1 , wherein each symbol is composed of 8 bits, and the codeword is composed of 80 bits.

7. The code generation method of claim 1 , wherein the error correction code includes a Reed-Solomon error correction code.

8. An error correction code generation apparatus, the apparatus comprising:
an extraction unit configured to extract columns corresponding to the number of symbols of a codeword from a parity check matrix of an error correction code;
a generation unit configured to generate a shortened parity check matrix for the error correction code on the basis of the columns corresponding to the number of symbols of the codeword; and
a checking unit configured to check whether the shortened parity check matrix includes an independent nonzero syndrome for each of a single symbol error and a double error,
in response to the shortened parity check matrix including the independent nonzero syndrome for each of the single symbol error and the double error, the generation unit is further configured to generate a parity check matrix for a correction of the single symbol error corresponding to the number of bits of the shortened parity check matrix and a correction of the double error corresponding to the number of bits of the shortened parity check matrix.

9. The error correction code generation apparatus of claim 8 , wherein the generation unit is further configured to set two rightmost columns of the parity check matrix as a unit matrix when generating the shortened parity check matrix.

10. The error correction code generation apparatus of claim 8 , wherein the extraction unit is further configured to determine the checked result for whether the shortened parity check matrix includes the independent nonzero syndrome for each of the single symbol error and the double error, and repeatedly extract the columns until it is checked that the shortened parity check matrix includes the independent nonzero syndrome for each of the single symbol error and the double error.

11. The error correction code generation apparatus of claim 8 , wherein the checking unit is further configured to convert symbols of each column of the shortened parity check matrix into a binary form.

12. The error correction code generation apparatus of claim 8 , wherein the correction of the double error satisfies a first condition in which all columns of the parity check matrix are nonzero and different from each other and a second condition in which exclusive bit ORs of arbitrary two columns of the parity check matrix are different from each other and are different from all columns of the parity check matrix.

13. The error correction code generation apparatus of claim 8 , wherein each symbol is composed of 8 bits, and the codeword is composed of 80 bits.

14. The error correction code generation apparatus of claim 8 , wherein the error correction code includes a Reed-Solomon error correction code.

15. A non-transitory computer-readable storage medium storing a computer program including instructions for causing a processor to perform a code generation method, the code generation method comprising:
extracting columns corresponding to the number of symbols of a codeword from a parity check matrix of an error correction code;
generating a shortened parity check matrix for the error correction code on the basis of the columns corresponding to the number of symbols of the codeword;
checking whether the shortened parity check matrix includes an independent nonzero syndrome for each of a single symbol error and a double error; and
in response to the shortened parity check matrix including the independent nonzero syndrome for each of the single symbol error and the double error, generating a parity check matrix for a correction of the single symbol error corresponding to the number of bits of the shortened parity check matrix and a correction of the double error corresponding to the number of bits of the shortened parity check matrix.

16. The non-transitory computer-readable storage medium of claim 15 , wherein the generating of the shortened parity check matrix includes setting two rightmost columns of the parity check matrix as a unit matrix.

17. The non-transitory computer-readable storage medium of claim 15 , wherein the code generation method further comprises determining the checked result for whether the shortened parity check matrix includes the independent nonzero syndrome for each of the single symbol error and the double error, and repeating the extracting columns until it is checked that the shortened parity check matrix includes the independent nonzero syndrome for each of the single symbol error and the double error.

18. The non-transitory computer-readable storage medium of claim 15 , wherein the checking whether the shortened parity check matrix includes the independent nonzero syndrome for each of the single symbol error and the double error includes converting symbols of each column of the shortened parity check matrix into a binary form.

19. The non-transitory computer-readable storage medium of claim 15 ,

Assignees

• Univ Sungkyunkwan Res Business Found
• Research & Business Found Sungkyunkwan Univ

Inventors

• Kim Jungrae
• Kim Dong Whee

Classifications

• H03M13/159 Primary

  Remainder calculation, e.g. for encoding and syndrome calculation · CPC title

• H03M13/616

  Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title

• H03M13/2906

  using block codes (H03M13/2957 takes precedence) · CPC title

• H03M13/152

  Bose-Chaudhuri-Hocquenghem [BCH] codes · CPC title