[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?
https://en.wikipedia.org/wiki/Hamming(7,4) ? On Wed, Jan 16, 2019 at 10:34 AM Henry Baker <hbaker1@pipeline.com> wrote:
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
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
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 the ECC can correct single-bit errors, then every vector v of Hamming weight 1 must satisfy: v . R . P = 0 But since the vectors of Hamming weight 1 span the space, then we have: v . R . P = 0 for every vector v, which implies that, in every case, decodedword = 0 -- so the code cannot store any information whatsoever. To summarise, there is no code which satisfies each of: (i) linear decoding; (ii) correction of arbitrary single-bit errors; (iii) ability to actually store information. If you remove any one condition, then there are examples: (i) + (ii) : empty code (i) + (iii) : identity code (ii) + (iii) : Hamming code Best wishes, Adam P. Goucher
On Wed, Jan 16, 2019 at 10:51 AM Adam P. Goucher <apgoucher@gmx.com> wrote:
To summarise, there is no code which satisfies each of:
(i) linear decoding; (ii) correction of arbitrary single-bit errors; (iii) ability to actually store information.
Hamming(7,4) is linear, corrects arbitrary single bit errors, and stores four bits of information. Is there some extra implicit constraint I'm missing? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
Hamming(7, 4) has linear encoding, but not linear decoding. For example: 0000 encodes to 0000000 which means (with the error-correcting property) that: 0000001 decodes to 0000 0000010 decodes to 0000 0000100 decodes to 0000 0001000 decodes to 0000 0010000 decodes to 0000 0100000 decodes to 0000 1000000 decodes to 0000 If the decoding function were linear, it would therefore be identically zero (which it isn't). Best wishes, Adam P. Goucher
Sent: Wednesday, January 16, 2019 at 6:14 PM From: "Mike Stay" <metaweta@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] *linear* decoding of ECC code ?
On Wed, Jan 16, 2019 at 10:51 AM Adam P. Goucher <apgoucher@gmx.com> wrote:
To summarise, there is no code which satisfies each of:
(i) linear decoding; (ii) correction of arbitrary single-bit errors; (iii) ability to actually store information.
Hamming(7,4) is linear, corrects arbitrary single bit errors, and stores four bits of information. Is there some extra implicit constraint I'm missing?
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Wed, Jan 16, 2019 at 11:25 AM Adam P. Goucher <apgoucher@gmx.com> wrote:
Hamming(7, 4) has linear encoding, but not linear decoding. For example:
0000 encodes to 0000000
which means (with the error-correcting property) that:
0000001 decodes to 0000 0000010 decodes to 0000 0000100 decodes to 0000 0001000 decodes to 0000 0010000 decodes to 0000 0100000 decodes to 0000 1000000 decodes to 0000
If the decoding function were linear, it would therefore be identically zero (which it isn't).
OK, I see. The syndrome is a linear function of the codewords, but the data is not. Thanks! -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
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
participants (4)
-
Adam P. Goucher -
Henry Baker -
Howard Cannon -
Mike Stay