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

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

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

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

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

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

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

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

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

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

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

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

Главни чланак: Компресија података

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

Дефиниција

Подаци се могу видети као рандомне променљиве $X:\Omega \rightarrow {\mathcal {X}}$, где се $x\in {\mathcal {X}}$ јавља са вероватноћом $\mathbb {P} [X=x]$.

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

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

$C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ (или $\Sigma ^{+}$ ако празан низ није део алфабета).

$C(x)$ је кодна реч асоцирана са $x$.

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

$l(C(x))$.

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

$l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]$

Спајањем кодних речи се добија $C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})$.

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

$C(\epsilon )=\epsilon$

Својства

1. $C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ је несингуларно ако је ињективно.
2. $C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}$ је јединствено декодиво ако је ињективно.
3. $C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ је тренутно ако $C(x_{1})$ није префиx од $C(x_{2})$ (и супротно).

Принцип

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

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

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

Пример

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

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

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

Литература

• Елwyн Р. Берлекамп (2014), Алгебраиц Цодинг Тхеорy, Wорлд Сциентифиц Публисхинг (ревисед едитион), Берлекамп, Елwyн Р. (2015). Алгебраиц Цодинг Тхеорy. Wорлд Сциентифиц. ИСБН 978-9-81463-589-9. .
• МацКаy, Давид Ј. C.. Информатион Тхеорy, Инференце, анд Леарнинг Алгоритхмс Цамбридге: Цамбридге Университy Пресс, 2003. МацКаy, Давид Ј. C. (25. 9. 2003). Информатион Тхеорy, Инференце анд Леарнинг Алгоритхмс. Цамбридге Университy Пресс. ИСБН 0-521-64298-1. ЦС1 одржавање: Формат датума (веза)
• Вера Плесс (1982), Интродуцтион то тхе Тхеорy оф Еррор-Цоррецтинг Цодес, , Инц., Плесс, Вера (1982). Интродуцтион то тхе Тхеорy оф Еррор-цоррецтинг Цодес. Неw Yорк: Јохн Wилеy & Сонс. ИСБН 0-471-08684-3. .
• Рандy Yатес, А Цодинг Тхеорy Туториал.
• Сцхроедер, Манфред Р. (2014). „Белл Лабораториес”. Ацоустицс, Информатион, анд Цоммуницатион: Мемориал Волуме ин Хонор оф Манфред Р. Сцхроедер. Спрингер. стр. 388. ИСБН 9783319056609. 
• Граy, Роберт M. (2010). „А Хисторy оф Реалтиме Дигитал Спеецх он Пацкет Нетwоркс: Парт II оф Линеар Предицтиве Цодинг анд тхе Интернет Протоцол” (ПДФ). Фоунд. Трендс Сигнал Процесс. 3 (4): 203—303. ИССН 1932-8346. дои:10.1561/2000000036. 
• Гханбари, Мохаммед (2003). Стандард Цодецс: Имаге Цомпрессион то Адванцед Видео Цодинг. Институтион оф Енгинееринг анд Тецхнологy. стр. 1—2. ИСБН 9780852967102. 
• Wаде, Грахам (1994). Сигнал цодинг анд процессинг (2 изд.). Цамбридге Университy Пресс. стр. 34. ИСБН 978-0-521-42336-6. Приступљено 22. 12. 2011. „Тхе броад објецтиве оф соурце цодинг ис то еxплоит ор ремове 'инеффициент' редунданцy ин тхе ПЦМ соурце анд тхеребy ацхиеве а редуцтион ин тхе овералл соурце рате Р.” 
• Саломон, Давид (2008). А Цонцисе Интродуцтион то Дата Цомпрессион. Берлин: Спрингер. ИСБН 9781848000728. 
• С. Миттал; Ј. Веттер (2015), „А Сурвеy Оф Арцхитецтурал Аппроацхес фор Дата Цомпрессион ин Цацхе анд Маин Меморy Сyстемс”, ИЕЕЕ Трансацтионс он Параллел анд Дистрибутед Сyстемс, ИЕЕЕ, 27 (5): 1524—1536, С2ЦИД 11706516, дои:10.1109/ТПДС.2015.2435788 
• Танк, M.К. (2011). „Имплементатион оф Лемпел-ЗИВ алгоритхм фор лосслесс цомпрессион усинг ВХДЛ”. Тхинкqуест~2010. Тхинкqуест 2010: Процеедингс оф тхе Фирст Интернатионал Цонференце он Цонтоурс оф Цомпутинг Тецхнологy. Берлин: Спрингер. стр. 275—283. ИСБН 978-81-8489-988-7. дои:10.1007/978-81-8489-989-4_51. 

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

• Explanation of lossless signal compression method used by most codecs
• Interactive blind listening tests of audio codecs over the internet