Лекции по прикладной алгебре. v1.1 (1127111), страница 10
Текст из файла (страница 10)
. . , St , которые нужно передать поканалу связи.Сообщения передаются в виде двоичных кодовых слов.Ограничимся случаями, когда:12все сообщения кодируются словами одинаковой длины;ошибки при передаче могут только изменять значениянекоторых битов.Задача (основная):построитькодминимальнойдлины,позволяющий восстановить сообщение, содержащее не более rошибок.Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования126 / 160Две задачиЕсть набор сообщений S1 , .
. . , St , которые нужно передать поканалу связи.Сообщения передаются в виде двоичных кодовых слов.Ограничимся случаями, когда:12все сообщения кодируются словами одинаковой длины;ошибки при передаче могут только изменять значениянекоторых битов.Задача (основная):построитькодминимальнойдлины,позволяющий восстановить сообщение, содержащее не более rошибок.Задача (вспомогательная): даныn — длина кода (может зависеть от некоторого параметра m),r — максимально допустимое число ошибок;Требуется построить код, максимизирующий число t сообщений,которое можно передать.Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияРешаем вспомогательную задачу —— она проще.127 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияРешаем вспомогательную задачу —— она проще.Мы увидим, что точное решение вспомогательной задачи найденолишь для случаев n = 2m − 1, r = 1 и n = 23, r = 3.Для остальных пар (n, r) будет дано приближённое решение.127 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования127 / 160Решаем вспомогательную задачу —— она проще.Мы увидим, что точное решение вспомогательной задачи найденолишь для случаев n = 2m − 1, r = 1 и n = 23, r = 3.Для остальных пар (n, r) будет дано приближённое решение.Основные понятия:Норма keγ k = число единичных координат в γe ∈ Bn.Метрика (вспоминаем, что это такое) на множестве бинарныхнаборов — хеммингово расстояние (⊕ — сумма по mod 2):e = kee .ρ(eα, β)α ⊕ βkШар Хэмминга с центром в αe и радиусом r —defe 6 r}.Sr (eα) = { βe | ρ(eα, β)Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияГрупповые кодыБо́льшая часть теории кодирования построена на т.н.
линейныхили групповых кодах — кодах, образующих группуотносительно операции ⊕.УтверждениеУстойчивая совокупность кодовых слов C = { αe1 , . . . , αeq }образует группу по сложению относительно операции ⊕.128 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияГрупповые кодыБо́льшая часть теории кодирования построена на т.н. линейныхили групповых кодах — кодах, образующих группуотносительно операции ⊕.УтверждениеУстойчивая совокупность кодовых слов C = { αe1 , . . . , αeq }образует группу по сложению относительно операции ⊕.ДоказательствоУстойчивость: для любых кодовых слов αei , αej ∈ Cijtвыполняется αe ⊕αe =αe ∈ C, 1 6 t 6 q —предполагается;Ассоциативность: свойство операции ⊕ ;defСуществование 0: αe⊕αe = (0, . .
. , 0) = e0;Противоположные элементы: −eα = αe — см. выше.128 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования129 / 160Минимальное расстояние между кодовыми словамиТеоремаМинимальное расстояние между кодовыми словами обладаетсвойствомe = min k γmin ρ(eα, β)ek.αe6=βeγe6=e0Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования129 / 160Минимальное расстояние между кодовыми словамиТеоремаМинимальное расстояние между кодовыми словами обладаетсвойствомe = min k γmin ρ(eα, β)ek.αe6=βeγe6=e0Доказательствоe =k αeρ(eα, β)e ⊕ βe k = k γe k, причем γe 6= e0 при αe 6= β.Отсюда получаем оценкуe > min k γmin ρ(eα, β)ek.αe6=βeγe6=e0Эта оценка достигается, например, при βe = e0.Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияКодовое расстояниеОпределениеМинимальное расстояние между словами кода называется кодовымрасстоянием.УтверждениеМножество C образует код с исправлением не менее r ошибок, еслиe = ∅ для всех αeSr (eα) ∩ Sr (β)e, βe ∈ C таких, что αe 6= β.130 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияКодовое расстояниеОпределениеМинимальное расстояние между словами кода называется кодовымрасстоянием.УтверждениеМножество C образует код с исправлением не менее r ошибок, еслиe = ∅ для всех αeSr (eα) ∩ Sr (β)e, βe ∈ C таких, что αe 6= β.ДоказательствоЕсли при передаче сообщения αe сделано не более r ошибок, то наборостанется в шаре Sr (eα).Если шары не пересекаются, то искомое кодовое слово α —ближайшее к полученному набору.130 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияПлотная упаковка шаров в булев кубСледствиеУ кода, исправляющего r ошибок, кодовое расстояние не менее2r + 1.Чтобы построить код максимального размера, исправляющий rошибок, нужно вложить в единичный куб B n максимальновозможное число непересекающихся шаров радиуса r — задачаплотной упаковки.131 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияПлотная упаковка шаров в булев кубСледствиеУ кода, исправляющего r ошибок, кодовое расстояние не менее2r + 1.Чтобы построить код максимального размера, исправляющий rошибок, нужно вложить в единичный куб B n максимальновозможное число непересекающихся шаров радиуса r — задачаплотной упаковки.Вопрос: При каких n и r в куб B n можно уложитьнепересекающиеся шары радиуса r «без остатка»?131 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияПлотная упаковка шаров в булев кубСледствиеУ кода, исправляющего r ошибок, кодовое расстояние не менее2r + 1.Чтобы построить код максимального размера, исправляющий rошибок, нужно вложить в единичный куб B n максимальновозможное число непересекающихся шаров радиуса r — задачаплотной упаковки.Вопрос: При каких n и r в куб B n можно уложитьнепересекающиеся шары радиуса r «без остатка»?Ответ: Такое удаётся в случаях:1 n = 2m − 1, r = 1;2 n = 23, r = 3.131 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияКоличество кодовых словТеорема (Хэмминга)При 2r < n максимальное число t кодовых слов находится впределах2n2n 6 t 6 .nnnnnn++ ...
+++ ... +012r01r132 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияКоличество кодовых словТеорема (Хэмминга)При 2r < n максимальное число t кодовых слов находится впределах2n2n 6 t 6 .nnnnnn++ ... +++ ... +012r01rДоказательствоt есть максимальное число непересекающихся шаров радиуса r,помещающихся в кубе B n .Верхняя оценка — шар радиуса r содержит точки: сам центр +все точки с одной, двумя, ..., r измененными координатами,т.е. всего n0 + n1 + n2 + nr штук и шары не пересекаются.132 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияПродолжение доказательстваДля оценки снизу построим негрупповой код:123берем произвольную точку B n и строим вокруг неё шаррадиуса 2r;берем произвольную точку вне построенного шара истроим вокруг неё шар радиуса 2r;и т.д., каждая новая точка выбирается вне построенныхшаров.
В результате:шары,возможно,пересекаются,но каждый шар занимаетnnn++...+точек⇒шаровне менее012r2n ;nnn++ ... +012rшары радиуса r с центрами в выбранных точках непересекаются.133 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияРис. 1. К теореме Хэмминга134 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования135 / 160Случай n = 2m − 1, r = 1 — код Хэммингаn2Покажем, что в данном случае t = 1+n, т.е.
верхняя оценка втеореме Хэмминга достигается.Построим код, а потом определим его кодовое расстояние.Рассмотрим таблицу:2m −(m+1)100. . . 000010. . . 000001. . . 000...000. . . 100000. . . 010000.
. . 0011100. . . 0001010. . . 0001001. . . 000...1111. . . 1011111. . . 1101111. . . 111||{z}2m −(m+1){zm}Слева — единичная матрица порядка 2m − (m + 1), справа — всебинарные наборы длины m, содержащие не менее двух единиц.Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования136 / 160Случай n = 2m − 1, r = 1: код ХэммингаПросуммируем всевозможные совокупности строк этойmтаблицы, получив всего 22 −(m+1) наборов–кодовых слов. Ноm22m −(m+1)2n22 −1=.=2mn+1Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования136 / 160Случай n = 2m − 1, r = 1: код ХэммингаПросуммируем всевозможные совокупности строк этойmтаблицы, получив всего 22 −(m+1) наборов–кодовых слов.
Ноm22m −(m+1)2n22 −1=.=2mn+1Найдём кодовое расстояние.Если суммируемдве строки — в левой части будет две единицы, а вправой — хотя бы одна,не менее трёх строк — в левой части будет не менее трехединиц,e > 3 ⇒ шары радиуса 1 с центрами вт.е. всегда ρ(eα, β)полученных наборах не пересекаются.Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования137 / 160Хэмминга длины n = 23 − 1 = 7, r = 1ПримерСоставим таблицу для кода Хэмминга длины 7 (m = 3):1000010000100001110110110111Складывая по mod 2 произвольные совокупности строк,получаем 16 различных бинарных наборов, которыми можнозакодировать 16 сообщений: например,10 цифр | разделитель | = | + | − | × | ÷ .При передаче сообщений с помощью кода Хэммингаможно исправить одну ошибку.Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования138 / 160Случай n = 23, r = 3В этом случае верхняя граница числа вложенных шароврадиуса 3 в 23-мерный единичный кубt =2231 + 23 +23·222+23·22·216=223223= 11 = 212 = 409620482достигается — имеем плотную упаковку, как и в ранеерассмотренных случаях.Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования138 / 160Случай n = 23, r = 3В этом случае верхняя граница числа вложенных шароврадиуса 3 в 23-мерный единичный кубt =2231 + 23 +23·222+23·22·216=223223= 11 = 212 = 409620482достигается — имеем плотную упаковку, как и в ранеерассмотренных случаях.Других пар (n, r), удовлетворяющих условию2n — целоеnnn++ ...
+01rнеизвестно (а если таковые и есть, то у них n 1 и такой кодне представляет практического интереса).Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды139 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыРаздел IIКоды БЧХЧто надо знать140 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: определениеОпределениеКод C называется циклическим, если он инвариантенотносительно циклических сдвигов, т.е.
для любого0 6 s 6 n − 1 справедливо(α0 , . . . , αn−1 ) ∈ C ⇒ (αs , αs+1 , . . . , αn−1 , α0 , . . . , αs−1 ) ∈ C.141 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: определениеОпределениеКод C называется циклическим, если он инвариантенотносительно циклических сдвигов, т.е. для любого0 6 s 6 n − 1 справедливо(α0 , . . . , αn−1 ) ∈ C ⇒ (αs , αs+1 , . . . , αn−1 , α0 , . . . , αs−1 ) ∈ C.Ранее рассматривалось и было показано:В кольце Fp [x]/(xn − 1), рассматриваемом как линейноевекторное пространство над полем Fp имеется базис{ 1, x, . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
