Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

The algorithm for synthesis of digital ICs based on the Gilbert decomposition
Authors
	Gurov S.I.
	Ryzhova D.I.
Date of publication
	2016
Abstract
	Today the problem of digital IC synthesis optimization is still continued to be relevant. In the process of design automation, methods oriented to the regular representations of combinational circuit parts are preferable in terms of reliability at the logical level and testing. Such representations of microsystems logical blocks can be obtained directly from the Gilbert decomposition. This article describes the algorithm of synthesis for combinational circuit that implements an arbitrary Boolean functions. It is based on the representation of partial Boolean function f in the form where are monotonic functions, and the F is the optimal extending the definition of f, in a certain sense. Functions we propose to call Gilbert functions, and formula – Gilbert decomposition for Boolean function (BF) f. Although on a text of this article algorithm for finding Gilbert functions can be restored, the direct use of this algorithm in many practically important cases can cause serious difficulties because of the operation of taking the function negation. In practice, the BF and their systems are often specified as tables of a special type, rows of which describe values of the functions on the edges of the Boolean n-dimensional unit cube In this case, receiving a table for the inverse function can be very laborious. This is due to the fact that these tables allow the presence of intersecting intervals at which the function can take various values. At the same time to determine the BF value in the area of the intervals intersection it is necessary to consider the priorities of the values on which the table is based. If the priorities of the values 0 and 1 are not equal, then the inverting of function with n variables (function is defined on the l intervals) requires the fulfillment of O(n•l) operations. This circumstance and the experience of the authors show that the efficiency of algorithm operation is largely depend on realization of inverting operation for the table-defined functions. For this reason, the efficient way of finding the negations for commonly used system of priorities of table-defined functions values is proposed. On the basis of this decomposition algorithm of circuit synthesis is implemented. It is calculated f in the actual design basis of microelectronic LSI. The algorithm operates as a part of automatic synthesis system for combinational logic blocks of LSI. An algorithm for finding Hilbert functions was programmed and was included in the LORD system for automatic multi-level synthesis of combinational logic blocks of digital integrated circuits. LORD system was created by the authors in the Research Institute of Molecular Electronics MEI of the USSR as one of the component of «Arc / ws» CAD system. An example of algorithm operation is given in the section III. As a result, the circuit realization of the video controller key as a table in size 10x36 only 18 functional elements are required. If we consider the realization of this circuit in CMOS technology, at least two transistors are necessary for each input of element. In our case the function of video controller key can be implemented using only 40 transistors.
Keywords
	Boolean function, combinational circuit, stroke (Sheffer) function
Library reference
	Gurov S.I., Ryzhova D.I. The algorithm for synthesis of digital ICs based on the Gilbert decomposition // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2016. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2016. Part 1. P. 48-55.
URL of paper
	http://www.mes-conference.ru/data/year2016/pdf/D023.pdf