As mentioned in comment, Livescribe uses a dot pattern technology licensed from a Swedish company Anoto. The dot pattern is most likely the one covered by patent
WO/03/038741.
Edward Aboufadel has a paper Position Coding
which explains the mathematical ideas behind Anoto's dot pattern.
The construct in this answer uses ideas from Aboufadel's paper.
It is not the one used by Livescribe nor the one explictly discussed in Aboufadel's paper.
All mistakes and misunderstandings are mine.
Let $P = \{ 0, 1, 2, \ldots, p - 1 \} \subset \mathbb{N}$ be the set of non-negative integers less than some positive integer $p$. Given any finite sequence
$$A = (a_0, a_1, \ldots, a_{m-1}) \in P^{m}$$
We can extend it to a sequence over $\mathbb{Z}$ by periodicity. i.e
$$P^m \ni A \mapsto A' = (\ldots a'_{-2}, a'_{-1}, a'_{0}, a'_1 a'_2,\ldots) \in P^{\mathbb{Z}}
\;\;\text{ s.t. }\;\; a'_k = a_{k\!\pmod m}
\;\;\text{ for } k \in \mathbb{Z}
$$
If there exists a $n$ such that the $m$ finite subsequences of length $n$
$$
(a'_0, a'_1, \ldots, a'_{n-1}),\,
(a'_1, a'_2, \ldots, a'_{n}),\,
\ldots,\,
(a'_{m-1}, a'_{m}, \ldots, a'_{n+m-2})$$
are all distinct, we will call the sequence $A'$ an $p$-ary pseudo De Bruijn sequence of order $n$ and length $m$. In the special case $m = 2^n$, $A'$ will be called a De Bruijn sequence.
The most important property of these sort of sequences is that if we know the value of
$n$ consecutive terms in a sequence, we will know the relative position of those terms modulo $m$.
From now on, let us abuse the notation by dropping the $'$ and use $A = (a_k)$ to represent both the original finite sequence and the generated infinite sequence.
Following are some examples of binary pseudo De Bruijn sequences:
$$\begin{array}{lcl}
n = 4, m = 16 &:& A = (a_k) = 0000110101111001\ldots\\
n = 3, m = 8 &:& B = (b_k) = 00010111\ldots\\
n = 3, m = 7 &:& C = (c_k) = 0001011\ldots\\
n = 3, m = 5 &:& D = (d_k) = 00111\ldots\\
n = 3, m = 3 &:& E = (e_k) = 001\ldots
\end{array}$$
Notice the sequences $B,C,D,E$ above all have order $n = 3$ and their lengths are relative prime to each other. If we construct a hexadecimal sequence $F = (f_k) \in \{ 0,\ldots, 15\}^{\mathbb{Z}}$ by
$$f_k = 8 b_k + 4 c_k + 2 d_k + e_k\quad\text{ for } k \in \mathbb{Z}$$
the sequence $F$ will be a pseudo De Bruijn sequence of order $3$ and length
$\text{lcm}(8,7,5,3) = 840$.
If we are given the values of 3 consecutive $f_k, f_{k+1}, f_{k+2}$, we can
recover the values of $k \pmod{840}$ by following procedure:
- breakdown $( f_{k}, f_{k+1}, f_{k+2} )$ into their bits, recover the values of
$$
( b_k, b_{k+1}, b_{k+2} ),\,
( c_k, c_{k+1}, c_{k+2} ),\,
( d_k, d_{k+1}, d_{k+2} ),\,\text{ and }
( e_k, e_{k+1}, e_{k+2} )$$
- Since $B$ is pesudo Bruijn with a relative short length $8$, we can use a table look-up
to discover the value of $k \pmod{8}$.
- If we do the same thing to $C$, $D$ and $E$, we will discover the value of $k \pmod{7}$,
$k \pmod{5}$ and $k \pmod{3}$ respectively.
- We can then use Chinese remainder theorem to recover the value of $k \pmod{840}$.
Let $\varphi : \mathbb{Z} \to \{0, \ldots, 15\}$ and
$X, Y : \mathbb{Z}^2 \to \{ 0, 1 \}$ be the functions defined by
$$\varphi(x) = \sum_{k=0}^{x-1} f_k \pmod{16} \quad\text{ and }\quad
\begin{cases}
X(x,y) &= a_{y + \varphi(x)}\\
Y(x,y) &= a_{x + \varphi(y)}
\end{cases}$$
where $(a_k) = A$ is the first example of De Bruijn sequences above.
For each $(x,y) \in [1,209] \times [1, 296]$, let us place a dot near $(x,y)$ based on the values of $X(x,y)$ and $Y(x,y)$:
$$\begin{array}{|cc:c|}
\hline
X(x,y) & Y(x,y) & \text{center}\\
\hline
0 & 0 & (x-0.1,y)\\
0 & 1 & (x+0.1,y)\\
1 & 0 & (x,y-0.1)\\
1 & 1 & (x,y+0.1)\\
\hline
\end{array}$$
Since the filmed area of the camera has dimension $10\text{mm} \times 10\text{mm}$,
it always contains a $9 \times 9$ square of dots. For our current placement of dots, we only need the $4 \times 4$ square of dots near the center of view.
Let's say the camera has decoded the offsets for a $4 \times 4$ square of dots
and return us with two $4 \times 4$ array of binary numbers. One for $X$ and another for $Y$. Let us look at the $4 \times 4$ array of binary numbers for $X$:
$$\begin{array}{r|cccc}
X & x & x+1 & x+2 &x+2\\
\hline
y & g_{00} & g_{10} & g_{20} & g_{30}\\
y+1 & g_{01} & g_{11} & g_{21} & g_{31}\\
y+2 & g_{02} & g_{12} & g_{22} & g_{32}\\
y+3 & g_{03} & g_{13} & g_{23} & g_{33}\\
\end{array}$$
Across any column, say the leftmost column,
$$( g_{00}, g_{01}, g_{02}, g_{03}) =
(a_{y+\varphi(x)}, a_{y+\varphi(x)+1}, a_{y+\varphi(x)+2}, a_{y+\varphi(x)+3})$$
is a sub-sequence of length $4$ for the De Bruijn sequence $A$ whose order is also $4$.
We can look-up the value of $y + \varphi(x) \pmod{16}$ from a table of $16$ entries.
If we do the same thing to other 3 columns, we will obtain the values of
$y + \varphi(x) + f_x \pmod{16}$, $y + \varphi(x) + f_x + f_{x+1}\pmod{16}$ and
$y + \varphi(x) + f_x + f_{x+1} + f_{x+2} \pmod{16}$ respectively.
We can combine these four pieces of information to get the values of $f_x$, $f_{x+1}$
and $f_{x+2}$. By the procedure discussed above, we can deduce the value of $x$.
By a similar procedure, we can deduce the value of $y$ from the $4 \times 4$ array of binary numbers for $Y$.
Since the pseudo De Bruijn sequence $F = (f_k)$ has a length $840$ larger than the dimension of the paper, all the "$4 \times 4$ square of dots" are distinct.
