Дисципліна: Теорія інформації та кодування Лектор доц.. Жолдаков О.О. Модуль №2. „ Основи кодування інформації в каналах зв’язку ” Лекція № 5. Пропускна спроможність каналів та оптимальне кодування. Формула Шенона для пропускної спроможності, поняття про оптимальне статистичне кодування та код Шенона-Фано 5.1. Об'єм сигналів та місткість каналів В теорії інформації для сигналів і каналів використовують деякі загальні показники, від яких залежить кількість інформації, що можуть переносити сигнали. Для сигналів ці показники такі: ширина спектру сигналу; Т - час тривалості сигналу; Це перевищення сигналу над шумом ( Рста Рш - відповідно потужності корисного сигналу та шуму). Добуток цих величин називають об'ємом сигналу V: Дослідження доказують, що об’єм V дуже об'єктивна характеристика і вона не може бути змінена подібно до того, як рідина (вода, масло) не міняють об'єму при тиску (легко міняють форму, але не об’єм). Наприклад, якщо на магнітну плівку записати імпульси з однією швидкістю, а зчитати - з іншою, в двічі більшою, то об'єм буде Тут довжина імпульсів скорочується вдвічі, а тому в стільки ж разів збільшується Для каналу вводяться такі характеристики; - смуга пропускання каналу ? - час, на який він надається -перевищення сигналу над щумом в каналі; - місткість каналу. Щоб узгодити сигнал з каналом (тобто пропустити сигнал через канал), необхідно виконати очевидні умовні . Можна довести не очевидну, але справедливу умову такого узгодження: . 5.2. Питома місткість сигналів Зв’язок між об'ємом сигналу та інформацією, яку він переносить, має важливе значення. Якщо вважати, що сигнал - це транспортний засіб, що перевозе інформацію, то резонно постає питання: що треба зробити, щоб перевозити найбільше. Тому введемо поняття питомої місткості і назвемо засоби для її підвищення. Будемо вважати, що передача ведеться m- річним n-розрядним кодом, причому кожна цифра передається прямокутним імпульсом довжиною , та амплітудою , де -постійна величина, а К- значення відповідної розрядної цифри. Тоді об’єм і кількість інформації в ньому і при умові, що код m -річний та n-розрядний, а всі цифри – рівноімовірні. (рівноімовірність для того, щоб зробити максимальним значення місткості ). Значить (5.1) Дія полегшення аналізу виразимо nта mчерез ,T,h. Оскільки n=T/ , n=2 T ( Т - тривалість n -розрядного сигналу). Далі визначимо . Підрахуємо середню потужність сигналу Рсза умови, що миттєва потужність (К )2 , з урахуванням рівноімовірності цифр: Для підрахування використовується формула q(q+1)(2q+1)/6. Якщо врахувати, що різницю між амплітудами сусідніх цифр вибирають, проаналізувавши рівень шуму , де - деякий коефіцієнт, що обґрунтовується зв'язківцями), то формулу(5.2) можна переписати так: Оскільки потужність шуму , після простого перетворення виразу (5.2) запишемо так: де коефіцієнт, залежний від m, тобто (5.4) Підставивши вираз (5.3 та значення n в формулу (5.1), одержимо: Таким чином, значення V залежить від основи зчислення m? . Візьмемо m>>1, тоді формула (5.4) дає: (5.5) Якщо ж m=2, то (5.6) За формулою (5.6) результат у 8/3 раза більший, ніж за формулою (5.5), а це значить, що для більшої питомої місткості двійковий код кращий, ніж інші з більшим значенням m. 5.3. Формула Шеннона для пропускної спроможності каналу Розглянемо це питання у спрощеному вигляді, беручи ту ж саму модель сигналу, яка використовувалась при оцінці питомої місткості сигналу, а саме, коли передача ведеться m- річним кодом та кожна цифра K передається імпульсом, що мав довжину та амплітуду . Допустимо, що на значення встановлено деякі чіткі обмеження, й шуми не заважають передачі. Тоді пропускна спроможність каналу Cбула б: (5.7) У випадку, коли використовуємо двійкову систему, тобто m= 2, та є межа для , маємо: (5.8) Відповідно, якщо зняти межу для , то,праховуючи, що ,одержимо: Якби на значення m не було обмежень, то згідно з формулою (5.7), пропускна спроможність С збільшувалась би до Але в каналах діє шум і, якщо різниця між суміжними амплітудами сигналів буде меншою за рівень щуму, то достовірно розрізняти відповідні цифри при прийомі сигналу не буде можливості. Спробуємо підрахувати пропускну спроможність у випадку, коли обмеження на параметри ставить тільки природа, тобто вирахуємо максимально можливе значення C. На основі формули (5.7) робимо висновок, що потрібно максимізувати 1/ =В та m) , Оскільки , то будемо вважати, що .Тепер mповинно бути таким, щоб сусідні амплітуди розпізнавались на фоні шуму, тобто де - максимальна амплітуда сигналу, що діє в каналі (шум та корисний сигнал); - амплітуда шуму в каналі; та Рш-відповідно корисного сигналу та шуму. З врахуванням сказаного вище та формули (5.7) маємо: (5.9) Таким чином, пропускна спроможність пропорційна смузі пропускання каналу та перевищенню корисного сигналу над шумом . Ясно, що можна обмінювати на , тобто одну і ту ж пропускну спроможність можна одержати за рахунок збільшення значення при зменшенні значення , чи навпаки. . Відмітимо, що згідно з формулою (5.9) навіть, коли <1, тобто перевищення від’ємне (шуми більші за сигнал), пропускна спроможність зменшується, але не дорівнює нулю. Це відповідає дійсності, а в тому, що воно можливе, легко впевнитись на такому прикладі. Збільшимо при даній моделі тривалість імпульсів, що передають цифри, а приймаючи, інтегруємо прийняті зашумлені сигнали: якщо це білий шум, то інтегрування зменшує його вклад, а корисний сигнал збільшує. Вибравши вірно довжину сигналу, доб'ємося вірного прийому імпульсів в указаному випадку (чим більша довжина, тим більша імовірність вірного прийому). З формули (8.25) видно, що чим більше значення тим більша пропускна спроможність, а при і . Але останнє невірне оскільки в каналі діє шум, і його потужність зростає пропорційно , тобто в цьому випадку по мірі збільшення буде зростати і С , але до певної межі. Формула (8.27) одержала назву "формула Шеннона для пропускної спроможності". 5.4. Поняття про оптимальне статистичне кодування Коли в каналі передачі відсутній шум, а передача ведеться за допомогою дискретних сигналів, то, як показав Шеннон, справедлива така.теорема: якщо продуктивність джерела повідомлень Rд (кількість інформації в одиницю часу) менша або дорівнює С-ε, де ε - скільки завгодно мала величина, то завжди є спосіб кодування, що дозволяє передавати всі його повідомлення, а при Rд >C цього зробити неможливо. Суть теореми в тому, що, яка б велика не була надлишковість джерела, всі його повідомлення можуть бути передані по каналу, якщо тільки R<=C- ε.. Для раціонального використання пропускної спроможності каналів треба розробляти відповідні способи кодування повідомлень. Оптимальним називають таке кодування, при якому найкраще використовується пропускна спроможність C в каналі без шуму. При оптимальноку кодуванні швидкість передачі інформації повинна наближатись до пропускної спроможності. Структура оптимального коду залежить в основному від статистичних характеристик джерела. Питання побудови оптимальних кодів дуже складне, тому розглянемо найбільш простий випадок, коли ви користовуемо джерело статистичне незалежних повідомлень. Таким чином, маємо джерело, що дає такі типи повідомлень: Імовірності цих повідомлень задані: Кожне з цих повідомлень потрібно закодувати двійковим кодом, витративши на кодування k-го повідомлення розрядів ( можуть бути різними), причому двійковий розряд передається за час Тоді швидкість передачі Rможна записати: (5.10) де - ентропія джерела повідомлень; - середня довжина кодової комбінації, яку легко вирахувати: (5.11) На основі формул (3.26) та (3.27) маємо; (5.12) Як бачимо, чисельник формули (5.12) залежить виключно від статистичних дачних якостей джерела, а знаменник, крім того, і від способу кодування (які значення прийняті для nк ) та якостей каналу ( ) . Згідно з формулою (5.8) у випадку, що розглядається,швидкість передачі R, не може бути більшою за 1/ . Щоб одержати цей найкращий результат, необхідно, щоб nк= -log p( ) Оскільки згідно з формулою -це кількість інформації, що в в повідомленні ак, то одержаний результат, слід інтерпретувати так: при оптимальному кодуванні кількість розрядів для повідомлення ак дорівнює кількості інформації, яку воно дає. Ясно також, що більш імовірні повідомлення передаються за коротший час, менш імовірні - за довший. Таким чином,розроблено загальний принцип побудови оптимального статистичного коду, але не якийсь конкретний код. 5.5. Оптимальний статистичний код Шеннона-Фано Одним з конкретних оптимальних кодів є так званий код Шеннона-Фано. Алгоритм його побудови такий: всі типи повідомлень записуються в стовпчик в порядку зменшення їх імовірностей; стовпчик розподіляється на дві частини з сумарно рівними імовірностями і для всіх повідомлень верхньої частини як перший розряд записують одиницю, а для нижньої - нуль; за тим же принципом на двоє розділяється кожна з одержаних раніше частин і таким же методом записуються інші цифри повідомлень. Такий процес ділення і кодування проводиться доти, доки в обох частинах не стане по одному елементу. Ясно, що код буде нерівномірним, але він буде оптимальним. Продемонструємо техніку кодування на такому прикладі. Нехай є джерело із чотирьох типів повідомлень, а саме: а імовірності їх появи відповідно рівні: р(а1) = 0,25; р(а2) = 0,25; р(а3) = 0,5; р(а4) = 0,125; Тоді реалізуючи алгоритм побудови коду Шеннона-Фано, будемо мати таку таблицю (табл.8.1). Таблиця 8.1
В табл.8.1 прийняті такі позначення: - двійкові цифри коду Шеннона-Фано; 1,2,3 - етапи розділення стовпчиків повідомлень; р ( ) - імовірність повідомлень . Таким чином, повідомлення закодовано так: В нерівномірних кодах при декодуванні виникають затруднення з виявленням меж між повідомленнями. Для виключення помилок, як правило, використовують спеціальні роздільні знаки, як наприклад, в коді Морзе, а це веде до зменшення швидкості передачі і деякого ускладнення пристроїв. Слід підкреслити, що в коді Шеннона-Фано, який також нерівномірний, роздільні знаки являються зайвими. Цю властивість легко перевірити на прикладі будь-якої послідовності прийнятих цифр при передачі коду Шеннона-Фано. Наприклад, якщо передавати то відповідна послідовність буде: 110101100111100. Починаючи декодувати спочатку, матимем: Труднощі тут відсутні, оскільки початок одних комбінацій коду Шеннона-Фано не є продовженням інших. Перевіримо швидкість передачі, при умові порівняння коду Шеннона-Фано та звичайного рівномірного коду (в даному випадку -це комбінації 00, 01, 10, 11). Згідно з формулою (8.30) для коду Шеннона-Фано в розглянутому випадку матимем: тобто швидкість передачі дорівнює пропускній спроможності каналу. А тепер порахуємо таким же чином для війкового рівномірного коду, в якого (для даного прикладу) всі комбінації двохрозрядні, тобто . Тоді R=1,75/2 =0,875/ =0,875C, тобто швидкість передачі менша, ніж пропускна спроможність. Досі був розглянутий найбільш простий випадок, коли повідомлення статистично незалежні. В більш складному випадку використовують так званий змінний метод кодування, коли кількість розрядів залежить від відносної імовірності, але тут дуже ускладнюються як процеси кодування, так і декодування. 5.6. Недоліки Шеннонівської теорії інформації Шеннонівська теорія чисто кількісна і побудована на тому, що основним показником повідомлення є його імовірність, а приймач в повній мірі “розуміє” те, що прийнято. Такий підхід дозволив побудувати чітку та конструктивну теорію, що добре служить для відповідних пояснень та оцінок явищ в засобах зв'язку. Але інформація складна, об'ємна та багатогранна, тому застосування теорії не за призначенням може не дати позитивних результатів, про що попереджав в одній із своїх робіт ("Бандвагон") Шеннон. Про це слід пам'ятати, оскільки популярність теорії, дуже висока і на цю тему опубліковано багато робіт, які не мають ціності і можуть дезорієнтувати при роботі. Таким чином, з загальних позицій теорія Шеннона має рад нодоліків. Так, з прийнятого повідомлення різні приймачі, які мають неоднаковий "інтелект", візьмуть різну кількість інформації. Якщо розглянути приведений нижче гіпотетичний'приклад, то в цьоцу легко пересвідчитись. Припустимо, що лектор читав лекцію для деякої аудиторії, де є малі діти, учні, студенти різних курсів, інженери, доценти, професори. Зрозуміло, що ніякої інформації з цієї лекції не одержать ті, що зовсім не мають відповідної підготовки, а також ті, які про це все знають. Найбільше інформації одержать ті, що не мали уяви про сказане, але мали відповідну підготовку, щоб усе зрозуміти. Тобто є залежність від інтелекту приймача, а цього Шеннонівська теорія не враховує. Кажуть про це так: "Не враховується тезаурус системи приймання". Крім того, з практики добре відомо, що повідомлення поділяються на повідомлення більшої та меншої важливості, що також не враховується - відсутня прагматика при оцінці інформації. Зрозуміло, що велике значення придається змісту повідомлень, а розглянута теорія цього зовсім не враховує, тобто відсутній семантичний аспект. Отже, слід зробити висновок, що теорія Шеннона не всюди діє і (наприклад, при обгрунтуванні інформаційної бази системи), тому і користуватись нею треба обережно і восновному за призначенням. |