1.4. АЛФАВИТНОЕ ПРЕДСТАВЛЕНИЕ И ПРЕОБРАЗОВАНИЕ ИНФОРМАЦИИ

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

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

В наиболее общем виде преобразование цифровой алфавитной информации может быть задано следующим образом. Пусть — два конечных алфавита. Обозначим через соответственно совокупности всех слов конечной длины в алфавитах X и Y. Если начальная информация записывается в алфавите X, а конечная — в алфавите то произвольное преобразование информации есть отображение множества на множество

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

Пример. X — множество букв русского алфавита. Y — множество номеров таких букв. Преобразование из в сводится к замене каждой буквы слова, принадлежащего ее номером. Ясно, что такое преобразование будет эквивалентным.

Пример. X — множество, состоящее из цифр 0, 1, 2, 9 и знака сложения. Y — множество натуральных чисел. Преобразование из в сводится к замене слова а — его суммой. Ясно, что задаваемое таким образом преобразование не является эквивалентным, так как, например, может быть представлено и как т. е. различные слова из могут дать одно и то же слово в

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

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

Пример. Преобразование из в сводится к замене каждой буквы из X комбинацией символов 0 и 1. Такую замену можно осуществить, например, следующим образом:

Легко заметить, что с помощью простейших эквивалентных преобразований, информацию, заданную в любом конечном алфавите, можно записать в двухбуквенном алфавите. Такой вариант получил название двоичного, а его буквы обозначаются нулем и единицей. Указанное преобразование выполняется следующим образом: ищется такое натуральное число чтобы число различных слов длины в двоичном алфавите превышало или было равно числу различных букв исходного алфавита; после этого каждая из букв исходного алфавита заменяется словом длины в двоичном алфавите так, чтобы различным буквам исходного алфавита соответствовали различные слова.

Поскольку число различных слов длины в двоичном алфавите равно то для возможности выполнения указанного требования достаточно выбрать так, чтобы выполнялось соотношение

Кодирование информации в двоичном алфавите неоднозначно. Более того, для любого исходного алфавита существует бесконечное множество таких преобразований. Все эти преобразования носят специальное название двоичного кодирования исходной информации и широко используются в вычислительной технике. В качестве начального может быть выбран не обязательно двоичный, а любой другой конечный алфавит, состоящий более чем из одной буквы. Правила кодирования при этом сохраняются. Нужно лишь вместо неравенства использовать неравенство где — число букв в выбранном алфавите.

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

ряда нулей и единиц другого ряда нулей и единиц, отличных от первого либо числом символов, либо их взаимным расположением, либо тем и другим вместе.