Научни публикации 1
Научни публикации 2
Научни публикации 3
Научни публикации 4
Научни публикации 5
Попул. Публикации 1
Попул. Публикации 2
Пламен Сидеров
Диана Левченко
Азнив Каспарян
Мая Стоянова
Асен Божилов
Евгения Великова
Силвия Бумова
Теория на кодирането
| вид: | изборен | Курс 1, 2, 3, 4; летен семестър |
|---|---|---|
| хорариум: | 3 часа лекции + 0 часа семинар | |
| изисквания: | добро познаване на материала от курса "Линейна алгебра" | |
| специалност: | "Математика", "Математика и Информатика", "Информатика", "Приложна Математика" |
|
| преподавател: | доц. Евгения Великова | |
| разписание: | Курсът не се чете през този семестър. | |
Анотация
Курсът по теория на кодирането е уводен в теорията на
кодовете поправящи грешки. В него се излагат основните
параметри на шумозащитните кодове , които се използуват при
предаване на информация по канали с шум. Предимно се
изучават линейни кодове над крайни полета и някои от
най-използваните граници за параметрите на кодове,
разглеждат се основните алгоритми за кодиране и
декодиране. Изучават се и конкретните класове на едни от
най-често прилаганите кодове - симплекс кодове и кодове
Хеминг, кодове на Рид-Малер и мажоритарни алгоритми за
декодиране. Някои от основните свойства на полиноми над
крайни полета са застъпени в този курс, както и приложението
им при цикличните кодове над произволно крайно поле,
въвеждат се БЧХ кодовете и един алгебричен алгоритъм за
тяхното декодиране. Разглеждат се и матрици на Адамар и
свързаните с тях оптимални нелинейни двоични кодове на
Адамар, а така също съвършените линейно-двоичен и троичен
код на Голей, които са свързани с матриците на Адамар.
Конспект
- Предаване на информация по канал с шум. Типове канали и основни видове кодове. Двоичен симетричен канал.
- Разстояние на Хеминг. Декодиране по метода на максималното правдоподобие. Декодиране и вероятност за грешки.
- Двоичен линеен код - размерност, пораждаща матрица, минимално разстояние. Двоичен симплекс код.
- Проверочна матрица на двоичен линеен код, външно произведение на двоични вектори и дуален код. Код на Хеминг. Самодуални кодове,
- Съседни класове и синдроми при двоични линейни кодове. Декодиране на двоичен код чрез таблица на Слепян и чрез синдроми. Декодиране на кодовете на Хеминг.
- Теглови спектър на двоичен линеен код и вероятност за неоткрита грешка. Тъждество на Мак-Уилиамс за двоичен линеен код.
- Булеви функции. Кодове на Рид-Малер - размерност и пораждаща матрица.
- Минимално разстояние и дуален код на на кодовете на Рид-Малер. Геометрично представяне на кодовете на Рид-Малер.
- Декодиране на кодовете на Рид-Малер - декодер на Рид и постъпков мажоритарен декодер.
- Граница на Плоткин за нелинейни двоични кодове. Матрици на Адамар и кодове на Адамар. Двоичен код на Голей.
- Линейни кодове над крайно поле. Пораждаща матрица, минимално разстояние. Кодиране. Вътрешна произведение, проверочна матрица и дуален код.
- Съседни класове и лидери на линеен код. Граница на Плоткин и "Норсе" границата. Граница на Сингълтон и граница на Вааршамов-Джилберт.
- Остатъчен код. Граница на Грийсмер. Грийсмерови и оптимални кодове. Граница на Хеминг и съвършени линейни кодове.
- Основни методи за декодиране на линеен код - декодиране чрез стандартни масиви, декодиране чрез масиви, мажоритарно декодиране.
- Методи за получаване на кодове.
- Полиноми над крайно поле - основни свойства. Построяване на крайно поле.
- Циклични кодове. Пораждащ и проверочен полином.
- Кодиране на цикличен код. Декодер на Мегит.
- БЧХ граница. БЧХ кодове, кодове на Рид-Соломон - свойства.
- Алгоритъм на Питерсон - Горенщейн - Цирлер за декодиране на БЧХ кодове.
Литература
- Е. Великова-Бандова, Записки по кодиране - Двоични шумозащитни кодове, ISBN 954-16-0018-2, ФОИ-КОМЕРСЕ, София, 2001.
- Е. Великова-Бандова, Записки по кодиране - Циклични кодове, ISBN 954-16-0020-4, ФОИ-КОМЕРСЕ, София, 2001.
- Adàmek, J, Foundations of coding, A Wiley-Interscience Publication, 1991.
- Берлекэмп Э., Алгебраическая теoрия кодирования, "Мир", Москва, 1971.
- Додунеков, С., Денев Й., Кодиране на информацията, "Народна Просвета", 1985.
- MacWilliams F.J., Sloan N.J.A, The theory of error-correcting codes, North-Holland, Amsterdam, 1977.
- Тончев, В., Комбинаторни конфигурации - Дизайни кодове, графи, "Наука и Изкуство", София, 1984.