Проектирование цифрового автомата, определяющего заданную двоичную последовательность равную: 010000

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

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

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

В самом  общем виде последовательность структурного синтеза последовательностного  цифрового автомата можно представить  следующим образом.

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

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

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

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

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

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

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

Элементарный  автомат. Триггерный элемент

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

Триггер имеет два выходных сигнала Q и Q. Сигнал Q считается истинным или прямым, а сигнал Q - дополнительным или инверсным. Этим сигналам соответствует один из двух уровней напряжения: L или H, и они дополняют друг друга. Выходные сигналы триггера постоянны до тех пор, пока они не будут изменены под воздействием входных сигналов, т.е. триггер имеет два устойчивых состояния (режима): Q = H и Q = L или Q = L и Q = H. Первое из них когда Q = H называется состоянием установки, а второе – состоянием сброса. Предположим, что для триггера используется положительная логика. Тогда состояниям установки и сброса ставятся в соответствие логические состояния «1» и «0».

Существуют различного типа триггерные схемы, в частности, типа: D, T, RS, JK. Для каждого из них имеется однозначное соответствие между входными сигналами и соответствующими переходами состояний триггера.

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

Синтез  логических схем с одним выходом

Перед тем как перейти к примерам синтеза композиционных логических схем рассмотрим способы использования  универсальности вентилей И-НЕ и  ИЛИ-НЕ.

 

Свойство универсальности вентиля  ИЛИ-НЕ:

 

Рис. 4

Свойство универсальности вентиля  И-НЕ:

Рис. 5

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

Рассмотрим некоторые простые  примеры перехода от логических уравнений  к логическим цепям, т.е. примеры  синтеза простых логических цепей. В частности, рассмотрим переход  от представления функции в НДФ (ДНФ) к ее реализации на элементах  И-НЕ и ИЛИ-НЕ.

Пусть задана функция 4-х переменных в НДФ:

F =CD +ABD + ABD +ABC + ACD.

Минимальная НДФ имеет вид: F = ABD + ABD + C.

Рассмотрим реализацию этого уравнения  с помощью элементов И-НЕ. В  общем случае на элементах И-НЕ НДФ  функция реализуется посредством  двух ступеней логики. На первой ступени  получаются инверсные значения логических произведений и однобуквенных членов. На второй ступени выполняются операции И-НЕ, т.е. НЕ-ИЛИ, над полученными  инверсиями.

Схема, соответствующая данному  уравнению, приведена ниже.

Рис. 6

В приведенной схеме для элементов  первой и второй ступени применены  различные, но эквивалентные условные обозначения. При реализации НДФ  функции посредством элементов  И-НЕ такой прием позволяет вести  проектирование схем, пользуясь операциями И, ИЛИ и НЕ.

По рассмотренным ранее правилам из вышеприведенной карты Карно, может быть найдена минимальная  НКФ заданной функции:

F = (C +D)(A +B +C)(A + B +C).

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

Рис. 7

При минимизации логических функций  для логических схем, которые предполагается строить на базе элементов И-НЕ или  ИЛИ-НЕ, необходимо кроме собственно минимизации стремиться также к  тому, чтобы структурная формула  была представлена в виде комбинации из элементов И-НЕ или ИЛИ-НЕ. Тогда  переход от структурной формулы  к функциональной схеме не будет  сложным. В любом случае при построении логической схемы в базисе И-НЕ на основе логической функции, представленной в МНДФ, необходимо везде вместо элементов И и ИЛИ ставить  элемент И-НЕ. При построении логической схемы в базисе ИЛИ-НЕ на основе логической функции, представленной в МНКФ, необходимо везде вместо элементов И и  ИЛИ ставить элемент ИЛИ-НЕ. Однако надо учесть, что есть точка зрения, по которой считается, что наиболее удобным для решения синтеза  схем цифровых автоматов является базис  И, ИЛИ, НЕ.

Алгоритм  функционирования цифрового автомата

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

Процессорное   устройство   описывается   множеством   входных   сигналов являющихся исходными данными. Множеством результатов  Z1-Zm,  управляющее устройство   вырабатывает   множество   управляющих    сигналов    y1-yn, операционное устройство вырабатывает множество признаков X1-Xs,  которые позволяют изменить  последовательность   выполненных   микрокоманд.   Напоследовательность выполнения микрокоманд так же влияют внешние  признаки

В состав процессорного  устройства входят регистры, счетчики и дешифратор. Пусть регистр Р1 хранит число А. В регистр Р2 поочередно заносятся элементы проверяемого массива, счетчик 1 служит для подсчета числа  циклов. Счетчик 2 служит для подсчета числа элементов =А. Дешифратор используется для формирования признака х. Алгоритм функционирования автомата в микрооперациях представлен на рис.2

Под действием  управляющего сигнала y1 в регистр Р1 записывается проверяемое число х. Под действием управляющего сигнала y2 в регистр R2 записывается число B. Под действием управляющего сигнала y3 в регистре R3 записываются число А ив сумматоре 1 сравнивается числа Аи х.  На выходе переноса сумматора вырабатывается признак х. Если х<А то признак х=1 и выполняется переход на формирование управляющего сигнала y5, если наоборот то х=0 и выполняется переход на формирование управляющего импульса у4.  Под действием управляющего сигнала y5 в сумматоре 2 должен быть организован режим сложения и в нем вычисляется х+В. Под действием управляющего сигнала у4 в сумматоре должен быть организован режим вычитания и вычисляется х-В. Под действием управляющего сигнала у6 результат полученный в сумматоре 2 записывается в регистр R4.

 

. Рис. 8

Практическая часть

 

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

№ =16

(16)₁₀ = (010000)₂

S0, S1, S2, S3, S4, S5, S6 – внутреннее состояние

Х - входной  алфавит

У - выходной алфавит

S₀ - начальная вершина

S_i–внутренний алфавит

λ - Функция переходов

β – Функция выходов

S₀ = 000

S₁ = 001

S₂ = 010

S₃ = 011

S₄ = 100

S₅ = 101

S₆ = 110

 

 

 

 

 

 

 

 

 

  

 

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

Входное состояние       Внутреннее состояние	Х=0	Х=1
S0	S4	S0
S1	S1	S2
S2	S3	S0
S3	S4	S2
S4	S5	S2
S5	S6	S2
S6	S1	S0

 

 

 

 

 

 

 

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

 

 

Входное                             состояние       Внутреннее     состояние	Х=0	Х=1
S0	У0	У0
S1	У0	У0
S2	У0	У0
S3	У0	У0
S4	У0	У0
S5	У1	У0
S6	У0	У0

 

 

 

 

 

 

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

 

Входное состояние   Внутреннее     состояние	Х=0	Х=1
S0	S1 у0	S0 у0
S1	S1 у0	S2 у0
S2	S3 у0	S0 у0
S3	S4 у0	S2 у0
S4	S5 у1	S2 у0
S5	S6 у0	S2 у0
S6	S1 у0	S0 у0