|
'''Serial concatenated convolutional codes''' ('''SCCC''') are a class of [[forward error correction]] (FEC) codes highly suitable for [[Turbo code|turbo]] (iterative) decoding.<ref name="Minoli2008">{{cite book|last=Minoli|first=Daniel|title=Satellite Systems Engineering in an IPv6 Environment |chapter=5 Error Correction Techniques §5.1.4 Turbo Codes |chapter-url=https://books.google.com/books?id=4yJi1UQDPp8C&pg=PA152|accessdate=4 June 2014|date=2008 |publisher=CRC Press|isbn=9781420078695|pages=152–}}</ref><ref name="RyanLin2009">{{cite book|last1=Ryan|first1=William|last2=Lin|first2=Shu|title=Channel Codes: Classical and Modern |chapter=7.3 Serial-Concatenated Convolutional Codes |chapter-url=https://books.google.com/books?id=0gwqxBU_t-QC&pg=PA320|accessdate=4 June 2014|date=2009 |publisher=Cambridge University Press|isbn=9781139483018|pages=320–}}</ref> 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.
{{AFC submission|||ts=20140403163912|u=Mrcodeguy|ns=2}}
{{afc comment|1=Illustrations or diagrams are not connected. [[User:Aggie80|The Ukulele Dude - Aggie80]] ([[User talk:Aggie80|talk]]) 20:52, 3 April 2014 (UTC)}}
----
SCCC'sSCCCs typically include an [[inner code ]], an [[outer code ]], and a linking interleaver. A distinguishing feature of SCCC'sSCCCs 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. ▼
SerialThe concatenatedanalysis convolutionalof SCCCs was spawned in part by the earlier discovery of [[turbo codes ]] in 1993. This analysis of (SCCC )'s weretook analyzedplace in the 1990's1990s in a series of publications from NASA's [[Jet Propulsion LaboratoriesLaboratory]] ( [[JPL ]]). ThisThe research yieldedoffered 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 ]]. The analysis of SCCC's was spawned in part by the earlier discovery of [[turbo codes]] in 1993. ▼== Serial Concatenated Convolutional Codes ==
Prior forms of [[Concatenated error correction code|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 ([[Soft-in soft-out decoder|SISO]]) decoding. SISO decoding is considered essential for turbo decoding. ▼▲Serial concatenated convolutional codes (SCCC) were analyzed in the 1990's in a series of publications from NASA's Jet Propulsion Laboratories ([[JPL]]). This research yielded 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]]. The analysis of SCCC's was spawned in part by the earlier discovery of [[turbo codes]] in 1993.
Serial concatenated convolutional codes have not found wide spreadwidespread commercial use, although they were proposed for communications standards such as [[DVB-S2]]. Nonetheless, the analysis of SCCC'sSCCCs has provided insight into the performance and bounds of all types of iterative decodable codes including [[turbo codes]] and [[LDPC]] codes. {{Citation needed|date = June 2014}}▼▲SCCC's typically include an inner code, an outer code, and a linking interleaver. A distinguishing feature of SCCC's 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.
US patent 6,023,783 covers some forms of SCCCs. The patent expired on May 15, 2016.<ref>{{cite patent |url=https://www.google.com/patents/US6023783 |country=US |number=6023783 |invent1=Dariush Divsalar |invent2=Fabrizio Pollara |status=Expired |title=Hybrid concatenated codes and iterative decoding |gdate=2000-02-08}}</ref>
▲Prior forms of [[Concatenated error correction code|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 ([[Soft-in soft-out decoder|SISO]]) decoding. SISO decoding is considered essential for turbo decoding.
▲Serial concatenated convolutional codes have not found wide spread commercial use, although they were proposed for communications standards such as [[DVB-S2]]. Nonetheless, the analysis of SCCC's has provided insight into the performance and bounds of all types of iterative decodable codes including [[turbo codes]] and [[LDPC]] codes.
US patent [https://www.google.com/patents/US6023783 6,023,783] covers some forms of SCCC's. This patent will expire on May 15, 2016.
== History ==
Serial concatenated convolutional codes were first analyzed viewwith 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.<ref>{{Cite web |url=http://www.systems.caltech.edu/EE/Courses/EE127/EE127C/handout/serial.pdf |id=TDA Progress Report 42-126 |date=August 15, 1996
"|title=Serial Concatenation of Interleaved Codes: Performance Analysis, Design, and Iterative Decoding"<ref> |first1=S. |last1=Benedetto |first2=D. |last2=Divsalar |first3=G. |last3=Montorsi |first4=F. |last4=Pollara |access-date=2014-04-02 |archive-date=2017-08-13 |archive-url=https://web.archive.org/web/20170813054421/http://www.systems.caltech.edu/EE/Courses/EE127/EE127C/handout/serial.pdf |url-status=dead }}</ref> by S. Benedetto, [http://coding.jpl.nasa.gov/index.php/ddivsalar D. Divsalar], G. Montorsi and F. Pollara. 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 "the use of a recursive convolutional inner encoder always yields an interleaver gain."{{Clarify|date=June 2014}} 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 SCCC'sSCCCs was done in "Coding Theorems for 'Turbo-Like' Codes" by D. Divsalar, Hui Jin, and Robert J. McEliece.<ref>{{cite web|url=http://www.mif.vu.lt/~skersys/vsd/turbo/Allerton98.pdf</ref> by|title=Coding D.Theorems for "Turbo-Like" Codes
|first1=Dariush |last1=Divsalar, |first2=Hui |last2=Jin, and |first3=Robert J. |last3=McEliece. |publisher=Jet Propulsion Laboratory, California Institute of Technology |date=1998 |accessdate=2014-06-04}}</ref> 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".<ref>{{cite conference |url=http://trs-new.jpl.nasa.gov/dspace/bitstream/2014/18647/1/99-2030.pdf |title=Serial Turbo Trellis Coded Modulation with Rate-1 Inner Code |first1=D. |last1=Divsalar |first2=S. |last2=Dolinar |first3=E |last3=Pollara |book-title=Globecom '00 - IEEE. Global Telecommunications Conference |date=2000 |doi=10.1109/GLOCOM.2000.891245 |isbn=0-7803-6451-1 |archive-url=https://web.archive.org/web/20100529020555/http://trs-new.jpl.nasa.gov/dspace/bitstream/2014/18647/1/99-2030.pdf |archive-date=2010-05-29 }}</ref> In this paper SCCC'sSCCCs 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.
[[File:SCCC_EncoderSCCC Encoder.png|thumb|none|500px|Fig. 1. SCCC Encoder]]
The example encoder is comprisedcomposed 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 codescode 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. ▼
▲The example encoder is comprised 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 codes 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 interativeiterative SCCC decoder.
[[File:SCCC_DecoderSCCC Decoder.png|thumb|none|500px|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.
== LDPC Encoder ==
Figure X provides an illustration of the functional components of most LDPC encoders.
[[File:LDPC encoder Figure.png|thumb|none|500px|Fig. 1. LDPC Encoder]]
During the encoding of a frame, the input data bits (D) are repeated and distributed to a set of constituent encoders. The constituent encoders are typically accumulators and each accumulator is used to generate a parity symbol. A single copy of the original data D is transmitted (S) with the parity bits (P) to make up the code symbols. The S bits from each constituent encoder are discarded.
In some cases a parity bit is encoded by a second constituent code (serial concatenation), but more typically the constituent encoding for the LDPC is done in parallel.
In an example using the DVB-S2 rate 2/3 code the encoded block size is 64800 symbols (N=64800) with 42300 data bits (K=43200) and 21600 parity bits ( M=21600). Each constituent code (check node) encodes 16 data bits except for the first party bit which encodes 8 data bits. The first 4680 data bits are repeated 13 times (used in 13 parity codes), while the remaining data bits are used in 3 parity codes (irregular LDPC code).
For comparison, classic turbo codes typically use two convolutional codes of moderate depth (8 or 16 state) configured in parallel, each of which encodes the entire input block (K) of data bits. These constituent encoders are combined with a code interleaver which interleaves one copy of the frame to generate the parity symbols.
The LDPC, in contrast, uses many low depth (2 state) 'convolutional codes' (accumulators) in parallel, each of which encode only a small portion of the input frame. The many constituent codes are connected via the repeat and distribute operations which perform the function of the interleaver in the turbo code.
The ability to more precisely manage the connections of the various constituent codes and the level of redundancy for each input bit give more flexibility in the design of LDPC codes, which can lead to slightly better performance than turbo codes in some instances. Turbo codes still seem to perform better than LDPCs at low code rates, or at least the design of good performing low rate codes is easier for Turbo Codes.
As a practical matter, the hardware that forms the accumulators is reused during the encoding process. That is, once a first set of party bits are generated and the parity bits stored, the same accumulator hardware is used to generate a next set of parity bits.
== Performance ==
SCCC'sSCCCs 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 ==
* [[BCJR algorithm]]
* [[Low-density parity-check code]]
* [[Repeat-accumulate code]]
* [[Turbo equalizer]]
== External links ==
*{{cite journal |first=Dave |last=Forney |date=2009 |journal=Scholarpedia |volume=4 |issue=2 |page=8374 |title=Concatenated codes|doi=10.4249/scholarpedia.8374 |bibcode=2009SchpJ...4.8374F |doi-access=free }}
[*{{cite web |url=http://www.mif.vu.lt/~skersys/vsd/turbo/ryan_chapter.pdf "|title=Concatenated Convolutional Codes and Iterative Decoding ", |first=Willian E. |last=Ryan ] |publisher=Department of Electrical & Computer Engineering, University of Arizona |date=2001}}▼
[[Category:Data]]
[http://www.scholarpedia.org/article/Concatenated_codes "Concatenated codes", Scholarpedia]
[[Category:Error detection and correction]]
[[Category:Encodings]]
▲[http://www.mif.vu.lt/~skersys/vsd/turbo/ryan_chapter.pdf "Concatenated Convolutional Codes and Iterative Decoding", Willian E. Ryan]
== Serial Concatenated Convolutional Codes ==
| 