Извините, этот техт доступен только в “Американский Английский”. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.
THE METHOD AND MULTIPLE DEVICE OF A MATRIX SEARCH FOR SIMPLE AND COMPLEX SAMPLES
Evgeny A. Titenko, The Southwest State University, Kursk, Russia, johntit@mail.ru
Alexey N. Schitov, The Southwest State University, Kursk, Russia, a.n.schitov@mail.ru
Abstract
The research consists in the development of hardware pattern search methods that use the principles of shared access and parallel data processing inherent in associative memory. Reducing the search time is achieved through the formation and parallel processing of a binary (characteristic) matrix of comparisons of pattern symbols and text. A composite pattern has been introduced, it allows flexible description of search terms. The characteristic matrix is in the form of a parallelogram; it consists of rows shifted to the right, starting from the first row. This form allows you to conduct a parallel search for simple and composite patterns on the diagonal elements of the matrix. The developed method supports hardware search in the characteristic matrix. It is distinguished by the simultaneous consideration of local and distributed relationships between the elements of the diagonals and rows of the matrix. Separate calculation of starting values along the diagonals of the matrix allows you to independently search for two types of samples by calculating in the cells of the diagonals of the characteristic matrix of two output search functions. The method has linear time and quadratic hardware complexity. The clock pulse duration is determined by the sum of the delays of the comparison circuit for a pair of symbols, a D-flip-flop and a two-input element I. The homogeneous structure of the matrix search device, the use of standard operations allow the device to be implemented on a promising FPGA element base, which determines its use in high-performance systems for processing and transmitting heterogeneous information.
Keywords: characteristic matrix, diagonal search, occurrence, string operand.
References
1. I.V. Ognev, V.V. Borisov, N.A. Stool (2016). Associative memory, environments, systems. Moscow: Hot line – Telecom. 420 p.
2. I.V. Ognev, V.V. Borisov (1996). Intelligent systems of associative memory. Moscow: Radio and communication. 176 p.
3. I.S. Zerin, O.I. Atakischev, E.A.Titenko, O.F. Korolkov, A.O. Atakischev. (2012. Method, algorithm and technical solution of parallel search and substitution on associative memory. In the world of scientific discoveries. No. 1-1 (25). P. 166-180.
4. T.A. Mirtalibov, S.N. Frolov A.L. Khanis, E.A. (2015). Titenko Multiagent systems in technical diagnostics of complex technical objects. News of the South-West State University. No. 3 (60). P. 18-25.
5. A.G. Kurochkin, S.G. Emelyanov, E.A. Titenko (2014). Analysis of pattern-based search algorithms for controlling a group of robots. Science-intensive technologies. Vol. 15. No. 12. P. 4-8.
6. A.V. Kalyaev, I.I. Levin (2003). Modularly expandable multiprocessor systems with structural and procedural organization of computations. Moscow: Yanus-K. 380 p.
7. J.F. Luger (2003). Artificial intelligence: strategies and methods for solving complex problems. Moscow: Williams Publishing House. 864 p.
8. A.A. Markov (2007). Selected Works. vol. 2. Theory of algorithms and constructive mathematics, mathematical logic, computer science and related issues. Moscow: MTsNMO. 650 p.
9. J. McConnell (2006). Fundamentals of modern algorithms. Moscow: Tekhnosfera. 368 p.
10. A. Wichert (2016). Artificial intelligence and a universal quantum computer. AI Communications. Vol. 29. Issue 4. P. 537-543.
11. A. Stephen Graham (1994). String searching algorithms. Lecture Notes Series on Computing. Vol. 6. Singapore: World Scientific Publishing.
12. E.A. Titenko (2011). Method and homogeneous computing device of k-approximate search for occurrences by pattern. Bulletin of the Voronezh State Technical University. Vol. 7. No. 7. P. 70-78.
13. Patent 2549525 RF, IPC G06 F 12/00, G06 F 17/30. Method and device for searching a composite sample in a sequence / A.V. Kripachev, E.A. Titenko, R.V. Bredikhin, Belokopytov A.V., Kurochkin A.G .; applicant and patentee Yugo-Zap. state un-t.: Appl. 07/15/2013; publ. 04/27/2015, Bull. No. 12.
14. V. Maksimov (1995). Search algorithms, or how to search for unknown what Monitor. No. 6. P. 10-16.
15. B.A. Kulik (1987). Search systems in free text. Programming. No. 1. P. 6-10.
16. S. Wu, U. Manber. Fast text searching allowing errors, Commun. ACM. 35 (10): 83-91.
17. E.A. Titenko, S.V. Degtyarev (2017). Search in the sample on the basis Manber-Wu method. Journal of Fundamental and Applied Sciences. Vol. 9. No. 2. P. 914.
18. E.A. Titenko (2011). Parallel pattern search method and matrix device for its implementation. Information systems and technologies. No. 4. P. 24-30.
19. Patent 72771 Russian Federation, IPC G06 F 12/00. Device for parallel search and data processing / E.A. Titenko, L.A. Lisitsin, V.M. Dovgal; applicant and patentee Kursk. state tech. un-t. No. 2007149075/22: app. 12/25/2007; publ. 27.04.2008, Bull. No. 12.
20. E.A. Titenko (2011). Hardware-oriented algorithm and homogeneous computing device for comparing words. Bulletin of computer and information technologies. No. 11. P. 51-56.
21. I.S. Potemkin (1988). Functional units of digital automation. Moscow: Energoatomizdat. 320 p.
22. O.P. Novozhilov (2013). Fundamentals of digital technology. Tutorial. Moscow: IP Radiosoft. 528 p.
23. E.V. Melnik, A.B. Klimenko, D.Ya. Ivanov, V.A. Gandurin (2016). Methods for ensuring uninterrupted operation of network-centric information-computing systems with clustering. News of the Southern Federal University. Technical science. No. 12 (185). P. 71-84.
24. A.M. Vinogradenko, N.P. Budko (2020). Adaptive control of the technical state of autonomous complex technical objects based on intelligent technologies. T-Comm. Vol. 14. No. 1. P. 25-35.
25. V.G. Dovbnya, S.N. Frolov, K.P. Sulima, A.N. Shchitov (2020). Specificity of Implementation of control systems based on LORAWA technology. T-Comm. Vol. 14. No. 9. P. 24-30.