4.7. Коды с обнаружением и исправлением ошибок
Если кодовые комбинации составлены так, что отличаются друг от друга на кодовое расстояние d = 3, то они образуют корректирующий код, который позволяет по имеющейся в кодовой комбинации избыточности не только обнаруживать, но и исправлять ошибки.
4.7.1. Коды Хэмминга
Для построения кода Хэмминга используется информационная часть в виде двоичного кода на все сочетания с числом информационных символов k, к которой добавляют контрольные символы т. Таким образом, общая длина полной кодовой комбинации n =k + m.
Рассмотрим последовательность кодирования и декодирования по Хэммингу.
Кодирование кодом Хэмминга предусматривает выполнение следующих этапов.
1. Определение числа контрольных символов. Для этого можно воспользоваться следующими рассуждениями. При передаче по каналу с помехами при единичном искажении может быть искажен любой из п символов кода, всего будет n вариантов искажённых комбинаций. Код может быть передан и без искажений. Таким образом, при единичном искажении может быть n + 1 вариантов передачи, включая передачу без искажений. Используя контрольные символы, необходимо различить все п + 1 вариантов. С помощью контрольных символов m можно описать 2m событий. Значит, должно быть выполнено условие
2m ≥ n + 1=k + m + 1. (4.3)
В неравенстве (4.3) по известной величине k находится число контрольных разрядов m, необходимых для построения кода, способного обнаружить и исправить заданное число ошибок.
В табл. 4.13 представлена зависимость между k и т, полученная из неравенства (4.3).
Таблица 4.13
Число контрольных символов в зависимости от числа информационных разрядов для исправления одной ошибки
|
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
|
m |
2 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
5 |
Число искажённых кодовых комбинаций зависит от кратности искажения и в общем случае определяется по формуле
, (4.4)
где n – число разрядов полной кодовой комбинации,
l – кратность искажения.
Неравенство (4.3) в общем случае записывается в виде
2m ≥ Е+1, (4.5)
где величина Е определяется (4.4).
Формулы (4.4) и (4.5) позволяют определить число контрольных разрядов для искажений произвольной кратности.
2. Размещение контрольных символов. Для удобства обнаружения искаженного символа целесообразно размещать их на местах, кратных степени 2, т.е. на позициях 1, 2, 4, 8 и т.д. Информационные символы располагаются на оставшихся местах. Поэтому, например, для семиэлементной полной кодовой комбинации можно записать
m1, m2, k4, m3, k3, k2, k1, (4.6)
где k4 – старший (четвертый) разряд информационной кодовой комбинации двоичного кода, подлежащий кодированию; k1 – младший (первый) разряд.
3. Определение состава контрольных символов. Какой из символов должен стоять на контрольной позиции (1 или 0), выявляют с помощью проверочной таблицы. Рассмотрим это на примере комбинации (4.6).
Вначале составляется предварительная таблица (табл. 4.14), в которой записаны все кодовые комбинации (исключая нулевую) для трехразрядного двоичного кода на все сочетания и в правом столбце сверху вниз проставлены символы комбинации кода Хэмминга, записанные в последовательности (4.6).
Таблица 4.14