(10 votes, average: 3.50 out of 5)
Loading ...

# Binary to Gray code conversion for PSK and PAM

by on May 11, 2008

In this post, let us try to understand Gray codes and their usage in digital communication. Quoting from Wiki entry on Gray code [Gray-Wiki],

The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one digit.

In a digital communication system, if the constellation symbols are Gray encoded, then the bit pattern representing the adjacent constellation symbols differ by only one bit. We will show in another post that having this encoding structure gives a lesser probability of error than the ‘natural binary ordering’. However, in this post, let us try to figure out the conversion of natural binary representation to Gray code.

## Conversion from natural Binary to Gray code

Consider a $n$ bit binary number$b[n-1:0]$ with $j$ representing the index of the binary number. Let $g[n-1:0]$ be the equivalent Gray code.

1. For $j=n-1$,

$g[n-1] = b[n-1]$ i.e, the most significant bit (MSB) of the Gray code is same as the MSB of original binary number.

2. For $j=n-2\mbox{ to }0$,

$g[j]=b[j+1]\oplus b[j]$ i.e, $j^{th}$ bit of the Gray code is the exclusive-OR (XOR) of ${j}^{th}$ of the bit of the binary number and ${j+1}^{th}$ of the bit of the binary number.

## Simulation

Simple Matlab/Octave code for doing the binary to Gray code conversion

```clear; ip = [0:15]; % decimal equivalent of a four bit binary word op = bitxor(ip,floor(ip/2)); % decimal equivalent of the equivalent four bit gray word```

## Table : Natural Binary to Gray code

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

## Note

1. As can be seen from the Table above, each row differs from the row above and below by only one bit. Further, just to highlight that this behavior is indeed true for 16th row [1000] and the 1st row [0000] .

2. The conversion shown in the Table above can be used for general modulation schemes like M-PSK (Phase Shift Keying), M-PAM (Pulse Amplitude Modulation) etc.

3. However, for a general M-QAM modulation the binary to Gray code conversion is bit more complicated (and I need to figure that out). We will discuss the QAM case in a future post.

Thanks,
Krishna

D id you like this article? Make sure that you do not miss a new article by subscribing to RSS feed OR subscribing to e-mail newsletter. Note: Subscribing via e-mail entitles you to download the free e-Book on BER of BPSK/QPSK/16QAM/16PSK in AWGN.

{ 13 comments… read them below or add one }

Evolution January 15, 2013 at 5:17 pm

i have a little problem in the conversion illustrated above???
What to do if the binary number is not a simple binary number but a binary including the decimal???
For example what would be the gray code of 110101.101101???
Today i got this question in my engineering exam…???
i am in a great doubt…so please help me???

Reply

Krishna Sankar January 17, 2013 at 6:27 am

@Evolution: Well, can’t one ignore the decimal point (not sure though)?

Reply

Rishu April 10, 2011 at 9:40 pm

Thanks a lot. Your method is fundamental and helps to understand the conversion properly.

Reply

Krishna Sankar May 26, 2011 at 5:52 am

@Rishu: Thanks, glad to help.

Reply

vijay j December 8, 2009 at 4:14 pm

Dear Sir,

Kindly send me the free e-book on AWGN, I am already a memebr.

Thankyou
Vijay

Reply

Krishna Sankar December 10, 2009 at 6:02 am

@vijay: I emailed you the details.

Reply

O.S.O October 22, 2009 at 9:32 am

Yes, i agree (strange) !
Disregarding the way of implementation of bitshift/floor under Matlab/Octave, it is well known that (Bit Shifting) is faster than any multiplication/division method, specially on microprocessors.

Reply

Krishna Sankar October 27, 2009 at 5:29 am

@O.S.O: I agree

Reply

O.S.O October 8, 2009 at 2:21 am

Great job
i just wanted to mention that this snippet :
``` op = bitxor(ip,floor(ip/2)); ```
can be more optimized by just doing a right-shift bit by 1.
so the equivalent code would be :
``` bitxor(ip,bitshift(ip,-1)); ```
-1 means a 1 bit shift to the right (the negative sign means right).

Reply

Krishna Sankar October 9, 2009 at 5:36 am

@O.S.O: Thanks for the tip. However, I did a quick experiment with octave using tic-toc and did not observe that using bitshift() instead of floor is faster.
octave:51> clear all; tic; ip = [0:2^20-1];op = bitxor(ip,floor(ip/2));toc
Elapsed time is 0.4 seconds.
octave:52> clear all; tic;ip1 = [0:2^20-1];op1 = bitxor(ip1,bitshift(ip1,-1));toc
Elapsed time is 0.46 seconds.

Agree?

Reply

suraj kumar September 14, 2008 at 10:36 am

i liked your method of conversion very much.
so
thanks

Reply

Krishna Sankar August 21, 2008 at 1:25 pm

@elizabeth: Well, you can use the steps 1, 2 in “Conversion from natural Binary to Gray code” to write your own code. No?

Reply

elizabeth August 19, 2008 at 10:33 pm

i am doing engg…. thanks for the quick reference…. please also include how to do it in order… egs why does the 1001 follow 1011..how should we write it on our own….. in a sequence such that we can make a tabulation table to draw the logic diagram of a code converter from binary to grey etc!

Reply

{ 1 trackback }

Previous post: