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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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