ПТЦА - Прикладная теория цифровых автоматов

Загрузить архив:
Файл: ref-9894.zip (649kb [zip], Скачиваний: 141) скачать

1. Методы анализа и синтеза комбинационных схем.

Техническим аналогомбулевой  функциив вычислительной технике является, так называемая, комбинационная схема,на вход которой поступаютис  выходаснимаются электрическиесигналыв  видеодного из уровней напряжения, соответствующих значениям логического 0 и логической 1.

Для выяснения,  чтожетакое   комбинационная   схема, рассмотрим схему S,имеющую m входов и n выходов (рис. 1). На её входы могут быть поданы наборы значений входныхпеременных Xi {0,1},YjÎ{0,1},

     

Схема S называетсякомбинационной,если  каждуюизn функцийеёвыходов Y1,Y2, ..., Yn можно представить как булеву функцию входных переменных X1, X2, ..., Xm.

Комбинационная схема описывается с помощью системы уравнений (1), где Fi– булева функция.

(1)

Как следует из определения комбинационной схемы,значения выходных переменных Yjв произвольный моментвремени  однозначно определяются значениями входных переменных Xi.

Структурно комбинационная схема может бытьпредставлена каксовокупность  элементарныхлогическихсхем – логических элементов (ЛЭ).ЛЭ выполняют над входными переменными элементарные логические операции типа И-НЕ,И,  ИЛИ,ИЛИ-НЕ и т.д. Число входов логического элемента соответствует числу аргументов воспроизводимой им булевой функции.  Графическое изображение комбинационной схемы,при котором  показанысвязимежду различными элементами,а сами элементы представлены условными обозначениями, называетсяфункциональнойсхемой.

В ходе  разработки комбинационных схем приходится решать задачи анализа и синтеза.

Задачаанализасостоит в определении статических и динамических свойств комбинационной схемы.В статике определяются   булевы  функции,реализуемыекомбинационной схемой по известной ей структуре.В динамикерассматривается способностьнадёжного  функционированиясхемыв  переходных процессах при смене значений переменных на входах схемы,т.е. определяетсяналичие на выходах схемы возможных нежелательных импульсных сигналов,  которые неследуютнепосредственноиз выражений для булевых функций, реализуемых схемой.

Задача синтеза заключается в построении из заданного наборалогическихэлементов  комбинационной схемы, реализующей заданную систему булевых функций.

Решение задачи  синтезане является однозначным,можно предложить различные варианты комбинационных схем, реализующих одну  и ту же систему булевых функций,  но отличающихся по тем или иным параметрам.Разработчик комбинационных схем из этого множествавариантоввыбирает один,исходя из дополнительных критериев: минимального количества логических элементов, необходимыхдля реализации схемы, максимального быстродействия и т.д.Существуют различные методы синтеза комбинационных схем, среди которых наиболее разработан канонический метод.

1.1. Канонический метод синтеза комбинационных схем.

Как отмечалось выше,комбинационнаясхема  (КС)может иметьнесколько выходов.При каноническом методе предполагается,что каждая выходная функция реализуетсясвоей  схемой, совокупность которых и даёт требуемую КС. Поэтому синтез сложной КС с n выходами заменяется синтезом n схем с  однимвыходом.

Согласно каноническому методу синтез КС включает всебя ряд этапов.

1. Подлежащая реализации булева функция (или  еёотрицание) представляется в виде СДНФ.

2. С использованием методов минимизации  определяетсяминимальная ДНФ (МДНФ) или минимальная КНФ (МКНФ).Из полученных двух минимальных форм выбирается более простая.

3. Булеву функцию в минимальной форме согласно п.2 представляют в заданном (или выбранном разработчиком) базисе .

4. По представлению функции в заданном базисе строят комбинационную схему.

Необходимо отметить,что  подлежащаяреализации булева функция F(X1,X2,...,Xm) может быть задана не на всех возможных наборах аргументов X1, X2, ..., Xm.На тех наборах,где функция неопределенна, её доопределяют так, чтобы в результате минимизации получить более простую МДНФ или МКНФ. При этом упростится и сама КС. Кроме того, довольно часто с целью получения ещё более простого  представления функции МДНФ, полученная в п.2, представляется в так называемой скобочной форме, т.е. выносятся за скобки общие части импликантМДНФ.

Рассмотрим канонический   метод   синтеза   на   примере построения схемы полного одноразрядного двоичного сумматора.

Как известно из курса машинной арифметики,полный одноразрядный сумматор - это устройство, которое осуществляет сложение по mod 2 соответствующих разрядов (X1,X2) двоичных чисел с учётом переноса (Рm) в данный разряд из соседнего младшего разряда суммы. Сумматор вырабатывает цифру результата (S) в данном разряде и перенос (Рс) в соседний старший разряд суммы. Таблица истинности такого сумматора (т.е. представление булевой функции, которую он реализует, в виде СДНФ) представлена ниже.

X1

0

0

0

0

1

1

1

1

X2

0

0

1

1

0

0

1

1

Табл.1. Таблица истинности полного одноразрядного двоичного сумматора.

Pm

0

1

0

1

0

1

0

1

S

0

1

1

0

1

0

0

1

Pc

0

0

0

1

0

1

1

1

Необходимо получить булевы функции S=F1(X1,X2m) и Рс=F2(X1,X2m). Карты Карно для этих функций приведены ниже (рис.2).

Как следует  изприведённыхкарт,  МДНФ соответствующих функций имеет вид:

(2)

S=Pm+X2+X1+ X1 X2 Pm

Pc= X1 X2+X1 Pm+X2 Pm

Полученная система булевых функций представлена в базисе И, ИЛИ, НЕ. Соответствующая ей КС приведена на рисунке 4.

Полученную комбинационную схему можно упростить, вынеся за скобки общие части в выражениях для S и Рc, однако существенного результата это не даст  (желательносамостоятельнов этом убедиться).

Значительно упростить схему можно,если воспользоваться другимбазисом, напримерлогическим  элементом "ИСКЛЮЧАЮЩЕЕ ИЛИ". В этом случае выражение для S можно записать S = (X1+X2+ Рm)mod2= X1Å X2Å Рm. Тогда схема для S будет иметь вид (рис.3).

    

Иногда для  синтезаКСс  несколькимивыходами может использоваться следующий приём. Будем считать, что при синтезе схемы   сумматора функция S является   функцией  четырёх переменных:S=f(X1,X2mс).Таблица истинностидля  этого случая принимает вид изображенный в таблице 2.


X1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

X2

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

Pm

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

Pc

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

S

0

X

1

X

1

X

X

0

1

X

X

0

X

0

X

1

Таблица 2. Таблица истинности сумматора.

Неопределённые значения для S соответствуют наборам, которые никогда не могут быть в реальной схеме.Карта Карно для функции S=f(X1,X2,Pm,Pc) представлена на рис.5.

В результате минимизации, получается :

(3)

S=+X2+X1+ X1 X2 Pm = (Pm+X2+X1)+ X1 X2 Pm

Сравнивая выражения (2) и (3),отмечаем,  чтофункция S=f(X1,X2,Pm,Pc)проще,  чемфункцияS=f1(X1,X2,Pm).Схему, соответствующую (3), предлагается построить самостоятельно.

Т.о. задача синтеза имеет обычно несколько решений. Для сравнения различных вариантов комбинационных схемиспользуют  их основныехарактеристики:сложность и быстродействие.

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.СИНТЕЗ  КССУЧЕТОМ ОГРАНИЧЕНИЙНА

При построении КС может оказаться,что выход  k - го логического элемента нагружен входов другихЛЭ  (рис.7а). Это   означает,что k - тый логическийэлемент  перегружени необходимопринять  меры,   устраняющие   указанное   явление. Существуют два способа обеспечения заданного

· использование дополнительных развязывающих усилителей;

· дублирование перегруженного элемента.

Схема с использованием дополнительных развязывающихусилителей представленанарис.7.б. Количество p дополнительных усилителей, необходимых для обеспечения заданного

         Недостаток рассматриваемогоспособа  в том,что в цепь распространения сигнала вносится дополнительная  задержка,что не всегда допустимо.

         Схема с использованием дублированияперегружаемогоэлемента представленана  рис.7.в.Количествоp  дополнительных элементов,  выполняющих ту же функцию,  чтоиК-тый  элемент, определяется по формуле:

         При таком способе обеспечения но увеличивается нагрузка на элементы, формирующиесигналы и что может привести к перегрузке этих элементов и введению дополнительных элементов дляобеспечения заданного Краз.

1.5. СИНТЕЗ  КССУЧЕТОМ  ОГРАНИЧЕНИЯНА.

Представлению функции    в    виде    ДНФ    соответствует двухуровневая КС (если считать,что на ее вход могут поступать какпрямые так и инверсные входные сигналы),на первом уровне которой элементы И ,а их выходы объединяются на втором уровне элементом   ИЛИ   .   Такое   построение   КС  обеспечиваетее максимальное быстродействие,таккак  рангсхемыминимален.  Однако,невсегда возможно на первом уровне и,особенно,  на втором выбрать логические элементы с требуемымт.к. может оказаться, что ЛЭ с таким     эквивалент   с   большим либо,   что предпочтительней,преобразовать БФ, перейдя от ДНФ к скобочной форме.Этотпереход сопровождается уменьшением   требуемого для построения схемы.  Осуществить такой переход можно с помощью факторного алгоритма, суть которого рассмотрим на примере.

Пусть задана некоторая булева функция в виде

Для реализацииэтой  функциипоприведенному  выражению необходимо   использовать   3   логическихэлемента4И,  один логический элемент 5И, один  логический элемент 4ИЛИ.

С помощью факторного алгоритма получим скобочную форму для заданной функции. Для этого обозначим все конъюнкции буквами:

      

и будемрассматриватьих  какнекоторыемножества.  Находим попарные пересечения множеств:

,,,,,.

Полученные пересечения показываютобщие  частиотдельных конъюнкций.Выбираем  пересечение,котороеимеет  наибольшую длину (если такое отсутствует,то выбирают  то,котороечаще всего встречается).В данном случае это   . Поэтому из конъюнкций А и В выносим общую часть. Тогда имеем:

     Обозначим F =   и находимпересечения:

   ,.

     Следовательно, для исходной функции имеем:

          Обозначим

ПересечениеСледовательно, окончательно имеем:

      Для реализации функции по последнему выражению необходимо 5 элементов 2И, 1 элемент 3И, 3 элемента 2ИЛИ ( рис.8 ).

Как видно из полученной схемы для ее реализации необходимы элементы с = 2 или 3 (в отличиеотисходной  с = 4 или 5). Однако ранг схемы увеличился до 7, что приводит к увеличению задержки срабатывания схемы.


1.6. Анализкомбинационных схем.

Задачи анализа КС возникают при необходимости проверить правильность синтеза (на этапе проектирования) или определить БФ, реализуемую КС (при анализе или ремонте схем). Все существующие методы анализа делятся напрямые и косвенные.

В результатеанализаКС прямым методом получается множество наборов входных переменных,  обеспечивающих заданное значение  навыходе,что позволяет записать в алгебраическом виде БФ,реализуемую схемой. К прямым методам относится метод p- алгоритма.

Применение косвенных методов  даетвозможность определитьреакцию схемы на заданный набор входных переменных в статике или проанализировать переходный процесс смены одного входного   наборана  другой. Примерамикосвенныхметодов анализа, являются методы синхронного и асинхронного моделирования.

Все упомянутые методы анализа являются машинoориентированными, что позволяет выполнить анализ схемы на ЭВМ.

Для всех методов анализа необходимо описать схему в виде схемного списка, в который включается в общем случае следующие данные:  номер ЛЭ в схеме;логическая функция, реализуемая ЛЭ; входные переменные    для    данного    ЛЭ. Например, схема представленная на рис.9, может быть описана следующим списком:

                                                                                         

1.7. Анализ комбинационных схемметодомp-алгоритма.

При данном методе,как упоминалось выше,ищутся наборы входных переменных, обеспечивающих заданное значение на выходе КС. Наборы, обеспечивающие на выходе КС логическую 1, образуют так называемое  единичное покрытиеАналогично, входные наборы,обеспечивающие на выходе КС логический 0,образуют нулевое покрытие Рассмотрим покрытияпростейшегологического элемента 2И, выполняющегофункцию  Y=X1X2.Таблица  истинностидляэтой функции:

Табл.3  Таблица истинности функции Y=X1X2


Как видно из приведенной таблицытолькопри  единственном наборе X1=1 и X2=1 на выходе ЛЭ будет 1, т.е.единичноепокрытие включает только один набор

Это покрытие можно упростить,заметив,что  первыйнабор склеивается со вторым и третьим, т.е.

Т.о. для ЛЭ 2И можно сказать, что 1 наего  выходебудет только при обеих единицах на входах, а для  обеспечения0на выходе достаточно подать хотя бы на один вход 0. Рассуждаяаналогично, получим таблицу покрытий для основных ЛЭ, представленных ниже в табл. 4.

Таблица 4.

                                                         

ЛЭ                  Y                    Y                     Y                   Y                    Y                  Y                   Y

         

             НЕ                 2И              2И – НЕ           2ИЛИ        2ИЛИ–НЕ   ИСК. ИЛИ     3И – НЕ                                                                 

              X                 X1 X2             X1 X2              X1 X2             X1 X2           X1 X2          X1 X2 X3  

1

X

&

X1

X2

&

X1

X2

1

X1

X2

1

X1

X2

=1

X1

X2

&

X1

X2

X3


        1                   0   X              1     1               0     0             1    X0    01    1   1                               

                                  X   0                                                             X    1            1    1    

        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. В последней колонке этой таблицы приведен оператор подстановки, в результате работы которого сигнал на выходе ЛЭ заменяется соответствующим покрытием. Необходимо обратить внимание, что все значения переменных, записанные в одной строке, должны одновременно быть в наличии     для     обеспечения      заданного    значения       выходного       сигнала. По-


этому, при замене одного из значений в строке соответствующим покрытием, все остальные значения для других переменных в этой строке должны присутствовать совместно с этим покрытием.

На основании полученного единичного покрытия можно записать БФ, реализуемую схемой:

Таблица 5 Анализ схемы методомp – алгоритма.

а) Получение первого покрытия

б) Получение нулевого покрытия

В дальнейшем можно сравнить полученную БФ с той, по которой строилась схема и проверить правильность ее построения.При анализе схемы может оказаться, что некоторая переменная, получившая на одном из предыдущих шагов некоторые значения на данном шаге должна принять противоположное значение. Возникшее противоречие говорит о том, что данный путь является тупиковым и его необходимо исключить из дальнейшего рассмотрения. Если ни при одной комбинации входных переменных не обеспечивается значение 1(0) на выходе, то это означает, что схема реализует константу 0(1) соответственно.


1. 8 Анализ КСметодом  синхронногомоделирования.

При данном методе считается, что все ЛЭ переключаются одновременно, без задержки. В результате применения метода определяется установившееся значение сигнала на выходе схемы.                       

Рассмотрим метод синхронного моделирования на примере схемы ( рис.9 ).

На первом этапе схему разбиваем на уровни и записываем в порядке возрастания уровня уравнения, описывающие функционирование ЛЭ:

№уровня

№элемента

уравнение

1

1

2

e1 = X1 X2

e2 =

2

3

e3 =

3

4

Y =e4 = e3 + X5


Проанализируем схему при подаче на вход набораX1=0, Х2=0, Х3=0, Х4=1, Х5=1. Для этого решаем записанные уравнения в порядке возрастания уравнения. Имеем:

Следовательно, при подаче на вход набора {00011}, на выходе будет Y=1. Аналогично можно промоделировать работу схемы при подаче на вход любого другого набора.

1.9Анализ  КСметодомасинхронного  моделирования.

Реальный ЛЭ переключается за какое-то конечное время, зависящее от технологии изготовления, условий эксплуатации, емкостей нагрузки и т.д. Прохождение сигнала последовательно через несколько ЛЭ будет приводить к накоплению времени задержки и возникновению сдвига во времени выходного сигнала по отношению ко входному. Наличие задержки и порождаемого ею временного сдвига сигналов может приводить к появлению на выходе отдельных ЛЭ и всей схемы в целом кратковременных сигналов, не предусмотренных БФ, реализуемой схемой. Как иллюстрацию, рассмотрим схему   рис.11, а .

                                                                        

Рис. 11 а)

Рис. 11 . Статический риск сбоя.

а)- схема, б)- временные диаграммы.

t1-время задержки инвертора

t2-время задержки элемента 2И   

Данная схема реализует функцию Рассмотренный случай возможен при задержке срабатывания второго элемента больше, чем первого. Такое явление называется риском сбоя. Различают статистический и динамический риски сбоя.

При статическом риске сбоя до и после переходного процесса состояние выходного сигнала одно и то же, а во время переходного процесса возможно кратковременное появление противоположного сигнала.

При динамическом риске сбоя до и после переходного процесса состояния выходного сигнала противоположные, но в переходном процессе выходной сигнал несколько раз меняет свое значение.Динамический риск сбоя возможен в схеме (рис.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. Комбинационная схема для метода асинхронного моделирования.

Уравнения, описывающие ЛЭ:

                                                                 

1-ый такт

2-ой такт

3-ий такт

Y= e6 = e4 + e5 + X5

e5 =e37

e3=X5 X6

e2=X5 X4

e1=X1 X2

*

*

-

*

*

*

*

*

*

-

-

-

*

-

-

-

-

-


                              Табл. 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         00


                         e1                   0          1         01 

Как следует из результатов моделирования, при смене набора А набором В на выходе элемента 4 имеет место статический риск сбоя, а на выходе схемы - динамический риск сбоя.

Радикальным способом устранения рисков сбоя является введение стробирования для снятия выходного сигнала КС. Стробирующий импульс подается после окончания переходного процесса в КС (т.е.когда на выходе КС уже установилось необходимое значение выходного сигнала), что исключает влияние возможных сбоев на вырабатываемый схемой сигнал.

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ АБСТРА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.

Автомат, у которого все состояния устойчивы -асинхронный.

Автомат  называетсясинхронным,если  онне является асинхронным.

Абстрактный автомат  называетсяконечным,если конечны множества      А = {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 )):

Входное слово

Zi1

Zi2

Zi3

Z

Последовательность cостояний

am

ai2 = d (am, Zi1 )

ai3 = d (ai2, Zi2 )

ai4 = d(ai3, Zi3 )

Выходное слово

wi1 = l (am,Zi1)

wi2 = l (ai2,Zi2)

wi3 = l (ai3,Zi3)

wi4 = l (ai4)


Очевидно, что   для   автомата   Мура   выходнойсигнал Wi1= l(am) в момент времени i1 не зависит от входного  сигнала Zi1 и определяется только состоянием am. Следовательно, сигнал Wi1 никак не связан с входным словом x.

В связи с этим под реакцией автомата Мура, установленного в состояние am,на входное словоx = Zi1, Zi2, . . . , Zikбудем понимать  выходноесловотойже длины w = l(am, x) = Wi2 Wi3 ...Wik+1, сдвинутое по отношению к x на один такт.

Рассмотрим пример. Пусть задан автомат Мура:

Подадим на вход этого автомата туже последовательность, что и для автомата Мили:           x=z1 z2 z2 z1 z2 z2.Последовательность смены состояний и вырабатываемых выходных сигналов представлена в таблице:

w1

w2

w3

w4

a1

a2

a3

a4

z1

a2

a3

a4

a4

z1

a4

a1

a1

a1


Сравнивая реакции   автоматаМили(табл. 13)  иавтоматаМура (табл.15), отмечаем,что эти реакции на одно и тоже  словоx совпадают. Следовательноавтоматы  Мили и Мура реализуют одно и то же преобразование слов входного алфавита. Такие автоматы называются эквивалентными.   Строгое  определениеэквивалентности следующее:

два автомата  содинаковымивходными и выходными алфавитами называются эквивалентными,если после установки их вначальное состояние их реакции на любое входное слово совпадают.

Для каждого автомата Мили можетбытьпостроен  эквивалентный ему автомат Мура и наоборот.

Переход от автомата Мура к эквивалентномуему  автомату Милитривиален и легко осуществляется при графическом способе задания автомата. Для получения графа автомата Мили необходимо выходнойсигнал 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, b­2, 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).

Минимизацией числа  внутренних состояний автомата заканчивается этап абстрактного синтеза.


Структурный синтез ЦА.

Задачи синтеза ЦА.

Канонический метод структурного синтеза ЦА.

Элементарные цифровые автоматы с памятью

(триггерные устройства) и их свойства.

Вслед за этапом абстрактного синтеза автоматов следует этап структурного синтеза, целью которого является построение схемы, реализующей автомат из элементов заданного типа. Если абстрактный автомат был лишь математической моделью, проектируемого устройства, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутренне устройство на уровне логических схем. Основной задачей структурной теории автоматов является разработка общих методов построения структурных схем автоматов.

            В отличие от абстрактного автомата,имеющего одинвходи один выход, на которые поступают сигналы во входноми выходят в выходном W={W1,..,WG} алфавитах, структурный автомат имеет L входных каналов х12,..,хL и N выходныхy1,y2,…,yN  на каждом из которых присутствует сигнал структурного алфавита.

Обычно в качестве структурного используется двоичный алфавит.

         

В этом случае каждому входному сигналу ZF абстрактного автомата соответствует некоторый двоичный вектор (lf1,lf2,..,lfL), где lfLÎ{0,1}.

Очевидно, что для представления (кодирования) входных сигналовZ1,..,ZFабстрактного автомата различными двоичными векторами должно быть выполнено условие

L ] log2F [,

аналогично

N ] log2G [

Например , Z={Z1,Z2,Z3,Z4}   W={W1,W2,W3}.

ТогдаL log24=2N log23=2

Закодировать входные и выходные сигналы можно ,например, так:

Z1 = 00           W1 = 00

Z2 = 01           W2 = 01

Z3 = 10           W3 = 11

Z4 = 11

Cледовательно, структурный автомат с двумя входами x1 и x2и двумя выходами y1иy2 может быть представлен в виде:



Задача синтеза структуры автомата.

На этапе структурного синтеза предварительно  выбираютсяэлементарные автоматы, путем композиции которых строят логические схемы полученных на этапе абстрактного синтеза автоматов Мили и Мура. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.

Рассмотрим канонический метод структурного синтеза при котором используются элементарные автоматы некоторого специального вида –автоматы с памятью, имеющие более одного состояния, и автоматы без памяти – с одним состоянием.Первые автоматы называются элементами памяти, вторые – комбинационные или логические  элементы.

Теоретическим обоснованием канонического метода структурного синтеза автоматов служит теорема о структурной полноте:           

Для правильной работы схем сигналы на входе запоминающих элементов не должны непосредственно участвовать в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. Поэтому запоминающими элементами должны быть не автоматы Мили, а автоматы Мура. Такимобразом,  структурнополная система элементарных автоматов должна содержать хотя бы один автомат Мура. В то жевремя,  для синтеза автоматов с минимальным числом элементов памяти, необходимо в качестве таких элементов выбирать автоматы Мура,имеющие полнуюсистему переходов и полную систему выходов –полные автоматы.

Полнота системы переходов означает, что для любой упорядоченной пары состояний автомата найдётся входной сигнал, переводящий первый элемент этой пары во второй, т.е в таком автомате в каждом столбце таблицы переходов должны встречаться всесостояния  автомата.

Полнота системы выходовавтомата Мура состоит в том, что каждому  состоянию автомата поставлен в соответствие свой особый выходной сигнал, отличный от выходных сигналовдругихсостояний. Т.о. в таком автомате число выходных сигналов равно числу состояний автомата. В связи с этим, в автоматах памяти будем использовать одни и те же обозначения и для состояний, и для выходных сигналов.

Канонический метод    структурного   синтеза   предполагает представление структурной схемы автомата в виде двух частей: памяти и комбинационной схемы.

Память состоит из элементарных автоматов Мура П1,....,ПZ,....,ПR. После выбора элементов памяти каждое состояние синтезируемого автомата А кодируется набором их состояний. Если все автоматы П1...,ПR одинаковы, что в общем случае необязательно, то их число

где M – число состояний синтезируемого автомата А, а b – число состояний элементарного автомата памяти. Обычно для элементарного автомата b=2,  тогда

Например, переход автомата А, имеющего 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 будет иметь два входных и два выходных канала.

Итак, сами компоненты Uz и Qz приZ = 1,...,Rвекторов сигналов возбуждения памяти U и сигналов обратной связи отпамяти Q также могут быть представлены в виде векторов:

Uz = (UZ1,UZ2,...,UZK)иQZ= (QZ1,QZ2,...,QZR).

Если не оговорено особо, то используется двоичный структурный алфавит как для входных и выходных каналов синтезируемого автомата,  такидля входных  и выходных каналов автоматов памяти.  Алфавит состояний автоматов памяти также обычно двоичный.

При построении функций возбуждения памяти автомата используют функцию входов элемента памяти   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-триггера представлена на рис..

D

Q t

Qt+1

0

0

0

0

1

0

1

0

1

1

1

1

Таблица переходов D-триггера.

Рис. 24.


Из приведеннойтаблицыпереходов  дляданноготриггера Qt+1= f(Qt,Dt) можно получить таблицу функций его входов Dt = j(Qt, Qt+1).

Q t

Q t+1

Dt

0

0

0

0

1

1

Таблица функции входов D-триггера.

1

0

0

1

1

1

Как видно из таблицы, состояние, в которое переходит триггер (средний столбец), совпадает с поступившим на его вход сигналом D(t) (правый столбец).В связи с этим таблица функцийвозбуждения  памятисинтезируемогоавтомата  с использованием D-триггеров будет полностью совпадать с кодированной таблицейпереходов этого автомата. Промышленность выпускает D-триггера в интегральном исполнении. Например,

K155TM2 (рис. 25).Таких триггеров два в одном корпусе. Вход С –вход синхронизации, Q,`Q – выходы,Q – прямой, – инверсный.    R, S  –входы установки в 0 и 1 соответственно. При подаче на вход R и S логического нуля триггер устанавливается в соответствующие состояния независимо от сигнала на входах DиC.

T-триггер – триггер со счетным входом – имеет один информационный вход Т и  одинвыход Qи осуществляет суммирование по модулю два значений сигнала T и состояния Q в заданный момент времени.

      Условное обозначение и таблица переходов T-триггера представлена на рис 26.

T

Q t

Qt+1

0

0

0

0

1

1

1

0

1

1

1

0

Таблица переходов T-триггера.


Таблица функцийвходовтриггера  Tt = f(Qt, Qt+1) представлена в таблице.

Q t

Q t+1

Tt

0

0

0

0

1

1

Таблица функции входов T-триггера.

1

0

1

1

1

0

На основании этой таблицы можно получать функцию возбуждения элементов памяти при синтезе автомата на базе T-триггера. Например, если автомат перешел из состояния ai = 010 всостояниеaj=110, то для обеспечения этого перехода функции возбуждения должныбыть:

дляпервого  триггерапри переходе       из 0 в 1           T1 = 1,

для второго триггера при переходе          из 1 в 1           T2 = 0,

для третьего триггера при переходе         из 0 в 0           T3 =0и т.д.

В чистом виде промышленность не выпускает T-триггера.

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

Q t+1

R

S

Q t+1

0

0

0

0

0

0

0

0

0

1

1

0

1

1

0

1

0

1

1

0

0

0

1

1

1

1

1

1

0

0

0

б)

1

0

1

0

1

1

0

1

1

1

а)

Таблица переходов RS-триггера.

RS-триггер

Т

T

C

Q

Рис. 27.

Таблица функций входовRS-триггера.

в)

Табл 21. а), б), в).


Q t

Q t+1

Rt

S

0

0

X

0

0

1

0

1

1

0

1

0

1

1

0

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 - триггер,используемый для синтеза ЦА, промышленностью не выпускается.

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

Q t+1

J

K

Q t+1

0

0

0

0

0

0

Q t

0

0

1

1

0

1

0

0

1

0

0

1

0

1

0

1

1

0

1

1

Q t

1

0

0

1

б)

1

0

1

1

1

1

0

1

1

1

1

0

а)

Т

J

K

Q

JK-триггер

Таблица переходов JK-триггера.

Рис. 28.

Табл. 22 а), б).


Как следует из таблиц переходов, для комбинаций входных сигналов         JK = 00¸10 триггер ведет себя как RS-триггер, а при комбинации JK = 11 – как T-триггер.

Анализируя таблицупереходов ( табл. 22 а), отмечаем,   что переходтриггера,  например,из 0 в 1 требует подачи входных сигналов J=1,K=0 или J=1,K=1,т.е. J=1, K=Х (безразличное значение).   Аналогично   рассуждая   поотношению  кдругим переходам,   получим   следующую   таблицу   функций    входов JK-триггера.

Q t

Q t+1

J

K

0

0

X

0

0

1

1

X

1

0

X

1

1

1

0

X

Таблица функций выходовJK-триггера.

На основаниипоследнейтаблицы  можно получить функцию возбуждения  элементов памяти при синтезе автомата на JK-триггерах. Например, при переходе автомата из состояния ai=010 в состояние aj=110, функции возбуждения должны быть:

для первоготриггера при переходе из 0 в 1                J1 = 1, K1 = X;

для второготриггера при переходе из 1 в 1                J2 = X,K2 = 0;

для третьего триггера при переходе из 0 в 0                J3 = 0, K3 = X.

Пример канонического метода структурного синтеза автомата.

Выполним структурный синтез частичного автомата А, заданного своими таблицами переходов и выходов (табл. 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

0

0

w1

0

0

a1

0

0

z2

0

1

w2

0

1

a2

0

1

z3

1

1

w3

1

1

a3

1

1

w4

1

0

a4

1

0

Кодирование, в общем случае, осуществляется произвольно. Поэтому, например,каждому из сигналов Zi можно поставить в соответствие любую двухразрядную комбинацию х1, х2. Необходимо только, чтобы разные выходные сигналы Zi кодировались разными комбинациями х1, х2. Аналогично для Wi и ai.

3. Получим кодированные таблицы переходов ивыходов структурного автомата. Дляэтого в таблицах переходов и выходов исходного абстрактного автомата вместо Zi, Wi, aicтавим соответствующие коды. Получим таблицы:

x1x2

Q1Q2

x1x2

Q1Q2

Рис. 30 .

Кодированная таблица переходов.

Рис. 31 .

Кодированная таблица выходов

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

В кодированной таблице переходов заданы функции

В кодированной таблице выходов заданны функции:

4. При каноническом методе синтез сводится к получению функций:

и последующем построении комбинационных схем, реализующих данную систему булевых функций.

Функции у1 и у2 могут быть непосредственнополучены из таблицы выходов, например, в виде :

Однако выражения для у1 и у2 можно существенно упростить в результате минимизации, например, с помощью карт Карно:

00

01

11

10

00

01

11

10

00

0

0

1

00

1

0

1

01

1

0

01

1

0

11

0

1

0

11

0

0

1

10

10

x1x2

Q1Q2

x1x2

Q1Q2

Рис. 32 .

Карта Карно для у1.

Рис.33.

Карта Карно для у2.

В результатеминимизацииимеем:

         

Для получения выражений для D1 и D2 необходимо получить таблицы функций возбуждения. Для чего в общем случае необходимо воспользоваться таблицей переходов и функциями входов элементов памяти. Зная код исходного состояния автомата и код

состояния перехода на основании таблицы входов триггера получаем требуемое значение функции возбуждения,обеспечивающее заданный переход. Однако для D-триггеров,как отмечалось ранее,таблица переходов совпадает с таблицей функции возбуждения.Тогда либо непосредственно из этой таблицы,либо врезультате минимизации получаем требуемые значения Di.Обычно используется минимизация с помощью карт Карно:

x1x2

Q1Q2

x1x2

Q1Q2

Рис. 34 .

Карта Карно для D1.

Рис.35.

Карта Карно для D2.

00

01

11

10

00

01

11

10

00

0

1

1

00

0

0

0

01

1

0

01

1

0

11

0

0

1

11

1

1

1

10

10

В результате минимизации получаем:

5. На основании полученных в результате синтеза  булевых выражений((*),(**)) ,строим функциональную схему автомата. Для этого уравнения ((*), (**)) представим в виде:

   

     

Функциональная схема автомата представлена на странице 41:

Дополнительно нафункциональнойсхеме  показансигнал устанавливающий автомат в начальное состояние (в данном случае 00).

     




Особенности синтеза автоматов на базе T, RS, JK триггеров.

Необходимо отметить, что синтез на базе указанных типов триггеров осуществляется аналогично выполненному синтезу на базе D-триггеров. В частности, п. 1¸3 (см. предыдущий параграф) абсолютно аналогичны. Кроме того, как следует из п.4 (см.предыдущий параграф) выходные сигналы не зависят от типа триггеров, поэтому выражение дляyiбудут одинаковыми для любого типатриггеров. Однако функции возбуждения будут различны для разных типов триггеров и получаются на основании таблицы переходов исходного автомата и функции входов выбранного триггера. Без особыхпояснений  нижеприведены таблицы функций входов,функций возбуждений и карты Карно для минимизации функций возбуждения при использовании длясинтеза автомата предыдущего параграфа T-, RS-, JK-триггеров.

                       

T-триггер.

Q t

Q t+1

T t

0

0

0

0

1

1

1

0

1

1

1

0

Таблица функции входов T-триггера.

Таблица функций возбуждения.

x1x2

Q1Q2


00

01

11

10

00

00

11

01

01

10

11

11

01

10

01

00

01

11

10

00

01

11

10

00

0

1

0

00

0

1

1

01

1

1

01

0

1

11

0

1

0

11

1

0

1

10

10

0

Карта Карно для Т1.

Карта Карно для Т2.

x1x2

Q1Q2

x1x2

Q1Q2

RS-триггер.

Q t

Q t+1

R

S

0

0

X

0

0

1

0

1

1

0

1

0

1

1

0

X

Таблица функции входовRS-триггера.

Таблица функций возбуждения.

x1x2

Q1Q2

00

01

11

10

R1

S1

R2

S2

R1

S1

R2

S2

R1

S1

R2

S2

R1

S1

R2

S2

00

X

0

X

0

0

1

1

0

0

X

1

0

01

0

1

0

X

1

0

1

0

11

X

0

0

1

1

0

0

X

0

X

0

1

       

x1x2

Q1Q2

x1x2

Q1Q2

x1x2

Q1Q2

x1x2

Q1Q2

00

01

11

10

00

01

11

10

00

X

0

0

00

0

1

X

01

0

1

01

1

0

11

X

1

0

11

0

0

X

10

10

00

01

11

10

00

01

11

10

00

X

1

1

00

0

0

0

01

0

1

01

X

0

11

0

0

0

11

1

X

1

10

10

JK-триггер.

Q t

Q t+1

J

K

0

0

0

X

0

1

1

X

1

0

X

1

1

1

X

0

00

01

11

10

J1

K1

J2

K2

J1

K1

J2

K2

J1

K1

J2

K2

J1

K1

J2

K2

00

0

X

0

X

1

X

X

1

X

0

X

1

01

1

X

X

0

X

1

X

1

11

0

X

1

X

X

1

X

0

X

0

1

X

       

00

01

11

10

00

01

11

10

00

0

1

X

00

X

X

0

01

1

X

01

X

1

11

0

X

X

11

X

1

0

10

10

    

00

01

11

10

00

01

11

10

00

0

X

X

00

X

1

1

01

X

X

01

0

1

11

X

1

0

11

0

0

X

10

10

Карта Карно для J2.

Карта Карно для K2.

x1x2

Q1Q2

x1x2

Q1Q2

Функциональные схемы автоматов с различными типами триггеров предлагается построить самостоятельно.


Кодирование внутренних состояний ЦА.

Гонки в автомате.

Кодирование заключается в сопоставлении каждому состоянию автомата набора (кода) состояний элементов памяти. При этом наборы для всех состояний должны иметь одинаковую длину, а разным состояниям автомата должны соответствовать разные наборы. Если элементы памяти двоичные, то их число

Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Если автомат переходит из состояния с кодом 010 в состояние с кодом 100, то это означает, что триггер V1 переходит из состояния 0 в состояние 1,V2 – из 1 в 0, V3 – сохраняет свое состояние.

При функционировании автомата могут появиться так называемые состязания. Это явление возникает вследствие того, что элементы памяти имеют различные, хотя и достаточно близкие, времена срабатывания. Различны также задержки сигналов возбуждения, поступающих на входные каналы элементарных автоматов по логическим цепям неодинаковой длины.

Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания. Тот элемент, который выиграет эти состязания, т.е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие, участвующие в состязаниях элементы, изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное его графом.Поэтому в процессе перехода из состояния 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 кодируется кодом: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

Предполагается самостоятельно окончить синтез автомата при данном кодировании ипри любом другом. Результаты сравнить.

Эвристический алгоритм кодирования.

Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе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).

Но тогда функция   w показывает, сколько всего единиц в функции возбуждения, т.е. позволяет оценивать сложность комбинационной схемы автомата. Wможно рассматривать как некую целевую функцию, минимум которой определит такое кодирование, при котором комбинационная схема наиболее простая. Кстати, миинмальное кодовое расстояние между различными состояниями равно 1 и если удается закодировать все состояния соседним кодированием, то очевидно, что w будет минимально возможным и равным т.е.суммарному числу переходов для автомата.

Из выражения для w следует,  что переход из аi в аi, для которого d(i,i)=0,не влияет на w (что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).

Рассмотрим применение эвристического алгоритма на конкретном примере автомата,заданного таблицами переходов и выходов (рис.41. ).Для данного автомата можно построить ориентированный граф (без учета петель), представленный на рис.42.На каждом ребре указан его вес.

Эвристический алгоритм состоит из следующих шагов.

1. Строимматрицу i, j), для которых р(i, j) ¹ 0 (т.е. в автомате есть переход из аi в аj или наоборот) и iуказываемеевес р(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. Упорядочим строки матрицы следующим образом. В первую строку матрицы поместим пару (a,b) с наибольшим весом р(a,b). В нашем случае (a,b) = (2,3),  р(2,3) = 3.Из всех пар, имеющих общий компонент с парой (a,b) выбирается пара (g,d) с наибольшим весом и заносится во вторую строку матрицыa,b}×{g,d}¹0.Затем из всех пар, имеющих общий компонент хотя бы с одной из внесенных уже в матрицу пар выбирается пара с наибольшим весом и заносится в матрицу и т.д..В случае равенства весов пар вычисляются суммы весов компонентов пар (весомр(a) компонента a называется число появлений a в матрице матрицу заноситсяпара  снаибольшей суммой весов. В рассматриваемом автомате на второе место вслед за парой (2,3) претендуют пары:(1,2) с р(1,2) = 2;(3,4) с р(3,4) = 2,(3,5) с р(3,5) = 2.

Для определения того, какая пара займет второе место в матрице находим веса компонентов пар:

     р(1) = 3      р(2) = 3           р(1) + р(2) = 6

     р(3) = 4      р(4) = 2           р(3) + р(4) = 6

     р(3) = 4      р(5) = 2           р(3) + р(5) = 6

В данном случае для всех пар совпадают и их веса и веса их компонентов. Поэтому на второе место матрицы может быть поставлена любая из пар (1,2), (3,4), (3,5). Но тогда на 3-м и 4-м будут остальные две. Выполнив упорядочивание всехпар, получим матрицу в виде:   

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

3. Определяем разрядность кода для кодирования состояний автомата (количество элементов памяти – триггеров). Всего состояний M=5. Тогда

R = ]log2M[ = ]log25[ =3.

Закодируем состояния из первой строки матрицы следующим образом: K2 = K(а2) = 000; K3 = K(а3) = 001.

            Для удобства кодирования будем иллюстрировать этот процесс картой Карно:

               

4. Вычеркнем из матрицы первую строку, соответствующую закодированным состояниям а2 иа3. Получим матрицу

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. Строим матрицу    выбравиз  строчки, содержащие g.

i

j

p(i,j)

1

2

2

Mg

=

M’

=

1

3

1

1

5

1

Пусть Bg= {g1,...,gF} –множество элементов из матрицы Кg1,..., KgF   соответственно. В нашем случае:

        Bg = B3 = {2,3}              K2 = 000         K3 = 001.

7. Для каждого Kgf (f=1, ..., F) найдемиеще  незанятыхдля  кодирования состояний автомата. (Для  соседнихкодов кодовое расстояние d=1).

            K2 = 000         = {100, 010}

            K3 = 001         = {011, 101}.

Построим множество

Если оказывается, что , где

8. Для каждого кода из множества Dgнаходим кодовое расстояние до кода

            K2 = 000K3 = 001

           d(100, 000) = 1                       d(100, 001) = 2

           d(010, 000) = 1                       d(010, 001) = 2

           d(011, 000) = 2                       d(011, 001) = 1

           d(101, 000) = 2                       d(100, 001) = 1

9. Находим значение функции w для каждого кода из множества Dg.

10. Из множества Dgвыбираем код Kg, укоторого получилось минимальное значение w в п.9. Выбираем код для состояния a1    К1 =100.

11. Из матрицы вычеркиваем строки, в которых оба элемента уже закодированы, в результате чего получим новую матрицу не осталось ни одной строки, то кодирование закончено. В противном случае возвращаемся к п.5. В нашем случае имеем:

i

j

p(i,j)

3

4

2

3

5

2

M’

=

1

5

1

2

4

1

2

5

1

К2 = 000         = {010}

K3 = 001         = {011, 101}

         

            K2 = 000         K3 = 001

            d(010, 000) = 1           d(010, 001) = 2

            d(011, 000) = 2           d(011, 001) = 1

           d(101, 000) = 2           d(101, 001) = 1

Выбираем К4 = 101.

            К1 = 100         = {110}

            K2 = 000         = {010}

            К3 = 001         = {011}

            К1 = 100                     K2 = 000                     K3 = 001

            d(110, 100) = 1           d(110, 000) = 2           d(110, 001) = 3

            d(010, 100) = 2           d(010, 000) = 1           d(010, 001) = 2

            d(011, 100) = 3           d(011, 000) = 2           d(011, 001) = 1

Выбираем К5 = 011.

Т.к. всесостояния автомата закодированы, то работа алгоритма заканчивается. Общее   количество переключений триггеров:

Минимально возможное количествопереключений(если бы состояния были закодированы соседним кодированием)

Коэффициент эффективности кодирования:

Рассмотренный алгоритм кодирования является машино-ориентированным,  существуют программы, реализующие этот алгоритм.

Необходимо отметитьвзаключении, что использование алгоритма кодирования для D-триггеровили эвристического алгоритма для других типов триггеров обеспечивает наиболее простую с точки зрения реализации схему,но при этом возможны гонки. Для радикального устранения последних используют аппаратные методы – триггеры с двойной памятью: триггеры, управляемые фронтом и т.д..

Управляющие и операторные автоматы.

Принцип микропрограммного управления.

ЭВМ перерабатывает информацию, выполняя над ней какие-то операции. Для выполнения операций над информацией используются операционные устройства – процессоры, каналы ввода-вывода, устройства управления внешними устройствами и т.д. Функцией операционного устройства является выполнение заданного множества операций F={f1,...,fG}над входными словами D={d1,...,dH} c целью вычисления слов R={r1,...,rQ}, которые представляют результаты операций R=fg(D), где g=1,2,...,G.

Функциональная и структурная организация операционных устройств базируется на принципе микропрограммного управления, который состоит в следующем:

1. Любая операция  fg(g=1,...,G), реализуемая устройством, рассматривается как сложное действие, которое разделяется на последовательность элементарных действий над словами информации. Эти элементарные действия называютсямикрооперациями.

2. Для управления порядком следования микроопераций используются логические условия, которые в зависимости от значений слов, преобразуемых микрооперациями, принимают значения "ложь" или "истина" (1 или 0).

3. Процесс выполнения операций в устройстве описывается в форме алгоритма, который представляется в терминах микроопераций и логических условий и называется микропрограммой.Микропрограмма определяет порядок проверки значений логических условий и следования микроопераций, необходимый для получения требуемых результатов.

4. Микропрограмма используется как форма представления функции устройства, на основе которой определяется структура и порядок функционирования устройства во времени.

          Т.о. из принципа микропрограммного управления следует, что структура и порядок функционирования операционных устройств предопределяется алгоритмом выполнения операции F={f1,...,fG}.

К элементарным действиям над словами информации микрооперациям относятся: передача информации из одного регистра в другой, взятие обратного кода, сдвиг и т.д.

Понятие операционного и управляющих автоматов.

Как показал академик В.М. Глушков в любом устройстве обработки цифровой информации можно выделить два основных блока – операционный автомат (ОА) и управляющий автомат (УА).

Операционный автомат (ОА) служит для хранения слов информации, выполнения набора микроопераций и вычисления значений логических условий, т.е. операционный автомат является структурой, организованной для выполнения действий над информацией. Микрооперации, выполняемые ОА, задаются множеством управляющих сигналов Y={y1,....,yM}, с каждым из которых отождествляется определенная микрооперация.

Значения логических условий, вычисляемые в операционном автомате, отображаются множеством осведомительных сигналов X={x1,...,xL}, каждый из которых отождествляется с определенным логическим условием.

Управляющий автомат (УА) генерирует последовательность управляющих сигналов, предписанную микропрограммой и соответствующую значениям логическим условий. Иначе говоря, управляющий автомат задает порядок выполнения действий в ОА, вытекающий из алгоритма выполнения операций. Наименование операции, которую необходимо выполнить в устройстве, определяется кодом g операции, поступающим в УА извне. По отношению к УА сигналы g1,...,gh, посредством которых кодируется наименование операции и осведомительные сигналы x1,...,xL, формируемые в операционном автомате, играют одинаковую роль: они влияют на порядок выработки управляющих сигналов Y. Поэтому сигналы g1,...,gh и x1,...,xL относятся к одному классу – к классу осведомительных сигналов, поступающих на вход УА.

Т.о. любое операционное устройство – процессор, канал ввода-вывода и т.д. – является композицией операционного и управляющего автоматов.Операционный автомат, реализуя действия над словами информации, является исполнительной частью устройства, работой которого управляет управляющий автомат, генерирующий необходимые последовательности управляющих сигналов.

Операционный и управляющий автоматы могут быть определены своими функциями – перечнем выполняемых ими действий.

  Функция ОА определяется следующей совокупностью сведений:

1) множеством входных слов D={d1,...,dH}, вводимых в автомат в качестве операндов;

2) множеством выходных слов R={r1,...,rQ}, представляющих результаты операций;

3) множеством внутренних слов S={s1,...,sN}, используемых для представления информации в процессе выполнения операций. Можно считать, что входные и выходные слова совпадают с определенными внутренними DÍS, RÍS.

4) множеством микроопераций Y={ym}, реализующих преобразование S=jm(s) над словами информации, где jm – вычисляемая функция;

5) множеством логических условий X={xi}, где xi=yi(si) и yi – булева функция;

T.o. функция ОА задана, если заданы (определены) множества D, R, S, Y, X. Время не является аргументом функции ОА. Функция устанавливает список действий-микроопераций и логических условий, которые может выполнять автомат, но никак не определяет порядок следования этих действий во времени. Т.е. функция ОА характеризует средства, которые могут быть использованы для вычислений, но не сам вычислительный процесс.

Порядок выполнения действий во времени определяется в форме функций управляющего автомата.

Функция управляющего автомата – это операторная схема алгоритма ( микропрограммы), функциональными операторами которой являются символы у1,...,уm, отождествляемые с микрооперациями, и в качестве логических условий используются булевы переменные х1,...,хL. Операторная схема алгоритма наиболее часто представляется в виде граф-схемы алгоритма (ГСА). ГСА определяет вычислительный процесс последовательно во времени, устанавливая порядок проверки логических условий х1L и порядок следования микроопераций у1m.



СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ И МИКРОПРОГРАММ

Наиболее наглядно изображать микропрограммы и алгоритмы в виде ориентированного графа, т.н. граф схемы алгоритма (ГСА). Кроме наглядности это дает возможность использовать для анализа и преобразования микропрограмм эффективные методы теории графов.  При графическом описании отдельные функции алгоритмов (микрооперации) отображаются в виде условных графических изображений, т.н. вершин. В ГСА обычно используют вершины следующих типов:

- вершина «начало» имеет один выход, входов не имеет. Обозначает начало микропрограммы.

- вершина «конец» имеет любое число входов, выходов не имеет. Обозначает конец микропрограммы.

- операторная вершина имеет любое число входов, один выход. Внутри операторной вершины записывается одна микрокоманда - совокупность микроопераций, допускающих совместное (т.е. одновременное) выполнение.

     

  

- условная вершина имеет любое число входов и 2 выхода. Внутри условной вершины записывается булевое выражение, в зависимости от значения которого осуществляется выбор направления дальнейшего выполнения микропрограммы.

- особый вид условной вершины - ждущая - имеет множество входов, 2 выхода, 1 из которых заведен на вход. При попадании в ждущую вершину выход из нее возможен только при выполнении условия Х.

Граф микропрограммы состоит из совокупности перечисленных вершин и дуг, соединяющих выходы одних вершин с входами других. Соединение вершин и направление дуг графа определяют исходя из алгоритма операции, описываемого графом, и структуры операционного автомата.

Сама микропрограмма и ее граф должны быть корректны, т.е. отвечать следующим условиям:

1. В графе должна быть только одна начальная и одна конечная вершина.

2. В любую вершину графа должен вести по крайней мере один путь из начальной вершины.

3. Из каждого выхода любой вершины графа должен существовать по

крайней мере один путь в конечную вершину.

4. При всех возможных значениях логических условий и используемых слов должен существовать путь из начальной вершины в конечную.



Пример ГСА представлен на рисунке:

ГСА на рис.43  называется содержательной, т.к. внутри вершин записаны в явном виде микрооперации и логические условия. Если же каждую микрооперацию обозначить символами Yi, a логические условия через Xi, то получится так называемая кодированная ГСА (рис.44 ).Для правильного восприятия микропрограммы, заданной в виде кодированной ГСА, необходимо знать соответствия между Yi, Xi и содержанием соответствующих микроопераций и логических условий.

Для записи микроопераций внутри вершин используется так называемый         Ф-язык. Подробно с зтим языком можно ознакомиться в последующих курсах «Схемотехника ЭВМ», «Теория и проектирование ЭВМ».Здесь же мы рассмотрим только основные положения этого языка.

В этом языке существуют двоичные константы и переменные: 0010 - константа, A(1:4) - четырехразрядное слово - четырехразрядная двоичная переменная.  Например, A(1:4)=1010 означает, что в первом разряде слова A будет 1, во втором - 0 и т.д. A(2:3) - часть слова A, размещенная во втором и третьем разрядах.

Наиболее употребительные операции Ф-языка:

присваивание - A( 0:3 ): = 1000, B( 1:4 ): = A( 5:8 ) и т.д.

инвертирование - A( 0:3 ): = ^ B( 1:4 )

конкатенации - С( 0:6 ): = A( 0:3 ). B( 1:3 )

Пример 1. A( 0:3 ): = 1100B( 1:4 ): = A( 0:3 ) ® B( 1:4 ): = 1100

2. B( 1:4 ): = 0101   A( 0:3 ): = ^B( 1:4 ) ® A( 0:3 ): = 1010

3. A( 0:3 ): = 1101   B( 1:3 ): = 110C( 0:6 ): = A( 0:3 ). B( 1:3 ) ® C(0:6):=1101110

Запись вида A(2) означает, что здесь рассматривается второй разряд слова A, т.е. это бит, записанный во втором разряде слова A.

При выполнении операций присваивания необходимо соблюдать равенство разрядов в словах слева и справа от знака присваивания.  Операции сложения, логического сложения и т.д. в Ф-языке записываются обычным способом через оператор присваивания:

C(0:n):=A(0:n)+B(0:n)

D(0:n):=A(0:n)vB(0:n) ит.д.

ОПЕРАЦИОННЫЕЭЛЕМЕНТЫ

Согласно принципа микропрограммного управления, любая сложная операция распадается на ряд микроопераций, которые выполняются ОА. Различные микрооперации выполняются элементарными ОА - так называемыми операционными элементами (ОЭ), которые являются составными частями основного ОА.

Под операционным элементом понимают устройство, реализующее одну из следующих функций или их произвольную комбинацию:

· хранение слова информации С;

· выполнение некоторых микроопераций, в результате которых вычисляется новое значение слова С;

· вычисления логического условия, зависящего от слова С;

Т.о. функция ОЭ определена, если заданы:

· описание хранимого или вычисляемого слова;

· описание множества микроопераций, выполняемых этим элементом;

· описание вычисляемых этим элементом логических условий.

Для построения ОА ОЭ соединяются между собой с помощью цепей передачи слов информации от выходов одних элементов к входам других.

В зависимости от выполняемых микроопераций ОЭ делятся на разновидности: шина, регистр, счетчик, сумматор, схема сравнения, дешифратор, шифратор и т.д.

Шина - это совокупность цепей, предназначенных для передачи слова информации. Условное обозначение шины представлено на рис.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. Построение графа автомата или таблиц переходов и выходов.

СИНТЕЗАВТОМАТА  МИЛИ

На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечают символами a1, a2,.. по следующим правилам:

1) символом а1 отмечают вход вершины, следующей за начальной, а также вход конечной вершины;

2) входы всех вершин следующих за операторными, должны быть отмечены;

3) входы различных вершин, заисключением конечной, отмечаются различными символами;

4) если вход вершины отмечается, то только одним символом.

Ясно, что для проведения отметок потребуется конечное число символов а1,...,am. Результатом первого этапа является отмеченная ГСА, которая служит основой для второго этапа - перехода к графу или таблицам переходов-выходов. Пример ГСА, отмеченной для автомата Мили, представлен на рис. 55.


На втором этапе, из отмеченной ГСА, строят граф автомата или таблицы переходов-выходов. Для этого полагают, что в автомате будет столько состояний сколько символов ai понадобилось при отметке ГСА.                       

i. Для каждого из состояний ai определяем по отмеченной ГСА все пути, ведущие в другие состояния и проходящие обязательно только через одну операторную вершину. Например, из состояния а1(рис.55.) есть переход в состояние a2 (путь проходит через операторную вершину y1 y2) и в состояние a4 (путь проходит через вершину y3 y4). Перехода из a1 в a3 нет, так как на этом пути нет ни одной операторной вершины. Будем считать, что автомат осуществляет переход, например, из a1 в a2 при условии x1 = 0 или x1 (см.ГСА, рис.55. ) и вырабатывает на этом переходе выходные сигналы у1 у2 (то, что записано в проходимой операторной вершине ГСА, рис.55.). Значение условий х2, х3, х4 на этом переходе не оказывает влияния на автомат.

6 в а1), т.е. не сопровождается выработкой выходных сигналов.

Отмечаем на графе все указанные пути для всех состояний в виде дуг, которым приписываем условия перехода и выходной сигнал, вырабатываемый на этом переходе. Получим граф автомата (рис.55. ).  

На этом графе переходам типа а3 ®a4,        a5 ® a1 приписывается условие перехода 1, т.к. эти переходы являются безусловными и выполняются всегда, когда автомат попадает в состояние а3 (или а5).На основании отмеченной ГСА или графа автомата можно построить таблицу переходов-выходов. Для микропрограммных автоматов таблица переходов-выходов строится в виде списка и различаются прямая и обратная таблицы. Для данного автомата прямая таблица представлена в табл. 27., обратная - в табл. 28.

            

     

Табл. 27.Прямая таблица переходов-                                   Табл. 28.Обратная таблица перехо-

       выходов автомата Мили                                                      дов - выходов автомата Мили

am

as

X

Y

am

as

X

Y

a1

a2

x1

y1y2

a4

a1

x2

y2

a4

x1

y3y4

a5

1

y2

a2

a2

x3x2

y1y2

a6

x4

-

a5

x3

y2y3

a1

a2

x1

y1y2

a6

x3x2

y4

a2

x3x2

y1y2

a3

a4

1

y3y4

a6

x4

y1y2

a4

a1

x2

y2

a4

a3

x2

y1y4

a3

x2

y1y4

a1

a4

x1

y3y4

a5

a1

1

y2

a3

1

y3y4

a6

a1

x4

-

a2

a5

x3

y2y3

a2

x4

y1y2

a2

a6

x3x2

y4

В приведенных таблицах am - исходное состояние, aS - состояние перехода, Х - условие (входной сигнал), обеспечивающий переход из состояния am в состояние as, Y - выходной сигнал, вырабатываемый автоматом при переходе из am в aS.

СИНТЕЗАВТОМАТА  МУРА.

Для автомата Мура на этапе получения отмеченной ГСА разметка производится согласно следующим правилам:

1) символом а1 отмечается начальная и конечная вершины;

2) различные операторные вершины отмечаются различными символами;

3) все операторные вершины должны быть отмечены;

Пример ГСА, отмеченной для автомата Мура, представлен на рис. 56.


Граф автомата Мура, соответствующий отмеченной ГСА (рис. ), представлен на рис. . Построение его аналогично построению графа для автомата Мили.

Таблицы переходов-выходов автомата Мура представлены в табл. 29 (прямая) и табл. 30 (обратная). Обычно для автомата Мура в таблице переходов-выходов дополнительный столбец для выходных сигналов не используется и выходной сигнал записывается в столбце, где указывается исходное состояние am или состояния перехода aS.

Табл. 29.Прямая таблица переходовТабл. 30.Обратная таблица переходов

автомата Мура.                                                                  автомата Мура.

am(Y)

a

X

am

a(Y)

X

a1(--)

a2

x1

a6

a1(-)

x4

a3

x1

a7

1

a2(y1y2)

a2

x3 x2

a1

a2(y1y2)

x1

a5

x3

a2

x3 x2

a6

x3 x2

a6

x4

a3(y3y4)

a4

x2

a1

a3(y3y4)

x1

a7

x2

a4

1

a4(y1y4)

a3

1

a3

a4(y1y4)

x2

a5(y2y3)

a7

1

a2

a5(y2y3)

x3

a6(y4)

a1

x4

a2

a6(y4)

x3 x2

a2

x4

a3

a7(y2)

x2

a7(y2)

a1

1

a5

1

Получением графа или таблиц переходов-выходов заканчивается этап абстрактного синтеза микропрограммного автомата. Как и для конечных автоматов, на этапе абстрактного синтеза можно выполнить минимизацию количества внутренних состояний автомата.

    

СТРУКТУРНЫЙ СИНТЕЗ МИКРОПРОГРАММНЫХАВТОМАТОВ

Структурный синтез микропрограммных автоматов после получения графа или таблицы переходов-выходов в принципе аналогичен каноническому методу синтеза цифровых автоматов, рассмотренному ранее. Однако существуют и определенные особенности в первую очередь связанные с тем, что для реальных автоматов количество элементов памяти и входных сигналов может достигать десяти и более. Функции возбуждения и выходных сигналов трудно поддаются минимизации да и практически минимизация не дает существенного упрощения этих функций при большом количестве переменных. Поэтому минимизация практически не используется при синтезе микропрограммных автоматов.

При выполнении структурного синтеза строят так называемые структурные таблицы переходов и выходов, которые также могут быть как прямыми так и обратными.

  Рассмотрим этапы структурного синтеза на конкретных примерах.

СТРУКТУРНЫЙСИНТЕЗ  АВТОМАТАМИЛИ

          Выполним структурный синтез микропрограммного автомата Мили, заданного своей таблицей переходов-выходов (табл. 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

ФВ

a1

000

a2

010

x1

y1y2

J2

a4

001

x1

y3y4

J3

a2

010

a2

010

x3x2

y1y2

-

a5

110

x3

y2y3

J1

a6

011

x3x2

y4

J3

a3

101

a4

001

1

y3y4

K1

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

y1y2

K3

4. Для получения функций возбуждения поступаем следующим образом.    Выражение для каждой функции получается в виде логической суммы произведений вида aiX, где ai- исходное состояние, X-условие перехода. Для упрощения полученных выражений выполняем все возможные операции склеивания и поглощения:

         

   J1 = a2x3 + a4x2       K1 = a3 + a5

   J2 = a1x1                  K2 = a5 + a6x4

   J3 = a1x1 + a2x3x2    K3 = a4x2 + a6x4 + a6x4 = a6 + a4x2

5. Для получения функций выходов поступаем аналогично:

     y1 = a1x1 + a2x3x2 + a4x2 + a6x4

     y2 = a1x1 + a2x3x2 + a2x3 + a4x2 + a5 + a6x4

     y3 = a2x3 + a3 + a1x1

     y4 = a1x1 + a2x3x2 + a3 + a4x2

6. Для построения функциональной схемы автомата по полученным выражениям необходимо либо заменить ai его значениями через Q1Q2Q3 либо получить сигнал, соответствующий ai. Обычно используют второй способ и для получения сигнала ai применяют так называемый дешифратор состояний, на вход которого поступают сигналы с выходов элементов памяти Q1Q2Q3. Кроме того, при построении схемы стараются выделить общие части, встречающиеся в функциях возбуждения или выходных сигналах. В этом случае окончательная система уравнений, по которым строится схема, будет иметь вид:

   A = a2x3x2+J2 ;             J1 = D + B ;        y1 = A + B + E ;

   B = a4x2 ;                      K1 = a3 + a5;        y2 = A + D + C + a5 + E ;

   C = a4x2 ;                      J2 = a1x1 ;             y3 = D + F + a3 ;

   D = a2x3 ;                      K2 = a5 + a6x4 ;    y4 = a3 + B + J3;

   E = a1x1 ;                      K3 = a6 + C ;

   F = a1x1                              J3 = F+a2x3x2

Функциональная схема автомата, построенная на основании полученных уравнений, представлена на рис. 58.



СТРУКТУРНЫЙСИНТЕЗ  АВТОМАТАМУРА

Выполним структурный синтез микропрограммного автомата Мура, заданного своей таблицей переходов-выходов (табл.29или табл. 30).В качестве примера синтез будем выполнять по обратной таблице (табл. 32).

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

a1

001

a2(y1y2)

000

x1

-

a2

000

x3x2

a6

110

x4

a1

001

a3(y3y4)

010

x1

D2

a4

011

1

D2

a3

010

a4(y1y4)

011

x2

D2D3

a2

000

a5(y2y3)

101

x3

D1D3

a2

000

a6(y4)

110

x3x2

D1D2

a3

010

a7(y2)

100

x2

D1

a5

101

1

D1

Построение таблицы выполняется аналогично автомату Мили.

4. Выражения для функций возбуждения получаются в виде суммы произведений aiх, где ai-исходное состояние, х - условие перехода.

D1 = a2x3 + a2x3x2 + a3x2 + a5

D2 = a1x1 + a4 + a3x2 + a2x3x2

D3 = a6x4 + a7 + a3x2 + a2x3

       или

A = a3x2

B = a2x3x2

D1 = a2x3 + B + a3x2 + a5

D2 = a1x1 + a4 + A + B

D3 = a6x4 + a7 + A + a2x3

5. Выражения для выходных сигналов автомата Мура получаем, исходя из того, что эти сигналы определяются только внутренним состоянием автомата.

y1 = a2 + a4

y2 = a2 + a5 + a7

y3 = a3 + a5

y4 = a3 + a4 + a6

6. Для построения функциональной схемы автомата как и в предыдущем случае используем дешифратор состояний. Схема представлена на рис. 61 .

ЗАМЕЧАНИЯ.

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. Обратная структурная таблица переходов-выходов для данного автомата представлена в таблице.

am

Kam

as(y)

Kas

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

D4

а4

0001000

а5( y2)

0000100

D5

а5

0000100

а6(y3)

0000010

1

D6

а4

0001000

а7(y4)

0000001

x

D7

На основании структурной таблицы записываем выражения для выходных сигналов yi и функций Di :

D1 = a6 + a7                         y1 = a2

D2 = a1                                   y2 = a2 + a3 + a5

D3 = a2                                   y3 = a4 + a6

D4 = a3                                   y4 = a4 + a7

D5 = a4

D6 = a5

D7 = a4×x

Т.к. состояния автомата закодированы унитарным кодом, то можно отождествить каждое состояние с выходом соответствующего триггера, т.е. принять аi=Qi. Для принятого способа кодирования переход из одного состояния в другое как бы сопровождается сдвигом кода, за-

писанного в семиразрядном регистре. Этим и объясняется название метода. Функциональная схема автомата Мура, построенная по полученным уравнениям, приведена на рисунке 62. При определенных навыках синтез автомата Мура на базе регистра сдвига выполняется непосредственно по отмеченной ГСА без построения структурной таблицы переходов-выходов.