1.8. Модулярное представление блоковых кодов и их эквивалентность

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

Пусть задана специальная матрица  размерности , содержащая в качестве столбцов все возможные векторы из  двоичных элементов, исключая нулевой вектор. Тогда j-й столбец матрицы можно рассматривать как столбец типа j, а код может быть задан вектором, образованным  положительными целыми числами. Пусть, где  – число столбцов типа i.  Известно  [8, 15, 84], что матрица  размерности  в качестве строк содержит все возможные ненулевые линейные комбинации строк матрицы . Следовательно, строками матрицы  являются все ненулевые кодовые векторы.

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

и пусть задана порождающая матрица укороченного кода Хэмминга (6,3,3)

.

Тогда ,   поскольку  в матрице   имеется весь набор чисел, кроме  3.  Оценка произведения  дает следующий результат

.

 

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

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

При изучении свойств кодов, в которых расположение столбцов несущественно, т.е. свойств, общих для эквивалентных кодов, особенно удобно пользоваться модулярным представлением. Существует много различных способов выбора базиса для одного и того же кода, и, следовательно, много различных порождающих матриц. Вообще говоря. Различные порождающие матрицы будут приводить к различным векторам модулярного представления, и желательно знать, когда модулярные представления описывают эквивалентные коды [84].

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

Пусть  – любая невырожденная матрица размерности . Если  vi и  vj – векторы с  компонентами каждый,   то   vivj (vivj)  есть линейная комбинация строк матрицы , и поскольку строки матрицы  линейно зависимы, то  (vivj)  тогда и только тогда, когда  (vivj)=0. Поэтому если векторы  vi и  vj   не совпадают, то не совпадают и векторы vi и vj. Следовательно, все  строк матрицы  будут различны.

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

,

 

где  – некоторая матрица перестановки.

Если  и  – невырожденные матрицы размерности , то

,

т.е. произведению  соответствует перестановка .  Отсюда следует, что рассматриваемые перестановки образуют группу, изоморфную (т.е. обладающую той же самой структурой) группе невырожденных матриц размерности .

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

                                   ,      

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

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

Пусть задана перестановка вида

,

с соответствующей матрицей перестановки . Пусть задана порождающая матрица (6,3,3)-кода вида

.

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

,

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

.

 

Совпадение вторых строк  матрицы   и  следует считать случайным. 

Сравним  результаты произведений    и  :

 

    ;             .

 

                      .                

 

Обе матрицы  и  представляют один и тот же код, но с разными проверочными соотношениями.  Заметно, что весовые значения векторов в  и  распределены не одинаково, поэтому обратные преобразования в   должны в первую очередь соответствовать  весовым  показателям в . Рассмотрим  вектор    vi = из .  Выполнив   vi, получим значение vj = из . Из рис. 1.10 становится ясно, что эквивалентные коды образуют множество подстановок вида

 

!

поскольку  векторы веса  могут перейти только в векторы аналогичного веса, при этом значение !.

Рис. 1.10. Принцип подстановок в эквивалентных кодах

 

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

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

.

После применения подстановки к порождающей матрице кода получим

.

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

 

         и         .

 

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

Весовые показатели остались неизменными, но в первых   столбцах  заметен повтор отдельных наборов, например, 110; 011 и 101. Именно в этом проявляется линейная зависимость строк матрицы  . Поскольку весовые показатели матрицы  остались неизменными, то для получения эквивалентного кода необходимо изменить подстановку (изменить порядок следования столбцов в произведении ). Эту процедуру можно выполнить нескольким путями.

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

.

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

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

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

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

Общее число отрицательных исходов может быть найдено из выражения

,

тогда суммирование по всем строкам матрицы   определит общее число  отрицательных исходов

                           при .

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

.

Например, для кода (7,4,3)  с   значение  составит , здесь – весовая матрица порождающей матрицы кода.

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