Основные сведения о коде - Построение декодера Рида - Маллера

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

Блоковый код мощности М над алфавитом из q символов определяется как множество из М q-ичных последовательностей длины n, называемых кодовыми словами (если q = 2, то символы называются битами).

При этом М = qK для некоторого целого k, код называется (n, k)-кодом. Причем каждой последовательности из k q-ичных символов можно сопоставить последовательность из n q-ичных символов, являющуюся кодовым словом. Имеются два основных класса кодов: блоковые коды и древовидные коды (смотри рисунок 1).

2

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

О блоковом коде судят по трем параметрам: длине блока n, информационной длине k и минимальному кодовому расстоянию d.

Расстоянием по Хэммингу [1] между двумя q-ичными последовательностями x и y длины n называется число позиций, в которых они различны. Это расстояние обозначается через d (x, y).

Минимальным кодовым расстоянием кода [1] называется наименьшее из всех расстояний по Хэммингу между различными парами кодовых слов, т. е.

(5),

(n, k)-код с минимальным расстоянием d называется также (n, k, d)-кодом.

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

(6).

Геометрическая иллюстрация дается на рисунке 2. В пространстве всех q-ичных n-последовательностей выбрано некоторое множество n-последовательностей, объявленных кодовыми словами. Если d' - минимальное расстояние этого кода, а t - наибольшее целое число, удовлетворяющее условию, то вокруг каждого кодового слова можно описать непересекающуюся сферу радиуса t. Принятые слова, лежащие внутри сфер, декодируются как кодовое слово, являющееся центром

Соответствующей сферы. Если произошло не более t ошибок, то принятое слово всегда лежит внутри соответствующей сферы и декодируется правильно.

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

Полем [3] называется множество с двумя определенными на нем операциями - сложением и умножением, причем имеют место следующие аксиомы:

    1) множество образует абелеву группу по сложению; 2) поле замкнуто относительно умножения, и множество ненулевых элементов образуют абелеву группу по умножению. 3) закон дистрибутивности:
      (a + b)c = ac+bc для любых a, b, c из поля.

Поле с q элементами, если оно существует, называется конечным полем, или полем Галуа [2], и обозначается через GF(q).

Линейный код образует подпространство в GF(q). Любое множество базисных векторов может быть использовано в качестве строк для построения (kn)-матрицы G, которая называется порождающей матрицей кода. Пространство строк матрицы G есть линейный код, любое кодовое слово есть линейная комбинация строк из G. Множество qK кодовых слов называется линейным (n, k)-кодом.

Строки матрицы G линейно независимы, и число строк k равно размерности подпространства. Размерность всего пространства GFN(q) может быть отображена на множество кодовых слов.

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

C = iG (7),

Где i - информационное слово, представляющее собой k-последовательность кодируемых информационных символов, а c - образующая кодовое слово n-последовательность.

Например, если

,

То информационное слово

I = [0 1 1]

Будет кодироваться в кодовое слово

Кроме порождающей матрицы существует так же проверочная матрица называемая Н матрицей. При этом выполняется условие

СНТ=0 (8).

Матрица Н является (n - k)n матрицей; поскольку равенство сНТ = 0 выполняется при подстановке вместо с любой строки матрицы G, то

GHT = 0 (9).

Для приведенной выше порождающей матрице G, получаем

.

Коды Рида - Маллера представляют собой класс линейных кодов над GF(2) c простым описанием и декодированием, осуществляемым методом простого голосования. По этим причинам коды Рида - Маллера играют важную роль в кодировании (коды Рида - Маллера были использованы при передаче фотографий Марса космическим кораблем Маринер в 1972г.)[2], хотя если судить по минимальному расстоянию, то, за некоторыми исключениями, они не заслуживают особого внимания. Для любых целых m и r < m существует код Рида - Маллера r-го порядка длины 2M.

Код Рида - Маллера является линейным кодом и определяется через порождающую матрицу, которая обычно, для удобства декодирования, строится в несистематической форме. Покомпонентным произведением двух векторов a = (a0, a1, ... aN-1) и b = (b0, b1, ... bN-1) является вектор

С = (a0B0, a1B1, ... aN-1BN-1) (10).

Порождающая матрица кода Рида - Маллера r-го порядка длиной 2M определяется как совокупность блоков

,

Где G0 - вектор размерности n = 2M, состоящий из одних единиц; G1 есть (m2M)-матрица, содержащая в качестве столбцов все двоичные m-последовательности; строки матрицы GL получаются из строк матрицы G1 как всевозможные произведения l строк из G1. Считается, что первый столбец в G1 состоит из одних нулей, последний - из одних единиц, а остальные m последовательности в G1 расположены в порядке возрастания, считая, что младший бит расположен в нижней строке. Существует всего способов выбора l строк, входящих в произведение, следовательно матрица GL имеет размер. Отсюда следует, что для кода Рида - Маллера порядка r

Что обеспечивается линейной независимостью строк в матрице G. Код нулевого порядка является (n, 1)-кодом. Это просто код с повторением, который тривиально декодируется с помощью мажоритарного метода. Минимальное расстояние такого кода равно 2M.

Например, возьмем m = 4, n = 16, r = 3. Тогда

,

.

Поскольку G1 имеет 4 строки, матрица G2 имеет строк:

,

А матрица G3 имеет строк:

Таким образом, порождающая матрица кода Рида - Маллера третьего порядка длины 16 является (1516)-матрицей вида

.

Эта порождающая матрица задает (16, 15)-код над GF(2) (на самом деле это просто код с проверкой на четность). Другой код Рида - Маллера может быть получен с использованием этих матриц, если взять r = 2. В этом случае порождающая матрица будет иметь вид

И задает (16, 11)-код над GF(2). В действительности это (15, 11)-код Хэмминга, расширенный с помощью проверки на четность.

Из определения порождающей матрицы ясно, что код Рида - Маллера r-го порядка может быть получен дополнением кода Рида - Маллера (r - 1)-го порядка, а код Рида - Маллера (r - 1)-го порядка получается из кода r-го порядка с помощью выбрасывания. Поскольку код Рида - Маллера r-го порядка содержит код (r - 1)-го порядка, ясно, что его минимальное расстояние не может быть больше минимального расстояния кода (r-1)-го порядка. Вообще, кодовое расстояние кода Рида - Маллера определяется по формуле

D = 2M - r (13).

Каждая строка матрицы G1 имеет вес 2M - l. Таким образом, любая строка матрицы G имеет четный вес, а сумма двух двоичных векторов четного веса также имеет четный вес. Следовательно все линейные комбинации строк матрицы G имеют четный вес, а это значит, что все кодовые слова имеют четный вес. Матрица GR содержит строки весом 2M - r, и, следовательно, минимальный вес кода не превосходит 2M - r.

Для декодирования кодов Рида - Маллера был специально разработан алгоритм Рида [2], который позволяет исправлять ошибок и восстанавливать k информационных символов. Отсюда следует, что минимальное расстояние будет не меньше 2M - r - 1, но оно должно быть четным и потому будет не меньше 2M - r.

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

Для удобства разобьем информационный вектор на r + 1 сегмент, положив, где сегмент IL содержит информационных битов. Каждый сегмент будет умножаться на один блок матрицы G. Следовательно, кодирование можно представить поблочным умножением вектора на матрицу:

(14).

Предположим, что информационная последовательность разбита на сегменты следующим образом: каждому сегменту соответствует один из r блоков порождающей матрицы, который при кодировании умножается на этот сегмент. Если мы сможем восстановить информационные биты в r-ом сегменте, то затем сможем вычислить их вклад в принятое слово и вычесть его из принятого слова. Тогда задача сведется к декодированию кода Рида - Маллера (r - 1)-го порядка. Процедура декодирования представляет собой последовательность мажоритарных декодирований и начинается с нахождения мажоритарным методом информационных символов в сегменте м номером r.

Принятое слово запишем в виде

(15).

Алгоритм декодирования сначала по принятому слову восстанавливает IR, затем вычисляется разность

(16),

Которая является искаженным кодовым словом кода Рида - Маллера (r - 1)-го порядка.

Прежде всего, рассмотрим декодирование информационного бита iK-1, который умножается на последнюю строку матрицы GR. Декодируем этот бит, вычисляя 2M - r проверочных сумм по 2R бит из 2M бит принятого слова, так что каждый принятый бит входит только в одну сумму. Проверочные суммы строятся таким образом, что символ iK-1 вносит вклад только в один бит, а все другие информационные биты вносят вклад в четное число бит в каждой проверочной сумме. Таким образом, при отсутствии ошибок все проверочные суммы равны iK-1. Но, даже если имеется не более ошибок, большинство проверочных сумм по-прежнему будет равняться iK-1.

Первая проверочная сумма представляет собой сумму по модулю 2 первых 2 бит принятого слова, вторая - сумму по модулю два вторых 2R бит принятого слова и т. д. Всего получается 2M - r проверочных сумм, и по предположению имеется ошибок. Таким образом, мажоритарное голосование проверочных сумм дает правильное значение iK-1. Для построенного ранее (16, 11)-кода Рида - Маллера эти четыре суммы выглядят следующим образом:

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

Аналогично может быть продекодирован любой информационный символ, который умножается на одну из строк матрицы GR. Это происходит потому, что любая строка матрицы GR ничем не выделяется среди остальных. Перестановкой столбцов мы можем добиться того, что любая строка будет выглядеть так же, как последняя строка матрицы GR. Следовательно, можно использовать те же самые проверочные суммы, соответственно переставив индексы у символов, входящих в эти суммы. После построения 2M - r проверочных сумм каждый бит декодируется мажоритарным методом.

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

Этот процесс повторяется до тех пор, пока не будут найдены все информационные биты.

Похожие статьи




Основные сведения о коде - Построение декодера Рида - Маллера

Предыдущая | Следующая