Решение.

Н а рис. 4.4 показаны двоичные последовательности на входе и выходе кодера, причем ради наглядности они разбиты на части, соответствующие отдельным шагам. Сплошные линии указывают, какие номера извлекаются из кодовой таблицы и подаются на выход кодера. Штриховые линии показывают путь внесения очередных записей в кодовую таблицу (первая запись “пробел” и его номер 000 внесены в таблицу заранее). Убедитесь, что по передаваемой последовательности в пункте приема можно в том же порядке заполнять кодовую таблицу и декодировать сигнал.

ЗАДАЧИ

4.2.1. Убедиться в том, что при кодировании двоичным ко­дом Шеннона-Фано сообщений источника, заданного табл. 4.2.4, может быть достигнута длина кодового слова, удовлетворяю­щая условию .

Сравнить полученный код с равномерным кодом.

Таблица 4.2.4

xj	x1	x2	x3	x4	x5	x6	x7	x8
р(хj)	1/2	1/4	1/8	1/16	1/32	1/64	1/128	1/128

4.2.2. Источник статистически независимых сообщений за­дан табл. 4.2.5.

Таблица 4.2.5

xj	x1	x2	x3	x4	x5	x6	x7	x8	x7	x7
р(хj)	1/4	1/4	1/8	1/8	1/16	1/16	1/16	1/32	1/64	1/64

Закодировать сообщения источника двоичным кодом так, чтобы средняя длина кодового слова была минимальна. Оце­нить эффективность полученного кода.

4.2.3. Ансамбль сообщений задан табл. 4.2.6.

Таблица 4.2.6

xj	x1	x2	x3	x4	x5	x6	x7	x8
р(хj)	0,2	0,25	0,15	0,1	0,05	0,05	0,14	0,06

Сообщения источника статистически независимы. Передача производится по двоичному каналу. Длительности символов кодированного сигнала одинаковы τ₀=τ₁=τ. Определить скорость передачи информации при использовании равномер­ного кода и кода Шеннона-Фано. Сравнить коды по их эф­фективности.

4.2.4. Закодировать статистически независимые сообще­ния источника (табл. 4.2.7) двоичным кодом Хафмана. Найти вероятности появления ну­лей и единиц в полученной последовательности.

Таблица 4.2.7

xj	x1	x2	x3	x4	x5	x6	x7
р(хj)	0,25	0,23	0,15	0,12	0,1	0,08	0,07

4.2.5. Закодировать двоичным кодом Шеннона-Фано алфа­вит источника, состоящий из четырех букв (А, В, С, Д) с ве­роятностями 0,28; 0,14; 0,48 и 0,1 соответственно. Оценить эф­фективность полученного кода.

4.2.6. Сколько вопросов в среднем надо задать, чтобы от­гадать задуманное собеседником целое положительное число, не превосходящее 10, если спрашиваемый на все вопросы от­вечает лишь «да» или «нет»?

4.2.7. Известно, что жители некоторого города А всегда го­ворят правду, а жители соседнего города Б всегда обманыва­ют. Наблюдатель Н знает, что он находится в одном из этих двух городов, но не знает, в каком именно. Путем опроса встречного ему требуется определить: а) в каком городе он находится, б) в каком городе живет его собеседник (в каж­дом пункте можно с одинаковой вероятностью встретить жи­телей обоих городов), в) то и другое вместе.

Каково наименьшее число вопросов, которые должен за­дать Н, если на все вопросы Н встречный отвечает лишь «да» или «нет»?

4.2.8. Сообщение на выходе источника без памяти состоит из букв, принимающих значение А и В с вероятностями 0,7 и 0,3. Произвести кодирование по методу Шеннона-Фано от­дельных букв, двух- и трехбуквенных блоков. Сравнить коды по их эффективности.

4.2.9. Имеются три города (А, Б и В), причем жители А всех случаях говорят правду, жители Б – только неправду, а жители В через раз отвечают на вопросы верно и неверно. Наблюдатель Н хочет выяснить, в каком городе он находится и в каком городе живет встреченный им человек. Сколько вопросов ему потребуется задать этому встречному, если на все вопросы он отвечает лишь «да» или «нет»?

4.2.10. Некто задумал два различных целых положитель­ных числа, не превосходящих четырех. Сколько в среднем на­до задать ему вопросов для того, чтобы определить сумму этих чисел, если на каждый вопрос спрашиваемый отвечает лишь «да» или «нет»?

4.2.11. Построить оптимальное множество кодовых слов для ансамбля X, заданного табл. 4.2.8.

Таблица 4.2.8

xj	x1	x2	x3	x4	x5
р(хj)	1/2	1/4	1/8	1/16	1/32

Показать, что если сообщения статистически независимы, то в получающейся последовательности кодовых слов символы 0 и 1 независимы и появляются с равными вероятностями.

4.2.12. Сообщения гипотетического алфавита, заданного табл. 4.2.9, для передачи по двоичному каналу преобразуются кодером в последовательности кодовых символов 0 и 1 со средней длиной кодового слава

Таблица 4,2.9

aj		a1		a2		a3		a4		a5
р(aj)		0.22		0.16		0.14		0.12		0.1
a6	a7		a8		a9		a10		a11		a12
0.07	0.06		0.05		0.04		0.02		0.01		0.01

Является ли полученный код оптимальным в статистическом смысле?

4.2.13. Радиотехническое устройство состоит из 5 блоков (А, Б, В, Г, Д). Блок А в среднем выходит из строя 1 раз в 100 дней, блок Б – 1 раз в 25 дней, В – 1 раз в 5 дней, Г– один раз в 4 дня и блок Д – 1 раз в 2 дня. Контрольный прибор позволяет за одно измерение проверить работоспособ­ность в целом любой комбинации блоков.

Как нужно проводить контроль, чтобы затратить на поис­ки неисправного блока в среднем минимальное количество проверок? Найти это среднее значение.

4.2.14. Имеются 12 монет одного достоинства; 11 из них имеют одинаковый вес, а одна – фальшивая – отличается по весу от остальных (причем не известно, легче она или тяжелее настоящих). Каково наименьшее число взвешиваний на ча­шечных весах без гирь, которое позволяет обнаружить фаль­шивую монету и выяснить, легче она, чем остальные монеты, или тяжелее?

4.2.15. На кабельной линии длиной 20 км имеются 5 кон­трольных отводов, расположенных на расстоянии 1, 3, 5, 9 и 14 км от ее начала. Вероятность пробоя кабеля в любой точке линии одинакова. При осуществлении одной проверки можно установить исправность отрезка кабеля между любыми кон­трольными точками.

Как нужно проводить измерения, чтобы найти участок с поврежденным кабелем и произвести в среднем минимальное количество проверок?

4.2.16. Все буквы алфавита равновероятны, то есть избыточность отсутствует. При каком условии удастся закодировать этот алфавит двоичным кодом без избыточности?

4.2.17. Закодировать кодом Лемпела–Зива двоичную последовательность 0 0 0 0 1 0 0 0 0 0… и определить количество передаваемых двоичных символов, если используются трехразрядные номера комбинаций.