Citation :

S. Suganthi, Dr. S. Durairaj, 2023. "Design and Implementation of KARATSUBA Based LMS Filters for Biological Signal Processing" ESP International Journal of Communication Engineering & Electronics Technology (ESP- IJCEET)  Volume 1, Issue 3 : 7-14

.

Abstract :

        This study introduces a novel approach for implementing a programmable Infinite Impulse Response (IIR) filter by leveraging the Modified Karatsuba formula. The Karatsuba formula is renowned for its capability to accelerate large number multiplication by dividing operands into equal-length parts. Traditionally, multiplying two n-digit numbers demands O(n^2) elementary operations. However, Karatsuba's breakthrough algorithm dramatically reduces this complexity to O(log^2 n) elementary steps.

        In our research, we delve into the historical context of the Karatsuba algorithm, highlighting its origins in disproving a conjecture by Andrey Kolmogorov. We provide a detailed explanation of the algorithm's fundamental steps, which involve cleverly splitting numbers and performing multiplications with additions and digit shifts. To elucidate its practical application, we present a concrete example of multiplying two numbers and outline the pseudocode for Karatsuba's algorithm.

        Furthermore, we explore the concept of common subexpression elimination (CSE) in compiler optimization and its relevance to this algorithm. By eliminating redundant expressions, CSE enhances computational efficiency.

        Overall, this research sheds light on the Modified Karatsuba formula's significance, offering a fresh perspective on multiplication optimization and its potential applications, particularly in VLSI architectures.
 

References :

[1] J. Govil, "Enhanced Residual Echo Cancellation using Estimation of Delay and Fast LMS/Newton Algorithm based on Autoregressive Model," 2016 40th Annual Conference on Information Sciences and Systems, Princeton, NJ, 2006, pp. 1356-1356, doi: 10.1109/CISS.2006.286675.
[2] S. Ramanathan and V. Visvanathan, "A systolic architecture for LMS adaptive filtering with minimal adaptation delay," Proceedings of 9th International Conference on VLSI Design, Bangalore, India, 1996, pp. 286-289, doi: 10.1109/ICVD.1996.489612.
[3] Chin-Liang Wang, Ching-Chia Chen and Che-Fu Chang, "A digit-serial VLSI architecture for delayed LMS adaptive FIR filtering," Proceedings of ISCAS'95 - International Symposium on Circuits and Systems, Seattle, WA, USA, 1995, pp. 545-548 vol.1, doi: 10.1109/ISCAS.1995.521571.
[4] T. C. Lu, M. L. Chiang and J. B. Kuo, "A one-transistor synapse circuit with an analog LMS adaptive feedback for neural network VLSI," 1991., IEEE International Sympoisum on Circuits and Systems, Singapore, 1991, pp. 1303-1306 vol.3, doi: 10.1109/ISCAS.1991.176610.
[5] S. Mula, V. C. Gogineni and A. S. Dhar, "Algorithm and VLSI Architecture Design of Proportionate-Type LMS Adaptive Filters for Sparse System Identification," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 26, no. 9, pp. 1750-1762, Sept. 2018, doi: 10.1109/TVLSI.2018.2828165.
[6] P. Bujjibabu and K. Sirisha, "Design and implementation of efficient IIR LMS adaptive filter with improved performance," 2017 International Conference on Big Data Analytics and Computational Intelligence (ICBDAC), Chirala, 2017, pp. 240-245, doi: 10.1109/ICBDACI.2017.8070841.
[7] S. R. B, G. S. L and N. C K, "FPGA based Optimized LMS Adaptive Filter using Distributed Arithmetic," 2018 3rd IEEE International Conference on Recent Trends in Electronics, Information & Communication Technology (RTEICT), Bangalore, India, 2018, pp. 1863-1867, doi: 10.1109/RTEICT42901.2018.9012288.
[8] Y. He, B. Chen and Q. Li, "Blind-LMS based digital background calibration for a 14-Bit 200-MS/s pipelined ADC," 2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration (VLSI-SoC), Istanbul, 2013, pp. 348-351, doi: 10.1109/VLSI-SoC.2013.6673307.
[9] M. T. Khan, S. R. Ahamed and F. Brewer, "Low Complexity and Critical Path Based VLSI Architecture for LMS Adaptive Filter Using Distributed Arithmetic," 2017 30th International Conference on VLSI Design and 2017 16th International Conference on Embedded Systems (VLSID), Hyderabad, 2017, pp. 127-132, doi: 10.1109/VLSID.2017.16.
[10] Yin-Tsung Hwang and Chun Shang Lin, "VLSI design of DLMS adaptive IIR filters for high speed echo cancellation," 1997 IEEE Workshop on Signal Processing Systems. SiPS 97 Design and Implementation formerly VLSI Signal Processing, Leicester, UK, 1997, pp. 341-350, doi: 10.1109/SIPS.1997.626258.

Keywords :

        Biological Signal Processing, LMS Filters, Karastuba formula, Algorithm.