Introduction
Reed-Solomon codes (RS-FEC) [1] are used in telecommunications and data storage devices due to their error correction properties. Input data is encoded by using polynomial division over Galois Fields (GF) and the bits resulted from this operation will be called parity symbols. The newly obtained parity symbols are then appended to the input data (which is also divided into data symbols) to form a codeword made up of data symbols and parity symbols. Each symbol has a fixed number of bits. The receiver uses the parity symbols during decoding to detect and correct errors in the codeword. Therefore, the number of parity symbols in a codeword determines the number of errors that can be detected or corrected.
This post aims to present a solution to the problem of finding a working reference model for functional verification of Reed-Solomon encoding and decoding modules.
Table of contents
1. Problem
Functional verification of a Reed-Solomon encoder or decoder module requires a working reference model of the encoding and decoding algorithms. However, currently there are no open-source implementations of these algorithms that can be easily integrated into UVM testbenches without spending too much time on linking and compatibility issues.
2. Solution
This article presents a Universal Verification Component (UVC) for Reed-Solomon codes, with encoding, decoding and error injection features, depicted in Figure 1.
The UVC has 3 modes that the user can set in the configuration object:
-
- decode only;
-
- encode only;
-
- both.
The UVC supports any valid codeword configuration and any symbol size between 3 and 20 bits. Examples include:
-
- 8-bit configurations (RS(255, 223), RS(208, 192), etc.);
-
- 10-bit configurations (RS(544, 514), RS(528, 514), etc.);
-
- any other configuration.
Using the Reed-Solomon decoding algorithm, the UVC can detect or correct a number of errors that depends on the number of parity symbols. This is because a Reed-Solomon decoder will always correct up to t symbols that contain errors in a codeword and detect up to 2t symbols, where 2t is the number of parity symbols. For instance, when using the configuration RS(255, 223), which means that a codeword will have 255 total symbols and 32 parity symbols, the decoder will correct up to 16 errors and detect up to 32 errors. The UVC’s Decoder packs its output data into an item which contains both the codeword converted into a bytestream and the decoding results (how many errors it corrected, or whether the codeword could not be recovered).
2.1 Encoding and decoding components
The Encoder receives bytestreams as input data. Afterwards, it converts the raw data to data symbols and encodes them using the Reed-Solomon encoding algorithm. Codewords are the final result of this process and they are sent to an optional component called Error Injector which adds noise to the codewords in order to simulate a real life communication channel. The Error Injector sends the codewords with errors to the Decoder which will either correct the errors or detect that there were too many errors for the original codeword to be recovered.
The UVC has two checkers for RTL encoders and decoders (Encode Checker, Decode Checker). The Encode Checker receives an encoded bytestream from the user’s RTL, extracts the data symbols and encodes them in order to compare the resulting parity symbols with the received ones. The Decode Checker receives noisy data from the user’s RTL, along with the user’s decoding results, and then decodes the data using the UVC’s algorithm. Afterwards, it compares the decoding algorithm’s results with the ones received from the user.
2.1.1 Algorithms validation
The encoding and decoding algorithms were validated by using functions from a C library developed by Phil Karn (libfec) [2] and the RS functions from Matlab’s Communications Toolbox [3]. While testing the UVC, the input data for the Encoder and Decoder was sent to C encoding and decoding functions using DPI-C [4] and the results from both implementations were then compared in order to initially validate the UVC’s algorithms. To test the UVC’s encoding and decoding algorithms against the Matlab RS functions, the UVC generated multiple sets of input data, codewords, noisy codewords and decoded data of varying RS configurations. Afterwards, these were loaded into a Matlab script that compared the UVC’s codewords with the ones generated by the Matlab RS functions.
Additionally, during the testing phase, the UVC’s Decoder’s input was generated by the Encoder and the Error Injector, so the Decoder’s results should be identical to the original codewords generated by the Encoder. In order to test this claim, the Decoder’s results were compared with the initial codewords inside a small Scoreboard.
2.2 Error injection
The UVC has a component called Error Injector that can be used to add errors to codewords in multiple ways. Its main purpose is to simulate a real life channel and it can be disabled if it is not needed in the user’s testbench. Another optional feature is the simulation of channel erasures (errors on known positions). If it is enabled, the Error Injector will send out an item containing a list of known symbols with errors.
The Error Injector has multiple modes of error injection, which can be seen in the following table:
| # | Name | Description |
| 1 | ERROR_NUMBER_MODE | The Error Injector will insert a certain number of errors in each codeword, based on an interval that the user can choose beforehand. |
| 2 | CODEWORD_STATUS_MODE | The user can choose whether to produce error-free, correctable, uncorrectable or corrupted codewords. The uncorrectable codewords will have between t and 2t errors, and the corrupted ones will go over this threshold. |
| 3 | ERROR_FREQUENCY_MODE | Each codeword will have a certain frequency of flipped bits, for example 1 bit in 200. |
| 4 | ONLY_ERASURES_MODE | The Error Injector will only add errors with known positions, or erasures, to a codeword. |
| 5 | USER_DEFINED_ERASURES_MODE | The user has to supply the UVC with an erasure item to be used during the test. This can be done by calling a function inside the UVC’s config object. |
2.2.1 Error injection validation
Similar to the UVC’s encoding and decoding algorithms, the Error Injector was validated in each mode of error injection. An additional component called Error Injector Checker compares the Error Injector’s input with its output in order to determine the number, type and pattern of errors and checks that they match the Error Injector’s settings.
2.3 Settings
The UVC is highly configurable and the user can tweak over 20 individual settings inside the UVC’s configuration object. The user can set these manually, or through the use of command line arguments (plusargs). These settings include:
-
- the ability to deactivate or activate coverage and various components;
-
- the ability to choose the Error Injector’s mode;
-
- multiple settings related to error injection that can help the user tweak the number, type and pattern of errors;
-
- the codeword configuration;
-
- etc.
2.4 UVC validation
In order to validate the UVC as a whole and collect coverage, multiple regressions were run consisting of a wide variety of tests. The UVC was instantiated in a test environment where input was driven to it and the Reed-Solomon algorithms and Error Injector were validated by running the following tests:
-
- Random test: The input data for the UVC, the Error Injector’s settings, and the Reed-Solomon code parameters are all constrained and randomized.
-
- Burst test: The UVC’s input, code parameters and the Error Injector’s settings are randomized as well, however the input data is constrained to consist of large bursts of codewords (100-200).
-
- Reconfiguration test: The UVC is reconfigured a random number of times during this test, and each time the code parameters and the Error Injector settings are randomized.
-
- High noise test: This is a directed test in which the UVC is instantiated with a code configuration consisting of 12 bit symbols and the Error Injector is set to generate mostly corrupted codewords in order to collect error coverage.
3. Usage
The user can integrate this UVC into UVM testbenches that contain a Reed-Solomon encoder/decoder RTL or use Reed-Solomon codes. Examples of usage include:
-
- generating codewords with errors as input for a decoder RTL;
-
- decoding codewords that can be compared with the output of a decoder RTL;
-
- validating an encoder RTL by using the Encode Checker;
-
- validating a decoder RTL by comparing its decoding results with the ones obtained by the Decode Checker;
-
- etc.
3.1 Decoder RTL validation
As seen in Figure 2, the user can deactivate the UVC’s Decoder and use only the Encoder and Error Injector to generate codewords and add errors to them, using a highly configurable error pattern. In this way, the user can simulate any real life error scenario for a decoder RTL.
If the user wants to validate the RTL, they can activate the UVC’s Decoder and compare its validated output with the decoder RTL’s output (Figure 3).
Likewise, as seen in Figure 4, the user can activate the Decode Checker component inside the UVC in order to validate a decoder RTL’s behavior and detection ability. In order to do so, the user can send noisy data and the decoding results obtained by an RTL (or another decoder implementation) to the Decode Checker. Afterwards, it decodes the data and compares the UVC’s decoding results with the ones that the user sent.
3.2 Encoder RTL validation
Testing an encoder RTL is similar to testing a decoder RTL. For instance, the user can manually compare the UVC’s Encoder’s output with an encoder RTL (Figure 5), or they can use the Encode Checker to directly validate the RTL’s codewords (Figure 6).
The presented use cases are not mutually exclusive, meaning that the user can test both an encoder RTL and a decoder RTL at the same time by using this UVC. Additionally, the user can reconfigure or reset the UVC at any point during the simulation. However, the user cannot reconfigure essential features, such as activating or deactivating certain components.
4. Conclusions
Given that implementing efficient encoding or decoding algorithms from scratch requires a deep understanding of the algorithms, it can be a time consuming process for a verification team. Choosing to use an external implementation of these algorithms (C/C++ libraries, Matlab functions) may not be a good idea either, as they could be costly (a Matlab license) or buggy and difficult to use (old C/C++ libraries with little to no documentation).
The Reed-Solomon UVC presented in this article aims to solve this problem encountered by verification teams by providing efficient Reed-Solomon encoding and decoding, and also error injection features. The UVC supports any valid codeword length and number of parity symbols across multiple symbol sizes (from 3 bits, up to 20 bits per symbol).
The Reed-Solomon functions are included in a software package which can be used by itself and without instantiating the UVC. Additionally, fast and simple checking of a DUT’s encoding and decoding algorithms can be done using the UVC’s checker components: Encode Checker and Decode Checker.
5. Installation
This project’s source code can be accessed at AMIQ’s GitHub repository.
6. References
[1] – An introduction to Reed-Solomon codes: principles, architecture and implementation
[2] – https://github.com/ka9q/libfec
[3] – Error Detection and Correction
[4] – How to Call C-functions from SystemVerilog Using DPI-C