Кодирование с помощью порождающего полинома

Содержание

Слайд 2

Пример умножения полиномов Пример. Перемножить два полинома A и G. K

Пример умножения полиномов

Пример. Перемножить два полинома A и G.
K = A

· G = (1 + х3)( 1 + х + х3).
Слайд 3

Узел умножения полиномов K = A · G = (1 +

Узел умножения полиномов
K = A · G = (1 + х3)(

1 + х + х3).
Слайд 4

Пример деления полиномов В результате получен код полинома К = 1101 и нулевой остаток.

Пример деления полиномов

В результате получен код полинома К = 1101 и

нулевой остаток.
Слайд 5

Узел деления полиномов Узел деления полиномов К = АG. А = К/G

Узел деления полиномов

Узел деления полиномов К = АG. А = К/G

Слайд 6

Пример умножения полиномов

Пример умножения полиномов

Слайд 7

Пример умножения полиномов

Пример умножения полиномов

Слайд 8

Пример деления полиномов

Пример деления полиномов

Слайд 9

Поля Галуа. Выполнение арифметических операций б) перемножим полиномы: 5 · 7

Поля Галуа. Выполнение арифметических операций

б) перемножим полиномы:
5 · 7 = (х2 +

1)( х2 + х +1) =
= х4 + х3 + х2 + х2 + х + 1 =
= х4 + х3 + х + 1 =
= 110112 = 2710.
Слайд 10

Поля Галуа. Порождающий полином Продолжим вычисление произведения 5 и 7, добавив

Поля Галуа. Порождающий полином

Продолжим вычисление произведения 5 и 7, добавив слагаемые

х2 + х + х2 + х, не меняющее уравнение:
5 · 7 =
= х4 + х3 + х + 1 =
= (х4 + х2 + х) + (х3 + х + 1) + х2 + х =
= x(х3 + х + 1) + (х3 + х + 1) + х2 + х =
= х2 + х = 1102 = 610.
Таким образом, результат умножения 5 · 7 = 6 принадлежит полю GF(23).
Слайд 11

Поля Галуа. Порождающий полином Такой же результат можно получить, вычислив остаток

Поля Галуа. Порождающий полином

Такой же результат можно получить, вычислив остаток от

деления полинома, полученного при умножении, на порождающий полином
(х3 + х + 1):
Вывод: полученное значение произведения двух чисел 5 и 7 также принадлежит полю GF(23).
Слайд 12

Поля Галуа. Таблица умножения Таблица умножения чисел от 1 до 7 (табл. 1).

Поля Галуа. Таблица умножения

Таблица умножения чисел от 1 до 7 (табл.

1).
Слайд 13

Поля Галуа. Таблица степеней Таблица степеней обладает цикличностью, т.е. «7» степень

Поля Галуа. Таблица степеней

Таблица степеней обладает цикличностью, т.е. «7» степень соответствует

«0», «8» – «1» и т.д. (табл. 2).
Слайд 14

Поля Галуа. Пример 2. Вычислить значение 52 в полиноминальной форме. 52

Поля Галуа.

Пример 2. Вычислить значение 52 в полиноминальной форме.
52

= (х2 + 1)2 = х4 + х2 + х2 + 1 = х4 + х2+ х + х2 + х + 1 =
= х(х3 + х + 1) + х2 + х + 1 = х2 + х + 1 = 1112 = 710.
При вычислении были добавлены значения х+х, а согласно определению х3 + х + 1 = 0.
Слайд 15

Поля Галуа Любой элемент поля можно выразить через степень примитивного полинома,

Поля Галуа

Любой элемент поля можно выразить через степень примитивного полинома, например:

5 = 26, 7 = 25. Рассмотрим примеры выполнения арифметических операций по таблице степеней.
Пример 3. Вычислить значение произведения двух чисел.
5·7 = 26 · 25 = 2(6+5) = 211 = 2(11 mod7)=24 = 6.
Слайд 16

Поля Галуа

Поля Галуа

 

Слайд 17

Поля Галуа GF(28) Согласно теории, i-й элемент поля Галуа – это

Поля Галуа GF(28)

Согласно теории, i-й элемент поля Галуа – это результат

возведения в i-ю степень некоторого примитивного элемента, в качестве которого обычно берется простое число 2, где i = 0…28 – 1.
Начиная i = 8, мы получим результат ,который уже выходит за пределы [0, 28 – 1] и здесь используется особый подход.
Слайд 18

Поля Галуа. GF(28) Правило первоначальной генерации поля:

Поля Галуа. GF(28)

Правило первоначальной генерации поля:

Слайд 19

Поля Галуа. GF(28) Правило построения поля: 0-й элемент поля это 1,

Поля Галуа. GF(28)

Правило построения поля:
0-й элемент поля это 1,
1-й элемент –

2,
а, начиная со 2-го элемента по 254-й элемент, элемент вычисляется как удвоенное значение предыдущего элемента, и если удвоение привело к числу, вышедшему заграницы 8-разрядов, то на него делается XOR с числом 28510 (11D16), наконец, последний 255-й элемент поля – 0.
Число 285 – это десятичное представление (11D в
16 – ричном представлении) так называемого неприводимого полинома x8+x4+x3+x2+1, с помощью которого и порождается первоначальное поле.
Слайд 20

Поля Галуа. GF(28) Символом обозначается операция XOR – побитовое сложение по

Поля Галуа. GF(28)

Символом обозначается операция XOR – побитовое сложение по модулю

2, а символом << обозначается логический сдвиг влево двоичного представления числа на указанное количество разрядов.
При этом биты, «вылезшие слева» из 8-разрядного байта, пропадают, а разряды, «освобождающиеся справа», заполняются нулями.
Сдвиг числа в двоичном представлении на один разряд влево– это эквивалентно удвоению числа.
Слайд 21

Поля Галуа. GF(28) Сгенерированное поле GF(28 ), содержит результаты возведения примитивного

Поля Галуа. GF(28)

Сгенерированное поле GF(28 ), содержит результаты возведения примитивного элемента

«2» во все степени, начиная с 0, заканчивая 255.
Слайд 22

Поля Галуа. GF(28) Вычисление значения 29 1 2 4 6 16

Поля Галуа. GF(28)

Вычисление значения 29
1 2 4 6 16 32 64 128 29 58…
----------------------------------------------------------------------------
128 64 32 16 8 4 2 1

1 0 0 0 0 0 0 0 = 128
1 0 0 0 0 0 0 0 0 - сдвиг
1 0 0 0 1 1 1 0 1 = 285
------------------------------------------------------------
1 1 1 0 1 = 29
Слайд 23

Поля Галуа. GF(28) Помимо основного поля в технологии кодирования важно также

Поля Галуа. GF(28)

Помимо основного поля в технологии кодирования важно также иметь

и так называемое обратное поле, позволяющее по заданному значению 2k выяснить степень k, в которое был возведен примитивный элемент 2, иными словами иметь таблицу логарифмов пооснованию2.
Обратное поле вычисляется следующим образом:
Слайд 24

Поля Галуа GF(28) Сгенерированное обратное поле GF-1(28), содержит логарифмы всех элементов,

Поля Галуа GF(28)

Сгенерированное обратное поле GF-1(28), содержит логарифмы всех элементов, начиная

с 0, заканчивая 255, по основанию примитивного элемента 2.
Слайд 25

Поля Галуа. Выполнение арифметических операций Определим четыре арифметические операции:

Поля Галуа. Выполнение арифметических операций

Определим четыре арифметические операции:

Слайд 26

Поля Галуа. Выполнение арифметических операций Операция деления:

Поля Галуа. Выполнение арифметических операций

Операция деления:

Слайд 27

Поля Галуа. Выполнение арифметических операций Возведение в степень: Особенности выполнения арифметических

Поля Галуа. Выполнение арифметических операций

Возведение в степень:
Особенности выполнения арифметических операций.
Сложение и вычитание

для поля GF(28) заменяется побитовым сложением по mod2.
Так как log(a ·b) = log a + log b и log (a/b) = log a - log b, то умножение (деление) сводится к вычислению log2 от операндов (по обратному полю Галуа), сложению (вычитанию) значений логарифмов и возведению в степень числа 2 суммы (разности) (по основному полю Галуа).
Слайд 28

Поля Галуа. Выполнение арифметических операций Примечания: Если сумма степеней больше или

Поля Галуа. Выполнение арифметических операций

Примечания:
Если сумма степеней больше или равна 255, то

из нее вычитается 255.
Если сумма степеней меньше 0, к ней прибавляется 255.
При вычислении произведения степеней за результат берется остаток произведения по mod2.
Слайд 29

Поля Галуа. Выполнение арифметических операций Пример 2. Выполнение условия а =

Поля Галуа. Выполнение арифметических операций

Пример 2. Выполнение условия а = (а/в) ·

в,
например при а = 7 и в = 3.
7 · 3 = 2^(log27 + log23) = 2^(198 + 25) = 2^(223) = 9.
9/3 = 2^(log29 – log23) =2^(223 - 25) – 2^(198) = 7.
Используем GF-1.
Слайд 30

Поля Галуа. Пример деления полиномов Пример 2. Разделить полином А(х) на

Поля Галуа. Пример деления полиномов

Пример 2. Разделить полином А(х) на полином g(х).
Делимое

А(х) = 4х4 ⊕ 2 х3 ⊕ х2
Делитель g(х) = х2 ⊕ 2 х ⊕ 2
Результат Q(х)
Остаток от деления R(х)
Слайд 31

Поля Галуа. Пример деления полиномов Первый шаг

Поля Галуа. Пример деления полиномов

Первый шаг

Слайд 32

Поля Галуа. Пример деления полиномов Второй шаг

Поля Галуа. Пример деления полиномов

Второй шаг

Слайд 33

Поля Галуа. Пример деления полиномов Третий шаг

Поля Галуа. Пример деления полиномов

Третий шаг

Слайд 34

Поля Галуа. Пример деления полиномов Проверка:

Поля Галуа. Пример деления полиномов

Проверка:

Слайд 35

Контрольные вопросы

Контрольные вопросы


- Предыдущая
Сепсис. Классификация и критерии диагностики сепсиса
Следующая -
Солнечная система в виртуальной реальности

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

Золотое Сечение
Правильные выпуклые многогранники
Положительные и отрицательные числа. Координатная прямая
Аттестационная работа. Методическая разработка по выполнению проекта «В стране задач»
Урок математики. (Часть 2. 1 класс)
Элементы линейной алгебры
Искусственный интеллект – наука и технология создания интеллектуальных машин
Внеклассное мероприятие по математике в 6 классе
Задания по математике (5 класс, часть 2)
Сложность вычислений
Умножение десятичных дробей на натуральное число
Деление десятичных дробей
Системы одновременных уравнений
Ортогональность системы тригонометрических функций
Системы линейных неравенств с одним неизвестным
Первый признак подобия треугольников
РАЗВИТИЕ ЛОГИЧЕСКОГО МЫШЛЕНИЯ-2
Умножение натуральных чисел и его свойства
Количественные методы педагогического исследования
Математика выборов
Урок №3. Полные квадратные уравнения (общая формула) Автор: Ильина Юлия Валерьевна ГБОУ лицей №373 «Экономический лицей»
Аттестационная работа. Математические исследования
Преобразование сумм тригонометрических функций в произведение
Детерминированные линейные модели с непрерывными переменными
Понятие одночлена. Стандартный вид одночлена
29 вересня - трагедія Бабиного Яру
Grafice ale functiilor si rolul derivatelor
Chiziqsiz temglamalar sistemasini taqribiy yechish usullari
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть