Patent ID: 7561641

Claim:
A method of Viterbi decoding implemented in a communication system with a reduced butterfly operation, which decodes an encoded signal to reconstruct a source data signal and uses a trellis diagram with a plurality of nodes, wherein each node of the trellis has four branches associated therewith, the method comprising the steps of: (A) receiving the encoded signal; (B) computing kernel branch metrics with the reduced butterfly operation in accordance with the encoded signal, wherein the reduced butterfly operation is a radix-4 butterfly operation based on symmetry property of the trellis, and the symmetry property of the trellis exists in the branches emanating from the same origin state node and the symmetry property of the trellis can be determined by a generator sequence; (C) using symmetry property of the reduced butterfly operation to obtain branch metrics other than the kernel branch metrics; (D) computing path metrics for each node ; and (E) selecting a surviving path with the smallest path metric for each nodes.