@zhongdao 2018-09-28T10:25:03.000000Z 字数 17573 阅读 2665

# FEC & LDPC

未分类

# Error detection and correction

https://en.wikipedia.org/wiki/Error_detection_and_correction

Redundant data, sent by transmitter is also called error correction code

# Forward Error Correction Codes

In telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding1 is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is the sender encodes the message in a redundant way by using an error-correcting code (ECC).

Common Forward Error Correction Codes:
* Convolutional Codes
* Block Codes (e.g. Reed-Solomon Code)
* Trellis-Coded-Modulation (TCM)
* Concatenated Codes

## 纠错码

• 卷积码是逐位处理的。它们特别适合在硬件中实现，维特比解码器允许最佳解码。
• 块代码在逐块的基础上处理。块代码的早期示例是重复代码，汉明码和多维奇偶校验码。它们之后是许多有效的代码，由于目前广泛使用，Reed-Solomon代码是最值得注意的。Turbo码和低密度奇偶校验码（LDPC）是相对较新的结构，可以提供几乎最佳的效率。

Shannon定理是前向纠错中的一个重要定理，描述了在具有一定误差概率或信噪比（SNR）的信道上可能进行可靠通信的最大信息速率。该严格的上限以信道容量表示。更具体地说，该定理说存在这样的代码，使得随着编码长度的增加，只要码率小于信道容量，就可以使离散无记忆信道上的误差概率任意小。码率定义为分数K / N的ķ源符号和Ñ 编码符号。

## Example

Transmission without interleaving:

Error-free message:         aaaabbbbccccddddeeeeffffggggTransmission with a burst error: aaaabbbbccc____deeeeffffgggg

Here, each group of the same letter represents a 4-bit one-bit error-correcting codeword. The codeword cccc is altered in one bit and can be corrected, but the codeword dddd is altered in three bits, so either it cannot be decoded at all or it might be decoded incorrectly.

With interleaving:

Error-free code words:                              aaaabbbbccccddddeeeeffffggggInterleaved:                                        abcdefgabcdefgabcdefgabcdefgTransmission with a burst error:                    abcdefgabcd____bcdefgabcdefgReceived code words after deinterleaving:           aa_abbbbccccdddde_eef_ffg_gg

In each of the codewords aaaa, eeee, ffff, gggg, only one bit is altered, so one-bit error-correcting code will decode everything correctly.

Transmission without interleaving:

Original transmitted sentence:                      ThisIsAnExampleOfInterleavingReceived sentence with a burst error:               ThisIs______pleOfInterleaving

The term "AnExample" ends up mostly unintelligible and difficult to correct.

With interleaving:

Transmitted sentence:                               ThisIsAnExampleOfInterleaving...Error-free transmission:                            TIEpfeaghsxlIrv.iAaenli.snmOten.Received sentence with a burst error:               TIEpfe______Irv.iAaenli.snmOten.Received sentence after deinterleaving:             T_isI_AnE_amp_eOfInterle_vin_...

No word is completely lost and the missing letters can be recovered with minimal guesswork.

## 教程：前向纠错

http://liquidsdr.org/doc/tutorial-fec/

Error Detection and Correction
https://www.slideshare.net/TechiNerd/error-detection-and-correction-36618963

A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems''
http://web.eecs.utk.edu/~plank/plank/papers/CS-96-332.html

Reed–Solomon_error_correction
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

Reed-Solomon Codes
An introduction to Reed-Solomon codes: principles, architecture and implementation
http://www.cs.cmu.edu/~guyb/realworld/reedsolomon/reed_solomon_codes.html

## 开源 前向纠错

turbo, reed-solomon,
http://itpp.sourceforge.net/4.3.1/tutorial.html

### 文件级

https://en.wikipedia.org/wiki/Parchive

par2cmdline 0.4 with Intel Threading Building Blocks 2.2

par2cmdline
https://github.com/Parchive/par2cmdline

### code级别

https://aff3ct.github.io/

## fcast / flute

http://planete-bcast.inrialpes.fr/articled77b.html?id_article=1#flute_tool_anchor

## Software for error-correcting codes

AFF3CT(A Fast Forward Error Correction Toolbox): a full communication chain in C++ (many supported codes like Turbo, LDPC, Polar codes, etc.), very fast and specialized on channel coding (can be used as a program for simulations or as a library for the SDR).

IT++: a C++ library of classes and functions for linear algebra, numerical optimization, signal processing, communications, and statistics.

OpenAir: implementation (in C) of the 3GPP specifications concerning the Evolved Packet Core Networks.

## openfec

http://openfec.org/
http://openfec.org: because open, free AL-FEC codes and codecs matter
You'll find there codecs for Application-Level Forward Erasure (AL-FEC) Codes.

# ldpc

https://en.wikipedia.org/wiki/Low-density_parity-check_code

https://www.slideshare.net/s4h4rr/ldpc-codes-34889266

# new article outlines

http://liquidsdr.org/doc/tutorial-fec/

https://en.wikipedia.org/wiki/Parchive

http://planete-bcast.inrialpes.fr/articled77b.html?id_article=1#flute_tool_anchor

# FEC教程翻译（含程序示例)

Tutorial: Forward Error Correction

## 前言

This tutorial will demonstrate computation at the byte level (raw message data) by introducing the forward error-correction (FEC) coding module. Please note that liquid only provides some very basic FEC capabilities including some Hamming block codes and repeat codes. While these codes are very fast and enough to get started, they are not very efficient and add a lot of redundancy without providing a strong level of correcting capabilities. liquid will use the convolutional and Reed-Solomon codes described in libfec , if installed on your machine.

## Problem Statement

Digital communications over a noisy channel can be unreliable, resulting in errors at the receiver. Forward error-correction (FEC) coding adds redundancy to the original data message that allows for some errors to be corrected at the receiver. The error-correction capability of the code is dependent upon many factors, but is usually improved by increasing the amount of redundancy added to the message. The drawback to adding a lot of redundancy is that the communications rate is decreased as the link must be shared among the important data information as well as the redundant bits. The benefit, however, is that the receiver has a better chance of correcting the errors without having to request a retransmission of the message. Volumes of research papers and books have been written about the error-correction capabilities of certain FEC encoder/decoder pairs (codecs) and their performance in a variety of environments. While there is far too much information on the subject to discuss here, it is important to note that liquid implements a very small subset of simple FEC codecs, including several Hamming and repeat codes. If the libfec library is installed when liquid is configured this list extends to convolutional and Reed-Solomon codes.

In this tutorial you will create a simple program that will generate a message, encode it using a simple Hamming(7,4) code, corrupt the encoded message by adding an error, and then try to correct the error with the decoder.

## 搭建环境 Setting up the Environment

Create a new file fec.c and open it with your favorite editor. Include the headers stdio.h and liquid/liquid.h and add the int main() definition so that your program looks like this:

#include <stdio.h>#include <liquid/liquid.h>int main() {    printf("done.\n");    return 0;}

Compile and link the program using gcc :

$gcc -Wall -o fec fec.c -lm -lc -lliquid The flag " -Wall " tells the compiler to print all warnings (unused and uninitialized variables, etc.), " -o fec " specifies the name of the output program is " fec ", and " -lm -lc -lliquid " tells the linker to link the binary against the math, standard C, and liquid DSP libraries, respectively. Notice that the above command invokes both the compiler and the linker collectively. If the compiler did not give any errors, the output executable fec is created which can be run as 标志“ -Wall ”告诉编译器打印所有警告（未使用和未初始化的变量等），“ - o fec ”指定输出程序的名称为“ fec ”，“ - lm -lc -lliquid ”告诉链接器分别将二进制数据与数学，标准C和 liquid DSP库相链接。请注意，上面的命令共同调用编译器和链接器。如果编译器没有给出任何错误， 则创建可以作为运行 的输出可执行文件 fec $ ./fec

and should simply print " done. " to the screen. You are now ready to add functionality to your program.

We will now edit the file to set up the basic simulation by generating a message signal and counting errors as a result of channel effects. The error-correction capabilities will be added in the next section.

First set up the simulation parameters: for now the only parameter will be the length of the input message, denoted by the variable n ( unsigned int ) representing the number of bytes. Initialize n to 8 to reflect an original message of 8 bytes. Create another unsigned int variable k which will represent the length of the encoded message. This length is equal to the original ( n ) with the additional redundancy. For now set k equal to n as we are not adding FEC coding until the next section. This implies that without any redundancy, the receiver cannot correct for any errors.

Message data in liquid are represented as arrays of type unsigned char . Allocate space for the original, encoded, and decoded messages as msg_org[n] , msg_enc[k] , and msg_dec[n] , respectively. Initialize the original data message as desired. For example, the elements in msg_org can contain 0,1,2,...,n-1 . Copy the contents of msg_org to msg_enc . This effectively is a placeholder for forward error-correction which will be discussed in the next section. Corrupt one of the bits in msg_en c (e.g. msg_enc[0] \verb|$|= 0x01; will flip the least-significant bit in the first byte of the msg_enc array), and copy the results to msg_dec . Print the encoded and decoded messages to the screen to verify that they are not equal. Without any error-correction capabilities, the receiver should see a message different than the original because of the corrupted bit. Count the number of bit differences between the original and decoded messages. liquid provides a convenient interface for doing this and can be invoked as liquid 中的 消息数据 表示为unsigned char类型的数组。分配原始，编码和解码消息的空间，分别为msg_org [n] ， msg_enc [k] 和 msg_dec [n]。根据需要初始化原始数据消息。例如，msg_org中的元素 可以包含 0,1,2，...，n-1 。将msg_org的内容复制 到 msg_enc 。这实际上是前向纠错的占位符，将在下一节中讨论。损坏msg_en c中的一个位 （例如 msg_enc [0] \ verb |$ | = 0x01; 将翻转msg_enc 数组的第一个字节中的最低有效位 ，并将结果复制到 msg_dec 。将编码和解码的消息打印到屏幕以验证它们不相等。如果没有任何纠错功能，因为损坏的位，接收器receiver应该会看到与原始消息不同的消息。计算原始消息和已解码消息之间的位差数。 liquid 为此提供了方便的界面，可以调用，如下：

unsigned int num_bit_errors = count_bit_errors_array(msg_org,                                                     msg_dec,                                                     n);

Print this number to the screen. Your program should look similar to this:

#include <stdio.h>#include <liquid/liquid.h>int main() {    // simulation parameters    unsigned int n = 8;             // original data length (bytes)    // compute size of encoded message    unsigned int k = n;             // (no encoding yet)    // create arrays    unsigned char msg_org[n];       // original data message    unsigned char msg_enc[k];       // encoded/received data message    unsigned char msg_dec[n];       // decoded data message    unsigned int i;    // create message    for (i=0; i<n; i++) msg_org[i] = i & 0xff;    // "encode" message (copy to msg_enc)    for (i=0; i<n; i++) msg_enc[i] = msg_org[i];    // corrupt encoded message (flip bit)    msg_enc[0] ^= 0x01;    // "decode" message (copy to msg_dec)    for (i=0; i<n; i++) msg_dec[i] = msg_enc[i];    printf("original message:  [%3u] ",n);    for (i=0; i<n; i++)        printf(" %.2X", msg_org[i]);    printf("\n");    printf("decoded message:   [%3u] ",n);    for (i=0; i<n; i++)        printf(" %.2X", msg_dec[i]);    printf("\n");    // count bit errors    unsigned int num_bit_errors = count_bit_errors_array(msg_org, msg_dec, n);    printf("number of bit errors received:    %3u / %3u\n", num_bit_errors, n*8);    return 0;}

Compile the program as before, creating the executable " fec ." Running the program should produce an output similar to this:

original message:  [  8]  00 01 02 03 04 05 06 07decoded message:   [  8]  01 01 02 03 04 05 06 07number of bit errors received:      1 /  64

Notice that the decoded message differs from the original and that the number of received errors is nonzero.

## 创建编码器/解码器 Creating the Encoder/Decoder

So far our program doesn't use any liquid interfaces (except for the function used to count bit errors). The FEC module in liquid provides a simple interface for adding forward error-correction capabilities to your project. The fec object abstracts from the gritty details behind the bit manipulation (packing/unpacking of bytes, appending tail bits, etc.) of error-correction structures. As an example, convolutional codes observe bits one at a time while Reed-Solomon codes operate on entire blocks of bits. The fec object in liquid conveniently abstracts from the organization of the codec and takes care of this overhead internally. This allows seamless integration of different codecs with one simple interface. As with the iirfilt_rrrf object in the phase-locked loop tutorial ( [section-tutorial-pll] ) the fec object has methods create() , print() , and destroy() . Nearly every object in liquid has these methods; however the fec object replaces execute() with encode() and decode() as the same object instance can be used for both encoding and decoding. The fec_create() method accepts two arguments, although the second one is basically ignored. The first argument is an enumeration of the type of codec that you wish to use.

To begin, create a new fec object of type LIQUID_FEC_HAMMING7 4 (the second argument can simply be NULL ) which creates a Hamming(7,4) code:

fec q = fec_create(LIQUID_FEC_HAMMING74, NULL);

Details of the available codes in liquid can be found in [section-fec] . This codec nominally accepts 4 bits, appends 3 parity bits, and can detect and correct up to one of these seven transmitted bits. The Hamming(7,4) code is not particularly strong for its rate; however it is computationally efficient and has been studied extensively in coding theory. The interface provided by liquid conveniently abstracts from the process of managing 8-bit data symbols (bytes), converting to 4-bit input symbols, encoding to 7-bit output symbols, and then re-packing into 8-bit output bytes. This is consistent with any forward error-correction code in liquid ; as the user, you simply see data bytes in and data bytes out. The length of the output sequence can be computed using the method

unsigned int k = fec_get_enc_msg_length(LIQUID_FEC_HAMMING74, n);
where n represents the number of uncoded input bytes and k represents the number of encoded output bytes. This value should be used to appropriately allocate enough memory for the encoded message. Encoding the data message is as simple as invoking

fec_encode(q, n, msg_org, msg_enc);
which uses our newly-created fec object q to encode n input bytes in the array msg_org and store the result in the output array msg_enc . The interface for decoding is nearly identical:

fec_decode(q, n, msg_enc, msg_dec);
Notice that the second argument again represents the number of uncoded data bytes ( n ). Don't forget to destroy the object once you are finished:

fec_destroy(q);
Final Program
The final program is listed below, and a copy of the source is located in the doc/tutorials/ subdirectory.

# include

int main() {
// simulation parameters
unsigned int n = 8; // original data length (bytes)
fec_scheme fs = LIQUID_FEC_HAMMING74; // error-correcting scheme

// compute size of encoded message
unsigned int k = fec_get_enc_msg_length(fs,n);

// create arrays
unsigned char msg_org[n];   // original data message
unsigned char msg_enc[k];   // encoded/received data message
unsigned char msg_dec[n];   // decoded data message

// CREATE the fec object
fec q = fec_create(fs,NULL);
fec_print(q);

unsigned int i;
// generate message
for (i=0; i<n; i++)
msg_org[i] = i & 0xff;

// encode message
fec_encode(q, n, msg_org, msg_enc);

// corrupt encoded message (flip bit)
msg_enc[0] ^= 0x01;

// decode message
fec_decode(q, n, msg_enc, msg_dec);

// DESTROY the fec object
fec_destroy(q);

printf("original message:  [%3u] ",n);
for (i=0; i<n; i++)
printf(" %.2X", msg_org[i]);
printf("\n");

printf("decoded message:   [%3u] ",n);
for (i=0; i<n; i++)
printf(" %.2X", msg_dec[i]);
printf("\n");

// count bit errors
unsigned int num_bit_errors = count_bit_errors_array(msg_org, msg_dec, n);
printf("number of bit errors received:    %3u / %3u\n", num_bit_errors, n*8);

printf("done.\n");
return 0;


}
The output should look like this:

fec: Hamming(7,4) [rate: 0.571]
original message: [ 8] 00 01 02 03 04 05 06 07
decoded message: [ 8] 00 01 02 03 04 05 06 07
number of bit errors received: 0 / 64
done.
Notice that the decoded message matches that of the original message, even though an error was introduced at the receiver. As discussed above, the Hamming(7,4) code is not particularly strong; if too many bits in the encoded message are corrupted then the decoder will be unable to correct them. Play around with changing the length of the original data message, the encoding scheme, and the number of errors introduced.

For a more detailed program, see examples/fec_example.c in the main liquid directory. [section-fec] describes liquid 's FEC module in detail. Additionally, the packetizer object extends the simplicity of the fec object by adding a cyclic redundancy check and two layers of forward error-correction and interleaving, all of which can be reconfigured as desired. See [section-framing-packetizer] and examples/packetizer_example.c for a detailed example program on how to use the packetizer object.

• 私有
• 公开
• 删除