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 координата — значением косинуса.

Примечания[править | править код]

  1. 1 2 3 Muller Jean-Michel. Elementary Functions: Algorithms and Implementation. — 2 edition. — Boston: Birkhäuser, 2006. — С. 134. — ISBN 978-0-8176-4372-0.
  2. 1 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. 1 2 3 Pitts Jarvis Implementing CORDIC algorithms - A single compact routine for computing transcendental functions // Dr. Dobbs Journal. — 1990. — Т. 15, № 10. — С. 152–156.
  6. 1 2 A. K. Yuen Intel's Floating-Point Processors // Electro/88 Conference Record. — 1988. — С. 48/5/1–7.

Литература[править | править код]