Конспект лекций по дискретной математике


главная страница Рефераты Курсовые работы текст файлы добавьте реферат (спасибо :)Продать работу

поиск рефератов

Реферат на тему Конспект лекций по дискретной математике

скачать
похожие рефераты
подобные качественные рефераты

Размер: 238.02 кб.
Язык: русский
Разместил (а): МАРАЗМ
04.09.2006
 1 2 3 4 5 6 7 8 9 10 11    
Синтез комбинационных схем
.

Понятие логического элемента.

Типовые логические элементы и их обозначения на функциональных схемах
.

Определение: как правило ,под логическим элементом понимается комбинационная схема ,реализующая некоторую элементарную булеву функцию.

Любой логический элемент характеризуется :

1) Наличием одного или нескольких входов на которые подаются входные сигналы( входные переменные).

2) Наличием выхода ,на котором формируется выходной сигнал

(выходная переменная).

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

1) Инвертор( НЕ)



2) Дизъюнктор (ИЛИ)



3) Конъюнктор (И)



4) Дизъюнктор с отрицанием (ИЛИ - НЕ)


5) Конъюнктор с отрицанием (И - НЕ)



6) Исключительное ИЛИ

(единичный сигнал на выходе имеет место в том и только том случае если на  

 одном и только одном входе присутствует единичный сигнал)



7) Сумматор по модулю 2



1)Элементы 1,2,3 образуют булев базис.

2)Элементы 1 и 2 или 1 и 3 образует сокращенный(неполный)

   булев базис.

3)Элементы 4 или 5 образуют универсальный базис.

4)Элементы 3 и 7 образуют базис Жегалкина.

Функции элементов 6 и 7 совпадают при наличии только двух входов.
Понятие двоичного сигнала
.


Способы его кодирования
.

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

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

1)Позитивное кодирование (положительное)

    высший уровень сигнала - 1 ,низший - 0

2)Негативное кодирование (отрицательное)

    высший уровень сигнала - 0 ,низший - 1

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



Типы логических систем
.

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

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

1)К любому входу логического элемента могут быть подключены: 

a) выход любого другого логического элемента( в частном     случае ,того же самого)

б) входной сигнал (входная переменная)

в) логическая константа(0 или 1)

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

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

1)Комбинационные

2)Последовательносные

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

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

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

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


Пример комбинационной схемы на элементах булева базиса :



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

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

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

Пример последовательносной схемы: (универсальный базис И-НЕ)



Последовательносные схемы характеризуются наличием так называемых петель ,по которым выход некоторого элемента соединяется со входом этого же самого элемента (через другие элементы схемы).

Основные параметры комбинационной схемы.

Основными параметрами комбинационных схем (КС) является стоимость и быстродействие ,как правило при построении абстрактных КС не привязанных к конкретной системе элементов цена схемы определяется в смысле Квайна. Быстродействие схемы ,как правило оценивается задержкой распространения сигналов от входов схемы к ее выходу. Для абстрактных КС эту задержку принято считать в виде : Т=кt  ,t-задержка на одном логическом элементе,к-максимальное количество логических элементов ,через которые проходит сигнал от входов к выходу.

 

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

Для приведенной схемы элементы 1,2,3 относятся к первому уровню.

Элементы 4,5 ко второму уровню.

Элемент 6 к третьему уровню.

Элемент 7 к четвертому уровню.
Задачи анализа и синтеза комбинационных схем
.

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

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

                              __

y=y1v y2=4v y3y6=x1x2v(y4v y5)x4x5=

  ___

=x1x2v(x1x2v3)x4x5

Определим реакцию схемы на входной набор.

Например (00000)   у=1

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

При решении этой задачи необходимо учитывать следующие моменты:

1) Синтезируемая схема должна по возможности содержать минимум оборудования. В связи с этим актуальной задачей является минимизация заданной булевой функции. При решении этой задачи целесообразно получить как МДНФ так и МКНФ.

2) Как правило ,синтезируемая схема строится на логических элементах ,принадлежащих некоторому базису. Естественно ,что используемая система элементов должна обладать свойством функциональной полноты ,то есть быть достаточной для построения на ее основе комбинационной схемы ,реализующую любую наперед заданную булеву функцию. Такими функционально полными системами логических элементов являются:             1.{И,ИЛИ,НЕ}   2.{И,НЕ}                                     3.{ИЛИ,НЕ}       4.{И-НЕ}                                                 5.{ИЛИ-НЕ}        6.{И,М2}

3) Как правило при решении задачи синтеза стараются добиться экстремального значения одного из параметров схемы :минимум цены или максимум быстродействия (минимум задержки).В тех случаях ,когда критерием эффективности схемы является минимум цены по Квайну над минимальными формами проводят дополнительные преобразования ,путем решения задач факторизации и возможно декомпозиции булевой функции. Как правило минимальная форма не дает абсолютного минимума стоимости ,чего можно добиться решением задач факторизации и декомпозиции.       Если критерием эффективности схемы является минимальная задержка ,то следует иметь в виду ,что факторное преобразование и декомпозиция булевой функции в общем случае уменьшает цену схемы и увеличивает ее задержку. В более сложном случае схема оптимизируется по одному из показателей при наличии ограничения на второй.      Примером подобной постановки задачи синтеза является: Синтезировать схему с минимальной ценой по Квайну ,чтобы ее задержка не превышала 4t.

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

5) При построении схем в реальной системе элементов необходимо учитывать ряд конструктивных ограничений ,основными из которых являются:                                                  

а) Коэффициент объединения по входу, который представляет собой ограничение на число входов в элемент. Может принимать значения 2,3,4,8,16.

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

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

7) Как правило в большинстве реальных систем элементов наряду с простыми логическими элементами используются также сдвоенные элементы реализующие составную булеву функцию. Типичным примером может служить элемент И-ИЛИ-НЕ.

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


1) Булев Базис (И, ИЛИ, НЕ)

    _ _     _ _ _  _      _

y=x1x2x3vx1x2x4vx1x5vx6 (МДНФ)

   --------  -------  -----

    и  (3)    и (3)  и (2)

Схема  с парафазными входами


SQ=3+3+2=12   Sa<SQ<Sb           Sa=9 Sb=9+4=13

В общем случае задержка Т=2t (схема 2-х уровневая).

При построении схемы по МКНФ элементами 1-го уровня будут ИЛИ, а 2-го И.

                Схема с однофазными входами



SQ=16  T=3t

         В общем случае задержка схемы с однофазными входами составляет 3t.

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

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

    ººº===ºººº==º===ºº   ººº=--ºººº-º==-ºº

y=x1x2x3 v x1x2x4 v x4x5 v x6= x1x2x3* x1x2x4* x4x5* x6=

   -------------------------------------------

=( x1v x2v x3)( x1v x2v x4)( x4v x5)* x6

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

         По сравне6нию с предыдущей схемой цена уменьшается на единицу (SQ=15). Однако наличие выходного инвертора приведет к увеличению цены схемы T=4t.

2) Сокращенный булев базис (И, НЕ).

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

         Используя предыдущие преобразования можно построить схему как с парафазными так и с однофазными входами.

         Схема с парафазными входами :



SQ=16  T=4t

При построении схемы на элементах базиса И, НЕ по МДНФ задержка схемы в общем случае составляет 4t. А при использовании однофазных входов 5t.

3) Универсальные базисы И-НЕ и ИЛИ-НЕ (см. Практику).
Задача факторизации (факторного преобразования) булевой функции
.

    продолжение
 1 2 3 4 5 6 7 8 9 10 11    

Удобная ссылка:

Скачать реферат бесплатно
подобрать список литературы


Конспект лекций по дискретной математике


Постоянный url этой страницы:
Реферат Конспект лекций по дискретной математике


Разместите кнопку на своём сайте:
Рефераты
вверх страницы


© coolreferat.com | написать письмо | правообладателям | читателям
При копировании материалов укажите ссылку.