Cyclic trellis coded modulation

• US 5,931,965 A
• Filed: 07/09/1997
• Issued: 08/03/1999
• Est. Priority Date: 11/23/1994
• Status: Expired due to Term

• Current Assignee: AT&T Mobility II LLC (AT&T, Inc.)
• Original Assignee: AT&T Wireless Services Incorporated (AT&T, Inc.)
• Inventors: Alamouti, Siavash M.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/890,507
• Time in Patent Office: 755 Days
• Field of Search: 371/43.4, 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/25 Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] modulation codes H03M13/31
• CPC Class Codes: H03M 13/256 with trellis coding, e.g. with convolutional codes and TCM
• CPC Class Codes: H04L 1/006 Trellis-coded modulation
• CPC Class Codes: H04L 27/3427 in which the constellation is the n - fold Cartesian product of a single underlying two-dimensional constellation

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. A method of forward error correction coding for a data signal mapped according to a given signal constellation, said method comprising the steps of:

defining a family of convolutional codes, said step of defining further comprising the steps of;

establishing a next-state value corresponding to each present-state/input-value pair;

establishing an output value corresponding to each present-state/input-value pair;

receiving an input data symbol corresponding to an input value;

providing an output value in response to the reception of said input value, wherein said output value is determined by said input value and said present-state value, and said present state value is determined by the previous next state value;

generating an output data symbol, wherein said output symbol is determined by said output value; and

encoding a data signal to correspond to said output symbol as determined by a signal mapping scheme.

2. A method of error encoding a data signal using a state machine wherein output values are determined as a function of input values and present state values, said method comprising the steps of:

defining a next state table within said state machine, said next state table including state values for each present-state/input-value pair, said state values in said next state table being defined such that a minimum number of transitions required to transition from a first state to a second state and back to the first state is maximized;

defining an output table within said state machine based upon the next state table, said output table including output values corresponding to each present-state/input-value pair such that symbols output in response to input values encoded over different trellis paths beginning and ending in the same state are maximally separated; and

encoding said data signal to corresponding to said output symbols.

3. A method as defined in claim 2, wherein said minimum number of transitions required to transition from the first state to the second state and back to the first state is three, for a state machine having four possible states and four possible input values.

4. A method as defined in claim 2, wherein said separation of symbols output by said state machine is measured as a sum of the square of the euclidian distances measured for each transition between states.