Лекция 1 Ақпарат теориясы ақпараттық жүйелерді сипаттаудың сапалы және сандық әдістері негізі ретінде. Ақпаратты өлшеу
жүктеу/скачать 1,34 Mb.
|
6-Лекция
| Ақпаратты сығу
Сығудың мақсаты – берілген ақпаратты сақтау немесе тасымалдауға қажет бит көлемін азайту, бұл мәліметті одан да тез жіберуге және тиімді және оперативті (соңғы сақтау құрылғысынан берілген ақпаратты алу өте тез болады, бұл мүмкін болады, егер мәліметтерді ашу жылдамдығы ақпарат тасымалдаушыдағы деректерді есептеу жылдамдығынан жоғары болады дегенді білдіреді) сақтауға мүмкіндік береді деген сөз. Сығу, мысалы, дискеттегі көп ақпаратты жазуға, қатты диск көлемін үлкейтуге, модеммен жұмыс жасауды тездетуге және т.б. мүмкіндік береді. Компьютермен жұмыс жасауда 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 болатын блок үшін мәлімет бірлігіне сәйкес бит саны орта есеппен ,823, ал ұзындығы 4 болатын блок үшін 0,818 және т.б. Жоғарыда қарастырылғанның барлығында қарастырылатын дискретті кездейсоқ шама 2 мән бойынша (0 және 1) кодталады делінген. Дискретті кездейсоқ шама m мәнімен кодталсын делік. Онда дискретті кездейсоқ шамасы үшін және оның кез келген кодтауы үшін және дұрыс. Сонымен қатар, мынадай да кодтау бар, және , мұндағы n=. Бұрында қарастырылып кеткен, сығу деңгейінің теориялық шегінің формулалары, бірнеше рет жіберілетін мәлімет бірлігі кодының орташа ұзындығына шектер белгілейді, яғни олар сығу днңгейінің, мәліметті жүзеге асыратын дискретті кездейсоқ шама энтропиясынан кіші және кейбір мәліметтерді жететін, төменгі шекарасы туралы ештеңе айтпайды. жүктеу/скачать 1,34 Mb. Достарыңызбен бөлісу:
|