Exponenta Banner
exponenta event banner

Вычислить квадратный корень с помощью CORDIC

Открыть сценарий

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

Введение

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

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

  • 1 поиск в таблице за одну итерацию

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

  • 3 добавления на одну итерацию

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

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

Можно использовать алгоритм режима вычислений CORDIC для вычисления гиперболических функций, таких как гиперболический тригонометрический, квадратный корень, log, 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 Square

Ниже приведен пример реализации кода 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 выше, за исключением того, что 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. Джек Э. Волдер, «Техника тригонометрических вычислений CORDIC», IRE Transactions on Electronic Computers, том EC-8, сентябрь 1959, стр. 330-334.

  2. J.S. Walther, «Единый алгоритм элементарных функций», Материалы конференции, Весенняя совместная компьютерная конференция, май 1971, стр. 379-385.

Документация конструктора фиксированных точек

Поддержка