CORDIC — Простий та ефективний алгоритм обчислення багатьох елементарних функцій . Назва методу походить від англ. Coordinate Rotation Digital Computer — цифровий комп'ютер для обертання координат.
Відомий класичний CORDIC-метод описав Джек Волдер (Jack E. Volder ) ще у 1959 р. [1].З того часу опубліковано надзвичайно багато робіт з цієї проблематики [2 — 10].Метод популярний і нині завдяки простоті його програмної та апаратної реалізації. Адже для класичного CORDIC потрібен лише невеликий об'єм пам'яті та деякі елементарні операції типу зчитування з пам'яті, додавання, віднімання та зсуву.
Розгляд методу почнемо з опису двох поширених кривих другого порядку — кола одиничного радіуса та гіперболи .Якщо параметрично подати коло та гіперболу, то положення будь-якої точки на цих кривих з координатами (x, y)Т описується такими рівняннями:
для кола
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);}
для гіперболи
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);}
де φ — кут, який утворює вектор початкового положення (xo ,yo )T = (1,0)T , рухаючись по колу або гіперболі, з віссю абсцис; кінець вектора досягає точки (x, y)T (Т- символ транспонування). Зв'язок між координатами двох точок, що лежать на колі (гіперболі), можна описати за допомогою повороту вектора навколо початку декартової системи координат . Точка, що розміщена на кінці вектора і має початкові координати (x, y)T , завдяки повороту вектора на кут φ переміститься у нове положення з координатами (x' ,y' )T . Якщо вектор рухається проти годинникової стрілки, то зв'язок (для кола) описується такими рівняннями:
[
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 &-sin\phi \\sin\phi &cos\phi \end{bmatrix}}}
[
x
y
]
(
3
)
{\displaystyle {\begin{bmatrix}x\\y\end{bmatrix}}(3)}
Для гіперболи цей зв'язок можна подати рівняннями:
[
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 &cosh\phi \\cosh\phi &sinh\phi \end{bmatrix}}}
[
x
y
]
(
4
)
{\displaystyle {\begin{bmatrix}x\\y\end{bmatrix}}(4)}
Якщо зобразити рух точки по колу (гіперболі) як сумарний результат мікрообертань вектора навколо початку системи координат на мікрокути
α
i
{\displaystyle \alpha _{i}}
ϕ
{\displaystyle \,\phi }
і ,yі )T та (xі+1 ,yі+1 )T для колового обертання вектора буде таким:
[
x
i
+
1
y
i
+
1
]
{\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}}
[
c
o
s
α
i
−
s
i
n
α
i
s
i
n
α
i
c
o
s
α
i
]
{\displaystyle {\begin{bmatrix}cos\alpha _{i}&-sin\alpha _{i}\\sin\alpha _{i}&cos\alpha _{i}\end{bmatrix}}}
[
x
i
y
i
]
(
5
)
{\displaystyle {\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}(5)}
Якщо точка рухається по гіперболі, рівняння набувають вигляду:
[
x
i
+
1
y
i
+
1
]
{\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}}
[
c
o
s
h
α
i
s
i
n
h
α
i
s
i
n
h
α
i
c
o
s
h
α
i
]
{\displaystyle {\begin{bmatrix}cosh\alpha _{i}&sinh\alpha _{i}\\sinh\alpha _{i}&cosh\alpha _{i}\end{bmatrix}}}
[
x
i
y
i
]
(
6
)
{\displaystyle {\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}(6)}
Надалі розглядатимемо лише колове обертання.
Як бачимо, для здійснення одного мікрообертання потрібно обчислити значення синуса та косинуса кута
α
i
{\displaystyle \alpha _{i}}
[
x
i
+
1
y
i
+
1
]
{\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}}
c
o
s
α
i
[
1
−
t
a
n
α
i
t
a
n
α
i
1
]
{\displaystyle cos\alpha _{i}{\begin{bmatrix}1&-tan\alpha _{i}\\tan\alpha _{i}&1\end{bmatrix}}}
[
x
i
y
i
]
(
7
)
{\displaystyle {\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}(7)}
Тепер спробуємо замінити множення зсувами.
Виконаємо заміну в системі (7) — виберемо елементарні кути
α
i
{\displaystyle \,\alpha _{i}}
α
i
=
a
r
c
t
a
n
(
2
−
i
)
(
8
)
{\displaystyle \alpha _{i}=arctan\left(2^{-i}\right)(8)}
У цьому випадку
t
a
n
α
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}}
α
i
{\displaystyle \alpha _{i}}
ϕ
=
∑
i
=
0
m
σ
i
α
i
,
(
9
)
{\displaystyle \phi =\sum _{i=0}^{m}\sigma _{i}\alpha _{i},(9)}
де
σ
i
∈
{
−
1
,
1
}
{\displaystyle \sigma _{i}\in {\big \{}-1,1{\big \}}}
decision operator ) напрямку обертання.
[
x
i
+
1
y
i
+
1
]
{\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}}
c
o
s
α
i
[
1
−
σ
i
2
−
i
σ
i
2
−
i
1
]
{\displaystyle cos\alpha _{i}{\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix}}}
[
x
i
y
i
]
(
10
)
{\displaystyle {\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}(10)}
Отже, щоб здійснити одне мікрообертання, необхідно заздалегідь обчислити значення косинуса кута
α
i
{\displaystyle \alpha _{i}}
Ураховуючи (3), (8) — (10), можемо записати:
[
x
′
y
′
]
{\displaystyle {\begin{bmatrix}x'\\y'\end{bmatrix}}}
c
o
s
α
0
[
1
−
σ
0
2
−
0
σ
0
2
−
0
1
]
{\displaystyle cos\alpha _{0}{\begin{bmatrix}1&-\sigma _{0}2^{-0}\\\sigma _{0}2^{-0}&1\end{bmatrix}}}
c
o
s
α
1
[
1
−
σ
1
2
−
1
σ
1
2
−
1
1
]
{\displaystyle cos\alpha _{1}{\begin{bmatrix}1&-\sigma _{1}2^{-1}\\\sigma _{1}2^{-1}&1\end{bmatrix}}}
c
o
s
α
2
[
1
−
σ
2
2
−
2
σ
2
2
−
2
1
]
{\displaystyle cos\alpha _{2}{\begin{bmatrix}1&-\sigma _{2}2^{-2}\\\sigma _{2}2^{-2}&1\end{bmatrix}}}
⋯
c
o
s
α
m
[
1
−
σ
m
2
−
m
σ
m
2
−
m
1
]
{\displaystyle \cdots cos\alpha _{m}{\begin{bmatrix}1&-\sigma _{m}2^{-m}\\\sigma _{m}2^{-m}&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
−
σ
i
2
−
i
σ
i
2
−
i
1
]
)
{\displaystyle {\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&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
−
σ
i
2
−
i
σ
i
2
−
i
1
]
)
{\displaystyle {\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix}}{\big )}}
[
x
y
]
,
(
11
)
{\displaystyle {\begin{bmatrix}x\\y\end{bmatrix}},(11)}
де
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)}
Зауважимо, що у такому разі
sin
α
i
=
2
−
i
/
1
+
2
−
2
i
;
(
13
)
{\displaystyle \sin \alpha _{i}=2^{-i}/{\sqrt {1+2^{-2i}}};(13)}
cos
α
i
=
1
/
1
+
2
−
2
i
;
(
14
)
{\displaystyle \cos \alpha _{i}=1/{\sqrt {1+2^{-2i}}};(14)}
tan
α
i
=
2
−
i
.
(
15
)
{\displaystyle \tan \ \alpha _{i}\ =2^{-i}.(15)}
Отже, (11) запишемо у вигляді
[
x
′
y
′
]
=
{\displaystyle {\begin{bmatrix}x^{'}\\y^{'}\end{bmatrix}}=}
P
{\displaystyle {\boldsymbol {P}}}
(
∏
i
=
0
m
{\displaystyle {\big (}\prod _{i=0}^{m}}
[
1
−
σ
i
2
−
i
σ
i
2
−
i
1
]
)
{\displaystyle {\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix}}{\big )}}
[
x
y
]
,
(
16
)
{\displaystyle {\begin{bmatrix}x\\y\end{bmatrix}},(16)}
де
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.}}}
Своєю чергою, добуток матриць, взятий у дужки (16), можна зобразити однією результуючою матрицею повороту
T
r
{\displaystyle T_{r}}
T
r
=
{\displaystyle {\boldsymbol {T_{r}=}}}
[
C
C
−
S
S
S
S
C
C
]
=
{\displaystyle {\begin{bmatrix}CC&-SS\\SS&CC\end{bmatrix}}{\boldsymbol {=}}}
∏
i
=
0
m
{\displaystyle \prod _{i=0}^{m}}
[
1
−
σ
i
2
−
i
σ
i
2
−
i
1
]
,
(
17
)
{\displaystyle {\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix}},(17)}
де
C
C
=
{\displaystyle {\boldsymbol {CC=}}}
c
o
s
ϕ
/
P
=
c
o
s
(
∑
i
=
0
m
σ
i
α
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
σ
i
α
i
)
/
P
,
{\displaystyle sin\phi /P=sin{\big (}\sum _{i=0}^{m}\sigma _{i}\alpha _{i}{\big )}/P,}
Звідси (16) набуде вигляду
[
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&-sin\phi /P\\sin\phi /P&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&-SS\\SS&CC\end{bmatrix}}}
[
x
P
y
P
]
(
18
)
{\displaystyle {\begin{bmatrix}xP\\yP\end{bmatrix}}(18)}
Як випливає з (11), (16), множення замінено зсувами, що значно спрощує апаратну реалізацію обчислювачів.
Вилучивши з (10) масштабуючий коефіцієнт
c
o
s
α
i
=
1
/
1
+
2
−
2
i
{\displaystyle cos\alpha _{i}=1/{\sqrt {1+2^{-2i}}}}
[
x
i
+
1
y
i
+
1
]
{\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}}
[
1
−
σ
i
2
−
i
σ
i
2
−
i
1
]
{\displaystyle {\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix}}}
[
x
i
y
i
]
(
19
)
{\displaystyle {\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}(19)}
або в розгорнутому вигляді
{
x
i
+
1
=
x
i
−
σ
i
y
i
2
−
i
y
i
+
1
=
y
i
+
σ
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)}
Якщо виконати всі
m
+
1
{\displaystyle m+1}
[
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&-SS\\SS&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&-sin\phi /P\\sin\phi /P&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 &-sin\phi \\sin\phi &cos\phi \end{bmatrix}}}
[
x
y
]
,
(
21
)
{\displaystyle {\begin{bmatrix}x\\y\end{bmatrix}},(21)}
[
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 &-sin\phi \\sin\phi &cos\phi \end{bmatrix}}}
[
x
/
P
y
/
P
]
,
(
22
)
{\displaystyle {\begin{bmatrix}x/P\\y/P\end{bmatrix}},(22)}
або
x
m
+
1
=
K
m
[
x
c
o
s
(
∑
i
=
0
m
σ
i
α
i
)
−
y
s
i
n
(
∑
i
=
0
m
σ
i
α
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
σ
i
α
i
)
+
x
s
i
n
(
∑
i
=
0
m
σ
i
α
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)}
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)}
де
K
m
{\displaystyle K_{m}}
Зв'язок між векторами (xm+1 ,ym+1 )T та (x' ,y' )T такий:
[
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)}
Ілюстрація ітерацій CORDIC Рівняння (27) — (30) описують традиційний ітераційний CORDIC у режимі обертання (Rotation mode) для колової системи координат
x
i
+
1
=
x
i
−
σ
i
y
i
2
−
i
;
{\displaystyle x_{i+1}=x_{i}-\sigma _{i}y_{i}2^{-i};\;}
y
i
+
1
=
y
i
+
σ
i
x
i
2
−
i
;
(
27
)
{\displaystyle y_{i+1}=y_{i}+\sigma _{i}x_{i}2^{-i};\;(27)}
z
i
+
1
=
z
i
−
σ
i
α
i
;
(
28
)
{\displaystyle z_{i+1}=z_{i}-\sigma _{i}\alpha _{i};\;(28)}
де
σ
i
=
{
−
1
if
z
i
<
0
+
1
if
z
i
≥
0
{\displaystyle \sigma _{i}={\begin{cases}-1&{\mbox{if }}z_{i}<0\\+1&{\mbox{if }}z_{i}\geq 0\end{cases}}}
i
=
0
,
1
,
2
,
.
.
.
,
m
,
(
29
)
{\displaystyle {\boldsymbol {i=0,1,2,...,m}},(29)}
α
i
=
arctan
(
2
−
i
)
,
(
30
)
{\displaystyle \alpha _{i}=\arctan {\big (}2^{-i}{\big )},(30)}
причому
x
0
=
x
,
y
0
=
y
,
z
0
=
ϕ
{\displaystyle x_{0}=x,y_{0}=y,z_{0}=\phi }
Тут введено ще одну змінну
z
{\displaystyle z\,}
ϕ
{\displaystyle \phi \,}
i
→∝
{\displaystyle i\to \propto }
z
i
+
1
{\displaystyle z_{i+1}\,}
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},\,}
Якщо прийняти
x
0
=
P
=
1
/
K
m
,
y
0
=
0
,
{\displaystyle x_{0}=P=1/K_{m},y_{0}=0,\,}
x
i
+
1
=
x
i
+
σ
i
y
i
2
−
i
;
{\displaystyle x_{i+1}=x_{i}+\sigma _{i}y_{i}2^{-i};\,}
y
i
+
1
=
y
i
+
σ
i
x
i
2
−
i
;
(
31
)
{\displaystyle y_{i+1}=y_{i}+\sigma _{i}x_{i}2^{-i};(31)\,}
z
i
+
1
=
z
i
−
σ
i
α
i
;
(
32
)
{\displaystyle z_{i+1}=z_{i}-\sigma _{i}\alpha _{i};(32)\,}
де
σ
i
=
{
−
1
if
z
i
<
0
;
+
1
if
z
i
≥
0
;
{\displaystyle \sigma _{i}={\begin{cases}-1&{\mbox{if }}z_{i}<0;\\+1&{\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)}
α
i
=
arctan
h
(
2
−
i
)
,
(
34
)
{\displaystyle \alpha _{i}=\arctan h{\big (}2^{-i}{\big )},(34)}
причому
x
1
=
x
,
y
1
=
y
,
z
1
=
ϕ
{\displaystyle x_{1}=x,y_{1}=y,z_{1}=\phi }
i
{\displaystyle i}
K
m
′
{\displaystyle K_{m}^{'}}
P
m
1
′
=
∏
i
=
1
m
c
o
s
h
(
α
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^{'}.}
Якщо ж початковий вектор задано координатами
x
0
=
x
,
y
0
=
y
,
z
0
=
0
{\displaystyle x_{0}=x,y_{0}=y,z_{0}=0\,}
y
{\displaystyle y\,}
i
→∝
{\displaystyle i\to \propto }
y
i
+
1
{\displaystyle y_{i+1}\,}
x
i
+
1
=
x
i
+
σ
i
y
i
2
−
i
;
{\displaystyle x_{i+1}=x_{i}+\sigma _{i}y_{i}2^{-i}\,;}
y
i
+
1
=
y
i
−
σ
i
x
i
2
−
i
;
(
35
)
;
{\displaystyle y_{i+1}=y_{i}-\sigma _{i}x_{i}2^{-i};(35)\,;}
z
i
+
1
=
z
i
+
σ
i
α
i
;
(
36
)
{\displaystyle z_{i+1}=z_{i}+\sigma _{i}\alpha _{i};(36)\,}
де
σ
i
=
{
−
1
if
y
i
<
0
+
1
if
y
i
≥
0
{\displaystyle \sigma _{i}={\begin{cases}-1&{\mbox{if }}y_{i}<0\\+1&{\mbox{if }}y_{i}\geq 0\end{cases}}}
i
=
0
,
1
,
2...
,
m
,
(
37
)
{\displaystyle {\boldsymbol {i=0,1,2...,m}},(37)}
α
i
=
arctan
(
2
−
i
)
.
(
38
)
{\displaystyle \alpha _{i}=\arctan {\big (}2^{-i}{\big )}.(38)}
У такому разі обчислюються функції
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)}
Для гіперболічної системи координат у векторному режимі (Vectoring mode) рівняння матимуть вигляд
x
i
+
1
=
x
i
−
σ
i
y
i
2
−
i
;
{\displaystyle x_{i+1}=x_{i}-\sigma _{i}y_{i}2^{-i};\,}
y
i
+
1
=
y
i
−
σ
i
x
i
2
−
i
;
(
40
)
{\displaystyle y_{i+1}=y_{i}-\sigma _{i}x_{i}2^{-i};(40)\,}
z
i
+
1
=
z
i
+
σ
i
α
i
,
(
41
)
{\displaystyle z_{i+1}=z_{i}+\sigma _{i}\alpha _{i},(41)\,}
де
σ
i
=
{
−
1
if
y
i
<
0
;
+
1
if
y
i
≥
0
;
{\displaystyle \sigma _{i}={\begin{cases}-1&{\mbox{if }}y_{i}<0;\\+1&{\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)}
α
i
=
arctan
h
(
2
−
i
)
,
(
43
)
{\displaystyle \alpha _{i}=\arctan h{\big (}2^{-i}{\big )},(43)}
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)}
Для уніфікації методу CORDIC пропонуємо використати такий варіант узагальнення [11]:
x
i
+
1
=
x
i
−
M
(
R
−
V
)
σ
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
)
σ
i
x
i
2
−
i
;
(
45
)
{\displaystyle y_{i+1}=y_{i}+{\big (}R-V)\sigma _{i}x_{i}2^{-i};(45)}
z
i
+
1
=
z
i
+
(
V
−
R
)
σ
i
α
i
.
(
46
)
{\displaystyle z_{i+1}=z_{i}+{\big (}V-R)\sigma _{i}\alpha _{i}.(46)}
де
M
−
{\displaystyle \,M-}
M
=
1
{\displaystyle M=1}
M
=
−
1
{\displaystyle M=-1}
M
=
0
{\displaystyle M=0}
Rotation mode ) R=1, V=0 та у векторному режимі (Vectoring mode ) — навпаки R=0, V=1;
σ
i
{\displaystyle \sigma _{i}\,}
σ
i
=
s
i
g
n
(
z
i
)
{\displaystyle \sigma _{i}=sign{\big (}z_{i})}
σ
i
=
s
i
g
n
(
y
i
)
{\displaystyle \sigma _{i}=sign{\big (}y_{i})}
σ
i
=
{
−
1
,
+
1
}
;
{\displaystyle \sigma _{i}={\big \{}-1,+1{\big \}};}
M
=
1
α
i
=
a
r
c
t
a
n
(
2
−
i
)
;
{\displaystyle M=1\ \alpha _{i}=arctan{\big (}2^{-i});}
M
=
−
1
α
i
=
a
r
c
t
a
n
h
(
2
−
i
)
;
{\displaystyle M=-1\ \alpha _{i}=arctanh{\big (}2^{-i});}
M
=
0
α
i
=
2
−
i
.
{\displaystyle M=0\,\alpha _{i}=2^{-i}.\,}
Таблиця деяких функцій, що обчислюються з допомогою 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 )}}
σ
i
=
{
−
1
if
z
i
<
0
+
1
if
z
i
≥
0
{\displaystyle \sigma _{i}={\begin{cases}-1&{\mbox{if }}z_{i}<0\\+1&{\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 )}}
σ
i
=
{
−
1
if
y
i
<
0
+
1
if
y
i
≥
0
{\displaystyle \sigma _{i}={\begin{cases}-1&{\mbox{if }}y_{i}<0\\+1&{\mbox{if }}y_{i}\geq 0\end{cases}}}
M
=
1
{\displaystyle M=1}
α
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
(
α
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
−
σ
i
y
i
2
−
i
;
{\displaystyle x_{i+1}=x_{i}-\sigma _{i}y_{i}2^{-i};\,}
y
i
+
1
=
y
i
+
σ
i
x
i
2
−
i
{\displaystyle y_{i+1}=y_{i}+\sigma _{i}x_{i}2^{-i}\,}
z
i
+
1
=
z
i
−
σ
i
α
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
+
σ
i
y
i
2
−
i
;
{\displaystyle x_{i+1}=x_{i}+\sigma _{i}y_{i}2^{-i};\,}
y
i
+
1
=
y
i
−
σ
i
x
i
2
−
i
{\displaystyle y_{i+1}=y_{i}-\sigma _{i}x_{i}2^{-i}\,}
z
i
+
1
=
z
i
+
σ
i
α
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\,}
α
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
(
α
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
+
σ
i
y
i
2
−
i
;
{\displaystyle 1.\qquad x_{i+1}=x_{i}+\sigma _{i}y_{i}2^{-i};\,}
y
i
+
1
=
y
i
+
σ
i
x
i
2
−
i
{\displaystyle y_{i+1}=y_{i}+\sigma _{i}x_{i}2^{-i}\,}
z
i
+
1
=
z
i
−
σ
i
α
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
+
σ
i
q
i
2
−
i
{\displaystyle 2.\qquad q_{i+1}=q_{i}+\sigma _{i}q_{i}2^{-i}\,}
z
i
+
1
=
z
i
−
σ
i
α
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
−
σ
i
q
i
2
−
i
{\displaystyle 3.\qquad q_{i+1}=q_{i}-\sigma _{i}q_{i}2^{-i}\,}
z
i
+
1
=
z
i
−
σ
i
α
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
−
σ
i
y
i
2
−
i
;
{\displaystyle 1.\qquad x_{i+1}=x_{i}-\sigma _{i}y_{i}2^{-i};\,}
y
i
+
1
=
y
i
−
σ
i
x
i
2
−
i
{\displaystyle y_{i+1}=y_{i}-\sigma _{i}x_{i}2^{-i}\,}
z
i
+
1
=
z
i
+
σ
i
α
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
−
σ
i
y
i
2
−
i
;
{\displaystyle 2.\qquad x_{i+1}=x_{i}-\sigma _{i}y_{i}2^{-i};\,}
y
i
+
1
=
y
i
−
σ
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
−
σ
i
y
i
2
−
i
;
{\displaystyle 3.\qquad x_{i+1}=x_{i}-\sigma _{i}y_{i}2^{-i};\,}
y
i
+
1
=
y
i
−
σ
i
x
i
2
−
i
{\displaystyle y_{i+1}=y_{i}-\sigma _{i}x_{i}2^{-i}\,}
z
i
+
1
=
z
i
+
σ
i
α
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\,}
α
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
+
σ
i
x
0
2
−
i
{\displaystyle 1.\qquad y_{i+1}=y_{i}+\sigma _{i}x_{0}2^{-i}\,}
z
i
+
1
=
z
i
−
σ
i
α
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
+
σ
i
x
0
2
−
i
{\displaystyle 2.\qquad y_{i+1}=y_{i}+\sigma _{i}x_{0}2^{-i}\,}
z
i
+
1
=
z
i
−
σ
i
α
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
−
σ
i
x
0
∗
2
−
i
{\displaystyle y_{i+1}=y_{i}-\sigma _{i}x_{0}*2^{-i}\,}
z
i
+
1
=
z
i
+
σ
i
α
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\,}
Модифікації (вдосконалення) методу CORDIC спрямовані на підвищення швидкодії, зменшення кількості ітерацій, розширення функціональних можливостей, спрощення апаратної реалізації, збільшення набору реалізованих функцій.
Зокрема, одне з основних завдань модифікацій методу — зменшити кількість ітерацій, зберігши похибки обчислень класичного методу. Опис (45) — (46) поширюється лише на синхронний режим роботи CORDIC (або на знакозмінні ітерації) [4]. Це пов'язано з тим що треба зберегти сталість значення коефіцієнта деформації вектора [4, 7]. Однак існують функції, для яких не потрібно дотримуватись цих вимог, тому що коефіцієнт деформації не входить до складу виразів, за якими обчислюють, або його вплив усувається, оскільки в цих операціях(макроопераціях) виконується операція ділення. Зокрема, це стосується обчислення функцій
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)}
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.Байков В. Д., Смолов В. Б. Аппаратурная реализация элементарных функций в ЦВМ , Ленинград, изд-во ЛГУ, 1975, 96 стр. [Архівовано 15 січня 2011 у Wayback Machine .] Байков В. Д., Смолов В. Б. Специализированные процессоры: итерационные алгоритмы и структуры , Москва, «Радио и связь» 1985, 288 стр. [Архівовано 18 липня 2011 у Wayback Machine .] CORDIC Bibliography Site [Архівовано 10 червня 2015 у Wayback Machine .] 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 .]
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b32d6ac2ebf0fdeb9cb8ff98f7e3536d45034e0)
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/960ca17b6fdff6d4e0d685f336da28d1a7578d7a)
![{\displaystyle \phi \in {\big [}0,1.74{\big ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/743e333127a34569b9e46563e2aaca8067b1d6b8)
![{\displaystyle \phi \in {\big [}0,1.118{\big ]}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92393989779d9d6357a3e4e3c0cb4f5740bb4f18)
![{\displaystyle for\ arctanh-{\frac {y_{1}}{x_{1}}}\in {\big [}0,0.8069{\big ]}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/daf1d3e8393fa6ff6784249fe9acc347da880bb1)
![{\displaystyle W\in {\big [}0.03,2.33{\big ]}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d17c6e01ef0c785b25e31e9f547c9f421b1b3679)
![{\displaystyle W\in {\big [}0.107,9.359{\big ]}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d0f8f636a3ce9846b900de261aaeb6f84ea7b37)
