Reed-Solomon Decoder May 2003 IP Data Sheet Features General Description Forward Error Correction (FEC) for Communication and Common Applications Reed-Solomon codes are used to perform Forward Error Correction. FEC encoders introduce redundancy in data before it is transmitted. The redundant data (check symbols) are transmitted along with the original data through the channel. A Reed-Solomon decoder at the receiver is used to recover any corrupted data. This type of error correction is widely used in data communications applications such as hard disk and media storage (CD) systems, Digital Video Broadcast (DVB) and Optical Carriers (e.g. OC-192). Selectable Reed-Solomon Standards * CCSDS (255,223) - Consultative Committee for Space Data Systems * ATSC (207,187) - Advanced Television Systems Committee * DVB (204,188) - Digital Video Broadcasting * OC-192 (255,239) - Optical Carrier Shortened Codes Supported The codes are represented by the format RS(n,k) where n is the total number of s-bit wide symbols, and k is the number of s-bit wide information (data) symbols in a codeword. The Reed-Solomon Decoder performs detection and correction of encoded data available at the receiver after demodulation. The RS encoded data is then processed to determine whether any errors have occurred during transmission. Once the number of errors is determined, the decoder decides if they are within the range of correction. After determining this, the decoder corrects the errors in the received data. A typical application of space signal processing is shown in Figure 2. Errors/Erasures Supported Supports Symbol Widths From 3 to 12 Bits, Corresponding to GF(8) to GF(4096) Respectively User-Defined and Default Field and Generator Polynomials Supported Error Measurement Information Block Diagram Figure 1. Reed-Solomon Decoder Block Diagram Control Bus Error Magnitude Corrector Syndrome Transform d_in Key Equation Solver Error Locator Output Processing Unit d_out ram ready clk err_fnd rst_b Control blk_start sync blk_end (c) 2003 Lattice Semiconductor Corp. All Lattice trademarks, registered trademarks, patents, and disclaimers are as listed at www.latticesemi.com/legal. All other brand or product names are trademarks or registered trademarks of their respective holders. The specifications and information herein are subject to change without notice. The product described herein is subject to continuing development, and applicable specifications and information are subject to change without notice. Such specifications and information are provided in good faith; actual performance is not guaranteed, as it is dependent on many factors, including the user's system design. www.latticesemi.com 1 ip1017_03 Lattice Semiconductor Reed-Solomon Decoder Figure 2. Application of Reed-Solomon Code in a Space Communication System Data Bits Decoded Bits RS Encoder Interleaver Convolutional Encoder RS Decoder Deinterleaver Viterbi Decoder Transmit Data Receive Data A Reed-Solomon Decoder can correct errors and erasures. The maximum number of correctable erroneous symbols in a codeword is t = (n-k)/2, and the maximum number of correctable erasures in a codeword is = n-k. Reed-Solomon codes are based on finite field arithmetic, also known as Galois Field. The size of the field is determined by the width s of the information symbol, and the field has 2s elements. When n is less than the maximum value of 2s -1, the code is called a shortened code. Reed-Solomon codes are characterized by two polynomials: the field polynomial and the generator polynomial. The field polynomial defines the Galois Field to which the information and check symbols belong. The generator polynomial determines the check symbol generation, and is a prime polynomial for all codewords (i.e. all codewords are exactly divisible by the generator polynomial). Both the field and generator polynomials are user configurable. Field Polynomial The field polynomial can be specified as any prime polynomial up to 2s+1 - 1. The field polynomial is defined by its decimal value (f). The decimal value of a field polynomial is determined by setting x = 2 in the polynomial and calculating the result. For example, the polynomial x2 + x + 1 in decimal value is 22 + 2 + 1 = 7. Generator Polynomial The generator polynomial determines the value of the check symbols. The starting root (gstart) and root spacing (rootspace) variables define the generator polynomial. The general form of the generator polynomial is: n-k-1 g(x) = (x - rootspace * (gstart + i)) (1) i=0 Shortened Codes A shortened code has a lesser number of total symbols than the maximum possible for the given symbol width. An example of a shortened code would be, RS(204,188) where s = 8. Functional Description The data received by the RS Decoder is Reed-Solomon encoded data. This data is a representation of a polynomial in a Galois Field. If there are no errors in the received data, the data polynomial will evaluate to zero at the roots of the generator polynomial. This result is obtained because the roots of the generator polynomial and received data polynomial are the same when no errors are present. If the received data has been corrupted during the transmission, the polynomial will not evaluate to zero. The RS Decoder can construct the syndrome polynomial by evaluating the received polynomial at all the roots of the generator polynomial. Once the syndrome polynomial has been constructed, it can be used to solve the Error Locator polynomial and Error Evaluator polynomial. Using these two polynomials, the decoder can find the error locations and magnitudes. Finally, the decoder can correct the errors in the received data, provided the errors are in the range of possible correction (determined by the level of encoding that has been performed). 2 Lattice Semiconductor Reed-Solomon Decoder If there are errors in the received codeword, it can be expressed as follows: r(x) = c(x) + e(x) where: * c(x) is the Transmitted codeword. * r(x) is the Received codeword. * e(x) is the Error polynomial. The syndrome polynomial S(x) is obtained by evaluating the received word at each root of the generator polynomial. The Error Locator polynomial (x) is orthogonal to the syndrome polynomial in the Galois field. This can be represented as: S(x) (x) = (x) mod x2t where: * (x) is the Error Evaluator polynomial. * 2t is the number of check symbols introduced by the decoder. The following sections describe the function of each block of the RS Decoder. Syndrome Transform The Syndrome Transform (also called Syndrome Generation) block evaluates the received codeword of the generator polynomial. If the received data contains an error, the syndrome polynomial generated will be non-zero. If the received data has no error, the syndrome polynomial is zero, and the data is passed out of the decoder without any error correction. Key Equation Solver This is the heart of the Reed-Solomon Decoder. This block generates the Error Locator polynomial (x) (also known as the "Key Equation" as it is the key to solve the decoding problem). After the Error Locator polynomial has been found, it is used to determine the Error Evaluator polynomial (x). Error Locator This block is implemented using the Chien-search method. Essentially, this method evaluates the Error Locator polynomial at all the elements in the Galois Field. The Error Locator polynomial evaluates to zero at its roots. The Chien-search takes m cycles, where m is the number of elements in the Galois Field. After m cycles, all roots have been determined. If the roots are determined before the m cycles are over, the search is terminated early. Error Magnitude Corrector Once the location of the error has been determined, the Error Magnitude Corrector evaluates the evaluator polynomial at the root. It uses the result to calculate the value of the error at the given location. Once this has been determined, the value is added to the received word to recover the corrected data. The addition occurs after the Error Locator evaluates to zero. Control Circuit The control circuit handles the interface, pipelining and handshaking communication between the various blocks and the I/O pins. The control circuit moves the data without processing it through the decoder when no error is detected. Similarly, when the number of errors exceeds the maximum range of correction, the control circuit stops all data processing activities. The control circuit interacts with the other blocks to generate the status signals like fail, err_fnd, err_cnt, ers_cnt and other handshaking signals. Once the block has been processed, the control circuit sends out the ready signal to the output to start the processing of the next data. 3 Lattice Semiconductor Reed-Solomon Decoder Parameter Descriptions Table 1 lists the parameters used for configuring the RS Decoder. The values of these parameters are set prior to synthesis. Table 1. RS Decoder Parameters Parameter Description Value n The total number of symbols in the code word. 3 - 4095 wsymb Width of input data d_in in bits. Ranges from 3 to 12 bits. The size of d_out equals the size of d_in. k Indicates the number of data symbols in the code. 1 - 4093 rootspace Indicates space between the roots of the generator polynomial. 1 - 65535 3 - 12 gstart Offset value of the generator polynomial. The starting value for the first root of the generator polynomial is calculated as rootspace * gstart. 0 - 65535 fpoly Field polynomial. This must be a valid finite field polynomial in the Galois field GF(2n). The default value is used if fpoly is not specified. 11 - 8191 Type of the RS Decoder core. It can be one of the following optimized types: CCSDS, ATSC, DVB or OC192 or it can be a custom configuration. The details of the different core types are listed below: * Hard coded parameters for CCSDS mode will be used to derive the decoder if this option is selected. Coretype = ccsds, wsymb = 8, n = 255, k = 223, gstart = 112, rootspace = 11, fpoly = 391, Numerasrs = 0 Coretype * Hard coded parameters for ATSC mode will be used to derive the decoder if this option is selected. Coretype = atsc, wsymb = 8, n = 207, k = 187, gstart = 0, rootspace = 1, fpoly = 285, Numerasrs = 0 * Hard coded parameters for DVB mode will be used to derive the decoder if this option is selected. Coretype = dvb, wsymb = 8, n = 204, k = 188, gstart = 0, rootspace = 1, fpoly = 285, Numerasrs = 0 OC192, CCSDS, ATSC, DVB or Custom * Hard coded parameters for OC192 mode will be used to derive the decoder if this option is selected. Coretype = oc192, wsymb = 8, n = 255, k = 239, gstart = 0, rootspace = 1, fpoly = 285, Numerasrs = 0 * When the parameter coretype is defined as custom, the parameter values can be individually selected by the user in the IP Manager tool. Numerasrs Number of erasures. 0 - 4088 4 Lattice Semiconductor Reed-Solomon Decoder Signal Descriptions Table 2. RS Decoder Signal Descriptions Port Name I/O Active State Signal Description rst_b Input Low Asynchronous reset. This resets all the flip-flops in the core and initializes the decoder. It has the highest priority. sync Input High Used to indicate the data boundaries for the block. It has two functions that can be selected as a parameter: (1) Pulse is high for first data and low for the rest. (2) DataEn is high for data symbols and low for the check symbols. Required Signals clk Input N/A System clock. d_in[wsymb-1:0] Input N/A Input data bus. The bus width is set by the symbol width parameter. Every symbol is sampled at the rising edge of the clock only after the sync pin has been asserted. A copy of each symbol can be passed directly (without processing) to d_del, if it exists. blk_start Output High Asserted for one clock cycle to indicate the first decoded symbol on the output d_out. blk_end Output HIgh Asserted for one clock cycle to indicate the last decoded symbol on the output d_out. ready Output High Asserted whenever the decoder is ready to sample input data from the next block. It is de-asserted to prevent any input sampling when the decoder is still processing the previous block. d_out[wsymb-1:0] Output N/A Output data bus. Corrected data is presented on d_out one symbol at a time after processing. If the decoding has failed, a copy of the original input data block will be presented at d_out, and the fail pin will be asserted, if it exists. Optional Signals (for custom core types, these optional signals can be selected or deselected in the IP Manager tool) ce Input High Clock Enable. While this is de-asserted, the decoder will ignore all other synchronous inputs and maintain its current state. Available only when Clock Enable is selected during core generation. sr Input High Synchronous reset. Asserted for at least one symbol duration in order to reinitialize the decoder state. Input data symbols sampled before sr is asserted are given unprocessed at the output. Available only when Sync Reset is selected during core generation. ers Input High Erasure. Asserted to indicate the input data symbol at the d_in pin is erased. Only available when Erase Count is selected during core generation. fail Output High Fail Indicator. Asserted through the duration of output data block to indicate that the block has more errors than the decoder can correct. Exists only when Fail is selected during core generation. err_fnd Output High Error Found Indicator. Asserted through the duration of the output data block when the block has at least one symbol in error. It is low otherwise. Exists only when Error Count is selected during core generation. d_del[wsymb-1:0] Output N/A Uncorrected Data Output. A delayed copy of the input data block. Data is presented on d_del concurrently with the decoded block on d_out. Exists only when Delayed Data is selected during core generation. err_cnt[wsymb-1:0] Output N/A Error Counter. Provides the number of corrected errors in the most recent output block. The bus width of err_cnt is equal to the number of bits required to represent the maximum possible number of correctable errors. Exists only when Error Count is selected during core generation. ers_cnt[wsymb-1:0] Output N/A Erasure Counter. Provides a count of the number of erasures fed into the decoder in the most recent input data block. The bus width of ers_cnt is equal to the number of bits required to represent the maximum possible number of correctable errors. Exists only when Erase Count is selected during core generation. 5 Lattice Semiconductor Reed-Solomon Decoder Timing Diagrams Every symbol of the RS Decoder is sampled at the rising edge of the clock when sync pin is asserted. There are two behaviors of the sync pin: * Start Pulse. The sync pin is asserted for one symbol duration to indicate the start of the input data block. * Data Symbol Enable. The sync pin is asserted for k-symbol duration from the start of the input data block, during which the information symbols are sampled in. Figure 3 shows the I/O signal's status after rst_b is asserted at the beginning of the block. During the decoding process, the ready and sync signals are asserted HIGH to indicate the start of the decoding process. In order to output the decoded data, blk_start is asserted for one clock cycle to indicate that the first decoded symbol is currently at the d_out pin. The pin blk_end is asserted for one clock cycle to indicate the last decoded symbol is currently at the d_out pin. Figure 3. I/O Signal Status of RS Decoder clk rst_b ready sync CI0 CI1 CI2 CIn-3 CIn-2 CIn-1 d_out AO0 AO1 AO2 AOn-3 AOn-2AOn-1 d_del AI0 AI1 AI2 AIn-3 AIn-2 AIn-1 d_in AI0 AI1 AI2 AIn-3 AIn-2 AIn-1 BI0 BI1 BI2 BIn-3 BIn-2 BIn-1 blk_start blk_end err_fnd err_cnt 0000 0010 Figure 4 illustrates the output status when sr is asserted. When sr is asserted during the decoding process, it reinitializes the decoder state. It forces the data at d_in to be output to d_out without correction. 6 Lattice Semiconductor Reed-Solomon Decoder Figure 4. Effect of Synchronous Reset on the Output Data from the Decoder clk rst_b sr ready sync CI0 CI1 CI2 CIn-3 CIn-2 CIn-1 d_out AI0 AI1 AI2 AIn-3 AIn-2 AIn-1 d_del AI0 AI1 AI2 AIn-3 AIn-2 AIn-1 d_in AI0 AI1 AI2 AIn-3 AIn-2 AIn-1 BI0 BI1 BIn-3 BIn-2 BIn-1 BI2 blk_start blk_end Figure 5 illustrates the effect of clock enable (ce) on the output data from RS Decoder. The decoder ignores all other synchronous inputs and remains in its current state when ce is de-asserted. When ce is asserted, the decoder goes back to the normal decoding process. In the figure, the data DX at d_in (that occurs during ce going low) is not recognized by the decoder. Figure 5. Effect of Clock Enable on the Output Data from Decoder clk rst_b ce ready sync d_in AI0 AI1 AI2 AIn-3 AIn-2 AIn-1 BI0 BI1 BI2 BIn-3 BIn-2 BIn-1 CI0 DX CI1 CI2 CIn-3 CIn-2 CIn-1 d_out AO0 AO1 AO2 AOn-3 AOn-2 AOn-1 d_del AI0 AI1 AI2 AIn-3 AIn-2 AIn-1 blk_start blk_end err_fnd err_cnt 0000 7 0010 Lattice Semiconductor Reed-Solomon Decoder Custom Core Configurations For custom Reed-Solomon Decoder core configurations not available in the Evaluation Package, please contact your Lattice sales office. Related Information For more information regarding core usage and design verification, refer to the Reed-Solomon Decoder User's Guide available on the Lattice web site at www.latticesemi.com. 8 Lattice Semiconductor Reed-Solomon Decoder Appendix for ORCA(R) Series 4 FPGAs or FPSCs Table 3. Performance and Resource Utilization1 Mode ORCA 4 PFUs2 LUTs Registers sysMEM EBR fMAX (MHz) External Pins reeds_deco_o4_1_001.lpc OC192 321 1595 918 2 83 35 reeds_deco_o4_1_002.lpc CCSDS 621 2627 1565 2 76 36 reeds_deco_o4_1_003.lpc DVB 330 1764 911 2 85 35 reeds_deco_o4_1_004.lpc ATSC 423 2139 1072 2 84 35 Parameter File 1. Performance and utilization characteristics are generated using an OR4E042BA352. When using this IP core in different density, package, speed, or grade within ORCA Series 4 family, performance may vary slightly. 2. PFU is a standard logic block of some Lattice devices. For more information, check the data sheet of the device. Supplied Netlist Configurations The Ordering Part Number (OPN) for all configurations of this core for use with ORCA Series 4 FPGAs is REEDSDECO-O4-N1. Table 4 lists the Lattice-specific netlists available in the Evaluation Package, which can be downloaded from the Lattice web site at www.latticesemi.com. Table 4. Core Configurations Configurations Number Parameter CCSDS DVB ATSC OC192 1 wsymb 8 8 8 8 2 n 255 204 207 255 3 k 223 188 187 239 4 rootspace 11 1 1 1 5 fpoly 391 285 285 285 6 gstart 112 0 0 0 7 Numerasrs 0 0 0 0 8 Coretype ccsds dvb atsc oc192 To load the preset parameters for this core, click on the "Load Parameters" button inside the IP Manager tool (included with the ispLEVER design tool). Make sure you select the correct directory location for the ReedSolomon Decoder. The Lattice Parameter Configuration files (*.lpc) are located within this directory. 9 Lattice Semiconductor Reed-Solomon Decoder Appendix for ispXPGATM FPGAs Table 5. Performance and Resource Utilization1 Mode ispXPGA PFUs2 LUTs Registers sysMEM EBR fMAX (MHz) External Pins reeds_deco_xp_1_001.lpc OC192 571 2034 1033 2 83 35 reeds_deco_xp_1_002.lpc CCSDS 1011 3660 1717 2 76 36 reeds_deco_xp_1_003.lpc DVB 586 2089 1049 2 84 35 reeds_deco_xp_1_004.lpc ATSC 712 2536 1286 2 80 35 Parameter File 1. Performance and Utilization characteristics are generated using LFX500B-04F516C. When using this IP core in different density, package, speed, or grade within the ispXPGA family, performance may vary slightly. 2. PFU is a standard logic block of some Lattice devices. For more information, refer to the data sheet of the device. Supplied Netlist Configurations The Ordering Part Number (OPN) for all configurations of this core for use with ispXPGA devices is REEDSDECO-XP-N1. Table 6 lists the Lattice-specific netlists that are available in the Evaluation Package, which can be downloaded from the Lattice web site at www.latticesemi.com. Table 6. Core Configurations Configurations Number Parameter CCSDS DVB ATSC OC192 1 wsymb 8 8 8 8 2 n 255 204 207 255 3 k 223 188 187 239 4 rootspace 11 1 1 1 5 fpoly 391 285 285 285 6 gstart 112 0 0 0 7 Numerasrs 0 0 0 0 8 Coretype ccsds dvb atsc oc192 To load the preset parameters for this core, click on the "Load Parameters" button inside the IP Manager tool. Make sure you navigate to the Reed-Solomon Decoder core's directory location. The Lattice Parameter Configuration files (*.lpc) are located within this directory. 10