Granted Patent B2

US 7,792,013 · App. 12/184,030 · Granted Sep 7, 2010

Abstract

Claims (73)

1. A method comprising:

receiving noisy data via a communications channel, wherein the noisy data includes a clean data component and a noise component;

decoding, utilizing a low-density lattice code (LDLC) matrix, the received noisy data to substantially recover the clean data component;

storing the decoded clean data component;

wherein LDLC matrix does not include any cycles of length less than six,

wherein LDLC matrix is algebraically constructed, and

wherein the LDLC includes a sparse matrix whose non-zero elements include values that are real numbers.

2. The method of claim 1 wherein the LDLC is constructed using mutually orthogonal Latin squares.

3. The method of claim 1 wherein decoding includes a linear-time integrative decoding scheme that substantially obtains an error performance of substantially 0.5 dB from a Shannon theoretical capacity of the communications channel for data with a block length of 100,000 symbols at a symbol error rate of 10 −6 .

4. The method of claim 1 wherein decoding includes utilizing an LDLC matrix whose construction includes:

selecting a prime number;

generating a plurality of mutually orthogonal Latin squares of a size equal to the selected prime number;

for each Latin square, producing an incidence matrix based upon the respective Latin square;

creating a mapping matrix, based upon in part the incidence matrixes, that comprises a square matrix,

wherein each row includes a number of elements equal to the selected prime number squared, and

a number of non-zero elements equal to the selected prime number, and

wherein each non-zero element has a value of one;

making, for each row of the mapping matrix, a sparse vector including the prime number of elements, in which the value the elements range between one and zero, inclusive;

assigning, for each row of the mapping matrix, a value to each non-zero element of the row utilizing a corresponding value of the respective sparse vector; and

constructing the LDLC matrix utilizing the assigned matrix by multiplying each non-zero element by a substantially randomly determined one or negative one.

5. The method of claim 4 wherein each incidence matrix includes dimensions of the prime number by the prime number squared.

6. The method of claim 4 wherein creating a mapping matrix includes:

generating a first matrix that includes, for each row, the prime number of sequential one valued elements, and

wherein the dimensions of the first matrix are the prime number by the prime number squared;

generating a second matrix including the prime number of identity matrixes, and

wherein the dimension of each identity matrix the equal to the prime number; and

concatenating the first matrix, the second matrix, and a sub-portion of the incidence matrixes to form the mapping matrix.

7. The method of claim 4 wherein making includes:

constructing an initial sparse vector of the prime number of elements,

wherein the first element of the initial sparse vector is equal to one,

the remaining elements of a first portion are of decreasing value until a value of zero is reached, and

all remaining elements are equal to zero; and

permuting, for each row of the mapping matrix, the initial sparse vector using a permutation function.

8. The method of claim 1 wherein the LDLC matrix is constructed utilizing a systematic single-pass scheme employing Latin squares to select non-zero values of the LDLC matrix.

9. The method of claim 1 further including:

encoding clean data with a lattice generator matrix to produce encoded data;

transmitting the encoded data via a noisy communications channel; and

wherein the lattice generator matrix includes the inverse of the LDLC matrix.

10. An apparatus comprising:

a transceiver configured to:

receive noisy data via a communications channel, wherein the noisy data includes a clean data component and a noise component;

a controller configured to:

decode, utilizing a low-density lattice code (LDLC) matrix, the received noisy data to substantially recover the clean data component;

a memory configured to:

store the decoded clean data component; and

the low-density lattice code (LDLC) matrix that does not include any cycles of length less than six, and wherein LDLC matrix is algebraically constructed, and wherein the LDLC includes a sparse matrix whose non-zero elements include values that are real numbers.

11. The apparatus of claim 10 wherein the LDLC is constructed using mutually orthogonal Latin squares.

12. The apparatus of claim 10 wherein the controller is configured to:

decode the received data utilizing linear-time integrative decoding scheme that substantially obtains an error performance of substantially 0.5 dB from a Shannon theoretical capacity of the communications channel for data with a block length of 100,000 symbols at a symbol error rate of 10 −6 .

13. The apparatus of claim 10 wherein the controller is configured to:

select a prime number, and

wherein the controller comprises:

a Latin square generator configured to generate a plurality of mutually orthogonal Latin squares of a size equal to the selected prime number;

an incidence matrix generator configured to, for each Latin square, produce an incidence matrix based upon the respective Latin square;

a matrix concatenator configured to:

create a mapping matrix, based upon in part the incidence matrixes, that comprises a square matrix, wherein each row includes a number of elements equal to the selected prime number squared, a number of non-zero elements equal to the selected prime number, and wherein each non-zero element has a value of one; a sparse vector generator configured to, for each row of the mapping matrix, make a sparse vector including the prime number of elements, in which the value the elements range between one and zero, inclusive; a combiner configured to, for each row of the mapping matrix, assign a value to each non-zero element of the row utilizing a corresponding value of the respective sparse vector; and a random sign multiplier configured to construct the LDLC matrix utilizing the assigned matrix by multiplying each non-zero element by a substantially randomly determined one or negative one.

14. The apparatus of claim 13 wherein the incidence matrix generator is configured to produce, for each Latin square, an incidence matrix including dimensions of the prime number by the prime number squared.

15. The apparatus of claim 13 the sparse vector generator is configured to:

construct an initial sparse vector of the prime number of elements, wherein the first element of the initial sparse vector is equal to one, the remaining elements of a first portion are of decreasing value until a value of zero is reached, and all remaining elements are equal to zero;

and the controller further includes:

a vector permutator configured to, for each row of the mapping matrix, permute the initial sparse vector using a permutation function.

16. The apparatus of claim 13 wherein the matrix concatenator is configured to:

acquire a first matrix that includes, for each row, the prime number of sequential one valued elements, and wherein the dimensions of the first matrix are the prime number by the prime number squared; acquire a second matrix including the prime number of identity matrixes, and wherein the dimension of each identity matrix the equal to the prime number; and concatenate the first matrix, the second matrix, and a sub-portion of the incidence matrixes to form the mapping matrix.

17. The apparatus of claim 10 wherein the controller is configured to decode utilizing a LDLC matrix that is constructed utilizing a systematic single-pass scheme employing Latin squares to select non-zero values of the LDLC matrix.

18. The apparatus of claim 10 wherein the controller is further configured to: encode clean data with a lattice generator matrix to produce encoded data, wherein the lattice generator matrix includes the inverse of the LDLC matrix; and wherein the transceiver is configured to: transmit the encoded data via a noisy communications channel.

19. An apparatus comprising:

a transceiver configured to:

receive noisy data via a communications channel, wherein the noisy data includes a clean data component and a noise component;

a controller configured to:

decode, utilizing a low-density lattice code (LDLC) matrix, the received noisy data to substantially recover the clean data component;

a memory configured to:

store the decoded clean data component; and

the low-density lattice code (LDLC) matrix that does not include any cycles of length less than six, and wherein LDLC matrix is algebraically constructed using mutually orthogonal Latin squares.

Assignments (9)