摘要：通过改进IFDR码，提出一种基于游程相等编码的改进FDR（ERFDR）方法.首先，该方法不仅能同时对原测试集的0游程和1游程进行编码，而且，当相邻游程相等时还可以用较短的码字来代替，从而进一步提高了压缩率.其次，还提出针对该压缩方法的测试集无关位填充算法，增强提出方法的压缩效果.实验结果表明，与FDR，EFDR，IFDR和ERLC相比较，本文提出的方法获得了更高的压缩率，降低了测试费用.
关键词：全扫描测试；测试数据压缩；无关位；FDR编码
中图分类号：TP302 文献标识码：A
文章编号：1674-2974（2016）02-0130-05
随着超大规模集成（VLSI）电路制造工艺的不断进步，越来越多的知识产权（IP）核被集成到一个系统芯片（SoC）上，与SoC相关的可测试性和测试方法问题被摆到了重要的位置.近十年来，如何降低测试成本，减少测试应用时间，降低测试功耗成为了研究的热点问题.
数据压缩技术能较好地解决这个问题，而编码压缩又是众多压缩方法中较好的一种.当前比较成熟的编码压缩方法有字典编码[1]、游程编码[2]、Huffman码[3]、Golomb码[4-5]、FDR码[6]、EFDR码[7-8]、IFDR码[9]等.这些编码压缩方法充分利用了测试集中的无关位（X）.FDR是一种变长0游程编码，测试集中的X都被填充为0以增加0游程的长度，当测试集中1的个数较少时有较好的压缩效果.EFDR码和IFDR码可以同时对0，1游程进行编码，当测试集中1的个数较多时，也能取得较好的压缩效果.然而以上方法均没考虑等游程的情况.本文在IFDR上进行改进，提出一种基于游程相等的改进FDR（ERFDR），一方面能同时对0，1游程编码，另一方面当相邻游程相等时用较短的码字来代替，以进一步提高压缩率，减少测试应用时间.
1IFDR编码
IFDR编码是一种改进型FDR编码（Improved FDR）.该方法将原测试集看作连续的0游程和1游程，0游程和1游程共用同一套码字，并规定0游程后接1游程，1游程后接0游程.若不是，即0游程后是0游程或者1游程后是1游程，编码时在两个相同游程中间添加一个“00”作为标识符.该方法默认从1游程开始编码，若测试集第一位为0，则在编码的过程中先必须加个“00”作为标识.表1给出了IFDR的编码表，可以看出游程长度l和其所在组k的关系为：k=「log2（l+3）-1.前缀中1的个数和其所在组的关系为：k组的前缀为1k-10，表示有k-1个1再接一个0.对于任一组，前缀和尾部的长度是相等的，组前缀是用来区分该码字所在的组（通过前缀的长度），尾部用来确定该码字所在组中的位置.和FDR编码表不同的是IFDR编码表的A1组只包含一个游程长度，且没有长度为0的游程.用IFDR对0游程和1游程编码时共用同一套编码.
为了进一步提高测试压缩率，本文在IFDR基础上进行改进，提出一种基于游程相等的改进FDR（ERFDR），编码表见表2.与IFDR码类似，ERFDR码也能同时对0游程和1游程编码，0游程和1游程共用同一套码字，且默认从1游程开始编码.考虑到相邻游程类型相同的可能性较高，与IFDR码不同，本文用一位“0”作为标识，则可多压缩一位.代价是游程长度为2n+1-3的编码增长2位，其中n为自然数.当这种游程个数小于相邻游程类型相同的游程个数的一半时，该编码方式有效.可以预见，当测试集中确定位比例越低，该编码方式越有效.进一步考虑到，每个游程的编码都是从1开始，且不会连续出现两个“0”标识符.我们可以用“00”标识相邻两个游程相等的情况，从而取得进一步的压缩效果.在不发生混淆的前提下，本文用“0000” 标识相邻游程类型相同且相等的情况.
总之，提出的方法有如下5个编码原则：1）若测试集第一个游程为0游程，须加“0”作为标识；2）当相邻游程类型相同但游程不相等时，在两游程的编码之间加“0”标识；3）当相邻游程长度相等且类型不同时，后一个游程用“00”编码；4）当相邻游程长度相等且类型相同时，后一个游程用“0000”编码；5）为了避免解码时发生歧义，当出现连续3个游程长度相等时，则对第3个游程直接用编码表编码，而不使用原则3）和4）编码.
3无关位的填充方法
大规模测试数据中无关位占95%以上，测试数据压缩效果的好坏在一定程度上取决于对X的填充.本方法对0，1同时编码，并充分利用游程长度和类型信息进一步提高测试压缩率，在对无关位填充的过程中应遵循下列两个基本原则：
1）尽量使用长游程编码；
2）尽可能地让相邻游程相等.
例如：00XX00X00XXXXXXX11XX11XX10这样一组测试数据，若在填充过程中仅仅遵循原则1），则填充后为00000000000000001111111110，用 表2编码，结果为11100011 110011，共14位.若遵循上述两原则：0000000000001 1111111111110，用本文的方法编码为110111 00共8位，减少了6位，压缩效果明显改善.本文所用的填充算法（无关位填充算法）如下.
6）FSM控制dec1为高电平，控制k+1位计数器的减1操作，直到k+1位计数器的值为3（即0…011）时，out输出为高电平，T触发器的输出翻转.
7）当解码完一个游程后，一直到bit_in为1之前，若bit_in共出现1个“0”，则令out为低电平，且v也为低电平0，表示输出无效，同时也为下一个游程编码做准备；出现两个0时，即“00”，则置load为高电平，通过dload把寄存器的值载入k+1位寄存器中，转到6）；当出现“000”时（共3个时钟周期），则在前2个时钟周期置load为高电平，通过dload把寄存器的值载入k+1位寄存器中，转到6），第3个时钟周期令out为低电平，v且也为低电平0，表示输出无效；出现“0000”时，令out为低电平，然后置load为高电平，通过dload把寄存器的值载入k+1位寄存器中，转到6）；当出现“00000”时，重复上述出现4个0的步骤，之后在最后一个时钟周期令out为低电平，且v也为低电平. 5实验结果
本文针对ISCAS89标准电路中较大的6个电路，采用mintest测试集在Visual C++平台上实验，得出的结果分别与Golomb码、FDR码、EFDR码、IFDR码以及ERLC[10]码进行比较，实验结果见表3.可以看到平均压缩率均优于其他方法，平均压缩率比Golomb编码方法提高了将近14%，比FDR和IFDR分别提高了6%和1.84%，比EFDR和ERLC也提高了0.5%.
6结论
本文在IFDR编码方法的基础之上进行改进，不仅能同时对0，1串编码，而且当出现相邻游程相等时，后一个游程用较短的码字来代替，进一步提高压缩率.实验结果充分验证了本文提出方法的有效性.该法简单可行，解码电路简单，硬件开销不高.
参考文献
[1]TOUBA N. Survey of test vector compression technique [J]. IEEE Design &Test of Computer， 2006，23（4）：294-303.
[2]JAS A， TOUBA N. Test vector decompression via cyclical scan chains and its application to testing core-based designs[C]//Proceedings of International Test Conference. New York： IEEE， 1998： 458-464.
[3]JAS A， GOSH-DASTIDAR J， NG M， et al. An efficient test vector compression scheme using sel
ective Huffman coding[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2003， 22（6）：797-806.
[4]CHANDRA A， CHAKRABARTY K. Test data compression and decompression based on internal scan chains and Golomb coding[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2002，21（6）：715-722.
[5]CHANDRA A， CHAKRABARTY K. System-on-a-chip test-data compression and decompression architectures based on Golomb codes[J]. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems， 2001， 20 （3）：355-368.
[6]CHANDRA A， CHAKRABARTY K. Frequency-directed run-length（FDR） codes with application to system-on-a-chip test data compression[C]//19th IEEE Proceedings on VLSI Test Symposium. New York： IEEE， 2001： 42-47.
[7]EL-MALEH A， AL-ABAJI R. Extended frequency-directed run-length codes with improved application to system-on-a-chip test data compression[C]//Proceedings of 9th International Conference of Electronics， Circuits and Systems. New York： IEEE， 2002： 449-452.
[8]EL-MALEH A. Test data compression for system-on-a-chip using extended frequency directed ran-length code[J]. IET Computers & Digital Techniques， 2008，2（3）：155-163.
[9]欧阳一鸣，郭文鹏，梁华国. 改进型FDR 码对SoC 测试数据的压缩及解压[J].计算机应用研究， 2008，25（1） ：174-177.
OUYANG Yi-ming， GUO Wen-peng， LIANG Hua-guo. Soc test data compression and decompression with improved FDR code[J]. Application Research of Computers， 2008， 25（1）：174-177.（In Chinese）
[10]ZHAN W F， EL-MALEH A. A new scheme of test data compression based on equal-run-length coding （ERLC）[J]. Integration the VLSI Journal ， 2012， 45（1）： 91-98.
