ECC memory module modification?

Hamming code with parity: to protect 4 bits of data against 2 errors takes 4 bits of overhead

ecc[0] parity_all ecc[1] parity 1,3,5,7 ecc[2] parity 2,3,6,7 ecc[3] data[0] ecc[4] parity 4,5,6,7 ecc[5] data[1] ecc[6] data[2] ecc[7] data[3]

--
     ?

5 bits can correct 1 bit error in 16 (26 actually) but cannot detect a second error. You need an extra bit to do SECDED.

Same goes for 7 bits, which can correct 1 in 120, but you need 8 for SECDED. 64-bit memory uses a 72/64 code.

See

Clifford Heath.

The advantage is that they perform better in communication systems where e.g. a long run of zeroes or ones would endanger the clock recovery (the bitstream provides both clock and data and requires data edges to recover the clock). It is possible to use a separate "scrambler" circuit to arrange this, but it can be combined with the ECC coding (which is usually called FEC in communications).

I was trying to remember the details of how it works and couldn't so a trip to Wikipedia is in order. Still, remember that you also have to account for bit errors in the ECC bits as well.

Rick C.

You need enough check bits to cover both data and check bits. With 7 check bits you can have up to 121 bits of data.

--

-TV

Everyone is saying that, but an error in the ECC bits is also a single bit error and would be detected (but also corrected) the same way in a simple parity system an error in the parity bit would be detected. Unless the objective is to distinguish between an error in the data and an error in the check bits.

The parity bits are all derived from themselves?

That would be correctable like any single bit error in the data.

Isn't that the objective? Errors in the check bits would be correctable as well.

Obviously hamming code is more efficient in the ratio of check bits to data bits, but the old ECC system can detect and correct errors in the ECC bits as well. The same way simple parity can detect an error in the parity bit.

The way the Hamming code parity works, every data bit is incorporated into the XOR that goes into two (or more) of the check bits. As a result, a single-bit error in a data bit results in two (or more) of the parity bits flipping. A "syndrome" calculation can then tell you precisely which data bit resulted in the double-bit parity flip... in fact, some of the Hamming codes are designed so that the syndrome (one calculated) is exactly the bit number of the error location.

In a code of this sort, a single-bit error in one of the check bits results in only that one check bit being wrong. The correction logic recognizes this as "the data's OK, the checksum itself is wrong" and no correction of the data bit needs to be done during a read. There's no separate "parity of the parity bits" computation or storage needed in this scheme... and so it's slightly faster than one which has such an additional level of parity.

In either case, the memory controller may or may not be designed to correct whatever error exists and write the corrected data back to memory. Doing so takes time (memory access cycles) and needs to be done carefully (so that it doesn't interfere unnecessarily with subsequent memory reads or writes from the CPU).

But everything you say above applies to the ECC system I described:

If you had 8-bit memory then you'd have 4 ECC bits.

1 would be parity for all 8 bits. 1 would be parity for the odd bits. 1 would be parity for bits 2,3,6,7. 1 would be parity for bits 4,5,6,7.

Obviously the last 3 ECC bits would have a binary value equal to the location of the error in the 8 data bits.

Now, expanding that scheme, you'd need 5 ECC bits for 16 data bits, 6 for 32 and 7 for 64.

So what's all this about needing 8 check bits for 64 data bits?

If you can correct the parity error (or ignore it in reality) then you have distinguished it from the data errors.

It looks like I was mistaken. I did say it had been a few decades since I worked with Hamming codes. The parity bits are included in the bits being checked. Then you don't need a parity bit for the overall word. Rather al l the bits are interleaved allowing any single bit error to be detected and corrected. The number of parity bits needed are n, where n is the smalles t integer to satisfy 2^n > m + n where m is the number of data bits.

Then as someone else pointed out, an extra bit is added to enable detection without correction of 2 bit errors and some 3 bit errors.

Rick C.

Yes. Hamming parity bits cover the Hamming parity bits.

only in the way that all parity bits are, the inital computation is done ignoring the parity bit, but the check includes it.

--
     ?

You've made this claim before and I assumed you meant 8 bits physical,

4 bits pariy and 4 bits data because that would be true, and I don't want to get into an argument over a mis-understanding.

However with this context you appear to be claiming 4 bits parity and 8 bits data (12 bits physical) which doesn't work.

for example: flip data bit zero and and the parity for all - that's an undetectable, 2 bit error.

There are other possible 2 bit errors that look like 1 bit errors.

No point in even discussing it. Hamming already did the work. All anyone needs to do is go to Wikipedia and read about it. They actually made this one fairly clear.

Rick C.

No, the parity bits are used in the initial calculation, too, just as they are in any parity scheme. "Odd positive parity", for example, means that the parity bit is set such there is an odd number of '1s' in the string, including the parity bit.

On Saturday, September 29, 2018 at 9:57:41 PM UTC-4, snipped-for-privacy@notreal.com wrote :

That's an interesting use of the word... "used". The parity bits are zero or not used in the initial calculation. The parity bit is then set to the result. Since the parity bit is produced by the initial calculation it can 't be used as part of the initial calculation.

Rick C.

Aha. Thank you. Now that's clear. I thought I remembered 16-bit systems had 5 bits of ECC, but no one said I remembered that wrong. I guess I did.