- Notifications
You must be signed in to change notification settings - Fork8
Open
Description
I run GAP 4.8.8 with Guava 3.14 on Fedora 28. The ReedSolomon decoding seems to be broken in at least two ways.
The decoder crashes with some inputs:
gap> C := ReedSolomonCode(10,5);a cyclic [10,6,5]3..4 Reed-Solomon code over GF(11)gap> r := Codeword([7,10,3,2,4,9,5,7,5,9], C);[ 7 10 3 2 4 9 5 7 5 9 ]gap> Decodeword(C, r);Error, FFE operations: <divisor> must not be zero in return Value( rnew, a ^ (- i) ) / Value( pol, a ^ (- i) ) ; at /usr/lib/gap/pkg/guava/lib/decoders.gi:380 called fromfunc( C[i] ) at /usr/lib/gap/lib/coll.gi:746 called fromList( ErrorLocator, function ( i ) return Value( rnew, a ^ (- i) ) / Value( pol, a ^ (- i) ); end ) at /usr/lib/gap/pkg/guava/lib/decoders.gi:380 called fromSpecialDecoder( C )( C, c ) at /usr/lib/gap/pkg/guava/lib/decoders.gi:146 called from<function "unknown">( <arguments> ) called from read-eval loop at line 28 of *stdin*you can replace <divisor> via 'return <divisor>;'brk>
The same also happens with eg.
r := Codeword([ 10 7 3 1 8 1 8 7 4 8 ], C);r := Codeword([ 4 0 0 6 5 0 0 0 0 0 ], C);r := Codeword([ 5 1 1 7 2 6 4 6 1 5 ] , C);
Additionally, the decoder fails silently with some inputs:
gap> C := ReedSolomonCode(10,4);a cyclic [10,7,4]2..3 Reed-Solomon code over GF(11)gap> r := Codeword([2,7,8,3,7,10,3,4,3,4], C);[ 2 7 8 3 7 10 3 4 3 4 ]gap> c := Decodeword(C, r);[ 2 7 8 3 3 10 3 4 3 4 ]gap> c in C;false
The distance from r to a closest codeword is 2, so r might not be uniquely decodable. Thus this could be considered a feature. On the other hand, we have:
gap> C:=ReedSolomonCode(10,5);a cyclic [10,6,5]3..4 Reed-Solomon code over GF(11)gap> r := Codeword([3,7,5,5,1,10,3,9,2,8], C);[ 3 7 5 5 1 10 3 9 2 8 ]gap> Decodeword(C, r);Error, not decodable called fromSpecialDecoder( C )( C, c ) at /usr/lib/gap/pkg/guava/lib/decoders.gi:146 called from<function "unknown">( <arguments> ) called from read-eval loop at line 17 of *stdin*you can 'quit;' to quit to outer loop, oryou can 'return;' to continuebrk>
and hence it seems logical to consider the silent failure a bug.
I am aware that the special decoder used for ReedSolomon codes is the BCH decoder. So maybe it would be more appropriate to say that the BCH decoder is broken. I have, however, only used the decoder with ReedSolomon codes, so I'm choosing the more conservative title.
Metadata
Metadata
Assignees
Labels
No labels