Labrador-LDPC

一个用于编码和解码一系列低密度奇偶校验（LDPC）错误纠正码的crate。目前支持CCSDS 231.1-O-1 TC码，速率r=1/2，尺寸k=128，k=256和k=512，以及CCSDS 131.0-B-2 TM码，速率r=1/2，r=2/3和r=4/5，尺寸k=1024和k=4096。

无依赖，no_std。旨在同时支持高性能解码和资源受限的嵌入式场景。

文档

仓库

C API

lib.rs:

Labrador-LDPC实现了LDPC错误纠正码的选择，包括编码器和解码器。

它旨在与Labrador的其他组件一起使用，但不依赖于任何东西（包括std），因此可以完全独立使用。它在严肃的计算机和小的嵌入式系统上都有相当高的效率。已考虑满足这两种用例。

此crate内部不进行内存分配，因此大多数方法都需要您传递一个已分配的内存块供其使用。请检查各个方法文档以获取更多信息。

示例

use labrador_ldpc::LDPCCode;

// Pick the TC128 code, n=128 k=64
// (that's 8 bytes of user data encoded into 16 bytes)
let code = LDPCCode::TC128;

// Generate some data to encode
let txdata: Vec<u8> = (0..8).collect();

// Allocate memory for the encoded data
let mut txcode = vec![0u8; code.n()/8];

// Encode, copying `txdata` into the start of `txcode` then computing the parity bits
code.copy_encode(&txdata, &mut txcode);

// Copy the transmitted data and corrupt a few bits
let mut rxcode = txcode.clone();
rxcode[0] ^= 0x55;

// Allocate some memory for the decoder's working area and output
let mut working = vec![0u8; code.decode_bf_working_len()];
let mut rxdata = vec![0u8; code.output_len()];

// Decode for at most 20 iterations
code.decode_bf(&rxcode, &mut rxdata, &mut working, 20);

// Check the errors got corrected
assert_eq!(&rxdata[..8], &txdata[..8]);

代码

命名法：我们用n表示码长（每个码字要传输的比特数），用k表示码维数（每个码字的可用信息比特数），用r表示速率 k/n，即每传输比特的可用信息比特数。

提供了一系列长度和速率的代码。当前的代码来自两套CCSDS建议，它们的TC（遥控）短长度低速率代码，以及它们的TM（遥测）长长度多速率代码。这些都是在性能良好的标准化的已发布代码。

TC代码有r=1/2的速率和k=128，k=256和k=512的尺寸。它们是CCSDS文件231.1-O-1及其后续修订中定义的相同代码（尽管n=256的代码最终被删除，但它在这里作为非常有用的代码继续存在）。

TM代码有r=1/2，r=2/3和r=4/5的速率，尺寸为k=1024和k=4096。它们是CCSDS文件131.0-B-2及其后续修订中定义的相同代码。

有关代码本身的更多信息，请参阅CCSDS出版物： https://public.ccsds.org/

可用的代码是 LDPCCode 枚举的变体，而其他所有内容（编码器、解码器、实用方法）都作为此枚举的方法实现。

我应该选择哪种代码？对于短且高度可靠的消息，TC代码是有意义的，特别是如果需要在嵌入式平台等受限制的系统上解码时。对于大多数其他数据传输，TM代码更加灵活，通常更适合。

由于生成生成矩阵的复杂性和涉及到的非常长的常量，没有包括非常大的k=16384 TM代码，但从理论上讲，可以包括它们。相关的校验位常量已经包括在内。

生成矩阵

要编码一个码字，我们需要一个生成矩阵，它是一个形状为k行n列的大型二进制矩阵。对于要编码的数据中每个被设置的位，我们将其对应行的生成矩阵相加以找到输出码字。由于所有我们的码都是 系统的，我们的码字的前k位正好是输入数据，这意味着我们只需要在码字的末尾编码最后的n-k校验位。

这些最后的n-k列的生成矩阵以紧凑的形式存储，其中只存储少量最后的行，其余的可以在运行时推断出来。我们的编码器方法直接使用这种紧凑形式，因此它永远不会被展开。

相关的常量在 codes.compact_generators 模块中，名称如 TC128_G。

校验矩阵

这是上一节中生成矩阵的对偶。它们由解码器用于确定哪些位是错误的并需要更改。当完全展开时，它们是一个大矩阵，具有n-k行（每个校验一个），n列（每个输入数据位或变量一个）。由于这些特定码的构造方式，我们可以以极紧凑的形式存储和使用它们。

常量在 codes.compact_parity_checks 中，并反映了CCSDS文档中定义的构造。

编码器

在 LDPCCode 上实现了两种编码方法：encode 和 copy_encode。

copy_encode 是一个方便的包装器，它首先将您的数据复制到编码字内存中，然后按常规执行编码。相比之下，encode 要求您的数据已位于编码字内存的起始位置，并且只需在末尾填充校验位。复制并不需要太多时间，因此使用哪个更方便。

编码方法需要您传递一个分配的编码字内存的切片，&mut [T]，它必须是恰好 n 位长。您可以将其作为 u8、u32 或 u64 的切片传递。通常，较大的类型将编码速度快3倍，因此通常值得使用它们。它们被解释为包含小端的数据，因此您可以在所有小端系统（也就是说，大多数系统）上直接在 &[u8] 和更大的解释之间进行转换。

编码方法总是返回对码字内存的 &mut [u8] 视图，如果您需要这种类型进行进一步使用（例如通过无线电传输），或者如果您忽略返回值，您可以继续使用原始的码字内存切片。

let code = LDPCCode::TC128;

// Encode into u32, but then access results as u8
let mut codeword: [u32; 4] = [0x03020100, 0x07060504, 0x00000000, 0x00000000];
let txcode = code.encode(&mut codeword);
assert_eq!(txcode, [0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
                    0x34, 0x99, 0x98, 0x87, 0x94, 0xE1, 0x62, 0x56]);

// Encode into u64, but maintain access as a u64 afterwards
let mut codeword: [u64; 2] = [0x0706050403020100, 0x0000000000000000];
code.encode(&mut codeword);
assert_eq!(codeword, [0x0706050403020100, 0x5662E19487989934]);

每个码字编码所需的内存（以字节为单位）

    | =k/8        | =n/8            |

TC128 | 8 | 16 | 32 TC256 | 16 | 32 | 64 TC512 | 32 | 64 | 128 TM1280 | 128 | 160 | 1024 TM1536 | 128 | 192 | 1024 TM2048 | 128 | 256 | 1024 TM5120 | 512 | 640 | 4096 TM6144 | 512 | 768 | 4096 TM8192 | 512 | 1024 | 4096

解码器

有两种解码器可用

• 低内存解码器 decode_bf 使用硬信息的位翻转算法。这可能比最佳解码低 1 或 2dB，但需要更少的 RAM，并且通常要快几倍。它只在非常慢或可用内存非常少的情况下才真正有用。
• 高性能解码器 decode_ms 使用带软信息的修改后的最小和解码算法进行近最佳解码，尽管速度较慢且内存开销较大。该解码器可以在各种软信息类型上运行，相应的内存开销也各不相同。

使用每个码字解码所需的内存（以字节为单位）

    | (`bf`, RAM) | (`mp`, RAM) | (RAM)    | (text)       | (RAM)         | (RAM)
    | =n/8        | =n*T        | =(n+p)/8 |              |               |

TC128 | 16 | 128T | 16 | 132 | 128 | 1280T + 8 TC256 | 32 | 256T | 32 | 132 | 256 | 2560T + 16 TC512 | 64 | 512T | 64 | 132 | 512 | 5120T + 32 TM1280 | 160 | 1280T | 176 | 366 | 1408 | 12160T + 48 TM1536 | 192 | 1536T | 224 | 366 | 1792 | 15104T + 96 TM2048 | 256 | 2048T | 320 | 366 | 2560 | 20992T + 192 TM5120 | 640 | 5120T | 704 | 366 | 5632 | 48640T + 192 TM6144 | 768 | 6144T | 896 | 366 | 7168 | 60416T + 384 TM8192 | 1024 | 8192T | 1280 | 366 | 10240 | 83968T + 768

T 反映了您的软信息类型的大小：对于 i8 这是 1，对于 i16 2，对于 i32 和 f32 它是 4，对于 f64 它是 8。您应该使用与您的软信息质量相称的类型；例如，通常 i16 就足够了。

两个解码器都需要相同大小的输出存储和奇偶校验常量。 bf 解码器接受较小的硬输入，工作区域也较小，而 mp 解码器需要软输入，并在内部使用软信息，需要更大的工作区域。

所需大小既可以在 CodeParams 常量中在编译时获得，也可以在 LDPCCode 上的方法如 decode_ms_working_len() 中在运行时获得。因此，您可以在运行时静态或动态分配所需内存。

请参阅各个解码器方法以获取更多关于其要求的详细信息。

位翻转解码器

本解码器基于原始的Gallagher解码器。它不是很优化，但运行速度快。其思路是查看哪些位连接到未满足的最大奇偶校验数，然后翻转这些位，并迭代直到情况好转。然而，这个例程不能纠正删除（它只知道位翻转）。所有TM码都是打孔的，这意味着一些奇偶校验位未传输，因此在接收器处未知。我们使用一个单独的算法来首先解码删除，基于Archonta、Kanistras和Paliouras的一篇论文，doi:10.1109/MOCAST.2016.7495161。

消息传递解码器

这是一个修改后的最小和解码器，它根据奇偶校验矩阵连接到它的其他位来计算每个位被设置的概率。它接受软信息，因此本质上也涵盖了打孔码。这个实现基于Savin描述的一个实现，arXiv:0803.1090。它既合理高效（不需要atahn），并且性能非常接近最优的乘积和解码。