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

КОНСПЕКТ ЛЕКЦИЙ 5 страница

Читайте также:
  1. ALTERED STATES OF CONSCIOUSNESS PSYHOSEMANTICS 1 страница
  2. ALTERED STATES OF CONSCIOUSNESS PSYHOSEMANTICS 2 страница
  3. ALTERED STATES OF CONSCIOUSNESS PSYHOSEMANTICS 3 страница
  4. ALTERED STATES OF CONSCIOUSNESS PSYHOSEMANTICS 4 страница
  5. ALTERED STATES OF CONSCIOUSNESS PSYHOSEMANTICS 5 страница
  6. ALTERED STATES OF CONSCIOUSNESS PSYHOSEMANTICS 6 страница
  7. ALTERED STATES OF CONSCIOUSNESS PSYHOSEMANTICS 7 страница
  8. ALTERED STATES OF CONSCIOUSNESS PSYHOSEMANTICS 8 страница
  9. Annotation 1 страница
  10. Annotation 2 страница
  11. Annotation 3 страница
  12. Annotation 4 страница

 

 

3. Преобразуем полученные выражения в соответствии с задуманными логическими элементами «и-не».

.

Для построения SМДНФ и SМКНФ на двухвходовых элементах «и-не» потребуется соответственно 20 и 21 логический элемент. Поэтому для построения части схемы, реализующей S, выберем SМДНФ.

,

.

Для реализации PМДНФ необходимо 6 двухвходовых элементов «и-не», а для РМКНФ – 7 (с учётом того, что уже получены в SМДНФ).

Для построения части схемы, реализующей Р, выберем РМДНФ.

 

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

; .

 
 

 


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

5. На этапе схемотехнической коррекции ограничимся лишь оценкой выполнения требований по коэффициентам объединения Ко и разветвления Кр. К0 был задан равным двум, а Кр для логических схем равен . Зададим Кр=5. Схема показывает, что для всех элементов К0=2, а Кр<4 и, следовательно, требования по Ко и Кр удовлетворены.

6. Проведём тестирование схемы сумматора только на одном наборе аргументов. Пусть а=1, b=0, c=1. По ТИ этому набору соответствуют S=0 и Р=1. Расположим на всех входах и выходах элементов схемы соответствующие логические значения (0 или 1) и убедимся в правильности реализации функции S и Р на данном наборе аргументов (см. схему). Если выполнить аналогичные действия для всех наборов аргументов их ТИ, то тестирование будет полным.

Обратим внимание на то, что полученная схема, в соответствии с заданием, содержит только двухвходовые элементы «и-не».

таблица 5
х1 х2 х3 х4 F1 F2 F3
            - - -

Задание 67. Синтезировать комбинационную схему, закон функционирования которой задан функцией F4 (таблица 4), используя логические элементы «и-не».

Задание 68. Синтезировать комбинационную схему полного одноразрядного сумматора на двухвходовых логических элементах «или-не» и протестировать её на наборе a=1, b=1, c=0.

Задание 69. Синтезировать комбинационную схему, реализующую функцию F1, заданную в таблице 5. Использовать двухвходовые логические элементы «или-не». Провести тестирование схемы при х1=0, х2=1, х3=1, х4=0.

таблица 6
х1 х2 х3 F1 F2 F3
          - -

Задание 70. Синтезировать комбинационную схему, реализующую функции F2 и F5, заданные в таблицах 5 и 6. Использовать двухвходовые логические элементы «и-не». Провести тестирование схем при х1=0, х2=1, х3=1, х4=1.

Задание 71. Синтезировать комбинационную схему, реализующую функции F3 и F6, заданные в таблицах 5 и 6. Использовать логические элементы: «не» и «2и». Провести тестирование при х135=0, х24=1.

 

 

1.4.4. Односторонние булевы уравнения

Рассмотрим метод решения односторонних булевых уравнений с одним и двумя неизвестными. Уравнения с одним неизвестным:

.

Уравнения с двумя неизвестными:

,

где F1(…) и F2(…) – известные (заданные) функции, а Р(…), Q(…), R(…) – неизвестные функции.

Решение этих уравнений будем искать методом подбора значений P, Q, R на всех наборах F1 и F2. Таких наборов 4. Составим таблицу решений.

таб. решений
F1 F2 P Q R
      - - - -

; .

Для получения решений в виде для уравнений с одним неизвестным и , для уравнения с двумя неизвестными, необходимо сначала перейти от формы представления исходных функций F1 и F2 к форме представления функций P, Q, R (для этого используется таблица решений), а затем выполнить минимизацию этих функций.

Пример. Решить булевы уравнения и при F1 и F2 заданных в строчной форме: , . Выполнить переход от F1 и F2 к P, Q, R. Используем таблицу решений односторонних булевых уравнений.

Перейдём от представления P, Q и R к строчной форме к представлению картами Карно и выполним минимизацию:

  карта Карно для Р
  x3x4
       
X1x2          
         
         
         
Карта Карно для R
  x3x4
       
x1x2     -   -
  - -    
  -   -  
      - -

 

карта Карно для Q
  x3x4
       
x1x2   -   -  
      - -
    -   -
  - -    

Проведя минимизацию Р, Q и R получим:

, , .

Задание 72. Решить односторонние булевы уравнения с одним и двумя неизвестными, если известные функции F4 и F5 заданы ТИ (таблица 6).

Задание 73. Решить односторонние булевы уравнения с одним и двумя неизвестными, если известные функции F1 и F2 заданы ТИ (таблица 5).

 

1.4.5. Методы синтеза комбинационных схем с многими выходами.

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

Рассмотрим два из них:

- метод учёта повторяющихся членов,

- метод последовательного наращивания.

 

Метод учёта повторяющихся членов.

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

Пример. Синтезировать комбинационную схему, реализующую функции:

, , .

Общими членами в этих выражениях являются: .

 
 

 

 


Задание 74. Синтезировать комбинационную схему, реализующую функции:

 

Метод последовательного наращивания.

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

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

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

Таким образом, получаем обычное булево уравнение с двумя неизвестными . Следовательно, при построении многовыходной схемы методом последовательного наращивания необходимо найти решение (n-1) булева уравнения и определить все Q­i и Ri.

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

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

Структурная схема, реализующая функцию F’i может быть представлена следующим образом:

.

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

 

  AB
       
C          
         
для Р
  AB
       
C          
         
для S

 

 

  AB
       
C   - -   -
  -      
для Q
  AB
       
C       -  
    - - -
для R
 

 

 

Проведём тестирование построенной схемы на наборе аргументов А=1, В=0, С=1. Этому набору должны соответствовать значения S=0 и Р=1. Проставленные логические значения на входах и выходах элементов схемы показывают работоспособность схемы (на данном наборе).

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

Задание 75. Реализовать рассмотренную схему только на двухвходовых элементах «и-не» и, проведя сравнение полученной реализации со схемой, определить выигрыш (проигрыш) в количестве элементов схемы и её быстродействии.

Задание 76. Используя условия задания 70 синтезировать двухвыходную комбинационную схему методом последовательного наращивания.

Задание 77 Используя условия задания 71 синтезировать двухвыходную комбинационную схему методом последовательного наращивания.

 

 

1.5. Синтез и анализ конечных автоматов.

Определение. Если совокупность выходных сигналов (выходного слова) Y(t) зависит, как от совокупности входных сигналов (входного слова) X(t), так и от внутренних состояний S(t-1), то такой преобразователь информации называется конечным автоматом (автоматом с памятью).

Для описания функционирования конечного автомата (КА) задаются:

- множество входных дискретных сигналов, ;

Y(t)={y1,…,yj,…,ym} – множество выходных дискретных сигналов, ;

S(t)={s1,…,sk,…sr} – множество внутренних дискретных состояний, ;

s0 – начальное состояние автомата;

FP – функция переходов, позволяющая определить новое внутреннее состояние автомата, если известно предыдущее внутреннее состояние и состояние входных сигналов в данных момент времени S(t+1)=FP[S(t),X(t)];

FV – функция выходов, позволяющая определить состояние выходных сигналов автомата, если известно внутреннее состояние и состояние входных сигналов Y(t)=FV[S(t),X(t)].

Таким образом, функционирования КА можно представить так:

 

S(t+1)=FP[S(t),X(t)],

Y(t)=FV[S(t),X(t)], где t=0,1,2…

S(t=0)=s0

Автомат Мили

или так:

S(t+1)=FP[S(t),X(t)],

Y(t)=FV[S(t)], где t=0,1,2…

S(t=0)=s0

Автомат Мура

 

Конечные автоматы делятся на 2 части:

Абстрактную – описание полноты FV, X, Y, S автомата, работоспособности

Структурную – отвечает на вопрос как построить КА.

 

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

таблицы состояний:

таблица переходов
  s0 s1 sr
x1 x2 … xn s3 s1 ... … s0 s3 … … … … … … … … … …
таблица выходов
  s0 s1 sr
x1 x2 … xn y4 y1 ... … y2 y3 … … … … … … … … … …

 

совмещённая таблица
  s0(t) s1(t)
x1(t)
x2(t)
(фрагмент)

 

 

 

 

Задание КА графом (соответствует содержимому таблиц состояний).

Различают два основных типа КА: автомат Мили м автомат Мура. Различие между ними заключается в том, что в автомате Мура состояние выходных сигналов не зависит от состояния входных сигналов, а определяется лишь внутренним состоянием, т. е. Y(t)=FV[S(t)].

 

Структурная схема КА.

 
 

 


или несколько подробнее

 
 

 

 


КС – комбинационная схема,

БП – блок памяти,

БФВС – блок формирования выходных сигналов (комбинационная схема, реализующая FV),

БВЭА – блок возбуждения элементарных автоматов (комбинационная схема, реализующая FP),

БЭА – блок элементарных автоматов (память КА),

q – функция возбуждения.

 

1.5.1. Элементарные конечные автоматы и их техническая реализация.

Функция памяти КА реализуется на элементарных автоматах. Элементарный автомат (ЭА) – это автомат Мура, имеющий два и только два различных состояния, имеющий 1 или 2 входа, при подаче сигналов на которые возможен переход из одного состояния в другое.

q(t) 0 0 1 1
Q(t) 0 1 0 1
Q1(t+1) 0 0 1 1
Q2(t+1) 0 1 1 0

Для построения памяти КА используются, в основном, четыре типа ЭА: два типа одновходовых и два двухвходовых.

 

Одновходовые ЭА:

Q1(t+1)=q(t) – ЭА D-типа,

- ЭА T-типа.

 

q0(t) 0 0 0 0 1 1 1 1
q1(t) 0 0 1 1 0 0 1 1
Q(t) 0 1 0 1 0 1 0 1
Q3(t+1) 0 1 1 1 0 0 - -
Q4(t+1) 0 1 1 1 0 0 1 0

Двухвходовые ЭА:

- ЭА RS-типа,

- ЭА JK-типа.

 

 

Техническая реализация ЭА:

 
 

 


q1(t)=qS(t), q1(t)=qJ(t), q0(t)=qR(t), q0(t)=qK(t).

 

1.5.2. Алгоритм структурного синтеза конечного автомата.

1. Задать закон функционирования конечного автомата.

2. Определить n – требуемое количество ЭА. n=ù log2(r+1) é, где r+1 – количество внутренних состояний ЭА, ù … é - ближайшее большее целое.

тип ЭА
D T RS JK
qD(t) qT(t) qS(t) qR(t) qJ(t) qK(t)
    - - - - - -

3. Выбрать тип ЭА по таблице. Для этого предварительно построить таблицу для требуемой функции возбуждения.

4. Построить функциональную схему БЭА.

5. Провести синтез комбинационной схемы БВЭА.

6. Провести синтез комбинационной схемы БФВС.

7. Составить из БЭА, БВЭА и БФВС схему конечного автомата.

8. Провести тестирование полученной схемы на соответствие закону функционирования.

 

1.5.3. Пример синтеза конечного автомата – двоично-десятичного счётчика.

Пример. Синтезировать схему двоично-десятичного счётчика.

                     
Q0                    
Q1                    
Q2                    
Q3                    

Зададим закон функционирования двоично-десятичного счётчика. Этот КА имеет 10 внутренних состояний:

 
 

 

 


Так как n=ù log210 é=4, то для запоминания всех 10 состояний КА потребуется четыре ЭА.

Выберем Тим ЭА. Пусть это будет ЭА Т-типа. Тогда структурная схема синтезируемого КА будет иметь вид:

 
 

 


Выполним синтез БВЭА. Построим либо совмещённую таблицу состояний, либо диаграмму состояний:

 

    Таблица состояний
текущее состояние следующее состояние выходы комбинационной схемы
Q3 Q2 Q1 Q0 Q3 Q2 Q1 Q0 q3 q2 q1 q0 / c
                        / / / / / / / / / /  

 

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

Построим карты Карно для выходных сигналов БВЭА (т. е. для сигналов q0, q1, q, q3).

 

 

  KK для q3
  Q1Q0
       
Q3Q2          
         
  - - - -
      - -

 

KK для q2
  Q1Q0
       
Q3Q2          
         
  - - - -
      - -

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

Поиск по сайту:



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