Булевский хаос

Rui Zhang, Hugo L. D. de S.Cavalcante, Zheng Gao, Daniel J. Gauthier, and Joshua E. S. Socolar

Department of Physics and Center for Nonlinear and Complex Systems, Duke University, Durham, North Carolina 27708, USA

Matthew M. Adams and Daniel P. Lathrop

Department of Physics, IPST and IREAP, University of Maryland, College Park, Maryland 20742, USA

( Оригинал статьи на английском: Boolean chaos )

В статье рассматривается детерминированный хаос, возникающий в простой цифровой схеме, состоящей из логических элементов, не тактируемых внешним сигналом. Импульсы на выходе схемы имеют сверхширокополосный спектр, в диапазоне от постоянного тока до 2 ГГц и более. Поведение схемы описывается на качественном уровне с помощью булевской модели, которая обновляется автономно. Время прохождения сигнала в модели зависит от набора предыдущих состояний элементов. Модель фильтрует короткие импульсы, наличие которых подтверждается экспериментально. Хаос в цифровых схемах может найти применение в качестве источника сверхширокополосного сигнала в радиодиапазоне.

Мы покажем, что с помощью очень простой цифровой схемы можно получить детерминированный хаос, который характеризуется широкополосным спектром и быстрым расхождением смежных траекторий. Такое поведение схемы мы будем называть «булевский хаос» и покажем, что он может быть описан моделью, где время обновления состояний определяется временем распространения сигнала. Наша схема может быть использована в защищенных широкополосных системах связи [1], для создания экономного датчика или маяка, или как основа для построения высокоскоростного генератора случайных чисел [2]. Также она может быть использована для изучения фундаментальных аспектов поведения сложных цепей.

Предлагаемая схема состоит из трех узлов, реализованных на высокоскоростных логических элементах общего применения. Выборка напряжения в любой точке схемы имеет неповторяющуюся структуру с ярко выраженными переходами булевского типа. Она демонстрирует экспоненциальную чувствительность к начальным условиям и имеет широкий спектр в диапазоне от постоянного тока до 2 ГГц и более (см. рис.1). Так как схема содержит цепи обратной связи с несоизмеримыми задержками, она спонтанно заходит в динамические состояния, где импульсы имеют минимально возможную ширину. В этом режиме незначительные изменения задержек создают хаос. Мы предполагаем, что подобное поведение будет свойственно широкому классу систем, описываемых с помощью автономных булевских цепей.

Булевские цепи изучались в различных контекстах. Для систем, которые демонстрируют поведение переключательного типа, таких, как логические схемы или генные распределительные цепи, зачастую оказывается полезным предположить, что системные переменные принимают только два значения (например «high» и «low») обновление которых задается булевскими функциями [3-6]. Детерминированные булевские модели часто включают в себя внешний процесс, например тактовый сигнал, синхронизирующий все обновления, или другое устройство, определяющее порядок обновлений для каждого из элементов. Пространство состояний таких моделей дискретно и конечно. Таким образом, у них могут быть только периодические аттракторы. С другой стороны, во многих физических или биологических системах информация распространяется между логическими элементами с задержками, которые могут быть разными для каждого из соединений [7–9]. Для того чтобы предсказать поведение таких систем, нужно точно определить моменты времени, в которые произошли смены состояний, что делает пространство состояний непрерывным. Математическое описание этих автономных булевских систем исследовано гораздо меньше, хотя известно, что они способны демонстрировать апериодическую структуру выборок, если логические элементы обладают мгновенной реакцией [10–12].

Ghil и соавторы [10-12] для изучения булевских цепей из идеальных логических элементов ввели булевские уравнения задержки (BDE). Динамика изменения состояний (называемых здесь «событиями») в цепях изучается в предположении, что логические элементы способны обрабатывать входящий сигнал сколь угодно быстро. Поведение системы в целом становится сложным, когда количество событий в единицу времени изменяется по степенному закону. Предполагается, что такое поведение характерно для широкого класса булевских цепей.

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

Топология нашей автономной булевской цепи показана на рис.1(а). Она состоит из трех узлов, каждый из которых имеет два входа и один выход, подключенный к двум другим входам. Обозначим через τ_ji (i, j=1,2,3) время, необходимое для распространения сигнала от узла i до узла j. Узлы 1 и 2 выполняют операцию «исключающего или» (XOR), а узел 3 ту же операцию только с инверсией (XNOR) как показано в таблице истинности на рис.1(а). Рассматриваемая цепь находится в неустойчивом состоянии (не имеет стабильной неподвижной точки), что и приводит к колебаниям. Суммарная задержка сигнала определяется внутренней задержкой каждого из логических элементов (XOR или XNOR) и внешней задержкой в соединительных проводах, инверторах или триггерах Шмитта. Необходимо подчеркнуть, что в системе отсутствуют тактовые импульсы, т.е. скорость обработки сигналов определяется задержкой логических элементов.

Рис. 1.

(a) Топология булевской цепи с хаосом и таблица истинности для логических операций, выполняемых узлами 1, 2 (XOR), и 3 (XNOR);

(b) развертка сигнала по времени;

Динамика нашей цепи наблюдалась с помощью активного щупа с высоким входным сопротивлением и цифрового осциллографа с полосой пропускания 8 ГГц и частотой дискретизации 40 GS/s. Рисунок 1(b) показывает типовое поведение схемы на выходе узла 2. Развертка сигнала по времени имеет сложную и неповторяющуюся структуру с четко определенными верхним и нижним значениями, которые указывают на булевское поведение схемы. Время нарастания напряжения – около 0.2 нс (что близко к пределу для логических элементов, применяемых в схеме). Минимальная, средняя и максимальная длины импульсов в хаотической последовательности – 0.2, 2.4 и 12 нс соответственно. Спектр импульсов (рис. 1c) лежит в полосе частот от нуля (постоянный ток) до ~1.3 ГГц (по уровню -10 дБ). Частотная характеристика – относительно плоская до 400 МГц и далее затухает обратно пропорционально частоте.

Мы обнаружили, что динамика цепи зависит от напряжения питания V_CC логических элементов, которое рассматривается в дальнейшем как параметр бифуркации. Эту зависимость динамики от V_CC можно объяснить тем, что все временные характеристики логических элементов такие, как переходная задержка, время нарастания и время спада и т.д. находятся в нелинейной зависимости от V_CC. Бифуркационная диаграмма цепи (Рис. 2) построена для интервала времени 1 µs на котором выходное напряжение V(t) узла 2 преобразуется в булевскую переменную x(t) при заданном V_CC следующим образом. Зададим пороговое напряжение V_CC/2, если V(t)<V_CC/2 то x(t)=0, если V(t)≥V_CC/2 то x(t)=1 как показано пунктиром на Рис. 1(b).

Таким образом, мы получаем последовательность булевских значений x(t), которая затем анализируется, чтобы определить время между соседними переходами из «low» в «high». Эти интервалы времени откладываются на бифуркационной диаграмме для каждого значения V_CC, в диапазоне от 0.9В до 3.3В с шагом 5мВ.

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

Рис. 2. Бифуркационная диаграмма булевской цепи. Стрелкой указано значение V_CC, при котором наблюдается сложное поведение, соответствующее рис. 1(b).

Признаком хаоса является экспоненциальное расхождение траекторий с примерно одинаковыми начальными условиями. На такое расхождение указывает положительная экспонента Ляпунова. Чтобы оценить наибольшую экспоненту Ляпунова предлагается следующий метод. Будем измерять напряжение на продолжительном интервале времени, а затем преобразуем его в последовательность двоичных переменных x(t). Для двух произвольных сегментов последовательности x(t), начинающихся в моменты времени t_a и t_b, определим булевское расстояние d(s) между ними как функцию времени s [11]

где T=10 нс – фиксированный параметр, а - операция XOR. На каждом интервале T, для которого d(0)< 0.01 (ln d(0)< −4.6) найдем в последовательности x(t) все пары t_a и t_b. Как правило, последовательность длиной 40 µs содержит около 3000 таких пар. После этого вычислим <ln d(s)>, где “< >” означает среднее по всем сочетающимся парам (t_a , t_b).

На рис.3(a) показаны две типовые выборки напряжений V(s+t_a) и V(s+t_b), а на рис.3(b) – соответствующие булевские переменные x(s+t_a) and x(s+t_b). При увеличении масштаба можно увидеть небольшую рассинхронизацию между этими двумя последовательностями импульсов. В выбранном масштабе она хорошо заметна после 20 нс, причем после 30 нс последовательности становятся независимыми.

Рис. 3.

(a) Типовые выборки похожих напряжений для V_CC=2.75В;

(b) Булевские переменные, соответствующие напряжениям рис.3 (a);

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

Чтобы оценить наблюдаемые результаты на качественном уровне, определим для аттрактора наибольшую экспоненту Ляпунова. Верхняя кривая на рис.3(c) имеет практически постоянный наклон (пунктирная линия) для s<20 нс и приближается к максимальному значению ln 0.5 ≈ −0.69, для которого x(s+T+t_a) и x(s+T+t_b) независимы. Будем считать, что в области постоянного наклона расхождение изначально похожих сегментов экспоненциально, т.е. ln d(s) =ln d₀+λ_abs, где λ_ab – локальная экспонента Ляпунова. Усреднение λ_ab по всем парам похожих сегментов и есть оценка наибольшей экспоненты Ляпунова λ системы. Производя поиск соседнего элемента в последовательности, как описано в [13] мы использовали булевское расстояние вместо координат задержки и обнаружили, что λ=0.16 нс⁻¹ (±0.02 нс⁻¹) указывает на хаос в цепи.

Чтобы проверить наш метод мы перевели систему в почти периодический режим (V_CC=2.35В) и повторили анализ. В результате булевское расстояние, как и ожидалось, осталось маленьким (<ln d> < −4). Более того, было установлено, что наш сигнал не порожден гипотетическим линейным нарастанием коррелированного шума. Этот вывод был сделан на основе сравнения экспериментальных данных с фиктивным сигналом, полученным перестановкой членов последовательности до тех пор, пока сохраняется ее спектр мощности и распределение вероятности [13]. Для лучшего понимания наблюдаемых результатов, рассмотрим булевские уравнения задержки [10,11]

x₁(t) = x₂(t − τ₁₂) x₃(t − τ₁₃),

x₂(t) = x₁(t − τ₂₁) x₂(t − τ₂₂),

x₃(t) = x₁(t − τ₃₁) x₃(t − τ₃₃) 1, (2)

где x_i – логическое состояние i-го узла, а «1» инвертирует переменную (NOT). Значения τ_ji приведены в нижней строке Таблицы I. Используя начальные условия x₁(t)=x₂(t)=x₃(t) = 0 при t<0, можно увидеть, что средняя скорость событий для x₁(t) (или любой другой переменной) растет по степенному закону с показателем ~2, что говорит о сложном поведении цепи, как установили Ghil и Mullhaupt [11].

Таблица I

ji	12	13	21	22	31	33
τ^r_ji(ns)	3.13	4.30	3.20	2.47	3.08	3.62
τ^f_ji(ns)	2.92	4.09	2.97	2.27	2.85	3.42

Такое нарастание скорости событий невозможно в экспериментальной системе, поскольку реальные логические элементы не могут изменять свое состояние мгновенно. Мы обнаружили, что основной причиной неидеального поведения цепи является задержка в элементах, которые формируют соединительную дугу между узлами XOR и XNOR. Задержка в самих этих узлах влияет на поведение цепи гораздо меньше. Чтобы оценить на качественном уровне неидеальность поведения каждой из соединительных дуг, мы измерили задержку распространения сигнала через нее. На основе полученных данных можно выделить три вида неидеального поведения:

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

2) Асимметрия логических состояний, которая делает задержку распространения сигнала через логический элемент зависимой от того, как меняется его логическое состояние с “low” на “ high” или наоборот [8];

3) Эффект деградации, который приводит к изменению задержки распространения событий, когда они быстро идут одно за другим [8,14].

Отметим, что эти виды неидеального поведения были предложены для булевских идеализаций электрических [14] и биологических [7,8] цепей. Это говорит о том, что изучение этих эффектов может иметь широкий круг приложений.

В нашей модели перечисленные виды неидеального поведения принимаются в расчет следующим образом. Во-первых чтобы описать эффект деградации при распространении сигнала по дуге введем новую переменную как это было сделано в [14]. . Пусть t_n – момент времени, в который событие n происходит в начале дуги, а t`_n – момент времени, в который соответствующее событие наблюдается в конце дуги. Заметим, что t_n не связано с деградацией в дуге, в то время как t`_n – связано. Определим

P_n ≡ t_n + τ^k_ji − t`_n−1, (3)

где τ^k_ji – номинальная задержка по дуге для событий нарастания (k=r) или спада (k=f). Типовое поведение задержки распространения τ^f_33,_n ≡ t`_n− t_n для событий спада как функция от P_n для дуги 3-3 показано на рис.4. Экспериментальные данные для каждой дуги были интерполированы с помощью формулы

τ^k_ji_,_n = τ^k_ji + Ae^-^BPn cos(ΩP_n + φ), (4)

где τ^k_ji, A, B, Ω, и φ – подстраиваемые параметры, а τ^k_ji_,_n – задержка распространения n-го события при по дуге ji. Минимальный интервал P_min определяется из данных как самый короткий промежутка времени на котором событие наблюдается. Единственным параметром, сильно зависящим от конкретной дуги и знака события, является τ^k_ji (см. Таблицу I). Основываясь на интерполяции данных показанной на рис. 4 мы нашли следующие значения параметров: A=1.28 нс, B=1.4 нс⁻¹, Ω=4.8 рад./с, φ =0.062 рад., и P_min=0.48 нс, которые мы собираемся использовать для всех дуг в цепи. Следующий этап нашей симуляции – решение булевских уравнений задержки (2) с заменой τ_ji на соответствующие τ^k_ji. Для каждого события мы оцениваем P_n, если P_n<P_min, текущее и предыдущее события отбрасываются. В противном случае мы подстраиваем новое значение времени перехода с помощью (4).

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

Используя полученные в симуляции последовательности вычислим <ln d> [рис. 3(c)] при начальном значении булевского расстояния d(0) < 0.001 [ln d(0) < −6.9] для которого выбираются пары. Полученное значение λ=0.10 ns⁻¹ (±0.02 ns⁻¹) говорит о том, что модифицированная модель, учитывающая неидеальное поведение логических элементов, демонстрирует детерминированный хаос. Кроме того, значения экспоненты Ляпунова, полученные экспериментальным путем и с помощью симуляции, очень близки, следовательно, модель учитывает основные свойства нашей электронной схемы. Детальное изучение каждого конкретного типа неидеального поведения выходит за рамки данной работы.

Таким образом, мы обнаружили, что последовательность смены состояний автономной булевской цепи демонстрирует детерминированный хаос. Это поведение сильно отличается от того, что наблюдается в периодически обновляемых (тактируемых) булевских сетях, для которых прогнозируется только периодическое поведение. Наше исследование может иметь важное значение для понимания других цепей, встречающихся в природе. К примеру, хаос был найден в системах дифференциальных уравнений, описывающих генные распределительные цепи [8], хотя источник хаоса не был найден. Чтобы осуществить переход к другим природным системам, нужно измерять параметры неидеальных логических элементов. Мы предполагаем, что три обнаруженные эффекта, , являются базовыми, хотя и трудными для непосредственного изучения. Также необходимы дальнейшие теоретические исследования для определения границ применимости модифицированных булевских уравнений задержки к разработке и пониманию поведения реальных цепей.

Литература:

[1] A. R. Volkovskii, L. S. Tsimring, N. F. Rulkov, and I. Langmore, Chaos 15, 033101 (2005).

[2] I. Reidler, Y. Aviad, M. Rosenbluh, and I. Kanter, Phys. Rev. Lett. 103, 024102 (2009).

[3] F. Jacob and J. Monod, J. Mol. Biol. 3, 318 (1961).

[4] F. Jacob and J. Monod, Cold Spring Harb Symp. Quant. Biol.26, 193 (1961).

[5] E. H. Davidson, The Regulatory Genome: Gene Regulatory Networks in Development and Evolution (Academic, San Diego, CA, 2006).

[6] A. Pomerance, E. Ott, M. Girvan, and W. Losert, Proc. Natl. Acad. Sci. U.S.A. 106, 8209 (2009).

[7] K. Klemm and S. Bornholdt, Phys. Rev. E 72, 055101(R) (2005).

[8] J. Norrell, B. Samuelsson, and J. E. S. Socolar, Phys. Rev. E 76, 046122 (2007).

[9] L. Glass, T. J. Perkins, J. Mason, H. T. Siegelmann, and R. Edwards, J. Stat. Phys. 121, 969 (2005).

[10] D. Dee and M. Ghil, SIAM J. Appl. Math. 44, 111 (1984).

[11] M. Ghil and A. Mullhaupt, J. Stat. Phys. 41, 125 (1985).

[12] M. Ghil, I. Zaliapin, and B. Coluzzi, Physica D 237, 2967 (2008).

[13] H. Kantz and T. Schreiber, Nonlinear Time Series Analysis (Cambridge University Press, Cambridge, England, 1997).

[14] M. J. Bellido-Diaz, J. Juan-Chico, A. J. Acosta, M. Valencia, and J. L. Huertas, IEE Proc.: Circuits Devices Syst. 147, 107 (2000).

Примечание. Если Вас заинтересовала данная статья, советуем зайти на страничку авторов: http://www.phy.duke.edu/research/photon/qelectron/proj/BooleanChaos/circuits.php . Кроме того, ниже приведена принципиальная схема, скопированная с этой страницы.

Рис. 5. Принципиальная схема

* Rui Zhang, Hugo L. D. de S.Cavalcante, Zheng Gao, Daniel J. Gauthier, Joshua E. S. Socolar, Matthew M. Adams and Daniel P. Lathrop. "Boolean Chaos". PHYSICAL REVIEW E 80, 045202(R) (2009) Перевод: А.Кушнеров, О.Калюжный.