Gray Code - ergodic reader

#math/discrete #cs/cp #review #flashcards/cs ## Summary A binary numeral system where sequential numbers only differ by a single bit. Its useful in hardware, communications, and ML [[genetic algorithms]] for smooth transitions between states. For example if we have a clock and the clock is perfectly between $3(011)$ and $4(100)$ then it possible to have the bits become $7(111)$ which is far. If we use Gray Code, where the [[Hamming Distance]] between adjacent numbers is 1, then the value will either be the previous or the next, but **never** a exception wrong value. Let $G(i)$ represent the $ith$ number in the Gray Code sequence. In the example below we have $0 \to 1 \to 3$ in decimal, but in gray code this would be $1 \to 2 \to 3$. $ (00)_{2} \to (01)_{2} \to (11)_{2} $ ## The pattern Given $G(n)$ notice that the $ith$ bit of $G(n)$ only equals $1$ when $n = b_{i+1}b_{i}\dots = (01) \text{ or } (10)$. And the $ith$ bit of $G(n)$ only equals $0$ when $n = b_{i+1}b_{i}\dots = (11) \text{ or } (00)$ For example: $ \begin{align} n &= (110)_{2} \\ g(n) & = (101)_{2} \\ \end{align} $ %%--%% With just that logic we can develop the following formula for the $n^{th}$ Gray Code, $G(n)$: %%?%% $ G(n) = n \oplus (n \gg 1 ) $  %%--%% ### Gray Code: The Effect of Adding 1 Gray code guarantees that $G(n)$ and $G(n+1)$ differ by exactly one bit, calculated via $G(n) = n \oplus (n \gg 1)$. When we add $1$ to $n$, the binary addition behaves in one of two ways. **Case 1: No Carryover** If $n$ is even, its least significant bit (LSB) is $0$. Adding $1$ simply flips this LSB to $1$ without affecting higher bits. Because the shifted value $(n \gg 1)$ remains identical in the LSB position, only the LSB flips in the resulting Gray code. $\begin{align*} G(6) &= 110 \oplus 011 = 101 \\ G(7) &= 111 \oplus 011 = 100 \quad \text{(Only the LSB changed)} \end{align*}$ **Case 2: Carryover** If $n$ ends in $i$ trailing ones preceded by a zero ($i+1^{th}$ bit), adding $1$ flips those ones to zeros and the preceding zero ($i+1^{th}$ bit) to a one. I.e. $0$ followed by $i$ ones to $1$ followed by $i$ 0s. The first $i$ bits after XOR operation are the same. The $i$ LSBs are preserved. $(i=2) \qquad \begin{align*} G(3) &= 011 \oplus 001 = 010 \\ G(4) &= 100 \oplus 010 = 110 \quad \text{(Only the 3rd bit changed)} \end{align*}$ **The $(i + 1)^{th}$ Bit Flips** The $(i + 1)^th$ bit of $n$ goes from a 0 to a 1 when we add $1$ to it. - If the $i+2^{th}$ bit was a 1 then the XOR for the $i+1^{th}$ bit goes from a 1 to a 0. - If the $i+2^{th}$ bit was a 0 then the XOR for the $i+1^{th}$ bit goes from a 0 to a 1. - $a \oplus b \neq \neg a \oplus b$ where $a,b \in \{0,1\}.$ **The $(i+2)^{\text{th}}$ Bit and Beyond are Preserved** Adding 1 did not effect anything beyond the $i+1^{th}$ bit. So all XORs after $i+1$ are the same. > [!Insight] > Case 1 is just case 2 where $i=0$. ## Code ```python int g (int n) { return n ^ (n >> 1); } ``` ## Finding the Inverse Let $N_{k}$ be the $k^{th}$ bit of an integer $N$. Then, $ \begin{align} n_{k} &= G(n)_{k} \\ n_{k-1} &= G(n)_{k-1}\oplus n_{k} = G(n)_{k} \oplus G(n)_{k-1}\\ n_{k-2} &= G(n)_{k} \oplus G(n)_{k-1} \oplus G(n)_{k-2}\\ \dots \\ n_{1} &= G(n)_{k} \oplus G(n)_{k-1} \oplus \dots \oplus G(n)_{1}\\ \end{align} $ ```python # Where g = G(n) int rev_g (int g) { int n = 0; for (; g; g >>= 1) # Don't confuse bit flips and XOR # XOR = 1 if bits are diff; 0 if same n ^= g; return n; } ```