Cyclic trellis coded modulation

• US 5,675,590 A
• Filed: 11/23/1994
• Issued: 10/07/1997
• 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): GRANT, WILLIAM ALEXANDER
• Assistant Examiner(s): GRANT, WILLIAM ALEXANDER
• Application Number:
  US08/344,111
• Time in Patent Office: 1,049 Days
• Field of Search: 371/43-45, 371/37.8, 371/37.1, 375/39, 375/53, 375/54, 375/57, 375/58, 375/27, 375/94
• US Class Current: 714/786
• 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 set of convolutional codes using an output table and a next state table, said output table defined according to the following steps;

providing 2^k present state rows and 2ⁿ input symbol columns in said output table;

assigning values to said points of said signal constellation, said values corresponding to said output symbols, wherein said output symbols are determined as a function of input symbols and a present state value;

partitioning said signal constellation into a first subset of 2ⁿ output symbols and a second subset of 2ⁿ output symbols;

loading even ones of said present state rows with values corresponding to output symbols from said first subset; and

loading odd ones of said present state rows with values corresponding to output symbols from said second subset;

and wherein said next-state table is defined according to the following steps;

providing 2^k present state rows and 2ⁿ input symbol columns;

dividing said next states into 2^k-n subsets wherein each subset has 2ⁿ next states; and

loading a first one of said present state rows with next states from a first one of said subsets, a second one of said present state rows with the next states from a second one of said subsets, and continuing this loading until the 2^k-n th present state row is loaded with the next states from the 2^k-n th one of said subsets;

implementing said output and next-state tables within an encoder so that output symbols from said encoder are determined as a function of input symbols to said encoder and the present state of said encoder in accordance with said output table, and transitions from the present state of said encoder to the next state of said encoder are in accordance with said next-state table; and

mapping said output symbols from said encoder into signals having phase and amplitude characteristics corresponding to respective output symbol points on said signal constellation.

2. A method as defined in claim 1, wherein said coordinate points of said signal constellation are assigned output symbols according to natural mapping techniques when the predominant channel interference is Additive White Gaussian Noise.

3. A method as defined in claim 1, wherein said coordinate points of said signal constellation are assigned output symbols according to Gray coding techniques when the predominant channel interference is Rayleigh fading.

4. 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 an output table of output symbols, said output table having present state rows and input symbol columns, wherein said output symbols are determined as a function of symbols input to an encoder and a present state of said encoder, defining said output table further comprising the steps of;

assigning each of said output symbols to said points of said signal constellation;

partitioning said points of said signal constellation into a first subset of output symbols and a second subset of output symbols;

loading even ones of said present state rows with output symbols from said first subset; and

loading odd ones of said present state rows with output symbols from said second subset;

defining a next-state table of next states for said encoder, said next-state table having present state rows and input symbol columns, wherein the next states are defined as a function of symbols input to said encoder and a present state of said encoder, defining said next-state look-up table further comprising the steps of;

loading first ones of said present state rows with next states of said encoder until at least one of said first present state rows is full and all of said next state values have been used; and

loading other ones of said present state rows with next states that are cyclicly shifted from said next states in each of said first ones of said present state rows until all of said present state rows are filled;

implementing said output and next-state tables within said encoder so that output symbols from said encoder are determined by input symbols to said encoder and the present state of said encoder in accordance with said output table, and transitions from the present state of said encoder to the next state of said encoder are performed in accordance with said next-state table; and

mapping said output symbols into signals having phase and amplitude characteristics corresponding to points on said signal constellation.

5. A method as defined in claim 4, wherein said coordinate points of said signal constellation are assigned output symbols according to natural mapping techniques when the predominant channel interference is Additive White Gaussian Noise.

6. A method as defined in claim 4, wherein said coordinate points of said signal constellation are assigned to output symbols according to Gray coding techniques when the predominant channel interference is Rayleigh fading.