figure 6: folding of the Reed–solomon code with parameter m = 4. each column represents an alphabet character.

f(x ) f(x ) f(x ) f(x ) f(x ) f(x ) f(x ) f(x )

01234567

f(x ) f(x ) f(x ) f(x ) n− 4 n− 3 n− 2 n− 1

f(x ) f(x )
04
f(x ) f(x )

15 f(x ) f(x )

26 f(x ) f(x )

37

f(x )
n− 4
f(x )
n− 3
f(x )
n− 2
f(x )
n− 1

error pattern over the original symbols needs to be taken care of in the Reed–Solomon case).

We would like to stress on a subtle point here: in the worst-case error model, the “atomic” unit of error is an alphabet character. This was used crucially in the example above to rule out an error pattern that was admissible for the smaller alphabet. For the reader who might we worried that this constitutes “cheating,” e.g., what if one collapses the entire RS codeword into one large symbol, we offer two counter-points. First, since we will only use a constant folding parameter, the increase in alphabet size from that of RS codes is modest. Second, in Section 4, we will see how to convert folded RS codes into codes over alphabets whose size does not depend at all on the block length, while still maintaining similar error-correction properties.

We now formally define the folded RS code. Let the non-zero elements of the field F be generated by g, i.e., every nonzero element is g ⁱ for some 0 ≤ i ≤ |F| − 2 (such a g always exists for any finite field F). Let m ≥ 1 be the folding parameter and let n be an integer that is divisible by m and n ≤ |F| − 1. The folded RS encoding (with folding parameter m) of the message polynomial f (X) has as its j’th symbol for 0 ≤ j < n/m, the m -tuple ( f (g ^j m), f (g ^{jm + 1}), . . . , f (g ^{jm + m − 1}) ).

The block length of these codes is N = n/m. The rate of the code remains k/n, since the folding operation does not introduce any further redundancy.

The folding operation does restrict the error patterns that one needs to worry about. But how can one actually exploit this in a decoding algorithm and manage to correct a larger fraction of errors compared to the unfolded RS codes? We turn to this question next.

3. 1. multivariate decoding

Recall the two step Guruswami–Sudan (GS) algorithm. First, we interpolate a bivariate polynomial Q(X, Y) through the points (a , y ) Î F². Then in the second step, we factor- ii

ize the bivariate polynomial and retain factors of the form
Y − f (X), where f (X) is a polynomial of degree less than k (there
might be factors that are not linear in Y: we ignore them).
Let us recast the second step in an equivalent description,
which will be useful later. In particular, consider the univari-
ate polynomial R (Y ) equivalent to Q(X, Y ), where the coef-
X
ficients themselves are polynomials in indeterminate X with
their own coefficients from F: given the polynomial Q(X, Y)
one can compute R (Y) by collecting all the coefficients of
X
the same power of Y together (e.g., if Q(X, Y) = (Y −(X − 1))
(Y² +X³) thenR (Y) =a Y³ + a ^. Y² +a ^. Y +a , wherea = 1,
X32 1 0 3

92 communications of the acm | march 2009 | Vol. 52 | no. 3

a = −X + 1, a = X ³ and a − X ⁴ + X ³). Now note that Y − f (X)
210
is a factor of Q(X, Y) if and only if f (X) is a root of the uni-
variate polynomial R (Y), that is, the polynomial R ( f (X) ) is
XY
the same as the zero polynomial (in the example, Y −(X − 1)
divides Q(X, Y) and R (X − 1) ≡ 0).

X

Let us now return to problem of list decoding folded RS code with m = 4. Given the received word whose ith symbol

(for 0 ≤ i < N) is ( y , y , y , y ), we need to output all the
i,0 i, 1 i, 2 i, 3
close-by folded RS codewords. To motivate the idea behind
the algorithm, for the time being assume that the transmit-
ted codeword was from the so-called interleaved RS code of
order 4. Any code word in such a code will have as its ith symbol
(0 ≤ i ≤ N − 1) the 4-tuple ( f (g ⁴ⁱ), f (g ⁴ⁱ), f (g ⁴ⁱ), f (g ⁴ⁱ) ), where
123
f (X), f (X), f (X) and f (X) are some polynomials of degree at
12 3
most k − 1. We remark that the folded RS code is a subcode^e
of the interleaved RS code where f (X ) = f (g ^j X) for 1 ≤ j ≤ 3.
j
Given the setup above, the first thing to explore is whether
one can generalize the GS algorithm to the setting of inter-
leaved RS codes. To see one such generalization, note that
RS codes are interleaved RS codes of order 1. The GS algo-
rithm interpolated a nonzero bivariate polynomial Q(X, Y) in
this case. Thus, for an interleaved RS code of order 4, a natu-
ral attempt would be to compute a nonzero 5-variate poly-
nomial Q(X, Y, Z, U, W), where (as before) Y is a placeholder
for f (X) and (this part is the generalization) Z, U, and W are
placeholders for f (X), f (X), and f (X), respectively. For the
12 3
next step of root finding, we compute the 4-variate polyno-
mial R (Y, Z, U, W) that is equivalent to Q(X, Y, Z, U, W ). Now
X
the hope would be to find out all the tuples ( Y, Z, U, W ) that
make R (Y, Z, U, W) vanish and that the required tuple ( f (X),
X
f (X), f (X), f (X) ) is one of them. The latter condition can in
123
fact be satisfied, but the trouble is that the number of tuples
that make R zero could be very large (growing exponentially
X
in n). To see intuitively what goes wrong, recall that in the
Guruswami–Sudan setting, we had one unknown Y and one
constraint R ( Y) = 0. However, in the interleaved RS setting,
X
we have four unknowns Y, Z, U, W but only one constraint
R (Y, Z, U, W) = 0. This essentially means that three of the
X
four unknowns are unconstrained and can thus be almost
any polynomial of degree less than k.
The generalization above (and similar ideas) were
tried out in a few works, but could not decode beyond
the radius. Finally, 7 years after the GS algorithm
was published, Parvaresh and Vardy¹⁴ had an ingenious
idea: force the polynomials f (X), f (X) and f (X) to be related
12 3
to f (X). In particular, they only look at the subcode of the
interleaved RS code where f (X) = ( f (X))^d mod (E(X)) for
j j− 1
1 ≤ j ≤ 3 (we set f (X) = f (X) ), for some positive integer param-
0
eter d and an irreducible polynomial E(X). The reason we
compute the modulus using an irreducible polynomial is
that the relationships between these polynomials translate
to the following relationships between their corresponding
23
placeholders: Z = Y ^d, U = Y ^d , and W = Y ^d . In other words, we
gain three new constraints on the four variables Y, Z, U, W.
Together with the interpolation constraint R (Y, Z, U, W) = 0,
X

this restores equality in the number of unknowns and the number of constraints. This in turn implies that the number

e

This is the same as looking at an appropriate subset of messages.