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 сводится к операциям сложения, вычитания и переноса запятой (сдвига). Следовательно, процедура вычисления функции десятичного логарифма по Бриггсу сводится к операциям сложения, вычитания и десятичного сдвига.

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

Литература

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home