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

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

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

Введение

CORDIC - это аббревиатура для COordinate Rotation DIgital Computer. Алгоритм CORDIC на основе вращения Givens (см. [1,2]) является одним из наиболее аппаратно эффективных алгоритмов, потому что он требует только итерационных операций shift-add. Алгоритм CORDIC устраняет необходимость в явных умножителях и подходит для вычисления множества функций, таких как синус, косинус, арксин, арксозин, арктангенс, векторные величины, деление, квадратный корень, гиперболические и логарифмические функции.

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

  • Поиск по 1 таблице на итерацию

  • 2 сдвиги на итерацию

  • 3 сложения за итерацию

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

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

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

КОРДИЧЕСКИЕ УРАВНЕНИЯ В РЕЖИМЕ ГИПЕРБОЛИЧЕСКОГО ВЕКТОРИРОВАНИЯ.

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

Для режима векторизации уравнения 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 Hyperbolic Vectoring Kernel следует (для случая скаляра x, y, и 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 квадратный корень Расчета

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

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

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

  • $$ x_{0} $$ установлено в.$$ v + 0.25 $$

  • $$ y_{0} $$ установлено в.$$ v - 0.25 $$

После$$ 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 Square Root Kernel следует (для случая скаляра 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 Hyperbolic Vectoring Kernel выше, кроме того 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 $$ количество начальных нулевых самых значащих битов (MSB) в двоичном представлении входов. $$ v $$Эти значения найдены через ряд побитовой логики и сдвигов. Примечание: поскольку должно$$ n $$ быть четным, если количество начальных нулевых MSB является нечетным, делается один дополнительный сдвиг бита, чтобы сделать четным.$$ 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)');

Ссылки

  1. Jack E. Volder, «The CORDIC Trigonometric Computing Technique», IRE Transactions on Electronic Computers, Volume EC-8, September 1959, pp. 330-334.

  2. J.S. Walther, «A Unified Algorithm for Elementary Functions», Conference Proceedings, Spring Joint Computer Conference, May 1971, pp. 379-385.

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

Поддержка

Для просмотра документации необходимо авторизоваться на сайте