Modems utilizing low density parity check codes
View Patent ↗A modem includes an LDPC encoder which utilizes a deterministic H-matrix, optionally via a generation matrix, to generate redundant parity bits for a bit block. Ones are placed into the H-matrix in a completely diagonal manner with diagonals subdivided into sets of diagonals. The first diagonal in each set i begins with coordinates H(1,k), where k=(1+(i*M j )). The remaining diagonals in the sets are offset from the first diagonals so that the column distances between any two pairs of diagonals is unique. In another embodiment, the H-matrix is determined by assigning “1s” in a first column, and then assigning “1s” of subsequent columns deterministically by causing each “1” in a previous ancestor column to generate a “1” in the next descendant column based on the rule that a descendant is placed one position below an ancestor except where rectangles would be generated. Interrupted descending diagonals are generated.
1. A digital modem, comprising:
a) a digital interface; and
b) a transmitter coupled to said digital interface, said transmitter including a low density parity check (LDPC) encoder which generates redundant bits utilizing a substantially deterministically generated H matrix;
c) a receiver coupled to said digital interface, said receiver including a LDPC decoder; and
d) means for substantially deterministically generating said H matrix, said H matrix having a plurality of columns (M k ) and a plurality of rows (M j ), said means for generating said H matrix being associated with at least one of said transmitter and said receiver and including means for assigning a plurality of “ones” in a diagonal fashion within said H matrix so as to generate a plurality of diagonals of “ones” while not creating any rectangles of ones in said H matrix, wherein column distances between any two pairs of said plurality of diagonals are unique.
2. A modem according to claim 1 , wherein:
said plurality of diagonals of ones include N sets of diagonals, where N is an integer greater than one.
3. A modem according to claim 2 , wherein:
said plurality of sets each include a number N j of diagonals equal to a required number of ones in a column.
4. A modem according to claim 3 , wherein:
said plurality of sets comprises N sets where N=ceil(M k /M j ), where M k is the number of columns in said H matrix, M j is the number of rows in said H matrix, and ceil is an indication of rounding-up to the next whole number.
5. A modem according to claim 2 , wherein:
a first diagonal in each of said plurality of sets begins from a point with coordinates H(1, k), where k=(1+(i*M j )) and where i an index of set number (i=0,1,2, . . . N−1) and is the number of rows in said H matrix.
6. A modem according to claim 4 , wherein:
when N j =2 the points of the second diagonals in each set are shifted 1+i columns relative to the points of the first diagonals where i is an index of set number.
7. A modem according to claim 3 , wherein:
when N j =2 the points of the second diagonal in a first set are located one column away from said points of the first diagonal in said first set, and the points of the second diagonal in a second set are located two columns away from said points of the first diagonal in said second set, and the points of the second diagonal in a third set are located five columns away from said points of the first diagonal in said third set, and the points of the second diagonal in a fourth set are located nine columns away from said points of the first diagonal in said fourth set.
8. A modem according to claim 3 , wherein:
when N j =3 the points of respective second diagonals of respective of said sets are located 1+(3*i) columns away relative to the points of the first diagonals of respective of said sets, and the points of the third diagonals of said sets are located 2+(3*i) columns away relative to the points of the respective second diagonals of said set, where i is an index of set number.
9. A modem according to claim 1 , wherein:
said LDPC encoder generates redundant bits utilizing a generation matrix which is a function of said substantially deterministically generated H matrix.
10. A modem according to claim 1 , wherein:
said LDPC encoder generates redundant bits directly via use of said substantially deterministically generated H matrix.
11. A modem according to claim 1 , further comprising:
memory means for storing a plurality of column distance sequences for a plurality of H matrices of different sizes.
12. A modem according to claim 1 , further comprising:
memory means for storing an algorithm which generates column distance sequences for a plurality of H matrices of different sizes.
13. A method comprising:
generating an H matrix for a low density parity check code by assigning a plurality of “ones” into an H matrix in a completely diagonal fashion with said H matrix having a plurality of columns (M k ) and a plurality of rows (M j ) such that said “ones” form a plurality of diagonals and column distances between any two pairs of said plurality of diagonals are unique;
generating an encoded data stream based upon said H matrix; and
outputting said encoded data stream for transmission over a channel.
14. A method according to claim 13 , wherein:
said plurality of diagonals comprises a plurality of N sets of diagonals, where N is an integer greater than one.
15. A method according to claim 14 , wherein:
N=ceil(M k /M j ), and ceil is an indication of rounding-up to the next whole number.
16. A method according to claim 14 , wherein:
said N sets of diagonals each include a number N j of diagonals equal to a required number of ones in a column.
17. A method according to claim 14 , wherein:
a first diagonal in each of said plurality of sets begins from a point with coordinates H(1,k), where k=(1+(i*M j )) and where i an index of set number (i=0,1,2, . . . N−1).
18. A method according to claim 16 , wherein:
when N j =2 the points of the second diagonals in each set are shifted 1+i columns relative to the points of the first diagonals where i is an index of set number.
19. A method according to claim 16 , wherein:
when N j =2 the points of the second diagonal in a first set are located one column away from said points of the first diagonal in said first set, and the points of the second diagonal in a second set are located two columns away from said points of the first diagonal in said second set, and the points of the second diagonal in a third set are located five columns away from said points of the first diagonal in said third set, and the points of the second diagonal in a fourth set are located nine columns away from said points of the first diagonal in said fourth set.
20. A method according to claim 16 , wherein:
when N j =3 the points of respective second diagonals of respective of said sets are located 1+(3*i) columns away relative to the points of the first diagonals of respective of said sets, and the points of the third diagonals of said sets are located 2+(3*i) columns away relative to the points of the respective second diagonals of said set, where i is an index of set number.