Tomographic Application-Specific Integrated Circuits for Fast Radon Transformation Oleksandr Ponomarenko1[0000-0002-6538-0468], Anna Bulakovskaya 1[0000-0001-6410-9476], Andrii Skripnichenko1[0000-0003-0098-6810], Jugoslav Achkoski 2[[0000-0003-2782-3739], Pavel Usik3[0000-0002-3268-342X] and Alexandr Olenyuk 4[0000-0003-1463-076X] 1 College of Engineering and Management of National Aviation University, Kyiv, Ukraine 2 Military Academy “General Mihailo Apostolski”, Skopje, North Macedonia 3 Central Ukrainian National Technical University, Kropivnitskiy, Ukraine 4 State Agrarian and Engineering University in Podilia, Kamianets-Podilskyi, Ukraine ponomarenkoS_200@ukr.net Abstract. The application-specific integrated circuit (ASIC) for tomographic processing of point objects is developed. The processing method is based on discrete Radon transform. We constructed modified method of replacing Radon transform with Fourier transform using interpolation on quasi-regular coordi- nate grids – regular with constant step on lengthwise coordinate and linearly growing step with constant difference on transverse coordinate. The resulting grid is quasi-regular and calculating complexity become significantly smaller. Grounding on concept of separate differences of arbitrary order we overcome the problem of irregularity of coordinate grids. The applied-specific tomograph- ic circuit for processing 2D signals is constructed and three-level automated control technological processes system is developed. Keywords: application-specific integrated circuit, tomographic processing of signals, discrete Radon transform, interpolation, quasi-regular grid. 1 Introduction In this paper we represent the results of development of application-specific integrated circuit (ASIC) for realisation fan-beam fast Radon transform with interpolation on quasi-regular coor- dinate grids. Many authors (see, e.g., 1) argue that Radon transform (discrete or fast) success- fully replaced by corresponding Fourier transform. Actually Radon transform (RT) is orthogo- nal transform in polar (cylindrical for 3D transform) coordinate system. (Further we'll consider 2D transforms and polar coordinates without any losses of generality.) The transformation from Cartesian to polar coordinates is conformal one, but only for infin- itesimal areas 2. Figures of arbitrary shape in an infinitesimal area become similar, that is, they remain in shape. At the same time, the figures of finite dimensions are distorted, although the angles between the two curves are preserved (the so-called conservatism of the angles). Consequently, in the case of RT of any kind, including the fan RT, and with the corresponding Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons Li- cense Attribution 4.0 International (CC BY 4.0). CybHyg-2019: International Workshop on Cyber Hygiene, Kyiv, Ukraine, November 30, 2019. transition from a discrete rectangular to a discrete polar coordinate grid, there is a distortion of geometric figures with conservatism of the angles. 2 Background overview An obvious regular method of eliminating geometric distortions when sampling the radial transformation of a Radon on a polar raster with irregular grid is the interpolation of data. The papers [3 – 5] suggest variations of the Lagrange interpolation formula – linear, bilinear, and similar. You can also use the interpolation formulas of Gauss, Stirling, Bessel, Padé approxima- tion methods etc. [6,7]. In the transition from a rectangular to a polar raster on irregular grid, the difference tables have a fundamentally alternating step, and the interpolation formulas of Gauss, Stirling, Bessel, and others are unacceptable. Let's consider this problem in details. To simplify the computational complexity of algorithms and to eliminate the problem of uncertainty of finite differences, a modified Lagrange interpolation formula with generalization of the concept of finite differences is introduced, introducing the so-called separated differences [8]. Using this generalization, the Lagrange interpolation formula is represented in a form simi- lar to Newton's first interpolation formula. We note that Newton's interpolation formula is more convenient for computer calculations [9]. 3 Integrated circuits for fast Radon transform development The realization of the fan Radon transform with an irregular grid is reduced to the restoring of the function f  x  for need number of samples xi , i  1, N , on line segment a  x  b , when its values are known x j , j  1, M , M  N . In this particular problem, the values represent the signals received by the sensors of the computer tomography system. It is desirable to have for f  x  quite simple, that is, a less laborious computation formula that could be used to find approximate value of a function with the correct precision at an arbitrary point in the segment. The mathematical problem is formulated as follows. We assign on line segment a  x  b the grid    x0  a  x1  x2   xM 1  xM  b . The set of the function f  x values are assigned in the nodes of the grid. They are equal f  x0   f0 , f  x1   f1 , , f  xM 1   f M 1 , f  xM   f M . (1) We have to construct the interpolant f  x  . Its values coincide with the values of the func- tion f  x  in the nodes of the grid: f  x j   f j , j  1, 2, M  1, M . To construct interpolants one needs to find the finite differences n -th order. Given the fact that the finite difference of the first order has the form f  x   f  x   f  x  x  , write the general expression for the finite difference n -th order:  f  x      f  x   . n n 1 Accordingly, the separated first-order differences will be written as f  f0 f f  x0 , x1   1 ;  x1 , x2   2 1 ; (2) x1  x0 x2  x1 separated second-order differences  xi 1 , xi  2    xi , xi 1  , i  1, 2,  xi , xi 1 , xi  2   etc. xi  2  xi We obtain separated differences n -th order from separated differences  n  1 -th order using recurrent relation  xi 1 , xi  2 , , xi  n    xi , xi 1 , , xi  n 1   xi , xi 1 , xi  2 , , xi  n   , n  1, 2, , i  0,1, 2, xi  n  xi In a regular coordinate grid, the difference of arbitrary order x1  x0  x2  x1   xi  2  xi 1   xi  n  xi  n 1 are constant quantities that are equal to each other. When the differences  x0  x1  ,  x1  x2  , ,  xi  2  xi  , ,  xi  n  xi  are independent random variables, the coordinate grid is obviously irregular by definition. For our particular task, the coordinate grid is 2D one with nodes  i , i  , i  1, N . Fig. 1 shows the elemental link of the grid:   1 , 1  1, 2   .  i , i  , i  1,2 :    2 , 1   2 , 2   If we continue to assign the nodes of the grid along the coordinates , we get a sequence of   nodes with coordinates of points i ,  j , i  1, N , j  1, 2 . Based on elementary geomet- ric considerations, one can calculate the values of the intervals between the points i , i 1 and  j ,  j 1 . Fig. 2 shows a sequence of links. It can be extended as in coordinate , and in coor- dinate , and the values of the intervals  i ,  j   remain unchanged. We call this coordinate grid quasi-regular. To create a difference table in an irregular coordinate grid, the so-called sub tabulation or condensation of the table is used [9]: the initial memory table is introduced into the computer memory, and the necessary values for the functions are entered as needed, according to the interpolation formula. It is obvious that in order to create a difference table for a quasi-regular coordinate grid, performing elementary arithmetic operations of type carries out the thickening of a table k    k ; 3) k      k . s(1, 2) s(1, 1) s(2, 2) s(2, 1)   0 Fig. 1. Elementary grid cell  i , i  , i  1, 2 +3 +2 + +3 +2  +   0 Fig. 2. Sequence of cells on quasi-regular grid. From formulas (3) and Fig. 2 it is seen that the coordinate grid along the lengthwise coordi- nate  is regular with step  . In transverse coordinate  the angular grid size increases linearly with a constant step  : k    k  ; k      k  . So, such a grid is fairly called quasi-regular. The illustration of quasi-regular 44 grid is shown on fig. 3. Let's consider the element of two-dimensional Radon transform 10 (the so-called directed "butterfly" graph). It's shown on fig. 4. Fig. 3. Quasi-regular 44 grid. Radon base 2 formal vector Butterfly s11 s11+ s12 s12 s11- s12 Wk+N/2r s21 s21+ s22 s22 s21- s22Wk+N/2r Fig. 4. Radon base 2 vector butterfly. In conclusion, we present the schemes of the specialized tomographic processor and the control system of the process of detection of anomalies, developed on the basis of the method of analytic hierarchy process with the prioritisation of key performance indicators 11. As noted in 12, any automated system consists of three job levels: field, executive and interface (fig. 5). Fourth level, which serves for decision-making, is the highest one. ACS levels REAL-TIME OPERATING SYSTEM UPPER LEVEL Human-machine interface, dispatch system INTERMEDIATE LEVEL Programmable logical controllers, regulation devices, counters etc. LOW LEVEL Instrumentation, sensors, actuators and devices Fig. 5. Abstract diagram of 3-level automated control system (ACS) of technological processes. The automated hierarchical multilevel system has the following levels. 1. Field level or object level. It includes sensors and actuators (remote controls). 2. The lower level or level of controllers in which signals, sensors and actuators are con- nected to the network layer. 3. Network layer or data layer. These are telecommunications and computer networks de- signed to share and exchange information. Depending on the geographical location of the facili- ty, its size, the complexity of the infrastructure, various physical transmission media, such as copper or fibre-optic cables, radio and radio relay lines, including space lines, may be used. The network layer is usually divided into separate zones, each of which has intermediate servers installed and local control subsystems are organized. 4. Top level or level of processing and decision-making. It has operator stations, system (central) servers. The servers contain all the archival information, databases and knowledge, system software. Operator stations (automated workstations - ARM) display mnemonics of functional systems of the object with all current parameters being measured. The operators control the technological processes, and their decisions are transferred to the central control room, where the correctness and mutual consistency of these decisions, the absence of contra- dictions, etc. are monitored. Thus, a hierarchical multilevel system is a symbiosis of decentralized and centralized man- agement systems. In a rational construction and tuning, it combines the advantages of previous systems and is to some extent free from their disadvantages. Hardware and software components are distinguished in the remote parameter control sub- system. The following are components of hardware:  sensors;  controllers;  controllers' matching devices with sensors and actuators;  modules of digital I / O interfaces;  additional systems (control of performance, external conditions, etc.);  Operator stations, servers, network equipment;  communication and communication lines. In accordance with the presented scheme and on the basis of the results of the synthesis of the device for joint processing, a functional diagram of the specialized tomographic processor is developed. The processor is implemented in hardware with the use of unified architecture mathematical co-processors for different modes – interpolation, rotation and vectorisation of components of a 2D signal. The mathematical co-processors also compute the smoothing func- tions of the -filter. The processor diagram is depicted in Fig. 6. U(xm) U(k) xm Vector interpolator Vector interpolator 2D inverse DRT 2D DRT through (modified through inverse (modified Newton's Newton's FFT FFT ym procedure) procedure) G(xm, ym) U(ym) U(k) G(k,k) Fig. 6. Applied-specific tomographic circuit for processing 2D signals. G  xm , ym  –resulting signal from direction  k ;  xm , ym  – projections of space spec- trum frequencies under the angle  k on axes fx , f y of space-frequent plane; Gk  k , k   Gi k , k U k  – estimate of space spectrum section Given the advanced capabilities of specialized digital computers, it is logical to develop a tomographic detection / measurement device based on a specialized digital signal processor. Consider a functional diagram of a tomographic processor. To substantiate the architecture of the processor, recall that in the most general case, the transformation of Radon S is an integral along the lines    , r   x   x1 , x2  2 , x1 cos   x2 sin   r,  0,  , r  :  f  , r    f  r cos    sin , r sin    cos   d  , where    is a Euclidean space of absolutely smooth functions integrating quadratically on 2   set. a  2 It is theoretically possible to imagine the Radon transform as a Fourier transform in a polar coordinate system with a smoothing r-filter. The so-called mathematical coprocessors CP 1 and CP2 play the role of calculators of smoothing functions of the -filter. Since the function f  r cos    sin , r sin    cos   is neither even nor odd, the Fou- rier cosine transform and sine transforms must be performed separately. This task must also be solved with the help of the mathematical co-processor CP3. The CP4 mathematical coprocessor is designed to calculate the sum of squares of the cosine ( ucos out ) and sine ( usin out ) com- ponents of a signal. The purpose of the other elements of the tomography processor is clear from Fig. 7. xm МCP1 Inverse FFCT RAM1c (cosine- VMM RAM2c FFCT RAM3c Processor -filter) Processor cos sin zm MCP3 MCP4 RAM4 cos sin ym MCP2 Inverse FFST RAM1s (sine- VMM RAM2s FFST RAM3s Processor -filter) Processor Fig. 7. Functional diagram of a specialized tomographic processor. FFCT Processor is Fast Fourier Cosine Transform Processor; FFST processor is a Fast Fou- rier Sine Transform Processor; RAM is a random access memory device; VMM is a device of vector-matrix multiplication; MCP is mathematical coprocessor; zm  xm2  ym2 . Mathematical coprocessors grounded on application-specific integrated circuits (ASIC) are required for the implementation of the algorithm of Fast Radon fan transform. In the case under consideration, mathematical coprocessors should be powerful and high-speed. Mathematical coprocessor is a coprocessor for extending a plurality of central processing unit (CPU) commands. It extends the CPU functionality of the floating-point hardware module to processors that do not have a built-in module. Floating-point unit (FPU) - part of the processor to perform a range of required mathemati- cal operations over numbers. In accordance with the Volder's algorithm, Z n : Z n 1  d n 1  arctg  2n 1  ;   1, zk  0; X n : X n 1  Yn 1  2n 1i  d n 1 ;  dk   (4)   1, else. Yn : Yn 1  X n 1  2 n 1  d n 1 ,   Conventional "integer" processors require proper support procedures and time to perform real numbers and mathematical operations. The floating-point operations module supports them at the level of primitives - loading, unloading a real number (to / from specialized registers), or mathematical operation on them is performed by one command. Due to this, a significant accel- eration of such operations is achieved. Using the Briggs method, the so-called CORDIC algorithm was developed - COordinate Rotation DIgital Computer - a correlation rotary digital computer. In the CORDIC algorithm, the vector can be inverted through a widely used iterative algorithm for generating trigonomet- ric and transcendental functions. The CORDIC algorithm was proposed by Volder and then modified by Walter who has included circular, linear and hyperbolic transforms. Representing the vector through its components x, y identifies each of these modes: (vectorisation) and rotation, depending on the angle of rotation of the vector. The basic idea of this algorithm is to split the rotation operation into a sequence of some elementary rotations. The rotation is accomplished by a shift and an arithmetic addition operation. Calculation of sine and cosine can be done using circular CORDIC in rotation mode at any desired angle. The algorithm is as follows. To implement the Radon discrete transform algorithm, it is necessary to form a linear sample of values x and у: x  xm  xmin  mx, m  0, M  1; (5) y  yn  ymin  ny, n  0, N  1. In general, M  N . Let yk  k sin k , 0  k  N  1 . Then the integral is superimposed by sum M 1 N 1 f    k , k     f  m cos m  rn sin n ,  m sin m  rn cos n  (6) m0 n0 To implement the basic equations (5-6), the processor uses two controlled arithmetic- logic devices (ADCs), which either add or subtract two 16-bit additions depending on the control signal formed by equation (8), that is, for the controller signal = 0, it executes (A + B) and for control signal = 1 it executes (AB). The addition-subtraction unit receives either x-in or y-in (or (A-B) real or imaginary component) as one input and a displaced version of the second as the second input. The offset value depends on the amount of iteration in the CORDIC loop as the amount of correct input offset to the variable switch ranges from 0 to 15 for the 16-bit precision module. The operations of converting the current quadrant are performed with the help of the copy of the senior significant bit (SPD) into the cell of the next regular bit. Any angle of ro- tation from 0 to 2p, located in an arbitrary quadrant, is sufficient to convert within the basic operating range from -p / 2 to p / 2. The initial conversion operation is carried out by copy- ing the normalized MSB of the angle of rotation k in the additional code to the MSB-1 multiplexer. In Fig. 7 A diagram of a coprocessor for vectorization and rotation of angles isin fig. 7. The main definitions are given in table 1. Table 1. Table captions should be placed above the tables. Heading level Example CSG control signals generator ALU arithmetic and logical unit CD MSB most significant bit copy device CD control device ComD compare device MUX multiplexer MST memory and search table ACRM angle quadrant converter in rotation mode 0 generator of zero code g digital amplifier (multiplication device on g coefficient, g>1) =1 XOR device delay device If we consider the two-dimensional butterfly of Radon transform on the selected grid, then, taking into account the conservatism of the angles, the computational complexity calc is:  in coordinate  : calc  N log2 N  ;  in coordinate  ; calc  N  M  log2  N  M  , where N and M – numbers of samples  and  . The computational complexity of orthogonal transformation algorithms based on fast Fou- rier transform in all cases does not exceed the polynomial. Taking into account that in the direct calculation (without interpolation) of two-dimensional 4   fast Radon transform, the computational complexity is calc N , then it's clear that saving computing costs is significant. 0 ComD 0 CSG1 ALU 1 xinp 1 ALU4 xout Shift1 =1 1 CSG4 Counter [0…15] g 0 Shift2 0 0 ПП ComD ALU 2 yinp 0 yout ALU5 1 Calculation CSG2 mode 0 0 0 ComD 0 ComD uk CDMSB 1 CSG 3 0 arctg (yout/xout) ALU 3 MST ALU6 14 MUX ACRM Control 15 Calculation Device mode Fig. 7. CORDIC mathematical coprocessor. Conclusions In accordance with the presented scheme and on the basis of the synthesis results of the co- processing device (Fig. 7), a functional scheme of a specialized tomographic processor was developed. The processor is implemented in hardware using mathematical co-processors of unified architecture for different modes - interpolation, rotation and vectorisation of compo- nents of two-dimensional signal [13-19]. Mathematical coprocessors also calculate the smooth- ing functions of the r-filter. Thus, a specialized tomographic system for detecting anomalies (through holes) in pressure pipelines, on the one hand, is a system synthesized on the basis of statistical models of acoustic signals and interference, and on the other hand, it is built according to a modern three-level control and control scheme. Such construction gives additional possibilities for modification, scaling and expansion of system capabilities. References 1. Bates R.T.H. Image Restoration and Reconstruction (Oxford Engineering Science Series) / R. H. T. Bates, M. J. McDonnell. - Oxford, Clarendon, 1986. - 304 pp. 2. Caratheodory C. Conformal Representation / Courier Corporation, 1998 - 115 pp. 3. Dutt A., Rokhlin V. Fast Fourier transforms for non-equispaced data // Applied and Com- putational Harmonic Analysis. 1995. Vol. 2. P. 85 – 100. 4. Beylkin G. On Applications of Unequally Spaced Fast Fourier Transforms / Mathematical Geophysics Summer School, Stanford, August 1998, pp. 1 - 8. 5. Bressler Y. Three-Dimensional Reconstruction from Projections with Incomplete and Noisy Data by Object Estimation // Y. Bressler, A. Masovski. – IEEE Trans. on Acoust., Speech, and Signal Proc., Vol. ASSP-35,No 8, Aug. 1987. – pp. 1139 – 1152. 6. George A. Baker. Padé Approximants, 2nd ed. / George A. Baker, Jr., Peter Graves-Morris, Susan S. Baker. - Cambridge University Press, 1996. - 746 pp. 7. Luke Y.L. The Special Functions and Their Approximations / Academic Press, 1969. – 348 pp. 8. John F. Lectures on advanced numerical analysis. – Thomas Nelson and Sons Ltd., 36 Park Street London, 1966. - 179 pp. 9. Samarsky A.A. Introduction to numerical methods. – M.: Nauka, 1982. - 286 pp. 10. Dudgeon D.E., Mersereau R.M. Multidimensional Digital Signal Processing. Prentice- Hall, Englewood Cliffs, New Jersey, 1983. - 400 pp. 11. Saaty T. L. The analytic hierarchy process. McGraw Hill, N.-Y., 1980, 288 pp. 12. Ponomarenko O. V. Computerized system of detecting fistulas in product pipelines. – PhD-of-science thesis Specialty 05.13.05 - computer systems and components. - Kyiv, NAU, 2011. 13. Mazin Al Hadidi, Jamil S. Al-Azzeh, R. Odarchenko, S. Gnatyuk, A. Abakumova, Adap- tive Regulation of Radiated Power Radio Transmitting Devices in Modern Cellular Net- work Depending on Climatic Conditions, Contemporary Engineering Sciences, Vol. 9, № 10, рр. 473-485, 2016. 14. Al-Azzeh J.S., Al Hadidi M., Odarchenko R., Gnatyuk S., Shevchuk Z., Hu Z. Analysis of self-similar traffic models in computer networks, International Review on Modelling and Simulations, № 10(5), pp. 328-336, 2017. 15. Fedushko, S., Ustyianovych, T., Gregus, M. Real-time high-load infrastructure transaction status output prediction using operational intelligence and big data technologies. Electron- ics (Switzerland), Volume 9, Issue 4, 668. (2020) DOI: 10.3390/electronics9040668 16. Odarchenko R., Abakumova A., Polihenko O., Gnatyuk S. Traffic offload improved meth- od for 4G/5G mobile network operator, Proceedings of 14th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET-2018), pp. 1051-1054, 2018. 17. R. Odarchenko, V. Gnatyuk, S. Gnatyuk, A. Abakumova, Security Key Indicators As- sessment for Modern Cellular Networks, Proceedings of the 2018 IEEE First International Conference on System Analysis & Intelligent Computing (SAIC), Kyiv, Ukraine, October 8-12, 2018, pp. 1-7. 18. Z. Hassan, R. Odarchenko, S. Gnatyuk, A. Zaman, M. Shah, Detection of Distributed De- nial of Service Attacks Using Snort Rules in Cloud Computing & Remote Control Sys- tems, Proceedings of the 2018 IEEE 5th International Conference on Methods and Systems of Navigation and Motion Control, October 16-18, 2018. Kyiv, Ukraine, pp. 283-288. 19. M. Zaliskyi, R. Odarchenko, S. Gnatyuk, Yu. Petrova. A. Chaplits, Method of traffic monitoring for DDoS attacks detection in e-health systems and networks, CEUR Work- shop Proceedings, Vol. 2255, pp. 193-204, 2018.