Two low-power Viterbi decoder (VD) architectures are presented in this paper. In the first, limited decision errors are introduced in the add-compare-select units (ACSUs) of a VD to reduce their critical path delays so that they can be operated at lower supply voltages in absence of timing errors. In the second one, we allow data-dependent timing errors which occur whenever a critical path in the ACSU is excited. Algorithmic noise-tolerance (ANT) is then applied at the level of the ACSU to correct for these errors. Power reduction in this design is achieved by either overscaling the supply voltage (voltage overscaling (VOS)) or designing at the nominal process corner and supply voltage (average-case design). Power savings in the first and second design are 58% and 40% at a coding loss of 0.15 dB and 1.1 dB respectively in a IBM 130nm CMOS process.