Приведены отсутствующие в литературе последних десятилетий клеточно-автоматные формулировки алгоритмов сортировки массивов символов и строк. Впервые предложен клеточный автомат, умножающий два целых числа, записанных в системе счисления с произвольным основанием. Алгоритм основан на схеме параллельного умножения Атрубина для систолического массива процессоров и требует четыре компонента (регистра) вместо пяти.
Матюшкин Игорь Валерьевич
Институт проблем проектирования в микроэлектронике Российской академии наук, г. Москва, Россия; Национальный исследовательский университет «МИЭТ», г. Москва, Россия
1. Stempkovsky A.L., Vlasov P.A., Kozin G.V. Algorithmic environment for VLSI design on cellular automata // Proc. of a Joint Symposium: Information Processing and Software, Systems Design Automation (Moscow, June 5/6, 1990). SpringerVerlag, 1990. P. 308312.
2. Kim K.-W., Lee W.-J. Efficient cellular automata based montgomery AB2 multipliers over GF(2m) // IETE Technical Review. 2014. 31:1. P. 92102.
3. Fisher P.C. Generation on primes by one dimensional real time iterative array // J. ACM. 1965. 12. P. 388394.
4. Heen O. Efficient constant speed-up for one dimensional cellular automata calculators // Parallel Computing. 1997. Vol. 23. – N. 11. – P. 1663–1671.
5. Petraglio E., Henry J.-M., Tempesti G. Arithmetic operations on self-replicating cellular automata // Lecture Notes in Artificial Intellegence. 1999. Vol. 1674. P. 447456.
6. Bidlo M., Vasicek Z., Slany K. Sorting network development using cellular automata // Proc. 9th Intern. Conf. «Evolvable Systems: From Biology to Hardware» (York, UK, Sept. 68, 2010). London: Springer London, 2010. Р. 8596.
7. Atrubin A.J. A one-dimensional real-time iterative multiplier // IEEE Trans. on Electronic Computers. 1965. Vol. EC-14. N.3. Р. 394399.
8. Goyal L.N. Design of an arithmetic element for serial processing in an iterative structure // Computer Arithmetic: IEEE 3rd Symposium on. 1975. Р. 223231.
9. Goyal L.N. A note on atrubin's real-time iterative multiplier // IEEE Trans. on Electronic Computers. 1976. Vol. 25. N.05. P. 546548.
10. Shimon Even, Ami Litman. A systematic design and explanation of the atrubin multiplier // Sequences II / Eds. R. Capocelli, A. De Santis, U. Vaccaro. Springer Verlag, 1993. P. 189202.
11. Guy Even Real-time iterative systolic integer multiplier // Integration, The VLSI Journal. 1997. Vol. 22. N. 1-2. P. 2338.
12. Jebelean T., Szakacs L. Functional-based synthesis of systolic online multipliers // Proc. of the Seventh Inter. Symposium on Symbolic and Numeric Algorithms for Scientific Computing (Timisoara, Romania, Sept. 25–29 2005). 2005. – P. 267–275.