Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: вычисление квадратного корня на tms320f2812
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
alexsl
May 7 2008, 12:31
Добрый день. При построении FSK демодулятора встретился с проблемой. Очень долго вычисляется квадратный корень. Пробовал аппаратную реализацию, как самую быструю:

unsigned int sqrt_user(unsigned long x){
unsigned long m = 0x40000000;
unsigned long y = 0;
unsigned long b;
while(m){
b = y | m;
y >>= 1;
if( x >= b ){
x -= b;
y |= m;
}
m >>= 2;
}
return y;
}

Получилось 400 циклов. Пробовал Cordic алгоритм. Еще больше получается.
Может быть есть у кого реализация, позволяющая уложится в 100 - 160 тактов?
ATname
May 7 2008, 16:07
Цитата(alexsl @ May 7 2008, 16:31) *
Добрый день. При построении FSK демодулятора встретился с проблемой. Очень долго вычисляется квадратный корень. Пробовал аппаратную реализацию, как самую быструю:

unsigned int sqrt_user(unsigned long x){
unsigned long m = 0x40000000;
unsigned long y = 0;
unsigned long b;
while(m){
b = y | m;
y >>= 1;
if( x >= b ){
x -= b;
y |= m;
}
m >>= 2;
}
return y;
}

Получилось 400 циклов. Пробовал Cordic алгоритм. Еще больше получается.
Может быть есть у кого реализация, позволяющая уложится в 100 - 160 тактов?

Есть такая "штука", называется сплайн функция. Вычисление квадратного корня апроксимируется полиномом нужного (в зависимости от точности рассчета) порядка. Обычно третьего за глаза хватает. Формула на работе валяется...
alexsl
May 8 2008, 03:56
Цитата(ATname @ May 7 2008, 20:07) *
Есть такая "штука", называется сплайн функция. Вычисление квадратного корня апроксимируется полиномом нужного (в зависимости от точности рассчета) порядка. Обычно третьего за глаза хватает. Формула на работе валяется...

Поделитесь пожалуйста. Заранее благодарен. smile.gif
1S49
May 8 2008, 04:58
Цитата(alexsl @ May 7 2008, 16:31) *
Может быть есть у кого реализация, позволяющая уложится в 100 - 160 тактов?


Есть на техасщине такая IQmath, дык там квадратный корень за 63 цикла с точностью 29 бит и размером программы 66 слов:

Texas Instruments TMS320C28x IQmath Library is collection of highly optimized and high
precision mathematical Function Library for C/C++ programmers to seamlessly port the floatingpoint
algorithm into fixed point code on TMS320C28x devices. These routines are typically used
in computationally intensive real-time applications where optimal execution speed & high
accuracy is critical. By using these routines you can achieve execution speeds considerable
faster than equivalent code written in standard ANSI C language. In addition, by providing readyto-
use high precision functions, TI IQmath library can shorten significantly your DSP application
development time.
TSerg
May 8 2008, 07:48
Цитата(alexsl @ May 7 2008, 16:31) *


Число итераций около N = Ln( Value)
Можно еще снизить число итераций подбором начального значения div_

function sqrt_newton(value: Int64; var cnt: integer): integer;
var
_div: int64;
begin
cnt := 0;
Result := 0;
if (value <= 0) then Exit;
Result := value;
_div := value;
while (True) do begin
Inc(cnt);
_div := (value div _div + _div) div 2;
if (Result > _div) then
Result := _div
else
break;
end;
end;
alexsl
May 9 2008, 15:10
Цитата(1S49 @ May 8 2008, 08:58) *
Есть на техасщине такая IQmath, дык там квадратный корень за 63 цикла с точностью 29 бит и размером программы 66 слов:

Спасибо smile.gif Буду разбиратся.
1S49
May 9 2008, 15:27
Цитата(alexsl @ May 9 2008, 19:10) *
Спасибо smile.gif Буду разбиратся.

Пожалуйста. Но главным образом благодарите Соединенные Штаты Америки, породившие фирму TI , которая собрала неплохих программистов Америки, Индии, Китая и России и написавших эту библиотеку.
Alex11
May 9 2008, 21:16
Вот еще один вариант, целочисленный корень из лонга. Оптимизирован, правда, под 55хх серию. Там занимает 82 клока. В файлике код на .с для понимания алгоритма, .s55 - оптимизированный. Нажмите для просмотра прикрепленного файла
DS
May 10 2008, 09:25
Странно, у меня вычисление на ADSP-21 занимает 23 такта при аппроксимации 5 порядком вместе с нормализацией/денормализацией.
nicks80
Jun 14 2008, 21:24
Цитата(DS @ May 10 2008, 12:25) *
Странно, у меня вычисление на ADSP-21 занимает 23 такта при аппроксимации 5 порядком вместе с нормализацией/денормализацией.

самое быстрое что пробовал.
unsigned int isqrt(unsigned int x) --- этот тест не прошёл гдето опечатка
{
unsigned int s,g0,g1;
if(x<=4224)
if(x<=24)
if(x<=3) return (x+3)>>2;
else if(x<=8) return 2;
else return (x>>4)+3;
else if(x<=288)
if(x<=80) s=3; else s=4;
else if (x<=1088) x=5; else s=6;
else if(x<=1024*1025-1)
if(x<=257*257-1)
if(x<=129*129-1) s=7; else s=8;
else if(x<=513*513-1) s=9;else s=10;
else if (x<= 4097*4097 -1)
if (x<=2049*2049 -1) s=11;else s=12;
else if(x<=16385*16385-1)
if(x<=8193*8193-1) s=13; else s= 14;
else if(x<=32769*32769-1)s=15;else s=16;
g0=1<<s;
g1 = (g0+(x>>s))>>1;
while(g1<g0) {
g0=g1;
g1=(g0+(x/g0))>>1;
};
return g0;
}



Цитата(1S49 @ May 9 2008, 18:27) *
Пожалуйста. Но главным образом благодарите Соединенные Штаты Америки, породившие фирму TI , которая собрала неплохих программистов Америки, Индии, Китая и России и написавших эту библиотеку.

Код
Да вот это на арме летает просто!!!
проверено в сравнении с sqrt на округление до 1650503060 все ок.
unsigned int isqrt2(unsigned long src) - здесь время константное. самый быстрый что я пробовал метод
{
    unsigned long wrk;
    unsigned int dst;
    int i;
    dst = 0x8000;
    wrk = 0x8000;
    for(i=0; i<16; i++)
    {
         if((long)dst*dst>src) dst &= ~wrk;
         wrk >>= 1;
         dst |= wrk;
    }
    return dst;
}
ATname
Jun 17 2008, 04:27
Цитата(alexsl @ May 8 2008, 07:56) *
Поделитесь пожалуйста. Заранее благодарен. smile.gif

Корень из суммы квадратов х1 и х2 апроксимация четвертого порядка, точность результата не хуже 0.007%.
A*t^4 + D*t^3 + C*t^2 + D*t + E, где
А = -0.011805615, В = -0.105819461, С = 0.535740269, D = -0.004076434, E = 1.000070802
t отношение х2 к х1 если х1>х2 или наоборот, т.е. t должно быть меньше единицы.
sigmaN
Jun 25 2008, 10:10
Слушайте, а как с этим делом на процах с FPU(TMS320F28335)?
IQMath она ведь только для фиксед поинт процов?
у FPU серии там должно быть всё в RTS Library уже оптимизировано, да?
1S49
Jun 25 2008, 11:56
Цитата(sigmaN @ Jun 25 2008, 14:10) *
Слушайте, а как с этим делом на процах с FPU(TMS320F28335)?
IQMath она ведь только для фиксед поинт процов?
у FPU серии там должно быть всё в RTS Library уже оптимизировано, да?


Оптимизировано. Но всегда хочется еще быстрее. sprc664 –это про RTS, sprc624 – это про “не ANSI, но быстро”.
sigmaN
Jun 27 2008, 20:57
Спасибо! sprc624 у меня есть, а вот sprc664 может быть очень полезен in general, так сказать ))
Andrew32768
Jul 23 2008, 18:20
а алгоритм извлечения корня из fixed-point произвольного формата, кто нибудь встречал?
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.