QAM Modulation using Karnaugh-map walks

This article focused on constructing constellation for rectangular QAM modulation using Karnaugh-map walks. Exploit inherent property of Karnaugh-maps to construct Gray coded QAM constellation points.

Karnaugh Map walk 1 for QAM modulation
Figure 1: Karnaugh-Map walks
Karnaugh Map walk 2 for QAM modulation
Figure 2: Karnaugh-Map walks

M-ary Quadrature Amplitude Modulation (M-QAM)

In MQAM modulations, the information bits are encoded as variations in the amplitude and the phase of the signal. The M-QAM modulator transmits a series of information symbols drawn from the set m \in \{1,2, ..., M\}, with each transmitted symbol holding k bits of information (k = log_2(M)). To restrict the erroneous receiver decisions to single bit errors, the information symbols are Gray coded. The information symbols are then digitally modulated using a rectangular M-QAM technique, whose signal set is given by

equation for QAM modulated symbols

Karnaugh Map Walks and Gray Codes:

In any M-QAM constellation, in order to restrict the erroneous symbol decisions to single bit errors, the adjacent symbols in the transmitter constellation should not differ by more than one bit. This is usually achieved by converting the input symbols to Gray coded symbols and then mapping it to the desired QAM constellation. But this intermediate step can be skipped altogether by using a Look-Up-Table (LUT) approach which properly translates the input symbol to appropriate position in the constellation.

This article is part of the following books
Digital Modulations using Matlab : Build Simulation Models from Scratch, ISBN: 978-1521493885
Digital Modulations using Python ISBN: 978-1712321638
All books available in ebook (PDF) and Paperback formats

We will exploit the inherent property of Karnaugh Maps to generate the look-up table of dimension N \times N (where N= \sqrt{M} ) for the gray coded M-QAM constellation which is rectangular and symmetric (M=4, 16, 64, 256, …). The first step in constructing a QAM constellation is to convert a sequential numbers representing the message symbols to gray coded format. The function to convert decimal numbers to Gray codes is given next.

function [grayCoded]=dec2gray(decInput)
%convert decimal to Gray code representation
%example: x= [0 1 2 3 4 5 6 7] %decimal
%y=dec2gray(x); %returns y = [ 0 1 3 2 6 7 5 4] %Gray coded
[rows,cols]=size(decInput);
grayCoded=zeros(rows,cols);
for i=1:rows
   for j=1:cols
    grayCoded(i,j)=bitxor(bitshift(decInput(i,j),-1),decInput(i,j));
   end
end

If you are familiar with Karnaugh Maps (K-Maps) [1], it is easier for you to identify that the K-Maps are constructed based on Gray Codes. By the nature of the construction of K-Maps, the address of the adjacent cells differ by only one bit. If we supper impose the given M-QAM constellation on the K-Map and walk through the address of each cell in certain pattern, it gives the Gray-coded M-QAM constellation.

As mentioned, a walk through the K-Map will produce a sequence of gray codes. Moreover, if the walk can be looped back to the origin or starting point, it will generate a sequence of cyclic Gray codes. Different walking patterns are possible on K-Maps that generate different sequences of Gray codes. Some of the walks on a \(4 \times 4\) K-Map are shown in Figures 1 and 2. This can be readily extended to any K-Map configuration of higher order.

In walk types 1,3 and 4, the address of the starting point and end point differ by only one bit and the corresponding cells are adjacent to each other. In effect, the walk can be looped to give cyclic Gray codes. But in type 2 walk, the starting cell (0000 ) and the ending cell (1101) are not adjacent to each other and thus the Gray code generated using this pattern of walk is not cyclic. By far, type 1 walk is the simplest. All we have to do is alternate the direction of the walk for every row and read the gray coded address.

The Matlab function constructQAM.m given in the book implements (refer the book Digital Modulations using Matlab for the full Matlab code, python code is available in the book Digital Modulations using Python) the walk type 1 for constructing a MQAM constellation.

Rectangular QAM from PAM constellation

There exist other constellation shapes (like circular, triangular constellations) that are more efficient (in terms of energy required to achieve same the error probability) than the standard rectangular constellation. Rectangular (symmetric or square) constellations are the preferred choice of implementation due to its simplicity in implementing modulation and demodulation.

Any rectangular QAM constellation is equivalent to superimposing two Amplitude Shift Keying (ASK) signals (also called Pulse Amplitude Modulation – PAM) on quadrature carriers. For example, 16-QAM constellation points can be generated from two 4-PAM signals, similarly the 64-QAM constellation points can be generated from two 8-PAM signals. The generic equation to generate PAM signals of dimension D is

equation for square QAM modulation using two PAM modulated symbols

For generating 16-QAM, the dimension D of PAM is set to D=\sqrt{16}=4. Thus for constructing a M-QAM constellation, the PAM dimension is set as D=\sqrt{M}. Matlab code for dynamically generating M-QAM constellation points based on Karnaugh map Gray code walk is given below. The resulting ideal constellations for Gray coded 16-QAM and 64-QAM are shown in following figure.

Signal space constellations for 16-QAM and 64-QAM
Figure 3: Signal space constellations for 16-QAM and 64-QAM

Rate this article : PoorBelow averageAverageGoodExcellent (5 votes, average: 4.80 out of 5)

For further reading

[1] C. E. Stroud, “Karnaugh Maps (K-map) – Combinational Logic Minimization”, course notes, Auburn University↗

Related topics in this chapter

Digital Modulators and Demodulators - Complex Baseband Equivalent Models
Introduction
Complex baseband representation of modulated signal
Complex baseband representation of channel response
● Modulators for amplitude and phase modulations
 □ Pulse Amplitude Modulation (M-PAM)
 □ Phase Shift Keying Modulation (M-PSK)
 □ Quadrature Amplitude Modulation (M-QAM)
● Demodulators for amplitude and phase modulations
 □ M-PAM detection
 □ M-PSK detection
 □ M-QAM detection
 □ Optimum detector on IQ plane using minimum Euclidean distance
● M-ary FSK modulation and detection
 □ Modulator for M orthogonal signals
 □ M-FSK detection

Books by the author

Wireless Communication Systems in Matlab
Wireless Communication Systems in Matlab
Second Edition(PDF)

PoorBelow averageAverageGoodExcellent (159 votes, average: 3.81 out of 5)

Digital modulations using Python
Digital Modulations using Python
(PDF ebook)

PoorBelow averageAverageGoodExcellent (122 votes, average: 3.60 out of 5)

digital_modulations_using_matlab_book_cover
Digital Modulations using Matlab
(PDF ebook)

PoorBelow averageAverageGoodExcellent (125 votes, average: 3.69 out of 5)

Hand-picked Best books on Communication Engineering
Best books on Signal Processing

 

3 thoughts on “QAM Modulation using Karnaugh-map walks”

Post your valuable comments !!!