Курсовая работа
На тему:
«Разработка арифметико-логическогоустройства, выполняющего операции сложения и вычитания в прямом двоичном коде»
Запорожье 2010 г.
Реферат
В данномкурсовом проекте производится разработка управляющего автомата реализующегофункции устройства для выполнения сложения и вычитания в прямых кодах с учетомзнака операндов и знака операции, каноническим методом структурного синтезацифровых автоматов.
Рассмотренабстрактный цифровой автомат Мили заданного устройства, алгоритм его работы,таблицы прошивки и возбуждения постоянного запоминающего устройства, составленыфункции возбуждения. Также составлены функциональная и электрическаяпринципиальная схемы.
Арифметико-логическоеустройство, алгоритм, абстрактный автомат, граф автомата, таблицапереходов-выходов, кодирование, ПЗУ, таблица возбуждений ПЗУ, функциявозбуждений ПЗУ, структурная схема, схема электрическая принципиальная.
цифровойустройство автомат алгоритм
Введение
Логическиеустройства, работающие с цифровым сигналом получили широкое применение вэлектронике. Стали развиваться науки связанные с цифровыми устройствами:«Цифровая схематехника», «Цифровые автоматы».
Основой всехцифровых устройств являются простейшие логические элементы, выполняющие простейшиелогические операции алгебры-логики. Все более сложные цифровые устройства можнопредставить в виде простейших устройств – логических элементов. Конструированиеэлектронных схем и эффективное применение цифровых устройств невозможно безпредставлений о принципах их действия и основных параметрах.
Структурнаясхема любого ЦА состоит из трех частей: запоминающей части с дешифратором,схемы формирования сигналов возбуждения триггеров запоминающей части, схемы формированиявыходных сигналов.
ЗУ с дешифраторомсодержит тригерный регистр, на котором могут размещаться всевозможные числа,соответствующие требуемым состояниям. Дешифратор расшифровывает число в нужныйсигнал состояния, индекс которого совпадает с величиной числа. Входные сигналы,множество которых обозначено через Х, сигналы состояний, множество которыхобозначено через S, используются для формирования сигналов возбуждениятриггеров, как для автоматов Мили, так и для автоматов Мура, а также дляформирования выходных сигналов автоматов Мили.
1.Выполнение операций сложения, вычитания в двоичном коде
Сложениечисел, представленных в двоичном коде, выполняется поразрядно, начиная смладшего разряда. В результате сложения двух первых кодов слагаемых Xo, Yo получаетсяпервый разряд суммы Sо и код переноса Pо в следующий разряд. В следующихразрядах код Si будет определяться с учетом переноса из соседнего младшегоразряда:
7 0111 5 0101
+ ── + ─────
12 1100
ОперацияВычитания в ЭВМ выполняется, так же как и сложение, но при этом отрицательныечисла представляются в дополнительном или обратном коде. Смысл переводаотрицательных чисел из прямого в дополнительный и обратный коды поясним напримере с десятичными числами.
Допустим,требуется сложить числа X1=76 и X2=-58. Заменим код отрицательного слагаемогоX2 его дополнением до 100, так чтобы [X2] доп=100+X2=42. Сложив числа X1+[X2] допполучим: Y=X1+[X2] доп=76+42=118.
Отбрасывая 1старшего разряда получим искомый результат 18. Равенство полученного результатаистинному объясняется тем, что при формировании дополнительного кода к X2 мы прибавляли100, а из результата вычитали 100 отбрасыванием старшего разряда.
Y=X1+[X2] доп-100=X1+[X2+100] –100=76+[-58+100] – 100=18.
При записидвоичного числа в прямом коде в знаковом разряде ставится его знак (0 – плюс, 1– минус), а само число записывается в естественной форме:
X=13 [X] пр=01101
10 2
X=-13 [X] пр=11101
10 2
Дополнительныйкод отрицательных двоичных чисел получается заменой двоичных кодов во всехразрядах на взаимно обратные (0 на 1, 1 на 0). После этого к младшему разрядучисла добавляется 1. В знаковом разряде отрицательного числа записывается 1.
[-14] доп=[-01110]доп=[10001+1]=10010
Кромедополнительного кода для представления отрицательных чисел используетсяобратный код. В этом случае в знаковом разряде записывается 1, а в остальныхразрядах цифры заменяются на взаимно обратные
[-14] обр=[-01110]обр=10001
Привыполнении арифметических операций с отрицательными числами производитсяпоразрядное сложение слагаемых, начиная с младшего и кончая знаковым разрядом.Если используется дополнительный код, то возможная единица переноса из знакового,разряда отбрасывается, при использовании обратного кода единица переносазнакового разряда суммируется с младшим разрядом полученной суммы. Результатвычисления получается в том коде, в каком были представлены слагаемые. Положительныечисла в прямом, обратном и дополнительном кодах имеют одну и ту же формузаписи.
2.Структурный синтез цифровых автоматов
2.1 Задачаструктурного синтеза
Процесспостроения схемы автомата обычно разделяют на две относительно независимыхстадии: абстрактный и структурный синтез. На стадии абстрактного синтеза,исходя из заданных условий работы, выполняется построение таблиц переходов ивыходов автомата. Задачей структурного синтеза является построениефункциональной схемы автомата. Исходными данными для стадии структурногосинтеза являются таблицы переходов и выходов автомата, система логическихэлементов, тип элемента памяти, а также дополнительные условия, накладываемыена качество и на работу схемы, например: время работы, допустимость риска,условия связи с внешней средой, стоимость и т.п.
Следуетотметить, что исходные данные и круг вопросов, решаемых на стадии структурногосинтеза, могут существенно изменяться. Например, в некоторых случаях приструктурном синтезе решают задачу выбора искомой схемы. В дальнейшем изложениисовокупность исходных данных и задач, а структурного синтеза предполагаютсятакими, как они описаны в начале настоящего параграфа.
2.2 Обобщеннаяструктурная схема автомата
На стадииабстрактного синтеза обычно пользуются представлением автомата в виде одногоблока, имеющего один вход и один выход. На стадии структурного синтеза автоматизображают в виде обобщенной структурной схемы, приведенной на рисунке 2.2 т nвходных и m выходных каналов, по которым в подавляющем большинстве случаевпередаются двоичные сигналы x1, x2,…, xn и z1,z2,…, zm. Переменные x1, x2,…, xnназывают входными переменными, а z1, z2,…, zm– выходными переменными или функциями выходов автомата.
/>
Рисунок 2.2. Обобщеннаяструктурная схема автомата
Рассматриваемаясхема состоит из двух частей: комбинационной схемы (КС) и набора элементовпамяти (ЭП). Переменные y1, y2,…, yh,соответствующие выходным сигналам элементов памяти, называют внутреннимипеременными автомата. Переменные y1', y2',…, yh'используются в схеме для обозначения входных сигналов, изменяющих состояниеэлементов памяти, и называют функциями возбуждения. В качестве элементовпамяти на практике чаще всего используют элементарные автоматы.
В приведеннойсхеме наборы значений входных переменных x1, x2,…, xnсоответствуют буквам входного алфавита Р абстрактного автомата, наборы выходныхпеременных z1, z2,…, zm — буквам выходного алфавитаW, y1, y2,…, yh — состояниям абстрактногоавтомата.
2.3Структурная схема с преобразователями входных и выходных сигналов
В общемслучае комбинационная схема в приведенной структурной схеме автомата можетрешать несколько различных задач. Если эту схему разбить на подсхемы так, чтобыкаждая задача решалась отдельной подсхемой, то структурная схема автомата можетбыть представлена в виде, изображенном на рис. 2.3. В этой схемекомбинационная схема КС1 вырабатывает функции выхода, КС2 – функциивозбуждения, преобразователь кодов ПК1 используется для перекодирования входныхсигналов, а преобразователь кодов ПК2 – для преобразования выходных сигналов.Наличие преобразователей кодов ПК1 и ПК2 не является обязательным в структурнойсхеме автомата, но в некоторых случаях их включение в схему позволяет добитьсяуменьшения сложности, упростить процесс построения или контроля работы схемыавтомата.
/>
Рисунок 2.3.Структурная схема с преобразователями входных и выходных сигналов
Необходимоотметить, что вид структурной схемы автомата в сильной степени зависит отиспользуемой системы логических элементов. Например, при построении схемы наэлементах с синхронизацией, сохраняющих результат логической операции домомента прихода считывающего сигнала, необходимость в элементах памяти частоотпадает. В этом случае структурная схема автомата может быть изображена ввиде, приведенном на рисунке 2.3.1.
/>
Рисунок 2.3.1.Упрощенная Структурная схема с преобразователями входных и выходных сигналов
2.4Структурная схема на элементах импульсного типа
Припостроении схемы из логических элементов импульсного типа, работающих симпульсными сигналами длительностью t, и элементов памяти с выходными сигналамипотенциального типа в структурную схему необходимо включить цепи синхронизациии линии задержки (ЛЗ), как это показано на рис. 4.
/>
Рисунок 2.4.Структурная схема с линиями задержки
Линиизадержки в такой схеме осуществляют задержку входных сигналов элементов памяти.Если время задержки (tз) этих линий немного больше величины t, тосостояние элементов памяти остается неизменным на время действиясинхронизирующего сигнала (СИ).
2.5 Основныеэтапы структурного синтеза
Процедуруструктурного синтеза удобно рассматривать, расчленив ее предварительно нанесколько связанных между собой этапов.
1.Выборструктурной схемы автомата.Этот этап синтеза во многом определяетпоследовательность построения схемы. Примеры того, как заданная системаэлементов влияет на структурную схему автомата, были приведены в предыдущемпараграфе. Структурные схемы автомата, применяемые при построении схемы напотенциальных элементах, будут рассмотрены в п. 9, а структурные схемы,использующие типовые блоки, будут описаны в п. 10. Основная трудностьэтого этапа заключается в отсутствии формальных критериев для выбораструктурной схемы. Одним из главных факторов, определяющих выбор структурнойсхемы, является опыт разработчика.
2.Кодирование входных и выходных сигналов.Кодирование входных сигналов заключается в том,что каждой букве pi входного алфавита абстрактного автоматаоднозначным образом ставится в соответствие набор значений двоичных переменныхх1, х2,…, хn. Очевидно, что кодированиеявляется однозначным, если число букв входного алфавита не превышает числаразличных двоичных наборов переменных х1, х2,…, хn.Исходя из этого, количество двоичных переменных n, необходимое для кодированияr букв входного алфавита, можно определить из условия r Ј 2n. Кодированиевыходных сигналов состоит в том, что буквам выходного алфавита wi абстрактногоавтомата аналогичным образом ставятся в соответствие наборы значений выходныхпеременных z1, z2,…, zm. Результатыкодирования обычно заносятся в таблицы кодирования входных и выходных сигналов.
В некоторыхзадачах кодирования входных и выходных сигналов задается в качестве условийработы схемы на этапе абстрактного синтеза. В таких случаях в структурную схемуавтомата могут быть включены преобразователи кодов. При этом кодированиезаключается в том, что каждому набору значений переменных х1, х2,…,хn однозначным образом ставится в соответствие набор переменных х1',х2',…, хq', а каждому набору переменных z1, z2,…,zm – набор переменных z1', z2',…, zs'.Заметим, что в качестве преобразователей кодов на практике часто используютдешифраторы. Необходимо иметь в виду, что кодирование входных и выходныхсигналов может существенно влиять на сложность комбинационной части схемы также, как и кодирование состояний автомата.
3.Выборчисла элементов памяти и кодирование состояний автомата.Кодирование состоянийзаключается в том, что каждому состоянию si О S однозначным образомставится в соответствие набор внутренних переменных у1, у2,…,уh. Состояния и соответствующие им коды обычно представляют в видетаблицы, которая называется таблицей кодирования состояний автомата.
Если автоматимеет l состояний, то, для того, чтобы получить однозначное соответствие,необходимо иметь не менее l различных двоичных кодов. Минимальное числоэлементов памяти, необходимое для получения однозначного кодирования, h=log2l.
Кодированиесостояний существенно влияет на сложность комбинационной части схемы автомата.Для того, чтобы упростить комбинационную схему, часто используют избыточноекодирование, выбирая h большим, чем это необходимо для получения однозначногокодирования. Избыточное кодирование используется также для построения схем безсостязаний. Кодирование состояний кажется целесообразным выполнять совместно скодированием входных и выходных сигналов, однако такая задача оказываетсявесьма сложной и практически не реализуется.
4.Построение функций возбуждения. Функция возбуждения yi' определяет,какой сигнал нужно подать на вход i-го элемента памяти, чтобы получить кодсостояния, в которое автомат должен перейти. Функции возбуждения приструктурном синтезе соответствуют функциям перехода абстрактного автомата. Этосоответствие показывает, что функции возбуждения должны зависеть от внутреннихпеременных y1, y2,…, yh, определяющихсостояние автомата, и входных переменных х1, х2,…, хn,относящихся к одному и тому же моменту времени. Последнее обстоятельствопозволяет нам рассматривать функции возбуждения как переключательные функции:
5. Построениефункции выхода.В автомате Мили каждая функция выхода zi определяетсоответствующий компонент набора выходных сигналов. Функции выхода приструктурном синтезе соответствуют функции выхода абстрактного автомата. Онизависят от внутренних переменных y1, y2,…, yhи входных переменных х1, х2,…, хn.Существенно, что значения переменных, определяющих zi, относятсявсегда к одному и тому же моменту времени, поэтому функции выхода являютсяпереключательными функциями:
/>
Функциивыхода автомата Мура в каждый момент времени определяют совокупность выходныхсигналов:
/>
6.Реализация функций выхода и функций возбуждения.Этот этап включает в себядействия, связанные с построением аналитического представления дляпереключательных функций, входящих в системы, их минимизацию, факторизацию ипреобразования в операторную форму для заданной системы элементов. Заметим, чтона этом этапе целесообразно также выполнять построение преобразователей кодов,которые обычно реализуются либо как система переключательных функций, либо ввиде схемы «дешифратор-шифратор».
7.Графическое изображениеполной схемы автомата.
2.6 Типыэлементов памяти
В качествеэлементов памяти на стадии структурного синтеза чаще всего используютэлементарные автоматы с двумя выходными сигналами. Однако в последнее время всвязи с разработкой больших интегральных схем представляет интересиспользование в качестве элементов памяти широко применяемых в цифровыхустройствах типовых схем: счетчиков и регистров. Элементы памяти с двумявыходными сигналами обычно называются триггерами. В большинстве случаев триггерявляется автоматом Мура. Он может иметь один или несколько входов. Работатриггера, как и любого автомата, описывается с помощью таблицы переходов.
На практикечасто возникает задача построения триггеров из элементов заданной системы. Дляэтой цели используют характеристическое уравнение триггера, которое определяетсостояние, в которое должен перейти триггер qt+1 в зависимости отвходного сигнала xt и состояния qt, в котором находитсятриггер qt+1 = c (xt, qt). Построение характеристическихуравнений триггеров выполняется обычно либо непосредственно по таблицепереходов, либо с помощью диаграмм Вейча.
Припостроении функций возбуждения автомата необходимо решать обратную задачу:находить сигналы, которые нужно подать на вход триггера, чтобы перевести его изодного состояния в другое. Для этого используют матрицу переходов автомата, вкоторой для каждого перехода указаны соответствующие входные сигналы,вызывающие такой переход. Построение матрицы переходов выполняется, как правило,непосредственно по таблице переходов автомата.
3.Проектирование алгоритма и построение абстрактного автоматаарифметико-логического устройства
3.1Задание и исходные данные
Разработкаарифметико-логического устройства, выполняющего операцию сложения и вычитания впрямом двоичном коде.
Исходныеданные:
– разрядностьоперандов – 8 бит;
– разрядностьрезультата – 8 бит;
– элементпамяти – ПЗУ;
– форматоперандов и результата – 8 бит;
3.2Разработка алгоритма устройства
Построималгоритм заданного логического устройства. Распишем все возможные комбинациисочетания знаков чисел, поступающих на вход устройства с учетом типа операции
1.A+B
2.А+(-В)
3.-А+В
4.-А+(-В)
5.А-В
6.А – (-В)
7.-А-В
8.-А – (-В)
Учтяособенности сложения и вычитания в двоичном коде, получим:
1. А+В
2. А+Вд
3. Ад+В
4. Ад+Вд
5. А+Вд
6. А+В
7. Ад+Вд
8. Ад+В,где д – означает число, переведенное в дополнительный код.
Очевидно, чтомы получили пары одинаковых комбинаций. Объединив номера 1 и 6, 2 и 5, 3 и 8, 4и 7 получим:
1. А+В
2. А+Вд
3. Ад+В
4. Ад+Вд
Теперь мыимеем все данные для построения алгоритма, построим его:
/>
Рисунок 3.2.1.Алгоритм арифметико-логического устройства
Далее разметималгоритм с учётом входных, выходных сигналов и состояний для построенияабстрактного автомата Мили:
/>
Рисунок 3.2.2– Алгоритм с учётом входных, выходных сигналов и состояний
Нарисуем Графавтомата Мили
/>
Запишемсоставляющие К1, К2, К3, К4, К5
К1=/>
К2=/>
К3=/>
К4=/>
К5=/>
Входныесигналы К1, К2, К3, К4, К5, X8, />
Поразмеченному алгоритму построим таблицу переходов-выходов автомата Мили.
Таблица 3.2 –Таблица переходов-выходов автомата Мили 1
/>
/>
/>
/>
/>
/>
/> Z0
/> Z1
/> Z2
/>
/>
/>
/>
/> Z3
/> Z4
/> Z5
/> Z6
/>
/> Z7
/>
4.Построение функциональной и электрической принципиальной схемы
Дляпостроения функциональной схемы с минимальными затратами входные сигналы исостояния нужно закодировать.
Табл. 4.1 –Кодировка состоянийВыходные сигналы
/> 1 000
/> 001
/> 010
/> 011
/> 100
/> 101
/> 110
/> 111
Табл. 4.2 –Кодировка выходных сигналовСостояния
/> Z0 000 Z1 001 Z2 010 Z3 011 Z4 100 Z5 101 Z6 110 Z7 111
Используем таблицу4.2 для построения шифратора
Запишемформулировки для /> в форме ДНФ
/>/>
/>/>
/>/>
/>/>/>/>/>/>/>/>
/>/>/>/>/>/>/>
/>/>/>/>/>/>/>
Теперьзапишем таблицу переходов с учётом кодировок.
Табл. 4.3 –Таблица переходов-выходов автомата Мили с учётом кодировок 000 001 010 011 100 101 110 111 000
/> 001
/> 010
/>
/>
/>
/>
/> 011
/> 100
/> 101
/> 110
/>
/> 111
/>
Используемприведенную выше таблицу для построения таблицы прошивки ПЗУ.
Табл. 4.4 – Таблицапрошивки ПЗУ системы управленияАдрес Данные
б1
б2
б3
в1
в2
в3
б1
б2
б3
y1
y2
y3
y4
y5
y6
y7
y8
y9
y10
y11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
/>
Послепостроения функциональной схемы выбираем по справочнику элементы и строим схемуэлектрическую принципиальную.
Выбираемследующие номиналы ИМС, присутствующие в схеме функциональной:
Так как частов наличии и при ограничении одной серией ИМС имеется только четырех разрядныйпараллельный регистр, а необходим восьмиразрядный, то информационные вх./вых.двух четырех разрядных регистров включаем независимо и параллельно, ауправляющие сигналы регистров необходимо соединить между собой соответственно.
Так как частов наличии и при ограничении одной серией ИМС имеется только четырех разрядный,управляющие сигналы соединить между собой соответственно, а вывода переполненияи прибавления лог. 1 в младший разряд, соединяем таким образом. Сигналпереполнения ИМС младших разрядов соединяем с входом «прибавления лог. 1 вмладший разряд» ИМС старших разрядов.
Вывод
В данномкурсовом проекте была разработана система управления арифметико-логическимустройством с элементами памяти ПЗУ, выполняющее операцию сложения и вычитанияв прямом двоичном коде. В процессе работы был составлен алгоритм работыустройства, абстрактный автомат Мили, таблицы прошивки ПЗУ и по ним построенасистема управления. В завершении работы были построены функциональная иэлектрическая принципиальная схемы устройства на форматах А3 и А1соответственно. Также составлены таблицы: переходов, выходов автомата,кодирования сигналов автомата, структурную таблицу переходов, выходов и функцийвозбуждения.
Осуществленареализация схемы управляющего автомата на микросхемах ТТЛ серии К555 обладающихвысоким быстродействием и малым потреблением.
В ходевыполнения задания по курсовому проектированию закреплены теоретические знанияпо дисциплине: «цифровые автоматы».
Списокисточников
1. Глушков В.М. Синтез цифровых автоматов. М.: 1967
2. Самофалов К.Г. и др. Прикладная теория цифровых автоматов.К.: 1987
3. Савельев А.Я. Прикладная теория цифровых автоматов. М.:1987
4. Справочник по интегральным микросхемам / Под ред. Б.В. Тарабрина.– М.: Энергия, 1980.
5. Каган Б.М., Сташин В.В. Основы проектированиямикропроцессорных устройств автоматики. М.: 1987
6. Шило В.Л. Популярные цифровые микросхемы: Справочник. –М.: Радио и связь, 1988. – 352 с.
7. Зубчук В.И., Сигорский В.П., Шкуро А.Н. Справочникпо цифровой схемотехнике. – К.: Техника, 1990. – 448 с.
8. Омельчук Н.А – Методические указания по курсовомупроектированию по дисциплине «Цифровые автоматы». — Запорожье: ЗГИА, 2001. –17 с.
9. Омельчук Н.А – Конспектлекций по дисциплине «Цифровые автоматы». — Запорожье: ЗГИА, 2002. – 68 с.
10. Глушков В.М – Синтезцифровых автоматов. — М.: 1967
11. Электронный справочник: Шульгин О.А.,Шульгина И.Б. – Справочник по цифровым логическим микросхемам (часть 1).