Реферат: ПТЦА - Прикладная теория цифровых автоматов
Гипероглавление:Методы анализа и синтеза комбинационных схем.
комбинационная схема
комбинационной
функциональной
Задача анализа
Задача синтеза
1.1. Канонический метод синтеза комбинационных схем.
1.2. Характеристики комбинационных схем.
Сложность схемы
Сложность (цена)
Быстродействие комбинационной схемы
1.3. Системы (серии) логических элементов и их
основные характеристики.
Серией (системой, комплексом)
питающих напряжений
1.7. Анализ комбинационных схем методом p-алгоритма.
единичное покрытие
нулевое покрытие
1. 8 Анализ КС методом синхронного моделирования.
1.9 Анализ КС методом асинхронного моделирования.
асинхронного моделирования
тактом моделирования.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ АБСТРАKТНЫХ АВТОМАТОВ.
Элементы алфавита
конечная упорядоченная последовательность букв — словом
Полностью определенным
детерминированным
вероятностный автомат
синхронных и асинхронных
устойчивого состояния
- асинхронный
СПОСОБЫ ОПИСАНИЯ И ЗАДАНИЯ АВТОМАТОВ.
СВЯЗЬ МЕЖДУ МОДЕЛЯМИ МИЛИ И МУРА.
МИНИМИЗАЦИЯ ЧИСЛА ВНУТРЕННИХ СОСТОЯНИЙ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ АВТОМАТОВ.
Структурный синтез ЦА.
Задачи синтеза ЦА.
Канонический метод структурного синтеза ЦА.
Элементарные цифровые автоматы с памятью
(триггерные устройства) и их свойства.
Задача синтеза структуры автомата.
комбинационные или логические элементы
теорема о структурной полноте
функцию входов элемента памяти
Элементарные цифровые автоматы – элементы памяти.
JK- триггер –
Пример канонического метода структурного синтеза автомата.
Особенности синтеза автоматов на базе T, RS, JK триггеров.
Кодирование внутренних состояний ЦА.
Гонки в автомате.
Если элементы памяти двоичные, то их число .
в тактировании входных сигналов автомата импульсами определенной длительности.
Кодирование состояний и сложность комбинационной схемы автомата.
Алгоритм кодирования для
Эвристический алгоритм кодирования.
Эвристический алгоритм состоит из следующих шагов.
Управляющие и операторные автоматы.
Принцип микропрограммного управления.
микрооперациями
логические условия
микропрограммой
Понятие операционного и управляющих автоматов.
Функция ОА определяется следующей совокупностью сведений:
СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ И МИКРОПРОГРАММ
ОПЕРАЦИОННЫЕ ЭЛЕМЕНТЫ
СИНТЕЗ АВТОМАТА МИЛИ
и проходящие обязательно только через одну операторную вершину
СИНТЕЗ АВТОМАТА МУРА.
СТРУКТУРНЫЙ СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ
СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МИЛИ
СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МУРА
1. В исходном автомате количество состояний М=7, следовательно число элементов памяти
ЗАМЕЧАНИЯ.
--PAGE_BREAK-- продолжение
--PAGE_BREAK--
Необходимо получить булевы функции S=F1(X1,X2, Рm) и Рс=F2(X1,X2, Рm). Карты Карно для этих функций приведены ниже (рис.2).
Как следует из приведённых карт, МДНФ соответствующих функций имеет вид:
S=<img width=«24» height=«25» src=«ref-1_118712647-216.coolpic» v:shapes="_x0000_i1030"><img width=«25» height=«25» src=«ref-1_118712863-221.coolpic» v:shapes="_x0000_i1031">Pm+<img width=«24» height=«25» src=«ref-1_118712647-216.coolpic» v:shapes="_x0000_i1032">X2<img width=«23» height=«27» src=«ref-1_118713300-214.coolpic» v:shapes="_x0000_i1033">+X1<img width=«25» height=«25» src=«ref-1_118712863-221.coolpic» v:shapes="_x0000_i1034"><img width=«23» height=«27» src=«ref-1_118713300-214.coolpic» v:shapes="_x0000_i1035">+X1X2Pm
Pc=X1X2+X1 Pm+X2Pm
Полученная система булевых функций представлена в базисе И, ИЛИ, НЕ. Соответствующая ей КС приведена на рисунке 4.
Полученную комбинационную схему можно упростить, вынеся за скобки общие части в выражениях для S и Рc, однако существенного результата это не даст (желательно самостоятельно в этом убедиться).
Значительно упростить схему можно, если воспользоваться другим базисом, например логическим элементом «ИСКЛЮЧАЮЩЕЕ ИЛИ». В этом случае выражение для S можно записать S = (X1+X2+ Рm)mod2= X1ÅX2ÅРm. Тогда схема для S будет иметь вид (рис.3).
Иногда для синтеза КС с несколькими выходами может использоваться следующий приём. Будем считать, что при синтезе схемы сумматора функция S является функцией четырёх переменных: S=f(X1,X2,Рm,Рс). Таблица истинности для этого случая принимает вид изображенный в таблице 2.
X1
1
1
1
1
1
1
1
1
X2
1
1
1
1
1
1
1
1
Pm
1
1
1
1
1
1
1
1
Pc
1
1
1
1
1
1
1
1
S
X
1
X
1
X
X
1
X
X
X
X
1
Неопределённые значения для S соответствуют наборам, которые никогда не могут быть в реальной схеме. Карта Карно для функции S=f(X1,X2,Pm,Pc) представлена на рис.5.
В результате минимизации, получается :
S=<img width=«39» height=«27» src=«ref-1_118717725-241.coolpic» v:shapes="_x0000_i1039">+X2<img width=«20» height=«27» src=«ref-1_118717966-211.coolpic» v:shapes="_x0000_i1040">+X1<img width=«20» height=«27» src=«ref-1_118717966-211.coolpic» v:shapes="_x0000_i1041">+X1X2Pm = (Pm+X2+X1)<img width=«20» height=«27» src=«ref-1_118717966-211.coolpic» v:shapes="_x0000_i1042">+ X1X2Pm
Сравнивая выражения (2) и (3), отмечаем, что функция S=f(X1,X2,Pm,Pc) проще, чем функция S=f1(X1,X2,Pm). Схему, соответствующую (3), предлагается построить самостоятельно.
Т.о. задача синтеза имеет обычно несколько решений. Для сравнения различных вариантов комбинационных схем используют их основные характеристики: сложность и быстродействие.
продолжение
--PAGE_BREAK--1.2. Характеристики комбинационных схем.
Сложность схемы оценивается количеством оборудования, составляющего схему. При разработке схем на основе конкретной элементной базы количество оборудования обычно измеряется числом корпусов (модулей) интегральных микросхем, используемых в схеме. В теоретических разработках ориентируются на произвольную элементную базу и поэтому для оценки затрат оборудования используется оценка сложности схем по Квайну.
Сложность (цена) по Квайну определяется суммарным числом входов логических элементов в составе схемы.
При такой оценке единица сложности – один вход логического элемента. Цена инверсного входа обычно принимается равной двум. Такой подход к оценке сложности оправдан по следующим причинам:
- сложность схемы легко вычисляется по булевым функциям, на основе которых строится схема: для ДНФ сложность схемы равна сумме количества букв,(букве со знаком отрицания соответствует цена 2), и количества знаков дизъюнкции, увеличенного на 1 для каждого дизъюнктивного выражения.
- все классические методы минимизации булевых функций обеспечивают минимальность схемы именно в смысле цены по Квайну.
Практика показывает, что схема с минимальной ценой по Квайну обычно реализуется наименьшим числом конструктивных элементов – корпусов интегральных микросхем.
Быстродействие комбинационной схемыоценивается максимальной задержкой сигнала при прохождении его от входа схемы к выходу, т.е. определяется промежутком времени от момента поступления входных сигналов до момента установления соответствующих значений выходных. Задержка сигнала кратна числу элементов, через которые проходит сигнал от входа к выходу схемы. Поэтому быстродействие схемы характеризуется значением rt, где t— задержка сигнала на одном элементе. Значение r определяется количеством уровней комбинационной схемы, которое рассчитывается следующим образом. Входам КС приписывается уровень нулевой. Логические элементы, связанные только со входами схемы относятся к уровню ПЕРВОМУ. Элемент относится к уровню k, если он связан по входам с элементами уровней k-1, k-2, и т.д. Максимальный уровень элементов r определяет количество уровней КС, называемое рангом схемы. Пример определения ранга r схемы приведён на рисунке 6.
Как известно, любая булева функция может быть представлена в ДНФ, которой соответствует двухуровневая комбинационная схема. Следовательно, быстродействие любой КС в принципе можно довести до 2t.
Минимизация булевой функции с целью уменьшения сложности схем обычно приводит к необходимости представления функций в скобочной форме, которой соответствуют схемы с r>2. Т.е., уменьшение затрат оборудования в общем случае приводит к снижению быстродействия схем.
1.3. Системы (серии) логических элементов и их
основные характеристики.
При построении КС устройств вычислительной техники используются различные логические элементы, которые должны согласоваться по входным и выходным сигналам, напряжению питания и т.д. Для этой цели логические элементы объединяют в серии.
Серией (системой, комплексом)логических элементов ЭВМ называется предназначенный для построения цифровых устройств функционально полный набор логических элементов, объединяемый общими электрическими, конструктивными и технологическими параметрами, использующий одинаковый способ представления информации, одинаковый тип межэлементных связей. Система элементов чаще всего избыточна по своему функциональному составу, что позволяет строить схемы более экономичные по количеству использованных элементов.
В состав серии входят элементы для выполнения логических операций, запоминающие элементы, элементы, реализующие функции узлов ЭВМ, а также специальные элементы для усиления, восстановления и формирования сигналов стандартной формы.
Конструктивно логические элементы представляют собой микроминиатюризованные интегральные электронные схемы (микросхемы), сформированные в кристалле кремния с помощью специальных технологических процессов.
В большинстве современных серий элементов имеются микросхемы малой степени интеграции (ИС до 100 элементов на кристалл), средней степени (СИС – до 1000 элементов на кристалл), большой степени интеграции (БИС – до 10000 элементов на кристалл) и сверхбольшой степени интеграции (СБИС – более 10000 элементов на кристалл). Логические элементы в виде ИС реализуют совокупность простых логических операций: И, ИЛИ, И-ИЛИ, И-НЕ, ИЛИ-НЕ и т.д. Логические элементы на СИС и БИС реализуют узлы ЭВМ, на СБИС – микроЭВМ.
Основными параметрами серии логических элементов являются:
— питающие напряжения и сигналы для представления логического 0 и логической 1;
— коэффициенты объединения по входу;
— нагрузочная способность (коэффициент разветвления по выходу);
— помехоустойчивость;
— рассеиваемая мощность;
— быстродействие.
Серия элементов характеризуется количеством используемых питающих напряжений и их номинальными значениями. Обычно логическому 0 соответствует низкий уровень напряжения, а логической 1 – высокий. Для наиболее часто используемых серий напряжение питания составляет +5В, уровень логической единицы 2,4-5В, уровень логического 0 – 0-0,4В.
Коэффициент объединения по входу(Коб) определяет максимально возможное число входов логического элемента, иными словами, функцию скольких переменных может реализовать этот элемент. Обычно Коб принимает значение от 2 до 4, реже Коб=8. Увеличение числа входов связано с усложнением схемы элементов и приводит к ухудшению других параметров – помехоустойчивости, быстродействия и т.д.
Коэффициент разветвления по выходу(Краз) показывает на сколько логических входов может быть одновременно нагружен выход данного логического элемента. Обычно Краз для наиболее часто используемых серий равен 10. Иногда вместо Краз задается предельно допустимое значение выходного тока логического элемента в состоянии 0 или 1.
Помехоустойчивость– это способность элемента правильно функционировать при наличии помех. Она определяется максимально допустимым напряжением помехи, при котором не происходит сбоя в его работе. Обычно это напряжение порядка 0,6-0,9 В.
Быстродействиелогических элементов является одним из важнейших параметров и характеризуется временем задержки распространения сигнала. Этот параметр существенно зависит от технологии изготовления микросхем и лежит в диапазоне от единиц до сотен наносекунд.
Наиболее часто употребляемые типы интегральных микросхем – это потенциальные элементы транзисторно-транзисторной логики (ТТЛ) — серии К155, К555, К531, К1533 и т.д., транзисторной логики с эмиттерными связями (ЭСТЛ) – это серии К500, К1500, элементы на КМОП транзисторах — серии К176, К561, К564 и т.д.
При синтезе КС на реальных логических элементах необходимо обязательно учитывать ограничения на Коб и Краз.
1.4. СИНТЕЗ КС С УЧЕТОМ ОГРАНИЧЕНИЙ НА <img width=«31» height=«24» src=«ref-1_118723381-223.coolpic» v:shapes="_x0000_i1045">.
При построении КС может оказаться, что выход k— го логического элемента нагружен <img width=«55» height=«24» src=«ref-1_118723604-250.coolpic» v:shapes="_x0000_i1046"> входов других ЛЭ (рис.7а). Это означает, что k — тый логический элемент перегружен и необходимо принять меры, устраняющие указанное явление. Существуют два способа обеспечения заданного<img width=«31» height=«24» src=«ref-1_118723381-223.coolpic» v:shapes="_x0000_i1047">:
· использование дополнительных развязывающих усилителей;
· дублирование перегруженного элемента.
Схема с использованием дополнительных развязывающих усилителей представлена на рис.7.б. Количество p дополнительных усилителей, необходимых для обеспечения заданного <img width=«31» height=«24» src=«ref-1_118723381-223.coolpic» v:shapes="_x0000_i1048">, определяется по формуле:
<img width=«171» height=«24» src=«ref-1_118724300-402.coolpic» v:shapes="_x0000_i1049">
Недостаток рассматриваемого способа в том, что в цепь распространения сигнала вносится дополнительная задержка, что не всегда допустимо.
Схема с использованием дублирования перегружаемого элемента представлена на рис.7.в. Количество p дополнительных элементов, выполняющих ту же функцию, что и К-тый элемент, определяется по формуле:
<img width=«56» height=«24» src=«ref-1_118724702-258.coolpic» v:shapes="_x0000_i1050">
При таком способе обеспечения <img width=«31» height=«24» src=«ref-1_118723381-223.coolpic» v:shapes="_x0000_i1051">дополнительная задержка не вносится, но увеличивается нагрузка на элементы, формирующие сигналы <img width=«21» height=«21» src=«ref-1_118725183-211.coolpic» v:shapes="_x0000_i1052"> и <img width=«23» height=«21» src=«ref-1_118725394-216.coolpic» v:shapes="_x0000_i1053">, что может привести к перегрузке этих элементов и введению дополнительных элементов для обеспечения заданного Краз.
1.5. СИНТЕЗ КС С УЧЕТОМ ОГРАНИЧЕНИЯ НА <img width=«27» height=«21» src=«ref-1_118725610-217.coolpic» v:shapes="_x0000_i1054">.
Представлению функции в виде ДНФ соответствует двухуровневая КС (если считать, что на ее вход могут поступать как прямые так и инверсные входные сигналы), на первом уровне которой элементы И , а их выходы объединяются на втором уровне элементом ИЛИ . Такое построение КС обеспечивает ее максимальное быстродействие, так как ранг схемы минимален. Однако, не всегда возможно на первом уровне и, особенно, на втором выбрать логические элементы с требуемым<img width=«27» height=«21» src=«ref-1_118725610-217.coolpic» v:shapes="_x0000_i1055">, т.к. может оказаться, что ЛЭ с таким <img width=«27» height=«21» src=«ref-1_118725610-217.coolpic» v:shapes="_x0000_i1056">не выпускаются промышленностью. В этом случае необходимо с помощью нескольких элементов с меньшим <img width=«27» height=«21» src=«ref-1_118725610-217.coolpic» v:shapes="_x0000_i1057">получить эквивалент с большим <img width=«27» height=«21» src=«ref-1_118725610-217.coolpic» v:shapes="_x0000_i1058"> либо, что предпочтительней, преобразовать БФ, перейдя от ДНФ к скобочной форме. Этот переход сопровождается уменьшением <img width=«27» height=«21» src=«ref-1_118725610-217.coolpic» v:shapes="_x0000_i1059">логических элементов, требуемого для построения схемы. Осуществить такой переход можно с помощью факторного алгоритма, суть которого рассмотрим на примере.
Пусть задана некоторая булева функция в виде
<img width=«399» height=«24» src=«ref-1_118726912-638.coolpic» v:shapes="_x0000_i1060">
Для реализации этой функции по приведенному выражению необходимо использовать 3 логических элемента 4И, один логический элемент 5И, один логический элемент 4ИЛИ.
С помощью факторного алгоритма получим скобочную форму для заданной функции. Для этого обозначим все конъюнкции буквами:
<img width=«111» height=«25» src=«ref-1_118727550-340.coolpic» v:shapes="_x0000_i1061"> <img width=«135» height=«21» src=«ref-1_118727890-351.coolpic» v:shapes="_x0000_i1062"> <img width=«108» height=«24» src=«ref-1_118728241-337.coolpic» v:shapes="_x0000_i1063">
и будем рассматривать их как некоторые множества. Находим попарные пересечения множеств:
<img width=«112» height=«24» src=«ref-1_118728578-328.coolpic» v:shapes="_x0000_i1064">, <img width=«76» height=«21» src=«ref-1_118728906-272.coolpic» v:shapes="_x0000_i1065">, <img width=«95» height=«24» src=«ref-1_118729178-309.coolpic» v:shapes="_x0000_i1066">, <img width=«75» height=«21» src=«ref-1_118729487-274.coolpic» v:shapes="_x0000_i1067">, <img width=«95» height=«21» src=«ref-1_118729761-308.coolpic» v:shapes="_x0000_i1068">, <img width=«76» height=«21» src=«ref-1_118730069-278.coolpic» v:shapes="_x0000_i1069">.
Полученные пересечения показывают общие части отдельных конъюнкций. Выбираем пересечение, которое имеет наибольшую длину (если такое отсутствует, то выбирают то, которое чаще всего встречается). В данном случае это <img width=«112» height=«21» src=«ref-1_118730347-331.coolpic» v:shapes="_x0000_i1070"> . Поэтому из конъюнкций А и В выносим общую часть<img width=«61» height=«21» src=«ref-1_118730678-280.coolpic» v:shapes="_x0000_i1071">. Тогда имеем:
<img width=«368» height=«24» src=«ref-1_118730958-610.coolpic» v:shapes="_x0000_i1072">.
Обозначим F = <img width=«153» height=«24» src=«ref-1_118731568-394.coolpic» v:shapes="_x0000_i1073"> и находим пересечения:
<img width=«76» height=«21» src=«ref-1_118731962-275.coolpic» v:shapes="_x0000_i1074">, <img width=«95» height=«21» src=«ref-1_118732237-305.coolpic» v:shapes="_x0000_i1075">, <img width=«76» height=«21» src=«ref-1_118730069-278.coolpic» v:shapes="_x0000_i1076">.
Следовательно, для исходной функции имеем:
<img width=«341» height=«24» src=«ref-1_118732820-576.coolpic» v:shapes="_x0000_i1077">.
Обозначим <img width=«249» height=«24» src=«ref-1_118733396-492.coolpic» v:shapes="_x0000_i1078">,
Пересечение<img width=«76» height=«21» src=«ref-1_118733888-276.coolpic» v:shapes="_x0000_i1079">. Следовательно, окончательно имеем:
<img width=«337» height=«24» src=«ref-1_118734164-568.coolpic» v:shapes="_x0000_i1080">
Для реализации функции по последнему выражению необходимо 5 элементов 2И, 1 элемент 3И, 3 элемента 2ИЛИ ( рис.8 ).
Как видно из полученной схемы для ее реализации необходимы элементы с <img width=«28» height=«24» src=«ref-1_118736522-219.coolpic» v:shapes="_x0000_i1081"> = 2 или 3 (в отличие от исходной с <img width=«28» height=«24» src=«ref-1_118736522-219.coolpic» v:shapes="_x0000_i1082"> = 4 или 5). Однако ранг схемы увеличился до 7, что приводит к увеличению задержки срабатывания схемы.
--PAGE_BREAK--прямые и косвенные.
В результате анализа КС прямым методом получается множество наборов входных переменных, обеспечивающих заданное значение на выходе, что позволяет записать в алгебраическом виде БФ, реализуемую схемой. К прямым методам относится метод p— алгоритма.
Применение косвенных методов дает возможность определить реакцию схемы на заданный набор входных переменных в статике или проанализировать переходный процесс смены одного входного набора на другой. Примерами косвенных методов анализа, являются методы синхронного и асинхронного моделирования.
Все упомянутые методы анализа являются машинoориентированными, что позволяет выполнить анализ схемы на ЭВМ.
Для всех методов анализа необходимо описать схему в виде схемного списка, в который включается в общем случае следующие данные: номер ЛЭ в схеме; логическая функция, реализуемая ЛЭ; входные переменные для данного ЛЭ. Например, схема представленная на рис.9, может быть описана следующим списком:
1.7. Анализ комбинационных схем методом
p
-алгоритма.
При данном методе, как упоминалось выше, ищутся наборы входных переменных, обеспечивающих заданное значение на выходе КС. Наборы, обеспечивающие на выходе КС логическую 1, образуют так называемое единичное покрытие <img width=«21» height=«21» src=«ref-1_118738835-206.coolpic» v:shapes="_x0000_i1085">. Аналогично, входные наборы, обеспечивающие на выходе КС логический 0, образуют нулевое покрытие <img width=«23» height=«21» src=«ref-1_118739041-207.coolpic» v:shapes="_x0000_i1086">. Рассмотрим покрытия<img width=«23» height=«21» src=«ref-1_118739041-207.coolpic» v:shapes="_x0000_i1087">и <img width=«21» height=«21» src=«ref-1_118738835-206.coolpic» v:shapes="_x0000_i1088">для простейшего логического элемента 2И, выполняющего функцию Y=X1X2. Таблица истинности для этой функции:
Табл.3 Таблица истинности функции Y=X1X2
Как видно из приведенной таблицы только при единственном наборе X1=1 и X2=1 на выходе ЛЭ будет 1, т.е. единичное покрытие включает только один набор <img width=«21» height=«21» src=«ref-1_118738835-206.coolpic» v:shapes="_x0000_i1090">={1 1}. На выходе ЛЭ будет 0 при трех наборах, образующих нулевое покрытие:
<img width=«69» height=«75» src=«ref-1_118740809-292.coolpic» v:shapes="_x0000_i1091">
Это покрытие можно упростить, заметив, что первый набор склеивается со вторым и третьим, т.е.
<img width=«76» height=«48» src=«ref-1_118741101-312.coolpic» v:shapes="_x0000_i1092">
Т.о. для ЛЭ 2И можно сказать, что 1 на его выходе будет только при обеих единицах на входах, а для обеспечения 0 на выходе достаточно подать хотя бы на один вход 0. Рассуждая аналогично, получим таблицу покрытий <img width=«23» height=«21» src=«ref-1_118739041-207.coolpic» v:shapes="_x0000_i1093">и<img width=«21» height=«21» src=«ref-1_118738835-206.coolpic» v:shapes="_x0000_i1094"> для основных ЛЭ, представленных ниже в табл. 4.
Таблица 4.
ЛЭ Y Y Y Y Y Y Y
НЕ 2И 2И – НЕ 2ИЛИ 2ИЛИ–НЕ ИСК. ИЛИ 3И – НЕ
X X1X2 X1X2 X1 X2 X1X2 X1X2 X1X2X3
<img width=«657» height=«301» src=«ref-1_118741826-5938.coolpic» v:shapes="_x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058 _x0000_s1059 _x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1064 _x0000_s1065 _x0000_s1066 _x0000_s1067 _x0000_s1068 _x0000_s1069 _x0000_s1070 _x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075 _x0000_s1076 _x0000_s1077 _x0000_s1078 _x0000_s1079 _x0000_s1080 _x0000_s1081 _x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095 _x0000_s1096 _x0000_s1097 _x0000_s1098">
<img width=«23» height=«21» src=«ref-1_118739041-207.coolpic» v:shapes="_x0000_i1095"> 1 0 X 1 1 0 0 1 X 0 0 1 1 1
X 0 X 1 1 1
<img width=«21» height=«21» src=«ref-1_118738835-206.coolpic» v:shapes="_x0000_i1096"> 0 1 1 0 X 1 X 0 0 0 1 0 X X
X 0 X 1 1 0 X 0 X
X X 0
При анализе схемы методом p— алгоритма, задавшись определенным значением на выходе, заменяют его соответствующим покрытием элемента, формирующего выходной сигнал. В результате этого определяется, какие должны быть сигналы на выходах элементов, подключенных к выходному ЛЭ. В свою очередь, сигналы на выходах этих элементов можно заменить соответствующими покрытиями, т.е. определить значения выходных сигналов для других ЛЭ и т.д. Этот процесс продолжается до тех пор, пока не получатся покрытия, состоящие только из входных переменных, называемых опорными. Совокупность таких покрытий и дает соответствующее покрытие схемы.
Пример анализа КС (рис 9. ) методом p— алгоритма представлен в табл. 5. В последней колонке этой таблицы приведен оператор подстановки, в результате работы которого сигнал на выходе ЛЭ заменяется соответствующим покрытием. Необходимо обратить внимание, что все значения переменных, записанные в одной строке, должны одновременно быть в наличии для обеспечения заданного значения выходного сигнала. По-
этому, при замене одного из значений в строке соответствующим покрытием, все остальные значения для других переменных в этой строке должны присутствовать совместно с этим покрытием.
На основании полученного единичного покрытия можно записать БФ, реализуемую схемой:
<img width=«196» height=«25» src=«ref-1_118748177-405.coolpic» v:shapes="_x0000_i1097">
Таблица 5 Анализ схемы методом p– алгоритма.
<img width=«99» height=«101» src=«ref-1_118748582-443.coolpic» v:shapes="_x0000_s1386"><img width=«414» height=«186» src=«ref-1_118749025-1927.coolpic» v:shapes="_x0000_i1098">
а) Получение первого покрытия<img width=«21» height=«21» src=«ref-1_118738835-206.coolpic» v:shapes="_x0000_i1099">
б) Получение нулевого покрытия <img width=«23» height=«21» src=«ref-1_118739041-207.coolpic» v:shapes="_x0000_i1101">
В дальнейшем можно сравнить полученную БФ с той, по которой строилась схема и проверить правильность ее построения. При анализе схемы может оказаться, что некоторая переменная, получившая на одном из предыдущих шагов некоторые значения на данном шаге должна принять противоположное значение. Возникшее противоречие говорит о том, что данный путь является тупиковым и его необходимо исключить из дальнейшего рассмотрения. Если ни при одной комбинации входных переменных не обеспечивается значение 1(0) на выходе, то это означает, что схема реализует константу 0(1) соответственно.
1. 8 Анализ КС методом синхронного моделирования.
При данном методе считается, что все ЛЭ переключаются одновременно, без задержки. В результате применения метода определяется установившееся значение сигнала на выходе схемы.
Рассмотрим метод синхронного моделирования на примере схемы ( рис.9 ).
На первом этапе схему разбиваем на уровни и записываем в порядке возрастания уровня уравнения, описывающие функционирование ЛЭ:
Проанализируем схему при подаче на вход набора X1=0, Х2=0, Х3=0, Х4=1, Х5=1. Для этого решаем записанные уравнения в порядке возрастания уравнения. Имеем:
<img width=«164» height=«23» src=«ref-1_118753883-354.coolpic» v:shapes="_x0000_i1102">;
<img width=«161» height=«27» src=«ref-1_118754237-354.coolpic» v:shapes="_x0000_i1103">;
<img width=«151» height=«27» src=«ref-1_118754591-347.coolpic» v:shapes="_x0000_i1104">;
<img width=«176» height=«24» src=«ref-1_118754938-344.coolpic» v:shapes="_x0000_i1105">.
Следовательно, при подаче на вход набора {00011}, на выходе будет Y=1. Аналогично можно промоделировать работу схемы при подаче на вход любого другого набора.
продолжение
--PAGE_BREAK--1.9 Анализ КС методом асинхронного моделирования.
Реальный ЛЭ переключается за какое-то конечное время, зависящее от технологии изготовления, условий эксплуатации, емкостей нагрузки и т.д. Прохождение сигнала последовательно через несколько ЛЭ будет приводить к накоплению времени задержки и возникновению сдвига во времени выходного сигнала по отношению ко входному. Наличие задержки и порождаемого ею временного сдвига сигналов может приводить к появлению на выходе отдельных ЛЭ и всей схемы в целом кратковременных сигналов, не предусмотренных БФ, реализуемой схемой. Как иллюстрацию, рассмотрим схему рис.11, а .
Рис. 11 а)
Рис. 11. Статический риск сбоя.
а)- схема, б)- временные диаграммы.
t1-время задержки инвертора
t2-время задержки элемента 2И
Данная схема реализует функцию <img width=«100» height=«23» src=«ref-1_118756299-302.coolpic» v:shapes="_x0000_i1106">, т.е. константу 0 независимо от входного сигнала X. Однако в переходном процессе в результате задержки срабатывания ЛЭ возможна ситуация, когда на обоих входах элемента 2И будут логические единицы, что может привести к появлению на выходе схемы логической 1 (см. рис.11 б). Рассмотренный случай возможен при задержке срабатывания второго элемента больше, чем первого. Такое явление называется риском сбоя. Различают статистический и динамический риски сбоя.
При статическом риске сбоя до и после переходного процесса состояние выходного сигнала одно и то же, а во время переходного процесса возможно кратковременное появление противоположного сигнала.
При динамическом риске сбоя до и после переходного процесса состояния выходного сигнала противоположные, но в переходном процессе выходной сигнал несколько раз меняет свое значение. Динамический риск сбоя возможен в схеме (рис.12 а) при смене набора (Х1=0, Х2=1, Х3=1) на набор (Х1=1, Х2=0, Х3=0) и иллюстрируется диаграммами (рис.12 б).
В данном примере динамический риск сбоя на выходе КС сопровождается статическим на выходе элемента 1. Как видно из временных диаграмм риск сбоя имеет место при наличии определенного временного сдвига между сигналами, поступающими на вход ЛЭ. Нежелательные сигналы на выходе могут и отсутствовать при другом соотношении временных сигналов, однако принципиальная возможность их появления является фактором снижающим надежность работы схемы. Поэтому очень важно уметь обнаруживать и устранять такие явления.
Для анализа процесса переключения КС при смене входных наборов и обнаружения рисков сбоя используется метод асинхронного моделирования. При этом методе считается, что каждый элемент переключается с одинаковой задержкой. Анализ включает такие этапы:
1.Каждому элементу схемы присваивается уровень, причем уровень 1 имеют элементы, все входы которых являются независимыми входами схемы.
2.Записываются уравнения, описывающие каждый ЛЭ в порядке убывания уровня.
3.Для исходного входного набора А(X1, X2, …, Xn) определяется значение сигналов на выходах всех ЛЭ схемы. Пусть данный набор А заменяется набором В(X1, X2, …, Xn).
4.Помечаются те уравнения, в правой части которых хотя бы одна из переменных изменила свое значение.
5.Решаются помеченные уравнения в порядке их записи в схеме . После решения уравнение считается непомеченным.
6.Если после решения всех уравнений системы переменные, входящие в левые части уравнений, изменили свои значения, то вновь помечаются те уравнения, в правые части которых входят эти переменные. Затем осуществляется переход к п.5. В противном случае моделирование данного входного набора считается законченным. Выполнение п.5 называется тактом моделирования.
Анализ схемы (рис.13) методом асинхронного моделирования приведен ниже. Для данной схемы входной набор А(1011110) заменяется набором В(1101011).
Рис. 13. Комбинационная схема для метода асинхронного моделирования.
Уравнения, описывающие ЛЭ:
Табл. 6 Таблица моделирования схемы
Выходы Такты моделирования Прим.
0 1 2 3
e6 1 0 1 0 дин.
e5 0 1 0 0 стат.
e4 0 0 0 0
e3 1 0 0 0
e2 1 0 0 0
<img width=«410» height=«319» src=«ref-1_118760042-2985.coolpic» v:shapes="_x0000_s1101 _x0000_s1102 _x0000_s1103 _x0000_s1104 _x0000_s1105 _x0000_s1106 _x0000_s1107 _x0000_s1108 _x0000_s1109 _x0000_s1110 _x0000_s1111 _x0000_s1112 _x0000_s1113 _x0000_s1114 _x0000_s1115 _x0000_s1116 _x0000_s1117 _x0000_s1118 _x0000_s1119 _x0000_s1120 _x0000_s1121 _x0000_s1122 _x0000_s1123 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127 _x0000_s1128">
e1 0 1 0 1
Как следует из результатов моделирования, при смене набора А набором В на выходе элемента 4 имеет место статический риск сбоя, а на выходе схемы — динамический риск сбоя.
Радикальным способом устранения рисков сбоя является введение стробирования для снятия выходного сигнала КС. Стробирующий импульс подается после окончания переходного процесса в КС (т.е. когда на выходе КС уже установилось необходимое значение выходного сигнала), что исключает влияние возможных сбоев на вырабатываемый схемой сигнал.
продолжение
--PAGE_BREAK--ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ АБСТРА
K
ТНЫХ АВТОМАТОВ
.
Ознакомившись в курсах «Программирование» и «Машинная арифметика» с принципами работы ЭЦВМ, можно указать на две основные особенности таких вычислительных машин: оперирование данными, представленными в цифровой форме и автоматическая работа по заранее составленной программе. Эти особенности показывают, что любая ЭЦВМ является цифровым автоматом (ЦА). Понятие ЦА служит обобщением для всех видов устройств обработки цифровой информации, имеющих программное управление.
Цифровой автомат — устройство, характеризующееся набором внутренних состояний в которое оно попадет под воздействием команд заложенной в него программы. Переход автомата из одного состояния в другое осуществляется в определенный момент времени.
Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстрактный автомат, определенный как 6-компонентный кортеж: S=(A,Z,W,d,l, а1) у которого:
1. A={a1, a2,… ,am} — множество состояний (внутренний алфавит)
2. Z={z1, z2,… ,zf} — множество входных сигналов (входной алфавит)
3. W={w1, w2, ..., wg} — множество выходных сигналов (выходной алфавит)
4. d: A·Z®A — функция переходов, реализующая отображение DdÍА·Z в А. Иными словами функция dнекоторым парам состояние — входной сигнал (аm, zf) ставит в соответствие состояния автомата аs= d(am, zf), asÎA.
5. l : A·Z®W — функция выходов, реализующая отображение DlÍА·Z на W. Функция l некоторым парам состояние — входной сигнал (аm, zf) ставит в соответствие выходные сигналы автомата Wg=l(аm, zf), WgÎW.
6. aiÎA — начальное состояние автомата.
Под алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называются буквами, а конечная упорядоченная последовательность букв — словом в данном алфавите.
Абстрактный автомат (рис.14) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном состоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита z(t)Î
Z. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита W(t)=l(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=d[a(t), z(t)], a(t) ÎA, w(t) ÎW.
Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z во множество слов выходного алфавита W. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1),… — входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1),… — выходное слово. Т.о. выходное слово = j(входное слово), где j— отображение, осуществляемое абстрактным автоматом.
На уровне абстрактной теории понятие «работа автомата» понимается как преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате отвлекаемся от его структуры — содержимого прямоугольника (рис. 14 ), рассматривая его как «черный ящик», т.е. основное внимание уделяем поведению автомата относительно внешней среды.
Понятие состояния в определении автомата введено в связи с тем, что часто возникает необходимость в описании поведения систем, выходы которых зависят не только от состояния входов в данный момент времени, но и от некоторой предыстории, т.е. от сигналов, которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходной сигнал как функцию состояния и входа в данный момент времени.
На практике наибольшее распространение получили два класса автоматов — автоматы Мили (Mealy) и Мура (Moore).
Закон функционирования автомата Мили задается уравнениями:
a(t+1) = d(a(t), z(t)); w(t) = l(a(t), z(t)), t = 0,1,2,...
Закон функционирования автомата Мура задается уравнениями:
a(t+1)=d(a(t), z(t)); w(t) = l(a(t)), t = 0,1,2,...
Из сравнения законов функционирования видно, что, в отличие от автомата Мили, выходной сигнал в автомате Мура зависит только от текущего состояния автомата и в явном виде не зависит от входного сигнала. Для полного задания автомата Мили или Мура дополнительно к законам функционирования, необходимо указать начальное состояние и определить внутренний, входной и выходной алфавиты.
Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так называемым С- автоматом.
Под абстрактным С- автоматом будем понимать математическую модель дискретного устройства, определяемую восьмикомпонентным вектором S=( A, Z, W, U, d, l1, l2, а1 ), у которого:
1. A={a1, a2,… ,am} — множество состояний;
2. Z={z1, z2,… ,zf} — входной алфавит;
3. W={w1, w2, ..., wg} — выходной алфавит типа 1;
4. U={u1, u2,...,uh} — выходной алфавит типа 2;
5. d: A ·Z ®A — функция переходов, реализующая отображение DdÍА·Z в А;
6. l1: A ·Z ®W — функция выходов, реализующая отображение Dl1ÍА·Z в W;
7. l2: A ®U — функция выходов, реализующая отображение Dl2Í
А в U;
8. а1 ÎА — начальное состояние автомата.
Абстрактный С- автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Отличие С — автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов l1 и l2, каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:
а( t + 1) = d( a( t ), z( t )); w( t ) = l1( a ( t ), z( t )); u( t ) = l2( a( t )); t = 0, 1, 2, ...
Выходной сигнал Uh=l2( am) выдается все время, пока автомат находится в состоянии am. Выходной сигнал Wg=l1( am, zf) выдается во время действия входного сигнала Zfпри нахождении автомата в состоянии am.
Рассмотренные выше абстрактные автоматы можно разделить на:
1) полностью определенные и частичные;
2) детерминированные и вероятностные;
3) синхронные и асинхронные;
Полностью определеннымназывается абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар ( ai, zj).
Частичнымназывается абстрактный автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар ( ai, zj).
К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов : автомат, находящийся в некотором состоянии ai, под действием любого входного сигнала zjне может перейти более, чем в одно состояние.
В противном случае это будет вероятностный автомат, в котором при заданном состоянии aiи заданном входном сигнале zjвозможен переход с заданной вероятностью в различные состояния.
Для определения синхронных и асинхронных автоматов вводится понятие устойчивого состояния. Состояние asавтомата называется устойчивым, если для любого состояния ai и входного сигнала zj таких, что d( ai, zj) = asимеет место d( as, zj) = as, т.е. состояние устойчиво, если попав в это состояние под действием некоторого сигнала zj, автомат выйдет из него только под действием другого сигнала zk, отличного от zj.
Автомат, у которого все состояния устойчивы продолжение
--PAGE_BREAK--- асинхронный.
Автомат называется синхронным, если он не является асинхронным.
Абстрактный автомат называется конечным, если конечны множества А = {a1, a2, ..., am}, Z = {z1, z2, ..., zf}, W = {w1, w2, ..., wg}. Автомат носит название инициального, если в нем выделено начальное состояние a1.
СПОСОБЫ ОПИСАНИЯ И ЗАДАНИЯ АВТОМАТОВ.
Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, Z, W, d, l, а1 ). Множества А, Z, W описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций dи l( следовательно и всего автомата в целом ) наибольшее распространение получили табличный и графический.
При табличном способе задания автомат Мили описывается с помощью двух таблиц. Одна из них (таблица переходов ) задает функцию d, т.е. a( t +1) = d( a( t ), z( t )) ( табл.7), вторая (таблица выходов ) — функцию l, т.е. W( t )=l( a( t ), z( t )) ( табл. 8).
Каждому столбцу из приведенных таблиц поставлено в соответствие одно состояние из множества А, каждой строке - один входной сигнал из множества Z. На пересечении столбца amи строки zfв табл.7 записывается состояние as, в которое должен перейти автомат из состояния amпод действием входного сигнала Zf, т.е. as = d(am, zf). На пересечении столбца amи строки zfв табл.8 записывается выходной сигнал Wg, выдаваемый автоматом в состоянии am при поступлении на вход сигнала zf, т.е. Wg = l( am, zf ).
Для приведенных таблиц множества, образующие автомат A={a1, a2, a3,a4}, Z={z1, z2}, W={w1, w2, w3, w4, w5}. Автомат Мили может быть задан одной совмещенной таблицей переходов и выходов (табл.9), в которой каждый элемент as/ wgзаписанный на пересечении столбца am и строки zf, определяется следующим образом:
as=d(am, zf); wf=l(am, zf).
Автомат Мура задается одной отмеченной таблицей переходов (табл.10), в которой каждому столбцу приписаны не только состояние am, но еще и выходной сигнал Wg, соответствующий этому состоянию, где Wg=l(am).
Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте не определенных состояний и выходных сигналов ставится прочерк. В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода. Кроме того, выходной сигнал может быть неопределенным и для некоторых существующих переходов.
Для задания С — автоматов также используется табличный метод. В этом случае таблица переходов (табл.11) аналогична таблице переходов автомата Мили, а в таблице выходов каждое состояние отмечено соответствующим выходным сигналом uiвыходного алфавита типа 2 (табл.12)
При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги — переходам между ними. Дуга, направленная из вершины am, задает переход в автомате из состояния am в состояние as. В начале этой дуги записывается входной сигнал ZfÎZ, вызывающий данный переход as=d(am,zf). Для графа автомата Мили выходной сигнал wgÎW, формируемый на переходе, записывается в конце дуги, а для автомата Мура — рядом с вершиной am, отмеченной состоянием am, в котором он формируется. Если переход в автомате из состояния am в состояние as производится под действием нескольких входных сигналов, то дуге графа, направленной из am в as, приписываются все эти входные и соответствующие выходные сигналы. Граф С- автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Графы автоматов, заданных своими таблицами переходов и выходов
(табл. 7¸12) представлены на рисунках 15,16,17.
СВЯЗЬ МЕЖДУ МОДЕЛЯМИ МИЛИ И МУРА.
Рассмотрим некоторый автомат Мили, заданный таблицами переходов и выходов. Таблица переходов а) и выходов б) автомата Мили
Подадим на вход автомата, установленного в состояние а1, входное слово x=z1 z2 z2 z1 z2 z2. Так как d(а1, z1) = a2, l(a1, z1) = W2, то под воздействием входного сигнала z1 автомат перейдет в состояние а2 и выдаст на переходе выходной сигнал W2. Затем, находясь в состоянии а2 под воздействием сигнала Z2 перейдет в состояние а1=d(а2, z2) и выдаст сигнал W1=l(a2, z2) и т.д. В табл. 13 приведена последовательность состояний, которые автомат проходит, воспринимая входное слово x, и выходные сигналы, вырабатываемые на этих переходах.
Назовем выходное слово w= l(a1,x) реакцией автомата Мили в состоянии а1 на входное слово x.
В нашем случае w= w2 w1 w2 w2 w1 w2
Как видно, из приведенного примера, в ответ на входное слово длины k автомат Мили выдаст последовательность состояний длины k +1 и выходное слово длины k.
В общем виде поведение автомата Мили, установленного в состояние am, можно описать следующим образом (табл. 14).
Аналогично можно описать поведение автомата Мура, находящегося в состоянии a1, при приходе входного слова
x = Zi1, Zi2,..., Zik , учитывая, что W( t ) = l(a( t )):
Очевидно, что для автомата Мура выходной сигнал Wi1= l(am) в момент времени i1 не зависит от входного сигнала Zi1и определяется только состоянием am. Следовательно, сигнал Wi1никак не связан с входным словом x.
В связи с этим под реакцией автомата Мура, установленного в состояние am, на входное слово x= Zi1, Zi2,..., Zik будем понимать выходное слово той же длины w= l(am, x) = Wi2Wi3...Wik+1, сдвинутое по отношению к xна один такт.
Рассмотрим пример. Пусть задан автомат Мура:
Подадим на вход этого автомата ту же последовательность, что и для автомата Мили: x=z1 z2 z2 z1 z2 z2. Последовательность смены состояний и вырабатываемых выходных сигналов представлена в таблице:
Сравнивая реакции автомата Мили (табл. 13) и автомата Мура (табл.15), отмечаем, что эти реакции на одно и то же слово xсовпадают. Следовательно автоматы Мили и Мура реализуют одно и то же преобразование слов входного алфавита. Такие автоматы называются эквивалентными. Строгое определение эквивалентности следующее:
продолжение
--PAGE_BREAK--два автомата с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установки их в начальное состояние их реакции на любое входное слово совпадают.
Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура и наоборот.
Переход от автомата Мура к эквивалентному ему автомату Мили тривиален и легко осуществляется при графическом способе задания автомата. Для получения графа автомата Мили необходимо выходной сигнал Wg, записанный рядом с вершиной asисходного автомата Мура, перенести на все дуги, входящие в эту вершину. На рис. 18 приведен граф автомата Мили, эквивалентного автомату Мура (рис. 16)
Легко убедиться, что полученный автомат Мили действительно эквивалентный исходному автомату Мура. Для этого достаточно рассмотреть реакцию обеих автоматов на произвольную входную последовательность, что предлагается выполнить самостоятельно. Необходимо также отметить, что в эквивалентном автомате Мили количество состояний такое же, как и в исходном автомате Мура.
Переход от автомата Мили к эквивалентному ему автомату Мура более сложен. Это связано с тем, что в автомате Мура в каждом состоянии вырабатывается только один выходной сигнал. Как и в предыдущем случае, переход наиболее наглядно делать при графическом способе задания автомата. В этом случае каждое состояние aiисходного автомата Мили порождает столько состояний автомата Мура, сколько различных выходных сигналов вырабатывается в исходном автомате при попадании в состояние ai. Рассмотрим переход от автомата Мили Sa к автомату Мура Sb на примере автомата (рис. 15).
Как следует из рис. 15 для автомата Sa при попадании в состояние а1 вырабатываются выходные сигналы W2, W4, W5, при попадании в а2 – W1, W2, a3 – W2, a4 – W3. Каждой паре состояние ai— выходной сигнал Wj, который вырабатывается при попадании в это состояние, поставим в соответствие состояние bkэквивалентного автомата Мура Sb с тем же выходным сигналом Wj : b1 = (a1, W2), b2 = (a1, W4), b3 = (a1, W5), b4 = (a2, W1), b5 = (a2, W2), b6 =(a3, W2), b7 = (a4, W3), т.е. каждое состояние aiавтомата Мили порождает некоторое множество Aiсостояний эквивалентного автомата Мура: A1 = { b1, b2, b3 }, A2 = { b4, b5 }, A3 = { b6 }, A4 = { b7 }. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа Sbпоступаем следующим образом. Т.к. в автомате Saесть переход из состояния а1 в состояние а2 под действием сигнала z1 с выдачей W1, то из множества состояний A1 = {b1, b2, b3}, порождаемых состоянием а1 автомата Sa в автомате Sb должен быть переход в состояние (a3, W2) = b6 под действием сигнала Z2 и т.д. Граф эквивалентного автомата Мура представлен на рис.19.
Если от автомата Мура Sb, эквивалентного автомату Мили Sa (рис. 19) вновь перейти к автомату Мили, то получим автомат Мили S1 (рис. 20)
Вследствие транзитивности отношения эквивалентности два автомата Мили S1 и Sa также будут эквивалентными, но у последнего будут на 3 состояния больше. Т.о., эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (т.е. с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов.
МИНИМИЗАЦИЯ ЧИСЛА ВНУТРЕННИХ СОСТОЯНИЙ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ АВТОМАТОВ.
Рассмотрим метод минимизации полностью определенных автоматов, предложенный Ауфенкампом и Хоном.
Основная идея этого метода заключается в разбиении всех состояний исходного абстрактного автомата на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Т.о. получающийся в результате минимальный автомат имеет столько состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата.
Для пользования методом введем несколько определений.
Два состояния абстрактного автомата называются 1-эквивалентными в том случае, если реакции автомата в этих состояниях на всевозможные входные слова совпадают.
Объединение всех 1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.
1-эквивалентные состояния автомата называются 2-эквивалентными, если они переводятся любым входным сигналом также в 1-эквивалентные состояния.
Объединение всех 2-эквивалентных состояний образует 2-класс эквивалентности.
По индукции можно распространить определение до i-эквивалентных состояний и i-классов эквивалентности.
Если для некоторого i разбиения состояний автомата на ( i +1) — классы совпадает с разбиением на i-классы, то оно является разбиением и на ¥— классы эквивалентности.
Разбиение множества внутренних состояний автомата на ¥— классы и является требуемым разбиением на классы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.
Все вышеизложенное непосредственно применимо к минимизации автомата Мили. При минимизации полностью определенных автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы: к такому классу относятся одинаково отмеченные состояния автомата Мура.
Если два 0-эквивалентных состояния любым входным сигналом переводится в два 0-эквивалентных состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автомата Мура определяются аналогично приведенному для автоматов Мили.
Рассмотрим пример минимизации автомата Мили, заданного таблицами переходов и выходов :
Из таблицы выходов получаем разбиение на 1-классы эквивалентности p1, объединяя в эквивалентные классы Bi состояния с одинаковыми столбцами:
p1= {B1, B2}; B2 = {a1, a2, a5, a6}; B2 = {a3, a4}
Для получения 2-эквивалентных состояний строим таблицу 1-разбиения (табл.17), заменяя в таблице переходов состояния a1 соответствующими классами эквивалентности B1 или B2.
Из полученной таблицы 1-разбиения получаем 2-классы эквивалентности Ci и разбиение p2 = {C1, C2, C3}, где С1 = {a1, a1}, C2 = {a5, a6}, C3 = {a3, a4}. Сравнивая p2и p1, отмечаем, что эти разбиения отличаются друг от друга. Поэтому аналогично строим таблицу 2-разбиения (табл. 18), опять заменяя в таблице переходов состояния aiсоответствующими классами эквивалентности Ci.
Из полученной таблицы 2-разбиения получаем 3-классы эквивалентности Diи разбиение p3 ={ D1, D2, D3}, где D1 = {a1, a2}, D2 = {a5, a6}, D3 = {a3, a4}.
Сравнивая p3и p2, замечаем, что D1 = C1, D2 = C2, D3 = C3, p3 = p3. Следовательно получили разбиение на ¥— эквивалентные классы. Т.к. всего три таких класса, то минимальный автомат будет содержать всего три состояния. Выбираем из каждого класса Diпо одному состоянию и получаем множество состояний A' минимального автомата. Пусть, например, A'={a1, a4, a5}. Для получения минимального автомата из первоначальных таблиц переходов и выходов (табл. 16) вычеркиваем столбцы, соответствующие «лишним состояниям» a2, a3, a6. В результате получается минимальный автомат Мили, эквивалентный исходному автомату (табл. 19).
Минимизацией числа внутренних состояний автомата заканчивается этап абстрактного синтеза.
продолжение
--PAGE_BREAK--Структурный синтез ЦА.
Задачи синтеза ЦА.
Канонический метод структурного синтеза ЦА.
Элементарные цифровые автоматы с памятью
(триггерные устройства) и их свойства.
Вслед за этапом абстрактного синтеза автоматов следует этап структурного синтеза, целью которого является построение схемы, реализующей автомат из элементов заданного типа. Если абстрактный автомат был лишь математической моделью, проектируемого устройства, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутренне устройство на уровне логических схем. Основной задачей структурной теории автоматов является разработка общих методов построения структурных схем автоматов.
В отличие от абстрактного автомата, имеющего один вход и один выход, на которые поступают сигналы во входном и выходят в выходном W={W1,..,WG} алфавитах, структурный автомат имеет L входных каналов х1, х2,.., хL и N выходных y
1
,
y
2
,…,
yN на каждом из которых присутствует сигнал структурного алфавита.
Обычно в качестве структурного используется двоичный алфавит.
В этом случае каждому входному сигналу ZF абстрактного автомата соответствует некоторый двоичный вектор (lf1
,lf
2
,..,lf
L
), где lfLÎ{0,1}.
Очевидно, что для представления (кодирования) входных сигналов Z1,..,ZF абстрактного автомата различными двоичными векторами должно быть выполнено условие
L
<img width=«13» height=«16» src=«ref-1_118798627-191.coolpic» v:shapes="_x0000_i1137">
] log2F [,
аналогично
N
<img width=«13» height=«16» src=«ref-1_118798627-191.coolpic» v:shapes="_x0000_i1138">
] log2G [
Например, Z={Z1,Z2,Z3,Z4} W={W1,W2,W3}.
Тогда L <img width=«13» height=«16» src=«ref-1_118798627-191.coolpic» v:shapes="_x0000_i1139"> log24=2 N <img width=«13» height=«16» src=«ref-1_118798627-191.coolpic» v:shapes="_x0000_i1140">
log23=2
Закодировать входные и выходные сигналы можно, например, так:
Z1= 00 W1 = 00
Z2= 01 W2 = 01
Z3= 10 W3 = 11
Z4= 11
Задача синтеза структуры автомата.
На этапе структурного синтеза предварительно выбираются элементарные автоматы, путем композиции которых строят логические схемы полученных на этапе абстрактного синтеза автоматов Мили и Мура. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.
Рассмотрим канонический метод структурного синтеза при котором используются элементарные автоматы некоторого специального вида – автоматы с памятью, имеющие более одного состояния, и автоматы без памяти – с одним состоянием. Первые автоматы называются элементами памяти, вторые – комбинационные или логические элементы.
Теоретическим обоснованием канонического метода структурного синтеза автоматов служит теорема о структурной полноте:
Для правильной работы схем сигналы на входе запоминающих элементов не должны непосредственно участвовать в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. Поэтому запоминающими элементами должны быть не автоматы Мили, а автоматы Мура. Таким образом, структурно полная система элементарных автоматов должна содержать хотя бы один автомат Мура. В то же время, для синтеза автоматов с минимальным числом элементов памяти, необходимо в качестве таких элементов выбирать автоматы Мура, имеющие полную систему переходов и полную систему выходов – полные автоматы.
Полнота системы переходов
означает, что для любой упорядоченной пары состояний автомата найдётся входной сигнал, переводящий первый элемент этой пары во второй, т.е в таком автомате в каждом столбце таблицы переходов должны встречаться все состояния автомата.
Полнота системы выходов автомата Мура состоит в том, что каждому состоянию автомата поставлен в соответствие свой особый выходной сигнал, отличный от выходных сигналов других состояний. Т.о. в таком автомате число выходных сигналов равно числу состояний автомата. В связи с этим, в автоматах памяти будем использовать одни и те же обозначения и для состояний, и для выходных сигналов.
Канонический метод структурного синтеза предполагает представление структурной схемы автомата в виде двух частей: памяти и комбинационной схемы.
Память состоит из элементарных автоматов Мура П1,...., ПZ,...., ПR. После выбора элементов памяти каждое состояние синтезируемого автомата А кодируется набором их состояний. Если все автоматы П1..., ПR одинаковы, что в общем случае необязательно, то их число
<img width=«89» height=«25» src=«ref-1_118808706-313.coolpic» v:shapes="_x0000_i1144">
где M – число состояний синтезируемого автомата А, а b – число состояний элементарного автомата памяти. Обычно для элементарного автомата b=2, тогда <img width=«77» height=«23» src=«ref-1_118809019-290.coolpic» v:shapes="_x0000_i1145">.
Например, переход автомата А, имеющего 5 элементов памяти, алфавит состояний которых – двоичный, из одного состояния (Am)=01011 в другое (A3)= 11000, заключается в изменении состояний соответствующих автоматов памяти: первый элемент памяти переходит из 0 в 1, второй – из 1 в 1, третий из 0 в 0, четвёртый – из 1 в 0, пятый — из 1 в 0.
Переходы автоматов памяти, соответствующие переходам в автомате А, происходят под действием сигналов возбуждения памяти, поступающих с выхода комбинационной схемы на вход памяти автомата. Так на рисунке X=(X1,X2,..,XL) и Y=(Y1,Y2,...,YN) – векторные структурные входной и выходной сигналы автомата, U=(U1,U2,...,UT) – векторная функция возбуждения памяти и Q=(Q1,...,QT) – вектор выходного сигнала обратной связи от элементов памяти автомата.
Рассмотрим отдельно элемент памяти Пz, таблица переходов которого дана в таблице. Множество выходных сигналов элементов памяти совпадает с множеством внутренних состояний.
Полнота переходов очевидна из таблицы (в каждом столбце все состояния встречаются). При рассмотрении автомата на абстрактном уровне его можно представить в виде рис.22 а.
При переходе от абстрактного автомата к структурному, входные и выходные сигналы должны быть закодированы наборами сигналов структурного алфавита (входного или выходного соответственно). При двоичном структурном алфавите автомат Пz будет иметь два входных <img width=«76» height=«23» src=«ref-1_118811782-292.coolpic» v:shapes="_x0000_i1149"> и два выходных <img width=«76» height=«23» src=«ref-1_118811782-292.coolpic» v:shapes="_x0000_i1150"> канала.
Итак, сами компоненты Uz и Qzпри Z = 1,...,R векторов сигналов возбуждения памяти U и сигналов обратной связи от памяти Q также могут быть представлены в виде векторов:
Uz = (UZ1,UZ2,...,UZK) и QZ= (QZ1,QZ2,...,QZR).
Если не оговорено особо, то используется двоичный структурный алфавит как для входных и выходных каналов синтезируемого автомата, так и для входных и выходных каналов автоматов памяти. Алфавит состояний автоматов памяти также обычно двоичный.
При построении функций возбуждения памяти автомата используют продолжение
--PAGE_BREAK--функцию входов элемента памяти m(bi,bj), ставящую в соответствие каждой паре состояний (bi,bj) сигнал, который должен быть подан на вход этого автомата для перевода его из состояния bi в состояние bj. Функцию входов удобно задавать в виде таблицы. Для элемента памяти (функция переходов которого приведена ранее) функция входов имеет вид:
Если входные сигналы элемента памяти q1,...,qp закодированы наборами (UZ1,...,UZK) сигналов на его входных каналах, то элементами таблицы, задающей функцию входов вместо qi будут соответствующие наборы. Так, если q1 = 00, q2 = 01, q3 = 10, то соответствующая f входов будет иметь вид рис.23a.
Элементарные цифровые автоматы – элементы памяти.
В качестве элементов памяти структурного автомата обычно используются триггеры.
Триггер– это устройство, имеющее два устойчивых состояния, в которые он переходит под действием определённых входных сигналов.
Обычно в триггерах выделяют два вида входных сигналов (и соответственно входов): информационные и синхросигналы.
Информационные сигналы определяют новое состояние триггера и присутствуют в любых триггерах. По типу информационных сигналов осуществляется классификация триггеров: D, T, RS, JK, RST, DV и т.д.
Синхросигнал не является обязательным и вводится в триггерах с целью фиксации момента перехода триггера в новое состояние, задаваемое информационными входами. Обычно, при синтезе ЦА используются триггеры с синхровходом, поэтому в дальнейшем будем рассматривать только такие триггеры.
На синхровход триггера поступают тактирующие импульсы задающего генератора, синхронизирующего работу ЦА. Период следования импульсов соответствует одному такту автоматного времени ЦА.
Рассмотрим основные типы триггеров, используемые для синтеза ЦА: D, T, RS, JK.
D-триггер – элемент задержки – имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт.
Условное обозначение и таблица переходов D-триггера представлена на рис. .
<img width=«303» height=«62» src=«ref-1_118815307-503.coolpic» v:shapes="_x0000_s1275 _x0000_s1276 _x0000_s1277">
Из приведенной таблицы переходов для данного триггера Qt+1 = f(Qt,Dt) можно получить таблицу функций его входов Dt = j(Qt,Qt+1).
Q t
Qt+1
D
t
1
1
1
1
1
1
Как видно из таблицы, состояние, в которое переходит триггер (средний столбец), совпадает с поступившим на его вход сигналом D(t) (правый столбец). В связи с этим таблица функций возбуждения памяти синтезируемого автомата с использованием D-триггеров будет полностью совпадать с кодированной таблицей переходов этого автомата. Промышленность выпускает D-триггера в интегральном исполнении. Например,
K155TM2 (рис. 25).Таких триггеров два в одном корпусе. Вход С –вход синхронизации, Q,`
Q– выходы, Q
– прямой, <img width=«16» height=«25» src=«ref-1_118816585-209.coolpic» v:shapes="_x0000_i1153">
– инверсный. R
,
S
– входы установки в 0 и 1 соответственно. При подаче на вход R
и S
логического нуля триггер устанавливается в соответствующие состояния независимо от сигнала на входах D
и C
.
T
-триггер– триггер со счетным входом – имеет один информационный вход Т и один выход Q и осуществляет суммирование по модулю два значений сигнала T и состояния Q в заданный момент времени.
Условное обозначение и таблица переходов T-триггера представлена на рис 26.
T
Q t
Q
t
+1
1
1
1
1
1
1
Таблица функций входов триггера Tt = f(Qt, Qt+1) представлена в таблице.
Q t
Qt+1
T
t
1
1
1
1
1
1
На основании этой таблицы можно получать функцию возбуждения элементов памяти при синтезе автомата на базе T-триггера. Например, если автомат перешел из состояния ai = 010 в состояние aj = 110, то для обеспечения этого перехода функции возбуждения должны быть:
для первого триггера при переходе из 0 в 1 T1 = 1,
для второго триггера при переходе из 1 в 1 T2 = 0,
для третьего триггера при переходе из 0 в 0 T3 =0 и т.д.
В чистом виде промышленность не выпускает T-триггера.
продолжение
--PAGE_BREAK--RS
-триггер– триггер с раздельными входами.
Данный триггер имеет два входных канала R и S и один выходной Q. Вход S (set) называется входом установки в единицу, вход R (reset) – входом установки в нуль. Условное обозначение и таблица переходов RS-триггера представлена на рис. 27.
В таблице переходов при подаче комбинации S = R = 1 состояние перехода Qt+1 не определено и эта комбинация сигналов является запрещенной для RS-триггера.
Таблицу переходов можно более компактно изобразить в виде (см. табл. 21б) Анализируя табл.21 б, в отмечаем что, например, переход триггера из 0 в 0требует подачи комбинации R=0, S=0 или R=1,S=0, т.е. можно сказать что этот переход будет при R=X(безразличное состояние), S=0.
Аналогично рассуждая по отношению к другим переходам получим следующую таблицу функций входов.
R
S
Q t
Qt+1
R
S
Qt+1
1
1
1
1
1
1
1
1
1
1
1
1
–
1
б)
1
1
1
1
–
1
1
1
–
а)
<img width=«551» height=«381» src=«ref-1_118817304-3276.coolpic» v:shapes="_x0000_s1294 _x0000_s1295 _x0000_s1296 _x0000_s1297 _x0000_s1298 _x0000_s1299 _x0000_s1300 _x0000_s1301 _x0000_s1302 _x0000_s1303 _x0000_s1304 _x0000_s1305 _x0000_s1306 _x0000_s1307 _x0000_s1308 _x0000_s1309 _x0000_s1310 _x0000_s1311 _x0000_s1312">
Q
t
Qt+1
Rt
S
X
1
1
1
1
1
1
X
На основании таблицы можно получить функцию возбуждения памяти автомата при синтезе на базе RS-триггеров. Например, если автомат переходит из состояния ai= 010 в состояние aj=110, то для обеспечения такого перехода функции возбуждения должны быть:
для первого триггера при переходе из 0 в 1 R1 =0, S1 = 1;
для второго триггера при переходе из 1 в 1 R2 =0, S2 = X;
для третьего триггера при переходе из 0 в 0 R3 =X, S3= 0.
Аналогично для любого другого перехода автомата.
В чистом виде синхронный RS — триггер, используемый для синтеза ЦА, промышленностью не выпускается.
продолжение
--PAGE_BREAK--
JK- триггер –имеет два информационных входа J и K и один выход Q. Вход J – вход установки в 1, вход K – вход установки в 0, т.е. эти входы аналогичны соответствующим входам RS-триггера: J – соответствует S, K – соответствует R. Однако, в отличие от RS-триггера, входная комбинация J = 1, K= 1 не является запрещённой. Условное обозначение и таблица переходов JK-триггера представлены на рис.28. и в табл. 22.
J
K
Q t
Qt+1
J
K
Qt+1
Q t
1
1
1
1
1
1
1
1
1
1
Q t
1
1
б)
1
1
1
1
1
1
1
1
1
а)
<img width=«557» height=«221» src=«ref-1_118820580-2191.coolpic» v:shapes="_x0000_s1278 _x0000_s1279 _x0000_s1280 _x0000_s1281 _x0000_s1282 _x0000_s1283 _x0000_s1284 _x0000_s1285 _x0000_s1286 _x0000_s1287 _x0000_s1288 _x0000_s1289 _x0000_s1290 _x0000_s1291 _x0000_s1292 _x0000_s1293">
Как следует из таблиц переходов, для комбинаций входных сигналов JK = 00¸10 триггер ведет себя как RS-триггер, а при комбинации JK = 11 – как T-триггер.
Анализируя таблицу переходов ( табл. 22 а), отмечаем, что переход триггера, например, из 0 в 1 требует подачи входных сигналов J=1, K=0 или J=1, K=1, т.е. J=1, K=Х (безразличное значение). Аналогично рассуждая по отношению к другим переходам, получим следующую таблицу функций входов JK-триггера.
Q t
Qt+1
J
K
X
1
1
X
1
X
1
1
1
X
На основании последней таблицы можно получить функцию возбуждения элементов памяти при синтезе автомата на JK-триггерах. Например, при переходе автомата из состояния ai=010 в состояние aj=110, функции возбуждения должны быть:
для первого триггера при переходе из 0 в 1 J1 = 1, K1 = X;
для второго триггера при переходе из 1 в 1 J2 = X, K2 = 0;
для третьего триггера при переходе из 0 в 0 J3 = 0, K3 = X.
продолжение
--PAGE_BREAK--Пример канонического метода структурного синтеза автомата.
Выполним структурный синтез частичного автомата А, заданного своими таблицами переходов и выходов (табл. 23 и 24.).
Синтез будем выполнять в следующем порядке:
1.Выберем в качестве элементов памяти D-триггер, функция входов которого представлена в таблице стр. 33.
2.Закодируем входные, выходные сигналы и внутренние состояния автомата. Количество входных абстрактных сигналов F = 3, следовательно количество входных структурных сигналов L= ]log2F [ = ]log23[ = 2, т.е. х1, х2.
Количество выходных абстрактных сигналов G = 4, следовательно количество выходных структурных сигналов N =]log2G[ = ]log24[ = 2, т.е. у1, у2. Количество внутренних состояний абстрактного автомата M = 4, следовательно количество двоичных элементов памяти (триггеров) R = ] log2M [ = ]log24[ = 2.
Следовательно, структура ЦА с учетом того, что исходный автомат является автоматом Мили, в качестве элементов памяти используется D-триггер, может быть представлена в виде(рис. 29):
Кодирование входных, выходных сигналов и внутренних состояний представлена в таблицах:
x1
x2
y1
y2
Q1
Q2
z1
w1
a1
z2
1
w2
1
a2
1
z3
1
1
w3
1
1
a3
1
1
w4
1
a4
1
Кодирование, в общем случае, осуществляется произвольно. Поэтому, например, каждому из сигналов Zi можно поставить в соответствие любую двухразрядную комбинацию х1, х2. Необходимо только, чтобы разные выходные сигналы Zi кодировались разными комбинациями х1, х2. Аналогично для Wi и a
i.
3. Получим кодированные таблицы переходов и выходов структурного автомата. Для этого в таблицах переходов и выходов исходного абстрактного автомата вместо Zi, Wi, ai cтавим соответствующие коды. Получим таблицы:
<img width=«600» height=«222» src=«ref-1_118825597-2419.coolpic» v:shapes="_x0000_s1264 _x0000_s1265 _x0000_s1266 _x0000_s1267 _x0000_s1268 _x0000_s1269 _x0000_s1270 _x0000_s1271 _x0000_s1272 _x0000_s1273">
a1
a2
a3
a4
a1
a2
a3
a4
00
01
11
10
00
01
11
10
Z1
00
00
10
10
–
Z1
00
01
00
11
–
Z2
01
–
11
00
–
Z2
01
–
11
00
–
Z3
11
01
–
01
Q1Q2
Z3
11
00
–
10
y1y2
В кодированной таблице переходов заданы функции <img width=«157» height=«24» src=«ref-1_118828016-413.coolpic» v:shapes="_x0000_i1158">
<img width=«176» height=«24» src=«ref-1_118828429-397.coolpic» v:shapes="_x0000_i1159">
В кодированной таблице выходов заданны функции:
<img width=«344» height=«24» src=«ref-1_118828826-574.coolpic» v:shapes="_x0000_i1160">
продолжение
--PAGE_BREAK--4. При каноническом методе синтез сводится к получению функций:
<img width=«224» height=«96» src=«ref-1_118829400-816.coolpic» v:shapes="_x0000_i1161">
и последующем построении комбинационных схем, реализующих данную систему булевых функций.
Функции у1 и у2 могут быть непосредственно получены из таблицы выходов, например, в виде :
<img width=«312» height=«51» src=«ref-1_118830216-887.coolpic» v:shapes="_x0000_i1162">
Однако выражения для у1 и у2 можно существенно упростить в результате минимизации, например, с помощью карт Карно:
00
01
11
10
00
01
11
<img width=«595» height=«259» src=«ref-1_118831103-6680.coolpic» v:shapes="_x0000_s1135 _x0000_s1136 _x0000_s1137 _x0000_s1138 _x0000_s1139 _x0000_s1140 _x0000_s1141 _x0000_s1142 _x0000_s1143 _x0000_s1144 _x0000_s1145 _x0000_s1146 _x0000_s1147 _x0000_s1148 _x0000_s1149 _x0000_s1150 _x0000_s1151 _x0000_s1152 _x0000_s1153 _x0000_s1154 _x0000_s1155 _x0000_s1156 _x0000_s1157 _x0000_s1158 _x0000_s1159">
В результате минимизации имеем:
<img width=«277» height=«51» src=«ref-1_118837783-748.coolpic» v:shapes="_x0000_i1163">
Для получения выражений для D1 и D2 необходимо получить таблицы функций возбуждения. Для чего в общем случае необходимо воспользоваться таблицей переходов и функциями входов элементов памяти. Зная код исходного состояния автомата и код
состояния перехода на основании таблицы входов триггера получаем требуемое значение функции возбуждения, обеспечивающее заданный переход. Однако для D-триггеров, как отмечалось ранее, таблица переходов совпадает с таблицей функции возбуждения. Тогда либо непосредственно из этой таблицы, либо в результате минимизации получаем требуемые значения Di. Обычно используется минимизация с помощью карт Карно:
<img width=«600» height=«261» src=«ref-1_118838531-5465.coolpic» v:shapes="_x0000_s1217 _x0000_s1218 _x0000_s1219 _x0000_s1220 _x0000_s1221 _x0000_s1222 _x0000_s1223 _x0000_s1224 _x0000_s1225 _x0000_s1226 _x0000_s1227 _x0000_s1228 _x0000_s1229 _x0000_s1230 _x0000_s1231 _x0000_s1232 _x0000_s1233 _x0000_s1234 _x0000_s1235">
00
01
11
10
00
01
11
10
00
1
1
–
00
–
01
–
1
–
01
–
1
–
11
–
1
11
1
–
1
1
10
–
–
–
–
10
–
–
–
–
В результате минимизации получаем:
<img width=«281» height=«53» src=«ref-1_118843996-618.coolpic» v:shapes="_x0000_i1164">
продолжение
--PAGE_BREAK--5. На основании полученных в результате синтеза булевых выражений ((*), (**)), строим функциональную схему автомата. Для этого уравнения ((*), (**)) представим в виде:
<img width=«231» height=«128» src=«ref-1_118844614-984.coolpic» v:shapes="_x0000_i1165">
Функциональная схема автомата представлена на странице 41:
Дополнительно на функциональной схеме показан сигнал <img width=«43» height=«25» src=«ref-1_118845598-240.coolpic» v:shapes="_x0000_i1166">, устанавливающий автомат в начальное состояние (в данном случае 00).
--PAGE_BREAK--
RS
-
триггер
.
Q t
Qt+1
R
S
X
1
1
1
1
1
1
X
<img width=«426» height=«256» src=«ref-1_118856294-2331.coolpic» v:shapes="_x0000_s1129 _x0000_s1130 _x0000_s1131 _x0000_s1132 _x0000_s1133 _x0000_s1134">
00
01
11
10
R1
S1
R2
S2
R1
S1
R2
S2
R1
S1
R2
S2
R1
S1
R2
S2
00
X
X
1
1
X
1
–
–
01
–
–
1
X
1
1
–
–
11
X
1
–
–
1
X
X
1
<img width=«538» height=«479» src=«ref-1_118858625-5712.coolpic» v:shapes="_x0000_s1160 _x0000_s1161 _x0000_s1162 _x0000_s1163 _x0000_s1164 _x0000_s1165 _x0000_s1166 _x0000_s1167 _x0000_s1168 _x0000_s1169 _x0000_s1170 _x0000_s1171 _x0000_s1172 _x0000_s1173 _x0000_s1174 _x0000_s1175 _x0000_s1176 _x0000_s1177 _x0000_s1178 _x0000_s1179 _x0000_s1180 _x0000_s1181 _x0000_s1182"> продолжение
--PAGE_BREAK--
00
01
11
10
00
01
11
10
00
X
–
00
1
X
–
01
–
1
–
01
–
1
–
11
X
–
1
11
–
X
10
–
–
–
–
10
–
–
–
–
<img width=«595» height=«53» src=«ref-1_118864337-545.coolpic» v:shapes="_x0000_i1170">
00
01
11
10
00
01
11
10
00
X
1
1
–
00
–
01
–
1
–
01
–
X
–
11
–
11
1
–
X
1
10
–
–
–
–
10
–
–
–
–
<img width=«595» height=«53» src=«ref-1_118864882-532.coolpic» v:shapes="_x0000_i1171">
<img width=«95» height=«96» src=«ref-1_118865414-571.coolpic» v:shapes="_x0000_i1172">
продолжение
--PAGE_BREAK--JK
-
триггер
.
Q t
Qt+1
J
K
X
1
1
X
1
X
1
1
1
X
00
01
11
10
J1
K1
J2
K2
J1
K1
J2
K2
J1
K1
J2
K2
J1
K1
J2
K2
00
X
X
1
X
X
1
X
X
1
–
–
01
–
–
1
X
X
X
1
X
1
–
–
11
X
1
X
–
–
X
1
X
X
1
X
00
01
11
10
00
01
11
10
00
1
X
–
00
X
X
–
01
–
1
X
–
01
–
X
1
–
11
–
X
X
11
X
–
1
10
–
–
–
–
10
–
–
–
–
00
01
11
10
00
01
11
10
00
X
X
–
00
X
1
1
–
01
–
X
X
–
01
–
1
–
11
X
–
1
11
–
X
10
–
–
–
–
10
–
–
–
–
<img width=«629» height=«271» src=«ref-1_118865985-3871.coolpic» v:shapes="_x0000_s1200 _x0000_s1201 _x0000_s1202 _x0000_s1203 _x0000_s1204 _x0000_s1205 _x0000_s1206 _x0000_s1207 _x0000_s1208 _x0000_s1209 _x0000_s1210 _x0000_s1211 _x0000_s1212 _x0000_s1213 _x0000_s1214 _x0000_s1215 _x0000_s1216"> продолжение
--PAGE_BREAK--
<img width=«92» height=«96» src=«ref-1_118869856-520.coolpic» v:shapes="_x0000_i1173">
Функциональные схемы автоматов с различными типами триггеров предлагается построить самостоятельно.
Кодирование внутренних состояний ЦА.
Гонки в автомате.
Кодирование заключается в сопоставлении каждому состоянию автомата набора (кода) состояний элементов памяти. При этом наборы для всех состояний должны иметь одинаковую длину, а разным состояниям автомата должны соответствовать разные наборы. Если элементы памяти двоичные, то их число <img width=«91» height=«27» src=«ref-1_118870376-312.coolpic» v:shapes="_x0000_i1174">.
<img width=«7» height=«79» src=«ref-1_118870688-181.coolpic» v:shapes="_x0000_s1321">Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Если автомат переходит из состояния с кодом 010 в состояние с кодом 100, то это означает, что триггер V1 переходит из состояния 0 в состояние 1, V2 – из 1 в 0, V3 – сохраняет свое состояние.
<img width=«7» height=«86» src=«ref-1_118870869-185.coolpic» v:shapes="_x0000_s1322">При функционировании автомата могут появиться так называемые состязания. Это явление возникает вследствие того, что элементы памяти имеют различные, хотя и достаточно близкие, времена срабатывания. Различны также задержки сигналов возбуждения, поступающих на входные каналы элементарных автоматов по логическим цепям неодинаковой длины.
Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания. Тот элемент, который выиграет эти состязания, т.е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие, участвующие в состязаниях элементы, изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное его графом. Поэтому в процессе перехода из состояния amв состояние asпод действием входного сигнала Zf автомат может оказаться в состоянии akили al: (рис.36.).
Если затем при том же входном сигнале Zf автомат из аk и аlперейдет в аs, то такие состязания являются допустимыми или некритическими.
Если же в этом автомате есть переход, например, из аk в аj¹аsпод действием того же сигнала Zf, то автомат может перейти в аj, а не в аs и правильность его работы будет нарушена (рис.37.).
Такие состязания называются критическими состязаниями или гонками и необходимо принимать меры для их устранения.
Устранить гонки можно аппаратными средствами либо используя специальные методы кодирования. Один из способов ликвидации гонок состоит в тактировании входных сигналов автомата импульсами определенной длительности. Предполагается, что кроме входных каналов х1, ..., хl имеется еще канал С от генератора синхроимпульсов, по которому поступает сигнал С = 1 в момент прихода импульса и С = 0 при его отсутствии. В связи с этим входным сигналом на переходе (am, as) будет не Zf, а CZf. Тогда, если длительность импульса tc меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационной схеме, то к моменту перехода в промежуточное состояние akсигнал C = 0, CZf=0, что исключает гонки. Канал С – это фактически синхровход триггера. Недостаток метода – в трудности подбора требуемой длительности импульса, т.к. она зависит от многих факторов, не поддающихся строгому учету.
Другой способ ликвидации гонок заключается во введении двойной памяти. В этом случае каждый элемент памяти дублируется, причем перепись из первого элемента памяти во второй происходит в момент С = 0(рис.38.).
Сигналы обратной связи для получения функций возбуждения и функций выходов автомата снимаются с выхода второго триггера. Таким образом состязания могут возникнуть только между первыми триггерами, сигналы ОС (выходы вторых триггеров) не могут измениться до тех пор, пока С не станет равным 0. Но тогда CZf = 0, первый триггер перестанет воспринимать информацию, и гонок не будет.
Для устранения гонок используются специальные методы противогоночного кодирования, среди которых чаще всего применяется так называемое соседнее кодирование состояний автомата, при котором условие отсутствия гонок всегда выполнено. При соседнем кодировании любые два, состояния связанные дугой на графе автомата кодируются наборами, отличающимися состояниями лишь одного элемента памяти.
Соседнее кодирование не всегда возможно. Граф автомата, допускающее соседнее кодирование, должен удовлетворять ряду требований, а именно:
1) в графе автомата не должно быть циклов с нечетным числом вершин;
2) два соседних состояния второго порядка не должны иметь более двух состояний, лежащих между ними.
Под состояниями второго порядка понимаются такие два состояния, путь между которыми по графу автомата состоит из двух ребер (независимо от ориентации). Примеры графов автоматов допускающих и не допускающих соседнее кодирование представлены на рис.39а. и 39б. соответственно.
При соседнем кодировании обычно пользуются картой Карно. В этом случае состояния, связанные дугой, располагают на соседних клетках карты (рис.40.).
Легко видеть, что при соседнем кодировании на каждом переходе переключается только один триггер, что принципиально устраняет гонки.
Кодирование состояний и сложность комбинационной схемы автомата.
Анализ канонического метода структурного синтеза автомата показывает, что различные варианты кодирования состояний автомата приводят к различным выражениям функций возбуждения памяти и функций выходов, в результате чего сложность комбинационной схемы существенно зависит от выбранного кодирования. Среди множества существующих алгоритмов кодирования рассмотрим лишь два наиболее часто встречаемых:
1) алгоритм кодирования для D-триггеров;
2) эвристический алгоритм кодирования.
Алгоритм кодирования для D
-триггеров.
Согласно рассматриваемому алгоритму при кодировании необходимо выполнить следующее:
1. Каждому состоянию автомата аm (m = 1,2,...,M) ставится в соответствие целое число Nm, равное числу переходов в состояние аm (Nm равно числу появлений аm в поле таблицы переходов или числу дуг, входящих в аm при графическом способе задания автомата).
2. Числа N1, N2, ..., Nm упорядочиваются по убыванию.
3. Состояние аs с наибольшим Ns кодируется кодом:<img width=«45» height=«30» src=«ref-1_118880996-227.coolpic» v:shapes="_x0000_i1180">, где R-количество элементов памяти.
4. Следующие R состояний согласно списка пункта 2 кодируются кодами, содержащими только одну 1: 00… 01, 00… 10, …, 01… 00, 10… 00.
5. Для оставшихся состояний опять в порядке списка п.2. используют коды с двумя единицами, затем с тремя и так далее пока не будут закодированы все состояния.
В результате получается такое кодирование, при котором чем больше имеется переходов в некоторое состояние, тем меньше единиц в его коде. Т.к. для D-триггеров функции возбуждения однозначно определяются кодом состояния перехода, то очевидно, что выражения для функций возбуждения будут проще. Этот метод особенно эффективен при отсутствии минимизации функций возбуждения, что имеет место в реальных автоматах с большим количеством внутренних состояний и входных переменных.
В частности, для автомата, заданного своими таблицами переходов и выходов (см. ниже) при кодировании на базе D-триггеров.
a1
a2
a3
a4
a5
a1
a2
a3
a4
a5
Z1
a1
a1
a5
a3
a1
Z1
w1
w2
w1
w1
w1
Z2
a2
a3
a2
a3
a3
Z2
w1
w3
w4
w2
w2
Z3
a3
a4
a2
a4
a2
Z3
w2
w2
w2
w1
w3
a1 ~ N1 = 3 N3 a3 = 000
a2 ~ N2 = 4 N2 a2 = 001
a3 ~ N3 = 5 N1 a1 = 010
a4 ~ N4 = 5 N4 a4 = 100
a5 ~ N5 = 1 N5 a5 = 011
Аналогично кодированию внутренних состояний для D-триггеров можно кодировать выходные сигналы для любого типа триггеров, т.е. чем чаще вырабатывается данный выходной сигнал wi, тем меньше единиц в его коде. Так для автомата (рис.41.) имеем:
w1 ~ N1 = 6 N1 w1 = 00
w2 ~ N2 = 5 N2 w2 = 01
w3 ~ N3 = 2 N3 w3 = 10
w4 ~ N4 = 2 N4 w4 = 11
Предполагается самостоятельно окончить синтез автомата при данном кодировании и при любом другом. Результаты сравнить.
продолжение
--PAGE_BREAK--Эвристический алгоритм кодирования.
Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе T, RS, JK-триггеров. Для данных типов триггеров (в отличие от D-триггеров!) на каждом переходе, где триггер меняет свое значение на противоположное, одна из функций возбуждения обязательно равна 1. Уменьшение числа переключений триггеров приводит к уменьшению количества единиц соответствующих функций возбуждения, что при отсутствии минимизации однозначно приводит к упрощению комбинационной схемы автомата.
Введем некоторые определения.
Пусть Г(S) – неориентированный граф переходов автомата S. Вершины графа отождествляются с состояниями автомата. Вершины i и j соединены ребром, если есть переход из аi и аj или наоборот.
Обозначим q(i, j) число всевозможных переходов автомата из аi в аj. Каждому ребру (i, j) графа Г(S) поставим в соответствие вес ребра р(i, j) = q(i, j)+ q(j, i).
Введем функцию w(i,
j) = р(i, j)×
d(i, j), где d(i, j) – число компонентов, которыми коды состояний аi в аj отличаются друг от друга (т.е. кодовое расстояние между кодами аi в аj).
Функция w(i ,j) имеет простой физический смысл. Перход автомата из аi в аj (или наоборот) сопровождается переключением стольких триггеров, сколькими компонентами отличаются коды этих состояний, т.е. их число равно w(i ,j). Следовательно, при переходе автомата по всем ребрам, соединяющим состояниям аi и аj (их число p(i, j)!) всего переключится количество триггеров, равное p(i, j)×d(i ,j) =w(i ,j).
Но тогда функция <img width=«241» height=«37» src=«ref-1_118881983-593.coolpic» v:shapes="_x0000_i1182">показывает, сколько всего переключается триггеров при прохождении автомата по всем возможным переходам. Функция wпоказывает, сколько всего единиц в функции возбуждения, т.е. позволяет оценивать сложность комбинационной схемы автомата. Wможно рассматривать как некую целевую функцию, минимум которой определит такое кодирование, при котором комбинационная схема наиболее простая. Кстати, миинмальное кодовое расстояние между различными состояниями равно 1 и если удается закодировать все состояния соседним кодированием, то очевидно, что wбудет минимально возможным и равным <img width=«103» height=«37» src=«ref-1_118882576-372.coolpic» v:shapes="_x0000_i1183">, т.е. суммарному числу переходов для автомата.
Из выражения для wследует, что переход из аi в аi, для которого d(i,i)=0, не влияет на w(что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).
Рассмотрим применение эвристического алгоритма на конкретном примере автомата, заданного таблицами переходов и выходов (рис.41. ). Для данного автомата можно построить ориентированный граф (без учета петель), представленный на рис.42. На каждом ребре указан его вес.
Эвристический алгоритм состоит из следующих шагов.
1. Строим матрицу <img width=«24» height=«21» src=«ref-1_118884716-201.coolpic» v:shapes="_x0000_i1185">, состоящую из всех пар номеров (i, j), для которых р(i, j) ¹0 (т.е. в автомате есть переход из аi в аj или наоборот) и i<j. Для каждой пары в матрице <img width=«24» height=«21» src=«ref-1_118884716-201.coolpic» v:shapes="_x0000_i1186"> указываем ее вес р(i, j), совпадающий с весом ребра соединяющего аi и аj.
i
j
p(i,j)
1
2
2
1
3
1
T
=
1
5
1
2
3
3
2
4
1
2
5
1
3
4
2
3
5
2
2. Упорядочим строки матрицы <img width=«24» height=«21» src=«ref-1_118884716-201.coolpic» v:shapes="_x0000_i1188">, для чего построим матрицу <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1189"> следующим образом. В первую строку матрицы <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1190"> поместим пару (a,
b) с наибольшим весом р(a,
b). В нашем случае (a,
b) = (2,3), р(2,3) = 3. Из всех пар, имеющих общий компонент с парой (a,
b) выбирается пара (g,
d) с наибольшим весом и заносится во вторую строку матрицы <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1191">. Ясно, что {a,
b}×{g,
d}¹0. Затем из всех пар, имеющих общий компонент хотя бы с одной из внесенных уже в матрицу <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1192"> пар выбирается пара с наибольшим весом и заносится в матрицу <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1193"> и т.д.. В случае равенства весов пар вычисляются суммы весов компонентов пар (весом р(a) компонента aназывается число появлений aв матрице <img width=«24» height=«21» src=«ref-1_118884716-201.coolpic» v:shapes="_x0000_i1194">) и в матрицу <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1195"> заносится пара с наибольшей суммой весов. В рассматриваемом автомате на второе место вслед за парой (2,3) претендуют пары: (1,2) с р(1,2) = 2; (3,4) с р(3,4) = 2, (3,5) с р(3,5) = 2.
Для определения того, какая пара займет второе место в матрице <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1196"> находим веса компонентов пар:
р(1) = 3 р(2) = 3 р(1) + р(2) = 6
р(3) = 4 р(4) = 2 р(3) + р(4) = 6
р(3) = 4 р(5) = 2 р(3) + р(5) = 6
В данном случае для всех пар совпадают и их веса и веса их компонентов. Поэтому на второе место матрицы <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1197"> может быть поставлена любая из пар (1,2), (3,4), (3,5). Но тогда на 3-м и 4-м будут остальные две. Выполнив упорядочивание всех пар, получим матрицу <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1198"> в виде:
i
j
p(i,j)
2
3
3
1
2
2
M
=
3
4
2
3
5
2
1
3
1
1
5
1
2
4
1
2
5
1
продолжение
--PAGE_BREAK--3.Определяем разрядность кода для кодирования состояний автомата (количество элементов памяти – триггеров). Всего состояний M=5. Тогда
R = ]log2M[ = ]log25[ =3.
Закодируем состояния из первой строки матрицы следующим образом: K2 = K(а2) = 000; K3 = K(а3) = 001.
Для удобства кодирования будем иллюстрировать этот процесс картой Карно:
4. Вычеркнем из матрицы <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1200"> первую строку, соответствующую закодированным состояниям а2 и а3. Получим матрицу <img width=«29» height=«21» src=«ref-1_118885319-213.coolpic» v:shapes="_x0000_i1201">.
i
j
p(i,j)
1
2
2
3
4
2
M’
=
3
5
2
1
3
1
1
5
1
2
4
1
2
5
1
5. В силу упорядочивания п.2 в первой строке закодирован ровно один элемент. Выберем из первой строки незакодированный элемент и обозначим его g. (В нашем случае g= 1).
6. Строим матрицу <img width=«39» height=«32» src=«ref-1_118888366-226.coolpic» v:shapes="_x0000_i1202">, выбрав из <img width=«36» height=«21» src=«ref-1_118888592-219.coolpic» v:shapes="_x0000_i1203"> строчки, содержащие g.
i
j
p(i,j)
1
2
2
Mg
=
M’
=
1
3
1
1
5
1
Пусть Bg = {g1,...,g
F} – множество элементов из матрицы <img width=«39» height=«32» src=«ref-1_118888366-226.coolpic» v:shapes="_x0000_i1204">, которые уже закодированы. Их коды Кg1,..., Kg
F соответственно. В нашем случае:
B
g= B3 = {2,3} K2 = 000 K3 = 001.
7. Для каждого Kg
f(f=1, ..., F) найдем <img width=«36» height=«36» src=«ref-1_118889037-242.coolpic» v:shapes="_x0000_i1205">– множество кодов, соседних с <img width=«31» height=«27» src=«ref-1_118889279-232.coolpic» v:shapes="_x0000_i1206"> и еще не занятых для кодирования состояний автомата. (Для соседних кодов кодовое расстояние d=1).
K2 = 000 <img width=«23» height=«27» src=«ref-1_118889511-225.coolpic» v:shapes="_x0000_i1207"> = {100, 010}
K3 = 001 <img width=«23» height=«27» src=«ref-1_118889736-219.coolpic» v:shapes="_x0000_i1208"> = {011, 101}.
Построим множество <img width=«217» height=«48» src=«ref-1_118889955-504.coolpic» v:shapes="_x0000_i1187">
<img width=«227» height=«27» src=«ref-1_118890459-431.coolpic» v:shapes="_x0000_i1209">
Если оказывается, что <img width=«56» height=«29» src=«ref-1_118890890-257.coolpic» v:shapes="_x0000_i1210">, то строим новое множество <img width=«91» height=«53» src=«ref-1_118891147-372.coolpic» v:shapes="_x0000_i1211">, где <img width=«29» height=«33» src=«ref-1_118891519-238.coolpic» v:shapes="_x0000_i1212">– множество кодов, у которых кодовое расстояние до кода <img width=«31» height=«27» src=«ref-1_118889279-232.coolpic» v:shapes="_x0000_i1213">равно 2 и т.д..
8. Для каждого кода из множества Dg находим кодовое расстояние до кода <img width=«31» height=«27» src=«ref-1_118889279-232.coolpic» v:shapes="_x0000_i1214">.
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.
<img width=«417» height=«95» src=«ref-1_118892221-1553.coolpic» v:shapes="_x0000_i1215">
10. Из множества Dg выбираем код Kg, у которого получилось минимальное значение wв п.9. Выбираем код для состояния a1 К1 =100.
11. Из матрицы <img width=«36» height=«21» src=«ref-1_118888592-219.coolpic» v:shapes="_x0000_i1217"> вычеркиваем строки, в которых оба элемента уже закодированы, в результате чего получим новую матрицу <img width=«36» height=«21» src=«ref-1_118888592-219.coolpic» v:shapes="_x0000_i1218">. Если в новой матрице <img width=«36» height=«21» src=«ref-1_118888592-219.coolpic» v:shapes="_x0000_i1219"> не осталось ни одной строки, то кодирование закончено. В противном случае возвращаемся к п.5. В нашем случае имеем:
i
j
p(i,j)
3
4
2
3
5
2
M’
=
1
5
1
2
4
1
2
5
1
<img width=«433» height=«52» src=«ref-1_118894951-640.coolpic» v:shapes="_x0000_i1220">
К2= 000 <img width=«23» height=«27» src=«ref-1_118889511-225.coolpic» v:shapes="_x0000_i1221"> = {010}
K3= 001 <img width=«21» height=«27» src=«ref-1_118895816-223.coolpic» v:shapes="_x0000_i1222"> = {011, 101}
<img width=«201» height=«27» src=«ref-1_118896039-413.coolpic» v:shapes="_x0000_i1223">
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
<img width=«416» height=«69» src=«ref-1_118896452-1351.coolpic» v:shapes="_x0000_i1224">
Выбираем К4 = 101.
<img width=«513» height=«79» src=«ref-1_118898342-878.coolpic» v:shapes="_x0000_i1226">
К1 = 100 <img width=«21» height=«27» src=«ref-1_118899220-219.coolpic» v:shapes="_x0000_i1228"> = {110}
K2 = 000 <img width=«21» height=«27» src=«ref-1_118899439-225.coolpic» v:shapes="_x0000_i1229"> = {010}
К3 = 001 <img width=«21» height=«27» src=«ref-1_118895816-223.coolpic» v:shapes="_x0000_i1230"> = {011}
<img width=«233» height=«27» src=«ref-1_118899887-451.coolpic» v:shapes="_x0000_i1231">
К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
<img width=«596» height=«69» src=«ref-1_118900338-1583.coolpic» v:shapes="_x0000_i1232">
Выбираем К5 = 011.
Т.к. все состояния автомата закодированы, то работа алгоритма заканчивается. Общее количество переключений триггеров:
<img width=«577» height=«71» src=«ref-1_118902489-1540.coolpic» v:shapes="_x0000_i1234">
Минимально возможное количество переключений (если бы состояния были закодированы соседним кодированием)
<img width=«144» height=«27» src=«ref-1_118904029-368.coolpic» v:shapes="_x0000_i1235">
Коэффициент эффективности кодирования:
<img width=«159» height=«45» src=«ref-1_118904397-420.coolpic» v:shapes="_x0000_i1236">
Рассмотренный алгоритм кодирования является машино-ориентированным, существуют программы, реализующие этот алгоритм.
Необходимо отметить в заключении, что использование алгоритма кодирования для 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}, вводимых в автомат в качестве операндов;
2) множеством выходных слов R={r1,...,rQ}, представляющих результаты операций;
3) множеством внутренних слов S={s1,...,sN}, используемых для представления информации в процессе выполнения операций. Можно считать, что входные и выходные слова совпадают с определенными внутренними DÍS, RÍS.
4) множеством микроопераций Y={ym}, реализующих преобразование S=jm(s) над словами информации, где jm– вычисляемая функция;
5) множеством логических условий X={xi}, где xi=y
i(si) и y
i– булева функция;
T.o. функция ОА задана, если заданы (определены) множества D, R, S, Y, X. Время не является аргументом функции ОА. Функция устанавливает список действий-микроопераций и логических условий, которые может выполнять автомат, но никак не определяет порядок следования этих действий во времени. Т.е. функция ОА характеризует средства, которые могут быть использованы для вычислений, но не сам вычислительный процесс.
Порядок выполнения действий во времени определяется в форме функций управляющего автомата.
Функция управляющего автомата – это операторная схема алгоритма ( микропрограммы), функциональными операторами которой являются символы у1,...,уm, отождествляемые с микрооперациями, и в качестве логических условий используются булевы переменные х1,...,хL. Операторная схема алгоритма наиболее часто представляется в виде граф-схемы алгоритма (ГСА). ГСА определяет вычислительный процесс последовательно во времени, устанавливая порядок проверки логических условий х1-хL и порядок следования микроопераций у1-уm.
--PAGE_BREAK--ОПЕРАЦИОННЫЕ ЭЛЕМЕНТЫ
Согласно принципа микропрограммного управления, любая сложная операция распадается на ряд микроопераций, которые выполняются ОА. Различные микрооперации выполняются элементарными ОА — так называемыми операционными элементами (ОЭ), которые являются составными частями основного ОА.
Под операционным элементом понимают устройство, реализующее одну из следующих функций или их произвольную комбинацию:
· хранение слова информации С;
· выполнение некоторых микроопераций, в результате которых вычисляется новое значение слова С;
· вычисления логического условия, зависящего от слова С;
Т.о. функция ОЭ определена, если заданы:
· описание хранимого или вычисляемого слова;
· описание множества микроопераций, выполняемых этим элементом;
· описание вычисляемых этим элементом логических условий.
Для построения ОА ОЭ соединяются между собой с помощью цепей передачи слов информации от выходов одних элементов к входам других.
В зависимости от выполняемых микроопераций ОЭ делятся на разновидности: шина, регистр, счетчик, сумматор, схема сравнения, дешифратор, шифратор и т.д.
Шина — это совокупность цепей, предназначенных для передачи слова информации. Условное обозначение шины представлено на рис.45.
Шины, изображенные на рис.45 называются неуправляемыми шинами.
Управляемые шины представлены на рис.46.
Под действием управляющего сигнала у управляемая шина выполняет микрооперации: у=0: B(0:3):=0 , y=1: B(0:3):=A(0:3)
Т.е. при y=1 осуществляется операция передачи. Разрядность шины может быть произвольная, но обычно это 8, 12, 16, 24, 32 и т.д.
Регистр — это операционный элемент, служащий для запоминания слов и обеспечивающий в общем случае выполнение следующих микроопераций:
· установка регистра в 0 (сброс);
· прием слова из другого регистра, шины и т.д.;
· передача слова на другой регистр, шину и т.д.;
· преобразование кодов хранимых слов в инверсные коды;
· сдвиг хранимого слова влево или вправо на требуемое число разрядов.
Регистр, выполняющий такие микрооперации, называется многофункциональным. Т.к. регистр предназначен для хранения информации, то он содержит элементы памяти, в качестве которых используются триггеры. Количество триггеров определяет разрядность регистра. Будем обозначать регистр в виде прямоугольника с указанием разрядности (рис.47 ).
Регистр может состоять из отдельных подрегистров, имеющих самостоятельное значение (рис.48.). На рис.48 представлен регистр, хранящий число в форме с плавающей запятой. В этом регистре три подрегистра: для хранения знака Рг(0), характеристики Рг(1:7), мантиссы Рг(8:31) числа.
Регистр может выполнять ряд микроопераций, например:
Регистр, который выполняет микрооперацию у4 (сдвиг вправо) или у5 (сдвиг влево) называются регистром сдвига.
Сумматор — операционный элемент, выполняющий суммирование кодов чисел. В зависимости от кодов чисел различают сумматоры прямого, обратного, дополнительного кодов. Кроме того, сумматоры бывают комбинационными и накапливающими.
Комбинационный сумматор вырабатывает выходные сигналы суммы и переноса, определяемые комбинацией цифр слагаемых, одновременно поданных на входы сумматора. Данный сумматор не обладает памятью и после снятия сигналов с входов выходные сигналы также исчезают.
Условное обозначение комбинационного сумматора представлено на рис.50.
Накапливающим называется сумматор, который осуществляет сложение слов A и B при подаче их на сумматор одного за другим. В накапливающем сумматоре имеется дополнительный регистр для хранения результата.
Структура и условное обозначение накапливающего сумматора представлены на рис. 51.
Счетчик— операционный элемент, который реализует микрооперацию счета. Микрооперация счета состоит в изменении состояния счетчика (значения хранимого слова) на 1. Кроме того счетчик может выполнить и такие микрооперации: установка в 0 и прием произвольного числа.
Т.е. полный набор возможных микроопераций для счетчика:
Счетчик, выполняющий микрооперацию у1 называется суммирующим, микрооперацию у2 — вычитающим, обе микрооперации — реверсивный.
Дешифратор — операционный элемент, выполняющий функцию преобразования некоторого n-разрядного двоичного кода в унитарный код «один из N». Если N=2n— то такой дешифратор называется полным, если N<2n— то частичным. Таблица истинности простейшего полного дешифратора (n=2) и его условное обозначение приведены в табл. 25. и на рис. 53.
Промышленность может выпускать дешифраторы с инверсными выходами. Для такого дешифратора таблица истинности и условное обозначение имеют вид (табл. 26., рис. 54.)
СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ ПО ГРАФ-СХЕМЕ АЛГОРИТМА
Граф-схема алгоритма есть форма представления микропрограммы, которую должно выполнить операционное устройство (ОУ). При построении операционного устройства, как состоящего из операционного (ОА) и управляющего (УА) автоматов, необходимо уметь выделить функции ОА и УА из ГСА. Обычно микропрограмма представляется в виде содержательной ГСА. В этом случае для задания функций ОА необходимо перечислить все выполняемые микрооперации и все проверяемые логические условия данной микропрограммы, а также описать разрядность слов, обрабатываемых операционным устройством. На основании этих данных можно построить ОА методами, которые будут изложены в курсе «Схемотехника ЭВМ». Для инициализации выполнения той или иной микрооперации на ОА должны поступать в нужный согласно ГСА момент времени управляющие сигналы Yi. Обычно при проектировании ОУ принимают определенный способ кодирования микроопераций (чаще всего кодом, содержащим столько разрядов, сколько всего различных микроопераций) и для разработки ОА считают, что УА выдает код микроопераций, которые должны выполниться в данный момент времени.
Для УА важна последовательность выдачи соответствующих кодов микроопераций в зависимости от логических условий, вырабатываемых ОА и анализируемых УА в нужные моменты времени. Если принят способ кодирования микроопераций, то функции УА задаются кодированной ГСА. Поэтому для различных содержательных ГСА, имеющих одинаковую кодированную ГСА, ОА будут различны, но УА будет одним и тем же.
В дальнейшем будем рассматривать синтез только УА и только кодированной ГСА.
Конечный автомат, интерпретирующий микропрограмму работы дискретного устройства, называется микропрограммным автоматом. Одну и ту же ГСА можно интерпретировать как автоматом Мили, так и автоматом Мура.
Абстрактный синтез микропрограммного автомата по ГСА осуществляется в два этапа:
1. Получение отмеченной ГСА.
2. Построение графа автомата или таблиц переходов и выходов.
продолжение
--PAGE_BREAK--
СИНТЕЗ АВТОМАТА МИЛИ
На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечают символами a1, a2,… по следующим правилам:
1) символом а1 отмечают вход вершины, следующей за начальной, а также вход конечной вершины;
2) входы всех вершин следующих за операторными, должны быть отмечены;
3) входы различных вершин, за исключением конечной, отмечаются различными символами;
4) если вход вершины отмечается, то только одним символом.
Ясно, что для проведения отметок потребуется конечное число символов а1,...,am. Результатом первого этапа является отмеченная ГСА, которая служит основой для второго этапа — перехода к графу или таблицам переходов-выходов. Пример ГСА, отмеченной для автомата Мили, представлен на рис. 55.
На втором этапе, из отмеченной ГСА, строят граф автомата или таблицы переходов-выходов. Для этого полагают, что в автомате будет столько состояний сколько символов ai понадобилось при отметке ГСА.
<img width=«10» height=«2» src=«ref-1_118927462-155.coolpic» v:shapes="_x0000_s1385">На плоскости рисунка отмечаем все состояния автомата ai. Для каждого из состояний ai определяем по отмеченной ГСА все пути, ведущие в другие состояния и проходящие обязательно только через одну операторную вершину. Например, из состояния а1(рис.55.) есть переход в состояние a2 (путь проходит через операторную вершину y1 y2) и в состояние a4 (путь проходит через вершину y3 y4). Перехода из a1 в a3 нет, так как на этом пути нет ни одной операторной вершины. Будем считать, что автомат осуществляет переход, например, из a1 в a2 при условии x1 = 0 или x1 (см.ГСА, рис.55. ) и вырабатывает на этом переходе выходные сигналы у1 у2 (то, что записано в проходимой операторной вершине ГСА, рис.55.). Значение условий х2, х3, х4 на этом переходе не оказывает влияния на автомат.
<img width=«263» height=«234» src=«ref-1_118927617-2347.coolpic» v:shapes="_x0000_i1250">
--PAGE_BREAK--
Таблицы переходов-выходов автомата Мура представлены в табл. 29 (прямая) и табл. 30 (обратная). Обычно для автомата Мура в таблице переходов-выходов дополнительный столбец для выходных сигналов не используется и выходной сигнал записывается в столбце, где указывается исходное состояние amили состояния перехода aS.
Табл. 29.Прямая таблица переходов Табл. 30.Обратная таблица переходов
автомата Мура. автомата Мура.
am(Y)
as
X
am
as(Y)
X
<img width=«8» height=«2» src=«ref-1_118936981-158.coolpic» v:shapes="_x0000_s1357">a1(--)
a2
x1
<img width=«8» height=«2» src=«ref-1_118936981-158.coolpic» v:shapes="_x0000_s1358">a6
a1(-)
x4
a3
x1
<img width=«8» height=«2» src=«ref-1_118936981-158.coolpic» v:shapes="_x0000_s1359">a7
1
<img width=«8» height=«2» src=«ref-1_118937455-153.coolpic» v:shapes="_x0000_s1360"><img width=«8» height=«2» src=«ref-1_118937608-157.coolpic» v:shapes="_x0000_s1361">a2(y1y2)
a2
x3 x2
a1
a2(y1y2)
x1
<img width=«8» height=«3» src=«ref-1_118937765-161.coolpic» v:shapes="_x0000_s1362">
a5
x3<img width=«8» height=«2» src=«ref-1_118936981-158.coolpic» v:shapes="_x0000_s1363">
<img width=«8» height=«2» src=«ref-1_118936981-158.coolpic» v:shapes="_x0000_s1364">a2
x3 x2
<img width=«8» height=«2» src=«ref-1_118938242-153.coolpic» v:shapes="_x0000_s1365">
a6
x3 x2
<img width=«8» height=«2» src=«ref-1_118936981-158.coolpic» v:shapes="_x0000_s1366">a6
x4
a3(y3y4)
a4
x2
a1
a3(y3y4)
x1
a7
x2<img width=«8» height=«2» src=«ref-1_118936981-158.coolpic» v:shapes="_x0000_s1367">
a4
1
a4(y1y4)
a3
1
a3
a4(y1y4)
x2
a5(y2y3)
a7
1
a2
a5(y2y3)
x3<img width=«8» height=«2» src=«ref-1_118937455-153.coolpic» v:shapes="_x0000_s1368">
a6(y4)
a1
x4
a2
a6(y4)
x3 x2
a2
x4<img width=«8» height=«2» src=«ref-1_118936981-158.coolpic» v:shapes="_x0000_s1369">
a3
a7(y2)
x2<img width=«8» height=«2» src=«ref-1_118937455-153.coolpic» v:shapes="_x0000_s1370">
a7(y2)
a1
1
a5
1
Получением графа или таблиц переходов-выходов заканчивается этап абстрактного синтеза микропрограммного автомата. Как и для конечных автоматов, на этапе абстрактного синтеза можно выполнить минимизацию количества внутренних состояний автомата.
продолжение
--PAGE_BREAK--СТРУКТУРНЫЙ СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ
Структурный синтез микропрограммных автоматов после получения графа или таблицы переходов-выходов в принципе аналогичен каноническому методу синтеза цифровых автоматов, рассмотренному ранее. Однако существуют и определенные особенности в первую очередь связанные с тем, что для реальных автоматов количество элементов памяти и входных сигналов может достигать десяти и более. Функции возбуждения и выходных сигналов трудно поддаются минимизации да и практически минимизация не дает существенного упрощения этих функций при большом количестве переменных. Поэтому минимизация практически не используется при синтезе микропрограммных автоматов.
При выполнении структурного синтеза строят так называемые структурные таблицы переходов и выходов, которые также могут быть как прямыми так и обратными.
Рассмотрим этапы структурного синтеза на конкретных примерах.
СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МИЛИ
Выполним структурный синтез микропрограммного автомата Мили, заданного своей таблицей переходов-выходов (табл. 27 или табл. 28). В качестве примера синтез будем выполнять по прямой таблице (табл. 27).
1. В исходном автомате количество состояний М=6, следовательно, число элементов памяти
m = ] log 2 M [ = ] log 2 6 [ = 3.
Пусть для синтеза используются JK триггеры.
2. Кодируем внутренние состояния автомата, используя для этого карту Карно (рис.57.) и по возможности метод соседнего кодирования. Рекомендуется самостоятельно закодировать состояние с помощью эвристического алгоритма.
3. Строим прямую структурную таблицу переходов-выходов автомата Мили (табл. 31). В данной таблице в столбцах k(am) и k(as) указывается код исходного состояния и состояния перехода соответственно. В столбце функций возбуждения ФВ указывается те значения функций возбуждения, которые на данном переходе обязательно равны 1. Остальные (т.е. равные 0 или принимающие неопределенные значения) не указываются. Это эквивалентно тому, что всем неопределенным значениям функций возбуждения приписывается значение 0, что в общем случае не дает минимальной функции, однако в реальных автоматах минимизация обычно не делается в виду ее неэффективности. Предлагается самостоятельно построить структурную таблицу переходов с указанием всех значений функций возбуждения (в том числе и неопределенных), выполнить минимизацию и сравнить результаты с приведенными ниже.
Табл. 31. Структурная таблица переходов-выходов автомата Мили.
Am
K(am)
as
K(as)
X
Y
ФВ
<img width=«11» height=«2» src=«ref-1_118940460-156.coolpic» v:shapes="_x0000_s1323">a1
000
a2
010
x1
y1y2
J2
a4
001
x1
y3y4
J3
<img width=«11» height=«2» src=«ref-1_118940616-161.coolpic» v:shapes="_x0000_s1329">a2
010
a2
010
x3x2
y1y2
-
<img width=«11» height=«2» src=«ref-1_118940777-157.coolpic» v:shapes="_x0000_s1330">
a5
110
x3
y2y3
J1
a6
011
x3x2
y4
J3
a3
101
a4
001
1
y3y4
K1
<img width=«11» height=«2» src=«ref-1_118940934-158.coolpic» v:shapes="_x0000_s1331">a4
001
a1
000
x2
y2
K3
a3
101
x2
y1y4
J1
a5
110
a1
000
1
y2
K1K2
a6
011
a1
000
x4
-
K2K3
a2
010
x4<img width=«11» height=«2» src=«ref-1_118940777-157.coolpic» v:shapes="_x0000_s1332">
y1y2
K3
4. Для получения функций возбуждения поступаем следующим образом. Выражение для каждой функции получается в виде логической суммы произведений вида aiX, где ai — исходное состояние, X-условие перехода. Для упрощения полученных выражений выполняем все возможные операции склеивания и поглощения:
<img width=«11» height=«2» src=«ref-1_118940616-161.coolpic» v:shapes="_x0000_s1342"> J1 = a2x3 + a4x2 K1 = a3 + a5
<img width=«11» height=«3» src=«ref-1_118941410-161.coolpic» v:shapes="_x0000_s1334"> J2 = a1x1 K2 = a5 + a6x4
<img width=«11» height=«2» src=«ref-1_118940934-158.coolpic» v:shapes="_x0000_s1338"><img width=«11» height=«2» src=«ref-1_118941729-154.coolpic» v:shapes="_x0000_s1336"><img width=«11» height=«2» src=«ref-1_118941883-158.coolpic» v:shapes="_x0000_s1340"> J3 = a1x1 + a2x3x2 K3 = a4x2 + a6x4 + a6x4 = a6 + a4x2
5. Для получения функций выходов поступаем аналогично:
<img width=«11» height=«2» src=«ref-1_118942041-153.coolpic» v:shapes="_x0000_s1348"><img width=«11» height=«2» src=«ref-1_118942194-160.coolpic» v:shapes="_x0000_s1344"><img width=«11» height=«2» src=«ref-1_118942354-160.coolpic» v:shapes="_x0000_s1345"> y1 = a1x1 + a2x3x2 + a4x2 + a6x4
<img width=«11» height=«2» src=«ref-1_118942514-153.coolpic» v:shapes="_x0000_s1350"><img width=«11» height=«2» src=«ref-1_118942667-153.coolpic» v:shapes="_x0000_s1351"><img width=«11» height=«2» src=«ref-1_118942820-158.coolpic» v:shapes="_x0000_s1349"><img width=«11» height=«2» src=«ref-1_118942978-153.coolpic» v:shapes="_x0000_s1346"><img width=«11» height=«2» src=«ref-1_118942667-153.coolpic» v:shapes="_x0000_s1347"> y2 = a1x1 + a2x3x2 + a2x3 + a4x2 + a5 + a6x4
<img width=«11» height=«2» src=«ref-1_118942978-153.coolpic» v:shapes="_x0000_s1352"> y3 = a2x3 + a3 + a1x1
y4 = a1x1 + a2x3x2 + a3 + a4x2
6. Для построения функциональной схемы автомата по полученным выражениям необходимо либо заменить aiего значениями через Q1Q2Q3 либо получить сигнал, соответствующий ai. Обычно используют второй способ и для получения сигнала aiприменяют так называемый дешифратор состояний, на вход которого поступают сигналы с выходов элементов памяти Q1Q2Q3. Кроме того, при построении схемы стараются выделить общие части, встречающиеся в функциях возбуждения или выходных сигналах. В этом случае окончательная система уравнений, по которым строится схема, будет иметь вид:
<img width=«11» height=«2» src=«ref-1_118943437-153.coolpic» v:shapes="_x0000_s1354"> A = a2x3x2+J2 ; J1 = D + B ; y1 = A + B + E ;
B = a4x2 ; K1 = a3 + a5; y2 = A + D + C + a5 + E ;
<img width=«11» height=«2» src=«ref-1_118943590-160.coolpic» v:shapes="_x0000_s1355"><img width=«11» height=«2» src=«ref-1_118940616-161.coolpic» v:shapes="_x0000_s1353"> C = a4x2 ; J2 = a1x1 ; y3 = D + F + a3 ;
<img width=«11» height=«2» src=«ref-1_118943911-159.coolpic» v:shapes="_x0000_s1356"> D = a2x3 ; K2 = a5 + a6x4 ; y4 = a3 + B + J3;
E = a1x1 ; K3 = a6 + C ;
F = a1x1 J3 = F+a2x3x2
Функциональная схема автомата, построенная на основании полученных уравнений, представлена на рис. 58.
СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МУРА
Выполним структурный синтез микропрограммного автомата Мура, заданного своей таблицей переходов-выходов (табл.29 или табл. 30). В качестве примера синтез будем выполнять по обратной таблице (табл. 32).
продолжение
--PAGE_BREAK--1. В исходном автомате количество состояний М=7, следовательно число элементов памяти
m = ] log 2 M [ = ] log 2 7 [ = 3
Пусть для синтеза используется D-триггеры.
2. Кодируем внутренние состояния автомата, используя алгоритм кодирования для D-триггеров. Количество переходов в данное состояние легко определяется из обратной таблицы: a1 ~ 2, a2 ~ 3, a3 ~ 2, a4 ~ 1, a5 ~ 1, a6 ~ 1, a7 ~ 2.
Поэтому коды состояний следующие:
a2-000, a1-001, a3-010, a7-100, a4-011, a5-101, a6-110.
3. Строим структурную таблицу переходов — выходов автомата Мура.
Табл. 32. Структурная таблица переходов — выходов автомата Мура.
am
K(am)
as(Y)
K(as)
X
ФВ
a6
110
a1(-)
001
x4
D3
a7
100
1
D3
<img width=«11» height=«2» src=«ref-1_118949535-155.coolpic» v:shapes="_x0000_s1324">a1
001
a2(y1y2)
000
x1
-
<img width=«11» height=«2» src=«ref-1_118949690-151.coolpic» v:shapes="_x0000_s1325">a2
000
x3x2
a6
110
x4<img width=«11» height=«2» src=«ref-1_118949535-155.coolpic» v:shapes="_x0000_s1326">
a1
001
a3(y3y4)
010
x1
D2
a4
011
1
D2
a3
010
a4(y1y4)
011
x2
D2D3
a2
000
a5(y2y3)
101
x3<img width=«11» height=«2» src=«ref-1_118949535-155.coolpic» v:shapes="_x0000_s1327">
D1D3
a2
000
a6(y4)
110
x3x2
D1D2
a3
010
a7(y2)
100
x2<img width=«11» height=«2» src=«ref-1_118949535-155.coolpic» v:shapes="_x0000_s1328">
D1
a5
101
1
D1
Построение таблицы выполняется аналогично автомату Мили.
4. Выражения для функций возбуждения получаются в виде суммы произведений aiх, где ai-исходное состояние, х — условие перехода.
<img width=«10» height=«2» src=«ref-1_118950306-150.coolpic» v:shapes="_x0000_s1335"><img width=«12» height=«2» src=«ref-1_118950456-156.coolpic» v:shapes="_x0000_s1333">D1 = a2x3 + a2x3x2 + a3x2 + a5
D2 = a1x1 + a4 + a3x2 + a2x3x2
<img width=«12» height=«2» src=«ref-1_118950612-158.coolpic» v:shapes="_x0000_s1337">D3 = a6x4 + a7 + a3x2 + a2x3
или
A = a3x2
B = a2x3x2
<img width=«11» height=«2» src=«ref-1_118942514-153.coolpic» v:shapes="_x0000_s1341"><img width=«12» height=«2» src=«ref-1_118950923-158.coolpic» v:shapes="_x0000_s1339">D1 = a2x3 + B + a3x2 + a5
D2 = a1x1 + a4 + A + B
<img width=«11» height=«2» src=«ref-1_118951081-160.coolpic» v:shapes="_x0000_s1343">D3 = a6x4 + a7 + A + a2x3
5. Выражения для выходных сигналов автомата Мура получаем, исходя из того, что эти сигналы определяются только внутренним состоянием автомата.
y1 = a2 + a4
y2 = a2 + a5 + a7
y3 = a3 + a5
y4 = a3 + a4 + a6
6. Для построения функциональной схемы автомата как и в предыдущем случае используем дешифратор состояний. Схема представлена на рис. 61 .
продолжение
--PAGE_BREAK--ЗАМЕЧАНИЯ.
1. При синтезе микропрограммных автоматов изложенным методом получаемые выражения для функций возбуждения не всегда являются минимальными и в некоторых случаях могут быть упрощены. В частности, можно доопределить функции возбуждения на некоторых наборах единичным значением (а не нулевым, как было ранее) и выполнить все операции склеивания. Например, в синтезированном ранее автомате Мили таким образом можно получить значение k1=1. Рекомендуется в этом убедиться самостоятельно.
Для упрощения схем автоматов можно также предварительно упростить ГСА, уменьшив количество вершин или узлов методами, изложенными в / /.
Автомат Мили в течении такта сохраняет свое состояние и лишь в конце его переходит в новое. Пока автомат находится в данном состоянии Ai он вырабатывает выходные сигналы y=f(Ai,x), где х — сигналы, подаваемые на вход автомата в течение данного такта. В связи с этим автомат Мили может интерпретировать микропрограмму корректно только в том случае, если для любого перехода выполняется условие независимости логических условий от результатов выполнения микроопераций на данном переходе.
Условие независимости нарушается, если на некотором переходе из аm в аs под действием сигнала х с выработкой уi наблюдается функциональная зависимость х = f(уi). В таком случае выполнение микрооперации уi может привести к изменению значения х и автомат, находясь в состоянии аm, и, реагируя на набор входных сигналов, сформирует набор выходных сигналов, не соответствующий микропрограмме. Чтобы избежать этого, можно использовать следующие способы:
1) запомнить значение сигналов х на промежуток времени, равный длительности такта;
2) ввести в автомат дополнительные состояния;
3) реализовать автомат по схеме Мура.
Запоминание значений сигналов х в течение такта осуществляется операционным автоматом с помощью дополнительных элементов памяти – триггеров. Интерпретация микропрограммы автоматом Мура рассматривалась ранее. Введение дополнительных состояний иллюстрируется рис. 59 .
В исходном автомате (рис. 59.а) есть переходы из аi в аj под действием сигналов х и х с выработкой y1 и y2 соответственно и имеет место х = f(y1, y2). Действительно, введение вспомогательных состояний аk и аl позволяет устранить возможную ошибку в выдаче выходных сигналов. На переходах аi аk или аiаl выходные сигналы не вырабатываются. Переходы аi аk или аiаl являются безусловными с выработкой y1 или y2 соответственно. В таком случае изменение значения х, в результате выполнения микроопераций y1 или y2, не повлияет на выходной сигнал, вырабатываемый автоматом, так как на переходах аi аk или аiаl выходной сигнал уже не зависит от х.
Синтез управляющего автомата Мура
на базе регистра сдвига.
Кроме рассмотренного ранее канонического метода, существуют и другие методы синтеза управляющих автоматов, среди которых наиболее широко используется синтез на базе регистра сдвига. Этот метод позволяет при построении схемы отказаться от дешифратора, т.к. состояния кодируются унитарным кодом. В автомате количество элементов памяти выбирается равным количеству внутренних состояний. В каждый момент времени только один триггер находится в 1, остальные в 0. Обычно при синтезе на базе регистра сдвига используются D-триггеры. Очень эффективен данный метод для так называемых линейных микропрограмм, т.е. микропрограмм без ветвлений (отсутствует логические условия). Рассмотрим пример синтеза управляющего автомата Мура данным методом. Пусть закодированная ГСА микропрограммы имеет вид рис. 60. Разметив данную ГСА для автомата Мура, получаем семь состояний. Следовательно число триггеров m=7. Выполним синтез с использованием D-триггеров. Закодируем состояния унитарным кодом: a1=1000000, a2=0100000,..., a7=0000001. Обратная структурная таблица переходов-выходов для данного автомата представлена в таблице.
a
m
Ka
m
a
s
(y)
Ka
s
x
ФВ
а6
0000010
а1(-)
1000000
1
D1
а7
0000001
1
D1
а1
1000000
а2(y1 y2)
0100000
1
D2
а2
0100000
а3(y2)
0010000
1
D3
а3
0010000
а4(y3 y4)
0001000
1
продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по истории украины
Реферат по истории украины
Детский музыкальный театр Экспромт
3 Сентября 2013
Реферат по истории украины
Научно-исследовательские и опытно-конструкторские разработки НИОКР
3 Сентября 2013
Реферат по истории украины
Гетьманщина після Переяславської ради. Руїна
3 Сентября 2013
Реферат по истории украины
Австрийский дом в Москве
3 Сентября 2013