Dyadic Encoding

Dyadic Encoding is a form of binary encoding defined by Smullyan commonly used in computational complexity theory '1's and '2's that is bijective and has the "technical advantage, not shared by binary, of setting up a one-to-one correspondence between finite strings and numbers."

Dyadic encoding works by using a recursive definition of concatenating strings of '1's and '2's together using the following formula.

• dya(0) = ξ (empty string)
• dya(2n + 1) = dya(n)'1' Odd numbers
• dya(2n + 2) = dya(n)'2' Even numbers

For example:

Natural Number	Dyadic Encoding
0	ξ (empty string)
1	1
2	2
3	11
4	12
5	21
6	22
7	111

The numerical value $n$ of a string $d_k\cdots d_2{d}_1$ with $d_i\in \{1,2\}$ is given by $n=d_k\cdot 2^{k-1}+\dots +d_2\cdot 2+d_1$. As the above recursive construction implies, each positive integer is uniquely represented in this way.

References

Computational complexity theory