PA_full (1127144), страница 14

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

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

, ↵etобразует группу по сложению относительно операции .ДоказательствоУстойчивость: для любых кодовых слов ↵ei , ↵ej 2 Cijkвыполняется ↵e↵e =↵e 2 C, 1 6 k 6 t �предполагается;Ассоциативность: свойство операции ;defСуществование 0: ↵e ↵e = ( 0, . . . , 0 ) = e0;Противоположные элементы:↵e = ↵e � см. выше.176 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды177 / 432Свойство кодового расстояния линейного кодаТеоремаКодовое расстояние d линейного кода обладает свойством (e↵, e иe � кодовые слова)d = min ⇢(e↵, e) = min k e k .↵e6= ee6=e0Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды177 / 432Свойство кодового расстояния линейного кодаТеоремаКодовое расстояние d линейного кода обладает свойством (e↵, e иe � кодовые слова)Доказательствоd = min ⇢(e↵, e) = min k e k .↵e6= ee6=e0eДля произвольных кодовых слов↵e⇣⌘ и всегда существует ихeсумма � кодовое слово : ⇢ ↵e,= ↵e e = kek,причем e 6= e0 при ↵e 6= e.⇣⌘Отсюда получаем оценку min ⇢ ↵e, e > min k e k.↵e6= ee6=e0Эта оценка достигается, например, при e = e0.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыБлоковое кодирование: общий случайОбозначим одно сообщение длины k вектором-столбцом(жирный шрифт) u 2 {0, 1}k :23u1u = 4 ··· 5.ukОпределениеv � кодовое слово (длины n = k + m);Множество {v 1 , .

. . , v 2k } всех 2k кодовых слов(длины k) � (n, k)-блоковый код;v = k/n � скорость кода.178 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды179 / 432Код Хемминга � блоковый линейный кодКод Хэмминга � частный случай блокового группового кода �это ( 2q 1, 2q (q + 1) )-код.Характеристики кода Хэмминга:кодовое расстояние d = 3, т.е. он исправляет r = 1 ошибку;qскорость v = 2 2q 1 1 q = 1 2qq 1 ;qосуществляет плотную упаковку � куб B 2 1 разбиваетсяq2nна t = n+1= 22 (q+1) шаров радиуса 3 с центрами вкодовых словах.Плотную упаковку осуществляет ещё только ( 23, 12 )-код,исправляющий r = 3 ошибки.Никакие другие коды не обеспечивают плотной упаковки шаровв единичный куб.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыБлоковое кодирование: ошибки и их исправлениеПри передаче по каналу со шумом кодовое слово vпревращается в принятое слово w = v + e той же длины n.e 2 {0, 1}n � вектор ошибок: ei = 1, если в i-ом битепроизошла ошибка.После получения слова w алгоритм декодирования:на первом этапе пытается восстановить переданное словопутём нахождения ближайшего к w в метрикеb;Хэмминга кодового слова, результат � vb переводится в декодированное словона втором этапе слово vb путём удаленияисходного сообщения uвставленных битов избыточности.(n, k)-блоковый код способен исправлять [(d 1)/2] ошибок.Вычисление кодового расстояния d для (n, k)-блокового кода �сложная задача.180 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды181 / 432Блоковое кодирование: общая схемаuкодированиеизбыточностьvошибкаewдекод.-1ближ.код.словоbvдекод.-2удол.избыт.buПрикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды181 / 432Блоковое кодирование: общая схемаuкодированиеизбыточностьvошибкаewдекод.-1ближ.код.словоbvдекод.-2удол.избыт.buПрименяя (n, k)-блоковый код, вообще говоря, необходимо:на этапе кодирования � использовать таблицу всех кодовыхслов размера 2k ⇥n,на этапе декодирования � перебирать все 2k кодовых словдля поиска ближайшего к принятому.В результате: использование произвольного (n, k)-блоковогокода возможно лишь при небольших значениях n и k.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды181 / 432Блоковое кодирование: общая схемаuкодированиеизбыточностьvошибкаewдекод.-1ближ.код.словоbvдекод.-2удол.избыт.buПрименяя (n, k)-блоковый код, вообще говоря, необходимо:на этапе кодирования � использовать таблицу всех кодовыхслов размера 2k ⇥n,на этапе декодирования � перебирать все 2k кодовых словдля поиска ближайшего к принятому.В результате: использование произвольного (n, k)-блоковогокода возможно лишь при небольших значениях n и k.Однако, приняв ряд дополнительных ограничений намножество кодовых слов, можно перейти от экспоненциальныхтребований по памяти для хранения кода и по сложностиалгоритмов кодирования/декодирования к линейным по n и k.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыЛинейные блоковые коды{0, 1}n � n-мерное координатное (линейное) пространство надконечным полем {0, 1}.ОпределениеБлоковый (n, k)-код C называется линейным, если он образуетлинейное подпространство размерности k координатногопространства {0, 1}n .182 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды182 / 432Линейные блоковые коды{0, 1}n � n-мерное координатное (линейное) пространство надконечным полем {0, 1}.ОпределениеБлоковый (n, k)-код C называется линейным, если он образуетлинейное подпространство размерности k координатногопространства {0, 1}n .Это означает, что в линейном коде C �123сумма любых кодовых слов � кодовое слово;кодовое расстояние d = min kek;e2Cсуществует базис из k векторов { g 0 , g 1 , .

. . , g kвектор v 2 C может быть представлен какk 1Xv =ui g i , ui 2 {0, 1}.i=01}и любойПрикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды183 / 432Элемент линейного кода: матричное представлениеv =k 1Xi=0ui g i = Gu , где G = [ g 0 g 1 . . . g k1]2 {0, 1}n⇥k �� порождающая матрица кодаПрикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды183 / 432Элемент линейного кода: матричное представлениеv =k 1Xi=0ui g i = Gu , где G = [ g 0 g 1 . . . g k1]2 {0, 1}n⇥k �� порождающая матрица кодаПример (код Хэмминга длины n = 7 с k = 4)Ранее была получена таблица, сложением произвольных строккоторой получаются все 24 = 16 кодовых слов. Порождающаяматрица получается транспонированием этой таблицы:231 0 0 060 1 0 076760 0 1 07677G7⇥4 = 660 0 0 1761 1 0 176741 0 1 150 1 1 1Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыЛинейные блоковые коды: кодированиеДля линейного кода с порождающей матрицей Gсообщению u соответствует кодовое слово v = Gu.На практике удобно использоватьсистематическое кодирование, при котором k бит исходногосообщения копируются в фиксированные k бит кодового слова,а затем вычисляются остальные m = n k проверочных бит.Возможность систематического кодирования основана на том,что матрица G определена с точностью до эквивалентныхпреобразований столбцов (переход к другому базису).При его использовании 2-й этап декодирования � удалениеb ! ub � становится тривиальным.избыточности v184 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыЛинейные блоковые коды: систематическое кодированиеПусть линейный код задан порождающей матрицей G.С помощью эквивалентных преобразований столбцовматрица G может быть приведена к виду, в котором (безпотери общности � первые) k строк образуют единичнуюподматрицу:Ike n⇥k =Gn⇥k ! G,Pm⇥kгде Ik � единичная матрица порядка k.e будет систематическим, приТогда кодирование v = Guкотором первые k бит кодового слова v являются битамиисходного сообщения u.185 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды186 / 432Ортогональное дополнение к подпространству кодаРазложение пространства {0, 1}n в прямую суммуподпространств:dim{0, 1}nn=Ck+C?m=nkC ? � ортогональное дополнение (подпространство) кподпространству кода C, т.е.8 v 2 C, w 2 C ?Tv⇥ w}| {zскалярное произведение(v T � транспонированный вектор v).= 0Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды187 / 432Линейные блоковые коды: проверочная матрицаОпределениеПусть { h0 , .

. . , hm2 {0, 1}n � базис C ? . Матрица2 T 3h06 hT 76 1 7Hm⇥n = 6 . 74 .. 5hTm 11}называется проверочной матрицей кода C.Ясно, что8 (v 2 C) Hv = 0;проверочная матрица определена с точностью доэквивалентных преобразований строк.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыПостроение систематической проверочной матрицыЕсли блоковый код задан исходной порождающей матрицей Gи построена матрицаIkeGn⇥k =,Pm⇥kто проверочная матрица H может быть построена как⇥⇤Hm⇥n = Pm⇥k Im ,(Ik и Im � единичные матрицы порядков k и m).e = (P + P )u = 0.Действительно, в этом случае Hv = H Gu188 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыЛинейный систематический блоковый код: заданиеТаким образом, линейный код для сообщений длины k имеетдлину n = k + m и задаётсялибо порождающей матрицей размера n⇥k,либо проверочной матрицей размера m⇥n.Эти матрицыопределены с точностью до эквивалентных преобразованийстолбцов и строк соответственно, что соответствуетвыбору различных базисов в пространствах C и C ? ,однако фиксирование позиций битов при систематическомкодировании задаёт порождающую и проверочнуюматрицу однозначно.Количество m дополнительных проверочных битов зависит отколичества ошибок, которые может исправить код (увеличениеm увеличивает кодовое расстояние d).189 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыБлоковый линейный код: пример кодированияДано: линейный блоковый (6,3)-код C задан порождающейматрицей230 0 16 1 0 17676 1 0 0767.G6⇥3 = 67111674 1 1 050 1 1Требуется:1с использование данного кода осуществить (а)несистематическое и (б) систематическое кодированиевекторов u1 = [0 1 1]T и u2 = [1 0 1]T ;2построить проверочную матрицу H кода;3определить кодовое расстояние d.190 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды191 / 432Блоковый линейный код: пример кодирования...1 (a).

Несистематическое кодирование находимнепосредственно:2061661[ v 1 v 2 ] = G ⇥ [ u1 u2 ] = 661641000011132311 16 1 0723177670 167077 ⇥ 4 1 05 = 6 0 17 .767176 0 071 15401 1510 1Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды192 / 432Блоковый линейный код: пример кодирования...1 (б). Для систематического кодирования с помощьюэквивалентных преобразований столбцов выделим в матрице Gединичную подматрицу размера 3⇥3 (над стрелками указанопроводимое преобразование над столбцами):206166166164100001113117707717705112061611+2 6!66064010001113117707e7 = G.177051В последней матрице в строках (3, 5, 1) стоит единичнаяподматрица.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыБлоковый линейный код: пример кодирования...Теперь систематическое кодирование u1 , u2 , при котором биты1, 2, 3 исходного сообщения переходят в биты 3, 5, 1 кодовогослова соответственно, вычисляется следующим образом:23230 0 11 16 1 0 17 26 1 0736767016 1 0 076 0 17s se676745[ v 1 v 2 ] = G ⇥ [ u1 u2 ] = 67 ⇥ 1 0 = 6 0 17 .01167671 14 0 1 054 1 051 1 10 02.

С учетом выделенной единичной подматрицы впорождающей матрице G, находим проверочную матрицу H.Для этого формируем матрицу P3⇥3 из строк G, отличных отстрок с единичной подматрицей.193 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды194 / 432Блоковый линейный код: пример кодирования...P3⇥3231 0 1= 4 0 1 15.1 1 1Далее нужно разместить столбцы P , соответственно, в 3-ом,5-ом и 1-ом cтолбце H, а во 2-й, 4-ый и 6-ой столбец Hпоставить единичную подматрицу:231 1 1 0 0 0H3⇥6 = 41 0 0 1 1 05 .1 0 1 0 1 1Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды195 / 432Блоковый линейный код: пример кодирования...Проверим, что в результате как систематического кодирования2 (а), так и несистематического 2 (б) были действительнонайдены кодовые слова:2123 6161 1 1 0 0 060s s45H ⇥ [ v1 v2 v1 v2 ] = 1 0 0 1 1 0 ⇥ 66061 0 1 0 1 1410204= 0010101111001031077177 =17705030 0 00 0 05 .0 0 0Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды196 / 432Блоковый линейный код: пример кодирования...3.

Найдем кодовое расстояние d, для чего построим матрицу всех23 = 8 кодовых слов и найдем минимальный ненулевой хэмминговвес � d = 3:[ v 1 . . . v 8 ] = G ⇥ [ u1 . . . u8 ] =230 0 161 0 17 23670 0 0 0 1 1 1 161 0 077 45= 660 1 17 ⇥ 0 0 1 1 0 0 1 1 =670 1 0 1 0 1 0 140 1 051 1 1u1 , . . .

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

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