The cellular automata formulations of the algorithm for sorting arrays of characters and strings, not available in literature of recent decades, have been presented. For the first time, the cellular automation, that multiplies two integers written in a number system with an arbitrary basis, has been proposed. The algorithm is based on the Atrubin’s scheme for parallel multiplication by means of a symbolic array of processors and requires four components (registers) instead of five.
Mariya A. Zapletina
Institute for Design Problems in Microelectronics of Russian Academy of Sciences, Moscow, Russia
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.