Boosting the implementation efficiency of Viterbi decoders by novel scheduling schemes

The scheduling scheme presented allows one to dramatically cut down the area needed to implement the ACS (add-compare-select) unit, which is the principal area consumer in high-speed Viterbi decoders (VDs). Since computation speed is only slightly compromised, a boost in implementation efficiency over existing methods can be achieved. Since a systematic derivation for a very efficient scheduling scheme is presented, the proposed scheme can be used to construct good schedules for traditional node serial processors as well. Therefore, the scheme is also well suited for VDs with a very high number of states. With the proposed scheduling scheme the same hardware structure can be used to efficiently decode a set of different codes that may even have different constraint lengths. Therefore, the scheme allows for easy and efficient implementation of programmable, high-speed VDs as well. It is shown that the novel scheduling scheme applied to a real-world Viterbi decoder, the 64-states industry standard rate 1/2, k=7 VD (CCSDS 101.0-B-2), leads to an increase of implementation efficiency of up to 600%