Автоматика и телемеханика, № 6, 2022

(Институт проблем управления им. В.А. Трапезникова РАН, Москва)

ОБ УСЛОВИЯХ ПРОХОЖДЕНИЯ СИГНАЛА ЧЕРЕЗ ЦЕПЬ

АСИНХРОННЫХ ПОРОГОВЫХ ЭЛЕМЕНТОВ¹

Исследуется процесс распространения сигнала в цепи последовательно

соединенных асинхронных пороговых элементов. Асинхронность элемен-

тов проявляется в том, что они могут иметь различные длительности

переключения из пассивного состояния в активное и обратно. Элементы

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

новятся пассивными, когда внешние воздействия отсутствуют. Показано,

что при различных соотношениях длительностей переходных процессов

включения и отключения элементов длительность сигнала, проходящего

по цепи, может сохраняться, увеличиваться или уменьшаться. В послед-

нем случае сигнал через достаточно длинную цепь не проходит. Сформу-

лированы условия прохождения сигнала через цепь.

Ключевые слова: асинхронный пороговый элемент, прохождение сигнала,

переходные процессы.

DOI: 10.31857/S0005231022060095, EDN: ADFCXE

1. Введение

Настоящая статья продолжает исследования сетей из асинхронных поро-

говых элементов, начатые в [1], где элементами сети являлись биологические

нейроны, а связи соответствовали химическим взаимодействиям между ни-

ми. В [2] предложено обобщение модели [1]: в нем узлы асинхронной сети

рассматриваются как абстрактные пороговые элементы, а химические взаи-

модействия заменены многосортными сигналами. В моделях [1, 2] асинхрон-

ность возникает из-за того, что разные элементы имеют разные длительности

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

и обратно. Это приводит к конкуренции между элементами, хорошо извест-

ной в дискретной схемотехнике под названием состязаний (см., например,

[3, 4]).

В различных областях важны разные аспекты асинхронности. В дискрет-

ной схемотехнике асинхронность порождает состязания, нарушающие нор-

мальную работу схем. Поэтому в ней преобладает принудительная синхро-

низация переключений элементов. В управлении бизнесом [5] и программи-

ровании [6] асинхронный подход повышает эффективность, экономя время:

основной процесс управления запускает параллельные процессы и движется

¹ Работа выполнена при частичной финансовой поддержке Российского фонда фунда-

ментальных исследований (проект № 20-07-00190).

118

дальше, не дожидаясь их окончания. В нейробиологии активно обсуждаются

асинхронные процессы распространения сигналов и их синхронизация в нерв-

ных системах [7, 8], а также использование асинхронного программирования

для их моделирования [9-11].

В данной статье исследуется еще один аспект асинхронности: влияние со-

отношения длительностей включения и отключения элементов на прохожде-

ние сигнала по сети, даже когда элементы одинаковы, а параллельные про-

цессы отсутствуют.

Результаты, изложенные в разделах 3, 4, опубликованы в [12] без доказа-

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

в [12]; в разделе 5 впервые излагается новый метод вычисления протоколов

прохождения сигнала по цепи.

2. Основные определения и постановка задачи

Асинхронный пороговый элемент² — это элемент с несколькими входами и

одним выходом, который может находиться в двух состояниях - активном и

пассивном. В активном состоянии элемент N_i генерирует сигнал мощности d_i.

Состояние y_i(t) элемента N_i определяется значением его потенциала U_i(t),

изменяющегося в интервале Ui0 ≤ U_i(t) ≤ U_max, и порогом P_i, лежащим в том

же интервале:

{

1, если U_i(t) ≥ P_i;

(1)

y_i(t) =

иначе.

Помимо потенциала и порога, асинхронный элемент обладает другими пара-

метрами — весами w_ij входов (i - номер элемента, j - номер входа) и дву-

мя эндогенными скоростями изменения потенциала (v^0ien для пассивного и

v^1ien для активного состояния). По определению v^1ien > v^0ien. Эндогенные ско-

рости не зависят от внешних воздействий; это константы, характеризующие

конкретный элемент.

Асинхронный элемент называется реактивным, если обе его эндогенные

скорости отрицательны. Он активируется только при наличии достаточно

сильных внешних воздействий; при их отсутствии потенциал реактивного

элемента стремится к Ui0.

Элемент может интерпретироваться как логический элемент электронной

схемы или электромагнитное реле, как нейрон в искусственной или биологи-

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

В дальнейшем будут рассматриваться однородные асинхронные цепи ре-

активных элементов, т.е. сети из реактивных элементов N₁, . . . , N_n, в кото-

рых 1) выход элемента N_i соединен с единственным входом элемента Ni+1,

² Асинхронные пороговые элементы впервые были рассмотрены в [1, 2]. В [1] они назы-

вались нейронами, а в [2] — агентами.

119

Таблица 1

P U_max U₀ v^0en v^1en d

N₀

1,0

N_i

0,5

0,9

-0,8

-0,5

1,0

i = 1,...,n, и других связей нет³; 2) вход элемента N₁ и выход элемента N_n —

внешние для цепи; 3) значения параметров для любого элемента цепи одина-

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

щей параметры цепи, приведен в табл. 1. N₀ - внешний источник возбужде-

ния.

Входное воздействие будем называть сигналом. Сигнал проходит через

элемент, если через некоторое время после поступления сигнала на его вход

элемент активируется и генерирует выходной сигнал. Сигнал поступает на

вход N_i, пока активен Ni-1. Сила влияния сигнала характеризуется экзо-

генной скоростью s_i(t) изменения потенциала N_i, которая пропорциональна

мощности d входного сигнала и весу w входа: s_i(t) = kwdyi-1(t). В дальней-

шем полагаем k = 1. Суммарная скорость v_i изменения потенциала элемен-

та N_i является суммой экзогенной и эндогенной скоростей

(2)

v_i(t) = s_i(t) + v^0en = wdyi-1(t) + v^0en,

если элемент пассивен (потенциал ниже порога), и

(3)

v_i(t) = s_i(t) + v^0en = wdyi-1(t) + v^0en,

если элемент активен (потенциал выше порога).

Знак скорости означает направление изменения потенциала.

Событием в момент t называется изменение состояния любого элемен-

та цепи, а также достижение Ui0 или U_max в момент t. Событиям со-

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

на отрезки — такты. Границы тактов нумеруются натуральными числами

0, 1, 2, . . . и называются дискретными моментами времени. Такт t — это по-

луинтервал [t, t + 1], длительность которого обозначается как τ(t). Последо-

вательность событий на непрерывной временной шкале называется протоко-

лом функционирования цепи. Внешним состоянием цепи называется вектор

Y (t) = (y₁(t), . . . , y_n(t)); внутренним состоянием — вектор значений потен-

циалов элементов U(t) = (U₁(t), . . . , U_n(t)).

Функционирование сети из асинхронных элементов, т.е. его протокол, в

общем случае вычисляется алгоритмом, описанным в [2]. Для случая асин-

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

³ В [1, 2] рассматриваются многосортные широковещательные связи: сигнал определен-

ного сорта воспринимается всеми элементами, у которых есть входы, чувствительные к

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

соединяющие ровно два элемента.

120

Внешний сигнал

U_max

N₁

U₀

U_max

U₀

U_max

N₃

U₀

Рисунок

все связи имеют стандартный вид (N_i, Ni+1), а изменения потенциалов вы-

числяются по более простым формулам (2) и (3). Этот алгоритм приведен

в [12]. В разделе 5 будет приведен еще более простой алгоритм, не требую-

щий таблиц переходов и связанных с ними понятий, введенных в [2, 12].

В цепи из реактивных элементов нетривиальное поведение может возник-

нуть только в результате подачи внешнего сигнала на вход N₁ и последова-

тельной активации следующих элементов. Главная задача, которая исследу-

ется в данной работе: при каких условиях сигнал пройдет через всю цепь,

т.е. через некоторое время после подачи сигнала на вход N₁ появится сигнал

на выходе N_n?

Необходимое условие прохождения сигнала через элемент заключается в

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

ную скорость, т.е. чтобы суммарная скорость была положительной. Однако

этого условия недостаточно; нужно, чтобы сигнал длился достаточно долго,

что видно из следующего примера.

Пример 1. На рисунке представлена временная диаграмма функциони-

рования цепи, параметры которой заданы табл. 1, при длительности вход-

ного сигнала Q₀ = 4,5. Жирными линиями обозначены периоды активности

элементов. Видно, что сигнал не проходит уже через третий элемент: дли-

тельности активности N₂ недостаточно, чтобы потенциал N₃ достиг порога

и N₃ включился. Вертикальные линии соответствуют совпадающим событи-

ям: например, включение N₁ означает начало генерации сигнала, входного

для N₂, и, соответственно, начало роста потенциала N₂.

121

Рассмотрим структуру процесса функционирования элемента N_i. Цикл

включения-отключения N_i, начинающийся с подачи на его вход входного

сигнала, называется полным, если он состоит из последовательности пяти

фаз (см. график N₁ на рисунке): 1) зарядки (роста потенциала от U₀ до P ),

2) роста потенциала от P до U_max; 3) пребывания потенциала в точке U_max;

4) разрядки (уменьшения потенциала от U_max до P ); 5) падения потенциала

до U₀.

Обозначим длительности этих фаз через q1i, q2i, q3i, q4i, q5i, где i = 1, . . . ,

n - номер элемента. Фазы 1 и 2 называются полными в данном цикле, если

за ними следуют фазы 2 и 3 соответственно; фазы 4 и 5 полны, если им пред-

шествуют фазы 3 и 4 соответственно. Если цепь однородна, а фазы 1, 2, 4,

5 полны, то их длительности выражаются формулами (4)-(7), содержащими

только параметры, т.е. не зависят от конкретных элементов и времени. По-

этому индексы номеров элементов для полных фаз опущены. Длительность

фазы 3 зависит от длительности входного сигнала и для разных элементов

может быть различной. Так как скорости v^0en и v^1en отрицательны, для на-

глядности вместо v^0en и v^1en будем писать -|v^0en| и -|v^1en|. Полагаем, что U₀ = 0

иU_max -P =lP.

P -U₀

(4)

q₁ =

wd + v^0en

wd - |v^0en|

U_max - P

(5)

q₂ =

wd + v^1en

wd - |v^1en|

U_max - P

(6)

q₄ =

|v^1en|

P -U₀

(7)

q₅ =

|v^0en|

Для N₁ формулы (4) и (6) верны, только если мощность d₀ внешнего сиг-

нала равна d. Однако именно это предположение d₀ = d будет использоваться

в дальнейшем. Оно не снижает общности исследования, поскольку начиная

с выхода первого элемента по цепи в любом случае будет распространяться

сигнал мощности d. Поэтому, если входной сигнал имеет другую мощность,

полученные результаты будут верны для цепи, где N₁ является внешним ис-

точником, а сама цепь начинается с элемента N₁.

Дополнительные обозначения: Q₀ - длительность внешнего сигнала; Q_i,

i = 1,...,n, - длительность активности элемента N_i и, соответственно, дли-

тельность его выходного сигнала, t_ji - момент начала фазы j элемента N_i,

t_zi - момент падения U_i до U₀. Для внешнего сигнала обозначим через t₀₀ =

= 0 - момент его начала, tz0 - момент его окончания; t_ji,t₀₀,tz0 - точки на

временной шкале, отмечающие моменты наступления событий; последова-

тельность этих моментов на временной шкале — это протокол функциониро-

вания цепи. Некоторые события неизбежно совпадают: например, tz0 = t₄₁.

122

Для дальнейшего важно простое равенство:

(8)

Q_i = t5i - q2i.

Выходные сигналы элементов цепи (кроме элемента N_n) будем называть

внутренними. Сигнал называется длинным, если Q_i ≥ q₁ + q₂, коротким, ес-

ли q₁ < Q_i < q₁ + q₂, недостаточным, если Q_i ≤ q₁. Заметим, что а) такая

классификация сигналов зависит от параметров сети, так как величины

q₁,q₂,q4 зависят от этих параметров; б) она относится не только ко внеш-

нему сигналу, но и к внутренним сигналам цепи; в) если сигнал короткий, то

длительности фаз 2 и 4 перестают быть постоянными; их заменяют величины

q2i,q4i, которые зависят от длины входного сигнала.

Из диаграммы на рисунке видно, что внешний сигнал — длинный, вход-

ной сигнал для N₂ (длительность которого равна Q₁) — короткий, а входной

сигнал для N₃ (его длительность равна Q₂) — недостаточный.

Справедливо следующее утверждение.

Лемма 1. Если Q_i > q₁, i = 0,1,... ,n - 1, то Qi+1 = Q_i - q₁ + q4,i+1.

Действительно, согласно (8) Q_i = t5i - q2i; активация Nn+1 наступает в мо-

мент t2i + q₁ и заканчивается в момент t5i + q4,i+1. Отсюда

(9)

Qi+1 = t5i + q4,i+1 - (t2i + q₁) = Q_i - q₁ + q4,i+1.

Если входной сигнал для Ni+1 - длинный, то q4,i+1 = q₄.

Сигнал, при котором q₁ = q₄₁, будем называть равновесным. Как будет

видно из дальнейшего, равновесным может быть как длинный (если q4,i+1 =

= q₄), так и короткий сигнал.

3. Случай длинного внешнего сигнала: Q₀ > q₁ + q₂.

В этом случае

(10)

Q₀ = q₁ + q₂ + α₀, α₀

> 0,

и N₁ с момента t = q₁ + q₂ переходит в фазу 3; ее длительность q₁₃ = α₀.

При этом фазы 1, 2, 4 элемента N₁ полны, и их длительности вычисляются

по формулам (4)-(6). Определение длительностей этих фаз для следующих

элементов цепи является одной из задач данной работы. Напомним, что Q_i -

это длительность активности элемента N_i и, соответственно, длительность

входного сигнала для Ni+1.

Теорема 1. Пусть на вход цепи с заданными параметрами подан сигнал

длительности Q₀ = q₁ + q₂ + α₀, α₀ > 0. Тогда:

1. Если q₁ = q₄, то Qi+1 = Q_i, i = 1, . . . , n, т.е. сигнал пройдет по всей

цепи с сохранением длительности.

2. Если q₄ = q₁ + β, β > 0, то при каждом прохождении через элемент

сигнал удлиняется на одну и ту же величину β. Поэтому сигнал пройдет

через цепь любой длины, причем приращение длительности сигнала на вы-

ходе цепи пропорционально длине цепи.

123

3. Если q₄ = q₁ - γ, γ > 0, то существует такое натуральное число z₁,

зависящее от длительности входного сигнала, что, если длина цепи пре-

восходит z₁, то сигнал через эту цепь не пройдет. Конкретнее: найдется

такое натуральное число k, что если цепь содержит не менее k + 1 элемен-

тов, то выходной сигнал (k + 1)-го элемента будет либо недостаточным,

либо коротким. В первом случае z₁ = k + 1; во втором случае z₁ = k + l + 1,

где l > 0.

Доказательство. 1. Если q₁ = q₄, то равенство Qi+1 = Q_i, i = 1,...,n

следует из леммы 1.

2. Если q₄ = q₁ + β, то из (9) имеем Qi+1 = Q_i + β, т.е. при каждом про-

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

длительности сигнала на выходе пропорционально длине цепи.

3. Из (9) следует, что

(11)

Qi+1 = Q_i-q₁ + q₄ = Q_i - q₁ + q₁ + γ = Q_i

+ γ,

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

на одну и ту же величину γ. Однако это верно только до тех пор, пока вы-

ходной сигнал Ni+1 остается длинным, т.е. период активности Ni+1 содержит

фазу⁴ 3 и длительность фазы 4 равна q₄. В общем случае дело обстоит так:

Q₁ = q₂ +α₀ +q₄. Представим α₀ в виде α₀ = kγ +δ, где k - неотрицательное

целое, 0 ≤ δ < γ. Пока i ≤ k, Qi+1 = q₂ + α_i + q₄, где α_i = α₀ - iγ, откуда

(12)

Qk+1 = q₂ + α_k + q₄ = q₂ + α₀ - kγ + q₄ = q₂ + δ + q₄.

Заменив в (12) q₄ на q₁ - γ, получим

Qk+1 = q₂ + δ + q₁ - γ = q₁ + q₂ + δ + γ.

Поскольку δ < γ, то Qk+1 < q₁ + q₂, т.е. уже не является длинным. Для акти-

вации Nk+2 нужно, чтобы Qk+1 > q₁. Поэтому, если q₂ + δ - γ ≤ 0, выходной

сигнал Nk+1 недостаточен, Nk+1 не активируется и z = k + 1, что и требова-

лось доказать. В противном случае выходной сигнал Nk+1 - короткий. Этот

случай будет рассмотрен в следующем разделе.

Примечание. Утверждение 3 теоремы 1 предполагает фиксированную дли-

тельность входного сигнала и потому не противоречит следующему очевид-

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

длительность внешнего сигнала, что сигнал через эту цепь пройдет. Для это-

го достаточно, чтобы внешний сигнал длился до момента, когда возбудится

последний элемент цепи.

Чтобы получить формулировку теоремы в терминах параметров цепи,

нужно заменить величины q₁ и q₄ на правые части формул (4) и (6) соот-

ветственно. В частности, равенство q₁ = q₄ после такой замены и простых

преобразований принимает вид:

|v^1en| = l(wd - |v^0en|).

⁴ На рисунке уже выходной сигнал N1 является коротким для N2.

124

Пример 2. Для входного сигнала в примере 1 α₀ = 1,2. По формулам

(4)-(6) получим q₁ = 2,5, q₂ = 0,8, q₄ = 0,8, т.е. имеет место случай 3 теоре-

мы 1. Далее, γ = q₁ - q₄ = 1,7; α₀ < γ и k = 0. Q₁ = q₂ + α₀ + q₄ = 0,8 + 1,2 +

+ 0,8 = 2,8, т.е. q₁ < Q₁ < q₁ + q₂. Поэтому выходной сигнал Ni+1 = N₂ корот-

кий, что видно на рисунке. Завершение примера приведено в конце раздела 4.

4. Случай короткого внешнего сигнала: Q₀ ≤ q₁ + q₂

Из п. 3 теоремы 1 видно, что короткий сигнал может возникнуть не только

на входе N₁, но и на входе любого элемента цепи. Однако рассмотрение обще-

го случая потребовало бы слишком громоздких обозначений. Поэтому огра-

ничимся случаем внешнего короткого сигнала; рассмотрение общего случая

будет отличаться только обозначениями.

4.1. Точка равновесия

В случае короткого сигнала фаза 3 для N₁ отсутствует и

(13)

Q₀ = q₁ + ε₀,

0<ε₀ ≤q₂.

Очевидно, что q₂₁ = ε₀. Тогда

(14)

Q₁ = q₂₁ + q₄₁ = ε₀ + q₄₁.

За время q₂₁ = ε₀ потенциал N₁ вырастет на величину ΔU₂₁ ≤ lP :

(

)

(15)

ΔU₂₁ = ε₀

wd - |v^1en|

после чего внешний сигнал отключится и у N₁ начнется урезанная фаза 4.

При этом



(

)

_v1

=ε0

(16)

q₄ = ΔU₂₁/

wd - |v^1en|

/|v^1en

(

)

В дальнейшем формула

wd - |v^1en|

/|v^1en| неоднократно понадобится. По-

(

)

этому введем обозначение

wd - |v^1en|

/|v^1en| = F и перепишем (16) в виде

(16

^′)

q₄₁ = ε₀

(

)

Заметим, что 1 + F = 1 +

wd - |v^1en|

/|v^1en| = wd/|v^1en|.

Из (14) и (16^′) следует, что

(17)

Q₁ = ε₀ + q₄₁ = ε₀ + ε₀F = ε₀

(1 + F ).

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

тельности, т.е. чтобы выполнялось равенство Qi+1 = Q_i, i = 1, . . . , n, как и

в случае длинного сигнала, необходимо и достаточно выполнение равенства

q₁ = q4i. Однако если для длинного сигнала q4i = q₄, т.е. зависит только от

125

параметров цепи, то при коротком сигнале, как видно из (16^′), величина q4i

зависит еще и от длины сигнала, т.е. выполняется только при определенном

значении ε₀, которое, в свою очередь, должно удовлетворять условию (13).

Выясним теперь, при каком значении ε₀ равенство q₁ = q₄₁ выполняется.

Подставляя в него вместо q₁ и q₄₁ их выражения из формул (4) и (16^′) соот-

ветственно, получим

(

)

wd - |v^0en|

=ε₀F,

откуда

(

)

(18)

ε₀ = P/

(wd - |v^0en|

F ).

Из условия (13) получим:

(

)

(19)

0<P/

(wd - |v^0en|

F)≤q₂.

Таким образом, справедливо следующее утверждение.

Лемма 2. Для любой цепи, параметры которой удовлетворяют усло-

вию (19), существует величина ε^∗ ≤ q₂, определяемая соотношением (18),

такая, что внешний сигнал длины q₁ + ε^∗ проходит по цепи без изменения

длительности, т.е. является равновесным.

Для цепи, удовлетворяющей условию (19), момент q₁ + ε^∗ назовем точкой

равновесия.

Пример 3. Для сети с параметрами, заданными таблицей 1, условие (19)

не выполняется. Действительно, для этой сети, как было показано в кон-

це предыдущего раздела, q₄ < q₁, и, следовательно, q4i< q₁. Поэтому усло-

вие (19) для этой сети выполняться не может.

Пример 4. Для сети с параметрами, заданными табл. 2, условие (19) вы-

(

)

полняется. Для этих параметров F =

wd - |v^1en|

/|v^1en| = 1/0,6; подстановка

0,5

в (18) дает ε^∗ =

= 0,375. Поскольку по формуле (5) q₂ = 0,5, то ε^∗ < q₂.

0,8F

В дальнейшем понадобится формула

(20)

q4i/q2i

= F,

которая следует из (16^′).

Поскольку при коротком сигнале величины q2i, q4i, Q_i зависят от ε, введем

для них более подробные обозначения. Эти величины в точке равновесия

Таблица 2

P U_max U₀ v^0en v^1en d

N₀

1,6

N_i

0,5

-0,8

-0,6

1,6

1,0

126

(если она существует) обозначим как q∗21, q∗41, Q∗0, а при Q₀ = q₁ + ε₀ - x,

как qx21, qx41, Qx0. В этих обозначениях

(21)

q∗41 = q₁, q∗21 = ε^∗.

Из (20) и (21) следует

(22)

q₁ = ε^∗

Заметим, что равенство (22), предполагающее существование точки рав-

новесия и, соответственно, справедливость равенства q₁ = q4i для любого i,

следует из (16^′) и (21).

4.2. Случай, когда внешний сигнал короче равновесного

В этом случае

(23)

Qλ0 = q₁ + ε^∗ - λ, λ > 0 и qλ21 = ε^∗

− λ.

Из (20) имеем

qλ41 = (ε^∗ - λ)F = q₁ - λF; Qλ1 = qλ21 + qλ41 = q₁ + ε^∗ - λ - λF

и с учетом (23)

(24)

Qλ0 - Qλ1

= λF.

Таким образом, при прохождении через N₁ длительность сигнала уменьша-

ется на величину λF . Если эта величина больше длительности фазы 2, т.е.

qλ21 = ε^∗ - λ ≤ λF, то выходной сигнал N₁ становится недостаточным и рас-

пространение сигнала прекращается. В противном случае N₂ активируется и

генерирует выходной сигнал.

Лемма 3. Пусть на вход цепи, имеющей точку равновесия, подан корот-

кий сигнал, который короче равновесного (т.е. сигнал, при котором q₁ > q₄₁)

и который проходит через p элементов. Тогда для любого i = 1, . . . , p - 1

справедливо неравенство

(25)

Q_λi - Qλ,i+1 > Qλ,i-1 - Q_λi.

Для доказательства леммы понадобится несколько простых соотношений,

верных для любого i < p.

Во-первых, при коротком сигнале очевидно, что

(26)

qλ2,i+1 = Q_λi - q₁.

Во-вторых, так как Q_λi = qλ2i + qλ4i, то с учетом (20) имеем Q_λi = qλ2i + qλ2iF

или

(27)

Q_λi = qλ2i

(1 + F ).

Из (27) следует, что Q_λi - Qλ,i+1 = (qλ2i - qλ2,i+1)(1 + F ).

127

Поэтому для доказательства неравенства (25) достаточно доказать нера-

венство

(28)

qλ2i - qλ2,i+1 > qλ2,i-1 - qλ2i.

Используя (26), в левой части (28) заменим qλ2i и qλ2,i+1 на Qλ,i-1 - q₁ и

Q_λi - q₁ соответственно, а после сокращения q₁ воспользуемся (27). Получим

qλ2i - qλ2,i+1 = Qλ,i-1 - Q_λi = (qλ2,i-1 - qλ2i)(1 + F), откуда непосредственно

следует справедливость (28). Тем самым лемма доказана.

Из леммы 3 следует, что:

— все разности Qλ,i-1 - Q_λi положительны, так как согласно (24) Qλ0 -

-Qλ1 > 0, а в дальнейшем они только увеличиваются; иначе говоря, величи-

ны Q_λi уменьшаются с возрастающей скоростью;

— поэтому найдется такое l, что выходной сигнал элемента N_l окажется

недостаточным и не сможет активировать элемент Nl+1. Способ вычисления l

легко извлечь из доказательства леммы 3.

Теперь можно завершить доказательство п. 3 теоремы 1.

Длительность короткого выходного сигнала элемента Nk+1 имеет вид

Qk+1 = q₂ + q4,k+1. По условию п. 3 теоремы 1 параметры цепи таковы, что

q₁ > q₄. Следовательно, q₁ > q4,k+1, т.е. этот сигнал короче равновесного и

удовлетворяет условиям леммы 3. Поэтому найдется такое l, что выходной

сигнал элемента Nk+l+1 окажется недостаточным. Тем самым доказательство

теоремы 1 завершено.

Еще одно следствие леммы 3 касается цепей, для которых q₄ = q₁, но сиг-

нал — короткий. В этом случае фаза 4 будет укороченной: q₄₁ < q₄ = q₁, т.е.

сигнал короче равновесного, и согласно лемме 3 по достаточно длинной цепи

этого класса сигнал не пройдет.

4.3. Случай, когда внешний сигнал длиннее равновесного

В этом случае

(29)

Qλ0 = q₁ + ε^∗ + λ, λ > 0 и qλ21 = ε^∗

+ λ.

По лемме 2 имеем

qλ41 = (ε^∗ + λ)F = q₁ + λF; Qλ1 = qλ21 + qλ41 = q₁ + ε^∗ + λ + λF

и с учетом (29)

(30)

Qλ1 - Qλ0 = λF.⁵

⁵ Это равенство совпадает с (23) с точностью до перемены знака в левой части. Все по-

следующее доказательство леммы 4 также повторяет доказательство леммы 3 с точностью

до перемены знака.

128

Таким образом, при прохождении через N₁ длительность сигнала увеличи-

вается на величину λF . Если эта длительность больше длительности фазы 2,

то выходной сигнал N₁ становится длинным. В противном случае справед-

лива

Лемма 4. Пусть на вход цепи, имеющей точку равновесия, подан ко-

роткий сигнал, который длиннее равновесного (т.е. сигнал, длительность

которого имеет вид (29)) и который проходит через l элементов, причем

сигнал, генерируемый элементом N_l, остается коротким. Тогда для любого

i < l справедливо неравенство

(31)

Qλ,i+1 - Q_λi > Q_λi - Qλ,i+1.

Из (27) следует, что Qλ,i+1 - Q_λi = (qλ2,i+1 - qλ2i)(1 + F ).

Поэтому для доказательства неравенства (30) достаточно доказать нера-

венство

(32)

qλ2,i+1 - qλ2i > qλ2i - qλ2,i-1.

Используя (26), в левой части (33) заменим qλ2,i+1 и qλ2i на Qλ,i-1 - q₁ и

Q_λi - q₁ соответственно, а после сокращения q₁ воспользуемся (27). Получим

qλ2,i+1 - qλ2i = Q_λi - Qλ,i-1 = (qλ2i - qλ2,i-1)(1 + F), откуда непосредственно

следует справедливость (31). Тем самым лемма доказана.

Из леммы 4 следует, что:

— все разности Q_λi - Qλ,i-1 положительны, так как согласно (30) Qλ1 -

-Qλ0 > 0, а в дальнейшем они только увеличиваются; иначе говоря, величи-

ны Q_λi увеличиваются с возрастающей скоростью;

— поэтому найдется такое l, что выходной сигнал элемента N_l окажется

длинным и, следовательно, длительность фазы разрядки N_l будет равна q₄.

Так как цепь имеет точку равновесия и потому q₁ = q4i < q₄, то поведение

сигнала при его прохождении через элементы Nl+1, Nl=2, . . . описывается слу-

чаем 2 теоремы 1: при прохождении сигнала через каждый элемент сигнал

будет удлиняться на одну и ту же величину.

Способ вычисления l легко извлечь из доказательства леммы 4.

Из лемм 2, 3 и 4 непосредственно следует

Теорема 2. Для любой цепи, параметры которой удовлетворяют усло-

вию (19):

1) существует точка равновесия: такая величина ε^∗ ≤ q₂, что внешний

сигнал длительности q₁ + ε^∗ проходит по цепи без изменения длительно-

сти;

2) если сигнал длительности q₁ + ε короче равновесного, т.е. q₁ < ε < ε^∗,

то существует величина z₂ такая, что через цепь, содержащую не менее

z₂ элементов, этот сигнал не пройдет;

3) если сигнал длительности q₁ + ε длиннее равновесного, т.е. ε^∗ < ε < q₂,

то существует величина r такая, что в цепи, содержащей не менее r эле-

129

ментов, потенциал r-го элемента достигнет максимума; для r-го и после-

дующих элементов будет выполняться случай 2 теоремы 1.

Вторая половина утверждения 3 теоремы следует из того, что условие (19)

означает выполнение равенства q₁ = q4i < q₄.

4.4. Случай, когда точка равновесия отсутствует

Точка равновесия существует, если выполняется равенство q₁ = q4i. В этом

случае оно выполняется для любого i. Отсутствие точки равновесия означает,

что при любой длительности короткого сигнала, т.е. сигнала, длительность

которого имеет вид (13), равенство q₁ = q4i не выполняется ни для какого i.

Это возможно только в двух случаях: либо q4i = q₄, т.е. сигнал должен быть

длинным (п. 1 теоремы 1), либо q₁ > q₄ (п. 3 теоремы 1). Второй случай озна-

чает, что для любого короткого сигнала существует такое натуральное k, что

через цепь длины не меньше k сигнал не пройдет.

4.5. Итоговый результат

Общая картина прохождения сигнала по однородной цепи, которая следу-

ет из результатов пп. 3, 4, представлена в табл. 3, где все цепи разбиты на три

типа, для которых q₁ = q₄, q₁ < q₄, q₁ > q₄. Случаи, представленные клетка-

ми таблицы, в дальнейшем будем кодировать строкой и столбцом: например,

случай длинного сигнала для типа 1 кодируется как Т1Д, а случаи короткого

сигнала — как Т1К, Т2К1, Т2К2, Т2К3.

Таблица 3

Сигнал

Тип 1: q₁ = q₄

Тип 2: q₁ < q₄

Тип 3: q₁ > q₄

Длинный

Проходит с

Проходит с увеличением

Укорачивается;

сохранением

длительности

не проходит

длительности

при длине цепи

n<z₁

Короткий

Укорачивается;

Есть точка равновесия:

не проходит

1) равновесный сигнал прохо-

при длине цепи

дит с сохранением длительно-

n<z₃

сти;

2) сигнал короче равновесно-

го не проходит при длине це-

пи n < z₂;

3) сигнал длиннее равновес-

ного проходит с увеличением

длительности

Недостаточный Не проходит через первый элемент

Наличие в цепи неоднородных элементов существенно повышает возмож-

ности сохранения длительности внешнего сигнала. Например, если началь-

ный отрезок цепи состоит из r₁ < z₁ элементов типа 3 (см. табл. 3), то длинный

130

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

последует отрезок цепи, состоящий из элементов типа 2, то существует такое

число r₂ элементов этого отрезка (способ его вычисления можно извлечь из

доказательства п. 3 теоремы 1), что на выходе (r₁ + r₂)-го элемента длитель-

ность сигнала будет не меньше длительности внешнего сигнала.

5. Метод вычисления поведения асинхронной цепи

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

класса цепей с заданными параметрами вычислить протокол конкретной це-

пи этого класса. Здесь опишем метод вычисления протокола функциониро-

вания цепи, который опирается на два специфических свойства однородных

асинхронных цепей:

1) каждый элемент активируется не более одного раза;

2) если на входе элемента Ni+1 сигнал появился, то это произошло в мо-

мент

(33)

t1i = (i - 1)q₁ < q₄.

Равенство (33) следует из того очевидного факта, что в момент окончания

фазы 1 элемента Ni-1, т.е. его включения, на входе элемента N_i появляется

сигнал и запускается его фаза 1. Поэтому моменты t1,i-1 и t1i отстоят друг

от друга на величину q₁.

Для описания метода введем ряд новых понятий.

Статическим профилем Pr_i элемента N_i называется вектор (q₁,q₂,q₄,q₅).

Эти числа определяются параметрами элемента и вычисляются по формулам

(4)-(7). Напомним, что длина τ_i входного сигнала для N_i - это длительность

активности Ni-1, т.е. τ_i = Qi-1.

Динамический профиль P r_i(t1i) элемента Ni - это вектор P ri (t1i) =

= (t1i, t2i, t3i, t4i, t5i), который с учетом (33) можно записать как P r_i (t1i) =

= ((i - 1)q₁, t2i, t3i, t4i, t5i). Отсутствие какой-либо фазы и соответственно мо-

мента ее наступления будем обозначать знаком ∼.

Динамическим профилем цепи из n однородных элементов с заданными

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

Поскольку динамический профиль элемента привязан к временной шкале,

то динамический профиль однородной цепи однозначно соответствует вре-

менной диаграмме функционирования цепи, пример которой приведен на ри-

сунке.

Предлагаемый метод заключается в вычислении протокола функциониро-

вания цепи путем последовательного (начиная с P r_i(t₁₁)) вычисления дина-

мических профилей элементов цепи и расположения событий, содержащихся

в этих профилях, т.е. моментов t_ji(j - 1, . . . , 5; i = 1, . . . , n) на временной

шкале. Он описывается следующим образом.

Пусть заданы параметры цепи, включая число n ее элементов, и длина Q₀

входного сигнала.

131

1. Вычисляем величины q₁, q₂, q₄, q₅, F.

2. Если Qi-1 > q₁ +q₂, то сигнал длинный, переход к п. 3; если q₁ < Qi-1 <

< q₁ + q₂, то сигнал короткий, переход к п. 4; если Qi-1 < q₁, то сигнал недо-

статочный, переход к п. 5.

3. Длинный входной сигнал имеет вид Qi-1 = q₁ + q₂

+ αi-1, αi-1 > 0.

Компоненты P r_i(t1i) вычисляются следующим образом:

t1i = (i - 1)q₁;

t2i = (i - 1) q₁ + q₁ = iq₁;

t3i = t2i + q₂ = iq₁ + q₂;

t4i = t3i + αi-1 = iq₁ + q₂ + αi-1;

t5i = t4i + q₄ = iq₁ + q₂ + α_i + q₄;

t_zi = t5i + P/v^0en.

Q_i = t5i - t2i.

Если i < n, увеличиваем i на 1 и переходим к п. 2; если i = n, переходим

к п. 6.

4. Короткий входной сигнал имеет вид Qi-1 = q₁ + εi-1,

0<εi-1 ≤q₂.

t1i = (i - 1)q₁;

t2i = (i - 1) q₁ + q₁ = iq₁;

t3i = ∼;

t4i = t2i + q2i = iq₁ + εi-1;

t5i = t4i + q4i = iq₁ + εi-1 + εi-1F = iq₁ + εi-1 (1 + F) =

= iq₁ + εi-1wd/|v^1en| (см. (16)).

t_zi = t5i + P/v^0en.

Q_i = t5i - t2i.

Если i < n, увеличиваем i на 1 и переходим к п. 2; если i = n, переходим

к п. 6.

5. Недостаточный входной сигнал имеет вид Qi-1 = ω < q₁.

t1i = (i - 1)q₁;

t2i = t3i = t4i = ∼;

t5i = (i - 1) q₁ + ω;

t_zi = t5i + ω(wd - |v^0en|)/|v^0en| (вычисляется аналогично (16)).

Переходим к п. 6.

6. Упорядочиваем вычисленное множество чисел {t_ji} по возрастанию.

7. Конец алгоритма.

132

Для проверки вычислений полезно отметить, что некоторые события

должны совпадать. В частности, t2,i-1 = t1i, t5,i-1 = t4i.

Пример 5. Вычислим этим методом протокол цепи, заданной табл. 1.

Для этой цепи

q₁ = 2,5; q₂ = 0,8; q₄ = 0,8;= 2,5; q₅ = 0,625.

(

)

wd - |v^1en|

0,5

F =

= 1.

|v^1en|

0,5

Если длительность входного сигнала равна 4,5, то

q₃₁ = Q₀ - q₁ - q₂ = 4,5 - 2,5 - 0,8 = 1,2;

Q₁ = q₂ + q₃₁ + q₄ = 0,8 + 1,2 + 0,8 = 2,8.

Q₁ < q₁ + q₂ = 2,5 + 0,8, поэтому сигнал для N₂

будет коротким.

Вычислим динамические профили элементов.

1. Для N₁: i = 1.

Q₀ = 4,5 = q₁ + q₂ + 1,2. Сигнал длинный и α₀ =

1,2.

t₁₁ = (i - 1) q₁ = 0;

t₂₁ = (i - 1) q₁ + q₁ = q₁ = 2,5;

t₃₁ = t₂₁ + q₂ = 2,5 + q₂ = 3,3;

t₄₁ = t₃₁ + α₀ = 3,3 + α₀ = 4,5;

t₅₁ = t₄₁ + q₄ = 4,5 + 0,8 = 5,3;

0,5

tz1 = t₅₁ +

= 5,3 +

= 5,925.

|v^0en|

0,8

Q₁ = t₅₁ - t₂₁ = 2,8;

Pr1 (t₁₁) = (0; 2,5; 3,3; 4,5; 4,5; 5,3).

2. Для N₂ : i = 2.

Q₁ = 2,8 = q₁ + 0,3. Сигнал короткий и ε₁ = q₂₂ = 0,3.

t₁₂ = (i - 1) q₁ = 2,5;

t₂₂ = (i - 1) q₁ + q₁ = 2q₁ = 5,0;

t₃₂ = ∼;

t₄₂ = t₂₂ + q₂₂ = t₂₂ + ε₁ = 5,3;

t₅₂ = t₄₂ + q₄₂ = 5,3 + ε₁F = 5,6;

0,5

tz2 = t₅₂ +

= 5,6 +

= 6,225.

|v^0en|

0,8

Q₂ = t₅₂ - t₂₂ = 5,6 - 5,0 = 0,6. Q₂ < q₁; сигнал недостаточный.

133

3. Для N₃ : i = 3.

t₁₃ = (i - 1)q₁ = 5,0;

t₂₃ = t₃₃ = q₄₃ = ∼;

t₅₃ = t₁₃ = Q₂ = 5,0 + 0,6 = 5,6.

wd - |v^0en|

0,2

tz3 = t₅₃ + Q₂

= 5,6 + 0,6 ·

= 5,75.

|v^0en|

0,8

На этом вычисление динамических профилей заканчивается. Представим

их в виде табл. 4:

Таблица 4

Элемент t1i t2i t3i t4i t5i t_zi

N₁

2,5

3,3

4.5

5,3

5,925

N₂

2,5

5,0

5,3

5,6

6,225

N₃

5,0

5,6

5,75

Расположение событий на единой шкале времени представлено в табл. 5.

Таблица 5

События t₁₁ t₂₁, t₁₂ t₃₁ t₄₁ t₂₂, t₃₁ t₅₁, t₄₂ t₅₂ tz1

tz2

tz3

Значения

2,5

3,3

4,5

5,0

5,3

5,6

5,925

6,225

5,75

6. Заключение

Естественным продолжением этого исследования является рассмотрение

сетей произвольной топологии.

Полученные результаты можно использовать в нейробиологии при анали-

зе распространения сигналов в нервных системах [1, 8, 13], в исследованиях

распространения влияний в социальных сетях [14, 15], а также в пороговых

моделях социального поведения [16-20].

СПИСОК ЛИТЕРАТУРЫ

1. Кузнецов О.П., Базенков Н.И., Болдышев Б.А. и др. Асинхронная дискретная

модель химических взаимодействий в простых нейронных системах // Искус-

ственный интеллект и принятие решений. 2018. № 2. С. 3-20.

2. Кузнецов О.П. Асинхронные многосортные системы // АиТ. 2021. № 2. С. 132-

148.

3. Brzozowski J.A. Topics in Asynchronous Circuit Theory // Recent Advances Formal

Languages Appl. 2006. V. 25. P. 11-42.

134

Sparsø J. Introduction to Asynchronous Circuit Design. TU of Denmark, 2020.

Chandy K.M. Event-Driven Applications: Costs, Benefits and Design Approaches.

California Institute of Technology, 2006.

Davies Alex. Async in C# 5.0. O’Reilly, 2012.

Buzsáki G. Neural Syntax: Cell Assemblies, Synapsembles, and Readers // Neuron.

2010. V. 68. No. 3. P. 362-385.

Feinerman O., Segal M., Moses E. Signal Propagation Along Unidimensional Neu-

ronal Networks // J. Neurophysiolog. 2005. V. 94. No. 5. P. 3406-3416.

D’Haene M., Schrauwen B., Van Campenhout J., Stroobandt D. Accelerating Event-

Driven Simulation of Spiking Neurons with Multiple Synaptic Time Constants //

Neural Comput. 2008. V. 21. P. 1068-1099.

https://doi.org/10.1162/neco.2008.02-08-707

10.

Naveros F., Garrido J.A., Carrillo R.R., Ros E., Luque N.R. Event- and Time-

Driven Techniques Using Parallel CPU-GPU Co-processing for Spiking Neural Net-

works // Frontiers Neuroinform. 2017. V. 11. Article 7. P. 1-22.

11.

Pecevski D., Kappeland D., Jonke Z. Nevesim: Event-Driven Neural Simulation

Framework with a Python Interface // Frontiers Neuroinform. 2014. V. 8. P. 70.

12.

Kuznetsov O.P. Signal Spreading Through a Chain of Asynchronous Threshold El-

ements // Lecture Notes in Networks and Systems. Proceedings of the Fifth In-

ternational Scientific Conference “Intelligent Information Technologies for Industry”

(IITI’21). 2021. V. 330. P. 24-34.

13.

Николас Дж., Мартин Р., Валлас Б., Фукс П. От нейрона к мозгу. Пер. с англ.

Изд. 5-е, стереотип. М.: УРСС: ЛЕНАНД, 2019.

14.

Jackson M.O. Social and Economic Networks. Prinston Univer. Press, 2008.

15.

Kempe D., Kleinberg J., Tardos E. Maximizing the Spread of Influence through a

Social Network // Theory of Computing. 2015. V. 11. No. 4. P. 105-147.

16.

Schelling T. Dynamic Models of Segregation // J. Math. Sociol. 1971. V. 1. P. 143-

186.

17.

Granovetter M.S. Threshold Models of Collective Behavior // Amer. J. Sociolog.

1978. V. 83. No. 6. P. 1420-1443.

18.

Li Z., Tang X. A Study of Collective Action Threshold Model Based on Utility

and Psychological Theories // Lecture Notes in Computer Science. 2012. V. 7669.

P. 474-482.

19.

Бреер В.В. “Модели толерантного порогового поведения (от Т. Шеллинга -

к М. Грановеттеру)” // Проблемы управления. 2016. № 1. P. 11-20.

20.

Zhilyakova L., Gubanov D. Double-Threshold Model of the Activity Spreading in a

Social Network: The Case of Two Types of Opposite Activities // Proceedings of

the 11th IEEE International Conference on Application of Information and Commu-

nication Technologies AICT2017. 2017. V. 2. P. 267-270.

Статья представлена к публикации членом редколлегии Д.Е. Пальчуновым.

Поступила в редакцию 08.12.2021

После доработки 10.01.2022

Принята к публикации 26.01.2022

135