Method and apparatus for generating super-orthogonal convolutional codes and the decoding thereof

• US 5,193,094 A
• Filed: 03/07/1990
• Issued: 03/09/1993
• Est. Priority Date: 03/07/1990
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Viterbi, Andrew J.
• Primary Examiner(s): Atkinson, Charles E.
• Assistant Examiner(s): Lo, Allen M.
• Application Number:
  US07/489,677
• Time in Patent Office: 1,098 Days
• Field of Search: 371/43, 371/44, 371/45, 341/94
• US Class Current: 714/795
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes

Abstract

An encoder and decoder for generating and decoding convolutional codes of enhanced orthogonality. In an exemplary embodiment the encoder includes a K bit length shift register for receiving an input serial stream of information bits and providing for each input bit a K bit parallel output to an orthogonal code sequence generator where one of 2^K-1 symbol sequences is generated with each symbol sequence of a K-2 symbol length. The encoded symbol stream is decoded using an orthogonal function generator driven by a K-2 binary counter to generate all possible symbol sequences for comparison with each received symbol sequence. The output of the comparison is Viterbi decoded to provide the original stream of information bits. Corresponding methods of encoding the information bits and decoding of the symbol sequences are included.

Claims

1. An apparatus for convolutional encoding of information bits comprising:

data converter means for receiving a serial input of information bits and for providing, for each received input information bit, a corresponding parallel output of a group of K most recently received ones of said received information bits, a most recently received information bit through a least recently received information bit respectively identified as first through K^th information bits; and

orthogonal sequence generator means for receiving each group of K information bits, for performing a logical "exclusive-or" operation on said first and K^th information bits of each received group of K information bits, for generating for each each received group of K information bits a plurality of predetermined sequences of K-2 binary count bits, for performing a logical "and" operation on each one of a second through a K-1 information bit of each received group of K information bits with respect to a corresponding binary count bit in each sequence of binary count bits, for performing a parity check on a result of each set of logical "and" operations and a result of said logical "exclusive-or" operation, and for providing a resultant output sequence of 2^K-2 symbols.

2. The apparatus of claim 1 wherein said data converter means comprises a shift register having a data input, a clock input and K register stages each with a corresponding stage output.

3. The apparatus of claim 1 wherein said orthogonal sequence generator means comprises:

a K-2 bit binary counter having a clock input and K-2 outputs;

a plurality of AND gates each having a pair of inputs and an output, one of each AND gate inputs for receiving a respective one of said second through K-1 information bits and the other one of each AND gate inputs coupled to a respective one of said counter outputs;

a plurality of EXCLUSIVE OR gates each having a pair of inputs and an output, a first EXCLUSIVE OR gate of said plurality of EXCLUSIVE OR gates having a pair of inputs for respectively receiving said first and K^th information bits, a last EXCLUSIVE OR gate of said plurality of EXCLUSIVE OR gates having one input coupled to an output of said first EXCLUSIVE OR gate, a cascaded sequence of a second EXCLUSIVE OR gate through a next-to-last EXCLUSIVE OR gate of said plurality of EXCLUSIVE OR gates with said second EXCLUSIVE OR gate having a pair of inputs respectively coupled to an output of a first and a second AND gates of said plurality of AND gates, a third EXCLUSIVE OR gate through said next-to-last EXCLUSIVE OR gate of said plurality of EXCLUSIVE OR gates each having one input respectively coupled to an output of a third AND gate through a last AND gate of said plurality of AND gates, and with another input of each of said third EXCLUSIVE OR gate through said next-to-last EXCLUSIVE OR gate respectively coupled to an output of a preceding EXCLUSIVE OR gate in said cascaded sequence of said second EXCLUSIVE OR gate through said next-to-last EXCLUSIVE OR gate with an output of said next-to-last EXCLUSIVE OR gate coupled to another input of said last EXCLUSIVE OR gate.

4. The apparatus of claim 2 wherein said orthogonal sequence generator means comprises:

a K-2 bit binary counter having a clock input and K-2 outputs;

a plurality of AND gates each having a pair of inputs and an output, one input of a first through a last AND gate of said plurality of said AND gates respectively coupled to a second through a K-1 output of said shift register and another input of said second through said last AND gate respectively coupled to a first through a last output of said K-2 counter outputs;

a plurality of EXCLUSIVE OR gates, each having a pair of inputs and an output, a first EXCLUSIVE OR gate of said plurality of EXCLUSIVE OR gates having a pair of inputs coupled to a first and a K^th stage output of said shift register, a last EXCLUSIVE OR gate of said plurality of EXCLUSIVE OR gates having one input coupled to an output of said first EXCLUSIVE OR gate, a cascaded sequence of a second EXCLUSIVE OR gate through a next-to-last EXCLUSIVE OR gate of said plurality of EXCLUSIVE OR gates with said second EXCLUSIVE OR gate having a pair of inputs respectively coupled to an output of said first AND gate and a second AND gate of said plurality of AND gates, a third EXCLUSIVE OR gate through said next-to-last EXCLUSIVE OR gate of said plurality of EXCLUSIVE OR gates each having one input respectively coupled to an output of a third AND gate through said last AND gate of said plurality of AND gates, and with another input of each of said third EXCLUSIVE OR gate through said next-to-last EXCLUSIVE OR gate respectively coupled to an output of a preceding EXCLUSIVE OR gate in said cascaded sequence of said second EXCLUSIVE OR gate through said next-to-last EXCLUSIVE OR gate with an output of said next-to-last EXCLUSIVE OR gate coupled to another input of said last EXCLUSIVE OR gate.

5. A method for convolutional encoding information bits comprising the steps of:

converting a serial input of information bits into a corresponding parallel output of the K most recently received information bits of said serial input of information bits wherein a most recently received information bit through a least recently received information bit are respectively identified as first through K^th information bits;

performing a logical "exclusive-or" operation on said first and K^th information bits;

generating, for each input of an information bit of said serial input of information bits, a plurality of predetermined sequences of K-2 binary count bits wherein each bit position in each sequence of K-2 binary count bits corresponds to a second through K-1 information bits;

performing a logical "and" operation on each respective one of said second through K-1 information bits with respect to each corresponding binary count bit in each sequence of binary count bits;

performing a parity check on a result of each logical "and" operations and a result of said logical "exclusive-or" operation; and

providing an output sequence of 2^K-2 symbols.

6. The method of claim 5 wherein said step of performing a parity check comprises the steps of:

performing a first parity check logical "exclusive-or" operation on each result of a first and a second one of said logical "and" operation; and

performing a sequence of a second through a last parity check logical "exclusive-or" operation each upon each result of a preceding one of said first through a next-to-last parity check logical "exclusive-or" operation with respect to each of a third through a last one of said logical "and" operations.

7. A data encoder comprising:

a register having an input for receiving an input sequence of data bits, and having a first through a K output at which is provided a respective one of the last K received bits of said input sequence of data bits;

an input EXCLUSIVE OR gate having a pair of inputs respectively coupled to said first and K outputs of said register, and an output;

an orthogonal function sequence generator having K-2 inputs each coupled to a respective one of a second through a K-1 output of said register, and having an output; and

an output EXCLUSIVE OR gate having a pair of inputs respectively coupled to said first EXCLUSIVE OR gate output and said generator output, and an output.

8. The data encoder of claim 7 wherein said register comprises a shift register having a serial data input, a clock input for receiving a clock signal of a data bit rate of R, and K register stages each with a corresponding register stage output, a first and a K register stage output coupled to said input EXCLUSIVE OR gate.

9. The data encoder of claim 7 wherein said orthogonal function sequence generator comprises:

a K-2 bit binary counter having a clock input for receiving a clock signal of a rate of 2^K-2 R, where R is a data bit rate, and having K-2 counter outputs;

a plurality of AND gates each having a pair of inputs and an output, a first through a K-2 AND gate of said plurality of AND gates each having one input respectively coupled to a second through a K-1 output of said register, and said first through said K-2 AND gate each having another input respectively coupled to a first through a K-2 output of said register; and

a plurality of generator EXCLUSIVE OR gates arranged in a cascaded sequence, each having a pair of inputs and an output, a first generator EXCLUSIVE OR gate inputs respectively coupled to an output of said first and second AND gate outputs, a second through a K-2 generator EXCLUSIVE OR gates each having one input coupled to a respective output of a third through said K-2 generator EXCLUSIVE OR gates with said third through said K-2 generator EXCLUSIVE OR gates other input coupled to a preceding generator EXCLUSIVE OR gate in said cascaded sequence, said K-2 generator EXCLUSIVE OR gate output coupled as an input to said output EXCLUSIVE OR gate.

10. The data encoder of claim 8 wherein said orthogonal function sequence generator comprises:

a K-2 bit binary counter having a clock input for receiving a clock signal of a rate of 2.sup.(K-2) R, and having K-2 counter outputs;

a plurality of K-2 AND gates each having a pair of inputs and an output, a first through a K-2 AND gate of said plurality of AND gates each having one input respectively coupled to a second through a K-1 output of said shift register, and said first through said K-2 AND gate each having another input respectively coupled to a first through a K-2 output of said register; and

a plurality of generator EXCLUSIVE OR gates arranged in a cascaded sequence, each having a pair of inputs and an output, a first generator EXCLUSIVE OR gate inputs respectively coupled to an output of said first and second AND gate outputs, a second through a K-2 generator EXCLUSIVE OR gates each having one input coupled to a respective output of a third through said K-2 generator EXCLUSIVE OR gates with said third through said K-2 generator EXCLUSIVE OR gates other input coupled to a preceding generator EXCLUSIVE OR gate in said cascaded sequence, said K-2 generator EXCLUSIVE OR gate output coupled as an input to said output EXCLUSIVE OR gate.

11. A decoder for decoding orthogonal convolutional coded data comprising:

orthogonal function generator means for generating and providing an output of a plurality of predetermined orthogonal function sequences;

combining means for, receiving and combining an input of encoded symbol data with said plurality of orthogonal function sequences, and providing a corresponding output;

accumulator means for, receiving and accumulating said combining means output, and providing a corresponding output; and

Viterbi decoder means for receiving said accumulator means output as branch metric data and computing from said branch metric data corresponding bit data.

12. The decoder of claim 11 further comprising input means for receiving and temporarily storing said input of encoded symbol data, and for providing an output thereof to said combining means.

13. The decoder of claim 11 further comprising intermediate means for receiving and temporarily storing said accumulator means output, and for providing an output thereof to said Viterbi decoder means.

14. The decoder of claim 12 further comprising intermediate means for receiving and temporarily storing said accumulator means output, and for providing an output thereof to said Viterbi decoder means.

15. A decoder comprising:

a first memory having an input for receiving an input of encoded symbol data and an output;

a multiplier having a pair of inputs and an output, one input of said multiplier coupled to said first memory output;

a K-2 bit binary counter having a counter clock input and an output;

an orthogonal function sequence generator having a generator clock input, a data input and an output, said generator data input coupled to said counter output and said generator output coupled to another input of said multiplier;

an accumulator having an input coupled to said multiplier output, and an output;

a second memory having an input coupled to said accumulator output, and an output; and

a Viterbi decoder having an input coupled to said second memory output, and and output at which bit data is provided.

16. The decoder of claim 15 wherein:

said a K-2 bit binary counter receives at said counter clock input a first clock signal of a rate of 2^K-2 R, where R is a bit data rate; and

said orthogonal function sequence generator receives at said generator clock input a second clock signal of a rate of (2^K-2)² R.

17. The decoder of claim 16:

wherein said input of encoded symbol data is provided at a rate 2^K-2 R; and

said bit data is provided at said Viterbi decoder output at a rate R.

18. A method for decoding orthogonal convolutional coded data comprising:

receiving an input of orthogonal convolutional encoded symbol data;

generating a plurality of predetermined orthogonal function sequences;

combining said received input of symbol data with said plurality of orthogonal function sequences so a to provide a corresponding combined data;

accumulating said combined data so as to provide a corresponding accumulated data;

providing said accumulated data as branch metric data to a Viterbi decoder;

computing from said branch metric data within said Viterbi decoder corresponding bit data; and

providing an output of said bit data from said Viterbi decoder.

19. The method of claim 18 further comprising the step of temporarily storing said input of encoded symbol data.

20. The method of claim 19 further comprising the step of temporarily storing said accumulated data.