[关闭]
@zhongdao 2018-09-28T10:25:03.000000Z 字数 17573 阅读 3300

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

前向纠错（FEC）是一种用于增强数据可靠性的数字信号处理技术。它通过在数据传输或存储之前引入称为纠错码的冗余数据来实现这一点。FEC为接收器提供纠正错误的能力，而无需反向信道来请求重传数据。

第一个FEC代码，称为汉明码，是在20世纪50年代初引入的。这是一种在数据传输中获得差错控制的方法，其中发送器发送冗余数据。接收器仅识别没有明显错误的一部分数据。这允许广播数据从单个源发送到多个目的地。

前向错误编码也称为信道编码。

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).
在电信，信息理论和编码理论，前向纠错 （FEC）或信道编码1是一种用于技术控制误差在数据传输在不可靠的或有噪声的通信信道。中心思想是发送者通过使用纠错码（ECC）以冗余方式对消息进行编码。

https://en.wikipedia.org/wiki/Forward_error_correction
https://en.wikipedia.org/wiki/Error_correction_code

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

纠错码

纠错码
一个纠错码（ECC）或前向纠错（FEC）码是添加的方法的冗余数据，或奇偶校验数据，对一个消息，例如，它可以由接收器中回收甚至当错误的数目（最多在传输过程中或在存储过程中引入了所使用代码的能力。由于接收器不必要求发送器重传数据，因此在前向纠错中不需要反向信道，因此它适用于诸如广播的单工通信。纠错码经常用于较低层通信，以及CD，DVD，硬盘和RAM等媒体中的可靠存储。

通常在卷积码和块码之间区分纠错码：

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

允许的实际最大码率取决于所使用的纠错码，并且可能更低。这是因为Shannon的证明只是存在性的，并没有说明如何构造既优化又具有有效编码和解码算法的代码。

Example

Transmission without interleaving:

  1. Error-free message:         aaaabbbbccccddddeeeeffffgggg
  2. Transmission 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:

  1. Error-free code words:                              aaaabbbbccccddddeeeeffffgggg
  2. Interleaved:                                        abcdefgabcdefgabcdefgabcdefg
  3. Transmission with a burst error:                    abcdefgabcd____bcdefgabcdefg
  4. Received 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:

  1. Original transmitted sentence:                      ThisIsAnExampleOfInterleaving
  2. Received sentence with a burst error:               ThisIs______pleOfInterleaving

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

With interleaving:

  1. Transmitted sentence:                               ThisIsAnExampleOfInterleaving...
  2. Error-free transmission:                            TIEpfeaghsxlIrv.iAaenli.snmOten.
  3. Received sentence with a burst error:               TIEpfe______Irv.iAaenli.snmOten.
  4. 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.

教程：前向纠错

前向纠错（FEC）编码模块来演示字节级计算
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

介绍fec的不错文章

使用前向纠错来改善数据通信
https://www.electronicdesign.com/communications/use-forward-error-correction-improve-data-communications

https://www.google.com/search?q=forward+error+correction+example&sa=X&ved=0ahUKEwjwvqbdyMbdAhWWwcQHHXknDHkQ1QIInQEoAA

介绍视频：
https://www.youtube.com/watch?v=CtrlGsD9Xow

开源 前向纠错

ldpc
http://radfordneal.github.io/LDPC-codes/

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
https://web.archive.org/web/20110309072849/http://www.chuchusoft.com:80/par2_tbb/download.html

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.

image_1cnnt4jmm3sndb0csa1rvq1jg6m.png-866.5kB

ldpc

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

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

new article outlines

错误检测与纠正
https://zh.wikipedia.org/wiki/%E9%94%99%E8%AF%AF%E6%A3%80%E6%B5%8B%E4%B8%8E%E7%BA%A0%E6%AD%A3
https://en.wikipedia.org/wiki/Error_detection_and_correction

定义：
https://www.techopedia.com/definition/821/error-correction

采用什么code的确认。

基本原理，示意
https://www.jianshu.com/p/93d2935ab7ed

摘录，然后重点实现验证一个代码示例。
翻译，运行：
前向纠错（FEC）编码模块来演示字节级计算
http://liquidsdr.org/doc/tutorial-fec/

文件级， 写信问作者：
https://en.wikipedia.org/wiki/Parchive

传输及文件级别 写信问作者，应用可行性， license.
http://planete-bcast.inrialpes.fr/articled77b.html?id_article=1#flute_tool_anchor

查看现有专利情况 google patents

查看自己原来写的卫星多播专利

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.
本教程将通过引入前向纠错（FEC）编码模块来演示字节级计算（原始消息数据）。请注意，液体liquid(一个开源的数字信号处理库，特别为基于嵌入式平台的软件无线电设计) 仅提供一些非常基本的FEC功能，包括一些汉明块码和重复码。虽然这些代码非常快且足以开始使用，但它们效率不高并且在不提供强大级别的校正功能的情况下增加了大量冗余。 如果安装在您的机器上，liquid 将使用libfec中描述的卷积和Reed-Solomon代码。

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.
噪声信道上的数字通信可能不可靠，导致接收器出错。前向纠错（FEC）编码为原始数据消息增加了冗余，允许在接收器处纠正一些错误。代码的纠错能力取决于许多因素，但通常通过增加添加到消息的冗余量来改进。增加大量冗余的缺点是通信速率降低，因为必须在重要数据信息和冗余比特之间共享链路。然而，好处是接收器更有可能在不必请求重传消息的情况下纠正错误。已经编写了大量关于某些FEC编码器/解码器对（编解码器）的纠错能力及其在各种环境中的性能的研究论文和书籍。虽然这里要讨论的主题信息太多，但重要的是要注意这一点 liquid 实现了一小部分简单的FEC编解码器，包括几个汉明和重复码。如果在 配置 liquid 时安装了 libfec库，则 此列表将扩展为卷积和Reed-Solomon代码。

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.
在本教程中，您将创建一个简单的程序，它将生成一条消息，使用简单的汉明（7,4）代码对其进行编码，通过添加错误来破坏编码消息，然后尝试使用解码器纠正错误。

搭建环境 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:
创建一个新文件 fec.c 并使用您喜欢的编辑器打开它。包括标题 stdio.h 和 liquid / liquid.h 并添加 int main（） 定义，以便您的程序如下所示：

  1. #include <stdio.h>
  2. #include <liquid/liquid.h>
  4. int main() {
  5.     printf("done.\n");
  6.     return 0;
  7. }

Compile and link the program using gcc :
使用gcc编译和链接程序 ：

  1. $ 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

  1. $ ./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.
首先设置模拟参数：现在唯一的参数是输入消息的长度，由 表示字节数的变量 n （ unsigned int 类型）表示。将 n 初始化 为8，以表示8字节的原始消息。创建另一个unsiged int 类型变量 k ，它将表示编码后消息的长度。该长度等于原始的n加上附加冗余的长度 。现在，当我们没有加入FEC编码，设置 k 等于 n，这意味着没有任何冗余，接收器无法纠正任何错误, 下一节我们会调整k.

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 为此提供了方便的界面，可以调用，如下：

  1. unsigned int num_bit_errors = count_bit_errors_array(msg_org,
  2.                                                      msg_dec,
  3.                                                      n);

Print this number to the screen. Your program should look similar to this:
将此编号打印到屏幕上。您的程序看起来应该类似于：

  1. #include <stdio.h>
  2. #include <liquid/liquid.h>
  4. int main() {
  5.     // simulation parameters
  6.     unsigned int n = 8;             // original data length (bytes)
  8.     // compute size of encoded message
  9.     unsigned int k = n;             // (no encoding yet)
  11.     // create arrays
  12.     unsigned char msg_org[n];       // original data message
  13.     unsigned char msg_enc[k];       // encoded/received data message
  14.     unsigned char msg_dec[n];       // decoded data message
  16.     unsigned int i;
  17.     // create message
  18.     for (i=0; i<n; i++) msg_org[i] = i & 0xff;
  20.     // "encode" message (copy to msg_enc)
  21.     for (i=0; i<n; i++) msg_enc[i] = msg_org[i];
  23.     // corrupt encoded message (flip bit)
  24.     msg_enc[0] ^= 0x01;
  26.     // "decode" message (copy to msg_dec)
  27.     for (i=0; i<n; i++) msg_dec[i] = msg_enc[i];
  29.     printf("original message:  [%3u] ",n);
  30.     for (i=0; i<n; i++)
  31.         printf(" %.2X", msg_org[i]);
  32.     printf("\n");
  34.     printf("decoded message:   [%3u] ",n);
  35.     for (i=0; i<n; i++)
  36.         printf(" %.2X", msg_dec[i]);
  37.     printf("\n");
  39.     // count bit errors
  40.     unsigned int num_bit_errors = count_bit_errors_array(msg_org, msg_dec, n);
  41.     printf("number of bit errors received:    %3u / %3u\n", num_bit_errors, n*8);
  43.     return 0;
  44. }

Compile the program as before, creating the executable " fec ." Running the program should produce an output similar to this:
像以前一样编译程序，创建可执行文件“ fec” 。运行程序应该产生类似于这样的输出：

  1. original message:  [  8]  00 01 02 03 04 05 06 07
  2. decoded message:   [  8]  01 01 02 03 04 05 06 07
  3. number 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.
到目前为止，我们的程序不使用任何 液体 接口（用于计算位错误的函数除外）。液体中的FEC模块 提供了一个简单的界面，用于为项目添加前向纠错功能。所述 FEC 从位操作背后的粗砂细节对象摘要（包装/字节的拆包，附加尾部比特，等）纠错结构。例如，卷积码一次观察一个比特，而里德 - 所罗门码对整个比特块进行操作。液体中的 fec 对象 方便地从编解码器的组织中抽象出来并在内部处理这种开销。这允许通过一个简单的界面无缝集成不同的编解码器。如同 iirfilt_rrrf 在锁相环教程对象（[ 段教程-PLL ]）的 FEC 对象具有方法 创建（） ， 打印（）， 和 破坏（） 。几乎液体中的每一个物体 都有这些方法; 但是 fec 对象 用encode（） 和 decode（）替换 execute（）， 因为相同的对象实例可以用于编码和解码。该 fec_create（） 方法接受两个参数，尽管第二个参数基本上被忽略。第一个参数是您希望使用的编解码器类型的枚举。

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:
首先，创建一个LIQUID_FEC_HAMMING7 类型的新 fec对象 （第二个参数可以简单地为 NULL ），它创建一个汉明（7,4）代码

  1. 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

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.

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注