CORDIC

Материал из Википедии — свободной энциклопедии

Метод CORDIC (в отечественной литературе также употребляются термины метод «цифра за цифрой» или алгоритм Волдера (Volder)

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

[править] История

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

[править] Метод Бриггса

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

Например, Бриггс умножал значение аргумента функции десятичного логарифма logX на константы вида: 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 и прибавлять ее со знаком минус. Значения всех констант вида 1+10^-i и 1-10^-i могут быть вычислены заранее, поскольку их относительно немного. Например, при допустимой ошибке 10^-6 их всего двенадцать. Остается пояснить, что умножение на константы вида 1+10^-i и 1-10^-i сводится к операциям сложения, вычитания и переноса запятой (сдвига). Следовательно, процедура вычисления функции десятичного логарифма по Бриггсу сводится к операциям сложения, вычитания и десятичного сдвига.

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

[править] Литература

• 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, pp335-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