前言

本文原作者为 Daniel Estévez，业余无线电呼号EA4GPZ / M0HXM。他是一位知识渊博的业余爱好者和射频工程师，他所做的工作对译者启发很大，具有很大的开创性。

欢迎访问他的博客获取更多内容：XXXXXXXXXXXXXXXXXXXXX

原文链接：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

正文

SSDV是一种业余的数字图像传输协议。它以数据包的形式传输图像，并且对丢包具有一定的容忍性。它基于JPEG图像格式，但和它又不大相同。即使丢失少量数据，JPEG 图像也可能整体损坏。而在SSDV中，图像中的不同部分是独立压缩的，这意味着丢包只会影响对应的图像部分，其他的部分仍然可以正常解码并显示，尽管会出现一些代表了数据丢失的块状损毁。

（详可参见译者所写的介绍文章：SSDV—面向不可靠信道的数字图像传输设计）

SSDV最初是为业余高空气球任务所设计的，但后来也应用于卫星任务，就例如中国的月球轨道业余卫星龙江二号。

尽管SSDV对丢包有一定的容忍性，但是如果想要完整的图片，仍然要接收到全部数据包。如果一部分数据包丢失了，则需要重新发送。本文将介绍一种针对擦除信道下SSDV传输的前向纠错方案，该方案向后兼容SSDV，其发送的前 k 个数据包与标准SSDV完全相同，其后则有若干的FEC前向纠错数据包。这使得只要成功接收总数量为 k 的任意数据包即可恢复完整图像（因此不存在为了冗余所造成的编码上的额外开销）。

这些 FEC 数据包类似喷泉码，最多可以生成2^16 个不同的数据包，不过这一上限在实际应用中几乎无法达到。

研究背景与其应用

设计这个 FEC 方案的主要动机来自于龙江二号任务。该卫星（又称 DSLWP-B）搭载了一台小型相机，可以通过遥控命令按需使用 SSDV 传输图像。其下行速率一般只有 125 bps，因此传输一张图像往往需要 20～30 分钟。漏收少量 SSDV 数据包是很常见的现象。即使使用荷兰的Dwingeloo 25 米射电望远镜进行接收，在信噪比较高的情况下，仍然会遇到诸如星上 TCXO 频率跳变等偶发问题导致接收错误。

一些情况下，图像中丢失的部分是已知完全黑暗的天空部分；但在另一些情况下，丢失的区域则极具价值。此时，我们会尝试通过发送遥控命令，赶在星载存储器中的图像被新图像覆盖之前让卫星重新发送缺失的数据包，以获得完整的图像。我们有两种选择，可以发送遥控命令，让卫星从某个包处重新开始传输；也可以发送遥控命令，让卫星单独传输某个特定的数据包。

如果只丢失了几个数据包，第一种选择似乎太浪费了。但在实际操作中，它反而是最实用的方案。由于遥控链路速率低且可靠性有限，在发现某个数据包丢失后遥控卫星从这里开始重发，通常比逐一发送指令请求重发十几个特定包更加高效。此外，统计每幅图像具体缺失了哪些数据包，本身也是一个耗时且容易出错的过程。

本文提出的 FEC 方案正是为这种场景量身定做的。假设一幅 SSDV 图像由 k 个数据包组成，使用该 FEC 算法，只要接收到 k 个任意的图像数据包或FEC数据包，就能够恢复完整图像。这意味着如果我们丢失了d 个数据包，只需要遥控卫星发送 d 个新的 FEC 数据包（可以多发一些以防再次丢包）即可。我们无需指定具体缺失的数据包编号，而这正是我们无法通过单条遥控指令完成补发的原因（因为该指令需要携带所有缺失包的编号列表，这将导致指令过长）。

此外，在首次发送图像时，也可以发送 k+l 个数据包，而非标准的 k 个。这样，我们即使丢失了 l 个数据包，也无需重传即可成功解码完整图像。参数 l 可以在任务过程中根据实际的数据丢失率进行动态调整。这一方法同样适用于无法进行重传遥控的场景，例如大多数高空气球载荷。

FEC 算法

本文介绍的 FEC 算法是一种在 GF(2^16) 域上构建的系统化里德-所罗门 (2^16, k) 码，用以在擦除信道下进行前向纠错。它也可以作为一种喷泉码使用，因为原始的 k 个数据块可以被编码为 2^16 个数据块，并具有如下特性：只要接收到k 个任意的数据包，就可以恢复出完整的原始数据。而在实际操作中，并不需要生成或传输全部 2^16 个编码块。2^16 这个数值仅代表了可生成的互不相同的编码块总数上限。在未达到该上限的应用场景中，可供提取的新编码块池看起来就像真正的喷泉码一样“无穷无尽”。

算法过程如下：

假设我们对 GF(2^16) 的元素进行编号：

给定一条消息：

首先，构造一个次数不超过 k−1 的多项式 p(x)∈GF(2^16)[x]，使得：

该多项式可以通过求解一个范德蒙德矩阵对应的线性方程组，或使用拉格朗日插值法得到。

其编码结果为：

其中：

由于构造方式的原因，当 j=0,…,k−1 时，有

因此该码是系统码。

在解码阶段，只要接收到任意 k 个不同索引的编码符号：

就可以唯一确定一个次数不超过 k−1 的多项式 p(x)，满足：

由此即可恢复原始消息：

需要注意的是，接收端除了拥有 k 个编码符号外，还必须知道参数 k，以及每个符号对应的索引编号。

SSDV 数据包格式

SSDV 数据包的格式可参考官方文档：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

本文提出的 FEC 方案保持前 k 个数据包（系统部分）与标准 SSDV 完全一致，因此可以使用现有的 SSDV 解码软件，实时接收并显示图像。

这前 k 个数据包称为系统数据包（systematic packets）。

在其之后，可以继续生成并发送最多 2^16 个 FEC 数据包。当接收端累计收集到 k 个数据包（无论是系统包还是 FEC 包）后，即可恢复完整图像。需要注意的是：如果在系统数据包发送完毕时仍有数据包缺失，那么图像显示将不会继续更新；只有当收集到足够的 k 个数据包并完成 FEC 解码后，图像才会突然完整显示出来。

目前尚不清楚是否存在一种 FEC 方案，能够在尚未恢复全部擦除的情况下，逐步恢复部分缺失数据。大多数擦除型 FEC 要么完全恢复，要么完全无法恢复。

为了定义这一 FEC 方案的包格式，我将重点介绍龙江二号所使用的 SSDV 变体。龙江二号所使用的格式与标准 SSDV不同，同步字、数据包类型、呼号字段以及 SSDV 自带的 RS 码 FEC 数据均不进行传输，以节省带宽。

不过，在进行 CRC-32 校验计算时，这些字段仍被视为存在且取固定值。因此，这等效于在 CRC-32 计算中使用一个初始寄存器值 0x4EE4FDE1（这一寄存器值是这些隐含字段的“部分CRC”），而不是标准 SSDV 使用的 0xFFFFFFFF。（卫星上使用的SSDV编码器呼号为SORA，代表了龙江二号相机设计师的昵称“索拉”，译者注）

每个数据包中被擦除型 FEC 算法所保护的系统包字段包括 MCU 偏移量、MCU索引和有效载荷数据字段，总计208字节。幸运的是，它可以被2整除，因此需要保护的数据可以编码为104个 GF(2^16) 符号。（译者注：16位纠错算法中每个纠错单元，即符号为两字节。）

====以下部分由译者改写，以便读者理解====

此时我们可以得到如下的矩阵：

其中每一列对应一个数据包编号，从“包0”到“包k-1”，共k个；每一行对应数据包中的一个符号，从“符号0”到“符号103”，共104个。

本文所提及的擦除型 FEC 算法对矩阵的每一行分别进行了 FEC 运算，即取所有 k 个系统数据包中相同偏移的符号（同一字节位置的两个字节），把它们组合成一个符号序列。每个数据包中有104个符号，会产生104个符号序列。由算法依次对这104个符号序列进行基于范德蒙德矩阵或拉格朗日多项式的编码计算，可以计算出这些符号序列对应的 FEC 冗余符号，每个符号长2字节。这样，每个FEC数据包就形成了 104 组相互独立的纠错数据，每一组都跨越全部的系统数据包。如果矩阵中的某一列（即某个系统数据包）在传输中丢失，接收方就可以通过其他系统数据包和 FEC 数据包将其恢复。

====以上部分由译者改写，以便读者理解====

FEC 数据包包含了以下字段：

原型实现

我在 Jupyter Notebook 

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

中实现了这个 FEC 方案的原型，以展示算法的实际运行效果。原型中使用了 galois Python 包来进行 GF(2^16) 的有限域运算。Notebook 中使用的数据来自龙江二号在2019 年 7 月 2 日日食观测任务拍摄的一张 SSDV 图像。该图像共有65 个数据包（因此 k = 65）。

Notebook中 展示了几种不同的实验场景。其中一个较为极端的情况是：生成 2k 个数据包（即 65 个系统数据包 + 65 个 FEC 数据包），然后随机丢弃 50% 的数据包。

在使用标准 SSDV 解码器（仅使用系统数据包）处理这种情况时，图像恢复效果非常糟糕，即便图像的大部分区域都是完全黑色的：

仅接收29/65个系统化SSDV包的SSDV映像（使用标准SSDV解码器）

当我们使用擦除FEC解码器来处理系统化和FEC数据包时，能够恢复完整的图像：

从29个系统性数据包和36个FEC数据包中恢复的完整SSDV图像

为了确保不同实现之间的兼容性，需要明确以下约定：

1. 16 位比特串与 GF(2^16)元素之间的映射
   两个字节 B0、B1 应以 MSB 顺序组成 16 位比特串。

2. GF(2^16) 元素的枚举顺序
   

一种直接的方式是：将 

其中 p(x) 是一个 16 次不可约多项式，并将比特串

映射为多项式：

galois Python 包使用的 Conway 多项式为：

未来工作

我计划在未来编写这一 FEC 算法的 Rust 实现，并自行实现 GF(2^16) 的有限域运算。该实现将以 C 库形式提供 API/ABI，以便集成到现有 SSDV 软件中。

发表于：2023 年 5 月 20 日
作者：Daniel Estévez