AA3-2(ECC) (1127140), страница 9
Текст из файла (страница 9)
Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ101 / 132Коды БЧХ: пример декодированияПусть БЧХ (15, 5, 7)-код (т.е. r = 3) построен в полеF42 ∼= F2 [x]/ x4 + x + 1 .Пусть имеется сообщение [01101] ↔ u(x) = x4 + x2 + x.При систематическом кодировании (опустим этот этап) кодовоеслово естьv(x) = x14 + x12 + x11 + x8 + x4 + x3 + x2 + x ↔↔ [011110001001101](убеждаемся, что биты сообщения находятся в крайне правыхпозициях кодового слова).Пусть полином ошибокe(x) = x12 + x6 + 1 ↔↔ [100000100000100],тогда принятое слово —w(x) = x14 + x11 + x8 + x6 + x4 + x3 + x2 + x + 1 ↔[напишите сами!].ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ102 / 132Коды БЧХ: пример декодирования...Ненулевые элементы поляα1α2α3α4α5α6α7α8α9α10α11α12α13α14α15F2 [x]/ x4 + x + 1 :αα2α3α+1α2 + αα3 + α2α3 + α + 1α2 + 1α3 + αα2 + α + 1α3 + α2 + αα3 + α2 + α + 1α3 + α2 + 1α3 + 11ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды БЧХ: пример декодирования...1. Найдём синдромы для принятого слова ( α4 + α + 1):s1 = w(α) == α3 + 1 + α3 + α2 + α + α2 + 1 + α3 + α2 + α + 1 + α3 ++ α2 + α + 1 = α,s2 = w(α2 ) = (w(α))2 = α2 ,s3 = w(α3 ) = α42 + α33 + α24 + α18 + α12 + α9 + α6 + α3 + 1 = .
. .. . . = α6 + α3 + 1 = α3 + α2 + α3 + 1 = α2 + 1 = α8 ,s4 = w(α4 ) = (w(α2 ))2 = α4 ,s5 = w(α5 ) = α70 + α55 + α40 + α30 + α20 + α15 + α10 + α5 + 1 == α10 + α10 + α10 + 1 + α5 + 1 + α10 + α5 + 1 = 1,s6 = w(α6 ) = (w(α3 ))2 = (α2 + 1)2 = α4 + 1 = α.Таким образом, синдромный полиномs(x) = αx6 + x5 + α4 x4 + α8 x3 + α2 x2 + αx + 1.103 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ104 / 132Коды БЧХ: пример декодирования...2.
Выбираем декодер на базе расширенного алгоритмаЕвклида — решаем уравнение x7 a(x) + s(x)σ(x) = λ(x):Шаг 0.Шаг 1.r−2 (x) = x7 ,r−1 (x) = s(x) = αx6 + x5 + α4 x4 + α8 x3 ++α2 x2 + αx + 1,y−2 (x) = 0,y−1 (x) = 1.r−2 (x) = r−1 (x)q0 (x) + r0 (x),q0 (x) = α14 x + α13 ,r0 (x) = α8 x5 + α12 x4 + α11 x3 + α13 ,y0 (x) = y−2 (x) + y−1 (x)q0 (x) = q0 (x) = α14 x + α13 .ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ105 / 132Коды БЧХ: пример декодирования...Шаг 2.r−1 (x) = r0 (x)q1 (x) + r1 (x),q1 (x) = α8 x + α2 ,r1 (x) = α14 x4 + α3 x3 + α2 x2 + α11 x,y1 (x) = y−1 (x) + y0 (x)q1 (x) = α7 x2 + α11 x.Шаг 3.
r0 (x) = r1 (x)q2 (x) + r2 (x),q2 (x) = α9 x,r2 (x) = α5 x + α13 ,y2 (x) = y0 (x) + y1 (x)q2 (x) = αx3 + α5 x2 + α14 x + α13 .Это последний шаг алгоритма Евклида, т.к. текущий остатокr2 (x) имеет степень 1 6 r = 3.Таким образом, полином локаторов ошибок найден:σ(x) = y2 (x) = αx3 + α5 x2 + α14 x + α13и ν = deg σ(x) = 3.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды БЧХ: пример декодирования...3. Найдём корни σ(x) полным перебором (α4 = α + 1):σ(α) = α4 + α7 + 1 + α13 = α2 ,σ(α2 ) = α7 + α9 + α + α13 = α3 + α2 + α,σ(α3 ) = α10 + α11 + α2 + α13 = 0,σ(α4 ) = α13 + α13 + α3 + α13 = α2 + 1,σ(α5 ) = α + 1 + α4 + α13 = α13 ,σ(α6 ) = α4 + α2 + α5 + α13 = α3 + α2 ,σ(α7 ) = α7 + α4 + α6 + α13 = α3 + 1,σ(α8 ) = α10 + α6 + α7 + α13 = α3 + α2 + 1,σ(α9 ) = α13 + α8 + α8 + α13 = 0,σ(α10 ) = α + α10 + α9 + α13 = α,σ(α11 ) = α4 + α12 + α10 + α13 = α2 + α,σ(α12 ) = α7 + α14 + α11 + α13 = 1,σ(α13 ) = α10 + α + α12 + α13 = α2 + α + 1,σ(α14 ) = α13 + α3 + α13 + α13 = α2 + 1,σ(α15 ) = α + α5 + α14 + α13 = 0.106 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды БЧХ: пример декодирования...4. По найденным корням α3 , α9 , α15 вычисляем позицииошибок:j1 = −3 ≡15 12,j2 = −9 ≡15 6,j3 = −15 ≡15 0.5. Отсюда e(x) = x12 + x6 + 1,vb(x) = w(x) + e(x) == x14 + x12 + x11 + x8 + x4 + x3 + x2 + x = v(x)и кодовое слово восстановлено.6. Легко проверяется, что vb(α) = vb(α2 ) = . . . = vb(α6 ) = 0,(т.е. восстановление верное).107 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХБЧХ (n, k, d)-коды: исторические сведенияПервым практически реализованным БЧХ-кодом был(127, 92, 11)-код.В системах передачи данных широко используется двоичный(255, 231, 15)-код, построенный с помощью примитивногоэлемента α ∈ F82 255-го порядка:степень порождающего многочлена g(x) —m = n − k = 24;корни g(x) — α, α2 , α3 , α4 , α5 и α6 .в общем числе слов длины 255 доля кодовых —12−24 ≈ 16·106 (при вводе случайных слов только примерноодно из шестнадцати миллионов оказалось бы кодовым).В течении многих лет не было случая, чтобы ошибка передачипрошла незамеченной.Для выбора минимальных многочленов при построенииБЧХ-кодов составлены специальные таблицы.108 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ109 / 132БЧХ (n, k, d)-коды: резюмеБЧХ-коды являются подклассом циклических.Важное свойство — возможность построения кода сзаданным кодовым расстоянием d.Кодирование осуществляется с помощью порождающегополинома, имеющего корнями степени некоторогопримитивного элемента поля.Декодирование может быть проведено с помощьюэффективных алгоритмов (Берлекэмпа-Мэсси,Питерсона-Горенстейна-Цирлера, Евклидов алгоритм, ...).Среди кодов БЧХ при небольших длинах существуютхорошие (но, как правило, не лучшие из известных) коды.С ростом n при фиксированном значении скорости кода, ксожалению, d/n → 0, и поэтому при больших длинахприходится использовать другие коды.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды Рида–Соломона: общие сведенияШироко используемым частным случаем кодов БЧХ являютсякоды Рида-Соломона (Reed–Solomon codes), которыепозволяют исправлять пакеты ошибок.Пакет ошибок характеризуется вектором ошибок ( 1 — символошибочен, 0 — нет) таких, что первый и последний из нихотличны от нуля.Коды Рида–Соломона:небинарные (в частности, очень распространены кодыРида–Соломона, работающие с байтами);широко используются в устройствах цифровой записизвука, в том числе на компакт-диски.110 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениямиРазделы I12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать111 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениями112 / 132Задача ТК-1Линейный код задан своей проверочной матрицей0 0 1 1 1 1H = 0 1 0 1 1 0 1 1 1 0 1 0Требуется1построить порождающую матрицу кода G длясистематического кодирования, при котором битыисходного сообщения переходят в последние биты кодовогослова;2найти систематическое кодирование для векторов.u1 = [110]T , u2 = [101]T .ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-1...РешениеПорождающая матрица кода G, обеспечивающая требуемоеPсистематическое кодирование, должна иметь вид, где I3 —I3единичная матрица порядка размера 3.113 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениями113 / 132Задача ТК-1...РешениеПорождающая матрица кода G, обеспечивающая требуемоеPсистематическое кодирование, должна иметь вид, где I3 —I3единичная матрица порядка размера 3.Матрицу P можно получить, если привести проверочную матрицуH к виду I3 P , т.е. с помощью эквивалентных преобразованийстрок выделить в первых трех колонках единичную матрицу:0 0 1 1 1 11 1 1 0 1 01↔3 1←1+20 1 0 1 1 0 −−−→ 0 1 0 1 1 0 −−−−→1 1 1 0 1 00 0 1 1 1 11 0 1 1 0 01 0 0 0 1 11←1+3→− 0 1 0 1 1 0 −−−−→ 0 1 0 1 1 0 .0 0 1 1 1 10 0 1 1 1 1ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениями114 / 132Задача ТК-1...Теперь можно построить требуемую порождающую матрицу иосуществить кодирование для u1 = [1 1 0]T , u2 = [1 0 1]T :011G=100111010101,001100[v 1 , v 2 ] = G × [u1 , u2 ] = 110110.101ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями115 / 132Задача ТК-2Циклический (9, 3)-код задан своим порождающим полиномомg(x) = x6 + x3 + 1.Требуется определить минимальное расстояние кода d, а такжеосуществить систематическое кодирование полиномаu(x) = x2 + x ↔ [011].ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями115 / 132Задача ТК-2Циклический (9, 3)-код задан своим порождающим полиномомg(x) = x6 + x3 + 1.Требуется определить минимальное расстояние кода d, а такжеосуществить систематическое кодирование полиномаu(x) = x2 + x ↔ [011].РешениеДля определения минимального кодового расстояния d найдёмвсе кодовые полиномы:v(x) = g(x)(ax2 + bx + c) = (x6 + x3 + 1)(ax2 + bx + c) == ax8 + bx7 + cx6 + ax5 + bx4 + cx3 + ax2 + bx + c, a, b, c ∈ F2 .ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-2...В векторном виде все кодовые слова представляются как[ a, b, c, a, b, c, a, b, c ].Следовательно, минимальный хэммингов вес ненулевогокодового слова равен 3, т.е. d = 3.116 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями116 / 132Задача ТК-2...В векторном виде все кодовые слова представляются как[ a, b, c, a, b, c, a, b, c ].Следовательно, минимальный хэммингов вес ненулевогокодового слова равен 3, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
