Тема 2_ Арифметические и логические основы ЭВМ

Кафедра	Логическая схема одноразрядного
информатики	двоичного сумматора
		УГАТУ

2.По таблице истинности представим выходные функции S и P в виде ДНФ

S = f1(x1 , x2 ) = x1x2 + x1 x2 ,

P= f2 (x1 , x2 ) = x1x2

3.По логическим функциям построим схему

101

Кафедра Классические основы построения ЭВМ

информатики

УГАТУ

Основы построения электронных вычислительных машин в их современном понимании были заложены в 30-е – 40-е годы прошлого века видными учеными: английским математиком Аланом Тьюрингом и американцем венгерского происхождения Джоном Нейманом.

В 1936 году А. Тьюринг сформулировал понятие абстрактной вычислительной машины. Одновременно с ним, хотя и не в столь явной форме, это же сделал Э. Пост (США).

Хотя машина Тьюринга (МТ) не стала реально действующим устройством, она до настоящего времени постоянно используется в качестве основной модели для выяснения сущности таких понятий, как «вычислительный процесс», «алгоритм», а также для выяснения связи между алгоритмом и вычислительными машинами.

102

Кафедра	Машина Тьюринга
информатики

УГАТУ

Вобщем случае абстрактная вычислительна машина Тьюринга состоит из следующих частей

103

Кафедра	Машина Тьюринга
информатики

УГАТУ

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

104

Кафедра	Машина Тьюринга
информатики

УГАТУ

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

105

Кафедра	Машина Тьюринга
информатики

УГАТУ

-Управляющего устройства, которое в каждый рассматриваемый момент находится в некотором «состоянии». Количество таких состояний конечно. Одно из состояний считается заключительным и управляет окончанием работы машины.

106

Кафедра	Машина Тьюринга
информатики

УГАТУ

1.Машина Тьюринга работает в произвольном конечном алфавите и выполняет некоторое конечное число приказов.

2.Машина может сдвигать ленту на одну ячейку влево или вправо, оставляя содержимое ячеек неизменным.

3.Машина может изменять состояние воспринимаемой ячейки, оставляя ленту при этом неподвижной.

4.В каждой ячейке машины находится один символ алфавита. Некоторая буква соответствует пустой ячейке.

107

Кафедра	Машина Тьюринга
информатики

УГАТУ

Конечную совокупность символов алфавита

A= {S0, S1, …, Sn},

скоторой работает машина, называют внешним алфавитом.

Конечную совокупность состояний устройства управления

Q = {q0, q1, …, qm}

называют внутренним алфавитом.

S0 – соответствует пустой ячейке, q0 – соответствует заключительному состоянию.

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

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

108

Кафедра		Машина Тьюринга
информатики
		УГАТУ
Еще раз si – символ, который может быть записан в ячейку;
qj – состояние, в котором находится ячейка, его может менять УУ.
Каждая конфигурация содержит лишь одно вхождение символа
qi из внутреннего алфавита. Этот символ может быть в слове
самым левым, но не может быть самым правым, так как справа
от него должен помещаться символ состояния обозреваемой
ячейки.
Если стандартная машина Тьюринга, находясь в состоянии qi и
воспринимая записанный на ленте символ Sk, переходит в
новое состояние qj, осуществляя при этом замену символа в
рассматриваемой ячейке на символ Sm и сдвиг ленты влево на
одну ячейку, то говорят, что машина выполняет команду
		qi Sk → qj SmЛ.
		109
Кафедра		Машина Тьюринга
информатики
		УГАТУ
Команды стандартной машины Тьюринга
задаются набором пятерок символов вида
qiSkqjSmЛ, т.е. стрелка без стрелки.
	При манипуляциях с лентами используют следующие
обозначения:
	- Л – движение ленты влево;
	- П – движение ленты вправо;
	- С – движения ленты нет.
		110

Кафедра	Машина Тьюринга
информатики
	УГАТУ
Пример. Рассмотрим пример работы машины Тьюринга с
алфавитами А = {1,0}, Q = {q0, q1}
и командами q11q11Л, q10q01С.
Пусть на ленте имеется слово 11100. Головка стоит над первой
единицей слева.
В результате работы данной машины Тьюринга это слово
превращается в слово 11110.
По окончании работы головка стоит над крайней правой
единицей.
	111
Кафедра	Машина Тьюринга
информатики
	УГАТУ
Можно сказать, что данная машина сложила в двоичной системе два
десятичных числа 28 и 2, т. к. 111002 = 2810, а 111102 = 3010
	112

Кафедра		Машина Тьюринга
информатики
		УГАТУ
Важная особенность машины Тьюринга –
	преобразование информации на каждом такте
	происходит лишь в одной ячейке, остальные
	дожидаются посещения головки.
Использование нескольких машин Тьюринга с
	общей для них внешней памятью (лентой) – не
	всегда допустимо из-за возможных конфликтов
	при обращении к одной и той же ячейке
	памяти.
		113
Кафедра		Автомат Неймана
информатики
		УГАТУ
Автомата Неймана состоит из элементов Неймана –
устройств, которые на каждом такте t пребывают в одном
из конечного числа состояний qi Q, образующих его
алфавит.
Элемент Неймана имеет два входных канала: левый и
правый; по каждому из них на такте t также поступает по
одному состоянию из Q.
Элемент в такте t +1 переходит в состояние,
определяемое его состоянием в текущий момент времени
и значениями, поступившими по входным каналам.
		114

Кафедра	Автомат Неймана
информатики
	УГАТУ
Состояния элементов Неймана в момент времени t
определяют конфигурацию автомата Неймана
За один такт свое состояние может менять большое
число элементов Неймана, что фактически приводит к
параллельной обработке информации.
В автомате Неймана число одновременно обрабатываемых
ячеек может неограниченно расти, оставаясь в каждый
момент конечным.
	115
Кафедра	Рекомендации Неймана
информатики
	УГАТУ
	В 1946 году Джоном фон Нейманом на
	летней сессии Пенсильванского
	университета был распространен
	отчет, заложивший основы развития
	вычислительной техники на
	несколько десятилетий вперед.
	В нем он описал, как должен быть
	устроен и как должен работать
	компьютер, чтобы он был
	универсальным и эффективным
	устройством для обработки
	информации.
Последующий опыт разработки ЭВМ показал
правильность основных выводов Неймана, которые в
последующие годы развивались и уточнялись.
	116

Кафедра	Рекомендации Неймана
информатики

УГАТУ

Основные рекомендации, предложенные Нейманом для разработчиков ЭВМ:

1.Машины на электронных элементах должны работать не в десятичной, а в двоичной системе счисления.

2.Программа должна размещаться в одном из блоков машины – в запоминающем устройстве (ЗУ), обладающем достаточной емкостью и соответствующими скоростями выборки и записи команд программы.

117

информатики	Рекомендации Неймана
Кафедра

УГАТУ

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

Это обстоятельство приводит к следующим важным последствиям:

•промежуточные результаты вычислений, константы и другие числа могут размещаться в том же ЗУ, что и программа;

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

118

информатики	Рекомендации Неймана
Кафедра

УГАТУ

4.Трудности физической реализации ЗУ, быстродействие которого соответствовало бы скорости работы логических схем, требует иерархической организации памяти.

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

6.В машине используется параллельный принцип организации вычислительного процесса (операции над словами производятся одновременно по всем разрядам).

119

	Кафедра	Следующая тема:	УГАТУ
	информатики

Общие принципы организации и работы компьютеров

120