Теория на кодирането

Теорията на кодирането изучава свойствата на кодовете и как да се използват за различни цели – компресиране на данни, криптография, отстраняване на грешки и мрежово кодиране. Кодовете също така се изучват от редица научни дисциплини – теория на информацията, електроинженерство, лингвистика, математика и компютърна наука, като главната цел на всички тях е разработването на надеждни и ефективни начини за предаване на данни. Този процес обикновено се състои от премахването на ненужни или повтарящи се парчета информация, засичането и поправянето на грешки и оптимизирането на начините за предаване и приемане на данни.

Теорията на кодирането има 4 практически дисциплини:^[1]

Компресията на данни има за цел да намали размера на данните, но и да запази техния интегритет за да могат да се трансферират по-лесно и бързо.

Корекцията на грешки използва редундантно кодиране за да осигури целостта на съобщението и да намали влиянието на външни фактори.

Криптографията или криптографичното кодиране използва кодовете като средство за гарантиране на сигурност и неприкосновеност на чувствителни данни (например лична или финансова информация).

Линейното кодиране се занимава с предаването на бинарни данни, както и най-ефективните и надеждни начини за осъществяването на тази цел.

История на теория на кодирането

След като практически дава начало на дигиталната ера чрез дисертацията си върху булева алгебра през 1937, през 1948 година Клод Шанън публикува статията „Математическа теория на комуникациите“. Статията се занимава с проблема как най-добре да се кодира информацията, която се предава. Клод Шанън използва инструменти от теория на вероятностите, разработена от Норберт Винер.

Клод Шанън работи известно време с Ричард Хеминг, който прави множество пробиви в отстраняването на грешки.^[2] и през 1968 година печели награда Тюринг за работата си върху числени методи, автоматични системи за кодиране и кодове за откриване и коригиране на грешки. Ричард Хеминг е автор на концепции като Hamming codes, Hamming windows, Hamming numbers и Hamming distance.

В последвалите години, множеството разузнавателни мисии до планетите в слънчевата система извършени от пробите Mariner, Viking и Voyager продължават развиват кодовата теория, като скоростта на предаване на данни и интегритета им са основни приоритети.^[3]

Компресиране на данни

Компресирането на данни или кодиране на източника представлява създаването на код, който представя същата информация с по-малък обем, с цел по-удобно съхраняване. Кодовете са функции, които преобразуват низове от информация от една азбука в низове (обичайно по-кратки) от друга азбука. Източник, сорс (на Английски Source code), изходен или първичен код – е „суровата“ форма, в която се пазят данни, с които работят хора и компютри. Има два основни типа компресии: със загуба на информация и без загуба.

Компресия със загуба на информация

При някои типове данни загубата на конкретна информация е приемлива. Пример за едни от основните приложения на компресия със загуба са най-често използваните формати – mp3 и mp4 за звук, jpg за картина и xvid за видео. При тях се получава компромисен вариант за качество, за сметка на обем данни, от пет до петдесет пъти по-малък. Схемите за компресии със загуба основно се състоят в изследване на това кои данни са по-маловажни, спрямо човешкото възприятие.

Компресия без загуба на информация

Компресиране без загуба се постига, чрез алгоритми, които елиминират статистическото повторение в съобщението и следователно представят данните в по-сбит вид. Например ако имаме нужда да представим информация под формата на черен екран не запазваме няколко десетки хиляди повторения на „черен пиксел“, а ги представяме като „480 000 черни пиксела“ (при резолюция 800х600).

Теорема на Шанън

През 1948 Клод Шанън публикува „Математическа теория на комуникацията“, в която сред много други, излага теоремата за ентропия на източника, която гласи, че не е възможно да се постигне компресия с кодово съотношение (брой битове, които могат да се представят с един символ, наричано още съотношение на компресия), по-малко от ентропията на източника, без това да доведе до загуба на данни.

В теорията на информацията ентропия представлява „мерна единица“ за липса на информация. Например ако разгледаме стандартно зарче (състоящо се от шест страни, всяка от които съдържа число от едно до шест) всяко число има еднаква вероятност да се окаже отгоре. В този случай ентропията има максимална стойност. Също така ако използваме зарче с тежест (която подсигурява винаги едно и също число да бъде отгоре) ентропията има нулева стойност, защото знаем какво ще се случи всеки път, когато метнем зарчето.

След като знаем какво представлява ентропия, можем да обобщим, че теоремата на Шанън гласи, че кодовото съотношение е обратно пропорционално на сложността на данните.

Алгоритми за кодиране

Има различни видове алгоритми за кодиране, които целят оптимален резултат при работа с различни данни. Следващите са примери за различни принципи при кодирането:

Кодиране по дължина – Посоченият по-горе пример с черните пиксели представлява кодиране по дължина. То е най-ефективно при данни, с много повторения.

Речниково кодиране – Алгоритъм без загуба, най-често използван при кодиране на текст. Всяко съвпадение в текста се заменя с индекса на кореспондиращата дума, намираща се в предефинирана структура от данни (речник). Такива алгоритми са LZ77, LZ78.
Кодиране с частично съвпадение – Използва статистически техники за предсказване на следващия символ, спрямо предишните.
Ентропологично кодиране – Алгоритъм за компресия без загуба, в който всеки символ се замества с уникален код, като най-честите символи ползват най-късите кодове. Често използвани техники са Кодировка на Хъфман и аритметичното кодиране:
- Кодировка на Хъфман – Алгоритъм за ентропологично кодиране при който се използват кодове от таблица, специфично генерирана според оценената вероятност за появяване на всеки от символите от сорса.
- Аритметично кодиране – Разновидност на ентропологично кодиране, при която не се кодират символи по отделно, а се кодира цялата информация под формата на число между 0.0 до 1.0
Кодиране чрез сортиране по блокове – Алгоритъм за кодиране без загуба, при който символите не се променят, а се пренареждат на редици с много повторения на един и същи символ и след това се прилага алгоритъм за кодиране на принцип, подобен на кодирането по дължина.^[4]

Засичане и отстраняване на грешки

Засичането и коригирането на грешки се състои от техники, позволяващи надеждния трансфер на данни по ненадеждни канали. Тъй като почти всички физически канали за предаване на информация са уязвими към външни смущения, множество техники са разработени с цел откриване и дори отстраняване на грешките. Дисциплината е основана от Ричард Хеминг в средата на 20 век.

Основният способ, който се използва е добавянето на допълнителни данни, които получателят може да използва, за да провери дали съобщението е пристигнало в първоначалния си вид, като някои методи позволяват и отстраняването на възникналите грешки. Спецификите на кода, който се използва зависят от характеристиките на комуникационния канал и дали грешките възникват случайно в течение на дълъг период от време или в сравнително кратки интервали.

Подходи към отстраняването на грешки

Отстраняването на грешки има 2 главни имплементации:

Automatic Repeat Request (ARQ) – при тази методология получателят може да изисква повторно изпращане на дадени данни ако се открият грешки в тях.
Forward Error Correction (FEC) – тук изпращача включва самия код, нужен за коригиране на грешки към съобщението, като най-често резултата е близка апроксимация до оригиналните данни.

Също така съществуват множество подходи за самия процес на откриване и отстраняване на грешки:

Repetition codes – съобщението, което бива изпращано се повтаря определен брой пъти, за да се гарантира обективна интерпретация от получателя.
Parity bits – след всяка група битове се поставя бит който пази информация за това дали броят на 1-ците е четен или нечетен.
Checksum – чексумата представлява резултата от аритметична или логическа (или комбинация от двете) операция извършена върху части съобщението и прибавена след края му.
Cyclic redundancy checks – често използван при дигитални системи поради лесна имплементация и висока ефективност, този подход използва резултата от полиномиално делене върху данните.
Cryptographic hash function – поради уникалността на генерираните хеш-функции, този метод може да засече дори и най-малката промяна в интегритета на дадено съобщение. Допълнителни мерки за сигурност също могат да бъдат въведени.

Засичането и отстраняването на грешки намира огромно приложение в модерния свят, като различни имплементации се използват както и за справяне с драскотини върху DVD-та, така и за поддържане на сателитите в орбита около Земята, които са постоянно изложени на влиянието на открития космос.

Криптографско кодиране

Криптографията или криптографичното кодиране се занимава с изучаването и разработването на техники за безопасна и сигурна комуникация. Много важна част има изграждането на мрежови протоколи, които имат ролята да ограничават достъпа на трети лица^[5] до определена информация. Освен сигурността на информацията, криптографията се опитва да гарантира както конфиденциалността, така и цялостността на данните, които биват предавани. Криптографията също така може да се разглежда като начин за правене на дадено съобщение по-трудно за четене.^[6]

Криптографията в модерната си форма практически не е съществувала преди началото на дигиталната революция. Техники за шифроване са съществували от хиляди години, но едва през XX век с развитието на далекосъобщенията и най-вече през Втората Световна Война технологиите започват да навлизат в създаването и разбиването на шифри.

В днешни дни математическата теория и компютърната наука са неразделни части от криптографията и практическото ѝ приложение. Основен принцип на сигурността, който също важи и при криптографията е това, че не е необходимо създаването на идеалната защита. Достатъчно е просто усилията и ресурсите, които биха били нужни за разбиване на подобна система да надвишават потенциалната печалба или полза, съдържаща се в системата. Развитието и разпространението на компютрите във всичките им форми налага постоянна еволюция на криптографията и разработването на все по-трудни за пробиване решения за сигурност, чието осъществяване да е сравнително лесно и бързо.

Линейно кодиране (Line Coding)

Линейното кодиране се осъществява чрез модулация на електрически сигнал, като моделът на вълната (waveform pattern) кореспондира на двоично представяне на цифровите данни. Спецификите на използвания код зависят от свойствата на физическия канал за предаване на сигнала. Най-често срещаните видове кодове са еднополюсен, полярен, биполярен и код Манчестър.

Други приложения на теорията на кодирането

Лингвистика (Linguistics)

Лингвистиката може да се счита като клон на теорията на кодирането, тъй като езикът на най-основно ниво е вид код. Концепции, обекти и феномени от реалния свят се компресират и представят като поредица от символи.^[7] Това позволява изключително ефективна комуникация и улеснява боравенето с абстракции.

Теорията на кодирането също така позволява и изчисляването на сложността на дадено езиково семейство.^[8]

Групово тестване (Group testing)

Груповото тестване работи с големи групи елементи. Целта е да се открият малкият брой елементи, които се различават от другите като се извършат най-малко тестове. За това се използват редица алгоритми и способи от комбинаториката. Първи стъпки в полето прави Робърт Дорфман^[9]

Неврално кодиране (Neural coding)

Невралното кодиране изучава взаимоотношенията между това как мрежите от неврони реагират на редица стимули и как електрическата активност в мозъка кореспондира на тези стимули.^[10]. Начина, по който мозъкът кодира и интерпретира информация споделя много прилики с модерните подходи за кодиране на дигитални данни. Амплитудата, честотата, силата и времето между невронните импулси могат да носят информация за стимула, на който са продукт.^[11]

Друго приложение на кодовете, използвани в някои мобилни телефонни системи, е с кодово разделен множествен достъп (CDMA). На всеки телефон е присвоена последователност от код, която е приблизително свързана помежду си с кодовете на други телефони. При предаване, кодовата дума се използва за модулиране на бита от данни, представляващи гласово съобщение.

В приемника процес демодулация се извършва за възстановяване на данни. Свойствата на този клас кодове позволяват на много потребители (с различни кодове), да използват един и същ радио канал по едно и също време.

Източници

↑ James Irvine, David Harle. "Data Communications and Networks". 2002. p. 18. section „2.4.4 Types of Coding“. quote: „There are four types of coding“
↑ Carnes 2005, pp. 220 – 221.
↑ Brief history of Coding Theory
↑ Theory of Data Compression, архив на оригинала от 8 май 2016, https://web.archive.org/web/20160508054615/http://www.data-compression.com/theory.html#entropy, посетен на 26 април 2016
↑ Ronald L. (1990). „Cryptology“. In J. Van Leeuwen. Handbook of Theoretical Computer Science 1. Elsevier.
↑ Dr Richard Pinch, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge. Coding theory: the first 50 years
↑ Study of linguistics
↑ Syntactic Parameters and a Coding Theory Perspective on Entropy and Complexity of Language Families
↑ Robert Dorfman (1943) 'The Detection of Defective Members of Large Populations Архив на оригинала от 2016-05-12 в Wayback Machine.'
↑ Brown EN, Kass RE, Mitra PP (May 2004). „Multiple neural spike train data analysis: state-of-the-art and future challenges“. Nat. Neurosci. 7 (5): 456 – 61. doi:10.1038/nn1228. PMID 15114358
↑ Coding schemes in the brain

Тази страница частично или изцяло представлява превод на страницата Coding theory в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[1] James Irvine, David Harle. "Data Communications and Networks". 2002. p. 18. section „2.4.4 Types of Coding“. quote: „There are four types of coding“

[2] Carnes 2005, pp. 220 – 221.

[3] Brief history of Coding Theory

[4] Theory of Data Compression, архив на оригинала от 8 май 2016, https://web.archive.org/web/20160508054615/http://www.data-compression.com/theory.html#entropy, посетен на 26 април 2016

[5] Ronald L. (1990). „Cryptology“. In J. Van Leeuwen. Handbook of Theoretical Computer Science 1. Elsevier.

[6] Dr Richard Pinch, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge. Coding theory: the first 50 years

[7] Study of linguistics

[8] Syntactic Parameters and a Coding Theory Perspective on Entropy and Complexity of Language Families

[9] Robert Dorfman (1943) 'The Detection of Defective Members of Large Populations Архив на оригинала от 2016-05-12 в Wayback Machine.'

[10] Brown EN, Kass RE, Mitra PP (May 2004). „Multiple neural spike train data analysis: state-of-the-art and future challenges“. Nat. Neurosci. 7 (5): 456 – 61. doi:10.1038/nn1228. PMID 15114358

[11] Coding schemes in the brain

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]