Лекции по прикладной алгебре. v2.0 (1127112), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Для систематического кодирования с помощьюэквивалентных преобразований столбцов выделим в матрице Gединичную подматрицу размера 3×3 (над стрелками указанопроводимое преобразование над столбцами):011110000111101101←1+2 −1−−−→010011000111110e = G.101В последней матрице в строках (3, 5, 1) стоит единичнаяподматрица.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыБлоковый линейный код: пример кодирования...Теперь систематическое кодирование u1 , u2 , при котором биты1, 2, 3 исходного сообщения переходят в биты 3, 5, 1 кодовогослова соответственно, вычисляется следующим образом:1 10 0 11 01 0 1 010 11 0 0s se[ v 1 v 2 ] = G × [ u1 u2 ] =  × 1 0 = 0 1 .0111 11 00 1 00 01 1 12. С учетом выделенной единичной подматрицы впорождающей матрице G, находим проверочную матрицу H.Для этого формируем матрицу P3×3 из строк G, отличных отстрок с единичной подматрицей.193 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды194 / 432Блоковый линейный код: пример кодирования...P3×31 0 1= 0 1 1.1 1 1Далее нужно разместить столбцы P , соответственно, в 3-ом,5-ом и 1-ом cтолбце H, а во 2-й, 4-ый и 6-ой столбец Hпоставить единичную подматрицу:1 1 1 0 0 0H3×6 = 1 0 0 1 1 0 .1 0 1 0 1 1Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды195 / 432Блоковый линейный код: пример кодирования...Проверим, что в результате как систематического кодирования2 (а), так и несистематического 2 (б) были действительнонайдены кодовые слова:1 11 1 1 0 0 00s sH × [ v1 v2 v1 v2 ] = 1 0 0 1 1 0 × 01 0 1 0 1 1100= 00101011110010101 =1000 0 00 0 0 .0 0 0Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды196 / 432Блоковый линейный код: пример кодирования...3.

Найдем кодовое расстояние d, для чего построим матрицу всех23 = 8 кодовых слов и найдем минимальный ненулевой хэмминговвес — d = 3:[ v 1 . . . v 8 ] = G × [ u1 . . . u8 ] =0 0 11 0 1 0 0 0 0 1 1 1 11 0 0 = 0 1 1 × 0 0 1 1 0 0 1 1 =0 1 0 1 0 1 0 10 1 01 1 1u1 , .

. . , u8 — все 8возможных сообщений000= 000110101000111110010011110101011011001101.100Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование блокового кода: синдромПод декодированием блокового (n, k)-кода будем пониматьразбиение множества из всех 2n сообщений, которые возможнопринять, на 2k подмножеств, каждое из которых соответствуеткодовому слову.ОпределениеСиндромом принятого сообщения w блокового (n, k)-коданазывается вектор s = Hw ∈ {0, 1}m , где H — проверочнаяматрица, m = n − k.Свойства синдрома:s = Hw = H(v + e) = Hv + He = He, s ∈ {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}=sOгдеbe — произвольное частное решение системы Hbe = s;u — произвольный вектор длины k;O — матрица нулей размера m × k.Ясно, что Gu ∈ {0, 1}n — произвольное решение однороднойсистемы Hx = 0.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды199 / 432Общая схема декодированияПосле нахождения частного решения be, всевозможные 2kkвариантов вектора u дадут 2 вариантов вектора e = be + Gu.Решение с наименьшим хэмминговым весом дает искомыйвектор ошибок.После получения вектора ошибок e декодированиеb = w + e.осуществляется по правилу vСхема декодирования:wws = Hwwe=be + Guwkek→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: 1 0  1 1 1 0 0 010 = 0 .s = Hw = 1 0 0 1 1 0 × 0 1 0 1 0 1 1010Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды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:0 1 0 1 0 1 00 1 0 1 1 0 10 0 0 0 1 1 1G × [ u1 . .

. u8 ] = 0 1 1 0 1 0 00 0 1 1 1 1 00 1 1 0 0 1 1найдено101.100Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды202 / 432Декодирование линейного кода: пример...Таким образом, все 8 решений системы He = s записываютсякак сумма вектора eb = [0 1 0 0 0 0]T со всеми столбцамиматрицы G × [ u1 . . . u8 ]:010000100101010111100010001110111011001001111.100Выбирая среди них решение с наименьшим весом, получим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Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: определениеОпределениеКод C называется циклическим, если он инвариантенотносительно циклических сдвигов, т.е. для любого0 6 s 6 n − 1 справедливо(α0 , .

. . , αn−1 ) ∈ C ⇒ (αs , αs+1 , . . . , αn−1 , α0 , . . . , αs−1 ) ∈ C.206 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: определениеОпределениеКод C называется циклическим, если он инвариантенотносительно циклических сдвигов, т.е. для любого0 6 s 6 n − 1 справедливо(α0 , . . . , αn−1 ) ∈ C ⇒ (αs , αs+1 , . . .

, αn−1 , α0 , . . . , αs−1 ) ∈ C.Ранее рассматривалось и было показано:В кольце Fp [x]/(xn − 1), рассматриваемом как линейноевекторноепространствоno над полем Fp , имеется базис1, x, . . . , xn−1 .Циклический сдвиг координат в этом базисе равносиленумножению на x.206 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: определениеОпределениеКод C называется циклическим, если он инвариантенотносительно циклических сдвигов, т.е. для любого0 6 s 6 n − 1 справедливо(α0 , .

. . , αn−1 ) ∈ C ⇒ (αs , αs+1 , . . . , αn−1 , α0 , . . . , αs−1 ) ∈ C.Ранее рассматривалось и было показано:В кольце Fp [x]/(xn − 1), рассматриваемом как линейноевекторноепространствоno над полем Fp , имеется базис1, x, . . . , xn−1 .Циклический сдвиг координат в этом базисе равносиленумножению на x.Теорема: Линейное подпространство I ⊆ Fp [x]/(xn − 1)является циклическим iff I Fp [x]/(xn − 1).206 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды207 / 432Циклические коды: идея построенияПоэтому построить циклический код (работаем втак:12F2 ) можновыбираем некоторый делитель g(x) многочлена xn + 1;в кольце F2 [x]/(xn + 1) образуем идеал (g(x)).g(x) — порождающий (образующий) многочлен.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды207 / 432Циклические коды: идея построенияПоэтому построить циклический код (работаем втак:12F2 ) можновыбираем некоторый делитель g(x) многочлена xn + 1;в кольце F2 [x]/(xn + 1) образуем идеал (g(x)).g(x) — порождающий (образующий) многочлен.Оказывается:при удачном выборе g(x) коэффициенты многочленов,принадлежащих этому идеалу, будут давать хороший код;есть только несколько конструкций циклических кодовс хорошими параметрами;вопрос о кодовом расстоянии произвольного циклическогокода чрезвычайно труден.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды208 / 432Линейные циклические кодыИз всех линейных блоковых (n, k)-кодов будем далеерассматривать те, которые являются также и циклическими.Установим соответствие вектора v координатного пространства{0, 1}n и полинома v(x) ∈ F2 [x]:v = [ v0 , v1 , .

. . , vn−1 ]T ↔ v(x) = v0 + v1 x + . . . + vn−1 xn−1 .Тогда свойство главного идеала переформулируется:для каждого (n, k)-циклического блокового кода найдетсяпорождающий полином g(x) такой, что12для любого кодового слова v(x) справедливопредставление v(x) = g(x)q(x), где q(x) — некоторыйполином, deg q(x) = k;deg g(x) = m = n − k и 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) ∈ C степени n − 1.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды209 / 432Циклические коды: кодированиеПусть задан порождающий полином g(x) степени m = n − k —это число проверочных битов у будущего кода C.Рассмотримвозможныеметодыпостроениялинейныхциклических (n, k)-кодов, кодирующих сообщения–полиномu(x) степени k:u(x) 7→ v(x)Результат — кодовое слово–полином v(x) ∈ C степени n − 1.Несистематическое кодирование:u(x) 7→ v(x) = g(x)u(x)В порождающей матрице Gn×k = [ g 0 .

Характеристики

Список файлов лекций