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

От Уикипедия, свободната енциклопедия

теория на кодирането- науката за свойствата на кодовете и тяхната пригодност за постигане на целта.

Главна информация

Кодирането е процес на преобразуване на данни от форма, удобна за директна употреба, във форма, удобна за предаване, съхранение, автоматична обработка и запазване от неоторизиран достъп. Основните проблеми на теорията на кодирането включват проблемите на кодирането едно към едно и сложността на реализирането на комуникационен канал при дадени условия:86. В това отношение теорията на кодирането разглежда главно следните области:18:

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

Напред за корекция на грешки

Криптография

Криптография (от др. гръцки. κρυπτός - скрит и γράφω - Пиша), това е област на знания за методите за осигуряване на поверителност (невъзможността за четене на информация на външни лица), целостта на данните (невъзможността за незабележима промяна на информацията), удостоверяване (удостоверяване на авторство или други свойства на обект), както и невъзможността за отказ от авторство

04.04.2006 г. Леонид Черняк Категория:Технологии

"Отворени системи" Създаването на компютри би било невъзможно, ако едновременно с появата им не беше създадена и теорията за кодирането на сигнали.Теорията на кодирането е една от онези области на математиката, които значително повлияха на развитието на изчислителната техника.

"Отворени системи"

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

Теорията на кодирането е една от онези области на математиката, които значително са повлияли на развитието на компютрите. Обхватът му се простира до предаване на данни по реални (или шумни) канали, а предметът е да се гарантира коректността на предаваната информация. С други думи, той изучава как най-добре да опакова данните, така че след сигнализиране, полезна информация да може да бъде извлечена от данните надеждно и лесно. Понякога теорията на кодирането се бърка с криптирането, но това не е вярно: криптографията решава обратния проблем, нейната цел е да затрудни извличането на информация от данните.

Необходимостта от кодиране на данни е възникнала за първи път преди повече от сто и петдесет години, малко след изобретяването на телеграфа. Каналите бяха скъпи и ненадеждни, което направи задачата за минимизиране на разходите и повишаване на надеждността на предаването на телеграми спешна. Проблемът се изостри от полагането на трансатлантически кабели. От 1845 г. се използват специални кодови книги; с тяхна помощ телеграфистите ръчно „компресираха“ съобщения, заменяйки последователности от общи думи с по-кратки кодове. В същото време, за да се провери правилността на прехвърлянето, започна да се използва паритет, метод, който се използва и за проверка на правилността на въвеждане на перфокарти в компютри от първо и второ поколение. За да направите това, специално подготвена карта с контролна сума беше поставена в последната входна колода. Ако входното устройство не е много надеждно (или палубата е твърде голяма), може да възникне грешка. За да се коригира, процедурата за въвеждане се повтаря, докато изчислената контролна сума съвпадне със сумата, съхранена на картата. Тази схема не само е неудобна, но и пропуска двойни грешки. С развитието на комуникационните канали беше необходим по-ефективен механизъм за контрол.

Първото теоретично решение на проблема с предаването на данни по шумни канали беше предложено от Клод Шанън, основателят на теорията на статистическата информация. Шанън беше звезда на своето време, той беше един от американския академичен елит. Като аспирант във Vannevar Bush през 1940 г. той получава Нобелова награда (да не се бърка с Нобеловата награда!), присъждана на учени под 30-годишна възраст. Докато е в Bell Labs, Шанън написва „Математическа теория за предаване на съобщения“ (1948), където показва, че ако честотната лента на канала е по-голяма от ентропията на източника на съобщението, тогава съобщението може да бъде кодирано така, че да бъде предадено без неоправдано забавяне. Това заключение се съдържа в една от теоремите, доказани от Шанън, смисълът му се свежда до факта, че ако има канал с достатъчна честотна лента, съобщението може да бъде предадено с известно време закъснение. Освен това той показа теоретичната възможност за надеждно предаване при наличие на шум в канала. Формулата C = W log ((P+N)/N), издълбана върху скромен паметник на Шанън, поставен в родния му град в Мичиган, се сравнява по стойност с формулата на Алберт Айнщайн E = mc 2 .

Работата на Шанън даде началото на много допълнителни изследвания в областта на теорията на информацията, но те нямаха практическо инженерно приложение. Преходът от теория към практика стана възможен благодарение на усилията на Ричард Хеминг, колега на Шанън в Bell Labs, който спечели слава с откриването на клас кодове, наречени „кодове на Хеминг“. Има легенда, че неудобството от работата с перфокарти на релейната изчислителна машина Bell Model V в средата на 40-те години е довело до изобретяването на техните кодове на Хеминг. Получаваше време да работи на машината през уикендите, когато нямаше оператори, и той самият трябваше да се занимава с въвеждането. Както и да е, но Хеминг предложи кодове, способни да коригират грешки в комуникационните канали, включително линиите за предаване на данни в компютрите, предимно между процесора и паметта. Кодовете на Хеминг станаха доказателство за това как възможностите, посочени от теоремите на Шанън, могат да бъдат реализирани на практика.

Хеминг публикува статията си през 1950 г., въпреки че вътрешните доклади датират неговата теория за кодиране от 1947 г. Ето защо някои смятат, че Хеминг, а не Шанън, трябва да се счита за бащата на теорията за кодирането. В историята на технологиите обаче е безполезно да се търси първият.

Сигурно е само, че Хеминг е първият, който е предложил „кодове за коригиране на грешки“ (Error-Correcting Code, ECC). Съвременните модификации на тези кодове се използват във всички системи за съхранение на данни и за обмен между процесора и RAM. Един от техните варианти, кодовете на Рийд-Соломон, се използват в компактдискове, позволявайки записите да се възпроизвеждат без скърцане и шумове, които биха могли да причинят драскотини и прахови частици. Има много версии на кодове, базирани на Hamming, те се различават по алгоритмите за кодиране и броя на битовете за проверка. Такива кодове са придобили специално значение във връзка с развитието на дълбоките космически комуникации с междупланетни станции, например има кодове на Рийд-Мюлер, където има 32 контролни бита за седем информационни бита или 26 за шест.

Сред най-новите ECC кодове трябва да се споменат кодовете LDPC (Low-Density Parity-check Code). Всъщност те са известни от около тридесет години, но особен интерес към тях беше открит точно през последните години, когато започна да се развива телевизията с висока разделителна способност. LDPC кодовете не са 100% надеждни, но процентът на грешки може да се регулира до желаното ниво, като същевременно се използва максимално честотната лента на канала. „Турбо кодовете“ са близки до тях, те са ефективни при работа с обекти, разположени в дълбокия космос и с ограничена честотна лента на канала.

Името на Владимир Александрович Котелников е твърдо вписано в историята на теорията на кодирането. През 1933 г. в „Материали по радиокомуникации за Първия всесъюзен конгрес по техническа реконструкция на комуникациите“ той публикува работата „За честотната лента? Етер? и жици? Името на Котелников, като равностойно, е включено в името на една от най-важните теореми в теорията на кодирането. Тази теорема определя условията, при които предаваният сигнал може да бъде възстановен без загуба на информация.

Тази теорема е наричана по различен начин, включително "WKS теорема" (съкращението WKS е взето от Whittaker, Kotelnikov, Shannon). В някои източници се използват както теоремата за вземане на проби на Найкуист-Шанън, така и теоремата за вземане на проби на Уитакър-Шанън, а в местните университетски учебници най-често се среща просто „теоремата на Котелников“. Всъщност теоремата има по-дълга история. Първата му част е доказана през 1897 г. от френския математик Емил Борел. Едмънд Уитакър допринесе през 1915 г. През 1920 г. японецът Киносуки Огура публикува корекции на изследванията на Уитакър, а през 1928 г. американецът Хари Найквист усъвършенства принципите на цифровизацията и реконструкцията на аналогов сигнал.

Клод Шанън(1916 - 2001) от ученическите си години проявява еднакъв интерес към математиката и електротехниката. През 1932 г. постъпва в Мичиганския университет, през 1936 г. - в Масачузетския технологичен институт, който завършва през 1940 г., като получава две степени - магистърска степен по електроинженерство и докторска степен по математика. През 1941 г. Шанън се присъединява към Bell Laboratories. Тук той започва да развива идеи, които по-късно водят до теория на информацията. През 1948 г. Шанън публикува статията „Математическа теория на комуникацията“, където са формулирани основните идеи на учения, по-специално определянето на количеството информация чрез ентропия, а също така предлага единица информация, която определя избора на две еднакво вероятни опции, тоест това, което по-късно беше наречено малко. През 1957-1961 г. Шанън публикува трудове, които доказват теоремата за пропускателната способност за шумни комуникационни канали, която сега носи неговото име. През 1957 г. Шанън става професор в Масачузетския технологичен институт, откъдето се пенсионира 21 години по-късно. На "заслужена почивка" Шанън се отдаде изцяло на старата си страст към жонглирането. Той построи няколко машини за жонглиране и дори създаде обща теория за жонглирането.

Ричард Хаминг(1915 - 1998) започва образованието си в Чикагския университет, където получава бакалавърска степен през 1937 г. През 1939 г. получава магистърска степен от Университета на Небраска и докторска степен по математика от Университета на Илинойс. През 1945 г. Хеминг започва работа по проекта Манхатън, мащабно правителствено изследователско усилие за създаване на атомната бомба. През 1946 г. Хеминг се присъединява към Bell Telephone Laboratories, където работи с Клод Шанън. През 1976 г. Хеминг получава председател във Военноморското следдипломно училище в Монтерей, Калифорния.

Работата, която го прави известен, фундаментално изследване на кодовете за откриване и коригиране на грешки, е публикувана от Хеминг през 1950 г. През 1956 г. той участва в разработването на един от ранните мейнфрейми IBM 650. Неговата работа полага основите на език за програмиране, който по-късно еволюира в езици за програмиране на високо ниво. Като признание за приноса на Хеминг в областта на компютърните науки, IEEE учреди медал за изключителни заслуги за компютърни науки и теория на системите, кръстен на негово име.

Владимир Котелников(1908 - 2005) през 1926 г. постъпва в Електротехническия факултет на Московското висше техническо училище на името на Н. Е. Бауман (MVTU), но става възпитаник на Московския енергиен институт (MPEI), който се отделя от Московското висше техническо училище като независим институт. Докато учи в аспирантура (1931-1933), Котелников математически прецизно формулира и доказва „референтната теорема“, която по-късно е кръстена на него. След като завършва аспирантура през 1933 г., Котелников, оставайки преподавател в Московския институт за енергетика, отива да работи в Централния изследователски институт по съобщенията (ЦНИИС). През 1941 г. В. А. Котелников формулира ясна позиция относно изискванията, на които трябва да отговаря една математически недешифрируема система и е дадено доказателство за невъзможността тя да бъде дешифрирана. През 1944 г. Котелников заема длъжността професор, декан на радиотехническия факултет на MPEI, където работи до 1980 г. През 1953 г., на 45-годишна възраст, Котелников веднага е избран за редовен член на Академията на науките на СССР. От 1968 до 1990 г. В. А. Котелников е и професор, ръководител на катедра в Московския физико-технически институт.

Раждането на теорията за кодирането

04.04.2006 г. Леонид Черняк Категория:Технологии

"Отворени системи"

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

Раждането на теорията за кодирането

„Целта на този курс е да ви подготви за вашето техническо бъдеще.“

Хей Хабр. Помните ли страхотната статия „Ти и твоята работа“ (+219, 2442 отметки, 394k прочитания)?

И така, Хаминг (да, да, самопроверяващи се и самокоригиращи кодове на Хеминг) има цяла книга, написана въз основа на неговите лекции. Превеждаме го, защото човекът си казва мнението.

Тази книга не е само за ИТ, това е книга за начина на мислене на невероятно готини хора. „Това не е просто заряд на позитивно мислене; той описва условията, които увеличават шансовете за извършване на страхотна работа.“

Вече сме превели 28 (от 30) глави. И ние работим върху публикацията "на хартия".

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

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

За да опростите проблема с представянето на информацията, разгледайте проблема с прехвърлянето на информация от точка до точка. Този въпрос е свързан с въпроса за запазването на информация. Проблемите на предаването на информация във времето и пространството са идентични. Фигура 10.1 показва типичен модел за трансфер на информация.

Фигура 10.1

От лявата страна на Фигура 10.1 е източникът на информацията. Когато разглеждаме модела, природата на източника не е важна за нас. Това може да бъде набор от букви, числа, математически формули, музикални ноти, символи, с които можем да представим танцови движения - естеството на източника и значението на знаците, съхранени в него, не е част от модела на предаване. Ние разглеждаме само източника на информация, с такова ограничение се получава мощна, обща теория, която може да бъде разширена в много области. Това е абстракция от много приложения.

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

Енкодерът се състои от две части, първата част се нарича енкодер на източника, точното име зависи от типа на източника. Източниците на различни типове данни съответстват на различни типове енкодери.

Втората част от процеса на кодиране се нарича кодиране на канала и зависи от вида на канала за предаване на данни. По този начин втората част от процеса на кодиране се съгласува с типа на предавателния канал. По този начин, когато се използват стандартни интерфейси, данните от източника първо се кодират според изискванията на интерфейса, а след това според изискванията на използвания канал за предаване на данни.

Според модела, на Фигура 10.1 връзката за данни е подложена на "допълнителен случаен шум". Целият шум в системата се обединява в тази точка. Предполага се, че енкодерът получава всички символи без изкривяване, а декодерът изпълнява функцията си без грешки. Това е известна идеализация, но за много практически цели е близо до реалността.

Фазата на декодиране също се състои от два етапа: канал - стандарт, стандарт - приемник на данни. В края на прехвърлянето данните се прехвърлят към потребителя. Отново, ние не вземаме предвид как потребителят интерпретира тези данни.

Както беше отбелязано по-рано, система за предаване на данни, като телефонни съобщения, радио, телевизионни програми, представя данните като набор от числа в регистрите на компютъра. Отново предаването в пространството не се различава от предаването във времето или съхранението на информация. Ако имате информация, която ще ви е необходима след известно време, тя трябва да бъде кодирана и съхранена в източника за съхранение на данни. Ако е необходимо, информацията се декодира. Ако системата за кодиране и декодиране е една и съща, ние предаваме данните през канала за предаване непроменени.

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

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

Първото очевидно необходимо свойство на кода е способността за недвусмислено декодиране на съобщение при липса на шум, поне това изглежда желателно свойство, въпреки че в някои ситуации това изискване може да бъде пренебрегнато. Данните от предавателния канал се появяват на приемника като поток от 0s и 1s.

Ще наречем два съседни знака двойно разширение, три съседни знака тройно разширение и като цяло, ако изпратим N знака, получателят вижда добавките към основния код от N знака. Получателят, който не знае стойността на N, трябва да раздели потока на излъчвани блокове. Или, с други думи, приемникът трябва да може да разложи потока по уникален начин, за да реконструира оригиналното съобщение.

Помислете за азбука от малък брой знаци; обикновено азбуките са много по-големи. Езиковите азбуки започват от 16 до 36 знака, включително главни и малки букви, цифри, знаци, препинателни знаци. Например в ASCII таблица 128 = 2^7 знака.
Помислете за специален код, състоящ се от 4 знака s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Как приемникът трябва да интерпретира следния получен израз

как s1s1s4или как s2s4?

Не можете да отговорите недвусмислено на този въпрос, този код определено не е декодиран, следователно е незадоволителен. От друга страна кодът

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Декодира съобщението по уникален начин. Нека вземем произволен низ и помислим как приемникът ще го декодира. Трябва да изградите дърво за декодиране според формата на Фигура 10.II. Линия

1101000010011011100010100110 …

Може да се раздели на символни блокове

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

Съгласно следното правило за конструиране на дърво за декодиране:

Ако сте на върха на дървото, прочетете следващия знак. Когато стигнете до лист от дървото, преобразувате последователността в знак и се връщате обратно към началото.

Причината за съществуването на такова дърво е, че никой знак не е префикс на друг, така че винаги знаете кога да се върнете към върха на дървото за декодиране.

Необходимо е да се обърне внимание на следното. Първо, декодирането е строго поточен процес, при който всеки бит се изследва само веднъж. Второ, протоколите обикновено включват знаци, които маркират края на процеса на декодиране и са необходими за обозначаване на края на съобщението.

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

Фигура 10.II

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

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Да предположим, че имаме последователност 011111...111 . Единственият начин да декодирате текста на съобщението е да групирате битове от края до 3 в групата и да изберете групи с водещи нули преди единици, след което можете да декодирате. Такъв код може да се декодира по уникален начин, но не моментално! За да декодирате, трябва да изчакате до края на трансфера! На практика този подход изравнява скоростта на декодиране (теорема на Макмилан), следователно е необходимо да се търсят методи за моментално декодиране.

Помислете за два начина за кодиране на един и същ знак, Si:

s1 = 0; s2 = 10; s3 = 110; s4=1110, s5=1111,

Дървото на декодиране за този метод е показано на фигура 10.III.

Фигура 10.III

Втори начин

s1 = 00; s2 = 01; s3 = 100; s4=110, s5=111,

Дървото на декодиране на тази грижа е представено на фигура 10.IV.

Най-очевидният начин за измерване на качеството на кода е средната дължина за някакъв набор от съобщения. За да направите това, е необходимо да изчислите дължината на кода на всеки символ, умножена по съответната вероятност за поява pi. Това ще ви даде дължината на целия код. Формулата за средната дължина L код за азбука от q знака е както следва

Където pi е вероятността за поява на знак si, li е съответната дължина на кодирания знак. За ефективен код стойността на L трябва да бъде възможно най-малка. Ако P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 и p5 = 1/16, тогава за код #1 получаваме стойността на дължината на кода

И за код №2

Получените стойности показват предпочитанието за първия код.
Ако всички думи в азбуката имат еднаква вероятност за поява, тогава вторият код е по-предпочитан. Например, с pi = 1/5, дължина на кода #1

И дължина на кода #2

Този резултат показва предпочитанието за код 2. По този начин, когато се проектира "добър" код, трябва да се вземе предвид вероятността за поява на знаци.

Фигура 10.IV

Фигура 10.V

Да разгледаме неравенството на Крафт, което определя граничната стойност на кодовата дължина на знака li. Според база 2 неравенството се представя като

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

За да докажем неравенството на Крафт за всеки бърз уникален декодируем код, ние конструираме декодиращо дърво и прилагаме метода на математическата индукция. Ако дървото има един или два листа, както е показано на фигура 10.V, тогава няма съмнение, че неравенството е вярно. Освен това, ако дървото има повече от две листа, тогава ние разделяме дървото с дължина m на две поддървета. Съгласно принципа на индукцията приемаме, че неравенството е вярно за всеки клон с височина m -1 или по-малко. Съгласно принципа на индукцията, прилагане на неравенството към всеки клон. Нека обозначим дължините на кодовете на клонове K" и K"". Когато два клона на дървото се слеят, дължината на всеки се увеличава с 1, следователно дължината на кода се състои от сумите K'/2 и K' '/2,

Теоремата е доказана.

Разгледайте доказателството на теоремата на Макмилан. Нека приложим неравенството на Крафт към непоточно декодируеми кодове. Доказателството се основава на факта, че за всяко число K > 1 n-тата степен на числото със сигурност е по-голяма от линейна функция на n, където n е доста голямо число. Повишете неравенството на Крафт на n-та степен и представете израза като сума

Където Nk е броят знаци с дължина k, сумирането започва с минималната дължина на представянето на n-тия символ и завършва с максималната дължина на nl, където l е максималната дължина на кодирания знак. От уникалното изискване за декодиране следва, че. Сумата е представена като

Ако K > 1, тогава е необходимо да зададете n доста голямо, за да стане неравенството невярно. Следователно к<= 1; теорема Макмиллана доказана.

Нека разгледаме някои примери за прилагане на неравенството на Крафт. Може ли да има уникално декодируем код с дължини 1, 3, 3, 3? Да защото

Какво ще кажете за дължини 1, 2, 2, 3? Изчислете по формулата

Неравенството е нарушено! В този код има твърде много кратки знаци.

Кодовете с точка (кодове със запетая) са кодове, които се състоят от знаците 1, завършващи на знака 0, с изключение на последния знак, който се състои от всички единици. Един от специалните случаи е кодът

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5= 11111.

За този код получаваме израз за неравенството на Крафт

В този случай постигаме равенство. Лесно е да се види, че за точковите кодове неравенството на Крафт се изражда в равенство.

Когато изграждате кода, трябва да обърнете внимание на сумата на Kraft. Ако Kraft сумата започне да надвишава 1, това е сигнал за включване на символ с различна дължина, за да се намали средната дължина на кода.

Трябва да се отбележи, че неравенството на Крафт не казва, че този код е уникално декодируем, а че има код със символи с такава дължина, който е уникално декодируем. За да създадете уникален декодируем код, можете да зададете съответната дължина в битове li като двоично число. Например за дължини 2, 2, 3, 3, 4, 4, 4, 4 получаваме неравенството на Крафт

Следователно може да съществува такъв уникален декодируем поточен код.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

Искам да обърна внимание какво всъщност се случва, когато обменяме идеи. Например, в този момент искам да прехвърля идея от моята глава във вашата. Казвам няколко думи, чрез които вярвам, че ще можете да разберете (схванете) тази идея.

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

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

Следва продължение...

Който иска да помогне с превода, оформлението и издаването на книгата - пишете на лични или имейл [имейл защитен]

Между другото, стартирахме и превода на друга готина книга -

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

Освен това приемаме, че източникът на информация е дискретен, като дава последователност от елементарни съобщения (i,), всяко от които е избрано от дискретен ансамбъл (азбука) a, a 2 ,...,d A; Да сее обемът на азбуката на източника на информация.

Всяко елементарно съобщение съдържа определена информация като набор от информация (в разглеждания пример) за състоянието на разглеждания източник на информация. За да се определи количествено мярката на тази информация, нейното семантично съдържание, както и степента на важност на тази информация за нейния получател, не е важно. Имайте предвид, че преди да получи съобщение, получателят винаги е несигурен кое съобщение съм аз. от всички възможни ще му бъде дадено. Тази несигурност се оценява, като се използва предварителната вероятност P(i,) за предаване на съобщението i,. Ние заключаваме, че обективна количествена мярка за информация, съдържаща се в елементарно съобщение от дискретен източник, се определя от вероятността за избор на дадено съобщение и определя cc като функция на тази вероятност. Същата функция характеризира степента на несигурност, която получателят на информация има по отношение на състоянието на дискретния източник. Може да се заключи, че степента на несигурност относно очакваната информация определя изискванията към каналите за предаване на информация.

Като цяло вероятността P(a,)изборът на източника на някакво елементарно съобщение i, (по-нататък ще го наричаме символ) зависи от избраните по-рано символи, т.е. е условна вероятност и няма да съвпадне с априорната вероятност за такъв избор.

Тим, че ^ P(a:) = 1, тъй като всички i образуват пълна група от събития

gyi), а изборът на тези символи се извършва с помощта на някаква функционална зависимост J(a,)= P(a,) = 1, ако изборът на символ от източника е предварително определен, J(a,)= a „ a P(a t,a)- вероятността за такъв избор, тогава количеството информация, съдържащо се в двойка символи, е равно на сумата от количеството информация, съдържащо се във всеки от символите i и i. Това свойство на количествена мярка за информация се нарича адитивност .

Ние вярваме в това P(a,)е условната вероятност за избор на символа i, след всички символи пред него, и P(a,,i,) е условната вероятност за избор на символа i; след i и всички предходни, но като се има предвид това P (a 1, a 1) \u003d P (a) P(i,|i y), условието за адитивност може да бъде написано

Въвеждаме нотацията P(a) = P p P (ar) \u003d Qи пренапишете условие (5.1):

Ние вярваме в това Р, О* 0. Използвайки израз (5.2), определяме формата на функцията (стр (R).Чрез диференциране, умножение по R* 0 и обозначаване RO = R,записвам

Отбележете, че връзката (5.3) е изпълнена за всеки R f O u^^O. Това изискване обаче води до постоянството на дясната и лявата страна на (5.3): Pq>"(P)= Ar"(/?) - Да се -конст. Тогава стигаме до уравнението Pc> "(P) = ДА СЕи след интегрирането получаваме

Да вземем предвид, че ще пренапишем

Следователно, при изпълнение на две условия за свойствата на J(a,), се оказа, че формата на функционалната зависимост J(a,)върху вероятността за избор на символ a tдо постоянен коефициент ДА СЕуникално определени

Коефициент ДА СЕзасяга само мащаба и определя системата от единици за измерване на количеството информация. Тъй като ln[P] Е 0, тогава има смисъл да изберете To Os, така че мярка за количеството информация J(a)беше положителен.

След като прие К=-1, запиши

От това следва, че единицата количество информация е равна на информацията, че е настъпило събитие, чиято вероятност е равна на азТакава единица за количество информация се нарича натурална единица. По-често се приема, че ДА СЕ= -, тогава

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

където логаритъма може да бъде с произволна основа.

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

Количествената мярка на информацията, съдържаща се в елементарното съобщение a (, не дава представа за средното количество информация J(A), издаден от източника, когато е избрано едно елементарно съобщение a d

Средното количество информация характеризира източника на информация като цяло и е една от най-важните характеристики на комуникационните системи.

Нека дефинираме тази характеристика за дискретен източник на независими съобщения с азбуката ДА СЕ.Означаваме с НА)средното количество информация на знак и е математическото очакване на случайна променлива L - количеството информация, съдържащо се в произволно избран знак А

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

От израз (5.10) следва, че ако една от вероятностите P(a)е равно на единица (следователно всички останали са равни на нула), тогава ентропията на източника на информация ще бъде равна на нула - съобщението е напълно дефинирано.

Ентропията ще бъде максимална, ако априорните вероятности на всички възможни символи са равни ДА СЕ, т.е. R(a() = 1 /ДА СЕ,Тогава

Ако източникът независимо избира двоични символи с вероятности P, = P(a x)и P 2 \u003d 1 - P, тогава ентропията на знак ще бъде

На фиг. 16.1 показва зависимостта на ентропията на двоичен източник от априорната вероятност за избор от два двоични символа, тази фигура също показва, че ентропията е максимална при R, = R 2 = 0,5

1 o 1 dvd - и в двоични единици log 2 2 = 1-

Ориз. 5.1. Ентропийна зависимост при К = 2 за вероятността да изберете един от тях

Ентропия на източници с равновероятен избор на символи, но с различна големина на азбуките ДА СЕ,нараства логаритмично с растежа ДА СЕ.

Ако вероятността за избор на символи е различна, тогава ентропията на източника пада I(A)спрямо възможния максимум H(A) psh =дневник ДА СЕ.

Колкото по-голяма е корелацията между символите, толкова по-малко свобода за избор на следващи символи и толкова по-малко информация има новоизбраният символ. Това се дължи на факта, че неопределеността на условното разпределение не може да надвишава ентропията на тяхното безусловно разпределение. Означете ентропията на източника с памет и азбука ДА СЕпрез H(AA"),и ентропията на източника без памет, но на същата азбука - чрез НА)и докажете неравенството

Чрез въвеждане на нотацията P(aa")за условната вероятност за избор на символа a,(/ = 1, 2, ДА СЕ)ако приемем, че символът е избран преди това аджиж =1,2,ДА СЕ)и пропускайки трансформациите, пишем без доказателство

което доказва неравенството (5.13).

Равенството в (5.13) или (5.14) се постига, когато

Това означава, че условната вероятност за избор на символ е равна на безусловната вероятност за избора му, което е възможно само за източници без памет.

Интересното е, че ентропията на текста на руски е 1,5 двоични единици на знак. При това, със същата азбука К= 32 с условието за независими и равновероятни символи H(A) tp = 5 двоични единици на символ. По този начин наличието на вътрешни връзки намалява ентропията приблизително 3,3 пъти.

Важна характеристика на дискретния източник е неговият излишък p и:

Излишъкът на източника на информация е безразмерна величина в рамките на . Естествено, при липса на излишък p u = 0.

За предаване на определено количество информация от източник, който няма корелации между символи, с еднаква вероятност за всички символи, минималният възможен брой предадени символи /7 min: /r 0 (/7 0 R (L max)) изисква се. За да се предаде същото количество информация от източник с ентропия (символите са взаимосвързани и неравновероятни), е необходим среден брой символи n = n„H(A) m JH(A).

Дискретният източник също се характеризира с производителност, която се определя от броя на символите за единица време v H:

Ако изпълнението I(A)след това дефинирайте в двоични единици и времето в секунди НА) -е броят на двоичните единици за секунда. За дискретни източници, които произвеждат стационарни символни последователности с достатъчно голяма дължина /?, се въвеждат следните понятия: типични и нетипични последователности от изходни знаци, в които всички последователности с дължина П.Всички типични последователности NlMl (A)източник при П-»oo имат приблизително еднаква вероятност за поява

Общата вероятност за поява на всички нетипични последователности клони към нула. В съответствие с равенството (5.11), като се приеме, че вероятността от типични последователности /N rm (A),ентропията на източника е logN TIin (,4) и след това

Помислете за количеството и скоростта на предаване на информация по дискретен канал с шум. Преди това разглеждахме информация, произведена от отделен източник под формата на поредица от знаци (i,).

Да предположим сега, че изходната информация е кодирана и представлява последователност от кодови символи (б, (/ = 1,2,..T -кодова база), е в съответствие с дискретен канал за предаване на информация, на изхода на който се появява последователност от символи

Приемаме, че кодирането е едно към едно - чрез последователността на знаците (б,)може еднозначно да се възстанови последователността (i,), т.е. чрез кодови символи е възможно да се възстанови напълно изходната информация.

Въпреки това, ако разгледаме екраниращите знаци |?. j и входни символи (/>,), тогава, поради наличието на смущения в канала за предаване на информация, възстановяването е невъзможно. Ентропия на изходната последователност //(/?)

може да бъде по-голяма от ентропията на входната последователност H(B), но количеството информация за получателя не се увеличи.

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

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

символ bjсъс същия номер (/= й).Тогава за идеален канал без шум пишем:

По символ bj-на изхода на канала поради неравенства (5.21)

несигурността е неизбежна. Можем да приемем, че информацията в символа b iне се предава напълно и част от него се губи в канала поради смущения. Въз основа на концепцията за количествена мярка за информация ще приемем, че числовият израз на несигурността, която възниква на изхода на канала след получаване на символа ft ; :

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

Фиксиране ft. и осреднявайки (5.22) за всички възможни символи, получаваме сумата

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

При осредняване на сумата (5.23) за всички ft, получаваме стойността Z?), която означаваме с n(в/в-Той определя количеството информация, загубена при предаване на един знак по канал без памет:

Където P^bjbjj-съвместна вероятност за събитие, което при предаване

символ b.ще вземе символа b T .

H [w/зависи от характеристиките на източника на информация

вход на канала INи върху вероятностните характеристики на комуникационния канал. Според Шанън в теорията на статистическата комуникация n(в/все нарича ненадеждност на канала.

Условна ентропия HB/B, ентропия на дискретен източник

на входа на канала H(W)и ентропия И ^B) на изхода си не може да бъде

отрицателен. В канал без смущения, ненадеждност на канала

n(v/v = 0. В съответствие с (5.20) отбелязваме, че H^v/v^

и равенство има само когато входът и изходът на канала са статистически независими:

Изходните символи не зависят от входните символи - случай на счупен канал или много силни смущения.

Както преди, за типичните последователности можем да пишем

да се каже, че при липса на смущения, неговата ненадеждност

Според информацията, предавана средно по канала J[ b/ на символ разбираме разликата между количеството информация на входа на канала J(B)и информация, загубена в /? канала).

Ако източникът на информация и каналът са без памет, тогава

Израз (5.27) определя ентропията на изходните символи на канала. Част от информацията на изхода на канала е полезна, а останалата част е невярна, тъй като се генерира от смущения в канала. Нека отбележим, че n[v/ 2?) изразява информация за смущението в канала, а разликата i(d)-I(d/d) - полезна информация, преминала през канала.

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

Като правило се взема предвид най-често срещаният тип смущения - адитивен шум. N(t);Сигналът на изхода на канала има формата:

За дискретни сигнали еквивалентният шум, произтичащ от (5.28), има дискретна структура. Шумът е дискретна произволна последователност, подобна на последователностите от входни и изходни сигнали. Нека обозначим символите на азбуката на адитивен шум в дискретен канал като C1 = 0, 1,2, T- 1). Вероятности за условен преход в такъв канал

защото И (^B/?) И (B) след това, следователно, информацията от изходната последователност на дискретния канал #(/) спрямо входа B(t)или обратното И (B) - H ^ in / in) (5).

С други думи, информацията, предавана по канала, не може да надвишава информацията на неговия вход.

Ако входът на канала получи средна стойност x kсимволи за една секунда, тогава е възможно да се определи средната скорост на предаване на информация по канал с шум:

Където Н(В) = V k J(B,B^ -производителност на източника на входа на канала; n (in / in) \u003d U до n (in, in) ~ненадеждност на канала за единица време; H (B) = V k H^B^- ефективността на източника, образуван от изхода на канала (издава част от полезна и част от невярна информация); H ^ in / B ^ \u003d U до 1 / (in / in)- количеството невярна информация,

създадено смущение в канала за единица време.

Концепциите за количеството и скоростта на предаване на информация по канал могат да бъдат приложени към различни участъци от комуникационния канал. Това може да е разделът "вход на енкодер - изход на декодер".

Обърнете внимание, че чрез разширяване на участъка от разглеждания канал е невъзможно да се превиши скоростта на която и да е от неговите съставни части. Всяка необратима трансформация води до загуба на информация. Необратимите трансформации включват не само въздействието на смущенията, но и детекцията, декодирането с кодове с излишък. Има начини да се намалят загубите при получаване. Това е "приемане като цяло".

Помислете за честотната лента на дискретен канал и теоремата за оптимално кодиране. Шанън въведе характеристика, която определя максималните възможни скорости на трансфер на информация по канал с известни свойства (шум) при редица ограничения върху ансамбъла от входни сигнали. Това е честотната лента на канал C. За дискретен канал

където максимумът се пази от възможни входни източници INдадено V kи силата на звука на азбуката на въведените знаци T.

Въз основа на дефиницията на пропускателната способност на дискретен канал, ние пишем

Обърнете внимание, че C = 0 с независим вход и изход (високо ниво на шум в канала) и съответно

при липса на смущения смущения на сигнала.

За двоичен симетричен канал без памет

Ориз. 5.2.

Графика на зависимостта на капацитета на двоичния канал от параметъра Рпоказано на фиг. 5.2. При Р= 1/2 честотна лента на канала C = 0, условна ентропия

//(/?//?) = 1. Практически интерес

графиката представлява 0

Основната теорема на Шанън за оптималното кодиране е свързана с концепцията за капацитет. Неговата формулировка за дискретен канал е следната: ако производителността на източника на съобщение НА)по-малко от честотната лента на канал C:

има метод за оптимално кодиране и декодиране, при който вероятността от грешка или ненадеждност на канала n[a!A j може да бъде произволно малък. Ако

няма такива начини.

В съответствие с теоремата на Шанън, крайната стойност СЪСе граничната стойност на скоростта на предаване на информация без грешки по канала. Но за шумен канал начините за намиране на оптималния код не са посочени. Теоремата обаче коренно промени възгледите за основните възможности на технологията за предаване на информация. Преди Шанън се смяташе, че в шумен канал е възможно да се получи произволно малка вероятност за грешка чрез намаляване на скоростта на трансфер на информация до нула. Това е, например, увеличаване на прецизността на комуникацията в резултат на повторение на знаци в канал без памет.

Известни са няколко строги доказателства на теоремата на Шанън. Теоремата беше доказана за дискретен канал без памет чрез произволно кодиране. В този случай се разглежда наборът от всички произволно избрани кодове за даден източник и даден канал и се потвърждава фактът на асимптотичното приближаване до нула на средната вероятност за погрешно декодиране за всички кодове с неограничено увеличаване на продължителността на последователността на съобщенията. По този начин се доказва само фактът на съществуването на код, който осигурява възможност за декодиране без грешки, но не се предлага недвусмислен метод на кодиране. В същото време, в хода на доказателството, става очевидно, че при запазване на равенството на ентропиите на ансамбъла от последователността на съобщенията и съответния едно към едно набор от кодови думи, използвани за предаване, ансамбълът INтрябва да се въведе допълнително излишък, за да се увеличи взаимната зависимост на последователността от кодови символи. Това може да стане само чрез разширяване на набора от кодови последователности, от които се избират кодови думи.

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