За счет чего при эффективном кодировании уменьшается средняя длина кодовой комбинации

Эффективное кодирование

Как известно, большинство сообщений, формируемых источником, содержат избыточность. Удаление или уменьшение избыточности является одной из задач кодирования.

Кодирование, которое осуществляет удаление или уменьшение избыточности из закодированных сообщений, называется эффективным.

Возможность эффективного кодирования основана на теореме Шеннона, согласно которой:

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

Эффективное кодирование осуществляется с применением неравномерных кодов, в которых более короткие кодовые комбинации соответствуют более вероятным символам сообщения, а более длинные — менее вероятным символам.

Основными требованиями, предъявляемыми к эффективному коду, являются:

Рассмотрим построение эффективного кода на примере кода Шеннона-Фано и кода Хаффмена.

Пример 1. Источник вырабатывает восемь сообщений с вероятностями Р(а₁) = Р(а₄) =0,25; Р(а₅) = Р(а₇) = 0,125; Р(а₂) = Р(а₃) = Р(а₆) = Р(а₈) = 0,0625. Осуществить эффективное кодирование кодом Шеннона-Фано.

Для построения кода необходимо составить таблицу 1.

Заполнение таблицы осуществляется в три этапа.

1 этап. Записываются сообщения a_i в порядке убывания их вероятностей (более вероятные вверху, менее вероятные внизу).

2 этап. Все сообщения делятся на две группы, таким образом, чтобы в каждой группе суммарные вероятности были примерно равны. Верхней группе присваивается ноль нижней единица. Затем каждая группа разбивается на две подгруппы, также, по возможности, с равными суммарными вероятностями. Верхней подгруппе присваивается ноль, нижней единица, и т. д. Деление подгрупп производится до тех пор, пока в каждой подгруппе не окажется по одному элементу a_i.

3 этап. Записываются кодовые комбинации, соответствующие каждому элементу сообщения, при этом 1-я группа соответствует старшему разряду, 2-я следующему и т. д. по всем столбцам. Если в столбце элемента a_i отсутствует символ «0» или «1», то в соответствующем разряде кодовой комбинации он не пишется.

Как видно из таблицы, каждому элементу a_i соответствует своя, нигде не повторяющаяся, кодовая комбинация. Ни одна более короткая кодовая комбинация не является началом другой более длинной. При этом более вероятные символы сообщения имеют более короткие комбинации, а менее вероятные — более длинные.

Определим, удалена ли избыточность в результате кодирования.

Энтропия, приходящаяся на один символ сообщения, определяется как

Максимальная энтропия источника формирующего восемь сообщений равна

Избыточность сообщения вырабатываемого источником равна

c_с = (Нmax(A) – Н(А))/Нmax(А) = (3 – 2,75)/3 = 0,09

Для определения избыточности сообщения после кодирования определим среднюю длину кодовой комбинации

Энтропия, приходящаяся на один разряд кодовой комбинации, определяется как

Нр(А) = Н(А)/n_ср = 2,75/2,75 = 1 бит/разряд

Максимальная энтропия на выходе двоичного дискретного источника равна

Нmax(А) = log₂2 = 1 бит/сообщ.

Определим коэффициент избыточности источника.

Таким образом, избыточность удалена.

Пример 2. По приведенным в примере 1 данным необходимо осуществить эффективное кодирование кодом Хаффмена.

Построение данного кода, также удобно оформить в виде таблицы 2.

Таблица заполняется следующим образом.

1 этап. Записываются сообщения a_i в порядке убывания их вероятностей (более вероятные вверху, менее вероятные внизу).

3 этап. Формируются кодовые комбинации, для этого записывают значение ветвей графа справа налево.

Источник

Эффективное кодирование

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

где k – число символов исходного алфавита;

n_s – число двоичных разрядов для кодирования символа s;

f_s – частота символа s; причем

где n – мощность кодируемого алфавита,

f_i – частота i-го символа кодируемого алфавита.

Этот метод требует упорядочения исходного множества символов по не возрастанию их частот. Затем выполняются следующие шаги:

а) список символов делится на две части (назовем их первой и второй частями) так, чтобы суммы частот обеих частей (назовем их Σ1 и Σ2) были точно или примерно равны. В случае, когда точного равенства достичь не удается, разница между суммами должна быть минимальна;

б) кодовым комбинациям первой части дописывается 1, кодовым комбинациям второй части дописывается 0;

в) анализируют первую часть: если она содержит только один символ, работа с ней заканчивается, – считается, что код для ее символов построен, и выполняется переход к шагу г) для построения кода второй части. Если символов больше одного, переходят к шагу а) и процедура повторяется с первой частью как с самостоятельным упорядоченным списком;

г) анализируют вторую часть: если она содержит только один символ, работа с ней заканчивается и выполняется обращение к оставшемуся списку (шаг д). Если символов больше одного, переходят к шагу а) и процедура повторяется со второй частью как с самостоятельным списком;

д) анализируется оставшийся список: если он пуст – код построен, работа заканчивается. Если нет, – выполняется шаг а).

Пример 1. Даны символы a, b, c, d с частотами fa = 0,5; fb = 0,25; fc = 0,125; fd = 0,125. Построить эффективный код методом Шеннона-Фано.

Сведем исходные данные в таблицу, упорядочив их по невозрастанию частот:

Первая линия деления проходит под символом a: соответствующие суммы Σ1 и Σ2 равны между собой и равны 0,5. Тогда формируемым кодовым комбинациям дописывается 1 для верхней (первой) части и 0 для нижней (второй) части. Поскольку это первый шаг формирования кода, двоичные цифры не дописываются, а только начинают формировать код:

В силу того, что верхняя часть списка содержит только один элемент (символ а), работа с ней заканчивается, а эффективный код для этого символа считается сформированным (в таблице, приведенной выше, эта часть списка частот символов выделена заливкой).

Второе деление выполняется под символом b: суммы частот Σ1 и Σ2 вновь равны между собой и равны 0,25. Тогда кодовой комбинации символов верхней части дописывается 1, а нижней части – 0. Таким образом, к полученным на первом шаге фрагментам кода, равным 0, добавляются новые символы:

Поскольку верхняя часть нового списка содержит только один символ (b), формирование кода для него закончено (соответствующая строка таблицы вновь выделена заливкой).

Третье деление проходит между символами c и d: к кодовой комбинации символа c приписывается 1, коду символа d приписывается 0:

Поскольку обе оставшиеся половины исходного списка содержат по одному элементу, работа со списком в целом заканчивается.

Таким образом, получили коды:

Определим эффективность построенного кода по формуле:

lср = 0,5*1 + 0,25*01 + 0,125*3 + 0,125*3 = 1,75.

Поскольку при кодировании четырех символов кодом постоянной длины требуется два двоичных разряда, сэкономлено 0,25 двоичного разряда в среднем на один символ.

Этот метод имеет два преимущества по сравнению с методом Шеннона-Фано: он устраняет неоднозначность кодирования, возникающую из-за примерного равенства сумм частот при разделении списка на две части (линия деления проводится неоднозначно), и имеет, в общем случае, большую эффективность кода.

Исходное множество символов упорядочивается по не возрастанию частоты и выполняются следующие шаги:

1) объединение частот:

· две последние частоты списка складываются, а соответствующие символы исключаются из списка;

· оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается;

· предыдущие шаги повторяются до тех пор, пока ни получится единица в результате суммирования и список ни уменьшится до одного символа;

2) построение кодового дерева:

· строится двоичное кодовое дерево: корнем его является вершина, полученная в результате объединения частот, равная 1; листьями – исходные вершины; остальные вершины соответствуют либо суммарным, либо исходным частотам, причем для каждой вершины левая подчиненная вершина соответствует большему слагаемому, а правая – меньшему; ребра дерева связывают вершины-суммы с вершинами-слагаемыми. Структура дерева показывает, как происходило объединение частот;

· ребра дерева кодируются: каждое левое кодируется единицей, каждое правое – нулем;

3) формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и «собирают» веса проходимых ребер.

Пример 1. Даны символы a, b, c, d с частотами fa = 0,5; fb = 0,25; fc = 0,125; fd= 0,125. Построить эффективный код методом Хаффмена.

1) объединение частот (результат объединения двух последних частот в списке выделен в правом соседнем столбце заливкой):

2) построение кодового дерева:

3) формирование кода:

Как видно, полученные коды совпадают с теми, что были сформированы методом Шеннона-Фано, следовательно, они имеют одинаковую эффективность.

Источник

Основы эффективного кодирования

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

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

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

При передаче дискретных сообщений по каналам связи буквы алфавита обычно отображаются кодовыми комбинациями постоянной длины (равномерное кодирование). Длина кодовой комбинации n выбирается из условия

Применение эффективного кодирования позволяет уменьшить среднее число l двоичных символов на букву сообщения:

(3.1)

где -длина кодовой комбинации, отображающей i-ю букву;

-вероятность появления i-ой буквы.

Уменьшение средней длины кодовой комбинации, отображающей букву сообщения, позволяет увечить скорость передачи.

Эффективное кодирование базируется на теореме Шеннона для каналов без шума.

(3.2)

Под энтропией дискретного источника Н(А) понимается среднее количество информации, приходящееся на одну букву сообщения:

(3.3)

Для по­строе­ния эф­фек­тив­ных ко­дов наи­боль­шее рас­про­стра­не­ние на­шли ме­то­ди­ки Шен­но­на-Фа­но и Хаф­фме­на.

3.2. Ме­тод Шен­но­на-Фа­но

1. Все К букв ал­фа­вита рас­по­ла­га­ют­ся в один стол­бец в по­ряд­ке убы­ва­ния их ве­ро­ят­но­стей.

2. Эти бу­к­вы раз­би­ва­ют­ся на две груп­пы: верх­нюю и ниж­нюю так, что­бы сум­мы ве­ро­ят­но­стей в ка­ж­дой из групп бы­ли по воз­мож­но­сти бли­же друг к дру­гу.

4. Вновь ка­ж­дую из по­лу­чен­ных групп де­лят на две час­ти с близ­ки­ми, по воз­мож­но­сти, сум­мар­ны­ми ве­ро­ят­но­стя­ми.

5. Верх­ним час­тям вновь об­ра­зо­ван­ных групп при­сваи­ва­ет­ся “1”, а ниж­ним — “0”. Эти зна­че­ния эле­мен­тов счи­та­ют­ся вто­ры­ми раз­ря­да­ми фор­ми­руе­мых ко­до­вых ком­би­на­ций.

Эти про­це­ду­ры по­вто­ря­ют­ся до тех пор, по­ка в ка­ж­дой груп­пе ос­та­нет­ся по од­ной бу­к­ве.

По­строе­ние ко­да Шен­но­на-Фа­но для ан­самб­ля из 8 букв при­ве­де­но в

При рав­но­мер­ном ко­ди­ро­ва­нии 8-ми букв ко­до­вые ком­би­на­ции со­дер­жат по три дво­ич­ных раз­ря­да. При ис­поль­зо­ва­нии ко­да Шен­но­на-Фа­но сред­няя дли­на ко­до­вой ком­би­на­ции со­став­ля­ет:

i=1Это мень­ше, чем при рав­но­мер­ном ко­ди­ро­ва­нии и не очень да­ле­ко от эн­тро­пии к

3.3. Ме­тод Хаф­фме­на

1. Бу­к­вы ал­фа­ви­та вы­пи­сы­ва­ют­ся столб­цом в по­ряд­ке убы­ва­ния ве­ро­ят­но­стей.

2. На­хо­дит­ся сум­ма ве­ро­ят­но­стей по­след­них двух букв.

3. Ве­ро­ят­но­сти букв, не уча­ст­вую­щих в объ­е­ди­не­нии, и по­лу­чен­ная сум­мар­ная ве­ро­ят­ность сно­ва рас­по­ла­га­ют­ся столб­цом в по­ряд­ке убы­ва­ния.

Вто­рой и тре­тий эта­пы по­вто­ря­ют­ся до тех пор, по­ка сум­мар­ная ве­ро­ят­ность не бу­дет рав­на еди­ни­це.

По­строе­ние ко­да Хаф­фме­на для ан­самб­ля из 8 букв при­ве­де­но в таб­л. 3.2.

Таб­ли­ца 3.2. Построение кода Хаффмена

Ко­до­вое де­ре­во стро­ит­ся сле­дую­щим об­ра­зом (рис.3.1). Сна­ча­ла на­хо­дят­ся бу­к­вы с наи­мень­ши­ми ве­ро­ят­но­стя­ми 0,07 (A₇) и 0,03 (A₈), за­тем от них про­во­дят­ся ли­нии к точ­ке, изо­бра­жаю­щей “ук­руп­нен­ный” сим­вол с сум­мар­ной ве­ро­ят­но­стью 0,10. На ри­сун­ке эта про­це­ду­ра обо­зна­че­на циф­рой I. За­тем бе­рут­ся две наи­мень­шие ве­ро­ят­но­сти со зна­че­ни­ем 0,10 и по­лу­ча­ют но­вый “ук­руп­нен­ный” сим­вол с ве­ро­ят­но­стью 0,20 (про­це­ду­ра I I). Те­перь наи­мень­шие ве­ро­ят­но­сти име­ют сим­во­лы А₄ (0,13) и А₅ (0,12). Со­еди­няя их ли­ния­ми фор­ми­ру­ют но­вый сим­вол с сум­мар­ной ве­ро­ят­но­стью 0,25 (про­це­ду­ра I I I).

Эти про­це­ду­ры по­вто­ря­ют­ся до тех пор, по­ка ли­нии от ос­нов­ных и “ук­руп­нен­ных” сим­во­лов не со­еди­нят­ся в точ­ке с сум­мар­ной ве­ро­ят­но­стью, рав­ной 1. Верх­нюю ли­нию обо­зна­ча­ют циф­рой “1”, а ниж­нюю “0”. Любая кодовая комбинация представляет собой последовательность “1” и “0”, ко­то­рые встре­ча­ют­ся на пу­ти от вер­ши­ны де­ре­ва с ве­ро­ят­но­стью 1 к точ­ке, изо­бра­жаю­щей нуж­ную бу­к­ву.

Срав­не­ние рас­смот­рен­ных ме­то­дик по­строе­ния эф­фек­тив­ных ко­дов по­зво­ля­ет сде­лать вы­вод, что ме­то­ди­ка Хаф­фме­на бо­лее удоб­на для прак­ти­че­ско­го ис­поль­зо­ва­ния. В об­щем слу­чае код Хаф­фме­на эко­но­мич­нее ко­да Шен­но­на-Фа­но.

Рис. 3.1 Кодовое дерево.

Не­труд­но за­ме­тить, что со­кра­ще­ние сред­ней дли­ны ко­до­вой ком­би­на­ции эф­фек­тив­но­го ко­да по срав­не­нию с рав­но­мер­ны­ми ко­да­ми дос­ти­га­ет­ся бла­го­да­ря при­свое­нию бо­лее ве­ро­ят­ным бу­к­вам ко­рот­ких ко­до­вых ком­би­на­ций, а ме­нее ве­ро­ят­ным бу­к­вам — бо­лее длин­ных ко­до­вых ком­би­на­ций. Та­ким об­ра­зом, эф­фек­тив­ность рас­смат­ри­вае­мых ко­дов свя­за­на с раз­ли­чи­ем в чис­ле сим­во­лов ко­до­вых ком­би­на­ций. Это при­во­дит к оп­ре­де­лен­ным труд­но­стям при де­ко­ди­ро­ва­нии. Ко­неч­но, для раз­ли­чия ко­до­вых ком­би­на­ций мож­но ста­вить раз­де­ли­тель­ный сим­вол, но при этом су­ще­ст­вен­но сни­жа­ет­ся эф­фект, ко­то­рый дос­ти­га­ет­ся ис­поль­зо­ва­ни­ем не­рав­но­мер­ных ко­дов, так как сред­няя дли­на ко­до­вой ком­би­на­ции, по су­ще­ст­ву, уве­ли­чи­ва­ет­ся на один сим­вол. Бо­лее ра­зум­ным яв­ля­ет­ся обес­пе­че­ние од­но­знач­но­го де­ко­ди­ро­ва­ния без вве­де­ния раз­де­ли­тель­ных сим­во­лов. Для это­го эф­фек­тив­ный код стро­ят так, что­бы ни од­на ком­би­на­ция ко­да не сов­па­да­ла с пер­выми сим­во­ла­ми бо­лее длин­ной ко­до­вой ком­би­на­ции. Ко­ды, удов­ле­тво­ряю­щие это­му ус­ло­вию, на­зы­ва­ют­ся пре­фикс­ны­ми.

Ко­ды, пред­став­ляю­щие пер­вич­ные ал­фа­ви­ты с не­рав­нове­ро­ят­ны­ми сим­во­ла­ми, имею­щие ми­ни­маль­ную сред­нюю дли­ну ко­до­во­го сло­ва, на­зы­ва­ют­ся оптимальными неравномерными ко­да­ми (ОНК).

Мак­си­маль­но эф­фек­тив­ны­ми бу­дут те ОНК, у ко­то­рых эн­тро­пия дис­крет­но­го ис­точ­ни­ка Н(А) чис­лен­но рав­на сред­не­му чис­лу дво­ич­ных сим­во­лов на бу­к­ву l:

или с уче­том (3.1) и (3.3)

Оче­вид­но, что это ра­вен­ст­во бу­дет иметь ме­сто толь­ко то­гда, ко­гда

Ве­ли­чи­на l точ­но рав­на Н(А), ес­ли ве­ро­ят­ности р_i пред­став­ляют со­бой це­ло­чис­лен­ные от­ри­ца­тель­ные сте­пе­ни двой­ки. Ес­ли это не вы­пол­ня­ет­ся, то l>Н(А) и со­глас­но ос­нов­ной тео­ре­ме ко­ди­ро­ва­ния Шен­но­на для ка­на­лов без шу­мов сред­няя дли­на ко­до­вой ком­би­на­ции при­бли­жа­ет­ся к эн­тро­пии ис­точ­ни­ка со­об­ще­ний по ме­ре ук­руп­не­ния ко­ди­руе­мых бло­ков.

Для оцен­ки эф­фек­тив­но­сти ОНК пред­на­зна­че­ны сле­дую­щие ха­рак­те­ри­сти­ки.

1. Ко­эф­фи­ци­ент ста­ти­сти­че­ско­го сжа­тия.

l = (3.8)

Он ха­рак­те­ри­зу­ет умень­ше­ние ко­ли­че­ст­ва дво­ич­ных сим­во­лов на бу­к­ву ал­фа­ви­та при при­ме­не­нии ОНК по срав­не­нию с при­ме­не­ни­ем ме­то­дов не­ста­тисти­че­ско­го ко­ди­ро­ва­ния.

2. Ко­эф­фи­ци­ент от­но­си­тель­ной эф­фек­тив­но­сти.

l=

Этот ко­эф­фи­ци­ент по­ка­зы­ва­ет, на­сколь­ко устраняется ста­ти­сти­че­ская из­бы­точ­ность пе­ре­да­вае­мо­го со­об­ще­ния.

Ме­то­ды уст­ра­не­ния из­бы­точ­но­сти по­зво­ля­ют эф­фек­тив­но ис­поль­зо­вать про­пу­ск­ную спо­соб­ность ка­на­ла свя­зи. Они по­лез­ны так­же в тех слу­ча­ях, ко­гда тре­бу­ет­ся хра­нить боль­шой объ­ем ин­фор­ма­ции в раз­лич­ных за­по­ми­наю­щих уст­рой­ст­вах. Эко­но­мия в про­пу­ск­ной спо­соб­но­сти ка­на­ла или в объ­е­ме за­по­ми­наю­ще­го уст­рой­ст­ва при­во­дит к сни­же­нию стои­мо­сти, со­кра­ще­нию раз­ме­ров и ве­са ап­па­ра­ту­ры. Рас­смот­рен­ные ме­то­ды ко­ди­ро­ва­ния по­лу­чи­ли при­ме­не­ние при передаче факсимильных сообщений.

Источник

Эффективное кодирование

3. Эффективное кодирование

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

Например, при двоичном кодировании 32 букв русского алфавита используется q = log₂32 = 5 разрядов, на чем и основывается телетайпный код.

Кроме двоичных кодов, наибольшее распространение получили восьмеричные коды.

Пусть, например, необходимо закодировать алфавит, состоящий из 64 букв. Для этого потребуется q = log₂64 = 6 двоичных разрядов или q = log₈64 = 2 восьмеричных разрядов. При этом буква с номером 13 при двоичном кодировании получает код 001101, а при восьмеричном кодировании 15.

Часто используются двоично-десятичные коды, в которых цифры десятичного номера буквы представляются двоичными кодами. Так, например, для рассматриваемого примера буква с номером 13 кодируется как 0001 0011. Ясно, что при различной вероятности появления букв исходного алфавита равномерный код является избыточным, т.к. его энтропия (полученная при условии, что все буквы его алфавита равновероятны): log_km = H₀

всегда больше энтропии H = log m данного алфавита (полученной с учетом неравномерности появления различных букв алфавита, т.е. информационные возможности данного кода используются не полностью).

Например, для телетайпного кода Н0 = log_k m = log₂32 = 5 бит, а с учетом неравномерности появления различных букв исходного алфавита Н » 4,35 бит. Устранение избыточности достигается применением неравномерных кодов, в которых буквы, имеющие наибольшую вероятность, кодируются наиболее короткими кодовыми последовательностями, а более длинные комбинации присваиваются редким буквам. Если i-я буква, вероятность которой Р_i, получает кодовую комбинацию длины q_i, то средняя длина комбинации

Считая кодовые буквы равномерными, определяем наибольшую энтропию закодированного алфавита как q_ср log m, которая не может быть меньше энтропии исходного алфавита Н, т.е. q_ср log m ³ Н.

При двоичном кодировании (m=2) приходим к соотношению q_ср ³ Н, или

Чем ближе значение q_ср к энтропии Н, тем более эффективно кодирование. В идеальном случае, когда q_ср » Н, код называют эффективным.

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

При построении неравномерных кодов необходимо обеспечить возможность их однозначной расшифровки. В равномерных кодах такая проблема не возникает, т.к. при расшифровке достаточно кодовую последовательность разделить на группы, каждая из которых состоит из q элементов. В неравномерных кодах можно использовать разделительный символ между буквами алфавита (так поступают, например, при передаче сообщений с помощью азбуки Морзе).

Если же отказаться от разделительных символов, то следует запретить такие кодовые комбинации, начальные части которых уже использованы в качестве самостоятельной комбинации. Например, если 101 означает код какой-то буквы, то нельзя использовать комбинации 1, 10 или 10101.

Практические методы оптимального кодирования просты и основаны на очевидных соображениях ( метод Шеннона – Фано ).

Пример16: Провести эффективное кодирование ансамбля из восьми знаков:

1234x10,251120,50,50x20,251020,50,50x30,1501130,450,41x40,1501030,450,41x50,05001140,20,22x60,05001040,20,22x70,05000140,20,22x80,05000040,20,22

= 2,7

Как видно, q_ср = H, следовательно, полученный код является оптимальным.

Решение: При обычном (не учитывающем статистических характеристик) двоичном кодировании с использованием k=2 знаков при построении равномерного кода количество элементов в кодовой последовательности будет q ³ log_k m = log₂ 8 = 3, т.е. для представления каждого знака использованного алфавита потребуется три двоичных символа.

1234567x11/21x21/401x31/8001x41/160001x51/3200001x61/64000001x71/1280000001x81/1280000000

Так как вероятности знаков представляют собой отрицательные целочисленные степени двойки, то избыточность при кодировании устранена полностью.

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

Вычислим среднее число символов на знак:

Кодовые комбинацииномер разбиения12345x10,2211x20,20101x30,16100x40,1601x50,10001x60,100001x70,0400001x80,0200000

Решение: 1. Средняя длина кодовых комбинаций

Источник