Арифметика двоичных чисел. Формальные правила двоичной арифметики. Прямой, обратный и дополнительный коды

роизвольное натуральное число можно единственным способом представить в виде суммы степеней двойки, например 23 = 16+4+2+1. Обозначая входящие в эту сумму степени двойки единицами, а не входящие в ее степени нулями, можно кратко обозначить эту сумму булевым набором (в другой терминологии - вектором) (10111) 2 . Индекс 2 напоминает о том, что число записано в двоичной системе. Единица, стоящая в младшем (самом левом) разряде, означает слагаемое 1, единица во втором слева разряде означает слагаемое 2, единица в третьем разряде означает 4, а нуль в четвертом разряде означает отсутствие слагаемого 8, единица в четвертом (старшем) разряде означает присутствие слагаемого 16 (в большинстве случаев разумно рассматривать только такие записи чисел в двоичной системе, в которых в старшем разряде стоит единица).

Главное достоинство двоичной системы (помимо естественности ее применения в электронной цифровой технике) - исключительная простота алгоритмов арифметических операций в ней. Таблица умножения в двоичной системе совсем не требует запоминания: любое число, умноженное на нуль дает нуль, а умноженное на единицу равно самому себе. Правило деления сводится к двум равенствам 0/1 = 0, 1/1 =1, благодаря чему деление столбиком в двоичной системе делается проще, чем в десятичной, и по существу сводится к многократному вычитанию. Таблица сложения в двоичной системе чуть сложнее таблицы умножения (в отличие от десятичной системы), так как 1+1 = (10) 2 и возникает перенос в следующий разряд.

Правило сложения двух битов в двоичной системе задается формулами x+y = 2v+u, v = x&y, u = xÅy. В силу симметрии для их проверки достаточно рассмотреть не четыре, а три случая: 0+0 = (00) 2 , 1+0=0+1= (01) 2 , 1+1 = (10) 2 . Схема, выполняющая это сложение, называется полусумматором (в англоязычной литературе: half adder) и обозначается обычно HA или FA2. Эта схема (в базисе {AND, XOR}) изображена на рисунке.

Схемы для арифметических операций над многоразрядными двоичными числами. Сложение двух n-разрядных двоичных чисел (x n ,….,x 1) 2 и (y n ,….,y 1) 2 как и в десятичной системе приводит к появлению переносов в следующий разряд, которые необходимо учитывать в вычислении. Эти переносы также равны нулю или единице (если перенос равен нулю, то в ручном вычислении он фактически не выполняется, но логическая схема обязана правильно работать и в этом случае, ведь она «не знает», какой перенос пришел из предыдущего разряда). Обозначим перенос из (i-1)-го разряда в следующий i-й разряд через w i (w 1 =0, потому что предыдущего разряда в этом случае просто нет). Тогда для вычисления z i (i-го бита результата) нужно сложить биты x i и y i и бит переноса w i . Это сложение выполняем по формулам

x i + y i +w i = 2v i +u i , v i =m(x i ,y i ,w i), u i =l(x i ,y i ,w i)

с помощью схемы FA3. Тогда z i =u i =l(x i ,y i ,w i), а следующий бит переноса w i +1 = v i =m(x i ,y i ,w i). При сложении n-разрядных чисел получается вообще говоря n+1-разрядное число. Его старший бит z n +1 = w n +1 равен последнему переносу.

Схема сложения трехразрядных чисел приведена на следующем рисунке. Аналогичным образом выглядит и схема сложения n-разрядных чисел.

Сложность указанного n-разрядного сумматора равна 5n-3. Н.П.Редькин доказал, что сумматоров для n-разрядных чисел меньшей сложности в базисе {AND,OR,XOR,NOT} не существует. Построенный сумматор является поэтому минимальной схемой. Но у этой схемы есть существенный недостаток - она имеет большую глубину. Глубиной схемы называется максимальное число ее элементов, образующих цепь, соединяющую какой-либо из входов схемы с одним из ее выходов. Например, глубина указанной выше схемы FA3 равна 3.

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

Теоретически вычислить задержку реальной схемы очень сложно. Цепей элементов схемы, соединяющих ее входы с выходами (эти цепи также называют путями), обычно довольно много и задержка схемы определяется задержкой по самому плохому в определенном смысле пути, который называется критическим. Например, на схеме FA3 критический путь, вероятно, соединяет входы X или Y с выходом m. Задержка по любому пути определяется не только суммой задержек всех элементов, лежащих на этом пути (в приведенном примере она равна 3, если считать задержку каждого элемента единичной). Следует учитывать также задержку соединяющих эти элементы проводов. Задержка элемента зависит от того, между каким его входом и каким его выходом она измеряется, а также от электрических характеристик самого элемента и элементов непосредственно с ним связанных в рассматриваемой схеме, она зависит от температуры схемы и даже от того, какие логические значения подаются в рассматриваемый момент на входы этого элемента и изменяется ли (и в какую сторону) значение на его выходе. Тем не менее, хотя и не очень точно, задержку пути можно оценить как сумму задержек его элементов. Если задержки всех элементов равны, то эта величина определяется глубиной схемы. Разумеется, понятие глубины схемы можно расширить, допустив, что элементы базиса могут иметь произвольные неотрицательные задержки.

Глубина указанной выше схемы n-разрядного сумматора на первый взгляд равна 3n-2. Но внимательный анализ возможных критических путей показывает, что она на самом деле равна 2n-1. Все равно это очень много и построенная таким образом реальная схема будет иметь большую задержку. На практике используются схемы, имеющие одновременно малую сложность, не превосходящую Cn (где С - небольшая константа) и малую глубину, приблизительно равную 2log 2 n. В.М. Храпченко в 1970 г. построил схему малой сложности и глубины, асимптотически равной log 2 n (т.е. равную (1+ e(n)) log 2 n, где e(n) стремится к нулю с ростом n). Он же недавно доказал, что глубина сумматора не может быть меньше log 2 n + log 2 n (log 2 (log 2 n))). Поэтому построенная им схема имеет асимптотически минимальную глубину. Однако схема Храпченко превосходит обычные схемы только при n порядка тысячи. Тем не менее существует некоторая модификация его схемы с глубиной приблизительно равной log j n, где j = (Ö5+1)/2, и эта схема имеет глубину меньшую, чем стандартные схемы, уже начиная с n = 8. В 2008 г. М.И.Гринчук построил схему глубины не большей log 2 n+log 2 (log 2 n)+6, которая уже при малых n имеет меньшую глубину, чем все известные схемы.

Задача построения оптимальных схем для умножения n-разрядных чисел оказалась еще труднее, чем задача о построении оптимальных сумматоров. Легко построить схему для умножения n-разрядных чисел в базисе {OR,AND,XOR,NOT} сложности приблизительно равной 6n 2 . Для этого можно использовать указанную выше схему для сумматора. Однако ее глубина будет велика. В начале 60-х годов несколько исследователей (в СССР Столяров и Офман, в США Авиценис и Уоллес) независимо построили схему для умножения сложности порядка n 2 и глубины порядка log 2 n. В смысле глубины эти схемы по порядку оптимальны, но до сих пор остается нерешенной задача построения схемы для умножения асимптотически минимальной глубины. В смысле сложности эти схемы оказались далеки от оптимальных. А. А. Карацуба построил в 1962 г. схему для умножения, имеющую сложность по порядку не большую n 1,6 , потом А. Л. Тоом построил схему сложности n 1+ e(n) , где e(n) стремится к нулю с ростом n. В определенном смысле этот результат окончательный, тем не менее он был уточнен на рубеже 70-х годов немецкими математиками А. Шенхаге и Ф. Штрассеном, которые получили для схем умножения верхнюю оценку сложности по порядку не превосходящую n log 2 n log 2 (log 2 n), а в 2008 г. эту оценку улучшил американский математик М. Фюрер, заменивший двойной логарифм крайне медленно растущей функцией. Есть предположение, что сложность схемы умножения по порядку не меньше n log 2 n, но и это не доказано.

Американский математик С.Кук доказал, что можно построить схему для деления 2n-разрядного числа на n-разрядное, у которой сложность по порядку не превосходит сложности умножения n-разрядных чисел. Известно также, что нижняя оценка сложности схемы для деления по порядку не меньше нижней оценки сложности умножения. Поэтому в смысле оценок сложности деление не представляет ничего нового в сравнении с умножением. Однако долгое время наилучшей оценкой глубины деления по порядку было (log 2 n) 2 .

Впоследствии были найдены схемы для деления с глубиной по порядку равной log 2 n, но их сложность оказалась велика. Американцы Рейф и Тейт построили схемы для деления глубины по порядку не превосходящей log 2 n log 2 (log 2 n) и одновременно сложности по порядку не превосходящей n log 2 n log 2 log 2 n, однако и эти схемы, как и схемы Шенхаге-Штрассена и Фюрера пока не нашли практических применений, так как в действительности начинают превосходить используемые на практике схемы лишь при огромных значениях n.

Рекомендуемая литература

1. О.Б. Лупанов « Асимптотические оценки сложности управляющих систем » изд. МГУ, 1984.
2. О.Б. Лупанов «Конспект лекций по математической логике »изд. МГУ, 2009.
3. Дж. Сэвидж «Сложность вычислений » М. изд. Факториал, 1998.
4. Д. Кнут « Искусство программирования на компьютере», т. 2, изд. Вильямс, 2000.
5. С.Б. Гашков «Системы счисления и их применения », М. изд. МЦНМО, 2004.
6. С.Б. Гашков, В.Н. Чубариков «Арифметика. Алгоритмы. Сложность вычислений », изд. Дрофа, 2005.

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

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

Таблица сложения, вычитания и умножения для двоичной системы счисления

Сложение двоичных чисел

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

Пример : 1011,1 2 + 1010,11 2

Интересна также ситуация, когда складываются больше двух чисел. В этом случае возможен перенос через несколько разрядов.
Пример : 111,1 2 + 111 2 + 101,1 2

При сложении в разряде единиц (разряд 0) оказывается 4 единицы, которые, объединившись, дают 100 2 . Поэтому из нулевого разряда в первый разряд переносится 0 , а во второй — 1 .
Аналогичная ситуация возникает во втором разряде, где с учетом двух перенесенных единиц получается число 5 = 101 2 . 1 остается во втором разряде, 0 переносится в третий и 1 переносится в четвёртый.

Вычитание двоичных чисел

В случаях, когда занимается единица старшего разряда, она дает две единицы младшего разряда. Если занимается единица через несколько разрядов, то она дает по одной единице во всех промежуточных нулевых разрядах и две единицы в том разряде, для которого занималась.
Пример : 10110,01 2 — 1001,1 2

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

В общем случае процедуры сложения и вычитания двух чисел

A B = C в любой позиционной системы счисления начинаются с младших разрядов.

Код суммы каждго i -того разряда с i получается в результате сложения

a i + b i +1, где единица соответствует переносу из младшего (i - 1)-разряда в i -тый, если в младшем разряде код суммы получился больше или равным основанию системы счисления.

Код разности каждого i -того разряда получается в результате вычитания

a i - b i -1, где единица соответствует заему, если он был, в младшие разряды величины, равной основанию системы счисления.

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

Теперь рассмотрим правила арифметики с числами, представленными в двоичном коде.

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

1 + 1 = 0 и осуществляется перенос 1 в старший соседний разряд.

Например:

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

0 - 1 =1 после заема единицы из соседнего старшего разряда.

Например:

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

Умножение двоичных чисел производится путем образования про-межуточных произведений и последующего их суммирования. Промежуточные поразрядные произведения формируются по следующим правилам:

0 x 0 = 0 101 510 x 310 = 1510

0 x 1 = 0 11

1 x 1 = 1 + 101

Деление чисел в двоичной системе производится по правилам умножения и вычитания.

Например:

110: 11 = 10 610: 310 = 210

Арифметические действия с двоичными числами подробно будут рассмотрены в дальнейшем.

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

ai HS S ci ai SM S ci

bi P Pi Pi-1 P Pi

Рис.2.1 Условное обозначение полусумматора (а)

и двоичного сумматора (б).

Здесь a i и b i это i -тые разряды чисел А и В, которые складываются, а c i - i -тый разряд суммы этих чисел, Pi - перенос из данного разряда в соседний следующий старший, Pi-1 - перенос из соседнего младшего в данный разряд.

Если для представления двоичных чисел А, В, С и их знаков выделена

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

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

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

A+B=C можно представить следующим образом:

где Рr - некоторые регистры, в которые записываются двоичные числа А, В и С; СM - сумматор, точнее группа сумматоров n SM, где n - длина разрядной сетки, отведенной для представления чисел А, В и С.

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

Кроме этих операций в цифровых автоматах, компьютерах, выполняется еще одна операция над двоичными числами - это сдвиг числа по разрядной сетке влево или вправо. В случае сдвига влево фактически осуществляется умножение двоичного числа на 2, а при сдвиге вправо - деление на 2, где - количество разрядов, на которое сдвигается двоичное число. Например: 0000112= 310 сдвинем влево на 2 разряда, получим 0011002 = 1210, т.е.

3х4(22) = 1210, а теперь 0010002 = 810 сдвинем на 2 разряда вправо, получим 0000102 = 210, т.е. 8:4(22) = 210.

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

В простейшем случае, для одноразрядных чисел, правила двоичного сложения имеют вид:

При сложении () возникает два случая:

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

Двоичное вычитание

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

Когда производится вычитание () осуществляется займ из более старшего разряда. Знак вопроса означает, что разряд уменьшаемого изменяется в результате займа по правилу:

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

Рассмотрим несколько примеров вычитания многоразрядных чисел (из большего числа вычитается меньшее).

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

Двоичная арифметика с учетом знаков чисел

Прямой, обратный и дополнительный коды

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

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

Так, в восьмиразрядном формате

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

Для того же числа обратный код имеет вид: , .

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

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

Для значащих разрядов отрицательного числа справедлива формула:

Напишем число в 7-разрядном дополнительном коде:

Таким образом в дополнительном коде , следовательно, указанный недостаток обратного кода преодолен.

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

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

Двоичная арифметика в дополнительном коде

Для наглядности возьмем два десятичных числа, например, и , и сделаем все возможные варианты вычислений:

.

Число положительное, поэтому ОК=ПК , для проверки числа нужно перевести его значащие разряды в десятичный код по (П3-2): .

• . Сначала получим дополнительный код отрицательного числа :

  

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

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

  

  а затем уже перевести его в десятичный код по (П3-2): .

• - Сначала получим ДК отрицательного числа .

  

  После этого произведем вычисления.

Цель работы. Научиться выполнять арифметические операции (сложение, вычитание, умножение и деления) с двоичными числами.

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

Задание 1. Выполните сложение чисел в двоичной системе счисления 100100111,001 2 +100111010,101 2

Методические указания.

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

Примеры .

1) Выполнить сложение двоичных чисел X=1101, Y=111.

В приведенном примере в младшем нулевом разряде две единицы: 1+1=10 дают нуль в данном разряде и единицу переноса в следующий. В первом разряде: 0+1+1=10 (крайняя единица перенесена из нулевого разряда) дают 0 и единицу переноса в следующий. Во втором разряде 1+1+1=11(крайняя единицы перенесена из первого разряда) дают 1 и единицу переноса в следующий. В старшем третьем разряде 1 и единица переноса из предыдущего разряда дают 1+1=10.

Результат: 1101+111=10100.

2) Сложить три двоичных числа X=1101, Y=101, Z=111.

Результат: 1101+101+111=11001.

Задание 2. Выполните вычитание чисел в двоичной системе счисления: 1100110110,0011 2 – 11111110,01 2 .

Методические указания.

При вычитании двоичных чисел в данном разряде при необходимости занимается 1 из старшего разряда. Эта занимаемая 1 равна двум единицам данного разряда, так как 10=1+1.

Примеры .

1) Заданы двоичные числа X=10010 и Y=101. Вычислить X–Y.

Результат: 10010 2 – 101 2 = 1101 2 .

Замечание. Число 100…00 2 можно представить в виде суммы

Данное разложение на слагаемые объясняет правило вычитания в столбик. Если вы занимаете 1 из ближайшего старшего разряда, тогда над всеми следующими за единицей нулями следует дописывать 1, а над крайним нулем, для которого произведен заем, 1+1 или 10.

2) Выполнить вычитание: 1100000011,011 2 – 101010111,1 2

Результат: 1100000011,011 2 – 101010111,1 2 = 110101011,111 2 .

Задание 3. Выполните умножение чисел 11001 2 и 1011100 2 в двоичной системе счисления.

Методические указания.

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

Пример . Найти произведение 1001 2 101 2

101

Задание 4. Выполните деление чисел 111101 2 и 1110 2 в двоичной системе счисления.

Методические указания.

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

Пример . Найти частное от деления 1100, 011 2 : 10, 01 2

Результат: 1100, 011 2 : 10, 01 2 =101, 1 2 .

Задания для самостоятельной работы

Контрольные вопросы.

1. Каковы правила сложения двоичных чисел?

2. Каковы правила вычитания двоичных чисел?

3. Каковы правила умножения двоичных чисел?

4. Каковы правила вычитания двоичных чисел?