CORDIC

Алгоритм для вычисления тригонометрических, гиперболических, логарифмических и экспоненциальных функций

CORDIC (для CO ордината R otation DI gital C компьютер), также известный как алгоритм Волдера, включая Circular CORDIC (Jack E. Volder), Linear CORDIC, Hyperbolic CORDIC (John Stephen Walther) и Generalized Hyperbolic CORDIC (GH CORDIC ) (Yuanyong Luo et al.), представляет собой простой и эффективный алгоритм для вычисления тригонометрических функций, гиперболических функций, квадратных корней, умножений., деления и экспоненты и логарифмы с произвольной базой, обычно сходящиеся с одной цифрой (или битом) на итерацию. Таким образом, CORDIC также является примером цифровых алгоритмов. CORDIC и близкие к нему методы, известные как псевдоумножение и псевдоделение или комбинирование множителей, обычно используются, когда нет аппаратного умножителя. (например, в простых микроконтроллерах и FPGA ), поскольку единственные операции, которые требуются, это сложение, вычитание, битовый сдвиг и таблицы поиска. Таким образом, все они принадлежат к классу алгоритмов сдвига и сложения. В информатике CORDIC часто используется для реализации арифметики с плавающей запятой, когда на целевой платформе не хватает аппаратного умножения по причинам стоимости или места.

• 1 История
• 2 Приложения
  • 2.1 Аппаратное обеспечение
  • 2.2 Программное обеспечение
• 3 Режимы работы
  • 3.1 Режим вращения
  • 3.2 Режим векторизации
• 4 Реализация
  • 4.1 Пример программного обеспечения
  • 4.2 Пример оборудования
• 5 Связанные алгоритмы
• 6 См. Также
• 7 Ссылки
• 8 Дополнительная литература
• 9 Внешние ссылки

Похожие математические методы были опубликованы Генри Бриггсом еще в 1624 г. и Робертом Флауэром в 1771 г., но CORDIC лучше оптимизирован для ЦП с конечным состоянием низкой сложности.

CORDIC был разработан в 1956 году отделом аэроэлектроники компании Convair из-за необходимости замены аналогового преобразователя в B -58 бомбардировщик с более точным и производительным цифровым решением в реальном времени. Поэтому CORDIC иногда называют a.

В своем исследовании Волдер был вдохновлен формулой из издания 1946 года Справочника по химии и физике CRC :

$K\; n\; R\; sin\; \; (\theta \; \pm \; \phi )\; =\; R\; sin\; \; (\theta )\; \pm \; 2\; -\; n\; R\; cos\; \; (\theta ),\; K\; n\; R\; cos\; \; (\theta \; \pm \; \phi )\; =\; R\; cos\; \; (\theta )\; \mp \; 2\; -\; n\; R\; sin\; \; (\theta ),\; \{\; \backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; K\_\; \{n\}\; R\; \backslash \; sin\; (\backslash \; theta\; \backslash \; pm\; \backslash \; varphi)\; =\; R\; \backslash \; sin\; (\backslash \; theta)\; \backslash \; pm\; 2\; ^\; \{-\; n\}\; R\; \backslash \; cos\; (\backslash \; theta),\; \backslash \backslash \; K\_\; \{n\}\; R\; \backslash \; cos\; (\backslash \; theta\; \backslash \; pm\; \backslash \; varphi)\; =\; R\; \backslash \; cos\; (\backslash \; theta)\; \backslash \; mp\; 2\; ^\; \{-\; n\}\; R\; \backslash \; sin\; (\backslash \; theta),\; \backslash \backslash \backslash \; конец\; \{выровнено\}\}\}$

с $К\; n\; =\; 1\; +\; 2\; -\; 2\; n\; \{\backslash \; displaystyle\; K\_\; \{n\}\; =\; \{\backslash \; sqrt\; \{1\; +\; 2\; ^\; \{-\; 2n\}\}\}\}$, $загар\; \; (\phi )\; =\; 2\; -\; n\; \{\backslash \; displaystyle\; \backslash \; tan\; (\backslash \; varphi)\; =\; 2\; ^\; \{-\; n\}\}$.

Его исследование привело к внутреннему техническому отчету, в котором предлагался алгоритм CORDIC для решения функций синус и косинус и прототип компьютера, реализующего это. В отчете также обсуждалась возможность вычисления гиперболического вращения координат, логарифмов и экспоненциальных функций с помощью модифицированных алгоритмов CORDIC. В то время также было задумано использование CORDIC для умножения и деления. Основываясь на принципе CORDIC, Дэн Х. Даггетт, коллега Волдера из Convair, разработал алгоритмы преобразования между двоичным кодом и десятичным двоичным кодом (BCD).

В 1958 году, наконец, начал работу Convair. создать демонстрационную систему для решения проблем с исправлением радара под названием CORDIC I, завершенную в 1960 году без Волдера, который уже покинул компанию. Более универсальные модели CORDIC II A (стационарные) и B (бортовые) были построены и испытаны Даггеттом и Гарри Шуссом в 1962 году.

Алгоритм CORDIC Волдера был впервые публично описан в 1959 году, что заставило его включить в навигационные компьютеры от компаний, включая: Computer Control, Litton, Kearfott, Lear-Siegler, Sperry, Raytheon и Collins Radio в ближайшее время.

Волдер объединился с Малкольмом Макмилланом для создания Athena, фиксированной точки настольного калькулятора используя свой двоичный алгоритм CORDIC. Этот дизайн был представлен на Hewlett-Packard в июне 1965 г., но не принят. Тем не менее, Макмиллан представил (HP) алгоритм Волдера, и когда Кокран позже встретил Волдера, он направил его к аналогичному подходу (IBM), предложенному в 1961 году как псевдоумножение и псевдоделение. Метод Меггитта также предлагал использовать основание 10, а не чем основание 2, которое до сих пор использовалось Volder's CORDIC. Эти усилия привели к логической реализации ROMable прототипа десятичной машины CORDIC внутри Hewlett-Packard в 1966 году, построенной и концептуально выведенной из прототипа Green Machine, четырехфункционального плавающего устройства. Point настольный калькулятор он завершил в логике DTL в декабре 1964 года. Результатом этого проекта стала публичная демонстрация первого настольного калькулятора Hewlett-Packard с научными функциями, hp 9100A в Март 1968 года, серийное производство началось позже в том же году.

Когда Wang Laboratories обнаружили, что hp 9100A использовала подход, аналогичный методу комбинирования факторов в их более раннем ( Сентябрь 1964) и (январь 1965) настольные калькуляторы Logarithmic Computing Instrument, они безуспешно обвинили Hewlett-Packard в нарушении одного из патентов An Wang в 1968 году.

в Hewlett-Packard обобщили. алгоритм в алгоритм Unified CORDIC в 1971 году, позволяющий вычислить h аперболические функции, натуральные экспоненты, натуральные логарифмы, умножения, деления и квадратные корни. Подпрограммы CORDIC для тригонометрических и гиперболических функций могут использовать большую часть своего кода. Результатом этой разработки стал первый научный портативный калькулятор, HP-35 в 1972 году. На основе гиперболического CORDIC, et al. далее предложил обобщенный гиперболический CORDIC (GH CORDIC) для прямого вычисления логарифмов и экспонент с произвольной фиксированной базой в 2019 году. Теоретически гиперболический CORDIC является частным случаем GH CORDIC.

Первоначально CORDIC был реализован только с использованием двоичная система счисления и, несмотря на то, что Меггитт предлагал использовать десятичную систему для своего подхода псевдоумножения, десятичная система CORDIC оставалась в основном неслыханной еще несколько лет, так что Герман Шмид и Энтони Богацки все еще предлагал его как новинку еще в 1973 году, и только позже выяснилось, что Hewlett-Packard реализовала его уже в 1966 году.

Десятичный CORDIC стал широко использоваться в карманных калькуляторах, большинство из которых работают в двоично-десятичном формате (BCD), а не в двоичном формате. Это изменение формата ввода и вывода не повлияло на основные алгоритмы вычислений CORDIC. CORDIC особенно хорошо подходит для портативных калькуляторов, в которых низкая стоимость - и, следовательно, малое количество микросхем - гораздо важнее скорости.

CORDIC был реализован в ARM- на основе STM32G4, Intel 8087, 80287, 80387 до серии сопроцессоров 80486, а также в Motorola 68881 и 68882 для некоторых видов команд с плавающей запятой, в основном как способ уменьшить количество вентилей (и сложность) подсистемы FPU.

CORDIC использует простые операции сдвига-сложения для нескольких вычислительных задач, таких как вычисление тригонометрических, гиперболических и логарифмических функций, действительное и комплексное умножение, деление, вычисление квадратного корня, решение линейные системы, оценка собственных значений,, разложение по сингулярным значениям,, QR-факторизация и многие другие. Как следствие, CORDIC использовался для приложений в различных областях, таких как сигнал и обработка изображений, системы связи, робототехника и Трехмерная графика помимо общенаучных и технических вычислений.

Аппаратное обеспечение

Алгоритм использовался в навигационной системе программы Apollo Лунный вездеход для вычисления пеленга и дальности или расстояния от лунного модуля. CORDIC использовался для реализации математического сопроцессора Intel 8087 в 1980 году, что позволило избежать необходимости реализации аппаратного умножения.

CORDIC обычно работает быстрее, чем другие подходы, когда аппаратный умножитель недоступен (например, микроконтроллер), или когда количество вентилей, необходимых для реализации поддерживаемых им функций, должно быть минимизировано (например, в FPGA или ASIC ).

С другой стороны, когда доступен аппаратный умножитель (например, в микропроцессоре DSP ), методы поиска по таблице и ряды степеней обычно быстрее, чем CORDIC. В последние годы алгоритм CORDIC широко используется в различных биомедицинских приложениях, особенно в реализациях FPGA.

Программное обеспечение

Многие старые системы с ЦП только для целых чисел реализовали CORDIC в различной степени как часть своих библиотек с плавающей запятой IEEE. Поскольку большинство современных процессоров общего назначения имеют регистры с плавающей запятой с общими операциями, такими как сложение, вычитание, умножение, деление, синус, косинус, квадратный корень, log 10, натуральный логарифм, необходимость реализации CORDIC в их с ПО практически не существует. Только микроконтроллер или специальные приложения, обеспечивающие безопасность и ограниченные по времени, должны рассматривать возможность использования CORDIC.

Режим вращения

CORDIC можно использовать для вычисления ряда различных функций. Это объяснение показывает, как использовать CORDIC в режиме вращения для вычисления синуса и косинуса угла, предполагая, что желаемый угол задан в радианах и представлен в формате с фиксированной точкой. Чтобы определить синус или косинус для угла $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$, координата y или x точки на единичной окружности, соответствующей желаемому углу, должна быть найденным. Используя CORDIC, можно начать с вектора $v\; 0\; \{\backslash \; displaystyle\; v\_\; \{0\}\}$:

$v\; 0\; =\; [1\; 0].\; \{\backslash \; displaystyle\; v\_\; \{0\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; 1\; \backslash \backslash \; 0\; \backslash \; end\; \{bmatrix\}\}.\}$

Иллюстрация выполняющегося алгоритма CORDIC

В первой итерации этот вектор повернут на 45 ° против часовой стрелки, чтобы получить вектор $v\; 1\; \{\backslash \; displaystyle\; v\_\; \{1\}\}$. Последовательные итерации поворачивают вектор в том или ином направлении путем уменьшения размера, пока не будет достигнут желаемый угол. Шаг $i\; \{\backslash \; displaystyle\; i\}$размер $arctan\; \; (2\; -\; i)\; \{\backslash \; displaystyle\; \backslash \; arctan\; \{(2\; ^\; \{-\; i\})\}\}$for $i\; =\; 0,\; 1,\; 2,\dots \; \{\backslash \; displaystyle\; i\; =\; 0,1,2,\; \backslash \; dots\}$.

Более формально, каждая итерация вычисляет поворот, который выполняется путем умножения вектора $vi\; -\; 1\; \{\backslash \; displaystyle\; v\_\; \{i-1\}\}$с матрицей поворота $R\; i\; \{\backslash \; displaystyle\; R\_\; \{i\}\}$:

$vi\; =\; R\; ivi\; -\; 1.\; \{\backslash \; displaystyle\; v\_\; \{i\}\; =\; R\_\; \{i\}\; v\_\; \{i-1\}.\}$

Матрица вращения задается как

$R\; i\; =\; [cos\; \; (\gamma \; i)\; -\; sin\; \; (\gamma \; i)\; sin\; \; (\gamma \; i)\; cos\; \; (\gamma \; i)].\; \{\backslash \; Displaystyle\; R\_\; \{я\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; cos\; (\backslash \; gamma\; \_\; \{i\})\; -\; \backslash \; sin\; (\backslash \; gamma\; \_\; \{i\})\; \backslash \backslash \backslash \; sin\; (\backslash \; gamma\; \_\; \{i\})\; \backslash \; cos\; (\backslash \; gamma\; \_\; \{i\})\; \backslash \; end\; \{bmatrix\}\}.\}$

Используя следующие два тригонометрических тождества :

$cos\; \; (\gamma \; i)\; =\; 1\; 1\; +\; tan\; 2\; \; (\gamma \; i),\; грех\; \; (\gamma \; я)\; знак\; равно\; загар\; \; (\gamma \; я)\; 1\; +\; загар\; 2\; \; (\gamma \; я),\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; cos\; (\backslash \; gamma\; \_\; \{i\})\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{1+\; \backslash \; tan\; ^\; \{2\}\; (\backslash \; gamma\; \_\; \{i\})\}\}\},\; \backslash \backslash \backslash \; sin\; (\backslash \; gamma\; \_\; \{i\})\; =\; \{\backslash \; frac\; \{\backslash \; tan\; (\backslash \; gamma\; \_\; \{i\; \})\}\; \{\backslash \; sqrt\; \{1+\; \backslash \; tan\; ^\; \{2\}\; (\backslash \; gamma\; \_\; \{i\})\}\}\},\; \backslash \; end\; \{align\}\}\}$

матрица поворота принимает вид

$R\; i\; =\; 1\; 1\; +\; tan\; 2\; \; (\gamma \; i)\; [1\; -\; tan\; \; (\gamma \; i)\; tan\; \; (\gamma \; i)\; 1].\; \{\backslash \; displaystyle\; R\_\; \{i\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{1+\; \backslash \; tan\; ^\; \{2\}\; (\backslash \; gamma\; \_\; \{i\})\}\}\}\; \{\backslash \; begin\; \{bmatrix\}\; 1\; -\; \backslash \; tan\; (\backslash \; gamma\; \_\; \{i\})\; \backslash \backslash \backslash \; tan\; (\backslash \; gamma\; \_\; \{i\})\; 1\; \backslash \; end\; \{bmatrix\}\}.\}$

Выражение для повернутого вектора $vi\; =\; R\; ivi\; -\; 1\; \{\backslash \; displaystyle\; v\_\; \{i\; \}\; =\; R\_\; \{i\}\; v\_\; \{i-1\}\}$тогда становится

$vi\; =\; 1\; 1\; +\; tan\; 2\; \; (\gamma \; i)\; [1\; -\; tan\; \; (\gamma \; i)\; tan\; \; (\gamma \; i)\; 1]\; [xi\; -\; 1\; yi\; -\; 1],\; \{\backslash \; displaystyle\; v\_\; \{i\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{1+\; \backslash \; tan\; ^\; \{2\}\; (\backslash \; gamma\; \_\; \{i\})\}\}\}\; \{\; \backslash \; begin\; \{bmatrix\}\; 1\; -\; \backslash \; tan\; (\backslash \; gamma\; \_\; \{i\})\; \backslash \backslash \backslash \; tan\; (\backslash \; gamma\; \_\; \{i\})\; 1\; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; x\_\; \{i-1\}\; \backslash \backslash \; y\_\; \{i-1\}\; \backslash \; end\; \{bmatrix\}\},\}$

где $xi\; -\; 1\; \{\backslash \; displaystyle\; x\_\; \{i-1\}\}$и $yi\; -\; 1\; \{\backslash \; displaystyle\; y\_\; \{i-1\}\}$- компоненты $vi\; -\; 1\; \{\backslash \; displaystyle\; v\_\; \{i-1\}\}$. Ограничение углов $\gamma \; i\; \{\backslash \; displaystyle\; \backslash \; gamma\; \_\; \{i\}\}$таким образом, чтобы $tan\; \; (\gamma \; i)\; =\; \pm \; 2\; -\; i\; \{\backslash \; displaystyle\; \backslash \; tan\; (\backslash \; gamma\; \_\; \{\; i\})\; =\; \backslash \; pm\; 2\; ^\; \{-\; i\}\}$, умножение на тангенс можно заменить делением на степень двойки, что эффективно выполняется в аппаратном обеспечении цифрового компьютера с использованием битовый сдвиг. Тогда выражение принимает вид

$vi\; =\; K\; i\; [1\; -\; \sigma \; i\; 2\; -\; i\; \sigma \; i\; 2\; -\; i\; 1]\; [xi\; -\; 1\; yi\; -\; 1],\; \{\backslash \; displaystyle\; v\_\; \{i\}\; =\; K\_\; \{i\}\; \{\backslash \; begin\; \{bmatrix\}\; 1\; -\; \backslash \; sigma\; \_\; \{i\}\; 2\; ^\; \{-\; i\}\; \backslash \backslash \backslash \; sigma\; \_\; \{i\}\; 2\; ^\; \{-\; i\}\; 1\; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; x\_\; \{i-1\}\; \backslash \backslash \; y\_\; \{i-1\}\; \backslash \; end\; \{bmatrix\}\},\}$

где

$K\; i\; =\; 1\; 1\; +\; 2-2\; i,\; \{\backslash \; displaystyle\; K\_\; \{i\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{1\; +\; 2\; ^\; \{-\; 2i\}\}\}\},\}$

и $\sigma \; i\; \{\backslash \; displaystyle\; \backslash \; sigma\; \_\; \{i\}\}$используется для определения направления вращения: если угол $\gamma \; i\; \{\backslash \; displaystyle\; \backslash \; gamma\; \_\; \{i\}\}$положительный, то $\sigma \; i\; \{\backslash \; displaystyle\; \backslash \; sigma\; \_\; \{i\}\}$равно +1, в противном случае - -1.

$K\; i\; \{\backslash \; displaystyle\; K\_\; \{i\}\}$можно игнорировать в итеративном процессе, а затем применять после этого с коэффициентом масштабирования

$K\; (n)\; =\; \prod \; i\; =\; 0\; n\; -\; 1\; K\; я\; знак\; равно\; \prod \; я\; знак\; равно\; 0\; N\; -\; 1\; 1\; 1\; +\; 2\; -\; 2\; я,\; \{\backslash \; Displaystyle\; К\; (п)\; =\; \backslash \; prod\; \_\; \{я\; =\; 0\}\; ^\; \{п-1\}\; K\_\; \{я\}\; =\; \backslash \; prod\; \_\; \{я\; =\; 0\}\; ^\; \{n-1\}\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{1\; +\; 2\; ^\; \{-\; 2i\}\}\}\},\}$

который вычисляется заранее и сохраняется в таблице или как отдельная константа, если количество итераций фиксировано. Это исправление также можно сделать заранее, масштабируя $v\; 0\; \{\backslash \; displaystyle\; v\_\; \{0\}\}$и, следовательно, сохраняя умножение. Кроме того, можно отметить, что

$K\; =\; lim\; n\; \to \; \infty \; K\; (n)\; \approx \; 0,6072529350088812561694\; \{\backslash \; displaystyle\; K\; =\; \backslash \; lim\; \_\; \{n\; \backslash \; to\; \backslash \; infty\}\; K\; (n)\; \backslash \; приблизительно\; 0,6072529350088812561694\}$

, чтобы разрешить дальнейшее снижение сложности алгоритма. Некоторые приложения могут вообще не исправлять $K\; \{\backslash \; displaystyle\; K\}$, что дает выигрыш при обработке $A\; \{\backslash \; displaystyle\; A\}$:

$A\; =\; 1\; K\; =\; lim\; n\; \to \; \infty \; \prod \; i\; =\; 0\; n\; -\; 1\; 1\; +\; 2\; -\; 2\; i\; \approx \; 1,64676025812107.\; \{\backslash \; displaystyle\; A\; =\; \{\backslash \; frac\; \{1\}\; \{K\}\}\; =\; \backslash \; lim\; \_\; \{n\; \backslash \; to\; \backslash \; infty\}\; \backslash \; prod\; \_\; \{i\; =\; 0\}\; ^\; \{n-1\}\; \{\backslash \; sqrt\; \{1\; +\; 2\; ^\; \{-\; 2i\}\}\}\; \backslash \; приблизительно\; 1.64676025812107.\}$

После достаточного количества итераций угол вектора будет близок к желаемому углу $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$. Для большинства обычных целей 40 итераций (n = 40) достаточно, чтобы получить правильный результат с точностью до 10-го знака после запятой.

Осталось только определить, следует ли вращать по часовой стрелке или против часовой стрелки на каждой итерации (выбирая значение $\sigma \; \{\backslash \; displaystyle\; \backslash \; sigma\}$). Это делается путем отслеживания того, на сколько угол был повернут на каждой итерации, и вычитания этого из желаемого угла; затем, чтобы приблизиться к желаемому углу $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$, если $\beta \; n\; +\; 1\; \{\backslash \; displaystyle\; \backslash \; beta\; \_\; \{n\; +\; 1\}\}$положительно, вращение - по часовой стрелке, в противном случае - отрицательное, и вращение - против часовой стрелки:

$\beta \; i\; =\; \beta \; i\; -\; 1\; -\; \sigma \; i\; \gamma \; i,\; \gamma \; i\; =\; arctan\; \; (2\; -\; i).\; \{\backslash \; displaystyle\; \backslash \; beta\; \_\; \{i\}\; =\; \backslash \; beta\; \_\; \{i-1\}\; -\; \backslash \; sigma\; \_\; \{i\}\; \backslash \; gamma\; \_\; \{i\},\; \backslash \; quad\; \backslash \; gamma\; \_\; \{i\}\; =\; \backslash \; arctan\; (2\; ^\; \{-\; i\}).\}$

Значения $\gamma \; n\; \{\backslash \; displaystyle\; \backslash \; gamma\; \_\; \{n\}\}$также должны быть предварительно вычислены и сохранены. Но для малых углов $arctan\; \; (\gamma \; n)\; =\; \gamma \; n\; \{\backslash \; displaystyle\; \backslash \; arctan\; (\backslash \; gamma\; \_\; \{n\})\; =\; \backslash \; gamma\; \_\; \{n\}\}$в представлении с фиксированной точкой, уменьшение размера стола.

Как видно на иллюстрации выше, синус угла $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$является координатой y конечного вектора $vn,\; \{\; \backslash \; displaystyle\; v\_\; \{n\},\}$, а координата x - это значение косинуса.

Режим векторизации

Алгоритм режима вращения, описанный выше, может повернуть любой вектор (не только единичный вектор, выровненный по оси x) на угол между -90 ° и + 90 °. Решения о направлении вращения зависят от положительного или отрицательного значения $\beta \; i\; \{\backslash \; displaystyle\; \backslash \; beta\; \_\; \{i\}\}$.

Режим работы с векторизацией требует небольшой модификации алгоритма. Он начинается с вектора, координата x которого положительна, а координата y произвольна. Последовательные повороты имеют цель повернуть вектор к оси x (и, следовательно, уменьшить координату y до нуля). На каждом шаге значение y определяет направление вращения. Конечное значение $\beta \; i\; \{\backslash \; displaystyle\; \backslash \; beta\; \_\; \{i\}\}$содержит общий угол поворота. Конечное значение x будет величиной исходного вектора, масштабированного с помощью K. Таким образом, очевидное использование режима векторизации - это преобразование прямоугольных координат в полярные.

Пример программного обеспечения

Ниже приведена реализация CORDIC MATLAB / GNU Octave, которая не полагается ни на какие трансцендентные функции, за исключением предварительного вычисления таблиц. Если количество итераций n заранее определено, то вторая таблица может быть заменена одной константой. С помощью стандартной арифметики с двойной точностью и распечатки «длинного формата» в MATLAB точность результатов увеличивается для n примерно до 48.

function v = cordic (beta, n)% Эта функция вычисляет v = [cos (beta), sin (beta)] (beta в радианах)% с использованием n итераций. Увеличение n увеличит точность. если бета < -pi/2 || beta>пи / 2, если бета < 0 v = cordic(beta + pi, n); else v = cordic(beta - pi, n); end v = -v; % flip the sign for second or third quadrant return end % Initialization of tables of constants used by CORDIC % need a table of arctangents of negative powers of two, in radians: % angles = atan(2.^-(0:27)); angles = [... 0.78539816339745 0.46364760900081 0.24497866312686 0.12435499454676... 0.06241880999596 0.03123983343027 0.01562372862048 0.00781234106010... 0.00390623013197 0.00195312251648 0.00097656218956 0.00048828121119... 0.00024414062015 0.00012207031189 0.00006103515617 0.00003051757812... 0.00001525878906 0.00000762939453 0.00000381469727 0.00000190734863... 0.00000095367432 0.00000047683716 0.00000023841858 0.00000011920929... 0.00000005960464 0.00000002980232 0.00000001490116 0.00000000745058 ]; % and a table of products of reciprocal lengths of vectors [1, 2^-2j]: % Kvalues = cumprod(1./abs(1 + 1j*2.^(-(0:23)))) Kvalues = [... 0.70710678118655 0.63245553203368 0.61357199107790 0.60883391251775... 0.60764825625617 0.60735177014130 0.60727764409353 0.60725911229889... 0.60725447933256 0.60725332108988 0.60725303152913 0.60725295913894... 0.60725294104140 0.60725293651701 0.60725293538591 0.60725293510314... 0.60725293503245 0.60725293501477 0.60725293501035 0.60725293500925... 0.60725293500897 0.60725293500890 0.60725293500889 0.60725293500888 ]; Kn = Kvalues(min(n, length(Kvalues))); % Initialize loop variables: v = [1;0]; % start with 2-vector cosine and sine of zero poweroftwo = 1; angle = angles(1); % Iterations for j = 0:n-1; if beta < 0 sigma = -1; else sigma = 1; end factor = sigma * poweroftwo; % Note the matrix multiplication can be done using scaling by powers of two and addition subtraction R = [1, -factor; factor, 1]; v = R * v; % 2-by-2 matrix multiply beta = beta - sigma * angle; % update the remaining angle poweroftwo = poweroftwo / 2; % update the angle from table, or eventually by just dividing by two if j+2>длина (углы) угол = угол / 2; иначе угол = углы (j + 2); end end% Настройте длину выходного вектора на [cos (beta), sin (beta)]: v = v * Kn; return endfunction

Умножение матриц два на два может быть выполнено парой простых сдвигов и сложений.

x = v [0] - сигма * (v [1] * 2 ^ (- j)); y = сигма * (v [0] * 2 ^ (- j)) + v [1]; v = [x; y];

В Java класс Math имеет метод scalb (double x, int scale)для выполнения такого сдвига, C имеет функцию ldexp, а класс процессоров x86 имеет операция fscaleс плавающей запятой.

Пример оборудования

Количество логических вентилей для реализации CORDIC примерно сопоставимо с требуемым количеством для множителя, поскольку оба требуют комбинации сдвигов и сложений. Выбор реализации на основе множителя или CORDIC будет зависеть от контекста. Умножение двух комплексных чисел , представленных их действительными и мнимыми компонентами (прямоугольными координатами), например, требует 4 умножений, но может быть реализовано одним CORDIC, работающим с комплексными числами, представленными их полярными координатами, особенно если величина чисел не имеет значения (умножение комплексного вектора на вектор на единичной окружности фактически равносильно повороту). CORDIC часто используются в схемах для телекоммуникаций, таких как цифровые преобразователи с понижением частоты.

CORDIC является частью класса алгоритмов «сдвиг-и-сложение», как являются логарифмическими и экспоненциальными алгоритмами, полученными из работы Генри Бриггса. Другой алгоритм сдвига и сложения, который может использоваться для вычисления многих элементарных функций, - это алгоритм BKM, который является обобщением логарифмических и экспоненциальных алгоритмов на комплексную плоскость. Например, BKM можно использовать для вычисления синуса и косинуса действительного угла $x\; \{\backslash \; displaystyle\; x\}$(в радианах) путем вычисления экспоненты $0\; +\; ix\; \{\backslash \; displaystyle\; 0\; +\; ix\}$, что равно $цис\; \; (x)\; =\; соз\; \; (x)\; +\; i\; sin\; \; (x)\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{cis\}\; (x)\; =\; \backslash \; соз\; (х)\; +\; я\; \backslash \; грех\; (х)\}$. Алгоритм BKM немного сложнее, чем CORDIC, но имеет то преимущество, что ему не нужен коэффициент масштабирования (K).

• Методы вычисления квадратных корней
• IEEE 754
• Модули с плавающей запятой
• Цифровые схемы / CORDIC в Викиучебках

• Парини, Джозеф А. (1966-09-05). «DIVIC дает ответы на сложные навигационные вопросы». Электроника : 105–111. ISSN 0013-5070.(NB. DIVIC расшифровывается как DIgital Variable Increments Computer. Некоторые источники ошибочно ссылаются на это как на J. M. Parini.)
• Anderson, Stanley F.; Эрл, Джон Дж.; Гольдшмидт, Роберт Эллиотт; Пауэрс, Дон М. (1965-11-01). «IBM System / 360 Model 91: блок выполнения с плавающей запятой» (PDF). Журнал исследований и разработок IBM. Ривертон, Нью-Джерси, США (опубликовано в январе 1967 г.). 11 (1): 34–53. doi : 10.1147 / rd.111.0034. Проверено 2 января 2016 г.
• Ликкардо, Майкл А. (сентябрь 1968 г.). Процессор межсоединений с упором на работу в режиме CORDIC (диплом магистра). Беркли, Калифорния, США: Калифорнийский университет, Беркли, факультет электротехники. OCLC 500565168.
• Патент США 3576983A, Кокран, Дэвид С., «Цифровая калькуляторная система для вычисления квадратных корней», опубликовано 4 мая 1971 г., выпущено 4 мая 1971 г., присвоенный Hewlett-Packard Co. ([14] )
• (июль 1972 г.). «Автоматическое вычисление экспонент, логарифмов, отношений и квадратного корня» ( PDF). IBM Journal of Research and Development. 16(4): 380–388. doi : 10.1147 / rd.164.0380. ISSN 0018-8646. Проверено 02.01.2016.
• Эгберт, Уильям Э. (май 1977 г.). «Алгоритмы персонального калькулятора I: квадратные корни» (PDF). Hewlett-Packard Journal. Пало-Альто, Калифорния, США: Hewlett-Packard. 28(9): 22–24. Проверено 2 января 2016 г. ([15] )
• Эгберт, Уильям Э. (июнь 1977 г.). «Алгоритмы персонального калькулятора II: тригонометрические функции» (PDF). Hewlett-Packard Journal. Пало-Альто, Калифорния, США: Hewlett-Packard. 28(10): 17–20. Проверено 2 января 2016 г. ([16] )
• Эгберт, Уильям Э. (Novembe r 1977). «Алгоритмы персонального калькулятора III: обратные тригонометрические функции» (PDF). Журнал Hewlett-Packard. Пало-Альто, Калифорния, США: Hewlett-Packard. 29(3): 22–23. Проверено 2 января 2016 г. ([17] )
• Эгберт, Уильям Э. (апрель 1978 г.). «Алгоритмы персонального калькулятора IV: логарифмические функции» (PDF). Журнал Hewlett-Packard. Пало-Альто, Калифорния, США: Hewlett-Packard. 29(8): 29–32. Проверено 2 января 2016 г. ([18] )
• Сенциг, Дон (1975). «Алгоритмы калькулятора». Дайджест читателей IEEE Compcon. IEEE : 139–141. Каталог IEEE № 75 CH 0920-9C.
• Байков, Владимир Д. (1972), Вопросы исследования вычислений элементарных функций по методу «цифра за цифрой» [Задачи вычисления элементарных функций на основе цифр по цифра (CORDIC) техника] (кандидатская диссертация), Ленинградский государственный электротехнический университет
• Байков Владимир Д.; Смолов, Владимир Б. (1975). Аппаратная реализация элементарных функций в CVM Аппаратурная реализация элементарных функций в ЦВМ [Аппаратная реализация элементарных функций в ЭВМ]. Ленинградский государственный университет. Архивировано из оригинала 02.03.2019. Дата обращения 02.03.2019.
• Байков Владимир Д.; Сельютин, С. А. (1982). Вычисление элементарных функций в ЭКВМ [Вычисление элементарных функций в микрокалькуляторах]. Москва: Радио и связь.
• Байков Владимир Д.; Смолов, Владимир Б. (1985). Специализированные процессоры: итерационные алгоритмы и структуры [Специализированные процессоры: итерационные алгоритмы и структуры]. Москва: Радио и связь.
• Томас Коппенс, изд. (Январь 1980 г.). «Константы CORDIC в ПЗУ TI 58/59». Информационный бюллетень по обмену программным обеспечением Texas Instruments. Капеллен, Бельгия: TISOFT. 2 (2).
• Коппенс, Томас, изд. (Апрель 1980 г.). «Схема вычисления натурального логарифма / Электронная схема вычисления / ⁄ x схема вычисления». Информационный бюллетень по обмену программным обеспечением Texas Instruments. Капеллен, Бельгия: TISOFT. 2(3).(о CORDIC в TI-58 / TI-59 )
• TI Graphic Products Team (1995) [1993]. «Алгоритмы трансцендентных функций». Даллас, Техас, США: Texas Instruments, Consumer Products. Архивировано из оригинала 17 марта 2016 года. Дата обращения 2019 -03-02.
• Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik (на немецком языке) (1-е изд.). Берлин, Германия: VEB Verlag Technik. Pp. 219, 261, 271–296. ISBN 3341005153. EAN 9783341005156. MPN 5539165. Лицензия 201.370 / 4 / 89. Проверено 01.12.2015.
• Фрэкинг, Марвин Э. (1994). Цифровая обработка сигналов в системах связи (1-е изд.).
• Кантабутра, Витит (1996). «Об оборудовании для вычисления экспоненциальных и тригонометрические функции ». Транзакции IEEE на компьютерах. 45(3): 328–339. doi : 10.1109 / 12.485571.
• Банерджи, Аян (2001). [_ob = ArticleURL _udi = B6V0X-4313PR1-1 "Реализация FPGA Процессор БПФ на базе CORDIC для обработки биомедицинских сигналов "] Проверьте значение | url =(). Микропроцессоры и микросистемы. Харагпур, Западная Бенгалия, Индия. 25 (3): 131–142. doi : 10.1016 / S0141-9331 (01) 00106-5.
• Кахан, Уильям Мортон (2002-05-20). «Алгоритмы псевдоделения для логарифмов с плавающей запятой и экспонент» (PDF). Беркли, Калифорния, США: Калифорнийский университет. Архивировано из оригинального (PDF) 25 декабря 2015 года. Проверено 15 января 2016 г.
• Кокрам, Крис К. (осень 2008 г.). «Реализация алгоритма CORDIC в цифровом понижающем преобразователе» (PDF).
• Лакшми, Боппана; Дхар, Аниндья Сундар (06.10.2009). «Архитектура CORDIC: обзор». Проектирование СБИС. Харагпур, Западная Бенгалия, Индия: Департамент электроники и электротехники, Индийский технологический институт (опубликовано 10 октября 2010 г.). 2010 : 1–19. DOI : 10.1155 / 2010/794891. 794891.
• Савард, Джон Дж. Г. (2018) [2006]. "Продвинутые арифметические методы". квадиблок. Архивировано из оригинала на 2018-07-03. Проверено 16 июля 2018 г.

• Ван, Шаоюнь (июль 2011 г.), Библиографический сайт CORDIC
• Soft CORDIC IP (код Verilog HDL)
• Библиографический сайт CORDIC
• BASIC Штамп, математическая реализация CORDIC
• реализация CORDIC в verilog
• CORDIC векторизация с произвольным целевым значением
• PicBasic Pro, Pic18 математическая реализация CORDIC
• реализация Python CORDIC
• Простой код C для фиксированной точки CORDIC
• Учебное пособие и реализация MATLAB - Использование CORDIC для оценки фазы сложного числа
• Описание аппаратных CORDIC в Arx с тестовыми программами на C ++ и VHDL
• Введение в алгоритм CORDIC
• Реализация алгоритма CORDIC в цифровом формате Понижающий преобразователь
• 50-я годовщина алгоритма CORDIC
• Реализация алгоритма CORDIC: C-код с фиксированной точкой для тригонометрических и гиперболических функций, C-код для тестирования и проверки производительности