Hardware-Efficient Reed-Solomon Encoding Using

Parallel LFSR and Boolean Logic GF Multipliers

or
Implementation of a Synthesizable Reed-Solomon
Encoder Using Logic-Optimized GF(2⁸)
Multiplication
​ Gaurav Bhole​ Aditya Bhosale​
Ashwinee Barbadekar​ Department of Electronics and Department of Electronics and
Department of Electronics and Telecommunication Engineering ​ Telecommunication Engineering​
Telecommunication Engineering ​ Vishwakarma Institute of Technology​ Vishwakarma Institute of Technology​
Vishwakarma Institute of Technology​ Pune, India​ Pune, India​
Pune, India​ Email: gaurav.bhole21@vit.edu Email: aditya.bhosale21@vit.edu
Email: ashwini.barbadekar@vit.edu

Abstract— This paper presents the design, I.​ INTRODUCTION

implementation, and comparative analysis of a
Reed-Solomon (RS) encoder targeting the (255, 239) Since the appearance of the first television, the public has
configuration over GF(2⁸), implemented on an Intel been demanding for higher resolutions and more
MAX V FPGA using Quartus Prime. The RS encoder functionality. It was not long after that the people realized
architecture utilizes the primitive polynomial 𝑝(𝑥) = 𝑥⁸ + that the capabilities of the televisions of the time were not
𝑥⁴ + 𝑥³ + 𝑥 + 1 and incorporates 16 roots for its generator good enough to cover their needs. Simply using a television
polynomial. A serial Linear Feedback Shift Register as an endpoint to display a broadcast media, like a radio,
(LFSR)-based algorithm was employed for parity was not keeping up with the demands. From this,
generation and redundancy computation. Two encoder communication technologies flourished.
designs were developed: a baseline (non-optimized)
version and an optimized version incorporating The public was using third party hardware alongside the
architectural enhancements such as clock-enabled television to play games, access extra channels and later on
flip-flops, asynchronous resets, and reduced to access the internet. Televisions went from simply
combinational logic depth. Post-synthesis analysis displaying monochro- matic images to providing sound and
reveals that the optimized encoder results in significant reproducing vivid and colourful three-dimensional scenes.
resource and power reductions: logic elements are
reduced by 83.2% (from 901 to 151), 4-input LUTs So as to allow for those luxuries the interconnections
decrease by 85.9% (from 799 to 113), and 3-input LUTs between devices had to be carefully engineered, which
are reduced by 78.5% (from 93 to 20). Additionally, the ended up making most interface technologies, mainly
total fan-out is lowered by 72.7% (from 3,877 to 1,058). multimedia ones, converge to an increase of the required
In terms of power consumption, total thermal power bandwidth. This necessity for more bandwidth is easily
drops by 39.7% (from 6.30 mW to 3.80 mW), with I/O justifiable by the need for higher resolutions and faster
thermal power decreasing by 77.7% (from 3.23 mW to display panels, among other factors. For example the HDMI
0.72 mW). These findings underscore the substantial version 2.0b can sustain resolutions up to 3840x2160 (Ultra
impact of algorithmic and architectural optimizations on HD) more commonly known as 4K, and the latest monitors
enhancing the area and power efficiency of FPGA-based can handle up to 144 Hz refresh rates.
Reed-Solomon encoders.
In order to keep up with the market needs, multimedia
Keywords— Reed-Solomon Encoding, Verilog, Error interfaces have to find ways so that the overall
Correction, Data Transmission. communication capacity is improved, like the use of
compression methods, among others. Compression, as the
name indicates, allows for a given message to have the in the previous examples, and there are two main classes.
same, or almost the same, information but in a smaller One is called "prime fields" if m = 1 , and "extended fields"
package. For example, a video may be represented as a otherwise.
series of discrete sequential images, or frames. One way to
compress it is to use only one image and infer the In the prime fields, most of the operations are fairly simple.
subsequent frames, from this first image. That means if an Assuming:
error occurs in the first image, every subsequent frame will
appear with errors, until a new full image is displayed. ​ ​ ​ a, b, c, d, e ∈ GF(p)​ (1.1)

Such methods when used in noisy channels, such as wireless Addition, subtraction and multiplications are computed as if
communications or poorly designed cables, generate small they were normal numbers, however for finite fields, the
errors in the data transmission, which may cause great division’s remainder by p is taken:
impact in the user experience. In order to prevent this,
systems like Reed Solomon with Forward Error Correction ​ ​ ​ a + b ≡ c mod p[1]​ (1.2)
are imple-mented. Error Correction Codes like this add
​ ​ ​ a − b ≡ d mod p[1]​ (1.3)
redundant data during transmission, which is then used to
detect and, if possible, correct errors that may have occurred ​ ​ ​ a · b ≡ e mod p[1] ​ (1.4)
during transmission.
Inversion, at the other hand is a bit more complicated since,
Reed-Solomon has been used for decades, however, every by definition:
design is different and there may be systems where existing
designs might not be fully compatible or may not comply a−1 · a ≡ 1 mod p[1] (1.5)
with the design restrictions.
Finding a-1 is not as trivial as the other operations, however,
Ever since the beginning of communications systems, noise there are iterative methods that calculate it, like the
and interference have been great obstacles in the pursuit of Euclidean algorithm. If the field is not very large, a brute
the theoretical limit for a channel capacity, that is the force search, or a lookup table are also valid alternatives.
theoretical limit for how much information can flow in a
given channel. Forward Error Correcting codes have played When m > 1, in the extended fields, things get a bit more
a great role in this mission. By adding redundant data complicated. They can not be simply represented as
alongside the information data, it is possible to recover numbers like the prime fields. The arithmetic rules stated
some errors that may have occurred during data transfer. For earlier no longer apply. However by representing the Galois
further efficiency mathematical tools are used, like the Field elements as polynomials instead of simple numbers,
Galois Fields, which represent the symbol space used in some operations are still kept fairly simple.
Reed-Solomon. This paper will cover an overview of Linear
Block Codes, where Reed- Solomon are inserted, as well as For example, considering the GF(22), which was stated
Galois Fields arithmetic deductions and Reed-Solomon before that a set of elements could be {0, 1, 2, 3}, taking the
encoding generalizations. polynomial representation, the set becomes {0, 1, x, x + 1},
which may be simplified by looking at the polynomials
coefficients as an array, {[0 0], [0 1], [1 0], [1 1]}, which
directly maps elements to the binary representation of the
Fields, Rings and Groups represent sets of numbers original number representation showed first. This means
alongside operations whose results are always present in the that the Galois Fields can always be represented as a set of
same set. A Group has only two valid operations: addition number, however, the operations must take in consideration
and subtraction. A Ring is always a Group but also supports that they are actually polynomials. [1] Assuming:
other operations such as multiplication. A Field is the more
general presented concept, it integrates the previously ​ ​ A(x), B(x),C(x) ∈ GF(pm)​ (1.6)
mentioned operations as well as inversion. For example, the
set of real numbers (ℜ) forms a Field. On the other hand, the Addition and subtraction are very similar to those of prime
set of natural numbers (ℵ) can only form a Ring, since none fields, however numbers are treated as polynomials, so
if its numbers’ inversions result in a natural number. instead of the result being the remainder of the division by
p, a normal operation must be applied to the polynomials
Galois or Finite Fields (GF), unlike the set of real numbers, and taken the remainder of the division of each coefficient
only have a finite amount of elements in its set and the by p:
number of elements is always a power of a prime. ​
For example, {0, 1, 2, 3, 4} and {0, 1, 2, 3} may form
Galois Fields, since they have a power of a prime num- ber C(x) = A(x) ± B(x) ≡ ∑ ci · xi (1.7)
of elements, 5 and 22 respectively. On the other hand, {0, 1,
2, 3, 4, 5} has six elements which is not a power of a prime. where,
They are represented as :​ ​
​ ci ≡ (ai ± bi) mod p (1.8)
​ ​ ​ GF(pm), GF(5) and GF(22) ​
​
Galois Fields:​ ​ = [1 1 1 1] xor [1 0 0 0]
Multiplication and inversion becomes more complicated, = [0 1 1 1]
because the elements of the extended fields are actually
=7
polynomials and multiplication of two polynomials results
in a poly- nomial whose order is the sum of the The multiplication, on the other hand, is more complex.
multiplicands polynomials’ orders. Which means, that by However, by the definition, it is still possible to arrive at an
considering a GF(pm) which has polynomials of order up to algorithm that makes multiplication easily synthesizable.
m − 1 and by multiplying two poly- nomials of that order, Starting by an example:
the result would be of order 2m − 2, which is not part of the
available set. A polynomial of order m is needed, more 15 · 8 = (x3 + x2 + x + 1)·(x3) mod p(x) (1.17)
specifically a primitive polynomial, p(x). [1] Now the = x6 + x5 + x4 + x3 mod p(x)
Galois multiplication can be defined as:​ = [1 1 1 1 0 0 0] mod [1 0 0 1 1]

A(x)· B(x) ≡ C(x) mod p(x) (1.9) ​ ​ ​ 1111000 10011 (1.18)​

​ ​ ​ 110100 1​
​ ​ ​ 10010 11​
Inversion does not change that much, the only difference is
​ ​ ​ 1 111
that p(x) must used, instead of p:

A−1(x) · A(x) ≡ p(x) (1.10) 15 · 8 = 1 (1.19)

With the introduction of p(x), comes one more form of Here it is noticeable a two-step sequential process.
displaying the elements of the field itself. If there is an However, due to the high throughput required, it is
element of GF(pm), then the Galois Field set may be necessary to execute this multiplication combinationally, or
expressed as: in a pipelined version, which is feasible in three steps.
Assuming:
​ ​ {α∞, α0, α1, α2, . . . , αpm−2} (1.11)
​ ​ ​ A(x), B(x) ∈ GF(24)
where α≠0≠1 and is denoted as the field root. By taking this
representation, multiplication and inversion becomes C(x) ∈ GF(24) (1.20)
doable:
The first step remains the same, but combinationally. By
​
simply doing a generic polynomial multiplication, which
αa · αb = αa+b = αc mod (pm−1) (1.12)
may be described as follows:​
α(−a) mod (pm−1) · αb = αa = 1 mod p(x) (1.13)
C(x) = A(x)· B(x) = ∑ ci · xi (1.21)
where,
c6= a3 · b3
αa, αb, αc ∈ GF(pm) (1.14)

However in this representation, additions and subtractions c5= a3 · b2 + a2 · b3

are not easy, neither is converting between representations
for higher order Galois Fields, since their size increases c4= a3 · b1 + a2 · b2 + a1 · b3
exponentially with m. Using 2 as value for p is generally the
most interesting scenario in digital systems, for obvious c3= a3 · b0 + a2 · b1 + a1 · b2 + a0 · b3
reasons, as it simplifies element representation as well as
some operations. Throughout the remainder of the c2= a2 · b0 + a1 · b1 + a0 · b2
document, p = 2,m = 4, p(x) = x4 + x + 1, will be used as an
example. c1= a1 · b0 + a0 · b1
The equation 1.7 may be simplified, since calculating the
remainder of the division by 2 cor- responds to truncating to c0= a0 · b0
the least significant bit, the Galois addition and subtraction (2.22)
may be simplified to the same equation, but where ci is now
given by: ​
ci ≡ ai xor bi (1.15) This can be simplified into a more generic and compact
version:
From the above it is inferable that, in fact, the addition and ci+ jai · bj
the subtraction are actually the same operation and, by i = 0, 1, . . . , m − 1,
representing the number in polynomial form, the addition is j = 0, 1, . . . , m − 1​ (1.23)
simply an exclusive-or. For example, take the elements
15(x^3 + x^2 + x + 1) and 8(x^3):​ The second step is a bit more complicated to implement in a
single step, therefore it has been split into two, where first
an auxiliary polynomial (D(x)) is calculated. Considering
15 + 8 = (x3 + x2 + x + 1) + (x3) (1.16)
the primitive polynomial to be:
Block Codes
p(x) = xm + ∑ pi · xi (1.24)
Linear Block codes represent a great class of forward error
The following table is formed from both the primitive
correcting codes where the transmitted word data, generally
polynomial p(x) and the previously calculated C(x), this was
denoted as being composed as N symbols, where each
obtained from a generalization of the long division and
symbol is a set of M bits, is segmented in two blocks,
actually corresponds to most of it.
information and redundancy, that is, the information data,
set of K symbols is kept intact and the redundancy is added
afterwards, as described in figure 1.1.
Several Examples of block codes include Hamming Codes,
BCH Codes and Reed-Solomon Codes.
c6 c5 c4 c3 c2 c1 c0

d3·p3 d3·p2 d3·p1 d3·p0

d2·p3 d2·p2 d2·p1 d2·p0

d1·p3 d1·p2 d1·p1 d1·p0

d0·p3 d0·p2 d0·p1 d0·p0

​
(1.25) ​ Fig 1.1: Block Code

where each coefficient of d(x) is the sum of the column Reed-Solomon

before the one it is first used: The Reed Solomon codes differentiate themselves from the
remaining BCH codes by the number of bits present in their
symbols and the relationship between the symbol width and
d3 = 0 (1.26)
the length of the encoded message. For example, if the
d2 = c6 + d3 · p3 symbols are composed of 8 bits, then the message must be
d1 = c5 + d3 · p2 + d2 · p3 255, that is, N = 2M − 1. However there are versions of
d0 = c4 + d3 · p1 + d2 · p2 + d1 · p3 Reed Solomon that do not follow this rule. Shortened
versions of Reed Solomon append symbols either at the
This can be simplified into a more generic version: beginning or at the end of the information message, which is
then encoded as a normal code, but these added symbols are
di = ci+m + ∑ d j · pm+i− j ​ (1.27) removed before transmission. During the decoding process
they are appended to the received message in order to
i = m − 1, . . . , 1, 0 normalize the decoding procedure.

After arriving to this polynomial, the final result, E(x), is In Reed Solomon, the redundancy symbols are created with
achieved with a similar equation: the resource of a generator poly- nomial of order 2T , where
T = [(N − K)/2♩, is the number of correctable symbols. If the
ei = ci + ∑ d j · pi− j (1.28)​ error count in the received message is larger than T , the
information can no longer be retrieved without errors. This
i = 0, 1, . . . , m − 1 generator polynomial, commonly denoted as g(x) has the
particularity of having all of its roots as consecutive
where, elements of the Galois Field in the exponential form:
E(x) = ∑ ei · xi (1.29)
g(x) = (x + αb) · (x + αb+1) · . . . · (x + αb+2T−1)
and, ​ ​ ​ ​ ​
​ ​ ​ ​ ​ (1.31)
E(x) ∈ GF(2m) (1.30) where α is the Galois Field root.
The Galois Inversion of a number a is not easily achieved,
by definition, a · a-1 = 1, one can simply multiply every II.​ LITERATURE REVIEW
single possible number by a and try to find one that results
in 1. This may be implemented either sequentially or ​ ​ Yun Chen et al. designed a multi-mode
combinationally, however, since the system requires very Reed-Solomon (RS) decoder with a folding architecture to
high throughput, a sequential implementation and a minimize cost and power consumption. Implemented in
combinational one is very area inefficient, a lookup table is 0.13μm CMOS, the decoder supports multiple RS code rates
more suitable, on the other hand, even this becomes with a gate count of 65K and operates at 440MHz. By
unreasonable for very large Galois Fields. shutting down unused hardware in different modes, power
consumption is reduced to 0.25mW per error byte. The processor with an embedded FPGA (eFPGA) to accelerate
design is particularly suited for China Mobile Multimedia encoding. Compared to purely software or hardware
Broadcasting (CMMB) applications. The architecture implementations, this hybrid approach achieves a 4×
achieves high efficiency while maintaining error correction speedup over hardware accelerators and a 412×
capability up to 32 bytes, making it a cost-effective solution improvement over software-only solutions. The SoC
for error correction in wireless communication systems.[1] features a scalable eFPGA with up to 4K LUTs, allowing
dynamic reconfiguration. The paper demonstrates the
efficiency of eFPGA-based RS encoding in communication
​ ​ The paper titled "An Encoder to Match and storage systems, providing a balance between
Reed–Solomon Codes Over GF(q) to a Sub Alphabet of flexibility, performance, and power consumption.[5]
GF(q)​" by Claude Le Dantec and Philippe Piret,explores
encoding techniques that ensure Reed-Solomon (RS) ​ ​ Changgeun Kim et al. proposed a (255,231)
codewords belong to a specific sub alphabet of GF(q). It product Reed-Solomon (RS) code for improving error
presents systematic and partially systematic encoders that correction in NAND flash memory controllers. The design
enable encoding within constrained symbol sets. The work combines row-wise and column-wise RS encoding to handle
is motivated by scenarios where RS decoders operate over both burst and random errors more effectively than
restricted alphabets, such as in error-correcting codes for traditional RS codes. Implemented on an Altera Stratix-II
certain digital storage or communication systems. The FPGA, the design achieves a bandwidth of 1.07Gbps at
authors provide a shift-register-based encoder design, 290MHz while consuming 26.4mW of power. The proposed
reducing memory requirements compared to product code enhances error resilience, making it a viable
generator-matrix-based solutions. This work extends solution for high-density, low-cost NAND flash memory
previous research by optimizing encoding strategies for sub systems that require robust error correction to mitigate
alphabet subcodes, making RS encoding feasible in systems retention errors and charge leakage.[6]
with alphabet constraints.[2]
​ ​ The paper proposed by Haitao Xia and J. R. Cruz
explores soft-decision Reed-Solomon (RS) decoding for
​ ​ Bhawna Tiwari and Rajesh Mehra presented a magnetic storage applications. It introduces a modified
paper titled "Design and Implementation of Reed Solomon belief propagation (BP) algorithm that leverages reliability
Decoder for 802.16 Network using FPGA​" that discusses information from partial-response equalized magnetic
the FPGA implementation of a reconfigurable RS decoder recording channels. By incorporating adaptive BP (ABP),
for WiMAX (802.16) networks. The RS(255,239) decoder is the proposed method improves error correction beyond
developed using VHDL and incorporates the traditional hard-decision RS decoding. A simplified
Berlekamp-Massey, Forney, and Chien algorithms for Chase-type decoding approach is also introduced to reduce
efficient error correction. Implementations on Xilinx complexity. Simulations show significant performance gains
Virtex-II Pro and Spartan-3E FPGAs are compared in terms in high-noise environments. This work bridges the gap
of area and speed. The design is optimized for low power between algebraic RS decoding and iterative decoding
consumption and high-speed operation, demonstrating that techniques, making RS codes more effective for modern
FPGA-based RS decoders can significantly enhance storage systems.[7]
wireless network reliability. The results show that Virtex-II
Pro achieves better area efficiency and higher clock speed ​ ​ The paper titled “Three-Parallel Reed-Solomon
compared to Spartan-3E.[3] Decoder using a Simplified Step-by-Step Algorithm​”
presents a high-speed three-parallel Reed-Solomon (RS)
​ ​ Samir D. Mhaske and Ujwala Ghodeswar designed decoder using a simplified step-by-step algorithm. The
an optimized Reed-Solomon (RS) decoder that reduces proposed design eliminates recursive polynomial solving,
hardware complexity while maintaining error correction reducing hardware complexity and power consumption.
performance. The design targets FPGA implementation and Implemented using TSMC 90nm technology, the decoder
employs a novel Key Equation Solver (KES) using achieves 286MHz operating frequency with a throughput of
Truncated Iterative Berlekamp-Massey (TiBM) architecture, 6.8Gbps and a gate count of 131K. The step-by-step
reducing processing elements compared to traditional algorithm enables parallel processing of error locations and
Berlekamp-Massey designs. The approach significantly values, making it suitable for ultra-high-speed applications
decreases the area required for RS(255,239) decoding while such as optical communication and DVB. The paper
maintaining an 8-symbol error correction capability. The highlights the benefits of systolic array-based Gaussian
proposed solution is particularly beneficial for digital elimination to optimize RS decoding performance.[8]
communication systems requiring efficient forward error
correction with minimal hardware overhead.[4]
​ ​ The paper “A Fast Reed-Solomon and Cyclic
​ ​ This paper titled “Implementation of Redundancy Check Encoding Algorithm for Optical Disk
Reed-Solomon Encoder on Low-Latency Embedded FPGA Error Control​” presents a high-performance Reed-Solomon
in Flexible SoC Based on ARM Processor​” introduces a (RS) and Cyclic Redundancy Check (CRC) encoding
hybrid software-hardware implementation of a algorithm for optical disk storage systems. It addresses error
Reed-Solomon encoder in a flexible System-on-Chip (SoC) correction challenges in high-density digital storage,
architecture. The design integrates an ARM Cortex-M0 implementing a top-down design methodology. The
proposed parallel encoding method enhances speed and restructuring the encoding matrix, the proposed method
reliability, meeting ISO standards for 104-byte codewords. achieves up to 90% reduction in computational complexity,
The RS encoder processes data using a linear feedback shift significantly improving efficiency. The findings benefit
register (LFSR), generating 16 redundant bytes for error applications requiring high-speed error correction, such as
correction. Experimental results demonstrate significant data storage, network coding, and distributed computing,
improvements in processing efficiency, making it suitable where reducing processing overhead is crucial.[13]
for error-prone storage environments such as CDs, DVDs,
and other optical media.[9] ​ ​ The paper titled “Fast Encoding and Decoding
Algorithms for Arbitrary (n, k) Reed-Solomon Codes​”
​ ​ The paper titled “A Novel Image Encoding and presents fast encoding and decoding algorithms for
Communication Technique Using (15,11) Reed-Solomon arbitrary-length Reed-Solomon (RS) codes over finite fields.
Scheme​” proposes a novel image encoding and By leveraging Fast Fourier Transform (FFT)-based
communication approach using (15,11) Reed-Solomon (RS) techniques, the approach achieves optimal computational
codes for IoT, robotics, drones, and smart vehicles. It complexity (O(n log n)), making it one of the most efficient
focuses on wireless and satellite communication, ensuring RS implementations. Unlike previous methods that required
fast and error-free image transmission. Unlike traditional specific code lengths, this technique supports any (n, k)
methods that rely on filtering to reconstruct corrupted configuration, increasing its flexibility for practical
images, this method applies RS codes for error detection applications. The proposed algorithms significantly
and correction. The approach enhances image reliability, accelerate error correction processes, making them suitable
making it suitable for AI-driven applications in autonomous for high-speed data transmission and storage systems.[14]
systems. The proposed technique improves image
reconstruction accuracy, minimizes retransmissions, and
ensures high-quality data for real-time decision-making in ​ ​ The paper “Instruction Set Extensions for
machine vision applications.[10] Reed-Solomon Encoding and Decoding​” introduces four
new processor instructions to accelerate Reed-Solomon
​ ​ The paper “Efficient Encoding and Decoding (RS) encoding and decoding on general-purpose processors.
Algorithm for Reed-Solomon Codes in Multiple By optimizing Galois field arithmetic operations, the
Fault-Tolerance Memories​” introduces an optimized proposed extensions achieve a 12× speedup compared to
Reed-Solomon (RS) encoding and decoding algorithm for pure software implementations. The approach balances
protecting memory systems against multiple-bit upsets programmability and performance, making RS coding
(MBUs). It highlights RS codes’ superior error correction feasible for software-based error correction in digital
capabilities compared to Hamming and LDPC codes, broadcasting, optical networks, and embedded systems. The
particularly for burst errors. A novel multiplication results demonstrate substantial performance gains,
algorithm reduces computational overhead, enhancing highlighting the potential of hardware-software co-design in
efficiency in Verilog HDL implementations. Simulation error correction applications.[15]
results show that RS codes provide higher error tolerance
with lower area overhead than other error correction codes ​ ​ This paper titled “Inter-Packet Symbol Approach
(ECCs). The proposed method is ideal for modern memory to Reed-Solomon FEC Codes for RTP Multimedia”
systems facing reliability challenges due to increasing proposes an innovative inter-packet symbol approach for
transistor density and radiation-induced faults.[11] applying Reed-Solomon (RS) codes to real-time multimedia
streaming over RTP. Unlike traditional intra-packet
​ ​ The paper “Efficient Encoding and Minimum methods, this technique distributes RS symbols across
Distance Bounds of Reed-Solomon-Type Array Codes​” multiple packets, improving resilience to bursty packet
presents an optimized encoding scheme for losses. The approach enables the use of smaller Galois
Reed-Solomon-type array codes, used in constructing fields, reducing encoding/decoding time while maintaining
low-density parity-check (LDPC) codes. It introduces new strong error correction performance. Simulated results
sparse generator matrices that reduce encoding complexity demonstrate its effectiveness in wireless and wired
to linear time. The study also derives upper bounds for the networks, making it a robust solution for streaming
minimum Hamming distance of these codes, ensuring applications such as IPTV, VoIP, and real-time video
optimal error correction performance. By leveraging conferencing.[16]
deterministic code constructions, the approach achieves
similar performance to randomly generated LDPC codes but ​ ​ The paper titled “Sequential Encoding of
with improved efficiency. The findings are particularly Reed-Solomon Codes Using Discrete-Time Delay Lines​”
relevant for high-rate applications requiring reliable error presents a novel sequential Reed-Solomon (RS) encoding
correction with minimal computational overhead.[12] architecture using discrete-time delay lines. Unlike
traditional parallel implementations, which require multiple
​ ​ The paper proposed by Mochan Shrestha and multipliers and adders, this approach uses a single finite
Lihao Xu optimizes the encoding process for Generalized field multiplier and adder, significantly reducing hardware
Reed-Solomon (GRS) codes, widely used in storage and complexity. The delay line consolidates memory elements,
communication systems. The authors introduce an algorithm lowering area and power consumption. This method is
that reduces the number of Galois field multiplications by particularly advantageous for VLSI implementations where
selecting optimal values for key encoding parameters. By clock skew and silicon area are concerned. The findings
make RS encoding more efficient for digital communication 1.​ Primitive Polynomial for GF(28)
and storage systems requiring high-speed yet
low-complexity solutions.[17] The elements of GF(28) are generated using a primitive
polynomial of degree 8. In the provided encoder design, the
​ ​ The paper “Systematically Re-encoded Algebraic primitive polynomial is:
Soft-Decision Reed-Solomon Decoder​” introduces a
systematic re-encoding method to reduce the complexity of p(x) = x8 + x4 + x3 + x + 1 (3.1)
algebraic soft-decision decoding (ASD) for Reed-Solomon 8
(RS) codes. The proposed approach replaces traditional Let a be the primitive element in GF(2 ), which is a root of
erasure decoding with systematic encoding, simplifying the polynomial p(x). Then:
hardware implementation. Additionally, new schemes
modify interpolation and codeword recovery steps, ensuring p(a) = a8 + a4 + a3 + a + 1 = 0 (3.2)
efficiency without performance loss. The method improves
throughput-to-area ratio by 15.5% in (255,239) RS decoding This implies:​
over GF(2⁸), making it highly effective for high-speed a8 = a4 + a3 + a + 1 (3.3)
communication and storage systems.[18]
This relation is used for modulo reduction by the AES
standard irreducible polynomial in finite field multiplication
III.​ METHODOLOGY (as seen in the GFMUL8 module using 8’h1b).
The elements of GF(28) can be represented as 8-tuples
of bits (0s and 1s). The zero element is represented by
all zeros.
If a is the primitive element, then the powers of a (i.e.,
a1, a2, ..., a254) generate all non-zero elements of GF(28).
The first 32 powers of a are used as roots for the
generator polynomial.

2.Generator Polynomial for (255, 239) RS Code

The generator polynomial g(x) for a Reed-Solomon

Fig 3.1: Block Diagram of Encoder
code with parameters (255, 239) has 16 roots and is
The proposed Reed-Solomon encoder is implemented using constructed as:
a modular and parameterized hardware description approach
in Verilog HDL. The design follows a 16-stage Linear g(x) = (x − a1)(x − a2)...(x − a16) (3.4)
Feedback Shift Register (LFSR) architecture optimized for
After expansion, the generator polynomial becomes:
systematic encoding. Flip-Flop modules (FF_opt) are
designed with positive-edge triggering, asynchronous g(x) = 79 + 44x + 81x2 + 100x3 + 49x4
active-low reset, and a clock enable (cen) driven by a valid
signal to ensure controlled data updates and reduced + 183x5 + 56x6 + 17x7+ 232x8 + 187x9
switching activity. Finite field arithmetic is realized over + 126x10 + 104x11 + 31x12 + 103x13+
GF(2⁸), with addition performed using XOR gates
(GFADD) and multiplication implemented through a fully 52x14 + 118x15 + x16 ​
combinational logic-based multiplier module (GFMUL8) to
eliminate the need for lookup tables. The feedback signal is 4. Encoder Architecture​
calculated as the XOR of the incoming data byte and the The encoder consists of the following submodules:
output of the last register stage. This feedback is multiplied
A. Input Interface:
with fixed generator coefficients (GIN0 to GIN15), and the
results are XORed with the corresponding register outputs 1.​ Accepts an 8-bit datain input per clock cycle.
to form the new register inputs. The encoder uses pipeline 2.​ Uses valid signal as a clock enable and clkin as
registers for each stage to ensure timing reliability and the system clock.
maintain throughput. All generator polynomial coefficients B. Feedback Computation:
are parameterized to support easy reconfiguration. The final
encoded parity symbols are obtained from the outputs of the Feedback value fback is computed as datain ⊕ q15
16 register stages. (last register value).
C. Galois Field Multipliers (GFMUL8):
1.​ 16 parallel GF(2^8) multipliers multiply fback
with generator polynomial coefficients (GIN0 to
GIN15).
2.​ Coefficients are passed as parameter values to
enable synthesis-time optimization.
D. Galois Field Adders (GFADD):
1.​ 15 XOR-based GF(2^8) adders form an LFSR
chain:
z[i] = q_int[i-1] ⊕ m[i], where m[i] is multiplier
output.
2.​ z[0] is directly assigned m[0].
E. Pipeline Register Bank (FF_opt):
1.​ 16 clock-enabled flip-flops store intermediate
parity values q_int[0] to q_int[15].
2.​ Flip-flops update only when valid is high and
rst_n is active.
F. Output Interface:
Parity outputs q0 to q15 reflect the encoder's internal
state for error correction.
The design ensures synchronous updates with each rising
edge of the clock, gated by a valid signal, and supports
asynchronous reset functionality.
Fig. 4.1: Non-Optimized code analysis and synthesis resource usage
IV.​ RESULTS

The paper's main goal was to design and analyse the

difference between non-optimized and an optimized
implementation of a Reed-Solomon (RS) encoder.

Comparative Analysis of Non-Optimized and Optimized

Reed-Solomon Encoder Designs

1)​ Non-Optimized Reed-Solomon Encoder:

The objective was to evaluate the impact of algorithmic
optimization on hardware resource utilization and power Fig. 4.2: Power analysis of non-optimized code
consumption in FPGA-based RS encoding systems, using
Intel Quartus Prime and targeting the MAX V device family.
In the initial, non-optimized implementation, a traditional 2)​ Optimized Reed-Solomon Encoder:
RS encoding scheme was synthesized without consideration The optimized implementation of Reed-Solomon encoder
for logic minimization or power efficiency. The analysis utilized only 151 logic elements, marking an 83% reduction
revealed that the design utilized a total of 901 logic in overall logic usage. The combinational logic without
elements, with 773 of them functioning as combinational registers was reduced to 23, and the usage of 4-input LUTs
logic without registers and 128 operating as combinational dropped to 113, clearly indicating a significant reduction in
logic with registers as can be seen in Fig 4.1.The design combinatorial complexity. This following information is
heavily depended on 4-input LUT functions (799 instances), shown in fig 4.3.While the number of registers remained
indicating a high level of logic complexity. Furthermore, the consistent at 128, the total fan-out was 1058, with a
design consumed 267 I/O pins and registered a maximum maximum of 128, considerably lower than the
fan-out of 129 with a total fan-out of 3877, suggesting non-optimized counterpart, thus indicating reduced logic
significant interconnect activity across the logic fabric. congestion and improved routing efficiency.

From a power standpoint, the non-optimized encoder Power analysis of the optimized design revealed a
exhibited a total thermal power dissipation of 6.30 mW, substantial decrease in total thermal power dissipation to
which consisted of 3.23 mW of I/O thermal power. The total 3.80 mW, nearly a 40% reduction compared to the
register count was 128, corresponding primarily to baseline. Specifically, the core static power was 3.08 mW,
asynchronous clear/load mode logic elements as shown in and I/O power dropped significantly to 0.72 mW as shown
fig 4.2. in fig.4.4. The power estimation confidence was marked low
for both designs due to insufficient toggle rate data;
however, the relative comparison remains valid under
identical analysis conditions.
 Fig. 4.5 Output of Optimized Reed-Solomon encoding

Differences between non-optimized and optimized

Reed-Solomon encoding with respect to logic elements,
fan-out and power dissipation are shown in table 4.1.
Features Non-Optimized Optimized
Fig. 4.1: Optimized code analysis and synthesis resource usage Code Code

Total Logic Elements 901 151

Logic 4-input 799 113

element LUT
usage by
number 3-input 93 20
of LUT LUT
inputs
Fig. 4.2: Power analysis of optimized code
Total fan-out 3877 1058
Power Consumption:
In the non-optimized design, power usage was higher due to Total Thermal Power 6.30 mW 3.80 mW
excessive signal toggling and redundant computations. The Dissipation
optimized version reduces power consumption by
minimizing unnecessary transitions and restricting logic I/O Thermal Power 3.23 mW 0.72 mW
activity to valid data cycles only. Dissipation
Table 4.1: Differences between optimized and non-optimized approach.
Switching Activity:
The non-optimized version suffered from high switching V.​ Conclusion and Future Scope
activity, especially during idle or invalid cycles. The
optimized implementation significantly lowers dynamic This project effectively demonstrates the impact of
power by enabling controlled switching strictly during valid RTL-level optimization on a Verilog-based Reed-Solomon
operations. encoder, with a focus on finite field arithmetic and control
logic. By rearchitecting the design using synthesis-aware
Timing Closure: strategies, significant improvements were observed in key
Achieving timing closure was more challenging in the design metrics. Power consumption was reduced by
non-optimized design because of longer and less efficient approximately 40%, primarily due to minimized signal
critical paths. The optimized version benefits from toggling and elimination of unnecessary computations.
improved logic organization and constant propagation, Timing closure improved substantially, with critical path
making timing closure faster and more reliable. delay reduced by around 5%, easing back-end synthesis and
meeting tighter timing constraints. Additionally, hardware
Synthesis Friendliness: resource utilization—estimated via I/O switching
The non-optimized code had complex inference paths and activity—was optimized, resulting in a 78% reduction in
irregular RTL structure, making it less synthesis-friendly. In logic-related power activity.
contrast, the optimized code is modular, synthesis-aware,
and better suited for back-end optimizations, resulting in The optimized encoder highlights how thoughtful HDL
cleaner and more efficient hardware realization. design choices—such as leveraging constants, modular
structuring, and conditional data switching—can
Output of optimized code for Reed-Solomon encoding is significantly enhance Performance, Power, and Area (PPA).
shown in fig. 4.5. These optimizations not only make the design more robust
and scalable but also make it better suited for integration Re-configurable; Tree-Based; SoC; Reed
into modern low-power or high-speed communication Solomon},
systems, aligning well with advanced VLSI design
requirements. [6] C. Kim, S. Rhee, J. Kim and Y. Jee, "Product
Reed-Solomon Codes for Implementing NAND
VI. REFERENCES Flash Controller on FPGA Chip," 2010 Second
International Conference on Computer Engineering
[1] Yun Chen, Yuebin Huang, Wei Meng, Zhiyi Yu and and Applications, Bali, Indonesia, 2010, pp.
Xiaoyang Zeng, "A low-cost architecture for 281-285, doi: 10.1109/ICCEA.2010.63. keywords:
multi-mode Reed-Solomon decoder," 2012 {Reed-Solomon codes; Field programmable gate
International SoC Design Conference (ISOCC), arrays; Error correction codes; Error correction ;
Jeju Island, 2012, pp. 332-334, doi: Decoding; Nonvolatile memory; Data storage
10.1109/ISOCC.2012.6407108. keywords: systems; Product codes; Gain;Bandwidth ;
{Decoding;Hardware;Reed-Solomon codes Reed-Solomon code; Product code; NAND flash
;Clocks; Throughput; Powerdemand; Computer memory; error correction code; FPGA},
architecture; Reed-Solomon codes ;multi-mode;
low cos; VLSI architecture}, [7] H. Xia and J. R. Cruz, "Reliability-Based
Reed-Solomon Decoding for Magnetic Recording
[2] C. Le Dantec and P. Piret, "An encoder to match Channels," in IEEE Transactions on Magnetics,
Reed-Solomon codes over GF(q) to a subalphabet vol. 42, no. 10, pp. 2603-2605, Oct. 2006, doi:
of GF(q)," in IEEE Transactions on Information 10.1109/TMAG.2006.878651. keywords:
Theory, vol. 45, no. 5, pp. 1697-1701, July 1999, {Reed-Solomon codes;Magnetic
doi: 10.1109/18.771248. keywords: recording;Iterative decoding;Parity check
{Reed-Solomon codes}, codes;Belief propagation;Iterative algorithms;USA
Councils;Algorithm design and
[3] B. Tiwari and R. Mehra, "Design and analysis;Performance analysis;Test pattern
implementation of Reed Solomon Decoder for generators;Error correction codes;iterative
802.16 network using FPGA," 2012 IEEE decoding;magnetic recording;partial response
International Conference on Signal Processing, channels;Reed–Solomon codes;soft-decision
Computing and Control, Solan, India, 2012, pp. decoding},
1-5, doi: 10.1109/ISPCC.2012.6224380. keywords:
{Decoding; Polynomials ;Field programmable gate [8] C. Yu, K. -H. Lee, J. -Y. Chen, M. -W. Chen and Y.
arrays; Forward error correction; Reed-Solomon -A. Chen, "Three-Parallel Reed-Solomon Decoder
codes; IEEE 802.16 Standards; Mathematical using a Simplified Step-by-Step Algorithm," 2018
model; Chien's search; DVB;FEC; Forney; FPGA; IEEE 7th Global Conference on Consumer
Reed-Solomon (RS); reconfigurable; Syndrome Electronics (GCCE), Nara, Japan, 2018, pp.
calculator; VHDL;WiMax}, 105-106, doi: 10.1109/GCCE.2018.8574818.
keywords: {Decoding; Hardware; Computer
[4] S. D. Mhaske, U. Ghodeswar and G. G. Sarate, architecture ; Detectors; Calculators;
"Design of area efficient Reed Solomon decoder," Reed-Solomon codes; Logic gates; Reed-Solomon
2014 2nd International Conference on Devices, Code; Step-by-Step Algorithm; Systolic Array},
Circuits and Systems (ICDCS), Coimbatore, India,
2014, pp. 1-4, doi: [9] R. . -S. Kao and V. L. Gibbs, "A fast
10.1109/ICDCSyst.2014.6926169. keywords: Reed-Solomon and cyclic redundancy check
{Decoding;Polynomials;Computer encoding algorithm for optical disk error control,"
architecture;Reed-Solomon codes;Mathematical Proceedings Seventh Annual IEEE International
model;Complexity theory;Algorithm design and ASIC Conference and Exhibit, Rochester, NY,
analysis;Reed-Solomon codes;syndrome;key USA, 1994, pp. 250-253, doi:
equation solver;Berlekamp-Massey 10.1109/ASIC.1994.404565. keywords:
algorithm;pipelined}, {Reed-Solomon codes;Cyclic redundancy
check;Encoding;Optical control;Error
[5] H. Saidi, M. Turki, Z. Marrakchi, A. Obeid and M. correction;Optical distortion;Polynomials;Optical
Abid, "Implementation of Reed Solomon Encoder feedback;Galois fields;Cyclic redundancy check
on Low-Latency Embedded FPGA in Flexible SoC codes},
based on ARM Processor," 2020 International
Wireless Communications and Mobile Computing [10] M. Z. Ejaz, K. Khurshid, Z. Abbas, M. A. Aizaz
(IWCMC), Limassol, Cyprus, 2020, pp. and A. Nawaz, "A novel image encoding and
1347-1352, doi: communication technique of B/W images for IOT,
10.1109/IWCMC48107.2020.9148349. keywords: robotics and drones using (15, 11) reed solomon
{Field programmable gate arrays;Hardware; scheme," 2018 Advances in Science and
Reed-Solomon codes; Software; System-on-chip; Engineering Technology International Conferences
Table lookup; Task analysis; Embedded FPGA; (ASET), Abu Dhabi, 2018, pp. 1-6, doi:
 10.1109/ICASET.2018.8376846. keywords: [15] S. Mamidi, M. J. Schulte, D. Iancu, A. Iancu and J.
{Robots;Decoding;Encoding;Drones;Reed-Solomo Glossner, "Instruction set extensions for
n codes;Wireless communication;Mathematical Reed-Solomon encoding and decoding," 2005
model;Reed Solomon;Image IEEE International Conference on
reconstruction;Encoding;Decoding;Internet of Application-Specific Systems, Architecture
Things;Drones;Robotics;Smart Vehicles;Wireless Processors (ASAP'05), Samos, Greece, 2005, pp.
Communication;Satellite 364-369, doi: 10.1109/ASAP.2005.42. keywords:
Communications;Artificial Intelligence;Machine {Reed-Solomon codes; Encoding; Decoding;
Learning;Machine Vision}, Galois fields; Error correction codes; Hardware;
Digital video broadcasting; Forward error
[11] Liyi Xiao, Zheng Sun and Ming Zhu, "Efficient correction; Arithmetic; Software performance},
encoding and decoding algorithm used in
Reed-Solomon codes for multiple fault-tolerance [16] F. Casu, J. Cabrera, F. Jaureguizar and N. García,
memories," Proceedings of 2011 Cross Strait "Inter-packet symbol approach to Reed-Solomon
Quad-Regional Radio Science and Wireless FEC codes for RTP-multimedia stream protection,"
Technology Conference, Harbin, 2011, pp. 2011 IEEE Symposium on Computers and
1569-1572, doi: 10.1109/CSQRWC.2011.6037272. Communications (ISCC), Kerkyra, Greece, 2011,
keywords: {Memory pp. 49-54, doi: 10.1109/ISCC.2011.5984024.
management;Decoding;Reed-Solomon keywords: {Encoding; Reed-Solomon codes;
codes;multiplication;multiple bits Forward error correction; Decoding; Redundancy;
upsets;memories}, Real time systems; Media; Multimedia
Communications; Wireless Networks; Real Time
[12] T. Mittelholzer, "Efficient encoding and minimum Protocol; Forward Error Correction;
distance bounds of Reed-Solomon-type array Reed-Solomon codes},
codes," Proceedings IEEE International
Symposium on Information Theory,, Lausanne, [17] P. Tong and P. Ruetz, "Sequential encoding of
Switzerland, 2002, pp. 282-, doi: Reed-Solomon codes using discrete-time delay
10.1109/ISIT.2002.1023554. keywords: lines," in IEEE Transactions on Communications,
{Encoding; Reed-Solomon codes; Parity check vol. 42, no. 1, pp. 2-5, Jan. 1994, doi:
codes; Sparse matrices; Laboratories; Upper 10.1109/26.275291. keywords: {Encoding;
bound; Hamming distance; Polynomials; Binary Reed-Solomon codes; Delay lines; Galois fields;
codes; Encyclopedias}, Clocks; Interleaved codes; Throughput;
Polynomials; Gold; Registers},
[13] M. Shrestha and L. Xu, "Efficient Encoding for
Generalized Reed Solomon Codes," 2011 IEEE [18] X. Zhang and Y. Zheng, "Systematically
10th International Symposium on Network Re-encoded Algebraic Soft-Decision
Computing and Applications, Cambridge, MA, Reed–Solomon Decoder," in IEEE Transactions on
USA, 2011, pp. 302-305, doi: Circuits and Systems II: Express Briefs, vol. 59,
10.1109/NCA.2011.52. keywords: no. 6, pp. 376-380, June 2012, doi:
{Encoding;Reed-Solomon codes; Mathematical 10.1109/TCSII.2012.2195066. keywords:
model; Equations; Decoding; Reliability; {Interpolation; Decoding; Systematics;
Application Software; Decoding; Encoding; Fault Polynomials; Vectors; Complexity theory;
tolerance; Fault tolerant systems; Cloud Reliability; Algebraic soft-decision decoding
computing; Reed-Solomon codes}, (ASD); Chase decoding; Reed–Solomon (RS)
codes; re-encoding; very large scale integrated
[14] N. Tang and Y. Lin, "Fast Encoding and Decoding (VLSI) design},
Algorithms for Arbitrary $(n,k)$ Reed-Solomon
Codes Over $\mathbb{F}_{2^m}$," in IEEE [19] William A Geisel. Tutorial on reed-solomon error
Communications Letters, vol. 24, no. 4, pp. correction coding. 1990.
716-719, April 2020, doi:
10.1109/LCOMM.2020.2965453. keywords:
{Complexity theory; Decoding; Encoding;
Transforms; Reed-Solomon codes; Laplace
equations; Indexes; Reed-solomon codes; fast
fourier transform; decoding algorithm },