УС

РК К=

РП

Хп

32

•» внутренние [сигналы : [управления

/!С$

РОИ.

С ТЭК . Lj

3

I"

Ш КША

=й r==fr

/7/7? 77"системы

Рис. 7.2

Первый микропроцессор появился в 1971 г. (Gntel4040). В настоящее время известно уже около 100 различных типов МП, точнее микропроцесоpных комплексов (наборов) МПК (МПН) БИС {21J, так как фирмы-изготовители .выпускают обычно наборы из нескольких БИС: МП, ОЗУ, ПЗУ, ППЗУ, ИВВ (порты [24]) и др. Гакое многообразие МП определяется различным сочетанием их характеристик.

Общими для всех типов МП являются следующие их основные характеристики и свойства [24]: малая разрядность слова: 2, 4, 8, 12 или 16 бит;

ограниченная мощность набора команд (обычно требуются двепять команд для выполнения операции, эквивалентной одной команде мини-ЭВМ);

аппаратно подкрепленная организация связи подпрограмм (с помощью стека);

программно-управляемый ввод-вывод;

низкая стоимость микро-ЭВМ (обычно 1-5% стоимости мини-ЭВМ

7.2. Методы программной реализации дискретных устройств

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

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

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

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

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

Непосредственное вычисление булевых функций.

Рассмотрим для примера булеву функцию f=x(yz\/ yz)M~xyz.(7.1)

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

1)логическое произведение y-z и занести результат в ячейку Л;

2)логическое произведение у-г и занести результат в ячейку В;

3)логическую сумму содержимого ячеек Л и В, занести результат в ячейку Л;

4)логическое произведение х- (содержимое ячейки Л) и занести результат в ячейку Л;

5)логическое произведение х-у и занести результат в ячейку В;

6)логическое произведение z- (содержимое ячейки В) и занести результат в ячейку В;

7)логическую сумму содержимого ячеек Л и В и занести результат (значение искомой функции) . в ячейку В.

При реализации вычисления этой булевой функции на основе МПС необходимо иметь программу в памяти системы, реализующую данную вычислительную процедуру. Эта программа должна быть составлена в системе команд используемого МП. Система команд наиболее распространенного отечественного однокристального 8-разрядного микропроцессора К-580 ИК-80, который входит в МПК серии К-580, приведена в [21].

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

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

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

Метод отображения входного набора. Рассмотрим функцию

f=wxy\jz(7.2)

Положим, что требуется вычислить значение этой функции навходном наборе переменных w, у, х, z, равном 1000. Будем считать, что такой входной набор определяет входное слово 1000,: Функция (7.2) включает в себя две конъюнкции: wyx и z. Если прямому вхождению переменной в конъюнкцию поставить в соответствие 1, а инверсному вхождению-0, то конъюнкции wyx будет соответствовать набор ОЮх, а конъюнкции z-набор ххх1. Символом «х» обозначены переменные, не входящие в рассматриваемую конъюнкцию. Построенные таким образом наборы далее будем называть словами-конъюнкциями. Очевидно, что если входное слово совпадает по всем разрядам с одним из слов конъюнкций рассматриваемой функции, то значение функции на данном входном наборе будет равно 1. В противном случае функция равна 0. Если конъюнкция образована не всеми переменными, то сравниваются только те разряды слова-конъюнкции, которые не содержат символа «х».

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

Обратимся к реализации такого подхода. Как и ранее, в качестве искомой функции возьмем функцию (7.2). Будем считать, что входные переменные уже введены в память микропроцессора и упорядочены в одно входное слово, каждый разряд которого соответствует одной входной переменной. С каждым из слов-конъюнкций искомой функции сопоставляется маскирующее слово. В разрядах маскирующего слова записаны 1, если соответствующие разряды слова-конъюнкции являются определенными, т. е. содержат 1 или 0. Если некоторый разряд слова-конъюнкции является неопределенным (т. е. содержит символ «х»), то в соответствующий разряд маскирующего слова записывается 0. Хранение маскирующих слов и слов-конъюнкций осуществляется в стеке. Пусть стек организован в оперативном ЗУ, а обращение к нему осуществляется через регистр указателя стека, в котором постоянно хранится адрес первого слова стека. По мере продвижения данных из стека в рабочие регистры микропроцессора содержимое регистра указателя стека автоматически увеличивается на единицу. Последним словом стека всегда является нулевое слово, т. е. слово, все разряды которого равны нулю.

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

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

Блок-схема программы вычисления функции (7.2) по методу

Таблица 7.1

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

Положить f=0

i

Издлечь из стека маскирующее слодо и слада-конъюнкцию

Поразрядное сложение памодулю? Входного слоВа ислова-коньюнкции

Поразрядное логическое умножение полученного результата и маскирующего слоён

Положить f=f

Останов

Рис. 7.3

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

В соответствии с блок-схемой программы, представленной на рис. 7.3, осуществляется программирование в системе команд используемого МП.

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

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