Из условия Фано следует, что в префиксном неравномерном двоичном коде, предусматривающем однозначное декодирование, ни одно кодовое слово не может быть началом другого.
Таким образом, оставшиеся три кода не могут быть началом кода буквы Б, и началами кодов друг друга.
То есть коды 0 и 00 отпадают сразу, т.к. это начала буквы Б.
Если предположить, что один из кодов равен 1, и что нам нужны кратчайшие коды, значит оставшиеся коды могут быть только 01 и 011.
Если предположить, что коды двузначны, тогда кодами могут быть 01, 10 и 11.
В первом случае суммарная длина кодов равна 1+2+3+3 = 9, во втором случае - 2+2+2+3 = 9.
Оба варианта подходят, кратчайшая суммарная длина - 9
Таким образом, оставшиеся три кода не могут быть началом кода буквы Б, и началами кодов друг друга.
То есть коды 0 и 00 отпадают сразу, т.к. это начала буквы Б.
Если предположить, что один из кодов равен 1, и что нам нужны кратчайшие коды, значит оставшиеся коды могут быть только 01 и 011.
Если предположить, что коды двузначны, тогда кодами могут быть 01, 10 и 11.
В первом случае суммарная длина кодов равна 1+2+3+3 = 9, во втором случае - 2+2+2+3 = 9.
Оба варианта подходят, кратчайшая суммарная длина - 9
картинка
Объяснение:
1.
Минимальное двоичное число из 5 цифр: 10000₂
10000₂ = 1 * 2⁴ + 0 * 2³ + 0 * 2² + 0 * 2¹ + 0 * 2⁰ = 16 + 0 + 0 + 0 + 0 = 16₁₀
Максимальное двоичное число из 5 цифр: 11111₂
11111₂ = 1 * 2⁴ + 1 * 2³ + 1 * 2² + 1 * 2¹ + 1 * 2⁰ = 16 + 8 + 4 + 2 + 1 = 31₁₀
2.
1 / 2 = 0 + остаток 1
записываем остатки снизу вверх
1₁₀ = 1₂
2 / 2 = 1 + остаток 0
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
2₁₀ = 10₂
3 / 2 = 1 + остаток 1
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
3₁₀ = 11₂
4 / 2 = 2 + остаток 0
2 / 2 = 1 + остаток 0
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
4₁₀ = 100₂
5 / 2 = 1 + остаток 1
2 / 2 = 1 + остаток 0
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
5₁₀ = 101₂
6 / 2 = 3 + остаток 0
3 / 2 = 1 + остаток 1
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
6₁₀ = 110₂
7 / 2 = 3 + остаток 1
3 / 2 = 1 + остаток 1
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
7₁₀ = 111₂
8 / 2 = 4 + остаток 0
4 / 2 = 2 + остаток 0
2 / 2 = 1 + остаток 0
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
8₁₀ = 1000₂
9 / 2 = 4 + остаток 1
4 / 2 = 2 + остаток 0
2 / 2 = 1 + остаток 0
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
9₁₀ = 1001₂
10 / 2 = 5 + остаток 0
5 / 2 = 1 + остаток 1
2 / 2 = 1 + остаток 0
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
10₁₀ = 1010₂
11 / 2 = 5 + остаток 1
5 / 2 = 1 + остаток 1
2 / 2 = 1 + остаток 0
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
11₁₀ = 1011₂
12 / 2 = 6 + остаток 0
6 / 2 = 3 + остаток 0
3 / 2 = 1 + остаток 1
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
12₁₀ = 1100₂
13 / 2 = 6 + остаток 1
6 / 2 = 3 + остаток 0
3 / 2 = 1 + остаток 1
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
13₁₀ = 1101₂
14 / 2 = 7 + остаток 0
7 / 2 = 3 + остаток 1
3 / 2 = 1 + остаток 1
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
14₁₀ = 1110₂
16 / 2 = 8 + остаток 0
8 / 2 = 4 + остаток 0
4 / 2 = 2 + остаток 0
2 / 2 = 1 + остаток 0
1 / 2 = 1 + остаток 1
записываем остатки снизу вверх
16₁₀ = 10000₂
3. Где есть цифра 1 - пишем 1, где цифр нет - пишем 0.