Для контроля хранения и передачи информации используются
Для контроля хранения и передачи информации используются специальные избыточные коды с обнаружением и контролем ошибок.
Способность кода обнаруживать или исправлять ошибки определяется т.н. минимальным кодовым расстоянием. Вообще говоря, кодовое расстояние - это то минимальное количество разрядов, на которое различаются два любых кода одинаковой разрядности. Для двоичных N-разрядных неизбыточных кодов кодовое расстояние - от D мин = 1 до N. В коде Грея =1.
Для избыточных кодов Dмин>1.
Если Dмин=2, то любые два кодовых слова отличаются по крайней мере двумя разрядами. Т.е. одиночная ошибка приведет к появлению недопустимого слова и может быть обнаружена. Если Dмин=3, то одиночная ошибка приведет к недопустимому слову, отличающемуся от правильного одним разрядом, а от любого другого на два разряда. Заменяя ошибочное слово на ближайшее к нему (по кодовому расстоянию), мы исправляем одиночную ошибку.
Код с проверкой четности.
Код с контролем по четности образуется добавлением одного контрольного разряда, дополняющего сумму единиц в слове до четного числа (или нечетного), и может обнаруживать нечетное число ошибок.
Код с исправлением одиночной ошибки
(код Хемминга).
Единичные ошибки в передаче информации исправляет код Хемминга.
Этот код состоит из собственно информационных разрядов и дополнительных разрядов, зависящих от информационной части.
Число контрольных разрядов надо выбирать таким образом, чтобы в них можно было записать в двоичном виде номер любого разряда как информационного, так и контрольного.
Пусть информационная часть занимает М разрядов, число контрольных разрядов - К. Тогда общее число разрядов N = М+К и должно соблюдаться соотношение:
2k-1>= N или 2k>= M + K + 1
Количество кодов в К - разрядном числе равно 2k. Из них не нулевых 2k-1 .
Каждый контрольный разряд есть признак четности группы разрядов. Т.е. таких групп К и необходимо производить К проверок.
В результате всех проверок тоже получим К - разрядный код, в котором правильным группам соответствуют нули, а ошибочным -единицы.
Максимальный номер ошибки в N-разрядном коде тоже N.
Количество кодов К-разрядном числе 2К, из них ненулевых 2К-1
Мы видим, что как код ошибки, так и номер ошибочного разряда является «К» разрядным числом. Чтобы ни совпадали необходимо выполнить два условия:
1) в качестве номеров контрольных разрядов следует выбирать такие номера, значение которых есть степень двойки.
2) группы разбить таким образом: чтобы двоичный номер разряда в группе содержал единицу в том разряде, который является контрольным для этой группы.
Рассмотрим пример.
Пусть число информационных разрядов равно 8-и. Если число контрольных разрядов выбрать К=3, то 23 = 8, а М+К+1= 8 +3 +1 =12 8 < 12, что мало. При К=4 24
= 16, а М+К+1= 8+4+1; 16 > 13; то есть 4-х разрядов достаточно. В качестве контрольных разрядов выбираем 1-й=20 ; 2-й = 21 ; 4-й = 22 ; 8-й = 23 .
N |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
К |
К4 |
К3 |
К2 |
К1 |
||||||||
М |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
1 = 0001; 3 = 0011; 5 = 0101; 7 = 0111; 9 = 1001; 11 = 1011
К1= [1] (+) [3] (+) [5] (+) [7] (+) [9] (+) [11]
к2 - контрольный разряд для разрядов
2 = 0010; 3 = 0011; 6 = 0110; 7 = 0111; 10 = 1010; 11 = 1011
к3 - контрольный разряд для разрядов
4 = 0100; 5 = 0101; 6 = 0110; 7 = 0111; 12 = 1100
к4 - контрольный разряд для разрядов
8 = 1000; 9 = 1001; 10 = 1010; 11 = 1011; 12 = 1100
Т.о., если ошибка была в 7-ом разряде, то
к1 = к2 = к3 = 1, к4 = 0;
если в 8-ом
к1 = к2 = к3 = 0; к4 = 1
Для исправления ошибки нужно изменить значение соответствующего разряда на противоположное.
Если же ошибка будет сразу в двух разрядах (1 и 2), то получим код 0011, который будет свидетельствовать о наличии ошибки в 3-м, что неверно.
Если объединить возможности кода контроля по четности с возможностями кода Хэмминга (добавив еще один разряд контроля по четности всех разрядов), получим код, который будет исправлять одну ошибку и обнаруживать две:
Контрольный разряд |
Разряд Чётности |
Результат |
Нули |
0 |
Ошибок нет |
Нули |
1 |
Ошибка разряда чётности |
Не нули |
0 |
Двойная ошибка |
Не нули |
1 |
Одиночная ошибка |
Для 16-разрядного кода число контрольных разрядов равно = 5.
2^5 >= 16 + 5 + 1; 32 > 21
Т.о. с ростом числа информационных разрядов доля контрольных разрядов сокращается.
4. Принципы функционирования компьютеров
