МАТЕМАТИЧЕСКИЕ МЕТОДЫ ТЕОРИИ СЕТЕЙ СВЯЗИ И ПЕРЕДАЧИ ДАННЫХ (ЦИКЛИЧЕСКИЕ КОДЫ) КОНТРОЛЬНАЯ РАБОТА. Математические методы теории сетей связи. 1 Основные алгебраические системы, используемые в теории кодирования

• Название: 1 Основные алгебраические системы, используемые в теории кодирования
• Анкор: МАТЕМАТИЧЕСКИЕ МЕТОДЫ ТЕОРИИ СЕТЕЙ СВЯЗИ И ПЕРЕДАЧИ ДАННЫХ (ЦИКЛИЧЕСКИЕ КОДЫ) КОНТРОЛЬНАЯ РАБОТА
• Дата: 19.05.2022
• Размер: 92.63 Kb.
• Имя файла: Математические методы теории сетей связи.docx
• Тип: Решение; #537662

Математические методы теории сетей связи и передачи данных


Содержание

1 Основные алгебраические системы, используемые в теории кодирования

Задание 1.5

Построить все возможные двоичные последовательности длины 5. Являются ли они группой по операции поразрядного сложения по mod 2? Доказать.
Решение

Количество двоичных последовательностей длины 5 равно :

0	0	0	0	0
0	0	0	0	1
0	0	0	1	0
0	0	0	1	1
0	0	1	0	0
0	0	1	0	1
0	0	1	1	0
0	0	1	1	1
0	1	0	0	0
0	1	0	0	1
0	1	0	1	0
0	1	0	1	1
0	1	1	0	0
0	1	1	0	1
0	1	1	1	0
0	1	1	1	1
1	0	0	0	0
1	0	0	0	1
1	0	0	1	0
1	0	0	1	1
1	0	1	0	0
1	0	1	0	1
1	0	1	1	0
1	0	1	1	1
1	1	0	0	0
1	1	0	0	1
1	1	0	1	0
1	1	0	1	1
1	1	1	0	0
1	1	1	0	1
1	1	1	1	0
1	1	1	1	1

Для того, чтобы данная последовательность являлась группой по операции поразрядного сложения по модулю два, необходимо выполнение групповых аксиом. Проверим их выполнение.

1. 
   Замкнутость. Поразрядное сложение по модулю 2 для суммы любых чисел из данной совокупности дает число из этой совокупности (других пятиразрядных двоичных чисел не существует).
   
2. 
   Ассоциативность и коммуникативность. Для операции сложения по модулю 2 результат сложения не зависит от очередности выбора суммируемых элементов из некоторой ассоциации, поэтому для нее ассоциативный и коммуникативный законы выполняются всегда.
   
3. 
   Наличие единичного элемента. Для данной совокупности единичным элементом будет являться последовательность 00000, так как при сложение ее с любой другой последовательностью не изменяет значения последней.
   
4. 
   Существование обратных элементов. Для любой последовательности сумма с точно такой же последовательностью даст в результате нулевую последовательность 00000, т. е. каждая двоичная последовательность является для себя обратной.
   

Таким образом, все возможные двоичные последовательности длины 5 являются группой по операции поразрядного сложения по mod 2.

2 Кольца многочленов и поля Галуа

Задание 2.4

Используя алгоритм Евклида, найти HOД (1573,308) и целые числа A и B, удовлетворяющие равенству HOД (1573,308) = 1573A+308B.
Решение

Воспользуемся алгоритмом Евклида:







Т.е. НОД (1573,308) = 11
Представим полученный результат в виде , для чего воспользуемся вычислениями НОД.
Выражение подставляем во второй шаг алгоритма:


Теперь подставляем выражения для 33 и 11 в последний шаг алгоритма:


И получаем:


Дополняем найденные равенства двумя формальными равенствами в качестве исходных:










Определяем целую часть дроби – общее выражение для , в этом случае представимо как .
Для наглядности представим в виде таблицы:

Шаг
-1	1	0	1573
0	0	1	308
1	1	-5	33
2	-9	46	11
3	28	-143	0

3 Теорема Ферма и циклотомические классы

Задание 3.4

Определить все неприводимые сомножители следующих двучленов:

1. 
   ;
   
2. 
   ;
   
3. 
   .
   

Решение
А)

Поскольку , то достаточно найти неприводимые сомножители .

Проверяем степени двойки.




Имеем: , значит все неприводимые многочлены 4-й степени будут делителями и, следовательно, . Таких многочленов три:










Имеем: , значит все неприводимые многочлены 2-й степени будут делителями и, следовательно, . Такой многочлен только один:






Имеем: , значит единственный неприводимый многочлен 1-й степени делит . Получили:


А, значит:



Б) ;
Т.к. , а 5 – простое число, то делителями двучлена будут только и все неприводимыми сомножителями 5-й степени:





Т.е.:


В) .

Т.к. , то единственным неприводимым сомножителем будет являться неприводимый многочлен 1-й степени:

4 Разложение на неприводимые сомножители

Задание 4.1

Найти все неприводимые сомножители двучленов следующих степеней: 23, 51, 73, 85, 127.
Решение

Для простых показателей степени разложение имеет вид
, где второй сомножитель неприводим.
Поэтому (числа 23, 73, 127 – простые):






Для составных показателей , где – простые числа, разложение имеет вид (последний сомножитель - неприводим):



Т.к. , , поэтому:

5 Декодер Меггита

Задание 5.1

Нарисовать схему декодера Меггита для исправления однократных ошибок укороченными циклическими кодами Хемминга:

1. 
   (10,5) с ;
   
2. 
   (11,5) с ;
   
3. 
   (12,5) с .
   

Решение

В состав декодера циклического кода входят: буферный регистр на 10 (11 и 12 соответственно) разрядов, регистр-делитель, схема ИЛИ-НЕ, схемы ИЛИ-НЕ и И, а также управляющее устройство, замыкающее ключ К после 10 (11 и 12) такта.

На вход регистра-делителя поступает кодовая комбинация, которая делится на порождающий многочлен . По окончании деления в триггерах 1-4 делителя записывается остаток от деления. Если при этом хотя бы один из этих триггеров находится в единичном состоянии, то это означает, что в принятой кодовой комбинации имеется ошибка. На выходе схемы ИЛИ-НЕ формируется нулевой сигнал, который при замкнутом ключе К поступает на вход схемы И. На первый же вход схемы И поступает исходная кодовая комбинация. Под действием нулевого сигнала с выхода ИЛИ-НЕ схема И запирается и кодовая комбинация не поступает на выход схемы декодера.

Если же триггеры 1-4 обнулены после 10 такта, то на выходе схемы ИЛИ-НЕ имеет место единичный сигнал. Тогда схема И пропускает на выход безошибочно принятую (или с необнаруженными ошибками) кодовую комбинацию, причем потребителю направляются первые 5 разрядов, составляющих информационную кодовую комбинацию.

Сумматоры в схему включаются перед ячейками, соответствующими слагаемым порождающего многочлена , исключая старшую степень.

А) (10,5) с


Б) (11,5) с


В) (12,5) с

6 Быстрое декодирование кодов БЧХ

Задание 6.1

Вычислить порождающий многочлен для кода Рида-Соломона (7,5).
Решение

Порождающий многочлен вычисляется по формуле:



В нашем случае .

Значения элементов поля :

0	000
	100
	010
	001
	110
	011
	111
	101
	100

И получаем:




Т.е. порождающий многочлен для кода Рида-Соломона (7,5), способного исправлять до ошибки имеет вид