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

Правила двоичной арифметики

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

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

Таблица 3.1

Правила арифметических операций

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

Заем из (i +1)-го разряда передается в i-й разряд с уменьшенным вдвое весом и увеличенным вдвое значением.

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

При вычитании двоичных чисел (см. табл. 3.1) в данном разряде при необходимости занимается единица из соседнего (старшего) разряда. Эта занимаемая единица равна двум единицам данного разряда. Заем производится каждый раз, когда цифра в разряде вычитаемого больше цифры в том же разряде уменьшаемого. Например, при вычитании:

единица из разряда с весом 2 4 была занята в разряд с весом 2 3 ; эта единица стала там двойкой, и в разряде с весом 2 3 выполнилось вычитание 10-1 = 1; на месте разряда с весом 2 4 в уменьшаемом фактически остался нуль.

Распространение займа сразу на несколько более старших разрядов можно проследить на примере вычитания чисел 101110,001 (2) и 101,011 (2) . Записав числа друг под другом:

нетрудно заметить, что в разряде с весом 2 -2 в результате вычитания должен произойти заем из разряда с весом 2 1 . Перепишем пример с учетом фактического расположения цифр после заема и выполним вычитание. Вместо зачеркнутых цифр необходимо использовать в качестве уменьшаемого надписанные цифры. Окончательный результат (разность) составляет 101000,110 (2) .

Пример . Уменьшаемое 1000000 (2) , вычитаемое 1 (2) , разность составляет

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

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

В основном арифметические операции выполняются на одном общем устройстве, называемом арифметико-логическим устройством (АЛУ).

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

, Конкурс «Презентация к уроку»

Презентация к уроку

Назад Вперёд

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

Цели урока: (слайд 2)

1. Познакомить учащихся с двоичной системой счисления.
2. Сформировать навыки выполнения арифметических действий с двоичными числами

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

Все позиционные системы счисления ”одинаковы”, а именно, во всех них арифметические операции выполняются по одним и тем же правилам:

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

Рассмотрим правила выполнения арифметических операций

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

Ребята выполняют работу самостоятельно. Потом открыть слайд с ответами.

Ответы. (Слайд 13)

1. Выучить правила выполнения арифметических действий в двоичной системе счисления.

2. Выполните действия:

1. 110010+11,01
2. 1111001-1101
3. 10101,1*11
4. 10101110:101

Арифметические операции во всех позиционных системах счисления выполняются по одним и тем же хорошо известным вам правилам.

Сложение. Рассмотрим сложение чисел в двоичной системе счисления. В его основе лежит таблица сложения одноразрядных двоичных чисел:

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

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

В качестве примера сложим в столбик двоичные числа 110 2 и 11 2 :

Проверим правильность вычислений сложением в десятичной системе счисления. Переведем двоичные числа в десятичную систему счисления и затем их сложим:

110 2 =1*2 2 + 1*2 1 + 0*2 0 = 6 10 ;

11 2 = 1*2 1 + 1*2 0 = 3 10 ;

6 10 + 3 10 = 9 10 .

Теперь переведем результат двоичного сложения в десятичное число:

1001 2 = 1*2 3 +0*2 2 + 0*2 1 + 1*2 0 = 9 10 /

Сравним результаты – сложение выполнено правильно.

Вычитание. Рассмотрим вычитание двоичных чисел. В его основе лежит таблица вычитания одноразрядных двоичных чисел. При вычитании из меньшего числа (0) большего (1) производится заем из старшего разряда. В таблице заем обозначен 1 с чертой:

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

Умножение. В основе умножения лежит таблица умножения одноразрядных двоичных чисел:

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

Деление. Операция деления выполняется по алгоритму, подобному алгоритму выполнения операции деления в десятичной системе счисления. В качестве примера произведем деление двоичного числа 110 2 и 11 2:

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

Сложение

Допустим нам нужно найти сумму двух двоичных чисел: 10011001110 + 11000101110. Как это сделать. Правила сложения двоичных чисел такие же, как и для десятичных. С той только разницей, что каждый разряд суммы может принимать только два значения - ноль или единица. Точно так же, как и в десятичной системе, для сложения чисел их удобно записать в столбик:

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

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

Умножение

Умножение двоичных чисел, также схоже на умножение десятичных. Сейчас мы так же покажем этот процесс на примере. Вспомните, как вы умножаете два десятичных числа столбиком. Вот пример умножения двоичных чисел столбиком:

Точно так же, как и при умножении двоичных чисел, мы умножаем первое число на каждый разряд второго и записываем полученные результаты под первой чертой, одно под другим со здвигом. Затем полученные промежуточные результаты мы складываем с учетом сдвига. Однако в случае с двоичными числами имеется одно существенное отличие. Так как любой разряд двоичного числа либо ноль, либо единица, то промежуточное умножение сильно облегчается. В самом деле, любое число, умноженное на единицу, равно самому себе. Любое число, умноженное на ноль, равно нулю! Поэтому тут и вычислять то ничего не нужно. Именно по этому умножение двух двоичных чисел сводится к операциям сдвига и сложения. Это очень важно для построения вычислительных машин. Теперь ясно, что нам не нужны какие нибудь там "умножители". Для реализации операций сложения и умножения нам нужны только сумматоры и сдвиговые регистры. С их устройством вы можете познакомиться на нашем сайте.

Вычитание

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

Правила перевода числа из десятичного представления в двоичное читайте в разделе «Системы исчисления».

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

• Перевести вычитаемое в дополнительный код.
• Сложить эти два числа (уменьшаемое и вычитаемое в дополнительном коде).
• При сложении перенос из самого старшего разряда не учитывать.
• Полученный результат и есть разность.

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

Число 13 берем в прямом двоичном коде (00001101).

Число 5 переводим в дополнительный двоичный код 5 (11111011).

Теперь производим сложение:

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

Для проверки переведем полученный результат в десятичный вид. 1000 в двоичной системе это 8 в десятичной. Советую внимательно проверить приведенный пример в соответствии с таблицей сложения (см выше).

Умножение и деление на 2

Аналогично происходит делениена 2. Только наоборот. Для того, что бы разделить двоичне числа на 2 (двоичное 10) нужно просто отбросить ноль в младшем разряде числа и все остальные разряды сдвинуть на один разряд вправо. Если в младшем разряде искомого числа не ноль, а единица, то это значит, что число не делится на два нацело. В этом случае возможно деление с остатком.

Примечание: Вы можете сами потренироваться в умножении на два с другими числами. О переводе из десятичного представления числа в двоичное смотри здесь.

Деление на произвольное число

Вспомним как мы делим одно число на другое в десятичной системе исчисления. Я имеется в виду деление столбиком или углом. Точно так же происходит деление в двоичной системе. Вот пример деления двух двоичных чисел:

Сначала мы записываем делимое. В данном случае это число 1000001 (в десятичном виде 65). Затем, справа от него, рисуем угол. В верхней части угла записываем делитель. В нашем случае – это 101 (десятичное 5). Затем мы начинаем находить частное по разрядно. В десятичной системе исчисления в данном случае мы подбираем, на какое число от 1 до 9 нужно умножить делитель, для того, что бы результат был бы все же меньше, чем три первые разряда делимого. Если такого числа не находится, то берут первые четыре разряда делимого. В двоичной системе исчисления любой разряд может принимать только два значения – ноль или единица. Поэтому выбор у нас гораздо меньший. Делитель можно умножать только на 1 либо на ноль. При этом в первом случае он останется неизменным, а во втором он будет равен нулю. Нам придется лишь проверять не больше ли делитель, чем число, составляющее первые три разряда делимого. Как видим первые три разряда составляют число 100, что меньше, чем 101. Поэтому берем первые четыре разряда делимого. Число, составляющее первые четыре разряда делимого (1000) естественно больше делителя. Поэтому мы записываем делитель под первыми четырьмя разрядами делимого и вычитаем эти два числа. Получаем разность 11. В первый разряд частного записываем 1.

Находим следующий разряд частного. Для этого сносим следующий разряд делимого (так же, как это делается при делении в десятичной системе). Проверяем – можно ли теперь вычесть из него 101. Число 110 больше, чем 101. Поэтому мы записываем единицу в следующий разряд частного и производим вычитание этих двух чисел. Разность равна 1.

Далее ищем третий разряд частного. Сносим еще один ноль с очередного разряда делимого. Но из числа 10 невозможно вычесть 101. 10 меньше, чем 101. Поэтому записываем в очередной разряд частного ноль и сносим последний разряд делимого. Теперь вычитание возможно. Более того, результат вычитания равен нулю. Это означает во первых, что последний разряд частного равен единице, а во вторых то, что число 1000001 поделилось на 101 без остатка. Результат деления равен 1101 (десятичное 13).

Заключение

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

роизвольное натуральное число можно единственным способом представить в виде суммы степеней двойки, например 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.