Henry, How are you thinking you'd expand the "majority test" to multiple bits? if you have in mind an ECC with something like ceiling(log2(# of data bits))+1 check bits, then that's like the one I used when I built the 44(?) bit ECC-corrected memory subsystem for the AI PDP-10. I used a ladder of XOR's to generate the ECC code while writing and to generate the error syndrome when reading. A lookup table on the syndrome gives the bit to correct. If you model the input word as a bit vector, then you should be able to compute the ECC code with one level of a matrix XOR (like multiply, but using XOR as the combining operator). I think sum mod 2 is equivalent. For the decode side you would then use a lookup table. There might be a way to use matrix-like ops to splay out a syndrome to a single bit and then use XOR on the incoming word to correct it, but I haven't thought it through. Perhaps I'm misunderstanding your question? (I'm certainly outclassed mathematically by everyone else on the list!) Regards, --Howard ________________________________ From: math-fun <math-fun-bounces@mailman.xmission.com> on behalf of Henry Baker <hbaker1@pipeline.com> Sent: Wednesday, January 16, 2019 12:32 PM To: math-fun@mailman.xmission.com Subject: [math-fun] *linear* decoding of ECC code ? The simplest form of ECC is that for a single bit: 0 -> 000, 1 -> 111. The decoding rule is also a simple majority test: 001/010/100 -> 0; 110/101/011 -> 1. My problem: I'd like an ECC code that can be computed *linearly* -- i.e., via a (chain of) matrix multiplication(s). Thus, codeword . R . P = decodedword Where R is an invertible matrix and P is some non-invertible matrix -- e.g., a projection matrix. I haven't been able to find a linear decoding for this version of ECC, nor have I been able to convince myself that it is impossible. If this type of ECC can't be decoded in a linear fashion, is there any other type of ECC that can? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun