Discrete cosine transform algorithms for FPGA devices

Babić, Domagoj

No public access

scientific master's theses

1 0

Discrete cosine transform algorithms for FPGA devices

Domagoj Babić (2003)

University of Zagreb
Faculty of Electrical Engineering and Computing

Cite this document...

APA 6th Edition

Babić, D. (2003). Discrete cosine transform algorithms for FPGA devices (Scientific master's theses). Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:756032

MLA 8th Edition

Babić, Domagoj. "Discrete cosine transform algorithms for FPGA devices." Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, 2003. https://urn.nsk.hr/urn:nbn:hr:168:756032

Chicago 17th Edition

Harvard

Babić, D. (2003). 'Discrete cosine transform algorithms for FPGA devices', Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 25 August 2019, https://urn.nsk.hr/urn:nbn:hr:168:756032

Vancouver

Babić D. Discrete cosine transform algorithms for FPGA devices [Scientific master's theses]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2003 [cited 2019 August 25] Available at: https://urn.nsk.hr/urn:nbn:hr:168:756032

IEEE

D. Babić, "Discrete cosine transform algorithms for FPGA devices", Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2003. Available at: https://urn.nsk.hr/urn:nbn:hr:168:756032

Cite this item: https://urn.nsk.hr/urn:nbn:hr:168:756032

Metadata

Title	Discrete cosine transform algorithms for FPGA devices
Title (croatian)	Algoritmi za diskretnu kosinusnu transformaciju za FPGA sklopove
Author	Domagoj Babić
Mentor	Mario Kovač (mentor)
Committee member	Mario Kovač (predsjednik povjerenstva)
Granter	University of Zagreb Faculty of Electrical Engineering and Computing Zagreb
Defense date and country	2003, Croatia
Scientific / art field, discipline and subdiscipline	TECHNICAL SCIENCES Computing
Universal decimal classification (UDC)	004 GENERALLY Computer science and technology. Computing. Data processing
Abstract	Polynomial transform was presented as an efficient way to map multidimensional transforms (like DCT and DFT) and convolutions to onedimensional ones. Resulting algorithms have significantly lower computational complexity, especially for convolutions and DCT. If optimal one-dimensional DCT would be available, it would be possible to obtain optimal multidimensional algorithms by using polynomial transforms. As demonstrated in the thesis, polynomial transform based DCT can be implemented in significantly less logic resources than row-column distributed arithmetic algorithm. Polynomial transform computation is performed as the series of additions and subtractions, so the finite-register length effects can be avoided resulting in higher accuracy. Second dimension of distributed arithmetic DCT implementation was more problematic due to larger input word length. The resulting longer carry chain, especially the one in the large accumulators at the output, was the major obstacle to achieving higher operating frequency. The implementation of polynomial transform DCT avoids this obstacle by using a butterfly of adders and no accumulators are needed at the output. The accuracy of both implementations has been extensively measured and detailed results were reported, more detailed then available in the previous work. Once the strong foundations for comparison were built, other factors, like resource usage, maximum achievable frequency, latency and throughput have been compared. Another contribution of the thesis is the proposal of designing the butterfly stage of such highly complex algorithms by scheduling the computation from the last stage, where the designer has no flexibility. This approach has yielded a very efficient FPGA implementation, superior to others reported.
Abstract (croatian)	Polinomijalna transformacija je predstavljena kao efikasan način mapiranja višedimenzionalnih transformacija (kao ˇsto su DCT i DFT) i konvolucija u jedno-dimenzionalne. Algoritmi koji nastaju takvim mapiranjem zahtijevaju znatno manji broj računskih operacija, posebno u slučaju konvolucija i DCT-a. Ako se koristi optimalan DCT algoritam za prvu dimenziju, korištenjem polinomijalnih transformacija se mogu konstruirati višedimenzionalni algoritmi koji dostižu teoretski minimum broja operacija. Kao ˇsto je pokazano u magistarskom radu, DCT baziran na polinomijalnim transformacijama se može implementirati tako da zauzima znatno manje logičkih resursa nego algoritam baziran na distribuiranoj aritmetici. Polinomijalne transformacije se računaju nizom zbrajanja i oduzimanja, tako da se mogu izbjeći efekti konačne dužine registara i prema tome dobiti viša preciznost. Druga dimenzija implementacije bazirane na distribuiranoj aritmetici je znatno problematičnija od prve zbog veće širine ulazne riječi. Glavna prepreka većoj brzini rada je dugački lanac prijenosa u akumulatoru na izlazu druge dimenzije. Implementacija bazirana na polinomijalnim transformacijama nema takvih nedostataka jer se izvodi nizom zbrajala i oduzimanja bez akumulatora na izlazu. Izmjerena je preciznost obje implementacije i prikazani su rezultati koji su detaljniji od prethodno objavljenih. Jednom kad su položeni jaki temelji za usporedbu, obje implementacije su usporedbene i po drugim faktorima kao što su zauzeće logičkih resursa, maksimalna radna frekvencija, latencija i količina podataka koja se može obraditi u jedinici vremena. Dodatni doprinos rada je prijedlog za dizajniranje izlaznog stupnja koji je baziran na organizaciji operacija počevši od zadnjeg stupnja, gdje dizajner ima najmanje slobode. Takav pristup je rezultirao u vrlo efikasnoj FPGA implementaciji koja je superiorna drugim implementacijama koje su objašnjene u literaturi.
Keywords
Keywords (english)
Language	english
URN:NBN	urn:nbn:hr:168:756032
Study programme	Title: Računarstvo Study programme type: sveučilišni Study level: poslijediplomski znanstveni (magistarski) Academic / professional title: magistar inženjer računarstva (magistar inženjer računarstva)
Type of resource	Text
Extent	84 str. ; 30 cm
File origin	Born digital
Access conditions	Closed access
Terms of use
Repository	FER Repository
Created on	2019-07-04 11:41:43