Modern computing methods for digital signal processing engineering systems

Available online at www.sciencedirect.com Available online at www.sciencedirect.com ScienceDirect ScienceDirect Available online at www.sciencedirect.com Procedia Computer Science 00 (2021) 000–000 Procedia Computer Science 00 (2021) 000–000 www.elsevier.com/locate/procedia ScienceDirect www.elsevier.com/locate/procedia Procedia Computer Science 192 (2021) 3534–3541 25th International Conference on Knowledge-Based and Intelligent Information & Engineering Systems and Intelligent Information & Engineering 25th International Conference on Knowledge-Based Systems Modern computing methods for digital signal processing Modern computingengineering methods forsystems digital signal processing engineering systems Paweł Poczekajłoa, Robert Suszyńskia * a Paweł Poczekajłoa, Robert Suszyńskia * Koszalin University of Technology. ul Śniadeckich 2, 75-453 Koszalin, Poland a Koszalin University of Technology. ul Śniadeckich 2, 75-453 Koszalin, Poland Abstract Abstract In the paper, the design and implementation of DSP systems with the use of modern computing and data processing methods are presented. The In the paper, theparallel design processing and pipeline and implementation implementation of DSP systems withofthecalculations as well use of modern as a number computing of solutions and data inmethods processing the fieldare of modern processing presented. techniques, The parallel processing such andaspipeline geneticimplementation algorithms, areofproposed. New calculations as possibilities and approach well as a number to designing of solutions in the fieldand of implementing DSP systems modern processing in thesuch techniques, fieldas of genetic cloud computing areare algorithms, alsoproposed. discussed.New possibilities and approach to designing and © 2021 The Authors. implementing Published DSP systems byfield in the ELSEVIER of cloudB.V. computing are also discussed. © 2021 This The is an Authors. open accessPublished by Elsevier article under B.V. the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0) © 2021 This The is an Authors. open access Published by ELSEVIER article under B.V. license the scientific CC BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0) Peer-review under This is an open responsibility access of article under the the CC committee BY-NC-ND of KES license International (https://creativecommons.org/licenses/by-nc-nd/4.0) Peer-review under data responsibility processing; of the cloud computing; scientific committee hardwarecommittee of computing; of KES International. digital Keywords: Peer-review under responsibility of the scientific KESsignal processing; genetic methods International Keywords: data processing; cloud computing; hardware computing; digital signal processing; genetic methods 1. Introduction 1. Introduction The development of computing data methods (especially in the last few years) has translated into the implementation The developmentof appropriate algorithms of computing dataand tools in(especially methods various applications. in the last Modern data processing few years) consistsinto has translated mainly the of algorithms focused implementation around fuzzy of appropriate logic,and algorithms artificial neural tools in networks, various and genetic applications. Modern algorithms [1, 2]. consists data processing However,mainly apart from the issuefocused of algorithms of appropriate around methods, recent fuzzy logic, years neural artificial have also seen, toand networks, a large extent, genetic the development algorithms of hardware [1, 2]. However, apart tools, from thesuch as high-performance issue computing of appropriate methods, systems recent years to support have activities also seen, to a and network large extent,services in the field the development ofof, among hardware others, cloud tools, such ascomputing and computing high-performance matrices. computing systems to support activities and network services in the field of, among Rapid others, progress cloud in theandfield computing of datamatrices. computing processing means primarily higher availability and much lower cost of implementation Rapid progress andinusetheoffield suchofsolutions. Currently,means data processing the most common primarily usesavailability higher concern theandimplementation much lower of costself- of learning algorithms implementation and[3], usethe of implementation such solutions. of closed control Currently, systems the most (regulators) common [4, 5], the uses concern and implementation searching large solution of self- learning algorithms [3], the implementation of closed control systems (regulators) [4, 5], and searching large solution * Corresponding author. Tel.: +48-94-3478707. * Corresponding [email protected] E-mail address:author. Tel.: +48-94-3478707. E-mail address: [email protected] 1877-0509 © 2021 The Authors. Published by ELSEVIER B.V. This is an open 1877-0509 access © 2021 Thearticle under Authors. the CC BY-NC-ND Published by ELSEVIER license B.V.(https://creativecommons.org/licenses/by-nc-nd/4.0) Peer-review under This is an open responsibility access of the article under the scientific CC BY-NC-NDcommittee of KES license International (https://creativecommons.org/licenses/by-nc-nd/4.0) Peer-review under responsibility of the scientific committee of KES International 1877-0509 © 2021 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0) Peer-review under responsibility of the scientific committee of KES International. 10.1016/j.procs.2021.09.126  Paweł Poczekajło et al. / Procedia Computer Science 192 (2021) 3534–3541 3535 Author name / Procedia Computer Science 00 (2021) 000–000 spaces for a given problem [6]. On the other hand, cloud computing services most often focus on the implementation of highly available systems and the handling of big data. One of the areas that can benefit a lot from modern computing methods is digital signal processing (DSP) and the methods used to synthesize, execute and implement them. Both appropriate algorithms for searching optimal solutions in design and high-performance cloud computing can be applied here. 2. The issues in obtaining digital signal processing (DSP) circuits Designing DSP systems according to the indicated guidelines (e.g. characteristics) is a process that requires specific calculations from a mathematical point of view [7, 8]. They are usually quite simple and most often a classical mathematical environment (Matlab, Scilab) is sufficient to obtain filter parameters. However, in selected cases, such as paraunitary filters [9], orthogonal filters [10] or pipelined rotation filters [11, 12], obtaining filter parameters (coefficients) is a mathematically very complex operation. Furthermore, the implementation of multidimensional systems introduces additional conditions, which are usually very complex and make individual activities and operations much more difficult. Another aspect is the hardware implementation, where significant computing power or parallel processing/pipelining is required for more complex structures. In such cases, modern methods of data processing can be useful. 2.1. Synthesis and implementation of DSP systems Synthesis and implementation of DSP systems are operations that boil down to the performance of many mathematical operations. Obtaining a simple FIR system, or even IIR, is quite easy, but in selected cases (atypical multi-input and multi-output structures [11], lossless systems [13, 14], orthogonal pipelined structures [10]), the actions necessary to implement them are more complex. 2.1.1. Factorization of polynomials (for systems described by the transfer function) Factorization of polynomials is a very difficult operation, especially when the polynomial has several dozen or several hundred coefficients [15]. However, a much more difficult operation is the factorization of polynomials of many variables - often impossible to calculate. Usually, in such a case, solutions are sought in a specific set, assuming certain accuracy. In such a situation, genetic algorithms or related search methods may be ideal. Such algorithms can make it possible to find a solution relatively quickly with a certain accuracy. Searching the whole set of solutions, checking one solution after another, is usually too time-consuming and therefore unprofitable or impossible to perform. An example of this can be achieving paraunitary systems [9]: 𝐻𝐻1 (𝑧𝑧) 𝑯𝑯(𝑧𝑧) = [ ], (1) 𝐻𝐻2 (𝑧𝑧) satisfying the dependency: 𝑯𝑯𝑇𝑇 (𝑧𝑧 −1 )𝑯𝑯(𝑧𝑧) = 1, (2) where the factorization of polynomials is necessary: 3536 Paweł Poczekajło et al. / Procedia Computer Science 192 (2021) 3534–3541 Author name / Procedia Computer Science 00 (2021) 000–000 𝐻𝐻2 (𝑧𝑧 −1 )𝐻𝐻2 (𝑧𝑧) = 1 − 𝐻𝐻1 (𝑧𝑧 −1 )𝐻𝐻1 (𝑧𝑧), (3) where H1(z) – initial transmittance, H2(z) – transmittance obtained by factorization of the right side of the equation (3), H(z) – the resulting paraunitary system. For 2D [14] or 3D [16] systems, it is necessary to reduce them to 1D subsystems, for which factorization is possible, e.g. with the Newton algorithm [17], where the accuracy of the result must still be monitored and the calculations may be repeated with different assumptions. 2.1.2. Matrix factorization (for systems described by state-space representation) As in the case of factorization of polynomials, also matrix factorization [18] can be a quite a problematic operation (despite the fact that matrices are limited to two-dimensional arrays). Additional conditions may be troublesome (e.g., matrix orthogonalization [18, 19], matrix minimization [18, 20]), so finding a solution is also time-consuming. The right data mining algorithms can be of great help in solving these equations. An example are individual operations for obtaining orthogonal state-space representations [19, 20], where usually the accuracy of matrix operations is of key importance, e.g., QR decomposition: 𝒕𝒕1 𝒕𝒕2 ⋯ 𝒕𝒕𝑘𝑘 𝒕𝒕2 𝒕𝒕3 ⋯ 0 𝑴𝑴 [ ] = 𝑸𝑸𝑸𝑸 = 𝑸𝑸 [ ], (4) ⋮ ⋮ ⋱ ⋮ 0 𝒕𝒕𝑘𝑘 0 ⋯ 0 where: Q – orthogonal matrix obtained after factorization, R, M – component matrices obtained after factorization, t. – transmittance (system) coefficients with two outputs and one input. With too low precision of calculation, the obtained solution comes down to obtaining a result system, which may have completely different parameters than originally assumed. Low accuracy is a problem especially with large matrices of multidimensional (3D) systems, where this problem is solved by reducing to 2D subsystems (Roesser model [21]) and 1D [16], by coefficient matrix decomposition: 𝑪𝑪 = 𝑪𝑪𝑑𝑑 𝑪𝑪𝑒𝑒 (5) where: 𝑏𝑏000 𝑏𝑏100 ⋯ 𝑏𝑏𝑘𝑘00 𝑏𝑏010 𝑏𝑏110 ⋯ 𝑏𝑏𝑘𝑘10 𝑏𝑏0𝑚𝑚0 𝑏𝑏1𝑚𝑚0 ⋯ 𝑏𝑏𝑘𝑘𝑘𝑘0 𝑏𝑏001 𝑏𝑏101 ⋯ 𝑏𝑏𝑘𝑘01 𝑏𝑏011 𝑏𝑏111 ⋯ 𝑏𝑏𝑘𝑘11 𝑏𝑏0𝑚𝑚1 𝑏𝑏1𝑚𝑚1 ⋯ 𝑏𝑏𝑘𝑘𝑘𝑘1 𝑪𝑪 = ⋯ - an example ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮ [[ 𝑏𝑏00𝑙𝑙 𝑏𝑏10𝑙𝑙 ⋯ 𝑏𝑏𝑘𝑘0𝑙𝑙 ] [ 𝑏𝑏01𝑙𝑙 𝑏𝑏11𝑙𝑙 ⋯ 𝑏𝑏𝑘𝑘1𝑙𝑙 ] [ 𝑏𝑏0𝑚𝑚𝑚𝑚 𝑏𝑏1𝑚𝑚𝑚𝑚 ⋯ 𝑏𝑏𝑘𝑘𝑘𝑘𝑘𝑘 ]] structure of a coefficients matrix of a 3D system [16], Cd – matrix obtained after decomposition, describing 1D component systems, Ce – matrix obtained after decomposition, describing 2D component systems.  Paweł Poczekajło et al. / Procedia Computer Science 192 (2021) 3534–3541 3537 Author name / Procedia Computer Science 00 (2021) 000–000 2.1.3. Coefficient quantization Coefficient quantization [7, 8] (adjusting to a particular length of registers) is a seemingly simple operation, but it is related to the so-called filter sensitivity to coefficient quantization. This sensitivity should be as low as possible so that the implemented system best reflects the original characteristics. In practice, quantization can significantly change the characteristics of a system. Additionally, there are different ways of quantizing (rounding down, rounding up, truncating, etc.): 𝛥𝛥𝑏𝑏𝑖𝑖 = 𝑄𝑄[ 𝑏𝑏𝑖𝑖 ] − 𝑏𝑏𝑖𝑖 , (6) where: bi – ith coefficient, Δbi – quantization error of the ith coefficient, Q[∙] – quantization operator. It should be remembered that even a simple DSP structure can have several coefficients (in the case of complex structures it can be up to several hundred). This makes it difficult to find the optimal form of the coefficients for registers of finite length. The use of algorithms that search the solution space can be very helpful here and significantly facilitate the selection of quantization for individual coefficients. An example may be the system from [16], where the 3D rotation filter has a total of 64 coefficients (32 rotators with 2 factors each). When quantizing with rounding up or down (we assume two possibilities), we have a total of 2 64 ≈ 1,845·1019 possibilities. 2.2. DSP implementation DSP implementation concerns the implementation of a given system on a specific hardware platform. In professional solutions, these are dedicated platforms based on FPGA or DSP [22, 23]. For simpler applications, implementation on a standard computer system is usually sufficient. However, selected applications require very fast DSP system operation (e.g., HD/2k/4k video processing in real time) or require significant computing power (e.g., multidimensional filters with a large number of coefficients). In such cases, modern data processing systems based on solutions from high-performance computing systems and/or remotely available cloud computing services are useful. 2.2.1. Parallel processing One of the basic methods of speeding up the operation of DSP systems is parallel processing (Fig. 1), e.g., simultaneous/parallel execution of all possible multiplications and then adding (for convolution [7, 8]). However, with a large number of multiplications, it is necessary to use dedicated FPGA reprogrammable circuits. A classic PC cannot process large-scale mathematical operations in parallel. Multi-core/multi-threaded processors are standard, but even in an ideal situation, they will only perform a few/a dozen multiplications simultaneously - which is usually insufficient. In the case of implementation in computer systems, it is necessary to provide additional computing resources available on-site or remotely via network. 3538 Paweł Poczekajło et al. / Procedia Computer Science 192 (2021) 3534–3541 Author name / Procedia Computer Science 00 (2021) 000–000 Fig. 1. General schema of parallel processing. 2.2.2. Pipelining Pipelining is a system architecture that enables the performance of tasks on many consecutive samples of the input signal (Fig. 2) [22]. The system is divided into blocks that carry out actions sequentially and the passage of a given sample (stimulus) through each of the computational blocks allows to obtain the output sample (system response). In such an implementation, each of the successive blocks may perform operations on successive input samples. In practice, however, this means that it is again necessary to use a hardware system that allows many operations/actions to be performed at the same time. A classic computer is also not able to provide the appropriate hardware solutions. Processing systems in reprogrammable FPGAs or cloud computing, where the infrastructure usually allows simultaneous multithreaded operations on separate hardware platforms, can be helpful. Fig. 2. General schema of the pipeline implementation. Figure 3 shows a schematic diagram showcasing the possibilities of using modern computing methods in the field of DSP.  Paweł Poczekajło et al. / Procedia Computer Science 192 (2021) 3534–3541 3539 Author name / Procedia Computer Science 00 (2021) 000–000 Fig. 3. Diagram of the possibility of using modern processing methods for the synthesis and implementation of DSP systems. 3. Selected aspects of computing for DSP Chapter 2 contains descriptions of the key aspects of the synthesis, realization and implementation of DSP systems, for which it is possible to apply selected methods and algorithms of modern processing. The use of such solutions can significantly facilitate the design stage and improve the signal processing cycle. Solutions that may be helpful in selected problems of designing DPS systems are proposed below. 3.1. State space search algorithms Genetic algorithms and other methods of finding the best/optimal solutions from a given set can be very helpful in solving complex mathematical operations. Selected numerical operations are presented in chapter 2.1. For a larger number of coefficients and DSP system dimensions, these tasks become very complex and often impossible to calculate with classical methods. A solution that can help in finding the result of individual tasks is the use of state space search methods using, for example, gradient and evolutionary algorithms or simulated annealing. Usually, with the classic approach, finding a solution with appropriate accuracy is very time-consuming and requires the task to be performed each time when changing the coefficients/parameters of the filter (DSP system). The use of genetic search algorithms can improve not only the speed of implementation of tasks, but also their accuracy. Likewise, when searching for the best combination of coefficient quantization - depending on the situation, different factors may require a different method of rounding, so that the final sensitivity of the system is as low as possible [7, 8]. 3.2. Parallel processing and pipelining Parallel processing and/or pipelining performed by means of dedicated hardware solutions such as expansion cards with GPUs or FPGAs [24, 25, 26] may significantly improve the speed of the DSP system compared to the implementation on a standard PC processor. Processing accelerators are systems dedicated to supporting the execution of a large number of computations in a parallel manner. They are therefore ideal solutions for a DSP hardware 3540 Paweł Poczekajło et al. / Procedia Computer Science 192 (2021) 3534–3541 Author name / Procedia Computer Science 00 (2021) 000–000 implementation. However, the installation of such expansion cards in standard computers is a small-scale solution and is more oriented towards testing or research. In the case of large-scale processing, it is necessary to use workstations or cloud computing, which may consist of a network of many individual workstations. 3.3. Cloud computing Network computing services and cloud computing are currently one of the fastest growing areas of IT. The currently available solutions of the largest companies (e.g. Amazon Web Services, Microsoft Azure, Google Cloud Platform, IBM Cloud, NVIDIA GPU Cloud) provide not only computing power, but also appropriate environments that are able to ensure the parallelization of individual tasks. Such ready-made systems are by far the best solution when processing large amounts of data, where high system reliability is also necessary. Usually, service providers guarantee emergency solutions and an automated system for transferring the implemented solutions to security servers. Providing continuous access to the service allows for the implementation of a DSP system operating in real time. At the same time, cloud computing can serve not only as a basic system for the implementation of a DSP system, but also as an environment for the implementation of synthesis methods and tasks described in points 2.1.1 - 2.1.3. 4. Conclusion The article describes the key problems in designing and implementing DSP systems, which can be solved by modern methods of computing and data processing. Computational problems resulting from factorization of polynomials and matrices as well as finding the best solutions in the searched set were indicated. The issue of parallel processing and pipelining of tasks in the finished DSP system was also discussed. Pointing to the above-mentioned issues, a number of solutions in the field of modern processing techniques, such as genetic algorithms and cloud computing, have been proposed. Data processing is currently a key field of IT. Due to the universality of network solutions, it is not only possible to transfer ready-made DSP systems to cloud computing, but also the scripts and appropriate algorithms responsible for obtaining the parameters of such a DSP system. Cloud computing provides a completely different possibility and approach to designing and implementing DSP systems. References [1] Ankita Bansal, Abha Jain, Sarika Jain, Vishal Jain, Ankur Choudhary, "Computational Intelligence Techniques and Their Applications to Software Engineering Problems", CRC Press, 2020, ISBN: 978-0367529741 [2] Nazmul Siddique, Hojjat Adeli, "Computational Intelligence: Synergies of Fuzzy Logic, Neural Networks and Evolutionary Computing", Wiley, 2013, ISBN: 978-1118337844 [3] Seyedali Mirjalili, Hossam Faris, Ibrahim Aljarah, "Evolutionary Machine Learning Techniques: Algorithms and Applications", Springer, 2020, ISBN: 978-9813299924 [4] http://www.genetic-programming.com/hc/pid.html [5] Antonia Plerou, Elena Vlamou, VasilPapadopoulos, "Fuzzy Genetic Algorithms: Fuzzy Logic Controllers and Genetics Algorithms" Global Journal For Research Analysis, no. 5, 2016, pp. 497-500. [6] Ossama Abdelkhalik, "Algorithms for Variable-Size Optimization", CRC Press, 2021, ISBN: 978-0815360162 [7] S.K. Mitra, J.F. Kaiser, "Handbook for Digital Signal Processing", John Wiley & Sons, New York (1993). ISBN: 0471619957 [8] A. Antoniou, "Digital Signal Processing: Signals, Systems, and Filters", McGraw Hill, New York (2005). ISBN: 0071454241 [9] R. E. Crochiere, L. R. Rabiner, "Multirate Digital Signal Processing", Prentice Hall, Englewood Cliffs, New Jersey (1983). ISBN: 978- 0136051626 [10] E. Deprettere, "Synthesis and fixed-point implementation of pipelined true orthogonal filters", ICASSP '83. IEEE International Conference on Acoustics, Speech, and Signal Processing, 1983, pp. 217-220. DOI: 10.1109/ICASSP.1983.1172177 [11] P.P. Vaidyanathan, "Multirate Systems And Filter Banks", Prentice-Hall, Englewood Cliffs, New Jersey (1993). ISBN: 81-7758-942-3 [12] R.T.Wirski, "On the realization of 2-D orthogonal state-space systems", Signal Processing, vol. 88, no. 11, 2008, pp. 2747-2753. DOI:10.1016/j.sigpro.2008.05.018  Paweł Poczekajło et al. / Procedia Computer Science 192 (2021) 3534–3541 3541 Author name / Procedia Computer Science 00 (2021) 000–000 [13] P. P. Vaidyanathan, Z. Doganata, "The role of lossless systems in modern digital signal processing: a tutorial", IEEE Transactions on Education, vol. 32, no. 3, 1989, pp. 181-197. DOI: 10.1109/13.34150 [14] A. Fettweis, "On the scattering matrix and the scattering transfer matrix of multidimensional lossless two-ports", AEÜ, vol. 36, 1982, pp. 374-381. [15] Joebert S. Jacaba, "Audio compression using modifieddiscrete cosine transform: the mp3coding standard" Undergraduate Research Paper, The University of the Philippines, College of Science, Department of Mathematics, October 2001. [16] P. Poczekajło, R. Wirski, "Synthesis and Realization of 3-D Orthogonal FIR Filters Using Pipeline Structures", Circuits Systems and Signal Processing, vol. 37, no. 4, 2018 (online 2017), pp. 1669-1691. DOI: 10.1007/s00034-017-06 [17] A. Jarząbek , M. S. Piekarsk i , „Faktoryzacja wielomianów nieujemnych na kole jednostkowym“, Materiały XI KK TOiUE, str. 96-101, Łódź-Rytro 1988. [18] G.H. Golub, C.F.Van Loan, "Matrix Computations", 3rd edn., The Johns Hopkins Univ. Press, Baltimore (1996). ISBN: 0801854148 [19] U.B. Desai, "A state-space approach to orthogonal digital filters", IEEE Transactions on Circuits and Systems, vol. 38, no. 2, 1991, pp. 160- 169. DOI: 10.1109/31.68294 [20] R.Wirski, K.Wawryn, B. Strzeszewski, "State-space approach to implementation of FIR systems using pipeline rotation structures", International Conference on Signals and Electronic Systems (ICSES), Wroclaw 2012. DOI:10.1109/ICSES.2012.6382223 [21] R.P. Roesser, "A discrete state-space model for linear image processing", IEEE Transactions on Automatic Control, vol. 20, no. 1, 1975, pp. 1-10. DOI: 10.1109/TAC.1975.1100844 [22] P. Poczekajlo, K. Wawryn, "Hardware implementation of 3D pipelined laplace filter based on rotation structures", 24th International Conference on Mixed Design of Integrated Circuits Systems (MIXDES), Bydgoszcz 2017, pp. 276-280. DOI: 10.23919/MIXDES.2017.8005215 [23] O. Dandekar, C.R. Castro-Pareja, R. Shekhar, "FPGA-based real-time 3D image preprocessing for image-guided medical interventions", Journal of Real-Time Image Processing, vol. 1, no. 4, 2007, pp. 285-301. DOI: 10.1007/s11554-007-0028-y [24] Wim Vanderbauwhede, Khaled Benkrid, "High-Performance Computing Using FPGAs" , Sprigner, 2013, ISBN 978-1-4614-1791-0 [25] https://www.bittware.com/resources/ [26] https://www.nvidia.com/en-us/gpu-accelerated-applications/