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

Содержание

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

1. ТЕМА КУРСОВОГО ПРОЕКТА. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4                                                                                                      

2. ОСНОВНЫЕ ПОНИТИЯ ЦИФРОВОГО АВТОМАТА . . . . . . . . . . . . . . . . .5

3. ГРАФ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7                                                                                                       

4. ТАБЛИЦЫ ИСТИННОСТИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9                                                                  

4.1. Таблица цифрового автомата . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9                                                                                        

4.2. Совмещённая таблица . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10                                                                                

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

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

4.5. Таблица кодирования  состояний. . . . . . . . . . . . .  . . . . . . . .  . . . . . . . . . . .12

4.6. Таблица переходов в двоичном коде. . . . . . . . . . . . . . . . . . .  . . . . . . . . .. .12

4.7. Совмещенная  таблица в двоичном коде. . . . . . . . . . . . . . . . . . . . . . . . .  . .13

5. МИНИМИЗАЦИЯ КАРТАМИ КАРНО . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14                                             

6. МИНИЗИРОВАННЫЕ ФУНКЦИИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19

7. ПЕРЕВОД В БАЗИС (ИЛИ – НЕ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21

8. ТРИГГЕРЫ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

9. КОМБИНАЦИОННАЯ СХЕМА АВТОМАТА . . . . . . . . . . . . . . . . . . . . . . .27                                               

Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

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

Введение 

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

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

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

      Прежде  всего, различают двоичное и двоично-десятичное представления чисел. В двоичном представлении используется двоичная система счисления с фиксированным числом двоичных разрядов (чаще всего 32 или, для малых ЭВМ, 16 разрядов, включая разряд для представления знака числа). Если нулем обозначать плюс, а единицей — минус, то 00001010 означает целое число +(2³+2^l)= + l0, а 10001100— число— (2³ + 2²) = —12 (для простоты взято 8-разрядное представление). Заметим, что знак числа в машинном представлении часто оказывается удобным ставить не в начале, а в конце числа.

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

1. ТЕМА КУРСОВОГО ПРОЕКТА

Синтез цифрового  автомата определяющий заданную последовательность. Последовательность представлена в двоичном коде и состоит из 2х частей: 
1часть - код группы(1): 01

2я часть  – номер студента по списку(19) представленный в двоичном коде 5ю разрядами: 10011

Последовательность=0110011 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. ОСНОВНЫЕ ПОНЯТИЯ ЦИФРОВОГО АВТОМАТА 

              Термин «автомат», как правило  используется в двух аспектах. С одной стороны, автомат –  это устройство, выполняющее некоторые  функции без непосредственного участия человека. В этом смысле мы говорим, что ЭВМ – автомат, так как после загрузки программы и исходных данных ЭВМ решает заданную задачу без участия человека. С другой стороны, термин «автомат» как математическое понятие обозначает математическую модель реальных технических автоматов. В этом смысле автомат представляется как «чёрный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний Q = {q₁(t), q₂(t), …, q_n(t)}, в которые он под действием входных сигналов переходит скачкообразно, т.е. практически мгновенно, минуя промежуточное состояние. Конечное, это условие не выполняется в реальности, так как любой переходный процесс длится конечное время.

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

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

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

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

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

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

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

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

3. ГРАФ 

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

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

          Это определение можно сформулировать  иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек

         Граф автомат – ориентированный  граф, вершины которого соответствуют состояниям, а дуги – переходам между ними.

         Две вершины графа автомата (исходное состояние и состояние перехода) соединяются дугой. Данной дуге приписывается входной и выходной сигналы. При этом выходной сигнал записывается внутри вершины или рядом с ней.

         Любой автомат может быть задан  с помощью графа, но не всякий граф в алфавитах Q, X, Y задаёт автомат. В графе автомата не должно существовать двух дуг с одинаковыми входными сигналами, выходящих из одной и той же вершины (условие однозначности).  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4. ТАБЛИЦЫ ИСТИННОСТИ 

4.1. Таблица цифрового автомата

4.2. Совмещённая таблица 

              Иногда при задании автоматов  используют совмещённую таблицу переходов и выходов.

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

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

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

4.5 Таблица кодирования состояний 

4.6 Таблица переходов в двоичном коде 
 
 
 

4.7 Совмещенная таблица в двоичном коде

5. МИНИМИЗАЦИЯ КАРТАМИ КАРНО 

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

              При числе переменных 5 и больше  отобразить графически функцию  в виде единой плоской карты  невозможно. Тогда строят комбинированные  карты, состоящие из совокупности  более простых карт. Процедура минимизации заключается тогда в том, что сначала находится минимальная форма 4-х мерных кубов (карт), а затем, расширяя понятие соседних клеток, отыскивают min-термы для совокупности карт. Причем соседними клетками являются клетки, совпадающие при совмещении карт поворотом вокруг общего ребра.

                  Карты Карно представляют собой  прямоугольную таблицу (матрицу), разбитую горизонтальными и вертикальными линиями на клетки (ячейки). Общее число ячеек совпадает с числом минтермов и равно 2ⁿ, где n – число переменных упрощаемой функции. Минтерм – это конъюнкция (логическое произведение), в которую входят все n входных переменных в прямой или инверсной форме, а макстерм – дизъюнкция (логическая сумма), в которую также входят в прямой или инверсной форме все n переменных, образующих функцию. Таким образом, каждая ячейка карты соответствует определенному минтерму, размещение которых осуществляется таким образом, чтобы смежные минтермы находились в соседних ячейках.

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

Карта Карно для   R : 

R₁=( _{1 2})&( _{2 3})&( _{2 3}) &( _{2 3}) 

Карта Карно для S : 

S₁= & ₁&Q₂&Q₃ 
 
 
 
 

Карта Карно для   R :