Розробка методів мажоритарного декодування з поліпшеними ймовірнісно-часовими характеристиками

Дипломна робота

«Розробка методів мажоритарного декодування з поліпшеними ймовірнісно-часовими характеристиками»

Введення

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

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

Виділяють дві основні причини виникнення помилок при передачі інформації в мережах:

• збої в якійсь частині обладнання мережі або виникнення несприятливих об'єктивних подій в мережі (наприклад, колізій при використанні методу випадкового доступу в мережу). Як правило, система передачі даних готова до такого роду проявів і усуває їх за допомогою планово передбачених коштів;

• перешкоди, викликані зовнішніми джерелами і атмосферними явищами. Перешкоди - це електричні обурення, що виникають у самій апаратурі або потрапляють в неї ззовні. Найбільш поширеними є флуктуаційні (випадкові) перешкоди. Вони являють собою послідовність імпульсів, що мають випадкову амплітуду і наступних один за одним через різні проміжки часу. Прикладами таких перешкод можуть бути атмосферні і індустріальні перешкоди, які зазвичай виявляються у вигляді одиночних імпульсів малої тривалості і великої амплітуди. Можливі й зосереджені перешкоди у вигляді синусоїдальних коливань. До них відносяться сигнали від сторонніх радіостанцій, випромінювання генераторів високої частоти. Зустрічаються і змішані перешкоди. У приймальнику перешкоди можуть настільки ослабити інформаційний сигнал, що він або взагалі не буде виявлений, або спотворений так, що «одиниця» може перейти в «нуль» і навпаки.

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

Серед численних методів захисту від помилок виділяються три групи методів: групові методи, завадостійке кодування і методи захисту від помилок в системах передачі зі зворотним зв'язком.

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

Суть мажоритарного методу, давно і широко використовується, полягає в наступному. Кожне повідомлення обмеженою довжини передається кілька разів, частіше всього три рази. Прийняті повідомлення запам'ятовуються, а потім проводиться їх поразрядное порівняння. Судження про правильність передачі виноситься за збігом більшості з прийнятої інформації методом «два з трьох».

Робота Хеммінга стала каталізатором ланцюгової реакції висунення нових ідей в області декодування, яка почалася з 1954 року. Американський вчений І.С. Рід був першим, хто використовував мажоритарне декодування кодів Ріда - Маллера. При мажоритарному декодуванні для кожного інформаційного символу формується непарне число оцінок шляхом додавання за модулем 2 певних комбінацій символів прийнятого коду. Рішення про істоту прийнятого символу приймається за мажоритарним принципом - якщо більша кількість оцінок дорівнює 1, то приймається саме таке рішення. У 1963 році Дж.Л. Мессі [13, 25] встановив загальні принципи побудови та декодування подібних кодів. Перевагою мажоритарно Декодовані кодів є надзвичайна простота і швидкодія алгоритмів декодування. Проте клас таких кодів дуже малий, і ці коди слабше інших. Значний внесок у створення теорії побудови мажоритарно Декодовані кодів внесли в 1965 році радянські вчені В.Д. Колісник і Є.Т. Мірончіков. [7, 35]

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

1. Підвищення ефективності використання каналів передачі даних (підвищення ймовірнісно-часових характеристик декодування)

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

Розглядаючи завдання підвищення ефективності використання каналів передачі даних, можна виділити три найважливіші проблеми:

1. Проблему забезпечення необхідної вірності Р _тр, прийнятої і видаваної споживачеві після декодування інформації. При цьому будемо розуміти, що ймовірність помилки Р _ош в такій інформації не повинна перевищувати при роботі з будь-якого з використовуваних каналів наперед заданої величини Р _тр. Зазвичай завдання забезпечення необхідної вірності прийнятої інформації визначають як «підвищення вірності», тобто як зниження ймовірності Р _ош щодо ймовірності помилки у використовуваному дискретному каналі, описуваної ймовірністю спотворення символу _0. Для цієї мети використовують коди з виявленням помилок, за допомогою яких виявляють і бракують кодові послідовності з помилками, а також коди з виправленням t і менш помилок. У разі виявлення помилок величина Р _ош визначається ймовірністю того, що використовуваний код не бракує спотворену кодову послідовність (не виявляє помилку) при роботі з даного каналу або класу каналів зв'язку. Питання про гарантії необхідної величини Р _тр зводиться до аналізу виявляє здатності використовуваного коду в розглянутому класі каналів зв'язку і до методів вибору типу і параметрів (синтезу) коду, що забезпечує Р _тр в будь-якому з використовуваних каналів зв'язку.

Широко використовуються для виправлення помилок виконавчі і q-ічние алгебраїчні коди з кодовою відстанню d виправляють всі вектори помилок з вагою не більш t = (d -1) / 2. З імовірністю , Де P (i, n) - ймовірність виникнень рівно i помилок у кодовому блоці довжиною п, такий код видає споживачеві інформацію без помилок. При числі помилкових символів S> t може відбуватися або відмова від декодування, коли декодер видає з ймовірністю Р _ст сигнал про необхідність стирання кодового блоку, або має місце декодування з помилкою, після чого перекручена інформація з числом перекручених символів S '≶ S видається споживачеві з ймовірністю Р _ош.

Якщо вважати, що код не виправляє помилок кратності S> t, то Р _ст + Р _ош = Р ₂ = . У цьому випадку проблема забезпечення необхідної вірності передачі складається з рішення наступних завдань:

а) визначення значень ймовірностей Р _ош і Р _ст для конкретного коду і різних характерних інтервалів кратності помилки від t +1 до d і вище;

б) оцінки властивостей дискретного каналу шляхом опису його параметрів, найпростішими з яких є значення P (i, n);

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

Рисунок 1 - ілюструє відміну завдання забезпечення необхідної вірності (крива 1) від завдання підвищення вірності (крива 2). При підвищенні вірності забезпечується Р _ош <Р _тр тільки при Р ₀ <Р _гр. При забезпеченні необхідної вірності будь-яку якість каналу (аж до його обриву) не збільшує ймовірність Р _ош вище Р _тр, зводячи всі випадки неможливості правильного декодування блоку до відмови від декодування, зберігаючи здатність видачі споживачеві інформації при поліпшенні стану каналу, при. якому методи прийому і забезпечення необхідних ймовірнісно-часових характеристик обміну інформації (проблема 2) призводять до успішного декодуванню та видачі інформації споживачеві. Для такого каналу повна група подій містить наступні події:

• правильний прийом кодового блоку, який не був спотворений необхідної в каналі або в якому правильно виправлена ​​помилка з імовірністю Р _п.пр;

• сталася помилка декодування і кодовий блок з помилкою виданий споживачеві з імовірністю Р _ош;

• відбулася відмова від декодування з імовірністю Р _отк.

Віднісши число фіналів кожної події до числа переданих блоків, маємо Р _п.пр + Р _ош + Р _отк = 1. Враховуючи, що інформація видається споживачеві в перших двох випадках, імовірність прийому Р _пр = Р _п.пр + Р _ош.

Рис. 1. Зіставлення завдань підвищення та забезпечення потрібної вірності передачі

Для будь-якого коду, що забезпечує необхідну вірність, можна розглядати дві області: область прийому і область відмови. В області прийому ймовірність помилки дорівнює нулю. Для кодів з виявленням помилки це випадок, коли кодовий блок не спотворений з імовірністю Р (0, п), а для кодів з виправленням помилок - це виникнення не більше t помилок. При цьому Р _ош = 0; Р _пр = Р _п.пр; Р _отк = 0. В області відмови (при кратності помилки, що перевищує t) Р _п.пр = 0; Р _пр = Р _ош; Р _отк = 1-Р _ош. Відзначимо що для кожної з цих областей поняття фінальної ймовірності помилки Р _ош.ф як відношення числа блоків з помилкою декодування до числа прийнятих блоків є безглуздим. Дійсно, за визначенням, в області прийому Р _ош.ф = 0. В області відмови прийом блоку можливий тільки при помилковому декодуванні його, тому Р _ош.ф = 1, причому для будь-якого коду, незалежно від його надмірності і того, яку частину помилок він виявляє або виправляє.

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

Як ймовірнісно-часових характеристик (ВВХ) будемо в першу чергу розглядати дві головні характеристики:

а) відносну швидкість передачі інформації по каналах зі зворотним зв'язком R = (k / n) (1-Р _ст), де п, k - параметри використовується (п, k) - коду; Р _ст - ймовірність стирання чергового кодового блоку через через виявлення в ньому Помилки, що не відповідним кодом помилок або через особливості використовуваного алгоритму зворотного зв'язку;

б) імовірність доведення повідомлення заданого об'єму V в певних умовах за час T-Р _дов (V, Т). Ця характеристика передбачає доведення повідомлення із заданою вірогідністю Р _тр і може використовуватися в першу чергу в симплексних каналах, а також у дуплексних каналах, використовуваних для темпової передачі інформації, або передачі в реальному масштабі часу.

3. Проблему складності реалізації пристроїв, які здійснюють найбільш трудомістку обробку дискретної інформації, до якої можна віднести кодування і декодування завадостійких кодів, у тому числі при використанні паралельних каналів / багаторазового передачі одного і того самого повідомлення. До цієї ж проблеми слід віднести завдання уніфікації апаратури передачі даних, маючи при цьому на увазі створення таких методів завадостійкого кодування і передачі інформації і реалізує їх апаратури, які могли б шляхом зміни перебудовуються параметрів апаратури забезпечувати роботу з дуплексним і симплексним каналах, з виправленням і виявленням помилок завадостійким кодами, використання широкого набору типів дискретних каналів з ​​різною інтенсивністю і розподілом потоків помилок. При цьому дуже важливо, щоб заміна дискретного каналу вимагала мінімальних відомостей про його якість і потоках помилок в каналі. У самому кращому випадку відомостей про потік помилок не потрібно взагалі, а рішення про придатність використовуваного каналу виробляються на основі критеріїв, закладених в алгоритмі передачі інформації (алгоритмі декодування) коду та пов'язаних з неможливістю виконання необхідних значень наведених вище основних ВВХ.

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

Виявлення помилок за допомогою блокових (п, k) - кодів характеризується меншою ніж виправлення помилок двійковими кодами, залежністю ймовірності невиявленої помилки Р _ош від властивостей вихідного дискретного каналу. Такі коди, мають кодове відстань d, за визначенням коду виявляють всі помилки ваги t <d з числом невиявлених помилок, що дорівнює кількості ненульових кодових слів 2 ^k -1. Для найбільш конструктивних з цього класу циклічних кодів відомо і широко вживається виявлення помилок за допомогою розподілу полінома, що відображає кодову послідовність, на фіксований породжує поліном коду g (X) ступеня п.

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

Однак не можна строго затверджувати, що блокові коди з виявленням помилок забезпечують Р _тр в довільному каналі. На практиці для оцінки ймовірності невиявленої помилки блоковими кодами [11, 38] користуються двома основними виразами:

Р _ош ≈ P (≥ 1, n) • 2 ^{- (n - k),} (1)

Р _ош ≈ P (≥ d, n) • 2 ^{- (n - k)} (2)

Обидві ці оцінки прийнятні для інженерних розрахунків для відносно хороших каналів і кодів з досить великим числом надлишкових символів r = n-k, але кожна має недоліками, пов'язаними з неможливістю обліку властивостей конкретних кодів з їх спектрами ваг. Формула (1) правильно відображає число векторів невиявленої помилки і їх частку від всіх 2 ⁿ векторів довжини п, але не враховує тієї обставини, що всі помилки кратності від 1 до d-1 і від п-d +1 до п такими кодами завжди виявляються .

Формула (2), навпаки, враховує частково остання обставина для помилки кратності до d-1 включно, але дає свідомо оптимістичний результат, так як припускає, що кількість незнайдених помилок менше 2 ^k -1, що не так. Справді, формула (2) передбачає відкидання з 2 ⁿ векторів помилки тих векторів, вага яких менше d і враховує тільки ^{(2 - (n - k))} - ю частку інших векторів, що менше 2 ^k -1.

Перешкодостійкі коди для забезпечення необхідної вірності переданої інформації мають у цей час досить широку сферу застосування. Розвиток і широке використання мереж ЕОМ, інформаційно-обчислювальних мереж (ІТТ), глобальних інформаційних мереж вимагають розробки ефективних методів передачі та захисту дискретної інформації від помилок у каналах зв'язку. Прагнення упорядкувати процедури взаємодії абонентів в ІТТ стало причиною створення Міжнародною організацією стандартів (МОС) так званої еталонної моделі взаємодії відкритих систем (ЕМВОС). Ієрархічний поділ функцій обробки інформації, що передається призвело до використання поняття рівня, що виконує певну логічну функцію. Сукупність правил (процедур) взаємодіючих об'єктів ІТТ однойменних рівнів називають протоколом. Рекомендована в ЕМВОС сукупність протоколів містить сім наступних рівнів: фізичний, рівень каналу ПД або ланки даних, мережний, транспортний, сеансовий, представницький і прикладний. Причому рівень каналу ПД має завжди, а транспортний та прикладної рівні, як правило, засоби контролю вірності прийнятої інформації за допомогою завадостійкого коду, що допускає просту програмну реалізацію в ЕОМ.

При обміні інформацією в мережах ЕОМ, що використовують на ребрах мережі різні за фізичну природу і якості каналу зв'язку, методи захисту від помилок повинні забезпечувати необхідну вірність циркулюючих даних при роботі з будь-якого з каналів зв'язку. Подібні вимоги пред'являються до каналів ПД, використовуваним в системах телемеханіки та телеуправління, в АСУ різного типу. Найбільш складною є задача забезпечення необхідної вірності при роботі по каналах низької якості, коли ймовірність спотворення двійкового символу P _0> 10 ^-2, і в каналах без зворотного зв'язку при використанні кодів з виправленням помилок.

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

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

2. Завадостійке кодування інформації

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

Здатність коду виявляти і виправляти помилки обумовлена ​​наявністю надлишкових елементів у кодовій комбінації r = n - k.

У цьому випадку загальне число можливих кодових комбінацій буде

, Число дозволених комбінацій , А заборонених .

Спотворення інформації в процесі передачі зводиться до того, що деякі з переданих елементів замінюються іншими - невірними. При цьому для систематичних кодів з випадків передачі можливо випадків переходу в інші дозволені комбінації, що відповідає необнаружіваемие помилок, і випадків переходу в недозволені комбінації, які можуть бути виявлені [5, 65]. Отже, частина упізнаних помилок від загального числа можливих випадків передачі складе

.

Наприклад, при використанні одного надлишкового елемента (r = 1) частину упізнаних помилок становить

.

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

Процедура упізнання спотвореної кодової комбінації в цьому випадку буде полягати в її порівнянні з усіма кодовими комбінаціями. Коли відбудеться збіг з одного з комбінацій, що належать , Здійсниться ототожнення спотвореної комбінації з i-ї дозволеної, тобто виправлення помилки. Помилка буде виправлена ​​в випадках з усіх можливих. Відношення числа виправляються кодом помилкових кодових комбінацій до числа виявлених помилкових комбінацій одно [5, 67]:

.

Ступінь відмінності будь-яких двох кодових комбінацій характеризується відстанню між ними в сенсі Хеммінга, званим кодовою відстанню. Воно виражається числом елементів, в яких комбінації відрізняються одна від одної, і позначається через d. Мінімальна кількість елементів, в яких всі комбінації коду відрізняються один від одного, називається мінімальним кодовою відстанню d _0. Мінімальна кодова відстань - параметр, що визначає завадостійкість надлишкового коду. У загальному випадку для виявлення всіх помилок до -Кратних включно мінімальне кодова відстань

. (3)

Мінімальна кодова відстань, необхідне для одночасного виявлення та виправлення помилок:

, (4)

де t - число виправляє помилок.

Для кодів, тільки виправляють помилки:

(5)

Співвідношення (3), (4) і (5) визначають лише кратність гарантійно виявляє і виправляє помилок. Зазвичай коди виявляють і виправляють частину помилок і більше високої кратності.

До найбільш уживаним надлишковим кодами можна віднести блокові і безперервні коди.

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

Рівномірні блокові коди характеризуються однаковою довжиною дозволених кодових слів, на відміну від нерівномірних кодів.

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

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

Нелінійні коди не володіють цією властивістю. Прикладом нелінійних кодів є код з постійною вагою, застосовуваний в телеграфії. У деяких випадках лінійні коди називають груповими, що обумовлено математичним описом підмножини дозволених кодових слів довжини n як підгрупи в групі всіх слів довжини n. Лінійний код, в якому інформаційні та перевірочні елементи розділені і розташовані на суворо визначених позиціях, називається систематичним, на відміну від несистематичних кодів, у яких не можна в явному вигляді виділити інформаційні та перевірочні елементи. Систематичні коди набули найбільшого поширення. Систематичні коди, як правило, позначаються (n, k) - кодами і включають: коди з перевіркою на парність, коди Хеммінга, циклічні коди, коди з повторенням, ітеративні коди, каскадні, коди Ріда-Малера, децікліческіе коди і багато інших [3 , 32].

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

3. Циклічні коди

3.1 Завдання циклічних кодів

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

Алгебраїчна структура циклічних кодів вперше була досліджена Боуз, Чоудхурі і хоквінгема, тому вони відомі як БЧХ-коди. Ці коди характеризуються наступними властивостями [7, 110]: довжиною кодових послідовностей

(6)

де т = 1,2,3, ...;

числом перевірочних елементів, що не перевищує величини , Тобто

(7)

здатністю виявляти всі пакети помилок довжини

(8)

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

Можливо завдання циклічних БЧХ-кодів за допомогою породжують або перевірочних матриць аналогічно загальним правилам, побудови лінійних кодів. Однак скористаємося простішими інженерними методиками, що базуються на алгебраїчних поняттях. У цьому випадку більш зручною є запис кодових комбінацій у вигляді полінома змінної х:

Коефіцієнти a _i представляють собою цифри даної системи числення. У двійковій системі числення коефіцієнти можуть приймати одне з двох значень 0 або 1. Так, двійкове чотирирозрядний число 1001 може бути записано у вигляді полінома

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

Циклічні коди утворюються множенням кожної комбінації - елементного безнадлишкових коду, вираженої у вигляді многочлена G (х), на який утворює поліном Р (х) ступеня (п - k). При цьому множення проводиться за звичайними правилами з приведенням подібних членів по модулю два [6, 98]. Отже, у разі відсутності помилок будь-яка дозволена кодова комбінація циклічного коду повинна розділитися на який утворює поліном Р (х) без залишку. Поява залишку від ділення вказує на наявність помилок у кодовій комбінації. При цьому гарантійно виявляються помилки, зумовлені виразами (7) і (8).

Крім того, виявляється велика часті помилок більш високої кратності.

Широке застосування знайшов інший метод, який у відношенні ступеня надмірності та завадостійкості призводить до побудови еквівалентного циклічного коду. У відповідності з цим методом кожна кодова комбінація первинного коду G (х) множиться на Одночлен X ^{n - k.} Це еквівалентно приписування праворуч до комбінації G (х), записаної у двійковій формі, (п - k) нулів. Твір G (х) x ^{n - k} ділиться на який утворює поліном Р (х) ступеня (п - k):

(9)

де Q (х) - частка від ділення такою ж мірою, як і G (х); R (х) - залишок.

Так як приватна Q (х) має таку ж ступінь, як ^і кодова комбінація G (х), то, отже, Q (х) є кодовою комбінацією цього ж простого k-елементного коду.

Множачи обидві частини рівності на Р (х) отримаємо:

(10)

Тут знак мінус замінений знаком плюс, так як додавання і віднімання за модулем два - операції еквівалентні.

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

3.2 Коди з постійною парністю одиниць

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

методами, викладеними в п.   4.1. При цьому дозволені кодові слова циклічного (k + 1, k) - коду у всіх випадках містять парне число одиниць. Доведемо це властивість, використовуючи метод побудови циклічних кодів, заснований на множенні комбінацій G (х) на який утворює поліном

Р (х) = х + 1.

Так як утворює поліном Р (х) є двучленном, то твір G (х) Р (х) незалежно від числа членів першого співмножники

G (х) завжди буде містити парне число членів.

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

Коди з постійною парністю одиниць дозволяють виявити будь-які помилки непарної кратності, тобто для цих; кодів = 1,3,5, ..., l, де l = k для непарних значень k і l = k + 1 для парних значень k.

3.3 Завадостійкість циклічних кодів

Циклічні коди можна використовувати в наступних режимах: для виправлення помилок; для виявлення помилок; для виправлення і виявлення помилок.

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

(11)

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

C урахуванням виразу (11) отримаємо

(12)

При ПР ₀ 1, обмежуючись першим членом суми, отримаємо наближений вираз, придатне для інженерних розрахунків:

(13)

При передачі інформації в каналі зв'язку з групуються помилками, визначаючи , І підставляючи в (11), отримаємо наближений вираз

(14)

Для точних розрахунків ймовірність повинна визначатися з виразу (3).

Використання циклічних кодів для виправлення помилок призводить до зниження вірогідності переданої інформації, яка може бути визначена за формулами (12), (13) і (14), якщо виключити коефіцієнт і замість параметра підставити параметр t, який визначає кратність гарантійно виправляються циклічним кодом помилок і пов'язаний з співвідношенням

. (15)

Режим одночасного виправлення і виявлення помилок за досягається достовірності займає проміжне положення між розглянутими режимами. Імовірність невиявлення помилок у цьому випадку може бути обчислена за формулами (11) - (13), якщо параметр зменшити на величину t.

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

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

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

(16)

де Р _ош - імовірність появи будь-якої помилки в кодової комбінації. Так як в реальних системах Р _Н.О. <Р _ош, то можна покласти, що

(17)

У режимі одночасного виправлення і виявлення помилок виправляються помилки до t - кратних включно. Тому втрати будуть обумовлені абсолютною більшістю помилок, кратність яких перевищує t, тобто

, (18)

де - Імовірність появи i-кратних помилок.

4. Мажоритарне декодування циклічних кодів

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

На рис. 2 зображена функціональна схема декодуючого пристрої для циклічних мажоритарних кодів з повторенням. Пристрій містить регістр зсуву 1, суматори за модулем два 2, розподільник 3, лічильники мажоритарних перевірок 4 - 1, 4-2, ..., 4 - k, блок запам'ятовування 5, блок, порівняння 6 і дешифратор 7.

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

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

Рис. 2

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

Лічильники мажоритарних перевірок 4-1, 4-2, .... 4 - k використовуються для підрахунку результатів мажоритарних перевірок. Вони виконані за схемою з кількома порогами спрацьовування. Кожен поріг визначається числом прийнятих кодових комбінацій, за результатами мажоритарних перевірок яких обчислюються інформаційні елементи. У загальному випадку число лічильників дорівнює числу інформаційних елементів k у вихідній кодової комбінації. Якщо l - число мажоритарних перевірок для одного інформаційного елемента за одне повторення, то мінімальний поріг визначиться величиною 0,5 l (l - парне) або 0,5 (l + 1). де l - непарне. За m повторень поріг визначиться величиною 0,5 lm або 0,5 (1 m + 1). За весь N повторень поріг визначиться величиною 0,5 lm або 0,5 (lm + 1). Так, для циклічного (7,3) - коду з триразовим повторенням l = 4, мінімальний поріг за одне повторення дорівнює двом, поріг за два повторення дорівнює чотирьом і поріг за все повторення дорівнює 6.

Рис. 3

При цьому лічильник мажоритарних перевірок для одного інформаційного елемента (рис. 3) буде складатися з трьох двійкових розрядів і значення інформаційного елемента для мінімального порогу визначиться станом другого розряду лічильника після обробки першого повторення, для другого порога - станом третього розряду лічильника після обробки двох повторень і для третього порога за все повторення - станом другого і третього розрядів лічильника після обробки трьох повторень.

В окремому випадку порогів спрацьовування може бути два: перший поріг за одне або частину повторень визначає перший етап обробки, другий поріг за все повторення визначає другий етап обробки.

Лічильники мажоритарних перевірок 4-1, 4-2, ..., 4 - t виконані за схемою з двома порогами і відповідно мають по два виходи.

Блок запам'ятовування 5 служить для почергового запам'ятовування результатів мажоритарної обробки, відповідних реалізованим порогах спрацьовування лічильників 4-1, 4-2, ..., 4-к.

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

Дешифратор 7 аналізує результати мажоритарних обробок і при виявленні забороненої комбінації блокує її видачу до закінчення прийому всіх повторень. До заборонених комбінаціям можуть бути віднесені повідомлення, виконання яких призводить до незворотних процесів у одержувача і які не можуть бути скориговані наступними результатами мажоритарних перевірок. В окремому випадку для систем, в яких відсутні заборонені комбінації, дешифратор 7 буде відсутнім. Робота пристрою відбувається наступним чином. Принимаемая n-розрядна кодова комбінація вводиться в регістр зсуву 1. Далі, протягом до тактів за допомогою регістра зсуву 1 і суматорів 2 формуються результати мажоритарних перевірок для кожного з к інформаційних елементів, які через розподільник 3 вводяться у відповідний лічильник мажоритарних перевірок 4-1, 4-2, ..., 4 - k. Вся процедура декодування здійснюється за час , Де V - швидкість модуляції для прийнятої кодової комбінації. Аналогічно обробляється кожне повторення циклічного коду. Після прийому і обробки т повторень, що визначають перший поріг спрацьовування, інформаційні елементи з перших виходів лічильників мажоритарних перевірок надходять одночасно до блоку запам'ятовування 5 і блок порівняння 6. З блоку порівняння 6 декодована комбінація надходить в дешифратор 7, який аналізує і не перешкоджає видачі для виконання дозволеної комбінації, або подачею сигналу в блок порівняння 6 блокує видачу забороненої комбінації.

Після прийому і обробки m повторень, що визначають другий поріг спрацьовування, інформаційні елементи з других виходів лічильників мажоритарних перевірок надходять одночасно до блоку запам'ятовування 5 і блок порівняння 6. Надійшли інформаційні елементи витісняють з блоку запам'ятовування 5 в блок порівняння 6 раніше запомненний результат. У блоці порівняння 6 порівнюються результати першого і другого етапів обробки. При їх збігу продовжує виконуватися повідомлення, декодувати на першому етапі. При розбіжності блок порівняння 6 видає сигнал на припинення виконання повідомлення, декодованого на першому етапі і видає для виконання повідомлення, декодувати на другому етапі. У випадку мала місце на першому етапі блокування блок порівняння 6 видає для виконання повідомлення, декодувати на другому етапі. Вибором відповідного значення m забезпечується те, що в абсолютній більшості випадків повідомлення, декодувати на першому і другому етапах, будуть збігатися і час прийому визначиться величиною

що в разів менше, ніж час прийому у відомих пристроях.

Якщо - Реалізоване кодова відстань циклічного мажоритарного М (n, k) - коду [7, 115], яке аналогічно мінімального відстані, то кратність гарантійно виправляє помилок визначається співвідношенням

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

, Причому .

Реалізоване кодова відстань, відповідне т повторенням першого етапу обробки,

а кратність виправляє помилок

(19)

Другий етап обробки характеризується прийомом N повторень, що реалізовується кодова відстань яких

а кратність виправляє помилок

(20)

Характеристики (19) і (20) дозволяють визначити достовірність інформації першого та другого етапів обробки за методикою (п. 3.3).

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

5. Мажоритарне декодування кодів з повторенням

5.1 Адаптивне мажоритарне декодування кодів з повторенням

Представляє інтерес розробка мажоритарних кодують пристроїв, що мають можливість перебудовуватися в залежності від якості каналів зв'язку і разом з тим зберігають простоту технічної реалізації. Розглянемо деякі з найбільш перспективних напрямків побудови такого типу пристроїв. [5, 57]

Визначення методу. У відповідності з цим методом запам'ятовують 1-у посилку, порівнюють його з наступною і додатково запам'ятовують позиції незбіжних елементів. При прийомі кожного наступного повторення виробляють його порівняння і виявляють розбіжності з попереднім результатом, на місце якого записують збігаються елементи прийнятого повторення, ті неспівпадаючі елементи, які відповідають збереженим в даний момент розбіжності, а інші елементи прийнятого повторення перед записом інвертують. Крім того, при прийомі непарного повторення логічно складають виявлені і збережені розбіжності, на місце яких записують результат логічного складання. При прийомі парного повторення виконують операцію логічного множення для виявлених і збережених розбіжностей, на місці яких записують результат логічного множення. На рис. 4 зображено граф, відповідний даному методу, де показано

Рис. 4.

- Стан однойменних елементів пам'яті; - «1» і «0» парного і непарного повторень.

Початковий стан пам'яті встановлюється після прийому першої пари елементів

Орієнтований граф (стрілка) визначає перехід системи з одного стану в інший залежно від виду наступних прийнятих елементів.

Розглянемо дію методу на прикладі мажоритарного аналізу коду з трьома і п'ятьма посилками. Для наочності припускаємо, що мають місце спотворення і тому посилки 1,2, 3-я не збігаються:

Запам'ятовують 1-у посилку. Порівнюють 2-у і 1-ю посилки і запам'ятовують 2-у посилку на місці 1-й.

Позиції розбіжностей

запам'ятовують додатково. Таким чином, використовують 2 n елементів пам'яті, де n - число елементів в одній посилці (у прикладі n = 6). Третю посилку порівнюють з другою. Співпадаючі елементи третього посилки без змін записують на місце 2-й посилки:

Аналогічно записують неспівпадаючі елементи 3-ї посилці, яким відповідають раніше запомненние розбіжності, а саме 4-й і 5-ї елементи

Решта неспівпадаючі елементи 3-ї посилці перед записом інвертують, отже, 3-й елемент

Таким чином, замість другої посилки виявиться записаний результат мажоритарної обробки «два з трьох»

(21)

Розбіжності 2-й третє посилок

Логічно складають з збереженими неспівпаданнями

(22)

А результат логічного складання (22) записують на місце раніше збережених розбіжностей.

Таким чином, до кінця прийому 3-ї посилці в n елементах пам'яті зберігається результат мажоритарної обробки і в n-елементах пам'яті - неспівпадання (22).

Якщо до кінця прийому 3-ї посилці оцінка стану каналу зв'язку вказує на необхідність продовження прийому посилки і декодування за критерієм «три з п'яти», то здійснюють прийом 4-й і 5-й посилок

Четверту посилку порівнюють з результатом мажоритарної обробки (21) і виявляють розбіжності

(23)

На місце результату (21) записують збігаються елементи 4-й посилки, тобто 2-й і 6-й:

(24)

і неспівпадаючі елементи, яким відповідають збережені розбіжності (6,3), тобто 3, 4 і 5-й елементи:

(25)

Інші елементи 4-й посилки перед записом інвертують, тому 1-й елемент

(26)

Таким чином, з (24), (25) і (26) формується проміжний результат

Раніше збережені розбіжності (22) логічно перемножують з виявленими неспівпаданнями (23):

(27)

і результат (27) записують на місце розбіжностей (22).

Таким чином, і на цьому етапі виявляються задіяними тільки 2n елементів пам'яті.

Продовжують прийом 5-й посилки, порівнюють її з проміжним результатом (26) і виявляють розбіжності:

(28)

Співпадаючі 2, 3, 6-й елементи 5-й посилки записують на місце проміжного результату (26) без зміни

Аналогічно записують неспівпадаючі елементи, яким відповідають збережені розбіжності (27), тобто 4 і 5-й елементи:

(29)

Інші елементи 5-й посилки перед записом отримують 1-й елемент

(30)

У результаті з (28), (29) і (30) формується результат мажоритарної обробки «три з п'яти»

який записується на місце проміжного результату (26). Імовірнісні характеристики методу « з »Мають такий вигляд:

5.2 Розширення області адаптивного мажоритарного декодування кодів з повторенням

При зниженні якості каналу зв'язку протягом тривалого часу виявляється доцільним введення додаткової надмірності шляхом збільшення числа передач кодів з повторенням, з подальшою мажоритарної обробкою. При цьому можлива поетапна обробка прийнятих посилок без втрати проміжних результатів [5, 60].

Визначення методу. У відповідності з цим методом підраховують число одиниць в однойменних елементах посилок, де - 2,3, ..., М, і отримане число для кожного з елементів у вигляді цифрового коду послідовно записують. При прийомі черговий посилки згадані цифрові коди послідовно і синхронно зчитують. Коригують, збільшуючи на одиницю ті числа , Яким відповідають одиничні елементи черговий посилки, за умови, що , І знову послідовно перезаписують. При цьому результат мажоритарної обробки утворюють щоразу в момент прийому непарних посилок за правилом: якщо - Формують інформаційну одиницю, а якщо - Формують нуль.

Розглянемо дію способу на прикладі мажоритарного декодування кодів з повторенням, де = 2,3, ..., 7, тобто М = 7. Як було відзначено, для запису цифрових кодів необхідно елементів пам'яті. Якщо = 5, то в окремому випадку можна використовувати три пятіразрядних регістра зсуву. Для наочності припустимо, що мають місце спотворення і тому посилки, наведені в табл. 1, не збігаються:

Таблиця 1