Cтраница 2
Таким образом, для кодирования Шеннона - Фано энтропия снова дает нижнюю границу средней длины кода. Энтропия входит также в верхнюю границу. Верхнюю границу для кодов Хаффмена ( см. гл. Хаффмена не могут быть хуже кодов Шеннона - Фано. [16]
Код Хаффмана ( Huffman code) [20] - это свободный от префикса код, который может давать самую короткую среднюю длину кода п для данного входного алфавита. Самая короткая средняя длина кода для конкретного алфавита может быть значительно больше энтропии алфавита источника, и тогда эта невозможность выполнения обещанного сжатия данных будет связана с алфавитом, а не с методом кодирования. Часть алфавита может быть модифицирована для получения кода расширения, и тот же метод повторно применяется для достижения лучшего сжатия. Эффективность сжатия определяется коэффициентом сжатия. Эта мера равна отношению среднего числа бит на выборку до сжатия к среднему числу бит на выборку после сжатия. [17]
Так как вероятности каждой группы различны, длина кода для каждой группы принимается в соответствии с рассмотренными выше рекомендациями, так чтобы средняя длина кода была минимальной. [18]
Из сделанных выше предположений следует, что это число отрицательно; переставляя кодовые слова, соответствующие символам Sn и sn, уменьшаем среднюю длину кода. Таким образом, приходим к заключению, что выполнены указанные две цепочки неравенства. [19]
Код Хаффмана ( Huffman code) [20] - это свободный от префикса код, который может давать самую короткую среднюю длину кода п для данного входного алфавита. Самая короткая средняя длина кода для конкретного алфавита может быть значительно больше энтропии алфавита источника, и тогда эта невозможность выполнения обещанного сжатия данных будет связана с алфавитом, а не с методом кодирования. Часть алфавита может быть модифицирована для получения кода расширения, и тот же метод повторно применяется для достижения лучшего сжатия. Эффективность сжатия определяется коэффициентом сжатия. Эта мера равна отношению среднего числа бит на выборку до сжатия к среднему числу бит на выборку после сжатия. [20]
Единица в клетке (, /) указывает на обнаружение отказавшего блока / в результате t - й проверки. Требуется определить среднюю длину кода неисправностей. [21]
Предположим, что оценки вероятностей Pi неточны. Как при этом ухудшается средняя длина кода. Короче говоря, будут ли малые ошибки в оценках сильно ухудшать ( или улучшать) систему. [22]
Если сообщения неравновероятны и независимы, статистическое кодирование достигается применением возможно коротких кодов для очень вероятных, часто повторяющихся сообщений, и более длинных кодов - для маловероятных, редко повторяющихся сообщений. В конечном счете это укорачивает среднюю длину кода, улучшает упаковку сообщений в сигналах. [23]
Таким образом, особенностью ПРПИ является то, что в ней возможно применение неизбыточных кодов, которые при равновероятности входных сообщений имеют постоянную длину. Если входные сообщения неравновероятны, то возникает проблема уменьшения средней длины кода за счет согласования источника информации со свойствами полученных кодовых комбинаций. В этом случае основная идея кодирования сводится к тому, чтобы наиболее часто встречающимся сообщениям присвоить наиболее короткие кодовые комбинации. Тогда уменьшается средняя длина кода и увеличивается количество информации, которая переносится в одном элементе кода. [24]
Отметим, что рассмотренная схема дает выигрыш только при неравномерном распределении символов по частоте. Если бы в приведенном выше примере частоты использования символов были одинаковы, средняя длина кода составила бы 1 - 0 25 2 - 0 25 3 - 0 25 3 - 0 25 е2 25 бита на символ, что хуже кода с фиксированной длиной. [25]
Чтобы улучшить эффективность кодирования или достичь большего сжатия, следует переопределить алфавит источника. Больший алфавит источника увеличивает разнообразие, что является одним из требований при сокращении средней длины кода и увеличении числа ветвей дерева для присвоения кода переменной длины. Это делается посредством выбора знаков ( по два) из алфавита источника, которые становятся новыми знаками в расширенном алфавите. Если предположить, что символы независимы, вероятность каждого нового элемента является произведением отдельных вероятностей. Алфавит расширения имеет следующий вид. [26]
Для первого кода количество информации в единицу времени равно 0 304 бит / с, для второго - 0 283 бит / с. Энтропия ансамбля сообщений равна t 78 бита. При кодировании двоичным оптимальным кодом может быть получена средняя длина кода 1 8 дв. [27]
Таким образом, особенностью ПРПИ является то, что в ней возможно применение неизбыточных кодов, которые при равновероятности входных сообщений имеют постоянную длину. Если входные сообщения неравновероятны, то возникает проблема уменьшения средней длины кода за счет согласования источника информации со свойствами полученных кодовых комбинаций. В этом случае основная идея кодирования сводится к тому, чтобы наиболее часто встречающимся сообщениям присвоить наиболее короткие кодовые комбинации. Тогда уменьшается средняя длина кода и увеличивается количество информации, которая переносится в одном элементе кода. [28]
Легко провести модификацию кода на случай кодового алфавита из г символов. Однако, если об этом заранее не позаботиться, на последнем шаге может оказаться невозможным найти в точности г слов для кодирования. Наименьшее увеличение средней длины кода произойдет, если неполная группа состоит из наименее вероятных символов. Поэтому при первом разбиении нужно сопоставить г символов ( верхнюю группу из г символов), затем следующие г символов и так далее до тех пор, пока это возможно; последний ( нижний) шаг разделения содержит все, что осталось. [29]