1) теория норм синдромов 2) Сети телекоммуникаций 3) заочная форма 4) контрольная 5) 2012 года 6) вариант 7 Задание 1. Найти порождающую ( 21 * 31) -матрицу G по построенной в задании 7 из контрольной работы «Прикладная математика» для двоичной проверочной (10* 31) -матрицы H реверсивного-кода. Решение H=(■(1&x&…&x^30@1&x^(-1)&…&x^(-30) ))= =(■(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&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&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&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@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&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0&0&1&0&0&0@0&0&1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0&0&1&0&0@0&0&0&1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0&0&1&0@0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0&0&1&0&0&0&0&1@1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0&0&1&0&0&0&0)) Прибавим к 2-ой строке 8-ю, к 3-ой строке – 5-ю, к 4-й строке – 6-ю, к 6-ой – 8-ю, к 7-ой – 10-ю, к 8-ой – 9-ю. H^*=(■(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&1&0&1&1&1&0&1&1&1&0&1&0&0&0&1&1&1&0&0&0@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@0&0&0&1&0&1&0&1&0&0&1&1&1&0&1&0&0&0&0&1&0&1&1&1&0&0&1&0&1&0&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@0&1&0&0&0&0&1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0@1&0&0&0&0&1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0&0@0&1&0&0&1&0&0&0&0&1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1@0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0&0&1&0&0&0&0&1@1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0&0&1&0&0&0&0)) Прибавим к 1-ой строке 8-ю, ко 2-ой -4-ю , к 5-ой – 7-ю, к 9-ой – 8-ю и 4-ю, к 10-ой – 3-ю и 2-ю. H^(**)=(■(0&1&0&0&0&0&0&1&0&0&1&1&0&0&0&0&1&0&1&0&0&1&0&1&0&0&0&0&1&1&0@0&0&0&1&0&0&1&0&0&0&1&0&1&1&0&1&0&1&1&0&0&0&1&1&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@0&0&0&1&0&1&0&1&0&0&1&1&1&0&1&0&0&0&0&1&0&1&1&1&0&0&1&0&1&0&1@0&0&0&0&0&0&0&1&1&1&0&0&0&1&0&1&1&1&0&1&1&1&0&1&0&0&0&1&1&1&0@0&1&0&0&0&0&1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0@1&0&0&0&0&1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0&0@0&1&0&0&1&0&0&0&0&1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1@0&0&0&0&0&0&0&0&1&1&1&0&0&0&1&0&1&1&1&0&1&1&1&0&1&0&0&0&1&1&1@0&0&0&0&1&0&0&0&1&1&1&1&1&1&0&0&0&1&0&0&0&0&0&1&1&0&0&0&1&1&0)) Прибавим ко 1-ой строке – 5-ю и 9-ю, к 3-ей – 5-ю и 9-ю, к 4-ой – 5-ю и 9-ю, к 5-ой – 9-ю, к 7-ой – 5-ю и 9-ю,к 8-ой – 10-ю и 9-ю, к 10-ой – 9-ю. H^(***)=(■(0&1&0&0&0&0&0&0&0&0&0&1&0&1&1&1&1&0&0&1&0&1&1&0&1&0&0&1&1&1&1@0&0&0&1&0&0&1&0&0&0&1&0&1&1&0&1&0&1&1&0&0&0&1&1&0&1&0&1&1&0&1@1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&1&1&1&0&0&1&0&1&1&0&1&0&0&1&1&1@0&0&0&1&0&1&0&0&0&0&0&1&1&1&0&1&0&0&1&0&0&1&0&0&1&0&1&1&1&0&0@0&0&0&0&0&0&0&1&0&0&1&0&0&1&1&1&0&0&1&1&0&0&1&1&1&0&0&1&0&0&1@0&1&0&0&0&0&1&0&1&0&1&1&1&0&1&1&0&0&0&1&1&1&1&1&0&0&1&1&0&1&0@1&0&0&0&0&1&0&0&0&1&0&1&0&0&0&1&0&0&0&0&1&1&0&1&1&1&1&1&1&0&1@0&1&0&0&0&0&0&0&0&1&0&0&1&0&0&1&1&1&0&0&1&1&0&0&1&1&1&0&0&1&0@0&0&0&0&0&0&0&0&1&1&1&0&0&0&1&0&1&1&1&0&1&1&1&0&1&0&0&0&1&1&1@0&0&0&0&1&0&0&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1&1&1&0&0&0&0&0&0&1)) Прибавим к 2ой строке – 6-ю,8-ю,9-ю, к 4-ей –2-ю, 6-ю,8-ю,9-ю, к 8-ой –1-ю H^(****)=(■(0&1&0&0&0&0&0&0&0&0&0&1&0&1&1&1&1&0&0&1&0&1&1&0&1&0&0&1&1&1&1@0&0&0&1&0&0&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1&1&1&0&0&0&0&0&0&1&0@1&0&1&0&0&0&0&0&0&0&0&0&1&0&1&1&1&1&0&0&1&0&1&1&0&1&0&0&1&1&1@0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1&1&1&0@0&0&0&0&0&0&0&1&0&0&1&0&0&1&1&1&0&0&1&1&0&0&1&1&1&0&0&1&0&0&1@0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1&1&1@1&0&0&0&0&1&0&0&0&1&0&1&0&0&0&1&0&0&0&0&1&1&0&1&1&1&1&1&1&0&1@0&0&0&0&0&0&0&0&0&1&0&1&1&1&1&0&0&1&0&1&1&0&1&0&0&1&1&1&1&0&1@0&0&0&0&0&0&0&0&1&1&1&0&0&0&1&0&1&1&1&0&1&1&1&0&1&0&0&0&1&1&1@0&0&0&0&1&0&0&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1&1&1&0&0&0&0&0&0&1)) Прибавим к 7-ой строке – 4-ю и 8-ю, к 3-ой строке – 4-ю,8-ю и 7-ю, к 9-ой строке –8-ю. И переставим строки : H^'=(■(1&0&0&0&0&0&0&0&0&0&1&0&1&1&1&1&0&0&1&0&1&1&0&1&0&0&1&1&1&1&0@0&1&0&0&0&0&0&0&0&0&0&1&0&1&1&1&1&0&0&1&0&1&1&0&1&0&0&1&1&1&1@0&0&1&0&0&0&0&0&0&0&1&0&0&1&0&0&1&1&1&0&0&1&1&0&0&1&1&1&0&0&1@0&0&0&1&0&0&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1&1&1&0&0&0&0&0&0&1&0@0&0&0&0&1&0&0&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1&1&1&0&0&0&0&0&0&1@0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1&1&1&0@0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&1&1&1&1&0&1&0&1&0&1&1&1&1@0&0&0&0&0&0&0&1&0&0&1&0&0&1&1&1&0&0&1&1&0&0&1&1&1&0&0&1&0&0&1@0&0&0&0&0&0&0&0&1&0&1&1&1&1&0&0&1&0&1&1&0&1&0&0&1&1&1&1&0&1&0@0&0&0&0&0&0&0&0&0&1&0&1&1&1&1&0&0&1&0&1&1&0&1&0&0&1&1&1&1&0&1))=(E_10 |K) Базисный минор составляют первые 10 столбцов матрицы H^' и базисными переменными являются переменные x1 , x 2 ,..., x10 . Поэтому свободными переменными являются x11 , x12 ,..., x31 . Положим x11= 1, x12= 0, ..., x31=0. Тогда базисные переменные принимают однозначно определенные значения, причем столбец этих значений ( x1 , x 2 ,..., x10) совпадает с первым столбцом подматрицы K матрицы H^'. А в целом получим первый базисный вектор пространства решений с1=(1 0 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0)и одновременно первый сттолбец матрицы G. И так находим остальные решения. Порождающая матрица G Задание 2. С помощью найденной порождающей матрицы закодировать информацию: i= (111 011 001 000 100 110 001) c=i*G=(010 100 000 111 101 100 100 010 011 000 1) Задание 3. По найденному в задании 2 кодовому слову c попытаться восстановить сообщение i. В силу структуры матрицы G информационный вектор i идентично отображается на последние 21 координат вектора c и, следовательно, однозначно восстанавливается по вектору c . Т.е. имея c, восстановим i как последние 21 значение вектора c: c=i*G=(010 100 000 111 101 100 100 010 011 000 1) i= (111 011 001 000 100 110 001) Задание 4. По найденному в задании 8 синдрому из контрольной работы «Прикладная математика» найти вектор ошибок сведением задачи к квадратному уравнению и решением последнего по формулам Чэня. S=(1 0 0 1 1 1 1 1 0 0)=(x^17,x^13) x ̅=(011 010 110 100 000100 001 000 000 000 1) Тогда: {█(x_1+x_2=x^17@1/x_1 +1/x_2 =x^13 )┤ Решим систему по формулам Чэня: Уравнение: xy=x^17/x^13 =x^4 a^2+x^17 a+x^4=0 a_1=x^15 a_2=x^20 Значит ошибочными были позиции 16 и 21, а исправленное сообщение: x ̅=(011 010 110 100 000 000 000 000 000 000 1) Задание 5. Для рассматриваемого в задании 4 кода данной контрольной работы составить таблицу образующих e_i Г-орбит двойных ошибок, синдромов S(e_i) и норм N_i=N(S(e_i))По синдрому из задания 8 в контрольной работе «Прикладная математика» найти вектор-ошибку норменным методом. Решение Воспользуемся таблицей: Степенное задание Полиномиальное задание Векторное задание x^(-∞) 0 (0,0,0,0,0) x^1 x (0,0,0,1,0) x^2 x^2 (0,0,1,0,0) x^3 x^3 (0,1,0,0,0) x^4 x^4 (1,0,0,0,0) x^5 x^2+1 (0,0,1,0,1) x^6 x^3+x (0,1,0,1,0) x^7 x^4+x^2 (1,0,1,0,0) x^8 x^3+x^2+1 (0,1,1,0,1) x^9 x^4+x^3+x (1,1,0,1,0) x^10 x^4+1 (1,0,0,0,1) x^11 x^2+x+1 (0,0,1,1,1) x^12 x^3+x^2+x (0,1,1,1,0) x^13 x^4+x^3+x^2 (1,1,1,0,0) x^14 x^4+x^3+x^2+1 (1,1,1,0,1) x^15 x^4+x^3+x^2+x+1 (1,1,1,1,1) x^16 x^4+x^3+x+1 (1,1,0,1,1) x^17 x^4+x+1 (1,0,0,1,1) x^18 x+1 (0,0,0,1,1) x^19 x^2+x (0,0,1,1,0) x^20 x^3+x^2 (0,1,1,0,0) x^21 x^4+x^3 (1,1,0,0,0) x^22 x^4+x^2+1 (1,0,1,0,1) x^23 x^3+x^2+x+1 (0,1,1,1,1) x^24 x^4+x^3+x^2+x (1,1,1,1,0) x^25 x^4+x^3+1 (1,1,0,0,1) x^26 x^4+x^2+x+1 (1,0,1,1,1) x^27 x^3+x+1 (0,1,0,1,1) x^28 x^4+x^2+x (1,0,1,1,0) x^29 x^3+1 (0,1,0,0,1) x^30 x^4+x (1,0,0,1,0) x^31 1 (0,0,0,0,1)
Решим задачу норменным методом: S=(1 0 0 1 1 1 1 1 0 0)=(x^17,x^13) N(S)=x^13*x^17=x^30 Следовательно, двойная вектор-ошибка e , которая присутствует в сообщении x , принадлежит Г-орбите J=<e_1,6> и получается циклическим сдвигом вектора e_1,6. Найдем величину сдвига x^17/x^2 =x^15 σ^15 (e_1,6 )=e_16,21 Т.е. ошибка содержится на 16 и 21 позициях. x ̅=(011 010 110 100 000 000 000 000 000 000 1) Задание 6. В (31, 16)-БЧХ-коде C_7 с проверочной матрицей H=(a^i,a^3i,a^5i )^T, где a корень примитивного полинома p (x ), принято сообщение x с синдромом S Найти вектор ошибок в принятом сообщении сведением задачи к кубическому уравнению и решением этого уравнения методом Чэня. p(x)=x^5+x^2+1 S=(a^16,a^8,a^27) Решение Составим систему: {█(x+y+z=a^16@x^3+y^3+z^3=a^8@x^5+y^5+z^5=a^27 )┤ Перейдем к элементарным симметрическим полиномам: σ_1=x+y+z σ_2=xy+xz+yz σ_3=xyz Составим новую систему: {█(σ_1=a^16@aσ_1+a^16 σ_2+σ_3=a^8@a^2 σ_1+a^8 σ_2+aσ_3=a^27 )┤ => {█(a^17+a^16 σ_2+σ_3=a^8@a^18+a^8 σ_2+aσ_3=a^27 )┤ => {█(a^16 σ_2+σ_3=a^8+a^17=a^24@a^8 σ_2+aσ_3=a^27+a^18=a^3 )┤ => {█(σ_3=a^16 σ_2+a^24@a^8 σ_2+a(a^16 σ_2+a^24 )=a^3 )┤ => a^8 σ_2+a^17 σ_2+a^25=a^3 => a^24 σ_2=a^10 =>σ_2=a^17 =>σ_3=a^16 σ_2+a^24=a^2+a^24=a^9 Полученные значения σ_i служат, согласно теореме Виета, коэффициентами кубического уравнения t^3+σ_1 t^2+σ_2 t+σ_3=0, корнями которого и являются искомые неизвестные x,y,z.
t^3+a^16*t^2+a^17*t+a^9=0 t_1=x^6,t_2=x^14,t_3=x^20 То есть ошибки расположены на 7-м, 15-м и 21-м местах. Задание 7. Задачу из задания 6 решить норменным методом. Решение S=(a^16,a^8,a^27) s_1^*=0 s_2^*=s_2+s_1^3=a^8+a^(3*16)=a^8+a^17=a^24 s_3^*=s_3+s_1^5=a^27+a^18=a^3 S(e^* )=(0,a^24,a^3) N=(∞,∞,a^(3*3)/a^(24*5) )=(∞,∞,a^13 ) Определим вектора-ошибки, у которых первый синдром =0 : # вектор S1 S2 S3 N 1 (1,2,19) 0 x^19 x^30 (∞,∞,a^26) 2 (1,3,6) 0 x^7 x^29 (∞,∞,a^21) 3 (1,5,11) 0 x^14 x^27 (∞,∞,a^11) 4 (1,8,23) 0 x^29 x (∞,∞,a^13) 5 … … … … … Нормы N=(∞,∞,a^13 ) среди норм векторов тройной ошибки принадлежит вектору e_1,8,23. Вычислим сдвиг x^29*x^3λ=x^24 => λ=19 σ^19 (e_1,8,23 )=e_20,27,11 x=x^19+x^16=x^14 y=x^26+x^16=x^20 z=x^10+x^16=x^6 Это означает, что в сообщении ошибки на 15-м,21-м и 7-м местах.
