БЧХ. Корневой подход

Август 20, 2022

Главная
Математика
БЧХ. Корневой подход

Содержание

2. Постановка задачи Корректирующий циклический (n, k) код представляется в полиномиальном виде как где F2[x] - кольцо
3. Корневой подход
4. Пример Обозначим примитивный элемент конечного поля GF(2m) как α. Определим проверочную матрицу H кода C ,
5. Пример
6. Корневой подход
7. Алгоритм формирования кода 1. Строится поле GF(pm) , для которого α - примитивный элемент поля. 2.
8. Теорема Пусть циклический код C длины n задан порождающим полиномом g(x) над полем GF(p) и пусть
9. Определение БЧХ Зададим циклический код C длины n над полем GF(p), определив наименьшее целое m такое,
10. БЧХ Если b = 1 то говорят, что код БЧХ определен в узком смысле. Если же
11. Соотношение между параметрами кода Для p = 2, b = 1, n = 2m – 1
12. Проверочная матрица БЧХ aj – элементы поля. Определитель ≠0, если aj – различны.
13. Galois Field GF(23) с неприводимым полиномом: x3 + x + 1 α = x примитивный элемент
14. GF Discrete Fourier Transform (DFT) GF-DFT Интерполяция полинома в n точках через умножение на матрицу: α
15. Вычисление минимальных полиномов через циклотомические классы
16. Сопряженные элементы Так для поля ??(16)=??(2^? ) минимальным многочленом элементов является один и тот же многочлен
17. Сопряженные элементы
18. Циклотомические классы
19. Циклотомические классы
20. Циклотомический класс
21. Пример
22. Минимальные полиномы Циклотомические классы позволяют вычислить минимальные полиномы с помощью выражения
23. Пример : исправление 1 ошибки Построим порождающий полином g(z) БЧХ-кода длины n = 23 – 1
24. GF(23) Мл.разряд
25. Пример: исправление 1 ошибки 3. Минимальный полином элемента α имеет вид m1(x) = (x + α)
26. Пример: исправление 2 ошибок Изменим условия примера, потребовав исправления до двух ошибок (t = 2 ⇒
27. Пример: исправление 2 ошибок Степень последнего равна трем, так что степень g(x) окажется равной шести, и
28. Построение БЧХ кода, корректирующего три ошибки Определим конечное поле GF(24), для которого существует четыре циклотомических класса
29. GF(24) Мл. разряд
30. Построение БЧХ кода, корректирующего три ошибки Элемент α3 является корнем полинома (x5 – 1). Элементы α
32. Скачать презентацию

Слайд 2

Постановка задачи
Корректирующий циклический (n, k) код
представляется в полиномиальном виде как
где F2[x]

- кольцо многочленов над полем F2 .

Слайд 3

Корневой подход

Слайд 4

Пример
Обозначим примитивный элемент конечного поля GF(2m) как α.
Определим проверочную матрицу

H кода C , столбцы которой равны α n – 1, α n – 2, …, α α0 , где n = 2m – 1 .
Произведению (cHT) соответствует полином
Если c(α) = 0 , то получим циклический код Хэмминга

Слайд 5

Пример

Слайд 6

Корневой подход

Слайд 7

Алгоритм формирования кода
1. Строится поле
GF(pm) ,
для которого α -

примитивный элемент поля.
2. Определяются минимальные полиномы
3. Порождающий полином g(x) вычисляется как

Слайд 8

Теорема
Пусть циклический код C длины n задан порождающим полиномом g(x) над

полем GF(p) и пусть имеется наименьшее целое m такое, что n|pm – 1, а α∈ GF(pm) – примитивный корень из единицы n-й степени.
Тогда, если элементы поля GF(pm) определяют нули кода для целых b ≥ 0 и δ ≥ 2, то код имеет dmin ≥ δ.

Слайд 9

Определение БЧХ
Зададим циклический код C длины n над полем GF(p), определив

наименьшее целое m такое, что n | pm – 1 и α∈ GF(pm) – примитивный корень из единицы n-й степени.
Тогда можно определить БЧХ код C с заданным значением кодового расстояния δ и порождающим полиномом
где mb (x) минимальный многочлен элемента
α b ∈ GF(pm), b – целое положительное число.

Слайд 10

БЧХ
Если b = 1 то говорят, что код БЧХ определен в

узком смысле.
Если же n = pm – 1 (α – примитивный элемент GF(pm)), то БЧХ код называют примитивным.
Теорема. БЧХ код длины n с заданным значением кодового расстояния δ, построенный над полем GF(p), имеет dmin ≥ δ и размерность k ≥ n – m(δ – 1)
Для p = 2, b = 1 и δ = 2t + 1, k ≥ n – mt.

Слайд 11

Соотношение между параметрами кода
Для p = 2, b = 1, n

= 2m – 1 и δ = 2t +1 код БЧХ
имеет dmin = 2t + 1, если
.
Если b = 1, n = δv, тогда dmin = δ.
Если b = 1, n = pm – 1 и δ = pv – 1, тогда dmin = δ.
Если n = pm – 1, тогда dmin ≤ pδ – 1 .

Слайд 12

Проверочная матрица БЧХ
aj – элементы поля. Определитель ≠0, если aj –

различны.

Слайд 13

Galois Field
GF(23) с неприводимым полиномом: x3 + x + 1
α =

x примитивный элемент

Слайд 14

GF Discrete Fourier Transform (DFT) GF-DFT
Интерполяция полинома в n точках через умножение

на матрицу:
α – примитивный n-й корень из единицы (αn = 1) – генератор

Оценка полинома mk-1xk-1 + ⋅⋅⋅ + m1x + m0
вt n различных корнях из 1, 1, α, α2, α3, ⋅⋅⋅, αn-1

Слайд 15

Вычисление минимальных полиномов через циклотомические классы

Слайд 16

Сопряженные элементы
Так для поля ??(16)=??(2^? ) минимальным многочленом элементов
является

один и тот же многочлен

Слайд 17

Сопряженные элементы

Слайд 18

Циклотомические классы

Слайд 19

Циклотомические классы

Слайд 20

Циклотомический класс

Слайд 21

Пример

Слайд 22

Минимальные полиномы
Циклотомические классы позволяют вычислить минимальные полиномы с помощью выражения

Слайд 23

Пример : исправление 1 ошибки
Построим порождающий полином g(z) БЧХ-кода длины

n = 23 – 1 = 7, исправляющего любую однократную ошибку.
1. Для этого необходимо расширенное поле GF(23).
2. Поскольку δ = 2t + 1 = 3 = dmin, корнями порождающего полинома должны быть элементы α и α 2 т. к.
g(x) = НОК(m1( x), m2( x)), .

Слайд 24

GF(23)
Мл.разряд

Слайд 25

Пример: исправление 1 ошибки
3. Минимальный полином элемента α имеет вид
m1(x)

= (x + α) (x + α 2) (x + α 4) =
= x3 + (α + α 2 + α 4) x2 + (α α 2 + α α 4 + α 2 α 4) x + α α 2 α 4.
Но α + α 2 + α 4 = α + α 2 + α + α 2 = 0,
α α 2 + α α 4 + α 2 α 4 = α 3 + α 5 + α 6 = α + 1 + α 2 + α + 1+ α 2 + 1 = 1, α α 2 α 4 = α 7= 1,
так что
m1(x) = x3 + x +1.
5. Элемент α 2 сопряжен с α и уже учтен в m1(x), поэтому
g(x) = m1(x) = x3 + x + 1.
6. Поскольку deg{g(x)} = 3, число информационных символов кода k = 4, и, таким образом, построенный код оказался циклической версией (7,4) кода Хэмминга.

Слайд 26

Пример: исправление 2 ошибок
Изменим условия примера, потребовав исправления до двух ошибок

(t = 2 ⇒ s = 2t = 4),
множество обязательных корней полинома g(x) пришлось бы расширить до α, α 2, α 3, α 4.
Элементы α, α 2 and α 4 входят в один и тот же сопряженный цикл, т.е. уже охвачены минимальным полиномом g1(x) = x3 + x + 1.
Остается найти лишь минимальный полином для α 3 (корнями которого будут и сопряженные с ним элементы α 6 и α 12 = α 5).
Ks=3 = {s= 3, 2s = 6, 22s = 12 ≡ 5 mod 7}→m3(x) = x3 + x2 +1

Слайд 27

Пример: исправление 2 ошибок
Степень последнего равна трем, так что степень g(x)

окажется равной шести, и полученный код есть тривиальный (7,1) код с повторением, передающий лишь один бит информации.
g(x) = (x3 + x + 1) (x3 + x2 +1) =
= x6 + x5 + x4 + x3 + x2 + x + 1

Слайд 28

Построение БЧХ кода, корректирующего три ошибки
Определим конечное поле GF(24), для которого

существует четыре циклотомических класса
K1 = {1, 2, 4, 8}; K3 ={3, 6, 12, 9}; K5= {5, 10};
K7 = {7, 14, 13, 11}.
Возьмем элемент поля α3 , которому соответствует минимальный неприводимый в Z2[x] полином .

Слайд 29

GF(24)
Мл. разряд

Слайд 30

Построение БЧХ кода, корректирующего три ошибки
Элемент α3 является корнем полинома (x5

– 1). Элементы α и α3 являются корнями полинома
Степень примитивного элемента поля
и, следовательно, α5 - является корнем многочлена
x3 – 1 = x3 + 1 = (x + 1) (x2 + x + 1)
кодовые слова должны быть кратны полиному
g(x) = m135(x) = m13(x) m5(x) = m13(x) (x2 + x + 1) =
= x10 + x8 + x5 +x4 +x2 +x + 1.

БЧХ. Корневой подход

Содержание

Постановка задачиКорректирующий циклический (n, k) кодпредставляется в полиномиальном виде какгде F2[x]

Корневой подход

ПримерОбозначим примитивный элемент конечного поля GF(2m) как α. Определим проверочную матрицу

Пример

Корневой подход

Алгоритм формирования кода1. Строится поле GF(pm) , для которого α -

ТеоремаПусть циклический код C длины n задан порождающим полиномом g(x) над

Определение БЧХЗададим циклический код C длины n над полем GF(p), определив

БЧХЕсли b = 1 то говорят, что код БЧХ определен в

Соотношение между параметрами кодаДля p = 2, b = 1, n

Проверочная матрица БЧХaj – элементы поля. Определитель ≠0, если aj –

Galois Field GF(23) с неприводимым полиномом: x3 + x + 1α =

GF Discrete Fourier Transform (DFT) GF-DFTИнтерполяция полинома в n точках через умножение

Вычисление минимальных полиномов через циклотомические классы

Сопряженные элементы Так для поля ??(16)=??(2^? ) минимальным многочленом элементов является

Сопряженные элементы

Циклотомические классы

Циклотомические классы

Циклотомический класс

Пример

Минимальные полиномы Циклотомические классы позволяют вычислить минимальные полиномы с помощью выражения

Пример : исправление 1 ошибки Построим порождающий полином g(z) БЧХ-кода длины

GF(23)Мл.разряд

Пример: исправление 1 ошибки3. Минимальный полином элемента α имеет вид m1(x)

Пример: исправление 2 ошибокИзменим условия примера, потребовав исправления до двух ошибок

Пример: исправление 2 ошибокСтепень последнего равна трем, так что степень g(x)

Построение БЧХ кода, корректирующего три ошибкиОпределим конечное поле GF(24), для которого

GF(24)Мл. разряд

Построение БЧХ кода, корректирующего три ошибкиЭлемент α3 является корнем полинома (x5

Похожие презентации

Постановка задачи
Корректирующий циклический (n, k) код
представляется в полиномиальном виде как
где F2[x]

Пример
Обозначим примитивный элемент конечного поля GF(2m) как α.
Определим проверочную матрицу

Алгоритм формирования кода
1. Строится поле
GF(pm) ,
для которого α -

Теорема
Пусть циклический код C длины n задан порождающим полиномом g(x) над

Определение БЧХ
Зададим циклический код C длины n над полем GF(p), определив

БЧХ
Если b = 1 то говорят, что код БЧХ определен в

Соотношение между параметрами кода
Для p = 2, b = 1, n

Проверочная матрица БЧХ
aj – элементы поля. Определитель ≠0, если aj –

Galois Field
GF(23) с неприводимым полиномом: x3 + x + 1
α =

GF Discrete Fourier Transform (DFT) GF-DFT
Интерполяция полинома в n точках через умножение

Сопряженные элементы
Так для поля ??(16)=??(2^? ) минимальным многочленом элементов
является

Минимальные полиномы
Циклотомические классы позволяют вычислить минимальные полиномы с помощью выражения

Пример : исправление 1 ошибки
Построим порождающий полином g(z) БЧХ-кода длины

GF(23)
Мл.разряд

Пример: исправление 1 ошибки
3. Минимальный полином элемента α имеет вид
m1(x)

Пример: исправление 2 ошибок
Изменим условия примера, потребовав исправления до двух ошибок

Пример: исправление 2 ошибок
Степень последнего равна трем, так что степень g(x)

Построение БЧХ кода, корректирующего три ошибки
Определим конечное поле GF(24), для которого

GF(24)
Мл. разряд

Построение БЧХ кода, корректирующего три ошибки
Элемент α3 является корнем полинома (x5