0
$\begingroup$

I have a simple question on how to implement SD for non-binary modulation, let say QPSK. Assume we transmit a complex symbol $\overline{a}$ drawn from a QPSK constellation. On a vector form, we can write the receive signal as $$\overline{y} = \overline{G} \: \overline{a} + \overline{w},$$ where $\overline{G}$ is the channel matrix and $\overline{w}$ is the complex noise samples. To detect $\overline{a}$ from $\overline{y}$, we can use maximum likelihood (ML) detection or to simplify the detection we use sphere decoding (SD).

To use SD, the above equation can be rewritten in a real-valued form as $${y} = {G} \: {a} + {w},$$ where $y = \begin{bmatrix} \Re\{{\overline{y}}\}\\ \Im\{{\overline{y}}\} \end{bmatrix},$ $G = \begin{bmatrix} \Re\{{\overline{G}}\} & - \Im\{{\overline{G}}\}\\ \Im\{{\overline{G}}\} & \Re\{{\overline{G}}\} \end{bmatrix},$ $a = \begin{bmatrix} \Re\{{\overline{a}}\}\\ \Im\{{\overline{a}}\} \end{bmatrix},$ $w = \begin{bmatrix} \Re\{{\overline{w}}\}\\ \Im\{{\overline{w}}\} \end{bmatrix}$, $\Re$ and $\Im$ are the real and imaginary parts of complex numbers. Now, the SD can be applied directly with no problems no the new problem of double the dimension.

My question is can we apply two parallel versions of the SD algorithm, one to detect the real part and the other to detect the imaginary part?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ you can't – the euclidean distance only makes sense in context of $y$ being twodimensional. Also, you should maybe explain why SD is simpler than ML here – as far as I can tell, the ML decision "boundaries" are much easier in QPSK than your circles (spheres) ... $\endgroup$
    – Marcus Müller
    Jan 13, 2017 at 15:59
  • 1
    $\begingroup$ Not in any trivial way, but search for "parallel sphere decoder" in Google scholar or similar engines: there are many results that can help you speed up the SD algorithm, and still find an optimum solution (or close to). $\endgroup$
    – MBaz
    Jan 13, 2017 at 16:03
  • 1
    $\begingroup$ @MarcusMüller The SD in general is much more efficient than a brute-force ML search because you evaluate a much reduced number of possible vectors $a$. $\endgroup$
    – MBaz
    Jan 13, 2017 at 16:05
  • $\begingroup$ @MBaz well in the general case, yes, but for a QPSK, the ML boundaries are simply the coordinate axes of the complex plane, so ML detection is a simple 4-LUT on the signs of Re, Im $\endgroup$
    – Marcus Müller
    Jan 13, 2017 at 16:57
  • $\begingroup$ @MarcusMüller I think you might be missing the fact that $G$ is a vector of channel gains; in other words, this is a SIMO system with 1 transmiter and $N$ receivers. The vector $y$ has $N$ elements, and you can't just apply the QPSK threshold to its elements. I agree that in this case the SD won't be much help since $a$ has only four possible values, but for larger constellations or MIMO systems, the SD makes a tremendous difference. $\endgroup$
    – MBaz
    Jan 13, 2017 at 17:36

2 Answers 2

Reset to default
2
$\begingroup$

This channel model is known as a multiplicative channel, and it differs from the AWGN channel in that the signal amplitude is scaled by a gain factor.

If the gain factor is real (that is, if the channel simply attenuates the signal), then we can write $\Re (y) = G\Re(a) + \Re(w)$ and $\Im(y) = G\Im(a)+\Im(w)$. In other words, the real and imaginary parts of the received signal are orthogonal and they can be detected separately.

In a case like this, using SD is overkill. For instance, if the transmitted constellation is QPSK, the optimum detection problem involves calculation of four distances in $\mathbb{R}^2$, which is not a hard problem. Furthermore, the symmetry of QPSK actually reduces the problem to that of finding in which quadrant $y$ lives in, which involves two sign checks.

To make things more interesting, consider a flat-fading wireless channel, where the gain $G$ is complex. In this channel, $\Re(y)$ depends on both the real and the imaginary parts of $a$, so the problem cannot be neatly separated in two anymore. If we write $G=|G|e^{j2\pi\angle{G}}$, then we can see that the wireless channel rotates and scales the transmitted constellation.

Even more interesting is the case where we have receive diversity, or mulitple receiver antennas operating concurrently. In this case $G$ becomes a vector, each element of which is the complex channel gain between the transmitter and one receiver. Now, $y$ is also a vector. For a large number of antennas and/or a large constellation, the problem of estimating $y$ becomes more and more complex.

Consider the case where we use 32-QAM and 4 receiver antennas. The ML calculation now involves calculating $32^4\approx10^6$ distances! And that is to estimate just a single symbol. It is in this situation that the SD algorithm starts to shine, since it can dramatically reduce the number of combinations to check.

Unfortunately, in a case like this the SD problem cannot be neatly separated into two. However, there are (more complex) ways to break the calculations into independent blocks that can be computed in parallel. Search for "parallel sphere decoder" in Google scholar or similar engines: there are many results that can help you speed up the SD algorithm, and still find an optimum solution (or close to).

Improve this answer
$\endgroup$
0
$\begingroup$

My question is can we apply two parallel versions of the SD algorithm, one to detect the real part and the other to detect the imaginary part?

You can't – the euclidean distance only makes sense in context of y being twodimensional.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I disagree with this answer: the Euclidean distance applies to one-dimensional geometry too, and the question is about a SIMO system, so $y$ is $N$-dimensional. $\endgroup$
    – MBaz
    Jan 13, 2017 at 17:42
  • $\begingroup$ @MBaz yes, that was my misunderstanding discussed in the comments to the question; but still, you can't reduce the calculation of a distance $|y-x_i| \in \mathbb C^N$ simply to two independent in $\mathbb R^N$ – pythagoras needs to take place, somewhere $\endgroup$
    – Marcus Müller
    Jan 13, 2017 at 18:04
  • 1
    $\begingroup$ Not like that, no. But don't forget that you can search for (maybe sub-) optimal solutions along a hyperplane subset of $\mathbb{C}^N$ -- in other words, you can proceed "one coordinate at a time". In QPSK over AWGN, you can solve for each coordinate independently of the other (solving two one-dimensional problems). In MIMO, V-BLAST would be a similar approach. I just felt that your answer could have been more nuanced in this sense. $\endgroup$
    – MBaz
    Jan 13, 2017 at 18:19
  • $\begingroup$ I am now confused. @MBaz mentioned that for QPSK over AWGN, you can solve for each coordinate independently of the other. So, this means the answer to my question is yes we can run two parallel SDs algorithms? $\endgroup$
    – Noor
    Jan 13, 2017 at 18:26
  • 2
    $\begingroup$ @Noor QPSK over AWGN corresponds to $G=1$. Nothing stops you from using SD in this case, but it's silly since the problem is trivial: just quantize the real and imaginary parts of $y$ as Marcus suggests. When $G$ is complex, you can no longer (trivially) break up the problem in two, because the real and imaginary parts of $a$ become "entangled". SD becomes useful when $G$ and/or the constellation have a large number of elements. $\endgroup$
    – MBaz
    Jan 13, 2017 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.