Теми рефератів
Авіація та космонавтика Банківська справа Безпека життєдіяльності Біографії Біологія Біологія і хімія Біржова справа Ботаніка та сільське гос-во Бухгалтерський облік і аудит Військова кафедра Географія
Геодезія Геологія Держава та право Журналістика Видавнича справа та поліграфія Іноземна мова Інформатика Інформатика, програмування Історія Історія техніки
Комунікації і зв'язок Краєзнавство та етнографія Короткий зміст творів Кулінарія Культура та мистецтво Культурологія Зарубіжна література Російська мова Маркетинг Математика Медицина, здоров'я Медичні науки Міжнародні відносини Менеджмент Москвоведение Музика Податки, оподаткування Наука і техніка Решта реферати Педагогіка Політологія Право Право, юриспруденція Промисловість, виробництво Психологія Педагогіка Радіоелектроніка Реклама Релігія і міфологія Сексологія Соціологія Будівництво Митна система Технологія Транспорт Фізика Фізкультура і спорт Філософія Фінансові науки Хімія Екологія Економіка Економіко-математичне моделювання Етика Юриспруденція Мовознавство Мовознавство, філологія Контакти
Українські реферати та твори » Информатика, программирование » Коди Боуза-Чоудхурі-хоквінгема

Реферат Коди Боуза-Чоудхурі-хоквінгема


РЕФЕРАТ

По курсу "Теорія інформації та кодування"

на тему:

"КОДИ Боуз-Чоудхурі-хоквінгема"


БЧХ коди

Коди Боуза-Чоудхурі-хоквінгема (БЧХ) - клас циклічних кодів, які виправляють кратні помилки, тобто дві і більше ( d 0 Ві 5).

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

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

Розглянемо процедуру кодування з використанням коду БЧХ на конкретних прикладах.

Приклад Побудувати 15-розрядний код БЧХ, що виправляє дві помилки в кодової комбінації (тобто n = 15, S = 2 ).

Рішення:

1. Визначимо кількість контрольних m та інформаційних розрядів k

m ВЈ h S.

Визначимо параметр h з формули

n = 2 h -1, h = log 2 (n +1) = log 2 16 = 4,

при цьому: m ВЈ h S = 4 Г— 2 = 8 ; k = n-m = 15-8 = 7 .

Таким чином, отримали (15, 7)-код.

2. Визначимо параметри утворює полінома:

- кількість мінімальних многочленів, що входять в створюючий

L = S = 2;

- порядок старшого (всі мінімальні - непарні) мінімального многочлена r = 2S-1 = 3;

- ступінь утворює многочлена b = m ВЈ 8.

3. Вибір утворює многочлена.

З таблиці для мінімальних многочленів для кодів БЧХ (див. додаток 4) з колонки 4 (т. к. l = h = 4 ) вибираємо два мінімальних многочлена 1 і 3 (т. к. r = 3 ):

M 1 (x) = 10011;

M 2 (x) = 11111.

При цьому

P (x) = M 1 (x) Г— M 2 (x ) = 10011'11111 = 111010001 = x 8 + x 7 + x 6 + x 4 +1 .

4. Будуємо утворюючу матрицю. Записуємо перший рядок утворює матриці, яка складається з утворює полінома з попередніми нулями, при цьому загальна довжина кодової комбінації дорівнює n = 15 . Решта рядків матриці одержуємо в Внаслідок k-кратного циклічного зсуву праворуч ліворуч першого рядка матриці.


Рядки утворює матриці являють собою 7 кодових комбінацій коду БЧХ, а інші можуть бути отримані шляхом підсумовування по модулю 2 всіляких поєднань рядків матриці.

Процедура декодування, виявлення та виправлення помилок у прийнятій кодовій комбінації така ж, як і для циклічних кодів з d 0 <5

Приклад Побудувати 31-розрядний код БЧХ, що виправляє три помилки в кодової комбінації (тобто n = 31, S = 3 ).

Рішення:

1. Визначимо кількість контрольних розрядів m та інформаційних розрядів k.

m ВЈ h S.

Визначимо параметр h з формули

n = 2 h -1, h = log 2 (n +1) = log 2 32 = 5,

при цьому: m ВЈ h S = 5 Г— 3 = 15 ; k = n-m = 31-15 = 16 .

Таким чином, отримали (31, 16)-код.

2.Определить параметри утворює полінома:

- кількість мінімальних многочленів, що входять в створюючий

L = S = 3;

- порядок старшого мінімального многочлена

r = 3S-1 = 5;

- ступінь утворює многочлена

b = M ВЈ 15.

1. Вибір утворює многочлена.


З таблиці для мінімальних многочленів для кодів БЧХ (додаток 4) з колонки 5 (Т. к. l = h = 5 ) вибираємо три мінімальні многочлена 1, 3 і 5 (т. к. r = 5 ):

M 1 (x) = 100101;

M 2 (x) = 111101;

M 3 (x) = 110111.

При цьому

P (x) = M 1 (x) Г— M 2 (x ) Г— M 3 (x) = 1000111110101111 =

= x 15 + x 11 + x 10 + x 9 + x 8 + x 7 + x 5 + x 3 + x 2 + x + 1 .

4. Будуємо утворюючу матрицю. Записуємо перший рядок утворює матриці, яка складається з утворює полінома з попередніми нулями, при цьому загальна довжина кодової комбінації дорівнює n = 31 . Решта рядків матриці одержуємо в Внаслідок k-кратного циклічного зсуву праворуч ліворуч першого рядка матриці.

000000000000000100011111011111

G (31,16) = 000000000000001000111110111110

. . .

100011111011111000000000000000

Рядки утворює матриці являють собою 16 кодових комбінації коду БЧХ, а інші можуть бути отримані шляхом підсумовування по модулю 2 всіляких поєднань рядків матриці.


Декодування кодів БЧХ

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

Розглянемо алгоритм ПГЦ (Пітерсона-Горенстейна-Цірлера). Нехай БЧХ код над полем GF (q) довжини n і з конструктивним відстанню d задається породжує поліномом g (x), який має серед своїх коренів елементи, - Ціле число (наприклад 0 або 1). Тоді кожне кодове слово має тим властивістю, що. Прийняте слово r (x) можна записати як r (x) = c (x) + e (x), де e (x) - поліном помилок. Нехай відбулося помилок на позиціях (t максимальне число виправляються помилки), значить, а - величини помилок.

Можна скласти j-ий синдром Sj прийнятого слова r (x):

.

Задача полягає в знаходжень числа помилок u, їх позицій і їх значень при відомих синдромах Sj.

Припустимо, для початку, що u в точності дорівнює t. Запишемо (1) у вигляді системи нелінійних рівнянь в явному вигляді:


Позначимо через локатор k-ой помилки, а через величину помилки,. При цьому всі Xk різні, так як порядок елемента ОІ дорівнює n, і тому при відомому Xk можна визначити ik як ik = logОІXk.

Складемо поліном локаторів помилок:

Корінням цього полінома є елементи, зворотні локатора помилок. Множитимемо обидві частини цього полінома на. Отримане рівність буде справедливо для

:

Покладемо і підставимо в (3). Вийде рівність, справедливе для кожного і при всіх:

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

:

.

Враховуючи (2) і те, що

(тобто змінюється в тих же межах, що і раніше) отримуємо систему лінійних рівнянь:

.

Або в матричній формі

,

Де

Якщо число помилок і справді одно t, то система (4) розв'язна, і можна ...


Страница 1 из 2Следующая страница

Друкувати реферат
Замовити реферат
Товары
загрузка...
Наверх Зворотнiй зв'язок