Error Control Coding Functions in Programmable Logic

By Tapan A. Mehta, Senior Product Marketing Engineer, Altera Corporation (tmetha@altera.com)

1.0 Introduction
Programmable Logic is ideal for implementing error control coding (ECC) functions for two main reasons. First, PLDs are inherently flexible, easing the modification of coding methods and improving algorithms. Second, the performance and density of PLDs align optimally with industry requirements. Unlike Application Specific Standard Products (ASSPs) designed specifically for ECC, programmable logic devices offer the designers the speed of hardware and the flexibility of software while implementing ECC functions.

ECC is a methodology that detects and in some cases corrects errors induced in digital data during transmission over a noisy channel (digital video/audio broadcast, satellite communications) or during storage in an unreliable medium (compact disc, digital tape). Some of the common ECC functions ideally suited for programmable logic are Reed-Solomon, Viterbi, Trellis Coded Modulation (TCM), etc. The Altera Megafunction Partners Program (AMPP), an alliance between Altera and developers of synthesizable functions, brings the advantages of design resuse to users of Altera PLDs. This article primarily focuses on the implementation of Reed-Solomon and Viterbi solutions optimized for programmable logic.

2.0 Traditional vs. Contemporary Ways of Implementing ECC Functions
ECC functions like Reed-Solomon, Viterbi, etc. have traditionally been implemented in Application Specific Standard Products (ASSPs) or ASICs only. Some of the commonly used dedicated solutions are from either LSI Logic or from Advanced Hardware Architectures (AHA). Many of these are available as either separate encoders or decoders, or sometimes together in one package.

In the past, ASSPs and ASICs had significant price and performance advantages over PLDs. Additionally, programmable devices several years ago didn't meet the density, performance, and price requirements, which are the key elements necessary for the implementation of ECC functions. Improvements in both programmable logic architecture and process technology have allowed companies like Altera Corporation to produce new devices which today are on par, and in most cases, better solutions for the implementation of ECC functions.

Programmable devices several years ago were often priced on a per - gate basis at about 50 gates/dollar. Currently Altera devices have reached the 1000 - gates/dollar threshold and should reach the 5000 - gates/dollar threshold by the end of this year. This high level of integration has allowed complex functions such as the RS codecs discussed in this paper to be implemented cost-effectively in programmable logic such as Altera FLEX device families. As an example, the DVB encoder that uses 199 logic cells can be implemented in less than 25% of an Altera EPF6016A device leaving over 1000 logic cells available for complementary functions. This device is currently less than $20 and is planned to be less than $10 in quantity by end of 1998, certainly competitive with the price of dedicated devices.

Regarding performance, the same improvements that have driven the cost of programmable logic down have greatly increased performance as well. Process migrations along with improvements in device architecture and synthesis tools have allowed designs that could only run at 20MHz several years ago to run at well over 60MHz today. This means that as new devices become available that are even faster, the core can be placed in these new devices to increase the performance of the design. The RS cores vary in performance based upon the targeted code, but DVB encoders at 88MHz and decoders at 22 MHz make programmable logic a viable solution for all but the highest end needs.

3.0 Reed-Solomon Codec in Programmable Logic

Figure 1: Reed-Solomon System Level Block Diagram

The above figure shows a typical Reed-Solomon block diagram. As one can see, the original data, which is a block consisting of N-R symbols, is run though a Reed-Solomon encoder and R check symbols are added to form a codeword of length N. Since Reed-Solomon can be done on any message length and can add any number of check symbols, a particular Reed-Solomon code will be expressed as a RS(N,N-R) code. N, as shown above, is the total number of symbols per codeword, R is the number of check symbols per codeword, and therefore N-R is the number of actual information symbols per codeword. An example of a RS codeword is shown in Figure 2.

Figure 2: Reed- Solomon Codeword

As an example, the Digital Video Broadcast (DVB) specification uses an RS(204,188) code, utilizing 16 check symbols per 188 information symbols for a total codeword length of 204 symbols.

Assuming the decision has been made to use a RS function and incorporate it into a PLD, the exact system requirements must then be determined. In our case, this would mean knowing what RS code is to be implemented (number of total symbols per codeword, number of check symbols per codeword), and values such as the field polynomial, generator polynomial, and the number of bits per symbol. Once these values are known (many common implementations such as the DVB or Intelsat examples define all of these values as part of the specification), the appropriate encoder or decoder can be built.

Examples of the performances and device utilization achieved for DVB i.e. RS (204,188) and Intelsat i.e. RS (255, 245) functions are shown in the table below.

Function	Device Utilization		Performance	Device
	LCells	EABs*
Reed-Solomon Encoder (204, 188)	199	0	88 MHz	EPF10K30A ý1
Reed-Solomon Decoder (204, 188)	1605	6	40MHz	EPF10K30A ý1
Reed-Solomon Encoder (255, 245)	201	0	26 MHz	EPF10K30A ý1
Reed-Solomon Decoder (255, 245)	1942	5	35 MHz	EPF10K30A ý1

*Note: Embedded Array Blocks

Table 1: Reed Solomon Encoder and Decoder Performance and Device Utilization for various RS Codes

As seen from Table 1, RS decoding is a far more complex operation than encoding. This is clearly illustrated by the number of logic cells and EABs used in implementing RS decoding versus RS encoding.

The EAB is a flexible block of RAM with registers on the input and output ports, and is ideal for implementing error correction circuits, because it is large and flexible. The EAB provides advantages over FPGAs, which implement on-board RAM as arrays of small, distributed RAM blocks. These FPGA RAM blocks contain delays that are less predictable as the size of the RAM increases. In addition, FPGA RAM blocks are prone to routing problems because small blocks of RAM must be connected together to make larger blocks. In contrast, EABs can be used to implement large, dedicated blocks of RAM that eliminate these timing and routing concerns. Altera FLEX 10K device contains EABs, which makes them ideal solutions for implementing ECC functions like Reed-Solomon.

4.0 Viterbi Functions in Programmable Logic
Unlike Reed-Solomon which works on block codes, the Convolutional Encoder, Convolutional Interleaver and Viterbi decoder works on convolutional codes. The basic idea of convolutional coding is that when data is sent, the encoder adds bits to the data to be transmitted. The encoding rate is normally 1/2 or 1/3; i.e. each transmitted bit is encoded to 2 or 3 bits. The transmitted bit is dependent on bits sent earlier.

The Convolutional Encoder function can be configured to use bit rate or symbol rate clocks, to accept the data in bit serial or symbol serial format, and to support a range of international standards.

The Convolutional Interleaver is responsible for reducing the number of burst errors. It helps to distribute the errors evenly over a code, which in turn facilitates in detecting and correcting the induced errors.

The Viterbi Decoder is one of the key elements used in detecting and correcting errors in a digital transmission, since the incoming erroneous data will go through the Viterbi decoder. The Viterbi decoder finds the most likely path of the incoming data. The path is calculated so that the data is compared to the data in a branch metric table (this table shows the allowed data symbols, and is dependent on the encoder), and the error between received symbol and the symbol in table is calculated. The path with the smallest error is selected. The Viterbi Decoder has several features as described below which plays an important role in detecting and correcting errors in a digital transmission.

4.1 Viterbi Decoder Features:

• Hard Decision Decoder   This means that the incoming data symbol will be '0' or '1', i.e. there are two quantization levels in A/D converter (normally the received data is analog, and it will be converted to digital). In a soft decision Viterbi decoder there are more than two quantization levels.
• Trace-back method for survivor memory
    This is the method to select the smallest path. Trace-back method means that all the possible paths are stored in RAM, and this method selects the most likely path.
• Branch Metrics computations can be added for different applications
    Branch metric computation makes the error calculation between the received symbol (2 or 3 bits) and the symbol in the table. In hard-decision Viterbi, the Hamming distance is calculated.

So, a Viterbi decoder has three parts:
- Branch Metric Computation
- ACS ( Add-Compare-Select)
- Survivor memory control

Branch metric computation calculates the error, ACS selects the smaller error of two possible paths, and stores it into memory, and Survivor memory control selects the path from memory by using trace-back method, and gives the decoded bit out.

Parameterized architecture of the Viterbi decoder available through the AMPP program, allows for user customization of the following functions:

- Number of states in the trellis
- Number of bits to represent transition values
- Add-Compare-Select (ACS) cells
  The number of ACS cells can be changed. The more ACS cells are used, the faster the decoding rate, which in turn results in a larger block size.
- The length of the trace-back
  Defines the decision length of the received data, i.e. how many earlier symbols must be taken into account when decoding the current symbol.
- The length of the received burst
  This Viterbi decoder is designed to decode bursts of data, and this parameter defines the length of the burst.
- The initial path metric for state 0
  This defines the default path metric when decoder starts decoding the burst.
- The survivor memory (RAM) word length
  This defines the word length of RAM that is used in Viterbi decoder.

Table 2 below outlines the performance and device utilization for various ECC functions used for convolutional codes.

Function	Device Utilization		Performance	Device
	LCells	EABs*
Convolutional Encoder	39	0	120MHz	EPF10K50-3
Convolutional Interleaver	252	0	52 MHz	EPF10K30-3
Viterbi Decoder	960	0	31 MHz	EPF10K30A-1
	954	0	17 MHz	EPF6016-2

* Note: EABs ý Embedded Array Blocks

Table 2: Performance and Device Utilization for various ECC functions used for convolutional codes

5.0 Conclusion
With the increasing need for the transmission of digital data over a wide variety of mediums, the need for error control coding will increase significantly as well. Reed-Solomon and Viterbi coding provides a robust error control method for many common types of data transfer mediums, particular those that are one-way or that are noisy and sure to produce errors. Error Control Codes are already the standard for a large number of satellite transmission specifications as well as for compact disc technology. It is unlikely that the needs will decrease in our increasing technological society. The trend will continue. More information about ECC functions can be found on the Altera web site at http://www.altera.com.

Programmable logic also has a trend that will continue: bigger, faster, and cheaper. Even today it can be seen that for many large complex functions such as RS and Viterbi codes, programmable logic is not only a viable solution, but is the best solution. The huge strides that have been made in only the last five years can be expected to continue, with the ability to incorporate even larger and more complex functions into programmable logic at increased levels of performance. These larger, faster devices, combined with the increasing availability of intellectual property targeted at programmable logic, such as the functions evaluated in this paper, is a win not only for the PLD manufacturer and the designer, but also the end customer who should see increased performance at lower cost in the end item product as well.

Home | Product of the Week | Tech Note | AppReview | Vendor Tools | Feedback

		Click here to get your listing up.