Жадсыз дискретті каналдар үшін кодтау

Теоремасы

Әр символ Т_S секунд ішінде берілетін С [бит/символ] өткізгіштік қабілетті жадсыз дискретті каналды қарастырайық. Мұнда С[бит/сек] = С[бит/сек]/Т_S.

Қандай-да бір Х дереккөзінің Т_S уақыт ішінде өлшенге энтропиясы Н(Х)-ке тең болсын. Бұл жағдайда келесі теорема орынды

7.6.1 Теоремасы.Канал үшін кодтау теоремасы (Шеннон теоремасы).

Х дереккөзі үшін R — H(X)/T_S [бит/сек] және R < С жылдамдықты бір код бар, және оның жәдемімен Х дереккөзінің мағлұматы байланыс каналы арқылы С[бит/сек] жылдамдықпен төмен қате ықтималдығымен тасымалдана алады. ¹

Канал үшін кодтау теоремасының дәлелі (мысал ретінде [10] көріңіз) дерліктей күрделі және бұл кітаптың қамтыған аумағынан шығып кетеді, сондықтан бұл жерде келесі ескерулермен шектелгеніміз жөн.

● Кодтау теоремасының дәлелі кездейсоқ шексіз өлшемді кодтарды және максималды хақиқатқа жақын, төмен қате ықтималдығын қамтамасыз ететін декодерді қолдануды қажет етеді. Дәлел ешқандай конструктивті шешімдерді қажет етпейді. Онда тек қана статистикалық қасиеттер мен шексіздікке ұмтылатын блок ұзындықты блок кодтары үшін ақтық өткелдер қолданылады. Дәлелде оптималды кодтардың конструкциясына ешқандай нұсқау берілмейді.

● Сонымен қатар кодтау теоремасы R тасымалдау жылдамдығы үшін жоғарғы шекті анықтайды. ²

● Теореманы дәлелдеу уақтысында техникалық қол жетімді ақпарат тасымалдау жылдамдығын бағалауда қолданылатын R₀ экспоненциалды бағалау көрсеткіші енгізіледі [4].

¹Кодтау теоремасы тек дискретті каналдар үшін ғана емес, одан бөлек ол үздіксіз каналдар арқылы дискретті хабарламалар тасымалдауға да дұрыс.

²Бұл жерде анықтап өткен жөн. R > С болғанда ақпаратты төмен қате ықтималдығымен тасымалдай алатын ешқандай кодтау тәсілі жоқ екенін айтатын кері кодтау теоремасы бар

БӨЛІМ

ЗДІКСІЗ

ДЕРЕККӨЗДЕР

ЖӘНЕ КАНАЛДАР

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

8.1 Сурет. Үздіксіз дереккөздің сигналы.

Нақты алфавитті дереккөздердің орнына шығысы үздіксіз сигналдар болып табылатын дереккөздерді қарап шығамыз. Мұндай сигналдардың мысалы ретінде біз телефон каналдарындағы уақытта өзгеретін кернеуді келтіре аламыз. 8.1 суретте шығысы t уақыттың кездейсоқ функциясы болып табылатын ұқсас сигналды X үздіксіз дереккөзі көрсетілген. -ның мәндерін X дереккөзі жайлы мағлұмат бар уақыттың кейбір назар салынған сәтіндегі кездейсоқ тәжірибе ретінде қарап шығамыз.

Дифференциалды энтропия

8.2 суретте канал арқылы байланысқан екі үздіксіз X және Y дереккөздері көрсетілген (7.4 суретке ұқсас). Мұнда, ықтималдықтардың орнына, стохастикалық айнымалылардың ықтималдықтарының бөліп тарату тығыздықтарының функциясы тұрады.

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

8.2 Сурет. Канал арқылы байланысқан екі жадсыз

үздіксіз дереккөздер.

Үздіксіз X дереккөзін дискреттіге түрлендіреміз. Бұл үшін Δ қадамды дереккөздің ұқсас шығысның мәнін кванттаймыз (8.3 сурет).

8.3 Сурет. Δ кванттау интервалды үздіксіз дереккөзді бақылау сәтінде цифрлеу

Мұнан басқа, ақпараттар теориясында әдеттегідей дереккөзді уақытта дискретизациялаймыз. Нәтижесінде, стохастикалық айнымалы-ларының реттілігін аламыз. 7.2 кесте бойынша, уақыт сәтіндегі, ал уақыт сәтіндегі шығыс символының мәні болатын символдарының өзара ақпаратын анықтаймыз.

Өзара ақпаратты айнымалысы интервалына меншіктілігі мағлұм болғандағы және керісініше интервалындағы айнымалысының «шешілген» (жоғалтылған) анықталмағандығы деп сипаттауға болады. Ықтималдықты бөліп тарату тығыздығының функциясын үздіксіз функция деп есептейік. Сонда, кванттау интервалының енін нөлге ұмтылдырып, алатынымыз

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

Ескерту.Мұнда, бұл бөлімнің белгілеуін 7.2 кестеге сәйкес келтіру үшін орнына , ал орына қолданылады.

Дереккөз ақпараты ұқсас тұжырымдар арқылы анықталады

Өзара ақпарат үшін (8.3) өрнекке қарағанда (8.4)-те Δ кванттау интервалына тәуелді қосынды пайда болады.

Δ→∞ тұсында шамасы шексіздікке ұмтылады. Нәтижесінде, үшін өрнек сондай-ақ ∞–ке ұмтылады. Бұл ғажаптанатын нәрсе емес, кванттау қадамының төмендеуіне байланысты бөлек оқиғалар (дереккөз алфавитінің символдары) саны жоғарылайды және сонымен қатар дереккөз анықталмағандығы да өседі.

шамасы дереккөзге тәуелді емес және оны суреттеу үшін мүлдем тура келмейді, сол себепті, үздіксіз дереккөз ықтималдығының бөліп тарату тығыздығының функциясын қолданған дұрыс. Осылайша, біз келесі анықтамаға өтеміз.

Үздіксіз дереккөздің орташа ақпараты, яғни дифференциалды энтропия, келесі түрде анықталады

Ең әуелі, дифференциалды энтропияның мұндай ерікті анықтамасы өзінің қажеттілігін дискретті дереккөздер үшін энтропиялы қатынастар каналдар және үздіксіз дереккөздер жағдайы үшін әділ екендігімен дәлелдейтінін айта кетейік. Атап айтқанда, үздіксіз дереккөздер үшін (7.39) – (7.42) қатынастары орынды.

Осылайша, үздіксіз дереккөздің дифференциалды энтропиясы жалпы жағдайда шексіз шама болып табылатын ықтималдықты бөліп тарату тығыздығының функциясына ғана тәуелді, сол себепті дифференциалды энтропияның мәні қаншалықты жоғары болуы мүмкін деген сұрақ қояйық. Ең әуелі, айтып кететін жайт, стохастикалық процесстің негізгі сипаттамасы болып табылатын екі шамасы бар: стохастикалық айнымалы (сызықтық қабілетке ие) қабылдайтын орташа μ мән және стохастикалық айнымалының стандартты σ ауытқуы.

Орташа мән я болмаса μ математикалық күтімі дифференциалды энтропияға ешқандай ықпал етпейді. σ өсуімен дереккөз анықталмағандығы жоғарылайды, ол оз кезегінде дифференциалды энтропияның өсуіне себепші болады. Осыған байланысты, түрлі ықтималдықты бөліп тарату тығыздығының функциясын оларға сәйкес энтропияларға қатысты салыстыру біркелкі σ тұсында өндіруге мәжбүрлейді.

Ескерту.Ақпараттық техникада бастапқы параметр ретінде - стохастикалық процесстің орташа қуаттылығын [10] қабылдайды. Тасымалдағыштың қуаттылығының жоғарылауымен тасымалданатын ақпараттың көлемі өседі, және, керісінше, шулардың қуаттылығының жоғарылауымен анықталмағандық жоғарылайды, яғни уақыт бірлігінде азырақ ақпарат тасымалданады.

Ақпараттар теориясы бойынша дифференциалдық энтропия өзінің максимумына ықтималдықтың гаусстық бөліп таралуы уақтысында жетеді.

Теорема 8.1.1.Берілген дисперсиясындаықтималдықты гаусстық бөліп тарататын дереккөз максималды дифференциалды энтропияға ие болады, сонымен қатар

Мысал: гаусстық дереккөздің дифференциалды энтропиясы.

(8.5) бойынша, гаусстық дереккөздің дифференциалды энтропиясы тең болады

Квадратты жақшалардағы өрнек екі интегралға бөлінуі мүмкін. Осылайша, соңғы форма

Көбірек қолданысқа ие бөлінулер үшін сандық мысалдар 8.1 кестеде келтірілген.

Мысал: Телефония.

Жоғарыда келтірілген нәтижелердің практикалық пайдасы цифрлы телефондық желілерде ақпарат тасымалдау (биттерде) жылдамдығының жетістіктерін бағалау арқылы көрсетілуі мүмкін. Заманауи цифрлы сөйлем (логарифмдық РСМ) тасымалдаудың стандартты тәсілдері санақтардың 8кГц жиілігінде бір санақты кодтау үшін 8 бит шығындауды қажет етеді. Осылайша, сөйлем тасымалдау жылдамдығы 64 кбит/сек құрайды.

8.1 Кесте.Дифференциалды энтропияның мысалы.

[-1, 1] интервалындағы ықтималдықтарды бірқалыпты бөліп таратудан бастасақ, тәжірибелі жолмен аламыз. Осылайша, бір санақ үшін дифференциалды энтропия құрайды

Есептеулер 8 кГц жиілікпен жүзеге асып жатқандықтан, қажетті сөйлем тасымалдау жиілігі 8кбит/сек құрайтынын білеміз. Энтропияны бағалау кезінде біз көрші есептеулер (дереккөз жадысы) арасындағы байланыстарға назар салмаппыз, және, сондықтан, сөйлем дереккөзінің шынайы дифференциалды энтропиясы одан да азырақ болады. Ақиқатында, заманауи сөйлем кодтау алгоритмдері сөйлемдік сигналды РСМ стандартымен теңесетін сапада 8 кбит/сек маңайындағы жылдамдықпен тасымалдауға мүмкіндік береді.