Синтез цифровых автоматов

     Подобно тому, как со всяким явлением в природе  или в обществе связана несущая этим явлением информация, взаимосвязь явлений приводит к понятию о преобразовании информации. Предположим, что любое явление á из некоторого класса А явлений влечет за собой некоторое определенное явление â из того же самого или любого другого класса В явлений. В таком случае говорят, что нам задано преобразование информации. Следовательно, с абстрактной точки зрения преобразование информации есть ни что иное, как отображение одного класса явлений в другой класс явлений. Стрелка «→» здесь служит в качестве знака преобразования информации, или, говоря иначе, в качестве обозначения отображения явления в явление. Если подобное отображение осуществляется каким-либо определенным объектом, то этот объект называется преобразователем информации. Например, обыкновенный радиоприемник, с информационной точки зрения, представляет собой преобразователь информации, осуществляющий преобразование информации, заданной в виде радиоволн, в информацию, задаваемую с помощью звуковых колебаний. Человек, решающий какую-либо задачу, также может рассматриваться как преобразователь информации: входной информацией в этом случае является условие задачи, а выходной – ответ. 

1.5. Преобразование алфавитной информации 

     В соответствии с высказанными ранее  соображениями будем рассматривать исключительно дискретно заданную алфавитную информацию и ее преобразования. В наиболее общем виде преобразование алфавитной информации может быть задано следующим образом. Пусть нам даны два конечных алфавита Х = (х1, х2, ..., хm) и Y = (y1, y2, ..., yn). Обозначим через F = F(х1, ..., хm) совокупность всех слов конечной длины в алфавите Х, а через G = G(y1,..., yn) – совокупность всех слов конечной длины в алфавите Y. Если исходная информация записывается в алфавите Х, а конечная информация – в алфавите Y, то произвольное преобразование информации ϕ будет представлять собой отображение множества F в множество G. В дальнейшем мы будем рассматривать лишь детерминированные преобразования информации, при которых входное слово полностью определяет слово на выходе преобразователя. Это требование есть ни что иное, как требование однозначности отображения.

     В самом общем случае целесообразно  считать преобразование информации частичным отображением. Иначе говоря, задавать отображение не обязательно на всем множестве F, а лишь на части этого множества (не исключая, впрочем, случай совпадения этой части со всем множеством F). Введение частичных отображений позволяет вместо отображений одного множества слов в другое рассматривать лишь отображения таких множеств в себя. Для этой цели достаточно u1074 ввести объединенный алфавит Z = (х1, ..., хm, y1,..., yn) и множество Н = Н(х1, ..., хm, y1,..., yn) слов над этим алфавитом. Теперь вместо отображения множества F в множество G можно рассматривать частичное отображение множества Н в себя. Это частичное отображение будет определено для слов, состоящих только из букв х1, х2, ..., хm. Однозначность отображения множества F в множество G не означает, вообще говоря, однозначности обратного отображения. Если такая однозначность имеет место, то отображение называется взаимно однозначным. В этом случае отображение ϕ осуществляет эквивалентное преобразование информации. В случае эквивалентного преобразования заключительная (выходная) информация полностью определяет исходную (входную) информацию. Преобразование информации в произвольном конечном алфавите заключается в зеркальном отображении слов: это преобразование эквивалентно. Пример 2. В алфавите, состоящем из всех десятичных цифр и знака суммы, задается отображение слов вида a + b, где а и b – целые числа, преобразуемые в сумму этих двух чисел. Например, слово 2 + 5 преобразуется в слово 7.Легко видеть, что это преобразование не эквивалентно, поскольку задание суммы не определяет слагаемых. Со всяким преобразованием информации связывается представление о его сложности. По критерию сложности целесообразно выделить простейшие преобразования информации. Простейшими или побуквенными, будем называть преобразования, заключающиеся в замене каждой буквы исходного алфавита некоторой определенной комбинацией букв нового алфавита, имеющего заранее фиксированную, одинаковую для всех букв длину. Пример 3. Исходная информация – произвольное слово в русском алфавите. Преобразование информации состоит в замене каждой буквы алфавита порядковым номером, записанным в десятичной системе счисления. При этом для соблюдения условия равенства длин комбинаций буквенного алфавита, представляющих буквы старого _________алфавита, необходимо первую букву обозначать комбинацией 01, вторую – 02 и т. д. В результате такого преобразования слово «дом» преобразуется в слово «051412». Это преобразование является не только простейшим, но и эквивалентным.

     Пример 4. Исходная информация – произвольное целое десятичное число (слово в алфавите, состоящем из десяти цифр 0, 1, 2, ..., 9). Преобразование информации состоит в замене каждой четной цифры нулем, а нечетной – единицей. Слово «125» при этом преобразуется в слово «101», слово «0342» – в слово 0100 и т. д. Отсюда видно, что с помощью простейших преобразований, информацию, заданную в любом конечном алфавите, можно записать в алфавите, содержащем только две буквы. Такой алфавит называют «двоичным алфавитом», а две его буквы будем обозначать нулем и единицей. Эти преобразования носят специальное название двоичного кодирования исходной информации. Таким образом, при различных преобразованиях информации можно, не нарушая общности, предполагать, что как исходная, так и заключительная информация задана в некотором стандартном (например, двоичном) алфавите. 

1.6. Способы задания автоматов 

     Абстрактные автоматы задаются с помощью таблиц переходов (выходов), графов, матриц переходов. Таблица переходов (таблица выходов) автомата Мили представляет собой таблицу, в которой левый столбец обозначается входными сигналами, а верхняя строка – состояниями, начиная с начального состояния. На пересечении строки и столбца указывается следующее состояние, в которое переходит автомат (в таблице переходов) или выходной сигнал, выдаваемый им (в таблице выходов). Представим автоматы Мили и Мура табличным способом. Описание работы автомата Мили таблицами переходов и выходов иллюстрируется на примере автомата А1 (рис. 1.5): Х – алфавит входных сигналов; Y – алфавит

     выходных  сигналов; Q – алфавит состояний.

     Автомат, имея один вход и один выход, работает в дискретном времени, принимающем значения t = 1, 2, 3, ... На вход автомата поступают входные сигналы xf (например, сигналы x1 и x2). В каждый момент t автомат находится в некотором состоянии q(t), начиная с начального состояния q1. На пересечении столбца qm и строки xf в таблице переходов ставится состояние qs, в которое автомат переходит из состояния qm под действием сигнала xf , а в таблице выходов – соответствующий этому переходу выходной сигнал yg. Иногда при задании автоматов Мили используют одну совмещенную таблицу переходов и выходов, в которой на пересечении столбца qm и строки xf записываются в виде qs / yg следующее состояние и выдаваемый выходной сигнал. На рис.1.представлена совмещенная таблица автомата А1.

     q1 q2 q3

     x1 q2 / y1 q3 / y3 q2 / y3

     x2 q3 / y2 q2 / y1 q1 / y1

     Рис. 1.Совмещенная таблица автомата А1

     Так как в автомате Мура выходной сигнал зависит только от внутреннего состояния и не зависит от входного сигнала, то он задается одной отмеченной таблицей переходов, в которой каждому ее столбцу приписан, кроме состояния qm еще и выходной сигнал yg, соответствующий этому состоянию. Пример табличного описания автомата Мура А2 (рис. 1.1).

     Для частичных автоматов, у которых  функции или определены не для всех пар (qm, xf) Q x X, на месте неопределенных состояний и выходных сигналов ставится прочерк.

     y1 y1 y3 y2 y3 q1 q2 q3 q4 q5

     x1 q2 q5 q5 q3 q3

     x2 q4 q2 q2 q1 q1

     Часто автомат задают с помощью графа  автомата. Граф автомата – ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Две вершины графа автомата qm и qs (исходное состояние и состояние перехода) соединяются дугой, направленной от qm к qs, если в автомате имеется переход из qm в qs, т. е. если qs при некотором xf Х. Данной дуге (qm , qs) приписывается входной сигнал xf и выходной сигнал yg. При этом выходной сигнал yg записывается внутри вершины qm или рядом с ней. Любой автомат может быть задан с помощью графа, но не всякий граф в алфавитах Q, X, Y задает автомат. В графе автомата не должно существовать двух дуг с одинаковыми входными сигналами, выходящих из одной и той же вершины (условие однозначности). Иногда применяется способ задания автомата с помощью матрицы переходов и выходов, которая представляет собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из состояния qm под действием входного сигнала xf в состояние qs, с выдачей выходного сигнала yi, то на пересечении строки qm и столбца qs записывается пара xf / yi.

     Для автомата Мура используется матрица, столбцы которой отмечены выходными сигналами yi, а на пересечении ее строк и столбцов указываются только входные сигналы xf. 

 

2. Практическая часть.  Синтез цифровых  автоматов определяющих  заданную последовательность 

2.1. Заданная бинарная  последовательность

1₁₀ = (0000001)₂

2.2. Граф

      
 
 

 

 

 

 
 
 
 

 

      0 
 
 

Рис. 1.

 

    

2.3. Таблицы 

Таблица 1. переходов 

 

Таблица 2. выходов 

 

Таблицы 3. переходов в двоичную систему счисления 

 

Таблица 4. выходов 

 

S₀  - 000

S₁ - 001

S₂  - 010

S₃  - 011

S₄  - 100

S₅  - 101

S₆  - 110

<