ЗАДАЧА 3.
1. Для дискретного каналу з незалежними помилками по елементах, імовірність яких дорівнює р (п.3 задачі 2 та п.2 задачі 3), визначити імовірність помилкового прийому Рпом кодової комбінації (п.3 задачі 1) та імовірність невиявленої перевіркою на парність помилки Рнп. Розрахунки, що треба виконати в даному пункті, мають на меті продемонструвати ефективність обраного методу захисту від помилок – виявлення на прийомі помилок в кодових комбінаціях застосуванням коду з парним числом одиниць (коду з одною перевіркою на парність). Для оцінки ефективності методу захисту від помилок необхідно визначити імовірність помилкового прийому Рпом кодової комбінації (п.3 задачі 1) та імовірність невиявленої перевіркою на парність помилки Рнп. Очевидно, що Рпом = P ( Для цього потрібно вміти розраховувати Р(t, n) - імовірність наявності рівно t помилок в блоці (кодовій комбінації) довжини n, а для цього треба знати, як помилки розподілені за часом. Різноманітність і складний характер завад в неперервному каналі приводить до складних імовірносних закономірностей при описі послідовності помилок в дискретному каналі Найбільш широко відома пуассонова модель, або модель незалежних помилок, яка вважає, що помилки в сусідніх елементах кодових комбінацій виникають незалежно і не впливають одна на одну. Дискретні канали з такими помилками називаються каналами без пам'яті. Ця модель є найбільш привабливою, оскільки вказані вище імовірності описуються простими формулами (Бернуллі), відповідними біноміальному розподілу імовірностей:
P(t, n) = C tn p t (1 – p) n – t де C tn = п! / (п – t)! t!
Тепер можна обчислити · імовірність помилкового прийому Рпом кодової комбінації
Рпом = P(t > 1, n) = Σ n t=1 C tn pt (1 - p) n – t = 1 - (1 - p) n » np (наближення вірне, якщо np << 1).
t нп, що не виявляються кодом з перевіркою на парність. Рнп = P(t > t нп, n) = Σ n t= t нп C tn pt (1 - p) n – t
Перевагою цієї моделі є її відносна простота: для прив'язки цих формул моделі до реального каналу зв'язку потрібно лише визначити коефіцієнт помилок каналу h і прирівняти його р – імовір-ності помилки в елементі.
2. Комбінацію коду МТК-2 двох перших букв Вашого прізвища закодувати циклічним кодом, що виправляє однократну помилку.
Для побудови циклічного коду необхідно пригадати алгоритм кодування і декодування. При кодуванні будь-яким систематичним лінійним кодом до заданих k інформаційних розрядів необхідно додати r перевірочних. У разі циклічного коду утворена таким чином п розрядна комбінація може бути представлена у вигляді полінома F(х ) ступеня n-1, який повинен без залишку ділитися на утворюючий поліном g(х) ступеня r. Щоб виконати цю вимогу, початкові k інформаційних розрядів також представляють у вигляді полінома К(х) ступеня k - 1 імножать його на х r . Теперь ділене К(х)* х r ділять на утворюючий поліном g(х) іотриманий залишок R(х) складають по модулю 2 з діленим К(х)* х r У результаті формується шукана комбінація циклічного коду F(х) = К(х)* х r + R(х) Декодування з виявленням помилок полягає в простому діленні прийнятої з каналу комбінації F"(х) на утворюючий поліном g(х) і визначенні залишку - синдрому помилки S(х). Якщо S(х) = 0,помилок немає, якщо S(х) / = 0, тобто залишок ненульовий - прийнята комбінація з помилками. Тепер лишилося тільки обрати необхідний утворюючий поліном g(х). Відомо, що для циклічних кодів, які виправляють однократну помилку, тобто з мінімальною кодовою відстанню d0 = 3, справедливе співвідношення (межа Гільберта):
r ³ log 2 (n+1)
З точки зору внесення мінімальної надмірності вигідно вибирати довгі кодові комбінації, оскільки із збільшенням n число перевірочних розрядів r збільшується повільно. У результаті відносна пропускна спроможність R збільшується, прагнучи до 1.
3.Побудувати функціональну схему кодуючого пристрою (для коду п.1) і декодуючого пристрою, що виправляє однократну помилку. З короткого опису алгоритму кодування і декодування видно, що основною операцією, яку треба виконати як при кодуванні, так і при декодуванні, є ділення полінома на поліном. Реалізувати цю операцію можна за допомогою схеми логічного регістра або зсуваючого регістра з логічним зворотним зв'язком, званого також багатотактним лінійним фільтром. Його структура задається видом дільника - утворюючого полінома g(х) ступеня r:регістр складається з r елементів пам'яті, суматорів по модулю 2 і зв'язків, відповідних ненульовим членам g(х). Кількість суматорів на одиницю менше числа ненульових членів g(х). Ділене - кодова комбінація - вводиться в регістр послідовно, починаючи зі старших розрядів, і коли введення закінчиться - в регістрі буде записаний залишок від ділення. Розглянемо детальніше побудову і роботу такого регістра на прикладі. Нехай заданий циклічний код (7,4) з утворюючим поліномом ступеня r = 3: g(x) = х3 + х2 + 1. Схема регістра ділення приведена на рис. 4.1. Вона складається з трьох елементів пам'яті і двох суматорів по модулю 2. Суматори встановлюються перед елементами пам'яті, відповідними ненульовим членам g(х): передкоміркою 1 (для х0 = 1) іпередкоміркою 3 (для х 2).
Рис. 1
Закодуємо комбінацію з чотирьох інформаційних розрядів, наприклад, 1011. Їй відповідає поліном К(х) = х3 + х + 1. У відповідності з вищенаведеним алгоритмом помножимо К(х)* х 3 = х6 + х4 + х3 і будемо ділити "в стовпчик" на утворюючий поліном g(x) = х3 + х2 + 1. Таке ділення не відрізняється від звичайного, арифметичного, за винятком того, що віднімання на кожному кроці ділення замінюється порозрядним (без перенесення) складанням по модулю 2. Ці операції можна виконати в звичайному вигляді: початкова комбінація - 1011, після множення- 1011000, утворюючий поліном в звичайному вигляді 1101. Ділимо 1011000: 1101 «в стовпчик» за вищезгаданими правилами.
Роботу схеми ділення (рис. 4.1) легко зрозуміти, зіставляючи кожний крок (такт) її роботи з кроками ділення «в стовпчик». У початковому положенні всі елементи пам'яті регістра знаходяться в стані «0». Тому на верхні (на малюнку) входи суматорів надходить «0» і вони просто пропускають сигнали з нижніх входів. Схема працює при цьому як звичайний зсувний (послідовний) регістр, керований не показаними на рисунку тактовими імпульсами. На її вхід надходить комбінація діленого 1 0 1 1 000, починаючи зі старших розрядів. Через 3 такти в регістрі будуть записані три старших розряди діленого, причому «1» старшого розряду виявиться в третій комірці. На наступному такті на вхід подається четвертий розряд діленого, а «1» старшого розряду «виштовхується» на вихід. При цьому вона надходить на верхні входи суматорів, а на нижні входи - одиниця і нуль, відмічені курсивом в комбінації діленого. Результат складання записується в комірки з номерами відповідно 3 і 1. Ці дії еквівалентні першому кроку ділення «в стовпчик», коли до чотирьох старших розрядів діленого додають по модулю 2 утворюючий поліном, і утвориться перший «залишок». Тепер стає зрозуміло, чому суматори встановлюються перед елементами пам'яті, відповідними ненульовим членам утворюючого полінома: це забезпечує складання по модулю 2 старших розрядів діленого з утворюючим поліномом)*. Введення в регістр подальших розрядів еквівалентне «зносу» цифр ділимого при діленні «в стовпчик». У результаті на п = 7 - му такті в регістрі буде записаний останній, тобто шуканий, залишок. Тепер легко побудувати структурну схему кодера (рис. 2)
Вхід Вихід
На вхід кодера надходить k розрядна інформаційна кодова комбінація, що супроводиться r нулями. У регістрі ділення протягом п тактів формується залишок - r перевірочних розрядів. Одночасно через регістр затримки і комутатор k інформаційних розрядів надходять на вихід, а услід за ними через комутатор на вихід надходять перевірочні розряди. Якби k - розрядна інформаційна кодова комбінація надходила прямо на вихід, то перевірочні розряди - лише через r тактів після неї, оскільки вони формуються протягом п= k + r тактів. Затримка на r тактів, здійснювана в регістрі затримки, необхідна, щоб усунути розрив в r тактів. Схема декодера залежить від призначення циклічного коду: якщо код призначений лише для виявлення помилок, то декодер складається з регістра ділення і детектора помилки, який при ненульовому залишку - синдромі S(х) видає сигнал про наявність помилки в комбінації. Якщо ж код, як в нашому випадку, здатний виправляти помилки, то декодер складається з регістра ділення, дешифратора помилок, буферного регістра і пристрою виправлення. Дешифратор помилок фіксує вид залишку - синдрому помилки S(х ), в буферному регістрі зберігається прийнята комбінація, а пристрій виправлення провадить в ній корекцію помилок за видом синдрому S(х).
)* Може викликати питання, чому в схемі відсутній третій суматор і четвертий елемент пам'яті, відповідні старшій одиниці утворюючого полінома. Це усуває «надмірність» в схемі, оскільки при діленні «в стовпчик» на кожному кроці в старшому розряді завжди складаються дві одиниці, так що не потрібен суматор, а їх сума всякий раз дає нуль, який не треба запам'ятовувати.
3. ПЕРЕЛІК ЛІТЕРАТУРИ
|
-імовірність помилки будь-якої кратності t (t = 1 і більше) в блоці - комбінації довжини n, а Рнп – ймовірність помилок такої кратності в комбінації, що не виявляються даним кодом. Кратність визначає число помилок t, що доводяться на задане число одиничних елементів (кодову комбінацію): помилки можуть бути однократними, двократними і т.д.
. Такий опис називають моделлю дискретного каналу.
,
