Complete & Orthogonal Replication of Hyperdimensional Memory via Elementary Cellular Automata
Nathan McDonald & Richard Davis
Air Force Research Lab/ Information Directorate, Rome, NY, USA; nathan.mcdonald.5@us.af.mil, PA: 88ABW-2019-1445

Abstract: Hyper-dimensional computing (HDC)/Vector Symbolic Architectures (VSA) [1] implements
associative learning using very large binary vectors.
This approach has been used to model the learningand transfer learning of a foraging honeybee [2]. In
real-world systems, we may want to copy learned
associations onto multiple agents, e.g. swarmsystems; however, simply copying the memory
vectors across multiple agents makes all agentsvulnerable to the same attack by a malicious entity.
Therefore the challenge is to replicate the parent
agent’s item memory and compositional memory
such that all learned associations are preserved yet
the clone’s memory vectors are maximallyuncorrelated with the parent’s memory vectors. This
work evaluated all 256 elementary cellular automata(ECA) rules for this task and identified 8 rules thatsatisfied these replication requirements. To the bestof the authors’ knowledge, this is the first report ofcomplete and orthogonal replication of HDC memory
using ECA.
Keywords: hyperdimensional computing, vector
symbolic architectures, elementary cellular automata
BACKGROUND
In this work, HDC vectors are represented as vectorsof ‘0’s and ‘1’s of length d = 1e4. The similarity between
any two such vectors is measured by the Hamming
distance (HD), the fraction of non-identical bits, e.g. fortwo random HDC vectors HD~0.5. Creating associative
memories among HDC vectors typically involves threeoperations: binding, bundling, and cyclic shifting [1].
Bundling is a majority bit operation on a collection ofvectors, denoted as [a+b+c]. Binding is analogous toassigning or reading a variable value and is performed as
bitwise XOR, denoted as ⨂. Cyclic shift of vector a by jelements is denoted as Sh(a,j). In the canonical example,
querying the compositional (associative) memory with
“What is the dollar of Mexico?” returns a noisy version(0<HD<<0.5) of the encoded “peso” HDC vector [1].
ECA are cell-based binary state machines which
follow a homogeneous rule for state transitions based onstrictly local interactions [4]. Despite their simplicity,chaos and Turing complete behavior are demonstrated
amongst these rules [4].
In [3], ECA were proposed to replicate HDC vectors
such that the resultant clones were orthogonal, that is
maximally uncorrelated (HD~0.5), to the parent vectors
while still preserving (HD~0) their encoded associations
through binding, bundling, and cyclic shift. An ECA rule
is viable when for each parent HDC vector, clones(denoted *) resultant from the ith iteration of ECA rule
R satisfy the target HDs (Tables 1 and 2) [2]. In [2], only
ECA rule 90 was studied, and it only met Table 1 criteria.
METHOD
This work explored the viability of all 256 ECA rules
to replicate HDC vectors, producing orthogonal clones
while preserving the associations of all 3 HDC encoding

Table 1. HDC Binding & Shift Operations and Target HD
xy
HD(x,y)a*0.5
a0.5(a⨂b)*a⨂b
Sh(a,10)Sh(a,10)*0.50(a⨂b)*a*⨂b*
Sh(a,10)Sh(a*,10)0Table 2. HDC Bundling & Shift Operation and Target HD
xy
HD(x,y)[a + b + c]*[a* + b* + c*]00[a⨂b + b + c]*[a*⨂b* + b* + c*][a + b + Sh(c,10)]*[a* + b* + Sh(c*,10)]0[b + [a + b + c] + c]* [b* + [a* + b* + c*] + c*]00[a⨂b + b + c]*[a*⨂b* + b* + c*]

operations. Random HDC vectors a, b, and c of length d= 1e4 were generated and operated upon according toTables 1 and 2. The resultant Hamming distances werethen calculated. Each ECA rule was tested for i = 1-50
iterations to study its cloning ability over time.
RESULTS
8 ECA rules, viz. 15, 85, 154, 166, 170, 180, 210, and240, achieved all target HDs. While rules 170 and 240
satisfied conditions with every iteration (Fig. 1a-b), theremaining six rules were viable only every 8th iteration(Fig. 1c-d) as indicated by the periodic striping. Each ofthese 8 rules when expressed as a Boolean cube are
related to one another, either of the Literal or MUX-XOR
logic family, accounting for their utility in this task [5].

a)b)c)
d)Fig. 1 HD between parent HDC vectors and clones via ECA rulea-b) 170 and c-d) 154 according to Tables 1 and 2 criteria.

All 256 ECA rules were then tested on a foraging bee
associative learning task (see Supplementary Materials),and only the 8 aforementioned rules demonstrated
complete replication (SM: Fig 1a,b red circles) andorthogonality (not shown) of the learned associations.
REFERENCES[1] P. Kanerva, Cogn. Comput., vol. 1, no. 2, pp. 139-159 (2009)[2] D. Kleyko, et. al., BICA, Vol 14, p 57-72, (2015)[3] D. Kleyko, E. Osipov, AISC 636, pp. 91-100, (2017)[4] S. Wolfram, A New Kind of Sciences (WolframMedia, Champaign
Illinois, USA).
[5] W. Bricken, “Symmetry in Boolean Functions with Examples for
Two and Three Variables,” retrieved online 2019-01-17,
http://iconicmath.com/mypdfs/symmetry-and-figures.020404.pdf