- •Основные параметры помехоустойчивых кодов.
- •Коды с общей проверкой на чётность и коды с повторениями: их корректирующие способности, описание с помощью матриц, алгоритмы кодирования и декодирования.
- •Итеративные прямоугольные и треугольные коды: их корректирующие способности, описание с помощью матриц, алгоритмы кодирования и декодирования.
- •Группы и их основные свойства. Смежные классы.
- •Поле Галуа. Свойства конечных полей.
- •Расширенное поле Галуа. Вычисления в конечных полях.
- •Неравномерные эффективные коды. Проблема декодирования. Вектор Крафта.
- •Основные информационные характеристики источника сообщений. Коды Шеннона—Фано.
- •Сжатие информации кодами Хаффмана.
- •Алгоритм арифметического кодирования информации, пример.
- •Алгоритм арифметического декодирования информации, пример.
- •Словарные методы кодирования. Метод Зива—Лемпела.
- •17) Общие сведения о линейных кодах.
- •18) Описание линейных блоковых кодов при помощи матриц: формирование проверочной матрицы и порождающей матрицы.
- •19) Декодирование линейных кодов: декодирование методом максимального правдоподобия.
- •20) Декодирование кодов Хэмминга. Понятие синдрома
- •21) Декодирование линейных кодов: мажоритарное декодирование.
- •22) Коды Хэмминга, модификации кодов, формирование.
- •23) Декодирование кодов Хэмминга, области применения данных кодов.
- •24) Описание циклических кодов с помощью матриц.
- •25) Декодирование циклических кодов.
- •26) Описание циклических кодов с помощью полиномов.
- •27) Кодирование информации циклическими кодами.
- •28) Параметры и построение кодов Рида–Маллера.
Поле Галуа. Свойства конечных полей.
Конечное поле (поле Галуа) – конечное множество с двумя определенными на нем операциями, сложения и умножения, в котором определены правила для выполнения арифметических операций, содержащее q элементов и обозначаемое GF(q).
Свойства конечного поля:
1. Может образовывать абелевую группу по сложению.
2. Поле замкнуто относительно умножения и множество не нулевых элементов образует
абелевую группу по умножению.
3. Выполняется правило ассоциативности, коммутативности и дистрибутивности для любого
элемента поля.
4. Поле всегда содержит мультипликативную единицу и аддитивную единицу, для любого
элемента поля.
5. Для любого элемента поля существует обратный элемент по сложению и обратный элемент
по умножению.
Конечное поле существует в случае, если число элементов поля является простым числом или степенью простого числа.
Наименьшее поле является двоичным полем, т.е. q = 2 и содержит элементы 0, 1:
GF (2) = {0, 1}
Для выполнения вычитания или деления необходимо найти соответственный обратный элемент, а
затем выполнить сложение или умножение. Например:
GF (5) GF (7)
3-4=(3+1)mod5=4 2-4=(2+3)mod7=5
3/4=(3*4)mod5=2 5/6=(5*6)mod7=2
Для сложения и умножения обратный элемент находить не требуется.
Поле обладает всеми свойствами кольца, а так же обладает следующим свойством: в поле всегда возможно сокращение, представляющее собой некоторую форму деления и означает, что если a*b=c*b=,то a=c.
Примитивным элементом поля Галуа называется некий элемент α , такой, что все элементы поля могут быть представлены в виде степени этого элемента, за исключением нуля. GF (5)={0,1,2,3,4} GF (5)={0,1,2,3,4,5,6}
α=2 α=3
т.к. =2, =4, =3, =1 (mod 5) т.к. =3, =2, =6, =4, =5, =1 (mod 7)
Пример.
Требуется определить все элементы, входящие в GF(5), и представить таблицы сложения и умножения в данном поле.
GF(5)={0,1,2,3,4}
Расширенное поле Галуа. Вычисления в конечных полях.
Расширенное поле Галуа (GF( )) – конечное множество, которое образуется как система вычетов по двойному модулю f (x),p и элементами такого поля являются полиномы степени не выше n −1 и с коэффициентами GF(p).
GF( )= {0, 1, x, x +1}
Неравномерные эффективные коды. Проблема декодирования. Вектор Крафта.
В связи с тем, что при кодировании неравновероятных сообщений равномерные коды обладают большой избыточностью, было предложено использовать для кодирования неравномерные коды, длительность кодовых комбинаций согласована с вероятностью выпадения различных букв.
Методы эффективного кодирования основаны на принципах:
укрупнения сообщений или предсказания для уменьшения избыточности, вызванной корреляцией между сообщениями
применения неравномерного кода для уменьшения избыточности, вызванной неравной вероятностью появления сообщений.
Проблема декодирования неравномерного кода:
Если источник производит буквы с фиксированной во времени скоростью и если необходимо передавать закодированные символы с фиксированной во времени скоростью, то неравномерный код приводит к проблеме ожидающей очереди. Когда источник выдаёт редкую букву, производиться длинное кодовое слово и ожидающая очередь увеличивается.
Вектор Крафта:
Вектор (L1, L2,…, Lk) состоит из неуменьшающихся положительных целых чисел, называется вектором Крафта. Для него выполняется неравенство – неравенство Крафта:
2-L1+2-L2+…+2-Lk<=1.