AA3-2(ECC) (1127140), страница 4

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

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

Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами41 / 132Блоковый линейный код: пример кодирования...1 (б). Для систематического кодирования с помощьюэквивалентных преобразований столбцов выделим в матрицеG единичную подматрицу размера 3×3 (над стрелкой указанопроводимое преобразование над столбцами):0111100001111011011←1+2 −−−−→ 100011000111110e = G.101В последней матрице в строках (3, 5, 1) стоит единичнаяподматрица.Можно дальше не переставлять её строки, а просто учесть, чтобиты исходного сообщения последовательно перейдут в 3-й,5-й и 1-й биты кодового слова.ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами42 / 132Блоковый линейный код: пример кодирования...Найдём систематическое кодирование u1 , u2 :10 0 111 0 1 0 101 0 0s se× 1 0 = [ v 1 v 2 ] = G × [ u1 u2 ] = 00 1 11110 1 001 1 1101.1002. Находим проверочную матрицу H, формируя матрицу P3×3e отличных от строк с единичной подматрицей:из строк G,1 0 1P3×3 = 0 1 1.1 1 1ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодамиБлоковый линейный код: пример кодирования...Для построения проверочной матрицы H нужнопоследовательно разместить столбцы P в 3-ом, 5-ом и1-ом её столбцах соответственно,остальные 2-ой, 4-ый и 6-ой столбцы H должныобразовывать единичную подматрицу.В итоге получимH3×61 1 1 0 0 0= 1 0 0 1 1 0 .1 0 1 0 1 143 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами44 / 132Блоковый линейный код: пример кодирования...Проверим, что в результате как систематического, так инесистематического кодирований были действительно найденыкодовые слова:1 11 1 1 0 0 00n n s sH × [ v1 v2 v1 v2 ] = 1 0 0 1 1 0 × 01 0 1 0 1 1100= 00101011110010101 =1000 0 00 0 0 .0 0 0ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыКодирование линейными кодами45 / 132Блоковый линейный код: пример кодирования...3.

Найдем кодовое расстояние d: построим матрицу всех 23 = 8кодовых слов и найдем минимальный ненулевой хэммингов вес:[v 1 . . . v 8 ] = G × [u1 . . . u8 ]0 0 11 0 1 01 0 0 × 0= 0 1 100 1 01 1 1u1 , . . . , u8 — все 8возможных сообщений,v 1 , .

. . , v 8 — все 8возможных кодовых слов.Оказалось d = 3=0 0 0 1 1 1 10 1 1 0 0 1 1 =1 0 1 0 1 0 1000= 000110101000111110010011110101011011001101.100ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование линейных кодовРазделы12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать46 / 132ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование линейных кодов47 / 132Декодирование группового кода: синдромОпределениеСиндромом принятого слова w, закодированного групповым(n, k)-кодом и, возможно, содержащего ошибки, назовём векторs = Hw ∈ {0, 1}m , где H — проверочная матрица, m = n − k.Свойства синдрома:s = 0 ⇔ w — кодовое слово;s = Hw = H(v + e) = Hv + He = He,т.е. вектор ошибок e удовлетворяет системе линейныхуравнений Hm×n e = s.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование линейных кодов48 / 132Вычисление вектора ошибок по синдромуРешение СЛАУHm×n e = s(∗)относительно вектора ошибок e будем искать в виде суммычастного be решения (∗) и общего Gu решениясоответствующей однородной системы: e = be + Gu ∈ {0, 1}n .Подставляя его в (∗), получимHbe + |{z}HG u = s,|{z}где=sObe — произвольное частное решение системы Hbe = s;u — произвольный вектор длины k;O — матрица нулей размера m × k.Ясно, что Gu ∈ {0, 1}n — некоторое решение однороднойсистемы Hx = 0.ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование линейных кодов49 / 132Групповые коды: общая схема декодированияПосле нахождения частного решения be, все возможныекодовые слова u1 , . . . , u2k входного вектора дадут 2kвариантов вектора ei = be + Gui .Решение с наименьшим хэмминговым весом kei k даетискомый вектор ошибок.Получив вектор ошибок e, декодирование осуществляют поb = w + e.правилу vСхема декодирования:ww s = HwHe=sw e=be + Guw vb =w+ekek→minДля каждого из 2m синдромов необходимо перебирать 2kрешений очередной СЛАУ — алгоритм декодированиялинейного кода в общем случае имеет экспоненциальнуютрудоёмкость и по памяти, и по числу операций.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование линейных кодовДекодирование линейного кода: примерВозьмём линейный (6, 3) -код из рассмотренного ранеепримера: вектор сообщения есть u = [0 1 1]T .Систематическое кодирование для него было получено раньше:v = [1 1 0 0 1 0]T .Пусть при передаче происходит ошибка во втором бите, т.е.принятый вектор w = [1 0 0 0 1 0]T .Декодирование1.

Найдём синдром принятого сообщения w: 1 0  1 1 1 0 0 010 = 0 = s .Hw = 1 0 0 1 1 0 × 0 1 0 1 0 1 101050 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование линейных кодовДекодирование линейного кода: пример...2. Находим все решения системы He = s.2.а Находим частное решение eb этой системы.

Поскольку встолбцах 2, 4, 6 проверочной матрицы H стоит единичнаяподматрица, возьмём координаты 1, 3 и 5 вектора ebнулевыми: eb1 = eb3 = eb5 = 0 и тогдаeb2 = s1 = 1, eb4 = s2 = 0, eb6 = s3 = 0, т.е. eb = [0 1 0 0 0 0]T .2.а Все решения однородной системы He = 0 уже былинайдены раньше при вычислении кодового расстояния d:0 1 0 1 0 1 0 10 1 0 1 1 0 1 00 0 0 0 1 1 1 1.G × [ u1 .

. . u8 ] = 0 1 1 0 1 0 0 10 0 1 1 1 1 0 00 1 1 0 0 1 1 051 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование линейных кодов52 / 132Декодирование линейного кода: пример...Таким образом, все 8 решений системы He = sзаписываются как сумма вектора eb = [0 1 0 0 0 0]T со всемистолбцами матрицы G × [ u1 . . .

u8 ]:010000100101010111100010001110111011001001111.100Выбираем среди них решение с наименьшим весом — этопервый столбец e = [0 1 0 0 0 0]T . Отсюдаb = w +e = [1 0 0 0 1 0]T +[0 1 0 0 0 0]T = [1 1 0 0 1 0]T = vvи исходное сообщение восстановлено верно.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиГрупповые (линейные) кодыДекодирование линейных кодовГрупповое коды (n, k): резюмеТребование линейности позволяет реализовывать болееэффективные алгоритмы кодирования и декодирования.Кодирование осуществляется особенно просто: для этого надоумножить вектор-сообщения на порождающую матрицу.Но вопрос «как найти подходящую порождающую матрицу?»остаётся открытым.Декодирование также значительно упрощается:осуществляется с помощью легко вычисляемых синдромов;этап 2 при систематическом кодировании элементарен.Однако в общем случае требуется перебрать 2k решений СЛАУ,т.е.

несмотря на указанные упрощения, процесс декодированияостаётся всё ещё достаточно трудоёмким (экспоненциальнаясложность по k).53 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыРазделы I12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать54 / 132ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиЦиклические кодыОпределение и основные свойстваРазделы12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать55 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыОпределение и основные свойства56 / 132Циклические коды: определениеОпределениеКод C называется циклическим (эквидистантным,сдвиговым), если он инвариантен относительно циклическихсдвигов, т.е. для любого 0 6 s 6 n − 1 справедливо(α0 , .

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

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