IEEE Circuits and Systems Magazine - Q2 2020 - 34

more general case, as shown in Fig. 3, for two randomly
-generated 10,000-bit binary hypervectors, their pointwise multiplication result is dissimilar to both of them.
A = 0 0 0 0 1 1 0 0 1 1,
B = 1 0 1 1 0 0 0 1 0 1, 

	

A 5 B = 1 0 1 1 1 1 0 11 0.

(6)

3) Permutation
Permutation t is a unique unary operation for HD computing, which shuffles the hypervector, let us say A.
The resulting permuted hypervector t (A) is quasi-orthogonal to the initial A, i.e., the normalized Hamming
distance is close to 0.5. Mathematically, permutation
can be realized by multiplying a permutation matrix.
As a specific permutation, circular shift is widely employed for its friendly hardware implementation. Eq. (7)

100

Probability (%)

60

20
0



(7)

Examples. We illustrate applications of above operations. For more details, please refer to [16]. Assume
that A, B, C, P, S, X, Y, Z represent 10,000-d random
hypervectors:
■■ Encode a pair: To encode `x = a_, where x is a variable with numerical value same as a, use multiplication to bind their corresponding hypervectors
X and A. The encoding is represented by the generated hypervector P = X 5 A.
■■ Release the value from the pair:
X 5 P = X 5 (X 5 A) = A (8)
144424443
■■ Represent a set: Given the set s = {a, b, c}, we have

S = [A + B + C] (9)

	

80

■■ Encode a data record: Given a record with a set

78

of bound pairs d = ] (x = a) & ( y = b) & (z = c),\ the
record is encoded as:
0.49

0

t (A) = 1 0 0 0 0 1 1 0 0 1.

X 5 X cancels out

82

40

A = 0 0 0 0 1 1 0 0 1 1,

	

	

Ham (A, B)
Ham (X, A )
Ham (X, B )

80

shows a circular shift of a 10-bit binary vector with Ham
(A, t (A)) = 0.4. Expected Hamming distance is supposed
to be 0.5 for ultra-wide -hypervectors. Fig. 4 indicates the
permutation result shows dissimilarity with the original
10,000-bit hypervector.

0.5

0.51

0.2
0.4
0.6
0.8
Normalized Hamming Distance

D = [X 5 A + Y 5 B + Z 5 C] (10)

	

■■ Extract the value from a record: To retrieve the

1

value of x:
Al = X 5 D
= X 5 [X 5 A + Y 5 B + Z 5 C]
1444444442444444443

Figure 3. Hamming distance distribution of multiplication
X = A 5 B for 10,000-bit hypervectors over 3000 cases.

distributed

	
100

Probability (%)

(11)

.A
■■ Encode a sequence: Given (a, b), then

	

60

AB = t(A) 5 B (12)
■■ Extend the sequence: Extend (a, b) to (a, b, c) using:

40

	

20

ABC = t (AB ) 5 C

= t ( t (A)) 5 t (B ) 5 C

(13)

■■ Extract the first element of the sequence:
0

0.2
0.4
0.6
0.8
Normalized Hamming Distance

1

Figure 4. Hamming distance distribution of permutation for
10,000-bit hypervectors over 3000 cases.
34 	

noise

=A

Ham (A, ρ (A))

80

0

= X 5 X 5 A + X 5Y 5 B + X 5 Z 5 C 
= X 5 X 5 A + (X 5 Y 5 B + X 5 Z 5 C )
1444244
43 14444444244444443

t -1 t -1 (ABC 5 BC )

	

= t -1 t -1( t ( t (A)) 5 t (B ) 5 C 5 t(B ) 5 C ) 
(14)
=A

where t -1 is the inverse operation of permutation t.

IEEE CIRCUITS AND SYSTEMS MAGAZINE 		

SECOND QUARTER 2020
IEEE Circuits and Systems Magazine - Q2 2020

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2020
