Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

Тема- Двійкові коди що виправляють однократні помилки.html

Работа добавлена на сайт samzan.ru: 2016-01-17


Завдання №1:

Побудувати твірну матрицю двійкового систематичного ( групового )  коду, який має  

N0 = 128  дозволених кодових комбінацій та здатен виправляти всі однократні помилки. Навести  приклад кодування за допомогою твірної матриці.

Розв'язання.

Кількість інформаційних розрядів коду  k =  log 128 = 7. Кількість перевірочних розрядів визначається як найменше ціле r,  яке задовольняє нерівності  2 r  =  r + 1 ; таким значенням буде  = 4 . Довжина коду =  r  = 11 . Таким чином, твірна матриця G n, має 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 ) - коду, містять помилку, якщо відомо, що код побудований за твірною матрицею:

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 – 11111112  3  4  5 ) .

з наведених комбінацій 0100010, 0100101, 1001011 двійкового групового ( 7,4 ) - коду, комбінації 0100010 та 1001011  містять помилку.

Завдання №3:

Визначити, які з комбінацій  0100011, 0100101, 1101011 двійкового групового  ( 7,4 ) - коду  містять помилку, якщо відомо, що перевірочна матриця коду має вигляд:

Н 7,3  =  .

Розв'язання.

Перевірочна матриця  утворюється за допомогою твірної матриці,  яка містить три стовпці і чотири рядки, кожний рядок якої відповідає стовпцю перевірочної під матриці та одиничної під-матриці  E .  Таким  чином:

=>

Одержуємо твірну матрицю 7,4  

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 – 11111112  3  4  5 ) .

з наведених комбінацій 0100011, 0100101, 1101011 двійкового групового ( 7,4 ) - коду, комбінації 0100011, 1101011 містять помилку.

Завдання №4:

Закодувати комбінації двійкового простого коду А 1 = 11001 та А 2 = 00111   довжиною k = 5 двійковим кодом з багатократним повторенням, здатним виправляти  помилки кратності  s = 1. Показати процес виправлення помилок на прикладі і визначити надмірність коду.

Розв’язання. 

Для коду А 1 число m повторень при виправленні однієї помилки визначається з виразу d min =  + 1. Кодова відстань при виправленні однократної помилки повинна бути не менша за  d min = 3, тому   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 =  + 1. Кодова відстань при виправленні однократної помилки повинна бути не менша за  d min = 3, тому   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. Довжина цієї комбінації  = 25,  вона  містить  =13  інформаційних та  = 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 log 2 ( 3 + 5 + 6 + 7 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 17+18+19 ) =

log159 =7,13

тобто  = 7.

Далі визначимо сумарну вагу комбінації первинного коду, для чого  треба додати послідовно вагу  2, 6, 7, 9, 12 і 14 розрядів, одержане десяткове число записати у двійковій формі 6 двійковими розрядами, інвертувати його і дописати до комбінації первинного коду:  5 + 10 + 11+13+17+19 =75,  7510 = 1001011 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 / n = 7 / 21 = 0,33(3).

Висновок: У лабораторній роботі були приклади кодування за допомогою твірної матриці. Визначені комбінацій двійкового групового коду які містять помилку за допомогою твірної матриці та перевірочної матриці. Кодування комбінації двійкового простого коду двійковим кодом з багатократним повторенням. Кодування інформаційної послідовністі двійкових елементів двійковим двомірним ітеративним кодом та кодування несистематичним кодом Бергера.




1. Тема 3 Структура культуры 1
2. Реферат на тему- Основи туризму ЗНАЧЕННЯ ТУРИЗМУ ДЛЯ ДОПРИЗОВНОЇ ПІДГОТОВКИ Туризм г це не т
3. никак это моя история и больше ничья да и быть никогда не могла ничьей только моей ~ со сна который привиде
4. Наказание за изготовления или сбыта поддельных денег или ценных бумаг
5. Перечень пожертвований сделанных родом Демидовых государству и общественным учреждениям подготовленный
6. Лабораторная работа ’ 4 по дисциплине ldquo;Сети ЭВМ и телекоммуникации rdquo;
7. Роль СМИ
8. опасное техногенное происшествие возникшее в процессе движения по дороге транспортного средства и с его уч
9. 1; n360013мин1; T2106306 Hм; T3 318264 Нм; Р221
10. малый жанр греческой эллинистической поэзии и своего рода упражнение в риторике
11. Контрольная работа по геометрии за 3 четверть.html
12. О туризме и туристской деятельности в Российской Федерации Актуальность В настоящее врем
13. Реферат- Деловое мышление
14. Лабораторная работа 1 Задание- При помощи табличного процессора Microsoft Excel определить целесообразность п
15. Полномочия государственных органов власти и местного самоуправления в области защиты населения от чрезвычайных ситуаций
16. иллюзорная реальность оборотная сторона Брахмана пестрое покрывало его скрывающее
17. тема в большой системе городов
18. і. В вектори компланарні
19. Социальная психология управления Общение в конфликте.
20. Коллектив