Decoding technique for tail biting codes

• US 5,920,597 A
• Filed: 09/16/1996
• Issued: 07/06/1999
• Est. Priority Date: 09/16/1996
• Status: Expired due to Term

• Current Assignee: Unwired Planet LLC (JP Morgan Chase & Co)
• Original Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Khayrallah, Ali S., Hassan, Amer
• Primary Examiner(s): Chan, Jason
• Assistant Examiner(s): Corrielus, Jean B.
• Application Number:
  US08/714,684
• Time in Patent Office: 1,023 Days
• Field of Search: 371/8, 371/9, 371/37.6, 371/37.4, 371/41, 371/69.1, 371/70, 371/67.1, 371/36, 371/43.4, 371/43.6, 371/43.7, 375/265, 375/262, 375/285, 375/254, 375/296, 375/341, 375/261, 375/340
• US Class Current: 375/265
• CPC Class Codes: H03M 13/4123 implementing the return to a predetermined state
• CPC Class Codes: H03M 13/413 tail biting Viterbi decoding
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing
• CPC Class Codes: H04L 1/0054 Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms

Abstract

A method for decoding encoded digital data. A decoder generates a replicated decoding trellis and performs some number D^max of decoding operations using the replicated trellis. Each decoding pass is offset by some amount δ, and the results of each pass are stored and compared with prior results to generate a final output information sequence.

Claims

1. A method for decoding encoded digital communication signals, comprising:

receiving encoded digital communication signals;

performing a first decoding of a decoding trellis generated from the received digital communication signals to generate a first decoded information sequence;

performing a second decoding of the decoding trellis to generate a second decoded information sequence;

comparing the second decoded information sequence with the first decoded information sequence to determine common information between the first and second decoded information sequences;

performing one or more subsequent decodings of the decoding trellis to generate one or more subsequent decoded information sequences, each subsequent decoding ignoring trellis locations containing common information;

comparing each subsequent decoded information sequence to portions of a previous decoded information sequence which does not contain common information; and

outputting a final decoded information sequence including conmmon information generated from all decodings.

2. The method of claim 1, wherein the final decoded information further includes portions of a selected one of decoded information sequences.

3. The method of claim 2, wherein the selected decoded information sequence is the first decoded information sequence.

4. The method of claim 1, wherein the decoding trellis is of length nL, where n is a rational number, and is generated by duplicating and concatenating a first decoding trellis of length L.

5. The method of claim 4, wherein the first decoding is performed by starting from a first index point 2L-x in the decoding trellis, selecting a best state at the first index point 2L-x, and tracing back a best path of length L in the decoding trellis to generate the first decoded information sequence, wherein x is a specified value in said decoding trellis.

6. The method of claim 5, wherein the second decoding is performed by starting from a second index point 2L-x-δ

, selecting a best state at the second index point 2L-x-δ

, tracing back a best path of length L in the decoding trellis, and reordering information derived from the tracing back from the second index point to generate the second decoded information sequence, wherein δ

is an upset value in said decoding trellis.

7. The method of claim 1, wherein the encoded digital communication signals are encoded with error control coding.

8. The method of claim 1, wherein each subsequent decoding is performed by starting from a subsequent index point offset by δ

from a previous index point, wherein δ

is an upset value in said decoding trellis.

9. The method of claim 1, wherein the final decoded information sequence further includes information derived from a majority logic operation of all portions of the decoding trellis not containing common information.

10. The method of claim 9, wherein the final decoded information sequence further includes portions of a selected one of decoded information sequences.

11. A communication system, comprising:

an encoder for encoding information signals with error control coding;

a modulator for modulating and transmitting encoded information signals; and

a receiver for receiving and decoding the encoded information signals, the receiver including a convolutional decoder which generates a plurality of alternative decoded sequences and outputs subsets of the alternative decoded sequences as correct sequences if the subsets occur in more than one of the alternative decoded sequences.

12. The system of claim 11, wherein the error control coding is a convolutional code with tail biting.

13. The system of claim 11, wherein the decoder generates alternative sequences by forming a decoding trellis from the encoded information signals, performing a first decoding of the decoding trellis to generate a first decoded information sequence;

performing a second decoding of the decoding trellis to generate a second decoded information sequence;

comparing the second decoded information sequence with the first decoded information sequence to determine common subsets between the first decoded information sequence and the second decoded information sequence;

performing one or more subsequent decodings of the decoding trellis to generate one or more subsequent decoded information sequences;

comparing each subsequent decoded information sequence to portions of one or more previous decoded information sequences to determine additional common subsets; and

outputting a final decoded information sequence including the common subsets generated from all decodings.

14. The system of claim 13, wherein the decoding trellis is of length nL, where n is a rational number, and is generated by replicating and concatenating a first decoding trellis of length L.

15. The method of claim 14, wherein the first decoding is performed by starting from a first index point 2L-x in the decoding trellis, selecting a best state at the first index point 2L-x, and tracing back a best path of length L in the decoding trellis to generate the first decoded information sequence, wherein x is a specified value in said decoding trellis.

16. The method of claim 15, wherein the second decoding is performed by starting from a second index point 2L-x-δ

, selecting a best state at the second index point 2L-x-δ

, tracing back a best path of length L in the decoding trellis, and reordering information derived from the tracing back from the second index point to generate the second decoded information sequence, wherein δ

is an upset value in said decoding trellis.

17. The method of claim 14, wherein each subsequent decoding is performed by starting from a subsequent index point offset by δ

from a previous index point, wherein δ

is an upset value in said decoding trellis.

18. The system of claim 11, wherein each of the subsets is of a predetermined length.

19. The system of claim 13, wherein the decoder further outputs portions of a selected one of the alternative decoded sequences.

20. The system of claim 19, wherein the selected one is the first decoded information sequence.

21. A decoder for decoding encoded digital communication signals, comprising:

means for receiving encoded digital communication signals;

means for performing a first decoding of a decoding trellis generated from the received digital communication signals to generate a first decoded information sequence;

means for performing a second decoding of the decoding trellis to generate a second decoded information sequence;

means for comparing the second decoded information sequence with the first decoded information sequence to determine common information between the first and second decoded information sequences;

means for performing one or more subsequent decodings of the decoding trellis to generate one or more subsequent decoded information sequences, each subsequent decoding ignoring trellis locations containing common information;

means for comparing each subsequent decoded information sequence to portions of a previous decoded information sequence which does not contain common information; and

means for outputting a final decoded information sequence including common information generated from all decodings.

22. A method for decoding encoded digital communication signals, comprising the steps of:

receiving encoded digital communication signals;

performing a predetermined number of decodings of a decoding trellis generated from the received digital communication signals to generate a predetermined number of decoded information sequences, wherein the decoding trellis is of length nL, and is formed by replicating and concatenating a rational number n of first decoding trellises of length L; and

determining an output decoded information sequence from a majority logic calculation performed for each sequence position of the predetermined number of decoded information sequences.

23. The method of claim 22, wherein the output decoded information sequence further includes, for each sequence position in which the majority logic calculation fails, items from a selected one of the predetermined number of decoded information sequences.

24. The method of claim 22, wherein the encoded digital communication signals are received in blocks.

25. A method for decoding encoded digital communication signals, comprising the steps of:

receiving encoded digital communication signals; and

performing a predetermined number of decodings of a decoding trellis generated from the received digital communication signals to generate a predetermined number of decoded information sequences, wherein the decoding trellis is of length nL, and is formed by replicating and concatenating a rational number n of first decoding trellises of length L.