ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.03.2024
Просмотров: 57
Скачиваний: 0
СОДЕРЖАНИЕ
Количество информации в сигнале при наличии помех
Передача информации по дискретному каналу
Кодирование информации (сообщений) в дискретном канале.
Алгоритмы эффективного кодирования
Возможность кодирования в условиях шумов
Концепция построения помехозащищенного кода.
Представление линейных кодов в матричном виде
Построение систематического кода с помощью генераторного многочлена
Математическое представление операции сдвига кодовой комбинации
Пусть: .
Сдвиг кодовой комбинации влево на разрядов можно записать как:
, где
, если степень не превосходит ,
- в обратном случае.
для :
Учтем, что
Или, используя терминологию умножения по модулю , имеем:
Где
Рассмотрим задачу выделения циклических кодов из всего множества (кольца) n-символьных кодовых комбинаций. Итак,
-
В множестве существует подмножество , элементы которых связаны свойством цикличности.
-
В теории кодирования доказывается, что подмножества характеризуются тем, что они кратны некоторым многочленам . Данные подмножества называют идеальными, порождаемыми .
-
Если разделить все элементы на , то для элементов идеала остатки от деления будут равны «0», а для всех остальных элементов будут получаться остатки , причем число различных остатков будет определяться видом .
-
Множество можно разложить на смежные классы по идеалу , причем в качестве образующих элементов смежных классов будут выступать .
-
В каждом смежном классе будут собираться те многочлены, которые при делении на , будут давать одинаковый остаток.
Сопоставить с разложением групповых кодов на смежные классы с порождающими элементами в виде векторов ошибок.
Теперь встает вопрос: как выбрать , чтобы он порождал циклический код? Имеем: все элементы циклического кода кратны (индекс убираем), порождающий многочлен длинного кода.
В качестве порождающей матрицы кода, содержащей линейно независимых строк, можно взять и результаты его циклического сдвига.
Старшая степень равна для канонической формы. Учитывая, что математическая модель сдвига есть
то для того, чтобы элементы циклического кода делились на без остатка, необходимо и достаточно, чтобы был делителем ( ).
Имеем: процедура циклического кодирования
На приемной стороне имеем:
прием без искажений,
прием с искажениями.
Таким образом, при декодировании мы должны выполнить определение остатков.
где - операция взятия остатка от деления. Ошибка будет обнаружена, если не делится на без остатка.
Корректирующая способность кода будет тем выше, чем больше разных остатков образуется при делении элементов на .
Наибольшее количество остатков (равное ) от деления дают неприводимые многочлены. Существуют таблицы для разных степеней .
Выбор степени порождающего многочлена:
Условие исправления одиночной ошибки ( :
Для исправления большей кратности ошибок используется правило Хемминга.
Пусть – позволяет исправлять ошибки кратности . Тогда для исправления ошибок кратности :
( увеличивается на 2) – дополнительная проверка на четность.
Выбор подходящего неприводимого многочлена степени :
Часто удобно использовать следующую методику: если , то многочлен равен произведению всех неприводимых многочленов, степени которых являются делителями числа от 1 до .
Пример:
. Один из сомножителей степени может быть взят в качестве . для найденного значения следует выбирать наиболее короткий многочлен, но при этом число его ненулевых членов должно быть не меньше .
Необходимо убедиться, что выбранный многочлен
дает необходимое число разных остатков для реализации исправления нужного числа ошибок.
Пример: (15,11)
Если взять , то остатков будет всего пять, так как входит в разложение не только , но и . Полученный по данной процедуре код будет не систематическим. Для получения систематического разделимого кода используют следующий прием:
-
– безызбыточный код, -символьный.
-
степень
-
Разделим
-
Степень остатка не превосходит
Построение систематического кода с помощью генераторного многочлена
Рекуррентная формула/ алгоритм вычисления по -символьной информационной комбинации ( ) значений проверочных символов ):
Алгоритм вычисления используется при .
Пример: – сообщение. Код циклический, (7,4). Выберем
Определим генераторный многочлен:
Т.е. ;
Сообщение