Quelle  decoders.gd   Sprache: Shell

#############################################################################
##
#A  decoders.gd             GUAVA library                       Reinald Baart
#A                                                        &Jasper Cramwinckel
#A                                                           &Erik Roijackers
##                                                              &David Joyner
##
##  This file contains functions for decoding codes
##
## some commands moved form cdeops.gi and Decodeword added in 10-2004
## added GeneralizedReedSolomonDecoder 11-2005
## added GeneralizedReedSolomonListDecoder and GRS<functions>, 12-2004
## added PermutationDecoderNC, CyclicDecoder 5-2005
## 1-2006: added BitFlipDecoder
##

#############################################################################
##
#F  Decode( <C>, <v> )  . . . . . . . . .  decodes the word(s) v to
##                                 the information digits of a codeword in <C>
##                                        (<C> must be linear)
##
##  v can be a codeword or a list of codewords
##
DeclareOperation("Decode", [IsCode, IsCodeword]);

#############################################################################
##
#F  Decodeword( <C>, <v> )  . . . . . . . . .  decodes the word(s) v to
##                                                 a codeword in <C>
##                                        (<C> need not be linear)
##
##  v can be a codeword or a list of codewords
##
DeclareOperation("Decodeword", [IsCode, IsCodeword]);

#############################################################################
##
#F  PermutationDecode( <C>, <v> )    decodes the vector <v> from <C>
##
##  v is a vector (ie, a list)
##
DeclareOperation("PermutationDecode", [IsLinearCode, IsList]);

#############################################################################
##
#F  PermutationDecodeNC( <C>, <v>, <P> )    decodes the vector <v> to <C>,
##
##  v is a vector (ie, a list), P subset Aut(C) is a finite permutation aut gp
##
DeclareOperation("PermutationDecodeNC", [IsLinearCode,IsCodeword,IsGroup]);

########################################################################
##
#F  SpecialDecoder( <code> )
##
##  Special function to decode
##
DeclareAttribute("SpecialDecoder", IsCode, "mutable");

#############################################################################
##
#F  BCHDecoder( <C>, <r> )  . . . . . . . . . . . . . . . . decodes BCH codes
##
DeclareOperation("BCHDecoder", [IsCode, IsCodeword]);

#############################################################################
##
#F  CyclicDecoder( <C>, <r> )  . . . . . . . . . . . . . decodes cyclic codes
##
DeclareOperation("CyclicDecoder", [IsCode, IsCodeword]);

#############################################################################
##
#F  HammingDecoder( <C>, <r> )  . . . . . . . . . . . . decodes Hamming codes
##
##  Generator matrix must have all unit columns
DeclareOperation("HammingDecoder", [IsCode, IsCodeword]);


#############################################################################
##
#F  GeneralizedReedSolomonDecoderGao( <C>, <v> )   . . decodes
##                                           generalized Reed-Solomon codes
##                                           using S. Gao's method
##
DeclareOperation("GeneralizedReedSolomonDecoderGao", [IsCode, IsCodeword]);

##########################################################
##
## GRSLocatorMat( <r> , <Xlist> , <L> )
## Input: Xlist=[x1,..,xn], l = highest power,
##       L=[h_1,...,h_ell] is list of powers
##       r=[r1,...,rn] is received vector
## Output: Computes matrix described in Algor. 12.1.1 in [JH]
##
## needed for both GeneralizedReedSolomonDecoder
##             and GeneralizedReedSolomonListDecoder

##############################################################
##
##  GRSErrorLocatorCoeffs( <r> , <Pts> , <L> )
##
## Input: Pts=[x1,..,xn],
##        L=[h_1,...,h_ell] is list of powers
##        r=[r1,...,rn] is received vector
##
## Output: the lists of coefficients of the polynomial Q(x,y) in alg 12.1.1.
##

#######################################################
##
##  GRSErrorLocatorPolynomials( <r> , <Pts> , <L> , <R> )
##
## Input: List L of ell_j,
##        R = F[x],
##        Pts=[x1,..,xn],
##        r=[r1,...,rn] is received vector
## Output: list of polynomials Qi as in Algor. 12.1.1 in [JH]
##

##########################################################
##
##   GRSInterpolatingPolynomial( <r> , <Pts> , <L> , <R> )
##
## Input: List L of ell_j
##        R = F[x]
##        Pts=[x1,..,xn],
##        r=[r1,...,rn] is received vector
## Output: interpolating polynomial Q as in Algor. 12.1.1 in [JH]
##

#############################################################################
##
#F  GeneralizedReedSolomonDecoder( <C>, <v> )   . . decodes
##                                           generalized Reed-Solomon codes
##                                           using the interpolation algorithm
##
DeclareOperation("GeneralizedReedSolomonDecoder", [IsCode, IsCodeword]);

#############################################################################
##
#F  GeneralizedReedSolomonListDecoder( <C>, <v> , <ell> )   . . ell-list decodes
##                                           generalized Reed-Solomon codes
##                                           using M. Sudan's algorithm
##
DeclareOperation("GeneralizedReedSolomonListDecoder",[IsCode, IsCodeword, IsInt]);

#############################################################################
##
#F  NearestNeighborGRSDecodewords( <C>, <v> , <dist> )   . . . finds all
##                                           generalized Reed-Solomon codewords
##                                           within distance <dist> from v
##                                           *and* the associated polynomial,
##                                           using "brute force"
##
## Input: v is a received vector (a GUAVA codeword)
##        C is a GRS code
##        dist>0 is the distance from v to search
## Output: a list of pairs [c,f(x)], where wt(c-v)<dist
##         and c = (f(x1),...,f(xn))
##
## ****** very slow*****
##
DeclareOperation("NearestNeighborGRSDecodewords",[IsCode, IsCodeword, IsInt]);

#############################################################################
##
#F  NearestNeighborDecodewords( <C>, <v> , <dist> )   . . . finds all
##                                           codewords in a linear code C
##                                           within distance <dist> from v
##                                           using "brute force"
##
## Input: v is a received vector (a GUAVA codeword)
##        C is a linear code
##        dist>0 is the distance from v to search
## Output: a list of c in C, where wt(c-v)<dist
##
## ****** very slow*****
##
DeclareOperation("NearestNeighborDecodewords",[IsCode, IsCodeword, IsInt]);
#############################################################################
##
#F  BitFlipDecoder( <C>, <v>  )   . . . decodes *binary* LDPC codes using bit-flipping
##                                                           or Gallager hard-decision
##               ** often fails to work if C is not LDPC **
##
## Input: v is a received vector (a GUAVA codeword)
##        C is a binary LDPC code
## Output: a c in C, where wt(c-v)<mindis(C)
##
## ****** fast *****
##
DeclareOperation("BitFlipDecoder",[IsCode, IsCodeword]);