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

Ö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

1. Başçiftçi F., Anahtarlama Fonksiyonları İçin
2. Yerel Basitleştirme Algoritmaları, Doktora
3. Tezi, Selçuk Üniversitesi, Fen Bilimleri
4. Enstitüsü, 2006.
5. Brayton R.K., Hachtel G.D., McMullen C.,
6. Sangiovanni-Vincentelli A.L., Logic
7. Minimization Algorithms For VLSI Synthesis,
8. ISBN 0-89838-164-9, Hardbound, Kluwer

9. Academic Publishers, 1984.
10. Sasao T., Butler J.T., Worst and Best Irredundant
11. Sum-of–Product Expressions, IEEE
12. Transactions on Computers, Vol. 50(9), pp.
13. -947, 2001.
14. Coudert O., Two-Level Logic Minimization: an
15. Overview. Integration, The VLSI Journal, 17-2,
16. pp. 97-140, October 1994.
17. Dagenais M.R., Agarwal V.K., Rumin N.C.,
18. McBOOLE: A New Procedure for Exact Logic
19. Minimization, IEEE Transactions On
20. Computer Aided Design, Vol. CAD-5, No:1,
21. Jaunary 1986.
22. Brown, D.W., A State-Machine Synthesizer –
23. SMS. Proc. 18th Design Automation
24. Conference, pp.301-304, Nashville, June 1981.
25. Svoboda A., White D.E, Advanced Logical
26. Circuit Design Techniques, New York: Garland
27. Pres, 1979.
28. Hong S.J., Cain R.G. and Ostapko D.L., MINI: A
29. Heuristic Approach For Logic Minimization,
30. IBM J. of Res. and Dev., Vol.18, pp.443-458,
31. September 1974.
32. Dietmeyer D.L., Logic Design of Digital
33. Systems, MA:Ally and Bacon, Boston 1979.
34. Nguyen K., Perkowski M., Goldstein N.,
35. Palmini-Fats Boolean Minimizer for Personal
36. Computers, Proc. Design Automation Conf., pp.
37. -621, Aug, 1987.
38. Mishchenco A., Sasao T., Large-Scale SOP
39. minimization Using Decomposition and
40. Functional Properties, DAC, pp149-154, June 2-6
41. -
42. Miller R.E., Switching Theory, Vol. 1
43. Combination Circuits, New York; John Wiley
44. and sons, 1965.
45. Mano M. M., Digital Design, Prentice-Hall
46. International Editions, 1984.
47. Perkins S.R., Rhyne T., An Algorithm for
48. Identifying and Selecting The Prime Implicants of a Multiple-Output Boolean Function, IEEE
49. Transactions On Computer Aided Design, Vol.
50. , No:11, November 1988.
51. Gurunath B., Biswas N.N., An Algorithm for
52. Multiple Output Minimization, IEEE
53. Transactions On Computer Aided Design, Vol.
54. , No:9, September 1989.
55. Bartlett K.A., Brayton R.K., Hachtel G.D.,
56. Jacoby R.M., Morrison C.R., Rudell R.L.,
57. Sangiovanni-Vincentelli A., Wang A.R.,
58. Multilevel Logic Minimization Using Implicit
59. Don’t Cares, IEEE Transactions On Computer
60. Aided Design, Vol. 7, No:6, June 1988.
61. Allahverdi N.M., Kahramanlı Ş.Ş., Erciyeş K., A
62. Fault Tolerant Routing Algorithm Based On Cube
63. Algebra For Hypercube Systems, Journal of
64. Systems Architecture, 46, pages 201-205, 2000.
65. Bernasconi A., Ciriani V., Luccio F., Pagli L.,
66. Fast Three-Level Logic Minimization Based on
67. Autoymmetry,
68. http://citeseer.nj.nec.com/cachedpage/462188/1
69. -
70. Beckert B., Iiahnle R., Escalada-Imaz G., Simp.
71. of Many-Valued Logic Formulas Using Anti-
72. Links, http://citeseer.nj.nec.com/cachedpage
73. /221052/1, 1997.
74. Kahramanlı Ş., Başçiftçi F., Boolean Functions
75. Simplification Algorithm Of O(n) Complexity,
76. Mathematical & Computational Applications,
77. Volume 8 Numbers 1-3, pages:271-278.
78. ISSN:1300-686X, 2003.
79. Kahramanlı Ş., Özcan M., Lojik Tasarımın
80. Temelleri ve Uygulamaları, Atlas Yayın
81. Dağıtım, İstanbul 2002.
82. Roth J.P., Algebric Topological Methods for the
83. Synthesis of Switching Systems in n-variables,
84. The Instute for Advanced Study, Princeton,
85. New Jersey, 1956.
86. Nadjafov E.M., Kahramanov S.S., On the
87. Synthesis of Multiple Output Switching Scheme,
88. Scientific Notes of Azerbaijan Institute of
89. Petrolium and Chemistry, Baku, Azaerbaijan,
90. Vol. IX, No 3 65-69, 1973.
91. Kahramanlı S.S., Allahverdi N.M., Compact
92. Method of Minimization of Boolean Functions
93. with Multiple Variables. Proc. Inter. Symp.
94. Application of Computers, Selçuk University,
95. Konya, Turkey, 433-440, 1993.