A weighted technique for programmable logic devices minimization

ABSTRACT

A new technique for minimizing the width of Programmable Logic Devices(PLDs) is introduced in this paper. The algorithm starts with the result of the technique introduced by Das Banerji and Chatopadhyay[4]. The solution obtained in [4] will be refined to form the temporary solution, or what is called a preliminary solution. The problem of the preliminary solution is that it does not guarantee a minimum solution, because it does not use redundant classes, that are sometimes essential to the final minimum solution. The weighting technique is introduced, which gives a weight to each micro-order. The micro-orders with the largest weights are stripped from each class to form a stripped set. The stripped micro-orders are tested for compatibility, and a new set of compatibility classes are formed based on the stripped micro-orders, and the reserved classes only. Some factors are taken into consideration before the stripped micro-orders become the final collection. The procedure loops again with the new set of compatibility classes as long as reduction is obtained.

REFERENCES

• 1: "Tutorial, Microprogramming and Firmware Engineering," Milutinvec Veljko, 1989.
• 2: Michael Andrews, Principles Firmware Engineering, W. H. Freeman & Co., New York, NY, 1980
• 3: "Microprogram Optimization," Agenvala, IEEE transactions, act. 1976 vol C-25 pp. 962-973.
• 4: "On control memory minimization in microprogrammed digital computers," S.R. Das, D.K Banerji, A Chattopadhyay. IEEE transactions, Comput., vol. C-22, pp. 845-848, sept 1973.
• 5: "Clause-column table approach for generating all the prime implicants of switching functions," SXDas, N.S.Khabra, IEEE Trans. comput., vol. C-21, pp1239-1246, Nov. 1972.
• 6: "On the minimization of read only memories in microprogrammed digital computers," AGrasselli and U.Montanari, IEEE Transactions, Comput., pp. 1111-1114, Nov. 1970.
• 7: "An approach for simplifying switching functions by utilizing the cover table representation," IEEE Transactions, Comput. vol. c-20, pp.355-359,197l.
• 8: "An introduction to the theory of switching circuits," New York:McGraw-Hill, 1965.
• 9: "A method for determination of all the forms of Boolean functions," A Mukhopadhyay, Proc. inst. Elec. Eng., Mono. 487E, Dec 1961.
• 10: "An algorithm for minimizing Bead Only Memories for machine control," S.J.Schwartz, 1968 IEEE 10th Annual symp. on Switching and Automata theory, pp. 28-33.
• 11: "Some covering problems in switching theory," A Grasselli F.Luccio, in Network and switching theory, G.Biorci, ED. New York Academic press, 1968, pp. 536-557.
• 12: "A method for minimizing the number of internal states in incompletely specified sequential networks," A Grasselli and F. Luccio, IEE Trans. Electron. comput., vol.EC- 14,pp. 350-359, June 1965.
• 13: "A note on the derivation of maximal compatibility classes," A Grasselli, calcolo, vol. 3, pp. 165-176,1966.
• 14: "Minimizing the number of states in incompletely specified sequential switching functions," M.C. Paul, S.H. Unger, IBE Trans. Electronics Computers, vol. ECS,pp. 365-367, September 1959.
• 15: "Minimization of boolean functions," Bell Sys.Tech. J.,vol.35 ,pp. 1417-1444., 1956.
• 16: "Computer system architecture,"M. Morris Mano, Printice Hall, 1982.
• 17: "Infinitesimal calculus," Bartholomew Price, vol. 1, 1930.
• 18: "On minimizing the width of Programmable Logic Devices," H. Azzam, thesis, Tufts University, May 1990.