Sunday 1 December 2013

Recusive NBit- GrayCode Generator in C++


While Reading tutorials on, one of the , educational institutes website , I have found this interesting property about Gray codes , so i tried implementing it  in C++.

Gray code : The Gray code , is a binary numeral system where two successive values differ in only one bit. It is a non-weighted code.
The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.
For More Information please refer wiki : http://en.wikipedia.org/wiki/Gray_code

Recursive Algorithm :
1. Write down the Gray code for N – 1 bits.
2. Copy that same list in reverse order below the original one.
3. Add a 0 bit in front of the codings in the original half of the list and a 1 bit in
front of those in the reversed copy.

C++ Code :

/*
* Author :  Nitendra Bhosle
*/
#include <iostream>
#include <vector>
#include <string>

void nBitGrayCodeGenerator(int n,std::vector<std::string>& resultVec)
{
 //Simple Case
 if(n ==1)
 {
  std::string zero = "0";
  std::string one = "1";
  resultVec.push_back(zero);
  resultVec.push_back(one);
 }
 else //Recursively solve problem by deviding it in simpler problems
 {
  std::vector<std::string> temp ;
  nBitGrayCodeGenerator(n-1,temp);

  for(int i = 0;i<temp.size();++i)
  {
   std::string res = "0"+temp[i];
   resultVec.push_back(res);
  }

  for(int i = temp.size()-1;i>=0;--i)
  {
   std::string res = "1"+temp[i];
   resultVec.push_back(res);
  }
 }
}

int main(void)
{
 std::vector<std::string> resultVec;

 nBitGrayCodeGenerator(4,resultVec);

 for(int i=0;i<resultVec.size();++i)
 {
  std::cout<<"\n"<<resultVec[i];
 }

 int halt;
 std::cin>>halt;

 return 0;
}



Result :  5-Bit GrayCode , generated from the above program

00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000

No comments :

Post a Comment