Low complexity algorithms and architectures for odd-type DCT hardware implementation

Il lavoro di tesi è incentrato sulla Trasformata Discreta del Coseno di tipo V (DCT5). Tale trasformata ha acquisito notevole interesse nel contesto degli standard di codifica video post-HEVC. In particolare, la DCT5 è stata introdotta nel software JEM sviluppato dal Joint Video Experts Team (JVET). Nella parte iniziale della tesi viene richiamata la definizione della DCT5 e nel seguito si procede alla derivazione di algoritmi che ne consentono il calcolo in modo efficiente. Più in dettaglio, la DCT5 è inizialmente espressa in funzione della Trasformata Discreta di Fourier (DFT). Infatti, viene dimostrato che una DCT5 di lunghezza N può essere ricondotta ad una DFT di lunghezza (2N-1). Si procede pertanto ad analizzare gli algoritmi per la DFT ed ad apportare a questi ultimi delle semplificazioni in modo da ridurre la complessità computazionale. Il primo algoritmo che viene considerato è il Winograd Fourier Transform Algorithm. Quest'ultimo viene analizzato sia nel caso in cui la lunghezza della DFT sia un numero primo, sia nel caso in cui la lunghezza della DFT possa essere fattorizzata come prodotto di numeri primi. Successivamente viene considerato il Prime Factor Algorithm ed infine sono stimate le performance degli algoritmi di Rader e Bluestein. Facendo riferimento a degli articoli esistenti, si procede poi ad esprimere la DCT5 in funzione di una Trasformata Discreta del Coseno di tipo II (DCT2). Anche in questo caso, i ben noti algoritmi per la DCT2 sono adattati al fine di consentire il calcolo efficiente della DCT5. La DCT5 è anche calcolata per mezzo delle Givens Rotations ed infine, viene presentata una fattorizzazione della DCT5 riportata in un articolo pubblicato prima della stesura di tale lavoro di tesi. Tutti gli algoritmi sono sviluppati per lunghezze della DCT5 pari a 4,8,16 e 32. Tali lunghezze sono infatti quelle che hanno maggior rilievo nel software JEM. Inoltre viene eseguita una comparazione degli algoritmi per ciò che concerne la complessità computazionale, la regolarità e la presenza di moltiplicatori in cascata. Tra gli algoritmi presentati, assume particolare importanza quello derivato da un articolo, pubblicato da Selesnick e Burrus, che descrive come calcolare in modo efficiente una DFT su 31 punti. Eseguendo delle semplificazioni, tale algoritmo è adattato al calcolo di una DCT5 su 16 punti. La versione floating point dell'algoritmo è quindi utilizzata per derivare il modello C in fixed-point. Il modello C viene dunque inserito all'interno del software JEM e le performance sono stimate facendo riferimento al delta di Bjøntegaard. Viene infine sviluppata e sintetizzata un'architettura le cui performance sono stimate in termini di frequenza, area e consumo di potenza.