Вычисление модуля комплексного числа

Операция вычисления модуля комплексного числа или вектора встречается в обработке сигналов практически повсеместно. Начиная от амплитудной модуляции и корреляции и заканчивая вычислением различных метрик таких как EVM. Рассмотрим один из алгоритмов, который позволит решить эту задачу без вычисления квадратного корня.

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

Magnitude = sqrt(Re*Re + Im*Im) # псевдокод

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

Magnitude ~= Alpha * max(|I|, |Q|) + Beta * min(|I|, |Q|) # псевдокод

С первого взгляда данное преобразование может показаться весьма замысловатым и не очевидным, но если разобрать его последовательно по шагам, то все встает на свои места. Возьмем произвольное комплексное число Z:

Z = 6.66 - j9.99 #псевдокод

Отобразим наше число на комплексной плоскости:

Первая операция - это вычисление модуля. Она перенесет наш вектор в первую четверть координатной плоскости:

Z = |6.66| + j|-9.99|  = 6.66 + j9.99 #псевдокод

Посмотрим как это выглядит на комплексной плоскости:

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

Вот и все, никаких трюков. Такой вектор можно довольно точно и монотонно аппроксимировать линейной комбинацией его проекций на оси. Ах да, остались же еще пресловутые коэффициенты Alpha и Betha. 

Будем надеться, что вы не успели подумать, что это все я сам придумал. Когда этот алгоритм опубликовал в открытом доступе Grant Griffin я еще рисовал флажки и кружочки в начальной школе. Собственно к этому алгоритму он предложил набор коэффициентов для вычисления аппроксимированного модуля с минимальной RMS ошибкой, минимальной пиковой ошибкой, минимальной RMS ошибкой, когда один из коэффициентов равен "1" и т.д. : 

=====================================================================
             Alpha * Max + Beta * Min Magnitude Estimator

Name                  Alpha           Beta       Avg Err   RMS   Peak
                                                 (linear)  (dB)  (dB)
---------------------------------------------------------------------
Min RMS Err      0.947543636291 0.392485425092   0.000547 -32.6 -25.6
Min Peak Err     0.960433870103 0.397824734759  -0.013049 -31.4 -28.1
Min RMS w/ Avg=0 0.948059448969 0.392699081699   0.000003 -32.6 -25.7
1, Min RMS Err   1.000000000000 0.323260990000  -0.020865 -28.7 -23.8
1, Min Peak Err  1.000000000000 0.335982538000  -0.025609 -28.3 -25.1
1, 1/2           1.000000000000 0.500000000000  -0.086775 -20.7 -18.6
1, 1/4           1.000000000000 0.250000000000   0.006456 -27.6 -18.7
Frerking         1.000000000000 0.400000000000  -0.049482 -25.1 -22.3
1, 11/32         1.000000000000 0.343750000000  -0.028505 -28.0 -24.8
1, 3/8           1.000000000000 0.375000000000  -0.040159 -26.4 -23.4
15/16, 15/32     0.937500000000 0.468750000000  -0.018851 -29.2 -24.1
15/16, 1/2       0.937500000000 0.500000000000  -0.030505 -26.9 -24.1
31/32, 11/32     0.968750000000 0.343750000000  -0.000371 -31.6 -22.9
31/32, 3/8       0.968750000000 0.375000000000  -0.012024 -31.4 -26.1
61/64, 3/8       0.953125000000 0.375000000000   0.002043 -32.5 -24.3
61/64, 13/32     0.953125000000 0.406250000000  -0.009611 -31.8 -26.6
=====================================================================

Сам Grant Griffin отмечает, что некоторые коэффициенты ему предоставил S. Clay. Приводить пример реализации этого алгоритма на одном из языков программирования я считаю излишним ввиду его простоты.

Хочется отметить, что порой знание о существовании подобных трюков может очень сильно выручить. Меня однажды выручил алгоритм приближенного вычисления логарифма при проектировании АРУ. Не исключаю, что и его мы тоже разберем.

p.s. Первоисточником этого алгоритма указывается раздел авторства R. Lyons в книге Digital Signal Processing in Communications Systems под редакцией Marvin Frerking. Вот на нее ссылка.