Prove that the following algorithm generates an n-bit Gray code. A Gray code is

Question

Prove that the following algorithm generates an n-bit Gray code. A Gray
code is a sequence of 2n bit strings of length n with the Gray property:
every consecutive pair of bit strings di ers by one bit. (Gray codes also
have the property that the rst and last strings di er by one bit and every
string of length n appears exactly once, but you do not need to prove
either of these properties.)

Input n: number of bits in Gray code, must be a positive integer Output array gray with 2n bit strings of length n such that every consecutive string differs by one bit 1 Algorithm: NaiveGray (n) 2 if n 1 then 3 return 0, 1] 4 end 5 left right NaiveGray (n -1) 6 Reverse right 7 Append 0 to all bit strings in left 8 Append 1 to all bit strings in right 9 return the concatenation of left and right

Explanation / Answer

case1:
{
   If n = 1:
   which results in G = {0,1}.
}

case2:
{
   If n = 2:
   L1 = {0, 1} (List of 1-bit Gray Codes)

   step no 6 in algorithm reflect the bits
   L2 = {1, 0}

   Step7:
   Prefix all entries of L1 with ‘0’, L1 becomes {00, 01}

   Step8:
   Prefix all entries of L2 with ‘1’, L2 becomes {11, 10}

   concatenate L2 with the original list
   G = {00, 01, 11, 10}
}

case 3:
{
    if n = 3:
   So we have to find 3 bits in graycode:

   2^n= 2^3=8:
   So output gray code array will have 8 strings of lenth 3

   following are steps by step explanation of algorithm for generating the 3-bit Gray code list.
   Here n = 3
   L1 = {00, 01, 11, 10} (List of 2-bit Gray Codes, It can also be generated using current algorithm)

   first we will hit step no 6 in algorithm, since n is greater than
   L2 = {10, 11, 01, 00} (Reverse of L1)

   Step 5 is recursive call which means:
   To generate n-bit Gray codes, we start from list of 1 bit Gray codes. The list of 1 bit Gray code is {0, 1}. We repeat above steps to generate 2 bit Gray codes from 1 bit Gray codes, then 3-bit Gray codes from 2-bit Gray codes till the number of bits becomes equal to n

   Step7:
   Prefix all entries of L1 with ‘0’, L1 becomes {000, 001, 011, 010}

   Step8:
   Prefix all entries of L2 with ‘1’, L2 becomes {110, 111, 101, 100}

   Step9:
   Concatenate L1 and L2, we get {000, 001, 011, 010, 110, 111, 101, 100}
   and return concatenated output
   G = {000, 001, 011, 010, 110, 111, 101, 100}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.