Liitteettömät koodit ja ¾-konjektuuri

Thumbnail Image

Files

Honda_Aiki_2025.pdf (808.02 KB)

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

2025-05-30

Department

Major/Subject

Informaatioteknologia

Mcode

ELEC3015

Degree programme

Sähkötekniikan kandidaattiohjelma

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.

Description

Supervisor

Lassila, Pasi

Thesis advisor

Östergård, Patric

Keywords

3/4-konjektuuri, Kraft-McMillan epäyhtälö, fix-free koodaus, välitön koodi

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202506174783

Collections

[kand] Sähkötekniikan korkeakoulu / ELEC