Viterbi decoding for wireless communication e.g. according to IEEE 802.16e, with generation of sets of a-priori bit values corresponding to expected combinations of bit values in the encoded data bits. Decoding paths that correspond to decoded data bits that are inconsistent with the a-priori bit values may be removed from the possible decoding paths to consider, and decoding the encoded data bits by selecting a decoding path from remaining decoding paths of the possible decoding paths that were not removed. A-priori bit values may be extracted from various messages, such as downlink-MAP, uplink-MAP, range-request and bandwidth-request messages.