AA3-2(ECC) (1127140), страница 2
Текст из файла (страница 2)
Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга14 / 132Блоковое кодирование: общая схема и сложностьuкодированиеизбыточностьw vошибкаw+ewдекод.-1декод.-2w vb удаление избыт.w ubближ. код. словоПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга14 / 132Блоковое кодирование: общая схема и сложностьuкодированиеизбыточностьw vошибкаw+ewдекод.-1декод.-2w vb удаление избыт.w ubближ.
код. словоИз приведённых оценок следует: использование произвольного(n, k)-блокового кода возможно лишь при небольших значенияхn и k.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга14 / 132Блоковое кодирование: общая схема и сложностьuкодированиеизбыточностьw vошибкаw+ewдекод.-1декод.-2w vb удаление избыт.w ubближ. код. словоИз приведённых оценок следует: использование произвольного(n, k)-блокового кода возможно лишь при небольших значенияхn и k.Однако, приняв ряд дополнительных ограничений намножество кодовых слов, можно перейти от экспоненциальных(2k ) требований по памяти для хранения кода и по сложностиалгоритмов кодирования/декодирования к линейным по n и k.Эти ограничения приводят к использованию блоковых кодовспециального вида: групповых, а из групповых — циклических.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование.
Коды Хэмминга15 / 132Плотная упаковка шаров в булев кубЧтобы построить код максимального размера, исправляющийr ошибок, нужно вложить в единичный куб B n максимальновозможное число непересекающихся шаров радиуса r — задачаплотной упаковки.Вопрос: При каких n и r в куб B n можно уложитьнепересекающиеся шары радиуса r «безостатка»?ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга15 / 132Плотная упаковка шаров в булев кубЧтобы построить код максимального размера, исправляющийr ошибок, нужно вложить в единичный куб B n максимальновозможное число непересекающихся шаров радиуса r — задачаплотной упаковки.Вопрос: При каких n и r в куб B n можно уложитьнепересекающиеся шары радиуса r «безостатка»?Ответ: Такое удаётся в случаях:1n = 2m − 1, r = 1 — коды Хэмминга;n = 23, r = 3 — код Голея.— это совершенные или экстремальные коды.2ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаКоличество кодовых словТеорема (Хэмминга)При 2r < n максимальное число t кодовых слов находится впределах2n2n 6 t 6 .nnnnnn++ ... +++ ... +012r01r16 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга16 / 132Количество кодовых словТеорема (Хэмминга)При 2r < n максимальное число t кодовых слов находится впределах2n2n 6 t 6 .nnnnnn++ ... +++ ... +012r01rДоказательствоt есть максимальное число непересекающихся шаров радиусаr, помещающихся в кубе B n .Верхняя оценка — шар радиуса r содержит точки: самцентр + все точки с одной, двумя, ..., r измененнымикоординатами, т.е.
всего n0 + n1 + n2 + nr штук и шары непересекаются.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаПродолжение доказательстваДля оценки снизу построим код:123берем произвольную точку B n и строим вокруг неё шаррадиуса 2r;берем произвольную точку вне построенного шара истроим вокруг неё шар радиуса 2r;и т.д., каждая новая точка выбирается вне построенныхшаров.
В результате:шары,возможно,пересекаются,но каждый шар занимаетnnn++...+точек⇒шаровне менее012r2n ;nnn++ ... +012rшары радиуса r с центрами в выбранных точках непересекаются.17 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаРис. 1. К теореме Хэмминга18 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга19 / 132Код Хэмминга n = 2m − 1, r = 1: построениеn2Покажем, что в случае n = 2m − 1 получим t = 1+n, т.е. верхняяоценка в теореме Хэмминга достигается.Построим код, а потом определим его кодовое расстояние.Рассмотрим таблицу:k = 2m −(m+1)100 . . .
000010 . . . 000001 . . . 000...000 . . . 100000 . . . 010000 . . . 0011100 . . . 0001010 . . . 0001001 . . . 000...1111 . . . 1011111 . . . 1101111 . . . 111||{z}k = 2m −(m+1){zm}Слева — единичная матрица порядка 2m − (m + 1), справа — всебинарные наборы длины m, содержащие не менее двух единиц.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование.
Коды Хэмминга20 / 132Код Хэмминга n = 2m − 1, r = 1: кодовое расстояниеПросуммируем всевозможные совокупности строк этойmтаблицы, получив всего 2k = 22 −(m+1) различныхнаборов–кодовых слов. Но22m −(m+1)m=22 −12m=2nn+1= max t.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга20 / 132Код Хэмминга n = 2m − 1, r = 1: кодовое расстояниеПросуммируем всевозможные совокупности строк этойmтаблицы, получив всего 2k = 22 −(m+1) различныхнаборов–кодовых слов.
Но22m −(m+1)m=22 −12m=2nn+1= max t.Найдём кодовое расстояние построенного кода: если сложитьдве строки — в левой части будет две единицы, а вправой — хотя бы одна,не менее трёх строк — в левой части будет не менее трехединиц,т.е. всегда ρ αe, βe > 3 ⇒ шары единичного радиуса сцентрами в полученных наборах не пересекаются.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование.
Коды Хэмминга21 / 132Код Хэмминга длины 7ПримерВыбирем m = 3, тогда n = 23 − 1 = 7, k = 7 − 3 = 4 исоставим таблицу кода Хэмминга:1000010000100001110110110111Складывая по mod 2 все совокупности данных 4-х строк(включая пустую), получаем 24 = 16 = 27 /(1 + 7) различныхбинарных наборов, которыми можно закодировать 16сообщений: например,10 цифр разделитель = + − × ÷ .ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование.
Коды Хэмминга21 / 132Код Хэмминга длины 7ПримерВыбирем m = 3, тогда n = 23 − 1 = 7, k = 7 − 3 = 4 исоставим таблицу кода Хэмминга:1000010000100001110110110111Складывая по mod 2 все совокупности данных 4-х строк(включая пустую), получаем 24 = 16 = 27 /(1 + 7) различныхбинарных наборов, которыми можно закодировать 16сообщений: например,10 цифр разделитель = + − × ÷ .Является ли кодом Хемминга тривиальный (3, 1)-код?ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга22 / 132Код Голея — (23, 12, 7)-кодВ данном случае верхняя граница числа вложенных шароврадиуса 3 в 23-мерный единичный кубt =2231 + 23 +23·221·2+23·22·211·2·3=223223= 11 = 212 = 409620482также достигается — имеем плотную упаковку, как и в кодахХэмминга.Других пар (n, r), удовлетворяющих условию2n nnn++ ...
+01r— целоенеизвестно (а если таковые и есть, то у них n 1 и такой кодне представляет практического интереса).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаМ. ГолейМарсель Голей(Marcel J. E. Golay, 1902–1989)— швейцарский математик и физик,работавший в США и занимавшийсяпроблемами газовой хроматографиии оптической спектроскопии.В своей единственной работе 1949 г.по теории информации предложилсовершенный двоичный код, исправляющий три ошибки.В ходе космической программыВояджер (1979-81) для передачицветных изображений Юпитера и Сатурнаиспользовался код Голея.23 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга24 / 132Граница ПлоткинаПусть t(n, d) — максимально возможное количество кодовыхслов среди всех двоичных кодов длины n с кодовымрасстоянием d.Граница Плоткина даёт верхний предел t(n, d).ТеоремаЕсли d —12чётно и 2d > n, тоdt(n, d) 6 2;2d − nнечётно и 2d + 1 > n, тоd+1t(n, d) 6 2.2d + 1 − nСуществуют коды, для которых граница Плоткина достигается.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыРазделы I12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать25 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойстваРазделы12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать26 / 132ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
