ASIC design in Residue Number System for calculating minimum sum of Absolute Differences

摘要

The Sum of Absolute Differences (SAD) is widely used in motion-estimation algorithms, the most computationally intensive task in video compression, and also in determining similarities between two data sets. This paper proposes a SAD hardware implementation using a Residue Number System (RNS). Residue Number Systems have been used for decades in designing low-power and high-speed computer hardware, because of their inherent parallel structure. In RNS, large integers are represented as sets of smaller integers or residues, where the number bases or moduli are mutually prime. Since these residues are independent from each other, mathematical operations such as addition, subtraction and multiplication can be carried out without any carry propagation between residues, which is in most cases a limiting factor in binary systems. However, some arithmetical operations such as comparison and division are more difficult in RNS than in conventional binary systems, such as determining the sign and magnitude comparison of two numbers. The proposed SAD architecture is based on a very recent advance in fast sign-detection algorithms for RNS, and the experimental results show that the proposed architecture has higher speed and less area than previous SAD implementations.