Код фиксированной длины
Код фиксированной длины — это способ кодирования, при котором каждому символу исходного алфавита ставится в соответствие кодовое слово одинаковой длины. Поэтому для чтения такого кода достаточно знать границу каждого блока: все блоки имеют одно и то же число разрядов.
Как определить длину кода
Если алфавит содержит \(N\) различных символов, для их различения нужно выбрать столько двоичных разрядов, чтобы число возможных кодовых слов было не меньше \(N\). Длина кода обозначается \(i\).
Здесь \(\lceil x \rceil\) означает округление вверх. Если \(N\) не является степенью двойки, часть возможных кодовых слов останется неиспользованной. Например, при \(N=5\) нужны 3 разряда: они дают \(2^3=8\) вариантов.
Пусть используются 4 символа: А, Б, В, Г. Так как \(2^2=4\), каждому символу можно назначить код длины 2: А — 00, Б — 01, В — 10, Г — 11. Сообщение 001110 читается блоками по два разряда: 00 11 10, то есть АГВ. Такой алгоритм декодирования не требует поиска границ кодовых слов.
Фиксированная длина означает одинаковую длину всех кодовых слов, а не обязательно использование всех возможных комбинаций. При 5 символах код длины 3 является фиксированным, хотя из 8 комбинаций используются только 5. Код переменной длины, напротив, использует кодовые слова разной длины.
Какова минимальная длина двоичного кода фиксированной длины для алфавита из 10 символов?
Главное
- В коде фиксированной длины все кодовые слова содержат одинаковое число разрядов.
- Для \(N\) символов минимальная длина двоичного кода равна \(\lceil\log_2 N\rceil\).
- При декодировании сообщение разбивают на равные блоки; неиспользованные комбинации возможны.