Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Завдання №1:
Побудувати твірну матрицю двійкового систематичного ( групового ) коду, який має
N0 = 128 дозволених кодових комбінацій та здатен виправляти всі однократні помилки. Навести приклад кодування за допомогою твірної матриці.
Розв'язання.
Кількість інформаційних розрядів коду k = log 2 128 = 7. Кількість перевірочних розрядів визначається як найменше ціле r, яке задовольняє нерівності 2 r = k + r + 1 ; таким значенням буде r = 4 . Довжина коду n = k + r = 11 . Таким чином, твірна матриця G n,k має 11 стовпців та 7 рядка, а перевірочна під-матриця C r,k має 4 стовпця та 7 рядка.
Згідно з правилом побудови під-матриці C r,k кількість одиниць у кожному рядку цієї під-матриці повинно бути не менша за d min – 1 = 3 – 1 = 2, а кодова відстань між окремими рядками цієї підматриці – не менша за d min – 2 = 3 – 2 = 1. Тому, з чотириелементних комбінацій для під-матриці С 4,7 вибираємо тільки ті, які задовольняють цим умовам, тобто 1110, 1101, 1011, 0111,1100,1001,0011. За інформаційну під-матрицю Е k твірної матриці обирають одиничну під-матрицю. Дописавши до неї перевірочну під-матрицю, одержимо твірну матрицю систематичного коду, здатного виправляти однократні помилки,
G11,7 =.
За допомогою одержаної твірної матриці G 11,7 визначимо всі 128 кодових комбінацій, які належать до цього систематичного коду:
1 – 00000000000 ;
2 – 10000001110 ;
3 – 01000001101 ;
4 – 00100001011 ;
5 – 00010000111 ;
6 – 00001001100 ;
7 – 00000101001 ;
8 – 00000010011;
9 – 11000000011 ( 2 3);
10 10100000101 (2 4 );
11 10010001001 (2 5 );
12 10001000010 (2 6 );
13 10000100111 (2 7 );
14 10000011101 (2 8 );
15 01100000110 (3 4 );
16 01010001010 (3 5 );
17 01001000001 (3 6 );
18 01000100100 (3 7 );
19 01000011110 (3 8 );
20 00110001100 (4 5 );
21 00101000111 (4 6 );
22 00100100010 (4 7 );
23 00100011100 (4 8 );
24 00011001011 (5 6 );
25 00010101110 (5 7 );
26 00010010100 (5 8 );
27 00001100101 (6 7 );
28 00001011111 (6 8 );
29 00000111010 (7 8 );
30 11100001000 (2 3 4 );
31 11010000100 (2 3 5 );
32 11001001111 (2 3 6 );
33 11000101010 (2 3 7 );
34 11000011000 (2 3 8 );
35 01110000001 (3 4 5 );
36 01101001110 (3 4 6 );
37 01100100101 (3 4 7 );
38 01100010101 (3 4 8 );
39 00111000000 (4 5 6 );
40 00110100101 (4 5 7 );
41 00110011111 (4 5 8 );
42 00011100010 (5 6 7 );
43 00011011000 (5 6 8 );
44 00001110110 (6 7 8 );
І так далі виконуємо суму по модулю 2 по черзі, поки не отримаємо 128 комбінацій.
Изм.
Арк.
№ докум.
Подпись
Дата
Арк.
6.050102.282.05.08
Завдання №2:
Визначити, які з наведених комбінацій 0100010, 0100101, 1001011 двійкового групового ( 7,4 ) - коду, містять помилку, якщо відомо, що код побудований за твірною матрицею:
G 7,4 = .
Розв'язання.
За допомогою твірної матриці G 7,4 визначимо всі 16 кодових комбінацій, які належать до цього систематичного коду:
1 – 0000000 ;
2 – 1000011 ;
3 – 0100101 ;
4 – 0010110 ;
5 – 0001111;
6 – 1100110 ( 2 3 ) ;
7 – 1010101 ( 2 4 ) ;
8 – 1001100 ( 2 5 ) ;
9 – 0110011 ( 3 4 ) ;
10 – 0101010 ( 3 5 ) ;
11 – 0011001 ( 4 5 ) ;
12 – 1110000 ( 2 3 4 ) ;
13 – 1101001 ( 2 3 5 ) ;
14 – 1011010 ( 2 4 5 ) ;
15 – 0111100 ( 3 4 5 ) ;
16 – 1111111 ( 2 3 4 5 ) .
з наведених комбінацій 0100010, 0100101, 1001011 двійкового групового ( 7,4 ) - коду, комбінації 0100010 та 1001011 містять помилку.
Завдання №3:
Визначити, які з комбінацій 0100011, 0100101, 1101011 двійкового групового ( 7,4 ) - коду містять помилку, якщо відомо, що перевірочна матриця коду має вигляд:
Н 7,3 = .
Розв'язання.
Перевірочна матриця утворюється за допомогою твірної матриці, яка містить три стовпці і чотири рядки, кожний рядок якої відповідає стовпцю перевірочної під матриці та одиничної під-матриці E 3 . Таким чином:
=>
Одержуємо твірну матрицю G 7,4
G 7,4 =
За допомогою твірної матриці G 7,4 визначимо всі 16 кодових комбінацій, які належать до цього систематичного коду:
1 – 0000000 ;
2 – 1000011 ;
3 – 0100101 ;
4 – 0010110 ;
5 – 0001111;
6 – 1100110 ( 2 3 ) ;
7 – 1010101 ( 2 4 ) ;
8 – 1001100 ( 2 5 ) ;
9 – 0110011 ( 3 4 ) ;
10 – 0101010 ( 3 5 ) ;
11 – 0011001 ( 4 5 ) ;
12 – 1110000 ( 2 3 4 ) ;
13 – 1101001 ( 2 3 5 ) ;
14 – 1011010 ( 2 4 5 ) ;
15 – 0111100 ( 3 4 5 ) ;
16 – 1111111 ( 2 3 4 5 ) .
з наведених комбінацій 0100011, 0100101, 1101011 двійкового групового ( 7,4 ) - коду, комбінації 0100011, 1101011 містять помилку.
Завдання №4:
Закодувати комбінації двійкового простого коду А 1 = 11001 та А 2 = 00111 довжиною k = 5 двійковим кодом з багатократним повторенням, здатним виправляти помилки кратності s = 1. Показати процес виправлення помилок на прикладі і визначити надмірність коду.
Розв’язання.
Для коду А 1 число m повторень при виправленні однієї помилки визначається з виразу d min = m + 1. Кодова відстань при виправленні однократної помилки повинна бути не менша за d min = 3, тому m = d min – 1 = 3 – 1 = 2. Кодова комбінація коду з багатократним повторенням буде мати вигляд: 001000001000001000.
Покажемо процес виправлення однократної помилки. Для цього припустимо, що при передачі комбінації коду з багатократним повторенням виникла однократна помилка, вектор якої 001000000000000000. Тоді прийнята кодова комбінація буде мати вигляд: 000000001000001000.
У декодері прийнята кодова комбінація розбивається на 3 частин по 5 елементів у кожній і виконується порозрядне їх порівняння:
11000
11001
11001,
у результаті якого виявляється помилка у 5 розряді. Застосувавши “ голосування за більшістю ”, можна виправити цю помилку. Виправлена комбінація двійкового первинного коду буде мати вигляд 11001.
Надмірність коду R = m / ( m + 1 ) = r / n = 2 / 3.
Для коду А 2 число m повторень при виправленні однієї помилки визначається з виразу d min = m + 1. Кодова відстань при виправленні однократної помилки повинна бути не менша за d min = 3, тому m = d min – 1 = 3 – 1 = 2. Кодова комбінація коду з багатократним повторенням буде мати вигляд: 110111110111110111.
Покажемо процес виправлення однократної помилки. Для цього припустимо, що при передачі комбінації коду з багатократним повторенням виникла однократна помилка, вектор якої 000100000000000000. Тоді прийнята кодова комбінація буде мати вигляд: 110011110111110111.
У декодері прийнята кодова комбінація розбивається на 3 частини по 6 елементів у кожній і виконується порозрядне їх порівняння:
00011
00111
00111,
у результаті якого виявляється помилка у 3 розряді. Застосувавши “ голосування за більшістю ”, можна виправити цю помилку. Виправлена комбінація двійкового первинного коду буде мати вигляд 00111.
Надмірність коду R = m / ( m + 1 ) = r / n = 2 / 3.
Завдання №5:
Закодувати інформаційну послідовність двійкових елементів 0100011010010111 двійковим двомірним ітеративним кодом, здатним виправляти однократні помилки. Показати процес виправлення будь якої однократної помилки і визначити надмірність коду.
Розв’язання.
Розбиваємо комбінацію первинного коду на 4 частини, записуємо у вигляді матриці з трьома рядками та робимо перевірку на парність елементів кожного рядка і кожного стовпця, дописуючи перевірочні елементи:
|
0 1 0 0 |
1 |
|
0 1 1 0 |
0 |
|
1 0 0 1 0 1 1 1 |
0 1 |
|
1 1 0 0 |
1 |
Таким чином отримали кодовий двовимірний масив ( комбінацію ) ітеративного коду з перевірками на парність, який має мінімальну кодову відстань d min = 2 2 = 4 ( добуток мінімальних кодових відстаней кодів, якими захищаються рядки та стовпці ). У лінію ( канал ) зв’язку передаються послідовно рядок за рядком двійкові елементи отриманого масиву: 0100101100100100111111001. Довжина цієї комбінації n = 25, вона містить k =13 інформаційних та r = 12 перевірочних елементів.
Припустімо, що при передачі у результаті спотворень виникла помилка і на приймач прийшла комбінація 0000101100100100111111001. При декодуванні у декодері прийняту двійкову послідовність знову записують у вигляді матриці, структура якої співпадає зі структурою масиву після кодування, і виконують перевірку на парність кожного рядка і кожного стовпця цієї матриці :
|
0 0 0 0 1 |
1 |
|
0 1 1 0 0 |
0 |
|
1 0 0 1 0 |
0 |
|
0 1 1 1 1 1 1 0 0 0 |
|
|
0 1 0 0 0 |
Помилка знаходиться на перетині рядка та стовпця, які мають непарну кількість одиниць. В даному випадку це 2 рядок та 5 стовпець. Для виправлення помилки цей елемент інвертуємо, тобто замість прийнятого “ 0 ” записуємо “ 1 ”. Тоді виправлена інформаційна частина комбінації буде мати вигляд 0100011010010111, що збігається із комбінацією первинного коду, яка підлягала кодуванню.
Надмірність коду R = r / n = 12 / 25
Завдання №6:
Закодувати несистематичним кодом Бергера, що виправляє однократні помилки, комбінацію двійкового первинного коду 01000110100101. Показати процес виправлення будь-якої однократної помилки та визначити надмірність коду.
Розв’язання. Для побудови коду Бергера визначимо кількість перевірочних елементів з виразу
rlog 2 = log 2 ( 3 + 5 + 6 + 7 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 17+18+19 ) =
= log2 159 =7,13
тобто r = 7.
Далі визначимо сумарну вагу комбінації первинного коду, для чого треба додати послідовно вагу 2, 6, 7, 9, 12 і 14 розрядів, одержане десяткове число записати у двійковій формі 6 двійковими розрядами, інвертувати його і дописати до комбінації первинного коду: 5 + 10 + 11+13+17+19 =75, 7510 = 10010112 0110100; тоді комбінація коду Бергера буде мати вигляд 010001101001010110100 . Таким чином комбінація складається з двох частин: інформаційної ( перші 14 елементів ) і перевірочної ( 15...21 елементи ).
Зробимо припущення, що при передачі по лінії зв’язку в результаті дії завад у кодовій комбінації виникає помилка і на приймач надходить комбінація 000001101001010110100. Для виявлення помилки у декодері спочатку виконуються такі ж операції, що і у кодері, тобто визначається сума ваги тих інформаційних елементів, на місцях яких розташовані “ 1 ”: S* = 10 + 11+13+17+19 = 70; це число записується у двійковій формі 6 розрядами 1000110 та інвертується 0111001. Перевірочна частина прийнятої комбінації і обчислена у декодері не збігаються, що вказує на наявність помилки у прийнятій кодовій комбінації. Далі для виправлення помилки інвертується двійковий запис перевірочної частини прийнятої кодової комбінації, одержане двійкове число переводиться у десяткову форму ( воно дорівнює 70 ) і від нього віднімається обчислене число S*. Маємо 75 – 70 = 5 ; це свідчить про те, що у прийнятій кодовій комбінації був спотворений 2 елемент, оскільки саме йому відповідає вага 7. Виправлення виконується інвертуванням спотвореного елемента у прийнятій комбінації. Таким чином, правильний запис первинної комбінації має вигляд: 01000110100101.
Надмірність коду R = r / n = 7 / 21 = 0,33(3).
Висновок: У лабораторній роботі були приклади кодування за допомогою твірної матриці. Визначені комбінацій двійкового групового коду які містять помилку за допомогою твірної матриці та перевірочної матриці. Кодування комбінації двійкового простого коду двійковим кодом з багатократним повторенням. Кодування інформаційної послідовністі двійкових елементів двійковим двомірним ітеративним кодом та кодування несистематичним кодом Бергера.