Motion estimation using on-line arithmetic

This paper proposes a class of motion estimation operation technologies and MSD-first comparators, which are implemented using on-line arithmetic. In on-line arithmetic, the numbers are represented in the redundant binary representation, where carry/borrow propagation chains are eliminated. This is because most significant digit (MSD) first accumulates and subtraction algorithms are applied by signed-digit (SD) representations. Most of previous MSD-first researches are used to decrease the initiation interval of recursive computations, particularly in IIR filters. In motion picture compression process, motion estimation (ME) represents a heavy loading. Intact motion estimation implementation using on-line arithmetic adopts MSD-first operations. This benefits reducing redundant calculation in two parts: 1. delete redundant summation of absolute different (SAD) calculation if existence another smaller SAD has been ascertained. 2. Decrease redundant lower-digits calculation if motion vector has been found. We developed two keys for the MSD-first algorithm to implement ME, including SAD calculation and SD comparison. This MSD-first ME algorithm can also cooperate with existent search algorithms to lower SAD computation further. This MSD-first ME algorithm can reduce 55% primitive SD operations