- •1.1. Повідомлення та інформація
- •1.2. Моделі інформаційних систем
- •1.4. Предмет теорії інформації та кодування
- •2.2. Кількісна міра інформації
- •2.3. Ентропія та її властивості
- •2.4. Безумовна ентропія
- •2.5. Умовна ентропія
- •2.6. Ентропія об'єднання двох джерел
- •3.1. Продуктивність дискретного джерела та швидкість передачі інформації
- •4.1. Квантування сигналів
- •4.2. Інформаційні втрати
- •4.3. Продуктивність неперервного джерела та швидкість передачі інформації
- •IhlilhM
- •4.4. Пропускна здатність . . . .
- •5.1. Класифікація кодів і характеристики їх
- •5.4. Способи подання кодів
- •5.6. Основні теореми кодування для каналів
- •6.1. Класифікація первинних кодів
- •6.2. Нерівномірні двійкові первинні коди
- •6.2.1. Код морзе
- •6.2.2. Число-імпульсні коди
- •6.3. Рівномірні двійкові первинні коди
- •6.3.1. Числові двійкові коди
- •6.3.2. Двійково-десяткові коди
- •6.3.4. Двійково-шістнадцятковий код ;;.-,-.
- •6.3.5. Рефлексні коди
- •7.1. Двійкові коди,
- •7.1.2. Код із перевіркою на непарність
- •7.1.3. Код із простим повторенням
- •7.2. Недвійкові коди, що виявляють помилки
- •7.2.1. Код із перевіркою за модулем q
- •7.2.2. Код із повторенням
- •8"6 90472 "100562 І' • шТрИховє зОбраЖєння кодового сло-
- •8.1. Двійкові групові коди
- •8.1.1. Лінійний систематичний груповий (блоковий) код
- •8.1.2. Коди хеммінга
- •8.1.4. Коди боуза - чоудхурі - хоквінгема
- •8.1.5. Код файра
- •8.1.6. Код із багатократним повторенням
- •8.3.2. Узагальнений код хеммінга
- •8.3.3. Коди боуза - чоудхурі - хоквінгема
- •8.3.4. Коди ріда - соломона
- •8.3.6. Недвійковий ланцюговий код
- •9.1. Вірогідність передачі кодованих повідомлень
- •9.2. Стиснення інформації"
- •9.2.1. Способи стиснення даних при передачі
- •9.2.2. Способи стиснення даних при архівації
- •Збіжного рядка
- •9.3. Збільшення основи коду
- •0Сзезс99е8с0е1с10d1c242d5c3d2c6d8cbd6e8c0
- •VosooooooooooooooooOvJvJ
9.1. Вірогідність передачі кодованих повідомлень
Вірогідністю передачі кодованих повідомлень оцінюється відповідність між кодовими комбінаціями, прийнятими на приймальному боці, та комбінаціями, переданими в канал зв'язку.
У свою чергу, оцінка вірогідності обміну інформацією визначається ймовірністю спотворень повідомлень, тобто прийняттям Рп помилкового повідомлення при відомій імовірності Ре спотворення елемента повідомлення, що передається. Таким чином, вірогідність передачі є похідною характеристикою, яка залежить як від коректувальної здатності коду, так і від типу каналу (лінії) зв'язку та умов передачі по ньому елементів кодової комбінації.
Для двійкових кодів дія завад на елемент кодової комбінації може призвести до різних наслідків у несиметричних і симетричних каналах. Так, у несиметричних каналах імовірності переходу під впливом завад 0 в 1 (Р01) та 1 в 0 (Р10) не будуть однаковими, а в симетричних вони збігаються. Проте для спрощення розрахунків при оцінюванні вірогідності повідомлень, що передаються, вважатимемо двійковий канал симетричним, тобто Р01 = Р10 - Рс.
Крім того, розрізняють канали з незалежними помилками, коли виникнення однієї помилки не залежить від появи іншої
216
(канал без пам'яті), та канали з пакетним розподілом помилок, в яких є залежність імовірності спотворення наступного елемента, що передається, від спотворення попереднього (канал має пам'ять).
Розглянемо оцінку вірогідності при передачі кодованих повідомлень по цих двійкових симетричних каналах.
У разі передачі повідомлень по каналах із незалежними помилками ймовірність відсутності спотворень двійкового елемента повідомлення позначимо як (1 - Ре). Тоді для двійкової послідовності завдовжки п елементів [12] імовірність правильно прийнятої послідовності
^пр = (1-^)п' (91)
а ймовірність помилки в прийнятій послідовності
Рп=1-{1-ру. (9.2)
Останній вираз можна подати так:
Л. = с*рє + сірі + с№ + ... + с;рі, (9.3)
де Cv = — , a v = 1, 2, 3,... — кратність помилки.
п v!(«-v)!
Через те, що Ре « 1, ймовірність помилки в «-елементній кодовій послідовності можна записати як
Як відомо, коректувальні коди дають змогу виявляти або виправляти (залежно від кодової відстані) ту чи іншу кількість помилок. Тому для оцінювання ефективності кодів необхідно знати ймовірність виникнення в кодовій комбінації помилок будь-якої кратності.
При незалежних помилках імовірність появи v-кратних помилок визначається за формулою Бернуллі
Pu(v) = C^(l-Pcr\ (9.4)
Для кодів з dmin > 1, що використовуються з метою виявлення всіх помилок кратністю vB = d -n - 1 і меншою, ймовірність помилкової (неправильної) комбінації на виході декодера легко знайти, врахувавши, що при передачі комбінації можуть бути такі чотири ситуації:
комбінація, яка приходить з каналу, прийнята без помилок (правильно) з імовірністю Р ;
комбінація містить не більш як vB спотворених елементів, що виявляються кодом (імовірність такої події Рв п);
217
комбінація містить v > v помилок, але вони розташовані так, що виявляються кодом (імовірність такої події Р'ъ п);
комбінація містить v > vB помилок, які кодом не виявляються з імовірністю РНВТ1.
Оскільки сума ймовірностей всіх перелічених подій дорівнює 1, а ймовірність ?'в п « 0,
р =р + р . (9.5)
А п х в.п л нв.п \'~'J
З урахуванням того, що спотворені комбінації, які виявляються декодером, не видаються споживачеві інформації, ймовірність здобуття ним помилкових комбінацій оцінюватиметься тільки ймовірністю невиявленої помилки Рнв п, яку можна записати у вигляді [12]
(9.6)
v=dmm
де W(w) — вагова характеристика коду (кількість його комбінацій вагою w, тобто кількість варіантів помилок, які не виявляються цим кодом); dmin — мінімальна кодова відстань.
Значення W(w) визначається за спеціальними методиками для різних кодів [14]. Так, доведено, що коли двійковий (п, к)-коа має кодову відстань d, то
(9.7)
W(w)--
с:
[=0,v<d;
-,v>d,
СІ
де/ = (</-1)/2.
З урахуванням (9.7) маємо
1
It
ПИ
(І-^е)'С'
+/-v
i-lc<n+tpt(i-Pj
v=0
^нв.п^
(9.8)
icvn+lp:d-Per
v=n+l
Права частина (9.8) при 0 < Ре < 0,5 обмежена зверху значенням) Ре = 0,5; тому в будь-якому каналі з незалежними помилками
де А: — кількість інформаційних елементів; d — мінімальна кодова відстань; п — довжина коду.
На практиці поширенішою є формула для приблизного оцінювання ймовірності виникнення невиявленої помилки [12]
P^~lc^{X-Pj~\ (9.9)
2rv=d
де г — кількість перевірних елементів коду; v — кратність помилки; d— мінімальна кодова відстань.
Для кодів з d > 2, що використовуються для виправлення всіх помилок .кратністю vBn = [(d-1)/2], де [•] означає цілу частину й менше, ймовірність Рп виникнення помилкової комбінації на виході декодера можна знайти, врахувавши, що після проходження кодової комбінації по каналу можливими є такі чотири ситуації:
комбінація прийнята без помилок (правильно) з імовірністю Р ;
комбінація містить не більш як vBn спотворених елементів, які виправляються кодом з імовірністю Рвп п;
комбінація містить v > vBn помилок, розташованих так, що вони виправляються кодом з імовірністю Р/вп п;
комбінація містить v > v помилок, які не виправляються кодом (імовірність такої події Рн вп п).
Оскільки ймовірність Р/ш п ~ 0, маємо
р = р + р (д Ю)
звідки
2п л вп.п л н.вп.п' V?lKJj
р -р -Р
н.вп.п п вп.п
При незалежних помилках імовірність виправлення помилок кратністю до v кодами, що виправляють помилки, визначається виразом
^п.п=МРЛі-^еГ- (9.П)
і=1
З урахуванням виразів (9.2) та (9.11) дістаємо
''„.вп.п =1-(1-Ре)"-£«(1-^Г''- (9.12)
Р
< 2ЧО
Цю оцінку можна застосувати для коротких кодів з невеликою надмірністю. Для кодів з великою надмірністю бажано користуватися виразом [14]
Pnbn<2k(dln)d(\-dlny-d,
1=1
На основі здобутих значень Рп можна визначити коректувальний код, оптимальний для даного каналу.
Двійковий коректувальний код завдовжки п з N комбінаціями називається оптимальним для двійкового симетричного каналу, якщо ймовірність Рп виникнення помилкової комбінації на
218
219
виході декодера не перевищує такої самої імовірності для будь-якого іншого двійкового коду тієї самої довжини п із тією самою кількістю комбінацій N.
У разі передачі повідомлень по каналах із пакетним розподілом помилок визначення ймовірності їх за формулами (9.3) — (9.12) дають значення, які набагато відрізняються від реальних. Це пояснюється тим, що в цих каналах на проходження сигналів (а це в основному радіоканали) сильно впливають сезонні та добові зміни метеорологічних умов, промислові завади, інтенсивність яких змінюється протягом доби та тижня, тощо [5, 12]. Все це призводить до виникнення в каналах пакетів (пачок) помилок. Визначити ймовірність їх за таких умов досить складно, оскільки необхідно провести дослідження реальних характеристик каналів.
Формула, що дає приблизне значення ймовірності помилок при пакетному розділі їх і передачі двійкової послідовності п елементів [21], має вигляд
Р "max
ъ
1+-
(9.13)
Л-П ЬРг
/
6=1
5тах ЇЬРЬ
Ь=1
де Рс — імовірність спотворення двійкового елемента; / — щільність помилок у пакеті, яка визначається відношенням кількості помилок у ньому до довжини пакета b; Ph — умовна ймовірність виникнення пакета помилок завдовжки Ь.
Для кодів, що виявляють пакети помилок, імовірності помилок можна знайти за формулами [21]:
Значення усіх величин, які входять у ці формули, дістають експериментально, визначаючи характер розподілу помилок, або беруть із літератури для каналів аналогічного типу.
У [46] реальні канали описано за допомогою двох параметрів: імовірності Ре спотворення двійкового елемента та показника а групування помилок. При цьому наближені формули для визначення ймовірності невиявлених помилок мають такий вигляд:
• для кодів, що виявляють помилки,
Р Л(П-Т
2ГУ) '
для кодів, що виправляють помилки,
для кодів, що виявляють і виправляють помилки,
1-а
J=0
нвп 2r U"VJ
де d— мінімальна кодова відстань; v — кратність помилки, що виправляється; г — кількість перевірних елементів.
Ці формули дають непогані результати при v < 0,3л, де п — кількість елементів кодової комбінації.
р
Р ~-М
л в.п т ^
ЇЬРЬ
6=1
gxfi+*-n ьрь іУГ
Ь--п-(21к+і)
^тах ЪЬРЬ
6=1
JHB.n . 7 L \ІЛ Z
2Г I b=lk+\l b
ЪРи
'max lbPb
де Ік довжина пакета помилок, яка виявляється.
(9.14)
(9.15)
