[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]

Помехоустойчивое кодирование

Надежность электронных устройств по мере их совершенствования все время возрастает, но, тем не менее, в их работе возможны ошибки, как систематические, так и случайные. Сигнал в канале связи может быть искажен помехой, поверхность магнитного носителя может быть повреждена, в разъеме может быть потерян контакт. Ошибки аппаратуры ведут к искажению или потере передаваемых или хранимых данных. При определенных условиях, некоторые из которых рассматриваются в этом разделе, можно применять методы кодирования, позволяющие правильно декодировать исходное сообщение, несмотря на ошибки в данных кода. В качестве исследуемой модели достаточно рассмотреть канал связи с помехами, потому что к этому случаю легко сводятся остальные. Например, запись на диск можно рассматривать как передачу данных в канал, а чтение с диска — как прием данных из канала.

1. Кодирование с исправлением ошибок

Пусть имеется канал связи С, содержащий источник помех:

где S — множество переданных, а S' — соответствующее множество принятых по каналу сообщений. Кодирование F, обладающее таким свойством, что

называется помехоустойчивым, или самокорректирующимся, или кодированием с исправлением ошибок.
Без ограничения общности можно считать, что А = В = {0, 1}, и что содержательное кодирование выполняется на устройстве, свободном от помех.

2. Классификация ошибок

Ошибки в канале могут быть следующих типов:

• 01, 10 — ошибка типа замещения разряда;
• 0 , 1 — ошибка типа выпадения разряда;
• 1, 0 — ошибка типа вставки разряда.

Канал характеризуется верхними оценками количества ошибок каждого типа, которые возможны при передаче через канал сообщения определенной длины. Общая характеристика ошибок канала (то есть их количество и типы) обозначается .
Пример
Допустим, что имеется канал с характеристикой = <1, 0, 0>, то есть в канале возможна одна ошибка типа замещения разряда при передаче сообщения длины n. Рассмотрим следующее кодирование: F(а): = ааа (то есть каждый разряд в сообщении утраивается) и декодирование F^-1 (аbс) : = а + b + с > 1 (то есть разряд восстанавливается методом “голосования”). Это кодирование кажется помехоустойчивым для данного канала, однако на самом деле это не так. Дело в том, что при передаче сообщения длины Зn возможно не более 3 ошибок типа замещения разряда, но места этих ошибок совершенно не обязательно распределены равномерно по всему сообщению. Ошибки замещения могут произойти в соседних разрядах, и метод голосования восстановит разряд неверно.

3. Возможность исправления всех ошибок

Пусть E_s — множество слов, которые могут быть получены из слова s в результате всех возможных комбинаций допустимых в канале ошибок , то есть s S А*, Еs В*. Если s' Е_s, то та конкретная последовательность ошибок, которая позволяет получить из слова s слово s', обозначается Е<s, s'>. Если тип возможных ошибок в канале подразумевается, то индекс не указывается.

Теорема
Чтобы существовало помехоустойчивое кодирование с исправлением всех ошибок, необходимо и достаточно, чтобыs1, s2 S Еs1 Е s2 = , то есть необходимо и достаточно, чтобы существовало разбиение множества В* на множества Вs (Вs = В*, Bs = ), такое что s S Еs Вs.

Доказательство
Если кодирование помехоустойчивое, то очевидно, что Е_s1 Е _s2 = . Обратно: по разбиению (Вs строится функция F_-1: s' F_-1(s') := s'.
Пример
Рассмотрим канал, в котором в любом передаваемом разряде происходит ошибка типа замещения с вероятностью р (0 < р < 1/2), причем замещения различных разрядов статистически независимы. Такой канал называется двоичным симметричным. В этом случае любое слово s Еⁿ₂ может быть преобразовано в любое другое слово s' Еⁿ₂ замещениями разрядов. Таким образом,s Еs = Еⁿ₂, и исправить все ошибки в двоичном симметричном канале невозможно.

4. Кодовое расстояние

Неотрицательная функция d(х, у): М х М R₊ называется расстоянием (или метрикой) на множестве М, если выполнены следующие условия (аксиомы метрики):

1. d(х, у) = 0 х = у,
2. d(х, у) = d(у, х),
3. d(х, у) <= d(х, z) + d(у, z).

Пусть

Эта функция называется расстоянием Хэммипга.
Мы рассматриваем симметричные ошибки, то есть если в канале допустима ошибка 0 1, то допустима и ошибка 1 0.
Введенная функция d является расстоянием. Действительно:

1. d( ', ') = 0 ' = ", поскольку ошибки симметричны, и из последовательности Е<', "> можно получить последовательность Е<", '>, применяя обратные ошибки в обратном порядке.

2. d(', ") = d(", ") по той же причине.

3. d(', ")<= d(', ") + d(", '), поскольку E<', "'> E< '", "> является некоторой последовательностью, преобразующей ' в ", а d (', ") является кратчайшей из таких последовательностей.

Пусть = <а_{i i}>ⁿ_i=1 — схема некоторого алфавитного кодирования, а d — некоторая метрика на В*. Тогда минимальное расстояние между элементарными кодами

называется кодовым расстоянием схемы .

Теорема
Алфавитное кодирование со схемой = <аi i>ni=1 и с кодовым расстоянием является кодированием с исправлением р ошибок типа тогда и только тогда, когда d() > 2р.

Доказательство
Е(х) — это шар радиуса р с центром в x для канала, который допускает не более р ошибок типа . Таким образом,

по теореме.

Пример

Расстояние Хэмминга в

5. Код Хэмминга для исправления одного замещения

Рассмотрим построение кода Хэмминга, который позволяет исправлять одиночные ошибки типа замещения.
Очевидно, что для исправления ошибки вместе с основным сообщением нужно передавать какую-то дополнительную информацию.
Пусть сообщение α = а₁ ... а_m кодируется словом = b₁ ... b_n, n > m. Обозначим k: = n - m. Пусть канал допускает не более одной ошибки типа замещения в слове длины n.

Отступление
Рассматриваемый случай простейший, но одновременно практически очень важный. Таким свойством, как правило, обладают внутренние шины передачи данных в современных компьютерах.

При заданном n количество дополнительных разрядов k подбирается таким образом, чтобы 2^k >= n + 1. Имеем:

Пример
Для сообщения длиной m = 32 потребуется k = 6 дополнительных разрядов, поскольку 64 = 2⁶ > 32 + 6 + 1 = 39.
Определим последовательности натуральных чисел в соответствии с их представлениями в двоичной системе счисления следующим образом:

• V₁:= 1, 3, 5, 7, 9, 11, ... — все числа, у которых разряд №1 равен 1;
• V₂:= 2, 3, 6, 7, 10, ... — все числа, у которых разряд №2 равен 1;
• V₃:= 4, 5, 6, 7, 12, ... - все числа, у которых разряд №3 равен 1,
• V₄:= 8, 9, 10, 11, 12, 13, 14, 15, 24 ... - все числа, у которых разряд №4 равен 1,

и т. д. По определению последовательность V_k начинается с числа 2^k-1.
Рассмотрим в слове b₁ ... b_n k разрядов с номерами 2⁰ = 1, 2¹ = 2, 2² = 4, ... 2^k-1. Эти разряды назовем контрольными. Остальные разряды, а их ровно m, назовем информационными. Поместим в информационные разряды все разряды слова a₁ ... а_n как они есть. Контрольные разряды определим следующим образом:

• b₁:= b₃ b₅ b₇ …, — то есть все разряды с номерами из V₁, кроме первого;
• b₂:= b₃ b₆ b₇ ..., — то есть все разряды с номерами из V₂, кроме первого;
• b₄:= b₅ b₆ b₇ ..., — то есть все разряды с номерами из V₃, кроме первого;

и вообще,
Пусть после прохождения через канал получен код с₁ ... с_n, то есть с₁ ... с_n : = С(b₁ ... b_n), причем

Здесь I — номер разряда, в котором, возможно, произошла ошибка замещения. Пусть это число имеет следующее двоичное представление: I = i_l ... i₁. Определим число J = j_l ... j₁ следующим образом:

• j₁ : = c₁ c₃ c₅ c₇ ..., — то есть все разряды с номерами из V₁;
• j₂ : = c₂ c₃ c₆ c₇ ..., — то есть все разряды с номерами из V₂;
• j₃ : = c₄ c₅ c₆ c₇ ..., — то есть все разряды с номерами из V₃;

и вообще,

Теорема
I=J.

Доказательство
Эти числа равны, потому что поразрядно равны их двоичные представления. Действительно, пусть i₁ = 0. Тогда I V₁, и значит,

по определению разряда b₁. Пусть теперь i₁ = 1. Тогда I V₁, и значит,

так как если в сумме по модулю два изменить ровно один разряд, то изменится и значение всей суммы. Итак, i₁ = j₁. Аналогично (используя последовательности V₂ и т. д.) имеем i₂ = j₂ и т. д.
Таким образом, I = J.
Отсюда вытекает метод декодирования с исправлением ошибки: нужно вычислить число J. Если J = 0, то ошибки нет, иначе с_J = с_J. После этого из исправленного сообщения извлекаются информационные разряды, которые уже не содержат ошибок.

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]