Cyclic trellis coded modulation

• US 8,037,396 B2
• Filed: 03/22/2005
• Issued: 10/11/2011
• Est. Priority Date: 11/23/1994
• Status: Expired due to Fees

• Current Assignee: AT&T Mobility II LLC (AT&T, Inc.)
• Original Assignee: AT&T Mobility II LLC (AT&T, Inc.)
• Inventors: Alamouti, Siavash M.
• Primary Examiner(s): Alphonse; Fritz
• Application Number:
  US11/087,390
• Publication Number:
  US 20050254606A1
• Time in Patent Office: 2,394 Days
• Field of Search: 714/792, 714/755, 714/746, 714/758, 375/261, 375/340, 375/262, 375/265
• US Class Current: 714/792
• CPC Class Codes: H03M 13/235 Encoding of convolutional codes, e.g. methods or arrangements for parallel or block-wise encoding
• CPC Class Codes: H03M 13/253 with concatenated codes
• CPC Class Codes: H03M 13/256 with trellis coding, e.g. with convolutional codes and TCM
• CPC Class Codes: H03M 13/2936 comprising an outer Reed-Solomon code and an inner convolutional code
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]
• CPC Class Codes: H03M 13/6538 ATSC VBS systems
• CPC Class Codes: H04L 1/006 Trellis-coded modulation

Abstract

A universal method of trellis encoding signals mapped according to any signal constellation format involves constructing an encoder output table and a state transition table. The encoder output table defines the output symbol of an encoder given the input symbol and the present state of the encoder, while the state transition table defines the next state of the encoder given the present state of the encoder and the input applied to the encoder. The output table and the next state table are constructed with the objective of providing maximal distances between the branches of the trellis diagram without any regards for the shift register implementation of the code. Cyclic trellis-coded modulation is an example of such codes without feed-forward or feed-back shift register implementations, and with equal or better performance than “optimal” shift register trellis codes with 16 states or less. The cyclic trellis codes for both AWGN and Rayleigh fading applications can be constructed for any signal constellation without resorting to exhaustive searches.

Claims

1. An apparatus comprising:

a cyclic trellis encoder for encoding digital signals,

wherein the cyclic trellis encoder comprises;

an encoder output storage element containing a predetermined set of possible encoder output values;

a state transition storage element containing a predetermined set of next encoder states; and

a present state storage element configured to receive a next encoder state and configured to provide a present encoder state.

2. The apparatus of claim 1, wherein the cyclic trellis encoder is not implemented as a feed-forward shift register or a feed-back shift register.

3. The apparatus of claim 1, wherein the cyclic trellis encoder is not implemented as a shift register.

4. The apparatus of claim 1,

wherein the encoder output storage element is configured as at least one table including an encoder output value for each possible combination of 2^k possible present states and 2ⁿ possible inputs, where n is a number of bits received at a time by the cyclic trellis encoder and k is a positive integer, and

wherein the state transition storage element is configured as at least one state transition storage table including a next encoder state for each possible combination of 2^k possible present states and 2ⁿ possible inputs.

5. The apparatus of claim 4,

wherein a first n entries of the state transition storage table correspond to each combination of a first present state and 2ⁿ possible inputs in sequential order, and

wherein a second n entries of the state transition storage table correspond to a k+1th present state and 2ⁿ possible inputs, the second n entries having the same set of next encoder states as the first n entries cyclically reordered from the first n entries to correspond to the 2ⁿ possible inputs in sequential order.

6. The apparatus of claim 1,

wherein the predetermined set of next encoder states includes, for a particular input value, a next encoder state same as a present state for at most one particular present state.

7. The apparatus of claim 1,

wherein the predetermined set of possible encoder output values is based on a first subset of possible encoder output values and a second subset of possible encoder output values and corresponds to a first subset of possible encoder states and a second subset of possible encoder states.

8. The apparatus of claim 7,

wherein the first and second subsets of possible encoder output values are based on application type.

9. The apparatus of claim 7,

wherein the application type is characterized by one of Rayleigh fading and AWGN.

10. A method for encoding data, comprising:

cyclic trellis encoding an input signal for a modulation scheme having an even number of constellation points,

wherein all paths originating from a state of an associated cyclic trellis state transition structure and merging into the same state of the trellis state transition structure are defined so as to provide maximal or near maximal spacing between outputs on state transition paths.

11. A wireless data transmitter, comprising:

data input means for receiving input data;

state machine encoder means, coupled to the data input means, for cyclic trellis encoding the received input data, wherein the cyclic trellis encoding provides a minimum number of two branch state transition paths between the states out of all possible state transition paths between the same state; and

transmitter means coupled to the state machine encoder means for transmitting the encoded data.

12. A method comprising:

cyclic trellis encoding an input to generate an encoder output according to at least the input, a present encoder state, a predetermined set of possible encoder output values; and

updating the present encoder state to a next encoder state according to the input, the present encoder state, and a predetermined set of possible next encoder states.

13. The method of claim 12,

wherein the predetermined set of possible encoder output values is based on a first subset of possible encoder output values and a second subset of possible encoder output values and corresponds to a first subset of possible encoder states and a second subset of possible encoder states.

14. The method of claim 13,

wherein the first and second subsets of possible encoder output values are based on application type.

15. The method of claim 14,

wherein the application type is characterized by one of Rayleigh fading and AWGN.

16. The method of claim 12,

wherein the input has one of 2ⁿ possible inputs, the encoder has one of 2^k possible encoder states, and each encoder state of the predetermined set of encoder states has 2ⁿ next encoder states corresponding to respective ones of the 2ⁿ possible inputs, where n is a number of bits of the input and k is a positive integer,

wherein a first present state has a first set of possible next encoder states corresponding to each of the 2ⁿ possible inputs, the first set of possible next encoder states being 2^k-n possible encoder states in sequential order corresponding to the 2ⁿ possible inputs in sequential order,

wherein the predetermined set of possible next encoder states is based on a sequence of the possible encoder states and includes 2^k-n subsets of possible next encoder states and wherein each subset of possible next encoder states has 2^k possible next encoder states, and

wherein a k+1th present state has a second set of possible next encoder states corresponding to each of the 2ⁿ possible inputs, the second set of possible next encoder states having the same next encoder states as the first set of possible next encoder states cyclically reordered from the first set of possible next encoder states to correspond to the 2ⁿ possible inputs in sequential order.

17. The method of claim 12,

wherein a particular input value corresponds to a next encoder state same as a present state for at most one particular present state.