ITMO University
“Programming Technologies” Department

Application for Contest of Research Projects in the Field of Automation of Designing of Integrated Circuits.
Intel Corporation and Moscow Physicotechnical Institute (Technical University)

1. Project name - "Decomposition and Logical Synthesis of Boolean Functions in Arbitrary Logical Elements Basis".

2. One of the most important problems in the field of logical synthesis is the problem of construction of combinational circuit, which realize boolean functions, using arbitrary, a priori known logical elements. There are two approaches to combinational circuit construction: from inputs to output and from outputs to input.

   Among methods, based on the first approach, lets note method, which was named "formula method" (Artuhov V.L., Kopeikin G.A., Shalyto A.A. Adjustable Modules for Controlling Logical Devices. Leningrad.: Energoizdat, 1981. 168 p.).

   When using this method, boolean function which is to be realized and function, which describes the element (elements generating function), are specified with normal boolean formulae, which may use set of brackets of any depth and dyadic operations, which are subjected to associative law. This method allows to construct circuit with single output. Amount of elements in this circuit arcwise depends on amount of letters in source formula (Artuhov V.L., Kopeikin G.A., Shalyto A.A. Bounds on the Realization Complexity of Boolean Formulas by Tree Circuits of Tunable Modules //Automation and Remote Control. 1982. Vol.42. N11, p.1532-1537).

   Among methods, based on the second approach, lets note method, which was named "multiplexer method" (Shalyto A.A. Logical Control. Methods of Hardware and Software Implementation of Algorithms. St.Petersburg: Nauka (Science), 2000. 780 p.).

   When using this method boolean function, which is to be realized and function, which describes the element are specified with truth-tables. This method allows to construct circuit from output to inputs. This method is based on decomposition of boolean functions (of given one and of its residual functions).

   While developing multiplexer method following tasks were accomplished:

   • we prepared review of methods of boolean functions construction using arbitrary logical elements and showed that this task wasn't solved though 50-years history of it;
   • we defined concept of "multiplexer decomposition". This decomposition executes in manner of multiplexer function. It serves as separating decomposition;
   • we suggested standard circuit, which consists of multiplexer and two permanent storage devices. This circuit realizes multiplexer decomposition;
   • we suggested method of construction of multiplexer decompositions, based on efficient approach of logical equations solving. Next to nobody was on success to solve these equations "beautifully" for 100 years (Lowenheim L. Uber die Auflosung von Gleichungen in Logishen gebietkalkul. //Math. Annal. 1910. Bd.68);
   • we suggested parametrical and explicit multiplexer forms for logical equations solving. Using equation, which is in one of these forms, it is easy to define the amount of solutions. There are constructive and obvious approaches to the solution for all of these forms. Choice of particular solution on each step at present time performs heuristically;
   • we suggested multiplexer method of realization of arbitrary boolean functions using arbitrary (but given a priory) logical elements. This method is based on studying of functional abilities of mentioned elements, composing and solving logical equation in multiplexer form, for each step of decomposition. Suggested method serves as generalization of the commonest method of synthesis of circuits, using multiplexers;
   • having taken examples from books, we compared suggested universal (by type of functions, which describes elements, used in synthesis) method with known methods of circuits synthesis, which use elements of the definite type (for example, majority elements).

   We showed that in these cases suggested method constructs circuits, which difficulty, as usual, isn't more than difficulty of circuits constructed using specialized methods.

   There are reasons to suppose that stated methods aren't known in the Occident, but they may be very efficient for constructing irregular combinational circuits in basis of arbitrary library elements, which are used for construction of very large-scale integration circuits.

   Further perfection of these methods connected with efficient (by the amount of elements) construction of combinational circuits with many outputs.

3. Project manager - Shalyto Anatoly Abramovich, doctor of technical science, professor, to head the department "Informational technologies" of Saint-Petersburg Institute of Fine Mechanics and Optics (Technical University) - SPbIFMO (TU).

4. Group staff - students and graduate student of department "Computer technologies" SPbIFMO (TU), participants and winners of finals of students team world programming championship Association for Computing Machinery (Ђ‘Њ), and students team world cybernetics championship Instrumental Society of America (ISA):

   • Shtuchkin Alexander - student of 3-rd course, champion of Russia in programming (2001), participant of final of ACM championship (2002), third place (gold medal) of final of ACM championship (2003);
   • Stankevich Andrey - student of 5-th course, third and fourth places (gold and silver medal) of finals of ACM championship (2001, 2000);
   • Korneev Georgiy - student of 5-th course, third and fourth places (gold and silver medal) of finals of ACM championship (2001, 2000);
   • Kazakov Matvey - first year graduate student, third place on ACM championship (1999);
   • Levkin Vladimir - first year graduate student, third place on ACM championship (1999);
   • Shamgunov Nikita - second year graduate student, three times - champion of Ural in programming (1998-2000), participant of finals of ACM championship (2000, 1999);
   • Tukkel Nikita - forth year graduate student, first place on ISA European championship (1999), second place on ISA world championship (1999);
   • Naumov Lev - student of 4-rd course, three times - "Soros's student".

   Main scientific works of authors of the project, which was complete during last year.

   Directly on the projects topic:

   1. Shalyto A.A. Multiplexor Method for Realization of Boolean Functions by Circuits Composed of Arbitrary Logical Elements //Journal of Computer and Systems Sciences International. 2003. Vol.42. N1, p.101-105.
   2. Shalyto A.A. Multiplexer Method of Realization of Boolean Functions, Using Circuits Made of Arbitrary Logical Elements // Section 3.5 in book "Control in Conditions of Vagueness". SPb.: SPbSTU (State Technical University), 2002, p.186-194. [in Russian]
   3. Shalyto A.A. Modules which Are Universal in the Class of Self-Dual Functions and in Close Classes //Journal of Computer and Systems Sciences International. 2001. Vol.40. N5. p.782-792.
   4. Shalyto A.A. Modules with Paraphase the Input Variables That are Universal in Class of All Boolean Functions //Journal of Computer and Systems Sciences International. 1997. Vol.36. N5. p.794-801.
   5. Artyukhov V.L., Kopeikin G.A., Shalyto A.A. Bounds on the Realization Complexity of Boolean Formulas by Tree Circuits of Tunable Modules //Automation and Remote Control. 1982. Vol.42. N11. p.1532-1537.
   6. Artyukhov V.L., Kopeikin G.A., Shalyto A.A. Estimation of the Logical Efficiency of Integrated Microcircuitry //Automatic Control and Computer Sciences. 1981. Vol.22. N1. p.32-34.

   Close to projects topic:

   7. Shalyto A.A. Realization of Boolean Formulas and Boolean Functions by Homogeneous Structures //Journal of Computer and Systems Sciences International. 2002. Vol.41. N2, p.264-273.
   8. Artyukhov V.L., Shalyto A.A. Realization of Boolean Formulas by Uniform Multiplexor and Majority Cascades //Journal of Computer and Systems Sciences International. 1996. Vol.35. N5. p.805-815.
   9. Artyukhov V.L., Shalyto A.A., Kuznetsova O.S. Evaluation of the Functional Capabilities of Programmable Logical Arrays //Automatic Control and Computer Sciences. 1985. Vol.26. N2. p.69-73.

   Programming, using automata - automata programming:

   10. Shalyto A.A., Tukkel N.I. Tanks and Automatons // BYTE/Russia. 2003. ь2, p. 69-73.
   11. Shalyto A.A., Tukkel N.I., Shamgunov N.N. Task of Knights Move // Mir PK (PC World). 2003. ь1. p. 152-155. Article is available in Russian on http://is.ifmo.ru.
   12. Shalyto A.A., Tukkel N.I., Shamgunov N.N. Hanoi Towers and Automata // Programmist (Programmer). 2002. ь8. p. 82-90. Article is available in Russian on http://is.ifmo.ru.
   13. Shalyto A.A., Tukkel N.I. Translating Iterative Algorithms into Automation Ones //Programming and Computer Software. 2002. 28(5).
   14. Shalyto A.A., Tukkel N.I., Shamgunov N.N. Realization of Recursive Algorithms Using Automata Approach // Telecommunications and Informatization of Education. 2002. ь5. p. 72 99.
   15. Shalyto A.A., Tukkel N.I. Automata Realization in Programming of Event Systems // Programmist (Programmer). 2002. ь4. p. 74-80. Article is available in Russian on http://is.ifmo.ru.
   16. Shalyto A.A., Tukkel N.I. From Turing Programming to Automata Programming // Mir PK (PC World). 2002. ь2. p. 144-149. Article is available in Russian on http://is.ifmo.ru.
   17. Shalyto A.A. Logic Control and "Reactive" Systems: Algorithmization and Programming //Automation and Remote Control. 2001. Vol.62. N1. p.1-29. http://is.ifmo.ru/?i0=english&i1=log_control.
   18. Shalyto A.A., Tukkel N.I. SWITCH-Technology: An Automated Approach to Developing Software for Reactive Systems //Programming and Computer Software. 2001. 27(5). http://www.maik.ru/, http://www.wkap.nl/.
   19. Shalyto A.A. Software Automation Design: Algorithmization and Programming of Problems of Logical Control //Journal of Computer and Systems Sciences International. 2000. Vol.39. N6. p.899-916. http://www.maik.ru/.
   20. Shalyto A.A. Algorithmic Graph Schemes and Transition Graphs: Their Use in Software Realization of Logical Control Algorithms. II. //Automation and Remote Control. 1996. Vol.57. N7. p.1027 - 1045. http://www.maik.ru/, http://www.wkap.nl/.
   21. Shalyto A.A. Algorithmic Graph Schemes and Transition Graphs: Their Use in Software Realization of Logical Control Algorithms. I. //Automation and Remote Control. 1996. Vol.57. N6. p.890 - 897.

   We also developed new methods of construction of multifunctional logical modules from elements with single- and double-sided conductivity.

   Other works of project manager, which were made in previous years are listed on http://is.ifmo.ru in section "Personalities".