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

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

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

. . , 6(т.е. все ненулевые элементы F2 [x]/ x3 + x + 1 ):α0 = 1,α1 = α,α2 = α2 ,α3 = α + 1,α4 = α(α + 1) = α2 + α,α5 = α2 (α + 1) = α3 + α2 = α2 + α + 1 = s1 ,α6 — можно уже не вычислять!Отсюда следует, что ошибка произошла в позиции 5 и, такимобразом, vb(x) = w(x) + x5 = x6 + x5 + 1 = v(x).90 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды БЧХ: декодированиеПусть при передаче сообщения, закодированого кодом БЧХ вполе Fq2 ∼= F[x]/(a(x)) произошло ν ошибок.Тогда e(x) = xj1 + xj2 + · · · + xjν , где степени j1 , .

. . , jν —позиции (локаторы) ошибок, ν 6 r = [(d − 1)/2].91 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды БЧХ: декодированиеПусть при передаче сообщения, закодированого кодом БЧХ вполе Fq2 ∼= F[x]/(a(x)) произошло ν ошибок.Тогда e(x) = xj1 + xj2 + · · · + xjν , где степени j1 , . . . , jν —позиции (локаторы) ошибок, ν 6 r = [(d − 1)/2].Запишем равенства si = w(αi ) = e(αi ), i = 1, 2r как систему:s1 = αj1 + αj2 + .

. . + αjν ,s2 = (αj1 )2 + (αj2 )2 + . . . + (αjν )2 ,...................................s2r = (αj1 )2r + . . . + (αjν )2r .91 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды БЧХ: декодированиеПусть при передаче сообщения, закодированого кодом БЧХ вполе Fq2 ∼= F[x]/(a(x)) произошло ν ошибок.Тогда e(x) = xj1 + xj2 + · · · + xjν , где степени j1 , . . . , jν —позиции (локаторы) ошибок, ν 6 r = [(d − 1)/2].Запишем равенства si = w(αi ) = e(αi ), i = 1, 2r как систему:s1 = αj1 + αj2 + . .

. + αjν ,s2 = (αj1 )2 + (αj2 )2 + . . . + (αjν )2 ,...................................s2r = (αj1 )2r + . . . + (αjν )2r .Любое решение данной системы ( j1 , . . . , jν ) для некоторогоν 6 r будет искомым (такое решение всегда существует иединственно, т.к. код по построению способен исправлять до rошибок).91 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды БЧХ: декодирование...Введя обозначения βi = αji , i = 1, 2r, перепишем систему:s1 = β1 + β2 + .

. . + βν ,s2 = β12 + β22 + . . . + βν2 ,(1) .......................s2r = β12r + β22r + . . . + βν2r .Рассмотрим полином локаторов ошибокνYσ(x) =(1 + βi x) = 1 + σ1 x + σ2 x2 + · · · + σν xν ,i=1корнями которого являются величины βi−1 = α−ji , i = 1, 2r.Для продвинутых: это производящий полином.92 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ93 / 132Коды БЧХ: декодирование...Связь между σk и βi определяет теорема Виета:σ1 = β1 + β2 + . . . + βν ,σ2 = β1Xβ2 + β2 β3 + β1 β3 + . . .

+ βν−1 βν ,σ3 =βi1 βi2 βi3 ,i<i<i123.......................σν = β1 β2 . . . βν .(2)ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ93 / 132Коды БЧХ: декодирование...Связь между σk и βi определяет теорема Виета:σ1 = β1 + β2 + . . . + βν ,σ2 = β1Xβ2 + β2 β3 + β1 β3 + . . . + βν−1 βν ,σ3 =βi1 βi2 βi3 ,i<i<i123.......................σν = β1 β2 . . . βν .(2)Введённые системы задают величины синдромов икоэффициентов полинома локаторов ошибок соответственнокак значения симметрических полиномов:(1) — суммы k-ых степеней βi , k = 1, 2r;(2) — элементарного.Соотношения между этими двумя типами симметрическихполиномов задаются тождествами Ньютона-Жирара.ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ94 / 132Коды БЧХ: декодирование...В двоичной арифметике тождества Ньютона-Жираразаписываются какs1 + σ1 = 0,s2 + σ1 s1 + 2σ2 = 0,s3 + σ1 s2 + σ2 s1 + 3σ3 = 0,.............................sν + σ1 sν−1 + . . . + σν−1 s1 + νσν = 0,sν+1 + σ1 sν + . . . + σν−1 s2 + σν s1 = 0,sν+2 + σ1 sν+1 + .

. . + σν−1 s3 + σν s2 = 0,.........................................s2r + σ1 s2r−1 + . . . + σν−1 s2r−ν+1 + σν s2r−νКлючевое уравнение= 0.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ95 / 132Коды БЧХ: декодирование...В литературе по кодам последние 2r − ν + 1 уравнений даннойсистемы получили название ключевого уравнения — оноявляется СЛАУ относительно σ1 , .

. . , σν .Решение ключевого уравнения позволяет найти полиномлокаторов ошибок σ(x).Далее полным перебором можно найти все его корни α−ji , а поним — позиции ошибок ji , i = 1, 2r.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ95 / 132Коды БЧХ: декодирование...В литературе по кодам последние 2r − ν + 1 уравнений даннойсистемы получили название ключевого уравнения — оноявляется СЛАУ относительно σ1 , . .

. , σν .Решение ключевого уравнения позволяет найти полиномлокаторов ошибок σ(x).Далее полным перебором можно найти все его корни α−ji , а поним — позиции ошибок ji , i = 1, 2r.Основная трудность в решении ключевого уравнения состоит втом, что значение ν неизвестно.Рассмотрим два наиболее простых способа решения ключевогоуравнения — их называют декодерами.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ96 / 132Коды БЧХ: декодирование...1. Декодер PGZ (Peterson-Gorenstein-Zierler) —состоит в последовательном решении ключевого уравнения дляν = r, r − 1, .

. . до тех пор, пока матрица очередной СЛАУ неокажется невырожденной (при переходе от r к r − 1 полагаемσr = 0).2. Декодер на базе расширенного алгоритма ЕвклидаДля нахождения полинома локаторов ошибок σ(x) и егокорней введём вспомогательный синдромный полиномs(x) = 1 + s1 x + s2 x2 + . . . + s2r x2r ,где si = w(αi ), i = 1, . . . , 2r — синдромы.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ96 / 132Коды БЧХ: декодирование...1. Декодер PGZ (Peterson-Gorenstein-Zierler) —состоит в последовательном решении ключевого уравнения дляν = r, r − 1, .

. . до тех пор, пока матрица очередной СЛАУ неокажется невырожденной (при переходе от r к r − 1 полагаемσr = 0).2. Декодер на базе расширенного алгоритма ЕвклидаДля нахождения полинома локаторов ошибок σ(x) и егокорней введём вспомогательный синдромный полиномs(x) = 1 + s1 x + s2 x2 + . . . + s2r x2r ,где si = w(αi ), i = 1, . . . , 2r — синдромы.Для продвинутых: это тоже производящий полином.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды БЧХ: декодирование...Перемножим полиномы — синдромный и локаторов ошибок:λ(x) = s(x)σ(x) = 1 + λ1 x + λ2 x2 + .

. . + λ2r+ν x2r+ν .Здесь коэффициенты λj =jXsi σj−i определяютсяi=0соотношением для произведения многочленов.Поскольку σ0 = 1 ключевое уравнение эквивалентно условиюλν+1 = λν+2 = . . . = λ2r = 0, т.е.λ(x) = 1 + λ1 x + λ2 x2 + . . . + λν xν ++ λ2r+1 x2r+1 + . . . + λ2r+ν x2r+ν .97 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХКоды БЧХ: декодирование...Перемножим полиномы — синдромный и локаторов ошибок:λ(x) = s(x)σ(x) = 1 + λ1 x + λ2 x2 + .

. . + λ2r+ν x2r+ν .Здесь коэффициенты λj =jXsi σj−i определяютсяi=0соотношением для произведения многочленов.Поскольку σ0 = 1 ключевое уравнение эквивалентно условиюλν+1 = λν+2 = . . . = λ2r = 0, т.е.λ(x) = 1 + λ1 x + λ2 x2 + . . . + λν xν ++ λ2r+1 x2r+1 + . . . + λ2r+ν x2r+ν .Рассмотрим остаток от деления λ(x) на x2r+1 . Ясно, чтоλ(x) ≡x2r+1 1 + λ1 x + · · · + λν xν .97 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ98 / 132Коды БЧХ: декодирование...Таким образом, некоторый многочлен λ(x) и полиномлокаторов ошибок σ(x) удовлетворяют уравнениюs(x)σ(x) + x2r+1 a(x) = λ(x)(напоминание: работаем в поле(∗)Fq2 ∼= F2 [x]/(a(x)) ).Данное уравнение может быть решено с помощьюрасширенного алгоритма Евклида для пары многочленов2r+1x, s(x) со свойствами:условие остановки — степень очередного остатка 6 r;количество фактически совершенных ошибок —ν = deg σ(x).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ98 / 132Коды БЧХ: декодирование...Таким образом, некоторый многочлен λ(x) и полиномлокаторов ошибок σ(x) удовлетворяют уравнениюs(x)σ(x) + x2r+1 a(x) = λ(x)(напоминание: работаем в поле(∗)Fq2 ∼= F2 [x]/(a(x)) ).Данное уравнение может быть решено с помощьюрасширенного алгоритма Евклида для пары многочленов2r+1x, s(x) со свойствами:условие остановки — степень очередного остатка 6 r;количество фактически совершенных ошибок —ν = deg σ(x).Замечание: наиболее эффективным декодером кодов БЧХявляется декодер Берлекэмпа-Мэсси.ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ99 / 132Э. Берлекэмп и Д. МэссиЭлвин Ральф Берлекэмп(Elwyn Ralph Berlekamp (1940)— американский математик,внесший существенный вклад в теориикодирования и комбинаторных игр (игра Го).Помимо математики,занимался инвестиционным менеджментом.Джеймс Ли Мэсси(James Lee Massey, (1934-2013)— выдающийся американский ученый,внесший значительный вклад втеорию информации и криптографию(в частности, в соавторстве разработалшифры SAFER и IDEA).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ100 / 132Коды БЧХ: общая схема декодированияПусть принято слово w(x), являющееся сообщением,закодированным БЧХ (n, k, d)-кодом и, возможно, содержащееошибки.1Для слова w(x) найти все синдромы si = w(αi ), i = 1, d − 1.2Найти полином локаторов ошибок σ(x), используя тот илииной декодер.3Найти все корни σ(x) полным перебором всех элементовполя Fq2 (их 2q − 1 = n, т.е.

алгоритм линейный по n, чегои добивались!); пусть найденные корни суть αk1 , . . . , αkν .4Найти позиции ошибок ji ≡n −ki , i = 1, ν.5Исправить ошибки, получив словоvb(x) = w(x) + xj1 + . . . + xjν .6Найти все значения vb(αi ), i = 1, d − 1; если не все ониравны нулю, то выдать отказ от декодирования.ПРИКЛАДНАЯ АЛГЕБРА.

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

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