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

Проблема надёжной передачи данных по каналам связи - одна из основных проблем информатики. Любой процесс передачи данных (сигналов) описывается общей схемой, см. рис.1 на стр. 14. При передаче по каналам связи сигналы подвергаются искажениям, в связи с чем ставится задача обнаружения и исправления ошибок, возникших при передаче. Одним из важнейших разделов теории информации, в рамках которого решаются указанные проблемы, является теория кодирования, основы которой были заложены Ричардом Хэммингом (1915-1998). Не менее важный вклад в теорию кодирования сделал К. Шеннон. Ещё в годы Второй мировой войны он работал в шифровальном отделе и занимался проблемами надёжной передачи данных и выделения нужной информации из зашифрованного текста.

Постановка задачи надёжной передачи сообщений состоит в следующем. Пусть по каналу связи требуется передавать слова в некотором алфавите А. На вход канала подаётся слово a, а на выходе принимается искажённое слово w. Требуется по слову w восстановить слово a.

Основная идея решения этой задачи состоит в том, что вместо слова a передаётся его код: слово b = K(a). Здесь через K(a) обозначена функция преобразования слова a в его код b. Преобразование K(a) называется кодированием. Очевидно, должно существовать и обратное преобразование a = K^-1(b), которое называется декодированием.

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

1) коды с обнаружением ошибок;

2) коды с исправлением ошибок.

Приведём пример простого кода с обнаружением одиночной ошибки. Рассмотрим сообщение a длины m над алфавитом B={0,1}:

a = a₁ a₂ a₃... a_m, где a_iÎB.

Код слова a:

b=K(a)=b₁ b₂ b₃... b_m b_m+1, где b_i = a_i, для i=1,2,…m;

последний символ b_m+1 равен сумме всех предыдущих по mod 2. Последнее означает, что b_m+1 = 0, если сумма предыдущих символов чётная, и b_m+1 = 1, если сумма предыдущих символов нечётная, так как для любого натурального k значение функции k mod 2 = 0 (для чётных k); либо =1 (для нечётных k)[5].

Значение символа b_m+1, вычисленное по данному правилу, называется контрольной суммой. Теперь для обнаружения ошибки в принятом слове длины m+1 надо вычислить контрольную сумму и сравнить её со значением b_m+1: если совпадения нет, то при передаче была допущена ошибка, в противном случае считается, что процесс передачи кодового слова b прошёл без ошибки. Ясно, что такое кодирование позволяет обнаружить в процессе передачи только нечётное число ошибок. Пусть надо передать слово a = 110011, (m=6), тогда b = 1100110 (контрольная сумма = 0). Если после передачи вместо кода b будет получено слово 1000110, то будет обнаружено наличие ошибки. Если будет получено, например, слово 0011110, то ошибка обнаружена не будет.

Рассмотрим пример кодирования с исправлением ошибки. Пусть требуется передать сообщение a. Будем кодировать сообщение a по правилу b=K(a) заменяя в a каждый символ его n-кратным повторением. После приёма кода b нужно выделить в полученном слове блоки, содержащие по n символов. Если в каком-либо блоке все символы одинаковые, то этот блок не содержит ошибок. Если есть различия – блок содержит ошибку, которую можно исправить методом голосования: заменить все символы на тот, который встречается в чаще остальных – он и считается правильным.

Пример 1. Пусть требуется передать слово a = 01011; выберем кратность повторения n = 3; тогда кодовое слово для передачи имеет вид b = 000 111 000 111 111; пусть в результате передачи по каналам связи получено слово c=010011000110101; разобьём его на блоки по три символа: с = 010 011 000 110 101 и исправим ошибки методом голосования: получим d = 000 111 000 111 111, т.е. получили слово b, от которого можно перейти к требуемому слову a.

Возникает вопрос, при каких условиях некоторый способ кодирования позволяет обнаружить ошибку, и когда может её исправить? Над решением этой проблемы работал Р. Хемминг. Он сформулировал ее решение в 1950 в своей единственной научной статье, посвящённой кодам для коррекции ошибок. Статья содержала конструкцию блочного кода, корректирующего одиночные ошибки, которые возникают при передаче сообщений. Следует отметить, что коды, способные корректировать ошибки при обработке сигналов, были предложены Хэммингом ещё до 1948, когда была опубликована знаменитая статья К. Шеннона «Математическая теория связи».

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

Определение. Пусть x и у – двоичные слова длины m в алфавите B={0,1}. Введем расстояние Хемминга d между x и y следующим образом: d(x,y) равно числу несовпадений в соответствующих позициях слов x и y.

Пример 2. Пусть x = 110101, y = 011001, z = 000110 à d(x,y) = 3, d(y,z) = 5, d(x,z) = 4.

Введённая функция удовлетворяет всем аксиомам расстояния:

1. d(x,y) ³ 0, причём d(x,y) = 0 только при x = y;

2. d(x,y) = d(y,x);

3. d(x,z) £ d(x,y) + d(y,z) – неравенство треугольника.