Циклические коды

Август 21, 2022

Главная
Информатика
Циклические коды

Содержание

2. Циклические коды (ЦК) Подкласс линейных кодов Кодирование и декодирование основано на: 1. Полиномиальном представлении 2. Операторах
3. Определение. Линейный (n, k)-код C над полем Fq называется циклическим, если из того, что вектор с
4. Циклический блоковый код с с с с с с = = = = = = )
5. ЦК - полиномы Алгебраическая структура Кодовые слова представляются как многочлены от x степени не выше n
6. Генераторный полином Важным свойством циклических кодов является то, что все кодовые слова-полиномы кратны одному фиксированному полиному
7. Генераторная матрица Генераторная матрица кода представляется как матрица размером (k×n) следующего вида Строки матрицы G линейно
8. Пример Циклический код Хэмминга (7, 4, 3) задается порождающим полиномом g(x) = x3 + x +
9. Пример Решение Обратимся к полиномам для систематического кодирования xm mod g(x), m = n – 1,
10. Требования к порождающему полиному : 1. g(x) должен быть ненулевым; 2. вес g(x) не должен быть
11. Факторизация бинома ( x n – 1) Разложим бином ( x n – 1) на множители
12. Проверочный многочлен h(x) Разобьем факторизованное множество на два непересекающихся подмножеств – Jg и Jh – так,
13. Проверочный многочлен h(x) Если полином g(x) - порождающий, то любое кодовое слово можно представить в виде
14. Проверочная матрица Проверочная матрица циклического кода C имеет вид или
15. Соотношение степеней Для циклического кода число информационных символов k и число проверочных символов r определяется как
16. Пример Построить циклический код над GF(2) длины n = 31 с числом проверочных символов r =
18. Пример
19. Пример
20. Пример
24. Проверочная матрица
28. Сравнительный анализ
30. Вычисление синдрома
31. Вычисление синдрома
32. Кодирование циклических кодов Кодирование с помощью порождающего полинома g(x). Несистематическое кодирование Систематическое кодирование где a(x) –
33. Систематическое кодирование Полином кодового слова c(x) находится с помощью соотношения c(x) = a(x) + b(x), где
34. Пример Для систематического циклического кода Хэмминга (7, 4) генераторный полином равен Найти кодовое слово для сообщения
35. Решение
36. Порождающая и проверочная матрицы Найдем матрицы G и H, соответственно. Несистематическая форма Преобразуем матрицу:
37. Кодирование циклическим кодом с помощью проверочного многочлена h(x) Систематическое кодирование низкоскоростным циклическим кодом удобно проводить с
38. Умножение и деление полиномов Умножение a(x) = ak xk +ak-1 xk-1+ …+ a1 x +a0 h(x)
39. Схемы умножения Внешние сумматоры Внутренние сумматоры D – элемент задержки на такт
40. Пример Схема умножения на полином h(x) = x6 + x5 +x4 +x3 +1 над GF(2)
41. Умножение полиномов Умножение на p3 +p+1 Эквивалентные топологии: unit delay element XOR-circuit Data in Encoded bits
42. Умножение по шагам Генераторный полином Инф. слово Кодовое слово x0 x1 x3
43. Деление полиномов d(x) = dn xn +dn-1 xn-1+ …+ d1 x +d0 g(x) = gr xr
44. Деление полиномов Внешние сумматоры
45. Пример Схема деления на полином g(x) = x6 +x5 +x4 +x3 + 1 над GF(2)
46. Кодер систематического циклического кода
47. Кодер систематического кода a Проверочные Кодовое слово Обратная связь Буфер Вход
48. Кодер систематического кода по h(x) 1 2 h0
49. Кодирование циклическим кодом путем задания корней всех кодовых полиномов Кодирование предполагает переход в соответствующее расширенное поле
50. Кодирование
51. Пример Пример. Построить проверочную матрицу циклического кода с параметрами (15, 11), используя метод задания корней кодовых
52. Решение. Определим полином f = x15 – 1. Разложим данный полином на множители, применив оператор: >
53. Выберем из полученного результата полином g(x) = (x4 + x + 1). Используя оператор irreduc( x^4
54. Определим примитивный элемент поля > alias (alpha = RootOf(Z^4 + Z + 1) mod 2): и
55. Найдем корни полинома (x4 + x + 1) в расширенном поле путем разложения полинома на элементарные
56. Таким образом, корнями полинома (x4 + x + 1) являются следующие элементы поля: .
57. Используя выражение для H и представляя корни β как вектор столбцы, после соответствующих упрощений получим
61. Скачать презентацию

Слайд 2

Циклические коды (ЦК)
Подкласс линейных кодов
Кодирование и декодирование основано на:
1.

Полиномиальном представлении
2. Операторах сдвига (регистрах сдвига с обратной связью РСОС)
Это упрощает решение задач ТК

Слайд 3

Определение.
Линейный (n, k)-код C над полем Fq называется циклическим, если из

того, что вектор
с = (c0, c1, …, cn-1)
принадлежит C, следует, что его циклический сдвиг
с(1) = (cn-1, c0, c1, …, cn-2 )
принадлежит C.

Слайд 4

Циклический блоковый код
с
с
с
с
с
с
=
=
=
=
=
=
)
1101
(

)
1011
(

)
0111
(

)
1110
(
)
1101
(
)
4
(
)
3
(
)
2
(
)
1
(
Пример

Слайд 5

ЦК - полиномы Алгебраическая структура
Кодовые слова представляются как многочлены от

x степени не выше n – 1
c = (c0, c1, …, cn – 1) → c(x) = c0 + c1 x + …+ cn-1 xn – 1.
Соотношения между кодовым словом и циклическими сдвигами:

По индукции

В полиномиальном представлении циклический сдвиг на одну позицию соответствует умножению на
x
по модулю
(xn – 1):

Слайд 6

Генераторный полином
Важным свойством циклических кодов является то, что все кодовые слова-полиномы

кратны одному фиксированному полиному g(x), который называется порождающим полиномом кода. Порождающий полином g(x) является делителем бинома ( x n – 1).

Множество {xi g(x); 0 ≤ i ≤ k – 1}можно рассматривать как базис размерности k циклического кода С.

Слайд 7

Генераторная матрица
Генераторная матрица кода представляется как матрица размером (k×n) следующего вида
Строки

матрицы G линейно независимы, и таким образом, ранг матрицы G равен k – размерности кода C. С помощью такой матрицы осуществляется несистематическое кодирование.

Слайд 8

Пример
Циклический код Хэмминга
(7, 4, 3)
задается порождающим полиномом
g(x) =

x3 + x + 1,
имеющий двоичное представление в виде кода
g = (1101).
Требуется. Построить порождающую матрицу систематического кода.

Слайд 9

Пример Решение
Обратимся к полиномам для систематического кодирования
xm mod g(x), m = n

– 1, …, n – k – 1.
Найдем остаток по модулю x3 + x + 1 степеней xm

Слайд 10

Требования к порождающему полиному :
1. g(x) должен быть ненулевым;
2. вес

g(x) не должен быть меньше минимального кодового расстояния:
;
3. g(x) должен иметь максимальную степень (n – k), которая определяет число избыточных элементов в коде;
4. g(x) должен быть делителем полинома (x n – 1).

Слайд 11

Факторизация бинома ( x n – 1)
Разложим бином ( x

n – 1) на множители mj(x), j = 1, 2, …, l,
( x n – 1) = m1(x) m2(x) … ml(x).
Представим многочлен ( x n – 1) как произведение минимальных многочленов

где J – множество индексов.

Слайд 12

Проверочный многочлен h(x)
Разобьем факторизованное множество на два непересекающихся подмножеств – Jg

и Jh – так, что
J = Jg ∪ Jh .
Введем два полинома

Многочлены g(x) и h(x) удовлетворяют условию
g(x) h(x) = (x n – 1).

Слайд 13

Проверочный многочлен h(x)
Если полином g(x) - порождающий, то любое кодовое слово

можно представить в виде
c(x) = a(x) g(x),
где a(x) – информационный полином. Следовательно, имеет место равенство
c(x) h(x) = a(x) g(x) h(x) = a(x)(xn – 1).
Откуда следует, что
c(x) h(x) ≡ 0 mod (xn – 1).
Многочлен h(x) называется проверочным полиномом, он может быть вычислен как

Слайд 14

Проверочная матрица
Проверочная матрица циклического кода C имеет вид
или

Слайд 15

Соотношение степеней
Для циклического кода число информационных символов k и число проверочных

символов r определяется как
Код с порождающей матрицей H , т. е. код, дуальный к коду C , также является циклическим кодом.
Кодовые слова по полиному h(x) образуют нуль пространство относительно кодовых слов построенных по полиному g(x).

Слайд 16

Пример
Построить циклический код над GF(2) длины n = 31 с числом

проверочных символов r = 16.
Решение. Проведем факторизацию (разложение на множители) полинома x31 – 1
Множество индексов J имеет вид J = {0, 1, 3, 5, 7, 11, 15}.
Для r = 16 выберем полином

Для k = 15, проверочный полином

Слайд 17

Слайд 18

Пример

Слайд 19

Пример

Слайд 20

Пример

Слайд 21

Слайд 22

Слайд 23

Слайд 24

Проверочная матрица

Слайд 25

Слайд 26

Слайд 27

Слайд 28

Сравнительный анализ

Слайд 29

Слайд 30

Вычисление синдрома

Слайд 31

Вычисление синдрома

Слайд 32

Кодирование циклических кодов Кодирование с помощью порождающего полинома g(x).
Несистематическое кодирование
Систематическое

кодирование
где a(x) – полином информационного сообщения.

Слайд 33

Систематическое кодирование
Полином кодового слова c(x) находится с помощью соотношения
c(x) =

a(x) + b(x),
где
многочлен информационных символов;
многочлен проверочных символов.
Для нахождения многочлена проверочных символов при систематическом кодировании достаточно разделить многочлен информационных символов на порождающий полином.
Остаток от деления и будет искомым многочленом проверочных символов

Слайд 34

Пример
Для систематического циклического кода Хэмминга (7, 4) генераторный полином равен
Найти кодовое

слово для сообщения

Слайд 35

Решение

Слайд 36

Порождающая и проверочная матрицы
Найдем матрицы G и H, соответственно.
Несистематическая форма
Преобразуем матрицу:

Слайд 37

Кодирование циклическим кодом с помощью проверочного многочлена h(x)
Систематическое кодирование низкоскоростным циклическим

кодом удобно проводить с помощью проверочного полинома, имеющего в данном случае меньшую размерность, чем порождающий многочлен.
Коэффициенты многочлена проверочных символов b(x) вычисляются по коэффициентам многочленов c(x) и h(x) следующим образом
что вытекает из равенства cHT = 0. Эти соотношения позволяют по заданным информационным символам вычислить проверочный символ ck, затем, зная ck, вычислить ck + 1 и т. д.

Слайд 38

Умножение и деление полиномов
Умножение
a(x) = ak xk +ak-1 xk-1+ …+

a1 x +a0
h(x) = hr xr +hr xr-1 + … + h1 x +h0
a(x)h(x) =ak hr xk+r+ (ak-1 hr +ak hr-1) xk+r-1 +
(ak-2 hr + ak-1 hr-1 + ak hr-2) xk+r-2 + …
…+ (a0 h2 + a1 h1 + a2 h2)x2 + (a0 h1 + a1 h0 ) x + a0 h0

Слайд 39

Схемы умножения
Внешние сумматоры
Внутренние сумматоры
D – элемент задержки на такт

Слайд 40

Пример
Схема умножения на полином
h(x) = x6 + x5 +x4 +x3

+1 над GF(2)

Слайд 41

Умножение полиномов
Умножение на p3 +p+1
Эквивалентные топологии:
unit delay
element
XOR-circuit
Data in
Encoded bits
x0
x1
xn-1
Note that

the tap order
is opposite in these
topologies

Форма ФИббоначи

Форма Галуа

Delay element

Элемент задержки

Слайд 42

Умножение по шагам
Генераторный полином
Инф. слово
Кодовое слово
x0
x1
x3

Слайд 43

Деление полиномов
d(x) = dn xn +dn-1 xn-1+ …+ d1 x +d0

g(x) = gr xr +gr xr-1 + … + g1 x +g0

Внутренние сумматоры

Слайд 44

Деление полиномов
Внешние сумматоры

Слайд 45

Пример
Схема деления на полином
g(x) = x6 +x5 +x4 +x3 + 1

над GF(2)

Слайд 46

Кодер систематического циклического кода

Слайд 47

Кодер систематического кода
a
Проверочные
Кодовое слово
Обратная связь
Буфер
Вход

Слайд 48

Кодер систематического кода по h(x)
1
2
h0

Слайд 49

Кодирование циклическим кодом путем задания корней всех кодовых полиномов
Кодирование предполагает

переход в соответствующее расширенное поле GF(pm). Условие, что все кодовые полиномы делятся на порождающий многочлен g(x), означает, что все полиномы слов кода должны принимать нулевое значение на корнях полинома g(x).

Слайд 50

Кодирование

Слайд 51

Пример
Пример. Построить проверочную матрицу циклического кода с параметрами (15, 11), используя

метод задания корней кодовых слов.

Слайд 52

Решение.
Определим полином f = x15 – 1. Разложим данный полином

на множители, применив оператор:
> Factor((x^15 – l)) mod 2;
(x^4 + x + 1)*(x^2 + x + 1)*(x^4 + x^3 + x^2 + x + 1)*(x^4 + x^3 + 1)*(x + 1)=
=(x4 + x + 1)(x2 + x + 1)(x4 + x3 + x2 + x + 1)(x4 + x3 + 1)(x + 1).

Слайд 53

Выберем из полученного результата полином g(x) = (x4 + x +

1).
Используя оператор irreduc( x^4 + x + 1), убедимся, что данный полином неприводимый и может служить в качестве полинома для построения поля GF(24).

Слайд 54

Определим примитивный элемент поля
> alias (alpha = RootOf(Z^4 + Z +

1) mod 2):
и построим элементы поля
> for i to 2^4-2 do powers[i] := evala (alpha^(i – 1)) mod p; od:

Слайд 55

Найдем корни полинома (x4 + x + 1) в расширенном поле

путем разложения полинома на элементарные множители:
> Factor(g, alpha) mod 2;
(x + alpha + 1)*(x + alpha)*(x + alpha^2 + 1)*(x + alpha^2)

Слайд 56

Таким образом, корнями полинома (x4 + x + 1) являются следующие

элементы поля:
.

Слайд 57

Используя выражение для H и представляя корни β как вектор столбцы,

после соответствующих упрощений получим

Слайд 58

Слайд 59

Циклические коды

Содержание

Циклические коды (ЦК)Подкласс линейных кодов Кодирование и декодирование основано на: 1.

Определение.Линейный (n, k)-код C над полем Fq называется циклическим, если из

Циклический блоковый кодсссссс======)1101( )1011( )0111( )1110()1101()4()3()2()1(Пример

ЦК - полиномы Алгебраическая структура Кодовые слова представляются как многочлены от

Генераторный полиномВажным свойством циклических кодов является то, что все кодовые слова-полиномы

Генераторная матрицаГенераторная матрица кода представляется как матрица размером (k×n) следующего видаСтроки

ПримерЦиклический код Хэмминга (7, 4, 3) задается порождающим полиномом g(x) =

Пример РешениеОбратимся к полиномам для систематического кодированияxm mod g(x), m = n

Требования к порождающему полиному :1. g(x) должен быть ненулевым; 2. вес

Факторизация бинома ( x n – 1) Разложим бином ( x

Проверочный многочлен h(x)Разобьем факторизованное множество на два непересекающихся подмножеств – Jg

Проверочный многочлен h(x)Если полином g(x) - порождающий, то любое кодовое слово

Проверочная матрицаПроверочная матрица циклического кода C имеет видили

Соотношение степенейДля циклического кода число информационных символов k и число проверочных

ПримерПостроить циклический код над GF(2) длины n = 31 с числом

Пример

Пример

Пример

Проверочная матрица

Сравнительный анализ

Вычисление синдрома

Вычисление синдрома

Кодирование циклических кодов Кодирование с помощью порождающего полинома g(x). Несистематическое кодированиеСистематическое

Систематическое кодирование Полином кодового слова c(x) находится с помощью соотношенияc(x) =

ПримерДля систематического циклического кода Хэмминга (7, 4) генераторный полином равенНайти кодовое

Решение

Порождающая и проверочная матрицыНайдем матрицы G и H, соответственно.Несистематическая формаПреобразуем матрицу:

Кодирование циклическим кодом с помощью проверочного многочлена h(x)Систематическое кодирование низкоскоростным циклическим

Умножение и деление полиномов Умножениеa(x) = ak xk +ak-1 xk-1+ …+

Схемы умноженияВнешние сумматорыВнутренние сумматорыD – элемент задержки на такт

ПримерСхема умножения на полином h(x) = x6 + x5 +x4 +x3

Умножение полиномовУмножение на p3 +p+1Эквивалентные топологии:unit delay elementXOR-circuitData inEncoded bitsx0x1xn-1Note that

Умножение по шагамГенераторный полиномИнф. словоКодовое словоx0x1x3

Деление полиномовd(x) = dn xn +dn-1 xn-1+ …+ d1 x +d0

Деление полиномовВнешние сумматоры

ПримерСхема деления на полиномg(x) = x6 +x5 +x4 +x3 + 1

Кодер систематического циклического кода

Кодер систематического кодаaПроверочныеКодовое словоОбратная связьБуферВход

Кодер систематического кода по h(x)12h0

Кодирование циклическим кодом путем задания корней всех кодовых полиномов Кодирование предполагает

Кодирование

ПримерПример. Построить проверочную матрицу циклического кода с параметрами (15, 11), используя

Решение. Определим полином f = x15 – 1. Разложим данный полином

Выберем из полученного результата полином g(x) = (x4 + x +

Определим примитивный элемент поля> alias (alpha = RootOf(Z^4 + Z +

Найдем корни полинома (x4 + x + 1) в расширенном поле

Таким образом, корнями полинома (x4 + x + 1) являются следующие

Используя выражение для H и представляя корни β как вектор столбцы,

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

Циклические коды (ЦК)
Подкласс линейных кодов
Кодирование и декодирование основано на:
1.

Определение.
Линейный (n, k)-код C над полем Fq называется циклическим, если из

Циклический блоковый код
с
с
с
с
с
с
=
=
=
=
=
=
)
1101
(

)
1011
(

)
0111
(

)
1110
(
)
1101
(
)
4
(
)
3
(
)
2
(
)
1
(
Пример

ЦК - полиномы Алгебраическая структура
Кодовые слова представляются как многочлены от

Генераторный полином
Важным свойством циклических кодов является то, что все кодовые слова-полиномы

Генераторная матрица
Генераторная матрица кода представляется как матрица размером (k×n) следующего вида
Строки

Пример
Циклический код Хэмминга
(7, 4, 3)
задается порождающим полиномом
g(x) =

Пример Решение
Обратимся к полиномам для систематического кодирования
xm mod g(x), m = n

Требования к порождающему полиному :
1. g(x) должен быть ненулевым;
2. вес

Факторизация бинома ( x n – 1)
Разложим бином ( x

Проверочный многочлен h(x)
Разобьем факторизованное множество на два непересекающихся подмножеств – Jg

Проверочный многочлен h(x)
Если полином g(x) - порождающий, то любое кодовое слово

Проверочная матрица
Проверочная матрица циклического кода C имеет вид
или

Соотношение степеней
Для циклического кода число информационных символов k и число проверочных

Пример
Построить циклический код над GF(2) длины n = 31 с числом

Кодирование циклических кодов Кодирование с помощью порождающего полинома g(x).
Несистематическое кодирование
Систематическое

Систематическое кодирование
Полином кодового слова c(x) находится с помощью соотношения
c(x) =

Пример
Для систематического циклического кода Хэмминга (7, 4) генераторный полином равен
Найти кодовое

Порождающая и проверочная матрицы
Найдем матрицы G и H, соответственно.
Несистематическая форма
Преобразуем матрицу:

Кодирование циклическим кодом с помощью проверочного многочлена h(x)
Систематическое кодирование низкоскоростным циклическим

Умножение и деление полиномов
Умножение
a(x) = ak xk +ak-1 xk-1+ …+

Схемы умножения
Внешние сумматоры
Внутренние сумматоры
D – элемент задержки на такт

Пример
Схема умножения на полином
h(x) = x6 + x5 +x4 +x3

Умножение полиномов
Умножение на p3 +p+1
Эквивалентные топологии:
unit delay
element
XOR-circuit
Data in
Encoded bits
x0
x1
xn-1
Note that

Умножение по шагам
Генераторный полином
Инф. слово
Кодовое слово
x0
x1
x3

Деление полиномов
d(x) = dn xn +dn-1 xn-1+ …+ d1 x +d0

Деление полиномов
Внешние сумматоры

Пример
Схема деления на полином
g(x) = x6 +x5 +x4 +x3 + 1

Кодер систематического кода
a
Проверочные
Кодовое слово
Обратная связь
Буфер
Вход

Кодер систематического кода по h(x)
1
2
h0

Кодирование циклическим кодом путем задания корней всех кодовых полиномов
Кодирование предполагает

Пример
Пример. Построить проверочную матрицу циклического кода с параметрами (15, 11), используя

Решение.
Определим полином f = x15 – 1. Разложим данный полином

Определим примитивный элемент поля
> alias (alpha = RootOf(Z^4 + Z +