Gray Code Implementation - 2023.2 English

Here, we give a brief outline of the implementation. With a pre-calculated matrix C, where the matrix-vector multiplications are performed in the finite field \(Z_{b}\) see sobol reference. To generate the j-th component of the points in a Sobol sequence, we need to choose a primitive polynomial of some degree \(S_{j}\) in the field \(Z\), where \(Z_{2}={0,1}\), the equation is shown as follow:

\[x^{S_{j}} + a_{1,j} x^{S_{j}-1} + a_{2,j} x^{S_{j}-2} + \cdots + a_{S_{j}-1,j} x^{1} + 1\]

where the coefficients \(a_{1,j} , a_{2,j} , \cdots , a_{S_{j}-1,j}\) are either 0 or 1. We define a sequence of positive integers \(\{ m_{1,j}, m_{2,j} , \cdots \}\) by the recurrence relation:

\[m_{k,j} := 2a_{1,j} m_{k-1,j} \oplus 2^{2} a_{2,j} m_{k-2,j} \oplus \cdots \oplus \ 2^{ S_{j}-1 } a_{S_{j}-1,j} m_{ k-S_{j} + 1, j} \oplus 2^{S_j} m_{k-S_j,j} \oplus m_{k-S_j,j}\]

where \(\oplus\) is the bit-by-bit exclusive-or operator. The initial values \(m_{1,j} , m_{2,j} , \cdots , m_{ S_{j},j}\) can be chosen freely provided that each \(m_{k,j} , 1 \le k \le S_{j}\) , is odd and less than \(2^{k}\) . The so-called direction numbers \(\{ \nu_{1,j}, \nu_{2,j}, \cdots \}\) are defined by:

\[\nu_{1,j} :=\frac { m_{k,j} } { 2^{k} }\]

Then the \(x_{i,j}\) element of the j-th dimension of the i-th point in a Sobol sequence, can be generated by:

\[x_{i,j} := i_{1} \nu_{1,j} \oplus i_{2} \nu_{2,j} \oplus \cdots \nu_{n,j}\]

where \(i_{k}\) is the \(k\)-th digit from the right-hand side when \(i\) is written in binary \(i = ( \cdots i_{3} i_{2} i_{1} )_{2}\). Here and elsewhere in this article, we use the notation \(()_{2}\) to denote the binary representation of numbers. The formula above corresponds to the original implementation of Sobol. The (binary-reflected) Gray code of an integer \(i\) is defined as:

\[gray(i) := i \oplus \lfloor \frac {i}{2} \rfloor =(\cdots i_3 i_2 i_1)_2 \oplus ( \cdots i_{4} i_{3} i_{2})_{2}\]

It has the property that the binary representations of \(gray(i)\) and \(gray(i-1)\) differs in only one position, namely, the index of the first 0 digit from the right in the binary representation of \(i-1\).

We generate the points of Sobol using

\[\bar{x}_{i,j} := g_{i,1} \nu_{1,j} \oplus g_{i,2} \nu_{2,j} \oplus \cdots\]

where \(g_{i,k}\) is the k-th digit from the right of the Gray code of \(i\) in binary, i.e., \(gray(i) = ( \cdots g_{3} g_{2} g_{1})_{2}\). Equivalently, since \(gray(i)\) and \(gray(i-1)\) differ in one known position, we can generate the points recursively using:

\[\bar{x}_{0,j} := 0 , \bar{x}_{i,j} := \bar{x}_{i-1,j} \oplus \bar{x}_{c_{i-1},j}\]

where \(c_{i}\) is the index of the first 0 digit from the right in the binary representation of \(i = ( \cdots i_{3} i_{2} i_{1})_{2}\). We have \(c_{0}=1, c_{1}=2, c_{2}=1, c_{3}=3, c_{4}=1, c_{5}=2\), etc.

With the implementation of Gray Code, we simply obtain the points in a different order, which still preserve their uniformity properties. It is because every block of \(2^{m}\) points for \(m=0,1, \cdots\) is the same as the original implementation. It is known that the two equations closely mentioned above can generate exactly the same sequence, and the former one allows one to start from any position in the sequence, while the later one is recursive and more computationally efficient. The reference is equation reference.