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

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.

PDF

___

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.