Hi All,

Can you please point me to reference(s) explaining the construction of
Binary to Gray code conversion
for a general QAM constellation.

I just know that the QAM maybe treated as independent PAM links + some
added constraints to ensure
that the adjacent constellation points differ by only one bit.

Thanks,
Krishna
~blogs @ http://www.dsplog.com

Krishna wrote:
> Hi All,
> 
> Can you please point me to reference(s) explaining the construction of
> Binary to Gray code conversion
> for a general QAM constellation.
> 
> I just know that the QAM maybe treated as independent PAM links + some
> added constraints to ensure
> that the adjacent constellation points differ by only one bit.
> 
> Thanks,
> Krishna
> ~blogs @ http://www.dsplog.com

To convert binary to Gray: x XOR (x >> 1)
See http://www.dspguru.com/comp.dsp/tricks/alg/grayconv.htm

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

On May 11, 6:53 pm, Jerry Avins <j...@ieee.org> wrote:
>
> To convert binary to Gray: x XOR (x >> 1)
> Seehttp://www.dspguru.com/comp.dsp/tricks/alg/grayconv.htm
>
> Jerry
> --
> Engineering is the art of making what you want from things you can get.
> =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF

Thanks for the link. If I may write the equivalent Matlab/Octave code

% ------- start
clear
% binary to Gray code
ipBin =3D [0:15]
opGray =3D bitxor(ipBin,floor(ipBin/2))

% Gray code to binary
opBin =3D bitxor(opGray,floor(opGray/2^8))
opBin =3D bitxor(opBin,floor(opBin/2^4))
opBin =3D bitxor(opBin,floor(opBin/2^2))
opBin =3D bitxor(opBin,floor(opBin/2^1))
% ---- end

I was thinking of a simple LUT based approach for doing the Gray to
Binary. However, this approach looks neat. But,  am unable to figure
out how this trick works. Can you kindly provide further pointers and/
or hints.

Thanks again,
Krishna
~blogs @ http://www.dsplog.com

>On May 11, 6:53 pm, Jerry Avins <j...@ieee.org> wrote:
>>
>> To convert binary to Gray: x XOR (x >> 1)
>> Seehttp://www.dspguru.com/comp.dsp/tricks/alg/grayconv.htm
>>
>> Jerry
>> --
>> Engineering is the art of making what you want from things you can
get.
>>
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF
>
>Thanks for the link. If I may write the equivalent Matlab/Octave code
>
>% ------- start
>clear
>% binary to Gray code
>ipBin =3D [0:15]
>opGray =3D bitxor(ipBin,floor(ipBin/2))
>
>% Gray code to binary
>opBin =3D bitxor(opGray,floor(opGray/2^8))
>opBin =3D bitxor(opBin,floor(opBin/2^4))
>opBin =3D bitxor(opBin,floor(opBin/2^2))
>opBin =3D bitxor(opBin,floor(opBin/2^1))
>% ---- end
>
>I was thinking of a simple LUT based approach for doing the Gray to
>Binary. However, this approach looks neat. But,  am unable to figure
>out how this trick works. Can you kindly provide further pointers and/
>or hints.
>
>Thanks again,
>Krishna
>~blogs @ http://www.dsplog.com
>

%%%%%%

I am assuming that u want to apply 4-QAM using gray mapping.

Now, start from 1st quadrant i.e. ++ lets say u put 00 over there. So in
the left quadrant u can put either 10 or 01. lets say 01. so in the thrid
quadrant u will put 11 and in the fourth quadrant u will put 10. This
mapping gives u grap mapping.

Now to generate this in matlab:
clc, clear all;
x=randint(1,100); % 100 bits
x_r=reshape(x,2,50).'; % 50 rows, 2 columns
x_d=bi2de(x_r,'left-msb'); % gives u symbols 0-3, 0=00, 1=01, 2=10, 3=11

for i=1:length(x_d)
    if(x_d(i)==0)
        y(i)=1+j*1;
    elseif (x_d(i)==1)
        y(i)=-1+j*1;
    elseif (x_d(i)==2)
        y(i)=1-j*1;
    else
        y(i)=-1-j*1;
    end
end

The above code is tested and works fine.

Hope this helps.

Chintan

k...@dsplog.com wrote:
> On May 11, 6:53 pm, Jerry Avins <j...@ieee.org> wrote:
>> To convert binary to Gray: x XOR (x >> 1)
>> Seehttp://www.dspguru.com/comp.dsp/tricks/alg/grayconv.htm
>>
>> Jerry
>> --
>> Engineering is the art of making what you want from things you can get.
>> ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
> 
> Thanks for the link. If I may write the equivalent Matlab/Octave code
> 
> % ------- start
> clear
> % binary to Gray code
> ipBin = [0:15]
> opGray = bitxor(ipBin,floor(ipBin/2))
> 
> % Gray code to binary
> opBin = bitxor(opGray,floor(opGray/2^8))
> opBin = bitxor(opBin,floor(opBin/2^4))
> opBin = bitxor(opBin,floor(opBin/2^2))
> opBin = bitxor(opBin,floor(opBin/2^1))
> % ---- end
> 
> I was thinking of a simple LUT based approach for doing the Gray to
> Binary. However, this approach looks neat. But,  am unable to figure
> out how this trick works. Can you kindly provide further pointers and/
> or hints.

The way to do it with gates (4 bits; extend to n) is

G3  o-------------------o B3
     |
     o---|¯¯¯¯¯|
         | XOR |-----+---o B2
G2  o---|_____|     |
     ________________|
     |
     o---|¯¯¯¯¯|
         | XOR |-----+---o B1
G1  o---|_____|     |
     ________________|
     |
     o---|¯¯¯¯¯|
         | XOR |---------o B0
  G0 o---|_____|

Except for ripple-through, this is O(1). The straight-forward conversion 
to software is O(n). Observe that each Gray bit is XORed with *all* the 
lower bits, not just the one immediately below. My method XORs bits in 
parallel to do the same thing in O(log(n)) Nuff said?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

On Sun, 11 May 2008 17:09:01 -0400, Jerry Avins <j...@ieee.org> wrote:

>k...@dsplog.com wrote:
>> On May 11, 6:53 pm, Jerry Avins <j...@ieee.org> wrote:
>>> To convert binary to Gray: x XOR (x >> 1)
>>> Seehttp://www.dspguru.com/comp.dsp/tricks/alg/grayconv.htm
>>>
>>> Jerry
>>> --
>>> Engineering is the art of making what you want from things you can get.
>>> ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
>> 
>> Thanks for the link. If I may write the equivalent Matlab/Octave code
>> 
>> % ------- start
>> clear
>> % binary to Gray code
>> ipBin = [0:15]
>> opGray = bitxor(ipBin,floor(ipBin/2))
>> 
>> % Gray code to binary
>> opBin = bitxor(opGray,floor(opGray/2^8))
>> opBin = bitxor(opBin,floor(opBin/2^4))
>> opBin = bitxor(opBin,floor(opBin/2^2))
>> opBin = bitxor(opBin,floor(opBin/2^1))
>> % ---- end
>> 
>> I was thinking of a simple LUT based approach for doing the Gray to
>> Binary. However, this approach looks neat. But,  am unable to figure
>> out how this trick works. Can you kindly provide further pointers and/
>> or hints.
>
>The way to do it with gates (4 bits; extend to n) is
>
>G3  o-------------------o B3
>     |
>     o---|¯¯¯¯¯|
>         | XOR |-----+---o B2
>G2  o---|_____|     |
>     ________________|
>     |
>     o---|¯¯¯¯¯|
>         | XOR |-----+---o B1
>G1  o---|_____|     |
>     ________________|
>     |
>     o---|¯¯¯¯¯|
>         | XOR |---------o B0
>  G0 o---|_____|
>
>Except for ripple-through, this is O(1). The straight-forward conversion 
>to software is O(n). Observe that each Gray bit is XORed with *all* the 
>lower bits, not just the one immediately below. My method XORs bits in 
>parallel to do the same thing in O(log(n)) Nuff said?
>
>Jerry

There's an added dimension, though, in that for gray coding to get the
best performance in QAM the symbols need to be assigned such that no
adjacent decision regions differ by more than a bit.    That can be
done strictly with symbol assignment and doesn't really need a
conversion from the data to the linear code mapping that you've shown.
i.e., you can take the data directly and just assing the appropriate
symbol from the constellation map.

In other words, for QAM what matters is where the codes land with
respect to the decision regions in the constellation, not on a number
line.



Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.ericjacobsen.org

On May 12, 3:17 am, Eric Jacobsen <eric.jacob...@ieee.org> wrote:

> There's an added dimension, though, in that for gray coding to get the
> best performance in QAM the symbols need to be assigned such that no
> adjacent decision regions differ by more than a bit.    That can be
> done strictly with symbol assignment and doesn't really need a
> conversion from the data to the linear code mapping that you've shown.
> i.e., you can take the data directly and just assing the appropriate
> symbol from the constellation map.
>
> In other words, for QAM what matters is where the codes land with
> respect to the decision regions in the constellation, not on a number
> line.

Thanks Eric & Chintan. I agree with your comments. However, I am
looking for rules (read equations)
which I can apply for a general M-QAM square constellation.

The closest I ve got is to look at the bin2gray() function in Matlab
and try to figure out
the code....

Thanks again,
Krishna
~blogs @ http://www.dsplog.com

Eric Jacobsen wrote:
> On Sun, 11 May 2008 17:09:01 -0400, Jerry Avins <j...@ieee.org> wrote:
> 
>> k...@dsplog.com wrote:
>>> On May 11, 6:53 pm, Jerry Avins <j...@ieee.org> wrote:
>>>> To convert binary to Gray: x XOR (x >> 1)
>>>> Seehttp://www.dspguru.com/comp.dsp/tricks/alg/grayconv.htm
>>>>
>>>> Jerry
>>>> --
>>>> Engineering is the art of making what you want from things you can get.
>>>> ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
>>> Thanks for the link. If I may write the equivalent Matlab/Octave code
>>>
>>> % ------- start
>>> clear
>>> % binary to Gray code
>>> ipBin = [0:15]
>>> opGray = bitxor(ipBin,floor(ipBin/2))
>>>
>>> % Gray code to binary
>>> opBin = bitxor(opGray,floor(opGray/2^8))
>>> opBin = bitxor(opBin,floor(opBin/2^4))
>>> opBin = bitxor(opBin,floor(opBin/2^2))
>>> opBin = bitxor(opBin,floor(opBin/2^1))
>>> % ---- end
>>>
>>> I was thinking of a simple LUT based approach for doing the Gray to
>>> Binary. However, this approach looks neat. But,  am unable to figure
>>> out how this trick works. Can you kindly provide further pointers and/
>>> or hints.
>> The way to do it with gates (4 bits; extend to n) is
>>
>> G3  o-------------------o B3
>>     |
>>     o---|¯¯¯¯¯|
>>         | XOR |-----+---o B2
>> G2  o---|_____|     |
>>     ________________|
>>     |
>>     o---|¯¯¯¯¯|
>>         | XOR |-----+---o B1
>> G1  o---|_____|     |
>>     ________________|
>>     |
>>     o---|¯¯¯¯¯|
>>         | XOR |---------o B0
>>  G0 o---|_____|
>>
>> Except for ripple-through, this is O(1). The straight-forward conversion 
>> to software is O(n). Observe that each Gray bit is XORed with *all* the 
>> lower bits, not just the one immediately below. My method XORs bits in 
>> parallel to do the same thing in O(log(n)) Nuff said?
>>
>> Jerry

Krishna,

I didn't give you the best answer. I replied to the question og Gray 
code in general instead of confining myself to QAP on particular. A LUT 
is appropriate when the largest number is small.

> There's an added dimension, though, in that for gray coding to get the
> best performance in QAM the symbols need to be assigned such that no
> adjacent decision regions differ by more than a bit.    That can be
> done strictly with symbol assignment and doesn't really need a
> conversion from the data to the linear code mapping that you've shown.
> i.e., you can take the data directly and just assing the appropriate
> symbol from the constellation map.
> 
> In other words, for QAM what matters is where the codes land with
> respect to the decision regions in the constellation, not on a number
> line.

Eric,

That's the same thing. Just as unsigned and two's complement numbers 
form a number circle, so do Gray codes. In fact, Gray codes are used on 
encoder wheels where the circularity is evident. There's an illustration 
at http://www.scienceprog.com/using-gray-code-for-rotary-encoders/

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

On Sun, 11 May 2008 22:49:33 -0400, Jerry Avins <j...@ieee.org> wrote:

>Eric Jacobsen wrote:
>> On Sun, 11 May 2008 17:09:01 -0400, Jerry Avins <j...@ieee.org> wrote:
>> 
>>> k...@dsplog.com wrote:
>>>> On May 11, 6:53 pm, Jerry Avins <j...@ieee.org> wrote:
>>>>> To convert binary to Gray: x XOR (x >> 1)
>>>>> Seehttp://www.dspguru.com/comp.dsp/tricks/alg/grayconv.htm
>>>>>
>>>>> Jerry
>>>>> --
>>>>> Engineering is the art of making what you want from things you can get.
>>>>> ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
>>>> Thanks for the link. If I may write the equivalent Matlab/Octave code
>>>>
>>>> % ------- start
>>>> clear
>>>> % binary to Gray code
>>>> ipBin = [0:15]
>>>> opGray = bitxor(ipBin,floor(ipBin/2))
>>>>
>>>> % Gray code to binary
>>>> opBin = bitxor(opGray,floor(opGray/2^8))
>>>> opBin = bitxor(opBin,floor(opBin/2^4))
>>>> opBin = bitxor(opBin,floor(opBin/2^2))
>>>> opBin = bitxor(opBin,floor(opBin/2^1))
>>>> % ---- end
>>>>
>>>> I was thinking of a simple LUT based approach for doing the Gray to
>>>> Binary. However, this approach looks neat. But,  am unable to figure
>>>> out how this trick works. Can you kindly provide further pointers and/
>>>> or hints.
>>> The way to do it with gates (4 bits; extend to n) is
>>>
>>> G3  o-------------------o B3
>>>     |
>>>     o---|¯¯¯¯¯|
>>>         | XOR |-----+---o B2
>>> G2  o---|_____|     |
>>>     ________________|
>>>     |
>>>     o---|¯¯¯¯¯|
>>>         | XOR |-----+---o B1
>>> G1  o---|_____|     |
>>>     ________________|
>>>     |
>>>     o---|¯¯¯¯¯|
>>>         | XOR |---------o B0
>>>  G0 o---|_____|
>>>
>>> Except for ripple-through, this is O(1). The straight-forward conversion 
>>> to software is O(n). Observe that each Gray bit is XORed with *all* the 
>>> lower bits, not just the one immediately below. My method XORs bits in 
>>> parallel to do the same thing in O(log(n)) Nuff said?
>>>
>>> Jerry
>
>Krishna,
>
>I didn't give you the best answer. I replied to the question og Gray 
>code in general instead of confining myself to QAP on particular. A LUT 
>is appropriate when the largest number is small.
>
>> There's an added dimension, though, in that for gray coding to get the
>> best performance in QAM the symbols need to be assigned such that no
>> adjacent decision regions differ by more than a bit.    That can be
>> done strictly with symbol assignment and doesn't really need a
>> conversion from the data to the linear code mapping that you've shown.
>> i.e., you can take the data directly and just assing the appropriate
>> symbol from the constellation map.
>> 
>> In other words, for QAM what matters is where the codes land with
>> respect to the decision regions in the constellation, not on a number
>> line.
>
>Eric,
>
>That's the same thing. Just as unsigned and two's complement numbers 
>form a number circle, so do Gray codes. In fact, Gray codes are used on 
>encoder wheels where the circularity is evident. There's an illustration 
>at http://www.scienceprog.com/using-gray-code-for-rotary-encoders/
>
>Jerry

Yes, and if the constellation were strictly PSK, i.e., traced a
circle, that would be all you'd need.   With a QAM grid, though, one
constellation point has potentially eight neighbors (not just two,
like on a line or in a circle), and, ideally, you'd like only one bit
to differ with each of them.  With low-order QAM (e.g., 16-QAM),
that's not possible, so one tries to manage the decision regions to
maximize the Euclidean distance while minimizing the Hamming distance.



Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.ericjacobsen.org

On May 12, 12:12 am, Eric Jacobsen <eric.jacob...@ieee.org> wrote:

> >Jerry
>
> Yes, and if the constellation were strictly PSK, i.e., traced a
> circle, that would be all you'd need.   With a QAM grid, though, one
> constellation point has potentially eight neighbors (not just two,
> like on a line or in a circle), and, ideally, you'd like only one bit
> to differ with each of them.  With low-order QAM (e.g., 16-QAM),
> that's not possible, so one tries to manage the decision regions to
> maximize the Euclidean distance while minimizing the Hamming distance.
>
> Eric Jacobsen
> Minister of Algorithms
> Abineau Communicationshttp://www.ericjacobsen.org

In all the messages in this thread with splendid examples
of MATLAB code and snippets of C operators and so on,
there has been little attention paid to the specific application
to QAM, and I think that Eric's comment about low-order QAM
is misleading in some respects.  My response discusses only
M-QAM where M = 2^{2n} as opposed to the general M-QAM
desired by the OP, with 16-QAM as an example.

An 2^{2n}-QAM signal is the sum of two 2^n-ASK signals transmitted
on the I and Q channels, with each channel carrying n bits.  The
mapping of data bits to signal constellation point on each channel
must correspond to Gray coding, but the Gray coding is not
explicit.  For example, in 16-QAM with 4 data bits (b_3,b_2,b_1,b_0),
one could send b_3 and b_2 using 4-ASK on the I channel  and
b_1 and b_0 using 4-ASK on the Q channel.  (Some might prefer
to send the odd-numbered bits on the I channel and the even-
numbered bits on the Q channel instead).  The mapping of
data bits to signal point is *effectively* Gray coding, with (for
example) 00, 01, 11, and 10 corresponding to signal levels
-3, -1, +1, and +3 respectively.  The DATA bits themselves
don't need to be transformed to Gray code explicitly because if
I give you bits 11, you cannot say whether I mean 3 (standard
binary coding) or 2 (Gray coding) UNLESS I tell you what
coding I was using when I produced the 11.  All the modulator
needs to know is that if the modulator input is 11, it needs to
produce output +1 and if the input is 10, it needs to produce
+3 etc.  Now, those who want to implement the modulator as
a LINEAR modulator can write code which says that my input
can take on values 00, 01, 11, and 10 which is Gray-coded
(actually it isn't Gray-coded or anything: it is raw data) which
thus represents 0, 1, 2, and 3 respectively, The output I have
to produce is -3 + 2A where A is the integer value of my
Gray-coded data input.  But remember that the data source
just handed the modulator two bits without saying anything
about whether the bits are Gray-coded or not.  It is the LINEAR
modulator which is treating these bits as Gray-coded and
converting them to standard binary representation (that is,
applying the inverse Gray-code mapping!) so as to be able to
use its magic formula -3+2A to produce the output.  A
modulator that is not quite as anal-retentive might just use
a LUT to translate data bits 00, 01, 11, and 10 into signal levels
-3, -1, +1, and +3 which uses Gray coding implicitly but not
explicitly.

Returning to 16-QAM, the 4-bit nybble (0111) is split into 01 and
11, and mapped to the signal constellation point (-1, +1) via
two modulators.  The 16-QAM constellation thus looks like

       -3       -1       +1     +3

+3  0010  0110  1110  1010

+1  0011  0111  1111  1011

-1  0001  0101  1101  1001

-3  0000  0100  1100  1000

where each constellation point differs from its 4 NEAREST
neighbors (distance 2) in one bit and from its 4 NEXT
NEAREST neighbors by 2 bits.  The latter have less effect
on the overall BER as compared to the 4 NEAREST neighbors
and so it matters less that the difference is two bits.

If the signal point (-1, +1) is transmitted and (X, Y) received,
then X and Y are each quantized into 4 levels
(-3, -1, +1, +3) and if the quantized X and Y are -1 and +1
respectively, then the demodulator output is 0111.  There
is no need for the demodulator to do do anything else, or
to translate the bits from Gray code back to standard binary
representation etc.  All that is built in to the demodulator
LUTs.  The harder way of doing this is to remember that
the modulator used the formula -3+2A to get +1, and so
A is given by (+1 + 3)/2 = 2, but since Gray coding is
being used, the output should be the Gray-coded version
of 2, viz. 11.

--Dilip Sarwate