Hardware implementation of Boolean functions based on the automaton model

Objectives. Currently, electronic control devices are increasingly being introduced into various household and production products. Microcontrollers of a wide variety of configurations are widely used as such devices. Another approach can be proposed where a control device with a standard structure is synthesized from typical integrated circuits and implements a Boolean function describing the required control actions.

The purpose of the work is to investigate the possibility of implementing Boolean functions using devices with a standard structure, the design of which is based on the use of a discrete automaton model.

Methods. The original Boolean function to be implemented is given as a disjunctive normal form. A binary  decision diagram (BDD) is built for such function, optimized by the number of vertices, on the basis of which a graph of transitions of a synchronous Moore automaton with an abstract state is formed. Further, after performing the state encoding step of the machine, input information for flashing (programming) of the matrix memory of the read-only memory (ROM) is generated based on its transition table.

Results. A device that implements a Boolean function based on an automaton model is synthesized from typical microcircuits. The main component is ROM, which, according to the standard structure of the device, is  supplemented by a shift register, a state register, a trigger and three selectors of the initial and two final states.

Conclusion. The process of designing a device with standard structure that implements the Boolean function, as a result, comes down to programming the ROM matrix memory based on an automaton transition table. The use of a reprogrammable ROM allows to change the functionality of the device while maintaining the previous circuit implementation. The disadvantage of such a device, as well as devices implemented on the basis of  microcontrollers, is the low speed, the advantage is the possibility of use it in various products and devices, primarily for household purposes, which do not require a high-speed response to the change of  input signal.

1. Belov A. V. Programmirovanie mikrokontrollerov dlya nachinayushchih i ne tol'ko Microcontroller Programming for Beginners and Beyond Saint-Petersburg, Nauka i tekhnika, 2016, 352 p. (In Russ.).

2. Kuz'min V. A. Realization of functions of the algebra of logic by automata, normal algorithms and Turing machines. Problemy kibernetiki [Cybernetics Issues], 1965, vol. 13, pp. 75–96 (In Russ.).

3. Hopcroft J. E., Motwani R., Ullman J. D. Introduction to Automata, Theory, Languages and Computation, 2nd edition. Addison-Wesley, 2000, 521 р.

4. Shalyto A. A. Logicheskoe upravlenie. Metody apparatnoj i programmnoj realizacii algoritmov. Logical Control. Methods of Hardware and Software Implementation of Algorithms. Saint-Petersburg, Nauka, 2000, 780 p. (In Russ.).

5. Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Fundamentals of Discrete Devices Design. Moscow, Fizmatlit, 2007, 592 p. (In Russ.).

6. Andersen H. R. An Introduction to Binary Decision Diagrams. Lecture Notes. Copenhagen, IT University of Copenhagen, 1999, 35 p.

7. Akers S. B. Binary decision diagrams. IEEE Transactions on Computers, 1978, vol. C-27, no. 6, pр. 509–516.

8. Bryant R. E., Meinel C. Ordered binary decision diagrams. Logic Synthesis and Verification. In S. Hassoun, T. Sasao, R. K. Brayton (eds.). Kluwer Academic Publishers, 2002, pp. 285–307.

9. Yang S., Ciesielski M. BDS: a BDD-based logic optimization system. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 7, pp. 866–876.

10. Bibilo P. N. Primenenie diagram dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Selection Diagrams in the Synthesis of Logic Circuits. Minsk, Belaruskaja navuka, 2014, 231 p. (In Russ.).

11. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications. Berlin, Heidelberg, Springer-Verlag, 1998, 267 p.

12. Ebendt R., Fey G., Drechsler R. Advanced BDD Optimization. Springer, 2005, 222 p.

13. Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascading Circuit. Moscow, Nauka, 1981, 416 р. (In Russ.).

14. Vemuri N., Kalla P., Tessier R. BDD-based logic synthesis for LUT-6-based FPGAs. ACM Transactions on Design Automation of Electronic Systems, 2002, vol. 7, no. 4, рр. 501–525.