Информацию-сохранение конечного порядка

Допустим, что система сохраняющих машин используется для кодирования и декодирования.  «Кодер» принимает входную последовательность и производит выходную последовательность, которая передается «декодеру». Понятно, что если кодер – информацию сохраняющий, то его входная последовательность может быть восстановлена из выходной последовательности так же хорошо, как и начальное и конечное состояния. Главное отступление в таком процессе заключается в факте, что информация относительно конечного состояния может быть передана кодером только после передачи всей информации. Отсюда следует, что вся информация должна быть записана в буфер перед началом процесса декодирования. Так как передаваемая последовательность может быть произвольно большой, информацию сохраняющая машина не может применяться на практике. С учетом этих ограничений перейдем к рассмотрению машин, для которых нет необходимости буферизовать полную информацию, но где процесс декодирования может начинаться только когда известно начальное состояние и длина входной последовательности.

Определение. 5 Машина называется (информацию) сохраняющей конечного порядка, если знание исходного состояния и первых µ выходных символов достаточно чтобы однозначно определить первый входной символ.

Знание начального состояния и первого входного символа достаточно, чтобы определить следующее состояние и  второй входной символ может быть вычислен при использовании (µ+1)-го выходного символа  и т.д.. Число µ, которое определяет задержку при декодировании входных символов, является порядком сохранения, если µ есть наименьшее целое, удовлетворяющее приведенному выше определению так, что если для некоторого исходного состояния и последовательности из (µ-1) выходных символов, существует минимум две возможных входных последовательностей, которые отличаются разными значениями исходного входного символа.

Простейший пример информацию содержащей машины конечного порядка – первого порядка, где первый входной символ может быть определен из знания исходного состояния и первого выходного символа. Очевидно, что декодирование производится без задержки для этого класса машин. В качестве примера примем машину Table 5. Поскольку для каждого состояния выход связан 0-преемник по выходу от выхода 1-преемника, знание начального состояния и первого выходного символа достаточно, чтобы определить первый входной символ. Например, если исходное состояние А, и если выход равен 1, то можно однозначно определить, что на вход был подан 0.

Содержание раздела

---

---