CORDIC

CORDIC (Метод CORDIC от англ. COordinate Rotation DIgital Computer — цифровой вычислитель поворота системы координат; метод «цифра за цифрой», алгоритм Волдера) — итерационный метод сведения прямых вычислений сложных функций к выполнению простых операций сложения и сдвига.

Идея метода

Идея метода заключается в сведении вычисления значений сложных (например, гиперболических) функций к набору простых шагов — сложению и сдвигу.

Такой подход особенно полезен при вычислении функций на устройствах с ограниченными вычислительными возможностями, такими как микроконтроллеры или программируемые логические матрицы (FPGA). Кроме того, поскольку шаги однотипны, то при аппаратной реализации алгоритм поддаётся развёртыванию в конвейер либо свертыванию в цикл.

История

Метод впервые был описан в применении к вычислению тригонометрических функций и операций преобразования координат Джеком Волдером в 1956 году, затем в 1959 году. В 1956 году Акушский и Юдицкий выдвинули аналогичную идею для вычисления показательных и логарифмических функций. Первоначально же близкая к этому идея была предложена Генри Бриггсом в 1624 году при составлении им таблиц логарифмов.

Метод Бриггса

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

Например, Бриггс умножал значение аргумента функции десятичного логарифма $\log X$ на константы вида: $1+10^{-i}$ либо $1-10^{-i}$.

При этом выбор первого множителя ($1+10^{-i}$) осуществлялся в том случае, если текущее значение величины $X$ оказывалось меньше единицы, а второго — в том случае, если текущее $X$ было больше единицы. Выбирая последовательно значения показателя степени от 1 до $N$, где $10^{-N}$ являлось максимальной допустимой ошибкой вычислений, Бриггс сводил значение $X$ с требуемой точностью к единице, а тем самым значение функции $\log X$ к нулю.

Однако, для равносильности указанных преобразований необходимо одновременно с умножением текущего $X$ на $1+10^{-i}$ делить указанное значение на ту же самую величину. Но, как известно, логарифм частного равен разности логарифмов числителя и знаменателя. Следовательно, одновременно с умножением текущего $X$ на $1+10^{-i}$ необходимо заранее вычисленную функцию логарифма значения $1+10^{-i}$ отнимать от произведения аргумента $X$ на множитель $1+10^{-i}$ .

Значения всех констант вида $1+10^{-i}$ и $1-10^{-i}$ могут быть вычислены заранее, поскольку их относительно немного. Например, при допустимой ошибке $10^{-6}$ их всего двенадцать.

Остаётся пояснить, что умножение на константы вида $1+10^{-i}$ и $1-10^{-i}$ сводится к операциям сложения, вычитания и переноса запятой (сдвига).

Следовательно, процедура вычисления функции десятичного логарифма по Бриггсу сводится к операциям сложения, вычитания и десятичного сдвига.

Обобщение идеи метода Бриггса на комплексные числа было осуществлено в середине-конце пятидесятых годов Джеком Волдером и почти одновременно с ним Акушским и Юдицким. Это позволило вычислять тригонометрические функции.

Режим работы

CORDIC может быть использован для расчета ряда различных функций. Это объяснение показывает, как использовать CORDIC в режиме вращения для расчета синуса и косинуса угла. Предполагается, что желаемый угол задается в радианах и результаты представлены в формате с фиксированной запятой. Чтобы определить синус или косинус угла $\beta$, должны быть найдены координаты точки у или х на единичной окружности в соответствии с желаемым углом. Используя CORDIC, мы начинаем с вектора $v_0$:

$v_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$

В первой итерации этот вектор будет вращаться на 45° против часовой стрелки, чтобы получить вектор $v_1$. Последовательные итерации будут вращать вектор в одном или другом направлении с уменьшающимся шагом, пока желаемый угол не будет достигнут. Величина i-ого шага — arctan(1/(2ⁱ⁻¹)), для i = 1, 2, 3, ….

Иллюстрации алгоритма CORDIC.

Более формально, на каждой итерации вычисляется вращение, которое осуществляется путем умножения вектора $v_{i-1}$ на матрицу поворота $R_{i}$:

$v_{i} = R_{i}v_{i-1}\$

Матрицы вращения R определяются по формуле:

$R_{i} = \left( \begin{array}{rr} \cos \gamma_{i} & -\sin \gamma_{i} \\ \sin \gamma_{i} & \cos \gamma _{i}\end{array} \right)$

Используя следующие два тригонометрические тождества

$\begin{align} \cos \alpha & = & {1 \over \sqrt{1 + \tan^2 \alpha}} \\ \sin \alpha & = & {{\tan \alpha} \over \sqrt{1 + \tan^2 \alpha}} \end{align}$

получаем матрицу поворота:

$R_i = {1 \over \sqrt{1 + \tan^2 \gamma_i}} \begin{pmatrix} 1 & -\tan \gamma_i \\ \tan \gamma_i & 1 \end{pmatrix}$

Выражение для поворачиваемого вектора $v_i = R_i v_{i-1}$:

$v_i = {1 \over \sqrt{1 + \tan^2 \gamma_i}} \begin{pmatrix} x_{i-1} &-& y_{i-1} \tan \gamma_i \\ x_{i-1} \tan \gamma_i &+& y_{i-1} \end{pmatrix}$

где $x_{i-1}$ и $y_{i-1}$ компоненты $v_{i-1}$. Ограничивая значения углов $\gamma_{i}$ так что $\tan \gamma_{i}$ принимает значения $\pm 2^{-i}$ умножение на тангенс можно заменить делением на степень двойки, которое эффективно реализовано в цифровом аппаратном обеспечении компьютера с помощью битового сдвига. Получаем выражение:

$v_i = K_i \begin{pmatrix} x_{i-1} &-& \sigma_i 2^{-i} y_{i-1} \\ \sigma_i 2^{-i} x_{i-1} &+& y_{i-1} \end{pmatrix}$

где

$K_i = {1 \over \sqrt{1 + 2^{-2i}}}$

и $\sigma_i$ может иметь значения −1 или 1 и используется для определения направления вращения: если угол $\beta_i$ является положительным, то $\sigma_i$ равняется 1, в противном случае он равен −1.

Мы можем игнорировать $K_i$ в итерационном процессе, а затем применить его потом для получения коэффициента масштабирования:

$K(n) = \prod_{i=0}^{n-1} K_i = \prod_{i=0}^{n-1} 1/\sqrt{1 + 2^{-2i}}$

который рассчитывается заранее и хранится в таблице, или как одна константа, если число итераций фиксировано. Эта поправка также может быть сделана заранее, путем масштабирования $v_0$.

Единственная задача которая осталась, это определить по часовой стрелке или против часовой стрелки должно выполнятся вращение на каждой итерации (выбор значения $\sigma$). Это делается путем отслеживания величины поворота на каждой итерации и вычитания из желаемого угла, а затем проверки, если $\beta_{n+1}$ является положительным, то мы должны вращаться по часовой стрелке или если он отрицательный, мы должны вращаться против часовой стрелки, чтобы приблизится к углу $\beta$.

$\beta_{i} = \beta_{i-1} - \sigma_i \gamma_i. \quad \gamma_i = \arctan 2^{-i},$

Значения $\gamma_n$ также должны быть посчитаны заранее. Но для малых углов $\arctan(\gamma_n) = \gamma_n$ в представлении с фиксированной точкой, что позволяет снизить размер таблицы.

Как видно на иллюстрации выше, синус угла $\beta$ является y координатой окончательного вектора $v_n$, а x координата — значением косинуса.

Литература

• Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, September 1959
• Daggett, D. H., Decimal-Binary conversions in CORDIC, IRE Transactions on Electronic Computers, Vol. EC-8 #5, pp 335—339, IRE, September 1959.
• J. E. Meggitt, Pseudo Division and Pseudo Multiplication Processes, IBM Journal, April 1962.
• Байков В. Д. Вопросы исследования вычисления элементарных функций по методу «цифра за цифрой», автореферат диссертации на соискание учёной степени кандидата технических наук, Ленинград, ЛЭТИ, 1972
• Schmid, Hermann, Decimal computation. New York, Wiley, 1974
• Байков В. Д., Смолов В. Б. Аппаратурная реализация элементарных функций в ЦВМ, Ленинград, изд-во ЛГУ, 1975, 96 стр.
• Байков В. Д., Селютин С. А., Вычисление элементарных функций в ЭКВМ, Москва, Радио и связь, 1982, 64 стр.
• Байков В. Д., Смолов В. Б. Специализированные процессоры: итерационные алгоритмы и структуры, Москва, «Радио и связь», 1985, 288 стр.
• Andraka, Ray, A survey of CORDIC algorithms for FPGA based computers
• Henry Briggs, Arithmetica Logarithmica. London, 1624, folio
• CORDIC Bibliography Site, Shaoyun Wang, July 2011
• CORDIC Bibliography Site