Аппроксимация квадратного корня из суммы двух квадратов на микроконтроллере

Question

Я работаю над реализацией алгоритма FFT в сборке на 8-битном микроконтроллере (HCS08) для развлечения.Когда алгоритм будет завершен, у меня будет массив из 8-битных вещественных / мнимых пар, и я хочу найти величину каждого из этих значений.То есть, если x является сложным, я хочу найти

|x| = sqrt(Re{x}^2 + Im{x}^2)  

Теперь у меня есть 16-битный регистр и 8-битный регистр.Я думал о том, чтобы просто возвести их в квадрат, сложить и взять квадратный корень из результата, но это создает проблему: максимально возможное значение суммы квадратов двух 8-битных чисел составляет ~ 130k, что больше, чеммаксимальное значение, которое может содержать 16-битный регистр (65,5 КБ).

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

Подводя итог: скажем, у меня есть вектор с двумя 8-битными компонентами, и я хочу найти длину вектора.Как я могу приблизить это без фактического вычисления квадратов и квадратных корней?

Спасибо!

Answer 1

Есть веб-страница, описывающая Оценщик быстрой величины .Основная идея - получить метод наименьших квадратов (или другого высокого качества) для уравнения:

Mag ~= Alpha * max(|I|, |Q|) + Beta * min(|I|, |Q|)

для коэффициентов Альфа и БетаНесколько пар коэффициентов перечислены со среднеквадратическими ошибками, максимальными ошибками и т. Д., Включая коэффициенты, подходящие для целочисленных ALU.

Answer 2

Если сумма больше 65535, разделите ее на 4 (сдвиньте вправо на 2 бита), возьмите квадратный корень и умножьте его на 2. Вы потеряете один бит точности, и, естественно, результат не гарантируется вписывается в 8 бит.

Answer 3

Вы можете быть ограничены только двумя регистрами, но вы можете посмотреть на этот код по адресу http://www.realitypixels.com/turk/opensource/index.html Тригонометрические функции с фиксированной точкой и квадратным корнем с использованием CORDIC

Answer 4

Если впоследствии вы будете преобразовывать величину в дБ, тогда вам вообще не придется выполнять операцию sqrt.Т.е. если ваш расчет:

magnitude = sqrt(re*re+im*im); // calculate magnitude of complex FFT output value
magnitude_dB = 20*log10(magnitude); // convert magnitude to dB

, вы можете переписать это как:

magnitude_sq = re*re+im*im; // calculate squared magnitude of complex FFT output value
magnitude_dB = 10*log10(magnitude_sq);  // convert squared magnitude to dB

Answer 5

Дешевый и грязный метод, который может или не может быть подходящим, состоит в том, чтобы использовать

|x| ~ max(|Re{x}|,|Im{x}|) + min(|Re{x}|,|Im{x})/2;

Это приведет к завышению | x |где-то между 0 и 12%.

Answer 6

Ну, вы можете написать x в полярной форме:

x = r[cos(w) + i sin(w)]

, где w = arctan(Im(x)/Re(x)), поэтому

|x| = r = Re(x)/cos(w)

Здесь нет больших чисел, но, возможно, вы потеряете точность при тригонометриифункции (то есть , если у вас есть доступ к тригонометрическим функциям: - /)