Лекции по прикладной алгебре. v2.0 (1127112), страница 13
Текст из файла (страница 13)
Коды ХэммингаНекоторые понятия, связанные с булевым кубомРешаем вспомогательную задачу — она проще.Вспоминаем дискретную матматику Норма γe = число единичных координат в γe ∈ Bn.Метрика (вспоминаем, что это такое) на множествебинарных наборов — хеммингово расстояние (⊕ — суммапо mod 2):e = ρ(eα, β)e ⊕ βe .αШар Хэмминга с центром в αe и радиусом r —n odefe 6r .Sr (eα) = βe ρ(eα, β)162 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды Хэмминга163 / 432Блоковое кодирование: определение и тривиальный случайКодирование—взаимно-однозначноепреобразованиеисходного сообщения длины k в кодовое слово длиныn > k.Пример (n = 3, r = 1)Информация разбивается на блоки длины k = 1, т.е.передаются два сообщения: S0 = 0 и S1 = 1.Кодирование0 ↔ 0001 ↔ 111исправляет одну ошибку!Однако, такое кодирование крайне неэффективно: длинасообщения утраивается.Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаКодовое расстояниеОпределениеМинимальное расстояние между словами кода называетсякодовым расстоянием.УтверждениеМножество C образует код с исправлением не менее r ошибок,e = ∅ для всех αeесли Sr (eα) ∩ Sr (β)e, βe ∈ C таких, что αe 6= β.164 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаКодовое расстояниеОпределениеМинимальное расстояние между словами кода называетсякодовым расстоянием.УтверждениеМножество C образует код с исправлением не менее r ошибок,e = ∅ для всех αeесли Sr (eα) ∩ Sr (β)e, βe ∈ C таких, что αe 6= β.ДоказательствоЕсли при передаче сообщения αe сделано не более r ошибок, тонабор останется в шаре Sr (eα).Если шары не пересекаются, то искомое кодовое слово α —ближайшее к полученному набору.164 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаПлотная упаковка шаров в булев кубСледствиеУ кода, исправляющего r ошибок, кодовое расстояние не менее2r + 1.Чтобы построить код максимального размера, исправляющий rошибок, нужно вложить в единичный куб B n максимальновозможное число непересекающихся шаров радиуса r — задачаплотной упаковки.165 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаПлотная упаковка шаров в булев кубСледствиеУ кода, исправляющего r ошибок, кодовое расстояние не менее2r + 1.Чтобы построить код максимального размера, исправляющий rошибок, нужно вложить в единичный куб B n максимальновозможное число непересекающихся шаров радиуса r — задачаплотной упаковки.Вопрос: При каких n и r в куб B n можно уложитьнепересекающиеся шары радиуса r «без остатка»?165 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаПлотная упаковка шаров в булев кубСледствиеУ кода, исправляющего r ошибок, кодовое расстояние не менее2r + 1.Чтобы построить код максимального размера, исправляющий rошибок, нужно вложить в единичный куб B n максимальновозможное число непересекающихся шаров радиуса r — задачаплотной упаковки.Вопрос: При каких n и r в куб B n можно уложитьнепересекающиеся шары радиуса r «без остатка»?Ответ: Такое удаётся в случаях:1 n = 2q − 1, r = 1 — коды Хэмминга;2 n = 23, r = 3.165 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаКоличество кодовых словТеорема (Хэмминга)При 2r < n максимальное число t кодовых слов находится впределах2n2n 6 t 6 .nnnnnn++ ...
+++ ... +012r01r166 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаКоличество кодовых словТеорема (Хэмминга)При 2r < n максимальное число t кодовых слов находится впределах2n2n 6 t 6 .nnnnnn++ ... +++ ... +012r01rДоказательствоt есть максимальное число непересекающихся шаров радиуса r,помещающихся в кубе B n .Верхняя оценка — шар радиуса r содержит точки: самцентр + все точки с одной, двумя, ..., rизмененнымикоординатами, т.е.
всего n0 + n1 + n2 + nr штук и шары непересекаются.166 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаПродолжение доказательстваДля оценки снизу построим негрупповой код:123берем произвольную точку B n и строим вокруг неё шаррадиуса 2r;берем произвольную точку вне построенного шара истроим вокруг неё шар радиуса 2r;и т.д., каждая новая точка выбирается вне построенныхшаров.
В результате:шары,возможно,пересекаются,но каждый шар занимаетnnn++...+точек⇒шаровне менее012r2n ;nnn++ ... +012rшары радиуса r с центрами в выбранных точках непересекаются.167 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаРис. 1. К теореме Хэмминга168 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды Хэмминга169 / 432Код Хэмминга n = 2q − 1, r = 1: построениеn2Покажем, что в данном случае t = 1+n, т.е. верхняя оценка втеореме Хэмминга достигается.Построим код, а потом определим его кодовое расстояние.Рассмотрим таблицу:2q −(q+1)100.
. . 000010. . . 000001. . . 000...000. . . 100000. . . 010000. . . 0011100. . . 0001010. . . 0001001. . . 000...1111. . . 1011111. . . 1101111. . . 111||{z2q −(q+1)}{zq}Слева — единичная матрица порядка 2q − (q + 1), справа — всебинарные наборы длины q, содержащие не менее двух единиц.Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаКод Хэмминга n = 2q − 1, r = 1: кодовое расстояниеПросуммируем всевозможные совокупности строк этойqтаблицы, получив всего 22 −(q+1) различных наборов–кодовыхслов. Ноq22 −12n2q −(q+1)= max t.2==2qn+1170 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаКод Хэмминга n = 2q − 1, r = 1: кодовое расстояниеПросуммируем всевозможные совокупности строк этойqтаблицы, получив всего 22 −(q+1) различных наборов–кодовыхслов.
Ноq22 −12n2q −(q+1)= max t.2==2qn+1Найдём кодовое расстояние.Если суммируемдве строки — в левой части будет две единицы, а вправой — хотя бы одна,не менее трёх строк — в левой части будет не менее трехединиц,т.е. всегда ρ αe, βe > 3 ⇒ шары радиуса 1 с центрами вполученных наборах не пересекаются.170 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды Хэмминга171 / 432Код Хэмминга длины n = 23 − 1 = 7ПримерСоставим таблицу для кода, исправляющего одну ошибку (кодаХэмминга) длины 7 (q = 3):1000010000100001110110110111Складывая по mod 2 произвольные совокупности строк,получаем 16 различных бинарных наборов, которыми можнозакодировать 16 сообщений: например,10 цифр разделитель = + − × ÷ .Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаСлучай n = 23, r = 3В этом случае верхняя граница числа вложенных шароврадиуса 3 в 23-мерный единичный кубt =2231 + 23 +23·222+23·22·216=223223= 11 = 212 = 409620482достигается — имеем плотную упаковку, как и в ранеерассмотренных случаях.172 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаСлучай 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 и такой кодне представляет практического интереса).172 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды173 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств174 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать175 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыГрупповые коды: определениеБо́льшая часть теории кодирования построена на т.н.
линейныхили групповых кодах — кодах, образующих группуотносительно операции ⊕.Утверждение 1Устойчивая совокупность кодовых слов C = αe , ..., αetобразует группу по сложению относительно операции ⊕.176 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыГрупповые коды: определениеБо́льшая часть теории кодирования построена на т.н. линейныхили групповых кодах — кодах, образующих группуотносительно операции ⊕.Утверждение 1Устойчивая совокупность кодовых слов C = αe , ..., αetобразует группу по сложению относительно операции ⊕.ДоказательствоУстойчивость: для любых кодовых слов αei , αej ∈ Cijkвыполняется αe ⊕αe =αe ∈ C, 1 6 k 6 t —предполагается;Ассоциативность: свойство операции ⊕ ;defСуществование 0: αe⊕αe = ( 0, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
