Parallel Algorithms and Systolic Architectures for 1-and 2-D Interpolation Using Discrete Hartley Transform
G.S. Maharana, Pramod Kumar Meher · International Journal of Computers and Applications · 2000
In this paper, we have presented an architecture for VLSI implementation of interpolation of 1-D real-valued data using a highly parallel Hartley-based interpolation algorithm. The proposed structure is fully pipelined, and neither reordering of data nor any delay cell is required within the computing blocks. For complete interpolation of an TV-point sequence into a sequence of length (ATL), the structure requires N/2 computational cycles, the duration of a computational cycle being equal to the time required to perform a multiply-accumulation operation. Due to the massive parallelism inherent with the DHT-based fast interpolation algorithm, the time-complexity of interpolation has been independent of the interpolation factor L. The proposed structure would, therefore, be very useful for fast interpolation in high-speed applications. In addition, a novel two-stage approach is suggested for 2-D interpolation, in which the rows and the columns of the 2-D data matrix are interpolated in two distinct stages using the proposed 1-D interpolation modules. A 2-D interpolation of (N x 7V)-point data to (NL x ATL)-point data can be computed by NL(L + 1) cuncurrent iV-point DHTs, which makes it convenient for implementation in a shared memory parallel machine. Using N(L + 1) numbers of 1-D interpolation modules, a VLSI will perform a 2-D interpolation in every (JV +1)/ 2 computational-cycles. Moreover, the proposed 2-D scheme requires a simpler program code and offers significant computational savings over the existing FFT-based fast 2-D interpolation algorithm for implementation in a general-purpose computer.