4. Модифицированные коды.

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

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

положительное число

0

0

РП Знак числа

отрицательное число

1

1

а)

0

1

положительное число

РП Знак числа

0

1

отрицательное число

б)

Рис. 2.11. Представление чисел в модифицированном коде: а) числа перед выполнением операции сложения; б) результат выполнения операции сложения двух положительных либо двух отрицательных чисел при наличии переполнения

5. Код с исправлением ошибок

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

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

1. Коды Хемминга

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

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

Коды Хемминга обладают большей относительной избыточностью, чем коды с проверкой на четность, и предназначены либо для исправления одиночных ошибок (при d ⁵=3), либо для исправления одиночных и обнаружения без исправления двойных ошибок (d=4). В таком коде n – значное число имеет m информационных и k контрольных разрядов (длина слова n = m + k). Каждый из контрольных разрядов является знаком четности для определенной группы информационных знаков слова. При декодировании производится k групповых проверок на четность. В результате каждой проверки в соответствующий разряд записывается 0, если проверка была успешной, или 1, если была обнаружена нечетность.

Группы проверки образуются таким образом, что в регистре ошибки после окончания проверки получается k – разрядное двоичное число, указывающее номер позиции ошибочного двоичного разряда. Изменение значения этого разряда (0 на 1 или 1на 0) исправляет ошибку.

Для любых двух кодированных слов, например 10001001 и 10110001, можно определить, сколько соответствующих битов в них различается. Используя логическую операцию исключающее ИЛИ (xor), сосчитаем число битов со значением 1 в полученном результате ( 10001001 xor 10110001=01000110 ). В данном примере таких бита 3. Число битовых позиций, по которым различаются два слова, называются интервалом Хэмминга. Если интервал Хэмминга для двух слов равен d, это означает, что достаточно d битовых ошибок, чтобы превратить одно слово в другое.

Память состоит из m - битных слов, существует 2^m вариантов сочетания битов. Кодированные слова состоят из n битов, но из-за способа подсчета контрольных разрядов допустимы только 2^m из 2ⁿ кодированных слов. Если в памяти обнаруживается недопустимое кодированное слово, то компьютер знает, что произошла ошибка. При наличии алгоритма для подсчета контрольных разрядов можно составить полный список допустимых кодированных слов и из этого списка найти два слова, для которых интервал Хэмминга будет минимальным. Это интервал Хэмминга полного кода.

Свойства проверки и исправления ошибок определенного кода зависят от его интервала Хэмминга. Чтобы обнаружить d ошибок в слове, необходим код с интервалом d+1, поскольку d ошибок не могут изменить одно допустимое кодированное слово на другое допустимое кодированное слово. Соответственно, чтобы исправить d ошибок в битах, необходим код с интервалом 2d+1, поскольку в этом случае допустимые кодированные слова настолько отличаются друг от друга, что даже если произойдет d ошибок, изначальное кодированное слово будет ближе к ошибочному, чем любое другое кодированное слово, поэтому его можно будет определить.

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

Для контроля выполнения операций в компьютере код Хэмминга непригоден, так как он основан на определении изменения исходного кода. При выполнении же арифметических и логических операций (АЛО) код изменяется всегда.

Известно много кодов для контроля выполнения АЛО. Например, код «2 из 5» (2 единицы и 3 нуля) или «2 из 7» (2 единицы и 5 нулей). Однако эти коды имеют большую избыточность, требуют сложной схемы реализации.

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

Кодирование чисел состоит в определении C(N_i), а для обнаружения ошибок АЛО вместо декодирования выполняется операция сравнения C(N₃) и C(N1)C(N₂), где - знак выполняемой операции. Совпадение результатов является признаком отсутствия ошибки при выполнении АЛО. Принцип раздельного контроля по модулю может быть представлен схемой, приведенной на рис. 2.12.

N₁

_N2

Основная

сумма

Определение вычета

C(N₃)

C(N₁)

C(N₂)

Сигнал

ошибки

C(N₁)+C(N₂)

Контрольная

сумма

Устройство сравнения

Рис. 2.12. Контроль по модулю

Модуль с минимальным кодовым расстоянием d=2 используют для обнаружения одиночных и некоторых кратных ошибок. Чаще выбирают P равный B-1, где B – основание системы счисления, что позволяет упростить определение вычетов.