Двоичная система счисления
Вспомним материал по системам счисления. В нём говорилось, что наиболее удобной системой счисления для компьютерных систем является двоичная система. Дадим определение этой системе:
Для записи любого числа в двоичной системе счисления используются всего лишь 2 цифры: 0 и 1.
Общая форма записи двоичных чисел
Для целых двоичных чисел можно записать:
Данная форма записи числа «подсказывает» правило перевода натуральных двоичных чисел в десятичную систему счисления: требуется вычислить сумму степеней двойки, соответствующих единицам в свёрнутой форме записи двоичного числа.
Правила сложения двоичных чисел
Основные правила сложения однобитовых чисел
Отсюда видно, что и, как и в десятичной системе счисления, числа, представленные в двоичной системе счисления, складывают поразрядно. Если разряд переполняется, единица переносится в следующий разряд.
Пример сложения двоичных чисел
Правила вычитания двоичных чисел
Но как быть с 0-1=? Вычитание двоичных чисел немного отличается от вычитания десятичных чисел. Для этого используется несколько способов.
Вычитание методом заимствования
Запишите двоичные числа друг под другом – меньшее число под большим. Если меньшее число имеет меньше цифр, выровняйте его по правому краю (так, как вы записываете десятичные числа при их вычитании).
Некоторые задачи на вычитание двоичных чисел ничем не отличаются от вычитания десятичных чисел. Запишите числа друг под другом и, начиная справа, найдите результат вычитания каждой пары чисел.
Вот несколько простых примеров:
1 — 0 = 1
11 — 10 = 1
1011 — 10 = 1001
Рассмотрим более сложную задачу. Вы должны запомнить только одно правило, чтобы решать задачи на вычитание двоичных чисел. Это правило описывает заимствование цифры слева, чтобы вы могли вычесть 1 из 0 (0 — 1).
В первом столбце справа вы получаете разность 0 — 1. Для ее вычисления необходимо позаимствовать цифру слева (из разряда десятков).
Во-первых, зачеркните 1 и замените ее на 0, чтобы получить такую задачу: 1010 — 101 = ?
Вы вычли («позаимствовали») 10 из первого числа, поэтому вы можете написать это число вместо цифры, стоящей справа (в разряд единиц). 101100 — 101 = ?
Вычтите цифры в правом столбце. В нашем примере:
101100 — 101 = ?
Правый столбец: 10 — 1 = 1.
102 = (1 x 2) + (0 x 1) = 210 (цифры нижнего регистра обозначают систему счисления, в которой записаны числа).
12 = (1×1) = 110.
Таким образом, в десятичной системе эта разность записывается в виде: 2 — 1 = 1.
Вычтите цифры в оставшихся столбцах. Теперь это легко сделать (работайте со столбцами, двигаясь, справа налево):
101100 — 101 = __1 = _01 = 001 = 1.
Вычитание методом дополнения
Запишите двоичные числа друг под другом так, как вы записываете десятичные числа при их вычитании. Этот метод используется компьютерами для вычитания двоичных чисел, так как он основан на более эффективном алгоритме.
Однако простому человеку, привыкшему вычитать десятичные числа, этот метод может показаться более сложным (если вы программист, обязательно познакомьтесь с этим методом вычитания двоичных чисел).
Рассмотрим пример: 1011002 — 111012= ?
Если значность чисел разная, к числу с меньшей значностью слева припишите соответствующее количество 0.
1011002 — 0111012= ?
В вычитаемом числе поменяйте цифры: каждую 1 поменяйте на 0, а каждый 0 на 1.
0111012 → 1000102.
На самом деле мы «забираем дополнение у единицы», то есть вычитаем каждую цифру из 1. Это работает в двоичной системе, так как у такой «замены» может быть только два возможных результата: 1 — 0 = 1 и 1 — 1 = 0.
К полученному вычитаемому прибавьте единицу.
1000102+ 12 = 1000112
Теперь вместо вычитания сложите два двоичных числа.
1011002 +1000112= ?
Проверьте ответ. Быстрый способ – откройте двоичный онлайн калькулятор и введите в него вашу задачу. Два других метода подразумевают проверку ответа вручную.
1) Переведем числа в двоичную систему счисления:
Допустим, что из числа 1011012 нужно вычесть 110112
2) Обозначим как A число 1011012 и как B число 110112.
3) Запишем числа A и B столбиком, одно под другим, начиная с младших разрядов (нумерация разрядов начинается с нуля).
Системы счисления. Сравнение чисел. Решения
Решение Так как 208 – это 16. Таким образом, D416 +208 = D416 +1016 = E416 = 111001002. Теперь сравниваем поочередно заданные числа с полученным числом. Первое, второе и четвертое число меньше 111001002 (у них меньше трех единиц в начале, то есть, слева); втрое число больше, чем 111001002 (у них в начале больше трех единиц; последнее число равно 111001002.
Таким образом, среди заданных чисел ровно одно больше, чем D416 +208.
Как сравнивать двоичные числа
Пусть заданы два -разрядных двоичных числа
где старшие разряды этих чисел. Соотношения между числами описываются пятью функциями:
Легко заметить, что можно рассматривать только две функции, например, так как остальные достаточно просто выражаются через них:
Схемы, реализующие все соотношения (6.17) или несколько из них, называются схемами сравнения чисел (Magnitude Comparator).
Соотношения (6.17) между числами в позиционных системах счисления, в которых вес любого старшего разряда больше веса любого младшего разряда, довольно просто могут быть установлены на основании последовательного сравнения их одноименных разрядов. Сравнение чисел можно производить, начиная или с младшего или со старшего разряда. Предпочтительнее первый вариант сравнения, так как он допускает более естественный способ наращивания разрядности чисел.
Схемы сравнения чисел.
Для описания схем сравнения двоичных чисел введем в рассмотрение переключательные функции переменных:
Сравнение чисел будем производить, начиная с младшего разряда. Из соотношений (6.18) следует, что
Табл. 6.15 задает функции для одноразрядных двоичных чисел Из нее следует, что
Пусть теперь имеются функции для младших разрядов а числа двухразрядные, т. е. Структурная схема сравнения этих чисел изображена на рис. 6.79,а. Требуется синтезировать КС для функций аргументами которых являются переменные Табл. 6.16
Таблица 6.15. (см. скан) Сравнение одноразрядных чисел
представляет собой таблицу истинности, описывающую эту КС. В строках с номерами значения функций не определены так как не выполняется условие Функция при (старший разряд числа меньше старшего разряда числа а также при Функция только при Из диаграмм Вейча (рис. 6.79,б), построенных на основании табл. 6.16, следует, что
Если теперь составить таблицу истинности для функций аргументами которых являются переменные и
Таблица 6.16. (см. скан) Сравнение двухразрядных чисел
то она будет иметь такой же вид, что и табл. 6.16, а значит
Из соотношений (6.19) — (6.21) следует общая рекуррентная формула
в которой необходимо задать значения равными 0 или 1. Из выражений (6.22) следует, что
Из сравнения (6.23) с (6.19) находим Представляет интерес установить, какие функции из (6.17) будут соответствовать рекуррентным соотношениям (6.22) при других значениях Легко показать, что
Докажем, например, последнее соотношение, которое на основании (6.19) справедливо при Для этого следует показать, что соотношение (6.24) истинно и для Из (6.22) следует, что
т.е. утверждение (6.24) справедливо при любом
На рис. 6.80,а изображена схема сравнения одноразрядных двоичных чисел построенная на основании выражений (6.23), а на рис. 6.80, б — ее условное графическое обозначение. Схема сравнения 4-разрядных двоичных чисел реализующая функции может быть построена по рекуррентным соотношениям (6.22) при (рис. 6.80,в). Недостатком такой КС является низкое быстродействие, так как сигналы соответствующие младшим разрядам сравниваемых чисел, последовательно проходят через все элементы, имеющие конечное быстродействие. Достоинство данной простота ее реализации при программируемости выполняемых функций с помощью входов
Если последовательными подстановками значений развернуть соотношения (6.22) при то можно получить:
Схема, реализованная в соответствии с этими функциями, будет иметь значительно большее быстродействие, чем схема, показанная на рис. 6.80, так как раскрытие скобок при развертывании соотношений (6.22) уменьшило порядок переключательных функций
Из (6.24) следует, что
Докажем это соотношение, используя закон двойственности и другие тождества алгебры логики:
Из соотношений (6.26) и (6.27) следует, что
Приведенные соотношения не являются единственными для построения схем сравнения двоичных чисел. На рис. 6.81 приведены ИС:
561ИП2 — схема сравнения -разрядных двоичных чисел, реализующая функции ;
555СП1 — схема сравнения -разрядных двоичных чисел, реализующая функции ;
CD4063В — схема сравнения -разрядных двоичных чисел, реализующая функции ;
74L85 (134СП1) — схема сравнения -разрядных двоичных чисел, реализующая функции
Схема сравнения 561ИП2 спроектирована в соответствии с соотношениями (6.25) и (6.27). Функции, выполняемые программируются с помощью входов что видно из табл. 6.17, составленной на основании выражений На рис. 6.81 для ИС 561ИП2 введены обозначения:
(входные управляющие сигналы, использующиеся для каскадирования ИС и программирования выполняемых функций),
(выходные сигналы Аналогичные обозначения введены и для остальных ИС, представленных на рис. 6.81.
Таблица 6.17. (см. скан) Функционирование ИС 561ИП2
Интегральные схемы, имеющие одинаковые номера (например, всегда имеют одно и то же функциональное назначение, но могут выполнять несколько различающиеся функции. Это вызвано тем, что при совершенствовании технологии изготовления ИС вводились и усовершенствования схемотехнических решений функциональных узлов. Для построения 4-разрядных ИС сравнения двоичных чисел можно использовать самые различные преобразования функций а также и другие функции. Введем функцию
Из сравнения соотношения (6.29) с (6.18) следует, что функция может быть получена из выражения (6.22) для функции
а функция из выражения (6.25) для взаимной заменой переменных
Реализация функций позволяет получить полностью симметричную схему относительно операций «меньше» и «больше». Интегральная схема (рис. 6.81) выполняет функции сравнения 4-разрядных двоичных чисел:
где переключательные функции определяются соотношениями (6.25) и (6.30). Как видно из (6.31), функции, выполняемые могут программироваться сигналами (табл. 6.18).
Таблица 6.18. (см. скан) Функционирование ИС 555СП1
Третий вариант схемы сравнения реализован в которая выполняет функции где
а функция получается из функции взаимной заменой переменных и заменой на Легко убедиться, что при схема выполняет функции
Четвертый вариант схемы сравнения реализован в ИС 74L85, которая выполняет функции
Из этих соотношений следует, что
Каскадирование схем сравнения двоичных чисел. На рис. 6.82 показана -разрядная схема сравнения двоичных чисел, построенная на трех 4-разрядных ИС 561ИП2 (символ означает, что вход следует подключить либо к корпусу, либо к источнику питания) Из рис. 6.82 и соотношений (6.26) и (6.27) следует, что функции
где Подставив (6.26) в (6.32), получим:
Аналогично на основании рис. 6.82 можно получить:
Из этих соотношений видно, что функции, выполняемые схемой на рис. 6.82, также задаются табл. 6.17 (индексы следует просто заменить на индексы и Сигналы и подаются на младшую ИС, а сигнал на старшую ИС (деление на младшие и старшие ИС производится в соответствии
с младшими и старшими разрядами сравниваемых чисел). На входы всех остальных ИС подаются значения (либо 0 В, либо ).
Можно построить схему последовательного включения и большего числа ИС 561ИП2 для сравнения -разрядных чисел, где число ИС. На рис. 6.83,а показана структурная схема сравнения 16-разрядных чисел при последовательном включении ИС 561ИП2. Каскадирование схем сравнения CD4063B при последовательном их включении представлено на рис. 6.83, б.
На рис. 6.84 показана схема сравнения -разрядных двоичных чисел, построенная на трех ИС 555СП1. Из рис. 6.84 на основании (6.31) следует, что
где Подставив в (6.33) значения (6.31) функций получим:
(кликните для просмотра скана)
Аналогично можно получить и функции
т.е. функции, выполняемые схемой на рис. 6.84, программируются сигналами (табл. 6.18).
Аналогично схеме на рис. 6.84 можно построить схему сравнения -разрядных чисел с последовательным включением На рис. 6.85 изображена структурная схема для сравнения 16-разрядных двоичных чисел. Программирование функций при последовательном включении сигналами будет определяться табл. 6.18: при нечетном при четном При последовательном включении ИС значительно снижается быстродействие схем сравнения многоразрядных чисел.
Каскадирование ИС сравнения двоичных чисел можно производить и при параллельном их включении. На рис. показано включение ИС 561ИП2 в качестве преобразователя разрядности сравниваемых чисел. Из рис. следует, что Подставив эти значения в (6.26) и (6.27), получим:
функция Из (6.34) видно, что соотношения «меньше», «больше» и «равно» между 4-разрядными числами полностью переносятся на функции (например, если то и которые можно рассматривать, как одноразрядные числа. На рис. 6.86,б приведено упрощенное обозначение этого преобразователя.
Схема сравнения -разрядных двоичных чисел при параллельном включении ИС 561ИП2 показана на рис. 6.87, а полная ее структурная схема — на рис. 6.88 (все входные сигналы последовательно проходят только через две Интегральные схемы включены в качестве преобразователей разрядности сравниваемых чисел. Программирование выполняемых схемой функций осуществляется сигналами в соответствии с табл. 6.17. Если в схеме на рис. 6.87 положить то ее можно использовать в качестве преобразователя -разрядных чисел в одноразрядные числа с сохранением соотношений «меньше», «больше» и «равно». Тогда вместо можно включить такие -разрядные преобразователи, а можно заменить на схему из результате получится схема сравнения 100-разрядных
(кликните для просмотра скана)
(кликните для просмотра скана)
двоичных чисел, причем последовательно будет включено не более трех ИС 561ИП2.
На рис. 6.89 показано включение ИС 555СП1 в качестве преобразователя разрядности сравниваемых чисел. Из рис. 6.89 следует, что
Подставив эти значения в (6.33), получим:
Из (6.35) видно, что соотношения «меньше», «больше» и «равно» между -разрядными числами полностью переносятся на функции (например,
(кликните для просмотра скана)
если то которые можно рассматривать, как одноразрядные числа.
Схема сравнения -разрядных двоичных чисел при параллельном включении ИС 555СП1 показана на рис. 6.90, а полная ее структурная схема — на рис. 6.91 (все входные сигналы последовательно проходят только через две Интегральные схемы используются в качестве преобразователей разрядности сравниваемых чисел. Программирование выполняемых схемой функций осуществляется сигналами в соответствии с табл. 6.18 для функций Если в схеме на рис. 6.90 положить то ее можно использовать в качестве преобразователя -разрядных чисел в одноразрядные числа с сохранением соотношений «меньше», «больше» и «равно». Тогда вместо можно включить такие -разрядные преобразователи, а можно заменить на схему из В результате получится схема сравнения -разрядных двоичных чисел, причем последовательно будет включено не более трех ИС 555СП1.
В табл. 6.19 приведены основные характеристики различных схем сравнения двоичных чисел [23] при параллельном включении ИС.