Главная страница
Навигация по странице:

  • Суть аналитического метода

  • Понятие базиса логических функций. Примеры

  • Минимизация сложности комбинационных схем: метод Квайна-Мак-Класски

  • ___________________Вопрос 33____________________ Синтез комбинационных схем по не полностью определенным ФАЛ

  • ___________________Вопрос 35____________________ Синтез комбинационных схем на дешифраторах и мультиплексорах

  • _____________________Вопрос 36____________________ Соединение автоматов: параллельное, последовательное. Параллельное

  • _____________________Вопрос 37____________________ Соединение автоматов с обратной связью.

  • ___________________Вопрос 38___________________ Синтез схем по временным булевым функциям(ВБФ)

  • ___________________Вопрос 39____________________ Синтез и анализ последовательностных автоматов. РБФ

  • ___________________Вопрос 43____________________ Определение абстрактного автомата. Автоматы Мура и Мили.

  • ___________________Вопрос 44____________________ Способы задания автоматов.

  • ___________Вопрос 45(совпадает с 21, читай выше)___________ ___________________Вопрос 47____________________ Элементарные автоматы RS-, D-, DV- триггеры.

  • ___________________Вопрос 48____________________ Элементарные автоматы JK-, T- триггеры.

  • ___________________Вопрос 49____________________ Реакции автомата Мили и Мура.

  • ВОПРОСЫ К ЭКЗАМЕНУ ПО ТЕОРИИ АВТОМАТОВ. Вопросы к экзамену Строки. Префиксы, суффиксы, подстроки. Формальные языки


    Скачать 3.16 Mb.
    НазваниеВопросы к экзамену Строки. Префиксы, суффиксы, подстроки. Формальные языки
    АнкорВОПРОСЫ К ЭКЗАМЕНУ ПО ТЕОРИИ АВТОМАТОВ
    Дата10.01.2023
    Размер3.16 Mb.
    Формат файлаdocx
    Имя файлаVoprosy_k_ekzamenu (2).docx
    ТипВопросы к экзамену
    #879376
    страница4 из 4
    1   2   3   4

    Минимизация сложности комбинационных схем: аналитический метод, метод Карт Карно (3,4,5 переменных).

    Критерием сложности к реализации является колич-во переменных и знаков логических д-ий в представляемой ф-ии.

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

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

    F(x,y,z)=xyz + xy + z = xy(z+1)+z = xy + z.

    Метод Карт Карно:

    1).исходная ф-ия представл в виде СДНФ

    2) Минтермы, образующие СДНФ, заносятся в карту Карно в соответствующие клетки в виде “1”. Пустые “0”.

    3).выделение групп.Каждая группа-это множ-во соседних клеток,заполненных единицами,причём колич-во клеток в группе м.б.=2,4,8…2k. Нужно стремится к тому чтобы групп было как можно меньше, но сами они были как можно больше.

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

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

    Карты Карно 5-ти переменных им особенности:

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

    1. Понятие базиса логических функций. Примеры

    Примеры базисов. 

    1. Базис Буля: {∧, v, ¬}

    2. Базис Жегалкина: {1,⊕,&} 

    3. Конъюктивный базис: {&; −}

    4. Дизъюктивный базис: {+; −}

    5. Базис Вебба: {↓} 



    1. Базис Шеффера: {|}



    7Сокращенный базис Буля (ИЛИ-НЕ)

    8Универсальный базис Буля (И-НЕ)



    1. Минимизация сложности комбинационных схем: метод Квайна-Мак-Класски

    Логические ф-ии м.б. представлены различным количеством переменных и знаком логических д-ий.Основная  идея минимизации сост в выполнении операции склеивания,в рез-те которой уменьшается кол-во термов и ранг полученных термов меньше ранга исходных.Термы,отлич-ся значением одной переменной,наз соседними.

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



    1)Выписываются 0-кубы. 0000, 0001, 0011,0101,0110,0111,1000, 1001,1101,1111

    2)0-ые кубы группируются по кол-ву 1 в них.



    3) Склеивание 0-ых кубов в 1-ые кубы, только м/у соседними кубами, особое внимание на термы, которые не участвовали в склеивании- претенденты на ответ. В данном примере таких нет.



    4).упорядочивание одномерных кубов по месту расположения x

    5)Склеивание внутри 1-кубов. 011x не участвовал в склеивании



    6).вычёркивание одной из двух одинаковых импликант

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

    Проверка:-не д.б. столбцов,не имеющих хотя однц метку; -каждая строка должна содерж точно 2k-клеток,гдк k-колич-во крестов в вертикальном первом столбце таблицы.8) вычеркивание столбцов, помеченных существенными импликантами.

    8).поиск минимального покрытия начинается с поиска существенных импликант.Импликанта-терм,входящий в состав термов,образующих ф-ию.Существенная импликанта порождает единственную метку в столбце.Такая импликанта обязательно входит в окончательный ответ.Если присутсствуют несущественные импликанты(имеющие несколько меток в соответ столбцах),то в ответ войдут некоторые из них.Сама процедура выбора одной из нескольких несуществующих импликант наз поиском минимального покрытия,состоящая в вычёркивании столбцов,порождающие существенные импликанты. Выписываем ответ 011x +x00x+0xx1+1xx1

    ___________________Вопрос 33____________________

    Синтез комбинационных схем по не полностью определенным ФАЛ

    Если значения ф-и на нек-х наборах не заданы, то она называется не полностью определенной.



    Пусть дана ф-ия от n-переменных:f(x1,x2,…,xn). Если функция нк определена на n наборах, то ее можно доопределить 2^n наборов способами, доведя до определенной ф-й таких, что они будут совпадать с ф-ией f на всех определённых наборах Т.к. можно построить 2p различных эквивалентных ф-ий, то возникает задача, какую конкретно из них выбрать, чтобы её сложность была минимальной. Чаще всего такие задачи решаются с пом карт Карно.

    ___________________Вопрос 35____________________

    Синтез комбинационных схем на дешифраторах и мультиплексорах

    Дешифратор - схема реализующая все конституенты единицы.ДШ имеет n входов и 2^n выходов. Синтез ДШ сводится к дизъюнктивному объединению необходимых выходов ДШ. Объединение дешифратора с помощью мультиплексора.



    Мультиплексор- схема с 1 выходом и 2мя группами входов: данных и адресными



    _____________________Вопрос 36____________________

    Соединение автоматов: параллельное, последовательное.

    Параллельное:





    В результате получается автомат

    A=A1*A2

    W=фи(W1*W2)

    -ф-я переходов

    - ф-я выходов.,

    Рассмотрим 2 автомата, заданные таблицами переходов-выходов и функцию фи.







    Последовательное:



    При послед. соединении число выходов автом S1 и число входов авт S2 должны совпадать.

    Единственное отличие от парал соединения это функция выходов А=А12  Z2=w1 и w=w2

    _____________________Вопрос 37____________________

    Соединение автоматов с обратной связью.

    Соединения с обратной связью:



    Хотя бы один должен быть автоматом Мура.





    Если ав-т нах-ся в сост-ии а2,т.е.S1 в сост-ии а11, а S2 в сост-ии а22.S2 в сост-ии а22 выраб-т сигнал w2'кот-й поступает на 2й вход элемента γ. На 1й вход элем-а γ пост-т вход.сигнал из мн-ва z, пусть б/т z1, тогда по таблице γ находим что по z1 и w2'выраб-ся сиг-л р2, кот-й поступ-т на вход ав-та S1. По условию ав-т S1 нах-ся в сост-ии а11. под дейст-м р2 он переходит в а21, выраб-вая при этом w3",кот-й явл-ся одновременно и выходным сиг-м эквив-го ав-та и входным для S2. Ав-т S2, находясь по умолчанию в сост-ии а22 под дейс-м w3" переходит в а12. на этом реакция на дан.вход.сигнал заканч-ся. Окончательно из а2 под дейс-м z1 ав-т переходит в а3 с выроботкой w3".

    ___________________Вопрос 38___________________

    Синтез схем по временным булевым функциям(ВБФ)

    Работа реальных автоматов, происходит во времени, чтобы описать работу реальных автоматов вводят понятие автоматного времени. Вводит в себя последовательность временных интервалов на к-е разбито все время работы автомата. S- число интервалов. 0, 1…- длит. врем. интервалов. В течение каждого интервала, время считается остановившимся, и тогда логика работы автомата будет описываться только лог. переменными.



    Синтез:

    1. строим временную диаграмму. Сколько проводов, столько интервалов.

    2. Функцию представим в виде логических функций

    3. По уравнениям строим логическую схему, реализующую ВБФ.


    ___________________Вопрос 39____________________

    Синтез и анализ последовательностных автоматов.

    РБФ - лог. ф-я, зависящая от текущих и от предшествующих значений ф-ци.



    Значения y(t+1)  получаются задержкой сигнала y(t) на J тактов с помощью операторов задержки D. x-входные переменные, у- сигналы обратной связи. Пример, поступают только сигналы обратной связи.



    Задание РБФ всегда должно происходить с оговоренными начальными условиями. Пусть обратная связь осуществляется с задержкой на 1 такт, тогда:



    Схемы описываемые уравнениями и заданными нач. условиями, называются последовательностными автоматами.

    Чтобы провести анализ последовательностной схемы, необходимо:

    1. получить мат. модель

    2. По полученной математической модели, строим таблицу истинности

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

    4. выявляем наличие циклов

    5. Строим круговую диаграмму

    6. Выписываем циклы  и тупиковые состояния

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

    ___________________Вопрос 43____________________

    Определение абстрактного автомата. Автоматы Мура и Мили.

    Абстрактная теория изучает лишь переходы, к-е выполняет автомат под воздействием входных сигналов и те выходные сигналы, к-е он выдает. Не рассмат-я структуру автомата. Абстрактный автомат  имеет один вход и один выход. Абстрактный автомат- мат. модель дискретного устройства, заданная: : S=(A,Z,W,сигма,лямда,а0) :

    1. A={a1, a2, ... ,am} - множество состояний автомата

    2.  Z={z1, z2, ... ,zf} - множество входных сигналов

    3.  W={w1, w2, ..., wg} - множество выходных сигналов

    4. сигма- функция переходов,  показыв в какое сост аs перейдёт авт-т,находясь в сост am ,при входном сигнале zf .

    5.  лямда - функция выходов,показ. в какой выходной сигнал вырабатыв на выходе авт-та am  под действием сигнала zf

    6.  a0 - начальное состояние автомата.



    Абстрактный автомат  называется  конечным,  если конечны множества  А = {a1, a2, ..., am}, Z = {z1, z2, ..., zf}, W = {w1, w2, ..., wg}. Автомат называется конечным, если множество его внутренних состояний, а также множества значений входных и выходных сигналов конечны.

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

    В каждый момент t дискретного времени автомат находится в некотором  состоянии  a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном со­стоянии a(0)=a1. В момент t, будучи в состоянии a(t),  автомат воспринимает сигнал z(t) на входном канале, и вырабатывает  на выходном канале сигнал W(t)=лямда(a(t), z(t)) и в соответствии с функцией переходов перейдет  в следующее состояние a(t+1)=сигма[a(t),  z(t)]

    Распространенные Мили и Мура.

    Мили(1ый род R):


    Мура(2ой род S):



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

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

    ___________________Вопрос 44____________________

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

    Табличный метод:

    Мили задается двумя таблицами 1ая сигма, 2ая лямда.



    Часто эти две табл совмещ в одну и она наз совмещённой табл переходов-выходов:



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



    Графический метод:

    Задается в виде ориентированного графа,  вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины am, задает  переход  в автомате из состояния am в состояние as.  В начале этой дуги записывается входной сигнал Zf,  вызывающий данный  переход as=сигма(am,zf).  Для графа автомата Мили выходной сигнал wg формируемый на переходе, записывается в конце дуги,  а  для  автомата  Мура - рядом с вершиной am, отмеченной состоянием am, в котором он формируется.

    Автоматы могут быть заданы с помощью матриц:

    Читается так, из состояния а0 в состояние а1 переходит под действием сигнала z1, при этом вырабатывается выходной сигнал w1.


    ___________Вопрос 45(совпадает с 21, читай выше)___________
    ___________________Вопрос 47____________________

    Элементарные автоматы RS-, D-, DV- триггеры.

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

    D-триггер – элемент задержки – имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт.



    Граф

    RS-триггер – триггер с раздельными входами.Данный триггер имеет два входных канала R и S и один выходной Q. Вход S (set) называется входом установки в единицу, вход R (reset) – входом установки в нуль.



    Граф, описывающий поведение RS триггера

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

    DV- триггер



    ___________________Вопрос 48____________________

    Элементарные автоматы JK-, T- триггеры.



    T триггер реализует



    ___________________Вопрос 49____________________

    Реакции автомата Мили и Мура.

    Реакции автоматов Мили и Мура на входные сигналы имеют различное представление. Пусть цепочка выходных данных имеет вид: Z=z1z2z1z2z2



    После окончания входной цепочки Мили находится в нек-м состоянии и выходной сигнал не вырабатывается, а в Мура находится в нек-м состоянии и вырабатывает выходной сигнал. Каждому автомату Мура можно поставить в соответствие Мили и наоборот. На примере видно, что реакции автоматов совпали. В Мура начальный выходной сигнал не учитывается.
    1   2   3   4


    написать администратору сайта