Самокорректирующиеся коды

В предыдущей лекции рассмотрено алфавитное кодирование (т.е. каждой букве входного алфавита присваивался элементарный код B_i). Пусть { A₁,A₂ ,A₃,…A_s } – некоторое конечное подмножество попарно различных слов в алфавите I, имеющих одинаковую длину m. Такая ситуация может возникнуть, когда, например, выполнено предварительное алфавитное бинарное кодирование информации (сообщение состоит из цепочки 0 и 1). Если такую цепочку разбить, начиная с начала или конца, на участки одинаковой длины, кратные степени двойки (8, 16, 32 …), то вариантов таких участков будет конечное множество. Это дает возможность создать словарь { A₁,A₂ ,A₃,…A_s } (где s = 2^m) и передавать, запоминать не само сообщение, а последовательность ссылок на номера слов в словаре. Если предварительное кодирование осуществлялось бинарными элементарными кодами одинаковой длины, то такое кодирование в смысле уменьшения длины закодированного сообщения ничего не дает. Однако такой подход дает возможность строить коды, которые могут сами исправлять ошибки, возникающие от помех в линиях связи.

Очевидно, что каждое слово сообщения A допускает разложение вида A =A_i1,A_i2 ,A_i3,…A_in, и имеет единственное такое разложение. Если ограничиться предварительным бинарным кодированием, то A_i = a₁ a₂ a₃…..a_m номера слов в словаре, записанные в двоичной системе (a_i принимает значения 0 или1). Необходимо отметить, что каждый двоичный номер слова может быть однозначно записан и десятеричным числом.

Пусть S”(I) – подмножество всех слов, допускающих разложение указанного вида. Рассмотрим следующую схему кодирования:

A₁® B₁

A₂® B₂

A₃® B₃ (7.1)

….

A_s® B_s,

где B_i = b₁ b₂ b₃ …b_l – элементарные двоичные коды, имеющие одинаковую длину l = m + k, при этом такие, чтобы по коду, полученному на выходе канала связи (помеха может изменить 0 на 1 или наоборот, но не может добавить или убрать элемент b_i) однозначно восстановить код на входе канала и из него получить исходное сообщение.

Построение самокорректирующихся кодов было осуществлено Хеммингом. Рассмотрим случай, когда источник помех может внести не более одного инвертирования в элементарный код B_i (р =1). Вариантов получения элементарного кода B_i будет l +1 (правильный и l штук с инвертированием b_i на каждой позиции). Для того, чтобы дополнительных разрядов в коде B_i хватило для кодирования l +1 случаев, необходимо выполнение следующего условия:

2 ^m ≤ 2^l / (l + 1) (7.2)

Из этих соображений выбираем как наименьшее целое число, удовлетворяющее неравенству (7.2).

Дальнейшее построение будет состоять из трех этапов:

1. Построение кодов Хемминга (описание алгоритма кодирования).
2. Обнаружение ошибок в кодах Хемминга.
3. Декодирование.

Поиск по сайту: