Корректирующие коды

Строки производящей матрицы линейного блочного
(n, 3)-кода – это три n -разрядные комбинаций (младший разряд – справа), которые в двоичной форме представляют десятичные числа g ₀, g ₁, g ₂. Найти: кодовое расстояние d_код, максимальные кратности гарантированно обнаруживаемых q _o и исправляемых q _и ошибок. Закодировать двоичную комбинацию, соответствующую десятичному числу in, затем двоичную комбинацию на выходе кодера представить в форме десятичного числа out.

Примечание: верхняя строка производящей матрицы g ₀ соответствует младшему разряду комбинации на входе кодера.

 

N n in	g 0 g 1 g 2
0 11 1 1 11 6 2 11 3 3 8 4 4 8 2 5 10 7 6 11 5 7 11 2 8 9 2 9 8 6 10 8 3 11 9 2 12 9 2 13 10 7 14 10 1 15 11 2 16 10 1 17 12 5 18 11 3 19 8 1 20 12 5 21 9 5 22 8 4 23 9 1 24 8 2 25 12 7 26 10 1 27 11 5 28 12 7 29 10 3 30 11 5 31 10 6 32 10 7 33 11 7 34 8 4 35 9 3 36 11 3 37 12 1 38 11 6 39 12 1 40 10 5 41 11 2 42 8 1 43 11 1 44 12 5 45 11 7 46 11 4 47 9 2 48 11 5 49 11 1	793 1261 1689 823 1528 1613 909 1342 1888 99 143 223 103 179 255 407 641 883 641 1398 1856 796 1252 2045 150 298 467 107 159 243 88 180 249 221 378 430 186 367 389 298 541 798 443 683 975 616 1222 1833 353 542 779 1025 2484 3544 798 1496 1974 111 144 242 1558 2769 3821 230 306 390 112 137 234 230 381 421 70 137 211 1857 2967 3347 479 728 778 742 1481 1815 2047 2936 3222 505 695 933 575 1216 2004 370 570 808 449 566 965 948 1299 1981 87 130 217 153 272 498 798 1240 1978 1722 3029 3879 581 1034 1919 1810 2694 3770 324 677 835 692 1267 1742 102 155 216 954 1382 1844 1411 3007 4059 720 1279 1983 813 1167 1983 238 280 497 542 1155 1595 537 1196 1799

Форма таблицы ответов:

N=28

dкод	q o	q и	out	S

Линейные блочные коды

Двоичные комбинации, соответствующие пяти десятичным числам (n, in, g ₀, g ₁, g ₂) из задачи 5, считать строками проверочной матрицы H кода (n, n -5).

Определить: способен ли этот код обнаружить любую однократную ошибку (d=1, если способен, d=0 в противном случае);

способен ли этот код исправить любую однократную ошибку (c=1, если способен, c=0 в противном случае).

Форма таблицы ответов:

N=28

d	c	S

7) Неравенство Хэмминга для линейного блочного кода	N n k	p
Требуется построить линейный блочный (n, k)-код. Определить теоретический предел для этого кода – найти максимальную кратность исправляемых ошибок q и. Определить вероятность ошибочного декодирования кодовой комбинации Pош, если ошибки в отдельных символах в канале передачи происходят с вероятностью p, а ошибки в разных символах независимы. В ответе для величины Pош оставить 6 знаков после десятичной точки.	0 32 19 1 38 11 2 34 14 3 48 13 4 45 11 5 44 25 6 46 23 7 48 21 8 48 23 9 23 13 10 34 10 11 20 9 12 33 18 13 24 11 14 26 12 15 43 18 16 39 19 17 43 8 18 45 22 19 34 12 20 22 10 21 30 6 22 32 20 23 28 13 24 42 12 25 21 14 26 30 8 27 24 5 28 23 6 29 25 7 30 27 15 31 30 6 32 39 7 33 47 18 34 23 12 35 36 13 36 46 12 37 46 11 38 31 18 39 40 22 40 28 16 41 49 20 42 37 16 43 23 7 44 38 9 45 30 8 46 34 11 47 48 11 48 49 14 49 35 8	0.129 0.085 0.196 0.181 0.192 0.056 0.084 0.072 0.038 0.148 0.141 0.021 0.129 0.072 0.154 0.184 0.129 0.161 0.118 0.091 0.038 0.025 0.067 0.061 0.175 0.029 0.030 0.035 0.193 0.178 0.093 0.139 0.190 0.020 0.029 0.096 0.129 0.095 0.132 0.021 0.091 0.077 0.174 0.056 0.104 0.098 0.095 0.124 0.081 0.191

Форма таблицы ответов:

N=28

q и	Pош	S
	0.000124	5.000124

Вопросы для самопроверки по курсу

1. В чем разница понятий “информация” и “сигнал”?

2. Приведите примеры радиоэлектронных устройств, предназначенных не для передачи информации.

3. Назовите два основных признака того, что сигнал не несет информации.

4. Почему для математического описания сигналов используют вероятностные модели?

5. Может ли детерминированный сигнал переносить информацию?

6. Какие случайные события (величины) называются независимыми?

7. Что нужно задать для полного вероятностного описания: символа? последовательности символов? последовательности отсчетов сигнала? непрерывной случайной функции?

8. Из каких соображений выбирается шаг квантования непрерывного сигнала:
по времени? по напряжению?

9. Опишите этапы аналого-цифрового преобразования непрерывного сигнала.

10. Опишите этапы цифро-аналогового преобразования.

11. Изобразите обобщенную модель системы передачи информации. Опишите функции кодера и декодера.

12. Назовите способы манипуляции гармонической несущей. Чем обусловлен выбор того или иного способа?

13. Каковы недостатки многопозиционных методов манипуляции гармонической несущей?

14. В чем отличие аддитивной помехи от мультипликативной? Приведите примеры каналов связи с такими помехами.

15. Что такое собственная информация и энтропия дискретной случайной величины?

16. Дайте определение взаимной информации переданного и принятого символов.
Как влияет на ее величину интенсивность помех в канале связи?

17. От чего зависит пропускная способность непрерывного канала связи с аддитивным белым шумом?

18. Что такое избыточность сигнала? В каких случаях она полезна, а когда нет?

19. Когда полезно применять кодирование с малой избыточностью?

20. Какой смысл вкладывают в понятия: “кодирование источника”? “канальное кодирование”?

21. Каково значение минимально-возможной средней длины кодовой комбинации?

22. Всегда ли удается закодировать сигнал так, чтобы избыточность на выходе кодера была нулевой?

23. Когда полезно кодировать блоки букв, а не отдельные буквы?

24. Какой способ разделения кодовых комбинаций применяется в кодах, обладающих малой избыточностью?

25. В чем заключается главный недостаток кодов Хафмана и Шеннона-Фано?

26. Откуда берется кодовая таблица, используемая при кодировании кодом Лемпела-Зива?

27. Чем определяется корректирующая способность кода? Поясните на примере.

28. Какие коды называются корректирующими?

29. Что значит “обнаружить ошибки” при декодировании кодовой комбинации?

30. Что значит “исправить ошибки” при декодировании кодовой комбинации?

31. Каков характерный признак, позволяющий отличить кодовую таблицу линейного блочного кода от кодовых таблиц других кодов?

32. Что такое проверочная матрица линейного блочного кода? Как она используется при обнаружении ошибок в принятой комбинации?

33. Каков характерный признак, позволяющий отличить кодовую таблицу циклического кода от кодовых таблиц других кодов?

34. Чему равно количество комбинации в кодовой таблице линейного блочного кода?

35. Почему в проверочной матрице не может быть нулевых: столбцов? строк?

36. Какой смысл имеют строки проверочной матрицы?

37. По каким признакам можно определить, что проверочная матрица принадлежит коду, способному исправить любую одиночную ошибку?

38. Чем обусловлена популярность циклических кодов? Из каких логических элементов состоят кодер и декодер?

39. В чем заключается фундаментальное свойство комбинаций циклического кода?

40. Поясните суть декодирования по минимуму расстояния.

41. Почему декодирование по минимуму расстояния применяется редко?

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРы

Основная

1. Акулиничев Ю.П. Теория электрической связи. Часть 1. – Томск, ТМЦДО. – 127 с.

2. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. - М.: Наука, 1982. - 416 с.

3. Галлагер Р. Теория информации и надежная связь. - М.: Сов. радио, 1974.

4. Зюко А.Г, Кловский Д.Д., Коржик В.И., Назаров М.В. Теория электрической связи, под ред. Д.Д. Кловского. - М.: Радио и связь, 1997. - 432 с.

5. Зюко А.Г. и др. Теория передачи сигналов. - М.: Связь, 1980 (и последующие издания), 288 с.

6. Тарасенко Ф.П. Введение в курс теории информации. -Томск: ТГУ, 1963.

Дополнительная

7. Харкевич А..А. Борьба с помехами. - М.: Наука, 1965.

8. Хэмминг Р.В. Теория кодирования и теория информации. - М: Радио и связь, 1983. - 176 с.

9. Кульбак С. Теория информации и статистика. - М.: Наука, 1967.

10. Клюев Л.Л. Теория электрической связи.- Мн.: Дизайн ПРО, 1998.- 336 с.

11. Кловский Д.Д., Шилкин В.А. Теория электрической связи. Сб. задач и упражнений. Учебное пособие для втузов. - М.: Радио и связь, 1990. - 280 с.

12. Орлов В.А., Филиппов Л.И. Теория информации в упражнениях и задачах. Учебное пособие для втузов. М.: Высшая школа, 1976. - 136 с.

13. Цимбал В.П. Задачник по теории информации и кодированию. - Киев: Вища школа, 1976. – 276 с.

14. Лосев Ю.И., Плотников Н.Д. Основы теории передачи данных. Сборник задач. - Киев: Вища школа, 1977. - 160 с.

15. Акулиничев Ю.П., Дроздова В.И. Сборник задач по теории информации. - Томск: ТГУ, 1976. - 146 с.