无冗余的抗干扰编码方法

本发明涉及一种无冗余的抗干扰编码方法，是一种提高数据包传输效率的高效编码方法，关于无线网 络数据包传输编码技术，特别关于一种新型的无线网络数据广播业务中的数据包传输编码方法，属于数据 通信传输编码技术领域。

在无线网络里传输数据包，由于信号衰弱，信道间的干扰和冲突，丢失数据包是不可避免的。对于无 线数据包广播业务或者多播业务，例如蜂窝网络中的文本分发，手机固件更新或升级，如果接收端无法得 到所有完整的数据包，那么将无法享受广播业务，例如无法得到文本，手机固件更新或升级失败。因此无 线数据广播业务需要考虑接收端接收数据包的完整性。

由于广播业务的特殊性，其网络拓扑是一对多的，也就是说一个数据发送端，多个数据接收端。同时 由于不同数据接收端处于相异的物理环境中，所经历的无线环境参数不一样，因此数据丢包率是不同的， 从而导致了接收端接收到的数据包存在差异，例如发送端广播了10个数据包p1，p2，…，p10，由于接收端A 和接收端B所处的环境不一样，A接收到的数据包可能是p1，p3，p5，p7，p9，B接收到的数据包可能是 p2，p4，p6，p8，p10。如果要保证接收端A和B都能够实现发送端的广播业务，那么发送端还需要发送数据 包使得接收端A收到p2，p4，p6，p8，p10，接收端B收到p1，p3，p5，p7，p9。

传统的方法是发送端通过ARQ(自动重传请求)来保证所有接收端都收到这10个数据包。对于数据 包pi(1≤i≤10)，如果接收端收到该数据包，那么其反馈告知发送端，当发送端接收到所有接收端针对pi 的反馈，那么发送端开始发送pi+1，否则发送端重传pi。虽然发送端通过ARQ可以保证所有接收端都收 到数据包，但是这种方法会造成很大的传输冗余，例如已经收到pi数据包的接收端可能会再次收到数据包 pi，从而浪费了正确的数据包传输。

纠删编码(Erasure Code)通过进行数据包间的编码，使得每次传输的数据包尽量避免与已收到的数 据包重复，从而减少重复的数据包传输，提高数据包传输的效率，表格.1是用于说明减少重复数据包传输 的一个简单例子。在表格.1中，发送端需要将p1，p2发送给接收端A和接收端B，当发送端发送p1时， 只有B接收到了数据包p1，当发送端发送p2时，只有A接收到了数据包p2。当传输完p1，p2后，发送端 并没有重复发送p1或者p2，而是发送了p1⊕p2，当A和B接收到p1⊕p2后通过异或操作可以得到p1和 p2。如果发送端重复发送p1或者p2，那么A和B中至少有一个会收到两个p1或者p2，从而浪费了一次 正确的数据包传输。

数据包 接收端A 接收端B

p1 错误 正确

p2 正确 错误

p1⊕p2 正确 正确

表格.1

对于接收端而言，要正确接收10个数据包必须至少通过10次正确的数据包传输。本发明标题中所述 的冗余是指正确传输数据包次数与接收端所需正确传输数据包次数的差。例如发送端需要发送10个数据 包给接收端，如果接收端通过11次正确的数据包传输才能够解码出发送端需要传输的10个数据包，那么 接收端接收到了1个无用的编码数据包，那么此编码方法对于该接收端的编码冗余就是1。

本发明编码方法属于无冗余的抗干扰编码方法，保证了接收端只需要与接收端所需正确数据包相同数 量的数据包传输次数就能完成传输，编码冗余为零。例如，发送端需要发送10个数据包，那么接收端只 需要通过10次正确的数据包传输，就能够通过对接收到的这10个编码数据包进行解码，得到发送端需要 传输的10个数据包。因此接收端不会正确接收无用的编码数据包，从而不会造成对数据包传输的浪费。

现有的纠删编码分为两类：有码率编码和率编码。假设发送端要发送k个数据包p1，p2，…，pk， 发送端通过编码产生N(N≥k)个编码数据包c1，c2，…，cN。有码率编码的N是个有限值，而率编码 的N是无穷大。

在传统的有码率编码中，RS(Reed-Solomon)码是一种MDS(Maximum Distance Separable)码，其 将k个数据包通过编码矩阵MN×k来获得N个编码数据包，编码过程如数学式.1所示：

数学式.1

其中编码矩阵MN×k中的元素aij(1≤i≤k，1≤j≤N)属于有限域Fq。矩阵MN×k具有MDS性质，即 从矩阵的N个行向量中任意抽取任意k行所得到的k个行向量是线性无关的。

RS码每次传输一个数据包就从MN×k中抽取一个编码行向量与k个数据包做有限域Fq中的内积运 算，得到的内积作为编码数据包c。由于MDS性质，接收端只要正确接收到k个编码后的数据包后就能 够通过求解k×k维接收编码矩阵M*(由k个编码数据包的编码行向量)的逆矩阵来求出原来的k个数据 包，其解码过程如数学式.2运算所示：

数学式.2

对于RS码来说，接收端只需要正确接收k个编码后的数据包就能够完全解出k个发送端需要传输的 数据包，因此RS码是无冗余的。但是对于无线网络而言，由于丢包的存在，如果接收端丢失数据包的数 量超过了N-k个，那么其正确接收到的编码数据包将会小于k个，从而无法正确解出任意一个数据包， 导致接收端浪费了已经正确接收到的数据包，造成了更大的资源损失。

率编码解决了RS码因丢失过多数据包而无法正确解码的问题，其能够产生无穷多个码字，保证
了接收端能收到足够的码字用于解码，例如喷泉码(Fountain code)。喷泉码在k个数据包p₁，p₂，…，p_k中
依照一定的概率分布选择m个数据包进行异或运算，并将异或完的数据包作为编码数据包发送。编码过程
中选择的数据包可以用一个向量表示，例如代表p₁，p₂被选中。编码数据包在传输之
前发送端会在包头添加向量的信息，接收端在接收到码字后会提取此向量信息用于解码。

接收端解码过程和RS码原理一致，都是通过矩阵求逆来获得。在喷泉码解码中，接收端解码所依据
的向量就是在数据包头添加的每当接收端接收到编码数据包，首先提取数据包包头的编码向量将
其写入编码矩阵，通过优化的矩阵求逆运算来求解逆矩阵。由于编码是按照一定概率分布产生的数据包异
或值，编码会产生冗余，例如这三个向量是线
性相关的，导致三个向量中有一个向量不起任何作用，浪费了一次数据包传输。目前应用广泛的喷泉码所
应用的概率分布会导致码字中含有巨大的冗余编码数据包，从而引入了数量庞大的冗余数据包的传输，造
成了无线传输资源很大的浪费。

在现有编码方法中，RS码虽然具有MDS性质，但是由于码率有限而无法保证接收端在丢包网络里能 够接收足够的编码数据包，从而无法保证正确解码；而喷泉码虽然码率无限可以保证接收端正确解码，但 是不具备MDS性质导致编码方法存在巨大的冗余，造成数据包传输不必要的浪费。本专利提出的编码方 法，既拥有RS码编码无冗余的优点，也拥有喷泉码保证接收端正确解码的优点，因此本专利编码方法在 保证接收端能够正确解码的情况下，达到了无冗余的数据传输。

本发明的目的是提出适合于无线网络广播业务的抗干扰传输编码方法，以克服无线广播业务中由于无 线丢包导致的业务质量下降的问题，并且解决现有编码方法存在的正确解码与冗余度控制兼顾问题，在保 证接收端能够正确解码的情况下，达到了无冗余的数据传输，提高无线网络中广播服务的传输可靠性和业 务质量。

本发明提出的无冗余的抗干扰编码方法，用于将需要传输的k个数据包p1，p2，…，pk编码成Ns个编 码数据包。本发明的编码方法利用Ns个编码数据包，保证了接收端能够正确解码，同时这Ns个数据包不 存在编码冗余。本编码方法包括以下步骤：

(1)确定编码矩阵Mc的大小：在获得了发送端需要传输的k个数据包后，本发明编码方法确定用于 对这k个数据包进行编码的编码矩阵Mc所含向量的个数Ns。

(2)确定编码矩阵Mc中元素所属的有限域：本发明编码过程中矩阵的元素是在有限域中进行运算， 有限域的大小(有限域中元素的数量)直接影响着有限域运算的复杂度。在确定完编码矩阵Mc的大小后， 需要对运算的有限域进行确定。本发明编码提出使Mc满足MDS性质的有限域大小区间，并设计了保证 Mc矩阵MDS性质的最小有限域大小和有限域的运算，获得最小的计算复杂度。

(3)确定编码矩阵Mc中的所有元素值：通过确定了Mc矩阵的大小和矩阵元素运算有限域的大小后， 构造Mc的元素保证Mc具有MDS的性质。

(4)数据包编码：在确定了编码矩阵Mc后，本发明编码方法利用编码矩阵对需要进行传输的数据 包进行编码。

(5)确定编码传输机制：在对数据包进行编码后获得了编码数据包，本发明通过带反馈的编码传输 机制保证了利用此编码方法能够保证所有接收端正确解码。

本发明提出的无冗余的抗干扰编码方法，其优点是：

与现有编码方法相比，本发明所提出的编码方法既有编码矩阵拥有MDS性质，保证了编码方法没有 冗余的优点，并且又能够保证接收端能够完全正确解码。同时，本发明的编码方法编码过程所涉及到的有 限域大小和有限域运算复杂度低，非常利于实现，具有很好的应用前景。

图1显示数据包编码从发送端到接收端的传输过程

图2显示本编码方法具体步骤

本发明提出的无冗余的抗干扰编码方法，其流程框图如附图1所示，将需要传输的k个数据包
p₁，p₂，…，p_k编码成N_s个编码数据包包括以下组成部分：

(1)为了保证所有接收端能够正确解码，发送端根据接收端数Nu和数据包数k确定编码矩阵的大小 为[Ns，k]，其中(Ns＝Nu×k)。由于无线丢包会造成现有编码方法在接收端无法正确解码的后果，表格.2 所示的是在至少有接收端正确接收数据包的情况下，接收端接收数据包最坏的情况，每次数据包传输只有 一个接收端能够接收到数据包。对于Nu个接收端和k个数据包，在以上最差的情况下至少需要Nu×k个 编码数据包来保证每个接收端都能通过正确接收k个编码数据包来正确解码p1，p2，…，pk。当 Ns≥Nu×k时，编码矩阵也能够保证接收端正确解码，但是实现更复杂，为便于实现的考虑，选择 Ns＝Nu×k。

时隙 用户1 用户2 用户3

1 正确 错误 错误

2 错误 正确 错误

3 错误 错误 正确

表格.2

(2)要保证[N_s，k]大小的编码矩阵M^c具备MDS的性质，即在M^c中N_s个行向量中任取k个行向
量是线性无关的。而在有限域F_q中，有限域的大小为q，在k维的有限域空间中，将中最大的一
个MDS子空间的大小记为S，即中任意k个向量线性无关，在S＞＞k时具有
q+1≤S≤q+k-1的性质，即S-k+1≤q≤S-1。要保证M^c中的N_s个向量具备MDS性质，并且使
得有限域的大小最小，可以取S＝N_s，因此有限域的大小q≥N_s-k+1＝N_u×k-k+1。为便于实现，
取q≥N_s，同时将有限域用比特表示，假设2^r-1≤N_S≤2^r，那么就将有限域的大小q设定为q＝2^r。那
么在有限域中必定能构造得到一个[N_s，k]大小的具有MDS性质的M^c矩阵。而且由于是便于实现
的最小的有限域，使得编码矩阵M^c的运算复杂度最小，实现最简单，便于实际应用。在有限域中，
加法通过异或实现(XOR)，乘法如数学式.3所示。乘法可以通过加法实现，而加法只需做简单的异或操
作，使得运算复杂度很低，便于实现。根据乘法的分配率，通过数学式.3得到有限域内的任意乘法。
(a_p，…，a_i，…，a₀)·(0_p，…，1_i，…，0₀)＝(a_p-i，…，a₀⊕a_p，…，a_p-i-2⊕a_p-i-1，a_p-i-1)

数学式.3

(3)通过部分(1)和(2)确定编码矩阵M^c为在有限域中的一个[N_s，k]矩阵，本发明编码方法
在中构造一个大小为[2^r，k]的范德蒙矩阵M_V，如数学式.4所示，其中是有限域中
的2^r个元素，由此M_V的任意k个行向量线性无关。在M_V中任取N_s个行向量便可构成编码矩阵M^c。

数学式.4

(4)利用构造好的MDS编码矩阵M^c对数据包p₁，p₂，…，p_k进行编码。通过矩阵行变换将M^c转化
成如数学式.5所示的形式，数学式.5中的I_k×k在数学式.6中表示。编码过程即将中的行向量与数
据包向量[p₁，p₂，…，p_k]做有限域中的向量内积运算，得到的内积做为编码数据包进行传输，运算过程
如数学式.7所示。在传输之前，在编码数据包包头添加用于编码的中相应行向量的信息。

$M_c^c={\left[\begin{array}{c}{I}_{k\times k}\\ M_{(N_s-k)\times k}^r\end{array}\right]}_{N_s\times k}$

数学式.5

数学式.6

$[c_1,c_2,...,c_{N_s}]=M_c^c·[p_1,p_2,...,p_k]$

数学式.7

(5)本发明编码方法要求接收端在正确接收到编码数据包时能够反馈给发送端一个信号Fs，例如高 电平信号。在某个数据包传输期间，发送端传输码字ci(1≤i≤Ns)给Nu个接收端。当接收端正确接收到ci 时，接收端反馈信号Fs，如果接收端没有正确接收到ci，接收端将不做任何操作。发送端在传输下个数据 包之前检测是否有来自接收端的反馈信号Fs，如果检测到Fs，那么发送端在下一个数据包传输时传输码 字ci+1，如果没有检测到Fs，那么发送端在下一个数据包传输时传输码字ci。由于Fs具有可叠加的特性， 例如高电平叠加高电平还是一个高电平信号，因此多个接收端同时反馈Fs的时候不会造成反馈的冲突，具 有很好的实际应用前景。

(6)本发明编码方法要求接收端在正确解得k个数据包p1，p2，…，pk后发给发送端一个完成传输的 确认消息，当发送端收到所有Nu个接收端的确认消息后，完成并停止本次传输。

附图2显示了本发明方法的具体实施步骤：

步骤S702：发送端获取需要传输的k个数据包p1，p2，…，pk。

步骤S704：根据数据包数k和接收端数Nu确定编码矩阵的大小。

步骤S706：确定编码矩阵元素所属有限域大小和有限域运算。

步骤S708：根据步骤S704和S706的得到的有限域和矩阵来确定编码矩阵的所有元素值。

步骤S710：利用得到的编码矩阵对数据包进行编码以产生码字用以传输。

步骤S712：发送端根据是否检测到接收端的反馈信号Fs来进行编码。

步骤S714：发送端在没有检测到Fs时，应用本次已经传输过的码字进行重传。

步骤S716：发送端检测是否所有接收端已经正确解码k个数据包p1，p2，…，pk。

步骤S718：发送端在检测到Fs时，应用之前没有使用过的新的码字进行传输。

步骤S720：发送端在确定是否检测到Fs后应用步骤S714或S718产生的码字进行传输。

步骤S722：发送端检测到所有接收端已经正确解码k个数据包p1，p2，…，pk时，完成并停止本次数据 传输。

以上虽以具体实施步骤说明本发明，但并不因此限定本发明的范围，只要不脱离本发明的要旨，该行 业者所进行的各种变形或变更，皆属于本发明的保护范围，本发明的保护范围以权利要求书所限定的范围 为准。