Patent ID: 6738949
Filing Date: 2004-05-18
Classification: H03M

Abstract:
An error correction method for receiving q-bit data having convolutional-encoded bits and unencoded bits as a trellis-encoded signal and for decoding the trellis-encoded signal according to a predetermined algorithm represented by a state transition diagram, the convolutional-encoded bits being obtained by convolutional-encoding lower t bits of an input p-bit data (where p>=2, q>p, and p>t>=1) by a convolutional-encoder having c internal states and the unencoded bits being upper (p-t) bits of the input p-bit data,wherein the state transition diagram has branches for respective transitions from c internal states at time i to c internal states at time (i+1), and each of c internal states at time i has a transition to two different internal states at time i+1, each branch including n parallel paths, the error correction method comprising the steps of: calculating a branch metric for each of the n parallel paths included in each branch, based on a level of the received trellis-encoded signal; selecting one of the n parallel paths for each branch, based on the branch metrics calculated for the n parallel paths of each branch; determining the branch metric calculated for the selected parallel path for each branch, as a branch metric for each branch; storing, into each branch, a candidate of a decoded value of the upper (p-t) bits corresponding to the selected parallel path for each branch; calculating a path metric for each of a plurality of paths, based on the determined branch metric for each branch, each of the plurality of paths representing state transitions from time (j-k) to time j; selecting one of the plurality of paths based on path metrics calculated for the plurality of paths; specifying a branch at each time from time (j-k) to time j in the selected path; and outputting the stored candidate of the decoded value of the upper (p-t) bits for the specified branch as a decoded value of the upper (p-t) bits together with a decoded value of the lower t bits based on the specified branch.