• Регистрация
hex oct bin
hex oct bin +17.80
н/д
  • Написать
  • Подписаться

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

    Операция вычисления модуля комплексного числа или вектора встречается в обработке сигналов практически повсеместно. Начиная от амплитудной модуляции и корреляции и заканчивая вычислением различных метрик таких как 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. Вот на ее ссылка.

Теги

      29.08.2020

      Комментарии

      • aBoomest
        aBoomest+359.36
        31.08.2020 08:51

        А физического или геометрического смысла у этого всего случайно не имеется? Еще всегда у такого интересно как рассчитываются коэффициенты?

        • hex oct bin
          hex oct bin +17.80
          31.08.2020 10:14

          Оригинальные коэффициенты из первоисточника это (1.0, 0.4) как они были получены я поищу ответ на этот вопрос. Ну а с MIN RMS и т.д. более менее очевидно, скоре всего они получены машинным перебором в окрестности оригинальных.

          • aBoomest
            aBoomest+359.36
            31.08.2020 11:14

            Спасибо.

            • hex oct bin
              hex oct bin +17.80
              31.08.2020 20:27

              Оригинальный алгоритм Р. Лайонц изложил в статье Lyons, R. G. “How Fast Must You Sample,” Test and Measurement World, November 1988. К сожалению материалы этой конференции у меня не получилось найти. Если у кого-нибудь получится буду крайне благодарен. В остальных публикациях он кочует, как есть, только набор коэффициентов продолжает пополняться с каждым годом.