Алфавитное кодирование

Пусть даны алфавиты Â = Обозначим через S (Â) и S () множества всех непустых слов в этих алфавитах. Соответствие между буквами алфавита Â и некоторыми словами в алфавите :

а ₁ —

а ₂ —

… … …

а_r —

называют схемой. Тогда каждому слову ставится в соответствие слово – код слова . Слова называются элементарными кодами. В случае, если из текста ясно, о какой схеме идёт речь, то мы будем говорить: Код Если соответствие между словами и их кодами взаимнооднозначное, то возможно декодирование, т.е. восстановление по коду исходного сообщения В этом случае говорят, что алфавитное кодирование является взаимнооднозначным, однозначно декодируемым или разделимым. Возникает вопрос: возможно ли по схеме å узнать, обладает ли она свойством взаимной однозначности?

Пусть слово В имеет Тогда слово называется началом или префиксом слова В, а слово – концом или суффиксом слова В. При этом пустое слово Λ и само слово В считаются началами. Все начала и концы слова В, отличные от В и Λ, называются, собственными. Схема å обладает свойствам префикса (задаёт префиксный код), если никакой элементарный код не является префиксом другого элементарного кода.