Boolean Delay Equations

1. Boolean Delay Equations
2. Numerical Solution
3. Memory Effects


1. Boolean Delay Equations

The natural framework to model autonomously updated Boolean systems is the Boolean Delay Equations (BDE). It expresses the evolution of n Boolean variables xi as functions of the values of those variables at past times:

(1) x1(t)  =  f1(t, x1(t-τ11), x2(t-τ12), … , xn(t-τ1n))
(2) x2(t)  =  f2(t, x1(t-τ12), x2(t-τ22), … , xn(t-τ2n))
     ⋮
(3) xn(t)  =  fn(t, x1(t-τn1), x2(t-τn2), …  xn(t-τnn))

where the functions fi are Boolean valued and the time delays τij are positive real constants.

To illustrate the rich behavior that may be described in this framework, let us assume that the functions fi are autonomous (don't depend explicitly on time) and linear, which in the definition given by Ghil and collaborators [4] means
(4) fi(x1(t1), x2(t2), …  xn(tn))  =  ci0   ⊕ ∑nj = 1   cij xj (tj ),
where the symbol ⊕ stands for the XOR operation, and the sum is the addition modulo 2, which also corresponds to the XOR, the constants are either zero or one, and the terms ⊕ 1 correspond to a possible negation of the logic state ( NOT(y) = y ⊕ 1).

The simplest case is the XOR element with two delayed inputs:
(5) x(t)  =  x(t1) ⊕ x(t2),
which may be represented diagrammatically as in the figure:
Fig. 1: Diagram for the XOR with two delays.

 

Without loss of generality, assume τ2 > τ1. In order to calculate the evolution, starting at time t = 0, we need to specify an initial condition given by x(t), t ∈ [-τ2, 0]. Notice that, unless the two inputs change at the same time, every change in the logic state (here called transition, kink or jump) of the input causes a transition in the output of the XOR logic function. Thus, we can work with a discrete set of transition times, instead of the values of x(t) in continuous time. We can calculate for which times a transition present in the initial condition is going to cause a transition at the output. If necessary, the value of x(t) can be recovered from its initial value and the parity of the number of transitions. The initial condition with x(t) ≡ 0 does not have any transitions, and thus, is a fixed point of the evolution. If we assume as initial condition x(t) ≡ 1 for t ∈ [-τ2, -τ1] and x(t) ≡ 0 for t ∈ [-τ1, 0], the single transition at t = -τ1 will cause a transition from 0 to 1 in the value of x at t = 0, another from 1 to 0 at time t = min(τ21, τ1), and so on. Another choice of initial conditions is to start with x(t) ≡ 1 for all negative times, and let the first transition take place at t = 0. although this latter initial condition does not satisfy the evolution equation for negative times, it is physically justified for systems that are initialized with constant inputs, as in electronic circuits. It is also commonly used in the literature [4,5,6].

To calculate a trajectory, we construct a queue of the times tm, at which transitions occur. When t1 is the earliest time in the queue it is processed, generating two possible transitions at times t1 + τ1 and t1 + τ2. These transition candidates are then compared to every transition in the queue. If any transition tk has the same value as one candidate, that specific transition is removed from the queue and the candidate is discarded. We call this phenomenon a collision between tk and the tentative transition t1 + τ1 or t1 + τ2. If one of the candidates does not collide with any transitions in the queue, the candidate is added to the queue and the transition t1 from which it originated is saved on a record of transitions that actually occur and removed from the processing queue. We take the next value from the queue and repeat the process until the desired time or number of transitions is reached.


2. Numerical Solution

The above algorithm is implemented below, using the Python interpreted language (version 2.x), which is very similar to a pseudo-code description or a Matlab or Mathematica script. The code uses the decimal module to calculate fixed point arithmetic in base 10 with arbitrary, user-specified precision. (Right click here and choose "save link as" to download the code as a text file).



""" Calculates the transition times for the XOR with two delays with arbitrary precision """

#imports
from decimal import *
import os 

#constants
Prec = 12           # number of decimal places
getcontext().prec=Prec
iterations = 1000   # counts the number of transitions
Verbose_level = 1   # 1 = normal messages, 2 = debug mode, 0 = silent mode
# tau1 = 1
tau1 = Decimal(1)
# tau2 = 1/phi , the golden ratio
tau2 = Decimal(2)/(Decimal(1)+Decimal(5).sqrt())
# Minimum allowed pulse width
w_min = Decimal("0.000")
# choices of initial conditions:
#ic = Decimal(0)
ic = -tau2
#tn = [ic-max(tau1,tau2),ic-min(tau1,tau2),ic]
tn = [ic]           # list of transitions


# The programs starts here:
# open outputfile
f = open("xor_2delays_"+str(Prec)+"digits.dat",'wt')
if Verbose_level>0: print "output file: ", "xor_2delays_"+str(Prec)+"digits.dat"
f.write("#tau1 = %s, tau2 = %s\n" % (str(float(tau1)), str(float(tau2))) )
f.write("#Prec = %d, iterations = %d\n" % (Prec, iterations) )


# main loop:
for i in range(iterations):
    collided1 = False
    collided2 = False
    # calculates the two candidates of future transitions from the first tn 
    # using tn[0], instead of min(tn), could be faster 
    next_t_candidate_1 = min(tn)+min(tau1,tau2)
    next_t_candidate_2 = min(tn)+max(tau1,tau2)
    if Verbose_level>1:            # optionally prints debug information     #
      print "Processing ", min(tn)                                           #
      print "list = %f " % tn[0],                                            #
      for t in tn[1:]:                                                       #
        print ", %f" % float(t),                                             #
      print "\nt1 = %f, t2 = %f" % (next_t_candidate_1, next_t_candidate_2)  #
    if len(tn)>0:        # if we have transitions in the list ...
        for t in tn:     # ... checks, for all of them, if they collide ...
          if (abs(next_t_candidate_1-t) <= w_min):   # ... with candidate 1 ...
            collided1 = True                         # remembers a collision occurred
            if Verbose_level>1: print "removing ", float(t)
            tn.remove(t)                             # removes colliding transition            
    else:
        if Verbose_level>0: print "empty list, stopping now"
        f.close()
        exit()
    if len(tn)>0:
        for t in tn:
          if (abs(next_t_candidate_2-t) <= w_min):   # ... and/or candidate 2
            collided2 = True                         # remembers a collision occurred
            if Verbose_level>1: print "removing ", float(t)
            tn.remove(t)                             # removes colliding transition 
    else:
        if Verbose_level>0: print "empty list, stopping now"
        f.close()
        exit()
    if not(collided1):                              # if the first candidate did not collide
        if Verbose_level>1: print "saving transition at", float(tn[0])
        #f.write("%s\n" % str(float(tn[0])))
        f.write("%s\n" % str(tn[0]))                # saves generating transition as good one 
        tn.append(next_t_candidate_1)               # appends the good candidate do the list
    if not(collided2):                              # if candidate 2 did not collide
        tn.append(next_t_candidate_2)               # appends the good candidate do the list
        if collided1:      # if candidate 1 collided, we haven't saved the good transition yet
          if Verbose_level>1: print "saving transition at", float(tn[0])
          #f.write("%s\n" % str(float(tn[0])))
          f.write("%s\n" % str(tn[0]))              # saves the transition now

    tn = tn[1:]                                     # removes the processed transition
    tn.sort()                                 # sorts the list, to make sure of the right ordering    


# we have almost finished after the main loop
f.close()
if Verbose_level>0: print "finished!"

 



The resulting time series can be displayed in gnuplot, for instance, using the following commands:


>   set style data steps
>   set xlabel "time"
>   set ylabel "x(t)"
>   set xrange [-0.5:13]
>   set yrange [-0.1:1.1]
>   parity(n) = (n/2>floor(n/2)) ? 1: 0 
>   plot "xor_2delays_12digits.dat" using 1:(parity($0))

Fig. 2: Segment of a time series from the XOR with two delayed inputs.

 

As discussed in the references [4], the number of transitions per unit time may grow without limits in the Boolean delay equation we just presented. This behavior is not expected to occur in physical systems, because finite response speed of the logic elements prevent two transitions that come in a too fast succession from being processed. In the program above, this memory effect, called pulse filtering or short-pulse rejection, is controlled by the parameter w_min, which sets the minimum allowed interval between two processed transitions. In the particular w_min = 0 there is no pulse filtering (except for transitions that are rigorously identical, up to the specified precision), and the number of transitions per unit time may grow until it reaches the resolution determined by the specified time precision. Whenever a non-zero short-pulse rejection is considered, the XOR system will end up in a periodic orbit, but the period may be very long. Other memory effect are discussed in the next section.


3. Memory Effects

As discovered in experiments and proved in Ref. [5], deterministic chaos is only possible in simple Boolean networks when another memory effect is present: the degradation effect, which bears its name from the distortion caused in short pulses when they propagate through digital electronic gates. The delay time for a transition depends on the time that the Boolean element remains in it previous state. To model the degradation effect, we start calculating transition candidates, as described in the previous section, for a given candidate tm we calculate the pulse width p = tm - tm-1, where tm-1 is the transition chronologically before tm, and assign a function g(p) to determine the value of the delay associated to the transition t1 originating tm. the value of the transition candidate tm is then corrected to t1 + g(p) and this value is used as the transition candidate in the process described in the previous sections. If accurate precision is required, the values of p and g(p) can be calculated again and should converge iteratively to a fixed value, for a given candidate. A Python source code to calculate the evolution of a single XOR with two delayed inputs using a piecewise linear degradation function may be found here.

Another memory effect observed experimentally is the asymmetry between the delays for rises and falls, as if the logic elements remembered whether the state before a transition is 1 or 0. This can be taken into account using a piecewise constant term in the degradation function g(p) described above, whose value depends on the logic state x(t) immediately before the transition, or equivalently, on the parity of the number of transitions. With non-constant time delays, care should be taken to prevent the trailing edge of a pulse to overtake the leading edge. This situations should be identified by a negative pulse width.


Previous   Next



The author(s) do not assume any responsability for the use of the programs or algorithms presented here.