Минимизация булевых функций с помощью карт Карно

⇐ Назад

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

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

При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид

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

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

· площадь контура покрытия должна быть S_k = 2^m-i клеток, где – целое число, m – число переменных. Если, например, m = 3, то S_k = 1, 2, 4, или 8 клеток;

· число сокращаемых переменных N_перем. = log₂ S_k , т.е. при S_k = 1 не сокращается ни одна переменная, при S_k = 2 сокращается одна переменная и т.д.

10. Алгебраический метод минимизации.

Минимизация как упрощение формул в булевой алгебре (как и в любой другой алгебре) производится на основе эквивалентных преобразований , опирающихся на основные законы, тождества и правила, о которых речь шла выше.
Пример 9.
Показать, что f₁(x,y)=f₂(x,y), где , а .
Решение.
Умножим (логически) f₂(x, y) на - логическую единицу:

Воспользуемся тождествами , правилом дизъюнктивного поглощения . Окончательно получим:

11. Табличный метод минимизации.

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

Карты Карно имеют порядок склеивания 00 01 11 10, диаграммы Вейча - 00 01 10 11. В остальном эти методы идентичны. Рассмотрим порядок процесса минимизации с помощью карт Карно:

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

Для заполнения таблицы удобно пользоваться эталонными картами Карно:

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

12. Типы цифровых устройств, комбинационные и последовательностные цифровые устройства.

В общем случае на вход цифрового устройства поступает множество двоичных переменных X(x₁ … x_n), а с выхода снимается множество двоичных переменных Y(y₁ … y_k),. Устройство при этом осуществляет определенную логическую функцию между входными и выходными переменными.

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

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

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

Структура последовательностного и комбинационного устройства приведена на рис. 4.

Рис. 4. Структура комбинационного а и последовательностного б цифровых устройств

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

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

y₁ = y₁ (x₁ , x₂ , …, x_n),

y_k = y_k (x₁ , x₂ , …, x_n).

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

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

y_i ^t+1 = f_i (x₁ , x₂ , …, x_n, z₁ , z₂ , …, z_s)^t+1.

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

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

y_i ^t+1 = f_i (z₁ , z₂ , …, z_s)^t+1.

Это выражение называется функцией выхода автомата Мура.

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

Таблицы истинности соответствуют только статическим или установившимся режимам работы цифровых устройств. При изменении входных сигналов в комбинационной схеме из-за инерционности логических элементов в ней начинает протекать переходный процесс. Максимальная длительность переходного процесса определяется максимальным числом последовательно включенных ЛЭ. Входные сигналы x_m изменяются не мгновенно, а в течение некоторого времени ф_ф , т. е. сигналы имеют фронты конечной длительности. В течение этого времени входные сигналы имеют неопределенное значение. По этой причине, а также из-за задержек сигналов в ЛЭ выходные сигналы комбинационной схемы в течение переходного процесса могут принимать значения не соответствующие описывающим их функциям. Это явление называют переходными состояниями или “гонками”. Появление кратковременных ложных значений выходных сигналов комбинационной схемы может привести к неправильному срабатыванию других схем, подключенных к ее выходам.

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

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

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

13. Преобразователи кода.

Шифратор (кодер) — (англ. encoder) логическое устройство, выполняющее логическую функцию (операцию) — преобразование позиционного n-разрядного кода в m-разрядный двоичный, троичный или k-ичный код.

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

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

{\displaystyle \ n=2^{m},} где
{\displaystyle \ n} — число входов,
{\displaystyle \ m} — число выходных двоичных разрядов.

Троичный шифратор выполняет логическую функцию преобразования унарно n-ичного однозначного (одноединичного или однонулевого) кода в троичный. При подаче сигнала («1» в одноединичном коде или «0» в однонулевом коде) на один из n входов на выходе появляется троичный код номера активного входа.

Число входов и выходов в полном троичном шифраторе связано соотношением:

{\displaystyle \ n=3^{m}}, где
{\displaystyle \ n} — число входов,
{\displaystyle \ m} — число выходных троичных разрядов.

Число входов и выходов в полном k-ичном шифраторе связано соотношением:

{\displaystyle \ n=k^{m}}, где
{\displaystyle \ n} — число входов,
{\displaystyle \ m} — число выходных k-ичных разрядов,
{\displaystyle \ k} — основание системы счисления.

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

Дешифра́тор (декодер) (англ. decoder) в цифровой электронике — комбинационная схема, преобразующая n-разрядный двоичный, троичный или k‑ичный код в {\displaystyle \ k^{n}}‑ичный одноединичный код, где {\displaystyle \ k} — основаниесистемы счисления.

Одноединичный код — последовательность бит, содержащая только один активный бит/трит; остальные биты/триты последовательности неактивны.

Активный бит/трит — бит/трит, равный либо единице, либо нулю (зависит от реализации дешифратора).

Неактивные биты/триты — биты/триты:

· либо равные значению, инверсному (NOT) значению активного бита/трита;

· либо находящиеся в 3-м, высокоимпедансном состоянии.

Логический сигнал активен на том выходе, порядковый номер которого соответствует двоичному, троичному или k‑ичному коду.

Двоичный (k=2) дешифратор работает следующим образом:

· на вход дешифратора двоичное слово из n бит. Количество допустимых входных комбинаций из n бит равно {\displaystyle 2^{n}};

· на выходе у дешифратора формируется двоичное слово из числа бит, меньшего или равного {\displaystyle 2^{n}}. В выходном слове всегда имеется один бит, активный бит, равный 1 или 0, остальные биты неактивны. Активность 0 или 1 зависит от конкретной реализации дешифратора. Неактивные биты либо все имеют состояние инверсное к активному биту, либо переводятся в 3-е, высокоимпедансное состояние.

· Mультипле́ксор — устройство, имеющее несколько сигнальных входов, один или более управляющих входов и один выход. Мультиплексор позволяет передавать сигнал с одного из входов на выход; при этом выбор желаемого входа осуществляется подачей соответствующей комбинации управляющих сигналов.

· Аналоговые и цифровые^[1]^[2] мультиплексоры значительно различаются по принципу работы. Первые электрически соединяют выбранный вход с выходом (при этом сопротивление между ними невелико — порядка единиц/десятков ом). Вторые же не образуют прямого электрического соединения между выбранным входом и выходом, а лишь «копируют» на выход логический уровень ('0' или '1') с выбранного входа. Аналоговые мультиплексоры иногда называют ключами^[3] или коммутаторами.

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

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

· Сигналы на адресных входах определяют, какой конкретно информационный канал подключен к выходу. Если между числом информационных входов {\displaystyle n\!\,} и числом адресных входов {\displaystyle m\!\,} действует соотношение {\displaystyle n=2^{m}\!\,}, то такой мультиплексор называют полным. Если {\displaystyle n<2^{m}\!\,}, то мультиплексор называют неполным.

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

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

14. Дешифраторы, двоичные дешифраторы.

Линейный или одноступенчатый дешифратор. Дешифратор – это комбинационное устройство, предназначенное для преобразования параллельного двоичного кода в унитарный, т.е. позиционный код. Обычно указанный в схеме номер вывода дешифратора соответствует десятичному эквиваленту двоичного кода, подаваемого на вход дешифратора в качестве входных переменных, вернее сказать, что при подаче на вход устройства параллельного двоичного кода на выходе дешифратора появится сигнал на том выходе, номер которого соответствует десятичному эквиваленту двоичного кода. Отсюда следует то, что в любой момент времени выходной сигнал будет иметь место только на одном выходе дешифратора. Этот сигнал, в зависимости от типа дешифратора, может иметь как уровень логической единицы (при этом на всех остальных выходах – уровень логического 0), так и уровень логического 0 (при этом на всех остальных выходах – уровень логической единицы).

Рассмотрим пример синтеза дешифратора 3 8, следовательно, количество разрядов двоичного числа – 3, количество выходов – 8.

Таблица состояний дешифратора

Х₃	Х₂	Х₁	Z₀	Z₁	Z₂	Z₃	Z₄	Z₅	Z₆	Z₇

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

Рис. 2.1

Для реализации полного дешифратора на m входов (переменных) потребуются n = 2^m элементов конъюнкции (количество входов каждого элемента «И» равно m) и m элементов отрицания.

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

^а ^б

Рис. 2.2

15. Мультиплексоры и демультиплексоры.

Основные понятия

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

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

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

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

16. Цифровые компараторы.

Очень важную роль при аналого-цифровом преобразовании играют компараторы. Компаратором называют устройство, предназначенное для сравнения изменяющегося аналогового входного сигнала с опорным напряжением. При этом в зависимости от того, больше входной сигнал опорного или меньше (на доли милливольт), на выходе компаратора должно установиться напряжение «логический нуль» (лог. 0) или «логическая единица» (лог. 1). Так как выходной сигнал компаратора подается обычно на логические схемы, его выходное напряжение согласуется с цифровыми логическими схемами [6].

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

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

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

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

Чтобы выходной сигнал компаратора изменился на конечную величину |U1вых - U0вых| при бесконечно малом изменении входного сигнала, компаратор должен иметь бесконечно большой коэффициент усиления (эпюра 1 на рис. 2) при полном отсутствии шумов во входном сигнале. Такую характеристику можно имитировать двумя способами - или просто использовать усилитель с очень большим коэффициентом усиления, или ввести положительную обратную связь.

Рассмотрим первый путь. Как бы велико усиление не было, при Uвхблизком к нулю характеристика будет иметь вид рис. 1а. Это приведет к двум неприятным последствиям. Прежде всего, при очень медленном изменении Uвх выходной сигнал также будет изменяться замедленно, что плохо отразится на работе последующих логических схем (эпюра 2 на рис. 2). Еще хуже то, что при таком медленном изменении Uвх около нуля выход компаратора может многократно с большой частотой менять свое состояние под действием помех (так называемый "дребезг", эпюра 3). Это приведет к ложным срабатываниям в логических элементах и к огромным динамическим потерям в силовых ключах. Для устранения этого явления обычно вводят положительную обратную связь, которая обеспечивает переходной характеристике компаратора гистерезис (рис. 1б). Наличие гистерезиса хотя и вызывает некоторую задержку в переключении компаратора (эпюра 4 на рис. 2), но существенно уменьшает или даже устраняет дребезг Uвых.

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

Пусть R1 = R2. Если Uвх - Uоп> 0, то диод VD2 открыт и выходное напряжение схемы небольшое отрицательное, равное падению напряжения на открытом диоде. При Uвх - Uоп< 0 на стабилитроне установится напряжение, равное его напряжению стабилизации Uст. Это напряжение должно соответствовать единичному логическому уровню цифровых интегральных микросхем (ИМС), входы которых подключены к выходу компаратора. Таким образом, выход ОУ принимает два состояния, причем в обоих усилитель работает в линейном режиме. Многие типы ОУ не допускают сколько-нибудь существенное входное дифференциальное напряжение. Включение по схеме на рис. 3 обеспечивает работу ОУ в режиме компаратора практически с нулевыми дифференциальными и синфазными входными напряжениями. Недостатком данной схемы является относительно низкое быстродействие, обусловленное необходимостью частотной коррекции, так как ОУ работает в линейном режиме со 100%-ной обратной связью. Используя для построения компаратора обычные ОУ, трудно получить время переключения менее 1 мкс. [4]

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

17. Сумматоры двоичных кодов чисел.

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

Сумматоры классифицируют по различным признакам.

В зависимости от системы счисления различают:

· двоичные;

· двоично-десятичные (в общем случае двоично-кодированные);

· десятичные;

· прочие (например, амплитудные).

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

· одноразрядные,

· многоразрядные.

По числу входов и выходов одноразрядных двоичных сумматоров:

· четвертьсумматоры (элементы "сумма по модулю 2"; элементы "исключающее ИЛИ"), характеризующиеся наличием двух входов, на которые подаются два одноразрядных числа, и одним выходом, на котором реализуется их арифметическая сумма;

· полусумматоры, характеризующиеся наличием двух входов, на которые подаются одноименные разряды двух чисел, и двух выходов: на одном реализуется арифметическая сумма в данном разряде, а на другом перенос в следующий (более старший разряд);

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

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

· последовательные, в которых обработка чисел ведется поочередно, разряд за разрядом на одном и том же оборудовании;

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

Параллельный сумматор в простейшем случае представляет собой n одноразрядных сумматоров, последовательно (от младших разрядов к старшим) соединенных цепями переноса. Однако такая схема сумматора характеризуется сравнительно невысоким быстродействием, так как формирование сигналов суммы и переноса в каждом i-ом разряде производится лишь после того, как поступит сигнал переноса с (i-1)-го разряда.Таким образом, быстродействие сумматора определяется временем распространения сигнала по цепи переноса. Уменьшение этого времени основная задача при построении параллельных сумматоров.

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

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

· с последовательным переносом;

· с параллельным переносом;

· с групповой структурой;

· со специальной организацией цепей переноса.

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

· сумматоры со сквозным переносом, в которых между входом и выходом переноса одноразрядного сумматора оказывается наименьшее число логических уровней [1];

· сумматоры с двухпроводной передачей сигналов переноса [1, 2];

· сумматоры с условным переносом (вариант сумматора с групповой структурой, позволяющий уменьшить время суммирования в 2 раза при увеличении оборудования в 1,5 раза) [3];

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

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

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

· комбинационный, выполняющий микрооперацию "S = A плюс B", в котором результат выдается по мере его образования (это комбинационная схема в общепринятом смысле слова);

· сумматор с сохранением результата "S = A плюс B";

· накапливающий, выполняющий микрооперацию "S = S плюс B".

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

Важнейшими параметрами сумматоров являются:

· разрядность;

· статические параметры: Uвх, Uвх, Iвх и так далее, то есть обычные параметры интегральных схем;

· динамические параметры. Сумматоры характеризуются четырьмя задержками распространения:

· от подачи входного переноса до установления всех выходов суммы при постоянном уровне на всех входах слагаемых;

· от одновременной подачи всех слагаемых до установления всех выходов суммы при постоянном уровне на входе переноса;

· от подачи входного переноса до установления выходного переноса при постоянном уровне на входах слагаемых;

· от подачи всех слагаемых до установления выходного переноса при постоянном уровне на входах слагаемых.

18. Триггеры, типы триггеров.

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

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

Рисунок 1. Схема простейшего триггера, построенного на инверторах

В схеме любого триггера может быть только два состояния — на выходе Q присутствует логическая единица и на выходе Q присутствует логический ноль. Если логическая единица присутствует на выходе Q, то на инверсном выходе триггера будет присутствовать логический ноль, который после очередного инвертирования подтверждает уровень логической единицы на выходе Q. И наоборот, если на выходе триггера Q присутствует логический ноль, то на инверсном выходе будет присутствовать логическая единица.

Описанная ситуация на выводах триггера будет сохраняться до тех пор пока включено питание. Но вот вопрос — а как записывать в простейший триггер необходимую нам информацию? Для этого в схеме потребуются входы записи нуля и записи единицы.

RS-триггеры

RS-триггер получил название по названию своих входов. Вход S (Set — установить англ.) позволяет устанавливать выход Q в единичное состояние. (Устанавливать означает записывать логическую единицу). Вход R (Reset — сбросить англ.) позволяет сбрасывать выход Q (Quit — выход англ.) в нулевое состояние.

Для реализации RS-триггера воспользуемся логическими элементами "2И-НЕ". Его принципиальная схема, реализованная на логических элементах "2И-НЕ", приведена на рисунке 2.

Рисунок 2. Схема RS-триггера на логических элементах "2И-НЕ". Входы R и S инверсные (активный уровень'0')

Рассмотрим работу изображенной на рисунке 2 схемы триггера подробнее. Пусть на входы R и S подаются единичные потенциалы. Если на выходе верхнего логического элемента "2И-НЕ" Q присутствует логический ноль, то на выходе нижнего логического элемента "2И-НЕ" появится логическая единица. Эта единица подтвердит логический ноль на выходе триггера Q. Если на выходе верхнего логического элемента "2И-НЕ" Q первоначально присутствует логическая единица, то на выходе нижнего логического элемента "2И-НЕ" появится логический ноль. Этот ноль подтвердит логическую единицу на выходе Q. То есть, при единичных уровнях на входах R и S, схема RS-триггера работает точно так же, как и схема триггера на инверторах.

Подадим на вход S триггера нулевой потенциал. Согласно таблице истинности логического элемента "2И-НЕ" на выходе Q появится единичный потенциал. Это приведёт к появлению на инверсном выходе триггера нулевого потенциала. Теперь, даже если снять нулевой потенциал с входа S, на выходе триггера останется единичный потенциал. То есть мы записали в триггер логическую единицу.

Точно так же можно записать в триггер и логический ноль. Для этого следует воспользоваться входом R. Так как активный уровень на входах триггера оказался нулевым, то эти входы — инверсные. Составим таблицу истинности RS-триггера. Входы R и S в этой таблице будем использовать прямые, то есть запись нуля, и запись единицы будут осуществляться единичными потенциалами (таблица 1).

Таблица 1. Таблица истинности RS-триггера.

R	S	Q(t)	Q(t+1)	Пояснения
				Режим хранения информации (триггером) R=S=0

				Режим установки триггера в единичное состояние S=1

				Режим записи нуля в триггер R=1

			*	R=S=1 запрещенная комбинация
			*

RS-триггер можно построить и на логических элементах "2ИЛИ-НЕ". Схема RS-триггера, построенного на логических элементах "2ИЛИ-НЕ" приведена на рисунке 3. Единственное отличие в работе этой схемы триггера будет заключаться в том, что его сброс и установка будет производиться единичными логическими уровнями. Эти особенности реализации схемы триггера связаны с принципами работы инверсной логики, которые рассматривались ранее.

Рисунок 3. Схема простейшего RS триггера на логических элементах "2ИЛИ-НЕ". Входы R и S прямые (активный уровень '1')

Так как RS-триггер при построении его на логических элементах "2И-НЕ" и "2ИЛИ-НЕ" работает одинаково, то его условно-графическое изображение на принципиальных схемах тоже одинаково. Условно-графическое изображение RS-триггера на принципиальных схемах приведено на рисунке 4.

Рисунок 4. Условно-графическое обозначение RS-триггера

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

Синхронные RS-триггеры

Схема RS-триггера позволяет запоминать состояние логической схемы, но так как в начальный момент времени может возникать переходный процесс (в цифровых схемах этот процесс называется "опасные гонки"), то запоминать состояния логической схемы в триггерах нужно только в определённые моменты времени, когда все переходные процессы закончены.

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

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

Для этого нам потребуется схема, пропускающая входные сигналы только при наличии синхронизирующего сигнала. Такую схему мы уже использовали при построении схем мультиплексоров и демультиплексоров. Это логический элемент "И". Принципиальная схема синхронного RS-триггера приведена на рисунке 5.

Рисунок 5. Схема синхронного RS-триггера, построенного на элементах "И"

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

Таблица 2. Таблица истинности синхронного RS-триггера.

С	R	S	Q(t)	Q(t+1)	Пояснения
	x	x			Режим хранения информации
	x	x
					Режим хранения информации

					Режим установки единицы S=1

					Режим записи нуля R=1

				*	R=S=1 запрещенная комбинация
				*

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

Рисунок 6. Условно-графическое обозначение синхронного RS-триггера

D-триггеры

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

Рисунок 7. Принципиальная схема D триггера (защелки)

Такой триггер получил название D триггер. Название происходит от английского слова delay — задержка. Конкретное значение задержки определяется частотой следования импульсов синхронизации. Условно-графическое обозначение D триггера на принципиальных схемах приведено на рисунке 8.

Рисунок 8. Условно-графическое обозначение D триггера (защелки)

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

Таблица 3. Таблица истинности D триггера

С	D	Q(t)	Q(t+1)	Пояснения
	x			Режим хранения информации
	x
		x		Режим записи информации
		x

Нужно отметить, что отдельный инвертор при реализации триггера на ТТЛ элементах не нужен, так как самый распространённый элемент ТТЛ логики - это “2И-НЕ”. Принципиальная схема D триггера на элементах 2И-НЕ” приведена на рисунке 9.

Рисунок 9. Схема D триггера, реализованная на ТТЛ элементах

T-триггер

T-триггер — это счетный триггер. У данного триггера имеется только один вход. Принцип работы T-триггера заключается в следующем. После поступления на вход T импульса, состояние триггера меняется на прямо противоположное. Счётным он называется потому, что T триггер как бы подсчитывает количество импульсов, поступивших на его вход. Жаль только, что считать этот триггер умеет только до одного. При поступлении второго импульса T-триггер снова сбрасывается в исходное состояние.

T-триггеры строятся только на базе двухступенчатых триггеров, подобных рассмотренному ранее D триггеру. Использование двух триггеров позволяет избежать неопределенного состояния схемы при разрешающем потенциале на входе синхронизации "C", так как счетные триггеры строятся при помощи схем с обратной связью

T триггер можно синтезировать из любого двухступенчатого триггера. Рассмотрим пример синтеза T триггера из динамического D триггера. Для того чтобы превратить D триггер в счётный, необходимо ввести цепь обратной связи с инверсного выхода этого триггера на вход, как показано на рисунке 1.

Рисунок 1. Схема T триггера, построенная на основе D триггера

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

Рисунок 2. Временные диаграммы T триггера

Т-триггеры используются при построении схем различных счётчиков, поэтому в составе БИС различного назначения обычно есть готовые модули этих триггеров. Условно-графическое обозначение T триггера приведено на рисунке 3.

Рисунок 3. Условно-графическое обозначение T триггера

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

Рисунок 4. Схема синхронного T триггера, построенная на основе D триггера

Подобная схема счетного триггера может быть реализована и на JK триггере. Временная диаграмма синхронного T триггера приведена на рисунке 5, а его условно-графическое обозначение — на рисунке 6.

Рисунок 5. Временные диаграммы синхронного T триггера

Рисунок 6. Условно-графическое обозначение синхронного T триггера

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

Jk триггер

Прежде чем начать изучение jk триггера, вспомним принципы работы RS-триггера. Напомню, что в этом триггере есть запрещённые комбинации входных сигналов. Одновременная подача единичных сигналов на входы R и S запрещены. Очень хотелось бы избавиться от этой неприятной ситуации.

Таблица истинности jk триггера практически совпадает с таблицей истинности синхронного RS-триггера. Для того чтобы исключить запрещённое состояние, его схема изменена таким образом, что при подаче двух единиц jk триггер превращается в счётный триггер. Это означает, что при подаче на тактовый вход C импульсов этот триггер изменяет своё состояние на противоположное. Таблица истинности jk триггера приведена в таблице 1.

Таблица 1. Таблица истинности jk триггера.

С	K	J	Q(t)	Q(t+1)	Пояснения
	x	x			Режим хранения информации
	x	x
					Режим хранения информации

					Режим установки единицы J=1

					Режим записи нуля K=1

					K=J=1 счетный режим триггера

Один из вариантов внутренней схемы JK-триггера приведен на рисунке 1. Эта схема удобна для изучения принципов работы данного триггера в счетном режиме.

Рисунок 1. Внутренняя схема jk триггера

Для реализации счетного режима в схеме введена перекрестная обратная связь с выходов второго триггера на входы R и S первого триггера. Благодаря обратной связи на входах R и S первого триггера никогда не может возникнуть запрещенная комбинация, а то, что она перекрестная, вводит новый режим работы — счетный. При подаче на входы j и k логической единицы одновременно JK-триггер переходит в счетный режим, подобно T триггеру.

Приводить временные диаграммы работы JK-триггера не имеет смысла, так как они совпадают с приведёнными ранее временными диаграммами RS- и T-триггера. Условно-графическое обозначение JK-триггера приведено на рисунке 2.

Рисунок 2. Условно-графическое обозначение jk триггера

На этом рисунке приведено обозначение типовой цифровой микросхемы К1554ТВ9, выполненной по ТТЛ технологии. В промышленно выпускающихся микросхемах обычно кроме входов j и k реализуются входы RS-триггера, которые позволяют устанавливать jk триггер в заранее определённое исходное состояние.

В названиях отечественных микросхем для обозначения jk триггера присутствуют буквы ТВ. Например, микросхема К1554ТВ9 содержит в одном корпусе два jk триггера. В качестве примеров иностранных микросхем, содержащих jk триггеры можно назвать такие микросхемы, как 74HCT73 или 74ACT109.

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

Рисунок 3. Схема обнаружения короткого импульса

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

Теперь рассмотрим пример построения на jk триггере ждущего мультивибратора. Один из вариантов подобной схемы приведен на рисунке 4.

Рисунок 4. Схема ждущего мультивибратора, собранного на jk триггере

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

В качестве последнего примера применения универсального jk триггера, рассмотрим схему счетного T-триггера. Схема счетного триггера приведена на рисунке 5.

Рисунок 5. Схема счетного триггера, построенного на jk триггере

В схеме, приведенной на рисунке 5, для реализации счетного режима работы триггера на входы J и K подаются уровни логической единицы. Если эти входы вывести в качестве отдельного входа, то они образуют отдельный вход разрешения счета T

19. Регистры последовательного и параллельного типа.

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

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

Основой построения регистров являются синхронные RS-триггеры или, предпочтительнее, В-триггеры. Принцип построения простейшего параллельного т-разрядного регистра показан на рис. 208.

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

Последовательные регистры, помимо хранения информации, способны преобразовывать последовательный код в параллельный и наоборот. При построении последовательных регистров триггеры соединяются последовательно путем подключения выхода Q i-го триггера ко входу D i-го триггера, как это показано на рис. 209.

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

При действии каждого очередного тактового импульса код, содержащийся в регистре, сдвигается на один разряд. Для схемы, приведенной на рис.209, сдвиг кода происходит вправо (в сторону младших разрядов). Действительно, сигнал выхода Q i+1-го триггера действует на вход D i-го триггера, а сигнал выхода Q i-го триггера действует на вход D i-1-го триггера. При действии синхросигнала i-й триггер примет состояние i+1-го, а i-1-й - состояние i-го триггера, т.е., произойдет сдвиг кода вправо на один разряд.

Параллельный двоичный код одновременно снимается с выходов Q триггеров. Для сдвига кода влево необходимо, чтобы сигнал с выхода Q i-1-го триггера подавался на вход Q i-го (старшего) триггера.

Реверсивные регистры должны содержать логические схемы управления, обеспечивающие прохождение сигнала с выхода Q i-го триггера на вход D i-1-го триггера при сдвиге кода вправо и прохождение этого же сигнала на вход D i+1-го при реализации сдвига кода влево. Схема построения реверсивного регистра приведена на рис. 210.

Направление сдвига кода определяется подачей требуемых сигналов управления на соответствующие входы. Так, в схеме, показанной на рис. 210, при подаче на вход S0 напряжения логической единицы сдвиг кода будет происходить влево (в сторону старших разрядов), поскольку логическая схема управления 2И - 2И - 2ИЛИ будет разрешать прохождение сигналов с выходов Q i-го триггера на вход D i-го триггера, и наоборот, при подаче на вход S1 напряжения логической единицы будет разрешено прохождение сигнала с выхода Q i-го триггера на вход D i1-го триггера - будет реализовываться сдвиг кода вправо (в сторону младших разрядов).

Условно-графическое обозначение параллельного, сдвигового и реверсивного регистров приведено на рис. 211.

20. Кольцевой счетчик.

Кольцевые счетчики.. Кольцевые счетчики - это замкнутые "в кольцо" регистры сдвига, состояния триггеров в которых изменяются под воздействием входных сдвигающих импульсов. В простейшем случае по кольцу циркулирует одна кодовая единица, так что коэффициент пересчета счетчика равен числу входящих в него триггеров. Схема подобного кольцевого счетчика, построенного на рассмотренном в главе Регистры регистре К155ИР1, показана на рис. 5, а.

Рисунок 5. Схемы кольцевых счетчиков.

Выход Q4 последнего триггера соединен со входом регистра I, благодаря чему и образуется кольцевое соединение триггеров. Начальная установка триггеров счетчика производится при V=l подачей импульса на вход C1. Поскольку на вход D1 подан потенциал 1, а на входы D2-D4-потенциал 0, то при этом первый триггер установится в 1, а остальные в 0. Счетный режим в данном случае реализуется при V=0 и подаче входных импульсов на вход С2. В этом случае триггеры последовательно принимают состояния 1000, 0100, 0010, 0001 и далее цикл снова повторяется. Таким образом, после прихода четырех входных импульсов счетчик возвращается в исходное состояние. Это и означает, что коэффициент пересчета счетчика равен четырем. Для увеличения коэффициента пересчета можно увеличивать число разрядов в кольце или соединять счетчики последовательно. В частности, счетчик на 10 может быть получен путем последовательного соединения одного счетного триггера и кольцевого счетчика на 5. Неприятной особенностью подобных кольцевых счетчиков является то, что сбои, вызванные лишними или не достающими кодовыми единицами в кольце, несамоустранимы. Действительно, если, например, под воздействием импульса помехи триггер, находившийся в состоянии "1", перейдет в "0", то все триггеры в кольце окажутся в нулевом состоянии и счетные импульсы не будут изменять состояния счетчика. Подобные сбои могут быть устранены только повторной начальной установкой триггеров счетчика. Одним из методов борьбы с подобными сбоями является введение в счетчик логической цепи, разрешающей запись единицы в первый триггер только тогда, когда все остальные триггеры находятся в нуле (рис. 5, б). Все то время, пока хотя бы один триггер регистра находится в единице, на выходе цепи ИЛИ-НЕ будет существовать потенциал "нуль". Когда под воздействием счетных импульсов все триггеры установятся в нуль, на выходе этой цепи появится единица. Очередной тактовый импульс установит в единицу первый триггер, и таким образом снова начнется цикл продвижения единицы по разрядам регистра. Подобный кольцевой счетчик имеет коэффициент пересчета на единицу больше числа разрядов используемого регистра. В частности, в счетчике рис. 5, 6 коэффициент пересчета равен пяти. С выхода ячейки ИЛИ-НЕ в данном случае можно снимать сигнал, как бы соответствующий пятому триггеру в кольце (Q5). Заметим, что если в схеме рис. 5,6 использовать вместо ячейки ИЛИ-НЕ ячейку И-НЕ, то счетчик так-же будет иметь коэффициент пересчета пять, но по кольцу будет циркулировать не единица, а нуль.

21. Сдвиговые регистры.

Сдвиговый регистр с обратной связью по переносу, или FCSR (feedbackwithcarryshiftregister), похож на LFSR. В обоих есть сдвиговый регистр и функция обратной связи, разница в том, что в FCSR есть также регистр переноса (см. Рис. 17-3). Вместо выполнения XOR над всеми битами отводной последовательности эти биты складываются друг с другом и с содержимым регистра переноса. Результат mod 2 и становится новым битом. Результат, деленный на 2, становится новым содержимым регистра переноса.

Рис. 17-3. Сдвиговый регистр с обратной связью по переносу.

На Рис. 17-4 приведен пример 3-битового FCSR с ответвлениями в первой и второй позициях. Пусть его начальное значение 001, а начальное содержимое регистра переноса равно 0. Выходом будет является крайний правый бит сдвигового регистра.

Сдвиговый регистр	Регистр переноса
0 0 1
1 0 0
0 1 0
1 0 1
1 1 0
1 1 1
0 1 1
1 0 1
0 1 0
0 0 1
0 0 0
1 0 0

Рис. 17-4. 3-битовый FCSR.

Заметим, что конечное внутреннее состояние (включая содержимое регистра переноса) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом, равным 10.

Стоит упомянуть и еще о нескольких моментах. Во первых, регистр переноса является не битом, а числом. Размер регистра переноса должен быть не меньше log2t, где t - это число ответвлений. В предыдущем примере только три ответвления, поэтому регистр переноса однобитовый. Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения 0, 1, 2 или 3.

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

⇐ Назад