prikaz prve stranice dokumenta Discrete cosine transform algorithms for FPGA devices
No public access
scientific master's theses
Discrete cosine transform algorithms for FPGA devices
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2003. urn:nbn:hr:168:756032
Babić, Domagoj
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

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

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

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

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

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 2024 December 26] Available at: https://urn.nsk.hr/urn:nbn:hr:168:756032

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

Metadata
TitleDiscrete cosine transform algorithms for FPGA devices
Title (croatian)Algoritmi za diskretnu kosinusnu transformaciju za FPGA sklopove
AuthorDomagoj Babić
MentorMario Kovač (mentor)
Committee memberMario Kovač (predsjednik povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2003, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Universal decimal classification
(UDC)		004 - 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)
Languageenglish
URN:NBNurn:nbn:hr:168:756032
Study programmeTitle: Postgraduate master programe in computing
Study programme type: university
Study level: postgraduate
Academic / professional title: magistar inženjer računarstva (magistar inženjer računarstva)
Catalog URLhttp://lib.fer.hr:8080/cgi-bin/koha/catalogue/detail.pl?biblionumber=29094&searchid=634plmj4
Type of resourceText
Extent84 str. ; 30 cm
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Created on2019-07-04 11:41:43