Xilinx Reed-Solomon Tutorial 1

This is the first of two tutorials developed to introduce users to the normal flow used for specifying, generating, implementing, and simulating the Xilinx Reed-Solomon Encoder and Decoder LogiCOREs. The tutorials use a simple image encoding/decoding application to help introduce the basic concepts of the Reed-Solomon encoding and decoding processes. This tutorial concentrates on using the encoder core, while Tutorial 2 concentrates on the decoder core.

Getting Started

The tutorials were developed and verified on a PC-based Windows platform. It should be possible to complete them on a unix-based system, although this has not been fully tested. Before commencing this tutorial, you must complete the following steps: Ensure your system has the following software tools (or appropriate alternatives): WinZIP (7.0 or later) Any tool capable of extracting ZIP files should be suitable. Netscape Communicator (4.5 or later) Any browser that supports the JDK1.1.5 version (or later) of Java, should be suitable. The latest version of Netscape Communicator may be downloaded from here. Note that Java must be enabled in the browser preferences. Also note that the cores are delivered to your email account, so you should also be able to access it. Xilinx Foundation Series (2.1i or later) Xilinx Alliance Series 2.1i is also suitable, but note that a 3rd-party synthesis tool capable of instantiating a "black-box" component will also be required. Modelsim PE (5.2e or later) Any VHDL simulator that supports VHDL records should be suitable. LViewPro (2.7 or later) The simulation testbenches read and write images using the PGM (Portable Gray Map) file format. Any image viewer that supports the PGM format should be suitable. If you don't already have one, PC-based users should check out the latest version of LViewPro at http://www.lview.com. Unix-based users should check out John Bradley's All things XV webpage. Download xrs.zip. It contains: copies of the tutorial worksheets (including this one) VHDL testbenches and support files command scripts for the implementations tools and modelsim Extract xrs.zip using WinZIP into a directory called C:\xrs. If you have to install it somewhere else, remember to modify all the pathnames of files and scripts referred to in the tutorial worksheets, as they all have "C:\xrs\" prepended. Read the Reed-Solomon Encoder datasheet Make a hard copy of this tutorial for annotation.

Example Application

Suppose we want to transmit the data stream generated by a digital still camera to a central data base, over a noisy communications channel. Assume that the captured monochrome images have 187x130 pixels, where there are 187 pixels in each row. Each pixel is represented by an 8-bit value where 0 is black, 255 is white, and the values in between are gray levels.

We could use a Reed-Solomon encoder to add check symbols to the data stream. Then, errors introduced by the noisy communications channel can be detected and corrected by a Reed-Solomon decoder at the receiver end.

Specifying the Reed-Solomon Code

The Xilinx Reed-Solomon LogiCOREs are parameterizable and can be configured to implement many different Reed-Solomon codes. These can be existing coding standards or fully customized codes defined by the user. This section explains how we can go about choosing a suitable Reed-Solomon code for the above application. The following parameters are needed to fully specify the Reed-Solomon code: n k Symbol Width Field Polynomial Generator Start h Note that any Reed-Solomon encoder/decoder pair must use exactly the same values for the above parameters. If these parameters aren't identical, then the cores will use different Reed-Solomon codes. Therefore the decoder will not recognise the code words that the encoder generates i.e. it won't be able to detect or correct any errors.

n and k Reed-Solomon codes are usually referred to as RS(n,k) codes, where n is the total number of symbols in a code word, and k is the number of information or data symbols in the code word. In a systematic code the complete code word is formed by appending (n-k) check symbols to the k information symbols i.e.:            k Information Symbols         (n-k) Check Symbols If we choose to encode each row of the image in a separate code word, then k=187. How should we select n? This depends on how much error correcting capability we want our Reed-Solomon code to have. The maximum number of errors that can be corrected in a code word is t=(n-k)/2. This is always rounded down to the nearest whole number. If the transmission channel is bandwidth limited, then it should be apparent that there is a trade-off between the bandwidth available for information symbols, and the bandwidth required for the check symbols. In communications theory the term code rate is used to give a measure for this trade-off. For Reed-Solomon codes the code rate is defined as k/n, and is typically > 0.8.

Let's choose to add twenty check symbols, so n = 207.

Q1. What is the code rate?

Answer : ____________________

Q2. How many errors will this code be able to correct?

Answer : ____________________

Symbol Width This defines the number of bits per symbol in the Reed-Solomon code. As the pixel gray levels are represented by 8-bit values, it makes sense to choose Symbol Width=8. Note that the maximum allowable values for n and k actually depend on Symbol Width (see data sheet for details).

Field Polynomial The underlying mathematics in Reed-Solomon codes uses finite field arithmetic. Finite field arithmetic was invented by a French mathematician called Évariste Galois (1811-1832), and is often referred to as Galois field arithmetic. A Galois field is a set of elements, for which the result of certain arithmetic operations (such as addition, subraction, multiplication, division) between any two elements, is another element of the set. The Field Polynomial is used to define the order of the elements in the Galois field. It is normally specified using a polynomial representation. For example, the field polynomial for the European Digital Video Broadcast (DVB) standard is usually given as: p(x) = x8 + x4 + x3 + x2 + 1 The encoder and decoder configuration GUIs require the field polynomial to be entered as a decimal number. How can we express the above polynomial as a decimal number? First of all, we convert the polynomial to a binary equivalent, then we convert the binary number into a decimal number. Therefore the decimal equivalent of the DVB polynomial is 285 i.e. p(x) = x8 + x4 + x3 + x2 + 1 => 100011101 => 285 Here the first (from left) 1 in the binary equivalent corresponds to the coefficient of the x8 term, the second 1 corresponds to the coefficient of the x4, and so on. Note that there are only a few valid field polynomials for each value of Symbol Width. For your future reference, here is a list of all the valid field polynomials for Symbol Width=3 to 8.  Symbol Width  Valid field polynomials (decimal representation) 3  11,13  4  19,25  5  37,41,47,55,59,61  6  67,91,97,103,109,115  7  131,137,143,145,157,167,171,185,191,193,203,211,229,241,247,253  8  285,299,301,333,351,355,357,361,369,391,397,425,451,463,487,501  For our application, we will use: p(x) = x8 + x7 + x2 + x + 1 Q3. What are its binary and decimal representations?

Answer : __________________(binary) __________(decimal)

Check that your decimal value appears in the valid field polynomial table.

Generator Start and h These are used to specify the generator polynomial. The generator polynomial is used to calculate the appropriate check symbols for each block of k information symbols. In some standards it is specified using a factored product form. For example, the generator polynomial for the DVB RS(204,188) standard is usually given as: g(x) = (x + a0)(x + a1)(x + a2)(x + a3)...(x + a12)(x + a13)(x + a14)(x + a15) There are a few things to note about this equation: It should have 16 terms - for brevity, the middle eight terms have been replaced by "...". In Galois field arithmetic, addition and subtraction are exactly the same operation (bit-wise XOR), and can be used interchangeably. Sometimes this equation is expressed using minus signs instead of plus signs. Normally the lower-case Greek "alpha" symbol is used in place of a, but not all browsers support Greek symbols. (As an aside, the "alpha" variable is also known as the primitive element of the Galois field.)

The Xilinx Reed-Solomon cores require the generator polynomial to be expressed in the following product form: where Generator Start and h are entered in the configuration GUIs. It is quite easy to convert the factored product form to the product form to evaluate Generator Start and h. This is achieved by examining the series of exponents of a. It is best to evaluate h first. For the DVB generator polynomial, the series is: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 The h parameter is just the increment index of the series, i.e. h=1. Most Reed-Solomon standards use h=1, and in fact the Xilinx Reed-Solomon decoder core only supports this value (so h isn't even on the configuration GUI). Note that the encoder core can support any positive integer for the h parameter.

Generator Start is evaluated by dividing the first element of the series by h, so for the above series, Generator Start=0/1=0.

For our application, we will use the following generator polynomial: g(x) = (x + a1)(x + a2)...(x + a19)(x + a20) Q4. Evaluate h and Generator Start for this generator polynomial, and enter them in the table below, along with the other parameters to completely define the Reed-Solomon code for our imaging application.   Parameter Value Symbol Width   k   n   Field Polynomial (decimal)   Generator Start   h   Click here to see completed table.

Generating the encoder core

Go to the Xilinx Reed-Solomon web page at www.xilinx.com/ipcenter/reed_solomon. This page describes some of the features of the Xilinx Reed-Solomon solution, and includes links to the datasheets and configuration GUIs. Click on Generate a RS Encoder Core under the heading Reed-Solomon Lounges (Customers only). The Username and Password Required window will appear: Enter your username and password. Once they have been confirmed, the Xilinx LogiCORE Reed-Solomon Encoder, Configuration and Download page will be displayed. The encoder configuration GUI is within this page: This is where the core can be customized for your requirements. Complete the fields by going through the following steps: Component Name: the testbench you will use later on in the Simulation section of this tutorial expects the encoder component to be called rse. Enter rse in the text field. Code Specification: this field has a pull-down menu with several pre-defined standards such as DVB, ATSC, etc. Note that if you choose one of these pre-defined standards, the rest of the Code-Block parameters become grayed out. The core specification you have to implement is not one of these standards, so select Custom. Enter the appropriate values for the other fields in the Code-Block Parameters box. The encoder configuration GUI also allows you to select whether the core should be optimized for Area or Speed. Speed optimization is recommended for Virtex, VirtexE and Spartan-II implementations of the core. Create RPM: select the tick box so that core will be a relationally placed macro. You may have noticed that some of the values turn red while you are entering them. This is because the GUI is continually checking that the parameter you are entering is valid. Also, some of the fields depend on the values entered in others. For example, when Symbol Width = 8, and you attempt to set n to 256, the value will turn red.

Note that you can reset the fields using the Defaults button, or you can go to the online Help page for further information on the parameters and their valid ranges. Once you have entered all the parameters click the Submit button. The Download Form window will appear. Enter your email address and ensure that the other fields match the following: When you have completed the Download Form, click OK. The Request Successfully Submitted page will appear. Xilinx Webmaster will send you a confirmation email detailing the core parameters and options you selected. It will then generate your customized core. This should only take a few minutes (unless the web server is particularly busy). Xilinx Webmaster will then send you an email with an attached zip file. Unzip this file in: C:\xrs\unzipped\rs_encoder Within this directory, the following 7 files should now be accessible: docs\readme.txt   - explains what each of the files is for docs\enc_spec.pdf - current version of the RS encoder core data sheet rs_encoder.v      - Verilog behavioral model for the core rs_encoder.vhd    - VHDL behavioral model for the core rse.edn           - EDIF netlist for your required parameters rsenc_wrap.v      - illustrates how to instantiate the core using Verilog rsenc_wrap.vhd    - illustrates how to instantiate the core using VHDL View these files using a text editor such as WordPad, starting with readme.txt.

Q5. What did you notice about the code within the behavioral models?

Answer : _____________________________________

Adding pads and global buffers

Before the core can be pushed through the Xilinx implementation tools, pads and buffers must be added. In this tutorial we will use FPGAExpress to accomplish this (if you use another sythesis tool, you should still be able to follow this part of the tutorial - just substitute the appropriate commands for your tool). You could just use the rsenc_wrap.vhd included in the emailed zip file. However, you should use an enhanced version called C:\xrs\fpgaexpress\rsenc_wrap.vhd. This version has: the core's reset pin connected to the dedicated Global Set/Reset resource (using a STARTUP_VIRTEX instantiation) the core's clk pin driven by a Global Low-skew clock buffer (a BUFG instantiation) Complete the following steps to create an EDIF wrapper from rsenc_wrap.vhd: Launch FPGAExpress. Create a new project by clicking the New Project button in the toolbar or by selecting File->New Project... In the Create New FPGA Express Project dialog box, you can choose a location for the project.  Use the drop-down list in the Save In field to navigate your directory tree to: C:\xrs\fpgaexpress Enter rs_encoder in the Name: field. The rs_encoder directory is where project files will be stored. Click on the Create button to create the new project. After the program creates the rs_encoder project, the Add sources dialog box is displayed. Select C:\xrs\fpgaexpress\rsenc_wrap.vhd. Click Open. The rs_encoder.exp window should pop up and rsenc_wrap.vhd should have a green tick next to it in the Design Sources section. Expand rsenc_wrap.vhd by double-clicking on it. Right-click on rsenc_wrap and select Create Implementation... In the Create Implementation window, complete the fields so that they match the following: Click OK. In the Chips section of the rs_encoder.exp window, there should be a red exclamation mark over rsenc_wrap. The associated warnings can be safely ignored as they are caused by the core being a black box component within rsenc_wrap.vhd. Right-click on rsenc_wrap-Optimized and select Export netlist... In the Export Netlist window, complete the fields so that they match the following: Click OK, then exit FPGAExpress. The EDIF wrapper rsenc_wrap.edf and the constraints file rsenc_wrap.ncf should be in the C:\xrs\fpgaexpress\rs_encoder directory.

Implementation

We're now ready to push the design through the Xilinx implementation tools. To save time, you will use the command-line approach rather than the Design Manager. First of all open a DOS command prompt window and, move to the appropriate directory: cd C:\xrs\implementation\rs_encoder The EDIF netlists for the core and wrapper should be copied to this directory: copy C:\xrs\unzipped\rs_encoder\rse.edn . copy C:\xrs\fpgaexpress\rs_encoder\rsenc_wrap.edf . The user constraints file generated by FPGAExpress should also be copied to this directory. However, it's extension must be changed to .ucf using the following command: copy C:\xrs\fpgaexpress\rs_encoder\rsenc_wrap.ncf rsenc_wrap.ucf FPGAExpress did not add a register-to-register timespec to rsenc_wrap.ucf because there are no registers within rsenc_wrap.vhd. Therefore you have to manually add the following timespec to rsenc_wrap.ucf: TIMESPEC TS_F2F = FROM FFS TO FFS 20 ns; Note that the TS_P2P timespec will be ignored by the implementation tools as there are no direct pad-to-pad boolean paths.

This directory should have the following files: go_map.bat go_par.bat go_trace.bat go_hdl.bat go_map go_par go_trace go_hdl rse.edn rsenc_wrap.edf rsenc_wrap.ucf At the DOS prompt, run the script files in the following order: go_map.bat go_par.bat go_trace.bat go_hdl.bat (Unix users should use the go_* scripts without the ".bat" extensions.)

Check the rsenc_routed.twr file. Did the place-and-route tools meet the timing constraints you set? View the core with FPGAEditor using the following command at the DOS prompt: fpga_editor rsenc_routed Notice that the core is a relationally placed macro (RPM).

Simulation

To illustrate how the Reed-Solomon encoder works, we will use a testbench that encodes a graphic image (pretend it has come from the digital still camera!) using an instantiation of the encoder. The testbench also adds pseudo-random noise to the encoded image to model the effects of a noisy transmission channel. In Tutorial 2, we will use an instantiation of the Reed-Solomon decoder to decode the corrupted version of the encoded image.

The testbench supports images stored in Portable Gray Map (pgm) format. The PGM format is used because it has a simple structure. A PGM file begins with a header which includes: a magic number to define the PGM flavor (ASCII, raw, gray, color), the width and height of the image, the maximum gray level value a pixel can have (0 is black, maximum value is white). The rest of the file is a stream of values representing the gray level of each pixel. These values can be in ASCII or raw format. The testbench supports the ASCII format because it is easier to process using the predefined package textio in the std library, where the file read and write commands are line-based (see Ref[1]). The ASCII format also permits an arbitrary number of gray level values whereas the raw format is limited to a maximum of 256 (because each pixel value is stored as a byte). Here is an example of a simple ASCII pgm file: P2                 - Magic number for ASCII format # test.pgm         - Comment 4 4                - Width and height 15                 - Maximum gray level value  0  1  2  3        - Pixel gray level values for row 1 of image  4  5  6  7        - row 2  8  9 10 11        - row 3 12 13 14 15        - row 4 Here is what it would look like when viewed (magnified) with an image viewing package such as LViewPro:

Launch LViewPro (or another graphics tool that can read pgm files) to view the image you will actually encode: C:\xrs\modelsim\input.pgm Note that for this tutorial, the image width of input.pgm is tailored to match the encoder's  k value. Also remember that the testbench has been configured to encode the image rather than the pgm file itself. This means that the header information at the start of the pgm files is not passed through the encoder, only the pixel data is. This ensures that the pgm files generated by the testbench can be viewed at the various stages of the encoding, transmission, and decoding.

Before we simulate the design, we need to copy across some source files. Launch a DOS-prompt, then go to the modelsim directory: cd C:\xrs\modelsim Copy the encoder behavioral model that was extracted from the zip file you received via email: copy C:\xrs\unzipped\rs_encoder\rs_encoder.vhd . Copy the structural VHDL netlist and SDF files that were generated by ngd2vhdl in the go_hdl.bat script: copy C:\xrs\implementation\rs_encoder\rsenc_routed.vhd . copy C:\xrs\implementation\rs_encoder\rsenc_routed.sdf . Launch Modelsim. At the Modelsim command prompt, change to the modelsim directory: cd C:/xrs/modelsim  [NOTE: Use forward slashes] Back-annotated simulation requires a simprim library. If you have installed Foundation onto your C: drive, type the following commands at the Modelsim prompt to compile the simprim library: vlib simprim vcom -87 -work simprim C:/fndtn/vhdl/src/simprims/simprim_Vcomponents.vhd vcom -87 -work simprim C:/fndtn/vhdl/src/simprims/simprim_Vpackage.vhd vcom -87 -work simprim C:/fndtn/vhdl/src/simprims/simprim_VITAL.vhd If you have installed Foundation in a different place, or use the Alliance tools, adjust the above paths accordingly.

At the Modelsim command prompt, type the following command to compile the necessary source files: do vcom_tutorial1.do This "do" script includes the following commands: vlib work -- -- compile structural model -- vcom -87 -work work rsenc_routed.vhd -- -- compile VHDL behavioral model -- vcom -87 -work work rs_encoder.vhd -- -- compile utility packages required by testbench -- vcom -87 -work work utils_pkg.vhd vcom -87 -work work pgm_pkg.vhd vcom -87 -work work random.vhd -- -- compile testbench -- vcom -87 -work work tb_rs_encoder.vhd All the source files should have compiled without any errors. The testbench (tb_rs_encoder.vhd) has a generic called num_errors. This can be used to add a specified number of pseudo-random errors to each code block, thus modelling (in a simplistic manner), the effects of a noisy transmission channel. Remember that the error-correcting capability of a Reed-Solomon code is t = (n - k)/2. So in order to give the decoder a tough time in Tutorial 2, set num_errors to 10 using the following command (all one line): vsim -sdfmax tb_rs_encoder/structural_gen/encoder1=rsenc_routed.sdf      tb_rs_encoder_config -Gnum_errors=10 Add the core signals to the Wave window using the following command: add wave reset clk enable bypass start data_in data_out info Use the following steps to set the radix for bus signals: In the Modelsim command prompt window, select Options->Simulation... In the Defaults tab, select Unsigned as the Default Radix. Click OK. Start the simulation using: run 300 ns Look at the signal waveforms in the Wave window. Scroll back to the start of the simulation, and zoom in so that the values on data_in and data_out are visible.

The symbol on data_in is sampled on the last rising edge of clk when start is asserted. Use cursors to measure the time from when the first symbol is sampled on data_in to when it first appears on data_out.

Q6. What is the clock cycle latency of the core?

Answer : __________

The testbench uses a clock period of 20 ns.

Q7. Looking at the start and info waveforms, and assuming enable is always asserted and bypass is never asserted, estimate when you would expect the first group of check symbols to start appearing on data_out?

Answer : __________

Continue the simulation to just beyond your estimation. Were you correct?

So that we can compare the simulation times for the structural and behavioral model simulations, restart the simulation and take a note of the time (real not simulation!) before you start the following run command: restart -f run -all This might be a good time to take a quick coffee break! The simulation should stop automatically once the whole image has been encoded.

Q8. How long did it take?

Answer : __________

When the simulation is complete the testbench creates three new pgm files in the modelsim directory: encoded.pgm noise.pgm received.pgm View these files using LViewPro. Note that the check symbols are appended to the end of each row in encoded.pgm. The received.pgm file is the result of XOR-ing the bits of each pixel in encoded.pgm with the bits of the corresponding pixel in noise.pgm.

Using the behavioral model

The above simulation used the back-annotated netlist model for the core. To use the behavioral model, re-run the simulation using the following commands, where use_behavioral_model is another testbench generic (which is false by default): vsim tb_rs_encoder_config -Guse_behavioral_model=true -Gnum_errors=10 add wave * run -all

Q9. How long did it take to encode the image using the behavioral model?

Answer : __________

Click here to view the answers for all the questions in this tutorial.

End of Tutorial 1!

By now you should know how to: specify all the Code-Block parameters for the Xilinx Reed-Solomon LogiCOREs generate a customized encoder core using the web-based configuration and download pages push the core through the Xilinx implementation tools simulate the core (using back-annotated netlist and behavioral models) In Tutorial 2 you will use an instantiation of the Xilinx Reed-Solomon decoder to remove the noise from the image contained in received.pgm.

Further reading

[1] P. J. Ashenden. "The designer's guide to VHDL". Section 18.2. Morgan Kaufmann Publishers, Inc., 1995. (ISBN 1-55860-270-4)

[2] S. Lin and D. J. Costello. "Error control coding: fundamentals and applications". Prentice-Hall, 1983. (ISBN 0-13-283796-X)

[3] S. B. Wicker and V. K. Bhargava (editors). "Reed-Solomon codes and their applications". IEEE Communications Society and IEEE Information Theory Society, 1994. (ISBN 0-7803-1025-X)

Back to Xilinx Reed-Solomon Solution page