Деление двоичных чисел в прямом, обратном и дополнительном кодах

Министерство образования Республики Таджикистан

Таджикский Технический Университет им. ак. М. С. Осими

кафедра АСОИиУ

Курсовая работа

на тему: «Деление двоичных чисел в прямом, обратном

и дополнительном кодах»

Душанбе 2009

Оглавление

Аннотация

Введение

Позиционные системы счисления

Двоичная арифметика

Правила перевода

Перевод целых чисел

Перевод дробных чисел

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

Сложение и вычитание в прямом, обратном и дополнительном кодах

Деление в прямом, обратном и дополнительном кодах

Заключение

Использованная литература

Аннотация

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

В середине ХХ века развитие атомной физики, ракетной и космической техники потребовало решения вычислительных задач такого большого объёма, что с ними нельзя было справиться при помощи в то время средств вычислительной техники – клавишных или перфорационных машин.

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

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

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

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

Введение

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

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

По делению в двоичном коде мы пройдёмся подробней. Будут рассмотрены методы реализования деления двоичных чисел в прямом, обратном и дополнительном кодах. В частности будут рассмотрены два основных метода организации деления двоичных чисел, а именно метод деления с восстановлением остатка и метод деления без восстановления остатка (этот метод аналогичен простому делению «в столбик»). Их преимущества и недостатки, принципы построения алгоритма.

Позиционные системы счисления

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

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

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

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

Количество s различных цифр, употребляемых в позиционной системе, называется ее основанием. Эти цифры обозначают s целых чисел, обычно 0, 1, ... , (s - 1). В десятичной системе используются десять цифр: О, 1, 2, 3, 4, 5, 6, 7, 8, 9 и поэтому эта система имеет основанием число десять.

В общем случае позиционной системы с основанием s любое число х может быть представлено в виде полинома от основания s:

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

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

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

С учетом сказанного в десятичной системе счисления запись 6097, 108 означает число:

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

Наибольшее распространение в ЦВМ имеет двоичная система счисления. В этой системе используются только две («двоичные») цифры: (нуль) и 1 (единица).

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

где αi могут быть либо 0, либо 1. Эта запись соответствует сумме степеней числа 2, взятых с указанными в ней коэффициентами:

Например, двоичное число

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

Изображения некоторых чисел в десятичной, двоичной, восьмеричной и шестнадцатеричной системах счисления показаны в таблице:

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

Помимо двоичной системы счисления в ЦВМ используются также другие системы с недесятичным основанием - восьмеричная и шестнадцатеричная, имеющие основанием соответственно числа 8 и 16. В восьмеричной системе употребляются восемь цифр: 0, 1, 2, 3, 4, 5, 6, 7.

Любое число в восьмеричной системе представляется последовательностью цифр:

в которой βi могут принимать значения от 0 до 7. Этой записи соответствует разложение числа x по степеням числа восемь с приведенными ниже коэффициентами:

Например, восьмеричное число:

В шестнадцатеричной системе для изображения чисел употребляется 16 цифр от 0 до 15. При этом, чтобы одну цифру не изображать двумя знаками, приходится вводить специальные обозначения для цифр, больших девяти. Обозначим первые десять цифр этой системы цифрами от 0 до 9, а старшие пять цифр - латинскими буквами: десять - А, одиннадцать - В, двенадцать - С, тринадцать - D, четырнадцать - Е, пятнадцать - F. Записи произвольного числа в шестнадцатеричной системе в виде последовательности цифр:

где γi может принимать любые из 16 значений от 0 до F (пятнадцать), соответствует разложение числа х по степеням числа 16 с указанными ниже коэффициентами:

Например, шестнадцатеричное число:

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

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

а шестнадцатеричное число 7В2,Е в двоичной системе запишется следующим образом:

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

Приведем примеры:

а) Перевод двоичного числа 1101111001, 1101 в восьмеричное:

б) Перевод двоичного числа 11111111011,100111 в шестнадцатеричное:

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

в виде трех (четырех) разрядного двоичного числа. Такие формы записи чисел носят название двоично-восьмеричной и двоично-шестнадцатеричной системы. Они называются также двоично-кодированными системами.

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

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

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

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

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

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

Двоичная арифметика

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

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

Переносы:

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

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

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

10111

10101

____________

10111

00000

+ 10111

00000

10111

________________________

111100011

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

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

Особенности выполнения деления двоичных чисел поясняются примером:

1100,011 : 10,01 = ?

1100011 10010

10010 101,1

____________________

11011

10010

______________

10010

10010

______________

00000

Благодаря простоте правил двоичного сложения, вычитания и умножения применение в ЦВМ двоичной системы счисления позволяет упростить схемы арифметических устройств.

Правила перевода

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

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

Обычно преобразования чисел из одной системы счисления в другую выполняются автоматически устройствами машины.

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

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

Пусть необходимо перевести число y, представленное в системе счисления с основанием s:

в h-систему, выполняя нужные для этого арифметические действия в новой h-системе. Для этого достаточно число представить в виде соответствующей суммы степеней s:

в которой основание s и все коэффициенты εi выражены в новой h-системе, и выполнить в h-системе все необходимые для вычисления этой суммы действия.

Пример 1. Перевести в десятичную систему шестнадцатеричное число у = (2Е5,А)16 . Для этого представляют у в виде:

Пример 2. Перевести в десятичную систему двоичное число z = (11011,101)2 :

Рассмотрим теперь перевод числа из s-системы в h-систему посредством арифметических операций исходной s-системы. В этом случае правила для перевода целых чисел и дробей различны.

Перевод целых чисел

Пусть целое число у, представленное в s-системе, требуется перевести в h-систему. Искомая запись числа у в h-системе имеет вид:

Разделив у на h, получим:

Отсюда

где у1 есть частное от деления числа у на основание системы h, а младшая цифра искомого представления числа у в h-системе есть остаток от этого деления.

Если теперь разделить у1 на h, то получим:

В силу

остаток от второго деления есть цифра σ2 следующего разряда в представлении числа у в h-системе и т.д. Таким образом, получаем правило: для перевода целого числа из s-системы счисления в h-систему нужно последовательно делить это число и получаемые частные на Основание h новой системы, представленное в старой s-системе, до тех пор, пока частное не станет меньше h. Старшей цифрой в записи числа в h-системе служит последнее частное, а следующие за ней цифры дают остатки, выписываемые s последовательности, обратной их получению.

Перевод дробных чисел

Перевод в h-систему правильной дроби z представленной в системе счисления с основанием s, означает запись этой дроби в виде:

Умножая z на h получаем:

где σ-1 и z1 соответственно целая и дробные части этого произведения. При этом целая часть σ-1 есть старшая цифра в представлении числа z в h-системе.

Если теперь умножить на h правильную дробь z1, то целая часть произведения дает следующую цифру σ-2 в представлении числа в h системе.

Следовательно, можно сформулировать правило: для перевода правильной дроби из s-системы в систему счисления с основанием h нужно умножить исходную дробь и дробные части получающихся произведений на основание h, представленное в старой s-системе. Целые части получающихся произведений дают последовательность цифр в представлении дроби в h-системе.

Обычно перевод дробей из одной системы в другую производят приближенно.

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

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

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

Для представления двоичных чисел в машине применяют прямой, обратный и дополнительный коды. Во всех этих кодах предусматривается дополнительный разряд для представления знака числа, причем знак «+» кодируется цифрой 0, а знак « — » - цифрой 1.

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

Прямой код (G)пр двоичного числа G = ± 0, γ1, γ2, … , γn (γi = 1 или 0) определяется условиями:

G при G ≥ 0

(G)пр =

(1 – G) при G ≤ 0

Положительное двоичное число с запятой, фиксированной перед старшим разрядом,

G+ = + 0, γ1, γ2, … , γn

в прямом коде представляется в виде:

(G+) пр = 0, γ1, γ2, … , γn (1)

Аналогично отрицательное двоичное число:

G- = - 0, γ1, γ2, … , γn (1a)

в прямом коде представляется в виде:

(G-) пр = 1, γ1, γ2, … , γn (2)

Способы представления чисел (1) и (2) называются прямым кодом соответственно положительных и отрицательных двоичных чисел.

Сложение и вычитание в прямом, обратном и дополнительном кодах

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

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

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

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

(G-) обр = 1, σ1, σ 2, … , σ n (3)

σi = 1 при γi = 0 и σi = 0 при γi = 1.

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

Отрицательное число G- = - 0, γ1, γ2,