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

<span class="mw-page-title-main">Enhanced Data rates for GSM Evolution</span> Digital mobile phone technology

Enhanced Data rates for GSM Evolution (EDGE), also known as 2.75G, Enhanced GPRS (EGPRS), IMT Single Carrier (IMT-SC), and Enhanced Data rates for Global Evolution, is a digital mobile phone technology that allows improved data transmission rates as a backward-compatible extension of GSM. EDGE is considered a pre-3G radio technology and is part of ITU's 3G definition. EDGE was deployed on GSM networks beginning in 2003 – initially by Cingular in the United States.

<span class="mw-page-title-main">Error detection and correction</span> 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 (EDAC) 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, including consumer technologies such as MiniDiscs, CDs, DVDs, Blu-ray discs, QR codes, Data Matrix, 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 code 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 in 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.

In coding theory, the repetition code is one of the most basic linear error-correcting codes. In order to transmit a message over a noisy channel that may corrupt the transmission in a few places, the idea of the repetition code is to just repeat the message several times. The hope is that the channel corrupts only a minority of these repetitions. This way the receiver will notice that a transmission error occurred since the received data stream is not the repetition of a single message, and moreover, the receiver can recover the original message by looking at the received message in the data stream that occurs most often.

In computing, 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.

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.

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.

<span class="mw-page-title-main">Amplitude and phase-shift keying</span>

Amplitude and phase-shift keying (APSK) is a digital modulation scheme that conveys data by modulating both the amplitude and the phase of a carrier wave. In other words, it combines both amplitude-shift keying (ASK) and phase-shift keying (PSK). This allows for a lower bit error rate for a given modulation order and signal-to-noise ratio, at the cost of increased complexity, compared to ASK or PSK alone.

A soft-in soft-out 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. Polar codes were developed by Erdal Arikan, a professor of electrical engineering at Bilkent University.

References

  1. ↑ Minoli, Daniel (2008). "5 Error Correction Techniques §5.1.4 Turbo Codes". Satellite Systems Engineering in an IPv6 Environment. CRC Press. pp. 152–. ISBN   9781420078695 . Retrieved 4 June 2014.
  2. ↑ Ryan, William; Lin, Shu (2009). "7.3 Serial-Concatenated Convolutional Codes". Channel Codes: Classical and Modern. Cambridge University Press. pp. 320–. ISBN   9781139483018 . Retrieved 4 June 2014.
  3. ↑ USExpired 6023783,Dariush Divsalar&Fabrizio Pollara,"Hybrid concatenated codes and iterative decoding",issued 2000-02-08
  4. ↑ Benedetto, S.; Divsalar, D.; Montorsi, G.; Pollara, F. (August 15, 1996). "Serial Concatenation of Interleaved Codes: Performance Analysis, Design, and Iterative Decoding" (PDF). TDA Progress Report 42-126. Archived from the original (PDF) on 2017-08-13. Retrieved 2014-04-02.
  5. ↑ Divsalar, Dariush; Jin, Hui; McEliece, Robert J. (1998). "Coding Theorems for "Turbo-Like" Codes" (PDF). Jet Propulsion Laboratory, California Institute of Technology. Retrieved 2014-06-04.
  6. ↑ Divsalar, D.; Dolinar, S.; Pollara, E (2000). "Serial Turbo Trellis Coded Modulation with Rate-1 Inner Code" (PDF). Globecom '00 - IEEE. Global Telecommunications Conference. doi:10.1109/GLOCOM.2000.891245. ISBN   0-7803-6451-1. Archived from the original (PDF) on 2010-05-29.
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.