25. Коды с минимальной избыточностью (коды Хаффмана), метод построения. Самокорректирующиеся коды (коды Хэмминга), метод построения.

Алгоритм Хаффмана — адаптивный жадный алгоритмоптимальногопрефиксногокодированияалфавита с минимальной избыточностью. В настоящее время используется во многих программах сжатия данных.

Пример:

префиксная =>однозначно декодируемая

Пусть известны частоты встречаемости букв a₁, a₂, a₃, a₄:

p₁=0,4 p₁l₁=0,4*1=0,4

p₂=0,25 p₂ l₂=0,25*2=0,5

p₃=0,2 p₃ l₃=0,2*3=0,6

p₄=0,15 p₄ l₄=0,15*3=0,45

l_ср=0,4+0,5+0,6+0,45=1,95

Избыточность схемы – число, вычисляемое по формуле l_ср= p₁l₁+ p₂l₂+…+ p_rl_r.

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

Замечание. Для каждого конкретного текста коэффициент удлинения может отличаться от величины l_ср и в большую, и в меньшую сторону.

Рассмотрим задачу построения кода с минимальной избыточностью в двухбуквенном кодирующем алфавите.

Пример2:

Заданы частоты встречаемости букв исходного алфавита:

p₁=0,4

p₂=0,25

p₃=0,2

p₄=0,1

p₅=0,05

Необходимо построить схему с минимальной избыточностью. B={0,1}

Упорядочиваем в порядке убывания частоты.

Строим дерево с 5-ю концевыми вершинами (количество букв в исходном алфавите). Идем по дереву: шаг направо 1, налево – 0.

Получаем схему:

l_ср=2,1

Самокорректирующиеся коды Хэмминга.

Помехоустойчивый код

В данном случае произошло одиночное искажение, но может быть и больше ошибок. Рассмотрим одиночные ошибки, т.е. инвертирование одного бита в кодовом слове.

Техническая защита – защищать каналы связи.

???????????? дальше

26. Недетерминированные двухполюсные источники, замкнутые множества состояний. Задача синтеза автоматов-распознавателей.

Задача синтеза автомата-распознавателя.

1 этап: строим источник, распознающий данный язык.

2 этап: источник превращаем в автомат.

Источник – воображаемое устройство, которое не может работать самостоятельно (непредсказуем).

Теорема. Если язык L распознается источником, имеющим n состояний, то обязательно найдется автомат, распознающий этот же язык и имеющий не более, чем 2ⁿ состояний.

Следствие. Источники могут распознавать только регулярные языки.

Замкнутое состояние – множество состояний недетерминированного источника, если для каждого состояния V, принадлежащего этому множеству, ему также будут принадлежать все другие состояния, в которые можно попасть по пустой дуге из данного состояния V.

Двухполюсником называется недетерминированный источник, у которого есть только одна вершина-источник и только одна вершина-сток.

Типы операций над двухполюсниками:

1. Последовательное соединение. Новый двухполюсник распознает язык L₁*L₂

2. Параллельное соединение. Полученный двухполюсник распознает сумму языков L₁ и L₂

3. Итерация. Распознает язык L₁*

Для любого регулярного языка можно построить двухполюсник, распознающий этот язык, используя только эти три операции.