Методичні вказівки для виконання контрольних робіт з дисципліни “Теорія інформації і кодування”

Державний економіко-технологічний університет транспорту

Факультет “Інфраструктура рухомого складу і зв’язку ”

Кафедра “Телекомунікаційні технології і автоматика”

МЕТОДИЧНІ ВКАЗІВКИ

для виконання контрольних робіт

з дисципліни “Теорія інформації і кодування”

Київ 2013

Зміст вміст

1 КІЛЬКІСНА ОЦІНКА ІНФОРМАЦІЇ 

2. УМОВНА ЕНТРОПІЯ І ЕНТРОПІЯ ОБ'ЄДНАННЯ

3. ОБЧИСЛЕННЯ ІНФОРМАЦІЙНИХ ВТРАТ ПРИ ПЕРЕДАЧІ

ПОВІДОМЛЕНЬ ПО КАНАЛАХ ЗВ'ЯЗКУ З ШУМАМИ

4. ВИЗНАЧЕННЯ НАДМІРНОСТІ ПОВІДОМЛЕНЬ.

ОПТИМАЛЬНЕ КОДУВАННЯ

5. ВИЯВЛЕННЯ І ВИПРАВЛЕННЯ ПОМИЛОК В ПОВІДОМЛЕННЯХ

5.1. Поняття про ідею корекції помилок

5.2. Лінійні групові коди

5.3. Тривіальні систематичні коди. Код Хеммінга

5.4. Циклічні коди

5.5. Побудова і декодування конкретних циклічних код

6. УЩІЛЬНЕННЯ ІНФОРМАЦІЇ

7. ВАРІАНТИ КОНТРОЛЬНОЇ РОБОТИ

8. ОСНОВНІ ВИМОГИ ДО ОФОРМЛЕННЯ КОНТРОЛЬНОЇ РОБОТИ

9. ПИТАННЯ до заліку

10. ЛІТЕРАТУРА

Застосування I

ДОДАТОК


1 КІЛЬКІСНА ОЦІНКА ІНФОРМАЦІЇ

Загальне число повідомлень, що не повторюються, яке може бути складене з алфавіту m шляхом комбінування по n символів в повідомленні

. (1)

Невизначеність, що припадає на символ первинного (кодованого) алфавіту, складеного з рівноймовірних і взаємнонезалежих символів

. (2)

Логарифм впливає лише на зручність обчислення. У разі оцінки ентропії:

а) у двійкових одиницях

б) у десяткових одиницях

де ;

в) у натуральних одиницях

де

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

(3)

Для випадків рівноймовірних і взаємонезалежних символів первинного алфавіту кількість інформації в к повідомленнях алфавіту m рівно

Для нерівно ймовірних алфавітів ентропія на символ алфавіту

(4)

а кількість інформації в повідомленні, складеному з к нерівноймовірних символів

(5)

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

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

(6)

де lсер– середня довжина кодових слів вторинного алфавіту.

Для рівномірних кодів (всі комбінації коду містять однакову кількість розрядів)

де n – довжина коду (число елементарних посилок в коді). Згідно до (3), об'єм дорівнює кількості інформації, якщо lсер=Н, тобто у разі максимального інформа-ційного навантаження на символ повідомлення. У решті всіх випадків .

Наприклад, якщо кодувати в коді Бодо деякий рівноймовірний алфавіт, що складається з 32 символів, то

Якщо закодувати в коді Бодо російський 32-буквений алфавіт, то без урахування кореляції між буквами|літерами| кількість інформації

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

Завдання 1.1: Припустимо, є набір з 3-х букв А, В, С.

1) Скласти максимальну кількість повідомлень, комбінуючи по дві букви в повідомленні.

2) Яка кількість інформації припадає на одне таке повідомлення?

Розв’язок:

1) АА, ВА, СА, АВ, ВВ, СВ, АС, ВС, СС;

2) ; .

Завдання 1.2: Символи алфавіту володіють двома якісними ознаками (m = 2, символів первинного алфавіту).

1) Яку кількість повідомлень можна отримати, комбінуючи по 3, 4, 5 і 6 елементів в повідомленнях?

2) Яка кількість інформації доводиться на ці повідомлення?

Розв’язок:

1) ; ;

2)

2. УМОВНА ЕНТРОПІЯ І ЕНТРОПІЯ ОБ'ЄДНАННЯ

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

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

Якщо при передачі n повідомлень символ А з'явився m разів, символ В з'явився l разів, а символ А разом з символом В – до к разів, то ймовірність появи символу А ; ймовірність появи символу В ; ймовірність сумісної появи символів А і В ; умовна ймовірність появи символу А щодо символу В і умовна ймовірність появи символу В щодо символу А

(7)

Якщо відома умовна ймовірність, то можна легко визначити і ймовірність сумісної появи символів А і В, використовуючи вирази (7)

(8)

Від класичного виразу (4) формула умовної ентропії відрізняється тим, що ймовірності в ній ймовірності - умовні:

(9)

(10)

де індекс i вибраний для характеристики довільного стану джерела повідомлення А, індекс j вибраний для характеристики довільного стану адресата В.

Розрізняють поняття частинної і загальної|спільної| умовної ентропії. Вирази (9) і (10) є частинними умовними ентропіями.

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

(11)

Вираз (11) є загальним виразом для визначення кількості інформації на один символ повідомлення для випадку нерівномірних і взаємонезалежних| символів.

Оскільки є ймовірністюймовірністю сумісної появи двох подій, то формулу (11) можна записати таким чином:

(12)

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

У загальному випадку, якщо ми передаємо m сигналів А і чекаємо отримати m сигналів В, вплив завад в каналі зв'язку повністю описується канальною матри-цею, яку ми наводимо нижче:

В

А

b1 b2 … bj … bm

а1

а2

ai

am

….…………………………………………………………

............................................................................................

…,

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

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

(13)

Сума ймовірностей розподілу (13) завжди рівна 1.

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

. (14)

Підсумовування проводиться по j, оскільки i-ий стан (у даному випадки перший) залишається сталим.

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

(15)

(на m ділимо, оскільки ентропія є невизначеність на один символ).

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

. (16)

Оскільки

то для обчислення загальної умовної ентропії нарівні з виразом (16) може бути використане наступний вираз

(17)

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

В

А

b1 b2 … bj … bm

а1

а2

ai

am

….…………………………………………………………

............................................................................................

В цьому випадку одиниці повинні дорівнювати сумі умовної ймовірності не по рядках, а по стовпцях канальної матриці

.

Частинна умовна ентропія

(18)

а загальна умовна ентропія

(19)

Якщо задані канальна матриця виду (частинна умовна ентропія в цьому випадку відповідає (14)) і безумовна ймовірність виду , то безумовну ймовірність приймача знаходимо як , тобто, якщо задані безумовна ймовірність джерела і канальна матриця, то може бути обчислена ентропія приймача

і навпаки, якщо задані ймовірність виду і канальна матриця, що описує канал зв'язку з боку приймача повідомлень (приватна умовна ентропія при цьому відповідає виразу (17)), то а значить може бути визначена ентропія джерела повідомлень

Ентропія об'єднання використовується для обчислення ентропії сумісної появи статистичних залежних повідомлень. Наприклад, передаючи сто разів цифру 5 по каналу зв'язку з перешкодами, відмітимо, що цифра 5 була прийнята 90 разів, цифра 6 – 8 разів і цифра 4 – 2 рази. Невизначеність виникнення комбінацій вигляду 5 – 4, 5 – 5, 5 – 6 при передачі цифри 5 може бути описана за допомогою ентропії об'єднання. - невизначеність того, що буде послане А, а прийняте В. Для ансамблів переданих повідомлень А і прийнятих повідомлень В ентропія об'єднання є сумою вигляду

(20)

Ентропія об'єднання і умовна ентропія зв'язані між собою наступними спів-відношеннями:

Ентропія об'єднання може бути підрахована за допомогою матриці вигляду

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

, (21)

. (22)

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

Умовні ймовірність виду і обчислюються як

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

Завдання 2.1: В результаті статистичних випробувань встановлено, що при передачі кожних 100 повідомлень завдовжки по 5 символів в повідомленні символ К зустрічається 50 разів, а символ Т – 30 разів. Разом з символом К символ Т зустрічається 10 разів. Визначити умовні ентропії Н(К/Т) і Н(Т/К).

Розв’язокозв'язанн|:

Загальна кількість переданих символів

Ймовірність появи символу К

Ймовірність появи символу Т

Ймовірність сумісної появи символу К і Т

Оскільки , то умовна ймовірність появи символу К відносно Т

Умовна ймовірність появи символу Т відносно символу К

Умовна ентропія символу К відносно Т

Умовна ентропія появи символу Т відносно К

3. ОБЧИСЛЕННЯ ІНФОРМАЦІЙНИХ ВТРАТ ПРИ ПЕРЕДАЧІ ПОВІДОМЛЕНЬ КАНАЛАМИ ЗВ'ЯЗКУ З ШУМАМИ

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

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

(23)

Оскільки У цьому випадку кількість інформації, що міститься в прийнятому ансамблі повідомлень В, дорівнює ентропії передаваних повідомлень ансамблю А, тобто I(В, А)= Н (А).

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

оскільки тобто умовна ентропія рівна безумовній, а кількість інформації, що міститься у В, відносно А дорівнює нулю:

.

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

.

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

(24)

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

(25)

а з використанням умовної ентропії

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

(26)

(27)

(28)

Для обчислення|підрахунку| часто зручно застосовувати вирази (26-28) у вигляді|виді|

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

Знаючи умовну і безумовну вірогідність, можна знайти Н(А), Н(В), Н(А/В) і Н(В/А).

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

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

Розв’язок:

Канальна матриця має вигляд|вид|

.

або

або

4. ВИЗНАЧЕННЯ НАДМІРНОСТІ ПОВІДОМЛЕНЬ. ОПТИМАЛЬНЕ КОДУВАННЯ

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

Для визначення кількості «зайвої» інформації, яка закладена в структурі алфавіту або в природі коду, вводиться поняття надмірності. Надмірність, з якою ми маємо справу в теорії інформації, не залежить від змісту повідомлення і зазвичай заздалегідь відома із статистичних даних. Інформаційна надмірність показує відносну недогруженность на символ алфавіту і є безрозмірною величиною:

(29)

де — коефіцієнт ущільнення|стиснення| (відносна ентропія), Н та Ні обчислюються щодо|відносно| одного і того ж алфавіту.

Окрім|крім| загального|спільного| поняття надмірності існують частинні види надмірності.

Надмірність, обумовлена нерівноймовірним розподілом символів в повідомленні

(30)

Надмірність, викликана|спричиняти| статистичним зв'язком між символами| повідомлення

(31)

Повна|цілковита| інформаційна надмірність

(32)

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

Так при передачі десяткових цифр двійковим кодом максимально завантаженими бувають тільки|лише| ті символи вторинного|повторного| алфавіту, які передають значення, що є|з'являються| цілочисельними ступенями|мірами| двійки. У решті випадків тією ж кількістю символів може бути передане|передавати| більша кількість цифр (повідомлень). Наприклад, трьома двійковими розрядами ми можемо передати|передавати| і цифру 5, і цифру 8, тобто на передачу п'яти повідомлень витрачається стільки ж символів, скільки витрачається і на вісім повідомлень.

Фактично для передачі повідомлення досить мати довжину кодової комбінації

,

де N - загальна кількість передаваних повідомлень.

L можна представити і як

,

де і —соответственно| якісні ознаки первинного і вторинного|повторного| алфавітів. Тому для цифри 5 в двійковому коді можна записати

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

де к - закруглене до найближчого цілого числа значення. Для нашого прикладу|зразка|

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

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

Найбільш ефективним способом зменшення надмірності повідомлення є|з'являється| побудова|шикування| оптимальних кодів.

Оптимальні коди - коди з практично нульовою надмірністю. Оптимальні коди мають мінімальну середню довжину кодових слів - L. Верхня і нижня межі L визначаються з нерівності

(33)

де Н - ентропія первинного алфавіту, m - число якісних ознак вторинного алфавіту.

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

Загальний|спільний| вираз|вираження| середнього числа елементарних символів на букву|літеру| повідомлення при блоковому|блочному| кодуванні

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

Суть блокового|блочного| кодування можна з'ясувати на прикладі|зразку| представлення десяткових цифр в двійковому коді. Так, при передачі цифри 9 в двійковому коді необхідно витратити 4 символи, тобто 1001. Для передачі цифри 99 при побуквенном| кодуванні - 8, при поблочному - 7, оскільки|тому що| 7 двійкових знаків достатні для передачі будь-якої цифри від 0 до 123; при передачі цифри 999 співвідношення буде 12 - 10, при передачі цифри 9999 співвідношення буде 16 - 13 і так далі В загальному|спільному| випадку «вигода» блокового|блочного| кодування виходить і за рахунок того, що в блоках відбувається|походить| вирівнювання вірогідності|ймовірності| окремих символів, що веде до підвищення інформаційного навантаження на символ.

При побудові|шикуванні| оптимальних кодів найбільше розповсюдження|поширення| знайшли методики Шенона - Фано і Хаффмена.

Згідно|згідно з| методиці Шенона - Фано побудова|шикування| оптимального коду ансамблю з|із| повідомлень зводиться до наступного|слідуючої|:

1-й крок. Множина|безліч| з|із| повідомлень розташовується в порядку убування вірогідності|ймовірності|.

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

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

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

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

Згідно методиці Хаффмена, для побудови оптимального коду символів первинного алфавіту виписуються в порядку спадання вірогідності. Останні

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

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

Максимально ефективними будуть ті ОНК, у|біля| яких

Для двійкових кодів

(36)

оскільки log22 = 1. Очевидно, що рівність (36) задовольняється за умови, що довжина коду у вторинному алфавіті

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

Ефективність ОНК оцінюють за допомогою коефіцієнта статистичного ущільнення|стиснення|:

(37)

який характеризує зменшення кількості двійкових знаків на символ повідомлення при застосуванні|вживанні| ОНК в порівнянні із застосуванням|вживанням| методів нестатистичного кодування і коефіцієнта відносної ефективності

(38)

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

Для найбільш загального|спільного| випадку нерівноімовірних і взаимонезависимых| символів

Для випадку нерівноімовірних і взаємозалежних символів

Завдання 4.1 : Повідомлення складається з алфавіту а, b, з, d. Ймовірність появи букв алфавіту в текстах рівна відповідно: Знайти надмірність повідомлень, складених з даного алфавіту.

Розв’язок:

Надмірність, згідно (29)

Для алфавіту з|із| чотирьох букв|літер| максимальна ентропія

Середня ентропія на символ повідомлення

Тоді надмірність

Завдання 4.2: Побудувати оптимальний код повідомлення, в якому ймовірність появи букв первинного алфавіту, що складається з 8 символів, є цілим від’ємним ступенем двійки, а .

Рішення: Побудова оптимального коду ведеться за методикою Шеннона-фано. Результати побудови відбіті в таблиці:

Буква

Імовірність

появи букви

Кодове слово

Число знаків в кодовому слові

А1

А2

А3

А4

А5

А6

А7

А8

1/4

1/4

1/8

1/8

1/16

1/16

1/16

1/16

00

01

100

101

1100

1101

1110

1111

2

2

3

3

4

4

4

4

0,5

0,5

0,375

0,375

0,25

0,25

0,25

0,25

Перевірка:

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

5. ВИЯВЛЕННЯ І ВИПРАВЛЕННЯ ПОМИЛОК В ПОВІДОМЛЕННЯХ

5.1. Поняття про ідею корекції помилок

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

10110 - передана|передавати| кодова комбінація;

10010 - 1-я прийнята комбінація;

10100 - 2-я прийнята комбінація;

00110 - 3-я прийнята комбінація;

10110 - накопичена комбінація.

Як видимий, не дивлячись на те, що у всіх трьох прийнятих комбінаціях були помилки, накопичена не містить помилок.

Прийняте повідомлення може також складатися з коди і його інверсії. Код і інверсія посилаються в канал зв'язку як одне ціле. Помилка на приймальному|усиновленому| кінці виділяється при зіставленні коди і його інверсії.

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

(39)

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

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

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

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

У загальному випадку для виявлення r помилок мінімальна кодова відстань

(40)

Мінімальна кодова відстань, необхідна для одночасного виявлення і виправлення помилок

(41)

де s - число помилок, що виправляються.

Для код, що тільки|лише| виправляють помилки

(42)

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

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

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

Для виявлення і виправлення одиночної помилки співвідношення між числом інформаційних розрядів і числом розрядів, що коректують, повинно задовольняти наступним|слідуючим| умовам:

(43)

(44)

при цьому мається на увазі, що загальна|спільна| довжина кодової комбінації

. (45)

Для практичних розрахунків при визначенні числа контрольних розрядів код з|із| мінімальною кодовою відстанню зручно користуватися виразами:

(46)

якщо відома довжина повної кодової комбінації п, і

(47)

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

Для кодів, що виявляють всі триразові|трикратні| помилки

(48)

або

(49)

Для кодів завдовжки в п символів, що виправляють одну або дві помилки

(50)

Для практичних розрахунків можна користуватися виразом|вираженням|

(51)

Для кодів, що виправляють 3 помилки

(52)

Для кодів, виправляючих s помилок

(53)

Вираз зліва відомий як нижня межа Хеммінга, а вираз справа - як верхня межа Варшамова - Гильберта.

Для наближених розрахунків можна користуватися виразом|вираженням|

(54)

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

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

Рішення|розв'язання|:

при n = 6, 192 + 32 > 64;

при n = 7, 224 + 32 > 128;

при n = 8, 288 + 32 >256;

при n = 9, 288 + 32 < 512

тобто n = 9.

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

Рішення|розв'язання|:

1)

2)

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

Рішення|розв'язання|:

при n = 12;

при n = 13;

при n = 14;

при n = 15;

тобто n = 15.

Завдання 6.4: Визначити кількість розрядів, що коректують, для побудови коди, що виявляє всі триразові помилки, якщо допустима довжина коди n=15.

Рішення|розв'язання|:

5.2. Лінійні групові коди

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

Для двійкових код як лінійна операція використовують складання по модулю 2.

Правила складання по модулю 2 визначаються наступною|слідуючою| рівністю:

Послідовність нулів і одиниць, що належать даному коду, називатимемо кодовим вектором.

Властивість лінійних код: сума (різниця) кодових векторів лінійної коди дає вектор, що належить даному коду.

Лінійні коди утворюють групу алгебри по відношенню до операції складання по модулю 2. У цьому сенсі вони є груповими кодами.

Властивість групової коди: мінімальна кодова відстань між кодовими векторами групової коди дорівнює мінімальній вазі ненульових кодових векторів.

Вага кодового вектора (кодовій комбінації) дорівнює числу його ненульових компонентів.

Відстань між двома кодовими векторами дорівнює вазі вектора, отриманого в результаті складання початкових векторів по модулю 2. Таким чином, для даної групової коди

.

Групові коди зручно задавати матрицями, розмірність яких визначається параметрами коди і . Число рядків матриці рівне число стовпців рівне +=:

(55)

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

Матриця, що породжує, З може бути представлена двома матрицями І і П (інформаційною і перевірочною). Число стовпців матриці П рівне число стовпців матриці І рівно :

(56)

Теорією і практикою встановлено, що за матрицю І зручно брати одиничну матрицю в канонічній формі:

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

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

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

званому лівою канонічною формою матриці, що породжує.

Для код з =2 матриця, що проводить, З має вигляд

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

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

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

Для код з співвідношення п і . наступні: (3; 1), (7;4), (15; 11), (31; 26), (63; 57) і так далі

Щільно упаковані коди, оптимальні з погляду мінімуму надмірних символів, виявляють максимально можливу кількість варіантів помилок кратністю r + 1; r + 2 і так далі і були досліджені Д. Слепяном. Для отримання цих код матриця П повинна мати комбінації з максимальною вагою. Для цього при побудові код з послідовно використовуються вектори довжиною пвагою . Тими ж Слепяном були досліджені нещільно упаковані коди з малою щільністю перевірок на парність. Ці коди економні з погляду простоти апаратури і містять мінімальне число одиниць в розрядах матриці, що породжує, що коректують. При побудові код з максимально простими шифраторами і дешифраторами послідовно вибираються вектори вагою = 2, 3 ..., . Якщо число комбінацій, що є розрядами коди, що коректують, і що задовольняють умові _

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

Алгоритм утворення перевірочних символів по відомій інформаційній частині|частці| коди може бути записаний таким чином:

(57)

В процесі декодування здійснюються перевірки, ідея яких в загальному|спільному| вигляді|виді| може бути представлена|уявляти| таким чином:

(58)

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

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

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

.

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

Процедура виправлення помилок в процесі декодування групових код зводиться до наступного|слідуючого|.

Будується кодова таблиця. У першому рядку таблиці розташовуються всі кодові вектори . У першому стовпці другого рядка розміщується вектор вага якого дорівнює 1.

Решта позицій другого рядка заповнюється векторами, отриманими в результаті підсумовування по модулю 2 вектори з вектором розташованим у відповідному стовпці першого рядка. У першому стовпці третього рядка записується вектор вага якого також дорівнює 1, проте, якщо вектор містить одиницю в першому розряді, то - у другому. У решту позицій третього рядка записують суми і .

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

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

Таблиця 6.2.1

A

e

...

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

Вектори не мають дорівнювати жодному з векторів, інакше в таблиці з'явилися|появлялися| б нульові вектори.

Завдання 6.5: Визначити мінімальну кодову відстань між двійковими векторами: 1100011; 1001111; 1010101.

Рішення|розв'язання|:

Таким чином

Завдання 6.6: Визначити здібності наступної коди, що коректують: 001; 010; 111.

Рішення|розв'язання|:

1) 2)

3) 4)

Код здатний|здібний| виявляти тільки|лише| одиночну помилку.

Завдання 6.7: Джерело передає повідомлення за допомогою 15 двійкових комбінацій. Скласти інформаційну //И// і перевірочну //П// матриці так, щоб повна матриця С=//іп//, що проводить, могла проводити груповий код, що коректує одиночні збої.

Рішення|розв'язання|:

оскільки|тому що| повинно бути більше або рівне 15;

5.3. Тривіальні систематичні коди. Код Хеммінга

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

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

Код Хеммінга є типовим прикладом систематичної коди. Проте при його побудові до матриць зазвичай не удаються. Для обчислення основних параметрів коди задається або кількість інформаційних символів, або кількість інформаційних комбінацій . При допомозі (43) і (44) обчислюються і . Співвідношення між для коди Хеммінга представлені в таблиці. 1 застосування I. Знаючи основні параметри коди, що коректує, визначають, які позиції сигналів будуть робочими, а які контрольними. Як показала практика, номери контрольних символів зручно вибирати згідно із законом де і так далі - натуральний ряд чисел. Номери контрольних символів в цьому випадку будуть відповідно: 1, 2, 4, 8, 16, 32 і так далі

Потім визначають значення контрольних коефіцієнтів (0 або 1), керуючись наступним правилом: сума одиниць на контрольних позиціях має бути парною. Якщо ця сума парна, то значення контрольного коефіцієнта - 0, інакше - 1.

Перевірочні позиції вибираються таким чином: складається таблиця для ряду|лави| натуральних чисел в двійковому коді. Число рядків таблиці

Першому рядку відповідає перевірочний коефіцієнт, другий і так далі, як показано в таблиці. 2 застосування 8. Потім виявляють перевірочні позиції, виписуючи коефіцієнти за наступним|слідуючим| принципом: у першу перевірку входять коефіцієнти, які містять|утримують| в молодшому розряді 1, тобто і т. д.; в другу - коефіцієнти, що містять|утримують| 1 в другому розряді, тобто і т.д.; в третю перевірку - коефіцієнти, які містять|утримують| 1 в третьому розряді, і так далі Номери перевірочних коефіцієнтів відповідають номерам перевірочних позицій, що дозволяє скласти загальну|спільну| таблицю перевірок (таблиця. 2, застосування I). Старшинство розрядів вважається|лічить| зліва направо, а при перевірці зверху вниз. Порядок|лад| перевірок показує також порядок|лад| проходження|дотримання| розрядів в отриманому|одержувати| двійковому коді.

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

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

5.4. Циклічні коди

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

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

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

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

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

Значення розрядів, що коректують, знаходять|находять| по результату від ділення|поділу| на :

або

Таким чином

або в загальному|спільному| вигляді|виді|

(59)

де - приватне, а - залишок від ділення на .

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

Таким чином, вираз|вираження| (59) можна записати як

(60)

що у разі|в разі| нашого прикладу|зразка| дасть

або

Многочлен 1101001 і є шукана комбінація, де 1101 - інформаційна частина|частка|, а 001 - контрольні символи. Відмітимо|помітимо|, що шукану комбінацію ми отримали|одержували| б і як в результаті|унаслідок| множення однієї з комбінацій повної|цілковитої| чотиризначної двійкової коди (в даному випадку 1111) на створюючий многочлен, так і множенням заданої комбінації на одночлен, що має той же ступінь|міру|, що і вибраний створюючий многочлен (у нашому випадку таким чином була отримана|одержувати| комбінація 1101000) з|із| подальшим|наступним| додаванням|добавляти| до отриманого|одержувати| твору|добутку| залишку|остачі| від ділення|поділу| цього твору|добутку| на створюючий многочлен (у нашому прикладі|зразку| залишок|остача| мав вигляд|вид| 001).

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

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

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

Циклічне зрушення кодової комбінації аналогічне множенню відповідного многочлена на х:

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

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

Проте мало побудувати циклічний код. Треба уміти виділити з нього можливі помилкові розряди, тобто ввести деякі пізнавачі помилок, які виділяли б помилковий блок зі всіх інших. Оскільки циклічні коди - блокові, то кожен блок повинен мати свій пізнавач. І тут вирішальну роль грають властивості створюючого многочлена . Методика побудови циклічної коди така, що створюючий многочлен бере участь в утворенні кожної кодової комбінації, тому будь-який многочлен циклічної коди ділиться на створюючий без залишку. Але без залишку діляться тільки ті многочлени, які належать даному коду, тобто створюючий многочлен дозволяє вибрати дозволені комбінації зі всіх можливих. Якщо ж при діленні циклічної коди на створюючий многочлен буде отриманий залишок, то означає або в коді відбулася помилка, або це комбінація якогось іншої коди (заборонена комбінація), що для декодуючого пристрою не має принципової різниці. По залишку і виявляється наявність забороненої комбінації, тобто виявляється помилка. Залишки від ділення многочленів є пізнавачами помилок циклічних кодів.

З іншого боку, залишки від ділення|поділу| одиниці з|із| нулями|нуль-індикаторами| на створюючий многочлен використовуються для побудови|шикування| циклічних код (можливість|спроможність| цього видно|показний| з|із| виразу|вираження| (60)).

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

починаючи|розпочинати| з|із| восьмого, залишки повторюватимуться.

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

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

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

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

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

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

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

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

(61)

де - число інформаційних розрядів коди.

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

(62)

де - довжина кодової комбінації.

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

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

Ідея виправлення помилок базується на тому, що помилкова комбінація після|потім| певного числа циклічних зрушень|зсувів| “ підганяється|припасовує| ” під залишок|остачу| таким чином, що в сумі із|із| залишком|остачею| вона дає виправлену комбінацію. Залишок|остача| при цьому є не що інше, як різницю між спотвореними і правильними символами, одиниці в залишку|остачі| стоять якраз на місцях|місце-милях| спотворених розрядів в підігнаній|припасовувати| циклічними зрушеннями|зсувами| комбінації. Підганяють|припасовують| спотворену комбінацію до тих пір, поки число одиниць в залишку|остачі| не дорівнюватиме числу помилок в коді. При цьому, природно, число одиниць може бути або дорівнює числу помилок, що виправляються даним кодом (код виправляє 3 помилки і в спотвореній комбінації 3 помилки), або менше s (код виправляє 3 помилки, а в прийнятій комбінації - 1 помилка).

Місце|місце-миля| помилки в кодовій комбінації не має значення. Якщо те після|потім| певної кількості зрушень|зсувів| всі помилки опиняться в зоні “разової” дії створюючого многочлена, тобто досить отримати|одержувати| один залишок|остачу|, вага якого, і це вже буде досить для виправлення спотвореної комбінації. У цьому сенсі|змісті| коди БЧХ (про них ми говоритимемо нижче) можуть виправляти пачки помилок, аби довжина пачки не перевищувала s.

5.5. Побудова|шикування| і декодування конкретних циклічних код

Коди, що виправляють одиночну помилку .

1. Розрахунок співвідношення між контрольними і інформаційними символами коди проводиться на підставі виразів (43) - (53).

Якщо задано число інформаційних розрядів, то число контрольних розрядів знаходимо|находимо| з|із| виразу|вираження|

Загальне|спільне| число символів коди

Якщо задана довжина коди, то число контрольних розрядів

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

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

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

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

4. Визначення елементів додаткової матриці проводиться по залишках від ділення останнього рядка транспонованої матриці (одиниці з нулями) на створюючий многочлен. Отримані залишки повинні задовольняти наступним вимогам:

а) число розрядів кожного залишку|остачі| має дорівнювати числу контрольних символів, отже, число розрядів додаткової матриці має дорівнювати ступеню|мірі| створюючого многочлена;

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

в) число одиниць кожного залишку|остачі|, тобто його вага, має бути не менше величини, де - мінімальна кодова відстань, не менша числа помилок, що виявляються;

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

5. Матриця твірної складається дописуванням елементів додаткової матриці праворуч від одиничної транспонованої матриці або множенням елементів одиничної матриці на створюючий многочлен.

6. Комбінаціями шуканої коди є рядки створюючої матриці і всі можливі суми по модулю 2 різних поєднань рядків створюючої матриці.

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

а) прийняту комбінацію ділять на створюючий многочлен і

б) підраховують|підсумовують| кількість одиниць в залишку|остачі| (вага залишку|остачі|).

Якщо де s - допустиме число що виправляються даним кодом помилок, то прийняту комбінацію складають по модулю 2 з отриманим залишком. Сума дасть виправлену комбінацію. Якщо то

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

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

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

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

Коди, що виявляють триразові|трикратні| помилки .

Вибір числа розрядів, що коректують, проводиться із співвідношення

або

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

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

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

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

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

Приклад: Початкова кодова комбінація - 0101111000, прийнята - 0001011001 (тобто відбувся потрійний збій). Показати процес виявлення помилки, якщо відомо, що комбінації коди були утворені за допомогою многочлена 101111.

Рішення|розв'язання|:

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

III. Циклічні коди, що виправляють дві і більша кількість помилок

Методика побудови|шикування| циклічних код з|із| відрізняється від методики побудови|шикування| циклічних код з|із| тільки|лише| у виборі створюючого многочлена. У літературі ці коди відомі як коди БЧХ (перші букви|літери| прізвищ Боуз, Чоудхурі, Хоквінхем - авторів методики побудови|шикування| циклічних код з|із| ).

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

Для виправлення числа помилок ще не достатньо|досить| умови, щоб|аби| між комбінаціями коди мінімальна кодова відстань . необхідно також, щоб|аби| довжина коди задовольняла умові

(63)

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

(64)

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

(65)

де є одним із співмножників, на які розкладається число п.

Співвідношення між З і h можуть бути зведені в наступну таблицю

п/п

h

C

1

2

3

4

5

6

7

8

9

10

3

4

5

6

7

8

9

10

11

12

7

15

31

63

127

255

511

1023

2047

4095

1

5; 3

1

7; 3; 3

1

17; 5; 3

7; 3; 7

31; 11; 3

89; 23

3; 3; 5; 7; 13

Наприклад, при h = 10 довжина кодової комбінації може бути рівна і 1023 і 341 (З = 3), і 33 (З =31), і 31 (З = 33), зрозуміло, що п не може бути менше Величина З впливає на вибір порядкових номерів мінімальних многочленів, оскільки індекси спочатку вибраних многочленів умножаються на С.

Побудова створюючого многочлена проводиться за допомогою так званих мінімальних многочленів які є простими многочленами, що не приводяться. Створюючим многочленом є твір непарних мінімальних многочленів і є їх найменшим загальним кратним (НОК). Максимальний порядок визначає номер останнього з вибираних табличних мінімальних многочленів

(66)

Порядок многочлена використовується при визначенні числа співмножників . Наприклад, якщо s = 6, то . Оскільки для побудови використовуються тільки непарні многочлени, то ними будуть: старший з них має порядок . Як видимий, число співмножників рівне 6, тобто числу помилок, що виправляються. Таким чином, число мінімальних многочленів, що беруть участь в побудові створюючого многочлена

(67)

а старший ступінь|міра|

(68)

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

Ступінь|міра| створюючого многочлена, отриманого|одержувати| в результаті перемножування вибраних мінімальних многочленів

(69)

У загальному|спільному| вигляді|виді|

(70)

Декодування кодів БЧХ проводиться за тією ж методикою, що і декодування циклічних кодів|із| з . Проте|однак| у зв'язку з тим, що практично всі коди БЧХ представлені|уявляти| комбінаціями з|із|, можуть виникнути вельми|дуже| складні варіанти, коли для виявлення і виправлення помилок необхідно проводити велике число циклічних зрушень|зсувів|. В цьому випадку для полегшення можна комбінацію, отриману|одержувати| після|потім| -кратного| зрушення|зсуву| і підсумовування із|із| залишком|остачею|, зрушувати|зсовувати| не управо|вправо|, а вліво на циклічних зрушень|зсувів|. Це доцільно робіти|чинити| тільки|лише| при .

6. УЩІЛЬНЕННЯ|стиснення| ІНФОРМАЦІЇ

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

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

Ущільнення інформації діленням коду на частини, менші деякої наперед заданої величини А, полягає в тому, що початковий код ділиться на частини, менші А, після чого отримані частини коду складаються між собою або за правилами двійкової арифметики, або по модулю 2. Наприклад, початковий код 101011010110; A = 4

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

Припустимо, початкове слово «газета» кодується кодом, в якому довжина кодової комбінації букви l = 8:

Грам - 01000111; а - 11110000; з - 01100011; е - 00010111; т - 11011000.

Повний|цілковитий| код слова «Газета»

010001111111000001100011000101111101100011110000.

Ущільнення|стиснення| здійснюється складанням за модулем 2 двійкових кодів букв|літер| стискуваного|стискати| слова з|із| побуквенным| зрушенням|зсувом| в кожному розряді.

nмакс

k

l

0

L

Двійкові знаки

а)

n

k

0

L

Двійкові знаки

б)

k

k

k+1

k+2

рис.1

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

(71)

де - максимально допустима довжина (кількість двійкових розрядів) стислої коди; N - можлива кількість адрес в ЗУ.

Якщо представити|уявляти| процес побуквенного| зрушення|зсуву| в загальному|спільному| вигляді|виді|, як показано на мал. 1, а, те довжина стислої коди

де до - число побуквенных зрушень; - довжина кодової комбінації букви.

Оскільки зрушуються всі букви, окрім першої, то і число зрушень де L - число букв в слові. Тоді

У російській мові найбільш довгі слова мають 23 - 25 букв. Якщо прийняти з умовою здійснення побуквенного зрушення з кожним кроком рівно на один розряд, для n і l можуть бути отримані наступні співвідношення

Якщо значення не задовольняє нерівності (71), можна кінцеві|скінченні| букви|літери| слова складати по модулю 2 без зрушення|зсуву| щодо|відносно| попередньої букви|літери|, як це показано на рис 1, би.

Наприклад, якщо для попереднього прикладу|зразка| із|із| словом “Газета”, стислий код матиме вигляд|вид|:

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

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

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

Для прикладу|зразка| розглянемо|розглядуватимемо| наступний|слідуючий| масив:

Згорнутий масив матиме вигляд|вид|:

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

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

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

Процес розгортання масиву здійснюється таким чином: перехід на наступний рядок відбувається при зустрічі к

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

Якщо в рядку масиву декілька ділянок, що повторюються, то можна замість вставляти спеціальні символи, вказуючі|показуючі| на необхідне число пропусків.

Наприклад, якщо позначити кількість пропусків, відповідно, Х - 2; Y - 3; Z - 5, то початковий і згорнутий масиви матимуть вигляд:

Процес розгортання масиву здійснюється таким чином: довжина рядка відома, кількість пропусків визначається символами X, Y, Z

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

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

Для розміщення в пам'яті ЕОМ М код, в яких найбільше з кодованих чисел рівне N, необхідний об'єм пам'яті

Із зростанням N довжина кодової комбінації ростиме як . Для економії об'єму пам'яті Q, число де вираз в дужках - закруглене значення до найближчого цілого числа, розбивають на L рівних частин. Максимальне число в отриманому інтервалі чисел буде не більше . Величина визначає розрядність чисел, що зберігаються, об'єм пам'яті для їх зберігання буде не більший . Якщо в пам'яті ЕОМ зберігати адреси меж відрізань і порядкові номери чисел, що зберігаються, відлічуваних від чергової межі, то визначає розрядність чисел для виразу номера межі (у останньому інтервалі має бути хоч би одне число); об'єм пам'яті для зберігання номерів меж буде _

(72)

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

(73)

Якщо підставити значення у вираз (72), то отримаємо. значення об'єму пам'яті при оптимальній кількості зон, на, які розбиваються числа, що зберігаються в пам'яті ЕОМ

(74)

Для значень при обчисленнях|підрахунках| можна користуватися наближеною формулою

(75)

При пошуку інформації в пам'яті ЕОМ перш за все|передусім| визначають значення і знаходять|находять| величину інтервалу між двома межами|кордонами|

Потім визначають, в якому саме з інтервалів знаходиться шукане число х

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

Завдання 7.1:. Визначити допустиму кількість слів, адреси яких можуть зберігати в ЗУ, якщо максимальна довжина кодованих слів L=15, а двійковий код букв – п'ятизначний.

Рішення|розв'язання|:

Завдання 7.2:. Визначити допустиму кількість зрушень при стискуванні восьмирозрядних кодових комбінацій, якщо допустима довжина стислої коди nмакс=12.

Рішення|розв'язання|:

Завдання 7.3. Використовуючи знак розділу р, скрутити наступний масив чисел:

1 9 7 1 1 3 7 4 3 0

1 9 7 1 1 3 7 4 3 1

1 9 7 1 1 3 7 4 3 2

1 9 7 1 1 3 7 4 3 0

1 9 7 1 1 3 7 4 3 1

1 9 7 1 1 3 7 4 3 2

Рішення|розв'язання|:

1 9 7 1 1 3 7 4 3 0

12012

7. ВАРІАНТИ КОНТРОЛЬНОЇ РОБОТИ

Варіант 1

Відомо, що одне з m можливих повідомлень, передаваних рівномірним двійковим кодом, несе 3 біта інформації. Чому дорівнює N?

Чому дорівнює ентропія системи, стан|достаток| якої описується дискретною величиною з|із| наступними|слідуючими| розподілами вірогідності|ймовірності|:

xi

x1

x2

x3

x4

pi

0,1

0,2

0,3

0,4

В результаті статистичних випробувань встановлено, що при передачі кожних 100 повідомлень завдовжки по 5 символів в повідомленні символ К зустрічається 50 разів, а символ Т – 30 разів. Разом з символом К символ Т зустрічається 10 разів. Визначити умовні ентропії Н(к/t) і Н(t/к).

Чому дорівнюють інформаційні втрати в каналі зв'язку, описаного за допомогою наступної|слідуючої| канальної матриці:

Визначити надмірність повідомлень, побудованих з алфавіту з наступним розподілом ймовірностіпояви символів в повідомленнях: pa = 0,03; pb = 0,26; pc = =0,09; pd = 0,05; ре = 0,16; pf = 0,1; pg=0,09; ph = 0,22.

Чому дорівнює мінімальна довжина кодових слів для передачі 16, 128, 57, 10, 432 повідомлень у вісімковому і двійковому кодах?

Варіант 2

Символи алфавіту володіють двома якісними ознаками (m = 2, символи первинного алфавіту). а) Яку кількість повідомлень можна отримати|одержувати|, комбінуючи по 3, 4. 5 і 6 елементів в повідомленні? б) Яка кількість інформації доводиться|припадає| на один елемент таких повідомлень?

Повідомлення складене з рівномірного алфавіту, m=128 якісних ознак, що містить. Чому дорівнює кількість символів в прийнятому повідомленні, якщо відомо, що воно містить 42 біта інформації? Чому дорівнює ентропія цього повідомлення?

Визначити загальну умовну ентропію повідомлень, складених з алфавіту А, В, якщоймовірністьпояви символів в повідомленні рівна рА=0,6; рВ=0,4. Умовна ймовірність переходів одного символу в іншій дорівнює р(В/а)=0,15; р(А/в)=0,1.

Визначити інформаційні втрати в каналі зв'язку, описаною наступною|слідуючою| матрицею:

Вірогідність появи букв первинного алфавіту на виході джерела повідомлень рівна: pa = 0,1; pb = 0,05; pc = 0,04; pd = 0,01; ре = 0,2; pf = 0,5; pg=0,07; ph = 0,03. Визначити ентропію, коефіцієнт ущільнення, надмірність і недогруженность символів повідомлень, побудованих з даного алфавіту.

6.Використовуючи знак розділу р, скрутити наступний масив чисел:

1 9 7 1 1 3 7 4 3 0

1 9 7 1 1 3 7 4 3 1

1 9 7 1 1 3 7 4 3 2

1 9 7 1 1 3 7 4 3 0

1 9 7 1 1 3 7 4 3 1

1 9 7 1 1 3 7 4 3 2

Варіант 3

У алфавіті три букви|літери| А, В, С. а) Скласти максимальну кількість повідомлень, комбінуючи по 3 букви|літери| в повідомленні? б) Яка кількість інформації доводиться|припадає| на одне таке повідомлення? у) Чому дорівнює кількість інформації на символ первинного алфавіту?

Визначити максимум системи, що складається з 6 елементів, кожен з яких може бути в одному з чотирьох станів|достатків| рівноімовірно.

При передачі повідомлень по каналу зв'язку з|із| шумами була отримана|одержувати| наступна|слідуюча| статистика: частота f1| з|із| 100 разів була прийнята 97 разів, 2 рази була прийнята частота f2| і 1 раз частота F3|; при передачі f2| 98 разів прийнята f2|, двічі – f1|; при передачі f3| 96 разів прийнята f3|, двічі - f2| і двічі – f4|; при передачі f4| 99 разів прийнята f4| і один раз - f3|.

а) Скласти канальну матрицю, що описує даний канал зв'язку з погляду умов проходження частот f1|, – f4|.

б) Визначити загальну|спільну| умовну ентропію повідомлень алфавітом яких є|з'являються| частоти f1| - f4,если| вірогідність|ймовірність| появи цих частот в передаваних повідомленнях відповідно рівна: p(f1|)=0,37, p(f2|)=0,3, p(f3|)=0,23, p(f4|)=0,1.

Повідомлення передаються комбінуванням частот f1|, f2|, f3|, f4|. Статистичні випробування каналу зв'язку для цих частот дали наступні|слідуючі| результати:

приемник

f1

f2

f3

f4

f1

0,9834

0,0160

0,0006

0

f2

0,0160

0,9837

0,0003

0

f3

0

0,0290

0,9708

0,0002

f4

0

0

0,0087

0,9913

а) Визначити ентропію об'єднання передаваних повідомлень, що приймаються, якщо частоти f1| – f4| з'являються|появляються| на виході передавача з|із| наступною|слідуючою| вірогідністю|ймовірністю|: p(f1|)= =p(f2|) = p(f3|)= 0,2; p(f4|)= 0,4.

б) Визначити інформаційні втрати при передачі повідомлень, що складаються з 1000 елементарних частотних посилок|посилань|.

Визначити середню надмірність на 200-буквений текст, побудований з алфавіту A, B, C, D з наступним розподілом вірогідності: pa = 0,1; pb = 0,25; pc = 0,35; pd = 0,3.

Яким способом найпростіше скрутити|згорнути| наступний|слідуючий| масив:

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

Показати процес згортання і розгортання даного масиву.

Варіант 4

1.Генератор виробляє чотири частоти f1|, f2|, f3|, f4|. У шифраторі частота комбінується по три частоти в кодовій комбінації. а) Чому дорівнює максимальна кількість комбінацій, складених з|із| цих частот? би) Чому дорівнює кількість інформації на одну кодову посилку|посилання| цих код?

2.Визначити ентропію словосполуки, складеної з|із| англійських букв|літер| Lemon| tea|. Вірогідність|ймовірність| появи букв|літер| в англійському тексті наступна|слідуюча|:

L-0,29|; E-0,1105|: M-0,021|; O-0,065|; N-0,059|; T-0,072|; A-0,063|.

3.В результаті статистичних випробувань встановлено, що при передачі кожних 100 повідомлень завдовжки по 5 символів в повідомленні символ До зустрічається 25 разів, а символ Т – 60 разів. Разом з символом До символ Т зустрічається 15 разів. Визначити умовні ентропії Н(К/т) і Н(Т/к).

4.Визначити середню кількість інформації, що міститься в прийнятому ансамблі повідомлень щодо переданого, якщо повідомлення складені з алфавіту А, Би, В. Вероятності появи букв в алфавіті на виході джерела повідомлень р(Аi)=0,25, p(Bi)=0,25, p(Ci)= 0,5. Умовнаймовірністьвиникнення пар виду ai/ bi наступна:

р(А/а)= 0,97; р(А/в)= 0,02; р(А/с)= 0,01; р(В/а)= 0,015; р(В/в)= 0,97; р(В/с)= 0,01; р(С/а)= 0,015; р(С/в)= 0,01; р(С/с)= 0,98.

5.Визначити загальну|спільну| і приватну надмірності деякого восьмибуквеного алфавіту, якщо відомо, що з урахуванням|з врахуванням| неравновероятности| розподілу символів його ентропія рівна Н’=2,7 біт/символ, а з урахуванням|з врахуванням| взаємозалежності букв|літер| ентропія цього алфавіту зменшується на 0,25 біт/символ.

6.Необхідно передати|передавати| в двійковому коді 9 чисел: 5, 7, 17, 31, 33, 127, 128, 129. Представити|уявляти| ці числа в двійковому коді.

Варіант 5

Відомо, що одне з m можливих повідомлень, передаваних рівномірним двійковим кодом, несе 4 біта інформації. Чому дорівнює N?

2.Чому дорівнює ентропія системи, стан|достаток| якої описується дискретною величиною з|із| наступними|слідуючими| розподілами вірогідності|ймовірності|:

xi

x1

x2

x3

x4

pi

0,25

0,25

0,3

0,2

Визначити загальну умовну ентропію повідомлень, складених з алфавіту А, В, якщоймовірністьпояви символів в повідомленні рівна рА=0,8; рВ=0,2. Умовнаймовірністьпереходів одного символу в іншій рівна р(В/а)=0,35; р(А/в)=0,2.

Визначити інформаційні втрати в каналі зв'язку, описаному наступною|слідуючою| канальною матрицею:

0,99

0,02

0

0

Р(а/b)=

0,01

0,98

0,01

0,01

0

0

0,98

0,02

0

0

0,01

0,97

Вірогідність появи символів A, B, C, D на виході джерела повідомлень відповідно рівні: рА = рВ = рС = рD =0,25. Визначити також середню кількість інформації в прийнятих повідомленнях щодо переданих.

З урахуванням частоти появи букв в текстах, ентропія англійської, німецької, французької і іспанської мов рівні відповідно: Нангл =4,03 біт/символ; Нфр = 3,96 біт/символ; Нісп = 3,98 біт/символ; Ннем = 4,1 біт/символ. Визначити приватну надмірність виду Dp для вказаних вище мов.

Визначити орієнтовну довжину кодового слова повідомлення, складеного з алфавіту А, Би, В, Грам, якщо рА = 0,1, рБ = 0,2; рВ = 0,3; рГ = 0,4, а вторинний код містить 8 якісних ознак.

Варіант 6

Символи алфавіту володіють двома якісними ознаками (m = 2, символи первинного алфавіту). а) Яку кількість повідомлень можна отримати|одержувати|, комбінуючи по 2, 3, 7 і 8 елементів в повідомленні? б) Яка кількість інформації доводиться|припадає| на один елемент таких повідомлень?

2.Повідомлення складене з рівномірного алфавіту, m=128 якісних ознак, що містить. Чому дорівнює кількість символів в прийнятому повідомленні, якщо відомо, що воно містить 42 біта інформації? Чому дорівнює ентропія цього повідомлення?

3.При передачі повідомлень по каналу зв'язку з|із| шумами була отримана|одержувати| наступна|слідуюча| статистика: частота f1| з|із| 100 разів була прийнята 97 разів, 2 рази була прийнята частота f2| і 1 раз частота F3|; при передачі f2| 98 разів прийнята f2|, двічі – f1|; при передачі f3| 96 разів прийнята f3|, двічі - f2| і двічі – f4|; при передачі f4| 99 разів прийнята f4| і один раз - f3|.

А) Скласти канальну матрицю, що описує даний канал зв'язку з погляду умов проходження частот f1|, – f4|.

Б) Визначити загальну|спільну| умовну ентропію повідомлень алфавітом яких є|з'являються| частоти f1| - f2,если| вірогідність|ймовірність| появи цих частот в передаваних повідомленнях відповідно рівна: p(f1|)=0,37, p(f2|)=0,3, p(f3|)=0,23, p(f4|)=0,1.

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

Визначити надмірність повідомлень, побудованих з алфавіту з наступним розподілом ймовірностіпояви символів в повідомленнях: pa = 0,07; pb = 0,03; pc = 0,09; pd = 0,01; ре = 0,3; pf = 0,11; pg=0,09; ph = 0,3.

Знайти верхню і нижню межі|кордони| мінімальної середньої довжини кодових блоків, якщо первинний алфавіт російський, а вторинний|повторний| містить|утримує| дві якісні ознаки. Блоки складаються з 5, 10, 50, 100 букв|літер| в блоці. Довести, що верхня і нижня межі|кордони| зближуються з|із| подовженням|видовженням| блоку.

Варіант 7

У алфавіті три букви|літери| D, E, F. а) Скласти максимальну кількість повідомлень, комбінуючи по 2 букви|літери| в повідомленні? б) Яка кількість інформації доводиться|припадає| на одне таке повідомлення? у) Чому дорівнює кількість інформації на символ первинного алфавіту?

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

3.В результаті статистичних випробувань встановлено, що при передачі кожних 100 повідомлень завдовжки по 5 символів в повідомленні символ До зустрічається 30 разів, а символ Т – 40 разів. Разом з символом До символ Т зустрічається 20 разів. Визначити умовні ентропії Н(К/т) і Н(Т/к).

4.Визначити кількість інформації в прийнятому ансамблі повідомлень, якщо задана умовнаймовірністьпереходу одного сигналу в іншій і ймовірностіпояви сигналів на виході джерела повідомлень: ра = 0,2; рb = 0,3; рс = 0,5; p(a’/a)= p(b’/b)= p(c’/c)= 0,97; p(b’/a)= p(c’/a)= p(a’/b)= p(c’/b)= p(a’/c)= p(b’/c)= 0,015.

Вірогідність появи букв первинного алфавіту на виході джерела повідомлень рівна: pa = 0,2; pb = 0,03; pc = 0,06; pd = 0,02; ре = 0,1; pf = 0,5; pg=0,06; ph = 0,03. Визначити ентропію, коефіцієнт ущільнення, надмірність і недогруженность символів повідомлень, побудованих з даного алфавіту.

6.Чому дорівнює середня довжина кодового слова оптимальної коди для первинного алфавіту з наступним розподілом вірогідності: р(а1)=0,13; р(а2)=0,16; р(а3)=0,02; р(а4)=0,03; р(а5)=0,6; р(а6)=0,01; р(а7)=0,05?

Варіант 8

Яка кількість інформації доводиться|припадає| на букву|літеру| алфавіту, що складається з 16, 25, 32 букв|літер|?

Визначити ентропію словосполуки, отриманої|одержувати| з|із| російських букв|літер|, – Яблуні квітнуть. Вірогідність|ймовірність| появи букв|літер| в російському тексті наступна|слідуюча|:

Я – 0,018; Би – 0,014; Л – 0,035; Про – 0,09; Н – 0,053; І – 0,062; Ц – 0,004; У - 0,038; Е – 0,072; Т – 0,053; У|біля| – 0,021.

3.Визначити загальну умовну ентропію повідомлень, складених з алфавіту А, В, якщоймовірністьпояви символів в повідомленні рівна рА=0,3; рВ=0,7. Умовнаймовірністьпереходів одного символу в іншій рівна р(В/а)=0,25; р(А/в)=0,15.

4.Визначити інформаційні втрати в каналі зв'язку, описаному наступною|слідуючою| канальною матрицею:

5.Визначити середню надмірність на 200-буквений текст, побудований з алфавіту A, B, C, D з наступним розподілом вірогідності: pa = 0,2; pb = 0,25; pc = 0,45; pd = 0,1.

Чому дорівнює довжина кодових комбінацій оптимальної коди для передачі повідомлень, складених з|із| 16, 32 і 28 рівноімовірних двійкових символів?

Варіант 9

1.Відомо, що одне з m можливих повідомлень, передаваних рівномірним двійковим кодом, несе 9 біта інформації. Чому дорівнює N?

2.Визначити максимум ентропії системи, що складається з 9 елементів, кожен з яких може бути в одному з трьох станів|достатків| рівноімовірно.

3.При передачі повідомлень по каналу зв'язку з|із| шумами була отримана|одержувати| наступна|слідуюча| статистика: частота f1| з|із| 100 разів була прийнята 97 разів, 2 рази була прийнята частота f2| і 1 раз частота F3|; при передачі f2| 98 разів прийнята f2|, двічі – f1|; при передачі f3| 96 разів прийнята f3|, двічі - f2| і двічі – f4|; при передачі f4| 99 разів прийнята f4| і один раз - f3|.

а) Скласти канальну матрицю, що описує даний канал зв'язку з погляду умов проходження частот f1|, – f4|.

б) Визначити загальну|спільну| умовну ентропію повідомлень алфавітом яких є|з'являються| частоти f1| - f2,если| вірогідність|ймовірність| появи цих частот в передаваних повідомленнях відповідно рівна: p(f1|) =0.37, p(f2|)=0,3, p(f3|)=0,23, p(f4|)=0,1.

4.Визначити інформаційні втрати в каналі зв'язку, описаному наступною|слідуючою| канальною матрицею:

5.Визначити загальну|спільну| і приватну надмірності деякого чотирьохбуквеного алфавіту, якщо відомо, що з урахуванням|з врахуванням| неравновероятности| розподілу символів його ентропія рівна Н’=1,7 біт/символ, а з урахуванням|з врахуванням| взаємозалежності букв|літер| ентропія цього алфавіту зменшується на 0,15 біт/символ.

6. Чому дорівнює початковий|вихідний| масив, якщо на проміжному етапі розгортання масив мав наступний|слідуючий| вигляд|вид|:

8 3 1 2 4 5 9 7

. . . . . . . 1

. . . . . . 2 1

. . . . . . . 4

. . . . . 3 5 7

3 4 2 1 3 4 2 2

. . . . . . 1 1

. . . . . . . 4

Варіант 10

Символи алфавіту володіють двома якісними ознаками (m = 2, символи первинного алфавіту). а) Яку кількість повідомлень можна отримати|одержувати|, комбінуючи по 3, 4. 9 і 11 елементів в повідомленні? б) Яка кількість інформації доводиться|припадає| на один елемент таких повідомлень?

2.Повідомлення складене з рівномірного алфавіту, m, що містить = 256 якісних ознак. Чому дорівнює кількість символів в прийнятому повідомленні, якщо відомо, що воно містить 42 біта інформації? Чому дорівнює ентропія цього повідомлення?

3.При передачі текстових повідомлень статистичні спостереження показали, що для слів з|із| середньою довжиною в 6 букв|літери| на кожних 100 повідомлень буква|літера| А зустрічається 80 разів, буква|літера| В зустрічається 50 разів, буква|літера| А і В разом зустрічаються 10 разів. Визначити умовну ентропію появи А, якщо в слові присутній В, і умовну ентропію В, якщо в слові присутній А.

4.Визначити інформаційні втрати в каналі зв'язку, описаному наступною|слідуючою| канальною матрицею:

5.З урахуванням частоти появи букв в текстах, ентропія англійської, німецької, французької і іспанської мов рівні відповідно: Нангл =4,03 біт/символ; Нфр = 3,96 біт/символ; Нісп = 3,98 біт/символ; Ннем = 4,1 біт/символ. Визначити приватну надмірність виду Dp для вказаних вище мов.

6.Яким початковим|вихідним| масивам відповідають наступні|слідуючі| згорнуті масиви:

а) 1 9 7 1 1 3 7 4 3 0

р 1 р 2 р 2 1 3 7 4

3 0 р 1 р 2

б) 1 9 7 1 1 3 7 4 3 0

р 1 р 2 р 2 1 3 7 4

3 0 р 1 р 2 р р р 7

8. ОСНОВНІ ВИМОГИ ДО ОФОРМЛЕННЯ КОНТРОЛЬНОЇ РОБОТИ

Контрольна робота повинна містити|утримувати| титульний лист|аркуш| (див. застосування II), умову завдання|задачі| і докладне|детальне| її рішення|розв'язання|. При описі рішення|розв'язання| необхідно указувати|вказувати|:

назва формул;

формули;

опис змінних, використовуваних у формулах;

назва методів, які використовуються при рішення конкретної задачі;

всю послідовність виконання розрахунків;

результати обчислень|підрахунків| і, якщо потрібний, зробіти вивід|висновок|.

Варіант контрольної роботи уточнюється у викладача (по списках).

9. ЕКЗАМЕНАЦІЙНІ ПИТАННЯ

Теорія інформації і кодування. Основні поняття і визначення.

Теорема відліків Котельникова.

Кількісна оцінка інформації.

Ентропія. Властивості ентропії.

Умовна ентропія. Канальна матриця.

Взаємна ентропія.

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

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

Надмірність інформації.

Основна теорема кодування для каналу зв'язку без шумів.

Побудова|шикування| оптимальної коди по методу Шеннона-фано.

Представлення код.

Принципи побудови|шикування| оптимальних код.

Побудова|шикування| оптимальної коди по методу Хаффмена.

Перешкодостійкість|перешкодостійкий|. Види перешкод.

Логічне кодування.

Цифрове кодування.

Пропускна спроможність дискретного каналу зв'язку з|із| шумами.

10. ЛІТЕРАТУРА

Кузин Л. Т. Основи кібернетики. Т. 1. Математичні основи кібернетики. Навчальний посібник для студентів вузів. М.: “Енергія”, 1973.

Теорія інформації і кодування. Цимбал Ст.|ст| П. Київ, Видавниче об'єднання “Вища школа”, 1977, 288 с.

Задачник по теорії інформації і кодуванню. Цимбал Ст.|ст| П. Видавниче об'єднання “Вища школа”, 1976, 276 с.

М. Н. Аршинів, Л. Е. Садовський Коди і математика (розповіді|оповідання| про кодування).- М.: Наука, Головна редакція фізико-математичної літератури, 1983.

Марков А. А. Введение в теорию кодирования. -М|.: Наука, 1982.

Шенон К. Работы по теории информации и кибернетике, М.: издательство иностр|. лит., 1963г|.

Хемминг Р. В. Коди с|із| выявлением и исправлением ошибок. Под ред|. Трофимова Д. Н., М.: Воениздат, 1970.

Застосування I

Таблиця 1

Співвідношення для коду Хеммінга

n

nu

nk

n

nu

nk

1

2

3

4

5

6

7

8

0

0

1

1

2

3

4

4

1

2

2

3

3

3

3

4

9

10

11

12

13

14

15

16

5

6

7

8

9

10

11

11

4

4

4

4

4

4

4

5

Таблиця 2

Загальна|спільна| таблиця перевірок

№ перевірки

Перевірочні позиції

№ контрольного символу

1

2

3

4

1, 3, 5, 7, 9, 11...

2, 3, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 27, 30, 31...

4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31..

8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, 43, 44, 45, 46...

1

2

3

4

Таблиця 3

Співвідношення розрядів

n

s

n

s

7

15

15

15

31

31

31

31

31

63

63

63

63

63

63

63

63

63

63

63

127

127

4

11

7

5

26

21

16

11

6

57

51

45

39

36

30

24

18

16

10

7

120

113

3

4

8

10

5

10

15

20

25

6

13

18

24

27

33

39

35

37

53

56

7

14

1

1

2

3

1

2

3

5

7

1

2

3

4

5

6

7

10

11

13

15

1

2

127

127

127

127

127

127

127

127

127

127

127

127

127

127

127

255

255

255

255

255

255

255

106

99

92

85

78

71

64

57

50

43

36

29

22

15

8

247

239

231

223

215

207

199

21

28

35

42

49

56

63

70

77

84

91

98

105

112

119

8

16

24

32

40

48

56

3

4

5

6

7

9

10

11

13

14

15

21

23

27

31

1

2

3

4

5

6

7

Зауваження: n – довжина кодового слова; - число інформаційних символів; - число коректуючих символів; s – число виправляємих символів.

Приложение II

Оформление титульного листа

Волжский университет им. В. Н. Татищева

Кафедра “Информатика и системы управления”

Контрольная работа

по дисциплине “Теория информации и кодирования”

специальность 071900 “Информационные системы и технологии”

(220100 “Вычислительные машины, системы, комплексы и сети”)

Выполнил: студент группы ИТЗ-301

Иванов С. И.

Проверил: ст. преп.

Маркова Т.И.

Дата сдачи:

Дата проверки:

Вариант 5

Тольятти, 2006

← Предыдущая
Страница 1
Следующая →

Файл

МЕТОДИЧНІ ВКАЗІВКИ1.docx

МЕТОДИЧНІ ВКАЗІВКИ1.docx
Размер: 941.7 Кб

.

Пожаловаться на материал

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

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Похожие материалы:

Научная теория управления Тейлора

Основная задача управления предприятием. Изложите основные принципы фордизма. Нужно признать, что не все люди одинаково одарены. Тавистокская школа и «гуманизация труда». Социальная структура трудового коллектива. Демографическая структура трудового коллектива.

Психологические проблемы диагностики аномального развития детей

Любопытно заметить, что Эскироль обратил внимание на недостатки речи умственно отсталых: дифференциацию внутри умственной отсталости он основывал на состоянии развития речи

Загальне мовознавство. Частина 1

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

Поиски и методика разведки месторождений полезных ископаемых

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

Рабочая программа учебной дисциплины Дошкольная педагогика

Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта среднего профессионального образования по профессии или специальности Дошкольное образование

Сохранить?

Пропустить...

Введите код

Ok