KORDIK - CORDIC

Trigonometriya
Kontur Tarix Foydalanish Vazifalar  (teskari ) Umumlashtirilgan trigonometriya
Malumot
Shaxsiyat To'liq konstantalar Jadvallar Birlik doirasi
Qonunlar va teoremalar
Sinuslar Kosinalar Tangents Kotangenslar Pifagor teoremasi
Hisoblash
Trigonometrik almashtirish Integrallar  (teskari funktsiyalar ) Hosilalari

KORDIK (uchun COordinat Rotatsiya DIgital Csifatida tanilgan (omputer) Volder algoritmi, shu jumladan Dumaloq CORDIC (Jek E. Volder),^[1][2] Lineer CORDIC, Giperbolik CORDIC (Jon Stiven Uolter),^[3][4] va Umumiy giperbolik CORDIC (GH KORDIK) (Yuanyong Luo va boshqalar), ^[5][6] oddiy va samarali algoritm hisoblash uchun trigonometrik funktsiyalar, giperbolik funktsiyalar, kvadrat ildizlar, ko'paytirish, bo'linmalar va eksponentlar va logarifmlar o'zboshimchalik bilan asos bilan, odatda takrorlash uchun bitta raqam (yoki bit) bilan yaqinlashadi. Shuning uchun CORDIC ham raqamli raqamli algoritmlar. Sifatida tanilgan CORDIC va chambarchas bog'liq usullar psevdo-multiplikatsiya va soxta bo'linish yoki omillarni birlashtirish odatda yo'q bo'lganda ishlatiladi apparat multiplikatori mavjud (masalan oddiy mikrokontrollerlar va FPGA ) talab qilinadigan yagona operatsiyalar bo'lgani kabi qo'shimchalar, olib tashlash, bitshift va qidiruv jadvallari. Shunday qilib, ularning barchasi sinfiga tegishli almashtirish va qo'shish algoritmlari. Kompyuter fanida CORDIC ko'pincha amalga oshirish uchun ishlatiladi suzuvchi nuqta arifmetikasi maqsad platformada qo'shimcha xarajatlar yoki kosmik sabablarga ko'ra qo'shimcha qurilmalar etishmayotganida.

Tarix

Shu kabi matematik texnikalar tomonidan nashr etilgan Genri Briggs 1624 yildayoq^[7][8] va 1771 yilda Robert Gul,^[9] ammo CORDIC murakkabligi past bo'lgan cheklangan holatdagi protsessorlar uchun yaxshiroq optimallashtirilgan.

CORDIC 1956 yilda o'ylab topilgan^[10][11] tomonidan Jek E. Volder da aeroelektronika bo'limi Ishonch o'rnini almashtirish zarurati tufayli analog hal qiluvchi ichida B-58 bombardimonchi real vaqtda raqamli echimini aniqroq va samarali bajaradigan navigatsion kompyuter.^[11] Shuning uchun, CORDIC ba'zan a deb nomlanadi raqamli hal qiluvchi.^[12][13]

O'zining tadqiqotida Volder 1946 yilgi nashrdagi formuladan ilhomlangan CRC Kimyo va fizika bo'yicha qo'llanma:^[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 {hizalanmış}}}$

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

Uning tadqiqotlari CORDIC algoritmini echishni taklif qiladigan ichki texnik hisobotga olib keldi sinus va kosinus funktsiyalari va uni amalga oshiradigan prototipli kompyuter.^[10][11] Hisobotda giperbolikani hisoblash imkoniyati ham muhokama qilindi koordinatalarning aylanishi, logarifmlar va eksponent funktsiyalar o'zgartirilgan CORDIC algoritmlari bilan.^[10][11] CORDIC-dan foydalanish ko'paytirish va bo'linish bu vaqtda ham o'ylab topilgan.^[11] Convairdagi Volderning hamkasbi Dan H. Dagget CORDIC printsipiga asoslanib, ikkilik va ikkilik kodli o‘nli kasr (BCD).^[11][14]

1958 yilda Convair nihoyat hal qilish uchun namoyish tizimini qurishni boshladi radar tuzatish - nomlangan muammolarni hal qilish KORDIK I, 1960 yilda kompaniyani tark etgan Voldersiz yakunlandi.^[1][11] Ko'proq universal KORDIK II modellar A (statsionar) va B (havodagi) 1962 yilda Daggett va Garri Shuss tomonidan qurilgan va sinovdan o'tgan.^[11][15]

Volderning CORDIC algoritmi birinchi marta 1959 yilda ommaviy ravishda tasvirlangan,^{[1][2][11][13][16]} bu navigatsiya kompyuterlariga, shu jumladan kompaniyalar tomonidan kiritilishiga olib keldi Martin-Orlando, Kompyuter nazorati, Litton, Kearfott, Lear-Siegler, Sperri, Raytheon va Kollinz radiosi.^[11]

Volder qurish uchun Malkom MakMillan bilan hamkorlik qildi Afina, a belgilangan nuqta ish stoli kalkulyatori uning ikkilik CORDIC algoritmidan foydalangan holda.^[17] Dizayn bilan tanishtirildi Hewlett-Packard 1965 yil iyun oyida, ammo qabul qilinmadi.^[17] Shunday bo'lsa-da, MacMillan tanishtirdi Devid S. Kokran (HP) Volder algoritmiga va keyinchalik Koxran Volder bilan uchrashganda, uni xuddi shunday yondashishga murojaat qilgan Jon E. Meggitt (IBM^[18]kabi taklif qilgan edi psevdo-multiplikatsiya va soxta bo'linish 1961 yilda.^[18][19] Meggitt usuli ham 10-bazadan foydalanishni taklif qildi^[18] dan ko'ra tayanch 2, Volder's CORDIC tomonidan hozirgacha ishlatilgan. Ushbu harakatlar olib keldi ROMable 1966 yilda Hewlett-Packard ichida o'nlik kasrli CORDIC prototip mashinasini mantiqiy amalga oshirish,^[20][19] tomonidan qurilgan va kontseptual tarzda olingan Tomas E. Osborne prototipik Yashil mashina, to'rt funktsiyali, suzuvchi nuqta u to'ldirgan ish stoli kalkulyatori DTL mantiq^[17] 1964 yil dekabrda.^[21] Ushbu loyiha Hewlett-Packard-ning ilmiy funktsiyalarga ega bo'lgan birinchi ish stoli kalkulyatorini ommaviy namoyish qilishiga olib keldi HP 9100A 1968 yil mart oyida, seriyali ishlab chiqarish shu yilning oxiridan boshlanadi.^{[17][21][22][23]}

Qachon Vang laboratoriyalari HP 9100A ishlatilganligini aniqladi shunga o'xshash yondashuv uchun omillarni birlashtirish ularning oldingi usuli LOCI-1^[24] (1964 yil sentyabr) va LOCI-2 (1965 yil yanvar)^[25][26] Logaritmik hisoblash vositasi ish stoli kalkulyatorlari,^[27] ular muvaffaqiyatsiz Hewlett-Packard-dan birini buzganlikda ayblashdi Vang 1968 yildagi patentlar.^{[19][28][29][30]}

Jon Stiven Uolter Hewlett-Packard da algoritmni umumlashtirdi Birlashtirilgan CORDIC hisoblash imkonini beradigan 1971 yilda algoritm giperbolik funktsiyalar, tabiiy eksponentlar, tabiiy logaritmalar, ko'paytirish, bo'linmalar va kvadrat ildizlar.^{[31][3][4][32]} KORDIK subroutines trigonometrik va giperbolik funktsiyalar uchun ularning ko'pgina kodlari bo'lishishi mumkin.^[28] Ushbu rivojlanish birinchi natijaga olib keldi ilmiy qo'l kalkulyatori, HP-35 1972 yilda.^{[28][33][34][35][36][37]} Giperbolik CORDIC asosida, Yuanyong Luo va boshq. qo'shimcha ravishda 2019 yilda o'zboshimchalik bilan xed bazasi bilan logaritmalarni va eksponentlarni to'g'ridan-to'g'ri hisoblash uchun Generalized Hyperbolic CORDIC (GH CORDIC) ni taklif qildi.^{[5][6][38][39][40]} Nazariy jihatdan, Giperbolik CORDIC - bu GH CORDIC ning alohida hodisasidir.^[5]

Dastlab, CORDIC faqat ikkilik sanoq sistemasi Meggitt o'zining psevdo-multiplikatsiya usuli uchun o'nlik tizimdan foydalanishni taklif qilganiga qaramay, CORDIC kasr yana bir necha yil davomida asosan eshitilmagan bo'lib qoldi, shuning uchun Hermann Shmid va Entoni Bogacki buni 1973 yilidayoq yangilik sifatida taklif qildi^{[16][13][41][42][43]} va keyinchalik Hewlett-Packard uni 1966 yilda amalga oshirganligi aniqlandi.^{[11][13][20][28]}

O'nli CORDIC keng qo'llanila boshlandi cho'ntak kalkulyatorlari,^[13] ularning aksariyati ikkilik emas, ikkilik kodli o'nlik (BCD) da ishlaydi. Kirish va chiqish formatidagi bu o'zgarish CORDIC-ning asosiy hisoblash algoritmlarini o'zgartirmadi. CORDIC, ayniqsa, qo'lda ishlaydigan kalkulyatorlar uchun juda mos keladi, bu erda past narx va shuning uchun chip chiplari soni pastligi tezlikka qaraganda ancha muhimdir.

CORDIC dasturi joriy qilingan ARM-ga asoslangan STM32G4, Intel 8087,^{[43][44][45][46][47]} 80287,^[47][48] 80387^[47][48] ga qadar 80486^[43] koprotsessor qatori, shuningdek Motorola 68881^[43][44] va 68882 suzuvchi nuqta ko'rsatmalarining ayrim turlari uchun, asosan, darvozalar sonini (va murakkabligini) kamaytirishning bir usuli sifatida FPU kichik tizim.

Ilovalar

CORDIC trigonometrik, giperbolik va logarifmik funktsiyalarni hisoblash, haqiqiy va murakkab ko'paytmalar, bo'linish, kvadrat ildizlarni hisoblash, chiziqli tizimlarni echish kabi bir qator hisoblash vazifalari uchun oddiy smenali qo'shish operatsiyalaridan foydalanadi. o'ziga xos qiymat taxmin, yagona qiymat dekompozitsiyasi, QR faktorizatsiyasi va boshqalar. Natijada, CORDIC kabi turli sohalardagi dasturlar uchun ishlatilgan signal va tasvirni qayta ishlash, aloqa tizimlari, robototexnika va 3D grafika umumiy ilmiy va texnik hisob-kitoblardan tashqari.^[49][50]

Uskuna

Algoritmi navigatsion tizimda ishlatilgan Apollon dasturi "s Oyda harakatlanuvchi transport vositasi hisoblash rulman va masofa yoki masofa Oy moduli.^{[51]:14[52]:17} Amalga oshirish uchun CORDIC ishlatilgan Intel 8087 matematik koprotsessor, 1980 yilda apparatni ko'paytirishni amalga oshirish zaruriyatidan qochib.^[53]

CORDIC odatda qo'shimcha multiplikator mavjud bo'lmaganda (masalan, mikrokontroller) yoki u qo'llab-quvvatlaydigan funktsiyalarni amalga oshirish uchun zarur bo'lgan eshiklar sonini kamaytirish kerak bo'lganda (masalan, FPGA yoki ASIC ).

Boshqa tomondan, qo'shimcha ko'paytirgich mavjud bo'lganda (masalan., a DSP mikroprotsessor), jadvalni qidirish usullari va quvvat seriyasi odatda CORDIC dan tezroq. So'nggi yillarda CORDIC algoritmi turli biotibbiyot dasturlari, ayniqsa FPGA dasturlarida keng qo'llanilmoqda.

Dasturiy ta'minot

Faqatgina butun sonli protsessorlarga ega bo'lgan ko'plab eski tizimlar CORDIC-ni o'zlarining tarkibiy qismlari sifatida har xil darajada amalga oshirdilar IEEE suzuvchi nuqta kutubxonalar. Ko'pgina zamonaviy umumiy maqsadli protsessorlarda suzuvchi nuqta registrlari mavjud, chunki ular qo'shish, ayirish, ko'paytirish, bo'lish, sinus, kosinus, kvadrat ildiz, jurnal kabi umumiy operatsiyalarga ega.₁₀, tabiiy jurnal, ularda dasturiy ta'minot bilan CORDICni amalga oshirish zarurati deyarli mavjud emas. CORDIC-dan foydalanishni faqat mikrokontroller yoki maxsus xavfsizlik va cheklangan dasturiy ta'minot dasturlari ko'rib chiqishi kerak.

Ish tartibi

Aylantirish rejimi

CORDIC yordamida turli xil funktsiyalarni hisoblash mumkin. Ushbu tushuntirish CORDIC-ni qanday ishlatishni ko'rsatadi aylanish rejimi kerakli burchak berilganligini nazarda tutib, burchakning sinusi va kosinusini hisoblash radianlar va belgilangan nuqta formatida namoyish etilgan. Burchak uchun sinus yoki kosinusni aniqlash ${ displaystyle beta}$, y yoki x bo'yicha nuqtaning koordinatasi birlik doirasi kerakli burchakka mos keladigan topilishi kerak. CORDIC-dan foydalanib, vektordan boshlanadi ${ displaystyle v_ {0}}$:

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

Amaldagi CORDIC algoritmining tasviri

Birinchi takrorlashda ushbu vektor soat yo'nalishi bo'yicha 45 ° burilib, vektorni oladi ${ displaystyle v_ {1}}$. Ketma-ket takrorlanishlar kerakli burchakka erishilguncha vektorni o'lchamlarini kamaytirish bosqichlari bilan u yoki bu yo'nalishda aylantiradi. Qadam ${ displaystyle i}$ hajmi ${ displaystyle arctan {(2 ^ {- i})}}$ uchun ${ displaystyle i = 0,1,2, nuqta}$.

Rasmiy ravishda har bir takrorlash vektorni ko'paytirish orqali amalga oshiriladigan aylanishni hisoblab chiqadi ${ displaystyle v_ {i-1}}$ bilan aylanish matritsasi ${ displaystyle R_ {i}}$:

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

Aylanish matritsasi quyidagicha berilgan

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

Quyidagi ikkitadan foydalanish trigonometrik identifikatorlar:

${ 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 {hizalangan}}}$

aylanish matritsasi bo'ladi

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

Qaytgan vektor uchun ifoda ${ displaystyle v_ {i} = R_ {i} v_ {i-1}}$ keyin bo'ladi

${ 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}} ,}$

qayerda ${ displaystyle x_ {i-1}}$ va ${ displaystyle y_ {i-1}}$ ning tarkibiy qismlari ${ displaystyle v_ {i-1}}$. Burchaklarni cheklash ${ displaystyle gamma _ {i}}$ shu kabi ${ displaystyle tan ( gamma _ {i}) = pm 2 ^ {- i}}$, teginish bilan ko'paytirishni ikkita kuch bilan bo'linish bilan almashtirish mumkin, bu raqamli kompyuter texnikasida bit siljishi. So'ngra ifoda aylanadi

${ 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}},}$

qayerda

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

va ${ displaystyle sigma _ {i}}$ aylanish yo'nalishini aniqlash uchun ishlatiladi: agar burchak ${ displaystyle gamma _ {i}}$ ijobiy bo'lsa, unda ${ displaystyle sigma _ {i}}$ +1 ga teng, aks holda u -1 ga teng.

${ displaystyle K_ {i}}$ takrorlanadigan jarayonda e'tiborsiz qoldirilishi mumkin va keyin miqyosi koeffitsienti bilan qo'llanilishi mumkin

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

oldindan hisoblab chiqiladi va jadvalda yoki bitta doimiy sifatida saqlanadi, agar takrorlanish soni aniqlangan bo'lsa. Ushbu tuzatish oldindan, miqyosi bilan amalga oshirilishi mumkin ${ displaystyle v_ {0}}$ va shuning uchun ko'paytirishni tejash. Bundan tashqari, buni ta'kidlash mumkin^[43]

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

algoritmning murakkabligini yanada kamaytirishga imkon berish. Ba'zi ilovalar tuzatishdan qochishi mumkin ${ displaystyle K}$ umuman, natijada qayta ishlash daromadiga olib keladi ${ displaystyle A}$:^[54]

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

Etarli miqdordagi takrorlashdan so'ng, vektorning burchagi kerakli burchakka yaqin bo'ladi ${ displaystyle beta}$. Oddiy maqsadlar uchun 40 ta takrorlash (n = 40) o'ninchi kasrga to'g'ri natijani olish uchun etarli.

Qolgan yagona vazifa - har bir iteratsiyada aylanish soat yo'nalishi bo'yicha yoki teskari yo'nalishda bo'lishi kerakligini aniqlash (ning qiymatini tanlash) ${ displaystyle sigma}$). Bu har bir iteratsiyada burchakning qay darajada aylanganligini kuzatib borish va kerakli burchakdan ayirish orqali amalga oshiriladi; keyin kerakli burchakka yaqinlashish uchun ${ displaystyle beta}$, agar ${ displaystyle beta _ {n + 1}}$ ijobiy, aylanish soat yo'nalishi bo'yicha, aks holda u salbiy va aylanish soat sohasi farqli ravishda:

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

Ning qiymatlari ${ displaystyle gamma _ {n}}$ shuningdek oldindan hisoblab chiqilishi va saqlanishi kerak. Ammo kichik burchaklar uchun, ${ displaystyle arctan ( gamma _ {n}) = gamma _ {n}}$ jadval o'lchamini kamaytirib, sobit nuqta bilan tasvirlashda.

Yuqoridagi rasmda ko'rinib turganidek, burchakning sinusi ${ displaystyle beta}$ bo'ladi y yakuniy vektorning koordinatasi ${ displaystyle v_ {n},}$ esa x koordinat - kosinus qiymati.

Vektorizatsiya rejimi

Yuqorida tavsiflangan aylanish-rejim algoritmi har qanday vektorni aylantirishi mumkin (faqat birlik vektori bo'ylab tekislangan emas x o'qi) -90 ° dan + 90 ° gacha bo'lgan burchak bilan. Aylanish yo'nalishi bo'yicha qarorlar bog'liq ${ displaystyle beta _ {i}}$ ijobiy yoki salbiy.

Vektorlashtirish-ishlash tartibi algoritmni biroz o'zgartirishni talab qiladi. Bu vektor bilan boshlanadi x koordinatasi ijobiy va the y koordinata o'zboshimchalik bilan Ketma-ket aylanishlar vektorni "ga" aylantirish maqsadiga ega x o'qi (va shuning uchun y koordinata nolga). Har bir qadamda qiymati y aylanish yo'nalishini belgilaydi. Ning yakuniy qiymati ${ displaystyle beta _ {i}}$ umumiy aylanish burchagini o'z ichiga oladi. Ning yakuniy qiymati x tomonidan o'lchangan asl vektorning kattaligi bo'ladi K. Shunday qilib, vektorlashtirish rejimidan aniq foydalanish to'rtburchaklar dan qutb koordinatalariga o'tishdir.

Amalga oshirish

Dasturiy ta'minot misoli

Quyidagi MATLAB /GNU oktavi hech kimga ishonmaydigan CORDIC dasturini amalga oshirish transandantal funktsiyalar jadvallarni oldindan hisoblashdan tashqari. Agar takrorlash soni bo'lsa n oldindan belgilanadi, keyin ikkinchi jadvalni bitta doimiy bilan almashtirish mumkin. MATLAB standart ikki tomonlama aniqlikdagi arifmetikasi va "formatdagi uzunligi" bilan chop etish natijasida natijalar aniqligini oshiradi n taxminan 48 gacha.

funktsiyav =samimiy(beta, n)% Ushbu funktsiya v = [cos (beta), sin (beta)] (radianlarda beta) ni hisoblab chiqadin takrorlanishdan%. N ni oshirish aniqlikni oshiradi.agar beta <-pi / 2 || beta> pi / 2    agar beta <0        v = samimiy(beta-versiya + pi, n);    boshqav = samimiy (beta - pi, n);    oxiriv = -v; % ikkinchi yoki uchinchi chorak uchun belgini aylantiring    qaytishoxiriCORDIC tomonidan ishlatiladigan doimiy jadvallar initsializatsiyasi% ga ikkita salbiy kuchning arktangentsalari jadvali kerak, radianlarda:% burchaklar = atan (2.. ^ - (0:27));burchaklar =  [  ...    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 ];% va o'zaro uzunlikdagi vektorlarning mahsulot jadvali [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, uzunlik(Kvalues)));% Loop o'zgaruvchilarini ishga tushirish:v = [1;0]; % 2-vektorli kosinus va nol sinusi bilan boshlanadiikki kuch = 1;burchak = burchaklar(1);% Takrorlashuchun j = 0:n-1;    agar beta <0        sigma = -1;    boshqasigma = 1;    oxirifactor = sigma * poweroftwo;    % Matritsani ko'paytirishni ikkala kattalik bo'yicha masshtablash va qo'shib ayirish yordamida amalga oshirish mumkinligiga e'tibor bering    R = [1, -omil; omil, 1];    v = R * v; % 2 dan 2 gacha matritsa ko'paytiriladi    beta-versiya = beta-versiya - sigma * burchak; % qolgan burchakni yangilang    ikki kuch = ikki kuch / 2;    % burchakni jadvaldan yangilaydi yoki oxir-oqibat ikkiga bo'linib    agar j + 2> uzunlik (burchaklar)        burchak = burchak / 2;    boshqaburchak = burchaklar (j + 2);    oxirioxiri% Chiqish vektorining uzunligini [cos (beta), sin (beta)] qilib sozlang:v = v * Kn;qaytishtugatish funktsiyasi

Ikki-ikkitasi matritsani ko'paytirish oddiy smenalar va qo'shimchalar juftligi tomonidan amalga oshirilishi mumkin.

    x = v[0] - sigma * (v[1] * 2^(-j));    y = sigma * (v[0] * 2^(-j)) + v[1];    v = [x; y];

Java-da matematik sinf a scalb (ikki baravar x, int o'lchov) bunday siljishni amalga oshirish usuli,^[55] C ga ega ldexp funktsiyasi,^[56] va x86 sinf protsessorlari quyidagilarga ega o'lchovli suzuvchi nuqta ishlashi.^[57]

Uskuna misoli

Soni mantiq eshiklari CORDIC-ni amalga oshirish uchun multiplikator uchun zarur bo'lgan raqam bilan taqqoslash mumkin, chunki ikkalasi ham siljish va qo'shimchalar kombinatsiyasini talab qiladi. Multiplikatorga asoslangan yoki CORDIC-ga asoslangan dasturni tanlash kontekstga bog'liq bo'ladi. Ikkala ko'paytma murakkab sonlar ularning haqiqiy va xayoliy tarkibiy qismlari (to'rtburchaklar koordinatalari) bilan ifodalangan, masalan, 4 marta ko'paytirishni talab qiladi, ammo ularni qutb koordinatalari bilan ifodalangan murakkab sonlar ustida ishlaydigan bitta CORDIC tomonidan amalga oshirilishi mumkin, ayniqsa, agar ularning kattaligi ahamiyatsiz bo'lsa ( birlik doirasidagi vektorli murakkab vektor aslida aylanishga to'g'ri keladi). CORDIC-lar ko'pincha telekommunikatsiya sxemalarida qo'llaniladi raqamli pastga o'tkazgichlar.

Tegishli algoritmlar

CORDIC sinfining bir qismidir "almashtirish va qo'shish" algoritmlari, Genri Briggsning ishidan olingan logaritma va eksponent algoritmlar kabi. Ko'p elementar funktsiyalarni hisoblash uchun ishlatilishi mumkin bo'lgan yana bir siljish va qo'shish algoritmi bu BKM algoritmi, bu logaritma va eksponent algoritmlarni kompleks tekislikka umumlashtirishdir. Masalan, BKM yordamida haqiqiy burchakning sinusi va kosinusini hisoblash mumkin ${ displaystyle x}$ (radianlarda) ning eksponentligini hisoblash orqali ${ displaystyle 0 + ix}$, bu ${ displaystyle operator nomi {cis} (x) = cos (x) + i sin (x)}$. BKM algoritmi CORDICga qaraganda biroz murakkabroq, ammo uning afzalligi shundaki, unga miqyoslash koeffitsienti kerak emas (K).

Shuningdek qarang

• Kvadrat ildizlarni hisoblash usullari
• IEEE 754
• Suzuvchi nuqta birliklari
• Raqamli elektronlar / CORDIC Vikikitoblarda

Adabiyotlar

Qo'shimcha o'qish

• Parini, Jozef A. (1966-09-05). "DIVIC murakkab navigatsiya savollariga javob beradi". Elektron mahsulotlar: 105–111. ISSN  0013-5070. (NB.) DIVIC degan ma'noni anglatadi DIgital o'zgaruvchan o'sish kompyuter. Ba'zi manbalarda bu kabi noto'g'ri yozilgan J. M. Parini.)
• Anderson, Stenli F.; Erl, Jon G.; Goldschmidt, Robert Elliott; Pauers, Don M. (1965-11-01). "IBM System / 360 Model 91: suzuvchi nuqtalarni bajarish birligi" (PDF). IBM Journal of Research and Development. Riverton, Nyu-Jersi, AQSh (1967 yil yanvarda nashr etilgan). 11 (1): 34–53. doi:10.1147 / rd.111.0034. Olingan 2016-01-02.
• Likkardo, Maykl A. (sentyabr, 1968). CORDIC rejimining ishlashiga urg'u beradigan o'zaro bog'liqlik protsessori (Magistrlik dissertatsiyasi). Berkli, Kaliforniya, AQSh: Berkli Kaliforniya universiteti, Elektrotexnika kafedrasi. OCLC  500565168.
• AQSh patent 3576983A, Cochran, David S., "Kvadrat ildizlarni hisoblash uchun raqamli kalkulyator tizimi", 1971-05-04 yillarda nashr etilgan, 1971-05-04 da chiqarilgan, tayinlangan Hewlett-Packard Co.  ([14] )
• Chen, Tien Chi (1972 yil iyul). "Eksponent ma'lumotlarni, logaritmalarni, nisbatlarni va kvadrat ildizlarni avtomatik hisoblash" (PDF). IBM Journal of Research and Development. 16 (4): 380–388. doi:10.1147 / rd.164.0380. ISSN  0018-8646. Olingan 2016-01-02.
• Egbert, Uilyam E. (1977 yil may). "Shaxsiy kalkulyator algoritmlari I: kvadrat ildizlar" (PDF). Hewlett-Packard jurnali. Palo Alto, Kaliforniya, AQSh: Hewlett-Packard. 28 (9): 22–24. Olingan 2016-01-02. ([15] )
• Egbert, Uilyam E. (1977 yil iyun). "Shaxsiy kalkulyator algoritmlari II: trigonometrik funktsiyalar" (PDF). Hewlett-Packard jurnali. Palo Alto, Kaliforniya, AQSh: Hewlett-Packard. 28 (10): 17–20. Olingan 2016-01-02. ([16] )
• Egbert, Uilyam E. (1977 yil noyabr). "Shaxsiy kalkulyator algoritmlari III: teskari trigonometrik funktsiyalar" (PDF). Hewlett-Packard jurnali. Palo Alto, Kaliforniya, AQSh: Hewlett-Packard. 29 (3): 22–23. Olingan 2016-01-02. ([17] )
• Egbert, Uilyam E. (1978 yil aprel). "Shaxsiy kalkulyator algoritmlari IV: logaritmik funktsiyalar" (PDF). Hewlett-Packard jurnali. Palo Alto, Kaliforniya, AQSh: Hewlett-Packard. 29 (8): 29–32. Olingan 2016-01-02. ([18] )
• Senzig, Don (1975). "Kalkulyator algoritmlari". IEEE Compcon Reader Digest. IEEE: 139–141. IEEE katalogi № 75 CH 0920-9C.
• Baykov, Vladimir D. (1972), Voprosy issedovaniya vichisleniya elementarnyx funktsiyasi po metodu «tsifra za tsifroy» [Boshlang'ich funktsiyalarni raqamlar bo'yicha raqamlar asosida baholash muammolari (CORDIC) texnikasi] (Doktorlik dissertatsiyasi) (rus tilida), Leningrad davlat elektrotexnika universiteti
• Baykov, Vladimir D .; Smolov, Vladimir B. (1975). Apparaturnaja realizatsija elementarnikh funktsij v CVM Apparaturnaya realizatsiya elementarnyx funktsiyasi v TsVM [Kompyuterlarda elementar funktsiyalarni texnik jihatdan amalga oshirish] (rus tilida). Leningrad davlat universiteti. Arxivlandi asl nusxasidan 2019-03-02. Olingan 2019-03-02.
• Baykov, Vladimir D .; Seljutin, S. A. (1982). Vychislenie elementarnyx funktsiyasi v EKVM [Mikrokalkulyatorlarda elementar funktsiyalarni baholash] (rus tilida). Moskva: Radio i svjaz (Radio i svyaz).
• Baykov, Vladimir D .; Smolov, Vladimir B. (1985). Spetsializirovannye protsessori: etatsionatsion algoritmy i struktury [Maxsus maqsadli protsessorlar: takrorlanadigan algoritmlar va tuzilmalar] (rus tilida). Moskva: Radio i svjaz (Radio i svyaz).
• Coppens, Tomas, ed. (1980 yil yanvar). "TI 58/59 ROMdagi CORDIC konstantalari". Texas Instruments Software Exchange Newsletter. Kapellen, Belgiya: TISOFT. 2 (2).
• Coppens, Tomas, ed. (1980 yil aprel). "Tabiiy logarifmni hisoblash sxemasi / e^x hisoblash sxemasi /¹⁄_x hisoblash sxemasi ". Texas Instruments Software Exchange Newsletter. Kapellen, Belgiya: TISOFT. 2 (3). (haqida CORDIC in TI-58 /TI-59 )
• TI Graphic Products Team (1995) [1993]. "Transandantal funktsiya algoritmlari". Dallas, Texas, AQSh: Texas Instruments, Iste'mol mahsulotlari. Arxivlandi asl nusxasidan 2016-03-17. Olingan 2019-03-02.
• Jorke, Gyunter; Lempe, Bernxard; Vengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik (nemis tilida) (1 nashr). Berlin, Germaniya: VEB Verlag Technik. 219, 261, 271-296 betlar. ISBN  3341005153. EAN  9783341005156. MPN 5539165. Litsenziya 201.370 / 4/89. Olingan 2015-12-01.
• Frerking, Marvin E. (1994). Aloqa tizimlarida raqamli signalni qayta ishlash (1 nashr).
• Kantabutra, Vitit (1996). "Eksponent va trigonometrik funktsiyalarni hisoblash uchun qo'shimcha qurilmalarda". Kompyuterlarda IEEE operatsiyalari. 45 (3): 328–339. doi:10.1109/12.485571.
• Banerji, Ayan (2001). [_ob = ArticleURL & _udi = B6V0X-4313PR1-1 "Biotibbiy signallarni qayta ishlash uchun CORDIC asosidagi FFT protsessorini FPGA amalga oshirish"] Tekshiring | url = qiymati (Yordam bering). Mikroprotsessorlar va mikrosistemalar. Xaragpur, G'arbiy Bengal, Hindiston. 25 (3): 131–142. doi:10.1016 / S0141-9331 (01) 00106-5.
• Kahan, Uilyam Morton (2002-05-20). "Suzuvchi nuqta logaritmalari va eksponentlari uchun psevdo-divizion algoritmlari" (PDF). Berkli, Kaliforniya, AQSh: Kaliforniya universiteti. Arxivlandi asl nusxasi (PDF) 2015-12-25. Olingan 2016-01-15.
• Cockrum, Chris K. (Kuz 2008). "Raqamli pastga konvertorda CORDIC algoritmini amalga oshirish" (PDF).
• Lakshmi, Boppana; Dhar, Anindya Sundar (2009-10-06). "CORDIC Arxitektura: So'rov". VLSI dizayni. Xaragpur, G'arbiy Bengal, Hindiston: Hindiston Texnologiya Instituti elektronika va elektr aloqa muhandisligi bo'limi (2010-10-10 yillarda nashr etilgan). 2010: 1–19. doi:10.1155/2010/794891. 794891.
• Savard, Jon J. G. (2018) [2006]. "Arifmetikaning ilg'or usullari". quadiblok. Arxivlandi asl nusxasidan 2018-07-03. Olingan 2018-07-16.

Tashqi havolalar

• Vang, Shaoyun (2011 yil iyul), KORDIK Bibliografiya sayti
• Yumshoq CORDIC IP (verilog HDL kodi)
• KORDIK Bibliografiya sayti
• BASIC Stamp, CORDIC matematik dastur
• CORDIC dasturini verilogda amalga oshirish
• O'zboshimchalik bilan maqsadli qiymat bilan CORDIC vektorlash
• PicBasic Pro, Pic18 CORDIC matematik dasturlari
• Python CORDIC dasturini amalga oshirish
• Belgilangan CORDIC uchun oddiy C kodi
• O'quv qo'llanmasi va MATLABni amalga oshirish - Kompleks sonning fazasini taxmin qilish uchun CORDIC yordamida
• C ++ va VHDL-da test stendlari bilan Arx-dagi apparat CORDIC-larining tavsifi
• CORDIC algoritmiga kirish
• CORDIC algoritmini raqamli pastga o'tkazgichda amalga oshirish
• CORDIC algoritmining 50 yilligi
• CORDIC algoritmini amalga oshirish: trigonometrik va giperbolik funktsiyalar uchun sobit nuqta kodi, Sinov va ishlashni tekshirish uchun C kodi