Білоруський державний університет інформатики і радіоелектроніки
кафедра РЕЗ
реферат на тему:
«Лінійні блокові коди»
МІНСЬК, 2009
Лінійним блоковою (n, k) - кодом називається безліч N послідовностей довжини n над GF (q), званих кодовими словами, яке характеризується тим, що сума двох кодових слів є кодовим словом, а твір будь-якого кодового слова на елемент поля також є кодовим словом .
Зазвичай N = q k, де k - деяке ціле число. Якщо q = 2, лінійні коди називаються груповими, так як кодові слова складають математичну структуру, яка називається групою. При формування цього коду лінійної операцією є підсумовування по mod2.
Приклад. У таблиці 1 представлені всі кодові слова (5,3) - коду (a i - інформаційні, а b i - перевірочні символи).
2. Системою перевірочних рівнянь, що визначають правила формування перевірочних символів по відомим інформаційним:
де
j - номер перевірочного символу;
i - номер інформаційного символу;
h ij - коефіцієнти, які беруть значення 0 або 1 відповідно до правил формування конкретних групових кодів.
Приклад. Для коду (5,3) перевірочні рівняння мають вигляд:
b 1 = a 2 + a 3;
b 2 = a 1 + a 2.
3. Матричне, засноване на побудові породжує і перевірочної матриць.
Векторний простір Vn над GF (2) включає в себе 2 n векторів (n-послідовностей), а підпростором його є безліч з 2 k кодових слів довжини n, яке однозначно визначається його базисом, що складається з k лінійно незалежних векторів. Тому лінійний (n, k) - код повністю визначається набором з k кодових слів, що належать цим кодом. Набір з k кодових слів, відповідних базису, зазвичай представляється у вигляді матриці, яка називається породжує.
Приклад. (5,3) - код, який був представлений в таблиці 1, може бути заданий матрицею
Решта кодові слова виходять складанням рядків матриць у різних поєднаннях.
Загальна кількість різних варіантів породжують матрицю визначається виразом
Для виключення неоднозначності в записі G (n, k) вводять поняття про канонічну або систематичної формі матриці, яка має вигляд
де
I k - одинична матриця, що містить інформаційні символи;
R k, r - прямокутна матриця, складена з перевірочних символів.
Приклад. Породжує матриця в систематичному вигляді для (5,3) - коду
Породжує матриця G (n, k) в систематичному вигляді може бути отримана з будь-якої іншої матриці за допомогою елементарних операцій над рядками (перестановкою двох довільних рядків, заміною довільній рядка на суму її самої і ряду інших) і подальшої перестановкою стовпців.
Перевірочна матриця в систематичному вигляді має вигляд
де I r - одинична матриця;
- Прямокутна матриця в транспонованої вигляді матриці R k, r з породжує матриці.
Приклад. Перевірочна матриця (5,3) - коду
на транспоновану перевірочну матрицю дає нульовий вектор розмірності (nk)
Приклад. для коду (5,3)
2. Твір деякого кодового слова
, Тобто з помилкою, на транспоновану перевірочну матрицю називається синдромом і позначається S i (x)
3. Між породжує і перевірочної матрицями в систематичному вигляді існує однозначна відповідність, а саме:
4. Кодова відстань d 0 (n, k) - коду одно мінімальному числу лінійно залежних стовпців перевірочної матриці
Приклад.
для коду (5,3):
для коду (5,2):
5. Твір інформаційного слова на породжує матрицю дає кодове слово коду
Приклад. для коду (5,3)
6. Два коду називаються еквівалентними, якщо їх породжують матриці відрізняються перестановкою координат, тобто породжують матриці виходять одна за одною перестановкою стовпців і елементарних операцій над рядками.
7. Кодова відстань будь-якого лінійного (n, k) - коду задовольняє нерівності
(Кордон Сінгтона). Лінійний (n, k) - код, що задовольняє рівності 
, Називається кодом з максимальною відстанню.
Утворюють або лідери суміжних класів вибираються таким чином, щоб до їх складу увійшли найбільш ймовірні зразки помилок в кодовому слові, тобто зразки помилок з найменшою вагою.
Приклад. Код (5,3) має матриці
і 
а стандартне розташування має вигляд,
Цей код має d 0 = 3. Він гарантує виправлення одиночних помилок, конфігурація яких дана в першому стовпці.
Процедура виправлення помилок наступна. Прийняте кодове слово аналізують і визначають, у якому стовпці воно знаходиться, а потім як виправленого кодового слова беруть слово, що знаходиться у верхній частині.
Однак, якщо довжина коду велика і таблиця стандартного розташування також значна, користуватися таким алгоритмом незручно. Тому при декодуванні використовують таблицю синдромів (декодування), що представляє собою список зразків помилок (див. перший стовпець стандартного розташування) і список відповідних синдромів, які однозначно характеризують кожен суміжний клас.
Приклад. Для (7,4)-коду Хеммінга
або 
Перевірочна матриця будь-якого коду Хеммінга завжди містить мінімум три лінійно залежних стовпця, тому кодова відстань коду дорівнює трьом.
Якщо стовпці перевірочної матриці представляють впорядковану запис десяткових чисел, тобто 1,2,3 ... в двійковій формі, то обчислений синдром
однозначно вказує на номер позиції спотвореного символу.
Приклад. Для (7,4)-коду Хеммінга перевірочна матриця в упорядкованому вигляді має вигляд
Нехай передане кодове слово
, А прийняте слово - 
.
Синдром, відповідний прийнятому слова буде дорівнює
Обчислений синдром вказує на помилку в п'ятій позиції.
Перевірочна матриця в упорядкованому вигляді являє сукупність перевірочних рівнянь, в яких перевірочні символи займають позиції з номерами 2 i (i = 0,1,2 ...).
Для (7,4)-коду Хеммінга перевірочними рівняннями будуть
де
- Перевірочні символи.
Елементи синдрому визначаються з виразів
Коригуюча здатність коду Хеммінга може бути збільшена введенням додаткової перевірки на парність. У цьому випадку перевірочна матриця для розглянутого (7,4)-коду буде мати вигляд
а кодова відстань коду d 0 = 4.
Перевірочні рівняння використовуються для побудови кодера, а синдромних - декодера коду Хеммінга.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р . - 1104 с.
кафедра РЕЗ
реферат на тему:
«Лінійні блокові коди»
МІНСЬК, 2009
Лінійним блоковою (n, k) - кодом називається безліч N послідовностей довжини n над GF (q), званих кодовими словами, яке характеризується тим, що сума двох кодових слів є кодовим словом, а твір будь-якого кодового слова на елемент поля також є кодовим словом .
Зазвичай N = q k, де k - деяке ціле число. Якщо q = 2, лінійні коди називаються груповими, так як кодові слова складають математичну структуру, яка називається групою. При формування цього коду лінійної операцією є підсумовування по mod2.
Способи завдання лінійних кодів
1. Перерахуванням кодових слів, тобто складанні списку всіх кодових слів коду.Приклад. У таблиці 1 представлені всі кодові слова (5,3) - коду (a i - інформаційні, а b i - перевірочні символи).
Таблиця 1 | |||||
| № | a 1 | a 2 | a 3 | b 1 | b 2 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 1 | 0 | 1 | 1 |
| 3 | 0 | 1 | 1 | 0 | 1 |
| 4 | 1 | 0 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 | 0 |
| 7 | 1 | 1 | 1 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 |
де
j - номер перевірочного символу;
i - номер інформаційного символу;
h ij - коефіцієнти, які беруть значення 0 або 1 відповідно до правил формування конкретних групових кодів.
Приклад. Для коду (5,3) перевірочні рівняння мають вигляд:
b 1 = a 2 + a 3;
b 2 = a 1 + a 2.
3. Матричне, засноване на побудові породжує і перевірочної матриць.
Векторний простір Vn над GF (2) включає в себе 2 n векторів (n-послідовностей), а підпростором його є безліч з 2 k кодових слів довжини n, яке однозначно визначається його базисом, що складається з k лінійно незалежних векторів. Тому лінійний (n, k) - код повністю визначається набором з k кодових слів, що належать цим кодом. Набір з k кодових слів, відповідних базису, зазвичай представляється у вигляді матриці, яка називається породжує.
Приклад. (5,3) - код, який був представлений в таблиці 1, може бути заданий матрицею
Решта кодові слова виходять складанням рядків матриць у різних поєднаннях.
Загальна кількість різних варіантів породжують матрицю визначається виразом
Для виключення неоднозначності в записі G (n, k) вводять поняття про канонічну або систематичної формі матриці, яка має вигляд
де
I k - одинична матриця, що містить інформаційні символи;
R k, r - прямокутна матриця, складена з перевірочних символів.
Приклад. Породжує матриця в систематичному вигляді для (5,3) - коду
Породжує матриця G (n, k) в систематичному вигляді може бути отримана з будь-якої іншої матриці за допомогою елементарних операцій над рядками (перестановкою двох довільних рядків, заміною довільній рядка на суму її самої і ряду інших) і подальшої перестановкою стовпців.
Перевірочна матриця в систематичному вигляді має вигляд
де I r - одинична матриця;
Приклад. Перевірочна матриця (5,3) - коду
Основні властивості лінійних кодів
1. Твір будь-якого кодового словаПриклад. для коду (5,3)
2. Твір деякого кодового слова
3. Між породжує і перевірочної матрицями в систематичному вигляді існує однозначна відповідність, а саме:
4. Кодова відстань d 0 (n, k) - коду одно мінімальному числу лінійно залежних стовпців перевірочної матриці
Приклад.
для коду (5,3):
для коду (5,2):
5. Твір інформаційного слова на породжує матрицю дає кодове слово коду
Приклад. для коду (5,3)
6. Два коду називаються еквівалентними, якщо їх породжують матриці відрізняються перестановкою координат, тобто породжують матриці виходять одна за одною перестановкою стовпців і елементарних операцій над рядками.
7. Кодова відстань будь-якого лінійного (n, k) - коду задовольняє нерівності
Стандартне розташування групового коду
Стандартне розташування групового коду являє розкладання безлічі всіх можливих n-елементних слів, що представляють собою групу, на суміжні класи по підгрупі з 2 k кодових слів, складових (n, k)-код (див. таблицю 2).Таблиця 2 | |||||
| | | ||||
Приклад. Код (5,3) має матриці
а стандартне розташування має вигляд,
| 00000 | 10111 | 01101 | 11010 |
| 00001 | 10110 | 01100 | 11011 |
| 00010 | 10101 | 01111 | 11000 |
| 00100 | 10011 | 01001 | 11110 |
| 01000 | 11111 | 00101 | 10010 |
| 10000 | 00111 | 11101 | 01010 |
| 00011 | 10100 | 01110 | 11001 |
| 10001 | 00110 | 11100 | 01011 |
Процедура виправлення помилок наступна. Прийняте кодове слово аналізують і визначають, у якому стовпці воно знаходиться, а потім як виправленого кодового слова беруть слово, що знаходиться у верхній частині.
Однак, якщо довжина коду велика і таблиця стандартного розташування також значна, користуватися таким алгоритмом незручно. Тому при декодуванні використовують таблицю синдромів (декодування), що представляє собою список зразків помилок (див. перший стовпець стандартного розташування) і список відповідних синдромів, які однозначно характеризують кожен суміжний клас.
Коди Хеммінга
Кодом Хеммінга називається (n, k)-код, перевірочна матриця якого має r = nk рядків і 2 r -1 стовпців, причому стовпцями є всі різні ненульові послідовності.Приклад. Для (7,4)-коду Хеммінга
Перевірочна матриця будь-якого коду Хеммінга завжди містить мінімум три лінійно залежних стовпця, тому кодова відстань коду дорівнює трьом.
Якщо стовпці перевірочної матриці представляють впорядковану запис десяткових чисел, тобто 1,2,3 ... в двійковій формі, то обчислений синдром
однозначно вказує на номер позиції спотвореного символу.
Приклад. Для (7,4)-коду Хеммінга перевірочна матриця в упорядкованому вигляді має вигляд
Нехай передане кодове слово
Синдром, відповідний прийнятому слова буде дорівнює
Обчислений синдром вказує на помилку в п'ятій позиції.
Перевірочна матриця в упорядкованому вигляді являє сукупність перевірочних рівнянь, в яких перевірочні символи займають позиції з номерами 2 i (i = 0,1,2 ...).
Для (7,4)-коду Хеммінга перевірочними рівняннями будуть
де
Елементи синдрому визначаються з виразів
Коригуюча здатність коду Хеммінга може бути збільшена введенням додаткової перевірки на парність. У цьому випадку перевірочна матриця для розглянутого (7,4)-коду буде мати вигляд
Перевірочні рівняння використовуються для побудови кодера, а синдромних - декодера коду Хеммінга.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа,
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок,
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс»,