Синтез цифровых автоматов

      Содержание 

    Введение………………………………………………………………………..3

    1. Теоретическая часть. Синтез цифровых автоматов……….……………...5

        1.1. Графы переходов……………………………………………………….5

        1.2. Минимизация…………………………………………………………...5

        1.3. Логические основы построения  цифровых автоматов………………7

        1.4. Понятие об информации и ее преобразованиях……………………...8

        1.5. Преобразование алфавитной информации…………………………..11

        1.6.Способы задания автоматов…………………………………………..13

    2. Практическая часть. Синтез цифровых  автоматов определяющих заданную последовательность…………………………………………...…..…....16

        2.1. Заданная бинарная последовательность……………………………..16

        2.2. Граф…………………………………………………………………….16

        2.3. Таблицы………………………………………………………………..17

    Заключение………………………………………………………………..….20

    Библиографический список………………………………………………....22

Введение 

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

     1) техническом,

     2) математическом.

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

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

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

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

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

     Цель  данной рассмотреть и построить  синтез цифрового автомата определяющего  заданную последовательность.

     Данная  цель последовательно реализуется  в задачах, а именно:

     - рассмотреть теоретическую сторону синтеза цифрового  автомата;

     - исследовать заданную бинарную последовательность;

     - построить граф;

     - рассчитать таблицы;

     - проследить минимизацию Карт  Карно

     - построить схему;

     - провести анализ применения цифровых  автоматов.

     Для написания работы использовался обширный список литературы. 
1. Теоретическая часть. Синтез цифровых автоматов 

     1.1. Графы переходов 

     Графом  автомата называется ориентированный  граф, вершины которых соответствуют  состояниям , а дуги переходам между  ними. Две вершины графа автомата a_m и a_s (исходное состояние и состояние перехода) соединяются дугой, направленной от a_m к a_s, если в автомате имеется переход из a_m в a_s. Дуге (a_m, a_s) графа автомата приписывается входной сигнал x_f и выходной сигнал w_g, если он определен, в противном случае ставится прочерк. Если переход автомата из состояния a_m в a_s происходит в под действием нескольких входных сигналов, то дуге (a_m, a_s) приписываются все эти входные и соответствующие выходные сигналы. Ниже на рисунке приведены заданные ранее таблицами графы автоматов

1.2. Минимизация 

     Однозначность соответствия формы логической функции  и параметров реальной электронной  схемы приводит к необходимости  оптимизации функции, т.е. к необходимости  получения наилучшего её вида по выбранному критерию. В общем случае речь должна идти об оптимизации функции по таким показателям, как быстродействие, надежность (достижение их максимума), количество потребного оборудования, вес, габариты, энергопотребление, стоимость (достижение их минимума) и т.п. Однако решение этой задачи в общем виде- достаточно трудное дело, тем более что некоторые из указанных показателей находятся в известном противоречии. Например, увеличение быстродействия, как правило, достигается за счет параллельной организации работы данного устройства, но это ведёт к увеличению оборудования, а значит, к уменьшению надежности и увеличению стоимости. Поэтому на практике обычно решается частная задача оптимизации по одному из критериев. Чаще всего это делается по минимуму потребного оборудования, так как при этом автоматически решаются задачи получения минимальных габаритов, веса, энергопотребления, стоимости. Такая частная задача оптимизации логической функции носит название минимизации. Таким образом, возникает задача нахождения из всех возможных форм логической функции её так называемой минимальной формы, обеспечивающей минимум затрат оборудования при построении синтезируемого узла, если имеется заданный набор логических элементов (НЕ, И, ИЛИ) с определенными техническими характеристиками (например, максимально возможное число входов у элементов И, ИЛИ и др.). Нетрудно заметить, что в рамках нормальных форм минимальной будет такая разновидность функции, которая состоит из наименьшего количества членов при наименьшем, по возможности, общем числе символов переменных. Из большего числа различных приемов и методов минимизации рассмотрим табличный метод (метод Вейча-Карно). Исходной формой для любого из этих методов является одна из совершенных форм-СДНФ или СКНФ. Это обстоятельство практически не накладывает особых ограничений, поскольку переход от произвольной формы функции к её совершенным формам, как это было показано выше, не представляет принципиальных трудностей. В общем случае при любом из вышеупомянутых методов минимизация производится в три этапа. 1-й этап – переход от совершенной Д(К)НФ к сокращенной Д(К)НФ путем производства всех возможных склеиваний друг с другом конституент, а затем всех производны членов более низкого ранга. Таким образом, под сокращенной формой будем понимать дизъюнктивную (или конъюнктивную) форму функции, членами которой служат только изолированные (несклеивающиеся) элементарные конъюнкции (или дизъюнкции). Члены сокращенной Д(К)НФ в алгебре логики носят название простых импликант (имплицент). Не исключен случай, когда СД(К)НФ тождественно равна сокращенной форме рассматриваемой функции. 2-й этап – переход от сокращенной нормальной к тупиковой нормальной форме. Тупиковой будем называть такую нормальную дизъюнктивную (конъюнктивную) форму функции, членами которой являются простые импликанты (имплиценты), среди которых нет ни одной лишней. Термин "лишний" здесь имеет прямое значение. Лишним будем называть такой член функции, удаление которого не влияет на значение истинности этой функции. Возможны случаи, когда в сокращенной форме не оказывается лишних членов. Тогда сокращенная Д(К)НФ тождественно равна тупиковой форме. Не исключены случаи появления нескольких тупиковых форм из одной сокращенной. Название «тупиковая форма» показывает, что дальнейшая минимизация в рамках нормальных форм уже невозможна.

     3-й  этап - переход от тупиковой (минимальной  среди нормальных форм) формы  функции к её минимальной форме.  Этот этап, называемый обычно  факторизацией, уже не является  регулярным, как два предыдущих, и требует определенной сноровки, интуиции и опыта. Здесь подразумевается поиск возможностей упрощения функции методом проб и испытаний. Для уменьшения числа операций отрицания следует применять законы инверсии. 

1.3. Логические основы построения цифровых автоматов 

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

     Аппарат алгебры логики (булевой алгебры) создан в 1854 г. Джорджем Булем как попытка изучения логики мышления математическими методами. Впервые практическое применение булевой алгебры было сделано Шенноном в 1938 году для анализа и разработки релейных переключательных сетей, результатом чего явилась разработка метода представления любой сети, состоящей из совокупности переключателей и реле, математическими выражениями и принципов их преобразования на основе правил булевой алгебры. Ввиду наличия аналогий между релейными и современными электронными схемами аппарата булевой алгебры нашел широкое применение для их структурно-функционального описания, анализа и проектирования. Использование булевой алгебры позволяет  не только более удобно оперировать с булевыми выражениями (описывающими те или иные электронные узлы), чем со схемами или логическими диаграммами, но и на формальном уровне путем эквивалентных преобразований и базовых теорем упрощать их, давая возможность создавать экономически и технически более совершенные электронные устройства любого назначения.                

     Аппарат булевой алгебры состоит из трех  составных частей:

• элементов (0,1 или  И, Л)
• операций над ними (базовые - конъюнкция, дизъюнкция, отрицание)
• аксиом и законов (отрицания, коммутативности, дистрибутивности, де Моргана и др.)

1.4. Понятие об информации и ее преобразованиях 

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

     Существуют  два различных подхода к изучению явлений с информационной точки зрения: непрерывный и дискретный. При непрерывном подходе все изучаемые явления рассматриваются как переменные векторные поля. Задание информации состоит в выборе какого-либо определенного (переменного) поля из фиксированной за-19 ранее совокупности таких полей. Характерным для непрерывного подхода являетсят то, что все описывающие явление величины (компоненты векторов, пространственные и временные координаты) являются вещественными числами и могут изменяться непрерывно. При дискретном подходе также имеют дело с переменными векторными полями. Однако, в отличие от предыдущего случая, компоненты векторов, а также пространственные и временные координаты принимают дискретные ряды значений. Наиболее употребительным является случай, когда число значений принимаемых компонентами векторов и пространственными координатами конечно (поле задано в конечном числе точек).

     Задание информации при дискретном подходе  сводится, таким образом, к заданию конечных последовательностей конечнозначных (постоянных) векторных полей. Если дискретная информационная задача фиксирована, то количество различных постоянных векторных полей, возможных в этой задаче, в соответствии с принятыми условиями конечно. Вводя для каждого такого поля специальное буквенное обозначение, мы получаем возможность задавать информацию конечными последовательностями букв. Подобный способ задания дискретной информации условимся называть алфавитным, совокупность элементарных символов (букв), из которых составляется информация – алфавитом, а конечные последовательности букв алфавита – словами в данном u1072 алфавите. Понятие слова в алфавите существенно отличается от понятия слова в обычном языке даже в том случае, когда исходный алфавит совпадает, например, с русским алфавитом. Различие заключается в том, что в силу принятых нами определений, мы будем называть словами не только все фактически существующие слова русского языка, но также и любые бессмысленные сочетания букв. Алфавитный способ задания информации является достаточно универсальным. Действительно, этим способом можно осуществить представление любой дискретной информации. Что же касается информации, задаваемой в непрерывной форме, то на практике, применяя методы аппроксимации, ее всегда можно представить с любой степенью точности в дискретной форме. С точки зрения устройства, воспринимающего информацию, любая непрерывная информация сводится, фактически, к дискретной, а следовательно, в конечном счете, к алфавитной информации. Отсюда следует универсальность алфавитного способа задания информации. Роль дискретных (алфавитных) методов задания информации особенно возросла после того, как появились мощные автоматы для преобразования дискретной информации (ЭВМ с программным управлением).

     Подобно тому, как со всяким явлением в природе  или в обществе связана несущая этим явлением информация, взаимосвязь явлений приводит к понятию о преобразовании информации. Предположим, что любое явление á из некоторого класса А явлений влечет за собой некоторое определенное явление â из того же самого или любого другого класса В явлений. В таком случае говорят, что нам задано преобразование информации. Следовательно, с абстрактной точки зрения преобразование информации есть ни что иное, как отображение одного класса явлений в другой класс явлений. Стрелка «→» здесь служит в качестве знака преобразования информации, или, говоря иначе, в качестве обозначения отображения явления в явление. Если подобное отображение осуществляется каким-либо определенным объектом, то этот объект называется преобразователем информации. Например, обыкновенный радиоприемник, с информационной точки зрения, представляет собой преобразователь информации, осуществляющий преобразование информации, заданной в виде радиоволн, в информацию, задаваемую с помощью звуковых колебаний. Человек, решающий какую-либо задачу, также может рассматриваться как преобразователь информации: входной информацией в этом случае является условие задачи, а выходной – ответ. 

1.5. Преобразование алфавитной информации 

     В соответствии с высказанными ранее  соображениями будем рассматривать исключительно дискретно заданную алфавитную информацию и ее преобразования. В наиболее общем виде преобразование алфавитной информации может быть задано следующим образом. Пусть нам даны два конечных алфавита Х = (х1, х2, ..., хm) и Y = (y1, y2, ..., yn). Обозначим через F = F(х1, ..., хm) совокупность всех слов конечной длины в алфавите Х, а через G = G(y1,..., yn) – совокупность всех слов конечной длины в алфавите Y. Если исходная информация записывается в алфавите Х, а конечная информация – в алфавите Y, то произвольное преобразование информации ϕ будет представлять собой отображение множества F в множество G. В дальнейшем мы будем рассматривать лишь детерминированные преобразования информации, при которых входное слово полностью определяет слово на выходе преобразователя. Это требование есть ни что иное, как требование однозначности отображения.

     В самом общем случае целесообразно  считать преобразование информации частичным отображением. Иначе говоря, задавать отображение не обязательно на всем множестве F, а лишь на части этого множества (не исключая, впрочем, случай совпадения этой части со всем множеством F). Введение частичных отображений позволяет вместо отображений одного множества слов в другое рассматривать лишь отображения таких множеств в себя. Для этой цели достаточно u1074 ввести объединенный алфавит Z = (х1, ..., хm, y1,..., yn) и множество Н = Н(х1, ..., хm, y1,..., yn) слов над этим алфавитом. Теперь вместо отображения множества F в множество G можно рассматривать частичное отображение множества Н в себя. Это частичное отображение будет определено для слов, состоящих только из букв х1, х2, ..., хm. Однозначность отображения множества F в множество G не означает, вообще говоря, однозначности обратного отображения. Если такая однозначность имеет место, то отображение называется взаимно однозначным. В этом случае отображение ϕ осуществляет эквивалентное преобразование информации. В случае эквивалентного преобразования заключительная (выходная) информация полностью определяет исходную (входную) информацию. Преобразование информации в произвольном конечном алфавите заключается в зеркальном отображении слов: это преобразование эквивалентно. Пример 2. В алфавите, состоящем из всех десятичных цифр и знака суммы, задается отображение слов вида a + b, где а и b – целые числа, преобразуемые в сумму этих двух чисел. Например, слово 2 + 5 преобразуется в слово 7.Легко видеть, что это преобразование не эквивалентно, поскольку задание суммы не определяет слагаемых. Со всяким преобразованием информации связывается представление о его сложности. По критерию сложности целесообразно выделить простейшие преобразования информации. Простейшими или побуквенными, будем называть преобразования, заключающиеся в замене каждой буквы исходного алфавита некоторой определенной комбинацией букв нового алфавита, имеющего заранее фиксированную, одинаковую для всех букв длину. Пример 3. Исходная информация – произвольное слово в русском алфавите. Преобразование информации состоит в замене каждой буквы алфавита порядковым номером, записанным в десятичной системе счисления. При этом для соблюдения условия равенства длин комбинаций буквенного алфавита, представляющих буквы старого _________алфавита, необходимо первую букву обозначать комбинацией 01, вторую – 02 и т. д. В результате такого преобразования слово «дом» преобразуется в слово «051412». Это преобразование является не только простейшим, но и эквивалентным.

     Пример 4. Исходная информация – произвольное целое десятичное число (слово в алфавите, состоящем из десяти цифр 0, 1, 2, ..., 9). Преобразование информации состоит в замене каждой четной цифры нулем, а нечетной – единицей. Слово «125» при этом преобразуется в слово «101», слово «0342» – в слово 0100 и т. д. Отсюда видно, что с помощью простейших преобразований, информацию, заданную в любом конечном алфавите, можно записать в алфавите, содержащем только две буквы. Такой алфавит называют «двоичным алфавитом», а две его буквы будем обозначать нулем и единицей. Эти преобразования носят специальное название двоичного кодирования исходной информации. Таким образом, при различных преобразованиях информации можно, не нарушая общности, предполагать, что как исходная, так и заключительная информация задана в некотором стандартном (например, двоичном) алфавите. 

1.6. Способы задания автоматов 

     Абстрактные автоматы задаются с помощью таблиц переходов (выходов), графов, матриц переходов. Таблица переходов (таблица выходов) автомата Мили представляет собой таблицу, в которой левый столбец обозначается входными сигналами, а верхняя строка – состояниями, начиная с начального состояния. На пересечении строки и столбца указывается следующее состояние, в которое переходит автомат (в таблице переходов) или выходной сигнал, выдаваемый им (в таблице выходов). Представим автоматы Мили и Мура табличным способом. Описание работы автомата Мили таблицами переходов и выходов иллюстрируется на примере автомата А1 (рис. 1.5): Х – алфавит входных сигналов; Y – алфавит

     выходных  сигналов; Q – алфавит состояний.

     Автомат, имея один вход и один выход, работает в дискретном времени, принимающем значения t = 1, 2, 3, ... На вход автомата поступают входные сигналы xf (например, сигналы x1 и x2). В каждый момент t автомат находится в некотором состоянии q(t), начиная с начального состояния q1. На пересечении столбца qm и строки xf в таблице переходов ставится состояние qs, в которое автомат переходит из состояния qm под действием сигнала xf , а в таблице выходов – соответствующий этому переходу выходной сигнал yg. Иногда при задании автоматов Мили используют одну совмещенную таблицу переходов и выходов, в которой на пересечении столбца qm и строки xf записываются в виде qs / yg следующее состояние и выдаваемый выходной сигнал. На рис.1.представлена совмещенная таблица автомата А1.

     q1 q2 q3

     x1 q2 / y1 q3 / y3 q2 / y3

     x2 q3 / y2 q2 / y1 q1 / y1

     Рис. 1.Совмещенная таблица автомата А1

     Так как в автомате Мура выходной сигнал зависит только от внутреннего состояния и не зависит от входного сигнала, то он задается одной отмеченной таблицей переходов, в которой каждому ее столбцу приписан, кроме состояния qm еще и выходной сигнал yg, соответствующий этому состоянию. Пример табличного описания автомата Мура А2 (рис. 1.1).

     Для частичных автоматов, у которых  функции или определены не для всех пар (qm, xf) Q x X, на месте неопределенных состояний и выходных сигналов ставится прочерк.

     y1 y1 y3 y2 y3 q1 q2 q3 q4 q5

     x1 q2 q5 q5 q3 q3

     x2 q4 q2 q2 q1 q1

     Часто автомат задают с помощью графа  автомата. Граф автомата – ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Две вершины графа автомата qm и qs (исходное состояние и состояние перехода) соединяются дугой, направленной от qm к qs, если в автомате имеется переход из qm в qs, т. е. если qs при некотором xf Х. Данной дуге (qm , qs) приписывается входной сигнал xf и выходной сигнал yg. При этом выходной сигнал yg записывается внутри вершины qm или рядом с ней. Любой автомат может быть задан с помощью графа, но не всякий граф в алфавитах Q, X, Y задает автомат. В графе автомата не должно существовать двух дуг с одинаковыми входными сигналами, выходящих из одной и той же вершины (условие однозначности). Иногда применяется способ задания автомата с помощью матрицы переходов и выходов, которая представляет собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из состояния qm под действием входного сигнала xf в состояние qs, с выдачей выходного сигнала yi, то на пересечении строки qm и столбца qs записывается пара xf / yi.

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

2. Практическая часть.  Синтез цифровых  автоматов определяющих  заданную последовательность 

2.1. Заданная бинарная  последовательность

1₁₀ = (0000001)₂

2.2. Граф

      0 
 
 

Рис. 1.

2.3. Таблицы 

Таблица 1. переходов 

Таблица 2. выходов 

Таблицы 3. переходов в двоичную систему счисления 

Таблица 4. выходов 

S₀  - 000

S₁ - 001

S₂  - 010

S₃  - 011

S₄  - 100

S₅  - 101

S₆  - 110