Практическая работа по теории информации. Циклические коды

Июль 24, 2022

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

Содержание

2. Циклические коды
4. Цикломатические классы
5. Цикломатические классы
6. Циклический код Циклический код – такой групповой код, все базовые комбинации которого могут быть получены из
7. Кодовые комбинации В теории циклических кодов принято записывать кодовые комбинации в виде полинома некоторой фиктивной переменной
8. Пример Представить в виде полинома кодовую комбинацию a ≈ 1011101.
9. Задание Задание 1. а) Представить в виде полинома кодовую комбинацию a ≈ 1001001. б) Представить в
10. Порождающий полином Неприводимым называется многочлен, который не может быть представлен в виде произведения многочленов низших степеней,
11. Порождающая матрица Можно записать порождающую матрицу циклического кода в следующем виде: p(x) p(x) · x −
12. Порождающий полином Комбинация p(x) называется порождающей (генераторной) комбинацией. Для построения циклического кода достаточно верно выбрать p(x).
13. Степень порождающего полинома Выполнение условия 4 приводит к тому, что все рабочие кодовые комбинации циклического кода
14. Примеры порождающих полиномов
15. Разрешенные кодовые комбинации Пусть задан полином P(x) = ar−1 xr + ar−2 xr−1 + … +
16. Алгоритм Умножаем многочлен исходной кодовой комбинации на xr: Ak−1(x) · xr Определяем проверочные разряды, дополняющие исходную
17. Пример Закодировать комбинацию вида 1101, что соответствует A(х) = х3 + х2 + 1. Определяем число
18. Задание2 а) Закодировать комбинацию вида 110. б) Закодировать комбинацию вида 11010. в) Закодировать комбинацию вида 1010.
19. Определение ошибки Пусть имеем n-элементные комбинации (n = k + r) тогда: Получаем остаток от деления
20. Определение ошибки Опять сравниваем полученный остаток с R0(x). Если они равны, то ошибки во втором разряде.
21. Пример Полином g(x) = 1 + x2 + x3 генерирует бинарный (7,4)-циклический код, dmin = 3
22. Задание 3 Принятая кодовая комбинация ЦК(7,4) имеет вид Bi'(X)=1101110. Определить и исправить ошибку в B i'
23. Задания по вариантам
24. Учебные материалы http://yourtutor.narod.ru/cyclic/CyclicCodes.htm http://informkod.narod.ru/5_5item.htm http://peredacha-informacii.ru/ustrojstva-rekurrentnyh-kodov.htmlhttp://peredacha-informacii.ru/ustrojstva-rekurrentnyh-kodov.html http://estohard.narod.ru/InfoTeory/1/15/153.htm
26. Скачать презентацию

Слайд 2

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

Слайд 3

Слайд 4

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

Слайд 5

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

Слайд 6

Циклический код
Циклический код – такой групповой код, все базовые комбинации

которого могут быть получены из одной путем циклического сдвига ее элементов.
Циклический сдвиг кодовой комбинации – перемещение ее элементов справа налево без нарушения порядка их следования, так что крайний левый элемент занимает место крайнего правого.

Слайд 7

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

полинома некоторой фиктивной переменной x:
где ai – значение символа кодовой комбинации на позиции i при нумерации справа налево; xi – 1 – фиктивная переменная в степени номера позиции i без единицы.

Слайд 8

Пример
Представить в виде полинома кодовую комбинацию a ≈ 1011101.

Слайд 9

Задание
Задание 1.
а) Представить в виде полинома кодовую комбинацию a ≈ 1001001.
б)

Представить в виде полинома кодовую комбинацию a ≈ 1101101.
в) Представить в виде полинома кодовую комбинацию a ≈ 1010111.

Слайд 10

Порождающий полином
Неприводимым называется многочлен, который не может быть представлен в виде

произведения многочленов низших степеней, т. е. такой многочлен делится только на самого себя или на единицу и не делится ни на какой другой многочлен. На такой многочлен делится без остатка двучлен xn + 1. Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов.

Слайд 11

Порождающая матрица
Можно записать порождающую матрицу циклического кода в следующем виде:

p(x) p(x) · x − C2 (xn − 1)
V = p(x) · x2 − C3 (xn − 1) … p(x) · xm−1 − Cm (xn − 1) ,
где p(x) — исходная кодовая комбинация, на базе которой получены все остальные (m − 1) базовые комбинации, Ci = 0 или Ci = 1 («0», если результирующая степень полинома p(x) · xi не превосходит (n − 1), «1», если превосходит).

Слайд 12

Порождающий полином
Комбинация p(x) называется порождающей (генераторной) комбинацией.
Для построения циклического

кода достаточно верно выбрать p(x). Затем все остальные кодовые комбинации получаются такими же, как и в групповом коде.
Порождающий полином должен удовлетворять следующим требованиям:
p(x) должен быть ненулевым;
вес p(x) не должен быть меньше минимального кодового расстояния: v(p(x)) ≥ dmin;
p(x) должен иметь максимальную степень k (k — число избыточных элементов в коде);
p(x) должен быть делителем полинома (xn − 1).

Слайд 13

Степень порождающего полинома
Выполнение условия 4 приводит к тому, что все рабочие

кодовые комбинации циклического кода приобретают свойство делимости на p(x) без остатка. Циклический код — код, все рабочие комбинации которого делятся на порождающий без остатка.
Для определения степени порождающего полинома можно воспользоваться выражением r ≥ log2(n+1), где n — размер передаваемого пакета за раз, т. е. длина строящегося циклического кода.

Слайд 14

Примеры порождающих полиномов

Слайд 15

Разрешенные кодовые комбинации
Пусть задан полином P(x) = ar−1 xr + ar−2 xr−1 + … + 1, определяющий корректирующую способность

кода и число проверочных разрядов r, а также исходная комбинация простого k-элементного кода в виде многочлена Ak−1(x).
Требуется определить разрешенную кодовую комбинацию циклического кода (n, k).

Слайд 16

Алгоритм
Умножаем многочлен исходной кодовой комбинации на xr: Ak−1(x) · xr
Определяем проверочные разряды,

дополняющие исходную информационную комбинацию до разрешенной, как остаток от деления полученного в предыдущем пункте произведения на порождающий полином: Ak−1(x) · xr ⁄ Pr(x) ⇒ R(x)
Окончательно разрешенная кодовая комбинация циклического кода определится так: An−1(x) = Ak−1(x) · xr + R(x)
Для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая комбинация — разрешенная, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о том, что принятая комбинация содержит ошибки. По виду остатка (синдрома) можно в некоторых случаях также сделать вывод о характере ошибки, ее местоположении и исправить ошибку.

Слайд 17

Пример
Закодировать комбинацию вида 1101, что соответствует A(х) = х3 + х2 + 1.
Определяем число контрольных символов r = 3.

Из таблицы возьмем многочлен P(х) = х3 + х + 1, т. е. 1011.
Умножим A(х) на хr:
A(x) · xr = (x3 + x2 + 1) · x3 = x6 + x5 + x3 ⇒ 11010000
Разделим полученное произведение на образующий полином g(х):
A(x) · xr ⁄ P(x) = (x6 + x5 + x3) ⁄ (х3 + х + 1) = х3 + х2 + х + 1 + 1 ⁄ (х3 + х + 1) ⇒ 1111 + 001 ⁄ 1011
При делении необходимо учитывать, что вычитание производится по модулю 2. Остаток суммируем с h(х) · хr. В результате получим закодированное сообщение:
F(x) = (x3 + x2 + 1) · (x3 + x + 1) = (x3 + x2 + 1) · x3 + 1 ⇒ 1101001
В полученной кодовой комбинации циклического кода информационные символы A(х) = 1101, а контрольные R(х) = 001. Закодированное сообщение делится на образующий полином без остатка.

Слайд 18

Задание2
а) Закодировать комбинацию вида 110.
б) Закодировать комбинацию вида 11010.
в) Закодировать комбинацию

вида 1010.
г) Закодировать комбинацию вида 10111.

Слайд 19

Определение ошибки
Пусть имеем n-элементные комбинации (n = k + r) тогда:
Получаем остаток от деления

Е(х) соответствующего ошибке в старшем разряде [1000000000], на порождающий полином Pr(x): E1(x) ⁄ Pr(x) = R0(x)
Делим полученный полином Н(х) на Pr(x) и получаем текущий остаток R(x).
Сравниваем R0(x) и R(x).
Если они равны, то ошибка произошла в старшем разряде.
Если нет, то увеличиваем степень принятого полинома на x и снова проводим деления: H(x) · x ⁄ Pr(x) = R(x)

Слайд 20

Определение ошибки
Опять сравниваем полученный остаток с R0(x).
Если они равны, то

ошибки во втором разряде.
Если нет, то умножаем Н(х) · х2 и повторяем эти операции до тех пор, пока R(x) не будет равен R0(x).
Ошибка будет в разряде, соответствующем числу, на которое повышена степень Н(х), плюс один.
Например: H(x) · x3 ⁄ Pr(x) = R0(x)

Слайд 21

Пример
Полином g(x) = 1 + x2 + x3 генерирует бинарный (7,4)-циклический

код, dmin = 3 (т.е. 1-ошибку исправляет). Рассмотрим кодовое слово 1 + x + x5 = (1 + x + x2) g(x). Пусть после передачи многочлен R(x) = 1 + x + x5 + x6 был получен.
Декодируем его. Разделим R(x) на g(x) для нахождения синдрома, R(x) = (x3 + 1)g(x) + (x + x2),
так S(x) = x + x2.Так как вес S(x) > 1 (= t), вычислим синдром s1(x) * xr(x). Так как S(x) = 2 = n - k - 1, умножаем S(x) на x и делим на g(x), что дает s1(x) = 1.
Поскольку вес 1, маска ошибки e(x) = x7-1(s1,0) = x6(1000000) = x6.
Так как n = 7 все ошибки веса 1 имеют циклический сдвиг на шесть 0's и 6 > k = 4, исправляются все единичные ошибки..

Слайд 22

Задание 3
Принятая кодовая комбинация ЦК(7,4) имеет вид Bi'(X)=1101110. Определить и исправить

ошибку в B i' (X),если она имеется.

Задание 4

Выполнить кодирование чисел(даны в 10-й с.с.) циклическим кодом с заданным порождающим полиномом(дан в 8-й с.с.)
по вариантам

Слайд 23

Задания по вариантам

Слайд 24

Учебные материалы
http://yourtutor.narod.ru/cyclic/CyclicCodes.htm
http://informkod.narod.ru/5_5item.htm
http://peredacha-informacii.ru/ustrojstva-rekurrentnyh-kodov.htmlhttp://peredacha-informacii.ru/ustrojstva-rekurrentnyh-kodov.html
http://estohard.narod.ru/InfoTeory/1/15/153.htm

Практическая работа по теории информации. Циклические коды

Содержание

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

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

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

Циклический код Циклический код – такой групповой код, все базовые комбинации

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

ПримерПредставить в виде полинома кодовую комбинацию a ≈ 1011101.

ЗаданиеЗадание 1.а) Представить в виде полинома кодовую комбинацию a ≈ 1001001.б)

Порождающий полином Неприводимым называется многочлен, который не может быть представлен в виде

Порождающая матрица Можно записать порождающую матрицу циклического кода в следующем виде:

Порождающий полином Комбинация p(x) называется порождающей (генераторной) комбинацией. Для построения циклического

Степень порождающего полиномаВыполнение условия 4 приводит к тому, что все рабочие

Примеры порождающих полиномов

Разрешенные кодовые комбинации Пусть задан полином P(x) = ar−1 xr + ar−2 xr−1 + … + 1, определяющий корректирующую способность

АлгоритмУмножаем многочлен исходной кодовой комбинации на xr: Ak−1(x) · xr Определяем проверочные разряды,

Пример Закодировать комбинацию вида 1101, что соответствует A(х) = х3 + х2 + 1.Определяем число контрольных символов r = 3.

Задание2а) Закодировать комбинацию вида 110.б) Закодировать комбинацию вида 11010.в) Закодировать комбинацию

Определение ошибкиПусть имеем n-элементные комбинации (n = k + r) тогда: Получаем остаток от деления

Определение ошибкиОпять сравниваем полученный остаток с R0(x). Если они равны, то

ПримерПолином g(x) = 1 + x2 + x3 генерирует бинарный (7,4)-циклический

Задание 3Принятая кодовая комбинация ЦК(7,4) имеет вид Bi'(X)=1101110. Определить и исправить

Задания по вариантам

Учебные материалыhttp://yourtutor.narod.ru/cyclic/CyclicCodes.htm http://informkod.narod.ru/5_5item.htmhttp://peredacha-informacii.ru/ustrojstva-rekurrentnyh-kodov.htmlhttp://peredacha-informacii.ru/ustrojstva-rekurrentnyh-kodov.html http://estohard.narod.ru/InfoTeory/1/15/153.htm

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

Циклический код
Циклический код – такой групповой код, все базовые комбинации

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

Пример
Представить в виде полинома кодовую комбинацию a ≈ 1011101.

Задание
Задание 1.
а) Представить в виде полинома кодовую комбинацию a ≈ 1001001.
б)

Порождающий полином
Неприводимым называется многочлен, который не может быть представлен в виде

Порождающая матрица
Можно записать порождающую матрицу циклического кода в следующем виде:

Порождающий полином
Комбинация p(x) называется порождающей (генераторной) комбинацией.
Для построения циклического

Степень порождающего полинома
Выполнение условия 4 приводит к тому, что все рабочие

Разрешенные кодовые комбинации
Пусть задан полином P(x) = ar−1 xr + ar−2 xr−1 + … + 1, определяющий корректирующую способность

Алгоритм
Умножаем многочлен исходной кодовой комбинации на xr: Ak−1(x) · xr
Определяем проверочные разряды,

Пример
Закодировать комбинацию вида 1101, что соответствует A(х) = х3 + х2 + 1.
Определяем число контрольных символов r = 3.

Задание2
а) Закодировать комбинацию вида 110.
б) Закодировать комбинацию вида 11010.
в) Закодировать комбинацию

Определение ошибки
Пусть имеем n-элементные комбинации (n = k + r) тогда:
Получаем остаток от деления

Определение ошибки
Опять сравниваем полученный остаток с R0(x).
Если они равны, то

Пример
Полином g(x) = 1 + x2 + x3 генерирует бинарный (7,4)-циклический

Задание 3
Принятая кодовая комбинация ЦК(7,4) имеет вид Bi'(X)=1101110. Определить и исправить

Учебные материалы
http://yourtutor.narod.ru/cyclic/CyclicCodes.htm
http://informkod.narod.ru/5_5item.htm
http://peredacha-informacii.ru/ustrojstva-rekurrentnyh-kodov.htmlhttp://peredacha-informacii.ru/ustrojstva-rekurrentnyh-kodov.html
http://estohard.narod.ru/InfoTeory/1/15/153.htm