Математические основы теории цифровых устройств. Градусов В.Н. - 7 стр.

UptoLike

ВУЗ: 

ИГЭУ | Иваново

Составители: 

Рубрика: 

15 16
На пересечении строки и столбца ставится метка ( V ) если импли-
канта отличается от конституенты независимыми координатами с уче-
том минимизируемых функций -
y, f.
Таблица 2.4
Покрытие импликантами
Конституенты единицы
Импликанта 001
y
010
y
100
y
100
f
101
f
y f 1 — 0
V V
y f — 0 0
V V
y f 1 0 —
V
V V
y 0 — —
V V
y — — 0
V V
y — 0 —
V V
f 1 — —
V V
Отыскание минимального покрытия функции приводится с исполь-
зованием обычного алгоритма [1. C.198]. Заметим, что в ядро Квайна
не входит ни одна из импликант, так как все столбцы содержат более
одной метки.
Строки первая, вторая и последняя (табл. 2.4) могут быть сокраще-
ны, так как каждая из них полностью входит в одну из оставшихся (по
-
крывается ей). Предпоследний столбец также может, быть вычеркнут
с учётом того, что в него входит последний. В преобразованном по-
крытии (табл. 2.5), вычёркиваем предпоследний столбец и две послед-
ние строки, получая минимальное покрытие (табл. 2.6).
Таким образом, минимальное покрытие функции имеет вид:
(
)
yf
y f
abc
,
∏
=
−
−−
⎧
⎨
⎩
⎫
⎬
⎭
10
0
y
(2.17)
На основании (2.17) записывается система уравнений
yaba
fab
=∨
=
⎧
⎨
⎩
(2.18)
Таблица 2.5
Преобразованное покрытие по Квайну
Конституенты единицы
Импликанты 001
y
010
y
100
y
101
f
yf
1 0 –
V V
y
0 – –
V V
y
– – 0
V V
y
– 0 –
V V
Таблица 2.6
Минимальное покрытие по Квайну
Конституенты единицы
Импликанты 001 010 101
y y f
y f
1 0 –
V
y
0 – –
V V
Заметим, что преобразование к виду bay ∨= не целесообразно, так
как проводилась совместная минимизация.
Для сравнения рассмотрим решение данной задачи с использовани-
ем метода карт Карно (рис. 2.3). Каждый из методов имеет свои досто-
инства и недостатки. Наглядности метода карт Карно (минимизиру-
ющих карт) противостоит ограничение на число переменных. Строгая
формализация и отлаженный алгоритм в переборе вариантов в
методе
Квайна и Мак-Класки сделали его основой для машинных методов ми-
нимизации, однако ручной расчет на его базе излишне громоздок. 
   На пересечении строки и столбца ставится метка ( V ) если импли-                                                           Таблица 2.5
канта отличается от конституенты независимыми координатами с уче-                      Преобразованное покрытие по Квайну
том минимизируемых функций - y, f.
                                                     Таблица 2.4                                      Конституенты единицы
                      Покрытие импликантами
                                                                            Импликанты         001          010        100          101
                                Конституенты единицы
        Импликанта      001     010    100     100         101                                  y            y            y             f
                         y       y      y       f           f                yf     10–                                   V             V
   yf         1—0                       V       V
   yf         —00                       V       V                            y      0––        V             V
   yf         10—                       V       V           V                y      ––0                      V            V
   y          0——        V       V
                                                                             y      –0–        V                          V
   y          ——0                V      V
   y          —0—        V              V                                                                                     Таблица 2.6
    f         1——                               V           V                             Минимальное покрытие по Квайну

    Отыскание минимального покрытия функции приводится с исполь-                                            Конституенты единицы
зованием обычного алгоритма [1. C.198]. Заметим, что в ядро Квайна
не входит ни одна из импликант, так как все столбцы содержат более                Импликанты          001            010           101
одной метки.                                                                                            y             y             f
    Строки первая, вторая и последняя (табл. 2.4) могут быть сокраще-
                                                                             yf        10–                                         V
ны, так как каждая из них полностью входит в одну из оставшихся (по-
крывается ей). Предпоследний столбец также может, быть вычеркнут              y        0––             V              V
с учётом того, что в него входит последний. В преобразованном по-
крытии (табл. 2.5), вычёркиваем предпоследний столбец и две послед-     Заметим, что преобразование к виду y = a ∨ b не целесообразно, так
ние строки, получая минимальное покрытие (табл. 2.6).                   как проводилась совместная минимизация.
    Таким образом, минимальное покрытие функции имеет вид:                  Для сравнения рассмотрим решение данной задачи с использовани-
                                                                        ем метода карт Карно (рис. 2.3). Каждый из методов имеет свои досто-
              ⎧1 0 − ⎫ y f
∏ ( y , f ) = ⎨⎩0    ⎬
                 − −⎭ y
                                                            (2.17)      инства и недостатки. Наглядности метода карт Карно (минимизиру-
abc                                                                     ющих карт) противостоит ограничение на число переменных. Строгая
    На основании (2.17) записывается система уравнений                  формализация и отлаженный алгоритм в переборе вариантов в методе
⎧ y = ab ∨ a                                                            Квайна и Мак-Класки сделали его основой для машинных методов ми-
⎨                                                            (2.18)     нимизации, однако ручной расчет на его базе излишне громоздок.
⎩ f = ab


                                 15                                                                         16

Страницы