Хабарламаны кодтау көздері

Жоспар

• Кіріспе
• Кодтау
• Хабарламаны кодтау көздері
• Ақпарат көздерінің сандық стационарлық кодтаушылары
• Хаффмен алгоритмінің кодтаушысы
• Қорытынды
• Қолданылған әдебиеттер тізімі

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Кіріспе

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

ECC жаңа кодтардың бірі  ретінде LDPC (Low-Density Parity-check Code) кодын айтуымызға болады. Негізінде олар отыз жыл бұрын танымал блған, бірақта қазіргі уақытта оларға ерекше көңіл бөлінуде. LDPC коды 100-пайыздық анықтылығы бомағанмен, ол қатенің мүмкіндігін керекті нәтижеге дейін жеткізуімізге мүмкіндік береді және сонымен қатар каналдың жіберу мүмкіндігі максимальді толық түрде қолданылады. Оларға  «турбокодтар» (Turbo Code) өте жақын келеді, олар алыс космостағы объектілермен жұмыс жасағанда өте қолайлы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Кодтау

Кодтау (кодирование; coding; кодировать; encode) — мәліметтерді олардың алдын ала тағайындаған кодтық комбинацияларымен бейнелеу немесе мәліметтер элементін (символдар жиынын) олардың кодтық комбинацияларымен сәйкес келтіру; программалау процесі; 2) ақпараттың 8 биттік (байттық) кодтауын 7 биттік кодтауға түрлендіру. Мұндай түрлендірудің қажеттілігі кейбір желілік программалардың мәліметтерді тек 7 биттік кодтауда жеткізе алатындығынан туындайды. Байттық мәліметтерді осындай арналармен тікелей жеткізу ақпараттың бұрмалануына жол береді; 3) белгілі бір ереже бойынша дискреттік хабарды дискреттік сигнал түріне түрлендіру (аудармалау), яғни шарт таңбаларды қолдану.

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

Мәліметтерді кодтаудың  қажеттілігімен алғашқы рет жүз  елу жыл бұрын тап болды. Каналдар өте қымбат және сенімсіз болғандықтан телеграммаларды жіберудің өте  тиімді жолдары қарастырылды.1845 жылы пайдалануға арнайы кодтау кітаптары  шықты; олардың көмегімен телеграфистер қолмен мәліметтердегі ұзақ сөйлемдерді қысқа кодтармен алмастырды. Сол кездері мәліметтердің жіберілуінің дұрыстығын тексеру үшін жұптық бақылау әдісі қолданылды, бұл әдісті перфокарталардың дұрыстығын тексеру үшін компьютердің бірінші және екінші буындарында да қолданылды. Ол үшін ең соңғы мәліметтер колодасына арнайы дайындалған бақылау сомасы бар картаны салған. Егер енгізу құрылғысы сенімсіз болса (немесе колода тым ұзын болған жағдайда), онда қате тууы мүмкін. Оны жөндеу үшін картадағы сомамен сәйкес келмегенше процедураны қайталай беретін. Бұл сұлбаның ыңғайсыз болғанымен қатар, ол екі есе қателер жіберетін. Байланыс каналдарының дамуымен қатар бақылаудың өте тиімді механизмі керек болды.

Бұл мәселенің теориялық  шешімін алғашқы болып ақпараттың статистикалық теориясынының негізін қалаушы Клод Шеннон ұсынды. Шеннон өз заманының жұлдызы болды,ол АҚШ-тың академиялық элитасынынң мүшесі болған. Ванневар Буштың аспиранты болып, ол 1940 жылы жасы 30 жетпеген оқымыстыларға берілетін Нобель атындағы сыйлыққа ие болды (Нобель премиясымен шатастырмаңыздар). Bell Labs жұмыс істеп жүріп Шеннон «Мәліметтерді жіберудің математикалық теориясы» (1948) атты жұмыс жазды, ол жұмыста Шеннон  каналдың жіберу мүмкіндігі мәліметтердің энтропия бастауынан жоғары болса, онда мәліметтерді ешқандай ақаусыз жіберілетіндей етіп кодтап қоюға болатынын дәлелдеді.Бұл түйіндеме Шеннонның көптеген дәлелдеген теоремалардың біреуінде бар. Сонымен қатар, ол каналда шудың бар болуына қарамастан мәліметтің жіберілу мүмкіндігінің теориялы түрде дәлелдеп берді.Шеннонның Мичиган штатында өзінің туып өскен қаласында орнатылған ескерткішінде ойып жазылған формуланы C = W log ((P+N)/N) Альберт Эйнштейннің E = mc2 формуласының мәнімен салыстырады.

Шеннонның еңбектері ақпараттар теория облысындағы ары қарай  зерттеулерінде өз ықпалын тигізді, бірақта оларда инженерлік практикалық  қосымшасы бар болмады. Теориядан  практикаға алмасу Ричарда Хэммингтің жұмысынан байланысты болды. Ол Шеннонның Bell Labs бойынша әріптесі болды және кодтар класын ашқандығы үшін әйгілі болды, оларды «Хэмминг коды» деп атады. Өзінің жаңалығын Хемминг 40 жылдардың ортасында Bell Model V есептеуіш машинасының перфокарталармен жұмыс жасау қолайсыздығынан ашты деген аңыз бар. Оған операторлар жоқ болғанда, яғни демалыс күндерде машинамен жұмыс жасауға мүмкіндік берді және ол өзі енгізулермен жұмыс жасады. Хемминг байланыс каналдарындағы, сонымен қатар компьютерлердегі ақпараттарды беру магистральдарында, ең бастысы жад пен процессор арасындағы қателерді түзете алатын кодты ұсынды. Хемминг коды Шеннон теоремасында көрсетілген мүмкіндіктерді практикалық түрде қалай іске асыруға болатындығын көрсетеді.

Хемминг өзінің мақаласын 1950 жылы жарыққа шығарды, бірақта ішкі жазбаларда кодтау теориясы 1947 жылмен белгіленген. Сондықтанда кейбіреулер  кодтау теориясының атасы ретінде  Шеннонды емес, Хеммингті атау керек деп ойлайды. Бірақта, техника тарихында алғашқыны іздеу пайдасыз нәрсе.

Хемминг бірінші болып  «қателерді түзейтін кодтарды» (Error-Correcting Code, ECC) ұсынғандығы анық екенін білеміз. Бұл кодтардың қазіргі заманғы модификациялары барлық ақпараттарды сақтау жүйелерінде және жад пен процессор арасындағы алмасулар үшін қолданатыны белгілі. Олардың бір нұсқасы Рид-Соломонның коды компакт-дискілерде қолданылады.  Хэмминг тәсілі бойынша жасалынған көптеген кодтар нұсқалары бар, олар кодтау алгоритмдері бойынша және тексеретін биттер саны бойынша айырмашылықтары бар. Мұндай кодтарға планетааралық станциялармен космостық байланыс жасау үшін ерекше көңіл беріле бастады, мысалы, Рид-Мюллердің кодтарын 7 ақпараттық битке 32 тексеруші бит немесе 6 ақпараттық битқа – 26 тексеруші биттар келетін болды.

ECC жаңа кодтардың бірі  ретінде LDPC (Low-Density Parity-check Code) кодын айтуымызға болады. Негізінде олар отыз жыл бұрын танымал блған, бірақта қазіргі уақытта оларға ерекше көңіл бөлінуде. LDPC коды 100-пайыздық анықтылығы бомағанмен, ол қатенің мүмкіндігін керекті нәтижеге дейін жеткізуімізге мүмкіндік береді және сонымен қатар каналдың жіберу мүмкіндігі максимальді толық түрде қолданылады. Оларға  «турбокодтар» (Turbo Code) өте жақын келеді, олар алыс космостағы объектілермен жұмыс жасағанда өте қолайлы.

 

Хабарламаны кодтау көздері

Кодтау теориясының тарихына Владимир Александрович Котельниковтың аты нық жазылған. 1933 году  «Материалах по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи»-да ол өзінің «О пропускной способности ‘эфира’ и ‘проволоки’» атты жұмысын жариялады. Бұл теоремада жіберілген сигнал ақпараттың жоғалтуынсыз қайтадан қалпына келетін шарттарды анықтайды.

Сандық байланыс каналы кодтаушысы мен хабарлама көзі арасында хабарламаны кодтаушы көздері қосылған. Хабарлама көздері сандық (компьютер, магнитті немесе оптикалық диск) немесе аналогты (телефонды, телевизиялық, телеметрикалық) сигналдар болып бөлінеді.  Хабарламаны кодтау көздерінің міндеті болып, экономды түрде байланыс каналына хабарламаны сандық түрде көрсетуді жеткізу болып табылады. Хабарламаны кодтау көздерін тағы да хабарламаларды сығу құрылғысы деп те атайды. Егер сандық хабарлама көзі R_и жылдамдықпен екілік символдардың ағынын құрса, онда хабарлама кодтаушысының шығысында R<R_и жылдамдықты ақпараттық бит ағыны пайда болады. Бұл жылдамдықтардың қатынасы сығу коэффициенті болып табылады:

К_сғ= R_и / R,

мысалы,  V.34 модемі үшін мәтіндік ақпараты бар сығу құрылғысы К_сғ=4 сығу коэффициентімен жасалған. Өйткені V.34 модемінің шығысында R_и=128кбит/с болған кезде R = 32 кбит/с мәніне ие.

Телефондық  сигналдарды  берген кезде R_и=64кбит/с жылдамдықты да қоюға болады. Бұл беру жылдамдығы кезінде аналогты телефонды сигналдың телефон сигналының сапасын жоғалтпай сандық түрге айналуы жүреді. Бригадалық эксперттің тыңдауы көрсеткендей, жеткен сигналдың қайтадан аналогтыға ауысуы, яғни оны қайтадан кері аударып тыңдау  кезінде ол сигналдың бастапқы кезінде шыққан сигналдан еш айырмасы жоқ екендігі анықталған.

Қазіргі кездегі түрлі-түсті  телевизиялық сигналдар үшін оның сапасы жоғалмастан R_и= 256кбит/с жылдамдыққа дейін жетеді. Бұл кезде телевизиялық сигналдың коммерциялық сапасында сығу коэффициенті К_сғ=50-100 мәніне жетеді.

 

Ақпарат көздерінің сандық стационарлық кодтаушылары

 

Ақпарат көздерін х₁, х₂, х₃ болсын, априорлық ықтималдық бойынша Р (х_і)-тең болатын х_і әріпін алайық. Сондағы Р (х_і) априорлық ықтималдықта   ақпараттар саны:

Сандық хабарламалардың  орта ақпарат көздері энтропия көзі деп аталады:

Егер екілік ақпарат көзі ықтималдығы q «0» тәуелсіз символын және ықтималдығы 1-q «1» тәуелсіз символын кезектесіп береді.

Бол көздің энтропиясы былай  болады:

 

Хаффмен алгоритмінің кодтаушысы

 

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

Хаффмен әдісі бойынша әріптер баған бойына жоғарыдан төмен қарай жазылады. Ол Р (х_і) ықтималдығы бойынша кему ретімен орналасып, кодтық ағаш сұлбасын түзеді (1-сурет).

Кодтық ағаш құруды ықтималдырақ х₈  және х₇ символдарынан бастаймыз. Бұл екеуін жоғарғы бұтаққа біріктіріп, жоғарғысына «0», ал төменгісіне «1» саламыз. Бұл екі бұтақтың ықтималдығы бірігіп ортақ суммалық ықтималдық құрайды. Ары қарай келесі ықтималдықты бұтақтарды біріктіреміз және солай жалғаса береді. Кодтық сөздер қозғалыс кезінде оң жақ шетінен бастап шеткі сол жаққа дейінге жерден алынады. Ағаш бойымен жоғары қозғалғанда «0» символы, төмен қозғалғанда «1» сиволы 1-суретте көрсетілгендей алынады.

1-сурет. Айнымалы ұзындықтағы  сөздерді кодтау

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Қорытынды

Мәліметтерді кодтаудың  қажеттілігімен алғашқы рет жүз  елу жыл бұрын тап болды. Каналдар өте қымбат және сенімсіз болғандықтан телеграммаларды жіберудің өте  тиімді жолдары қарастырылды.1845 жылы пайдалануға арнайы кодтау кітаптары  шықты; олардың көмегімен телеграфистер қолмен мәліметтердегі ұзақ сөйлемдерді қысқа кодтармен алмастырды. Сол кездері мәліметтердің жіберілуінің дұрыстығын тексеру үшін жұптық бақылау әдісі қолданылды, бұл әдісті перфокарталардың дұрыстығын тексеру үшін компьютердің бірінші және екінші буындарында да қолданылды. Ол үшін ең соңғы мәліметтер колодасына арнайы дайындалған бақылау сомасы бар картаны салған. Егер енгізу құрылғысы сенімсіз болса (немесе колода тым ұзын болған жағдайда), онда қате тууы мүмкін. Оны жөндеу үшін картадағы сомамен сәйкес келмегенше процедураны қайталай беретін. Бұл сұлбаның ыңғайсыз болғанымен қатар, ол екі есе қателер жіберетін. Байланыс каналдарының дамуымен қатар бақылаудың өте тиімді механизмі керек болды.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Қолданылған әдебиеттер тізімі

1. И.М. Тепляков «Tелекоммуникационные системы», Mосква «РадиоСофт» 2008
2. www.google.kz