Шуугиангүй кодчилох теорем

Шуугиангүй кодлох теорем гэж юу вэ?

Эх үүсвэрээс мэдээллийг хэрхэн үр дүнтэй дамжуулахад үүсвэрийн тодорхойгүй байдалд үндсэн хязгаарлалтыг өгдөг. 
Энэ нь кодлогдсон үгийн дундаж уртыг багасгадаг. Үүсвэрээс гарч байгаа үгийн цацалтын магадлалаас хамаарч кодлогдсон 
үгийн уртын хүлээгдсэн утга багасах юм.

ƒ : W → ∑*   гэсэн m ширхэг File:Noiseless1.JPG үгүүдийг агуулсан  W,
File:Noiseless9.JPG кодлогдсон үгүүд ба тэдгээрийн урт File:Noiseless2.JPG  авъя. 
Эх үүсвэрээс гарах File:Noiseless1.JPG үг тус бүрийн магадлалыг File:Noiseless3.JPGгэж үзвэл

Кодлогдсон үгийн дундаж урт нь File:Noiseless4.JPG байна.

Теорем:
Х нь санах ойгүй үүсгүүр бөгөөд түүний тодорхойгүй байдал H(X) юм. 
Тэмдэгт мөр рүү нэгэн утгатайгаар задрах код ƒ : W → ∑*  нь ∑ (|∑| > 1)  цагаан толгойн олонлогоос үүснэ. 
Уг цагаан толгойн олонлог ∑ (|∑| > 1) нь File:Noiseless6.JPGнөхцлийг хангах дундаж урттай  байх ёстой. 
Үүнээс File:Noiseless7.JPGнөхцлийг хангах ямар нэг ƒ кодлолт оршин байна.   
Тодорхойгүй байдал ньFile:Noiseless8.JPG томъёологдоно.

Тайлбар: Шуугиангүй гэдэг нь ямар нэг алдаагүй гэж үзэж байгаа.

Хэрэглээ

Шуугиангүй кодлох теорем нь мэдээллийн илүүдлийг багасгаж, өгөгдлийг шахан дамжуулах хурдыг нэмэгдүүлэхэд хэрэглэгддэг. Өгөгдлийг шахахад ямар нэг математик загвар хэрэгтэй. Claude Shannon 1948 онд математикийн хүрээнд өгөгдлийн шахах загварыг тогтоосон.

Жишээ:

Үүсвэрээс ¼ магадлалтай cat, 1/8 магадлалтай dog, 1/8 магадлалтай elephant, ½  магадлалтай zebra үгүүдийг авъя. 
Кодын цагаан толгой  ∑={0,1}, f  кодлогдсон үгүүд нь дараах байдлаар тодорхойлогдсон
f(‘cat’) = ‘011’
f(‘dog’) = ‘01’
f(‘elephant’) = ‘0’
f(‘zebra’) = ‘111’
Кодлогдсон үгийн дундаж уртыг тодорхойльё.
Дундаж урт = P(‘cat’) • урт(f(‘cat’)) + P(‘dog’) • урт(f(‘dog’)) + P(‘elephant’) • урт(f(‘elephant’)) + P(‘zebra’) • урт(f(‘zebra’)) = P(‘cat’) • урт(‘011’) + P(‘dog’) • урт(‘11’) + P(‘elephant’) • урт(‘0’) +
P(‘zebra’) • урт(‘111’)  = P(‘cat’) • 3 + P(‘dog’) • 2 + P(‘elephant’) • 1 + P(‘zebra’) • 3 = ¼ • 3 + 1/8 •2 + 1/8 • 1 + 1/2 •3 = 21/8 = 2.625
Уг кодчилол нь 2.625 дундаж урттай 
Тэмдэглэхэд үүсвэрийн үгүүдийн урт энэ тооцоололд нөлөөлөхгүй.
|∑| - төгсгөлөг элементтэй ∑ олонлогийн элементийн тоо.
Ангилал:Мэдээллийн онол
Ангилал:Кодын онол
Ангилал:Математикийн теорем
Ангилал:Өгөгдөл