Operazioni in virgola fissa - somma, prodotto e riallineamento

In un processore a virgola fissa (Virgola fissa - formati n.m e normalizzazioneIn virgola fissa il processore fa aritmetica sugli interi (con segno) e il fattore di scalacostante per cui si moltiplica un valore reale per ottenere l'intero memorizzato $2^{m}$ resta sottinteso: il formato n.m dice che dei bit disponibili $n$ sono la parte intera (compreso il segno se il numero è con segno, S; nessun segno se U) e $m$ la parte frazionaria. Il valore è $\text{codice}/2^m$. Passare dal formato n.m al decimale, o viceversa, è il calcolo più frequente dell'esame: su 16 bit $\text{valore}=\text{codice}/2^m$, l'intervallo è $[0,2^n)$ (U) oppure $[-2^{n-1},2^{n-1})$ (S), la risoluzione è $2^{-m}$.Virgola fissa - formati n.m e normalizzazione →) l'ALUunità aritmetico-logica: il circuito che esegue somme, prodotti e operazioni logiche esegue somme e prodotti tra interi. Che quegli interi rappresentino frazioni, con una certa virgola implicita, è una convenzione del programmatore: il processore non allineaporta i due dati allo stesso numero di bit frazionari, spostando la virgola implicita le virgole da solo. Questa nota spiega come mantenere coerente la convenzione. Il programmatore deve dichiarare i formati scelti nel codice.

La somma

Due dati $a=C_a/2^{m_a}$ e $b=C_b/2^{m_b}$ si sommano correttamente solo se $m_a=m_b$: allora $a+b=\frac{C_a+C_b}{2^m}$. Se i formati sono diversi si allinea il dato con meno bit frazionari spostandolo a sinistra di $m_a-m_b$ posti (oppure si sposta a destra l'altro, perdendo risoluzione). Prima di ogni somma conviene chiedersi: "i due addendi hanno lo stesso peso per bit?".

Nella somma c'è anche il problema di overflowrisultato fuori dall'intervallo rappresentabile: dopo la somma di due dati nell'intervallo $[-1,1)$ il risultato può stare in $[-2,2)$. Si evita con una scelta del formato che lasci un margine (bit interi in più), oppure con l'aritmetica saturatail risultato viene limitato al massimo o al minimo rappresentabile invece di avvolgersi.

Il prodotto

Se $P=C_P/2^{m_1}$ e $Q=C_Q/2^{m_2}$, il prodotto degli interi è $$C_P\,C_Q=2^{m_1+m_2}\,PQ .$$ Quindi il fattore di scala del prodotto è il prodotto dei fattori di scala: i bit frazionari si sommano. Inoltre il risultato richiede il doppio dei bit (due parole da $W$ bit danno un risultato da $2W$): per questo gli acceleratori hardware hanno un accumulatoreregistro a larghezza doppia dove si raccolgono prodotti e somme senza perdere bit a $2W$ bit.

Per riportare il risultato al formato $n.m$ di un dato con $m$ bit frazionari bisogna togliere $m_1+m_2-m$ bit frazionari: uno shiftscorrimento dei bit di una parola verso destra o verso sinistra aritmetico a destra di $m_1+m_2-m$ posti (aritmetico per un valore con segno, per estendere il segno). Se $m_1=m_2=m$ la quantità da togliere è $m$: si prende la parte alta della parola a $2W$ bit (un'operazione che coincide con uno shift a destra di $m$ posti). Questo scarto è un troncamentoeliminazione dei bit bassi senza arrotondare interno all'algoritmo, quindi una piccola fonte di errore (Quantizzazione, fattori di scala e cicli limiteUn algoritmo di filtro o regolatore pensato per un processore ideale va adattato alla realtà: temporizzazionedistribuzione nel tempo delle operazioni di un algoritmo (l'algoritmo nella ISR dell'ADC, durata minore di $T_c$), acquisizione (condizionamento del segnale per sfruttare tutto il fondo scala dell'ADC), fattori di scala (normalizzazione intera o 1.15; evitare overflow), quantizzazione di ingresso, uscita, coefficienti e prodotti (sposta i poli, genera errori a regime e cicli limite). Una frequenza di campionamento troppo alta rende più critica la quantizzazione dei coefficienti: va scelta coerente con la lunghezza di parola.Quantizzazione, fattori di scala e cicli limite →).

Prodotto in normalizzazione 1.15

Con $a,b$ in 1.15 S, $a=C_a/2^{15}$, $b=C_b/2^{15}$: $C_aC_b=ab\cdot2^{30}$, cioè il prodotto è in formato 2.30 (il primo bit è di segno esteso). Ma il risultato è ancora una frazione in $[-1,1)$ (salvo il caso $-1\cdot-1$), quindi il formato naturale sarebbe 1.31: si ottiene con uno shift a sinistra di 1. I DSP e molti µC fanno questo shift in automatico nella modalità frazionariafunzionamento del moltiplicatore che dopo il prodotto sposta a sinistra di un bit per riportare il formato 2.30 a 1.31 del moltiplicatore, mentre nella modalità intera non lo fanno. La parte altai W bit più significativi di una parola a 2W bit (bit 31-16) del risultato shiftato è il prodotto in 1.15. Esempio: $0{,}5\cdot0{,}5$: $\texttt{0x4000}\cdot\texttt{0x4000}=\texttt{0x10000000}$ (2.30), dopo lo shift $\texttt{0x20000000}$ (1.31), parte alta $\texttt{0x2000}=0{,}25$ ✓.

Esempio con dati senza segno (0.16)

$\texttt{0x4000}$ in 0.16 U vale $0{,}25$ e $\texttt{0xA000}$ vale $0{,}625$. Il prodotto intero a 32 bit è $\texttt{0x28000000}$; il risultato atteso nella stessa normalizzazionescelta del fattore di scala, cioè di dove sta la virgola, per un dato 0.16 è $0{,}25\cdot0{,}625=0{,}15625=\texttt{0x2800}$ ($0{,}15625\cdot65536=10240$). Si ottiene spostando a destra di 16 posizioni: $\texttt{0x28000000}\gg16=\texttt{0x2800}$ ✓. In generale, premoltiplicaremoltiplicare un coefficiente per una costante prima dell'uso, per renderlo intero due dati per $2^p$ dà un prodotto per $2^{2p}$; uno shift a destra di $p$ lo riporta a $2^p$ (la scala degli operandi).

Scelta dei fattori di scala

Il problema esiste solo nei processori a virgola fissa. Una scelta sbagliata porta a overflow (di solito rende il codice inutilizzabile) o a un cattivo uso dell'aritmetica (quantizzazionesostituzione di un valore con uno dei valori rappresentabili, con un piccolo errore).

Caso 1: normalizzazione intera. Calcolare $y=a\,x+b$ con $a=0{,}12$, $b=60$, $x=1350$ (atteso $y=222$). Il coefficiente $a<1$ non è rappresentabile come intero: si premoltiplica per una potenza di 2 grande, per esempio 1024, e si arrotonda: $a'=\mathrm{round}(0{,}12\cdot1024)=123$ (errore di arrotondamento: vale $0{,}1201$ invece di $0{,}12$). Il prodotto vale $a'x=166050$, in scala $1024$: prima di sommare $b$ (che è in scala 1) si divide per 1024 con uno shift a destra di 10 posti: $166050\gg10=162$. Quindi $y=162+60=222$ ✓ (il valore esatto è $0{,}12\cdot1350+60=222$). Un fattore di scala grande minimizza l'errore di arrotondamento del coefficiente: se si fosse usato 16, $a'=\mathrm{round}(1{,}92)=2$ e l'errore sarebbe stato enorme; ma non può essere troppo grande o il prodotto va in overflow.

Caso 2: normalizzazione 1.15. Calcolare $y=a\,x+b$ con $a=3{,}5$, $b=0{,}2$, $x=0{,}2$ (atteso $0{,}9$). Il coefficiente $a>1$ non è rappresentabile in 1.15: si predividedivide un coefficiente per una costante prima dell'uso, per renderlo minore di 1 per una potenza di 2, per esempio 4: $a'=a/4=0{,}875=\texttt{0x7000}$. Il prodotto $a'x$ (in 1.15, con $x=\texttt{0x199A}$) è $\texttt{0x1666}=0{,}175$; prima di sommare $b$ si moltiplica per 4 (shift a sinistra di 2): $0{,}7$; con $b=\texttt{0x199A}$ si ottiene $\texttt{0x7332}=0{,}89996$ ✓.

Regole pratiche:

• scegliere normalizzazioni che non diano overflow nel caso peggiore;
• prima di ogni somma, controllare che gli addendi siano in scala uguale;
• dopo ogni prodotto, riportare il risultato al formato dell'accumulatore o del registro di destinazione;
• usare la normalizzazione 1.15 quando possibile: il prodotto di due frazioni è una frazione e non va in overflow; gli interi maggiori di 1 si gestiscono con fattori di scala in potenza di 2 (shift).

Errori comuni

• Dimenticare lo shift dopo il prodotto: il risultato è $2^{m}$ volte troppo grande.
• Fare lo shift logico al posto dell'aritmetico per un valore negativo.
• Sommare un prodotto non riallineato a un dato in scala diversa.
• Scegliere un fattore di scala piccolo e poi stupirsi dell'errore sul coefficiente.