Browse Prior Art Database

DeBruijn Sequences From Cellular Automata

IP.com Disclosure Number: IPCOM000119959D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 4 page(s) / 119K

Publishing Venue

IBM

Related People

Bardell, PH: AUTHOR [+2]

Abstract

Disclosed are methods of including the all 0's word in a maximum length sequence generated by cellular automata (CA). Such sequences will be called deBruijn sequences. The CAs considered are one-dimensional, binary, finite-state machines. The next state of each cell of a CA is determined by the value of the cell itself and values of the cells immediately adjacent to it on the left and right. Maximum length sequences are generated by CAs that use linear rules within the three- neighborhood to determine the next state, and specifically those "hybrid" CAs that use the following two rules: Rule 90: sn + 1(m) = sn(m - 1)+sn(m + 1) Rule 150: sn + 1(m) = sn(m - 1)+sn(m)+sn(m + 1) where sn(m) is the value of cell m at time step n and + denotes addition modulo 2 (the exclusive-OR function).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

DeBruijn Sequences From Cellular Automata

      Disclosed are methods of including the all 0's word in a
maximum length sequence generated by cellular automata (CA). Such
sequences will be called deBruijn sequences.  The CAs considered are
one-dimensional, binary, finite-state machines.  The next state of
each cell of a CA is determined by the value of the cell itself and
values of the cells immediately adjacent to it on the left and right.
Maximum length sequences are generated by CAs that use linear rules
within the three- neighborhood to determine the next state, and
specifically those "hybrid" CAs that use the following two rules:
           Rule 90:  sn + 1(m) = sn(m - 1)+sn(m + 1)
      Rule 150:  sn + 1(m) = sn(m - 1)+sn(m)+sn(m + 1)
where sn(m) is the value of cell m at time step n and + denotes
addition modulo 2 (the exclusive-OR function).  Rule 90 says that the
value of a particular cell is the exclusive-OR (XOR) of the values of
its two neighboring cells on the previous clock cycle, while Rule 150
also includes the previous value of the cell itself.  (The rules are
named in (1), and the use of hybrid Rule 90/Rule 150 automata is
suggested in (2)).

      These two rules can be combined in a k-cell CA to generate a
cyclic sequence of length 2k - 1.  Figure 1 shows an example for k =
4.  Note the null boundary condition in Figure 1 in which the first
and last cell receive 0.  This will be the case for all CAs
considered herein.  If the CA of Figure 1 is initialized to a
non-zero word, it will generate the maximum-length sequence shown.
Note that only the all 0's word is missing from the sequence.

      The left-most cell of a maximum-length CA must be either a Rule
90 or a Rule 150.  Figure 1 has a Rule 150 cell left-most.  The CA
of Figure 2 has a Rule 90 cell left-most.  Again, in the cyclic
sequence for this CA only the all 0's word is missing.

      In some applications the all 0's word is necessary. The all 0's
word can be inserted into a maximum length sequence generated by a CA
immediately after any word that contains a single 1.  These "target"
words are highlighted by arrows in Figures 1 and 2.  Obviously, in a
sequence of length 2k - 1 there are k such target words.  The first
step in the insertion is to AND the complements of all of the cells
with value 0 in the target word.  The output of this AND gate is fed
to the exclusive-ORs driving the cells with value 1 in the word
following the target word...