IJICA

Minimize Logic Synthesis FPGA – Extraction And Substitution Problems

---

---

Abstract

The objective of multi-level logic synthesis of FPGA is to find the “best” multi-level structure, where “best” in this case means an equivalent presentation that is optimal with respect to various parameters such as size, speed or power consumption... Five basic operations are used in order to reach this goal: decomposition, extraction, factoring, substitution and collapsing. In this paper we propose a novel application of Walsh spectral transformation to the evaluation of Boolean function correlation. In particular, we present an algorithm with approach to solve the problems of extraction and substitution based on the use of Walsh spectral presentation. The method, operating in the transform domain, has appeared to be more advantageous than traditional approaches, using operations in the Boolean domain, concerning both memory occupation and execution time on some classes of functions.

Recommended Citation

[1] Goldenberg LM,Matyushkin BD,Polak MN

"Digital Signal Processing." Moscow: Radio

Svyaz, 1985.

[2] Murgai R., Nishizaki Y., Shenoy N., Brayton R.

K., Sangiovanni-Vlncentelli A. "Logic synthesis

algorithms for programmable gate arrays" In

Proc. of the CM/IEEE Design Autom. Conf.

(Orlando, FL, June), 620-625. 1990.

[3] F. Mailhot and G. De Micheli, “Algorithms for

technology mapping based on binary decision

diagrams and on Boolean operations”, IEEE

Trans. On CAD, vol. 12, no. 3, pp. 599-620, May

1993.

[4] Darrlnger J., Joyner W., Berman L, Trellyan L

"Logic Synthesis through local transformation"

IBM J. Res. Develop., v.25, №4, pp.272-280,

July 1981.

[5] Muzio J.C. "Composite Spectra and the Analysis

of Switching Circuits" IEEE Trans. On Comput

Vol. C-29, № 8 Aug. 1980.

[6] Karpovsky M.G. "Finite Ortogonal Series In the

Design of Digital Devices" NY.:Wiley, 1976.

[7] Zeidman B. “All about FPGAs / Logic Design

Line”. March 21. 2006.

[8] Karp R. M. "Functional decomposition and

switching circuit design" J. SIAM 11,2, 291-335.

1963.

[9] Preparata F.P. "VLSI algorithms and

architecture" In M.P. Chytil, V. Koubek

(ed.;Lecture notes In Computer Science 176),

Springer-Verlag, 1984.

[10] Pratt W., Kane J., Andrews H.C., "Hadamard

transform image coding" Proc. IEEE Vol. 57, №

1 pp. 58-68, 1969.

[11] Trimberg S."Reprogrammable Gate Arrays and

Applications" Proc. of the IEEE,V.81,N 7, July

1993.

[12] Karp R.M. "deducibility among combinatorial

problem on Complexity of Computer

computation" ,1972.

[13] Gary M. D. Johnson, "Computers and

Intractability problem" ed. AA Friedman - Mir,

1982.

[14] M. Dertouzos, "Threshold Logic," Trans. from

English. edited by VI Warsaw, Moscow,

Mir.ZhT. – pp.342.

[15] Sapozhenko AA, "On the complexity of

disjunctive normal forms obtained by the gradient

algorithm," Discrete Analysis. Vyp.21,

Novosibirsk, 1972 - pp.62-71.

[16] Proc. IEEE, “Custom Integrated Circuits

conference”, Boston, Mass., May 13-16, 1990

(N.Y.).1990, pp. 27.5.1-27.5.4.

[17] M. J. Ciesielski. S. Yang, and M. A. Perkowski,

“Minimization of multiple-valued logic based on

graph coloring,” Tech. Rep. TR-CSE- 90.13,

Dep. Elect. Comp. Eng., Univ. of Massachusetts.

Amherst, Sept. 1990.