Министерство образования и науки украины

ЗАПОРОЖСКИЙ ИНСТИТУТ ЭКОНОМИКИ И

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

УТВЕРЖДАЮ

Проректор

_______________

проф. А.В. Сыпко

КОНСПЕКТ ЛЕКЦИЙ

По дисциплине

«Прикладная теория цифровых автоматов»

«АРИФМЕТИКО-ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ»

для студентов специальности

6.091501 – «Компьютерные системы и сети»

5.091504 – «Обслуживание компьютерных систем и сетей»

Запорожье 2011

Конспект лекций по дисциплине «Прикладная теория цифровых автоматов», «АРИФМЕТИКО-ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ» для студентов специальности «Компьютерные системы и сети» «Обслуживание компьютерных систем и сетей» / сост. ст. преп. Прокопенко Р. В. – Запорожье.: ЗИЭИТ, 2011. – 131 с.

Составитель: ст. преп. Прокопенко Р. В.

Утверждена на заседании кафедры

экономической кибернетики и компьютерныхсистем

протокол № __________

от «___» _________ 20__ г.

зав. кафедрой _________

к.ф.-м.н., проф. Лебедева Л.Н.

Содержание

Глава 1. Арифметико-логические основы ЭВМ …………………...	4
Глава 2. Представление числовой информации в цифровом автомате ………………………………………………………………...	11
Глава 3. Формы представления чисел в цифровых автоматах ….	23
Глава 4. Арифметические действия с двоичными числами………	37
Глава 5. Выполнение операций над двоично -десятичными числами …………………………………………………………………	55
Глава 6. Информационные основы цифровых автоматов ………..	62
Глава 7. Основы логического проектирования ЦА ……………….	67
Глава 8. Минимизация функций алгебры логики ………………...	76
Глава 9. Абстрактная теория автоматов …………………………...	87
Глава 10. Структурная теория автоматов …………………………	92
Глава 11. Проектирование асинхронных цифровых автоматов …	95
Глава 12. Канонический метод структурного синтеза ЦА с памятью ………………………………………………………………..	105
Глава 13. Обеспечение устойчивости функционирования ЦА …..	115
Глава 14. Микропрограммные автоматы …………………………..	122
Литература ………………………………………………………..	131

Глава 1 Арифметико-логические основы эвм

1.1 Информационные процессы

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

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

Характер изменения сигнала во времени может быть представлен графически, в виде осциллограмы, посредством таблицы, в которую вносятся значения s_iвi-тые моменты времени; сигнал также может быть описан аналитически.

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

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

s=f(t). Причем при такой модели имеется в виду, что причиной изменения величиныsявляется не само время, а некоторая другая физическая величина. Поэтому точнее говорить, что обозначая сигнал черезs(t), q(t),... принимается модель, описывающая изменение величинs, q,... во времени.

Существуют различного типа сигналы: непрерывные, т.е.аналоговые, сигналыдискретные, квантованные, кодированные (цифровые), модулированные, импульсныеи т.д.

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

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

Дискретный сигналописывается решетчатой функцией (последова-тельностью, временным рядом)X(nt), в которой величинаXможет принимать любые значения в некотором интервале [X',X"], в то время, как независимая переменнаяnпринимает только дискретные значенияn= 0, 1, 2,...t- интер-вал (шаг) дискретизации. Дискретизация непрерывного сигналаs(t) может производиться во времени или по уровню (параметру). Последний случай дискретизации обычно называется квантованием по параметру и он будет рассмотрен отдельно.

Когда дискретизация сигнала s(t) осуществляется во времени, то не-прерывный сигналs(t) заменяется (представляется) последовательностью импульсных сигналов, амплитуда которых соответствует значениям непрерывного сигнала в дискретные моменты времениnt. В данном случае значениеtравно временному интервалу между смежными отсчетами. ТогдаfD= 1/t- это циклическая частота дискретизации, аD= 2fDсоответствующая круговая частота.

Примем, что сигнал s(t) задан или графически или же таблично, в котору. внесены его значения в пределах периода времениТчерез определенные равные интервалы времени, т.е. периодТразделен в этом случае на 2nравных частей (рис.1.1.). Тогда абсциссы точек разбиения будут равны:

tk= (kT)/2n, а ординаты в этих точках:

sk = f(tk ), где k=0,1,2,...,2n.

Здесь skзначение амплитуды сигналаs(t) вk-тый момент времени.

Если для непрерывного сигнала действительно следующее выражение:

s(t) =Smsint, то после дискретизации во времени этот сигнал описывается уравнением:

s(nt) = Smsin nt.

Рис. 1.1. Кривая квантования.

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

,

где n- степень полинома,ai- действительные коэффициенты.

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

Согласно теореме В.А.Котельникова, если функция s(t) не содержит частот выше некоторойFm, то она полностью определяется своими мгновенными значениями в моменты времени, отстоящими друг от друга на величину

1/(2Fm), т.е.

,

где k- порядковый номер отсчета функции;t= 1/(2Fm) - шаг дискретизации по времени,sk=s(tk) - мгновенные значения сигналаs(t) вk-ой отсчетной точкеtk=k/m=k/(2Fm) =kt.

Из этой теоремы следует, что для однозначного представления функции с ограниченным спектром на интервале времени Тдостаточно иметь некоторыеnзначений этой функции, где

n=T /t= 2FmT.

При выполнении этого равенства (условия) непрерывная и дискретная функции обратимы между собой, т.е. тождественны. Таким образом, произвольный сигнал, спектр которого не содержит частот выше Fmможет быть представлен в виде последовательности импульсов, амплитуда которых равна значению исходного сигнала в дискретные моменты времениkt= а интервалы между нимиt= 1/(2Fm).

Из приведенной выше формулировки теоремы Котельникова однозначно следует, что для выбора оптимального шага дискретизации необходимо предварительно провести количественные оценки всех значащих гармоник спектрального разложения исходного непрерывного сигнала, для нахождения величины Fm, т.е.m.

Рассмотрим теперь процедуру квантованиясигнала по параметру.

В диапазоне непрерывных значений функции f(t) выбирается конечное число дискретных значений функции, распределенных, например, равномерно по всему диапазону. В произвольный момент времени значение функцииf(t) заменяется ближайшим дискретным по параметру значением.Тем самым функция приобретает ступенчатый вид (рис.1.2.):

Рис. 1.2. Кривая квантования по параметру

Шагом квантования по параметру называется разность между соседними дискретными значениями функции. Для равномерного квантования шаг квантования постоянный и равен :

k= (fmax_fmin)/(q_ 1),

где q- число шагов квантования.

Абсолютная погрешность квантования по параметру может изменяться от 0 до k/2. Тогда среднеквадратичная погрешность квантования при равномерном распределении приведенной погрешности от 0 до 0,5kравна:

k=k/2.

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

Цифровой сигнал описывается квантованной решетчатой функцией (квантованной последовательность., квантованным временным рядом) Xw(nt), которая принимает ряд дискретных значений уровней квантованияh1,h2,h3,...,hk,, в то время как независимая переменнаяn= 0, 1, 2,....Каждому из уровней квантования ставится в соответствие некоторое число и тем самым сигнал кодируется. Поэтому передача или обработка отсчета цифрового кодированного сигнала сводится к операциям над безразмерными числами (кодами). Представление сигнала в цифровой форме практически всегда дает существенное преимущество при передаче, хранении и обработке информации.

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

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