В этом примере показано, как вычислить квадратный корень с помощью алгоритма ядра 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 вычислительный алгоритм режима, чтобы вычислить гиперболические функции, такие как гиперболический тригонометрический, квадратный корень, журнал, exp, и т.д.
УРАВНЕНИЯ CORDIC В ГИПЕРБОЛИЧЕСКОМ РЕЖИМЕ ВЕКТОРИЗАЦИИ
Гиперболический режим векторизации является используемым в вычислениях квадратным корнем.
Для режима векторизации уравнения 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
Разумный выбор начальных значений позволяет ядру CORDIC гиперболический алгоритм режима векторизации, чтобы вычислить квадратный корень.
Во-первых, выполняющие шаги инициализации выполняются:
установлен в.
установлен в.
После итераций эти начальные значения приводят к следующему выходу как подходы:
Это может быть далее упрощено можно следующим образом:
где усиление CORDIC как задано выше.
Примечание: для квадратного корня и atanhLookupTable
не окажите влияние на результат. Следовательно, и atanhLookupTable
не используются.
Пример реализации кода 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)');
Джек Э. Волдер, "Тригонометрический Вычислительный Метод CORDIC", Транзакции IRE на Электронно-вычислительных машинах, Volume EC 8, сентябрь 1959, стр 330-334.
Дж.С. Вальтер, "Объединенный Алгоритм для Элементарных функций", Заседания конференции, Компьютерная Конференция по Соединению Spring, май 1971, стр 379-385.