Espresso sezgisel mantık sadeleştiricisi

Espresso mantık sadeleştiricisi, dijital mantık kapısı devrelerinin karmaşıklığını etkili bir şekilde azaltmak için sezgisel ve özel algoritmalar kullanan bir bilgisayar programıdır. Espresso, IBM'den Robert K. Brayton tarafından geliştirilmiştir. Richard L. Rudell daha sonra 1986'da "PLA Sentezi için Çok Değerlikli Mantık Minimizasyonu" başlığı altında Espresso-MV varyantını yayınladı. Espresso birçok türevine ilham vermiştir.

Giriş

Elektronik cihazlar, birleşimleri gerekli görevleri yerine getiren çok sayıda dijital devre bloğundan oluşur. Üretim maliyetlerini en aza indirmek veya bir cihazın performansını en üst düzeye çıkarmak için mantık fonksiyonlarının mantık kapısı devreleri biçiminde, gerekenden daha çok mantık kapısı kullanılmadan verimli bir şekilde gerçeklenmesi gerekir.

Dijital mantık devreleri tasarlama

Tüm dijital sistemler iki temel fonksiyondan oluşur: bilgi depolayan bellek elemanları ve bu bilgiyi dönüştüren kombinasyonel devreler. Sayıcılar gibi durum makineleri, bellek elemanlarının ve kombinasyonel mantık devrelerinin bir kombinasyonudur. Bellek elemanları standart mantık devreleri olduğundan sınırlı sayıda alternatif devre arasından seçilirler; bu yüzden dijital fonksiyonların tasarımı kombinasyonel kapı devrelerinin tasarlanması ve birbirine bağlanması ile ilgilidir.

Genel olarak, yüksek seviyeli soyutlamadan mantık devrelerinin somutlaştırılması, mantık sentezi olarak adlandırılır ve elle gerçekleştirilebilir ancak genellikle bilgisayar tarafından bazı biçimsel usuller uygulanır. Bu maddede, kombinasyonel mantık devreleri için tasarım yöntemleri kısaca özetlenmiştir.

Bir dijital mantık devresinin tasarımı için başlangıç noktası, sistemin bir bütün olarak analizinden elde edilecek ve mantık devresinin bir parçası olacak istenilen işlevselliktir. Tanım, bazı algoritmik formlarla veya mantık denklemleriyle ifade edilebilir, bunların yanı sıra bir tablo şeklinde de özetlenebilir. Aşağıdaki örnek, ondalık hane değerleri için ikili kodu, ekranın ilgili bölümlerinin yanmasını sağlayan sinyallere dönüştüren 7 segmentli bir ekran sürücüsüne ait böyle bir tablonun bir bölümünü göstermektedir.

  Rakam  Kod        Bölümler
                   A B C D E F G
    0    0000      1 1 1 1 1 1 0          -A-
    1    0001      0 1 1 0 0 0 0         |   |
    2    0010      1 1 0 1 1 0 1         F   B
    3    0011      1 1 1 1 0 0 1         |   |
    4    0100      0 1 1 0 0 1 1          -G-
    5    0101      1 0 1 1 0 1 1         |   |
    6    0110      1 0 1 1 1 1 1         E   C
    7    0111      1 1 1 0 0 0 0         |   |
    8    1000      1 1 1 1 1 1 1          -D-
    9    1001      1 1 1 1 0 1 1

Gerçekleme süreci, ayrı terimleri daha az değişken içeren daha büyük terimlerle birleştirerek fonksiyon tablosunu basitleştirmek için aşağıda tarif edilecek bir mantıksal minimizasyon aşaması ile başlar.

Daha sonra, minimize edilmiş sonuç bir çarpanlara ayırma prosedürü ile daha küçük parçalara bölünebilir ve sonunda hedef teknolojinin mevcut temel mantık hücreleri üzerine eşleştirilir. Bu işleme genel olarak mantıksal optimizasyon denir.

Klasik minimizasyon yöntemleri

Klasik Karnaugh haritalarını kullanarak Boole işlevlerini elle sadeleştirmek zahmetli, sıkıcı ve hataya meyilli bir süreçtir. Altıdan fazla giriş değişkeni için uygun değildir ve yalnızca dört değişkene kadar pratiktir, çoklu çıkış işlevleri için çarpım terimi paylaşımının gerçekleştirilmesi ise daha da zordur. Dahası, bu yöntem bir bilgisayar programı şeklinde otomatikleştirilmeye müsait değildir. Bununla birlikte modern mantık fonksiyonları genellikle bu kadar az sayıda değişkenle sınırlandırılmadığından ve maliyet ile hata yapma riski, mantık fonksiyonlarının elle gerçeklenmesinde engelleyici olduğundan, bilgisayar kullanımı vazgeçilmez hale gelmiştir.

Popüler hale gelen ilk alternatif yöntem, Willard Quine ve Edward McCluskey tarafından geliştirilen tablo metoduydu. Bir dizi mantık fonksiyonu için doğruluk tablosundan başlayarak, fonksiyonların aktif olduğu veya fonksiyon değerinin alakasız olduğu (farketmediği) mintermleri birleştirerek bir dizi asal implikant oluşturulur. Son olarak, çıktı fonksiyonlarının gerçekleştirilebileceği en küçük asal anlam kümesini bulmak için sistematik bir prosedür izlenir.

Bu Quine-McCluskey algoritması bir bilgisayar programında uygulanmaya çok uygun olmasına rağmen, sonuç işleme süresi ve bellek kullanımı açısından hala verimli olmaktan uzaktır. İşleve bir değişken eklemek, hem işlem süresini hem de bellek kullanımını kabaca ikiye katlayacaktır, çünkü doğruluk tablosu uzunluğu değişken sayısıyla katlanarak artar. Bir kombinasyonel fonksiyon bloğunun çıktı fonksiyonlarının sayısı arttırıldığında da benzer bir problem ortaya çıkar. Sonuç olarak Quine – McCluskey yöntemi yalnızca sınırlı sayıda girdi değişkeni ve çıktı işlevi olan işlevler için pratiktir.

Espresso algoritması

Kaliforniya Üniversitesi, Berkeley'de Brayton ve diğerleri tarafından geliştirilen Espresso algoritmasında bu konuya farklı bir yaklaşım izlenmiştir. Bir mantık fonksiyonunu mintermlere genişletmek yerine, program, ürün terimlerini ON-, DC- ve OFF- kapaklarında yinelemeli olarak temsil eden "küpleri" manipüle eder. Minimizasyon sonucunun global minimum olacağı garanti edilmese de, pratikte buna çok yakın bir şekilde yaklaşılırken, çözüm her zaman fazlalık içermez. Diğer yöntemlerle karşılaştırıldığında, bu yöntem esasen daha verimlidir, bellek kullanımını ve hesaplama süresini birkaç büyüklük derecesinde azaltır. Adı, anında bir fincan taze kahve yapma şeklini yansıtır. Bir kombinasyonel fonksiyon bloğunun değişken sayısı, çıktı fonksiyonları ve çarpım terimlerinde neredeyse hiç kısıtlama yoktur. Genel olarak, örneğin, onlarca çıktı fonksiyonuna sahip onlarca değişken kolayca ele alınır.

Espresso için girdi, istenen işlevselliğin bir fonksiyon tablosudur; sonuç ise seçilen seçeneklere bağlı olarak işlevin AÇIK veya KAPALI olduğunu açıklayan simge durumuna küçültülmüş bir tablodur. Öntanımlı olarak, çarpım terimleri birkaç çıkış işlevi tarafından mümkün olduğunca paylaşılacaktır, ancak programdan çıkış işlevlerinin her birini ayrı ayrı ele alması istenebilir. Bu, bir PLA (Programlanabilir Mantık Dizisi) veya bir PAL (Programlanabilir Mantık Dizisi) gibi iki seviyeli mantık dizilerinde verimli uygulamaya olanak tanır.

Espresso algoritması o kadar başarılı olduğunu kanıtladı ki, hemen hemen her türlü çağdaş mantık sentez aracına standart bir mantık işlevi sadeleştirme adımı olarak dahil edildi. Çok seviyeli mantıkta bir fonksiyon gerçeklemek için minimizasyon sonucu çarpanlara ayırma yoluyla optimize edilir ve ister alanda programlanabilir kapı dizisi (FPGA), ister uygulamaya özel entegre devre (ASIC) olsun, hedef teknolojideki mevcut temel mantık hücrelerine eşlenir.

Yazılım

Espresso

Orijinal Espresso programı Kaliforniya Üniversitesi, Berkeley web sitesinde C kaynak kodu olarak mevcuttur. Son sürümü 1988 tarihli 2.3 sürümüdür. Modern POSIX sistemleri için Espresso'nun güncellenmiş bir sürümü olan Espresso-ab ve eqntott (eşitlikten doğruluk tablosuna dönüştürücü) programı, Debian paketi (.deb) biçiminde ve C kaynak kodu olarak mevcuttur. Son sürüm 2008 tarihli 9.0 sürümüdür.

Logic Friday

Logic Friday, Espresso'ya ve Berkeley Octtools paketindeki bir başka modül olan misII'ye grafik arabirim sağlayan ücretsiz bir Windows programıdır. Logic Friday ile kullanıcılar, bir mantık fonksiyonunu doğruluk tablosu, denklem veya kapı diyagramı olarak girebilir, fonksiyonu sadeleştirebilir ve ardından da sonuçları diğer iki gösterimde görüntüleyebilir. Son sürümü 2012 tarihli 1.1.4 sürümüdür.

Minilog

Minilog, Espresso algoritmasından yararlanarak mantık minimizasyonu sağlayan ücretsiz bir Windows programıdır. 40'a kadar giriş ve çıkışa sahip kombinasyonel fonksiyon bloğu veya 256 duruma kadar senkronize durum makinesi için iki seviyeli bir kapı gerçeklemesi üretebilir. Publicad eğitim tasarım paketinin bir parçasıdır.

Konuyla ilgili yayınlar

• Logic Synthesis for VLSI Design. Electronics Research Laboratory, College of Engineering, University of California, Berkeley, USA. April 1989.  (Espresso-EXACT)
• Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken [Functional design of digital circuits - Methods and CAD techniques]. Springer-Lehrbuch (Almanca). Springer-Verlag. May 1993. ss. 136-137, 140-141. ISBN 9-783540-56788-2. 3-540-56788-7.