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

Граница Хемминга

Множество столбцов Col_jи корректирующая способность t кода С связаны между собой через Хеммингову сферу S_t(y_j) следующим образом: двоичный линейный (п, k, d) код С имеет корректирующую способность t, если каждая область декодирования Со1_jсодержит Хеммингову сферу радиуса t, т.е. S_t(v_j)  Col_j.

Учитывая, что каждая область декодирования содержит 2^n-kслов, и, используя уравнение (1.6), получаем знаменитую границу Хемминга

                                          (1-24)

где

Граница Хемминга имеет несколько комбинаторных интерпретаций. Вот одна из них:

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

Пример7. Двоичный код (3,1,3) имеет порождающую матрицу G = (111) и проверочную матрицу

Соответственно, стандартная таблица имеет вид:

Четыре вектора во втором столбце таблицы (т.е. лидеры смежных классов) являются элементами Хемминговой сферы S₁(000), показанной на Рисунке 4. Этот столбец содержит все векторы длины 3 ивеса 1 или меньше. Аналогично, третий столбец (правый) содержит все элементы S₁(111). Для этого кода граница Хемминга выполняется с равенством.

Блоковые коды, удовлетворяющие границе (1.24) с равенством, называются совершенными кодами. Нетривиальными совершенными кодами являются следующие:

- двоичные (2^т - 1, 2^т - т - 1, 3) коды Хемминга,

- недвоичные (q^т - 1)/(q - 1), (q^m - 1)/(q - 1) - т - 1, 3) коды Хемминга, q > 2.

- коды-повторения (n,1,n),

- коды с проверкой на четность (n,n-1,2),

- двоичный (23,12,7) код Голея и

- троичный (11,6,5) код Голея.

Расширенные, т.е. дополненные общей проверкой на четность, коды Хемминга и Голея тоже совершенны.

Для недвоичных кодов граница Хемминга имеет вид:

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

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

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

Распределение весов W(С) = {A_i ,0 ≤ i ≤ n} кода С, исправляющего ошибки, определено как совокупность п + 1 целых A_i где A_i — количество кодовых слов Хеммингова веса i.

В следующем ниже разделе выводится оценка вероятности необнаруженной ошибки линейного кода в ДСК. Заметим, прежде всего, что вес wt(v) слова v равен Хеммингову расстоянию до нулевого слова, т.е. wt(v) = d_H(v,0). Напомним также, что Хеммингово расстояние между кодовыми словами v₁ и v₂ равно весу их разности,

где из линейности кода следует, что v₃  С

Вероятность необнаруженной ошибки P_U(C) равна вероятности того, что принятое из канала связи слово отличается от переданного, но имеет нулевой синдром, т.е.

 Таким образом, вероятность того, что синдром принятого ненулевого слова равен нулю, есть вероятность того, что вектор ошибок совпадает с одним из ненулевых кодовых слов.

В ДСК вектор ошибок веса i возникает с вероятностью, равной вероятности того, что i символов приняты с ошибкой, а остальные n-i приняты правильно. Обозначим вероятность этого события через Р(е,i). Тогда

Для того чтобы возникла необнаруженная ошибка, вектор ошибок должен быть ненулевым кодовым словом. Имеется А_i кодовых слов веса i в кодовом множестве С. Следовательно,

               (1.26)

Формула (1.26) дает точное значение Р_и(С) в ДСК. К сожалению, для большинства кодов, имеющих практическое значение, распределение весов неизвестно. В таких случаях, можно использовать тот факт, что число кодовых слов веса i меньше (или равно) общего числа слов веса i в двоичном векторном пространстве V₂. Следовательно, справедлива следующая верхняя граница:

                                     (1.27)

Примечание  На самом деле допустима и более сильная оценка:

В уравнении еН^т = 0 матрица Н имеет ранг p=d_min-1 и, по меньшей мере, р неизвестных элементов любого вектора ошибок еопределяются однозначно. Следовательно, средняя вероятность того, что произвольный вектор ошибок совпадает с некоторым кодовым словом, не превосходит 2^-p.

Формулы (1.26) и (1.27) полезны в системах, использующих помехоустойчивое кодирование только для обнаружения ошибок таких, как системы связи с обратной связью и автоматическим

Рис. 6. Точное значение и верхняя граница вероятности необнаруженной ошибки для двоичного линейного (4,2,2) кода в ДСК.

запросом (ARQ) на повторную передачу сообщения с обнаруженными ошибками. Оценки помехоустойчивости для случая, когда кодирование используется для исправления ошибок, выводятся в следующем ниже разделе.

Пример 8.Для двоичного линейного (4,2,2) кода из Примера 4 W(C)=( 1,0,1,2,0). С помощью (1.26) находим

На Рисунке 6 показана зависимость Р_и(С) вместе с правой частью границы (1.27).

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

Целью этого раздела является введение в базовые модели каналов связи, которые будут рассматриваться в пособии, и вывод формул для оценки помехоустойчивости линейных кодов. Первым рассматривается ДСК.

Модель ДСК

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

Обозначим L_i число лидеров смежных классов веса i в стандартной таблице линейного кода С. Вероятность правильного декодирования равна вероятности того, что вектор ошибок совпадает с одним из лидеров смежных классов,

                                           (1.28)

где  это максимальный вес лидера смежного класса е. Для совершенных кодов = t,

и из границы Хемминга (1.24) следует, что

В общем случае для двоичных кодов выражение (1.28) дает нижнюю границу P_C(C), так как существует хотя бы один лидер смежного класса веса более t.

Вероятность неправильного декодирования  или вероятность ошибки декодирования равна вероятности того, что вектор ошибок принадлежит дополнению множества исправляемых ошибок, т.е. P_e(C) = 1 - P_C(C). Из (1.28) получаем,

                                             (1-29)

Наконец, учитывая обсуждение оценки (1.28), получаем верхнюю границу

                                                (1.30)

которую можно записать и в следующем виде

                                             (1.31)

Рис.7. Вероятность ошибки декодирования для двоичного (3,1,3) кода.

Эти границы удовлетворяются с равенством только для совершенных кодов (когда и граница Хемминга удовлетворяется с равенством).

Пример 9.На Рисунке 7 показана зависимость Р_е(С) по оценке (1.31) от переходной вероятности ДСК p для двоичного (совершенного) кода-повторения (3,1,3).

Модель канала с АБГШПожалуй, наиболее важной моделью для систем цифровой связи является модель канала с аддитивным белым гауссовым шумом (АБГШ - additive white Gaussian noise (AWGN)). В этом разделе выводятся оценки вероятности ошибки декодирования и вероятности ошибки на бит для линейных кодов в канале с АБГШ. Хотя аналогичные выражения оказываются справедливыми и для сверточных кодов, они будут выведены в последующих разделах, вместе с обсуждением декодирования с «мягким решением» по алгоритму Витерби. Следующие ниже результаты содержат необходимые инструменты для оценки помехоустойчивости двоичных систем кодирования в гауссовом канале.

Рассмотрим двоичную систему передачи сигналов, в которой кодовые символы {0,1} отображаются в действительные числа {+1,-1}, соответственно, как показано на Рисунке 8. В дальнейшем, вектора имеют размерность п и обозначение х = (x₀, x₁, …, x_n-1). Условная функция плотности вероятности (ф.п.в.) последовательности у на выходе канала при условии, что на его входе передавалась последовательность х, равна

                              (1-32)

где р_п(п) есть ф.п.в. п статистически независимых и одинаково распределенных (i.i.d.) отсчетов шума, каждый из которых имеет Гауссово распределение с нулевым средним и дисперсией, равной N₀/2. Величина N₀ называется односторонней спектральной плотностью мощности шума. Легко показать, что декодирование по максимуму правдоподобия (м.п.) линейного кода в таком канале соответствует выбору последовательности х', минимизирующей квадрат Евклидова расстояния между принятой последовательностью у и х', т.е.

                                                 (1.33)

Следует заметить, что декодер, использующий (1.33) как метрику, называется декодером с мягким решением не зависимо от того, используется или нет принцип максимума правдоподобия.

Рис.8. Система двоичной передачи с кодированием по каналу с АБГШ.

Рис.9. Вероятность ошибки декодирования для жесткого декодирования (Pt(3,l,3)_HDD) и мягкого декодирования (Pe(3,l,3)_SDD) двоичного (3,1,3) кода при передаче двоичных сигналов в канале с АБГШ.

Вероятность ошибки для МП декодирования, Р_е(С), равна вероятности того, что при передаче последовательности х вектор шума оказался таким, что принятая последовательность у = х + n ближе к другой кодовой последовательности х"  С, х" ≠ х. Для линейного кода можно предположить, что передается нулевое кодовое слово. Тогда вероятность Р_е(С) может быть ограничена сверху с помощью границы объединения и распределения весов W(C) следующим образом:

                                                (1-34)

где R = k/n скорость кода, Е_ь/N₀ отношение энергии сигнала на бит к мощности шума или (SNR на бит) и Q(x) определено в (1.2).

На Рисунке 9 показаны оценки вероятности ошибки для жесткого декодирования (1.30) и для мягкого декодирования (1.34) для двоичного (3,1,3) кода. Декодирование с жестким решением (или жесткое декодирование) означает, что декодер для ДСК использует выход двоичного демодулятора. Эквивалентный ДСК имеет переходную вероятность равную

Заметим, что в данном частном случае, обе оценки вероятности ошибки являются точными, т.е. не оценками сверху, так как используется совершенный код, содержащий только два кодовых слова. Рисунок 9 показывает также, что мягкое декодирование обеспечивает большую эффективность, чем жесткое декодирование, в том смысле, что одинаковое значение P_e(C) при меньшей мощности передачи сигналов. Разность (в дБ) между соответствующими отношениями SNR на бит обычно называют выигрышем от кодирования.

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

                                        (1.35)

Эта граница справедлива только для систематического кода. Кроме того, систематическое кодирование минимизирует вероятность ошибки на бит. Это означает, что систематическое кодирование не только желательно, но и оптимально в рассматриваемом выше смысле.

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

Рис. 10. Моделирование и границы объединения для двоичного (6,3,3) кода при передаче двоичных сигналов в канале с АБГШ.

соответственно. Распределение весов этого кода равно W(C) = {1,0,0,4,3,0,0}, которое может быть проверено непосредственным вычислением для всех кодовых слов v = (u,v_p):

В этом частном случае, МП декодирование состоит в вычислении квадрата Евклидова расстояния по формуле (1.33) между принятым словом и каждым из восьми возможных кодовых слов. В качестве решения выбирается слово с наименьшим расстоянием. На Рисунке 10 показаны результаты моделирования и границы объединения для жесткого и мягкого декодирования по максимуму правдоподобия для передачи двоичных сигналов в канале с АБГШ.

Модель канала с общими Релеевскими замираниями.

Другой важной моделью канала является модель с общими Релеевскими замираниями. Замирания сигналов происходят в системах беспроводной связи в виде меняющихся во времени искажений передаваемых сигналов. В этом пособии рассматриваются только общие замирания (flat fading). Термин «общие» (или «гладкие») означает, что канал не является частотно-селективным, т.е. передаточная функция канала в полосе пропускания равна константе.

Модель канала с покомпонентными мультипликативными искажениями показана на Рисунке 11. Мультипликативные искажения представлены случайным вектором α размерности п, компоненты которого являются независимыми, одинаково распределенными случайными величинами (i.i.d.),  имеющими плотность вероятности Релея,

                                           (1.36)

При такой плотности вероятностей множителей среднее значение отношения сигнал-шум (SNR) на бит равно E_b/N₀ (как и для АБГШ без замираний), так как второй момент коэффициентов замирания равен E{a²_i} = 1.

Рис. 11 Передача двоичных кодированных сообщений в канале с гладкими Релеевскими замираниями

Рис. 12. Двоичная передача по Релеевскому каналу. Результаты моделирования (SIM), оценка границы объединения методом Монте-Карло (Р_е(3,1,3)_МС) и граница Чернова (Р_е(3,1,3)_ЕХР) для двоичного (3,1,3) кода.

Оценки эффективности двоичных линейных кодов в канале с общими Релеевскими замираниями находятся из оценок условной вероятности ошибки декодирования, Р_е(С\α), или условной вероятности ошибки на бит, Р_ь(С\α). Безусловные вероятности ошибки находятся интегрированием условных вероятностей с весами α_i, имеющими плотность вероятности (1.36).

Условные вероятности ошибки идентичны безусловным в канале с АБГШ. Существенное различие имеется только в аргументах функции Q(x), которые теперь взвешены на коэффициенты замирания α_i,. Рассматривая передачу двоичных кодированных сообщений при отсутствии (внешней) информации о состоянии канала, находим, что

                                         (1.37)

где

                                                        (1.38)

Окончательно, вероятность ошибки декодирования при передаче двоичных сигналов в канале с Релеевскими замираниями получается как математическое ожидание относительно случайной величины ∆_w,

                           (1.39)

Известны несколько методов оценивания выражения (1.39). Один из них состоит в применении метода Монте-Карло численного интегрирования с использованием следующей аппроксимации:

                                            (1.40)

где  равно сумме квадратов w независимых одинаково распределенных (i.i.d.) случайных величин с Релеевской плотностью вероятностей (1.38), выданных на -ом обращении к компьютерной программе генерации, и N достаточно большое целое число, зависящее от ожидаемого диапазона значений Р_е(С). Хорошим правилом, которое следует запомнить, является следующее: величина N должна быть, по меньшей мере, в 100 раз больше обратной величины P_e(C).

Другим методом является экспоненциальная аппроксимация сверху функции Q, которая позволяет проинтегрировать выражение или воспользоваться границей Чернова. Этот подход хоть и несколько ухудшает результат, зато дает замкнутое выражение:

                                         (1.41)

Рис.13. Двоичная передача по Релеевскому каналу. Результаты моделирования (SIM_(6,3,3)),°neHKa границы объединения методом Монте-Карло (Р_е(6,3,3)_МС) и граница Чернова (Р_е(6,3,3)_ЕХР) для двоичного (6,3,3) кода.

Граница (1.41) полезна в случаях, когда достаточно знать первое приближение в оценке помехоустойчивости кода.

Пример 11.На Рисунке 12 показаны результаты компьютерного моделирования двоичного (3,1,3) кода в канале с общими Релеевскими замираниями. Заметим, что интегрирование методом Монте-Карло дает точное значение помехоустойчивости кода, так как граница (1.40) содержит только один член. Заметим также, что граница Чернова дает результат, смещенный почти на 2дБ, относительно результата моделирования при отношении сигнал-шум на бит Е_ь/N₀>18 дБ,

Пример 12.На Рисунке 13 показаны результаты компьютерного моделирования двоичного (6,3,3) кода из примера 10 в Релеевском канале. В этом случае граница объединения теряет точность при малых значениях E_b/N₀ из-за присутствия дополнительных членов в формуле (1.40). Как и раньше, граница Чернова проигрывает около 2 дБ в отношении сигнал - шум на бит при E_b/N₀> 18 дБ.

Рис. 14. Общая структура жесткого декодера для линейных блоковых кодов для ДСК.

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

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

В этом разделе проводится итоговое обсуждение структуры декодера с жестким решением. На Рисунке 14 показана упрощенная блок-схема процесса декодирования. Так как обсуждается жесткое решение, то решения демодулятора поступают на вход декодера, рассчитанного на работу с ДСК.

Обозначим v  С переданное кодовое слово. На вход декодера подается принятое искаженное слово r = v + е. Процедура декодирования состоит из следующих шагов:

• Вычисляется синдром s = r Н^T. Согласно свойству линейного кода синдром является линейным преобразованием вектора ошибок, возникшего в канале,

                                                                      (1-42)

•Для вычисленного синдрома s найти наиболее вероятный вектор ошибок е и вычесть его (по модулю два в двоичном случае) из принятого вектора.

Несмотря на то, что большинство практических декодеров не реализуют процедуру декодирования так, как она сформулирована выше, имеет смысл рассматривать процедуру жесткого декодирования как метод решения уравнения (1.42). Заметим, что любой метод решения этого уравнения является методом декодирования. Например, можно попытаться решать это (ключевое) уравнение с помощью псевдо-обратной матрицы (Н^T)⁺ матрицы Н^T такой, что Н^Т(Н^Т)⁺ = I_n и для которой результат декодирования

                                                        (1.42)

имеет наименьший вес Хемминга. Как легко бы это не казалось, задача эта очень сложна. Мы вернемся к этому соображению при обсуждении методов декодирования кодов БЧХ и Рида-Соломона.

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

1. Из каких функциональных блоков состоит функциональная модель канонической цифровой системы передачи информации?

2. Чем понятие кодовая модуляция отличается от понятия помехоустойчивое кодирование?

3. Что понимают под мягким и жёстким способом построения декодера?

4. Имеет ли смысл в одной цифровой системе использовать комбинацию различных кодов исправляющих ошибки?

5. В чём состоит общая идея построения кодов исправляющих ошибки?

6. Что представляет собой кодовое слово систематического блокового кода?

7. В чём разница между блоковыми и сверточными кодами?

8. Поясните смысл понятия минимальное Хеммингово расстояния ?

9. Поясните, какие параметры имеет блоковый код (п, k, d_min).

10. Найдите минимальное Хеммингово расстояние d кода (3,1,d) состоящего из двух кодовых слов (000), (111).

11. Поясните, что называют Хемминговой сферой S_t(v).

12. Поясните, что понимают под корректирующей способностью t блокового кода.

13. Запишите формулу, по которой можно определить какое максимальное количество ошибок может исправить линейный блоковый код С(n,k,d_min) в неверно принятом слове.

14. Какому принципу должно удовлетворять множество кодовых слов, чтобы код обладал свойством помехоустойчивости?

15. Что такое порождающая матрица?

16. Что такое проверочная матрица?

17. Дайте определение веса Хемминга wt_H (x)

18.  Из чего состоит систематическая порождающая матрица G_sys линейного блокового кода (n, к, d_min)?

19. Из чего состоит систематическая форма проверочной матрицы H_sys линейного блокового кода (n, к, d_min)?

20. Как от порождающей матрицы G линейного блокового кода (n, к, d_min) перейти к систематической порождающей матрице G_sys этого же кода?

21. Раскройте смысл понятия скорость кода

22. Имеется двоичный линейный (4,2,2) код с порождающей матрицей запишите систематическую порождающую матрицу G_sys?

23.  Имеется двоичный линейный (4,2,2) код с порождающей матрицей запишите систематическую проверочную матрицу H_sys?

24. Имеется двоичный линейный (4,2,2) код с порождающей матрицей запишите проверочную матрицу P.

25. Какую матрицу лучше использовать в процессе кодирования с точки зрения минимизации логических операций при скорости кода меньше 0.5.

26. Какую матрицу лучше использовать в процессе кодирования с точки зрения минимизации логических операций при скорости кода больше 0.5.

27. Что представляют собой кодовые слова, если при их создании использовались систематические формы матриц.

28. Имеется двоичный линейный (4,2,2) код с порождающей матрицей запишите кодовое слово соответствующее информационному сообщению (00)?

29. Имеется двоичный линейный (4,2,2) код с порождающей матрицей запишите кодовое слово соответствующее информационному сообщению (01)?

30. Имеется двоичный линейный (4,2,2) код с порождающей матрицей запишите кодовое слово соответствующее информационному сообщению (10)?

31. Имеется двоичный линейный (4,2,2) код с порождающей матрицей запишите кодовое слово соответствующее информационному сообщению (11)?

32. Что называют стандартной таблицей (стандартной расстановкой ) для двоичного линейного (n, k, d_min) кода С?

33. Как найти синдром кодового слова?

34. Имеется двоичный линейный (4,2,2) код с проверочной матрицей запишите значение синдрома, если лидер смежного класса равен 1000?

35. Имеется двоичный линейный (4,2,2) код с проверочной матрицей запишите значение синдрома, если лидер смежного класса равен 0100?

36. Имеется двоичный линейный (4,2,2) код с проверочной матрицей запишите значение синдрома, если лидер смежного класса равен 0001?

37. Имеется двоичный линейный (4,2,2) код с проверочной матрицей запишите значение синдрома, если лидер смежного класса равен 0010?

38. Что понимают под лидером смежного класса?

39. Способен ли код (4,2,2) в принципе исправлять ошибки?

40. Какие коды называют кодами с неравной защитой от ошибок?

41. Чему равно количество слов в столбце стандартной таблицы?

42. Что такое область декодирования кодового слова?

43. Как связаны между собой корректирующая способность t кода С и множество столбцов из стандартной таблицы

44. Как определить число синдромов для линейного блокового кода С (n,k,d)?

45. Сформулируйте правило границы Хемминга

46. Имеется двоичный линейный (3,1,3) код с проверочной матрицей  запишите значение синдрома, если лидер смежного класса равен 100?

47. Имеется двоичный линейный (3,1,3) код с проверочной матрицей  запишите значение синдрома, если лидер смежного класса равен 010?

48. Имеется двоичный линейный (3,1,3) код с проверочной матрицей  запишите значение синдрома, если лидер смежного класса равен 001?

49. Имеется двоичный линейный (3,1,3) код с проверочной матрицей  запишите значение синдрома, если лидер смежного класса равен 000?

50. Какие коды называются совершенными?

51. Какие двоичные коды называются кодами Хемминга?

52. Найти распределение весов W(C) для двоичного линейного (4,2,2) кода с набором кодовых слов (0000), (0110), (1011), (1101)?

53. Дайте определение распределения весов W(С) кода С?

54. Чему равна вероятность того, что синдром принятого ненулевого искажённого кода равен нулю?

55. Дан двоичный линейный (6,3,3) код с порождающей матрицей  найти кодовые слова соответствующие сообщениям (000) и (001)

56. Дан двоичный линейный (6,3,3) код с порождающей матрицей  найти кодовые слова соответствующие сообщениям (010) и (011).

57. Дан двоичный линейный (6,3,3) код с порождающей матрицей  найти кодовые слова соответствующие сообщениям (100) и (101)

58. Дан двоичный линейный (6,3,3) код с порождающей матрицей  найти кодовые слова соответствующие сообщениям (110) и (111)

59. Вычислить значение синдрома, если лидер класса равен (000001), а порождающая матрица равна

60. Вычислить значение синдрома, если лидер класса равен (000010), а порождающая матрица равна

61. Вычислить значение синдрома, если лидер класса равен (000100), а порождающая матрица равна

62. Вычислить значение синдрома, если лидер класса равен (001000), а порождающая матрица равна

63. Вычислить значение синдрома, если лидер класса равен (010000), а порождающая матрица равна

64. Вычислить значение синдрома, если лидер класса равен (100000), а порождающая матрица равна

65. Найти распределение весов W(C) для кодовой последовательности (000000),(001101), (010011), (011110), (100110), (101011), (110101), (111000)

66. Опишите процедуру декодирования при структуре декодера с жёстким решением и распространением сигнала в канале ДСК

67. Опишите процедуру декодирования при структуре декодера с мягким решением и распространением сигнала в канале АБГШ

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

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

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

Напомним (формула (1.12)), что любое кодовое слово v линейного (n, k, d_min) кода С удовлетворяет уравнению

                                                       (2.1)

Полезная интерпретация этого уравнения состоит в следующем: максимальное число линейно независимых столбцов проверочной матрицы Н кода С равно d_min - 1.

В двоичном случае, для d_min = 3, из (2.1) следует, что сумма любых двух столбцов проверочной матрицы не равна нулевому вектору. Положим, что столбцы Н являются двоичными векторами длины m. Имеется всего 2^m - 1 ненулевых различных столбцов. Следовательно, длина двоичного кода, исправляющего одиночную ошибку, удовлетворяет условию

Это неравенство в точности совпадает с границей Хемминга (1.24) для кода длины п, с п — к= т проверками и исправлением t = 1 ошибок. Соответственно, код, удовлетворяющий этой границе с равенством, известен как код Хемминга.

Пример 13. Для т=3 мы получаем (7,4,3) код Хемминга с проверочной матрицей

Как уже отмечалось, проверочная матрица кода Хемминга обладает тем свойством, что все ее столбцы различны. Если возникает одиночная ошибка на j-ой позиции, 1≤ j ≤ п, то синдром искаженного принятого слова равен j-ому столбцу матрицы Н. Обозначим евектор ошибок, добавленный к кодовому слову в процессе его передачи по ДСК, и предположим, что все его компоненты равны нулю за исключением j-ой позиции, е_j = 1. Тогда синдром принятого слова равен

                                                (2.2)

где h_j- представляет j-ый столбец Н.

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

Из уравнения (2.2) следует, что, если столбцы проверочной матрицы рассматривать как двоичное представление целых  чисел, то значение синдрома равно номеру искаженной (ошибочной) позиции. Эта идея лежит в основе алгоритмов кодирования и декодирования, представленных ниже. Запишем столбцы проверочной матрицы в виде двоичного представления номера (от 1 до n) позиции кодового слова в возрастающем порядке. Обозначим эту матрицу через Н*. Очевидно, что матрице Н* соответствует эквивалентный код Хемминга с точностью до перестановки позиций кодового слова.

Напомним, что проверочная матрица в систематической форме содержит единичную подматрицу I_n-kразмера (п - k)× (п - к) как показано в (1.16). Очевидно, что в матрице Н* столбцы единичной подматрицы I_n-k (т.е. столбцы веса один) размещаются на позициях с номерами, равными степени 2, т.е. 2^z z= 0,1,..., т.

Пример 14.Пусть т = 3. Тогда систематическая (каноническая) проверочная матрица может быть задана в следующем виде

Матрица Н* заданная двоичным представлением целых чисел от 1 до 7 (младший разряд записывается в верхней строке) имеет вид:

где матрица I₃ содержится в столбцах 1, 2 и 4.

В общем случае, для (2^m - 1, 2^т-1-т) кода Хемминга и данного (арифметического) порядка столбцов единичная матрица I_т содержится в столбцах проверочной матрицы с номерами 1, 2,4,..., 2^m-1.

 Кодирование

Процедура кодирования следует из уравнения (1.18). При вычислении проверочных символов p_j для всех 1 ≤ j ≤ m проверяются номера столбцов и те столбцы, номера которых не являются степенью 2, сопоставляются информационным позициям слова. Соответствующие информационные символы включаются в процесс вычисления проверок. Такая процедура кодирования в чем-то сложнее обычной процедуры для систематического (канонического) кода Хемминга. Однако, соответствующая ей процедура декодирования очень проста. Для некоторых приложений этот подход может оказаться наиболее привлекательным, так как обычно декодирование должно быть очень быстрым.

Декодирование

Если кодирование выполнялось в соответствии с матрицей Н*, то декодирование оказывается очень простым. Синдром (2.2) равен номеру позиции, в которой произошла ошибка! После вычисления синдрома s , который рассматривается как целое число s, ошибка исправляется по правилу

                                                                     (2.2)

где выполняется сложение по модулю 2 (т.е. 0+0=0, 1 + 1=0, 0+1=1,1+0=1).

Примечание.Следует заметить, что в расширенном толковании оба варианта кода Хемминга в Примере 14 являются систематическими, так как в обоих случаях известен фиксированный набор позиций кодового слова, на которых значения символов кодового слова всегда совпадают с соответствующими информационными символами. Другими словами, любые перестановки символов кодового слова оставляют код систематическим (в расширенном смысле).

Пример 14 интересен еще и тем, что Н*=РН,т.е. проверочной матрице Н*, полученной перестановкой некоторых позиций, соответствует, как оказывается, линейное преобразование исходной матрицы, где преобразующая матрица имеет вид

Таким образом, проверочная матрица заданного кода может иметь много различных представлений. Если еН^Т = 0, то и еН^ТP^T= 0, где Р любая невырожденная 3×3 матрица. Если еН^Т =s, то и eH^TP^T= sP^T =s*. Следовательно, для заданного линейного кода можно найти такое линейное преобразование его проверочной матрицы, которое окажется наиболее удобным для реализации, без каких-либо изменений самого кода. Эта возможность будет использована, например, при декодировании циклических кодов БЧХ.

Из примера 14 следует еще одно свойство линейных кодов. Пользуясь линейным преобразованием проверочной матрицы можно «назначить» проверочными любые ( n - k) позиций кодового слова, если только соответствующие им столбцы матрицы являются линейно независимыми. Это означает,  что по оставшимся k позициям можно однозначно восстановить все кодовое слово. Такие наборы позиций называются информационными совокупностями. Множество информационных совокупностей используется в процедурах декодирования под общим названием «ловля ошибок».

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

Голей обнаружил, что

Это равенство позволяет предположить возможность существования совершенного двоичного (23,12, 7) кода с t = 3, т.е. кода, способного исправлять до трех ошибок в словах длиной 23 символа. В своей статье Голей привел порождающую матрицу такого двоичного кода, исправляющего до трех ошибок.

Из-за относительно небольшой длины (23) и размерности (12), а также небольшого числа проверок (11), кодирование и декодирование двоичного (23,12,7) кода Голея может быть выполнено табличным методом.

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

Табличное (LUT, look-up-table) кодирование реализуется с помощью просмотра таблицы, содержащей список всех 2¹² = 4096 кодовых слов, которые пронумерованы непосредственно информационными символами. Обозначим и информационный вектор размерности 12 бит и v соответствующее кодовое слово (23 бита). Табличный кодер использует таблицу, в которой для каждого информационного вектора (12 бит) вычислен и записан синдром (11 бит). Синдром берется из таблицы и приписывается справа к информационному вектору.

Операция LUT является взаимно однозначным отображением из множества векторов u на множество векторов v, которое может быть записано в виде

                                 (2.3)

В реализации табличного кодера учтены упрощения, которые следуют из циклической природы кода Голея. Его порождающий полином имеет вид

или в шестнадцатиричной счисления системе С75. Этот полином используется в процедуре "get_syndrome", заданной уравнением (2.3).

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

Напомним, что задачей декодера (Часть 1, Рисунок 14) является оценка наиболее вероятного (т.е. обладающего минимальным Хемминговым весом) вектора ошибок е по принятому вектору r.

Процедура построения табличного LUT-декодера состоит в следующем:

Выписать все возможные вектора ошибок е, вес Хемминга которых не превышает трех;

Для каждого вектора ошибок вычислить соответствующий синдром s=get_syndrome(e);

Записать в таблицу для каждого значения s соответствующий ему вектор е, так что

Исправление до трех ошибок в принятом искаженном слове r с помощью LUT-декодера может быть представлено следующим образом:

где v" — исправленное кодовое слово.

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

В этом разделе рассматривается процедура декодирования расширенного (24,12,8) кода Голея С₂₄, реализующая арифметический алгоритм декодирования. Этот алгоритм использует строки и столбцы подматрицы В проверочной матрицы Н=(В, I₁₂). Заметим, что (24,12,8) код Голея, эквивалентный с точностью до перестановки отдельных позиций коду С₂₄, может быть построен добавлением общей проверки на четность к кодовым словам (23,11,7) кода Голея.

Двенадцать строк подматрицы В, обозначенные как row_i, 1 ≤ i < 12, имеют следующий вид в шестнадцатеричной системе:

Важно отметить, что подматрица В проверочной матрицы кода С₂₄ удовлетворяет равенству В = В^т, т.е. транспонированная и исходная матрицы совпадают. Это означает, что код С₂₄ является самодуальным кодом. Дуальным кодом называют код, использующий проверочную матрицу исходного кода в качестве порождающей.

В программе golay24.c кодирование реализуется рекуррентно, по правилу (1.18). Как и раньше, через wt_H(x) обозначен вес Хемминга вектора х. Процедура декодирования состоит в выполнении следующей последовательности шагов:

1. Вычислить синдром s = rН^T.

2. Если wt_H(s) ≤ 3, то исправляющий вектор равен е = (s, 0), перейти к шагу 8.

3. Если wt_H(s + row_i) ≤ 2, для 1 ≤ i≤ 12, то исправляющий вектор равен е = (s + row_i, х_i), где х_i вектор длины 12, содержащий 1 в i-ой координате и нули в остальных. Перейти к шагу 8.

4. Вычислить sB.

5. Если wt_H(sB) ≤ 3, то исправляющий вектор равен е = (0, sB), перейти к шагу 8.

6. Если wt_H(sB + row_i) ≤ 2, для некоторого i, 1 ≤i ≤12, то исправляющий вектор равен е = (х_i, sB + row_i), где х_i вектор длины 12, содержащий 1 в i-ой координате и нули в остальных. Перейти к шагу 8.

7. Если ни одно из условий шагов 2 - 6 не было удовлетворено, то вектор r содержит неисправимое сочетание ошибок и устанавливается флаг «отказ от декодирования». Конец процедуры.

8. Вычислить с = r + е. Конец процедуры.

Примичание. Эта процедура имеет очень простое объяснение. Кодовое слово длиной 24 символа состоит из информационной части (12) бит и проверочной части (12) бит. Если все ошибки находятся только в проверочной части, то вес синдрома равен числу ошибок. Если этот вес не превышает трех, то декодер принимает на шаге 2 процедуры декодирования однозначное решение о том, что вектор ошибок совпадает с синдромом.

На шаге 3 проверяется предположение о том, что одна (именно одна) ошибка находится на i-ой позиции в информационной части принятого слова. Для правильного выбора i прибавление row_i к синдрому компенсирует вклад этой ошибки в синдром, после чего вес измененного синдрома будет равен 2 или 1. На основании этого декодер принимает однозначное решение о том, что исправляющий вектор равен конкатенации (соединению) вектора x_i с измененным синдромом. В противном случае, число ошибок возрастет, вес синдрома не удовлетворит условию. Разумеется, может оказаться, что какое-то другое слово расположено на расстоянии не более 2 от измененного слова при условии, что в принятом слове больше трех ошибок.

На шагах 4—6 процедуры выполняются такие же проверки в предположении, что, либо все ошибки, либо все кроме одной, находятся в информационной части принятого слова. Для этого используется следующее линейное преобразование проверочной матрицы:

которому соответствует преобразование синдрома, равное sB.

Справедливость этого преобразования следует из равенства ВВ = I₁₂, которое легко можно проверить. Другими словами, с помощью этого преобразования, с точки зрения декодера, меняются местами  информационные и проверочные позиции кодового слова, хотя никакие изменения с самим кодом не происходят.

Рассмотренная идея использована в некоторых алгоритмах декодирования, близкого к максимуму правдоподобия.

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

Двоичные коды Рида-Маллера (РМ) составляют семейство кодов, исправляющих ошибки, с простым декодированием, основанным на мажоритарной логике. Кроме того, известно, что коды этого семейства имеют очень простые и хорошо структурированные решетки.

Известно элегантное определение двоичных РМ кодов, основанное на двоичных полиномах (или Булевых функциях). Согласно этому определению, РМ коды становятся близкими к кодам БЧХ и PC, которые входят в класс полиномиальных кодов.

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

Обозначим f(x₁, х₂,..., х_т) Булеву функцию от т двоичных переменных x₁, х₂,..., х_т. Известно, что такие функции легко представить с помощью таблицы истинности. Таблица истинности содержит список значений функции f для всех 2^т комбинаций значений ее аргументов. Все обычные Булевы операции (такие как «и», «или») могут быть представлены как Булевы функции.

Пример 15.Рассмотрим функцию f(х_1,х₂), заданную следующей таблицей истинности:

Тогда

Ассоциируем с каждой Булевой функцией f двоичный вектор f длины 2^т, составленный из значений данной функции для всех возможных комбинаций значений т ее аргументов. В последнем примере f=(0110), где принято соглашение о лексикографическом (иначе, арифметическом) упорядочении значений аргументов функции, таком, что x₁ представляет младший разряд, a x_m- старший разряд.

Заметим, что Булева функция может быть записана прямо по таблице истинности с помощью дизъюнктивной нормальной формы (ДНФ). В терминах ДНФ любая Булева функция может быть записана как сумма 2^m элементарных функций: 1, х₁, х₂, …x_m, x₁ х₂,..., х₁х_m,..., х₁х₂..х_m такой что

  (2.4)

где вектор 1 добавлен для того, чтобы учесть свободный член (степени 0). В примере 15 f=x₁+x₂.

Двоичный (2^т, k, 2^т-r) РМ код, обозначенный РМ_r,m, определяется как множество векторов, ассоциированных со всеми Булевыми функциями степени до r, включительно, от mпеременных. Код PM_r,m называют также кодом РМ r-ого порядка длины 2^т. Размерность РМ_r,m кода, как легко может быть показано, равна

Это число равно числу способов, которыми могут быть построены полиномы степени rили меньше от mпеременных.

С учетом уравнения (2.4) строками порождающей матрицы РМ_r,m кода являются вектора, ассоциированные с kБулевыми функциями, которые могут быть записаны как полиномы степени rили меньше от m переменных.

Пример 16.Код РМ первого порядка длины 8, PM_1,3, является двоичным (8,4,4) кодом, который может быть построен из Булевых функций степени 1 от 3 переменных: {1, х₁, х₂, х₃}.Таким образом,

Порождающая матрица РМ_1,3 кода имеет, следовательно, вид

                                 (2.5)

Заметим, что код PM_1,3 может быть построен также и из кода Хемминга (7,4,3) добавлением общей проверки на четность. Расширенный код Хемминга и РМ_1,3 код могут отличаться только порядком позиций (столбцов).

Дуальные коды кодов РМ также являются кодами РМ

Можно показать, что РМ_m-r-1, _т код дуален коду PM _r,m. Другими словами, порождающая матрица РМ_m-r-1,ткода может быть использована как проверочная матрица PM _r,m кода.

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

Определение кодов РМ может быть дано и в терминах конечных геометрии. Евклидова геометрия, EG(m,2), размерности т над GF(2) содержит 2^т точек, которые представляют собой все двоичные вектора длины т. Заметим, что столбцы матрицы, образованной последними тремя строками порождающей матрицы PM_1,3 кода, см. Пример 16, представляют собой 8 точек EG(3,2). Удалением нулевой точки это множество точек преобразуется в проективную геометрию PG(m-1,2). Коды над конечными геометриями являются по существу обобщением кодов РМ.

Связь между кодами и конечными геометриями можно объяснить следующим образом. Возьмем EG(m,2). Столбцы матрицы (x^T₁ , х^т₂ … х^т_m)^т (где Т - операция транспонирования матрицы) рассматриваются как координаты точек геометрии EG(m,2). Тогда имеет место взаимно однозначное соответствие между компонентами двоичного вектора длины 2^т и точками EG(m,2). Заданный двоичный вектор длины 2^т ассоциируется с подмножеством точек EG(m,2). В частности, подмножество EG(m,2) может быть ассоциировано с двоичным вектором w = (w₁ , w₂, …, w_n) длины п=2^т, если интерпретировать значение его координат w_i =1 как выбор точки. Другими словами, w является вектором инцидентности (совпадений).

Теперь двоичный код Рида-Маллера можно определить следующим образом: кодовыми словами PM_r,m кода являются вектора инцидентности всех подпространств (т.е. линейных комбинаций точек) размерности т-r в EG(m,2) Из этого определения следует, что число кодовых слов минимального веса РМ_r,m кода равно

                                          (2.6)

Код, который получается после удаления (перфорации) координат, соответствующих условию х₁ = х₂ = ... = х_m = 0, из всех кодовых слов PМ_r,m кода является двоичным циклическим РМ*_r,m кодом. Число слов минимального веса циклического РМ кода равно

                                            (2.7)

Декодирование РМ кодов может быть выполнено на основе мажоритарной логики (МЛ). Идея мажоритарного декодирования состоит в следующем. Как известно, проверочная матрица порождает 2^п-к проверочных уравнений. Построение МЛ декодера сводится к выбору такого подмножества проверочных уравнений, чтобы решение о значении кодового символа на определенной позиции формировалось по большинству «голосов», причем каждый «голос» связан с одним из проверочных уравнений. В качестве иллюстрации рассмотрим код РМ_1,3 из Примера 16.

Пример 17.Пусть вектор является кодовым словом кода PM_1,3. Как уже упоминалось ранее, выражение (2.5) определяет порождающую, а также и проверочную матрицу PM_1,3 кода, поскольку в данном случае r= 1 и m-r-1=1 и, следовательно, код является самодуальным. Все возможные ненулевые линейные комбинации (всего 15) проверочных уравнений (строк проверочной матрицы Н) имеют вид:

                                             (2.8)

Читателю предлагается проверить, что сумма v_i + v_j любой пары кодовых символов v_i и v_jпоявляется точно в четырех уравнениях. Более того, в уравнениях, которые содержат одинаковую сумму (v_i + v_j), любые другие суммы пар появляются не более одного раза (т.е. не более чем в одном уравнении). Такие проверочные уравнения называют ортогональными относительно пары символов v_i и v_j.

Покажем теперь способ исправления одиночной ошибки. Пусть в результате передачи кодового слова v по ДСК получен вектор

r = v + e = ( r₁, r₂, r₃, r₄, r₅, r₆, r₇, r₈)

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

Выберем два уравнения, включающие сумму v_i + v₅, i≠ 5, и два других уравнения, содержащие сумму v_j+ v₅, j≠5 , i≠j. Примем, например, i = 3 и j = 4. Имеется четыре проверки ортогональные сумме v₃ + v₅. Выберем любые две из них. Выполним тоже самое для суммы v₄ + v₅. Ассоциированные с выбранными проверками синдромы обозначим S₁ и S₂ для суммы v₃ + v₅, а также S₃ и S₄ для суммы v₄ + v₅. В результате имеем:

                                                              (2.9)

Так как вектор v является кодовым словом PM_1,3 кода, то система уравнений (2.9) эквивалентна следующей

                                                           (2.10)

Поскольку проверки S₁ S₂, S₃, S₄ ортогональны относительно е₃ + е₅ и е₄ +e₅ , то может быть построена новая пара уравнений ортогональных относительно е₅.

                                                                 (2.11)

где e'_j, j = 3, 4, 5, представляют мажоритарные оценки, полученные из уравнений (2.9). Уравнения (2.11) ортогональны относительно е'₅ и, следовательно, значение е'₅ может быть получено голосованием. Например, в данном случае это может быть результат операции «И» с входами S’₁ и S'₂

Предположим, что передавалось слово v = (111 10000) и было принято слово r = (11111000). Тогда из (2.10) получаем

                                                             (2.12)

Таким образом, оба терма е₃ + e₅ и е₄ + е₅ оцениваются равными «1». Из (2.11) получаем оценку е₅ = 1 и оценку исправляющего вектора е = (00001000). Окончательно, оценка переданного слова равна v = r + е = (11110000). Таким образом, продемонстрирован двух шаговый способ мажоритарного исправления одной ошибки на пятой позиции.

В предыдущем примере было показано, как исправляется одна ошибка в заданной позиции для кода PM_1,3 Аналогичная процедура может быть применена к любой позиции принятого слова. Следовательно, могут быть получены и все восемь мажоритарных оценок для каждого символа.

В общем случае код РМ_r,m может быть декодирован (r + 1) -шаговой мажоритарной процедурой декодирования с исправлением любой из возможных комбинаций случайных ошибок веса |_(2^{m - 2} - 1) / 2_| или меньше .

Дополнительно заметим, что циклический код РМ*_r,m декодируется несколько проще. В циклическом коде С, если (v₁, v₂,..., v_n) любое кодовое слово, то и его циклический сдвиг (v_n, v₁, ... , v_n-1) тоже кодовое слово. Отсюда следует, что, если некоторая позиция может быть декодирована по мажоритарному методу, то и все n позиций будут декодированы тем же самым способом с использованием циклического сдвига.

Пример 18. В этом примере рассматривается декодер циклического PM*_1,3 кода, который совпадает с двоичным (7,4,3) кодом Хемминга. Для того, чтобы получить проверочные уравнения циклического кода из проверок PM_1,3 кода, достаточно удалить во всех уравнениях координату v₁, для которой x₁ = х₂ =...= х_m. После удаления v₁ изменим нумерацию позиций PM*_1,3 кода следующим образом:

Как и раньше, можно построить мажоритарный декодер для произвольной позиции (например, пятой), учитывая семь линейно независимых проверочных уравнений:

                                             (2.13)

По аналогии с предыдущим примером находим, что синдромы S₁ и S₂ ортогональны относительно символов v₄ и v₅, а S₂ и S₃ ортогональны относительно v₅ и v₆:

                                              (2.14)

Используя промежуточные оценки сумм v₄ + v₅ и v₅ + v₆, получаем дополнительно два ортогональных уравнения относительно v₅:

    (2.15)

где e'_j, j = 4, 5, 6, обозначены мажоритарные оценки, полученные на предыдущем шаге. Этот алгоритм представлен на Рисунке 15 в виде логической схемы.

Эта схема работает следующим образом. Начальное состояние семи ячеек регистра памяти устанавливается нулевым. Предположим, что принятое слово содержит ошибку в позиции с номером i, 1 ≤ i ≤ 7. На каждом такте содержимое регистра памяти сдвигается вправо на одну позицию. Время в тактах представлено на схеме нижним индексом.

Рис. 15.Мажоритарный декодер циклического кода РМ*(1,3)

Рассмотрим случай i = 1. Это означает, что ошибка находится в первой позиции принятого слова. Через три такта эта ошибка переместится в пятую ячейку регистра (v₅). Выход мажоритарной логической схемы примет состояние е_п = 1. Еще через четыре такта (на седьмом такте) первый принятый символ попадет на выход декодера и будет исправлен. Рассмотрим теперь случай i = 7. Через девять тактов ошибка будет обнаружена и выход мажоритарной схемы примет значение е_п = 1. Спустя четыре такта (т.е. на тринадцатом такте) последний символ поступит на выход декодера и будет исправлен. Декодер, который здесь рассматривается, имеет задержку 13 тактов. Через 13 тактов содержимое регистра стирается и начинается обработка нового принятого слова.

В следующей части рассматриваются циклические коды и обширное семейство БЧХ кодов.

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

Какие коды называются самодуальными?

Запишите параметры (n,k,d) двоичного кода Голея.

Что значит понятие систематический код в расширенном смысле?

Мы поможем в написании ваших работ!