Galois does not support non-cyclic Reed-Solomon codes

[fyellin]

This package only supports cyclic Reed-Solomon codes. For a Reed-Solomon code RS(n, k, field, alpha), the RS code can only be created if n is a divisor of field.order. If alpha is given, it must be an nth root of unity. This was the original implementation of RS encoding, but it is no longer necessary.

Many common RS codes are not cyclic. In particular, the RS code used by QR Codes uses field=GF(2**8), alpha=2 (a primitive root of multiplicative order 255) and many different combinations of n and k. For example to encode https://github.com/mhostetter/galois.git"it used RS(70, 44). Since 70 isn't a divisor of 255, galois.ReedSolomon will give an error.

In terms of implementation, it would be fairly straightforward to allow non-cyclic implementations. The main changes are:

1. In _cyclic.py remove the assert remainder_poly == 0. If this polynomial is 0, then the RS is cyclic, otherwise it isn't.
2. If the RS isn't cyclic, there really isn't a parity check polynomial. Should it just be set to None?
3. The current constructor for the G field only works for cyclic RS. The construction needs to be changed to work for both cyclic and non-cyclic RS. It is straightforward.
4. Do we want a new property is_cyclic indicating whether the RS is cyclic?

At present, ReedSolomon is a direct superclass of _CyclicCode. Not sure whether to leave this as the direct superclass or not. Most of what's in there is okay.

There is also a question of API visible to the user. There are two possibilities:

1. If the user specified an n that isn't a divisor of field.order - 1, or if the user specifies a particular alpha that isn't an n'th root, then we suppose the user knows what they want and generate the specified RS code.
2. Alternatively, require the user to specify cyclic=False to get a non-cyclic group. If they do specify cyclic=False, then alpha, if not specified, will be field.primitive_element and a possibly non-cyclic RS will be generated.

[mhostetter]

Are you talking about shortened codes? Without knowing the specifics of the QR RS code you've described, I would implement it like this.

import galois

n, k = 70, 44
rs = galois.ReedSolomon(255, 255 - (n - k))
print(rs)

m = rs.field.Random(k)
print(m.size)
print(m)

c = rs.encode(m)
print(c.size)
print(c)

Reed-Solomon Code:
  [n, k, d]: [255, 229, 27]
  field: GF(2^8)
  generator_poly: x^26 + 241x^25 + 204x^24 + 209x^23 + 64x^22 + 208x^21 + 165x^20 + 51x^19 + 3x^18 + 57x^17 + 178x^16 + 236x^15 + 106x^14 + 171x^13 + 194x^12 + 227x^11 + 74x^10 + 128x^9 + 230x^8 + 157x^7 + 236x^6 + 47x^5 + 54x^4 + 227x^3 + 229x^2 + 125x + 217
  is_primitive: True
  is_narrow_sense: True
  is_systematic: True
44
[  9  74 202   8   2 160 119 220 235  24 202 188 179  27 238   9 165 215
 100 246 145  45 242  60  18 101  10 150 101 129 149  86  61 112 240  18
  37  38   5  74 230 247  74 181]
70
[  9  74 202   8   2 160 119 220 235  24 202 188 179  27 238   9 165 215
 100 246 145  45 242  60  18 101  10 150 101 129 149  86  61 112 240  18
  37  38   5  74 230 247  74 181 120 136 108 201  81  94  48 234 221 137
 127 226 162 198 106  42 136 246 206  44  84  16  57 113 170 122]

[fyellin]

Yeah. I'm in the middle of submitting a different bug about shortened codes when I realized that shortened codes could be used to solve the QRCode problem.

While I recognize this is a solution, I'm not sure it's a clean solution.

• The G table is going to be size (229, 255) rather than (44, 70) which is a lot more memory and a lot more work to construct. Likewise for the H table.
• If the user wants to use a specific alpha, they have to figure out what it's multiplicative order is and do all the above arithmetic to increase n to the arithmetic order whiling leaving d fixed.
• From my reading of the literature, RS used to be implemented as only cyclic, but once people realized that shortened codes worked, they realized that cyclicity was an unnecessary requirement, and the shortened codes could exist as codes on their own.

If I get a chance, I may clean up my changes and submit them as a PR. If you decide to discard them, that's fine.

[mhostetter]

If you can send links to any literature or discussion of what you'd like implemented, that'd help too.

Are you describing Reed-Solomon codes using the original view, where I have implemented RS codes using the BCH view?

[mhostetter]

In terms of implementation, it would be fairly straightforward to allow non-cyclic implementations. The main changes are:

In _cyclic.py remove the assert remainder_poly == 0. If this polynomial is 0, then the RS is cyclic, otherwise it isn't.
If the RS isn't cyclic, there really isn't a parity check polynomial. Should it just be set to None?
The current constructor for the G field only works for cyclic RS. The construction needs to be changed to work for both cyclic and non-cyclic RS. It is straightforward.
Do we want a new property is_cyclic indicating whether the RS is cyclic?
At present, ReedSolomon is a direct superclass of _CyclicCode. Not sure whether to leave this as the direct superclass or not. Most of what's in there is okay.

There is also a question of API visible to the user. There are two possibilities:

If the user specified an n that isn't a divisor of field.order - 1, or if the user specifies a particular alpha that isn't an n'th root, then we suppose the user knows what they want and generate the specified RS code.
Alternatively, require the user to specify cyclic=False to get a non-cyclic group. If they do specify cyclic=False, then alpha, if not specified, will be field.primitive_element and a possibly non-cyclic RS will be generated.

I'm back to reviewing this. Your initial thoughts and suggestions seem reasonable to me. Have you had a chance to think more about this / are you willing to submit a PR? (We can discuss the design decisions before coding)