Serial concatenated convolutional codes

Last updated

Serial concatenated convolutional codes (SCCC) are a class of forward error correction (FEC) codes highly suitable for turbo (iterative) decoding. [1] [2] Data to be transmitted over a noisy channel may first be encoded using an SCCC. Upon reception, the coding may be used to remove any errors introduced during transmission. The decoding is performed by repeated decoding and [de]interleaving of the received symbols.

Contents

SCCCs typically include an inner code, an outer code, and a linking interleaver. A distinguishing feature of SCCCs is the use of a recursive convolutional code as the inner code. The recursive inner code provides the 'interleaver gain' for the SCCC, which is the source of the excellent performance of these codes.

The analysis of SCCCs was spawned in part by the earlier discovery of turbo codes in 1993. This analysis of SCCC's took place in the 1990s in a series of publications from NASA's Jet Propulsion Laboratory (JPL). The research offered SCCC's as a form of turbo-like serial concatenated codes that 1) were iteratively ('turbo') decodable with reasonable complexity, and 2) gave error correction performance comparable with the turbo codes.

Prior forms of serial concatenated codes typically did not use recursive inner codes. Additionally, the constituent codes used in prior forms of serial concatenated codes were generally too complex for reasonable soft-in-soft-out (SISO) decoding. SISO decoding is considered essential for turbo decoding.

Serial concatenated convolutional codes have not found widespread commercial use, although they were proposed for communications standards such as DVB-S2. Nonetheless, the analysis of SCCCs has provided insight into the performance and bounds of all types of iterative decodable codes including turbo codes and LDPC codes.[ citation needed ]

US patent 6,023,783 covers some forms of SCCCs. The patent expired on May 15, 2016. [3]

History

Serial concatenated convolutional codes were first analyzed with a view toward turbo decoding in "Serial Concatenation of Interleaved Codes: Performance Analysis, Design, and Iterative Decoding" by S. Benedetto, D. Divsalar, G. Montorsi and F. Pollara. [4] This analysis yielded a set of observations for designing high performance, turbo decodable serial concatenated codes that resembled turbo codes. One of these observations was that "the use of a recursive convolutional inner encoder always yields an interleaver gain."[ clarification needed ] This is in contrast to the use of block codes or non-recursive convolutional codes, which do not provide comparable interleaver gain.

Additional analysis of SCCCs was done in "Coding Theorems for 'Turbo-Like' Codes" by D. Divsalar, Hui Jin, and Robert J. McEliece. [5] This paper analyzed repeat-accumulate (RA) codes which are the serial concatenation of an inner two-state recursive convolutional code (also called an 'accumulator' or parity-check code) with a simple repeat code as the outer code, with both codes linked by an interleaver. The performance of the RA codes is quite good considering the simplicity of the constituent codes themselves.

SCCC codes were further analyzed in "Serial Turbo Trellis Coded Modulation with Rate-1 Inner Code". [6] In this paper SCCCs were designed for use with higher order modulation schemes. Excellent performing codes with inner and outer constituent convolutional codes of only two or four states were presented.

Example Encoder

Fig 1 is an example of a SCCC.

Fig. 1. SCCC Encoder SCCC Encoder.png
Fig. 1. SCCC Encoder

The example encoder is composed of a 16-state outer convolutional code and a 2-state inner convolutional code linked by an interleaver. The natural code rate of the configuration shown is 1/4, however, the inner and/or outer codes may be punctured to achieve higher code rates as needed. For example, an overall code rate of 1/2 may be achieved by puncturing the outer convolutional code to rate 3/4 and the inner convolutional code to rate 2/3.

A recursive inner convolutional code is preferable for turbo decoding of the SCCC. The inner code may be punctured to a rate as high as 1/1 with reasonable performance.

Example Decoder

An example of an iterative SCCC decoder.

Fig. 2. SCCC Decoder SCCC Decoder.png
Fig. 2. SCCC Decoder

The SCCC decoder includes two soft-in-soft-out (SISO) decoders and an interleaver. While shown as separate units, the two SISO decoders may share all or part of their circuitry. The SISO decoding may be done is serial or parallel fashion, or some combination thereof. The SISO decoding is typically done using Maximum a posteriori (MAP) decoders using the BCJR algorithm.

Performance

SCCCs provide performance comparable to other iteratively decodable codes including turbo codes and LDPC codes. They are noted for having slightly worse performance at lower SNR environments (i.e. worse waterfall region), but slightly better performance at higher SNR environments (i.e. lower error floor).

See also

Related Research Articles

Error detection and correction Techniques that enable reliable delivery of digital data over unreliable communication channels

In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.

In telecommunication, a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of the encoder over the data, which gives rise to the term 'convolutional coding'. The sliding nature of the convolutional codes facilitates trellis decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity.

Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960. They have many applications, the most prominent of which include consumer technologies such as MiniDiscs, CDs, DVDs, Blu-ray discs, QR codes, data transmission technologies such as DSL and WiMAX, broadcast systems such as satellite communications, DVB and ATSC, and storage systems such as RAID 6.

A satellite modem or satmodem is a modem used to establish data transfers using a communications satellite as a relay. A satellite modem's main function is to transform an input bitstream to a radio signal and vice versa.

In information theory, turbo codes are a class of high-performance forward error correction (FEC) codes developed around 1990–91, but first published in 1993. They were the first practical codes to closely approach the maximum channel capacity or Shannon limit, a theoretical maximum for the code rate at which reliable communication is still possible given a specific noise level. Turbo codes are used in 3G/4G mobile communications and in satellite communications as well as other applications where designers seek to achieve reliable information transfer over bandwidth- or latency-constrained communication links in the presence of data-corrupting noise. Turbo codes compete with low-density parity-check (LDPC) codes, which provide similar performance.

In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC is constructed using a sparse Tanner graph. LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close to the theoretical maximum for a symmetric memoryless 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.

Claude Berrou is a French professor in electrical engineering at École Nationale Supérieure des Télécommunications de Bretagne, now IMT Atlantique. He is the sole inventor of a groundbreaking quasi-optimal error-correcting coding scheme called Turbo codes as evidenced by the sole inventorship credit given on the fundamental patent for turbo codes. The original patent filing for turbo codes issued in the US as US Patent 5,446,747.

A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using a convolutional code or trellis code.

In computer science, Raptor codes are the first known class of fountain codes with linear time encoding and decoding. They were invented by Amin Shokrollahi in 2000/2001 and were first published in 2004 as an extended abstract. Raptor codes are a significant theoretical and practical improvement over LT codes, which were the first practical class of fountain codes.

In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is the sender encodes the message with redundant information in the form of an ECC. 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. 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.

In computer science, repeat-accumulate codes are a low complexity class of error-correcting codes. They were devised so that their ensemble weight distributions are easy to derive. RA codes were introduced by Divsalar et al.

The error floor is a phenomenon encountered in modern iterated sparse graph-based error correcting codes like LDPC codes and turbo codes. When the bit error ratio (BER) is plotted for conventional codes like Reed–Solomon codes under algebraic decoding or for convolutional codes under Viterbi decoding, the BER steadily decreases in the form of a curve as the SNR condition becomes better. For LDPC codes and turbo codes there is a point after which the curve does not fall as quickly as before, in other words, there is a region in which performance flattens. This region is called the error floor region. The region just before the sudden drop in performance is called the waterfall region.

EXIT chart

An extrinsic information transfer chart, commonly called an EXIT chart, is a technique to aid the construction of good iteratively-decoded error-correcting codes.

The BCJR algorithm is an algorithm for maximum a posteriori decoding of error correcting codes defined on trellises. The algorithm is named after its inventors: Bahl, Cocke, Jelinek and Raviv. This algorithm is critical to modern iteratively-decoded error-correcting codes including turbo codes and low-density parity-check codes.

A-VSB or Advanced VSB is a modification of the 8VSB modulation system used for transmission of digital television using the ATSC system. One of the constraints of conventional ATSC transmission is that reliable reception is difficult or impossible when the receiver is moving at speeds associated with normal vehicular traffic. The technology was jointly developed by Samsung and Rohde & Schwarz.

ATSC-M/H is a U.S. standard for mobile digital TV that allows TV broadcasts to be received by mobile devices.

In coding theory, concatenated codes form a class of error-correcting codes that are derived by combining an inner code and an outer code. They were conceived in 1966 by Dave Forney as a solution to the problem of finding a code that has both exponentially decreasing error probability with increasing block length and polynomial-time decoding complexity. Concatenated codes became widely used in space communications in the 1970s.

A soft-in soft-out (SISO) decoder is a type of soft-decision decoder used with error correcting codes. "Soft-in" refers to the fact that the incoming data may take on values other than 0 or 1, in order to indicate reliability. "Soft-out" refers to the fact that each bit in the decoded output also takes on a value indicating reliability. Typically, the soft output is used as the soft input to an outer decoder in a system using concatenated codes, or to modify the input to a further decoding iteration such as in the decoding of turbo codes.

In digital communications, a turbo equalizer is a type of receiver used to receive a message corrupted by a communication channel with intersymbol interference (ISI). It approaches the performance of a maximum a posteriori (MAP) receiver via iterative message passing between a soft-in soft-out (SISO) equalizer and a SISO decoder. It is related to turbo codes in that a turbo equalizer may be considered a type of iterative decoder if the channel is viewed as a non-redundant convolutional code. The turbo equalizer is different from classic a turbo-like code, however, in that the 'channel code' adds no redundancy and therefore can only be used to remove non-gaussian noise.

In information theory, a polar code is a linear block error-correcting code. The code construction is based on a multiple recursive concatenation of a short kernel code which transforms the physical channel into virtual outer channels. When the number of recursions becomes large, the virtual channels tend to either have high reliability or low reliability, and the data bits are allocated to the most reliable channels. It is the first code with an explicit construction to provably achieve the channel capacity for symmetric binary-input, discrete, memoryless channels (B-DMC) with polynomial dependence on the gap to capacity. Notably, polar codes have modest encoding and decoding complexity O(n log n), which renders them attractive for many applications. Moreover, the encoding and decoding energy complexity of generalized polar codes can reach the fundamental lower bounds for energy consumption of two dimensional circuitry to within an O(nε polylog n) factor for any ε > 0.

References

  1. ↑ Minoli, Daniel (2008-12-18). Satellite Systems Engineering in an IPv6 Environment. CRC Press. pp. 152–. ISBN   9781420078695 . Retrieved 4 June 2014.
  2. ↑ Ryan, William; Lin, Shu (2009-09-17). Channel Codes: Classical and Modern. Cambridge University Press. pp. 320–. ISBN   9781139483018 . Retrieved 4 June 2014.
  3. ↑ "Patent US6023783 - Hybrid concatenated codes and iterative decoding - Google Patents". Google.com. Retrieved 2014-06-04.
  4. ↑ "Archived copy" (PDF). Archived from the original (PDF) on 2017-08-13. Retrieved 2014-04-02.{{cite web}}: CS1 maint: archived copy as title (link)
  5. ↑ "Allerton98.tex" (PDF). Retrieved 2014-06-04.
  6. ↑ NASA.gov
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.