A FAST ALGORITHM FOR COMPUTING SHORT AND LONG –LENGTH LINEAR AND CIRCULAR DISCRETE CONVOLUTION

Ali Nahar; Hussein Khleaf

doi:10.30572/2018/KJE/160327

Authors

Ali Nahar Electrical Engineering Dept., University of Technology-Iraq https://orcid.org/0000-0002-6301-0447
Dr. Hussein Khleaf Electrical Engineering Dept., University of Technology-Iraq https://orcid.org/0000-0002-8336-6539

DOI:

https://doi.org/10.30572/2018/KJE/160327

Keywords:

Digital Signal Processor, linear convolution algorithms, circular convolution algorithms, Fast Table Methods, Discrete Fourier transform

Abstract

Convolution is a powerful operator that has applications in science, engineering, and mathematics. However, Convolution:-(Issues and Applications) is necessary for addressing many scientific and technical cases, including partial differential equations, signal processing, and image processing. Traditional problem resolution is complicated and has several drawbacks. This work presents a set of efficient algorithmic methods for both linear and circular computing. Depending on the duration of introduction and the treatment medium, three sloven methods can be applied based on the rapid table method. Convolution-based systems are very suitable for dealing with complex data that requires appropriate handling to achieve an ideal solution with increasing data length. Though the suggested techniques are geared toward fully parallel hardware implementation, they are contrasted with depending on length N and multiples, fully parallel hardware implementation using the proposed approach requires 40% to 65% less compared to the traditional approach. Since multipliers need a lot more space on the chip and energy than adders, the proposed algorithms are resource and power efficient when implemented on hardware.

Downloads

Download data is not yet available.

References

A. E. Abdelkareem, Convolutional Code Constraint Length over Rayleigh Fading Channel: Performance Evaluation and Hardware Aspects, Iraqi Journal of Computers, Communication and Control & System Engineering (IJCCCE), Vol. 17, No. 1, November 2017.

A. Lavin and S. Gray, "Fast Algorithms for Convolutional Neural Networks,", 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Las Vegas, NV, USA, 2016, pp. 4013-4021.

A. T. Alrubei, Mohammed, and Pozdnyakov Alexander Dmitrievich. “AN APPROACH FOR SINGLE-TONE FREQUENCY ESTIMATION USING DFT INTERPOLATION WITH PARZEN WINDOWING”. Kufa Journal of Engineering, vol. 14, no. 3, Aug. 2023, pp. 93-104, doi:10.30572/2018/KJE/140307.

Abdul-Jaleel Al-Asady, Heba, et al. “AN IMAGE ENCRYPTION METHOD BASED ON LOGISTICAL CHAOTIC MAPS TO ENCRYPT COMMUNICATION DATA”. Kufa Journal of Engineering, vol. 15, no. 4, Nov. 2024, pp. 55-64, doi:10.30572/2018/KJE/150405.

Abtahi, T.; Shea, C.; Kulkarni, A.; Mohsenin, T. Accelerating convolutional neural network with fft on embedded hardware. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 2018, 26, 1737–1749.

Alkadhim, Saif Aldeen Saad, Digital Convolution with Digital Signal Processing (DSP) (July 9, 2020). Available at SSRN: https://ssrn.com/abstract=3647517.

Bi, G.; Zeng, Y. Transforms and Fast Algorithms for Signal Analysis and Representations; Springer Science & Business Media: New York, NY, USA, 2004.

C. Li, H. K. Kwan and X. Qin, "Revisiting Linear Convolution, Circular Convolution and Their Related Methods," 2020 13th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics (CISP-BMEI), Chengdu, China, 2020, pp. 1124-1131.

Cariow, A.; Cariowa, G. Minimal Filtering Algorithms for Convolutional Neural Networks. ArXiv 2020, arXiv:2004.05607.

Chan, Y.H.; Siu, W.C. General approach for the realization of DCT/IDCT using convolutions. Signal Process.1994,p.p 37, 357–363.

Ghasemi, S. Hooman; Nowak, Andrzej S. , "Reliability Index for Non-normal Distributions of Limit State Functions", Structural Engineering and Mechanics, 62 (3): 365–372, 2017.

Grinshpan, A. Z. , "An inequality for multiple convolutions with respect to Dirichlet probability measure", Advances in Applied Mathematics, 82 (1): 102–119, 2017.

Hsu, H. (2011). Schaum’s Outline of Signals and Systems (2nd ed.). New York, NY: McGraw-Hill.

Ju, C.; Solomonik, E. Derivation and Analysis of Fast Bilinear Algorithms for Convolution. ArXiv 2019, arXiv:1910.13367.

Krishna, H. Digital Signal Processing Algorithms: Number Theory, Convolution, Fast Fourier Transforms, and Applications; Routledge: New York, NY, USA, 2017.

Krizhevsky, A.; Sutskever, I.; Hinton, G.E. Imagenet classification with deep convolutional neural networks. Commun. ACM 2017, 60, 84–90.

Lavin, A.; Gray, S. Fast algorithms for convolutional neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, USA, 27–30 June 2016; pp. 4013–4021.

Lin, S.; Liu, N.; Nazemi, M.; Li, H.; Ding, C.; Wang, Y.; Pedram, M. FFT-based deep learning deployment in embedded systems. In Proceedings of the 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany, 19–23 March 2018; pp. 1045–1050.

M. S. Naghmash, M. K. Wali, A. A. Abdulmajeed,High Level Implementation Methodologies of DSP Module using FPGA and System Generator, Eng. &Tech.Journal, Vol.34,Part (A), No.2, 2016.

Mathieu, M.; Henaff, M.; LeCun, Y. Fast training of convolutional networks through ffts. ArXiv 2013, arXiv:1312.5851.

N.Vasilache, J. Johnson, M. Mathieu, S. Chintala, S. Piantino, and Y. LeCun. Fast convolutional nets with fbfft: A GPU perfor-mance evaluation. CoRR, abs/1412.7580, 2014.

Parhi, K.K. VLSI Digital Signal Processing Systems: Design and Implementation; John Wiley & Sons: New York, NY, USA, 2007.

Pratt, W.K. Digital Image Processing; John Wiley & Sons: Hoboken, NJ, USA, 2007.

Roberts, M.J. (2012). Signals and Systems: Analysis Using Transform Methods and MATLAB® (2nd ed.). New York, NY: McGraw-Hill.

W.A. mahmoud; M. N.Hussainn, Wavelet and Wavelet Packet Transform Realization Using FPGA, Iraqi Journal of Computers, Communication and Control & System Engineering IJCCCE, Vol.6, No.2, 2006.

Wang, X.; Wang, C.; Zhou, X. Work-in-progress: WinoNN: Optimising FPGA-based neural network accelerators using fast winograd algorithm. In Proceedings of the 2018 International Conference on Hardware/Software Codesign and System Synthesis (CODES+ ISSS), Turin, Italy, 30 September–5 October 2018; pp. 1–2.