标签归档:行译码

并行流水结构的RS255RS233译码器设计实现

  61RS纠错编码是目前最有效、应用最广泛的差错控制编码之一,是一种纠错能力很强的多进制BCH码,也是一类典型的代数几何码。它是由里德(Reed)和索洛蒙(Solomon)应用MS多项式于1960年首先构造出来的。

  RS码被广泛用于差错控制系统中,以提高数据的可靠性,而且可以用来构造其他码类,如级联码。在无线通信卫星通信、磁或光存储以及网络通信中RS码也有较为广泛的应用。RS码不仅具有良好的随机纠错和突发纠错能力,而且有低复杂度的编译码算法,因此被国际电信联盟(ITU)推荐为光纤子系统的前向纠错(FEC)码。RS(225,223)码被CCSDS选为常规分包遥测信道纠错编码和高级在轨系统前向和反向链路的纠错编码,是实现CCSDS标准低差错率信道纠错编码的关键部件。只要每个码字(255个符号)中出现的错误不超过16个符号,它就能将其纠正。

  近年来,关于RS(255,223)码译码器实现的算法得到了广泛的关注,但是这些算法的实现速度都不太快,即便有速度稍高的,其占用硬件资源也较多,而一些占用硬件资源较少的算法速度却很慢。本文采用基于ME算法的8倍并行设计方案,结合流水线技术,克服了上述算法的缺陷,利用尽可能少的硬件资源获得了极高的译码速度。

  因其码元取自GF(q),RS编解码过程中的所有运算都是在GF(q)的有限域上面进行。RS(n,k)码的编码过程是将k个输入信息码字,用生成多项式产生(n,k)个冗余的纠错信息码字,与原码字合成形成n个信息码字进行传输。译码是在接收端,对接收的n个码字信息进行纠错处理,恢复k个信息码字。对于1个长度为am-1符号的RS码,每个码字都可以看成是有限域GF(am)中的1个元素。最小码距为d的码字,其RS码生成多项式具有如下形式:

  对于RS(255,223)码而言,q=256,a=2,码字符号在GF(28)中。m=8,是每个RS符号的码元数;n=28-1,是每个RS码字的符号数;k=223,是RS码中信息位的符号数;t=16,是RS码字内符号的纠错能力;d=33,是最小码距。

  由于RS码为分组码,故其译码算法主要由伴随式计算、关键方程求解和钱搜索和Forney算法3部分构成,译码器结构如图1所示。

  首先,根据接收码字乘以校验矩阵得到其伴随多项式,对于RS(225,223)码,其伴随式求解式可以表示为:

  求得伴随式以后,则利用伴随多项式求解关键方程:错误位置多项式(x)和错误特征多项式(x),如下所示:

  此后,由错误位置多项式与错误特征多项式来求得错误位置与错误值。求解错误位置本设计采用穷举算法钱搜索算法来完成。同时,使用Forney公式求得错误值。最后,用延时后的接收值减去错误值,得到最后的译码输出。Forney公式可以表示为:

  其中,ei代表发生在i位置上的错误值,odd(x)代表错误位置多项式奇数次项之和。

  本设计采用8倍并行流水方案。将255个码元8倍并行后,只需要32个周期便完成所有32个伴随多项式系数的求解。然后将32个伴随多项式系数顺序输出到下一级,在此基础上采用流水线结构,周期刚好满足且不会浪费资源。本设计中所有乘法器都是采用GF(28)有限域乘法器。

  8倍并行伴随多项式的求解算法,是在迭代算法的基础上展开实现,其推导过程如下:

基于CMMB系统的LDPC译码器的设计与实现

  低密度奇偶校验(Low Density Parity Check,LDPC)码是由Gallager博士在1962年首次提出来的,由于LDPC码的误码性能能够逼近香农限,因而在无线通信、卫星通信等领域都得到了较多应用。中国移动多媒体广播(CMMB)中使用的就是LDPC纠错编码。在CMMB标准中,LDPC码长为9216,可支持1/2和3/4两种码率。作者通过深入分析CMMB中LDPC码校验矩阵的特点,采用了一种合适的硬件实现结构,因而在保证译码器较高性能和较快译码速度的情况下,以较低的硬件资源实现了两种码率的复用。

  CMMB采用规则的LDPC码,两种码率的LDPC校验矩阵有类似的规律。CMMB中1/2码率的LDPC码校验矩阵为一个4608×9216的矩阵,进一步可划分为256个18×9216行子矩阵。其中下一个行子矩阵是上一个行子矩阵的向右循环移36位,每一个行子矩阵的行重都为6;也可以把它划分为256个4608×36列子矩阵,其中后一个列子矩阵是前一个列子矩阵的向下循环移18位,每一个列子矩阵的列重都为3。同理,3/4码率的矩阵也可以进行类似的划分,可划分为256个9×9216的行子矩阵,每个行子矩阵的行重为12;当然,也可以分为256个2304×36,列重为3的列子矩阵。从校验矩阵的特点可以看出,只要存储器能存储一个行或列子矩阵的非零元素,则利用这些非零元素,就可以恢复出整个校验矩阵,从而进行译码。而且更为重要的是,对于同种码率,行子矩阵组和列子矩阵组之间在非零元素位置上有着潜在的对应关系。本文正是通过挖掘这种潜在的对应关系,设计出了一种独特的存储器调用控制策略,并成功实现了复用RAM的同时,满足了两种码率的硬件结构。

  常用的LDPC码译码算法为置信度传递解码算法(BP decoding)。该算法相对比较成熟,性能非常优异。但是,BP算法中的f(x)函数包含对数运算和指数运算,这些复杂运算大大增加了BP译码器的运算量和复杂度。Fossorier等在1999年提出了一种min-sum译码算法,即利用一种近似的方法来处理BP算法中的f(x)函数,以将对数和指数运算化简为乘法和比较运算,从而减少了译码器的运算量,但该方法在性能上也有一定损失。后来,Jinghu Chen和Fossorier又提出了修正的min-sum算法。在码长较长的情况下,修正的min-sum算法比BP算法性能只差0.03~0.05 dB,而在算法复杂度上则只需要乘以一个常量修正因子。基于以上分析,本文采用修正的min-sum算法来进行迭代更新,此更新分为校验节点更新和变量节点更新。其迭代译码步骤分为两步。

  从而达到预定的迭代次数。否则重新更新Qm=n并开始下一轮迭代。上面式中的k表示第k次迭代。

  记集合N(m)表示与校验节点相连的所有变量节点;集合M(n)表示与变量节点相连的所有校验节点;N(m)\n表示N(m)中除去变量节点n,同理,M(n)\m表示M(n)中除去校验节点m。α一般取值为0.6~0.9,本系统中通过C模型浮点和定点仿真,可以得到α的最佳取值约为0.8,为了便于移位实现,取值为0.7875或者0.8125均可。

  LDPC码的译码器通常有串行结构、并行结构和部分并行结构等。根据校验矩阵的特点,LDPC部分并行译码结构可简单分为输入和输出存储单元、VNU(变量节点运算)单元、CNU(校验节点运算)单元和中间结果存储单元。其译码器结构如图1所示。为了便于ASIC实现,本文采用单端口RAM,每块RAM由一个控制器控制以实现不同码率的地址初始化、读RAM、写RAM等操作。

  检测到输入数据有效后,可把输入的串行数据依次存到初始化RAM里。本译码器一共有36个初始化存储器,每个存储器的深度为256。第1个数据存到第1个RAM的0地址,第2个数据存到第2个RAM的0地址,依次类推,第37个数据再存到第1个RAM的1地址,直到一帧9216个数据全部存满36个RAM。同样,输出存储单元可采用类似的存储器调度方式。为了实现译码的连续性,本设计在输入和输出部分使用了乒乓结构,即采用两组相同的36个RAM交替操作方式。

  VNU单元用于完成两部分工作:一是由校验节点和初始化信息来更新变量节点的值;二是对每一列进行硬判决。检验节点更新后的值将存储到存储单元R_Mem,而硬判决后的比特值则存到输出存储单元,直到满足停止译码两个条件之一时才可输出码字。第一次垂直更新时,不用输入存储单元Q_Mem的值,而只把输入存储单元里的初始值送到VNU单元进行更新运算即可。由于两种码率下LDPC检验矩阵的列重都是3,因此,两种码率下的VNU个数都为36个,且每个VNU结构也都是4输入的VNU。每次运算时,都必须读输入存储单元和Q_Mem(除第一次迭代外)中的数据的运算结果,但应同时写入R_Mem存储单元中。本操作内部采用流水线个时钟周期。由于读地址都为0,而且读地址每次加1,因此,执行变量节点更新运算共需花费256+2个时钟,垂直更新结构的变量节点单元加法运算器结构如图2所示。

  CNU单元也包括两部分工作:一是由变量节点来更新校验节点的值,并将更新后的值存储到外部存储器;二是对每一行硬判决后的比特进行校验,以确定其是否满足校验方程,也就是对每一行所对应比特进行异或,并看结果是否为零。若所有行的异或结构都为零,则译码成功,退出迭代。在CMMB标准中,两种码率校验矩阵H的行重有所不同(分别为6和12)。为了能共用CNU模块并且共享存储器资源,笔者设计了12输入的CNU单元,并且使用9个CNU单元并行计算。这样,当码率为1/2时,1个CNU单元更新2行,9个正好更新18行;而当码率为3/4时,9个CNU单元更新9行。每个12输入的CNU单元由2个6输入CNU单元组成,通过1个选择器可控制CNU输出。l/2码率时,2个6输入CNU的输出结果可直接作为12输入CNU的输出结果,然后经缓存后送入Q_Mem;3/4码率时,2个6输入CNU的输出再经过一级比较器得出的结果,才作为12输入CNU的输出值送到Q_Mem存储。为了方便比较最后一级比较器,可在复用已有的两组6输入输出比较单元的同时,还得输出两组最小值。CNU单元电路采用流水线码率)。6输入输出CNU单元的结构简图如图3所示。

  由于两种码率时,校验矩阵第1个子矩阵中非零元素的位置不一样。故在水平更新时,RAM的初始化地址也不一样,需要用两组初始地址值。对两种码率来说,第1个行子矩阵非零元素的个数都为108(18×6或9×12)。事实上,第1个列子矩阵非零元素的个数同样为108(3×36)。第1个行子矩阵和第1个列子矩阵非零元素位置有着潜在的一一对应的关系。举例来说,第1行(下标从0开始)6个1的列位置(下标从0开始)分别为0,7,19,26,31,5664。若分析第5664列可以发现5664=157×36+12,即5664列是第12列的移位。第12列中非零位置对应的行号为0,119,1783=99×18+1。第5664列中非零位置对应的行号为1,826,2945。于是非零位置(1783,12)的映射为(1,5664)。这样,通过挖掘行子矩阵和列子矩阵中每一个非零位置的对应关系,就能准确地得出VNU和CNU运算单元数据之间的对应关系。把这种对应关系体现到memory的调度上来,就能准确地从R_Mem和Q_Mem中取值以进行水平和垂直更新。表1所列是中间结果存储单元和写地址的对应关系。

  这里分别用了108个深度为256、宽度为6bits的单口RAM作为R_Mem和Q_Mem。当进行变量节点运算时,VNU输入可从Q_Mem中读取,读数时,首地址为0,VNU输出写入R_Mem中,写顺序首地址为黑体数字,运算周期为256;当所有变量节点更新后,接着是校验节点的运算,同时

  可进行检验方程运算。此时,CNU输入从R_Mem中读取,读数的首地址为0,CNU输出写入Q_Mem中,写入顺序首地址为黑体数字,运算周期同样为256。如此交替,便可完成迭代过程。上述例子中,(1,5664)和(1783,1)的对应关系反映在存储单元上,正如表1中的第2列所示。

  作者通过C语言模型和MATLAB模型对译码器进行了浮点和定点仿真。为了达到性能和面积的平衡,位宽的取值为6 bits,而译码器性能只比浮点模型损失了约0.15 dB。在AWGN信道和BPSK的调制解调方式下,当码率为1/2,信噪比SNR为1.6 dB时,误码率已经降至10-5以下。而在信噪比SNR为1.7 dB时,误码率已经降至10-7以下;当码率为3/4时,在信噪比SNR为3.0 dB时,误码率可以降至10-6以下。

  本文按照上面所描述的硬件结构,采用XILINX的VirtexIV-XC4VLX80器件实现了CMMB标准中两种码率的LDPC译码,并且达到了和C定点模型同样的性能。在ISE开发工具上对其进行编译时,其具体的资源利用情况如表2所列。

  从表2中可以看出,此结构不仅完全地复用了存储器资源,而且最大限度地复用了逻辑运算单元。正是因为两种码率可复用RAM资源,使memory消耗较少,从而剩下大量的RAM资源可以用作CMMB其余部分(如解交织模块)使用。LUT资源相对来说用得较多,这是由于并行结构造成的,它有36个VNU和9个CNU交替进行运算。

  本文设计的部分并行结构的LDPC译码器能够兼容不同码率和不同校验矩阵行重的LDPC码。运用该译码结构在XILINX的VirtexIVC4VLX80器件上可实现CMMB标准中两种码率的LDPC译码。事实上,针对校验矩阵的特点,采用一种独特的存储器控制策略,可以最大限度地复用硬件资源,从而大大减少了译码器的资源消耗。

几行代码就搞乱了苹果发布会直播 火了Chinese lady

  苹果昨晚的发布会官方视频直播出现了一系列故障,导致许多苹果粉丝无法观看iPhone 6和Apple Watch的发布。

  其中,发布会前30分钟的影响最大,许多用户看到的是一个测试画面,而不是CEO蒂姆库克(Tim Cook)介绍新产品。

  影响远不止于此。当视频直播恢复后,现场的中文同声传译的声音居然比英语原声还要大。此次苹果发布会仍面向全球同步直播,与往年不同的是,此次发布会加入了中文同声传译,而这却让“chinese lady”狠狠的火了一把!

  对于一向精心准备的苹果,这一次的视频直播表现为何如此糟糕呢?罪魁祸首就在于几行JavaScript代码。

  为了此次视频直播,苹果为面添加了一些JSON (JavaScript Object Notation)代码,旨在为页面增加互动元素,在底部显示有关此次发布会的推文(Twitter消息)。

  这一调整导致页面几毫秒就刷新一次调用,添加几行JSON代码就意味着网站无法缓存,从而影响了视频质量。

  之前,苹果通常使用Akamai缓存系统进行视频直播。但这一次,由于苹果使用了JSON代码,导致Akamai服务器无法缓存。

  至于前27分钟现场的中文同声传译一直压制着英语原声,错误全部在于苹果自身。业内人士称,一定是苹果员工没有正确设置译码器,导致主要和备份数据流不同步。

  该知情人士称,应该是译码器在发布会开始后被重新启动,这就是导致Apple TV和iOS用户接到“无法加载视频”和“无权限访问错误信息”等提示的原因。