3 ms·

Yes, I am sure that it’s GF(2^4) and not GF(2^16). The problem is not that GF(2^8) or GF(2^16) are “too big”, it’s just that GF(2^4) is faster and uses less CPU

Yes, I am sure that it’s GF(2^4) and not GF(2^16). The problem is not that GF(2^8) or GF(2^16) are “too big”, it’s just that GF(2^4) is faster and uses less CPU. The purpose of using GF(2^128) or other large sizes is usually cryptographic, which has different tradeoffs. For example, Galois counter mode. The linked paper describes secure storage mechanisms. Also note that you’re not just doing one field operation per byte, but several. If I’m remembering correctly, let’s say you’re using an (11,8) code, then you’re doing 24 multiply and 21 addition operations to calculate the encoded message. You might think of various ways to accelerate this which benefit from a smaller field size, especially if you are doing the calculations on commodity CPUs. The only point I’m making here is that the computation consumes some nontrivial amount of CPU resources, and so it can be fruitful to optimize. The fact that space probes like Voyager use a large field size is just because the cost of resources is different. For space probes, bandwidth is a precious resource. If you spent $250M on a single space probe, you can afford to use a bit more CPU to encode and decode your puny 100 kHz downlink. On the other hand, if you are running a data center, the power consumption of CPUs is one of your largest costs.

dragontamer 6y ago
> Yes, I am sure that it’s GF(2^4) and not GF(2^16). The problem is not that GF(2^8) or GF(2^16) are “too big”, it’s just that GF(2^4) is faster and uses less CPU. A multiply in GF(2^8) is just a single multiplication lookup. 256 x 256 == 64kB lookup table. I'm not sure how much faster you can get than a single 8-bit lookup on a table small enough to fit in a typical CPU's cache. GF(2^8) is so small that you don't even need to do the log-table / antilog-table trick. Just store the entire multiplication table, since the multiplication table fits in L2 cache. A GF(2^4) multiply would be a single multiplication lookup 16 x 16 or 256 byte (0.25kB) lookup table. Very, very tiny, probably no faster than the GF(2^8) lookup. > Also note that you’re not just doing one field operation per byte, but several. If I’m remembering correctly, let’s say you’re using an (11,8) code, then you’re doing 24 multiply and 21 addition operations to calculate the encoded message. That RS(11,8) code (probably shortened / punctured) could be a GF(2^8) code. The question is: do you want to organize your data in 8-bit bytes in GF(2^8), or 4-bit nibbles in GF(2^4)? I expect that 8-bit bytes is actually faster for modern computers than 4-bit nibbles. Even if you are using a severely shortened / punctured code, there are strong benefits to sticking with 8-bit bytes on a modern computer. That's the thing: computers usually have 8-bit bytes as the smallest pragmatic unit to use. GF(2^8) lines up with that perfectly, and is used in a variety of high-performance applications (including AES). > The fact that space probes like Voyager use a large field size is just because the cost of resources is different. For space probes, bandwidth is a precious resource. If you spent $250M on a single space probe, you can afford to use a bit more CPU to encode and decode your 100 kHz downlink. The Voyager probe launched in 1977, it was with an utter crap CPU by today's standards. Your USB power-cable has more CPU power and RAM than the voyager probe... that tiny USB CPU is used to negotiate the voltage level (5V vs 12V USB power negotiation) -------- Voyager launched with 32k 18-bit words of RAM and 4MHz for its 6x parallel CPUs (handling different parts of the craft: flight vs imaging unit vs radio unit... etc. etc.). I think you're severely overestimating the strength of Voyager probe, or the level of technology available to 1977.
- klodolph 6y ago
  > A multiply in GF(2^8) is just a single multiplication lookup. 256 x 256 == 64kB lookup table. I'm not sure how much faster you can get than a single 8-bit lookup on a table small enough to fit in a typical CPU's cache. 64 KB often won’t fit in L1 cache anyway. > A GF(2^4) multiply would be a single multiplication lookup 16 x 16 or 256 byte (0.25kB) lookup table. Very, very tiny, probably no faster than the GF(2^8) lookup. Or you can do three operations using a single 16 x 16 x 16 x 16 lookup table, and introduce fewer data dependencies into your CPU pipeline. The operations work on half as many bits, but complete three times as many steps. Sounds like a win to me. > I expect that 8-bit bytes is actually faster for modern computers than 4-bit nibbles. Even if you are using a severely shortened / punctured code, there are strong benefits to sticking with 8-bit bytes on a modern computer. You keep saying this. I understand how CPUs are byte-addressed. When you operate on smaller sizes, you have to do packing / unpacking. If your CPU core spends most of its time doing table lookups, then a little bit of packing / unpacking is nearly free, since your ALUs are otherwise fairly idle, assuming you have a couple registers free.
  - dragontamer 6y ago
    > Or you can do three operations using a single 16 x 16 x 16 x 16 lookup table, and introduce fewer data dependencies into your CPU pipeline. Gotcha. So to summarize: you've seen GF(2^4) calculations performed SIMD style. A singular 16-bit lookup can be 4x GF(2^4) lookups in parallel. Seems legit to me. A non-obvious implementation, but clearly possible and faster.

dragontamer 6y ago

> Yes, I am sure that it’s GF(2^4) and not GF(2^16). The problem is not that GF(2^8) or GF(2^16) are “too big”, it’s just that GF(2^4) is faster and uses less CPU. A multiply in GF(2^8) is just a single multiplication lookup. 256 x 256 == 64kB lookup table. I'm not sure how much faster you can get than a single 8-bit lookup on a table small enough to fit in a typical CPU's cache. GF(2^8) is so small that you don't even need to do the log-table / antilog-table trick. Just store the entire multiplication table, since the multiplication table fits in L2 cache. A GF(2^4) multiply would be a single multiplication lookup 16 x 16 or 256 byte (0.25kB) lookup table. Very, very tiny, probably no faster than the GF(2^8) lookup. > Also note that you’re not just doing one field operation per byte, but several. If I’m remembering correctly, let’s say you’re using an (11,8) code, then you’re doing 24 multiply and 21 addition operations to calculate the encoded message. That RS(11,8) code (probably shortened / punctured) could be a GF(2^8) code. The question is: do you want to organize your data in 8-bit bytes in GF(2^8), or 4-bit nibbles in GF(2^4)? I expect that 8-bit bytes is actually faster for modern computers than 4-bit nibbles. Even if you are using a severely shortened / punctured code, there are strong benefits to sticking with 8-bit bytes on a modern computer. That's the thing: computers usually have 8-bit bytes as the smallest pragmatic unit to use. GF(2^8) lines up with that perfectly, and is used in a variety of high-performance applications (including AES). > The fact that space probes like Voyager use a large field size is just because the cost of resources is different. For space probes, bandwidth is a precious resource. If you spent $250M on a single space probe, you can afford to use a bit more CPU to encode and decode your 100 kHz downlink. The Voyager probe launched in 1977, it was with an utter crap CPU by today's standards. Your USB power-cable has more CPU power and RAM than the voyager probe... that tiny USB CPU is used to negotiate the voltage level (5V vs 12V USB power negotiation) -------- Voyager launched with 32k 18-bit words of RAM and 4MHz for its 6x parallel CPUs (handling different parts of the craft: flight vs imaging unit vs radio unit... etc. etc.). I think you're severely overestimating the strength of Voyager probe, or the level of technology available to 1977.

klodolph 6y ago
> A multiply in GF(2^8) is just a single multiplication lookup. 256 x 256 == 64kB lookup table. I'm not sure how much faster you can get than a single 8-bit lookup on a table small enough to fit in a typical CPU's cache. 64 KB often won’t fit in L1 cache anyway. > A GF(2^4) multiply would be a single multiplication lookup 16 x 16 or 256 byte (0.25kB) lookup table. Very, very tiny, probably no faster than the GF(2^8) lookup. Or you can do three operations using a single 16 x 16 x 16 x 16 lookup table, and introduce fewer data dependencies into your CPU pipeline. The operations work on half as many bits, but complete three times as many steps. Sounds like a win to me. > I expect that 8-bit bytes is actually faster for modern computers than 4-bit nibbles. Even if you are using a severely shortened / punctured code, there are strong benefits to sticking with 8-bit bytes on a modern computer. You keep saying this. I understand how CPUs are byte-addressed. When you operate on smaller sizes, you have to do packing / unpacking. If your CPU core spends most of its time doing table lookups, then a little bit of packing / unpacking is nearly free, since your ALUs are otherwise fairly idle, assuming you have a couple registers free.
- dragontamer 6y ago
  > Or you can do three operations using a single 16 x 16 x 16 x 16 lookup table, and introduce fewer data dependencies into your CPU pipeline. Gotcha. So to summarize: you've seen GF(2^4) calculations performed SIMD style. A singular 16-bit lookup can be 4x GF(2^4) lookups in parallel. Seems legit to me. A non-obvious implementation, but clearly possible and faster.