Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

АЛФАВИТНОЕ КОДИРОВАНИЕ

ЗАДАНИЕ 8 Однозначность декодирования

Теория кодирования - раздел дискретной математики, имеющий обширную область приложений. Кодирование буквально пронизывает сегодняшний мир информационных технологий и является центральным вопросом при решении самых разных практических задач хранения, защиты, передачи и обработки данных. Основы теории кодирования заложил в 1948 г. К. Шеннон. Им были сформулированы и доказаны две фундаментальные теоремы (для канала без помех и канала с помехами), которые определили развитие теории кодирования в последующие годы. К настоящему времени наиболее полно исследованы алфавитные коды, им посвящена глава 3 учебного пособия. Здесь рассматриваются две основные задачи алфавитного кодирования: распознавание однозначного декодирования и оптимальное кодирование.

Цель данного задания: изучение, разработка и программирование критериев однозначного декодирования алфавитных кодов.

Основные понятия и обозначения

Пусть А = ь ..., ап} - конечное непустое множество, или алфавит. Элементы алфавита называются буквами. Конечная последовательность

букв алфавита А называется словом, а число | а | — его длиной. Пустое слово (обозначается Л) - это слово, в котором нет букв, т. е. | Л | = 0.

Конкатенацией слов oil и <Х2 называется слово а^. Заметим, что аЛ = Да = а, т. е. если слову а предшествует или следует за ним пустое слово, то в результате конкатенации получаем то же самое слово а. Множество всех слов в алфавите А, включая пустое слово, принято обозначать А*.

Рассмотрим другой алфавит В = {Ь, ..., bq} с множеством В* всех его слов р. Пусть S с А*. Всякая функция ср: S -> В*, ставящая в соответствие каждому слову а е S слово Р - ф(а) е В*, называется кодированием. При этом слова из S называются сообщениями, а их образы - кодами сообщений. Алфавит А называется исходным алфавитом, а В - кодирующим алфавитом. Обратная функция ср ', если она существует, называется декодированием. В зависимости от числа букв в кодирующем алфавите различают двоичное, троичное и в общем случае g-ичное кодирование. Так, при двоичном кодировании в качестве кодирующего алфавита чаще всего выступает множество В = {0, 1}.

Кодирование ф может сопоставлять код Р всему сообщению а как единому целому или же строить р из кодов букв, входящих в сообщение а. В последнем случае речь идет об алфавитном (или по- буквенном) кодировании. Это простейший способ кодирования.

Алфавитное кодирование задается схемой

где я, е А, Р, е В*, / = 1, ..., п, которая устанавливает соответствие между буквами алфавита А и некоторыми словами из В*.

Множество кодов букв {рь ..., Р„} - {ф(<яf), ..., ф(я„)} обозначается ф(А) и называется множеством элементарных кодов (или алфавитным кодом).

При алфавитном кодировании код сообщения - конкатенация кодов букв сообщения, т. е. каждому слову

ставится в соответствие слово

Если | pi | = ... = | Р„ I, то алфавитный код cp(A) = {pu ..P„} называется равномерным, в противном случае - неравномерным. Число i = | Pi | = ... = | Р„ | называется разрядностью равномерного алфавитного кода (р(А) = {рь ..., р„}.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>