Low Complexity LDPC Encoding Algorithm

Abstract

A method of encoding a binary source message u, by calculating x:=Au, calculating y:=B′x, resolving the equation Dp=y for p, and incorporating u and p to produce an encoded binary message v, where A is a matrix formed only of permutation sub matrices, B′ is a matrix formed only of circulant permutation sub matrices, and D is a matrix of the form D = ( T 0 … 0 0 0 T … 0 0 … … … … … 0 0 … T 0 I I … I I ) where T is a two-diagonal, circulant sub matrix, and I is an identity sub matrix.

1 . (canceled) 
     
     
         2 . (canceled) 
     
     
         3 . (canceled) 
     
     
         4 . In a parity check matrix of the type used for an LDPC encoding method, where the parity check matrix is formed entirely of non-overlapping sub matrices, the improvement comprising the sub matrices are all permutation matrices. 
     
     
         5 . The parity check matrix of  claim 4 , wherein the permutation matrices are all circulant permutation matrices. 
     
     
         6 . The parity check matrix of  claim 4 , wherein the permutation matrices are all one of bitwise permutation matrices and circulant permutation matrices. 
     
     
         7 . The parity check matrix of  claim 4 , wherein the permutation matrices all have a size that is a power of two. 
     
     
         8 . The parity check matrix of  claim 4 , wherein the parity check matrix has a B sub matrix that is a singular matrix. 
     
     
         9 . The parity check matrix of  claim 4 , wherein the parity check matrix has an A sub matrix and a B sub matrix, where A has a size of (n−k)×n and B has a size of (n−k)×(n−k), where n and k are integers. 
     
     
         10 . In an LDPC encoding method, the improvement comprising converting a stream of digital information to a coded stream of digital information using a parity check matrix that is formed entirely of non-overlapping sub matrices, where the sub matrices are all permutation matrices. 
     
     
         11 . The method of  claim 10 , wherein the permutation matrices are all circulant permutation matrices. 
     
     
         12 . The method of  claim 10 , wherein the permutation matrices are all one of bitwise permutation matrices and circulant permutation matrices. 
     
     
         13 . The method of  claim 10 , wherein the permutation matrices all have a size that is a power of two. 
     
     
         14 . The method of  claim 10 , wherein the parity check matrix has a B sub matrix that is a singular matrix. 
     
     
         15 . The method of  claim 10 , wherein the parity check matrix has an A sub matrix and a B sub matrix, where A has a size of (n−k)×n and B has a size of (n−k)×(n−k), where n and k are integers.