KORDİK - CORDIC

CORDIC için ( CO ordinat R -rotasyon DI gital olarak da bilinen, omputer) Volder algoritması ya da: Rakam göre basamaklı usul Dairesel CORDIC (Jack E. Volder), doğrusal CORDIC , hiperbolik CORDIC (John Stephen Walther) ve Genelleştirilmiş Hiperbolik CORDIC ( GH CORDIC ) (Yuanyong Luo ve ark.), bir basit ve etkilidir yani algoritma hesaplamak trigonometrik fonksiyonlar , hiperbolik fonksiyonlar , karekök , çarpma , bölünmeleri ve üstel ve logaritma tipik olarak bir rakam ile birleşen rasgele bir baz ile (veya bit ) yineleme başına. CORDIC bu nedenle aynı zamanda basamak basamak algoritmalara bir örnektir . Olarak bilinen CORDIC ve yakın ilişkili yöntemler sözde çoğalması ve psödo-bölme ya da faktör birleştirilmesi herhangi bir zaman yaygın olarak kullanılan donanım çarpan kullanılabilir (örneğin, basit mikro denetleyici ve FPGA ) gerektiriyorsa, sadece operasyon olarak, ilave , çıkarmalar , bitshift ve arama tabloları . Bu nedenle, hepsi kaydırma ve ekleme algoritmaları sınıfına aittir . Bilgisayar biliminde, CORDIC genellikle , hedef platformda maliyet veya alan nedenleriyle donanım çarpması olmadığında kayan nokta aritmetiğini uygulamak için kullanılır .

Tarih

Benzer matematiksel teknikler 1624 gibi erken bir tarihte Henry Briggs ve 1771'de Robert Flower tarafından yayınlandı , ancak CORDIC düşük karmaşıklıklı sonlu durum CPU'ları için daha iyi optimize edilmiştir.

CORDIC tarafından 1956 yılında tasarlanmıştı Jack E. Volder de aeroelectronics bölümü Convair yerine zorunluluk dışında analog çözümleyicinizi içinde B-58 bombardıman uçağı daha doğru ve daha hızlı gerçek zamanlı dijital çözüm ile 'ın navigasyon bilgisayarı. Bu nedenle, CORDIC bazen dijital çözümleyici olarak adlandırılır .

Volder araştırmasında, CRC Kimya ve Fizik El Kitabı'nın 1946 baskısındaki bir formülden ilham aldı :

ile , .

Araştırması, sinüs ve kosinüs fonksiyonlarını çözmek için CORDIC algoritmasını ve bunu uygulayan prototip bir bilgisayarı öneren dahili bir teknik rapora yol açtı . Rapor ayrıca , değiştirilmiş CORDIC algoritmaları ile hiperbolik koordinat döndürme , logaritma ve üstel fonksiyonları hesaplama olasılığını da tartıştı . CORDIC'i çarpma ve bölme için kullanmak da bu zamanda tasarlandı. CORDIC ilkesine dayalı olarak, Volder'in Convair'deki bir meslektaşı olan Dan H. Daggett, ikili ve ikili kodlu ondalık sayı (BCD) arasında dönüştürme algoritmaları geliştirdi .

1958'de Convair nihayet CORDIC I adlı radar düzeltme sorunlarını çözmek için bir gösteri sistemi kurmaya başladı ve 1960'ta şirketten ayrılan Volder olmadan tamamlandı. Daha evrensel CORDIC II modelleri A (sabit) ve B (havadan), 1962'de Daggett ve Harry Schuss tarafından inşa edildi ve test edildi.

Volder'ın CORDIC algoritması ilk olarak 1959'da halka açık olarak tanımlandı ve bu da Martin-Orlando , Computer Control , Litton , Kearfott , Lear-Siegler , Sperry , Raytheon ve Collins Radio gibi şirketler tarafından navigasyon bilgisayarlarına dahil edilmesine neden oldu .

Volder inşa etmek Malcolm McMillan ile takım Athena , bir sabit nokta masaüstü hesap makinesi onun ikili CORDIC algoritmayı kullanan. Tasarım, Haziran 1965'te Hewlett-Packard'a tanıtıldı , ancak kabul edilmedi. Yine de McMillan, David S. Cochran'ı (HP) Volder'ın algoritmasıyla tanıştırdı ve Cochran daha sonra Volder ile tanıştığında onu John E. Meggitt'in (IBM) 1961'de sözde çarpma ve sözde bölme olarak önerdiği benzer bir yaklaşıma yönlendirdi . Meggitt'in yöntemi ayrıca , şimdiye kadar Volder's CORDIC tarafından kullanıldığı gibi, taban 2 yerine taban 10'un kullanılmasını önermektedir. Bu çabalar , 1966'da Hewlett-Packard'ın içinde, Thomas E. Osborne'un sahip olduğu dört işlevli, kayan noktalı bir masaüstü hesap makinesi olan prototipik Yeşil Makinesi tarafından oluşturulan ve kavramsal olarak türetilen bir ondalık CORDIC prototip makinesinin ROMable mantık uygulamasına yol açtı. Aralık 1964'te DTL mantığında tamamlandı . Bu proje, Hewlett-Packard'ın bilimsel işlevlere sahip ilk masaüstü hesap makinesi olan hp 9100A'nın Mart 1968'de halka açık tanıtımıyla sonuçlandı ve seri üretimi o yıl daha sonra başladı.

Ne zaman Wang Laboratuvarları hp 9100A kullanılan bulundu benzer bir yaklaşım için birleştirerek faktörü daha önceki yöntemi LOCI-1 (1964 Eylül) ve LOCI-2 (Ocak 1965) Logaritmik Computing Enstrüman masaüstü hesap makineleri, bunlar başarısız ihlali Hewlett-Packard suçladı biri bir Wang 1968 yılında 'ın patent.

John Stephen Walther Hewlett-Packard de içine algoritma genelleştirilmiş Birleştirilmiş CORDIC o hesaplamak için izin 1971 yılında algoritma hiperbolik fonksiyonlar , doğal üstel , doğal logaritma , çarpma , bölünmeleri ve karekök . Trigonometrik ve hiperbolik fonksiyonlar için CORDIC alt programları , kodlarının çoğunu paylaşabilir. Bu gelişme , 1972'de ilk bilimsel el hesap makinesi olan HP-35 ile sonuçlandı. Hiperbolik CORDIC'e dayanan Yuanyong Luo ve ark. ayrıca 2019'da logaritma ve üstelleri rastgele bir sabit tabanla doğrudan hesaplamak için bir Genelleştirilmiş Hiperbolik CORDIC (GH CORDIC) önerdi. Teorik olarak, Hiperbolik CORDIC, GH CORDIC'in özel bir durumudur.

Başlangıçta, CORDIC yalnızca ikili sayı sistemi kullanılarak uygulandı ve Meggitt'in sahte çarpma yaklaşımı için ondalık sistemin kullanılmasını önermesine rağmen, ondalık CORDIC birkaç yıl daha çoğunlukla duyulmamış kalmaya devam etti, böylece Hermann Schmid ve Anthony Bogacki hala önerdi. 1973 kadar geç bir yenilik olarak görüldü ve ancak daha sonra Hewlett-Packard'ın 1966'da zaten uyguladığı bulundu.

Decimal CORDIC , çoğu ikili kod yerine ikili kodlu ondalık (BCD) olarak çalışan cep hesaplayıcılarında yaygın olarak kullanılmaya başlandı . Giriş ve çıkış biçimindeki bu değişiklik, CORDIC'in temel hesaplama algoritmalarını değiştirmedi. CORDIC, özellikle düşük maliyetin ve dolayısıyla düşük çip kapısı sayısının hızdan çok daha önemli olduğu elde taşınan hesap makineleri için çok uygundur.

CORDIC hayata geçirildi ARM tabanlı STM32G4 , Intel 8087 , 80287 , 80387 kadar 80486 işlemci serisi yanı sıra Motorola 68881 ve 68882 esas kapısı sayılarını azaltmak için bir yol olarak, kayan nokta talimatların bazı türlü (ve karmaşıklığı) FPU alt sisteminin.

Uygulamalar

CORDIC, trigonometrik, hiperbolik ve logaritmik fonksiyonların hesaplanması, gerçek ve karmaşık çarpmalar, bölme, karekök hesaplama, doğrusal sistemlerin çözümü, özdeğer tahmini, tekil değer ayrıştırması , QR çarpanlarına ayırma ve diğerleri. Sonuç olarak, CORDIC, genel bilimsel ve teknik hesaplamanın yanı sıra sinyal ve görüntü işleme , iletişim sistemleri , robotik ve 3D grafikler gibi çeşitli alanlardaki uygulamalar için kullanılmıştır .

Donanım

Algoritması seyir sistemi kullanılmıştır Apollo programı 'nin ay taşıtı işlem için yatak gelen ve dizi veya mesafe Ay modülü . CORDIC, 1980'de Intel 8087 matematik yardımcı işlemcisini uygulamak için kullanıldı ve donanım çarpması uygulama ihtiyacını ortadan kaldırdı.

CORDIC, bir donanım çarpanı mevcut olmadığında (örneğin, bir mikro denetleyici) veya desteklediği işlevleri uygulamak için gereken kapı sayısının en aza indirilmesi gerektiğinde (örneğin, bir FPGA veya ASIC'de ) genellikle diğer yaklaşımlardan daha hızlıdır . Aslında, CORDIC, Xilinx için Vivado gibi FPGA geliştirme uygulamalarında standart bir drop-in IP'dir, oysa bir güç serisi uygulaması böyle bir IP'nin özgünlüğünden kaynaklanmaz, yani CORDIC birçok farklı işlevi (genel amaçlı) hesaplayabilirken, bir güç serisi uygulamalarını yürütmek için yapılandırılan donanım çarpanı, yalnızca tasarlandığı işlevi hesaplayabilir.

Öte yandan, bir donanım çarpanı mevcut olduğunda ( örneğin , bir DSP mikroişlemcisinde), tablo arama yöntemleri ve güç serileri genellikle CORDIC'den daha hızlıdır. Son yıllarda, CORDIC algoritması, özellikle FPGA uygulamalarında, çeşitli biyomedikal uygulamalar için yaygın olarak kullanılmaktadır.

STM32G4 serisi ve bazı STM32H7 MCUs dizisinde, için grafik gibi çeşitli karma sinyal uygulamalarında hesaplamaları hızlandırmak için bir CORDIC modülünü uygulamak İnsan Makine Arayüzü ve saha yönelimli kontrol motorların. Bir güç serisi yaklaşımı kadar hızlı olmasa da, CORDIC, ARM CMSIS ve C standart kitaplıkları tarafından sağlananlar gibi tablo tabanlı uygulamaları enterpolasyona tabi tutmaktan gerçekten daha hızlıdır. Sağlanan CORDIC modülleri sonuçta yalnızca 20 bit hassasiyet elde ettiğinden sonuçlar biraz daha az doğru olabilir. Örneğin, ARM uygulamasına kıyasla performans farkının çoğu, tam kayan nokta kesinliğine (24 bit) ulaşan ve muhtemelen bu hassasiyete göreli hata elde edebilen enterpolasyon algoritmasının ek yükünden kaynaklanmaktadır. Diğer bir faydası ise CORDIC modülünün bir yardımcı işlemci olması ve diğer CPU görevleriyle paralel olarak çalıştırılabilmesidir.

Kuvvet serilerini kullanmanın sorunu, küçük mutlak hata sağlarken, iyi davranışlı göreli hata göstermemeleridir.

Yazılım

Yalnızca tamsayılı CPU'lara sahip birçok eski sistem, CORDIC'i IEEE kayan nokta kitaplıklarının bir parçası olarak değişen kapsamlarda uygulamıştır . Modern genel amaçlı CPU'ların çoğunda toplama, çıkarma, çarpma, bölme, sinüs, kosinüs, karekök, log 10 , doğal log gibi ortak işlemlere sahip kayan noktalı yazmaçlar olduğundan, bunlara yazılımla CORDIC uygulama ihtiyacı neredeyse sıfırdır. -mevcut. Yalnızca mikro denetleyici veya özel güvenlik ve zaman kısıtlamalı yazılım uygulamalarının CORDIC kullanmayı düşünmesi gerekir.

Operasyon modları

Döndürme modu

CORDIC, bir dizi farklı işlevi hesaplamak için kullanılabilir. Bu açıklama, istenen açının radyan cinsinden verildiğini ve sabit nokta biçiminde temsil edildiğini varsayarak, bir açının sinüs ve kosinüsünü hesaplamak için CORDIC'in döndürme modunda nasıl kullanılacağını gösterir . Bir açı için sinüs ve kosinüs belirlemek için , y veya X üzerindeki bir noktanın koordinat birim çember istenen açısına karşılık gelen bulunması gerekmektedir. CORDIC kullanarak, biri şu vektörle başlar :

Devam eden CORDIC algoritmasının bir örneği

İlk yinelemede, bu vektör, vektörü elde etmek için saat yönünün tersine 45° döndürülür . Ardışık yinelemeler, istenen açı elde edilene kadar vektörü boyut küçültme adımlarıyla bir veya diğer yönde döndürür. Adım boyutu içindir .

Daha resmi olarak, her yineleme, vektörü döndürme matrisi ile çarparak gerçekleştirilen bir döndürmeyi hesaplar :

Dönme matrisi şu şekilde verilir:

Aşağıdaki iki trigonometrik kimliği kullanarak :

rotasyon matrisi olur

Döndürülmüş vektör için ifade daha sonra olur

nerede ve bileşenleridir . Kısıtlama açılar şekilde teğet çarpma verimli bir şekilde kullanan bir dijital bilgisayar donanım yapılır iki gücüne, bir bölme ile ikame edilmiş olabilir, biraz kayma . ifade daha sonra olur

nerede

ve dönme yönünü belirlemek için kullanılır: açı pozitifse +1, değilse -1'dir.

yinelemeli süreçte göz ardı edilebilir ve daha sonra bir ölçeklendirme faktörü ile uygulanabilir

önceden hesaplanır ve bir tabloda veya yineleme sayısı sabitse tek bir sabit olarak saklanır. Bu düzeltme, ölçeklendirme ve dolayısıyla bir çarpma kaydederek önceden de yapılabilir . Ek olarak, not edilebilir ki

algoritmanın karmaşıklığını daha da azaltmak için. Bazı uygulamalar tamamen düzeltme yapmaktan kaçınarak işlem kazancına neden olabilir :

Yeterli sayıda yinelemeden sonra vektörün açısı istenen açıya yakın olacaktır . Çoğu sıradan amaç  için, 10. ondalık basamağa kadar doğru sonucu elde etmek için 40 yineleme ( n = 40) yeterlidir.

Geriye kalan tek görev, dönüşün her yinelemede saat yönünde mi yoksa saat yönünün tersine mi olacağını belirlemektir ( değerini seçerek ). Bu, her yinelemede açının ne kadar döndürüldüğünü takip ederek ve bunu istenen açıdan çıkararak yapılır; Daha sonra yakın istediği açısına almak için eğer pozitif ise, döndürme, saat yönünde olduğunu aksi takdirde negatiftir ve rotasyon yönünün tersine geçerli:

değerleri de önceden hesaplanmalı ve saklanmalıdır. Ancak küçük açılar için, sabit nokta gösteriminde tablo boyutunu küçültmek.

Yukarıdaki çizimde görüldüğü gibi, açılı sinüs olan y son vektörden koordinatı ise X kosinüs değerdir koordine ederler.

Vektör modu

Yukarıda açıklanan döndürme modu algoritması, herhangi bir vektörü (yalnızca x ekseni boyunca hizalanmış bir birim vektörü değil ) -90° ile +90° arasında bir açıyla döndürebilir . Dönme yönüne ilişkin kararlar olumlu veya olumsuz olmasına bağlıdır .

Vektörleme çalışma modu, algoritmada küçük bir değişiklik gerektirir. x koordinatı pozitif ve y koordinatı keyfi olan bir vektörle başlar . Ardışık döndürmeler, vektörü x eksenine döndürme (ve dolayısıyla y koordinatını sıfıra indirme) amacına sahiptir . Her adımda, y değeri dönme yönünü belirler. Son değeri toplam dönüş açısını içerir. x'in son değeri, K tarafından ölçeklenen orijinal vektörün büyüklüğü olacaktır . Dolayısıyla, vektör modunun bariz bir kullanımı, dikdörtgenden kutupsal koordinatlara dönüşümdür.

uygulama

Yazılım örneği

Aşağıdaki CORDIC'in MATLAB / GNU Octave uygulamasıdır ve tabloların ön hesaplaması dışında herhangi bir aşkın işleve dayanmaz . İterasyon sayısı n önceden belirlenmişse, ikinci tablo tek bir sabitle değiştirilebilir. MATLAB'ın standart çift kesinlikli aritmetiği ve "uzun biçimli" çıktısıyla, sonuçların doğruluğu n için yaklaşık 48'e kadar artar .

function v = cordic(beta,n)
% This function computes v = [cos(beta), sin(beta)] (beta in radians)
% using n iterations. Increasing n will increase the precision.

if beta < -pi/2 || beta > pi/2
    if beta < 0
        v = cordic(beta + pi, n);
    else
        v = cordic(beta - pi, n);
    end
    v = -v; % flip the sign for second or third quadrant
    return
end

% Initialization of tables of constants used by CORDIC
% need a table of arctangents of negative powers of two, in radians:
% angles = atan(2.^-(0:27));
angles =  [  ...
    0.78539816339745   0.46364760900081   0.24497866312686   0.12435499454676 ...
    0.06241880999596   0.03123983343027   0.01562372862048   0.00781234106010 ...
    0.00390623013197   0.00195312251648   0.00097656218956   0.00048828121119 ...
    0.00024414062015   0.00012207031189   0.00006103515617   0.00003051757812 ...
    0.00001525878906   0.00000762939453   0.00000381469727   0.00000190734863 ...
    0.00000095367432   0.00000047683716   0.00000023841858   0.00000011920929 ...
    0.00000005960464   0.00000002980232   0.00000001490116   0.00000000745058 ];
% and a table of products of reciprocal lengths of vectors [1, 2^-2j]:
% Kvalues = cumprod(1./abs(1 + 1j*2.^(-(0:23))))
Kvalues = [ ...
    0.70710678118655   0.63245553203368   0.61357199107790   0.60883391251775 ...
    0.60764825625617   0.60735177014130   0.60727764409353   0.60725911229889 ...
    0.60725447933256   0.60725332108988   0.60725303152913   0.60725295913894 ...
    0.60725294104140   0.60725293651701   0.60725293538591   0.60725293510314 ...
    0.60725293503245   0.60725293501477   0.60725293501035   0.60725293500925 ...
    0.60725293500897   0.60725293500890   0.60725293500889   0.60725293500888 ];
Kn = Kvalues(min(n, length(Kvalues)));

% Initialize loop variables:
v = [1;0]; % start with 2-vector cosine and sine of zero
poweroftwo = 1;
angle = angles(1);

% Iterations
for j = 0:n-1;
    if beta < 0
        sigma = -1;
    else
        sigma = 1;
    end
    factor = sigma * poweroftwo;
    % Note the matrix multiplication can be done using scaling by powers of two and addition subtraction
    R = [1, -factor; factor, 1];
    v = R * v; % 2-by-2 matrix multiply
    beta = beta - sigma * angle; % update the remaining angle
    poweroftwo = poweroftwo / 2;
    % update the angle from table, or eventually by just dividing by two
    if j+2 > length(angles)
        angle = angle / 2;
    else
        angle = angles(j+2);
    end
end

% Adjust length of output vector to be [cos(beta), sin(beta)]:
v = v * Kn;
return

endfunction

İkiye iki matris çarpımı , bir çift basit kaydırma ve toplama işlemiyle gerçekleştirilebilir.

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

Java'da Math sınıfının scalb(double x,int scale)böyle bir kaydırma gerçekleştirmek için bir yöntemi vardır , C'nin ldexp işlevi vardır ve x86 işlemci sınıfı fscalekayan nokta işlemine sahiptir.

Donanım örneği

Sayısı mantık kapıları bir CORDIC uygulanması için iki kaymalar ve eklemelerin kombinasyonlarını gerektiren bir çarpan için gerekli sayıda aşağı yukarı aynıdır. Çarpan tabanlı veya CORDIC tabanlı uygulama seçimi, bağlama bağlı olacaktır. Örneğin, gerçek ve sanal bileşenleri (dikdörtgen koordinatlar) tarafından temsil edilen iki karmaşık sayının çarpımı, 4 çarpım gerektirir, ancak özellikle sayıların büyüklüğü, kutupsal koordinatlarıyla temsil edilen karmaşık sayılar üzerinde çalışan tek bir CORDIC tarafından gerçekleştirilebilir. ilgili değildir (birim çemberdeki bir vektörle karmaşık bir vektörü çarpmak aslında bir dönüş anlamına gelir). CORDIC'ler genellikle dijital aşağı dönüştürücüler gibi telekomünikasyon devrelerinde kullanılır .

Çift yineleme CORDIC

Yayınlarda: http://baykov.de/CORDIC1972.htm ve http://baykov.de/CORDIC1975.htm işlevlerin uygulanması için çift ​​yineleme yönteminin kullanılması önerildi : arcsinX, arccosX, lnX, expX ve hiperbolik fonksiyonların hesaplanması için. Çift yineleme yöntemi, yineleme adımı değerinin HER zaman, yani her yinelemede değiştiği klasik CORDIC yönteminden farklı olarak, çift yineleme yönteminde yineleme adımı değerinin iki kez tekrarlanması ve yalnızca bir yineleme ile değişmesi gerçeğinden oluşur. Bu nedenle, çift yinelemeler için derece göstergesi ataması ortaya çıktı: i = 1,1,2,2,3,3... Sıradan yinelemelerde: i = 1,2,3... Çift yineleme yöntemi yakınsamayı garanti eder argüman değişikliklerinin geçerli aralığı boyunca yöntemin.

Rastgele konumsal sayı sistemi http://baykov.de/CORDIC1985.htm için CORDIC yakınsama problemlerinin Radix R ile genelleştirilmesi, sin, cos, arctg işlevleri için, (R-1) yinelemelerini gerçekleştirmenin yeterli olduğunu gösterdi. i'nin her değeri (i = 0 veya 1'den n'ye, burada n, basamak sayısıdır), yani sonucun her basamağı için. ln, exp, sh, ch, arth, R fonksiyonları için her i değeri için yinelemeler yapılmalıdır. arcsin ve arccos 2 (R-1) fonksiyonları için, her bir sayı basamağı için, yani i'nin her değeri için yinelemeler yapılmalıdır. arsh, arch işlevleri için, her bir i için, yani her sonuç basamağı için yineleme sayısı 2R olacaktır.

İlgili algoritmalar

CORDIC, Henry Briggs'in çalışmasından türetilen logaritma ve üstel algoritmalar gibi "kaydır ve ekle" algoritmaları sınıfının bir parçasıdır . Birçok temel işlevi hesaplamak için kullanılabilecek başka bir kaydırma ve ekleme algoritması , logaritma ve üstel algoritmaların karmaşık düzleme genelleştirilmesi olan BKM algoritmasıdır . Örneğin BKM sinüs ve gerçek açı kosinüs hesaplamak için kullanılabilir üssünü hesaplayarak (radyan cinsinden) olan, . BKM algoritması CORDIC'ten biraz daha karmaşıktır, ancak bir ölçekleme faktörüne ( K ) ihtiyaç duymaması avantajına sahiptir .

Ayrıca bakınız

Referanslar

daha fazla okuma

Dış bağlantılar