CORDIC

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

Идея метода

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

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

История

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

Метод был использован при реализации некоторых видов инструкций с плавающей точкой в математических сопроцессорах Intel, включая 8087[1][2][3][4][5], 80287[5][6], 80387[5][6] и вплоть до 80486[1], а также в сопроцессорах Motorola 68881[1][2] и 68882. Это позволило уменьшить число логических элементов (и сложность) сопроцессора.

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

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

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

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

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

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

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

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

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

Режим работы

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

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

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

Более формально, на каждой итерации вычисляется вращение, которое осуществляется путём умножения вектора на матрицу поворота :

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

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

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

Выражение для поворачиваемого вектора :

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

где

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

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

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

Единственная задача которая осталась, это определить по часовой стрелке или против часовой стрелки должно выполняться вращение на каждой итерации (выбор значения ). Это делается путём отслеживания величины поворота на каждой итерации и вычитания из желаемого угла, а затем проверки, если является положительным, то мы должны вращаться по часовой стрелке или если он отрицательный, мы должны вращаться против часовой стрелки, чтобы приблизится к углу .

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

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


Метод "двойных итераций"

В работах: http://baykov.de/CORDIC1972.htm и http://baykov.de/CORDIC1975.htm было предложено использовать при вычислении функций arcsinX, arccosX, lnX, expX, а также для вычиcления гиперболических функций метод "двойных итераций" (double iterations). Состоит он в том, что в отличие от классического метода CORDIC, где величина шага итерации меняется ВСЯКИЙ раз, т.е. на каждой итерации, при методе двойных итераций величина шага итерации повторяется дважды и меняется лишь через одну итерацию. Отсюда появилось обозначение для показателя степени при двойных итерациях: i= 1,1,2,2,3,3... Тогда как при обычных итерациях: i=1,2,3... Метод двойных итераций гарантирует сходимость метода во всем допустимом диапазоне изменения аргументов.

Обобщение вопросов сходимости алгоритмов метода CORDIC на произвольную позиционную систему счисления  http://baykov.de/CORDIC1985.htm с основанием R показало, что для функций sin, cos, arctg достаточно выполнения (R-1)итераций при каждом значении i (i от 0 или 1 до n, где n - разрядность чисел), т.е. для каждого разряда результата.   Для функций ln, exp, sh, ch, arth следует выполнять R итераций для каждого значения i. Для фукнций arcsin и arccos следует выполнять 2(R-1) итераций на каждый разряд, т.е. при каждом значении i. 
 Для функций arsh, arch  количество итераций составит 2R для каждого i, т.е. для каждого разряда результата.


Литература

Примечания

  1. Muller Jean-Michel. Elementary Functions: Algorithms and Implementation. — 2 edition. — Boston: Birkhäuser, 2006. — С. 134. — ISBN 978-0-8176-4372-0.
  2. Rafi Nave. Implementation of Transcendental Functions on a Numerics Processor // Microprocessing and Microprogramming. — 1983. Т. 11, № 3-4. С. 221–225.
  3. John F. Palmer, Stephen Paul Morse. The 8087 Primer. — John Wiley & Sons Australia, Limited, 1984. — ISBN 9780471875697.
  4. Glass L. Brent. Math Coprocessors: A look at what they do, and how they do it // Byte Magazine. — 1990. Т. 15, № 1. С. 337–348. ISSN 0360-5280.
  5. Pitts Jarvis. Implementing CORDIC algorithms - A single compact routine for computing transcendental functions // Dr. Dobbs Journal. — 1990. Т. 15, № 10. С. 152–156.
  6. A. K. Yuen. Intel's Floating-Point Processors // Electro/88 Conference Record. — 1988. С. 48/5/1–7.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.