Citation :

S. Suganthi, Dr. S. Durairaj, 2023. "Design and Implementation of KARATSUBA Based LMS Filters for Biological Signal Processing" ESP International Journal of Advancements in Computational Technology (ESP-IJACT)  Volume 1, Issue 3: 6-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.

[11] D. D. Rao, "Multimedia Based Intelligent Content Networking for Future Internet," 2009 Third UKSim European Symposium on Computer Modeling and Simulation, Athens, Greece, 2009, pp. 55-59, doi: 10.1109/EMS.2009.108.

[12] Manish Krishnan, Tong Jiang, Vivekananda Shenoy, Soumil Ramesh Kulkarni, Vinod Nair, Jeba Paulaiyan, 2020 Cloud network having multiple protocols using virtualization overlays across physical and virtualized workloads” United States Patent Application Publication, Application number- 16368381,

[13] Chanthati, Sasibhushan Rao. (2022). A Centralized Approach To Reducing Burnouts In The It Industry Using Work Pattern Monitoring Using Artificial Intelligenc. International Journal on Soft Computing Artificial Intelligence and Applications. Sasibhushan Rao Chanthati. Volume-10, Issue-1, PP 64-69.

[14] Nimeshkumar Patel, 2022.” Quantum Cryptography In Healthcare Information Systems: Enhancing Security In Medical Data Storage And Communication”, Journal of Emerging Technologies and Innovative Research, volume 9, issue 8, pp.g193-g202.

[15] Empowering Rules Engines: AI and ML Enhancements in BRMS for Agile Business Strategies. (2022). International Journal of Sustainable Development through AI, ML and IoT, 1(2), 1-20. https://ijsdai.com/index.php/IJSDAI/article/view/36

[16] Naga Ramesh Palakurti, 2022. "AI Applications in Food Safety and Quality Control" ESP Journal of Engineering & Technology Advancements 2(3): 48-61.

[17] Next-Generation Decision Support: Harnessing AI and ML within BRMS Frameworks (N. R. Palakurti , Trans.). (2023). International Journal of Creative Research In Computer Technology and Design, 5(5), 1-10. https://jrctd.in/index.php/IJRCTD/article/view/42

[18] Ayyalasomayajula, Madan Mohan Tito, Srikrishna Ayyalasomayajula, and Sailaja Ayyalasomayajula. "Efficient Dental X-Ray Bone Loss Classification: Ensemble Learning With Fine-Tuned VIT-G/14 And Coatnet-7 For Detecting Localized Vs. Generalized Depleted Alveolar Bone." Educational Administration: Theory and Practice 28.02 (2022).

[19] Ayyalasomayajula, Madan Mohan Tito, Sathishkumar Chintala, and Sandeep Reddy Narani. "Optimizing Textile Manufacturing With Neural Network Decision Support: An Ornstein-Uhlenbeck Reinforcement Learning Approach." Journal of Namibian Studies: History Politics Culture 35 (2023): 335-358.

[20] Ayyalasomayajula, Madan Mohan Tito. "Innovative Water Quality Prediction For Efficient Management Using Ensemble Learning." Educational Administration: Theory and Practice 29.4 (2023): 2374-2381.

[21] Vishwanath Gojanur , Aparna Bhat, “Wireless Personal Health Monitoring System”, IJETCAS:International Journal of Emerging Technologies in Computational and Applied Sciences,eISSN: 2279-0055,pISSN: 2279-0047, 2014.

[22] Aparna Bhat, “Comparison of Clustering Algorithms and Clustering Protocols in Heterogeneous Wireless Sensor Networks: A Survey,” 2014 INTERNATIONAL JOURNAL OF SCIENTIFIC PROGRESS AND RESEARCH (IJSPR)-ISSN : 2349-4689 Volume 04- NO.1, 2014.

[23] Aparna K Bhat, Rajeshwari Hegde, 2014. “Comprehensive Analysis Of Acoustic Echo Cancellation Algorithms On DSP Processor”, International Journal of Advance Computational Engineering and Networking (IJACEN), volume 2, Issue 9, pp.6-11.

[24] Muthukumaran Vaithianathan, Mahesh Patil, Shunyee Frank Ng, Shiv Udkar, 2023. "Comparative Study of FPGA and GPU for High-Performance Computing and AI" ESP International Journal of Advancements in Computational Technology (ESP-IJACT) Volume 1, Issue 1: 37-46.

[25] Rao, D. D. (2009, November 25). Multimedia-based intelligent content networking for future internet. In Proceedings of the 2009 Third UKSim European Symposium on Computer Modeling and Simulation (pp. 55-59). IEEE.

[26] Thapliyal, A., Bhagavathi, P. S., Arunan, T., & Rao, D. D. (2009, January 10). Realizing zones using UPnP. In 2009 6th IEEE Consumer Communications and Networking Conference (pp. 1-5). IEEE.

[27] Deshpande, A., Arshey, M. R., Ravuri, D., Rao, D. D., Raja, E., & Rao, D. C. (2023). Optimizing Routing in Nature-Inspired Algorithms to Improve Performance of Mobile Ad-Hoc Network. International Journal of Intelligent Systems And Applications In Engineering, 508–516. IJISAE. ISSN: 2147-6799.

[28] Rao, D. D., & Sharma, S. (2023). Secure and Ethical Innovations: Patenting AI Models for Precision Medicine, Personalized Treatment and Drug Discovery in Healthcare. International Journal of Business, Management and Visuals (IJBMV), 6*(2)*,

[29] Radhika Kanubaddhi, "Real-Time Recommendation Engine: A Hybrid Approach Using Oracle RTD, Polynomial Regression, and Naive Bayes," SSRG International Journal of Computer Science and Engineering , vol. 8, no. 3, pp. 11-16, 2021.

[30] Radhika Kanubaddhi, 2022. "Designing an Enterprise-Grade, Cloud-Native Chatbot Solution for the Hospitality Industry Using Azure QnA Maker and Azure LUIS", ESP Journal of Engineering & Technology Advancements, 2(1): 56-62.

Keywords :

Digital Hardware, Geffe, Generator, BIST, LFSR.