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

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

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

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

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

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

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

Хэрэглээ

Шуугиангүй кодлох теорем нь мэдээллийн илүүдлийг багасгаж, өгөгдлийг шахан дамжуулах хурдыг нэмэгдүүлэхэд хэрэглэгддэг. Өгөгдлийг шахахад ямар нэг математик загвар хэрэгтэй. 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 дундаж урттай Тэмдэглэхэд үүсвэрийн үгүүдийн урт энэ тооцоололд нөлөөлөхгүй. |∑| - төгсгөлөг элементтэй ∑ олонлогийн элементийн тоо.