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 2^n bit strings of length n with the Gray property: every consecutive pair of bit strings differs by one bit. (Gray codes also have the property that the first and last strings differ 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 2^n bit strings of length n such that every consecutive string differs by one bit Algorithm: NaiveGray(n) if n = 1 then return [0, 1] end left = right = NaiveGray(n - 1) Reverse right Append 0 to all bit strings in left Append 1 to all bit strings in right return the concatenation of left and right

Explanation / Answer

For example, following are steps for generating the 3-bit Gray code list from the list of 2-bit Gray code list.
L1 = {00, 01, 11, 10} (List of 2-bit Gray Codes)
L2 = {10, 11, 01, 00} (Reverse of L1)
Prefix all entries of L1 with ‘0’, L1 becomes {000, 001, 011, 010}
Prefix all entries of L2 with ‘1’, L2 becomes {110, 111, 101, 100}
Concatenate L1 and L2, we get {000, 001, 011, 010, 110, 111, 101, 100}

C++ program to generate n-bit Gray codes

#include <iostream>

#include <string>

#include <vector>

using namespace std;

void generateGrayarr(int n)

{

  

    if (n <= 0)

        return;

    vector<string> arr;

    arr.push_back("0");

    arr.push_back("1");

  

    int i, j;

    for (i = 2; i < (1<<n); i = i<<1)

    {

  

        for (j = i-1 ; j >= 0 ; j--)

            arr.push_back(arr[j]);

        for (j = 0 ; j < i ; j++)

            arr[j] = "0" + arr[j];   

        for (j = i ; j < 2*i ; j++)

            arr[j] = "1" + arr[j];

    }

    // print contents of arr[]

    for (i = 0 ; i < arr.size() ; i++ )

        cout << arr[i] << endl;

}

int main()

{

    generateGrayarr(4);

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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