1. Задача теории кодирования. Общая схема передачи дискретной информации. Алфавитное и равномерное кодирование. Систематические коды. Кодирование и декодирование.

2. Примеры кодов: код с проверкой на четность; код Хэмминга; код с повторением.

3. Кодовое расстояние Хэмминга и его связь с корректирующей способностью.

4. Верхняя граница Хэмминга.

5. Нижняя граница Гилберта.

6. Определение линейного кода. Порождающая матрица линейного кода. Приведенно-ступенчатая форма порождающей матрицы.

7. Проверочная матрица линейного кода и ее построение по приведенно-ступенчатой форме порождающей матрицы этого кода.

8. Вычисление минимального веса линейного кода по порождающей матрице этого кода.

9. Обобщенный q-ичный код Хэмминга.

10. Нижняя граница Варшамова-Гилберта

11. Методы декодирования линейных кодов.

12. Теорема кодирования Шеннона.

13. Определение циклического кода. Порождающий многочлен циклического кода.

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

15. Способ кодирования циклического кода по порождающему многочлену без нахождения порождающей матрицы кода.

16. Двойственный код к циклическому коду и его свойства. Проверочная матрица циклического кода.

17. Методы декодирования циклических кодов.

18. Двоичный и троичный коды Голея.

19. Декодирование кода Голея с помощью метода покрывающих многочленов.

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

21. Построение проверочной матрицы циклического кода по корням его порождающего многочлена.

22. Построение циклического кода, минимальное расстояние которого не меньше заданного числа.

23. Определение БЧХ-кодов. Построение совершенного циклического кода, исправляющего одиночные ошибки.

24. Основные этапы декодирования БЧХ-кодов.

25. *Итеративный алгоритм Бэрлекэмпа.

26. Нахождение числа информационных символов в БЧХ-кодах.

27. Обобщенные коды Рида-Соломона. Альтернантные коды.

28. Коды Гоппы.

29. *Криптосистема МакЭлайса

30. *Теорема о несуществовании асимптотически хорошего семейства примитивных кодов БЧХ в узком.

31. *Теорема о существовании асимптотически хорошего семейства длинных альтернантных кодов.

32. Каскадные коды. Код Юстесена.

33. Обобщенные коды Рида-Маллера.

34. Расширенные евклидово-геометрические коды и пороговое декодирование.

35. Методы мажоритарного декодирования

36. *Многочлен Мэттсона-Соломона

37. *Определение с помощью многочлена Мэттсона-Соломона минимального расстояния кода Голея.

38. Сверточные коды. Метод порогового декодирования.

39. Теорема Мэсси и Робинсона. Построение сверточных кодов с помощью простых совершенных разностных множеств.

40. Древовидные коды и принцип последовательного декодирования.

41. Алгоритм Фано.

42. *Среднее число операций при последовательном декодировании с помощью алгоритма Фано.

43. *Верхняя и нижняя оценки Витерби вероятности ошибки для алгоритма декодирования по максимуму правдоподобия для сверточных кодов.

СПИСОК ЛИТЕРАТУРЫ.

1.     Ф.Дж.Мак-Вильямс, Н.Дж.А.Слоэн, Теория кодов, исправляющих ошибки, Москва, “Связь”, 1979.

2.     Р.Лидл, Г.Нидеррайтер, Конечные поля, Т. 1,2, Москва, “Мир”, 1988.

3.     Т.Касами, Н.Токура, Е.Ивадари, Я.Инагаки, Теория кодирования, Москва, “Мир”, 1978.

4.     У.Петерсон, Э.Уэлдон, Коды, исправляющие ошибки, Москва, “Мир”, 1976.

5.     Э.Берлекэмп, Алгебраическая теория кодирования, Москва, “Мир”, 1971.

6.     К.Э.Шеннон, Работы по теории информации и кибернетики, Москва, “Иностранная литература”, 1963.

Наверх