ответы основы информоционных систем. ОИС отв. Жйелер теориясыны негізгі элементтерін натылап крсетііз. Жйені асиеттерін атаыз жне р асиетіне сипаттама берііз

• Название: Жйелер теориясыны негізгі элементтерін натылап крсетііз. Жйені асиеттерін атаыз жне р асиетіне сипаттама берііз
• Анкор: ответы основы информоционных систем
• Дата: 14.05.2021
• Размер: 1.95 Mb.
• Имя файла: ОИС отв.docx
• Тип: Документы; #205007
• страница: 7 из 10

Шартты энтропияға анықтама беріңіз және формуласын жазыңыз.   Шартты энтропия қасиеттерін ашып жазыңыз. Мысал келтіріңіз. Жалпы энтропияның анықтамасы мен формуласын жазыңыз.



Х шамасының Y шамасына қатысты шартты энтропиясы

, (1.5)

мұндағы P(x_i/y_j)  Y шамасы y_j мәнін қабылдады деген шартпен, Х шамасының x_i мәнінің ықтималдығы (шартты ықтималдық).

Y шамасының y_j мәніне қатысты Х шамасының шартты энтропиясы

. (1.6)

X-тің Y-ке қатысты шартты энтропиясы

.

18. 
    Хабарламалар және сигналдар туралы жалпы мәліметтер беріңіз.  Ақпараттық жүйелерде ақпаратты беру үдерісін сипаттаңыз. 
    

Хабарлама- ақпарат көзінен алынатын символдар жиынтығы.

Хабарлама: Дискретті, Үзіліссіз.

Үзіліссіз хабарлама-хабарламанның ақпарат көзінен ақпаратты қабылдаушыға берілетін уақыт көзімен сипаттталады, ол символ, сұлба, график т.с.с. болуы мүмкін.

Дискретті хабарлама-бірнеше бөлікке бөлінген хабарламалардың жинтығы.

Сигнал (лат. signum — белгі) — байланыс каналы бойынша хабарламаны беруді қамтамасыз ететін өзгермелі физикалық шама. Сигналды ақпаратқа түрлендіру демодуляция, құрылғы демодулятор, декодер деп адалады.

Бөгеулер сигналдарды түрлендіе алатын сыртқы әсерлер , шабылдауылдар.

Егер байланыс линииясы бөгеусіз болса, онда:



Ақпараттық жүйеде ақпаратты беру үдерісі:

19. 
    Модуляция және демодуляция процедураларының қызметі мен мазмұны туралы жазыңыз. Модуляция түрлерінің салыстырмалы сипаттамаларын келтіріңіз. 
    

Ақпараттық сигналдар шектеулі диапазон шегінде кейбір шамалар мәндерінің сансыз мөлшерін көрсете алады.

Цифрлі (дискретті) сигналдар мәндердің біреуіне немесе түпкілікті жиынтығына ие бола алады.

Аналогты сигналдар бұрмалануға икемді, есесіне деректерді кодерлеу мен декодерлеу цифрлі сигналдар үшін қарапайым жүзеге асады.

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

ЭЕМ келіп түсетін цифрлі деректер модулятор – демодулятор көмегімен аналогты формаға түрленеді.

Цифрлі деректерді аналогты формаға түрлендірудің үш тәсілі немесе модуляцияның үш әдісі мүмкін:

Амплитудты модуляция – жүйелі берілетін ақпарат биттеріне сәйкес негізгі синусоидалды тербелістің амплитудасы ғана өзгереді: мысалы, бірлік бергенде тербеліс амплитудасы үлкен болады, ал ноль бергенде – кіші немесе негізгі сигнал типті болмайды;

• 
  Жиілікті модуляция, мұндай модульденетін сигналдар әрекетімен тек негізгі синусоидалды тербеліс жиілігі ғана өзгереді: мысалы, ноль бергенде – төмен;
  
• 
  Фазалық модуляция, мұнда тек негізгі синусоидалды тербелістің фазасы ғана өзгереді: сигнал 1 – ден сигнал 0 өткенде немесе керісінше болғанда фаза 180° өзгереді;
  

Ақпараттық канал – ақпарт көзіне ақпаратты беру үшін арналған байланыс линияларымен біріккен құрылғы.

Каналдың тиімділігі ақпаратты беру жылдамдығымен, құрылғының жұмыс істеу сенімділігімен сипатталады.

Ақпараттық канал: ақпаратты енгізу жылдамдығы, ақпаратты беру жылдамдығы және каналдың өткізу қабілеті.

Ақпаратты енгізу жылдамдығы - уақыт бірлігінде хабарлар көзінен ақпараттық каналға енгізілген ақпараттың орташа саны.

Ақпаратты беру жылдамдығы– уақыт бірлігінде ақпараттық канал бойынша берілетін ақпараттың орташа саны.

Каналдың өткізу қабілеті– канал үшін ақпаратты беру жылдамдығының неғұрлым жеткілікті шамасы.

Ақпаратты енгізу жылдамдығы каналдың өткізу қабілетінен асып кетпеуі керек, болмаса канал арқылы берілетін ақпарат толық түспеуі мүмкін.

Каналдың қабілеті ақпаратты беру санымен сипатталады:

С=maxI(m) , бит/символ

Сигнал әр түрлі параметрлермен сипатталуы мүмкін. Канал бойынша ақпаратты беруге қатысты негізгі үш параметр: Tс – сигналды беру уақыты, Lc немесе Dc (динамикалық диапазон ) Pс – сигнал қуатымен аықталады, Fc– спектр ені.



Сигнал көлемі:



Канал сиымдылығы



Қажетті шарт:



Жеткілікті шарт:



Цифрлі деректерді цифрлі кодирлеу тікелей, сигнал деңгейін өзгерту жолымен атқарылады. Мысалы, егер ЭЕМ цифрлі деректер 1 мен 0,2В коды үшін, 0 коды үшін 5В деңгей сигналымен берілсе, онда осы деректерді байланыс желісіне бергенде сигналдар деңгейі +12В мен -12В – ге лайықты түрленеді. Мұндай кодирлеу RS – 232 – C асинхронды тізбекті адаптерлер көмегімен үлкен емес (ондаған және жүз метрлер) қашықтықта бір компьютерден екіншісіне цифрлі деректерді беру кезінде жүзеге асырылады.

20. 
    Ақпараттық каналға түсініктеме беріңіз. Каналдың  өткізу қабілетінің анықтамасы мен формуласын жазыңыз. Канал сыйымдылығының қажетті және жеткілікті шарттарын түсіндіріңіз. 
    

21. 
    Хаффман ағашы мен Хаффман кодын түсіндіріңіз. Мысал келтіріңіз. Сығу коэффициентін есептеу жолын көрсетіңіз.
    

Деректерді тиімді кодтаудың бірінші алгоритмдерінің бірі 1952 жылы Д. Хаффмен ұсынылды. Алгоритм идеясы келесідей: хабардағы символдардың ықтималдығын білу, биттердің бүтін санынан тұратын айнымалы ұзындық кодтарының кодтарын жасау тәртібін сипаттауға болады. Таңбалар әлдеқайда қысқа кодтар тағайындалады. Huffman кодтары префикс сипатына ие (яғни код сөзі басқа кодтың префиксі емес), ол бірегейлендіруге мүмкіндік береді.

Кірісіндегі классикалық Хафман алгоритмі хабардағы таңбалардың пайда болу жиілігінің кестесін алады. Сонымен қатар, осы кестенің негізінде Хафмен кодтау ағашының (H-tree) құрылысы жүргізілді.

1. Кіріс алфавитіндегі таңбалар бос түйіндердің тізімін құрайды. Әр парақтың салмағы бар, ол ықтималдығы немесе қысылған хабарламада таңбаның көріну санына тең болуы мүмкін.

2. Ең кішігірім салмақтарға ие екі бос түйін түйіні таңдалады.

3. Ата-анасы олардың жалпы салмағына тең салмақпен жасалады.

4. Ата-ана бос түйіндер тізіміне қосылады және оның екі баласы осы тізімнен жойылады.

5. Ата-аналардан шыққан бір доға бит 1, екіншісі - 0-ге бөлінеді. Тамырдан шыққан бұтақтардың бит мәндері ұрпақтың салмағына тәуелді емес.

6. Екіншіден басталатын қадамдар бос түйіндер тізімінде бір бос түйін қалмайынша қайталанады. Бұл ағаштың түбірі деп саналады.

Мысалы, бізде келесі жиілік кестесі бар:

Символ	А	Б	В	Г	Д
Жиілігі	15	7	6	6	5

Бұл үдерісті ағаш құру ретінде көрсетуге болады, оның түбірі — соңғы қадамнан символдарды біріктіру кезінде алынған біріктірілген символдардың ықтималдығы бар символ, оның N0 ұрпақтары — алдыңғы қадамнан алынған символдар және т. б.

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

Осы мысал үшін ағаш құру

Бұл таңбалар кестесі үшін Хаффман кодтары келесідей болады.

Символ	А	Б	В	Г	Д
Код	0	100	101	110	111

Алынған кодтардың ешқайсысы екіншісінің префиксі болмағандықтан, оларды ағыннан оқылғаннан кейін бірегей түрде декодтауға болады. Сонымен қатар, A хабарламасының ең жиі сипаты аз биттермен кодталады, ал ең сирек D таңбасы ең үлкен болып табылады.

Сонымен қатар, кестеде келтірілген нышандардан тұратын хабарламаның жалпы ұзындығы 87 бит болады (орташа белгі 2,2308 бит). Бірыңғай кодтауды пайдаланған кезде жалпы хабардың ұзындығы 117 бит болады (әр таңбаға 3 бит). Белгіленген жиіліктермен таңбаларды дербес шығаратын көздің энтропиясы - бұл символға 2.1858 биттерді құрайды, яғни осы таңба үшін жасалған Huffman кодының қайталануы, символға және энтропияға арналған биттердің орташа саны арасындағы айырмашылық ретінде түсіндірілген, 0.05 биттерден аз таңба бойынша.

Классикалық Huffman алгоритмінде бірқатар маңызды кемшіліктер бар. Біріншіден, қысылған хабардың мазмұнын қалпына келтіру үшін декодер кодтаушы пайдаланатын жиілік кестесін білуі керек. Демек, қысылған хабарламаның ұзындығы деректерді алға жіберетін жиіліктер кестесінің ұзындығымен көбейтіледі, бұл хабарды қысу үшін бар күш-жігерін жоққа шығарады. Сонымен қатар, нақты кодтауды бастамас бұрын толық жиіліктің статистикасының қажеттілігі хабар арқылы екі өтуді талап етеді: бір хабар үлгісін (жиілік кестесі және H-tree) жасау, екіншісі нақты кодтау үшін. Екіншіден, кодтаудың қайталануы тек кодталған таңбалардың ықтималдығы 2-ші инверсия болып табылған жағдайда ғана жоғалады. Үшіншіден, энтропия 1-ден аспайтын дереккөз үшін (мысалы, екілік дереккөз үшін) Хафман кодын тікелей қолдану мағынасы жоқ.

Сығу коэффиценті:

15+7+6+6+5+11+13+24+39=126

126/8=15,75



Ақпаратты сығу – деректерді берудің маңызды аспектісі, бұл деректерді жедел түрде беруге мүмкіндік береді. Сығу мақсаты – берілген ақпаратты сақтау және беру үшін қажетті бит санын азайту, бұл ақпаратты үнемді және тиісмді түрде жазуға мүмкіндік береді.

Сығу әдістерін екі үлкен топқа бөлуге болады: қайтарылатын және қайтарылмайтын.

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

Қайтарылатын алгоритмдерді кез-келген типті деректерді сығу үшін қолдануға болады. Ақпаратты жоғалтпай сығылатын файлдар форматтары:

• GIF, TIF, PCX, PNG — графиктік деректер үшін;

• AVI — кезектесетін видео- және дыбыс деректері үшін;

• ZIP, ARJ, RAR, LZH, LH, CAB — деректердің кез-келген типі үшін

Егер сығу кезінде деректер жоғалмайтын болса, онда сығу әдісі қайтарылатын деп аталады

Қайтарылатын әдістердің негізгілері:

1. қаттау әдісі;

2. Хаффман алгоритмі;

3. RLE алгоритмі;

4. Лемпель—Зив алгоритмі.

22. 
    Хемминг кодының алгоритмін түсіндіріңіз.  Хэмминг шекараларын көрсетіңіз. Хэмминг кодына мысал келтіріңіз. 
    

Хэмминг коды - өткен ғасырдың 1940 жылдарында Ричард Хемминг әзірлеген бір қатені түзетуге және қос қателерді түзеуге мүмкіндік беретін блоктық код.

Басқаша айтқанда, бұл қандай да бір ақпараттық хабарламаны белгілі бір жолмен кодтауға және (мысалы, желі бойынша) жібергеннен кейін осы хабарламада қандай да бір қате пайда болғанын анықтауға (мысалы, кедергілерге байланысты) және мүмкіндігінше, осы хабарламаны қалпына келтіруге мүмкіндік беретін алгоритм.

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

Бірден айта кету керек, Хэмминг коды екі бөліктен тұрады. Бірінші бөлім белгілі бір орындарда бақылау биттерін (ерекше түрде есептелген) енгізе отырып, бастапқы хабарламаны кодтайды. Екінші бөлім кіріс хабарын алады және бақылау биттерін қайта есептейді (БІРІНШІ БӨЛІМ сияқты алгоритм бойынша). Егер барлық жаңадан есептелген бақылау биттері алынғандармен сәйкес келсе, онда хабарлама қатесіз алынды. Әйтпесе, қате туралы хабарлама шығады және мүмкін болса қате түзетіледі.

Егер кодталатын ақпараттық блоктың ұзындығы m - бит болса. Кодтау үшін пайдаланылатын басқару биттерінің саны k, одан кейін кодталған блок ұзындығы: n = m + k биттерге ие болады. Осы ұзындықтың әр блогы үшін, қателігі бар әр түрлі комбинациялары мүмкін.

Осылайша, берілген әрбір блок үшін блок болуы мүмкін n - блоктары бар бір қате және бір блок қатесіз. Сондықтан, бірден көп қате болмайтын әр түрлі кодталған блоктардың максималды саны болады: 2^m(n+1), где n = m+k



Егер m Ұзындығы ақпараттық деректер үшін бақылау биттерінің k санын таңдасаңыз, ұзындығы m+k әр түрлі тізбектердің максималды мүмкін болатын саны бір қатеден аспайтын әр түрлі кодталған ақпараттық блоктардың барынша көп немесе тең болады, онда бір реттік қатені түзетуге кепілдік беретін k бақылау биттерінің көмегімен ақпараттық деректерді кодтаудың осындай әдісі бар екенін дәл айтуға болады.

Демек, бір реттік қатені түзету үшін қажетті бақылау биттерінің ең аз саны теңдіктен анықталады: 2^m * (n+1)=2ⁿ

n = m + k екенін ескере отырып, біз: k=2^k – m – 1

Биттердің саны бүтін сан болуы керек болғандықтан, осы теңдеуді пайдалана отырып есептелген k ең жақын бүтін санға дейін дөңгелектелуі керек.

Мысалы, ұзындығы 7, 4 ақпарат туралы деректер үшін бір реттік қателерді түзетуді қамтамасыз ету үшін бақылау биттары қажет, ал 128 биттердің ұзақтығы үшін 8 бақылау биты қажет.

Қатені түзету үшін қажетті басқару биттерінің ең аз санын анықтау жеткіліксіз. Бұл бақылау биттерін пайдаланып, деректерді тексерудің алгоритмін жасау керек. Ричард Хемминг келесі алгоритмді ұсынды.

Кезектегі реттік сандар екеуі болып табылатын барлық биттер бақылау биті болып табылады. Яғни, егер биттің реттік нөмірі «n» белгісімен белгіленсе, онда басқару биттары үшін теңдік шын болуы керек: n = 2k, мұндағы k - кез келген оң бүтін сан.

Мысалы, ұзындығы 13 бит ұзындықты кодтау үшін, тексерулер келесідей болады: 1, 2, 4 және 8 биттерді құрайды, себебі 2⁰= 1, 2¹ = 2, 2²= 4, 2³ = 8

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

Қандай бақылау биттерін биттерді басқаратындығын анықтау үшін оның дәрежесін 2-дәрежеге қарай бөлшектеу қажет. Осылайша, тоғызыншы бит 1 және 8 биттермен бақыланады, себебі 9 = 2⁰ + 2³ = 1 + 8.

Тапсырма. Бұл сөзді Хэмминг кодымен кодтау.

1) 1001 0001 1101 1110 0000 000

ШЕШІМІ. M = 23 ұзындықтағы осы хабарламаны кодтау үшін k = 5 қосымша разряд қажет болады, яғни шығыста N = 28 ұзындықтағы хабарды аламыз (қосымша разрядтардың саны 2K ≥ n+1, n – алынған разрядтардың саны, k – қосымша разрядтардың саны).

Кодталған хабардың түрі болсын

b28 b27 b26 b25 b24 b23 b22 b21 b20 b19 b18 b17 b16 b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 B5 b4 b3 b2 b1,

b1, b2, b4, b8, b16 разрядтары бақылау, ал қалғандары Ақпараттық болады. Ақпараттық разрядтарға рет бойынша бастапқы санның разрядтарын орналастырамыз, яғни.

b3 =1, b5 = 0, b6 = 0, b7=1,

b9=0, b10 =0, b11=0, b12=1,

b13= 1, b14=1, b15=0, b17=1,

b18=1, b19=1, b20=1, b21=0,

b22=0, b23=0, b24=0, b25=0,

b26=0, b27=0, b28=0.

Енді бақылау разрядтарының мәнін табамыз.

Ыңғайлы болу үшін келесі жиындарды енгіземіз:

V1 = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27... - бірінші разряд 1-ге тең барлық сандар

V2 = 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27... - екінші разряд 1-ге тең барлық сандар

V3 = 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28... - үшінші разряд 1-ге тең барлық сандар

V4 = 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28... - төртінші разряд 1-ге тең барлық сандар,

V5 = 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 ... - бесінші разряд 1-ге тең барлық сандар.

Бұдан әрі + деп 2 Модуль бойынша қосуды түсінеміз.

Сонда b1 = b3+b5+b7+b9+b11+b13+b15+b17+b19+b21+b23+b25+b27 = 1 (барлық разрядтар бірі-V1 қоспағанда, қолданысқа)

B2 = B3+b6+b7+B10+b11+b14+ B15+ b18+ b19+ B22+ b23+ B26+ b27 = 1 (бірінші разрядтан басқа V2 барлық разрядтары)

B4 = B5+b6+b7 +b12+b13+ b14+ b15+ b20 +b21+b22+b23+B28 = 1) (бірінші разрядтан басқа V3 барлық разрядтары)

B8 = B9+B10+b11+B12+b13+b14+B15+b24+b25+B26+b27+B28 = 1), (бірінші разрядтан басқа V4 барлық разрядтары)

b16 = b17+B18+B19+B20+B21+B22+b23+b24+b25+B26+b27+B28 = 0 (бірінші разрядтан басқа V5 барлық разрядтары).

Осылайша, 1111 0011 0001 1100 1111 0000 0000 кодын алды.

1.N=32 ақпараттық комбинация Саны кезінде бір қатені түзететін кодта қанша ақпараттық таңба бар.

2.Жалпы санда түзету кодының артықтығын анықтау

N=256 кодтық комбинациялар.

3.100110 екілік санды ондық жүйеге аудару.

4.Дәлдік ережесі бойынша кодтарды ойластыру:

0101100011

111110001100

0010001010.

5. Хэммминг кодының макетін құру, Хаффман кодының 00101 кодтық комбинациясы үшін түзету разрядтарының мәнін анықтау.

6.Хэмминг кодын пайдалана отырып, 1111 1011 хабарламасында қатені табу

0010 1100 1101 1100 110.

7.Кодтық сөздерді дұрыс тексеру, егер олар Хэмминг кодын пайдаланып жасалған болса. Егер жоқ болса, бастапқы деректерді табу.

-010101100011

-111110001100

-000010001010

8.10011010 тізбегі берілген. Кодпен кодтау Хемминг.

9.H – 01000100, a – 00111101, b – 00111110, r – 01001000. (ескерту. Бастапқы хабарламаны 16 биттен екі блокқа бөлу)

10.Алдыңғы 6 тапсырмадан хабарлама 11-ші қатемен алынды

бит. Қатені табу.