4. Кодирование и декодирование информации: шифрование слова

Известны кодовые слова:

• К — $01$;
• Р — $001$.

Одноразрядный код $0$ использовать нельзя, так как он является началом кодов $01$ и $001$. Код $1$ использовать можно, но тогда два других кодовых слова должны иметь длину не менее $4$: например, $0000$ и $0001$. Такой вариант не будет оптимальным.

Без одноразрядного кода можно использовать два свободных двухразрядных слова:

$10$ и $11$.

Для третьей буквы подходит код $000$. Получаем, например:

• А — $10$;
• Б — $11$;
• Н — $000$.

Все кодовые слова

$01$, $001$, $10$, $11$, $000$

удовлетворяют условию Фано.

В слове БАРАБАН:

• буква А встречается $3$ раза;
• буква Б — $2$ раза;
• буква Р — $1$ раз;
• буква Н — $1$ раз.

Количество двоичных знаков: $3\cdot2+2\cdot2+1\cdot3+1\cdot3=16$.

Код буквы Р равен $1$, поэтому все остальные кодовые слова должны начинаться с $0$.

Код $0$ использовать нельзя, так как он является началом кода К — $0000$. Кратчайший свободный код — $01$. Его выгодно отдать букве А, поскольку в слове КАРАВАН она встречается $3$ раза.

Для остальных букв можно выбрать, например, такие коды:

Код удовлетворяет условию Фано. Буква Д в слове КАРАВАН не встречается, поэтому ей можно назначить один из наиболее длинных кодов.

В слове КАРАВАН:

• К встречается $1$ раз;
• А — $3$ раза;
• Р — $1$ раз;
• В — $1$ раз;
• Н — $1$ раз.

Количество двоичных знаков: $4+3\cdot2+1+3+5=19$.

Меньше получить нельзя: после выбора кода $01$ для буквы А в ветви $00$ необходимо разместить код К — $0000$ и ещё три кодовых слова. Минимальные возможные длины этих трёх слов — $3$, $5$, $5$ или $4$, $4$, $4$, поэтому суммарная длина кодов букв В и Н не может быть меньше $8$.

Буква Н имеет код $0$, поэтому все остальные кодовые слова должны начинаться с $1$.

Код $1$ использовать нельзя, так как он является началом кода буквы К — $1001$. Код $10$ также использовать нельзя, поскольку он является началом кода $1001$.

Единственное возможное кодовое слово длины $2$ — $11$. Его выгодно назначить букве О, поскольку она встречается в слове КОНОВОД $3$ раза.

Остальные буквы можно закодировать так:

Все кодовые слова удовлетворяют условию Фано.

Сделать сумму длин кодов букв В и Д меньше $8$ нельзя. В ветви $10$ уже расположен код К — $1001$, и в ней необходимо разместить ещё три кодовых слова. Поэтому для двух букв В и Д минимальная суммарная длина равна $4+4=8$.

В слове КОНОВОД:

• К встречается $1$ раз;
• О — $3$ раза;
• Н — $1$ раз;
• В — $1$ раз;
• Д — $1$ раз.

Общая длина закодированного слова: $4+3\cdot2+1+4+4=19$.

В слове КАЗАЧКА:

• буква А встречается $3$ раза;
• буква К — $2$ раза;
• буквы З и Ч — по $1$ разу.

Поэтому самое короткое свободное кодовое слово нужно назначить букве А, следующее по длине — букве К.

Код $0$ не является началом известных кодов, поэтому выберем: А — $0$.

Следующее кратчайшее свободное слово: К — $10$.

Для буквы Ч кратчайшим возможным кодом будет $1110$. Получаем код:

Этот код удовлетворяет условию Фано.

Количество двоичных знаков для слова КАЗАЧКА: $2\cdot2+3\cdot1+1\cdot3+1\cdot4=4+3+3+4=14$.

Код буквы К равен $1$, поэтому все остальные кодовые слова должны начинаться с $0$.

Код $01$ можно использовать: он не является началом кода Н — $001$ и сам не начинается с известного кода. Самое короткое слово выгодно назначить букве А, которая встречается $3$ раза: А — $01$.

После этого для букв Т и З остаётся свободная ветвь $000$. Её необходимо разделить на два кодовых слова: Т — $0000$; З — $0001$.

Полученный код удовлетворяет условию Фано:

В слове КАНТАТА:

• К встречается $1$ раз;
• А — $3$ раза;
• Н — $1$ раз;
• Т — $2$ раза.

Длина сообщения: $1+3\cdot2+3+2\cdot4=18$.