Patent ID: 6877132

Claim:
A method for hard-decision channel decoding of tail-biting convolutional codes, the method comprising the steps of: a. receiving from a channel an input bit stream encoded by a tail-biting convolutional channel encoder, the encoder comprising a number of memory elements and having a rate, the input bit stream comprising a series of symbols, each symbol comprising a number of bits, the number of bits per symbol being related to the rate of the encoder; b. generating a modified bit stream comprising a number of symbols by repeating a segment of the input bit stream, the segment comprising a number of symbols, the number of symbols being equal to the sum of a decision depth and a stabilization depth; c. assuming an initial accumulated Hamming distance for each possible initial state of the encoder; d. setting a stage position to a first stage of a trellis structure corresponding to the encoder, the trellis structure representing: i. a number of states, the number of states being related to the number of memory elements of the encoder; ii. a plurality of transitional branches; and iii. a number of stages, the number of stages being related to the number of symbols in the modified bit stream; e. for each stage of the trellis structure within the decision depth: i. reading a symbol from the modified bit stream; ii. for each transitional branch in each state, computing a Hamming distance to the symbol and then an accumulated Hamming distance of a survivor path extended with the branch; and iii. for each state, determining a survivor path by comparing the accumulated Hamming distances for the survivor paths merging to the state; f. generating a preliminary output bit stream comprising a beginning and an end by executing the following steps for each stage of the trellis structure outside the decision depth: i. reading a symbol from the modified bit stream; ii. for each transitional branch in each state, computing a Hamming distance to the symbol and then an accumulated Hamming distance of a survivor path extended with the branch; iii. for each state, determining candidate survivor paths by comparing the accumulated Hamming distances for the survivor paths merging to the state, storing each said survivor path as a candidate survivor path; and iv. using majority logic on said stored candidate survivor paths, deciding each decoded symbol of the modified bit stream; g. deriving a truncated preliminary output bit stream comprising a beginning and an end by: i. discarding from the beginning of the preliminary output bit stream a number of bits related to the stabilization depth; and ii. discarding from the end of the preliminary output bit stream a number of bits related to the decision depth; and h. deriving an output bit stream by reorganizing the truncated preliminary output bit stream by moving bits between the beginning and end of the truncated output bit stream in accordance with the relative number of bits in the stabilization depth and in the segment of the input bit stream repeated in step “b”.