«ж
о
о.
при этом детерминироваыно; равенство достигается при равновероятном появлении ситуация наибольшей неопредел╦нности. При т=2 и равномерном появлении букв аг и л2 энтропия максимальна и Я(Р)^1. Эта величина ≈ неопредел╦нность при равновероятном выборе из двух альтернатив используется как единица кол-ва энтропии ≈ 1 бит.
Пусть, далее, канал работает в г-буквенном алфавите и г<т. Кодирование при этом будет заключаться в сопоставлении каждому символу at£Am слова Ь(а-) в алфавите Вг.
Каждый способ кодирования характеризуется ср. числом L(P] букв выходного алфавита, приходящихся на одну букву входного алфавита А т. Для алфавит-
m
ного кодировапия L(P)= 2 P&I гДе *i' ≈ Длина слова
Ь (я,) в алфавите Вг. Если кодирование взаимно
однозначно, то
т
1=1
Величина I(P}~L(P)≈ЯГ(Р] наз. избыточностью кодирования при распределении Р. Задача состоит в отыскании в заданном классе взаимно однозначных кодирований кодирования, обладающего мин. величиной 1(Р}- Существование минимума и его значение устанавливаются теоремой Шеннона для канала без шума, гласящей, что для источника с конечным алфавитом Ат с энтропией Н (Р) можно так приписать кодовые слова буквам источника, что ср, длина кодового слова Ь(Р) будет удовлетворять условиям
L(P] <
+ 1-
logy т ^ ^ ' logr
Оптимальным считается такой код, что никакой другой не обеспечит меньшего значения Ь(Р],
Конструктивная процедура отыскания олтим. кода для кодирования данного множества сообщений предложена в 1952 Д. Хафменом (D. R, Huffman). Идея заключается в том, что буквы алфавита Ат упорядочиваются по вероятности и более вероятным приписываются более короткие кодовые слова. Код Хафмена обладает след, свойствами; слово, соответствующее наименее вероятному сообщению, имеет наибольшую длину; два наименее вероятных сообщения кодируются словами одинаковой длины, одно из к-рых оканчивается нул╦м, а другое ≈ единицей (г=2).
Оптимальное равномерное кодирование. Пусть источник с двухбуквенным алфавитом Л2≈{0, 1} и P ≈ {q, р] генерирует слова длиной Z. Относительно всего множества на 2L слов (словаря источника) существует утверждение, что при p=£q и достаточно больших / словарь источника распадается на два подмножества: группу из 2lH(Pi равновероятных слов (рабочий словарь источника) и группу слов с суммарной вероятностью, близкой к нулю («нетипичные» последовательности). Здесь Н(Р] ≈ энтропия на символ источника. Доля слов рабочего словаря весьма мала и с увеличением / стремится к нулю. Идея равномерного, или блокового, кодирования заключается в том, что кодер, получая на входе слова источника, сопоставляет кодовые слова лишь словам из рабочего словаря, кодируя все остальные одним словом, имеющим смысл ошибки. Вероятность ошибки может быть произвольно уменьшена увеличением длины слова источника. При этом объ╦м кодируемых слов 2*Я(Л требует п^1Н(Р) символов кодового слова. Поскольку слова рабочего словаря практически равновероятны, равновероятны будут и кодовые слова, а энтропия на символ кодового слова будет близка к 1 биту. Кодер, т. о., выда╦т слова длиной п</т экономя за сч╦т того, что «догружает» каждый символ до максимально возможной информационной нагрузки в 1 бит.
Кодирование источника приобретает новое значение в связи с необходимостью «сжатия» информационных
массивов данных в базах и банках данных. Массивы организационной, экономич., измерит, информация имеют столь большую избыточность, что допускают сжатие, доходящее до 80 ≈ 85%. Развитые системы управления базами данных (СУБД) имеют спец. программы (утилиты) анализа, сжатия и восстановления текста, работающие на принципах, изложенных выше. Корректирующее кодирование информации. Его целью является обнаружение и (или) исправление ошибок в кодовых словах, возникших при передаче информации по каналу с шумом. Коррекция искажений возможна за сч╦т введения избыточности в систему передачи. При этом из всего множества слов кодера канала NO лишь N будет соответствовать передаваемым сообщениям (разреш╦нные слова). Теоретически при этом доля обнаруженных ошибок не превысит
Предполагается, что информационное слово U≈ (иц
. . ., ип), где иу=0, 1, поступает на вход кодера канала (в дальнейшем ≈ кодера), ставящего ему в соответ-
ствие кодовое слово X (х1ч . . ., ^), я/≈ 0,1, />и. Кодер» т. о., добавляет по определ. правилу к слову U группу из fc ≈ 1≈n избыточных (корректирующих) разрядов. Кодовое слово X поступает в канал с шумом, где помеха искажает нек-рые из символов i/. Принятое на выходе канала слово Y≈(yi, . . ., у/) поступает на декодер, восстанавливающий (с нек-рым приближением) слово X. С кодовыми словами оперируют как с векторами в линейном векторном пространстве с метрикой Хэмминга, задающей расстояние между векторами X' и X
"
d(X', AT") =
Теорема Шеннона для каналов с шумом, утверждающая, что при помощи подходящих кодов можно передавать информацию так, чтобы вероятность ошибки после декодирования была произвольно малой при условии, что скорость передачи не превосходит пропускной способности канала связи, неконструктивна: она не указывает способа построения кода. При конструировании кода решающее значение имеет выбор модели возникновения ошибок в передаваемом слове.
Наиб, распространена модель симметричного канала с равновероятными ошибками разл. типов ≈ перехода, напр., символа 0 в 1 и 1 в 0.
Специфична модель канала «со стиралием». Выходной алфавит такого канала содержит спец. символ стирания, в к-рый и переходят символы входного алфавита при возникновении ошибки подобного типа.
Выдвигаются разл. предположения относительно распределения ошибок в передаваемой последовательности символов (кодовом слове). Возможна модель независимых ошибок (канала без памяти), модель сгруппированных ошибок (пачек ошибок), ошибок, расположенных на определ. расстоянии друг от друга, и т. д. Распространены предположения о предельной кратности ошибок в кодовых словах [3].
В рамках последнего предположения корректирующая способность кода оценивается числом ошибок, обнаруживаемых и (или) исправляемых с его помощью в кодовых словах. Предполагается, что в канале с X посимвольно суммируется (по mod 2) шумовой вектор Z> образуя слово К≈ А"фУ. Кратность возникающей в результате ошибки совпадает с числом единиц (весом Хэмминга) в Z. В векторе из I элементов не более
чем г единиц могут быть размещены ^ С≥ способами.
171=1
Это ≈ то разнообразие ошибок, к-рое может возникнуть при передаче.
Основной характеристикой кода/ определяющей его корректирующую способность по отношению к независимым ошибкам, является кодовое расстояние. Кодовое расстояние является наименьшим хэмминговым
