Синтез цифровых автоматов. Захаров Н.Г - 21 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

20
Если подобное отображение осуществляется каким-либо определенным объек-
том, то этот объект называется преобразователем информации. Например, обыкно-
венный радиоприемник, с информационной точки зрения, представляет собой преоб-
разователь информации, осуществляющий преобразование информации, заданной в
виде радиоволн, в информацию, задаваемую с помощью звуковых колебаний. Чело-
век, решающий какую-либо задачу, также может рассматриваться как преобразова-
тель информации: входной информацией в этом случае является условие задачи, а
выходной – ответ.
1.5.2. Преобразование алфавитной информации
В соответствии с высказанными ранее соображениями будем рассматривать
исключительно дискретно заданную алфавитную информацию и ее преобразования.
В наиболее общем виде преобразование алфавитной информации может
быть задано следующим образом. Пусть нам даны два конечных алфавита
Х = (х
1
, х
2
, ..., х
m
) и Y = (y
1
, y
2
, ..., y
n
). Обозначим через F = F(х
1
, ..., х
m
) совокупность
всех слов конечной длины в алфавите Х, а через G = G(y
1
,..., y
n
) – совокупность всех
слов конечной длины в алфавите Y. Если исходная информация записывается в алфа-
вите Х, а конечная информация – в алфавите Y, то произвольное преобразование ин-
формации ϕ будет представлять собой отображение множества F в множество G. В
дальнейшем мы будем рассматривать лишь детерминированные преобразования ин-
формации, при которых входное слово полностью определяет слово на выходе преоб-
разователя. Это требование есть ни что иное, как требование однозначности
отображения ϕ.
В самом общем случае целесообразно считать преобразование информации ϕ
частичным отображением. Иначе говоря, задавать отображение ϕ не обязательно на
всем множестве F, а лишь на части этого множества (не исключая, впрочем, случай
совпадения этой части со всем множеством F). Введение частичных отображений по-
зволяет вместо отображений одного множества слов в другое рассматривать лишь
отображения таких множеств в себя. Для этой цели достаточно ввести объединенный
алфавит Z = (х
1
, ..., х
m
, y
1
,..., y
n
) и множество Н = Н(х
1
, ..., х
m
, y
1
,..., y
n
) слов над этим
алфавитом. Теперь вместо отображения множества F в множество G можно рассмат-
ривать частичное отображение множества Н в себя. Это частичное отображение будет
определено для слов, состоящих только из букв х
1
, х
2
, ..., х
m
.
Однозначность отображения ϕ множества F в множество G не означает, вообще
говоря, однозначности обратного отображения ϕ
-1
. Если такая однозначность имеет
место, то отображение ϕ называется взаимно однозначным. В этом случае отображе-
ние ϕ осуществляет эквивалентное преобразование информации. В случае эквива-
лентного преобразования заключительная (выходная) информация полностью опре-
деляет исходную (входную) информацию.
Пример 1. Преобразование информации в произвольном конечном алфавите
заключается в зеркальном отображении слов: это преобразование эквивалентно.
Пример 2. В алфавите, состоящем из всех десятичных цифр и знака суммы, за-
дается отображение слов вида a + b, где а и b – целые числа, преобразуемые в сумму
этих двух чисел. Например, слово 2 + 5 преобразуется в слово 7.
Легко видеть, что это преобразование не эквивалентно, поскольку задание
суммы не определяет слагаемых.

Страницы