130
разрядтардын бір бөлігі арнайы түрде құрастырылатын болса. a
0
, a
1
, a
2
разрядтарды басқа
разрядтардың модулі 2 бойынша үйірткісі ретінде қарастыруға болады, олар келесі
теңдеуге қатысады:
a
0
= a
3
a
5
a
6
a
1
= a
3
a
4
a
6
a
2
= a
3
a
4
a
5
Табылған тәуелсіздіктер берілген ақпараттық сөздер бойынша кодты сөздерді
генерациялаға, және де қабылданған кодты сөздер үшін синдромды есептеуге мүмкіндік
береді.
Бастапқы ақпараттық сөз 1101 тең болсын, яғни a
6
=1, a
5
=1, a
4
=1, a
3
=1. Бөгеуілге
тұрақты Хэмминг (7,4)-кодының мүмкін кодты сөзіне оны түрлендіру үшін бақылау
разрядтарды есептейік:
a
1
= 1 0
1 = 1,
a
1
= 1 0
1 = 0,
a
2
= 1 0
1 = 0.
Сонымен, бақылау разрядтарды еске алғанда кодты сөз 1101001 тең болады.
Егер беру немесе сақтау процесінде сөз бұрмаланбаған болып қалса, онда оның
синдромы s
0
…s
2
сәйкес тең болады:
s
0
= 1 1 1
1 = 0,
s
1
= 0 1 0
1 = 0,
s
2
= 0 1 0
1 = 0.
Тек нөлден ғана тұратын синдром қателік жоқ дегенді көрсетеді және нөлдік
қателік векторға сәйкес.
Беру немесе сақтау барысында сыртқы факторлар әсерінен кодты сөздің жеке
разряды бұрмаланған болсын. Мысалы, 1101001 сөздің орнына 1001001 сөз қабылданды.
Бұл жағдайда синдром нөлге тең болмайды: s
0
…s
2
сәйкес тең болады:
s
0
= 1 1 0
1 = 1,
s
1
= 0 1 0
1 = 0,
s
2
= 0 1 0
0 = 1.
Синдром 101 қателік векторға 0100000 сай болады, бұл кезде бірлік қателік болған
разрядты көрсетеді. Оны түзету үшін қабылданған бұзылған кодты сөзді қателік векторы
мен модулі 2 бойынша қосу жеткілікті.
Хэмминг (7,4)-кодының артықтығын есептейік:
%
43
%
100
7
4
7
%
100
n
k
Q
Бұл өте үлкен мән. Тәжірибеде одан күрделі кодтар жиі қолданылады, олар
бөгеуілге тұрақты жақсығырақ сипаттамаларын қамсыздандырады.
14.3 Деректерді сығу принциптері
Жоғарыда айтылғандай, шифрлауға деректерді дайындаудың маңызды есебінің бірі
олардың артықтығын азайту және қолданатын тілдің статистикалық заңдылықтарын
тегістеу. Артықтықты жарым-жартылай жоюына деректерді сығу арқылы жетеді.
Ақпаратты сығу бұл бастапқы хабарды бір кодты жүйеден басқаға түрлендіру
процесі, нәтижесінде хабар мөлшері азаяды. Ақпаратты сығу үшін арналған
алгоритмдарды екі үлкен топқа бөлуге болады: шығынсыз сығу (қайтымды сығу) және
шығыны бар сығу (қайтымсыз сығу).
Қайтымды сығу декодтаудан кейін деректерді абсолют дәл қалпына келтіруді
айтады және ол кез келген ақпаратты сығу үшін қолданылу мүмкін. Ол әрқашан
ақпараттық құрылымын жоғалтпай ақпараттың шығу ағын көлемінің азаюына әкеледі.
Онан әрі, шығу ағыннан, қайталанатын немесе декомпресстау алгоритмы көмегімен, кіру
131
ағынды алуға болады, ал қалпына келтіру процесі декомпрессия немесе түйіншекті шешу
деп аталады. Шығынсыз сығу мәтін, орындалу файлдар, сапалы дыбыс және графика үшін
қолданылады.
Қайтымсыз сығуда әдетте сығу дәрежесі салыстырмалы жоғары, бірақ декодталған
деректердің бастапқыдан кейбір ауытқулар болу мүмкін. Тәжірибеде декомпрессиядан
кейін бастапқы ақпаратты дәл қалпына келтіруді талап етпейтін бірнеше міндеттер бар:
дыбыс, фото- немесе видео бейнелер. Мысалы, мультимедиалық ақпарат форматта JPEG
пен MPEG қайтымсыз сығу қолданылады. Қайтымсыз сығу криптографиялық
шифрлаумен бірге әдетте пайдаланбайды, себебі криптожүйеге қойылатын негізгі талап
дешифрланған деректердің бастапқыға толық ұқсастығы.
Деректерді қайтымсыз сығудың кейбір ең кең таралған тәсілдерін қарап шығайық.
Ең танымал қарапайым жол және ақпаратты қайтымсыз сығу алгоритмы – бұл
тізбектер сериясын кодтау (Run Length Encoding – RLE). Осы жолдың мағынасы –
қайталанатың байт тізбектерін немесе серияларын бір кодтайтын байт-толтырушыға және
олардың қайталау санын есептеуішке ауыстыру. Осындай барлық ұқсас әдістердің
проблемасы - нәтижелі байттар ағынында кодталған серияны басқа кодталмаған байттар
тізбектерінен айыру. Проблеманы кодталған тізбектердің басына белгілер қойып шешуге
болады. Осындай белгілер ретінде кодталған серияның бірінші байттағы биттердің
сипатты мәні және кодталған серияның бірінші байт мәні болу мүмкін. RLE әдістің
кемшілігі төмен сығу дәрежесі немесе аз сериялар саны бар файлды кодтау бағасы.
Ақпаратты бір қалыпты кодтауда хабарға, оның пайда болу ықтималдығына
қарамастан, бірдей бит саны бөлінеді. Сонымен қатар, егер жиі кездесетін хабарларды
қысқа кодты сөздермен кодтаса, ал сирек кездесетіндерді - ұзынырақ сөздермен кодтаса,
онда берілетің хабарлардың жалпы ұзындығы азаяды деп болжау жасауға болады. Мұнда
айнымалы ұзындығы бар кодты сөзден тұратын кодты пайдалану қажеттілігіне
байланысты проблемалар туады. Осындай кодты құруға бірнеше жолдар бар.
Тәжірибеде кең қолданылатылардың біреуі сөздік әдістер, олардың негізгі өкілдері
Зива мен Лемпел алгоритмдары. Оның негізгі идеясы - кіру ағынның фрагменттері
(«сөйлемдер») мәтінде бұрын болған орынға көрсететін сілтегішпен ауыстырылады.
Әдебиетте осындай алгоритмдар LZ сығу алгоритмы деп белгіленеді.
Сол сияқты әдіс мәтін құрылымына тез лайықтанады және қысқа функционалды
сөздерді кодтай алады, себебі олар мәтінде жиі кездеседі. Жаңа сөздер мен сөйлемдер
бұрын кездескен сөздердің бөліктерінен де құрастырылу мүмкін. Сығылған мәтіннің
декодтауы тікелей жүргізіледі, - сілтегішті сөздіктен алынған дайын сөйлеммен
ауыстырады. Тәжірибеде LZ-әдісі жақсы сығуды жеткізе алады, оның маңызды қасиеті
декодердің өте жылдам жұмысы.
Ақпаратты сығудың тағы бір жолы кодер мен декодеры қарапайым аппараттық
жүзеге асыруы бар Хаффман коды болып табылады. Алгоритмның идеясы мұндай:
хабарға символдардың кіру ықтималдығын біле отырып, айнымалы ұзындығы бар бүтін
бит санынан тұратын кодты құру процедурасын бейнелеуге болады. Үлкен ықтималдығы
бар символдарға қысқа код беріледі, ал сирек кездесетін символдарға – ұзынырақ. Осы
себептен кодты сөздің орта ұзындығы қысқарады және сығудың тиімділігі өседі. Хаффман
кодында бірегей префиксы (кодты сөздің басы) бар, сондықтан оларды айнымалы
ұзындығына қарамастан бір мәнді декодтауға болады.
Хаффман классикалық кодын синтездеу процедурасын жүргізу үшін хабар көзінің
статистикалық сипаттамасы туралы априорды ақпарат болу қажет. Басқаша айтқанда,
хабарды құрайтын қандай да болса символдардың пайда болу ықтималдығы
құрастырушыға белгілі болу керек. Хаффман кодының синтезін қарапайым мысал
көмегімен қарастырайық.
Ақпарат көзі төрт әртүрлі символды S
1
…S
4
генерациялайтын болсын, олардың
шығу ықтималдығы p(S
1
)=0,2, p(S
2
)=0,15, p(S
3
)=0,55, p(S
4
)=0,1. Символдарды шығу
ықтималдығы азаю бойынша сұрыптайық және кесте түрінде көрсетейік (сурет 14.3, а).
Достарыңызбен бөлісу: |
