Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Изявление на кодиращия проблем, първата теорема на Шанън

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

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

Въвеждаме серия от определения.

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

Код - (1) правило, описващо съответствието на знаците или техните комбинации от основната азбука с символи или техните комбинации от вторичната азбука.

(2) набор от символи за вторична азбука, използван за представяне на символи или техните комбинации от основната азбука.

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

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

Coder - устройство, което осигурява операция на кодиране.

Декодер е декодиращо устройство.

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

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

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

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

Нека първичната азбука А се състои от N символа със средна информация за I ( A ) , а вторичната азбука B - M символи със средна информация за I ( B ) . Нека и оригиналното съобщение, представено в основната азбука, съдържа n знака, а кодираните съобщения - m знака. Ако първоначалното съобщение съдържа I- ва (А) информация и кодираната I перка (В), тогава условието за обратимост на кодирането, т.е. неизчерпването на информация при кодирането, очевидно, може да бъде записано, както следва:

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

или

Съотношението m / n очевидно характеризира средния брой символи на вторичната азбука, които трябва да използваме, за да кодираме един символ от основната азбука - ще го наречем дължината на код или дължината на кодова верига и ще означава K (A, B). следователно

Обикновено N > M и I (A)> I ( B ), откъдето K (A, B)> 1, т.е. един символ от основната азбука е представен от няколко знака на вторичната. Тъй като има много начини за изграждане на кодове с фиксирани азбуки А и В , възниква проблемът с избора (или изграждането) на най-добрия вариант - ще го наречем оптимален код. Рентабилността на код при предаване и съхраняване на информация е икономически фактор, тъй като по-ефективният код ви позволява да отделяте по-малко време за изпращане на съобщение, както и по-малко време и съответно по-малко заемане на комуникационната линия; по време на съхранението се използва по-малка повърхност (обем) на носителя. В същото време трябва да се разбере, че рентабилността на кода не е идентична с предимството във времето на цялата верига за кодиране и прехвърляне; Възможно е използването на ефективен код по време на предаване да се плаща, така че операциите по кодиране и декодиране да отнемат повече време и други ресурси (например пространство в паметта на техническо устройство, ако тези операции се извършват с негова помощ).

Както следва от (3.1), минималната възможна стойност на средната дължина на кода ще бъде:

Този израз трябва да се интерпретира като съотношение на оценената природа, което определя долната граница на дължината на кода, но от нея не е ясно до каква степен в реалните кодиращи схеми е възможно приближаване на K (A, B) до K min (A, B). Поради тази причина две теореми, доказани от Шанън, са от първостепенно значение за теорията на кодирането и теорията на комуникацията. Първият - сега ще го разгледаме - засяга ситуацията с кодирането при липса на намеса, която нарушава посланието. Втората теорема е свързана с реални комуникационни линии с интерференция и ще бъде обсъдена в гл. 5.

Първата теорема на Шанън, която се нарича основната кодираща теорема в отсъствието на интерференция, е формулирана както следва:





Вижте също:

Етапи на решаване на проблем с помощта на компютър

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

Пример 4.17

Ентропията на сложен експеримент, състоящ се от няколко независими, е равна на сумата на ентропията на отделните експерименти.

глосар

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru