Помехоустойчивое кодирование Циклические коды – подкласс линейных кодов. - презентация

1 Помехоустойчивое кодирование Циклические коды – подкласс линейных кодов

2 Примеры использования линейных кодов Пример 1. Протокол передачи данных по телефонному каналу ISDN-D, в котором используется формат передачи данных LAPD (2) max FACIFCSF

3 Примеры использования линейных кодов F= (flag) А – поле адреса (address) С поле команд (control) I –информационное поле (information) FCS – проверочные разряды (frame check sequence) Общая длина 266х8=21128 бит, проверочных – 16 бит 1 2 1(2) max FACIFCSF

4 Примеры использования линейных кодов Пример 2. Протокол передачи данных в CSMA/CD для передачи данных в локальных сетях связи (LAN) 7 1 2(6) 2(6) Преамбула Разделитель Адрес получателя Адрес источника Данные Контроль четности

5 Линейные циклические коды Циклические коды интенсивно изучаются, так как: Циклические коды обладают богатой алгебраической структурой, что используется в различных приложениях. Для циклических кодов чрезвычайно кратко формулируются технические требования (спецификации). Циклические коды легко реализуются с помощью сдвиговых регистров. Многие практически важные коды являются циклическими.

6 Линейные циклические коды Линейный (n,k)-код С называется циклическим, если циклический сдвиг любого кодового слова из С также принадлежит С:

7 Замечание Для задания произвольного кода из 2 k слов длины n необходимо выписать все 2 k кодовых слов длины n. Для задания линейного кода из 2 k слов длины n достаточно выписать k базисных слов длины n (порождающая матрица). Для задания линейного циклического кода из 2 k слов длины n достаточно выписать одно ненулевое кодовое слово.

8 Реализация циклического сдвига Циклический сдвиг реализуется с помощью регистра сдвига длины n с обратной связью: …

9 Реализация циклического сдвига Регистр сдвига на такте 1 Регистр сдвига на такте 2 … …

10 Представление кодовых слов в виде кодовых многочленов

11 Представление кодовых слов в виде многочленов

12 Циклический сдвиг многочлена

13 Пример

14

15

16 Циклический сдвиг многочлена

17 Важные теоремы Теорема 1. Циклический код содержит единственный кодовый многочлен минимальной степени. Теорема 2.Если – кодовый многочлен минимальной степени, то его младший коэффициент Теорема 3.Пусть -кодовый многочлен минимальной степени. Многочлен является кодовым многочленом тогда и только тогда, когда он кратен

18 Порождающий многочлен Пусть -кодовый многочлен минимальной степени, этот многочлен называется порождающим многочленом. Пусть степень порождающего многочлена равна r. Базис подпространства С (порождающая матрица): Степень порождающего многочлена

19 Теоремы о порождающем многочлене Теорема1.Порождающий многочлен циклического кода делит без остатка многочлен. Теорема 2.Если некоторый многочлен - степени n-k делит многочлен без остатка, то порождает циклический (n,k)-код.

20 Кодирование Кодирование циклического кода – умножение информационного многочлена на порождающий многочлен

21 Циклический (7,4)-код Пример. (разложение )

22 инф.сл.кодовое сл.многочлен Заполните самостоятельно

23 Циклический (7,4)-код Минимальный вес (7,4)-кода равен 3, код исправляет 1 ошибку Это циклический код Хэмминга

24 Замечания (1) По сравнению с линейными, циклические коды редки. Например, существует линейных двоичных (7,3)-кодов, но только два из них являются циклическими.

25 Замечания (2) Тривиальные двоичные циклические коды. Код без информации – код из нулевого слова. Код с повторением – код состоящий из двух слов: 00…0 и 11…1. Код с проверкой на четность – код из слов четного веса. Код без проверки – код из всех слов длины n. В некоторых случаях (например n = 19), не существуют циклические коды, кроме описанных выше четырех кодов.

26 Порождающая матрица циклического кода

27 Проверочный многочлен циклического кода Так как порождающий многочлен циклического кода делит без остатка многочлен то Многочлен h(x) – проверочный многочлен

28 Проверочная матрица циклического кода Всякое кодовое слово можно представить как Тогда поэтому

29 Проверочная матрица циклического кода Поэтому коэффициенты при степенях x старше k-1 равны 0. Тогда

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

31 Порождающий многочлен дуального кода

32 Параметры циклического кода Хэмминга Длина кода Число информационных символов Минимальное расстояние - 3 Число исправляемых ошибок - 1