авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |

«Л. Ф. МАРАХОВСКИЙ ОСНОВЫ НОВОЙ ИНФОРМАЦИОННОЙ ТЕХНОЛОГИИ Фундаментальные основы построения реконфигурируемых устройств компьютерных систем и ...»

-- [ Страница 3 ] --

Q e j e : j Q a0 a1 a2 a3 a4 a5 a ej e1 a0 a1 a2 a3 – – – e2 a0 - a4 a5 a – – При описании работы многофункционального автомата А 2-го рода вы ходной сигнал зависит только от запоминаемых состояний блока j автомата, которые устанавливаются в тактовый момент t и сохраняются во время реа лизации функций сохранения состояний во время внутреннего такта авто матного непрерывного времени Т.

Автоматы 1-го и 2-го рода способны осуществлять функции переходов в тактовый момент t автоматного непрерывного времени Т под воздействием информационных х(t) входных сигналов.

Работа автомата 2-го рода может быть задана с помощью отмеченных таблиц функций o однозначных переходов вместе с функцией 2 таблицы выходов типа 2 и таблицы сохранения состояний (табл. 3.8). Пример таблич ного описания автомата 2-го рода А3 приведен в таблицах 3.8 –3.10.

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

Это принципиальное отличие автоматов 3-го рода позволяет им осуществ лять переходы в матричной структуре схем автоматной памяти (МФСП), ко торые происходят не только в блоках j состояний в тактовый момент t, представляющих строку состояний МФСП, но и в блоках i во время внут реннего такта, представляющих столбец состояний МФСП, за один внеш ний такт Т автоматного непрерывного времени.

Отмеченная Отмеченная таблица переходов 3.9 таблица переходов 3. 02 : Q(-1) X(t) Q(T) 0 : Q(-1) X(t) Q(T) уі у0 у1 у2 у3 уі у0 у4 у5 у 1 а0 а1 а2 а3 а0 а4 а5 а xi xi x1 а1 а2 а1 а0 x1 a4 a0 a6 a x2 а2 а3 а0 а2 x2 a5 a6 a4 a Автоматы 1-го, 2-го и 3-го рода также отличаются своими функциями 1, 2 и 3 выходных сигналов, рассматриваемых в автоматном непрерывном времени Т.

Функция выходов 1 автоматов 1-го рода реализуется только в тактовый момент t под воздействием информационных х(t) входных сигналов и со стояний автомата а(-1), то есть у(t)= 1(а(-1), х(t)), где у YI.

Функция выходов 2 автоматов 2-го рода реализуется в тактовый момент t после перехода автомата в новое состояний под воздействием информаци онных х(t) входных сигналов и предыдущего во времени состояния автомата а(-1). Функция выходов 2, во первых, является по этому сдвинутой по сравнения с началом тактового момента t, а также зависит только от вновь установленного состояния а(t) и сохраняемого состояния а(), где а(t) = а() и у(Т) = 2(а(t), а()), где у YII.

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

Работа автомата 3-го рода может быть задана с помощью таблиц функ ций o однозначных и отмеченных таблиц функций y укрупненных перехо дов вместе с функцией 3 таблицы выходов типа 3. Пример табличного опи сания автомата 3-го рода А3 приведен в таблицах 3.11–3.14 и таблицы сохра нения состояний (табл. 3.8).

Таблица переходов 3.11 Таблица переходов 3. 02 : Q(-1) X(t) Q(t) 0 : Q(-1) X(t) Q(t) 1 а0 а1 а2 а3 а0 а4 а5 а хi хi х1 а1 а2 а1 а х1 a4 a0 a6 a х2 а2 а3 а0 а х2 a5 a6 a4 a Отмеченная Отмеченная таблица переходов 3.13 таблица переходов 3. 02 : Q(t) E() Q() 0 : Q(t) E() Q() уі у0 у1 у2 у3 уі у0 у4 у5 у 1 а0 а1 а2 а3 а0 а4 а5 а еi еi е1 а1 а2 а1 а0 е1 a4 a0 a6 a е2 а2 а3 а0 а2 е2 a5 a6 a4 a 3.4. Табличные способы задания абстрактных вероятностных автоматов 3-го рода В отличие от детерминированных автоматов, в которых возможен толь ко однозначный переход от одного состояния в другое под воздействием элементарных однозначных р0(T) и укрупненных ру(T) входных слов, в веро ятностных автоматах осуществляется переход в состояние определенного блока j состояний автомата с определенной вероятностью Ре перехода под воздействием элементарных вероятностных рв(T) входных слов.

Вероятностный абстрактный автомат 3-го рода первого типа задается с помощью таблицы сохранения состояний, как и в детерминированных авто матах (табл. 3.8), таблицы однозначного перехода в ар(t) состояние (табл.

3.15–3.16), отмеченной таблицы переходов в а() состояние блока j состоя ний (табл. 3.17) с определенной вероятностью Ре перехода.

Таблица переходов 3.15 Таблица переходов 3. 02 : Q(-1) хр(t) ар(t) 0 : Q(-1) хр(t) ар(t) 1 а0 а1 а2 а3 а0 а4 а5 а хi хi хр ар ар ар ар хр ар ар ар ар Отмеченная таблица вероятностных переходов 3. B1 : ар(t) еj() j(аB()) 3 1 : ар(t) еj() YIII1 (ув1()) B B ув ej у0(Pe1) у1(Pe1) … уk(Pe1) ej ap j e0 а0(Pe1) а1(Pe1) … аk1(Pe1) … … … em а0(Pe1) а1(Pe1) … аkm(Pe1) m Вероятностный абстрактный автомат 3-го рода второго типа задается с помощью таблицы сохранения состояний, как и в детерминированных авто матах (табл. 3.8), таблицы однозначного перехода в а(t) состояние (табл.

3.18–3.19), отмеченной таблицы переходов в а() состояние блока j состоя ний (табл. 3.20) с определенной вероятностью Ре перехода.

Таблица переходов 3.18 Таблица переходов 3. 02 : Q(-1) X(t) Q(t) 0 : Q(-1) X(t) Q(t) 1 а0 а1 а2 а3 а0 а4 а5 а хi хi х1 а1 а2 а1 а0 х1 a4 a0 a6 a х2 а2 а3 а0 а2 х2 a5 a6 a a Отмеченная Отмеченная таблица переходов 3.9 таблица переходов 3. 02 : Q(-1) X(t) Q(T) 0 : Q(-1) X(t) Q(T) уі у0 у1 у2 у3 уі у0 у4 у5 у 1 а0 а1 а2 а3 а0 а4 а5 а xi xi x1 а1 а2 а1 а0 x1 a4 a0 a6 a x2 а2 а3 а0 а2 x2 a5 a6 a4 a Вероятностные переходы в автомате 3-го рода первого типа происходят в определенном блоке j состояний, а в автомате 3-го рода второго типа про исходят в определенном блоке µі состояний. Таким образом, вероятностные автоматы 3-го рода первого типа и вероятностные автоматы 3-го рода второ го типа осуществляют вероятностные переходы в состояния вполне опреде ленных подмножеств соответствующих блоков j и µі состояний с опреде ленной мерой вероятности.

Автоматы 4-го рода задаются таблицами переходов (3.15) – (3.16), а вы ходной сигнал у4(t) = 4(xp(t), ap(t)) зависит от входного сигнала xp(t) и уста новленного однозначного состояния базовой схемы памяти ap(t), которое не сохраняется ни при каких сохраняющих e() входных сигналов. После окон чания этого сигнала детерминированные автоматы должны устанавливаться в начальное состояние а0.

3.5. Табличный способ задания абстрактных нечетких автоматов 3-го рода Абстрактный нечеткий автомат 3-го рода задается с помощью таблиц сохранения состояний, как в многофункциональных детерминированных ав томатах (табл. 3.8), таблицы однозначного перехода в ар(t) состояние, как в вероятностных автоматах 3-го рода первого типа (табл. 3.15–3.16), и отме ченной таблицы переходов в а() состояние блока j состояний (табл. 3.21) с определенной вероятностью Рн перехода.

Отмеченная таблица нечетких переходов 3. yН : ар(t) еН()j(ан()) 3 : ар(t) еН() YIII (уН()) Н Н ун ej у0(Pн) у1(Pн) … уk(Pн) ej ap j e0 а0(Pн) а1(Pн) … аk1(Pн) … … … em а0(Pн) а1(Pн) … аkm(Pн) m 3.6. Графические способы задания переходов в многофункциональных абстрактных автоматах Абстрактные автоматы с памятью используются для реализации функ ций однозначного перехода в новое состояние аі(t) при соответствующем входном сигнале х(t) при условии сохранения этого состояния после оконча ния сигнала х(t), то есть во времени внутреннего такта автоматного непре рывного времени Т.

Однозначные переходы в абстрактных детерминированных автоматах 1-го и 2-го роду изображает рис. 3.3.

хі(t) хі(t) ej() аk( – 1) аі(Т) Рис. 3.3. Однозначный переход Выходные сигналы абстрактных автоматов 1-го и 2-го рода соответст венно изображаются в графе либо на дуге перехода из одного состояния в другое в автоматах 1-го рода, либо возле вершины графа в автоматах 2-го ро да.

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

хі(t) ej() ej() ak( – 1) aі(t) аj() Рис. 3.4. Укрупненный переход Выходные сигналы абстрактных автоматов 3-го рода соответственно изображаются, как и в автоматах 2-го рода, возле вершины графа.

Блок j ej() а j1 () хр (t) e j() а k( – 1) a і(t) ej() а jN () ej() Рис. 3.5. Вероятностный переход первого типа Вероятностные абстрактные автоматы первого и второго типа 3-го рода используются для реализации функций вероятностного перехода в новое со стояние а() при соответствующих входных элементарных словах рв1(T)) или рв2(T) с определенной вероятностью Ре во время внутреннего такта, как это изображено на рис. 3.5 (для вероятностного автомата 3-го рода пер вого типа и автомата 4-го рода) и на рис. 3.6 (для вероятностного автомата 3-го рода второго типа).

Блок µі ej() аj1() e вj () хi(t) аk( – 1) aі(t) ej() в e j () аjM() Рис. 3.6. Вероятностный переход второго типа Нечеткие абстрактные автоматы 3-го рода используются для реализации функций нечеткого перехода в новое состояние а() при соответствующем входном элементарном слове рн(T) с определенной вероятностью Рн во время внутреннего такта, как это изображено на рис. 3.7.

Блок аj1() ej() в ej () аjN() ej() ejв() Блок аj1() ej() ejв() хр(t) ak( – 1) aі(t) ejв() ejв() аjN() ej() Блок k аj1() ej() ejв() аjN() ej() Нечітка підмножина Qн Рис. 3.7. Нечеткий переход в автомате 3-го рода Таким образом, многофункциональные абстрактные автоматы увеличи вают типы переходов, используемых в классических абстрактных автоматах Мили и Мура, расширяют понятие функционирования автомата с дискретно го автоматного времени t до непрерывного автоматного времени T, что дает возможность более глубоко исследовать их работу.

3.7. Математическая модель иерархического абстрактного автомата с многофункциональной системой организации памяти Последовательные многофункциональные автоматы Мараховского 1-го, 2-го и 3-го рода, имеющие два множества входных алфавитов: Х – информа ционный входной алфавит и Е – сохраняющий входной алфавит, способен настраиваться другим многофункциональным автоматом через множество букв еj (еj Е) сохраняющего входного алфавита на функционирование в определенном блоке j (подмножестве) своих состояний. В этом случае об разуется многоуровневая (иерархическая) структура абстрактного Fи– Yn Xn Sn En 1 Zn- Y Yn Х Y Y X S E 1 Z Y Yn Рис. 3.8. Иерархический абстрактный Fи–автомат автомата из последовательных многофункциональных подавтоматов Si (i=1, 2, …, n). Организация такой объединенной структуры иерархического авто мата (ИА) представлена на рис. 3.8.

Каждый многофункциональный подавтомат Si (i=1, 2, …, n) иерархиче ского абстрактного Fи–автомата может переходить из одного состояния в другое параллельно с другими подавтоматами ИА (рис. 3.8). Функциониро вание подавтомата Si в определенном подмножестве состояний j может быть изменено воздействиями входных букв информационного алфавита Х в тактовый момент t и воздействиями результатов работы других подавтоматов Si ИА буквами сохраняющего входного алфавита Е в моменты внутреннего такта автоматного непрерывного времени Т.

Дадим определение абстрактного иерархического Fи–автомата.

Определение 3.2. Математической моделью иерархического дискретного устройства с многофункциональной системой организации памяти является абстрактный иерархический Fи–автомат, определяемый как N-компонентный вектор Fи = (S1, S2, …, SN), (3.1) компоненты Si которого задаются шестнадцатикомпонентным вектором Si ( X i, Ei, Z i, Yi1,Yi II, Yi III, Qi, i, ei0, ai0, i0, ie, iy, i1, i2, i3 ) (3.2) у которого Xi – множество информационных входных сигналов;

Ei – множество сохраняющих входных сигналов;

Zi – множество разрешающих входных сигналов;

Yi I – множество выходных сигналов типа 1;

Yi II – множество выходных сигналов типа 2;

Yi III – множество выходных сигналов типа 3;

Qi – произвольное множество состояний;

i – множество блоков i состояний подавтомата Si;

j ei – начальный сохраняющий входной сигнал;

ai – начальное состояние подавтомата Si;

i : Qi Xi Qi – однозначная функция переходов;

i : Qi ei i – функция сохранения блоков состояний;

j j e i : Qi Ei i – функция укрупненного перехода;

y j i : Qi Xi Yi I – функция выходов типа 1;

i : i Yi II – функция выходов типа 2;

j i : Qi Ei Yi III – функция выходов типа и определенный функционально, как и компоненты структуры Si, шестна дцатикомпонентным вектором FA = (X, E, Z, Y I, Y II, Y III, Q,, E0, Q0, F1, F2, F3, 1, 2, 3 ) (3.3) у которого X={X1, X2, …, XN} – множество информационных входных сигналов;

E ={E1, E2, …, EN}– множество сохраняющих входных сигналов;

Zi ={Z1, Z2, …, ZN}– множество разрешающих входных сигналов;

Y I ={ Y1I,Y2I,...,Y NI }– множество выходных сигналов типа 1;

Y II ={ Y1 II,Y2II,...,YNII }– множество выходных сигналов типа 2;

Y III ={ Y1 III,Y2III,...,YNIII }– множество выходных сигналов типа 3;

Q ={ Q1, Q2, …, QN}– произвольное множество состояний;

={ 1, 2,…, N }– множество блоков состояний подавтомата Si;

E0= {e1, e2,..., eN } – начальный сохраняющий входной сигнал;

0 0 a0 = {a1, a2,..., a N } – начальное состояние подавтомата Si;

0 0 F1: Q X Q – однозначная функция переходов, реализующая отобра жение DF1 Q X в Q;

F2: Q еj j – функция сохранения блоков состояний, реализующая отображение DF2 Q еj в j;

F3: Q E j – функция укрупненного перехода, реализующая ото бражение DF3 Q E в j;

1: Q X Y I – функция выходов типа 1, реализующая отображение D1 Q X на Y I ;

2: j Y II – функция выходов типа 2, реализующая отображение D2 j на Y II ;

3: Q E Y III – функция выходов типа 3, реализующая отображение D3 Q Е на Y III.

Подавтоматы Si, реализующие свою автоматную память на регистрах открытого типа, функционируют в автоматном непрерывном времени Т.

В начальный тактовый момент t0 все подавтоматы Si устанавливаются в начальное состояние а0 соответствующим входным сигналом N i (t 0 ) X i. Во время последующего внутреннего такта 0 начальное состояние а0 сохраня ется под воздействием начальных сохраняющих ei0 (0) входных сигналов.

Объединение состояний ai подавтоматов Si определяют состояния аi иерар j хичного автомата в данный тактовый момент ti или i автоматного непре рывного времени Тi. В иерархичном автомате А во время тактового момента ti все или только некоторые подавтоматы Si могут осуществлять функции одно значных переходов i, реализуя общую функцию однозначных переходов F иерархического автомата А в новое состояние a s (t ) ai (t ). Во время внут j i реннего такта i подавтоматы Si могут осуществлять укрупненные переходы i y, реализуя общую функцию перехода F3 иерархического автомата А в но вое состояние a k ( ) ai (). Если подавтоматы Si за время всего внешнего j i такта Т не совершают переходы в новое состояние, то, следовательно, они реализуют функцию сохранения состояний ie, реализуя в ИА А объединен ную функцию сохранения состояний F2.

Каждый из подавтоматов Si работает в определенном блоке i состоя j ний всего множества своих состояний Qi. Блоки i состояний подавтоматов j Si образуют в ИА А определенный блок i множества блоков i состояний, в j котором ИА А функционирует в данный момент времени.

Характерной особенностью ИА А является возможность взаимодейст вия подавтоматов Si не только во время такта ti, но и во время внутреннего такта i автоматного непрерывного времени Тi. Память подавтоматов Si пред ставляет собою матричную структуру, в которой во время такта ti под воз действием информационных хі(t) входных сигналов подавтомат Si способен перейти из одного состояния в другое в одном блоке i состояний (строке j матричной структуры схемы автоматной памяти). А во время внутреннего такта i под воздействием сохраняющих еj() входных сигналов подавтомат Si способен перейти из одного состояния в другое в одном блоке µi (столбике матричной структуры схемы автоматной памяти), то есть из определенного состояния одного блока i в определенное состояние другого блока i со j j стояний.

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

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

Наглядным способом задания классических автоматов с памятью на тригге рах является задание их в виде микропрограммы [125] или в более обобщен ном виде автограммы [26].

Для алгоритмического описания иерархических автоматов с автоматной памятью с общим состоянием, состоящим из частичных состояний подавто матов Si, предложен термин «полиграмма» по следующим соображениям. Во первых, термин «микропрограмма», «автограмма» и другие способы задания автоматов с памятью на триггерах ориентированы вполне обоснованно на описания функций переходов в автоматах только во время тактового момента ti, имеют сильное ограничение, не позволяющее описывать работу автомата во время внутреннего такта i автоматного непрерывного времени Тi. Во вторых, понятия «микропрограмма», «автограмма» и другие способы задания классических автоматов ориентированы на реализацию запоминаемого со стояния в регистре на триггерах. В связи с этим, термины «микропрограм ма», «автограмма» не подходят при описании общего состояния регистров на схемах автоматной памяти. Термин же «полиграмма» ассоциируется со схемной реализацией управления на многоуровневых регистрах с много функциональной системой организации памяти, которую называют много уровневой иерархической автоматной реализацией [64]. В-третьих, поли грамма ориентирована не только на преобразование входной информации в выходную информацию, но и на изменение области запоминаемых состояний автомата, которая определяется сохраняющим еj() входным сигналом. Эта особенность позволяет использовать полиграмму при описании иерархиче ской структуры автомата, способной преобразовывать входную информацию и изменять внутреннюю структуру преобразования информации [64].

Полиграмма описывает каждое состояние иерархического автомата (ИА) А как объединение состояний подавтоматов Si.

a k ai (3.3) i В каждом пункте полиграммы описываются режимы работы подавтома тов Si за один внешний такт Т автоматного непрерывного времени. За один внешний такт Т ИА А воспринимает входное слово Rk(T), состоящее из сово купности элементарных рi(T) входных слов подавтоматов Si Rk p i (T ). (3.4) i Под воздействием входного слова Rk ИА А способен перейти в новое состояние as и выдать выходные сигналы Yki (і=1, 2, 3), состоящие из сово купности выходных сигналов Yki определенных типов подавтоматов Si Yk1 (t ) Yi1 (t );

(3.5) i Yk2 (T ) Yi 2 (T );

(3.6) i Yk3 () Yi 3 (), (3.7) i где выходные сигналы Yi1 (t ), Yi 2 (T ), Yi 3 () определяются соответственно по функциям выхода, описываемые в уравнениях (2.15)–(2.17).

При неизменяемых сохраняющих еі() входных сигналах подавтоматы Si функционируют в определенных блоках i своих состояний, а, следова j тельно, и ИА А функционирует в те же периоды времени в определенных блоках k своих состояний k i (3.8) i Каждое состояние аі подавтомата Si сохраняет свое значение при соот ветствующих сохраняющих еj входных сигналах. Изменение сохраняющего еj входного сигнала в подавтомате Si происходит в тактовый момент t в зависи мости от выходных сигналов Yi 2 (T ), поступающих от других подавтоматов Si в соответствии с алгоритмом решения задачи, и во время внутреннего такта сохраняющий еі() входной сигнал определяет область запоминаемых со стояний (блок i состояний) подавтомата Si. Сохраняющие еі() входные j сигналы однозначно определяют блоки i состояний, в которых работает j подавтомат Si, а совокупность Еk сохраняющих еі() входных сигналов одно значно определяет блок k состояний, в которых работает ИА А Ek e j (3.9) j Пункт полиграммы при детерминированном элементарном входном слове Rk записывается в следующем виде:

KE. R1 Y11 – K1E1, R2 Y21 – K2E2, (3.10) ------------------- Rm Y21 – KmEm, где K – состояние ИА А;

Е – сохраняющий входной сигнал ИА А;

Rj(j=1, 2, …, m) – элементарное входное слово ИА А;

Kj(j=1, 2, …, m) – состояние ИА А, к которому совершается переход от состояния K при выполнении строки j;

Еj(j=1, 2, …, m) – сохраняющий входной сигнал, при котором запо минается состояние Kj;

Y ji ( j 1, 2,..., m) – выходной сигнал типа і ИА А.

Каждая строка (Rj Y11 – KjEj) пункта KE полиграммы описывается в виде Sk строк a1e1 p j1 Y ji1 a j1e j1, a2e2. p j 2 Y ji2 a j 2e j 2, (3.11) i aqeq. p jq Y jq a jqe jq, q – число строк Sk(k= 1, 2, …,, m где ), имеющихся в описа нии строки полиграммы j (j=1, 2, …, m);

pj – элементарное входное слово строки Sk;

i Y ji – выходной вектор строки Sk;

i aj – состояние подавтомата Si, к которому совершается пере i ход от состояния аі в состояние аk при выполнении строки Sk;

еі – сохраняющий входной сигнал состояния аі.

Такое описание поведения ИА А в состоянии КЕ является пунктом ие рархического алгоритма функционирования автомата А.

Пункт полиграммы КЕ, как видно из описания поведения ИА А, имеет иерархическую структуру, то есть вначале описываются обобщенные со стояния К0, К1, …, Кm, обобщенные элементарные входные слова Rj(j=1, 2, …, m), обобщенные входные сигналы Е0, Е1, …, Еm, а затем каждая строка пункта полиграммы разворачивается в Sk(k= 1, 2, …,, m ) строк, которые реализуются в подавтоматах Si ИА А, осуществляя переход из одного со стояния аі в состояние аk при выполнении строки Sk. Во время функциони рования ИА А некоторые, а, возможно, и все подавтоматы Si могут не изме нять своих состояний на каком-то отрезке автоматного времени. Тогда при описании полиграммы ИА А в конце строк будут обозначения состояний, которые совпадают с начальным обозначением пункта полиграммы или пункта строки полиграммы.

Каждая j-я строка пункта полиграммы КЕ состоит из следующих эле ментов, функционирование которых описывается в автоматном непрерыв ном времени Т: обозначение самого пункта КЕ, отображающего состояние К(-1), сохраняемое при входном сигнале Е(-1);

элементарного входного слова Rj(Т), состоящего из последовательных соответственно информацион ного Х j(t) входного сигнала и сохраняющего Еj() входного сигнала;

Y ji вы i ходных сигналов, описываемых уравнениями (3.5)–(3.7).

Содержательный смысл каждой j-й строки полиграммы заключается в установлении связи между состояниями К(-1) ИА А в предыдущем внеш нем такте Тi-1 и реакцией ИА А в следующем внешнем такте Тi- при переходе в состояние Кj().

Каждая j–я строка полиграммы может быть представлена из трех час тей. Первая часть задает вектор Rj, вторая – вектор Y ji выходных сигналов, а i третья часть определяет функцию F2 однозначного сохранения вектора Kj состояний либо функцию F3 укрупненного перехода в состояние Ks при век торе Е j сохраняющего входного сигнала.

Вектор Еj сохраняющего входного сигнала при реализации функции F однозначного сохранения вектора Kj состояний задает определенный блок j запоминаемых состояний ИА А, в котором он функционирует в данный мо мент автоматного непрерывного времени Т, а при реализации функции F осуществляет укрупненный переход в состояние Ks в момент внутреннего такта автоматного непрерывного времени Т. Входной сигнал Еj обеспечи вает межуровневую связь подавтоматов Si в ИА А в момент внутреннего так та автоматного непрерывного времени Т.

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

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

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

Опишем некоторые основные типы строк полиграммы.

Строку полиграммы, имеющий вид KE. Rj Y j – KjEj, (3.12) назовем общей строкой, подчеркивая этим термином, что в данной строке представлены все три вектора упомянутой команды.

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

Например, строку вида KE. Еi Y j – KjEj при Еi Ej (3.13) назовем строкой перехода третьего рода, поскольку в ней описан переход, осуществляемый под воздействием только компоненты вектора Еi сохраняе мых входных сигналов. В этом случае Хi=, а Еi Ri.

Строку вида KE. Rj – KjEj, (3.14) назовем просто строкой перехода, поскольку в ней представлен только пе реход в следующее состояние KjEj без вектора Y j выходных сигналов.

Строку вида KE. Rj Y j –, (3.15) назовем строкой выхода, поскольку в ней не представлен переход в вектор состояний Kj и не представлен вектор Ej сохраняющий новое состояние.

При совпадении векторов Еi и Ej в строке их можно опустить. Строка тогда (например, общая) принимает такой вид K. Rj Y j – Kj, (3.16) а векторы Еi и Ej (Еi = Ej) в данном случае подразумеваются и задают вполне определенный блок j (K, Kj j) запоминаемых состояний. Такая строка (3.16) называется С-вида и используется при описании микропрограммы или автограммы [26] автоматов Мили, Мура и С-автомата, которые используют в качестве памяти триггеры в регистрах, состояния которых сохраняются при одном сохраняющем е() входном сигнале. Такое описание микропрограм мы лишний раз подчеркивает, что автоматы Мили, Мура и С-автомата явля ются подмножеством многофункциональных автоматов Мараховского, на основе которых рассматривается полиграмма, описывающая ИА А, постро енный на схемах автоматной памяти.

Отметим одну важную особенность выходных векторов Y ji ИА А.i Упомянутые выше компоненты Yki векторов Y ji (3.5)–(3.8) одновременно во i i внешнем такте Т могут инициировать различные операции в управляемых объектах, а также функциональное отключение одного из подавтоматов Si ИА А, при определении его ненадобности или ошибочности в работе. Это свойство является важным при создании отказоустойчивых цифровых уст ройств [8].

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

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

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

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

3.9. Формулирование полиграммы Работать с полиграммой упрощается, если соблюдать следующие прави ла.

1. Пункт полиграммы удобно обозначать двумя номерами, отмечен ными символами K и E. Например, 12K,2E.

2. Начальный пункт обычно имеет номер 1K,1E, а остальные пункты полиграммы нумеруются числами до максимального номера с символом K и до максимального номера с символом E.

3. Пункты в полиграмме целесообразно располагать в порядке возрас тания в начале номера с символом K, без изменения номеров возле сим вола E, а после изменения номера с символом E нумерацию с символом K можно начинать с начала, то есть с номера 1K.

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

5. Установочные пункты не имеют конкретных номеров, так как при подсчете количества пунктов в полиграмме они не учитываются. Целе сообразно место установочного пункта определять в начале нумерации чисел с символом K при определенном номере с символом E.

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

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

Задание автомата в табличном виде, в виде графа, в виде полиграммы или каким-то другим способом является творчеством проектировщика. Про ектировщик перед заданием автомата, с одной стороны, должен полностью разобраться в работе объекта и временных последовательностях управляю щих воздействий, необходимых при управлении объектом, а с другой сторо ны – владеть методами формального синтеза автоматов по полиграмме на доступной ему элементной базе со схемами автоматной памяти сверхболь ших интегральных схем (СБИС). Проверка правильной (корректной) работы полиграммы или спроектированного управляющего устройства может быть выполнена средствами моделирования устройства на компьютере [74].

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

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

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

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

2. Процесс расщепления общей информации алгоритма на уровни воз можен при иерархическом характере обработки информации во время реше нии задачи.

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

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

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

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

7. Формулирование полиграммы надо начинать с установочного пункта.

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

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

9. Необходимо проверить согласование во времени процессов, проис ходящих в управляемом объекте и в автомате. При несогласовании во вре мени процессов необходимо скорректировать полиграмму.

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

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

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

Часть ОСНОВЫ ПОСТРОЕНИЯ СХЕМ АВТОМАТНОЙ ПАМЯТИ Введение В 1918 году русский ученый Михаил Александрович Бонч-Бруевич соз дал ламповый триггер, способный сохранять одну двоичную цифру. Это изо бретение положило фундамент электронным цифровым компьютерам [74]. В дальнейшем, в США этот триггер стали называть автоматом Мура с нетриви альной памятью в честь американского математика, начавшего изучение пра вильных автоматов [24].

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

12–14;

18–21;

24–26;

32;

40;

42–43;

46;

90–91;

94–95;

104–106;

108;

114– 117;

119–121;

124–132;

135–136;

140;

143].

Актуальным направлением снять ограничения двоичных схем памяти стала разработка многофункциональных схем памяти. Исследования в облас ти создания многофункциональных схем памяти рассмотрены многими из вестными учеными ХХ века. В первую очередь нужно выделить работы представителей научных школ В. М. Глушкова [24–26;

113], М. А. Гаврилова [21], А. Д. Закревского [36], Е. Е. Евреинова и Н. В. Парангишвили, [32], и многих других известных ученых в мире. Попытка применить в построении автоматов Мили и Мура (2.8) – (2.10) схем памяти, в которых осуществля лось управление многофункциональными функциями возбуждения и функ ций выходов двоичных схем памяти, не дало ожидаемых результатов (рис. 2.8). Это связано с тем, что изменение управляющих сигналов и запо минание состояния схемы памяти в реконфигурированных вычислительных системах выполняется последовательно, что ограничивает быстродействие компонентов компьютерных систем [90].

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

Иначе обстоит дело с элементами автоматной памяти, такими как мно гофункциональные (МФСП) и многоуровневые (МУСП) схемы памяти, и ме тодами построения реконфигурируемых устройств с использованием свойств изменять структуру запоминаемых состояний МФСП и МУСП еще на «эле ментном» уровне [64].

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

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

4. МОНОФУНКЦИОНАЛЬНЫЕ ЭЛЕМЕНТАРНЫЕ СХЕМЫ ПАМЯТИ 4.1. Основные понятия В современное время в интегральной схемотехнике применяются десят ки различных триггеров в компьютерных устройствах, отличающихся свои ми функциями, схемотехнической реализацией способами записи информа ции и т. д. [125]. В основу классификации потенциальных триггеров, полу чивших в интегральной схемотехнике наибольшее распространение, положе ны два принципа: функциональный и способ записи информации [17]. При этом за базовую схему триггеров принимается одноуровневая схема RS триггера [17;

125]. Развитие базовой схемы триггеров явилось основой созда ния одноуровневых многостабильных схем памяти [17]. Триггеры являются монофункциональными автоматами, реализующих только одно отражение множества Х входных сигналов во множество Y выходных сигналов ({X} {Y}), что отождествляют состояния триггеров.

Перспективным направлением развития монофункциональных элемен тарных автоматов с памятью является создание многофункциональных. В основу построения многофункциональных структур положен принцип реали зации несколько отображений информации (не менее двух) {Y}, где fi - функциональность, определяющий пару функций пере {Х} ходов (i) и выходов (i) [90]. В этом случае коммутируются функции возбуж дения и выходов, а базовая схема памяти триггеров, которая запоминает со стояния элементарного автомата с памятью, остается монофункциональной (рис. 2.8) [90]. Широкий смысл многофункциональности заключается в воз можности использования аппаратуры при различных режимах работы и раз личных типах интерпретации [32].

Базовая схема памяти тоже может быть многофункциональной и способ ной работать в разных блоках (подмножествах) j и i своих состояний под влиянием соответствующих еj() входных сигналов, изменяя отображения информации (не менее двух) X}ej{A}, где еj - функциональность, оп ределяющий пару функций е сохранения состояния и 2 выходов или пару функций у, в1, в2, н соответствующих переходов и выходов элементарного многофункционального автомата [64]. Структура многофункциональной схемы памяти (МФСП) заключается в том, что она имеет матричную струк туру блоков состояний памяти j и i (табл. 2.1). Переходы в такой схеме па мяти происходят по двум переменным: xi(t) и ej(). Смысл многофункцио нальности базовой многофункциональной схемы памяти (МФСП) заключает ся в том, что она имеет возможность использовать альтернативные блоки j и i состояний схемы памяти, а также работать не только в детерминированном однозначному режиме при переходе из одного состояния аi в другое ак со стояние одного только блока 0 (рис. 3.3), но и в детерминированном одно значно укрупненном режиме при переходе из состояния аі блока j в другое ак состояние определенного блока i (аі j;

ак i) (3.4). Базовая многофунк циональная схема памяти (МФСП) может работать в заданном режиме при предполагаемом переходе в другое ак состояние по мере вероятности Р1 в оп ределенном блока j (рис. 3.5) и при вероятностном переходе в другое ат со стояние по мере вероятности Р2 в определенном блока і состояний схемы (рис. 3.6), а также в нечетком режиме при нечетком переходе в другое ан со стояние нечеткого подмножества QH, состоящее из определенных блоков j (рис. 3.7). Создание базовой МФСП и на ее основе многоуровневых схем па мяти (МУСП) расширяет современные основы вычислительной техники и предоставляет качественно новые возможности. Они способны повысить скорость перестройки алгоритмов функционирования компьютерных уст ройств, расширить функциональные возможности систем, увеличить про должительность существования систем на различных уровнях обработки ин формации, а также осуществить одновременную обработку общей и частич ной информации на основе иерархического принципа программного управ ления, что невозможно осуществить на компьютерных устройствах с памя тью на триггерах.

4.2. Основы моделирование компьютерных схем При моделировании схем памяти надо один и тот же класс схем (с об ратной связью – «петлями») последовательно вычислять несколько раз, ис пользуя предыдущие значения пока значение на всех узлах этого класса схем не будут совпадать друг с другом. В этом случае получаем устойчивые зна чения выходных сигналов в схемах памяти.

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

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

Сигнал х в реальных устройствах имеет значение логической единицы и значение логического нуля. Значение сигнала, которое находится в проме жутке этих двух значений (1 и 0) считается неопределенным и этому значе нию присваивается значение «0,5». Значения сигнала х представлены на рис. 4.1.

Логическая 1(1-1’) Логическая неопре деленность «0,5»

Логический 0(0’-0) Рис.4.1. Изменение значения сигнала при переходе от нулевого значения к единичному При вычислении значений в схемах памяти значения на всех узлах в мо мент t и (t+k) могут совпадать. Когда k = 1, дальнейшее вычисление значений останавливается, потому что получены все устойчивые значения.

y(t) = y(t + k) (4.1) При k 1 дальнейшее вычисление значений также останавливается, по тому что схема не имеет устойчивых значений. Когда при математическом моделировании во время устанавливающего процесса (k = 1) существуют на некоторых узлах значение сигнала «0,5», то это говорит либо о некорректно сти построения детерминированного дискретного устройства, или о появле нии на его узлах запрещенной последовательности входных сигналов [57].

Впервые методику моделирования компьютерных схем в отделе Глуш кова предложил и применил в 1962 году молодой ученый к.т.н. Мацеви тый Л.В. при разработке «Малой интегрирующей машины (МИМ)». В году на основе этой методики под руководством Мараховского Л.Ф. были разработаны программы по моделированию цифровых схем, на основе кото рых моделировались большие интегральные схемы и схемы вычислительной машины [56–57].

В настоящее время используют программу имитационного моделирова ния в электронике (Electronics Workbench), которая была разработана в году в г. Торонто (Канада) компанией Interactive Image Technologies ]43;

74].

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

Полнота системы переходов элементарного автомата определяет, что для каждой пары внутренних состояний автомата, которые сохраняются при одном сохраняющем e() входном сигнале, найдется входной сигнал х(t), ко торый переведет автомат с одного состояния в другое.

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

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

В компьютерах в настоящее время широко используют монофункцио нальные элементарные автоматы Мура (триггеры), обладающие полной сис темой переходов и выходов с двумя внутренними состояниями, которые со храняются при одном сохраняющем e() входном сигнале [125].

Структурная схема одноступенчатого RS-триггера состоит из двух логи ческих элементов И-НЕ (ИЛИ-НЕ), которые имеют по два входа: один из них связан с входным узлом триггера, а другой с выходом другого логического элемента (рис. 4.2).

Рис.4.2. Схемы RS-триггеров на элементах И-НЕ и ИЛИ-НЕ 4.4. Триггер RS-типа на элементах потенциальной системы Базовым элементарным автоматом с двумя входами и двумя выходами является RS-триггер, на основе которого проецируются триггеры D-, T, E-, DV-, JK-типа и т.п.[17;

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

По характеру работы триггеры являются асинхронные и синхронные.

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

Особенностью RS-триггера является то, что запись информации в нем осуществляется непосредственно с поступлением информационного x() (ус танавливающего) сигнала на его входы, который однозначно определяет зна чения выходных сигналов RS-триггера. Хранение состояний выходных сиг налов в схемах триггеров осуществляется при одном сохраняющем e() входном сигнале, который действует между устанавливающими входными сигналами. Функционирование RS-триггера в табличном виде изображено в табл.4. При анализе математической модели RS-триггера на элементах ИЛИ-НЕ в троичном исчислении («0», «0,5», «1») можно описать его в виде системы непосредственных связей в булевых выражениях (4.2):

Входной сигнал может менять свое значение в математической модели при переходе от «0» до «1» и наоборот, проходя значение «0,5», которое бу дем для удобства изображать звездочкой «*» [54;

56–57].

Рассмотрим работу триггера при появление на его входных узлах R и S входного слова р(Т), которое состоит из устанавливающего x(t) входного сигнала, который однозначно устанавливает значение на выходных узлах триггера, и сохраняющего e() входного сигнала, действующего между уста навливающими x(t) входными сигналами.

Таблица 4. Работа RS-триггера на элементах И-НЕ на элементах ИЛИ-НЕ _ _ _ _ S Q Q R S Q Q R 0 0 1 1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 Триггер на элементах ИЛИ-НЕ имеет следующие три устанавливающие входные сигналы: x1(t) (R = 1;

S = 1);

x2(t) (R = 1;

S = 0);

x3(t)(R = 0;

S = 1);

и один сохраняющем входной сигнал: e() (R = 0;

S = 0), с помощью которых можно рассмотреть действие трех входных слов р1(Т)= x1(t), e() (табл. 4.2.);

р2(Т)= x2(t), e() (табл. 5.3.) и р3(Т)= x3(t), e() (табл. 5.4).

Таблица 4. Входное слово р1(Т)= x1(t), e() Такты 1 2 3 4 5 R 111* S 111* Q *000** _ *000** Q Таблица 4. Входное слово р2(Т)= x2(t), e() Такты 1 2 3 4 5 R 111* S Q *0000* _ ** Q Таблица 4. Входное слово р3(Т)= x3(t), e() Такты 1 2 3 4 5 R S 111* Q ** _ * Q При рассмотрении результатов вычислений при действии входного сло ва р1(Т) (табл. 4.2.), мы видим, что устанавливающий x1(t) входной сигнал определяет на обоих выходных узлах значение 0, которое не сохраняется при появлении сохраняющего e() входного сигнала, потому что на обоих исход ных узлах триггера сигналы имеют неопределенное значение 0,5 (Q = 0,5 и Q = 0,5). Это объясняет то, что при применении слова р1(Т) триггер не имеет устойчивого выходного сигнала, а поэтому, такое входное слово для RS триггера является запрещенным при использовании. На элементах И-НЕ и на элементах ИЛИ-НЕ входное слово р1(Т) в RS-триггере запрещается при ис пользовании в детерминированных дискретных устройствах.

Считается, что для контроля работоспособности схем памяти и уст ройств компьютера необходимо резервировать аппаратуру в три раза, чтобы достоверно убедиться в ее правильной работе [44]. При соответствующем подходе при сравнении результатов входного сигнала x1(t) и выходного сиг нала у4(t), рассмотренного в автомате 4-го рода (рис. 2.16), можно автомати чески обнаружить катастрофический отказ и, тем самым, обнаружить неис правное устройство.

В литературе не описаны автоматические методы проверки работоспо собности схем памяти. А, между прочим, все триггера построены на асин хронном RS-триггере (рис. 4.2), работоспособность которого можно легко контролировать. Для этого достаточно подать на его вход устанавливающий сигнал x1(t) (R = 1;


S = 1), который на обоих его входах имеет одинаковые ак тивные значения. При этом, на его выходе появляются два пассивных значе ния ( Q 0;

Q 0 ), которые легко отличить от обычных значений триггера, так как он всегда имеет разные значения Q 0;

Q 1 или Q 1;

Q 0 на своих выхо дах. Если же при поступлении такого устанавливающего x(t) входного сигна ла на выходных узлах RS-триггера значения будут разные, то это сигнализи рует, что элемент с активным выходным сигналом работает не правильно, а следовательно и все устройство работает не правильно.

При рассмотрении результатов вычислений при воздействии входного слова р2(Т) (табл. 4.3.), Мы видим, что устанавливающий x2(t) входной сигнал определяет на выходных узлах значение Q = 0 и Q = 1, которые сохраняются при появлении сохраняющего e() входного сигнала.

При рассмотрении результатов вычислений при действии входного слова р3(Т) (табл. 4.4), Мы видим, что устанавливающий x3(t) входной сигнал опре деляет на выходных узлах значение Q = 1 и Q = 0 хранящихся при появлении сохраняющего e() входного сигнала.

Триггер считается, что находится в нуле, когда Q = 0, и в единице, когда Q = 1. Это условие необходимо запомнить, чтобы всегда было легко опреде лить состояние, в каком находится триггер.

Рис. 4.3. Граф RS-триггера в автоматном непрерывном времени Рассмотрены схемы асинхронного одноступенчатого RS-триггера. Для приема информации вводятся синхроимпульсы С и специальные дополни тельные элементы И (рис. 4.4). Наличие синхроимпульса на условном изо бражении триггера отображается входом С (рис. 4.5).

4.5. RS-триггер на элементах динамической системы В потенциальной системе элементов (рис. 4.2) организация обратной связи в схемах памяти осуществляется без разделения ее на действия такто вых сигналов [17;

54;

125]. В связи с этим при устанавливающих x(t) входных сигналах осуществляется переключение в двух группах логических элемен тов RS-триггера в период такта t, а запоминание состояния при сохраняющих е() входных сигналах элемента в период действия внутреннего такта.

В динамической четырехфазной системе элементов [54] может быть предложена базовая схема памяти (RS-триггер), ограниченная двумя группа ми элементов, в каждой из которых применен один логический элемент.

Один из этих элементов функционирует в одном подмножестве тактовых сигналов (например, Ф1 и Ф2) и запоминает выходной сигнал в период такто вых сигналов Ф3 и Ф4, а второй - в другом подмножестве тактовых сигналов (например, Ф3 и Ф4) и запоминает выходной сигнал в период тактовых сигна лов Ф1 и Ф2 (рис. 4.6).

Рис. 4.6. RS-триггер на элементах четырехфазной динамической системы элементов ИЛИ-НЕ Обобщенная система уравнений базовой схемы памяти RS-триггер на динамических элементах ИЛИ-НЕ имеет такой вид:

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

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

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

Анализируя работу динамического RS-триггера (рис.4.6), рассмотрим множество устанавливающих xi(t) входных сигналов с соответствующими тактовыми фазами (табл. 4.5).

Таблица 4. Устанавливающие наборы хi входных сигналов Для первой группы Для второй группы j Входные сигналы xi x12 x 1 z 0 z Устанавливающие наборы входных сигналов для одной группы каскадов должны иметь предварительную (опережающую) установку входных узлов по сравнению с входными сигналами второй группы в неактивный (нулевой) набор, отражены в табл. 4.5. После установки одной группы каскадов в запо минающее состояние, надо установить для первой и второй группы соответ ствующий еj() входной сигнал, при котором на входные узлы подаются ну ли.

Множество сохраняющего набора входных сигналов также разбивается на два подмножества, которые воздействуют на разные группы каскадов. При сохраняющем наборе еj входных сигналов, при котором z12 = 0 и z 2 = 1, запо минаются два устойчивых состояния триггера А1 (Q = 1 и Q = 0) и А2 (Q = 0 и Q = 1).

В динамических триггерах за один период Т наборы входных сигналов х(Т) способны установить одно из двух состояний схемы памяти RS-триггера, который способен запомнить установленное состояние в последующий пери од (Т +1) при действии сохраняющего набора е(Т +1) входных сигналов ( z12 = 0;

z 2 = 0).

Сделаем анализ работы динамического RS-триггера при воздействии на его входные узлы входного слова р(Т).

Таблица 4. Установка RS-триггера в ноль (Q = 0) при z12 = 1;

z 2 = Выходные сигналы Ф1 Ф2 Ф3 Ф4 Ф1 Ф2 Ф * 0 0 0 0 0 y * * * 1 1 1 y При установки триггера в устойчивое состояние выходные сигналы триггера нам неизвестны и поэтому при анализе схем памяти их задают, сна чала сигналы в виде звездочки "*" (см. в табл. 4.6 и 4.7).

Таблица 4. Установка RS-триггера в единицу (Q = 1) при z12 = 0;

z 2 = Выходные сигналы Ф3 Ф4 Ф1 Ф2 Ф3 Ф * * * 1 1 y * 0 0 0 0 y Анализ работы RS-триггера показывает, что все основные характеристи ки, пригодные для реализации в потенциальной системе элементов, действи тельны и для RS-триггера, реализованного на элементах динамической сис темы элементов. Но это с учетом временных соотношений входных и выход ных сигналов, запоминающих свои устойчивые значения в различных фазо вых тактах [57].

Триггеры других типов строятся на основе RS-триггера обычными мето дами структурного синтеза автоматов [17].

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

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

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

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

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

Чтобы этого не было, используют линии задержки. При длительных сигналах триггер, который имеет входных узлах сигналы J и К одновременно, пере ключается из одного состояния в другое до окончания действия сигналов на его входных узлах. Конечное состояние триггера указать невозможно. Чтобы ликвидировать эту неопределенность в схему вводят элементы задержки, продолжительность которого не менее длительности входного сигнала в са мом неблагоприятном случае. В триггерах на интегральных схемах вместо линий задержки используют второй RS-триггер и двухтактную систему син _ хроимпульсов С и C.

Синхроимпульсы С обеспечивают прием сигналов J и K (рис. 4.10), ус танавливают новое состояние в RS-триггере Т1, и запрещают в то же время передачу информации с выходов RS-триггера Т1 на RS-триггер Т2. Поэтому при С = 1 состояние RS-триггер Т2 не меняется. RS-триггер Т1 устанавливает ся в единицу Q1 = 1 при появлении на входных узлах C=J=1 (CJ=1;

Q1=1) или в ноль Q1 = 0 - при C = К = 1 (СК = 1;

Q1 = 0).

При C = 1 положение в RS-триггере Т1 не меняется, а RS-триггер Т2 при нимает состояние RS-триггер Т1, когда RS-триггер Т2 не был в том же состоя нии до этого. При С = 1 всегда должно быть Q1 = Q2, поэтому на комбинации кодовых состояний на 01 и 10 переходы запрещены.

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


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

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

Устойчивость состояний автомата можно обеспечить как схемными ме тодами, так и выбором способа кодирования состояний автомата.

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

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

Для облегчения соседнего кодирования состояний автомата можно ис пользовать диаграммы Вейча или карты Карно, где соседние ячейки отлича ются значениями только одной переменной. Разрядность кодовых состояний автомата вычисляется по формуле n = 1 + int(log2K), (4.4) К-число состояний автомата;

где int(2,5) = 2 – функция, которая выделяет только целую часть числа.

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

Устойчивость состояний автомата можно обеспечить применением двух ступенчатой памяти, в которой процесс переключения состояний разделяется во времени, за счет двухтактной синхронизации, как это сделано в двухтакт ном JK-триггере или в Т-триггере [17;

125]. Аппаратные затраты, при этом растут, а скорость работы уменьшается. Двойная память широко применяет ся в интегральных схемах устройств компьютера.

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

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

Использование элементного, группового и системного резервирования аппаратуры;

Внедрение эффективных способов эксплуатации аппаратуры, систе матическое проведение профилактических работ;

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

4.7. Методы проектирования моногостабильных схем памяти с учетом ограничения элементной базы Многостабильные схема памяти. По сравнению с триггерами много стабильные схема памяти (МСП) имеет более двух состояний [17]. Характер ной особенностью МСП является запоминание всех своих состояний при од ном сохраняющую е() входном сигнале. Эта особенность обусловлена принципом структурной организации МСП. Она заключается в том, что ис пользуются n (n 2) логических элементов ИЛИ-НЕ (И-НЕ). Выходы каждо го i-го элемента ИЛИ-НЕ (И-НЕ) соединяют со входами всех остальных ло гических элементов МСП или по определенному закону (например, с входа ми только двух, трех и т.д. из n логических элементов), а один из входов ка ждого i-го элемента соединяется с входным шиной МСП.

Принцип запоминания в схемах памяти заключается в том, что устанав ливающие х(t) входные сигналы устанавливают выходное значения активно го сигнала 1 (0) на узле одного или группы логических элементов ИЛИ-НЕ (И-НЕ). Это выходное значения активного сигнала 1 (0) через свои обратные структурные связи удерживают в инверсном состоянии 0 (1) выходные зна чения других логических элементов МСП. которые, в свою очередь, через обратные структурные связи подтверждают установленные выходные значе ния логических элементов при действии на них только одного сохраняющего е() входного сигнала, поступающего из устанавливающей входной шине во время отсутствующего синхросигнала С. В зависимости от характера соеди нения логических элементов, МСП имеет или М = n устойчивых состояний, или меньше (M n) устойчивых состояний, или не имеет вообще устойчивых состояний [17].

Структурная схема МСП, которая запоминает М (М = n) устойчивых со стояний изображена на рис. 4.11.

z1 z2 zn Рис. 4.11. Обобщенная структурная схема МСП Законы работы многостабильные схемы памяти (МСП) (рис. 4.11) анало гичные законам работы RS-триггера. Эти законы рассмотрим в табличном виде (табл. 4.8).

Таблица 4. Законы работы многостабильные схемы памяти на элементах И-НЕ z1 z2 – zn a1 a2 – an 0 1 – 1 1 0 – 1 0 – 1 0 1 – – – – – – – – – 1 1 – 0 0 0 – При поступлении только на один входной узел МСП значение активного нулевого сигнала zi(t) = 0 (а на другие - значение единичного сигнала) на со ответствующем выходе логического элемента И-НЕ появляется через время задержки э сигнал ai(t) = 1, значение которого равно логической единицы во время действия сигнала zi(t). Этой выходной единичный сигнал ai(t) за время действия сигнала zi(t) через время задержки э совместно с другими входны ми значениями устанавливает другие выходные сигналы элементов схемы памяти И-НЕ в пассивные значения логической единицы. Те, в свою очередь, через обратные структурные связи МСП поступают на логический элемента И-НЕ, на который поступал входной сигнал zi(t) и подтверждают в его вы ходном сигнале активное значение нуля. Таким образом, входной сигнал zi(t) должен быть по продолжительности не менее времени 2э для определенной устойчивости функциональной работы триггера.

Определение параметров монофункциональных схем памяти. Число М запоминающих состояний двоичных или многостабильных триггеров вы числяется по формуле [64]:

n M ( 2 1)i n, (4.5) i где n-число элементов И-НЕ (ИЛИ-НЕ) в схеме триггера или МСП.

Число rе сохраняющих е () входных сигналов двоичных или многоста бильных триггеров вычисляется по формуле [64] n re (2 1)i 1. (4.6) i Сущность метода проектирования двоичных или многостабильных триг геров, сохраняющих М (M 2) запоминающих состояний при одном е() входном сигнале, заключается в том, что сначала выбирают К-входовые эле менты И-НЕ (ИЛИ-НЕ) с нагрузочной способностью Р1, а затем используют n (2 n K;

2 n P1 ) логических элементов И-НЕ (ИЛИ-НЕ), выходы каж дого из которых соединяются соответственно с входами всех остальных эле ментов И-НЕ (ИЛИ-НЕ), один вход каждого из элементов И-НЕ (ИЛИ-НЕ) соединяем с установочной шиной Вх.Ш всей схемы памяти, а выходы всех элементов И-НЕ (ИЛИ-НЕ) соединяем с выходной шиной Вых.Ш всей схемы памяти.

Схема многостабильного триггера, построенного по этой методологии на 4-входовых логических элементах (4И-НЕ) с нагрузочной возможностью Р (Р1 = 10), отражена на рис. 4.12.

Вых. Ш z1 z2 z3 z Вх. Ш Рис. 4.12. Схема МСП на 4-входовых логических элементах Эта схема памяти имеет следующие конструктивные характеристики:

Число n логических элементов: n = 4 (2 n K;

2 n P1);

Число М запоминающих состояний: М = 4 (M = n).

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

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

· Предельная рабочая частота переключения (Fp) · Нагрузочная способность по выходам (РQ) · Число внутренних связей (Scв) · Число внешних связей (Sвc) · Число элементов на одно состояние (L) · Максимальное число альтернативных отображений (re).

Максимальное число запоминающих состояний. Однофазные много стабильные схемы памяти, построенные на К-входовых элементах И-НЕ (ИЛИ-НЕ) с нагрузочной способностью по выходам Р1, используют n (2 n K;

2 n P1) элементов [64]. Максимальное возможное число М запоми нающих состояний однофазных многостабильные схем памяти при K P1 и n=m=К определяется по формуле:

K M max ( 2 1)i K. (4.7) i Таким образом, при параметрах элементов, которые ограничены, можно не строя саму схему памяти определить ее максимальное возможное число М запоминающих состояний однофазных многостабильные схем памяти. Для расширения максимальных возможностей схем памяти необходимо расши рить ограничения элементов. Иначе, взять элементы с большим количеством входов и нагрузочной способностью или построить такие схемы за счет рас ширения (для увеличения нагрузочной способности элементов) и построения иерархических элементов (для увеличения количества входов элементов), но при этом уменьшается скорость работы элементов, которые будут иметь дли тельность задержки не., а 2э [69].

Например, при использовании элементов 8И-НЕ однофазные многоста бильные схемы памяти могут иметь восемь запоминаемых состояния (4.6).

Расширение возможностей логичных элементов для построения схем памяти показаны на рис. 4.13.

Рис. 4.13. Расширители по выходам (а) и входам (б) Предельная рабочая частота переключения (Fp).

Максимальная частота переключения триггера Fmах определяется мини мальными допустимыми временными интервалами между двумя последова тельными синхросигналами минимальной продолжительности, поступающих на входы схем памяти[64] Fmах = 1/2ср, (4.8) где ср, - средняя задержка одного логического элемента (э).

Максимальная частота появления сигналов на входах триггера определя ется интервалом времени t = 2э. Таким образом, появление нового инфор мационного сигнала допускается только после окончания переходного про цесса в триггере и переключение его в другое устойчивое состояние. Таким образом, для надежной передачи информации новый входной информацион ный (активный) сигнал схемы памяти можно использовать только после пе реходного процесса в схеме памяти. Длительность этого входного сигнала должна имеет продолжительность не менее 2э. Итак, предельная рабочая частота переключения Fp асинхронного одноуровневого триггера при дли тельности исходящего информационного (активного) сигнала равна 2э, оп ределяется по формуле:

(4.9) F p 1 / 4 э.

Максимальная частота переключения Fmах для триггера и предельная ра бочая частота переключения вычисляются по формулам (4.7) - (4.8), что ста новится понятным при рассмотрении временных отношений синхронизиро ванных сигналов (рис. 1.3), которые подаются на схему памяти.

Нагрузочная способность по выходам (РQ).

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

Параметр РQ указывает, какое число аналогичных логических элементов можно подключать к выходу устройства, не нарушая его работу на предель ной рабочей частоте. Этот параметр зависит от нагрузочной способности по выходам элемента Рэ и от числа связей выхода данного элемента Sэ с другими элементами устройства. Для однофазных многостабильных схем памяти наименьший параметр РQ определяется по формуле [64]:

PQ Pэ M max Pэ K ;

( PQ 1;

Pэ K ), (4.10) где Мmах - максимальное число запоминающих состояний схемы памяти К (К=Мmax) – число входов элементов И-НЕ (ИЛИ-НЕ).

Например, при использовании схем 4И-НЕ и 3И параметр РQ для одно фазных многостабильные схем памяти равен:

РQ Pэ - Мmах = 10 – 4 = 6.

Число внутренних связей (Scв).

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

Параметр Scв для однофазных многостабильные схем памяти определяет ся так:

Scв = n (n-1) (4.11) где n - число элементов И-НЕ (ИЛИ-НЕ), которые используются в схеме па мяти.

Число внешних связей (Sвc).

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

Для однофазной многостабильной схемы памяти параметр Sвc определя ется так:

Sвc = 2 n, (4.12) где n - число элементов И-НЕ (ИЛИ-НЕ), которые используются в схеме па мяти.

Для однофазной многостабильные схемы памяти запоминающей 6 со стояний и построенной на 6 логических элементах, параметр Sвc равен (4.12).

Число элементов на одно состояние (L).

Параметр L относится к важным характеристикам схем памяти, так как позволяет оценивать потребляемую мощность и в некоторой степени аппа ратные затраты на организацию памяти. Наиболее экономичные по аппара турным расходам считаются схемы памяти с минимальными значениями па раметра L, который определяется по формуле [64] n L, (4.13) M где n - общее число элементов схемы памяти;

M - число запоминающих состояний схемы памяти.

Для асинхронного одноуровневого RS-триггера (рис. 4.2) и всех одно фазных многостабильные триггеров (рис. 4.11, рис. 4.12) значение параметра L равно единице, потому что M = n.

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

Известны основные схемы памяти (асинхронные одноуровневые RS триггеры, однофазные многостабильные схемы памяти и другие [17;

125]).

На основе этих схем проектируются различные монофункциональные схемы памяти, преобразующие устанавливающие xi(t) входные сигналы в однознач ные аi(t) состояния схемы памяти, то есть {X} в {A}, где xi(t) Х, а аi(t) А.

Множество А состояний в таких схемах памяти запоминается при одном со храняющую е() входном сигнале, который автоматически появляется между устанавливающими xi(t) входными сигналами.

Монофункциональные схемы памяти (RS-триггеры, однофазные много стабильные схемы памяти и другие [17]) запоминают состояния аi(t) только в одном блоке. Задача однофазных многостабильные схем памяти однознач но преобразовывать устанавливающие xi(t) входные сигналы в запоминаю щие аi(Т) состояния, которые запоминаются при одном сохраняющем е() входном сигнале и принадлежат одному блоку запоминающих состояний.

Задание многостабильных схем памяти отражены в табличном виде (табл.

4.11).

Устанавливающие xi(t) входные сигналы характеризуются тем, что на входные узлы одной группы логических элементов И-НЕ (ИЛИ-НЕ), состоя щих из одного логического элемента (рис. 4.2), подается «пассивный» сиг нал, равный 1(0), а на другие элементы И-НЕ (ИЛИ-НЕ) подается «актив ный» сигнал, который равен 0(1).

Таблица 4. Задание многостабильных схем памяти хi х1 х2 хn-1 хn … е e0 a1 a2 an-1 an … При появлении устанавливающего xi(t) входного сигнала на выходных узлах одной группы элементов И-НЕ (ИЛИ-НЕ) появляется «активный» сиг нал, равный 0(1), который удерживает в инверсном состоянии выходы эле ментов И-НЕ (ИЛИ-НЕ) других групп схемы памяти. «Активные» выходные сигналы одной группы и характеризуют состояния аi схемы памяти. Состоя ния аi схемы памяти запоминаются при определенном сохраняющем е() входном сигнале.

5. СТРУКТУРНАЯ ОРГАНИЗАЦИЯ МНОГОФУНКЦИОНАЛЬ НЫХ СХЕМ ПАМЯТИ 5.1. Многофункциональные элементарные автоматы с памятью.

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

Расширим класс монофункциональных триггерных схем памяти до уровня многофункциональных за счет разработки новых принципов и мето дов структурной организации многофункциональных. Принцип структурной организации многофункциональных схем памяти (МФСП) заключается в том, что используются n логических элементов ИЛИ-НЕ (И-НЕ), которые разбиваются на m (m n) групп. Выходы элементов одной группы не связаны с входами своей группы логических элементов. Они соединяются с входами элементов других групп схемы памяти по одному из определенных законов (например, с входами всех остальных логических элементов или входами только элементов двух, трех и т.д. из m групп элементов). Один из свободных входов каждого i-го элемента соединяется с входами устанавливающей вход ной шины, а второй из свободных входов каждого i-го элемента соединяется с входами сохраняющей входной шины схем памяти.

Принцип запоминания состояний в МФСП заключается в том, что уста навливающие хi(t) входные сигналы, которые поступают на узлы устанавли вающей входной шины, однозначно устанавливают выходные значения хотя бы одного логического элемента i-ой группы. Выходные значения установ ленного элемента через свои выходные структурные связи удерживает в ин версном состоянии выходные значения других элементов схемы памяти, ко торые, в свою очередь, через обратные структурные связи подтверждают ус тановленные выходные значения логических элементов при воздействии на них одного из сохраняющих еj() наборов входных сигналов, подаваемых по сохраняющей входной шине. Эти установленные значения сохраняются.

Определение 6.1. МФСП назовем одноуровневым многофункциональ ным элементарным автоматом (МЭА) с полной системой переходов и полной системой выходов при реализации каждой из re (re 1) функций e сохране ния состояний.

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

5.2. Метод микроструктурного синтеза элементарных МФСП Рассмотрим метод микроструктурного синтеза, который позволяет по строить асинхронную МФСП класса L из логических элементов функцио нально полной системы.

Воспользуемся комбинационной схемой ИЛИ-НЕ, реализующей такую функцию:

_ y f ( a ) f ( x ) f ( e), (5.1) где f(a) - функция от произвольного входного сигнала, поступающего из вы хода элемента другой группы для запоминания состояния в МФСП;

f(х) - функция от произвольного устанавливающего хi(t) набора входного сигнала;

f(е) - функция от произвольного сберегающего еj() набора входного сигнала.



Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.