жними, вони належать до дуже обмеженої класу блокових кодів, званих досконалими.
Циклічні коди. Важливим підкласом лінійних блокових кодів є виконавчі циклічні коди (cyclic codes). Код легко реалізується на регістрі зсуву зі зворотним зв'язком; на подібних регістрах зсуву зі зворотним зв'язком обчислюється синдром; алгебраїчна структура циклічного коду природним чином дозволяє ефективно реалізувати методи декодування. Отже, лінійний код (n, до) називається циклічним, якщо він має наступну властивість. Якщо n-кортеж U = (u 0 , u 1 , і 2 , ..., u n -1 ) є кодовим словом в підпросторі S, тоді U (1) = (u n -1 , u 0 , u 1 , і 2 , ..., u n - 1 ), отриманий з U за допомогою циклічного зсуву, також є кодовим словом у S. Або, взагалі, U (i) = (u n - i ;. U n - i +1 , ..., u n -1 , u 0 , u 1, ... u n - i -1 ), отриманий i циклічними зрушеннями, є кодовим словом у S.
Циклічний код Файр . Циклічні коди, що виявляють і виправляють пакети помилок (коди Файр). Під пакетом помилок довжиною b розуміють такий вид комбінації перешкоди, у якій між крайніми розрядами, ураженими перешкодами, міститься b -2 розряду. Наприклад, при b = 5 комбінації перешкоди, тобто пакет помилок, можуть мати наступний вигляд: 10001 (вражені тоько два крайніх символу), 11111 (уражені всі символи), 10111, 11101, 11011 (не уражений лише один символ), 10011, 11001, 10101 (вражені три символи). При будь-якому варіанті неодмінною умовою пакета даної довжини є ураження крайніх символів.
Коди Файр можуть виправляти пакет помилок довжиною b і виявляти пакет помилок довжиною b [зауважимо, що в кодах Файр поняття кодового відстані - d ].
Коди Боуза-Чоудхурі-Хоквінгема. . Ці коди, розроблені Боуза, Чодхурі і Хоквінхемом (скорочено коди БЧХ), дозволяють виявляти та виправляти будь-яке число помилок. Заданими при кодуванні є число помилок s , яке слід виправити, і загальне число символів, що посилаються в лінію, тобто довжина слів n . Числа інформаційних символів k і контрольних символів m , а також склад контрольних символів підлягають визначенню. p> Коди БЧХ для виявлення помилок . Їх будують наступним чином. Якщо необхідно утворити код з виявленням парного числа помилок, то за заданим числом r знаходять значення d і s . Подальше кодування виконують, як і раніше. Якщо потрібні виявити непарне число помилок, те знаходять найближчим меншу ціле число s та кодування роблять так само, як і в попередньому випадку: утворює многочлен додатково множать на двочлен. Наприклад, потрібні побудувати код виявляє сім помилок при n = 15 . Знаходимо, що d = 8 , а найближчим менше значення s = 3 . Далі визначаємо многочлен, як зазначено в прикладі 3.5, і множимо його на двочлен, тобто отримуємо. Таким чином побудований код БЧХ (15,4).
В
11 Лекція № 11 . П омехоустойчів ті код и і метод и декодування коригувальних кодів
Мета лекції: вивчення завадостійких кодів і методів декодування коригувальних кодів
Зміст:
а) коди Ріда-Соломона;
б) згорткові коди;
в) класифікація коригувальних кодів;
г ) методи декодування коригувальних кодів.
11.1 Коди Ріда- Соломона
Коди Ріда-Соломона (Reed-Solomon code, RS code) - це недвійкові циклічні коди, символи яких являють собою m-бітові послідовності, де т - позитивне ціле число, більше 2. Код (n, до) визначений на m-бітових символах при всіх n і k, для яких
(11.1)
де k - число інформаційних бітів, підлягають кодування, а n - число кодових символів у кодируемом блоці. Для більшості сверточних кодів Ріда-Соломона (n, до)
(11.2)
де t - кількість помилкових бітів у символі, які може виправити код, а nk = 2t-число контрольних символів. Розширений код Ріда-Соломона можна отримати при n = 2 m або n = 2 m + 1, але не більше того.
Код Ріда-Соломона володіє найбільшим мінімальним відстанню, можливим для лінійного коду з однаковою довжиною вхідних і вихідних блоків кодера. Для недвійковий кодів відстань між двома кодовими словами визначається (за аналогією з відстанню Хеммінга) як число символів, якими відрізняються послідовності. Для кодів Ріла...
