CORDIC — Простий та ефективний алгоритм обчислення багатьох елементарних функцій. Назва методу походить від англ. — цифровий комп'ютер для обертання координат.
Класичний CORDIC-метод
Відомий класичний CORDIC-метод описав Джек Волдер () ще у 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 кут повороту φ наближається сумою знакозмінних кутів
:
де — оператор вибору () напрямку обертання.
Тоді (7) можна замінити на
=
Отже, щоб здійснити одне мікрообертання, необхідно заздалегідь обчислити значення косинуса кута та виконати лише дві операції множення. Дві інші операції множення замінено операціями зсуву.
Ураховуючи (3), (8) — (10), можемо записати:
=
=
де
Зауважимо, що у такому разі
Отже, (11) запишемо у вигляді
де
Своєю чергою, добуток матриць, взятий у дужки (16), можна зобразити однією результуючою матрицею повороту
де
Звідси (16) набуде вигляду
Як випливає з (11), (16), множення замінено зсувами, що значно спрощує апаратну реалізацію обчислювачів.
Вилучивши з (10) масштабуючий коефіцієнт , отримаємо класичний (спрощений) ітераційний CORDIC. Ротації в такому випадку називають псевдоротаціями, а рівняння набувають вигляду
=
або в розгорнутому вигляді
Якщо виконати всі ітерації за алгоритмом (20), то отримаємо:
або
де — коефіцієнт деформації вектора.
Зв'язок між векторами (xm+1,ym+1)T та (x',y')T такий:
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODRMemc1TDBOUFVrUkpReTFwYkd4MWMzUnlZWFJwYjI0dWNHNW5Mek13TUhCNExVTlBVa1JKUXkxcGJHeDFjM1J5WVhScGIyNHVjRzVuLnBuZw==.png)
Рівняння (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 (
-колова,
- гіперболічна,
— лінійна);
в режимі обертання () R=1, V=0 та у векторному режимі () — навпаки R=0, V=1;
- оператор вибору напрямку обертання (його вибирають з умови
для режиму обертання (Rotation mode) або
для векторного режиму (Vectoring mode) і набуває значення
для для
для
.
Модифікований 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 [ 19 липня 2011 у Wayback Machine.] 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 стр. [ 15 січня 2011 у Wayback Machine.]
5.* Байков В. Д., Смолов В. Б. Специализированные процессоры: итерационные алгоритмы и структуры, Москва, «Радио и связь» 1985, 288 стр. [ 18 липня 2011 у Wayback Machine.]
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 [ 10 червня 2015 у Wayback Machine.]
13. M. Zechmeister Solving Kepler’s equation with CORDIC double iterations Institut für Astrophysik, Georg-August-Universität, Friedrich-Hund-Platz 1, 37077 Göttingen, Germany, Preprint 10 August 2020, p.1-10. [ 22 серпня 2021 у Wayback Machine.]
![]() | Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Ця стаття потребує додаткових для поліпшення її . (травень 2016) |
Ця стаття містить текст, що не відповідає . (травень 2016) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
CORDIC Prostij ta efektivnij algoritm obchislennya bagatoh elementarnih funkcij Nazva metodu pohodit vid angl cifrovij komp yuter dlya obertannya koordinat Klasichnij CORDIC metodVidomij klasichnij CORDIC metod opisav Dzhek Volder she u 1959 r 1 Z togo chasu opublikovano nadzvichajno bagato robit z ciyeyi problematiki 2 10 Metod populyarnij i nini zavdyaki prostoti jogo programnoyi ta aparatnoyi realizaciyi Adzhe dlya klasichnogo CORDIC potriben lishe nevelikij ob yem pam yati ta deyaki elementarni operaciyi tipu zchituvannya z pam yati dodavannya vidnimannya ta zsuvu Rozglyad metodu pochnemo z opisu dvoh poshirenih krivih drugogo poryadku kola odinichnogo radiusa ta giperboli Yaksho parametrichno podati kolo ta giperbolu to polozhennya bud yakoyi tochki na cih krivih z koordinatami x y T opisuyetsya takimi rivnyannyami dlya kola x c o s ϕ displaystyle x cos phi y s i n ϕ 1 displaystyle y sin phi 1 ϕ a r c t a n y x displaystyle phi arctan left frac y x right dd dd dd dd dd dd dd dd dd dd dd dd dd dd dlya giperboli x c o s h ϕ displaystyle x cosh phi y s i n h ϕ 2 displaystyle y sinh phi 2 ϕ a r c t a n h y x displaystyle phi arctanh left frac y x right dd dd dd dd dd dd dd dd dd dd dd dd dd dd de f kut yakij utvoryuye vektor pochatkovogo polozhennya xo yo T 1 0 T ruhayuchis po kolu abo giperboli z vissyu abscis kinec vektora dosyagaye tochki x y T T simvol transponuvannya Zv yazok mizh koordinatami dvoh tochok sho lezhat na koli giperboli mozhna opisati za dopomogoyu povorotu vektora navkolo pochatku dekartovoyi sistemi koordinat Tochka sho rozmishena na kinci vektora i maye pochatkovi koordinati x y T zavdyaki povorotu vektora na kut f peremistitsya u nove polozhennya z koordinatami x y T Yaksho vektor ruhayetsya proti godinnikovoyi strilki to zv yazok dlya kola opisuyetsya takimi rivnyannyami x y displaystyle begin bmatrix x y end bmatrix c o s ϕ s i n ϕ s i n ϕ c o s ϕ displaystyle begin bmatrix cos phi amp sin phi sin phi amp cos phi end bmatrix x y 3 displaystyle begin bmatrix x y end bmatrix 3 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Dlya giperboli cej zv yazok mozhna podati rivnyannyami x y displaystyle begin bmatrix x y end bmatrix s i n h ϕ c o s h ϕ c o s h ϕ s i n h ϕ displaystyle begin bmatrix sinh phi amp cosh phi cosh phi amp sinh phi end bmatrix x y 4 displaystyle begin bmatrix x y end bmatrix 4 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Yaksho zobraziti ruh tochki po kolu giperboli yak sumarnij rezultat mikroobertan vektora navkolo pochatku sistemi koordinat na mikrokuti a i displaystyle alpha i sho ye chastinoyu zagalnogo vhidnogo kuta ϕ displaystyle phi zv yazok mizh dvoma susidnimi tochkami z koordinatami xi yi T ta xi 1 yi 1 T dlya kolovogo obertannya vektora bude takim x i 1 y i 1 displaystyle begin bmatrix x i 1 y i 1 end bmatrix c o s a i s i n a i s i n a i c o s a i displaystyle begin bmatrix cos alpha i amp sin alpha i sin alpha i amp cos alpha i end bmatrix x i y i 5 displaystyle begin bmatrix x i y i end bmatrix 5 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Yaksho tochka ruhayetsya po giperboli rivnyannya nabuvayut viglyadu x i 1 y i 1 displaystyle begin bmatrix x i 1 y i 1 end bmatrix c o s h a i s i n h a i s i n h a i c o s h a i displaystyle begin bmatrix cosh alpha i amp sinh alpha i sinh alpha i amp cosh alpha i end bmatrix x i y i 6 displaystyle begin bmatrix x i y i end bmatrix 6 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Nadali rozglyadatimemo lishe kolove obertannya Yak bachimo dlya zdijsnennya odnogo mikroobertannya potribno obchisliti znachennya sinusa ta kosinusa kuta a i displaystyle alpha i ta vikonati chotiri operaciyi mnozhennya Peretvorimo sistemu 5 shob zmenshiti kilkist neobhidnih operacij ta sprostiti aparatnu realizaciyu pristroyu Dlya cogo zobrazimo sistemu u takomu viglyadi x i 1 y i 1 displaystyle begin bmatrix x i 1 y i 1 end bmatrix c o s a i 1 t a n a i t a n a i 1 displaystyle cos alpha i begin bmatrix 1 amp tan alpha i tan alpha i amp 1 end bmatrix x i y i 7 displaystyle begin bmatrix x i y i end bmatrix 7 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Teper sprobuyemo zaminiti mnozhennya zsuvami Vikonayemo zaminu v sistemi 7 viberemo elementarni kuti a i displaystyle alpha i na pidstavi a i a r c t a n 2 i 8 displaystyle alpha i arctan left 2 i right 8 dd dd dd dd dd dd dd dd dd dd dd dd dd dd U comu vipadku t a n a i t a n a r c t a n 2 i 2 i displaystyle tan alpha i tan big arctan big 2 i big big 2 i a kut povorotu f nablizhayetsya sumoyu znakozminnih kutiv a i displaystyle alpha i ϕ i 0 m s i a i 9 displaystyle phi sum i 0 m sigma i alpha i 9 dd dd dd dd dd dd dd dd dd dd dd dd dd dd de s i 1 1 displaystyle sigma i in big 1 1 big operator viboru napryamku obertannya Todi 7 mozhna zaminiti na x i 1 y i 1 displaystyle begin bmatrix x i 1 y i 1 end bmatrix c o s a i 1 s i 2 i s i 2 i 1 displaystyle cos alpha i begin bmatrix 1 amp sigma i 2 i sigma i 2 i amp 1 end bmatrix x i y i 10 displaystyle begin bmatrix x i y i end bmatrix 10 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Otzhe shob zdijsniti odne mikroobertannya neobhidno zazdalegid obchisliti znachennya kosinusa kuta a i displaystyle alpha i ta vikonati lishe dvi operaciyi mnozhennya Dvi inshi operaciyi mnozhennya zamineno operaciyami zsuvu Urahovuyuchi 3 8 10 mozhemo zapisati x y displaystyle begin bmatrix x y end bmatrix c o s a 0 1 s 0 2 0 s 0 2 0 1 displaystyle cos alpha 0 begin bmatrix 1 amp sigma 0 2 0 sigma 0 2 0 amp 1 end bmatrix c o s a 1 1 s 1 2 1 s 1 2 1 1 displaystyle cos alpha 1 begin bmatrix 1 amp sigma 1 2 1 sigma 1 2 1 amp 1 end bmatrix c o s a 2 1 s 2 2 2 s 2 2 2 1 displaystyle cos alpha 2 begin bmatrix 1 amp sigma 2 2 2 sigma 2 2 2 amp 1 end bmatrix c o s a m 1 s m 2 m s m 2 m 1 displaystyle cdots cos alpha m begin bmatrix 1 amp sigma m 2 m sigma m 2 m amp 1 end bmatrix x y displaystyle begin bmatrix x y end bmatrix i 0 m cos arctan 2 i displaystyle prod i 0 m cos Big arctan Big 2 i Big Big i 0 m displaystyle big prod i 0 m 1 s i 2 i s i 2 i 1 displaystyle begin bmatrix 1 amp sigma i 2 i sigma i 2 i amp 1 end bmatrix big x y displaystyle begin bmatrix x y end bmatrix P displaystyle boldsymbol P i 0 m displaystyle big prod i 0 m 1 s i 2 i s i 2 i 1 displaystyle begin bmatrix 1 amp sigma i 2 i sigma i 2 i amp 1 end bmatrix big x y 11 displaystyle begin bmatrix x y end bmatrix 11 de P displaystyle boldsymbol P i 0 m cos arctan 2 i c o n s t 12 displaystyle big prod i 0 m cos Big arctan Big 2 i Big Big boldsymbol const 12 dd dd dd dd dd dd dd dd dd dd Zauvazhimo sho u takomu razi sin a i 2 i 1 2 2 i 13 displaystyle sin alpha i 2 i sqrt 1 2 2i 13 cos a i 1 1 2 2 i 14 displaystyle cos alpha i 1 sqrt 1 2 2i 14 tan a i 2 i 15 displaystyle tan alpha i 2 i 15 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Otzhe 11 zapishemo u viglyadi x y displaystyle begin bmatrix x y end bmatrix P displaystyle boldsymbol P i 0 m displaystyle big prod i 0 m 1 s i 2 i s i 2 i 1 displaystyle begin bmatrix 1 amp sigma i 2 i sigma i 2 i amp 1 end bmatrix big x y 16 displaystyle begin bmatrix x y end bmatrix 16 dd dd dd dd dd dd dd dd dd dd dd dd de P displaystyle boldsymbol P i 0 m cos arctan 2 i i 0 m 1 1 2 2 i c o n s t displaystyle big prod i 0 m cos Big arctan Big 2 i Big Big boldsymbol prod i 0 m left frac 1 sqrt 1 2 2i right boldsymbol const dd dd dd dd dd dd dd dd dd dd Svoyeyu chergoyu dobutok matric vzyatij u duzhki 16 mozhna zobraziti odniyeyu rezultuyuchoyu matriceyu povorotu T r displaystyle T r T r displaystyle boldsymbol T r C C S S S S C C displaystyle begin bmatrix CC amp SS SS amp CC end bmatrix boldsymbol i 0 m displaystyle prod i 0 m 1 s i 2 i s i 2 i 1 17 displaystyle begin bmatrix 1 amp sigma i 2 i sigma i 2 i amp 1 end bmatrix 17 dd dd dd dd dd dd dd dd dd dd dd dd dd dd de C C displaystyle boldsymbol CC c o s ϕ P c o s i 0 m s i a i P displaystyle cos phi P cos big sum i 0 m sigma i alpha i big P S S displaystyle boldsymbol SS s i n ϕ P s i n i 0 m s i a i P displaystyle sin phi P sin big sum i 0 m sigma i alpha i big P dd dd dd dd dd dd dd dd dd dd dd dd dd dd Zvidsi 16 nabude viglyadu x y displaystyle begin bmatrix x y end bmatrix P c o s ϕ P s i n ϕ P s i n ϕ P c o s ϕ P displaystyle boldsymbol P begin bmatrix cos phi P amp sin phi P sin phi P amp cos phi P end bmatrix x y displaystyle begin bmatrix x y end bmatrix C C S S S S C C displaystyle boldsymbol begin bmatrix CC amp SS SS amp CC end bmatrix x P y P 18 displaystyle begin bmatrix xP yP end bmatrix 18 dd dd dd dd dd dd dd dd dd dd dd Yak viplivaye z 11 16 mnozhennya zamineno zsuvami sho znachno sproshuye aparatnu realizaciyu obchislyuvachiv Viluchivshi z 10 masshtabuyuchij koeficiyent c o s a i 1 1 2 2 i displaystyle cos alpha i 1 sqrt 1 2 2i otrimayemo klasichnij sproshenij iteracijnij CORDIC Rotaciyi v takomu vipadku nazivayut psevdorotaciyami a rivnyannya nabuvayut viglyadu x i 1 y i 1 displaystyle begin bmatrix x i 1 y i 1 end bmatrix 1 s i 2 i s i 2 i 1 displaystyle begin bmatrix 1 amp sigma i 2 i sigma i 2 i amp 1 end bmatrix x i y i 19 displaystyle begin bmatrix x i y i end bmatrix 19 dd dd dd dd dd dd dd dd dd dd dd dd dd dd abo v rozgornutomu viglyadi x i 1 x i s i y i 2 i y i 1 y i s i x i 2 i 20 displaystyle begin cases x i 1 x i sigma i y i 2 i y i 1 y i sigma i x i 2 i end cases 20 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Yaksho vikonati vsi m 1 displaystyle m 1 iteraciyi za algoritmom 20 to otrimayemo x m 1 y m 1 displaystyle begin bmatrix x m 1 y m 1 end bmatrix C C S S S S C C displaystyle boldsymbol begin bmatrix CC amp SS SS amp CC end bmatrix x y displaystyle begin bmatrix x y end bmatrix c o s ϕ P s i n ϕ P s i n ϕ P c o s ϕ P displaystyle begin bmatrix cos phi P amp sin phi P sin phi P amp cos phi P end bmatrix x y displaystyle begin bmatrix x y end bmatrix 1 P c o s ϕ s i n ϕ s i n ϕ c o s ϕ displaystyle boldsymbol 1 P begin bmatrix cos phi amp sin phi sin phi amp cos phi end bmatrix x y 21 displaystyle begin bmatrix x y end bmatrix 21 dd dd dd dd dd dd x m 1 y m 1 displaystyle begin bmatrix x m 1 y m 1 end bmatrix c o s ϕ s i n ϕ s i n ϕ c o s ϕ displaystyle boldsymbol begin bmatrix cos phi amp sin phi sin phi amp cos phi end bmatrix x P y P 22 displaystyle begin bmatrix x P y P end bmatrix 22 dd dd dd dd dd dd dd dd dd dd dd dd dd dd abo x m 1 K m x c o s i 0 m s i a i y s i n i 0 m s i a i 23 displaystyle x m 1 K m big x cos big sum i 0 m sigma i alpha i big y sin big sum i 0 m sigma i alpha i big big 23 y m 1 K m y c o s i 0 m s i a i x s i n i 0 m s i a i 24 displaystyle y m 1 K m big y cos big sum i 0 m sigma i alpha i big x sin big sum i 0 m sigma i alpha i big big 24 dd dd dd dd dd dd dd dd dd dd dd dd dd dd K m 1 P i 0 m 1 2 2 i 25 displaystyle K m 1 P prod i 0 m sqrt 1 2 2i 25 dd dd dd dd dd dd dd dd dd dd dd dd dd dd de K m displaystyle K m koeficiyent deformaciyi vektora Zv yazok mizh vektorami xm 1 ym 1 T ta x y T takij x y displaystyle begin bmatrix x y end bmatrix P x m 1 y m 1 26 displaystyle boldsymbol P begin bmatrix x m 1 y m 1 end bmatrix 26 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Ilyustraciya iteracij CORDIC Rivnyannya 27 30 opisuyut tradicijnij iteracijnij CORDIC u rezhimi obertannya Rotation mode dlya kolovoyi sistemi koordinat x i 1 x i s i y i 2 i displaystyle x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i 27 displaystyle y i 1 y i sigma i x i 2 i 27 z i 1 z i s i a i 28 displaystyle z i 1 z i sigma i alpha i 28 dd dd dd dd dd dd dd dd dd dd dd dd dd dd de s i 1 if z i lt 0 1 if z i 0 displaystyle sigma i begin cases 1 amp mbox if z i lt 0 1 amp mbox if z i geq 0 end cases i 0 1 2 m 29 displaystyle boldsymbol i 0 1 2 m 29 dd dd dd dd dd dd dd dd dd dd dd dd dd dd a i arctan 2 i 30 displaystyle alpha i arctan big 2 i big 30 dd dd dd dd dd dd dd dd dd dd dd dd dd dd prichomu x 0 x y 0 y z 0 ϕ displaystyle x 0 x y 0 y z 0 phi dd dd dd dd dd dd dd dd dd dd dd dd dd dd Tut vvedeno she odnu zminnu z displaystyle z dlya zrivnovazhennya znachennya vhidnogo kuta ϕ displaystyle phi Yaksho i displaystyle i to propto znachennya zalishkovogo kuta z i 1 displaystyle z i 1 pryamuye do 0 Dlya kompensaciyi deformaciyi vektora vikoristovuyut pochatkove znachennya x 0 x P x K m y 0 y P y K m displaystyle x 0 xP x K m y 0 yP y K m yak viplivaye z 22 ta 26 Yaksho prijnyati x 0 P 1 K m y 0 0 displaystyle x 0 P 1 K m y 0 0 to v rezultati vikonannya 27 30 bude realizovano funkciyi sinusa ta kosinusa za sistemoyu rivnyan 1 Dlya giperbolichnoyi sistemi koordinat u rezhimi obertannya Rotation mode rivnyannya matimut viglyad x i 1 x i s i y i 2 i displaystyle x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i 31 displaystyle y i 1 y i sigma i x i 2 i 31 z i 1 z i s i a i 32 displaystyle z i 1 z i sigma i alpha i 32 dd dd dd dd dd dd dd dd dd dd dd dd dd dd de s i 1 if z i lt 0 1 if z i 0 displaystyle sigma i begin cases 1 amp mbox if z i lt 0 1 amp mbox if z i geq 0 end cases i 1 2 3 4 4 5 12 13 13 14 m 33 displaystyle boldsymbol i 1 2 3 4 4 5 12 13 13 14 m 33 dd dd dd dd dd dd dd dd dd dd dd dd dd dd a i arctan h 2 i 34 displaystyle alpha i arctan h big 2 i big 34 dd dd dd dd dd dd dd dd dd dd dd dd dd dd prichomu x 1 x y 1 y z 1 ϕ displaystyle x 1 x y 1 y z 1 phi Pochatkovi umovi z urahuvannyam kompensaciyi deformaciyi vektora taki sami yak i dlya kolovoyi sistemi koordinat Odnak zvernemo uvagu na te sho pochatkove znachennya zminnoyi i displaystyle i dorivnyuye 1 a deyaki yiyi znachennya povtoryuyutsya dlya zabezpechennya zbizhnosti iteracijnogo procesu div rivnyannya 33 1 10 Ci obstavini takozh treba vrahovuvati obchislyuyuchi znachennya koeficiyenta deformaciyi vektora dlya giperbolichnoyi sistemi koordinatK m displaystyle K m za takimi formulami P m 1 i 1 m c o s h a i i 1 m 1 1 2 2 i displaystyle P m1 prod i 1 m cosh big alpha i prod i 1 m frac 1 sqrt 1 2 2i P m 2 1 1 2 8 1 1 2 26 1 1 2 80 displaystyle P m2 frac 1 sqrt 1 2 8 frac 1 sqrt 1 2 26 frac 1 sqrt 1 2 80 P P m 1 P m 2 displaystyle P P m1 P m2 K m 1 P displaystyle K m 1 P dd dd dd dd dd dd dd dd dd dd dd dd dd dd Yaksho zh pochatkovij vektor zadano koordinatami x 0 x y 0 y z 0 0 displaystyle x 0 x y 0 y z 0 0 i pri comu zrivnovazhuyetsya znachennya zminnoyi y displaystyle y tobto prii displaystyle i to propto znachennya y i 1 displaystyle y i 1 pryamuye do 0 to ce tak zvanij vektornij rezhim roboti Vectoring mode Todi dlya kolovoyi sistemi koordinat rivnyannya nabuvayut viglyadu x i 1 x i s i y i 2 i displaystyle x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i 35 displaystyle y i 1 y i sigma i x i 2 i 35 dd dd dd dd dd dd dd dd dd dd dd dd dd dd z i 1 z i s i a i 36 displaystyle z i 1 z i sigma i alpha i 36 dd dd dd dd dd dd dd dd dd dd dd dd dd dd de s i 1 if y i lt 0 1 if y i 0 displaystyle sigma i begin cases 1 amp mbox if y i lt 0 1 amp mbox if y i geq 0 end cases i 0 1 2 m 37 displaystyle boldsymbol i 0 1 2 m 37 dd dd dd dd dd dd dd dd dd dd dd dd dd dd a i arctan 2 i 38 displaystyle alpha i arctan big 2 i big 38 dd dd dd dd dd dd dd dd dd dd dd dd dd dd U takomu razi obchislyuyutsya funkciyi X m 1 K m x 0 2 y 0 2 displaystyle X m 1 approx K m sqrt x 0 2 y 0 2 Z m 1 arctan y 0 x 0 39 displaystyle Z m 1 approx arctan big frac y 0 x 0 big 39 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Dlya giperbolichnoyi sistemi koordinat u vektornomu rezhimi Vectoring mode rivnyannya matimut viglyad x i 1 x i s i y i 2 i displaystyle x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i 40 displaystyle y i 1 y i sigma i x i 2 i 40 dd dd dd dd dd dd dd dd dd dd dd dd dd dd z i 1 z i s i a i 41 displaystyle z i 1 z i sigma i alpha i 41 dd dd dd dd dd dd dd dd dd dd dd dd dd dd de s i 1 if y i lt 0 1 if y i 0 displaystyle sigma i begin cases 1 amp mbox if y i lt 0 1 amp mbox if y i geq 0 end cases i 1 2 3 4 4 5 12 13 13 14 m 42 displaystyle boldsymbol i 1 2 3 4 4 5 12 13 13 14 m 42 dd dd dd dd dd dd dd dd dd dd dd dd dd dd a i arctan h 2 i 43 displaystyle alpha i arctan h big 2 i big 43 dd dd dd dd dd dd dd dd dd dd dd dd dd dd X m 1 K m x 1 2 y 1 2 displaystyle X m 1 approx K m sqrt x 1 2 y 1 2 Z m 1 arctan y 1 x 1 44 displaystyle Z m 1 approx arctan big frac y 1 x 1 big 44 dd dd dd dd dd dd dd dd dd dd dd dd dd dd Dlya unifikaciyi metodu CORDIC proponuyemo vikoristati takij variant uzagalnennya 11 x i 1 x i M R V s i y i 2 i displaystyle x i 1 x i M big R V sigma i y i 2 i y i 1 y i R V s i x i 2 i 45 displaystyle y i 1 y i big R V sigma i x i 2 i 45 dd dd dd dd dd dd dd dd dd dd dd dd dd dd z i 1 z i V R s i a i 46 displaystyle z i 1 z i big V R sigma i alpha i 46 dd dd dd dd dd dd dd dd dd dd dd dd dd dd deM displaystyle M parametr sho vkazuye na sistemu koordinat v yakij pracyuye CORDIC M 1 displaystyle M 1 kolova M 1 displaystyle M 1 giperbolichna M 0 displaystyle M 0 linijna v rezhimi obertannya R 1 V 0 ta u vektornomu rezhimi navpaki R 0 V 1 s i displaystyle sigma i operator viboru napryamku obertannya jogo vibirayut z umovi s i s i g n z i displaystyle sigma i sign big z i dlya rezhimu obertannya Rotation mode abo s i s i g n y i displaystyle sigma i sign big y i dlya vektornogo rezhimu Vectoring mode i nabuvaye znachennya s i 1 1 displaystyle sigma i big 1 1 big dlya M 1 a i a r c t a n 2 i displaystyle M 1 alpha i arctan big 2 i dlya M 1 a i a r c t a n h 2 i displaystyle M 1 alpha i arctanh big 2 i dlya M 0 a i 2 i displaystyle M 0 alpha i 2 i Tablicya deyakih funkcij sho obchislyuyutsya z dopomogoyu CORDIC R o t a t i o n R 1 V 0 z i 0 displaystyle Rotation big R 1 V 0 z i to 0 big s i 1 if z i lt 0 1 if z i 0 displaystyle sigma i begin cases 1 amp mbox if z i lt 0 1 amp mbox if z i geq 0 end cases V e c t o r i n g R 0 V 1 y i 0 displaystyle Vectoring big R 0 V 1 y i to 0 big s i 1 if y i lt 0 1 if y i 0 displaystyle sigma i begin cases 1 amp mbox if y i lt 0 1 amp mbox if y i geq 0 end cases M 1 displaystyle M 1 a i arctan 2 i displaystyle alpha i arctan big 2 i big i 0 1 2 m displaystyle boldsymbol i 0 1 2 m P displaystyle boldsymbol P i 0 m cos a i i 0 m 1 1 2 2 i displaystyle prod i 0 m cos Big alpha i Big boldsymbol prod i 0 m frac 1 sqrt 1 2 2i K m 1 P i 0 m 1 2 2 i displaystyle K m 1 P prod i 0 m sqrt 1 2 2i x i 1 x i s i y i 2 i displaystyle x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i displaystyle y i 1 y i sigma i x i 2 i z i 1 z i s i a i displaystyle z i 1 z i sigma i alpha i x 0 P y 0 0 z 0 ϕ displaystyle x 0 P y 0 0 z 0 phi x m 1 c o s ϕ displaystyle x m 1 approx cos big phi y m 1 s i n ϕ displaystyle y m 1 approx sin big phi ϕ 0 1 74 displaystyle phi in big 0 1 74 big x i 1 x i s i y i 2 i displaystyle x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i displaystyle y i 1 y i sigma i x i 2 i z i 1 z i s i a i displaystyle z i 1 z i sigma i alpha i x 0 X y 0 Y z 0 0 displaystyle x 0 X y 0 Y z 0 0 X m 1 K m X 2 Y 2 displaystyle X m 1 approx K m sqrt X 2 Y 2 Z m 1 arctan Y X displaystyle Z m 1 approx arctan big frac Y X big X 2 Y 2 X m 1 P displaystyle sqrt X 2 Y 2 approx X m 1 P M 1 displaystyle M 1 a i arctan h 2 i displaystyle alpha i arctan h big 2 i big i 1 2 3 4 4 5 12 13 13 14 m displaystyle boldsymbol i 1 2 3 4 4 5 12 13 13 14 m P m 1 i 1 m c o s h a i i 1 m 1 1 2 2 i displaystyle P m1 prod i 1 m cosh big alpha i prod i 1 m frac 1 sqrt 1 2 2i P m 2 1 1 2 8 1 1 2 26 1 1 2 80 displaystyle P m2 frac 1 sqrt 1 2 8 frac 1 sqrt 1 2 26 frac 1 sqrt 1 2 80 P P m 1 P m 2 displaystyle P P m1 P m2 K m 1 P displaystyle K m 1 P 1 x i 1 x i s i y i 2 i displaystyle 1 qquad x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i displaystyle y i 1 y i sigma i x i 2 i z i 1 z i s i a i displaystyle z i 1 z i sigma i alpha i x 0 P y 0 0 z 0 ϕ displaystyle x 0 P y 0 0 z 0 phi x m 1 c o s h ϕ displaystyle x m 1 approx cosh big phi y m 1 s i n h ϕ displaystyle y m 1 approx sinh big phi ϕ 0 1 118 displaystyle phi in big 0 1 118 big x m 1 y m 1 e x p ϕ displaystyle x m 1 y m 1 approx exp big phi x m 1 y m 1 e x p ϕ displaystyle x m 1 y m 1 approx exp big phi 2 q i 1 q i s i q i 2 i displaystyle 2 qquad q i 1 q i sigma i q i 2 i z i 1 z i s i a i displaystyle z i 1 z i sigma i alpha i q 0 P z 0 ϕ displaystyle q 0 P z 0 phi q m 1 e x p ϕ displaystyle q m 1 approx exp big phi ϕ 0 1 118 displaystyle phi in big 0 1 118 big 3 q i 1 q i s i q i 2 i displaystyle 3 qquad q i 1 q i sigma i q i 2 i z i 1 z i s i a i displaystyle z i 1 z i sigma i alpha i q 0 P z 0 ϕ displaystyle q 0 P z 0 phi q m 1 e x p ϕ displaystyle q m 1 approx exp big phi ϕ 0 1 118 displaystyle phi in big 0 1 118 big 1 x i 1 x i s i y i 2 i displaystyle 1 qquad x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i displaystyle y i 1 y i sigma i x i 2 i z i 1 z i s i a i displaystyle z i 1 z i sigma i alpha i x 1 X y 1 Y z 1 0 displaystyle x 1 X y 1 Y z 1 0 x m 1 K m X 2 Y 2 displaystyle x m 1 approx K m sqrt X 2 Y 2 z m 1 arctan h Y X displaystyle z m 1 approx arctan h big frac Y X big X 2 Y 2 x m 1 P displaystyle sqrt X 2 Y 2 approx x m 1 P f o r a r c t a n h y 1 x 1 0 0 8069 displaystyle for arctanh frac y 1 x 1 in big 0 0 8069 big 2 x i 1 x i s i y i 2 i displaystyle 2 qquad x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i displaystyle y i 1 y i sigma i x i 2 i x 1 W 0 25 y 1 W 0 25 displaystyle x 1 W 0 25 y 1 W 0 25 W 0 03 2 33 displaystyle W in big 0 03 2 33 big W x m 1 K m x m 1 P displaystyle sqrt W approx x m 1 K m x m 1 P 3 x i 1 x i s i y i 2 i displaystyle 3 qquad x i 1 x i sigma i y i 2 i y i 1 y i s i x i 2 i displaystyle y i 1 y i sigma i x i 2 i z i 1 z i s i a i displaystyle z i 1 z i sigma i alpha i x 1 W 1 y 1 W 1 z 1 0 displaystyle x 1 W 1 y 1 W 1 z 1 0 l n W 2 z m 1 displaystyle ln big W approx 2z m 1 W 0 107 9 359 displaystyle W in big 0 107 9 359 big M 0 displaystyle M 0 a i 2 i displaystyle alpha i 2 i i 0 1 2 m displaystyle i 0 1 2 m 1 y i 1 y i s i x 0 2 i displaystyle 1 qquad y i 1 y i sigma i x 0 2 i z i 1 z i s i a i displaystyle z i 1 z i sigma i alpha i x 0 X y 0 0 z 0 Z displaystyle x 0 X y 0 0 z 0 Z y m 1 X Z displaystyle y m 1 approx XZ 2 y i 1 y i s i x 0 2 i displaystyle 2 qquad y i 1 y i sigma i x 0 2 i z i 1 z i s i a i Y displaystyle z i 1 z i sigma i alpha i Y x 0 X y 0 X z 0 Z Y displaystyle x 0 X y 0 X z 0 Z Y x m 1 Z X Y displaystyle x m 1 approx ZX Y y i 1 y i s i x 0 2 i displaystyle y i 1 y i sigma i x 0 2 i z i 1 z i s i a i displaystyle z i 1 z i sigma i alpha i x 0 X y 0 Y z 0 0 displaystyle x 0 X y 0 Y z 0 0 z m 1 Y X displaystyle z m 1 approx Y X Modifikovanij CORDIC metodModifikaciyi vdoskonalennya metodu CORDIC spryamovani na pidvishennya shvidkodiyi zmenshennya kilkosti iteracij rozshirennya funkcionalnih mozhlivostej sproshennya aparatnoyi realizaciyi zbilshennya naboru realizovanih funkcij Zokrema odne z osnovnih zavdan modifikacij metodu zmenshiti kilkist iteracij zberigshi pohibki obchislen klasichnogo metodu Opis 45 46 poshiryuyetsya lishe na sinhronnij rezhim roboti CORDIC abo na znakozminni iteraciyi 4 Ce pov yazano z tim sho treba zberegti stalist znachennya koeficiyenta deformaciyi vektora 4 7 Odnak isnuyut funkciyi dlya yakih ne potribno dotrimuvatis cih vimog tomu sho koeficiyent deformaciyi ne vhodit do skladu viraziv za yakimi obchislyuyut abo jogo vpliv usuvayetsya oskilki v cih operaciyah makrooperaciyah vikonuyetsya operaciya dilennya Zokrema ce stosuyetsya obchislennya funkcij t a n X displaystyle tan big X a r c t a n Y X displaystyle arctan big Y X t a n h X displaystyle tanh big X ta inshih V takih vipadkah mozhna vikoristati asinhronnij rezhim roboti CORDIC abo znakostali iteraciyi yakij tezh zabezpechuye zbizhnist iteracijnogo procesu i pidvishuye shvidkodiyu priblizno vdvichi 11 Spisok literaturi1 Jack E Volder The CORDIC Trigonometric Computing Technique IRE Transactions on Electronic Computers pp330 334 September 1959 19 lipnya 2011 u Wayback Machine 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 Oranskij A M Apparatnye metody v cifrovoj vychislitelnoj tehnike Minsk Izdatelstvo BGU 1977 208 s 4 Bajkov V D Smolov V B Apparaturnaya realizaciya elementarnyh funkcij v CVM Leningrad izd vo LGU 1975 96 str 15 sichnya 2011 u Wayback Machine 5 Bajkov V D Smolov V B Specializirovannye processory iteracionnye algoritmy i struktury Moskva Radio i svyaz 1985 288 str 18 lipnya 2011 u Wayback Machine 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 Aristov V V Funkcionalnye makrooperacii Osnovy iteracionnyh algoritmov K Naukova dumka 1992 280 s 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 Obregon D R Agurto Rios 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 Moroz L V Adaptivnij CORDIC metod obchislennya deyakih funkcij Komp yuterni tehnologiyi drukarstva 2010 rr 24 C 105 110 12 CORDIC Bibliography Site 10 chervnya 2015 u Wayback Machine 13 M Zechmeister Solving Kepler s equation with CORDIC double iterations Institut fur Astrophysik Georg August Universitat Friedrich Hund Platz 1 37077 Gottingen Germany Preprint 10 August 2020 p 1 10 22 serpnya 2021 u Wayback Machine Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno traven 2016 Cya stattya mistit tekst sho ne vidpovidaye enciklopedichnomu stilyu Bud laska dopomozhit udoskonaliti cyu stattyu pogodivshi stil vikladu zi stilistichnimi pravilami Vikipediyi Mozhlivo storinka obgovorennya mistit zauvazhennya shodo potribnih zmin traven 2016