PA_full (1127144), страница 15
Текст из файла (страница 15)
, u8 � все 8возможных сообщений2060660= 660640011010100011111001001111010101101100131077177.177050Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование блокового кода: синдромПод декодированием блокового (n, k)-кода будем пониматьразбиение множества из всех 2n сообщений, которые возможнопринять, на 2k подмножеств, каждое из которых соответствуеткодовому слову.ОпределениеСиндромом принятого сообщения w блокового (n, k)-коданазывается вектор s = Hw 2 {0, 1}m , где H � проверочнаяматрица, m = n k.Свойства синдрома:s = Hw = H(v + e) = Hv + He = He, s 2 {0, 1}m ;s = 0 , w � кодовое слово;вектор ошибок e удовлетворяет системе линейныхуравнений Hm⇥n e = s.197 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды198 / 432Вычисление вектора ошибок по синдромуРешение относительно вектора ошибок e СЛАУHe = s(⇤)будем искать в виде e = be + Gu: подставляя его в (⇤), получимHbe + |{z}HG u = s,|{z}=sгдеObe � произвольное частное решение системы Hbe = s;u � произвольный вектор длины k;O � матрица нулей размера m ⇥ k.Ясно, что Gu 2 {0, 1}n � произвольное решение однороднойсистемы Hx = 0.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды199 / 432Общая схема декодированияПосле нахождения частного решения be, всевозможные 2kkвариантов вектора u дадут 2 вариантов вектора e = be + Gu.Решение с наименьшим хэмминговым весом дает искомыйвектор ошибок.После получения вектора ошибок e декодированиеb = w + e.осуществляется по правилу vСхема декодирования:ws = Hwe=be + Gukek!minb =w+evВ общем случае: для каждого из 2m синдромов необходимоперебирать 2k решений очередной СЛАУ и процедурадекодирования произвольного линейного кода требуетэкспоненциальных затрат как по памяти, так и по сложностиалгоритма декодирования.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды200 / 432Декодирование линейного кода: примерВозьмём линейный код из рассмотренного ранее примера.Пусть исходный вектор u = [0 1 1]T .Систематическое кодирование для него было получено раньше:v = [1 1 0 0 1 0]T .Пусть при передаче происходит ошибка во втором бите, т.е.принятый вектор w = [1 0 0 0 1 0]T .Декодирование1.
Найдём синдром принятого сообщения w:2 3123 6 072 36 71 1 1 0 0 016 077 = 405 .s = Hw = 41 0 0 1 1 05 ⇥ 66 076 71 0 1 0 1 104 150Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды201 / 432Декодирование линейного кода: пример...2. Находим все решения системы He = s = [1 0 0]T .2.а Находим частное решение eb этой системы. Поскольку встолбцах 2, 4, 6 проверочной матрицы H стоит единичнаяподматрица, возьмём координаты 1, 3 и 5 вектора eb нулевыми:eb1 = eb3 = eb5 = 0 и тогда eb2 = s1 = 1, eb4 = s2 = 0, eb6 = s3 = 0,т.е. eb = [0 1 0 0 0 0]T .2.а Все решения однородной системы уже былораньше при вычислении кодового расстояния d:20 1 0 1 0 1 060 1 0 1 1 0 1660 0 0 0 1 1 1G ⇥ [ u1 .
. . u8 ] = 660 1 1 0 1 0 0640 0 1 1 1 1 00 1 1 0 0 1 1найдено31077177.177050Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды202 / 432Декодирование линейного кода: пример...Таким образом, все 8 решений системы He = s записываютсякак сумма вектора eb = [0 1 0 0 0 0]T со всеми столбцамиматрицы G ⇥ [ u1 .
. . u8 ]:2061660660640010010101011110001000111011101100100131177177.177050Выбирая среди них решение с наименьшим весом, получимe = [0 1 0 0 0 0]T .b = w + e = [1 1 0 0 1 0]T и исходное сообщение vОтсюда vвосстановлено.Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды203 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств204 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать205 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды206 / 432Циклические коды: определениеОпределениеКод C называется циклическим, если он инвариантенотносительно циклических сдвигов, т.е.
для любого0 6 s 6 n 1 справедливо(↵0 , . . . , ↵n1)2 C ) (↵s , ↵s+1 , . . . , ↵n1,↵ 0 , . . . , ↵s1)2 C.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды206 / 432Циклические коды: определениеОпределениеКод C называется циклическим, если он инвариантенотносительно циклических сдвигов, т.е. для любого0 6 s 6 n 1 справедливо(↵0 , . . .
, ↵n1)2 C ) (↵s , ↵s+1 , . . . , ↵n1,↵ 0 , . . . , ↵s1)2 C.Ранее рассматривалось и было показано:В кольце p [x]/(xn 1), рассматриваемом как линейноевекторноепространствоno над полем p , имеется базис1, x, . . . , xn 1 .Циклический сдвиг координат в этом базисе равносиленумножению на x.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды206 / 432Циклические коды: определениеОпределениеКод C называется циклическим, если он инвариантенотносительно циклических сдвигов, т.е. для любого0 6 s 6 n 1 справедливо(↵0 , .
. . , ↵n1)2 C ) (↵s , ↵s+1 , . . . , ↵n1,↵ 0 , . . . , ↵s1)2 C.Ранее рассматривалось и было показано:В кольце p [x]/(xn 1), рассматриваемом как линейноевекторноепространствоno над полем p , имеется базис1, x, . . . , xn 1 .Циклический сдвиг координат в этом базисе равносиленумножению на x.Теорема: Линейное подпространство I ✓ p [x]/(xnnявляется циклическим iff I1).p [x]/(x1)Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды207 / 432Циклические коды: идея построенияПоэтому построить циклический код (работаем втак:122)можновыбираем некоторый делитель g(x) многочлена xn + 1;в кольце 2 [x]/(xn + 1) образуем идеал (g(x)).g(x) � порождающий (образующий) многочлен.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды207 / 432Циклические коды: идея построенияПоэтому построить циклический код (работаем втак:122)можновыбираем некоторый делитель g(x) многочлена xn + 1;в кольце 2 [x]/(xn + 1) образуем идеал (g(x)).g(x) � порождающий (образующий) многочлен.Оказывается:при удачном выборе g(x) коэффициенты многочленов,принадлежащих этому идеалу, будут давать хороший код;есть только несколько конструкций циклических кодовс хорошими параметрами;вопрос о кодовом расстоянии произвольного циклическогокода чрезвычайно труден.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды208 / 432Линейные циклические кодыИз всех линейных блоковых (n, k)-кодов будем далеерассматривать те, которые являются также и циклическими.Установим соответствие вектора v координатного пространства{0, 1}n и полинома v(x) 2 2 [x]:v = [ v 0 , v 1 , .
. . , vn1]T$ v(x) = v0 + v1 x + . . . + vn1xn 1.Тогда свойство главного идеала переформулируется:для каждого (n, k)-циклического блокового кода найдетсяпорождающий полином g(x) такой, что1для любого кодового слова v(x) справедливопредставление v(x) = g(x)q(x), где q(x) � некоторыйполином, deg q(x) = k;2deg g(x) = m = nk и g(x) xn + 1.Любой полином, являющийся делителем xn + 1, являетсяпорождающим для некоторого циклического кода длины n.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды209 / 432Циклические коды: кодированиеПусть задан порождающий полином g(x) степени m = n k �это число проверочных битов у будущего кода C.Рассмотримвозможныеметодыпостроениялинейныхциклических (n, k)-кодов, кодирующих сообщения–полиномu(x) степени k:u(x) 7! v(x)Результат � кодовое слово–полином v(x) 2 C степени n1.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды209 / 432Циклические коды: кодированиеПусть задан порождающий полином g(x) степени m = n k �это число проверочных битов у будущего кода C.Рассмотримвозможныеметодыпостроениялинейныхциклических (n, k)-кодов, кодирующих сообщения–полиномu(x) степени k:u(x) 7! v(x)Результат � кодовое слово–полином v(x) 2 C степени n1.Несистематическое кодирование:u(x) 7! v(x) = g(x)u(x)В порождающей матрице Gn⇥k = [ g 0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
