Методическое пособие к лабораторным работам по курсу «Теория конечных автоматов»

  • От :
  • Категории : Без рубрики

высшего профессионального образования ФИЗИЧЕСКИЙ ФАКУЛЬТЕТКАФЕДРА РАДИОЭЛЕКТРОНИКИКоршунов Алексей Дмитриевич Методическое пособие к лабораторным работам по курсу«Теория конечных автоматов»
Содержание Предисловие ……………………………………………………………….….3Тема 1. Логические функции. Булевский базис ……………………………4Тема 2. Построение и моделирование логических схем ………………….7 Тема 3. Методика работы в системе PCAD …………………………….…9Тема 4. Минимизация (упрощение) логических функций……………….14Тема 5. Дополнительные сведения о логических функциях ……………16Тема 6. Пример реализации функции в инвертирующем базисе ……….18Тема 7. Этапы построения логической схемы. Варианты заданий………19Тема 8. Цифровые устройства без памяти8.1. Дешифраторы……………………………………………………198.2. Шифраторы………………………………………………………208.3. Мультиплексоры………………………………………………..218.4. Схемы преобразования произвольных кодов…………………228.5. Сумматоры и арифметические устройства……………………23Тема 9. Цифровые устройства с памятью9.1. Триггеры…………………………………………………………249.2. Регистры и счётчики……………………………………………26
Моим лучшим друзьям
Михаилу и Григорию
посвящается
ПредисловиеИнтенсивное развитие цифровой электроники в начале XXI века ставит перед профессиональными учебными заведениями страны множество вопросов, связанных с изучением методов анализа и синтеза схем электронных устройств дискретного принципа действия, работающих с логическими сигналами. Это относится в первую очередь к таким специальностям, как «Автоматизированные системы управления», «Радиофизика и электроника», «Телекоммуникации» и ряду других.На физическом факультете ИГУ студенты III курса изучают дисциплину «Теория конечных автоматов», частью которой является рассмотрение методов логического проектирования цифровых электронных схем. В процессе изучения дисциплины студенты должны выполнить цикл лабораторных работ по синтезу схем различных цифровых устройств и моделированию этих схем на компьютере в системе PCAD. Сведения, необходимые для выполнения этих работ, представлены в настоящем пособии.Учебный материал пособия разделён на структурные единицы, названные здесь темами. За одно лабораторное занятие могут быть изучены одна, две и более такие темы, в зависимости от уровня подготовки студента. Пособие будет особенно полезно студентам, пропустившим какие-либо занятия, позволяя им быстро нагнать упущенное.Пособие может также оказаться полезным для преподавателей, ведущих лабораторные занятия по данному предмету – с целью быстро «освежить» материал в памяти, наметить и уточнить планы будущей работы со студентами. В процессе подготовки пособия был использован графический редактор программной системы LogModel с целью подготовки изображений цифровых схем. Автор пособия выражает глубокую благодарность разработчику системы LogModel, выпускнику физического факультета ИГУ Агафонникову Владимиру Анатольевичу.
Тема 1. Логические функции. Булевский базис
Алгебра логики – это формальный математический аппарат для описания логической стороны различных процессов и явлений, в том числе процессов в цифровых устройствах. Ниже будут даны основные сведения по алгебре логики лишь в том минимальном объёме, который необходим для понимания материалов данного лабораторного практикума. Для более глубокого овладения предметом существует обширная учебная литература, список которой подскажет ваш преподаватель.
Зарождение логики как науки происходило ещё в античные времена, в частности, Аристотелем были сформулированы основные её законы. В то время логика мыслилась исключительно как наука о человеческих высказываниях и рассуждениях. В XIX веке английским математиком Джорджем Булем (George Boole) были сформулированы и развиты базовые положения математической логики. В XX веке алгебра логики нашла своё новое применение – стала использоваться как средство описания работы электрических и электронных схем дискретного действия.
Алгебра логики имеет дело с логическими переменными, то есть такими переменными, которые могут принимать только два значения, изображаемые как ДА и НЕТ, ИСТИНА и ЛОЖЬ, TRUE и FALSE, 1 и 0. Наиболее распространено последнее обозначение – в силу его краткости. При этом 1 и 0 нельзя трактовать как числа, над ними нельзя производить обычные арифметические действия. Не следует смешивать алгебру логики с арифметикой двоичной системы счисления.
Логические переменные хорошо описывают состояния таких объектов, как реле, тумблеры, кнопки и т.д., то есть таких, которые могут находиться в двух чётко различимых состояниях – включено или выключено. Сюда относятся и полупроводниковые логические элементы, которые при определённых условиях могут находиться в двух различных состояниях. Существуют также логические функции одной или нескольких переменных, которые тоже могут принимать лишь значения 0 и 1.
Если логическая функция зависит от нескольких переменных (а это наиболее распространённый случай), то её аргументы образуют какое-то множество (или набор) значений, которое вместе со значениями самой функции удобно представить в виде таблицы. Именно табличная форма задания логической функции является очень распространённой в повседневной практике. Приведём пример. Пусть некий любитель горного туризма произнёс следующее высказывание:
Моя поездка в горы состоится лишь при условии, что я достану путёвку в лагерь и не будет аврала на работе.
Здесь предполагается, что поездка в горы (G) есть логическая функция двух аргументов – аврала (A) и путёвки (Р). По смыслу высказывания очевидно, что:
если А=0 и Р=0, то G=0;
если А=0 и Р=1, то G=1;
если А=1 и Р=0, то G=0;
если А=1 и Р=1, то G=0.
Весь этот набор фактов принято записывать в виде таблицы:
Такая таблица полностью и однозначно описывает логическую функцию. Таблица, где перечислены обязательно все возможные (!) значения логической функции, называется таблицей истинности.
Количество строк в таблице истинности напрямую связано с числом аргументов функции. Если аргументов два, в таблице будет четыре строки, при трёх аргументах – восемь строк, при четырёх – шестнадцать, при N аргументах — 2N строк. Чтобы не ошибиться при перечислении всех возможных наборов значений аргументов, эти наборы всегда следует располагать в порядке возрастания натурального ряда чисел, записанных в двоичной системе счисления, начиная с нуля. Так, при двух аргументах (А и Р в предыдущем примере) этими наборами будут 00, 01, 10, 11. В случае трёх аргументов будем иметь наборы 000, 001, 010, 011, 100, 101, 110, 111. По аналогии с обычной (классической) математикой можно сказать, что эти наборы образуют область определения функции.
Отметим, что, в отличие от классической математики, где область определения функции может содержать (чаще всего так и бывает) бесконечное множество чисел, область определения логической функции всегда конечна. Именно поэтому и возможно полностью описать логическую функцию с помощью таблицы. Число самих логических функций от N аргументов также конечно. Оно равно в точности . Так, при трёх аргументах может существовать не более 256 различных логических функций.
Множество, состоящее из трёх логических функций с названиями «НЕ». «И», «ИЛИ», называется стандартным, каноническим или булевским базисом в честь уже известного нам Джорджа Буля, подробно исследовавшего эти функции.
Функция НЕ, или инверсия, отрицание – самая простая их всех. По определению, она равна 1, если её единственный аргумент равен 0, и равна 0, если аргумент равен 1. Таблица истинности этой функции, очевидно, состоит из двух строк, и мы не будем её рассматривать. Электронный логический элемент, реализующий эту функцию, называется инвертор. Он имеет один вход и один выход. На рисунке ниже приведено условное графическое изображение инвертора (обратите внимание на кружок на выходе), а также его наглядная реализация в виде размыкающего контакта реле. Этот контакт замкнут (1), когда в обмотке реле нет тока (0), и наоборот, разомкнут (0), когда ток есть (1). На этом же рисунке приведено наиболее распространённое условное обозначение самой функции отрицания А, а именно «А с чертой сверху». Существуют и другие обозначения, например, Not(A), в школьном курсе информатики эта функция обозначена ¬A.
Функция И (по-другому называемая конъюнкция), по определению, равна 1 тогда и только тогда, когда все её аргументы (их может быть два или более) равны 1. Функция называется также логическим умножением, обозначается как A&B (& — знак амперсанд), либо A·B, либо просто AB. Встречается также крайне неудобное обозначение (принятое, к сожалению, в школьном курсе информатики) AΛB. Соответствующий логический элемент называется конъюнктор.
На рисунке ниже приведено два условных графических обозначения конъюнктора – для случая двух и четырёх входов (теоретически их может быть любое количество, большее или равное 2), а также наглядная реализация в виде последовательно включённых замыкающих контактов реле. Электрический сигнал на выходе такой цепочки будет, очевидно, если замкнут и первый, и второй контакт.
Функция ИЛИ (также называемая дизъюнкция), по определению, равна 1 тогда и только тогда, если хотя бы один её аргумент (их может быть, как и в предыдущем случае, два или более) равны 1. Эта функция называется также логическим сложением, обозначается AVB (здесь V – это знак ИЛИ), а также иногда A+B, хотя такое обозначение нельзя признать удачным. Соответствующий логический элемент называется дизъюнктор. На рисунке ниже приведено два условных графических обозначения дизъюнктора – опять же для случая двух и четырёх входов, а также наглядная реализация в виде параллельно включённых замыкающих контактов реле. Электрический сигнал на выходе такой цепочки будет, очевидно, если замкнут или первый, или второй контакт, или оба сразу.
Таблица истинности для случая двух аргументов A и B приведена ниже. Кроме уже знакомых нам И, ИЛИ, в таблицу включены также значения функции «сложение по модулю два» (кратко обозначенную M2), а также широко используемых на практике комбинированных функций И-НЕ (обозначено NAND – от Not And), ИЛИ-НЕ (обозначено NOR – от Not Or).
A
B
A&B
AVB
M2
A NAND B
A NOR B
0
0
1
1
0
1
0
1
0001
0111
0110
1110
1000
Рассмотренный булевский базис (набор функций) И, ИЛИ, НЕ обладает свойством полноты – это означает, что с помощью только этих функций можно выразить любую функцию алгебры логики, сколь бы сложной она ни была (отметим, что существуют и другие базисы с этим же свойством). Соответственно, при помощи одних только конъюнкторов, дизъюнкторов и инверторов можно (в принципе) построить логическую схему любого цифрового устройства, работа которого описывается в терминах алгебры логики!
Отметим, что приведённые выше обозначения логических элементов относятся к так называемой европейской системе. В отечественном школьном курсе информатики (Угринович Н.Д. и др.) используется другая символика, а именно:
Студенты, не занимавшиеся ранее цифровой электроникой, скорее всего, знакомы именно с этими обозначениями, оставшимися в памяти после школы. В инженерной литературе они практически не применяются. Существует также и американская система обозначений элементов, рассматривать которую здесь не будем.
Тема 2. Построение и моделирование логических схем
Представление логической функции в виде таблицы истинности – не единственно возможное. Располагая такой таблицей, можно получить представление функции в виде формулы, а затем, если это необходимо, построить по этой формуле логическую схему устройства, реализующего данную функцию.Пусть дана таблица истинности для какой-то функции трёх переменных (здесь для экономии места таблица разбита на две части, размещённые рядом):
A
B
C
F
A
B
C
F
0000
0011
0101
0
1
1
0
1111
0011
0101
0
0
1
0
Мы видим, что столбец F заполнен нулями и единицами, в этом наборе оказалось три единицы, все остальные – нули. Откуда взялись эти данные? Они определяются постановкой задачи на разработку конкретного цифрового устройства. Сейчас наша цель – перейти от таблицы к формуле.
Делается это очень просто. Для каждой строки таблицы, содержащей 1 в столбце F, следует выписать так называемую элементарную конъюнкцию трёх входных переменных. Переменные A, B, C соединяем знаком конъюнкции (то есть попросту пишем переменные рядом, как при операции умножения) и затем ставим знак инверсии (черту над буквой) там, где во входном наборе переменных стоит ноль, и оставляем без инверсии там, где стоит единица:
Теперь полученные элементарные конъюнкции соединяем, как слагаемые в обычной алгебре, знаками дизъюнкции:
Выражение, которое у нас получилось, носит название совершенная дизъюнктивная нормальная форма (сокращённо СДНФ). Это и есть искомое представление логической функции в виде формулы. СДНФ всегда содержит ровно столько слагаемых, сколько единиц в таблице истинности; каждое слагаемое содержит обязательно все переменные, причём каждая из них входит в формулу либо непосредственно, либо в виде инверсии.
Существуют также представления логической функции в виде ДНФ (дизъюнктивных нормальных форм, без слова «совершенный»), когда каждое слагаемое содержит не обязательно все переменные.Следующий шаг – это переход от СДНФ к логической схеме.Стандартный вид логической схемы, построенной по СДНФ (и вообще любой ДНФ) – это так называемая трёхъярусная структура. В первом ярусе схемы располагаются инверторы (в нашем случае 555LN1); их количество не превосходит количества переменных-аргументов функции, Второй ярус образуют конъюнкторы (в нашем случае 555LI3); их число равно количеству слагаемых (элементарных конъюнкций). Наконец, третий ярус – это дизъюнктор, вырабатывающий выходной сигнал функции:
При построении этой схемы было учтено, что в учебной библиотеке логических элементов TTL.SLB системы PCAD нет, к сожалению, дизъюнктора с тремя входами, поэтому в третьем ярусе применено каскадное включение двух дизъюнкторов с двумя входами каждый (а именно 555LL1).Схема построена. Уже в таком виде её можно моделировать в системе PCAD, хотя в дальнейшем мы будем подвергать её существенной доработке. Работа с этой системой описана в отдельном пособии, кроме того, самые необходимые сведения будут приведены ниже. Мы будем предполагать, что исходный файл со схемой, построенный в программе-редакторе схем PCCAPS, имеет имя F31.SCH, из которого после обработки программами PCNODES и PRESIM получился файл F31.NET. Рекомендуем использовать следующее содержимое CMD-файла:
LOAD F31.NET
CYCLE 10
GEN [0 0] A (S0/4 S1/4)
GEN [0 0] B (S0/2 S1/2)
GEN [0 0] C (S0/1 S1/1)
^
DISPLAY 1
SIM 25
Переменная A, как следует из таблицы истинности, изменяется медленнее всего (в её столбце идут сверху вниз сначала четыре нуля, затем четыре единицы), а переменная C – быстрее всего (0-1-0-1…). Исходя из этого и были выбраны параметры (длительность периода нуля – s0 и периода единицы – s1) в командах GEN.Рассматривая временную диаграмму, построенную программой PCLOGS в результате обработки этого файла, мы должны убедиться, что она (диаграмма) полностью соответствует заданной таблице истинности. Если это не так, придётся искать ошибку в схеме или командном файле.

высшего профессионального образования ФИЗИЧЕСКИЙ ФАКУЛЬТЕТКАФЕДРА РАДИОЭЛЕКТРОНИКИКоршунов Алексей Дмитриевич Методическое пособие к лабораторным работам по курсу«Теория конечных автоматов»
Содержание Предисловие ……………………………………………………………….….3Тема 1. Логические функции. Булевский базис ……………………………4Тема 2. Построение и моделирование логических схем ………………….7 Тема 3. Методика работы в системе PCAD …………………………….…9Тема 4. Минимизация (упрощение) логических функций……………….14Тема 5. Дополнительные сведения о логических функциях ……………16Тема 6. Пример реализации функции в инвертирующем базисе ……….18Тема 7. Этапы построения логической схемы. Варианты заданий………19Тема 8. Цифровые устройства без памяти8.1. Дешифраторы……………………………………………………198.2. Шифраторы………………………………………………………208.3. Мультиплексоры………………………………………………..218.4. Схемы преобразования произвольных кодов…………………228.5. Сумматоры и арифметические устройства……………………23Тема 9. Цифровые устройства с памятью9.1. Триггеры…………………………………………………………249.2. Регистры и счётчики……………………………………………26

Моим лучшим друзьям

Михаилу и Григорию

посвящается

ПредисловиеИнтенсивное развитие цифровой электроники в начале XXI века ставит перед профессиональными учебными заведениями страны множество вопросов, связанных с изучением методов анализа и синтеза схем электронных устройств дискретного принципа действия, работающих с логическими сигналами. Это относится в первую очередь к таким специальностям, как «Автоматизированные системы управления», «Радиофизика и электроника», «Телекоммуникации» и ряду других.На физическом факультете ИГУ студенты III курса изучают дисциплину «Теория конечных автоматов», частью которой является рассмотрение методов логического проектирования цифровых электронных схем. В процессе изучения дисциплины студенты должны выполнить цикл лабораторных работ по синтезу схем различных цифровых устройств и моделированию этих схем на компьютере в системе PCAD. Сведения, необходимые для выполнения этих работ, представлены в настоящем пособии.Учебный материал пособия разделён на структурные единицы, названные здесь темами. За одно лабораторное занятие могут быть изучены одна, две и более такие темы, в зависимости от уровня подготовки студента. Пособие будет особенно полезно студентам, пропустившим какие-либо занятия, позволяя им быстро нагнать упущенное.Пособие может также оказаться полезным для преподавателей, ведущих лабораторные занятия по данному предмету – с целью быстро «освежить» материал в памяти, наметить и уточнить планы будущей работы со студентами. В процессе подготовки пособия был использован графический редактор программной системы LogModel с целью подготовки изображений цифровых схем. Автор пособия выражает глубокую благодарность разработчику системы LogModel, выпускнику физического факультета ИГУ Агафонникову Владимиру Анатольевичу.

Тема 1. Логические функции. Булевский базис

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

Зарождение логики как науки происходило ещё в античные времена, в частности, Аристотелем были сформулированы основные её законы. В то время логика мыслилась исключительно как наука о человеческих высказываниях и рассуждениях. В XIX веке английским математиком Джорджем Булем (George Boole) были сформулированы и развиты базовые положения математической логики. В XX веке алгебра логики нашла своё новое применение – стала использоваться как средство описания работы электрических и электронных схем дискретного действия.

Алгебра логики имеет дело с логическими переменными, то есть такими переменными, которые могут принимать только два значения, изображаемые как ДА и НЕТ, ИСТИНА и ЛОЖЬ, TRUE и FALSE, 1 и 0. Наиболее распространено последнее обозначение – в силу его краткости. При этом 1 и 0 нельзя трактовать как числа, над ними нельзя производить обычные арифметические действия. Не следует смешивать алгебру логики с арифметикой двоичной системы счисления.

Логические переменные хорошо описывают состояния таких объектов, как реле, тумблеры, кнопки и т.д., то есть таких, которые могут находиться в двух чётко различимых состояниях – включено или выключено. Сюда относятся и полупроводниковые логические элементы, которые при определённых условиях могут находиться в двух различных состояниях. Существуют также логические функции одной или нескольких переменных, которые тоже могут принимать лишь значения 0 и 1.

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

Моя поездка в горы состоится лишь при условии, что я достану путёвку в лагерь и не будет аврала на работе.

Здесь предполагается, что поездка в горы (G) есть логическая функция двух аргументов – аврала (A) и путёвки (Р). По смыслу высказывания очевидно, что:

  • если А=0 и Р=0, то G=0;
  • если А=0 и Р=1, то G=1;
  • если А=1 и Р=0, то G=0;
  • если А=1 и Р=1, то G=0.

Весь этот набор фактов принято записывать в виде таблицы:

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

Количество строк в таблице истинности напрямую связано с числом аргументов функции. Если аргументов два, в таблице будет четыре строки, при трёх аргументах – восемь строк, при четырёх – шестнадцать, при N аргументах — 2N строк. Чтобы не ошибиться при перечислении всех возможных наборов значений аргументов, эти наборы всегда следует располагать в порядке возрастания натурального ряда чисел, записанных в двоичной системе счисления, начиная с нуля. Так, при двух аргументах (А и Р в предыдущем примере) этими наборами будут 00, 01, 10, 11. В случае трёх аргументов будем иметь наборы 000, 001, 010, 011, 100, 101, 110, 111. По аналогии с обычной (классической) математикой можно сказать, что эти наборы образуют область определения функции.

Отметим, что, в отличие от классической математики, где область определения функции может содержать (чаще всего так и бывает) бесконечное множество чисел, область определения логической функции всегда конечна. Именно поэтому и возможно полностью описать логическую функцию с помощью таблицы. Число самих логических функций от N аргументов также конечно. Оно равно в точности . Так, при трёх аргументах может существовать не более 256 различных логических функций.

Множество, состоящее из трёх логических функций с названиями «НЕ». «И», «ИЛИ», называется стандартным, каноническим или булевским базисом в честь уже известного нам Джорджа Буля, подробно исследовавшего эти функции.
Функция НЕ, или инверсия, отрицание – самая простая их всех. По определению, она равна 1, если её единственный аргумент равен 0, и равна 0, если аргумент равен 1. Таблица истинности этой функции, очевидно, состоит из двух строк, и мы не будем её рассматривать. Электронный логический элемент, реализующий эту функцию, называется инвертор. Он имеет один вход и один выход. На рисунке ниже приведено условное графическое изображение инвертора (обратите внимание на кружок на выходе), а также его наглядная реализация в виде размыкающего контакта реле. Этот контакт замкнут (1), когда в обмотке реле нет тока (0), и наоборот, разомкнут (0), когда ток есть (1). На этом же рисунке приведено наиболее распространённое условное обозначение самой функции отрицания А, а именно «А с чертой сверху». Существуют и другие обозначения, например, Not(A), в школьном курсе информатики эта функция обозначена ¬A.

Функция И (по-другому называемая конъюнкция), по определению, равна 1 тогда и только тогда, когда все её аргументы (их может быть два или более) равны 1. Функция называется также логическим умножением, обозначается как A&B (& — знак амперсанд), либо A·B, либо просто AB. Встречается также крайне неудобное обозначение (принятое, к сожалению, в школьном курсе информатики) AΛB. Соответствующий логический элемент называется конъюнктор.

На рисунке ниже приведено два условных графических обозначения конъюнктора – для случая двух и четырёх входов (теоретически их может быть любое количество, большее или равное 2), а также наглядная реализация в виде последовательно включённых замыкающих контактов реле. Электрический сигнал на выходе такой цепочки будет, очевидно, если замкнут и первый, и второй контакт.

Функция ИЛИ (также называемая дизъюнкция), по определению, равна 1 тогда и только тогда, если хотя бы один её аргумент (их может быть, как и в предыдущем случае, два или более) равны 1. Эта функция называется также логическим сложением, обозначается AVB (здесь V – это знак ИЛИ), а также иногда A+B, хотя такое обозначение нельзя признать удачным. Соответствующий логический элемент называется дизъюнктор. На рисунке ниже приведено два условных графических обозначения дизъюнктора – опять же для случая двух и четырёх входов, а также наглядная реализация в виде параллельно включённых замыкающих контактов реле. Электрический сигнал на выходе такой цепочки будет, очевидно, если замкнут или первый, или второй контакт, или оба сразу.

Таблица истинности для случая двух аргументов A и B приведена ниже. Кроме уже знакомых нам И, ИЛИ, в таблицу включены также значения функции «сложение по модулю два» (кратко обозначенную M2), а также широко используемых на практике комбинированных функций И-НЕ (обозначено NAND – от Not And), ИЛИ-НЕ (обозначено NOR – от Not Or).

A B A&B AVB M2 A NAND B A NOR B
0

0

1

1

0

1

0

1

0001 0111 0110 1110 1000

Рассмотренный булевский базис (набор функций) И, ИЛИ, НЕ обладает свойством полноты – это означает, что с помощью только этих функций можно выразить любую функцию алгебры логики, сколь бы сложной она ни была (отметим, что существуют и другие базисы с этим же свойством). Соответственно, при помощи одних только конъюнкторов, дизъюнкторов и инверторов можно (в принципе) построить логическую схему любого цифрового устройства, работа которого описывается в терминах алгебры логики!

Отметим, что приведённые выше обозначения логических элементов относятся к так называемой европейской системе. В отечественном школьном курсе информатики (Угринович Н.Д. и др.) используется другая символика, а именно:

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

Тема 2. Построение и моделирование логических схем

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

A B C F A B C F
0000 0011 0101 0

1

1

0

1111 0011 0101 0

0

1

0

Мы видим, что столбец F заполнен нулями и единицами, в этом наборе оказалось три единицы, все остальные – нули. Откуда взялись эти данные? Они определяются постановкой задачи на разработку конкретного цифрового устройства. Сейчас наша цель – перейти от таблицы к формуле.

Делается это очень просто. Для каждой строки таблицы, содержащей 1 в столбце F, следует выписать так называемую элементарную конъюнкцию трёх входных переменных. Переменные A, B, C соединяем знаком конъюнкции (то есть попросту пишем переменные рядом, как при операции умножения) и затем ставим знак инверсии (черту над буквой) там, где во входном наборе переменных стоит ноль, и оставляем без инверсии там, где стоит единица:

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

Выражение, которое у нас получилось, носит название совершенная дизъюнктивная нормальная форма (сокращённо СДНФ). Это и есть искомое представление логической функции в виде формулы. СДНФ всегда содержит ровно столько слагаемых, сколько единиц в таблице истинности; каждое слагаемое содержит обязательно все переменные, причём каждая из них входит в формулу либо непосредственно, либо в виде инверсии.

Существуют также представления логической функции в виде ДНФ (дизъюнктивных нормальных форм, без слова «совершенный»), когда каждое слагаемое содержит не обязательно все переменные.Следующий шаг – это переход от СДНФ к логической схеме.Стандартный вид логической схемы, построенной по СДНФ (и вообще любой ДНФ) – это так называемая трёхъярусная структура. В первом ярусе схемы располагаются инверторы (в нашем случае 555LN1); их количество не превосходит количества переменных-аргументов функции, Второй ярус образуют конъюнкторы (в нашем случае 555LI3); их число равно количеству слагаемых (элементарных конъюнкций). Наконец, третий ярус – это дизъюнктор, вырабатывающий выходной сигнал функции:

При построении этой схемы было учтено, что в учебной библиотеке логических элементов TTL.SLB системы PCAD нет, к сожалению, дизъюнктора с тремя входами, поэтому в третьем ярусе применено каскадное включение двух дизъюнкторов с двумя входами каждый (а именно 555LL1).Схема построена. Уже в таком виде её можно моделировать в системе PCAD, хотя в дальнейшем мы будем подвергать её существенной доработке. Работа с этой системой описана в отдельном пособии, кроме того, самые необходимые сведения будут приведены ниже. Мы будем предполагать, что исходный файл со схемой, построенный в программе-редакторе схем PCCAPS, имеет имя F31.SCH, из которого после обработки программами PCNODES и PRESIM получился файл F31.NET. Рекомендуем использовать следующее содержимое CMD-файла:

LOAD F31.NET

CYCLE 10

GEN [0 0] A (S0/4 S1/4)

GEN [0 0] B (S0/2 S1/2)

GEN [0 0] C (S0/1 S1/1)

^

DISPLAY 1

SIM 25

Переменная A, как следует из таблицы истинности, изменяется медленнее всего (в её столбце идут сверху вниз сначала четыре нуля, затем четыре единицы), а переменная C – быстрее всего (0-1-0-1…). Исходя из этого и были выбраны параметры (длительность периода нуля – s0 и периода единицы – s1) в командах GEN.Рассматривая временную диаграмму, построенную программой PCLOGS в результате обработки этого файла, мы должны убедиться, что она (диаграмма) полностью соответствует заданной таблице истинности. Если это не так, придётся искать ошибку в схеме или командном файле.

булевский базис алгебра логики,электронных схем дискретного действия,превосходит количества переменных-аргументов функции,display sim переменная a,столбец f заполнен нулями,занимавшиеся ранее цифровой электроникой,учебный материал пособия разделён,американская система обозначений элементов,c соединяем знаком конъюнкции,программе-редакторе схем pccaps

Комментариев нет

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Планы мероприятий
Игра викторина по ЭКОЛОГИИ-10 класс

  Цель игры «Викторина по экологии» : углубить экологические знания Весь класс разбит на четыре команды по 6 человек. Время обдумывания ответа -1 минута. Ведущий читает высказывания великих людей с паузами , там , где пропущены слова. Команды должны вставить эти слова «Оценивать … только по стоимости её материальных богатств- …

Задания
Хирургия и Реаниматология. Тесты. Методическое пособие

Тестовые задания. Хирургия и Реаниматология.   Профилактика хирургической инфекции. Инфекционная безопасность в работе фельдшера   Обезболивание   Кровотечение и гемостаз   Переливание крови и кровозаменителей, инфузионная терапия   Десмургия   Ведение больных в полеоперационном периоде   Синдром повреждения. Открытые повреждения мягких тканей. Механические повреждения костей, суставов и внутренних органов   …

Планы занятий
Профориентационный тест Л.А. Йовайши на определение склонности человека к тому или иному роду деятельности

ПРОФЕССИЯ – это вид трудовой деятельности человека, который требует определенного уровня знаний, специальных умений, подготовки человека и при этом служит источником дохода. Профессиональная принадлежность – одна из важнейших социальных ролей человека так как, выбирая профессию, человек выбирает себе не только работу, но и определенные нормы, жизненные ценности и образ жизни, …