Equitable and uneven codes

Содержание и основные понятия

Back to the table of contents
Alterna · encoding information
Equitable and uneven codes
Codes of the same and different length: definitions, comparison, code trees and Fano condition.
Equal Codes
- all symbols are encoded by words of the same length.
Uneven Codes
- Different characters get codes of different lengths, which saves memory.
GEF
PIF
OGE No. 2.4
EEG No. 4
01
Equivalent coding
Fixed length codes: simplicity and reliability
GEF
Definition
Equivalent code
- code in which all alphabet symbols are coded by code words
equal length
.
Minimum code length for N symbols:
k = ⌈log₂(N)⌉
Bit.
Пример:
4 символа → k = log₂(4) = 2 бита
A=00, B=01, C=10, D=11
Equator code: 4 characters 2 bits
A = 00
B = 01
C = 10
D = 11
"ABACAD" message = 00 01 00 10 00 11 =
12 bits
6 characters x 2 bits = 12 bits
♪ Decoding is always unambiguous (s fixed length blocks)
Uniform code tree (4 characters, 2 bits)
All symbols
one level
(deep 2) is the same length code.
02
Uneven coding
Codes of variable length: Savings on frequent symbols
GEF
OGE No. 2.4
EEG No. 4
Definition
Uneven code
- code in which different characters are encoded by words
Different lengths
.
Principle:
frequent symbols receive short codes
The rare ones are long.
Пример:
A=0, B=10, C=110, D=111
Сообщение «AAAAABCD» = 0 0 0 0 0 10 110 111 =
13 бит
В равномерном коде: 8 × 2 = 16 бит → экономия 3 бита!
Wood of uneven code (A=0, B=10, C=110, D=111)
Symbols
different levels
- A at depth 1, B at depth 2, C and D at depth 3.
Comparison: even vs uneven
Property
Equal
Uneven
Code length
Same
Miscellaneous
Decoding
Simple (block)
More complex (prefix code required)
Savings
None
Yes (up to 30-50%)
Fano's condition
Always done.
We need to check.
Example
ASCII, UTF-32
Huffman Code, Morse
🔄
Combination of message codes
Enter message and symbol codes. Compare even and uneven options.
Message:
Code A:
Code B:
Code C:
Code D:
03
Minimum length of the uniform code
How to determine how many bits are needed for N symbols
GEF
OGE No. 2
📊
Minimum code length calculator
Enter the number of characters -- you get the minimum length of the even code.
Number of N characters:
Interactive graphics: k = xlog2(N)
Number of N characters:
20
04
Decoding messages
Practice: Decode the binary line by the specified code
🔓
Decipher: from the binary line to the text
Give the symbol codes and the binary line to decode.
A:
B:
C:
D:
Double line:
📝
OGE/EGB task bank
0 / 15
05
Mini test
🎯
Check yourself out: 5 questions
0 / 500 XP
0/5