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

Проверим кодовые слова по возрастанию длины.

Код длины $1$ выбрать нельзя:

• $0$ является началом слов $00$, $010$, $011$;
• $1$ является началом нескольких кодовых слов.

Код длины $2$ также выбрать нельзя:

• $00$ уже используется;
• $01$ является началом слов $010$ и $011$;
• $10$ является началом слов $1000$, $1001$, $1010$, $1011$;
• $11$ является началом слов $1101$ и $111$.

Коды длины $3$ не подходят:

• $000$ и $001$ начинаются с $00$;
• $010$, $011$ и $111$ уже используются;
• $100$, $101$ и $110$ являются началами других кодовых слов.

Рассмотрим коды длины $4$. Слово $1100$:

• не начинается ни с одного имеющегося кодового слова;
• не является началом другого кодового слова;
• не совпадает с уже используемыми кодами.

Следовательно, $1100$ удовлетворяет условию Фано и является кратчайшим возможным кодовым словом.

Код длины $1$ выбрать нельзя:

• $0$ является началом кодов $00$ и $01$;
• $1$ является началом кодов $100$ и $110$.

Коды длины $2$ также не подходят:

• $00$ и $01$ уже используются;
• $10$ является началом кода $100$;
• $11$ является началом кода $110$.

Рассмотрим коды длины $3$. Коды $101$ и $111$ не нарушают условие Фано:

• для буквы П можно выбрать $101$;
• для буквы Р можно выбрать $111$.

Из возможных кодов минимальной длины код $101$ имеет наименьшее числовое значение.

Коды длины $1$ выбрать нельзя:

• $0$ является началом кодов $00$, $010$, $011$;
• $1$ является началом остальных кодов.

Коды длины $2$ также не подходят:

• $00$ уже используется;
• $01$ является началом кодов $010$, $011$;
• $10$ является началом кодов $1000$, $1001$, $1010$, $1011$;
• $11$ является началом кодов $110$, $1111$.

Коды длины $3$ выбрать нельзя:

• $000$, $001$ начинаются с кода $00$;
• $010$, $011$, $110$ уже используются;
• $100$, $101$, $111$ являются началами существующих кодовых слов.

Рассмотрим коды длины $4$. Код $1110$ подходит:

• ни одно существующее кодовое слово не является его началом;
• он не является началом ни одного существующего кодового слова;
• он не совпадает с другими кодами.

Следовательно, кратчайшее возможное кодовое слово для буквы Р — $1110$.

Код длины $1$ выбрать нельзя:

• $0$ является началом кодов $00$, $010$, $011$;
• $1$ является началом остальных кодов.

Коды длины $2$ не подходят:

• $00$ уже используется;
• $01$ является началом кодов $010$ и $011$;
• $10$ является началом кодов $1000$, $1010$, $1011$;
• $11$ является началом кодов $110$, $1110$, $1111$.

Коды длины $3$ также не подходят:

• $000$ и $001$ начинаются с $00$;
• $010$, $011$ и $110$ уже используются;
• $100$, $101$ и $111$ являются началами других кодовых слов.

Рассмотрим коды длины $4$. Код $1000$ уже используется, а следующий по числовому значению код $1001$ не является началом другого кодового слова и сам не начинается ни с одного имеющегося кодового слова.

Следовательно, кратчайшее подходящее кодовое слово с наименьшим числовым значением: $1001$.

Кодовые слова $00$ и $01$ занимают обе ветви, начинающиеся с $0$. Поэтому новые кодовые слова могут начинаться только с $1$.

В ветви $10$:

• коды $1000$ и $1001$ занимают всю ветвь $100$;
• код $101$ уже используется.

Следовательно, ветвь $10$ полностью занята.

В ветви $11$ код $110$ уже используется, поэтому остаётся свободной только ветвь $111$.

Код $111$ нельзя использовать для одной буквы, так как тогда он станет началом любого другого кода в этой ветви, а других свободных ветвей нет.

Поэтому два кратчайших возможных кодовых слова: $1110$ и $1111$.

Длина каждого кодового слова равна $4$. Их суммарная длина: $4+4=8$.

Кодовое слово $0$ запрещает использовать другие слова, начинающиеся с $0$.

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

Следовательно, все четыре новых кодовых слова должны начинаться с $11$.

Код $11$ использовать нельзя, так как тогда он стал бы началом остальных кодовых слов. Наименьшая сумма длин получается при выборе четырёх слов длины $4$: $1100$, $1101$, $1110$, $1111$.

Они удовлетворяют условию Фано. Сумма их длин равна $4+4+4+4=16$.

Коды длины $1$ выбрать нельзя: $0$ и $1$ являются началами существующих кодовых слов.

Коды длины $2$ также не подходят:

• $00$ уже используется;
• $01$ — начало кодов $010$ и $011$;
• $10$ — начало кодов $100$, $1010$, $1011$;
• $11$ — начало кодов $1100$, $1110$, $1111$.

Коды длины $3$ не подходят:

• $000$, $001$ начинаются с $00$;
• $010$, $011$, $100$ уже используются;
• $101$, $110$, $111$ являются началами существующих кодов.

Рассмотрим коды длины $4$. Код $1101$ подходит: он не совпадает с существующими кодами и не образует с ними отношения «начало другого кодового слова».

Все коды длины $4$ с меньшим числовым значением либо начинаются с уже имеющегося кода, либо уже используются.

Коды длины $1$ выбрать нельзя:

• $0$ является началом кодов $00$, $010$, $011$;
• $1$ является началом остальных кодов.

Коды длины $2$ также не подходят:

• $00$ уже используется;
• $01$ является началом кодов $010$ и $011$;
• $10$ является началом кодов $1000$ и $1001$;
• $11$ является началом кодов $1100$, $1101$, $1110$, $1111$.

Проверим коды длины $3$ по возрастанию:

• $000$ и $001$ начинаются с кода $00$;
• $010$ и $011$ уже используются;
• $100$ является началом кодов $1000$ и $1001$;
• $101$ не является началом ни одного известного кода и не начинается ни с одного известного кодового слова.

Следовательно, кратчайшее подходящее кодовое слово с наименьшим числовым значением — $101$.

Код длины $1$ выбрать нельзя:

• $0$ уже используется;
• $1$ является началом кодов $101$ и $110$.

Коды длины $2$ также не подходят:

• $00$ и $01$ начинаются с кода $0$;
• $10$ является началом кода $101$;
• $11$ является началом кода $110$.

Среди кодов длины $3$ подходят $100$ и $111$. Они не начинаются с известных кодовых слов и не являются началом других кодовых слов.

Выбираем код с наибольшим числовым значением: $111>100$.

Коды $00$ и $01$ занимают всю ветвь, начинающуюся с $0$.

В ветви, начинающейся с $1$:

• ветвь $100$ занята кодами $1000$ и $1001$;
• коды $110$ и $111$ уже используются;
• свободной остаётся только ветвь $101$.

Код $101$ нельзя назначить одной из букв, так как тогда для второй буквы свободного места не останется. Поэтому ветвь $101$ нужно разделить на два кодовых слова: $1010$ и $1011$.

Длина каждого кода равна $4$, поэтому суммарная длина: $4+4=8$.

Код длины $1$ выбрать нельзя:

• $0$ уже используется;
• $1$ является началом кодов $101$ и $110$.

Коды длины $2$ также не подходят:

• $00$ и $01$ начинаются с кода $0$;
• $10$ является началом кода $101$;
• $11$ является началом кода $110$.

Среди кодов длины $3$ подходят два варианта: $100$ и $111$.

Оба кода удовлетворяют условию Фано. Выбираем код с наибольшим числовым значением: $111>100$.

Коды длины $1$ выбрать нельзя:

• $0$ является началом кодов $00$, $010$, $011$;
• $1$ является началом остальных кодов.

Коды длины $2$ также не подходят:

• $00$ уже используется;
• $01$ является началом кодов $010$ и $011$;
• $10$ является началом кодов $1000$, $1001$, $101$;
• $11$ является началом кодов $1100$, $1101$, $1110$.

Коды длины $3$ не подходят:

• $000$ и $001$ начинаются с кода $00$;
• $010$, $011$ и $101$ уже используются;
• $100$, $110$ и $111$ являются началами существующих кодов.

Среди кодов длины $4$ единственный подходящий вариант — $1111$. Он не совпадает с известными кодами и не образует с ними отношения «начало другого кодового слова».

Коды длины $1$ выбрать нельзя:

• $0$ является началом кодовых слов $00$, $010$, $011$;
• $1$ является началом остальных кодовых слов.

Коды длины $2$ также не подходят:

• $00$ уже используется;
• $01$ является началом слов $010$ и $011$;
• $10$ является началом слов $1000$, $1001$, $1010$, $1011$;
• $11$ является началом слов $1101$ и $111$.

Коды длины $3$ не подходят:

• $000$ и $001$ начинаются с кода $00$;
• $010$, $011$ и $111$ уже используются;
• $100$, $101$ и $110$ являются началом других кодовых слов.

Рассмотрим коды длины $4$. Код $1100$ не совпадает ни с одним известным кодом, не начинается с существующего кодового слова и сам не является началом другого кодового слова.

Следовательно, кратчайшее кодовое слово для буквы Р: $1100$.

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

Для второй буквы код длины $2$ выбрать нельзя:

• $00$ является началом кода $001$;
• $01$ является началом кодов $010$ и $0111$;
• коды $10$ и $11$ начинаются с выбранного кода $1$.

Кратчайший подходящий код для второй буквы имеет длину $3$, например $000$.

Таким образом, можно использовать:

• Г — $1$;
• Д — $000$.

Сумма длин кодовых слов: $1+3=4$. Меньшая сумма невозможна.

Коды длины $1$ использовать нельзя:

• $0$ является началом кодов $0101$, $0100$, $011$;
• $1$ является началом кодов $110$, $111$, $101$.

Среди кодов длины $2$ свободен только код $00$. Коды $01$, $10$ и $11$ являются началами уже существующих кодовых слов.

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

Например:

Эти кодовые слова не являются началами других кодов и не начинаются с уже существующих кодовых слов.

Суммарная длина: $2+3=5$.

Кодовые слова $00$ и $01$ занимают все ветви, начинающиеся с $0$. Поэтому коды букв $C$, $D$, $E$, $F$ должны начинаться с $1$.

Код $1$ использовать нельзя, так как тогда он станет началом остальных кодовых слов.

Минимальную сумму получим, если использовать четыре кодовых слова длины $3$:

$100$, $101$, $110$, $111$.

Они удовлетворяют условию Фано. Сумма их длин равна $3+3+3+3=12$.

Меньшая сумма невозможна: если использовать код длины $2$, например $10$, то три остальных кода придётся размещать в ветви $11$, и их минимальные длины составят $3$, $4$ и $4$. Тогда сумма будет равна $2+3+4+4=13$.

Код $0$ занимает всю ветвь, начинающуюся с $0$.

Код $10$ занимает ветвь, начинающуюся с $10$. Поэтому кодовые слова для букв $C$, $D$, $E$, $F$ должны начинаться с $11$.

Чтобы получить четыре кратчайших кодовых слова, разделим ветвь $11$ на четыре равноправные ветви: $1100$, $1101$, $1110$, $1111$.

Каждое кодовое слово имеет длину $4$ и удовлетворяет условию Фано.

Сумма длин: $4+4+4+4=16$.

Коды длины $1$ выбрать нельзя: $0$ и $1$ являются началами существующих кодовых слов.

Коды длины $2$ также не подходят:

• $00$ уже используется;
• $01$ является началом кодов $010$ и $011$;
• $10$ является началом кодов $1001$, $1010$, $1011$;
• $11$ является началом кодов $110$, $1110$, $1111$.

Коды длины $3$ не подходят:

• $000$ и $001$ начинаются с кода $00$;
• $010$, $011$, $110$ уже используются;
• $100$, $101$, $111$ являются началами существующих кодов.

Среди кодов длины $4$ наименьший подходящий код — $1000$. Он не совпадает с другими кодами и не образует с ними отношения «начало другого кодового слова».

Коды длины $1$ выбрать нельзя:

• $0$ является началом кодов $00$, $010$, $011$;
• $1$ является началом остальных кодов.

Коды длины $2$ также не подходят:

• $00$ уже используется;
• $01$ является началом кодов $010$ и $011$;
• $10$ является началом кодов $1000$, $1001$, $1010$, $1011$;
• $11$ является началом кодов $1100$ и $1101$.

Проверим коды длины $3$:

• $000$ и $001$ начинаются с кода $00$;
• $010$ и $011$ уже используются;
• $100$ и $101$ являются началами существующих кодов;
• $110$ является началом кодов $1100$ и $1101$;
• $111$ подходит.

Код $111$ не начинается ни с одного существующего кодового слова и сам не является началом другого кодового слова.

Коды длины $1$ выбрать нельзя:

• $0$ уже используется;
• $1$ является началом остальных кодовых слов.

Коды длины $2$ также не подходят:

• $00$ и $01$ начинаются с кода $0$;
• $10$ уже используется;
• $11$ является началом кодов $1110$, $11110$ и $11111$.

Проверим коды длины $3$:

• $100$ и $101$ начинаются с кода $10$;
• $111$ является началом существующих кодов;
• $110$ не начинается ни с одного имеющегося кодового слова и не является началом другого кодового слова.

Следовательно, кратчайшее подходящее кодовое слово — $110$.