Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

3.4. Коды Рида-Маллера

Коды Рида-Маллера образуют класс двоичных линейных кодов с простым описанием и декодированием, осуществляемым методом простого голосования. Длина кодового слова в коде Рида-Маллера равна 2m, где m ≥ 2. Задавать код удобно порождающей матрицей.

Для задания порождающей матрицы кода определим покомпонентное произведение двух двоичных векторов a и b. Если a= (a0, a1, ..., an-1) и b= (b0, b1, ..., bn-1), то их произведение равно вектору ab= (a0b0, a1b1, ..., an-1bn-1).

Порождающая матрица кода Рида-Маллера r-го порядка, r m, с длиной кодового слова 2m строится как совокупность блоков G0, G1, ..., Gr, где G0 - матрица, содержащая единственную строку из одних единиц. Блок G1 есть (m × 2m)-матрица, содержащая в качестве столбцов все двоичные последовательности длины m. Строки матрицы Gj, j r, получаются как все возможные произведения j строк из матрицы G1. Таким образом, для кода Рида-Маллера порядка r число информационных символов равно 1 + Cm1 + ...+ Cmr, Можно показать, что строки построенной матрицы являются линейно независимыми и определить расстояние кода, для которого данная матрица является порождающей.

Теорема 3.3. Кодовое расстояние кода Рида-Маллера порядка r с длиной кодового слова 2m есть d = 2m- r .                                               

Приведенная ниже матрица является порождающей матрицей для кода Рида-Маллера для m = 3, r = 1.

Известно, что для любых целых m ≥ 2 и r < m существует код Рида-Маллера с длиной кодового слова  2m, который называется кодом Рида-Маллера r-го порядка длины 2m. Процедура кодирования для кодов Рида-Маллера такая же, как для всех линейных кодов, т. е. совпадает с процедурой, описанной в главе 2. Для кода Рида-Маллера порядка 1 и длины 4, порождающая матрица которого приведена выше, рассмотрим информационное слово i = 0110. Данное слово преобразуется в кодовое слово v = iGT = 00111100.

Процедура исправления ошибок для кодов Рида-Маллера отличается от процедуры, описанной в главе 3, и происходит по мажоритарному принципу. Мы далее обозначаем  ai1i2...il информационный символ, на который умножается вектор vi1vi2...vil в порождающей подматрице Gl, и называем этот символ информационным символом l-го порядка. Таким образом, информационный символ aj1...jk  соответствует базисному вектору, который есть произведение  строк j1, ..., jk матрицы G1.

Процедура исправления ошибок начинается с нахождения символов старшего порядка, т. е. символов r-го порядка. Имеет место следующая теорема:

Теорема 3.4. Каждый из Cmr информационных символов порядка r кода Рида-Маллера можно представить в точности 2m-r различными способами в виде сумм 2r компонент кодового слова, так, что каждое слагаемое входит только в одну сумму.

В каждое проверочное соотношение подставляются соответствующие компоненты принятого слова. Если при передаче произошло не более чем 2m-r-1 - 1 ошибок, то переданное значение информационного символа можно вычислить простым голосованием. Мы далее покажем, каким образом проверочные суммы строятся для каждого информационного символа.

После того, как декодированы информационные символы r-го порядка, находится линейная комбинация вектор-строк подматрицы Gr с вычисленными коэффициентами. Полученная линейная комбинация вычитается, т. е. складывается по модулю 2, с принятым словом, и начинается декодирование информационных символов порядка r -1 и т. д.

Рассмотрим порождающую матрицу кода Рида-Маллера порядка 1 для m = 3. Длина кодового слова равна 8, и порождающая матрица имеет следующий вид:

Пусть информационное слово имеет вид a0a1a2a3. Для кодового слова v = v1...v8 и информационного символа a1, который соответствует первой строке матрицы G1, получим следующие 4 суммы: a1 = v1 + v5, a1 = v5 + v7, a1 = v2 + v6 и a1 = v4 + v8. Если в принятом слове произошла одна ошибка, то она повлияет только на одно из соотношений, т. е. правильное значение переданного символа a1 можно вычислить по значению остальных трех сумм. Так как расстояние данного кода равно 23 - 1 = 4 (теорема 4.3), то код исправляет только одну ошибку.

Пусть было передано кодовое слово 00111100, которое соответствует информационному слову 0110, и при передаче произошла ошибка в 4-м разряде, т. е. принято слово 00101100. Проверочные суммы для символа a1 суть: v1 + v5 = 1, v3 + v7 = 1, v2 + v6 = 1 и v4 + v8 = 0. Таким образом, a1 = 1.

Построим проверочные суммы для информационного символа a2: a2 = v1 + v3, a2 = v2 + v4, a2 = v5 + v7 и a2 = v6 + v8. Для принятого слова значения трех сумм равно 1, т.е. a2 = 1. Проверочные суммы для информационного символа a3 суть: a3 = v1 + v2, a3 = v3 + v4, a3 = v5 + v6 и a3 = v7 + v8. Для принятого слова значения трех сумм равно 0, т. е. a3 = 0.

Находим линейную комбинацию 00111100 вектор-строк подматрицы G1 с коэффициентами 1, 1, 0 и сумму 00010000 по модулю 2 полученной линейной комбинации с принятым словом 00101100. По полученному слову u = u1...u8 вычислим информационный символ по соотношениям: a0 = u1 = ...= u8. По принципу голосования получаем, что a0 = 0. Таким образом, переданное информационное слово равно 0110.

Опишем алгоритм построения проверочных сумм для информационных символов. Алгоритм основан на построении парных компонент для каждой строки матрицы G1.

В строке с номером i, i = 1, ..., m, матрицы G1 компоненты с номерами p и t, называются парными, если t = p + 2m-i. Множество пар парных компонент образует разбиение множества номеров всех компонент, т. е. разбиение множества {1, ..., 2m}. Разбиение на парные компоненты для i-й строки матрицы G1 будем обозначать pi.

Пусть p1 и p2 - разбиение некоторого множества М. Наименьшее разбиение М, содержащее p1 и p2, называется эквивалентным замыканием p1 и p2, и обозначается p1 + p2. Любые два элемента, содержащиеся в одном блоке разбиения p1 или p2, находятся в одном блоке разбиения p1 + p2. Любое другое разбиение t, обладающее данным свойством, больше разбиения p1 + p2, т. е. любой блок разбиения t является подмножеством подходящего блока разбиения t. Операция эквивалентного замыкания естественным образом распространяется на k разбиений pj1,..., pjk.

При построении проверочных сумм ля информационного символа aj1...jk  , k < m, строк матрицы G1, строятся разбиения pj1,..., pjk множества {1, ..., 2m} на парные компоненты для вектор-строк j1, ..., jk матрицы G1.Каждый блок эквивалентного замыкания pj1 + p j2 + p j3 + ...  + p jk задает проверочную сумму.

В качестве примера рассмотрим порождающую матрицу кода Рида-Маллера порядка 2 для m = 4. Длина n кодового слова в этом случае равна 16. Порождающая матрица кода имеет следующий вид:

(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) =v0    
(0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1) =v1    
(0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1) =v2    
(0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1) =v3    
(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) =v4    
(0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1) =v1v2
(0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1) =v1v3
(0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1) =v2v3
(0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1) =v1v4
(0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1) =v2v4
(0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1) =v3v4


Запишем проверочные суммы для информационного символа a12. Разбиения p1 и p2 на парные компоненты суть: p1 = {{1, 9}, {2, 10}, {3, 11}, {4, 12}, {5, 13}, {6, 14}, {7, 15}, {8, 16}} и p2 = {{1, 5}, {2, 6}, {3, 7}, {4, 8}, {9, 13}, {10, 14}, {11, 15},      {12, 16}}. Эквивалентное замыкание p1 и p2 есть разбиение  p12 =  {{1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15}, {4, 8, 12, 16}}. Таким образом, проверочные суммы для информационного символа  a12 суть: a12 = v1 + v5 + v9 + v13, a12 = v2 + v6 + v10 + v14, a12 = v3 + v7 + v11+ + v15, a12 = v4 + v8 + v12 + v16.