Дәріс 7. Ақпаратты сығу. Ақпаратты сығудың қарапайым амалдары.
Сығудың мақсаты – берілген ақпаратты сақтау
немесе тасымалдауға қажет бит көлемін азайту, бұл мәліметті
одан да тез жіберуге және тиімді және оперативті (соңғы
сақтау құрылғысынан берілген ақпаратты алу өте
тез болады, бұл мүмкін болады, егер мәліметтерді ашу жылдамдығы
ақпарат тасымалдаушыдағы деректерді есептеу жылдамдығынан жоғары
болады дегенді білдіреді) сақтауға мүмкіндік береді деген сөз.
Сығу, мысалы, дискеттегі көп ақпаратты жазуға, қатты
диск көлемін үлкейтуге, модеммен жұмыс жасауды тездетуге және
т.б. мүмкіндік береді. Компьютермен
жұмыс жасауда ZIP, GZ, ARJ
форматындағы деректердің және басқа да программалық
архиваторлары жиі қолданылады. Ақпаратты сығу әдісі ұзақ
уақыт бойы (80-жылдардың алғаш жартысына дейін), тәжірибеде
компьютерде сирек қолданылған математикалық теория
ретінде жасалынып шығарылған.
Ақпаратты сығу кейбір теориялық шектен асып түспеуі
керек. Осы шекті формальды түрде анықтау үшін n ұзындықтағы кез келген ақпараттық
мәліметті - тәуелсіз, бірдей үлестірілген хі
дискретті кездейсоқ шаманың
кезектестігі ретінде немесе бір Хі
дискретті кездейсоқ
шама мәнінің n ұзындықтағы
таңдауы ретінде қарастырамыз.
Дискретті кездейсоқ шаманың
бір кодталатын мәніне сәйкес келетін биттің орташа саны, осы дискретті кездейсоқ шаманың энтропиясынан аз болмауы
керектігі дәлелденген, яғни
ML(X) HX кез келген Х дискретті кездейсоқ шамасы және оның кез келген коды үшін.
Сонымен бірге, HXML(X)-1 түріндегі кодтаудың
(Шеннона-Фэно, Fano) бар екені туралы тұжырым да дәлелденген.
Х1 және Х2 тәуелсіз,
бірдей үлестірілген дискретті кездейсоқ шаманы қарастырайық. НХ1=НХ2
және I(Х1,Х2)=0, бұдан,
Х1 және Х2 орнына екі өлшемді дискретті
кездейсоқ шаманы айтуға
болады. n өлшемді
дискретті
кездейсоқ шама үшін аналогтық
тәсілмен Н
=nНХ1
–ді алуға болады.
, мұндағы
болсын, яғни
-
мәлімет
бірлігіндегі кодтың бит саны. Онда
- бұл
мәліметтерінің
шексіз жиынын жіберудегі мәлімет бірлігіндегі кодтың орташа бит саны.
үшін
Шеннона-Фэно коды
теңдігінен осы
код үшін
туындайды.
Осылайша, кедергі болмағанда
кодтаудың негізгі теоремасы дәлелденді, соның ішінде, барлық
мәліметтерді Шеннона-Фэноның әдісі арқылы түгелімен
кодтағанда, мәліметтердің
n ұзындығының өсуімен мәлімет бірлігі
энтропиясынан айырмашылығы аз болады. Бұндай кодтау тәжірибелік
тұрғыда жүзеге асырылмайды, себебі мәлімет ұзындығы
өскен сайын, бұл кодты құрастырудың көлемі
шектен тыс үлкейіп кетеді. Сонымен қатар, бұндай кодтау мәліметті
бөліктеп жіберуге мүмкіндік бермейді, бұл деректі жіберудің
үздіксіз процессіне қажет. Кодтау тәсілінің қосымша
жетіспеушілігі алынған кодты жіберу немесе сақтау үшін алғашқы
ұзындығымен бірге болуын қажет етеді, бұл сығу
тиімділігін кеміте түседі. Тәжірибеде сығу деңгейін көтеру
үшін блоктау әдісі қолданылады.
Таңдалған мәні арқылы
s-ті таңдауға болады, бұл егер барлық мәліметті s
ұзындықтағы блоктарға бөлсек, онда осындай
блоктарды Шеннона-Фэно тәсілімен кодтау арқылы мәлімет
бірлігіндегі биттің орташа санын энтропиядан
-ге көп етуге болады. Шынымен,
болады және т.б., яғни
Онда және
бұдан,
яғни s=1/ алу жеткілікті. Берілген
бойынша s минимумы 1/
-нан аз болуы мүмкін.
Мысал, - тәуелсіз және бірдей үлестірілген
дискретті кездейсоқ шама болсын,
ол тек қана 2 мәнді
және
қабылдай алады
. Онда
Мұндағы минималды кодтау –
бұл әрқайсысы ұзындығы 1 бит болатын 0 және
1 коды. Бұндай кодтауда бит саны мәлімет бірлігіне орта есеппен
1-ге тең болады. Мәліметті ұзындығы
2 болатын блоктарға бөлеміз. Ықтималдылықты үлестіру
және екі өлшемді дискретті кездейсоқ шама үшін кодтау заңы бойынша:
Онда осындай минималды кодтауға
бит саны мәлімет бірлігіне сәйкес орта есеппен мынадай болады:
яғни,
блоксыз кодтауға қарағанда аз. Ұзындығы 3 болатын
блок үшін мәлімет бірлігіне сәйкес бит саны орта есеппен 0,823, ал ұзындығы 4 болатын блок үшін
0,818 және т.б.
Жоғарыда қарастырылғанның
барлығында қарастырылатын дискретті кездейсоқ шама 2 мән бойынша (0 және 1)
кодталады делінген. Дискретті кездейсоқ шама m мәнімен кодталсын делік.
Онда дискретті кездейсоқ
шамасы үшін және оның кез келген кодтауы үшін
және
дұрыс. Сонымен қатар,
мынадай да кодтау бар,
және
, мұндағы n=
.
Бұрында қарастырылып
кеткен, сығу деңгейінің теориялық шегінің
формулалары, бірнеше рет жіберілетін мәлімет бірлігі кодының орташа
ұзындығына шектер белгілейді, яғни олар сығу днңгейінің,
мәліметті жүзеге асыратын дискретті кездейсоқ шама энтропиясынан кіші және кейбір мәліметтерді
жететін, төменгі шекарасы туралы ештеңе айтпайды.
Ақпаратты
сығудың қарапайым амалдары.
Шеннонна-Фэно әдісі
келесідей құрылады, дискретті кездейсоқ шаманың мәні ықтималдылықтың
кему ретімен орналасады, ал содан кейін бірдей ықтималдылықпен 2 бөлікке
бөлінеді, бірінші бөліктің кодына 0, ал екіншінің
кодына 1 қосылады.
Бұл мысалда алатынымыз
Тағыда бір мысал. Код іріктелгеннен кейін құрылады, яғни
В және С мәнін орналастырғаннан кейін.
Хаффмен(Huffman) әдісі 1952 жылы жасалынды. Ол тиімді және сығу
деңгейі бойынша ешқашанда Шеннонна-Фэно әдісіне жол бермейді,
сонымен қатар ол максималды тығыз сығады. Код екілік ағаштың
(бинарлық) көмегімен құрылады. Дискретті кездейсоқ
шама мәнінің ықтималдылығы
оның жапырағына жазылады, барлық ағаш жапыраққа
сүйене отырып құрылады. Ағаш түйініне жазылған
шама түйін салмағы деп аталады. Ең аз салмақтағы
екі жапырақтың салмақтарының қосындысына тең
салмаққа ие басшы түйінді құрайды. Тамырды құраған
соң, басшы түйінінен шығатын әрбір бұтаққа
0 немесе 1 мәнін жазу қажет. Дискретті кездейсоқ шаманың әрбір мәнінің
коды- бұл берілген мәнге сәйкес бұтақтың
тамырдан жапыраққа тіркесі кезінде алынатын сан.
Хаффмен және Шеннонна-Фэно әдісінің
тәсілдері үшін әрқашан мәліметпен бірге код
кестесін жіберу керек. Мысалы, 2 мысал үшін, 10 кодқа С символы,
0-ге А және т.б.сәйкес келетінін хабарлау керек.
Алдынғы екі мысалдығы дискретті кездейсоқ шаманың мәні үшін Хаффмен
кодын құрамыз.
Қолданылған әдебиеттердің тізімі: 1-5
1. Чисар И., Кернер Я. Теория информации— М.: Мир, 1985.
2. Шеннон К. Работы по теории информации и
кибернетики — М., Издательство иностранной литературы, 1963.
3. Яглом А., Яглом И. Вероятность
и информация — М.; Наука, 1973.
4. Введение
в криптографию /Под
общей редакцией В. В. Ященко. — М.: МЦНМО: "ЧеРо",
2000.
5. Джордж Ф. Основы кибернетики — М.:
Радио и Связь, 1984.