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

Введение

Переход на цифровые методы обработки ин­формации предполагает оптимизацию мето­дов реализации функциональных зависимо­стей, определяющих характеристики специализированных вычислителей (СВ) радиотех­нических систем [1, 2]. Правильный выбор физических эталонов, узлов интерполяции по­линомов наилучшего приближения Чебышёва при калибровке обеспечивает повышение точностных характеристик измерительных систем, находящихся в эксплуатации [3, 4], в несколько раз. Высокая эффективность СВ достигается за счет упрощения, адаптации вычислительных алгоритмов к более узкому классу задач и требований по точности пу­тем минимизации разрядных сеток [2, 5, 6]. Так, например, измерительный канал с вось­миразрядными аналого-цифровыми преобра­зователями (АЦП) и СВ при использовании специальных методов обработки информации могут обеспечить погрешность результата δ_ρ менее единицы (1/256) младшего разряда представления выходной информации в дво­ичной системе, т. е. соответствовать прибору с приведенной относительной погрешностью 0,195 % класса точности 0,2/0,1.

В СВ для приближения стандартных функций, воспроизведения рабочих эталонов, калибровки измерительных систем широко применяется полиномиальный метод. Аппроксимируем функцию f (x) с помощью полино­ма степени n

При этом ограничение числа операций и устранение избыточной точности результата достигается путем ограничения числа членов в полиноме (1), начиная с (n + 1)-й степени, исходя из оценки максимального значения по­грешности метода δ_{max м} в полиноме Чебышёва

Здесь  - производная   (n +1) -го порядка на интервале аппроксимации;

f (x) - L_n (х) = δ_τ - текущая погрешность метода воспроизведения функции.

Необходимо проводить оптимизацию ко­эффициентов полинома, когда имеет место изменение значений производной f^{[ я}+^1]( x). Важно правильно выбрать интервал аппрок­симации в полиноме (1) [2, 7, 8].

Улучшению методов воспроизведения типовых функциональных зависимостей, ис­пользуемых в вычислительных процедурах ос­новных алгоритмов работы радиолокационных устройств, с позиций оптимизации критериев вычислительного процесса (точностных ха­рактеристик, быстродействия и программно­аппаратных затрат) посвящен ряд работ [2, 6-8]. Однако в указанных работах по большей степени рассмотрены конечные результаты со­вершенствования непосредственно численных методов воспроизведения типовых функцио­нальных зависимостей, не приведены конкрет­ные методы математического моделирования, компьютерной математики, которая развивается как научное направление на стыке мате­матики и информатики. Кроме того, в них не рассмотрены вопросы уменьшения времени для реализации компьютерных программ по­иска оптимальных алгоритмов.

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

Совершенствование методов моделирования и оптимизации вычислительных алгоритмов

На первом этапе оптимизация процесса вы­числения полинома (1) производится путем минимизации числа вычислительных опера­ций А и числа обращений к памяти m при за­данных значениях погрешности δ_{max. м}.

Поиск проводится в соответствии со стратегией максимальной идентичности гра­фиков функции f (x) или преобразователь­ной характеристики датчика измерительной системы и приближающего полинома L_n (х) [7, 8]. При этом исключаются неэффектив­ные, оказывающие меньшее влияние на зна­чение погрешности δ_maxм члены ряда a_i xⁱ , константы a_i, например, когда задаются а₀ = 0, а₁ = 1, используются только четные (нечетные) члены ряда и т. п. В усеченном полиноме наилучшего приближения L_n (x) с m < n +1 оставшимися константами a_i на интервале аппроксимации обеспечивает­ся, по крайней мере (m +1) точек, в кото­рых с учетом неустранимых погрешностей Δδ_maxм погрешности δ_maxм принимают рав­ные максимальные значения +(δ_maxм ± Δδ_maxм ) и -(δ_maxм ± Δδ_maxм ) (рис 1). По сравнению с полиномом (1) для уменьшения числа членов, констант полинома требуется меньшее число операций, узлов аппроксимации и физиче­ских эталонов, как при вычислении функций, так и при калибровке измерительного канала системы.

При компьютерном моделировании обе­спечивается возможность получить полиномы наилучшего приближения, например, с 16 де­сятичными цифрами результата. В то же время уже с тремя десятичными верными цифрами фактически можно обеспечить десятиразряд­ное представление результата в двоичной си­стеме счисления. Такое представление потен­циально обеспечивает возможность получить приведенную относительную погрешность ре­зультата порядка 0,05-0,1 %. В измерительном канале с аналоговым датчиком, работающим на восьмиразрядном АЦП, принципиально можно уменьшить приведенную относитель­ную погрешность системы обработки инфор­мации до значений 2^-9 · 100...2^-8 · 100 %.

Работающие с датчиками и системами АЦП имеют примерно равный двум двоич­ным разрядам дискрет приращения разряд­ности. Для оптимизации аппаратурных за­трат путем устранения избыточной точности СВ, реализуемые на программируемых ло­гических интегральных схемах (ПЛИС), це­лесообразно проектировать с переменной и минимальной разрядностью. При меньшем числе разрядов существенно снижаются про­граммно-аппаратурные затраты на реализацию ПЛИС и повышается быстродействие СВ. По этим причинам актуально уменьшение разряд­ных сеток операндов СВ при приемлемом со­хранении заданных точностных характеристик систем в целом. Однако в реальных условиях при обработке информации, воспроизведе­нии функций возникает дополнительная со­ставляющая погрешности δ_к, обусловленная квантованием констант полинома с урезанием разрядных сеток в полиноме (1): δ_к = Δα_0ρ + + Δα_1ρ х + Δα_2ρ x² + ... + Δα_nρ xⁿ.

Обеспечим уменьшение погрешности δ_Γ, на выходе СВ системы, определяемой как сум­ма погрешностей метода δ_м квантованного представления δ_αί набора констант a_i, промежуточных преобразований δ_пр с ограничен­ным числом разрядов в форматах данных СВ. В связи с этим на втором этапе оптимизации вычислительного алгоритма производится та­кое сокращение разрядных сеток СВ, чтобы погрешность результата не увеличивалась бо­лее чем на 5-10 % от погрешности δ_{max . м}. При возрастании значений аргумента график по­грешности δ_m полинома наилучшего прибли­жения в полиноме (1) представляет знакочере­дующуюся функцию (см. рис. 1). Его формой можно управлять, меняя узлы аппроксимации или коэффициенты в полиноме. Значения по­грешностей урезания констант a_i определя­ют степень наклона линейной функции a_ix и растяжения парабол a_ixⁱ и монотонно воз­растают по абсолютной величине с ростом аргумента E. В то же время в совокупности графики комбинаций парабол с разным зна­ком, например, y = ∆a₃x³ -∆a₁X¹, функции δ_к = = Δα_0р + Δα_1ρx + Δα_2ρx² + ... + Δα_nρxⁿ при опре­деленных соотношениях квантованного пред­ставления δ_αί набора констант a_t могут напо­минать графики погрешностей аппроксима­ции полиномом наилучшего приближения (см. рис. 1), в том числе и с противоположными знаками.

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

Компенсацию можно реализовать мето­дом простого перебора всех возможных вза­имных комбинаций отклонений констант в пределах определенного числа последних отбрасываемых цифр с фиксацией каждый раз наименьшего значения δ_р. Общее число ком­бинаций составляет j = s^m (где m < n - ко­личество коэффициентов полинома; s - число перебираемых вариантов для одной констан­ты a_i), но при таком подходе при s = 1000 и m = 7 получим 1000⁷ вариантов перебора. Для значительного уменьшения числа вариантов перебора (итераций) осуществляется после­довательное урезание одной или определен­ного числа разрядных цифр с последующей проверкой только максимального значения погрешности и сравнения ее с ранее полу­ченным значением δ_{max . м}. Поиск полиномов с урезанием разрядных сеток операндов про­водится до таких критических минимальных значений числа значащих цифр констант, ког­да их последовательное сокращение еще не оказывает практического влияния на погреш­ность δ_ρ (например, увеличение δ_ρ по сравне­нию с δ_{max. м} на 1-2 %). После этого урезается еще одна разрядная цифра, определяется число итераций комбинаций (в данном случае 10⁷ ) и запускается цикл перебора массива пробных коэффициентов (рис. 2).

Этот цикл выполняется методом прямо­го перебора по всем возможным комбинаци­ям значений коэффициентов. Для очередной итерации определяется максимальная погреш­ность, которая сравнивается с предыдущим значением. Коэффициенты с меньшим значе­нием погрешности запоминаются. По оконча­нии цикла фиксируются коэффициенты с наи­меньшим значением погрешности результата. Если значение погрешности δ_p превышает зна­чение δ_maxм на 5-10 %, то число разрядных цифр увеличивается на 1. С помощью разра­ботанного графического интерфейса резуль­таты моделирования с параметрами полинома и графика погрешности выводятся на экран. 

В соответствии с вышеизложенным, были разработаны методы поиска полиномов наилучшего приближения в средах програм­мирования MathCad, Delphi, Builder C+ + [8]. Перед проведением эксперимента вводится количество членов полинома (например, 3), аппроксимируемая функция (arcsin(x)), нача­ло и конец интервала (0 и π/4), определяется наличие только членов полинома с нечетной степенью. Под надписью «Экстраполяция» находится указатель «Есть», который обозна­чает присутствие члена полинома а₀. В следу­ющем за этой надписью окне задается число десятичных цифр после запятой. Командой «Пуск» задается полином Ньютона, а с помо­щью команды «Улучш.» он превращается в по­лином наилучшего приближения. В програм­ме предусмотрена последующая компенсация составляющих погрешностей результата при урезании разрядных сеток.

Оптимизированный набор алгоритмов вычисления функции arcsin (л)

Специализированные вычислители широко используются в приборах для генерации гар­монических сигналов, в быстродействующих цифровых вычислительных синтезаторах с аппаратурной реализацией воспроизведения функций sin(x), tg(x), arcsin(x) [8]. Для вы­числения функции arcsin (x) одного полино­ма при изменении значения аргумента x от -1 до 1 для максимальных значений погреш­ностей аппроксимации δ_maxм в диапазоне 0,15-0,0015 обеспечивается незначительное приращение числа значащих цифр результа­та на одну операцию при последовательном увеличении степени полинома с первой до девятой и выше. Исходя из этого, для поиска набора полиномов с большим увеличением значений приращения числа двоичных цифр результата на одну операцию был исследован интервал [0; 0,707].

В соответствии с разработанными алго­ритмами поиска полинома наилучшего при­ближения для функции arcsin(x) в интерва­ле значений аргумента [0; 0,707] при часто используемой на практике области значений угла [0°; 45°] для диапазона 2,09851 10^-2­6,229703 10^-9 погрешностей δ_maxм получены полиномы с нечетными степенями (табл. 1). Уменьшение погрешности для полинома тре­тьей степени по сравнению с полиномом пер­вой степени составит 20,98/1,6 = 13,1. Тогда для полиномов пятой степени по сравнению с третьей степенью уменьшение погреш­ности составит 16,02/1,628 = 9,84, седьмой степени по сравнению с пятой степенью - 16,28/1,897 = 8,582, девятой степени по срав­нению с седьмой степенью - 18,97/2,392 = = 7,93, 11-й степени по сравнению с девятой степенью - 23,92/3,188 = 7,5. В среднем име­ем приращение порядка одной разрядной дво­ичной цифры на одну операцию. Проведено исследование возможности уменьшения дис­крета приращения числа операций путем фак­тического исключения константы a_i в полино­ме (принимаем а_х = I, полином № 2' в табл. 1).

В данном случае уменьшение числа операций на 1 обеспечивает уменьшение погрешности по сравнению с полиномом первой степени только в 20,98/1,96 = 2,63 раза.

Для поиска полиномов с возможным большим увеличением значения приращения числа двоичных цифр результата на одну опе­рацию интервал [0; 0,707] был разбит на два подынтервала с двумя полиномами от первой до седьмой степени с примерно одинаковы­ми погрешностями δ_{max м} на подынтервалах (табл. 2). Для двух полиномов первой степени не обеспечено уменьшение погрешности δ_{max м} по сравнению с полиномом третьей степени P(x) = x(0,9895 + 0,2379x²) с одним интерва­лом интерполяции и одинаковым количеством операций, равным 6. В то же время для двух полиномов седьмой степени с общим числом операций, равным 16, максимальное значение погрешности составит 5,35 10^-7.

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

без компенсации погрешность составила δ_р = = 7,83 · 10^-8.

С компенсацией для полинома она равна δ_ρ = 6,2 · 10^-9, т. е. погрешность уменьшилась в 7,83 · 10^-8/6,2 · 10^-9 = 12 раз.

Введение сокращенного интервала для значений угла от 0° до 45° обеспечивает при­ращение одной двоичной цифры результата на одну операцию, что примерно в 3 раза больше приращения для значений углов от 0° до 90°. При взаимной компенсации составляющих погрешностей результата обеспечено умень­шение разрядных сеток операндов для поли­номов седьмой степени и выше примерно на два-три двоичных разряда.

Заключение

В средах программирования MathCad, Delphi, Builder C++ разработаны программы поис­ка полиномов наилучшего приближения для воспроизведения функциональных зависимо­стей с взаимной компенсацией составляющих погрешностей результата. Созданы алгорит­мы вычисления функции arcsin(x) с устра­нением избыточной точности путем обеспе­чения последовательного дискретного при­ращения 1-3 двоичных цифр результата при возрастании сложности алгоритмов не более чем на 2-5 операций в диапазоне представ­ления выходных данных приборов и систем 3-32 двоичными разрядами. Математическое моделирование вычислительных алгоритмов обеспечило сокращение разрядных сеток СВ на 2-5 двоичных разряда.