Automatic frame synchronization recovery utilizing a sequential decoder

A method for automatic frame synchronization and error correction in the transmission and reception of data in a digital communication system including an encoder and a decoder comprising the steps of encoding a bit stream by:

• error correction encoding said data bit stream with a convolutional code to produce an error correctable bit stream;
• and
• combining a predetermined sequence of autosynchronization bits with the error correctable bit stream, thereby producing an encoded data sequence for transmission over said data communication system;
• and
• the steps of said method further comprising decoding the received encoded data sequence by:
• storing said received encoded data sequence;
• initializing the decoder by placing a plurality of initial code word subsets on a stack, each code word subset having distinct phase values;
• selecting a phase of the stored received bit stream based upon the phase of the code word subset with the best metric on the stack;
• combining the selected phase of the stored received bit stream with a predetermined sequence of autosynchronization bits corresponding to the bits combined in the encoding process so that the combined autosynchronization bits are removed by the decoder if the correct phase is selected to yield a sequence of combination bits, said combining step generating errors if an incorrect phase is selected;
• extending code word subsets from the node with the best metric to find extended code word subsets;
• comparing the sequence of combination bits for the selected phase to the extended code word subsets;
• generating new extended codeword subset metrics based on the codeword subset comparisons;
• removing the old codeword subset with the best metric from the stack;
• placing the new extended codeword subsets on the stack;
• and repeating the decoding steps of selecting, combining, extending, comparing, generating, removing and placing until an entire code word and phase are selected corresponding to a decoded data estimate and phase estimate.

A decoder for automatically recovering frame synchronization, accomplishing error correction, and decoding convolutionally encoded data transmitted from a digital communications system encoder, the decoder comprising:

• received data storage means for receiving and storing a predetermined number of received data bits from the encoder;
• phase offset bit selector means for selecting N bits of the received data stored in said data storage means in response to a phase select signal from a sequential decoder means;
• autosynchronization storage means for storing a predetermined autosynchronization sequence corresponding to the autosynchronization sequence stored at the encoder;
• combining means for generating a bit stream such that the Nth bit of the bit stream is the exclusive OR of the Nth bit of the autosynchronization sequence in the decoder storage means, with the Nth bit from the phase offset bit selector means;
• and
• sequential decoding means for comparing convolutional codeword subsets with the bit stream from the combining means, selecting a codeword subset having the best metric and providing as outputs a decoded data estimate signal and a phase select signal corresponding to the selected codeword subset.

A method of decoding a received encoded data sequence from an encoder at a decoder, in a digital communications system to achieve automatic frame synchronization and error correction, comprising the steps of:

• storing said received encoded data sequence;
• initializing the decoder by placing a plurality of initial code word subsets on a stack, each code word subset having distinct phase values;
• selecting a phase of the stored received bit stream based upon the phase of the code word subset with the best metric on the stack;
• combining the selected phase of the stored received bit stream with a predetermined sequence of autosynchronization bits corresponding to the bits combined in the encoding process so that the combined autosynchronization bits are removed by the decoder if the correct phase is selected to yield a sequence of combination bits, said combining step generating errors if an incorrect phase is selected;
• extending code word subsets from the node with the best metric to find extended code word subsets;
• comparing the sequence of combination bits for the selected phase to the extended code word subsets;
• generating new extended codeword subset metrics based on the codeword subset comparisons;
• removing the old codeword subset with the best metric from the stack;
• placing the new extended codeword subsets on the stack;
• repeating the steps of selecting, combining, extending, comparing, generating, removing and placing until an entire code word and phase are selected corresponding to a decoded data estimate and phase estimate.