Fano's condition

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

Back to the table of contents
Alterna chapter 26
Fano's condition
Binary coding · Huffman algorithm · Decoding
Chapter 26
Codes
- codes that are decoded with no separations, study the Fano condition, the code tree, the Huffman algorithm and practice.
GEF
PIF
OGE No. 2.4
EEG No. 4
📚
Theory
26.1
Fano's condition
Prefix codes, definition, code tree, Craft inequality
26.2
Duplicate coding
Huffman algorithm, even and uneven codes, optimality
26.3
Decoding
Walking decoder, decrypting errors, certainty
🎯
Practice
26.4
EEG/EGL workshop
50+ Filters, Reviews and Statistics Jobs
26.5
Polygon examination
Quest 800 XP · Test 8 min · Open task
🔗
Relationship with other chapters
Previous chapter
Chapter 25 - Trees
- Binary trees, bypassing, and a binary tree are the basis for a tree code.
Next chapter
Chapter 27 entropy
is a quantitative measure of information, a connection to optimal coding.
📝
Key formulas
Concept
Formula
Description
Fano's condition
Ни одно кодовое слово не префикс другого
One-digit decoding
Inequality of Kraft
∑ 2
−Li
≤ 1
Prefix code condition
Huffman.
min-heap → дерево → коды
Greedy optimal coding algorithm
Average length
L = Σ pᵢ × lᵢ
Weighted sum of length by frequency
Enthropia
H = −Σ pᵢ log₂(pᵢ)
Minimum possible average length