Motion estimation (ME) is of great importance for video compression. In this dissertation, a paradigm for real-time ME is presented. Solutions at all levels of abstractions, i.e., algorithmic, architectural, and circuit level, are provided. Two ME algorithms, one based on pattern search and other based on full search, are proposed. The goal is to provide fast estimation with minimum loss in visual quality. The first approach, called multi-path search (MPS), iteratively zeros in on the absolute minimum. Unlike other pattern search algorithms, the proposed algorithm is robust to local minima traps. It eliminates up to 98% computations with less than 1% loss in quality as compared to full search. It is flexible and suitable for real-time encoding of natural video sequences with any type of motion content.

The second approach, named adaptive search window size (ASWS) algorithm, is designed specifically for hardware implementation. The search window size and the search origin are optimized for each individual block based on the spatial and temporal correlated nature of video data. With a regular dataflow, it retains the regularity and scalability of full search, eliminating more than 94% of candidates in the search window with a maximum loss of 0.2dB in quality when compared to full search.

An efficient ME engine (MEE) is also implemented. Computational complexity is tackled at algorithmic level by using the ASWS algorithm while memory I/O is reduced by using a clever data reuse scheme. The design includes several novelties, among which are a novel processing element, an innovative dataflow scheme facilitated by clever processing array design, and a small local memory. The proposed architecture performs real-time ME for 4CIF video with 60 fps at 100 MHz while maintaining 100% hardware utilization.

Adder circuits form the core of the proposed MEE. Their performance significantly impacts the entire system and hence a high performance hybrid-CMOS full adder circuit is proposed. The proposed adder offers high speed operation, good driving capability, and high noise tolerance making it ideal for larger cascaded adders, commonplace in ME hardware. The adder shows roughly 30% improvement in the PDP when compared to its best counterpart.