При передаче информации в каналах связи возможно появление помех. Передаваемые сигналы могут искажаться. Чтобы обеспечить надежную передачу информации, применяют различные методы кодирования информации. Вместе с основной информацией пересылают некоторую дополнительную, позволяющую судить об искаженности принятых сообщений. Коды делятся на два больших класса: коды с обнаружением ошибок и коды с исправлением ошибок.
Пример.Код, обнаруживающий одиночные ошибки. Пусть сообщения, предназначенные для передачи, представляются двоичными векторами размерности 4. Произвольное сообщение α имеет вид α=(α1,α2,α3,α4)∈{0,1}4. Перед тем как сообщение α будет передано, его кодируют, добавляя бит проверки на четность:
E(α)=(α1,α2,α3,α4,α1⊕α2⊕α3⊕α4)∈{0,1}5.
По каналу связи пересылается сообщение E(α). В пересылаемом сообщение число единичных битов четно:
α1⊕α2⊕α3⊕α4⊕(α1⊕α2⊕α3⊕α4)=0.
Предположим, что при пересылке ошибка может произойти не более, чем в одном бите. Пусть β=(β1,β2,β3,β4,β5) – принятое сообщение. Тогда, если ошибка произошла, то β1⊕β2⊕β3⊕β4⊕β5=1, если нет – β1⊕β2⊕β3⊕β4⊕β5=0.
Пример.Код Хемминга, исправляющий одиночные ошибки. Сообщение α=(α1,α2,α3,α4) при кодировании дополняется тремя битами:
E(α)=(α1,α2,α3,α4,α5,α6,α7),
где
α5=α2⊕α3⊕α4;
α6=α1⊕α3⊕α4;
α7=α1⊕α2⊕α4.
Сообщение E(α)∈{0,1}7 передается по каналам связи. Пусть β=(β1,β2,β3,β4,β5,β6,β7) – принятое сообщение. Вычислим следующие суммы:
σ1=β4⊕β5⊕β6⊕β7;
σ2=β2⊕β3⊕β6⊕β7;
σ3=β1⊕β3⊕β5⊕β7.
Если сообщение передано без ошибки, то все три суммы нулевые. В самом деле, при безошибочной передаче βi=αi для i=1,2,…,7. Легко видеть, что после замены α5, α6, α7 их выражениями через α1, α2, α3 и α4, каждая из сумм σ1, σ2, σ3 содержит четное число слагаемых αi , i=1,2,3,4, и потому равна 0. Верно и обратное. Если все три суммы нулевые, сообщение передано без ошибки. В противном случае число j, 1≤j≤7, с двоичной записью σ1σ2σ3 указывает номер позиции, в которой произошла ошибка. Пусть, например, ошибка произошла в первой позиции. Тогда β1=1⊕α1 и βi=αi при i=2,3,…,7. Имеем
σ3 = 1⊕α1⊕α3⊕α5⊕α7 =
= 1⊕α1⊕α3⊕(α2⊕α3⊕α4)⊕( α1⊕α2⊕α4) = 1.
Так как в вычислении σ1 и σ2 ошибочный бит не участвует, то эти суммы равны 0. Значит, j=0012=1.
Для исправления ошибки в принятом сообщении β, нужно заменить βj на 1⊕βj и отбросить последние три бита. Первые четыре бита исправленного сообщения дают исходное сообщение α. Этот алгоритм реализует функцию декодирования α=D(β).
В общем случае (n,m)-блочный двоичный код определяется двумя функциями: функцией кодирования E:{0,1}n→{0,1}m и функцией декодирования D:{0,1}m→{0,1}n, где m≤n. Векторы вида E(α)∈{0,1}m называются кодовыми словами. Интуитивно ясно, что код тем лучше приспособлен к обнаружению и исправлению ошибок, чем больше различаются его кодовые слова.
Кодовым расстоянием блочного двоичного кода называется величина d(E), равная наименьшему расстояние между различными кодовыми словами:
d(E) = min{d(E(α),E(β)) | α, β∈{0,1}m , α≠β }.
Пример.Вычислим кодовое расстояние для (4,5)-кода с проверкой на четность. Имеется 16 кодовых слов:
00000; 00011; 00101; 00110;
01001; 01010; 01100; 01111;
10001; 10010; 10100; 10111;
11000; 11011; 11101; 11110.
Нетрудно проверить, что нет ни одной пары кодовых слов, для которых расстояние равнялось бы 1. В то же время имеются кодовые слова, расстояние между которыми равно 2. Следовательно, кодовое расстояние для рассматриваемого кода равно 2.
Пример.Найдем кодовое расстояние для рассмотренного ранее (4,7)-кода Хемминга. Имеется 16 кодовых слов (проверочные биты записаны через пробел):
0000 000; 0001 111; 0010 110; 0011 001;
0100 101; 0101 010; 0110 011; 0111 100;
1000 011; 1001 100; 1010 101; 1011 010;
1100 110; 1101 001; 1110 000; 1111 111.
Легко обнаружить кодовые слова, расстояние между которыми равно 3. Несколько сложнее проверяется, что кодовых слов, расстояние между которыми равно 2 или 1, нет. Значит, кодовое расстояние рассматриваемого кода равно 3.
Теорема.1) Код позволяет обнаруживать ошибки в k (или менее) позициях тогда и только тогда, когда его кодовое расстояние превышает k.
2) Код позволяет обнаруживать и исправлять ошибки в k (или менее) позициях тогда и только тогда, когда его кодовое расстояние превышает 2k.
Доказательство. Мы ограничимся доказательством второй части теоремы. Первая доказывается аналогично.
Необходимость. Предположим, что кодовое расстояние меньше, чем 2k. Тогда найдутся два слова α и γ такие, что d = d(E(α), E(γ)) ≤ 2k. В слове E(α)⊕E(γ) заменим часть единиц нулями: d/2 единиц, если d четно, и (d−1)/2 единиц, если d нечетно, и обозначим полученное так слово через δ. Заметим, что
w(δ)≤k и w(δ⊕E(α)⊕E(γ)) ≤ k.
Положим β=E(α)⊕δ. Тогда
d(E(α),β) = w(E(α)⊕E(α)⊕δ) = w(δ) ≤ k,
d(E(γ),β) = w(E(γ)⊕E(α)⊕δ) ≤ k.
Следовательно, слово β может появиться в результате ошибочной передачи (с числом ошибок, не превосходящим k) как слова α, так и слова β. Такую ошибку исправить невозможно.
Достаточность. Предположим, что при передаче слова E(α) ошибки произошли в r≤k битах и на выходе было получено слово β. Поскольку E(α)⊕β – вектор ошибок, то
d(E(α),β) = w(E(α)⊕β) = r.
Так как кодовое расстояние превышает 2k, то для произвольного кодового слова E(γ), отличного от E(α), имеем d(E(α),E(γ))>2k. Используя неравенство треугольника, получаем
d(E(α),β) + d(β,E(γ)) ≥ d(E(α),E(γ)) > 2k,
d(β,E(γ)) ≥ 2k − d(E(α),β) = 2k−r > k.
Следовательно, слово β может получиться при передаче слова E(γ) только в том случае, когда сделано более k ошибок. Это позволяет по слову β однозначным образом восстановить E(α) как ближайшее к нему кодовое слово, единственное, которое может привести к появлению слова β в результате не более, чем k ошибок.
