Експоненціальний закон збiльшення числа повiдомленнь

Всяку iнформацiю ми передаємо вiд одного джерела до iншого за допомогою певної системи символiв - кодiв, що складається з обмеженого числа знакiв - алфавiту. Наприклад, всi слова i речення в росiйськiй мовi можна передати за допомогою 32 знакiв. Тут алфавiт мiстить L=32 символа. В двiйковiй системi числення алфавiт мiстить L=2 символiв (0 i 1), в десятковiй L=10 i т. д.

Доведемо тепер, що якщо код не мiстить обмежень, те послiдовнiсть з n символiв припускає можливiсть скласти

N=Ln (1.60)

рiзноманiтних повiдомлень. В цьому i заключаеться експоненциальний закон збiльшення числа повiдомлень з збiльшенням довжини повiдомлення n.

Покажемо справедливiсть виразу (1. 60) за допомогою методу математичної iндукцiї. Для цього достатньо довести два твердження: а) якщо вираз (1.60) вiрний для будь-якого n (n - цiле, додатне число), те вiн вiрний i для n+1; б) вираз (1. 60) справедливий для n=1. Очевидно, що якщо твердження (а) i (б) справедливi, те вираз (1.60) вiрний для будь-якого n.

Почнемо з твердження (б). Якщо n=1, тобто наше повiдомлення складається тiльки з одного символу, то в якостi цього символу ми можемо взяти будь-який з L, тобто число рiзноманiтних повiдомлень буде N=L. Це число i дасть формула (1. 60) при n=1.

Перейдемо до доведення твердження (а). Нехай ми маємо послiдовнiсть довжиною в n символiв. Тодi по припущенню кiлькiсть рiзноманiтних повiдомлень, що можна здiйснити за допомогою такої послiдовностi, рiвна Ln. Додамо до цiєї послiдовностi ще один символ. Тодi, підставляючи на це нове мiсце будь-який з L символiв, отримаємо з кожного старого повiдомлення L нових повiдомлень. Всього кiлькiсть нових повiдомлень буде рiвна

Nn+1 = Ln · L = Ln+1,

тобто ми довели, що якщо вираз (1.60) справедливий для n, то вiн справедливий i для n+1.

Формулу (1. 60) можна видозмiнити слiдуючим чином. Нехай час передачi кожного символа рiвно t сек (будемо вважати, що тривалiсть передачi всiх символiв однакова). Тодi тривалiсть передачi повiдомлень з n символiв буде рiвна

Т = nt сек. (1.61)

Виключаючи n з формул (1.61) i (1.60), отримаємо

N = Ln = LT/t = LbT, (1. 62)

де b=1/t(символ/сек) являє собою швидкiсть передачi символiв по каналу. Таким чином, можливе число рiзноманiтних повiдомлень тривалостi Т росте зi збiльшенням T по експоненцiальному закону, що в функцiї часу справедливо i тодi, коли тривалiсть передачi окремих символiв неоднакова (але T >> ti). При цьому вiн набуває вигляду

N(T)=AwT, (1. 63)

де А i w залежать вiд L i довжини символiв. Так, w визначається як найбiльший дiйсний корень рiвняння

(1. 64)

де t1, t2,..., tL- довжини символiв алфавiту.

Експоненціальнiй закон збiльшення числа повiдомлень справедливий i тодi, коли в кодi є детермiнiстськi або ймовiрноснi обмеження кiнцевої тривалостi, але коли ми маємо дiло з так званими ергодичними повiдомленнями, де довжина повiдомлення значно бiльша, нiж довжина обмежень (пiд кiнцевою довжиною обмежень ми розумiємо, що обмеження розповсюджується тiльки на кiнцеве число наступних символiв).

Проiлюструємо сказане прикладом. Нехай за допомогою двiйкового цифрового коду потрiбно передати ординати електрокардiограмми з точнiстю до 1%. Яку довжину (скiльки розрядiв) двiйкового коду потрiбно взяти для цiєї мети? Оскiльки задана точнiсть 1%, то кiлькiсть рiзноманiтних повiдомлень (рiзноманiтних числових значень електрокардiограмми) буде N=100; L=2. Отже, n визначається з формули 100=2n, або найближче бiльше цiле n=7. Отже, для цифровой передачi електрокардiограмми зi згаданою точнiстю достатньо скористатися семирозрядним двiйковим кодом.

1.3 КОДИ З ВИЯВЛЕННЯМ ТА ВИПРАВЛЕННЯМ ПОМИЛОК

1.3.1 Кодування інформації

Кодуванням називається процес встановлення певної вiдповiдностi мiж повiдомленнями i тiєю системою символiв, за допомогою яких цi повiдомлення передаються. Сама система символiв називається кодом.

Основнi цiлi кодування наступнi.

1. Надання повiдомленням максимально короткої (стислої) форми з метою збiльшення пропускної спроможностi каналу, зоокрема для кращого використання пам'ятi в математичних машинах.

2. Надання повiдомленням форми, зручної для подання їх за допомогою електричних або механiчних сигналiв.

3. Максимальне спрощення логiчних i обчислювальних операцiй над повiдомленнями. Наприклад, якщо кiлькiснi повiдомлення представленi десятковим кодом (десяткова система числення), то для виконання операцiї множення необхiдно було б реалiзувати фiзично в пам'ятi машини таблицю множення. Якщо ж цi повiдомлення кодувати двiйковим кодом (двiйкова система числення), то оскiльки всi символи коду - одиницi або нулi, то потреба в таблицi множення пропадає; множення на нуль дасть нуль, а множення на одиницю зводиться до повторення числа.

4. Максимальна помiхостійкiсть лiнiї зв'язку i приладiв передачi i обробки iнформацiї.

Звичайно, створити код, що задовольняв би всiм перерахованим умовам, практичнi неможливо. Тому в залежностi вiд головних вимог, що накладаються системою або частиною системи, вибирають код, що краще всього задовольняє якiйсь з цих умов. При цьому нерiдко для однiєї частини системи використовують одну систему кодування, а для iншої - iншу. Стикуючи їх за допомогою приладiв, що переводять один код в iнший.

Так, наприклад, для лiнiї передачi iнформацiї, де важлива максимальна швидкiсть передачi повiдомлень, тобто максимальне використання пропускної спроможностi каналу, код слiд вибирати по першiй умовi. В цьому випадку може виявитися найбiльш зручним метод кодування Фано. Однак такий код являє собою код змiнної довжини, внаслiдок чого вiн незручний для виконання логічних i обчислювальних операцiй. Тому для обчислювальних приладiв системи бажаний код, що задовольняє третiй умовi, i т. д.

Найбiльш часто ми зустрiчаємось з проблемою кодування, коли маємо дiло з кiлькiсними повiдомленнями. Всяка система числення в принципi є певним кодом. Наприклад, в десятковiй системi число 123 представляється в виглядi: 1·102+ 2·101+ 3·100, тобто в виглядi суми мiр десятки. При цьому кодом числа є коефiцiенти при цих мiрах, тобто в даному випадку 123. Алфавiт такого коду складається з 10 символiв 0, 1, 2, 3,..., 9, тобто L=10. Аналогiчно в двiйковiй системi числення, числа представляються в виглядi суми мiр двiйки. Наприклад, число 14 представляється в виглядi 1·23 + 1·22 + 1·21 + 0·20або 1110. Тут кодом є коефiцiенти при вiдповiдних мiрах двiйки, i, отже алфавiт коду мiстить два символи - 0 i 1, тобто L= 2.

Декодування - процес, зворотний кодуванню. Вiн полягає в переходi вiд системи символiв до повiдомлень на звичайнiй мовi. Отже, процес декодування використовує ту ж систему вiдповiдностi, але в зворотньому напрямку. В принципi, код - це мова даної iнформацiйної системи. Тому кодування i декодування - це перехiд з однiєї мови на iншу.

Якщо в якостi сигналу, що передає iнформацiю, використовується безперервний сигнал, та вiдповiднiсть мiж повiдомленням i сигналом звичайно представляється за допомогою масштабного множника

х(t) =me (t). (1.86)

Тут x(t) - деяка кiлькiсна величина (повiдомлення), e(t) - безперервний фiзичний сигнал (наприклад, електрична напруга), m -масштабний множник. Безперервнi сигнали використовуються головним чином для передачi кiлькiсної iнформацiї, наприклад математичних змiнних в обчислювальних машинах безперервної дiї.

Навпаки, при дискретних сигналах навiть при передачi кiлькiсної iнформацiї використовуються коди, i в принципi окремi сигнали передають символи кодiв. Оскiльки кiлькiсть рiзноманiтних символiв обмежена (алфавiт коду), то достатньо мати всього декiлька дискретнiх рiвнiв сигналу для передачi будь-якого повiдомлення. Останнє дозволяє iстотно збiльшити точнiсть i помiхостiйкiсть систем передачi i обробки iнформацiї, бо тiльки дуже сильнi перешкоди можуть викривити сигнал, що передаеться, настiльки, що на приймальному кiнцi даний рiвень сигналу, котрий представляє даний символ, може бути прийнятий за iнший рiвень сигналу котрий представляє iнший символ. Саме тому цифрова електронна математична машина, де iнформацiя представлена дискретним кодом (тому вона i називається цифровою), значно точнiша, нiж математична машина безперервної дiї (аналогова).

Вибiр того або iншого коду визначається головною метою, яку ми переслiдуємо при кодуваннi. Однак незалежно вiд цього будь-який код повинен задовольняти наступнiй основнiй умовi: даний код може служити мовою деякої iнформацiйної системи в тому i тiльки в тому випадку, якщо свобода вибору в кодi (його ентропiя) рiвна або бiльша свободи вибору в iнформацiї (в системi повiдомлень). Справдi, очевидно, необхiдна умова вибору коду полягає в тому, щоб число допустимих комбiнацiй коду Nkбуло бiльше або рiвне числу рiзноманiтних повiдомлень Nc, тобто

Nk ³ Nc. (1.87)

Виберемо код постiйної довжини, алфавiт якого складається з L символiв i число позицiй (довжина кодового слова) рiвно n. За допомогою такого коду можна утворити Lnрiзноманiтних комбiнацiй (за вiдсутностi в кодi обмежень)

Nk = Ln. (1.88)

Пiдставляючи (1.88) в нерiвнiсть (1.87), отримаємо

Ln ³ Nc

або

nlogL ³ logNc (1.89)

звiдки

n ³ log Nc/log L (1.90)

Умова (1.90) - це умова вибору мiнiмального коду постiйної довжини для даної системи повiдомлень. Тут n - найближче бiльше цiле число, причому якщо має мiсце знак >, то код буде надлишковим.

Так як всi Lnкомбiнацiї рiвноможливi, свобода вибору коду рiвна

Hk = logNk = n logL. (1.91)

З iншого боку, максимальна свобода вибору iнформацiї буде при рiвноможливих повiдомленнях, i в цьому випадку вона рiвна

Hc= logNc. (1.92)

Порiвнюючи (1.91), (1.92) з (1.89), отримаємо, що умова (1. 89) рівносильна

Hk ³ Hс (1. 93)

Таким чином, свобода вибору в кодi повинна бути бiльша або рiвна свободi вибору в системi повiдомлень. Якщо ж iмовiрностi рiзноманiтних повiдомлень неоднаковi, то необхiдна рiвнiсть в (1. 87) або (1. 89) призведе до нерiвностi в (1.93) (так як log Nс>Hc), тобто в цих випадках код постiйної довжини надлишковий. При нерiвноможливих повiдомленнях отримати рiвнiсть водночас в (1. 87) i (1. 93), тобто отримати код, оптимальний в сенсi мiнiмуму довжини повiдомлень, можна тiльки за допомогою коду змiнної довжини.

Дата добавления: 2015-07-21