留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种高吞吐率的系统Raptor码并行译码方法

任雁鹏 管武 梁利平

任雁鹏, 管武, 梁利平. 一种高吞吐率的系统Raptor码并行译码方法[J]. 电子科技大学学报, 2018, 47(6): 814-818. doi: 10.3969/j.issn.1001-0548.2018.06.003
引用本文: 任雁鹏, 管武, 梁利平. 一种高吞吐率的系统Raptor码并行译码方法[J]. 电子科技大学学报, 2018, 47(6): 814-818. doi: 10.3969/j.issn.1001-0548.2018.06.003
REN Yan-peng, GUAN Wu, LIANG Li-ping. A High Throughput Parallel Decoding Method for Systematic Raptor Codes[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(6): 814-818. doi: 10.3969/j.issn.1001-0548.2018.06.003
Citation: REN Yan-peng, GUAN Wu, LIANG Li-ping. A High Throughput Parallel Decoding Method for Systematic Raptor Codes[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(6): 814-818. doi: 10.3969/j.issn.1001-0548.2018.06.003

一种高吞吐率的系统Raptor码并行译码方法

doi: 10.3969/j.issn.1001-0548.2018.06.003
基金项目: 

国家自然科学基金面上项目 61471354

详细信息
    作者简介:

    任雁鹏(1984-), 男, 博士生, 主要从事纠错编码、无线通信协议等方面的研究

  • 中图分类号: TN919.3

A High Throughput Parallel Decoding Method for Systematic Raptor Codes

图(4) / 表(3)
计量
  • 文章访问数:  3919
  • HTML全文浏览量:  1174
  • PDF下载量:  62
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-02-02
  • 修回日期:  2018-07-12
  • 刊出日期:  2018-11-01

一种高吞吐率的系统Raptor码并行译码方法

doi: 10.3969/j.issn.1001-0548.2018.06.003
    基金项目:

    国家自然科学基金面上项目 61471354

    作者简介:

    任雁鹏(1984-), 男, 博士生, 主要从事纠错编码、无线通信协议等方面的研究

  • 中图分类号: TN919.3

摘要: 在系统Raptor码译码中,针对高复杂度的高斯消元运算导致译码延时大、吞吐率低的问题,提出一种低延时高吞吐率的降维并行译码方案。该方案采用仅对少量丢包译码的低复杂度降维运算,替换对全部源数据包译码的高斯消元运算,降低译码延时;并针对降维译码采用全并行的硬件结构实现,提高译码吞吐率。依此方案,在Xilinx FPGA XC7K410T平台上实现系统Raptor译码器。测试结果表明,当网络丢包率在10-2以下时,译码数据吞吐率达到3.5 Gbps,是相同硬件下采用高斯消元译码实现的80倍以上。

English Abstract

任雁鹏, 管武, 梁利平. 一种高吞吐率的系统Raptor码并行译码方法[J]. 电子科技大学学报, 2018, 47(6): 814-818. doi: 10.3969/j.issn.1001-0548.2018.06.003
引用本文: 任雁鹏, 管武, 梁利平. 一种高吞吐率的系统Raptor码并行译码方法[J]. 电子科技大学学报, 2018, 47(6): 814-818. doi: 10.3969/j.issn.1001-0548.2018.06.003
REN Yan-peng, GUAN Wu, LIANG Li-ping. A High Throughput Parallel Decoding Method for Systematic Raptor Codes[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(6): 814-818. doi: 10.3969/j.issn.1001-0548.2018.06.003
Citation: REN Yan-peng, GUAN Wu, LIANG Li-ping. A High Throughput Parallel Decoding Method for Systematic Raptor Codes[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(6): 814-818. doi: 10.3969/j.issn.1001-0548.2018.06.003
  • 数字喷泉码技术以其高性能的纠错能力,得到广泛的青睐。其中的低复杂度码型——系统Raptor码[1-2],更是广泛应用于无线传输领域[3-5]。系统Raptor码在编码时,对源数据包增加少量冗余包;在译码时,通过接收到的源数据包和冗余包纠正传输过程中的丢包,实现数据恢复。这种以包为单位的纠错方法,具有较高的吞吐率和较低的复杂度,在高速数据传输中优势明显。

    随着超高清、3D视频以及海量数据的高速传输,未来无线数据传输吞吐率将达到1 Gbps以上。然而,当前3GPP标准(3rd generation partnership project)中采用的系统Raptor码技术,速率还在100 Mbps量级,已经无法满足高速传输的需求。需要更高速率的系统Raptor码编码译码技术。

    目前,许多学者都在进行系统Raptor码的改进和优化。文献[6]发现系统Raptor码运算耗时最大的部分为译码中的高斯消元运算,其占整个译码总时间的91%以上;并提出优化失活译码高斯消元算法,将传统高斯消元算法中矩阵求逆的计算复杂度由O(L3)降低至O(L),其中L为与源数据包数量相关的参数。矩阵递归求逆译码算法[7]和矩阵降维快速译码算法[8]基于系统Raptor码的部分码——系统RaptorQ码,实现了软件优化,但速率较低。文献[9]采用CPU(central processing unit)+GPU(graphics processing unit)的模式进行系统Raptor码并行加速,使无线数据传输吞吐率达到21 Mbps。文献[10-11]则采用FPGA(filed programmable gate array)进行高斯消元运算的硬件加速,进一步提升吞吐率。

    上述方案针对高斯消元运算的改进和优化,使译码性能得到了提升。但是,其译码过程中,高斯消元运算需要译码出所有源数据包,译码运算复杂度大、串行依赖度高,无法大幅降低译码延时,提高译码吞吐率。实际上,数据传输中仅存在少量丢包;如果能够只对丢失的少量数据包进行译码,则可大大降低译码复杂度。本文经过对译码过程的分解,提出了一种低复杂度的降维译码算法。该算法仅对丢失的数据包进行译码,并采用全并行的硬件加速结构,实现低延时高吞吐率的系统Raptor码译码器。

    • 系统Raptor码的编译码原理如图 1所示。发送端,编码器对源数据分别进行预编码和LT(Luby transform)编码,生成编码数据。编码数据包含所有源数据和少量冗余数据。编码数据经物理信道发送给接收端。物理信道呈删除信道的特征,会有少量编码数据的丢失。接收端,译码器对接收到的数据包进行预译码和LT译码,纠正信道中丢失的数据包,恢复出所有的源数据包[1]

      图  1  系统Raptor码编译码原理图

    • 系统Raptor码编码时,首先,源数据包T=[t0, t1, …, tK-1]和零矩阵Z1×(S+H)构成预编码输入矢量D=[Z1×(S+H), T]T,其中K为源数据包的数量,SH分别为预编码参数,由K计算得出。输入矢量D与预编码矩阵的逆矩阵A-1进行二进制乘法,生成L个预编码码字C=[c0, c1, …, cL-1]T,其中L=K+S+H

      $$ \mathit{\boldsymbol{C}} = {\mathit{\boldsymbol{A}}^{ - 1}}\mathit{\boldsymbol{D}} $$ (1)

      然后,进行LT编码,生成编码码字E=[e0, e1, …, eN-1]T

      $$ \mathit{\boldsymbol{E}} = {\mathit{\boldsymbol{G}}_{{\text{LT}}}}\mathit{\boldsymbol{C}} $$ (2)

      式中,GLT是一个N×L的矩阵,NK;码字E包含K个源数据包和N-K个冗余包。

    • 接收端,首先进行预译码。译码端接收到Nr个码字E′=[e0, e1, …, eNr-1] (K < NrN)。E′和零矩阵Z1×(S+H)构成预译码输入矢量D′=[Z1×(S+H), E′]T。根据接收码字的ESI(encoding symbol ID,编码符号索引号),重建与E′对应的预译码矩阵AM×L,其中M= Nr+S+HAM×L的行数M跟列数L不相等,无法进行求逆运算。在计算预译码码字C'=[c0, c1, …, cL-1]T时,需通过高斯消元法进行运算:

      $$ \mathit{\boldsymbol{D'}} = {\mathit{\boldsymbol{A'}}_{M \times L}}\mathit{\boldsymbol{C'}} $$ (3)

      然后,进行LT译码,得到所有源数据包T

      $$ \mathit{\boldsymbol{T}} = {\mathit{\boldsymbol{G'}}_{{\text{LT}}}}\mathit{\boldsymbol{C'}} $$ (4)

      式中,${\mathit{\boldsymbol{G'}}_{{\text{LT}}}}$是一个K×L的矩阵,根据已接收冗余包的ESI构建。

      传统系统Raptor码的译码结构如图 2所示。接收端首先接收编码码字,并根据ESI构建${\mathit{\boldsymbol{A'}}_{M \times L}}$和${\mathit{\boldsymbol{G'}}_{{\text{LT}}}}$。然后执行高斯消元的预译码和LT译码,得到所有源数据包。预译码和LT译码串行执行。

      图  2  系统Raptor码译码串行执行结构

      在译码过程中,高斯消元需经过逐行列的递进处理,串行依赖性高,运算复杂度为O(L3)[12]。即使采用硬件加速,也只能对局部运算并行实现,降低译码延时的效果有限。而且随着K的增大,高斯消元运算的复杂度大幅增长,严重影响译码延时和吞吐率。

    • 传统系统Raptor码译码延时大,无法满足未来无线传输高吞吐率的需求。在实际中,接收数据仅存在少量丢包。只要译码出丢包数据,即可完成纠错。本节对传统系统Raptor码译码算法进行分解,结合系统Raptor码编码的已知矩阵,提出低复杂度的降维译码方案,降低译码延时。

      根据式(1)与式(2),系统Raptor码的编码可表示为:

      $$ \mathit{\boldsymbol{E}} = {\mathit{\boldsymbol{G}}_{{\text{LT}}}}\mathit{\boldsymbol{C}} = {\mathit{\boldsymbol{G}}_{{\text{LT}}}}{\mathit{\boldsymbol{A}}^{ - 1}}\mathit{\boldsymbol{D}} $$ (5)

      经过删除信道丢包后,接收端共收到Nr个编码包,其中包含Kr(KrK)个源数据包Tr=[t0, t1, …, tKr-1]和Nr-Kr个冗余包R=[r0, r1, …, rNr-Kr-1]。丢失的K-Kr个源数据包记为Tx=[tx0, tx1, …, txK-Kr-1]。

      在式(5)中,当有丢包时,实际接收的数据包构成E′。根据实际接收冗余包的ESI重新构建LT矩阵为GLT″。输入矢量Drx由零矩阵Z(S+H)×1TrTTxT构成,其中TrTx中的各元素根据ESI置于Drx的相应位置。式(5)变换为:

      $$ \mathit{\boldsymbol{E'}} = {\mathit{\boldsymbol{G''}}_{{\text{LT}}}}\mathit{\boldsymbol{C}} = {\mathit{\boldsymbol{G''}}_{{\text{LT}}}}{\mathit{\boldsymbol{A}}^{ - 1}}{\mathit{\boldsymbol{D}}_r}_x $$ (6)

      式中,${\mathit{\boldsymbol{G''}}_{{\text{LT}}}}$是一个Nr×L的矩阵;Drx是一个L×1的矩阵。

      式(6)对输入矢量Drx中的源数据包进行分解,拆分成两个输入矢量Dr0D0xDr0D0x都是L×1的矩阵。Dr0包含所有已接收的源数据包,其中丢包的地址用0填充。D0x为待求的丢包矩阵,D0x中对应已接收数据包的地址都为0。式(6)分解为:

      $$ \mathit{\boldsymbol{E'}} = {\mathit{\boldsymbol{G''}}_{{\text{LT}}}}{\mathit{\boldsymbol{A}}^{ - 1}}{\mathit{\boldsymbol{D}}_{{\text{r0}}}} + {\mathit{\boldsymbol{G''}}_{{\text{LT}}}}{\mathit{\boldsymbol{A}}^{ - 1}}{\mathit{\boldsymbol{D}}_0}_{\text{x}} $$ (7)

      进一步变换,得出系统Raptor码的降维译码公式为:

      $$ {\mathit{\boldsymbol{G''}}_{{\text{LT}}}}{\mathit{\boldsymbol{A}}^{ - 1}}{\mathit{\boldsymbol{D}}_0}_x = \mathit{\boldsymbol{E'}} - {\mathit{\boldsymbol{G''}}_{{\text{LT}}}}{\mathit{\boldsymbol{A}}^{ - 1}}{\mathit{\boldsymbol{D}}_{r{\text{0}}}} $$ (8)

      当网络丢包率较低时,丢包数量远小于源数据包数量KD0x中待求的丢包元素很少,求解D0x可实现系统Raptor码的降维运算。另外,在式(8)的运算中,使用预编码逆矩阵A-1替代预译码矩阵AM×L,避免了对AM×L的高斯消元运算,大幅降低运算复杂度和译码延时。

      对式(8)的各项进一步分解:

      $$ \mathit{\boldsymbol{A''}}{\mathit{\boldsymbol{D}}_0}_x = \mathit{\boldsymbol{E'}} - \mathit{\boldsymbol{Y}} $$ (9)

      其中:

      $$ \mathit{\boldsymbol{A''}} = {\mathit{\boldsymbol{G''}}_{{\text{LT}}}}{\mathit{\boldsymbol{A}}^{ - 1}} $$ (10)
      $$ \mathit{\boldsymbol{Y}} = {\mathit{\boldsymbol{G''}}_{{\text{LT}}}}\mathit{\boldsymbol{X}} $$ (11)
      $$ \mathit{\boldsymbol{X}} = {\mathit{\boldsymbol{A}}^{ - 1}}{\mathit{\boldsymbol{D}}_{{\text{r0}}}} $$ (12)

      由式(9)可以看出,根据实际接收的数据E′、参数A″和Y,即可求解出丢失的数据D0x。在译码过程中,对于给定的K值,A-1为已知矩阵;对于A″和Y,可根据已接收的源数据包Dr0和冗余包进行并行运算得到。

      经过对传统系统Raptor码算法的分解,仅对丢失的数据包进行译码,实现降维运算。运算中使用已知的预编码矩阵A-1替换原始的预译码矩阵AM×L,避免了复杂的高斯消元运算。实现了低复杂度的降维译码,降低了译码延时。

    • 结合系统Raptor码的降维译码算法,本节给出低延时的降维并行译码结构,如图 3所示。译码主要包括3个运算模块:源数据包处理模块、冗余包处理模块和丢包计算模块。源数据包处理模块对式(12)进行运算。根据已接收的源数据包,计算得出矩阵X中的元素。冗余包处理模块根据已接收的冗余包构建LT译码矩阵${\mathit{\boldsymbol{G''}}_{{\text{LT}}}}$,并计算式(10)和式(11)中$\mathit{\boldsymbol{A''}}$和Y中的元素。然后根据式(9)计算丢包D0x,完成整个译码过程。在该结构中,所有接收到的源数据包和冗余包并行处理,降低运算延时,提高译码吞吐率。

      图  3  系统Raptor码降维并行译码结构

      根据图 3的降维并行译码结构,设计系统Raptor码的全并行硬件结构,如图 4所示。在系统Raptor码中,对于给定K值,其A-1为确定的,可以将A-1预先存储在寄存器中。冗余包处理模块处理接收到的冗余包,源数据包处理模块处理接收到的源数据包,最后计算丢包。所有接收的数据包存入寄存器中。下面对各模块的运算做具体说明。

      图  4  系统Raptor码全并行降维译码硬件结构

    • 首先将接收数据包根据ESI存储到E′的对应位置。发送端发送完一组数据后,接收端根据ESI查询源数据。如果全部接收则不需译码;如果存在丢包,则保存丢包的ESI并等待恢复。

      然后利用接收的源数据包计算矩阵X。根据接收包的ESI查找A-1对应的矩阵行,将A-1与接收包进行与和异或运算,得出X中该ESI对应的值。所有源数据包的运算并行执行,降低译码延时。

    • 根据冗余包的ESI查找生成矩阵表GLT,将GLT中ESI对应的行组合在一起重新构建LT译码矩阵${\mathit{\boldsymbol{G''}}_{{\text{LT}}}}$。然后根据式(10)和式(11)计算$A''$和Y。${\mathit{\boldsymbol{G''}}_{{\text{LT}}}}$为稀疏矩阵,A-1和${\mathit{\boldsymbol{G''}}_{{\text{LT}}}}$矩阵都为0~1矩阵。在硬件实现中,将${\mathit{\boldsymbol{G''}}_{{\text{LT}}}}$矩阵中1对应的地址与A-1中的值进行与和异或运算,计算出译码逆矩阵$A''$。同理,${\mathit{\boldsymbol{G''}}_{{\text{LT}}}}$与矩阵X进行运算得到矩阵Y

      该结构可以对所有冗余包并行处理,不需采用串行处理的模式,这样就避免了类似高斯消元中逐行列串行处理的耗时。

    • 接收端收到Nr个接收包时,查询ESI并确定丢包位置,计算丢包。根据式(9),使用矩阵Y、$A''$和E′计算丢包矩阵D0x

      在系统Raptor码全并行的降维译码硬件结构中,所有已接收的源数据包和冗余包并行运算,源数据包处理模块和冗余包处理模块并行执行,可以在很少的时钟周期内计算出所有丢包,大幅降低了译码延时,提高译码吞吐率。

    • 结合本文提出的全并行降维译码方案,在Xilinx Kintex-7系列的410T FPGA芯片实现系统Raptor码译码器。源数据包数量K取216,网络丢包率为10-2量级,单个数据包的位宽W为4 Byte。采用Xilinx软件平台进行硬件综合和功耗估计,结果如表 1所示。其中逻辑单元需67 539个,占芯片总资源的26.5%,最高运行时钟为128.2 MHz,功耗为1 155 mW。

      表 1  系统Raptor码译码器的硬件开销与性能

      类型 结果 占比
      逻辑单元/个 67 539 26.5%
      寄存器/个 11 486 2.26%
      块存储器/个 38.5 4.84%
      功耗/mW 1 155 N/A
      最高时钟/MHz 128.2 N/A
    • 在本文提出的降维译码方案中,当K为216时,根据网络丢包率得出编码包数N为230。经仿真,对源数据包和冗余包的并行处理,最多仅需N个时钟周期。对丢包的计算,仅需6个时钟周期。即完成一次系统Raptor码译码共需N+6个时钟周期。

      与之相比,如表 2所示。文献[11]的译码器采用图 2的串行译码结构。源数据包数量K为12,需延时79个时钟周期完成高斯消元运算和LT译码,而且随着K的增大,译码延时大幅增长。本文在K取12时,根据丢包率计算N为14,仅需20个时钟周期可完成译码。而且本文的译码延时随K的变化很小,有效降低了译码延时。

      表 2  系统Raptor码译码延时比较

      源数据包数K/个 文献[11]/个 本文/个
      12 79 20
      216 N/A 236
    • 结合上边的仿真结果,当系统运行时钟fClk取128.2 MHz时,每秒可以完成的系统Raptor码译码次数S为:

      $$ S = {f_{{\text{Clk}}}}{\text{/(}}N{\text{ + 6) = 543 220}} $$ (13)

      则数据吞吐率为:

      $$ 吞吐率 = 8 \times W \times K \times S = 3.75\;{\rm{Gbps}} $$ (14)

      式中,W为每个源数据包的字节数。本文采用W为4字节的Raptor码,译码数据吞吐率可达3.75 Gbps。

      本文的硬件方案与相关文献的硬件加速方案的性能比较结果如表 3所示。其中文献[9]采用3 GHz的i7 CPU与732 MHz的GPU联合平台,文献[10-11]采用FPGA硬件平台,主要对高斯消元法进行硬件加速实现。

      表 3  系统Raptor码译码性能比较

      方案 文献[9] 文献[10] 文献[11] 本文
      硬件平台 CPU + GPU Altera StratixⅢ Xilinx Kintex-7 Xilinx Kintex-7
      最高时钟/MHz 3 000 100 230 128.2
      归一化功耗/mW N/A 9.88×10-4 3.24×10-4 3.08×10-7
      吞吐率/bps 21 M 1.05 M 46.5 M 3.75 G

      表 3可以看出,本文的降维译码方案,仅对丢包进行译码,并且采用已知的预编码矩阵,替代需进行高斯消元的预译码矩阵,避免了对所有源数据包译码的高斯消元运算,实现了低复杂度的降维译码。在全并行降维译码的硬件结构中,所有已接收的源数据包和冗余包并行运算,大幅降低了译码延时。在单位时间内完成更多次的译码运算,实现了高吞吐率的译码和传输。

    • 本文对系统Raptor码高复杂度的高斯译码算法进行改进,提出了一种低复杂度的降维译码算法。在该算法中,仅对少量丢包进行译码,替代传统译码算法中对全部源数据包译码的高斯消元运算,实现译码维度的大幅降低。并采用全并行的结构实现降维译码算法,最终在Xilinx FPGA XC7K410T上实现了该译码器。测试结果表明,当网络丢包率在10-2以下时,译码器译码延时大幅降低;其译码吞吐率可达到3.5 Gbps,是相同平台下采用高斯消元译码的80倍以上。该方案有效提高了系统Raptor码的译码效率,降低了译码延时,提高了数据传输吞吐率。

参考文献 (12)

目录

    /

    返回文章
    返回