[Rezolvare] codificarea a 20 de mesaje

[root]

EXEMPLU REZOLVAT
Codificarea unei surse cu 20 de mesaje

Imaginea 1 — 20 de instrumente muzicale

codex-clipboard-47b1e686-d795-4c14-bf56-1a570a0b4aeb.png (99.62 KiB) Viewed 26 times

Enunț

În imagine sunt incluse 20 de cartonașe digitale care reprezintă instrumente muzicale. Fiecărui cartonaș i se asociază un cod unic, format din cuvinte binare de aceeași lungime.

Ansamblul cartonașelor reprezintă o sursă de mesaje, iar fiecare cartonaș reprezintă un mesaj distinct.

Cerință: Calculați cea mai mică lungime a cuvintelor binare de lungime egală, suficientă pentru codificarea și decodificarea univocă a celor 20 de mesaje.

Datele problemei

• Numărul mesajelor distincte: n = 20
• Alfabetul utilizat: binar {0, 1}
• Necunoscuta: lungimea minimă m a unui cuvânt binar

Formula utilizată

Pentru un cuvânt binar de lungime m se pot forma 2^m coduri distincte. Condiția codificării univoce este:

2^m ≥ n

Echivalent:

m ≥ log₂(n)

Calcule efectuate

Înlocuim n = 20 și verificăm puterile lui 2 apropiate:

2⁴ = 16 < 20

Patru biți permit numai 16 coduri distincte, deci nu sunt suficienți.

2⁵ = 32 ≥ 20

Cinci biți permit 32 de coduri distincte, deci sunt suficienți pentru toate cele 20 de mesaje.

Putem scrie și direct:

m = ⌈log₂(20)⌉ = ⌈4,3219...⌉ = 5

Concluzie

Lungimea minimă necesară pentru fiecare cuvânt binar este de 5 biți. Din cele 32 de coduri posibile vor fi folosite 20, câte unul pentru fiecare instrument muzical.

Răspuns: 5 biți