The main objective of the paper is identification of the target coordinates in the Hamming space in Cartesian coordinates, which is solved by digital processing of the input signals characteristics. The technical solution of the device is determination of linear estimate of the Euclidean distance in one-dimensional Hamming space. Achievement of the maximum speed of such device is implemented by means of optimized XOR logic elements with minimal hardware complexity and minimal signal delay per microcycle, which are comparable to the known structures of XOR elements, providing 2.5fold reduction in hardware complexity and two-fold increase in performance. Acoustic signals, correlators, special processors, Hamming space
The correlation method of sources of acoustic signals (SAS) search in the general case with certain calculations accuracy is reduced to the solution of the problem of searching SAS location coordinates in Cartesian or polar system, is shown in Figure 1. acoustic signals (RAS) in two-dimensional Hamming space
2023 Copyright for this paper by its authors.
Matrix of the Hamming space (HS) [1-4] in the form of two-dimensional discretization element (Figure 2) makes it possible to identify Cij target in HS with the polygon size i 1, n and j 1, m . Then the number Cij = n*m, respectively, will determine the number of solutions in the form of angles pairs definitions αi, αi = αij at the level of receivers of acoustic signals (RAS 1, RAS 2 and RAS 3), as shown in Figure 3.
j j+1 For example, it is necessary to identify target Cij in HS with select the characteristics of the basic distance
In order to simplify the calculations according to the expression
L 0 and the corresponding time delay of acoustic signal
L0 , it is reasonable to i αi
Oij L0
L αj
C11 αi
L0 N αi
N
L0 αi
N αi
C1m t at the speed of propagation of acoustic waves in the air in the form . Then
In order to simplify the algorithm for calculating the values of function sin with known speed of propagation of acoustic vibrations in the air, it is reasonable to select the basic distance between microphones (Figure 6).
The device for the calculation of modular correlation function is designed for digital correlation processing of analogue signals and can be used for direction finding of acoustic signal sources in twodimensional Hamming space [5-7].
The basis of the development is the task of reducing its hardware complexity and expanding the functional capabilities of the device due to three priority acoustic receivers and three parallel analogue-digital converters with binary output codes, three-input multi-channel digital device for calculating the modular correlation function, each channel of which contains the pair of threshold drives of digital modular differences between signals based on expressions
n d xy xi j yi mod P; i1 n d xz xi j zk mod P; i1 n d yz yi zk mod P,
i1 which are the output codes of the remote direction finding device and the spatial placement of acoustic signals source on two-dimensional polygon of Hamming space.
The task is solved by the fact that multi-channel device for calculating the modular correlation function, which contains receivers of acoustic signals, correlators, which outputs are connected to the corresponding inputs of storage devices, the outputs of which are the coordinate outputs of the device, in which the first, second and third automatic gain control devices , the inputs of which are connected to the outputs of the corresponding first, second, and third acoustic signals receivers, and the outputs are connected to the first inputs of the corresponding analogue-digital converters (ADCs) of the serial type with output binary codes of Rademacher theoretical-numerical base, the second output of the device of automatic adjustment of the gain of the first priority input channel у(t) of the device is connected to the start input of the synchronizer, the first output of which is connected to the second inputs of ADC, the first inputs of the synchronization of the multi-bit shift register and the first inputs of the logic elements І, the second output of the synchronizer is connected to the first reset inputs to “0” of all threshold accumulators of modular differences of digitized input signals of the first and second groups, S - inputs of the first and second RS - triggers the outputs of which are connected to the corresponding second inputs of the first and second counters, the first outputs of which are connected to the corresponding second and third inputs of the xi j yi , xi j zk , yi zk y z i second threshold accumulator of modular differences k , the output of which is connected to the first input of the coordinate system, the second and third inputs of which are connected to the second inputs of the corresponding first and second counters, and the outputs of the coordinate system are the code output of the spatial placement of the acoustic signals source in the polygon nodes of two-dimensional Hamming space.
Time diagram of the correlation determination of digital codes at the output of the device coordinate system, where t1 , t2 and t3 are time delays between acoustic signals is shown in Figure 7.
The structural diagram of multi-channel device for calculating the modular correlation function, which contains: 1.1, 1.2, 1.3 - respectively: the first priority, second and third acoustic signals receivers; 2 – automatic gain adjustment devices; 3 – matched filter of acoustic signals; 4 – reference acoustic signal input; 5 – synchronizer; 6 – parallel-type ADC with source codes in binary counting system of Rademacher theoretical-numerical basis; 7 – multi-channel shift register; 8 – logical elements I; 9 – threshold accumulator of modular differences; 10– RS – triggers; 11 – binary counters; 12–– modular-difference adder; 13 - coordinate system based on constant memory device (ROM) is shown in Figure 8 [7].
t1 |xi-j-yi| |xi-j-zk| |yi-zk| c 1 c 1 c 1 0 x(t) 0 z(t) 0 start 4
The device operates in the following way: at the beginning of the device operation cycle, So signal of the first output of synchronizer 5 forms the start pulse, which resets the memory registers of all storage adders of modular differences 9, trigger inputs 10, and binary counters 11 to zero state [7].
Input analogue acoustic signals x(t), y(t), z(t), which are generated by remote source of acoustic signals, enter the input of the acoustic signals receiver 1.1, which is located spatially closer to the source of acoustic signals and with certain time delay t1 and t2 accordingly enter the 7 inputs of the corresponding acoustic signal receivers 1.2 and 1.3. [7]. 9 9 The electrical signals formed at the outputs of acoustic signal receivers 1.1, 1.2 and 1.3 are fed to the inputs of the corresponding automatic gain 7 control devices 2, at the output of which electrical signals normalized by amplitude and positive 9 9 sample potential С are formed (Figure 8). The output signals of the automatic gain control 10 10 devices 2 generated in tsuch a way are fed to the 8 8 first inputs of the matching filters 3, the second inputs of which are connected to the input inputs 11 12 11 of the reference acoustic signals 4, and the 13 outputs are connected to the first inputs of the corresponding ADC 6 [7].
During the device operation cycle, the clock Figure 8: Structural diagram of multi-channel signals of the second output of synchronizer 5 Sx device for the calculation of modular synchronize the formation of output codes xi, yi correlation function and zi at the outputs of the corresponding ADC 6, the corresponding shifts of digital codes xi-j in multi-channel shift register 7, and pulses coming from the outputs of the corresponding logic elements І 8 to the inputs of the corresponding counters 10. At the same time, the corresponding threshold sums are formed in the modular difference adders 9 of the first and second groups
The accumulated sum of pulses in the first counter 11 t1 and in the second counter 11 t2 are supplied to the first and second inputs of the coordinate system 13, and the obtained modular difference in modular-difference adder 12 in the form of code t3 is supplied to the third input of the coordinate system 13, the output of which is the device output.
The structure of the device for determining the linear estimation of Euclidean distance in onedimensional Hamming space with binary values of the image characteristic is shown in Figure 9.
Xn Yn X3 Y3 X2 Y2 X1 Y1 Sn
XOR НС Sn-1
XOR НС S1
XOR НС S0
XOR characteristics на xi and yi
In general, with sample volume of characteristics xi and yi the device contains the following types and numbers of components: 1) n – logical elements "Exclusive OR" (XOR); 2) n-1 – incomplete one-bit binary adders (IA ).
The hardware and time complexity of such device is calculated according to the following expressions:
A n AXOR (n 1) AHC ; XOR (n 1) HC. (1)
Depending on the applied implementation of such microelectronic components structure, the corresponding characteristics of the device are calculated A - where is the number of FPGA valves and - where is the number of microcycles of signal delay at Sn the device output.
Classical microelectronic implementation of XOR logic element have the structure and characteristics presented in Figure 10 [1, 9].
It is evident from Figure 10 that the structures of XOR logical elements with direct inputs contain at least 4 logical elements of NOT, AND-NOT and OR-NOT types. Moreover, each structure has at least 3 serially connected logical elements. Thus, the hardware and time complexity of such component of the device with the structure presented in Figure 10, is respectively: XOR 3 .
Xi Yi
Si Pi+1
Xi Yi
Si Pi+1
Typical implementations of the structures of incomplete one-bit binary adders with direct inputs and outputs are presented in Figure 11. hardware and time complexity of such device components (Figure 9), is respectively:
AHC (5...8) , and HC 3...4 .
Thus, the calculation of hardware and time complexity of the device for determining Euclidean distance estimate in one-dimensional Hamming device according to expressions (1) at n=1024 is: A 1024 4 1023 ( 5...8 ) 9211 ...12280 ; 3 1023 ( 3...4 ) 3070 ...4093 .
In paper [8] microelectronic implementation of single-bit IA on 3 logic elements (Figure 12) where the logic element “Conductor I” is applied on 2 logic elements, which performs XOR logic operation with direct inputs and direct output is proposed, t.
Such component has hardware AHC 3 and time HC 1 complexity.
The application of such component in the device with the structure (Figure. 9) makes it possible to reduce its hardware and time complexity in the following way:
A 1024 2 1023 3 5117 ; 110231 1024.
Thus, the hardware complexity of optimized Euclidean distance estimator compared to typical component structures is reduced by more than 2 times, and time complexity is reduced by 2.9 - 3.99 times.
The evaluation of the speed of the digital device correlator is performed according to the expression that determines the total time delay of the signals in the serially connected components of the device structure: МК 5 7 8 9 10 11 12 13 , where 5 4 ; 7 2 ; 9 24*32 768 ( at the bit rate of digital codes хi j , y j , zk 8bit); 8 1 ; 10 2 ; 11 2 ( when synchronous binary counters are used); 12 27 (on ROM basis) ; 13 3 .
That is, the total delay of signals in digital correlator of such device is:
МК 8 2 768 1 2 2 27 3 813 microtacts.
The hardware complexity of such correlator is calculated according to the expression:
A=A5+A6+A7-10+A11+A12+A13=60+2048+831499+6+122+2048=835783.
Thus, the proposed device for the calculation of modular correlation function is characterized by increased speed, decreasing by two times the number of correlators of acoustic signals, and expanded functionality for implementing multi-channel device for calculating the modular correlation function.
For the first time, the structure and scheme of technical solution of the device for determining the linear estimate of Euclidean distance in one-dimensional Hamming space, by means of digital processing of the characteristics of input signals represented by binary codes, is proposed. The achievement of the maximum speed of such device is implemented by means of optimized XOR logic elements with minimal hardware complexity (2 AND-NOT and OR logic elements) and minimum delay of signals per one microcycle, which in comparison with known structures of XOR elements, provided the reduction of hardware complexity by 2, 5 times and two-fold increase in speed. The maximum speed of the developed Euclidean distance estimation device is achieved due to multi-bit combinational incremental adder based on incomplete one-bit binary adders with minimum delay of sum signals and end-to-end transfers per microcycle. This makes it possible to reduce the overall hardware complexity by more than two times, and to increase the speed of the devices by 3-4 times in comparison with known circuit-technical implementations of this digital device class.
[1] S. T. Birchfield and D. K. Gillmor, “Acoustic Source Direction by Hemisphere Sampling,” Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Salt Lake City, Utah, May, 2001. [2] A.M. Krivosheev, V.N. Petrenko, A.I. Prikhodko, Fundamentals of artillery reconnaissance: textbook. Ukraine, Sumy: Sumy State University, 2014. [3] Bohdan Trembach, Roman Kochan, Rostyslav Trembach. “Multiplex digital correlator with high priority deployment of one of the acoustic signal receivers”, Scientific Journal of TNTU, 4(84), 99-104, 2016. — http://visnyk.tntu.edu.ua/pdf/84/339.pdf [4] Bohdan Trembach, Roman Kochan, Rostyslav Trembach. “Methods of structural design optimization of software hardware problem identification of the spatial parameters of acoustic signals sources”, Scientific Journal of KNU, 1(245), 136-139, 2017. — http://lib.khnu.km.ua/pdf/visnyk_tup/2017/(245)2017-1-t.pdf [5] Bohdan Trembach, Roman Kochan, Rostyslav Trembach. “The method of correlation investigation of acoustic signals with priority placement of microphones”, in 14th IEEE International Conference on The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM), Polyana, Ukraine, 2017. — https://DOI: 10.1109/CADSM.2017.7916117 [6] Trembach B. Method of spatial identification of acoustic signals source in the two-dimensional Hemming space / B. Trembach // Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Serie: Kompiuterni systemy ta merezhi. — Lviv: Vydavnytstvo Lvivskoi politekhniky, 2017. — No 881. — P. 166–177. — https://doi.org/10.23939/csn2017.881.166 [7] B. Trembach, R. Kochan, R. Trembach. "The method of correlation investigation of acoustic signals with priority placement of microphones", Advances in Science, Technology and Engineering Systems Journal, vol. 3, no. 1, pp. 412-417 (2018) — https://astesj.com/v03/i01/. [8] I. Albanskiy, V. Pikh, T. Zavedyuk, G. Korniychuk, “Theory and Special Processors of Spectral Cosine Fourier Transformation Based on Various Correlation Functions in Hamming Space”. Proceedings of the XI–th International Conference ”Modern Problems of Radio Engineering, Telecommunications and Computer Science” (TCSET–2014), L’viv, Slavske, Ukraine, 2014, pp. 677-679. [9] J. M. Nykolaichuk, Theory of informationsources, Monography, Ukraine, Ternopil:TNEU, 2008.