Types Of Forward Error Correction

Error correcting codes are important in protecting transmitted data. In this paper we introduce the forward error correction (FECs) about the background of it — INTRODUCTION, how they works, explain the principles of forward error correcting codes (FECs) – Principles of FECs. And we also introduce the different types of FECs and how they work in internet and wireless communications – TYPES of FECs.

Index Terms-forward error correction (FECs), Error Correction Code, internet, wireless.

INTRODUCTION

Forward Error Correction code is a data code which is used in error control for data transmission. In FEC which using FECs, the receiver not only can catch transmission error, but also determine where the error happened by binary symbol and correct it.

Different from ARQ, FEC is applied to the relatively costly retransmissions. What’s more, in order to recover corrupted data, FEC information is usually added to mass storage devices. The advantage of forward error correction is that retransmission of data can often be avoided. Digital communication systems also use FEC to minimum SNR. When the channel errors tend to occur in bursts, FEC coded data can reduce the all or nothing properties of transmitted FEC codes. [1] But this advantage is based on the cost of higher bandwidth requirements on average, which means that FEC is applied in situations where retransmissions are relatively expensive or impossible.

2 PRINCIPLES of FECs

Forward error correction code (FECs) is a data codes which is used in FEC system for data transmission. Because of the FECs, the sender adds to its messages by using a predetermined algorithm, the receiver can detect and correct errors without asking the sender for additional data. Not all the errors can be corrected by the same design of the code, thus, various conditions need different FEC codes to match. Furthermore, many FEC algorithms can take analog data in, and put digital data out.

There are two basic ways to code, linear block code and cycle code. But they share the similar principle.

When we send k bits date and use linear block codes to correct it, the transmission system will reconstruct n bits code word by multiplied n*k generator matrix such that we can tolerate k-n losses. And when then receiver get the n bits code word, and multiplied the n bits code by HT matrix – n*(n-k) matrix composed by the unit matrix and arbitrary matrix. It will control the error and rectify the error by using the result of the last multiplied. Final, the decoder will reconstruct the date – like the picture.

To check large data we need lots of work. And consider about the strength and accuracy, the linear block codes are not easy to implement in hardware.

The cycle codes are easier to implement than linear block code by using shift registers. The sender multiplies the data by order of generator polynomial P(x) to create code word. And in receiver, it divides receive code by P(x) to get the syndrome and find where the error is. Then the decoder will reconstruct the date.

3 TYPES of FECs

Block codes and Convolution codes

The two main types of FECs are block codes and convolution codes. In this section, we will talk about the different bound of each of them and compare those advantages and disadvantage.

Block codes work on fixed length blocks of bits or symbols of predetermined size. It encode the data by multiple a complex matrix and in receiver, the decoder will reconstruct the data and correct the errors. There are many types of block codes such as BCH codes and Hamming codes.

Convolution codes work on bit or symbol streams, which have arbitrary length. In general, they are decoded with the Viterbi algorithm. While increasing constraint length of the convolution code, it allows asymptotically optimal decoding efficiency, it’s still at the expense of exponentially increasing complexity. [2] It encodes k bits information into n bits symbols. Because k and n is small, it is easy to transmission. Different from Block code, the n bits code work not only depend on the k bits date, but also depend on the forward symbols. Convolution codes are used in numerous applications such as digital video, radio, mobile communication, and satellite communication. It is high speed and efficient.

In another word, we can choose which types FECs can be used in our system by we need. But Reed-Solomon coding (RS) is the most widely used because it strange ability in error control. Now we introduce some types of FECs.

CRC:

Cyclic Redundancy Check is the most important of linear group codes and the most commonly used error checking code. Its information field and check the length of the field can be arbitrarily selected. A CRC is formed by date and check code. The senders code the source data and send the check code behind the data. And the receivers yet code the data via the same way and compare the check code with the result. The advantage of CRC is that it is easy to use in computer and digital components because it is formed by binary code. But the codes’ length is large and it takes more unwanted time and channels.

An example of using CRC code is the FPGAs (Field-Programmable Gate Array). During device operation, it can make continual verification of the CRAM contents feasible by using hard CRC checker. The CRC is guaranteed to detect multi-bit errors. Integrating CRC circuitry on-chip in hard gates has many benefits, for example, the circuitry is capable of performing without failure under a wide range of conditions and not susceptible to soft errors. Furthermore, the CRC circuit is a self-contained block and is enabled simply. [3]

BCH code and R-S code:

BCH code can check and correct multiple random errors in model multi-level, cycle, error correction, variable-length digital code. It is a non-binary codes.

Reed-Solomon is encompassed from BCH. It is made up of n symbols, and each of the symbols is m bits long. [4] After coding, it adds t check symbols to the data, and the decoder can use an R-S code to detect any errors of up to t symbols, and correct up to t/2 errors. It is more complex then simple of CRC and has strong error correction ability. It is widely used in mass data storage system such as DVD, e-Reader and some game systems to correct the burst errors. And the R-S code also can be use to overcome the unreliable condition of data transmissions. An application of R-S codes was to correct the data sent back by Voyager. It is significant that R-S code is used in satellite transmission. Because R-S code gains much bandwidth need to net transition, so we can’t use it in internet.

Turbo Code:

Turbo codes come from serial concatenated codes which based on an outer Reed-Solomon error correction code. Turbo Codes are well- performance FECs, which is the first practical code to closely approach the channel capacity. They combine a variety of ways of encoding and decoding. The encoders reconstruct the data into three parts -one m bits data and two n/2 bits code. And in receiver, two interconnected decoders are used to avoid error bursts.

There are two different type of Turbo Code — Turbo Convolution Code (TCC) and Block Turbo Code (BTC) [5]. One is base on Convolution code and the other is Block code.

The Turbo Convolution Code has greater correction ability than BTC and is widely used in wireless communication while Block Turbo Code shows better performance at high code rate and suits for optical communication systems.

4. FECs in WIRELESS and INTERNET

FECs in wireless

High-speed multimedia data transmission is vulnerable to burst errors primarily due to the structure. The quality of service (QoS) of a wireless network is largely dependent on the link stability and availability and the error probability. FECs minimize the effects of multipart fading to enhance the QoS by adding check code in the transmitted data.

And in all kinks of FECs, the R-S code has the most strong error correction ability. And R-S codes are effective in minimizing the irrecoverable system problems which are aroused by burst errors in high speed data traffic and reducing the bit error rate [6]. As a result, the wireless link is higher availability and E/N is dropped. So both in industry wireless net and wireless transmission, it is in widespread. And now in BWA, an R-S (204,188) has been put forward. It can diffuse a number of errors in one point to some small error. And the error will been corrected in decoder.

FECs in internet

FECs is applied in internet is a new development research problem in recently decennium. In internet, FECs adapt to complete more address transmission. First, people think about the R-S code because it reliability. And R-S code is easy to be decoded. But R-S code needs a complex math operation. In long data transmission, it will take too long time and it may tribute network traffic jam by using R-S code. So R-S code just using in short length date transmission. And now most use the Tornado code in internet.

Tornado code is a Low-density parity codes and constructed in a kind of non-formula picture. Spielman provide the Expander code in 1995 on the base of Low-density parity codes.[7] And in 1998, Byers J W, and Luby M put out the Tornado code on the base of it.[8] Tornado code can be coded in a linearity time. And it has a quickly spread speed than R-S code. This is the structure of Tornado code.

By using FECs, the speed of transmission in internet will be decreased with less retransmission. And FECs also can avoid the blocking and ensuring internet reliability when we transmit data in internet.

Comparing the application of FECs between in internet and wireless, we can get the conclusion. The wireless need higher QoS and can provide more bandwidth to transmit data. So we use R-S code or Turbo Convolution Code to enhance the availability of links to get high QoS. While in internet, R-S code will take more time in encoding and decoding and in internet retransmit isn’t cost a lot so we use Tornado instead or just use ARQ only.

5. CONCLUSION and REFLECTION

As FEC uses excess information to locate the errors and correct them without further communication with the sender, it is generally effective when there is a high degree of corre- lation in the error.

We can see that there are many advantages of FEC: it sometimes has no feedback channel necessary; it has long delay path; it is one-way transmission; it is useful for multi- cast, etc. Despite of these, FEC also meets some problems: it needs high bandwidth, thus it is computationally expensive; it requires over-transmission, etc. Therefore, FEC is not extensively used at the packet level.

So in the next step, we need build new protocol and update our modern FECs to get higher QoS and speed of encoding and decoding such as Tornado code and RS (204, 188). And we also need to update our FEC to seek new way to construct FECs.

6. EVALUATION

After this assignment, we take a further step in learning FECs. We become much more clearly about the different types of FECs, including their strengths and weaknesses and how they work. At first, we just surfed on the internet and collected any useful information about FECs we could find. Nevertheless, we found that the resources were limited and decentralized. In order to explain the fundamental of FECs clearly, we borrowed some books from library and then solved the problems we met. Although the process of doing research and selecting useful information is plain and boring, we benefit a lot from it. We not only learn about the knowledge, but also got some researching experience.