Способы задания линейных кодов

1. Перечислением кодовых слов, т.е. составлении списка всех кодовых слов кода.

Пример. В таблице 1 представлены все кодовые слова (5,3) - кода (a_i - информационные, а b_i - проверочные символы).

Таблица 1
№	a1	a2	a3	b1	b2

2. Системой проверочных уравнений, определяющих правила формирования проверочных символов по известным информационным:

где

j - номер проверочного символа;

i - номер информационного символа;

h_ij - коэффициенты, принимающие значения 0 или 1 в соответствии с правилами формирования конкретных групповых кодов.

Пример. Для кода (5,3) проверочные уравнения имеют вид:

b₁= a₂ + a₃;

b₂= a₁ + a₂.

3. Матричное, основанное на построении порождающей и проверочной матриц.

Векторное пространство Vn над GF(2) включает в себя 2ⁿ векторов (n-последовательностей), а подпространством его является множество из 2^k кодовых слов длины n, которое однозначно определяется его базисом, состоящим из k линейно независимых векторов. Поэтому линейный (n,k) - код полностью определяется набором из k кодовых слов, принадлежащих этому коду. Набор из k кодовых слов, соответствующих базису, обычно представляется в виде матрицы, которая называется порождающей.

Пример. (5,3) - код, который был представлен в таблице 1, может быть задан матрицей

Остальные кодовые слова получаются сложением строк матриц в различных сочетаниях.

Общее количество различных вариантов порождающих матрицу определяется выражением

Для исключения неоднозначности в записи G(n,k) вводят понятие о канонической или систематической форме матрицы, которая имеет вид

где

I_k - единичная матрица, содержащая информационные символы;

R_k,r - прямоугольная матрица, составленная из проверочных символов.

Пример. Порождающая матрица в систематическом виде для (5,3) - кода

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

Проверочная матрица в систематическом виде имеет вид

где I_r - единичная матрица; - прямоугольная матрица в транспонированном виде матрицы R_k,r из порождающей матрицы.

Пример. Проверочная матрица (5,3) - кода

36. Декодирование М-последовательностей по методу максимального правдоподобия

Пусть есть код А, содержащий М=2^к слов, причем каждое слово имеет разрядность п:

На длине кода возможны следующие ошибки:

- одиночные, t = 1;

- двукратные, t = 2;

- n -кратные, t = п.

Суммарное число всевозможных ошибок равно Е=2ⁿ-1.

Задача декодирования состоит в том, чтобы по принятому вектору bj однозначно определить переданное сообщение ai, т. е. в качестве ai следует принять такой вектор, для которого условная вероятность p(ai/bj) максимальна. Декодирование, когда максимизируется p(a_i/bj), получило название декодирования по максимуму апостериорной вероятности. В теории информации доказывается, что p(a_i/bj)=C р(bj/аi), где С - константа. Следовательно, для максимизации p(ai/bj) необходимо максимизировать условную вероятность p(bj/ai). Для каждого отдельного канала эта вероятность имеет свое конкретное значение. Для наиболее широко применяемого двоично-симметричного канала зависимость этой вероятности от числа ошибок показана на рис. 7.2.

Рис. 7.2. Зависимость вероятности p(bj/ai) от кратности ошибок

Из рис. 7.2 следует, что для максимизации p(bj/ai) необходимо выбирать кратность ошибки как можно меньше. Отсюда следует правило декодирования: в качестве переданного слова следует выбирать такое слово, которое отличается от принятого слова в наименьшем числе позиций. Это можно определить так же, как декодирование по минимуму расстояния: принятое слово отождествляется с тем кодовым словом, от которого оно удалено на минимальное расстояние. В теории

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

На рис. 7.3 представлена структурная схема декодирующего устройства (декодера), реализующего декодирование по минимуму расстояния, где УСр -устройство сравнения, РУ - решающее устройство.

Часто декодирование по минимуму расстояния определяется как декодирование в целом, так как при декодировании принимается решение обо всем слове, а не об отдельном символе, когда принятое слово коррелируется со всеми кодовыми словами, и в качестве переданного принимается то, корреляция с которым будет максимальна. Такое декодирование называется декодированием по максимуму правдоподобия и реализуется многоканальным корреляционным приёмником, опорными словами которого являются все кодовые слова. Оценим сложность декодера. Пусть код имеет длину п и содержит 2^к кодовых слов. Для вычисления расстояния нужно умножить каждое из этих слов на принятое, вычислить скалярное произведение. Одно умножение требует выполнения п арифметических операций сложения двух чисел. Общее количество арифметических операций пропорционально величине п -2. Это число растет очень быстро с ростом к, поэтому декодирование по минимуму расстояния целесообразно использовать лишь в кодах с малым числом информационных символов (в низкоскоростных кодах, когда г»к).

С формальной точки зрения операция корреляции сводится к умножению принятого вектора на кодовую матрицу. Для кодов с основанием q = 2 для подобного умножения требуется п(п-1) операций сложения (вычитания). При больших п это приводит к большим вычислительным затратам.

Для некоторых кодов найдены операции векторно-матричного умножения, требующие п log2ti операций.

Пример 7.2. Рассмотрим код Адамара с п=4, который задается следующей матрицей кодовых слов:

Пусть принятый сигнал Х= (xj, Х2, хз, Х4)^T. При декодировании производим

умножение:

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

Первую итерацию можно представить как умножение принятого сигнала X на матрицу С1, а вторую - как умножение вектора (а, Ь, с, d) на матрицу С2. Эти матрицы имеют вид

Весь процесс вычислений сводится к умножению принятого вектора на две слабозаполненные матрицы:

Y=C₂C1X.

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

Факторизуя матрицы кодовых слов различных линейных и нелинейных кодов (Рида-Маллера, Адамара, максимальной длины и др.), можно ускорить процесс декодирования по максимуму правдоподобия.