CORDIC — Простий та ефективний алгоритм обчислення багатьох елементарних функцій. Назва методу походить від англ. Coordinate Rotation Digital Computer — цифровий комп'ютер для обертання координат.

Класичний CORDIC-методРедагувати

Відомий класичний CORDIC-метод описав Джек Волдер (Jack E. Volder) ще у 1959 р. [1].З того часу опубліковано надзвичайно багато робіт з цієї проблематики [2 — 10].Метод популярний і нині завдяки простоті його програмної та апаратної реалізації. Адже для класичного CORDIC потрібен лише невеликий об'єм пам'яті та деякі елементарні операції типу зчитування з пам'яті, додавання, віднімання та зсуву.
Розгляд методу почнемо з опису двох поширених кривих другого порядку — кола одиничного радіуса та гіперболи.Якщо параметрично подати коло та гіперболу, то положення будь-якої точки на цих кривих з координатами (x, y)Т описується такими рівняннями:
для кола

 
 
 

для гіперболи

 
 
 

де φ — кут, який утворює вектор початкового положення (xo,yo)T = (1,0)T, рухаючись по колу або гіперболі, з віссю абсцис; кінець вектора досягає точки (x, y)T(Т- символ транспонування). Зв'язок між координатами двох точок, що лежать на колі (гіперболі), можна описати за допомогою повороту вектора навколо початку декартової системи координат. Точка, що розміщена на кінці вектора і має початкові координати (x, y)T, завдяки повороту вектора на кут φ переміститься у нове положення з координатами (x' ,y')T. Якщо вектор рухається проти годинникової стрілки, то зв'язок (для кола) описується такими рівняннями:

 =  

Для гіперболи цей зв'язок можна подати рівняннями:

 =  

Якщо зобразити рух точки по колу (гіперболі) як сумарний результат мікрообертань вектора навколо початку системи координат на мікрокути  , що є частиною загального вхідного кута  , зв'язок між двома сусідніми точками з координатами (xі,yі)T та (xі+1,yі+1)T для колового обертання вектора буде таким:

 =  

Якщо точка рухається по гіперболі, рівняння набувають вигляду:

 =  

Надалі розглядатимемо лише колове обертання.
Як бачимо, для здійснення одного мікрообертання потрібно обчислити значення синуса та косинуса кута   та виконати чотири операції множення. Перетворимо систему (5), щоб зменшити кількість необхідних операцій та спростити апаратну реалізацію пристрою. Для цього зобразимо систему у такому вигляді:

 =  

Тепер спробуємо замінити множення зсувами.
Виконаємо заміну в системі (7) — виберемо елементарні кути   на підставі

 

У цьому випадку   ,a кут повороту φ наближається сумою знакозмінних кутів  :

 

де   — оператор вибору (decision operator) напрямку обертання.
Тоді (7) можна замінити на

 =  

Отже, щоб здійснити одне мікрообертання, необхідно заздалегідь обчислити значення косинуса кута   та виконати лише дві операції множення. Дві інші операції множення замінено операціями зсуву.
Ураховуючи (3), (8) — (10), можемо записати:
 =     =

        

де

  

Зауважимо, що у такому разі

 
 
 

Отже, (11) запишемо у вигляді

     

де

  

Своєю чергою, добуток матриць, взятий у дужки (16), можна зобразити однією результуючою матрицею повороту  

    

де

  
  

Звідси (16) набуде вигляду

     

Як випливає з (11), (16), множення замінено зсувами, що значно спрощує апаратну реалізацію обчислювачів.
Вилучивши з (10) масштабуючий коефіцієнт  , отримаємо класичний (спрощений) ітераційний CORDIC. Ротації в такому випадку називають псевдоротаціями, а рівняння набувають вигляду

 =  

або в розгорнутому вигляді

 

Якщо виконати всі   ітерації за алгоритмом (20), то отримаємо:

       
   

або

 
 
 

де   — коефіцієнт деформації вектора.
Зв'язок між векторами (xm+1,ym+1)T та (x',y')T такий:

  
 
Ілюстрація ітерацій CORDIC

Рівняння (27) — (30) описують традиційний ітераційний CORDIC у режимі обертання (Rotation mode) для колової системи координат

 
 
 

де

  
 

причому

 

Тут введено ще одну змінну   для зрівноваження значення вхідного кута   . Якщо   , значення залишкового кута   прямує до 0.
Для компенсації деформації вектора використовують початкове значення   як випливає з (22) та (26).
Якщо прийняти   то в результаті виконання (27) — (30) буде реалізовано функції синуса та косинуса за системою рівнянь (1).
Для гіперболічної системи координат у режимі обертання (Rotation mode) рівняння матимуть вигляд

 
 
 

де

  
 

причому  . Початкові умови з урахуванням компенсації деформації вектора такі самі, як і для колової системи координат. Однак звернемо увагу на те, що початкове значення змінної   дорівнює 1, а деякі її значення повторюються для забезпечення збіжності ітераційного процесу (див. рівняння (33)) [1;10].Ці обставини також треба враховувати, обчислюючи значення коефіцієнта деформації вектора для гіперболічної системи координат за такими формулами

 
 
 
 

Якщо ж початковий вектор задано координатами   і при цьому зрівноважується значення змінної   , тобто при  значення   прямує до 0, то це так званий векторний режим роботи (Vectoring mode).
Тоді для колової системи координат рівняння набувають вигляду

 
 
 

де

  
 

У такому разі обчислюються функції

 
 

Для гіперболічної системи координат у векторному режимі (Vectoring mode) рівняння матимуть вигляд

 
 
 

де

  
 
 
 

Для уніфікації методу CORDIC пропонуємо використати такий варіант узагальнення [11]:

 
 
 

де параметр, що вказує на систему координат, в якій працює CORDIC ( -колова,  - гіперболічна,   — лінійна);
в режимі обертання (Rotation mode) R=1, V=0 та у векторному режимі (Vectoring mode) — навпаки R=0, V=1;
 - оператор вибору напрямку обертання (його вибирають з умови   для режиму обертання (Rotation mode) або   для векторного режиму (Vectoring mode) і набуває значення  
для   для   для  .

Таблиця деяких функцій, що обчислюються з допомогою CORDIC:
 
 
 
 
 
 
 
  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Модифікований CORDIC-методРедагувати

Модифікації (вдосконалення) методу CORDIC спрямовані на підвищення швидкодії, зменшення кількості ітерацій, розширення функціональних можливостей, спрощення апаратної реалізації, збільшення набору реалізованих функцій. Зокрема, одне з основних завдань модифікацій методу — зменшити кількість ітерацій, зберігши похибки обчислень класичного методу. Опис (45) — (46) поширюється лише на синхронний режим роботи CORDIC (або на знакозмінні ітерації) [4]. Це пов'язано з тим що треба зберегти сталість значення коефіцієнта деформації вектора [4, 7]. Однак існують функції, для яких не потрібно дотримуватись цих вимог, тому що коефіцієнт деформації не входить до складу виразів, за якими обчислюють, або його вплив усувається, оскільки в цих операціях(макроопераціях) виконується операція ділення. Зокрема, це стосується обчислення функцій  ,  ,   , та інших. В таких випадках можна використати асинхронний режим роботи CORDIC (або знакосталі ітерації), який теж забезпечує збіжність ітераційного процесу і підвищує швидкодію приблизно вдвічі [11].

Список літературиРедагувати

1. Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, pp330-334, September 1959 2. Walther, J.S. A unified algorithm for elementary functions// In Proceedings of AFIPS, 1971, Spring Joint Computer Conference, vol. 38, AFIPS Press, Arlington, Va., 1971, pp. 379-385.
3. Оранский А. М. Аппаратные методы в цифровой вычислительной технике. — Минск: Издательство БГУ, 1977. −208 с.
4. *Байков В. Д., Смолов В. Б. Аппаратурная реализация элементарных функций в ЦВМ, Ленинград, изд-во ЛГУ, 1975, 96 стр.
5.* Байков В. Д., Смолов В. Б. Специализированные процессоры: итерационные алгоритмы и структуры, Москва, «Радио и связь» 1985, 288 стр.
6. Pramod K. Meher, Javier Valls,Tso-Bing Juang,K. Sridharan, Koushik Maharatna. 50 Years of CORDIC: Algorithms, Architectures, and Applications/IEEE Transactions on Circuits and Systems—I: Regular Papers, Vol. 56, No. 9, September 2009, pp. 1893-1907.
7. Аристов В. В. Функциональные макрооперации. Основы итерационных алгоритмов. -К.: Наукова думка, 1992. −280 с.
8. Lakshmi B. and Dhar A. S. CORDIC Architectures: A Survey. VLSI Design. Volume 2010, Article ID 794891, 19 pages, January 8, 2010.
9. Llamocca-Obregón D.R., Agurto-Ríos C.P. A Fixed-Point Implementation of the Natural Logarithm Based on a Expanded Hyperbolic CORDIC Algorithm. XII WORKSHOP IBERCHIP, 2006, pp. 322 −323.
10. X. Hu, R. Huber, S. Bass, Expanding the Range of Convergence of the CORDIC Algorithm// IEEE Transactions on Computers. Vol. 40, Nº 1,1991, pp. 13-21.
11. Мороз Л. В. Адаптивний CORDIC-метод обчислення деяких функцій// Комп'ютерні технології друкарства. 2010, рр. № 24. C. 105–110.
12. CORDIC Bibliography Site