вход Вход Регистрация



Общая задача минимизации булевых функций может быть сформулирована таким образом: найти аналитическое выражение заданной булевой функции в форме, содержащей минимальное число букв. Эта задача достаточно хорошо исследована в классе дизъюнктивно – конъюнктивных форм.

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

 

Определение: Булева функция q(x1… xn) называется импликантой булевой функции f(x1… xn) если для любого набора переменных, на котором, справедливо .

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

1. Дизъюнкция любого числа импликант булевой функции так же является импликантой этой функции.

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

Пример:

x1 x2 x3 f q1 q2 q3 q4 q5 q6 q7
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

0

0

1

1

0

 

0

0

0

0

0

0

1

0

 

0

0

0

0

0

1

0

0

 

0

0

0

0

0

1

1

0

 

0

0

1

0

0

0

0

0

 

0

0

1

0

0

0

1

0

 

0

0

1

0

0

1

0

0

 

0

0

1

0

0

1

1

 

и простые импликанты.

Сокращенная ДНФ :

Импликанты и покрывают своими "1" все "1" функции .

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

Определение: СкДНФ булевой функции называется тупиковой, если в ней отсутствуют лишние простые импликанты.

Тупиковые ДНФ булевых функций , содержащие минимальное число букв, являются минимальными. МДНФ может быть несколько.

Случайные новости

7.2 Последовательные регистры

Последовательный (или сдвигающий) регистр обеспечивает последовательную запись кода числа. Для этого на информационный вход регистра последовательно подаются значения двоичных разрядов числа. Сдвигающие импульсы, поступающие на тактовые входы, передают записанную информацию от разряда к разряду вправо или влево. В однотактных сдвигающих регистрах при поступлении одного тактирующего импульса обеспечивает сдвиг одновременно всего числа на один разряд вправо или влево. В зависимости от количества каналов, по которым поступает информация на входы разрядов регистра, различают регистры парафазные (информация на каждый разряд поступает по двум каналам Q и ) и однофазные (информация, поступает по одному каналу Q или ). При построении сдвигающих регистров применяются триггеры типа – RS, – Д и – JК. Наиболее просто регистр сдвига реализуется на Д-триггерах (рис.7.2,а). Выход Q предыдущего разряда соединяется с входом Д последующего. Благодаря этому каждый тактовый импульс устанавливает последующий триггер в состояние, в котором до этого находился предыдущий, осуществляя тем самым сдвиг информации на разряд вправо. Вход аi первого разряда служит для приема в регистр информации в виде последовательного кода. С каждым ТИ на этот вход должен подаваться код нового разряда входной информации. С выхода Q3 последнего триггера снимается последовательный код с задержкой относительно входного последовательного кода на число периодов ТИ, равное числу разрядов регистра. На рис.7.2,б показана схема сдвигающего регистра на JK- триггерах. В этой схеме входы J и К последующих триггеров соединены с выходами соответственно Q и предыдущих.

Рис.7.2. Сдвигающие регистры

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

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

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

а)

(б)

Рис.7.3. Сдвигающие регистры: а – параллельно-последовательный регистр

на Д-триггерах; б – преобразователь параллельного кода

в последовательный и наоборот на базе регистра сдвига.

© 2019
  • Сайт "Литературка"
  • мы собираем различную техническую, образовательную, научную литратуру