Кодтау және кодтаудың жіктелуі

Кіріспе 3
I Кодтау теориясы
1.1 Кодтау және кодтаудың жіктелуі 4
1.2 Кодтаудың артықшылығы 4
1.3 Жалпы кодаларға сипаттама 5
II Тиімді кодтау. Тиімді кодтаудың әдістері мен прициптері
2.1 Тиімді кодалардың құрылуы 9
2.2 Тиімді кодтауды жобалау 10
2.3 Тиімді кодтаудың принциптері мен әдістері
2.4 Шеннон . Фано бойынша тиімді кодттау
2.5 Хаффман әдісі бойынша тиімді кодттау
Қорытынды 15
Пайдаланылған әдебиеттер 16

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

1. Дмитриев В.И. Учебное пособие по курсу «Теория информации и кодирования» –М.: 1977. [1]
2. Дэвис Д.,және басқалары.Вычислительные сети сетевые протоколы.-М.:Мир,1982. [2]
3. Гольдштейн Борис Соломонович. Протоколы сети доступа. — БХВ-Петербург. — 2005. [3]
4. Передача дискретных сообщений: Учебник для вузов/ В. П. Шувалов, Н. В. Захарченко, В. О. Шварцман и др. ; Под ред. В. П. Шувалова. — М.: Радио и связь, —1990—464 ISBN: 5-256-00852-8 [4]
5. Сухман С.М., Бернов А.В., Шевкопляс Б.В. Синхронизация в телекоммуникационных системах: Анализ инженерных решений. - М.: Эко-Тренз, - 2003, 272с. ISBN: 5-88405-046-1. [5]

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 15 бет
Таңдаулыға:

Мазмұны

Кіріспе
3
I
Кодтау теориясы
1.1
Кодтау және кодтаудың жіктелуі
4
1.2
Кодтаудың артықшылығы
4
1.3
Жалпы кодаларға сипаттама
5
II
Тиімді кодтау. Тиімді кодтаудың әдістері мен прициптері
2.1
Тиімді кодалардың құрылуы
9
2.2
Тиімді кодтауды жобалау
10
2.3
Тиімді кодтаудың принциптері мен әдістері
11
2.4
Шеннон - Фано бойынша тиімді кодттау
12
2.5
Хаффман әдісі бойынша тиімді кодттау
13
Қорытынды
15
Пайдаланылған әдебиеттер
16

Кіріспе

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

I Кодтау теориясы

1.1 Кодтау және кодтаудың жіктелуі

Кодтау теориясы -- компьютердің дамуына өз үлесін қосқан математиканың бір облысы болып табылады. Оның таралу облысы мәліметтерді нақты каналдар бойынша беру, ал оның пәні берілген ақпараттың нақтылығын қамтамасыз ету болып табылады. Кейбірде кодтау теориясын шифрлеумен шатастырады, бірақ ол дұрыс емес: криптография кері есепті шешеді, оның мақсаты- мәліметтерден ақпаратты алуды қиындату.
Кода (франц. code) -- үзілісті хабарды сигналға айналдырғанда қолданылатын белгілер жиынтығы. Қолданылатын орнына және көзделетін мақсатына байланысты кодалар бірнеше түрге бөлінеді.
Мақсатына қарай кодалар үш түрге бөлінеді:
oo бөгеуілге орнықты бірінші кода
oo қарапайым кода
oo түзетуші кода.
Кодалаушы белгілер жүйесіне қарай:
oo екілік,
oo үштік,
oo төрттік және одан да көп болады.
Хабардың бір бөлігіндегі белгілер санына байланысты:
oo бірдей,
oo бірдей емес
oo болып бөлінеді.
Хабардың бір бөлігін белгілейтін символдар саны онда I қолданылатын жүйенің негізіне байланысты болады. Мысалы, екілік жүйедегі символдар саны көп болып, ал ондық немесе одан да көп жүйедегі символдар саны аз болады.[1]

1.2 Кодтаудың артықшылығы

Кодтау теориясы мәліметтерді жоғалтпай алуды қамтамасыз етеді. Мәліметтерді кодтаудың қажеттілігімен алғашқы рет жүз елу жыл бұрын тап болды. Каналдар өте қымбат және сенімсіз болғандықтан телеграммаларды жіберудің өте тиімді жолдары қарастырылды.1845 жылы пайдалануға арнайы кодтау кітаптары шықты; олардың көмегімен телеграфистер қолмен мәліметтердегі ұзақ сөйлемдерді қысқа кодтармен алмастырды. Сол кездері мәліметтердің жіберілуінің дұрыстығын тексеру үшін жұптық бақылау әдісі қолданылды, бұл әдісті перфокарталардың дұрыстығын тексеру үшін компьютердің бірінші және екінші буындарында да қолданылды. Ол үшін ең соңғы мәліметтер колодасына арнайы дайындалған бақылау сомасы бар картаны салған. Егер енгізу құрылғысы сенімсіз болса (немесе колода тым ұзын болған жағдайда), онда қате тууы мүмкін. Оны жөндеу үшін картадағы сомамен сәйкес келмегенше процедураны қайталай беретін. Бұл сұлбаның ыңғайсыз болғанымен қатар, ол екі есе қателер жіберетін. Байланыс каналдарының дамуымен қатар бақылаудың өте тиімді механизмі керек болды.
Бұл мәселенің теориялық шешімін алғашқы болып ақпараттың статистикалық теориясынының негізін қалаушы Клод Шеннон ұсынды. Шеннон өз заманының жұлдызы болды,ол АҚШ-тың академиялық элитасынынң мүшесі болған. Ванневар Буштың аспиранты болып, ол 1940 жылы жасы 30 жетпеген оқымыстыларға берілетін Нобель атындағы сыйлыққа ие болды (Нобель премиясымен шатастырмаңыздар). Bell Labs жұмыс істеп жүріп Шеннон Мәліметтерді жіберудің математикалық теориясы (1948) атты жұмыс жазды, ол жұмыста Шеннон каналдың жіберу мүмкіндігі мәліметтердің энтропия бастауынан жоғары болса, онда мәліметтерді ешқандай ақаусыз жіберілетіндей етіп кодтап қоюға болатынын дәлелдеді.Бұл түйіндеме Шеннонның көптеген дәлелдеген теоремалардың біреуінде бар. Сонымен қатар, ол каналда шудың бар болуына қарамастан мәліметтің жіберілу мүмкіндігінің теориялы түрде дәлелдеп берді.Шеннонның Мичиган штатында өзінің туып өскен қаласында орнатылған ескерткішінде ойып жазылған формуланы C=W log ((P+N)N) Альберт Эйнштейннің E=mc2 формуласының мәнімен салыстырады.[2]
Шеннонның еңбектері ақпараттар теория облысындағы ары қарай зерттеулерінде өз ықпалын тигізді, бірақта оларда инженерлік практикалық қосымшасы бар болмады. Теориядан практикаға алмасу Ричарда Хэммингтің жұмысынан байланысты болды. Ол Шеннонның Bell Labs бойынша әріптесі болды және кодтар класын ашқандығы үшін әйгілі болды, оларды Хэмминг коды деп атады.
Өзінің жаңалығын Хемминг 40 жылдардың ортасында Bell Model V есептеуіш машинасының перфокарталармен жұмыс жасау қолайсыздығынан ашты деген аңыз бар. Оған операторлар жоқ болғанда, яғни демалыс күндерде машинамен жұмыс жасауға мүмкіндік берді және ол өзі енгізулермен жұмыс жасады.
Хемминг байланыс каналдарындағы, сонымен қатар компьютерлердегі ақпараттарды беру магистральдарында, ең бастысы жад пен процессор арасындағы қателерді түзете алатын кодты ұсынды. Хемминг коды Шеннон теоремасында көрсетілген мүмкіндіктерді практикалық түрде қалай іске асыруға болатындығын көрсетеді.[1]

1.3 Жалпы кодаларға сипаттама

Хемминг бірінші болып қателерді түзейтін кодтарды (Error-Correcting Code, ECC) ұсынғандығы анық екенін білеміз. Бұл кодтардың қазіргі заманғы модификациялары барлық ақпараттарды сақтау жүйелерінде және жад пен процессор арасындағы алмасулар үшін қолданатыны белгілі. Олардың бір нұсқасы Рид-Соломонның коды компакт-дискілерде қолдланылады. Хэмминг тәсілі бойынша жасалынған көптеген кодтар нұсқалары бар, олар кодтау алгоритмдері бойынша және тексеретін биттер саны бойынша айырмашылықтары бар. Мұндай кодтарға планетааралық станциялармен космостық байланыс жасау үшін ерекше көңіл беріле бастады, мысалы, Рид-Мюллердің кодтарын 7 ақпараттық битке 32 тексеруші бит немесе 6 ақпараттық битқа - 26 тексеруші биттар келетін болды.
ECC жаңа кодтардың бірі ретінде LDPC (Low-Density Parity-check Code) кодын айтуымызға болады. Негізінде олар отыз жыл бұрын танымал блған, бірақта қазіргі уақытта оларға ерекше көңіл бөлінуде. LDPC коды 100-пайыздық анықтылығы бомағанмен, ол қатенің мүмкіндігін керекті нәтижеге дейін жеткізуімізге мүмкіндік береді және сонымен қатар каналдың жіберу мүмкіндігі максимальді толық түрде қолданылады. Оларға турбокодтар (Turbo Code) өте жақын келеді, олар алыс космостағы объектілермен жұмыс жасағанда өте қолайлы.
Кодтау теориясының тарихына Владимир Александрович Котельниковтың аты нық жазылған. 1933 году Материалах по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи-да ол өзінің О пропускной способности `эфира' и `проволоки' атты жұмысын жариялады. Бұл теоремада жіберілген сигнал ақпараттың жоғалтуынсыз қайтадан қалпына келетін шарттарды анықтайды.
Бұл теореманы әркім әрқалай атайды, соның ішінде WKS теоремасы (аббревиатура WKS взята от Whittaker, Kotelnikov, Shannon). Кейбір бастауларда Nyquist-Shannon sampling theorem және Whittaker-Shannon sampling theorem деп те аталады, ал өзіміздің жоғарғы оқу орындарының оқулықтарында жай ғана Котельников теоремасы деп кездестіреміз. Шын мәнінде теореманың өзіндік тарихы бар. Оның бірінші бөлігін 1897 жылы француз математигі Эмиль Борель дәлелдеген. Ал 1915 жылы өзінің еңбегін Эдмунд Уиттекер қосты. 1920 жылы жапондық Кинносуки Огура Уиттекер зерттеулеріне өзінің жөндеулерін жариялады, ал 1928 жылы американдық Гарри Найквист цифрлардың принциптерін жасаған.
Тиімділігі жөнінен Шеннон кодынан кем емес екінші код - Хаффман коды болып саналады. Хаффман кодасы сигналдың статикалық құрылымын ескереді. Әріптердің пайда болуы p1, р2, ...рк араларында тең емес, сондықтан H log n.
Бірінші ретті кодалар . Бірінші ретті кодалар хабар көзінен берілетін ақпаратты байланыс арнасымен таратуға дайындап және хабар көзіндегі артық ақпараттан тазартып, ондағы сигналдың берілу жылдамдығын арттыруға арналған.
Морзе кодыБірінші ретті коданың тарихы алғашқы қарапайым телеграфтық кодадан басталады.
Бірінші телеграфтық кода деп XIX ғасырдың бірінші жартысында ондық сандарды белгілеуге қолданылған Морзе кодасын айтуға болады.
Морзе коды - шартты сигналдар жүйесі. Морзе әліппесі америкалық өнертапқыш Сэмюэл Морзе (1791 - 1872) ойлап тапқан аппарат (Морзе аппараты) арқылы жүзеге асырылады. Морзе аппаратымен хабарларды кодпен беруге және қағаз таспаға кодпен жазып алуға болады.[1]Морзе кодында әрбір әріпке немесе таңбаға ток импульстерінің қысқа мерзімді (нүкте) және үш есе ұзағырақ (тире) сигналдың белгілі бір комбинациясы сәйкес келеді; олардың арасы нүкте ұзақтығына тең токсызинтервалмен бөлініп отырады. Сөздегі әріп және көп таңбалы цифрлар арасы әр комбинацияны аяқтайтын үш еселі токсыз интервалмен, ал текстегі сөздердің арасы бес еселі токсыз интервалмен бөлінеді. Морзе аппаратында әрбір әріп байланыс желісі мен батареяға қосылған контактыны (түйіспені) кілттің көмегімен қосу арқылы беріледі.

Кесте 1.1 - Морзе әліппесі
Орыс әріптері
Латын әріптері
Морзе коды
Шырқауы (орыс тілінде)
A
A
· −
ай-даа, ай-ваа
Б
B
− · · ·
баа-ки-те-кут, беей-ба-ра-бан
В
W
· − −
ви-даа-лаа, вол-чаа-таа
Г
G
− − ·
гаа-раа-ж, гаа-гаа-рин
Д
D
− · ·
доо-ми-ки
Е (также и Ё)
E
·
есть
Ж
V
· · · −
же-ле-зис-тоо, жи-ви-те-таак, я-бук-ва-жее, же-ле-ки-таа
З
Z
− − · ·
заа-каа-ти-ки, заа-моо-чи-ки, заа-раа-зи-ки
И
I
· ·
и-ди
Й
J
· − − −
йас-наа-паа-раа, йош-каа-роо-лаа, и-краат-коо-ее
К
K
− · −
каак-же-таак, каак-де-лаа, каа-тень-каа
Л
L
· − · ·
лу-наа-ти-ки
М
M
− −
маа-маа, моор-зее

Морзе кодасының кейінгі жетілдірілген түрінде нүктелер мен сызықшалардан тұратын символдар құрамы қолданылды. Жиі кездесетін әріптерге қысқа, аз символдар, ал сирек кездестін әріптерге ұзын, көп символдар беріліп, жалпы сигнал өткізу жылдамдығын арттырды.
Морзе кодасының қарапайымдылығы, жадта оңай сақталуы оның жетістігі болып табылады. Морзе кодасының кемшілігі - әріптердегі символдар санының бірдей болмауы, кодалап және кодадан шығару үшін қосымша, күрделірек құрылғыны талап етуі.
Құрамы бірдей болғандықтан, бірінші ретті кодалардың ішінде Бодо кодасының құрылуы ыңғайлы және кодадан шығару оңай, Бодо барлық әріпті төрт топқа (жолга) бөліп, әр топқа (жолға) жеті әріптен орналастырып, әр әріпке бес разрядты символдан берген (алғашқы екі разряд жолды, кейінгі үш разряд қатарды көрсетеді).
Кейінгі халықаралық стандарттарда және есептеу машиналарында осы Бодо кодасының негізінде жеті және сегіз разрядты кодалар жасалған.
Байланыс арналарында қосымша элементтерді пайдалану арқылы берілетін ақпараттың дәлдігін жоғарылату үшін қолданылатын коданы богеуілге орнықты кодалар немесе түзетуші кодалар деп атайды.
Бөгеуілге орнықты (түзетуші) кодалар бірінші ретті кодаларға қосымша разрядтар косу арқылы жасалады. Қосымша разрядтар байланыс арналарындағы бөгеуілдердің пайда болу зандылығына байланысты қосылып, сол бөгеуілдердің әсерінен пайда болатын қателерді жою үшін пайдаланылады. Қосымша разрядтар кодаларды күрделендіреді. Дәлдікті жоғарылату дәрежесі түзетуші коданың күрделілігіне байланысты. Дәлдікті неғұрлым жоғары дөрежеге көтеру үшін түзетуші кода соғұрлым күрделі болу керек. Сөйтіп акпаратты тарату дәлдігін жоғарылату әдістерінің әсері байланыс арналарындағы қателердің жалпы саны мен олардың таратылу заңдылығына байланысты болады.
Кез келген екілік жүйедегі топталған кодаларды әр түрлі m жолдан тұратын n бағаналы матрицамен жазуға болады. Немесе оған керісінше кез келген п орынды кодалық қомбинациядан тұратын m жолдың жиынтығынан топталған кодаларды құрушы матрица деп қарауға болады.
Қазіргі іс жүзінде кездесетін байланыс жүйелерінде қабылданған сигнал, алдымен кодалық символдарға, содан кейін хабарға ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.