Power-efficient communication protocol

• US 6,553,535 B1
• Filed: 08/20/1999
• Issued: 04/22/2003
• Est. Priority Date: 08/21/1998
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Asada, Haruhiko H., Erin, Cem, Siu, Kai-Yeung
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Torres, Joseph D.
• Application Number:
  US09/378,411
• Time in Patent Office: 1,341 Days
• Field of Search: 714/704, 714/792, 714/253, 714/777, 714/783, 375/265
• US Class Current: 714/777
• CPC Class Codes: H03M 13/11 using multiple parity bits
• CPC Class Codes: H03M 13/251 with block coding
• CPC Class Codes: H03M 13/253 with concatenated codes
• CPC Class Codes: H03M 13/255 with Low Density Parity Check [LDPC] codes
• CPC Class Codes: H03M 13/256 with trellis coding, e.g. with convolutional codes and TCM
• CPC Class Codes: H03M 13/258 with turbo codes, e.g. Turbo Trellis Coded Modulation [TTCM]
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/63 Joint error correction and other techniques H03M13/31 and H03M13/33 take precedence
• CPC Class Codes: H04L 1/0044 specially adapted for power saving
• CPC Class Codes: H04L 1/0058 Block-coded modulation
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes
• CPC Class Codes: H04L 27/3411 reducing the peak to average power ratio or the mean power of the constellation; Arrangements for increasing the shape gain of a signal set

Abstract

A method and apparatus for telemetering data on a channel having a maximum data rate by utilizing a power efficient communication protocol is provided. The data to be telemetered comprises a number of source symbols where each source symbol is characterized by a probability of occurrence. A sequence of signals forming codewords having an energy and a length is produced. The length for the codewords is based at least on the number of symbols to be coded. Each codeword signifies a specified source symbol on the basis of a mapping between source symbols and codewords. The mapping is such that each source symbol of lower probability of occurrence is associated with a codeword of at least equal energy.

Claims

1. A method for encoding data into codewords, the data comprising source symbols selected from an alphabet each codeword comprising a signal characterized by an energy, each source symbol characterized by a probability of occurrence, the method comprising:

determining a length for the codewords based at least on a total number of symbols in the alphabet to be coded;

creating a set of codewords based on the determined length; and

producing a mapping at the transmitter between source symbols and codewords mapped such that each symbol of lower probability of occurrence relative to all other source symbols in the alphabet is associated with a codeword of higher or at least equal energy in comparison to each codeword associated with a source symbol having a greater probability of occurrence.

2. The method according to claim 1, wherein the step of determining requires satisfying inequalities 2^L≧

C and L≦

1/(mt_b);

wherein C represents the number of symbols, L is length of the codewords, m is number of symbols per second, and t_b is a unit of time representative of a bit period.

3. The method according to claim 1, further comprising:

transmitting codewords representative of symbols to a receiver.

4. The method according to claim 3, further comprising:

modulating the codewords on a carrier wave.

5. The method according to claim 4, wherein in the step of modulating further comprises performing block-coded modulation wherein the codewords are mapped to a signal constellation.

6. The method according to claim 4, wherein in the step of modulating further comprises performing trellis-coded modulation wherein the codewords are mapped to a signal constellation.

7. A method for encoding data into codewords, each codeword comprising a sequence of signals and characterized by an energy, the data comprising source symbols, each source symbol characterized by a probability of occurrence, the method comprising:

determining a length for the codewords based at least on a number of concatenated symbols to be coded;

creating a set of codewords based on the determined length;

determining a probability of occurrence for multiple concatenated source symbols;

producing a mapping between the multiple concatenated source symbols and codewords mapped such that each concatenated symbol of lower probability of occurrence relative to all other concatenated symbols is associated with a codeword of higher or at least equal energy in comparison to each codeword associated with a concatenated symbol having a greater probability of occurrence.

8. A method for encoding data into codewords, each codeword comprising a sequence of signals, each codeword characterized by an energy, the data comprising at least one of a number of source symbols, each source symbol characterized by a probability of occurrence relative to all other source symbols in an alphabet, the method comprising:

constructing a set of codewords having a length based upon a coding scheme wherein the length of the codewords is constrained by the number of symbols and a given transmission rate for a channel; and

producing a mapping between the source symbols and codewords mapped such that each symbol of lower probability of occurrence relative to all other source symbols in the alphabet is associated with a codeword of higher or at least equal energy in comparison to each codeword associated with a source symbol having a greater probability of occurrence.

9. The method according to claim 8, wherein the coding scheme is a Hamming code.

10. The method according to claim 9, wherein the Hamming code is extended to add a parity check bit.

11. The method according to claim 8, wherein the coding scheme is a Golay code.

12. The method according to claim 11, wherein the Golay code is extended to add a parity check bit.

13. The method according to claim 8, wherein the coding scheme is a turbo code.

14. The method according to claim 8, wherein the coding scheme is a Reed-Muller Code.

15. The method according to claim 8, wherein the sequence of signals have at least two levels of energy.

16. The method according to claim 8, further comprising:

modulating the codewords using binary modulation.

17. The method according to claim 8, the codewords are defined by more than one discrete energy level.

18. The method according to claim 8, wherein the coding scheme is a block coding.

19. The method according to claim 8, wherein the coding scheme is burst error correction.

20. The method according to claim 8, wherein the coding scheme is convolution coding.

21. The method according to claim 8, wherein the coding scheme is trellis coding converted to a block code.

22. The method according to claim 8, wherein the coding scheme is a lattice code.

23. The method according to claim 8, wherein the coding scheme is error correction coding.

24. The method according to claim 8, wherein the coding scheme is a low density parity check code.

25. A computer program product for use on a computer system for encoding data into codewords, the data comprising source symbols selected from an alphabet each codeword comprising a signal characterized by an energy, each source symbol characterized by a probability of occurrence relative to all other source symbols in the alphabet, the computer program product comprising a computer usable medium having computer readable program code thereon, the computer readable program code including:

computer code for determining a length for the codewords based at least on a total number of symbols in the alphabet to be coded;

computer code for creating a set of codewords based on the determined length; and

computer code for producing a mapping between source symbols and codewords mapped such that each symbol of lower probability of occurrence relative to all other source symbols in the alphabet is associated with a codeword of higher or at least equal energy in comparison to each codeword associated with a source symbol having a greater probability of occurrence.

26. The computer program product according to claim 25, wherein computer code for determining requires satisfying inequalities 2^L≧

C and L≦

1/(mt_b);

wherein C represents the number of symbols, L is length of the codewords, m is number of symbols per second, and t_b is a unit of time representative of a bit period.

27. The computer program product according to claim 25, further comprising:

computer code for transmitting codewords representative of symbols to a receiver.

28. The computer program product according to claim 27, further comprising:

computer code for modulating the codewords on a carrier wave.

29. The computer program product according to claim 28, wherein the computer code for modulating further comprises performing block-coded modulation wherein the codewords are mapped to a signal constellation.

30. The computer program product according to claim 28, wherein the computer code for modulating further comprises performing trellis-coded modulation wherein the codewords are mapped to a signal constellation.

31. A computer program product for use on a computer system for encoding data into codewords, each codeword comprising a sequence of signals and characterized by an energy, the data comprising source symbols, each source symbol characterized by a probability of occurrence relative to all other symbols in an alphabet, the computer program product comprising a computer usable medium having computer readable program code thereon, the computer readable program code including:

the method comprising;

computer code for determining a length for the codewords based at least on a number of concatenated symbols to be coded;

computer code for creating a set of codewords based on the determined length;

computer code for determining a probability of occurrence for multiple concatenated source symbols based on the probability of occurrence of each source symbol relative to all other symbols in the alphabet; and

computer code for producing a mapping between the multiple concatenated source symbols and codewords mapped such that each concatenated symbol of lower probability of occurrence relative to all other concatenated symbols is associated with a codeword of higher or at least equal energy in comparison to each codeword associated with a concatenated symbol having a greater probability of occurrence.

32. A computer program product for use on a computer system for encoding data into codewords, each codeword comprising a sequence of signals, each codeword characterized by an energy, the data comprising at least one of a number of source symbols, each source symbol characterized by a probability of occurrence relative to all other source symbols in an alphabet, the computer program product comprising a computer usable medium having computer readable program code thereon, the computer readable program code including:

computer code for constructing a set of codewords having a length based upon a coding scheme wherein the length of the codewords is constrained by a given transmission rate for a channel; and

computer code for producing a mapping between the source symbols and codewords mapped such that each symbol of lower probability of occurrence relative to all other source symbols in the alphabet is associated with a codeword of higher or at least equal energy in comparison to each codeword associated with a source symbol having a greater probability of occurrence.

33. The computer program product according to claim 32, wherein the coding scheme is a Hamming code.

34. The computer program product according to claim 33, wherein the Hamming code is extended to add a parity check bit.

35. The computer program product according to claim 32, wherein the coding scheme is a Golay code.

36. The computer program product according to claim 32, wherein the Golay code is extended to add a parity check bit.

37. The computer program product according to claim 32, wherein the coding scheme is a turbo code.

38. The computer program product according to claim 32, wherein the coding scheme is a Reed-Muller Code.

39. The computer program product according to claim 32, wherein the sequence of signals have at least two levels level of energy.

40. The computer program product according to claim 32, further comprising:

computer code for modulating the codewords using binary modulation.

41. The computer program product according to claim 32, wherein the codewords are defined by more than one discrete energy level.

42. The computer program product according to claim 32, wherein the coding scheme is block coding.

43. The computer program product according to claim 32, wherein the coding scheme is burst error correction.

44. The computer program product according to claim 32, wherein the coding scheme is convolution coding.

45. The computer program product according to claim 32, wherein the coding scheme is trellis coding converted to a block code.

46. The computer program product according to claim 32, wherein the coding scheme is a lattice code.

47. The computer program product according to claim 32, wherein the coding scheme is error correction coding.

48. The computer program product according to claim 32, wherein the coding scheme is a low density parity check code.