КОДИ́РОВАНИЕ

КОДИ́РОВАНИЕ, опе­ра­ция ото­жде­ст­в­ле­ния сим­во­лов или групп сим­во­лов од­но­го ко­да с сим­во­ла­ми или груп­па­ми сим­во­лов дру­го­го ко­да. Не­об­хо­ди­мость К. воз­ни­ка­ет пре­ж­де все­го из по­треб­но­сти при­спо­со­бить фор­му со­об­ще­ния к дан­но­му ка­на­лу свя­зи или к.-л. дру­го­му уст­рой­ст­ву, пред­на­зна­чен­но­му для пре­об­ра­зо­ва­ния или хра­не­ния ин­фор­ма­ции. Так, с по­мо­щью те­ле­граф­ных ко­дов со­об­ще­ния, пред­став­лен­ные в ви­де по­сле­до­ва­тель­но­сти букв и цифр, пре­об­ра­зу­ют­ся в оп­ре­де­лён­ные ком­би­на­ции то­чек и ти­ре. Др. це­лью К. яв­ля­ет­ся за­щи­та со­об­ще­ний от не­санк­цио­ни­ро­ван­но­го дос­ту­па (см. Крип­то­гра­фия).

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

Приё­мы, при­ме­няе­мые в тео­рии ин­фор­ма­ции для дос­ти­же­ния ука­зан­но­го со­гла­со­ва­ния, мож­но по­яс­нить на при­ме­ре по­строе­ния эко­ном­ных дво­ич­ных ко­дов. Пусть ка­нал свя­зи мо­жет пе­ре­да­вать толь­ко сим­во­лы 0 и 1, за­тра­чи­вая на ка­ж­дый од­но и то же вре­мя $t$. Для умень­ше­ния вре­ме­ни пе­ре­да­чи (или для уве­ли­че­ния её ско­ро­сти) це­ле­со­об­раз­но до пе­ре­да­чи ко­ди­ро­вать со­об­ще­ния та­ким об­ра­зом, что­бы сред­няя дли­на $L$ ко­до­во­го обо­зна­че­ния бы­ла наи­мень­шей. Пусть $x_1,x_2,…, x_n$ обо­зна­ча­ют воз­мож­ные со­об­ще­ния не­ко­то­ро­го ис­точ­ни­ка, а $p_1,p_2,…, p_n$ – со­от­вет­ст­вую­щие им ве­ро­ят­но­сти. То­гда, как ус­та­нав­ли­ва­ет­ся в тео­рии ин­фор­ма­ции, при лю­бом спо­со­бе К.

$$L\geq H,\tag 1 $$где $H= \sum_{i=1}^n p_i \text{log}_2 (1/p_i)$ – эн­тро­пия источ­ни­ка. Ра­вен­ст­во в фор­му­ле $(1)$ мо­жет не дос­ти­гать­ся. Од­на­ко при лю­бых $p_1,p_2,…, p_n$ су­ще­ст­ву­ет ме­тод К. (ме­тод Шен­но­на – Фэ­но), для ко­то­ро­го $$L\leq H+1.\tag 2 $$

Ме­тод со­сто­ит в том, что со­об­ще­ния рас­по­ла­га­ют­ся в по­ряд­ке убы­ва­ния ве­ро­ятно­стей и по­лу­чен­ный ряд де­лит­ся на две час­ти с сум­мар­ны­ми ве­ро­ят­но­стя­ми, по воз­мож­но­сти близ­ки­ми друг к дру­гу. В ка­че­ст­ве пер­во­го дво­ич­но­го зна­ка при­ни­ма­ют 0 в 1-й час­ти и 1 – во 2-й. Та­ким же об­ра­зом де­лят по­по­лам ка­ж­дую из час­тей и вы­би­ра­ют вто­рой дво­ич­ный знак и т. д., по­ка не при­дут к час­тям, со­дер­жа­щим толь­ко по од­но­му со­об­ще­нию.

При­мер 1. Пусть $n=4 $ и $p_1 $=⁹/₁₆, $p_2=p_3=$³/₁₆, $p_4 $=¹/₁₆. При­ме­не­ние ме­то­да ил­лю­ст­ри­ру­ет­ся таб­ли­цей

В дан­ном слу­чае $L=1 \cdot \frac{9}{16}+2 \cdot \frac{3}{16}+3 \cdot \frac{3}{16}+3 \cdot \frac{1}{16}=\frac{27}{16}= 1, 688, $

при­чём ни­ка­кой дру­гой код не да­ёт для $L$ мень­ше­го зна­че­ния. В то же вре­мя $H=1,623 $. Всё ска­зан­ное при­ме­ни­мо и к слу­чаю, ко­гда ал­фа­вит но­во­го ко­да со­дер­жит не две, как пред­по­ла­га­лось вы­ше, а $m>2 $ букв. При этом ве­ли­чи­на $H$ в фор­му­лах $(1)$ и $(2)$ долж­на быть за­ме­не­на ве­ли­чи­ной $H/\text{log}_2m$.

За­да­ча о сжа­тии за­пи­си со­об­ще­ний в дан­ном ал­фа­ви­те (т. е. за­да­ча об умень­ше­нии из­бы­точ­но­сти) мо­жет быть ре­ше­на на ос­но­ве ме­то­да Шен­но­на – Фэ­но. Ес­ли со­об­ще­ния пред­став­ле­ны по­сле­до­ва­тель­но­стя­ми дли­ны $N$ букв из $m$-бу­к­вен­но­го ал­фа­ви­та, то их сред­няя дли­на $L_N$ по­сле К. все­гда удов­ле­тво­ря­ет не­ра­вен­ст­ву
$$L_N\geq NH/\text{log}_2m, $$где $H$ – эн­тро­пия ис­точ­ни­ка на бу­к­ву. Кро­ме то­го, при сколь угод­но ма­лом $ε>0 $ мож­но до­бить­ся вы­пол­не­ния при всех дос­та­точ­но боль­ших $N$ не­ра­вен­ст­ва$$L_N\lt N(H/\text{log}_2m+\varepsilon). \tag 3$$

С этой це­лью ис­поль­зу­ют К. бло­ка­ми: по дан­но­му $ε$ вы­би­ра­ют дос­та­точ­но боль­шое на­ту­раль­ное чис­ло $s$ и де­лят ка­ж­дое со­об­ще­ние на рав­ные час­ти – бло­ки, со­дер­жа­щие по $s$ букв. За­тем эти бло­ки ко­ди­ру­ют ме­то­дом Шен­но­на – Фэ­но в тот же ал­фа­вит. То­гда при дос­та­точ­но боль­ших $N$ бу­дет вы­пол­не­но не­ра­вен­ст­во $(3)$. Спра­вед­ли­вость это­го ут­вер­жде­ния лег­че все­го по­нять, рас­смат­ри­вая слу­чай, ко­гда ис­точ­ни­ком яв­ля­ет­ся по­сле­до­ва­тель­ность не­за­ви­си­мых сим­во­лов 0 и 1, по­яв­ляю­щих­ся со­от­вет­ст­вен­но с ве­ро­ят­но­стя­ми $p$ и $q$, $0 \lt p \lt 1$. Эн­тро­пия на блок рав­на $s$-крат­ной эн­тро­пии на од­ну бу­к­ву, т. е. рав­на $sH=s (p \text{log}_{2}1/p+q\text{log}_{2}1/q)$. Ко­до­вое обо­зна­че­ние бло­ка тре­бу­ет в сред­нем не бо­лее $sH+1 $ дво­ич­ных зна­ков. По­это­му для со­об­ще­ния, со­стоя­ще­го из $N$ букв,
$$L_N\leq(1+N/s) (sH+1)=N (H+1/s) (1+s/H), $$что при дос­та­точ­но боль­ших $s$ и $N/s$ при­во­дит к не­ра­вен­ст­ву $(3)$. При та­ком К. эн­тро­пия на бу­к­ву при­бли­жа­ет­ся к сво­ему макс. зна­че­нию – еди­ни­це, а из­бы­точ­ность – к ну­лю.

При­мер 2. Пусть ис­точ­ни­ком со­об­ще­ний яв­ля­ет­ся по­сле­до­ва­тель­ность не­за­ви­си­мых зна­ков 0 и 1, в ко­то­рой ве­роят­ность по­яв­ле­ния ну­ля рав­на $p$=³/₄, а еди­ни­цы – $q$=¹/₄. Здесь эн­тро­пия $H$ на бу­к­ву рав­на 0,811, а из­бы­точ­ность – 0,189. Наи­мень­шие бло­ки ($s=2$ ), т. е. 00, 01, 10, 11, име­ют со­от­вет­ст­вен­но ве­ро­ят­но­сти $p^2 $=⁹/₁₆, $pq$=³/₁₆, $qp$=³/₁₆, $q^2 $=¹/₁₆. При­ме­не­ние ме­то­да Шен­но­на – Фэ­но при­во­дит к сле­дую­ще­му пра­ви­лу К.: 00→0, 01→10, 10→110, 11→111. При этом, напр., со­об­ще­ние 00111000… при­мет вид 01111100… На ка­ж­дую бу­к­ву со­об­ще­ния в преж­ней фор­ме при­ходит­ся в сред­нем 27/32=0,844 бу­к­вы в но­вой фор­ме (при ниж­ней гра­ни­це коэф. сжа­тия, рав­ной $H$=0,811). Эн­тро­пия на бу­к­ву в но­вой по­сле­до­ва­тель­но­сти рав­на 0,811/0,844=0,961, а из­бы­точ­ность рав­на 0,039.