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