Пређи на садржај

Теорија кодирања

С Википедије, слободне енциклопедије
Дводимензионална визуализација Хаминговог растојања, критичне мере у теорији кодирања.

Теорија кодирања је студија која проучава својства кодова и њихову прикладност за специфичне примене. Кодови се користе за компресију података, криптографију, откривање и исправљање грешака, пренос података и складиштење података. Кодови се проучавају у различитим научним дисциплинама - попут теорије информација, електротехнике, математике, лингвистике и рачунарске науке - у сврху дизајнирања ефикасних и поузданих метода преноса података. То обично укључује уклањање сувишних вредности и исправљање или откривање грешака у пренешеним подацима.

Постоје четири врсте кодирања:[1]

  1. Компресија података (или, кодирање извора)
  2. Контрола грешке (или одирање канала)
  3. Криптографско кодирање
  4. Линијско кодирање

Компресија података покушава да уклони сувишност података из неког извора како би се што ефикасније преносили. На пример, Зип компримовање података чини датотеке података мањим у сврхе попут смањења интернетског промета. Компресија података и исправљање грешака могу се проучавати у комбинацији.

Исправљање грешака додаје екстра битове како би пренос података био робуснији на сметње које настају на каналу преноса. Обични корисник можда није свестан многих видова примене у којима се користи корекција грешака. Типични музички CD користи Рид-Соломонов код за кориговања импакта огреботина и прашине. У овој апликацији канал преноса је сам CD. Мобилни телефони такође користе технике кодирања за корекцију слабљења и буке преноса високих фреквенција. Модеми података, телефонски преноси и Мрежа дубоког свемира агенције НАСА, сви користе технике кодирања канала како би преносили битове, на пример турбо код и ЛДПЦ кодове.

Историја теорије кодирања

[уреди | уреди извор]

Године 1948. Клод Шанон је објавио „Математичку теорију комуникација”, чланак у два дела у јулском и октобарском броју техничког часописа Bell Sistem.[2][3][4][5] Овај рад се фокусира на проблем најбољег кодирања информације које пошиљалац жели да пренесе. У овом фундаменталном раду он је користио алате теорије вероватноће, које је развио Норберт Винер, а који су у то време били у поченим ступњевима примене у теорији комуникације. Шанон је развио информациону ентропију као меру неизвесности у поруци, чиме је есенцијално зачео поље теорије информација.[6]

Голајов бинарни код развијен је 1949. године.[7][8] То је код за исправљање грешака којим се могу исправити до три грешке у свакој 24-битној речи и детектовати четврта. Ричард Хеминг је освојио Тјурингову награду 1968. године за свој рад у Беловим лабораторијма на нумеричким методама, системима аутоматског кодирања и кодовима за детектовање и кориговање грешака. Он је изумео концепте познате као Хемингови кодови, Хемингови прозори, Хемингови бројеви и Хемингово растојање.

Насир Ахмед је 1972. године предложио дискретну косинусну трансформацију (ДЦТ), коју је развио са Т. Натарајаном и К. Р. Раом 1973. године.[9] ДЦТ је најчешће кориштен алгоритам компресије с губитком, и основа за мултимедијске формате као што су JPEG, MPEG и MP3.

Кодирање извора

[уреди | уреди извор]

Циљ кодирања извора је да се изворни подаци учинити мањим.[10][11]

Дефиниција

[уреди | уреди извор]

Подаци се могу видети као рандомне променљиве , где се јавља са вероватноћом .

Подаци се кодирају низовима (речима) преко абецеде .

Код је функција

(или ако празан низ није део алфабета).

је кодна реч асоцирана са .

Дужина кодне речи се пише као

.

Очекивана дужина кода је

Спајањем кодних речи се добија .

Кодна реч празног низа је сам празни низ:

Својства

[уреди | уреди извор]
  1. је несингуларно ако је ињективно.
  2. је јединствено декодиво ако је ињективно.
  3. је тренутно ако није префиx од (и супротно).

Ентропија извора је мера информација. У основи, изворни код покушава да смањи сувишност која постоји у извору, и да представи извор с мањим бројем битова који садрже више информација.

Компресија података која изричито покушава да минимизује просечну дужину порука према одређеном претпостављеном моделу вероватноће назива се ентропијско кодирање.

Различите технике које користе схеме кодирања извора покушавају да остваре границу ентропије извора. C(x) ≥ Х(x), где је Х(x) ентропија извора (бит-стопа), а C(x) је бит-стопа након компресије. Конкретно, ниједна шема кодирања извора не може надмашити ентропију извора.

Факс трансмисија користи једноставно кодирање дужине извођења. Кодирање извора уклања све сувишне податке према потребама предајника, смањујући опсег неопходан за пренос.

Неурално кодирање

[уреди | уреди извор]

Неурално кодирање је поље повезано са неуронауком које се бави начином на који су сензорне и друге информације у мозгу представљене мрежама неурона. Главни циљ проучавања неуронског кодирања је карактеризација односа између стимулуса и појединца или одговора неурона и односа између електричне активности неурона у целини.[12] Сматра се да неурони могу кодирати дигиталне и аналогне информације,[13] и да неурони следе принципе теорије информација и компримују информације.[14] Они детектују и коригују грешке[15] у сигналима који се шаљу кроз мозак и шири нервни систем.

Референце

[уреди | уреди извор]
  1. ^ Јамес Ирвине; Давид Харле (2002). „2.4.4 Тyпес оф Цодинг”. Дата Цоммуницатионс анд Нетwоркс. Јохн Wилеy & Сонс. стр. 18. ИСБН 9780471808725. „Тхере аре фоур тyпес оф цодинг 
  2. ^ Сханнон, Цлауде Елwоод (јул 1948). „А Матхематицал Тхеорy оф Цоммуницатион” (ПДФ). Белл Сyстем Тецхницал Јоурнал. 27 (3): 379—423. дои:10.1002/ј.1538-7305.1948.тб01338.x. хдл:11858/00-001М-0000-002Ц-4314-2. Архивирано из оригинала (ПДФ) 15. 7. 1998. г. „Тхе цхоице оф а логаритхмиц басе цорреспондс то тхе цхоице оф а унит фор меасуринг информатион. Иф тхе басе 2 ис усед тхе ресултинг унитс маy бе цаллед бинарy дигитс, ор море бриефлy битс, а wорд суггестед бy Ј. W. Тукеy. 
  3. ^ Сханнон, Цлауде Елwоод (октобар 1948). „А Матхематицал Тхеорy оф Цоммуницатион”. Белл Сyстем Тецхницал Јоурнал. 27 (4): 623—666. дои:10.1002/ј.1538-7305.1948.тб00917.x. хдл:11858/00-001М-0000-002Ц-4314-2. 
  4. ^ Роберт Б. Асх. Информатион Тхеорy. Неw Yорк: Интерсциенце, 1965. ISBN 0-470-03445-9. Неw Yорк: Довер 1990. ISBN 0-486-66521-6. стр. в.
  5. ^ Yеунг, Р. W. (2008). „Тхе Сциенце оф Информатион”. Информатион Тхеорy анд Нетwорк Цодинг. стр. 1—01. ИСБН 978-0-387-79233-0. дои:10.1007/978-0-387-79234-7_1. 
  6. ^ Сханнон, Цлауде Елwоод; Wеавер, Wаррен (1949). А Матхематицал Тхеорy оф Цоммуницатион (ПДФ). Университy оф Иллиноис Пресс. ИСБН 0-252-72548-4. Архивирано из оригинала (ПДФ) 15. 7. 1998. г. 
  7. ^ Голаy, Марцел Ј. Е. (1949). „Нотес он Дигитал Цодинг”. Проц. ИРЕ. 37: 657. 
  8. ^ Берлекамп, Е.Р. (1974), Кеy Паперс ин тхе Девелопмент оф Цодинг Тхеорy, I.Е.Е.Е. Пресс, стр. 4 
  9. ^ Насир Ахмед. „Хоw I Цаме Уп Wитх тхе Дисцрете Цосине Трансформ”. Дигитал Сигнал Процессинг, Вол. 1, Исс. 1, 1991. стр. 4—5. 
  10. ^ Махди, О.А.; Мохаммед, M.А.; Мохамед, А.Ј. (новембар 2012). „Имплементинг а Новел Аппроацх ан Цонверт Аудио Цомпрессион то Теxт Цодинг виа Хyбрид Тецхниqуе” (ПДФ). Интернатионал Јоурнал оф Цомпутер Сциенце Иссуес. 9 (6, Но. 3): 53—59. Архивирано из оригинала (ПДФ) 28. 12. 2018. г. Приступљено 6. 3. 2013. 
  11. ^ Wаде, Грахам (1994). Сигнал цодинг анд процессинг (2 изд.). Цамбридге Университy Пресс. стр. 34. ИСБН 978-0-521-42336-6. Приступљено 22. 12. 2011. „Тхе броад објецтиве оф соурце цодинг ис то еxплоит ор ремове 'инеффициент' редунданцy ин тхе ПЦМ соурце анд тхеребy ацхиеве а редуцтион ин тхе овералл соурце рате Р. 
  12. ^ Броwн ЕН, Касс РЕ, Митра ПП (мај 2004). „Мултипле неурал спике траин дата аналyсис: стате-оф-тхе-арт анд футуре цхалленгес”. Нат. Неуросци. 7 (5): 456—61. ПМИД 15114358. С2ЦИД 562815. дои:10.1038/нн1228. 
  13. ^ Тхорпе, С.Ј. (1990). „Спике арривал тимес: А хигхлy еффициент цодинг сцхеме фор неурал нетwоркс” (ПДФ). Ур.: Ецкмиллер, Р.; Хартманн, Г.; Хауске, Г. Параллел процессинг ин неурал сyстемс анд цомпутерс (ПДФ). Нортх-Холланд. стр. 91—94. ИСБН 978-0-444-88390-2. Приступљено 30. 6. 2013. 
  14. ^ Гедеон, Т.; Паркер, А.Е.; Димитров, А.Г. (пролеће 2002). „Информатион Дистортион анд Неурал Цодинг”. Цанадиан Апплиед Матхематицс Qуартерлy. 10 (1): 10. ЦитеСеерX 10.1.1.5.6365Слободан приступ. Архивирано из оригинала 17. 11. 2016. г. Приступљено 02. 09. 2019. 
  15. ^ Стибер, M. (јул 2005). „Спике тиминг прецисион анд неурал еррор цоррецтион: лоцал бехавиор”. Неурал Цомпутатион. 17 (7): 1577—1601. ПМИД 15901408. С2ЦИД 2064645. арXив:q-био/0501021Слободан приступ. дои:10.1162/0899766053723069. 

Литература

[уреди | уреди извор]

Спољашње везе

[уреди | уреди извор]