1. Жүйелер теориясының негізгі элементтерін нақтылап көрсетіңіз. Жүйенің қасиеттерін атаңыз және әр қасиетіне сипаттама беріңіз
жүктеу/скачать 2,1 Mb.
|
Қосымша мәліметтер
Үлестердің қосындысы әр бөлікте аз ерекшеленетіндей етіп, кестені екіге бөлеміз. Бірінші бөліктегі символдар коды 0-ден, ал екіншісі 1-ден басталсын: Символ a b c d Мәтіндегі үлесі 4/10 3/10 2/10 1/10 Үлестер қосындысы 4/10 6/10 Кодтың бірінші цифры 0 1 Кестенің бір символдан артық бөліктеріне осы процедураны қайталаймыз: Символ a b c d Мәтіндегі үлесі 4/10 3/10 2/10 1/10 Үлестер қосындысы 4/10 6/10 Кодтың бірінші цифры 0 1 3/10 3/10 Кодтың екінші цифры 0
Символ a b c d Мәтіндегі үлесі 4/10 3/10 2/10 1/10 Үлестер қосындысы 4/10 6/10 Кодтың бірінші цифры 0 1 3/10 3/10 Кодтың екінші цифры 0
2/10
Кодтың үшінші цифры 0 1 Сонымен әліпби символдары үшін жаңа код алынды: a – 0, b – 10, c – 110 и d – 111. аbabcaacdb хабарламасы 19 битті құрайды. 1- мысал. a, b, c, d симводары берілген олардың жиіліктері: fa = 0,5; fb = 0,25; fc = 0,125; fd = 0,125. Шеннон-Фано әдісімен тиімді кодты тұрғызыңыз. Шешуі: Алғашқы деректерді кестеге жазайық
Тұрғызылған кодтың тиімділігін формула бойынша есептейміз lср = 0,5*1 + 0,25*2 + 0,125*3 + 0,125*3 = 1,75.
Средняя длина кода К2=1∙0.49+2∙0.21+3∙0.21+3∙0.09=1.81; в расчете на один символ К1=К2/2=0.905. Коэффициент эффективности кода КОЭ = 0.88/0.905 = 0.972. 2) Составим алфавит из трёхбуквенных комбинаций.
Средняя длина кода К3=2.686; в расчете на один символ К1=К3/3=0.895. Коэффициент эффективности кода КОЭ = 0.88/0.895 = 0.983. 28. АҚПАРАТТЫҢ ҚҰРЫЛЫМДЫҚ ӨЛШЕМДЕРІН АТАҢЫЗ. ҚҰРЫЛЫМДЫҚ, ГЕОМЕТРИЯЛЫҚ, АДДИТИВТІ ӨЛШЕМДЕРГЕ ТОЛЫҚ СИПАТТАМА БЕРІҢІЗ. АДДИТИВТІ ӨЛШЕМГЕ МЫСАЛ КЕЛТІРІҢІЗ. Ақпараттар теориясы– бұл ақпаратты алу, түрлендіру, жинау, өңдеу және беру жайлы ғылым. Құрылымдық теория жеке ақпараттық хабарламаларды құру құрылымын қарастырады. Статистикалық теория анықталмағандық өлшемі тұрғысынана ақпаратты бағалайды. Семантикалық теория ақпараттың мағыналық сипаттамаларын оқытады: бағалылығы, пайдалылығы, тиімділігі, ақпаратты өткізу қабілеттілігі, ақпараттық бөгеуілге тосқауыл беруі және құрамы. Құрылымдық теорияда ақпараттың геометриялық, комбинаторлық және аддитивтік өлшемдері қарастырылады. Ең кең тарағаны- екілік аддитивтік өлшем, ол Хартли өлшемі (1928ж.) деп те аталады. Ақпараттың саны екілік өлшеммен - битпен өлшенеді. I=log2m, мұндағы, I – ақпарат саны немесе көлемі m – элементтер саны Геометриялық өлшем ақпарат көлемін бағалайды. Комбинаторлық өлшем ақпаратты әр түрлі комбинациялармен өрнектегенде қолданылады. Мысалы, 1110 саны берілген. 0 саны орын ауыстырғаннан кейін комбинация өзгерді: 0111. Яғни, 14 саны 7-ге ауысты. 29. ШУЛЫ КАНАЛДАРДАҒЫ АРТЫҚТЫҚҚА АНЫҚТАМА БЕРІҢІЗ ЖӘНЕ СИПАТТАҢЫЗ. МЫСАЛ КЕЛТІРІҢІЗ. ӨЗАРА АҚПАРАТ ЖӘНЕ ОРТАША ӨЗАРА АҚПАРАТҚА АНЫҚТАМА БЕРІҢІЗ ЖӘНЕ ФОРМУЛАЛАРЫН ЖАЗЫҢЫЗ. ҚАСИЕТТЕРІН АТАҢЫЗ. Кодтау мақсаты – тасымалдауға немесе ақпаратты сақтауға кететін шығындарды азайту. Есептің шешімі жіберілетін мәліметтер ағымынан артық ақпаратты «жою» деп түсіндіруге болады. Жіберілетін ақпаратты байланыс каналдары арқылы жіберу кезіндегі бөгеуілдер мен бұрмалаудан қорғау немесе ақпаратты сақтау мақсатында кодтау қарастырылады. Тиімді байланыс жүйесін құру үшін жіберілетін ақпараттың көлемін азайту мақсатында алдымен хабарламадағы артықты жоюға, содан кейін ақпаратты қателіктерден қорғау үшін артықтықты енгізу керек. Шумен күресу теорияcының ең маңызды идеясы мынада, байланыс каналы бойынша берілген код артықтық (избыточность) болуы керек. Код артықтығы – бұл берілетін ақпараттың немесе деректердің бірнеше рет қайталануы. Код артықтығы өте үлкен бола алмайды. Себебі бұл байланыстың қымбаттауына және кешеуілдеп жетуіне ықпал етеді. Кодтау теориясы оңтайлы кодты алуға тырысады: берілетін ақпарат артықтығы мүмкіндігінше минимум, ал қабылданған ақпарат нақтылығы максимум болуы тиіс. Энтропиясы үлкен (максимум) хабарламалар берілген ақпараттың символының санына қатысты оңтайлы болып табылады. Сандық бағалау өлшемі сығу коэффициентімен бағаланады: мұндағы Н(ξ) – нақты хабарлама энтропиясы, max H(ξ) – нақты хабарламаға сәйкес оңтайлы энтропия. Артықтықты сандық бағалау өлшемі артықтық коэффициенті болып табылады. М ысалы. Хабарламалар көзі алфавитінен символдар береді. Символдарды беру ықтималдықтары: Ақпарат саны мен артықтығын табу керек. Шешуі. Шеннон формуласы бойынша бит Артықтық анықтамасы бойынша Канал коды деп алфавит үстіндегі A={xm}, m=1,…,M , A Xn кез келген тізбектер жиыны айтылады. Тізбектердің өзі кодтық сөз, олардың ұзындығы n код ұзындығы, тізбектер саны М код қуаттылығы деп аталады, ал R = logM / n мәні код жылдамдығы деп аталады. Код жылдамдығы бит канал символымен өлшенеді. Жекелей жағдайда M=2k болған кезде әрбір кодтық сөзге k ақпараттық символдан тұратын тізбекті сәйкестендіруге болады (k бит). Оларды жіберу үшін n ұзындықты кодтық сөз қолданылады. Канал символына биттерді жіберу жылдамдығы R = logM / n = k / n бит/символын құрайды. Өзара ақпарат. Орташа өзара ақпарат. Байланыс каналдарын меңгеру барысында канал кірісінде бақыланатын символдар бойынша хабарламаны жіберу туралы ақпарат алу мүмкіндігі туындайды. X және Y дискретті ансамбльдердің XY = {(x, y), p(x, y)} берілген көбейтіндісі үшін y ∈Y шығыс символдарында болатын кіріс ансамблінің x ∈ X элементтері туралы ақпаратты сандық түрде өлшеу керек болса, онда мұндай ақпаратқа сәйкес келетін шама (x, y)∈ XY кез келген жұптары үшін I (x; y) = I (x) − I (x | y) арақатынасымен анықталатын өзара ақпарат бар болады. Өзара ақпараттың қасиеттері: 1. Симметриялық: I (x; y) = I ( y; x) . 2. Егер x және y тәуелсіз болса, онда I (x, y) = 0 X және Y ансамбльдері арасындағы орташа өзара ақпарат деп I (X;Y) = M[I (x; y)] өлшемі айтылады. Орташа өзара ақпаратты ортақ үлестірім ықтималдығы арқылы өрнектейтін формула Орташа өзара ақпараттың қасиеттері 1 қасиет. Симметриялық I (X;Y) = I (Y; X ) . 2 қасиет. Теріс болмаушылық: I (X;Y) ≥ 0. 3 қасиет. X және Y ансамбльдері тәуелсіз болған кезде, тек сол кезде ғана I(X;Y)=0 тепе-теңдігі орын алады. 4 қасиет. I (X;Y) = H(X ) − H(X | Y) = = H(Y) − H(Y | X ) = = H(X ) + H(Y) − H(XY) . 5 қасиет. I (X;Y) ≤ min{H(X ),H(Y)}. 6 қасиет. I (X;Y) ≤ min{log | X |, log | Y |}. 7 қасиет. Өзара ақпарат I (X;Y) – p(x) үлестірім ықтималдығының дөңес ∩ функциясы. 8 қасиет. Өзара ақпарат I (X;Y) – p(у|x) шартты үлестірімінің ойыс ∪ функциясы. 30.ЦИФРЛЫҚ АҚПАРАТТЫ СЫҒУ ӘДІСТЕРІ. Анықтама. Ақпаратты кодтау артықтық болып табылады, егер алғашқы ақпаратты декодтауға қарағанда, алынған кодта бит саны артық болса. Ақпаратты сақтау және беру нақты ресурстар шығынын қажет етеді. Деректерді сығу (сақтау немесе байланыс каналы арқылы беру алдында) осы шығындарды азайтуға мүмкіндік береді. Ақпараттарды сығудың теориялық негізі 1940 жылдардың соңында қалана бастады. К.Шеннонның мақаласы жарияланды: «Коммуникацияның математикалық теориясы». Сығу әдістерін екі үлкен топқа бөлуге болады: 1. Қайтарылатын 2. қайтарылмайтын Қайтарылатын алгоритмдер кіріс деректерін ең ықшам кодталатын формаға келтіре отырып, тек кіріс деректерінің берілу тәсілін өзгертеді. Мұндай алгоритмдер үшін кері алгоритм бар, олар сығылған жиымнан алғашқы деректерді қалпына клтіре алады. Қайтарылатын алгоритмдерді кез-келген типті деректерді сығу үшін қолдануға болады. Ақпаратты жоғалтпай сығылатын файлдар форматтары: • GIF, TIF, PCX, PNG — графиктік деректер үшін; • AVI — кезектесетін видео- және дыбыс деректері үшін; • ZIP, ARJ, RAR, LZH, LH, CAB — деректердің кез-келген типі үшін Анықтама: Сығу әдісі қайтарылатын деп аталады, егер сығу кезінде деректер жоғалмайтын болса. Қайтарылатын әдістердің негізгілері: Қаттау (упаковка) әдісі Хаффман алгоритмі RLE алгоритмі Лемпель—Зив алгоритмі RLE (ағ. Run-Length Encoding — қайталану санын есепке ала отырып кодтау) алгоритмінің негізі қайталанатын тізбектерді табу қағидасына сүйенеді: қайталанатын фрагменттер мен қайталану коэффициенттері. RLE кодтау әдісімен ақпаратты кодтау: тізбек басқару байттарынан тұрады. Егер сандар тізбегі бірнеше рет қатарынан қайталанса, онда басқарушы байт 1-ден басталады да, одан кейін қайталанатын сан жазылады. Егер сандар тізбегі қайталанбаса, онда басқарушы байт 0-ден басталады да, сандар өзгертілмейді. RLE кодтау әдісімен ақпаратты қалпына келтіру: тізбек басқару байттарынан тұрады, егер басқару байтының басы 1 –ге тең болса, онда басқару байтынан кейінгі деректерді сонша рет қайталау керек. Ал егер 0-ге тең болса, онда одан кейін байттарды өзгертпеу керек. Егер басқару байты 10000111 болса, онда одан кейінгі байтты 7 рет қайталау керек, ал басқару байты 00000100 болса, онда одан кейінгі 4 байтты өзгеріссіз қалдыру керек. Сығу дәрежесін жақсарту үшін жиі қайталанатын символдарды қысқа кодпен, ал сирек кездесетіндерді ұзын кодпен алмастыру керек. Бүл әдіс идеясын ұсынған - Д. Хаффман (1952 жыл). Хаффман алгоритмінің көмегімен деректерді сығу: кездесетін символдар жиілігі есептелінеді, содан кейін Хаффман кодтау ағашы тұрғызылады. Кодтау ағашы бойынша символар коды жасалынады. Хаффман ағашын тұрғызу алгоритмі: Алғашқы символдар бос түйіндер тізімін құрайды. Әр түйіннің алғашқы хабарламадағы символдар санына тең салмағы бар. Тізімнен ең кіші салмағы бар екі бос түйін таңдалады. Олардың салмақтарының қосындысына тең салмағы бар «ата-ана» түйіні құрылады, ол «ұрпақтарымен» доға арқылы байланысады. «Ата-анадан» шығатын бір доғаға 1, екіншісіне 0 қойылады. «Ата-ана» бос түйінді тізімге қосылады, ал оның «ұрпақтары» тізімнен жойылады. Тізімдегі қадам тек бір бос түйін қалғанша қайталана береді. Ол ағаштың басы (тамыры) болып есептелінеді. М ысалы. «КОЛ_ОКОЛО_КОЛОКОЛА» мәтіні үшін Хаффман ағашын тұрғызу және префикстік кодты алу: Лемпель—Зив алгоритмдері (LZ77, LZ78) Хаффман алгоритмінде символдар кодталса, ал L Z77, LZ78 алгоритмдерінде сөздер кодталады. LZ77 алгоритмі : • КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ КОЛО(-4,3)_0(-8,4)_(-14,7)ЬНИ. жүктеу/скачать 2,1 Mb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||