ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ

Основные определения и понятия темы

Алфавит, слово, длина слова, кодирующая функция, декодирующая функция, сообщение, код сообщения, m-ичное кодирование, взаимно-однозначное кодирование, алфавитное кодирование, элементарный код, алфавитный код, префикс слова, постфикс слова, префиксная схема кодирования, кодирование с минимальной избыточностью, самокорректирующиеся коды..

Основные теоремы и утверждения темы

Алгоритм распознавания взаимной однозначности декодирования, теорема редукции, алгоритм построения кода с минимальной избыточностью (алгоритм Хаффмена), алгоритм Фано, алгоритм построения и декодирования кодов Хемминга.

Рекомендуемая литература

1. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992.

2. Левенштейн В. И. Элементы теории кодирования. – В. сб. Дискретная математика и математическая кибернетика. Т. 1. / Под общей редакцией С. В. Яблонского и О. Б. Лупанова. – М.: Наука, 1974. – С. 207-305.

Задание 3.1. Выяснить, является ли кодирование со схемой взаимно однозначным. Если нет, то указать слово, декодируемое неоднозначно:

1. : , , , , , , ;

2. : , , , , , , ;

3. : , , , , , ;

4. : , , , , , ;

5. : , , , , , , ;

6. : , , , , ;

7. : , , , , , ;

8. : , , , , , , ;

9.

10. ;

11. ;

12. ;

13.

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 3.2.Построить схему оптимального префиксного алфавитного кодирования по методу Хаффмена для распределения вероятностей появления букв алфавита в сообщении при -ичном кодировании.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 3.3. Дано распределение вероятностей появления букв алфавита в сообщении. Построить схему алфавитного кодирования по алгоритму Фано.

1. ;

2. ;

3. ;

4. ;

5.

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 3.4. Построить по методу Хэмминга код сообщения .

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 3.5.По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения . Было получено кодовое слово . Восстановить слово .

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .