3.1. Параметры кода

Коды Рида-Маллера (РМ-коды) представляют собой двупараметрическое семейство блочных кодов с целыми неотрицательными параметрами m и r, для которых: 0 <= r < m. Характеристики РМ-кода: длина n = 2^m; размерность k=С_n⁰+С_n¹+….+С_n^r, минимальное кодовое расстояние d = 2^m-r, количество гарантированно исправляемых ошибок t = 2^m-r-1-1.

При построении кодирующей матрицы будем использовать операцию побитового произведения векторов: x = (a₁b₁, … , a_nb_n), где = (a₁, a₂, ... a_n), = (b₁, b₂, ... b_n). Очевидно, что x = x.

Кодирующую матрицу G для параметров m и r определим как блочную матрицу вида: G = (G₀| G₁| …| G_r|)^T, где G_i – специальная (C_mⁱxn)-матрица. Именно, G₀ = (1, 1, … , 1). В качестве столбцов матрицы G₁ взяты все двоичные слова длины m, записанные в их естественном порядке. Матрица G₁ имеет размерность C_m² ? 2^m.

Матрица G₂ строится из строк матрицы G₁ следующим образом: рассматриваются всевозможные побитовые произведения пар строк матрицы G₁ и полученные результаты записываются как строки матрицы G₂, причем порядок записи строк матрицы G₂ несущественен, но обычно применяется лексикографическое упорядочение. Матрица G₂ имеет размерность C_m² ? 2^m. Для любого l матрица G_l строится по аналогии с G₂: рассматриваются всевозможные наборы по l строк матрицы G₁ и для них вычисляются l-кратные побитовые произведения. Из полученных в результате новых строк формируется матрица G_l размерности C_m^l x 2^m. Порядок записи строк матрицы Gl несущественен, но обычно применяется лексикографическое упорядочение. Отметим, что все строки матрицы G линейно независимы.

Пример 3. Рассмотрим m = 4, n = 2⁴ = 16 и построим все блоки кодовой матрицы Рида-Маллера:

Для конкретного значения параметра r из этих блоков строится кодирующая матрица G = (G₀| G₁| …| G_r|)^T.

3.2. Кодирование

Для кодов Рида-Маллера кодирование можно осуществлять простым умножением на кодирующую матрицу. Пример 4. Рассмотрим случай m = 3, r = 1, n = 2³-1 = 7, k=C₃⁰+C₃¹ = 4. Тогда кодирующая матрица имеет вид:

Закодируем слово (1010): (1010)G =(11001100).

3.3. Мажоритарный декодер Рида

Отличительной особенностью декодера Рида является то, что по полученному из канала зашумленному кодовому слову восстанавливается не истинное кодовое слово , а непосредственно сообщение . Искомый информационный вектор =(1,…, k) представляется в блочном виде (₍₀₎, ₍₁₎, ... _(r)), длина j-того блока равна С_m^j. Декодирование производится по блокам справа налево, и при декодировании каждого следующего блока используются полученные ранее результаты.

Если r = 0, то РМ-код является кодом n-кратного повторения и декодирование производится обычным мажоритарным способом. Для остальных r построим последовательность алгоритмов, назовем их i-алгоритмами, которые позволяют декодировать i-тый блок сообщения и передавать управление на (i-1)-алгоритм.

i-Алгоритм.

1) Рассмотрим пришедшее по каналу слово GFⁿ(2) и представление (₍₀₎, ₍₁₎, ... _(r)) префикса информационного вектора .

2) Анализ кодовой матрицы показывает, что биты кодового слова представляют собой суммы некоторых битов информационного слова. Биты блока _(i) будем восстанавливать справа налево. Для восстановления бита _s блока построим контрольные суммы _p, р = 1, 2, …, 2^m-i, по 2ⁱ слагаемых, состоящих из битов кодового слова, таким образом, чтобы все информационные символы, отличные от _s, входили четное число раз в каждую контрольную сумму, а искомый информационный символ _s входил в эту сумму нечетное число раз. Следовательно, при отсутствии ошибок все суммы _p должны совпадать между собой и совпадать с _s. (Генерирование систем контрольных сумм в общем случае является трудной задачей, для конкретных значений параметров эти системы будут указаны в примерах. Вопросы программной реализации генерирования систем контрольных сумм рассмотрены А. Шамшиным [3] и В. Мкртичаном [4].) Вычислим по битам слова значения _p, р = 1, 2, …, 2^m-i. При условии, что ошибок на блок сделано не более чем 2^m-r-1-1, простое голосование позволяет из набора _p выбрать правильное значение для _s. Проводя такие вычисления для каждого бита блока _(i), восстанавливаем весь блок.

3) После восстановления блока _(i) проводим редукцию к (i-1)-алгоритму. А именно полагаем, что по каналу получено слово ' = - _(i)G_i и применим (i-1)-алгоритм для декодирования блока _(i-1).

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

Пусть m = 4, r = 2. Вычислим параметры кода: длина n = 16, размерность k = 11, минимальное кодовое расстояние d = 4, количество гарантированно исправляемых ошибок t = 1.

Пусть = (01101011010) исходное информационное слово. Закодируем его = G = (0101111111000110). Пусть на выходе канала получено слово = (0111111111000110). Декодируем полученное слово .

= (a₁, a₂, ... a₁₁); = G =(0101111111000110)

Символы a₆,…..a₁₁ декодируем с помощью 2-алгоритма..

Составим контрольные суммы

Проводим редукцию к 1-алгоритму: ' = - (011010)G₂ = (0111111111000110)- (0000010101100011) = (0111101010100101). К слову ' применим декодер 1-го порядка. Результат: a₅ = 1, a₄ = 0, a₃ = 1, a₂ = 1. Осталось декодировать последний символ. Вычислим новое слово '' = ' - (a₂, a₃, a₄, a₅)G₁ = (0111101010100101) – (1101)G₁ = (0111101010100101) – (0101101010100101) = (0010000000000000). Следовательно, a₁ = 0.

Информационное слово имеет вид (01101011010).

3.4. Упражнения

1. Составьте двоичное четырехбитное слово. Полученное слово закодируйте кодом Рида-Маллера с параметрами m = 3, r = 1.

2. Составьте двоичное слово из следующих значений: Ваше число (5 битов) и месяц (4 бита) рождения, Ваш возраст (5 бит), наличие у Вас младших сестры или брата (1-да, 0-нет), наличие у Вас старших сестры или брата (1-да, 0-нет). Полученное слово закодируйте кодом Рида-Маллера с параметрами m = 5, r = 2.

а) Внесите в кодовое слово одну ошибку и декодируйте рaезультат.

б) Внесите в кодовое слово число гарантированно исправляемых этим кодом ошибок и декодируйте результат.