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 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):

    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:

    1. 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.
    2. 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.
    3. 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:

    1. Shalyto A.A., Tukkel N.I. Tanks and Automatons // BYTE/Russia. 2003. 2, p. 69-73.
    2. 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.
    3. 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.
    4. Shalyto A.A., Tukkel N.I. Translating Iterative Algorithms into Automation Ones //Programming and Computer Software. 2002. 28(5).
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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/.
    10. 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/.
    11. 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/.
    12. 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".