Сначала ответы на ваши вопросы:
Количество ячеек на каждой карте Карно соответствует количеству всех возможных входных комбинаций. Способ индексации ячеек карты должен соответствовать таблице истинности. На следующем рисунке приведены примеры различных размеров карт Карно, где визуализация соседних ячеек все еще довольно проста.
Как видите, дело в том, что две соседние ячейки отличаются только значением одной переменной, четыре соседние ячейки отличаются значениями двух переменных и так далее. Вот почему вам следует искать группы размером 2^n. Индексирование карты может выглядеть немного запутанным, но это делается для отображения всех взаимосвязей между каждой строкой в таблице истинности.
Если вы индексируете К-карту, но не знаете, какие строки для каких переменных и в каком порядке они должны идти, то проверить это можно так:
- индекс 0 = где не ни одна переменная верна
- индекс 1 = где только наименьший значащий бит является истинным (для таблицы истинности, упорядоченной abcd это будет d)
- индекс 2 = где истинен только второй младший значащий бит (для той же таблицы истинности, которая была бы c)
- индекс 4 = где истинен только третий младший значащий бит (для той же таблицы истинности, которая была бы b)
- индекс 8 = где только четвертый младший значащий бит является истинным (для той же таблицы истинности, которая была бы a)
В качестве примера: Здесь вы можете увидеть диаграмму состояний генератора последовательности 01364, реализованного в виде машины Мура. Все ребра машины помечены входным значением кнопки сброса.
Желаемое поведение машины и выходные значения, соответствующие состояниям, могут быть описаны этой таблицей переходов:
state || output (decimal) | reset || next state
-------------------------------------------------
S_0 || 0 | 0 || S_1
|| | 1 || S_0
-------------------------------------------------
S_1 || 1 | 0 || S_2
|| | 1 || S_0
-------------------------------------------------
S_2 || 3 | 0 || S_3
|| | 1 || S_0
-------------------------------------------------
S_3 || 6 | 0 || S_4
|| | 1 || S_0
-------------------------------------------------
S_4 || 4 | 0 || S_0
|| | 1 || S_0
После кодирования представления состояний в соответствии с десятичными выходными данными в двоичном виде (q_2, q_1 и q_0; d_2, d_1 и d_0), таблица переходов выглядит следующим образом:
state || q_2 | q_1 | q_0 | reset || d_2 | d_1 | d_0 || next state
-------------------------------------------------------------------
S_0 || 0 | 0 | 0 | 0 || 0 | 0 | 1 || S_1
|| | | | 1 || 0 | 0 | 0 || S_0
-------------------------------------------------------------------
S_1 || 0 | 0 | 1 | 0 || 0 | 1 | 1 || S_2
|| | | | 1 || 0 | 0 | 0 || S_0
-------------------------------------------------------------------
S_2 || 0 | 1 | 1 | 0 || 1 | 1 | 0 || S_3
|| | | | 1 || 0 | 0 | 0 || S_0
-------------------------------------------------------------------
S_3 || 1 | 1 | 0 | 0 || 1 | 0 | 0 || S_4
|| | | | 1 || 0 | 0 | 0 || S_0
-------------------------------------------------------------------
S_4 || 1 | 0 | 0 | 0 || 0 | 0 | 0 || S_0
|| | | | 1 || 0 | 0 | 0 || S_0
Полезно изучить таблицу переходов для всех возможных комбинаций входов, потому что есть несколько выходных значений «безразлично» (x) (для состояний, которых нет в последовательности), которые можно использовать для минимизации картами Карно.
index | state || q_2 | q_1 | q_0 | reset || d_2 | d_1 | d_0 || next state
---------------------------------------------------------------------------
0 | S_0 || 0 | 0 | 0 | 0 || 0 | 0 | 1 || S_1
1 | S_0 || 0 | 0 | 0 | 1 || 0 | 0 | 0 || S_0
---------------------------------------------------------------------------
2 | S_1 || 0 | 0 | 1 | 0 || 0 | 1 | 1 || S_2
3 | S_1 || 0 | 0 | 1 | 1 || 0 | 0 | 0 || S_0
---------------------------------------------------------------------------
4 | - || 0 | 1 | 0 | 0 || x | x | x || -
5 | - || 0 | 1 | 0 | 1 || 0 | 0 | 0 || S_0
---------------------------------------------------------------------------
6 | S_2 || 0 | 1 | 1 | 0 || 1 | 1 | 0 || S_3
7 | S_2 || 0 | 1 | 1 | 1 || 0 | 0 | 0 || S_0
---------------------------------------------------------------------------
8 | S_4 || 1 | 0 | 0 | 0 || 0 | 0 | 0 || S_0
9 | S_4 || 1 | 0 | 0 | 1 || 0 | 0 | 0 || S_0
---------------------------------------------------------------------------
10 | - || 1 | 0 | 1 | 0 || x | x | x || -
11 | - || 1 | 0 | 1 | 1 || 0 | 0 | 0 || S_0
---------------------------------------------------------------------------
12 | S_3 || 1 | 1 | 0 | 0 || 1 | 0 | 0 || S_4
13 | S_3 || 1 | 1 | 0 | 1 || 0 | 0 | 0 || S_0
---------------------------------------------------------------------------
14 | - || 1 | 1 | 1 | 0 || x | x | x || -
15 | - || 1 | 1 | 1 | 1 || 0 | 0 | 0 || S_0
Наконец, вы можете видеть, что функции, определяющие d_2, d_1 и d_0 (то есть двоичное кодированное состояние/выход, соответствующие числу в последовательность 01364) можно просто выделить на следующих К-картах.
f(d_2) = q_1 ⋅ ¬(reset)
f(d_1) = q_0 ⋅ ¬(reset)
f(d_0) = ¬(q_2) ⋅ ¬(q_1) ⋅ ¬(reset)
(Все изображения были созданы с использованием латекса.)
person
Kit Ostrihon
schedule
09.03.2016
