BCH decoding

[osj1961]

see email from Alex K

[osj1961]

The first problem with this issue was that the special BCH decoding function was not even getting called. I wonder if it ever was...

Code objects have a SpecialDecoder attribute which is actually a function. Since BCH codes are first actualized as Cyclic Codes, the SpecialDecoder attribute was initialized to the "special" decoding function for cyclic codes, then later the BCH code constructor tries to call SetSpecialDecoder again to set the attribute to the BCH decoder function. This didn't work (and failed silently) because the SpecialDecoder attribute was immutable. I changed the declaration of the attribute to make it mutable and now the correct special decoding function is called. It still doesn't work but at least the expected method is running.

I think this SpecialDecoder attribute is a holdover from GAP3 thinking and now we should be using the method selection mechanism (with Filters) to call the appropriate decoder function for a code.

[osj1961]

Further investigation of why the BCH decoder returns "fail" even when trying to decode a codeword that was actually IN the code... I executed the decoder function one line at a time (Question: Is there something like a symbolic debugger for GAP, or is cutting and pasting one line at a time into the terminal the best that I can do?)

The first deviation from expected behavior came in evaluating membership in the code

with C a bch code and c a codeword (generated by Random(C)),

gap> c in C; false

Further investigation showed this same sort of (wrong) behavior when C was a code created via a generator polynomial.

gap>x:= Indeterminate( GF(2) );; P:= x^2+1;; gap> C:= GeneratorPolCode(P,7,GF(2)); a cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2) gap> c :=Random(C); [ 0 1 0 0 0 0 1 ] gap> c in C; false

There is a GUAVA method which should be called in this scenario but it isn't:

gap> TraceMethods(\in); gap> c in C;

I in: for wrong family relation

false

That info string comes from elsewhere (in list.gi in the top-level GAP libs)

There is a possible clue in a note in the reference manual:

Note: The GAP kernel provides special treatment for the infix operations+, -, *, \/, ^, \mod and \in. For some kernel objects (notably cyclotomic numbers, finite field elements and row vectors thereof) it calls kernel methods circumventing the method selection mechanism. Therefore for these operations ApplicableMethod may return a method which is not the kernel method actually used.

[osj1961]

Contrary to what the manual says, the BCH special decoder function is returning a corrected codeword (that is, the element of the BCH code closest to the received codeword). It is supposed to return an information word.

It seems strange to me that this function is working at all since the "in" operation is broken, and it uses it in several places.

[osj1961]

Here's a pretty minimal example showing the problem with "in":

gap> C := HammingCode(3); a linear [7,4,3]1 Hamming (3,2) code over GF(2) gap> x:= Indeterminate( GF(2) );; P:= x^3+x^2+1;; D:=GeneratorPolCode(P,7,GF(2)); a cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2) gap> c:=Random(C); [ 1 1 1 1 1 1 1 ] gap> c in C; true gap> d := Random(D); [ 1 1 0 1 0 0 1 ] gap> d in D; false

[olexandr-konovalov]

Using

ApplicableMethod(\in,[c,C],"all"); 
ApplicableMethod(\in,[d,D],"all");

I conclude that neither c in C nor d in D use GUAVA's methods. Which ones from GUAVA do you expect to be used?

[osj1961]

Guava defines several \in methods at around line 1390 in codeops.gi.
I think that for "c in C", the filters [IsCodeword, IsLinearCode] would be applicable and for "d in D" that would be [IsCodeword, IsCyclicCode]. That "note" in the manual that I referenced previously is making me think that GAP is looking at a codeword as being a list of FFEs and pre-empting the method selection mechanism...

[olexandr-konovalov]

When I call

ApplicableMethod(\in,[c,C],"all");

it tells that is uses

#I  Method 55: ``in: for vector and free left module that is handled by a nice basis'', value: 33
#I  Function Body:
function ( v, V )
    local  W, a;
    W := NiceFreeLeftModule( V );
    a := NiceVector( V, v );
    if a = fail  then
        return false;
    elif IsZero( a )  then
        return true;
    else
        return a in W and v = UglyVector( V, a );
    fi;
    return;
end

but when I call

ApplicableMethod(\in,[d,D],"all");

there is something wrong with the family relation:

gap> ApplicableMethod(\in,[d,D],"all");
#I  Searching Method for in with 2 arguments:
#I  Total: 98 entries
#I  Method 1: ``in: for a ring element and a union of res.-cl. with fixed rep's (ResClasses)'', value: 1*SUM_FLAGS+14
#I   - 1st argument needs [ "IsMultiplicativeElement" ]
#I   - 2nd argument needs [ "IsUnionOfResidueClassesWithFixedRepresentatives" ]
#I  Method 2: ``in: for an object, and a collection that contains the whole family'', value: 1*SUM_FLAGS+4
#I   - 2nd argument needs [ "IsWholeFamily", "Tester(IsWholeFamily)" ]
#I  Method 3: ``in: for wrong family relation'', value: 1*SUM_FLAGS+2
#I  Function Body:
function ( arg... )
    <<kernel or compiled code>>
endfunction( arg... ) ... end
gap> PageSource(last);
Cannot locate source of kernel function RETURN_FALSE.

This may point to the fact that d was not created in a proper way: this method for in says

InstallMethod( IN,
    "for wrong family relation",
    IsNotElmsColls,
    [ IsObject, IsCollection ],
    SUM_FLAGS, # can't do better
    ReturnFalse );

and this means that the following returns true:

IsNotElmsColls := function ( F1, F2 )
    return not HasElementsFamily( F2 )
       or IsNotIdenticalObj( F1, ElementsFamily(F2) );
end;

Indeed, we have

gap> FamilyObj(d);
NewFamily( "CodewordFamily", [ 2645 ], [ 16, 17, 18, 38, 43, 57, 102, 105, 109, 113, 117, 121, 124, 140, 2645, 2707 ] )
gap> ElementsFamily(FamilyObj(D));
NewFamily( "CollectionsFamily(...)", [ 58 ], [ 57, 58, 102, 103, 106, 110, 114, 118, 121, 122, 124, 125, 128, 132, 
  136, 140, 148, 155, 158, 162, 200, 554, 555 ] )

while in the working example we have

gap> FamilyObj(c);
NewFamily( "CodewordFamily", [ 2645 ], [ 16, 17, 18, 38, 43, 57, 102, 105, 109, 113, 117, 121, 124, 
  140, 2645, 2707 ] )
gap> ElementsFamily(FamilyObj(C));
NewFamily( "CodewordFamily", [ 2645 ], [ 16, 17, 18, 38, 43, 57, 102, 105, 109, 113, 117, 121, 124, 
  140, 2645, 2707 ] )

[osj1961]

Okay! That was exactly the hint I needed. I think I've got a fix (which I'll commit after testing)

[osj1961]

The actual creation of most Code objects is handled by LinearCodeByGenerators which expects a list of Codewords as its 2nd argument -- the generators of the code. In the case of codes that were created using a generator polynomial, the list of generators was created as vectors of FFEs and not converted to Codewords prior to being passed into LinearCodeByGenerators. Thus, such codes didn't get recognized as being collections of Codewords; causing the failure (d in D) referenced above. Many thanks to Alex K.!

[olexandr-konovalov]

@osj1961 great, thanks! How close are we to have a new release?

[osj1961]

Hi Alex,

Yes, Guava 3.13 is now live!

The Guava website has been down for a time and I just got a replacement together

and a "forward" put in place. I've been having ongoing problems with my university's web service which is/was part of my reason for migrating Guava to GitHub.

I've edited the old PackageInfo.g file so that the URLs for the README and PackageInfo.g point to the new location for Guava:

http://osj1961.github.io/guava/

If I understand things correctly this should mean the automatic system will figure out the new release.

Thanks again for all of your help!

-Joe

Joseph E. Fields Professor of Mathematics Southern Connecticut State University http://www.southernct.edu/~fields/

---

From: Alexander Konovalov notifications@github.com Sent: Friday, February 12, 2016 7:50 PM To: osj1961/guava Cc: Fields, Joseph Subject: Re: [guava] BCH decoding (#5)

@osj1961https://github.com/osj1961 great, thanks! How close are we to have a new release?

Reply to this email directly or view it on GitHubhttps://github.com/osj1961/guava/issues/5#issuecomment-183547930.

[olexandr-konovalov]

@osj1961 Thank you! The package update detected changes, but failed to pick up the new release:

Package: GUAVA
 changed components: [ "README_URL", "PackageInfoURL" ]
 ERROR (GUAVA): There are changed components in the new info file from
 http://www.southernct.edu/~fields/Guava/PackageInfo.g
  but .Version remains the same. This is not allowed, so the info file will not be changed
 PackageInfo.g is not accepted because of an error.

What you need to do is not to edit the old PackageInfo.g file but just replace it by the copy of the new one. Is this still possible? If not, I could specify the new address manually - please let me know.