A Low Complexity Algorithm and Architecture for Systematic Encoding of
  Hermitian Codes
A Low Complexity Algorithm and Architecture for
Systematic Encoding of Hermitian Codes
Rachit Agarwal∗†, Ralf Koetter‡ and Emanuel M. Popovici∗§
∗ Department of Microelectronic Engineering, University College Cork, Cork, Ireland
† Microelectronics Application Integration Group, Tyndall National Institute, Cork, Ireland
‡ Institute for Communications Engineering, Technische Universitaet, Muenchen, Germany
§ Claude Shannon Institute for Discrete Mathematics, Coding and Cryptography, Ireland
Email: rachit.agarwal@ue.ucc.ie, ralf.koetter@tum.de, e.popovici@ucc.ie
Abstract— We present an algorithm for systematic encoding of
Hermitian codes. For a Hermitian code defined over GF (q2), the
proposed algorithm achieves a run time complexity of O(q2) and
is suitable for VLSI implementation. The encoder architecture
uses as main blocks q varying-rate Reed-Solomon encoders and
achieves a space complexity of O(q2) in terms of finite field
multipliers and memory elements.
I. INTRODUCTION
Algebraic-Geometric (AG) codes [1] offer desirable prop-
erties such as large code lengths over small finite fields, the
potential to find a large selection of codes and good error-
correction at high code rates [2]. In recent years, an important
class of one-point AG codes, called Hermitian codes, has been
frequently discussed [3]-[6].
For a Hermitian code defined over GF (q2), a brute-force
way to design an encoder is to multiply the information vector
by a generator matrix. The space complexity of a serial-in
serial-out architecture for this systematic encoder is O(q5) in
terms of finite field multipliers and O(q3) in terms of memory
elements. The encoder requires 2n clock cycles to generate a
codeword of length n, thus, the latency is n.
By considering a Hermitian code as a superposition of
several generalized Reed Solomon (RS) codes, an encoding
scheme is introduced in [4]. In [5], an encoding algorithm by
forming a bivariate information polynomial and evaluating this
polynomial at every finite rational point on the Hermitian curve
is proposed. However, both such schemes are nonsystematic
and involve the evaluation of bivariate polynomials at n finite
rational points, thus, they may not have efficient hardware
architecture for implementations.
A computationally efficient approach for systematic encod-
ing was proposed in [7]. A serial-in serial-out architecture for
this approach was proposed in [8]. This architecture requires
n clock cycles to encode a codeword of length n. The space
complexity for this architecture is O(q3), both in terms of
finite field multipliers and memory elements.
In this paper, we present an algorithm for systematic encod-
ing and syndrome computation of Hermitian codes. We give an
outline for the encoder architecture, which uses q varying-rate
RS encoders as main blocks and requires n2/3 clock cycles
for encoding a codeword of length n. The space complexity of
the architecture is O(q2) in terms of both, memory elements
and finite field multipliers.
II. HERMITIAN CODES AND SYNDROME COMPUTATION
We consider codes from a Hermitian curve
χ : xq+1 = yq + y
over a finite field Fq2 . The space L(mP∞) consists of all
functions on χ that have a pole of multiplicity at most m only
at the unique point at infinity. For L(mP∞), we choose a basis
L(mP∞) = 〈xayb : aq + b(q + 1) ≤ m, 0 ≤ a, 0 ≤ b < q〉
Let y0 be an element of Fq2 such that y0 + y0q = 1. The
affine rational points on χ are of the form
Pα,β = (α, α
q+1(y0 + β) + δ(α)β),
where δ is the Kronecker-delta and α and β represent arbitrary
elements in Fq2 and Fq respectively.
Let � be a primitive element in Fq2 and let γ be a primitive
element in Fq . We label the positions in a codeword by the
corresponding elements α = �i, β = γj and we thus naturally
consider a codeword as a q × q2 matrix c. Occasionally we
will index elements in this array by elements of the fields Fq2
and Fq , otherwise we index starting with 0.
A Hermitian code C(m) is defined as
{c ∈ Fq
cβ,αf(Pα,β) = 0, ∀f ∈ L(mP∞)}
For an in-depth treatment of AG codes we refer to [9].
Throughout this paper we consider m and thus the Hermitian
code as being fixed.
Given a q × q2 matrix r we can check if r is a codematrix
in a Hermitian code by computing the syndromes
Sa,b(r) =
rβ,α(x(Pα,β))
a(y(Pα,β))
r is a code-matrix iff Sa,b(r) is zero for all xayb ∈ L(mP∞).
Substituting the explicit form of the points we get
Sa,b(r) =
αa(α(q+1)(y0 + β) + δ(α)β)
brβ,α
These equations can further be developed to give specific
forms as shown in (1) and (2). From the structure of (2), it
comes naturally to define a matrix as in (3) to convert the
expression into a matrix multiplication. Similarly we define a
matrix A′ as

1 (γ0)0 (γ1)0 . . . (γq−2)0
0 (γ0)1 (γ1)1 . . . (γq−2)1
0 (γ0)2 (γ1)2 . . . (γq−2)2
. . .
0 (γ0)q−1 (γ1)q−1 . . . (γq−2)q−1

For later use we give here the following Lemma.
A. Lemma 1
The l×l submatrices of A consisting of the elements indexed
by i, j and that of A′ consisting of the elements indexed by
j, i, i = q − l, q − l + 1, . . . , q − 1, j = 0, 1, . . . , l − 1 are
non-singular.
Proof: This lemma follows in both cases from the properties
of Vandermonde matrices.
It will be convenient to define an array A of matrices of
type A and A′.
A = (A0, A1, . . . , Aq2−1), Ai =
A′ i = q2-1
A otherwise
Given a q× q2 array r with columns rj , we define a q× q2
matrix r̃ with columns r̃j as
r̃j = Ajrj
One of the main ingredients in both the syndrome calcu-
lation and a systematic encoding is the use of techniques for
cyclic codes which are extended by one extra position. Let
â(b) = b(m − (q − 1 − b)(q + 1))/qc = max(a : xayb ∈
L(mP∞)).
B. Definition 1
Let an ordered set < = {ξ0, ξ1, . . . } of elements from Fq
be given. We define the code EC(<, q) as
{c ∈ Fqq :
i = 0, ∀ξ ∈ <\{ξ0}, cq−1 +
i = 0}
For the natural indexing of elements in Fq and Fq2 induced
by γ and � we have the following Lemma.
C. Lemma 2
Let a q × q2 matrix r be given. The matrix r is a code
matrix in the Hermitian code C(m) iff the ith row of r̃ is a
codeword in EC((�0+i(q+1), �1+i(q+1), . . . , �â(i)+i(q+1)), q2).
Proof: The proof follows immediately from the syn-
drome definition.
Codes of type EC((�i(q+1), �1+i(q+1), . . . , �â(i)+i(q+1)), q2)
will play a central roll in the sequel. We define codes Ei as
Ei = EC((�
0+i(q+1), �1+i(q+1), . . . , �â(i)+i(q+1)), q2)
From Lemma 2 we can derive an efficient way to compute
the syndrome for a Hermitian code. Given a received matrix
r we obtain a matrix r̃ with columns r̃j = Ajrj .
Given r̃ we can easily solve the task of computing syn-
dromes provided we can compute the corresponding syn-
dromes for codes Ei, i = 0, 1, . . . , q − 1.
III. SYSTEMATIC ENCODING
The idea behind the systematic encoding of Hermitian
codes is to use the well known techniques for the systematic
encoding of cyclic codes. Lemma 2 almost immediately gives
a nonsystematic encoding procedure for Hermitian codes. To
this end let r̃ be a q×q2 matrix such that the jth row of r̃ is a
codeword in Ej . It follows from Lemma 2 that we can obtain a
code-matrix for a Hermitian code by multiplying the columns
of r̃ with matrices A−1 and A′−1 respectively. We can obtain
such a matrix r̃ using eg. systematic encoding procedures for
codes of type Ej , j = 0, . . . , q − 1.
We will need A−1 and A′−1.
A. Lemma 3
The matrices A and A′ have inverses given in (4) and (5).
Proof: The inverse of A′ is straight forward to verify. We
only show the inverse of A. The rows of A−1 and the columns
of A may be thought of as being indexed by elements of Fq .
Sa,b(r) =
q2\{0}
β∈Fq α
aαb(q+1)(y0 + β)
brβ,α a 6= 0∑
β∈Fq (α
b(q+1)(y0 + β)b + δ(α)βb)rβ,α a = 0
Sa,b(r) =
{ ∑q2−2
i=0 �
i(a+b(q+1))(yb0r0,i +
j=0 (y0 + γ
rj+1,i) a 6= 0∑q2−2
i=0 �
ib(q+1)(yb0r0,i +
j=0 (y0 + γ
rj+1,i) +
j=0 γ
jbrj+1,q2−1 a = 0

(y0 + 0)0 (y0 + γ0)0 (y0 + γ1)0 . . . (y0 + γq−2)0
(y0 + 0)1 (y0 + γ0)1 (y0 + γ1)1 . . . (y0 + γq−2)1
(y0 + 0)2 (y0 + γ0)2 (y0 + γ1)2 . . . (y0 + γq−2)2
. . .
(y0 + 0)q−1 (y0 + γ0)q−1 (y0 + γ1)q−1 . . . (y0 + γq−2)q−1
 (3)
A−1 =

1− (y0 + 0)q−1 (y0 + 0)q−2 . . . (y0 + 0)0
1− (y0 + 1)q−1 (y0 + 1)q−2 . . . (y0 + 1)0
1− (y0 + γ)q−1 (y0 + γ)q−2 . . . (y0 + γ)0
. . .
1− (y0 + γq−2)q−1 (y0 + γq−2)q−2 . . . (y0 + γq−2)0
 (4)
A′−1 =

1 0 0 . . . 0 −1
0 −(1)q−2 −(1)q−3 . . . −(1)1 −1
0 −(γ)q−2 −(γ)q−3 . . . −(γ)1 −1
. . .
0 −(γq−2)q−2 −(γq−2)q−3 . . . −(γq−2)1 −1
 (5)
Let C be the matrix obtained as C = A−1A. The entry Ci,j
is thought of as being indexed by µ, ν ∈ Fq .
Cµ,ν = (1− (y0 + µ)q−1(y0 + ν)0 − (y0 + µ)q−2(y0 + ν)1
· · · − (y0 + µ)0(y0 + ν)q−1)
i=0 (y0 + µ)
q−1−i(y0 + ν)i
(y0 + µ)q − (y0 + ν)q
y0 + µ− (y0 + ν)
1− (µ− ν)q−1 =
1 µ = ν
0 µ 6= ν
We note that we are entirely free to choose ”virtual information
symbols” in matrix r̃. Let a sequence of information symbols
be given that are to be encoded systematically in a codeword of
a Hermitian code. The trick in obtaining a systematic encoding
procedure is to choose the information symbols in r̃ so that the
mapping with A−1 and A′−1 respectively, gives the primary
information symbols that we really want to encode.
Before we derive a systematic encoding procedure for
Hermitian codes, we treat a somewhat simpler case, which
will elucidate the idea of systematic encoding. Let Ĉ be a
code on a Hermitian curve defined as
Ĉ = {c ∈ Fq
: Sa,b(c) = 0,
a = 0, 1, . . . , â < q2 − 1, b = 0, 1, . . . , q − 1}
The code Ĉ has dimension (q2 − â − 1)q. The following
algorithm may be used for systematic encoding of code Ĉ.
B. Algorithm 1
1) Write the (q2− â−1)q information symbols in an array
d of size q × (q2 − â− 1)
2) Compute r̂ = AdT
3) Encode the ith row of r̂ independently in a systematic
way into codewords of the code
EC((�0+i(q+1), �1+i(q+1), . . . , �â(i)+i(q+1)), q2)
Denote the resulting q × q2 matrix with r̂′.
4) Compute columns ci = A
Algorithm 1 yields a systematic encoding procedure for the
code Ĉ because c is a code matrix by Lemma 2 and the first
(q2− â−1)×q symbols are the original information symbols.
The first (q2 − â− 1) columns of d determine the first (q2 −
â− 1) columns of r̂. It is the first (q2 − â− 1) columns of r̂
that contain the virtual information symbols for the encoding
of the cyclic codes.
The situation for Hermitian codes is complicated by the fact
that the codes Ei have different rates. Thus at some instance
of the algorithm we have to process the columns that are in
one part determined by information symbols and the other
part is determined by redundancy symbols generated by the
systematic encoders of the codes Ei. For simplicity, we will
restrict our attention to codes C(m) of dimension k that is
less than (q3 − g − q).
Let φi : F
q2−â(i)−1
−→ Fq
be a systematic encoder for
a code Ei. The input sequence to the encoder φi are symbols
from an array r̃ = r̃i,j for j = 0, 1, . . . , q2 − â(i)− 2.
We want to construct an algorithm that takes as input an
array d of size q × q2 with arbitrarily chosen symbols in po-
sitions (a, b) : b = 0, 1, . . . , q − 1; a = 0, 1, . . . , q2 − â(b)− 2
and zero in the remaining positions and that produces as
output a code-array c. Let b̂(j) be defined as the number of
information symbols in the jth column of d. The columns of d
thus have the form dj = (d0,j ,d1,j , . . . ,db̂(j)−1, 0, 0, . . . , 0).
We give a systematic encoder procedure in the following
algorithm. During the procedure we also construct an array r̃.
The ith row of r̃ is a codeword in Ei. Thus the first q2 −
â(i) − 1 positions in the ith row of r̃ determine the ith row
of r̃ completely.
C. Algorithm 2
The algorithm is shown in (6).
Theorem 1: Algorithm 2 computes a code array c of the
Hermitian code C = (evD(mP∞))⊥.
Proof: The matrix r̃ in the algorithm satisfies the
conditions r̃j = Aj cj and the i-th row of r̃ is a codeword
in Ei. Thus c is a code-array by Lemma 2.
Algorithm 2 outlines the mathematical procedure to achieve
systematic encoding of a Hermitian code. The real difficulty
Algorithm 2 (6)
Input: An q × q2 array d. An empty q × q2 array r̃.
Iterations: For j = 0, 1, . . . , q2 − 1
1) Compute the known part of r̃j for i = 0, 1, . . . , q − 1− b̂(j) as
r̃i,j = (φi((r̃i,0, r̃i,1, . . . , r̃i,q2−â(i)−2)))j
2) Solve the equation
Aj(d0,j ,d1,j , . . . ,db̂(j)−1,j , yb̂(j),j , yb̂(j)+1,j , . . . , yq−1,j)
T = (r̃0,j , r̃1,j , . . . , r̃q−1−b̂(j),j , uq−b̂(j),j , uq−b̂(j)−1,j , . . . , uq−1)
for y
b̂(j),j
b̂(j)+1,j
, . . . , yq−1,j , uq−b̂(j),j , uq−b̂(j)−1,j , . . . , uq−1
3) Set
ci = (d0,j ,d1,j , . . . ,db̂(j)−1,j , yb̂(j),j , yb̂(j)+1,j , . . . , yq−1,j)
r̃i = (r̃0,j , r̃1,j , . . . , r̃q−1−b̂(j),j , uq−b̂(j),j , uq−b̂(j)−1,j , . . . , uq−1)
lies in an efficient implementation of the algorithm. We give
such an implementation in Section IV but before proceeding
we will need a simple lemma.
Let A be any n × n matrix with inverse A−1. We
assume that the submatrix of A indexed by elements
i, j, i = n − l, . . . , n − 1 and j = 0, 1, . . . , l − 1 is
nonsingular. This will always be true for the cases that we
are interested in by Lemma 1. Let Il denote the l × l matrix
and let D(l) be a n× n matrix of the following form:
D(l) =
such that
A−1D =
for a l × l matrix P̃ . We note that D(l)T is just a systematic
encoding matrix for a code which has a parity check matrix
the first l rows of A−1.
D. Lemma 5
Let x0, x1, . . . , xn−l−1 and v0, v1, . . . , vl−1 be given. The
solution for yn−l, yn−l+1, . . . , yn−1 and ul, ul+1, . . . , un−1 to
the linear system of equations
A(x0, x1, . . . , xn−l−1, yn−l, yn−l+1, . . . , yn−1)T =
(v0, v1, . . . , vl−1, ul, ul+1, . . . , un−1)T
can be found with the following algorithm.
E. Algorithm 3
Algorithm 3 is given as shown in (7).
Proof: A−1b̃T = A−1Db̂T which proves that
y0, y1, . . . , yn−l−1 equal zero.
Now it follows that
A(x0, x1, . . . , xn−l−1, yn−l, yn−l+1, . . . , yn−1)T
= b̃T + bT
= A(A−1Db̂T ) + bT
= Db̂T + bT
= D(v0, v1, . . . , vl−1, 0, 0, . . . , 0)T
−D(b0, b1, . . . , bl−1, 0, 0, . . . , 0)T + bT
= (v0, v1, . . . , vl−1, ul, ul+1, . . . , un−1)T
IV. EFFICIENT IMPLEMENTATION OF A SYSTEMATIC
ENCODER
Inspecting Algorithm 2 and Lemma 4, we see that we need
modules for multiplication of an array with matrix A, A−1,
systematic encoding of codes Ej , and a systematic encoding
module for codes Dl defined as
Dl = {d ∈ F
A−1i,j dj = 0, i = 0, 1, . . . , l − 1}
Before describing the modules in detail we give a black box
description and the overall description of the implementation.
A. Module A: Multiplication with Matrix A,A′
The module has as parallel input a vector d of length
q and produces as serial output the numbers (AdT )i, i =
0, 1, . . . , q − 1 during the next q clock cycles.
B. Module B: Multiplication with Matrix A−1, A′−1
Module B has as serial input a vector d of length q. After
q clock cycles the parallel output is a vector A−1dT .
C. Module C: Systematic Encoding of Codes Ei
The module has a serial input of q2− â(i)−1 symbols and
produce one symbol per clock cycle. The clocking frequency
is 1/q of the overall clock rate.
Fig. 1
OVERALL OUTLINE OF THE ENCODER CIRCUIT. SWITCHES a & b ARE SYNCHRONIZED AND ROTATE EVERY CLOCK CYCLE. THE CIRCUIT IS DESCRIBED
IN THE TEXT.
D. Module D: Systematic Encoding of Codes Dl
Module D takes a serial input of length l and produces as
serial output a codeword of length Dl.
E. Encoder
Figure 1 outlines the overall implementation. When the left
hand input becomes valid, the output of Module A is added
to the negative output of Module C, effectively implementing
steps 1 and 2 of Algorithm 3. The sum is fed to Module
D which implements step 3 of Algorithm 3. The output of
Module D is combined with the output of Module A to
implement step 4 of Algorithm 3. Simultaneously it is fed
to module B of the implementation. After q clock cycles the
output of Module B is added to the input thus implementing
step 5 of Algorithm 3.
Module C can be implemented as an obvious modification
of a systematic encoding circuits for RS codes [10].
Module D implements systematic encoding of a code with
parity check matrix given by first l rows of matrix A−1. From
the form of matrices A−1, we see that code Dl may be defined
Dl = {d ∈ F
j=0 dq−1−j(xi)
j = d0, x0 = y0,
xs+1 = (y0 + γs), s = 0, 1, . . . , l − 2}
and we can use standard encoding techniques for shortened
cyclic codes which are modified in the obvious way.
V. FINAL REMARKS
A low complexity algorithm for systematic encoding and
syndrome computation of Hermitian codes has been presented.
The algorithm has a run time complexity of O(n2/3) and is
suitable for VLSI implementation. We give an outline for the
encoder architecture, which uses as main blocks, q varying-
rate Reed Solomon encoders. The architecture achieves a much
lower space complexity in terms of finite field multipliers and
memory elements when compared to earlier reported works.
VI. ACKNOWLEDGEMENT
The authors would like to thank Science Foundation Ireland,
Claude Shannon Institute and Deutsche Forschungsgemein-
schaf for supporting parts of this research work.
REFERENCES
[1] V. D. Goppa, Codes on Algebraic Curves, Soviet math. Dokl., 1981, 24,
pp. 75-91
[2] B. E. Wahlen, and J. Jimenez, Performance Comparison of Hermitian and
Reed-Solomon Codes, Proc. MILCOM, 1997.
[3] J. H. van Lint and T. A. Springer, Generalized Reed-Solomon Codes
from Algebraic Geometry, IEEE Trans. Inform. Theory, vol. IT-33, pp.
305-309, May 1987
[4] T. Yaghoobian and I. F. Blake, Hermitian Codes as Generalized Reed-
Solomon Codes, Design, Codes, Cryptography, vol. 2, pp. 5-17, 1992
[5] B. Z. Shen, On Encoding and Decoding of the codes from Hermitian
Curves, Proc., Cryptography and Coding III, vol. 45, M. Ganley, Ed.,
Oxford, UK, pp. 337-356, 1993
[6] J. Little, K. Saints and C. Heegard, On the structure of Hermitian Codes,
Journal of Pure and Applied Algebra, vol. 121, pp. 293-314, 1997
Algorithm 3 (7)
1) bT = A(x0, x1, . . . , xn−l−1, 0, 0, . . . , 0)T
2) b̂T = (v0, v1, . . . , vl−1, 0, 0, . . . , 0)T − (b0, b1, . . . , bl−1, 0, 0, . . . , 0)T
3) b̃T = Db̂T
4) (x0, x1, . . . , xn−l−1, yn−l, yn−l+1, . . . , yn−1)T = (x0, x1, . . . , xn−l−1, 0, 0, . . . , 0)T +A−1b̃
5) (v0, v1, . . . , vl−1, ul, ul+1, . . . , un−1)T = b̃T + bT
[7] C. Heegard, J. Little and K. Saints, “Systematic Encoding via Gröbner
bases for a class of Algebraic-Geometric Codes,” IEEE Trans. Info.
Theory, vol. IT-41, pp. 1752-1762, Nov. 1995
[8] J. Chen and C. Lu, ”A Serial-In-Serial-Out Hardware Architecture for
Systematic Encoding of Hermitian Codes via Gröbner Bases”, IEEE
Trans. Info. Theory, Vol. 52, No. 8, pp. 1322-1332, August 2004
[9] H. Stichtenoth, Algebraic Function Fields and Codes, Springer-Verlag,
Berlin, Germany 1993.
[10] G. Fettewis and M. Hassner, “A Combined Reed-Solomon Encoder and
Syndrome Generator with Small Hardware Complexity” Proc. Int. Symp.
Circuits and Systems, pp. 1871-1874, 1992.
	Introduction
	Hermitian Codes and Syndrome Computation
	Lemma 1
	Definition 1
	Lemma 2
	Systematic Encoding
	Lemma 3
	Algorithm 1
	Algorithm 2
	Lemma 5
	Algorithm 3
	Efficient Implementation of a Systematic Encoder
	Module A: Multiplication with Matrix A, A'
	Module B: Multiplication with Matrix A-1, A'-1
	Module C: Systematic Encoding of Codes Ei
	Module D: Systematic Encoding of Codes Dl
	Encoder
	Final Remarks
	Acknowledgement
	References
