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

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

13.1 Основные понятия

Теорема Шеннона утверждает, что если скорость передачи информации источником меньше или равна пропускной способности канала, то существует код, обеспечивающий передачу информации по каналу со сколь угодно малой частотой ошибок. Однако с её помощью не решается вопрос, как следует кодировать сообщения, чтобы добиться при максимальной скорости передачи минимального количества ошибок, то есть не решается проблемы помехоустойчивого кодирования. Для решения этой проблемы используются специальные методы. Широкое распространение получили алгебраические методы, с помощью которых, в частности, исследован широкий класс так называемых групповых кодов, а также геометрические методы, при которых кодовые комбинации представляются в виде элементов некоторого абстрактного пространства, называемого кодовым пространством.

Рассмотрим построение кодового пространства применительно к равномерным кодам, в частности, к блочным, кодовые комбинации которых кодируются и декодируются независимо друг от друга. Пусть выходной алфавит B равномерного n-значного кода Г состоит из m символов; число m называется основанием кода. Кодовая комбинация такого кода имеет вид a₁a₂…a_n, где a_i – значение i-го разряда кода, i=1,2,…,n, . Упорядочим произвольно символы алфавита. Индекс класса поставим в соответствие значению остатка от деления любого представителя класса наm. Введём на множестве B две алгебраические операции: умножение и сложение, понимая под произведением классов класс, гдеr – остаток от деления произведения kj на m, и под суммой классов класс при k+j<m и класс при k+j≤m. Множество с введёнными операциями сложения и умножения является полем, что позволяет кодовые комбинации над алфавитом B рассматривать как векторы в n-мерном пространстве над полем B. Это пространство также называется кодовым пространством, а его элементы – кодовыми векторами.

При анализе воздействия ошибок на кодовые векторы в кодовом пространстве вводятся метрики. Наиболее часто применяются метрики Ли и Хэмминга. Для определения метрики Ли используется понятие веса вектора v = a₁a₂…a_n, где :

Расстоянием Ли d(v_j,v_k) между векторами v_j = a₁a₂…a_n и v_k = b₁b₂…b_n называется вес разности векторов v_j и v_k:

(13.1)

При построении большинства наиболее употребимых блочных кодов используется метрика Хэмминга. Вес вектора v, по Хэммингу, равен числу ненулевых разрядов этого вектора, а расстояние Хемминга между векторами v_j и v_k определяется как вес разности векторов v_j и v_k. Следует отметить, что при m=2 и m=3 расстояния Хэмминга и Ли совпадают.

Кодовое пространство n-разрядного кода с основанием m содержит mⁿ векторов. При передаче информации, как правило, используются не все возможные комбинации, а лишь некоторое их подмножество V₁={v₁,v₂,…,v_N}, где N<mⁿ. Обозначим расстояние между парой векторов V₁ символом d(v_i,v_j), где i, j =1,2,…,N, i ≠j. Величина min d(v_i,v_j) называется минимальным кодовым расстоянием и обозначается символом d.

В системах передачи и хранения данных обычно используют бинарные коды, то есть коды с основанием 2: B={0,1}. Определим минимальное кодовое расстояние системы векторов V={11001,01101,01110,00000}. Для бинарного кода операцию вычитания в выражении (13.1) можно заменить сложением по модулю 2. Расстояние между нулевой комбинацией и всеми остальными равно 3, то есть числу единиц в каждой из комбинаций. Для остальных векторов

11001+01101 = 10100,

11001+01110 = 10111,

01101+01110 = 00011.

Минимальное число единиц в результирующих векторах равно 2, следовательно, минимальное кодовое расстояния d=2.

Для анализа действия помех на передаваемый кодовый вектор вводят понятие вектора ошибки. Кодовый вектор v₁ и вектор ошибки e складываются по модулю 2, после чего получается искажённый вектор v₁'. Например, если v₁ = 11111 и e=01000, то v₁' = 10111. Следовательно, в разрядах передаваемой кодовой комбинации, соответствующих единичным разрядам вектора e, возникают ошибки.

При исследовании процесса возникновения ошибок в дискретном канале используют математические модели ошибок, которые представляют собой распределение вероятностей по всем возможным векторам ошибки. В качестве примера рассмотрим одну из самых распространённых моделей, которая основана на статистической гипотезе о том, что в каждом разряде вектора ошибки единица появляется с вероятностью p независимо от того, какие значения получили остальные разряды вектора ошибки. Величина, равная количеству единиц в векторе ошибки называется кратностью и обозначается символом q. Из теории вероятностей известно, что выдвинутой статистической гипотезе соответствует биномиальный закон распределения кратности ошибки. Поэтому математической моделью ошибки может служить выражение , определяющая вероятность того, что при передаче по дискретному каналу в кодовой комбинации бинарного кода длиныn возникнет ошибка кратности q.

Определим вероятности появления ошибок кратности 0, 1, 2, 3, 4, 5 в кодовой комбинации длины 5 бинарного кода, если вероятность ошибочного приёма разряда равна 0,1. Используя биномиальный закон распределения получаем, что P_5,0=0,56, P_5,1=0,33, P_5,2=0,07, P_5,3=0,008, P_5,4=0,00004, P_5,5=0,00001. Отсюда видно, что вероятность появления ошибок большой кратности мала. Наиболее часто появляются ошибки кратности 1.

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