ДИСКРЕТКА105 (Лекции в ворде), страница 2

Несистематические методы минимизации.

Пример: построить одноразрядный двоичный сумматор. (00)

Синтез схем в базисе функции Шефера И-НЕ.

А 0011 В 0101 А/В 1110 1. А/В=не(А*В)=неА+неВ 2. А/А=неА 3. А/неА=1 4. А/0=1 5. А/1=неА 6. АВ=нене(АВ)=не(неА+неВ)=не(АштрихВ)=(АштрихВ)штрих(АштрихВ) 7. А+В=ненеА+ненеВ=неАштрихнеВ=(АштрихА)штрих(ВштрихВ)

Для того, чтобы перейти от функции заданной в ДНФ к его выражению через функцию Шефера необходимо взять в скобки все ментальные соединения, все операции логического сложения, умножения на операцию Шефера, записать все инверсные переменные через выражение неА=А/А и неА=А/1; так как операция Шефера является двуместной (два аргумента), то каждое элементарное произведение, в котром есть только один аргумент следует представить в виде А=А*1

Синтез схем в базисе функций Пирса (стрелка Пирса ИЛИ-НЕ)

А 0011 В 0101 А/В 1000 1. АстрелкаВ=не(А+В)=неАнеВ 2. АстрелкаА=неА 3. АстрелканеА=0 4. Астрелка0=неА 5. Астрелка1=0 6. АВ=ненеАненеВ=неАстрелканеВ 7. А+В=нене(А+В)=не(неАнеВ)=не(АстрелкаВ)

Функция Шефера и Пирса связаны соотношением Де Моргана.

не(АштрихВ)=не(АстрелкаВ) не(АстрелкаВ)=неАштрихнеВ

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

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

Основные понятия теории конечных автоматов.

Х=(Х1,Х2,…Хn) У=(У1,У2,…Уm) S=(S0,S2,…Sk)

Конечным автоматом называется дискретный преобразователь информации с конечным входным алфавитом Х=(Х1,Х2,…Хn), с конечным выходным У=(У1,У2,…Уm), с конечным числом состояний S=(S0,S2,…Sk), работа которого описывается двумя характеристическими функциями У(Т+1)=Фу(Х(Т),S(Т)) – функция выходов, S(Т+1)=Фs(Х(Т),S(Т)) – функция переходов. Таким образом, чтобы определить конечный автомат нужно задать функцию входов и выходов и задать конечное состояние автоматов. Если функция входов и выходов задается вероятностью уравнений, то и автомат вероятностей, в противном случае автомат называется детерминированным. Работа автомата определяется в дискретные моменты времени, которые называются тактами, а сам конечный автомат синхронным. Конечные автоматы можно задавать с помощью таблиц входов и выходов методом теории графов с помощью матриц. автомат Мили S(Т+1)=Фs((х)Т),S(Т)) автомат Мура У(Т+1)=Фу(S(Т)) Автомат Мили и Мура эквивалентны между собой.

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

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

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

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

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

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

Синтез конечных автоматов. Задача синтеза конечных автоматов заключается в построении сложных конечных автоматов.

Элементарные автоматы обладают следующими свойствами:

1. имеют два внутренних состояния

2. входной и выходной алфавиты двоичные

3. описываются, как автоматы Мура

4. должны обладать полной системой переходов и выходов

Конечный автомат обладает полной системой переходов, если найдется, хотя бы один сигнал, который переводит автомат из одного состояния в другое для каждой пары. Для элементарного автомата, имеющего два состояния, полная система переходов будет выглядеть S(Т)0011 стрелка S(Т+1)0101 Если в каждом состоянии конечный автомат имеет выходной сигнал, отличный от выходных сигналов других состояний, то говорят, что конечный автомат обладает полной системой выходов.

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

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

Элементарные автоматы с одним входом. Д-триггер Д-вход КУ-состояние

Д(Т)0011 КУ(Т)0101 КУ(Т+1)0011

Функция перехода Д-триггера. КУ(Т+1)=Д(Т)неКУ(Т)+Д(Т)КУ(Т)=Д(Т) Д-триггер является триггером задержки сигнала на один такт (триггер защёлка).

Т-триггер Д(Т)0011 КУ(Т)0101 КУ(Т+1)0110 КУ(Т+1)=неД(Т)КУ(Т)+Д(Т)неКУ(Т)=Д(Т)+вкругеКУ(Т) (если считать по нулям) то есть триггер складывает по модулю входной сигнал и предыдущее состояние. Функции переходов триггеров определяют лишь законы их функционирования. Других элементарных автоматов с одним входом нет, а все их возможные модификации могут отличаться способом кодирования.

Элементарные автоматы с двумя входами. Составим общую таблицу переходов такого элементарного автомата с её помощью можно строить элементарные автоматы с двумя входами с различными свойствами. ку1(Т) и ку2(Т) – входные сигналы

ку1(Т)00001111 ку2(Т)00110011 КУ(Т)01010101КУ(Т+1)--1100-- Комбинация на входе двух 0 или 1 считается запрещенными в данном случае. Сигнал ку2(Т) считается сигнал установки триггера в единицу, так как не зависимо от состояния, в котором находится триггер в момент времени Т, устанавливается 1, соответственно сигнал ку считается установкой в 0. В зависимости от того, как заполняется неопределенное состояние в таблице переходов получают триггер с двумя переходами, R-S и J-K триггеры.

R-S триггеры Р(Т)00001111 S(Т)00110011 КУ(Т)01010101 КУ(Т+1)011000—Триггер R-S одновременная подача единиц запрещена на входе. Р(Т)=S(Т)=1 – запрещено. КУ(Т+1)=S(Т)+неР(Т)КУ(Т). Данный триггер получил большое распространение в связи с тем, что при любой технической реализации не критичен к длительности входных сигналов и устойчиво сохраняет своё предыдущее состояние.

Триггер типа J-K. Вход J считается установкой в единицу, вход K установкой в 0. Таблица переходов К(Т)00001111 J(Т)00110011 КУ(Т)01010101 КУ(Т+1)01110010 (1+2-хранение КУ(Т); 3+4-установка в 1; 5+6-установка в 0; 7+8-инверсия КУ(Т)). неКУ(Т)=J(Т)КУ(Т)+неК(Т)КУ(Т).

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

Синтез элементарных автоматов. Чтобы синтезировать элементарный автомат выбирают так называемый базовый элементарный аппарат, в качестве выбирается асинхронный R-S триггер, так как он достаточно просто реализуется и имеет логические возможности, будем реализовывать его на элементах И-НЕ, таблица переходов этого триггера. Р(Т)00001111 S(Т)00110011 КУ(Т)01010101 КУ(Т+1)011100** (1+2-хранение; 3+4-установка в 1; 5+6-установка в 0; 7+8-запрещенная комбинация). КУ(Т+1)=неРнеSКУ+неРSнеКУ+неРSКУ. Триггер логически устойчив, так как переход из 0 в1 и 1 в 0 продублирован. Сокращенная таблица переходов R-S триггера КУ(Т)0011 в КУ(Т+1)0101 Р(Т)б010 S(Т)010б Рб б101 неSб 101б

Синтез синхронного R-S-триггера на базе асинхронного R-S триггера и на элементах И-НЕ. Составим таблицу переходов триггера с учетом переходов синхросигнала С. От метим, что при сигнале С=0, триггер не меняет своё состояние. С(Т)00001111 00001111 Р(Т)00110011 00110011 S(Т)01010101 01010101 КУ(Т)01010101 01010101 КУ(Т+1)01010101 011100** неР0(Т)б1б1б1б1 б111б1бб неS0(Т)1б1б1б1б 1б0б10бб. неРб(Т)=неСнеРнеSКУ+неСнеРSКУ+неСРнеsКУ+неСРSКУ+СнеРнеSКУ+СнеРSнеКУ+СнеРSКУ

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

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

Проблема риска и гонок в конечных автоматах. Возникают только в асинхронных конечных автоматах. В ЗЭ (запоминающий элемент) задержка сигналов близка друг к другу, но могут различаться. В связи с этим в переходе конечного автомата в новое состояние на одном или нескольких элементах сигнал на выходе сформируется раньше, чем в других, а, следовательно, на входе может сформироваться слово, отличное от того, которое в этот момент времени должно быть на входе и конечный автомат может перейти в не предусмотренное состояние. До сих пор считали, что Х и неХ не могут быть равными в один момент времени. Для реальных схем это допущение не всегда выполняется. Когда реальный триггер меняет свое состояние, возникает короткий промежуток времени, в котором схемы или воспринимают эти сигналы, равные ”1” одновременно. В этом случае на триггер 2 поступает сигнал кратковременный одиночный, который может привести триггер в непредусмотренное состояние. Такое называется риском неправильного срабатывания схемы.

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

Существует противогоночное кодирование. Пусть (Х,У) и (М,Н) две пары двоичных кодов с длиной н. Эти пары кодов называются развязанными, если при и (1<=и<=н), и-тый разряд кода принимает одно значение на паре (Х,У), а другое на (М,Н).

Теорема. В конечном автомате состояние которых закодировано 2 кодами конечной длины, гонки отсутствуют, тогда и только тогда, когда для любых двух переходов конечного автомата (Ам,Ас) М(Ак,Ае). Под воздействием одного и того же входного сигнала соответствует паре кодов кодирования этого состояния развязаны => алгоритм противогоночного кодирования: 1. Последовательно просмотреть все пары переходов конечного автомата для которых имеется хотя бы 1 общий входной сигнал, осуществляющий эти переходы. 2. Присвоить этим парам переходов такие значения кодов, чтобы эти пары кодов были развязанными. Существует частный случай противогоночного кодирования – соседний. При таком кодировании конечный автомат при переходе из состояния в состояние в своём значении меняет лишь 1 элемент. Однако, соседнее кодирование не всегда возможно для конечного автомата.