і не може бути задана однією цифрою на підставі статистичних випробувань.
Так при передачі десяткових цифр двійковим кодом максимально завантаженими бувають тільки ті символи вторинного алфавіту, які передають значення, що є цілочисельними ступенями двійки. В інших випадках тією ж кількістю символів може бути передано більшу кількість цифр (повідомлень). Наприклад, трьома двійковими розрядами ми можемо передати і цифру 5, і цифру 8, т. Е. На передачу п'яти повідомлень витрачається стільки ж символів, скільки витрачається і на вісім повідомлень.
Фактично для передачі повідомлення достатньо мати довжину кодової комбінації
де N - загальна кількість переданих повідомлень.
L можна представити і як
де і -відповідно якісні ознаки первинного та вторинного алфавітів. Тому для цифри 5 у двійковому коді можна записати
Однак цю цифру необхідно округлити до найближчого цілого числа, так як довжина коду не може бути виражена дробовим числом. Округлення, природно, проводиться в більшу сторону. У загальному випадку, надмірність від округлення
де - округлене до найближчого цілого числа значення. Для нашого прикладу
Надмірність - не завжди небажане явище. Для підвищення завадостійкості кодів надмірність необхідна і її вводять штучно у вигляді додаткових символів (див. Тему 6). Якщо в коді всього п розрядів і з них несуть інформаційне навантаження, то = характеризує абсолютну коригувальну надмірність, а величина характеризує відносну коригувальну надмірність.
Інформаційна надмірність - зазвичай явище природне, закладена вона в первинному алфавіті. Коригувальна надмірність - явище штучне, закладена вона в кодах, представлених у вторинному алфавіті.
Найбільш ефективним способом зменшення надмірності повідомлення є побудова оптимальних кодів.
Оптимальні коди [5] - коди з практично нульовою надмірністю. Оптимальні коди мають мінімальну середню довжину кодових слів - L. Верхня і нижня межі L визначаються з нерівності
де Н - ентропія первинного алфавіту, т - число якісних ознак вторинного алфавіту.
У разі поблочного кодування, де кожен з блоків складається з М незалежних букв. мінімальна середня довжина кодового блоку лежить в межах
Загальна вираз середнього числа елементарних символів на букву повідомлення при блоковому кодуванні
З точки зору інформаційного навантаження на символ повідомлення по блоках кодування завжди вигідніше, ніж побуквенное.
Суть блокового кодування можна усвідомити на прикладі представлення десяткових цифр в двійковому коді. Так, при передачі цифри 9 в двійковому коді необхідно витратити 4 символу, т. Е. 1001. Для передачі цифри 99 при побуквенном кодуванні - 8, при блоках - 7, так як 7 довічних знаків досить для передачі будь-якої цифри від 0 до 123; при передачі цифри 999 співвідношення буде 12 - 10, при передачі цифри 9999 співвідношення буде 16 - 13 і т. д. У загальному випадку «вигода» блокового кодування виходить і за рахунок того, що в блоках відбувається вирівнювання ймовірностей окремих символів, що веде до підвищення інформаційного навантаження на символ.
При побудові оптимальних кодів найбільшого поширення знайшли методики Шеннона-Фано і Хаффмена.
Згідно з методикою Шеннона - Фано побудова оптимального коду ансамблю з повідомлень зводиться до наступного:
1-й крок. Безліч з повідомлень розташовується в порядку убування ймовірностей.
2-й крок. Початковий ансамбль кодованих сигналів розбивається на дві групи таким чином, щоб сумарні ймовірності повідомлень обох груп були по можливості рівні. Якщо рівній ймовірності в підгрупах не можна досягти, то їх ділять так, щоб у верхній частині (верхньої підгрупі) залишалися символи, сумарна ймовірність яких менше сумарної ймовірності символів у нижній частині (в нижній підгрупі).
3-й крок. Першій групі присвоюється символ 0, другої групи символ 1.
4-й крок. Кожну з освічених підгруп ділять на дві частини таким чином, щоб сумарні ймовірності новостворених підгруп були по можливості рівні.
5-й крок. Першим групам кожної з підгруп знову присвоюється 0, а другим - 1. Таким чином, ми отримуємо другі цифри коду. Потім кожна з чотирьох груп знову ділиться на рівні (з точки зору сумарної ймовірності) частини до тих пір, поки в кожній з підгруп не залишиться по одній букві.
Згідно з методикою Хаффмена, для побудови оптимального коду N символи первинного алфавіту виписуються в порядку убування ймовірностей. Останні символів, де [6] і - ціле число, об'єднують в деякий новий символ з імовірністю, яка дорівнює сумі ймовірностей об'єднаних символів Останні символи з урахуванням утвореного символу знову об'єднують, отримують новий, допоміжний символ, знову виписують символи в порядку убування ймовірностей з урахуванням допоміжного символу і т. д. до тих пір, поки сума ймовірностей т символів, що залишились після -го виписування в порядку убування ймовірностей не дасть в сумі ймовірність, рівну 1. На практиці зазвичай, не виробляють многократн ого виписування ймовірностей символів з урахуванням ймовірності допоміжного символу, а обходяться елементарними геометричними побудовами, суть яких зводиться до того, що символи кодованого алфавіту попарно об'єднуються в нові символи, починаючи з символів, що мають найменшу ймовірність. Потім з урахуванням новостворених символів, яким присвоюється значення сумарної ймовірності двох попередніх, будують кодове дерево, в вершині якого стоїть символ з імовірністю 1. При цьому відпадає необхідність в упорядкуванні символів кодованого алфавіту в порядку убування ймовірностей.
Побудовані за вказаними вище (або подібним) методикам коди з нерівномірним розподілом символів, що мають мінімальну середню довжину кодового слова, називають оптимальним, нерівномірним, кодами (ОНК). Рівномірні коди можуть бути оптимальними тільки для передачі повідомлень з равновероятности розподілом символів первинного алфавіту, при цьому число символів первинного алфавіту має дорівнювати цілій степені числа, рівного кількості якісних ознак вторинного алфавіту, а в разі двійкових кодів - цілої ступеня двох.
Максимально ефективними будуть ті ОНК, у яких
Для двійкових кодів
так як log22 = 1. Очевидно, що рівність (52) задовольняється за умови, що довжина коду у вторинному алфавіті
Величина точно дорівнює Н, якщо, де п - будь-яке ціле число. Якщо п не є цілим числом для всіх значень букв первинного алфавіту, то і, згідно з основною теоремою кодування [7], середня довжина кодового слова наближається до ентропії джерела повідомлень в міру укрупнення кодованих блоків.
Ефективність ОНК. оцінюють за допомогою коефіцієнта статистичного стиснення:
який характеризує зменшення кількості двійкових знаків на символ повідомлення при застосуванні ОНК в порівнянні з застосуванням методів нестатистичні кодування і коефіцієнта відносної ефективності
який показує, наскільки використовується статистична надмірність переданого повідомлення.
Для найбільш загального випадку неравновероятних і взаємонезалежних символів
Для випадку неравновероятних і взаємозалежних символів
ТЕМА 6. ВИЯВЛЕННЯ І ВИПРАВЛЕННЯ ПОМИЛОК В ПОВІДОМЛЕННЯХ
Поняття про ідею корекції помилок
Для того щоб в ухваленому повідомленні можна було виявити помилку це повідомлення повинно володіти деякою надлишковою інформацією, що дозволяє відрізнити помилковий код від правильного Наприклад, якщо передане повідомлення складається з трьох читається ну ніяк однакових частин, то в прийнятому повідомленні відділення правильних символів від помилкових може бути здійснено за результатами накопичення посилок одного виду, наприклад 0 або 1. Для двійкових кодів цей метод можна проілюструвати дотримуюся-щим прикладом:
10110 - передана кодова комбінація;
10010 - 1-я прийнята комбінація;
10100 - -я прийнята комбінація;
00110 - 3-тя прийнята комбінація;
10110 - накопичена комбінація.
Як бачимо, незважаючи на те, що у всіх трьох прийнятих комбінаціях були помилки, накопичена не містить помилок [8].
Прийняте повідомлення може також складатися з коду і його інверсії. Код та інверсія посилаються в канал зв'язку як одне ціле. Помилка на приймальному кінці виділяється при зіставленні коду і його інверсії.
Для того щоб спотворення будь-якого з символів повідомлення призвело до забороненої комбінації, необхідно в коді виділити комбінації, що відрізняються один від одного в ряді символів, частина з цих комбінацій заборонити і тим самим ввести в код надмірність. Наприклад, в рівномірному блочному коді вважати дозволеними кодові комбінації з постійним співвідношенням нулів і одиниць в кожної кодової комбінації. Такі коди отримали назву кодів з постійною вагою. Для двійкових кодів число кодових комбінацій в кодах з постійним вагою довжиною в п символів одно
де - число одиниць в кодовому слові. Якби не існувало умови постійної ваги, то число комбінацій коду могло б бути набагато більшим, а саме. Прикладом коду з постійним вагою може служити стандартний телеграфний код № 3 (див. Додаток 4). Комбінації цього коду побудовані таким чином, що на 7 тактів, протягом яких повинна бути прийнята одна кодова комбінація, завжди припадають три струмові і чотири безтоковие посилки. Збільшення або зменшення кількості струмових посилок говорить про наявність помилки.
Ще одним прикладом введення надмірності в код є метод суть якого полягає в тому, що до вихідних кодів додаються нулі або одиниці таким чином, щоб сума їх завжди. була парній або непарній. Збій будь-якого одного символу завжди порушить умову парності (непарності), і помилка буде виявлена. В цьому випадку комбінації один від одного повинні відрізнятися мінімум в двох символах, т. Е. Рівно половина комбінацій коду є забороненою (забороненими є всі непарні комбінації при перевірці на парність або навпаки).
У всіх згаданих вище випадках повідомлення мають надлишкову інформацією. Надмірність повідомлення говорить про те, що воно могло б містити більшу кількість інформації, якщо бьг не багатократна повторення одного і того ж коду, не додавання до коду його інверсії, що не несе ніякої інформації, якби. не штучна заборона частини комбінацій коду і т. д. Але всі перераховані види надмірності доводиться вводити для того, щоб можна було відрізнити помилкову комбінацію від правильної.
Коди без надмірності виявляти, а тим більше виправляти помилки не можуть [9]. Мінімальна кількість символів, в яких будь-які дві комбінації коду відрізняються один від одного, називається кодовою відстанню. Мінімальна кількість символів, в яких всі комбінації коду відрізняються один від одного, називається мінімальним кодовою відстанню. Мінімальна кодова відстань - параметр, що визначає стійкість коду і закладену в коді надмірність. Мінімальним кодовою відстанню визначаються коригувальні властивості кодів.
У загальному випадку для виявлення r помилок мінімальна кодова відстань
Мінімальна кодова відстань, необхідне для одночасного виявлення і виправлення помилок,
де s - число виправляє помилок.
Для кодів, тільки виправляють помилки,
Для того щоб визначити кодову відстань між двома комбінаціями двійкового коду, досить підсумувати ці комбінації по модулю 2 і підрахувати число одиниць в отриманій комбінації.
Поняття кодового відстані добре засвоюється на прикладі побудови геометричних моделей кодів. На геометричних моделях в вершинах n-кутників, де n-значность коду, розташовані кодові комбінації, а кількість ребер n-кутника, що відокремлюють одну комбінацію від іншої, так само кодовому віддалі.
Якщо кодова комбінація двійкового коду А відстоїть від кодової комбінації В на відстані d, то це означає, що в коді А потрібно d символів замінити на зворотні, щоб отримати код В, але це не означає, що потрібно d додаткових символів, щоб код володів даними корректирующими властивостями. У довічних кодах для виявлення одиночної помилки досить мати 1 додатковий символ незалежно від числа інформаційних розрядів коду, а мінімальна кодова відстань
Для виявлення та виправлення одиночної помилки співвідношення між числом інформаційних розрядів і числом коригувальних розрядів повинно відповідати таким вимогам:
при цьому мається на увазі, що загальна довжина кодової комбінації
Для практичних розрахунків при визначенні числа контрольних розрядів кодів з мінімальним кодовою відстанню зручно користуватися виразами:
якщо відома довжина повної кодової комбінації п, і
якщо при розрахунках зручніше виходити з певної кількості інформаційних символів [10].
Для кодів, що виявляють все триразові помилки
Для кодів довжиною в п символів, що виправляють одну або дві помилки
Для практичних розрахунків можна користуватися виразом
Для кодів, що виправляють 3 помилки
Умовна функція. Логічні вирази. Вкладені логічні функції ЯКЩО. Особливості записи логічних операцій в табличних процесорах: спочатку записується ім'я логічної операції (І, АБО, НЕ).
Інформаційним називають процес, що виникає в результаті встановлення зв'язку між двома об'єктами матеріального світу: джерелом. або генератором інформації та її приймачем, або одержувачем.
Схема і коефіцієнт ефективності дискретного каналу. Функції блоків, властивості канальних матриць, інформаційні характеристики джерела повідомлень і приймача. Теореми Шеннона про критичної швидкості, криптографічного і помехоустойчивому кодування.
Інформатика - наука про закони і методи накопичення, обробки і передачі інформації. У найбільш загальному вигляді поняття інформації можна висловити так: Інформація - це відображення предметного світу за допомогою знаків і сигналів.
Основні поняття і визначення кодування інформації. Кодова комбінація і її довжина. Класифікація кодів за різними ознаками, способи їх подання, призначення. Подання у вигляді кодових дерев або многочленів, матричне і геометричне.
Біт, невизначеність, кількість інформації та ентропія. Формула Шеннона. Формула Хартлі. Логарифми. Кількість інформації, що отримується в процесі повідомлення. Взаємодія джерела і приймача інформації. Кількість, інформаційна ємність осередків пам'яті.
Основи теорії передачі інформації. Експериментальне вивчення кількісних аспектів інформації. Кількість інформації по Хартлі і К. Шеннон. Частотні характеристики текстових повідомлень. Кількість інформації як міра знятої невизначеності.
Інформація є відносно новим об'єктом, властивості якого вивчаються природознавством, і немає нічого незвичайного в тому, що не всі її властивості вивчені досить повно.
Оптимальне статистичне (економне) кодування. Основні поняття і визначення теорії кодування. Принципи побудови оптимальних кодів. Здатність системи здійснювати прийом інформації в умовах наявності перешкод. Збільшення потужності сигналів.
Механізм передачі інформації, її кількість і критерії вимірювання. Одиниці інформації в залежності від підстави логарифма. Основні властивості і характеристики кількості інформації, її ентропія. Визначення ентропії, надмірності інформаційних повідомлень.
Джерело (передавач) і одержувач (приймач) служать для обміну деякої інформацією. В одному випадку відправником і одержувачем інформації служить
Програма розрахунку інформаційних характеристик каналу зв'язку. Побудова коду для передачі Повідомлень. Процедури кодування, декодування та оцінка ефектівності кодів. Програма на алгорітмічній мові Паскаль. Канальна матриця, что візначає Втрата информации.
Особливості обчислення кількості інформації, одержуваної при фазовому зсуві сигналу, якщо відома його амплітуда. Розрахунок інформаційних характеристик джерел дискретних повідомлень і дискретного каналу. Особливості застосування дискретизації і квантування.
Загальна схема дії каналів зв'язку, їх класифікація та характеристика. Дискретний, бінарний канал зв'язку і визначення їх пропускної спроможності, особливості дії з перешкодами і без них по теоремі Шеннона. Пропускна здатність безперервного каналу.
2.2.2. Інформаційний критерій оцінки фонетичної неопреде-лінощів. При розпізнаванні усного мовлення необхідно прагнути до того, щоб всі фонеми класифікувалися правильно, тому нас цікавить розпізнавання повної послідовності фонетичних одиниць, складових висловлювання.
Загальна кількість неповторюваних повідомлень. Обчислення швидкості передачі інформації та пропускної здатності каналів зв'язку. Визначення надмірності повідомлень і оптимальне кодування. Процедура побудови оптимального коду за методикою Шеннона-Фано.
Рішення типових задач з телекомунікацій.
Аналіз ймовірності входу в систему зловмисником з одного і трьох спроб. Ймовірності входу в систему при фіксованій та випадкової довжині вибірки. Дослідження і розрахунок захищеності (надійності) методу при підглядання. Оптимізація довжини вибірки.
Об'єднання як сукупність кількох ансамблів дискретних, випадкових подій. Безумовна ентропія - середня кількість інформації, що припадає на один символ. Опис інформаційних властивостей безперервного джерела. Поняття диференціальної ентропії.