Реферат: ПТЦА - Прикладная теория цифровых автоматов

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

1.5. СИНТЕЗ  КС  С  УЧЕТОМ  ОГРАНИЧЕНИЯ  НА  .

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

Пусть задана некоторая булева функция в виде

Для реализации  этой  функции  по  приведенному  выражению необходимо   использовать   3   логических  элемента  4И,  один логический элемент 5И, один  логический элемент 4ИЛИ.

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

и будем  рассматривать  их  как  некоторые  множества.  Находим попарные пересечения множеств:

,  ,  ,  ,  ,  .

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

.

     Обозначим F =   и находим  пересечения:

,   ,  .

     Следовательно, для исходной функции имеем:

.

          Обозначим ,

Пересечение.  Следовательно, окончательно имеем:

      Для реализации функции по последнему выражению необходимо 5 элементов 2И, 1 элемент 3И, 3 элемента 2ИЛИ ( рис.8 ).

Как видно из полученной схемы для ее реализации необходимы элементы с  = 2 или 3 (в отличие  от  исходной  с  = 4 или 5). Однако ранг схемы увеличился до 7, что приводит к увеличению задержки срабатывания схемы.

1.6. Анализ  комбинационных схем.

Задачи анализа КС возникают при необходимости проверить правильность синтеза (на этапе проектирования) или определить БФ, реализуемую КС (при анализе или ремонте схем). Все существующие методы анализа делятся на  прямые и косвенные.

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

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

Все упомянутые методы анализа являются машинoориентированными, что позволяет выполнить анализ схемы на ЭВМ.

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

1.7. Анализ комбинационных схем  методом  p-алгоритма.

При данном методе,  как упоминалось выше,  ищутся наборы входных переменных, обеспечивающих заданное значение на выходе КС. Наборы, обеспечивающие на выходе КС логическую 1, образуют так называемое  единичное покрытие  .  Аналогично, входные наборы,  обеспечивающие на выходе КС логический 0,  образуют нулевое покрытие .  Рассмотрим покрытияи для  простейшего  логического элемента 2И, выполняющего  функцию  Y=X1X2.  Таблица  истинности  для  этой функции:

 Табл.3  Таблица истинности функции Y=X1X2

Как видно из приведенной таблицы  только  при  единственном наборе X1=1 и X2=1 на выходе ЛЭ будет 1, т.е.  единичное  покрытие включает только один набор ={1 1}. На выходе ЛЭ будет 0 при трех наборах, образующих нулевое покрытие:

Это покрытие можно упростить,  заметив,  что  первый  набор склеивается со вторым и третьим, т.е.

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

Таблица 4.

ЛЭ                  Y                    Y                     Y                   Y                    Y                  Y                   Y

             НЕ                 2И              2И – НЕ           2ИЛИ        2ИЛИ–НЕ   ИСК. ИЛИ     3И – НЕ                                                                 

              X                 X1 X2             X1 X2              X1  X2             X1 X2           X1 X2          X1 X2 X3  

        1                   0   X              1     1               0     0             1    X            0    0            1    1   1                               

                                  X   0                                                             X    1            1    1    

        0                   1    1              0     X              1     X            0     0             0    1           0   X   X               

                                                        X     0              X     1                                  1    0           X   0    X                                             

                                                                                                                                               X   X    0  

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

Пример анализа КС (рис 9. ) методом p - алгоритма представлен в табл. 5. В последней колонке этой таблицы приведен оператор подстановки, в результате работы которого сигнал на выходе ЛЭ заменяется соответствующим покрытием. Необходимо обратить внимание, что все значения переменных, записанные в одной строке, должны одновременно быть в наличии     для     обеспечения      заданного    значения       выходного       сигнала. По-

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

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

Таблица 5 Анализ схемы методом  p – алгоритма.

а) Получение первого покрытия

б) Получение нулевого покрытия  

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

1. 8 Анализ КС  методом  синхронного  моделирования.

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

Рассмотрим метод синхронного моделирования на примере схемы ( рис.9 ).

На первом этапе схему разбиваем на уровни и записываем в порядке возрастания уровня уравнения, описывающие функционирование ЛЭ:

	№уровня №элемента уравнение 1 1 2 e1 = X1 X2 e2 = 2 3 e3 = 3 4 Y =  e4 = e3 + X5

Проанализируем схему при подаче на вход набора  X1=0, Х2=0, Х3=0, Х4=1, Х5=1. Для этого решаем записанные уравнения в порядке возрастания уравнения. Имеем: 

;

;

;

.

Следовательно, при подаче на вход набора {00011}, на выходе будет Y=1. Аналогично можно промоделировать работу схемы при подаче на вход любого другого набора.

1.9  Анализ  КС  методом  асинхронного  моделирования.

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

Рис. 11 а)

Рис. 11 . Статический риск сбоя.

а)- схема, б)- временные диаграммы. 

t1-время задержки инвертора

t2-время задержки элемента 2И   

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

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

При динамическом риске сбоя до и после переходного процесса состояния выходного сигнала противоположные, но в переходном процессе выходной сигнал несколько раз меняет свое значение.  Динамический риск сбоя возможен в схеме (рис.12 а) при смене набора (Х1=0, Х2=1, Х3=1) на набор (Х1=1, Х2=0, Х3=0) и иллюстрируется диаграммами (рис.12 б).

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

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

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

2.Записываются уравнения, описывающие каждый ЛЭ в порядке убывания уровня.

3.Для исходного входного набора А(X1, X2, … , Xn ) определяется значение сигналов на выходах всех ЛЭ схемы. Пусть данный набор А заменяется набором В(X1, X2, … , Xn ).

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

5.Решаются помеченные уравнения в порядке их записи в схеме         . После решения уравнение считается непомеченным.

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

Анализ схемы (рис.13) методом асинхронного моделирования приведен ниже. Для данной схемы входной набор А(1011110) заменяется набором В(1101011).

Рис. 13. Комбинационная схема для метода асинхронного моделирования.

Уравнения, описывающие ЛЭ:

	1-ый такт 2-ой такт 3-ий такт Y= e6 = e4 + e5 + X5 e5 = e3 X7 e3=X5 X6 e2=X5 X4 e1=X1 X2 * * - * * * * * * - - - * - - - - -

                              Табл. 6 Таблица моделирования схемы

                    Выходы            Такты моделирования                Прим.

                                              0          1          2           3                        

                         e6                  1          0          1           0              дин.

                         e5                  0          1          0           0              стат.

                         e4                  0          0          0           0

                         e3                   1          0          0           0

                         e2                   1          0         0            0           

                         e1                   0          1         0            1 

Как следует из результатов моделирования, при смене набора А набором В на выходе элемента 4 имеет место статический риск сбоя, а на выходе схемы - динамический риск сбоя.

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

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ АБСТРАKТНЫХ АВТО­МАТОВ.

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

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

Математической моделью  ЦА (а в общем случае любого дискретного устройства) является так называемый абстракт­ный  автомат, определенный как 6-компонентный кортеж: S=(A,Z,W,d,l,а1)  у которого:

1. A={a1, a2, ... ,am} - множество состояний (внутренний алфавит)

2.  Z={z1, z2, ... ,zf} - множество входных сигналов  (входной  алфавит)

3.  W={w1, w2, ..., wg} - множество выходных сигналов (выходной алфавит)

4. d : A·Z®A - функция переходов,  реализующая отображение Dd ÍА·Z в А. Иными словами функция d некоторым парам состояние - входной сигнал (аm, zf) ставит в соответствие состояния автомата аs= d (am, zf), asÎA.

5. l : A·Z®W - функция выходов,  реализующая отображение Dl ÍА·Z на W. Функция l  некоторым  парам состояние - входной сигнал (аm, zf) ставит  в  соответствие  выходные  сигналы  автомата Wg=l(аm, zf) , WgÎW.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9