Здійснити розрахунки при розв’язанні таких задач.
1. Яка кількість інформації буде передана двійковим симетричним каналом при Pпом = 0,5? Що це означає?
2. Яка кількість інформації буде передана двійковим симетричним каналом при Pпом = 0? Що це означає?
3. Яка кількість інформації буде передана двійковим симетричним каналом при Pпом = 1? Що це означає?
4. Визначити середню кількість інформації, що приходиться на кожне повідомлення для наступних випадків:
а) P(x1) = 0,2; P(x2) = 0,1; P(x3) = 0,3; P(x4) = 0,25; P(x5) = ……;
б) P(x1) = 0,2; P(x2) = 0,2; P(x3) = 0,4; P(x4) = 0,25; P(x5) = ……;
в) P(x1) = 0,4; P(x2) = 0,1; P(x3) = 0,3; P(x4) = 0,15; P(x5) = ……;
г) P(x1) = 0,2; P(x2) = 0,4; P(x3) = 0,3; P(x4) = 0,05; P(x5) = ……;
д) P(x1) = 0,1; P(x2) = 0,1; P(x3) = 0,3; P(x4) = 0,25; P(x5) = …….
5. Визначити надлишковість алфавіту двійкового джерела, що видає повідомлення “0” і “1” незалежно при умові, що:
а) Р(0) = 0,1; б) Р(0) = 0,2; в) Р(0) = 0,3; г) Р(0) = 0,4; д) Р(0) = 0,25; е) Р(0) = 0,01; ж) Р(0) = 0,02; з) Р(0) = 0,04 і) Р(0) = 0,05; к) Р(0) = 0,5.
6. Визначити ентропію повідомлення із п’яти літер, якщо загальне число літер в алфавіті дорівнює 33 і всі літери та повідомлення рівноймовірні.
7. Безперервна величина, що вимірюється, змінюється у межах від 
до + а і розподілена рівноймовірно. Знайти диференційну ентропію даної величини.
8. Визначити пропускну здатність безпреревного каналу з завадами типу білого шуму. Смуга каналу 1000 Гц; потужність сигналу 4 Вт, спектральна густина потужності шумів 
Вт/Гц.
9. При передачі безперервного повідомлення з шириною спектру 50 Гц відбувається його перетворення в цифровий сигнал; квантування по рівню має 64 градації. Визначити продуктивність джерела.
10. Виконати дослідження інформаційних характеристик дискретного джерела при таких умовах.
По дискретному стаціонарному симетричному каналу без пам’яті передаються повідомлення x1, x2,... xN Їх ймовірності та ймовірність помилки при передачі, а також тривалість сигналу, який використовується для передачі кожного із повідомлень, надані у таблиці 1.
Таблиця 1
| Вариант | P(x1) | P(x2) | P(x3) | P(x4) | P(x5) | Тривалість посилки (Тпос) | Pпом |
| P(x1) = 0,1 | P(x2) = 0,2 | P(x3) = 0,4 | P(x4) = 0,25 | P(x5) = ……. | 100мкс | 0.05 | |
| P(x1) = 0,5 | P(x2) = 0,1 | P(x3) = 0,15 | P(x4) = 0,05 | P(x5) = ……. | 1нс | 0.1 | |
| P(x1) = 0,1 | P(x2) = 0,2 | P(x3) = 0,4 | P(x4) = 0,25 | P(x5) = …… | 20мс | 0.2 | |
| P(x1) = 0,4 | P(x2) = 0,1 | P(x3) = 0,3 | P(x4) = 0,15 | P(x5) = …… | 25мкс | 0.3 | |
| P(x1) = 0,2 | P(x2) = 0,4 | P(x3) = 0,3 | P(x4) = 0,05 | P(x5) = …… | 50мс | 0.4 |
(Номер варіанту обирається студентом самостійно.)
10.1. Визначити:
власну ентропію джерела,
максимальну ентропію джерела,
надмірність джерела,
швидкість передачі інформації при наявності завад,
швидкість передачі інформації при відсутності завад,
пропускну здатність каналу при наявності завад,
пропускну здатність каналу при відсутності завад.
10.2 Перерозподілити ймовірності повідомлень таким чином, що величина ймовірності найбільш ймовірного повідомлення залишається незмінною, а решта повідомлень стають рівноймовірними. Розрахувати зазначені у пункті 1 величини.
10.3 Повернутися до початкового розподілу ймовірностей. Збільшити (зменшити) ймовірність помилки на 0,1. Розрахувати зазначені у пункті 1 величини.
10.4 Проаналізувати результати розрахунків за пунктами 1…3, представивши їх у окремій таблиці.
Вивчення теми 3.
При вивченні теми 3 - основи теорії кодування слід звернути увагу на такі основні визначення, поняття та теоретичні положення.
Процес перетворення дискретного повідомлення (заданого набору символів) у комбінацію кодових символів, який здійснюється за певним правилом, зветься кодуванням (у вузькому розумінні). У широкому розумінні кодування - будь-яке перетворення повідомлення у сигнал шляхом встановлення взаємної відповідності.
Множина всіх кодових послідовностей (кодових комбінацій), які можливі при певному правилі кодування, утворює код.
Сукупність символів, які використовують для формування кодових послідовностей, називають кодовим алфавітом, а їх число m – основою коду. Загальна кількість символів (розрядів) у кодовій комбінації (n) називають довжиною коду (значністю або розрядністю). Кількість кодових комбінацій, яку можна утворити при основі m і розрядності n, звуть потужністю коду Nкод = mn. Ще одним параметром коду є його вага (w); для двійкового коду - це кількість одиниць у кодовій комбінації.
У відповідності до зазначених параметрів коди класифікують так.
За величиною основи:
m = 1 – одиничний код;
m = 2 – двійковий код;
m > 2 – багатопозиційні коди (наприклад, m = 8 – вісімковий; m = 10 – десятковий; m = 16 – шістнадцятьковий).
За величиною розрядності:
– код блочний (блоковий) - для такого коду існує величина n (тобто повідомлення розділяють на кодові слова):
при n =const (кількість символів у кожній кодовій комбінації однакова) – код блочний рівномірний;
при n = var (кількість символів у кодових комбінаціях різна) – код блочний нерівномірний;
- безперервний код - для такого коду величину n не визначають.
За величиною ваги:
при w =const – код з постійною вагою;
при w = var – код блочний нерівномірний.
Для однозначного представлення певної кількості повідомлень Nпов необхідно виконати умову Nпов ≤ Nкод. При введенні даних в системах передачі та оброблення інформації застосовують первинні коди, для яких виконується умова mn-1 ≤ Nпов ≤ mn.
Наприклад, якщо деяке джерело має 32 стани, то при передачі їх двійковим телеграфним кодом стани можна закодувати п’ятизначними двійковими числами. (в цьому разі будуть використані всі можливі 32 комбінації). Подібні коди називають також рівнодоступними. (Удеяких джерелах їх називають простими або примітивними).
Прагнуть, щоб код дозволяв представляти повідомлення комбінаціями з мінімальним числом розрядів. Такий код зветься економним або статистичним при умові, коли його середня розрядність мінімізована завдяки тому, що повідомленням, які мають максимальну ймовірність відповідають найкоротші комбінації, а малоймовірним – довші (як було показано у темі2).
Але при застосуванні рівнодоступного і економного кодів зміна (з будь-яких причин, наприклад, із-за завад) лише одного символу веде до помилкового прийому повідомлення. Тому при передачі по каналу все частіше застосовуються завадостійкі коди. У таких кодах використовують не всі можливі комбінації, а лише їх частину. Вони звуться дозволеними, а решта – забороненими кодовими комбінаціями. Завдяки цьому можна виявляти і навіть виправляти помилки у прийнятих комбінаціях, що веде до підвищення достовірності передачі.
Дуже велике значення для аналізу властивостей кодів має визначення відмінності одна від одної кодових комбінацій, що належать відповідному коду.
Для оцінки відмінності однієї кодової комбінації від іншої використовують величину, яка зветься відстань Хемінга d(Bi, Bj). Вона визначається кількістю розрядів, у яких одна кодова комбінація (Bi) відрізняється від іншої (Bj). Для двійкового коду із значністю n (наприклад, блочного коду) вона визначається так
d(Bi, Bj) = 
, (2)
де 
і 
jk – k -ті символи комбінацій Bi та Bj відповідно;
- символ складання за модулем 2.
Найменша відстань Хемінга між комбінаціями даного коду зветься кодовою відстанню dк.
Для рівнодоступних кодів, де використовуються усі можливі комбінації, 1≤ dк ≤ n.
Для завадостійких кодів2 ≤ dк ≤ n.
Первинні коди розглянути детальніше самостійно за [4; 8]
Завадостійке кодування
Завадостійкими є такі коди, які дозволяють виявляти або виявляти та виправляти помилки, що виникають у процесі передачі внаслідок дії завад. Як зазначалося вище, при завадостійкому кодуванні з усіх N0 можливих кодових комбінацій довжиною n символів використовують лише Nд дозволених (тобто частину із N0).
Усі заборонені комбінації, кількісит яких становить Nз = N0 – Nд, розбиваються на Nд підмножин Мі, і=1... Nд, і кожній підмножині ставиться у відповідність дозволена комбінація Ві. Правило прийому встановлюють таке: коли прийнята комбінація попала у підмножину Мі, то приймають рішення на користь комбінації Ві. У такому випадку фактично виправляються всі ті помилки, які не виводять передану кодову комбінацію за межі віднесеної до неї підмножини заборонених.
У підмножину Мі повинні бути включені комбінації 
, при прийомі яких найбільш імовірною переданою комбінацією є Ві. Доцільно, щоб декодер приймав рішення на користь комбінації Ві тоді, коли прийнята комбінація відрізняється від Ві на меншу кількість символів ніж від інших дозволених комбінацій. Таке правило прийняття рішення є оптимальним за критерієм максимуму правдоподібності. У такому випадку рішення приймається на користь Ві, коли умовна ймовірність Р 
прийняття кодової комбінації 
при передачі комбінації Ві є максимальною.
Для двійкового симетричного каналу без пам’яті.
Р 
, (28)
де Рпом – імовірність спотворення символу,
d 
- відстань Хемінга між 
(число розрядів, в яких комбінації 
відрізняються одна від одної).
Існує два великих класи завадостійких кодів:
блочні (блокові);
безперервні.
(Детальнішу класифікацію див. [1,3,4,6])
При блочному кодуванні послідовність елементарних повідомлень (у вигляді, наприклад, двійкових символів) розбивається на відрізки, кожному з яких ставиться у відповідність певна послідовність (блок) кодових символів, яку звуть кодовою комбінацією. Множина всіх можливих при цьому кодових комбінацій зветься блочним кодом. Коли довжина блоку (кількість символів кодової комбінації) n є постійна величина, – код зветься рівномірним. Коли n = var, - нерівномірним. Як правило використовують рівномірні завадостійкі коди.
Здатність коду виявляти (виправляти) помилки оцінюється кратністю помилок, які він дозволяє виявити (виправити) tв (tвип). Кратність помилки це кількість символів кодової комбінації, які спотворені.
Ці величини у свою чергу обумовлені кодовою відстанню d. Для виявлення помилок необхідно, щоб кодова відстань відповідала співвідношенню
dв 
1+tв; . (29)
для виправлення помилок –
dвип 1+2tвип, (30)
де tв - кратність помилок, що виявляються,
tвип - кратність помилок, що виправляються.
При цьому деякі помилки більшої кратності можуть також виявлятися (виправлятися).
Необхідна кодова відстань забезпечується шляхом введення надлишковості. Кодова відстань обумовлює потрібну кількість перевірочних (надлишкових) розрядів r у кодовому слові блокового коду. В результаті n -розрядне кодове слово складається із k інформаційних розрядів та r перевірочних розрядів. Їх розташування в межах кодового слова блокового роздільного коду може бути довільним, але відомим приймальній та передавальній стороні.
Надлишковість є одною з характеристик завадостійких кодів, під якою розуміють (для блокових кодів) величину
R = 
. (31)
Величина 
зветься відносною швидкістю коду.
Величина r визначається через верхню межу Хемінга
r 
. (32)
для парного значення tв.
Або
r 
(33)
для непарного tв.
Це співвідношення справедливе для „швидких” кодів, тобто коли 
.
Для „повільних” кодів, коли 
, треба використовувати верхню межу Плоткіна
r 
. (34)
Щоб не перевищити доцільний рівень r користуються нижнею межею Варшамова-Гільберта
r 
. (35)
Найбільш поширеними способами опису блокових кодів є матричний та поліноміальний.
Матричний опис блокових лінійних кодів.
Матричне представлення кодів є досить зручним. В першу чергу це стосується систематичних (
) кодів.
Усі їх дозволені комбінації можна отримати маючи 
вихідних (базисних) лінійно незалежних дозволених комбінацій. Ці комбінації повинні задовольняти таким умовам[3]:
1) до числа базисних комбінацій не може входити нульова комбінація;
2) кодова відстань між будь – якими парами базисних комбінацій не може бути меншою 
;
3) кожна базисна комбінація повинна мати кількість одиниць не менше (це стосується будь–якої дозволеної)
4) всі базисні комбінації повинні бути лінійно незалежними.
Базисні комбінації представляють у вигляді матриці розмірності к x п
G= 
. (36)
Цю матрицю називають породжуючою. Процес кодування полягає у виконанні операції
В=А × G, (37)
де: А – вектор розмірності 1×k, який відповідає повідомленню, що підлягає кодуванню,
В – вектор розмірності 1×n, який відповідає дозволеній кодовій комбінації даного коду.
Матрицю G можна представити у вигляді двох підматриць: інформаційнoї матриці І розмірності k×k, яку зручно обирати одиничною, та матриці перевірочних символів Р розмірності k×r (де r=n-k)
G = 
. (38).
Лінійний (n,k)код може бути заданий перевірочною матрицею Н розмірності r×n. Тоді для кодової комбінації, яка належить даному коду, виконується
ВНТ =0, (39)
де символ Т означає транспонування матриці.
Канонічна форма матриці Н має вигляд
Н= 
. (40)
Кодуючий пристрій лінійного () коду[1] складається із k розрядного регістру зсуву та r блоків суматорів за модулем 2. Інформаційні символи подають на вхід регістру і на вихід кодуючого пристрою через ключ, який після приходу k -го інформаційного символу починає покроково підключатися до виходів суматорів починаючи з першого і до r -го (для видачі на вихід кодера перевірочних символів від вk+1 до вп).
Процес декодування полягає у виконанні операції
S=BHT, (41)
де S – вектор синдрому розмірності 1×r,
B- вектор прийнятої комбінації.
У випадку, коли прийнята кодова комбінація співпадає з одною із дозволених, вектор S =0.
Вектор S ≠0 у випадку, коли мало місце спотворення кодової комбінації, яке можна представити дією вектора помилок Е (таких, що даний код виявити може; при наявності помилок,які не виявляються, S =0).
А саме
S = B HT=(B E)HT=EHT, (42)
де B -вектор спотвореної прийнятої комбінації,
символ - складання за модулем 2.
Декодер лінійного коду складається [1] з k -розрядного регістру із зсувом, r блоків суматорів за модулем 2, r схем порівняння прийнятих перевірочних розрядів з отриманими у ході декодування і аналізатора помилок. Іншими словами, декодер таким же чином, як і кодер, отримує перевірочні розряди на основі інформаційних розрядів, що містяться у інформаційній частині прийнятої кодової послідовності, і порівнює їх з прийнятими перевірочними розрядами. На основі порозрядного порівняння робиться висновок про наявність помилки, а при можливості і про той (ті) розряд(и), де вона має місце. У останньому випадку її можна виправити.
Поліноми (багаточлени) зручно застосувати для опису циклічних кодів. При такому представленні значення двійкових розрядів кодового слова відіграють роль коефіцієнтів при ступенях х. Наприклад, двійкове повідомлення 10011 можна представити у вигляді багаточлена
.
Усі операції з багаточленами здійснюються за законами алгебри, за винятком того, що складання здійснюється за модулем 2: xa xa=0; xa 0=xa; 0 0=0.
Циклічні коди відрізняються високою ефективністю виявлення помилок і порівняно простою реалізацією кодуючих і декодуючих пристроїв у вигляді регістрів з зсувом і зворотними зв’язками.
Циклічний код це код, у якого з приналежної йому комбінації
а0, а1 , а2 ... аn-1,.. an
шляхом циклічної перестановки отримують також дозволену комбінацію
an, a0, a1...an-2, an-1.
Дозволеними комбінаціями циклічного коду є такі комбінації, які діляться на деякий вихідний (утворюючий) багаточлен Р(х), який має ступінь r. Комбінація з помилкою (з діапазону тих помилок, що може виявити даний код) після ділення на Р(х) дасть залишок відмінний від нуля, що свідчить про наявність спотворення у прийнятій комбінації.
Один із можливих варіантів кодування при застосуванні циклічних кодів передбачає, що багаточлен G(x), який відображає двійковий код призначеного для передачі повідомлення, помножують на хr, де r – ступінь поліному Р(х). Це збільшує довжину кодової комбінації на r розрядів, які потрібні для запису у них перевірочних розрядів.
Добуток G(x) 
xr ділять на утворюючий поліном Р(х), а залишок R( x) від цього ділення дописують до G(x) xr, тобто записують залишок у r молодших розрядів(де після зсуву – перемноження на хr записані нулі). Отриманий поліном F(x)= G(x) xr R(x) є комбінацією, що ділиться без залишку на Р(х), тобто він є дозволеною комбінацією даного циклічного коду.
Дійсно, якщо f(x) є частка від ділення G(x) xr на Р(х), то
G(x) xr = f(x) P(x) R(x). (43)
Додавши за модулем 2 до правої та лівої частини R(x) отримуємо
G(x) xr R(x)= f(x) P(x), (44)
Тобто, комбінація F(x) =G(x) xr R(x) дійсно ділиться на Р(х) без залишку.
До циклічних кодів відносяться коди Боуза-Чоудхурі-Хоквінгема (БЧХ).
Кодуючі та декодуючі пристрої циклічних кодів будують на основі регістрів зсуву з зворотними зв’язками.
Такі регістри здійснюють операцію ділення, яка полягає у послідовному складанні за модулем 2 дільника із старшими розрядами діленого або отриманого на черговому кроці ділення залишку. Регістри складаються з тригерів.
Регістр зсуву з зворотними зв’язками будується у відповідності до обраного утворюючого багаточлена за такими формальними правилами (теоретичною базою побудови таких пристроїв є теорія кінцевих автоматів з пам’яттю):
1. Число каскадів (тригерів) регістра обирають рівним степені (
) утворюючого багаточлена.
2. Кількість суматорів за модулем 2 береться на одиницю менше числа ненульових членів утворюючого багаточлена.
3. Входи всіх тригерів регістра позначають хі (і=0, 1, 2). Вихід останнього тригера позначається 
, а вхід першого – х0.
4. Суматори за модулем 2 встановлюються на вході тих тригерів, для яких у формулі утворюючого багаточлена коефіціент при відповідній степені хі має ненульове значення. Наприклад, для Р(х) =х3+х+1 (див. рис. 3) суматори встановлюються на входах першого та другого тригерів (тригерів, що відповідають х0 та х).
5. Вихід останнього тригера з’єднується з одним із входів суматорів.
6. Виходи попередніх тригерів з’єднуються з входами наступних через суматори (в залежності від того, встановлені вони між тригерами чи ні) або безпосередньо.
Кл1
Кл2; Вих
Х0 Х1 Х2
Рис. 3
Робота пристрою відбувається наступним чином.
Нехай, наприклад, при кодуванні діленню на зазначений поліном підлягає комбінація 01010. У вигляді поліному це G(x) = x3 + x. Після множення на x3 отримуємо G(x)∙x3 = x6 + x4. Відповідна двійкова комбінація 01010000 покроково подається на вхід регістру (див. рис. 3) починаючи із старшого розряду (див. Таблицю 1).
