Кіріспе

Деректер беру жылдамдығының шегі

Ақпарат теориясында, шулы арна кодтау теоремасы (кейде Шеннон теоремасы немесе Шеннон шегі деп аталады), байланыс арнасының шумен ластануының кез келген деңгейі үшін, дискретті деректерді (цифрлық ақпаратты) арна арқылы есептеліп шығарылатын максималды жылдамдыққа дейін, дерлік қатесіз жеткізуге болатынын анықтайды. Бұл нәтижені 1948 жылы Клод Шеннон ұсынды, және ол Гарри Найквист пен Ральф Хартлидің бұрынғы жұмыстары мен идеяларына негізделген. Шеннон шегі немесе Шеннон сыйымдылығы – байланыс арнасы арқылы теориялық түрде қатесіз берілуі мүмкін деректердің ең жоғары жылдамдығын көрсетеді, егер байланыс белгілі бір шу деңгейінде кездейсоқ деректер беру қателеріне ұшыраса. Оны алғаш рет Шеннон (1948 ж.) сипаттады, ал көп ұзамай Шеннон мен Уоррен Уивердің «Математикалық коммуникация теориясы» атты кітабында жарияланды (1949 ж.). Осылайша, ақпарат теориясының қазіргі заманғы ғылымы құрылды.

Шолу

1948 жылы Клод Шеннон айтқан теорема, шулы кедергілер мен деректердің бұзылуына қарсы қателерді түзету әдістерінің ең жоғары тиімділігін сипаттайды. Шеннон теоремасы байланыс және деректерді сақтау салаларында кеңінен қолданылады. Бұл теорема қазіргі заманғы ақпарат теориясының негізгі қағидасы болып табылады. Шеннон дәлелдің тек қана жоспарын келтірді. Дискретті жағдай бойынша алғашқы қатаң дәлел келтірілген. Шеннон теоремасы былай тұжырымдайды: егер каналдың сыйымдылығы C және ақпаратты беру жылдамдығы R болса, онда қабылдаушыдағы қателік ықтималдығын кез келген қалағанша кіші мәнге дейін төмендетуге мүмкіндік беретін кодтар бар. Бұл теориялық тұрғыдан алғанда, ақпаратты шектеу жылдамдығы C-ден төмен кез келген жылдамдықпен дерлік қатесіз беруге болады.

Кері тұжырым да маңызды. Егер , онда қателік ықтималдығын кездейсоқ кіші мәнге дейін төмендету мүмкін емес. Барлық кодтардың қателік ықтималдығы белгілі бір оң минималды деңгейден жоғары болады, және бұл деңгей жылдамдық артуымен бірге өседі. Сондықтан, ақпаратты канал арқылы каналдың сыйымдылығынан асып түсетін жылдамдықпен сенімді түрде беруге кепілдік беруге болмайды. Теорема жылдамдық пен сыйымдылықтың тең болатын сирек жағдайды қарастырмайды. Каналдың сыйымдылығы каналдың физикалық қасиеттерінен есептелуі мүмкін; Гаусс шуы бар жолақты шектелген канал үшін Шеннон-Хартли теоремасын пайдалану арқылы. "Хабарды 3 рет жіберіп, көшірмелер өзгеше болған жағдайда, 3 дауыс беру схемасының ең жақсы 2-сін пайдалану" сияқты қарапайым схемалар тиімсіз қателерді түзету әдістері болып табылады, олар деректер блогының қатесіз берілуіне кепілдік бере алмайды. Рид-Соломон кодтары және соңғы кезде төмен тығыздықты тепе-теңдік тексеру (LDPC) кодтары мен турбо кодтары сияқты жетілдірілген техникалар теориялық Шеннон шегіне жақындауға мүмкіндік береді, бірақ бұл жоғары есептеу күрделілігімен байланысты. Осы өте тиімді кодтарды пайдалану және қазіргі заманғы цифрлық сигнал процессорларының есептеу қуатының арқасында Шеннон шегіне өте жақын қол жеткізуге болады. Шындығында, LDPC кодтары Шеннон шегінен 0,0045 дБ-ға дейін жете алатыны көрсетілді (бинарлық аддитивті ақ Гаусс шуы (AWGN) каналдары үшін, өте ұзын блоктармен).

Дәлелдің тұжырымдамасы

Ақпарат теориясындағы басқа да маңызды нәтижелер сияқты, шулы каналды кодтау теоремасының дәлелі де қол жетімділік туралы нәтиже мен оған сәйкес келетін кері нәтижеден тұрады. Бұл екі компонент, осы жағдайда, шулы канал арқылы хабар алмасуға болатын мүмкін жылдамдықтар жиынын шектеуге және осы шектердің нақты екенін көрсетуге мүмкіндік береді. Төмендегі сипаттамалар – ақпарат теориясы бойынша оқулықтарда қарастырылатын көптеген әртүрлі стильдердің тек бір мысалы ғана.

Дәлелдің мазмұны

Дәлелдің өзі каналдық кодтау теоремасының дәлеліне ұқсас. Жетілуі кездейсоқ кодтау арқылы қамтамасыз етіледі, мұнда әрбір символ сол арна үшін сыйымдылыққа жететін таралымнан кездейсоқ таңдалады. Типикалық аргументтер асимптотикалық тепе-теңдік қасиеттері мақаласында анықталған, стационарлық емес көздер үшін типтік жиынтардың анықтамасын пайдаланады. lim inf-тің техникалық жағы, егер ол жиналмаса, қолданылады.