способ манипуляционного кодирования

Формула изобретения

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

Описание изобретения к патенту

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

Известен способ манипуляционного кодирования [Нечаев Ю.Б. Манипуляционные коды для систем с итеративной обработкой принимаемого сигнала. / Нечаев Ю.Б., Малютин А.А. Инфокоммуникационные технологии. - 2009. № 2. - с.70-74], основанный на компьютерном переборе всех возможных вариантов отображения блока кодовых символов в передаваемый сигнал. Недостатком способа является низкая помехоустойчивость передачи дискретной информации.

Известен способ согласования модуляции и кодирования [Васильев К.К. Теория электрической связи: учебное пособие / Васильев К.К., Глушков В.А., Дормидонтов А.В., Нестеренко А.Г.; под общ. ред. Васильева К.К. - Ульяновск: УлГТУ, 2008. - с.387-388] на основе разбиения ансамбля сигналов на вложенные подансамбли. Способ согласования модуляции и кодирования на основе разбиения ансамбля сигналов на вложенные подансамбли снижает размерность переборной задачи синтеза сигнально-кодовой конструкции, но не обеспечивает гарантированное построение сигнально-кодовой конструкции с максимальными частотно-энергетическими характеристиками и не всегда позволяет согласовать евклидовы и хэмминговы расстояния, что определяет низкую помехоустойчивость этого способа согласования модуляции и кодирования. Другим существенным ограничением применения этого способа является требование четности общего числа точек в ансамбле сигналов и четности числа точек в каждом из подансамблей, получаемых при разбиении, что определяет возможность его применения только для сигнально-кодовых конструкций с числом точек, кратным степени числа 2.

Наиболее близким по технической сущности (прототипом) к заявленному способу является способ модуляции и демодуляции, устройство модуляции и устройство демодуляции (RU 2384960 С2 20.03.2010), в формуле изобретения которого представлен способ модуляции и демодуляции, при котором передаются данные (2n+1) битов (где "n" - целое число, больше 1), и многоуровневое значение установлено в 2⁽²ⁿ⁺¹⁾, причем способ содержит: разделение сигнальных точек, упорядоченных в каждом из четырех квадрантов на 8 подгрупп, соответствующих 3 битам из данных (2n+1) битов, причем четыре квадранта разделены синфазной осью и ортогональной осью, перпендикулярными друг другу; кодирование 3 битов таким образом, чтобы среднее расстояние Хэмминга между соседними сигнальными точками в 8 подгруппах стало минимальным; выполнение кодирования Грея для 2 битов из данных (2n+1) битов, в качестве сигнала, обеспечивающего возможность идентификации четырех квадрантов.

Недостатком известного прототипа является то, что он применим только к сигналам с многоуровневой квадратурной амплитудной модуляцией, при этом общее число точек должно определяться формулой 2⁽²ⁿ⁺¹⁾, при этом описанный в прототипе способ модуляции и демодуляции обладает низкой помехоустойчивостью передачи дискретной информации.

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

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

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

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

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

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

Реализация изобретения достигается следующим образом.

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

Евклидово расстояние между i-ой и j-ой точками сигнального созвездия рассчитывается по формуле:

,

где ,

, - k-я координата i-ой (j-ой) точки в сигнальном пространстве,

Р - размерность сигнального пространства (например, для квадратурно-амплитудной модуляции Р=2).

Матрица I инциденций состоит из матриц инциденций исходящих дуг графа I_исх и матриц инциденций входящих дуг графа I _вх, при этом

I=I_исх+I_вх .

Исходные данные:

- матрица инциденций исходящих дуг графа I_исх;

- матрица инциденций входящих дуг графа I_вх;

- вектор величины евклидовых расстояний (весов дуг графа) , где D - число дуг;

- номера вершин истока и стока выбираемого пути , ;

- множество вершин, обязательных для прохода {V_pr};

- множество свободных для прохода вершин {V_sw}.

Задачу маршрутизации по вершинам графа представляют в следующей формулировке:

где T_k - евклидово расстояние между сигнальными точками,

- вектор назначений дуг графа, .

Целевая функция (1) отражает необходимость минимизации суммарного евклидова расстояния в маршруте, образованном последовательным прохождением дуг в векторе _k.

Вспомогательные структурные переменные свяжем с декомпозированной матрицей инциденций для V-узлов и D-дуг, вектором истоков и вектором стоков с помощью соотношений:

При задании векторов истоков и стоков необходимо положить , .

Пусть для формирования вариантов выборов маршрутов заданы множества:

{V_pr} - множество вершин, обязательных для прохода по маршруту i j;

{V_sw} - множество вершин, свободных для прохода по маршруту i j (т.е. маршрут может проходить, а может и не проходить через вершину, принадлежащую этому множеству).

Очевидно: {V_pr} {V_sw}={V}.

Тогда: , k {V_pr}; , l {V_pr}.

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

Ограничение на отсутствие циклов в путях графа записывается в виде:

где - вектор размерности V×1.

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

Используем свойство идемпотентности ограничения: х²=х, которое допускает лишь булевость переменной х (х=0 или 1). Тогда ограничения (5, 6) на континуальных множествах переменных , записываются в виде

и таким образом целочисленная задача (1), (2-6) преобразована (погружена) в общую задачу нелинейного программирования (1), (2-4, 7, 8).

Эта задача является задачей оптимизации при наличии ограничений в виде равенств. Поэтому к ней применим метод множителей Лагранжа. Тогда запишем функцию Лагранжа в виде: лямбда - множители Лагранжа

Введем общий вектор искомых переменных в виде составного вектора размерностью D+n+2V+n+1+D.

Необходимые условия экстремума запишем в виде системы уравнений:

;

;

;

;

Таким образом, сформирована система из m=D+n+2V+n+1+D уравнений с m=D+n+2V+n+1+D неизвестных.

Выберем метод Ньютона-Рафсона [Хэмди А. Таха. Введение в исследование операций, 6-е издание: Пер. с англ. - М.: Издательский дом "Вильяме", 2001. - С.744-745] (второго порядка) для решения системы нелинейных уравнений. При этом в качестве целевой функции эквивалентной задачи минимизации положим минимум невязки между левой и правой частями системы уравнений (10):

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

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

Так, для системы уравнений , i=1, 2, , m, метод использует итерационную процедуру , где: - матрица якобиана.

Алгоритмы, построенные по методу Ньютона-Рафсона, имеют малый радиус сходимости [Хэмди А. Таха. Введение в исследование операций, 6-е издание: Пер. с англ. - М.: Издательский дом "Вильяме", 2001. - С.745]. Поэтому будем использовать двухэтапную процедуру поиска начального приближения. На первом этапе применим полиномиальный алгоритм венгерского метода [Пападимитриу X. Комбинаторная оптимизация. Алгоритмы и сложность / Пападимитриу X., Стайглиц К. - М.: Мир, 1985. - с.255-262] решения задачи о назначениях, которая не содержит ограничения на цикличность пути, сформулированной в виде:

,

.

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

3. Вычисляют вектор градиента для начального вектора.

Вектор коррекции градиента

На втором этапе используем наискорейший градиентный спуск первого порядка, при этом алгоритм второго этапа включим в алгоритм метода Ньютона-Рафсона.

4. Находят методом одномерного поиска минимум в направлении вектора градиента. Для этого:

- положим U= ;

- зададим номер шага i=1, точность работы алгоритма: Тосп=10^-3;

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

- вычислим вектор градиента ;

- проверим условие |Cel_i-U|>Tосп, если оно выполняется, то перейдем к следующему пункту, а если нет, то определим значение вспомогательной переменной i1=1 и методом одномерного поиска определим минимум в новом направлении;

- положим U=Cel_i;

- увеличим значение i на 1;

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

Исходные данные для одномерного поиска точки минимума:

- - общий вектор исходных переменных;

- grad - градиент ;

- - вектор евклидовых расстояний (весов дуг графа).

Порядок одномерного поиска точки минимума

Шаг 1. Присвоить номер шага: i=1.

Шаг 2. Задать пороговое значение: Porog = 10¹³.

Шаг 3. Присвоить ; min=W_x.

Шаг 4. Задать значение шага градиента: =-1×10^-0, .

Шаг 5. Проверка условия |W_x -Porog}>10^-3, если да, то перейти к шагу 6, если нет, то к шагу 14.

Шаг 6. Присвоить i=i+1.

Шаг 7. Пороговое значение Porog=W_x.

Шаг 8. Проверка условия , если да, то к шагу 9, если нет, то к шагу 10.

Шаг 9. Вычислить значение шага: = ×10^-3.

Шаг 10. Вычислить значение вектора: .

Шаг 11. Вычислить: .

Шаг 12. Проверка условия W_x <min.

Шаг 13. Присвоить значения: min=W _x, и перейти к шагу 5.

Шаг 14. Формирование выходных данных: .

5. Повторно вычисляют вектор градиента в точке минимума.

Вычислить новое значение градиента .

Вычисляют значение целевой функции .

Определяют значение вспомогательной переменной i1=1.

6. Методом одномерного поиска определяют минимум в новом направлении.

7. Получают улучшенное приближение вектора назначения.

8. Находят оптимальное решение задачи маршрутизации в евклидовом пространстве с помощью метода Ньютона-Рафсона.

Далее введем обозначение матриц с указанием их размерности, так:

- матрица размера m×n.

,

где

,

здесь символом обозначено кронекеровское произведение матриц А и В:

,

dg() - оператор формирования диагональной матрицы с элементами равными диагональным элементам матрицы ().

A=-I_исх;

B=I_вх .

;

;

I_L - единичная матрица размера L×L;

E_L - единичный вектор размера L×1;

;

- диагональная матрица с вектором на главной диагонали;

vecI_D - оператор векторизации матрицы I_D.

; ; ; ;

;

; , n {V_sw};

; , n {V_sw};

; ;

; ; ;

; ; ;

; ; n {V_sw}; ;

; ; ;

; ; ; ;

; ;

; ; ; ;

; .

U=

Проверить условие: |NewLagr_i1 -U|>Тосп; если нет, то переходят к формированию последовательности обхода вершин графа.

i1=i1+1

возвращаются к проверке условия |NewLagr _i1- U|>Тосп.

9. Формируют последовательность обхода вершин графа

.

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

В источнике [Dayan Adionel Guimaraes. Digital Transmission: A Simulation-Aided Introduction with VisSim/Comm. Springer-Verlag Berlin Heidelberg, 2009. - С.397] предложена оценка границы вероятности ошибки в случае применения манипуляционного кода и в альтернативном случае:

,

где P_b - вероятность ошибочного приема бита (ошибка в одном двоичном разряде кодовой комбинации),

P_e - вероятность ошибочного приема символа,

М - число точек в сигнальном созвездии (позиционность системы

модуляции).

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

Так, например, при применении описанного способа манипуляционного кодирования для М=256 вероятность ошибочного приема бита снизится приблизительно в 4 раза.

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