Контроль арифметических операций

 

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

Операцию сдвига можно представить как передачу слова из i -того разряда в (i+x)-е или (i-x)-е разряды. Поэтому, контроль сдвига можно осуществить по методу четности-нечетности.

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

Например:

1) Числовой контроль. Найти контрольные коды чисел А = 571 = 1000111011 и В = 329 = 0101001001 и контрольный код их суммы по методу контроля по модулю 3. При делении А на 3 имеем остаток 012 (110), а при делении В на 3 - остаток равен 102 (210). Просуммируем эти числа и их остатки:

 

А = 1000111011 (01)

В = 0101001001 (10)

А + В = 1110000100 (11)

 

Если разделить сумму на 3 отаток будет 0, и если разделить сумму контрольных кодов на 3 остаток также будет 0. Значит операция прошла без сбоя.

 

2) Цифровой контроль.

На том же примере. Сумма цифр А равна 6, следовательно контрольный код равен 0. Сумма цифр В равна 4, следовательно контрольный код этого числа есть 1. Значит числа А и В с учетом контрольных кодов запишутся так:

 

А = 1000111011 (00)

В = 0101001001 (01)

А + В = 1110000100 (01)

 

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

 

 

Глава 7.

 

ОСНОВЫ АЛГЕБРЫ ЛОГИКИ

 

Основные понятия алгебры логики

 

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

Функция f(x1, x2,..., xn) называется логической (переключательной), или булевой, если она, так же как и ее аргументы xi, может принимать только два значения: 0 или 1.

Логическая (булева) переменная эта такая величина x, которая может принимать только два значения: 0 или 1.

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

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

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

X = 1, если же ложно, то X = 0.

Высказывания с различным содержанием обозначаются разными буквами и считаются различными. Два высказывания называются эквивалентными, если истинности их одинаковые. Эквивалентность высказываний обозначается знаком равенства или тождества:, или же знаком. Например, запись A = B означает, что A и B либо истинны, либо ложны одновременно.

Как это будет показано в дальнейшем, в вычислительной технике символу состояния 1 чаще всего ставится в соответствие наличие некоторого сигнала, в частности электрического, а символу состояния 0 - отсутствие этого сигнала. Иначе говоря, если есть некоторый источник цифровой информации, который рассматривается в качестве определенной логической переменной, например переменной А, то при наличии сигнала от этого источника А = 1, а при отсутствии - А, 0.

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

Совокупность значений аргументов логической функции называется набором (или точкой) и может обозначаться, в частности, как х 1, х 2,..., х n, где xi равно нулю или единице (i = 1, 2,..., n). Очевидно, что набор значений аргументов фактически представляет собой некоторое двоичное число. Каждому набору значений аргументов приписывается номер, равный двоичному числу, которое соответствует значению данного набора. Например, для четырех аргументов 0, 0, 0, 0 - нулевой набор; 0, 0, 0, 1 - первый набор;

0, 0, 1, 0 - второй набор; 1, 0, 1, 0 - десятый набор и т.д.

Таким образом, логическая функция (функция алгебры логики) это функция f (x 1, x 2 ,..., x n) которая принимает значение 0 или 1 на наборе логических переменных x 1, x 2 ,..., x n. Каждой логической функции данного набора аргументов, также принято приписывать номер: 0, 1, 2,.......

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

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

Например, для одного аргумента имеем 21, т.е. 2 набора и 22, 4, т.е. четыре логические функции от одной переменной, которые приведены в таблице 7.1.

Т а б л и ц а 7.1

x f0(x) f1(x) f2(x) f3(x)

0 1 0 0 1

1 1 0 1 0

 

В связи с тем, что функция f0(x) равна единице при любых значениях аргумента, то эта функция называется абсолютно истинной (константа единицы), тогда функция f1(x) - абсолютно ложная функция (константа нуля). Функция f2(x), повторяющая абсолютное значение логической переменной, - тождественная функция: f2(x) x.

Функция f3(x), принимающая значение, обратное значению x, - логическое отрицание (инверсия), или функция НЕ (NOT), которая обозначается одним из следующих способов:

 

f3(x) = x = x.

 

Логическое отрицание или инверсия некоторой логической переменной, например переменной А, это также логическая переменная, принимающая значение обратное значению переменной А, и обозначаемая как А. Если А =1, то А = 0, если же А = 0, то А = 1. Но нужно учесть, что часто посредством отрицания, т.е. инверсии переменной просто обозначают случай, когда ее значение равно нулю.

В Таблице 7.2. приведен полный перечень всех шестнадцати элементарных логических функций от двух переменных x1 и x2.

Обратим внимание на следующие функции:

Дизъюнкция (логическое сложение) или функция ИЛИ (OR) - это функция f7(x1, x2), которая истинна тогда, когда истинна хотя бы одна из ее переменных. Условные обозначения этой функции:

 

f7(x1, x2) = x1 + x2 = x1 x2 = x1! x2

 

Это читается следующим образом: функция истинна, т.е. равна единице, когда аргумент x1 = 1, т.е. истинен, или аргумент x2 = 1, или же оба аргумента истинны одновременно.

 

 

Т а б л и ц а 7.2

 

Функция x1x2 Примечание

00 01 10 11

f0 0 0 0 0 f0 константа нуль

f1 0 0 0 1 x1 x2 конъюнкция

f2 0 0 1 0 x1 x2 запрет x2

f3 0 0 1 1 x1x2 x1x2 = x1 переменная x1

f4 0 1 0 0 x1 x2 запрет x1

f5 0 1 0 1 x1x2 x1x2 = x2 переменная x2

f6 0 1 1 0 x1 x2 сложение по модулю 2

f7 0 1 1 1 x1 x2 дизъюнкция

f8 1 0 0 0 x1 x2 функция Пирса

f9 1 0 0 1 x1 x2 равнозначность

f10 1 0 1 0 x1x2 x1x2 =x2 инверсия x2

f11 1 0 1 1 x2 x1 импликация

f12 1 1 0 0 x1 x2 x1x2 =x1 инверсия x

f13 1 1 0 1 x1 x2 импликация

f14 1 1 1 0 x1 / x2 функция Шеффера

f15 1 1 1 1 f1 константа единица

 

Конъюнкция (логическое умножение) или функция И (AND) - это функция f1(x1, x2), которая истинна тогда, когда все ее переменные одновременно истинны. Эту функцию условно обозначают следующим образом:

 

f1(x1, x2) = x1 x2 = x1 x2 = x1 & x2

 

Это читается следующим образом: функция истинна, т.е. равна единице, когда оба аргумента одновременно истинны, т.е. равны единице.

Функция (штрих) Шеффера или функция И-НЕ - это функция f14(x1, x2), которая ложна тогда, когда все переменные истинны. Условное обозначение этой фнкции:

f14(x1, x2) = x1/x2

 

Это читается следующим образом: функция ложна, т.е. равна 0, когда оба аргумента одновременно истинны, т.е. равны единице, и функция истинна, т.е. равна единице, когда или оба аргумента одновременно ложны, или же хотя бы один из них ложен.

Функция (стрелка) Пирса (Вебба) или функция ИЛИ-НЕ - это функция

f8(x1, x2), которая истинна только тогда, когда все переменные ложны. Условное обозначение этой функции:

 

f8(x1, x2) = x1 x2 = x1 O x2.

 

Это читается следующим образом: функция ложна, т.е. равна 0, когда хотя бы один из ее аргументов истинен, или же оба одновременно истинны, т.е. равны единице, и функция истинна, т.е. равна единице, когда оба аргумента одновременно ложны.

Импликация или функция ЕСЛИ-ТО (IF-THEN) это функция f13(x1, x2), которая ложна тогда и только тогда, когда x1 истинно и x2 ложно. Аргумент х1 называется посылкой, а х2 - следствием. Ее условное обозначение

 

f13(x1, x2) = x1 x2.

 

Исключающее ИЛИ (XOR) - это функция f6(x1, x2), которая обозначается знаком. Эта операция, как видно из таблицы, реализует функцию неравнозначности, т.е. фактически реализуется процедура суммирования по модулю 2, которая обозначается знаком:

 

f6(x1, x2) = x1 x2 = x1 x2

 

Все рассмотренные функции являются элементарными.

Из всех приведенных выше определениий ясно, что в алгебре логики все знаки действий: или &, или +,, и т.д, в отличии от обыкновенной алгебры, являются знаками логических связок, т.е. логических действий, а не знаками арифметических действий.

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

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

Логическая переменная x i действительна, если значение логической функции f(x1, x2,..., xn) изменяется при изменении x i. В противном случае эта переменная для данной функции фиктивна, т.е. не является ее аргументом.

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

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

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

 

И ИЛИ Искл. ИЛИ НЕ

01011010 0101010 0101010 01011010

11110000 1111000 1111000 10100101

01010000 1111010 1010010

 

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

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

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

Схема, реализующая элементарную логическую функцию НЕ:

 

 

x y =x или x y =x

 

Схема, реализующая элементарную логическую функцию ИЛИ:

 

x1

x2 y = (x1 x2) = (x1x2) или

Схема, реализующая элементарную логическую функцию И:

 

x1

x2 y = (x1 x2) = (x1 +x2) или

 

 

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

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

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