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

О формировании сигнальных созвездий для телекоммуникационных систем

Батенков А.А., Батенков К.А.

Annotation

телекоммуникационный система сигнальный дискретный

The main present methods forming Euclidean codes utilized at telecommunication system design are analyzed. The claim about many-dimensional signal ensembles synthesis opportunity for discrete channel with additive white Gaussian noise on the basis of optimization problem with differentiable criterion function and constraint is proved. Development opportunity of algorithm forming signal constellations on basis of given claim is displayed.

Основная часть

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

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

Существуют несколько способов формирования ансамблей сигналов для данной модели канала связи. Их можно условно разделить на две группы: 1) способы на основе известных плотнейших упаковок; 2) способы на основе численных методов оптимизации.

Первая из этих групп опирается на достаточно разработанную теорию решеток [2]. При таком подходе сигналы отбираются из бесконечного числа точек многомерного решетчатого пространства по заданному правилу. Подобные алгоритмы отличаются значительной степенью эвристичности вследствие неоптимальности процедур выбора точек в целом, а также фиксированности структуры решетки. Тем не менее, на отдельных этапах формирования множества сигналов (добавление одной из точек) поиск может быть оптимальным, но только в рамках заданной решетки [11]. Необходимо отметить, что для данных конструкций получены асимптотические границы эффективности кодирования [13], а также, благодаря регулярности их структуры, разработаны довольно простые алгоритмы декодирования [1, 6, 10].

Вторая группа используется в предположении произвольного расположения точек созвездия. Их основой является формулировка оптимизационных задач по заданным критериям, например, критерий максимума минимума квадрата расстояния Евклида [13], критерий максимума минимума среднего расстояния по Кульбаку [12] и др. При этом решения таких оптимизационных задач в общем случае существуют только для ограниченного класса сигналов, например, при заданном числе измерений пространства сигналов [2].

Поэтому поиск сигнальных созвездий сводится к преобразованию целевого функционала к дифференцируемому виду путем аппроксимации целевой функции [14], либо преобразованию максиминной задачи к задаче на максимум или минимум [8, 12]. Особенностью получаемых решений является их локальная оптимальность и, как следствие, зависимость от начальных условий.

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

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

Утверждение. Задача на поиск экстремумов функционала:

, (1)

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

при ограничении

, (2)

где - максимально допустимая величина средней мощности ансамбля сигналов; эквивалентна по решению задаче о плотнейшей укладке шаров в многомерном пространстве. Характер экстремумов определяется величиной отношения квадрата минимального евклидова расстояния между точками к дисперсии гауссовского шума. При этом минимумы соответствуют плотнейшей укладке при выполнении неравенства:

, (3)

а максимумы при:

. (4)

Доказательство. Задача о плотнейшей упаковке шаров в многомерном пространстве трактуется как поиск такого расположения точек в многомерном пространстве, при котором максимизируется квадрат минимального расстояния между ними при заданной максимально возможной сумме квадратов расстояний до центра координат [2]:

, (5)

. (6)

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

, (7)

имеют определенный знак [4]. Это свидетельствует о том, что решения задач (1) и (5) эквивалентны, т.к. нули производных этих функционалов будут в этом случае совпадать [3].

Производная функционала (5) по переменным представляет собой вектор длиной , элементы которого определяются выражением:

. (8)

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

Используя (7), первая производная функционала (1) приобретает вид:

. (9)

Производная функционала (1) по направлению производной функционала (5) имеет вид [4]:

. (10)

Обозначив экспоненту как:

, (11)

на основе выражений для производных (8) и (9) равенство (10) преобразуется в форму:

, (12)

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

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

. (13)

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

. (14)

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

. (15)

Поскольку область определения переменной , согласно (11), то третий корень (15) можно отбросить, т.к. он всегда меньше нуля. Оставшиеся два корня определяют точки пересечения через нуль производной по направлению (12). Так как знак при наибольшей третьей степени полинома (14) отрицателен, то чередование знака начинается с минуса в бесконечности [3]. Таким образом, производная больше нуля, если , и меньше - при . Однако найти величину второго корня довольно проблематично при большом количестве точек. Поэтому оценим верхнюю и нижнюю границы величины второго корня при произвольном распределении точек. Производные второго корня (15) по входящим в суммы экспонентам имеют вид:

. (16)

Выражение в первой из квадратных скобок (16) идентично подкоренному выражению (15). Для нахождения экстремумов приравняем (16) к нулю и выразим из (16) подкоренное выражение. Тогда его подстановка во второй корень (15) и сокращение подобных членов приводит к равенству: .

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

. (17)

Группировка слагаемых при различных степенях экспонент и решение полученного полиномиального уравнения дает минимальное значение второго корня:

. (18)

Максимальное значение находится также на границе допустимой области для производной по направлению (12). Исследование граничных точек [3] показывает, что максимальная величина достигается при равенстве нулю всех экспонент (11), за исключением случая . Тогда на основании (15):

. (19)

Таким образом, на основании (18) и (19) в случае произвольного распределения точек сигнального созвездия производная по направлению (12) имеет положительный знак на интервале и отрицательный - . Причем длина второго интервала не зависит от параметров исходной задачи, а первого определяется только числом точек ансамбля сигналов.

На основании (11) длины интервалов постоянного знака производной по направлению (14) можно выразить через отношение квадрата минимального расстояния к дисперсии гауссовского шума. Таким образом, производная по направлению отрицательна при и положительна при . Следовательно, функционалы (1) и (5) на втором интервале имеют идентичные максимумы, а на первом - максимуму функционала (5) соответствует максимум функционала (1). Значит, решению задачи о плотнейшей укладке соответствует поиск максимумов на втором интервале и минимумов на первом.

Таким образом, утверждение доказано.

Задача (1), (2) относится к классу задач нелинейного программирования с нелинейной целевой функцией и нелинейным ограничением [9]. Решение данной задачи в общем виде получить затруднительно, так как числитель и знаменатель (1) имеют аддитивные экспоненциальные зависимости. Поэтому рационально использовать численные градиентные методы оптимизации вследствие непрерывности как целевого функционала, так и ограничения.

Рисунок 1 Расположение точек сигнального созвездия на -ой итерации

В качестве примера был использован алгоритм, разработанный на основе метода градиентного спуска (подъема) в сочетании с методом штрафных функций [8], при следующих исходных данных: размерность ансамбля сигналов - , число точек ансамбля - , максимально допустимая средняя мощность сигналов - . На рисунке 1 представлено расположение точек сигнального созвездия на нескольких шагах итерационного процесса, а также нормированные минимальные расстояния

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

Литература

1. Зяблов, В.В. Высокоскоростная передача сообщений в реальных каналах [Текст] / В.В. Зяблов, Д.Л. Коробков, С.Л. Портной. М.: Радио и связь, 1991. 288 с.

2. Конвей, Дж. Упаковки шаров, решетки и группы [Текст]: [пер. с англ.] / Дж. Конвей, Н. Слоэн. В 2-х т.Т.1.М.: Мир, 1990. 704 с.

3. Корн, Г., Корн К. Справочник по математике для научных работников и инженеров [Текст] / Г. Корн, К. Корн. М.: 1970. 720 с.

4. Курант, Р. Курс дифференциального и интегрального исчисления [Текст]: В 2-ч т. Курант, Р. М.: Наука, 1970.

5. Зюко, А.Г. Помехоустойчивость и эффективность систем передачи информации [Текст] / А.Г. Зюко [и др.]; под. ред. А.Г. Зюко. М.: Радио и связь, 1985. 272 с.

6. Скляр, Б. Цифровая связь. Теоретические основы и практическое применение [Текст]: [пер. с англ.] / Б. Скляр. Изд. 2-е испр. М.: Вильямс, 2003. 1104 с.

7. Теория электрической связи [Текст]: учебник для ВУЗов / Под ред. Д.Д. Кловского - М.: Радио и связь, 1999. 432 с.

8. Федоров, В.В. Численные методы максимина [Текст] / В.В. Федоров. М.: Наука, Главная редакция физико-математической литературы, 1979. 280 с.

9. Химмельблау, Д. Прикладное нелинейное программирование [Текст]: [пер. с англ.] / Д. Химмельблау; под ред. М.Л. Быховского. М.: Мир, 1975. 534 с.

10. Calderbank, A.R. The art of signaling: fifty years of coding theory [Text] / A.R. Calderbank // IEEE Trans. Inform. Theory. vol. 44, № 6,1998. P. 2261 - 2595.

11. Forney, G.D. Jr. Coset codes - part I [Text]: introduction and geometrical classification / G.D. Forney // IEEE Trans. Inform. Theory. vol. 34, № 5, 1973. P. 1123 - 1151.

12. Gokenbach, M.S. Optimal signal sets for non-Gaussian detectors [Text] / Gokenbach, M.S., Kearsley A.J. // Contribution of the National Institute of Standards and Technology.

13. Honig, M.L., Steiglitz K., Norman S.A. Optimization of signal sets for partial-response channels - part I [Text]: numerical techniques // IEEE Trans. Inform. Theory. vol. 37, № 5, 1991. P. 1327 - 1341.

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