КОРДИК - CORDIC

«Псевдо-деление» перенаправляется сюда. Для полиномиального псевдоделения см. Псевдо-остаток.

КОРДИК (за COордината рответ DIгиталь Cкомпьютер), также известный как Алгоритм Волдера, включая Циркуляр CORDIC (Джек Э. Волдер),^[1][2] Линейный CORDIC, Гиперболический КОРДИК (Джон Стивен Вальтер),^[3][4] и Обобщенный гиперболический кордик (GH CORDIC) (Yuanyong Luo et al.), ^[5][6] простой и эффективный алгоритм вычислять тригонометрические функции, гиперболические функции, квадратные корни, умножения, подразделения, и экспоненты и логарифмы с произвольной базой, обычно сходящейся с одной цифрой (или битом) на итерацию. Таким образом, CORDIC также является примером цифровые алгоритмы. CORDIC и близкие к нему методы, известные как псевдоумножение и псевдоделение или же фактор комбинирования обычно используются, когда нет аппаратный умножитель доступен (например, в простом микроконтроллеры и ПЛИС ), поскольку для этого требуются только операции дополнения, вычитания, битовый сдвиг и таблицы поиска. Таким образом, все они принадлежат к классу алгоритмы сдвига и сложения. В информатике CORDIC часто используется для реализации арифметика с плавающей запятой когда целевой платформе не хватает аппаратного обеспечения, умножьте количество по причинам стоимости или места.

История

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

CORDIC был задуман в 1956 году.^[10][11] к Джек Э. Волдер на аэроэлектроника Департамент Convair из-за необходимости заменить аналоговый преобразователь в Бомбардировщик В-58 Навигационный компьютер с более точным и производительным цифровым решением в реальном времени.^[11] Поэтому CORDIC иногда называют цифровой преобразователь.^[12][13]

В своем исследовании Волдер вдохновился формулой из издания 1946 г. CRC Справочник по химии и физике:^[11]

${\displaystyle {\begin{aligned}K_{n}R\sin(\theta \pm \varphi )&=R\sin(\theta )\pm 2^{-n}R\cos(\theta ),\\K_{n}R\cos(\theta \pm \varphi )&=R\cos(\theta )\mp 2^{-n}R\sin(\theta ),\\\end{aligned}}}$

с ${\displaystyle K_{n}={\sqrt {1+2^{-2n}}}}$, ${\displaystyle \tan(\varphi )=2^{-n}}$.

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

В 1958 году Convair наконец приступила к созданию демонстрационной системы для решения исправление радара -принятие задач по имени CORDIC I, завершенный в 1960 году без Волдера, который уже покинул компанию.^[1][11] Более универсальный КОРДИК II модели А (стационарный) и B (бортовые) были построены и испытаны Даггеттом и Гарри Шуссом в 1962 году.^[11][15]

Алгоритм Волдера CORDIC был впервые опубликован в 1959 году.^{[1][2][11][13][16]} что привело к его встраиванию в навигационные компьютеры компаниями, включая Мартин-Орландо, Компьютерное управление, Litton, Kearfott, Лир-Зиглер, Сперри, Raytheon, и Коллинз Радио.^[11]

Волдер объединился с Малкольмом Макмилланом, чтобы построить Афина, а фиксированная точка настольный калькулятор используя его двоичный алгоритм CORDIC.^[17] Дизайн был представлен Hewlett Packard в июне 1965 г., но не принят.^[17] Тем не менее, Макмиллан представил Дэвид С. Кокран (HP) к алгоритму Волдера, и когда Кокран позже встретил Волдера, он направил его к аналогичному подходу. Джон Э. Меггитт (IBM^[18]) предложил как псевдоумножение и псевдоделение в 1961 г.^[18][19] Метод Меггитта также предлагал использовать основание 10.^[18] скорее, чем база 2, который до сих пор использовался Volder's CORDIC. Эти усилия привели к ROMable логическая реализация прототипа десятичной машины CORDIC внутри Hewlett-Packard в 1966 году,^[20][19] построены и концептуально выведены из Томас Э. Осборн прототип Зеленая машина, четырехфункциональный, плавающая точка настольный калькулятор он закончил в DTL логика^[17] в декабре 1964 г.^[21] Результатом этого проекта стала публичная демонстрация первого настольного калькулятора Hewlett-Packard с научными функциями. hp 9100A в марте 1968 года, а серийное производство началось в том же году.^{[17][21][22][23]}

Когда Ван Лаборатории обнаружил, что hp 9100A использовал подобный подход к фактор комбинирования метод в их более ранних LOCI-1^[24] (Сентябрь 1964 г.) и LOCI-2 (Январь 1965 г.)^[25][26] Логарифмический вычислительный прибор настольные калькуляторы,^[27] они безуспешно обвинили Hewlett-Packard в нарушении одного из Ан Ван патентов в 1968 году.^{[19][28][29][30]}

Джон Стивен Вальтер в Hewlett-Packard обобщили алгоритм в Единый CORDIC алгоритм в 1971 году, позволяющий вычислить гиперболические функции, натуральные экспоненты, натуральные логарифмы, умножения, подразделения, и квадратные корни.^{[31][3][4][32]} КОРДИК подпрограммы для тригонометрических и гиперболических функций могли бы разделять большую часть своего кода.^[28] Это развитие привело к появлению первых научный портативный калькулятор, то HP-35 в 1972 г.^{[28][33][34][35][36][37]} На основе гиперболического CORDIC, Юаньонг Луо и другие. далее предложил обобщенный гиперболический CORDIC (GH CORDIC) для прямого вычисления логарифмов и экспонент с произвольным фиксированным основанием в 2019 году.^{[5][6][38][39][40]} Теоретически Hyperbolic CORDIC является частным случаем GH CORDIC.^[5]

Первоначально CORDIC был реализован только с использованием двоичная система счисления и несмотря на то, что Меггитт предлагал использовать десятичную систему для своего подхода псевдоумножения, десятичная система CORDIC оставалась в основном неслыханной еще несколько лет, так что Герман Шмид и Энтони Богацки все еще предлагал это в качестве новинки еще в 1973 году.^{[16][13][41][42][43]} и только позже выяснилось, что Hewlett-Packard реализовала это уже в 1966 году.^{[11][13][20][28]}

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

CORDIC был реализован в На базе ARM STM32G4, Intel 8087,^{[43][44][45][46][47]} 80287,^[47][48] 80387^[47][48] вверх к 80486^[43] сопроцессора, а также в Motorola 68881^[43][44] и 68882 для некоторых видов команд с плавающей запятой, в основном как способ уменьшить количество вентилей (и сложность) FPU подсистема.

Приложения

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

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

Алгоритм использовался в навигационной системе Программа Аполлон с Лунный вездеход вычислить несущий и дальность, или расстояние от Лунный модуль.^{[51]:14[52]:17} CORDIC использовался для реализации Intel 8087 математический сопроцессор в 1980 году, что избавляет от необходимости реализовывать аппаратное умножение.^[53]

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

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

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

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

Режимы работы

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

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

${\displaystyle v_{0}={\begin{bmatrix}1\\0\end{bmatrix}}.}$

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

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

Более формально, каждая итерация вычисляет поворот, который выполняется путем умножения вектора ${\displaystyle v_{i-1}}$ с матрица вращения ${\displaystyle R_{i}}$:

${\displaystyle v_{i}=R_{i}v_{i-1}.}$

Матрица вращения определяется выражением

${\displaystyle R_{i}={\begin{bmatrix}\cos(\gamma _{i})&-\sin(\gamma _{i})\\\sin(\gamma _{i})&\cos(\gamma _{i})\end{bmatrix}}.}$

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

${\displaystyle {\begin{aligned}\cos(\gamma _{i})&={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})}}},\\\sin(\gamma _{i})&={\frac {\tan(\gamma _{i})}{\sqrt {1+\tan ^{2}(\gamma _{i})}}},\end{aligned}}}$

матрица вращения становится

${\displaystyle R_{i}={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})}}}{\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}.}$

Выражение для повернутого вектора ${\displaystyle v_{i}=R_{i}v_{i-1}}$ затем становится

${\displaystyle v_{i}={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})}}}{\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}{\begin{bmatrix}x_{i-1}\\y_{i-1}\end{bmatrix}},}$

куда ${\displaystyle x_{i-1}}$ и ${\displaystyle y_{i-1}}$ компоненты ${\displaystyle v_{i-1}}$. Ограничение углов ${\displaystyle \gamma _{i}}$ такой, что ${\displaystyle \tan(\gamma _{i})=\pm 2^{-i}}$, умножение на касательную можно заменить делением на степень двойки, что эффективно выполняется в аппаратном обеспечении цифрового компьютера с использованием битовый сдвиг. Затем выражение становится

${\displaystyle v_{i}=K_{i}{\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix}}{\begin{bmatrix}x_{i-1}\\y_{i-1}\end{bmatrix}},}$

куда

${\displaystyle K_{i}={\frac {1}{\sqrt {1+2^{-2i}}}},}$

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

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

${\displaystyle K(n)=\prod _{i=0}^{n-1}K_{i}=\prod _{i=0}^{n-1}{\frac {1}{\sqrt {1+2^{-2i}}}},}$

который вычисляется заранее и сохраняется в таблице или как единственная константа, если количество итераций фиксировано. Эту поправку также можно внести заранее, масштабируя ${\displaystyle v_{0}}$ и, следовательно, сохранение умножения. Дополнительно можно отметить, что^[43]

${\displaystyle K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694}$

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

${\displaystyle A={\frac {1}{K}}=\lim _{n\to \infty }\prod _{i=0}^{n-1}{\sqrt {1+2^{-2i}}}\approx 1.64676025812107.}$

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

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

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

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

Как видно на рисунке выше, синус угла ${\displaystyle \beta }$ это у координата конечного вектора ${\displaystyle v_{n},}$ в то время как Икс координата - значение косинуса.

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

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

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

Выполнение

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

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

функцияv =сердечный(бета, n)% Эта функция вычисляет v = [cos (beta), sin (beta)] (beta в радианах)% с использованием n итераций. Увеличение n увеличит точность.если бета <-pi / 2 || бета> пи / 2    если бета <0        v = сердечный(бета + число Пи, п);    ещеv = сердцевина (бета - пи, п);    конецv = -v; % переверните знак для второго или третьего квадранта    возвращатьсяконец% Инициализация таблиц констант, используемых CORDIC% нужна таблица арктангенсов отрицательных степеней двойки в радианах:% angles = atan (2. ^ - (0:27));углы =  [  ...    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 ];% и таблица произведений обратных длин векторов [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(мин(п, длина(Kvalues)));% Инициализировать переменные цикла:v = [1;0]; % начать с 2-вектора косинуса и синуса нуляpoweroftwo = 1;угол = углы(1);% Итерацийза j = 0:п-1;    если бета <0        сигма = -1;    ещесигма = 1;    конецкоэффициент = сигма * мощность два;    % Обратите внимание, что умножение матриц может быть выполнено с использованием масштабирования по степеням двойки и сложения вычитания.    р = [1, -фактор; фактор, 1];    v = р * v; Умножение матрицы% 2 на 2    бета = бета - сигма * угол; % обновить оставшийся угол    poweroftwo = poweroftwo / 2;    % обновить угол из таблицы или, в конечном итоге, просто разделив на два    если j + 2> длина (углы)        угол = угол / 2;    ещеугол = углы (j + 2);    конецконец% Задайте длину выходного вектора [cos (beta), sin (beta)]:v = v * Kn;возвращатьсяконечная функция

Два на два матричное умножение может осуществляться парой простых сдвигов и сложений.

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

В Java класс Math имеет скальб (двойной x, int масштаб) способ выполнения такой смены,^[55] C имеет ldexp функция^[56] а процессоры класса x86 имеют fscale операция с плавающей запятой.^[57]

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

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

Связанные алгоритмы

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

Смотрите также

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

Рекомендации

1. Волдер, Джек Э. (1959-03-03). "Вычислительная техника CORDIC" (PDF). Труды Западной совместной компьютерной конференции (WJCC) (презентация). Сан-Франциско, Калифорния, США: Национальный объединенный компьютерный комитет (NJCC): 257–261. Получено 2016-01-02.
2. Волдер, Джек Э. (1959-05-25). «Тригонометрическая вычислительная техника CORDIC» (PDF). Операции IRE на электронных компьютерах. Институт Радиоинженеров, Inc. (IRE) (опубликовано в сентябре 1959 г.). 8 (3): 330–334 (перепечатка: 226–230). ИС-8 (3): 330–334. Получено 2016-01-01.
3. Вальтер, Джон Стивен (май 1971 г.). Написано в Пало-Альто, Калифорния, США. «Единый алгоритм элементарных функций» (PDF). Материалы весенней совместной компьютерной конференции. Атлантик-Сити, Нью-Джерси, США: Компания Hewlett-Packard. 38: 379–385 - через Американская федерация обществ обработки информации (AFIPS).
4. Вальтер, Джон Стивен (июнь 2000 г.). "История единого КОРДИК". Журнал обработки сигналов СБИС. Хингем, Массачусетс, США: Kluwer Academic Publishers. 25 (2): 107–112. Дои:10.1023 / А: 1008162721424. ISSN  0922-5773. S2CID  26922158.
5. Ло, Юаньонг; Ван, Юйсюань; Ха, Яджун; Ван, Чжунфэн; Чен, Сиюань; Пан, Хунбин (сентябрь 2019 г.). «Обобщенный гиперболический CORDIC и его логарифмические и экспоненциальные вычисления с произвольной фиксированной базой». Транзакции IEEE в системах с очень крупномасштабной интеграцией (СБИС). 27 (9): 2156–2169. Дои:10.1109 / TVLSI.2019.2919557. S2CID  196171166.
6. Ло, Юаньюн; Ван, Юйсюань; Ха, Яджун; Ван, Чжунфэн; Чен, Сиюань; Пан, Хунбин (сентябрь 2019 г.). «Поправки к» обобщенному гиперболическому CORDIC и его логарифмическому и экспоненциальному вычислению с произвольной фиксированной базой"". Транзакции IEEE в системах с очень крупномасштабной интеграцией (СБИС). 27 (9): 2222. Дои:10.1109 / TVLSI.2019.2932174.
7. Бриггс, Генри (1624). Arithmetica Logarithmica. Лондон. (Перевод: [1] В архиве 4 марта 2016 г. Wayback Machine )
8. Лапорт, Жак (2014) [2005]. "Генри Бриггс и HP 35". Париж, Франция. Архивировано из оригинал на 2015-03-09. Получено 2016-01-02. [2]
9. Цветок, Роберт (1771). Радикс. Новый способ создания логарифмов. Лондон: Дж. Бикрофт. Получено 2016-01-02.
10. Волдер, Джек Э. (1956-06-15), Алгоритмы двоичных вычислений для вращения координат и генерации функций (внутренний отчет), Convair, Группа Аэроэлектроника, ИАР-1.148
11. Волдер, Джек Э. (июнь 2000 г.). «Рождение КОРДИК» (PDF). Журнал обработки сигналов СБИС. Хингем, Массачусетс, США: Kluwer Academic Publishers. 25 (2): 101–105. Дои:10.1023 / А: 1008110704586. ISSN  0922-5773. S2CID  112881. Архивировано из оригинал (PDF) на 2016-03-04. Получено 2016-01-02.
12. Перл, Майкл Д. (июнь 1971 г.), «Техника CORDIC уменьшает поиск тригонометрических функций», Компьютерный дизайн, Бостон, Массачусетс, США: Computer Design Publishing Corp .: 72–78. (NB. Некоторые источники ошибочно называют это П. З. Перле или в Компонентный дизайн.)
13. Шмид, Герман (1983) [1974]. Десятичное вычисление (1 (переиздание) изд.). Малабар, Флорида, США: Издательство Роберта Кригера. С. 162, 165–176, 181–193. ISBN  0-89874-318-4. Получено 2016-01-03. (NB. По крайней мере, некоторые партии этого переизданного издания были опечатки с дефектными страницами 115–146.)
14. Даггетт, Дэн Х. (сентябрь 1959 г.). «Десятично-двоичные преобразования в CORDIC». Операции IRE на электронных компьютерах. Институт Радиоинженеров, Inc. (IRE). 8 (3): 335–339. Дои:10.1109 / TEC.1959.5222694. ISSN  0367-9950. ИС-8 (3): 335–339. Получено 2016-01-02.
15. Advanced Systems Group (1962-08-06), Техническое описание крепежного врезного оборудования (отчет), Форт-Уэрт, Техас, США: Общая динамика, FZE-052
16. Шмид, Герман (1974). Десятичное вычисление (1-е изд.). Бингемтон, Нью-Йорк, США: John Wiley & Sons, Inc. стр.162, 165–176, 181–193. ISBN  0-471-76180-X. Получено 2016-01-03. До сих пор было известно, что CORDIC реализован только в двоичной форме.Но, как будет продемонстрировано здесь, алгоритм может быть легко модифицирован для десятичной системы счисления. * […] * Между тем было выяснено, что Hewlett Packard и другие производители калькуляторов используют десятичные методы CORDIC в своих научных калькуляторах.
17. Лейбсон, Стивен (2010). «Проект HP 9100: экзотермическая реакция». Получено 2016-01-02.
18. Меггитт, Джон Э. (1961-08-29). «Псевдоделение и процессы псевдоумножения» (PDF). Журнал исследований и разработок IBM. Ривертон, Нью-Джерси, США: Корпорация IBM (опубликовано в апреле 1962 г.). 6 (2): 210–226, 287. Дои:10.1147 / rd.62.0210. Получено 2016-01-09. Джон Э. Меггитт Б.А., 1953 год; Кандидат медицинских наук, 1958 г. Кембриджский университет. Награжден первым Премия Смита в Кембридже в 1955 г. и избрал научную стипендию Эммануэль Колледж. […] Присоединился Британская лаборатория IBM в Хёрсли, Винчестер в 1958 г. коды с исправлением ошибок и небольшие микропрограммные компьютеры. ([3], [4] )
19. Кокран, Дэвид С. (19 ноября 2010 г.). «Четверть века в HP» (машинопись интервью). Музей истории компьютеров Воспоминания HP. 7: Научные калькуляторы, около 1966 года. CHM X5992.2011. Получено 2016-01-02. Я даже прилетел в Южную Калифорнию, чтобы поговорить с Джеком Волдером, который реализовал трансцендентные функции в Афина машина и общались с ним около часа. Он направил меня к оригинальным статьям Меггитта, в которых он получил псевдоделение, обобщенные функции псевдоумножения. […] Я провел довольно много литературных исследований, что привело к очень интересным открытиям. […] Я нашел трактат 1624 г. Генри Бриггс обсуждая вычисление десятичных логарифмов, интересно использовать тот же метод псевдоделения / псевдоумножения, который Макмиллан и Волдер использовали в Афина. […] Мы приобрели LOCI-2 из Ван Лабс и признал, что Wang Labs LOCI II использовал тот же алгоритм делать квадратный корень, а также логарифмически и экспоненциально. После введения 9100 наш юридический отдел получил письмо от Вана о том, что мы нарушили их патент. И я только что отправил записку со ссылкой на Бриггса на латыни, в которой говорилось: "Похоже, предшествующий уровень техники мне. "Мы никогда не слышали ни слова. ([5] )
20. Кокран, Дэвид С. (1966-03-14). «Об использовании CORDIC для вычисления трансцендентных функций в BCD» (личное сообщение с Джеком Э. Волдером).
21. Осборн, Томас Э. (2010) [1994]. "История Тома Осборна его собственными словами". Получено 2016-01-01.
22. Лейбсон, Стивен (2010). «HP 9100: первое путешествие». Получено 2016-01-02.
23. Кокран, Дэвид С. (сентябрь 1968 г.). «Внутреннее программирование вычислителя 9100A». Журнал Hewlett-Packard. Пало-Альто, Калифорния, США: Hewlett Packard: 14–16. Получено 2016-01-02. ([6] )
24. Расширьте свои персональные вычислительные мощности с помощью нового логарифмического вычислительного прибора LOCI-1, Wang Laboratories, Inc., 1964, с. 2–3, получено 2016-01-03
25. Бенсен, Рик (31 августа 2013 г.) [1997]. "Ван ЛОКИ-2". Старый веб-музей калькулятора. Биверкрик, Орегон-Сити, Орегон, США. Получено 2016-01-03.
26. "Руководство по обслуживанию Wang LOCI" (PDF). Wang Laboratories, Inc. 1967. L55-67. Получено 2018-09-14.
27. Бенсен, Рик (2004-10-23) [1997]. "Система калькулятора Wang Model 360SE". Старый веб-музей калькулятора. Биверкрик, Орегон-Сити, Орегон, США. Получено 2016-01-03.
28. Кокран, Дэвид С. (июнь 2010 г.). «Конструкция HP-35: пример инноваций». Проект памяти HP. Получено 2016-01-02. Во время разработки рабочего стола HP 9100 калькулятор. Я отвечал за разработку алгоритмов, соответствующих архитектуре, предложенной Томом Осборном. Хотя предложенная методология алгоритмов была предложена Малкольмом Макмилланом, я много читал, чтобы понять основные вычисления […] Хотя Ван Лаборатории использовали аналогичные методы расчета, мое исследование показало предшествующий уровень техники датированные 1624 годом, которые читали на их патентах. […] Это исследование позволило адаптировать трансцендентные функции за счет использования алгоритмов для соответствия потребностям клиента в рамках ограничений оборудования. Это оказалось неоценимым во время разработки HP-35, […] Силовая серия, полиномиальные разложения, непрерывные дроби, и Полиномы Чебышева все считались трансцендентными. Все они были слишком медленными из-за количества требуемых умножений и делений. Обобщенный алгоритм, который наилучшим образом соответствовал требованиям скорости и эффективности программирования для HP-35, представлял собой итеративный метод псевдоделения и псевдоумножения, впервые описанный в 1624 г. Генри Бриггс в 'Arithmetica Logarithmica ', а затем Волдером и Меггиттом. Это тот же тип алгоритма, который использовался в предыдущих настольных калькуляторах HP. […] Сложность алгоритмов сделала необходимым многоуровневое программирование. Это означало, что калькулятор должен обладать функцией подпрограмм, […] Для генерации трансцендентной функции, такой как Arc-Hyperbolic-Tan, требовалось несколько уровней подпрограмм. […] Крис Клэр позже задокументировал это как Алгоритмический конечный автомат (ASM) методология. Даже простой синус или косинус использовали процедуру касания, а затем вычисляли синус из тригонометрических тождеств. Эти трудные манипуляции были необходимы для минимизации количества уникальных программ и программных шагов […] Набор арифметических инструкций был разработан специально для калькулятора десятичных трансцендентных функций. Основные арифметические операции выполняются 10-е дополнение сумматор-вычитатель, у которого есть пути данных к трем регистрам, которые используются в качестве рабочего хранилища.
29. Патент США 3402285A, Ван, Ан, "Счетный аппарат", опубликовано 1968-09-17, выдано 1968-09-17, закреплено за Ван Лаборатории  ([7], [8] )
30. Патент DE 1499281B1, Ван, Ан, "Rechenmaschine fuer logarithmische Rechnungen", опубликовано 1970-05-06, выпущено 1970-05-06, назначено Ван Лаборатории  ([9] )
31. Шварцлендер младший, Эрл Э. (1990). Компьютерная арифметика. 1 (2-е изд.). Лос-Аламитос: Пресса IEEE Computer Society. ISBN  9780818689314. 0818689315. Получено 2016-01-02.
32. Петрочелли, Орландо Р., изд. (1972), Лучшие компьютерные статьи 1971 года, Издательство Auerbach, п. 71, ISBN  0877691274, получено 2016-01-02
33. Кокран, Дэвид С. (июнь 1972 г.). «Алгоритмы и точность в HP-35» (PDF). Журнал Hewlett-Packard. 23 (10): 10–11.
34. Ляпорт, Жак (2005-12-06). «Тригонометрический алгоритм HP35». Париж, Франция. Архивировано из оригинал на 2015-03-09. Получено 2016-01-02. [10]
35. Лапорт, Жак (февраль 2005 г.) [1981]. «Секрет алгоритмов». L'Ordinateur Индивидуальный. Париж, Франция (24). Архивировано из оригинал на 18.08.2016. Получено 2016-01-02. [11]
36. Лапорт, Жак (февраль 2012 г.) [2006]. «Цифровые методы». Париж, Франция. Архивировано из оригинал на 18.08.2016. Получено 2016-01-02. [12]
37. Лапорт, Жак (февраль 2012 г.) [2007]. «Алгоритм логарифмирования HP 35». Париж, Франция. Архивировано из оригинал на 18.08.2016. Получено 2016-01-07. [13]
38. Ван, Юйсюань; Ло, Юаньюн; Ван, Чжунфэн; Шэнь, Цинхун; Пан, Хунбин (январь 2020 г.). «Архитектура на основе GH CORDIC для вычисления корня N для чисел с плавающей запятой одинарной точности». Транзакции IEEE в системах с очень крупномасштабной интеграцией (СБИС). 28 (4): 864–875. Дои:10.1109 / TVLSI.2019.2959847. S2CID  212975618.
39. Мопури, Суреш; Ачарья, Амит (сентябрь 2019 г.). "Методология проектирования общей архитектуры СБИС низкой сложности для вычислений N-го корня и N-го уровня". IEEE Transactions on Circuits and Systems I: Regular Papers. 66 (12): 4673–4686. Дои:10.1109 / TCSI.2019.2939720. S2CID  203992880.
40. Вачани, Лина (ноябрь 2019 г.). «CORDIC как переключаемая нелинейная система». Схемы, системы и обработка сигналов. 39 (6): 3234–3249. Дои:10.1007 / s00034-019-01295-8. S2CID  209904108.
41. Шмид, Герман; Богацки, Энтони (1973-02-20). «Используйте Decimal CORDIC для генерации многих трансцендентных функций». EDN: 64–73.
42. Франке, Ричард (1973-05-08). Анализ алгоритмов аппаратной оценки элементарных функций (PDF). Монтерей, Калифорния, США: Департамент военно-морского флота, Военно-морская аспирантура. NPS-53FE73051A. Получено 2016-01-03.
43. Мюллер, Жан-Мишель (2006). Элементарные функции: алгоритмы и реализация (2-е изд.). Бостон: Биркхойзер. п. 134. ISBN  978-0-8176-4372-0. LCCN  2005048094. Получено 2015-12-01.
44. Неф, Рафи (март 1983). «Реализация трансцендентных функций на числовом процессоре». Микропроцессоры и микропрограммирование. 11 (3–4): 221–225. Дои:10.1016/0165-6074(83)90151-5.
45. Палмер, Джон Ф .; Морс, Стивен Пол (1984). Праймер 8087 (1-е изд.). John Wiley & Sons Australia, Limited. ISBN  0471875694. 9780471875697. Получено 2016-01-02.
46. Гласс, Л. Брент (январь 1990 г.). «Математические сопроцессоры: посмотрите, что они делают и как они это делают». Байт. 15 (1): 337–348. ISSN  0360-5280.
47. Джарвис, Питтс (1990-10-01). «Реализация алгоритмов CORDIC - единая компактная процедура для вычисления трансцендентных функций». Журнал доктора Добба: 152–156. Архивировано из оригинал на 2016-03-04. Получено 2016-01-02.
48. Юэн, А. К. (1988). «Процессоры Intel с плавающей точкой». Запись конференции Electro / 88: 48/5/1–7.
49. Мехер, Прамод Кумар; Валлс, Хавьер; Хуанг, Цо-Бин; Sridharan, K .; Махаратна, Кушик (22 августа 2008 г.). «50 лет CORDIC: алгоритмы, архитектуры и приложения» (PDF). IEEE Transactions on Circuits and Systems I: Regular Papers (опубликовано 09.09.2009). 56 (9): 1893–1907. Дои:10.1109 / TCSI.2009.2025803. S2CID  5465045.
50. Мехер, Прамод Кумар; Пак, Сан Юн (февраль 2013 г.). "Методология проектирования общей архитектуры СБИС низкой сложности для вычислений N-го корня и N-го уровня". Транзакции IEEE в системах с очень крупномасштабной интеграцией (СБИС). 21 (2): 217–228. Дои:10.1109 / TVLSI.2012.2187080. S2CID  7059383.
51. Heffron, W.G .; ЛаПиана, Ф. (1970-12-11). «Технический меморандум 70-2014-8: Система навигации лунного вездехода» (PDF). НАСА. Вашингтон, округ Колумбия.: Bellcomm.
52. Смит, Эрнест С .; Мастин, Уильям К. (ноябрь 1973 г.). «Техническая нота D-7469: Обзор характеристик системы навигации лунного вездехода» (PDF). НАСА. Хантсвилл, Алабама: Центр космических полетов Маршалла.
53. Ширрифф, Кен (май 2020 г.). «Извлечение констант ПЗУ из матрицы математического сопроцессора 8087». righto.com. Самостоятельно опубликовано Кеном Ширриффом. Получено 2020-09-03. ПЗУ содержит 16 значений арктангенса, арктанов 2^-n. Он также содержит 14 значений журнала, логарифм по основанию 2 из (1 + 2^-n). Эти значения могут показаться необычными, но они используются в эффективном алгоритме CORDIC, который был изобретен в 1958 году.
54. Андрака, Рэй (1998). «Обзор алгоритмов CORDIC для компьютеров на базе ПЛИС» (PDF). ACM. Норт Кингстаун, Род-Айленд, США: Andraka Consulting Group, Inc. 0-89791-978-5 / 98/01. Получено 2016-05-08.
55. «Класс по математике». Стандарт платформы Java (8-е изд.). Корпорация Oracle. 2018 [1993]. В архиве из оригинала на 2018-08-06. Получено 2018-08-06.
56. "ldexp, ldexpf, ldexpl". cppreference.com. 2015-06-11. В архиве из оригинала на 2018-08-06. Получено 2018-08-06.
57. «Раздел 8.3.9 Логарифмические, экспоненциальные и масштабные». Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32 Том 1: Базовая архитектура (PDF). Корпорация Intel. Сентябрь 2016. С. 8–22.

дальнейшее чтение

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

внешняя ссылка

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