Òåìà ¹4: Îïòèìàëüíîå (ýôôåêòèâíîå) êîäèðîâàíèå èñòî÷íèêîâ.
4.1. Ïîíÿòèå êîäèðîâàíèÿ. Êîäîâîå äåðåâî.
 ïðîöåññå êîäèðîâàíèÿ êàæäàÿ áóêâà èñõîäíîãî àëôàâèòà ïðåäñòàâëÿåòñÿ ðàçëè÷íûìè ïîñëåäîâàòåëüíîñòÿìè, ñîñòîÿùèìè èç êîäîâûõ áóêâ (öèôð). Åñëè èñõîäíûé àëôàâèò ñîäåðæèò m áóêâ, òî äëÿ ïîñòðîåíèÿ ðàâíîìåðíîãî êîäà ñ èñïîëüçîâàíèåì D êîäîâûõ áóêâ íåîáõîäèìî îáåñïå÷èòü âûïîëíåíèå ñëåäóþùåãî óñëîâèÿ:
,
ãäå n- êîëè÷åñòâî ýëåìåíòîâ êîäîâîé ïîñëåäîâàòåëüíîñòè.
Äëÿ ïîñòðîåíèÿ ðàâíîìåðíîãî êîäà äîñòàòî÷íî ïðîíóìåðîâàòü áóêâû èñõîäíîãî àëôàâèòà è çàïèñàòü èõ êîäû êàê n-ðàçðÿäíîå ÷èñëî â D-è÷íîé ñèñòåìå ñ÷èñëåíèÿ.
Çàìåòèì: ïîíÿòèå ðàâíîìåðíîãî êîäà îçíà÷àåò, ÷òî êàæäàÿ áóêâà èñõîäíîãî àëôàâèòà m êîäèðóåòñÿ êîäîâîé ïîñëåäîâàòåëüíîñòüþ îäèíàêîâîé äëèíû n.
Ïðèìåð: êîä äëèíû n=S â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ D=2 ïîçâîëÿåò ïðåäñòàâèòü 32 áóêâû ðóññêîãî àëôàâèòà ïÿòèðàçðÿäíûìè äâîè÷íûìè ÷èñëàìè.
Î÷åâèäíî, ÷òî ïðè ðàçëè÷íîé âåðîÿòíîñòè ïîÿâëåíèÿ áóêâ èñõîäíîãî àëôàâèòà ðàâíîìåðíûé êîä ÿâëÿåòñÿ èçáûòî÷íûì, òàê êàê ýíòðîïèÿ, õàðàêòåðèçóþùàÿ èíôîðìàöèîííóþ åìêîñòü ñîîáùåíèÿ ìàêñèìàëüíà ïðè ðàâíîâåðîÿòíûõ áóêâàõ èñõîäíîãî àëôàâèòà:
.
Ò.å. èíôîðìàöèîííûå âîçìîæíîñòè êîäà èñïîëüçóþòñÿ íå ïîëíîñòüþ.
Ïðèìåð: Äëÿ äâîè÷íîãî ïÿòèðàçðÿäíîãî êîäà áóêâ ðóññêîãî àëôàâèòà èíôîðìàöèîííàÿ åìêîñòü ñîñòàâëÿåò 5 áèò, =4,35 áèò.
Óñòðàíåíèå èçáûòî÷íîñòè äîñòèãàåòñÿ ïðèìåíåíèåì íåðàâíîìåðíûõ êîäîâ, â êîòîðûõ áóêâû, èìåþùèå íàèáîëüøóþ âåðîÿòíîñòü, êîäèðóþòñÿ áîëåå êîðîòêèìè êîäîâûìè ïîñëåäîâàòåëüíîñòÿìè, à áîëåå äëèííûå êîìáèíàöèè ïðèñâàèâàþòñÿ ðåäêèì, èìåþùèì ìåíüøóþ âåðîÿòíîñòü áóêâàì.
Åñëè i-àÿ áóêâà, âåðîÿòíîñòü êîòîðîé pi, ïîëó÷àåò êîäîâóþ êîìáèíàöèþ äëèíû ni, òî ñðåäíÿÿ äëèííà êîäà (êîäîâîãî ñëîâà) ðàâíà:
Ââåäåì ïîíÿòèå êîäîâîãî äåðåâà, êîòîðûì ÷àñòî ïîëüçóþòñÿ ïðè ðàññìîòðåíèè êîäîâ.
Èçâåñòíî, ÷òî ëþáóþ áóêâó (ñîáûòèå), ñîäåðæàùèåñÿ â àëôàâèòå (ñîîáùåíèè) èñòî÷íèêà, ìîæíî ðàçëîæèòü íà ïîñëåäîâàòåëüíîñòè äâîè÷íûõ ðåøåíèé ñ èñõîäàìè «äà»=1 è «íåò»=0 áåç ïîòåðè èíôîðìàöèè.
Òàêèì îáðàçîì, êàæäîé áóêâå èñõîäíîãî àëôàâèòà ìîæåò áûòü ïîñòàâëåíà â ñîîòâåòñòâèå (ïðèïèñàíà) íåêîòîðàÿ ïîñëåäîâàòåëüíîñòü äâîè÷íûõ ñèìâîëîâ – «0» èëè «1», à òàêóþ ïîñëåäîâàòåëüíîñòü íàçûâàþò êîäîâûì ñëîâîì. Ïðè ýòîì ïîòåðè èíôîðìàöèè íå ïðîèñõîäèò, òàê êàê êàæäîå ñîáûòèå ìîæåò áûòü âîññòàíîâëåíî ïî ñîîòâåòñòâóþùåìó êîäîâîìó ñëîâó.
C1,C2, C3,C4 – äåðåâî êîäîâ èìååò ðàçíóþ äëèíó êîäà (êîäîâîãî ñëîâà).