N-Cubes from Binary Codes

Introduction

I have been seeing many hyper-cube animations lately and am inspired to try to create something similar. So, today I want to look into generating n-dimensional cubes with binary block codes. I will break this project down into two parts:

  1. Generate points for a cube of any given dimension
  2. Render and rotate the cube on the screen

Binary Codes and Cubes

Back in college, my math professor showed me a relationship between binary block codes and cubes, which is helpful for point generation. For those of you unfamiliar with binary block codes, A binary block code of length n is any subset (C ⊆ {0, 1}^n) of the set of all binary n-tuples of length n 1. A math-y way of saying a binary block code of a specific length n is any permutation of 1s and 0s of that length. So, for example, a binary block code of length 3 is 101. It's three digits long and is a binary number. All permutations of this 000, 001, 010, 011, 100, 101, 110, 111, are all binary block codes of length three.

What's interesting about these block codes is that if you take all the binary block codes of a given dimension, you can create a cube of that dimension. Looking at a simple case where the dimension is two (n = 2), all of the codes are: 00, 01, 10, and 11. You'll notice there are four of them, just as there are four corners on a square (a two-dimensional cube). We can transform these binary digits into two-dimensional coordinates and plot them on a graph:

This works out since the coordinates of a square can be simplified to (±1,±1), the current square defined by our points is half the size of this one. Any cube of any dimension follows this pattern so that a cube would be (±1,±1,±1) and a hyper-cube would be (±1,±1,±1,±1).

Knowing the points is just the first part of the generation though, for us, it's easy to see the square; however, a computer doesn't know what a square is and doesn't know which dots to connect to create the square shape after. Additionally, we to will struggle to connect the dots as we increase the dimensions. Luckily, there is a rule we can use to figure out which points go to which.

If we draw the lines on the square on the dots above, there's an interesting pattern that appears when connecting the vertices. All the connected points are only one x-y-coordinate off from each other. We can take advantage of this relationship to determine the sides of the cube. This rule involves one more math term, weight. The weight of a binary block code is simply the number of digits that are 1. The weight of 11 is two, and the weight of 10 or 01 is one. We can find whether or not there is an edge between the two vertices by XOR-ing the binary codes of the vertices and then looking at the weight of the resulting code. If the weight of the resultant is one, then there is an edge between the vertices. A good way to visualize this is to order the codes in a hierarchy by their respective weights:

This rule extends into any dimension; below is a cube using the same rule.

With that in place, the only thing left is to start creating the generator.

Generator

A good data structure to use for this cube looks to be an undirected graph from the figures above. With this in mind, the generator should return a graph. Graphs consist of nodes and edges. There are two common ways to represent them:

A good breakdown of these two can be found here. For our case an adjacency list will be the easiest to implement because we can represent a graph using an object like this:

const square = {
  "00": ["01", "10"],
  "01": ["00", "11"],
  10: ["00", "11"],
  11: ["01", "10"],
};

Note that there are duplicate edges in this graph; this is normally used to delineate direction. In our case, we aren't worried about direction.

Let's start by getting all the nodes. Since we are looking at the entirety of the space {0,1}^n (all numbers between 000...0 and 111...1), we only need to know the largest value in the space. From there, we can fill in the rest. After finding all the nodes, the edges can be retrieved by going over those nodes and checking the weight of the a single node XOR-ed with each of the other nodes one at a time.

// A helper function to convert decimals (Number) into padded binary strings
function decimalToBinaryString(decimal, dimension) {
  return decimal.toString(2).padStart(dimension, "0");
}

function cubeGenerator(dimension) {
  // Left shift is raising 2 to a power
  const maxNumber = 1 << dimension;

  // Create an array with values 0...maxNumber
  const nodes = Array.from(Array(maxNumber).keys());

  // Create edges
  const graph = nodes.reduce((graph, currentNode, index, allNodes) => {
    const connectedNodes = allNodes
      .map((otherNode) => {
        const resultant = currentNode ^ otherNode;

        // count the number of ones
        const weight = decimalToBinaryString(resultant).split("1").length - 1;

        return weight == 1 ? decimalToBinaryString(otherNode) : null;
      })
      .filter((value) => value != null);

    return {
      ...graph,
      [decimalToBinaryString(currentNode)]: connectedNodes,
    };
  }, {});

  return graph;
}

from this function we get the following for n = 2:

{
  '10': [ '00', '11' ],
  '11': [ '01', '10' ],
  '00': [ '01', '10' ],
  '01': [ '00', '11' ]
}

and n = 3:

{
  '100': [ '000', '101', '110' ],
  '101': [ '001', '100', '111' ],
  '110': [ '010', '100', '111' ],
  '111': [ '011', '101', '110' ],
  '000': [ '001', '010', '100' ],
  '001': [ '000', '011', '101' ],
  '010': [ '000', '011', '110' ],
  '011': [ '001', '010', '111' ]
}

With this, the cube generation is complete. Earlier it was shown how one could connect points. That said, it's right now just that a collection of binary numbers, and if we were to try and graph this or render it at all, it wouldn't work. So, next time (Part Two), I will create a renderer that takes this graph data structure and projects all the points down into 2D to be rotatated and rendered.

Footnotes

  1. MIT Electrical Engineering Book ↩