Синтез цифрового автомата с 'жесткой логикой'

Синтез цифрового автомата с 'жесткой логикой'

ВВЕДЕНИЕ

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

Более подходящий пример - команды в операционной системе Unix, каждая их которых - конечный автомат. Конечный автомат - абстракция, которая позволяет не рассматривать динамические состояния, которые возникают во время переходных процессов. Конечный автомат рассматривает состояния перед началом и после завершения перехода, в промежуточные моменты времени конечно-автоматное описание невозможно. Методы конструирования реальных устройств позволяют рассматривать конечно-автоматное описание как описание функции автомата, а переходные процессы учесть и скрыть от внешнего мира. Если эта задача решена, то можно рассматривать устройство как конечный автомат. Еще более простое соотношение между конечным автоматом и программой. Любой конечный автомат может быть представлен программой. Мы будем употреблять термин «цифровой автомат» для устройств, которые реализуют действий над числами. Это сумматоры, умножители, делители, устройства для извлечения корня, вычисления тригонометрических функций и других операций, которые разработчик считает нужным реализовать аппаратно. Отличия цифрового автомата от конечного автомата общего вида состоят в следующем: он предназначен для представления чисел и выполнения операций над ними, в нем на самом первом этапе, этапе синтеза одноразрядного или многоразрядного сумматора, решается проблема гонок (порождаемых задержками), цифровой автомат имеет погрешность представления - погрешность, которая возникает при представлении счетных или несчетных числовых систем из-за ограниченного количества разрядов и памяти.

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

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

. СТРУКТУРНАЯ СХЕМА ЦИФРОВОГО АВТОМАТА

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

Рисунок 1-Структурная схема цифрового автомата.

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

. АЛГОРИТМ ФУНКЦИОНИРОВАНИЯ ЦИФРОВОГО АВТОМАТА В МИКРООПЕРАЦИЯХ

цифровой автомат кодирование сигнал

Для решения поставленной задачи в состав операционного устройства ЦА входят следующие элементы:

счетчик Сч1 - для счета циклов;

счетчик Сч2 - для счета количества четных элементов массива;

счетчик СчЗ - для счета количества нечетных элементов массива;

регистр RG1 - для хранения элементов массива;

сумматор SM1 - для определения суммы четных элементов массива;

регистр RG2 - для хранения суммы четных элементов массива;

сумматор SM2 -для определения суммы нечетных элементов массива;

регистр RG3 - для хранения суммы нечетных элементов массива.

Алгоритм функционирования цифрового автомата в микрооперациях представлен на рисунке 2.

Рисунок 2 Алгоритм функционирования ЦА в микрооперациях

Под действием управляющего сигнала y₁ в счетчик Сч1 записывается n, соответствующее числу элементов массива.

Под действием управляющего сигнала у₂ счетчики Сч2 и СчЗ устанавливаются в нулевое состояние. Под действием управляющего сигнала у₃ в регистр RG1 поочередно записываются элементы проверяемого массива, и формируется признак x_l. Признак x_l=0 для четных элементов, признак x_l=l для нечетных элементов.

В сумматоре SM1 складываются четные элементы. Под действием управляющего сигнала у₄ сумма четных элементов записывается в регистр RG2. под действием управляющего сигнала у₅ к содержимому Сч2 прибавляется 1.

В сумматоре SM2 складываются нечетные элементы массива. Под действием управляющего сигнала у₆ сумма нечетных элементов записывается в регистр RG3. Под действием управляющего сигнала у₇ к содержимому СчЗ прибавляется 1.

Под действием управляющего сигнала y₈ из содержимого Сч1 вычитается 1 и формируется признак х₂. Признак х₂=1, если содержимое счетчика Сч1 равно нулю и признак х₂=0, если содержимое Сч1 не равно нулю.

. СТРУКТУРНАЯ СХЕМА ОПЕРАЦИОННОГО УСТРОЙСТВА

В состав операционного устройства входят: в качестве счетчика Сч1 - микросхема К531ИЕ16, в качестве счетчиков Сч2 и Сч3 - микросхема - К555ИЕ11, в качестве регистровRG1, RG2, RG3 - микросхемы К555ИР11, в качестве сумматоров SM1,SM2 - микросхема ИМ. Структурная схема операционного устройства представлена на рисунке 3.

Под действием управляющего сигнала y₁ в счетчике Сч1 должен быть организован режим параллельной загрузки. Для этого необходимо на входы подать сигналы: =лог. «0», С = (положительный перепад напряжения). На информационные входы D необходимо подать двоичный код, соответствующий числу n = 14, т.е. D₀ =лог. «0», D₁=1, D₂=1, D₃=1.

Под действием управляющего сигнала у₂ в Сч2 и СчЗ должен быть организован режим сброса. Для этого необходимо на входы подать сигналы: =лог. «0», С =.

Рисунок 3 Структурная схема операционного устройства

Под действием управляющего сигнала у₃ в регистре RG1 должен быть организован режим параллельной загрузки. Для этого необходимо на входы регистра RG1 подать сигналы:=лог. «0», С = ↓. На выходе Q_o регистра RG1 формируется признак x_l. Для четных элементов массива x_l = лог. «0», для нечетных элементов массива x_l = лог. «1». Выходы Q_o - Q₃ регистраRG1 через элементы «И» соединены со входами В₀ -В₃ сумматоров SM1,SM2.

Под действием управляющего сигнала у₄ с помощью схемы «И» четный элемент массива передается в сумматор SM1и в регистре RG2 осуществляется режим параллельной загрузки. Для этого необходимо на входы регистра RG2 подать сигналы: =лог. «0», С = ↓.

На входы А₀ -А₃ сумматора SM1 подаются сигналы в выходов Q_o - Q₃ регистраRG2. В комбинационной схеме сумматора накапливается сумма четных элементов массива «А» и результат записывается регистр RG2. Для этого выходы сумматора SM1S₀ - S₃ (F₀ - F₀для микросхемы К155ИП3) соединены со входами D₀ -D₃ регистра RG2.

Так как в качестве сумматора SM1 используется арифметико-логическое устройство К155ИП3, то для организации режима сложения при активных высоких уровнях на входы необходимо подать сигналы: M=S₁= S₂= S₃=лог. «0», С_n=S₀ = лог. «1».

Под действием управляющего сигнала у₅ в Сч2 должен быть организован режим счета на увеличение. Для этого необходимо на входы счетчика Сч2 подать сигналы: =1, С = , СЕР =СЕТ = = лог «1». На выходах Q_o - Q₃ счетчика Сч2 формируется количество четных элементов массива «А».

Под действием управляющего сигнала у₆ с помощью схемы «И» нечетный элемент массива передается в сумматор SM2 и в регистре RG3 осуществляется режим параллельной загрузки. Для этого необходимо на входы регистра RG3 подать сигналы: =лог. «0», С = ↓.

На входы А₀ -А₃ сумматора SM2 подаются сигналы в выходов Q_o - Q₃ регистраRG3. В комбинационной схеме сумматора накапливается сумма нечетных элементов массива «А» и результат записывается регистр RG3. Для этого выходы сумматора SM2 S₀ - S₃ (F₀ - F₀для микросхемы К155ИП3) соединены со входами D₀ -D₃ регистра RG3.

Так как в качестве сумматора SM2 используется арифметико-логическое устройство К155ИП3, то для организации режима сложения при активных высоких уровнях на входы необходимо подать сигналы: M=S₁= S₂= S₃=лог. «0», С_n=S₀ = лог. «1».

Под действием управляющего сигнала у₇ в Сч3 должен быть организован режим счета на увеличение. Для этого необходимо на входы счетчика Сч3 подать сигналы: =1, С = , СЕР =СЕТ = = лог «1». На выходах Q_o - Q₃счетчика Сч3 формируется количество нечетных элементов массива «А»

Под действием управляющего сигнала y₈ в Сч1 должен быть организован ражим счета на уменьшение. Для этого необходимо на входы счетчика Сч1 подать сигналы: = ==лог. «0», =лог. «1», С =.

На выходе переноса при счете на уменьшение ТС_d формируется признак х₂.

. СИНТЕЗ ЦИФРОВОГО АВТОМАТА

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

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

Алгоритм функционирования ЦА в микрокомандах представлен на рисунке 4.

Рисунок 4 Алгоритм функционирования ЦА в микрокомандах.

В микрокоманду Y₁ входят управляющие сигналы у₁ , у ₂ . В микрокоманду Y₂ входит управляющий сигнал у₃. В микрокоманду Y₃ входят управляющие сигналы у₄, y_{5 .} В микрокоманду Y4 входят управляющие сигналы у₆, у₇. В микрокоманду Y5 входит управляющий сигнал у₈. Символами а_о обозначим начало и конец алгоритма. Символами а₁ а₂, а₃, а₄, a₅ обозначают операторные блоки. Символы a_o-a₅ соответствуют состояниям ЦА.

.2 Граф функционирования цифрового автомата

Граф функционирования ЦА строится на основе алгоритма функционирования в микрокомандах. В узлах графа записываются состояния ЦА, стрелками показывают возможные переходы, над стрелками записывают условия перехода, а выделенные стрелки соответствуют безусловным переходам.

Граф функционирования ЦА представлен на рисунке 5.

Рисунок. 5 Граф функционирования цифрового автомата.

Из состояния а_о выполняется безусловный переход в состояние а_1. Из состояния a₁ выполняется безусловный переход в состояние а₂. Из состояния а₂ при условии xl=0 выполняется переход в состояние а₃ , а при условии x1=1 выполняется переход в состояние а₄. Из состояний а₃ и а₄ выполняются безусловные переходы в состояние а₅. Из состояния а₅ при условии х2=0 выполняется переход в состояние а₂, а при х2=1 выполняется переход в состояние а_о.

.3 Кодирование состояний

Для кодирования состояний ЦА выберем триггеры. Необходимое количество триггеров выберем из условия минимального n, удовлетворяющего соотношению (1).

(1)

гдеn - количество триггеров,- количество состояний цифрового автомата.

Для N=6, n=3. Каждому состоянию ЦА поставим в соответствие комбинацию состояний триггеров. Кодирование состояний ЦА представлено в таблице 1.

Таблица 1. Кодирование состояний цифрового автомата

.4 Таблица функционирования

Функционирование ЦА можно представить в виде таблицы построенной на основе графа функционирования. В каждой строке таблицы описывается определенный переход графа и сигналы управления триггерами, необходимые для данного перехода.

В качестве триггеров выберем RS - триггеры (микросхема К155ТР2), имеющие инверсные входы R и S. Необходимо учесть, что для перевода RS-триггера из нулевого состояния в единичное, необходимо активный логический уровень (лог. «0») подать на вход S, а для перевода RS- триггера из единичного состояния в нулевое необходимо активный логический уровень (лог. «0») подать на вход R.Функционирование ЦА представлено в таблице 2.

Таблица 2. Функционирование цифрового автомата

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

В каждом состоянии ЦА формируется соответствующая микрокоманда Y. Для микрокоманд Y можно записать логические выражения (2-6).

 (2)

 (3)

 (4)

 (5)

 (6)

Логические выражения для сигналов управления триггерами запишем как простую дизъюнкцию конъюнкций текущих состояний и условий перехода, при которых эти сигналы получаются. Сигналы управления триггерами соответствуют логическим выражениям (7-12).

 (7)

 (8)

 (9)

 (10)

 (11)

 (12)

.6 Схема управляющего устройства

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

Дешифратор служит для преобразования кодовых комбинаций с выходов триггеров в состояния цифрового автомата a_o-a₅.

Комбинационный узел служит для формирования сигналов управления триггерамиS₀,R₀, S₁,R₁, S₂,R₂ и строится в соответствии с логическими выражениями (7-12).

Регистр состояний формирует кодовые комбинации состояний цифрового автомата. Он построен на трех RS триггерах с инверсными входами. Схема управляющего устройства представлена на рисунке 6.

Рисунок 6. Схема управляющего устройства

В качестве дешифратора используется микросхема К155ИД12.

Выходы триггеров Т1 Т2, Т3 соединены со входами Ао, А1 А2 дешифратора. Кодовая комбинация с выходов триггеров преобразуется в дешифраторе в активный логический уровень одном из выходов 0-5, что соответствует состояниям цифрового автомата a_o-a₅. Для выполнения функции дешифрации на вход запрета V должен действовать сигнал V= лог. «0».

Цепи соответствующие состояниям ЦА и линии, по которым приходят признаки X1 и Х2 из операционного устройства объединены в «жгут» и пронумерованы от1 до 9.

Управляющее устройство построено с использованием следующих интегральных микросхем: DD 1-К155ИД12DD2-K155ЛH1, DDЗ-К155ЛИ1, DD4-К155ЛЕ4, DD5-K155ЛE1, DD6-K555TP2.

.7 Проверка управляющего устройства

Проверка переходов ЦА выполняется с использованием логических выражений (7-12) и схемы управляющего устройства.

Возможные переходы ЦА представлены в таблице 3.

В исходном состоянии =1 на триггеры действуют управляющие сигналы S2=R2=S1=R1=R0=0 и S0-1. При таких управляющих сигналах триггеры T1 и Т2 сохраняют нулевое состояние, а триггер Т0 переходит в единичное состояние и ЦА приходит в состояние .

При =l на триггеры действуют управляющие сигналы S2=R2=R1=S0=0 и S1=Ro=l. При таких управляющих сигналах триггер Т2 сохраняет нулевое состояние, триггер T1 переходит в единичное состояние, а триггер Т0 переходит в нулевое состояние и ЦА переходит в состояние .

Таблица 3 Переходы цифрового автомата

При =1 и условии X₁=0 на триггеры действуют управляющие сигналы S2=R2=S1=R1=R0=0 и S0=l. При таких управляющих сигналах триггер Т2 сохраняет нулевое состояние, триггер T1 сохраняет единичное состояние, а триггер Т0 переходит в единичное состояние и ЦА переходит в состояние а3.

При =1 и условии X₁=1 на триггеры действуют управляющие сигналы S2=R1=l и R2=S1=S0=R0 =0. При таких управляющих сигналах триггер Т2 переходит в единичное состояние, триггер Т1 переходит нулевое состояние, триггер Т0 сохраняет нулевое состояние и ЦА переходит в состояние .

При =1 на триггеры действуют управляющие сигналы S2=R1=l и R2=S1=S0=R0=0. При таких управляющих сигналах триггер Т2 переходит в единичное состояние, триггер T1 переходит в нулевое состояние, триггер Т0 сохраняет единичное состояние и ЦА переходит в состояние .

При =1 на триггеры действуют управляющие сигналы S2=R2= S1=R1=R0=0 и S0=l. При таких управляющих сигналах триггер Т2 остается в единичном состоянии, триггер Т1 сохраняет нулевое состояние, а триггер T0 переходит в единичное состояние и ЦА переходит в состояние .

При = 1 и условии =0 на триггеры действуют управляющие сигналы S2=R1=S0=0 и R2=S1=R0=l. При таких управляющих сигналах триггеры Т2 и Т0 переходят в нулевое состояние, а триггер Т1 переходит в единичное состояние и ЦА переходит в состояние .

При =1 и условии =l на триггеры действуют управляющие сигналы S2=S1=R1=S0=0 и R2=R0=l. При таких управляющих сигналах триггеры Т2 и Т0 переходят в нулевое состояние, а триггер Т1 сохраняет нулевое состояние и ЦА переходит в состояние а_о.

.8 Проверка операционного устройства

Проверка операционного устройства для исходных данных n=15 и 14, 6, 9, 11, 4, 2, 8, 5, 3, 1, 7, 10, 12, 13, 4 представлена в таблице 4.

Таблица 4 Проверка операционного устройства