A Multiplier-Less Architecture for High Speed Computation of Multi-Dimensional Convolution

One of the most computationally intensive operations in digital image/video processing systems is multi-dimensional convolution. Every image/video processor needs the convolution module in its pre-processing stage. Fast and efficient design of the convolution module in an application specific system is a great challenge in VLSI (Very Large Scale Integration) design. Convolution operator requires a large set of multipliers and accumulators. A high precision multiplier takes enormous amount of VLSI area and it consumes more power. Hence reduction of the number of multipliers is another important challenge in VLSI design. A multiplier-less architecture for the design of a multi-dimensional convolution module is proposed in this thesis. The convolution expression is suitably partitioned to make it appropriate for overall pipelining and internal parallelism in the architecture design. An absolute flexibility is provided in the architecture for choosing the kernel characteristics in the convolution module. A novel architecture for performing convolution with symmetric kernels is also proposed in this thesis. This quadrant symmetric architecture exploits the symmetry of the kernels and performs computation with one quarter area of the kernel. Since the kernel characteristics are the same in all other three quarters, the intermediate results are reused and manipulated accordingly to obtain the final convolution result. This design reduces the VLSI area by about 75%. A new concept of log2 and inverse-log2 computation by an approximation process is also presented in this research. This leads to the elimination of the need for multipliers in the generic architecture by employing only adders and shifters for computation. The proposed architectures are implemented in a FPGA (Field Programmable Gate Array) environment on Xilinx's Virtex II 2v2000ff896-4 chip with a clock frequency of 99 MHz. It is observed that the new design reduces the VLSI area further by about 10% in addition to the reduction of power consumption. It is also observed that the new design could generate an output pixel in every clock cycle. Research work is in progress to employ the concept of log2 and inverse-log2 computations in building multiplier-less architectures for auto-correlation and cross-correlation functions.