Теория информации

Наоборот, если: , (1.33) тогда сколь угодно близка к 1 при достаточно больших . Исходя из этой теоремы мы видим, что среднее число бит на символ источника требуемое для кодирования выхода дискретного источника без памяти с произвольно малой вероятностью ошибки декодирования, ограничено снизу энтропией источника . С другой стороны, если , вероятность ошибки декодирования приближается к 100%, если произвольно увеличивать. Понятие. Кодовые слова переменной длины . Если символы источника неравновероятны, более эффективный метод кодирования сводится к использованию кодовых слов переменной длины. Примером такого кодирования является код Морзе, который восходит к девятнадцатому веку. В коде Морзе символам, возникающим более часто, сопоставляются более короткие кодовые слова, а символам, возникающим менее часто, сопоставляются более длинные кодовые слова. Следуя этой общей идее, мы можем учесть вероятность различных символов источника при выборе кодовых слов. Определение. Проблема в том, чтобы предложить метод выбора кодовых слов для символов источника. Этот метод кодирования назван энтропийным кодированием . Теорема кодирования источника без памяти . Пусть - ансамбль символов двоичного источника без памяти с конечной энтропией и выходными символами , с соответствующими вероятностями выбора , . Существует возможность создать код, который удовлетворяет префиксному условию и имеет среднюю длину , которое удовлетворяет неравенству: