50. Теорема об эффективном кодировании.

Этот вид кодирования используется для уменьшения объемов информации на носителе - сигнале.

Для кодирования символов исходного алфавита используют двоичные коды переменной длины: чем больше частота символа, тем короче его код.

При эффективном кодировании существует предел сжатия, ниже которого не «спускается» ни один метод эффективного кодирования - иначе будет потеряна информация. Существуют два классических метода эффективного кодирования: метод Шеннона-Фано и метод Хаффмена. Входными данными для обоих методов является заданное множество исходных символов для кодирования с их частотами; результат - эффективные коды.

51. Общие принципы использования избыточности

Рассмотрим, для примера, полный набор трехразрядных кодовых слов Х₀-Х₇ (рис 18.1).

Очевидно, что любая ошибка здесь приведет к неверному распознаванию переданного слова X_i. Если ограничить набор допустимых кодовых комбинаций (например по принципу четного количества «1» в слове), то одиночная ошибка при передаче приведет к приему недопустимого слова и ее можно будет обнаружить. Это достигается ценой избыточности (в примере для кодирования четырех символов достаточно было бы двух разрядов)-рис.18.1б.

Наконец, если ограничиться лишь двумя словами, отличающимися в максимальном количестве разрядов, то обнаружить можно будет и двукратные ошибки, а единократные даже исправить (как видно по рис.18.1 в, слово искаженное однократной ошибкой, всегда ближе к своему «прототипу», чем к другим словам кода). Разумеется, платой за это является дополнительная избыточность.

Обобщим эти замечания. Будем называть кодовым расстоянием d между двумя кодовыми словами количество несовпадающих разрядов (так для слов 100 и 010 d = 2, а для 010 и 011 d = 1). Полный набор кодовых слов характеризуется минимальным кодовым расстоянием d_min. Для без избыточного кода (рис.18.1 a) d_min = 1, для кода рис.18.1 б d_mjn ⁼ 2, рис.18.1 в d_min = 3. Минимальное кодовое расстояние определяет гарантированную возможность обнаружения и исправления ошибок. Рис.18.1 наглядно иллюстрирует также следующие соотношения:

-минимальная кратность r_m ошибок, которые могут быть распознаны r_m⁼d_min-l (18.1)

-максимальная кратность S_m ошибок, которые могут быть исправлены.

(18.2)

-если ставится задача сочетать исправление ошибок кратности S<S_m и обнаружение ошибок более высокой кратности г, то r≤d_min-S-1 (18.3)

Соотношения 18.1 - 18.3, как следует из определения d_min, рассчитаны на самый худший случай. В конкретных ситуациях иногда удается обнаружить и исправить ошибки и большей кратности.

Сделаем еще несколько общих замечаний относительно помехозащитных кодов:

Во-первых, важной характеристикой кода является его способность противостоять так называемым «пачкам» ошибок (в соседних разрядах кодового слова). Под пачкой ошибок длиной l понимают набор соседних разрядов х_i – х_i+1, где разряды х_i и х_i+1 ошибочны, а среди промежуточных X_j (i≤_j≤j+l) ошибки распределены произвольно. Существуют коды, которые распознают пачки ошибок длиной l>> d_min.

Во-вторых, чем больше длина кодовых слов, тем меньшую долю составляют избыточные разряды, обеспечивающие заданный уровень d_min. To есть, избыточное кодирование выгоднее выполнять именно для длинных слов.

В-третьих, избыточные разряды могут быть в принципе распределены по всей длине слова, однако чаще всего они образуют так называемый «хвост». В этом случае кодовое слово имеет следующую структуру:X₁… Х_k -Информационные разряды X_k+1…X_k+m - Избыточные разряды