ANAHTARLAMA FONKSİYONLARI İÇİN YENİ YAKIN MİNİMUM SADELEŞTİRME ALGORİTMASI

Yıl 2010, Cilt: 25 Sayı: 1, 0 - , 15.02.2013

Fatih Başçiftçi Şirzat Kahramanlı

Öz

Anahtarlama fonksiyonlarının sadeleştirilmesi tasarımcılara daha kısa zaman süresinde, daha sade lojik devrelertasarlama imkanı sağlamaktadır. Sadeleştirilmiş olan bir fonksiyon daha az güç tüketimi, daha az hacim ve dahaaz 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ımterimlerin 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 örtmeprensibine 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 toplamifadelerinin 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.

Anahtar Kelimeler

Anahtarlama fonksiyonu, sadeleştirme, asal çarpım terim, Off-küme tabanlı minimumlaştırma, doğrudan örtme prensibi.

Kaynakça

• Başçiftçi F., Anahtarlama Fonksiyonları İçin
• Yerel Basitleştirme Algoritmaları, Doktora
• Tezi, Selçuk Üniversitesi, Fen Bilimleri
• Enstitüsü, 2006.
• 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.
• Sasao T., Butler J.T., Worst and Best Irredundant
• Sum-of–Product Expressions, IEEE
• Transactions on Computers, Vol. 50(9), pp.
• -947, 2001.
• Coudert O., Two-Level Logic Minimization: an
• Overview. Integration, The VLSI Journal, 17-2,
• pp. 97-140, October 1994.
• 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.
• Brown, D.W., A State-Machine Synthesizer –
• SMS. Proc. 18th Design Automation
• Conference, pp.301-304, Nashville, June 1981.
• Svoboda A., White D.E, Advanced Logical
• Circuit Design Techniques, New York: Garland
• Pres, 1979.
• 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.
• Dietmeyer D.L., Logic Design of Digital
• Systems, MA:Ally and Bacon, Boston 1979.
• Nguyen K., Perkowski M., Goldstein N.,
• Palmini-Fats Boolean Minimizer for Personal
• Computers, Proc. Design Automation Conf., pp.
• -621, Aug, 1987.
• Mishchenco A., Sasao T., Large-Scale SOP
• minimization Using Decomposition and
• Functional Properties, DAC, pp149-154, June 2-6
• -
• Miller R.E., Switching Theory, Vol. 1
• Combination Circuits, New York; John Wiley
• and sons, 1965.
• Mano M. M., Digital Design, Prentice-Hall
• International Editions, 1984.
• 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.
• , No:11, November 1988.
• Gurunath B., Biswas N.N., An Algorithm for
• Multiple Output Minimization, IEEE
• Transactions On Computer Aided Design, Vol.
• , No:9, September 1989.
• 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.
• 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.
• Bernasconi A., Ciriani V., Luccio F., Pagli L.,
• Fast Three-Level Logic Minimization Based on
• Autoymmetry,
• http://citeseer.nj.nec.com/cachedpage/462188/1
• -
• 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.
• 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.
• Kahramanlı Ş., Özcan M., Lojik Tasarımın
• Temelleri ve Uygulamaları, Atlas Yayın
• Dağıtım, İstanbul 2002.
• Roth J.P., Algebric Topological Methods for the
• Synthesis of Switching Systems in n-variables,
• The Instute for Advanced Study, Princeton,
• New Jersey, 1956.
• 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.
• 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.