Главная стр 1
скачать
10. Статистические параметры логических элементов.

К статистическим параметрам, характеризующим логические и схемотехничес­кие возможности логическим элементам (ЛЭ) микросхем и больших интегральных схем (БИС), относятся:

— реализуемая логическая функция;

— нагрузочная способность n, характеризующая возможность под­ключения определенного числа идентичных ЛЭ;

— коэффициент объединения по входу m (mи — для реализации логической функции И; mили — для реализации логической функ­ции ИЛИ);

— средняя задержка передачи сигнала tср (полу сумма времени задержек передачи сигналов 1 и 0 со входа ЛЭ на его выход);

—предельная рабочая частота fр (частота переключения тригге­ра, составленного из рассматриваемых ЛЭ);

— помехоустойчивость;

— потребляемая мощность.



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

Нагрузочная способность ЛЭ n определяет число входов иден­тичных элементов, которое может быть подключено к выходу каж­дого из них. При этом обеспечивается неискаженная передача двоичных символов 0 и 1 в цифровом устройстве по цепи из произвольного числа последовательно включенных элементов при наи­худших сочетаниях дестабилизирующих факторов. Дестабилизиру­ющими факторами могут быть: изменение питающих напряжений, разброс параметров компонентов, изменение температуры и т. п.

Часто нагрузочная способность n называется коэффициентом разветвления элементов по выходу и выражается целым положи­тельным числом (n =4, 5, 7, 10 и т. д.). Чем выше нагрузочная способность ЛЭ, тем шире их логические возможности и тем меньше затраты при построении цифрового устройства. Однако увеличение параметра n возможно до определенных пределов, поскольку при этом ухудшаются другие параметры ЛЭ: снижается быстродействие, ухудшается помехоустойчивость и увеличивается потребляемая мощность. По этой причине в состав одной серии интегральной микросхемы часто входят ЛЭ с различной нагрузочной способностью: ос­новные ЛЭ с n =4...10 и буферные элементы — так называемые усилители мощности с n =20...50. Это позволяет более гибко про­ектировать цифровые устройства, достигая оптимальных показате­лей по потребляемой мощности и числу ЛЭ.

В зависимости от частного диапазона работы логических МДП-микросхем их нагрузочная способность может изменяться в широ­ких пределах (n = 10 ... 100).

Коэффициент объединения по входу m характеризует макси­мальное число логических входов функционального элемента. С увеличением параметра m расширяются логические возможности микросхемы за счет выполнения функций с большим числом аргу­ментов на одном типовом элементе И—НЕ, ИЛИ—НЕ и т. п. Од­нако при увеличении числа входов, как правило, ухудшаются дру­гие параметры функционального элемента, такие как быстродей­ствие, помехоустойчивость и нагрузочная способность.

С точки зрения возможности увеличения коэффициента объеди­нения по входу И или по входу ИЛИ логические схемы существен­но отличаются друг от друга. В существующих сериях интегральных микросхем основные логические элементы выполняются, как правило, с небольшим чи­слом входов (mи =2...6, mили=2... 4). Увеличение числа входов m обеспечивается за счет введения в серию ЛЭ специального логи­ческого расширителя.



Помехоустойчивость. Базовый элемент интегральной микросхе­мы в статическом режиме может находиться в одном из двух ус­тойчивых состояний (0 или 1). По этой причине различают стати­ческую помехоустойчивость ЛЭ по уровню 0 Uпо и по уровню 1 Uп1.

Определение 10.1: Статическая помехоустойчивость базовых элементов ИМС определяется значением напряжения, которое может быть подано на вход ИМС относительно уровня 0 или 1, не вызывая ее ложно­го срабатывания (например, переход из состояния 1 в состояние 0 или наоборот).

ИМС, принадлежащие од­ной и той же серии, спроектированы взаимно согласованными. То есть уровни выходных сигналов одного логического элемента (даже при их изменении в допустимых пределах) могут использоваться в качестве уровней входного сигнала следующего элемента без каких-либо согласующих устройств.



Потребляемая мощность. При работе в реальном устройстве каждый ЛЭ может находиться в следующих состояниях: в состоя­нии

— выключено;

— в стадии включения;

— в состоянии включено;

— в стадии выключения.

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

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

Для ИМС на биполярных транзисторах, предполагая, что схема примерно одинаковое время находится в состояниях 0 и 1, среднюю мощность рассчи­тывают по формуле:



Рср=(Р01)/2,

где P1 — мощность, потребляемая микросхемой в состоянии вклю­чено; Р0—мощность, потребляемая микросхемой в состоянии вы­ключено.

Для ИМС на МДП-транзисторах мощность, потребляемая ими в процес­се переключения, в десятки раз и более превышает мощность, потребляемую в статических состояниях, поэтому для них Рср оценивают при максималь­но допустимой частоте переключения.

По потребляемой мощности ИМС можно разделить на относительно мощные (Рср от сотен до единиц милливатт), маломощные (от единиц мил­ливатт до микроватта) и еще меньшей мощности, называемые «нановаттными» (Рср <1 мкВт).



11. Быстродействие цифровых устройств.

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

Быстродействие является одним из основных параметров устройства, характеризующим её производительность.



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

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

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

19. Базовые логические элементы.

Логические элементы — это наиболее простые цифровые микросхемы. Именно в этой простоте и состоит их отличие от других микросхем.

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

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

Инверторы.


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




Рис. 10.1.  Условные обозначения инверторов: зарубежные (слева) и отечественные (справа).


Таблица истинности инвертора

Вход

Выход

0

1

1

0

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

Элементы И, И-НЕ, ИЛИ, ИЛИ-НЕ.


Самые распространенные логические функции — это И, И-НЕ, ИЛИ и ИЛИ-НЕ. Присутствие слова НЕ в названии элемента обозначает только одно — встроенную инверсию сигнала. Объединяет все эти элементы то, что у них есть несколько равноправных входов (от 2 до 12) и один выход, сигнал на котором определяется комбинацией входных сигналов.

Определение 10.2: Элемент И — логический элемент, который формирует на выходе единицу тогда и только тогда, если на всех его входах (и на первом, и на втором, и на третьем и т.д.) присутствуют единицы. Если речь идет об элементе И-НЕ, то на выходе формируется нуль, когда на всех входах — единицы.

Определение 10.3: Элемент ИЛИ – логический элемент, который формирует на выходе единицу тогда и только тогда, когда хотя бы на одном из его входах присутствует единица. Если речь идёт об элементе ИЛИ-НЕ, то на выходе формируется единица только в том случае, когда на все входах присутствуют все нули, в остельных случаях на выходе формируется ноль.


Вход 1

Вход 2

Выход И

Выход И-НЕ

Выход ИЛИ

Выход ИЛИ-НЕ

0

0

0

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

1

1

0

1

0



20. Синтез комбинационных ЦУ.

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

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



Этапы синтеза.

  1. Входы и выходы получают двоичную кодировку.

  2. Выбираются элементный базис, а также триггерные элементы.

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

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

Пример комбинационной схемы.



21. Понятие конечного автомата, автомата с памятью: синхронный и асинхронный автоматы.

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


На такие устройства в последовательные дискретные моменты времени 1,2, …, t, t+1,… поступают входные сигналы x(1),x(2), …, x(t),x(t+1),… и в ответ на них автомат A вырабатывает выходные сигналы y(1) y(2), …, y(t), y(t+1),…. Конечные автоматы характеризуются двумя особенностями.

Отсутствие предвосхищения: выходной сигнал y(t), выдаваемый автоматом в момент t, зависит лишь от полученных к этому времени входов x(1),x(2), …, x(t), т.е. автомат не может предвосхитить будущие входы и заранее на них отреагировать. Таким образом, имеется некоторая функция выходов (x(1),x(2), …, x(t))= y(t), определяющая очередной выход по предшествующему входу.

Конечная память: в каждый момент t информация в автомате о полученном к этому моменту входе x(1),x(2), …, x(t) конечна. Это свойство удобно интерпретировать следующим образом: автомат имеет конечное множество состояний Q и в каждый момент находится в одном из этих состояний. При получении очередного входа состояние может измениться. Таким образом, состояние q Q, в котором находится автомат после получения входной последовательности x(1),x(2), …, x(t), и представляет информацию об этой последовательности, используемую в дальнейшей работе автомата при определении следующего состояния и выхода.

Определение 22.2: Асинхронный автомат - конечный автомат, в котором выходные сигналы считываются в любое время, а переход в новое состояние определяется лишь временем срабатывания всех логических элементов, входящих в логический преобразователь.
Определение 22.3: Синхронный автомат - конечный автомат, в котором:
- генератор тактовых импульсов воздействует на автомат;
- выходные сигналы считываются только во время выдачи тактовых импульсов, когда под воздействием входных и промежуточных сигналов автомат уже перешел в новое состояние.
22. Функции переходов и выходов синхронного автомата Мили.
Определение 22.1: В случае синхронного автомата входные сигналы действуют в строго определённые моменты времени при Т=const, определяемые генератором синхронизирующих импульсов, в которые возможен переход автомата из одного состояния в другое.

Поведение автомата Мили описывается с помощью следующих уравнений:

zt+1 = (xt,zt);

yt = (xt,zt);

здесь функция перехода определяет следующее внутреннее состояние автомата (состояние перехода) zt+1, а функция выхода - формируемый выходной набор yt. Характерным для автомата Мили является то, что выходной набор yt зависит как от входного набора xt, так и от внутреннего состояния zt. Индекс t – временной показатель, определяет поведение автомата в момент времени t.



23. Функции переходов и выходов синхронного автомата Мура.

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

zt+1 = (xt, zt);

yt = (zt).



- функция перехода; - функция выхода.

24. Особенности таблиц переходов и выходов асинхронного автомата.

Определение 24.1: Более сложное определение асинхронного автомата. Асинхронным автоматом будем называть шестерку m=(V,v0,X,e,Y,T), где:

  • Z - множество состояний;

  • z0Z – начальное состояние;

  • X - входной алфавит стимулов;

  • e X - пустой символ, X`=X{e} – расширенный алфавит символов;

  • Y – выходной алфавит; будем считать, что входной и выходной алфавиты не пересекаются X`Y=;

  • T = R`SI - множество переходов, где:

    • R` V х X` х V - принимающие переходы,

    • S V х Y х V - посылающие переходы,

    • I V х V - пустые переходы.

Принимающие переходы можно разделить на два вида: R = R` V х X х V – принимающие переходы по непустым символам или x-переходы, и E = R` V х {e} х V – принимающие переходы по пустым символам или e-переходы.

Для определения особенностей таблицы переходов и выходов рассмотрим более простой случай. Пусть дан асинхронный автомат, в котором Х={x0(t), x1(t)……, xn(t)} – входной алфавит, Y={y0(t),y1(t),…… ,yn(t)} – выходной алфавит, Z={z0(t), z1(t), ……,zn(t)} – множество состояний автомата, f(zi(t), xk(t)) – функция перехода и g(zi(t), xk(t)) – функция выхода.

В асинхронном автомате все переходы осуществляются между устойчивыми состояниями, что создает дополнительные сложности при построении таблицы переходов. Если состояние zi(t) является устойчивым, то в клетке таблицы переходов, определяемой строкой, отмеченной состоянием zi(t), и столбцом, отмеченным входным сигналом xk, должен быть записан символ состояния zi(t), поскольку f(zi(t), xk(t))=zi(t). Таким образом, для устойчивых состояний в таблице переходов асинхронного автомата необходимы дополнительные средства, указывающие, в какое состояние должен перейти автомат при изменении входного сигнала. Это затруднение решается следующим образом. Процесс изменения состояния автомата разбивается на два этапа, полагая, что вначале происходит изменение входных сигналов, а состояние автомата остается неизменным, а затем уже происходит изменение состояния при новых значениях входных сигналов. Первому этапу этого процесса соответствует перемещение по строке таблицы переходов, отмеченной старым состоянием, в столбец, отмеченный новыми значениями входных сигналов. Итак, первый этап однозначным образом определяет новую клетку таблицы, которая соответствует переходному состоянию автомата. Такие состояния будем называть транзитивными. B этой клетке записывается символ того состояния, в которое должен перейти автомат. При этом второму этапу изменения состояния соответствует перемещение по столбцу, определяемому новыми входными сигналами, в строку, отмеченную тем состоянием, в которое автомат должен перейти. Для того чтобы не путать устойчивые состояния с указателями перехода, используемыми на втором этапе, условимся заключать символы, соответствующие устойчивым состояниям, в круглые скобки. Примером таблицы переходов и выходов асинхронного автомата является табл. 1. Эта таблица построена по графу, приведенному на рис. 2(б) (вопрос 25).

 

   Рассмотрим, как выполняются переходы в табл. 24.1 на примере. Допустим, что автомат находится в состоянии 3 под действием входных сигналов 00. Согласно таблице переходов, это состояние является устойчивым. Если теперь значение входных сигналов изменится на 10, то для того, чтобы найти в какое состояние перейдет автомат, необходимо выполнять перемещение по третьей строке в столбец, отмеченный сигналами 10. В определенной таким образом клетке таблицы находится номер состояния, в которое переходит автомат - это состояние 5*. Перемещаясь по вертикали в столбце 10 до строки 5*, находим, что это состояние является устойчивым. Следовательно, переход завершен. В рассмотренном примере при переходе из одного устойчивого состояния в другое автомат миновал одно транзитное состояние. В общем случае изменение состояния автомата может происходить с переходом через несколько транзитных состояний, которые, конечно, должны быть расположены в одном и том же столбце таблицы переходов.

25. Графы переходов и выходов.

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

Остановимся вначале на способе построения графа асинхронного и синхронного автомата. Пусть задан синхронный автомат со следующей таблицей переходов-выходов.
Таблица 25.1

Z\X

01

10

1

1/0

2/0

2

3/0

2/0

3

1/1

2/0

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

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

Таблица переходов-выходов асинхронного автомата представлена в вопросе 24 (таблица 1).

Таким образом, можем построить определение:

Определение 25.1: Граф автомата - это сигнальный граф, вершины которого обозначают состояния автомата, на дугах отражены условия перехода из состояния в состояние и значения выходных сигналов в виде дроби: над косой чертой - xj, под ней - yj.




26. Матрицы переходов.

Конечный автомат можно также описать с помощью матрицы переходов. Это аналог графа в табличной форме.



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

Построим матрицу переходов на примере синхронного автомата и его таблицы переходов-выходов, рассмотренного в вопросе 25.




01

10

х

х

10

01

01

10

х

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



27. Триггеры.

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

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

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

Триггер можно рассматривать как одноразрядную ячейку памяти.

В основе любого триггера (англ. — "тrigger" или "flip-flop") лежит схема из двух логических элементов, которые охвачены положительными обратными связями (то есть сигналы с выходов подаются на входы). В результате подобного включения схема может находиться в одном из двух устойчивых состояний, причем находиться сколь угодно долго, пока на нее подано напряжение питания.

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


  • RS-триггер (обозначается ТР) — самый простой триггер, но редко используемый.

  • JK-триггер (обозначается ТВ) имеет самое сложное управление, также используется довольно редко.

  • D-триггер (обозначается ТМ) — наиболее распространенный тип триггера.



28. RS-триггер.

У схемы есть два инверсных входа: –R — сброс (от английского Reset), и –S — установка (от английского Set), а также два выхода: прямой выход Q и инверсный выход –Q. Отрицательный импульс на входе –R перебрасывает выход в нуль, а отрицательный импульс на входе –S перебрасывает выход в единицу. Одновременные сигналы на входах –R и –S переводят выход в единицу, а после окончания импульсов триггер попадает случайным образом в одно из своих устойчивых состояний.




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

Входы

Выходы

-R

-S

Q

-Q

1

1

1

Без изменения

X

0

1

1

0

X

1

1

1

1

0

0

X

0

0

Не определен

0

X

0

Не определен

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



29. JK-триггер.

JK-триггер значительно сложнее по своей структуре, чем RS-триггер. Он относится к так называемым тактируемым триггерам, то есть он срабатывает по фронту тактового сигнала.

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

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




Таблица 7.3. Таблица истинности JK-триггера

Входы

Выходы

-S

-R

C

J

K

Q

-Q

0

1

Х

Х

Х

1

0

1

0

Х

Х

Х

0

1

0

0

Х

Х

Х

Не определено

1

1

10

1

0

1

0

1

1

10

0

1

0

1

1

1

10

0

0

Не изменяется

1

1

10

1

1

Меняется на противоположное

1

1

1

Х

Х

Не изменяется

1

1

0

Х

Х

Не изменяется

1

1

01

Х

Х

Не изменяется



30. D-триггер.

Cамый распространенный D-триггер занимает, можно сказать, промежуточное положение между RS-триггером и JK-триггером. Помимо общих для всех триггеров входов установки и сброса –S и –R, он имеет один информационный вход D (вход данных) и один тактовый вход C.




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

Входы

Выходы

-S

-R

C

D

Q

-Q

0

1

Х

Х

1

0

1

0

Х

Х

0

1

0

0

Х

Х

Не определено

1

1

01

1

1

0

1

1

01

0

0

1

1

1

0

Х

Не меняется

1

1

1

Х

Не меняется

1

1

10

Х

Не меняется

Тактируется триггер (то есть меняет свое состояние) по положительному фронту сигнала С (по его переходу из нуля в единицу) в зависимости от состояния входа данных D. Если на входе D единичный сигнал, то по фронту сигнала С прямой выход триггера устанавливается в единицу (инверсный — в нуль). Если же на входе D — нулевой сигнал, то по фронту сигнала С прямой выход триггера устанавливается в нуль (инверсный — в единицу).




31. Регистры.

Регистры представляют собой, по сути, несколько D-триггеров (обычно от 4 до 16), соединенных между собой тем или иным способом. Триггеры, входящие в состав регистров, не имеют большого количества разнообразных управляющих входов, как одиночные триггеры.

Все регистры делятся на две большие группы:



  • Параллельные регистры;

  • Регистры сдвига (или сдвиговые регистры).

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

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




Рис. 31.1.  Структура параллельного регистра (а) и сдвигового регистра (б).

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



Параллельные регистры, в свою очередь, делятся на две группы:

  • Регистры, срабатывающие по фронту управляющего сигнала С (или тактируемые регистры).

  • Регистры, срабатывающие по уровню управляющего сигнала С (или стробируемые регистры).

Регистры, срабатывающие по фронту.


Принцип действия регистров, срабатывающих по фронту тактового сигнала, ничем не отличается от принципа действия D-триггера. По положительному фронту тактового сигнала С каждый из выходов регистра устанавливается в тот уровень, который был в этот момент на соответствующем данному выходу входе D, и сохраняется таковым до прихода следующего положительного фронта сигнала С. То есть если триггер запоминает один сигнал (один двоичный разряд, один бит), то регистр запоминает сразу несколько (4, 6, 8, 16) сигналов (несколько разрядов, битов). Память регистра сохраняется до момента выключения питания схемы.

Регистры, срабатывающие по уровню.


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

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

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

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

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

  • С приходом каждого нового входного импульса двоичный код на выходе счетчика увеличивается (или уменьшается) на единицу.

  • Срабатывать счетчик может по отрицательному фронту входного (тактового) сигнала или по положительному фронту.

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

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

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

Большинство счетчиков работают в обычном двоичном коде, то есть считают от 0 до (2N–1), где N - число разрядов выходного кода счетчика. Имеются также двоично-десятичные счетчики, предельный код на выходе которых не превышает максимального двоично-десятичного числа, возможного при данном количестве разрядов. Двоично-десятичные счетчики удобны, например, при организации десятичной индикации их выходного кода. Применяются они гораздо реже обычных двоичных счетчиков.



По быстродействию все счетчики делятся на три большие группы:

  • Асинхронные счетчики (или последовательные).

  • Синхронные счетчики с асинхронным переносом (или параллельные счетчики с последовательным переносом, синхронно-асинхронные счетчики).

  • Синхронные счетчики (или параллельные).

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

Асинхронные счетчики.


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

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

Таким образом, если нам нужен выходной код асинхронного счетчика, то есть все его выходные сигналы (разряды) одновременно, то должно выполняться следующее неравенство: T> Ntз, где T - период входного сигнала, N - число разрядов счетчика, tз - время задержки одного разряда.

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


Синхронные счетчики с асинхронным переносом.


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

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

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

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

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


33. Распознаватели.

Пусть Σ={a1, …, am} - это алфавит, который состоит из конечного множества элементов, называемых символами (буквами).

Слово в алфавите Σ - это конечная последовательность символов этого алфавита: w =w1… wn, wi Σ при i=1, …, n. Число букв в этой последовательности называется длиной слова и обозначается |w|. Имеется одно специальное "пустое" слово длины 0. Будем обозначать его через ε. Для слова определена операция конкатенации.

Языком в алфавите Σ называется произвольное множество слов этого алфавита. Язык, включающий все слова в алфавите Σ (в том числе и пустое слово ε), будем обозначать через Σ*.

Конечные автоматы часто используются для определения тех или иных свойств слов, т.е. для распознавания языков: автомат, распознающий некоторый язык L должен по произвольному слову w ответить на вопрос " w L? ". Для решения такой задачи функция выходов может быть заменена на проверку того, в какое состояние переходит автомат после получения входного слова w - "принимающее" или "отвергающее".



Определение 33.1: Детерминированный конечный автомат (ДКА) - распознаватель - это система вида

включающая следующие компоненты:



  • Σ ={a1, … , am} (m 1) - конечное множество - входной алфавит;

  • Q={q0, … , qn-1} (n 1) - конечное множество - алфавит внутренних состояний;

  • q0 Q - начальное состояние автомата;

  • F Q - множество принимающих (допускающих, заключительных) состояний;

  • Φ: Q × Σ Q - функция переходов,

  • Φ(q, a) - это состояние, в которое переходит автомат из состояния q, когда получает на вход символ a.

Функцию Φ называют программой автомата A и задают как список из m n команд вида qiaj Φ(qi,aj) .

Удобно также задавать функцию Φ с помощью описанной выше таблицы размера n × m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита Σ, и в которой на пересечении строки qi и столбца aj стоит состояние Φ(qi,aj).

Автоматы-распознаватели можно представлять с помощью размеченных ориентированных графов, называемых диаграммами.

Определение 33.2: Диаграмма ДКА A = <Σ, Q, q0, Φ > - это ориентированный (мульти)граф DA=(Q, E) с помеченными ребрами, в котором выделена вершина - начальное состояние q0, из каждой вершины q Q выходит |ΣX| ребер, помеченных символами a Σ так, что для каждой q Q и каждого символа a Σ имеется единственное ребро из q в вершину q' =Φ(q,a) с меткой a .

Скажем, что представленный последовательностью ребер путь p=e1e2 … et в диаграмме несет слово w=w1w2 … wt, если wi - это метка ребра ei (1 i t). Если q - начальная вершина (состояние) этого пути, а q' - его заключительная вершина, то будем говорить, что слово w переводит q в q'.

Работа конечного автомата-распознавателя состоит в чтении входного слова и изменению состояний в зависимости от его символов.

Определение 33.3: Назовем конфигурацией ДКА A = <Σ, Q, q0, F, Φ, > произвольную пару вида (q, w), в которой q Q и w Σ*.

На множестве конфигураций введем отношение перехода за один шаг :



Если w=ε, то положим для каждого q Q: (q, ε) (q, ε).

Через обозначим рефлексивное и транзитивное замыкание .

Содержательно, означает, что автомат A, начав работу в состоянии q на слове w=w1 … wl, через некоторое конечное число шагов 0 k l прочтет первые k символов слова w и перейдет в состояние q', а w' =wk+1 … wl - это непрочтенный остаток слова w.



Определение 33.4: ДКА A распознает (допускает, принимает) слово w, если для некоторого q F

, т.е. после обработки слова w автомат переходит в принимающее состояние.

Язык LA, распознаваемый (допускаемый, принимаемый) автоматом A, состоит из всех слов, распознаваемых этим автоматом:



Язык называется конечно автоматным, если он распознается некоторым ДКА.

Из этого определения, в частности, следует, что ε LA q0 F. Один и тот же язык может распознаваться разными автоматами.

Определение 33.5: Автоматы-распознаватели A и B называются эквивалентными, если совпадают распознаваемые ими языки, т.е. LA = LB.

Определение распознавания слова и языка можно легко перевести на язык диаграмм.



Лемма 33.1: Автомат A распознает (допускает, принимает) слово w, если для некоторого q F в диаграмме DA имеется путь из q0 в q, который несет слово w, т.е. w переводит q0 в заключительное состояние q.

34. Автоматы с распределёнными состояниями. Матрица переходов.

Определение 34.1: Автоматы с распределенными состояниями каждой паре zi-xi имеют в соответствии состояние zk и только одно, где Z={z1, z2, ……zn} – состояния автомата и X={x1,x2,……xn} – входной алфавит. При этом выходного алфавита у автомата может и не быть.

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

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

Пример: Матрицу переходов рассмотрим на примере автомата, который ищет в строке, состоящей их символов А и В, первую подстроку типа ABBAA. Входной алфавит Х={А, В}. Из графа автомата имеем следующие состояния Z={S0,……S5}.

Граф автомата:



A

A

B

B

A




B

B

A


A

A+B


B






Матрица переходов:



В

А

х

х

х

х

х

А

В

х

х

х

х

А

х

В

х

х

В

х

х

х

А

х

х

х

В

х

х

А

х

х

х

х

х

В+А



35. Устойчивые предельные состояния распределенных автоматов.

Пусть дан распределённый автомат.



Определение 35.1: Если на вход распределённого автомата поступают сигналы из алфавита X={x1, x2,……,xn}, то в этом автомате устойчивым предельным состоянием называется состояние zk, в которое автомат переходит под действием сигналов отличных от xk.Состояния zk изображаются так:


xk




xk

Если все состояния автомата устойчивы, то автомат называется устойчивым.
V W V

W

Триггер типа Т – неустойчивый автомат, т.е. если на входе присутствует сигнал W, то он будет менять своё состояние непредсказуемо.



Q(t+1)

q(t)


пусть

>t

Вывод: триггер T- очень чувствителен к задержкам.

RS-триггер является устойчивым триггером.
V Z V


U U

Z


Q(t+1)


q(t)

Так как RS триггер не зависит от длительности входного сигнала, то элемент задержки не нужен.



36. Эквивалентные автоматы. Минимизация автоматов.

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

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

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

Определение 36.3: Состояния называются k+1 различимыми, если любая допустимая входная последовательность длины k приводит к одинаковым выходным последовательностям при условии, что автоматный процесс начинается с этих состояний, а входная последовательность длины k+1 приводит к различным выходным последовательностям при тех же условиях.

Алгоритм Мили.

Алгоритм Мили состоит в следующей последовательности.



  1. Состояния автомата разбивают на классы эквивалентности πi. В один класс попадают состояния, имеющие одинаковую реакцию на входные последовательности длины 1 (т.е. состояния, имеющие одинаковые строки в таблице выходов).

  2. Для k от двух до предпоследнего состояния автомата из возможных производится дробление пока πk<>πk-1.

  3. В новое разбиение πk входит состояния, которые либо уже ранее входили в разные классы, либо входили в один класс, но показали разную реакцию на последовательности длины k.

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

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

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

37. Критические и некритические состояния элементов памяти.

Задача кодирования состояний является одной из основных задач канонического метода структурного синтеза автоматов. Напомним, что кодирование заключается в установлении взаимно-однозначного cоответствия между множеством А = {а1,…,аm} состояний автомата и множеством R-компонентных векторов {К1,…, Кm), Кm=(еm1,…,emR}, где еmR, - состояние r-го элемента памяти r=1,…,R. В качестве элементов памяти возьмем RS-триггеры, которые будем обозначать Т1,…,ТR.

Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Так, если автомат переходит из состояния аm с кодом 0101 в состояние аs, с кодом 1001, то это означает, что триггер Т1, переходит из состояния 0 в состояние 1, триггер Т2 - из состояния 1 в состояние 0, а состояние триггеров Т3, и Т4 не изменяются.

При функционировании автомата могут появиться так называемые состязания (гонки). Явление состязаний возникает вследствие того, что элементы памяти имеют различные, хотя и достаточно близкие, времена срабатывания. Кроме того, различны также задержки сигналов возбуждения, поступающих на входные каналы элементарных автоматов по логическим цепям неодинаковой длины. Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания. Тот элемент, который выиграет эти состязания, т. е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное его графом. Поэтому в процессе перехода из состояния аm в состояние аs, под действием входного сигнала zf автомат может оказаться в некотором промежуточном состоянии аk или аl, в зависимости от того, какой элемент памяти выиграет состязания.

Если затем при том же входном сигнале автомат из аk и аl, перейдет в cостояние аs то такие состязания являются допустимыми, или некритическими (элементы памяти в эти моменты также находятся в некритическом состоянии). Если же в этом автомате есть переход, например, из аk в аj № as, под действием того же сигнала zf, то автомат может перейти в аj, а не в аs, и правильность его работы тем самым будет нарушена. Такие состязания называются критическими состязаниями (элементы памяти находятся в критическом состоянии) или гонками.



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

Определим конечный автомат как следующую пятёрку: , где

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

У – выходной алфавит (набор допустимых выходных комбинаций);

Z – множество состояний устройства, т.е. множество состояний, которые принимают элементы памяти внутри устройства;

f – функция перехода, которая указывает какое следующее состояние примет автомат, если до того он находился в состоянии Zn и на вход пришло Хn;

g – функция выхода, которая указывает какой выход возникнет у автоматного устройства, если на вход пришло Хn.

Х = {x1, x2, x3, ……, xn}.

Y = {y1, y2, y3, ……, ym}.

Z = {z1, z2, z3, ……, zk}.

Конечный автомат имеет следующую таблицу переходов-выходов:

zi\xj

x1

… … …

xn

z1









.

.

.



.

.

.



zs/yl

.

.

.



zk






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










zn+1 = f(xn, zn)

yn+1 = g(xn, zn)







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


Смотрите также:
10. Статистические параметры логических элементов. К статистическим параметрам
513.54kb.
Курсовой проект по курсу «Схемотехника эвм»
49.11kb.
Лабораторная работа по дисциплине «Инженерная психология»
397.46kb.
Выбор оконечных транзисторов, расчет площади теплоотводов
22.29kb.
Сравнительный подход
114.82kb.
Параметры участка встраивания
42.26kb.
Стандарт является одним из ключевых элементов модернизации российской школы, базовые параметры которой были определены в Послании Президента России Д. А
77.67kb.
Составление запросов для поисковых систем с использованием логических выражений
206.73kb.
Оценка условий труда по параметрам микроклимата Методические указания
480.87kb.
Задачи: научиться применять статистические функкции в среде Mathcad
23.32kb.
Лабораторная работа №1. Построение логических схем
34.97kb.
1. Парная регрессия и корреляция 1
129.52kb.