Very Large Scale Integration Architecture of Finite Impulse Response Filter Implementation Using Retiming Technique

Authors: S. Jalaja, A. M. Vijaya Prakash

Abstract:

Recursive combination of an algorithm based on Karatsuba multiplication is exploited to design a generalized transpose and parallel Finite Impulse Response (FIR) Filter. Mid-range Karatsuba multiplication and Carry Save adder based on Karatsuba multiplication reduce time complexity for higher order multiplication implemented up to n-bit. As a result, we design modified N-tap Transpose and Parallel Symmetric FIR Filter Structure using Karatsuba algorithm. The mathematical formulation of the FFA Filter is derived. The proposed architecture involves significantly less area delay product (APD) then the existing block implementation. By adopting retiming technique, hardware cost is reduced further. The filter architecture is designed by using 90 nm technology library and is implemented by using cadence EDA Tool. The synthesized result shows better performance for different word length and block size. The design achieves switching activity reduction and low power consumption by applying with and without retiming for different combination of the circuit. The proposed structure achieves more than a half of the power reduction by adopting with and without retiming techniques compared to the earlier design structure. As a proof of the concept for block size 16 and filter length 64 for CKA method, it achieves a 51% as well as 70% less power by applying retiming technique, and for CSA method it achieves a 57% as well as 77% less power by applying retiming technique compared to the previously proposed design.

Keywords: Carry save adder Karatsuba multiplication, mid-range Karatsuba multiplication, modified FFA, transposed filter, retiming.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1129764

References:

[1] A. Karatsuba and Y. Ofman, “Multiplication of many-digital numbers by automatic computers,” Doklady Akad. Nauk SSSR, 1962, vol. 145, no. 2, pp. 293–294, 1962.
[2] Albicocco, P.; Cardarilli, G.C.; Pontarelli, S.; Re, M., "Karatsuba implementation of FIR filters," Signals, Systems and Computers (ASILOMAR), 2012 Conference Record of the Forty Sixth Asilomar Conference on, vol., no., pp.1111,1114, 4-7 Nov. 2012
[3] Basant Kumar Mohanty and Pramod Kumar, “High Performance FIR Filter architecture for fixed and reconfigurable applications” IEEE transcation on 2015.
[4] C.E Leiserson and J.B. Saxe, “Retiming synchronous circuitry,” Algorithmica, Vol. 6, no. 1, pp. 5-35, 1991.
[5] Chao Cheng; Parhi, K.K., "Low- Cost Parallel FIR Filter Structures With 2-Stage Parallelism," Circuits and Systems I: Regular Papers, IEEE Transactions on, vol.54, no.2, pp.280, 290, Feb. 2007
[6] Chin-Bou Liu, Chua-Huang Huang, and Chin-Laung Lei, "Design and Implementation of Long-Digit Karatsuba's Multiplication Algorithm Using Tensor Product Formulation", The Ninth Workshop on Compiler Techniques for High-Performance Computing, 2003, pages 23-25.
[7] D. Knuth, “The Art of Computer Programming, Volume 2. Third Edition", Addison-Wesley, 1997. Section 4.3.3.A: Digital methods.
[8] Ehtiba, F.O.; Samsudin, A., "Multiplication and exponentiation of big integers with hybrid Montgomery and distributed Karatsuba algorithm," Information and Communication Technologies: From Theory to Applications, 2004. Proceedings. 2004 International Conference on, vol., no., pp.421, 422, 19-23 April 2004
[9] Gary C.T. Chow, Ken Eguro, Wayne Luk, Philip Leong, “A Karatsuba based Montgomery Multiplier”, Embedded and Reconfigurable Computing Group, Microsoft Research, Redmond, USA, pp-1-4, Dec-2013.
[10] J. Monteriro, S. Devadas, and A.Ghosh, “Retiming sequential circuits for low power,” International journal of high speed electronics and systems, Vol. 7, no.02, pp. 323-340, 1996.
[11] K.K Parhi, VLSI Digital Signal Processing Systems: Design and Implementation, New York, NY, USA: Wiley, 1999.
[12] Koc, Cetin K.; Erdem, Serdar S., (2003): A Less Recursive Variant of Karatsuba-Ofman Algorithm for Multiplying Operands of Size a Power of Two. Proceedings of the 16th IEEE Symposium on Computer Arithmetic, 1063-6889.
[13] N. Nedjah and L. Macedo Mourelle, “A reconfigurable recursive and efficient hardware for Karatsuba-Ofman’s multiplication algorithm,” in Proc. IEEE Conf. on Control Applications, Jun. 2003, pp. 1076–1081.
[14] Pramod Kumar Meher, “On Efficient Retiming of Fixed-Point Circuits,” IEEE Transactions Journal.
[15] Shri Prakash Dwivedi, "An Efficient Multiplication Algorithm Using Nikhilam Method". ArXiv: 1307.2735v1 (cs.DS) 10 Jul 2013.
[16] Yu-Chi Tsao; Ken Choi, "Area-Efficient Parallel FIR Digital Filter Structures for Symmetric Convolutions Based on Fast FIR Algorithm," Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, vol.20, no.2, pp.366,371, Feb. 2012.