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

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

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

. . , 0 ) = e0;Противоположные элементы: −eα = αe — см. выше.176 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды177 / 432Свойство кодового расстояния линейного кодаТеоремаКодовое расстояние d линейного кода обладает свойством (eα, βe иγe — кодовые слова)e = min k γd = min ρ(eα, β)ek.αe6=βeγe6=e0Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды177 / 432Свойство кодового расстояния линейного кодаТеоремаКодовое расстояние d линейного кода обладает свойством (eα, βe иγe — кодовые слова)e = min k γd = min ρ(eα, β)ek.αe6=βeγe6=e0ДоказательствоeДля произвольных кодовых словαe и βвсегдасуществует ихeсумма — кодовое слово γ: ρ αe, β = αe ⊕ βe = keγ k,eпричем γe 6= e0 при αe 6= β.Отсюда получаем оценку min ρ αe, βe > min k γe k.αe6=βeγe6=e0Эта оценка достигается, например, при βe = e0.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыБлоковое кодирование: общий случайОбозначим одно сообщение длины k вектором-столбцом(жирный шрифт) u ∈ {0, 1}k :u1u =  ··· .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= 1 − 2qq−1 ;скорость v = 2 2−1−qq −1qосуществляет плотную упаковку — куб B 2 −1 разбиваетсяq2nна t = n+1= 22 −(q+1) шаров радиуса 3 с центрами вкодовых словах.Плотную упаковку осуществляет ещё только ( 23, 12 )-код,исправляющий r = 3 ошибки.Никакие другие коды не обеспечивают плотной упаковки шаровв единичный куб.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыБлоковое кодирование: ошибки и их исправлениеПри передаче по каналу со шумом кодовое слово vпревращается в принятое слово w = v + e той же длины n.e ∈ {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кодированиеwизбыточностьvwошибкаewдекод.-1wближ.код.словоbvдекод.-2удол.избыт.wbuПрикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды181 / 432Блоковое кодирование: общая схемаuкодированиеwизбыточностьvwошибкаewдекод.-1wближ.код.словоbvдекод.-2удол.избыт.wbuПрименяя (n, k)-блоковый код, вообще говоря, необходимо:на этапе кодирования — использовать таблицу всех кодовыхслов размера 2k ×n,на этапе декодирования — перебирать все 2k кодовых словдля поиска ближайшего к принятому.В результате: использование произвольного (n, k)-блоковогокода возможно лишь при небольших значениях n и k.Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды181 / 432Блоковое кодирование: общая схемаuкодированиеwизбыточностьvwошибкаewдекод.-1wближ.код.словоbvдекод.-2удол.избыт.wbuПрименяя (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 —12сумма любых кодовых слов — кодовое слово;кодовое расстояние d = min keγ k;γe∈C3существует базис из k векторов { g 0 , g 1 , .

. . , g k−1 } и любойвектор v ∈ C может быть представлен какk−1Xv =ui g i , ui ∈ {0, 1}.i=0Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды183 / 432Элемент линейного кода: матричное представлениеv =k−1Xui g i = Gu , где G = [ g 0 g 1 . . . g k−1 ] ∈ {0, 1}n×k —i=0— порождающая матрица кодаПрикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды183 / 432Элемент линейного кода: матричное представлениеv =k−1Xui g i = Gu , где G = [ g 0 g 1 .

. . g k−1 ] ∈ {0, 1}n×k —i=0— порождающая матрица кодаПример (код Хэмминга длины n = 7 с k = 4)Ранее была получена таблица, сложением произвольных строккоторой получаются все 24 = 16 кодовых слов. Порождающаяматрица получается транспонированием этой таблицы:1 0 0 00 1 0 00 0 1 0G7×4 = 0 0 0 11 1 0 11 0 1 10 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=n−kC ⊥ — ортогональное дополнение (подпространство) кподпространству кода C, т.е.∀ v ∈ C, w ∈ C ⊥Tv× w}| {zскалярное произведение(v T — транспонированный вектор v).= 0Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыЛинейные блоковые коды: проверочная матрицаОпределениеПусть { h0 , .

. . , hm−1 } ∈ {0, 1}n — базис C ⊥ . Матрица T h0 hT  1 Hm×n =  .  .. hTm−1называется проверочной матрицей кода C.Ясно, что∀ (v ∈ C) Hv = 0;проверочная матрица определена с точностью доэквивалентных преобразований строк.187 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) кодыПостроение систематической проверочной матрицыЕсли блоковый код задан исходной порождающей матрицей Gи построена матрицаIke,Gn×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 задан порождающейматрицей0 0 11 0 11 0 0.G6×3 = 1111 1 00 1 1Требуется:1с использование данного кода осуществить (а)несистематическое и (б) систематическое кодированиевекторов u1 = [0 1 1]T и u2 = [1 0 1]T ;2построить проверочную матрицу H кода;3определить кодовое расстояние d.190 / 432Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды191 / 432Блоковый линейный код: пример кодирования...1 (a).

Несистематическое кодирование находимнепосредственно:011[ v 1 v 2 ] = G × [ u1 u2 ] = 11000011111110 10 × 1 0 = 0011 11001101.011Прикладная алгебраКоды, исправляющие ошибкиГрупповые (линейные) коды192 / 432Блоковый линейный код: пример кодирования...1 (б).

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

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