Рицхард Хамминг: Поглавље 13. Теорија информација

Успели смо!

"Сврха овог курса је да вас припреми за вашу техничку будућност."

Здраво, Хабр. Запамтите сјајан чланак "Ти и твој рад" (+219, 2588 обележивача, 429 хиљада читања)?

Дакле, Хаминг (да, да, самонадгледање и самоисправљање Хамингови кодови) постоји целина књига, написан на основу његових предавања. Ми то преводимо, јер човек говори шта мисли.

Ово није књига само о ИТ-у, то је књига о стилу размишљања невероватно кул људи. „То није само подстицај позитивног размишљања; описује услове који повећавају шансе за обављање сјајног посла.”

Хвала Андреју Пахомову на преводу.

Теорију информација развио је Ц. Е. Сханнон касних 1940-их. Менаџмент Белл Лабс-а је инсистирао да он то назове "Теорија комуникације" јер... ово је много тачније име. Из очигледних разлога, назив „Теорија информација“ има много већи утицај у јавности, због чега га је Шенон одабрала, а то је име које познајемо до данас. Сам назив сугерише да се теорија бави информацијама, што је чини важном како се крећемо дубље у информационо доба. У овом поглављу ћу се дотакнути неколико главних закључака из ове теорије, пружићу не строге, већ прилично интуитивне доказе о неким појединачним одредбама ове теорије, како бисте разумели шта је заправо „Теорија информација“, где је можете применити. а где не.

Пре свега, шта су „информације“? Шенон изједначава информације са неизвесношћу. Одабрао је негативан логаритам вероватноће догађаја као квантитативну меру информација које добијате када се деси догађај са вероватноћом п. На пример, ако вам кажем да је време у Лос Анђелесу магловито, онда је п близу 1, што нам заиста не даје много информација. Али ако кажем да у јуну у Монтереју пада киша, у поруци ће бити несигурности и она ће садржати више информација. Поуздан догађај не садржи никакве информације, пошто је лог 1 = 0.

Погледајмо ово детаљније. Шенон је веровао да квантитативна мера информације треба да буде континуирана функција вероватноће догађаја п, а за независне догађаје треба да буде адитивна – количина информација добијена као резултат појаве два независна догађаја треба да буде једнака количина информација добијених као резултат настанка заједничког догађаја. На пример, исход бацања коцке и новчића се обично третирају као независни догађаји. Хајде да преведемо горе наведено на језик математике. Ако је И (п) количина информација садржана у догађају са вероватноћом п, онда за заједнички догађај који се састоји од два независна догађаја к са вероватноћом п1 и и са вероватноћом п2 добијамо

(к и и су независни догађаји)

Ово је функционална Кошијева једначина, тачна за све п1 и п2. Да бисте решили ову функционалну једначину, претпоставите да

п1 = п2 = п,

ово даје

Ако је п1 = п2 и п2 = п онда

итд. Проширујући овај процес користећи стандардну методу за експоненцијале, за све рационалне бројеве м/н важи следеће

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

У теорији информација, уобичајено је да се база логаритма узима као 2, тако да бинарни избор садржи тачно 1 бит информације. Дакле, информација се мери формулом

Хајде да застанемо и схватимо шта се горе догодило. Пре свега, нисмо дефинисали појам „информације“, већ смо једноставно дефинисали формулу за њену квантитативну меру.

Друго, ова мера је подложна несигурности, и иако је разумно погодна за машине — на пример, телефонске системе, радио, телевизију, компјутере, итд. — не одражава нормалне људске ставове према информацијама.

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

Дакле, Шенонова дефиниција информација је прикладна за машине у многим случајевима, али изгледа да не одговара људском разумевању те речи. Из тог разлога је „Теорија информација“ требало да се зове „Теорија комуникације“. Међутим, прекасно је да се мењају дефиниције (које су теорији дале почетну популарност, а које и даље терају људе да мисле да се ова теорија бави „информацијама“), тако да морамо да живимо са њима, али у исто време морате јасно разумети колико је Шенонова дефиниција информације далеко од њеног уобичајеног значења. Шенонове информације се баве нечим сасвим другим, наиме неизвесношћу.

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

Размотримо систем чија абецеда се састоји од симбола к са вероватноћама пи. У овом случају просечна количина информација у систему (његова очекивана вредност) је једнака:

Ово се зове ентропија система са дистрибуцијом вероватноће {пи}. Користимо термин "ентропија" јер се исти математички облик појављује у термодинамици и статистичкој механици. Због тога појам „ентропија“ око себе ствара одређену ауру важности, што на крају није оправдано. Исти математички облик записа не подразумева исто тумачење симбола!

Ентропија дистрибуције вероватноће игра главну улогу у теорији кодирања. Гибсова неједнакост за две различите расподеле вероватноће пи и ки је једна од важних последица ове теорије. Зато то морамо доказати

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

а једнакост се постиже само када је к = 1. Применимо неједнакост на сваки члан збира са леве стране:

Ако се абецеда комуникационог система састоји од к симбола, онда узимајући вероватноћу преноса сваког симбола ки = 1/к и замењујући к, добијамо из Гибсове неједнакости

Слика 13.И

То значи да ако је вероватноћа преноса свих к симбола иста и једнака - 1 / к, онда је максимална ентропија једнака лн к, иначе важи неједнакост.

У случају јединствено декодираног кода, имамо Крафтову неједнакост

Сада ако дефинишемо псеудо-вероватноће

где наравно = 1, што следи из Гибсове неједнакости,

и применити мало алгебре (запамтите да је К ≤ 1, тако да можемо да избацимо логаритамски члан, и можда касније појачамо неједнакост), добијамо

где је Л просечна дужина кода.

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

Сада размотрите главну теорему о ограничењима комуникационих система у којима се информације преносе као ток независних битова и присутан је шум. Подразумева се да је вероватноћа исправног преноса једног бита П > 1/2, а вероватноћа да ће вредност бита бити инвертована током преноса (догодиће се грешка) једнака К = 1 - П. Ради погодности, ми претпоставимо да су грешке независне и да је вероватноћа грешке иста за сваки послани бит – односно да постоји „бели шум“ у комуникационом каналу.

Начин на који имамо дугачак ток од н битова кодираних у једну поруку је н-димензионално проширење једнобитног кода. Касније ћемо одредити вредност н. Размотрите поруку која се састоји од н-битова као тачку у н-димензионалном простору. Пошто имамо н-димензионални простор – а ради једноставности претпоставићемо да свака порука има исту вероватноћу појављивања – постоји М могућих порука (М ће такође бити дефинисано касније), стога је вероватноћа било које послате поруке

(пошиљалац)
Прилог 13.ИИ

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

где је, као и раније, П вероватноћа да нема грешке у било ком послатом биту. Када се шаље н независних битова, капацитет канала је дат са

Ако смо близу капацитета канала, онда морамо послати скоро ову количину информација за сваки од симбола аи, и = 1, ..., М. С обзиром да је вероватноћа појављивања сваког симбола аи 1/М, добијамо

када пошаљемо било коју од М једнако вероватних порука аи, имамо

Када се пошаље н битова, очекујемо да ће се појавити нК грешака. У пракси, за поруку која се састоји од н-битова, имаћемо приближно нК грешака у примљеној поруци. За велико н, релативна варијација (варијација = ширина дистрибуције, )
дистрибуција броја грешака ће постајати све ужа како се н повећава.

Дакле, са стране предајника, узимам поруку аи да пошаљем и нацртам сферу око ње са радијусом

који је нешто већи за износ једнак е2 од очекиваног броја грешака К, (слика 13.ИИ). Ако је н довољно велико, онда постоји произвољно мала вероватноћа да се тачка поруке бј појави на страни пријемника која се протеже изван ове сфере. Хајде да скицирамо ситуацију како је ја видим са становишта предајника: имамо било које полупречнике од пренете поруке аи до примљене поруке бј са вероватноћом грешке једнаком (или скоро једнаком) нормалној дистрибуцији, достижући максимум оф нК. За било које дато е2, постоји н толико велико да је вероватноћа да ће резултујућа тачка бј бити изван моје сфере онолико мала колико желите.

Погледајмо сада исту ситуацију са ваше стране (слика 13.ИИИ). На страни пријемника налази се сфера С(р) истог радијуса р око примљене тачке бј у н-димензионалном простору, тако да ако је примљена порука бј унутар моје сфере, онда је порука аи коју сам послао унутар ваше сфера.

Како може доћи до грешке? До грешке може доћи у случајевима описаним у табели испод:

Слика 13.ИИИ

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

Имамо математичку једначину за вероватноћу грешке Пе ако је послата порука аи

Можемо избацити први чинилац у другом члану, узимајући га као 1. Тако добијамо неједнакост

Очигледно

дакле

поново применити последњи термин са десне стране

Узимајући н довољно велико, први члан се може узети колико год желите, рецимо мањи од неког броја д. Стога имамо

Погледајмо сада како можемо да конструишемо једноставан заменски код за кодирање М порука које се састоје од н битова. Немајући појма како тачно конструисати код (кодови за исправљање грешака још нису били измишљени), Шенон је одабрала насумично кодирање. Баците новчић за сваки од н битова у поруци и поновите поступак за М порука. Укупно треба направити нМ окретања новчића, тако да је могуће

речници кода са истом вероватноћом ½нМ. Наравно, случајни процес креирања шифрарника значи да постоји могућност дупликата, као и кодних тачака које ће бити близу једна другој и самим тим бити извор вероватних грешака. Мора се доказати да ако се то не деси са вероватноћом већом од било ког малог изабраног нивоа грешке, онда је дато н довољно велико.
Кључна ствар је да је Шенон усредсредио све могуће шифрарнике да би пронашао просечну грешку! Користићемо симбол Ав[.] да означимо просечну вредност у скупу свих могућих случајних шифрарника. Усредњавање преко константе д, наравно, даје константу, пошто је за усредњавање сваки члан исти као и сваки други члан у збиру,

који се може повећати (М–1 иде у М)

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

где је с=К+е2 <1/2 и нс мора бити цео број.

Последњи појам десно је највећи у овом збиру. Прво, проценимо његову вредност користећи Стирлингову формулу за факторијеле. Затим ћемо погледати опадајући фактор члана испред њега, приметити да се овај фактор повећава како се крећемо улево, и тако можемо: (1) ограничити вредност збира на збир геометријске прогресије са овај почетни коефицијент, (2) проширити геометријску прогресију са нс чланова на бесконачан број чланова, (3) израчунати збир бесконачне геометријске прогресије (стандардна алгебра, ништа значајно) и коначно добити граничну вредност (за довољно велику н):

Обратите пажњу на то како се ентропија Х(с) појавила у биномном идентитету. Имајте на уму да проширење Тејлоровог низа Х(с)=Х(К+е2) даје процену добијену узимајући у обзир само први извод и занемарујући све остале. Сада да саставимо коначни израз:

где

Све што треба да урадимо је да изаберемо е2 тако да је е3 < е1, и тада ће последњи члан бити произвољно мали, све док је н довољно велико. Сходно томе, просечна ПЕ грешка се може добити онолико мала колико се жели са капацитетом канала произвољно близу Ц.
Ако просек свих кодова има довољно малу грешку, онда бар један код мора бити одговарајући, дакле постоји бар један одговарајући систем кодирања. Ово је важан резултат који је Шенон добио – „Шенонова теорема за бучни канал“, мада треба напоменути да је то доказао за много општији случај него за једноставан бинарни симетрични канал који сам користио. За општи случај, математички прорачуни су много компликованији, али идеје нису толико различите, тако да врло често, користећи пример одређеног случаја, можете открити право значење теореме.

Хајде да критикујемо резултат. Више пута смо понављали: „За довољно велико н. Али колико је н? Веома, веома велико ако заиста желите да будете близу капацитета канала и да будете сигурни у исправан пренос података! Толико велика, у ствари, да ћете морати да чекате веома дуго да акумулирате поруку од довољно битова да бисте је касније кодирали. У овом случају, величина речника случајног кода ће бити једноставно огромна (на крају крајева, такав речник се не може представити у краћем облику од комплетне листе свих Мн битова, упркос чињеници да су н и М веома велики)!

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

Истовремено, горе доказана теорема још увек није бесмислена! То показује да ефикасни системи преноса морају да користе паметне шеме кодирања за веома дугачке низове битова. Пример су сателити који су летели изван спољашњих планета; Како се удаљавају од Земље и Сунца, принуђени су да исправљају све више грешака у блоку података: неки сателити користе соларне панеле, који дају око 5 В, други користе нуклеарне изворе енергије, који дају отприлике исту снагу. Мала снага напајања, мала величина антена предајника и ограничена величина пријемних антена на Земљи, огромна раздаљина коју сигнал мора да пређе - све ово захтева употребу кодова са високим нивоом корекције грешака за изградњу ефикасан систем комуникације.

Вратимо се на н-димензионални простор који смо користили у доказу изнад. У расправи смо показали да је скоро цела запремина сфере концентрисана у близини спољне површине – тако да је готово извесно да ће се послати сигнал налазити близу површине сфере изграђене око примљеног сигнала, чак и са релативном мали полупречник такве сфере. Стога није изненађујуће што се примљени сигнал, након исправљања произвољно великог броја грешака, нК, испоставља произвољно близак сигналу без грешака. Капацитет везе о којем смо раније говорили је кључ за разумевање овог феномена. Имајте на уму да се сличне сфере конструисане за Хемингове кодове за исправљање грешака не преклапају једна са другом. Велики број скоро ортогоналних димензија у н-димензионалном простору показује зашто можемо сместити М сфере у простор са малим преклапањем. Ако дозволимо мало, произвољно мало преклапање, које може довести до само малог броја грешака током декодирања, можемо добити густо постављање сфера у простору. Хаминг је гарантовао одређени ниво исправљања грешака, Шенон – ниску вероватноћу грешке, али истовремено одржавајући стварну пропусност произвољно близу капацитета комуникационог канала, што Хамингови кодови не могу.

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

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

Сада ћемо погледати пример ИК тестова где је дефиниција кружна колико год желите да буде и, као резултат, обмањујућа. Направљен је тест који би требало да мери интелигенцију. Затим се ревидира како би био што конзистентнији, а затим се објављује и, једноставном методом, калибрише тако да се измерена „интелигенција“ испостави да је нормално распоређена (на калибрационој кривој, наравно). Све дефиниције се морају поново проверити, не само када се први пут предложе, већ и много касније, када се користе у закључцима. У којој мери су дефиниционе границе прикладне за проблем који се решава? Колико често се дефиниције дате у једној поставци примењују у сасвим различитим окружењима? Ово се дешава прилично често! У хуманистичким наукама, са којима ћете се неизбежно сусрести у животу, то се дешава чешће.

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

Чувена Едингтонова прича говори о људима који су пецали у мору мрежом. Након проучавања величине рибе коју су уловили, утврдили су минималну величину рибе која се налази у мору! Њихов закључак је вођен инструментом који је коришћен, а не стварношћу.

Наставиће се ...

Ко жели да помогне око превода, прелома и објављивања књиге - пишите у личну поруку или мејл [емаил заштићен]

Иначе, покренули смо и превод још једне цоол књиге - „Машина снова: прича о компјутерској револуцији“)

Посебно тражимо они који ће помоћи у превођењу бонус поглавље, које је само на видео снимку. (трансфер за 10 минута, првих 20 је већ заузето)

Садржај књиге и преведена поглављаПредговор

1. Увод у уметност бављења науком и инжињерингом: Учити да учимо (28. март 1995.) Превод: Поглавље 1
2. „Основе дигиталне (дискретне) револуције“ (30. март 1995.) Поглавље 2. Основе дигиталне (дискретне) револуције
3. „Историја рачунара – хардвера“ (31. март 1995.) Поглавље 3. Историја рачунара – Хардвер
4. „Историја рачунара – софтвер“ (4. април 1995.) Поглавље 4. Историја рачунара – софтвер
5. „Историја рачунара – апликације“ (6. април 1995.) Поглавље 5: Историја рачунара – практичне примене
6. „Вештачка интелигенција – први део“ (7. април 1995.) Поглавље 6. Вештачка интелигенција – 1
7. „Вештачка интелигенција – ИИ део“ (11. април 1995.) Поглавље 7. Вештачка интелигенција - ИИ
8. „Вештачка интелигенција ИИИ“ (13. април 1995.) Поглавље 8. Вештачка интелигенција-ИИИ
9. „н-димензионални простор“ (14. април 1995.) Поглавље 9. Н-димензионални простор
10. „Теорија кодирања – Репрезентација информација, И део“ (18. април 1995.) Поглавље 10. Теорија кодирања – И
11. „Теорија кодирања – Репрезентација информација, ИИ део“ (20. април 1995.) Поглавље 11. Теорија кодирања - ИИ
12. „Кодови за исправљање грешака“ (21. април 1995.) Поглавље 12. Кодови за исправљање грешака
13. „Теорија информација“ (25.) Поглавље 13. Теорија информација
14. „Дигитални филтери, први део“ (27. април 1995.) Поглавље 14. Дигитални филтери - 1
15. „Дигитални филтери, ИИ део“ (28. април 1995.) Поглавље 15. Дигитални филтери - 2
16. „Дигитални филтери, део ИИИ“ (2. мај 1995.) Поглавље 16. Дигитални филтери - 3
17. „Дигитални филтери, ИВ део“ (4. мај 1995.) Поглавље 17. Дигитални филтери - ИВ
18. „Симулација, први део“ (5. мај 1995.) Поглавље 18. Моделарство – И
19. „Симулација, ИИ део“ (9. мај 1995.) Поглавље 19. Моделовање - ИИ
20. „Симулација, део ИИИ“ (11. мај 1995.) Поглавље 20. Моделовање - ИИИ
21. „Фибер Оптицс“ (12. мај 1995.) Поглавље 21. Оптика
22. „Цомпутер Аидед Инструцтион“ (16. мај 1995.) Поглавље 22: Инструкције уз помоћ рачунара (ЦАИ)
23. „Математика“ (18.) Поглавље 23. Математика
24. „Квантна механика“ (19. мај 1995.) Поглавље 24. Квантна механика
25. „Креативност“ (23. мај 1995). превод: Поглавље 25. Креативност
26. „Стручњаци“ (25.) Поглавље 26. Стручњаци
27. „Непоуздани подаци“ (26. мај 1995.) Поглавље 27. Непоуздани подаци
28. „Системски инжењеринг“ (30. мај 1995.) Поглавље 28. Системско инжењерство
29. „Добијаш оно што мериш“ (1. јун 1995.) Поглавље 29: Добијате оно што мерите
30. "Како знамо шта знамо" (Јун КСНУМКС, КСНУМКС) преведите у деловима од 10 минута
31. Хаминг, „Ти и твоје истраживање“ (6. јун 1995.). Превод: Ти и твој рад

Ко жели да помогне око превода, прелома и објављивања књиге - пишите у личну поруку или мејл [емаил заштићен]

Извор: ввв.хабр.цом