ReedSolomon编解码数字设计回顾

[toc]

最近完成了一个Reed-Solomon编解码模块的设计和验证. 趁此机会, 回顾总结其设计过程.

功能分析

Reed-Solomon编解码模块的功能: 对输入信息块添加冗余之后再传输, 经过信道之后, 如果遇到少量的错误,可以通过数学算法计算进行错误纠正.

输入信息块是固定长度的字节流, 每一个字节称为一个symbol, 每个symbol的值代表的是GF(256)中的一个数, symbol之间的运算就是Galois Field中的运算.

编码算法比较简单, 通过输入的symbol, 计算出4个冗余的symbol.将此4个冗余的symbol和输入symbol一起合并传输. 可以这样理解, 这些冗余symbol就是对输入所有symbol的一个数值校验. 类似做奇偶校验一样.

解码算法相对复杂, 对于简单的ReedSolomon, 可以分两步完成:

• 计算错误症状Syndrome. 通过syndrome的值可以得到一个方程组.
• 迭代解方程组. 通过遍历所有的可能数值来解方程组.

设计步骤分析

纠错算法模块是以数学计算为核心的数字模块, 他的设计验证方式和以控制时序为核心的数字模块设计方式不同. 我的设计步骤如下:

1. 学习ReedSolomin算法, 查资料, 理解编解码的工作原理和算法步骤. 因为之前有一定的抽象代数基础, 所以费时不太多, 大概费时2~3天.
2. 用数学编程软件Gap建模RS-ECC编解码过程, Gap自带Galois Field运算支持, 因此实现基于域运算的算法非常简洁. 代码长度150行左右即可. 编程, 调试, 加debug, 大概费时1~2天.步骤1和2有部分时间重合, 总共时间不超过3天.
3. 用python语言重新实现Gap的数学模型, 需要对Galois Field的运算做了细节的实现. 利用了Github上的开源代码, 在开源代码的基础上做了扩展和修缮. 开源提供了GF(256)的基础运算, 自己补充了运算之后, 又写了多项式运算扩展类, 扩展类的代码不到80行. 在多项式扩展类的基础上, 对RS-ECC做编解码建模, 代码长度不到150行.可以随机产生激励来做算法的验证, 并作为将来RTL的行为级参考. 编码, 调试, corner测试, 费时1周.
4. 实现编码算法, 用python算法模型产生激励和验证pattern. 由于编码算法等价于一个GF域的多项式除法, 硬件实现比较简单, 1-2天即可完成RTL编码加基础验证.
5. 解码算法相对较复杂. 分析解码算法实现的硬件架构, 主要包括如下:
   1. 计算动作的分步细化, 分析所需要的硬件资源.1~2天
   2. 关键信号分析, 计算的过程中需要哪些关键数据, 减少信息冗余.1-2天
   3. 状态机设计, 根据硬件资源和关键信号分析结果, 设计紧凑的状态机, 来回迭代.1-2天
   4. 在状态机基础上, 修改python的行为级实现, 增加状态机硬件级别的算法建模, 将解码的过程通过状态机的计算步骤来实现. 目的是给出RTL的实现参考, 同时也是RTL实现的行为级model. 3~4天
   5. 解码分析的过程, 除了python建模之外, 还有框架图, timing分析图.
6. 解码算法的RTL编码以及验证
   1. 参考python的状态机实现model, 分析和优化register资源, 尽量节省register的使用.
   2. 开始RTL编码, 1~2天时间.
   3. 验证RTL: 由于有了python的状态机级别的建模. 加上很详细的timing和register分配资源图, 可以先对着python状态机和timing/register资源图, 对RTL做几轮人工检查. 在人工检查阶段, 发现了不少错误. 耗时0.5~1天. 代码对照设计文档检查费时较少, 只需要细心认真即可. 这些bug通过仿真来检查, 需要耗费更多的时间. 所以设计思路清晰, 推敲严谨, 看似耗费了不少时间, 但是实际上是为后续的验证节省了很多时间. 并且也会增加自己设计能力的自信心.
   4. 写testcase对RTL验证, 仿真有错误, debug发现有一个信号定义的宽度错误, 修正之后, basic case仿真竟然OK了.
   5. 随机regression测试, 找到1个Corner Case,没有分析很透彻. 因为硬件实现上和python描述的算法还是有差异, 有些差异只有在corner case才能体现出来. 需要充分的regression以及directly corner case测试才能发现. 大概耗时3~4天.
   6. 总结RTL的解码算法实现和验证, 分成2个子模块完成, 第一个是syndrome计算, 实现和验证相对简单, 在python模型准备好的基础上, 1天时间足够完成RTL加上unit test. 第二个模块是解方程组, 需要迭代, 涉及到的变量和计算过程相对复杂不少, 时序也复杂不少. 因此时间要多一些. 大概需要3~5天. 最后整理一个top模块, 将这两个子模块整合在一起, 然后写随机验证pattern, 这属于水到渠成的事情. 不过top模块还有一个难度, 就是如何定义top层的接口时序, 需要仔细推敲.
   7. 解码top层的接口时序, 需要和上下游进行讨论, 他们需要的速度, 带宽, 数据的传输方式, 是否需要hold机制, 是否需要内部缓冲来加快输入数据的连贯性. 都是考量的因素.
   8. 解码top层设计主要是时序考量和throughput分析, 代码量很少, 但是控制时序比较精巧, debug要借助于波形. 总耗时1~2天. 对于时序控制为主的电路, 关键在于定义重要信号, 然后画波形图, 对于每一个重要信号, 我都在笔记本上写出它们的控制条件. 然后对照典型波形进行推演, 迭代.待所有的重要信号的控制规则都写下来之后, 就可以开始设计代码了.

Bug分析

在Gap/Python建模阶段, 在RTL阶段, 都会出现Bug, 作为一个有十几年经验的人, 写代码依然会有一系列bug, 回顾这个设计, 主要的bug如下:

1. python建模的时候, 对于多项式class的设计, 定义了degree, 经过运算之后如果最高次系数结果为0, 会消去最高次项. 如此继续下去, 直到最高次项不为0.
   1. 考虑corner case, 即次数为1的时候, 是常数多项式. 若常数为0, 则不要消去这个唯一的0.
   2. 做多项式除法取模的时候, 除一个5次多项式, 结果最高是4次多项式. 有可能为3次多项式,甚至更低次多项式. 在ReedSolomon的redundent计算的时候, 没有考虑余数多项式低于4次的情形, 导致所有的编码数据shift. 从而仿真错误. 只有特定的pattern才能发现这个问题. 我是通过大量随机测试才发现这个问题的.
2. 通过详细的设计文档, 加上RTL写完之后, 对照设计文档从头到尾检查一次, 然后对照python model从头到尾检查一次. 这两次检查之后, 仿真结果有一半正确. 剩下的错误是由于RTL中对两个变量没有定义, 结果缺省为1bit, 导致仿真错误. 如果用lint检查, 可以很快发现问题. 另外, systemverilog仿真器对变量的定义要求比较松, 如果没有定义, 出现在assign中没有报错.
3. RTL还有一个bug, 比较难发现. 不是RTL实现本身, 是算法映射到物理的时候, 某个值会超过边界. 当时分析, 超过边界用一个错误的返回值代替, 就可以解除. 结果, 在regression大批量验证的时候, 某个数据组合正好碰巧可以满足这个错误返回值, 让解码出现错误结果. 报告出一个错误的方程解. 第一次debug的时候, 将超过边界的返回值换成另外一个错误值, 这个pattern就可以pass, 当时经过数学推理, 发现其他的某些pattern仍然可以满足这个新的错误值, 从而出现错误解. 最后改用比较彻底的方式, 如果出现越界, 直接让输出为error. 这样避免了错误的解出现.
4. 解码整合电路的时候, 涉及到很多时序, 因此要借助waveform来debug. 发现很重要的错误是:
   1. 优先级控制, 连两个控制信号同时到达的时候, 优先级设计错误.
   2. 模块间数据传递, 时序错开.
   3. 思考过这个问题, 对于这种控制密集, 时序设计比较多的电路模块, 能否不用波形就能debug? 就像计算密集型电路一样, 仅仅通过print, assertion就可以debug. 目前看起来有点困难. 可能后续要加强assertion, 从而减少对波形debug的依赖.