Выполнение операций сложения и вычитания в Д-кодах

 

Операции сложения и вычитания в Д-кодах выполняются над операндами по формальным правилам десятичной арифметики, описанным ранее:

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

2. Сложение отрицательных чисел выполняется аналогично сложению положительных с той лишь разницей, что результату присваивается отрицательный знак.

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

Рассмотрим пример когда одно число отрицательное, а другое положительное:

1) Сложить два числа в коде Д1 A = -1000 0010 0101, B = 1001 0100 0110.

[A]l = 1. 0001 0111 0101

[B] = 0. 1001 0100 0110

1. 1010 1011 1011

+ 0110 0110 0110 поправки

[C] = 0. 0001 0010 0001

 

Умножение чисел в Д-кодах

 

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

Рассмотрим пример умножения двух чисел, представленных в коде Д1:

умножим X = 2510 = 0010 0101 на Y = 1210 = 0001 0010, частные произведения формируем в P. Анализ тетрад Y начинаем с младшей.

 

0010 0101 x 0001 0010 = 0011 0000 0000 = 30010

P 0000 0000 0000

+ X 0010 0101 0010 - 0001 = 0001 > 0, значит надо еще раз X + P

P 0000 0010 0101

+ X 0010 0101 0010 - 0001 = 0, конец анализа младшей тетрады.

P 0000 0100 1010

+ 0110 поправка

P 0000 0101 0000 сдвигаем X на 4 разряда влево и складываем с P, анализируя старшую тетраду Y.

 

P 0000 0101 0000

+ X 0010 0101 0000 0001 - 0001 = 0

P 0010 1010 0000

+ 0110 поправка

P 0011 0000 00002 = 30010 ответ.

 

Деление чисел в Д-кодах

 

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

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

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

X = 48 = 0100 1000, Y = 2 = 0000 0010, X:Y = 24 = 0010 0100, в С1 - формируем старшую тетраду частного, а в С2 - младшую.

0100 1000: 0010

- 0010

0010 > 0 С1 = С1 + 1 = 1

- 0010

0000 С1 = 1 + 1 = 2 = 0010

-0010

+ 0010

0000 сдвигаем Y на 4 разряда (1 тетраду) вправо и выполняем те же действия:

0100 1000

- 0010

0110 >0 С2 = С2 + 1 = 1

- 0010

0100 > 0 С2 = 1 + 1 = 2

- 0010

0010 > 0 С2 = 2 + 1 = 3

- 0010

0000 С2 = 3 + 1 = 4 = 0100

 

Ответ С1 + С2 = 0010 0000 + 0000 0100 = 0010 0100 = 2410

 

Перевод чисел из Д-кода в двоичный и из двоичного в Д-код

 

Пусть задано 4-х разрядное число в коде Д1 A = a4a3a2a1, каждая десятичная цифра которого должна быть представлена в виде

ai = {4 3 2 1 }i. В данном случае i = 1, 2, 3, 4. Как нам уже известно, изображение числа А можно представить в следующем виде:

 

A = a4103+ a3102+ a2101+ a1100,

 

Как видно из этой формулы, при переводе из кода Д1в двоичный код каждый i -тый разряд кода Д1 надо умножать на 10I-1, т.е.

a11, a210, a3100, a41000.

В то же время 10 = 8 + 2 = 23+ 21, значит

a1= {4 3 2 1 }1

a2 = {4 3 2 1 }2 (23+ 21)

a3= {4 3 2 1 }3 (23+ 21) (23 + 21)

a4= {4 3 2 1 }4 (23+ 21) (23 + 21) (23 + 21)

 

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

Например, переведем 2510= 0010 0101 в двоичную систему счисления. Вторую тетраду (0010) сдвигаем на 3 разряда влево, получаем 0001 0000. Эту же тетраду сдвигаем на 1 разряд влево и складываем с полученной:

 

0001 0000

+0000 0100

0001 0100

+0000 0101 (первая тетрада)

0001 1001 = 2510

 

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

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

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

Например, 1100012 = 4910 переведем в код Д1.

 

 

1) Сдвиг 1 10001

2) Сдвиг 1 1 0001

3) Сдвиг 1 1 0 001

4) Сдвиг и коррекция +0110 1 0 1 1 0 1 0 0 01

Рез.-т после корр. 1 0 0 1 0 01

5) Сдвиг 1 0 0 1 0 0 1

6) Сдвиг 1 0 0 1 0 0 1

 

Ответ 0100 1001D = 4910.

 

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

 

 

Глава 6

 

КОНТРОЛЬ РАБОТЫ ЦИФРОВОГО АВТОМАТА

Основные понятия теории кодирования

 

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

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

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

 

Кодирование по методу четности-нечетности

 

Если в математическом коде выделен один контрольный разряд (k=1), то к каждому двоичному числу добавляется один избыточный разряд и в него записывается 1 или 0 с таким условием, чтобы сумма цифр в каждом числе была по модулю 2 равна 0 для случая четности или 1 для случая нечетности. Появление ошибки в кодировании обнаружится по нарушению четности (нечетности). При таком кодировании допускается, что может возникнуть только одна ошибка. Пример реализации метода четности представлен в таблице 6.1.

 

Т а б л и ц а 6.1.

Число Контрольный разряд Проверка

10101011 1 0

11001010 0 0

10010001 1 0

11001011 0 1 - нарушение

 

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

 

a1 a2 a3 a4 a5 k1

a6 a7 a8 a9 a10 k2

a11 a12 a13 a14 a15 k3

a16 a17 a18 a19 a20 k4

a21 a22 a23 a24 a25 k5

k6 k7 k8 k9 k10

 

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

Например:

1001110 0

1110101 0

0101101 0

1010110 0

1101011 1

 

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

 

Коды Хеминга

 

Коды, предложенные американским ученым Р.Хемингом, позволяют не только обнаружить но и исправить одиночные ошибки. Эти коды - систематические. Хеминг впервые ввел понятие кодового расстояния.

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

Минимальным кодовым расстоянием (dmin) данного кода называется минимальное расстояние между двумя любыми словами в этом коде. Если длина слова n, то кодовое расстояние может принимать значение от 1 до n. Если имеется хоть одна пара слов, отличающихся в одном разряде, то минимальное кодовое расстояние равно 1. Для систематических кодов

d min > 1. В общем случае, чтобы код позволял обнаруживать ошибки кратностью r, должно выполняться условие:

 

d min r + 1.

 

Допустим к n 0 информационным разрядам в коде Хеминга добавляется k контрольных разряда для автоматического определения местоположения ошибочного разряда. Общее количество символов n = n 0 + k. Производится k проверок на четность (по количеству контрольных разрядов) и записывается k -разрядное двоичное число, которое определяет номер позиции кода с ошибкой. Если n - общее количество разрядов, то

 

n +1 = n 0 + k + 1 2k отсюда n 0 2k- k - 1.

 

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

Информационные и контрольные разряды необходимо размещать на определенных местах для нахождения ошибок. Обычно контрольные разряды принято размещать на позициях кода 20, 21, 22,... (1, 2, 4, 8, 16...), у которых в записи есть только одна 1 (для удобства). При этом нумерация позиций идет слева направо. А нумерация позиций для записи информационных разрядов идет справа налево. Рассмотрим пример перевода двоичного кода числа в код Хеминга. Пусть надо передать информацию, для которой выделено 3 контрольных разряда, т.е. k = 3, тогда n 0= 4, т.е. для представления числа нам отводится 4 разряда. В итоге передается 7-разрядный код. Через И обозначим информационные разряды, а через К - контрольные.

 

1 2 3 4 5 6 7

К1 К2 И4 К3 И3 И2 И1

0 0 0 0 1 1 0

 

т.е. передается 01102 = 610. Для проверки на четность складываем позиции 1, 3, 5, 7 (отсчет идет слева направо), т.е. порядковые номера которых имеют 1 в младшем разряде (в двоичном представлении). Получаем: 0 + 0 + 1 + 0 = 1, сумма равна 1, значит в К1 записываем 1 (для четности). Далее аналогично складываем позиции 2, 3, 6, 7 (порядковые номера содержат 1 во втором разряде), получаем: 0 + 0 + 1 + 0 = 1, значит в К2 записываем тоже 1. И наконец складываем позиции 4, 5, 6, 7 (порядковые номера содержат 1 в третьем разряде), получаем: 0 + 1 + 1 + 0 = 0, в К3 записывается 0. Таким образом мы получили следующий код:

 

1 2 3 4 5 6 7

К1 К2 И4 К3 И3 И2 И1

1 1 0 0 1 1 0

 

Это и есть 6 в коде Хеминга. Надо отметить, что общее количество 1 в коде должно быть четным.

Теперь рассмотрим пример корректировки полученного кодированного в коде Хеминга числа, в котором есть сбой: число 0111000. Надо определить позицию, в которой произошел сбой. Для этого суммируем позиции 1, 3, 5, 7, получаем: К1 = 0 + 1 + 0 + 0 = 1. Далее суммируем позиции 2, 3, 6, 7, получаем: К2 = 1 + 1 + 0 + 0 = 0. И наконец суммируем позиции 4, 5, 6, 7, получим К3 = 1 + 0 + 0 + 0 = 1. Контрольный код равен 1012 = 510, значит ошибка на 5-й позиции кода, т.е 01111002 = 1210.

Существует модифицированный код Хеминга, в котором добавляется еще один разряд общей четности. Такой код позволяет обнаруживать и устранять двойные ошибки. Например, записываем число 1011010, а считываем со сбоем: 1 1 110 0 0. Надо проинвертировать считанное число, послать его и снова считать (опять с таким же сбоем): А = 1 1 110 0 0 = А = 0000111, посылаем и читаем В = 0 1 001 0 1, складываем А и В, получаем: С = 0 1 000 1 0, в котором единицы показывают в каких разрядах произошел сбой.

 

Контроль по модулю

 

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

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

Например: определить контрольный код чисел А = 125 и В = 89 по модулю 11. 1) 125: 11 = 12 (4), т.е. контрольный код равен 4. 2) 89: 11 = 8 (1), т.е. контрольный код равен 1.

При цифровом методе контроля контрольный код числа образуется делением суммы цифр числа на выбранный модуль. В данном варианте возможны два пути получения контрольного кода: 1) непосредственное деление суммы цифр на модуль; 2) просто суммирование цифр по выбранному модулю.

Например: определить контрольный код для чисел 153 и 41 по модулю 3. Сумма цифр 153 равна 9, а сумма цифр 41 равна 5. Разделив эти суммы на 3 получим соответственно контрольные коды 0 и 2.