3.12. Код Рида — Маллера

Коды Рида-Маллера (Маллер открыл коды, построил декодирующую схему) образуют класс двоичных систематических кодов, имеющих различные значения избыточности и значения минимальных кодовых расстояний Эта коды характеризуются следующими значениями параметров [130]: длина кода количество информационных разрядов

минимальное кодовое расстояние

где -любое целое положительное число; порядок кода.

Пример. Если то 8 может принимать значения 1, 2, 3. Определить параметры кода.

Для

Таблица 23 (см. скан)

(см. скан)

Продолжение табл. 24 (см. скан)

Таким образом, в зависимости от порядка кода можно получить коды (16,5), (16, 11), (16,15), характеризующиеся различными значениями избыточности и значениями минимального кодового расстояния. В табл. 24 приведены параметры кодов Рида — Маллера до

Построение кодов Рида — Маллера сводится к следующему. Вначале строится производящая матрица С, первая строка которой содержит единиц. Далее следует строк, совокупность которых удобно рассматривать как -матрицу, в качестве столбцов которой выбраны двоичные числа (начиная с нуля). Номера разрядов двоичных чисел удобно считать сверху вниз. Эти строк составляют векторы первого порядка 6. Далее идут строки векторов второго порядка, которые получаются из всех произведений двух строк первого порядка, затем — строки третьего порядка, являющиеся всеми произведениями трех строк первого порядка, и т. д.

Таким образом, если строится матрица для кода порядка 6, то она содержит одну строку со всеми единицами, строк первого порядка, строк второго порядка, строк третьего порядка и т. д. В общем случае количество строк и совпадает с количеством информационных разрядов

Пример. Построить матрицу для кода Рида — Маллера второго порядка Первая строка содержит единиц (11111111).

Строим матрицу строк первого порядка

Для дальнейшего построения етрок необходимо иметь в виду, что, если перемножаются строки, например и 00110011, результат получается путем поразрядного перемножения строк

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

Полиостью построенная матрица для кода Рида — Маллера второго порядка и имеет вид

Производящую матрицу кода Рида — Маллера можно привести к виду для того, чтобы декодирование производить методами, присущими всем систематическим кодам.

Важнейшее свойство кодов Рида-Маллера состоит в том, что декодирование для них проводится простым способом. В этих кодах каждый из информационных символов может быть описан не менее чем независимыми проверочными уравнениями, аргументами которых являются символы кодового слова. Анализ результатов решения этих уравнений по принципу большинства позволяет определить значение информационных символов Тем самым при исправлении ошибок исключается этап определения места ошибок, как это имело место в кодах Хэмминга. Поэтому в кодах Рида — Маллера можно использовать мажоритарный принцип декодирования

Простота структуры производящей матрицы С этих кодов позволяет установить связь между информационными символами и символами кодового слова Это легко показать на примере. Рассмотрим код второго порядка для Это код (16, 11), одиннадцать информационных символов которого кодируются с помощью производящей матрицы имеющей вид

Матрица образуется с помощью векторов построенных указанным ранее способом и их произведений. В (3.40) показано также «соответствие» между информационными символами векторами

Кодовый вектор (закодированные информационные символы) имеет вид

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

Например, из приведенной матрицы следует, что

Эти соотношения позволяют закодировать сообщение по известным информационным символам. Предположим, что исходное сообщение имеет вид 10001011011. Тогда закодированное сообщение (кодовый вектор) выглядит как 1111101001101100. Соотношения для определения информационных символов из кодового вектора можно получить, решая уравнения (3.41) относительно т. е. определить

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

На основании этого можно записать проверочное соотношение

В справедливости этого равенства можно убедиться, подставляя в него значения из (3.41). Получим так как входят в правую часть

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

Таким образом, из матрицы получено четыре независимых уравнения:

В общем случае для каждого и должно быть не менее независимых уравнений. Суммы, каких именно символов кодового слова должны быть равны информационному символу можно определить следующим образом. Назовем компоненту, соответствующую нулю в векторе и компоненту, соответствующую единице в векторе парными компонентами. Например, для векторов матрицы (3.40) парные компоненты показаны на рис. 15. Тогда сумм парных

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

Рис. 15. Парные компоненты для векторов первого порядка.

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

На рис. 16 показаны парные компоненты (см. матрицу 3.40), используемые для определения соответствующих информационных символов. Для этих парных компонент

Аналогично каждое соотношение для является суммой некоторых парных компонент вектора сложенной с суммой компонент вектора парных к этим компонентам, и с суммой компонент вектора парных к уже выбранным компонентам, так что в каждой сумме получается всего восемь слагаемых. Например, вектор х имеет вид 0000000100000001. Из рис. 16 определяем компоненты и выбираем парные компоненты для Получаем рис. 17, из которого видно, что для вектора имеет следующие проверочные соотношения:

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

(кликните для просмотра скана)

информационными символами и символами кодового вектора, но при этом сначала записываются уравнения для соответствующие векторам наивысшего порядка 8, затем — порядка

Пример. Закодированное кодом Рида-Маллера (16, 11) сообщение имеет вид . Определить исходное сообщение. Воспользовавшись любыми из соотношений (3.43), определим для векторов второго порядка:

Нами найдены информационные символы (коэффициенты, соответствующие векторам второго порядка Дальше определять информационные символы по формулам (3.42) нельзя, так как выполняются не все соотношения. Это объясняется тем, что они выведены только для матрицы, содержащей векторы первого порядка и не выполняются для всей матрицы (с учетом векторов второго порядка). Действительно, например, согласно Складывая соответствующие столбцы матрицы кода (16, 11), получаем единицу не только в разряде, соответствующем но и в других разрядах. Поэтому закодированное сообщение необходимо преобразовать так, чтобы для него были справедливы соотношения векторов матрицы первого порядка. Для этого к закодированному сообщению прибавляют векторы по модулю два:

Согласно (3.42) определяем

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

т. е.

Таким образом, исходное сообщение, выделенное из кодового слова, имеет вид 10001011011.

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

При наличии ошибок критерий большинства имеет вид

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

При наличии ошибки достаточен следующий критерий большинства проверок: если количество единиц в полученном векторе если количество единиц в полученном векторе

Пример. При передаче закодированного сообщения 1111101001101100 в седьмом разряде произошел сбой. Принятое сообщение имеет вид 1111100001101100. Найти исходное сообщение. Согласно (3.43) и критерию большинства (3.46) находим, что Остальные определяем так же, как и в предыдущем примере.