GNU Radio's SATNOGS Package
decode_rs.h
Go to the documentation of this file.
1/* The guts of the Reed-Solomon decoder, meant to be #included
2 * into a function body with the following typedefs, macros and variables supplied
3 * according to the code parameters:
4
5 * data_t - a typedef for the data symbol
6 * data_t data[] - array of NN data and parity symbols to be corrected in place
7 * retval - an integer lvalue into which the decoder's return code is written
8 * NROOTS - the number of roots in the RS code generator polynomial,
9 * which is the same as the number of parity symbols in a block.
10 Integer variable or literal.
11 * NN - the total number of symbols in a RS block. Integer variable or literal.
12 * PAD - the number of pad symbols in a block. Integer variable or literal.
13 * ALPHA_TO - The address of an array of NN elements to convert Galois field
14 * elements in index (log) form to polynomial form. Read only.
15 * INDEX_OF - The address of an array of NN elements to convert Galois field
16 * elements in polynomial form to index (log) form. Read only.
17 * MODNN - a function to reduce its argument modulo NN. May be inline or a macro.
18 * FCR - An integer literal or variable specifying the first consecutive root of the
19 * Reed-Solomon generator polynomial. Integer variable or literal.
20 * PRIM - The primitive root of the generator poly. Integer variable or literal.
21 * DEBUG - If set to 1 or more, do various internal consistency checking. Leave this
22 * undefined for production code
23
24 * The memset(), memmove(), and memcpy() functions are used. The appropriate header
25 * file declaring these functions (usually <string.h>) must be included by the calling
26 * program.
27 */
28
29
30#if !defined(NROOTS)
31#error "NROOTS not defined"
32#endif
33
34#if !defined(NN)
35#error "NN not defined"
36#endif
37
38#if !defined(PAD)
39#error "PAD not defined"
40#endif
41
42#if !defined(ALPHA_TO)
43#error "ALPHA_TO not defined"
44#endif
45
46#if !defined(INDEX_OF)
47#error "INDEX_OF not defined"
48#endif
49
50#if !defined(MODNN)
51#error "MODNN not defined"
52#endif
53
54#if !defined(FCR)
55#error "FCR not defined"
56#endif
57
58#if !defined(PRIM)
59#error "PRIM not defined"
60#endif
61
62#if !defined(NULL)
63#define NULL ((void *)0)
64#endif
65
66#undef MIN
67#define MIN(a,b) ((a) < (b) ? (a) : (b))
68#undef A0
69#define A0 (NN)
70
71{
73 int i, j, r, k;
75 data_t lambda[NROOTS + 1], s[NROOTS]; /* Err+Eras Locator poly
76 * and syndrome poly */
77 data_t b[NROOTS + 1], t[NROOTS + 1], omega[NROOTS + 1];
80
81 /* form the syndromes; i.e., evaluate data(x) at roots of g(x) */
82 for (i = 0; i < NROOTS; i++)
83 {
84 s[i] = data[0];
85 }
86
87 for (j = 1; j < NN - PAD; j++)
88 {
89 for (i = 0; i < NROOTS; i++) {
90 if (s[i] == 0) {
91 s[i] = data[j];
92 }
93 else {
94 s[i] = data[j] ^ ALPHA_TO[MODNN(INDEX_OF[s[i]] + (FCR + i) * PRIM)];
95 }
96 }
97 }
98
99 /* Convert syndromes to index form, checking for nonzero condition */
100 syn_error = 0;
101 for (i = 0; i < NROOTS; i++)
102 {
103 syn_error |= s[i];
104 s[i] = INDEX_OF[s[i]];
105 }
106
108 {
109 /* if syndrome is zero, data[] is a codeword and there are no
110 * errors to correct. So return data[] unmodified
111 */
112 count = 0;
113 goto finish;
114 }
115 memset(&lambda[1], 0, NROOTS * sizeof(lambda[0]));
116 lambda[0] = 1;
117
118 if (no_eras > 0)
119 {
120 /* Init lambda to be the erasure locator polynomial */
121 lambda[1] = ALPHA_TO[MODNN(PRIM * (NN - 1 - eras_pos[0]))];
122 for (i = 1; i < no_eras; i++) {
123 u = MODNN(PRIM * (NN - 1 - eras_pos[i]));
124 for (j = i + 1; j > 0; j--) {
125 tmp = INDEX_OF[lambda[j - 1]];
126 if (tmp != A0) {
127 lambda[j] ^= ALPHA_TO[MODNN(u + tmp)];
128 }
129 }
130 }
131
132#if DEBUG >= 1
133 /* Test code that verifies the erasure locator polynomial just constructed
134 Needed only for decoder debugging. */
135
136 /* find roots of the erasure location polynomial */
137 for (i = 1; i <= no_eras; i++) {
138 reg[i] = INDEX_OF[lambda[i]];
139 }
140
141 count = 0;
142 for (i = 1, k = IPRIM - 1; i <= NN; i++, k = MODNN(k + IPRIM)) {
143 q = 1;
144 for (j = 1; j <= no_eras; j++)
145 if (reg[j] != A0) {
146 reg[j] = MODNN(reg[j] + j);
147 q ^= ALPHA_TO[reg[j]];
148 }
149 if (q != 0) {
150 continue;
151 }
152 /* store root and error location number indices */
153 root[count] = i;
154 loc[count] = k;
155 count++;
156 }
157 if (count != no_eras) {
158 printf("count = %d no_eras = %d\n lambda(x) is WRONG\n", count, no_eras);
159 count = -1;
160 goto finish;
161 }
162#if DEBUG >= 2
163 printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n");
164 for (i = 0; i < count; i++) {
165 printf("%d ", loc[i]);
166 }
167 printf("\n");
168#endif
169#endif
170 }
171 for (i = 0; i < NROOTS + 1; i++)
172 {
173 b[i] = INDEX_OF[lambda[i]];
174 }
175
176 /*
177 * Begin Berlekamp-Massey algorithm to determine error+erasure
178 * locator polynomial
179 */
180 r = no_eras;
181 el = no_eras;
182 while (++r <= NROOTS) /* r is the step number */
183 {
184 /* Compute discrepancy at the r-th step in poly-form */
185 discr_r = 0;
186 for (i = 0; i < r; i++) {
187 if ((lambda[i] != 0) && (s[r - i - 1] != A0)) {
188 discr_r ^= ALPHA_TO[MODNN(INDEX_OF[lambda[i]] + s[r - i - 1])];
189 }
190 }
191 discr_r = INDEX_OF[discr_r]; /* Index form */
192 if (discr_r == A0) {
193 /* 2 lines below: B(x) <-- x*B(x) */
194 memmove(&b[1], b, NROOTS * sizeof(b[0]));
195 b[0] = A0;
196 }
197 else {
198 /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */
199 t[0] = lambda[0];
200 for (i = 0 ; i < NROOTS; i++) {
201 if (b[i] != A0) {
202 t[i + 1] = lambda[i + 1] ^ ALPHA_TO[MODNN(discr_r + b[i])];
203 }
204 else {
205 t[i + 1] = lambda[i + 1];
206 }
207 }
208 if (2 * el <= r + no_eras - 1) {
209 el = r + no_eras - el;
210 /*
211 * 2 lines below: B(x) <-- inv(discr_r) *
212 * lambda(x)
213 */
214 for (i = 0; i <= NROOTS; i++) {
215 b[i] = (lambda[i] == 0) ? A0 : MODNN(INDEX_OF[lambda[i]] - discr_r + NN);
216 }
217 }
218 else {
219 /* 2 lines below: B(x) <-- x*B(x) */
220 memmove(&b[1], b, NROOTS * sizeof(b[0]));
221 b[0] = A0;
222 }
223 memcpy(lambda, t, (NROOTS + 1)*sizeof(t[0]));
224 }
225 }
226
227 /* Convert lambda to index form and compute deg(lambda(x)) */
229 for (i = 0; i < NROOTS + 1; i++)
230 {
231 lambda[i] = INDEX_OF[lambda[i]];
232 if (lambda[i] != A0) {
233 deg_lambda = i;
234 }
235 }
236 /* Find roots of the error+erasure locator polynomial by Chien search */
237 memcpy(&reg[1], &lambda[1], NROOTS * sizeof(reg[0]));
238 count = 0; /* Number of roots of lambda(x) */
239 for (i = 1, k = IPRIM - 1; i <= NN; i++, k = MODNN(k + IPRIM))
240 {
241 q = 1; /* lambda[0] is always 0 */
242 for (j = deg_lambda; j > 0; j--) {
243 if (reg[j] != A0) {
244 reg[j] = MODNN(reg[j] + j);
245 q ^= ALPHA_TO[reg[j]];
246 }
247 }
248 if (q != 0) {
249 continue; /* Not a root */
250 }
251 /* store root (index-form) and error location number */
252#if DEBUG>=2
253 printf("count %d root %d loc %d\n", count, i, k);
254#endif
255 root[count] = i;
256 loc[count] = k;
257 /* If we've already found max possible roots,
258 * abort the search to save time
259 */
260 if (++count == deg_lambda) {
261 break;
262 }
263 }
265 {
266 /*
267 * deg(lambda) unequal to number of roots => uncorrectable
268 * error detected
269 */
270 count = -1;
271 goto finish;
272 }
273 /*
274 * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
275 * x**NROOTS). in index form. Also find deg(omega).
276 */
278 for (i = 0; i <= deg_omega; i++)
279 {
280 tmp = 0;
281 for (j = i; j >= 0; j--) {
282 if ((s[i - j] != A0) && (lambda[j] != A0)) {
283 tmp ^= ALPHA_TO[MODNN(s[i - j] + lambda[j])];
284 }
285 }
286 omega[i] = INDEX_OF[tmp];
287 }
288
289 /*
290 * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
291 * inv(X(l))**(FCR-1) and den = lambda_pr(inv(X(l))) all in poly-form
292 */
293 for (j = count - 1; j >= 0; j--)
294 {
295 num1 = 0;
296 for (i = deg_omega; i >= 0; i--) {
297 if (omega[i] != A0) {
298 num1 ^= ALPHA_TO[MODNN(omega[i] + i * root[j])];
299 }
300 }
301 num2 = ALPHA_TO[MODNN(root[j] * (FCR - 1) + NN)];
302 den = 0;
303
304 /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */
305 for (i = MIN(deg_lambda, NROOTS - 1) & ~1; i >= 0; i -= 2) {
306 if (lambda[i + 1] != A0) {
307 den ^= ALPHA_TO[MODNN(lambda[i + 1] + i * root[j])];
308 }
309 }
310#if DEBUG >= 1
311 if (den == 0) {
312 printf("\n ERROR: denominator = 0\n");
313 count = -1;
314 goto finish;
315 }
316#endif
317 /* Apply error to data */
318 if (num1 != 0 && loc[j] >= PAD) {
319 data[loc[j] - PAD] ^= ALPHA_TO[MODNN(INDEX_OF[num1] + INDEX_OF[num2] + NN -
320 INDEX_OF[den])];
321 }
322 }
323finish:
324 if (eras_pos != NULL)
325 {
326 for (i = 0; i < count; i++) {
327 eras_pos[i] = loc[i];
328 }
329 }
330 retval = count;
331}
#define NN
Definition: ccsds.h:3
#define NROOTS
Definition: ccsds.h:4
unsigned char data_t
Definition: ccsds.h:1
#define FCR
Definition: char.h:16
#define PAD
Definition: char.h:19
#define MODNN(x)
Definition: char.h:8
#define INDEX_OF
Definition: char.h:13
#define PRIM
Definition: char.h:17
#define IPRIM
Definition: char.h:18
#define ALPHA_TO
Definition: char.h:12
data_t q
Definition: decode_rs.h:74
#define NULL
Definition: decode_rs.h:63
data_t num2
Definition: decode_rs.h:74
#define A0
Definition: decode_rs.h:69
data_t lambda[NROOTS+1]
Definition: decode_rs.h:75
data_t num1
Definition: decode_rs.h:74
data_t reg[NROOTS+1]
Definition: decode_rs.h:78
data_t loc[NROOTS]
Definition: decode_rs.h:78
int j
Definition: decode_rs.h:73
#define MIN(a, b)
Definition: decode_rs.h:67
int syn_error
Definition: decode_rs.h:79
int r
Definition: decode_rs.h:73
data_t den
Definition: decode_rs.h:74
deg_omega
Definition: decode_rs.h:277
data_t discr_r
Definition: decode_rs.h:74
el
Definition: decode_rs.h:181
data_t s[NROOTS]
Definition: decode_rs.h:75
data_t u
Definition: decode_rs.h:74
data_t tmp
Definition: decode_rs.h:74
data_t t[NROOTS+1]
Definition: decode_rs.h:77
int k
Definition: decode_rs.h:73
int i
Definition: decode_rs.h:73
data_t omega[NROOTS+1]
Definition: decode_rs.h:77
data_t root[NROOTS]
Definition: decode_rs.h:78
int count
Definition: decode_rs.h:79
deg_lambda
Definition: decode_rs.h:228
data_t b[NROOTS+1]
Definition: decode_rs.h:77
memset(parity, 0, NROOTS *sizeof(data_t))