Low cost, high performance error detection and correction

Abstract

A method and apparatus provides the ability to build and use low-density linear parity-check (LDPC) codes for implementing error detection and correction (EDC). A number of data bits and a number of parity bits are received. While the number of data bits and number of parity bits are within a defined threshold with respect to each other, codes are created. The codes are based on the number of parity bits as combinations of values for the parity bits. The codes are sorted into weight subsections with each subsection containing having the same weight. A subset of each subsection is determined based on the number of data bits with the subset containing codes representing a lowest number of inputs to a parity tree for a given parity bit. An identity matrix of a size of the number of data bits is appended to the subset.

1 . A method for building a family of low-density linear parity-check (LDPC) codes used for implementing error detection and correction (EDC) comprising:
 (a) receiving a first number of data bits from an operator;   (b) receiving a second number of parity bits from an operator;   (c) while the first number of data bits and the second number of parity bits are within a defined threshold with respect to each other:
 (i) creating one or more first LDPC matrix codes based on the second number of parity bits, wherein the first LDPC matrix codes comprise combinations of values for the parity bits; 
 (ii) sorting the first LDPC matrix codes into weight subsections, wherein each weight subsection comprises one or more LDPC matrix codes having a same weight; 
 (iii) determining a subset of each weight subsection based on the first number of data bits, wherein the subset comprises those LDPC matrix codes representing a lowest number of inputs to a parity tree for a given parity bit; and 
   (d) appending an identity matrix of a size of the first number of data bits to the subset.   
     
     
         2 . The method of  claim 1  wherein the defined threshold comprises:
 the first number of data bits is greater than the second number of parity bits; and   the second number of parity bits is above a minimum number of parity bits with respect to the first number of data bits.   
     
     
         3 . The method of  claim 2 , wherein the second number of parity bits (P) is above a minimum number of parity bits with respect to the first number of data bits (d) based on d>2 p −p−1. 
     
     
         4 . The method of  claim 1  wherein those LDPC matrix codes representing a lowest number of inputs to a parity tree for a given parity bit comprise LDPC matrix codes having a lowest row weight. 
     
     
         5 . The method of  claim 1  further comprising while the first number of data bits and second number of parity bits are within a defined threshold with respect to each other:
 (i) dividing the first number of data bits into two or more subsets based on the first number of data bits and the second number of parity bits;   (ii) creating one or more additional first LDPC matrix codes, wherein each additional first LDPC matrix code is based on a respective subset; and   (iii) creating a second LDPC matrix code comprising two or more first LDPC matrix codes.   
     
     
         6 . A method of data transmission using a family of low-density linear parity-check (LDPC) codes comprising:
 (a) receiving input data;   (b) receiving a LDPC matrix, wherein the LDPC matrix is obtained by:
 (i) receiving a first number of data bits from an operator; 
 (ii) receiving a second number of parity bits from an operator; 
 (iii) while the first number of data bits and the second number of parity bits are within a defined threshold with respect to each other:
 (1) creating one or more first LDPC matrix codes based on the second number of parity bits, wherein the first LDPC matrix codes comprise combinations of values for the parity bits; 
 (2) sorting the first LDPC matrix codes into weight subsections, wherein each weight subsection comprises one or more LDPC matrix codes having a same weight; 
 (3) determining a subset of each weight subsection based on the first number of data bits, wherein the subset comprises those LDPC matrix codes representing a lowest number of inputs to a parity tree for a given parity bit; and 
 
 (iv) appending an identity matrix of a size of the first number of data bits to the subset; and 
   (c) encoding the input data using the LDPC matrix to produce output data.   
     
     
         7 . The method of  claim 6  wherein the defined threshold comprises:
 the first number of data bits is greater than the second number of parity bits; and   the second number of parity bits is above a minimum number of parity bits with respect to the first number of data bits.   
     
     
         8 . The method of  claim 7 , wherein the second number of parity bits (P) is above a minimum number of parity bits with respect to the first number of data bits (d) based on d>2 p −p−1. 
     
     
         9 . The method of  claim 6  wherein those LDPC matrix codes representing a lowest number of inputs to a parity tree for a given parity bit comprise LDPC matrix codes having a lowest row weight. 
     
     
         10 . The method of  claim 6  further comprising while the first number of data bits and second number of parity bits are within a defined threshold with respect to each other:
 (i) dividing the first number of data bits into two or more subsets based on the first number of data bits and the second number of parity bits;   (ii) creating one or more additional first LDPC matrix codes, wherein each additional first LDPC matrix code is based on a respective subset; and   (iii) creating a second LDPC matrix code comprising two or more first LDPC matrix codes.   
     
     
         11 . A digital circuit data transmission apparatus comprising:
 (a) a low density parity check (LDPC) encoder for encoding input data, wherein the encoder is configured in accordance with:
 (i) a first number of data bits received from an operator; 
 (ii) a second number of parity bits received from an operator; 
 (iii) while the first number of data bits and the second number of parity bits are within a defined threshold with respect to each other:
 (1) one or more first LDPC matrix codes are created based on the second number of parity bits, wherein the first LDPC matrix codes comprise combinations of values for the parity bits; 
 (2) the first LDPC matrix codes are sorted into weight subsections, wherein each weight subsection comprises one or more LDPC matrix codes having a same weight; 
 (3) a subset of each weight subsection is determined based on the first number of data bits, wherein the subset comprises those LDPC matrix codes representing a lowest number of inputs to a parity tree for a given parity bit; and 
 
 (iv) an identity matrix of a size of the first number of data bits is appended to the subset. 
   
     
     
         12 . The apparatus of  claim 11  wherein the defined threshold comprises:
 the first number of data bits is greater than the second number of parity bits; and   the second number of parity bits is above a minimum number of parity bits with respect to the first number of data bits.   
     
     
         13 . The apparatus of  claim 12 , wherein the second number of parity bits (P) is above a minimum number of parity bits with respect to the first number of data bits (d) based on d>2 p −p−1. 
     
     
         14 . The apparatus of  claim 11  wherein those LDPC matrix codes representing a lowest number of inputs to a parity tree for a given parity bit comprise LDPC matrix codes having a lowest row weight. 
     
     
         15 . The apparatus of  claim 11  wherein while the first number of data bits and second number of parity bits are within a defined threshold with respect to each other:
 (i) the first number of data bits is divided into two or more subsets based on the first number of data bits and the second number of parity bits;   (ii) one or more additional first LDPC matrix codes are created, wherein each additional first LDPC matrix code is based on a respective subset; and   (iii) a second LDPC matrix code is created that comprises two or more first LDPC matrix codes.