Method and apparatus for encoding and decoding convolutional codes

• US 5,416,787 A
• Filed: 07/29/1992
• Issued: 05/16/1995
• Est. Priority Date: 07/30/1991
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Nakamura, Makoto, Kodama, Tomoko, Saito, Tatsunori
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US07/921,507
• Time in Patent Office: 1,021 Days
• Field of Search: 371/43, 371/374, 371/44, 371/45, 371/46, 371/41
• US Class Current: 714/790
• CPC Class Codes: H03M 13/3961 Arrangements of methods for branch or transition metric calculation
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors
• 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
• CPC Class Codes: H04L 1/0069 Puncturing patterns
• CPC Class Codes: H04L 2001/0098 Unequal error protection

Abstract

A reduction of the redundancy due to the use of the convolutional codes as the error correction codes is achieved by a convolutional encoding at an identical encoding rate and a puncture process using different puncture rates for different classes of the input signals classified by the error sensitivity of each bit. A reduction of the decoding delay time without deteriorating the decoding error rate is achieved by updating the survivor path by remaining bits of the selected survivor path for each state other than the oldest bit and an additional bit indicative of the each state to which a transition is made at the present stage of decoding. A reduction of a circuit size of a Viterbi decoder is achieved by using a single RAM for memorizing a path metric and a survivor path for each state at an immediately previous stage of decoding together in each word of the memory capacity. A reduction of the decoding error rate for the data block encoded by the convolutional encoding is achieved by using the (i+N+j) bits of decoder input signals containing entire N bits of the received signals, preceded by last i bits of the received signals and followed by first j bits of the received signals.

Claims

1. An apparatus for error correction encoding using convolutional codes, comprising:

means for classifying input signals containing a plurality of bits into a plurality of classes according to an error sensitivity of each bit;

encoder means for applying a convolutional encoding to the input signals classified into said plurality of classes, using an identical encoding rate for all the classes, to obtain encoded signals; and

puncture means for carrying out a puncture process for puncturing selected bits of the encoded signals, using different puncture rates for the encoded signals corresponding to different ones of said plurality of classes, to obtain error correction encoded output signals in which different classes of the input signals are encoded at different encoding rates according to the error sensitivity of each bit.

2. The apparatus of claim 1, wherein the error correction encoded output signals contains bits corresponding to the different classes of the input signals in an ascending order of the puncture rates used in puncturing the encoded signals corresponding to the different classes of the input signals.

3. The apparatus of claim 1, wherein the error correction encoded output signals contains bits corresponding to the different classes of the input signals in a descending order of the puncture rates used in puncturing the encoded signals corresponding to the different classes of the input signals.

4. A Viterbi decoder for decoding convolutional codes encoded by a convolutional encoder, comprising:

branch metric calculation means for calculating a branch metric for each state at a present stage of decoding;

path metric memory means for memorizing a path metric for each state at an immediately previous stage of decoding;

path memory means for memorizing a survivor path for each state at the immediately previous stage of decoding;

ACS circuit means for selecting a survivor path for each state at the present stage of decoding, by calculating the path metric for each state at the present stage of decoding from the branch metric calculated by the branch metric calculation means, the path metric memorized in the path metric memory means, and the survivor path memorized in the path memory means, the ACS circuit means outputs an oldest bit of the selected survivor path for each stage at the present stage of decoding, and updates the survivor path memorized in the path memory by remaining bits of the selected survivor path for each state at the present stage of decoding other than the oldest bit to be outputted and an additional bit indicative of said each state to which a transition is made at the present stage of decoding; and

output generation means for determining a decoded output according to the oldest bit of the selected survivor path for each state at the present stage of decoding outputted from the ACS circuit means.

5. The Viterbi decoder of claim 4, wherein the additional bit is an encoder input bit which caused the transition to said each state at a time of encoding by the convolutional encoder.

6. A Viterbi decoder for decoding convolutional codes encoded by a convolutional encoder, comprising:

branch metric calculation means for calculating a branch metric for each state at a present stage of decoding;

memory means, formed by a single RAM having a memory capacity of 2^m words×

(L+N) bits, where m is a memory length of the convolutional encoder, L is a truncation length for each survivor path used in the Viterbi decoder, and N is a number of bits used for expressing each path metric, for memorizing a path metric and a survivor path for each state at an immediately previous stage of decoding together in each word of the memory capacity;

ACS circuit means for selecting a survivor path for each state at the present stage of decoding, by calculating the path metric for each state at the present stage of decoding from the branch metric calculated by the branch metric calculation means, and the path metric and the survivor path memorized in the memory means, the ACS circuit means outputs an oldest bit of the selected survivor path for each stage at the present stage of decoding; and

output generation means for determining a decoded output according to the oldest bit of the selected survivor path for each state at the present stage of decoding outputted from the ACS circuit.

7. The Viterbi decoder of claim 6, wherein each stage of decoding includes 2×

2^m processing timing units for carrying out a reading of the path metric and the survivor path for each state at the immediately previous stage of decoding memorized in the memory means to the ACS circuit means and a writing of the path metric and the survivor path for each state at the present stage of decoding obtained by the ACS circuit means into the memory means.

8. The Viterbi decoder of claim 6, wherein the ACS circuit means also updates the path metric and the survivor path memorized in the memory means simultaneously.

9. A communication system for transmitting data block containing K bits encoded by convolutional codes, comprising:

a convolutional encoder for applying a convolutional encoding to the data block, in which the convolutional encoding starts from a state in which first m bits of the data block are entered in the convolutional encoder, and the convolutional encoding of remaining (K-m) bits of the data block are followed by the convolutional encoding of the first m bits of the data block, to obtain encoded signals containing N bits;

memory means for memorizing the N bits of the encoded signals (R₀, R₁, . . . , R_N-1), and outputting decoder input signals containing (i+N+j) bits arranged in an order of (R_N-i+h(mod N), R_N-i+h+1(mod N), . . . , R_N-1+h(mod N) ;

R_h(mod N), R_h+1(mod N), . . . , R_N-1+h(mod N) ;

R_h(mod N), R_h+1(mod N), R_h+j-1(mod N)), where i is a positive integer, j is a non-negative integer, and h is a non-negative integer; and

a Viterbi decoder for decoding the (i+N+j) bits of the decoder input signals in said order in which the decoder input signals are outputted from the memory means.

10. The communication system of claim 9, wherein the (i+N+j) bits of the decoder input signals comprises first i bits corresponding to last i bits of the encoded signals memorized in the memory means, next N bits corresponding to entire N bits of the encoded signals memorized in the memory means, and last j bits corresponding to first j bits of the encoded signals memorized in the memory means.

11. The communication system of claim 10, wherein the Viterbi decoder obtains a provisional final state by decoding the first i bits of the decoder input signals, and then decodes the next N+j bits of the decoder input signals by setting the provisional final state as an initial state.

12. The communication system of claim 11, wherein i is a number of stages required in the Viterbi decoder to obtain the provisional final state, and j is a truncation length for each survivor path used in the Viterbi decoder.

13. The communication system of claim 9, further comprising an interleaver for interleaving the encoded signals obtained by the convolutional encoder, and wherein the memory means comprises a deinterleaver for deinterleaving the memorized encoded signals before outputting the decoder input signals.

14. A method of transmitting data block containing K bits encoded by convolutional codes, comprising the steps of:

(a) applying the convolutional encoding to the data block, in which the convolutional encoding starts from a state in which first m bits of the data block are entered in a convolutional encoder, and the convolutional encoding of remaining (K-m) bits of the data block are followed by the convolutional encoding of the first m bits of the data block, to obtain encoded signals containing N bits;

(b) memorizing the N bits of the encoded signals (R₀, R₁, . . , R_N-1), and outputting decoder input signals containing (i+N+j) bits arranged in an order of (R_N-i+h(mod N), R_N-i+h+1(mod N), . . . , R_N-1+h(mod N) ;

R_h(mod N), R_h+1(mod N), . . . , R_N-1+h(mod N) ;

R_h(mod N), R_h+1(mod N), . . . , R_h+j-1(mod N)), where i is a positive integer, j is a non-negative integer, and h is a positive integer; and

(c) decoding the (i+N+j) bits of the decoder input signals in said order in which the decoder input signals are outputted, by a Viterbi decoder.

15. The method of claim 14, further comprising the step of interleaving the encoded signals obtained at the step (a), and wherein at the step (b), the memorized encoded signals are deinterleaved before outputting the decoder input signals.

16. A method of decoding data encoded by a convolutional encoder having a memory length equal to m and capable of taking 2^m states;

comprising the steps of;

(a) memorizing the data;

(b) calculating a likelihood for each of the 2^m states of the convolutional encoder to be an initial state, from at least a part of the data memorized at the step (a); and

(c) decoding the data memorized at the step (a) by using the likelihood for each state to be the initial state calculated at the step (b), by a Viterbi decoder.

17. The method of claim 16, wherein the step (b) further comprises the steps of:

(b1) calculating a branch metric for each state with respect to each of last i bits of the data memorized at the step (a), where i is a positive integer; and

(b2) calculating the path metric for each state with respect to each of the last i bits of the data memorized at the step (a), from the branch metric calculated at the step (b1), and outputting the path metric calculated for each state with respect to a last bit of the last i bits of the data memorized at the step (a) as the likelihood.

18. An apparatus for decoding data encoded by a convolutional encoder capable of taking M states;

comprising;

Viterbi decoding means for decoding the data more than once with more than one different settings of an initial state of a trellis to be a different one of the M states of the convolutional encoder, to obtain a plurality off decoded outputs; and

output determining means for selecting one of said plurality of decoded outputs of the Viterbi decoding unit.

19. The apparatus of claim 18, wherein the Viterbi decoding means includes M Viterbi decoders, each of which has the initial state of the trellis set to be one of the M states different from the initial states used in other ones of the M Viterbi decoder.

20. The apparatus of claim 18, wherein the Viterbi decoding means includes:

control means for setting an initial state of the trellis to be each of the M states sequentially; and

a Viterbi decoder for decoding the data, for each setting of the initial state of the trellis set by the control means.