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

Лекція 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 _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, коли на входи логічного елемента «&», тобто вирішального пристрою, надходять дві одиниці. Декодування відповідно до такого коду дозволяє виправляти помилково прийняті інформаційні символи за умови, що між ними будуть проміжки неспотворених символів довжиною не менш чим з чотирьох символів.