Блочные двоичные коды

При передаче информации в каналах связи возможно появление помех. Передаваемые сигналы могут искажаться. Чтобы обеспечить надежную передачу информации, применяют различные методы кодирования информации. Вместе с основной информацией пересылают некоторую дополнительную, позволяющую судить об искаженности принятых сообщений. Коды делятся на два больших класса: коды с обнаружением ошибок и коды с исправлением ошибок.

Пример. Код, обнаруживающий одиночные ошибки. Пусть сообщения, предназначенные для передачи, представляются двоичными векторами размерности 4. Произвольное сообщение α имеет вид α=(α₁,α₂,α₃,α₄)∈{0,1}⁴. Перед тем как сообщение α будет передано, его кодируют, добавляя бит проверки на четность:

E(α)=(α₁,α₂,α₃,α₄,α₁⊕α₂⊕α₃⊕α₄)∈{0,1}⁵.

По каналу связи пересылается сообщение E(α). В пересылаемом сообщение число единичных битов четно:

α₁⊕α₂⊕α₃⊕α₄⊕(α₁⊕α₂⊕α₃⊕α₄)=0.

Предположим, что при пересылке ошибка может произойти не более, чем в одном бите. Пусть β=(β₁,β₂,β₃,β₄,β₅) – принятое сообщение. Тогда, если ошибка произошла, то β₁⊕β₂⊕β₃⊕β₄⊕β₅=1, если нет – β₁⊕β₂⊕β₃⊕β₄⊕β₅=0.􀀀

Пример. Код Хемминга, исправляющий одиночные ошибки. Сообщение α=(α₁,α₂,α₃,α₄) при кодировании дополняется тремя битами:

E(α)=(α₁,α₂,α₃,α₄,α₅,α₆,α₇),

где

α₅=α₂⊕α₃⊕α₄;

α₆=α₁⊕α₃⊕α₄;

α₇=α₁⊕α₂⊕α₄.

Сообщение E(α)∈{0,1}⁷ передается по каналам связи. Пусть β=(β₁,β₂,β₃,β₄,β₅,β₆,β₇) – принятое сообщение. Вычислим следующие суммы:

σ₁=β₄⊕β₅⊕β₆⊕β₇;

σ₂=β₂⊕β₃⊕β₆⊕β₇;

σ₃=β₁⊕β₃⊕β₅⊕β₇.

Если сообщение передано без ошибки, то все три суммы нулевые. В самом деле, при безошибочной передаче β_i=α_i для i=1,2,…,7. Легко видеть, что после замены α₅, α₆, α₇ их выражениями через α₁, α₂, α₃ и α₄, каждая из сумм σ₁, σ₂, σ₃ содержит четное число слагаемых α_i , i=1,2,3,4, и потому равна 0. Верно и обратное. Если все три суммы нулевые, сообщение передано без ошибки. В противном случае число j, 1≤j≤7, с двоичной записью σ₁σ₂σ₃ указывает номер позиции, в которой произошла ошибка. Пусть, например, ошибка произошла в первой позиции. Тогда β₁=1⊕α₁ и β_i=α_i при i=2,3,…,7. Имеем

σ₃ = 1⊕α₁⊕α₃⊕α₅⊕α₇ =

= 1⊕α₁⊕α₃⊕(α₂⊕α₃⊕α₄)⊕(α₁⊕α₂⊕α₄) = 1.

Так как в вычислении σ₁ и σ₂ ошибочный бит не участвует, то эти суммы равны 0. Значит, j=001₂=1.

Для исправления ошибки в принятом сообщении β, нужно заменить β_j на 1⊕β_j и отбросить последние три бита. Первые четыре бита исправленного сообщения дают исходное сообщение α. Этот алгоритм реализует функцию декодирования α=D(β).􀀀

В общем случае (n,m)-блочный двоичный код определяется двумя функциями: функцией кодирования E:{0,1}ⁿ→{0,1}^m и функцией декодирования D:{0,1}^m→{0,1}ⁿ, где 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 ошибок.􀀀

Коды Хемминга

Начнем с нескольких определений и конструкций общего характера.

Если функция кодирования блочного кода E:{0,1}ⁿ→{0,1}^m линейна, то код называется линейным. В дальнейшем мы рассматриваем только линейные коды. Назовем проверочным такое линейное отображение S:{0,1}^m→{0,1}^k, что S(β)=0 тогда и только тогда, когда β является кодовым словом. Для произвольного β∈{0,1}^m вектор S(β) называется синдромом. Нулевой синдром имеют кодовые слова, и только они.

Предположим, что в зашумленном канале передаваемое кодовое слово E(α) исказилось, к нему добавился вектор ошибок δ, так что на выходе принято слово β=δ⊕E(α). Тогда

S(β)=S(δ⊕E(α))=S(δ)⊕S(E(α))=S(δ).

Для того чтобы правильно декодировать передаваемое сообщение, нужно уметь определять вектор ошибок по его синдрому. Если вектор ошибок определен, то исправить их несложно: E(α)=δ⊕β. Ограничившись случаем одиночных ошибок, можно привести сравнительно несложное построение кода, исправляющего ошибки.

Вектор одиночной ошибки имеет всего одну ненулевую координату, то есть является одним из векторов канонического базиса пространства {0,1}^m. Линейный код позволяет исправлять все одиночные ошибки тогда и только тогда, когда синдромы всех векторов из канонического базиса пространства {0,1}^m отличны от нуля и друг от друга. Поскольку пространство {0,1}^k содержит всего 2^k−1 ненулевых векторов, используя проверочное отображение S:{0,1}^m→{0,1}^k, можно исправлять одиночные ошибки лишь в том случае, когда длины кодовых слов ограничены числом 2^k−1, то есть m≤2^k−1. Оказывается, что можно построить коды с исправлением ошибок, в которых m=2^k−1. В таких кодах их «исправляющие» возможности используются с максимальной эффективностью. К их числу относятся рассматриваемые ниже коды Хемминга.

Перейдем к описанию кода Хемминга. Пусть m=2^k−1. Среди m позиций кодового слова k позиций являются контрольными, а n = 2^k−k–1 – информационными. Матрица H (размерности k×(2^k−1)), задающая проверочное отображение, содержит в качестве столбцов все ненулевые векторы пространства {0,1}^k. Порядок столбцов не важен, но технически удобнее считать, что в каждом столбце записан его номер в двоичном формате. Строки матрицы H определяют коэффициенты системы из k однородных линейных уравнений c 2^k−1 неизвестными. Множество кодовых слов совпадает с множеством решений этой системы. Выражая последние k неизвестных через первые 2^k−k–1, мы получаем уравнения для вычисления контрольных битов. Вектор с нулевым синдромом является кодовым и его декодирование сводится просто к отбрасыванию контрольных битов. Если синдром отличен от нуля, он представляет собой двоичную запись номера позиции, в которой произошла ошибка. В этом случае при декодировании ошибка исправляется. Доля информационных позиций в коде Хемминга составляет

1211212−−=−−−kkkkk

и стремится к 1 с ростом k.

Пример. Рассмотрим случай k=3, m=7, n=4. Проверочное отображение S задается следующей матрицей:

=101010111001101111000H.

Столбцы матрицы представляют собой образы векторов канонического базиса пространства {0,1}⁷ относительно S. Для произвольного вектора β=(β₁,β₂,β₃,β₄,β₅,β₆,β₇) синдром S(β)=(σ₁,σ₂,σ₃) определяется уравнениями

σ₁=β₄⊕β₅⊕β₆⊕β₇;

σ₂=β₂⊕β₃⊕β₆⊕β₇;

σ₃=β₁⊕β₃⊕β₅⊕β₇.

Кодовое слово S(α)=(α₁,α₂,α₃,α₄,α₅,α₆,α₇) должно удовлетворять системе уравнений

α₄⊕α₅⊕α₆⊕α₇=0;

α₂⊕α₃⊕α₆⊕α₇=0;

α₁⊕α₃⊕α₅⊕α₇=0.

Решив эту систему относительно α₅, α₆, α₇, можно найти уравнения, задающие контрольные биты. Сложив первые два уравнения, получаем

α₂⊕α₃⊕α₄⊕α₅=0,

откуда

α₅=α₂⊕α₃⊕α₄.

Подставив выражение для α₅ в третье уравнение системы, получаем

α₇=α₁⊕α₂⊕α₄.

Теперь подставляем выражение для α₇ во второе уравнение системы и находим

α₆=α₁⊕α₃⊕α₄.􀀀

Не нашли, что искали? Воспользуйтесь поиском: