Моделі каналів передачі інформації. 3 страница
Таблиця 1
№кроку | Вхідна послідовність | Стан тригерів | ||
X0 | X1 | X2 | ||
На першому кроці старший розряд вхідної послідовності (символ 0) через перший суматор за модулем 2 записується у перший тригер (суматори за модулем 2 перший та другий не впливають на стан тригерів бо перший ключ (Кл1) розімкнений).
На другому кроці цей символ зсувається у другий тригер, а другий символ вхідної послідовності (1) записується у перший тригер.
На третьому кроці символ 0 із другого тригера переноситься у третій тригер, символ 1 із першого тригера у другий, а третій символ вхідної послідовності (0) записується у перший тригер. Після r-того кроку (у прикладі, що розглядається, - після третього) замикається Кл1 і розмикається другий ключ (Кл2). Тому на наступних кроках зворотній зв’язок починає впливати на стан тих тригерів (розрядів), перед якими встановлені суматори за модулем 2.
На четвертому кроці одиниця четвертого розряду вхідної послідовності поступає на перший вхід першого суматора за модулем 2, на другий вхід якого із третього тригера через ключ 1 поступає 0. За результатом додавання цих чисел за модулем 2 на виході суматора формується одиниця, яка записується у перший тригер. Нуль, який знаходився до цього у першому тригері, подається на перший вхід другого суматора за модулем 2, де до нього додається нуль, що прийшов на другий вхід цього суматора через ключ 1. За результатом додавання цих чисел за модулем 2 на виході другого суматора формується нуль, який записується у другий тригер, а одиниця із другого тригера безпосередньо переписується у третій тригер.
На п’ятому кроці нуль п’ятого розряду вхідної послідовності поступає на перший вхід першого суматора за модулем 2, на другий вхід якого із третього тригера через ключ 1 поступає одиниця. За результатом додавання цих чисел за модулем 2 на виході суматора формується одиниця, яка записується у перший тригер. Одиниця, яка знаходилась до цього у першому тригері, подається на перший вхід другого суматора за модулем 2, де до неї додається одиниця, що прийшла на другий вхід цього суматора через ключ 1. За результатом додавання цих чисел за модулем 2 на виході другого суматора формується нуль, який записується у другий тригер, а нуль із другого тригера безпосередньо переписується у третій тригер.
На подальших кроках подібні процедури продовжуються і на n-ному (у даному прикладі на восьмому) кроці отримано залишок, який дорівнює (записуємо починаючи із старшого розряду) 011, що відповідає поліному RI(x)= x+1 і дозволяє сформувати кодове слово завадостійкого коду, заданого поліномом Р(х) =х3+х+1. Для розглянутого прикладу це кодове слово у двійковому вигляді буде мати вигляд 01010011, а у поліноміальному F(x) = x6 + x4 + x + 1.
Для повторення і закріплення матеріалу з теми 3 доцільно самостійно відповісти на такі контрольні питання.
1. Коди, способи представлення кодів, поняття про кодування.
- Що розуміють під кодуванням у широкому та у вузькому смислі?
- Що називають кодом?
- Основні параметри кодів.
5. Різновиди кодів.
6. Цілі кодування.
7. Кодування для каналу без шумів.
8. Мета і принципи побудови завадостійких (коректувальних) кодів.
9. Класифікація, коректувальні властивості і показники якості завадостійких кодів.
10. Блочні циклічні та каскадні коди.
11. Ланцюгові коди.
12. Алгоритми та пристрої кодування і декодування.
13. Підвищення достовірності передачі інформації на основі коректувального кодування.
- Відстань Хемінга і як вона розраховується?
- За якими ознаками класифікують коди?
- Як класифікуються коди за величиною m?
- Як класифікуються коди за основою?
- Як класифікуються коди за величиною n?
- Як класифікуються коди за значністю?
- Як класифікуються коди за порядком передачі символів у часі?
- У чому різниця між паралельним та послідовним кодом?
- Як класифікуються коди за вагою?
- Що таке одиничний код?
- Що таке багатопозиційний код?
- Що таке код Грея?
- Що таке код з постійною вагою?
- Що таке код з перевіркою на парність?
- У чому суть рівномірного та нерівномірного кодування? Дати порівняльну характеристику.
- Позиційні коди.
- Непозиційні коди.
- Составні коди.
- Рефлексні коди.
- Що таке завадостійкий код?
- Що лежить в основі завадостійкого кодування?
- Кодова відстань і як вона визначається.
- Яке максимальне (мінімальне) значення може мати відстань Хемінга?
- Яке максимальне (мінімальне) значення може мати кодова відстань ?
- Яке максимальне (мінімальне) значення може мати кратність помилки у блочному (n, k) коді?
- Що таке блочний код?
- Що таке безперервний код?
- Які коди звуть систематичними?
- Що таке кратність помилки?
- Що таке вектор помилки?
- Що таке поліном помилки?
- Яка різниця між вектором помилки і поліномом помилки?
- Що загального між вектором помилки і поліномом помилки?
- Яку максимальну ступінь може мати поліном помилки при відомій значності коду?
- Яку мінімальну ступінь може мати поліном помилки?
- На що вказує кількість ненульових членів поліному помилки?
- На що вказує кількість нульових членів поліному помилки?
- На що вказують ступені ненульових членів поліному помилки?
- Вкажіть зв’язок кодової відстані з кратністю помилок, що виявляються.
- Поясніть зв’язок кодової відстані з кратністю помилок, що виправляються.
- Довести теоретично, що залишок від ділення A(x)xr на P(x), доданий за модулем 2 до A(x)xr, утворює поліном, який ділиться на P(x) без залишку.
- Яким вимогам повинні задовольняти базові комбінації лінійного коду?
- Що таке примітивний код?
- Що таке рівнодоступний код?
- Яку функцію виконує кодер каналу?
- Яку функцію виконує кодер джерела?
- Як представляють числа у системі залишкових класів?
- Як визначити кількість перевірочних розрядів у кодовій комбінації завадостійкого рівномірного блочного коду?
- Як визначити ступінь утворюючого поліному циклічного коду?
- Які поліноми можуть застосовуватись у якості утворюючих?
- Побудова кодерів (декодерів) циклічних кодів.
- Структура утворюючої матриці лінійного (n,k) коду при розташуванні інформаційних розрядів на початку ( у кінці) кодового слова.
- Як пов’язані між собою утворююча та перевірочна матриці лінійного коду?
- Як можна задати лінійний код?
Здійснити розрахунки при розв’язанні таких задач.
Яку розрядність повинен мати кодер джерела при представленні у двійковому коді алфавіту із 26 (56; 72; ) символів?
Яку мінімальну розрядність повинен мати двійковий код у системі дистанційного управління вибором номеру телевізійного каналу, якщо кабельна мережа телебачення транслює до 150 (120; 60; 30) каналів?
Представити у одиничному коді число 9 (12; 15; 8; 13).
Записати у вигляді поліному за основою 2 (3; 4; 5; 6; 7; 8; 9; 10) число 9 (19; 15; 8; 13; 25; 52; 65; 72; 121; 130).
Представити у двійковому коді числа 9 (19; 15; 8; 13; 25; 52; 65; 72; 121; 130; 250; 312; 500; 502; 510; 1023).
Представити у шістнадцятковому коді числа 9 (19; 15; 8; 13; 25; 52; 65; 72; 121; 130).
Представити у вісімковоиу коді числа 9 (19 15 8 13 25 (52; 65; 72;
Представити у двійково-десятковому коді числа 9 (19 15 8 13 25 (52; 65; 72;
Представити у коді Грея числа від 1 до 8 (16; 32).
Представити у непозиційному коді (у системі залишкових класів) число 9 (19; 15; 81; 103; 240; 325; 415).
Визначити необхідну величину ваги коду з постійною вагою при значності n =7 і необхідності передавати інформацію про 30 (20; 25; 40) подій.
Визначити відстань Хемінга між комбінаціями, якими представляються у двійковому коді за номером літери у алфафіті (у коді МТК №2) послідовності літер АБ і ВД.
Визначити відстані Хемінга між комбінаціями, якими представляються у двійковому коді за номером літери у алфафіті (у коді МТК №2; у коді ASCII; у коді KOI-7; у коді KOI-8) літери Ваших ініціалів.
Порівняти можливості щодо виявлення та виправлення помилок кодів, що мають кодові відстані 4 та 5 (5 та 6; 6 та 7; 7 та 8; 8та 9; 9 та 10)
Перевірити наявність помилки при прийомі кодової комбінації 1010101. Утворюючий поліном має вигляд P(x) = x3 + x2 + 1.
Визначити вигляд інформаційної комбінації, яка повинна видаватися у декодер отримувача інформації (джерела), при прийомі кодової комбінації виду 1011100, що належить завадостійкому циклічному коду, заданому поліномом P(x) = x3 + x2 + 1.
Визначити, чи буде виявлена помилка, поліном якої має вигляд E(x) = x2 + 1, декодером циклічного коду, заданого поліномом P(x) = x4 + x2 + x + 1.
Двійкове число має вигляд А =100110 (011101; 111010; 101101; 111001; 110010; 101011); породжуюча підматриця лінійного коду
Р = .
Визначити вигляд породжуючої матриці, при необхідності розміщення інформаційних розрядів на початку (у кінці) кодової комбініції, вигляд кодової комбініції, що буде сформована кодером, відносну швидкість, надлишковість коду та кратність помилок, які він може виявляти.
Визначити ступінь утворюючого поліному циклічного коду, який повинен забезпечити виявлення помилок кратності 2 (3; 4; 5; 6;7; 8; 9) при довжині інформаційної частини слова 4(5;6;7;8;9;10;11;12).
Визначити ступінь утворюючого поліному циклічного коду, який повинен забезпечити виявлення помилок кратності 2 (3; 4; 5; 6;7; 8; 9) при необхідності передавати двійкові повідомлення із 4(5;6;7;8;9;10;11;12) символів.
Визначити ступінь утворюючого поліному циклічного коду, який повинен забезпечити виправлення помилок кратності 2 (3; 4; 5; 6;7) при довжині інформаційної частини слова 4(5;6;7;8;9;10;11;12).
Визначити ступінь утворюючого поліному циклічного коду, який повинен забезпечити виправлення помилок кратності 2 (3; 4; 5; 6;7) при необхідності передавати двійкові повідомлення із 4(5;6;7;8;9;10;11;12) символів.
Визначити розмірність породжуючої матриці коду, який повинен забезпечити виявлення помилок кратності 2 (3; 4; 5; 6;7; 8; 9) при довжині інформаційної частини слова 4(5;6;7;8;9;10;11;12).
Визначити розмірність породжуючої матриці коду, який повинен забезпечити виявлення помилок кратності 2 (3; 4; 5; 6;7; 8; 9) при довжині кодового слова 4(5;6;7;8;9;10;11;12).
Визначити розмірність породжуючої матриці коду, який повинен забезпечити виправлення помилок кратності 2 (3; 4; 5; 6;7) при довжині інформаційної частини слова 4(5;6;7;8;9;10;11;12).
Визначити розмірність породжуючої матриці коду, який повинен забезпечити виправлення помилок кратності 2 (3; 4; 5; 6;7) при довжині кодового слова 4(5;6;7;8;9;10;11;12).
Визначити ступінь утворюючого поліному циклічного коду та вибрати можливий до застосування утворюючий поліном при умові, що код повинен забезпечувати виявлення помилок кратності 2 (3; 4; 5; 6;7; 8; 9) при довжині інформаційної частини слова 4(5;6;7;8;9;10;11;12).
Визначити ступінь утворюючого поліному циклічного коду та вибрати можливий до застосування утворюючий поліном при умові, що код повинен забезпечувати виправлення помилок кратності 2 (3; 4; 5; 6;7) при довжині інформаційної частини слова 4(5;6;7;8;9;10;11;12).
Відобразити у тримірному просторі розташування кодових комбінацій двійкового тризначного коду; пояснити, які кодові комбінації доцільно використовувати для передачі повідомлень 1 та 0 і які при цьому можливості буде мати код щодо виявлення та виправлення помилок.
Відобразити у тримірному просторі розташування кодових комбінацій двійкового тризначного коду; пояснити, які кодові комбінації доцільно використовувати для передачі повідомлень 1; 2; 3; 4 і які при цьому можливості буде мати код щодо виявлення та виправлення помилок.
Відобразити у двомірному просторі розташування кодових комбінацій двійкового двозначного коду; пояснити, які кодові комбінації доцільно використовувати для передачі повідомлень 1; 2 і які при цьому можливості буде мати код щодо виявлення та виправлення помилок.
Відобразити у лінійному просторі розташування кодових комбінацій двійкових кодів, дозволені кодові комбінації яких мають кодові відстані, відповідно, 2 і 3 ( 2 і 4; 3 і 4; 3 і 5 ); пояснити можливості цих код щодо виявлення та виправлення помилок.
Вивчення теми 4.
При вивченнітеми 4 - методи передачі та прийому повідомлень слід звернути увагу на такі основні визначення, поняття та теоретичні положення.
Повідомлення у системах електро - та радіозв’язку переважно передаються за допомогою гармонічних коливань тої чи іншої частоти. При цьому певний параметр або декілька параметрів сигналу-носія змінюють у відповідності до повідомлення, яке передається. Ці параметри прийнято називати інформаційними. Повідомленням може бути, наприклад, двійкове кодове слово, сформоване на виході кодуючого пристрою.
У сигналі за законом повідомлення може змінюватися:
1) амплітуда – така модуляція зветься амплітудною. Коли передається двійковий сигнал, амплітуда може приймати значення Um (наприклад, при передачі одиниці), і 0 (наприклад, при передачі нуля) на протязі інтервалу часу, відведеного для передачі відповідного символу. Цей інтервал часу називають тривалістю посилки Тпос (або тривалістю сигналу Тс).
У такому разі кажуть, що має місце амплітудна маніпуляція (АМ), тобто
S(t)= . (45)
Такий режим називають також роботою з пасивною паузою (один із символів передається відсутністю сигналу) або амплітудною телеграфією (АТ);
2) частота – така модуляція зветься частотною(у дискретному випадку застосовують термін частотна маніпуляція (ЧМ)). При передачі двійкового повідомлення одиниця передається, наприклад, сигналом з частотою ω1 , а нуль – з частотою ω2
S(t)= . (46)
Такий режим називають також частотною телеграфією (ЧТ)
3) фаза - така модуляція зветься фазовою (у дискретному випадку застосовують термін фазова маніпуляція (ФМ)). При передачі двійкового повідомлення символ одиниця передається сигналом з фазою, наприклад, 0, а символ нуль, відповідно, сигналом з фазою π
S(t)= . (47)
Такий режим називають також фазовою телеграфією (ФТ).
(На відміну від АТ режими ФТ і ЧТ називають роботою з активною паузою.)
Пояснення процесу фазової маніпуляції при передачі двійкового повідомлення виду 01010011 показано на рис. 4 Символ 1 передається сигналом із фазою π, а символ 0 сигналом із фазою 0.
Рис. 4
Фазова маніпуляція з прив’язкою абсолютного значення фази коливання до символу, що передається, застосовується досить рідко із–за можливості зворотного прийому символів (випадковий скачок фази у каналі або у апаратурі може приводити до сприйняття одиниць за нулі, а нулів за одиниці).
Від цього недоліку позбавляються завдяки застосуванню відносної фазової маніпуляції (ВФМ), при якій інформація про символ міститься у різниці фази чергової поcилки по відношенню до фази попередньої посилки. Наприклад, у момент початку посилки, яка відповідає передачі 1, фаза коливання чергової посилки по відношенню до фази коливання попередньої посилки змінюється на π, а при передачі 0 зміна фази відсутня (або навпаки ).
Існують і широко застосовуються відносні види маніпуляції. Наприклад, однократна відносна фазова (ОВФ), при застосуванні якої сигнал, який повинен свідчити про передачу одного із символів, відрізняється за фазою на π порівняно із попередньою посилкою, а при передачі іншого символу така зміна фази не відбувається. На рис. 5 для прикладу розглянуто передачу двійкового повідомлення виду 01010011 у випадку, коли символ 1 передаємо зміною фази відповідного сигналу (посилки) порівняно з попереднім на π, а при передачі символа 0 зміна фази не відбувається.
Рис. 5
=======
У загальному випадку дискретне повідомлення може приймати m станів. Тоді застосовують багатократні види маніпуляції, при яких або один із параметрів сигналу приймає m значень, або використовують m комбінацій значень різних параметрів (з технічної точки зору зручно, коли величина m кратна 2q, де q ціле число більше 1). Багатократну маніпуляцію використовують для підвищення пропускної здатності систем передачі (при фіксованій фізичній швидкості передачі (фіксованій тривалості посилки) збільшення m веде до збільшення пропускної здатності у q разів порівняно з двійковим каналом).
Враховуючи, що кожному стану повідомлення відповідає сигнал з певним значенням параметру(ів), можна вважати, що в системі застосовують m сигналів.
==========
======================================================
3.4.1. Основні положення теорії оптимального прийому дискретних сигналів
Одною із найбільш складних процедур у ході обміну інформацією є демодуляція. По відношенню до дискретних повідомлень її називають розрізненням сигналів. Результатом розрізнення є рішення про те, який із м можливих корисних сигналів поступив у даний момент часу на вхід приймального пристрою.
Для каналу з адитивною завадою n(t) сигнал на вході демодулятора є випадковим процесом виду
x(t)=sr(t)+ n(t), 0≤t≤Tа, (48)
де: sr(t) – один із м можливих сигналів (r=1… м ),
Tа – інтервал аналізу, як правило він дорівнює тривалості сигналу Tс (у термінології систем передачі інформації його називають тривалістю посилки Tпос). У подальшому будемо користуватися позначкою Tс.
Стратегія розрізнення полягає у тому, що множину X усіх можливих реалізацій процесу x(t) розбивають на м підмножини Xr, які не перетинаються. У залежності від того, якій із цих підмножин належить прийнята реалізація x(t), приймається рішення, що прийнятим є сигнал si(t) із сукупності можливих sr(t).
При м=2 (передача двійкових повідомлень) модель процесу на вході має вигляд
x(t)=As1(t)+(1-A)s2(t)+n(t), 0≤t≤Tс, (49)
де: s1(t) – сигнал, який застосовується для передачі, наприклад, символа 1,
s2(t) – сигнал, який застосовується для передачі, відповідно, символа 0,
A – випадковий невідомий множник, який приймає значення 1 або 0 в залежності від того, який із символів породжує у черговий момент часу джерело повідомлення.
Враховуючи той факт, що повідомлення носить випадковий характер і сигнали, які переносять символи приймаються на фоні завади, яка теж є випадковим процесом, задача розрізнення сигналів є частковим випадком загальної задачі перевірки статистичних гіпотез. При застосуванні роботи з пасивною паузою задача розрізнення переходить у задачу виявлення.
Рішення приймається у кінці інтервалу Tс на основі спостереження реалізації процесу x(t) при двох взаємно виключаючих умовах: а) умова H1, тобто A=1 (передавався сигнал s1(t)); б) умова H2, тобто A=0 (передавався сигнал s2(t)). Це рішення не може бути безпомилковим оскільки заздалегідь не відомо, який із сигналів передається, а прийом ведеться при наявності завад і флуктуацій. Але рішення повинно бути оптимальним (у деякому розумінні).
Апріорні відомості про параметр A (про гіпотези H1 і H2 )можуть бути: 1) відомими – відомі апріорні безумовні імовірності P(H1) і P(H2); 2) ці імовірності невідомі. Розв’язуючою функцією є Â(x), яка приймає значення 1, коли процес x(t) потрапив у підмножину X1, і 0, коли процес x(t) потрапив у підмножину X2. При наявності завад і флуктуацій кожній умові може відповідати одне з двох рішень: а) справедлива гіпотеза Ĥ1, тобто Â(x)=0 (прийнято сигнал s1(t)); б) справедлива гіпотеза Ĥ2, тобто Â(x)=0 (прийнято сигнал s2(t)). Таким чином, можливі чотири ситуації суміщення випадкових подій (рішень і умов). Кожна з цих ситуацій має свою імовірність: 1) P(Ĥ1,H1) - суміщення факту передачі першого сигналу та рішення про прийом першого сигналу; 2) P(Ĥ2,H1) - суміщення факту передачі першого сигналу та рішення про прийом другого сигналу; 3) P(Ĥ2,H2) - суміщення факту передачі другого сигналу та рішення про прийом другого сигналу; 4) P(Ĥ1,H2) - суміщення факту передачі другого сигналу та рішення про прийом першого сигналу.
За відомими правилами їх можна представити через умовні та безумовні імовірності
P(Ĥk,Hr)= P(Ĥk/Hr)∙P(Hr), (k,r=1,2), (50)
де: P(Ĥk/Hr) умовна імовірність прийняття рішення про прийом k-го сигналу при передачі r-го сигналу;
P(Hr) безумовна імовірність передачі r-го сигналу.
Серед умовних імовірностей дві: (P(Ĥ1/H1) і P(Ĥ2/H2))відповідають правильним рішенням, а дві: (P(Ĥ2/H1) і P(Ĥ1/H2)) є умовними імовірностями помилкових рішень. Для кожної з умов справедливі такі співвідношення:
P(Ĥ1/H1) = 1 - P(Ĥ2/H1); (51)
P(Ĥ2/H2) = 1 - P(Ĥ1/H2). (52)
Умовні імовірності помилкових рішень P(Ĥ2/H1) і P(Ĥ1/H2) будемо позначати Pпом(Ĥ2/H1) і Pпом(Ĥ1/H2), відповідно.
Припустимо, що відомі умовні багатомірні щільності імовірності (функції правдоподібності) w(x/H1) та w(x/H2) вектору x, проекції якого x1, x2,…….xM є відліками процесу x(t). Тоді інтегруванням першої щільності по області X2 отримаємо
Pпом(Ĥ2/H1) = ∫ w(x/H1)dx, (53)
X2
а інтегруванням другої щільності по області X1 отримаємо
Pпом(Ĥ1/H2) = ∫ w(x/H2)dx. (54)
X1
Як бачимо з (53) і (54) імовірності помилок у значній мірі залежать від способу розподілення множини X на підмножини X1 та X2 Між тим, не є очевидним, що цей спосіб повинен обиратися лише із міркувань отримання певних значень імовірностей Pпом(Ĥ2/H1) та Pпом(Ĥ1/H2), наприклад, їх мінімізації. Вибір способу може залежати від інших показників системи. Тому перш ніж розв’язувати задачу розрізнення сигналів треба визначити критерій оптимальності. Це залежить від характеру задачі та від наявності відомостей про апріорні імовірності.
У загальному випадку необхідно враховувати наслідки як помилкових, так і правильних рішень. Для цього вводять функцію втрат (або середній ризик)
R(s,Â(x)) = r11P(Ĥ1,H1) + r12P(Ĥ2,H1) + r22P(Ĥ2,H2) + r21P(Ĥ1,H2), (55)
де r11, r12, r22, r21 – коефіцієнти втрат при прийнятті рішення на користь певної гіпотези при певній умові.
Враховуючи (50), (51), (52) вираз (55) можна представити
R(s,Â(x)) = r1 P(H1) + r2 P(H2), (56)
де: - r1 та r2 - умовні ризики при відповідних умовах, які дорівнюють
r1 = r11 [1 - Pпом(Ĥ2/H1)] + r12 Pпом(Ĥ2/H1); (57)
r2 = r22 [1 - Pпом(Ĥ1/H2)] + r21 Pпом(Ĥ1/H2). (58)
Доцільно обрати таку стратегію прийняття рішення про розділення множини X на підмножини, щоб середній ризик був мінімальним. Така стратегія зветься оптимальною байєсовською, а відповідний критерій оптимальності - критерієм мінімуму середнього ризику ( критерій Байєса). Він є найбільш загальним.
Виконавши відповідні перетворення (53)...(58) можна показати, що стратегія прийняття рішення у рамках цього критерію має вигляд:
при Λ(M)(x) ≥ Λ0 справедлива гіпотеза H1;
(59)
при Λ(M)(x) < Λ0 справедлива гіпотеза H2,
де: Λ(M)(x) = w(x/H1)/w(x/H2) – відношення правдоподібності;(60)
– поріг прийняття рішення. (61)