{'fraction_non_alphanumeric': 0.03312788906009245, 'fraction_numerical': 0.01078582434514638, 'mean_word_length': 4.756541019955654, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient Absolute Difference Circuit for SAD Computation On FPGA

Video Compression is very essential to meet the technological demands such as low power, less memory and fast transfer rate for different range of devices and for various multimedia applications. Video compression is primarily achieved by Motion Estimation (ME) process in any video encoder which contributes to significant compression gain.Sum of Absolute Difference (SAD) is used as distortion metric in ME process.In this paper, efficient Absolute Difference (AD) circuit is proposed which uses Brent Kung Adder(BKA) and a comparator based on modified 1’s complement principle and conditional sum adder scheme. Results shows that proposed architecture reduces delay by 15% and number of slice LUTs by 42% as compared to conventional architecture. Simulation and synthesis are done on Xilinx ISE 14.2 using Virtex 7 FPGA.


INTRODUCTION
To meet the technological demands such as low power, less memory and fast transfer rate for a wide range of applications including the growing demand of High Definition(HD)(1080p) to Ultra-High Definition(UHD)(4K and 8K), resulted in creation of stronger needs for better video compression efficiency. HEVC or H.265is a video compression standard designed to substantially improve coding efficiency when compared to its precedent, the Advanced Video Coding (AVC) or H.264.HEVC is a block-based video compression designed to support higher resolutions and it can achieve 50% bit rate saving compared to H.264/MPEG-4 AVC for the same video quality [1] [2].This considerable increase in performance is due to the many enhanced techniques and methodologies that have been introduced in H.265/HEVC. Some of these enhancements are included in the motion estimation process, which is one the most complex and time consuming block in video encoding. The objective of the ME unit is to find the best matched block in the reference (past/future) frame search window (region of interest), for every block of the current frame such that there constructed frame contributes to the lowest residual information [3].The bottleneck for the ME system design lies in the implementation of an appropriate SAD architecture. For block based ME, the Sum of Absolute Difference(SAD) is the generally used metric which adds up the absolute differences between corresponding elements in a candidate and reference block in video frames. However with the increase in the coding block size to 64x64 in HEVC, compared to 16x16 in H.264/AVC, results in greater complexity in ME process. Thus in HEVC for ME process, the number of SAD computations vastly increases resulting in increase in the processing delay, power consumption and hardware complexity. Thus, a pragmatic strategy to elevate the performance of H.265/HEVC relies on enhancing the performance of the core component of the motion estimation engine which is the block matching unit. Different VLSI architectures for SAD computations are available in the literature where there is a lot of tradeoffs between the speed, power and area during the hardware implementation. Due to the increasing demand for the portable devices with low power consumption and high performance, the circuits are optimized according to the applications. In this paper, implementation of absolute difference circuit on FPGA is proposed to increase speed performance and to minimize the amount of occupied resources on FPGA for SAD calculation.

RELATED WORK
SAD is one of the most popular techniques used for motion estimation in digital video encoding systems. There are large number of methods available for SAD computation where there are tradeoffs between speed, power and area during the hardware implementation. Typically, the SAD computation consists of first computing the absolute difference between corresponding pixels in current and reference video frame.
The calculation of SAD from the current and reference block is performed using equation (1), Where, CB -Current Block, RB -Reference Block, N X M -block size of current and reference block, i,j -two dimensional coordinates of block.
Generally, the SAD operation basically consists of first computing the absolute difference |CB(i,j) -RB(i,j)| and then summing up these in a multi-input addition.
For absolute difference calculation, one method is to detect the smaller operand in the absolute difference computation |CB−RB| and to subtract it from the larger operand [4], [5].The other method comprises of complimenting the smaller of the two numbers and then performing addition of two numbers followed by plus one to compute the absolute difference [6]. To compute the absolute difference for SAD, in [7] a novel architecture is optimized for realizing efficient absolute difference circuits in Virtex-5 FPGA devices which uses the 6-input look-up tables available within the chosen devices family to maximize speed performance and to minimize the amount of occupied resources. In [8] an improved architecture for efficiently computing the sum of absolute differences (SAD) on FPGAs is proposed based on a configurable adder/subtractor implementation in which each adder input can be negated at runtime. The SAD architecture proposed in this paper provides a significant resource reduction on current FPGAs. In [9] FPGA design for fast computing of the minimum SAD is proposed. The hardware unit proposed is intended to augment a general-purpose core and with the use online arithmetic (OLA) it is possible to implement a full 16 X 16 macroblock SAD in a single FPGA device and it permits to speed up the computation by early truncation of the SAD calculation when the involved candidate is bigger than the current reference SAD. In [10] pipelined SAD architecture for efficient SAD calculations is proposed where consecutive pipeline stages performs the addition of absolute differences to obtain SAD of 8 X 8 block. In [11] Different architectures for binary addition were proposed for SAD computation on FPGA Table 1 summarises the above mentioned related work on SAD computation. Review work motivates for a proposal of high speed compact AD circuits on FPGA for SAD calculation. In this paper, AD circuit on FPGA is proposed to increase speed performance and to minimize the amount of occupied resources on FPGA for SAD calculation.

PROPOSED ARCHITECTURE
Hardware architecture for computing the absolute difference between corresponding pixels in current and reference video block is proposed. The method used for AD calculation is as used in [6] where adder and comparator form the basic component as shown in Figure 1.The 8-bit comparator compares two numbers and returns the 1's complement of the smaller number and the larger number as it is. Proposed Architecture: In this architecture:  Ripple Carry Adders in AD circuit ( Figure 1) are replaced by Brent Kung Adder (Type of Parallel Prefix Adders-PPA).  8-bit conventional comparator in Figure 1 is replaced by comparator based on modified 1's complement principle and conditional sum adder scheme.
These replacements results in reduction in delay and reduces LUTs count used in the circuit.

PPA:
PPA (Parallel Prefix Adder) circuits use a tree network to reduce the latency to O (log2n)where 'n' represents the number of bits.PPA employs 3-structural stages as shown in Figure 2. The first stage at the top is used for computing generate and propagate signals as given in equation (2) and (3)exactly as in Carry Look ahead Adder (CLA) where a and b represents binary digits.

g=a.b-(2) p=a⊕b-(3)
The carry bits are calculated in the second stage. In this stage, to formulate the operation of the prefix adders, "prefix operator" which is represented as "." is used. The "prefix operator" function has two essential properties to keep the computational operation faster. The first one is called the associative property and the second one is idempotency property. Using the advantages of these properties, carry-out can be found at a depth proportional to log2(n) [12]. The final summation is obtained in the last stage.The associative and idempotency properties of "." operator allow carry output to be computed in a different number of levels or simply depth. Therefore, various topologies of prefix adders can be designed which are mentioned in the literature and are inspiring to VLSI designers because of their minimum depth and delay.
The logical structures used in prefix adders scheme consists of black cell, gray cell and white cell as defined in Figure 3 [13].  Electronic copy available at: https://ssrn.com/abstract=3381409 The logical structure of black cell can propagate and generate signals while the logical structure of gray cell can only generate signals. The white cell (buffer)is used for loading the signal out. In parallel prefix scheme, generate and propagate signals can be grouped in multiple ways to get the same correct carry signals. Based on different methodologies of grouping these signals, different prefix architectures can be created. The parallel form of obtaining the carry bit makes PPAs perform addition arithmetic faster. There are many types of PPA such as Brent Kung, Kogge Stone, Ladner Fisher, Hans Carlson and Knowles [12]. Out of many types of PPA, Brent Kung Adder(BKA)is used as for 8-bit implementation it has less delay compared to other types of PPA [12] [13].
In BKA propagate signals and generate signals are combined into groups of two by using the associative property. The first stage in BKA includes computation of generate and propagate signals corresponding to each pair of bits in a and bas given by equation (2) and (3). The second stage ie. prefix carry tree includes computation of carries corresponding to each bit. Equations (4) and (5)

Modified Comparator:
The proposed architecture apart from using BKA, also uses comparator (based on modified 1's complement principle and conditional sum adder scheme). In this modified 1's complement scheme, if A>B, bit Cout = 1 and if A≤B bit Cout =0 so the only concern is about carry out bit information as shown in Figure 5.This method always adds a fixed carry after modification, so if A ≥ B, bit Comp = 1 and if A < B, bit Comp = 0 [15].For realization of this comparator conditional sum adder scheme has been used that provides a logarithmic increase in speed for addition [16].
The principle behind this scheme is to generate two sets of outputs for a given group of k bits operands. Each set includes k sum bits and an outgoing carry. The one set assumes that the eventual incoming carry will be zero, while the other assumes that it will be one. Depending upon the incoming carry correct set of outputs (out of the two sets) is selected without waiting for the carry to further propagate through the k positions as shown in Figure 6. However, this scheme is generally not applied to long n-bits operand at the beginning of the add operation, since it will add delay as the carry propagates through all n positions before making the selection for correct output. Generally, the given n bits are divided into smaller groups to apply this conditional adder scheme separately. Thus, the serial carry-propagation inside the separate groups can be done in parallel, reducing the overall execution time. The outputs of the subgroups are then combined to generate the output of the final output.  This architecture reduces delay and also provides significant reduction in resource utilization in FPGA.

SIMULATION AND RESULTS
Simulations of the conventional and proposed architecture for AD circuit implementation have been carried out using Verilog HDL programming in Xilinx ISE 14.2 platform and implemented on Virtex7 FPGA. Adequate testing of each design was done to verify correct operation. Figure 8 shows the simulation result of proposed AD circuit. Electronic copy available at: https://ssrn.com/abstract=3381409   Table 2 Comparison of proposed AD architecture architecture with conventional architecture Figure 9 shows graphical representation of delays in proposed architecture with conventional architecture and Figure 10 shows implementation and area occupied of proposed AD architecture on FPGA. Table 2 shows comparison of proposed AD circuit architecture in terms of time delay and area. Referring to the above table, it can be seen that there is reduction in delay and number of occupied resources on FPGA in the proposed architecture for AD circuit resulting in improved performance for SAD computation in motion estimation.

CONCLUSIONS
VLSI architecture for SAD computations is proposed in this paper for reducing delay and area and is implemented on Virtex7 FPGA. The proposed architecture reduces delay and provides significant reduction in resource utilization in FPGA. Synthesis results shows that proposed architecture reduces delay by 15% and number of slice LUTs by 42 % as compared to conventional architecture.