Тақырып 11. Нәтижелі кодтардың префиксттілікті талап етуі (Кедергіге тұрақты емес кодтар).

5. 5-кесте

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

Мысал 5. 7

Пайда болу ық тималдық тары р (z1) = 0, 9 жә не ρ (z2) = 0, 1 болатын ә ліпби кө мегімен қ ұ растырылғ ан z1 жә не z2 таң баларынан тұ ратын хабарламалардың тиімді кодтау процедурасын қ арастырамыз.

Ық тималдық тар тең емес болғ андық тан, осындай ә ріптер бойынша тізбектелу артық шылық қ а ие болады. Бірақ ә ріп бойынша кодтауда біз ешқ андай ә сер алмаймыз.

Шындығ ында, энтропия 0, 47-ге тең уақ ытта, ә рбір ә ріптің берілуі ү шін 1 немесе 0 символы керек.

Екі ә ріпі болатын блоктарды кодтауда, 5. 6. кестесінде кө рсетілген кодтарды аламыз.

5. 6-кесте

Таң балар статистикалық байланыссыз болғ андық тан, блоктардың ық тималдық тары, оны қ ұ райтын таң балардың ық тималдық тарының туындысымен анық талады.

Блок ү шін символдардың орташа саны 1, 29-ғ а, ал ә ріп ү шін — 0, 645-ке тең.

Ү ш таң бадан тұ ратын блокдарды кодтау ү лкен ә сер береді. Сә йкесінше ансамбль мен кодтар 5. 7. кестесінде берілген.

5. 7-кесте

Блок ү шін символдардың орташа саны 1, 59-ғ а тең, ал таң ба ү шін — 0, 53-ке, энтропиядан небә рі 12 % -ғ а артық . Теориялық минимум Η (Ζ ) = 0, 47 таң балардың шексіз санынан тұ ратын блоктарды кодтауда жетуі мү мкін:

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

Шеннон— Фаноның қ арастырылғ ан ә дістемесі кодты ә рдайым бірмә нді қ ұ растыруғ а алып келмейді. Анығ ында шағ ын топтарғ а ү лкен ық тималдық бойынша бө ліктеуде жоғ арғ ы сияқ ты тө менгі шағ ын топтарғ а да жасауғ а болады. Мысалы, ық тималдық тардың жиыны 5. 5 кестесінде келтірген, оны 5. 8 кетесінде кө рсетілгендей бө ліктеуге де болар еді.

5. 8-кесте

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

Екілік код ү шін ә дістеме келесідей болады. Хабарлама ә ліпбинің ә ріптері ық тималдық тардың кему ретімен негізгі бағ анағ а жазылады. Екі соң ғ ы ә ріп жиынтық ық тималдық жазатын бір қ осалқ ы ә ріпке біріктіреді. Біріктіруге қ атыспағ ан ә ріптердің ық тималдық тары мен алынғ ан жиынтық ық тималдық қ осымша бағ анада ық тималдық тардың кему ретімен қ айтадан орналасады, ал екі соң ғ ысы біріктіріледі. Процесс ық тималдығ ы бірлікке тең жалғ ыз қ осалқ ы ә ріпталғ анша созылады.

Мысал 5. 8

Хаффман ә дістемесін қ олдану арқ ылы 5. 5 кестесінде келтірген таң балар ансамблінің тиімді кодтауын іске асырамыз.

Кодтаулар процессі 5. 9 кестесінде тү сіндіріледі. Осы таң бағ а лайық ты кодтық комбинацияларды қ ұ растыруғ а таң баның кесте жолдары мен бағ андары бойынша ө тетін жолын бақ ылау қ ажет.

5. 9-кесте

Кө рнекілік ү шін кодтық ағ аш тұ рғ ызамыз. Ық тималдығ ы 1-ге тең нү ктеден, екі тармақ бағ ыттаймыз, ү лкен ық тималдық ты тармақ қ а 1 символын жазамыз, ал кішісіне 0. Осындай тізбектей тармақ талуды ә рбір ә ріптің ық тималдығ ына жеткенше дейін жалғ астырамыз. Ә ріптер ә ліпбиі ү шін кодтық ағ аш 5. 9 кестесінде, жә не 5. 16 суретінде берілген.

Енді, кодтық ағ аш бойынша жоғ арыдан тө мен қ озғ ала отырып, ә рбір ә ріп ү шін оғ ан лайық ты кодтық комбинацияны жазып алуғ а болады:

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

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

Код мысалы

Қ айта кодталады:

Префиксті 000101010101 код комбинацияларының тізбегі

Код мысалы

(01 комбинациясы 010 комбинацияның бастауы болып табылады) қ айта кодтау ә ртү рлі болуы мү мкін:

Немесе

Шеннона – Фано немесе Хаффмен методикаларын қ олдана отырып алғ ан кодымыз префиксті код екеніне кө зіміз жетті.

Белгілердің коррелироенген тізбегін тиімді ә діспен кодтау. Декорреляция шығ ыс тізбегінің алфавит таң баларымен ірілетуге болады. Бастауыш хабарлама беруші 2-3 немесе n знакты ү йлестіруші болады:

Ә р ү йлестіруші Шеннона — Фано немесе Хаффмен ә дістері бойынша қ ойылады.

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

Кө рсетілген жетіспеушілікті диаграмм, триграмм немесе l-грамм кодтау ә дісі бойынша шешуге болады. Шарт бойынша l-граммалы ү йлестіруші l шектес таң баны хабарлайды. Екі шектес таң балы ү йлестірушіні диаграмма, ү ш шектес таң баны триграмма т. с. с.

Енді кодалау ү рдісінде l-грамма хабарлама бойынша шексіз орналасып отырады

Ә рбір келесі таң баның кодтық мә ні l-1 алдындағ ы таң бағ а байланысты жә не Шеннона - Фано или Хаффмен ә дісінің ә р тү рлі l-граммдық мү мкіндіктері арқ ылы табылады.

l-дің нақ ты мә нін корреляция байланысының таң балар немесе техникалық реалиязияның кодтау жә не декодтау қ ұ рылғ ылары арқ ылы таң дайды.

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

Екінші жетіспеушідік ақ парат беру кідірісімен байланысты.

Ең ү лкен ә сер ұ зын блокты кодтағ анда пайда болады, бұ л таң баларды жинауғ а ә келеді, алдын ала сә йкес келетін тізбектілік символдар қ оярда. Декодтағ анда кідіріс қ айта пайда болады. Жалпы кідіріс уақ ыты ү лкен болуы мү мкін, ә детте блок пайда болғ ан кезде. Мұ ны кодтау блогының ұ зындығ ын таң дағ ан кезде ескерген жө н.

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

Арнайы тиімді кодтың қ ұ рылысының ә дістерімен қ ате тегі минимумғ а ә келуге тырысады.

Бақ ылау сұ рақ тары:

1. Тиімді кодалаудың ұ ғ ымы

2. Шеннон теоремасы

3. Белгінің корреляционды емес тізбектілігінің тиімді кодалауының ә дістері.

4. Хаффмен ә дісі

Тақ ырып 11. Нә тижелі кодтардың префиксттілікті талап етуі (Кедергіге тұ рақ ты емес кодтар).

Дә ріс мақ саты: Нә тижелі кодтар тү сінігін ү йрену. Кедергіге тұ рақ ты емес кодтар.

Сұ рақ тар:

1. Екілік кодты қ олдануда оны жіберуде, сақ тауғ а жә не ақ парат ө ң деуде қ андай артық шылығ ы бар?

2. Тиімді статикалық кодалаудың мә ні неде?

3. Салалы дә йекті белгінің кодалауының тиімділігінің себептері қ андай?

4. Ненің арқ асында тиімді кодалау кезінде кодалық комбинацияның орташа ұ зындығ ы кемиді.

5. Тиімді кодалау кезінде кодалық комбинацияның орташа ұ зындығ ы қ андай шекке дейін кемуі мү мкін?

6. Тиімді код қ андай басты шартты қ анағ аттандыруы керек?

7. Тиімді кодты қ олдану барысында пайда болатын қ иындық тарды атап ө тің із

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

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

Бірден кодсызданады:

Префикстік емес кодтың бірізділігі 000101010101 мысалы,

(01 амалы 010 амалының басы боолып табылады) кодсыздануы ә р тұ рлі болуы мү мкін:

немесе

Геннрн-Фано мен Хаффмен ә дістерін қ олданғ аннан кейінгі кодтар префикстік болатынына кө з жеткізу қ иын емес.

Таң балар бірізділігімен коррелиянғ ан нә тижелі кодтаудың ә дістері. Алғ ашқ ы бірізділік декорреляциясы таң балар алфавитін ү лкейту арқ ылы жү зеге асуы мү мкін. Жіберуге тиісті хабарлама бір, екі немесе n-тіркеске бө лінеді, ық тималдылығ ы мынадай болады:

Ә рбір тіркеске сә йкесінше Шеннон-Фано мен Хаффмен ә дістері бойынша кодтық амалдар қ ойылады.

Бұ л ә дістің тиімсіздігі мынада: таң балар арасындағ ы бірінен соң бірінгі тіркестерге кіретін корреляциялық байланыстар ескерілмейді. Ә рине, Естественно, ә рбір тіркеске кө п таң ба кірген сайын ол аз айқ ындалады.

Кө рсетілген кемшілік диаграмм немесе триграмм, l-грамм ә дісі қ олданылса жойылады. Хабарламаның l іргелес таң баларының тіркесуін l-грамм деп атайық. Екі іргелес таң баның байланысы диаграмма, ү шеуінікі — триграмма деп атайық жә не т. б

Енді l-грамма кодтау процесінде хабарламада текст тоқ таусыз қ озғ алады.

Ә рбір кезекті таң баның кодтық белгіленуі l-1 алдың ғ ы таң бағ а юайланысты жә не Шеннона - ФанонемесеХаффмен ә дістері негізінде ә р тү рлі l-грамм ық тмалдылығ ымен анық талады.

l нақ ты мә ні таң балар арасындағ ы корреляциялық байланыс дең гейіне байланысты немесе кодтайтын немесе кодсыздандыратын қ ұ рылғ ылардың техникалық орындау қ индығ ына байланысты таң далады.

Нә тижелі кодалау жү йесінің кемшіліктері. Кемшіліктердің бір себептерінің бірі ол кодалық қ иыстыру айырмашылығ ында. Егер ақ паратты ақ парат кө зінен алу басқ арылмайтын(мысалы, магнит лентада есте сақ тау қ ұ рылғ ысында ү здіксіз ақ парат алу) болса, кодаланатын қ ұ рылғ ы бірдей уақ ыт аралығ ында ә р тү рлі узындық тағ ы қ иыстыруды береді. Сонымен, байланыс сызық тары тек символдар тұ рақ ты жылдамдық пен берілгенде тиімді болады, шығ ысында кодаланғ ан қ ұ рылғ ы буферді қ ұ рылғ ы қ арастырылуы керек. ол символдарды тү су кө леміне байланысты қ орландырады жә не байланыс сызық тарына тұ рақ ты жылдамдық пен беріп отырады. Аналогты қ ұ рылғ ы қ абылдау бетінде де қ ажетті.

Екінші кемшілігі ақ парат жіберу барысында туындағ ан кідіріс.

Ең ү лкен ә серге ұ зын блоктарды кодалағ анда жетеді, ал ол символдарды белгілі бір ретпен қ оймай жатып таң баны жинау қ ажеттілігін туындатады. Қ айта кодалау барысында кідіріс қ айта пайда болады. Бұ ны кодаланатын блоктын ұ зындығ ын таң дағ анда қ арастыру керек.

Тағ ы бір кемшілігі кедергілердің қ абылдау дұ рыстығ ына айрық ша ә сері. Дара қ ателік жіберіліп отырғ ан кодалық қ иыстыруды ұ зындығ ы сай келмейтін басқ а кодалық қ иыстыруғ а айналдыруы мү мкін. Артынан «қ ателік трегі» (трек ошибки) деп аталатын келесі тізбек қ иыстыруының дұ рыс емес қ айта кодалауын ілестіреді.

Қ ателік трегінің нә тижелі кодасын қ ұ рдың арнайы ә дісі ол минимумғ а ұ мтылдыру [18].

Нә тижелі кодалауды орындаудың техникалық салыстырмалы қ иындығ ын айта кету керек.

Ақ парат кө зінің кодері суретте кө рсетілген сур. 5. 17. Онда негізгі матрицалық 1 щифраторды 3 регистрімен жә не 2 матрицалық шифраторды 4 жылжу регистрімен ақ парат оқ уды басқ аратын кө мекші сұ лбаны ерекшелеуге болады. Кө лденең шифратор шиналарының саны кодаланатын таң балар санына тең, ал тік шифратор шиналарының саны ә рқ айсысынның нә тижелі кодалаудағ ы ең ұ зын қ иыстыруындағ ы символдар санына тең.

ί -тү йініндегі кө лденең шинаның 1 негізгі шифраторына диодты қ осу 3 жылжу регистріне z_i таң басына сай келетін кодалық қ иыстыруды жазуды қ амтамасыз етеді.

2 кө мекші шифраторына ә р i –ші кө лденең шинағ а бір 4 регистрғ а нө мірі кодаланғ ан қ иыстыруда таң ба санына сә йкес келетін бірлік жазбаны қ амтамасыз ететін диод жалғ анғ ан.

7 ақ парат кө зі берген кезекті z_iтаң басын кодалау 6 импульсті қ ор кө зінен ί –ші кө лденең шифратор шинасындағ ы И импульсі элементтері жіберу арқ ылы жү зеге асады. Сонымен қ атар, z_i таң басына сай келетін 3 жылжу регистріне кодаланғ ан қ иыстыру жазылады, ал 4 регистрі-кодаланғ ан қ иыстырудың соң ы жайлы ақ парат беретін бірлік. 3 регистрінде жазылғ ан 5 жылжымалы импульсті генератор таң балары байланыс арналарына шығ ады. Сол генератор арқ ылы 4 регистріндегі бірлікте жылжиды. 3 регистрдан кодаланғ ан қ иыстырудағ ы соң ғ ы таң ба шық қ ан кезде ғ ана шығ ыста сә йкес импульс пайда болады. Бұ л импульс кодаланғ ан келесі таң бағ а ө туді басқ ару ү шін қ олданылады.

5. 18 суретте Гильбертпен Мурдың ә зірлеген декодтаушы қ ұ рылымның жобасы келтірілген.

2 кіріске тасымалданатын декодтаушы кодты комбинация символы, оның бойымен 5 ші тактілі генератор импульсымен жылжиды. Келіп тү суші кодалық комбинциялардың кейбіреулері бір немесе бірнеше 0 ден басталатын болғ андық тан, регистірдің қ ұ рылымы бойынша бұ л комбинацияларың басын анық тау мү мкін емес, сондық танда оны дұ рыс декодтау мү мкін емес. Жә шік регистірінің кодты комбинациясының санының басын анық тау ү шін ең ұ зақ анағ ұ рлым пайдалы кодалық комбинацияны алады жә не бірлікке анағ ұ рлым кө бірек сандар мен символ дарды алады. Бірінші қ осымша жә шік регистіріне тү сетін келесі декодталғ ан комбинация тү серден алдын ә рдайым бірді жазады. Регистір бойынша жылжып, ол кодалық комбинацияның басталуы жө нінде сигнал береді жә не оның ұ зындығ ы бойынша.

Ә р тактылы импульсте соң 6 шы импульті бастаудан жү реді, ол 1 ші матрицалы дешифратордан қ орек алады. Соң ғ ысы қ олданылғ ан комбинацилық кодқ а сә йкес жасалынғ ан, оғ ан ү лкен разряд жақ тан артық бірлік жазылғ ан. _.Схемасы арқ ылы бұ л импульс 4 ші аралық жә шіктің жадына жазылады жә не келесі импультің оқ ылуымен 3 тастау генераторы барша жә шіктің бастапқ ы қ алыпқ а орнатылуында қ олданылады. ( бірінші жә шікте 1, ал қ алғ андарында 0). Одан кейін келесі кодтық комбинация басталады жә не декодтық процесс қ айталанады.

Бақ ылау сұ рақ тары

8. Екілік кодты қ олдануда оны жіберуде, сақ тауғ а жә не ақ парат ө ң деуде қ андай артық шылығ ы бар?

9. Тиімді статикалық кодалаудың мә ні неде?

10. Салалы дә йекті белгінің кодалауының тиімділігінің себептері қ андай?

11. Ненің арқ асында тиімді кодалау кезінде кодалық комбинацияның орташа ұ зындығ ы кемиді.

12. Тиімді кодалау кезінде кодалық комбинацияның орташа ұ зындығ ы қ андай шекке дейін кемуі мү мкін?

13. Тиімді код қ андай басты шартты қ анағ аттандыруы керек?

14. Тиімді кодты қ олдану барысында пайда болатын қ иындық тарды атап ө тің із

⇐ Предыдущая 24 25 26 27 282930 31 32 33 Следующая ⇒