Лекции по прикладной алгебре. v1.1 (1127111), страница 11
Текст из файла (страница 11)
, xn−1 }.Циклический сдвиг координат в этом базисе равносиленумножению на x.141 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: определениеОпределениеКод C называется циклическим, если он инвариантенотносительно циклических сдвигов, т.е. для любого0 6 s 6 n − 1 справедливо(α0 , . . . , αn−1 ) ∈ C ⇒ (αs , αs+1 , . . .
, αn−1 , α0 , . . . , αs−1 ) ∈ C.Ранее рассматривалось и было показано:В кольце Fp [x]/(xn − 1), рассматриваемом как линейноевекторное пространство над полем Fp имеется базис{ 1, x, . . . , xn−1 }.Циклический сдвиг координат в этом базисе равносиленумножению на x.Теорема: Линейное подпространство I ⊆ Fp [x]/(xn − 1)является циклическим iff I Fp [x]/(xn − 1).141 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: построениеПоэтому построить циклический код можно так:12выбираем некоторый делитель ϕ(x) многочлена xn − 1;в кольце F2 [x]/(xn − 1) образуем идеал (ϕ(x)).ϕ(x) — образующий многочлен.142 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: построениеПоэтому построить циклический код можно так:12выбираем некоторый делитель ϕ(x) многочлена xn − 1;в кольце F2 [x]/(xn − 1) образуем идеал (ϕ(x)).ϕ(x) — образующий многочлен.Оказывается:при удачном выборе ϕ(x) коэффициенты многочленов,принадлежащих этому идеалу, будут давать хороший код;есть только несколько конструкций циклических кодовс хорошими параметрами;вопрос о кодовом расстоянии произвольного циклическогокода чрезвычайно труден.142 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: пример построенияПримерПусть n = 7.
Разложение на неприводимые множители:x7 − 1 = (1 + x)(1 + x2 + x3 )(1 + x + x3 ).143 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды143 / 160Циклические коды: пример построенияПримерПусть n = 7. Разложение на неприводимые множители:x7 − 1 = (1 + x)(1 + x2 + x3 )(1 + x + x3 ).В качестве ϕ возьмем последний множитель, deg ϕ = 3.Умножая его на степени x (циклически сдвигая 3 раза) получимбазис в подпространстве, которое является кодом:(1101000) ↔ ϕ(0110100) ↔ ϕ · x(0011010) ↔ ϕ · x2(0001101) ↔ ϕ · x3Можно проверить, что кодовое расстояние для этого кода равно 3.Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыДля декодирования циклического кода нужно —— принятую кодовую комбинацию поделить на ϕ.Если остаток от деления R(x) ≡ 0, то ошибок нет (или ихбольше 1).Иначе ненулевые коэффициенты остатка от деления R(x)(вектора ошибок) определяют, в каком разряде произошлаошибка.144 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды144 / 160Для декодирования циклического кода нужно —— принятую кодовую комбинацию поделить на ϕ.Если остаток от деления R(x) ≡ 0, то ошибок нет (или ихбольше 1).Иначе ненулевые коэффициенты остатка от деления R(x)(вектора ошибок) определяют, в каком разряде произошлаошибка.(исправление одной ошибки)1) Пусть принято слово (1111000) ↔ 1 + x + x2 + x3 = ψ(x).Делим ψ(x) на ϕ(x):ϕ(x)z}|{ψ(x) = x3 + x2 + x + 1 = 1 · (x3 + x + 1) +x2 ,т.е.
R(x) = x2 ↔ (0010000).Единственный ненулевой коэффициент показывает позициюошибки: 2-й разряд.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды144 / 160Для декодирования циклического кода нужно —— принятую кодовую комбинацию поделить на ϕ.Если остаток от деления R(x) ≡ 0, то ошибок нет (или ихбольше 1).Иначе ненулевые коэффициенты остатка от деления R(x)(вектора ошибок) определяют, в каком разряде произошлаошибка.(исправление одной ошибки)1) Пусть принято слово (1111000) ↔ 1 + x + x2 + x3 = ψ(x).Делим ψ(x) на ϕ(x):ϕ(x)z}|{ψ(x) = x3 + x2 + x + 1 = 1 · (x3 + x + 1) +x2 ,т.е. R(x) = x2 ↔ (0010000).Единственный ненулевой коэффициент показывает позициюошибки: 2-й разряд.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды(исправление одной ошибки, продолжение)2) Пусть принято слово (0001100) ↔ x4 + x3 = ψ(x).Делим ψ(x) на ϕ(x):ψ(x) = x4 + x3 = (x + 1) · (x3 + x + 1) + (x2 + 1),т.е.
R(x) = x2 + 1 ↔ (1010000) — более одного ненулевогокоэффициента.Алгоритмы декодирования, основанные на применениипроверочной матрицы (о них — позже) позволяют определить,что ошибка произошла во 6-м разряде.145 / 160Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды(исправление одной ошибки, продолжение)2) Пусть принято слово (0001100) ↔ x4 + x3 = ψ(x).Делим ψ(x) на ϕ(x):ψ(x) = x4 + x3 = (x + 1) · (x3 + x + 1) + (x2 + 1),т.е.
R(x) = x2 + 1 ↔ (1010000) — более одного ненулевогокоэффициента.Алгоритмы декодирования, основанные на применениипроверочной матрицы (о них — позже) позволяют определить,что ошибка произошла во 6-м разряде.Операции декодирования циклических кодов (умножения иделения многочленов) просто реализуются на регистрах сдвигас обратными связями. Эта техническая простота и послужилапричиной их широкого распространения.145 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды146 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХРаздел IIКоды БЧХЧто надо знать147 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХКоды БЧХ — коды длины n = 2k − 1Рассматриваемый далее способ построения «хорошего» кода,исправляющего «много» ошибок предложили Радж ЧандраБоуз и Двайджендра Камар Рей-Чоудхури в 1959 г.
инезависимо Алексис Хоквингем в 1960 г.Они называются кодами Боуза-Чоудхури-Хоквингема илиБЧХ-кодами (BCH, Bose-Chaudhuri-Hocquenghem) — это классциклических кодов, исправляющих кратные (2 и более) ошибки.Теоретически коды БЧХ могут исправлять произвольноеколичество ошибок, но при этом существенно увеличиваетсядлина кодового слова (что приводит к уменьшению скоростипередачи данных и усложнению приёмно-передающейаппаратуры).Коды Хэмминга — частный случай БЧХ-кодов.148 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХУточнение описанной выше схемы при n = 2m − 1 —— конкретизирующей выбор идеала:149 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХУточнение описанной выше схемы при n = 2m − 1 —— конкретизирующей выбор идеала:123Строим поле Fn2 ∼= F2 [x]/(f ), f — неприводимыймногочлен степени n = 2m − 1.Выберем в циклической группе Fn∗2 порождающий элементn∗α ∈ F2 и рассмотрим его степениα, α2 , .
. . , α2r ,где r — число ошибок, которые нужно уметь исправлять.В разложении многочлена xn − 1 выберем такиенеприводимые многочлены, чтобы каждая из указанныхстепеней была корнем одного из них. ϕ есть результатперемножения этих многочленов.Коды — коэффициенты многочленов из идеала (ϕ).149 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХУточнение описанной выше схемы при n = 2m − 1 —— конкретизирующей выбор идеала:123Строим поле Fn2 ∼= F2 [x]/(f ), f — неприводимыймногочлен степени n = 2m − 1.Выберем в циклической группе Fn∗2 порождающий элементn∗α ∈ F2 и рассмотрим его степениα, α2 , .
. . , α2r ,где r — число ошибок, которые нужно уметь исправлять.В разложении многочлена xn − 1 выберем такиенеприводимые многочлены, чтобы каждая из указанныхстепеней была корнем одного из них. ϕ есть результатперемножения этих многочленов.Коды — коэффициенты многочленов из идеала (ϕ).Оказывается (далее будет доказано), что это гарантируетисправление r ошибок.149 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ150 / 160Построение кода БЧХ, исправляющего 3 ошибкиПример (m = 4, многочлен для разложения: x15 − 1)Пусть нужен код, исправляющий r = 3 ошибки. Значит, нужнонайти многочлены, корнями которых являются первые 2r = 6степеней порождающего элемента α.123если многочлен имеет кореньαα3α5то он имеет корниα2 , α4 , α86α , α12 , α9 (= α24 )α10По трём наборам корней построим три многочлена, два — 4-йстепени и один — 2-й.
Перемножив их, получим многочлен 10-йстепени.Идеал по модулю этого многочлена будет 5-мернымпространством.Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХСколько элементов содержит идеал (ϕ)?ϕ = произведение некоторых специально выбранныхнеприводимых многочленов-делителей xn − 1.Каждый делитель имеет, как минимум, 2 корня изсовокупности { α, .
. . , α2r }, т.е. их требуется не более rштук.Если делитель имеет корнями s элементовs{ αt , α2t , . . . , α2 t }, то 2s 6 n = 2m − 1, т.е. степенькаждого делителя не более m = log2 (n + 1).deg ϕ 6 rm = r log2 (n + 1).Идеал, порожденный ϕ, имеет размерность n − deg ϕ.2n|(ϕ)| 6 2n−r log2 (n+1) = (n+1)r.Ясно, что эта оценка далека от точности.151 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХСколько элементов содержит идеал (ϕ)?ϕ = произведение некоторых специально выбранныхнеприводимых многочленов-делителей xn − 1.Каждый делитель имеет, как минимум, 2 корня изсовокупности { α, .
. . , α2r }, т.е. их требуется не более rштук.Если делитель имеет корнями s элементовs{ αt , α2t , . . . , α2 t }, то 2s 6 n = 2m − 1, т.е. степенькаждого делителя не более m = log2 (n + 1).deg ϕ 6 rm = r log2 (n + 1).Идеал, порожденный ϕ, имеет размерность n − deg ϕ.2n|(ϕ)| 6 2n−r log2 (n+1) = (n+1)r.Ясно, что эта оценка далека от точности.151 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХОценка кодового расстоянияПокажем, что расстояние между точками кода не меньше, чем2r + 1 (что нам и требуется!).152 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХОценка кодового расстоянияПокажем, что расстояние между точками кода не меньше, чем2r + 1 (что нам и требуется!).Все многочлены, входящие в код — в идеал (ϕ) — кратны ϕ⇒ каждый кодовый многочлен имеет корни α, α2 , . .
. , α2r(как и ϕ).Кодовое расстояние = min keγ k, γe — элемент кода.Значит, надо доказать следующееУтверждениеЕсли многочлен ψ ∈ (ϕ) имеет корни αs , s = 1, . . . , 2r, то у ψне менее 2r + 1 ненулевого коэффициента.152 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХОценка кодового расстояния...ДоказательствоРассмотрим многочленψ(x) = a0 + a1 x + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
