Dynamic voltage and frequency scaling (DVFS) is an effective technique for reducing power consumption. Because of the increasing popularity of multimedia applications for portable consumer electronic devices, the importance of reducing their power consumption has become crucial. This paper proposes a table-based DVFS mechanism for frame decoding that can effectively reduce the power consumption of a processor by exploiting the frame-decoding complexity features. This proposed table-based DVFS predictor requires no prior knowledge on video decoders, and can be flexibly applied on different video codecs. This study implemented the table-based DVFS predictor on the PXA270 embedded platform and all benchmarks were encoded into various video coding formats, including H.264, VP8 and WMV formats. In addition, the proposed DVFS predictor was also ported on a modern platform NVIDIA JETSON TK1, and has demonstrated that the proposed algorithm can provide significant energy saving performance on high definition (HD) videos. The experimental results demonstrate that the energy consumption of decoding videos can be reduced from 6 to 21 %, whereas the frame drop rate is less than 3 %.