22
\$\begingroup\$

"Stand-Up Maths" recently did a video about QAM/data encoding. He presented a diagram of the encoding spacing for QAM:
Huawei provided QAM 16 diagram

I'm from a software engineering background and I couldn't help but think: given that telecommunication companies are always aiming to get more out of the existing infrastructure, why not use a more efficient pattern for a QAM-like encoding scheme?

My original thought was a equilateral triangle spacing:

a grid of dots spaced as the vertex's of a plane of equilateral triangles

It satisfies some of the design parameters mentioned in the video (avoiding passing over the origin).

A triangular grid is about 2.3 times denser (the area of a equilateral triangle is about 0.43 with a grid spacing of 1).

My primary question is: what is the limiting factor for such a standard?

  • Is it too complex to decode?
  • Maybe it doesn't offer any measurable benefit?
  • Could it be that a grid follows the same power of 2 expansion rate and that's just easier?
  • Perhaps larger encoding spaces can be achieved with increasing the maximum amplitude, rather than a more complex system?
  • Backwards compatibility?
  • Perhaps there isn't a single bit change "Gray code" system to traverse a triangular graph?
\$\endgroup\$
6
  • 3
    \$\begingroup\$ @Kubahasn'tforgottenMonica you're right, but Joshua is also right: packing the same number of points denser, or putting more points in the same area, yields higher spectral efficiency, which, in the end, is what we communications engineers sacrifice tofu kittens in obscure mathematical rituals for! \$\endgroup\$ Feb 29 at 22:49
  • 1
    \$\begingroup\$ @MarcusMüller I'll have to work the numbers for that, because my gut feel is that the difference isn't as dramatic as it may seem. In the ballpark of 10% maybe? \$\endgroup\$ Feb 29 at 22:52
  • \$\begingroup\$ If I remember the math for 64QAM and larger: Less, actually, even if you're smarter than a triangular lattice, but try to optimize the actual positions of 16 points with a constant average power constraint. But: 10% is a lot, in terms of modern channel coder performance (for fixed word lengths)! \$\endgroup\$ Feb 29 at 23:04
  • 4
    \$\begingroup\$ Please don't ask new questions in an existing question that you've already gotten answers to. Instead, open a new question. \$\endgroup\$ Mar 1 at 9:24
  • 2
    \$\begingroup\$ I'm removing the "New question" from your post. Please ask it in a new question post, if you want to ask it! \$\endgroup\$ Mar 1 at 13:57

3 Answers 3

22
\$\begingroup\$

My original thought was a equilateral triangle spacing:

Some, more obscure standards, use such or similar schemes, indeed.

  • Is it to complex to decode?

That's the main reason.

  • Maybe it doesn't offer any measurable benefit?

For a couple of decades, that was the case, but with modern channel coding, these additional (fractions of) bits you can transport per symbol start to pay of: That's why on high-SNR channels with very high rates, you see custom constellations. (Look for what people are doing for 400 Gb/s fiber optical communications.)

In fact, constellation shaping is a science of its own; there's more optimization objectives than just the bits per average power you can theoretically squeeze through; immunity to phase distortion, or ability to still synchronize well are important.

  • Could it be that a grid follows the same power of 2 expansion rate and that's just easier?

What's very nice about square grids is that one half of the "remaining" grid always encodes 1 bit (under Gray coding). Is the value I received in the left or right half of the complex plane? That's the first bit. Is it above or below the real axis? the second bit. In the remaining quadrant, is it left or right of the middle? third bit. And so on.

Furthermore, this gives you a direct method to calculate soft bits through likelihoods; essentially, how far on this "halving" of the remaining space you are away from the decision boundary directly translates into a certainty. And if you use these certainties instead of only the already "decided" bits in your channel decoder, you can correct finer, and get more bits through. This makes QAM constellations desirable for soft decoding; and that has more advantage over hard decoding (i.e. after your constellation demapper has already mapped the noisy received symbol to bits that might be wrong, without telling how likely they are wrong) than denser packings have compared to QAM.

But: we've (as a field) have been better the last decades about building decoders and learning to formulate soft information even for irregular constellations. This advantage is slipping, and it's more and more becoming a problem of complexity!

  • Perhaps larger encoding spaces can be achieved with increasing the maximum amplitude, rather than a more complex system?

Larger maximum amplitude is highly undesirable. Two options:

  1. you increase not only the maximum amplitude and thus power, but also the average. But then you just put more power into your transmitter! Can't do that; if that was an option, you would have done it in the first place to get better SNR.
  2. you don't increase your average power, but increase your peak power, increasing the distance between that and "closer to origin" constellation points. That's undesirable, because then more points are closer together close to the origin (higher error probability), and also, you get Peak-to-Average-Power (PAPR) problems, meaning you need more expensive and less power-efficient amplifiers in both the transmitter and the receiver. Big "do not want," technologically.
  • backwards compatibility?

Sure, but if that was the argument, we'd still be using Morse code to get our morning cat videos via 5G.

  • perhaps there isn't a single bit change "grey code" system to traverse a triangular graph?

yes, for your constellation I don't think there's a Gray code (capital G, that guy's name was Frank Gray). In general, you can do clever things that belong in the category of Space-Time codes (essentially, get another dimension by combining multiple symbols into one constellation point), and find equivalents to Gray coding in higher dimension with tighter sphere packings still! But again, complexity constraints strike.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ I disagree that the decoding complexity is a concern today. Today, the decoding is done in ASICs, and there's no worthwhile difference in silicon area that would be taken up by a more complex pattern in the decoder. Back in the day when the decoders used discrete logic etc., it was indeed a concern. \$\endgroup\$ Feb 29 at 22:46
  • 4
    \$\begingroup\$ @Kubahasn'tforgottenMonica but it really is. Decoding is one of the major power consumers in battery driven mobile communication devices (i.e, phones); just because we can doesn't mean we can afford to. You're of course not wrong – when we have to distinguish 16 points in a rectangular or triangular grid, the decision complexity barely matters. However, and that's why I mention that explicitly, soft decoding is state of the art, and with equilateral triangles, the clostest-neighbor approximation for error probabilities breaks down (the neighbors are not on orthogonal axes, and there's a \$\endgroup\$ Feb 29 at 22:54
  • 6
    \$\begingroup\$ non-power of two number of them), so that you can't calculate softbits based on the position of a received symbol within one single "cell" within the constellation lattice anymore. The moment your softbit calculation is no longer the purely distance-based log-likelihood ratio anymore, you're going to have a bad time, complexity wise, because your noise is still Gaussian, and that \$e^{-|x-\hat{x}|^2}\$ in that PDF is not going to be friendly for optimization. Sure, we know good decoders for these non-square-lattice constellations, but they're really still expensive in J/b, even in ASICs. \$\endgroup\$ Feb 29 at 22:58
  • 4
    \$\begingroup\$ That's why I mentioned that this is done, for high-power fiber optics at fantastic speeds; there, while it's still annoying as hell to have to cool the line cards, the cost of "yeah, due to increased demand for cat videos on the transatlantic cable between New York and Bristol, we have to put lay another fiber optical cable, including repeaters/amplifiers every hundred km and the necessary power cords" justifies the power and R&D effort of custom, nonregular constellation decoder ASICs. \$\endgroup\$ Feb 29 at 23:02
  • \$\begingroup\$ Thank you for such a detail step by step explanation of such a fascinating data scheme, I've edited my answer to see if maybe quantization may be the limiting factor at play here? \$\endgroup\$ Mar 1 at 8:11
11
\$\begingroup\$

I'd suggest that the "square" constellation is more related to the I/Q signal processing that most of these digital systems employ.

They will generally transmit and capture two out-of-phase signals - one at 0° (In-phase), and one at 90° (Quadrature). By varying the amplitude of each, the sum permits generating a signal of any phase or amplitude - and that signal can also be captured as these two components as well.

If you now look at the "square" 16-QAM constellation again, you can see that each point is actually not handled by the equipment as an odd-looking phase and amplitude pair, but rather one of four discrete amplitudes (possibly negative) in the I component, and one of four in the Q component.

This is much more straightforward to decode than acually handling those odd-looking phase and amplitude figures.

In the diagram below, and from the point of view of the equipment, we don't have Phase=18.4° and Amplitude=0.745, we actually have I=1.0, Q=0.333. The "real" phase and amplitude almost becomes an "artifact" of the way these signals are processed, generated and captured.

an X/Y plot showing a selected point on the 16-QAM constellation, with arrows in the X, Y directions locating it, along with a direct arrow


why not use a more efficient pattern for a QAM-like encoding scheme

A triangular grid is about 2.3 times denser (the area of a equilateral triangle is about 0.43 with a grid spacing of 1).

Don't forget that density is generally a tradeoff for errors... when you add noise and jitter to the system, the constellations start to become much more spread out, rather than the perfect points seen in the video and my diagram above. Our technology is getting better and better - with better clocks, clock recovery, reduced noise, etc... When you recieve a signal that is difficult to categorise into one bucket or the other, you either end up with corruption or need to retransmit the data.

Matt's video is good, but quite misleading when it comes to how these signals are actually handled. Also, 16-QAM is at least as old as V.32 modems (November 1988) and was alo used in DVB-T (~1997, aka: "Freeview" in the UK)... it looks like 5G can use 256-QAM, other technologies like PowerLine Ethernet can use up to 4096-QAM, and DOCSIS 3.1 up to 16384-QAM!

\$\endgroup\$
10
  • 4
    \$\begingroup\$ yeah, the video is very misleading if you only watch the beginning. QAM is not based on the idea of Phase + Amplitude modulation, it's really just based on the idea of I and Q being things that can have separate amplitudes. \$\endgroup\$ Feb 29 at 22:34
  • 1
    \$\begingroup\$ there's much larger QAMs than 4096 in wired applications, for example DSL and DOCSIS (internet via coax cable). \$\endgroup\$ Feb 29 at 22:41
  • \$\begingroup\$ Thank you for clarifying the amplitude combination underpinning the technology I've made a edit that may be the limiting factor on why irregular QAM scheme are not used maybe you can confirm or provide new insight on why my intuition may be wrong? \$\endgroup\$ Mar 1 at 8:10
  • 1
    \$\begingroup\$ 16-QAM was used in V.32 modems in 1988 Recommendation V.32 \$\endgroup\$
    – grahamj42
    Mar 1 at 8:56
  • 1
    \$\begingroup\$ @MarcusMüller woops! I did ask and forgot to mention! link \$\endgroup\$ Mar 1 at 18:21
4
\$\begingroup\$

I see your question is explicitly about QAM, but implicitly is about what is called set partitioning and around it. Below i'll try to explain in detail.

0. QAM itself as a digital-data transmission technique

QAM operates on (modulates) a harmonic signal (the carrier). Given a timescale (or simply a time, t), we can represent a harmonic signal in the given timescale as a total of two orthogonal signals -- sine and cosine, of the same frequency (let's label it w = 2 * pi * f) -- of two amplitudes, let's call them A and B, respectively. I.e.,

harmonic(t) = A * sine(w * t) + B * cosine(w * t)

From this, we see that each orthogonal part can be modulated independently. I.e.,

modulated_harmonic(t) = A(t) * sine(w * t) + B(t) * cosine(w * t)

If we set A(t) = Q[t] and B(t) = I(t), where X[t] means a variable whose value changes discretely both in level and over time, this results in QAM(-modulated harmonic signaling):

QAM(t) = Q[t] * sin(w * t) + I[t] * cos(w * t)

Assuming that X[t] is generated by a DAC (digital-to-analog conversion) circuitry, we have that:

QAM(t) = DAC_Q[t] * sin(w * t) + DAQ_I[t] * cos(w * t)

From here is the answer for the first part of your title question:

Why does QAM use a grid-like distribution ... ?

As we can see, it is because a grid-like distribution is natural for QAM. Moreover, a regular, 2-D, square grid is the most natural for QAM, because it is an obvious way to use two similar DACs in the design.

In your initial figure two DACs of the same 2-bit construction each are assumed. Each drives it own orthogonal "sub-carrier" (Q or I) independently in content but synchronously in time, that gives a composite modulation of 4-bit a time, over the "total" carrier.

If we analyze only the discrete values (levels) of the Q and I DAC outputs, we deal with what is called the (initial) constellation (an image of the DAC-driven 2-D grid) of our QAM case.

Please note here that QAM itself gives us only a constellation, i.e., a set of abstract points in some abstract 2-D space. No codes (binary or other) are assigned (predefined) by the QAM itself.

Also, the QAM-specific part ends here, and the rest of my answer (and your implicit question) is applicable to any modulation that can be operated (abstractly modeled) as a constellation.

0/1. Restricting the initial constellation

Since we have an initial constellation, we can restrict on it, depending on our goals. It is an intermediate step in the coding design flow. I can give the following definition for this step: we eliminate the points which are never used in operation.

In literature, there is no consensus (in a form of attention) on this step is explicit or not, and often the initial constellation of a modulation scheme is already given restricted, i.e., with some number of its points excluded, before it will be partitioned. But in our case, it is better to explicitly demarcate it.

Please note here too, that still no codes are assigned after this step.

1. Partitioned constellation

Invented by Gottfried Ungerboeck as the basis of his TCM, set partitioning is a technique to partition a given initial (already restricted or not) constellation into a number of non-intersecting sets (also called cosets) of points. All such the points are used in operation.

At this level of abstraction, i.e., when we have a constellation, the most common metric used to qualify the points is the (square) distance, which is a geometric one, natural since a constellation is an geometric representation (reflection, model) of the signal.

During set partitioning, two (SQ)Ds are used: free minimal (SQ)D as (the square of) the Euclidean distance between two closest points in the initial constellation, and (simply) minimal (SQ)D as the same distance between to closest points in the partitioned cosets. Squares are preferred in comparison because give integer numbers.

The goal of partitioning is to provide, at least, M(SQ)D > free M(SQ)D. The purpose of set partitioning is to enable soft decoding-based FEC/FED (forward error correction/detection) on the receiving side, e.g., in a form of Viterbi algorithm.

In your initial figure, free MD is 1/sqrt(10), free MSQD=1/10. And as i can see, your need more :-)

And what do you propose?

2. Your proposition

Assuming QAM, you propose restrict on its initial constellation and next partition it (if i understand your coloring correctly, let's take it so), both to increase free M(SQ)D and next in-coset M(SQ)D, respectively. But your way seems unnatural because gives two different DACs, one is 6 levels (about one bit, even not a power of two) more in resolution than the other:

Non-similar DACs

First, this leads for two irregular circuits of the same purpose to occur in the design. It's not optimal and good.

Second, let we'll be fair, your reinvent the wheel here, and the most close, practiced case here is the DSQ constellation design, e.g., DSQ-128 used in 10GBASE-T:

2D-PAM12 vs. DSQ-128

So, here the answer for the second part of your title question:

... versus a more efficient spacing?

There are many ways to increase the free M(SQ)D of an initial constellation, be it 2-D square grid (like in QAM) or other (e.g. 4-D hyper-cubic grid like it is modeled in 1000BASE-T), (the most used) one of such is set partitioning giving a higher M(SQ)D between points in the resulted cosets.

An initial constellation is rarely used alone. The general way is:

Step 0/1. restrict the initial constellation

Step 1. partition the (restricted) constellation

Step 2. assign each operable point in each coset a code (binary or another)

Gray codes and/or other coding techniques are applied only on step 2 and contributes into the whole coding gain of the design. Today, an initial constellation (= plain modulation) alone is not considered in the context as the stand-alone subject of an effective solution, only as the ground for.

For example, PCI Express 6.0 uses the following coding scheme: RS-FEC over Gray over PAM-4.

1000BASE-T implements TCM over 8x2 cosets over 4D-PAM5 (at PCS, over 4D-PAM17, at PMA).

10GBASE-T implements LDPC-backed FEC over 2x (Gray + Pseud-Gray over DSQ-128 over 2D-[PAM16 + THP]), where THP = Tomlinson-Harashima Precoding.

(Of course, above i mention schemes that work over PAM, not QAM, but as i stated earlier (see sections 0 and 0/1), since we have a constellation (as an abstract, geometric representation of the underlying signaling and/or modulation), we can use the universal, modulation-independent principles of modeling.)

As Marcus Müller stated in his answer, (as an integral part of the whole coding design flow) constellation shaping is a science of its own. The above examples show this clean.

On other your sub-questions:

Is it too complex to decode?

Maybe it doesn't offer any measurable benefit?

Typically, a decoder is much more complex than the respective encoder. The complexity of encoding for 1000BASE-T and 10GBASE-T your can see in the above mentioned documents.

The measurable benefit is the coding gain of a coding scheme. As shown above, such a gain is a total of many but tightly-matched items. In the simplest modern case, it is resulted from well-matched binary FEC coding + bit coding + line coding (modulation).

At this point, i think the rest your sub-questions cannot have meaningful answers.

Additional notes

If you are interesting in this theme, i recommend you to begin with the following papers:

[1]. G. Ungerboeck, Trellis-coded modulation with redundant signal sets, Part I: Introduction

[2]. G. Ungerboeck, Trellis-coded modulation with redundant signal sets, Part II: State of the art

[3]. again G. Ungerboeck, 10GBASE-T Coding and Modulation: 128-DSQ + LDPC

[4]. now not Ungerboeck, but Jaime E. Kardontchik, 4D ENCODING IN LEVEL-ONE'S PROPOSAL FOR 1000BASE-T

Moreover, you can meet how the real designers designed real constellation-based coding schemes, reading the materials documenting the respective IEEE 802.3 standardization processes:

[5]. Public area of the 1000BASE-T task force

[6]. Public area of the 10GBASE-T task force and its preceding studying group

Also, because Marcus Müller mentioned some signal power-related issues in his answer, and because i see the tag "Theory" under your question, i recommend you to read something like this:

[7]. "A collection of the data coding means and event coding means multiplexed over and inside the 1000BASE-T PMA sublayer" (abstract at arXiv)

where power balancing of the physical signal is one of the tasks of the design flow, that results in schemes like a stellarial constellation over the 4D-PAM17 grid:

stellarial constellation

\$\endgroup\$

Your Answer

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

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