Автор: Пользователь скрыл имя, 22 Января 2013 в 14:48, контрольная работа
Задание 1. По построенной в задании 7 из КР «Прикладная математика» двоичной проверочной матрице БЧХ-кода (Вариант 5) найти порождающую матрицу этого кода.
Задание 2. С помощью найденной порождающей матрицы закодировать информацию
Задание 5. Для рассматриваемого в задании 4 кода составить таблицу образующих Г-орбит двойных ошибок, синдромов и норм По синдрому из задания 7 в КР «Прикладная математика» найти вектор-ошибку норменным методом.
Задание 7. Задачу из задания 6 решить норменным методом.
Белорусский государственный институт
информатики и радиоэлектроники
Факультет заочного обучения
Кафедра сети телекоммуникаций
Контрольная работа
по предмету
Теория норм синдромов
Выполнил: Проверил:
Минск 2011
Задание 1 По построенной в задании 7 из КР «Прикладная математика» двоичной проверочной матрице БЧХ-кода (Вариант 5) найти порождающую матрицу этого кода.
Решение:
0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1
0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 0 1
0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1
0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0
Н = 1 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 0 1
0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1
0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0
0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1
0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0
1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1 1 0
Порождающая матрица составляется из системы решений однородной системы уравнений
Воспользуемся методом Гаусса – Жордана. Приведем матрицу к квазитреугольному виду, затем к виду или подобному виду. Здесь единичная матрица порядка
Прибавим 6-ю строку ко 2-й; 8-ю
строку к 7-й и поменяем 2-ю и 7-ю строки местами;
прибавим 8-ю строку к 3-й; 6-ю строку к 8-й
и поменяем 3-ю и 8-ю строки местами; прибавим
3-ю строку к 10-й и поменяем 1-ю и 10-ю строки
местами; прибавим 7-ю и 8-ю строки к 4-й ,
в результате 4-я строка преобразуется
к виду: (
1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 1
0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1
0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0
0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 1 1 1
Н* = 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1
0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1
0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 0
0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 0
0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0
0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1
В матрице Н* 4-ю и 9-ю строки поменяем местами;
прибавим 3-ю строку к 5-й; 9-ю строку к 8-й
и поменяем 5-ю и 8-ю строки местами; 10-ю
строку прибавим к 6-й , в результате 6-я
строка преобразуется к виду: (
1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 1
0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1
0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0
0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0
Н** = 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 0
0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1
0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1
0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 1 1 1
0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0
В матрице Н** 7-ю и 10-ю строки прибавим к 1-й; 10-ю строку прибавим ко 2-й, 4-й и 7-й; 8-ю и 9-ю строки к 3-й; 6-ю и 8-ю строки к 5-й; 7-ю и 8-ю строки поменяем местами; 6-ю, 7-ю и 8-ю строки прибавим к 9-й. В итоге получим матрицу:
1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1
0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0
Н*** = 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 0 1
0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 1
В матрице Н*** 9-ю строку прибавим к 1-й, 4-й строкам. В итоге получим матрицу:
1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1
0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1
0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1
Н′ = 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 0 1
0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 1
Н′ = (Е10|К)
Таким образом,
система линейных уравнений
эквивалентна системе
. В ней 31 неизвестных. Базисный минор
составляют первые 10 столбцов матрицы
и базисными переменными являются
переменные
Поэтому свободными переменными являются
Положим
Тогда базисные переменные принимают
однозначно определённые значения, причем
столбец этих значений
совпадает с первым столбцом подматрицы
матрицы
Первый базисный вектор пространства
решений системы
:
= (
1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
G = 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Задание 2 С помощью найденной порождающей матрицы закодировать информацию
Решение:
Кодовое слово вычисляется по формуле:
= (10 10 10 10 111 011 001 000 100 110 001)
Задание 3 По найденному в задании 2 кодовому слову попытаться восстановить сообщение
Решение:
В силу структуры матрицы информационный вектор идентично отображается на последние 21 координат вектора и, следовательно, однозначно восстанавливается по вектору
Задание 4 По найденному в задании 7 из КР «Прикладная математика» синдрому найти вектор ошибок сведением задачи к квадратному уравнению и решением последнего по формулам Чэня.
Решение:
В задании 7 рассматривается модель ТКС, функционирующая на основе (31, 10) – БЧХ-кода с проверочной матрицей корень полинома . На приёмное устройство поступило очередное сообщение:
с синдромом ошибок
S = (0 0 1 0 0 1 0 0 0 0)T ≠ .
В соответствии со структурой матрицы синдром разбивается на компоненты S1 = (0 0 1 0 0) и S2 = (1 0 0 0 0) Это элементы α2 и α4 поля Галуа GF(25) (31, 10) – БЧХ-кода исправляет одиночные и двойные ошибки в принимаемых сообщениях. Если бы сообщение содержало одиночную ошибку, то его синдром совпадал бы с одним из столбцов проверочной матрицы. Но такое совпадение отсутствует. Пусть, сообщение содержит двойную ошибку на неизвестных двух позициях. Этим позициям соответствуют столбцы (αi α3i)T и (αj α3j)T матрицы с неизвестными целыми значениями Пусть Тогда
Здесь .
Отсюда, ; .
По теореме Виета x и y являются корнями квадратного уравнения . Это уравнение над полем Z/2Z корней не имеет. Но в поле GF(25), непосредственной подстановкой находим корни: α12 и α16.
Следовательно, двойная ошибка произошла на 13-й и 17-й позициях и истинным является сообщение:
= (110 110 111 100 100 010 001
Задание 5. Для рассматриваемого в задании 4 кода составить таблицу образующих Г-орбит двойных ошибок, синдромов и норм По синдрому из задания 7 в КР «Прикладная математика» найти вектор-ошибку норменным методом.
Решение:
Воспользуемся таблицей, задающей поле Галуа GF(25) с помощью полинома .
№ п/п |
Степенное задание |
Полиномиальное задание |
Векторное задание |
1 |
α |
α |
(0, 0, 0, 1, 0) |
2 |
α2 |
α2 |
(0, 0, 1, 0, 0) |
3 |
α3 |
α3 |
(0, 1, 0, 0, 0) |
4 |
α4 |
α4 |
(1, 0, 0, 0, 0) |
5 |
α5 |
α4 + α3 + α + 1 |
(1, 1, 0, 1, 1) |
6 |
α6 |
α3 + α2 + 1 |
(0, 1, 1, 0, 1) |
7 |
α7 |
α4 + α3 + α |
(1, 1, 0, 1, 0) |
8 |
α8 |
α3 + α2 + α + 1 |
(0, 1, 1, 1, 1) |
9 |
α9 |
α4 + α3 + α2 + α |
(1, 1, 1, 1, 0) |
10 |
α10 |
α2 + α + 1 |
(0, 0, 1, 1, 1) |
11 |
α11 |
α3 + α2 + α |
(0, 1, 1, 1, 0) |
12 |
α12 |
α4 + α3 + α2 |
(1, 1, 1, 0, 0) |
13 |
α13 |
α + 1 |
(0, 0, 0, 1, 1) |
14 |
α14 |
α2 + α |
(0, 0, 1, 1, 0) |
15 |
α15 |
α3 + α2 |
(0, 1, 1, 0, 0) |
16 |
α16 |
α4 + α3 |
(1, 1, 0, 0, 0) |
17 |
α17 |
α3 + α + 1 |
(0, 1, 0, 1, 1) |
18 |
α18 |
α4 + α2 + α |
(1, 0, 1, 1, 0) |
19 |
α19 |
α4 + α2 + α + 1 |
(1, 0, 1, 1, 1) |
20 |
α20 |
α4 + α2 + 1 |
(1, 0, 1, 0, 1) |
21 |
α21 |
α4 + 1 |
(1, 0, 0, 0, 1) |
22 |
α22 |
α4 + α3 + 1 |
(1, 1, 0, 0, 1) |
23 |
α23 |
α3 + 1 |
(0, 1, 0, 0, 1) |
24 |
α24 |
α4 + α |
(1, 0, 0, 1, 0) |
25 |
α25 |
α4 + α3 + α2 + α + 1 |
(1, 1, 1, 1, 1) |
26 |
α26 |
α2 + 1 |
(0, 0, 1, 0, 1) |
27 |
α27 |
α3 + α |
(0, 1, 0, 1, 0) |
28 |
α28 |
α4 + α2 |
(1, 0, 1, 0, 0) |
29 |
α29 |
α4 + α + 1 |
(1, 0, 0, 1, 0) |
30 |
α30 |
α4 + α3 + α2 + 1 |
(1, 1, 1, 0, 1) |
31 |
α31 |
1 |
(0, 0, 0, 0, 1) |
32 |
α-∞ |
0 |
(0, 0, 0, 0, 0) |
Для вектора – ошибки синдром где s1 = 1 + α = α13; s2 = 1 + α3 = α23.Тогда = α23/ α39 = α23/ α8 = α15.
Для вектора – ошибки синдром где s1 = 1 + α2 =
= α26; s2 = 1 + α6 = α15.Тогда = α15/ α78 = α15/ α16 =
= α15 · α15/ α16 · α15 = α30/ α31 = α30.
Для вектора – ошибки синдром где s1 = 1 + α3 =
= α23; s2 = 1 + α9 = α25.Тогда = α25/ α69 = α25/ α7 = α18.
Для вектора – ошибки синдром где s1 = 1 + α4 =
= α21; s2 = 1 + α12 = α30.Тогда = α30/ α63 = α30/ α = α29.
Для вектора – ошибки синдром s1 = 1 + α5 =
= α7; s2 = 1 + α15 = α6.Тогда = α6/ α21 = α6 · α10/ α21 · α10 =
= α16/ α31 = α16.
Для вектора – ошибки синдром где s1 = 1 + α6 =
= α15; s2 = 1 + α18 = α19.Тогда = α19/ α45 = α19/ α14 = α5.
Для вектора – ошибки синдром где s1 = 1 + α7 =
= α5; s2 = 1 + α21 = α4.Тогда = α4/ α15 = α4 · α16/ α15 · α16 =
= α20/ α31 = α20.
Для вектора – ошибки синдром где s1 = 1 + α8 =
= α11; s2 = 1 + α24 = α29.Тогда = α29/ α33 = α29/ α2 = α27.
Для вектора – ошибки синдром где s1 = 1 + α9 =
= α25; s2 = 1 + α27 = α17.Тогда = α17/ α75 = α17/ α13 = α4.
Для вектора – ошибки синдром где s1 = 1 + α10 =
= α14; s2 = 1 + α30 = α12.Тогда = α12/ α42 = α12/ α11 = α.
Результаты вычислений сведём в таблицу.
Образующие Г-орбит двойных ошибок, их синдромы и нормы синдромов (15, 7) – БЧХ-коде
|
№ Г-орбиты п/п |
Образующая Г-орбиты |
Синдром |
Норма | |
|
|
||||
|
1 |
α13 |
α23 |
α15 | |
|
2 |
α26 |
α15 |
α30 | |
|
3 |
α23 |
α25 |
α18 | |
|
4 |
α21 |
α30 |
α29 | |
|
5 |
α7 |
α6 |
α16 | |
|
6 |
α15 |
α19 |
α5 | |
|
7 |
α5 |
α4 |
α20 | |
|
8 |
α11 |
α29 |
α27 | |
|
9 |
α25 |
α17 |
α4 | |
|
10 |
α14 |
α12 |
α | |