LT编译码算法的DSP实现

师 歌，高宏峰

(河南科技大学电子信息工程学院，河南 洛阳 471000)

LT(Lucy Transform)码是第一类基于纠删码技术的高效率无码率码[1]，同时也是第一类Fountain码。Fountain码的设计思想来源于水喷泉:服务器可以随机生成编码信息包，一个客户端从一个或者多个服务器接收编码包，一旦接收到足够的编码包N就可以重构出源信号，N的数量与信道特性无关。Fountain码的特性决定其十分适合用于计算机网络、广播信道、无线传感器网络等信道的信息传输。2003年Lucy提出LT码[2]，LT码对于具有不同删除概率的各种删除信道均是逼近最优的。

鉴于DSP技术精度高、速度快、成本低、灵活性强、可靠性好的特点，DSP技术被越来越多地运用于信道编码领域。通过研究，Turbo 码[3]、卷积码[4]、LDPC 码[5]等大部分早期码的编译码器都通过DSP等技术得以实现。但由于LT编译码器的数据运算量和内存使用量随编码长度的增加而快速增大[6]，使用DSP技术实现LT码编译码器必须要解决两个难题:1)如何设计编译码算法，简化程序，减少CPU负担;2)如何建立信息储存机制，存储度邻接信号表，合理利用DSP芯片片上内存资源。

本文使用反馈控制信号，控制编码信号的码长，降低编码器功耗;引入冗余信息处理程序，剔除编码信号中的冗余，提高LT译码效率;建立度邻接信号表的位置系数储存机制，合理存储度邻接信号信息，减少DSP芯片片上内存使用量。最终采用TI公司的TMS320VC5416芯片，在CCS(Code Composer Studio)集成开发环境下使用C语言编程[7]，设计和实现了LT编译码器。

1 LT编译码算法的DSP硬件实现

本文采用TI公司的TMS320VC5416芯片，整个系统的硬件结构如图1所示。

图1 系统的硬件结构框图

在编码器中，源信号通过串口(RS－232接口)传入芯片。由于数据采用异步传输，可以采用DSP的McBSP结合DMA，在不扩展硬件的情况下，用软件实现异步数据传输。但该方法软件设计复杂，加大了CPU的负担，因此添加TI公司的TL16C550异步串行通信收发器来实现异步数据传输。此外，使用TI公司的双路低压差电源调节器芯片TPS767D301给TMS320VC5416芯片供电，使用TI公司的Flash芯片AM29LV800保存编译码程序段，以便在系统启动时将编(译)码程序装载进DSP内部DARAM运行。

译码器从通信信道异步接收到编码信号后进行译码。译码过程中译码器通过通信信道发送反馈信息给编码器，控制编码器的工作。

2 LT编译码法的DSP软件实现

2.1 LT编码算法的DSP软件实现

图2为LT编码算法的软件流程图。编码器接收到k个信源信号后，根据信道删除率设定编码信号的数量N=B×k，1.0＜B＜2.0。根据稳健弧波分布确定N个编码信号的度值，随机均匀选择每个编码信号的度邻接信号，异或运算得到N个编码信号，通过通信信道发送。

图2 LT编码算法的软件流程图

2.1.1 反馈控制信号ACK

使用反馈控制信号ACK，控制编码器工作。ACK由译码器判定生成，初值设定为ACK=0。

当译码器未成功译码时，译码器生成ACK=1，反馈到编码器。编码器在接收到ACK=1信号后，根据信源信号码长k确定添加N=b ×k，0.01≤b≤0.10 个编码信号。

当译码算法结束，ACK=0，编码器停止工作，LT编译码算法结束。

2.1.2 编码信号度值的确定

稳健弧波分布(Robust Soliton distribution)μ(k)是LT编译码算法中普遍使用的度分布函数。其将理想弧波分布ρ(i)和补充分布τ(i)相结合，并且通过统一化处理得到。如式(1)～(4)所示

根据稳健弧波分布确定编码信号的度分布率函数μ(k)。根据μ(k)将时隔[0，1]划分成非重复且不等的k个子时隔，每个子时隔与每个度值一一对应[8]。例如:0.0 ～μ(1)对应度值1，μ(i)～μ(i+1)对应度值 i+1。

本文使用srand函数设置随机数发生器的初始化种子seed=s1。当第一次生成编码信号时，使用rand函数生成[0，1]区间长度为N的随机数列。确定随机数列中第i项值所处的子时隔，根据对应关系确定第i个编码信号的度值di。记M为添加编码信号的次数，T为已生成的编码信号的数量，T=B×k+(M－1)×b×k。当添加编码信号时生成[0，1]区间长度为T+N的随机数列，确定随机数列中第T+i项值所处的子时隔，根据对应关系确定新加的第i个编码信号的度值di。

2.1.3 编码信号度邻接信号的确定

编码信号的度邻接信号从k个信源信号中随机均匀选择，所以随机均匀选择的效果将直接影响到LT编译码算法的效率。

设置随机数发生器的初始化种子seed=s2(s1≠s2)，当第一次生成编码信号时，生成[0，k]区间长度为di的不重复随机数列{adi}。取出{adi}中第ai(i=1，2，…，di)个信源信号做为该编码信号的度邻接信号。当添加编码信号时，记前T个编码信号的度值总和为n，先生成[0，k]区间长度为n的不重复随机数列，再生成[0，k]区间长度为di的不重复随机数列{bdi}。取出{bdi}中第bi(i=1，2，…，di)个信源信号做为该编码信号的度邻接信号。

2.2 LT译码算法的DSP软件实现

在发送端和接收端建立seed表，接收端在接收编码分组后根据seed表序列号确定seed值，进而得到编码信号的度和度邻接信号表，进行译码。图3为LT译码算法的软件流程图。

将编码信号及其度邻接信号表存储后，根据反馈控制信号ACK，对新添加的编码信号及其度邻接信号表进行冗余信号处理。寻找度为1的编码信号开始进行译码。当编码信号被释放后，删除该编码信号及其度邻接信号表。重复以上步骤，至度为1的编码信号耗尽。如信源信号未被完全恢复，则生成反馈控制信号ACK=1，编码器添加编码信号。

图3 LT译码算法的软件流程图

2.2.1 度邻接信号表的位置系数存储机制

在LT译码算法中，存储编码信号的度邻接信号表占用了大量的DSP芯片片上内存空间，所以采用合理的度邻接信号表存储机制，可以减少DSP芯片片上内存使用量。

若不经处理直接对度邻接信号表进行存储，1个16 bit的整形数据中仅能存储1位度邻接信号表信息，对DSP片上内存空间造成了极大浪费，极大地限制了信源信号数量k的选择范围。

为了克服原始存储机制的缺点，可使用二进制位存储机制。通过位操作在16 bit的整型数据中存储16位的度邻接信号表信息。这样能够将存储度邻接信号表所需的内存缩小为原先的1/16左右。但当k值较大时，使用该存储机制存储仍需占用很大的存储空间。例如，当k=1024时，每一个编码信号的度邻接信号表都需要占用约64×16 bit的内存空间。

根据文献[2]所述，编码信号的平均度为

式中:当k值较大时，编码信号的度小于k/16，所以通过存储度邻接信号的位置系数可以减小度邻接信号表的存储空间。本文使用位置系数存储机制将将每个编码信号的度邻接信号位置系数按顺序存储。

通过使用位置系数存储机制，减小了用于储存编码信号度邻接信号表的内存，提高了可选信源信号数量k的上限值。表1为3种度邻接信号表存储机制的性能参数。采用二进制存储机制可以在原始存储机制的基础上提高k的上限4倍，而采用位置系数存储机制又可以在二进制存储机制的基础上再提高k的上限3倍。

表1 3种度邻接信号表存储机制的性能参数

2.2.2 冗余信息处理程序

当ACK=1时，译码程序已经恢复了部分源信号，新添加的编码信号带有冗余信息，需要进行处理，删除冗余信息，提高节点携带信息质量，加快译码算法。

经过译码，信源信号si已经被恢复。译码端接收到N个新编码信号，其中一部分编码信号携带了信源信号si的信息(该编码信号的度邻接信号表中存储有信源信号si的位置系数i)，则将该编码信号与源信号si进行异或运算，并将其度邻接信号表中的位置系数i置0。重复上述操作，至N个新编码信号及其度邻接信号表都得到处理。

3 实验数据与结论

图4 LT译码器译码码长的分布柱状图

本文设置信源信号数量 k=1536，c=0.01，δ=0.05，B=1.05，b=0.01，即第一次生成编码信号数量为 N=1.05×k≈1612，添加的编码信号数量为 N=0.01 × k≈15，进行100次实验。

图4显示了该LT译码器译码码长N的分布柱状图。通过观察发现，译码码长集中于1672～1717，当N的值增加至1717时，LT译码器的译码成功率达到了86%。通过分析，修改设置 B=1.12，b=0.01，可以在不添加编码信号的情况下使译码器以很高的概率恢复信源信号，降低译码延时，提高LT码的传输效率。

图5显示当B=1.12，b=0.01时LT译码器译码成功率与添加编码信号次数M的关系曲线。通过观察发现当第一次生成编码信号的数量为N=1.12×k≈1720时，译码成功率已经达到89%，即使译码不成功也只需添加很少数量的编码信号就能保证译码成功率达到100%。通过计算得到，通过重新设置，当信源信号长度k=1536时，LT译码器译码码长的均值为1726，编码效率达到0.890。

图5 译码成功率与添加编码信号次数的关系曲线

4 结论

本文使用反馈控制信号，控制编码信号的长度，降低了LT编码算法功耗;使用C语言函数生成随机数列，改善了编码信号的度和度邻接信号的随机选择效果;建立位置系数储存机制、缩小了储存信息所需的DSP芯片片上内存空间，提高了LT编译码器的性能;引入冗余信息处理程序，剔除编码信号的冗余，提高了译码效率。通过实验表明，当信源信息码长为1536时，本文提出的基于DSP技术实现的LT编译码算法的译码码长均值为1726，编码效率为0.890。

[1]MACKAY D J C.Fountain codes[C]//Proc.IEEE Communications.[S.l.]:IEEE Press，2005:1062－1068.

[2]LUBY M.LT Codes[C]//Proc.43rd Annual IEEE Symposium on Foundations of Computer Science.[S.l.]:IEEE Press，2002:271－280.

[3]彭玉吉.Turbo码编译码技术的研究及DSP实现[D].成都:电子科技大学，2007.

[4]张博.卷积码的译码研究及DSP实现[D].天津:天津大学，2008.

[5]陈蓉.LDPC编译码的DSP实现[D].苏州:苏州工业大学，2009.

[6]侯登峰，朱晓晶，崔慧娟，等.Raptor码在TMS320C55X DSP上的实现及优化[J].电视技术，2010，34(S2):26－30.

[7]张勇.C/C++语言硬件程序设计——基于TMS320C5000系列DSP[M].西安:西安电子科技大学出版社，2003.

[8]ZHOU Qian，CHEN Zengqiang.Application of chaos in digital fountain codes[C]//Proc.the 9th International Conference for Young Computer Scientists.[S.l.]:IEEE Press，2008:2786－2791.