загрузка...
загрузка...
На головну

Перша теорема Шеннона

  1. Аксіома Больцано-Вейєрштрасса і теорема про стягують системі відрізків
  2. Активізація політичних партій і перша російська революція 1905-1907 рр.
  3. В) Теорема про зміну моментів кількості руху для матеріальної системи (теорема моментів)
  4. Вектор прискорення в даний момент часу визначається як перша похідна від вектора швидкості за часом або друга похідна від радіуса-вектора за часом.
  5. Зовнішня політика. Перша Російсько-турецька війна
  6. Друга теорема подвійності
  7. Друга теорема Шеннона.

Раніше зазначалося, що при передачі повідомлень по каналах зв'язку можуть виникати перешкоди, здатні призвести до спотворення прийнятих знаків. Так, наприклад, якщо ви спробуєте передати мовне повідомленням у вітряну погоду людині, що знаходиться від вас на значній відстані, то воно може бути сильно спотворено такий перешкодою як вітер. Взагалі, передача повідомлень за наявності перешкод є серйозної теоретичної і практичної завданням. Її значимість зростає в зв'язку з повсюдним впровадженням комп'ютерних телекомунікацій, в яких перешкоди неминучі. [1]

При роботі з кодованої інформацією, спотворює перешкодами, можна виділити наступні основні проблеми: встановлення самого факту того, що відбулося спотворення інформації; з'ясування того, в якому конкретно місці переданого тексту це сталося; виправлення помилки - хоча б з деякою мірою вірогідності.

Перешкоди в передачі інформації - властивість не лише технічних систем. Це - цілком звичайна справа в побуті. Приклад був вище; інші приклади - розмова по телефону, в трубці якого "тріщить", водіння автомобіля в тумані і т.д. Найчастіше людина цілком пристойно справляється з кожної із зазначених вище завдань, хоча і не завжди віддає собі звіт, як він це робить (тобто неалгоритмічних, а виходячи з якихось асоціативних зв'язків). Відомо, що природна мова має велику надмірністю (в європейських мовах - до 70%), чим пояснюється велика завадостійкість повідомлень, складених із знаків алфавітів таких мов. Прикладом, який ілюструє стійкість російської мови до перешкод, може служити пропозиція "в словох всо глосноо зомононо боквой про". Тут 26% символів "вражені", однак це не призводить до втрати сенсу. Таким чином, в даному випадку надмірність є корисним властивістю.

Наприклад, кожен фрагмент тексту ( "пропозиція") передається тричі, і вірним вважається та пара фрагментів, яка повністю збіглася. Однак, велика надмірність призводить до великих тимчасових витратах при передачі інформації і вимагає великого обсягу пам'яті при її зберіганні. Звідси випливає завдання усунення надмірності, або ефективного кодування. Вперше теоретичне дослідження такого роду проблем зробив К.Шеннон.

Перша теорема Шеннона про передачу інформації, яка називається також основною теоремою про кодування при відсутності перешкод, формулюється таким чином: [5]

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

Використовуючи поняття надмірності коду, можна дати більш коротку формулювання теореми:

При відсутності перешкод передачі завжди можливий такий варіант кодування повідомлення, при якому надмірність коду буде як завгодно близькою до нуля.

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

Таким чином, оптимальне кодування принципово можливо.

Найбільш важлива для практики ситуація, коли М = 2, тобто інформацію кодують лише двома сигналами 0 і 1. [1]

Шенноном була розглянута ситуація, коли при кодуванні повідомлення в первинному алфавіті враховується різна ймовірність появи знаків, а також рівна ймовірність появи знаків вторинного алфавіту. тоді:

Кmin (А, В) = I (A) / log2 M = I (A) ,

тут I (A) - Середня інформація на знак первинного алфавіту.

Обмежимо себе ситуацією, коли M = 2, тобто для подання кодів в лінії зв'язку використовується лише два типи сигналів - найбільш просто реалізується варіант. Подібне кодування називається двійковим. Знаки довічного алфавіту прийнято позначати "0" і "1 Зручність двійкових кодів і в тому, що кожен елементарний сигнал (0 або 1) несе в собі 1 біт інформації (log2M = 1); тоді з (1), теореми Шеннона:

I1(A)? K(2)

і перша теорема Шеннона отримує таку інтерпретацію:

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

Визначення кількості переданої інформації при довічним кодуванні зводиться до простого підрахунку числа імпульсів (одиниць) і пауз (нулів). При цьому виникає проблема виділення з потоку сигналів (послідовності імпульсів і пауз) окремих кодів. Приймальний пристрій фіксує інтенсивність і тривалість сигналів. Елементарні сигнали (0 і 1) можуть мати однакові або різні тривалості. Їх кількість в коді (довжина кодової ланцюжка), який ставиться у відповідність знаку первинного алфавіту, також може бути однаковим (в цьому випадку код називається рівномірним) або різних (нерівномірний код). Нарешті, коди можуть будуватися для кожного знака вихідного алфавіту (алфавітний кодування) або для їх комбінацій (кодування блоків, слів). В результаті при кодуванні (алфавітному і словесному) можливі наступні варіанти поєднань:

Таблиця 1. Варіанти поєднань

 Тривалості елементарних сигналів  Кодування первинних символів (слів)  ситуація
 однакові  рівномірна  (1)
 однакові  нерівномірне  (2)
 різні  рівномірна  (3)
 різні  нерівномірне  (4)

У разі використання нерівномірного кодування або сигналів різної тривалості (ситуації (2), (3) і (4)) для відділення коду одного знака від іншого між ними необхідно передавати спеціальний сигнал - тимчасової роздільник (ознака кінця знака) або застосовувати такі коди, які виявляються унікальними, тобто незбіжними з частинами інших кодів. При рівномірному кодуванні однаковими за тривалістю сигналами (ситуація (1)) передачі спеціального роздільник не потрібно, оскільки відділення одного коду від іншого проводиться за загальною тривалістю, яка для всіх кодів виявляється однаковою (або однаковому числу біт при зберіганні).

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

Якщо є джерело інформації з ентропією Н (х) і канал зв'язку з пропускною здатністю С, то якщо С> H (X), то завжди можна закодувати досить довге повідомлення таким чином, що воно буде передано без затримок. Якщо ж, навпаки, С

Перша теорема Шеннона декларує можливість створення системи ефективного кодування дискретних повідомлень, у якій середня кількість двійкових символів на один символ повідомлення асимптотично прагне до ентропії джерела повідомлень (у відсутності перешкод).

Перша теорема Шеннона (переформулировка). [13]

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

Які ж можуть бути особливості вторинного алфавіту при кодуванні:

Елементарні коди 0 і 1 можуть мати однакові тривалості (t0 = t1) або різні (?).

Довжина коду може бути однаковою для всіх знаків первинного алфавіту (код рівномірний) або різної (нерівномірний код)

Коди можуть будуватися для окремого знака первинного алфавіту (алфавітний кодування) або для їх комбінацій (кодування блоків, слів).




Попередня   1   2   3   4   5   6   7   8   9   10   11   12   Наступна

Вступ | Класифікація завадостійких кодів. | Основні параметри і побудова завадостійких кодів. | Код Шеннона. |

загрузка...
© um.co.ua - учбові матеріали та реферати