Компьютерная арифметика

Свойство взвешенности упрощает выполнение логических и арифметических операций. ДДК, получаемые друг из друга простой перестановкой весов (_i), образуют кодовую группу. Для обозначения конкретных ДДК и кодовых групп часто используют последовательность их весов, записанную в порядке их убывания, например, «8,4,2,1», «4,4,2,1» и т.п.

Упорядоченность ДДК состоит в выполнении одного из условий:

0₍₂₎<1₍₂₎<2₍₂₎<...<9₍₂₎. (6.2)

0₍₂₎>1₍₂₎>2₍₂₎>...>9₍₂₎. (6.3)

для двоичных представлений ( 0₍₂₎,1₍₂₎,2₍₂₎,...,9₍₂₎ ) десятичных цифр. Наличие упорядоченности ДДК необходимо для реализации логических операций.

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

Сущность свойства дополнительности («самодополняемость») ДДК заключается в следующем. Если сумма двух десятичных цифр равна (9), то переход от двоичного представления одной цифры к двоичному представлению другой цифры должен осуществляться путем инверсии двоичных разрядов.

Наличие этого свойства необходимо для упрощения алгебраических операций (операций с учетом знаков операндов) по правилам десятичной арифметики.

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

Особенностью взвешенных ДДК, имеющих только положительные веса, кроме ДДК группы «8,4,2,1», является отсутствие однозначного представления десятичных цифр. Это означает, что некоторые десятичные цифры могут быть записаны несколькими комбинациями двоичных цифр. Например, в ДДК «4,4,2,1» цифру 4 можно представить как 1000 и как 0100, цифру 5 - как 1001 и как 0101, цифру 6 - как 1010 и как 0110, цифру 7 - как 1011 и как 0111. Причиной этого служит неоднозначность решения уравнения (6.1) относительно переменных a_i (i=l,h).

Однозначность представления десятичных цифр, состоящая в том, что каждой такой цифре соответствует только одна из 16 двоичных тетрад, обеспечивается в ДДК группы «8,4,2,1».

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

Таблица 6.1 - Кодовые группы однозначных ДДК

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

Существует 86 кодовых групп безизбыточных ДДК, обладающих свойствами взвешенности и единственности. Среди них есть ДДК, отрицательными весами, например, «8,4,2,1», «8,4,2,-1», «6,3,-1,-1». Свойством дополнительности обладают все взвешенные ДДК с положительными весами, у которых сумма весов равна (9). Существуют четыре кодовых группы взвешенных ДДК, обладающих также и свойствами единственности и дополнительности, с именно: «5,2,1,1», «4,3,1,1», «4,2,2,1», «3,3,2,1». Среди взвешенных ДДК с отрицательными весами свойствами единственности и дополнительности обладают ДДК из 19 кодовых групп, перечисленных в табл. 6.2.

Таблица 6.2 - Кодовые группы ДДК с отрицательными весами, обладающие свойствами единственности, дополнительности и взвешенности

Упорядоченность присуща лишь ДДК, не имеющим отрицательных весов. Одновременно свойствами единственности, упорядоченности, дополнительности и взвешенности обладают ДДК кодовых групп «5,2,1,1», «4,3,1,1», «3,3,2,1»,»4,2,2,1». Всеми пятью свойствами обладают ДДК кодовой группы «4,2,2,1», называемые также кодами Эмери («2,4,2,1» - код Айкена).

Недостатком ДДК этой кодовой группы является искусственный порядок весов, что затрудняет выполнение арифметических операций.

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

Достоинством ДДК «8,4,2,1» следует считать простоту и удобство перевода чисел из десятичной системы счисления в двоично-десятичную и обратный перевод.

В каждом конкретном случае применение какого-либо ДДК обуславливается определенными его преимуществами по сравнению с другими типами ДДК. Например, код «7,4,2,1» применяется в электромеханических цифровых устройствах, где двоичной единице соответствует замкнутое состояние некоторой контактной пары и энергопотребляющее состояние соответствующей электрической цепи, а двоичному нулю - разомкнутое состояние контактной пары и не потребляющее энергии состояние электрической цепи. В этом случае каждое двоичное представление десятичной цифры содержит не более двух единиц, что обеспечивает минимальное и постоянное потребление энергии от источника питания. В ДДК «5,4,2,1», десятичные цифры можно рассматривать как двоично-пятеричные с кодированным представлением цифр. Три младших разряда в каждой тетраде изображают одну пятеричную цифру, с старшая цифра тетрады соответствует двоичному разряду. Этот ДДК имеет ряд достоинств при выполнении арифметических операций и переводе чисел из одной системы счисления в другую.

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

ДДК «8,4,2,1» и коды с избытком (полученные из кода «8,4,2,1» по аналогии с кодом «с избытком 3») обладают еще одним важным свойством, не входящим в перечень Рутисхаузера, а именно: свойством аддитивности. Это свойство состоит в том, что ДДК суммы двух десятичных цифр равен двоичной сумме ДДК этих цифр или отличается от нее на некоторую константу. Это свойство позволяет свести операции десятичной арифметики в таких ДДК к выполнению операций по правилам двоичной арифметики.

Примерами избыточных ДДК, где каждая десятичная цифра кодируется пятью двоичными разрядами, являются ДДК «3А+2» и «2 из 5». Первый из этих ДДК обладает свойством дополнительности, а двоичные представления десятичных цифр получают в нем путем записи в двоичной системе с естественным порядком весов числа ЗА+2, где А - заданная десятичная цифра.

В ДДК «2 из 5» каждая десятичная цифра изображается пятью двоичными разрядами, из которых только два содержат единицы. Можно считать, что ДДК «2 из 5» получается из ДДК «7,4,2,1» путем добавления справа дополнительного разряда с весом, равным нулю. В этот разряд записывают такую цифру, чтобы общее число единиц было равно двум (за исключением десятичного нуля). ДДК «3А+2» и «2 из 5» используют обычно для передачи информации, поскольку они позволяют обнаруживать одиночные ошибки, возникающие в процессе такой передачи, сравнительно простыми средствами.

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

ДДК - (w,x,y,z,) - обладает следующим свойством. Для десятичной цифры (А) в таком ДДК перестановка ее двоичных разрядов вида (z,w,x,y) равна младшему десятичному разряду (в двоичном представлении) произведения (А) на (3); перестановка вида (x,y,z,w) равна младшему разряду произведения (А) на (7); перестановка (y,z,w,x) равна младшему разряду произведения (А) на( 9).

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

6.1 Форматы числовых данных BCD - кодов

В современных компьютерных системах, обрабатывающих не только числовую информацию, но и текстовую (алфавитно-цифровую), отдельные символы чаще всего представляются словами длиной в один байт. Так как байт равен двум двоичным тетрадам, то в компьютерных системах с байтовым представлением информации можно записывать две десятичные цифры в один байт. Такую запись называют также упакованной записью или упакованным форматом записи десятичных цифр. Вместе с тем, можно записывать в один байт и по одной десятичной цифре, используя остальные четыре разряда для записи знаков и вспомогательных символов. Такую запись называют распакованной записью или распакованным форматом. В компьютерных системах широкого назначения обычно реализуются обе возможности записи десятичных цифр. Рассмотрим упакованный десятичный формат. Младшая цифра занимает в байте правую тетраду (биты 3-0), а старшая - левую (биты 7-4). Обе цифры представлены в коде «8,4,2,1». Многоразрядные упакованные десятичные числа занимают несколько байт. Для представления знака числа используют запрещенные кодовые комбинации: для «+» - C₍₁₆₎, для «-» - D₍₁₆₎. Код знака числа записывают в старшей тетраде старшего байта.

Распакованный формат называют символьным или ASCII - форматом.

Каждый байт содержит код, соответствующий десятичной цифре в кодовой таблице ASCII. В ней цифры имеют коды 30₍₁₆₎-39₍₁₆₎. Таким образом, значение десятичной цифры представлено в младшей тетраде, а старшая тетрада является кодом «зоны» (3). Поэтому такой формат также называют зонированным. Для обозначения знака используют коды символов «+» и «-» из кодовой таблицы ASCII (2B₍₁₆₎ 2D₍₁₆₎ соответственно).

6.2 Арифметические операции над числовыми данными BCD - кодов

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

- правила формирования десятичного переноса отличаются от правил формирования двоичного переноса;

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

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

1) суммируют двоичные представления десятичных цифр по правилам двоичной арифметики;

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

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

Рассмотрим, как можно определить корректирующую поправку и правильно сформировать перенос в старший десятичный разряд для ДДК «8,4,2,1». Для этого составим таблицу двоичных сумм, их представлений после первого этапа сложения, правильных их представлений в ДДК «8,4,2,1» десятичных переносов и корректирующих поправок (табл. 6.3).

Таблица 6.3 - Таблица двоичных сумм после первого этапа сложения

Из таблицы видно, что если результат, полученный на первом этапе, находится в пределах от 0 до 9, то корректировать его нет необходимости, а двоичный и десятичный перенос в этом случае совпадают. Если же результат первого этапа находится в пределах от 10 до 19, то для образования правильной суммы (pz₄z₃z₂z₁) к предварительной сумме (s₅s₄s₃s₂s₁) необходимо прибавить корректирующую поправку (00110). Признаком нахождения суммы первого этапа в диапазоне от 10 до 19 может служить наличие единичного значения переноса p. Таким образом, если при прибавлении коррекции перенос (р=0), то как правильную сумму необходимо взять результат первого этапа, если же (p=l), то как правильную сумму необходимо взять откорректированный результат.

При сложении или вычитании многоразрядных десятичных операндов описанные действия должны выполняться по каждому десятичному разряду (в ДДК «8,4,2,1» - по каждой тетраде двоичных разрядов).

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

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

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

- сдвиг в регистрах осуществляется одновременно на один десятичный разряд;

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

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

При умножении по этому алгоритму на один разряд множителя в среднем приходится 4,5 тактов суммирования (предполагаем, что цифры 0,1,...,9 появляются во всех разрядах множителя с равными вероятностями).

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

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

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

Размещено на Allbest.ru