![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
See stuffChCommunication for the basics.
Links:
The two main categories of forward-error-correction (FEC) codes are block codes and convolutional codes.[1]
Block codes work on fixed-sized blocks of symbols. The size is not arbitrary, but predetermined, for each code.[2]
Convolutional codes work on streams of arbitrary length.
" 1. Forward Error Correction (FEC) coding techniques are classified as either block codes or convolutional codes. The classification depends on the presence or absence of memory. 2. A block code has no memory, since it collects and therefore isolates k- bits in a buffer prior to processing: A. There is no retention within the encoding system of information related to the previous samples points (memoryless) . B. Each output codeword of an ( n,k ) block code depends only on the current buffer. 3. A convolutional coder may process one or more samples during an encoding cycle: A. The number of sample points collected prior to processing is far less than required for a block code. The delay through the encoder is therefore far less. B. The encoder acts on the serial bit stream as it enters the transmitter. C. Each bit in the output stream is not only dependent on the current bit, but also on those processed previously. This implies a form of memory. D. Its performance is less sensitive to Signal-to-Noise Ratio variations than that of block codes. In situations of limited power, where Signal-to-Noise Ratios would be a concern, the preferred method for achieving FEC is: Convolutional codes.
...
Convolutional error correcting codes are applied in applications that require good performance with low implementation cost. A. Easy implementation using a linear finite-state shift registers...to apply a polynomial to a stream of data...Convolutional codes pass the data to be transmitted through a special shift register. As the serial data is shifted through the shift register flip-flops, some of the flip-flop outputs are XORed together to form two outputs. ... Convolutional codes are typically decoded using the Viterbi algorithm, which increases in complexity exponentially with the constraint length: K. The Viterbi decoder is a Maximum Likelihood Sequence Estimator, that estimates the encoder state using the sequence of transmitted codewords.
" [atlantarf.com/Error_Control.php]
(Serial) Concatenated codes mean first using one type of coding on the signal and then using another type on the result. The first code is called the 'outer code' and the second is called the 'inner code' (you can remember which is which by the diagram outer_encode -> inner_encode -> raw channel -> inner_decode -> outer_decode). This provides a way to have both exponentially decreasing error probability with increasing block length (if the inner code has this property), while also having polynomial-time decoding complexity (if the outer code has this property)[3]. There are also 'parallel concatenated codes' in which multiple codes are generated, for example the multiple parity segments in Turbo Codes (see below).
Some error correcting codes have an 'error floor' which means that even if the signal-to-noise ratio is relatively good, the code will still make a few errors sometimes [4]. In this case, the code with an error floor can be used as an inner code and a code without an error floor can be used as an outer code to 'mop up' the residual errors [5] [6].
Good when the noise is bursty. "This is because it does not matter to the code how many bits in a symbol are in error — if multiple bits in a symbol are corrupted it only counts as a single error." [7]. Used a lot in optical media (CDs, DVDs).
Often used as the outer code of a concatenated code[8].
Hamming codes are perfect linear block codes. They can correct single-bit errors in a block. However, Hamming codes cannot detect double-bit errors. Extended Hamming codes can correct single bit errors and can also detect double-bit errors; this property is called SECDED (single error correction, double error detection). "Particularly popular is the (72,64) code, a truncated (127,120) Hamming code plus an additional parity bit, which has the same space overhead as a (9,8) parity code." [9].
The perfect binary Golay code, G_23, is a linear block code. It allows the correction of up to 3 bit errors. It is described as "23,12,7", meaning that each block has 23 bits, out of which 12 bits are the message (and the other 11 are check bits), and also that any pair of codewords (allowed blocks) differ in at least 7 locations.
The extended Golay code, G_24, described as "24, 12, 8", has blocks of 24 bits, out of which 12 bits are the message; any pair of codewords differ in at least 8 locations. This code can correct up to 3 bit errors, and also detect 4-bit errors or other even numbers of bit errors.
Ternary Golay codes are related codes over the ternary alphabet (0,1,2 instead of 0,1). The ternary Golay code is described as "[11 , 6 , 5]_3", meaning that the block length is 11 ternary bits, the message length is 6 ternary bits, and any pair of codewords differ in at least 5 locations. The ternary Golay code can correct up to 2 errors. The extended ternary Golay code is described as "[12,6,6]_3", meaning block length of 12 bits, message length of 6 bits, and any pair of codewords differ in at least 6 locations.
A nontrivial linear perfect code is either a repetition code, a Hamming code, or a Golay code (theorem by van Lint and Tietavainen [10] [11]). The ternary Golay code is the only known perfect non-binary code[12].
Based on the type of Google hits that come up, i get the sense that Golay codes are of more theoretical than practical interest, but i'm not sure. The extended binary Golay code was used in the Voyager spacecraft, so they are used at least sometimes.
Links:
"One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an algebraic method known as syndrome decoding. This simplifies the design of the decoder for these codes, using small low-power electronic hardware.
BCH codes are used in applications such as satellite communications, compact disc players, DVDs, disk drives, solid-state drives and two-dimensional bar codes.
...a Reed–Solomon? code is a BCH code where the decoder alphabet is the same as the channel alphabet." [13]
Popular (if complicated) codes that get close to the theoretical channel capacity ([14][15]).
Here's a representative example of a turbo code: a block code where in each block, the payload is transmitted, and then also two segments of parity data are transmitted (these three segments (payload, parity1, parity2) are interleaved). The first parity segment consists of parities calculated on the payload. The second parity segment consists of parities calculated on a known permutation of the payload. The decoder uses an iterative process similar to loopy belief propagation in a Bayesian network to combine information about the payload and both parities to try and come up with a good decoding [16]. This example would be placed in the class of parallel concatenated codes, because of the two parity segments.
Other codes using a similar iterative decoding process may be said to use 'turbo' decoding, but also 'iterative' decoding [17].
Many turbo codes are affected by an error floor, meaning that even if the signal-to-noise ratio is relatively good, the turbo code will still make a few errors sometimes, eg with some low-weight codewords [18].
Not popular but interesting in that it's a simplified turbo code (the paper called it a 'turbo-like' code). It can also be seen as a simple LDPC code. It is still complex to decode, however.
Steps: " 1) frame of information symbols of length N is repeated q times, resulting in a length qN frame.
2) A random (but fixed) permutation is applied to the resulting frame.
3) The permuted frame is fed to a rate-1 accumulator with transfer function 1 /(1 + D).
Divsalar et al. prefer to think of the accumulator as a rate-1 block code whose input block [x_1,...,x_qN] and output block [y_1,...,y_qN] are related by the following formula:
y_1 = x_1 y_2 = x_1 + x_2 ... y_qN = x_1 + x_2 + ... + x_qN
" [19] (with presumed typo corrected)
Pros and cons:
Pros:
Cons:
Links:
A capacity-approaching code. I'm not sure i understand these but i think that, like turbo codes, these are usually block codes in which you have a bunch of parity bits except that, instead of having the parity bits uniformally compute the parity of increasing prefixes of the input data, and then having one or more other sets of parity bits doing the same operation on permutation(s) of the input data, in LDPC you just take the parity of various random subsets of the input data bits.
Like turbo codes, they tend to have an error floor.
They yield similar performance to turbo codes [20]. Some say that LDPC is better for high code rates and turbo is better for low code rates [21].
Fountain codes are rateless erasure codes. In fountain codes, a potentially limitless sequence of encoded packets can be generated from the message to be transmitted, such that the original message can be recovered with high probability from any subset of the encoded packets roughly the same size as than the source message. This allows the transmitter to vary the level of redundancy ("code rate") at runtime; you can get more redundancy by just generating and transmitting more and more of these encoded packets. Because the code rate can vary, these are called 'rateless' codes. These are also classed as an 'erasure coding' method; meaning that it assumes that the channel has no errors, but may fail to deliver some messages. So these are 'rateless erasure codes'.
Tornado codes were the precursor to fountain codes. "LT codes were the first practical realization of fountain codes. Raptor codes and online codes were subsequently introduced, and achieve linear time encoding and decoding complexity through a pre-coding stage of the input symbols....Raptor codes are the most efficient fountain codes at this time" [22].
"Fountain codes are flexibly applicable at a fixed code rate, or where a fixed code rate cannot be determined a priori, and where efficient encoding and decoding of large amounts of data is required. One example is that of a data carousel, where some large file is continuously broadcast to a set of receivers." [23].
" Can collect data from multiple digital fountains for the same source seamlessly. Since each fountain has an “infinite” collection of packets, no duplicates. Relative fountain speeds unimportant; just need to get enough. Combined multicast/multigather possible. Can be used for BitTorrent?-like applications " [24]
also
" TCP has problems over long-distance connections. Packets must be acknowledged to increase sending window (packets in flight). Long round-trip time leads to slow acks, bounding transmission window. Any loss increases the problem. Using digital fountain + TCP-friendly congestion control can greatly speed up connections. Separates the “what you send” from “how much” you send. Do not need to buffer for retransmission. " [25]
" Setting: Web server with popular files, may have many open connections serving same file. Problem: has to have a separate buffer, state for each connection to handle retransmissions. Limits number of connections per server. Instead, use a digital fountain to generate packets useful for all connections for that file. Separates the “what you send” from “how much” you send. Do not need to buffer for retransmission. Keeps TCP semantics, congestion control. " [26]
I don't really understand the difference between LT codes, Raptor codes, and online codes. Here is one description, taken mostly from [27]:
The message is divided into blocks. A number of 'check blocks' are sent. Each check block is XOR of a random subset of message blocks (the receiver must be told which message blocks go with each check block; instead of sending this information with the check blocks, the 'random' subsets can be determined by the protocol, or they can be pseudorandomly selected but by a PseudoRandom? Number Generator determined by the protocol and whose seed is sent along with each check block (redundantly)).
The receiver must hold a large buffer of check blocks. When the receiver knows the contents of all but one of the message blocks that a check block XOR'd, then this allows the receiver to figure out the content of that other message block. Eventually the receiver gets enough check blocks to allow them to decode most of the message blocks. Alternately, i don't quite understand this part, but i think some sort of fancy belief propagation algorithm can be used to probabalistically predict the message, possibly allowing recovery from corrupted check blocks or fast approximate decoding or both.
Since real channels are noisy, not theoretical erasure channels (which lose packets but never corrupt them), an error-detecting code (such as a cyclic redundancy check (CRC)) should probably be applied to the message packets.
This can be used as the inner code of a concatenated code to allow the receiver to decode a few remaining blocks after most of the message blocks have been decoded.
Links:
I think some fountain codes are capacity-approaching but i'm not sure which ones, due to their inclusion in [28].
A capacity-approaching 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 (in other words, they polarize), and the data bits are allocated to the most reliable channels." [29]
" There are many aspects that polar codes should investigate further before considering for industry applications. Especially, the original design of the polar codes achieves capacity when block sizes are asymptotically large with successive cancellation decoder. However, in block sizes that industry applications are operating, the performance of the successive cancellation is poor compared to the well-defined and implemented coding schemes such as LDPC and Turbo. Polar performance can be improved with successive cancellation list decoding, but, their usability in real applications still questionable due to very poor implementation efficiencies.[4]
In October 2016 Huawei announced that it had achieved 27Gbps in 5G field trial tests using the Polar codes for channel coding. The improvements have been introduced so that the channel performance has now almost closed the gap to the Shannon limit which sets the bar for the maximum rate for a given bandwidth and a given noise level.[5]
In November 2016 3GPP agreed to adopt Polar codes for the eMBB (Enhanced Mobile Broadband) control channels for the 5G NR (New Radio) interface. At the same meeting 3GPP agreed to use LDPC for the corresponding data channel. [6] "
Links:
A class of codes which directly involve modulation, rather than just the transformation of a digital message (i think?).
Codes which involve transmitting on multiple channels (i think?).
