Video2NAND

Much has been written about turning NAND gates into computers, but knowledge of how to build these NAND gates is not as common. You may think that it’s in the realm of transistors and electrical engineering, but we’ll explore a much more exotic substrate: the video codec.

Specifically, we’ll talk about the VP8 video codec and how to abuse its prediction mechanisms to simulate combinatorial logic. Our goal is to build up a set of composable “gadgets” which can construct arbitrary logic circuits.

A Tiny Bit About Video Codecs

Video codecs are standards which describe a method of encoding a video (a series of images) into some bitstream, and how to decode that bitstream back into the original video. Instead of prescribing exactly how to encode a video, they usually define a general structure and some set of primitives which can be used to encode the video. As such, different video encoder implementations (or even the same encoder with different settings) may encode the same video differently, but all decoders are expected to be able to reconstruct the video regardless.

We will not explain the whole inner-workings of VP8, our video codec of choice, and instead focus on a subset relevant to our purposes. Furthermore, the following explanations are not entirely accurate, in an attempt to simplify the prerequisite knowledge to its essence. If you are interested in learning more about video codecs, I’d recommend reading the Theora spec, which is surprisingly readable.

In a sense, a video is just a series of images. In video codec jargon, these images are called “frames” where each frame is grid of pixels. Frames are generally divided into to two kinds: key-frames and inter-frames.

Key-frames are frames which are encoded independently of other frames. All data required to reconstruct the image is contained within the representing frame. The pixel data may be encoded directly into the frame, or predicate using intra-frame prediction. Intra-frame prediction allows the encoder to state that a certain block of the image can be predicted from another nearby block.

Since VP8 decodes these blocks row-by-row, from the top-left down to the bottom-right, the intra-frame prediction primitives it offers allow predicting a block using the row above it, the column to the left of it, and the top-left pixel between them.

Inter-frames are frames which exploit the fact that subsequent frames don’t change much, and allow predicting blocks of pixels based on previously decoded frames. They offer the same encoding primitives as key-frames, as well as allowing inter-frame prediction: describing a block by referencing a block from a previous frame.

We will build our combinatorial circuits purely using key-frames. Partly because the semantics of combinatorial-vs-sequential logic map well to key-frames-vs-inter-frames, and partly because the extra challenge of a limited toolkit is more interesting.

Wires and Gates

Combinatorial circuits are built up out of inputs, outputs, wires and gates. In our case, instead of electrical current representing True and False, each block in the frame will either be completely white (all pixel values set to 255) or completely black (all pixels values set to 0), respectively.

And we’ll model wires going right or down using H_PRED and V_PRED prediction modes. H_PRED stands for “horizontal prediction”, and means that every pixel value in the block is predicted by copying the value of the pixel to the left of it. Similarly, V_PRED stands for “vertical prediction”, and copies the value from above instead.

Drawing the frame as a grid of blocks:

Inputs will be represented as non-predicted blocks, set to a constant value of either completely white or completely black. Outputs are simply labeled wire blocks:

At this point, only logic gates are left. In order for our system to be functionally complete, meaning it can describe any truth-table, it is enough to construct two gates: NOT and AND. We could have chosen a different functionally complete set of gates, such as just a NAND, but as we’ll see these gates are trivial to construct.

Both gates will gate constructions will use the TM_PRED prediction mode. It stands for “True Motion prediction”, and is only slightly more complex than the prediction modes we’ve seen so far. In a TM_PRED block, the value of each pixel is computed as the sum of the corresponding pixel in the above row and the corresponding pixel in the left column, minus the value of the top-left pixel. So for a pixel with row i and column j, the value will be left[i] + top[j] - top_left.

All of our blocks are homogeneous - either completely black or white. This means that top[0] = top[1] = top[2] = ... and likewise left[0] = left[1] = left[2] = .... Leading to a simplified calculation of a TM_PRED block: left + top - top_left:

Since pixel values are clamped between 0 and 255, a NOT gate is equivalent to the formula 255 - INPUT (verify for yourself by substituting INPUT with either 0 or 255). We can represent this formula using a TM_PRED block. Assume the input is the top_left pixel, set the top row to all 255, and the left column to all 0 (or vice-versa). The output of the gate is the right and bottom of the TM_PRED block, which can be propagated further using the wire blocks we’ve described above.

Similarly, we can construct an AND gate by setting top_left to 255, the first input to the top row and the second input to the left column. A TM_PRED block in such a setup will represent the formula A + B - 255. Plugging in all the possible input values of A and B, we can see that the output is exactly an AND gate:

Now that we’ve constructed all the basic gadgets, we can combine them to create various other gates and circuits, including the venerable NAND:

Wrapping Up

Hopefully you’ve enjoyed this cross-domain journey, and learned something about video codecs, combinatorial logic or weird machines. We’ve only just scratched the surface, there are still a lot of open questions and directions we can take this in. Could we optimize the gadgets to be smaller? What about integrating these ideas into a synthesis tool, possibly enabling synthesis of Verilog down to VP8 frames? Or maybe, explore sequential logic and how we could implement it using inter-frames?