Вычислите квадратный корень Используя CORDIC

Открыть скрипт

В этом примере показано, как вычислить квадратный корень с помощью алгоритма ядра CORDIC в MATLAB®. Основанные на CORDIC алгоритмы очень важны для многих встраиваемых приложений, включая блоки управления приводом, навигацию, обработку сигналов и радиосвязи.

Введение

CORDIC является акронимом для Координатного Компьютера Вращения. Основанный на вращении алгоритм CORDIC Givens (см. [1,2]) является одним из большей части оборудования эффективные алгоритмы, потому что это только требует итеративных операций shift-add. Алгоритм CORDIC избавляет от необходимости явные множители и подходит для вычисления множества функций, таков как синус, косинус, arcsine, arccosine, арктангенс, векторная величина, разделитесь, квадратный корень, гиперболические и логарифмические функции.

Фиксированная точка алгоритм CORDIC требует следующих операций:

1 поиск по таблице на итерацию
2 сдвига на итерацию
3 сложения на итерацию

Обратите внимание на то, что для гиперболических основанных на CORDIC алгоритмов, таких как квадратный корень, определенные итерации (i = 4, 13, 40, 121..., k, 3k+1...) повторяются, чтобы достигнуть сходимости результата.

Алгоритмы ядра CORDIC Используя гиперболические режимы расчета

Можно использовать CORDIC вычислительный алгоритм режима, чтобы вычислить гиперболические функции, такие как гиперболический тригонометрический, квадратный корень, журнал, exp, и т.д.

УРАВНЕНИЯ CORDIC В ГИПЕРБОЛИЧЕСКОМ РЕЖИМЕ ВЕКТОРИЗАЦИИ

Гиперболический режим векторизации является используемым в вычислениях квадратным корнем.

Для режима векторизации уравнения CORDIC следующие:

$x_{i+1} = x_{i} + y_{i}*d_{i}*2^{-i}$

$y_{i+1} = y_{i} + x_{i}*d_{i}*2^{-i}$

$z_{i+1} = z_{i} - d_{i}*\mbox{atanh}(2^{-i})$

где

$d_{i} = +1$ если $y_{i} < 0$ , и $$ -1 $$ в противном случае.

Этот режим обеспечивает следующий результат как $$ N $$ подходы $+\infty$ :

$x_{N} \approx A_{N}\sqrt{x_{0}^2-y_{0}^2}$
$y_{N} \approx 0$
$z_{N} \approx z_{0} + \mbox{atanh}({y_{0}/x_{0}})$

где

$A_{N} = \prod_{i=1}^{N}{\sqrt{1-2^{-2i}}}$ .

Обычно $$ N $$ выбирается, чтобы быть достаточно большим постоянным значением. Таким образом, $A_{N}$ может быть предварительно вычислен.

Обратите внимание также, что для квадратного корня мы будем использовать только $x_{N}$ результат.

Реализация MATLAB гиперболического алгоритма векторизации CORDIC

Пример реализации кода MATLAB Гиперболического алгоритма Ядра Векторизации CORDIC следует (для случая скалярного xY, и z). Этот тот же код может использоваться и для фиксированной точки и для типов данных с плавающей точкой.

CORDIC гиперболическое ядро векторизации

k = 4; % Used for the repeated (3*k + 1) iteration steps
for idx = 1:n
    xtmp = bitsra(x, idx); % multiply by 2^(-idx)
    ytmp = bitsra(y, idx); % multiply by 2^(-idx)
    if y < 0
        x(:) = x + ytmp;
        y(:) = y + xtmp;
        z(:) = z - atanhLookupTable(idx);
    else
        x(:) = x - ytmp;
        y(:) = y - xtmp;
        z(:) = z + atanhLookupTable(idx);
    end
    if idx==k
        xtmp = bitsra(x, idx); % multiply by 2^(-idx)
        ytmp = bitsra(y, idx); % multiply by 2^(-idx)
        if y < 0
            x(:) = x + ytmp;
            y(:) = y + xtmp;
            z(:) = z - atanhLookupTable(idx);
        else
            x(:) = x - ytmp;
            y(:) = y - xtmp;
            z(:) = z + atanhLookupTable(idx);
        end
        k = 3*k + 1;
    end
end % idx loop

Расчет квадратного корня CORDIC-Based

Расчет квадратного корня Используя гиперболическое ядро векторизации CORDIC

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

Во-первых, выполняющие шаги инициализации выполняются:

$x_{0}$ установлен в.
$y_{0}$ установлен в.

После $$ N $$ итераций эти начальные значения приводят к следующему выходу как $$ N $$ подходы $+\infty$ :

$x_{N} \approx A_{N}\sqrt{(v + 0.25)^2 - (v - 0.25)^2}$

Это может быть далее упрощено можно следующим образом:

$x_{N} \approx A_{N}\sqrt{v}$

где $A_{N}$ усиление CORDIC как задано выше.

Примечание: для квадратного корня $$ z $$ и atanhLookupTable не окажите влияние на результат. Следовательно, $$ z $$ и atanhLookupTable не используются.

Реализация MATLAB ядра квадратного корня CORDIC

Пример реализации кода MATLAB алгоритма Ядра Квадратного корня CORDIC следует (для случая скалярного x и y). Этот тот же код может использоваться и для фиксированной точки и для типов данных с плавающей точкой.

Ядро квадратного корня CORDIC

k = 4; % Used for the repeated (3*k + 1) iteration steps

for idx = 1:n
    xtmp = bitsra(x, idx); % multiply by 2^(-idx)
    ytmp = bitsra(y, idx); % multiply by 2^(-idx)
    if y < 0
        x(:) = x + ytmp;
        y(:) = y + xtmp;
    else
        x(:) = x - ytmp;
        y(:) = y - xtmp;
    end

     if idx==k
         xtmp = bitsra(x, idx); % multiply by 2^(-idx)
         ytmp = bitsra(y, idx); % multiply by 2^(-idx)
         if y < 0
             x(:) = x + ytmp;
             y(:) = y + xtmp;
         else
             x(:) = x - ytmp;
             y(:) = y - xtmp;
         end
         k = 3*k + 1;
      end
 end % idx loop

Этот код идентичен Гиперболической реализации Ядра Векторизации CORDIC выше, за исключением того, что z и atanhLookupTable не используются. Это - сокращение затрат 1 поиска по таблице и 1 сложения на итерацию.

Пример

Используйте функцию CORDICSQRT, чтобы вычислить аппроксимированный квадратный корень из v_fix использование десяти итераций ядра CORDIC:

step  = 2^-7;
v_fix = fi(0.5:step:(2-step), 1, 20); % fixed-point inputs in range [.5, 2)
niter = 10; % number of CORDIC iterations
x_sqr = cordicsqrt(v_fix, niter);

% Get the Real World Value (RWV) of the CORDIC outputs for comparison
% and plot the error between the MATLAB reference and CORDIC sqrt values
x_cdc = double(x_sqr); % CORDIC results (scaled by An_hp)
v_ref = double(v_fix); % Reference floating-point input values
x_ref = sqrt(v_ref);   % MATLAB reference floating-point results
figure;
subplot(211);
plot(v_ref, x_cdc, 'r.', v_ref, x_ref, 'b-');
legend('CORDIC', 'Reference', 'Location', 'SouthEast');
title('CORDIC Square Root (In-Range) and MATLAB Reference Results');
subplot(212);
absErr = abs(x_ref - x_cdc);
plot(v_ref, absErr);
title('Absolute Error (vs. MATLAB SQRT Reference Results)');

Преодоление ограничений входного диапазона алгоритма

Много алгоритмов квадратного корня нормируют входное значение $$ v $$ , к в области значений [0.5, 2). Эта предварительная обработка обычно делается с помощью фиксированной нормализации размера слова и может использоваться, чтобы поддержать маленькие, а также большие области значений входного значения.

Основанная на CORDIC реализация алгоритма квадратного корня особенно чувствительна к входным параметрам за пределами этой области значений. Функциональный CORDICSQRT преодолевает это ограничение области значений алгоритма посредством подхода нормализации на основе следующих математических отношений:

$v = u * 2^{n}$ , для некоторых $$ 0.5 <= u < 2 $$ и некоторых даже целое число $$ n $$ .

Таким образом:

$\sqrt{v} = \sqrt{u} * 2^{n/2}$

В функции CORDICSQRT значения для $$ u $$ и $$ n $$ , описанные выше, найдены во время нормализации входа $$ v $$ . $$ n $$ количество начального нуля старшие значащие биты (MSBs) в бинарном представлении входа $$ v $$ . Эти значения найдены через серию поразрядной логики и сдвигов. Примечание: потому что $$ n $$ должен быть четным, если количество начального нуля, MSBs является нечетным, сдвиг на один дополнительный бит, сделано сделать $$ n $$ даже. Получившееся значение после этих сдвигов является значением $$ 0.5 <= u < 2 $$ .

$$ u $$ становится входом к основанному на CORDIC ядру квадратного корня, где приближение к $\sqrt{u}$ вычисляется. Результат затем масштабируется тем, $2^{n/2}$ так, чтобы он вернулся в правильной выходной области значений. Это достигается через простой сдвиг разряда $$ n/2 $$ битами. (Левое или правое) направление сдвига зависит от знака $$ n $$ .

Пример

Вычислите квадратный корень из 10-битных входных данных фиксированной точки с маленькой неотрицательной областью значений с помощью CORDIC. Сравните основанные на CORDIC результаты алгоритма с результатами ссылки MATLAB с плавающей точкой по тому же входному диапазону.

step     = 2^-8;
u_ref    = 0:step:(0.5-step); % Input array (small range of values)
u_in_arb = fi(u_ref,0,10); % 10-bit unsigned fixed-point input data values
u_len    = numel(u_ref);
sqrt_ref = sqrt(double(u_in_arb)); % MATLAB sqrt reference results
niter    = 10;
results  = zeros(u_len, 2);
results(:,2) = sqrt_ref(:);

% Compute the equivalent Real World Value result for plotting.
% Plot the Real World Value (RWV) of CORDIC and MATLAB reference results.
x_out = cordicsqrt(u_in_arb, niter);
results(:,1) = double(x_out);
figure;
subplot(211);
plot(u_ref, results(:,1), 'r.', u_ref, results(:,2), 'b-');
legend('CORDIC', 'Reference', 'Location', 'SouthEast');
title('CORDIC Square Root (Small Input Range) and MATLAB Reference Results');
axis([0 0.5 0 0.75]);
subplot(212);
absErr = abs(results(:,2) - results(:,1));
plot(u_ref, absErr);
title('Absolute Error (vs. MATLAB SQRT Reference Results)');

Пример

Вычислите квадратный корень из 16-битных входных данных фиксированной точки с большой положительной областью значений с помощью CORDIC. Сравните основанные на CORDIC результаты алгоритма с результатами ссылки MATLAB с плавающей точкой по тому же входному диапазону.

u_ref    = 0:5:2500;       % Input array (larger range of values)
u_in_arb = fi(u_ref,0,16); % 16-bit unsigned fixed-point input data values
u_len    = numel(u_ref);
sqrt_ref = sqrt(double(u_in_arb)); % MATLAB sqrt reference results
niter    = 16;
results  = zeros(u_len, 2);
results(:,2) = sqrt_ref(:);

% Compute the equivalent Real World Value result for plotting.
% Plot the Real World Value (RWV) of CORDIC and MATLAB reference results.
x_out = cordicsqrt(u_in_arb, niter);
results(:,1) = double(x_out);
figure;
subplot(211);
plot(u_ref, results(:,1), 'r.', u_ref, results(:,2), 'b-');
legend('CORDIC', 'Reference', 'Location', 'SouthEast');
title('CORDIC Square Root (Large Input Range) and MATLAB Reference Results');
axis([0 2500 0 55]);
subplot(212);
absErr = abs(results(:,2) - results(:,1));
plot(u_ref, absErr);
title('Absolute Error (vs. MATLAB SQRT Reference Results)');

Ссылки

Джек Э. Волдер, "Тригонометрический Вычислительный Метод CORDIC", Транзакции IRE на Электронно-вычислительных машинах, Volume EC 8, сентябрь 1959, стр 330-334.
Дж.С. Вальтер, "Объединенный Алгоритм для Элементарных функций", Заседания конференции, Компьютерная Конференция по Соединению Spring, май 1971, стр 379-385.

Документация

Вычислите квадратный корень Используя CORDIC

Введение

Алгоритмы ядра CORDIC Используя гиперболические режимы расчета

Реализация MATLAB гиперболического алгоритма векторизации CORDIC

Расчет квадратного корня CORDIC-Based

Реализация MATLAB ядра квадратного корня CORDIC

Ссылки

Документация Fixed-Point Designer

Поддержка