Образец решения задачи об однозначности кодирования. Образец решения задачи об однозначности кодирования (Критерий Маркова)
 Скачать 81.5 Kb.
|
|
Образец решения задачи об однозначности кодирования (Критерий Маркова) Пусть схема кодирования задана следующей таблицей:
Обозначим элементарные коды:  ,  ,  ,  ,  Выпишем все нетривиальные разложения каждого элементарного кода (см. конспект), подписав внизу, какую роль играет тот или иной элемент разложения (начало, конец, элементарный код). Напоминаю, что начало  не должно заканчиваться на какой-либо элементарный код, а конец  – начинаться на него.     Составим множество  всех начал разложений (не повторяя в перечне одних и тех же элементов): Составим множество  всех концов  разложений: Найдём множество  : Построим ориентированный граф с вершинами, соответствующими элементам множества М. Ребро, идущее из одной вершины этого графа в другую, имеет место тогда и только тогда, когда существует нетривиальное разложение с началом, соответствующим первой вершине  и концом, соответствующим второй вершине . Над каждым ребром мы подписываем промежуточные коды, стоящие между началом и концом разложения (если они там имеются).        Поскольку построенный граф содержит цикл, проходящий через вершину, соответствующую пустому слову, кодирование не является однозначным. В разложении, соответствующим нижнему ребру, никаких промежуточных кодов нет, потому мы над ним ничего не пишем. Как предъвить пример неоднозначно раскодируемого слова? Для этого нужно, идя по циклу, проходящему через пустое слово, начиная с него, выписать все коды, которые встречаются по пути. В данном случае это будет  Получив это слово, нетрудно найти два разных его раскодирования:  что согласно таблице соответствует   что согласно таблице соответствует  . |