1############################################################################# 2## 3#A decoders.gd GUAVA library Reinald Baart 4#A &Jasper Cramwinckel 5#A &Erik Roijackers 6## &David Joyner 7## 8## This file contains functions for decoding codes 9## 10## some commands moved form cdeops.gi and Decodeword added in 10-2004 11## added GeneralizedReedSolomonDecoder 11-2005 12## added GeneralizedReedSolomonListDecoder and GRS<functions>, 12-2004 13## added PermutationDecoderNC, CyclicDecoder 5-2005 14## 1-2006: added BitFlipDecoder 15## 16 17############################################################################# 18## 19#F Decode( <C>, <v> ) . . . . . . . . . decodes the word(s) v to 20## the information digits of a codeword in <C> 21## (<C> must be linear) 22## 23## v can be a codeword or a list of codewords 24## 25DeclareOperation("Decode", [IsCode, IsCodeword]); 26 27############################################################################# 28## 29#F Decodeword( <C>, <v> ) . . . . . . . . . decodes the word(s) v to 30## a codeword in <C> 31## (<C> need not be linear) 32## 33## v can be a codeword or a list of codewords 34## 35DeclareOperation("Decodeword", [IsCode, IsCodeword]); 36 37############################################################################# 38## 39#F PermutationDecode( <C>, <v> ) decodes the vector <v> from <C> 40## 41## v is a vector (ie, a list) 42## 43DeclareOperation("PermutationDecode", [IsLinearCode, IsList]); 44 45############################################################################# 46## 47#F PermutationDecodeNC( <C>, <v>, <P> ) decodes the vector <v> to <C>, 48## 49## v is a vector (ie, a list), P subset Aut(C) is a finite permutation aut gp 50## 51DeclareOperation("PermutationDecodeNC", [IsLinearCode,IsCodeword,IsGroup]); 52 53######################################################################## 54## 55#F SpecialDecoder( <code> ) 56## 57## Special function to decode 58## 59DeclareAttribute("SpecialDecoder", IsCode, "mutable"); 60 61############################################################################# 62## 63#F BCHDecoder( <C>, <r> ) . . . . . . . . . . . . . . . . decodes BCH codes 64## 65DeclareOperation("BCHDecoder", [IsCode, IsCodeword]); 66 67############################################################################# 68## 69#F CyclicDecoder( <C>, <r> ) . . . . . . . . . . . . . decodes cyclic codes 70## 71DeclareOperation("CyclicDecoder", [IsCode, IsCodeword]); 72 73############################################################################# 74## 75#F HammingDecoder( <C>, <r> ) . . . . . . . . . . . . decodes Hamming codes 76## 77## Generator matrix must have all unit columns 78DeclareOperation("HammingDecoder", [IsCode, IsCodeword]); 79 80 81############################################################################# 82## 83#F GeneralizedReedSolomonDecoderGao( <C>, <v> ) . . decodes 84## generalized Reed-Solomon codes 85## using S. Gao's method 86## 87DeclareOperation("GeneralizedReedSolomonDecoderGao", [IsCode, IsCodeword]); 88 89########################################################## 90## 91## GRSLocatorMat( <r> , <Xlist> , <L> ) 92## Input: Xlist=[x1,..,xn], l = highest power, 93## L=[h_1,...,h_ell] is list of powers 94## r=[r1,...,rn] is received vector 95## Output: Computes matrix described in Algor. 12.1.1 in [JH] 96## 97## needed for both GeneralizedReedSolomonDecoder 98## and GeneralizedReedSolomonListDecoder 99 100############################################################## 101## 102## GRSErrorLocatorCoeffs( <r> , <Pts> , <L> ) 103## 104## Input: Pts=[x1,..,xn], 105## L=[h_1,...,h_ell] is list of powers 106## r=[r1,...,rn] is received vector 107## 108## Output: the lists of coefficients of the polynomial Q(x,y) in alg 12.1.1. 109## 110 111####################################################### 112## 113## GRSErrorLocatorPolynomials( <r> , <Pts> , <L> , <R> ) 114## 115## Input: List L of ell_j, 116## R = F[x], 117## Pts=[x1,..,xn], 118## r=[r1,...,rn] is received vector 119## Output: list of polynomials Qi as in Algor. 12.1.1 in [JH] 120## 121 122########################################################## 123## 124## GRSInterpolatingPolynomial( <r> , <Pts> , <L> , <R> ) 125## 126## Input: List L of ell_j 127## R = F[x] 128## Pts=[x1,..,xn], 129## r=[r1,...,rn] is received vector 130## Output: interpolating polynomial Q as in Algor. 12.1.1 in [JH] 131## 132 133############################################################################# 134## 135#F GeneralizedReedSolomonDecoder( <C>, <v> ) . . decodes 136## generalized Reed-Solomon codes 137## using the interpolation algorithm 138## 139DeclareOperation("GeneralizedReedSolomonDecoder", [IsCode, IsCodeword]); 140 141############################################################################# 142## 143#F GeneralizedReedSolomonListDecoder( <C>, <v> , <ell> ) . . ell-list decodes 144## generalized Reed-Solomon codes 145## using M. Sudan's algorithm 146## 147DeclareOperation("GeneralizedReedSolomonListDecoder",[IsCode, IsCodeword, IsInt]); 148 149############################################################################# 150## 151#F NearestNeighborGRSDecodewords( <C>, <v> , <dist> ) . . . finds all 152## generalized Reed-Solomon codewords 153## within distance <dist> from v 154## *and* the associated polynomial, 155## using "brute force" 156## 157## Input: v is a received vector (a GUAVA codeword) 158## C is a GRS code 159## dist>0 is the distance from v to search 160## Output: a list of pairs [c,f(x)], where wt(c-v)<dist 161## and c = (f(x1),...,f(xn)) 162## 163## ****** very slow***** 164## 165DeclareOperation("NearestNeighborGRSDecodewords",[IsCode, IsCodeword, IsInt]); 166 167############################################################################# 168## 169#F NearestNeighborDecodewords( <C>, <v> , <dist> ) . . . finds all 170## codewords in a linear code C 171## within distance <dist> from v 172## using "brute force" 173## 174## Input: v is a received vector (a GUAVA codeword) 175## C is a linear code 176## dist>0 is the distance from v to search 177## Output: a list of c in C, where wt(c-v)<dist 178## 179## ****** very slow***** 180## 181DeclareOperation("NearestNeighborDecodewords",[IsCode, IsCodeword, IsInt]); 182############################################################################# 183## 184#F BitFlipDecoder( <C>, <v> ) . . . decodes *binary* LDPC codes using bit-flipping 185## or Gallager hard-decision 186## ** often fails to work if C is not LDPC ** 187## 188## Input: v is a received vector (a GUAVA codeword) 189## C is a binary LDPC code 190## Output: a c in C, where wt(c-v)<mindis(C) 191## 192## ****** fast ***** 193## 194DeclareOperation("BitFlipDecoder",[IsCode, IsCodeword]); 195