lots'a data, please correct (Part 7/12) 🕊️

Unlike humans, slght errs in a messge kan render a message completly ruined to a a computer. As humans we can deal with things lke typos, missing or duplicated worlds, and if all else fails try to figure out what’s happening with context clues (see what I did there?). When we’re sending messages over pigeon, I’ve employed a forward error correction (FEC) scheme to help receivers correct erorrs. FEC comes at a cost (added bits to send, time to encode, time to decode) but can often prevent even more expensive costs above it in the stack (tcp retransmits, missing messages, retry loops, etc). The FEC scheme I’ve opted to use in pigeon is Low-density parity-check (LDPC) codes.

Low-density parity-check (LDPC) codes use a (very) neat construction of some number (k) of even/odd parity checkbits, each covering a (in some case: randomly picked!) set of data bits, where both checkbits and databits are written into a fixed size block. The LDPC matrix is often communicated as the “H” matrix, where every row (of length k) of the matrix represents a single checkbit, and the set columns (of length n) represents the message bits covered by the checkbit. There’s a second matrix – the “G” matrix, which, when multiplied by a transposed copy of the “H” matrix, will result in all zeros.

There’s a lot to LDPC, and I don’t feel like I can explain it yet (I was hoping to be able to by now – but I still haven’t got to that point yet), so I’m going to have to stick to some of the mechanical basics here on how to encode and check LDPC messages. Once I figure out LDPC for real, expect a followup post (if such a post comes into existence, I’ll link it right here).

Encoding and checking messages turn out to be pretty easy if you have an LDPC matrix – data (as a vector of bits) can be multiplied by the “G” matrix to calculate (and set!) the checkbits. In pigeon, that looks something like this:

  /// LDPC encode `data`, writing the encoded data to `message`.
  pub fn encode(
    &self,
    dst: &mut Vector,
    m: &Vector
  ) -> usize {
    let encoded = m * self.g;
    dst.copy_from(encoded)
  }

On the other end, when we receive LDPC encoded messages, we can check the encoded blocks for errors by multiplying “H” by the message vector, checking to be sure that the resulting vector (the “syndrome vector” in LDPC speak) is all zeros. In the past, I did a bit of exploritory work on correcting errors by looking the syndrome vector up in a table and mapping the vector to specific bitflips to correct the message – which works but is generally impractical.

  // Check for errors (without correcting anything)
  fn check(
    &self,
    m: &Vector
  ) -> bool {
    let check_matrix = self.h * m;

    // Return true (no errors) if the syndrome vector
    // is all zeros, otherwise return false (there is
    // an error somewhere).
    check_matrix.is_zero()
  }

Correcting errors, though, is fairly involved, although, it turns out, a fairly close-to-home (I say that, given the research topic that my professors in college (and myself during one summer) worked on) – namely, Belief Propagation. This works, generally speaking, by iteratively letting checkbits “vote” on the probability of which bits being right or wrong. This is usually augmented with information from the modulation process regarding how good of a guess that bit is (how close to “perfect” it is).

That being said, I haven’t gotten a chance to spend the time needed to implement the LDPC error correcting side of the demodulation code; I would like to try out the Belief propagation (specifically min-sum) and get it correcting errors reliably. Once that’s working, I’m interested in exploring a move to a different LDPC matrix, one that is “quasi-cyclic” (such as the WIMAX matrix from 802.16E), since they contain an internal structure (‘dual diagonal’) that enables parallelization in a way that a non-quasi-cyclic LDPC matrix does not.

Throughout all the pigeon modes, I used the well known, publicly documented and well characterized LDPC matrices from the 802.3an 10GbE Ethernet spec. I went down this route since it was well-understood, lots of big-brains have worked on ensuring the tables are robust, and it was a size that I could work with easily. The 802.3an-2022 LDPC Matrices can be found on the IEEE Website. If you’re interested in downloading them yourself, they can be found inside 802.3-2022_downloads.zip, contained in another zip named Annex_55A_matrices.zip. That zip contains g.txt (the “G” matrix) and H.txt (the “H” matrix), which, as we now know, are the two LDPC matrices required for encoding, checking and correcting messages (and errors).

We’ll be using these matrices throughout pigeon, since they’re well understood, work very well in practice, and means I can side-step generating a new ldpc matrix just for pigeon for now. Since each LDPC “message” is a fixed size (2048 bits – 256 bytes – in length), and since each PHY burst is larger (around 1400 bytes), the burst contains some fixed number of independent LDPC messages, packed one after another.

When each LDPC message is checked and verified to be error free (possibly after correcting recoverable errors), the data contained in each message is then extracted and written out as a single contiguous block of data.

With the 802.3an ethernet matrix (and I suspect most matrices out there, for ease of use and efficiency, although nothing requries it), the data bits are encoded at the very end of the LDPC message. Extracting our data is as simple as slicing out the number of data-bits from the message, and concatinating the data from each LDPC message in the output buffer.

802.3an Annex 55A

When I was working with these files, I’ve come to believe that one of the files distributed as part of 802.3an (as of 802.3-2022) – namely file descriptions.txt – has some typos. This is a wildly bold claim – akin to blaming the compiler. I fully realize saying “the fucking ethernet spec has an error” comes off as absolutely deranged, given the number of people who have worked in-depth implementing and reviewing the standard. Just like when it actually is the compiler, it’s never the first thing you blame – I spent a good week or two trying to figure out why my interpretation of the matrices didn’t match the test cases I wrote off the LDPC Matrix description before I questioned the counts I found in the zip.

Long after I talked myself into there actually being a bug in the description of the matrices, I worked up the courage to report the typos I found to the IEEE 802.3 chair, David Law. David – being the extremely kind and helpful person he is – was kind enough to take the request seriously (even though it’s a bit silly!), and turn my emailed descriptions of the typos into an actual Revision Request, which was accepted (and at the time of writing, ready for voting) as #1404 via the IEEE 802.3 working group’s Revision Requests process.

Thank you, David!

I never thought working on Pigeon would have lead me down a path where I submitted a change request to the ethernet standard, but alas, here we are.

This is a very long way of saying – for those of you following along at home, please beware: file descriptions.txt says that H.txt is 325 rows – it’s actually 384 rows. This unfortunate and well intentioned red herring will hopefully be addressed in a future release of the 802.3 standard.

Let’s decode a packet →