Kandaurova_N_Vychislitelnye_sistemy_seti_i_telekommunikatsii

Выполнение операции A–B в 10-ой системе счисления обеспечивает результат:

A–B=280,3(10)–73,15(10)=207,15(10).

Вычислим ошибку выполненной операции в 10-ой системе счисления

=207,1503906(10) – 207,15(10) = 0,0003906.

Это достаточно точный результат, который даѐт погрешность (ошибку)

лишь в 4-ом разряде после запятой.

Вывод: операция вычитания A–B выполнена в ДМК как сумма A+( B) правильно и с достаточно высокой точностью.

Отметим, что все операции в ЭВМ благодаря рассмотренному кодированию сводятся к сложению или многократному сложению. Так, операция умножения сводится к многократному сложению со сдвигом, а операция деления – к многократному вычитанию со сдвигом, которая в свою очередь заменяется тоже сложением.

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

2.4. Логические основы компьютеров

Алгебра логики широко используется для описания схем компьютеров, их оптимизации и проектирования. Она устанавливает основные законы формирования и преобразования логических функций и позволяет представить любую сложную функцию в виде композиции простейших функций [6, 9, 12, 23].

Из четырѐх комбинаций двух переменных х1х2 (22=4) можно построить шестнадцать (24=16) различных функций. В левой части таблицы 2.2 перечислены комбинации входных переменных, а в правой – функции двух переменных yj. В этой таблице выделена заливкой та часть из них, которая имеет фундаментальное значение при построении основных схем компьютеров.

Таблица 2.2 – Таблица истинности функций двух переменных

	yj
х1х2			у0			у1		у2	у3	у4	у5		у6			y7			у8			у9		у10	у11	у12	у13		у14			у15
0 0			0			0		0	0	0	0		0			0			1			1		1	1	1	1		1			1
0 1			0			0		0	0	1	1		1			1			0			0		0	0	1	1		1			1
1 0			0			0		1	1	0	0		1			1			0			0		1	1	0	0		1			1
1 1			0			1		0	1	0	1		0			1			0			1		0	1	0	1		0			1

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

30

логическое умножение (конъюнкция) и связываются знаками логического сложения (дизъюнкция). Такие формы функций получили название

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

Запишем логические выражения для функций, выделенных заливкой. Функция у0 – константа ноль:

у0 = 0.

Функция у1 – логическое умножение (конъюнкция):

у1 х1 х2 .

Функция у6 – инверсия равнозначности (инверсия функции y9) или сложение по модулю 2 (Σmod2):

у6 у9 х1 х2 х1 х2 х1 х2 х1 х2 .

Функция у7 – логическое сложение (дизъюнкция):

у7 х1 х2 х1 х 2 х1 х2 х1 х2 .

Функция у8 – отрицание дизъюнкции (стрелка Пирса):

у8 у7 х1 х2 х1 х2 .

Функция у9 – логическая равнозначность:

у9 х1 х 2 х1 х2 .

Функция у14 – отрицание конъюнкции (штрих Шеффера):

у14 у1 х1 х2 х1 х 2 .

Функция у15 – константа единица:

у15 = 1.

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

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

Законы алгебры логики. Из определения вышеприведенных функций можно установить целый ряд простейших свойств [6, 9, 12, 23]:

х 1=1			х∙1=х			х х … х=х
х 0=х			х∙0=0			х∙х∙…∙х= х
х			х		=0
	х	=1		х
х х=х			х∙х=х

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

коммутативный (переместительный):

31

	х1∙х2=х2∙х1	х1 х2=х2 х1;
	ассоциативный (сочетательный):
(х1∙х2)∙х3=(х1∙х3)∙х2=х1∙(х2∙х3)		(х1 х2) х3=(х1 х3) х2=х1 (х2 х3);
	дистрибутивный (распределительный):
	х1∙(х2 х3)=х1∙х2 х1∙х3	х1 х2∙х3=(х1 х2)(х1 х3);

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

х1 х1∙х2=х1

х1∙(х1 х2)=х1;

законы склеивания:

х1∙х2 х1∙ х 2=х1

(х1 х2)(х1 х 2)=х1,

Fx F х =F

(x F)( х F)=F,

где F – логическая функция общего вида, не зависящая от переменной х;

закон свертки:

x х F=x F

x( х F)=xF;

правило де Моргана:

1

1

2 .

х1 х2

х

х

2

х1 х2

х

х

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

Пример. Найти минимальную дизъюнктивную форму функции, заданной таблицей истинности (таблица 2.3).

Таблица 2.3 Таблица истинности функции y=f(x1, х2, x3)

х1	х2	х3	y
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

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

у= х 1 х 2 х 3 х 1 x2 х 3 х 1 x2 x3 x1 х 2 х 3 x1 х 2 x3 x1x2 x3.

32

Пунктирными линиями в этом выражении отмечены пары конъюнкций, к которым можно последовательно применить операцию склеивания типа

Fx F x F :

у= х 2 х 3 х 1 х 3 х 1 x2 x2 x3 x1 х 2 x1 x3.

Особенно хорошо это видно при использовании диаграммы Вейча (таблица 2.4), в которой «склеиваемые» конъюнкции находятся по соседству друг с другом. После выделения конъюнкций (они отмечены заливкой), видно, какие конъюнкции могут образовывать пары для склеивания.

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

у= х 1 x2 x2 x3 x1 x3 x1 х 2 х 2 х 3 х 1 х 3,

в котором отсутствуют возможности дальнейших склеиваний и поглощений.

Таблица 2.4 – Диаграмма Вейча функции у

x2

х1

х 2

x1 x2 x3

x x

х

3

x

х

2

x

x

х

2

х

3

1

2

1

3

1

х 1 x2 х 3

х 1 x2 x3

х 1 х 2 x3

х 1 х 2 х 3

х 1

х 3

x3

х 3

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

у1= х 1 x2 x1 x3 х 2 x3;

у2= х 1 x2 x2 x3 x1 х 2 х 1 х 3; у3= х 1 x2 x1 x3 x1 х 2 х 1 х 3; у4= х 1 х 3 x2 x3 x1 х 2;

у5= х 1 х 3 х 1 x2 x1 x3 x1 х 2.

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

33

Литература

Список основной литературы

1.Бройдо В.Л., Ильина О.П. Вычислительные системы, сети и телекоммуникации. – 3-е изд. – СПб.: Питер, 2008.

2.Лихтарников Л. М., Сукачева Т.Г. Математическая логика: курс лекций. – СПб.: Лань,1998.

3.Пятибратов А.П. Вычислительные системы, сети и телекоммуникации: учебник / А.П. Пятибратов, Л.П. Гудыно, А.А. Кириченко; под ред. А.П. Пятибратова. – 4-е изд., перераб. и доп. – М.: Финансы и статистика; ИНФРА-М, 2008.

Список дополнительной литературы

1.Бройдо В.Л. Вычислительные системы, сети и телекоммуникации: учебник. – 2-е изд. – СПб.: Питер, 2005.

2.Информатика: учебник / под ред. Н.В. Макаровой. – М.: Финансы и статистика, 2004.

3.Основы современных компьютерных технологий: учебник / под ред. проф. А.Д. Хомоненко. – СПб.: КОРОНА принт, 2005.

4.Пятибратов А.П. Вычислительные системы, сети и телекоммуникации: учебник / А.П. Пятибратов, Л.П. Гудыно, А.А. Кириченко; под ред. А.П. Пятибратова. – 3-е изд., перераб. и доп. – М.: Финансы и статистика, 2005.

5.Пятибратов А.П. и др. Вычислительные системы, сети и телекоммуникации: учебник / А.П. Пятибратов, Л.П. Гудыно, А.А. Кириченко; под ред. А.П. Пятибратова. – 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2002.

Лекция № 3. ЭЛЕМЕНТНАЯ БАЗА КОМПЬЮТЕРОВ

3.1.Классификация элементов и узлов компьютеров

Вструктуре компьютеров выделяют следующие структурные единицы [23, 24, 25]: элементы, узлы, блоки и устройства.

Нижний уровень обработки реализуют элементы. Каждый элемент

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

Все современные компьютеры строятся на интегральных схемах (ИС). Основу набора ИС обычно составляют большие интегральные схемы (БИС) и сверхбольшие интегральные схемы (СБИС). Уже появились многоядерные микропроцессоры, которые будут относиться к ультрабольшим ИС (УБИС). Кроме них обычно используются микросхемы с малой (МИС) и средней степенью интеграции (СИС). Функционально микросхемы могут соответствовать узлу, блоку или устройству, но каждая из них состоит из комбинации простейших логических элементов.

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

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

При потенциальном (статическом) представлении сигналов единичное значение двоичной переменной отображается высоким уровнем напряжения, а нулевое значение – низким уровнем (рисунок 3.1, б).

U											U
0	1				1	0		0		1	0	1	1	0	0	1
	1		2			3 4		5		6 Такты		1	2	3 4	5	6 Такты
						а								б

Рисунок 3.1 – Представление информации в компьютерах: а – импульсные сигналы; б – потенциальные сигналы

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

35

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

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

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

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

По своему назначению элементы делятся на формирующие, логические

изапоминающие.

Кформирующим элементам относятся: генераторы импульсов,

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

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

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

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

3.2. Комбинационные схемы

Обработка информации в схемах компьютеров обеспечивается преобразователями (цифровыми автоматами) двух видов: комбинационными схемами и схемами с памятью [23, 24, 25].

36

Комбинационные схемы (КС) – это схемы, у которых выходные сигналы Y = (y1, y2,..., уm) в любой момент дискретного времени однозначно определяются совокупностью входных сигналов Х = (х1, х2,..., хn), поступающих в тот же момент времени t. Реализуемый в КС способ обработки информации называется комбинационным, т.к. результат обработки зависит только от комбинации входных сигналов и формируется сразу же при поступлении входных сигналов. Поэтому одним из достоинств комбинационных схем является их высокое быстродействие. Преобразование информации однозначно описывается логическими функциями вида Y = f (X).

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

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

Дешифраторы (ДШ) – это комбинационные схемы с п входами и т = 2n выходами. Единичный сигнал, формирующийся на одном из т выходов, однозначно соответствует комбинации входных сигналов. Например, разработка структуры ДШ для n=3 позволяет получить таблицу истинности и логические зависимости (таблица 3.1).

Таблица 3.1 – Таблица истинности дешифратора и логические зависимости

	Входы							Выходы						Логические
х1		х2	х3	у0		у1	у2		у3	у4	у5	у6	у7	зависимости
0		0	0	1	0		0	0		0	0	0	0	у0= х 1 х 2 х 3
0		0	1	0		1	0	0		0	0	0	0	у1= х 1 х 2 х3
0		1	0	0	0		1	0		0	0	0	0	у2= х 1 х2 х 3
0		1	1	0	0		0		1	0	0	0	0	у3= х 1 х 2 х 3
														у4= х 1 х 2 х 3
1		0	0	0	0		0	0		1	0	0	0
1		0	1	0	0		0	0		0	1	0	0	у5= х 1 х 2 х 3
1		1	0	0	0		0	0		0	0	1	0	у6= х 1 х 2 х 3
1		1	1	0	0		0	0		0	0	0	1	у7= х 1 х 2 х 3

Дешифраторы широко используются в ЭВМ для определения адреса данных, для расшифровки кода операции и др.

На рисунке 3.2 представлены структурная схема ДШ, построенная в базисе И-НЕ, и ее условное обозначение на принципиальных электрических схемах.

Шифратор (ШР) решает задачу, обратную схемам ДШ, т.е. по номеру входного сигнала формирует однозначную комбинацию выходных сигналов.

37

Пример построения ШР иллюстрируется таблицей истинности (таблица 3.2) и схемами на рисунке 3.3.

х1 х2 х3	х 1 х 2 х 3
	&
	&	у0	х	1	DC 0	Y0
	&		1
			х2		i	Yi
	& у1			2
	&		х3	3	7	Y7
	&	у7
	а				б

Рисунок 3.2 – Структурная схема дешифратора (а) и обозначение дешифратора на принципиальных электрических схемах (б)

Таблица 3.2 – Таблица истинности ШР и логические зависимости

							Входы															Выходы									Логические
	х1			х2		х3		х4				х5			х6		х7			у0				у1		у2				зависимости
	1		0			0		0				0		0			0		0					0		1			у =х			х	х		х
	0			1		0		0				0		0			0		0					1		0		0		4		5	6		7
	0		0			1		0				0		0			0		0					1		1			у = х			х	х х
	0		0			0			1			0		0			0		1					0		0		1		2		3	6		7
	0		0			0		0				1		0			0		1					0		1			у =х			х	х		х
	0		0			0		0				0			1		0		1					1		0
																												2		1		3	5		7
	0		0			0		0				0		0			1		1					1		1
Обратим внимание, что в таблицах 3.1 и 3.2 входы и выходы
поменялись местами.
	х0 х1 х2 х3 х4 х5 х6 х7
																			1
																							у0
																											х0				0	CD 0				Y0
																											х1				1
																			1
																																	1			Y1
																							у1
																																				Y2
																											х7				7		2
																			1
								а															у2									б

Рисунок 3.3 – Структурная схема шифратора (а) и обозначение шифратора на принципиальных электрических схемах (б)

38

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

Таблица 3.3 истинности компаратора отражает логику работы i-го разряда схемы сравнения.

Таблица 3.3 – Таблица истинности i-разрядного компаратора и логическая зависимость

Входы

Выходы

Логические

ai

bi

Yi

зависимости

0

0

1

Y

ai bi a

b

i

i

i

0

1

0

i bi ai

i

a

b

1

0

0

a

b

1

1

1

i

i

На рисунке 3.4 показана структурная схема компаратора. На нѐм помимо выхода Y2, фиксирующего равенство значений разрядов (в виде инвенрсии формулы Σmod2), показаны выходы Y1, и Y3 соответствующие сигналам a>b и a<b.

a b

1	b			Y1	a b
		&
						a	= = >	Y1
			1	Y2	a b
		&					=	Y2
1	a			Y3	a b	b	<	Y3
			a				б

Рисунок 3.4 – Структурная схема компаратора (а) и обозначение компаратора на принципиальных электрических схемах (б)

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

Таблица 3.4 – Таблица истинности полусумматора и логические зависимости

	Входы		Выходы		Логические зависимости
	ai	bi	Si	Pi
	0	0	0	0
					Si a			bi ai b ai bi
	0	1	1	0
							i			i
	1	0	1	0
					Pi ai			bi
	1	1	0	1
					39