Логические основы ЭВМ. Реализация арифметических и логических операций в ЭВМ

Логические основы ЭВМ. Реализация арифметических и логических операций в ЭВМ

Аппаратура современных ЭВМ, если не учитывать оперативную память, конструируется из некоторых относительно простых элементов, называемых в русскоязычной литературе вентилями (по-английски – circuits). Каждый вентиль является достаточно простой (электронной) схемой и реализует одну из логических операций, у него есть один или два входа (аргументы операции) и один выход (результат). На входах и выходе могут быть электрические сигналы двух видов: низкое напряжение (трактуется как ноль или логическое значение false) и высокое (ему соответствует единица или логическое значение true). Обычно напряжение менее 1 вольта трактуется как логический ноль, а напряжение более 2 вольт – как логическая единица. Основные вентили у нас будут следующие:

1. Отрицание, этот вентиль имеет один вход и один выход, он реализует операцию отрицания not (НЕ). Другими словами, если на вход такого вентиля подаётся импульс высокого напряжения (значение true), то на выходе получится низкое напряжение (значение false) и наоборот.

2. Дизъюнкция или логическое сложение, этот вентиль реализует операцию or (ИЛИ).

3. Конъюнкция или логическое умножение, этот вентиль реализует операцию and (И).

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

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

NOT	AND	OR	XOR

или, чаще, прямоугольником с указанной внутри операцией:

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

Операция исключающее «ИЛИ»

Исключающее «ИЛИ», сложение по модулю 2, XOR, логическое сложение, строгая дизъюнкция, поразрядное дополнение, побитовый комплемент — такое количество названий говорит о важности этой операции. Для двух переменных результат выполнения операции является истинным тогда и только тогда, когда лишь один из аргументов является истинным. Приоритет операции такой же, как у дизъюнкции

Таблица истинности A B A xor B

Название операции «исключающее ИЛИ» обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из четырех случаев входа — случай одновременной истинности обоих аргументов «исключается». Ещё в русской грамматике значение данной логической связки передаётся союзом «либо». Обозначение Å, конечно, короче.

Пример. Докажите, что операция xor является обратимой: (A xor B) xor B = A. Составим таблицу истинности

x	y	x XOR y	(x XOR y) XOR y

 

В Си операция ^ - побитовое исключающее ИЛИ. Например, результатом выполнения операции 65^98 будет число 35, потому что 1000001 ^ 1100010 = 0100011 = 25 + 2 + 1 = 35. Однако логической операции исключающего ИЛИ в Си нет. Операцию надо будет представить в нормальной форме. http://neerc.ifmo.ru/wiki/index.php?title=Категория:Булевы_функции

Полусумматор и сумматор

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

Неполный сумматор (полусумматор) — логическая схема имеющая два входа и два выхода (двухразрядный сумматор, бинарный сумматор). Позволяет вычислять сумму , где и — это разряды двоичного числа, при этом результатом будут два бита , где — это бит суммы по модулю, а — бит переноса (carry-in bit).

a b С S

Полусумматор собран из сумматора по модулю 2 с добавлением элемента AND для получения сигнала переноса; его действие можно описать следующим логическим выражением:

S = a XOR b; С = a AND b,

где a и b – содержимое входов, S – содержимое выхода «сумма», С – содержимое выхода «перенос».

Теперь, если реализовать этот двоичный сумматор (полусумматор) в виде интегральной схемы (ИС), то она будет иметь не менее 7-ми внешних контактов (см. рис. 1.). Это входные контакты a и b, выходные s и с, один контакт для подачи тактовых импульсов (о них мы уже говорили, когда объясняли работу вентилей), два контакта для подачи электрического питания (ясно, что без энергии ничего работать не будет) и, возможно, другие контакты.

Рисунок 1. Пример ИС двоичного сумматора

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

Полный сумматор

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

Каскадный сумматор

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

С помощью полного сумматора можно сложить 2 одноразрядных двоичных числа. Для сложения двух -разрядных двоичных чисел можно использовать полных сумматоров.

При сложении двух чисел в -том разряде складываются , и входной бит переноса (carry-in bit) . Младший разряд суммы записывается в -й разряд ответа (), а старший становится выходным битом переноса (carry-out bit) и используется при сложении в следующем разряде.

При этом в первый входной бит переноса подаётся ноль, а последний бит переноса даёт старший разряд суммы.

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

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

Ясно, что скорость работы интегральной схемы напрямую зависит от частоты прихода тактовых импульсов, называемой тактовой частотой схемы. У современных ЭВМ не очень высокой производительности тактовые импульсы приходят на схемы основной памяти с частотой несколько сотен миллионов раз в секунду, а на схемы центрального процессора – ещё примерно в 10 раз чаще. Это должно дать Вам представление о скорости работы электронных компонент современных ЭВМ.

Теперь Вы должны почувствовать разницу в ви́дении, например, центрального процессора, системным программистом (на внутреннем уровне по нашей классификации), от ви́дения того же процессора инженером-конструктором ЭВМ. Для системного программиста архитектура центрального процессора представляется в виде устройств УУ и АЛУ, имеющих регистры, обменивающихся командами и числами с основной памятью, выполняющим последовательность команд программы по определённым правилам и т.д. В то же время для инженера-конструктора центральный процессор представляется в виде сложной структуры, состоящей из узлов-вентилей, соединённых проводниками и такими радиотехническими элементами, как сопротивлениями, конденсаторами и индуктивностями. По этой структуре распространяются электрические сигналы, которые в дискретные моменты времени (при приходе на вентили тактовых импульсов) преобразуются логическими операциями.

Взаимодействие УУ и АЛУ

Революционность идей Джона Фон Неймана заключалась в строгой специализации: каждое устройство компьютера отвечает за выполнение только своих функций. Например, раньше память ЭВМ часто не только хранила данные, но и могла производить операции над ними. Теперь же было предложено, чтобы память только хранила данные, АЛУ производило арифметико-логические операции над данными в своих регистрах, устройство ввода вводило данные из "внешнего мира" в память и т.д. Таким образом, Джон Фон Нейман предложил жёстко распределить выполняемые ЭВМ функции между различными устройствами, что существенно упростило схему машины, и сделало более понятной её работу.

Устройство управления тоже имеет свои регистры, оно может считывать команды из памяти на специальный регистр команд РK (IR – instruction register), на котором всегда хранится текущая выполняемая команда. Регистр УУ с именем РA называется регистром или счётчиком адреса (в англоязычной литературе его часто обозначают IP – instruction pointer), при выполнении текущей команды в него по определённым правилам записывается адрес следующей выполняемой команды (первую букву в сокращении слова регистр мы будем в дальнейшем изложении часто записывать латинской буквой R).

Рассмотрим, например, схему выполнения команды, реализующей оператор присваивания с операцией сложения двух чисел z:=x+y. ВАЖНО! Здесь x, y и z – адреса ячеек памяти, в которых хранятся, соответственно, операнды и будет помещен результат операции сложения (предположим, что такая команда есть в языке машины). После получения из памяти этой команды на регистр команд РK, УУ последовательно посылает управляющие сигналы в АЛУ, предписывая ему сначала считать операнды x и y из памяти и поместить их на регистры R1 и R2. Затем по следующему управляющему сигналу устройства управления АЛУ производит операцию сложения чисел, находящихся на регистрах R1 и R2, и записывает результат на регистр сумматора S. По следующему управляющему сигналу АЛУ пересылает копию регистра S в ячейку памяти с адресом z.

Приведем иллюстрацию описанного примера на языке Паскаль, где R1, R2 и S – переменные, обозначающие регистры АЛУ, ПАМ – массив ячеек, условно обозначающий память ЭВМ, а ⊗ – бинарная операция (в нашем случае это сложение, т.е. ⊗ = +).

R1:= ПАМ[x]; R2:= ПАМ[y]; S: = R1⊗R2; ПАМ[z]:= S;

В научной литературе по архитектуре ЭВМ принято конструкцию ПАМ[А] обозначать как <А>, тогда наш пример выполнения команды перепишется так:

R1: = <x>; R2: = <y>; S: = R1⊗R2; <z>:= S;

Опишем теперь более формально шаги выполнения одной команды в машине Фон Неймана:

1. РK:= <РA>; считать из ячейки памяти с адресом РA команду на регистр команд РK; 2. РA:= РA+1; увеличить счётчик адреса на единицу; 3. Выполнить очередную команду, хранящуюся в регистре РK.

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

Итак, если машинное слово попадает на регистр команд, то оно интерпретируется УУ как команда, а если слово попадает в АЛУ, то оно по определению считается числом. Это позволяет, например, складывать команды программы как числа, либо выполнить некоторое число как команду. Разумеется, обычно такая ситуация является семантической ошибкой, если только специально не предусмотрена программистом для каких-то целей.

Современные ЭВМ в той или иной степени нарушают практически все принципы Фон Неймана. Исключение, пожалуй, составляют только принцип автоматической работы, он лежит в самой основе определения ЭВМ как устройства для автоматической обработки данных, и принцип хранимой программы.

Например, существуют компьютеры, которые различают команды и данные. В них каждая ячейка основной памяти кроме собственно машинного слова хранит ещё специальный признак, называемый тэгом (tag), который и определяет, чем является это машинное слово. Для экономии памяти современные компьютеры могут приписывать такой тэг не каждой ячейке в отдельности, а сразу целой последовательности ячеек, называемой сегментом. Таким образом, различают, например, сегменты команд и данных, при этом выполнение данных в виде команды может трактоваться как ошибка. Так нарушается принцип неразличимости команд и чисел. В такой архитектуре при попытке выполнить число как команду, либо складывать команды как числа, центральным процессором будет зафиксирована ошибка. Очевидно, что это позволяет повысить надёжность программирования на языке машины, не допуская, как часто говорят, случайного "выхода программы на константы".

Практически все современные ЭВМ нарушают принцип однородности и линейности памяти. Память может, например, состоять из двух частей со своей независимой нумерацией ячеек в каждой такой части; или быть двумерной, когда адрес ячейки задаётся не одним, а двумя числами; либо ячейки памяти могут вообще не иметь адресов, такая память называется ассоциативной и т.д.

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

Вообще говоря, следует отметить, что в архитектуре машины Фон Неймана зафиксированы и другие принципы, которые из работы самого Фон Неймана явно не вытекали, так как, безусловно, считались самоочевидными. Так, например, предполагается, что во время выполнения программы не меняется число узлов компьютера и взаимосвязи между ними, не меняется число ячеек в оперативной памяти. Далее, например, считалось, что машинный язык при выполнении программы не изменяется (например, "вдруг" не появляются новые машинные команде) и т.д. В то же время сейчас существуют ЭВМ, которые нарушают и этот принцип. Во время работы одни устройства могут, как говорят, отбраковываться (например, отключаться для ремонта), другие – автоматически подключаться. Кроме того, во время работы программы могут, как изменяться, так и появляются новые связи между элементами ЭВМ (например, в так называемых транспьютерах). Существуют и компьютеры, которые могут менять набор своих команд, они называются ЭВМ с микропрограммным управлением.

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

На этом закончим краткое описание машины Фон Неймана и принципов её работы. Первая ЭВМ, построенная на основе принципов Фон Неймана, называлась EDVAC (Electronic Delay Storage Automatic Calculator – автоматический вычислитель с электронной памятью на линиях задержки). Компьютер EDVAC был построен в 1949 году в Англии М.Уилксом (при участии А.Тьюринга). EDVAC работала в двоичной системе счисления со скоростью примерно 100 операций в секунду. Заметим, что именно от этой машины принято отсчитывать первое поколение ЭВМ (все предшествующие "не совсем настоящие" компьютеры можно условно отнести к нулевому поколению).

[1] Триггер (триггерная система) — класс электронных устройств, обладающих способностью длительно находиться в одном из двух устойчивых состояний и чередовать их под воздействием внешних сигналов. Каждое состояние триггера легко распознаётся по значению выходного напряжения. По характеру действия триггеры относятся к импульсным устройствам — их активные элементы (транзисторы, лампы) работают в ключевом режиме, а смена состояний длится очень короткое время.

[2] Разрывные характеристики электронных ламп, на которых основано действие триггеров, впервые под названием «катодное реле» были описаны М. А. Бонч-Бруевичем в 1918 г.

Практическая схема триггера была опубликована 5 августа 1920 года У. Г. Икклзом и Ф. У. Джорданом в патенте Великобритании № 148582, заявленном 21 июня 1918 г. и в статье «Переключающее реле, использующее трёхэлектродные вакуумные лампы» от 19 сентября 1919 года.

[3] Баула Владимир Георгиевич. Окончил факультет вычислительной математики и кибернетики МГУ (1971). Кандидат физико-математических наук (1975). Доцент кафедры АСВК (с 1982 г.)

[4] Здесь рассматривается несколько модифицированная схема машины фон Неймана: устройства ввода / вывода обмениваются данными непосредственно с памятью, а в схеме самого фон Неймана этот обмен производился через арифметико-логическое устройство (АЛУ) под контролем устройства управления.

[5] В частности, можно написать программу, которая ничего не вводит и выводит запись своего собственного текста. Вы можете попробовать сделать это на некотором языке программирования высокого уровня (например, на Паскале). Кому любопытно, могут посмотреть, как это делается, в книге Уэзерелл Ч. Этюды для программистов. – М., Мир, 1982.

 

[6] В современных ЭВМ некоторые программы, называемые Базовыми процедурами ввода/вывода (BIOS) крайне нежелательно изменять (стирать) во время работы компьютера. Такие программы располагают в уже упомянутой ранее памяти типа ROM, закрытой для записи, хотя по внешнему виду команды в такой памяти тоже неотличимы от чисел.

Логические основы ЭВМ. Реализация арифметических и логических операций в ЭВМ

Аппаратура современных ЭВМ, если не учитывать оперативную память, конструируется из некоторых относительно простых элементов, называемых в русскоязычной литературе вентилями (по-английски – circuits). Каждый вентиль является достаточно простой (электронной) схемой и реализует одну из логических операций, у него есть один или два входа (аргументы операции) и один выход (результат). На входах и выходе могут быть электрические сигналы двух видов: низкое напряжение (трактуется как ноль или логическое значение false) и высокое (ему соответствует единица или логическое значение true). Обычно напряжение менее 1 вольта трактуется как логический ноль, а напряжение более 2 вольт – как логическая единица. Основные вентили у нас будут следующие:

1. Отрицание, этот вентиль имеет один вход и один выход, он реализует операцию отрицания not (НЕ). Другими словами, если на вход такого вентиля подаётся импульс высокого напряжения (значение true), то на выходе получится низкое напряжение (значение false) и наоборот.

2. Дизъюнкция или логическое сложение, этот вентиль реализует операцию or (ИЛИ).

3. Конъюнкция или логическое умножение, этот вентиль реализует операцию and (И).

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

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

NOT	AND	OR	XOR

или, чаще, прямоугольником с указанной внутри операцией:

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

Операция исключающее «ИЛИ»

Исключающее «ИЛИ», сложение по модулю 2, XOR, логическое сложение, строгая дизъюнкция, поразрядное дополнение, побитовый комплемент — такое количество названий говорит о важности этой операции. Для двух переменных результат выполнения операции является истинным тогда и только тогда, когда лишь один из аргументов является истинным. Приоритет операции такой же, как у дизъюнкции

Таблица истинности A B A xor B

Название операции «исключающее ИЛИ» обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из четырех случаев входа — случай одновременной истинности обоих аргументов «исключается». Ещё в русской грамматике значение данной логической связки передаётся союзом «либо». Обозначение Å, конечно, короче.

Пример. Докажите, что операция xor является обратимой: (A xor B) xor B = A. Составим таблицу истинности

x	y	x XOR y	(x XOR y) XOR y

 

В Си операция ^ - побитовое исключающее ИЛИ. Например, результатом выполнения операции 65^98 будет число 35, потому что 1000001 ^ 1100010 = 0100011 = 25 + 2 + 1 = 35. Однако логической операции исключающего ИЛИ в Си нет. Операцию надо будет представить в нормальной форме. http://neerc.ifmo.ru/wiki/index.php?title=Категория:Булевы_функции