Кіріспе

Бинарлы симметриялық арна (немесе BSCp) – кодтау теориясы мен ақпарат теориясында қолданылатын кең таралған байланыс арнасының моделі. Бұл модельде бергіш бір бит (нөл немесе бір) жібергісі келеді, ал қабылдағыш сол битті қабылдайды. Бит "crossover ықтималдығы" p-мен "қарсыға айналдырылады", ал қалған жағдайда дұрыс қабылданады. Бұл модель телефон желілері немесе дискілік жад сияқты әртүрлі байланыс арналарына қолданылуы мүмкін. Шулы арнаны кодтау туралы теорема BSCp-ге қатысты, ол ақпаратты арнаның сыйымдылығына дейінгі кез келген жылдамдықпен, кез келгендей төмен қателікпен беруге болатынын айтады. Арнаның сыйымдылығы – бит, мұнда – бинарлық энтропия функциясы. Форни кодын қоса алған кодтар ақпаратты арна арқылы тиімді жеткізу үшін жасалған.

Анықтама

Кроссовер ықтималдығы p-мен белгіленетін бинарлық симметриялық арна (BSCp) – бинарлық кіріс және бинарлық шығысы бар, сондай-ақ қате ықтималдығы бар арна. Яғни, егер жіберілген кездейсоқ айнымалы X, ал алынған айнымалы Y болса, онда арна шартты ықтималдықтармен сипатталады:

Егер p > 0 болса, қабылдаушы шығысты ауыстыра алады (0-ді 1 деп, ал 1-ді 0 деп түсіндіреді) және кроссовер ықтималдығы (1-p) бар эквивалентті арнаны алады.

Шулы арна кодтау теоремасы

Шеннонның шулы арна кодтау теоремасы байланыс арнасы арқылы төмен қателікпен берілуге болатын ақпарат мөлшерінің жылдамдығы туралы мәлімдейді. Біз нақты жағдайды қарастырамыз, онда шуды сипаттайтын кездейсоқ айнымалы n тәуелсіз кездейсоқ биттен тұрады (n төменде анықталады), мұнда әрбір кездейсоқ бит ғана ықтималдықпен және ғана ықтималдықпен болады. Мұны «» деп жазу арқылы көрсетеміз. Бұл теореманың мағынасы мынада: хабар , кездейсоқ кодтау функциясымен кодталған және шулы арна арқылы жіберілген кезде, егер немесе, басқаша айтқанда, арнаның жылдамдығы теоремада көрсетілген шамамен шектелген болса, бастапқы хабарды декодтау арқылы қалпына келтірудің жоғары ықтималдығы бар. Декодтау қателігінің ықтималдығы экспоненциалды түрде кішкентай.

Шеннонның сыйымдылық теоремасының керісі

Қуат теоремасының керісі, негізінен, екілік симметриялық арнада қол жеткізілетін ең жақсы жылдамдық осы екенін көрсетеді. Теореманың формальды тұжырымы:

Дегенмен, дәлелдемені түсіну үшін, жылдамдық арнаның сыйымдылығынан асып кеткенде қателер саны тез өседі екенін көрсету қажет. Идея мынада: жіберуші өлшемді хабарларды жасайды, ал арна беріліс кезінде қателер енгізеді. Егер арнаның сыйымдылығы болса, қателер саны әдетте, блок ұзындығы бар код үшін болады. Хабарламалардың ең көп саны ал, арнаның шығысындағы мүмкін мәндер саны болады. Егер кез келген екі хабарлама шатасқан жағдай туындаса, онда болады. Біз бұндай жағдайдан қашыңқы болуға тырысамыз, себебі бұл декодтау қателігінің ықтималдығын экспоненциалды түрде төмендетуге көмектеседі.

Кодтар

Жқында, бірнеше стандартты коммуникация арналарының сыйымдылығына жету үшін нақты қателерді түзету кодтарын жобалау бойынша көп жұмыс істелді және жалғасуда. Мұндай кодтарды жобалаудың себебі – кодтың жылдамдығын, ол түзетуге қабілетті қателердің үлесімен байланыстыру. Бинарлық жою арнасының немесе арна сыйымдылықтарына жақын кодтарды жобалау тәсілі – жоғары ықтималдықпен қателердің аз санын түзету және ең жоғары мүмкін жылдамдыққа қол жеткізу болды. Шеннон теоремасы бізге берілген арнада қол жеткізілетін ең жақсы жылдамдықты көрсетеді, бірақ осы жылдамдыққа жететін нақты кодтар туралы ақпарат бермейді. Шындығында, мұндай кодтар көбінесе жоғары ықтималдықпен қателердің шағын бөлігін ғана түзетуге құрылады, бірақ өте жақсы жылдамдыққа қол жеткізеді. Мұндай алғашқы кодты 1966 жылы Джордж Д. Форни жасаған. Бұл код екі түрлі кодты тізбектеу арқылы құрылған біріктірілген код.

Форнидің коды

Форни шулы арна кодтау теоремасының сыйымдылығына жету үшін тізбектес кодты құрастырды. Оның кодында, сыртқы код – бұл блок ұзындығы және өрістегі жылдамдығы бар код. Сонымен қатар, ең нашар жағдайдағы қателердің белгілі бір үлесін түзете алатын және уақыт ішінде жұмыс істейтін сыртқы кодты іздеу алгоритмі бар. Ішкі код – бұл блок ұзындығы, өлшем және жылдамдығы бар код. Сонымен қатар, бізде кодтау алгоритмі бар, оның кодтау қатесінің ықтималдығы және уақыт ішінде жұмыс істейді. Сыртқы код үшін Рид-Соломон коды бірінші болып ойға келер еді. Алайда, мұндай кодты полиномиалдық уақытта құрастыру мүмкін емес екенін көреміз. Сондықтан, екілік сызықтық код қолданылады. Ішкі код үшін шулы арна кодтау теоремасы бойынша сыйымдылыққа жақым жылдамдығы бар блок ұзындығы және өлшемі бар сызықтық кодты толық іздеу арқылы табамыз. Бұл сыйымдылыққа жақын жылдамдық. Сонымен қатар, кодтау және декодтау полиномиалдық уақытта жүзеге асырылатынын атап өтейміз. Шындығында, кодтау уақыты алса, декодтау алгоритмі уақыт алады, егер ; және .

Қолданбалар

Бинарлы симметриялық арна жад сақтауға арналған диск жегішті модельдей алады: арнаның кірісі дискке жазылатын битті көрсетеді, ал шығысы кейін оқылатын битке сәйкес келеді. Қателіктер магниттелудің өзгеруінен, фондық шудан немесе жазу бас басының қателігінен туындауы мүмкін. Бинарлы симметриялық арна телефондық немесе радио байланыс желісін, сондай-ақ жасушаның бөлінуін де модельдей алады, онда туған жасушалар аналық жасушадан ДНК ақпаратын алады. Бұл арна теориялық зерттеушілер арасында жиі қолданылады, себебі ол талдауға ең оңай шулы арналардың бірі болып табылады. Коммуникация теориясының көптеген мәселелерін BSC арнасына келтіріп шешуге болады. Керісінше, BSC арнасы арқылы тиімді деректерді жіберу мүмкіндігі күрделі арналар үшін шешімдер табуға көмектеседі.