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

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

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

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

Требуется закодировать это сообщение, т.е. указать правило сопоставления каждой букве первичного алфавита последовательности «0» и «1», образующих вторичный алфавит.

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

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

(3.1)

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

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

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

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

Согласно этой теореме (основной теореме кодирования), сообщения, составленные из букв некоторого алфавита, можно закодировать так, что среднее число l двоичных символов, приходящихся на букву, будет сколь угодно близко к энтропии источников этих сообщений Н(А), но не менее этой величины, т.е.

(3.2)

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

(3.3)

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

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

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

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

3. Для букв верх­ней груп­пы в ка­че­ст­ве пер­во­го сим­во­ла ко­до­вой ком­би­на­ции вы­би­ра­ет­ся “ 1 ”, а для ниж­ней - “ 0 ”.

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

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

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

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

табл. 3.1.

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

к

l =ån_i p_i=0,2·2+0,2· 3+0,15·3+0,13·3+0,12·3+0,10·3+0,07·4+0,03·4=2,9

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

Н(А)=-å р_i log₂p_i=2,806 бит/буква. (3.4)

i=1

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

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

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

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

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

Таб­ли­ца 3.1.Построение кода Шеннона - Фано

Бу­к­вы	Рi	Де­ле­ние букв на груп­пы	Код Шен­но­на-Фа­но
А1	0,20
А2	0,20
А3	0,15
А4	0,13
А5	0,12
А6	0,10
А7	0,07
А8	0,03

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

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

Бу­к­вы	Pi	Вспо­мо­га­тель­ные столб­цы
		1 2 3 4 5 6 7
А1	0,20	0,20 0,20 0,25 0,35 0,40 0,60 1
А2	0,20	0,20 0,20 0,20 0,25 0,35 0,04
А3	0,15	0,15 0,20 0,20 0,20 0,25
А4	0,13	0,13 0,15 0,20 0,20
А5	0,12	0,12 0,13 0,15
А6	0,10	0,10 0,12
А7	0,07	0,10
А8	0,03

Ко­до­вое де­ре­во стро­ит­ся сле­дую­щим об­ра­зом (рис.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 к точ­ке, изо­бра­жаю­щей нуж­ную бу­к­ву.

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

Бу­к­ва	pi	Ко­до­вое де­ре­во	Код	ni	nipi
А1	0,2				0,4
А2	0,2				0,6
А3	0,15				0,45
А4	0,13				0,39
А5	0,12				0,36
А6	0,10				0,3
А7	0,07				0,28
А8	0,03				0,12

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

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

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

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

Н(А)= l (3.5)

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

к к

ån_ip_i=-åp_ilog­₂p_i (3.6)

i=1 i=1

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

n_i=-lo­g₂p_i=log₂(1/p_i) (3.7)

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

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

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

Н_max (А) log₂К

l = (3.8)

к ån_i p_i

i=1

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

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

Н(А)

l =

К_э (3.9)

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

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