一种LT编译码算法的DSP硬件实现方法

摘要

一种LT编译码算法的DSP硬件实现方法，包括异步串行通信收发器、TMS320VC5416芯片、FIASH芯片、电源调节器芯片、LT编码器和译码器，采用异步串行通信收发器来实现异步数据传输，使用电源调节器芯片给TMS320VC5416芯片供电，使用FIASH芯片保存编译码程序段，LT译码器从异步串行通信收发器接收到编码信号后进行译码，译码过程中LT译码器通过通讯信道发送反馈信息给LT编码器，控制LT编码器的工作，便捷地实现LT编译码算法，并且提高算法效率，充分减少DSP芯片片上内存使用量的一种LT编译码算法的DSP实现方法。

说明书

技术领域

本申请涉及一种基于DSP技术实现LT编译码算法的方法，该方法可以广泛的运用于有线数字通讯，数字存储，多源下载等技术领域。

背景技术

随着信息技术的高速发展，传统的TCP/IP协议由于数据传输时延较大，并不适合互联网中大容量信息的实时传输，因此研究学者提出了纠删编码技术。即发送端把需要传输的K个源信息包通过编码，整合成N个编码包，通过网络发送出去。接收端接收到这个N个编码包中的任意K个编码包就能使用特定的译码方法以很高的概率重构这K个源信息包。

1998年Bayers等提出了一类新的纠删码--Fountain码。它具有鲁棒性和可靠性，且可以在无反馈信道下，以任意的码率传输数据，从而简化了网络中数据的传输方式，使其得成为一类适用于可靠通信的有效编码技术，在远距离，大容量的实时传输中具有广阔的应用前景。

2003年Lucy提出了第一类Fountain码，也是第一类码率不受限制的码--LT码。LT码对于具有不同删除概率的各种删除信道均是逼近最优的^【1】。由于LT码的诸多优点，LT码被认为是适用于可靠多播传输、多源下载、数据存储和无线协作传输等应用方向最有前途的编码技术，在国际上掀起了一场LT码的研究热潮。

近些年，随着信息技术地高速发展，人们迫切地需要将各种先进的编码技术引入实际运用。由于DSP技术精度高，速度快，成本低，灵活性强，可靠性好的特点，DSP技术被越来越多了运用于信道编码技术中。通过研究，Turbo码，卷积码^[3]，LDPC码^[4]等大部分早期码的编译码器都通过DSP等技术得以实现。但由于DSP芯片的处理能力和内存空间都十分有限，使用DSP技术实现LT码编译码器必须要解决两个难题：1）如何设计编译码算法，简化程序，减少CPU负担；2）如何建立信息储存机制，存储度邻接信号表，合理利用DSP芯片片上内存资源。

发明内容

本发明为解决上述技术问题，提供一种设计使用TI公司的TMS320VC54146芯片，便捷地实现LT编译码算法，并且提高算法效率，充分减少DSP芯片片上内存使用量的一种LT编译码算法的DSP实现方法。

本发明为解决上述技术问题所采用的技术方案是：一种LT编译码算法的DSP硬件实现方法，包括异步串行通信收发器、TMS320VC5416芯片、FIASH芯片、电源调节器芯片、LT编码器和译码器，采用异步串行通信收发器来实现异步数据传输，使用电源调节器芯片给TMS320VC5416芯片供电，使用FIASH芯片保存编译码程序段，LT译码器从异步串行通信收发器接收到编码信号后进行译码，译码过程中LT译码器通过通讯信道发送反馈信息给LT编码器，控制LT编码器的工作；

步骤一、LT编码器从通讯信道中接收到k个源信号，确定首次生成编码信号的数量N=1.05×k；

步骤二、根据鲁棒弧波分布确定编码信号的度分布率μ(k)，根据μ(k)将时隔[0,1]划分成非重复不等间隔的k个子时隔，一个子时隔对应一个不同的度值，使用C语言内部函数生成[0,1]区间的随机数列，根据随机数列中第i项的值确定第i个编码信号的度值d_i；

步骤三、使用函数生成[0,k]区间长度d_i为的随机数列{a_di}，取出第a_i(i=1,2,…,d_i)个源信号做为该编码信号的度邻接信号，异或运算得到编码信号e_i；

步骤四、重复步骤二和步骤三，生成N个编码信号, 通过通信信道发送；

步骤五、译码器接收到所有的编码信号后，根据预先在编码器和译码器设立的seed表，确定seed值，进而得到编码信号的度和度邻接信号表，将编码信号及其度邻接信号表分别存储于数据链表L₁和L₂中；

步骤六、 寻找度为1的编码信号开始进行译码，当编码信号被释放后，删除存储该编码信号的数据链表L₁中节点，及存储其度邻接信号表的数据链表L₂中节点，重复以上操作至度为1的编码信号耗尽；

步骤七、如源信号未被完全恢复，则生成反馈控制信号ACK=1,反馈到编码器，编码器在接收到ACK=1信号后，重复步骤二至步骤四，添加生成N=0.01×k个编码信号；

步骤八、译码器接收到所有的新编码信号后进行冗余信息处理，将已恢复源信号的信息更新至所有的新编码信号及其度邻接信号表中，继续进行译码，重复步骤五至步骤七，至源信号被完全恢复停止处理。

本发明的优点：使用反馈控制信号ACK，实现根据编码器实际需要生成最少数量编码信号的功能，简化LT编码过程。使用C语言内部函数生成随机数列，改善编码信号的度和度邻接信号的随机选择效果。建立二进制位储存机制、构建数据链表，不但缩小储存信息所需的DSP芯片片上内存空间，还方便信息的添加和删除。引入冗余信息处理程序，剔除编码信号的冗余，提高了译码效率。

附图说明

图1是本发明的系统硬件结构框图；

图2是本发明的LT编码算法的软件流程图；

图3是本发明的LT译码算法的软件流程图；

图4是本发明的度邻接信号表存储机制示意图。

具体实施方法

下面结合附图对本发明的一种LT编译码算法的DSP硬件实现方法进行说明。

一种LT编译码算法的DSP硬件实现方法，包括异步串行通信收发器、TMS320VC5416芯片、FIASH芯片、电源调节器芯片、LT编码器和译码器，采用异步串行通信收发器来实现异步数据传输，使用电源调节器芯片给TMS320VC5416芯片供电，使用FIASH芯片保存编译码程序段，LT译码器从异步串行通信收发器接收到编码信号后进行译码，译码过程中LT译码器通过通讯信道发送反馈信息给LT编码器，控制LT编码器的工作。

如图1所示，在编码器中，源信号通过串口（RS232接口）传入芯片。由于数据采用异步传输，可以采用DSP的McBSP结合DMA，在不扩展硬件的情况下，用软件实现异步数据传输。但该方法软件设计复杂，加大了CPU的负担，因此添加TI公司的TL16C550异步串行通信收发器来实现异步数据传输。

使用TI公司的双路低压差电源调节器芯片TPS767D301给TMS320VC5416芯片提供1.6V的工作电压。

使用TI公司的FIASH芯片AM29LV800保存编译码程序段，以便在系统启动时将编(译)码程序装载进DSP内部DARAM运行。

下面结合附图对本发明的一种LT编码算法的DSP软件实现方法进行说明。如图2所示，其具体步骤如下：

步骤一、使用反馈控制信号ACK， ACK由译码器判定生成，控制编码信号的生成，初值设定为ACK=0。当译码器中源信号未被完全恢复时，译码器生成ACK=1，反馈到编码器；当译码算法结束，ACK=0，编码器停止工作，LT编译码结束。

步骤二.编码器从通讯信道中异步接收到k个源信号，确定生成编码信号的数量N=1.05×k。

步骤三、根据鲁棒弧波分布确定编码信号的度分布率μ(k)，根据μ(k)将时隔[0,1]划分成非重复不等间隔的k个子时隔，一个子时隔对应一个不同的度值。例如：0.0~μ(1)对应度值1，μ(i) ~μ(i+1)对应度值i+1。

步骤四、使用srand函数设置随机数发生器的初始化种子seed=s₁。使用rand函数生成 [0,1]区间长度为N的随机数列。确定随机数列中第i项值所处的子时隔，根据对应关系确定第i个编码信号的度值d_i。

步骤五、设置随机数发生器的初始化种子seed=s₂(s_1≠s₂)，生成[0,k]区间长度为d_i的不重复随机数列{a_di}。

步骤六、取第a_i(i=1,2,…,d_i)个源信号做为该编码信号的度邻接信号。异或运算得到该编码信号e_i，通过通讯信道发送。

步骤七.当编码器接收到ACK=1信号时，生成N=0.01×k个编码信号。记M为添加编码信号的次数，T为已生成的编码信号的数量，M初值位0，编码器每次接收到ACK=1信号M自动加1。T=1.05×k+(M-1)×0.01×k。

步骤八、重复步骤三，生成[0,1]区间长度为1.05×k+M×0.01×k的随机数列，确定随机数列中第T+i项值所处的子时隔，根据对应关系确定新加的第i个编码信号的度值d_i。

步骤九、记前T个编码信号的度值总和为n。

步骤十、生成[0,k]区间长度为n+d₁的不重复随机数列，取出该数列中元素n+1~n+d₁，组成随机数列{b_d1}。取出{b_d1}中第b_i(i=1,2,…,d₁)个源信号做为编码信号e₁的度邻接信号，异或运算得到该编码信号e₁。

步骤十一、生成[0,k]区间长度为d_i(i≠1)的不重复随机数列{b_di}。取出第b_i(i=1,2,…,d_i)个源信号做为编码信号e_i的度邻接信号，异或运算得到该编码信号e_i。

下面结合附图对本发明的一种LT译码算法的DSP软件实现方法进行说明。如图2所示，其具体步骤如下：

步骤一、译码器在接收编码信号分组后根据seed表序列号确定seed值，参照[0038]-[0048] 内容得到编码信号的度和度邻接信号表。

采用二进制位存储机制将编码信号及其度邻接信号表分别存储于数据链表L₁、L₂中。

为了减少DSP芯片片上内存使用量，提高DSP芯片译码效率。采用二进制位存储机制将度邻接信号表分别存储于整形数组中，即在16bit的整型数据中存储16位度邻接信号信息。然后构建数据链表，将每一个度邻接信号表存储于数据链表节点上，方便信息地插入和删除。如附图4所示。

对度邻接信号表信息进行更新操作通过位操作实现。为方便操作，定义两个位置参数h和l，对于度邻接信号表第i位：

h=i/16；l=i%16。

对度邻接信号表第i位进行操作，只需对整型数组中第h个元素的第l位进行位操作。例如：将度邻接信号表的第35位置1，需将整型数组中的第2个元素与0x0004进行按位或运算。

步骤二、寻找度为1的编码信号e_j开始进行译码。将e_j值赋予其唯一的度邻接信号s_i，释放e_j。

当编码信号被释放后，删除存储该编码信号的数据链表L₁中节点。此时存储其度邻接信号表的数据链表L₂中节点内为无用信息（全零整形数组），也将此节点删除。

将s_i与度邻接信号表第j位为1的编码信号进行异或运算，并将该编码信号度邻接信号表第j位置0，源信号s_i恢复成功。

步骤103.重复以上步骤，至度为1的编码信号耗尽。如源信号未被完全恢复，则生成反馈控制信号ACK=1,编码器添加编码信号。

当ACK=1时，译码程序已经恢复了部分源信号，数据链表L₁，L₂节点带冗余信息，需要进行处理.

则将该编码信号与源信号s_i进行异或运算，并将其度邻接信号表的第i位置0。重复上述操作，至N个新编码信号及其度邻接信号表都得到处理，删除冗余信息，提高节点携带信息质量。

重复译码算法步骤101,102至源信息被完全恢复，译码过程结束。

本发明解决了译码器根据实际情况生成最少数量编码信号的问题，减少了编码器不必要的工作，降低了编码器的功耗。使用C语言内部函数对编码信号的度和度邻接信号进行随机选择，改善了两者的随机选择效果，提高了LT编译码算法效率。

本发明采用二进制位存储机制将度邻接信号表储存于整形数组中，再构建数据链表，不但减小了DSP芯片片上内存空间的使用量，而且方便信息的添加和删除，简化了LT译码过程。引入冗余信息处理程序，剔除了编码信号中的冗余，提高节点携带信息的质量，一定程度上加快了译码算法。

以上仅为本发明的优选实施方案，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有任何更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。