5.8. Вычислительная сложность и CORDIC–арифметика

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

Таблица 5.1. Вычислительная сложность

Алгоритм	х	÷		±
МНК	2	0	0	2
Градиентная решетка	6	1	0	6
РНК	6	6	0	7
НККРНК	10	2	3	6

Количество вычислительных операций для решетчатого фильтра в 3 – 6 раз превышает количество вычислительных операций для простейшего адаптивного фильтра на линии задержки с отводами (МНК). Однако это увеличение вычислительной сложности приводит к существенно более быстрой сходимости, к лучшим численным значениям коэффициентов и обеспечивает гарантию устойчивости фильтра. В табл. 5.1 дана оценка сложности нескольких адаптивных алгоритмов. Масштабирование производится с помощью постоянного весового коэффициента (например,  или  обычно аппроксимируются как сдвиг показателя степени на 2). Таким образом, это фиксированное масштабирование не включается в число операций. МНК – алгоритм является градиентным методом наименьших квадратов, используемым для линии задержки с отводами. Градиентным решетчатым алгоритмам соответствуют выражения (5.22) и (5.18). Алгоритм 5.3 обозначается как РНК, а алгоритм 5.4 – как НККРНК. Число операций подсчитано для случая, когда единственный каскад фильтра выполняет обработку единственной выборки данных. Чтобы фильтр - го порядка обрабатывал  выборок данных, потребовалось бы в раз больше вычислений.

Самым сложным из этих алгоритмов является НККРНК – алгоритм; чтобы осуществить корректировку для каждого каскада решетки при каждой новой выборке данных, требуется три раза извлекать квадратный корень, 10 раз умножать и два раза делить. Однако, НККРНК – алгоритм имеет очень компактную форму, содержащую всего лишь три уравнения, переменные которых имеют ограниченные величины. Для аппаратной реализации НККРНК – уравнений потребовался бы специальный аппаратно реализованный умножитель повышенного быстродействия, а при использовании микропроцессоров общего назначения потребовалось бы значительное время для выполнения расчетов. Даже при использовании сдвига и сложения вместо умножения и метода Ньютона для операций извлечения квадратного корня необходимо было бы затратить значительное время на расчеты.

В результате использования вращающейся системы координат для интерпретации решетчатых уравнений в работе [9] была разработана эффективная реализация решетчатого алгоритма, нормированного на корень квадратный, и использующего CORDIC – арифметику. Цифровой компьютер во вращающейся системе координат, разработанный Волдером [316], представляет аппаратную реализацию итеративного алгоритма для расчета тригонометрических функций, выполнения операций умножения, деления и извлечения квадратного корня. CORDIC – алгоритм интерпретирует перечисленные функции как вращения вектора в различных системах координат. Это вращение осуществляется в результате последовательных операций сдвига и сложения. Такой тип арифметики не нов; он применялся для вычисления прямых и обратных тригонометрических функций в микрокалькуляторах. Многие другие алгоритмы обработки сигнала, например дискретное преобразование Фурье (ДПФ) и обращение матриц, также могут выполняться в массивах памяти CORDIC – процессоров [12].