Слайд 2
![Примеры использования линейных кодов Пример 1. Протокол передачи данных по](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-1.jpg)
Примеры использования линейных кодов
Пример 1. Протокол передачи данных по телефонному каналу
ISDN-D, в котором используется формат передачи данных LAPD.
1 2 1(2) max 260 2 1
Слайд 3
![Примеры использования линейных кодов F=01111110 (flag) А – поле адреса](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-2.jpg)
Примеры использования линейных кодов
F=01111110 (flag)
А – поле адреса (address)
С поле команд
(control)
I –информационное поле (information)
FCS – проверочные разряды (frame check sequence)
Общая длина 266х8=21128 бит, проверочных – 16 бит
1 2 1(2) max 260 2 1
Слайд 4
![Примеры использования линейных кодов Пример 2. Протокол передачи данных в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-3.jpg)
Примеры использования линейных кодов
Пример 2. Протокол передачи данных в 802.3 CSMA/CD
для передачи данных в локальных сетях связи (LAN)
7
1
2(6)
2(6)
65-1518
4
Слайд 5
![Линейные циклические коды Циклические коды интенсивно изучаются, так как: Циклические](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-4.jpg)
Линейные циклические коды
Циклические коды интенсивно изучаются, так как:
Циклические коды обладают
богатой алгебраической структурой, что используется в различных приложениях.
Для циклических кодов чрезвычайно кратко формулируются технические требования (спецификации).
Циклические коды легко реализуются с помощью сдвиговых регистров.
Многие практически важные коды являются циклическими.
Слайд 6
![Линейные циклические коды Линейный (n,k)-код С называется циклическим, если циклический](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-5.jpg)
Линейные циклические коды
Линейный (n,k)-код С называется циклическим, если циклический сдвиг любого
кодового слова из С также принадлежит С:
Слайд 7
![Реализация циклического сдвига Циклический сдвиг реализуется с помощью регистра сдвига длины n с обратной связью:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-6.jpg)
Реализация циклического сдвига
Циклический сдвиг реализуется с помощью регистра сдвига длины n
с обратной связью:
Слайд 8
![Реализация циклического сдвига Регистр сдвига на такте 1 Регистр сдвига на такте 2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-7.jpg)
Реализация циклического сдвига
Регистр сдвига на такте 1
Регистр сдвига на такте 2
Слайд 9
![Замечания Для задания произвольного кода из 2k слов длины n](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-8.jpg)
Замечания
Для задания произвольного кода из 2k слов длины n необходимо выписать
все 2k кодовых слов длины n.
Для задания линейного кода из 2k слов длины n достаточно выписать k базисных слов длины n (порождающая матрица).
Для задания линейного циклического кода из 2k слов длины n достаточно выписать одно кодовое слово.
Слайд 10
![Представление кодовых слов в виде кодовых многочленов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-9.jpg)
Представление кодовых слов в виде кодовых многочленов
Слайд 11
![Представление кодовых слов в виде многочленов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-10.jpg)
Представление кодовых слов в виде многочленов
Слайд 12
![Действие циклического сдвига на многочлен](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-11.jpg)
Действие циклического сдвига на многочлен
Слайд 13
![Сложение и умножение многочленов по модулю](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-12.jpg)
Сложение и умножение многочленов по модулю
Слайд 14
![Пример](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-13.jpg)
Слайд 15
![Пример](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-14.jpg)
Слайд 16
![Пример](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-15.jpg)
Слайд 17
![Действие циклического сдвига на многочлен](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-16.jpg)
Действие циклического сдвига на многочлен
Слайд 18
![Циклический сдвиг многочлена на i позиций](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-17.jpg)
Циклический сдвиг многочлена на i позиций
Слайд 19
![Пространство слов длины n – множество многочленов степени Циклический код длины n – подмножество многочленов степени](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-18.jpg)
Пространство слов длины n – множество многочленов степени
Циклический код длины n
– подмножество многочленов степени
Слайд 20
![Важные теоремы Теорема 1. Циклический код содержит единственный кодовый многочлен](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-19.jpg)
Важные теоремы
Теорема 1. Циклический код содержит единственный кодовый многочлен минимальной степени.
Теорема
2.Если – кодовый многочлен минимальной степени, то его младший коэффициент
Теорема 3.Пусть -кодовый многочлен минимальной степени. Многочлен является кодовым многочленом тогда и только тогда, когда он кратен
Слайд 21
![Порождающий многочлен Пусть -кодовый многочлен минимальной степени, этот многочлен называется](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-20.jpg)
Порождающий многочлен
Пусть -кодовый многочлен минимальной степени, этот многочлен называется порождающим многочленом.
Базис (n,k)- кода: к базисных многочлена
Степень порождающего многочлена
Слайд 22
![Теоремы о порождающем многочлене Теорема1. Порождающий многочлен циклического кода делит](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-21.jpg)
Теоремы о порождающем многочлене
Теорема1. Порождающий многочлен циклического кода делит без остатка
многочлен .
Теорема 2. Если некоторый многочлен -степени n-k делит многочлен без остатка, то порождает циклический (n,k)-код.
Слайд 23
![Пример Разложение](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-22.jpg)
Слайд 24
![Различные циклические коды](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-23.jpg)
Различные циклические коды
Слайд 25
![Кодирование Кодирование циклического кода – умножение информационного многочлена на порождающий многочлен](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-24.jpg)
Кодирование
Кодирование циклического кода – умножение информационного многочлена на порождающий многочлен
Слайд 26
![Циклический (7,4)-код Хэмминга](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-25.jpg)
Циклический (7,4)-код Хэмминга
Слайд 27
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-26.jpg)
Слайд 28
![Циклический (7,4)-код Минимальный вес (7,4)-кода равен 3, код исправляет 1 ошибку](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-27.jpg)
Циклический (7,4)-код
Минимальный вес (7,4)-кода равен 3, код исправляет 1 ошибку
Слайд 29
![Замечания (1) По сравнению с линейными, циклические коды редки. Например,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-28.jpg)
Замечания (1)
По сравнению с линейными, циклические коды редки. Например, существует порядка
300000 линейных двоичных (7,3)-кодов, но только два из них являются циклическими.
Слайд 30
![Замечания (2) Тривиальные двоичные циклические коды. Код без информации –](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-29.jpg)
Замечания (2)
Тривиальные двоичные циклические коды.
Код без информации – код из
нулевого слова.
Код с повторением – код состоящий из двух слов: 00…0 и 11…1.
Код с проверкой на четность – код из слов четного веса.
Код без проверки – код из всех слов длины n.
В некоторых случаях (например n = 19), не существуют циклические коды, кроме описанных выше четырех кодов.
Слайд 31
![Порождающая матрица циклического кода](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-30.jpg)
Порождающая матрица циклического кода
Слайд 32
![Проверочный многочлен циклического кода Так как порождающий многочлен циклического кода](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-31.jpg)
Проверочный многочлен циклического кода
Так как порождающий многочлен циклического кода делит без
остатка многочлен то
Многочлен h(x) – проверочный многочлен
Слайд 33
![Проверочная матрица циклического кода Всякое кодовое слово можно представить как Тогда поэтому](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-32.jpg)
Проверочная матрица циклического кода
Всякое кодовое слово можно представить как
Тогда
поэтому
Слайд 34
![Проверочная матрица циклического кода Поэтому коэффициенты при степенях x старше k-1 равны 0. Тогда](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-33.jpg)
Проверочная матрица циклического кода
Поэтому коэффициенты при степенях x старше k-1 равны
0.
Тогда
Слайд 35
![Проверочная матрица циклического кода](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-34.jpg)
Проверочная матрица циклического кода
Слайд 36
![Порождающий многочлен дуального кода](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/408389/slide-35.jpg)
Порождающий многочлен дуального кода