Завдання кодування

Введення

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

Хоча існуючі на даний момент системи передачі даних відповідають усім основним стандартам і вимогам, вони все ж не є досконалими. Причин тому вплив перешкод в каналі зв'язку. При передачі повідомлень по каналах зв'язку можуть виникати перешкоди, здатні призвести до спотворення прийнятих знаків. Природна мова має великий надмірністю (у європейських мовах - до 7%), чим пояснюється велика завадостійкість повідомлень, складених із знаків алфавітів таких мов. Прикладом, який ілюструє стійкість російської мови до перешкод, може служити пропозиція «в словох ВСО глосноо зомононо боквой о». Тут 26% символів «вражені», однак це не призводить до втрати сенсу. Таким чином, в даному випадку надлишковість є корисним властивістю. Надмірність могла б бути використана і при передачі кодованих повідомлень в технічних системах. Наприклад, кожен фрагмент тексту («пропозиція») передається тричі, і вірним вважається та пара фрагментів, яка повністю збіглася. Однак, хвора надмірність призводить до великих тимчасових витратах при передачі інформації і вимагає великого об'єму пам'яті при її зберіганні. Вперше теоретичне дослідження ефективного кодування зробив К. Шеннон.

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

Актуальність: Робота переважної більшості сучасних систем зв'язку заснована на передачі повідомлень в цифровому вигляді. Збій при прийомі будь-якого елемента цифрових даних здатний викликати значне спотворення всього повідомлення в цілому, що, у свою чергу, може призвести до повної втрати інформації, що міститься в ньому. В сучасних інформаційних системах найважливішим завданням є забезпечення інформаційної безпеки, пов'язаної з методами криптографії та кодування, теоретичні основи якої заклав Шеннон в своїх працях. У даній роботі будуть розглянуті основи задачі кодування, а також практичне застосування завадостійких кодів.

Об'єкт: процес формування цифрових сигналів

Предмет: кодування інформації

Мета дослідження: розробити алгоритм на основі аналізу задачі кодування.

Завдання:

1) Проаналізувати теоретичні основи задачі кодування.

2) Розглянути основні види завадостійких кодів.

3) Практична реалізація завадостійкого кодування.

1. Теоретичні основи задачі кодування

1. Постановка задачі кодування

Перш ніж розглянути завдання кодування, необхідно розглянути ряд визначень, що використовуються в теорії кодування [1]:

Код - (1) правило, що описує відповідність знаків або їх поєднань одного алфавіту знаків або їх сполученням іншого алфавіту; - (2) знаки вторинного алфавіту, використовувані для представлення знаків або їх поєднань первинного алфавіту.

Кодування - переклад інформації, представленої за допомогою первинного алфавіту, в послідовність кодів.

Декодування - операція, зворотна кодуванню, тобто відновлення інформації в первинному алфавіті за отриманою послідовності кодів.

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

Інформаційна ентропія - в ​​теорії зв'язку ентропія використовується як міра невизначеності очікуваного повідомлення, тобто ентропія джерела інформації з незалежними повідомленнями є середнє арифметичне кількостей інформації повідомлень

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

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

Без технічних сторін передачі і зберігання повідомлення (тобто того, яким чином фактично реалізовані передача-прийом послідовності сигналів або фіксація станів), математична постановка задачі кодування, дається наступним чином. [5]

Нехай первинний алфавіт A містить N знаків з середньою інформацією на знак, визначеній з урахуванням ймовірностей їх появи, I ₁ ^(A) (нижній індекс відображає ту обставину, що розглядається перше наближення, а верхній індекс у дужках вказує алфавіт). Вторинний алфавіт B нехай містить M знаків з середньою інформаційної ємністю I ₁ ^(A). Нехай також вихідне повідомлення, представлене в первинному алфавіті, містить n знаків, а закодоване повідомлення - m знаків. Якщо вихідне повідомлення містить I ^(A) інформації, а закодоване - I ^(B), то умова оборотності кодування, тобто неісчезновенія інформації при кодуванні, очевидно, може бути записано таким чином:

I ^(A) ≤ I ^(B),

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

n * I ₁ ^(A) ≤ n * I ₁ ^(B),

або

I ₁ ^(A) ≤ m / n * I ₁ ^(B)

Ставлення m / n, вочевидь, характеризує середнє число знаків вторинного алфавіту, яке доводиться використовувати для кодування одного знака первинного алфавіту - будемо називати його довжиною коду або довжиною кодової ланцюжка і позначимо K ^(B) (верхній індекс вказує алфавіт кодів). [

В окремому випадку, коли поява будь-яких знаків вторинного алфавіту равновероятно, згідно з формулою Хартлі I ₁ ^(B) = log ₂ M, і тоді

I ₁ ^(A) / log ₂ M ≤ K ^{(B) (1)}

За аналогією з величиною R, що характеризує надмірність мови, можна ввести відносну надмірність коду (Q):

Q = 1 - I ^(A) / I ^(B) = 1 - I ₁ ^(A) / K ^(B) * I ₁ ^{(B) (2)}

Ця величина показує, наскільки операція кодування збільшила довжину вихідного повідомлення. Очевидно, чим менше Q (тобто чим ближче вона до 0 або, що те ж, I ^(B) ближче до I ^(A)), тим більш вигідним виявляється код і більш ефективної операція кодування. Вигідність кодування при передачі і зберіганні - це економічний фактор, оскільки більш ефективний код дозволяє витратити на передачу повідомлення менше енергії, а також часу і, відповідно, менше займати лінію зв'язку; при зберіганні використовується менше площі поверхні (обсягу) носія. При цьому слід усвідомлювати, що вигідність коду не ідентична тимчасової вигідності всього ланцюжка кодування - передача - декодування, можлива ситуація, коли за використання ефективного коду при передачі доведеться розплачуватися тим, що операції кодування та декодування будуть займати більше часу і інших ресурсів (наприклад, місця в пам'яті технічного пристрою, якщо ці операції проводяться з його допомогою).

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

Реалізація основних характеристик каналу зв'язку крім розробки технічних пристроїв, потребує вирішення інформаційних завдань - вибір оптимального методу кодування. [11]

Основними завданнями кодування є:

1. Забезпечення економічності передачі інформації за допомогою усунення надмірності.

2. Забезпечення надійності (завадостійкості) передачі інформації

3. Узгодження швидкості передачі інформації з пропускною спроможністю каналу

Відповідність між елементами дискретних повідомлень і видом кодування забезпечується вибором:

1. тривалості сигналів

2. Довжини кодового слова

3. Алфавіту знаків і способу кодування (побуквенное, блочного)

Вважається, що повідомлення джерела інформації формується із знаків аi, i = 1,2, .. Na зовнішнього (вхідного, первинного) алфавіту А обсягом Na. Повідомлення є слова, утворені послідовністю nr знаків: Ar = a1a2 ... anr. У кодує пристрої слово Ar перетвориться в кодове слово Br = b1b2 ... bmr, складене з mr знаків b _j, j = 1,2, .. Nb внутрішнього (вихідного, вторинного) алфавіту В. Число знаків кодового алфавіту називають підставою коду. Кількість символів в кодовому слові називають довжиною кодового слова. Відображення G множини слів у алфавіті А на безліч слів у алфавіті В називають кодований відображенням або кодом. Застосування кодує відображення G до будь-якому слову з вхідного алфавіту називається кодуванням. Тобто код - це правило відображення знаків одного алфавіту в знаки іншого алфавіту, кодування - це перетворення однієї форми повідомлення в іншу за допомогою зазначеного коду.

Розрізняють побуквенное і блочне кодування. При побуквенное кодуванні кожному знаку зовнішнього алфавіту ставитися у відповідність кодове слово із знаків внутрішнього алфавіту. [2]

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

Cлова із знаків внутрішнього алфавіту В, зіставлені словами із знаків зовнішнього алфавіту А за правилом G, називаються кодовими комбінаціями. Якщо ArE A і G (Ar) = Br, то говорять, що слову Ar відповідає кодова комбінація Br. Сукупність кодових комбінацій використовуються для передач заданої кількості дискретних повідомлень називають кодовим словником.

Процес, зворотний кодуванню, полягає у відновленні з кодової комбінації Br = b1b2 ... bmr слова Ar = a1a2 ... anr з вхідного алфавіту і називається декодуванням. Якщо процес кодування здійснюється з використанням правила G, то процес декодування заснований на застосуванні правила G-1, де G-1 є відображення, зворотне відображення G.

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

Нехай Ar - слово в алфавіті А і Br = G (Ar) - слово в алфавіті В. Код називається оборотним, якщо для будь-якого слова Br = G (Ar) в алфавіті В існує єдине перетворення G-1 (Br) = Ar. Тобто, за словом Br в алфавіті В, завжди однозначно відновлюється слово Ar в алфавіті А, з якого було утворено слово Br.

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

Прикладом необоротного кодування є переклад тексту з однієї природної мови на іншу. (Інший переклад побуквенно зазвичай не відповідає початковому тексту.)

Щоб код був оборотним, необхідно:

1) щоб різним символів вхідного алфавіту А були зіставлені різні кодові комбінації;

2) щоб ніяка кодова комбінація не становила початкової частини який-небудь інший кодової комбінації.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

До _min (А, В) = I ^(A) / log ₂ M = I ^(A),

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

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

I ₁ ^(A) ≤ K ⁽²⁾

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 Друга теорема Шеннона

Ставлення пропускної спроможності каналу зв'язку до швидкості неспотвореної передачі символів алфавіту переданого повідомлення повинно бути більше або дорівнює ентропії передачі одного символу. [5]

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

Доказ теореми грунтується на наступних міркуваннях. Спочатку послідовність X = {x _i} кодується символами з У так, що досягається максимальна пропускна здатність (канал не має перешкод). Потім у послідовність з У довжини n вводиться r символів по каналу передається нова послідовність з n + r символів. Число можливих послідовностей довжини n + r більше числа можливих послідовностей довжини n. Безліч всіх послідовностей довжини n + r може бути розбите на n підмножин, кожному з яких зіставлено одна з послідовностей довжини n. При наявності перешкоди на послідовність з n + r виводить її з відповідного підмножини з імовірністю як завгодно малою. [12]

Теорема дозволяє визначати на приймальній стороні каналу, якому підмножині належить перекручена перешкодами ухвалена послідовність n + r, і тим самим відновити вихідну послідовність довжини n.

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

1.4 Завадостійке коди

1.4.1 Класифікація завадостійких кодів

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

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

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

Теорія кодування виникла наприкінці 40-х років з появою робіт Голі, Хеммінга і Шеннона. Видатні два вчені Голей і Хеммінга заклали основу алгебраїчним методам кодування, які використовуються і до цього дня, а Шеннон запропонував і дослідив поняття випадкового кодування. Відзначимо, що в сучасних інформаційних системах найважливішим завданням є забезпечення інформаційної безпеки, пов'язаної з методами криптографії та кодування, теоретичні основи якої заклав Шеннон в своїх працях. [3]

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

У 50-ті-70-і роки було розроблено велику кількість алгебраїчних кодів з виправленням помилок, серед яких найбільш затребуваними стали коди Боуза-Чоудхурі-хоквінгема (БЧХ), Ріда-Соломона (РС), Ріда-Малера, Адамара, Юстенсена, Гоппе , циклічні коди, сверточних коди з різними алгоритмами декодування (послідовне декодування, алгоритм Вітербо), арифметичні коди.

Однак на практиці застосовується відносно невелика група алгебраїчних завадостійких кодів: БЧХ, Ріда-Соломона і надточні коди. Найбільш широко застосовуються циклічні коди з виявленням помилок в стандартних протоколах HDLC, Х.25 / 2 (LAP - B, LAP - M). Коди Ріда-Соломона з виправленням помилок знаходять застосування в каналах радіозв'язку. У каналах супутникового зв'язку, що характеризуються незалежним характером помилок, широко застосовуються надточні коди.

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

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

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

У різних середовищах характер перешкод різний. Помилки можуть бути поодинокі, а можуть виникати групами, відразу по кілька. У результаті перешкод можуть зникати біти або навпаки - з'являтися зайві.

Основною характеристикою інтенсивності перешкод в каналі є параметр шуму - p. Це число від 0 до 1, рівне ймовірності інвертування біта, за умови що, він був переданий на каналі і отриманий на іншому кінці.

Наступний параметр - p 2. Це ймовірність того ж події, але за умови, що попередній біт також був інвертований.

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

У групових помилок є свої плюси і мінуси. Плюси полягають в наступному. Нехай дані передаються блоками по 1000 біт, а рівень помилки 0,001 на біт. Якщо помилки ізольовані і незалежні, то 63% блоків будуть містити помилки. Якщо ж вони виникають групами по 100 відразу, то помилки будуть містити 1% блоків.

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

Для надійної передачі кодів було запропоновано два основні методи.

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

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

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

Зовнішні джерела перешкод викликають в основному імпульсні перешкоди, а внутрішні - флуктуаційні. Перешкоди, накладаючись на відеосигнал, призводять до двох типів перекручувань: крайові і дроблення. Крайові спотворення пов'язані зі зміщенням переднього або заднього фронту імпульсу. Дроблення пов'язано з подрібненням єдиного відеосигналу на деяку кількість більш коротких сигналів. [4]

Перешкодостійкі коди поділяються на блокові і безперервні.

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

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

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

До безперервним кодами відносяться і сверточних коди, в яких кожен інформаційний символ, що надходить на вхід кодує пристрої, викликає поява на його вихід ряду перевірочних елементів, утворених підсумовуванням за модулем 2 цього символу і "k-1" попередніх інформаційних символів. Рекурентні коди дозволяють виправляти групові помилки ("пачки") в каналах зв'язку.

Блокові коди поділяються на рівномірні і нерівномірні. У рівномірних кодах, на відміну від нерівномірних, всі кодові комбінації містять однакове число n - символів (розрядів) з постійною тривалістю τ0 імпульсів символів коду. Рівномірні коди в основному і застосовуються в системах зв'язку, тому що це спрощує техніку передачі і прийому.

Класичними прикладами нерівномірного коду є код Морзе, широко застосовуваний в телеграфії, і код Хафмена, застосовуваний для компресії інформації (факсимільний зв'язок, ЕОМ).

Ніяких спеціальних заходів щодо виправлення і виявлення помилок в коді Морзе не передбачається у зв'язку з великою надмірністю самого переданого тексту. У цьому сенсі код Морзе не відноситься до класу коригувальних кодів.

Майже всі блокові коригувальні коди належать до разделімие кодами, в яких кодові комбінації складаються з двох частин: інформаційної та перевірочної. Їх символи завжди займають одні й ті ж позиції, тобто розташовуються на певних місцях. Як правило, в таких кодах, всі кодові комбінації яких містять n символів, перші k символів є інформаційними, а за ними розташовуються (n - k) перевірочних символів. Відповідно до цього разделімие коди отримали умовне позначення - (n, k) - коди.

У нероздільних кодах поділ на інформаційні та перевірочні символи відсутня. До таких кодами відносяться, зокрема, коди з постійною вагою, так звані рівноважні коди. Наприклад, Міжнародним Консультативним Комітетом з телеграфії і телефонії (МККТТ) рекомендований для використання телеграфний код № 3 - семіразрядний код з постійною вагою, тобто з числом одиниць у кожної кодової комбінації, рівним 3 (W = 3).

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

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

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

Несистематичні (нелінійні) коди зазначеними вище властивостями не володіють і застосовуються значно рідше в спеціальних випадках. Прикладом нелінійного коду є вже згадуваний нероздільний, рівноважний код. Ці коди зазвичай використовуються в несиметричних каналах зв'язку, в яких імовірність переходу 1 → 0 значно більше ймовірності переходу 0 → 1 або навпаки. У таких каналах дуже малоймовірно, щоб в одному блоці були переходи обох видів, і тому майже всі помилки призводять до зміни ваги блоку, і, отже, виявляються.

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

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

У систематичних кодах розрізняють два методи формування перевірочної групи символів: поелементний і в цілому.

Найбільш відомі серед систематичних кодів коди Хеммінга, які історично були знайдені раніше багатьох інших кодів і відіграли велику роль у розвитку теорії коригувальних кодів. У цих кодах використовується принцип перевірки на парність певного ряду інформаційних символів.

Перевірочна група з r символів формується поелементно за відповідним алгоритмом. Коди Хеммінга, що мають dmin = 3, дозволяють виправити одну помилку

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

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

Серед циклічних кодів особливе місце займає клас кодів, запропонованих Боуз і Рой-Чоудхурі і незалежно від них хоквінгема. Коди Боуза-Чоудхурі-хоквінгема отримали скорочене найменування БЧХ - коди і відрізняються спеціальним вибором породжує (утворить) циклічний код полінома, що призводить до простою процедурою декодування. [7]

У циклічних кодах "r" перевірочних символів, що додаються до вихідних "k" інформаційним, можуть бути отримані відразу, тобто в цілому, в результаті множення вихідної підлягає передачі кодової комбінації Q (x) простого коду на Одночлен xr і додаванням до цього твору залишку R (x), отриманого в результаті поділу твори на породжує поліном P (x).

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

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

1.4.2 Основні параметри та побудова завадостійких кодів

Проблема підвищення вірності обумовлена ​​не відповідністю між вимогами, що висуваються при передачі даних і якістю реальних каналів зв'язку. У мережах передачі даних потрібно забезпечити вірність не гірше 10-6 - 10-9, а при використанні реальних каналів зв'язку і простого (первинного) коду зазначена вірність не перевищує 10-2 - 10-5.

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

Прості коди характеризуються тим, що для передачі інформації використовуються всі кодові слова (комбінації), кількість яких дорівнює N = qn (q - підстава коду, а n - довжина коду). У загальному випадку вони можуть відрізнятися один від одного одним символом (елементом). Тому навіть один помилково прийнятий символ призводить до заміни одного кодового слова іншим і, отже, до неправильного прийому повідомлення в цілому.

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

Застосування завадостійких кодів для підвищення вірності передачі даних пов'язано з вирішенням завдань кодування і декодування.

Завдання кодування полягає в отриманні при передачі для кожної k - елементної комбінації з безлічі qk відповідного їй кодового слова довжиною n з безлічі qn.

Завдання декодування полягає в отриманні k - елементної комбінації з прийнятого n - розрядного кодового слова при одночасному виявленні або виправлення помилок. [6]

Основні параметри завадостійких кодів

Довжина коду - n;

Довжина інформаційної послідовності - k;

Довжина перевірочної послідовності - r = n - k;

Кодова відстань коду - d 0;

Швидкість коду - R = k / n;

Надмірність коду - R в;

Імовірність виявлення помилки (спотворення) - РОО;

Ймовірність не виявлення помилки (спотворення) - РНО.

Кодова відстань між двома кодовими словами (відстань Хеммінга) - це число позицій, в яких вони відрізняються один від одного.

Кодова відстань коду - це найменша відстань Хеммінга між різними парами кодових слів.

Стиранням називається "втрата" значення переданого символу в деякій позиції кодового слова, яка відома.

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

Побудова завадостійких кодів в основному пов'язано з додаванням до вихідної комбінації (k-символів) контрольних (r-символів) Закодована комбінація буде складати n-символів. Ці коди часто називають (n, k) - коди.

k-число символів у вихідній комбінації

r-число контрольних символів

Розглянемо основні поняття завадостійкого кодування. Двійковий (n, k)-код передбачає правило переходу від комбінації з k інформаційних символів, загальне число яких 2k, до такого ж числа кодових комбінацій завдовжки n (причому n> k), загальне число яких 2n, тобто до введення надмірності (для систематичних кодів надлишкових символів). Для коду існує безліч з 2k дозволених кодових комбінацій завдовжки n, кожна з яких відповідає одній з інформаційних комбінацій. Якщо порівняти пару кодових комбінацій завдовжки n символів, то число двійкових символів в яких вони не збігаються, називають відстанню. Якщо попарно порівняти всі кодові комбінації, мінімальне з отриманих відстаней називають кодовою відстанню d, яке описує здатність коду виправляти або виявляти спотворення в каналі кодових комбінацій.

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

Виправлення помилки виконується за якимось правилом або критерієм вибору дозволеної комбінації, в яку перетворюється прийнята перекручена комбінація (не рівна переданої в канал зв'язку). При декодуванні двійкових алгебраїчних кодів використовується принцип максимуму правдоподібності, в основу якого покладено припущення, що в каналі зв'язку ймовірність помилки більшої кратності менше вірогідності меншою кратності. Тобто якщо в каналі може викривитися один із символів кодової комбінації (кратність помилки t = 1), два символи (t = 2), три символи (t = 3) і т.д., то справедливо для ймовірностей спотворення Р ( t = 1)> Р (t = 2)> Р (t = 3) ... Якщо таке припущення справедливе для використовуваного дискретного каналу, то в декодері, який не знає, що було спотворено в прийнятої кодової комбінації, виправдано ототожнити з переданої комбінацією ту з дозволених комбінацій, яка ближче по відстані від комбінації, що підлягає виправленню. Найближча (знана в меншій кількості символів) дозволена комбінація вважається переданою і оголошується результатом виправлення помилки.

При декодуванні за принципом максимуму правдоподібності справедливе твердження, що код з кодовим відстанню d правильно виправляє число помилок t = [(d-1) / 2], де [a] - менше ціле від а. У той же час ясно, що якщо реальне число викривлених символів в кодовому блоці перевищує величину [(d-1) / 2], то відбудеться невірне виправлення помилки (помилка декодування з імовірністю Рош). Таким чином, код правильно виправляє помилки з кратністю не вище [(d-1) / 2], при цьому число викривлених символів в прийнятої інформаційної послідовності зменшується, і вносить помилки декодування у результаті виправлення помилок з кратністю, що перевищує величину [(d-1 ) / 2], коли число спотворень в інформаційній послідовності збільшується (залишаються спотворення, отримані в каналі зв'язку, і додається невірне виправлення в декодері). Зрозуміло, що якщо в каналі зв'язку число помилок у кодовій послідовності може перевищувати величину [(d-1) / 2] з досить великою ймовірністю, то реалізація режиму виправлення помилок може бути марною або навіть шкідливою.

У реальному каналі зв'язку часто спостерігається групування помилок, коли спотворюється не один двійковий символ, а цілий пакет, довжина якого може перевищувати величину [(d-1) / 2]. Ця обставина є однією з причин, що обмежує широке застосування кодів з виправленням помилок. Для широкого застосування кодів з виправленням помилок такий код в якості одного зі своїх властивостей повинен забезпечувати гарантовану кордон для ймовірності помилки декодування в каналі зв'язку з довільним розподілом потоку помилок в каналі зв'язку.

Зазвичай оцінка ймовірності помилки декодування робиться для q-ічного симетричного каналу при ймовірності спотворення q-ічного символу P _q. У такому каналі з вероятностио 1 - P _{q q-ічний} символ приймається вірно, після його перекручування з ймовірністю Р _q кожне значення q-ічного символу відрізняється від переданого і з'являється на вході декодера з однаковою ймовірністю

P _q / (q-1).

У такому каналі в залежності від кратності помилки t ймовірність помилки декодування

P _ош (t) = 0 при t ≤ (d _РС -1) / 2 = t _РС

P _ош (t) ≤ (q -1) → Σ C _n ^S (q -1) ^S

при d - t _РС ≤ t ≤ d -1

P _ош (t) ≤ (q -1) → Σ C _n ^S (q -1) ^S при t ≥ d (1)

У каналі, а не тільки q-ічним симетричним для коду РС, отримані такі оцінки для t> d - t _P c

1 / (q-1) ^i-2 + 1 / (q-1) ⁱ при t _РС = 1

P (t) ≤ (2)

1 / (q-1) ^i-2t -1 / t! при t _РС ≥ 2

При виправленні t _РС помилок в [9] пропонується оцінка

(3)

Тобто, якщо кратність помилки t перевершує виправляють здатність коду tpc, то в каналі, що не є q-ічним симетричним, ймовірність помилки декодування не залежить від підстави коду q при виправленні tpc помилок і досить близька до одиниці при малих tpc. Але q-ічний симетричний канал не існує в природі, особливо для великих q, властивість равновероятности (q-1) значень спотвореного q-ічного символу для такого каналу досягається застосуванням стохастичного перетворення q-ічних символів каналу. [3]

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

З урахуванням сказаного вище, можна сказати, що теорія алгебраїчного кодування з алгоритмом декодування за принципом максимальної правдоподібності для виправлення незалежних помилок є прикладом того, як помилкова постановка задачі про незалежних помилках в каналі зв'язку зводить практично нанівець праці цілого покоління дослідників.

Для забезпечення застосування кодів, що виправляють помилки, сформулюємо два варіанти постановки задачі. [4]

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

Перша постановка, яка є «м'якої», полягає в тому, що застосовувані коди з виправленням помилок повинні забезпечувати в каналі з природними перешкодами (помилками) подвергаемую кількісній оцінці ймовірність помилки декодування окремо за такими характерним інтервалам кратності помилки:

- Кратність помилки t менше половини величини кодового відстані d, тобто t £ [(d-1) / 2]

- Кратність помилки t менше величини кодового відстані d, тобто t <d

- Кратність помилки t більше величини кодового відстані d, t> d ³

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

З евристичних міркувань сформулюємо властивості завадостійкого коду з виправленням помилок, які дозволили б забезпечити його застосування для захисту інформації в сучасних інформаційних і телекомунікаційних системах у будь-яких з існуючих завданнях застосування. [14]

1. Код має режими виявлення та виправлення помилок з забезпеченням в обох режимах гарантованої (наперед заданої) ймовірності декодування з помилкою в довільному каналі зв'язку та надійним відмовою від декодування при неможливості виправлення помилки.

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

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

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

5. Процедури кодування і декодування коду містять, в основному, операції за модулем 2.

6. Метод кодування повинен мати властивості випадковості сигналів на виході кодера, забезпечують спільне вирішення завдань забезпечення завадостійкості та секретності в постановці К. Шеннона.

1.4.3 Код Шеннона

Оптимальним кодом можна визначити той, в якому кожен двійковий символ буде передавати максимальну інформацію. У силу формул Хартлі та Шеннона максимум ентропії досягається при рівноймовірно події, отже, двійковий код буде оптимальним, якщо в закодованому повідомленні символи 0 і 1 будуть зустрічатися однаково часто. [8]

Розглянемо як приклад оптимальне двійкове кодування букв російського алфавіту разом із символом пробілу «-». Вважаємо, що відомі імовірності появи в повідомленні символів російського алфавіту, наприклад, наведені в таблиці 3.

Таблиця 3.Частота літер російської мови (припущення)

К. Шеннон і Р. Фано незалежно запропонували в 1948-1949 рр.. спосіб побудови коду, заснований на виконанні умови рівної ймовірності символів 0 і 1 у закодованому повідомленні. [10]

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

Для символів першої групи значення першого розряду коду присвоюється рівним «0», для символів другої групи - рівними «1».

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

Приклад кодування символів російського алфавіту наведено в табл. 4

Таблиця 4. Приклад кодування букв російського алфавіту за допомогою коду шеннн-Фано.

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

Разом з тим процедура побудови коду Шеннона-Фано відповідає критерію розрізнення Фано. Код є префіксним і не вимагає спеціального символу, що відокремлює букви один від одного для однозначного нього декодування двійкового повідомлення.

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

Найбільш розроблені ці завдання стосовно до систематичних кодами. Такі коди успішно застосовуються в обчислювальній техніці, різних автоматизованих цифрових пристроях і цифрових системах передачі інформації.

2.Практіческая реалізація задачі кодування

2.1 Приклад до першій теоремі Шеннона

Завдання ефективного кодування описується тріадою:

X = {X 4i 0} - кодує пристрій - В.

Тут Х, В - відповідно вхідний і вихідний алфавіт. Під безліччю х 4i 0 можна розуміти будь-які знаки (літери, слова, речення). В - безліч, число елементів якого у разі кодування знаків числами визначається основою системи числення 2 (наприклад 2, m = 2 2). Кодує пристрій зіставляє кожному повідомленням x 4i 0 з Х кодову комбінацію, складену з n 4i символів безлічі В. Обмеженням даного завдання є відсутність перешкод. Потрібно оцінити мінімальну середню довжину кодової комбінації.

Для вирішення даної задачі має бути відома імовірність P 4i появи повідомлення x 4i 0, якому відповідає певна кількість символів n 4i алфавіту B. Тоді математичне сподівання кількості символів з ​​B визначиться наступним чином: n 4ср = n 4i P 4i (середня величина).

Цьому середній кількості символів алфавіту В відповідає максимальна ентропія H 4max = n 4ср log m. Для забезпечення передачі інформації, що міститься в повідомленнях Х кодовими комбінаціями з В, повинна виконуватися умова H 4max> = H (x) 4, або n 4ср log m> = - P 4i log P 4i. У цьому випадку закодоване повідомлення має надмірність

n 4ср> = H (x) / log m, n 4 min = H (x) / log 4 m.

Коефіцієнт надмірності

Ku = (H 4max - H (x)) / H 4max = (n 4 ср - n 4min) / n 4 СР

Складемо відповідну таблицю. Маємо:

n 4 min = H (x) / log 2 = 2.85, Ku = (2.92 - 2.85) / 2.92 = 0.024,

тобто код практично надмірності не має. Видно, що середня кількість двійкових символів прагне до ентропії джерела повідомлень.

Таблиця 2.1 Приклад до першій теоремі Шеннона

2.2 Приклад побудови коду Шеннона

У таблиці 2.2 наведені проміжні обчислення і результат побудови коду Шеннона. Середня довжина кодових слів l = 2,95. У даному випадку надмірність коду Шеннона на 0,5 біта більше, ніж надмірність коду Хаффмена. З цього малюнка зрозуміло, чому код неефективний. Кодові слова для букв b, d, e, f можуть бути укорочені на 1 біт без втрати властивості однозначної Декодовані.

Таблиця 2.2 Побудова коду Шеннона

Буква	Імовірність pm	Кумулятивна вірогідність qm	Довжина кодо-вого слова lm	Двійковий запис [q] 2	Кодове слово cm
a	0,35	0,00	2	0,00 ...	00
b	0,20	0,35	3	0,0101 ...	010
c	0,15	0,55	3	0,10001 ...	100
d	0,10	0,70	4	0,10110 ...	1011
e	0,10	0,80	4	0,11001 ...	1100
f	0,10	0,90	4	0,11100 ...	1110

Доведемо однозначну Декодовані коду Шеннона. Для цього виберемо повідомлення з номерами i та j, i <j. Кодове слово c _i для i завідомо коротше, ніж слово c _j для j, тому досить довести, що ці слова відрізняються в одному з перших l _i символів.

Розглянемо різницю q _j - q _i = Σ p _k - Σ p _k = Σ p _k ≥ p _i

Згадаймо, що довжина слова і його ймовірність пов'язані співвідношенням

l _i = [- log p _i] ≥ - log p _i.

Тому p _i ≥ 2 ^{- li.}

З урахуванням цієї нерівності

q _j - q _i ≥ 2 ^{- li}

У двійковій запису числа в правій частині ми маємо після коми l _i -1 нулів і одиницю в позиції з номером li. Це означає, що щонайменше в одному з l _i розрядів слова c _i і c _j відрізняються і, отже, c _i не є префіксом для c _j. Оскільки це вірно для будь-якої пари слів, то код є префіксним.

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

l ≤ H +1.

Примітно, що при побудові коду Шеннона ми вибрали довжини кодових слів приблизно рівними (трохи більшими) власної інформації відповідних повідомлень. У результаті середня довжина кодових слів виявилося приблизно рівної (трохи більшої) ентропії ансамблю.

2.3 Приклад Коду Шеннона

Припустимо, потрібно закодувати деяке повідомлення: AABCDAABC

Маємо:

A - 5 5 / 10 = 0.5

B - 2 2 / 10 = 0.2

C - 2 2 / 10 = 0.2

D - 1 1 / 10 = 0.1

Довжина всього повідомлення 10 (Обчислюється веpоятность встpечаемості кожного символу і pасполагают їх у стовпчик у поpядке yбиванія веpоятность)

Після цього ставимо кодові комбінації пpосто методом. Ділимо стовпчик з веpоятность таким обpазмо, щоб сyмма веpоятность веpхняя частини pавнялась пpиблизительно сyмме веpоятность нижньої частини

0.5 - пеpвая частина = 0.5

-----

0.2 \

0.2 | - втоpая частина = 0.5

0.1 /

Напpітів веpоятность веpхняя частини пpоставляем нyлі, напpотив нижньої - одиниці. У нашому пpимеp полyчім.

0.5 0

0.2 1

0.2 1

0.1 1

Пpделиваем потім те саме з pазделение частинами. В кінці-кінців пpідем до томy, що ділити більше нічого.

А 0.5 0

B 0.2 10

C 0.2 110

D 0.1 111

Разом - AABCDAABC = 0 0 10 110 111 0 0 10 110

Пpичем закодіpованное повідомлення (це видно) не може бути pаскодіpовано декількома способами, хоча довжина кодів символів відрізняється. Щоб прочитав закодіpованное повідомлення стpоя бінаpное деpево. У нашому слyчае воно бyдет таке.

()

/ \

0 (A) 1

/ \

0 (B) 1

/ \

0 (C) 1 (D)

Ось ще пpимеp складання кодових комбінацій по веpоятносям:

0.3 00

0.25 01

--------------- (Пеpвое розподіл)

0.1 100

0.1 101

------------- (Втоpое розподіл)

0.1 1100

0.05 1101

----------- (Тpетьем розподіл)

0.05 1110

0.05 1111

2.4 Приклад кодування і декодування методом Шеннона-Фано

За допомогою табл. 4 можна закодувати і декодувати будь-яке повідомлення. У вигляді прикладу запишемо двійковим кодом фразу: "Теорія інформацій"

0 111 010000 11 01 000 11 011 11 0000

01101000111111 111 00110 100

11 0000 1011 1111 10101100110

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

10011100110011001001111010000

1011100111001001101010000110101

010110000110110110

Результат декодування - фраза "спосіб кодування". При такому кодуванні будь-яка помилка (випадкове перепутиваніе знаків 0 і 1) згубна, тому що декодування всього наступного за помилкою тексту стає неможливим. Тому даний принцип кодування використовується тоді, коли помилки при кодування і передачі повідомлення виключені.

Висновок

В ході курсової роботи було розглянуто завдання кодування, яка включає в себе:

1.Забезпечення економічності передачі інформації за допомогою усунення надмірності.

2. Забезпечення надійності (завадостійкості) передачі інформації

3.Узгодження швидкості передачі інформації з пропускною спроможністю каналу

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

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

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

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