12490

Учебно-методическое пособие по дисциплине «Теория автоматов»

Книга

Коммуникация, связь, радиоэлектроника и цифровые приборы

Учебно-методическое пособие по дисциплине Теория автоматов Направление 230100 Информатика и вычислительная техника Специальность 230101 Вычислительные машины комплексы системы и сети Учебно-методическое пособие Курс Теория автоматов является базовым при

Русский

2013-04-29

13.21 MB

49 чел.

Учебно-методическое пособие

по дисциплине «Теория автоматов»

Направление 230100 Информатика и вычислительная техника

Специальность 230101 – Вычислительные машины, комплексы, системы и сети

Учебно-методическое пособие

Курс «Теория автоматов» является базовым при подготовке специалистов по специальности «Вычислительные машины, комплексы, системы и сети». В основных разделах курса рассматриваются методы синтеза комбинационных схем, методы абстрактного и структурного синтезу автоматов.


Раздел I. Общие сведения о цифровых автоматах

1.1. Основные понятия и определения

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

Все схемы ЭВМ можно разделить на два больших класса:

Класс логических или комбинационных схем (КС).

Класс конечных автоматов (КА).

    В логических (комбинационных) схемах значение выходных сигналов в момент времени t однозначно определяется значениями входных сигналов в момент времени t1  t.

     Выходные сигналы в схемах второго класса определяются не только значениями входных сигналов в данный момент времени, но и состоянием схемы, которое, в свою очередь, зависит от значения сигналов, поданных на её входы в предшествующие моменты времени. Эти схемы обязательно содержат в своем составе элементы памяти, в качестве которых используется триггера различных типов.

Технические вопросы синтеза комбинационных схем решаются с помощью аппарата математической логики. При этом используется самая простая часть математической логики, а именно, алгебра логики или булева алгебра. Основным понятием в алгебре логики, на котором основывается её приложение к синтезу КС, является понятие булевой или переключательной функции (ПФ). Переключательной  или  булевой функцией  называется  функция      f(x1, x2,, xn), способная принимать как и ее аргументы x1, … , xn  только два значения 0 или 1.

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

1.2. Свойства переключательных функций

Любая ПФ n аргументов определена на 2n наборов.

Число различных ПФ n аргументов конечно и равно . При n = 1,

число различных ПФ равно 4, при n = 2 – 16, при n = 3 – 256, при n = 4 – 65536, при n = 5 – примерно 4,3109. Ясно, что прямое изучение ПФ с помощью таблиц истинности возможно лишь для небольшого числа аргументов.

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

Возьмем какую либо комбинационную схему (рис.1.1):

Рис.1.1. Комбинационная схема

Схема имеет n входов и m выходов и следовательно реализуют m ПФ от n аргументов.

Любая сколь угодно сложная КС строится из более простых схем, называемых логическими элементами.

В ЭВМ в основном используются логические элементы с одним или двумя входами, реализующие ПФ одного или двух аргументов. Поэтому задача синтеза КС заключается в том, чтобы из логических элементов построить любую сколь угодно сложную схему, реализующую заданный набор ПФ. Математически в алгебре логики этой задачи соответствует задача представления любой сложной ПФ через элементарные ПФ.

При составлении сложных схем используют два приема: последовательное соединение элементов и перестановку входов элементов. Последовательное соединение логических элементов I и II показано на рис.1.2.

Рис.1.2. Последовательное соединение логических элементов

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

Перестановка входов логических элементов показана на рис.1.3.

                     Рис.1.3. Перестановка входов логических элементов

В общем случае функция f4(x1, x2, x3) отличается от функции f3(x1, x2, x3). В математическом плане мы заменили одни аргументы ПФ другими. Замена одних аргументов функции другими или изменение порядка записи аргументов называется подстановкой аргументов.

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

Раздел 2. Синтез цифровых автоматов без памяти

 Общая задача структурного синтеза комбинационных схем

Будем рассматривать синтез КС, реализующей одну ПФ. Процесс синтеза КС на элементах заданного базиса разбивается на следующие этапы:

Аналитическая запись ПФ в булевом базисе: в совершенной дизъюнктивной нормальной форме (СДНФ) или в совершенной дизъюнктивной нормальной форме (СКНФ).

Минимизация ПФ в булевом базисе.

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

Аналитическая запись ПФ в булевом базисе (запись в виде СДНФ или в СКНФ).

2.1. Аналитическая запись переключательной функции

Для аналитического представления ПФ используют 2 правила ее записи: по единицам и по нулям. При записи по единицам:

- в таблице истинности выбирают все наборы, на которых ПФ равна единице;

- выписывают произведения аргументов, соответствующих этим наборам. При этом, если в этом наборе аргумент равен 1, то он вписывается в произведение без изменения, если же он равен 0, то он вписывается со знаком отрицания;

- все полученные произведения соединяются знаком дизъюнкции.

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

При записи по нулям:

– в таблице истинности выбирают все наборы, на которых ПФ равна нулю;

– выписывают дизъюнкцию аргументов, соответствующих этим наборам. При этом если в этом наборе аргумент равен 0, то он вписывается в произведение без изменения, если же он равен 1, то он вписывается со знаком отрицания;

- все полученные дизъюнкции соединяются знаком произведения.

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

2.2. Минимизация ПФ в булевом базисе

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

В процессе минимизации СДНФ получается последовательно в начале сокращенная ДНФ, далее тупиковая и минимальная.

Существуют различные методы минимизации ПФ, из которых чаще всего используются методы Квайна, Мак-Класки, Блейка-Порецкого, диаграмм Вейча и карт Карно. В принципе все эти методы являются равновидностями метода Квайна.

2.3. Метод минимизации Блейка-Порецкого

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

Если в ДНФ для данной функции f(А, В, С) входят две конъюнкции вида АС и B, то имеет место следующее равенство:

.

Запишем функцию f (А, В, С) в следующем виде:

.

Из этого вытекает метод построения сокращенной ДНФ. Этот метод заключается в том, что если в ПФ есть конъюнкции с переменными С и , то не изменяя исходную функцию необходимо пополнить ее новыми членами вида АВ. После этого надо провести поглощения и вновь повторить пополнение ДНФ. Этот процесс необходимо производить до тех пор, пока не будут возникать новые конъюнкции вида АВ. По окончании преобразований получаем сокращенную ДНФ.

 Пример. Найти сокращенную ДНФ для функции 3-х аргументов:

.

2.4. Метод минимизации Мак-Класки

 В методе Квайна есть одно существенное неудобство. Оно связано с необходимостью полного попарного сравнения всех членов СДНФ ПФ на этапе нахождения всех простых импликант (при выполнении всевозможных операций неполного склеивания). При большом числе переменных применение метода Квайна становится затруднительным. Мак-Класки предложил модернизацию метода Квайна, дающую уменьшение числа сравнений.

Идея метода Мак-Класки заключается в следующем: конституенты 1 в СДНФ представляются не в буквенном виде, а виде условных чисел – номеров соответствующих конституент.

Пример. =

                  =  0000  0001  0010  0111 1001 1010  1110  1111  =

                  = 01279101415 =  (0, 1, 2, 7, 9, 10, 14, 15).

При этом оказывается, что переменные имеют вес: ABCD 8421.

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

= 00000001 = 01=; 01 = (0, 1), (1), т.е. склеиваются конституенты 0 и 1, а в скобках указывается разность, какая переменная исключается (D).

Еще пример: 01000110 = 46 = (4, 6), (2) – склеиваются по C.

Вводится понятие индекса. Индексом целого числа называется количество 1 в двоичном представлении этого числа: 7 = 0111 – индекс равен 3, 0000 – индекс равен 0 и т.д. Если конституенты 1 склеиваются, то их индексы отличаются на 1,  а в скобках должно быть число (их разности), равное целой степени 2 (по какой переменной склеиваются).

Правило. Для того чтобы два числа m и n являлись номерами двух склеивающихся между собой конституент 1, необходимо и достаточно, чтобы их индексы отличались точно на 1, чтобы сами числа отличались друг от друга на степень 2, и чтобы число с большим индексом было больше числа с меньшим индексом.

Так конституенты 1 с номерами 4 и 3, равными 0100 и 0011, не склеиваются, хотя их разности равны 1.

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

Пример. (0, 1, 3, 4, 5, 6, 10, 11, 12, 14, 15). Минимизировать методом Мак-Класки.

Прежде всего группируем номера конституент в порядке роста их индексов. В нулевую группу попадает номер 0. В 1 группу – конституенты с индексом 1 (1 и 4), во 2 группу – конституенты с индексом 2 (3 = 0011, 5 = 0101, 6 = 0110, 10 = 1010 и 12 = 1100), в 3 группу – конституенты с индексом 3 (11 = 1011 и 14 = 1110), в 4 группу – конституенты с индексом 4 (15 = 1111). В результате имеем следующее разбиение конституент функции  на группы:

0

0

1

1

4

2

3

5

6

10

12

3

11

14

4

15

В силу рассмотренного правила,

склеивание возможно между номерами конституент соседних групп, т.е. 0 и 1, 1 и 2, 2 и 3 и 3 и 4. Никакие другие склеивания невозможны. Необходимо также, чтобы число, стоящее в следующей группе, было больше соответствующего числа  в предыдущей группе, причем больше на целую степень 2. Например, 0 склеивается с 1, записывается пара (0,1) и рядом их разность: 1 – 0 = 1. Запись выглядит так: (0, 1), (1).

Около склеенных номеров ставятся звездочки, показывающие, что эти члены участвовали хотя бы в одном склеивании. Такие члены, как известно, в сокращенную ДНФ уже не войдут. После завершения склеивания групп отделяем горизонтальной чертой полученные выражения.

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

0

0

*

 1

1

4

*

*

2

3

5

6

10

12

*

*

*

*

*

3

11

14

*

*

4

15

*

(0,1),   (1) *

(0,4),   (4) *

(0,1,4,5),          (1,4)   (с)

(0,1,4,5),          (4,1)

(1,3),   (2)  (а)

(1,5),   (4) *

(4,5),   (1) *

(4,6) ,  (2) *

(4,12), (8) *

(4,6,12,14),      (2,8)   (d)

(4,6,12,14),      (8,2)

(10,11,14,15)   (1,4)   (e)

(10,11,14,15)   (4,1)

(3,11),   (8) (в)

(6,14),   (8) *

(10,11), (1) *

(10,14), (4) *

(12,14), (2) *

(11,15), (4) *

(14,15), (1) *

Для склеивания пар применяются те же правила, но добавляется еще одно условие: разности у склеиваемых пар должны быть одинаковы. При этом оказывается, что в парах переменные в выражении одинаковы.

Возьмем, например, пары (0, 1),(1) и (1, 3), (2). 0 и 1 склеиваются, 1 и 3 тоже, но разности у них не одинаковы – поэтому склеивание невозможно (у первой пары нет переменной D, у второй пары нет переменной С – они, конечно, и не могут склеиваться). В результате склеивания пишем уже четверки (0, 1, 4, 5) и две разности (1, 4), т.е. в результирующем выражении нет 2-х переменных B и D. После завершения этих склеиваний получают, если возможно, восьмерки, при этом должны совпадать уже разности в скобках у четверок и т.д.

Обозначим пары и четверки, которые не участвовали в склеивании, латинскими буквами. Тогда . При получении выражения для импликант а, в, с и т.д., поступают следующим образом: берут любую из конституент 1, участвующих в операции склеивания, и исключают переменные, указанные в разностях. Например, для импликанты а получим: 0001= (разность 2). Эта разность говорит о том, из выражения необходимо исключить переменную с весом 2, т.е. С. Тогда а = .

Аналогично получим: для в: 0011= (разность 8), в = , для с: 0001= (разности 1 и 4), с = , для d: 0100 =  (разности 2 и 8),     d =, для e: 1111=AВCD (разности 1 и 4), e = АС. В результате получим:

.

2.5. Табличный метод минимизации ДНФ

Метод диаграмм Вейча или карт Карно

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

Переключательные функции двух аргументов

Пример. . Диаграмма Вейча имеет следующий вид:

      Тогда: .

Для представления функции с помощью диаграмм Вейча или карт Карно следует записать 1 в клетках таблицы, соответствующие наборам, на которых функция равна 1, а 0 в остальные клетки.

При склеивании соседние конституенты будем обводить овалом.

Переключательные функции трех аргументов

Пример. .

Диаграмма Вейча состоит из 8 клеток и имеет следующий вид:

   BC

A  

00

01

11

10

0

1

0

1

1

1

1

1

0

1

                                               

     Тогда.

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

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

Переключательные функции четырех аргументов

В диаграммах Вейча и картах Карно для четырех аргументов соседними клетками являются крайние клетки каждого столбца и строки. Поэтому такую диаграмму следует рассматривать как свернутую в тор.

Пример. (0, 1, 4, 5, 9, 10, 11, 13, 14, 15).

Диаграмма Вейча состоит из 16 клеток и имеет следующий вид:

  CD

AB

00

01

11

10

 00

1

1

0

0

01

1

1

0

0

11

0

1

1

1

10

0

1

1

1

.

Построим схему в булевом базисе (рис. 2.1):

Рис. 2.1

Построим схему, реализующую функции  в базисе И-НЕ (штрих Шеффера). Для этого осуществим переход от булевого базиса к базису И-НЕ:                              .

Схема, реализующая функцию  в базисе И-НЕ, приведена на рис. 2.2.

 

Рис. 2.2

Построим схему, реализующую функции  в базисе ИЛИ-НЕ (стрелка Пирса). Для этого осуществим переход от булевого базиса к базису ИЛИ-НЕ:                           .

Схема, реализующая функцию  в базисе ИЛИ-НЕ, приведена на рис. 2.3.

                               Рис. 2.3

Переключательная функция для пяти аргументов

Пример. (2, 3, 6, 7, 9, 10, 11, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30). Диаграмма Вейча состоит из 32 клеток и имеет следующий вид:

CDE

AB

000

001

011

010

110

111

101

100

00

0

0

1

1

1

1

0

0

01

0

1

1

1

1

1

1

0

11

1

0

0

1

1

0

0

1

10

1

0

0

1

1

0

0

1

                                        .

В этой диаграмме, как и прежде, соседними являются крайние клетки каждого столбца и строки левой и правой половин. Кроме того, соседними являются клетки расположенные на одной строке и равноудаленные от центральной вертикальной линии, т.е. диаграмму следует представить ещё и сложенную по центральной вертикальной линии как страница книги.

2.6. Преобразование функции в минимальную конъюнктивную

нормальную форму (КНФ)

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

Пример. Найти минимальную КНФ функции . Диаграмма Вейча имеет вид:

Из диаграммы получим:

 .

Тогда:   

– минимальная КНФ.

2.7. Минимизация не полностью определенных переключательных функций

В ЭВМ иногда применяются КС, закон функционирования которых определен не полностью. В таких схемах некоторые комбинации сигналов на входы никогда не подаются. Эти комбинации входных сигналов называются запрещенными. Для запрещенных входных комбинаций выходные сигналы не определены, т.е. могут принимать любые значения 0 или 1. Поэтому при синтезе КС с не полностью заданным законом функционирования можно произвольно задать значение выходных сигналов для запрещенной комбинации входных сигналов, поскольку нормальная работа схемы при этом не нарушается. Обычно выходным сигналам на запрещенных комбинациях придают такие значения, при которых можно построить наиболее простую схему. Работа схем с запрещенными комбинациями входных сигналов описывается не полностью определенными ПФ, т.е. функциями, значения которых определены не на всех наборах аргументов. Поэтому минимизация не полностью определенных ПФ с помощью карт Карно сводится к такому доопределению ПФ, при котором получаются группы с максимальным числом соседних единиц в каждой группе, а число таких групп минимально. При этом ПФ будет содержать минимум букв.

Пример. Найти минимальную ДНФ и минимальную КНФ не полностью определенной ПФ: , . На остальных наборах функция не определена.

– минимальная ДНФ,

;

 

– минимальная КНФ.

2.8. Минимизация систем переключательных функций

Работа КС, имеющей n входов и m выходов, описывается системой m переключательных функций, каждая из которых определяет закон функционирования схемы по одному выходу.

Если провести минимизацию ПФ, входящих в систему независимо друг от друга, то получится схема, содержащая m изолированных цепей, в общем случае не минимальная. Однако эту схему можно существенно упростить за счет объединения участков схемы, реализующих одинаковые члены.

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

Раздел 3. Общая теория конечных цифровых автоматов с памятью
3.1. Основные понятия и определения

В вычислительной технике используются схемы двух классов: комбинационные схемы и цифровые автоматы. Отличительной особенностью КС является наличие функциональной зависимости между входными и выходным сигналами: y(t) = f(x(t)). Причем при отсутствии входных сигналов выходные сигналы также отсутствуют, поскольку такие схемы не имеют памяти. В отличии КС схемы второго класса содержат в своем составе элементы памяти (запоминающие элементы). Эти схемы называются цифровыми автоматами (ЦА) или просто автоматами. В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени, но и от состояния схемы, которое, в свою очередь, определяется значениями входных сигналов, поступивших в предшествующие моменты времени. Введем основные понятия и определения.

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

3.2. Кодирование информации

Информацию, поступающую на вход автомата, а так же выходную информацию, принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит – буквами, а любые упорядоченные последовательности букв – словами в этом алфавите. Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1, x2x2, x1x1x1 и т.д.

Наряду со словами, состоящими не менее чем из одной буквы, введем слово, не содержащее ни одной буквы, которое будем обозначать символом е и называть пустым словом или пустой буквой.

Математической моделью реального КА является абстрактный автомат, который имеет один входной канал и один выходной канал (рис. 3.1):

X(x1, …, xF)

--->

A(a0, ..., aM)

--->

Y(y1, …, yG).

Рис. 3.1. Абстрактный автомат

Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый

дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (Tconst). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами t = 0, 1, 2, 3, … , имеющими смысл номера такта.

Для задания любого КА S необходимо задавать совокупность из пяти объектов:                                    S{A, X, Y, d, l}, 

где A = {a0, a1, a2, ..., am, ..., aM} – множество состояний автомата,          X = {x1, x2, …, xf ,…, xF} – множество входных сигналов или входной алфавит, Y = {y1, y2, …, yg,…, yG} – множество выходных сигналов или выходной алфавит, d – функция переходов, определяющая состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, т.е. a(t + 1) = d [a(t), x(t)],

l – функция выходов, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, т.е.                             y(t) = l[a(t), x(t)].

Если множества А, Х и У конечны, то автомат называется конечным.

Автомат работает следующим образом. В каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0 он находится в состоянии a0. Автомат воспринимает входной сигнал x(t), выдает выходной сигнал          y(t) = l[a(t), x(t)] и переходит в состояние a(t + 1) = d[a(t), x(t)]. Другими словами, абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t + 1) и y(t). Такие автоматы называют детерминированными.

Кроме детерминированных автоматов существуют вероятностные   автоматы, в которых переход из одного состояния в другое под воздействием случайных или детерминированных входных сигналов происходит случайно. Работа таких автоматов описывается уже матрицей переходов d, элементами которой являются вероятности переходов из одного состояния в другое. Нами будут рассмотрены, в основном,  детерминированные автоматы.

Применяемые на практике автоматы принято разделять на два класса – это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать. Законы функционирования автоматов описываются следующими системами уравнений:

   Автомат Мили:                                     Автомат Мура:

a(t + 1) = d [a(t), x(t)],                           a(t + 1) = d [a(t), x(t)],

     y(t) = l[a(t), x(t)]..                                   y(t) = l[a(t)].

Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y(t) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.

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

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d, l}, т.е. необходимо описать входной и выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l. При этом среди множества A = {a0, a1, …, aМ} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

Табличный способ

При табличном способе задания автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов:

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

xj/ ai

a0

aМ

x1

d(a0, x1)

d(aМ, x1)

xF

d(a0, xF)

d(aM, xF)

             

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

xj/ai

a0

aM

x1

l(a0, x1)

l(aM, x1)

xF

l(a0, xF)

l(aM, xF)

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = d[ ai, xj], в которое автомат перейдет из состояния ai под воздействием сигнала xj, а в таблице выходов – соответствующий этому переходу выходной сигнал yg = l[ai, xj]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов:

xj / ai

a0

aМ

x1

d(a0, x1) / l(a0, x1)

d(aM, x1) / l(aM, x1)

xF

d(a0, xF) / l(a0, xF)

d(aM, xF) / l(aM, xF)

Так как в автомате Мура выходной сигнал однозначно определяется состоянием автомата, то для его задания требуется только одна таблица, которая называется отмеченной таблицей переходов автомата Мура:

yg

l(a0)

l(aM)

xj / ai

a0

aM

x1

d(a0, x1)

d(aM, x1)

xF

d(a0, xF)

d(aM, xF)

В этой таблице каждому столбцу приписан, кроме состояния ai, еще и выходной сигнал y(t) = l(a(t)), соответствующий этому состоянию. Таблица переходов

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

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

Автомат Мура:

yg

y2

y1

y1

y3

y2

xj/ai

a0

a1

a2

a3

a4

x1

a2

a1

a3

a4

a2

x2

a3

a4

a4

a0

a1

Автомат Мили:

xj/ai

a0

a1

a2

a3

x1

a1/y1

a2/y3

a3/y2

a0/y1

x2

a0/y2

a0/y1

a3/y1

a2/y3

По этим таблицам можно найти реакцию автомата на любое входное слово.

Для автомата Мура:

 

x1

x2

x2

x2

x1

 

a0

a2

a4

a1

a4

 

 

y2

y1

y2

y1

y2

 

 

 

 

 

 

 

 

Для автомата Мили:

 

x1

x2

x2

x2

x1

 

a0

a1

a0

a0

a0

a1

 

y1

y1

y2

y2

y1

 

Графический способ

При графическом способе задание автомата осуществляется с помощью графа. Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as, если в автомате имеется переход из ai в as, то есть        as = d(ai, xj). В автомате Мили (рис. 3.2) дуга отмечается входным сигналом xj, под действием которого происходит этот переход, и выходным сигналом yg, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние автомата. В автомате Мура (рис. 3.3) в вершинах графа кроме состояния автомата отмечается соответствующий выходной сигнал, а дуга отмечается только входным сигналом xj, под действием которого происходит этот переход.                                                                 

 


Рис. 3.2. Граф для автомата Мили                                Рис. 3.3. Граф для автомата Мура

3.4. Частичные автоматы

В инженерной практике часто встречаются автоматы, на входы которых некоторые последовательности сигналов никогда не подаются. Такие последовательности будем называть запрещенными входными словами данного автомата, а сам автомат – частичным автоматом. У частичного автомата функции переходов и выходов определены не на всех парах ai, xj. На месте неопределенных состояний и выходных сигналов ставится прочерк. При синтезе обычно производят доопределение частичного автомата, чтобы его схемная реализация получилась как можно проще.

Пример таблицы переходов и выходов частичного автомата Мили:

xj\ai

a0

a1

a2

a3

x1

a1/y1

a3/y3

a2/y2

a2/y1

x2

/

/

a0/y4

a0/y2

3.5. Элементарные автоматы

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

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

Теорема о структурной полноте формулируется следующим образом:

Для того чтобы система элементов была структурно полной, необходимо и достаточно, чтобы она содержала какую-либо функционально полную систему логических элементов и хотя бы один элементарный автомат с двумя устойчивыми состояниями, обладающий полной системой переходов и выходов.

Полнота переходов в автомате означает, что для любой пары состояний ai и aj существует хотя бы один входной сигнал, который переводит автомат из состояния ai в состояние aj, причем i = j и , т.е. в каждом столбце таблицы переходов должны встречаться все состояния. Полнота выходов автомата означает, что в каждом состоянии автомат выдает выходной сигнал, отличный от сигналов, выдаваемых в других состояниях.

Таким образом, для построения любого  конечного автомата необходимо иметь элементарные автоматы, обладающие полной системой, как переходов, так и выходов. Рассмотрим конкретные типы элементарных автоматов, имеющих полную систему переходов и выходов и нашедших применение в вычислительной технике.

В настоящее время в вычислительной технике, как правило, используются элементарные автоматы, имеющие следующие особенности:

Элементарные автоматы являются автоматами Мура с двумя внутренними состояниями.

Автомат выдает два различных выходных сигнала, соответствующих двум его внутренним состояниям. В дальнейшем состояния автомата и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и 1.

Элементарные автоматы могут иметь в общем случае несколько

физических входов.

В качестве элементарных автоматов в вычислительной технике используются триггеры различных типов (рис. 3.4). Рассмотрим некоторые из них.

                         Рис. 3.4

                                         

Т-триггер

Т-триггером называют автомат Мура с двумя устойчивыми состояниями и одним входом Т, который изменяет свое состояние на противоположное всякий раз, когда на вход Т поступает единичный сигнал.

Таблица переходов Т-триггера:

yg

0

1

xj /ai

0

1

T = 0

0

1

T = 1

1

0

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

На практике более удобно вместо отмеченных таблиц переходов пользоваться так называемыми матрицами переходов элементарных автоматов.

Матрица переходов

T

Q(t)

Q(t+1)

0

0

0

1

0

1

1

1

0

0

1

1

Она определяет значения сигналов на входах элементарного автомата, обеспечивающих каждый их четырех возможных переходов. Здесь Q(t) и  Q(t + 1) – состояния автомата в моменты времени t и t + 1 соответственно.

 Поскольку Т-триггер имеет один вход, а число возможных переходов равно четырем, то матрица переходов имеет четыре строки.

Для записи закона функционирования Т-триггера в аналитическом виде составим диаграмму Вейча:

T\Q(t)

0

1

  0

0

1

  1

1

0

Из диаграммы имеем:         .

Поскольку эта формула совпадает

с аналитической записью ПФ логической неравнозначности (сложение по модулю два), то Т-триггер часто называют триггером со счетным входом, а входной сигнал, поступающий на вход Т, счетным сигналом.

На практике кроме асинхронного Т-триггера используют так же и синхронный Т-триггер, который меняет свои состояния только при Т = 1 и С = 1. Вход С называют входом синхронизации.

Поясняющая работу комбинационная схема и обозначение синхронного
Т-триггера представлены на рис. 3.5:

Рис.3.5.

D-триггер

D-триггером (триггером задержки) называют элементарный автомат Мура с двумя устойчивыми состояниями и одним входом D таким, что       Q(t + 1) = D(t). Название D-триггера происходит от английского слова “delay” – задержка. Состояние триггера в момент времени t + 1 повторяет значение входного сигнала D(t) в момент времени t .

Матрица переходов D-триггера: 

D

Q(t)

Q(t + 1)

0

0

0

1

0

1

0

1

0

1

1

1

Обозначение синхронного D-    триггера:                                                                                              

Рис. 3.6

В синхронном D-триггере при С = 0 триггер свое состояние не меняет, а при С=1 работает так же, как и асинхронный, то есть .

Граф D-триггера (рис. 3.7):

                                                                                                 

                                                                                             

Рис. 3.7

RS-триггер

RS-триггером называют автомат Мура с двумя устойчивыми состояниями, имеющий два входа R и S. При S = 1 триггер устанавливается в состояние 1, а при R = 1 – в состояние 0. Одновременная подача двух сигналов, равных 1, запрещена, т.е. R S = 0.  В соответствии с состоянием, принимаемым триггером, вход S называет единичным входом, а вход Rнулевым.

Переход триггера из 0 в 0 возможен при двух комбинациях входных сигналов: R = 0, S = 0 и R = 1, S = 0. Поэтому в первой строке матрицы переходов в столбце R поставлен неопределенный коэффициент b1 = 0 v 1. Аналогично переход из состояния 1 в 1 также возможен при двух комбинациях входных сигналов: R = 0, S = 0 и R = 0, S = 1.

Матрица переходов RS-триггера:

R

S

Q(t)

Q(t+1)

b1

0

0

0

0

1

0

1

1

0

1

0

0

b2

1

1

Поскольку при таком переходе значения сигнала на входе S безразлично, то в нижней строке матрицы переходов в столбце S записан коэффициент b2. По матрице переходов можно построить граф RS-триггера.

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

Запишем закон функционирования RS-триггера в аналитическом виде, для чего составим по матрице переходов диаграмму Вейча:

 

SQ(t)

R

00

01

11

10

0

0

1

1

1

1

0

0

Запрещенные комбинации входных сигналов при минимизации заполним единичными значениями. Тогда имеем:         .    

                                   

JK-триггер

JK-триггером называют автомат Мура с двумя устойчивыми состояниями и двумя входами J и K. При JK = 1 триггер меняет свое состояние на противоположное. В остальных случаях он функционирует в соответствии с таблицей истинности RS-триггера, при этом вход J эквивалентен входу S, а вход K - входу R.

Таблица истинности JK-триггера:                                                                       

J

K

Q(t)

Q(t+1)

0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

0

Построим диаграмму Вейча

и матрицу переходов:

 

KQ(t)

J

00

01

11

10

0

0

1

0

0

1

1

1

0

1

J

K

Q(t)

Q(t+1)

0

b1

0

0

1

b2

0

1

b3

1

1

0

b4

0

1

1

Тогда:                    .

JK-триггер относится к разряду универсальных триггеров, поскольку на его основе можно построить RS-, D- и T-триггера. RS-триггер получается наложением ограничения на комбинацию входных сигналов J = K = 1, так как эта комбинация является запрещенной для RS-триггера. Т-триггер получается путем объединения входов J и K (рис. 3.8). D-триггер строится путем подключения к входу K инвертора, на который подается тот же сигнал, что и на вход J. В этом случае вход J выполняет функцию входа D (рис. 3.9).                               

         Рис. 3.8.

Рис. 3.9

3.6. Структурная схема конечного автомата

В структурной теории автомат представляют в виде композиции двух частей: запоминающей части, состоящей из элементов памяти, и комбинационной части, состоящей из логических элементов (рис. 3.10):

                                            

                                                   Рис. 3.10

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

Каждое состояние абстрактного автомата ai, где i = {0, М}, кодируется в структурных автоматах набором состояний элементов памяти Qr, r = {1, R}. Поскольку в качестве элементов памяти используются триггера, то каждое состояние можно закодировать двоичным числом . Здесь            аi = {0, 1}, a Q – состояние автомата. Отсюда:  .

Общее число необходимых элементов памяти можно определить из следующего неравенства: , где (М + 1) – число состояний автомата. Логарифмируя неравенство, получим: . Здесь ]C[  означает ближайшее целое число, большее или равное C.

В отличие от абстрактного автомата, имеющего один входной и один выходной каналы, на которые поступают сигналы во входном
X = {x1, x2,..., xf,…, xF} и выходном Y = {y1, y2,..., yg, ..., yG} алфавитах, структурный автомат имеет L входных и N выходных каналов. Каждый входной xj и выходной yj сигналы абстрактного автомата могут быть закодированы двоичным набором состояний входных и выходных каналов структурного автомата:                ,          .                                                                                       

Здесь  и – значения двоичных входных и выходных сигналов соответственно. Число каналов L и N можно определить аналогичнo формуле для определения R:                     , .  

Изменение состояния элементов памяти происходит под действием сигналов U = (U1, U2, ..., UR), поступающих на их входы. Эти сигналы формируются комбинационной схемой КС1 и называются сигналами возбуждения элементарных автоматов. На вход КС1 по цепи обратной связи поступают сигналы  Q  = (Q1, Q2, ..., Qr,..., QR) с выходов элементов памяти автомата. Комбинационная схема КС2 служит для формирования выходных сигналов Y = {y1, y2,..., yg, ..., yG}, причем в случае автомата Мили на вход этой схемы поступают входные сигналы, а в случае автомата Мура – входные сигналы не поступают.

3.7. Табличный метод структурного синтеза конечных автоматов

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

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

Пример. Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов:

xj /ai

a0

a1

a2

x1

a1/y1

a1/y2

a1/y2

x2

a2/y3

a2/y3

a0/y1

   

 В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов – элементы И, ИЛИ, НЕ.

 A = {a0, a1, a2}; X = {x1, x2}; Y = {y1, y2, y3}. Здесь  M + 1 = 3; F = 2, G = 3.

1. Перейдем от абстрактного автомата к структурному, для чего определим количество элементов памяти R и число входных L и выходных N каналов:

= 2,        = 1,      = 2.

Таким образом необходимо иметь два элементарных автомата Q1 и Q2, один входной канал  и два выходных канала z1 и z2 (каналы  и z называют еще физическими входами и выходами автомата соответственно).

2. Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов.

Таблицы кодирования

состояний

входных

выходных

автомата

сигналов

сигналов

aj

Q1

Q2

a0

0

0

a1

0

1

a2

1

0

xf

O1

x1

0

x2

1

yg

z1

z2

y1

0

0

y2

0

1

y3

1

0

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

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

xj /ai

00

01

10

0

01/00

01/01

01/01

1

10/10

10/10

00/00

3. Построим кодированные таблицы переходов и выходов. Эти таблицы  определяют зависимости состояний элементарных автоматов и выходных сигналов в момент времени (t + 1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t, т.е:

,

.

Кодированная таблица переходов и выходов имеет следующий вид:

t

t + 1

Q1

Q2

z1

z2

Q1

Q2

0

0

0

0

0

0

1

0

0

1

0

1

0

1

0

1

0

0

1

0

1

0

1

1

1

0

0

1

0

1

0

1

0

1

1

0

1

0

1

1

0

0

0

0

0

1

1

1

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

переходов заполняются столбцы   таблицы функций возбуждения. В строках этой таблицы записываются значения J и K, обеспечивающие нужный переход. Ниже представлена таблица функций возбуждения.

Таким образом, получим значения входных сигналов J и K элементарных автоматов, которые зависят как от значения входного сигнала, так и от состояния автомата в тот же момент времени.  

t

t + 1

Q1

Q2

J1

K1

J2

K2

Q1

Q2

0

0

0

0

b

1

b

0

1

0

0

1

0

b

b

0

0

1

0

1

0

b

1

1

b

0

1

0

1

1

1

0

0

1

b

0

b

1

0

1

0

1

1

b

b

1

1

0

1

1

0

b

1

0

b

0

0

1

1

1

В результате получим систему переключательных функций z1(t), z2(t), J1(t), K1(t), J2(t) и K2(t), заданных в виде таблиц их истинности.

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

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

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

                                                     

,    ,    ,    ,    ,    .

В результате минимизации мы получим следующую схему конечного автомата (рис. 3.11):

Рис. 3.11

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

3.8. Технические особенности конечных автоматов

В схемах ЭВМ все сигналы изменяются и воспринимаются, как правило, в дискретные моменты времени, обозначаемые числами натурального ряда t = 0, 1,…. Для отметки моментов дискретного времени ЭВМ содержит специальный блок, вырабатывающий синхронизирующие импульсы (СИ), следующие через равные интервалы времени Т. Этот интервал времени Т определяет такт работы устройства.

Поэтому первая техническая особенность связана с необходимостью синхронизации работы конечного автомата, причем синхронизации подлежат не только выходные сигналы, но и функции возбуждения. В связи с этим в автомат обычно вводят две серии синхроимпульсов СИ1 и СИ2, сдвинутых на половину периода друг против друга (рис. 3.12).

                             Рис. 3.12

 Под действием СИ1 формируются выходные сигналы, а под
действием СИ
2 автомат переводится в новое состояние. Структурная схема автомата имеет следующий вид (рис. 3.13).

Рис. 3.13

На входах каждого из триггеров стоят элементы И. На практике триггера часто выполняются в синхронном варианте (синхронные триггера), когда элементы И включают в схему триггера. Например, схему синхронного RS-триггера можно рассматривать как состоящую из асинхронного RS-триггера, ко входам R и S которого подключены двухвходовые элементы И.

На эти элементы кроме входных сигналов поступает синхронизирующий сигнал, обозначаемый буквой C (рис. 3.14):

Рис. 3.14

Очевидно, синхронные триггера будут сохранять свои состояния при  С = 0, а переходы в них возможны при С = 1.

Вторая техническая особенность конечного автомата связана с возможностью возникновения неустойчивых состояний и так называемых «гонок» в автомате. Понятие устойчивости заключается в следующем. Пусть в графе автомата мы имеем такой участок (рис. 3.15):

                                                                  

                                                                    Рис. 3.15

Здесь оба перехода выполняются под действием одного и того же входного сигнала xj. Если длительность сигнала СИ2 больше времени перехода автомата из состояния ai в состояние as, то сразу после перехода автомата в as может начаться переход в следующее состояние af под действием того же входного сигнала xj. Таким образом автомат может перескочить состояние as и к моменту времени t + 1 оказаться не в as, как это требуется по графу, а в af. Состояние as в данном случае будет неустойчивым.

Другой неприятный момент заключается в том, что при работе автомата могут возникать «гонки» (состязания). Дело в том, что триггера в схеме имеют различные времена срабатывания, а также различные времена задержек сигналов обратной связи, которые поступают с выходов триггеров на их входы через КС1. По этим причинам, если при переходе автомата из состояния ai в as должны измениться состояния нескольких триггеров, то между их выходными сигналами начинаются гонки. Тот триггер, который выиграет гонку, то есть изменит свое состояние раньше других триггеров, может через цепь обратной связи изменить сигналы возбуждения на входах других триггеров до того момента, как они изменят свои состояния. Это, очевидно, может вызвать переход автомата совсем не в то состояние, которое нужно по графу. Пусть, например, ai = 101, as = 010. Тогда при переходе из ai в as меняются состояния всех триггеров. Допустим, что первый триггер изменил свое состояние раньше других. В этом случае автомат окажется в некотором промежуточном состоянии ah = 001, и если из этого состояния есть переход под действием сигнала xj в состояние, например, al = 011, то автомат в момент времени t + 1 может оказаться в al, а не в состоянии as, т.е совсем в другом состоянии.

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

 

Рис. 3.16

Здесь под действием синхронизирующего сигнала СИ1 формируются выходные сигналы zl(t) …  zN(t) и переключаются в новое состояние триггера первого ряда. Под действием СИ2 состояния триггеров первого ряда переписываются в соответствующие триггера второго ряда. Поскольку СИ2 сдвинуты относительно СИ1 на половину периода, а сигнал обратной связи о состоянии автомата снимается с триггеров второго ряда, то в момент поступления входного сигнала, то есть в СИ1, состояние автомата не изменяется и продолжает оставаться прежним до прихода СИ2. Поэтому в такой схеме полностью обеспечивается устойчивость состояний и устраняется влияние гонок. С целью упрощения построения схем автоматов, имеющих двойную память, выпускаются специальные двухступенчатые триггера. Рассмотрим работу такого триггера на примере двухступенчатого JK-триггера (рис. 3.17).

Двухступенчатый триггер

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

                         Рис. 3.17                                           

В момент С = 0 состояние триггера Т1 переписывается в триггер Т2.

3.9. Эквивалентные автоматы

Два автомата Sa и Sb с одинаковыми входными и выходными алфавитами называются эквивалентными. Для любого автомата Мили существует эквивалентный ему автомат Мура, и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили. Рассмотрим алгоритм перехода от произвольного конечного автомата Мили к эквивалентному ему автомату Мура.

Пусть дан конечный автомат Мили Sa = {Aa, Xa, Ya, da, la}, имеющий множество состояний Aa = {a0, a1,…, an,…,aM}, множество входных и выходных сигналов Xa = {x1, x2,…, xf,…, xF} и Y = {y1, y2, …, yg, …, yG}, а также функции переходов da(a, x) и выходов la(a, x).

 Требуется построить эквивалентный ему автомат Мура Sb = {Ab, Xb, Yb, db, lb}, у которого Xb = Xa, Yb = Ya, так как множества входных и выходных сигналов у эквивалентных автоматов должны совпадать.

Для определения множества состояний Ab автомата Мура образуем всевозможные пары вида (am, yg), где yg – выходной сигнал, приписанный к дуге, входящей в состояние am.

 Например, для вершины am имеем пары (am, y1), (am, y2), (am, y3)   рис.3.18.

 

                                                                                         Рис. 3.18

Если такие пары мы образуем для всех вершин, то получим множество пар, которое является множеством состояний автомата Мура: Ab = {(a0, y1), (a0, y2), …, (aM, yG)} = {b1, b2, …, bM}, где bl  = (ai, yg).                                  

           Функции выходов lb и переходов db определим следующим образом. Каждому состоянию автомата Мура, представляющему собой пару вида (ai, yg) поставим в соответствие выходной сигнал yg, то есть функция выходов равна   yg = lb[(ai, yg)] = lb[bl]. Если в автомате Мили Sa был переход
da(ai, xj) = as и при этом выдавался выходной сигнал la(ai, xj) = yp, то в эквивалентном автомате Мура будет переход из множества состояний (ai, yg), где g принадлежит G, G – множество номеров выходных сигналов, приписанных к входящей ai дуге, в состояние (as, yp) под действием входного сигнала xj.

Преобразование автомата Мили в автомат Мура

Рассмотрим пример. Пусть необходимо преобразовать автомат Мили в автомат Мура. Граф автомата  Мили имеет следующий вид:

                            

                        Рис. 3.19

В автомате Мили Xa = {x1, x2}, Ya = {y1, y2}, Aa = {a0, a1, a2}.

В эквивалентном автомате Мура

Xb = Xa = {x1, x2}, Yb = Ya = {y1, y2}.

Построим множество состояний Ab автомата Мура, для чего найдем множества пар, порождаемых каждым состоянием автомата Sa.

Состояние

Порождаемые пары

a0

{(a0, y1), (a0, y2)} = {b1, b2}

a1

{(a1, y1)} = {b3}

a2

{(a2, y1), (a2, y2)} = {b4, b5}

Отсюда имеем множества Ab состояний автомата Мура Ab = {b1, b2, b3, b4, b5}. Для нахождения функции выходов lb с каждым состоянием, представляющим собой пару вида (ai, yg), отождествим выходной

 

сигнал, являющийся вторым элементом этой пары. В результате имеем:

lb(b1) = lb(b3) = lb(b4) = y1;          lb(b2) = lb(b5) = y2.

Построим функцию переходов db. Так как в автомате Sa из состояния a0 есть переход под действием сигнала x1 в состояние a2 с выдачей y1, то из множества состояний {b1, b2}, порождаемых a0, в автомате Sb должен быть переход в состояние (a2, y1) = b4 под действием сигнала x1. Аналогично, из {b1, b2} под действием x2 должен быть переход в (a0, y1) = b1. Из (a1, y1) = b3 под действием x1 переход в (a0, y1) = b1, а под действием x2 – в (a2, y2) = b5. Наконец из состояний {(a2, y1), (a2, y2)} = {b4, b5} под действием x1 в (a0, y2) = b2, а под действием x2 – в (a1, y1) = b3. В результате имеем граф (рис. 3.20) и таблицу переходов эквивалентного автомата Мура.

Рис. 3.20. Граф эквивалентного

                автомата Мура

yg

y1

y2

y1

y1

y2

xj\bi

b1

b2

b3

b4

b5

x1

b4

b4

b1

b2

b2

x2

b1

b1

b5

b3

b3

                                    

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

В качестве начального состояния автомата Sb можно взять любое из состояний b1 или b2, так как оба порождены состоянием a0 автомата Sa.

Переход от автомата Мура к автомату Мили

Переход от автомата Мура к автомату Мили решается чрезвычайно просто. Пусть дан автомат Мура Sb ={Ab, Xb, Yb, db, lb}. Необходимо построить эквивалентный ему автомат Мили Sa = {Aa, Xa, Ya, da, la}.

По определению эквивалентности имеем Xa = Xb; Ya = Yb. Кроме того,  Aa = Ab, da= db. Остается только построить функцию выходов. Если в автомате Мура db(ai, xj) = as, а lb(as) = yg, то в автомате Мили la(ai, xj) = yg. Другими словами: la(ai, xj) = lb(db(ai, xj)). Таким образом, таблица переходов автоматов Мили и Мура совпадают. А таблица выходов эквивалентного автомата Мили строится так, что в каждую клетку таблицы записывается выходной сигнал, которым отмечено состояние, расположенное в данной клетке.

Пример. Пусть дан автомат Мура:

xj\yi

y1

y1

y3

y2

y3

xj\ai

a0

a1

a2

a3

a4

x1

a1

a4

a4

a2

a2

x2

a3

a1

a1

a0

a0

Тогда эквивалентный ему автомат Мили имеет следующую совмещенную таблицу переходов и выходов:

xj\ai

a0

a1

a2

a3

a4

x1

a1/ y1

a4/ y3

a4/ y3

a2/ y3

a2/ y3

x2

a3/ y2

a1/ y1

a1/ y1

a0/ y1

a0/ y1

Раздел 4.Синтез типовых узлов ЭВМ.

К типовым узлам ЭВМ, предназначенным для хранения и преобразования двоичной информации, относятся различные виды регистров, счетчиков, сумматоров и дешифраторов.

4.1. Регистры

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

Регистры параллельного действия

В регистрах параллельного действия запись числа осуществляется параллельным кодом, т.е. во все разделы регистра одновременно.

Регистр строится на триггерах, число которых равно числу разрядов в хранимом слове. В качестве триггеров используется, как правило, RS- и D-триггера. В зависимости от количества каналов, по которым поступает информация на входы регистра, различают регистры парафазного и однофазного вида. Парафазные регистры характеризуются тем, что информация на каждый разряд поступает по двум каналам (прямому и инверсному), а в однофазных регистрах – по одному каналу (прямому или инверсному). Приведем схему парафазного регистра на синхронных RS-триггерах с асинхронными и установочными входами R и S (рис. 4.1).

Пусть в n-разрядный регистр необходимо записать n-разрядное двоичное число X = xn-1xn-2x1x0. Прямой и обратный коды каждого разряда числа поступают одновременно на входы S и R триггера. Запись числа осуществляется по синхронизирующему сигналу С. Если необходимо прочитать прямой код числа, хранящегося в регистре, необходимо в схему подать сигнал Чтпр (чтение прямое). Аналогично, при подаче сигнала Чтобр (чтение обратное), на выходах конъюнкторов второй группы появится число в обратном коде, а при одновременной подаче сигналов Чтпр и Чтобр будет прочитано число из регистра в парафазном параллельном коде.

Рис.4.1

Схема однофазного регистра на синхронных RS-триггерах с установочными R и S входами отличается от тем, что на вход R регистра инверсный код числа не подается. В этом случае этапу приема числа в регистр предшествует этап сброса регистра в нулевое состояние, который осуществляется по сигналу Уст «0», поступающему одновременно на асинхронные входы R всех триггеров. Далее по сигналу С те триггера, на входы S которых подается единичный сигнал, перейдут в единичное состояние, а остальные останутся в нулевом состоянии. Таким образом, однофазный регистр на RS-триггерах является двухтактным, тогда как парафазный регистр – однотактным. Поэтому для увеличения быстродействия однофазные регистры строятся на D-триггерах, сбрасывать которые в нулевое состояние нет необходимости.

Регистр последовательного действия

В ЭВМ на ряду с параллельным используется также последовательный способ представления двоичной информации, при котором код числа передается по одному каналу последовательно разряд за разрядом в дискретные моменты времени, задаваемые синхроимпульсами. Для приема и выдачи чисел, представленных в последовательном коде, и используются регистры последовательного действия, основу которых составляют регистры сдвига. Регистр сдвига осуществляет операцию сдвига записанного в него двоичного числа влево или вправо на один или несколько разрядов при подаче специального управляющего сигнала «сдвиг». Рассмотрим синтез двухразрядного сдвигающего регистра на D-триггерах. Регистр должен работать следующим образом: в момент прихода синхронизирующего сигнала С число сдвигается в регистре вправо на один разряд. При этом разряды числа, сдвигаемые вправо, поступают на выход регистра, а в освобождающиеся слева разряды вводятся разряды числа, поступившего в последовательном коде на его вход. Имеем следующую кодированную таблицу переходов и функции возбуждения (таблица выходов не строится, ибо выходами регистра являются выходы самих триггеров):

Используя диаграммы Вейча, получаем следующие минимальные дизъюнктивные нормальные формы функций возбуждения триггеров:

Отсюда получаем следующую схему сдвигающего регистра (рис.4.2). С целью устранения гонок и неустойчивых состояний используются двухступенчатые D-триггера.

 Рис. 4 .2

                                                                      

Регистр работает следующим образом. В момент поступления синхроимпульсов (С = 1) в первый триггер записывается очередной разряд числа, поступающего на вход регистра. При С = 0 записанная информация появляется на выходе триггеров. Двухступенчатый D-триггер имеет вид (рис. 4.3):

                                                                    Рис. 4.3

Аналогично строится и n-разрядный регистр сдвига.

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

Рис. 4.4

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

Рис. 4.5

Регистр сдвига на функциональных схемах обозначается следующим образом (рис. 4.6):

           Рис. 4.6

Для указания направления сдвига используется стрелка:

® сдвиг в сторону старших разрядов, ¬ сдвиг в сторону младших разрядов.

4.2. Счетчики

Счетчиком называется типовой узел ЭВМ, предназначенный для подсчета числа входных сигналов (импульсов). По целевому назначению счетчики подразделяются на суммирующие, вычитающие  и реверсивные.

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

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

Основными характеристиками счетчиков являются:

1. Быстродействие, оцениваемое максимальной частотой поступления входных импульсов F = 1/T , Tпериод следования счетных импульсов.

2. Модуль счета или коэффициент пересчета К. Он характеризует число устойчивых состояний счетчика. Например при К = 12 счетчик имеет 12 состояний: от 0 до 11. Если счетчик имеет n разрядов, то Kmax = 2n. Каждому состоянию соответствует n разрядное двоичное число (от 0 до 2n –- 1).

 Суммирующий счетчик

В простейшем случае двоичный счетчик может быть образован из асинхронных Т-триггеров, соединенных последовательно. При этом сигналы счета a поступают на вход Т-триггера младшего разряда счетчика. Выход Q триггера каждого разряда соединен со входом Т соседнего триггера более старшего разряда (рис. 4.7):

Рис. 4.7

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

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

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

Рис. 4.8

В синхронном триггере смена состояний происходит по заднему фронту синхроимпульсов С (рис. 4.9):

Рис. 4.9

Временная диаграмма работы 3-х разрядного асинхронного суммирующего счетчика с последовательным переносом имеет следующий вид (рис. 4.10):

Рис. 4.10

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

где tсч – длительность счетных импульсов, tn – время переключения второй ступени триггера.

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

.

Здесь n- разрядность счетчика, tопр – длительность сигнала опроса, ntn – время полного переключения n разрядов счетчика.

Вычитающий счетчик. Реверсивный счетчик

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

Рис. 4.11

Для построения реверсивного счетчика необходимо объединить схемы суммирующего и вычитающего счетчиков (рис. 4.12):

Рис. 4.12

Здесь при наличии единичного сигнала на управляющей шине I счетчик работает как суммирующий, а при наличии единичного сигнала на управляющей шине II – как вычитающий. Обычно счетчики имеют цепи установки в нулевое и единичное состояния. Схема асинхронного реверсивного счетчика на синхронных JK-триггерах, имеющих асинхронные инверсные установочные входы R и S, представлена на рис.4.13.

Рис. 4.13

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

Счетчики с одновременным, сквозным и групповым  переносом

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

На основании этой таблицы построим диаграммы Вейча для сигналов возбуждения триггеров, рассматривая их как функции состояний триггеров Q1(t), Q2(t) и Q3(t) при a = 1. Имеем:

Из диаграмм получаем следующие выражения для сигналов возбуждения триггеров: T1 = a, T2 = Q1a, T3 = Q1Q2a.

При синтезе n-разрядного счетчика по аналогии получим следующие выражения для сигналов возбуждения триггеров:

T1 = a, T2 = Q1a, T3 = Q1Q2a, T4 = Q1Q2Q3a, …, Tn = Q1Q2Q3Qn1a .

Счетчик, построенный в соответствии с этими уравнениями, носит название счетчика с одновременным или параллельным переносом (рис. 4.14):

Рис. 4.14

В таком счетчике изменение состояния всех триггеров происходит одновременно. Частота работы такого счетчика определяется из следующего выражения:

.

Здесь Δt – время задержки сигнала коньюнктором. Разрядность счетчика с параллельным переносом ограничивается возможностями логических элементов: коэффициентами разветвления и объединения. Поэтому иногда бывает целесообразно строить менее быстродействующую схему, но с использованием только двухвходовых логических элементов. При синтезе такого счетчика достаточно переписать функции возбуждения, полученные ранее, в виде T1 = a; T2 = Q1T1; T3 = T2Q2; T4 = T3Q3;Tn = Tn-1Qn-1. Счетчик, построенный по этим уравнениям, называется счетчик со сквозным переносом (рис. 4.15).

Рис. 4.15

Максимальная частота работы такого счетчика равна                 .

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

Рассмотрим процесс построения такого счетчика. Пусть n разрядов счетчика делятся на группы по k разрядов. Введем обозначения: Tl гр – перенос на вход l-ой группы ; Tl гр j – перенос на вход  j-го разряда в l-ой группы . Примем для простоты  n = 9, k = 3. Тогда формулы, полученные ранее для функций возбуждения, можно представить в виде:

 T1 гр = T1 = 1;  

 T2 гр = Tl гр(Q3Q2Q1) = Q3Q2Q1 = T4;

 T3 гр = T2 гр(Q6Q5Q4) = T7;

 T4 гр = T3 гр(Q9Q8Q7) = T10.

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

Рис. 4.16

4.2.1. Синтез счетчиков с коэффициентом пересчета, не равным 2n 

Рассмотренные схемы n-разрядных счетчиков имеют коэффициент пересчета k=2n. Для многих устройств ЭВМ необходимы счетчики с коэффициентом . Такие счетчики называют еще пересчетными схемами. Эти счетчики получают за счет введения в схему обратной связи, управляющей переходом двоичного счетчика из состояния, соответствующего числу k1, в нулевое состояние.

Синтезируем счетчик с коэффициентом пересчета, равным 5, на Т-триггерах и элементах булева базиса. Такой счетчик имеет пять состояний (от 0 до 4). В исходном состоянии счетчик находится в нуле. После поступления на его вход пяти импульсов он снова должен оказаться в нулевом состоянии. Количество триггеров определяется согласно формуле , где k = 5 – число состояний. Отсюда R = 3. Выходной сигнал       z = 1 должен формироваться на каждый пятый входной сигнал. В результате получаем кодированную таблицу переходов и выходов, а также сигналы возбуждения:

При a = 1 построим следующие диаграммы Вейча:

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

Построим схему счетчика (рис. 4.17):

Рис. 4.17

Аналогичным образом может быть синтезирован вычитающий и реверсивный счетчики с различными коэффициентами пересчета. При синтезе реверсивного счетчика появится дополнительный входной сигнал y, управляющий режимом работы счетчика. При сигнале y = 0 синтезируем, например, суммирующий счетчик, а при y = 1 – вычитающий. Кодированную таблицу переходов строим одну.

4.2.2. Счетчики на сдвигающих регистрах

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

После каждого счетного импульса осуществляется сдвиг этой единицы на один разряд, и получается переход счетчика в новое состояние. Такой счетчик осуществляет подсчет сигналов по модулю n, т.е. k = n, где n – число разрядов счетчика. Такой счетчик называют еще электронным коммутатором. Основным преимуществом такого счетчика является простота дешифрации его состояний и высокое быстродействие. Недостаток заключается в том, что при больших значениях k требуется большое число триггеров. Эти счетчики обычно строятся на D-, RS- и JK-триггерах. Построим схему такого счетчика на синхронных двухступенчатых RS-триггерах при k = n = 5 (рис. 4.18):

                                                                          Рис. 4.18

Такой счетчик имеет 5 состояний: 10000 – исходное состояние, затем: 01000, 00100, 00010, 00001 и вернулись в исходное состояние 10000.

Кодовое кольцо

Если в приведенной схеме счетчика на кольцевом регистре прямой выход последнего триггера соединить со входом R первого триггера, а инверсный выход – со входом S, то получится кодовое кольцо или счетчик Джонсона. Такой счетчик будет иметь число k = 2n. В нашем примере это состояния: 10000, 11000, 11100, 11110, 11111, 01111, 00111, 00011, 00001, 00000, 10000 и т.д., т.е. 5-ти разрядный счетчик имеет коэффициент пересчета, равный 10. Путем исключения из схемы одного «избыточного» состояния можно сделать счетчик Джонсона и с нечетным коэффициентом пересчета k = 2n1.

4.2.3. Полиномиальные счетчики

Полиномиальные счётчики строятся на основе n-разрядного регистра сдвига с линейными обратными связями (с сумматорами по модулю два в цепи обратной связи).

В качестве примера рассмотрим схему счётчика при n = 4 (рис. 4.19):

Рис. 4.19

Последовательность состояний регистра сдвига представлена на рис. 4.20 (состояние 0 0 0 0 запрещено).

Рис. 4.20

Работа схемы описывается с помощью квадратной матрицы С, связывающей данное  и последующее  состояния. Для нее состояния триггеров  q1, q2, q3  и  q4 в момент времени (t + 1) определятся следующим образом:

 

 

 

или в матричной форме

                                                                             

или                                             ,                                                 

где

.                                                

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

Периодические свойства последовательностей на выходах счетчика определяются характеристическим многочленом , который является определителем матрицы  (Е – единичная матрица).

Если многочлен  неприводим и примитивен, то счетчик будет формировать последовательность максимальной длины или М- последовательность. Для данного примера характеристический многочлен j (х) неприводим, примитивен и имеет следующий вид:  = x4  x 1.

Вероятности появления символа 1   и символа 0  для М-последовательности определяются следующим образом:

                     ,       .                                                                       

Известен оригинальный метод построения счетчика на регистре с s-шаговым сдвигом за один рабочий такт (). Запишем следующие соотношения: ,  и т.д.  

Пусть s = 2.  Тогда матрица  будет имеет вид:

.                  

По матрице построим схему счетчика:

 Рис. 4.21

Последовательность состояний регистра сдвига при s = 2 (пунктирные линии) и при s = 1 (сплошные линии) показаны на рис. 4.22:

 

Рис. 4.22

Как видно из рисунка, счетчик также формирует М-последовательность. Возьмем s = 3. Матрица функционирования счетчика в этом случае имеет вид:

.                       

Рассмотрим схему счетчика при s = 3 (рис. 4.23):

 

Рис. 4.23

В данном случае D-триггер и сумматор по модулю два в его обратной связи представляют собой T-триггер. Поэтому эту схему можно преобразовать следующим образом (рис. 4.24), и она может быть построена только на D- и T-триггерах, соединенных в кольцо (рис. 4.25).

Рис. 4.24

Рис. 4.25

Здесь необходимо отметить, что для того, чтобы каждый выходной разряд счетчика также формировал  последовательности максимальной длины, необходимо, чтобы число шагов s и период последовательности M были взаимно простыми числами, т.е. (M, s) = 1. Поскольку в данном примере это условие не выполняется, диаграмма последовательности состояний регистра разбивается на несколько периодов меньшей длины (рис. 4.26):

Рис. 4.26

Пусть s = 4. Матрица в этом случае имеет вид:

.                     

Схема счетчика приведена на рис. 4.27.

Рис. 4.27

Эта схема может быть построена только на Т-триггерах и одном сумматоре по модулю два (рис. 4.28):

Рис. 4.28

 В общем случае схема полиномиального счетчика на основе n-разрядного регистра сдвига с линейными обратными связями представлена на рис. 4.29:

                                                            Рис. 4.29

Если коэффициент Ci = 1, то выход i-го триггера подается на вход сумматора по модулю 2, если же Ci = 0, то – не подается. В соответствии с коэффициентами многочлена однозначно определяется структура обратной связи регистра сдвига. Есть таблица всех неприводимых многочленов, из которой находят многочлены, представленные в 8-ричной форме.

Например, характеристический многочлен  = x4  x 1 в этой таблице будет иметь следующий вид:

               =  .         

В двоичном виде этом многочлен запишется как: 10 011, или в 8-ричном виде – 23. По такой записи многочлена однозначно строится схема полиномиального счетчика.    

4.3. Дешифраторы

Дешифратор представляет собой комбинационную схему с n входами и m выходами. Назначение дешифраторов – обеспечить на каждом из выходов сигнал, равный единицы, только при вполне определенной комбинации входных сигналов. Пусть входные шины дешифратора пронумерованы целыми числами, начиная с нуля. Тогда при подаче на входы дешифратора сигналов, соответствующих n-разрядному двоичному числу L, единичный выходной сигнал появится на L-м выходе. Например. Пусть на входы дешифратора подается комбинация сигналов 1100(2) = 12(10). Тогда единичный сигнал появится только на 12-м выходе дешифратора, а на остальных выходах будут нулевые сигналы. Максимальное число выходов дешифратора равно 2n. Такие дешифраторы называются полными.

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

 . (4.1)

                            Рис. 4.30

Каждая переключательная функция уj представляет собой конституенту единицы и поэтому равна единице на одном наборе, номер которого равен j.

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

4.3.1. Линейные дешифраторы

Линейные дешифраторы являются наиболее быстродействующими. Они представляют собой одну ступень логических элементов, которая непосредственно реализует систему (4.1) ПФ. Такой дешифратор содержит 2n конъюнкторов с числом входом n у каждого. В качестве примера приведем схему дешифратора с парафазными входами при n = 3, m=8 (рис.4.31).

Рис. 4.31

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

Параметры линейного дешифратора: быстродействие: tзадержки = t&, число логических элементов 2n, число входов у элементов n, общее число входов логических элементов вл = n2n.

4.3.2. Прямоугольные дешифраторы

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

Рис. 4.32

Для двухступенчатого прямоугольного дешифратора справедливы следующие соотношения (4.2):

,  (4.2)

      где    при нечетном n,   при четном n.                        

При таком разбиении общее число элементов И в первой и второй ступени равно  (n четное), а общее число входов у этих элементов равно , т.к. в первой ступени элементы имеют n/2 входов (формула справедлива при n > 2). Быстродействие: tзадержки = 2t&, число элементов в выходном каскаде (ступени) 2n, число входов у элементов в выходном каскаде равно 2, общее число входов во второй ступени равно 2n+1.

Для прямоугольного дешифратора фактором, ограничивающим число разрядов дешифрируемого слова, чаще всего является нагрузочная способность элементов входного регистра или элементов первого каскада. При достаточно большом числе разрядов дешифрируемого слова (n ³ 6) и ограниченной нагрузочной способности элементов (F £ 10) полный прямоугольный дешифратор строится с числом ступеней больше двух. При этом на элементы оконечной ступени подаются сигналы с 2-х прямоугольных дешифраторов предоконечной ступени, на каждый из которых подаются сигналы с двух предшествующих прямоугольных дешифраторов и т.д. 1-й каскад дешифратора строится из линейных дешифраторов. В большинстве случаев оказывается достаточным использовать 3 каскада. На рис. 4.33 приведена схема трехступенчатого прямоугольного дешифратора на 9 входов и 512 выходов.

Рис. 4.33

На рис. 4.34 приведена схема трехступенчатого дешифратора на 12 входов, имеющего 4096 выходов.

Рис. 4.34

4.3.3. Пирамидальные дешифраторы

Пирамидальные дешифраторы, так же как и прямоугольные, относятся к разряду многоступенчатых дешифраторов, особенностью которых является применение во всех ступенях дешифрации двухвходовых элементов И с обязательным подключение выхода элемента i-ой ступени ко входам только двух элементов (i+1)-ой группы. Число ступеней N в таком дешифраторе на единицу меньше разрядности n дешифрируемого слова, т.е. N = n1, а число элементов И в каждой из ступеней определяется из выражения B = 2i+1, где – номер ступени пирамидального дешифратора.

Пирамидальные дешифраторы строятся следующим образом. В начале получаются все произведения двух аргументов: , ,  и . Затем получаются все конъюнкции  3-х аргументов путем умножения каждого из полученных произведений 2-х аргументов на  и , затем все конъюнкции 4-х аргументов. Другими словами, каждая функция системы (4.1) формируется поэтапно. Это соответствует записи системы (4.1) в следующем виде:

                                          .                                 (4.3)

Принцип построения пирамидального дешифратора наглядно виден из примера построения такого дешифратора на 16 выходов (рис.4.35).

                                                Рис.4.35

Быстродействие прямоугольного дешифратора определяется временем задержки, равным (n – 1)t&, а общее число входов у элементов равно:

.

Недостатком пирамидального дешифратора следует считать большое число ступеней, снижающих быстродействие дешифратора. Сравним по числу входов у элементов И и по быстродействию рассмотренных дешифраторы:

 

При  n®¥                         .

т.е. при больших значениях n прямоугольный дешифратор почти в 2 раза экономичнее пирамидального и в тоже время имеет большее быстродействие:

.

Преимущественное развитие получили прямоугольные дешифраторы.

4.4. Сумматоры

Сумматор является основным узлом арифметического устройства ЭВМ и предназначается для выполнения операции арифметического суммирования двух чисел с фиксированной запятой. В дальнейшем будем считать, что все числа, поступающие на входы сумматора, меньше единицы, т.е. запятая фиксирована после знакового разряда. Слагаемые и сумму будем обозначать соответственно буквами A, B и S, где  A = amam-1aia1;                B = bmbm-1bib1;   S = smsm-1sis1.

Классификация сумматоров.

1.  В зависимости от основания системы счисления и принятой системы кодирования различают двоичные, троичные, десятичные, двоично-десятичные и др. сумматоры.

2. По способу организации процесса суммирования различают сумматоры комбинационного и накапливающего типов. Сумматор комбинационного типа – это логическое устройство, обеспечивающее получение сигналов суммы и переноса при одновременной подаче кодов слагаемых. При снятии сигналов хотя бы одного слагаемого значение суммы на выходе комбинационной схемы исчезает, т.к. такой сумматор не имеет памяти.

Сумматор накапливающего типа строится на основе Т-триггеров. Исходные числа (слагаемые), поданные на вход сумматора одно за другим, накапливаются в сумматоре в виде суммы и сохраняются после прекращения подачи входных сигналов.

3. По способу обработки многоразрядных чисел различают сумматоры последовательного, параллельного и параллельно-последовательного действия. В последовательном сумматоре производится поразрядная обработка слагаемых А и В. Пары разрядов аi и вi этих чисел поступают в сумматор последовательно от младших разрядов к старшим. В параллельном сумматоре числа А и В поступают одновременно и поэтому обработка всех разрядов слагаемых производится также одновременно. В параллельно-последовательном сумматоре все числа разбиваются на a групп по b разрядов в каждой группе. Внутри групп числа суммируются параллельно, а сами группы разрядов подаются на входы сумматора последовательно.

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

Рассмотрим схемы двоичных сумматоров.

4.4.1. Одноразрядные двоичные сумматоры

Сумматор SM служит для образования сигнала суммы Si по сигналам трех цифр  аi, вi и рi  i-го разряда и формирования сигнала переноса рi+1 в следующий старший разряд. Одноразрядный сумматор принято обозначать на схемах в следующем виде (рис. 4.36). Кроме сумматоров существуют полусумматоры, которые осуществляют сложение двух чисел (рис. 4.37).

                                        

                                            Рис. 4.36                                      Рис.4.37

       Одноразрядный комбинационный сумматор

Закон функционирования сумматора при сложении трех цифр определяется следующей таблицей истинности:

На основе таблицы строятся диаграммы Вейча и получаются минимальные ДНФ функций si и pi+1.

,                .

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

Рис. 4.38

Эта схема, имеющая парафазные входы, обладает большим быстродействием, т.к. число уровней здесь r = 2, а суммарное число входов у логических элементов равно 25.

Полученную схему можно упростить, если рассматривать si как функцию 4-х переменных si = f(аi, вi, pi, pi+1).

Отсюда имеем:

 

.                                           

Схема представлена на рис. 4.39. Эта схема, имеющая однофазные входы, обладает худшим быстродействием, т.к. r = 6. Суммарное число входов равно здесь 17, т.е. последняя схема несколько проще.

Рис. 4.39

Схема с однофазными входами на элементах И-НЕ и ИЛИ-НЕ

Преобразуем выражения для сигналов переноса и суммы: следующим образом:       ,=                 =.

Схема с однофазными входами на элементах И-НЕ и ИЛИ-НЕ имеет следующий вид (рис. 4.40). Число уровней r = 5, суммарное число входов равно 20. В зависимости от назначения следует использовать ту или иную схему.

Рис.4.40

Одноразрядный накапливающий сумматор

Одноразрядным сумматором накапливающего типа является схема, суммирующая поочередно поступающие на ее вход цифры слагаемого и переноса с запоминанием результата суммирования. Для запоминания результата сложения на выходе рассмотренных комбинационных сумматоров можно установить триггеры (триггера R-S и D-типов). Совместно с триггером комбинационный сумматор будет выполнять функции накапливающего сумматора. Роль накапливающего сумматора может выполнять и счетный триггер со схемой формирования переноса, на счетный вход которого все слагаемые должны подаваться последовательно во времени. В этом случае суммирование трех слагаемых будет проходить за 3 такта (рис. 4.41):

Рис. 4.41

Рассмотрим работу устройства. В первый момент времени t1 через схему ИЛИ1 на вход Т-триггера, который был предварительно установлен в нулевое состояние, поступает цифра ai и запоминается. После завершения переходных процессов в триггере в момент времени t2 через схему ИЛИ1 поступает цифра вi второго слагаемого. При этом Т-триггер реализует функцию . Наконец в следующий момент времени t3 через схему ИЛИ1 подается цифра переноса из более младшего разряда рi и триггер реализует функцию: 

,

которая совпадает с функцией si, полученной ранее по таблице истинности одноразрядного сумматора. Таким образом по истечении трех тактов в триггере будет находится значение i-го  разряда суммы слагаемых А и В, т.е. si. Сигнал переноса pi+1 формируется комбинационной схемой, стоящей на выходе триггера. В момент времени t3, когда триггер еще находится в состоянии f1, приходит сигнал рi. На выходе И1 имеем:     

Если теперь к f3 добавить через дизъюнкцию aibi, то получится рi+1. Непосредственно aibi получить с помощью конъюнктора нельзя, т.к. они поступают в различные дискретные моменты времени. Поэтому aibi формируются с помощью элемента И2,  реализующего функцию .

Окончательно сигнал переноса pi+1 на выходе ИЛИ2 равен:

.

Этот сигнал совпадает с переносом, формируемом в комбинационном сумматоре на выходе рi+1. Недостаток рассмотренного сумматора заключается в том, что он имеет малое быстродействие, поскольку в каждом цикле суммирования число срабатываний триггера может равняться четырем: Уст «0», ai(t1), bi(t2) и рi(t3).

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

Комбинационно-накапливающий одноразрядный сумматор

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

Рис. 4.42

Сумматор работает следующим образом. Сигнал ai подается на вход S  триггера, который был предварительно установлен в нуль (если ai вводится в триггер в парафазном коде, то установка триггера в нуль не делается).

Цифра bi второго слагаемого и перенос рi поступают в комбинационную схему, реализующую функцию сложения по модулю два, т.е. Сигнал f5 поступает на счетный вход триггера, в котором хранится цифра ai первого слагаемого. В результате в триггере образуется код суммы, т.е.

. 

При подаче синхроимпульсов в триггере образуется сумма si, которая появится на выходе в момент окончания действия синхроимпульса. Если ai будет поступать в триггер в парафазном коде, то операция сложения  будет выполняться за один такт: вначале такта в триггер поступает ai (СИ = 0), а при     СИ = 1 поступают bi и pi, т.е. такой сумматор обладает большим быстродействием по сравнению с сумматором накапливающего типа.

4.4.2. Многоразрядные сумматоры

В зависимости от того, каким образом в ЭВМ передаются числа, может быть два способа сложения: последовательный и параллельный. При последовательном способе сложения при передаче каждого слагаемого используется один канал, по которому код числа передается в виде временной последовательности цифр разряд за разрядом. Если для передачи каждого разряда числа предусмотрен отдельный канал, то применяется параллельный способ сложения.

Последовательный сумматор

Последовательный сумматор должен преобразовывать последовательные коды слагаемых в последовательный код суммы этих слагаемых. Такие сумматоры обычно строятся на основе одноразрядного комбинационного сумматора, в котором для запоминания сигнала переноса используется D-триггер (рис. 4.43):

                  

Рис. 4.43

При последовательном суммировании разряды ai и bi слагаемых А и В, начиная с младших, поступают на входы одноразрядного комбинационного сумматора SM с выходов сдвигающих регистров. Значения разрядов суммы Si заносятся в освобождающиеся разряды одного из сдвигающих регистров. На вход pi сумматора SM поступает сигнал переноса, который был получен в предыдущем такте при суммировании ai-1, bi-1 и Pi-1. Для запоминания сигнала переноса используется D-триггер. Очевидно, для сложения m разрядных чисел А и В используется m+1 такт (в последнем (m+1)-ом такте перенос из самого старшего разряда поступает на вход сумматора, где суммируется с нулевыми значениями цифр слагаемых). Поэтому такой сумматор обладает очень низким быстродействием. С целью ускорения процесса сложения используются параллельные сумматоры.

Параллельные сумматоры с последовательным переносом

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

Простейшим является параллельный комбинационный сумматор с последовательным переносом, схема которого приведена на рис. 4.44:

Рис. 4.44

Здесь сигнал переноса, который возникает в каком либо разряде, распространяется к старшим разрядам по цепочке сумматоров, т.е. в таком сумматоре цепь переноса получается последовательной. Поэтому время сложения двух m-разрядных чисел будет равно m×tзр, где tзр – время задержки сигнала в цепях формирования переноса одноразрядного сумматора.

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

Параллельный сумматор со сквозным переносом

При построении сумматора со сквозным переносом представим выражение для сигнала переноса в следующем виде:

                ,

где Ci = aibi – собственный перенос, сформированный в i-м разряде;  

признак распространения переноса, образованного в предыдущих разрядах, через i-разряд; Tiрi – транзитный перенос, т.е. перенос из предыдущих разрядов, проходящий через i-й разряд.

С учетом полученного выражения для рi+1 схема сумматора со сквозным переносом может быть представлена в виде рис. 4.45:

Рис. 4.45

В этой схеме предполагается, что в каждом i-ом одноразрядном комбинационном сумматоре формируется кроме si еще и Ci = aibi и . Время суммирования m разрядных чисел равно tå =  tзå + (m1)tзр, где tзå – время задержки в одноразрядном сумматоре сигнала на выходе S (суммы), tзр – задержка в цепях формирования переноса. Отличительная особенность таких сумматоров заключается в том, что формирование переноса производится до образования цифры суммы в каждом разряде, что и способствует увеличению быстродействия. 

Параллельный сумматор с одновременным переносом

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

, , …, , .

Подставив значение р2 в уравнение для р3, значение р3 – в р4 и т.д., получим логическое уравнение переноса в (i + 1) разряд, выраженное через значения разрядов слагаемых имеет вид:

.

Из этого уравнения следует, что на выходе i-го разряда перенос рi+1 возникает тогда, когда он образован в данном разряде, или если он был образован в некотором предыдущем разряде, а во всех последующих разрядах, включая данный, выполняется условие распространения переноса. Следовательно, перенос в каждом разряде может быть выработан одновременно с запуском переноса р1 в младший разряд.

Из этого выражения  может быть образована система уравнений для сумматора с одновременным переносом. Так система уравнений для трехразрядного сумматора имеет следующий вид:

, .

На основании записанной системы уравнений построим схему сумматора с одновременным переносом (рис. 4.46):

Рис. 4.46

Т.к. слагаемые А и В в такой схеме подаются параллельно, то и переносы формируются одновременно. Время суммирования чисел в таком сумматоре равно                                     tå =  tзå  + tзр,

где tзå – время задержки формирования сигнала суммы si, tзр – время задержки формирования сигнала переноса.

Схема формирования сигнала переноса на элементах булевого базиса  в каждом разряде трехуровневая (один уровень – вычисление Ti и Сi, второй и третий уровни получение pi+1 по сформированным Ti и Сi). Поэтому tзр=3Dt, где Dt – задержка сигнала в одном логическом элементе. Такие сумматоры являются самыми быстродействующими.

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

Параллельные сумматоры с групповым переносом

В сумматорах с групповым переносом все разряды разбиваются на  групп по  разрядов в каждой группе (обычно  = 4¸6). В пределах каждой из групп организуется одновременный или сквозной перенос. Между группами перенос может быть либо одновременным, либо сквозным. Например, 12-ти разрядный сумматор с одновременным переносом между группами (в каждой группе 4 разряда) имеет следующий вид (рис. 4.47):

Рис. 4.47

Здесь каждый 4-х разрядный сумматор с одновременным переносом строится так же, как это было рассмотрено ранее.

Cjгр – сигнал переноса из j группы (собственный перенос).

Tjгр – сигнал условия прохождения через j-ю группу (признак транзитного переноса).

Tjгр =TlTl-1Tk, где k – номер младшего разряда в группе, l номер старшего разряда в группе.

Ti – признак прохождения переноса через i-й разряд.

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

Раздел  5. Абстрактный синтез конечных автоматов

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

5.1. Представление событий в автоматах

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

Пусть Y{y1, y2, …, yG} – выходной алфавит конечного автомата S с фиксированным начальным состоянием a0. Тогда каждой букве yj выходного алфавита можно поставить в соответствие множество входных слов Sj (x1, x2,…, xF), которые вызывают появление на выходе автомата буквы yj. Определенное таким образом множество слов Sj (x1, x2, …, xF) называют событием, представленным в автомате выходным сигналом yj.

Поэтому для задания конечного автомата, имеющего выходной алфавит Y{y1, y2, …, yG}, достаточно разбить множество всех возможных входных слов на G событий S1, S2, …, SG, представленных в автомате выходными сигналами y1, y2, …, yG соответственно. Для частичного автомата необходимо, кроме того, задать множество Sз запрещенных слов. Таким образом, конечный автомат может быть задан таблицей, устанавливающей соответствия между событиями и буквами выходного алфавита. Зная набор событий Sj, можно не пользуясь таблицами переходов и выходов найти реакцию автомата на любое входное слово, для чего достаточно определить  множество каких слов входного алфавита оно входит (т.е. какому событию принадлежит).

Соответствие событий буквам выходного алфавита:

Событие

Буква

S1 (x1, x2,…, xF)

S2 (x1, x2,…, xF)

SG (x1, x2,…, xF)

Sз  (x1, x2,…, xF)

y1

y2

yG

Для описания автоматов на языке регулярных событий вводят ряд операций над событиями, т.е. строят алгебру событий. Мы рассмотрим алгебру событий, введенную Клини и усовершенствованную академиком Глушковым В. М.

5.2. Операции в алгебре событий

Алгебра событий включает три операции: дизъюнкцию (объединение) событий, произведение событий и итерацию событий.

Дизъюнкцией событий называют событие S = S1 v S2 v …v SG, состоящее из всех слов, входящих в события S1, S2, …, SG.

Пример. Событие S1 содержит слова x1, x1x1, x2x1, т.е. S1 = (x1, x1x1, x2x1), а
S2 = (x2, x1x2). Тогда S = S1 v S2 = (x1, x2, x1x1, x1x2, x2x1).

Произведением событий называется событие , состоящее из всех слов, полученных приписыванием к каждому слову события S1 каждого слова события S2, затем слова события S3 и т.д.

Пример. При тех же событиях S1 и S2,  = (x1x2, x1x1x2, x2x1x2, x1x1x2, x1x1x1x2, x2x1x1x2). Произведение событий не коммутативно, т.е. . Поэтому следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий  можно сказать, что событие S2 умножено на событие S1 справа, а событие S1 на S2 – слева.

Третьей операцией, применяемой в алгебре событий, является одноместная операция итерация, которая применима только к одному событию. Для обозначения итерации вводят фигурные скобки, которые называются итерационными. Итерацией события S называется событие {S}, состоящее из пустого слова e и всех слов вида S, SS, SSS и т.д. до бесконечности, т.е.:{S} = e v S v SS v SSS v …

Пример. S = (x2, x1x2). Тогда {S} = (e, x2, x2x2, x2x2x2, …, x1x2, x1x2x1x2, …, x2x1x2, x1x2x2, …)

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

Теорема: Любые регулярные выражения и только они представимы в конечных автоматах.

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

Рассмотрим, как можно совершить переход от описательной формы задания алгоритмов работы КА к представлению этих алгоритмов в виде регулярных выражений. С целью упрощения такого перехода вводят основные события, из которых с помощью операций дизъюнкции, умножения и итерации можно составить более сложные события, соответствующие заданному алгоритму работы автомата. За основные события принимают такие события, которые более часто встречаются в инженерной практике при синтезе схем ЭВМ.

Пусть дан конечный алфавит X = (x1, x2, …, xm).

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

5.3. Система основных событий

В эту систему мы включим те из наиболее часто встречающихся событий, которые используются при записи регулярных выражений. Пусть дан алфавит X{x1, x2, …, xm}.

1. Событие, состоящее из всех слов входного алфавита (всеобщее событие):
F = {x1 v x2 v …v xm}

2. Событие, содержащее все слова, оканчивающиеся буквой xi:
S = {x1 v x2 vv xi vv xm} xi = Fxi.

3. Событие, содержащее все слова, оканчивающиеся отрезком слова l1:
S = F l1.

4. Событие, содержащее все слова, начинающиеся с отрезка слова l1 и оканчивающиеся на l2: S = l1 F l2.

5. Событие, содержащее только однобуквенные слова входного алфавита:
S = x1 v x2 v …v xm.

6. Событие, содержащее только двухбуквенные слова входного алфавита:
S = (x1 v x2 v …v xm)( x1 v x2 v …v xm).

7. Событие, содержащее все слова длиной r:

S = (x1 v x2 v…v xm)(x1v x2 v…v xm)…(x1 v x2 v…v xm) - r членов.

8. Событие, содержащее все слова, длина которых кратна r:

S = {(x1 v x2 v…v xm)(x1 v x2 v…v xm)…(x1 v x2 v…v xm)} - r членов

9. Событие, состоящее из всех слов алфавита X{x1, x2}, не содержащих комбинации букв x1x1 и оканчивающихся буквой x2:         S = {x2 v x1 x2}.

10. Событие, состоящее из всех слов алфавита X{x1, x2}, не содержащих серии из r букв x1 и оканчивающихся буквой x2:

S = {x2 v x1x2 v x1x1x2 v … v x1x1x1x2} - (r – 1) членов.

Рассмотрим пример составления регулярного выражения.

Пример. Записать в виде регулярного выражения алгоритм работы автомата, сравнивающего два двоичных числа, представленных в последовательном коде. Количество разрядов числа – произвольно. Окончание чисел фиксируется подачей на вход автомата сигнала xs. Если число, поданное на первый вход автомата, меньше числа, поданного на второй вход, то КА выдает сигнал y1, если больше – то y2, если оба числа равны – то y3. Числа подаются на входы автомата младшими разрядами вперед. На входы автомата сравнения одновременно может поступить одна из четырех комбинаций сигналов 00, 01, 10, 11, которые закодируем следующим образом x00=00, x01=01, x10=10, x11=11. При этом будем считать, что первая цифра каждой комбинации относится к первому входу, а вторая – ко второму входу. Таким образом, входной алфавит автомата включает пять букв X{x00, x01, x10, x11, xs}, а выходной – три буквы Y{y1, y2, y3}:

-------------------------

КА

----------

Х{x00, x01, x10, x11, xs}

Y{y1, y2, y3}

 

Два двоичных числа равны, если равны цифры в любых одинаковых разрядах. Поэтому событие, заключающееся в поступлении на вход автомата равных чисел, состоит из всех возможных слов, содержащих буквы x00 и x11. То есть S3 = {x00 v x11} xs.

События, представленные в автомате сигналами y1 и y2, можно записать соответственно в виде:

S1 = {x00vx01vx10vx11}x01{x00vx11}xs,   S2 = {x00vx01vx10vx11}x10{x00vx11}xs.

 События  S1, S2 и S3 не охватывают всего множества слов, которые могут быть записаны в алфавите X{x00, x01, x10, x11, xs}, т.к. в эти события входят только слова, оканчивающиеся буквой xs. Слова, не входящие в S1, S2 и S3, должны быть представлены в автомате пустой буквой e: .

Очевидно, что записанные выражения можно упростить, если входные сигналы 00 и 11 закодировать одной буквой, например xr. Такое кодирование возможно, т.к. КА одинаково реагирует на эти комбинации: S3 = {xr} xs,

S1={xrvx01vx10}x01{xr}xs, S2 = {xrvx01vx10}x10{x00vx11}xs, .

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

S1 v S2 = S2 v S1 – закон коммутативности;

(S1v S2) v S3 = S1 v (S2 v S3) = S1 v S2 v S3законы ассоциативности;

  законы ассоциативности; 

  закон дистрибутивности; 

{{S}} = {S};

; 

{{S1} v {S2}} = {S1 v S2};

{e} = e;

eS = Se = S .

5.4. Методы абстрактного синтеза

Задача абстрактного синтеза заключается в составлении таблиц переходов и выходов автоматов по заданным условиям его функционирования, представленным в форме регулярных выражений. Абстрактный синтез обычно выполняется в 2 этапа:

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

На втором этапе производится минимизация количества внутренних состояний заданного автомата.

Синтезируемый автомат может быть задан либо как автомат Мура, либо как автомат Мили. Поскольку для автомата Мура всегда можно построить эквивалентный автомат Мили, то достаточно рассмотреть алгоритм синтеза автомата Мура, который проще автомата Мили.

Алгоритм синтеза автомата Мура

Рассмотрим пример абстрактного синтеза автомата для случая, когда регулярные отношения составлены без применения операции итерации. Составим отмеченную таблицу переходов автомата, имеющего входной алфавит X{x1, x2} и реализующий следующий алгоритм:

S1 = x1x2 v x1x1x1,

S2 = x1x2x2 v x2x2,

Sзапр. = x1 v x2x2x2.

При синтезе условимся начальное состояние автомата обозначать цифрой 0, а остальные состояния – десятичными числами 1, 2, 3 и т.д. Очевидно, это самый простой, хотя и не очень экономный по числу используемых внутренних состояний автомата. Алгоритм синтеза заключается в следующем. Фиксируется начальное состояние и для входного слова, содержащего r букв, назначается r внутренних состояний. Переходы в автомате определяются так, что первая буква входного слова переводит автомат из начального состояния 0 в состояние 1, вторая буква из 1 в 2 и т.д. Аналогичные последовательности внутренних состояний назначаются для всех остальных слов. Затем все конечные состояния, в которые автомат попадает после подачи слов, входящих в событие Si, отмечаются выходными сигналами yi.

Для того, чтобы система переходов автомата была определенной, для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. Например, для регулярного события S1 первая буква x1 переводит автомат из начального состояния 0 в состояние 1, вторая буква x2 – из 1 в 2:

S1 =

|

x1

|

x2

|

v

|

x1

|

x1

|

x1

|

 

0

 

1

 

2

 

0

 

1

 

3

 

4

S2 =

|

x1

|

x2

|

x2

|

v

|

x2

|

x2

|

 

0

 

1

 

2

 

5

 

0

 

6

 

7.

Поскольку первая буква второго слова x1x1x1, входящего в S1, также есть x1, то она переводит автомат из начального состояния 0 в 1. Вторая буква x1 переводит автомат из 1 в 3, третья – из 3 в 4.

Первые две буквы слова x1x2x2, входящего в S2, совпадают с первым словом события S1. Поэтому первые две буквы этого слова должны последовательно переводить автомат из 0 в 1, и из 1 в 2. Дальнейшие состояния обозначим числами 5, 6 и 7. Получившаяся в результате форма записи определяет разметку мест регулярных выражений.

Местами регулярного выражения называют промежутки между двумя буквами, между буквой и знаком дизъюнкции, а так же между буквой и скобкой. Кроме того, вводят начальное место, обозначаемое цифрой 0 и конечные места, отождествляемые с концом каждого слова. Для запрещенного события Sзапр последовательность событий можно не назначать. Для размеченных регулярных выражений составляется отмеченная таблица переходов.

 уg

е

е

y1

e

y1

y2

e

y2

e

x j/ai

0

1

2

3

4

5

6

7

*

x1

1

3

*

4

*

*

*

*

*

x2

6