Kanonik normal form - Canonical normal form

Gelen Boole cebri , bir Boole fonksiyonu içine konabilir kanonik ayırıcı normal form ( CDNF ) ya da Minterm kanonik formu ve çift kanonik birleşik normal form ( CCNF ) ya da maxterm kanonik formu . Diğer kanonik formlar , asal imaların veya Blake kanonik formunun (ve onun ikili) tam toplamını ve cebirsel normal formu (Zhegalkin veya Reed-Muller olarak da adlandırılır) içerir.

Mintermler çünkü onlar ürünlerini denir mantıksal AND değişkenlerin bir dizi ve maxtermler çünkü onlar meblağlar denir mantıksal OR değişkenler kümesinin. Bu kavramlar, De Morgan yasalarında ifade edildiği gibi tamamlayıcı-simetri ilişkileri nedeniyle ikilidir .

Herhangi bir Boole fonksiyonunun iki kanonik formu, "mintermlerin toplamı" ve "maksimumların çarpımı"dır. " Ürün Toplamı " ( SoP veya SOP ) terimi, mintermlerin bir ayrımı (OR) olan kanonik form için yaygın olarak kullanılmaktadır. Onun De Morgan ikili bir "dir Tutarlarla Ürün (" POS veya POS maxtermlerin bir bağlaç (AND) 'dir kanonik form için). Bu formlar genelde Boole formüllerinin özelde sayısal devrelerin optimizasyonunda büyük önem taşıyan bu fonksiyonların sadeleştirilmesi için faydalı olabilir.

Mintermler

Değişkenlerin bir boole işlevi için , değişkenlerin her birinin bir kez göründüğü (tamamlanmış veya tamamlanmamış biçiminde) bir çarpım terimine minterm denir . Bu nedenle, bir minterm , yalnızca tümleyen operatörünü ve bağlaç operatörünü kullanan n değişkenin mantıksal bir ifadesidir . ${\görüntüleme stili n}$${\displaystyle {x_{1},\dots ,x_{n}}}$${\görüntüleme stili n}$

Örneğin , ve üç değişkenli bir Boole fonksiyonu için 8 minterme 3 örnektir , ve . Bunların sonuncusunun alışılmış okuması a AND b AND NOT-c şeklindedir . ${\görüntüleme stili abc}$${\ Displaystyle ab'c}$${\görüntüleme stili abc'}$${\görüntüleme stili bir}$${\görüntüleme stili b}$${\görüntüleme stili c}$

Minterm ifadesindeki bir değişken, doğrudan veya tümleyen biçiminde olabileceğinden, değişken başına iki seçenek olabileceğinden , n değişkenli 2 ⁿ minterm vardır.

Mintermleri indeksleme

Mintermler genellikle değişkenlerin standart bir sırayla, genellikle alfabetik olarak yazıldığı, değişkenlerin tamamlama modelinin ikili kodlamasıyla numaralandırılır. Bu kural, doğrudan forma ( ) 1 değerini ve tümleyen forma ( ) 0 değerini atar ; minterm o zaman . Örneğin minterm 110 ₂  = 6 ₁₀ olarak numaralandırılır ve . ${\displaystyle x_{i}}$${\displaystyle x'_{i}}$${\displaystyle \sum \limits _{i=1}^{n}2^{i}\operatöradı {değer} (x_{i})}$${\görüntüleme stili abc'}$${\displaystyle m_{6}}$

fonksiyonel eşdeğerlik

Belirli bir minterm n , girdi değişkenlerinin yalnızca bir kombinasyonu için gerçek bir değer (yani 1) verir. Örneğin, minterm 5, a b ' c , yalnızca a ve c'nin her ikisi de doğru ve b yanlış olduğunda doğrudur - a = 1, b = 0, c = 1'in 1 ile sonuçlandığı giriş düzenlemesi .

Mantıksal bir fonksiyonun doğruluk tablosu verildiğinde, fonksiyonu "ürünlerin toplamı" olarak yazmak mümkündür. Bu, ayrık normal formun özel bir şeklidir . Örneğin, bir toplayıcı devresinin bir bitlik konumunun mantığının aritmetik toplamı bit u için doğruluk tablosu verilirse , toplamalardan ve taşımadan x ve y'nin bir fonksiyonu olarak , ci :

ci	x	y	u(ci,x,y)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

1 bir çıkış var satırlar 2., 3., 5., ve 8. kullandığını işaret biz yazabiliriz u minterme toplamı olarak ve . Bunu doğrulamak istersek: üç değişkenin 8 kombinasyonunun tümü için değerlendirilen tabloyla eşleşecektir. ${\displaystyle m_{1},m_{2},m_{4},}$${\ Displaystyle m_{7}}$${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y' )+(ci,x',y')+(ci,x,y)}$

maksimum terimler

Bir için Boole fonksiyonunun bir n değişkenleri , her hangi bir miktar terimi , n değişkenleri göründüğünü kez (ya da tamamlanabilir ya da uncomplemented biçimde) bir adlandırılır maxterm . Bu nedenle, bir maksimum terim , yalnızca tümleyen operatörünü ve ayırma operatörünü kullanan n değişkenin mantıksal bir ifadesidir . Maxterms, minterm fikrinin ikilidir (yani, her bakımdan tamamlayıcı bir simetri sergiler). AND'leri ve tamamlayıcıları kullanmak yerine, OR'leri ve tamamlayıcıları kullanır ve benzer şekilde devam ederiz. ${\displaystyle {x_{1},\dots ,x_{n}}}$

Örneğin, aşağıdakiler üç değişkenli sekiz maksimum terimden ikisidir:

a + b ′ + c

bir ′ + b + c

Yine maksimum n değişkenli 2 ⁿ maksimum terim vardır , çünkü maksimum terim ifadesindeki bir değişken, doğrudan veya tümleyen biçiminde de olabilir - değişken başına iki seçenek.

Maksimum terimleri indeksleme

Her maxterm'e, mintermler için kullanılan zıt geleneksel ikili kodlamaya dayalı bir indeks atanır. maxterm kuralı, 0 değerini doğrudan forma ve 1 değerini tümleyen forma atar . Örneğin, maxterm için indeks 6 atamak (110) gibi bu maxterm belirtmek M ₆ . Benzer bir şekilde M ₀ , bu üç değişkenin olduğu (000) ve M ₇ olan (111). ${\görüntüleme stili (x_{i})}$${\görüntüleme stili (x'_{i})}$${\ Displaystyle a'+b'+c}$${\ Displaystyle a+b+c}$${\ Displaystyle a'+b'+c'}$

fonksiyonel eşdeğerlik

Maksterm n'nin , girdi değişkenlerinin yalnızca bir kombinasyonu için yanlış bir değer (yani, 0) verdiği açıktır . Örneğin, maxterm 5, a ′ + b + c ′, yalnızca a ve c'nin her ikisi de doğru ve b yanlış olduğunda yanlıştır - a = 1, b = 0, c = 1'in 0 ile sonuçlandığı giriş düzenlemesi.

Birine mantıksal bir fonksiyonun doğruluk tablosu verilirse , fonksiyonu "toplamların çarpımı" olarak yazmak mümkündür. Bu, konjonktif normal formun özel bir şeklidir . Örneğin, bir taşıma-out bit doğruluk tablosunu verilen ortak bir işlevi olarak, bir toplayıcı devre bir bit konumunun mantık x ve y addends gelen ve içinde taşıma ci :

ci	x	y	co(ci,x,y)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

0 çıktısı olan satırların 1., 2., 3. ve 5. satırlar olduğunu göz önünde bulundurarak, co yazabiliriz , maxterms ve . Bunu doğrulamak istersek: ${\displaystyle M_{0},M_{1},M_{2}}$${\ Displaystyle M_{4}}$

${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}=(ci+x+y)(ci+x+y')(ci+x'+ y)(ci'+x+y)}$

üç değişkenin tüm 8 kombinasyonu için değerlendirilen tabloyla eşleşecektir.

ikileme

Bir minterm'in tamamlayıcısı, ilgili maxterm'dir. Bu, de Morgan yasasını kullanarak kolayca doğrulanabilir . Örneğin: ${\displaystyle M_{5}=a'+b+c'=(ab'c)'=m_{5}'}$

Kanonik olmayan PoS ve SoP formları

Kurallı minterm formunun eşdeğer bir SoP formuna basitleştirilebileceği sıklıkla görülen bir durumdur. Bu basitleştirilmiş form, yine de, ürün terimlerinin toplamından oluşacaktır. Bununla birlikte, basitleştirilmiş biçimde, daha az sayıda ürün terimi ve/veya daha az değişken içeren ürün terimi olabilir. Örneğin, aşağıdaki 3 değişkenli işlev:

bir	b	c	f(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

kanonik minterm gösterimine sahiptir: , ancak eşdeğer basitleştirilmiş bir forma sahiptir: . Bu önemsiz örnekte, , ancak basitleştirilmiş formda hem daha az ürün terimi hem de terimin daha az değişkeni olduğu açıktır . ${\displaystyle f=a'bc+abc}$${\görüntüleme stili f=bc}$${\displaystyle bc=a'bc+abc}$

Bir fonksiyonun en basitleştirilmiş SoP gösterimi, minimal SoP formu olarak adlandırılır .

Benzer bir şekilde, bir kanonik maxterm formu, basitleştirilmiş bir PoS formuna sahip olabilir.

Bu örnek, normal cebirsel yöntemler [ ] uygulanarak basitleştirilmiş olsa da , daha az belirgin durumlarda, dört değişkene kadar bir fonksiyonun minimum PoS/SoP formunu bulmak için uygun bir yöntem Karnaugh haritası kullanmaktır . ${\displaystyle f=(a'+a)bc}$

Minimal PoS ve SoP formları, boole fonksiyonlarının optimal uygulamalarını bulmak ve mantık devrelerini en aza indirmek için önemlidir.

Uygulama örneği

Yukarıdaki mintermler ve maxtermler için örnek doğruluk tabloları, ikili sayıların eklenmesinde tek bir bit konumu için kanonik formu oluşturmak için yeterlidir, ancak kapı envanteriniz VE ve VEYA içermedikçe dijital mantığı tasarlamak için yeterli değildir. Performansın bir sorun olduğu durumlarda (Apollo Guidance Computer'da olduğu gibi), transistör mantığında bulunan tamamlayıcı eylem nedeniyle mevcut parçaların NAND ve NOR olması daha olasıdır. Değerleri gerilim durumları, bir yakın yere ve DC besleme gerilimi V yakın olarak tanımlanır _cc +5 VDC, örneğin. Daha yüksek voltaj 1 "doğru" değer olarak tanımlanırsa, NOR geçidi mümkün olan en basit kullanışlı mantıksal öğedir.

Spesifik olarak, 3 girişli bir NOR geçidi, emitörlerinin tümü topraklanmış, kollektörleri birbirine bağlanmış ve bir yük empedansı aracılığıyla V _cc'ye bağlı 3 bipolar bağlantı transistöründen oluşabilir . Her baz bir giriş sinyaline bağlıdır ve ortak toplayıcı nokta çıkış sinyalini sunar. Tabanına 1 (yüksek voltaj) olan herhangi bir giriş, transistörünün emitörünü kollektörüne kısa devre yaparak akımın yük empedansından akmasına neden olur, bu da kollektör voltajını (çıkış) toprağa çok yaklaştırır. Bu sonuç diğer girdilerden bağımsızdır. Yalnızca 3 giriş sinyalinin tümü 0 (düşük voltaj) olduğunda, 3 transistörün tümünün emitör-toplayıcı empedansları çok yüksek kalır. Daha sonra, çok az akar, ve kolektör noktada yük empedansı getirdiği V çok yakın bir yüksek voltaj ile voltaj bölücü etkisi _cc .

Bu kapı devrelerinin tamamlayıcı özelliği, bir işlevi kurallı biçimde uygulamaya çalışırken bir dezavantaj gibi görünebilir, ancak telafi edici bir avantajı vardır: yalnızca bir girişi olan böyle bir kapı, dijital mantıkta sıklıkla gerekli olan tamamlayıcı işlevi uygular.

Bu örnek, Apollo parça envanterini varsaymaktadır: yalnızca 3 girişli NOR kapıları, ancak tartışma, 4 girişli NOR kapılarının da mevcut olduğu varsayılarak basitleştirilmiştir (Apollo'da bunlar, 3-girişli NOR çiftlerinden birleştirilmiştir).

NOR kapılarının kanonik ve kanonik olmayan sonuçları

8 NOR kapısından oluşan bir set, eğer girişleri, ci, x ve y 3 giriş değişkeninin doğrudan ve tümleyen biçimlerinin kombinasyonlarıysa , her zaman minimum terimler üretir, asla maksimum terimler üretmez, yani tüm kombinasyonları işlemek için gereken 8 kapıdan 3 giriş değişkeninden yalnızca birinin çıkış değeri 1'dir. Bunun nedeni, adına rağmen bir NOR geçidinin (De Morgan yasasını kullanarak) giriş sinyallerinin tümleyenlerinin AND'si olarak daha iyi görülebilmesidir.

Bunun bir sorun olmamasının nedeni, minterm ve maxterm'in ikiliğidir, yani her maxterm, benzer indeksli minterm'in tümleyenidir ve bunun tersi de geçerlidir.

Yukarıdaki minterm örneğinde yazmıştık, ancak bunu 4 girişli bir NOR geçidi ile gerçekleştirmek için, toplamların zıt maksimum terimler olduğu toplamların çarpımı (PoS) olarak yeniden ifade etmemiz gerekiyor. Yani, ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}}$

${\displaystyle u(ci,x,y)=\mathrm {AND} (M_{0},M_{3},M_{5},M_{6})=\mathrm {NOR} (m_{0}, m_{3},m_{5},m_{6}).}$

doğruluk tabloları

ci x y M 0 M 3 M 5 E 6 VE u(ci,x,y) 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1

ci x y m, 0 m 3 m 5 m 6 NOR u(ci,x,y) 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1

Yukarıdaki maxterm örneğinde yazmıştık ama bunu 4 girişli bir NOR geçidi ile gerçekleştirmek için aynı mintermlerin NOR'larına eşitliğine dikkat etmemiz gerekiyor. Yani, ${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}$

${\displaystyle co(ci,x,y)=\mathrm {AND} (M_{0},M_{1},M_{2},M_{4})=\mathrm {NOR} (m_{0}, m_{1},m_{2},m_{4}).}$

doğruluk tabloları

ci x y M 0 M 1 M 2 E 4 VE co(ci,x,y) 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

ci x y m, 0 m 1 m 2 m 4 NOR co(ci,x,y) 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1

Kanonik formlara ek olarak dikkate alınan tasarım değiş tokuşları

Bir toplayıcı aşaması tasarlama işinin artık tamamlandığı varsayılabilir, ancak girdi değişkenlerinin 3'ünün de hem doğrudan hem de tamamlayıcı formlarında görünmesi gerektiği gerçeğini ele almadık. Bu açıdan x ve y ekleriyle ilgili herhangi bir zorluk yoktur , çünkü bunlar toplama boyunca statiktirler ve bu nedenle normal olarak hem doğrudan hem de tamamlayıcı çıktılara sahip olan mandal devrelerinde tutulurlar. (NOR kapılarından yapılmış en basit mandal devresi, bir flip-flop yapmak için çapraz bağlanmış bir çift kapıdır: her birinin çıkışı, diğerinin girişlerinden biri olarak bağlanır.) Ayrıca tamamlayıcı formu oluşturmaya gerek yoktur. toplamının u . Bununla birlikte, bir bit konumunun yürütülmesi, hem doğrudan hem de tamamlayıcı formlarda bir sonraki bit konumuna taşıma olarak geçirilmelidir. Bunu yapmanın en basit yolu geçmektir co 1-girişi NOR kapıdan ve çıkış etiketlemek işbirliği ', ama bu sola dalgalanan sağdan taşıdığı yavaşlatan, olası en kötü yerde bir kapı gecikme eklemek istiyorum. Kanonik formu yapı ek 4 girişli NOR kapısı co (zıt minterme üzerinden ' ko ) bu sorunu çözer.

${\displaystyle co'(ci,x,y)=\mathrm {AND} (M_{3},M_{5},M_{6},M_{7})=\mathrm {NOR} (m_{3} ,m_{5},m_{6},m_{7}).}$

doğruluk tabloları

ci x y M 3 M 5 E 6 M 7 VE co'(ci,x,y) 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0

ci x y m 3 m 5 m 6 m, 7 NOR co'(ci,x,y) 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0

Bu şekilde tam hızı korumanın bedeli (daha büyük bir kapı kullanmak zorunda olmanın yanı sıra) beklenmedik bir maliyet içerir. co öğesini tamamlamak için bu 1 girişli geçidi kullansaydık, minterm için bir kullanım olmazdı ve onu oluşturan geçit ortadan kaldırılabilirdi. Yine de, yine de iyi bir ticaret. ${\ Displaystyle m_{7}}$

Artık NOR kapılarını belirtilen fonksiyonlara çevirerek bu fonksiyonları tam olarak SoP ve PoS kanonik formlarına göre uygulayabilirdik. Bir NOR kapısı, çıkışı 1 girişli bir NOR kapısından geçirilerek OR kapısına dönüştürülür; ve girişlerinin her biri 1 girişli NOR kapısından geçirilerek AND kapısına dönüştürülür. Bununla birlikte, bu yaklaşım sadece kullanılan kapı sayısını artırmakla kalmaz, aynı zamanda sinyalleri işleyen kapı gecikmelerinin sayısını iki katına çıkararak işlem hızını yarıya indirir. Sonuç olarak, performans ne zaman hayati önem taşırsa, kanonik formların ötesine geçmek ve geliştirilmemiş NOR kapılarının işi yapmasını sağlamak için Boole cebrini yapmak faydalı olacaktır.

Yukarıdan aşağıya ve aşağıdan yukarıya tasarım

Şimdi minterm/maxterm araçlarının, çıktıların her biri için sadece 2 geçit gecikmesine mal olan bir miktar Boole cebirinin eklenmesiyle kanonik biçimde bir toplayıcı aşaması tasarlamak için nasıl kullanılabileceğini gördük. Bu işlev için dijital devre tasarlamanın "yukarıdan aşağıya" yolu budur, ancak en iyi yol bu mu? Tartışma, "en hızlı"yı "en iyi" olarak belirlemeye odaklandı ve artırılmış kanonik form bu kriteri kusursuz bir şekilde karşılıyor, ancak bazen başka faktörler baskın geliyor. Tasarımcının birincil amacı, kapı sayısını en aza indirmek ve/veya büyük yayılımlar bozulmuş bir güç kaynağına veya diğer çevresel faktörlere karşı direnci azalttığından, diğer kapılara giden sinyallerin çıkışlarını en aza indirmek olabilir. Böyle bir durumda, bir tasarımcı bir temel olarak kanonik form tasarımını geliştirebilir, ardından aşağıdan yukarıya bir geliştirme deneyebilir ve son olarak sonuçları karşılaştırabilir.

Aşağıdan yukarıya geliştirme, u = ci XOR ( x XOR y ) olduğunu fark etmeyi içerir ; burada XOR, münhasır VEYA [girişlerden biri doğru olduğunda ancak ikisi de doğru olmadığında doğru] anlamına gelir ve co = ci x + xy + y ci anlamına gelir . Böyle bir geliştirme, toplamda on iki NOR kapısı alır: 5 kapı gecikmesinde u üretmek için altı adet 2 girişli kapı ve iki adet 1 girişli kapı , artı 2 kapı gecikmesinde co ' üretmek için üç adet 2 girişli kapı ve bir adet 3 girişli kapı . Kanonik temel , 2 kapı gecikmesinde u, co ve co ' üretmek için sekiz adet 3 girişli NOR kapısı artı üç adet 4 girişli NOR kapısı aldı. Devre envanteri aslında 4 girişli NOR kapıları içeriyorsa, yukarıdan aşağıya kurallı tasarım hem kapı sayısı hem de hız açısından kazanan gibi görünür. Ancak (uygun varsayımımızın aksine) devreler aslında her 4 girişli NOR işlevi için ikisi gerekli olan 3 girişli NOR kapıları ise, kanonik tasarım aşağıdan yukarıya yaklaşım için 12'ye kıyasla 14 kapı alır, ancak yine de toplam basamağı u'yu önemli ölçüde daha hızlı üretir . Yayılma karşılaştırması şu şekilde tablolaştırılmıştır:

Değişkenler	Yukarıdan aşağıya	Altüst
x	4	1
x'	4	3
y	4	1
sen	4	3
ci	4	1
hayır	4	3
M veya m	4@1,4@2	Yok
x XOR y	Yok	2
Çeşitli	Yok	5@1
Maks.	4	3

Aşağıdan yukarıya gelişme tanımı söz co bir çıkış değil gibi " co . Bu tasarım, yürütmenin doğrudan biçimine asla ihtiyaç duymaz mı? Evet ve hayır. Her aşamada, hesaplanması co 'Yalnızca bağlıdır ci ' x 've y ', burada araçlarının bit pozisyonları boyunca sadece hızlı olarak hiç geliştirme olmadan standart tasarımda taşıma yayılma dalgaların co . Hesaplanması u gerektirir, ci dan yapılacak ci bir 1-girişi ile 'NOR, yavaş ama herhangi bir kelime uzunluğu için tasarımı sadece (en soldaki toplamı haneli geliştirilen) bir kez bu cezayı öder. Bunun nedeni, bu hesaplamaların, bir sonraki bit konumunun toplam bitinin ne zaman hesaplanabileceğini etkilemeden, her biri kendi küçük ardışık düzenine denk gelecek şekilde çakışmasıdır. Ve, emin olmak için, en soldaki bit konumundan co ', muhtemelen, toplamanın taşıp taşmadığını belirleyen mantığın bir parçası olarak tamamlanmalıdır. Ancak 3 girişli NOR geçitleri kullanıldığında, aşağıdan yukarıya tasarım, önemsiz olmayan bir kelime uzunluğuna paralel ekleme yapmak kadar hızlıdır, geçit sayısını azaltır ve daha düşük yayma kullanır ... bu yüzden geçit sayımı kazanırsa kazanır ve/veya fanout çok önemlidir!

Tüm bu ifadelerin doğru olduğu aşağıdan yukarıya tasarımın tam devresini, ilgilenen okuyucu için bir alıştırma olarak, bir cebirsel formülle daha destekleyerek bırakacağız: u = ci ( x XOR y ) + ci ′( x XOR y )′]′. Taşıma yayılımını toplam oluşumundan bu şekilde ayırmak, ileriye dönük bir toplayıcının performansını bir dalgalı taşıma toplayıcısının performansına göre yükselten şeydir .

Dijital devre tasarımında uygulama

Boole cebrinin bir uygulaması, bir amacı kapı sayısını en aza indirmek ve diğeri de yerleşme süresini en aza indirmek olan dijital devre tasarımıdır.

İki değişkenin on altı olası işlevi vardır, ancak dijital mantık donanımında en basit kapı devreleri bunlardan yalnızca dördünü uygular: bağlaç (VE), ayrılma (VEYA dahil) ve bunların ilgili tamamlayıcıları (NAND ve NOR).

Çoğu kapı devresi 2'den fazla giriş değişkenini kabul eder; örneğin, 1960'larda tümleşik devrelerin uygulanmasına öncülük eden uzay kaynaklı Apollo Rehberlik Bilgisayarı , çıkışı yalnızca 3 girişin tümü yanlış olduğunda doğru olan, yalnızca bir tür kapıyla, 3 girişli bir NOR ile inşa edildi.

Ayrıca bakınız

• Boole cebri konularının listesi

Referanslar

daha fazla okuma

• Bender, Edward A.; Williamson, S. Gill (2005). Ayrık Matematikte Kısa Bir Kurs . Mineola, NY: Dover Publications, Inc. ISBN 0-486-43946-1.
  Yazarlar, herhangi bir Boolean (mantık) fonksiyonunun ya ayrık ya da birleştirici normal biçimde ifade edilebileceğine dair bir kanıt gösterirler (bkz. sayfa 5-6); ispat basitçe 2 ^N satırlık N Boole değişkeninin tümünü oluşturarak ilerler ve her satırın ("minterm" veya "maxterm") benzersiz bir Boolean ifadesine sahip olduğunu gösterir. N değişkenlerinin herhangi bir Boole işlevi , minterm veya maxterm mantıksal 1'ler ("true") olan satırların bir bileşiminden türetilebilir.
• McCluskey, EJ (1965). Anahtarlama Devreleri Teorisine Giriş . NY: McGraw-Hill Kitap Şirketi. s. 78. LCCN  65-17394 . Kanonik ifadeler tanımlanır ve tanımlanır
• Tepe, Fredrick J.; Peterson, Gerald R. (1974). Anahtarlama Teorisine ve Mantıksal Tasarıma Giriş (2. baskı). NY: John Wiley & Sons. s. 101. ISBN'si 0-471-39882-9. Fonksiyonların minterm ve maxterm tanımları

Dış bağlantılar

• Boole, George (1848). Çeviren Wilkins, David R. "Mantığın Hesabı" . Cambridge ve Dublin Matematik Dergisi . III : 183–198.