Например, Бобцов

ЛИНЕЙНАЯ КОММУТАЦИЯ СТРУКТУРЫ ПРОСТРАНСТВА НЕЛИНЕЙНЫХ УСТРОЙСТВ РЕКУРРЕНТНОГО ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ КОДОВ

ЛИНЕЙНАЯ КОММУТАЦИЯ СТРУКТУРЫ ПРОСТРАНСТВА НЕЛИНЕЙНЫХ УСТРОЙСТВ …

5 АНАЛИЗ И СИНТЕЗ СЛОЖНЫХ СИСТЕМ

УДК [517.938+519.713/.718]:621.398
ЛИНЕЙНАЯ КОММУТАЦИЯ СТРУКТУРЫ ПРОСТРАНСТВА НЕЛИНЕЙНЫХ УСТРОЙСТВ РЕКУРРЕНТНОГО ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ КОДОВ
А.В. Ушаков, Е.С. Яицкая

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

Введение

Каноническое представление «вход–состояние–выход» произвольной двоичной динамической

системы (ДДС) задается в виде двух векторных выражений [1, 2]

x(k 1)  [x(k), u(k)] , 

(1)

y(k)  [x(k)] ,

(2)

в которых [x(k), u(k)] , [x(k)] именуются соответственно функциями перехода и выхода. Если функ-

ции перехода и выхода допускают представление в виде линейных операций умножения матрицы на вектор и суммирования [3], то система именуется линейной двоичной динамической (ЛДДС), если такой возможности нет, то соотношения (1)–(2) задают нелинейную двоичную динамическую систему (НДДС)

с вектором состояния x(k) размерности dim x(k)  n  log2n  , где n – размерность ЛДДС, которая ре-

шает аналогичную с НДДС задачу преобразования кодов, k – дискретное время, выраженное в числе тактов длительностью t .
Нетрудно видеть из (1)–(2), что любая ДДС представляет собой функциональное объединение

блока памяти (БП), который строится над двоичным

полем Галуа

GF ( p) p2

 {0;1}

на триггерах, и ком-

бинационной схемы, реализующей правила  и  . В схемотехнике современных устройств дискретной

автоматики и техники преобразования кодов и кодовых последовательностей выделяют четыре базовых типа триггеров: 1. линейный синхронный одновходовый D-триггер; 2. линейный асинхронный одновходовый T-триггер; 3. нелинейный синхронный двухвходовый JK-триггер; 4. нелинейный асинхронный двухвходовый RS-триггер [1].
Очевидно, ЛДДС при реализации БП в своем составе используют линейные триггеры, причем в основном D-типа. НДДС могут быть реализованы на триггерах любых из перечисленных выше типов. При этом триггер как конечный автомат (КА) первого порядка, реализующий автоматную логику Мура
[1], задается двумя функциями: функцией перехода вида x(k 1)  *[x(k), v* (k)] и функцией возбужде-
ния информационного входа (входов) вида v* (k)  *[x(k), x(k 1)] . Для случая нелинейных триггеров
обе функции задаются в виде дизъюнкций основных конъюнкций, что делает их аналитически нелинейными.

Аналитические представления функций перехода и функций возбуждения входов триггеров

Аналитические представления функций перехода * : x(k 1)  *[x(k), v* (k), c(k)] и возбуждения информационных входов v* (k)  *[x(k), x(k 1)] в силу[1, 4] принимают следующий вид:



для D-триггера

 D D

: x(k 1)  c (k)x(k)  c(k)vD (k)  vD (k) c(k)1 : vD (k )  x(k  1) c(k )1

;



для

T-триггера

TT

: :

x(k  vT (k)

1) 

 x(k) x(k) 

 vT (k) x(k 1)

;

50 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 4 (80)

А.В. Ушаков, Е.С. Яицкая



для

RS-триггера

 

RS RS

: :

x(k 1) vS (k) 

 vS x(k

(k)vR (k) 1)x (k);

 vR (k) vR (k) 

x(k) x (k



1)

x(k

)

;



для

JK-триггера

 JK  JK

: x(k 1)  vK (k)x(k)  vJ (k)x(k) c(k)1

.

: vJ (k)  x(k 1)x(k);vK (k)  x(k 1)x(k);с(k)  1

Функции перехода триггеров D - и T -типа показывают, что состояние перехода x(k 1) линейно

связано с исходным состоянием x(k) и с сигналом на информационном входе этих триггеров. При этом

T -триггер представляет собой D -триггер, охваченный единичной обратной связью, и, если D -триггер описывается передаточной функцией D (d )  d , то T -триггер – T (d )  d (1 d ) . Триггеры RS - и
JK -типа – нелинейные, так как их функции перехода показывают, что состояние перехода x(k 1) не-

линейно связано с исходным состоянием x(k) и с сигналами на информационных входах этих триггеров.

Все асинхронные триггеры ( T - и RS -типа) могут быть поставлены в режим синхронных, если информа-

ционные входы этих триггеров возбуждать сигналами в виде конъюнкций {c(k)vT (k)} и {c(k)vS (k)} ,
{c(k)vR (k)} . Путем сравнения таблиц истинности функций перехода триггеров можно выявить возможность
реализации одного триггера средствами другого. Таких «реализационных пар» не мало, приведем примеры некоторых из них. Так, D -триггер может быть реализован с помощью T -триггера в форме {vT (k)  vD (k)  x(k)} , RS -триггера в форме {vS (k)  vD (k);vR (k)  vD (k)} и JK -триггера с помощью
сигналов {c(k)  c(k); vJ (k)  vD (k); vK (k)  vD (k)} . В свою очередь, T -триггер может быть реализован с помощью D -триггера в формах
{vD (k)  vT (k)  x(k)} и {c(k)  vT (k);vD (k)  x (k)} , с помощью RS -триггера в форме

{vS (k)  vT (k)  x(k);vR (k)  (vT (k)  x(k))} , а также JK -триггера в форме сигналов
{c(k)  vT (k);vJ (k)  vK (k)  1} . Таким образом, триггеры обладают свойством взаимной функциональной трансформируемости.

Постановка задачи линейной коммутации структуры пространства НДДС, построенных в логике произвольных триггеров

Задача решается на примере НДДС, БП которой реализован на D -триггерах, которые представляют собой элементы задержки на интервал дискретности длительности t , т.е. на один такт, и аналити-
чески задаются передаточной функцией D (d )  d . Следует заметить, что в теории и практике ДДС возникают «пограничные» задачи, решение кото-
рых требует изменения структуры пространства [5] системы (1). К ним относятся задачи построения генераторов управляющих, тестовых и скремблирующих последовательностей, устройств управления приемом помехозащищенных кодов, помехозащитные свойства которых реализованы в режиме обнаружения искажений, а не исправления. Эти задачи сводятся к организации перехода ДДС из данного исходного состояния x(k) в требуемое состояние перехода xR (k 1) под действием некоторого служебного
сигнала коммутации uc , инициация которого порождается внешним вынуждающим сигналом vf (k) .
Постановка задачи. Осуществить переход НДДС (1) из исходного состояния x(k) в требуемое

состояние xR (k 1) с помощью служебного скалярного сигнала коммутации uc и дополнительной мат-

рицы-столбца коммутирующего входа Bс , включение которых приводит (1) к виду

xR (k 1)  [x(k), u(k)] Bcuc ,   

(3)

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

сигнала коммутации uc .

Таким образом, предметом работы являются формирование аналитических представлений матри-

цы Bc  Bc ( xR (k 1), [x(k),u(k)]) в предположении, что в (3) обеспечено выполнение равенства

uc  1 ;

(4)

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

Формирование аналитического представления для матрицы коммутирующего входа и сигнала коммутации структуры пространства состояний НДДС

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

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)

51

ЛИНЕЙНАЯ КОММУТАЦИЯ СТРУКТУРЫ ПРОСТРАНСТВА НЕЛИНЕЙНЫХ УСТРОЙСТВ …

Утверждение 1 (У.1). Если для НДДС (3) заданы вектор требуемого состояния перехода xR (k 1)

и вектор исходного состояния x(k) , а также выполняется условие (4), то матрица Bс коммутирующего

входа, с помощью которой осуществляется переход из x(k) в xR (k 1) , определяется выражением

Bc  x(k 1)  xR (k 1) ,

(5)

где x(k 1)  [x(k), u(k)] – переходное состояние в случае отсутствия сигнала коммутации.



Доказательство утверждения строится на использовании соотношения (3) в предположении за-

данных xR (k 1) , x(k) и известной функции перехода (1) с последующим разрешением (3) относительно

матрицы Bс



Определение 1 (О.1). Основной конъюнкцией &{()} набора ()  (x1, x2  xi  xn ) двоичных пере-

менных называется конъюнкция, которая на данном наборе принимает единичное значение &{()}  1 . □

Перенесем это определение с набора булевых переменных на вектор, составленный из тех же переменных.
Определение 2 (О.2). Основной конъюнкцией &{()} вектора ()  (x(k)) , составленного из эле-

ментов xi  GF (2)  0;1 , будем называть конъюнкцию, которая на данном наборе двоичных перемен-

ных, образующих вектор x(k) , принимает единичное значение &{()}  1 .



Сформулируем утверждение для сигнала коммутации uc НДДС вида (3).

Утверждение 2 (У.2). Сигнал коммутации uc для НДДС (3) может быть сформирован в виде ос-

новной конъюнкции исходного вектора состояния x(k) и сигнала vf принуждения изменения порядка

(1) состояний НДДС на (3) в силу графов канонических переходов u(k)  1 .



Доказательство. Рассмотрим НДДС (3) с введенным в нее сигналом коммутации uc . На момент коммутации (на момент начала перехода из исходного состояния x(k) ) сигнально представлены только

состояние x(k) и дополнительный внешний сигнал принуждения vf , несущий информацию об изменении порядка состояний НДДС в силу графа канонических переходов ( u(k)  1 ). Таким образом, скаляр-

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

вида uc  &{x(k), vf } .



Схема формирования сигнала коммутации для версии НДДС (3) представлена на рис. 1. При этом

решение задачи строится применительно к случаю реализации НДДС на D-триггерах в автоматной логи-

ке Мура. Представим процесс формирования матрицы-столбца входа Bс и скалярного сигнала коммута-

ции uc НДДС в виде следующего алгоритма.

u(k)

x(k 1) xR(k 1)

x(k)

[u(k),x(k)]

D

vf & uc
Bc

y(k)  [ x(k)]

Рис. 1. Схема формирования сигнала коммутации нелинейной двоичной динамической системы
(D – многомерный D-триггер;  – сумматор по модулю два)
Алгоритм 1 (А.1) 1. Задать граф и совмещенную таблицу переходов и выходов проектируемого устройства преобразо-
вания двоичных кодов (УПДК) на уровне его абстрактного представления (АП) в автоматной логике Мура. 2. Перейти от АП УПДК к представлению его в виде КА путем двоичного кодирования состояний и выходов АП, в результате чего УПДК будет представлен в виде НДДС с совмещенной таблицей переходов и выходов, записанной в кодах. 3. По совмещенной таблице переходов и выходов п.1 составить аналитические представления функций (1), (2) в булевом базисе. 4. Задать два набора векторов состояний: один из них – набор {x(k)} исходных состояний x(k) , из
которых в силу решаемой задачи требуется осуществить переход, а другой – набор {xR (k 1)} со-

52 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 4 (80)

А.В. Ушаков, Е.С. Яицкая

стояний перехода xR (k 1) , в которые требуется осуществить переход в силу решаемой задачи, организовав на этих наборах пары, задействованные в переходах.

5. Сформировать согласно утверждению У.2 набор {uc} сигналов коммутации в виде конъюнкций

uc  &{x(k), v f } .

6. Вычислить набор {Bc} матриц-столбцов коммутирующих входов Bс вида (5).

7. Составить описание полученного устройства коммутации в форме (3).

8. Осуществить проверку правильности функционирования устройства.

9. Осуществить техническую реализацию.



Пример. Рассматривается НДДС, средствами которой входная двоичная последовательность

u(k)  1(k) :11111 преобразуется в выходную управляющую последовательность

y(k) :1101000 1101000  с периодом T  7 . Решается задача конструирования УПДК, которое с помо-

щью внешнего принуждающего сигнала vf преобразует НДДС, генерировавшую управляющую последовательность с периодом T  7 в НДДС, генерирующую управляющую последовательность с периодом T  5 вида y(k) :11010 11010  , путем введения в исходную НДДС дополнительного сигнала комму-

тации uc . Для решения поставленной задачи воспользуемся алгоритмом А.1, в результате чего получим: 1. граф и таблицу переходов и выходов проектируемого УПДК на уровне его АП (рис. 2, табл. 1), а так-
же таблицу кодирования элементов алфавитов высокого уровня АП элементами двоичного поля Галуа GF (2)  {0;1} (табл. 2) и совмещенную таблицу переходов и выходов КА (табл. 3);
2. аналитические представления функций (1), (2) в булевом базисе y(k)  x1(k)x2 (k)  x1(k)x2 (k)x3 (k) ; x1(k 1)  uD1(k)   x1(k)x2 (k)x3 (k)  x1(k)x2 (k)x3 (k)  u (k)x1(k)x2 (k)x3 (k)  u(k)x1(k)x2 (k)x3 (k) ; x2 (k 1)  uD2 (k)   x1(k)x2 (k)x3 (k)  u(k)x2 (k)x3 (k)  u (k)x1(k)x2 (k)x3 (k)  u (k)x1(k)x2 (k)x3 (k) ; x3 (k 1)  uD3 (k)   u (k)x2 (k)x3 (k)  u(k)x2 (k)x3 (k)  u (k)x1(k)x2 (k)x3 (k)  u(k)x1(k)x2 (k)x3 (k) ;
3. вектор исходного состояния x(k)  x(4) , из которого требуется осуществить переход в вектор тре-

буемого состояния xR (k 1)  x(0) ; 4. сигнал коммутации согласно утверждению У.2 uc  &{x(4), vf }  x1(k)x2 (k)x3 (k)vf ;
5. матрицу-столбец коммутирующего входа Bc  x(k 1)  xR (k 1)  [101]T  [000]T  [101]T ;
6. описание полученного устройства коммутации xR1 (k  1)  uD1 (k )  Bc1uc ; xR2 (k  1)  uD1 (k )  Bc2uc ; xR3 (k  1)  uD1 (k )  Bc3uc ;
 

W2 Z1

Z1 W1

Z2 S7

S1 Z2

Z1

W2 S2

Z1 W1

Z2 λ,δ

S6 Z2
S5

Z2

S4

Z2 Z1
S3 W1
Z2

Z1 W1

W2 Z1

 

Рис. 2. Граф переходов и выходов (автоматная логика Мура): Zj, j  1, 2 – элемент алфавита Z

высокого уровня входов; Si, i  1, 7 – элемент алфавита S высокого уровня состояний;

Wj, j  1, 2 – элемент алфавита W высокого уровня выходов абстрактного представления
проектируемого устройства

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)

53

ЛИНЕЙНАЯ КОММУТАЦИЯ СТРУКТУРЫ ПРОСТРАНСТВА НЕЛИНЕЙНЫХ УСТРОЙСТВ …

z(k)   Z

w(k ) s(k)
z1 (k )

w2 (k) s1 (k )
s1(k 1)

w2 (k) s2 (k)
s2 (k 1)

w1 (k ) s3 (k)
s3 (k 1)

w2 (k) s4 (k)
s4 (k 1)

w1 (k ) s5 (k)
s5 (k 1)

w1 (k ) s6 (k)
s6 (k 1)

w1 (k ) s7 (k)
s7 (k 1)

z2 (k)

s2 (k 1)

s3 (k 1)

s4 (k 1)

s5 (k 1)

s6 (k 1) s7 (k 1) s1(k 1)

 

Таблица 1. Таблица переходов и выходов абстрактного представления

 

U  K{Z}  

Y  K{W}  

X  K{S}  

U u

 Y

y

  X x1 x2 x3

s1 0 0 0

z1   0

w1 0

s2 0 0 1

s3 0 1 0

W S s4 0 1 1

z2   1

w2 1

s5 1 0 0 s6 1 0 1

s7 1 1 0

 
Таблица 2. Таблица кодирования алфавитов абстрактного представления

 

y(k) 1 1 0 1 0 0 0

x(k) 000 001 010 011 100 101 110

u(k)

0 000 001 010 011 100 101 110 1 001 010 011 100 101 110 000

x(k 1)  {x1(k 1)x2 (k 1)x3 (k 1)}

 
Таблица 3. Таблица переходов и выходов конечного автомата
  7. проверку правильности функционирования, осуществляемую на базе гипотезы, что полученное уст-
ройство приведено в состояние x(k)  x(4)  [100]T и на его вход подается сигнал vf принуждения
изменения порядка (1) состояний НДДС на (3) в силу графов канонических переходов u(k)  1 . В

этом случае должен обеспечиваться переход из состояния x(4) в x(0) . Исходя из этого, имеем

xR1(k 1)  uD1(k)  Bc1uc  (1 0  0  0) 1  0 ; xR2 (k 1)  uD2 (k)  Bc2uc  (0  0  0  0)  0  0 ;
xR3 (k  1)  uD3 (k)  Bc3uc  (0  1 0  0) 1  0 . Таким образом, вектор требуемого состояния после коммутации структуры пространства имеет вид xR (k 1)  [000]T .
Заключение

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

Литература

1. Баранов С.И. Синтез микропрограммных автоматов. – Л.: Энергия, 1979. – 232 с. 2. Бохман Д., Постхофф Х. Двоичные динамические системы. – М.: Энергоатомиздат, 1986. – 400 с.

54 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 4 (80)

П.А. Борисов, Н.А. Поляков

3. Ушаков А.В., Яицкая Е.С. Двоичное динамическое наблюдение в задаче нелинейного формирования сигнала коммутации структуры пространства линейных устройств рекуррентного преобразования кодов // Проблемы управления и информатики. – 2012. – № 1. – С. 111–117.
4. Угрюмов Е.П. Цифровая схемотехника: Учебное пособие для вузов. – 2-е изд., перераб. и доп. – СПб: БХВ-Петербург, 2004. – 800 с.
5. Ушаков А.В., Яицкая Е.С. Анализ структуры пространства состояний линейных двоичных динамических систем на основе их рекуррентного модельного представления // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 4 (74). – С. 43–49.

Ушаков Анатолий Владимирович Яицкая Елена Сергеевна

– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, ushakov-AVG@yandex.ru
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, yaitskayaes@mail.ru

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)

55