一种lt喷泉码编码度分布的构造方法
一种lt喷泉码编码度分布的构造方法
【技术领域】
[0001] 本发明是关于信息通信领域中利用数字喷泉码一LT喷泉码对信号进行编码时， 所使用的编码度分布的构造方法。
【背景技术】
[0002] 化hn Byers及Michael Luby等人于1998年提出了数字喷泉码的概念，为如何在 有限的网络带宽下处理可靠数据广播等问题给出了理想的解决方法。相对于传统的自动重 传请求机制，当出现数据包丢失的情况时，数字喷泉码并不需要发送大量的反馈信息告知 源端重新发送数据包，接收端只要再多接收一定数量的编码数据包就能够恢复原始数据。 送样避免了传输反馈信号时产生的延时，解决了广播应用中的反馈风暴问题。并且当有多 个接收端时，不同接收端之间接收到的错误信息都是相互独立的，因此接收端的数量可W 任意地增加或者减少，但并不会对彼此的译码性能造成影响。与传统前向纠错码相比，数字 喷泉码更能灵活地适应信道状况的变化。在运用传统纠错码时，首先要对信道的状况进行 估计，并W此为依据选取码长、码率等编码参数之后，再确定其编译码方式。然而由于信道 状态的不稳定性，当实际信道条件好于预估情况时，由于前向纠错码增加了过多的校验元， 降低了数据传输的有效性；相反，当信息在比预估情况更坏的实际信道进行传输时，前向纠 错码因不能提供更多的校验元而无法保证数据传输的可靠性。数字喷泉码的提出解决了上 述问题。利用数字喷泉码传输数据，接收端不用关必具体接收到了哪些正确的数据包W及 丢弃了哪些错误的编码数据包，只要接收端正确收到的编码数据包数量略微大于源数据包 的个数，它就可W完全恢复源信息。接收端在接收到足够多的编码数据包完成译码后，只需 向源端发送一个反馈信息，源端便停止编码。
[0003] 2002年Luby提出了第一种现实可行的喷泉码--LT码。LT码具有编译码方法 简单、译码开销和编译码复杂程度低的特点。其编码过程为；发送端原始数据由k个数据包 组成，根据某一编码度分布随机产生每个编码数据包的度d，然后从k个原始数据包中任意 地选择d个数据包，再将送d个数据包进行异或运算，从而生成一个编码数据包。编码器重 复操作送个过程就可W产生无限长的编码数据包流。LT码的译码一般采用置信传播译码算 法，其过程为；将接收到的一定数量的编码数据包与源数据包建立对应的双向图，任意地选 取一个度为1的数据包开始进行译码。由于度为1数据包就是对源数据包的复制，所W通 过简单的复制运算，就能恢复源数据包。然后，对已经恢复的源数据包，将它与其有关联的 所有编码数据包进行异或运算，更新送些编码数据包的值，再将恢复的源数据包和与它有 关联的编码数据包在Tanner图中所对应的边删除，使送些编码数据包的度数减1。W此循 环下去直到恢复所有原始数据为止。
[0004] 常用的编码度分布：
[0005] 1.理想孤子度分布
[0006] 理想孤子度分布理论上使每一个编码数据包在每一次译码迭代中释放的概率相 同，保证在每次迭代过程中有且只有一个度为1的编码数据包出现，完成每一次迭代恢复 一个源数据包，同时又有一个度为1的编码数据包出现。其度分布函数为：
[0007]
烘
[0008] 式中，P (d)为采用理想孤子度分布进行编码时，编码数据包的度为d(d = l，2,3...，k)的概率；k为源数据包数量。由其函数表达式可W看出，理想孤子度分布产生 的编码数据包中多数的度较小，但产生度1数据包的概率很小，仅为1A。在实际中，由于度 分布映射的随机性，在译码过程中很容易出现度1编码数据包消失；另一方面，产生度值较 大编码数据包的概率也较小，喷泉码编码时全覆盖的概率较低，会出现不能完全译出所有 源数据包的情况。
[0009] 2.鲁棒孤子度分布
[0010] 鲁棒孤子度分布（Robust Soliton Distribution, RSD)是对理想孤子度分布做出 的改进。鲁棒孤子度分布在度分布函数中引入了 2个参数C和δ，通过C和δ的选择来确 保译码过程中期望度为1的编码数据包个数S为：
[0011]
傑
[0012] 鲁棒孤子度分布设计了一个τ函数，目的是增加编码中取较大度值的概率，提高 覆盖性。τ函数为：
[0013]
[0014] 将τ函数与理想孤子度分布函数进行合并，并归一化就得到鲁棒孤子度分布函 数：
[0018] 式中，μ (d)表示采用鲁棒孤子度分布进行编码时，编码数据包度为d的概率；k为 信源数据包数量；δ为译码器未能全恢复源信息的概率；C为0和1之间的常数。采用鲁棒 孤子度分布进行编码时，产生的编码数据包多为度较大的编码数据包，具有较高的覆盖性， 但因此增加了兀余度，造成译码效率的降低，而且产生度1和其他小度编码数据包的数量 较少，当源数据包码长较短时，容易出现译码中断的情况。
[0019] 3.二进制指数度分布
[0020] 二进制指数度分布度inary Exponential Distribution,邸D):
[0021]
[0022] 式中，b(d)表示采用二进制指数度分布进行编码时，编码数据包度为d的概率；k 为信源数据包数量。采用二进制指数进行编码时，编码数据包度为1的概率很大，可W很好 地保证译码的持续性。但是随着d值的增加，取得d值的概率呈指数减少，所W产生度值较 大的编码数据包的概率很小，源数据包的充分覆盖得不到保证
[0023] 目前常用的度分布在源数据较长时具有较好的性能，但在数据较短时性能有明显 下降。送一特性让LT码在延时受限的系统中，W及信源具有突发性但数据较短的系统，女口 无线传感网中的应用受到限制。
【发明内容】
[0024] 本发明的目的在于给出一种喷泉码编码度分布设计方法，W得到一种当源数据为 短码长时也有较好性能的度分布。
[00巧]本发明的技术方案如下：
[0026] 一种LT喷泉码编码度分布的构造方法，其构造过程是；先对二进制度分布进行调 整，然后将其与不同特性的鲁棒孤子度分布进行有机结合。结合时，首先通过理论分析给出 了两种度分布组成比例系数α和目的取值范围，并在该范围内通过计算机搜索的方式得 到最佳值。然后通过优化可译集值来进一步优化度分布，并用序列二次规划法（Sequential 如a化atic Programming, SQP，即是一种常见的求解约束优化问题最优值的数学方法）求出 调整量Δ Ρι、Δ Ρ2、Δ Pm。、得到更适合于短码长源数据的度分布。采用该度分布构造方案得 到的度分布对源数据进行LT编码，相比较现有度分布，其译码性能得到了明显提高，并且 码长越短，性能提高越明显。
[0027] 基于W上内容，本发明具体包括W下步骤：
[002引步骤1，将邸D度分布中度1、2的概率值交换；即改为Pbed,i = 0. 25, Pbed,2 = 0. 5， 通过送种互换使得改变后的邸D满足度2概率值应是整个度分布函数的最大值的要求；
[0029] 步骤2,将调整后的邸D与RSD按照一定组成比例进行归一化合并，确定比例系数 α和目的取值；
[0030] 步骤3,通过优化可译集合值得到Pi、Ρ2、Pm。、的调整量Δ Ρι、Λ Ρ2、Δ Pm。、；
[003。 步骤4,将进行步骤2后得到的度分布函数中的Pl、P2、Pm。x更新为Δpl+Pl、Δ化+P2、 Δ Pmex+Pm。、，得到最终优化后的度分布函数。
[0032] 本方法先对二进制度分布进行调整，然后将其与鲁棒孤子度分布进行有机结合， 再通过优化可译集合值来进一步优化度分布函数，得到一种当源数据为短码长时也有较好 性能的度分布，即修正二进制-鲁棒孤子度分布。运用修正二进制-鲁棒孤子度分布对源 数据进行LT喷泉编码，可W减少译码开销，提高译码效率。本发明译码开销较采用现有度 分布时低，特别当是源数据长度较短时，性能提高更明显，使喷泉码能够更好地应用在各个 通信领域。
【附图说明】
[0033] 图1 (a)、图1化）和图1 (C)为修正二进制-鲁棒孤子度分布；译码成功时所需要 的编码数据包数随比例系数α和目的变化情况；
[0034] 图2 (a)、图2化）和图2 (C)为可译集合值随译码成功比率Ρ A的变化情况；
[003引图3 (a)、图3 (b)为k = 500、k = 1000,采用立种不同度分布进行编码，译码成功 比率与接收到的编码数据包的关系。
【具体实施方式】
[0036] 为了使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进 一步的详细描述：
[0037] -个好的编码度分布会有一些特点，根据送些特点来设计的喷泉码编码度分布会 得到较好的性能。研究表明度为2的概率值P2应为整个度分布函数中的最大值，且应尽量 接近0. 5 ;度为1的概率值Pi要适当大，W保障译码过程的开始及持续进行；还要保证一定 的最大度的概率值Pm。、，W确保编码过程能覆盖全部源数据包。因此，送3个度的概率值对 度分布函数的性能有着重大的影响。在设计度分布时，除了要考虑W上几个概率值的要求 夕F，还需要考虑可译集合的值。可译集合是进行每一步译码时产生的度为1的编码数据包 的集合。当源数据包码长很长时，可译集合的值一般都趋于一个恒值；在源数据包码长较短 时，可译集合的值会出现一定的波动。当可译集合的值较小时，即度1编码数据包的个数较 少，有可能导致译码中断，需要得到更多的编码数据包才能进行译码，送样译码开销必然增 加。可译集合值跟度分布函数有密切联系，通过优化可译集合值可进一步调整度分布函。 [003引1.两种度分布的合并
[0039] 通过对理想孤子度分布、鲁棒孤子度分布和二进制指数度分布的分析，我们可W 得出送Η种度分布的特点；RSD产生度较大的编码数据包的概率较大，但是产生度1的编码 数据包的概率很小，译码中断的可能性较高；Β邸能够产生足够多的度1编码数据包，能保 证译码开始并持续的进行，然而过多地产生度1编码数据包，会降低全部信源数据包都参 与编码的概率；同时，按照Β邸产生的编码数据包之间的关联性较小，度为2的编码数据包 在译码中度值降为1的概率相应也较小，因而译码的迭代效率较低。另外，Β邸中度1的概 率PwD, 1 = 0. 5远远大于度2的概率PwD, 2 = 0. 25,并不符合一个好的度分布的特点。因此， 我们在设计度分布时，首先对邸D做出调整，将度1的概率值与度2的概率值互换，即改为 PwD,i = 0. 25，PeeD,2 = 0. 5。通过送种互换使得改变后的B邸满足度2概率值应是整个度分 布函数的最大值的要求。调整后的B邸的度1概率值仍然过大，而取较大度的概率过小。而 RSD则取较大度的概率较大，产生度1编码数据包的概率较小。将调整后的B邸与RSD进 行合并并归一化，可结合送两种度分 布的优点，形成一种新的度分布，即修正二进制-鲁棒 孤子度分布（Modified Binary Robust Dishibution, MB畑）。并在进行合并时通过调整的 B邸与RSD的比例系数α和目来形成最佳的度分布函数。其概率分布函数如下：
[004引式中，m(d)表示采用MBRD进行编码时，编码数据包度为d的概率，μ (d)为鲁棒孤 子度分布，b(d)为二进制指数度分布。
[0043] 要从理论上的推到得到最佳的比例系数α和目的取值较为困难，但可W先根据 要求推导出它们的取值范围，然后再利用Monte-Carlo方法确定其最佳值。合并后的度分 布中度1的概率值主要是由调整后的邸D的度1概率值决定，而其最大度概率值主要是由 RSD的最大度概率值决定。根据概率值的特性，W及要获得好的度分布的要求，α和目的 取值范围应满足W下约束条件：
[0051] PmBRD, 1, PmBRD, 2, PMBRD,nmx分力iJ表不修正一进制-鲁棒孤子度分布度1、度2和巧大度的 概率值，PeeD,2分别表示鲁棒孤子度分布度1、度2, W及二进制指数度分布度2 的概率值。
[0052] 2、度分布的进一步优化
[0053] 为了使度分布在源数据包较短时有更好的编码译码性能，我们还需要考虑译码过 程中可译集合值的波动。当可译集合的值较小时，即度1编码数据包的个数较少，送样译码 中断的可能性较高，译码开销增大。因此，需要足够大的可译集合值W保证译码过程的持续 进行。可译集合值的表达式为：
[0058] 式中，P表示成功译码的源数据包个数，k表示源数据包个数，N为译码成功时所 需要的编码数据包个数，表示度为d的概率值，ε为译码开销。0(1)为1的高阶无穷 小量。由此可见，可译集合值与度分布有关，可W通过调整度分布来改善可译集合值。度分 布函数中Pi、P2、Pm。、的取值对编译码性能的影响最大，因此我们根据可译集合值的要求进一 步调整Pi、化、Pmax的值，而其他度的概率值保持不变。令Pi、化、Pmax的调整量分别为Δ Pi、 Δ化、Δ Pmax，根据概率之和固定为一的特点，有
[005引 Δ Pi+ Δ P2+ Δ Pmax = 0 (17)
[0060] 由于送Η个调整量间存在送样的约束关系，实际上优化的调整量只有两个，我们 选择Δρι、Δ化。度分布调整后的可译集合值为：
[0061]
[0062] 在整个译码过程中，可译集合值的平均值为：
[0066] 改善可译集合值也就是使可译集合值的平均值最大，方差最小，即找到使下式取 得最小值的Δρι、Δ化值：
[0067] η = λ XV-M (21)
[0068] 由式（17) W及度分布函数中每个概率值都大于0可W得出Δ Ρι、Δ P2的约束条 件为：
[0069]
(22)
[0070] 可译集值的优化涉及到求解最优值的数学方法，序列二次规划法是一种求解约束 优化问题的有效算法，本发明运用序列二次规划法来求解Δ Ρι、Δ化、Δ Pm。、的值。
[007。 表1为Δ Ρι、Λ Ρ2、Δ Pm。、在不同源数据包个数下的取值：
[0072]
[007引表2为采用Η种不同度分布进行编码时的译码开销：
[0074]
[00 巧]
[0076] 本发明的喷泉码的编译码方案可W应用在许多方面，包括数据的存储、发送、广播 等等。
[0077] 在为文件作备份时，由于磁带或硬盘的突发性故障，数据可能会产生丢失。在存储 一个大型的文件时，如果其中部分数据出现无法纠正的错误就有可能导致全部数据无法恢 复。如果将文件分为k个源数据包并进行喷泉编码，将生成的η (n〉k)个编码数据包存储在 多个服务器上，读取时只需获得其中任意k'（稍大于k)个编码数据包就可W恢复原始数 据，实现了数据存储的高效和可靠
[0078] 假如一个地区内的10万个用户同时通过广播的方式接收一部数字电影。它通过 广播网络将电影分成数据包通过宽带的电话线或者是卫星发送。假设每个接受者都丢失了 其中0. 1 %数据包。在标准模式下，数据包是按照顺序发送的，并且没有编码，郝么每个接 受者就必须向发送端通报他们丢失了的数据包，并要求重发。当10万个用户都提出送样的 重发要求时，郝就几乎相当于要把所有的数据包都进行重发。送样一来，发送端需要把整个 广播多次地重复发送才能确保每个用户都能完整接收到电影，每个用户也都同样需要等待 几倍长的时间直到完全接收。然而，如果广播端使用喷泉码对电影进行编码的话，每个用户 只要接收到k'（稍大于k)个数据包就可W覆盖送部电影，送样广播端（可能）只需要发送 1.化的数据包就可W确保每个用户都完整接收整部电影。
[0079] 另外的一种喷泉码在广播中的应用是为汽车提供数据。假如我们想通过卫星为车 载导航数据库提供更新服务时应该怎么办呢？地球上有成千上万的机动车，它们只有在开 阔的路上行驶的时候才能接收到数据，并且它们还不存在反馈信道。通常人们把数据放在 关键路段的广播设备中，如果采用常规方式，一旦用户没有接收到全部的更新信息就断线 了，郝么他就需要在下个路段重新接收；而采用喷泉码，每辆车只需要接收到1.05%的原 始数据包就可W获得完整的更新信息，对于是否断线不太关必。
[0080] 既然喷泉码可W简化一到多的广播方式，郝么它也可W用于多到一的并行下载。 虽然没有喷泉码也可W实现多点的并行下载，但是如果使用的话可W大大简化送个下载过 程。因为使用数字喷泉，每个资源点可W独立的产生无穷无尽的编码数据包，由于可W提供 无数的可靠的数据包，并且从多个资源点收到的编码包不会冲突。当接收端收到了足够数 量的数据包后就断开连接，并不需要考虑送些数据包的来源或者发送速率及误码率。
[0081] 视频点播系统可W使用码长较短的喷泉码对数据进行编码来得到更好的性能。假 设想用数字喷泉方案来对一部平均码率为384k bit/s的电影提供视频点播服务，信道传输 速率也是384k bit/s，网络包的大小为128字节（在无线局域网中的典型值）。若采用码 长为104的LT码，郝么在接收端至少要缓冲1.28M字节的内容（如果考虑到网络的丢包和 喷泉码的译码开销，缓冲长度还会更长），从客户开始点播到能把数据译出来播放，至少要 等1. 28MX8/384化PS = 26. 7砂，送通常是难W忍受的。然而，若将码长降到103的量级， 郝么相应的延迟就属于可接受的范围了，因此码长喷泉码可W视频点播系统提供更好的服 务。
[0082] 无线传感器网络的节点通常被部署在环境相对恶劣、条件受限制的环境中，同时， 传感器节点本身具有能量有限的特点，由于环境条件受限，能量一般无法进行补充。当节 点由于能量耗尽而失效时，也会使数据的可用性严重下降。在无线传感器网络中引入喷泉 码的编码技术能够提高网络数据的持久性，它推翻了传统的通信网络中使用的信息只能存 储和转发而不能叠加的路由机制，允许网络节点对传输的数据包W合适的方式进行编码处 理。利用网络编码技术，提高了数据在网络中的持久性和可靠性。在无线传感网中，传感器 传输的往往是长度很短的数据，如：温度、重量、光亮程度等物理量。因此，运用在码长较短 时也有很好性能的喷泉码进行编码，可W减少译码开销，从而减少传感器能量的消耗，保证 数据的正确性。
【主权项】
1. 一种LT喷泉码编码度分布的构造方法，包括以下步骤： 步骤1，将BED度分布中度1、2的概率值交换；即改为pBEDil = 0. 25, pBEDi2 = 0. 5,通过 这种互换使得改变后的BED满足度2概率值应是整个度分布函数的最大值的要求； 步骤2,将调整后的BED与RSD按照一定组成比例进行归一化合并，确定比例系数α和 β的取值； 步骤3,通过优化可译集合值得到P^PpPmax的调整量Λ ρ^Λ ρ2、Λ pmax ; 步骤4,将得到的度分布函数中的p2、pmax更新为Λ Pi+ρ^Λ ρ2+ρ2、Λ pmax+pmax,得到 最终优化后的度分布函数。2. 根据权利要求1所述的LT喷泉码编码度分布的构造方法，其特征在于：所述步骤2 的方法是：在进行合并时通过调整的BED与RSD的比例系数（！和β来形成最佳的度分布 函数，其概率分布函数如下：式中，m(d)表示采用MBRD进行编码时，编码数据包度为d的概率，μ (d)为鲁棒孤子度 分布，b(d)为二进制指数度分布； α和β的取值范围满足以下约束条件：P_：u，Ρ_，2, Ρ_，咖分别表示修正二进制-鲁棒孤子度分布度1、度2和最大度的概率 值，PRS：u、PRSDl2、P_l2分别表示鲁棒孤子度分布度1、度2,以及二进制指数度分布度2的概 率值。3. 根据权利要求2所述的LT喷泉码编码度分布的构造方法，所述步骤3的方法为： 可译集合值的表达式为：式中，P表示成功译码的源数据包个数，k表示源数据包个数，N为译码成功时所需要 的编码数据包个数，〇,表示度为d的概率值，ε为译码开销，0(1)为1的高阶无穷小量； 根据可译集合值的要求进一步调整P 1即式（7)中的m(l)、ρ2即式（7)中的m(2)、ρ_ 即式（7)中的m(max)的值，其他度的概率值保持不变，令 Pl、p2、p_的调整量分别为ΛΡι、 Λ ρ2、Λ ρ_，根据概率之和固定为一的特点，有 Δ P1+ Δ ρ2+ Δ pnax = 0 (11) 选择Λ Ρι、Λ P2两个调整量，度分布调整后的可译集合值为：在整个译码过程中，可译集合值的平均值为：方差为：改善可译集合值也就是使可译集合值的平均值最大，方差最小，即找到使下式取得最 小值的Ap1、Ap2值： η = λ XV-M (15) 由式（17)以及度分布函数中每个概率值都大于0可以得出Λ Ρι、Λ ρ2的约束条件为：4.根据权利要求2所述的LT喷泉码编码度分布的构造方法，其特征在于：所述步骤4 的具体实现过程为： 对步骤2得到的度分布中的Pl、p2、p_按照步骤3得到的调整量Λ Ρι、Λ ρ2、Λ p_进 行调整，得到度分布中的其他值不变。
【专利摘要】本发明提出一种LT码度分布的构造方法。该方法先对二进制度分布进行调整，然后将其与鲁棒孤子度分布进行有机结合，再通过优化可译集合值来进一步优化度分布函数，得到一种当源数据为短码长时也有较好性能的度分布，即修正二进制-鲁棒孤子度分布。运用修正二进制-鲁棒孤子度分布对源数据进行LT喷泉编码，可以减少译码开销，提高译码效率，使喷泉码能够更好地应用在各个通信领域。
【IPC分类】H04L1/00
【公开号】CN105490771
【申请号】CN201410474394
【发明人】雷维嘉, 张梦
【申请人】重庆邮电大学
【公开日】2016年4月13日
【申请日】2014年9月17日
【技术领域】
[0001] 本发明是关于信息通信领域中利用数字喷泉码一LT喷泉码对信号进行编码时， 所使用的编码度分布的构造方法。
【背景技术】
[0002] 化hn Byers及Michael Luby等人于1998年提出了数字喷泉码的概念，为如何在 有限的网络带宽下处理可靠数据广播等问题给出了理想的解决方法。相对于传统的自动重 传请求机制，当出现数据包丢失的情况时，数字喷泉码并不需要发送大量的反馈信息告知 源端重新发送数据包，接收端只要再多接收一定数量的编码数据包就能够恢复原始数据。 送样避免了传输反馈信号时产生的延时，解决了广播应用中的反馈风暴问题。并且当有多 个接收端时，不同接收端之间接收到的错误信息都是相互独立的，因此接收端的数量可W 任意地增加或者减少，但并不会对彼此的译码性能造成影响。与传统前向纠错码相比，数字 喷泉码更能灵活地适应信道状况的变化。在运用传统纠错码时，首先要对信道的状况进行 估计，并W此为依据选取码长、码率等编码参数之后，再确定其编译码方式。然而由于信道 状态的不稳定性，当实际信道条件好于预估情况时，由于前向纠错码增加了过多的校验元， 降低了数据传输的有效性；相反，当信息在比预估情况更坏的实际信道进行传输时，前向纠 错码因不能提供更多的校验元而无法保证数据传输的可靠性。数字喷泉码的提出解决了上 述问题。利用数字喷泉码传输数据，接收端不用关必具体接收到了哪些正确的数据包W及 丢弃了哪些错误的编码数据包，只要接收端正确收到的编码数据包数量略微大于源数据包 的个数，它就可W完全恢复源信息。接收端在接收到足够多的编码数据包完成译码后，只需 向源端发送一个反馈信息，源端便停止编码。
[0003] 2002年Luby提出了第一种现实可行的喷泉码--LT码。LT码具有编译码方法 简单、译码开销和编译码复杂程度低的特点。其编码过程为；发送端原始数据由k个数据包 组成，根据某一编码度分布随机产生每个编码数据包的度d，然后从k个原始数据包中任意 地选择d个数据包，再将送d个数据包进行异或运算，从而生成一个编码数据包。编码器重 复操作送个过程就可W产生无限长的编码数据包流。LT码的译码一般采用置信传播译码算 法，其过程为；将接收到的一定数量的编码数据包与源数据包建立对应的双向图，任意地选 取一个度为1的数据包开始进行译码。由于度为1数据包就是对源数据包的复制，所W通 过简单的复制运算，就能恢复源数据包。然后，对已经恢复的源数据包，将它与其有关联的 所有编码数据包进行异或运算，更新送些编码数据包的值，再将恢复的源数据包和与它有 关联的编码数据包在Tanner图中所对应的边删除，使送些编码数据包的度数减1。W此循 环下去直到恢复所有原始数据为止。
[0004] 常用的编码度分布：
[0005] 1.理想孤子度分布
[0006] 理想孤子度分布理论上使每一个编码数据包在每一次译码迭代中释放的概率相 同，保证在每次迭代过程中有且只有一个度为1的编码数据包出现，完成每一次迭代恢复 一个源数据包，同时又有一个度为1的编码数据包出现。其度分布函数为：
[0007]
烘
[0008] 式中，P (d)为采用理想孤子度分布进行编码时，编码数据包的度为d(d = l，2,3...，k)的概率；k为源数据包数量。由其函数表达式可W看出，理想孤子度分布产生 的编码数据包中多数的度较小，但产生度1数据包的概率很小，仅为1A。在实际中，由于度 分布映射的随机性，在译码过程中很容易出现度1编码数据包消失；另一方面，产生度值较 大编码数据包的概率也较小，喷泉码编码时全覆盖的概率较低，会出现不能完全译出所有 源数据包的情况。
[0009] 2.鲁棒孤子度分布
[0010] 鲁棒孤子度分布（Robust Soliton Distribution, RSD)是对理想孤子度分布做出 的改进。鲁棒孤子度分布在度分布函数中引入了 2个参数C和δ，通过C和δ的选择来确 保译码过程中期望度为1的编码数据包个数S为：
[0011]
傑
[0012] 鲁棒孤子度分布设计了一个τ函数，目的是增加编码中取较大度值的概率，提高 覆盖性。τ函数为：
[0013]
[0014] 将τ函数与理想孤子度分布函数进行合并，并归一化就得到鲁棒孤子度分布函 数：
[0018] 式中，μ (d)表示采用鲁棒孤子度分布进行编码时，编码数据包度为d的概率；k为 信源数据包数量；δ为译码器未能全恢复源信息的概率；C为0和1之间的常数。采用鲁棒 孤子度分布进行编码时，产生的编码数据包多为度较大的编码数据包，具有较高的覆盖性， 但因此增加了兀余度，造成译码效率的降低，而且产生度1和其他小度编码数据包的数量 较少，当源数据包码长较短时，容易出现译码中断的情况。
[0019] 3.二进制指数度分布
[0020] 二进制指数度分布度inary Exponential Distribution,邸D):
[0021]
[0022] 式中，b(d)表示采用二进制指数度分布进行编码时，编码数据包度为d的概率；k 为信源数据包数量。采用二进制指数进行编码时，编码数据包度为1的概率很大，可W很好 地保证译码的持续性。但是随着d值的增加，取得d值的概率呈指数减少，所W产生度值较 大的编码数据包的概率很小，源数据包的充分覆盖得不到保证
[0023] 目前常用的度分布在源数据较长时具有较好的性能，但在数据较短时性能有明显 下降。送一特性让LT码在延时受限的系统中，W及信源具有突发性但数据较短的系统，女口 无线传感网中的应用受到限制。
【发明内容】
[0024] 本发明的目的在于给出一种喷泉码编码度分布设计方法，W得到一种当源数据为 短码长时也有较好性能的度分布。
[00巧]本发明的技术方案如下：
[0026] 一种LT喷泉码编码度分布的构造方法，其构造过程是；先对二进制度分布进行调 整，然后将其与不同特性的鲁棒孤子度分布进行有机结合。结合时，首先通过理论分析给出 了两种度分布组成比例系数α和目的取值范围，并在该范围内通过计算机搜索的方式得 到最佳值。然后通过优化可译集值来进一步优化度分布，并用序列二次规划法（Sequential 如a化atic Programming, SQP，即是一种常见的求解约束优化问题最优值的数学方法）求出 调整量Δ Ρι、Δ Ρ2、Δ Pm。、得到更适合于短码长源数据的度分布。采用该度分布构造方案得 到的度分布对源数据进行LT编码，相比较现有度分布，其译码性能得到了明显提高，并且 码长越短，性能提高越明显。
[0027] 基于W上内容，本发明具体包括W下步骤：
[002引步骤1，将邸D度分布中度1、2的概率值交换；即改为Pbed,i = 0. 25, Pbed,2 = 0. 5， 通过送种互换使得改变后的邸D满足度2概率值应是整个度分布函数的最大值的要求；
[0029] 步骤2,将调整后的邸D与RSD按照一定组成比例进行归一化合并，确定比例系数 α和目的取值；
[0030] 步骤3,通过优化可译集合值得到Pi、Ρ2、Pm。、的调整量Δ Ρι、Λ Ρ2、Δ Pm。、；
[003。 步骤4,将进行步骤2后得到的度分布函数中的Pl、P2、Pm。x更新为Δpl+Pl、Δ化+P2、 Δ Pmex+Pm。、，得到最终优化后的度分布函数。
[0032] 本方法先对二进制度分布进行调整，然后将其与鲁棒孤子度分布进行有机结合， 再通过优化可译集合值来进一步优化度分布函数，得到一种当源数据为短码长时也有较好 性能的度分布，即修正二进制-鲁棒孤子度分布。运用修正二进制-鲁棒孤子度分布对源 数据进行LT喷泉编码，可W减少译码开销，提高译码效率。本发明译码开销较采用现有度 分布时低，特别当是源数据长度较短时，性能提高更明显，使喷泉码能够更好地应用在各个 通信领域。
【附图说明】
[0033] 图1 (a)、图1化）和图1 (C)为修正二进制-鲁棒孤子度分布；译码成功时所需要 的编码数据包数随比例系数α和目的变化情况；
[0034] 图2 (a)、图2化）和图2 (C)为可译集合值随译码成功比率Ρ A的变化情况；
[003引图3 (a)、图3 (b)为k = 500、k = 1000,采用立种不同度分布进行编码，译码成功 比率与接收到的编码数据包的关系。
【具体实施方式】
[0036] 为了使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进 一步的详细描述：
[0037] -个好的编码度分布会有一些特点，根据送些特点来设计的喷泉码编码度分布会 得到较好的性能。研究表明度为2的概率值P2应为整个度分布函数中的最大值，且应尽量 接近0. 5 ;度为1的概率值Pi要适当大，W保障译码过程的开始及持续进行；还要保证一定 的最大度的概率值Pm。、，W确保编码过程能覆盖全部源数据包。因此，送3个度的概率值对 度分布函数的性能有着重大的影响。在设计度分布时，除了要考虑W上几个概率值的要求 夕F，还需要考虑可译集合的值。可译集合是进行每一步译码时产生的度为1的编码数据包 的集合。当源数据包码长很长时，可译集合的值一般都趋于一个恒值；在源数据包码长较短 时，可译集合的值会出现一定的波动。当可译集合的值较小时，即度1编码数据包的个数较 少，有可能导致译码中断，需要得到更多的编码数据包才能进行译码，送样译码开销必然增 加。可译集合值跟度分布函数有密切联系，通过优化可译集合值可进一步调整度分布函。 [003引1.两种度分布的合并
[0039] 通过对理想孤子度分布、鲁棒孤子度分布和二进制指数度分布的分析，我们可W 得出送Η种度分布的特点；RSD产生度较大的编码数据包的概率较大，但是产生度1的编码 数据包的概率很小，译码中断的可能性较高；Β邸能够产生足够多的度1编码数据包，能保 证译码开始并持续的进行，然而过多地产生度1编码数据包，会降低全部信源数据包都参 与编码的概率；同时，按照Β邸产生的编码数据包之间的关联性较小，度为2的编码数据包 在译码中度值降为1的概率相应也较小，因而译码的迭代效率较低。另外，Β邸中度1的概 率PwD, 1 = 0. 5远远大于度2的概率PwD, 2 = 0. 25,并不符合一个好的度分布的特点。因此， 我们在设计度分布时，首先对邸D做出调整，将度1的概率值与度2的概率值互换，即改为 PwD,i = 0. 25，PeeD,2 = 0. 5。通过送种互换使得改变后的B邸满足度2概率值应是整个度分 布函数的最大值的要求。调整后的B邸的度1概率值仍然过大，而取较大度的概率过小。而 RSD则取较大度的概率较大，产生度1编码数据包的概率较小。将调整后的B邸与RSD进 行合并并归一化，可结合送两种度分 布的优点，形成一种新的度分布，即修正二进制-鲁棒 孤子度分布（Modified Binary Robust Dishibution, MB畑）。并在进行合并时通过调整的 B邸与RSD的比例系数α和目来形成最佳的度分布函数。其概率分布函数如下：
[004引式中，m(d)表示采用MBRD进行编码时，编码数据包度为d的概率，μ (d)为鲁棒孤 子度分布，b(d)为二进制指数度分布。
[0043] 要从理论上的推到得到最佳的比例系数α和目的取值较为困难，但可W先根据 要求推导出它们的取值范围，然后再利用Monte-Carlo方法确定其最佳值。合并后的度分 布中度1的概率值主要是由调整后的邸D的度1概率值决定，而其最大度概率值主要是由 RSD的最大度概率值决定。根据概率值的特性，W及要获得好的度分布的要求，α和目的 取值范围应满足W下约束条件：
[0051] PmBRD, 1, PmBRD, 2, PMBRD,nmx分力iJ表不修正一进制-鲁棒孤子度分布度1、度2和巧大度的 概率值，PeeD,2分别表示鲁棒孤子度分布度1、度2, W及二进制指数度分布度2 的概率值。
[0052] 2、度分布的进一步优化
[0053] 为了使度分布在源数据包较短时有更好的编码译码性能，我们还需要考虑译码过 程中可译集合值的波动。当可译集合的值较小时，即度1编码数据包的个数较少，送样译码 中断的可能性较高，译码开销增大。因此，需要足够大的可译集合值W保证译码过程的持续 进行。可译集合值的表达式为：
[0058] 式中，P表示成功译码的源数据包个数，k表示源数据包个数，N为译码成功时所 需要的编码数据包个数，表示度为d的概率值，ε为译码开销。0(1)为1的高阶无穷 小量。由此可见，可译集合值与度分布有关，可W通过调整度分布来改善可译集合值。度分 布函数中Pi、P2、Pm。、的取值对编译码性能的影响最大，因此我们根据可译集合值的要求进一 步调整Pi、化、Pmax的值，而其他度的概率值保持不变。令Pi、化、Pmax的调整量分别为Δ Pi、 Δ化、Δ Pmax，根据概率之和固定为一的特点，有
[005引 Δ Pi+ Δ P2+ Δ Pmax = 0 (17)
[0060] 由于送Η个调整量间存在送样的约束关系，实际上优化的调整量只有两个，我们 选择Δρι、Δ化。度分布调整后的可译集合值为：
[0061]
[0062] 在整个译码过程中，可译集合值的平均值为：
[0066] 改善可译集合值也就是使可译集合值的平均值最大，方差最小，即找到使下式取 得最小值的Δρι、Δ化值：
[0067] η = λ XV-M (21)
[0068] 由式（17) W及度分布函数中每个概率值都大于0可W得出Δ Ρι、Δ P2的约束条 件为：
[0069]
(22)
[0070] 可译集值的优化涉及到求解最优值的数学方法，序列二次规划法是一种求解约束 优化问题的有效算法，本发明运用序列二次规划法来求解Δ Ρι、Δ化、Δ Pm。、的值。
[007。 表1为Δ Ρι、Λ Ρ2、Δ Pm。、在不同源数据包个数下的取值：
[0072]
[007引表2为采用Η种不同度分布进行编码时的译码开销：
[0074]
[00 巧]
[0076] 本发明的喷泉码的编译码方案可W应用在许多方面，包括数据的存储、发送、广播 等等。
[0077] 在为文件作备份时，由于磁带或硬盘的突发性故障，数据可能会产生丢失。在存储 一个大型的文件时，如果其中部分数据出现无法纠正的错误就有可能导致全部数据无法恢 复。如果将文件分为k个源数据包并进行喷泉编码，将生成的η (n〉k)个编码数据包存储在 多个服务器上，读取时只需获得其中任意k'（稍大于k)个编码数据包就可W恢复原始数 据，实现了数据存储的高效和可靠
[0078] 假如一个地区内的10万个用户同时通过广播的方式接收一部数字电影。它通过 广播网络将电影分成数据包通过宽带的电话线或者是卫星发送。假设每个接受者都丢失了 其中0. 1 %数据包。在标准模式下，数据包是按照顺序发送的，并且没有编码，郝么每个接 受者就必须向发送端通报他们丢失了的数据包，并要求重发。当10万个用户都提出送样的 重发要求时，郝就几乎相当于要把所有的数据包都进行重发。送样一来，发送端需要把整个 广播多次地重复发送才能确保每个用户都能完整接收到电影，每个用户也都同样需要等待 几倍长的时间直到完全接收。然而，如果广播端使用喷泉码对电影进行编码的话，每个用户 只要接收到k'（稍大于k)个数据包就可W覆盖送部电影，送样广播端（可能）只需要发送 1.化的数据包就可W确保每个用户都完整接收整部电影。
[0079] 另外的一种喷泉码在广播中的应用是为汽车提供数据。假如我们想通过卫星为车 载导航数据库提供更新服务时应该怎么办呢？地球上有成千上万的机动车，它们只有在开 阔的路上行驶的时候才能接收到数据，并且它们还不存在反馈信道。通常人们把数据放在 关键路段的广播设备中，如果采用常规方式，一旦用户没有接收到全部的更新信息就断线 了，郝么他就需要在下个路段重新接收；而采用喷泉码，每辆车只需要接收到1.05%的原 始数据包就可W获得完整的更新信息，对于是否断线不太关必。
[0080] 既然喷泉码可W简化一到多的广播方式，郝么它也可W用于多到一的并行下载。 虽然没有喷泉码也可W实现多点的并行下载，但是如果使用的话可W大大简化送个下载过 程。因为使用数字喷泉，每个资源点可W独立的产生无穷无尽的编码数据包，由于可W提供 无数的可靠的数据包，并且从多个资源点收到的编码包不会冲突。当接收端收到了足够数 量的数据包后就断开连接，并不需要考虑送些数据包的来源或者发送速率及误码率。
[0081] 视频点播系统可W使用码长较短的喷泉码对数据进行编码来得到更好的性能。假 设想用数字喷泉方案来对一部平均码率为384k bit/s的电影提供视频点播服务，信道传输 速率也是384k bit/s，网络包的大小为128字节（在无线局域网中的典型值）。若采用码 长为104的LT码，郝么在接收端至少要缓冲1.28M字节的内容（如果考虑到网络的丢包和 喷泉码的译码开销，缓冲长度还会更长），从客户开始点播到能把数据译出来播放，至少要 等1. 28MX8/384化PS = 26. 7砂，送通常是难W忍受的。然而，若将码长降到103的量级， 郝么相应的延迟就属于可接受的范围了，因此码长喷泉码可W视频点播系统提供更好的服 务。
[0082] 无线传感器网络的节点通常被部署在环境相对恶劣、条件受限制的环境中，同时， 传感器节点本身具有能量有限的特点，由于环境条件受限，能量一般无法进行补充。当节 点由于能量耗尽而失效时，也会使数据的可用性严重下降。在无线传感器网络中引入喷泉 码的编码技术能够提高网络数据的持久性，它推翻了传统的通信网络中使用的信息只能存 储和转发而不能叠加的路由机制，允许网络节点对传输的数据包W合适的方式进行编码处 理。利用网络编码技术，提高了数据在网络中的持久性和可靠性。在无线传感网中，传感器 传输的往往是长度很短的数据，如：温度、重量、光亮程度等物理量。因此，运用在码长较短 时也有很好性能的喷泉码进行编码，可W减少译码开销，从而减少传感器能量的消耗，保证 数据的正确性。
【主权项】
1. 一种LT喷泉码编码度分布的构造方法，包括以下步骤： 步骤1，将BED度分布中度1、2的概率值交换；即改为pBEDil = 0. 25, pBEDi2 = 0. 5,通过 这种互换使得改变后的BED满足度2概率值应是整个度分布函数的最大值的要求； 步骤2,将调整后的BED与RSD按照一定组成比例进行归一化合并，确定比例系数α和 β的取值； 步骤3,通过优化可译集合值得到P^PpPmax的调整量Λ ρ^Λ ρ2、Λ pmax ; 步骤4,将得到的度分布函数中的p2、pmax更新为Λ Pi+ρ^Λ ρ2+ρ2、Λ pmax+pmax,得到 最终优化后的度分布函数。2. 根据权利要求1所述的LT喷泉码编码度分布的构造方法，其特征在于：所述步骤2 的方法是：在进行合并时通过调整的BED与RSD的比例系数（！和β来形成最佳的度分布 函数，其概率分布函数如下：式中，m(d)表示采用MBRD进行编码时，编码数据包度为d的概率，μ (d)为鲁棒孤子度 分布，b(d)为二进制指数度分布； α和β的取值范围满足以下约束条件：P_：u，Ρ_，2, Ρ_，咖分别表示修正二进制-鲁棒孤子度分布度1、度2和最大度的概率 值，PRS：u、PRSDl2、P_l2分别表示鲁棒孤子度分布度1、度2,以及二进制指数度分布度2的概 率值。3. 根据权利要求2所述的LT喷泉码编码度分布的构造方法，所述步骤3的方法为： 可译集合值的表达式为：式中，P表示成功译码的源数据包个数，k表示源数据包个数，N为译码成功时所需要 的编码数据包个数，〇,表示度为d的概率值，ε为译码开销，0(1)为1的高阶无穷小量； 根据可译集合值的要求进一步调整P 1即式（7)中的m(l)、ρ2即式（7)中的m(2)、ρ_ 即式（7)中的m(max)的值，其他度的概率值保持不变，令 Pl、p2、p_的调整量分别为ΛΡι、 Λ ρ2、Λ ρ_，根据概率之和固定为一的特点，有 Δ P1+ Δ ρ2+ Δ pnax = 0 (11) 选择Λ Ρι、Λ P2两个调整量，度分布调整后的可译集合值为：在整个译码过程中，可译集合值的平均值为：方差为：改善可译集合值也就是使可译集合值的平均值最大，方差最小，即找到使下式取得最 小值的Ap1、Ap2值： η = λ XV-M (15) 由式（17)以及度分布函数中每个概率值都大于0可以得出Λ Ρι、Λ ρ2的约束条件为：4.根据权利要求2所述的LT喷泉码编码度分布的构造方法，其特征在于：所述步骤4 的具体实现过程为： 对步骤2得到的度分布中的Pl、p2、p_按照步骤3得到的调整量Λ Ρι、Λ ρ2、Λ p_进 行调整，得到度分布中的其他值不变。
【专利摘要】本发明提出一种LT码度分布的构造方法。该方法先对二进制度分布进行调整，然后将其与鲁棒孤子度分布进行有机结合，再通过优化可译集合值来进一步优化度分布函数，得到一种当源数据为短码长时也有较好性能的度分布，即修正二进制-鲁棒孤子度分布。运用修正二进制-鲁棒孤子度分布对源数据进行LT喷泉编码，可以减少译码开销，提高译码效率，使喷泉码能够更好地应用在各个通信领域。
【IPC分类】H04L1/00
【公开号】CN105490771
【申请号】CN201410474394
【发明人】雷维嘉, 张梦
【申请人】重庆邮电大学
【公开日】2016年4月13日
【申请日】2014年9月17日
最新回复(0)