Lsi Logic Corporation

Sergej B Gashkov

Alexander Andreev

Aiguo Lu

An adder based circuit embodied in an integrated circuit includes an input module, a carry module and an output module. The carry module has a minimum depth defined by a recursive expansion of at least one function associated with the carry module based on a variable k derived from a Fibonacci series. Invertor, XOR, XNOR (more preferably, OR(NOT(a),b)) and multiplexer elements are selectively coupled to the input and output modules to configure the adder based circuit as a subtractor, adder-subtractor, incrementor, decrementor, incrementer-decrementor or absolute value calculator. A computer process of designing the adder base circuit recursively expands the functions, and optimization of death, fanout and distribution of negations is performed.

Optimization of adder based circuit architecture

A circuit embodied in an integrated circuit is characterized by an architecture having a minimal depth defined by a recursive expansion of output functions h_n&equals;OR(h_k, AND(v_k, h_&lcub;n&minus;k&rcub;)) and v_n&equals;AND(v_k, v&lcub;n&minus;k&rcub;), where k&equals;F_l and n&minus;k&equals;F_&lcub;l&minus;1&rcub;, satisfies F_l<n&equals;F_&lcub;l&plus;1&rcub;, &lcub;F_l&rcub; is a Fibonacci series and n is the number of bits of an input to the circuit. In one form, the circuit is a comparator having output functions h_n and v_n that depend from input functions U&lsqb;i&rsqb;&equals;AND(NOT(A&lsqb;i&rsqb;), B&lsqb;i&rsqb;) and V&lsqb;i&rsqb;&equals;OR(NOT(A&lsqb;i&rsqb;), B&lsqb;i&rsqb;), where A&lsqb;i&rsqb; and B&lsqb;i&rsqb; are inputs to the comparator, and functions h_n, v_n defined as h_n&equals;h_n(U&lsqb; &rsqb;, U&lsqb; &rsqb;, V&lsqb; &rsqb;, . . . , U&lsqb;n&minus;1&rsqb;, V&lsqb;n&minus;1&rsqb;)&equals;OR(U&lsqb;n&minus;1&rsqb;, AND(V&lsqb;n&minus;1&rsqb;, U&lsqb;n&minus;2&rsqb;), . . . , AND(V&lsqb;n&minus;1&rsqb;, . . . , V&lsqb; &rsqb;, U&lsqb; &rsqb;)), and v_n&equals;v_n(V&lsqb; &rsqb;, . . . , V&lsqb;n&minus; &rsqb;)&equals;AND(V&lsqb; &rsqb;, . . ., V&lsqb;n&minus;1&rsqb;). In one form, the comparator includes an LEQ input that identifies strict or non-strict inequality comparison by the comparator. The depth is further minimized by a distribution of negations of elements forming the circuit. A computer process is described to carry out the design, including mapping 2-input elements from a cell library of 3-input elements.

Growing community of inventors

Moscow, Russia

Sergej B Gashkov