- •Введение
- •Элементы теории чисел
- •Модулярная арифметика
- •Алгоритм Евклида для нахождения наибольшего общего делителя
- •Вычисление обратных величин
- •Основные способы нахождения обратных величин
- •Расширенный алгоритм Евклида
- •Китайская теорема об остатках
- •Вычисления в конечных полях
- •Квадратичные вычеты
- •Свойства многочленов в двоичном поле gf(2)
- •Достоинства вычислений в поле Галуа gf(2 n)
- •Кодирование
- •Оптимальное кодирование
- •Обнаружение и исправление ошибок
- •Общие понятия
- •Линейные групповые коды
- •Код Хэмминга
- •Циклические коды
- •Построение и декодирование конкретных циклических кодов
- •Циклические коды, исправляющие две и большее количество ошибок, d0 5
- •Сжатие информации
- •Исключение повторения строк в последующих строках
- •Алгоритм lzw
- •Задания для самостоятельного выполнения
- •Расчетно-графическая работа №1
- •Расчетно-графическая работа №2
- •Список рекомендуемой литературы
- •Рекомендованная литература
-
Алгоритм lzw
-
Задания для самостоятельного выполнения
-
Расчетно-графическая работа №1
-
Задание 1.
Построить порождающую матрицу группового кода, исправляющего одну ошибку, оптимального по числу корректирующих разрядов для передачи не менее (см. таблицу 5.1.1) сообщений
Таблица 5.1.1 – Количество сообщений
|
№ вари-анта |
k |
№ вари-анта |
k |
№ вари-анта |
k |
№ вари-анта |
k |
№ вари-анта |
k |
№ вари-анта |
k |
|
1 2 3 4 5 6 7 8 9 10 |
4000 1000 1500 3500 2500 800 3000 2000 500 200 |
11 12 13 14 15 16 17 18 19 20 |
300 100 1800 1200 2200 520 40 5000 80 5500 |
21 22 23 24 25 26 27 28 29 30 |
60 300 3200 1900 70 750 6000 150 1250 7000 |
31 32 33 34 35 36 37 38 39 40 |
4000 1000 1500 3500 2500 800 3000 2000 500 200 |
41 42 43 44 45 46 47 48 49 50 |
300 100 1800 1200 2200 520 40 5000 80 5500 |
51 52 53 54 55 56 57 58 59 60 |
60 300 3200 1900 70 750 6000 150 1250 7000 |
|
61 62 63 64 65 66 67 68 69 70 |
4000 1000 1500 3500 2500 800 3000 2000 500 200 |
71 72 73 74 75 76 77 78 79 80 |
300 100 1800 1200 2200 520 40 5000 80 5500 |
81 82 83 84 85 86 87 88 89 90 |
60 300 3200 1900 70 750 6000 150 1250 7000 |
91 92 93 94 95 96 97 98 99 100 |
4000 1000 1500 3500 2500 800 3000 2000 500 200 |
101 102 103 104 105 106 107 108 109 110 |
300 100 1800 1200 2200 520 40 5000 80 5500 |
111 112 113 114 115 116 117 118 119 120 |
60 300 3200 1900 70 750 6000 150 1250 7000 |
Задание 2.
Построить код Хэмминга для передачи информационной комбинации:
Таблица 5.1.2 – Информационные комбинации
|
№ варианта |
Комбинация |
№ варианта |
Комбинация |
|
1 2 3 4 5 6 7 8 9 10 11 |
1100110101 11001111011 1010101011 111110101 100001111 11001010010 100110111 1011111011 10110010010 1110010010101 100111110010 |
61 62 63 64 65 66 67 68 69 70 71 |
100110101 11001111011 1010101011 111110101 100001111 11001010010 100110111 1011111011 100110010010 1110010010101 100111110010 |
|
№ варианта |
Комбинация |
№ варианта |
Комбинация |
|
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
11011111000001 1110101000 1000001011 110110101 10001111001 101010111100011 11100111 11010101011111 11100111 100010101111011 100110010111 101110111 1111111010 10001110000111 11001001011 10100101 1110001111001 1000011011 10001101 |
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
11011111000001 1110101000 1000001011 110110101 10001111001 101010111100011 11100111 11010101011111 11100111 100010101111011 100110010111 101110111 1111111010 10001110000111 11001001011 10100101 1110001111001 1000011011 10001101 |
|
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
11011111000001 1110101000 1000001011 110110101 10001111001 101010111100011 11100111 11010101011111 11100111 100010101111011 100110010111 101110111 1111111010 10001110000111 11001001011 10100101 1110001111001 1000011011 10001101 |
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
11011111000001 1110101000 1000001011 110110101 10001111001 101010111100011 11100111 11010101011111 11100111 100010101111011 100110010111 101110111 1111111010 10001110000111 11001001011 10100101 1110001111001 1000011011 10001101 |
|
№ варианта |
Комбинация |
№ варианта |
Комбинация |
|
50 51 52 53 54 55 56 57 58 59 60 |
11011111000001 1110101000 1000001011 110110101 10001111001 101010111100011 11100111 11010101011111 11100111 100010101111011 10001101 |
110 111 112 113 114 115 116 117 118 119 120 |
11011111000001 1110101000 1000001011 110110101 10001111001 101010111100011 11100111 11010101011111 11100111 100010101111011 100110010111 |