Anahtarlama fonksiyonları için yeni yakın minimum sadeleştirme algoritması

Anahtarlama fonksiyonlarının sadeleştirilmesi tasarımcılara daha kısa zaman süresinde, daha sade lojik devreler tasarlama imkanı sağlamaktadır. Sadeleştirilmiş olan bir fonksiyon daha az güç tüketimi, daha az hacim ve daha az maliyet gerektirir. Bu konu ile ilgili olarak geliştirilen yöntemlerin çoğu iki ana adımda gerçekleştirilir. Birinci adımda, asal çarpım terimlerinin tümü belirlenir. İkinci adımda fonksiyonu sadeleşmiş olarak örtecek, esas asal çarpım terimler kümesi belirlenir. Anahtarlama fonksiyonlarını sadeleştirecek algoritmaların tümü O(2n) karmaşıklığına sahiptirler. Araştırmalar göstermiştir ki n’in çok yüksek değerlerinde esas asal çarpım terimlerin tam kümesini belirleme yöntemi pratik olarak gerçekleştirilemez duruma gelmektedir. Bu yüzden bu çalışmada, asal çarpım terimlerin belli kıstaslara cevap verecek alt kümeleri oluşturularak, doğrudan örtme prensibine dayanan yakın minimum sadeleştirme algoritması geliştirilmiştir. Geliştirilen algoritma çeşitli problemler üzerinde test edilmiş ve dünyaca örnek olarak kabul edilen ESPRESSO algoritması ile karşılaştırılmıştır. Karşılaştırma kıstasları olarak algoritmaların; çözüm sonucunda buldukları çarpım terimlerinin toplam ifadelerinin sayısı, çözüme ulaşma süreleri ve çözüme ulaşırken kullandıkları bellek kapasitesi alınmıştır. Karşılaştırma sonuçlarına göre geliştirilen algoritmanın başarılı sonuçlar verdiği görülmüştür.

A new near minimum simplification algorithm for switching functions

The minimization of Switching functions allows designers to make use of fewer components, thus reducing the cost of particular system. Simplified as a function requires less power consumption, less volume and less cost. Most of minimization techniques work on a two–step principle, the first step identifies all of the prime implicants and the second step selects the subset of prime implicants that covers the function(s) being minimized. All procedures for Boolean networks into prime and irredundant form have O(2n) complexity. Prime Implicants identification step can be computational impractical as n increases. Therfore, in this study, subsets of prime implicants that can prove direct cover principle which based on definite criterions use for mimimization method. The method has been tested on several different kinds of problems and results of which were compared with ESPRESSO Comparison of algorithms as benchmarks; solution as a result they find that their total number of product terms, the solution times and reach a solution when they reach the memory capacity is taken. According to the results of the comparison developed algorithm gives successful results.

PDF

___

1. Başçiftçi F., Anahtarlama Fonksiyonları İçin Yerel Basitleştirme Algoritmaları, Doktora Tezi, Selçuk Üniversitesi, Fen Bilimleri Enstitüsü, 2006.
2. Brayton R.K., Hachtel G.D., McMullen C., Sangiovanni-Vincentelli A.L., Logic Minimization Algorithms For VLSI Synthesis, ISBN 0-89838-164-9, Hardbound, Kluwer Academic Publishers, 1984.
3. Sasao T., Butler J.T., Worst and Best Irredundant Sum-of–Product Expressions, IEEE Transactions on Computers, Vol. 50(9), pp. 935-947, 2001.
4. Coudert O., Two-Level Logic Minimization: an Overview. Integration, The VLSI Journal, 17-2, pp. 97-140, October 1994.
5. Dagenais M.R., Agarwal V.K., Rumin N.C., McBOOLE: A New Procedure for Exact Logic Minimization, IEEE Transactions On Computer Aided Design, Vol. CAD-5, No:1, Jaunary 1986.
6. Brown, D.W., A State-Machine Synthesizer – SMS. Proc. 18th Design Automation Conference, pp.301-304, Nashville, June 1981.
7. Svoboda A., White D.E, Advanced Logical Circuit Design Techniques, New York: Garland Pres, 1979.
8. Hong S.J., Cain R.G. and Ostapko D.L., MINI: A Heuristic Approach For Logic Minimization, IBM J. of Res. and Dev., Vol.18, pp.443-458, September 1974.
9. Dietmeyer D.L., Logic Design of Digital Systems, MA:Ally and Bacon, Boston 1979.
10. Nguyen K., Perkowski M., Goldstein N., Palmini-Fats Boolean Minimizer for Personal Computers, Proc. Design Automation Conf., pp. 615-621, Aug, 1987.
11. Mishchenco A., Sasao T., Large-Scale SOP minimization Using Decomposition and Functional Properties, DAC, pp149-154, June 2-6 2003.
12. Miller R.E., Switching Theory, Vol. 1 Combination Circuits, New York; John Wiley and sons, 1965.
13. Mano M. M., Digital Design, Prentice-Hall International Editions, 1984.
14. Perkins S.R., Rhyne T., An Algorithm for Identifying and Selecting The Prime Implicants of a Multiple-Output Boolean Function, IEEE Transactions On Computer Aided Design, Vol. 7, No:11, November 1988.
15. Gurunath B., Biswas N.N., An Algorithm for Multiple Output Minimization, IEEE Transactions On Computer Aided Design, Vol. 8, No:9, September 1989.
16. Bartlett K.A., Brayton R.K., Hachtel G.D., Jacoby R.M., Morrison C.R., Rudell R.L., Sangiovanni-Vincentelli A., Wang A.R., Multilevel Logic Minimization Using Implicit Don’t Cares, IEEE Transactions On Computer Aided Design, Vol. 7, No:6, June 1988.
17. Allahverdi N.M., Kahramanlı Ş.Ş., Erciyeş K., A Fault Tolerant Routing Algorithm Based On Cube Algebra For Hypercube Systems, Journal of Systems Architecture, 46, pages 201-205, 2000.
18. Bernasconi A., Ciriani V., Luccio F., Pagli L., Fast Three-Level Logic Minimization Based on Autoymmetry, http://citeseer.nj.nec.com/cachedpage/462188/1 2001.
19. Beckert B., Iiahnle R., Escalada-Imaz G., Simp. of Many-Valued Logic Formulas Using Anti- Links, http://citeseer.nj.nec.com/cachedpage /221052/1, 1997.
20. Kahramanlı Ş., Başçiftçi F., Boolean Functions Simplification Algorithm Of O(n) Complexity, Mathematical & Computational Applications, Volume 8 Numbers 1-3, pages:271-278. ISSN:1300-686X, 2003.
21. Kahramanlı Ş., Özcan M., Lojik Tasarımın Temelleri ve Uygulamaları, Atlas Yayın Dağıtım, İstanbul 2002.
22. Roth J.P., Algebric Topological Methods for the Synthesis of Switching Systems in n-variables, The Instute for Advanced Study, Princeton, New Jersey, 1956.
23. Nadjafov E.M., Kahramanov S.S., On the Synthesis of Multiple Output Switching Scheme, Scientific Notes of Azerbaijan Institute of Petrolium and Chemistry, Baku, Azaerbaijan, Vol. IX, No 3 65-69, 1973.
24. Kahramanlı S.S., Allahverdi N.M., Compact Method of Minimization of Boolean Functions with Multiple Variables. Proc. Inter. Symp. Application of Computers, Selçuk University, Konya, Turkey, 433-440, 1993.