aalto1 untyped-item.component.html
Liitteettömät koodit ja ¾-konjektuuri
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Sähkötekniikan korkeakoulu |
Bachelor's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
ELEC3015
Degree programme
Language
fi
Pages
22+4
Series
Abstract
Tietokone käsittelee symboleja, binäärisinä lukuina. Symbolien yleisyys kuitenkin vaihtelee. Antamalla useammin ilmestyville symboleille lyhyemmät ja harvemmille pitemmät bittijonot, joita kutsutaan koodisanoiksi, symboleista muodostetusta bittijonosta tulee mahdollisesti lyhyempi.
Koodisanojen vaihteleva pituus tekee dekoodauksesta monimutkaisempaa, mutta etuliitteetön koodi ratkaisee tämän; mikään koodisana ei ole minkään toisen koodisanan etuliite. Kyseessä on välitön koodi, jossa dekoodaus tapahtuu välittömästi jotakin symbolia vastaavan koodisanan esiinnyttyä, koska se ei voi olla minkään muun koodisanan etuliite.
Etuliitteettömässä koodissa kun data jostain kohtaa korruptoituu, niitä seuraava ehjä data saattaa menettää yksiselitteisyyttä. Tarvitaan liitteetöntä koodia, jossa mikään koodisana ei ole minkään toisen koodisanan etuliite eikä jälkiliite. Tämä ei ole yhtä tehokas kuin etuliitteetön koodi, mutta kestää paremmin datakorruptiota.
Liitteettömästä koodista ja sen matemaattisista ominaisuuksista tunnetaan suhteellisen vähän. Tämä kirjoitus käsittelee liitteettömän koodin ominaisuuksia, siihen liittyviä ratkaisemattomia ongelmia kuten ¾-konjektuuria, sekä aiheen ymmärtämiseen tarvittavia taustatietoja ja peruskäsitteitä.
Computers process symbols as binary numbers. However, the frequency of symbols varies. By assigning shorter sequence of bits, called codewords, to more frequent symbols and longer ones to less frequent symbols, the resulting bit sequence composed of symbols can potentially be shorter.
The varying length of codewords makes decoding more complex, but a prefix-free code solves this: no codeword is a prefix of any other codeword. This is an instantaneous code, where decoding happens immediately when a codeword corresponding to a symbol appears, because it cannot be a prefix of any other codeword.
In a prefix-free code, if the data becomes corrupted at some point, the uncorrupted data that follows may no longer be uniquely decodable. A fix-free code is needed, in which no codeword is a prefix or a suffix of any other codeword. This is not as efficient as a prefix-free code but is more resilient to data corruption.
Relatively little is known about fix-free codes and their mathematical properties. This paper discusses the characteristics of fix-free codes, the unresolved problems related to them, and some basic information and concepts needed to understand the topic.