Cyclic trelles coded modulation

• US 5,784,417 A
• Filed: 12/11/1995
• Issued: 07/21/1998
• 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): Chin, Stephen
• Assistant Examiner(s): Le, Amanda T.
• Application Number:
  US08/570,289
• Time in Patent Office: 953 Days
• Field of Search: 375/262, 375/265, 375/341, 371/37.8, 371/43, 371/43.4, 371/43.7
• US Class Current: 375/341
• 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 receiver for a trellis-coded multi-level modulation communication system comprising:

a trellis decoder which receives a baseband signal, said trellis decoder comprising;

means for reconstructing a trellis structure defined by a state transition look-up table wherein a set of present states is partitioned into subsets having successive members, and next state values assigned to each of said present state subsets are shifted cyclicly for successive members of said present state subset;

means for determining input and output symbols associated with branches of said trellis structure as defined by an encoder output look-up table wherein said present states are partitioned into two subsets and the outputs are partitioned into two subsets so that said output look-up table outputs a symbol which belongs to a first output subset when in one of said present state subsets and outputs a symbol which belongs to a second output subset when in the other of said present state subsets;

a calculation circuit which determines the Euclidean distances between points on a phase/amplitude coordinate system corresponding to the received signals and points of a phase/amplitude signal constellation corresponding to signals associated with branches on said trellis structure; and

comparator and selector circuits for selecting the most likely path of the received signal on said trellis structure on the basis of said determined Euclidean distances.

2. A receiver for a trellis-coded multi-level modulation communication system comprising:

a trellis decoder which receives a baseband signal, said trellis decoder comprising;

first signal processing circuitry for reconstructing a trellis structure defined by a state transition input/output table wherein a set of present states is partitioned into subsets having successive members, and next state values assigned to each of said present state subsets are shifted cyclicly for successive members of said present state subset;

second signal processing circuitry for determining input and output symbols associated with branches of said trellis structure as defined by an encoder output input/output table wherein said present states are partitioned into two subsets and the outputs are partitioned into two subsets so that said encoder output input/output table outputs a symbol which belongs to a first output subset when in one of said present state subsets and outputs a symbol which belongs to a second output subset when in the other of said present state subsets;

a calculation circuit which determines distances between points on a phase/amplitude coordinate system corresponding to the received signals and points of a phase/amplitude signal constellation corresponding to signals associated with branches on said trellis structure; and

comparator and selector circuits for selecting the most likely path of the received signal on said trellis structure on the basis of said determined distances.

3. A receiver as defined in claim 2, wherein said first and second signal processing circuitry include a Viterbi decoder which utilizes soft-decision Viterbi decoding methods.

4. A receiver as defined in claim 2, further comprising a constellation signal mapper which maps said received signals to points on said phase/amplitude signal constellation.

5. A receiver for a trellis-coded multi-level modulation communication system comprising:

a trellis decoder which receives a baseband signal, said trellis decoder comprising;

a first look-up table for reconstructing signal constellation points divided into two symmetrical sets of symbol points wherein said first look-up table is defined as an inverse of an output table of output symbols wherein said output table is defined to have present state rows and input symbol columns wherein said output symbols are determined as a function of symbols input to a trellis encoder and a present state of said trellis encoder, said output table being further defined by having each of said output symbols assigned to said signal constellation points, said signal constellation points partitioned into a first subset of output symbols and a second subset of output symbols, even ones of said present state rows loaded with output symbols from said first subset, and odd ones of said present state rows loaded with output symbols from said second subset; and

a second look-up table for cyclic trellis decoding data mapped according to said signal constellation.

6. A receiver as defined in claim 5, wherein said second look-up table is defined as an inverse of a next-state table, said next-state table defined to have 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, said next-state look-up table further defined to have:

first ones of said present state rows loaded 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

other ones of said present state rows loaded 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.