CN108768407A - 一种低硬件成本、高吞吐率的硬判决译码器架构 - Google Patents

Abstract

本发明涉及一种低硬件成本、高吞吐率的硬判决译码器架构，基于mCS‑RiBM硬判决译码器架构实现，改进之处包括下列几个方面：(1)采用并行结构来实现SC模块的功能；(2)译码过程的第二步是进行关键方程求解，将折叠技术引进基于mCS‑RiBM算法的KES模块，将相邻两个采用完全相同的更新方式的处理单元融合成一个折叠式处理单元，利用重定时技术将普通乘法器替换成流水线乘法器；(3)在完成关键方程求解之后，得到的错误位置多项式和错误估值多项式被送入CSEE模块，CSEE模块也设计成二度并行架构。

Description

一种低硬件成本、高吞吐率的硬判决译码器架构

技术领域

本发明属于信道编码中的差错控制编码领域，涉及一种低硬件成本、高吞吐率的硬判决译码器架构。

背景技术

信息社会的发展，对数据传输可靠性的要求日益提高，如何控制由传输信道引入的差错，保证数据的可靠传输成为系统设计必须关注的问题。自1948年香农的信道传输理论问世之后，差错控制编码成为了保证数据可靠传输的研究热点。作为一种重要的差错控制码，里德-所罗门(Reed-Solomon，RS)码以其优秀的纠错能力和相对简单的构造，被广泛应用于数据存储、数字视频广播、深空探测、无线通信、无线城域网等诸多领域。

RS码的译码算法主要有两大类：软判决译码算法和硬判决译码算法。硬判决虽然不能获得与软判决相当的译码增益，但是译码算法和VLSI实现都比较简单，因此成为目前的工业实现中的主流算法。硬判决RS译码器主要包括三个模块：校验子计算(SyndromeComputation，SC)、关键方程求解(KeyEquation Solver，KES)、钱搜索与错误估值(ChienSearch and Error Evaluation，CSEE)。作为最经典的KES算法，RiBM(Reformulatedinversionless Berlekamp-Massey)算法的硬件架构包含了3t+1个齐次的处理单元(ProcessingElement，PE)，排列规则，仅需要2t个时钟周期就可以完成错误位置多项式和错误估值多项式的计算，在本说明中，t代表RS码的纠错能力。在RiBM算法基础上衍生出的mCS-RiBM(modified Compensated Simplified-Reformulated inversionlessBerlekamp-Massey)算法，去掉了若干个冗余的处理单元，显著降低了硬件资源消耗。

值得注意的是，在现有的硬判决译码器架构中，KES模块的最小延迟是2t-1个时钟周期，相对于其他两个模块的延迟n个时钟周期来说很小，因而KES模块存在大量的空闲时间，造成了硬件资源的极度浪费。另外，由于每个PE中都包含1组乘法器-加法器组合(2个伽罗华域乘法器和1个伽罗华域加法器)，因此KES模块中是整个译码器中关键路径延迟最长、占用硬件资源最多的模块。综上所述，直接实现的译码器占用面积大、面积利用率低、吞吐率低。因此一种能够有效降低硬件成本、提高吞吐率的硬判决译码器架构设计方法需要得到进一步的研究。

发明内容

本发明的目的在于提供一种低硬件成本、高吞吐率的硬判决译码器架构，在保证译码性能的前提下，减少占据大量硬件资源的乘法器和加法器的数量，同时缩短译码器的关键路径延迟，以实现减小面积、提高吞吐率的目标。主要技术方案如下：

一种低硬件成本、高吞吐率的硬判决译码器架构，基于mCS-RiBM硬判决译码器架构实现，改进之处包括下列几个方面：

(1)采用并行结构来实现SC模块的功能，将校验子分为奇数部分和偶数部分分别进行计算，最后进行加和，计算2t个校验子，校验子计算电路的并行度因子为2，按照从高位到低位的顺序依次输入每路码元，在一个时钟周期内，校验子计算电路同时处理2个码元，在经过n/2个时钟周期后，计算出的校验子被送到KES模块来完成之后的运算；

(2)译码过程的第二步是进行关键方程求解，将折叠技术引进基于mCS-RiBM算法的KES模块，将相邻两个采用完全相同的更新方式的处理单元融合成一个折叠式处理单元，即，将前t个只采用RiBM更新方式的处理单元两两成折叠式PE1，将后t+1个既能采用RiBM更新方式、又能采用CS-RiBM更新方式的处理单元两两成折叠式PE4；此外，设计出与折叠式处理单元相匹配的折叠式补偿单元，利用三种更新模式循环产生、传递涉及到的多项式系数，在折叠式处理单元和折叠式补偿单元中，寄存器级数相较原来均有增加，利用重定时技术将普通乘法器替换成流水线乘法器；

(3)在完成关键方程求解之后，得到的错误位置多项式和错误估值多项式被送入CSEE模块，CSEE模块也设计成二度并行架构，即在一个时钟周期内，电路可以同时处理2个码元，CSEE模块需要n/2个时钟周期计算出所有错误位置和错误值。

本发明针对基于mCS-RiBM算法的译码器硬件成本高、吞吐率低的问题，将已成功应用于其他硬判决算法的折叠技术、重定时技术等和mCS-RiBM算法相结合，同时SC模块和CSEE模块采用流水线并行架构。最终基于新算法的架构中只存在少量深度流水线化的处理单元和一个与原mCS-RiBM算法相对应的补偿单元，从而减小了译码器面积，节约了硬件成本。且缩短了关键路径延迟，大大提高了译码器的吞吐率。

附图说明

图1为对传统并行SC单元作出修改后的二度并行SC模块。

图2为折叠式PE1和PE4。(1)折叠式PE1；(2)折叠式PE4。

图3为折叠式CS电路图。

图4为二度并行钱搜索及其基本单元。

图5为基于RS码的16沟道二度并行FEC架构。

具体实施方式

本发明主要是在mCS-RiBM硬判决译码器架构的基础上，通过引入折叠技术减少了乘法器和加法器的使用，极大降低了译码器的硬件成本，提高了硬件资源的使用率；同时通过重定时技术的引入进一步缩短了整体架构的关键路径延迟，最终获得了较高的吞吐率。同时，为适用于高速译码器，校验子计算模块、钱搜索与错误估值模块融合了并行技术和流水线技术。

下面结合附图和实例对本发明进行详述。为方便起见，本说明中一律以用途最广泛的RS(255，239)码(n＝255，t＝8)作为实例进行阐述。

(1)译码过程的第一步是计算2t个校验子S_i，0≤i≤2t-1，如果2t个校验子全部为0，则意味着没有错误发生，反之则代表在传输中出现了差错。校验子计算最基本的公式是：为了提高译码器的速度和吞吐率，本发明采用融合流水线技术的二度并行结构来实现SC模块的功能。将上述公式变化成以下形式：s_i＝(…(r_n-1α^i(q-1)+r_n-2α^i(q-2)+…+r_n-q+1αⁱ+r_n-q)α^iq+…+r_q)α^iq+r_q-1α^i(q-1)+r_q-2α^i(q-2)+…+r₁αⁱ+r₀，该电路的并行度因子为q，按照从高位到低位的顺序依次输入每路码元，在一个时钟周期内，校验子计算电路可以同时处理q个码元，这样在经过n/q个周期以后，寄存器中的结果就是所求的最终校验子值。但是这种传统的多度并行结构无疑会增长模块的关键路径延迟，为了解决这一问题，将校验子分为奇数部分和偶数部分分别进行计算，最后进行加和。即：s_i＝R(αⁱ)＝R_odd(αⁱ)+R_even(αⁱ)，图1展示了对传统并行SC单元作出修改后的二度并行模块。在二度并行结构中，需要128个时钟周期来完成校验子的计算。计算出的校验子被送到KES模块来完成之后的运算。

(2)折叠的KES架构。由于mCS-RiBM算法关于关键方程求解的部分包含两方面内容：处理单元和补偿单元，因此折叠的mCS-RiBM架构也包含这两方面。

折叠的处理单元：显然，将原架构折叠起来，占据较多资源的乘法器和加法器个数将骤减，且由于KES延迟增加，可以与较低并行度的SC和CSEE模块搭配使用。综上，整个架构的总面积将极大减小。值得注意的是，随着折叠因子的增加，吞吐率将会相应降低，这是因为折叠程度越高，整体时延随之增加。通过对采用不同折叠因子的情况进行分析可知，折叠因子为2时可以取得面积和吞吐率的最优折衷。在本设计中，将相邻的两个采用完全相同更新方式的处理单元融合在一起，即将前t个只采用RiBM更新方式的处理单元两两成折叠式PE1，将后t+1个或采用RiBM更新方式、或采用CS-RiBM更新方式的处理单元两两成折叠式PE4。折叠式的处理单元如图2所示。修改后的折叠式处理单元包含了2个流水线伽罗华域乘法器，1个伽罗华域加法器，2个2-1选择器，15个锁存器。折叠式PE4与折叠式PE1稍有不同的是多了3个选择器。折叠后的处理单元中上下两排锁存器δ_k ^l#和θ_k ^l#分别用于存储多项式Δ(r,z)和Θ(r,z)的系数，在本说明中，Δ(r,z)指代错误位置多项式Λ(r,z)和校验子多项式S(z)的乘积，Θ(r,z)指代中间多项式B(r,z)和S(z)的乘积。下标k与未折叠前的处理单元序号一致，上标l则表示沟道序号。在折叠架构中，由于每次迭代都是4沟道串行执行，因此在15×2×4-3＝117个时钟周期后开始输出第一个沟道的Θ(r,z)系数，在124个时钟周期后完成一次迭代。

折叠的补偿单元单元：在mCS-RiBM算法中，补偿单元用来存储溢出系数，输出补偿系数δ_c并在合适的时刻传递给处理单元。图3展示了折叠式补偿单元电路图，可以看到每一个时钟周期中可以选择将D₃，D₄或D_M中的数据通过选择器送入最左边的寄存器，即补偿单元架构中存在L₃，L₄和L_m三种反馈循环回路。由于该折叠架构中折叠因子为2，且是4沟道并行，所以每次迭代完成需要8个时钟周期。在提出的适用于折叠架构的补偿单元单元中，存在三种更新模式用于循环产生、传递涉及到的多项式系数。模式1应用于k(r)≥0&flag(r)≥0条件(k(r)和flag(r)均为mCS-RiBM控制单元里的中间变量)，目的是将当前系数向左移动一位并在本次迭代完成后接收一个新的溢出系数。具体实现步骤是先令当前系数经过一次L4反馈回路，这样在4个周期之后系数回到原位置，之后从第5个时钟周期开始，完成一次L3反馈回路，与此同时D₅和D_m的值保持不变，在第8个时钟周期到来时，将新的溢出系数θ_f送入最右边的寄存器。模式2应用于k(r)＜0条件，目的是将当前全部系数乘上γ(r)并向右移动一位。具体操作步骤是在前4个时钟周期中令当前系数经过Lm反馈回路，在第5个周期时全部数据开始完成L₄反馈回路。模式3则是应用于k(r)≥0&flag(r)＜0条件下，作用是在一次迭代完成后所有系数保持原有位置不动。即在该次迭代中令当前系数经历两次L₄反馈回路，同时保持D₅的值不变。

(3)在完成关键方程求解之后，得到的错误位置多项式和错误估值多项式被送入CSEE模块。其中，钱搜索模块计算错误位置多项式的根。福尼算法模块则是计算每个错误值。为了适用于高速RS译码器，CSEE模块也需要采用流水线技术。由于存在反馈回路，在流水线钱搜索和福尼算法结构中需要调整α的系数来调整时序。图4显示了二度并行流水线钱搜索模块的架构。福尼算法模块仅是在原基础上把C8单元去掉，其余部分基本类似。在输出第一个接受码字之前有7个周期的延迟，而完成所有错误值的计算需要128个时钟周期。

图5是本文提出的16沟道多度并行RS-FEC架构，包含了四个4沟道多二度并行RS译码器。图中的Q代表并行度。其中，校验子计算需要128个时钟周期，折叠式KES架构在第245个时钟周期开始输出第一个沟道的错误位置多项式和错误估值多项式的系数，并将输出结果送入CSEE模块，在252个时钟周期后完成所有错误位置多项式和错误估值多项式系数的输出。

Claims (1)

1.一种低硬件成本、高吞吐率的硬判决译码器架构，基于mCS-RiBM硬判决译码器架构实现，改进之处包括下列几个方面：

(1)采用并行结构来实现SC模块的功能，将校验子分为奇数部分和偶数部分分别进行计算，最后进行加和，计算2t个校验子，校验子计算电路的并行度因子为2，按照从高位到低位的顺序依次输入每路码元，在一个时钟周期内，校验子计算电路同时处理2个码元，在经过n/2个时钟周期后，计算出的校验子被送到KES模块来完成之后的运算；

(2)译码过程的第二步是进行关键方程求解，将折叠技术引进基于mCS-RiBM算法的KES模块，将相邻两个采用完全相同的更新方式的处理单元融合成一个折叠式处理单元，即，将前t个只采用RiBM更新方式的处理单元两两成折叠式PE1，将后t+1个既能采用RiBM更新方式、又能采用CS-RiBM更新方式的处理单元两两成折叠式PE4；此外，设计出与折叠式处理单元相匹配的折叠式补偿单元，利用三种更新模式循环产生、传递涉及到的多项式系数，在折叠式处理单元和折叠式补偿单元中，寄存器级数相较原来均有增加，利用重定时技术将普通乘法器替换成流水线乘法器；

(3)在完成关键方程求解之后，得到的错误位置多项式和错误估值多项式被送入CSEE模块，CSEE模块也设计成二度并行架构，即在一个时钟周期内，电路可以同时处理2个码元，CSEE模块需要n/2个时钟周期计算出所有错误位置和错误值。