Parallel VLSI Architecture for Approximate Computation of Discrete Hadamard Transform
Basant Kumar Mohanty
Abstract
Conventionally, decimation-in-time (DIT) data-flowgraph (DFG) is used to obtain computing structures for discrete Hadamard transform (DHT). The fixed-width structures based on conventional approach, however, offers a marginal bit-saving and introduces relatively more truncation error. In this paper, we have derived decimation-in-frequency (DIF) DFG for DHT which is more convenient for approximation using truncation than the DIT-DFG. To achieve higher bit-saving with relatively less truncation error, we propose an efficient truncation model comprising of pre-truncation (δ) and post-truncation (γ). Also, we present a logic optimized adder-subtractor design customized for DHT structure. Using the proposed truncation model, we have three variants of proposed structures for parallel computation of 2D DHT. The proposed structure-2 for DHT size N = 8, wordsize w = 8, and approximation (δ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> = 2, γ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> = 1, δ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> = 2, γ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> = 1) involves nearly 38% less area-delay-product (ADP) and 46% less energy per sample (EPS), and calculates outputs with almost the same accuracy as the existing fixed-width structure based on posttruncation. For the same word-size and N = 16, the proposed structure-2 for approximation (δ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> = 2, γ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> = 2, δ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> = 2, γ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> = 2) involves nearly 36% less ADP and 44% less EPS than the existing structure and calculates outputs with the same accuracy. We have observed that reconstructed images obtained using the proposed structure-2 are less by 7 dB and 2 dB PSNR than those obtained using the existing fixed-width structures for N = 8 and 16, respectively.