ПТЦА - Прикладная теория цифровых автоматов (стр. 15 из 20)
8. Для каждого кода из множества Dg находим кодовое расстояние до кода
.K2 = 000 K3 = 001
d(100, 000) = 1 d(100, 001) = 2
d(010, 000) = 1 d(010, 001) = 2
d(011, 000) = 2 d(011, 001) = 1
d(101, 000) = 2 d(100, 001) = 1
9. Находим значение функции w для каждого кода из множества Dg.
10. Из множества Dg выбираем код Kg, у которого получилось минимальное значение w в п.9. Выбираем код для состояния a1К1 =100.
 |
11. Из матрицы
вычеркиваем строки, в которых оба элемента уже закодированы, в результате чего получим новую матрицу . Если в новой матрице 
не осталось ни одной строки, то кодирование закончено. В противном случае возвращаемся к п.5. В нашем случае имеем: | i | j | p(i,j) | ||
| 3 | 4 | 2 | ||
| 3 | 5 | 2 | ||
| M’ | = | 1 | 5 | 1 |
| 2 | 4 | 1 | ||
| 2 | 5 | 1 |
К2 = 000
= {010}K3 = 001
= {011, 101}
K2 = 000 K3 = 001
d(010, 000) = 1 d(010, 001) = 2
d(011, 000) = 2 d(011, 001) = 1
d(101, 000) = 2 d(101, 001) = 1
Выбираем К4 = 101.
 |
К1 = 100
= {110}K2 = 000
= {010}К3 = 001
= {011} 
К1 = 100 K2 = 000 K3 = 001
d(110, 100) = 1 d(110, 000) = 2 d(110, 001) = 3
d(010, 100) = 2 d(010, 000) = 1 d(010, 001) = 2
d(011, 100) = 3 d(011, 000) = 2 d(011, 001) = 1
Выбираем К5 = 011.
 |
Т.к. все состояния автомата закодированы, то работа алгоритма заканчивается. Общее количество переключений триггеров:
Минимально возможное количество переключений (если бы состояния были закодированы соседним кодированием)
Коэффициент эффективности кодирования:
Рассмотренный алгоритм кодирования является машино-ориентированным, существуют программы, реализующие этот алгоритм.
Необходимо отметить в заключении, что использование алгоритма кодирования для D-триггеров или эвристического алгоритма для других типов триггеров обеспечивает наиболее простую с точки зрения реализации схему, но при этом возможны гонки. Для радикального устранения последних используют аппаратные методы – триггеры с двойной памятью: триггеры, управляемые фронтом и т.д..
Управляющие и операторные автоматы.
Принцип микропрограммного управления.
ЭВМ перерабатывает информацию, выполняя над ней какие-то операции. Для выполнения операций над информацией используются операционные устройства – процессоры, каналы ввода-вывода, устройства управления внешними устройствами и т.д. Функцией операционного устройства является выполнение заданного множества операций F={f1,...,fG} над входными словами D={d1,...,dH} c целью вычисления слов R={r1,...,rQ}, которые представляют результаты операций R=fg(D), где g=1,2,...,G.
Функциональная и структурная организация операционных устройств базируется на принципе микропрограммного управления, который состоит в следующем:
1. Любая операция fg(g=1,...,G), реализуемая устройством, рассматривается как сложное действие, которое разделяется на последовательность элементарных действий над словами информации. Эти элементарные действия называются микрооперациями.
2. Для управления порядком следования микроопераций используются логические условия, которые в зависимости от значений слов, преобразуемых микрооперациями, принимают значения "ложь" или "истина" (1 или 0).
3. Процесс выполнения операций в устройстве описывается в форме алгоритма, который представляется в терминах микроопераций и логических условий и называется микропрограммой. Микропрограмма определяет порядок проверки значений логических условий и следования микроопераций, необходимый для получения требуемых результатов.
4. Микропрограмма используется как форма представления функции устройства, на основе которой определяется структура и порядок функционирования устройства во времени.
Т.о. из принципа микропрограммного управления следует, что структура и порядок функционирования операционных устройств предопределяется алгоритмом выполнения операции F={f1,...,fG}.
К элементарным действиям над словами информации микрооперациям относятся: передача информации из одного регистра в другой, взятие обратного кода, сдвиг и т.д.
Понятие операционного и управляющих автоматов.
Как показал академик В.М. Глушков в любом устройстве обработки цифровой информации можно выделить два основных блока – операционный автомат (ОА) и управляющий автомат (УА).
 |
Операционный автомат (ОА) служит для хранения слов информации, выполнения набора микроопераций и вычисления значений логических условий, т.е. операционный автомат является структурой, организованной для выполнения действий над информацией. Микрооперации, выполняемые ОА, задаются множеством управляющих сигналов Y={y1,....,yM}, с каждым из которых отождествляется определенная микрооперация.
Значения логических условий, вычисляемые в операционном автомате, отображаются множеством осведомительных сигналов X={x1,...,xL}, каждый из которых отождествляется с определенным логическим условием.
Управляющий автомат (УА) генерирует последовательность управляющих сигналов, предписанную микропрограммой и соответствующую значениям логическим условий. Иначе говоря, управляющий автомат задает порядок выполнения действий в ОА, вытекающий из алгоритма выполнения операций. Наименование операции, которую необходимо выполнить в устройстве, определяется кодом g операции, поступающим в УА извне. По отношению к УА сигналы g1,...,gh, посредством которых кодируется наименование операции и осведомительные сигналы x1,...,xL, формируемые в операционном автомате, играют одинаковую роль: они влияют на порядок выработки управляющих сигналов Y. Поэтому сигналы g1,...,gh и x1,...,xL относятся к одному классу – к классу осведомительных сигналов, поступающих на вход УА.
Т.о. любое операционное устройство – процессор, канал ввода-вывода и т.д. – является композицией операционного и управляющего автоматов. Операционный автомат, реализуя действия над словами информации, является исполнительной частью устройства, работой которого управляет управляющий автомат, генерирующий необходимые последовательности управляющих сигналов.
Операционный и управляющий автоматы могут быть определены своими функциями – перечнем выполняемых ими действий.
Функция ОА определяется следующей совокупностью сведений:
1) множеством входных слов D={d1,...,dH}, вводимых в автомат в качестве операндов;