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

Орловский государственный технический университет, г. Орел

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

Батенков А.А. Профессор кафедры прикладной математики

и информатики, д.т.н.,

Ковальский С.П. Преподаватель кафедры систем многоканальной

электросвязи

Annotatіon

In article the mathematical model of system of run-length coding in view of a binary channel is presented. It consists of the description of a source of messages and the channel of supervision. The source is presented in the form of the direct and indirect description of dynamic stochastic system. It generates values in the form of a multivariate code. The channel of supervision represents three matrixes providing transition from a multivariate code in a binary code and on the contrary. The results received in article are initial data for the filter of a run-length code. It will allow to reduce effect of duplication of mistakes at decoding the deformed compressed messages.

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

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

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

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

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

Мультипликативное уравнение - сумма переходных вероятностей всех ребер дерева, от корневой вершины до концевой, равна вероятности появления концевой вершины, то есть вероятности выпадения буквы источника сообщений. Линейное уравнение показывает, что сумма переходных вероятностей двух вершин, вышедших из одной вершины, равна единице. Запишем данные уравнения в аналитическом виде:

, (1)

где {G} - путь по дереву кодирования из l-й вершины в корневую вершину;

k - корневая вершина дерева кодирования.

, (2)

где {R} - пара вершин, вышедших с i-ой вершины.

Вводя новую переменную , получаем из мультипликативной системы (1) уравнений линейную с решением в виде:

, (3)

где - частное решение неоднородной преобразованной системы [1];

[B] - общее решение однородной преобразованной системы [1];

- вектор свободных переменных.

При ограничении .

Теперь рассмотрим систему линейных уравнений (2). Ее решение:

, (4)

где - частное решение неоднородной системы [1];

[D] - общее решение однородной системы [1];

- вектор свободных переменных.

При ограничении .

Данные системы уравнений решаются методами линейной алгебры. Для каждой системы уравнений получаем множество решений. Переходные вероятности в данном случае находим, как пересечение множеств решений для двух систем уравнений. С помощью потенцирования выражения (3) получаем:

. (5)

Множество пересечений находим, как неподвижные точки следующего уравнения:

=. (6)

Задавая , удовлетворяющее ограничению , находим неизвестное значение , где - номера соседних вершин дерева кодирования. Если i и j не соседние вершины, то .

Из полученных переходных вероятностей формируем матрицу Р размерностью NхN, где N - число вершин дерева кодирования неравномерного кода:

. (7)

При этом выполняются условия:

, . (8)

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

, (9)

где - прямое произведение матриц.

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

Рисунок 1 Дерево кодирования неравномерного кода

Например, для распределения вероятностей появления букв алфавита источника сообщений р=(0,5; 0,3; 0,2) и дерева кодирования, представленного на рисунке 1, матрица переходных вероятностей имеет следующий вид:

= (10)

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

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

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

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

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

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

, (11)

где .

При ограничениях:

, (12)

где - матрица детерминированных переходов при управлении .

. (13)

Тогда, решая задачу (11), (12-13), матрица переходных вероятностей для дерева кодирования, представленного на рисунке 1, может быть декомпозирована в виде:

=

Примем соглашение, что нумерация вершин, образующих N-ичную систему кодирования, производится слева направо и сверху вниз по дереву кодирования. В двоичный симметричный канал связи передается "0", если кодируется нечетная вершина, и "1" - четная вершина.

Для формализации математического описания модели введем переменные: - вектор размерности N, такой что , если система находится в i-ом состоянии, и при . k - номер шага дискретизации времени. Тогда уравнение состояния [3] системы неравномерного кодирования запишем в виде:

, при i-ом управлении, (14)

Будем рассматривать источник сообщений на уровне N-ичного канала связи. С этой целью в уравнение наблюдения включим уравнение перехода от N-ичного в двоичный канал и обратно. Этот переход можно характеризовать матрицей MN2 размера 2xN. Для рассматриваемого примера:

MN2=.

Двоичный симметричный канал связи опишем с помощью матрицы переходных вероятностей МК размера 2х2.

МК=

Обратный переход от двоичного к N-ичному каналу описывается с помощью матрицы M2N размера Nx2. Для рассматриваемого примера:

M2N=

Следовательно, уравнения наблюдения на уровнях N-ичного входа канала и N-ичного выхода записываются как:

(15)

На основе уравнения состояния (14) и уравнений наблюдения (15) построим модель структуры неравномерного кодирования с учетом двоичного симметричного канала связи, показанную на рисунке 2.

Рисунок 2 Модель структуры неравномерного кодирования с учетом двоичного симметричного канала связи

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

Литература

1. Ильин, В.А. Линейная алгебра [Текст]: учеб. для вузов / В.А. Ильин, Э.Г. Позняк. - 4-е изд. - М. : Наука. Физматлит, 1999. - 296 с.

2. Левин, Б.Р. Вероятностные модели и методы в системах связи и управления [Текст] / Б. Р. Левин, В. Шварц. - М.: Радио и связь, 1985. - 312 с.: ил.

3. Тихонов, В.И. Статистический анализ и синтез радиотехнических устройств и систем [Текст]: учеб. пособие для вузов / В. И. Тихонов, В. Н. Харисов. - М. : Радио и связь, 1991. - 608 с.: ил.

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