Контрольные тренировочные задания
(решения)

Часть 1

Задание 5

Решение примера 1

Для передачи помехоустойчивых сообщений в алфавите, который содержит 16 различных символов, используется равномерный двоичный код. Этот код удовлетворяет следующему свойству: в любом кодовом слове содержится четное количество единиц (возможно, ни одной). Какую наименьшую длину может иметь кодовое слово?.
Ответ: ___________________________.

Решение.

Код равномерный, значит на каждый символ выделено одинаковое количество бит. При этом коды должны содержать четное количество единиц.
4 бита нам явно не подходит, хоть и 2^4=16, но нам нужны коды с четным количеством единиц.
Коды символов представляют из себя подряд идущие числа от 0 до n, записанные в двоичной системе счисления.
В четырёх битах (16 двоичных чисел) существует восемь таких, в которых количество единиц четно, и восемь, в которых количество единиц не четно. Это легко проверить по таблице тетрад. Соответственно в пяти битах будет в два раза больше таких чисел, то есть 16.
Можно решить по другому.
Один бит - это два числа:
0
1

Одно число содержит четное количество единиц (0), другое нечетное. Два бита - четыре числа:
00
01
10
11

Добавили один разряд - количество чисел с четным количеством единиц увеличилось в два раза, то есть теперь их два. Добавим 3 разряд - получим 4 четные единицы, добавим 4 разряд - получим 8 четных единиц, добавим 5 - получим 16 четных единиц, то есть 16 чисел, в которых количество единиц четно. То есть для записи 16-ти двоичных чисел с четным количеством единиц требуется 5 бит.
Ответ: 5 бит

Возврат на страницу    Решение примеров части 1 задание 5