Quine-McCluskey algoritması: Revizyonlar arasındaki fark
| [kontrol edilmemiş revizyon] | [kontrol edilmemiş revizyon] |
İçerik silindi İçerik eklendi
k ekleme |
ekleme |
||
134. satır:
|1
|}
Bu tablodan çarpımların kanonik toplamını, fonksiyonun bir olarak değerlendirdiği mintermleri (önemsiz terimleri dışarıda bırakarak) toplayarak kolayca oluşturabilirsiniz:
f<sub>A,B,C,D</sub>=A'BCD' + ABC'D' + AB'CD' + ABC'D + ABC'D' + ABCD
Bu nedenle, optimize etmek için, bir olarak değerlendirilen tüm mintermler önce bir minterm tablosuna yerleştirilir. Önemsiz terimler de bu tabloya eklenir (adlar parantez içindedir), böylece mintermlerle birleştirilebilirler:
{| class="wikitable"
|+
!1lerin
sayısı
!Minterm
!İkili Gösterimi
|-
| rowspan="2" |1
|m4
|0100
|-
|m8
|1000
|-
| rowspan="3" |2
|(m9)
|1001
|-
|m10
|1010
|-
|m12
|1100
|-
| rowspan="2" |3
|m11
|1011
|-
|(m14)
|1110
|-
|4
|m15
|1111
|}
Bu noktada mintermleri diğer mintermlerle birleştirmeye başlanabilir. İki terim yalnızca tek bir basamakla farklılık gösteriyorsa, o basamak, basamağın önemli olmadığını belirten bir tire ile değiştirilebilir. Artık birleştirilemeyecek terimler bir yıldız (*) ile işaretlenmiştir. Örneğin 1000 ve 1001, 100- verecek şekilde birleştirilebilir; bu, her iki mintermin de ilk hanenin 1 ve sonraki ikisinin 0 olduğunu ima ettiğini gösterir.
{| class="wikitable"
|+
!1lerin
sayısı
!Minterm
!0-küp
! colspan="2" |2. Boyut etkileri
|-
| rowspan="4" |1
|m4
|0100
|m(4,12)
| -100*
|-
|m8
|1000
|m(8,9)
|100-
|-
| -
| -
|m(8,10)
|10-0
|-
| -
| -
|m(8,12)
|1-00
|-
| rowspan="4" |2
|m9
|1001
|m(9,11)
|10-1
|-
|m10
|1010
|m(10,11)
|101-
|-
| -
| -
|m(10,14)
|1-10
|-
|m12
|1100
|m(12,14)
|11-0
|-
| rowspan="2" |3
|m11
|1011
|m(11,15)
|1-11
|-
|m14
|1110
|m(14,15)
|111-
|-
|4
|m15
|1111
| -
|
|}
Boyut 2'den Boyut 4'e geçerken - üçüncü bir bit değeri olarak ele alın. Örneğin, -110 ve -100, -1-0'ı vermek üzere birleştirilebilir, ca -110 ve -11-'in -11- vermesi gibi, ancak -110 ve 011- olamaz çünkü -110, 1110 tarafından ima edilirken 011- değil. (Püf Noktası: İlkini eşleştirin.)
{| class="wikitable"
|+
!1lerin
sayısı
!minterm
!0-küp
! colspan="2" |2. Boyut etkileri
! colspan="2" |4. Boyut etkileri
|-
| rowspan="4" |1
|m4
|0100
|m(4,12)
| -100*
|m(8,9,10,11)
|10--*
|-
|m8
|1000
|m(8,9)
|100-
|m(8,10,12,14)
|1--0*
|-
| -
| -
|m(8,10)
|10-0
| colspan="2" | -
|-
| -
| -
|m(8,12)
|1-00
| colspan="2" | -
|-
| rowspan="4" |2
|m9
|1001
|m(9,11)
|10-1
|m(10,11,14,15)
|1-1-*
|-
|m10
|1010
|m(10,11)
|101-
| colspan="2" | -
|-
| -
| -
|m(10,14)
|1-10
| colspan="2" | -
|-
|m12
|1100
|m(12,14)
|11-0
| colspan="2" | -
|-
| rowspan="2" |3
|m11
|1011
|m(11,15)
|1-11
| colspan="2" | -
|-
|m14
|1110
|m(14,15)
|111-
| colspan="2" | -
|-
|4
|m15
|1111
|
| -
| colspan="2" | -
|}
Not: Genel olarak bu işleme daha fazla terim birleştirilemeyecek duruma gelene kadar devam edilmelidir. Bu örnekteki terimlerin hiçbiri daha fazla birleştirilemez.
=== 2. Adım ===
Terimlerin hiçbiri bundan daha fazla birleştirilemez, bu nedenle bu noktada bir asal dolaylı tablo oluşturuyoruz. Kenar boyunca, henüz oluşturulmuş olan asal çıkarımlar gider ve üst kısım boyunca daha önce belirtilen mintermler gider. Önemsiz terimler en üste yerleştirilmemiştir - gerekli girdiler olmadıkları için bu bölümden çıkarılmıştır.
:{| class="wikitable" {{ts|ac}}
|-
! || 4 || 8 || 10 || 11 || 12 || 15 || ⇒ || A || B || C || D
|-
| {{ts|al}} | m(4,12)* || {{Ya|✓}} || || || || {{Ya|✓}} || || ⇒ || - || 1 || 0 || 0
|-
| {{ts|al}} | m(8,9,10,11) || || {{Ya|✓}} || {{Ya|✓}} || {{Ya|✓}} || || || ⇒ || 1 || 0 || - || -
|-
| {{ts|al}} | m(8,10,12,14) || || {{Ya|✓}} || {{Ya|✓}} || || {{Ya|✓}} || || ⇒ || 1 || - || - || 0
|-
| {{ts|al}} | m(10,11,14,15)* || || || {{Ya|✓}} || {{Ya|✓}} || || {{Ya|✓}} || ⇒ || 1 || - || 1 || -
|} Temel asal çıkarımları bulmak için en üst sıra boyunca ilerliyoruz. Sadece bir "✓" içeren sütunları aramamız gerekiyor. Bir sütunda yalnızca bir "✓" varsa, bu, minterm'in yalnızca bir asal dolaylı tarafından kapsanabileceği anlamına gelir. Örneğin: ilk sütunda minterm 4 ile yalnızca bir "✓" vardır.
:Bu, m(4,12)'nin gerekli olduğu anlamına gelir. Bu yüzden yanına bir yıldız koyuyoruz. Minterm 15'te de sadece bir "✓" vardır, dolayısıyla m(10,11,14,15) de esastır. Artık bir "✓" içeren tüm sütunlar kapsanmıştır.
:İkinci asal implikant üçüncü ve dördüncü tarafından "kapsanabilir" ve üçüncü asal implikeant ikinci ve birinci tarafından "kapsanabilir" bu nedenle hiçbiri zorunlu değildir. Bir asal implikant gerekliyse, beklendiği gibi, onu minimize edilmiş boole denklemine dahil etmek gerekir. Bazı durumlarda, temel asal çıkarımlar tüm mintermleri kapsamaz, bu durumda çizelge indirgemesi için ek prosedürler kullanılabilir. En basit "ek prosedür" deneme yanılma yöntemidir, ancak daha sistematik bir yol [[Petrick'in yöntemi|Petrick'in yöntemidir]]. Mevcut örnekte, temel asal çıkarımlar tüm mintermleri işlemez, bu nedenle, bu durumda, temel çıkarımlar, bir denklem elde etmek için iki temel olmayanlardan biriyle birleştirilebilir:
:f<sub>A,B,C,D</sub>=BC'D + AB' + AC
:veya
:f<sub>A,B,C,D</sub>=BC'D + AD' + AC
:Bu son denklemlerin her ikisi de orijinal denkleme işlevsel olarak eşdeğerdir:
:''f''<sub>A,B,C,D</sub> = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.
:
== Kaynakça ==
| |||