# US 5,703,911 A · Decoding method for trellis codes with large free distances

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,703,911 A
- Document ID: US5703911A
- Status: Granted
- Kind: A
- Application number: 08/516,217
- Filed: 1995-08-17
- Granted: 1997-12-30
- Earliest claimed: 1995-08-17
- Assignees: Chung-Chin Chen
- Inventors: Mao-Chao Lin; Jia-Yin Wang
- Web page: https://patentgrep.com/patent/US5703911A

## CPC

- H03M 13/256: {with trellis coding, e.g. with convolutional codes and TCM}
- H03M 13/41: using the Viterbi algorithm or Viterbi processors
- H04L 27/186: {in which the information is carried by both the individual signal points and the subset to which the individual signal points belong, e.g. coset coding or related schemes}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

This invention is a decoding method for a special class of trellis codes which have large free distances. The encoding of the trellis code to be decoded can be implemented by employing a single binary convolutional code followed by more than one processor. The decoding can be implemented by using the trellis of the binary convolutional code and additional processors.

## Claims

### Claim 1

A decoding method for a trellis code T of which the encoding can be implemented by first using an encoder of a binary trellis code C.sup.(1) to encode an r-bit message u(t) into an intermediate binary m-tuple v.sup.(l) (t) at a t-th time unit which is sequentially converted into binary m-tuples v.sup.(2) (t), . . . , v.sup.(L) (t) and a signal point v.sup.(L+1) (t) in a signal space .OMEGA. through L (L.gtoreq.2) processors, comprising the decoding steps of:
(a) at a (t+.LAMBDA..sup.(l) + . . . +.LAMBDA..sup.(L))-th time unit, a processor P.sup.(L) determining a set T.sub.M.sup.(L) (t+.LAMBDA..sup.(l) + . . . +.LAMBDA..sup.(L-1)) which consists of 2.sup.m metrics for the 2.sup.m possible values of v.sup.(L) (t+.LAMBDA..sup.(1) + . . . +.LAMBDA..sup.(L-1)), based on part of the set {y(t+i): i.ltoreq..LAMBDA..sup.(1) + . . . +.LAMBDA..sup.(L) } and part of the set {v.sup.(L) (t-j): j.gtoreq..lambda.}; feeding the metric set T.sub.M.sup.(L) (t+.LAMBDA..sup.(1) + . . . +.LAMBDA..sup.(L-1)) into a processor P.sup.(L-1) ; wherein y(t+i) is a received symbol to be decoded, .LAMBDA..sup.(1), . . . , .LAMBDA..sup.(L) are nonnegative constants and .lambda. is a truncation length to be used in decoding C.sup.(1) ;
(b) for l=L-1, L-2, . . . ,1, a processor P.sup.(l) determining a set T.sub.M.sup.(l) (t+.LAMBDA..sup.(1) + . . . +.LAMBDA..sup.(l-1)) which consists of 2.sup.m metrics for the 2.sup.m possible values of v.sup.(l) (t+.LAMBDA..sup.(1) + . . . +.LAMBDA..sup.(l-1)) based on part of {T.sub.M.sup.(l+1) (t+i): i.ltoreq..LAMBDA..sup.(1) + . . . +.LAMBDA..sup.(l) } and part of the set {v.sup.(l) (t-j): j.gtoreq..lambda.}; feeding the metric set T.sub.M.sup.(l) (t+.LAMBDA..sup.(1) + . . . +.LAMBDA..sup.(l-1)) into a processor P.sup.(l-1) ; wherein .LAMBDA..sup.(l) is a nonnegative constant;
(c) a processor P.sup.(0) recovering the transmitted symbol u(t-.lambda.+1) and v.sup.(1) (t-.lambda.+1) by applying the Viterbi decoding algorithm to the trellis of C.sup.(1) and using part of the set {T.sub.M.sup.(1) (t-i): i.gtoreq.0}; feeding back the recovered v.sup.(1) (t-.lambda.+1) to P.sup.(1) ;
(d) for l=1,2, . . . ,L-1, P.sup.(l) processing the set {v.sup.(l) (t-j): j.gtoreq..lambda.-1} and determining v.sup.(l+1) (t-.lambda.+1) which is then fed back to P.sup.(l+1).

### Claim 2 (depends on 1)

A decoding method as in claim 1, wherein the encoder of said single binary trellis code C.sup.(1) is replaced by the encoders of a plurality of binary trellis codes which together convert u(t) into v.sup.(1) (t)=(v.sub.1.sup.(1) (t), v.sub.2.sup.(1) (t), . . . , v.sub.m.sup.(1) (t)), which is then processed by L multilevel delay processors and L signal mappers; and wherein said Viterbi decoding algorithm for C.sup.(1) used in the processor P.sup.(0) is replaced by a plurality of Viterbi decoding algorithms for said plurality of binary trellis codes.

### Claim 3 (depends on 1, 2)

An decoding method as in claims 1 or 2, wherein the encoding of said trellis code T can be implemented by the steps of:
i) using the encoder of a single binary trellis code C.sup.(1) to encode an r-bit message u(t) at the t-th time unit so as to obtain an m-bit output v.sup.(1) (t)=(v.sub.1.sup.(1) (t),v.sub.2.sup.(1) (t), . . . ,v.sub.m.sup.(1) (t));
ii) processing said output of the encoder through a multilevel delay processor Q.sup.(1) to obtain a processed output s.sup.(1) (t)=(s.sub.1.sup.(1) (t), s.sub.2.sup.(1) (t), . . . , s.sub.m.sup.(1) (t)) such that ##EQU11## wherein .lambda..sub.1.sup.(1), .lambda..sub.2.sup.(1), . . . , .lambda..sub.m.sup.(1) are nonnegative constants;
iii) feeding said output of Q.sup.(1) into a signal mapper S.sup.(1) to select a signal point w.sup.(1) (s.sup.(1) (t))=v.sup.(2) (t)=(v.sub.1.sup.(2) (t),v.sub.2.sup.(2) (t), . . . ,v.sub.m.sup.(2) (t));
iv) for l=2, 3, . . . , L, feeding the output v.sup.(l) (t) into a multilevel delay processor Q.sup.(l) to obtain a processed output s.sup.(l) (t)=(s.sub.1.sup.(l) (t),s.sub.2.sup.(l) (t), . . . ,s.sub.m.sup.(l) (t)), such that ##EQU12## wherein .lambda..sub.1.sup.(l), .lambda..sub.2.sup.(l), . . . , .lambda..sub.m.sup.(l) are nonnegative constants, and then feeding s.sup.(l) (t) into a signal mapper S.sup.(l) to select a signal point w.sup.(l) (s.sup.(l) (t))=v.sup.(l+1) (t), whereby if l<L, v.sup.(l+1) (t) is a binary m-tuple and if l=L, v.sup.(l+1) (t) is in the signal space .OMEGA. and is the output signal point.

### Claim 4 (depends on 3)

A decoding method as in claim 3, wherein the parameter .lambda..sup.(l) of the processor P.sup.(l) is no less than .SIGMA..sub.i=1.sup.m .lambda..sub.i.sup.(l) for 1.ltoreq.l.ltoreq.L.

### Claim 5 (depends on 3)

A decoding method as in claim 3, wherein said constants .lambda..sub.1.sup.(l), .lambda..sub.2.sup.(l), . . . , .lambda..sub.m.sup.(l) are distinct values and/or at least one of the constants .lambda..sub.1.sup.(l), .lambda..sub.2.sup.(l), . . . , .lambda..sub.m.sup.(l) is not zero.

### Claim 6 (depends on 3)

A decoding method as in claim 3, wherein said constants .lambda..sub.1.sup.(l), .lambda..sub.2.sup.(l), . . . , .lambda..sub.m-1.sup.(l) are all identical to a constant .lambda..sup.(l) and .lambda..sub.m.sup.(l) =0.

### Claim 7 (depends on 1, 2)

A decoding method as in claims 1 or 2, wherein said binary trellis code or a plurality of binary trellis codes is/are a linear and time-invariant code or a plurality of linear and time-invariant codes respectively, i.e., a binary convolutional code or a plurality of binary convolutional codes.

### Claim 8 (depends on 1, 2)

A decoding method as in claims 1 or 2, wherein the signal space .OMEGA. is a signal constellation; then said method can be used to decode trellis coded modulation.

### Claim 9 (depends on 1, 2)

A decoding method as in claims 1 or 2, wherein the signal space .OMEGA. is a collection of binary m-tuples; then said method can be used to decode binary trellis codes.

### Claim 10 (depends on 1, 2)

A decoding method as in claims 1 or 2, wherein the r-bit information, u(t), represents m/m.sup.(1) binary (r.multidot.m.sup.(1) /m)-tuples, whereby m.sup.(1) is a positive integer.

### Claim 11 (depends on 1, 2)

A decoding method as in claims 1 or 2, wherein the binary m-tuple v.sup.(l) (t), 1.ltoreq.l.ltoreq.L, can be decomposed into m/m.sup.(l) binary m.sup.(l) -tuples, wherein m.sup.(l) is a positive integer; and v.sup.(L+1) (t) represents m/m.sup.(L+1) signal points in .OMEGA. which consists of 2.sup.(m.spsp.(L+1).sup.) signal points, wherein m.sup.(L+1) is a positive integer.