WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 16 | 17 || 19 | 20 |   ...   | 24 |

Для решения поставленной задачи в силу А3.2 осуществляем:

1. Кодирование в силу (3.4) элементов алфавита S состояния АА при образующем многочлене g( x)= x + 1, полученным в соответствии с п.1 алгоритма 1.11, дает кодовые вектора xГДДС состояния ГДДС – представленные в таблице 3.1.

u y {x1} u y u {x2} u u y u {x3} Рисунок 3.2. Диаграмма переходов и выхода исходного устройства Таблица 3.~ {S} {X} xНДДС i,i =1,n xi,i =1,n xНДДС xГДДС =[xНДДС ~ ] s1 x1 [00 0] 00 s2 x2 [01 1] 01 s3 x3 [10 1] 10 2. Осуществление модификации правил, в форме (3.5) – (3.7), приводит к представлению правила в форме таблица 3. Таблица 3. Вектор xT (k) состояния Вход u 000 011 0 000 000 1 011 101 T xT (k + 1)= ([ x(k), u(k)]) Таблица 3.Выход Вектор xT (k) состояния Вход u КА 000 011 y – 0 0 (k)= [ x(k), u(k)] и правила – в форме таблица 3.3. Указанные действия приводят к графу рисунок 3.3 переходов и выхода ГДДС.

{s1} {s2} {s3} Рисунок 3.3. Диаграмма переходов и выхода ГДДС 3. Выбор типа триггера, приводящий к использованию Dтриггеров, дает в силу таблиц 3.2, 3.3 булевы функции µi, i = 1,dim xГДДС возбуждения их информационного входа i вида µ1 = u( x1x2 x1x2 )= u( x1 x2 ), µ2 = u x1x2, µ3 = u( x1x2 x1x2 )= u( x1 x2 )= v1.

5.Конструирование булевой функции формирования выхода ГДДС, которое дает аналитическое представление y = x1x2.

Полученное булево описание ГДДС является аналитической базой для построения схемотехнической реализации устройства.

Примечание 3.1 (ПМ3.1). Следует заметить, что реализация корректирующей способности в рассмотренном примере 3.1 для случая использования автоматной Мили осуществляется посредством формирования синдрома E сбоя в кодах вектора состояния ГДДС с помощью БФ E = y x1, в свою очередь для ГДДС, использующей автоматную логику Мура, синдром формируется в силу БФ E = x3 x2 x1.

Примечание 3.2 (ПМ3.2). С использованием аппарата селлерсовского дифференцирования нетрудно убедиться, что в рамках примера 3.1 при составлении соответствующих БФ возбуждения информаци онных входов D-триггеров µi, i = 1,dim xГДДС как функций четырех аргументов {u,x1,x2,x3} происходит их минимизация склеиванием термов по переменной x3, что приводит БФ к функции трех аргументов {u,x1,x2}.

В заключение рассмотрим ситуацию, когда кодовое пространство оказывается вырожденным, что имеет место в силу определения 3.при выполнении условия nн = nл. Охарактеризуем ситуацию следующими постулатами.

Постулат 3.1 (ПС.3.1). Задача кодопреобразования, решаемая средствами ЛДДС, векторно-матричное описание которой имеет (n n)-матрицу A состояния с характеристическим неприводимым полиномом D()= det(I + A), принадлежащим показателю µ = 2n - 1, характеризуется минимальной размерностью вектора состояния на множестве линейных ДДС, формирующих на своем выходе периодическую последовательность периода T = µ.

Постулат 3.2 (ПС.3.2). Задача кодопреобразования, формализуемая на уровне абстрактного автомата в виде графа переходов, образующего замкнутый цикл с числом состояний nS, равным 2n - 1, и решаемая средствами НДДС-КА, характеризуется размерностью nг = nн = E{ log2 nS}= n вектора состояния этой ДДС.

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

Утверждение 3.1 (У.3.1). Для того чтобы сконструировать НДДС с минимальной размерностью n вектора состояния и сложностью КСХ, генерирующую произвольную кодовую последовательность максимального периода T = 2n - 1 достаточно на этапе перехода от формализованной в форме АА версии устройства к его версии в форме КА осуществить кодирование алфавита состояния АА так, чтобы в качестве кодов были использованы коды, получаемые в силу соотношения (1.209) вида x(k + 1)= Aq x(0), x(0) O, q [1,2n - 1], в котором матрица A имеет характеристический неприводимый полиномом D()= det(I + A), принадлежащий показателю µ = 2n - 1 так, что Aµ = I, а также в качестве ячеек памяти НДДС были использованы D-триггеры, при этом степень q и номер кодируемого состояния АА должны быть согласованы.

Проиллюстрируем на примере положения утверждения 3.1.

Пример 3.2 (Пр3.2) Требуется сконструировать автономную (u(k) 0 ) НДДС при условии минимальной сложности ее технической реализации, которая генерирует скремблирующую [28, 33] периодическую последовательность с периодом T = 15, имеющую вид y(k)= y(k + T )= 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 В соответствии с утверждением 3.1 выбираем в качестве характеристического полинома D()= det(I + A) матрицы A неприводимый многочлен степени n = 4 D()= 4 + 3 + 1, который принадлежит показателю µ = 15.

Матрицу A зададим в сопровождающей выбранный характеристический полином форме:

0 1 0 0 0 1 A =.

0 0 0 1 0 0 Зададим матрицу выхода ЛДДС в форме C = [1 0 0 0], матрицу входа B не задается так, как задача решается в классе автономных представлений.

Дальнейшее конструирование НДДС осуществим в три этапа. На первом этапе воспользуемся моделью x(k + 1)= A x(k); y(k)= C x(k) и сформируем таблицу 3.4 переходов и выхода устройства.

Таблица 3.Выход y(k) устройства 0 0 0 0 0 0 0 Вход Вектор xT (k) состояния u 0000 0001 0010 0011 0100 0101 0110 0 0000 0011 0100 0111 1000 1011 1100 T xT (k + 1)= ( A x(k)) Таблица 3.4 (продолжение) Выход y(k) устройства 1 1 1 1 1 1 1 Вход Вектор xT (k) состояния u 1000 1001 1010 1011 1100 1101 1110 0 0001 0010 0101 0110 1001 1010 1101 T xT (k + 1)= ( A x(k)) На втором этапе положим, что устройство запускается с исходным соT стоянием x( 0 ) = [10 0 0].

На третьем этапе с использованием полученных результатов формируем таблицу 3.5 переходов и выхода НДДС для условия u(k)= 0 и T исходного состояния x( 0 ) = [10 0 0], в которое НДДС можно перевесT ти из нулевого начального состояния x(0)= [0000] с помощью сигнала начальной установки u = x1x2x3x4, подаваемый на вход первого триггера.

Таблица 3.Выход y(k) устройства 1 0 0 0 1 1 1 Вход Вектор xT (k) состояния u 1000 0001 0011 0111 1111 1110 1101 0 0001 0011 0111 1111 1110 1101 1010 T xT (k + 1)= ([ x(k), u(k)]) Таблица 3.5(продолжение) Выход y(k) устройства 0 1 0 1 1 0 Вход Вектор xT (k) состояния u 0101 1011 0110 1100 1001 0010 – 1011 0110 1100 1001 0010 0100 T xT (k + 1)= ([ x(k), u(k)]) Восстанавливаем граф переходов и выхода НДДС, который с учетом таблицы 3.5 принимает вид рисунок 3.4. В силу У3.1 для реализации ячеек памяти устройства будем использовать D-триггеры. Тогда булевы функции возбуждения информационных входов vi, i = 1,4 этих триггеров и формирования выхода y устройства при движении по заданному в постановочной части примера циклу примут вид:

µ1 = x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 x3 x4 ;

µ2 = x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 ;

µ3 = x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 ;

µ4 = x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 ;

y = x1.

С учетом сигнала u начальной установки НДДС функция возбуждения первого триггера принимает вид ~ µ1 = x1x2 x3 x4 ( x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 ).

{s0} u = x1x2x3x/0000/ {s1} y =/1000/ y = {s15} {s2} /0100/ y = 0 /0001/ y ={s14} {s3} /0010/ /0011/ y =y ={s13} {s4} /1001/ /0111/ y = y ={s12} /1100/ {s5} /1111/ y =y = {s11} {s6} /0110/ /1110/ y =y ={s10} {s7} /1011/ y = /1101/ y = {s9} y = {s8} /0101/ /1010/ Рисунок 3.4. Диаграмма переходов и выхода ГДДС Приведем теперь с использованием положений теоремы 2.1 представления полученных БФ аналитического описания НДДС к форме полиномов (2.94) Жегалкина, в результате чего получим:

µ1 µ1 = x2 ; µ2 µ2 = x3 ; µ3 µ3 = x4 ; µ4 µ4 = x1 + x4 ;

y = x1.

Если теперь составить БФ µi, i = 1,4 возбуждения информационных входов vi, i = 1,4 D-триггеров для модели x(k + 1)= Ax(k) с полученной матрицей A вида 0 1 0 0 0 1 A =, 0 0 0 1 0 0 то получим тождества µ1 µ1 µ1 ; µ2 µ2 µ2 ; µ3 µ3 µ3 ; µ4 µ4 µ4. Так как матрица выхода имеет вид C = [1 0 0 0], то для БФ y, формирующей в силу матрицы C выход устройства, можно записать, что y y = x1.

Построим теперь реализацию конструируемой ГДДС в структурной форме рисунок 3.5.

u Рисунок 3.5. Структурное представление ГДДС В силу вырожденности кодового пространства, а также однотипности выбранных элементов памяти в форме D-триггеров, с учетом использования правила кодирования состояний синтез ЛДДС и НДДС дал одно и то же решение в форме структурной схемы, приведенной на рисунке 3.5.

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

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

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

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

Гипотеза 3.1 (Г3.1). Коммутационная способность комбинационной схемы ДДС, представленной булевыми функциями µi( x,u), i = 1,n возбуждения, количественно оценивается показателем n n 2n µi ( 2.86 ) n n m= = µi, (3.9) P xk i=1 k =1 j=1 i=1 k = xk j выраженным в числе кодовых переходов, на которых ДДС осуществляет требуемое кодопреобразование, где n – число переменных xk со µi стояния x = col{xk, k = 1,n} ДДС, – значение первой частной xk j селлерсовской производной БФ µi( x,u), i = 1,n возбуждения информа ционного входа i -го триггера по переменной xk на j -м кодовом наборе, составляющим алфавит состояния X представления НДДС в форме КА в виде кортежа (2.5).

Величина (3.9), как нетрудно заметить, характеризует совокупную величину коммутационной способности КСХ произвольной ДДС.

В силу О3.5 и положений Г3.1 можно сказать, что коммутационная способность КСХ, представленной БФ µi( x,u), i = 1,n возбуждения, обнаруживает, что аргументы указанных БФ оказываются «разновостребованными» на кодовых переходах, на которых эти БФ изменяют свое значение. В связи с тем, что БФ µi( x,u), i = 1,n имеют своими аргументами переменные xi, i = 1,n состояния и переменные u, = 1,r входа, то решение задачи будем проводить в два этапа: при рассмотрении ДДС как автономной системы, в которой u = 0, = 1,r, и при рассмотрении общего случая, при котором u 0, = 1,r.

Рассмотрим первый этап решения задачи (случай автономной ДДС, для которой u = 0, j = 1,r ), для чего введем следующие понятия.

j Определение 3.6 (О3.6). Под абсолютной оценкой востребованности r булевой переменной xi произвольной автономной ДДС, то есть такой ДДС, функционирование которой определяется только переменными xk, k = 1,n ее состояния, будем понимать величину n 2n µi ( 2.86 ) n r= = µi : n

xk Определение 3.7 (О3.7). Под относительной оценкой приведенной востребованности [r] (ОПВ) булевой переменной xi произвольной автономной ДДС будем понимать величину n 2n n 1 µi ( 2.86 ) [r]= = µi : 2-n

Определение 3.8 (О3.8). Обобщенной относительной оценкой при веденной востребованности булевой переменной xi произвольной [r] ДДС будем называть величину, имеющую два эквивалентных представления:

n 2m 1 µi [r] = + m2m xk k=1 j= j r 2m µi +, m = n + r, (3.12а) uk k=1 j= j n r [r] = µi + P µi, m = n + r (3.12б) P m2m xk k=1 k=uk где uk, k = 1,r – булевы переменные входа ДДС.

Нетрудно видеть, что введенные О3.7 и О3.8 дают количественную оценку востребованности соответствующих булевых переменных в процедуру динамического кодопреобразования, при этом оценка вычисляется с приведением ее к мощности полного множества кодовых переходов ДДС так, что для выражения (3.10) она определяется нормирующим коэффициентом =, (3.13) авт n 2n а для выражений (3.12а), (3.12б) – нормирующим коэффициентом =. (3.14) пр m2m Разница в коэффициентах обуславливается тем, что значения переменных uk, k = 1,r входа ДДС на кодовых переходах не формируются непосредственно средой ДДС так, как формируются значения переменных состояния посредством БФ µi( x,u), i = 1,n возбуждения (2.12), а лишь принимают участие в процедуре кодопреобразования.

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

Pages:     | 1 |   ...   | 16 | 17 || 19 | 20 |   ...   | 24 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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