Fano's condition

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

Back to the table of contents
Alterna · Chapter 26 · page 26.1
Fano's condition
Prefix codes and absolute decoding.
Fano's condition
- The key to unmistakable decoding without dividers. No code word is a precursor to another.
GEF
OGE No. 2.4
EEG No. 4
Communication with Chapter 25.
A tree of code is a bin tree from
Chapter 25: Trees
: Leaves keep symbols, the path from the root sets the code word. Phano condition = all symbols in the leaves.
01
Definition
Code
- The rule of comparison for each symbol of the code word (bit line).
Prefix code
- No code word is a precursor to another word.
Fano condition
.
Prefix codes are clearly decoded
without dividers
.
Example of the Prefix Code
Code {
A=0
,
B=10
,
C=110
,
D=111
}:
0 is not a precursor 10, 110, 111
10 - Not a Prefig. 110, 111
110 — Not a Prefix 111
Decoding of the Line
01101110
: 0♪ A, 110 ♪ C, 111 ♪ D, 0 ♪ A ♪ Result:
A C D A
.
Example of the NEC Code
Code {
A=0
,
B=01
,
C=011
}:
0 - Prefig. 01 and 011
Line
011
Can be decoded as A+B (0+01) or C (011) is ambiguous!
02
Checking Fano conditions
🔍
Test of the code for accuracy
Codes (format: A=0;B=10;C=110)
03
Code Tree
Code Tree
- root binary tree. Each sheet = symbol with its code. Each rib = 0 (left) or 1 (right). The path from root to sheet = code word.
All the symbols of the Prefix code are in
Leaves
Trees.
🌳
Code Tree Designer
Codes
04
Inequality of Kraft
Inequality of Kraft
is necessary and sufficient for the existence of a prefix code with the lengths of L1, L2, ..., Ln in d-faced alphabet:
∑ d
−Li
≤ 1
For
Biblinary
Code (d=2):
∑ 2
−Li
≤ 1   например: 1/2 + 1/4 + 1/4 = 1  ✓
Checking the existence of the code
Code with lengths 1, 2, 3, 3: 1/2 + 1/4 + 1/8 + 1.8 = 1 = 1 exists.
Code with lengths of 2, 2, 2, 2: 1/4 + 1/4+ 1/4 plus 1/4 _ 1/4 = 1.25 > 1 does not exist!
🎯
Mini-test: 5 questions
XP: 0
🧩
Check yourself out.
5 Fano 20 XP questions for each correct answer