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

S=K₁+1+λ, n=n₁ (149)

деп ұйғарамыз, мұндағы, λ- K₁ + 1-ді mⁿ₁-ге дейін толықтыратын санды былайша жазуға болады:

n_{i = = + Ɵ = + Ɵ}

 

 

мұндағы, Ɵ = К санын ұлғайта отырып, ол қосындыланатын (К_Р ∞ және К _1Р ∞ кезінде) санмен салыстыру бойынша Ɵ санын азайтуға болады. Осылай ойлай отырып, бөлетін комбинацияларды ескеріп, n₂ үшін өрнек аламыз:

L=N_u^k (Ψ және ϒ жайлы да, λ және Ɵ жайлы сияқты айтуға болады).

Өйткені бұл ретте кодтық комбинациялардың орташа ұзындығы n= (1-d)*n₁ +d*n₂-г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 (x_i , y_i)cos ((2i +1)π u/2N)cos ((2j +1)π v/2N), (183)

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

RES = DCT^T *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 - кодтық сөздегі бірліктер саны. Егер тұрақты салмақ шарты қолданылмаған болса, онда код комбинацияларының саны анағұрлым үлкен, атап айтқанда 2ⁿ болар еді. Стандартты телеграфтық код №3, салмағы тұрақты кодтың мысалы болып пайдаланылуы мүмкін. Осы кодтың комбинациялары, 7 тактыға, сол уақыт ішінде бір комбинация қабылдануы тиіс түрде құрылады, яғни әрқашанда үш осындай және төрт осындай емес жөнелтпелер қажет болады. Осындай жөнелтпелердің санын үлкейту немесе азайту, қателердің бар болуын растайды.

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

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

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

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

d₀=r+1 (189)

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

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

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

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

d₀=2s+1. (191)

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

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

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

Бір қатені анықтау және түзету үшін n_M ақпараттық разрядтар саны мен п_к түзетуші разрядтар саны арасындағы арақатынас мына шарттарды қанағаттандыруы тиіс:

 

(192)

 

(193)

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

п=п_м+п_к. (194)

Тәжірибеде есептеу үшін d₀ =3 ең аз кодтық қашықтық пен кодтардың бақылау разрядтарының санын анықтау кезінде мына өрнектерді пайдаланған ыңғайлы болады:

(195)

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

(196)

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

(d₀ =4) үш еселі қателерді анықтайтын кодтар үшін,

 

(197)

немесе

(198)

 

(d₀=5) бір немесе екі қатені түзететін ұзындығы п символдардағы кодтар үшін,

(199)

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

(200)

(d₀=7) 3 қатені түзететін кодтар үшін

(201)

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

(202)

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

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

 

(203)

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

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

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

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

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

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

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

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

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

Екі кодтық векторлар арасындағы қашықтық 2 модуль бойынша алғашқы векторларды қосу нәтижесінде алынған вектор салмағына тең. Осылайша, осы топтық код үшін W_min=d₀.

Топтық кодтарды, өлшемділігі п_M және п_K кодтың параметрімен анықталатын матрицалармен берген ыңғайлы болады. Матрицадағы жолдар саны п_м -гe тең, матрицалар бағаналарының саны п_м + п_к = n-гe тең:

(204)

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

С туғызушы матрица А және Т (ақпараттық және тексерілетін) екі матрицалармен көрсетілуі мүмкін. Т матрицалары бағаналарының саны n_K-ғa, ал А матрицалары бағаналарының саны п_м-ге тең: