Системы счисления дополнительный код. Дополнительный код (представление числа)

Для определения знака числа в двоичном коде используются 0 и 1. Нулем кодируется знак "+", Единицей кодируется знак "-".

Для представления положительных и отрицательных чисел в вычислительной технике используются ПРЯМОЙ, ОБРАТНЫЙ и ДОПОЛНИТЕЛЬНЫЙ коды.

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

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

1. Прямой код . В знаковый разряд помещается цифра 1, а в разряды цифровой части числа - двоичный код его абсолютной величины. Например:

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

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

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

Пример: Представить число +7, -12, -15, -16 в прямом, обратном и дополнительном кодах.

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

При переводе из дополнительного в прямой код происходит 1) инверсия цифр числа , 2)добавляется +1 в младший разряд инвертированного числа.

Арифметические действия над числами со знаком

В большинстве компьютеров операция вычитания не используется. Вместо нее производится сложение обратных или дополнительных кодов уменьшаемого и вычитаемого. Это позволяет существенно упростить конструкцию АЛУ.

Сложение обратных кодов . Здесь при сложении чисел А и В имеют место четыре основных и два особых случая:

Алгебраическое сложение

Если результат получен со знаком минус (с "1"), то результат необходимо преобразовать в прямой код!!!

1. А и В положительные. При суммировании складываются все разряды, включая разряд знака. Так как знаковые разряды положительных слагаемых равны нулю, разряд знака суммы тоже равен нулю. Например:

Получен правильный результат.

2. А положительное, B отрицательное и по абсолютной величине больше, чем А. |A| < |B|

Например:

Если результат получен со знаком минус с "1", то результат необходимо преобразовать в прямой код!!!

Получен правильный результат в обратном коде. При переводе в прямой код биты цифровой части результата инвертируются: 1 0000111 = -7 10 .

3. А положительное, B отрицательное и по абсолютной величине меньше, чем А. |A| > |B|

Например:

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

4. А и В отрицательные. Например:

Полученный первоначально неправильный результат (обратный код числа -11 10 вместо обратного кода числа -10 10) компьютер исправляет переносом единицы из знакового разряда в младший разряд суммы. При переводе результата в прямой код биты цифровой части числа инвертируются: 1 0001010 = -10 10 .

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

5. А и В положительные, сумма А+В больше, либо равна 2 n-1 , где n - количество разрядов формата чисел (для однобайтового формата n=8, 2 n-1 = 27 = 128). Вариант переполнения.

Например:

Семи разрядов цифровой части числового формата недостаточно для размещения восьмиразрядной суммы (162 10 = 10100010 2), поэтому старший разряд суммы оказывается в знаковом разряде. Это вызывает несовпадение знака суммы и знаков слагаемых , что является свидетельством переполнения разрядной сетки .

Представление целых чисел в компьютере.

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

Представление целых чисел в беззнаковых целых типах.

Для беззнакового представления все разряды ячейки отводятся под представление самого числа. Например, в байте (8 бит) можно представить беззнаковые числа от 0 до 255. Поэтому, если известно, что числовая величина является неотрицательной, то выгоднее рассматривать её как беззнаковую.

Представление целых чисел в знаковых целых типах.

Для представления со знаком самый старший (левый) бит отводится под знак числа, остальные разряды - под само число. Если число положительное, то в знаковый разряд помещается 0, если отрицательное - 1. Например, в байте можно представить знаковые числа от -128 до 127.

Прямой код числа.

Представление числа в привычной форме "знак"-"величина", при которой старший разряд ячейки отводится под знак, а остальные - под запись числа в двоичной системе, называется прямым кодом двоичного числа. Например, прямой код двоичных чисел 1001 и -1001 для 8-разрядной ячейки равен 00001001 и 10001001 соответственно.
Положительные числа в ЭВМ всегда представляются с помощью прямого кода. Прямой код числа полностью совпадает с записью самого числа в ячейке машины. Прямой код отрицательного числа отличается от прямого кода соответствующего положительного числа лишь содержимым знакового разряда. Но отрицательные целые числа не представляются в ЭВМ с помощью прямого кода, для их представления используется так называемый дополнительный код .

Дополнительный код числа.

Дополнительный код положительного числа равен прямому коду этого числа. Дополнительный код отрицательного числа m равен 2 k -|m|, где k - количество разрядов в ячейке.
Как уже было сказано, при представлении неотрицательных чисел в беззнаковом формате все разряды ячейки отводятся под само число. Например, запись числа 243=11110011 в одном байте при беззнаковом представлении будет выглядеть следующим образом:

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

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

Алгоритм получения дополнительного кода отрицательного числа.

Для получения дополнительного k-разрядного кода отрицательного числа необходимо

1. модуль отрицательного числа представить прямым кодом в k двоичных разрядах;

2. значение всех бит инвертировать:все нули заменить на единицы, а единицы на нули(таким образом, получается k-разрядный обратный код исходного числа);

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

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

В истории развития компьютеров использовались три основных варианта представления знаковых чисел:

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

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

Прямой код двоичного числа

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

Примеры прямого кода для правильных дробей:

Примеры прямого кода для целых чисел:

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

то есть значение, существенно отличающееся от ожидаемого.

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

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

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

Обратный код двоичного числа

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

Примеры обратного кода для правильных дробей:

.

Примеры обратного кода для целых чисел:

.

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

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

Дополнительный код двоичного числа

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

Для примера рассмотрим число X , которое в прямом коде имеет вид:

Тогда обратный код можно записать как

.

Для получения дополнительного кода прибавим 1 к младшему разряду обратного кода:

.

Примеры дополнительного кода для правильных дробей:

.

Примеры дополнительного кода для целых чисел:

.

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

В большинстве вычислительных машин отрицательные числа представлены в дополнительном коде.

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

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

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

Пример 1. Сложить числа и

При использовании обратного кода получим:

При использовании дополнительного кода получим:

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

Основная статья : Дизъюнктивная нормальная форма

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

правильная , если в неё каждая переменная входит не более одного раза (включая отрицание);

полная , если в неё каждая переменная (или её отрицание) входит ровно 1 раз;

монотонная , если она не содержит отрицаний переменных.

Например - является ДНФ.

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

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции отличной от тождественного нуля - даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора построить конъюнкцию , где . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации результатом является , что можно упростить до .

[Править]Конъюнктивная нормальная форма (кнф)

Основная статья : Конъюнктивная нормальная форма

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

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

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

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

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

16 Законы преобразования логических выражений: однопарных элементов, отрицания.

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

Для простоты записи приведем основные законы алгебры логики для двух логических переменных А и В. Эти законы распространяются и на другие логические переменные.

1. Закон противоречия:

2. Закон исключенного третьего:

3. Закон двойного отрицания:

4. Законы де Моргана:

5. Законы повторения: A & A = A; A v A = A; В & В = В; В v В = В.

6. Законы поглощения: A ∨ (A & B) = A; A & (A ∨ B) = A.

7. Законы исключения констант: A ∨ 1 = 1; A ∨ 0 = A; A & 1 = A; A & 0 = 0; B ∨ 1 = 1; B ∨ 0 = B; B & 1 = B; B & 0 = 0.

8. Законы склеивания:

9. Закон контрапозиции: (A ⇔ B) = (B ⇔ A).

Для логических переменных справедливы и общематематические законы. Для простоты записи приведем общематематические законы для трех логических переменных A, В и С:

1. Коммутативный закон: A & B = B & A; A ∨ B = B ∨ A.

2. Ассоциативный закон: A & (B & C) = (A & B) & C; A ∨ (B ∨ C) = (A ∨ B) ∨ C.

3. Дистрибутивный закон: A & (B ∨ C) = (A & B) ∨ (A & C).

Как уже отмечалось, с помощью законов алгебры логики можно производить равносильные преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого соглашения установлены следующие правила (приоритеты) для выполнения логических операций: первыми выполняются операции в скобках, затем в следующем порядке: инверсия (отрицание), конъюнкция (&), дизъюнкция (v), импликация (⇒), эквиваленция (⇔)

Выполним преобразование, например, логической функции

применив соответствующие законы алгебры логики.

17 Законы преобразования логических выражений: комбинационные законы.

Законы формальной логики

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

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

Закон тождества: в процессе определенного рассуждения всякое понятие и суждение должны быть тождественны самим себе.

Закон непротиворечия: невозможно, чтобы одно и то оке в одно то же время было и не было присуще одному и тому же в одном и том же отношении. То есть невозможно что-либо одновременно утверждать и отрицать.

Закон исключенного третьего: из двух противоречащих суждений одно истинно, другое ложно, а третьего не дано.

Закон достаточного основания: всякая истинная мысль должна быть достаточно обоснована.

Последний закон говорит о том, что доказательство чего-либо предполагает обоснование именно и только истинных мыслей. Ложные же мысли доказать нельзя. Есть хорошая латинская пословица: «Ошибаться свойственно всякому человеку, но настаивать на ошибке свойственно только глупцу». Формулы этого закона нет, так как он имеет только содержательный характер. В качестве аргументов для подтверждения истинной мысли могут быть использованы истинные суждения, фактический материал, статистические данные, законы науки, аксиомы, доказанные теоремы.

Законы алгебры высказываний

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

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

Законы алгебры высказываний (алгебры логики) - это тавтологии.

Иногда эти законы называются теоремами.

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

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

Закон тождества:

Всякое понятие и суждение тождественно самому себе.

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

Например, рассуждение Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык, значит, теперь смело могу идти в Киев неверно, так как первое и второе слова «язык» обозначают разные понятия.

В рассуждении: Движение вечно. Хождение в школу - движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое - в философском смысле - как атрибут материи, второе - в обыденном смысле - как действие по перемещению в пространстве), что приводит к ложному выводу.

Закон непротиворечия:

Не могут быть одновременно истинными суждение и его отрицание. То есть если высказывание А - истинно, то его отрицание не А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным.

18 Минимизация аналитической записи логических функций: метод карт Карно.

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

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

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

Двоичное 8-разрядное число со знаком в дополнительном коде может представлять любое целое в диапазоне от −128 до +127. Если старший разряд равен нулю, то наибольшее целое число, которое может быть записано в оставшихся 7 разрядах, равно 2 7 − 1 {\displaystyle 2^{7}-1} , что равно 127.

Дополнительный код для десятичных чисел

Тот же принцип можно использовать и в компьютерном представлении десятичных чисел: для каждого разряда цифра X заменяется на 9−X, и к получившемуся числу добавляется 1. Например, при использовании четырёхзначных чисел −0081 заменяется на 9919 (9919+0081=0000, пятый разряд выбрасывается).

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

Преобразование в дополнительный код

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

1. Если число, записанное в прямом коде, положительное, то к нему дописывается старший (знаковый) разряд, равный 0, и на этом преобразование заканчивается;
2. Если число, записанное в прямом коде, отрицательное, то все разряды числа инвертируются , а к результату прибавляется 1. К получившемуся числу дописывается старший (знаковый) разряд, равный 1.

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

обратный код :

Добавим к результату 1

Допишем слева знаковый единичный разряд

Для обратного преобразования используется тот же алгоритм. А именно:

Инвертируем все разряды числа, получая таким образом обратный код :

Добавим к результату 1

И проверим, сложив с дополнительным кодом

0101 + 1011 = 10000, пятый разряд выбрасывается.

p-адические числа

В системе p -адических чисел изменение знака числа осуществляется преобразованием числа в его дополнительный код. Например, если используется 5-ричная система счисления, то число, противоположное 1000... (1), равно 4444.... (−1).

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

Pascal

If a < 0 then a := ((not a ) or 128 ) + 1 ;

C/C++

Int convert (int a ) { if (a < 0 ) a = ( ~- a | 128 ) + 1 ; return a ; }

Преимущества и недостатки

Преимущества

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

Недостатки

• Представление отрицательного числа не читается по обычным правилам, для его восприятия нужен особый навык или вычисления
• В некоторых представлениях (например, двоично-десятичный код) или их составных частях (например, мантисса числа с плавающей запятой) дополнительное кодирование неудобно
• Модуль наибольшего числа не равен модулю наименьшего числа. Например, для восьмибитного целого со знаком, максимальное число: 127 10 = 01111111 2 , минимальное число: -128 10 = 10000000 2 . Соответственно, не для любого числа существует противоположное. Операция изменения знака может потребовать дополнительной проверки.