一种面向 MCU 低成本测试的串行压缩传输协议的
实现及压缩算法研究
唐乃坚
瑞萨集成电路设计北京有限公司苏州分公司
email:naijian.tang.wg@su.rdb.renesas.com
摘 要:本文通过对串行传输协议的研究,提出了一种适用于微控制器(MCU)低成本测
试的数据串行压缩传输方法。该方法用较小的电路面积实现了片上接收端逻辑,并通过对发
射端压缩算法的优化,实现了超过 30%的传输时间缩减。
关键词:微控制器 低成本测试 串行压缩传输 哈夫曼编码 可变帧长 迭代搜索 SystemC
1.引言
随着半导体芯片特别是ASIC测试技术的发展,微控制器领域为追求更低的测试成本,
也从早期的基于CPU指令级的测试实现了向可测试设计(DFT)的转变。扫描设计(Scan
Test)、边界扫描设计(JTAG)、BIST(Built In Self Test)等技术使得在同等测试品质下,
测试难度及测试时间均得到大幅降低。但由于MCU架构复杂、宏单元多的特点、传统的可
测试设计难以做到全覆盖。以嵌入式闪存(FLASH)为例,不同于随机存取存储器(RAM)
嵌入式闪存的测试有着复杂的流程。传统上仍然需要编制CPU程序实现这一测试。非同期设
计的IP,模拟类宏单元、系统模块等的情况也是一样。由于难以实现一般意义上的可测试设
计,编制CPU程序进行测试是默认选项。
依赖于CPU程序的测试,首先必须面对的如何读取测试用CPU程序的问题。早期的MCU
通常采用两种方式:一)使用外部存储器扩张模式,即放置在芯片外部,CPU边取指令边执
行的方式。二)使用外部存储器扩张模式或类似模式,传输程序至片上RAM1,再转至RAM
上执行的方式。方式一的优点是程序结构简单无需额外的片上RAM,缺点是由于外部扩张
时总线周期长,对于执行周期较长的程序测试时间也会变长。方式二则利用了片上RAM总
线周期短的优势,一定程度上克服了方式一的缺点。随着MCU搭载片上锁相环 (PLL)越来
越成为主流,MCU核心包括RAM可以有远高于外部总线频率的片上工作时钟。这使得上述
两方式之间的测试时差进一步扩大,方式二逐渐成为首选。工艺的进步﹑核心频率的增加使
得在片上RAM上执行的测试时间不断得到缩减,但限于测试条件及测试机性能等因素,传
输CPU程序至RAM的过程并没有得到明显改善,并越来越成为一个瓶颈。图1是利用多个芯
片同时测试(Multi-Die Test)以降低单位测试时间的一种少管脚低成本测试方案。为了最大
化利用测试机的测试通道,测试用端子做了最大程度的削减,用于传输CPU程序代码的端子
1目前主流的 8 位 MCU 的片上 RAM 平均容量为 8K,16 位 MCU 为 16K,32 位 MCU 则更高[1]。
- 1 -
仅为一根。程序代码的串行传输使得本就成为测试瓶颈的传输时间问题更显特出。
t
u
o
d
/
n
i
d
…
c
c
V
s
s
V
t
s
r
k
l
c
t
u
o
d
/
n
i
d
…
s
s
V
t
s
r
k
l
c
A TE
t
u
o
d
/
n
i
d
s
s
V
t
s
r
k
l
c
…
DUT
DUT
…………
DUT
图 1 多个芯片同时测试(Wafer sort with Multi-Die Test)
本文基于对MCU程序代码特征的分析,结合哈夫曼编码(Huffman Coding)可变字长编
码的特点,设计了一种适合于片上实现的串行压缩传输协议。针对本协议帧长可变的特点,
本文进一步提出了一种最佳帧长分割的迭代算法。实验表明:在只增加有限电路面积的情况
下,与不利用压缩传输相比本方法实现了超过30%的传输时间缩减。
2.串行压缩传输协议
考虑到传输对象为 CPU 程序,数据的压缩方法须为无损压缩算法。同时数据接收端是
在片上以硬件方式实现,本协议的解压缩逻辑应尽可能简单。哈夫曼码的编码一侧较为复杂,
但译码侧仅作查表动作,正符合这一要求。下面我们就围绕基于哈夫曼编码订立传输协议展
开论述。
2.1 MCU 程序代码特征分析
哈夫曼编码是一种用于无损数据压缩的熵编码算法,使用变长编码表对源符号进行编
码,其编码表是通过一种评估来源符号出现机率的方法得到的,在数据中出现频度高的符号,
使用短的位序列,而那些很少出现的符号,则用较长的位序列。这使编码之后的数据的平均
长度、期望值降低,从而达到无损压缩数据的目的[2]。
表 1 MCU 程序代码符号出现频度统计
位宽单位:16 位
位宽单位:8 位
代码符号 出现次数 百分比 代码符号 出现次数 百分比
[0000]
[0303]
[FB92]
[0800]
19603
13.6%
7222
6835
6703
5.0%
4.7%
4.6%
[00]
[FB]
[03]
[08]
77175
20082
16861
13829
26.7%
6.9%
5.8%
4.8%
表 1 是对一组 MCU 例程中代
码符号出现频度前四位的统计结
果。不难发现,各代码符号的出现
频度是有着明显区别的。本例中出
现频度最多的是数据[00],[0303]则
- 2 -
为连续空操作指令。从信息论的角度看,MCU 程序代码中有着较大的信息冗余,存在有足
够压缩空间。
2.2 变长编码表的制定
哈夫曼编码的算法核心是变长编码表的确定。本节就基于表 1 的频度统计结果,使用哈
夫曼树(最优二叉树)构建算法[2]确定变长编码表。按照哈夫曼编码的通常规则,需要为源
符号集进行完整编码。如果为 16 位或 8 位代码符号全部作哈夫曼编码,则理论上最大可能
需要 216 或 28 组编码,这时的编码表趋于不经济且解码侧电路也会因过于庞大而失去意义。
观察各代码符号的频度统计结果,不难看出如果只对出现频度最高的四个代码作编码,而其
他代码符号使用前置转义码的方式进行原始连续传输(参考表 2),则可以很好的解决这个
问题。
在正式编码前,首先简单介绍一下编码收益的概念。
CELP
−−=
)1(
在公式(1)中定义 P为编码收益;L为源符号长度;E为目标编码长度;C为转义码
长度。通常的哈夫曼编码由于是全符号编码,编码时无需考虑编码收益问题。但如上文所述,
如果仅对一部分符号作编码时,则存在编码收益问题,即仅当 P大于零时才可以进行编码,
否则应作为原始符号传输。
在表 1 中,位宽为 8 时,前四位的代码符号的出现频度明显高于 16 位宽时的情况。但
实际上由于存在编码收益的问题,位宽为 8 时的代码符号并不总可以进行编码。以下列代码
符号序列为例,虽然[03]出现数次但均是单次出现,由于其后存在转义码的切换,单次编码
收益不大于 0(参考表 2),均不能编码,只能进行原始传输。
DD
:03:
CC
AA
:03:
BB
:03:
当位宽为 16 位时,由于 L相比 8 位时增加了一倍,编码收益扩大的同时,即使代码符
号单次出现,编码收益仍大于 0,因而编码总是可以进行。位宽为 4 位时可作全符号编码,
不存在转义码和编码收益问题,但由于丢失了程序代码间关联信息,压缩预期较低。32 位
时具有最大的编码收益,但由于 MCU 程序代码指令长一般不超过 16 位,16 位以上代码符
号缺乏关联性,压缩预期也偏低。鉴于 16 位宽时具有更大的压缩预期,在本协议中仅对位
宽为 16 的代码符号进行哈夫曼编码。
表 2 是基于哈夫曼树构建算法,根据样本程序代码符号的出现概率制定的一个变长编码
表。由于在非完整编码的情况下,转义码的出现频度最高,其码长最短。而出现频度最低的
为设计用来调节接收端时序的空操作码。
- 3 -
表 2 变长编码表
编码名称 哈夫曼码
略称
转义码
符号 0
符号 1
符号 2
符号 3
符号定义码
空操作码
0
10
1100
1101
1110
11110
111110
NTM
SY0
SY1
SY2
SY3
SYD
NOP
2.3 帧长对压缩结果的影响
除去符号 0~3 为数据码,转义码(NTM)﹑符号定
义码(SYD)﹑空操作码(NOP)2均为压缩协议的控制用码。
其中符号 SYD 仅在一帧数据的起始出现,它规定了符号
0~3 所代表的实际数据,其后将紧接传输 4 组 16 位原始
数据,SYD 的实际码长为 69(5+16*4)。NTM 规定其后
将紧接传输 1-8 组原始非压缩数据序列,NTM 的实际码
长为 1+3+16*n(n=1~8)3。
由于被压缩对象在原序列中空间分布的不均匀性,如果传输的始终只使用唯一 SYD,
显然是不经济的。在被压缩序列较长时,有必要分割序列并根据符号出现频度的顺位重新定
义符号(新 SYD 码)。我们定义:两个 SYD 的之间传输的数据单位的总量为一帧的帧长。
图 2 是在固定帧长为 512 时,对一组样本程序代码进行压缩后的结果。可以看出平均压缩率
已超过 30%。图 3 是设定不同帧长压缩相同样本时压缩比的变化情况。
7000
6000
5000
4000
3000
2000
1000
)
K
:
位
单
(
度
长
据
数
0
P001
P010
P019
P028
P037
P046
P055
P064
P073
35%
30%
25%
20%
15%
10%
5%
0%
P190
P199
P208
P217
P226
P235
P244
P253
比
缩
压
比
缩
压
35.0%
30.0%
25.0%
20.0%
15.0%
10.0%
5.0%
0.0%
32
128
512
2048
8192
32768
帧长
压缩前累计大小
压缩后累计大小゙
累计压缩比
P118
P136
P145
P100
P109
P127
P181
P091
P082
程序代码的文件数量
P154
P163
P172
图 2 帧长为 512 时的压缩结果
图 3 在不同帧长下的压缩结果
可以看出,对于不同的帧长,压缩的效率是不一样的。当帧长过低时,频繁的SYD所带
来的额外传输一定程度上抵消了编码收益。相反,在帧长过长时,由于忽略了各代码符号在
空间分布的不均匀性,压缩收益也呈现逐步降低趋势。在本例中,当帧长在512附近时压缩
比趋于最大化。
3.压缩算法的优化
不同于实时压缩传输对压缩算法时间复杂度的严格要求,本方法仅对已知数据进行事先
压缩,所以牺牲一定的时空复杂度进行进一步的算法优化是可行的。如前文所述,在设定帧
2考虑到由于片上 RAM 的数据存取位宽和时序的不同,在可能发生数据溢出时可进行空操作码插入。
3 NTM 码长的其中 3 位为传输长度指示,其中 000 指示为 1 位,001 为 2 位,依此类推 111 为 8 位。
- 4 -
长固定的情况下实施的压缩算法,其流程可以简单分为三步骤:1)帧长范围内符号出现频
度评估;2)对一帧数据实施压缩;3)重复步骤 1。其中,作为固定帧长下的一种算法优化,
我们可以对不同帧长进行扫描,精确选择压缩比最高的结果。
另一方面,观察本协议可以发现,在一组串行序列中,只需对 SYD 码的插入点进行调
整,就可以进行帧长可变的传输。固定帧长算法只是可变帧长算法的一个子集,显然,在帧
长可变的情况下,可以有更好的压缩预期。
在帧长可变情况下,问题变为如何将被压缩序列分割成不同帧长的各帧,即在序列的何
处适当插入 SYD 码以达到整体压缩比最高。通过扫描搜索,显然是不切实际的。对于一个
符号长度为 n的代码序列,固定帧长时理论上需要的扫描次数为 n,而可变帧长时则为指数
关系的 2n-2。为了减小算法复杂度,需设计一个算法来约束上述无选择的搜索过程。
下文将给出一个至上而下基于迭代的序列分割搜索算法。
对于下列长度为 n的被压缩序列 S,我们定义
i ≤ 。函数
(
)(sL 为对序列 s 实施固定帧长压缩后的长度,其中帧长固定设置为序列 s的长度,即压缩
数据中有且仅有一个 SYD 码。
为其子列{ Si﹑…Sj }
j
is
),(
)
j
{ S1﹑S2﹑S3﹑…Si﹑…Sj… Sn } (Si 代表第 i 个代码符号)
我们首先对序列 S进行整体压缩,得到
),1( i
n
sL
,1((
is +
(
得到子列{ S1﹑…Si }和{ Si+1﹑…Sn }即
后 子 列 进 行 独 立 压 缩 , 得 到 共 n-1 组 iL ,1 和
k
∈
is +
(
,记为 nL ,1 。然后对 S进行一次分割,
))
n
),1
。再分别对分割
L
++
k
,1
且其和为 n-1组中最小值时,我们即得到第一个分割点 k。接下来对
−
再分别重复迭代上述过程,直到不存在满足条件的分割点为止。
∈
iL ,1+ 。 当 满 足
n
~1{
n
),1
, 其 中
),1( i
s
和
~1{
L
,1
}1
−
L
,1
n
>
其中
}1
和
s
i
n
n
n
k
20.0%
15.0%
10.0%
5.0%
量
化
变
比
缩
压
0.0%
P0001
P0061
P0121
P0181
压缩比累计平均变化量
算法累计平均搜索深度
P0301
P0541
P0481
P0361
P0601
P0421
P0241
P1081
P1021
图 4 算法优化后的结果
P0781
P0961
P0841
P0901
P0661
P0721
P1141
P1201
2.5
2.0
1.5
1.0
度
深
索
搜
0.5
0.0
图4为利用上述搜索算法对一组样本代码
以512为单位长度实施压缩后的结果。相比帧
长固定时的压缩结果,在帧长可变的情况下,
压缩效率提高了平均超过5%。平均搜索深度
为2.1,算法复杂度大为降低。提高初始序列的
单位长度在更大范围内进行搜索,有助于得到
更好的压缩结果。当然随着搜索深度的增加,
计算时间也会大为延长。
4.接收端电路的实现
相对于压缩端算法的复杂性,接收端的解压缩电路则简单的多。可简单概括为:编码表
接收;编码接收及查表;内部写周期生成。图 5 为基于 SystemC 的接收端核心状态机的描述。
- 5 -
接收端在电路综合后的面积约为 2500 门左右,如果使用 RTL 描述,面积则可以进一步缩小。
在目前 MCU 的主流设计中,大面积宏单元几乎决定了芯片的整体布局。在此背景下,核心
...
while(1){
sc_lv <8> cmd;
if(error) { wait(); continue; }
cmd.range(0,0)=getbit(1).range(0,0);
if(cmd[0]==NTM){
proc_ntm(); continue;
}
cmd.range(1,1)=getbit(1).range(0,0);
if(cmd.range(1,0)==SY0){
decode_sym(0); continue;
}
cmd.range(3,2)=getbit(2).range(1,0);
if(cmd.range(3,0)==SY1){
decode_sym(1); continue;
}else
if(cmd.range(3,0)==SY2){
decode_sym(2); continue;
}else
if(cmd.range(3,0)==SY3){
decode_sym(3); continue;
}
cmd.range(6,5)=getbit(2).range(1,0);
if(cmd.range(4,0)==SDM){
proc_sdm(); continue;
}
err.write(1); error=1;
}
...
图 5 接收端核心状态机描述
数字逻辑的略微增加对设计全局影响微小。
5.总结
本文着眼微控制器低成本测试过程中数据串
行传输对测试时间的影响,通过对串行传输协议
的研究,提出了一种基于哈夫曼编码,以缩减数
据传输时间为目标的压缩传输协议。同时也提出
了一种基于本协议的优化压缩算法。在针对样本
测试程序代码的实验中,实现了超过 30%的传输
时间短缩。
本协议主要预想的应用领域为微控制器的低
成本测试,SoC/ASIC 等类似的应用场合也可供
参考。
参考文献
[1] EMITT Solutions, Microcontroller Market and Technology Analysis Report –2008,Page 10
[2] http://zh.wikipedia.org/wiki/哈夫曼编码
[3] Cadence Corporation, Cadence C-to-Silicon Compiler User Guide (2010)
A Compressed Serial Data Transmission Protocol with
Optimized Encoding Algorithm for Low-cost MCU Testing
Renesas Semiconductor Design(Beijing) Co.,Ltd.Suzhou Branch
NaiJian TANG
1. Abstract
This paper provides a MCU testing oriented compressed serial data transmission method with an
optimized encoding algorithm. With just a small increase in gate count, compression ratio of more than
30% is achieved, as contrasted with non-compressed transmission method.
……
Keywords: MCU, Low-cost testing, Compressed serial data transmission, Huffman coding,
Variable frame size, Nested search, SystemC
唐乃坚:瑞萨集成电路设计北京有限公司苏州分公司 副部长 naijian.tang.wg@su.rdb.renesas.com
主要从事微控制器设计﹑测试﹑评价
- 6 -