ДРІС №9. Апаратты жйелерде процесіні моделі деректер. 4 страница

S=K1+1+, n=n1 (149)

деп йарамыз, мндаы, - K1 + 1-ді mn1-ге дейін толытыратын санды былайша жазуа болады:

ni = = + = +

 

 

мндаы, = К санын лайта отырып, ол осындыланатын (КР жне К 1Р кезінде) санмен салыстыру бойынша санын азайтуа болады. Осылай ойлай отырып, блетін комбинацияларды ескеріп, n2 шін рнек аламыз:

L=Nuk ( жне жайлы да, жне жайлы сияты айтуа болады).

йткені бл ретте кодты комбинацияларды орташа зындыы n= (1-d)*n1 +d*n2-гe те, сондытан хабарды бip элементіне келетін кодты символдарды орташа саны = мндаы =

мндаы, лкен К кезінде андай болмасын кіші болады. Бл тура теореманы длелдейді.

 

ДРІС №14. Араласуынсыз санды арнаны беру кодтау апарат. Цифрлы нысанда процесі рнек апаратты кодтау. Цифрлы нысанда апарат техникалы ралдары. Криптографиялы апаратты жабу ралы ретінде Coding тиімді кодтау. Тиімді кодтау жне декодтау кодтары техникалы ралдары

 

Дрісті мтіні

Масаты: Апаратты ысу дістеріні жалпы баыттарын білу

Дріс жоспары

1.Трлендірулерді кодтау. JPEG ысу стандарты

2. Фракталды діс

3. Рекурсивті (толкынды) алгоритм

 

Негізгі тсініктер: абсолютті дл, деректерді жуытап алпына келтіру, кванттау. пиксель, квадратты блоктар, дабыл спектрі, арифметикалы кодтау, Хаффмен алгоритмі, спектрлік компоненттер, фракталды кодтау, wavelet

Таырыпты мазмны: Алашы деректерді ттынушыа беруді абсолютті длдігіне деген ажеттілікті, кбінесе керегі жо болады. Біріншіден, деректер кздеріні зі шектеулі динамикалы диапозона ие жне брмалаулар мен ателерді белгілі бір дегейімен алашы хабарды шыарады. Екіншіден байланыс арналары бойынша деректерді беру мен оларды сатау ркашанда ртрлі кедергілерді болуы кезінде жргізіледі. Сондытан (жаыртылан) хабар рашанда белгілі бір дрежеде берілген хабардан згешеленеді. Е соында апараттарды алушылар - адамны сезетін органдары, атарушы тетіктер жне т.б., сондай-а соы шешуші абілетке ие, яни жаыртылатын хабарды абсолютті дл жне жуы мндері арасындаы шамалы айырмаларды байамайды.

Бзу мен кодтау осы длелдерді деректерді жуытап алпына келтіру пайдасы шін ескереді жне шамасы бойынша кейбір баыланатын ателер есебінен ысу коэффициенттерін алуа ммкіндік береді, бл кейбір уаытта бзбайтын дістер шін ысу дрежесінен ондаан есе артып кетеді.

Бзатын ысу дістеріні басым кпшілігі деректерді зін емес, одан, мысалы, Фурье дискреттік трлендіруіні коэффициенттерінен, косинусты трлендіруді коэффициенттерінен сияты сызыты трлендірулерді кодтауа негізделген.

JPEG - аса уатты алгоритм. Тжірибеде ол толы трлі тсті бейнелер шін де-факто стандарты болып саналады. Анытыы мен тсі салыстырмалы трде біралыпты згеретін алгоритм 8x8 айматарында сйеніп пайдаланылады. Осыны салдарынан, матрицаларды осындай аймаын косинустар бойынша екілік атара жіктеу кезінде, алашы коэффициенттер ана маызды болады. Сонымен JPEG-ке ысу, бейнелердегі тстерді згертуді біралыптылыы есебінен жзеге асырылады.

Алгоритм 24-биттік бейнелерді ысу шін фотографиялар саласындаы сарапшылар тобы арнайы зірлеген болатын. JPEG -Joint Photographic Expert Group - ISO - стандарттау жніндегі Халыкаралы йым шеберіндегі блімше. Ттастай аланда алгоритм - коэффициенттерді белгілі бір жаа матрицаларын алу шін бейнелеу матрицасына олданылатын дискреттік косинусойдалды трлендірулерге DCT (Discrete-Cosine Transform -СТ)-ке негізделеді. Алашкы бейнені алу шін кері трлендіру алынады.

DCT бейнелерді кейбір жиіліктер амплитудалары бойынша зара бледі. Сонымен, трлендіру кезінде біз кптеген коэффициенттері нлге жаын, я те болатын матрицаны аламыз. Бдан зге, адам кзіні жетілмегендігінен коэффициенттерді бейнелеу сапасын айтарлытай жоалтусыз нерлым рескелдеу аппроксимациялауа болады.

Бл шін коэффициенттерді кванттау (quantization) пайдаланылады. Е арапайым жадайда - бл арифметикалы бит бойынша о жаа ыысу. Мндай трлендірулерде апараттарды бір блігі жоалады, біра лкен ысу дрежесіне ол жеткізілуі ммкін.

256 дегейлердегі (8 екілік разрядтар) аныкты градацияларыны санымен зіні санаулар (пиксельдер) жиынымен берілген а-ара бейнені кодтау кезіндегі JPEG ысу алгоритміні жмысын арастырамыз. Бл бейнелерді сатауды е кп таралан тсілі - экрандаы рбір нктеге, оны айындыын анытайтын, бір байт (8бит - 256 ммкін мндер) сйкес келеді. 255 - е жоары айынды (а тс), 0 - е тменгі айынды (ара тс). Аралы мн ср тстердін бкіл алан гаммасын райды (58-сурет)

JPEG ысу алгоритміні жмысы бейнені 8×8 = 64 пиксельдер лшемімен квадратты блоктара бліктеу жолымен басталады.

ысуды екінші кезеі - бкіл блоктара дискреттік косинусты трлендіруді - DCT олдану. Дискреттік косинусты трлендіру бейнені кеістіктік крсетуден (санаулар немесе пиксельдер жиынымен) спектрлік крсетуге (жиілікті раушыларды жиынымен) кшуге жне керісінше жасауа ммкіндік береді.

IMG ( х, у ) бейнелеуден дискреттік косинусты трлендіру мынадай трде жазылуы ммкін:

 

DCT (u,v) = sqrt(2/N) i,j IMG (xi , yi )cos ((2i +1) u/2N)cos ((2j +1) v/2N), (183)

мндаы, = 8, 0 < i < 7, 0<j< 7, немесе, матрицалы формада

RES = DCTT *IMG * DCT (184)

мндаы, DCT - тмендегідей трге ие, лшемі 8x8 трлендіру шін базистік (косинусты) коэффициенттер матрицасы:

 

 

 

Сонымен, блока дискреттік косинусты трлендіруді лшемі 8x8 пиксельдері бейнесін олдану нтижесінде, сондай-а санауларды 8x8 лшеміне ие екі лшемді спектр аламыз. Басаша айтса, бейнені санауларын крсететін 64 саны, оны DCT-спектріні санауларын крсететін 64 сана айналады.

 

 

58-сурет. Ср тстер гаммаларыны аралы мндері

 

Дабыл спектрі - бл тиісті спектрлік раушылар, нтижесінде осы дабылды беретін жиына кіретін коэффициенттер шамалары. Дабыл соан зара блінетін, жекелеген спектрлік раушылар, кбінесе базистік атарымдар деп аталады. ПФ шін ртрлі жиіліктердегі синустар мен косинустар базистік атарымдар деп аталады.

8x8 DCT шін базистік атарымдар жйесі мына формуламен беріледі

(186)

ал базистік атарымдарды зі 59-суретте крсетілген сияты крінеді. (0,0) индекстерге сйкес келетін, аса тмен жиілікті базистік атарым суретті сол жа жоары брышында, ал аса жоары жиілік - тменгі о жата бейнеленген. (0,1) шін базистік атарым, бір координат бойынша косинусоид периодыны жартысын жне (1,0) индекстермен зге базистік атарым бойынша константаны крсетеді, біра 90°-а брылан.

Дискреттік косинусты трлендіру 8x8 пиксельдер бейнесіні блоктарын осы базистік атарымдарды рбірімен элемент бойынша айта кбейту жне осындылау жолымен есептеледі.

Нтижесінде, мысал шін, DCT - спектріні компоненті (0,0) индекстермен, бейне блогыны бкіл элементтеріні жиынын жай трде крсететін болады, яни блок шін орташа анытыты крсетеді. (0,1) индекспен компонентке бейнені бкіл горизонталь блшектері бірдей салматармен орташаландырылады, ал вертикаль бойынша е лкен салма бейнені жоары бліктеріні элементтеріне беріледі. DCT матрицасында оны компоненті нерлым тмен жне о жаа арай болса, ол сорлым бейнені нерлым жоары жиіліктік блшектеріне сйкес келеді.

59-сурет. 8x8 DCT шін базистік атарымдар жйесі

DCT-спектрі бойынша алашы бейнені алу шін (кері трлендіруді орындау шін), енді (0,0) индекстері бар базистік атарымды (0,0) координаталарымен спектрлік компонентке кбейту, кбейтінді нтижесіне, спектрлік (1,0) базистік атарымдар кбейтіндісіні нтижесіне компонентке (1,0) базистік атарымдарды (1,0) осу ажет.

Тменде келтірілген 10-кестеден бейне блоктарыны жне оны DCT-спектріні біріні санды мндерін круге болады:

10-кесте. Бейнені жне оны DCT-спектріні санды мні75

Алашы деректер
DCT нтижесі
235.6 -1 -12.1 -5.2 2.1 -1.7 -2.7 1.3
-22.6 -17.5 -6.2 -3.2 -2.9 -0.1 0.4 -1.2
-10.9 -9.3 -1.6 1.5 0.2 -0.9 -0.6 -0.1
-7.1 -1.9 0.2 1.5 0.9 -0.1 0.3
-0.6 -0.8 1.5 1.6 -0.1 -0.7 0.6 1.3
1.8 -0.2 1.6 -0.3 -0.8 1.5 -1
-1.3 -0.4 -0.3 -1.5 -0.5 1.7 1.1 -0.8
-2.6 1.6 -3.8 -1.8 1.9 1.2 -0.6 -0.4

 

Алынан DCT-спектрді те ызыты ерекшелігін атап теміз: оны е лкен мні сол жа жоары брышына шоырландырылан (тмен жиілікті раушылар), оны о жатаы тменгі блігі (жоары жиілікті раушылар) салыстырмалы трде шаын сандармен толтырылан. Бл сандар, бейне блогындаыдай болады: 8x8 = 64, яни зірге ешандай ысу болмаандай жне егер кері трлендіруді орындайтын болса, бейнені сондай блогын алатын боламыз.

 

ДРІС №15. Араласуынсыз санды арнаны беру кодтау апарат. Цифрлы нысанда процесі рнек апаратты кодтау. Цифрлы нысанда апарат техникалы ралдары. Криптографиялы апаратты жабу ралы ретінде Coding тиімді кодтау. Тиімді кодтау жне декодтау кодтары техникалы ралдары

 

Дрісті мтіні

Масаты: Криптографиялы кодтауды трлерін арастыру

Дріс жоспары

1. Кедергіге тзімді кодтау

2. Сызыты топты кодтар

3. Тривиальді жйелік кодтар

4. Циклдік кодтар

 

Негізгі тсініктер: абылданан хабар, артысызды кодтар, кодты ашыты, сызыты, кодты вектор, туызатын, ндіруші, рушы

Таырыпты мазмны: абылданан хабардаы атені анытау ммкін болу шін, ате кодты дрыс кодтан ажыратуа ммкіндік беретін, бл хабарды кейбір арты апараты болуы тиіс. Мысалы, егер берілген хабар ш абсолютті бірдей бліктерден трса, онда абылданан хабарлардаы дрыс символдарды ате символдардан бліп алу жнелтпені бір тріні (мысалы 0 немесе 1) жинаталу нтижелері бойынша жзеге асырылуы ммкін. Екілік кодтар шін бл дісті мынадай мысалмен крсетуге болады:

10110 - берілген кодты комбинация;

10010- 1-ші абылданан комбинация;

10100-2-ші абылданан комбинация;

00110 - 3-ші абылданан комбинация;

10110 - жинаталан комбинация. Байаанымыздай, бкіл абылданан ш комбинацияларда ателер боландыына арамастан, жинаталан комбинацияда ателер болмайды.

абылданан хабар сондай-а кодтан жне оны инверсияларынан труы ммкін. Инверсиялар коды, бірттас ретінде байланыс арнасына жіберіледі. абылдау шындаы ате код пен оны инверсияларын салыстыру кезінде шыады. Хабар символдарыны кез келгенін брмалау тыйым салынан комбинациялара келмес шін, кодта символдар атарында бір-бірінен згешеленетін комбинацияларды бліктеу, осы комбинацияларды бір блігіне тыйым салу жне сол арылы кода артыты енгізу ажет. Мысалы, біралыпты блокты кодта, рбір кодты комбинациялардаы нлдер мен бірліктерді траты араатынасымен кодты комбинацияларды шешілген (рсат етілген) деп санау керек. Осындай кодтар салмаы траты кодтар деген атауа ие болды. Екілік кодтар шін салмаы траты, кодты комбинациялар саныны п символдардаы зындыы мынаан те:

мндаы l- кодты сздегі бірліктер саны. Егер траты салма шарты олданылмаан болса, онда код комбинацияларыны саны анарлым лкен, атап айтанда 2n болар еді. Стандартты телеграфты код №3, салмаы траты кодты мысалы болып пайдаланылуы ммкін. Осы кодты комбинациялары, 7 тактыа, сол уаыт ішінде бір комбинация абылдануы тиіс трде рылады, яни рашанда ш осындай жне трт осындай емес жнелтпелер ажет болады. Осындай жнелтпелерді санын лкейту немесе азайту, ателерді бар болуын растайды.

Оларды сомасы рашанда жп немесе та болатындай алашы кодтара нлдерді, я бірліктерді осу дісі кода артышылыты енгізуді таы бір мысалы болып табылады. Кез келген бір символды тотап алуы рашанда жптылы (тактылы) шартын бзады жне ате аныталатын болады. Бл жадайда комбинациялар бір-бірінен, аз дегенде екі символдармен згешеленуі тиіс, яни код комбинацияларыны тура жартысы тыйым салынан болып саналады (жптылыа немесе керісінше тексеру кезінде бкіл та комбинациялар тыйым салынан болып саналады).

Ілгеріде айтылан барлы жадайларда хабар арты апарата ие болады. Хабарды артытыы, егер сол, бір кодты кп рет айталамаса, кода оны инверсиясын оспаса, егер код комбинацияларыны бір блігіне жасанды тыйым салмаса, оны одан да кп апараттар санынан тратындыын растайды. Біра бкіл айтылан артышылыты трлерін, ате комбинацияны дрыс комбинациядан ажырата білу шін енгізуге тура келеді.

Кодты кез келген екі комбинациялары бір-бірінен згешеленетін символдарды е аз саныны, артысызды кодтарын анытай алмайтыны, оны стіне ателерді тзей алмайтыны кодты ашыты деп аталады. Кодты бкіл комбинациялары бір-бірінен згешеленетін символдарды е аз саны е аз кодты ашыты деп аталады. Е аз кодты ашыты-кодты кедергіге тзімділігін анытайтын жне код артытыыны параметрі. Е аз кодты ашыты пен кодты тзетуші асиеті аныталады.

Жалпы жадайда r ателерді анытау шін е аз кодты ашыты

d0=r+1 (189)

Бір мезгілде анытау жне ателерді тзету шін ажет е аз кодты ашыты,

d()=r+s+1 (190)

мндаы, s -тзетілетін ателер саны.

ателерді тзететін ана кодтар шін,

d0=2s+1. (191)

Екілік кодты екі комбинациялары арасындаы кодты ашытыты анытау шін, 2 модуль бойынша осы комбинацияларды осындылау жне алынан комбинациялардаы бірліктер санын санау жеткілікті болады.

Кодты ашыты ымы кодтарды геометриялы модельдерін ру мысалында жасы игеріледі. Геометриялы модельдердегі п тбелердегі - брыштар, мндаы, п- кодты мнділігі кодты комбинациялар орналасан, ал бір комбинацияны екіншісінен бліп тратын п брыш абыраларыны саны кодты ашытыа те.

Егер А екілік кодты кодты комбинациясы В кодты комбинациядан d ашытыта болса, онда бл А кодында d символдарды, В кодын алу шін кері символдара ауыстыруы ажет, біра бл кодты тзетушілік асиеттерге ие болуы шін, d осымша символдар ажет дегенді білдірмейді. Екілік кодтарда бір атені анытау шін кодты апаратты разрядтарыны санына туелсіз 1 осымша символа ие болуы жеткілікті, ал е аз кодты ашыты d0=2.

Бір атені анытау жне тзету шін nM апаратты разрядтар саны мен пк тзетуші разрядтар саны арасындаы араатынас мына шарттарды анааттандыруы тиіс:

 

(192)

 

(193)

бл ретте, кодты комбинацияларды жалпы зындыы

п=пм+пк. (194)

Тжірибеде есептеу шін d0 =3 е аз кодты ашыты пен кодтарды баылау разрядтарыны санын анытау кезінде мына рнектерді пайдаланан ыайлы болады:

(195)

егер п толы кодты комбинацияларды зындыы белгілі болса жне

(196)

егер есептеулер кезінде берілген сандардан пм апаратты символдарды табу ыайлы болса.

(d0=4) ш еселі ателерді анытайтын кодтар шін,

 

(197)

немесе

(198)

 

(d0=5) бір немесе екі атені тзететін зындыы п символдардаы кодтар шін,

(199)

Тжірибеде есептеулер шін мына рнекті пайдалану ажет

(200)

(d0=7) 3 атені тзететін кодтар шін

(201)

(d0=2s+1) s ателерді тзейтін кодтар шін,

(202)

Сол жатаы рнек Хэммингті тменгі шекарасы ретінде белгілі, ал о жатаы рнек - Варшамов-Гильбетті жоары шекарасы ретінде белгілі.

Жуы есептеулер шін мына рнекті олдануа болады:

 

(203)

пк мні логарифм белгісіндегі рнекті ттас дрежесіне жаындайтыны аншалыты крсетілгенше атысты жоары немесе тменгі шекараа жаындайды деп жорамалдауа болады.

Тексерілетін символдар апаратты символдарды сызыты комбинациялары болып крсетілетін кодтар сызыты деп аталады.

Екілік кодтар шін сызыты операциялар ретінде 2 модуль бойынша осылыш пайдаланылады.

2 модуль бойынша осылыш ережесі мына тедіктермен аныталады:

Осы кода жататын нлдер мен бірліктерді тізбектілігін кодты вектор деп атаймыз.

Сызыты кодтарды асиеті: сызыты кодты кодты векторларыны жиыны (айырымы), аталан кода жататын векторды береді.

Сызыты кодтар 2 модуль бойынша осу операциясына атынасы бойынша алгебралы топ рады жне бл маынасында олар топты кодтар болып саналады.

Топты кодты асиеті: топты кодты кодты векторлары арасындаы е аз кодты ашыты нлдік емес кодты векторларды е аз салмаына те болады.

Кодты векторды аймаы (кодты комбинациялар) оны нлдік емес компоненттеріні санына те.

Екі кодты векторлар арасындаы ашыты 2 модуль бойынша алашы векторларды осу нтижесінде алынан вектор салмаына те. Осылайша, осы топты код шін Wmin=d0.

Топты кодтарды, лшемділігі пM жне пK кодты параметрімен аныталатын матрицалармен берген ыайлы болады. Матрицадаы жолдар саны пм -гe те, матрицалар бааналарыны саны пм + пк = n-гe те:

(204)

Осы матрицалар туызатын кодтар (n; k) - кодтар ретінде белгілі, мндаы k=пM , ал оан сйкес келетін матрицалар туызатын ндіруші, рушы деп аталады.

С туызушы матрица А жне Т (апаратты жне тексерілетін) екі матрицалармен крсетілуі ммкін. Т матрицалары бааналарыны саны nK-a, ал А матрицалары бааналарыны саны пм-ге те: