Применение автомата Мура для решения элементарных логических задач | Статья в журнале «Молодой ученый»

Авторы: ,

Рубрика: Технические науки

Опубликовано в Молодой учёный №11 (145) март 2017 г.

Дата публикации: 20.03.2017

Статья просмотрена: 212 раз

Библиографическое описание:

Дроздова И. И., Загинайло М. В. Применение автомата Мура для решения элементарных логических задач // Молодой ученый. — 2017. — №11. — С. 56-62. — URL https://moluch.ru/archive/145/40742/ (дата обращения: 15.08.2018).



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

Принцип микропрограммного управления допускает, что цифровое устройство состоит из двух частей: операционного автомата (ОА) и управляющего автомата (УА) [1]. ОА выполняет элементарные операции (микрооперации) такие как сдвиг, алгебраическое сложение, конъюнкция и дизъюнкция. УА формирует последовательность управляющих сигналов, которые поступают к ОА и это даёт возможность реализовывать более сложные алгоритмы.

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

Для наглядного примера реализуем простейшую микропрограмму, выполняющую заданный порядок действий на основе входных данных. В качестве входных данных принимаются значения регистров RA, RB, RC которые задаются вручную до начала работы микропрограммы.

Опишем принцип работы микропрограммы. Общая схема приведена на рисунке 1.

ГСА вычисления функции Y_СПб

Рис. 1. Общий алгоритм вычисления формулы S

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

Функциональный алгоритм разработаем согласно входным данным. Сначала выполним загрузку входных данных в регистры RA, RB, RC. При составлении алгоритма необходимо уменьшить разнообразие команд, а также уменьшить количество операторных вершин. Из-за того, что невозможно загрузить за один такт работы данные сразу в три регистра, осуществим это за два такта. За первый так параллельно загрузим данные в регистры RA и RB с помощью шин Z1 и Z2, а за второй — в регистр RC через шину Z1.

Далее необходимо построить операционный автомат. Чтобы построить структурную схему необходимо обозначить набор комбинационных схем: двуместные: {Sum, Sub, And}; одноместные: {Not, L2, L3, R1, R2, R3 }; распределить связи между регистра и локальными шинами А1, А2, А3: А1 = {RA, RB, RC, RD, RE}, А2 = {RA, RB, RD, RF, RE}, А3 = {RA, RB, RC, RD, RF, RE}; и обозначить обратные связи шин Z1 и Z2 с регистрами памяти: Z1 = {RA, RC, RD, RF, RE}, Z2 = {RB, RD, RF, RE}.

Каждое элементарное действие в схеме может выполняться только при наличии определённого управляющего сигнала yn (микрооперации):

y1–y3 — загрузка начальных данных на шины.

y4–y12 — загрузка данных в регистры памяти.

y13–y28 — загрузка из памяти на шины операндов А1, А2, А3.

y29–y31 — загрузка результатов двуместных операций на шину Z2.

y32–y37 — загрузка результатов двуместных операций на шину Z1.

Согласно с полученными данными формируем операционный автомат (Рис. 2).

Операционный автомат1.jpg

Рис. 2. Структурная схема операционного автомата

Шинный формирователь — это комбинационная схема, которая обеспечивает соответствие бита информации, который принимается на шину и проводника.

Формулы для i-го бита шинного формирователя Аі:

;

;

;

Формулы для i-го бита шинного формирователя Zi:

;

;

Формулы для i-го бита шинного формирователя в заданном базисе:

Рис. 3. Фрагмент схемы шинного формирователя

В результате получаем граф-схему алгоритма вычисления формулы S. Она служит начальными данными для синтеза управляющего автомата.

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

Порядок синтеза автомата Мура [2]:

На первом этапе начальная и конечная вершины обозначаются одним состоянием. Затем отдельным состоянием обозначается вход каждой операторной вершины.

Построение таблицы переходов сводится к формированию по обозначенной ГСА таблицы, которая содержит столбцы:

am — начальное состояние

k(am) — код начального стостояния

as — следующее состояние

k(as) — код следующего состояния

X — логическое условие, при котором выполянется переход

Y — мокрокоманды, которые выполняются при переходе

F — функции возбуждения памяти

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

Построим таблицу дла автомата Мура (Табл. 1), проверка RD=0 обозначена как Х1, проверка RD<0 обозначена как Х2, код операции (КОП) — как Х3, проверка RA

Таблица 1

Прямая структурная таблица для автомата Мура

am

K(am)

as

K(as)

X

Y

F

a0

00000

a1

00001

1

-

S0

a1

00001

a2

00010

1

y1, y2, y4, y5

S1 R0

a2

00010

a3

00011

1

y3, y6, y16, y17, y29, y10

S0

a3

00011

a4

00100

y13, y24, y30, y8

S2 R1 R0

a7

00111

*

S2

a1o

01010

*

S3 R0

a4

00100

a5

00101

1

y21, y19, y30, y8, y18, y32, y0

S0

a5

00101

a6

00110

1

y21, y24, y29, y8, y15, y33, y4

S1 R0

a6

00110

a14

01110

y21, y27, y29, y12

S3

a16

10000

S4 R2 R1

a7

00111

a8

01000

1

y15, y34, y11

S3 R2 R1 R0

a8

01000

a9

01001

1

y16, y27, y29, y12, y18, y33, y7

S0

a9

01001

a14

01110

y26, y22, y30, y10

S1 S2 R0

a16

10000

S4 R3 R0

a10

01010

a11

01011

1

y13, y17, y31, y10

S0

a11

01011

a12

01100

1

y25, y33, y9

S2 R1 R0

a12

01100

a13

01101

1

y21, y24, y30, y8

S0

a13

01101

a14

01110

y23, y35, y11

S1 R0

a16

10000

S4 R3 R2 R0

a14

01110

a15

01111

1

y20, y32, y9

S0

a15

01111

a19

10011

y16, y24, y29, y10

S4 R3 R2

a24

11000

S4 R2 R1 R0

a16

10000

a17

10001

1

y28, y34, y7

S0

a17

10001

a18

10010

1

y21, y27, y30, y6

S1 R0

a18

10010

a0

00000

1

y23, y36, y7

R4 R1

a19

10011

a20

10100

1

y18, y33, y7

S2 R1 R0

a20

10100

a21

10101

y21, y17, y30, y8

S0

a22

10110

S1

a21

10101

a29

11101

1

y21, y14, y29, y6

S3

a22

10110

a23

10111

1

y21, y14, y29, y8

S0

a23

10111

a29

11101

1

y23, y37, y7

S3 R1

a24

11000

a25

11001

1

y13, y19, y30, y10, y18, y32, y7

S0

a25

11001

a26

11010

1

y21, y24, y29, y10

S1 R0

a26

11010

a27

11011

1

y25, y33, y7

S0

a27

11011

a28

11100

1

y21, y24, y29, y8

S2 R1 R0

a28

11100

a29

11101

1

y21, y24, y29, y8

S0

a29

11101

a30

11110

1

y23, y32, y7

S1 R0

a30

11110

a0

00000

1

y26, y22, y29, y8

R4 R3 R2 R1

Функции возбуждения памяти в заданном базисе:

Уравнения выходных сигналов в заданном базисе:

;; ; ;; ;

; ;

Мура маленькая.jpg

Рис.4. Сокращённая схема автомата Мура

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

В дальнейшем эта же задача будет решена на автомате, спроектированном по принципу автомата Мили и проведено экономическое сравнение с данным автоматом.

Литература:

  1. Баркалов А. А., Титаренко Л. А.. Прикладная теория цифровых автоматов.. — Донецк: ДонНТУ, Технопарк ДонНТУ УНИТЕХ, 2010. — 320 с.
  2. Баркалов А. А., Титаренко Л. А.. Синтез операционных устройств. — Донецк: РВА ДонНТУ, 2003. — 306 с.
Основные термины (генерируются автоматически): Мура, операционный автомат, i-го бита, данные, жесткая логика, загрузка результатов, автомат, регистр памяти, структурная схема, управляющий автомат.


Похожие статьи

Применение автомата Мили для решения элементарных...

Прямая структурная таблица для автомата Мили.

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

Анализ математических моделей автоматов Мили и Мура для...

Логическая схема и граф модели УМА Мура данного устройства представлены на рис. 4, иллюстрирует процесс моделирования управляющего микропрограммного автомата Мура.

Методы задания автоматов | Статья в журнале «Молодой ученый»

Иначе говоря, конечный автомат — математическая (алгоритмическая) модель поведения устройств с конечной памятью.

Автомат Мура S2={A, Z, W, δ, λ, а1}, представленный в табл.1.8 в явной форме описывается так

Расширенный конечный автомат для тестирования мобильных...

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

Анализ применения гомоморфных схем шифрования в алгоритмах...

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

Рис. 2. Общая схема машинного обучения над зашифрованными данными. Рис. 3. Структура работы ГОСТ 28147–89.

Обзор аппаратных генераторов случайных чисел

Рис. 1. Схема ГСЧ, построенного на базе фазового квантового шума в лазерном луче.

Случайные числа, полученные в результате дрейфа (погрешности хода) двух генераторов

Фазовое дрожание цифрового сигнала данных (джиттер от англ. jitter) — нежелательные...

Система мониторинга остатка воды в цистернах пожарных машин

Запрос состоит из номера машины, занимающего 5 бит (потенциальная ёмкость системы — до 32 автомобилей), и кода запроса информации с датчиков уровня (2 бита).

Структурная схема подвижной системы представлена на рис. 3.

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

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

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

Построение логических схем с использованием Matlab/Simulink...

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

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Применение автомата Мили для решения элементарных...

Прямая структурная таблица для автомата Мили.

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

Анализ математических моделей автоматов Мили и Мура для...

Логическая схема и граф модели УМА Мура данного устройства представлены на рис. 4, иллюстрирует процесс моделирования управляющего микропрограммного автомата Мура.

Методы задания автоматов | Статья в журнале «Молодой ученый»

Иначе говоря, конечный автомат — математическая (алгоритмическая) модель поведения устройств с конечной памятью.

Автомат Мура S2={A, Z, W, δ, λ, а1}, представленный в табл.1.8 в явной форме описывается так

Расширенный конечный автомат для тестирования мобильных...

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

Анализ применения гомоморфных схем шифрования в алгоритмах...

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

Рис. 2. Общая схема машинного обучения над зашифрованными данными. Рис. 3. Структура работы ГОСТ 28147–89.

Обзор аппаратных генераторов случайных чисел

Рис. 1. Схема ГСЧ, построенного на базе фазового квантового шума в лазерном луче.

Случайные числа, полученные в результате дрейфа (погрешности хода) двух генераторов

Фазовое дрожание цифрового сигнала данных (джиттер от англ. jitter) — нежелательные...

Система мониторинга остатка воды в цистернах пожарных машин

Запрос состоит из номера машины, занимающего 5 бит (потенциальная ёмкость системы — до 32 автомобилей), и кода запроса информации с датчиков уровня (2 бита).

Структурная схема подвижной системы представлена на рис. 3.

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

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

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

Построение логических схем с использованием Matlab/Simulink...

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

Задать вопрос