2.2.6 The Hypercube

A $d$-dimensional hypercube possesses exactly $P = 2^d$ nodes.

Recursive construction

• The nodes are placed with respect to the Gray code.
• A hypercube of dimension $d$ will be constructed by the appropriate union of two hypercubes with dimension $d-1$.
• Neighboring nodes in the hypercube differ in exactly one bit of their binary presentation. The position of that bit defines uniquely the number of the link connecting these nodes, e.g., nodes $5=LOL$ and $4=L00$ are connected via link $1$ in a 3-dimensional hypercube.
• All links with the same link number (= bit position) subdivide the $d$-dimensional hypercube in 2 $(d-1)$-dimensional hypercubes. Depending on the fact whether the bit is set or not, all nodes are mapped to one of the two subcubes, e.g. in Fig. 2.6, link 2 divides the 3-dimensional hypercube into the subcubes  $\{0,1,4,5\}$ and  $\{2,3,6,7\}$.

Figure 2.6: Hypercube $d=0,\ldots ,3$

• $d$ links per node.
• Diameter: $d = \log_2 P$
• The shortest path in a hypercube between nodes $p$ and $q$ can be calculated by XOR($p$,$q$) , wherein the not-cleared bits determine the links used in that path.
  
  Ex.: $p = 1 = 00L$, $q = 7 = LLL$ $\Longrightarrow$ XOR($1$,$7$) $= LL0$
  The path in the example is contained in a 2-dimensional subcube.
• Hardware: nCube

The hypercube contains also the topologies ring, toris and optimal tree (2.2.2 - 2.2.5).
A ring consisting of $P = 2^d$ nodes can be defined recursively and can be embedded in the hypercube :

Figure 2.7: Embedding of a ring in a 3d hypercube

Exercise 1:

Map a $2^k \times 2^{\ell}$ torus into a ($k+{\ell}$)-dimensional hypercube.

Exercise 2:

Visualize by means of a 3d hypercube that the optimal tree (Sec. 2.2.5) with node $000$ as root is embedded therein. How many mappings are possible ?

Exercise 3:

Determine an embedding of an optimal tree with root $L0L$ onto a 3d hypercube.

Exercise 4:

Find a simple function which maps the node numbers from E2.2 onto those of E2.3.