Ещё пример задания. Ещё пример задания

Ещё пример задания

Р-15.По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы: X, Y, Z, W; для кодировки букв используются кодовые слова длины 5. При этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв X, Y, Z используются 5-битовые кодовые слова:

X: 01111, Y: 00001, Z: 11000. Определите 5-битовое кодовое слово для буквы W, если известно, что оно начинается с 1 и заканчивается 0.

Решение:

6) По условию кодовое слово для буквы W соответствует маске 1***0, где вместо звёздочек можно поставить 0 или 1.

7) Найдем расстояния Хэмминга – количество позиций, в которых отличается это кодовое слово от известных кодовых слов букв X, Y и Z:

X: 01111 Y: 00001 Z: 11000

W: 1***0 W: 1***0 W: 1***0

2+? 2+? 0+?

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

8) Как видим, наиболее критичная ситуация сложилась для пары Z-W. Для того, чтобы эти кодовые слова различались в трёх позициях, все неизвестные биты кодового слова буквы W должны иметь значения, обратные соответствующим битам кодового слова для буквы Z, то есть, W = 10110

9) Проверяем полученное кодовое слово: находим расстояние Хэмминга в парах X-W и Y-W:

X: 01111 Y: 00001 Z: 11000

W: 10110 W: 10110 W: 10110

3 4 3

10) Как видим, для все пар расстояние не меньше трёх, что соответствует условию задачи.

11) Ответ: 10110.

Ещё пример задания

Р-14.Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная

сумма длин всех шести кодовых слов? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение:

1) это задание удобнее решать с помощью дерева; условие Фано выполняется тогда, когда все выбранные кодовые слова заканчиваются в листьях дерева

2) построим дерево по известным кодовым словам: А – 0, Б – 10:

3) на оставшуюся свободную ветку нужно «повесить» 4 кодовых слова (для букв В, Г, Д, Е)

4) если выбрать один код длиной 3 (В – 110), то оставшиеся 3 кода нужно «повесить» на одну ветку, так, что на ней нужно делать две развилки:

5) суммарная длина кодовых слов будет в этом случае равна

1 + 2 + 3 + 4 + 2·5 = 20

6) попробуем другой вариант: оставшиеся 4 кода повесить на 4 ветки одинаковой длины:

7) суммарная длина кодовых слов будет в этом случае меньше, чем в предыдущем случае:

1 + 2 + 4·4 = 19

8) Ответ: 19.

⇐ Предыдущая 123 4 5 6 Следующая ⇒