Шуугиант кодын онол

Мэдээллийн онолд шуугиантай кодлох теорем нь (Англи: Noisy-channel coding theorem) (Шенноний теорем) холбооны суваг дахь шуугианы зэргийг тодорхойлдог. Шуугианы зэрэг гэдэг нь суваг дахь бараг алдаагүй утгаас тооцоолж болохуйц хамгийн их утга хүртэлх холболт үүсгэх боломжтой дискрет өгөгдөл (тоон мэдээлэл)юм. Шуугиантай кодлох теоремыг Клауд Шеннон 1948 онд Харри Неквист болон Ральф Хартлей нарын эхэн үеийн судалгаан дээр тулгуурлан дэвшүүлсэн юм.

Холбооны сувгийн Шенноны хязгаар болон Шенноны багтаамж гэдэг нь тодорхой шуугианы түвшин дэх сувгийн хамгийн их мэдээлэл дамжуулах утга юм.

Тойм

Клауд Шенноний тодорхойлсноор энэхүү теором нь шуугианы интерференс болон өгөгдлийн гажуудлын түвшингээс ялгаатай нь алдаа засах аргуудын хамгийн их боломжит бүтээмжийг илэрхийлдэг. Харилцаа холбооны болон өгөгдөл хадгалалтын салбарт Шенноний теоремийг ашигладаг. Энэхүү теорем нь орчин үеийн мэдээллийн онолын салбарт чухал ач холбогдолтой. Шеннон энэхүү теоремийн баталгааны зөвхөн ерөнхий тоймыг гаргасан бөгөөд 1954 онд Амиэл Фейнстейн анхны нарийн баталгааг гаргасан юм.

Шенноний теоремд тодорхойлсноор шуугиантай суваг С сувгийн багтаамжтай ба мэдээллээ R хурдаар дамжуулдаг бөгөөд $R<C$ бол хүлээн авагч дээрх тухайн кодын алдаа гарах магадлал дурын бага байна. Энэ нь онолын хувьд С-ээс бага ямар ч хурдаар мэдээллийг бараг алдаагүйгээр дамжуулах боломжтой гэсэн үг.

Эсрэгээ $R>C$ бол алдаа гарах магадлал бага байх боломжгүй. Бүх кодуудын алдаа гарах магадлал нь эерэг хамгийн бага түвшингээсээ их болж энэ түвшин нь дамжуулах хурд ихсэхэд мөн нэмэгдэнэ. Ийм учраас сувгаар дамжуулах хурд нь сувгийн багтаамжаас их үед мэдээллийг найдвартай дамжуулж чадахгүй гэсэн үг. Шенноний теоремд хурд багтаамж хоёр тэнцүү байх ховор нөхцөлийн тухай дурьдагдаагүй байдаг.

Гаусын шуугианаар сувгийн өргөн хязгаарлагддаг бол Шеннон-Хартлейгийн теоремыг ашиглан сувгийн багтаамж С-г сувгийн физик төлөв дээр тулгуурлан тооцоолж болдог.

"Мессежийг 3 удаа илгээгээд илгээсэн мессежүүд нь ялгаатай байвал хамгийн бага алдаатай 2 мессежийг сонгох" мэтийн энгийн схемүүд нь үр ашиггүй алдаа-засах арга бөгөөд өгөгдлийн блок алдаатай дамжигддаг. Рийд-Соломоны код, бага-нягттай тэгш сондгой шалгах код(low-density parity-check (LDPC)), турбо код зэрэг нь онолын хувьд Шенноний хязгаар руу маш их дөхдөг боловч тооцоолол хийхэд маш төвөгтэй. Гэхдээ эдгээр өндөр үр дүнтэй кодуудыг өнөөгийн хүчирхэг процессоруудыг ашиглан тооцоолсноор Шенноний хязгаарт хүрэхэд тун ойртоод байна.

Математик тооцоолол

Шенноний теорем (1948 он):

1. Дискрет санах ойгүй суваг бүрийн багтаамж нь:

$\ C=\sup _{p_{X}}I(X;Y)\,$

2. Хэрвээ битийн алдаа гарах магадлал p_b ба хурд R(p_b) хүрэх боломжтой бол:

$R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.$

ба

$H_{2}(p_{b})$ нь хоёртын ентропи функц болно.

$H_{2}(p_{b})=-\left[p_{b}\log _{2}{p_{b}}+(1-p_{b})\log _{2}({1-p_{b}})\right]$

3. Ямар ч p_b-н хувьд хурд R(p_b)-с их байх боломжгүй.

Дискрет санах ойгүй сувгийн баттай эсрэг нөхцөл

Баттай эсрэг теоремийг 1957 онд Волфовиц баталсан ба түүний тодорхойлсноор

$P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-{\frac {n(R-C)}{2}}}$

А нь ямар нэг хязгаартай эерэг тогтмол

Тогтвортой бус санах ойгүй сувгуудын сувгийн кодын теорем

Сувгийг санах ойгүй гэж үзэж байгаа боловч дамжуулалтын магадлал нь хугацааны туршид өөрчлөгддөг. Тийм учраас сувгийн багтаамж нь:

$C=\lim \inf \max _{p^{(}X_{1}),p^{(}X_{2}),...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i}).$ байна.