Системи документального електрозв’язку

Тема розділу: Захист інформації від спотворень

Лекція 1. Корегуючі коди. Класифікація. Параметри. Згортувальні коди.

 

Корегуючі коди – це такі коди, в які формуються на основі інформаційної послідовності символів а₁,а₂... а_к послідовність перевірочних символів в₁, в₂... в_r. в кодері. За допомогою введеної збитковості декодер має можливість в залежності від вибраного коду і алгоритму декодування, виявляти чи виправляти помилково прийняті інформаційні символи, які створені в результаті дії різного роду перешкод в каналі зв’язку.

В класифікаційній діаграмі розглянемо тільки ті коди, що знаходять найбільше застосування в системах документального електрозв’язку.

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

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

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

Для лінійних (n, k) кодів відносяться такі коди, в яких r = n- k збиткових символів формується із k інформаційних за допомогою лінійних операцій, тобто операцій додавання та переключення.

Для двійкових кодів додавання виконується по mod2, тобто 0+1=1, 1+0=1, 0+0=0 і 1+1≡0, а перемноження здійснюється в звичайному порядку.

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

mod2 j=1, 2,…, r

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

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

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

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

Значну частину лінійних кодів займають циклічні коди, до них відносяться:

–  коди Хемінга;

–  коди БЧХ (Боуза-Чоудхури-Хоквингема);

–  коди з мажоритарним декодуванням (ЦКМД), яким властива проста схемна реалізація декодера;

–  коди Файра (виправляють пакети помилково прийнятих кодових символів).

Згортувальні коди як і блокові можна розділити на систематичні та несистематичні. Перші декодуються відносно простим методом – пороговим (ЗКПД), а другі – з використанням алгоритму послідовного декодування (ЗКАПД) і алгоритму Вітербі (ЗКАВ). Несистематичні коди з алгоритмом декодування Вітерці знаходять широке застосування в телекомунікаційному обладнанні.

 

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

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

,

де  – біноміальні коефіцієнти;

, якщо , то найбільш вірогідні помилки малої кратності.

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

,

де ; j, l = 1, 2,...,2^k; – номери дозволених КК.

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

Для лінійних кодів. враховуючи, що в коді завжди є нульова КК, кодова відстань визначається мінімальною вагою КК,

Максимальна кратність виявлення помилок ,

, (1)

а виправлення: ; (2)

Теорема. Якщо d₀ парне, то код може виправляти  помилок і виявляти  помилок.

Рис. 1

На рисунку 1 приведена геометрична модель найпростішого коригувального коду (4, 3) з парним числом одиниць, представлена на площині, де всі дозволені КК зображені у виді крапок, що є центрами окружностей з радіусами d = 1. Заборонені КК відображені крапками на окружностях, що завжди є загальними для двох суміжних окружностей.

З рис. 1 видно, що мінімальна відстань між двома дозволеними КК дорівнює двом одиницям по Хемінгу, тобто d₀ = 2. Тут дозволені КК мають єдине відображення – центри окружностей, а кожній заборонений КК відповідають дві дозволені КК, у чому виявляється невизначеність при декодуванні таких КК. Принцип виявлення помилок при використанні коду (4, 3) очевидний. Якщо в результаті дії перешкод дозволена КК "переходи" з центра на окружність (d = 1), то таке викривлення в місці прийому завжди буде виявлено за структурою коду. Перехід з одного центра окружності в центр будь-якої іншої окружності (d = 2 чи 4) приводить до невиявленої помилки. Такий код, як видно з приведеного рисунку, дозволяє виявляти всі помилки непарної кратності.

Подібно до коду (4,3), на рис. 2 а приведений тільки фрагмент геометричного представлення коду з d₀ = 3, а на рис. 2 б – коду з d₀ = 4. З наведених рисунків видно, що перший код дозволяє виправляти однократні помилки, а інший – дає можливість, окрім виправлення однократних помилок ще й виявлення двократних помилок, що переконує у справедливості виразів (1) і (2).

а) б)

Рис. 2

Код з парним числом одиниць має один перевірочний символ, який визначається:

, де j=1, a g_ji=1

d₀=2, значність коду n=k+1; збитковість .

Такий код дозволяє виявити всі помилки непарної кратності:

,  – найближче менше непарне число до n

.

Для КПВ

; ;

;

;

Швидкість коду ;

Збитковість коду ;

Згортувальні коди – це такі коди, в яких кодова послідовність на виході кодера може бути представлена як дискретна "згортка" по mod2 інформаційних символів і імпульсної реалізації кодера, тобто:

,

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

і = 0, 1, 2, ... – порядковий номер символів на вході та на виході;

L – об’єм пам’яті кодера;

x (i-l) – послідовність інформаційних символів з врахуванням затримки в комірках пам’яті кодера;

h (l) – імпульсна реакція кодера на дію - ...000010000...

Рис. 3

Відносна швидкість коду

 – збитковість;

 – найбільша кількість комірок в регістрі кодера;

 – довжина кодового обмеження;

Інформаційна довжина слова

 – кількість вихідних символів кодера, яке обирається при кодуванні  інформації.

Код характеризується двома параметрами () (6,3) (9,6) (9,3)

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

Процес кодування полягає в наступному. На вхід кодера надходить послідовність інформаційних символів а_і, наприклад, 0010110010, швидкість модуляції якої В₁. У результаті підсумовування по mod 2 символів, що приходять у деякі моменти часу і попередніх їм, утвориться послідовність перевірочних символів в_і. За допомогою перемикача К1 послідовності а_і і в_і, поєднуються в одну с_2і, формування якої має вид:

При цьому повинно бути зрозуміло, що швидкість модуляції на виході кодера В₂ = = 2В₁. Далі ця послідовність надходить у дискретний канал.

У декодері кодова послідовність , розділяється на дві –  і , що можуть у деякі моменти часу відрізнятися від  і , через дію перешкод у каналі зв'язку. Після поділу двійкові символи  надходять на вхід кодера-декодера (КД), схема якого збігається зі схемою кодера на передавальному кінці ДК. У результаті на виході суматора СМ2 утворюється послідовність , яка при відсутності спотворень сигналу в ДК буде збігатися з послідовністю . Сумматор СМЗ формує синдромну послідовність Si, що при вище зазначених обставинах містить тільки нульові символи.

Розглянемо тепер процес виправлення помилково прийнятого демодулятором кодового символу. Припустимо, що в послідовності  п'ятий інформаційний символ спотворений (1→0), що підкреслений. Виправлення помилкове прийнятого символу виконується суматором СМ4, коли на входи логічного елемента «&», тобто вирішального пристрою, надходять дві одиниці. Декодування відповідно до такого коду дозволяє виправляти помилково прийняті інформаційні символи за умови, що між ними будуть проміжки неспотворених символів довжиною не менш чим з чотирьох символів.

Тема розділу: Адаптивні системи передачі.

 

Лекція 2.  Класифікація. Алгоритмічний опис. Системи з інформаційним зворотнім зв’язком

 

Зворотнім зв’язком можуть бути охоплені різні частини системи:

Рис.1

1.  канал зв’язку, при цьому по ЗК передають відомості про приймальний сигнал до прийняття якогось рішення;

2.  дискретний канал, при цьому по зворотньому каналу зв’язку передаються рішення, прийняті першою вирішувальною системою РС1 на основі аналізу одиничних елементів сигналу;

3.  канал ПД, при цьому по ЗК передаються рішення, прийняті другою РС2 на основі кодових комбінацій.

В першому випадку для контролю каналу зв’язку такі пристрої: детектори якості, які аналізують ті чи інші параметри сигналу, який приймається (амплітуду, частоту, довжина) або рівень перешкод. При цьому по ЗК можуть передаватись команди на зміну параметрів сигналів, які передаються: потужності, спектрального складу, темпа передачі, збитковості коду. На передаючій стороні повинні бути передбачені відповідні органи дії на джерела сигналів: регулятори потужності, коректори, кодоперетворювачі, які керуються сигналами, які поступають по ЗК.

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

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

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

 

Системи зв’язку з зворотнім зв’язком можна класифікувати по типу зворотнього зв’язку, засобу кодування, методу перевірки прийнятих сигналів, величині коефіцієнта повторення, ємності пам’яті вирішувального пристрою і способу повторення робочих сигналів. В залежності від того, де приймається рішення – на передаючій чи на приймальній стороні – розділяють адаптивні системи ПД з інформаційним зворотним зв’язком, вирішувальним (ВЗЗ) і комбінованим ЗЗ.

Рис. 2

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

Системи з ІЗЗ дозволяють одержати високу якість зв’язку при малі збитковості передачі ( мале), якщо рівень перешкод в зворотньому каналі низький. В протилежному випадку створення квитанції даже при безпомилковому прийомі робочих сигналів робочих сигналів буде визивати дублювання повідомлень. Крім цього в зворотному каналі можливі створення типу "зсуву" (дзеркальні помилки), коли спотворена квитанція відповідає неспотвореним робочим сигналам, що викликає помилкову команду підтвердження. Ці особливості системи ПД з ІЗЗ понижують їх технічні показники порівняно з другими системами зі зворотніми каналами. Їх називають ретрансляційними, є повні і укорочені.

Рис. 3

В системах ПД з ВЗЗ рішення виробляється на приймальній стороні і по зворотньому каналу посилається не квитанція, а команда запиту на повторення (прийнятий сигнал визнано недостовірним), або на передачу наступної команди (прийнятий сигнал визнано достовірним). Такі системи характеризуються значно меншою загрузкою зворотнього каналу, по якому потрібно посилати тільки два сигнали – "перезапит" і "підтвердження". Це полегшує здійснювати режим роботи систем ВЗЗ по навчальним дуплексним каналам при відносно не великому ускладненню обладнання.

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

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

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

Системи з ЗЗ діляться на системи з обмеженим числом повторювань та з необмеженим числом.

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

Наявність помилок в ЗК приводить до того, що в системах з ВЗЗ виникають специфічні втрати вірності, а саме поява лишніх кодових комбінацій – вставок та пропадання кодових комбінацій – випадання.

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

Канали зв’язку організовуються за допомогою ЧРК, ВРК, або структурного методу розділення (для сигналу перезапиту використовується спеціальна кодова комбінація).

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

Системи з очікуванням – після передачі КК завжди очікують будь-якого сигналу ЗЗ – підтвердження чи запиту. Після сигналу підтвердження система передає наступну КК. а при отриманні сигналу "запит" блокує передачу наступної кодової комбінації і передає повторно попередню КК. Передачу наступної КК система починає тільки після отримання сигналу підтвердження по раніше перезапитаній КК.

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

Порівняння систем ВЗЗ та ІЗЗ. Нехай в двох системах використовується завадостійкий код (n,k). Якщо канали прямого зворотнього напрямків передачі однакові і помилки в них незалежні, то ймовірності однакової трансформації перевірочних розрядів в двох каналів в двох каналах однакові. Тому виявляюча спроможність коду не залежить від того, де відбувається порівняння перевірочних розрядів: на передаючій (в системі з ІЗЗ) або на приймальній (в системі з ВЗЗ) стороні системи.

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

Середня швидкість передачі повідомлень по прямому каналу в системі з ВЗЗ менше, ніж в системі з ІЗЗ, оскільки в перших з корисним блоком довжиною К додатково передається n-k перевірочних символів.

Якщо завадостійкість ЗК вище, ніж прямого, то вірність передавання в системах з ІЗЗ також вище, ніж в системах з ВЗЗ.

Порівняння систем передачі по швидкості. порівняння СПД із використанням завадостійких коригуючих кодів (ЗКК) і систем з вирішальним зворотним зв'язком (ВЗЗ) здійснюється по відношенню до раніше розглянутого циклічного коду (з довжиною базових кодових слів n та довжиною іх інформаційної частки m_k чи m).

1. Для систем, що використовують завадостійкий коригуючий код (ЗКК), швидкість передачі визначається відносною швидкістю коду R_k, тобто

R_k, = m_k/n,

де n —загальне, а m_k— число інформаційних символів у базовому кодовому слові (БКС).

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

s_г ≤ 1/t_c,

де: t_c — час, необхідний для передачі БКС;

s_г — граничне значення інтенсивності завад, що приводять до пакетів помилок, число яких не перевищує одного пакета на БКС.

Час t_c, необхідний для передачі БКС, визначається з виразу:

t_c = n/В,

де: В — швидкість передачі даних.