Achieving 32-bit verification code with 16-bit CRC? I am programming an embedded chip that has a hardware 16-bit CRC module. I have to protect some data bytes $d_0,d_1,...,d_{n-1}$ against corruption caused by sudden loss of power; a 32-bit CRC would provide the level of protection that I need, but the chip doesn't have that capability.

Unfortunately the CRC module uses a hard-coded polynomial that can't be changed. And I need the computation to be as fast as possible. Perhaps a table-based CRC algorithm would be fast enough, but the table would occupy 1 kilobyte of ROM, which I want to avoid if I can.

So my question is this: Can I somehow use this hardware CRC-16 module to reach the level of security that I need?

My current idea is to compute $CRC_{\mathrm{forward}}$, the CRC-16 of the data bytes $d_0,d_1,...,d_{n-1}$, and $CRC_{\mathrm{backward}}$, the CRC-16 of the data bytes $d_{n-1},d_{n-2},...,d_0$, and simply concatenate these two 16-bit CRCs to create a 32-bit EDC. Is this sufficient? Or are these two CRCs in some sense dependent?

More precisely: Suppose $D$ is the data, and $E$ is a corrupted version with $E \ne D$. Then I want the probability that $CRC_{\mathrm{forward}}(E) = CRC_{\mathrm{forward}}(D)$ to be independent of the probability that $CRC_{\mathrm{backward}}(E) = CRC_{\mathrm{backward}}(D)$. Is this the case here, or have I missed something?

Edited to add: If the discrepancy $E \oplus D$ is palindromic, and $CRC_{\mathrm{forward}}(E) = CRC_{\mathrm{forward}}(D)$, then $CRC_{\mathrm{backward}}(E) = CRC_{\mathrm{backward}}(D)$. So this idea doesn't work. Does anybody have a better idea?
I'll assume $n$ is a multiple of 4. One option is to compute the CRC16 of the bytes $d_{4j},d_{4j+1}$ ($0\le j&lt;n/4$), giving 2 bytes appended as $d_{n},d_{n+1}$; and the CRC16 of the bytes $d_{4j+2},d_{4j+3}$, giving 2 bytes appended as $d_{n+2},d_{n+3}$.

That


reduces the work compared to the original solution, because each byte is processed once instead of twice;
has a desirable property of CRC32: if all bits in error are within the same 32-bit segment of data+CRC (including within the same 32-bit word), then the error is detected [note: the capability to always detect short error bursts lying across data and CRC requires care in the finalization of the CRC];
detects a large number of random errors with odds comparable to a 32-bit CRC, including all errors affecting an odd number of bits.


One very negative aspect compared to a 32-bit CRC is that errors which, for hardware reasons, are bound to always affect the same single bit of a 32-bit word (or some wider multiple) are not detected far more often ($2^{-16}$) than for a 32-bit CRC ($2^{-32}$).

Therefore, that solution is fine to detect communication errors on a serial link, but poor to detect corruption of a Flash or DRAM memory (assuming there is no built-in ECC) as occurring from a defective sense amplifier, and I guess a marginal write.



In the context of detecting corruption in memory (without ECC), I would consider


computing a CRC16 of the whole data;
simultaneously counting the number of 0 bits in the data (which will fit 16 bits if $n&lt;2^{13}$);
storing the concatenation of that along the data.


Integrity check using the count of 0 bits has the property (desirable in the context of storage in computer memory without ECC) that if an error changes all bits in error to the same value, then it is always detected (that includes errors in the count). Also, it is fast to compute even on CPUs without hardware popcount, using a small table or various bit tricks.