Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up

ReedSolomon decoding is broken #41

Open
@fblomqvi

Description

@fblomqvi

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

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions


      [8]ページ先頭

      ©2009-2025 Movatter.jp