Студопедия

КАТЕГОРИИ:

АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Рекурентні булеві функції. Теорія кінцевих автоматів

⇐ ПредыдущаяСтр 2 из 2

Рекурентною булевою функцією називається така часова булава функція, яка залежить від аргументів і самої функції у даному такті та попередніх тактах .

Рекурентна булава функція першого роду залежить від аргументів у даному такті і значень функції у попередніх тактах.

Наприклад:

 

     Якщо РБФ-1 залежить тільки від значень самої функції у попередніх тактах и не залежить від входів, вона називається вираженою РБФ -1.

Наприклад:

 

     Такі функції реалізуються з допомогою автономних кінцевих автоматів. При цьому можливо вирішувати задачі синтезу і аналізу АКА.

     Розглянемо задачу синтезу автомата. Необхідно синтезувати автономний кінцевий автомат, який виробляє періодичний двійковий код <000-001-010-100>.

     Составимо діаграму стану автомата (Рис.1).

Рис.3.1.

Таблиця 1

y 1 t 0 1 0 1 0 1 0 1
y 2 t 0 0 1 1 0 0 1 1
y 3 t 0 0 0 0 1 1 1 1
y 1 (t+1) 0 0 1 0 0 0 0 0
y 2 (t+1) 0 0 0 0 1 0 0 0
y 3 (t+1) 1 0 0 0 0 0 0 0

 

 

     Дуги з вершин графу, які не увійшли в заданий код, направляємо у вершину 000. Це дозволить мінімізувати синтизуємий автомат.

     По діаграмі стану автомата составимо його таблицю істинності (табл.1)

 

Составимо логічні рівняння, описуючі роботу автомата

Ці рівняння можливо реалізувати наступною структурною схемою (Рис. 2)

Рис.2

Індивідуальне завдання 1

     Синтезувати АКА, виробляючий двійковий код:

Варіант 1                 <0001-0101-1001-1101>

Варіает2                   <0101-1000-1100-1111>

Варіант 3                 <0100-1000-1101-1110>

Варіант 4                 <0000-0110-1001-1011>

Варіант 5                 <0110-0111-1010-1101>

Варіант 6                 <1000-1010-1100-1110>

Варіант 7                 <1111-0010-0101-0111>

Варіант 8                 <0101-0001-1101-1010>

Варіант 9                 <0110-1011-1110-0001>

Варіант 10               <0101-1001-1100-0011>

Варіант 11               <0000-1000-1011-1110>

Варіант 12               <0100-1000-0001-0010>

Варіант 13               <0111-1011-1101-1110>

Варіант 14               <0001-0111-1001-1111>

Варіант 15               <0101-1011-1101-0011>

Варіант 16               <0110-1110-0000-0010>

Варіант 17               <0111-1011-1110-0010>

Варіант 18               <1001-0110-0001-1101>

Варіант 19               <0101-0110-0111-1000>

Варіант 20               <0111-1000-1001-1010>

Варіант 21               <1011-1100-1101-1110>

Варіант 22               <1110-1111-0001-0101>

Варіант 23               <0101-0100-0011-0001>

Варіант 24               <0111-1100-1111-0100>

Варіант 25               <0011-0001-1101-1001>

Варіант 26               <0111-1110-1111-0011>

Варіант 27               <1000-0111-0110-0101>

Варіант 28               <1011-1110-0011-0101>

Варіант 29               <0011-1100-1101-1110>

Варіант 30               <0010-0101-1001-1101>

     Розглянемо задачу аналізу АКА. Надана структурна схема автомата. Описати алгоритм його роботи (Рис. 3)

Опишемо роботу цієї схеми аналітично:

     Составимо таблицю істинності автомата табл. 2

                                                                                           Таблиця 2

 

0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1
0 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0

 

Рис.3.

Діаграма стану автомата:

       Автомат виробляє двійковий періодичний код <000-001-100-110>.

Індивідуальне завдання 2

Провести аналіз АКА, заданого структурною схемою.

                                                                                           Варіант 1

                                                                                                                      Варіант 2

1
&
1
1
1
1
&
АКА
1
1
1

 

 

Варіант 3

       Рекурентна булава функція другого роду залежить тільки від  аргументів в даному і попередніх тактах.

     Наприклад .

Рекурентна булава функція (РБФ) об’єднує в собі РБФ-1 і РБФ-2. Ця функція реалізується кінцевими автоматами з пам’яттю (КП).

     Розглянемо синтез і аналіз таких автоматів.

Надана таблиця переходів-виходів автомата (табл.3).

                                                                

Сост.   Входи 0 1
0 0/0 1/1
1 1/1 0/1
2 1/0 1/0
3 0/1 1/1

Таблиця 3

 

 

Скласти структурну схему автомата.

 

Таблиця істинності цього автомата має вигляд (табл. 4)

 

                                                                        Таблиця 4

0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1
0 1 1 0 1 1 0 1
0 0 1 1 1 0 1 1

 

     Аналітично робота автомата може бути представлена рівняннями.

 

 

     Перше рівняння може бути реалізовано двохвходовим тригером, на вхід якого надається сигнал.

 

на  вхід тригера подається сигнал:

       Структурна схема автомата:

 

Індивідуальне завдання 3

Синтезувати КП по таблицям переходів-виходів.

 

Варіант 1                                                              Варіант 2                        

Состоян. Входи 0 1 2 3
0 0/0 1/2 2/1 3/3
1 2/1 3/0 1/3 0/2
2 1/2 2/2 3/1 1/3
3 3/1 3/0 2/3 2/2
Состоян. Входи 0 1 2 3
0 1/0 2/1 3/2 0/0
1 2/1 2/2 3/0 1/3
2 3/2 1/1 2/0 0/3
3 2/2 1/0 3/1 3/3

 

Варіант 3                                                                 Варіант 4

Cостоян.   Входи 0 1 2 3
0 3/1 2/3 1/2 0/0
1 1/2 2/2 3/1 0/3
2 2/0 3/1 1/2 0/3
3 3/2 2/1 3/0 2/2
Состоян.   Входи 0 1 2 3
0 0/2 1/3 2/1 3/0
1 1/2 2/2 3/3 0/2
2 2/2 3/3 0/0 1/1
3 3/3 2/2 1/1 0/0

                           

 

                  

 

 Варіант 5                                                         Варіант 6

    Состоян. Входи 0 1 2 3
0 0/3 2/2 3/1 1/0
1 1/2 1/1 2/3 0/2
2 1/3 0/2 2/0 0/1
3 3/2 2/3 3/1 1/0

                                     

     Состоян. Входи 0 1 2 3
0 1/0 0/1 1/3 0/2
1 2/3 3/2 0/1 1/0
2 1/0 2/1 3/1 2/0
3 2/3 3/2 1/3 2/1

 

                            

 

       

                                                                 

 

Варіант 7                                                               Варіант 8

     Состоян. Входи 0 1 2 3
0 0/3 0/2 1/1 2/0
1 2/3 1/2 0/1 3/2
2 3/2 1/3 2/3 0/2
3 1/3 2/2 0/1 1/3

                            

     Состоян. Входи 0 1 2 3
0 3/1 3/2 2/3 2/1
1 0/3 1/2 3/0 2/1
2 2/1 1/2 3/0 2/3
3 1/0 2/1 0/2 3/3

 

 

                                                                                                                                                        Варіант 9                                                                           Варіант 10

     Состоян. Входи 0 1 2 3
0 2/2 2/1 1/3 1/0
1 2/0 3/1 3/1 2/0
2 3/2 2/3 1/0 2/1
3 1/1 0/3 2/2 3/0
     Состоян. Входи 0 1 2 3
0 3/2 2/1 1/0 0/3
1 2/3 3/2 0/1 1/0
2 3/0 2/1 1/3 2/2
3 2/0 3/2 1/1 0/3

                                     

 

 

 

Варіант 11                                                               Варіант 12

     Состоян. Входи 0 1 2 3
0 1/2 1/3 1/3 1/2
1 2/0 3/1 2/1 1/0
2 3/2 2/1 1/0 3/3
3 2/1 2/2 1/3 0/1
       Состоян. Входи 0 1 2 3
0 0/1 0/2 1/3 1/0
1 1/3 2/0 0/1 3/2
2 2/3 3/2 0/0 2/0
3 3/2 1/1 0/0 3/3

 

 

 Варіант 13                                                                        Варіант 14

     Состоян. Входи 0 1 2 3
0 0/2 1/3 1/1 3/2
1 1/3 0/2 1/0 3/1
2 1/2 0/3 3/2 1/1
3 2/3 3/3 1/1 0/0
     Состоян. Входи 0 1 2 3
0 1/2 0/3 1/0 0/1
1 1/3 2/2 2/0 1/1
2 3/0 2/1 1/2 3/3
3 2/3 3/2 1/3 0/2

                                               

 

 

 

 

 

Варіант 15                                                               Варіант 16

     Состоян. Входи 0 1 2 3
0 2/0 2/1 1/1 2/0
1 0/2 3/2 2/1 0/3
2 3/1 1/2 0/3 2/0
3 1/3 1/1 0/2 2/0

                            

     Состоян. Входи 0 1 2 3
0 1/2 1/1 1/3 0/0
1 3/1 1/0 2/2 3/1
2 2/2 3/1 1/0 0/3
3 0/1 2/3 1/2 0/1

 

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

       Рівняння тригеру:

     Приведемо його до досконалої діз’юнктивної нормальної форми:

 

 

 

Рівняння виходу:

     Таблиця істинності цього автомату (табл. 5)

 

Таблиця 5

0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1
1 1 0 1 1 1 0 1
1 0 1 1 1 1 1 1

 

 

     Таблиця переходів-виходів автомату:

 

          Состоян. Входи 0 1
0 1/1 1/1
1 0/1 0/1
2 1/0 1/1
3 1/1 1/1

 

 

 

 

Діаграма стану автомату:

 

Індивідуальне завдання 4

     Надана структурна логічна схема кінцевого автомату з пам’яттю. Описати алгоритм його роботи за допомогою таблиці переходів-виходів.

 

Варіант 1

1
1
1
1
&
&
&
&
1
&
1
J
k
J
k
КП
1
1

 

Варіант 2

Варіант 3

 

 

Список літератури

 

1. Коршунов Ю.М. Математические основы кибернетики. - М.: Энергия, 1980. - 423 с.

2. Грешилов А.А. Как получить наилучшее решение в реальных условиях. - М.: Радио и связь, 1991. - 317 с.

3. Поспелов Д.А. Логические методы анализа и синтеза схем. - М.: Энергия, 1968. - 328 с.

 

 

Укладачі:

Власов Александр Вячеславович

Малієнко Андрій Вікторович

 

Методичні вказівки до виконання самостійної роботи

з дисципліни: „Дискретна математика”

для студентів спеціальностей 7.080203 і 7.091501

 

Редактор

 

Підписано до друку . .05. Формат 30*42/4

Папір офсет. Ризографія. Умов. друк. арк.2,3.

Обліково-видавн. Арк. 2,3. Тираж 100 прим. Зам №

НГУ

49024, м. Дніпропетровськ, проспект К.Маркса,19

 




⇐ Предыдущая12






Последнее изменение этой страницы: 2018-06-01; просмотров: 145.

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