ЧАСТЬ 1 ВВЕДЕНИЕ

Максимов М.Н.

В г.ТАГАНРОГЕ

________________________________________________________

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

Таганрог 2011

ГЛАВА3. 4

ЧАСТЬ 1 ВВЕДЕНИЕ.. 4

1.1. Кодирование для исправления ошибок: Основные положения. 7

1.1.1. Блоковые и сверточные коды.. 7

1.1.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность. 8

1.2. Линейные блоковые коды.. 11

1.2.1. Порождающая и проверочная матрицы.. 12

1.2.2. Вес как расстояние. 13

1.3. Кодирование и декодирование линейных блоковых кодов. 13

1.3.1. Кодирование с помощью матриц G и Н.. 13

1.3.2. Декодирование по стандартной таблице. 15

1.3.3. Хемминговы сферы, области декодирования и стандартная таблица. 19

1.4. Распределение весов и вероятность ошибки. 21

1.4.1. Распределение весов и вероятность необнаруженной ошибки в ДСК. 21

1.4.2. Границы вероятности ошибки в ДСК, каналах с АБГШ и с замираниями. 23

1.5 Общая структура жесткого декодера для линейных кодов. 33

Вопросы для самоконтроля. 34

ЧАСТЬ 2 КОДЫ ХЕММИНГА, ГОЛЕЯ И РИДА-МАЛЛЕРА.. 39

2.1. Коды Хемминга. 39

2.1.1. Процедуры кодирования и декодирования. 40

2.2. Двоичный код Голея. 43

2.2.1 Кодирование. 43

2.2.2. Декодирование. 44

2.2.3. Арифметическое декодирование расширенного (24,12,8) кода Голея. 44

2.3. Двоичные коды Рида-Маллера. 46

2.3.1. Булевы полиномы и РМ коды.. 46

2.3.2. Конечные геометрии и мажоритарное декодирование. 48

Вопросы для самоконтроля. 54

ЧАСТЬ 3 ДВОИЧНЫЕ ЦИКЛИЧЕСКИЕ КОДЫ И КОДЫ БЧХ.. 54

3.1. Двоичные циклические коды. 55

3.1.1. Порождающий и проверочный полиномы. 55

3.1.2. Порождающий многочлен. 56

3.1.3. Кодирование и декодирование двоичных циклических кодов. 57

3.1.4. Проверочный полином. 59

3.1.5. Укороченные циклические коды и CRC коды.. 61

3.2. Общий алгоритм декодирования циклических кодов. 63

3.2.1. Арифметика GF(q) 66

3.3. Двоичные коды БЧХ.. 72

3.4. Полиномиальные коды.. 74

3.5. Декодирование двоичных БЧХ кодов. 75

3.5.1. Общий метод декодирования для БЧХ кодов. 77

3.5.2. Алгоритм Берлекемпа-Мэсси (ВМА) 78

3.5.3. Декодер PGZ.. 81

3.5.4. Евклидов алгоритм (ЕА) 83

3.5.5. Метод Ченя и исправление ошибок. 85

3.5.6. Исправление стираний и ошибок. 86

3.6. Распределение весов и границы вероятности ошибки. 88

3.6.1. Оценка вероятности ошибки. 89

Вопросы для самоконтроля. 92

ЧАСТЬ 4 НЕДВОИЧНЫЕ БЧХ КОДЫ -КОДЫ РИДА-СОЛОМОНА.. 94

4.1. Коды PC как полиномиальные коды.. 94

4.2. От двоичных кодов БЧХ к PC кодам.. 95

4.3. Декодирование кодов PC.. 96

4.3.1. Комментарий к алгоритмам декодирования. 101

4.3.2. Исправление ошибок и стираний. 102

4.4. Распределение весов. 107

Вопросы для самоконтроля. 108

ГЛОССАРИЙ.. 109

ЛИТЕРАТУРА.. 110

ГЛАВА3

История кодов, исправляющих ошибки, началась с изобретения кодов Хемминга почти одновременно с появлением основополагающей работы Шеннона. Чуть позже были предложены коды Голея. Эти классы кодов являются оптимальными. Понятие оптимальности кода мы рассмотрим в последующих разделах.

На Рисунке 1 показана блок-схема канонической цифровой системы передачи или хранения информации. Это знаменитый Рисунок 1, с которого начинаются почти все книги по теории помехоустойчивого кодирования (в дальнейшем будет использоваться сокращение ЕСС со значением - помехоустойчивое кодирование, или кодирование с исправлением ошибок, или коды, исправляющие ошибки). Источник и получатель информации обычно включают какое-либо кодирование (преобразование) источника, соответствующее природе информации. Кодирующее устройство (кодер канала) системы помехоустойчивого кодирования получает информационные символы от источника и добавляет к ним избыточные символы таким образом, чтобы могла быть исправлена большая часть ошибок, возникающих в процессе модуляции сигналов, их передачи по каналу с шумом и демодуляции.

Рис. 1. Каноническая цифровая система связи.

Обычно предполагается, что в канале связи отсчеты аддитивного шумового процесса прибавляются к модулированным символам (рассматривается узкополосное комплексное представление сигналов). Отсчеты шума предполагаются независимыми от источника символов. Эту модель сравнительно легко исследовать. Она легко позволяет включить каналы с гауссовым шумом (АБГШ), каналы с общими Релеевскими замираниями, а также двоичный симметричный канал (ДСК). На приемной стороне декодирующее устройство (декодер канала) использует избыточные символы для исправления ошибок, внесенных каналом связи. В режиме обнаружения ошибок декодер ведет себя как кодер полученного из канала сообщения и проверяет совпадение вычисленных избыточных символов с принятыми.

В классической теории кодов, исправляющих ошибки, комплекс, включающий модулятор, демодулятор и шумовую среду распространения сигналов, называется дискретным каналом без памяти с входом v и выходом г. Примером такого канала является система передачи двоичных сигналов по каналу с АБГШ (аддитивным белым гауссовым шумом), который моделируется как двоичный симметричный канал с вероятностью ошибки (или вероятностью перехода) р равной вероятности ошибки на бит для двоичного сигнала в АБГШ,

(1.1)

где

(1.2)

является гауссовой Q-функцией и Е_b/N₀ есть отношение сигнал-шум (SNR) на бит. Этот случай будет исследован ниже в этой части.

В 1974 Мэсси предложил рассматривать помехоустойчивое кодирование (ЕСС) и модуляцию как единое целое, известное в современной литературе как кодовая модуляция (coded modulation) (Часто используется и несколько более точный термин — сигнально кодовая конструкция). Совместное конструирование кода и множества сигнальных точек обеспечивает более высокую эффективность и больший (энергетический) выигрыш от кодирования (coding gain) {Выигрыш от кодирования определен как разность между отношениями сигнал-шум системы с кодированием и системы без кодирования при одинаковой скорости (и одинаковой вероятности ошибки)}, чем последовательное применение ЕСС и модуляции. В этой пособии рассмотрены некоторые методы комбинирования кодирования и модуляции, включая: решетчатую кодовую модуляцию (ТСМ— trellis-coded modulation) in многоуровневую кодовую модуляцию (МСМ — multilevel coded modulation). В системах кодовой модуляции «мягкое решение» (soft decision) на выходе канала вводится непосредственно в декодер и обрабатывается им. Напротив, в классической системе с помехоустойчивым кодированием в декодер вводится «жесткое решение» (hard decision) демодулятора.

Коды, исправляющие ошибки, можно комбинировать различными способами. Примером последовательного каскадирования (serial concatenation, т.е. каскадная конструкция в классическом смысле) является следующая конструкция. Многие годы наиболее популярной каскадной схемой ЕСС была комбинация внешнего кода Рида-Соломона (PC), промежуточного перемежения (или перемешивания — interleaving) и внутреннего сверточного кода. Эта конструкция была использована во многих приложениях от систем космической связи до цифровых широковещательных систем телевидения высокой четкости. Основная идея состоит в том, что пакеты ошибок, которые появляются на выходе декодера сверточного кода с мягким решением, могут быть разбиты на мелкие части с помощью интерливинга и затем полностью исправлены декодером кода PC. Коды Рида-Соломона являются недвоичными кодами, каждый символ которых состоит из нескольких двоичных бит. Эти коды способны исправлять многократные пакеты ошибок. Преимуществом каскадной конструкции является то, что для нее требуются раздельные декодеры внутреннего и внешнего кодов вместо одного, но очень сложного декодера для каскадного кода в целом.

В пособии изучаются разные типы систем с ЕСС. Сначала рассматриваются базовые кодовые конструкции и алгоритмы их декодирования в Хемминговом пространстве (т.е. работающие с битами). Затем, во второй части пособия, вводятся алгоритмы декодирования с мягким решением для передачи двоичных сигналов, работающие в Евклидовом пространстве. В системах этого типа необходимая мощность передаваемых сигналов снижается на 2 дБ/бит по сравнению с декодерами в Хемминговом пространстве (с жестким решением). Рассматриваются декодеры с мягким решением нескольких типов. При этом основное внимание уделяется собственно алгоритмам (тому, как они работают), а не теоретическим вопросам (почему они работают).

1.1. Кодирование для исправления ошибок: Основные положения

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

Рис.2. Систематическое блоковое кодирование для исправления ошибок.

кодирования блокового кода (block code). Такое кодирование называют систематическим (systematic). Это означает, что информационные символы всегда появляются на первых к позициях кодового слова. Символы на оставшихся п-к позициях являются различными функциями от информационных символов, обеспечивая тем самым избыточность, необходимую для обнаружения или исправления ошибок. Множество всех кодовых последовательностей называют кодом, исправляющим ошибки (error correcting code), и обозначают через С.

1.1.1. Блоковые и сверточные коды

В соответствии с тем, как вводится избыточность в сообщение, коды, исправляющие ошибки, могут быть разделены на два класса: блоковые и сверточные (convolutional code) коды. Обе схемы кодирования нашли практическое применение. Исторически сверточные коды имели преимущество главным образом потому, что для них известен алгоритм декодирования Витерби с мягким решением и в течение многих лет существовала убежденность в том, что блоковые коды невозможно декодировать с мягким решением. Однако последние достижения в теории и конструировании алгоритмов декодирования с мягким решением для линейных блоковых кодов помогли рассеять это убеждение. Более того, наилучшие ЕСС, известные сегодня (в начале двадцать первого века), являются блоковыми кодами (нерегулярными кодами с низкой плотностью проверок - irregular low-density parity-check codes).

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

Следует заметить, что на самом деле блоковые коды обладают памятью, если рассматривать кодирование как побитовый процесс в пределах кодового слова. Сегодня это различие между блоковыми и сверточными кодами кажется все менее и менее ясным, особенно после недавних достижений в понимании решетчатой (trellis) структуры блоковых кодов и кольцевой (tail-biting) структуры некоторых сверточных кодов.

Примечание: Название кольцевые сверточные коды еще не окончательно утвердилось в отечественной литературе, иногда tail-biting convolutional codes называют циклически замкнутыми.

Специалисты по сверточным кодам иногда рассматривают блоковые коды как «коды с меняющейся во времени структурой решетки» (time-varying trellis structure). Аналогично, специалисты в области блоковых кодов могут рассматривать сверточные коды как «коды с регулярной структурой решетки».

1.1.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность

Рассмотрим двоичный код С, исправляющий ошибки. Если не все из 2^п возможных двоичных векторов длины п будут передаваться по каналу связи, то этот код может обладать свойством помехоустойчивости. В действительности, код С является подмножеством w-мерного двоичного векторного пространства V₂ = {0, 1}ⁿтаким, что элементы этого подмножества максимально удалены друг от друга.

В двоичном пространстве V₂ расстояние определяется как число позиций, на которых два вектора не совпадают. Пусть x₁=(x_1,0, x_1,1, …,x_1,n-1) и х₂=(х_2,0 , х_2,1,..., x_2,n-1) два вектора в V₂. Тогда Хеммингово расстояние между векторами х₁ и х₂, обозначаемое как d_H(x₁, x₂), равно

(1.3)

где через |А| обозначено число элементов в множестве А.

Для заданного кода С минимальное Хеммингово расстояние, d_min, определяется как минимум Хеммингова расстояния по всем возможным парам различных кодовых слов,

(1.4)

Повсюду в пособии обозначение (n, k, d_min) используется для параметров блокового кода длины n, который используется для кодирования сообщений длины k, и имеет минимальное Хеммингово расстояние d_min. Предполагается, что число кодовых слов этого кода равно |С|=2^k.

Пример 1.Простейшим примером является код-повторение длины 3. Каждый информационный бит повторяется три раза. Таким образом, сообщение «0» кодируется вектором (000), а сообщение «1», вектором (111). Так как два вектора различаются в трех позициях, Хеммингово расстояние между ними равно 3. На Рисунке 3 показано графическое представление этого кода. Трехмерное двоичное векторное пространство соответствует 2³=8 вершинам трехмерного единичного куба. Хеммингово расстояние между кодовыми словами (000) и (111) равно числу вершин, через которые проходит соединяющий их путь. Это эквивалентно числу координат, которые необходимо изменить, чтобы преобразовать (000) в (111) и наоборот. Таким образом, d_H= ((000),(111)) = 3. Так как в этом коде только два кодовых слова, то d_min = 3.

Двоичное векторное пространство V₂ обычно называют Хемминговым пространством. Пусть v кодовое слово кода С. Хемминговой сферой S_t(v) радиуса t с центром в точке v является

Рис. 3. (3,1,3) код-повторение в трехмерном векторном пространстве.

Рис. 4. Хемминговы сферы радиуса t=1, окружающие кодовые слова (3,1,3) двоичного кода-повторения.

множество векторов (точек) в V₂ на расстоянии меньше или равном t от центра v,

(1.5)

Заметим, что число слов (число векторов) в S_t(v) равно

(1.6)

Пример 2. На Рисунке 4 показаны Хемминговы сферы радиуса t = 1, окружающие кодовые слова (3,1,3) двоичного кода-повторения.

Заметим, что Хемминговы сферы для этого кода не пересекаются, т.е. в пространстве V₂ нет векторов (или вершин в единичном трехмерном кубе), принадлежащих одновременно и S₁(000), и S₁(111). В результате, если изменить любую одну позицию кодового слова v, то получится вектор, который, тем не менее, останется внутри Хемминговой сферы с центром в v. Эта идея является принципиальной для понимания и определения корректирующей способности кода С.

Корректирующей способностью (error correcting capability) t кода С называют наибольший радиус Хемминговой сферы S_t(v) для всех кодовых слов v C такой, что для любых различных пар v_i, v_j С соответствующие им Хемминговы сферы не пересекаются, т.е.

(1.7)

Это соответствует более распространенному определению

(1.8)

где [x] обозначена целая часть x, т.е. целое число меньше или равное x.

Заметим, что для определения минимального кодового расстояния произвольного блокового кода С в соответствии с (1.4), необходимо вычислить все 2^k(2^k — 1) расстояний между различными парами кодовых слов. Это практически невозможно даже для сравнительно коротких кодов, например, с к = 50. Одним из важных преимуществ линейных блоковых кодов является то, что для вычисления d_min достаточно знать только Хемминговы веса 2^к — 1 ненулевых кодовых слов.

1.2. Линейные блоковые коды

Как уже упоминалось выше, построение хорошего кода означает поиск в V₂ подмножества элементов в наибольшей степени удаленных друг от друга. Это очень трудная задача. Более того, если даже это сделано, то остается неясным как назначить кодовые слова информационным сообщениям.

Линейный код (т.е. множество кодовых слов) является векторным подпространством в пространстве V₂. Это означает, что операция кодирования может быть представлена умножением на матрицу. В терминах цифровой электроники простое кодирующее устройство может быть построено на элементах «исключающее ИЛИ», «И» и триггерах типа D. В этой части операциями сложения и умножения вдвоичном векторном пространстве являются «исключающее ИЛИ» (сложение по модулю 2) и «И», соответственно. Таблицы сложения и умножения двоичных элементов имеют следующий вид:

1.2.1. Порождающая и проверочная матрицы

Пусть С двоичный линейный (п, к, d_min) код. Так как С есть k-мерное подпространство, то оно имеет базис, например, (v₀, v₁,…, v_k-1) такой, что любое кодовое слово v С может быть записано как линейная комбинация элементов этого базиса:

(1.9)

где u_i {0, 1}, 0 ≤ i < k. Уравнение (1.9) может быть записано в матричной форме через порождающую матрицу G и вектор-сообщение и = (и₀, u₁, …, u_k-1):

v=uG (1.10)

где

(1-11)

Так как С является k- мерным векторным пространством в V₂, то существует (n-k)-мерное дуальное пространство (dual space) С┴, которое порождается строками матрицы Н, называемой проверочной матрицей (parity-check matrix), такой, что GH^T=0,где через Н^T обозначена транспонированная матрица Н. Заметим, в частности, что любое кодовое слово v С удовлетворяет условию

vH^T=0 (1.12)

Как будет показано в разделе 1.3.2 уравнение (1.12) является фундаментальным для декодирования линейных кодов.

Линейный код С┴, который генерируется матрицей Н, является двоичным линейным (п, п - k, d┴_min) кодом, который называют обычно дуальным коду С.

1.2.2. Вес как расстояние

Как упоминалось в разделе 1.1.2, линейные коды отличаются тем, что для определения минимального расстояния кода достаточно знать минимум Хеммингова веса ненулевых кодовых слов. Ниже этот факт будет доказан. Определим вес Хемминга wt_H (x) вектора х V₂, как число ненулевых элементов в х. Из определения Хеммингова расстояния ясно, что wt_H(x) = d_H(x, 0). Для двоичного линейного кода С получаем

(1-13)

Наконец, из свойства линейности кода имеем v₁+v₂ C. Отсюда следует, что минимальное расстояние кода С равно и может быть вычислено как минимальный вес по всем 2^к — 1 ненулевым кодовым словам. Эта задача существенно проще, чем полный перебор по всем парам кодовых слов, хотя и остается очень сложной даже для кодов среднего размера (или размерности к).

1.3. Кодирование и декодирование линейных блоковых кодов

1.3.1. Кодирование с помощью матриц G и Н

Равенство (1.10) определяет по существу правило кодирования для линейного блокового кода, которое может быть использовано непосредственно. Если кодирование должно быть систематическим, то произвольная порождающая матрица G линейного блокового (n, к, d_min) кода С может быть преобразована к систематической форме G_sys (иначе, к канонической форме) с помощью элементарных операций и перестановок столбцов матрицы. Матрица G_sys состоит из двух подматриц: k×k единичной матрицы, обозначаемой I_k, и k× (n-k) проверочной подматрицы Р. Таким образом,

(1.14)

где

(1.15)

Так как GH^T = 0, то отсюда следует, что систематическая форма проверочной матрицы имеет вид

(1-16)

Пример 3.Рассмотрим двоичный линейный (4,2,2) код с порождающей матрицей

Перестановкой второго и четвертого столбцов преобразуем эту матрицу в систематическую форму

Таким образом, проверочная подматрица равна

Интересно отметить, что в данном случае выполняется соотношение Р = Р^т. Из (1.16)следует, что систематическая форма проверочной матрицы имеет вид

В дальнейшем будет использовано обозначение u = (u₀, u₁,…,u_k-1) для информационного сообщения и обозначение v = (v₀, v_l,..., v_n-1) для соответствующего кодового слова кода С.

Если параметры С таковы, что k<(n- k) или, эквивалентно, скорость кода k/п < 1/2, то кодирование с помощью порождающей матрицы более экономно по числу логических операций.

В этом случае

(1.17)

где v_р= uP = (v_k,v_k+1,…,v_n-1) представляет проверочную часть кодового слова.

Однако, если k>(n-k) или k/n > 1/2, тогда кодирование с помощью проверочной матрицы Н требует меньшего количества вычислений. Этот вариант кодирования основан на уравнении (1.12) (u, v_p)H^T= 0. Проверочные позиции (v_k, v_k+1, …, v_n-1) вычисляются следующим образом:

(1.18)

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

Пример 4.Рассмотрим двоичный линейный (4,2,2) код из примера 3. Пусть сообщение и кодовые слова обозначены u= (u₀,u₁) иv = (v₀, v₁, v₂, v₃), соответственно. Из уравнения (1.18) получаем

v₂=u₀+ u₁,

^V3=u₀

Соответствие между 2² = 4 двух битными сообщениями и кодовыми словами имеет следующий вид:

(1-19)

1.3.2. Декодирование по стандартной таблице

В этом разделе представлена процедура декодирования, которая находит кодовое слово v, ближайшее к принятому с искажениями слову r = v + е, где вектор ошибок е {0, 1} создан двоичным симметричным каналом (ДСК) в процессе передачи кодового слова. Модель ДСК показана на Рисунке 5. По предположению переходная вероятность р (или параметр ДСК) меньше 1/2.

Рис.5. Модель двоичного симметричного канала.

Стандартной таблицей (или стандартной расстановкой) для двоичного линейного (n, k, d_min) кода С называется таблица всех возможных принятых из канала векторов r, организованная таким образом, что может быть найдено ближайшее к r кодовое слово v.

Таблица 1. Стандартная таблица двоичного линейного блокового кода.

Стандартная таблица содержит 2^n-k строк и 2^к + 1 столбцов. Правые 2^к столбцов таблицы содержат все вектора из пространства V₂={0,1}ⁿ

Для описания процедуры декодирования необходимо ввести понятие синдрома. Определение синдрома произвольного слова из V₂ следует из уравнения (1.12),

(1-20)

где Н проверочная матрица кода С. Покажем, что синдром является индикатором вектора ошибок. Предположим, что кодовое слово v С, переданное по ДСК, принято как r = v + е. Синдром принятого слова равен

(1.21)

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

Процедура построения стандартной таблицы

Правые столбцы первой строки заполним кодовыми словами кода С, начиная с нулевого кодового слова. В первую ячейку первого столбца запишем нулевой синдром. Положим j = 0.

Для j =j + 1, найдем слово е_j V₂ минимального веса Хемминга, не являющееся кодовым и не включенное в предыдущие строки таблицы. Соответствующий синдром s_j = e_jH^T запишем в первый (крайний левый) столбец j-ой строки. В оставшиеся 2^к ячеек этой строки запишем суммы e_j и содержимого первой строки (т.е. кодового слова).

3. Повторяем шаг 2 процедуры, пока все вектора из V₂ не окажутся включенными в таблицу. Эквивалентно, повторяем шаг 2 пока j <2^п-к, иначе Стоп.

Пример 5.Стандартная таблица двоичного линейного (4,2,2) кода:

Декодирование с помощью стандартной таблицы выполняется следующим образом. Пусть r = v +е принятое слово. Найдем это слово в таблице и возьмем в качестве результата декодирования сообщение u, записанное в верхней (первой) ячейке того столбца, в котором лежит принятое слово r. По идее, этот процесс требует хранения в памяти всей таблицы и поиска в ней заданного слова.

Однако, возможно некоторое упрощение процедуры декодирования, если заметить, что все элементы одной и той же строки имеют один и тот же синдром. Каждая строка Row_i,0 ≤i<2^n-k, этой таблицы представляет смежный класс кода С, а именно, Row_i= { e_i +v|v C}. Вектор е_i называется лидером смежного класса.

Синдром всех элементов i-ой строки равен

(1.22)

и не зависит от конкретного значения кодового слова v С. Упрощенная процедура декодирования состоит в следующем: вычислить синдром принятого слова r = е_j + v

и найти его в левом столбце стандартной таблице; взять лидер смежного класса е_j из второго столбца той же строки и прибавить его к принятому слову, получив ближайшее к принятому r = е’_j + v’кодовое слово v’.

Таким образом, вместо таблицы п×2^п бит для декодирования достаточно использовать таблицу лидеров смежных классов п х 2^n-kбит.

Пример 6.Снова рассмотрим двоичный линейный (4, 2, 2) код из Примера 3. Положим, что передано было кодовое слово (0110), а принято слово (0010). Тогда синдром равен

Находим в стандартной таблице лидер смежного класса (0100) и получаем декодированное кодовое слово (0010)+(0100)=(0110). Одиночная ошибка в слове исправлена! Это может показаться странным, так как минимальное кодовое расстояние равно 2 и, согласно условию (1.8), исправление однократных ошибок невозможно. Однако объяснение этому может быть найдено в стандартной таблице (Пример 5). Заметим, что третья строка таблицы содержит два различных двоичных вектора веса 1. Это означает, что только три из возможных четырех одиночных ошибок могут быть исправлены. В Примере 6 дана одна из исправляемых ошибок.

Оказывается, что данный (4, 2, 2) код является простейшим примером линейного кода с неравной защитой от ошибок (linear unequal error protection - LUEP код). Данному LUEP коду соответствует разделяющий вектор (3,2), который показывает, что минимальное кодовое расстояние равно трем, если различаются первые биты сообщений и равно двум, если различаются вторые биты сообщений.

В случае систематического кодирования рассмотренная выше процедура находит оценку переданного сообщения на первых kпозициях декодированного слова. Это может быть одной из возможных причин применения систематического кодирования.

1.3.3. Хемминговы сферы, области декодирования и стандартная таблица

Стандартная таблица предоставляет удобный способ объяснения понятий Хемминговой сферы и корректирующей способности линейного кода С, введенной в Разделе 1.1.2.

Из конструкции стандартной таблицы видно, что j-ый столбец из 2^k правых столбцов таблицы, обозначаемый Col_j, 1 ≤ 2^k, содержит кодовое слово v_j С и множество 2^n-kслов, ближайших к нему по Хеммингову расстоянию, т.е.

(1.23)

Каждый столбец (1.23) представляет собой область декодирования j-ого кодового слова в Хемминговом пространстве. Таким образом, если по ДСК передано кодовое слово v_j С и принятое слово rпринадлежит столбцу Col_j, то оно будет успешно декодировано в переданное слово v_j.