2 ms·

How do you achieve actual multiplication? I remember there was some polynomial that you had to divide by, and then every non-zero element becomes invertible? Su

How do you achieve actual multiplication? I remember there was some polynomial that you had to divide by, and then every non-zero element becomes invertible? Such pseudo-multiplication doesn't seem to be invertible, as 0b00000010 multiplied by anything will always end with a 0: 0b???????0.

dragontamer 3y ago
You've got the gist but you're confusing a bunch of concepts together. Note: Remember that "x / y" division in a field is simply "x * (1/y)", because (1/y) is always uniquely defined in a field and "proper". So in practice, its actually a whole lot of multiplies. Note2: For the 8-bit domain to become a field, you must perform a "modulo p", where p is prime (for simple fields), or an irreducible polynomial (for an extension field). For us computer-programmers, we're almost always operating on an extension field (8-vector of field(2), aka a binary vector of size 8-bits). (Though hardware designers may choose say, GF(2^5), the 5-bit numbers, for USB1.0 packets for example) So you need to perform the operation (x modulo p) and normalize the result to return it to a field. There are different fields for each chosen p, so the first step is to choose a p. P is almost always chosen arbitrarily, but there's benefits to different p's chosen. In any case, p differs from case-to-case since they have minor benefits (this p might be slightly faster at multiplication in software, this other p might have an easier circuit layout and is related to some simple LSFR, etc. etc.). So p is arbitrary and changes from case-to-case. After that, (x modulo p) is performed by (x / p), which results in (quotient + remainder/p). In practice, one iteration of this operation commonly results in a 9-bit number or 10-bit number or 16-bit number. Anything 9 to 16 bits in length is obviously "not in GF(2^8)", so we repeatedly perform the operation until the top-bits are zero and we only have an 8-bit result. (remainder/p) is simply (remainder * (1/p)), because this is a field (all numbers 1/x are properly defined), so we can "implement" this in practice through multiplications only. -------------- And that's all CRC-32 and Reed Solomon Encoding is. EDIT: I'm not sure if what I said originally was correct. I decided to change the "modulo" algorithm to the LSFR style which was simpler for me to discuss.

dragontamer 3y ago

You've got the gist but you're confusing a bunch of concepts together. Note: Remember that "x / y" division in a field is simply "x * (1/y)", because (1/y) is always uniquely defined in a field and "proper". So in practice, its actually a whole lot of multiplies. Note2: For the 8-bit domain to become a field, you must perform a "modulo p", where p is prime (for simple fields), or an irreducible polynomial (for an extension field). For us computer-programmers, we're almost always operating on an extension field (8-vector of field(2), aka a binary vector of size 8-bits). (Though hardware designers may choose say, GF(2^5), the 5-bit numbers, for USB1.0 packets for example) So you need to perform the operation (x modulo p) and normalize the result to return it to a field. There are different fields for each chosen p, so the first step is to choose a p. P is almost always chosen arbitrarily, but there's benefits to different p's chosen. In any case, p differs from case-to-case since they have minor benefits (this p might be slightly faster at multiplication in software, this other p might have an easier circuit layout and is related to some simple LSFR, etc. etc.). So p is arbitrary and changes from case-to-case. After that, (x modulo p) is performed by (x / p), which results in (quotient + remainder/p). In practice, one iteration of this operation commonly results in a 9-bit number or 10-bit number or 16-bit number. Anything 9 to 16 bits in length is obviously "not in GF(2^8)", so we repeatedly perform the operation until the top-bits are zero and we only have an 8-bit result. (remainder/p) is simply (remainder * (1/p)), because this is a field (all numbers 1/x are properly defined), so we can "implement" this in practice through multiplications only. -------------- And that's all CRC-32 and Reed Solomon Encoding is. EDIT: I'm not sure if what I said originally was correct. I decided to change the "modulo" algorithm to the LSFR style which was simpler for me to discuss.