Теорија на информациите

Теоријата на информациите ги проучува квантификацијата, складирањето и комуникацијата на информациите. Првично било предложено од Клод Шенон во 1948 година да се пронајдат основните граници за обработка на сигнали и комуникациски операции, како што се збивање на податоци, во обележје со наслов „Математичка теорија на комуникацијата“. Неговото влијание е клучно за успехот на мисиите на Војаџер во длабок простор, изум на компактен диск, изводливост на мобилни телефони, развој на Интернет, проучување на лингвистиката и на перцепцијата на човекот, разбирање на црните дупки и сл. и бројни други полиња.

Областа е на пресекот на математиката, статистиката, компјутерските науки, физиката, невробиологијата, информатичкото инженерство и електротехниката. Теоријата исто така пронајде апликации во други области, вклучувајќи статистички заклучок, обработка на природен јазик, криптографија, невробиологија, човечка визија, еволуција и функција на молекуларни кодови (биоинформатика), избор на модели во статистиката, топлинска физика, квантна пресметка, лингвистика, откривање на плагијат, препознавање на модели и откривање на аномалија. Важни под-полиња на теоријата на информации вклучуваат кодирање на изворот, теорија на алгоритмичка сложеност, алгоритмичка теорија на информации, теоретска безбедност на информации, теорија на сивиот систем и мерки на информации.

Апликациите на фундаментални теми на теоријата на информации вклучуваат компресија на податоци без загуби (на пр ZIP-датотеки), компресирана загуба на податоци (на пр. MP3 и JPEG) и кодирање на канали (на пр. За DSL). Теоријата на информации се користи при пронаоѓање информации, собирање разузнавачки информации, коцкање, па дури и во музички состав.

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

Преглед

Теоријата на информации го проучува преносот, обработката, екстракцијата и користењето на информациите. Апстрактивно, информацијата може да се смета како резолуција на неизвесноста. Во случај на комуникација на информации преку бучен канал, овој апстрактен концепт е направен бетон во 1948 година од Клод Шенон во неговиот труд „Математичка теорија на комуникацијата“, во која „информацијата“ се смета за збир на можни пораки, каде целта е да се испратат овие пораки преку бучен канал, а потоа приемникот да ја реконструира пораката со мала веројатност за грешка, и покрај бучавата на каналот. Главниот резултат на Шенон, бучната теорема за шифрирање на каналот покажа дека, во границата на многубројни канали, стапката на информации што е асимптоматично постигната е еднаква на капацитетот на каналот, количина која зависи само од статистиката на каналот преку кој се наоѓаат пораките се испраќаат

Теоријата на информации е тесно поврзана со збирка чисти и применети дисциплини кои биле истражувани и сведени на инженерска практика под различни рубрики низ целиот свет во текот на изминатиот половина век или повеќе: адаптивни системи, антиципативни системи, вештачка интелигенција, сложени системи и сл . наука за сложеност, кибернетика, информатика, машинско учење, заедно со системски науки со многу описи. Теоријата на информации е широка и длабока математичка теорија, со подеднакво широки и длабоки апликации, меѓу кои е и клучното поле на теоријата за кодирање.

Теоријата за кодирање се занимава со пронаоѓање на експлицитни методи, наречени кодови, за зголемување на ефикасноста и намалување на стапката на грешка во комуникацијата со податоци преку бучни канали до близина на капацитетот на каналот. Овие кодови можат грубо да се поделат во техники за компресија на податоци (изворно кодирање) и исправка на грешки (канали за кодирање). Во последниот случај, беа потребни многу години да се пронајдат методите што докажано дека работата на Шенон биле можни.

Трета класа на кодови за теорија на информации се криптографски алгоритми (и шифри). Концептите, методите и резултатите од теоријата за кодирање и теоријата на информации се широко користени во криптографијата и криптанализата.

Историска позадина

Обележан настан што ја утврдил дисциплината на теоријата на информации и ја донел непосредно во светски рамки било објавувањето на класичниот труд на Клод Е. Шенон „Математичка теорија на комуникацијата“ во Техничкиот журнал во системот Бел во јули и октомври 1948 година.

Пред овој труд, во Bell Labs се развија ограничени теоретски идеи за информации, сите имплицитно претпоставуваа настани со еднаква веројатност. Хартијата на Хари Никвист од 1924 година, „ Одредени фактори кои влијаат на брзината на телеграфот“, содржи теоретски дел кој ја измери „интелигенцијата“ и „брзината на линијата“ со која може да се пренесе преку комуникациски систем, давајќи му на односот W = K log m (потсетувајќи на константа на Болцман ), каде W е брзината на пренесување на интелигенцијата, m е бројот на различни нивоа на напон што треба да се изберат на секој чекор чекор, а К е константа. Хартијата на Ралф Хартли во 1928 година, Пренесување на информации, го користи зборот информации како мерлива количина, како одраз на можноста на примачот да разликува една низа на симболи од која било друга, со што ги квантифицира информациите како H = log Sⁿ = n log S, каде S беше бројот на можни симболи и n бројот на симболи во менувачот. Оттаму, единицата на информација беше децимални децимални цифри, кои оттогаш понекогаш се нарекуваа картел во нејзина чест како единица или скала или мерка на информации. Ален Туринг во 1940 година користел слични идеи како дел од статистичката анализа на кршењето на шифрите на германската втора светска војна Енигма.

Голем дел од математиката зад теоријата на информации со настани со различни веројатности беа развиени за областа на термодинамиката од Лудвиг Болцман и Ј. Вилард Гибс . Врските помеѓу информативно-теоретската ентропија и термодинамичката ентропија, вклучувајќи ги и важните придонеси на Ролф Ландауер во 1960-тите, се истражени во Ентропија во термодинамиката и теоријата на информации.

Во револуционерната и привлечна хартија на Шенон, работата за која беа значително завршени во Bell Labs до крајот на 1944 година, Шенон за првпат го воведе квалитативниот и квантитативниот модел на комуникација како статистички процес во кој се темели теоријата на информации, отворајќи со тврдење дека

„Основниот проблем на комуникацијата е тој на репродукција во еден момент, точно или приближно, порака избрана во друга точка“.

Со тоа дојдоа идеите на

• ентропија на информации и вишок на изворот и нејзината важност преку теоремата за кодирање на изворот ;
• заемна информација и капацитетот на каналот на бучен канал, вклучително и ветување за совршена загуба без комуникација дадена од бучната теорема за кодирање на бучни канали ;
• практичниот резултат на законот Шенон-Хартли за капацитетот на каналот на гаузискиот канал ; како и
• бит - нов начин за гледање на најосновната единица на информации.

Количини на информации

Теоријата на информации се заснова на теорија на веројатност и статистика. Теоријата на информации честопати се однесува на мерките на информации за дистрибуциите поврзани со случајни променливи. Важни количини на информации се ентропија, мерка на информации во единечна случајна променлива и меѓусебна информација, мерка на заедничка информација помеѓу две случајни променливи. Поранешната количина е својство на веројатносна распределба на случајна променлива и дава ограничување на стапката според која податоците генерирани од независни примероци со дадената дистрибуција можат со сигурност да се компресираат. Вториот е својство на заедничка распределба на две случајни променливи и е максимална стапка на сигурна комуникација преку бучен канал во границата на долги блокови должини, кога статистиката на каналот се утврдува со заедничката дистрибуција.

Изборот на логаритамска основа во следниве формули ја одредува единицата на информативна ентропија што се користи. Заедничка информација е малку, заснована врз бинарниот логаритам . Другите единици вклучуваат nat, која се заснова на природниот логаритам и децимална цифра, која се заснова на заедничкиот логаритам .

Во она што следува, израз на формуларот p log p се смета од страна на конвенцијата да биде еднаков на нула кога p = 0 Ова е оправдано затоа што $\lim _{p\rightarrow 0+}p\log p=0$ за која било логаритамска основа.

Врз основа на веројатната функција на масата на секој изворен симбол што треба да се комуницира, ентропијата Шанон H, во единици на битови (по симбол), ја дава

$H=-\sum _{i}p_{i}\log _{2}(p_{i})$

каде што p_i е веројатноста за појава на i -th можна вредност на симболот на изворот. Оваа равенка ја дава ентропијата во единиците на „битови“ (по симбол) затоа што користи логаритам од основата 2, а оваа мерка за основно-2 на ентропија понекогаш се нарекува „шанон“ во нејзина чест. Ентропијата е исто така најчесто се пресметува со користење на природниот логаритам (база e, каде e е Ојлеров број ), која произведува мерење на ентропија во Nats на симболот, а понекогаш и поедноставува анализа, преку избегнување на потребата да се вклучат дополнителни константи во формули. Други основи се исто така можни, но поретко се користат. На пример, логаритам од основата 2⁸ = 256 ќе произведе мерење во бајти по симбол, а логаритамот од основата 10 ќе произведе мерење во децимални цифри (или картели) по симбол.