gray code

By | October 11, 2020
0 Comment
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

This is the gray code. The changing rule can be:

rule1: update the rightmost bit
rule2: for xxx100…00, it can change the digit x which is next to 100..00

See lc1611

For example, 1001000 has 2 ways of change:
1. rule1 -> 1001001
2. rule2 -> 1011000

Another example, 1111 has 2 ways of change:
1. rule1 -> 1101
2. rule2 -> 1110

The property of gray code, is that each two adjacent number only have 1 bit difference.

For example, in decimal, if we want to update from 011 to 100, the electronic element may change like 100->101->111->100. There is potential ephemeral number 101, 111. In gray code, this won’t happen. Because each two adjacent number only has 1 bit difference.

Decimal Binary Gray
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000

 

Transformation from decimal to gray code. See here.

  1. keep the leftmost bit same.
  2. For each following bit, xor the 2 adjacent decimal bits

(10011001)d -> (11010101)gc

Transformation from gray code to decimal. See here

  1. keep the leftmost bit same.
  2. For each following bit, xor current gray code bit and decimal bit

(11010101)gc -> (10011001)d