4355

Компьютерная схемотехника и архитектура компьютеров

Конспект

Информатика, кибернетика и программирование

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

Русский

2012-11-16

446.5 KB

61 чел.

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

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

В общем случае проектируемое КЦУ может быть представлено в виде черного ящика (ЧЯ), имеющего n входов и m выходов. Единственно, что изначально известно об этом ЧЯ – это требуемый алгоритм его функционирования, т.е. характер связи между входными воздействиями и выходными сигналами (реакциями). Проектирование сводится к определению оптимальной (в некотором смысле) структуры (схемы) КЦУ (ЧЯ), реализуемой в заданном базисе ЛЭ. Другими словами, проектирование КЦУ сводится к нахождению схемы КЦУ, удовлетворяющей требуемому алгоритму функционирования при двух следующих ограничениях: во-первых, схема КЦУ должна быть реализована с помощью ЛЭ заданного функционального полного набора; во-вторых, поскольку требуемый алгоритм функционирования, в общем случае, может быть реализован с помощью различных схем, то должна быть определена (выбрана) некоторая, в определенном смысле, наилучшая (оптимальная) схема, например, схема, отличающаяся минимумом аппаратурных затрат, т.е. минимальным числом ЛЭ или ИС.

Процесс проектирования КЦУ в общем случае включает следующие этапы:

  1.  Словесное описание алгоритма функционирования КЦУ, т.е. описание работы устройства в понятийной форме (на обычном языке).
  2.  Оценка размерности задачи и решение вопроса о проектировании КЦУ в целом или по частям, чему предшествует разделение (условное) КЦУ на составные части. В отдельных случаях для снижения трудоемкости и громоздкости задачи проектирования КЦУ разбивается на ряд более простых устройств (узлов), в совокупности реализующих требуемый алгоритм функционирования, проектирование которых не составляет особых сложностей.
  3.  Переход от словесного к формализованному заданию алгоритма функционирования КЦУ с помощью логических (булевых) функций.
  4.  Минимизация логических функций.
  5.  Преобразование минимальных форм логических функций к виду, реализуемому ЛЭ заданного функционально полного набора.
  6.  Построение схемы КЦУ по полученным (этапы 1-5) логическим функциям.

1.1 Формы представления алгоритмов функционирования КЦУ

Алгоритм функционирования любого КЦУ может быть представлен в виде словесного описания.

Например, алгоритм функционирования КЦУ, фиксирующего совпадение (эквивалентность) двух двоичных переменных может быть задан следующим образом: КЦУ должно формировать на выходе сигнал уровня логической единицы (у=1) тогда и только тогда, когда совпадают двоичные переменные х1 и х2 на его входах, в иных случаях сигнал на выходе КЦУ должен быть уровня логического нуля (у=0).

Условно сказанное можно записать в виде y = x1 ~ x2; запись следует читать: «у равно х1 эквивалентно (или равнозначно) х2». Эту же функцию можно представить в табличной форме (рис. 1).

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

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

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

Количество минтермов и макстермов заданного числа n переменных совпадает с числом различных наборов переменных – 2n.

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

СКНФ логической функции – это конъюнкция макстермов, соответствующих входным наборам, для которых функция равна нулю.

  1.  Алгоритм перехода от таблицы истинности

логической функции к ее записи в виде СДНФ

  1.  Выбрать в таблице такие наборы входных переменных, на которых функция обращается в единицу;
  2.  Записать минтермы для выбранных наборов входных переменных. При этом необходимо руководствоваться следующим правилом: если значение входной переменной в наборе – единичное, то она записывается в прямой форме, если же значение переменной – нулевое, то – в инверсной форме;
  3.  Полученные минтермы объединить между собой знаками дизъюнкции.

Пример 1. Получить СДНФ логической функции y = x1 ~ x2.

Решение. Из таблицы истинности (рис.1.) следует, что функция у=1 на двух наборах входных переменных: (0 0) и (1 1). Для выбранных наборов записываем минтермы в соответствии с п.2 приведенного выше алгоритма:

,  .

Соединив минтермы знаком дизъюнкции, получим СДНФ функции:

1.3 Алгоритм перехода от таблицы истинности

логической функции к ее записи в виде СКНФ

  1.  Выбрать в таблице истинности такие наборы входных переменных, на которых функция принимает нулевые значения;
  2.  Записать макстермы для выбранных наборов. При этом следует руководствоваться следующим правилом: если значение входной переменной в наборе нулевое, то она записывается в прямой форме, если значение переменной единичное, то – в инверсной форме;
  3.  Полученные макстермы соединить знаками конъюнкции.

Пример 2. Получить СКНФ логической функции y = x1 ~ x2.

Решение. Из таблицы истинности (рис.1.), следует, что функция y=x1~x2=0 на двух наборах входных переменных (0 1) и (1 0). Для указанных наборов записываем макстермы

и .

Соединив их знаком конъюнкции, получим СКНФ функции:

Нетрудно убедиться, что СДНФ и СКНФ функции эквивалентны.

1.4 Минимизация логических функций

Работа любого КЦУ с одним выходом может быть описана логическим выражением или системой m логических выражений, если у КЦУ m выходов. Другими словами, всякому КЦУ с одним выходом или каждому из m выходов многовыходного КЦУ взаимно однозначно соответствует логическое выражение, в котором буквы соответствуют входным переменным, а знаки операций – ЛЭ, выполняющим эти операции. Подобные логические выражения именуют уравнениями связи «вход-выход» КЦУ. В этих условиях упрощение схемы КЦУ сводится к минимизации логических выражений, соответствующих этим устройствам.

СДНФ и СКНФ используются для первоначального представления логических функций, но эти формы, как правило, неэкономичны для построения схем КЦУ. Прежде чем строить схему, реализующую логическую функцию, ее необходимо минимизировать, т.е. найти такую эквивалентную форму представления, при которой выражение для функции будет состоять из наименьшего числа переменных (букв).

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

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

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

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

Например,

Операция объединения смежных минтермов по разнящейся переменной именуется склеиванием.

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

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

Процесс минимизации логических функций значительно упрощают карты Карно. Карты Карно представляют собой прямоугольную таблицу (матрицу), разбитую горизонтальными и вертикальными линиями на клетки (ячейки). Общее число ячеек совпадает с числом минтермов и равно 2n, где n – число переменных упрощаемой функции. Таким образом, каждая ячейка карты соответствует определенному минтерму, размещение которых осуществляется таким образом, чтобы смежные минтермы находились в соседних ячейках. Соседними считаются ячейки, имеющие общие стороны, а также расположенные на краях одних и тех же строк или столбцов карты.

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

Для функции двух переменных карта Карно представляет собой таблицу, разделенную на четыре ячейки, по одной на каждый входной набор (рис. 2, а). Строки карты связаны с переменной , столбцы – с переменной . Расположенная слева вверху ячейка соответствует входному набору (0 0) или минтерму (), расположенная ниже ее ячейка соответствует входному набору (1 0) или минтерму () и т.д.

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

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

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



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

x2

х1

x3

а)

х3

*

х2

х1

x4

б)

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

Минтермы, соответствующие определенным ячейкам карты, образуются из наборов групп переменных (рис. 2) или наборов переменных (рис. 3), обозначающих строку и столбец, на пересечении которых расположена рассматриваемая ячейка. Например, ячейке, выделенной на рис. 3,б соответствует минтерм .


1.5 Алгоритм минимизации логических функций, заданных

в СДНФ при помощи карт Карно

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

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

При образовании блоков необходимо придерживаться следующих правил:

2.1. Одни и те же ячейки могут входить в несколько блоков;

2.2. Блоки должны покрывать все обозначенные ячейки;

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

3. Для каждого блока записать логическое выражение в виде конъюнкции тех переменных, значения которых совпадают у всех объединенных в блок ячеек. Если блок покрывает 2, 4 или более ячеек, то конъюнкции представляют собой импликанты склеиваемых минтермов. Ранг полученных таким образом импликант меньше ранга минтермов, объединенных в контур, на К единиц.

4. Логические выражения для блоков объединить значками дизъюнкции. Полученное выражение представляет собой минимизированную дизъюнктивную нормальную форму (МДНФ) логической функции.

Пример 3. Минимизировать с помощью карты Карно логическую функцию:

Решение. Упрощаемая функция трех переменных задана своей СДНФ. Выбираем соответствующую карту Карно (рис. 3,а) и обозначаем ее ячейки, соответствующие минтермам функции. Так как упрощаемая функция содержит пять минтермов, то и на карте Карно должно быть пять обозначенных ячеек (рис.4).

х1

1

1

 1

1

1

Рис. 4. Пример минимизации функции

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

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

1.6 Минимизация частично определенных

и инверсных логических функций

Частично (не полностью) определенными называют функции, значения которых заданы лишь для части множества возможных наборов их переменных. Такие функции достаточно часто встречаются в задачах проектирования КЦУ, где их происхождение обусловлено тем, что некоторые сочетания (комбинации) входных переменных при работе КЦУ не имеют места.

Наборы переменных, для которых функция не определена, называют избыточными или запрещенными. Например, избыточные наборы будут иметь место при реализации двоично-десятичного кода, т.е. при представлении десятичных цифр от 0 до 9 двоичным кодом. Действительно, для такого представления необходимо использовать четыре двоичные переменные (четыре двоичных разряда), и из общего числа 16 наборов этих переменных использовать только первые 10. Следовательно, 6 наборов оказываются избыточными.

При минимизации частично определенных функций производят их доопределение, которое состоит в произвольном задании значений функции, соответствующих избыточным наборам. Эти значения можно выбирать равными 0 или 1. Доопределение выполняют таким образом, чтобы результирующая МДНФ функции была наиболее простой (при этом учитывается возможность выполнения дополнительных склеиваний при доопределении функции).

Пример 4. Минимизировать логическую функцию, заданную своей таблицей истинности (рис. 5, а). Значения функции, соответствующие трем последним наборам входных переменных, не определены (что отмечено * в столбце yисх). На карте Карно рассматриваемой функции (рис. 5, б) ячейки для избыточных наборов также отмечены звездочками. Доопределение функции единицами для всех избыточных наборов позволяет представить ее МДНФ в виде:

Для сравнения приведем выражение исходной функции:

,

которую без приема доопределения упростить невозможно.

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

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

х1

х2

х3

уисх

удоопр

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

0

0

1

1

*

*

*

0

0

0

1

1

1

1

1

а)

х1

*

1

х3

1

*

 

х2

б)

Рис. 5. Таблица истинности (а) и карта Карно (б)

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

Пример 5. Упростить функцию, заданную таблицей истинности (рис. 6).

Решение. СДНФ требуемой (прямой) функции

х1

х2

х3

y

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

1

1

1

1

1

0

1

0

0

0

0

0

0

1

0

1

Рис. 6. Таблица истинности функции

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

Для  СДНФ будет значительно проще:

Последнее выражение более обозримо, чем для у, и легко минимизируется:

, откуда .

1.7 Преобразование минимальных форм логических функций к виду, реализуемому ЛЭ заданного функционально полного набора

Любая логическая функция, как было сказано выше, может быть записана в виде СДНФ или СКНФ. Следовательно, любую функцию n переменных можно представить с помощью набора трех элементарных функций: инверсии, дизъюнкции и конъюнкции. Возможны и другие наборы функций, с помощью которых может быть выражена произвольная функция.

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

Набор логических функций инверсия (НЕ), дизъюнкция (ИЛИ) и конъюнкция (И) получил наименование основного (ОФПН).

Среди других наборов функций, образующих ФПН, особый интерес представляют так называемые монофункциональные наборы, содержащие всего одну булеву функцию. Таковыми, в частности, являются набор, состоящий только из функции «штрих Шеффера» (И-НЕ) и набор, состоящий только из функции «стрелка Пирса» (ИЛИ-НЕ).

1.8 Минимальные формы в монофункциональных базисах

Основой для получения минимальных форм логических функций в базисах функций штрих Шеффера и стрелка Пирса может служить МДНФ, полученная в результате решения задачи минимизации.

МДНФ представляет собой дизъюнкцию простых импликант и может быть представлена в обобщенном виде:

      (1)

где Ji символ импликант, а d - их количество.

Формулы функций штрих Шеффера и стрелка Пирса для случая r переменных имеют вид:

            (2)

   (3)

Для перехода от МДНФ к минимальной форме в базисе функции штрих Шеффера конъюнкции и дизъюнкции в выражении (1) должны быть заменены функциями вида (2). Это достигается двукратным инвертированием (1) и применением теоремы де Моргана-Шеннона. Первое инвертирование (1) с учетом указанной теоремы приводит к соотношению:

       (4)

Второе инвертирование с учетом закона двойного отрицания дает:

    (5)

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

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

Переход от МДНФ к минимальной форме в базисе функций стрелка Пирса осуществляется заменой импликант в (1) функциями вида (3). Обозначим преобразованную в соответствии с теоремой де Моргана-Шеннона инверсию импликанты  символом Gi. Тогда (4) можно переписать в виде:

             (6)

Трехкратное инвертирование (6) приводит к искомой форме формулы в базисе функций стрелка Пирса

                   (7)

Каждый член дизъюнкции в (7) и инверсия всей дизъюнкции представляет собой функции стрелка Пирса; заключительное инвертирование также может быть выполнено элементами стрелка Пирса (ИЛИ - НЕ). Формулу (7) называют оптимальной дизъюнктивной инверсной формой логической функции или оптимальной инверсной суммой.

Пример. 6. Представить логическую функцию «равнозначность двух переменных» в базисе функций штрих Шеффера и стрелка Пирса.

Решение. СДНФ функции равнозначность двух переменных (приведена выше) имеет вид:

    (8)

Первое инвертирование (8) с учетом теоремы де Моргана приводит к выражению:

.

Второе инвертирование с учетом закона двойного отрицания приводит к искомой форме в базисе функций штрих Шеффера:

   (8.1)

Четырехкратное инвертирование (8.1) дает искомую форму в базисе функций стрелка Пирса:

                 (8.2)

1.9 Проектирование схемы КЦУ в заданном базисе ЛЭ

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

Аналогичным образом могут быть реализованы функции монофункциональных наборов: функции штрих Шеффера – с помощью ЛЭ «И-НЕ», функции стрелка Пирса – с помощью ЛЭ «ИЛИ -НЕ», образующих монофункциональные наборы ЛЭ.

Основой для проектирования КЦУ в ОФПН ЛЭ служит минимальная форма логической функции – МДНФ или МКНФ. Основой для проектирования КЦУ в монобазисном наборе ЛЭ служит оптимальное инверсное произведение или оптимальная инверсная сумма.

Пример 7. Спроектировать схему КЦУ равнозначности двух переменных а) в ОФПН ЛЭ, б) в монофункциональном наборе ЛЭ «И -НЕ», в) в монофункциональном наборе ЛЭ «ИЛИ -НЕ».

Решение. Основой для проектирования являются выражения (8), (8.1) и (8.2) соответственно. Схемы КЦУ, реализующие функцию “равнозначность двух переменных”, приведены на рис.7.

1.10 Проектирование многовыходных КЦУ

На практике часто встречается необходимость проектирования КЦУ, имеющих несколько (m) выходов. В этих случаях для синтеза схемы устройства можно воспользоваться рассмотренной выше последовательностью действий, если представить устройство в виде совокупности соответствующего числа (m) КЦУ, имеющих общие входы. Другими словами, проектирование многовыходного КЦУ сводится к синтезу m одновыходных схем КЦУ, имеющих общие входы х1, х2, …, хn, выходы которых в совокупности образуют выходы устройства: у1, у2, …, уm.

Пример 8. Спроектировать схему КЦУ, вычисляющего значения функции у=х2+3, если х может принимать целые значения в диапазоне от 0 до 3.

Решение. Представим функцию, подлежащую реализации в виде таблицы (рис.8.)

В проектируемом устройстве как аргумент х, так и функция у должны быть представлены в виде двоичных кодов. Перевод х и у в двоичные коды осуществляется по известным правилам преобразования десятичных чисел в двоичные коды. Число разрядов n и m, необходимых для представления х и у в двоичном коде, определяется согласно соотношениям:

n ≥ log2(xmax+1), m ≥ log2(ymax+1).  (9)

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

nlog2(3+1)=2, mlog2(12+1)=4.



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

х2

х1

у4

у3

у2

у1

21

20

23

22

21

20

0

0

1

1

0

1

0

1

0

0

0

1

0

1

1

1

1

0

1

0

1

0

1

0

          

а)        б)

Рис. 9. Условное графическое изображение (а)

и таблица функционирования (б) проектируемого устройства

Из таблицы функционирования для каждого выхода уi (i=1, 2, 3, 4) получим уравнения связи в виде СДНФ:

,

,

.

Упростим (минимизируем) полученные выражения (выражение для у4 не упрощается):

,

,                                                  (10)

.

По полученным МДНФ (10) синтезируем схему устройства, используя ОФПН ЛЭ (рис. 10).

Рис. 10. Схема КЦУ, вычисляющего значения функции у=х2+3,

(область определения х: 0, 1, 2, 3)
2 Задачи  контрольной работы

2.1  Задача 1

2.1. Для каждого КЦУ, предусмотренного заданием (см. табл. 1):

2.1.1. Составить таблицу истинности;

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

2.1.3. Преобразовать полученные в п. 2.1.2. СДНФ к виду, реализуемому в монофункциональном базисе ЛЭ «И-НЕ».

2.1.4. Составить схему КЦУ, используя: а) ЛЭ ОФПН; б) монофункционального набора ЛЭ «И- НЕ».

2.1.5. Собрать схемы КЦУ на стенде и проверить правильность их функционирования.

  1.  Варианты первой задачи

№ варианта

ЗАДАНИЕ

1

Неравнозначность двух двухбитовых переменных

2

Голосования (мажоритарного контроля) «3 из 4»

3

Неравнозначности трех булевых переменных

4

Четности количества единиц в трехразрядном двоичном числе

5

Нечетности количество единиц в четырехразрядном двоичном числе

6

Четности количества нулей в трехразрядном двоичном числе

7

Нечетности количества нулей в трехразрядном двоичном числе

8

Равенства количества нулей и единиц в четырехразрядном двоичном числе

9

Неравенства количества нулей и единиц в четырехразрядном двоичном числе

10

Наличие двух рядом стоящих единиц в четырехразрядном двоичном числе

11

Отсутствие двух рядом стоящих единиц в четырехразрядном двоичном числе

12

Сумма единичных разрядов четырехразрядного слова равна 3

13

Сумма нулевых разрядов четырехразрядного слова равна 3

14

Сумма двух двухбитовых переменных больше 4

15

Разность двух двухбитовых переменных меньше 2

16

Количество нулей четырехразрядного слова больше количества единиц

17

Количество единиц четырехразрядного слова больше или равно количеству нулей

18

Количество нулей четырехразрядного слова равно  количеству единиц

19

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

20

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

21

Значения двух половин четырехразрядного слова равны

22

Значения двух половин четырехразрядного слова не равны

2.2 Задача 2

2.2.1 Минимизируйте выражение, используя карту Карно.

2.2.2 Реализуйте схему на элементах: четные варианты – элементы 2 ИЛИ-НЕ, нечетные – элементы 2 И-НЕ.

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

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

  1.  Варианты второй задачи

№ п/п

Выражение

№  п/п

Выражение

1

0+1+2+5+8+9+10+13

12

5+7+8+9+10+11+12+14

2

0+1+2+9+11+12+13+14+15

13

0+2+5+6+7+8+10+14

3

0+2+3+4+6+7+8+9+14

14

1+3+4+9+10+11+12+13+15

4

0+4+6+8+10+11+12+14

15

0+2+4+6+8+9+12+13

5

1+2+3+5+7+10+13+15

16

0+2+5+6+7+8+10+14

6

0+1+2+3+8+9+10+11+13

17

2+3+4+6+7+8+10+12

7

0+2+4+6+7+8+10+12+14

18

1+2+3+5+6+7+9+10+11

8

1+3+4+6+9+11+12+13+14

19

0+2+4+5+6+8+14

9

0+1+4+5+8+9+10+14+15

20

0+1+2+6+8+9+10+15

10

2+4+5+6+10+12+14

21

0+1+8+9+10+12+14

11

3+4+5+6+7+9+11+13

22

1+2+3+5+8+9+10+14

Примечание: числа в структуре выражения соответствуют значениям клеток в картах Карно.

2.3 Задача 3

2.3.1. Спроектируйте многовыходное КЦУ, реализующее следующую функцию при изменении аргумента от нуля до семи. Результат выводится в виде двоичного кода.

Для нечетных вариантов: Y=2x+A, где A – номер варианта

Для четных вариантов: Y=х/2+А, где А – номер варианта

2.3.2 Реализуйте КЦУ на элементах: четные варианты – элементы 2 ИЛИ-НЕ, нечетные – элементы 2 И-НЕ

3 Содержание отчета

Для каждого спроектированного и исследованного в соответствии с заданием КЦУ должны быть приведены:

3.1. Таблица истинности и логические выражения функции, реализуемых КЦУ, представленные в СДНФ и СКНФ.

3.2. Карты Карно, отражающие ход минимизации логических функций.

3.3. Преобразования, иллюстрирующие переход от МДНФ к оптимальному инверсному произведению.

3.4. Схемы КЦУ, реализованные в ОФПН ЛЭ и монофункциональном наборе ЛЭ «И-НЕ».

4 Контрольные вопросы

  1.  Основные постулаты (аксиомы) и законы алгебры логики.
  2.  Понятия минтермов и макстермов. Дизъюнктивные и конъюнктивные нормальные формы представления функций.
  3.  Понятия смежных минтермов, операции их склеивания, импликант.
  4.  Минимизация логических функций с помощью карт Карно.
  5.  Понятие функционального полного набора (ФПН). Примеры ФПН.
  6.  Последовательность (алгоритм) приведения МДНФ к виду, реализуемому в монофункциональном наборе ЛЭ,
  7.  Реализовать в монофункциональном наборе ЛЭ «И-НЕ» логические функции: инверсия, дизъюнкция трех переменных, конъюнкция трех переменных.
  8.  Реализовать в монофункциональном наборе ЛЭ «ИЛИ -НЕ» логические функции: инверсия, дизъюнкция трех переменных, конъюнкция трех переменных.
  9.  Оцените аппаратурные затраты (количество ИС), потребные для реализации КЦУ «равнозначность двух переменных» а) в ОФПН ЛЭ, б) в монофункциональных наборах ЛЭ. Какое схемотехническое решение является предпочтительным?
  10.  В чем суть операции доопределения логической функции?
  11.  Сколько входов и выходов должно иметь цифровое устройство, вычисляющее значение функции y= 0.5·x+4, если х может принимать целые значения в диапазоне от 0 до 10?
  12.  Какого типа ЛЭ необходимы для построения схемы, реализующей логическую функцию y= x1·x2+x1·x3+x2·x3? Укажите потребное количество ЛЭ и ИС.


Задание 2

ПОСТРОЕНИЕ СЧЕТЧИКОВ

Цель: изучить принципы действия элемента цифровой техники – счетчика. Спроектировать счетчик с нестандартным модулем счета. Спроектировать схему делителя частоты на базе счетчика.

1 Теоретические сведения

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

Счетчики классифицируют по следующим признакам:

способу кодирования — позиционные и непозиционные;

модулю счета — двоичные, десятичные, с произвольным постоянным или переменным (программируемым) модулем;

направлению счета — простые (суммирующие, вычитающие) и реверсивные;

способу организации межразрядных связей — с последовательным, сквозным, параллельным и комбинированным переносами (заемом);

типу используемых триггеров — T, JK, D в счетном режиме;

элементному  базису  —  потенциальные,   импульсные   и   потенциально-импульсные.

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

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

Где ri — вес i-го разряда; Qi, — значение выхода i-го разряда; n — число разрядов.

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

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

По виду переходов простые счетчики подразделяются на суммирующие (прямого счета) и вычитающие (обратного счета). В суммирующих счетчиках каждый прибавляемый импульс увеличивает состояние на единицу. Из М-1-го состояния очередной сигнал  возвращает счетчик в начальное состояние и выдает сигнал переполнения Р. Перенос информации из одного разряда в другой, более старший, имеет место, когда происходит смена состояния 1 на 0.

В вычитающих счетчиках каждый вычитаемый импульс  уменьшает состояние на единицу, После вычитания М импульсов счетчик выдает сигнал заема Z и возвращается в исходное М-1 состояние. Перенос из младшего разряда в старший здесь имеет место при смене состояния младшего разряда с 0 на 1.

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

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

Счетчик, образованный цепочкой из m триггеров, может подсчитать в двоичном коде 2m импульсов. Каждый из триггеров такой цепочки называют разрядом счетчика. Число m определяет количество разрядов двоичного числа, которое может быть записано в счетчик. Число Кcч=2m называют коэффициентом (модулем) счета. Коэффициент счета, таким образом, характеризует число входных импульсов, необходимое для выполнения одного цикла и возвращения в исходное состояние.

Схему двоичного счетчика можно получить с помощью формального синтеза, однако более наглядным путем представляется эвристический. Таблица истинности двоичного счетчика — последовательность двоичных чисел от нуля до М—1. Наблюдение за разрядами чисел, составляющих таблицу, приводит к пониманию структурной схемы двоичного счетчика. Состояния младшего разряда при его просмотре по соответствующему столбцу таблицы показывают чередование нулей и единиц вида 01010101..., что естественно, т. к. младший разряд принимает входной сигнал и переключается от каждого входного воздействия. В следующем разряде наблюдается последовательность пар нулей и единиц вида 00110011... . В третьем разряде образуется последовательность из четверок нулей и единиц 00001111... и т.д. Из, этого наблюдения видно, что следующий по старшинству разряд переключается с частотой, в два раза меньшей, чем данный.

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

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

Различия при этом состоят в направлении переключения предыдущего разряда, вызывающего переключение следующего. При прямом счете следующий разряд переключается при переходе предыдущего в направлении 1-0, а при обратном — при переключении 0-1. Следовательно, различие между вариантами заключается в разном подключении входов триггеров к выходам предыдущих. Если схема строится на счетных триггерах с прямым динамическим управлением, то характер подключения следующих триггеров к предыдущим для получения счетчиков прямого и обратного счета будет соответствовать рисунку ниже.

 

Рисунок 1 - . Структура последовательного счетчика (а), ее реализация на триггерах с прямым динамическим управлением (б) и межразрядные связи реверсивного счетчика (в)

Реверсивный счетчик может работать в качестве суммирующего и вычитающего. Эти счетчики имеют дополнительные входы для задания направления счета. Режим работы определяется управляющими сигналами на этих входах. В программе EWB такие счетчики представлены ИМС 74163 и 74169 (К155ИЕ18, ИЕ17).

Главное достоинство счетчиков с последовательным переносом — простота схемы. Увеличение разрядности осуществляется подключением дополнительных триггеров к выходу последнего триггера. Основной недостаток счетчиков с последовательным переносом — сравнительно низкое быстродействие, поскольку триггеры срабатывают последовательно, один за другим.

Быстродействие счетчика определяется двумя параметрами: разрешающей способностью Траз.сч. и временем установки кода счетчика Туст. Под разрешающей способностью подразумевают минимальное время между двумя входными сигналами, в течение которого не возникают сбои в работе. Обратная величина Fмакс=1/Tpаз,cч, называется максимальной частотой счета. Время установки кода Туст равно времени между моментом поступления входного сигнала и переходом счетчика в новое устойчивое состояние. Эти параметры зависят от быстродействия триггеров и способа их соединения между собой.

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

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

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

Х1

0

1

1

0

0

1

1

1

Х1

0

1

1

0

1

0

0

0

+Х2

1

-Х2

1

У=

1

1

1

0

1

0

0

0

У=

1

1

1

0

0

1

1

1

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

Структура суммирующего синхронного счетчика с параллельным переносом, реализованного на триггерах с управлением фронтом, показана на Рисунок 2.

Рисунок 2 - Схема параллельного счетчика прямого счета

Срабатывание триггеров параллельного счетчика происходит синхронно, и задержка переключения всего счетчика равна задержке одного триггера. В таких счетчиках используются JK- и D-триггеры. В схемном отношении они сложнее счетчиков с последовательным переносом. Число разрядов у этих счетчиков обычно невелико (4...6), поскольку с повышением числа разрядов число внутренних логических связей быстро растет.

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

Счетчики с параллельным переносом (их чаще называют синхронными) в библиотеке EWB представлены счетчиками 74160, 74162, 74163 и 74169 (аналоги — К155ИЕ9, ИЕ11 ИЕ18, ИЕ17 соответственно).

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

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

Делитель частоты с коэффициентом деления 2 представляет собой делитель частоты на 2.

Рисунок 3 Делитель частота на 2

Делитель частоты с коэффициентом деления кратным 2 представляет собой последовательно соединенные делители частоты на 2.

Рисунок 4 - Делитель частоты на 8

1

0

1

0

1

0

1

1

0

1

0

1

Рисунок 5 Временная диаграмма делителя частоты на 8

Рисунок 6 - Делитель частоты на 3

Рисунок 7 - Делитель частоты на 5

Каскадные делители частоты

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

Общий коэффициент деления равен N=N1 N2 N3 Nk.

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

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

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

Результаты проектирования применимы к триггерам разных видов логики, однако реальные схемы при этом могут различаться в деталях. Поскольку принудительная установка в нуль по R-входу у некоторых типов триггеров осуществляется сигналами логического нуля (ТТЛ, ДТЛ), у других — сигналами логической единицы (КМОП), в первом случае должен быть применен логический элемент И-НЕ, во втором — И. Кроме того, в суммирующем счетчике опрокидывание каждого последующего триггера должно происходить тогда, когда сигнал на выходе предыдущего триггера изменяется от 1 к 0, поэтому важен порядок соединения триггеров между собой. Если в счетчике применяются триггеры с прямым управлением (по фронту 0—>1), их входы присоединяются к инверсным выходам предыдущих. В случае триггеров с инверсным управлением входы подключают к прямым выходам. Добавив к исходной схеме несколько дополнительных элементов, можно расширить ее возможности — сделать счетчик с самоостановом (одноразового действия) или обеспечить в режиме деления кратковременный импульс на выходе последнего триггера.

  1.  Задачи  контрольной работы
  2.  

Задача 4. Постройте счетчики с нестандартными значениями модуля счета. Значение модуля счета выберите следующим образом: до 10 номера по списку: n+5; от 11 до 15: n-4; от 16 и выше: n-8.  Четные варианты строят схему последовательного счетчика, нечетные варианты – параллельного.

Задание 5. Постройте делители частоты со следующими значениями коэффициента деления:

Таблица 1  - Индивидуальные задания 2 к лабораторной работе

Вариант

Коэффициент деления

  1.  
  1.  

12

  1.  
  1.  

24

  1.  
  1.  

6

  1.  
  1.  

18

  1.  
  1.  

15

  1.  
  1.  

9

  1.  
  1.  

16

  1.  
  1.  

10

  1.  
  1.  

20

  1.  
  1.  

24

  1.  
  1.  

25

  1.  
  1.  

36

  1.  
  1.  

30

3 Содержание отчета

3.1 Схему принципиальную спроектированного счетчика и делителя.

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

4 Контрольные вопросы

  1.  Что такое счетчик, какого типа они бывают?
  2.  Каким образом создаются счетчики с коэффициентом счета, не кратным 2?
  3.  Приведите основные характеристики счетчиков.
  4.  Разработайте схему счетчика с коэффициентом счета 3 на JK- и D-триггерах.
  5.  Каковы преимущества и недостатки последовательного и параллельного счетчика?
  6.  Основные функциональные назначения счетчиков.
  7.  Схема построения вычитающих счетчиков.
  8.  Реверсивные счетчики.


х1

х2

у

0

0

1

1

0

1

0

1

1

0

0

1

Рис. 1 . Таблица истинности функции y = x1 ~ x2

     х2 х3

00

01

11

10

х1

0

0 0 0

0 0 1

0 1 1

0 1 0

1

1 0 0

1 0 1

1 1 1

1 1 0

б)

х2

0

1

х1         

0

1

00

01

10

11

а)

х3 х4

00

01

11

10

х1х2

00

0000

0001

0011

0010

01

0100

0101

0111

0110

11

1100

1101

1111

1110

10

1000

1001

1011

1010

в)

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

1

2

*

xmax=3

ymax=12

х

0

1

2

3

у

3

4

7

12

Рис. 8. Табличное представление функции у=х2+3

x1

x2

1

1

1

x2

x1x2

x2

x1

x1

x2

x1x2

x1

x1x2

1

1

1

1

1

1

a)

б)

в)

Рис. 7. Схемы КЦУ равнозначности двух переменных, реализованные в ОФПН ЛЭ (а),

 монофункциональных наборах ЛЭ «И- НЕ» (б) и «ИЛИ -НЕ» (в)

x2

Дв. разряды х и у

у1(20)

у2(21)

у3(22)

у4(23)

у=х2+3

х1(20)

х2(21)

есовые

коэф-ты

разрядов

y1(20)

1

1

&

y2(21)

y3(22)

y4(23)

x1(20)

x2(21)

  1.  

 

А также другие работы, которые могут Вас заинтересовать

79274. Нормативно-методическое и правовое обеспечение системы управления персоналом 16.07 KB
  Нормативнометодическое обеспечение системы управления персоналом представляет собой обеспечение документами устанавливающими нормы управления правила и методы организации труда необходимыми для нормальной организации трудовых процессов ведения нормативного хозяйства системы управления. Нормативнометодические документы подразделяются на следующие группы: нормативносправочные определяют нормы времени управленческих действий задания на конкретный период времени инструкции вышестоящих организаций или органов власти;...
79275. Кадровая политика организации – основа формирования стратегии управления персоналом 20.81 KB
  Кадровая политика организации генеральное направление кадровой работы совокупность принципов методов форм организационного механизма по выработке целей и задач направленных на сохранение укрепление и развитие кадрового потенциала на создание квалифицированного и высокопроизводительного сплоченного коллектива способного своевременно реагировать на постоянно меняющиеся требования рынка с учетом стратегии развития организации. Назначение кадровой политики – своевременно формулировать цели в соответствии со стратегией развития...
79276. Система стратегического управления персоналом организации 23.23 KB
  Система стратегического управления персоналом организации Кадровая политика предусматривает в первую очередь формирование стратегии управления персоналом организации. Цель стратегического управления персоналом – обеспечить адекватное состоянию внешней и внутренней среды формирование человеческого капитала предприятия в расчете на долгосрочный период. Стратегическое управление персоналом направлено на решение следующих задач: 1 обеспечение организации необходимым трудовым потенциалом в соответствии со стратегией; 2 формирование внутренней...
79277. Стратегия управления персоналом организации и ее реализация 25.51 KB
  Стратегия управления персоналом организации и ее реализация Стратегическое управление – это система менеджмента ориентирующаяся на человеческий капитал как основу компании гибко реагирующая на динамику изменений внешней среды проводящая своевременные изменения в организации позволяющие добиться конкурентных преимуществ через приближение своей деятельности к запросам покупателей что обеспечивает долгосрочное устойчивое развитие и достижение поставленных целей. Стратегическое управление персоналом – это управление формированием...
79280. Маркетинг персонала 14.68 KB
  Маркетинг персонала это вид деятельности который направлен на выявление потребности в персонале а также удовлетворение этих потребностей то есть покрытие потребности организации в персонале. С одной стороны маркетинг персонала можно рассматривать как философию организации и стратегию управления человеческими ресурсами компании а с другой стороны маркетинг персонала это одна из функций кадровой службы организации. Однако маркетинг персонала подходит к вопросу определения и покрытия потребности в персонале с точки зрения рыночного...
79281. Планирование и прогнозирование потребности в персонале 13.31 KB
  Планирование потребностей в персонале как и любой хороший план базируется на предпосылках которые позволяют делать предположения относительно будущего. Если Вы разрабатываете планы потребностей в персонале Вам скорее всего понадобятся три вида прогнозов: один для разработки Ваших требований к персоналу другой для поиска кандидатов со стороны и третий для поиска кандидатов внутри организации. Прогнозирование потребности в персонале строится на основе анализа прогнозов спроса и предложения для определения перспективной нехватки или...
79282. Планирование производительности труда и показателей по труду 14.55 KB
  Производительность труда – это плодотворность продуктивность производственной деятельности людей. Планирование производительности труда определение уровня производительности труда и темпов ее роста обеспечивающих конкурентоспособность организации. На уровень и динамику производительности труда влияет множество факторов.