Вычислите квадратный корень Используя 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 следующие:

где

если, и в противном случае.

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

где

.

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

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

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

Пример реализации кода MATLAB Гиперболического алгоритма Ядра Векторизации CORDIC следует (для случая скалярного 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-Based

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

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

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

  • установлен в.

  • установлен в.

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

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

где усиление CORDIC как задано выше.

Примечание: для квадратного корня и atanhLookupTable не оказывают влияния на результат. Следовательно, и 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)');

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

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

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

, для некоторых и некоторых даже целое число.

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

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

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

Пример

Вычислите квадратный корень из 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 на Электронно-вычислительных машинах, Volume EC 8, сентябрь 1959, стр 330-334.

  2. Дж.С. Вальтер, "Объединенный Алгоритм для Элементарных функций", Заседания конференции, Компьютерная Конференция по Соединению Spring, май 1971, стр 379-385.

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