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

Размещено на http://www.allbest.ru/

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

Захарченко Н.В.¹, Корчинский В.В.², Радзимовский Б.К.³, Бектурсунов Д.Н.⁴, Горохов Ю.С.⁵

¹Доктор технических наук, ²Кандидат технических наук, ³Кандидат технических наук, ⁴Аспирант, ⁵Аспирант, Одесская национальная академия связи

Аннотация

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

Ключевые слова: Блоковые коды, корректирующие коды, групповой корректирующий код.

Zakharchenko N.V.¹, Korchinskiy V.V.², Radzimovsky B.K.³, Bektursunov D.N.⁴, Gorokhov Y.S.⁵

¹Ph.D., ²Ph.D., ³Ph.D., ⁴Graduate, ⁵Graduate, Odessa National Academy of Telecommunications;

PARAMETERS SELF-SYNCHRONIZING PROPERTIES OF POSITIONAL REDUNDANT BLOCK CODES

Abstract

A physics of the two subspaces of vectors excess line code , set their generating matrix and defined power limits of space intersection, contains recommendations for individual redundant block codes.

Keywords: Block codes, error-correcting codes, group correction code.

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

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

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

Групповой корректирующий (n,k) код (ГКК) может быть задан с помощью порождающей матрицы , которая представляет собой набор линейно-независимых (базисных) векторов линейного кода

(1)

код вектор двоичный пространство

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

Допустим, последовательно передаются два любых n-элементных кодовых вектора

где i, l = 1, 2, …, 2k, k - ранг матрицы .

Рассмотрим случай (рис. 1), когда начало отсчета n-элементного кодового вектора на приеме смещается на некоторую величину j относительно переданного, что соответствует нарушению цикловой синхронизации. В результате получим вектор

который назовем вектором пересечения кодовых векторов и , и обозначим через .

Рис. 1 - Границы векторов пересечений

Вектор можно представить в виде суммы двух векторов: (n-j)-элементного вектора и j-элементного вектора .

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

(2)

(3)

где + - обозначение прямой суммы, а ? - пересечение подпространств.

Выражение (2) означает, что всякий вектор пересечения кодовых векторов ? может быть записан в виде: =+ (?, ?), а условие (3) показывает, что подпространства и не имеют общих векторов, кроме нулевого.

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

= + ..

Элементы матрицы задаются соотношениями:

=0 во всех остальных случаях.

Тогда

(4)

Мощность пространства при этом будет равна:

(5)

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

Для определения обозначим через пересечение пространств и . Множество есть векторное подпространство каждого из подпространств и , и имеет размерность дj. Тогда может быть найдено из

(6)

где - мощность пространства равная .

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

откуда

(7)

Значения бj, вj и k нам известны. Определение дj и уj осуществляется следующим образом.

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

(8)

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

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

В связи с вышесказанным, для расчета необходимо определить:

· общее количество векторов пересечений , т.е. мощность пространства ;

· структуру векторов ? , т.е. найти пространство .

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

При изменении j от 1 до (n,k), суммарное количество векторов будет равно

(8а)

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

С учетом вышесказанного получаем

(9)

Таким образом, величина ранга матрицы при изменении j от 1 до (n-1) полностью зависит от структуры группового (n,k) кода, в частности от структуры матрицы дополнения и вычисляется по (8) и (9).

Для групповых кодов характерно такое построение матрицы-дополнения , что с целью достижения наивысшей корректирующей способности по аддитивным ошибкам, она после приведения к каноническому виду, является порождающей для пространства, мощность которого равна 2r при r<k и 2k при r>k.

Раскрывая выражения (8), (8а) и (9) можно показать, что

(9а)

В связи с этим, в случае , величина будет равна:

а) при 1 ? j ? r,

(10)

б) при r ? j ? k,

(11)

т.к. в (9а) , следовательно, и ;

в) при k < j < n,

(12)

т.к. , то будет равен числу ее столбцов, а именно (n-j), поэтому из (9) следует, что .

В случае r>k:

а) при 1 ? j < k,

(13)

т.к. в (9а) , следовательно, и ;

б) при k ? j ? r,

(14)

т.к. в (9а) , следовательно, и ;

в) при r < j < n,

(15)

т.к. , то будет равен числу ее столбцов, а именно (n-j), поэтому из этого следует, что .

Систематизируя выражения, получим:

(16)

(17)

Вычисление мощности пространств векторов осуществляется по (5). На рис. 2 приведены графики зависимости мощности пространства от j, n и k, а на рис. 3 зависимости предельных значений Рj от структуры используемых кодов и величины смещения j.

Рис. 2. Зависимость мощности пространства от j, n и k

Рис. 3. Зависимость от величины смещения j

Литература

1. Захарченко В.Н., Улеев А.П., Липчанский А.И. Эффективность исправления ошибок смещения ЗМВ в системах с РОС на базе МВС. Вестник Харьковского политехнического университета. - Харьков: ХГПУ, 1999. - Выпуск 35. - С. 85-91.

2. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. - М.: Техносфера, 2005. - 320 с.

3. Помехоустойчивость и эффективность систем передачи информации. / А.Г. Зюко, А.И. Фалько, И.П. Панфилов, В.Л. Банкет, П.В. Иващенко; Под ред. А.Г. Зюко. - М.: Радио и связь, 1985. - 272 с.

4. Берлекамп Э. Алгебраическая теория кодирования: Пер. с англ. / Под ред. С.Д. Бирмана. - М.: Мир, 1971. - 477с.

Размещено на Allbest.ru