Method and apparatus for rateless source coding with/without decoder side information

1. A method of rateless source coding, comprising the steps of:

providing a set of low-density parity check (LDPC) codes, each of said codes accepting a range of data input lengths and a range of target compression rates;

identifying a data input having a data input length, and identifying a desired compression rate;

selecting one of said LDPC codes based on said data input length and desired compression rate;

encoding the data input, using the selected LDPC code, to generate an encoded sequence of data values; and

puncturing some of said data values to maintain the compression efficiency of the selected LDPC code.

2. A method according to claim 1 , wherein the encoding step includes the step of generating a syndrome sequence and a parity sequence from the data input.

3. A method according to claim 2 , wherein the encoding step includes the further step of mixing a remaining portion of the data input with the generated parity sequence according to a predefined arithmetic operation.

4. A method according to claim 2 , wherein the parity sequence includes a multitude of parity bits, and the puncturing step includes the step of puncturing the parity bits according to the desired compression rate.

5. A method according to claim 4 , comprising the further step of forming an output bit stream from the generated syndrome sequence and the punctured parity bit sequence conforming to a predefined syntax.

6. A method according to claim 5 , comprising the further steps of:

applying said output bit stream to a decoder; and

decoding said output bit stream using said decoder.

7. A method according to claim 6 , comprising the further steps of:

modeling the parity bits that are punctured as erasures;

and using said erasure model to decode said output bit stream.

8. A method according to claim 6 , wherein the decoding step includes the steps of:

providing the decoder with side information; and

using said side information to decode said output bit stream.

9. A method according to claim 6 , wherein the decoding step includes the step of decoding said output bit stream without providing the decoder with side information.

10. A method according to claim 6 , wherein the decoding step includes the steps of:

providing the decoder with said selected one of the LDPC codes; and

decoding said output stream using said selected one of said LDPC codes.

11. A method according to claim 10 , wherein the step of providing the decoder with said selected one of the LDPC codes includes the step of providing the decoder with said set of LDPC codes.

12. A system for rateless source coding comprising:

a set of low-density parity check (LDPC) codes, each of said codes accepting a range of data input lengths and a range of target compression rates;

a code selector for receiving a first value identifying a data input length and a second value identifying a desired compression rate, and for selecting one of said LDPC codes based on said first and second values;

a generator for receiving an input data sequence and the selected LDPC code, and for encoding the data sequence using said selected LDPC code by generating a syndrome sequence and a parity sequence from said data sequence; and

a puncturing unit for puncturing the parity sequence to maintain a target compression rate.

13. A system according to claim 12 , further comprising a mixing unit for mixing the parity sequence with a portion of the input data by using a predefined arithmetic operation.

14. A system according to claim 13 , further comprising a multiplexor for forming an output bit steam from the generated syndrome sequence and the punctured parity bit sequence conforming to a predefined syntax.

15. A system according to claim 14 , further comprising:

a decoder for decoding said output bit stream;

a selector for providing the decoder with the selected LDPC code; and

wherein the decoder decodes said output bit stream using said selected LDPC code.

16. A system according to claim 15 , wherein the decoder decodes said output bit stream with/without decoder side information.

17. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for rateless source coding, said method steps comprising:

providing a set of low-density parity check (LDPC) codes, each of said codes accepting a range of data input lengths and a range of target compression rates;

identifying a data input having a data input length, and identifying a desired compression rate;

selecting one of said LDPC codes based on said data input length and desired compression rate;

encoding the data input, using the selected LDPC code, to generate an encoded sequence of data values; and

puncturing some of said data values to maintain the compression efficiency of the selected LDPC code.

18. A program storage device according to claim 17 , wherein the encoding step includes the steps of:

generating a syndrome sequence and a parity sequence from the data input; and

mixing a remaining portion of the data input with the generated parity sequence according to a predefined arithmetic operation.

19. A program storage device according to claim 18 , wherein the parity sequence includes a multitude of parity bits, and the puncturing step includes the step of puncturing the parity bits according to the desired compression rate.

20. A program storage device according to claim 19 , comprising the further step of forming an output bit stream from the generated syndrome sequence and the punctured parity bit sequence conforming to a predefined syntax.