DÚ: Akcelerace Euklidovské normy ve 2D pomocí CORDIC

Vysvětlení problému a algoritmu

Navrhovaný modul bude umět spočítat euklidovskou normu 2D vektoru postupným zpřesňováním výsledku (tzv. iterativně), a to pouze za použití dvou sčítaček-odčítaček a dvou barrel shifterů (a jedné násobičky konstantou), pomocí algoritmu CORDIC.

Euklidovská norma

Spočítat euklidovskou normu vektoru $\vec{v}$ znamená geometricky vzato spočítat jeho skutečnou "délku" v (euklidovském) prostoru. Normu značíme $\Vert \vec{v}\Vert$ a pro 2D vektor $\vec{v}=[x,y]$ ji spočítáme pomocí Pythagorovy věty: $\Vert \vec{v}\Vert =\sqrt{x^2+y^2}$. Určovat normu vektoru je potřeba na nejrůznějších místech: v samotné matematice, ale i ve fyzice, při zpracování signálu a třeba i v počítačové grafice. Protože umocňování i odmocňování jsou náročné operace, existují algoritmy, které se k výsledku postupně dopočítají pomocí jednodušších operací. My si ukážeme algoritmus CORDIC.

COrdinate Rotation DIgital Computer (CORDIC)

Algoritmus CORDIC vzniknul v roce 1959 (ale podobné matematické techniky se používaly už v 17. století) pro výpočty při zaměřování v radarových systémech. Samotná implementace CORDICu je jednoduchá a kompaktní, proto se používá např. v kalkulačkách, a je hotová k dispozici pro všechna možná FPGA - jedná se o standardní aritmetický blok v hardwarových knihovnách.

Samotný CORDIC provádí velmi jednoduchou operaci: Na vstupech bere 2D vektor $\vec{v}$ a úhel $\Theta$, a po několika cyklech vrátí otočený vektor $\vec{v}$ o úhel $\Theta$ proti směru hodinových ručiček, viz obrázek (zdroj):

Nezní to příliš zajímavě, ale pomocí této jednoduché operace a vhodně zvolených vstupů lze s vysokou přesností spočítat hodnoty nejrůznějších "strašidelných" funkcí:
$\sin (\theta ),\cos (\theta ),\sinh (\theta ),\cosh (\theta ),a\cdot e^{\theta },\ln (a),\sqrt{a^2+b^2},\sqrt{a^2-b^2},\sqrt{a},\dots$

Princip Rotačního CORDICu

Rotace vektoru pomocí rotační matice

Otočit vektor $\vec{v}=[x_0,y_0]$ o úhel $\theta$ je velmi jednoduché, pokud umíme spočítat sin a cos a násobit vektor maticí. Vektor stačí zleva vynásobit tzv. Rotační maticí o úhel $\theta$ proti směru hodinových ručiček:

${\mathbf{R}}_{\theta }=\left[\begin{array}{cc}\cos (\theta )& -\sin (\theta )\\ \sin (\theta )& \cos (\theta )\end{array}\right]$

$\left[\begin{array}{c}x\\ y\end{array}\right]=\vec{u}={\mathbf{R}}_{\theta }\cdot \vec{v}=\left[\begin{array}{cc}\cos (\theta )& -\sin (\theta )\\ \sin (\theta )& \cos (\theta )\end{array}\right]\cdot \left[\begin{array}{c}{x}_0\\ y_0\end{array}\right]$

Tedy po roznásobení matice:

$$\begin{gathered} x=x_0\cos (\theta )-y_0\sin (\theta ) \\ y=x_0\sin (\theta )+y_0\cos (\theta ) \end{gathered}$$

Spočítat $\sin (\theta )$ a $\cos (\theta )$ pro libovolné $\theta$ je obtížné. Ale pro některé $\theta$ je to jednoduché: např. pro $\theta =\pi /2$ víme, že $\sin (\theta )=1$ a $\cos (\theta )=0$. Pokusíme se problém nějak převést na výpočet s pomocí pouze "známých úhlů", ke kterým známe odpověď.

Rozložení na více menších rotací

Pokud zvolíme nějaké $\alpha$ a $\beta$ tak, že $\theta =\alpha +\beta$, můžeme místo jedné rotace o $\theta$ provést dvě rotace za sebou: prvně o $\alpha$ a pak o $\beta$. To lze vyjádřit i pomocí rotačních matic, postupným násobením:

$\vec{u}={\mathbf{R}}_{\theta }\cdot \vec{u}={\mathbf{R}}_{\beta }\cdot ({\mathbf{R}}_{\alpha }\cdot \vec{u})$

Tento princip lze libovolně rozšířit pro $N$ malých rotací:

Pokud $\theta =\sum _{i=0}^{N-1}{\phi }_i$, pak $\vec{u}=(\prod _{i=0}^{N-1}{\mathbf{R}}_{{\phi }_i})\cdot \vec{v}$

Na následujícím obrázku (zdroj) je vidět skutečný princip CORDICu. Začínáme vektorem $V_0=[1,0]$, a chceme vektor $V_3$ otočený o $\beta =56.25^{\circ }$. Tak prvně otočíme o nějaký menší úhel ($45^{\circ }$) a dostaneme $V_1$. Pak dalším otočením ($22.5^{\circ }$) dostaneme $V_2$. Sice jsme cílový úhel přestřelili, ale to nevadí, můžeme se vrátit otočením o záporný úhel ($-11.25^{\circ }$), získáváme $V_3$. Mělo by být evidentní, že ze složek $V_3$ lze vyčíst $\sin (\beta )$ a $\cos (\beta )$, a tohle je skutečně způsob, kterým se tyto funkce pomocí CORDICu počítají. Jde pouze ilustraci, ve skutečnosti se úhly volí jiným způsobem, nicméně princip je stejný: stačí vhodně zvolit rozložení $\theta$ na ${\phi }_0,\dots ,{\phi }_{N-1}$ tak, aby šly matice ${\mathbf{R}}_{{\phi }_i}$ jednoduše spočítat.

Z celé této sekce je opravdu nejdůležitější princip algoritmu, ne nutně konkrétní matematika.

Zjednodušení rotace pouze na tangens

Chceme tedy náš vektor vynásobit několika rotačními maticemi:

$\left[\begin{array}{c}x\\ y\end{array}\right]=(\prod _{i=0}^{N-1}{\mathbf{R}}_{{\phi }_i})\cdot \vec{v}=\underset{\text{postupneˊ naˊsobenıˊ maticemi}}{\underbrace{(\prod _{i=0}^{N-1}\left[\begin{array}{cc}\cos ({\phi }_i)& -\sin ({\phi }_i)\\ \sin ({\phi }_i)& \cos ({\phi }_i)\end{array}\right])\cdot \left[\begin{array}{c}{x}_0\\ y_0\end{array}\right]}}$

Protože budeme chtít úhly ${\phi }_i$ volit vůči trigonometrickým funkcím speciálně tak, aby nám vyšlo hezké číslo, kterým se bude dobře násobit, vadí nám, že máme ve výrazu dvě různé goniometrické funkce. Tyto dvě funkce totiž pro skoro všechny vstupy mají odlišné, navíc iracionální výstupy, kterými se težko násobí.

Tento problém se dá vyřešit následujícím "trikem": z i-té matice ${\mathbf{R}}_{{\phi }_i}$ vytkneme $\cos ({\phi }_i)$:

$\left[\begin{array}{cc}\cos ({\phi }_i)& -\sin ({\phi }_i)\\ \sin ({\phi }_i)& \cos ({\phi }_i)\end{array}\right]=\cos ({\phi }_i)\cdot \left[\begin{array}{cc}\frac{\cos ({\phi }_i)}{\cos ({\phi }_i)}& -\frac{\sin ({\phi }_i)}{\cos ({\phi }_i)}\\ \frac{\sin ({\phi }_i)}{\cos ({\phi }_i)}& \frac{\cos ({\phi }_i)}{\cos ({\phi }_i)}\end{array}\right]=\cos ({\phi }_i)\cdot \left[\begin{array}{cc}1& -\tan ({\phi }_i)\\ \tan ({\phi }_i)& 1\end{array}\right]$

Teď už máme v maticích, kterými se bude náš vektor násobit, pouze $\tan ({\phi }_i)$. Zůstal nám sice $\cos ({\phi }_i)$ mimo matici, ale protože násobení matic skalárem ("číslem") je komutativní (samotné násobení matice maticí komutativní není!), můžeme všechny $\cos ({\phi }_i)$ vytknout před samotné násobení maticemi, do samostatného součinu skalárů, který si označíme $K_N$. (zdroj, zdroj, zdroj)

Dostaneme tedy:

$\left[\begin{array}{c}x\\ y\end{array}\right]=\underset{K_N}{\underbrace{(\prod _{i=0}^{N-1}\cos ({\phi }_i))}}\cdot \underset{\text{postupneˊ naˊsobenıˊ maticemi}}{\underbrace{(\prod _{i=0}^{N-1}\left[\begin{array}{cc}1& -\tan ({\phi }_i)\\ \tan ({\phi }_i)& 1\end{array}\right])\cdot \left[\begin{array}{c}{x}_0\\ y_0\end{array}\right]}}$

Levý člen $K_N$ zatím vynecháme - ukáže se, že je konstantní a vůbec nezávisí na $\theta$ ani na samotných ${\phi }_i$ - budeme ho aplikovat až úplně na konci algoritmu jako korekci.

Postupné násobení matic si rozložíme na jednotlivé mezikroky $x_0,\dots ,x_N$ a $y_0,\dots ,y_N$ a zapíšeme jako rekurenci (tj. vzorec pro (i+1)-tý člen posloupnosti na základě i-tého):

$\left[\begin{array}{c}{x}_{i+1}\\ y_{i+1}\end{array}\right]=\left[\begin{array}{cc}1& -\tan ({\phi }_i)\\ \tan ({\phi }_i)& 1\end{array}\right]\cdot \left[\begin{array}{c}{x}_i\\ y_i\end{array}\right]$

Pozn.: S pomocí této rekurence můžeme konstatovat vztah $N$-tého členu posloupnosti ke správnému výsledku:

$\left[\begin{array}{c}x\\ y\end{array}\right]=K_N\cdot \left[\begin{array}{c}{x}_N\\ y_N\end{array}\right]$

Poté rozepíšeme maticové násobení a dostaneme následující vzorce pro $x_{i+1}$ a $y_{i+1}$:

$$\begin{gathered} x_{i+1}=x_i-\tan ({\phi }_i)\cdot y_i \\ {y}_{i+1}=y_i+\tan ({\phi }_i)\cdot x_i \end{gathered}$$

Až na ten $\tan ({\phi }_i)$ tohle vypadá už docela implementovatelně. Zbývá nám tedy nějak zařídit, abychom nemuseli v hardwaru implementovat výpočet $\tan (x)$. To uděláme tak, že ${\phi }_i$ zvolíme "magicky" tak, abychom úplně bez počítání, na první pohled, věděli, kolik bude $\tan ({\phi }_i)$.

Volba vhodných úhlu pro tangens

A jak tedy zvolit ${\phi }_i$ tak, abychom hned věděli kolik je $\tan ({\phi }_i)$? Jednoduše, pomocí k $\tan$ opačné funkce $\arctan$:

Zvolme ${\phi }_i=\arctan (2^{-i})$, pak platí

$\tan ({\phi }_i)=\tan (\arctan (2^{-i}))=2^{-i}$.

Tedy pokud takto "kouzelně" zvolíme ${\phi }_i$, pak $\tan ({\phi }_i)=2^{-i}$. Např. $\tan ({\phi }_4)=2^{-4}=1/16$. Není potřeba žádný tangens počítat. Sice jsme problém tangensu jenom přesunuli jinam, protože pokud by nás zajímala skutečná hodnota ${\phi }_i$, museli bychom umět spočítat $\arctan (x)$ - ale najednou ne pro libovolný vstup, ale pouze pro konkrétní $x=2^{-i}$, kde $i$ jde od $0$ do $N-1$. To se dá udělat například předpočítáním $N$-řádkové tabulky, kterou budeme mít v nějaké paměti. My dokonce pro výpočet $\sqrt{x^2+y^2}$ skutečnou hodnotu ${\phi }_i$ znát vůbec nepotřebujeme, takže tu tabulku nepotřebovat nebudeme. Budeme totiž používat CORDIC ve vektorovém režimu popsaném níže, kde nás úhel $\theta$ a tímpádem ani konkrétní hodnoty ${\phi }_i$ nezajímají.

V tomto místě je vhodné do výpočtu vnést i zmiňovaný "směr" rotace. Pokud je ${\phi }_i$ kladné, otáčíme proti směru hodinových ručiček. Pokud je záporné, použijeme identitu $\tan (-\alpha )=-\tan (\alpha )$. Budeme tedy uvažovat, že samotný úhel ${\phi }_i$ je vždy kladný (je to pouze "velikost"), a směr budeme ovládat koeficientem $d_i\in \{-1,1\}$, kde $1$ je proti směru hodinových ručiček (dopředu) a $-1$ opačně (zpátky). Tedy pokud je směr $-1$, tak jenom prohodíme znaménka před $\tan ({\phi }_i)$ v tom vzorci, nic dalšího není potřeba měnit.

Skutečný krok CORDICu a jeho implementace

Po dosazení ${\phi }_i=\arctan (2^{-i})$ do zmíněné rekurence

$$\begin{gathered} x_{i+1}=x_i-\tan ({\phi }_i)\cdot y_i \\ {y}_{i+1}=y_i+\tan ({\phi }_i)\cdot x_i \end{gathered}$$

a zjednodušení $\tan (\arctan (2^{-i}))=2^{-i}$ a přidání směru $d_i$ tedy získáme skutečný jeden krok algoritmu CORDIC:

$$\begin{gathered} x_{i+1}=x_i-d_i\cdot 2^{-i}\cdot y_i \\ {y}_{i+1}=y_i+d_i\cdot 2^{-i}\cdot x_i \end{gathered}$$

Povšimněte si, jak dobře se tyto matematické operace budou implementovat v hardwaru. Kvůli tomu jsme všechny ty úpravy a triky dělali.

Zaprvé, násobení číslem $2^{-i}$ je to samé jako dělení číslem $2^i$. Podobně jako dělení číslem $10^i$ v desítkové soustavě je tato operace triviální - jednoduše posun o $i$ číslic, ve dvojkové soustavě o $i$ bitů (tzn. barrel shifter). Tohle je mimochodem důvod, proč jsme zvolili ${\phi }_i=\arctan (2^{-i})$, a ne něco jiného - fungovaly by i jiné hodnoty, ale hůř by se jimi násobilo.

Za druhé, protože $d_i$ je pouze $1$ nebo $-1$ a hodnotu pak ihned přičítáme/odčítáme od něčeho jiného, není potřeba nic násobit, ani nic invertovat - stačí oba dva součty/rozdíly implementovat pomocí sčítaček-odčítaček - a pouze správně (podle $d_i$) rozhodnout o tom, zda se má sčítat nebo odčítat. Jenom to pro $x_i$ bude fungovat opačně než pro $y_i$.

Určení směru rotace v každém kroku rotačního CORDICu

Jediné, co zbývá, je nějak určit ty $d_i$ tak, aby byl výsledek správně, tj., pokud se snažíme otočit o konkrétní úhel $\theta$ (to je co dělá rotační CORDIC), musíme ho nějak poskládat jako součet:

$\theta =\sum _{i=0}^{N-1}{d}_i\cdot \arctan (2^{-i})$ (fuj)

V praxi se to dělá tak, že během výpočtu, v $i$-té iteraci, koukáme, jestli je zbývající $\theta$ větší nebo menší než ${\phi }_i=\arctan (2^{-i})$ (ty taháme z tabulky v paměti), podle toho určíme $d_i$, a pak ${\phi }_i$ od $\theta$ odečteme, a se zbytkem pokračujeme dál do příští iterace. Tedy pro výpočet $\sin$ a $\cos$ pomocí CORDICu je potřeba tabulka ${\phi }_i$, a právě kvůli tomu jsem vám záměrně zadal místo $\sin$ nebo $\cos$ právě výpočet normy, kde taková tabulka potřeba není.

Škálování výsledku

Pokud se rozhodneme pro $N$ iterací algoritmu, začneme s hodnotami $[x_0,y_0]$ (ze vstupu), a budeme iterovat, dokud nezískáme $[x_N,y_N]$. Hodnota $[x_N,y_N]$ v určitém smyslu reprezentuje náš výsledek, ale zatím není úplný. Musíme do výsledku ještě zahrnout konstantní člen kosinů:

$x=\underset{K_N}{\underbrace{(\prod _{i=0}^{N-1}\cos ({\phi }_i))}}\cdot x_N$

Tento člen $K_N$ koriguje skutečnost, že během "zjednodušeného" CORDIC algoritmu, kde jsme cosiny vynechali, se nám výsledek postupně více a více "natahuje" o faktor $1/K_N$. Ovšem my umíme $K_N$ spočítat, a vynásobíme jím náš výsledek abychom ho zase "zkrátili" na správnou velikost:

$K_N=\prod _{i=0}^{N-1}\cos ({\phi }_i)=1/(\prod _{i=0}^{N-1}\sqrt{1+2^{-2i}})$

Pro konkrétní $N$ iterací je vhodné použít přesně $K_N$, protože to přesně odpovídá natažení, které způsobilo těch $N$ iterací. Ovšem pro $N>10$ je mezi jednotlivými $K_N$ už velmi malý rozdíl, proto často stačí jednoduše použít limitu $K_{\infty }$:

$K_{\infty }=\underset{N\to \infty }{\lim }{K}_N\approx 0.6072529350088812561694$

Jakmile máme vhodné $K_N$, které je konstantní pro CORDIC s konstantním počtem iterací, stačí naše vypočítané $x_N$ přeškálovat pomocí $K_N$, čímž konečně získáme výsledek.

$x=K_N\cdot x_N$

Zde je potřeba násobit - ovšem násobení konstantou lze implementovat efektivněji než obecné násobení, a násobit je potřeba pouze jednou, na konci algoritmu - násobení v tomto případě není bottleneck.

Vektorový CORDIC

U rotačního CORDICu se algoritmus snažil vektor otočit o konkrétní úhel. CORDIC lze ale použít i jinak, ve vektorovém režimu. Ten se snaží vstupní vektor natočit určitým směrem, a výstup je kromě otočeného vektoru i úhel, o který bylo potřeba vektor otočit (pokud nás zajímá). Standardně se provádí otáčení do směru vektoru $\overrightarrow{e_x}=[1,0]$ (tj. na osu X), protože se jednoduše implementuje.

Vektorový CORDIC dostane na vstupu vektor s nenulovým $y$, a snaží se ho postupně "sklopit" do vodorovné polohy na ose X tím, že se snaží dostat $y$ vektoru na nulu. To je jednodušší než rotační CORDIC - vektor otáčíme v $i$-tém kroku o úhel ${\phi }_i$, ale vždy jednoduše směrem k ose X: Pokud je $y>0$, tak po směru hodinových ručiček ("dolů", $d_i=-1$), a pokud $y<0$, tak proti směru ("nahoru", $d_i=1$), viz následující obrázek (zdroj):

Výpočet normy pomocí vektorového CORDICu

Pokud vektor $\vec{v}=[x_0,y_0]$ otočíme tak, aby byl vodorovně s osou X ($y=0$), dostaneme právě vektor $\vec{u}=[\sqrt{x_0^2+y_0^2},0]$, což vychází z podobnosti trojúhelníků, viz obrázek:

Stačí tedy na zadaný vstupní vektor pustit vektorový CORDIC, a v souřadnici $x$ výsledného vektoru nalezneme "skoro" normu. Tu jenom přenásobíme $K_N$, což nám dá skutečnou normu vstupního vektoru:

$\vec{v}=[x_0,y_0]$

$[x_N,y_N]={\text{VectorCORDIC}}_N(\vec{v})$

Nyní platí $y_N\approx 0$

$\Vert \vec{v}\Vert =\sqrt{x_0^2+y_0^2}=K_N\cdot x_N$

Příklad výpočtu normy

Mějme $\vec{v}=[4,3]$, stejně jako na obrázku výše. Norma je $\Vert \vec{v}\Vert =\sqrt{x_0^2+y_0^2}=\sqrt{4^2+3^2}=\sqrt{25}=5$. Pojďme se podívat, jestli CORDIC dospěje ke stejnému závěru:

Všimněte si, jak rychle se CORDIC přiblížil ke správnému výsledku (tedy po přenásobení $K_i$). Obecně platí, že každá iterace CORDICU zvětší přesnost výsledku o 1 bit (pokud máme dost přesnou sčítačku atd.). Standardně tedy pokud CORDIC interně pracuje s 32-bitovými čísly, bude se používat cca. $N=32$ iterací, po nich už bude celý 32bit výsledek velmi přesný.

Desetinné čísla ve dvojkové soustavě

Protože CORDIC potřebuje pracovat s desetinnými čísly, musíme je nějak reprezentovat pomocí bitů. V praxi, např. při programování, jste se nejspíš setkali s čísly s plovoucí řádovou čárkou (floating-point numbers), nejspíš ve formě datových typů float a double. Ty jsou super, protože umí reprezentovat zároveň obrovská čísla a také velmi přesně čísla velmi blízko k nule, ovšem pro naše využití jsou zbytečně komplikované. Nám budou stačit čísla s tzv. pevnou řádovou čárkou (fixed-point numbers). Sice mají nějaké nedostatky, obzvlášť omezenou přesnost, ale zase je práce s nimi drasticky jednodušší.

Fixed-point numbers

Jak napovídá název, ve fixed-point desetinném čísle je na nějakém místě zafixovaná desetinná čárka, viz obrázek (zdroj).

Tato desetinná čárka se neukládá, je vlastností zvoleného číselného formátu. V obrázku tedy například pracujeme s čísly Q5.3: máme 5 bitů před čárkou a 3 bity za čárkou, dohromady 8 bitů. "Na drátě" existuje pouze těch 8 bitů, bez jakékoliv informace o tom, co znamenají, tj. jak se mají správně interpretovat. To je popsané někde v dokumentaci a ovlivňuje to, jak budeme s číslem pracovat.

Hodnotu čísla $00010.110_2$ můžeme chápat jako $00010_2+110_2\cdot 2^{-3}$. V této reprezentaci se už vyskytují pouze celé binární čísla, a po převedení do desítkové soustavy dostaneme $2+6/8=2.75$.

Existuje i jiný způsob přemýšlení o fixed-point číslech. Jak jistě víte, násobením $2^n$ můžeme posouvat desetinnou čárku doleva nebo doprava (násobíme nebo dělíme řádem, funguje to úplně stejně v desítkové soustavě pro $10^n$). Tedy místo $00010.110_2$ můžeme psát $00010110_2\cdot 2^{-3}$. Pracujeme tedy s číslem $00010110_2$ (to jsou surové bity tohoto fixed-point čísla na drátě), ale bokem si "pamatujeme", že toto číslo je $2^3$-krát větší než opravdová hodnota. Tohle je, jak budeme k fixed-point číslům přistupovat my, protože nás to nechá se k nim chovat prostě jako k celým číslům, až do momentu, kdy je potřebujeme ukázat uživateli (v ten moment musíme umístit na správné místo desetinnou čárku).

Operace s fixed-point čísly

Pokud chci sečíst dvě fixed-point čísla stejného typu, stačí je reprezentovat výše zmíněným způsobem a vytknout těch $2^{-n}$:

$a\cdot 2^{-n}+b\cdot 2^{-n}=(a+b)\cdot 2^{-n}$

Z toho plyne, že můžeme prostě sčítat bitové reprezentace stejných fixed-point čísel a dostaneme správné fixed-point číslo stejného typu.

U násobení budeme muset provést drobnou úpravu, protože budeme mít ve výrazu přebytečné $2^{-n}$:

$(a\cdot 2^{-n})\cdot (b\cdot 2^{-n})=(a\cdot b\cdot 2^{-n})\cdot 2^{-n}$

Tedy po klasickém celočíselném vynásobení $a\cdot b$ musíme jedno násobení $2^{-n}$ aplikovat: posuneme výslednou hodnotu o $n$ bitů doprava (protože exponent je záporný). Tím dostaneme $a\cdot b\cdot 2^{-n}$, což je správná reprezentace výsledku ve fixed-point číslech.

Zmiňované operace lze navrhnout i pro čísla různých typů, ale my budeme v celém obvodu pracovat pouze s čísly jednoho jediného fixed-point typu, Q12.16 (12 bitů před a 16 bitů za desetinnou čárkou = 28 bitů). Pro případ Q12.16 je $n=16$ a tedy pracujeme s čísly v podobě $a\cdot 2^{-16}$.

Záporná fixed-point čísla

Určitě jste zaznamenali, že CORDIC potřebuje pracovat i se zápornými čísly, musíme tedy naše fixed-point obohatit o znaménko, abychom měli čísla se znaménkem. To se dělá velmi jednoduše, stačí říct, že v našem desetinném čísle $a\cdot 2^{-n}$ je $a$ reprezentováno ve dvojkovém doplňku. Dostáváme tedy něco, čemu můžeme říkat two's-complement signed fixed-point.

Pokud už si nepamatujete, jak funguje dvojkový doplňek, doporučuji si znovu projít příslušnou kapitolu skript. Nejdůležitější potřebné skutečnosti pro práci s ním shrnu tady:

• $-A=\overline{A}+1$. To stačí udělat na celou reprezentaci fixed-point čísla bez ohledu na jeho typ, protože platí, že $-(a\cdot 2^{-n})=(-a)\cdot 2^{-n}$. Z toho vyplývá i, že odčítání fixed-point čísel funguje identicky jako odčítání celých čísel (skripta).
• Nejvyšší bit čísla je znaménko. Platí pro libovolné fixed-point číslo, nehledě na typ.
• Násobení $2^n$ odpovídá shiftu doleva. Pokud vypadnou shiftem zleva nějaké nenulové bity, dochází k přetečení a výsledek nelze reprezentovat. Zprava hodnotu doplňujeme nulami.
• !!! Násobení $2^{-n}$ (tedy dělení $2^n$) odpovídá aritmetickému shiftu doprava. Ten se chová odlišně od logického (kde se doplňuje nulami). Při aritmetickém shiftu musí zůstat znaménko čísla zachované, tzn. bity zleva se doplňují hodnotou znaménka (a NE nulami!). Tedy pro kladná čísla se doplňuje nulami (sign bit je nula) a pro záporná čísla se doplňuje jedničkami (sign bit je 1). Více detailů a diagram je na wikipedii. Bity, které vypadávají zprava, pokud jsou jedničkové, znamenají ztrátu přesnosti (zaokrouhlení výsledku), ale to neznamená, že výsledek je nesprávný, jenom je nepřesný. V Logisimu můžete použít Shifter, pokud ho správně nastavíte.
• Čísla ve dvojkovém doplňku nelze přímo násobit!!! Jak se to implementuje, aby to fungovalo, neprobíráme. V Logisimu můžete použít Multiplier v režimu 2's Complement.

V Logisimu

V Logisimu žádná konkrétní podpora pro fixed-point čísla není, budete muset správně manipulovat jejich bitovou reprezentaci (není to těžké). Ale, Logisim umí zobrazovat floating-point čísla. V projektovém souboru máte připravené moduly Q12_16_tofloat a Q12_16_fromfloat, které konvertují mezi reprezentací Q12.16 a 32-bit floating-point čísly. Pomocí nich, a inputů/outputů/probes s nastaveným radixem "Float" můžete při testování zadávat hodnotu jako (nepřesné) desetinné číslo, a také si ho jako desetinné číslo nechat zobrazit. To hodně pomahá, pokud se snažíte odladit, při kterém kroku váš modul udělal výpočetní chybu. Konverze z/do floatů jsou pouze přibližné, měli byste obvod otestovat i přímo poskytnutými testovacími vektory v Q12.16 formátu a ujistit se, že dostáváte úplně přesný výsledek.

Specifikace modulu

Struktura a chování

• Plně sekvenční modul, synchronizovaný na nábežné hraně
• Vstupy X_IN a Y_IN výstup OUTP
  • V signed two's-complement fixed-point formátu Q12.16 (28 bitů)
  • Výstup bude vzhledem k povaze výpočtu vždy kladný, ale stejně bude v signed formátu
• Vstupy START, CLK a výstup DONE tvoří start-done interface modulu
• Na výstupy DEBUG_X a DEBUG_Y přiveďte aktuální stav vašich registrů pro $X$ a $Y$, ve kterých provádíte mezivýpočty, aby bylo zvenku vidět, co modul dělá. Hodnota těchto výstupů se nekontroluje, slouží pouze pro ladění.
• Modul spočítá $\text{OUTP}=\sqrt{{\text{X}}_{\text{IN}}^2+{\text{Y}}_{\text{IN}}^2}$ pomocí CORDIC algoritmu
• Po jednom úvodním načítacím cyklu (start=1) modul provede přesně 28 iterací CORDIC algoritmu
  • Výsledek 28. iterace CORDICu $x_{28}$ je potřeba přenásobit konstantou $K_{28}$ (stačí kombinačně na výstupu z modulu)
  • Použijte hodnotu $K_{28}=\mathrm{0.6072529350...}$ zaokrouhlenou do formátu Q12.16:
    $K_{28}\approx {\text{0.1001101101110101}}_2={\text{00.9B75}}_{16}$
  • Tato hodnota je ve skutečnosti přesně $0.6072540283_{10}$, ale to je ke $K_{28}$ dostatečně blízko
• Modul se bude jmenovat NORM
• Používejte logisimové matematické operátory
  • Pro implementaci stačí dvě sčítačky/odčítačky (můžete pro jednoduchost použít i separátní sčítačku+odčítačku+multiplexor), dva shiftery a jedna násobička. Pokud toho potřebujete víc, zkuste se vrátit k zadání.

Časování

Modul je plně synchronní, reaguje na vstup a mění svůj výstup tedy pouze s náběžnou hranou vstupu clk. Modul používá standardní start-done interface, jak jsme ho probírali. Po skončení výpočtu (done=1) výsledek musí zůstat konstantní až do příštího start=1. Detailní popis níže.

Standardní start-done interface

Pokud je na vstupu start=1, načte modul vstupy a připraví se na výpočet (toto může nastat i během již probíhajícího předchozího výpočtu, v takovém případě se tento výpočet ruší a připraví se nový podle vstupů). "Příprava na výpočet" může znamenat různé věci: pouhé uložení vstupních hodnot do registrů, nebo přímo provedení prvního kroku výpočtu podle vstupů a uložení částečného výsledku do registrů. V každém případě by se ale měla inicializovat řídící část obvodu - pokud obvod provádí výpočet v nějakých "krocích", nebo má v registrech jiné poznámky o výpočtu, je potřeba tyto inicializovat na hodnoty, které umožní začít výpočet od začátku.

Jakmile start=0, provede modul s každým clockem jeden krok výpočtu. Během tohoto musí být výstup done=0. Modul může počítat s tím, že po celou dobu jednoho výpočtu zůstanou vstupy A a B konstatní. Jakmile modul dokončil výpočet a na výstupu OUTP prezentuje správný výsledek, musí přestat počítat (výsledek musí zůstat konstantní, dokud nepřijde další start=1 signál). Zároveň toto musí indikovat pomocí done=1.

Postup řešení

U celého vašeho řešení se bude hodnotit čitelnost a srozumitelnost - vše co odevzdáváte kromě řešení slouží jako dokumentace k projektu. Pokud vám dokumentace přijde nepřehledná, je nutné ji přepsat, přepracovat, nebo překleslit, aby byla. Toto platí obzvlášť pro diagram - např. škrtání a matoucí věci v diagramu budou penalizovány.

Pokud budete pracovat na papír, použijte kontrastní propisku, ne slabou tužku, a výsledek buď naskenujte, nebo s dobrým osvětlením, kolmo a ve vysokém rozlišení vyfoťte (vyhněte se tvrdým stínům ve fotce), a upravte, aby vypadal jako naskenovaný, zejména proveďte korekci zkosení (pro tento účel lze použít např. aplikaci Microsoft Lens, dříve Office Lens, na telefony). Odevzdání v nízké kvalitě (jak rozlišení tak vizuálně) bude vráceno k přepracování.

1. Zadání

Přečtěte si zadání, ujistěte se, že rozumíte CORDICu, postupu výpočtu, desetinným číslům a záporným číslům. Pochopení těchto konceptů může být zkoušeno v rámci hodnocení domácího úkolu.

2. Teoretická příprava

Buď na papír nebo digitálně (bude součástí odevzdání) si připravte (jako v předchozích úlohách)

1. Stručný popis algoritmu, ať máte ujasněné, co implementujete. Tento popis je oproti uvedené teorii velmi jednoduchý, to je záměrně (úloha je navžená tak, aby byla implementace jednoduchá).
2. Seznam registrů (stavu), jejich velikosti, stručný popis jejich funkce, pokud to není evidentní.
3. Popis zápisů do registrů za určitých podmínek (při start=1, při done=0, etc.). Použijte syntaxi z předchozích úloh a obecně zažité výrazy/konstrukce z číslicového návrhu nebo programování. Cokoliv nejasného popište.
4. Detailní simulaci příkladu nemusíte provádět, ani to moc bez programování nejde, stačí aby vám bylo jasno, jak zjistit že proběhlo přesně 16 iterací CORDICu. Pokud necháte proběhnout 15 nebo 17 iterací, nedostanete správný výsledek.
5. Pro každý stavový registr rozepište, jaké různé hodnoty je potřeba do něj umět uložit.
6. Uveďte, jak z aktuálního stavu vypočítáváte všechny kontrolní i datové signály, např. DONE, OUTP, všechny write-enably, a cokoliv jiného pojmenovaného, co používáte v popisu chování.

3. Blokový diagram

Buď na papír nebo digitálně (buď tabletem s tužkou nebo např. pomocí draw.io) nakreslete blokový diagram zapojení obvodu. Diagram musí odpovídat běžným elektronickým diagramům.

Zejména upozorňuji na:

1. Datovou cestu se snažte zapojit přímým napojováním drátů, bez tunelů
2. Pro kontrolní signály používejte tunely (pojmenované odkazy na jiné vodiče)
3. U vícebitových drátů/registrů označte zavedeným způsobem šířku (počet bitů)
4. V blokovém diagramu mohou být operace a bloky víc "high level" - jde o chování, ne o konkrétní způsob implementace (např. násobění dvěma v diagramu by se pak implementovalo shifterem)
5. Diagram musí být přehledný (bez škrtání atd.) a smysluplně rozvržený - má sloužit jako dokumentace. Pokud je nepřehledný, musíte ho překreslit. Dokonce se dá počítat s tím, že vaše první iterace nebude dostatečně přehledná, a budete odevzdávat až druhou/třetí verzi.
6. Označte všechny clock vstupy zavedeným symbolem. Dále není v diagramu potřeba clocky spojovat, clocky se předpokládají vždy spojené.

4. Zapojení v Logisimu

Stáhněte si 🔗 template pro tento úkol a do předpřipraveného modulu NORM podle vašeho blokového diagramu postavte řešení. Dbejte na následující:

• Upravujte pouze modul NORM, modifikace ostatních modulů budou při odevzdání zahozeny!
• V datové cestě modulu použijte:
  • 2x připravený modul ADDSUB
  • 1x Logisimovou celočíselnou 28-bitovou násobičku
  • Libovolný počet Logisimových shifterů (libovolné nastavení)
  • Libovolný počet Logisimových sčítaček jako inkrementorů
  • Libovolný počet Logisimových komparátorů pro rozhodování
  • Žádná další aritmetika není pro datovou cestu potřeba!
• Snažte se, aby struktura vaší Logisimové implementace (hlavně datové cesty) odpovídala vašemu blokovému diagramu (stavte to podle něj!)
• Není potřeba vytvářet žádné další moduly, všechno stačí zapojit do NORM
• Pro debuggování můžete používat připravenou sadu Q12_16_* modulů spolu s Logisimovou Probe nastavenou na Radix Float - nechá vás to sledovat skutečnou (ale nepřesnou, kvůli konverzi na float) hodnotu fixed-point drátů živě, aniž byste museli ručně konvertovat. Příklad použití je v modulu main.
• Testujte svůj modul proti testovacím vektorům v modulu main.
• Před odevzdáním na svůj modul pusťte testovací baterii připravenou v modulu NORM_TEST_BATTERY, případně můžete zkusit jeden test ručně pomocí modulu NORM_GOLDEN_TEST. Červeně jsou vyznačeny parametry testu, které můžete měnit.

Ujistěte se, že jste nezměnili externí interface modulu NORM. Měl by vypadat následovně:

5. Testování

Váš modul otestujte v main pomocí (některých z) následujících testovacích vektorů. Nemusíte mít výsledek úplně přesně jako je zde uvedeno, ale neměl by se lišit o více než 0.01%. V OUTPUT_ACTUAL jsem uvedl výsledek z mojí implementace. Pozn.: tyto testovací hodnoty odpovídají těm v modulu NORM_TEST_BATTERY.

Zde uvádím tabulku kompletního průběhu příkladu X=3 Y=4 na mé implementaci. Opět připomínám, že stačí, aby vaše hodnoty byly blízko k těm mým, s dostatečnou přesností.

Test včetně kontroly přesnosti lze provést v modulu NORM_GOLDEN_TEST. Přesnost tam je zadaná jako 0x64 miliontin, což je 0.01%.

Finálně na svůj modul pusťte baterii testů v NORM_TEST_BATTERY a ověřte počet PASS/FAIL/TIMEOUT. Pokud budete mít nějaké selhání, můžete si nastavit konstantu tak, aby se tester zastavil. Proklikáním do modulů se pak můžete podívat na vaše hodnoty vs. očekávané, spočítanou chybu v přesnosti, a získat vstupy X a Y pro další debuggování selhávajícího příkladu. Pozn.: Odevzdávač testuje právě tuto baterii testů.

6. Odevzdávání

Nejspíše na Submitty, Logisim se bude kontrolovat automaticky, zbytek (přípravu na papír) budu hodnotit ručně. TBA.

FAQ

V případě, že máte nějakou otázku, se určitě neváhejte co nejdříve ptát. Pokud bude odpověď užitečná pro všechny, přidám ji zde do FAQ.

• TBA