|
- |
||||
28 |
17 |
- |
|||
30 |
17 |
- |
|||
|
|
|
|||
G22(5) |
0 |
1 |
|||
33 |
1 |
- |
|||
35 |
1 |
- |
|||
37 |
1 |
- |
|||
39 |
1 |
- |
|||
41 |
1 |
- |
|||
|
|
|
|||
G23(5) |
0 |
1 |
|||
11 |
25 |
24 |
|||
|
|
|
|||
G24(5) |
0 |
1 |
|||
21 |
26 |
- |
|||
|
|
|
|||
G25(5) |
0 |
1 |
|
||
20 |
21 |
- |
|
||
|
|
|
|
||
G26(5) |
0 |
1 |
|
||
25 |
22 |
- |
|
||
29 |
22 |
- |
|
||
31 |
22 |
- |
|
||
При построении нормализованного автомата переход d = (Ci, zj) считается неопределённым, если для всех состояний этого класса не определены переходы в другое состояние. Если хотя бы для одного состояния класса переход определён, то в клетку таблицы нормализованного автомата заносится индекс класса, в который переходит цифровой автомат из этого состояния. Таким образом, доопределяются неопределённые переходы исходного автомата. Нормализованный автомат является эквивалентным любому из минимизированных автоматов и не имеет, как минимум, ни одной пары совместимых состояний. В соответствии с изложенной методикой минимизации получаются либо полностью определённые, либо частичные нормализованные автоматы.
У полностью определённых автоматов класс конечной совместимости не пересекаются, поэтому нормализованный автомат является единственным и процесс минимизации этим заканчивается. В случае получения частичного автомата классы i-совместимости пересекаются. Это приводит к тому, что нормализованный автомат может описываться конечным количеством вариантов таблиц или графов. В случае частичных автоматов часто отказываются от достижения абсолютной минимизации и ограничиваются нахождением нормализованного автомата и его эвристическим доопределением.
Таблица состояний и выходов нормализованного автомата
Вх/сост
G1
G2
G3
G4
G5
G6
G7
G8
G9
G10
G11
G12
G13
0
G2/0
G3/0
G4/0
G5/0
G10/0
G11/0
G12/0
G13/0
G16/0
G17/0
G18/0
G20/0
G21/0
1
G6/0
G7/0
G8/0
G9/0
-/-
G14/0
-/-
G15/0
-/-
-/-
-/-
G19/0
-/-
Вх/сост
G14
G15
G16
G17
G18
G19
G20
G21
G23
G24
G25
G26
0
G23/0
G26/0
G22/0
G1/0
G13/0
G16/0
G10/1
G17/1
G25/1
G26/1
G21/0
G22/1
1
-/-
-/-
-/-
-/-
G15/1
-/-
-/-
-/-
G24/1
-/-
-/-
-/-
В результате всех преобразований мы получили нормализованный минимизированный автомат, по которому построим граф автомата Мили:
Структурный синтез цифрового автомата
Структурный синтез цифрового автомата - это кодирование его входных и переменных и состояний автомата и получение функции возбуждения и функций выходов триггера.
Задачей этапа структурного синтеза является построение принципиальной схемы автомата из элементарных автоматов заданного типа. Элементарные автоматы подразделяются на два больших класса:
- элементарные автоматы памяти (запоминающие элементы);
- элементарные автоматы без памяти (элементарные комбинационные схемы или логические элементы).
Задача синтеза цифрового автомата имеет решение в том случае, если система элементарных автоматов является структурно полной.
Всякая система элементарных автоматов, содержащая элементарный автомат, Мура (триггер) и какую-нибудь функционально полную систему логических элементов является структурно полной системой.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
При использовании материалов активная ссылка на источник обязательна.