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

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

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

Абсолютно минимальные формы булевых функций. Задача минимальных форм булевых функций дала формулу решения гарантированно минимальную формулу Абхаянкаром. Количество операций в зависимости от числа функций растет как <=2встепени 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 элемент. Однако, соседнее кодирование не всегда возможно для конечного автомата.

Основные теории множеств Н. Бурбаки. Под множеством понимается множество элементов, обладающих некоторыми свойствами и находящимися в некотором отношении между собой или с элементами других множеств. Два множества тождественно равны между собой А---В только в том случае, если все элементы множества А принадлежат множеству В и наоборот. Множество может содержать, как множество элементов, так и содержать ни одного. Такое множество пустое 0. Его роль, как число ”0”. Множество А, все элементы которого принимают элементы множества В, называются подмножеством В. А<В Если А=В, то А<=В. Подмножество любого множества является пустое множество. АсА и 0сА=собственные подмножества, любые другие подмножества будут несобственные. Множества могут задаваться перечислениями (1) и описаниями (2). 1. А=(а,б,с,д,ф) перечислены все элементы 2. Описываются элементы, входящие в множество. Для (2) требуется задание некоторого …… свойства всем элементам, чтобы определить их отношение к множеству.

Операции над множествами: 1. Объединение А и В есть множество всех элементов, входящих в А или В 2. Пересечением А и В есть множество всех элементов, принадлежащих и А и В. Множества, не имеющие общих элементов называются не пересекающимися. 3. Разность множеств А/В есть множество состоящее из элементов А, не входящих в В. 4. Универсальное множество Е – все другие возможные множества будут подмножеством Е. 5. А II=Е/А дополнение множества А. Для наглядности представления операций над множествами используются круги Эйлера.

Свойства операций. Для этих операций справедливы законы дистрибутивный, коммутационный, ассоциативный.

Картели – есть последовательность элементов любой природы. Длина картели – количество элементов картели (вектор, очередь). 1,1…1 элементы могут быть одни. Картели с длиной=2 называются парами. Множество пар представляют собой плоский график. Картели с длиной 3-тройки ит.д. Если картели для Н, то он ЭНКА.

Прямая (декартово) произведение множеств. А*В – произведение есть множество всех пар, первая компонента которых берется из множества А, а другие из множества В. А=(а,б) В=(с,д) А*В=((а,с)(а,д)(б,с)(б,д)) Прямое произведение не ассоциативное и не коммутационное А*Вне=В*А, А*(В*С)не=(А*В)*С. Понятие степени множества АвстепениН=А*А*…*А (=Н раз). В этом случае ЭНКИ содержат элементы множества А, которые одинаковы А=(а1,а2), Авквадрате=((а1,а1),(а1,а2),(а2,а1),(а2,а2)). Произведение множеств отличаются от операций над множествами: в результате операций над множествами получаются множества, элементы которых принадлежат исходному множеству; элементы произведения множеств есть множества другой природы. Пусть, например, П, М ряд натуральных чисел. Тогда множество (П,М) – множество пар натуральных чисел, каждый из которых может иметь собственную природу.

Бинарные отношения. Р(с-под)МвстепениН называется местным отношением на множестве М. Если Н=1 – это само подмножество М, такие отношения называются признаками. Говорят М обладает признаком Р (асР), если (ас-посерединеР) принадлежит этому множеству, а множество Рс-посерединеМвстепени1 является подмножеством. Так как при Н=1, отношение Р есть признак, то отношение к ним не применяются. Примером 3-х местного или тетрарного отношения являются множества координат самолетов в пространстве. Говорят, что координата находится в некотором отношении с двумя другими координатами. Наиболее часто встречаются двух местные бинарные отношения. Эти отношения устанавливают соответствия одного множества А к элементам другого множества В. Такое отношение может быть задано совокупностью упорядоченных пар множеств. Если элементы А и В находятся в некотором отношении Р, то пишут аРб. В общем случае пары элементов переставлять нельзя.

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

Задание бинарных отношений. Используются любые способы задания множеств. Наиболее часто используется матричный способ задания. Матрица бинарного отношения М=(а1,а2,ан) есть квадратная матрица Г порядка Н, в которой элемент матрицы Сиж, стоящий на пересечении и строки и ж столбца определяется как: сиж=(1, если выполняется Аи Раж; 0, в противном случае.

Бинарное отношение можно задавать с помощью графов. Отношением Р называется рефлексивным, если для любого ас-посерединеМ выполняется аРа. Главная диагональ матрицы такого уравнения содержит только 1. Отношение Р называется антирефлексивным, если выполняется аРа. Отношение Р называется симметричным, если для пары (а,б)с-посерединеМ из того, что аРб => обратное соотношение бРа. Матрица симметричного отношения симметрична относительно главной диагонали, то есть Сиж=Сжи. Отношение Р называется транзитивным, если для любых (а,б,с)с-посерединеМ из аРб, бРс => аРс. Если Р отношение ”больше”, а>б, б>c, а>с. В булевой алгебре доказано, что нарушение одного из 3х свойств ведет к тому, что оптимальное решение получено не может быть.

Основные теории графов. Под графом Г понимается пара Г(Х,Г), где Х - непустое множество вершин, а Г - непустое множество ребер, соединяющее некоторые из вершин Х. Две дуги называются смежными, если они различны и для них существует граничная точка.

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

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

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

Булева функция называется линейной, если она может быть представлена полиномом Жегалкина I степени.

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

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

К полным системам булевых функций относится система, состоящая всего лишь из одной системы: эта функция Пирса (ИЛИ-НЕ) и функция Шефера (И-НЕ).

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

Сокращенной ДНФ функции называется дизъюнкция всех её простых импликант.

Булева сумма элементарных произведений называется дизъюнктивной нормальной формой (ДНФ).

Булево произведение элементарных сумм называется конъюнктивной нормальной формой (КНФ).

Импликантой булевой функции называется такая булева функция, которая принимает значение 1 на тех же наборах, что и сама функция.

Под логическим многополюсником понимается логическая схема, где m – входов и n – выходов.

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

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

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

Работа автомата определяется в дискретные моменты времени, которые называются тактами, а сам конечный автомат синхронным.

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

Автомат Мили – J и S уравнения:

Автомат Мура:

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

Триггер – есть запоминающее устройство, способное хранить 1 бит информации.

Под графом понимается пара , где - непустое множество вершин, а – непустое множество ребер, соединяющие некоторые из вершин .