КОРДИК

Тригонометрия
Контур История использование Функции  ( обратные ) Обобщенная тригонометрия
Справка
Идентичности Точные константы Столы Единичный круг
Законы и теоремы
Синусы Косинусы Касательные Котангенсы теорема Пифагора
Исчисление
Тригонометрическая замена Интегралы  ( обратные функции ) Производные
v т е

CORDIC (для СО ординаты R otation DI gital C omputer), также известный как алгоритм Volder в , или: Digit-по-цифры метода круговой CORDIC (Джек Е. Volder), ^{[1] [2]} Линейный CORDIC , гиперболического CORDIC (Джон Стивен Walther), ^{[3] [4]} и Generalized Hyperbolic CORDIC ( GH CORDIC ) (Yuanyong Luo et al.), ^{[5] [6]} - это простой и эффективный алгоритм для вычисления тригонометрических функций , гиперболических функций, квадратные корни , умножения , деления , экспоненты и логарифмы с произвольным основанием, обычно сходящиеся с одной цифрой (или битом) за итерацию. Таким образом, CORDIC также является примером алгоритмов, использующих цифру за цифрой . CORDIC и близкие к нему методы, известные как псевдоумножение и псевдоделение или комбинирование множителей , обычно используются, когда аппаратный умножитель недоступен (например, в простых микроконтроллерах и ПЛИС ), поскольку единственные операции, которые он требует, - это сложение , вычитание., битовые сдвиги и таблицы поиска . Таким образом, все они принадлежат к классу алгоритмов сдвига и сложения . В информатике CORDIC часто используется для реализации арифметики с плавающей запятой, когда на целевой платформе не хватает аппаратного умножения по причинам стоимости или места.

История [ править ]

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

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

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

${\ Displaystyle {\ begin {align} 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), \\\ конец {выровнено}}}$

с , .${\ displaystyle K_ {n} = {\ sqrt {1 + 2 ^ {- 2n}}}}$${\ Displaystyle \ загар (\ varphi) = 2 ^ {- п}}$

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

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

Алгоритм Волдера CORDIC был впервые публично описан в 1959 году ^{[1] [2] [11] [13] [16],} что привело к его внедрению в навигационные компьютеры такими компаниями, как Martin-Orlando , Computer Control , Litton , Kearfott , Lear. -Siegler , Sperry , Raytheon и Collins Radio . ^[11]

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

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

Джон Стивен Вальтер из Hewlett-Packard обобщил алгоритм в унифицированный алгоритм CORDIC в 1971 году, что позволило ему вычислять гиперболические функции , натуральные экспоненты , натуральные логарифмы , умножения , деления и квадратные корни . ^{[31] [3] [4] [32]} Подпрограммы CORDIC для тригонометрических и гиперболических функций могут использовать большую часть своего кода. ^[28] Такое развитие событий привело к первой научной карманном калькуляторе , то HP-35 в 1972 г. ^{[28][33] [34] [35] [36] [37]} На основе гиперболического CORDIC, Yuanyong Luo et al. далее предложил обобщенный гиперболический CORDIC (GH CORDIC) для прямого вычисления логарифмов и экспонент с произвольным фиксированным основанием в 2019 году. ^{[5] [6] [38] [39] [40]} Теоретически гиперболический 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 был реализован в процессорах STM32G4 на базе ARM , Intel 8087 , ^{[43] [44] [45] [46] [47]} 80287 , ^{[47] [48]} 80387 ^{[47] [48]} до 80486 ^{[43] ],} а также в Motorola 68881 ^{[43] [44]} и 68882 для некоторых видов команд с плавающей запятой, в основном как способ уменьшить количество вентилей (и сложность) подсистемы FPU .

Приложения [ править ]

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

Оборудование [ править ]

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

CORDIC обычно работает быстрее, чем другие подходы, когда аппаратный умножитель недоступен (например, микроконтроллер) или когда количество вентилей, необходимых для реализации поддерживаемых им функций, должно быть минимизировано (например, в FPGA или ASIC ). Фактически, CORDIC является стандартным подключаемым IP-адресом в приложениях разработки FPGA, таких как Vivado для Xilinx, в то время как реализация Power Series не связана со спецификой такого IP-адреса, т.е. CORDIC может вычислять множество различных функций (общего назначения), в то время как Аппаратный умножитель, сконфигурированный для выполнения реализаций степенного ряда, может вычислять только ту функцию, для которой он был разработан.

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

В STM32G4 серия и некоторые STM32H7 серии микроконтроллеров реализовать CORDIC модуль для ускорения вычислений в различных смешанных сигналах приложениях , такие как графики для человеко - машинного интерфейса и полевого ориентированного управление двигателями. Хотя CORDIC не так быстр, как приближение степенного ряда, он действительно быстрее, чем реализации на основе интерполяции таблиц, такие как те, которые предоставляются стандартными библиотеками ARM CMSIS и C. ^[54]Хотя результаты могут быть немного менее точными, поскольку предоставленные модули CORDIC достигают только 20-битной точности в результате. Например, большая часть разницы в производительности по сравнению с реализацией ARM связана с накладными расходами алгоритма интерполяции, который обеспечивает полную точность с плавающей запятой (24 бита) и, вероятно, может достичь относительной ошибки с этой точностью. ^[55] Еще одним преимуществом является то, что модуль CORDIC является сопроцессором и может выполняться параллельно с другими задачами ЦП.

Проблема с использованием степенных рядов заключается в том, что, хотя они и дают небольшую абсолютную ошибку, они не демонстрируют корректную относительную ошибку. ^[56]

Программное обеспечение [ править ]

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

Режимы работы [ править ]

Режим вращения [ править ]

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

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

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

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

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

Матрица вращения задается формулой

${\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+1}=R_{i}v_{i}}$

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

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

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

где

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

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

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

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

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

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

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

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

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

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

${\displaystyle \beta _{0}=\beta }$

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

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

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

Режим векторизации [ править ]

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

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

Реализация [ править ]

Пример программного обеспечения [ править ]

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

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

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

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

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

Пример оборудования [ править ]

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

Двойные итерации CORDIC [ править ]

В публикациях: http://baykov.de/CORDIC1972.htm и http://baykov.de/CORDIC1975.htm предлагалось использовать метод двойных итераций для реализации функций: arcsinX, arccosX, lnX, expX , а также для вычисления гиперболических функций. Метод двойных итераций заключается в том, что в отличие от классического метода CORDIC, где значение шага итерации изменяется КАЖДЫЙ раз, т.е. на каждой итерации, в методе двойной итерации значение шага итерации повторяется дважды и изменяется только через одну итерацию. Отсюда и появилось обозначение индикатора степени для двойных итераций: i = 1,1,2,2,3,3 ... Тогда как при обычных итерациях: i = 1,2,3 ... Метод двойной итерации гарантирует сходимость метода во всем допустимом диапазоне изменений аргумента.

Обобщение задач сходимости CORDIC для произвольной позиционной системы счисления http://baykov.de/CORDIC1985.htm с Radix R показали, что для функций sin, cos, arctg достаточно выполнить (R-1) итераций для каждого значения i (i = 0 или от 1 до n, где n - количество цифр), т.е. для каждой цифры результата. Для функций ln, exp, sh, ch, arth, R итерации должны выполняться для каждого значения i. Для функций arcsin и arccos 2 (R-1) итерации должны выполняться для каждой цифры числа, т.е. для каждого значения i. Для функций arsh, arch количество итераций будет 2R для каждого i, то есть для каждой цифры результата.

Связанные алгоритмы [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Парини, Джозеф А. (1966-09-05). «DIVIC дает ответы на сложные навигационные вопросы». Электроника : 105–111. ISSN  0013-5070 .(NB. DIVIC расшифровывается как DIgital Variable Increments Computer . В некоторых источниках это ошибочно упоминается как JM Parini .)
• Андерсон, Стэнли Ф .; Эрл, Джон Дж .; Гольдшмидт, Роберт Эллиотт; Пауэрс, Дон М. (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 , Кокран, Дэвид С., «Цифровая калькуляторная система для вычисления квадратных корней», опубликован 04 мая 1971 г., выдан 04 мая 1971 г., переуступлен Hewlett-Packard Co.  ( [14] )
• Чен, Тянь Чи (июль 1972 г.). «Автоматическое вычисление экспонент, логарифмов, отношений и квадратного корня» (PDF) . Журнал исследований и разработок IBM . 16 (4): 380–388. DOI : 10.1147 / rd.164.0380 . ISSN  0018-8646 . Проверено 2 января 2016 .
• Эгберт, Уильям Э. (май 1977 г.). «Алгоритмы персонального калькулятора I: квадратные корни» (PDF) . Журнал Hewlett-Packard . Пало-Альто, Калифорния, США: Hewlett-Packard . 28 (9): 22–24 . Проверено 2 января 2016 .( [15] )
• Эгберт, Уильям Э. (июнь 1977 г.). «Алгоритмы персонального калькулятора II: тригонометрические функции» (PDF) . Журнал Hewlett-Packard . Пало-Альто, Калифорния, США: Hewlett-Packard . 28 (10): 17–20 . Проверено 2 января 2016 .( [16] )
• Эгберт, Уильям Э. (ноябрь 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). Аппаратурная реализация элементарных функций в ЦВМ Аппаратурная реализация элементарных функций в ЦВМ[ Аппаратная реализация элементарных функций в компьютерах ]. Ленинградский государственный университет. Архивировано 2 марта 2019 года . Проверено 2 марта 2019 .
• Байков Владимир Д .; Сельютин, С.А. (1982). Вычисление элементарных функций в ЭКВМ[ Оценка элементарных функций в микрокалькуляторах ]. Москва: Радио и связь (Радио и связь).
• Байков Владимир Д .; Смолов, Владимир Б. (1985).Специализированные процессоры: итерационные алгоритмы и структуры[ Специализированные процессоры: итерационные алгоритмы и структуры ]. Москва: Радио и связь (Радио и связь).
• Коппенс, Томас, изд. (Январь 1980 г.). «Константы CORDIC в ПЗУ TI 58/59». Информационный бюллетень по обмену программным обеспечением Texas Instruments . Капеллен, Бельгия: TISOFT. 2 (2).
• Коппенс, Томас, изд. (Апрель 1980 г.). «Натуральный логарифм схема вычисления / е ^х вычислительная схема / ¹ / _х вычислительная схема». Информационный бюллетень по обмену программным обеспечением Texas Instruments . Капеллен, Бельгия: TISOFT. 2 (3).(о CORDIC в TI-58 / TI-59 )
• TI Graphic Products Team (1995) [1993]. «Алгоритмы трансцендентных функций» . Даллас, Техас, США: Texas Instruments , Потребительские товары. Архивировано 17 марта 2016 года . Проверено 2 марта 2019 .
• Йорке, Гюнтер; Лампе, Бернхард; Венгель, Норберт (1989). Arithmetische Algorithmen der Mikrorechentechnik (на немецком языке) (1-е изд.). Берлин, Германия: VEB Verlag Technik . С. 219, 261, 271–296. ISBN 3341005153. EAN 9783341005156 . MPN 5539165. Лицензия 201.370 / 4/89 . Проверено 1 декабря 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 .
• Кахан, Уильям Мортон (20 мая 2002 г.). "Алгоритмы псевдоделения для логарифмов с плавающей запятой и экспонент" (PDF) . Беркли, Калифорния, США: Калифорнийский университет . Архивировано из оригинального (PDF) 25 декабря 2015 года . Проверено 15 января 2016 .
• Кокрам, Крис К. (осень 2008 г.). «Реализация алгоритма CORDIC в цифровом преобразователе с понижением частоты» (PDF) .
• Лакшми, Боппана; Дхар, Аниндья Сундар (06.10.2009). «CORDIC Architectures: Обзор» . Проектирование СБИС . Харагпур, Западная Бенгалия, Индия: Департамент электроники и электротехники, Индийский технологический институт (опубликовано 10 октября 2010 г.). 2010 : 1–19. DOI : 10.1155 / 2010/794891 . 794891.
• Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы» . квадиблок . Архивировано 3 июля 2018 года . Проверено 16 июля 2018 .

Внешние ссылки [ править ]

• Ван, Шаоюнь (июль 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 для тестирования и проверки производительности