Uvod v teorijo informacij

delo diplomskega seminarja

Primož Durcik (Author), Tomaž Košir (Mentor), Gregor Šega (Co-mentor)

Abstract

V delu diplomskega seminarja sem se ukvarjal z iskanjem kodiranja, ki ima najmanjšo pričakovano dolžino. Takšnemu kodiranju pravimo optimalno kodiranje. Najprej sem določil omejitve dolžin optimalnega kodiranja in dokazal Kraftovo neenakost za predponska kodiranja in kodiranja, ki se jih da enolično odkodirati (enolična kodiranja). Kraftova neenakost nam namreč daje potreben in zadosten pogoj za obstoj predponskega kodiranja ali enoličnega kodiranja za dano množico dolžin. V zaključku dela pa sem se osredotočil na Huffmanovo kodiranje. Na primerih sem predstavil idejo Huffmanovega algoritma ter povezave z nekaterimi drugimi matematičnimi problemi. Nato sem podal teoretično ozadje algoritma in dokazal, da je kodiranje, ki ga dobimo s Huffmanovim algoritmom, optimalno.

Keywords

matematika;entropija;Huffmanove kode;informacija;kode;kodiranje;Kraftova neenakost;optimalno kodiranje;

Data

Language:	Slovenian
Year of publishing:	2018
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[P. Durcik]
UDC:	519.8
COBISS:	18429529
Views:	623
Downloads:	242
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Introduction to information theory
Secondary abstract:	In the course of the diploma seminar I was looking for code with the smallest expected length. Such code is called optimal code. First I defined the limits of lengths of optimal code and presented Kraft inequality for prefix code and uniquely decodable code. Kraft inequality gives us a necessary and sufficient condition for the existence of a prefix code or a uniquely decodable code for a given set of codeword lengths. At the end of my work I focused on Huffman codes. Using examples I presented the idea of Huffman algorithm and the connection with some other mathematical problems. Then I gave the theoretical background to the algorithm and concluded that the code obtained with the Huffman algorithm is optimal.
Secondary keywords:	mathematics;entropy;Huffman codes;information;codeword;codes;coding;Kraft inequality;optimal coding;Shannon information;
Type (COBISS):	Final seminar paper
Study programme:	0
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Finančna matematika - 1. stopnja
Pages:	27 str.
ID:	10958730