Eighth International Workshop on Optimal Codes and Related Topics
July 10-14, 2017, Sofia, Bulgaria

pp. xxx-xxx

Code Constructions based on
Reed-Solomon Codes

arXiv:1706.05830v1 [cs.IT] 19 Jun 2017

Michael Schelling

michael.schelling@uni-ulm.de

Institute of Communications Engineering, University of Ulm, Germany

Martin Bossert

martin.bossert@uni-ulm.de

Institute of Communications Engineering, University of Ulm, Germany

Abstract. Reed–Solomon codes are a well–studied code class which fulfill the
Singleton bound with equality. However, their length is limited to the size q of
the underlying field Fq . In this paper we present a code construction which yields
codes with lengths of factors of the field size. Furthermore a decoding algorithm
beyond half the minimum distance is given and analyzed.

1

Introduction

Reed–Solomon (RS) codes were introduced in [1] and are well–studied and
widely used in various applications. This is due to the fact that RS Codes
are maximum distance separable (MDS) codes and due to the existence of efficient decoding algorithms. The classical decoding algorithms are the Peterson
algorithm [2], the Berlekamp–Massey algorithm [3], and the Sugiyama et al. algorithm [4]. Recently, in 2008, Wu [5] described list decoding algorithms based
on an extension of the Berlekamp-Massey algorithm.
A main drawback of these codes is that their length is limited be the size q of
the used field Fq .
In [6] Wu introduced generalized integrated (GII) RS-Codes which allows to
construct longer codes based on RS codes.
The code construction presented in this paper is based on a generalized version of the Plotkin-construction [7] and yields the same length and minimumdistance as Wu’s GII codes for an interleaving degree ν = 3.

2

2

OC2017

Code Construction

Let n, q ∈ N with n ≤ q and q = pm .
Consider the RS Codes Ca (n, ka , da ), Cb (n, kb , db ) and Cz (n, kz , dz ) over the field
Fq , such that
Cz ⊆ Cb ⊆ Ca .
This especially implies
da ≤ db ≤ dz and ka ≥ kb ≥ kz .
Construction 1. The code C is defined using a generalized Plotkin-construction.
Let α ∈ Fq \{0, 1}.
n
o


C := c = ca |cb |cz = a|a + b|a + αb + z
a ∈ Ca , b ∈ Cb , z ∈ Cz .
(1)
Theorem 1. The parameters of the code C are
n0 = 3n
k0 = ka + kb + kz
d0 = min{3da , 2db , dz }.
Proof. The length and dimension are obvious.
 minimum distance is proven
 The
later by giving a decoding algorithm up to d−1
2 .
Comparing the dimension of the code in (1) to the one of a GII-RS code
of interleaving degree ν = 3 it follows, that the constructed codes are not
equivalent.
In the following we choose the parameter α to be a multiplicative generator of
the group F∗q .

3

Decoding Algorithm

Definition 1. Let c ∈ C be a transmitted codeword and r = c + e be received.
Then r and e consist of the parts


r = ra |rb |rz , e = ea |eb |ez ,
where ra , rb , rz , ea , eb , ez have length n respectively.
According to the construction of C the sub code Cz is the strongest and Ca
is the weakest sub code. We take advantage of this property by first decoding
in Cz and then trying to decode in the weaker codes using information from the
previous decoding results.

Michael Schelling, Martin Bossert

3.1

3

Algorithm



Let c = a|a + b|a + αb + z be transmitted and r = c + e = ra |rb |rz be
received. Let the the error e have weight τ ≤ b d02−1 c.
1. Decode rz − αrb + (α − 1)ra = z + ez − αeb + (α − 1)ea in Cz .
Let the set of resulting error locations be Eabz .
2. Calculate rb − ra = b + eb − ea .
Erase all positions from Eabz and decode in a accordingly shortened Cb∗ .
Find the corresponding codeword in Cb .
3. Calculate rb − b = a + eb and rz − αb − z = a + ez .
Decode a+ea , a+eb , a+ez in Ca and receive up to three different solutions
a(i) , i = 1, 2, 3.
(i)

(i)

(i)

4. Calculate the errors ea = ra −a(i) , eb = rb −b−a(i) , ez = rz −αb−z−a(i)
for all i and choose the a(i) with
n
o
(i)
(i)
|
+
|e
|
+
|e
|
τmin = min |e(i)
a
z
b
i

as decoding result.

3.2

Correctness of the Algorithm

Proof. The number of errors τ fulfills


dz − 1
τ≤
2


2db − 1
τ≤
= db − 1
2


3da − 1
.
τ≤
2

(2)
(3)
(4)

∗ is bounded
1. The decoding in Cz is successful as the number of errors in Eabz
from above by τ . As overlapping error positions are possible the number
of errors is possibly less then τ .
∗ |, k , d∗ = d −|E ∗ |)
2. The shortened code Cb∗ has parameters (n∗b = n−|Eabz
b b
b
abz
and has to decode all errors that canceled out in the first step. Let Iabz
be the set of these errors. For each such erasures of errors at least two
errors are necessary, and thus
∗
|Eabz
| + 2 · |Iabz | ≤ τ.

4

OC2017
Together with (3) the decoding of b is successful due to
|Iabz | ≤

∗ |
∗ |
db − 1 − |Eabz
d∗ − 1
τ − |Eabz
≤
= b
.
2
2
2

3. According to (4) it holds that
n
o d − 1
a
min |ea |, |eb |, |ez | <
.
2


W.l.o.g. assume |ea | < da2−1 . Then the decoding of a + ea in Ca is
successful and a(1) = a. Assume there is an i with a(i) 6= a(1) and
(i)

(1)

(i)
(1)
(1)
|e(i)
a | + |eb | + |ez | ≤ |ea | + |eb | + |ez |.

Then the codewords
c(1) = a(1) |a(1) |a(1)



and c(i) = a(i) |a(i) |a(i)



are two codewords of a concatenated repetition code with distance
(i)

(1)

(i)
(1)
(1)
d(c(1) , c(i) ) ≤ |e(i)
a | + |eb | + |ez | + |ea | + |eb | + |ez |


(4)
3da − 1
< 3da .
≤ 2τ < 2 ·
2

This is a contradiction to the minimum distance dm in = 3da of the concatenated code. Thus the decoding of a is successful due to
n
o
(i)
1 = argmin |ea(i) | + |eb | + |e(i)
z | .
i

Note that the number of errors considered in the first step is possibly smaller
than the total number of errors τ due to overlapping error positions. As a result
the stated algorithm can decode certain error patterns bevond half the minimum
distance.

4

Simulation

The simulation was done for the parameters in table 1 and compared to a MDS
code with parameters (384, 216, 169).

Michael Schelling, Martin Bossert

5

Table 1: Code Parameters
n
k
d
Ca
128
98
31
Cb
128
82
47
Cz
128
36
93
C
384
216
93

5

Conclusion

We proposed a new construction for codes based on RS codes, which present
a way to construct longer codes over smaller field sizes compared to RS codes.
We limited ourselves to the case of three sub codes, a generalization to longer
constructions seems possible.
The simulation confirms the capability of the presented decoder to decode be-

6

OC2017

yond half the minimum distance . Furthermore the given decoding principles
are straight-forward, can easily be implemented and yield a runtime in the scale
of the underlying RS decoder.

References
[1] Reed,I.S. and Solomon G., ”Polynomial Codes over Certain Finite Fields”
SIAM Journal of Applied Math., vol. 8, 1960, pp. 300-304.
[2] W. W. Peterson, ”Encoding and error-correction procedures for BoseChaudhuri codes”, IRE Transactions on Information Theory, vol. IT-60,
pp. 459-470, 1960.
[3] Berlekamp, Elwyn , ”Nonbinary BCH decoding” IEEE transactions on
information theory, vol 14, 1968.
[4] Y. Sugiyama, M. Kasahara, S. Hirasawa, and T. Namekawa, ”A method
for solvin key equation for decoding Goppa codes”, Inf. Contr., vol. 27,
1975, pp. 87–99.
[5] Y. Wu, ”New list decoding algorithms for Reed–Solomon and BCH codes”,
IEEE Transactions on Information Theory, vol. 54, no. 8, 2008, pp. 3611–
3630.
[6] Y. Wu, ”Generalized Integrated Interleaved Codes”, IEEE Transactions
on Information Theory, 2017
[7] M. Plotkin. ”Binary codes with specified minimum distances,” IEEE
Transactions on Information Theory, vol. 6, pp. 445-450, 1960.

