- •Основные параметры помехоустойчивых кодов.
- •Коды с общей проверкой на чётность и коды с повторениями: их корректирующие способности, описание с помощью матриц, алгоритмы кодирования и декодирования.
- •Итеративные прямоугольные и треугольные коды: их корректирующие способности, описание с помощью матриц, алгоритмы кодирования и декодирования.
- •Группы и их основные свойства. Смежные классы.
- •Поле Галуа. Свойства конечных полей.
- •Расширенное поле Галуа. Вычисления в конечных полях.
- •Неравномерные эффективные коды. Проблема декодирования. Вектор Крафта.
- •Основные информационные характеристики источника сообщений. Коды Шеннона—Фано.
- •Сжатие информации кодами Хаффмана.
- •Алгоритм арифметического кодирования информации, пример.
- •Алгоритм арифметического декодирования информации, пример.
- •Словарные методы кодирования. Метод Зива—Лемпела.
- •17) Общие сведения о линейных кодах.
- •18) Описание линейных блоковых кодов при помощи матриц: формирование проверочной матрицы и порождающей матрицы.
- •19) Декодирование линейных кодов: декодирование методом максимального правдоподобия.
- •20) Декодирование кодов Хэмминга. Понятие синдрома
- •21) Декодирование линейных кодов: мажоритарное декодирование.
- •22) Коды Хэмминга, модификации кодов, формирование.
- •23) Декодирование кодов Хэмминга, области применения данных кодов.
- •24) Описание циклических кодов с помощью матриц.
- •25) Декодирование циклических кодов.
- •26) Описание циклических кодов с помощью полиномов.
- •27) Кодирование информации циклическими кодами.
- •28) Параметры и построение кодов Рида–Маллера.
Основные параметры помехоустойчивых кодов.
Основание кода q-число элементарных символов выбранных для передачи сообщений. Пример для двоичного и троичного кода
Длина кода n – число символов, выбранных для передачи сообщений. Коды бывают блоковые и непрерывные. Блоковые коды в свою очередь делятся на равномерные, в которых длина кода постоянна n – const, и неравномерные где n = var.
В непрерывных кодах, к которым относятся широко используемые свёрточные коды, сообщения передаются без деления на блоки (у этих кодов роль длины n, на которой контролируется определённое число ошибок, играет кодовое ограничение).
Число информационных позиций в коде, выбранных для передачи данных: k.
Число проверочных (контрольных) позиций в коде: r = n-k.
Мощность кода M- число кодовых комбинаций, выбранных для передачи сообщений. В полном безызбыточном коде ,в помехоустойчивом (избыточном) коде . Очевидно, что всегда . Пример: Код с q=2, n=3 число кодовых комбинаций , кодов равно ,
Скорость передачи кода R=k/n характеризует качество кода.
Кратность контролируемой ошибки t ( ).
Кодовое расстояние кода d характеризует возможности кода по контролю ошибок.
Вероятность (частота) ошибки на бит : p.
На практике коды обозначают (n;k) или (n;k;d).
Коды с общей проверкой на чётность и коды с повторениями: их корректирующие способности, описание с помощью матриц, алгоритмы кодирования и декодирования.
Коды с проверкой на чётность являются линейными блочными кодами и строятся путём добавления к сообщению одного символа, который зависит от всех символов сообщения: , где . Обозначается (n,n-1,2), как видно кодовое расстояние d = 2, следовательно число ошибок которые можно обнаружить равно 1 (d-1), исправить 0 ((d-1)/2).
Порождающая матрица кода имеет n-1строк и n столбцов:
G =
Проверочная матрица:
H =
Декодирование кода основано на проверки чётности числа единиц в принятой последовательности. То есть если при сложении по модулю 2 всех символов результат равен 0 то последовательность правильная, если 1 то произошла ошибка. Но заметим что данный метод позволяет обнаружить только нечётное количество ошибок.
Коды с повторениями - коды, в которых один заданный информационный символ повторяется n раз. , где a- информационный символ b- проверочные которые повторяют информационный.
Обозначается (n,1,n), как видно кодовое расстояние d = n, следовательно число ошибок которые можно обнаружить равно (d-1), исправить ((d-1)/2).
Порождающая матрица состоит из одной строки:
G =
Следовательно код с повторениями имеет всего 2 слова одно содержит только нули, другое только единицы.
Проверочная матрица:
H =
Имеет n-1 строк и n столбцов и указывает, что сумма первого и любого другого символов кодового слова должна равняться 0. Число избыточных символов в коде достигает нижней границы, следовательно, коды нечетной длины с повторением относятся к совершенным. Проверочная матрица кода (n,n-1,2) с простой проверкой на четность совпадает с порождающей матрицей кода с повторением (n,1,n), а порождающая матрица первого кода подобна проверочной матрице второго. Такие коды называются дуальными.