Patent ID: 7793199

Claim:
A method for reducing the computational complexity of a Viterbi decoder included in a channel decoder of a receiver in a communication system, comprising the steps of: (A) decomposing a trellis diagram with a convolutional code at a code rate k/n into 2 v−k radix-2 k butterfly units, where k, n, v are positive integers, and k indicates a number of input bits, n indicates a number of output bits, and v indicates a constraint length; (B) for a butterfly unit in the r-th level, decomposing each radix-2 k−r butterfly unit into four radix-2 k−r−l butterfly units; (C) determining a branch symmetry among the radix-2 k−r−l butterfly units based on a generator sequence for the convolutional code; (D) determining if r is equal to k, and when r is not equal to k, adding one to r and executing step (B); and (E) using the branch symmetry to reduce a branch metric computation required by a convolutional decoding at the code rate k/n, wherein steps (A) to (E) are performed by said receiver.