Question

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: А = 11, Б = 0, В = 100. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

Answer 1

Ответ:

Мы можем выбрать код для Г как код без префиксов (также известный как мгновенный код), чтобы не было неоднозначных кодовых слов. Один из возможных беспрефиксных кодов для Г — 101. Таким образом, полный код для четырех букв будет таким:

А = 11 Б = 0 B = 100 Г = 101

Этот код не содержит префиксов, потому что ни одно кодовое слово не является префиксом любого другого кодового слова. Следовательно, любая последовательность битов, начинающаяся с кодового слова, представляет собой уникальную последовательность букв. Например, последовательность «110100101» представляет собой сообщение «АБВГ», потому что ее можно однозначно разделить на «11» (A), «0» (B), «100» (В) и «101» (Г). .

Answer 2

Для того чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы, необходимо выбрать код для буквы Г так, чтобы он не был префиксом кодам других букв (то есть не мог быть началом кода для другой буквы). Это свойство называется "беспрефиксным кодированием".

Исходно даны следующие коды:

• А = 11
• Б = 0
• В = 100

Заметим, что код для "Б" (0) является префиксом кода для "В" (100), поэтому он не подходит для буквы Г. Мы можем выбрать код для Г так, чтобы он не был префиксом ни одному из существующих кодов. Например, мы можем выбрать код для Г как 101:

• Г = 101

Теперь все коды букв не являются префиксами других кодов, и сообщение, состоящее из этих кодов, может быть однозначно разбито на буквы.