Backward Error Correction

Backward Error Correction (BEC) is a type of error correction in which the receiver detects an error and sends a request for retransmission to the sender.

BEC protocols impose less bandwidth overhead than Forward Error Correction (FEC) protocols, but require more time and bandwidth to recover from errors.

Backward Error Correction is a better solution when errors are rare and bandwidth should be optimized.

BEC algorithms include:

• Parity bits
• CRC (Cyclic Redundancy Check)
• LRC (Longitudinal Redundancy Check)

 

List of error-correcting codes

• AN codes
• BCH code
• Constant-weight code
• Convolutional code
• Group codes
• Golay codes, of which the Binary Golay code is of practical interest
• Goppa code, used in the McEliece cryptosystem
• Hadamard code
• Hagelbarger code
• Hamming code
• Latin square based code for non-white noise (prevalent for example in broadband over powerlines)
• Lexicographic code
• Long code
• Low-density parity-check code, also known as Gallager code, as the archetype for sparse graph codes
• LT code, which is a near-optimal rateless erasure correcting code (Fountain code)
• m of n codes
• Online code, a near-optimal rateless erasure correcting code
• Raptor code, a near-optimal rateless erasure correcting code
• Reed–Solomon error correction
• Reed–Muller code
• Repeat-accumulate code
• Repetition codes, such as Triple modular redundancy
• Tornado code, a near-optimal erasure correcting code, and the precursor to Fountain codes
• Turbo code
• Walsh–Hadamard code

Forward Error Correction

Forward error correction

In telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is the sender encodes their message in a redundant way by using an error-correcting code (ECC). The American mathematician Richard Hamming pioneered this field in the 1940s and invented the first error-correcting code in 1950: the Hamming (7,4) code.

The redundancy allows the receiver to detect a limited number of errors that may occur anywhere in the message, and often to correct these errors without retransmission. FEC gives the receiver the ability to correct errors without needing a reverse channel to request retransmission of data, but at the cost of a fixed, higher forward channel bandwidth. FEC is therefore applied in situations where retransmissions are costly or impossible, such as when broadcasting to multiple receivers in multicast. FEC information is usually added to mass storage devices to enable recovery of corrupted data.

FEC processing in a receiver may be applied to a digital bit stream or in the demodulation of a digitally modulated carrier. For the latter, FEC is an integral part of the initial analog-to-digital conversion in the receiver. The Viterbi decoder implements a soft-decision algorithm to demodulate digital data from an analog signal corrupted by noise. Many FEC coders can also generate a bit-error rate (BER) signal which can be used as feedback to fine-tune the analog receiving electronics.

The maximum fractions of errors or of missing bits that can be corrected is determined by the design of the FEC code, so different forward error correcting codes are suitable for different conditions.

How it works

FEC is accomplished by adding redundancy to the transmitted information using a predetermined algorithm. A redundant bit may be a complex function of many original information bits. The original information may or may not appear literally in the encoded output; codes that include the unmodified input in the output are systematic, while those that do not are non-systematic.

This allows an error in any one of the three samples to be corrected by “majority vote” or “democratic voting”. The correcting ability of this FEC is:

• Up to 1 bit of triplet in error, or
• up to 2 bits of triplet omitted (cases not shown in table).

Though simple to implement and widely used, this triple modular redundancy is a relatively inefficient FEC. Better FEC codes typically examine the last several dozen, or even the last several hundred, previously received bits to determine how to decode the current small handful of bits (typically in groups of 2 to 8 bits).

Averaging noise to reduce errors

FEC could be said to work by “averaging noise”; since each data bit affects many transmitted symbols, the corruption of some symbols by noise usually allows the original user data to be extracted from the other, uncorrupted received symbols that also depend on the same user data.

• Because of this “risk-pooling” effect, digital communication systems that use FEC tend to work well above a certain minimum signal-to-noise ratio and not at all below it.
• This all-or-nothing tendency — the cliff effect — becomes more pronounced as stronger codes are used that more closely approach the theoretical Shannon limit.
• Interleaving FEC coded data can reduce the all or nothing properties of transmitted FEC codes when the channel errors tend to occur in bursts. However, this method has limits; it is best used on narrowband data.

Most telecommunication systems used a fixed channel code designed to tolerate the expected worst-case bit error rate, and then fail to work at all if the bit error rate is ever worse. However, some systems adapt to the given channel error conditions: hybrid automatic repeat-request uses a fixed FEC method as long as the FEC can handle the error rate, then switches to ARQ when the error rate gets too high; adaptive modulation and coding uses a variety of FEC rates, adding more error-correction bits per packet when there are higher error rates in the channel, or taking them out when they are not needed.

Types of FEC

The two main categories of FEC codes are block codes and convolutional codes.

• Block codes work on fixed-size blocks (packets) of bits or symbols of predetermined size. Practical block codes can generally be decoded in polynomial time to their block length.
• Convolutional codes work on bit or symbol streams of arbitrary length. They are most often decoded with the Viterbi algorithm, though other algorithms are sometimes used. Viterbi decoding allows asymptotically optimal decoding efficiency with increasing constraint length of the convolutional code, but at the expense of exponentially increasing complexity. A convolutional code can be turned into a block code, if desired, by “tail-biting”.

There are many types of block codes, but among the classical ones the most notable is Reed-Solomon coding because of its widespread use on the Compact disc, the DVD, and in hard disk drives. Other examples of classical block codes include Golay, BCH, Multidimensional parity, and Hamming codes.

Hamming ECC is commonly used to correct NAND flash memory errors. This provides single-bit error correction and 2-bit error detection. Hamming codes are only suitable for more reliable single level cell (SLC) NAND. Denser multi level cell (MLC) NAND requires stronger multi-bit correcting ECC such as BCH or Reed–Solomon.

Classical block codes are usually implemented using hard-decision algorithms, which means that for every input and output signal a hard decision is made whether it corresponds to a one or a zero bit. In contrast, soft-decision algorithms like the Viterbi decoder process (discretized) analog signals, which allows for much higher error-correction performance than hard-decision decoding.

Nearly all classical block codes apply the algebraic properties of finite fields.

Concatenated FEC codes for improved performance

Classical (algebraic) block codes and convolutional codes are frequently combined in concatenated coding schemes in which a short constraint-length Viterbi-decoded convolutional code does most of the work and a block code (usually Reed-Solomon) with larger symbol size and block length “mops up” any errors made by the convolutional decoder. Single pass decoding with this family of error correction codes can yield very low error rates, but for long range transmission conditions (like deep space) iterative decoding is recommended.

Concatenated codes have been standard practice in satellite and deep space communications since Voyager 2 first used the technique in its 1986 encounter with Uranus. The Galileo craft used iterative concatenated codes to compensate for the very high error rate conditions caused by having a failed antenna.

Low-density parity-check (LDPC)

Low-density parity-check (LDPC) codes are a class of recently re-discovered highly efficient linear block codes. They can provide performance very close to the channel capacity (the theoretical maximum) using an iterated soft-decision decoding approach, at linear time complexity in terms of their block length. Practical implementations can draw heavily from the use of parallelism.

LDPC codes were first introduced by Robert G. Gallager in his PhD thesis in 1960, but due to the computational effort in implementing encoder and decoder and the introduction of Reed–Solomon codes, they were mostly ignored until recently.

LDPC codes are now used in many recent high-speed communication standards, such as DVB-S2 (Digital video broadcasting), WiMAX (IEEE 802.16e standard for microwave communications), High-Speed Wireless LAN (IEEE 802.11n), 10GBase-T Ethernet (802.3an) and G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable). Other LDPC codes are standardized for wireless communication standards within 3GPP MBMS.

Turbo codes

Turbo coding is an iterated soft-decoding scheme that combines two or more relatively simple convolutional codes and an interleaver to produce a block code that can perform to within a fraction of a decibel of the Shannon limit. Predating LDPC codes in terms of practical application, they now provide similar performance.

One of the earliest commercial applications of turbo coding was the CDMA2000 1x (TIA IS-2000) digital cellular technology developed by Qualcomm and sold by Verizon Wireless, Sprint, and other carriers. It is also used for the evolution of CDMA2000 1x specifically for Internet access, 1xEV-DO (TIA IS-856). Like 1x, EV-DO was developed by Qualcomm, and is sold by Verizon Wireless, Sprint, and other carriers (Verizon’s marketing name for 1xEV-DO is Broadband Access, Sprint’s consumer and business marketing names for 1xEV-DO are Power Vision and Mobile Broadband, respectively.).

Local decoding and testing of codes

Sometimes it is only necessary to decode single bits of the message, or to check whether a given signal is a codeword, and do so without looking at the entire signal. This can make sense in a streaming setting, where codewords are too large to be classically decoded fast enough and where only a few bits of the message are of interest for now. Also such codes have become an important tool in computational complexity theory, e.g., for the design of probabilistically checkable proofs.

Locally decodable codes are error-correcting codes for which single bits of the message can be probabilistically recovered by only looking at a small (say constant) number of positions of a codeword, even after the codeword has been corrupted at some constant fraction of positions. Locally testable codes are error-correcting codes for which it can be checked probabilistically whether a signal is close to a codeword by only looking at a small number of positions of the signal.

Convolutional Codes

Introduction

Convolutional codes are frequently used to correct errors in noisy channels. They have rather good correcting capability and perform well even on very bad channels (with error probabilities of about 10−3). Convolutional codes are extensively used in satellite communications. Although convolutional encoding is a simple procedure, decoding of a convolutional code is much more complex task.

Several classes of algorithms exist for this purpose:

1. Threshold decoding is the simplest of them, but it can be successfully applied only to the specific classes of convolutional codes. It is also far from optimal.

2. Sequential decoding is a class of algorithms performing much better than threshold algorithms. Their serious advantage is that decoding complexity is virtually independent from the length of the particular code. Although sequential algorithms are also suboptimal, they are successfully used with very long codes, where no other algorithm can be acceptable. The main drawback of sequential decoding is unpredictable decoding latency.

3. Viterbi decoding is an optimal (in a maximum-likelihood sense) algorithm for decoding of a convolutional code. Its main drawback is that the decoding complexity grows exponentially with the code length. So, it can be utilized only for relatively short codes.

There are also soft-output algorithms, like SOVA (Soft Output Viterbi Algorithm) or MAP algorithm, which provide not only a decision, but also an estimate of its reliability. They are used primarily in the decoders of turbo codes.

Convolutional Encoders

1. Like any error-correcting code, a convolutional code works by adding some structured redundant information to the user’s data and then correcting errors using this information.
2. A convolutional encoder is a linear system.
3. A binary convolutional encoder can be represented as a shift register. The outputs of the encoder are modulo 2 sums of the values in the certain register’s cells. The input to the encoder is either the un-encoded sequence (for non-recursive codes) or the un-encoded sequence added with the values of some register’s cells (for recursive codes).
4. Convolutional codes can be systematic and non-systematic. Systematic codes are those where an un-encoded sequence is a part of the output sequence. Systematic codes are almost always recursive; conversely, non-recursive codes are almost always non-systematic.
5. A combination of register’s cells that forms one of the output streams (or that is added with the input stream for recursive codes) is defined by a polynomial. Let m be the maximum degree of the polynomials constituting a code, then K=m1 is a constraint length of the code.
6. A code rate is an inverse number of output polynomials.

Trellis Diagram

• A convolutional encoder is often seen as a finite state machine.
• Each state corresponds to some value of the encoder’s register.
• Given the input bit value, from a certain state the encoder can move to two other states.
• These state transitions constitute a diagram which is called a trellis diagram.
• A trellis diagram for the code is depicted on the Figure.
• A solid line corresponds to input 0, a dotted line – to input 1 (note that encoder states are designated in such a way that the rightmost bit is the newest one).
• Each path on the trellis diagram corresponds to a valid sequence from the encoder’s output.
• Conversely, any valid sequence from the encoder’s output can be represented as a path on the trellis diagram.
• One of the possible paths is denoted as red (as an example).
• Note that each state transition on the diagram corresponds to a pair of output bits.
• There are only two allowed transitions for every state, so there are two allowed pairs of output bits, and the two other pairs are forbidden.
• If an error occurs, it is very likely that the receiver will get a set of forbidden pairs, which don’t constitute a path on the trellis diagram.
• So, the task of the decoder is to find a path on the trellis diagram which is the closest match to the received sequence.

Let’s define a free distance d f as a minimal Hamming distance between two different allowed binary sequences (a Hamming distance is defined as a number of differing bits).

A free distance is an important property of the convolutional code. It influences a number of closely located errors the decoder is able to correct.

Viterbi Algorithm

We will use the code generated by the encoder on Figure as an example.

Basic Definitions

Ideally, Viterbi algorithm reconstructs the maximum-likelihood path given the input sequence.

Let’s define some terms:

Soft Decision Decoder

• A soft decision decoder is a decoder receiving bits from the channel with some kind of reliability estimate.
• Three bits are usually sufficient for this task.
• Further increasing soft decision width will increase performance only slightly while considerably increasing computational difficulty.
• For example, if we use a 3-bit soft decision, then “000” is the strongest zero, “011” is a weakest zero, “100” is a weakest one and “111” is a strongest one.

Hard Decision Decoder

• A hard decision decoder is a decoder which receives only bits from the channel (without any reliability estimate).

Branch Metric

• A branch metric – a distance between the received pair of bits and one of the “ideal” pairs (“00”, “01”, “10”, “11”).

Path Metric

A path metric is a sum of metrics of all branches in the path.

Distance

A meaning of distance depends on the type of the decoder:

• for a hard decision decoder it is a Hamming distance, i.e. a number of differing bits;
• For a soft decision decoder it is a Euclidean distance.

In these terms, the maximum-likelihood path is a path with the minimal path metric. Thus the problem of decoding is equivalent to the problem of finding such a path.

Let’s suppose that for every possible encoder state we know a path with minimum metric ending in this state. For any given encoder state there is two (and only two) states from which the encoder can move to that state, and for both of these transitions we know branch metrics. So, there are only two paths ending in any given state on the next step. One of them has lesser metric, it is a survivor path.

The other path is dropped as less likely. Thus we know a path with minimum metric on the next step, and the above procedure can be repeated.

Implementation

A Viterbi algorithm consists of the following three major parts:

1. Branch metric calculation – calculation of a distance between the input pair of bits and the four possible “ideal” pairs (“00”, “01”, “10”, “11”).
2. Path metric calculation – for every encoder state, calculate a metric for the survivor path ending in this state (a survivor path is a path with the minimum metric).
3. Trace back – this step is necessary for hardware implementations that don’t store full information about the survivor paths, but store only one bit decision every time when one survivor path is selected from the two.

1.     Branch Metric Calculation

Methods of branch metric calculation are different for hard decision and soft decision decoders.

For a hard decision decoder, a branch metric is a Hamming distance between the received pair of bits and the “ideal” pair. Therefore, a branch metric can take values of 0, 1 and 2. Thus for every input pair we have 4 branch metrics (one for each pair of “ideal” values).

For a soft decision decoder, a branch metric is measured using the Euclidean distance. Let x be the first received bit in the pair, y – the second, x₀ and y₀ – the “ideal” values. Then branch metric is

M_b = (x−x₀)² + (y−y₀)²

Furthermore, when we calculate 4 branch metric for a soft decision decoder, we don’t actually need to know absolute metric values – only the difference between them makes sense. So, nothing will change if we subtract one value from the all four branch metrics:

M_b = (x² − 2 x x₀ + x₀²) + (y²−2 y y₊ y₀²)

M_b * = M_b−x²−y² = ( x₀ ² −2 x x₀ ) + (y₀ ² −2 y y₀)

Note that the second formula, M_b *, can be calculated without hardware multiplication: x₀² and y₀² can be pre-calculated, and multiplication of x by x₀ and y by y₀ can be done very easily in hardware given that x₀ and y₀ are constants.

It should be also noted that M_b * is a signed variable and should be calculated in 2’s complement format.

Path Metric Calculation

Path metrics are calculated using a procedure called ACS (Add-Compare-Select). This procedure is repeated for every encoder state.

1. Add – for a given state, we know two states on the previous step which can move to this state, and the output bit pairs that correspond to these transitions. To calculate new path metrics, we add the previous path metrics with the corresponding branch metrics.
2. Compare, select – we now have two paths, ending in a given state. One of them (with greater metric) is dropped.

As there are 2K−1 encoder states, we have 2K−1 survivor paths at any given time.

It is important that the difference between two survivor path metrics cannot exceed logK−1 , where δ is a difference between maximum and minimum possible branch metrics.

The problem with path metrics is that they tend to grow constantly and will eventually overflow.

But, since the absolute values of path metric don’t actually matter, and the difference between them is limited, a data type with a certain number of bits will be sufficient.

There are two ways of dealing with this problem:

1. Since the absolute values of path metric don’t actually matter, we can at any time subtract an identical value from the metric of every path. It is usually done when all path metrics exceed a chosen threshold (in this case the threshold value is subtracted from every path metric). This method is simple, but not very efficient when implemented in hardware.
2. The second approach allows overflow, but uses a sufficient number of bits to be able to detect whether the overflow took place or not. The compare procedure must be modified in this case.

The whole range of the data type’s capacity is divided into 4 equal parts. If one path metric is in the 3-rd quarter, and the other – in the 0-th, then the overflow took place and the path in min max the 3-rd quarter should be selected. In other cases an ordinary compare procedure is applied.

This works, because a difference between path metrics can’t exceed a threshold value, and the range of path variable is selected such that it is at least two times greater than the threshold.

Traceback

It has been proven that all survivor paths merge after decoding a sufficiently large block of data, i.e. they differ only in their endings and have the common beginning.

If we decode a continuous stream of data, we want our decoder to have finite latency. It is obvious that when some part of path at the beginning of the graph belongs to every survivor path, the decoded bits corresponding to this part can be sent to the output. Given the above statement, we can perform the decoding as follows:

1. Find the survivor paths for N+D input pairs of bits.
2. Trace back from the end of any survivor paths to the beginning.
3. Send N bits to the output.
4. Find the survivor paths for another N pairs of input bits.
5. Go to step 2.

In this procedure D is an important parameter called decoding depth. A decoding depth should be considerably large for quality decoding, no less than 5K. Increasing D decreases the probability of a decoding error, but also increases latency.

As for N, it specifies how many bits we are sending to the output after each traceback. For example, if N=1, the latency is minimal, but the decoder needs to trace the whole tree every step. It is computationally ineffective. In hardware implementations N usually equals D.

Viterbi Algorithm

Viterbi algorithm is a well-known maximum-likelihood algorithm for decoding of convolutional codes.

The terms “Viterbi path” and “Viterbi algorithm” are also applied to related dynamic programming algorithms that discover the single most likely explanation for an observation. For example, in statistical parsing a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is sometimes called the “Viterbi parse”.

The Viterbi algorithm was conceived by Andrew Viterbi in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links. For more details on the history of the development of the algorithm see David Forney’s article.[1] The algorithm has found universal application in decoding the convolutional codes used in both CDMA and GSM digital cellular, dial-up modems, satellite, deep-space communications, and 802.11 wireless LANs. It is now also commonly used in speech recognition, keyword spotting, computational linguistics, and bioinformatics. For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the “hidden cause” of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.

Introduction

 The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources, and more generally, hidden Markov models. The forward algorithm is a closely related algorithm for computing the probability of a sequence of observed events. These algorithms belong to the realm of information theory.

Assumptions

The algorithm makes a number of assumptions.

• First, both the observed events and hidden events must be in a sequence. This sequence often corresponds to time.
• Second, these two sequences need to be aligned, and an instance of an observed event needs to correspond to exactly one instance of a hidden event.
• Third, computing the most likely hidden sequence up to a certain point t must depend only on the observed event at point t, and the most likely sequence at point t − 1.

These assumptions are all satisfied in a first-order hidden Markov model.

Overview

Assumption 1

• The Viterbi algorithm operates on a state machine assumption.
• That is, at any time the system being modeled is in one of a finite number of states.
• While multiple sequences of states (paths) can lead to a given state, at least one of them is a most likely path to that state, called the “survivor path”.
• This is a fundamental assumption of the algorithm because the algorithm will examine all possible paths leading to a state and only keep the one most likely.
• This way the algorithm does not have to keep track of all possible paths, only one per state.

Assumption 2

• A second key assumption is that a transition from a previous state to a new state is marked by an incremental metric, usually a number.
• This transition is computed from the event.

Assumption 3

• The third key assumption is that the events are cumulative over a path in some sense, usually additive.
• So the crux of the algorithm is to keep a number for each state.
• When an event occurs, the algorithm examines moving forward to a new set of states by combining the metric of a possible previous state with the incremental metric of the transition due to the event and chooses the best.
• The incremental metric associated with an event depends on the transition possibility from the old state to the new state.

Path history must be stored. In some cases, the search history is complete because the state machine at the encoder starts in a known state and there is sufficient memory to keep all the paths. In other cases, a programmatic solution must be found for limited resources: one example is convolutional encoding, where the decoder must truncate the history at a depth large enough to keep performance to an acceptable level. Although the Viterbi algorithm is very efficient and there are modifications that reduce the computational load, the memory requirements tend to remain constant.

Extensions

With the algorithm called iterative Viterbi decoding one can find the subsequence of an observation that matches best (on average) to a given HMM. Iterative Viterbi decoding works by iteratively invoking a modified Viterbi algorithm, re-estimating the score for filler until convergence.

An alternative algorithm, the Lazy Viterbi algorithm, has been proposed recently. This works by not expanding any nodes until it really needs to, and usually manages to get away with doing a lot less work (in software) than the ordinary Viterbi algorithm for the same result – however, it is not so easy to parallelize in hardware.

The Viterbi algorithm has been extended to operate with a deterministic finite automaton in order to quickly generate the trellis with state transitions pointing back at variable amount of history.

Iteration

• The action or a process of iterating or repeating: as
  • A procedure in which repetition of a sequence of operations yields results successively closer to a desired result
  • The repetition of a sequence of computer instructions a specified number of times or until a condition is met — compare recursion
• One execution of a sequence of operations or instructions in an iteration

Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an “iteration,” and the results of one iteration are used as the starting point for the next iteration.

Mathematics

Iteration in mathematics may refer to the process of iterating a function i.e. applying a function repeatedly, using the output from one iteration as the input to the next. Iteration of apparently simple functions can produce complex behaviors and difficult problems – for examples, see the Collatz conjecture and juggler sequences.

Another use of iteration in mathematics is in iterative methods which are used to produce approximate numerical solutions to certain mathematical problems. Newton’s method is an example of an iterative method.

Computing

Iteration in computing is the repetition of a process within a computer program. It can be used both as a general term, synonymous with repetition, and to describe a specific form of repetition with a mutable state.

When used in the first sense, recursion is an example of iteration, but typically using a recursive notation, which is typically not the case for iteration.

However, when used in the second (more restricted) sense, iteration describes the style of programming used in imperative programming languages. This contrasts with recursion, which has a more declarative approach.

Here is an example of iteration relying on destructive assignment, in imperative pseudo code:

• var i, a = 0        // initialize a before iteration
• for i from 1 to 3    // loop three times
• {
• a = a + i       // increment a by the current value of i
• }
• print a              // the number 6 is printed

In this program fragment, the value of the variable i changes over time, taking the values 1, 2 and 3. This changing value—or mutable state—is characteristic of iteration.

Iteration can be approximated using recursive techniques in functional programming languages. The following example is in Scheme. Note that the following is recursive (a special case of iteration) because the definition of “how to iterate”, the iter function, calls itself in order to solve the problem instance. Specifically it uses tail recursion, which is properly supported in languages like Scheme so it does not use large amounts of stack space.

• ;; sum : number -> number
• ;; to sum the first n natural numbers
• (define (sum n)
• (if (and (integer? n) (> n 0))
• (let iter ([n n] [i 1])
• (if (= n 1)
• i
• (iter (- n 1) (+ n i))))
• ((assertion-violation
• ‘sum “invalid argument” n))))

An iterator is an object that wraps iteration.

Iteration is also performed using a worksheet, or by using solver or goal seek functions available in Excel. Many implicit equations like the Colebrook equation can be solved in the convenience of a worksheet by designing suitable calculation algorithms.

Many of the engineering problems like solving Colebrook equations reaches 8-digit accuracy in as small as 12 iterations and a maximum of 100 iterations is sufficient to reach a 15-digit accurate result.

Project Management

Iterations in a project context may refer to the technique of developing and delivering incremental components of business functionality, product development or process design. This is most often associated with agile software development, but could potentially be any material. A single iteration results in one or more bite-sized but complete packages of project work that can perform some tangible business function. Multiple iterations recurse to create a fully integrated product. This is often compared with the waterfall model approach.

Reed Solomon Code

Introduction

Reed-Solomon codes are block-based error correcting codes with a wide range of applications in digital communications and storage. Reed-Solomon codes are used to correct errors in many systems including:

• Storage devices (including tape, Compact Disk, DVD, barcodes, etc)
• Wireless or mobile communications (including cellular telephones, microwave links, etc)
• Satellite communications
• Digital television / DVB
• High-speed modems such as ADSL, xDSL, etc.

A typical system is shown here:

The Reed-Solomon encoder takes a block of digital data and adds extra “redundant” bits. Errors occur during transmission or storage for a number of reasons (for example noise or interference, scratches on a CD, etc). The Reed-Solomon decoder processes each block and attempts to correct errors and recover the original data. The number and type of errors that can be corrected depends on the characteristics of the Reed-Solomon code.

Properties of Reed-Solomon codes

Reed Solomon codes are a subset of BCH codes and are linear block codes. A Reed-Solomon code is specified as RS(n,k) with s-bit symbols.

This means that the encoder takes k data symbols of s bits each and adds parity symbols to make an n symbol codeword. There are n-k parity symbols of s bits each. A Reed-Solomon decoder can correct up to t symbols that contain errors in a codeword, where 2t = n-k.

The following diagram shows a typical Reed-Solomon codeword (this is known as a Systematic code because the data is left unchanged and the parity symbols are appended):

The following diagram shows a typical Reed-Solomon codeword (this is known as a Systematic code because the data is left unchanged and the parity symbols are appended):

Given a symbol size s, the maximum codeword length (n) for a Reed-Solomon code is n = 2^s – 1

Reed-Solomon codes may be shortened by (conceptually) making a number of data symbols zero at the encoder, not transmitting them, and then re-inserting them at the decoder.

The amount of processing “power” required to encode and decode Reed-Solomon codes is related to the number of parity symbols per codeword. A large value of t means that a large number of errors can be corrected but requires more computational power than a small value of t.

Symbol Errors

One symbol error occurs when 1 bit in a symbol is wrong or when all the bits in a symbol are wrong.

Reed-Solomon codes are particularly well suited to correcting burst errors (where a series of bits in the codeword are received in error).

Decoding

Reed-Solomon algebraic decoding procedures can correct errors and erasures. An erasure occurs when the position of an erred symbol is known. A decoder can correct up to t errors or up to 2t erasures. Erasure information can often be supplied by the demodulator in a digital communication system, i.e. the demodulator “flags” received symbols that are likely to contain errors.

When a codeword is decoded, there are three possible outcomes:

1. If 2s + r < 2t (s errors, r erasures) then the original transmitted code word will always be recovered,

OTHERWISE

2. The decoder will detect that it cannot recover the original code word and indicate this fact.

OR

3. The decoder will mis-decode and recover an incorrect code word without any indication.

The probability of each of the three possibilities depends on the particular Reed-Solomon code and on the number and distribution of errors.

Coding Gain

The advantage of using Reed-Solomon codes is that the probability of an error remaining in the decoded data is (usually) much lower than the probability of an error if Reed-Solomon is not used. This is often described as coding gain.

Architectures for Encoding & Decoding Reed-Solomon Codes

Reed-Solomon encoding and decoding can be carried out in software or in special-purpose hardware.

Finite (Galois) Field Arithmetic

Reed-Solomon codes are based on a specialist area of mathematics known as Galois fields or finite fields. A finite field has the property that arithmetic operations (+,-,x,/ etc.) on field elements always have a result in the field. A Reed-Solomon encoder or decoder needs to carry out these arithmetic operations. These operations require special hardware or software functions to implement.

Generator Polynomial

A Reed-Solomon codeword is generated using a special polynomial. All valid codewords are exactly divisible by the generator polynomial. The general form of the generator polynomial is:

and the codeword is constructed using:

c(x) = g(x).i(x)

where g(x) is the generator polynomial, i(x) is the information block, c(x) is a valid codeword and a is referred to as a primitive element of the field.

Encoder architecture

The 2t parity symbols in a systematic Reed-Solomon codeword are given by:
The following diagram shows an architecture for a systematic RS(255,249) encoder:

Each of the 6 registers holds a symbol (8 bits). The arithmetic operators carry out finite field addition or multiplication on a complete symbol.

Decoder architecture

A general architecture for decoding Reed-Solomon codes is shown in the following diagram

Key

r(x)	Received codeword
Si	Syndromes
L(x)	Error locator polynomial
Xi	Error locations
Yi	Error magnitudes
c(x)	Recovered code word
v	Number of errors

The received codeword r(x) is the original (transmitted) codeword c(x) plus errors:

r(x) = c(x) + e(x)

A Reed-Solomon decoder attempts to identify the position and magnitude of up to t errors (or 2t erasures) and to correct the errors or erasures.

Syndrome Calculation

This is a similar calculation to parity calculation. A Reed-Solomon codeword has 2t syndromes that depend only on errors (not on the transmitted code word). The syndromes can be calculated by substituting the 2t roots of the generator polynomial g(x) into r(x).

Finding the Symbol Error Locations

This involves solving simultaneous equations with t unknowns. Several fast algorithms are available to do this. These algorithms take advantage of the special matrix structure of Reed-Solomon codes and greatly reduce the computational effort required. In general two steps are involved:

Find an error locator polynomial

This can be done using the Berlekamp-Massey algorithm or Euclid’s algorithm. Euclid’s algorithm tends to be more widely used in practice because it is easier to implement: however, the Berlekamp-Massey algorithm tends to lead to more efficient hardware and software implementations.

Find the roots of this polynomial

This is done using the Chien search algorithm.

Finding the Symbol Error Values

Again, this involves solving simultaneous equations with t unknowns. A widely-used fast algorithm is the Forney algorithm.

Implementation of Reed-Solomon encoders and decoders

Hardware Implementation

A number of commercial hardware implementations exist. Many existing systems use “off-the-shelf” integrated circuits that encode and decode Reed-Solomon codes. These ICs tend to support a certain amount of programmability (for example, RS(255,k) where t = 1 to 16 symbols). A recent trend is towards VHDL or Verilog designs (logic cores or intellectual property cores). These have a number of advantages over standard ICs. A logic core can be integrated with other VHDL or Verilog components and synthesized to an FPGA (Field Programmable Gate Array) or ASIC (Application Specific Integrated Circuit) – this enables so-called “System on Chip” designs where multiple modules can be combined in a single IC. Depending on production volumes, logic cores can often give significantly lower system costs than “standard” ICs. By using logic cores, a designer avoids the potential need to do a “lifetime buy” of a Reed-Solomon IC.

Software Implementation

Until recently, software implementations in “real-time” required too much computational power for all but the simplest of Reed-Solomon codes (i.e. codes with small values of t). The major difficulty in implementing Reed-Solomon codes in software is that general purpose processors do not support Galois field arithmetic operations. For example, to implement a Galois field multiply in software requires a test for 0, two log table look-ups, modulo add and anti-log table look-up. However, careful design together with increases in processor performance mean that software implementations can operate at relatively high data rates. The following table gives some example benchmark figures on a 166MHz Pentium PC:

Code	Data rate
RS(255,251)	12 Mbps
RS(255,239)	2.7 Mbps
RS(255,223)	1.1 Mbps

These data rates are for decoding only: encoding is considerably faster since it requires less computation.

LDPC Code

• In information theory, a low-density parity-check (LDPC) code is a linearerror correcting code, a method of transmitting a message over a noisy transmission channel, and is constructed using a sparse bipartite graph.
• A low-density parity-check(LDPC) codeis a linear block code for which the parity-check matrix Hhas a low density
  of 1’s
• A regular(n, k)LDPCcode is a linear block code whose parity-check matrix H contains exactly Wc1’s per column and exactly Wr= Wc(n/m) 1’s per row, where Wc<< m.
• LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close (or even arbitrarily close on the BEC) to the theoretical maximum (the Shannon limit) for a symmetric memory-less channel.
• The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired.
• Using iterative belief propagation techniques, LDPC codes can be decoded in time linear to their block length.
• The name comes from the characteristic of their parity-check matrix which contains only a few 1’s in comparison to the amount of0’s.
• Their main advantage is that they provide a performance whichis very close to the capacity for a lot of different channels
  and linear time complex algorithms for decoding.

Bipartite Graph

A bipartitegraphis a graph (nodes or vertices connected by undirected edges) whose nodes may be separated into two classes,and where edges may only connect two nodes not residing in the same class.

Representations for LDPC codes

 I. Matrix Representation

Let’s look at an example for a low-density parity-check matrix first.The matrix defined in equation (1) is a parity check matrix with dimension n ×m for a (8, 4) code.

We can now define two numbers describing this matrix. wrfor the number of 1’s in each row and wcfor the columns. For a matrix to be called low-density the two conditions wc<<n and wr<<m must

Tanner graph corresponding to the parity check matrix in equation (1). The marked path c2 !f1 !c5 !f2 !c2is an example for a short cycle. Those should usually be avoided since they are bad for decoding performance. Be satisfied. In order to do this, the parity check matrix should usually be very large, so the example matrix can’t be really called low-density.

II. Graphical Representation

Tanner graphs are bipartite graphs. That means that the nodes of the graph are separated into two distinctive sets and edges are only connecting nodes of two different types. The two types of nodes in a Tanner graph are called variable nodes (v-nodes) and check nodes v-nodes (c-nodes).

It consists of m check nodes (the number of parity bits) and n variable nodes (the number of bits in a code word). Check node fi is connected to variable node cj if the element hij of H is a 1.

Regular and Irregular LDPC codes

A LDPC code is called regular if wc is constant for every column regular and wr = wc · (n/m) is also constant for every row.There is the same number of incoming edges for every v-node and also for all the c-nodes.

If H is low density but the numbers of 1’s in each row or column aren’t constant the code is called an irregular LDPC code.

Reference:

http://users.tkk.fi/pat/coding/essays/ldpc.pdf

Turbo Code

• The term “turbo codes” has been generalized to cover block codes as well as convolutional codes
• A turbo code is formed from the parallel concatenation of two codes separated by an interleaver
• The generic design of a turbo code allows for free choice of the encoders and the interleaver, most designs follows
  • The two encoders used are normally identical
  • The code is in a systematic form, i.e. the input bits also occur in the output
  • The interleaver reads the bits in a pseudo-random order
• Turbo codes are a recent development in the field of forward-error-correction channel coding.
• The codes make use of three simple ideas:
• Parallel concatenationof codes to allow simpler decoding
• Interleaving to provide better weight distribution
• Soft decoding to enhance decoder decisions and maximize thegain from decoder interaction

Interleaver

The task of the interleaver is to “scramble” bits in a (pseudo-)random, albeit predetermined fashion.

Why interleaver is used in Turbo codes?

• The choice of the interleaver is a crucial part in the turbo code design.
• This serves two purposes.
  • Firstly, if the input to the second encoder is interleaved, its output is usually quite different from the output of the first encoder. This means that even if one of the output code words has low weight, the other usually does not, and there is a smaller chance of producing an output with very low weight. Higher weight is beneficial for the performance of the decoder.
  • Secondly, since the code is a parallel concatenation of two codes, the divide-and-conquer strategy can be employed for decoding. If the input to the second decoder is scrambled, also its output will be different or uncorrelated from the output of the first encoder. This means that the corresponding two decoders will gain more from information exchange.

Designs of Interleaver

The choice of the interleaver has a key part in the success of the code and the best choice is dependent on the code design.

I. A “row-column” interleaver

• Data is written row-wise and read column wise
• While very simple, it also provides little randomness

II. A “helical” interleaver

• Data is written row-wise and read diagonally

III. An “odd-even” interleaver

• First, the bits are left un-interleaved and encoded, but only the odd-positioned coded bits are stored
• Then, the bits are scrambled and encoded, but now only the even-positioned coded bits are stored
• Odd-even encoders can be used, when the second encoder produces one output bit per one input bit

IV. A pseudo-random interleaver

Defined by a pseudo-random number generator or a look-up table

Turbo Codes Decoding

In the traditional decoding approach, the demodulator makes a “hard” decision of the received symbol, and passes to the error control decoder a discrete value, either a 0 or a 1. The disadvantage of this approach is that while the value of some bits is determined with greater certainty than that of others, the decoder cannot make use of this information.

A soft-in-soft-out (SISO) decoder receives as input a “soft” (i.e. real) value of the signal. The decoder then outputs for each data bit an estimate expressing the probability that the transmitted data bit was equal to one.

In the case of turbo codes, there are two decoders for outputs from both encoders. Both decoders provide estimates of the same set of data bits, albeit in a different order. If all intermediate values in the decoding process are soft values, the decoders can
gain greatly from exchanging information, after appropriate reordering of values. Information exchange can be iterated a number of times to enhance performance.

At each round, decoders re-evaluate their estimates, using information from the other decoder, and only in the final stage will hard decisions be made, i.e. each bit is assigned the value 1 or 0. Such decoders, although more difficult to implement, are
essential in the design of turbo codes.

Hamming Code

• Hamming codes are the first class of linear codes devised for error correction.
• These codes and their variations have been widely used for error control in digital communication and data storage systems.
• For any positive integer m > 3, there exists a Hamming code with the following parameters

The parity-check matrix H of this code consists of all the nonzero m-tuples as its columns. In systematic form, the columns of H are arranged in the following form:

H = [Im Q]