Содержание к диссертации
Стр.
ВВЕДЕНИЕ 4
1. ВЫБОР ОПТИМАЛЬНЫХ ПАРАМЕТРОВ СХОДИМХТИ В ИЗВЕСТНЫХ
АЛГОРИТМАХ НАСТРОЙКИ НИЗКОЧАСТОТНЫХ ГАРМОНИЧЕСКИХ
КОРРЕКТОРОВ 17
-
Постановка задачи 17
-
Настройка ГК на основе метода минимальных невязок . 24
-
Выбор параметра сходимости в ZF -алгоритме ... 32
-
Модернизация модифицированного алгоритма Лакки . . 38
-
Оценка быстродействия алгоритмов 40
-
Выводы 45
2. ВЫБОР ОПТИМАЛШЫХ ПАРАМЕТРОВ СХОДИМХТИ В АЛГОРИТМАХ
НАСТРОЙКИ ПОЛХОВЫХ ГК . . . . 47
-
Алгоритм настройки полосовых ГК на основе метода минимальных невязок 51
-
Оптимизация настройки ПГК с использованием
знаковых алгоритмов 62
2.2.1. Модифицированный алгоритм настройки ПГК .... 63
2.3. Выводы 67
3. БЫСТРОДЕЙСТВУЮЩИЕ АЛГОРИТМЫ НАСТРОЙКИ ГК НА ОСНОВЕ
МЕТОДА НАИСКОРЕЙШЕГО СПУСКА 69
-
Общие замечания 69
-
Быстродействующий оптимальный алгоритм настройки
ГК на основе метода наискорейшего спуска 74
3.3. Модифицированные алгоритмы настройки ГК на основе
метода наискорейшего спуска «84
Стр.
3.4. Алгоритм настройки полосового ГК на основе
метода наискорейшего спуска 90
-
Адаптивные алгоритмы обработки сигналов 99
-
Выводы 104
4. ДВУХШАГОШЕ МЕТОДЫ НАСТРОЙКИ ГК 107
-
Общие замечания 107
-
Двухшаговый метод решения СЛАУ, автономный на
каждой итерации НО
-
Двухшаговые алгоритмы настройки ГК 114
-
Скоростной алгоритм адаптации ГК 123
-
Компромиссный алгоритм настройки ГК 125
-
Выводы 134
5. РАЗРАБОТКА ЭКОНОМИЧНОГО МЕТОДА НАСТРОЙКИ ГК 136
5.1. Метод поочередного сведения невязок к нулю
с фиксацией нулевых невязок 137
-
Метод поочередного сведения составляющих градиента к нулю с фиксацией нулевых составляющих градиента 152
-
Алгоритм настройки ГК на основе метода поочередного сведения невязок к нулю 155
-
Алгоритм настройки ГК методом поочередного
сведения к нулю составляющих градиента 158
5.5. Выводы 161
ЗАКЛЮЧЕНИЕ 163
ЛИТЕРАТУРА 170
Введение к работе
Актуальность темы. Принятые ХХУІ съездом КПСС "Основные направления экономического и социального развития СССР на 1981 - 1985 годы и на период до 1990 года предусматривают "...продолжить формирование единой автоматизированной сети связи (ЕАСС) страны на базе новейших систем передачи информации...", непосредственно перед специалистами в области обработки сигналов поставлена задача совершенствования и развития "...средств и систем передачи и обработки информации...". Эта задача выполняется в рамках целевой комплексной программы ОЦ - 025 "Создание сети обработки и передачи данных на базе новых и развиваемых вычислительных центров коллективного пользования и вычислительных центров отраслей народного хозяйства первой очереди государственной сети вычислительных центров и общегосударственной системы передачи данных".
Увеличивающиеся всё возрастающими темпами потоки информации, необходимые для нормального функционирования народного хозяйства, сопровождаются ростом потребности в передаче больших объёмов данных по коммутируемым каналам связи с высокими скоростями и верностью [15,24,26,82,83,99,112] .
Важнейшими требованиями, предъявляемыми к проектируемым системам передачи данных является повышение их пропускной способности и помехоустойчивости. Первое требование возникло в связи со стремлением уменьшить капитальные затраты на линейные сооружения, являющиеся наиболее дорогостоящим оборудованием средств связи. Одной из основных причин, в результате чего снижается помехоустойчивость, являются линейные искажения каналов и трактов передачи. Исследования показали, что передача данных по коммутируемым - 5 -каналам тональной частоты на скоростях выше 2400 бит/с приводит к резкому снижению верности, например, при скорости 4800 бит/с частость ошибок увеличивается в 4-6 раз [П2] .
Снижение помехоустойчивости за счет линейных искажений каналов связи компенсируется введением в состав устройства преобразования сигналов (ЛІС) адаптивного корректора, в качестве которого в большинстве случаев используется гармонический корректор (трансверсальный фильтр), который перед передачей данных необходимо настраивать [4-6,9,10,12,14,15,19,22-24,26,27,32-36,39,45-48, 50-61,72-87,91-93,95-99,112,115-166] .
Приемники ЛІС, использующие коррекцию, могут работать в двух режимах: автоматическом и адаптивном (рабочем) [4,10,12,15, 19,32,36,59-61,87,96,109-111,113,116-121,123-130,132-134,136-140, 142-158,160-166 ] . В первом режиме, предваряющем передачу данных, в канал связи посылается серия зондирующих импульсов или псевдослучайная последовательность, в соответствии с которой настраивается адаптивный корректор на основе анализа тестовых сигналов. По окончании режима настройки по тесту, ЛІС переходит во второй режим - режим передачи данных, когда информация об искажениях оценивается вероятностно, по мере поступления очередных данных, и в соответствии с этим производится подстройка регулируемых параметров корректора согласно выбранного алгоритма адаптации. По своей структуре, существующие в настоящее время корректоры относятся к смешанному типу, и называются адаптивными корректорами с возможность обучения [4 J .
Важнейшими параметрами любого адаптивного корректора при работе как в автоматическом, так и в рабочем режимах, является время его настройки, т.е. время, за которое начальная погрешность снижается до требуемого значения, при котором возможна устойчивая работа системы передачи данных, а также сложность системы автоматической настройки. Это вызвано тем, что время, затраченное на настройку корректора в автоматическом режиме для передачи данных потеряно. Промежуток времени, затраченный на настройку корректора становится значительным тогда, когда корректор должен часто настраиваться вновь, например, при работе УПС на коммутируемых сетях, или при работе УПС в полудуплексном режиме. В рабочем режиме, при изменениях параметров каналов связи, решающим фактором повышения верности передачи является уменьшение времени перестройки (адаптации) корректора.
Таким образом, гармонический корректор (ПО, с одной стороны - повышает помехоустойчивосить систем связи за счет компенсации линейных искажений, а с другой стороны - снижает пропускную способность систем связи, так как требуется определенное время для настройки корректора в автоматическом и адаптивном режимах для снижения погрешности до требуемого значения.
Настройка корректоров осуществляется с помощью определенных алгоритмов. Время настройки и сложность системы автоматической настройки определяется применяемыми алгоритмами, поэтому разработка высокоэффективных алгоритмов и структур систем автоматической настройки корректоров, реализующих данные алгоритмы, является важной теоретической и практической проблемой.
Состояние вопроса. Кратко остановимся на существующих критериях качества коррекции, применяемых алгоритмах и численных методах оптимизации, положенных в основу алгоритмов настройки ГК и критериях оценки сложности алгоритмов.
Критерием качества коррекции или целевой функцией может быть выбран минимум вероятности ошибки, или косвенно связанные с минимумом вероятности ошибки - среднеквадратичная погрешность - 7 -(СКП), суммарный абсолютный, суммарный обощенный, критерий Чебы-шева и др. [ 15,32,84,96J .
Задача оптимизации заключается в определении значений регулируемых параметров корректора, минимизирующих (максимизирующих) выбранную целевую функцию, т.е. решение задачи оптимизации в математическом плане сводится к отысканию глобального минимума (максимума) целевой функции. В дальнейшем рассматриваются задачи нахождения безусловного экстремума функций многих переменных, т.е. методы оптимизации без ограничений.
Настройка ГК заключается в образовании целевой функции и минимизации её численными методами путем решения систем линейных уравнений: методом Зейделя, методом наискорейшего спуска, методом сопряженных градиентов и др. ^2,6,8-10,15,16,20,23,25,28-32,36, 38,40,41,45-49,52-61,66-68,82,84,87-89,93,95-98,100-103,106-108, II5-I66 ] .
Итерационные*' алгоритмы настройки регулируемых параметров ГК реализуются в виде рекуррентной процедуры
С і (п+і) = С і (п) - oL(n) Ц (п)р где С?- (п) - регулируемые параметры корректора, іь =0,1,2,... - номер итерации, oL(n)- скалярный параметр сходимости (шаг настройки), 1У(п)- некоторый вектор, в направлении которого улучшается выбранный критерий качества коррекции.
Полное время настройки корректора, с одной стороны, определяется скоростью сходимости итерационного процесса, т.е. числом итераций, необходимых для достижения заданной погрешности корректирования, а с другой стороны - сложностью алгоритма, под которой к) итерация - однократное изменение всех регулируемых параметров гармонического корректора. - 8 -понимают количество арифметических операций, необходимых для проведения одной итерации [2,7,31,65-68] .
Итерационные методы решения систем линейных уравнений основаны на следующем подходе. Выбирается исходное состояние регулируемых параметров корректора, обычно С0 (о) = I, Ci (о) » 0, iV О . После того, как начальная точка С-г (о) выбрана, прежде чем получить следующую точку, нужно принять два решения: (I) необходимо выбрать направление Vi(vi) » вдоль которого предполагается расположить следующую точку, и (2) необходимо решить, какой величины шаг (параметр сходимости) oL(yi) должен быть сделан в выбранном направлении.
Изменяя процедуру выбора Щ (п) и оС(п) , можно получить различные методы спуска. Рассмотрим существующие методы спуска.
Часто, независимо от выбора направления Щ(п.) , параметр сходимости выбирают постоянным на всех итерациях [4,12,15,32,52-62,62,96,140 J . При простоте технической реализации, основной недостаток широко используемых в настоящее время алгоритмов настройки корректоров с постоянным параметром сходимости, на основе перечисленных методов, состоит в их медленной сходимости, т.е. в медленном убывании исходной погрешности до требуемой величины.
Для оптимизации скорости сходимости итерационных процессов используют два основных направления при выборе параметра сходимости Ы-(п) [8,66-68] . Первое направление основано на использовании спектральных характеристик участвующих в процессе операторов. Все работы по линейной коррекции, направленные на оптимизацию параметра сходимости при использовании спектрального подхода не дали какого-либо существенного улучшения в скорости сходимости [4,60,129,152,153] .
Второй подход к исследованию и построению итерационных - 9 -процессов основан на методах поиска экстремума [2,8,11,13,16,18, 28-32,40,66-68]. При этом оптимизация скорости сходимости итерационных методов осуществляется последовательно минимизацией некоторого функционала, как правило, квадратичного, который достигает минимального значения на искомом решении системы.
Отметим, что эпитет "оптимальный" указывает на тот факт, что при выбранном методе в качестве следующей точки выбирается точка, лежащая на прямой С^п)- об- 1//и)и являющаяся на этой прямой точкой минимума функционала. Это не означает, что метод обладает какими-либо иными оптимальными свойствами: например, способностью осуществить отыскание минимальной точки функционала за минимальное число итераций, или при минимальном объеме вычислений.
Достоинство вариационных методов типа наискорейшего спуска [28-30,66-68] и итерационного процесса с минимальными невязками [40,66-68] состоит в том, что параметры сходимости выбираются на основе использования апостериорной информации (а не априорной, как при спектральном подходе) о самом решении на каждой итерации в процессе настройки, что существенно повышает эффективность алгоритмов адаптации. Скорость сходимости таких методов не ниже, чем для спектральных методов, использующих полиномы Чебышева[б8] . Кроме того, почти все итерационные методы, основанные на вариационных принципах, имеют ещё одно важное достоинство: в них не накапливаются ошибки вычислений [ЗІ,65j . Ошибка вычислений эквивалентна некоторому ухудшению очередного приближения, но это отразится только на числе итераций, а не на точности окончательного результата. Подобные методы устойчивы даже по отношению к грубым ошибкам (сбоям микропроцессора), если только ошибка не выбрасывает очередное приближение за пределы области сходимости [Зі] .
Однако существенным недостатком перечисленных оптимальных - 10 -универсальных итерационных методов является сложность алгоритмов, а следовательно и сложность (неэкономичность) реализации вычислительного устройства автоматического выбора оптимального параметра сходимости. Так, например, при реализации вычислительного устройства в ГК для определения параметра сходимости по методу наискорейшего спуска, на каждой итерации необходимо произвести прибли-зительно в rft операций умножения и столько же операций сложения (здесь уп. - количество регулируемых параметров корректора) .
Это обстоятельство оказалось настолько существенным, что в существующих и проектируемых системах передачи информации указанные методы и разработанные на их основе устройства настройки корректоров не используются из-за большого объема вычислений, требуемых на каждой итерации.
Постановка задачи. При реализации высокоскоростных УПС на базе цифровой техники предъявляются жесткие требования к быстродействию вычислительных устройств для решения задач цифровой обработки сигналов в реальном масштабе времени Г 14,15,165,166] . Быстродействие любого вычислительного устройства принято характеризовать временем выполнения элементарных арифметических операций [З] . Наиболее ёмкими по числу арифметических операций [I5J являются системы автоматической настройки регулируемых параметров корректора в приемниках УПС, что связано со сложностью решаемой задачи.
О сложности задачи имеет смысл говорить как о сложности алгоритмов, предназначенных для её решения [1,3,7,21,37,42-44, 64,71,90,101J . Чаще всего сложность алгоритма ассоциируется с его быстродействием, т.е. с числом арифметических операций, необходимых для решения задачи [7,71,1141 , что связано со временем - II - вычислений и объёмом памяти, необходимой для реализации вычислений. Для конкретной решаемой задачи временная сложность - это функция, отображающая размерность задачи во время, требуемое для решения задачи. Поведение этой функции в пределе при увеличении размера задачи называется асимптотической временной сложностью[7]. Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если, объём вы- зс числений при решении некоторой задачи пропорционален С-УП , где
С и Уп некоторые постоянные, то говорят, что временная сложность этого алгоритма есть 0(тх), Очевидно, что алгоритмы, решающие задачу размерности ууь (т.е. решение системы линейных уравнений порядка m ) за 0(т) времени, предпочтительнее алгоритмов, решающих её за Of т. J или 0(т!) времени. Таким образом, лишь существенное улучшение алгоритма может внести чувствительный прогресс в эффективность вычислительного процесса. Это может быть только качественный скачок, который изменит теоретическую сложность алгоритма, например, с 0(тх) на 0(т) [70].
На первый взгляд может показаться, что наличие таких универсальных методов решения алгебраических систем, как методы наискорейшего спуска и сопряженных градиентов, и универсальность программ, реализующих эти методы, делает излишними всякие поиски в этом направлении. Однако универсальность математических методов оптимизации, как правило, сопровождается большим объёмом вычислений [ 114 ] . Например, объём вычислений при решении алгебраической системы из УП, уравнений с таким же числом неизвестных (матрица упхщ ) методом сопряженных градиентов, без учета ошибок округлений, требует на весь процесс (3*4)т операций умножения и столько же операций сложения [8j , что затрудняет в настоящее время применение универсальных методов оптимизации в вычислитель- - 12 -ных устройствах настройки ГК для систем передачи данных по коммутируемым сетям связи.
Проблема уменьшения объёма вычислений решается по двум направлениям:
1. В последние годы ведется интенсивный поиск частных способов решения на основе универсальных методов оптимизации, где объём вычислений и погрешности получились бы меньшими [3,7,21,42,62,63, 70,90,92,102,114 J . Применимость таких частных способов определя ется видом матрицы системы, для решения которой они предназнача ются. Например, имеются способы для решения многодиагональных, ленточных, блочных матриц и т.д. Некоторые из этих частных спосо бов получаются экономичными с точки зрения объёма вычислений по сравнению с указанными универсальными методами. Например, имеются методы, объём вычислений в которых пропорционален пъ (метод про гонки в случае ленточной матрицы). В частности, настройка ГК не рекурсивной структуры (без обратной связи) основана на решении систем линейных несовместных уравнений в свёртках, матрица коэф фициентов которых имеет также специальный вид, что, как показано в данной работе позволит получить частные способы решения методов оптимизации при соответствующем уменьшении объёмов вычислений.
2. Второй путь решения проблемы быстродействия при решении задач оптимизации для обработки сигналов в реальном масштабе времени: разработка новых эффективных универсальных методов оптимизации, где объём вычислений и погрешность получились бы меньшими по срав нению с существующими методами оптимизации.
Проблема уменьшения числа итераций, требующихся для отыскания минимума целевой функции с заданной погрешностью, решается на основе известного подхода путем выбора оптимального параметра сходимости в смысле максимально возможной минимизации целевой - ІЗ -функции на каждой итерации.
Целью настоящей работы является повышение эффективности использования пропускной способности коммутируемых каналов связи за счет уменьшения времени вхождения в связь систем передачи данных путем разработки и применения в УПС эффективных устройств настройки гармонических корректоров, реализованных на основе модернизированных, и новых, предлагаемых в работе, алгоритмов и методов оптимизации.
Достижение поставленной цели потребовало решения следующих основных задач: минимизации времени настройки ГК низкочастотной и полосовой структур за счет рационального выбора параметра сходимости в известных алгоритмах настройки, применяемых в настоящее время; разработки и исследования быстродействующих, оптимальных и квазиоптимальных алгоритмов настройки ГК на основе универсальных методов решения систем линейных уравнений в свёртках; разработки и исследования новых, эффективных по скорости сходимости и быстродействию двухшаговых алгоритмов настройки ГК, и алгоритмов настройки ГК, сходящихся к решению за конечное число арифметических операций; экспериментального исследования путем моделирования на ЭВМ процессов настройки и адаптации гармонических корректоров; разработки устройств настройки ГК, реализующих исследуемые алгоритмы.
Структура диссертации. Работа состоит из введения, пяти глав, заключения и библиографии.
В первой главе на основе часто используемых на практике алгоритмов настройки с постоянным параметром сходимости для ГК, устраняющих малые частотные искажения каналов связи, по- - 14 -лучены аналитические выражения оптимальных параметров сходимости, применительно к настройке ГК низкочастотной структуры. Исходя из полученных рекуррентных уравнений (математических моделей) с оптимальными параметрами сходимости, разработаны структурные схемы настройки ГК. Моделированием на ЭВМ исследована скорость сходимости процессов настройки корректоров при использовании разработанных систем настройки, в зависимости от различных исходных искажений и числа регулируемых параметров корректора. Даны практические рекомендации по использованию полученных модернизированных алгоритмов настройки.
Во второй главе диссертации на основе известных методов оптимизации, рассмотренных в первой главе, получены оптимальные по скорости сходимости модернизированные алгоритмы настройки для полосовых ГК, устраняющих малые частотные искажения полосовых каналов связи. На основе математических моделей разработаны структурные схемы настройки ГК. Проведено имитационное моделирование процессов настройки корректоров с использованием полученных систем настройки. Исследована скорость сходимости процессов настройки ГК в зависимости от различных исходных искажений и числа регулируемых отводов.
В третьей главе на основе метода наискорейшего спуска получены частные, оптимальные по скорости сходимости экономичные (быстродействующие) алгоритмы настройки ГК низкочастотной и полосовой структур. Предложены квазиоптимальные (компромиссные) алгоритмы настройки, при использовании которых скорость сходимости процессов настройки выше, чем у алгоритмов с постоянным параметром сходимости, а реализация вычислительных устройств настройки значительно проще, чем реализация оптимальных алгоритмов. Проведено экспериментальное исследование скорости сходимости при - 15 -различных исходных искажениях каналов передачи данных. Проведено сравнение по быстродействию полученных и известных алгоритмов настройки.
В четвертой главе диссертации предложен и исследован итерационный метод оптимизации для решения систем линейных уравнений с высокой скоростью сходимости процессов минимизации. На основе метода разработаны алгоритмы и вычислительные устройства настройки ГК. Моделированием на ЭВМ исследована скорость сходимости процессов настройки.
В пятой главе разработан универсальный экономичный метод минимизации целевой функции для решения систем линейных уравнений, сходящийся к минимуму целевой функции за конечное число шагов. На основе метода разработаны экономичные алгоритмы настройки ГК с высокой скоростью сходимости и высоким быстродействием процессов адаптации.
В заключении приведены основные результаты, полученные в диссертационной работе.
Основные положения, выносимые на защиту:
Модернизированные алгоритмы и устройства настройки ГК с оптимальными параметрами сходимости, обеспечивающие высокую скорость сходимости процессов адаптации ГК при малых исходных линейных искажениях в каналах связи. Полученные расчетные соотношения и разработанные устройства показывают на возможность применения модернизированных алгоритмов для настройки низкочастотных и полосовых ГК в условиях реальных каналов тональной частоты.
Алгоритмы и структурные схемы систем настройки ГК с оптимальными и квазиоптимальными параметрами сходимости, обеспечивающие высокую скорость сходимости процессов адаптации ГК при произволь- ных исходных линейных искажениях в каналах связи. Разработанные устройства обладают высоким быстродействием и могут быть реализованы на микропроцессорах или микро-ЭВМ.
Алгоритмы и устройства настройки ГК, разработанные на основе предложенного двухшагового высокоскоростного метода оптимизации, быстродействие которого на 25-50$ выше по сравнению с известными двухшаговыми методами.
Алгоритмы и устройства настройки ГК, разработанные на основе предложенного метода оптимизации, быстродействие которого в 3-9 раз выше по сравнению с известными методами оптимизации. Разработанные алгоритмы позволяют настроить корректор за конечное число тестовых сигналов.
