Syndrome sequential decoder

• US 4,998,253 A
• Filed: 03/08/1989
• Issued: 03/05/1991
• Est. Priority Date: 03/11/1988
• Status: Expired due to Term

• Current Assignee: Kokusai Denshi Denwa Company Limited (KDDI Corporation)
• Original Assignee: Kokusai Denshi Denwa Company Limited (KDDI Corporation)
• Inventors: Yasuda, Yutaka, Ohashi, Masayoshi
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US07/320,633
• Time in Patent Office: 727 Days
• Field of Search: 371/43, 371/44, 371/45, 371/46
• US Class Current: 714/791
• CPC Class Codes: H03M 13/39 Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes

Abstract

A syndrome sequential decoding system for error correction of a convolutional code has a syndrome former for providing a syndrome sequence from a received sequence, a syndrome buffer memory for storing the syndrome sequence, an estimated error buffer memory for storing an estimated error sequence, a syndrome register for representing a syndrome state under searching, a comparator for testing if content of the syndrome register is all zero, and an algorithm controller. The algorithm controller controls the syndrome register, calculates a path metric and raises a flag in the estimated error buffer memory for showing an estimated error bit position. The syndrome sequential decoding system also includes an exclusive-OR circuit for correcting an information bit error according to the output of the estimated error buffer memory. When the content of the syndrome register is all zero, it shows that a currently searching path merges with the maximum likelihood path. Then a decoded sequence up to this point is explicitly determined. Moreover no further search will be required as long as the following syndromes remain zero. When the content of the syndrome register becomes nonzero, the normal path search restarts at this point. A back search limit pointer is provided on the estimated error buffer memory and a syndrome buffer memory to show the limit of the depth of back search.

Claims

1. A syndrome sequential decoding system for decoding a received code word sequence which is convolutionally encoded, comprising:

an input terminal for receiving the received code word sequence which is convolutionally encoded, said received code word sequence including an information bit and a parity bit;

an input/output buffer memory for storing data representing said received code word sequence;

a syndrome former means coupled to receive said received code word sequence from said input terminal, for generating a syndrome sequence which is a product of the received code word sequence and a parity check matrix of said convolutional code;

an estimated error buffer memory for indicating an estimated channel error sequence;

a syndrome buffer memory coupled with the output of said syndrome former means, for storing said output of said syndrome former means;

a syndrome register coupled to said syndrome buffer memory for storing data representing a new syndrome state;

shifting means for receiving bits from said syndrome buffer memory and storing said bits in said syndrome register, said shifting means including a decoding pointer which is shiftable to indicate one of a plurality of syndromes in said syndrome buffer memory;

a comparator means coupled with the output of said syndrome register for testing whether or not the contents of said syndrome register are all zero;

an algorithm controller coupled to receive the output of said comparator means for determining, in event of detection of an error, a position of an error bit and for producing a signal indicative of said position of said error bit, said algorithm controller being coupled to said estimated error buffer memory for inverting a bit located at said position of said error bit in said estimated error buffer memory in the event of detection of an error;

a back search limit pointer which is shiftable to specify one of a plurality of different bit positions in said estimated error buffer memory, for restricting said decoding pointer so that it does not go beyond a bit position specified by said back search limit pointer;

an exclusive-OR circuit coupled to receive the output of said input/output buffer memory and the output of said estimated error buffer memory for inverting an output bit of the output of said input/output buffer memory depending upon the output of said estimated error buffer memory; and

an output terminal coupled to an output of said exclusive-OR circuit for supplying an error corrected decoded output sequence.

2. A syndrome sequential decoding system according to claim 1, wherein said shifting means further comprises stack memory means coupled with said syndrome register for storing information including the state of said syndrome register and for sending said information to said syndrome register in response to a request by said algorithm controller means.

3. A syndrome sequential decoding system according to claim 1, wherein said comparator sends a signal to said algorithm controller if said contents of said syndrome register are all zero, and said stack memory is cleared by a signal from said algorithm controller.

4. A syndrome sequential decoding system according to claim 2 or claim 3, wherein said algorithm controller operates for error correction only when said contents of said syndrome register are not zero.

5. A syndrome sequential decoding system according to claim 1, wherein said received code word sequence is encoded by a convolution code system having a feedback loop, said convolution code system having an encoder having delay circuits, exclusive-OR circuits alternatingly coupled in series with said delay circuits, and a feedback loop between an output of a downstream one of said exclusive-OR circuits and an input of an upstream one of said exclusive-OR circuits.

6. A syndrome sequential decoding method using a tree structure of a convolutional code, comprising the following steps:

receiving at an input terminal a received sequence which was encoded by the convolutional code;

storing an information sequence derived from said received sequence in an input/output buffer;

supplying said received sequence to a syndrome former and using said syndrome former to prepare a syndrome sequence from said received sequence;

storing said syndrome sequence in a syndrome buffer;

determining a path which has the largest path metric by performing the following steps;

retrieving a syndrome from said syndrome buffer at a searching point;

supplying said syndrome to a syndrome register;

generating a new state of said syndrome register from both a previous state of said syndrome register and from a succeeding syndrome by performing a resetting operation on said syndrome register;

monitoring the state of said syndrome register;

raising an error flag in an estimated error buffer which stores an estimated information error sequence if the state of said syndrome register is indicative of occurrence of an information error;

calculating a branch metric according to the result of the resetting operation performed on said syndrome register;

updating a path metric of a current searching path by adding said branch metric to a previously calculated path metric;

determining, in response to the updated path metric, whether to continue a forward search or to start a back search;

determining a decoded path up to a current searching point when said previous state of said syndrome register becomes all zero;

determining a decoded path if said previous state of said syndrome register does not become all zero beyond the predetermined backsearch limit; and

correcting errors of said information sequence responsive to the determined decoded path.

7. A syndrome sequential decoding method using a tree structure of a convolutional code, comprising the following steps of:

receiving at an input terminal a received sequence which was encoded by the convolutional code;

storing an information sequence derived from said received sequence in an input/output buffer;

supplying said received sequence to a syndrome former and using said syndrome former to prepare a syndrome sequence from said received sequence;

storing said syndrome sequence in a syndrome buffer; and

determining a path which has the largest path metric by performing the following steps;

retrieving a syndrome from said syndrome buffer at a searching point;

supplying said syndrome to a syndrome register;

generating a new state of said syndrome register from both a previous state of said syndrome register and from a succeeding syndrome by performing a resetting operation on said syndrome register;

monitoring the state of said syndrome register;

raising an error flag in an estimated error buffer which stores an estimated information error sequence if the state of said syndrome register is indicative of occurrence of an information error;

calculating a branch metric according to the result of the resetting operation performed on said syndrome register;

updating a path metric of a current searching path by adding said branch metric to a previously calculated path metric;

determining, in response to the updated path metric, whether to continue a forward search or to start a back search;

determining a decoded path up to a current searching point when said previous state of said syndrome register becomes all zero, stopping said resetting operation, raising an error flag and continuing calculation of said branch metric until a non-zero syndrome exists in said syndrome register, while determining a decoded path having no determined error;

determining a decoded path beyond a predetermined backsearch limit when said previous state of said syndrome register does not become all zero; and

correcting errors of said information sequence responsive to the determined decoded path.

8. A syndrome sequential decoding method for decoding an information sequence which is encoded at a transmitting end by a systematic convolutional encoder which contains internal feedback, the encoded information sequence being transmitted to a receiving end to be decoded, comprising the following steps:

receiving at an input terminal a received sequence which was encoded by the systematic convolutional encoder;

storing an information sequence derived from said received sequence in an input/output buffer;

supplying said received sequence to a syndrome former and using said syndrome former to prepare a syndrome sequence from said received sequence;

storing said syndrome sequence in a syndrome buffer; and

determining a path which has the largest path metric by performing the following steps;

retrieving a syndrome from said syndrome buffer at a searching point;

supplying said syndrome to a syndrome register;

generating a new state of said syndrome register from both a previous state of said syndrome register and from a succeeding syndrome by performing a resetting operation on said syndrome register;

monitoring the state of said syndrome register;

raising an error flag in an estimated error buffer which stores an estimated information error sequence if the state of said syndrome register is indicative of occurrence of an information error;

calculating a branch metric according to the result of the resetting operation performed on said syndrome register;

updating a path metric of a current searching path by adding said branch metric to a previously calculated path metric;

determining, in response to the updated path metric, whether to continue a forward search or to start a back search;

determining a decoded path up to a current searching point when said previous state of said syndrome register becomes all zero, stopping said resetting operation, raising an error flag and continuing calculation of said branch metric until a non-zero syndrome exists in said syndrome register, while determining a decoded path having no determined error;

determining a decoded path beyond a predetermined backsearch limit when said previous state of said syndrome register does not become all zero; and

correcting errors of said information sequence responsive to the determined decoded path.

9. A syndrome sequential decoding method for decoding an information sequence which is encoded at a transmitting end by a systematic convolutional encoder which contains internal feedback, the encoded information sequence being transmitted to a receiving end to be decoded, comprising the following steps:

receiving at an input terminal a received sequence which was encoded by the convolutional code;

storing an information sequence derived from said received sequence in an input/output buffer;

supplying said received sequence to a syndrome former and using said syndrome former to prepare a syndrome sequence from said received sequence;

storing said syndrome sequence in a syndrome buffer; and

determining a path which has the largest path metric by performing the following steps;

retrieving a syndrome from said syndrome buffer at a searching point;

supplying said syndrome to a syndrome register;

generating a new state of said syndrome register from both a previous state of said syndrome register and from a succeeding syndrome by performing a resetting operation on said syndrome register;

raising an error flag in an estimated error buffer which stores an estimated information error sequence if said decoder is thinking of said occurrence of an information error;

calculating a branch metric according to said resetting operation;

updating a path metric of current searching path by adding said branch metric to said previous path metric;

whether to continue a forward search or to start a back search;

determining a decoded path beyond a predetermined backsearch limit; and

correcting errors of said information sequence responsive to the determined decoded path.