1. A method for decoding a signal encoded with a trellis code corresponding to a trellis diagram having a plurality of states, the method comprising: computing a node metric for each of the plurality of states; computing a set of conditional optimal symbol sequences leading to all possible current states; selecting a state having the smallest node metric, as a current optimal state; selecting an optimal symbol sequence from the computed set of conditional optimal symbol sequences, wherein the selected optimal symbol sequence ends at the selected current optimal state; and outputting the optimal symbol sequence as a decoded signal.