AA3-2(ECC) (1127140), страница 3
Текст из файла (страница 3)
Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойстваГрупповые коды: определениеБо́льшая часть теории блокового кодирования построена налинейных или групповых кодах, образующих группу относительно⊕ (двоичные коды) и позволяющих реализовывать эффективныеалгоритмы кодирования/декодирования.Утверждение 1Устойчивая совокупность кодовых слов C = αe , ..., αetобразует группу по сложению относительно операции ⊕.27 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойстваГрупповые коды: определениеБо́льшая часть теории блокового кодирования построена налинейных или групповых кодах, образующих группу относительно⊕ (двоичные коды) и позволяющих реализовывать эффективныеалгоритмы кодирования/декодирования.Утверждение 1Устойчивая совокупность кодовых слов C = αe , ..., αetобразует группу по сложению относительно операции ⊕.ДоказательствоУстойчивость (предполагается): для любых кодовых словαei , αej ∈ C выполняется αei ⊕ αej = αek ∈ C;Ассоциативность: свойство операции ⊕ ;defСуществование 0: αe⊕αe = ( 0, .
. . , 0 ) = e0 ∈ C;Противоположные элементы: −eα = αe — см. выше.27 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойстваСвойство кодового расстояния линейного кодаТеоремаКодовое расстояние d линейного кода C равноd = min ρ αe, βe = min keγ k,αe6=βeгде αe, βe и γe — кодовые слова из C.γe6=e028 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойства28 / 132Свойство кодового расстояния линейного кодаТеоремаКодовое расстояние d линейного кода C равноd = min ρ αe, βe = min keγ k,αe6=βeγe6=e0где αe, βe и γe — кодовые слова из C.ДоказательствоДля произвольных кодовых словeи βe всегда существует их αсумма — кодовое слово γ: ρ αe, βe = αe ⊕ βe = keγ k,eпричем γe 6= e0 при αe 6= β.Отсюда получаем оценку min ρ αe, βe > min keγ k.αe6=βeγe6=e0Эта оценка достигается, например, при βe = e0.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойстваХарактеристики кода Хэмминга:исправляет одну ошибку;избыточность —m;2m − 1совершенный код: осуществляет плотную упаковку —mкуб B 2 −1 разбивается на2nmt== 22 −(m+1)n+1шаров радиуса r = 1 с центрами в кодовых словах;код Хэмминга — групповой ( 2m − 1, 2m − 1 − m, 3 )-код.29 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойстваЛинейные коды{0, 1}n — n-мерное координатное (линейное) пространство надконечным полем F2 = {0, 1}.ОпределениеБлоковый (n, k)-код C называется линейным (то же, что игрупповым в двоичном случае), если он образует линейноеподпространство размерности k координатного пространства{0, 1}n .30 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойстваЛинейные коды{0, 1}n — n-мерное координатное (линейное) пространство надконечным полем F2 = {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=030 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойства31 / 132Элемент линейного кода: матричное представлениеv =k−1Xui g i = Gu , где Gn×k = [ g 0 g 1 . . . g k−1 ] —i=0— порождающая матрица кода.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыОпределение и свойства31 / 132Элемент линейного кода: матричное представлениеv =k−1Xui g i = Gu , где Gn×k = [ g 0 g 1 . . . g k−1 ] —i=0— порождающая матрица кода.Пример ( (7, 4)-код Хэмминга)Ранее была получена таблица, сложением произвольных строккоторой получаются все 24 = 16 кодовых слов.
Порождающаяматрица получается транспонированием этой таблицы:1 0 0 00 1 0 00 0 1 0G7×4 = 0 0 0 11 1 0 11 0 1 10 1 1 1ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодамиРазделы12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать32 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами33 / 132Линейные коды: кодированиекодированиеuw v = GuизбыточностьНа практике используютсистематическое кодирование, при котором k бит исходногосообщения копируются в фиксированные позиции кодовогослова, а затем вычисляются остальные m = n − kпроверочных бит.Такая возможность основана на том, что матрица Gопределена с точностью до эквивалентных преобразованийстолбцов (переход к другому базису).При систематическом кодировании 2-й этап декодированияb → ub , удаление избыточности) становится тривиальным.(vПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами34 / 132Систематическое кодирование: примерПусть линейный код задан порождающей матрицей G.С помощью эквивалентных преобразований столбцовматрица G может быть приведена к виду, в котором (безпотери общности — первые) k строк образуют единичнуюподматрицу Ik :Ike n×k =Gn×k −→ GPm×ke будет систематическим:Тогда кодирование v = Guпервые k бит кодового слова v являются битамиисходного сообщения u.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами35 / 132Ортогональное дополнение к подпространству кодаРазложение пространства {0, 1}n в прямую суммуподпространств:пространствоdim{0, 1}nn=Ck+C⊥m=n−kC ⊥ — ортогональное дополнение (подпространство) кподпространству кода C, т.е.∀ v ∈ C, w ∈ C ⊥Tv× w}| {zскалярное произведение(v T — транспонированный вектор v).= 0ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодамиЛинейные коды: проверочная матрицаОпределениеПусть { h0 , .
. . , hm−1 } ∈ {0, 1}n — базис C ⊥ . Тогда матрица T h0 hT 1 Hm×n = . .. hTm−1называется проверочной матрицей кода C.Ясно, что∀ v ∈ C ( Hv = 0 );проверочная матрица определена с точностью доэквивалентных преобразований строк.36 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами37 / 132Построение систематической проверочной матрицыЕсли линейный код C задан исходной порождающей матрицейG и построена матрицаIke,Gn×k =Pm×kто проверочной матрицей H кода C будетHm×n = Pm×k Im(Ik и Im — единичные матрицы порядков k и m).Действительно, в этом случаеe = (P + P )u = 0.Hv = H GuПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами38 / 132Линейный систематический код: заданиеТаким образом, линейный код для сообщений длины k имеетдлину n = k + m и задаётсялибо порождающей матрицей размера n×k,либо проверочной матрицей размера m×n.Эти матрицыопределены с точностью до эквивалентных преобразованийстолбцов и строк соответственно, что соответствуетвыбору различных базисов в пространствах C и C ⊥ ,однако фиксирование позиций информационных бит присистематическом кодировании задаёт порождающую ипроверочную матрицу однозначно.Увеличение m ведёт к увеличению кодового расстояния d(как конкретно — никто не знает) и, следовательно, кувеличению количества ошибок, которые может исправить код.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодамиБлоковый линейный код: пример кодированияДано: линейный (6, 3)-код C задан порождающей матрицейG6×3011= 110000111110.101Требуется:1с использование данного кода осуществить(а) несистематическое и (б) систематическое кодированиевекторов u1 = [0 1 1]T и u2 = [1 0 1]T ;2построить проверочную матрицу H кода;3определить кодовое расстояние d.39 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами40 / 132Блоковый линейный код: пример кодирования...1 (a). Несистематическое кодирование находимнепосредственно:011n n[ v 1 v 2 ] = G × [ u1 u2 ] = 11000011111110 10 × 1 0 = 0011 11001101.011ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
