Uvod v teorijo informacij : delo diplomskega seminarja

Durcik, Primož (author), Košir, Tomaž (mentor), Šega, Gregor (co-mentor)

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.

• Language: Slovenian
• Keywords: entropija, Huffman, informacija, koda, kodiranje, Kraftova neenakost, optimalno, Shannon
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2018
• PID: 20.500.12556/RUL-102701
• UDC: 519.8
• COBISS.SI-ID: 18429529
• Publication date in RUL: 07.09.2018

Secondary language

• Language: English
• Title: Introduction to information theory

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.

• Keywords: entropy, Huffman, information, codeword, code, Kraft inequality, optimal, Shannon