Question

a. Generate the binary reflexive Gray code of order 4. b. Trace the following nonrecursive algorithm...

a. Generate the binary reflexive Gray code of order 4.
b. Trace the following nonrecursive algorithm to generate the binary reflexive
Gray code of order 4. Start with the n-bit string of all 0

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Answer:

a) Generating the Binary Reflexive Gray code of order 4:

#include <bitset>
#include <iostream>
#include <string>

uint32_t gray_encode(uint32_t b)
{
return b ^ (b >> 1);
}

uint32_t gray_decode(uint32_t g)
{
for (uint32_t bit = 1U << 4; bit > 1; bit >>= 1)
{
if (g & bit) g ^= bit >> 1;
}
return g;
}

std::string to_binary(int value) // utility function
{
const std::bitset<4> bs(value);
const std::string str(bs.to_string());
const size_t pos(str.find('1'));
return pos == std::string::npos ? "0" : str.substr(pos);
}

int main()
{
std::cout << "Number\tBinary\tGray\tDecoded\n";
for (uint32_t n = 0; n < 4; ++n)
{
uint32_t g = gray_encode(n);
uint32_t b = gray_decode(g);

std::cout << n << "\t" << to_binary(n) << "\t" << to_binary(g) << "\t" << b << "\n";
}
}

b) For Gray code 1 bit should be 0 1,
for 2 bit should be 00 01 11 10 etc.

This algorithm does not start with lower values of n. All strings it generates have the same length,
and the i-th (for i = 1, ..., 2n-1) string is generated from the (i-1)-th one.

Here is the fist few steps for n = 4:

Start with G0 = 0000

To generate G1, flip 0-th bit in G0, as 0 is the position of the least significant 1 in the binary representation of 1 = 0001b. G1 = 0001.

To generate G2, flip 1-st bit in G1, as 1 is the position of the least significant 1 in the binary representation of 2 = 0010b. G2 = 0011.

To generate G3, flip 0-th bit in G2, as 0 is the position of the least significant 1 in the binary representation of 3 = 0011b. G3 = 0010.

To generate G4, flip 2-nd bit in G3, as 2 is the position of the least significant 1 in the binary representation of 4 = 0100b. G4 = 0110.

To generate G5, flip 0-th bit in G4, as 0 is the position of the least significant 1 in the binary representation of 5 = 0101b. G5 = 0111.

Add a comment
Know the answer?
Add Answer to:
a. Generate the binary reflexive Gray code of order 4. b. Trace the following nonrecursive algorithm...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT