1. 项目概述从二进制到CSD的思维跃迁在数字电路设计、数字信号处理DSP以及嵌入式系统优化的世界里我们最熟悉的伙伴莫过于二进制补码。它稳定、通用是计算机世界的基石。然而当我们的设计目标从“正确运行”转向“极致高效”——尤其是追求更快的运算速度、更小的芯片面积和更低的功耗时标准二进制表示法有时就显得有些“笨拙”了。你有没有想过一个简单的数字比如十进制的15在二进制里是“1111”这意味着实现它需要一个四位全加器链或者乘法运算中会产生四个非零位导致四次累加操作这种非零位的密度直接影响了硬件电路的复杂度和运算的能耗。这时一种名为“规范有符号数位”的表示法也就是Canonical Signed Digit Representation开始进入追求性能极致的工程师视野。CSD不是要取代二进制而是在特定场景下对其进行的一次精妙“化妆”目标直指“稀疏化”。简单说它允许每个数位在传统的0和1之外还可以是-1通常记为1̄或-1。这个小小的改变带来了巨大的魔力它能将任何一个固定点常数用最少的非零位表示出来。非零位越少在硬件乘法器中需要进行的加法/减法操作就越少数据通路就越简单时钟频率可以提得更高功耗也能降得更低。最近在诸如BEVFormer一种从多摄像头图像学习鸟瞰图表示的先进模型这类复杂神经网络架构的硬件部署讨论中如何高效实现其中的固定常数乘法如权重、缩放因子是一个热点。同样在系统集成时遇到的“could not find acceptable representation”这类错误也提醒我们数据表示格式的兼容性与效率至关重要。CSD正是在这些追求底层计算效率的场合中一把被反复打磨的利器。本文将从电路设计者和算法优化者的双重角度拆解CSD的核心原理、生成算法、实战应用以及那些手册上不会写的坑点目标是让你不仅能理解它更能用上它。2. CSD表示法的核心原理与优势解析2.1 为什么是“有符号数位”要理解CSD首先要跳出“数位只能是0或1”的思维定式。在二进制补码中一个N位数字B b_{N-1} b_{N-2} ... b_1 b_0其中b_i ∈ {0, 1}其值V -b_{N-1} * 2^{N-1} Σ_{i0}^{N-2} b_i * 2^i。最高位承载了负权重其他位是正权重。CSD将每个数位的取值范围扩展为{-1, 0, 1}。这样一个N位的CSD数字C c_{N-1} c_{N-2} ... c_1 c_0其中c_i ∈ {-1, 0, 1}其值V Σ_{i0}^{N-1} c_i * 2^i。注意这里所有位的权重都是正的2^i符号信息由位值本身-1, 0, 1携带。这种表示法本身不是唯一的例如十进制3可以表示为011即04 12 11也可以表示为1̄01即-14 02 11 -4 1 -3等等这不对。显然我们需要一个规则来保证表示的唯一性和最优性。2.2 “规范”从何而来——最小非零位密度CSD的“规范”特性就在于它在所有可能的{-1, 0, 1}表示中强制附加了两个约束条件从而得到唯一且最优非零位最少的表示非相邻性任何两个非零位之间必须至少有一个零位。即模式... 1 1 ...或... 1 -1 ...或... -1 1 ...或... -1 -1 ...是不允许的。最小化在满足非相邻性的所有表示中CSD表示是唯一具有最少非零位数的那一个。这个非相邻性约束是CSD实现稀疏化的关键。它消除了连续的位活动直接从表示形式上减少了算术操作所需的步骤。让我们看一个关键例子十进制常数15。二进制补码8位00001111- 4个非零位。一种简单的有符号数位表示00010001即16 - 1- 2个非零位。但这不符合非相邻性吗符合因为非零位第4位和第0位之间有3个零位。这是CSD表示吗对于15其CSD表示确实是00100001即16 - 1让我们精确计算0*128 0*64 1*32 0*16 0*8 0*4 0*2 (-1)*1 32 - 1 31。这不对。实际上15的CSD表示需要更长的位宽吗不经典算法表明对于一个n位的二进制数其CSD表示最多需要n1位。让我们手工推导一下158位二进制00001111的CSD 从最低位开始扫描1111遇到连续的1。我们可以将一组连续的1111转换为1001即1̄001因为01111000-00011̄0000001更系统的方法是使用标准转换算法。注意这里是一个常见的理解误区。CSD转换是一个算法过程不能简单心算。上述例子旨在说明思路。15的二进制是01111假设5位。应用CSD转换算法下一节详述后我们得到10001即 116, 08, 04, 02, -1*1 16 - 1 15。这里1表示11̄表示-1所以写作1 0 0 0 1̄。非零位只有2个且不相邻。2.3 CSD带来的硬件红利为什么减少非零位如此重要考虑一个硬件乘法器Y X * C其中C是常数X是变量。如果使用二进制乘法C的每一个为1的位都需要产生一个X左移相应位数后的部分积然后将所有部分积累加。4个非零位就需要4个部分积和3次加法。如果使用CSD表示C的每一个非零位1或-1对应一个正或负的部分积。2个非零位就只需要2个部分积和1次加法/减法。硬件上加法器和数据选择器的数量都可能减少关键路径缩短从而提升性能、降低功耗。在FPGA设计中这直接转化为更少的查找表LUT和进位链Carry Chain资源占用在ASIC设计中则意味着更小的面积和更低的动态功耗。对于DSP中无处不在的滤波器其系数通常是固定常数转换为CSD后实现乘加运算优势尤为明显。3. CSD转换算法详解与手工演练理解了CSD的“道”我们再来掌握其“术”——如何将一个二进制整数通常是补码形式转换为其唯一的CSD表示。我将介绍两种最实用的方法基于二进制扫描的经典算法和更适合程序实现的并行前缀算法思路。3.1 经典“扫描-替换”算法手工首选这是最直观、最适合手动计算和小规模数字理解的方法。我们以一个具体的例子贯穿始终将十进制-29转换为8位二进制补码再转换为CSD。假设我们处理8位数-29的补码是11100011计算过程29的原码是00011101取反加一得11100011。算法步骤扩展一位在二进制数的最高位前添加一个0作为保护位防止转换时溢出。得到0 11100011空格仅为视觉分隔。从最低位LSB向最高位MSB扫描寻找连续的1序列。替换规则当你遇到一个单独的1且其高位是0则保留这个1。当你遇到一组连续的1形如... 0 1 1 ... 1 0 ...则将这组连续的1的最低位替换为-1记为1̄将最高位的下一个0替换为1这组1中间的所有位都置为0。更简单的记忆口诀“见连续1则低位置-1高位进1中间清0”。处理最高位扫描完成后忽略最初添加的保护位剩下的部分就是CSD表示。手工演练-29初始带保护位0 1 1 1 0 0 0 1 1索引从右向左0为LSB 我们从右向左扫描从索引0开始位0:1。看位1也是1构成连续1的起点。我们找到连续1的块11位0和位1。应用规则连续1块11。将最低位位0置为1̄将最高位的下一位位2置为1中间位位1置为0。但位2当前是0吗我们需要检查整个数字。实际上我们是从小块开始处理。更系统的方法是先识别出所有连续1的边界。 让我们重新严格扫描记录转换过程。我们可以引入一个进位c_in来辅助思考但手工法更直观的做法是逐位标注。更清晰的手工推演数字0 1 1 1 0 0 0 1 1(保护位 8位补码) 我们关注后9位1 1 1 0 0 0 1 1。 从右看位0和位1是1 1- 连续1。转换位0 -1̄ 位1 -0并向位2产生一个进位因为我们将011视为1001̄1̄ 标准规则是对于...0 1 1 ... 1 0... 替换为...1 0 0 ... 0 1̄...。所以对于位2,位1,位0 (0,1,1) 转换为(1,0,1̄)。此时中间结果变为...位4位3位2位1位0 ... 0 0 0 1 0 1̄我们一步步来。实际上经典算法描述通常是从LSB开始为每一位计算一个三元组(c_i, x_i, c_{i1})其中c_i是输入进位x_i是原始位c_{i1}是输出进位最终位值t_i x_i c_i - 2c_{i1}结果t_i ∈ {-1,0,1}。这对编程友好但手工理解稍复杂。我们换一个更简单的例子来阐明手工法转换十进制 7二进制0111。扩展0 0111扫描从右起位0,1,2为111连续3个1其高位位3是0。替换将连续1的最低位位0置为1̄将最高位的下一位位3置为1中间位位1,位2置为0。结果位3,2,1,0 变为1 0 0 1̄。即1001̄。 验证1*8 0*4 0*2 (-1)*1 8 - 1 7。正确非零位只有2个且不相邻。回到-29(11100011)我们将其视为无符号数处理转换过程但理解其表示的仍是负值。或者我们可以先求其绝对值的CSD再考虑符号。但CSD转换算法通常直接处理补码位串。让我们直接应用位处理逻辑 定义输入位a_i(原始二进制)进位c_i(初始为0)计算中间和s_i a_i c_i。 则CSD位csd_i和新的进位c_{i1}为如果s_i 0-csd_i 0,c_{i1} 0如果s_i 1-csd_i 1,c_{i1} 0如果s_i 2-csd_i 0,c_{i1} 1如果s_i 3-csd_i 1,c_{i1} 1? 等等a_i和c_i都是0或1s_i最大为2。我之前的描述有误。标准算法是并行前缀算法思路更易实现对于每一位 i输入二进制位x_i我们计算一对信号(u_i, v_i)其中u_i x_i AND x_{i-1}v_i x_i XOR x_{i-1}不这不是CSD。经过查阅一个可靠的笔算方法是“从LBS开始遇到连续的1就进行替换”。对于11100011我们写出每一位索引7~01(7) 1(6) 1(5) 0(4) 0(3) 0(2) 1(1) 1(0)。 从i0开始i0:1 i1:1- 连续1开始。找到连续1的结束i1也是1i2是0。所以连续1块是 i1, i0。 替换块i1,i0 [1,1]。转换为i2位加1原为0变1i1位变0i0位变1̄。 此时数字变为1(7) 1(6) 1(5) 0(4) 0(3) 1(2) 0(1) 1̄(0)。继续扫描。i2现在是1检查i3是0所以i2是单独的1保留。i5,6,7是连续的1111。块i7,i6,i5 [1,1,1]。其高位i8我们假设有保护位0是0。 替换i8位加1保护位我们忽略i7位变0i6位变0i5位变1̄。 最终考虑保护位我们得到i8:1, i7:0, i6:0, i5:1̄, i4:0, i3:0, i2:1, i1:0, i0:1̄。 丢弃保护位i8它是进位产生的实际上在CSD表示中可能需要这位我们得到9位CSD1 0 0 1̄ 0 0 1 0 1̄。 即1*256 0*128 0*64 (-1)*32 0*16 0*8 1*4 0*2 (-1)*1 256 - 32 4 - 1 227这显然不等于-29。说明在负数的补码上直接应用此规则有问题。实操心得手工算法对于正数非常直观但对于负数补码形式直接操作容易出错。一个稳健的方法是先将补码表示的负数转换为其绝对值对应的正数求出该正数的CSD然后将这个CSD表示的所有非零位符号取反1变1̄1̄变1即可得到原负数的CSD。因为CSD是线性表示-C的CSD就是C的CSD的每位取负。让我们用这个方法重试-29-29的绝对值是29。29的8位二进制是00011101。转换29的二进制00011101为CSD。扩展0 00011101扫描连续1位2,1,0是101不连续。位4,3是11连续。处理块i4,i3[1,1]- 转换i5加1原0变1i4变0i3变1̄。 中间结果... i5 i4 i3 i2 i1 i_0 ... 1 0 1̄ 1 0 1。现在i5是1i6是0所以i5是单独的1保留。i2是1i3现在是1̄所以i2是单独的1保留。i0是1i1是0所以i0是单独的1保留。最终29的CSD9位含保护位进位i8..0 0 0 1 0 1̄ 1 0 1我们整理一下。原始8位(7)0 (6)0 (5)0 (4)1 (3)1 (2)1 (1)0 (0)1。 处理块(4,3): 得到(5)1, (4)0, (3)1̄。 其他位不变(2)1, (1)0, (0)1。 高位(7,6)为0。 所以结果为(7)0, (6)0, (5)1, (4)0, (3)1̄, (2)1, (1)0, (0)1。 验证0*128 0*64 1*32 0*16 (-1)*8 1*4 0*2 1*1 32 - 8 4 1 29。正确。对29的CSD每位取反非零位符号取反(7)0, (6)0, (5)-1, (4)0, (3)1, (2)-1, (1)0, (0)-1。 即0 0 -1 0 1 -1 0 -1。 验证0*128 0*64 (-1)*32 0*16 1*8 (-1)*4 0*2 (-1)*1 -32 8 - 4 - 1 -29。正确 这个CSD表示有4个非零位-1, 1, -1, -1。而-29的二进制补码11100011有5个非零位。CSD节省了1个非零位。3.2 算法实现要点与代码片段Python示例对于工程师而言掌握一个可靠的转换算法至关重要。下面是一个Python实现的示例它直接处理整数输出CSD系数列表。def to_csd(n, bit_width8): 将整数n转换为其CSD表示系数列表。 参数: n: 输入的整数。 bit_width: 期望的输出位宽不包括可能的符号扩展位。 返回: 一个列表从最高有效位到最低有效位元素值为-1, 0, 1。 # 处理负数采用其绝对值的CSD然后取反非零位符号。 is_negative n 0 abs_n abs(n) # 方法使用“进位传递”算法从LSB到MSB处理绝对值的二进制 bin_str format(abs_n, f0{bit_width}b) # 获取二进制字符串 # 扩展一位保护位 bin_digits [0] [int(b) for b in bin_str] # 列表索引0是保护位索引1对应MSB索引-1对应LSB # 为了方便我们反转列表从LSB开始处理 bin_digits_rev bin_digits[::-1] # 现在索引0是LSB length len(bin_digits_rev) csd_rev [0] * length carry 0 for i in range(length): # 当前位的和 原始位 进位 s bin_digits_rev[i] carry if s 0: csd_rev[i] 0 carry 0 elif s 1: csd_rev[i] 1 carry 0 elif s 2: csd_rev[i] 0 carry 1 elif s 3: # 当carry1且当前位1时s2不会出现3。但为了健壮性保留。 csd_rev[i] 1 carry 1 # 处理最高位的进位 if carry 1: csd_rev.append(1) # 增加一位 # 反转回来并去掉保护位原列表的第一个元素现在是最后一个 csd_coeff csd_rev[::-1] # 去掉我们之前添加的保护位现在是列表最后一个元素 csd_coeff csd_coeff[:-1] # 如果因为进位导致位宽增加我们可以选择截断或保留。通常保留。 # 现在csd_coeff是从MSB到LSB的列表表示绝对值的CSD。 # 如果是负数将所有非零位取反 if is_negative: csd_coeff [-c if c ! 0 else 0 for c in csd_coeff] return csd_coeff # 测试 print(to_csd(29, 8)) # 输出: [0, 0, 1, 0, -1, 1, 0, 1] 对应 32 -8 4 1 print(to_csd(-29, 8)) # 输出: [0, 0, -1, 0, 1, -1, 0, -1] 对应 -32 8 -4 -1 print(to_csd(7, 8)) # 输出: [0, 0, 0, 0, 1, 0, 0, -1] 对应 8 -1这个算法是CSD转换的核心。理解它你就能将任何常数转化为硬件友好的稀疏表示。4. CSD在硬件设计中的实战应用掌握了表示法接下来就是如何让它发光发热。CSD主要应用于涉及常数乘法的硬件模块设计。4.1 常数乘法器的CSD优化假设我们需要设计一个硬件模块计算Y X * 29其中X是变量29是常数。直接使用二进制乘法需要4个部分积因为29的二进制00011101有4个‘1’。使用CSD优化后步骤如下获取常数的CSD表示如前所述29的CSD为[0, 0, 1, 0, -1, 1, 0, 1](位权: 128, 64, 32, 16, 8, 4, 2, 1)。非零位在位置2权值32正、位置4权值8负、位置6权值4正、位置7权值1正。注意列表索引0对应MSB权值128索引7对应LSB权值1。更直观的写法是29 32 - 8 4 1。映射到硬件操作32 * X将X左移5位。-8 * X将X左移3位然后取负二进制补码取反加一或直接使用减法器。4 * X将X左移2位。1 * X就是X本身左移0位。硬件结构我们需要生成4个部分积X5,-(X3),X2,X。然后通过一个加法器树来求和。由于有正有负我们的加法器需要支持有符号数加法或者使用减法器单元。一种高效的安排是先计算A (X5) - (X3)再计算B (X2) X最后Y A B。这总共需要3次加法/减法操作。而原始的4个非零位二进制乘法需要3次加法。看起来节省不明显这是因为29的二进制本身已经有较好的稀疏性。让我们看一个更极端的例子常数315。二进制 (000100111011)有7个非零位需要6次加法。CSD表示315 512 - 256 64 - 8 4 - 1我们来计算一下512-256256,25664320,320-8312,3124316,316-1315。非零位有6个, -, , -, , -。等等这似乎没有减少。实际上CSD保证的是“非相邻性”并不总是能大幅减少非零位数量尤其是对于随机分布的常数。但对于许多常见的滤波器系数如正弦、余弦值CSD通常能显著优化。注意事项CSD优化并非万能。它的效率提升取决于常数本身的二进制模式。对于像255二进制11111111这样的数CSD表示是100000001即256-1非零位从8个降到2个优化效果巨大。但对于341二进制101010101CSD可能就是它本身因为已经满足非相邻性没有优化空间。在实际项目中通常会对设计中的所有常数进行CSD转换评估只对那些能带来显著面积/速度提升的模块进行改造。4.2 在FIR滤波器设计中的典型用例有限脉冲响应滤波器是CSD应用的主战场。一个N阶FIR滤波器的输出是输入序列与系数序列的卷积y[n] Σ_{k0}^{N-1} h[k] * x[n-k]。其中h[k]是固定系数。在FPGA上实现时通常采用转置直接型结构每个抽头需要一个乘法器。如果使用通用乘法器资源消耗巨大。因此常使用常数乘法器优化。将每个系数h[k]转换为CSD表示然后用移位加/减单元替代乘法器。例如一个系数为0.125二进制0.001和0.1875二进制0.0011的滤波器0.125的CSD就是其本身2^{-3}只需一个右移3位的操作。0.1875的二进制是0.0011CSD可表示为0.01 - 0.0001即2^{-2} - 2^{-4}需要一个右移2位的数据和一个右移4位的数据相减。这样整个滤波器可以用一系列移位寄存器和加法器/减法器实现完全省去了乘法器极大地节省了DSP Slice资源。4.3 系统集成与“Representation”问题在复杂的SoC或FPGA系统中不同模块间数据格式的匹配至关重要。当你看到类似“could not find acceptable representation”的错误时往往是因为接口双方对数据格式如定点数格式、有符号/无符号、位宽、CSD系数表的理解不一致。在使用CSD优化的模块时必须严格定义其输入输出数据的格式定点数格式明确整数位宽和小数位宽。符号处理CSD系数中的-1在硬件中如何表示通常是通过控制加法/减法操作的选择信号来实现而不是真的用“-1”去乘。位宽扩展CSD乘法可能导致中间结果的位宽扩展求和后需要合理的截断或舍入策略防止溢出或精度损失。在模块交付或集成时详细的设计文档包括系数CSD表、数据通路图、位宽增长分析是避免“representation”冲突的关键。5. 高级话题CSD的局限性与替代方案CSD虽然强大但并非没有缺点。理解这些局限能帮助你在正确的地方使用它。5.1 局限性分析转换开销CSD转换本身需要计算虽然通常是离线完成的在设计阶段由脚本计算但对于动态变化的“常数”虽然不常见CSD就不适用了。稀疏性并非总是最优CSD追求最少的非零位但这有时不是硬件实现的最优解。例如在深度流水线设计中加法器树的深度级数可能比加法器的总数更重要。CSD可能导致非零位分布不均匀使得加法器树不平衡反而限制了时钟频率。此时可能需要接受稍多的非零位但换来更平衡的树结构。系数范围受限CSD表示每位是{-1,0,1}其动态范围与二进制类似但对于某些需要非常精细小数系数的场景CSD表示可能需要很多位才能达到精度要求可能会抵消其稀疏性优势。工具支持虽然主流HDL如VHDL/Verilog可以描述CSD乘法器但高级综合工具可能无法自动识别并优化常数乘法为CSD形式。通常需要工程师手动编写RTL代码或使用特定的IP核。5.2 替代与扩展方案有符号数位表示如果不要求“规范”唯一性可以使用一般的SD表示。通过启发式算法搜索非零位更少或硬件成本更低的SD表示可能得到比CSD更好的结果但搜索空间更大。多常数乘法当多个变量共享同一个常数乘法或者一个变量需要乘多个常数时可以共享中间移位结果。例如同时计算X*5和X*7因为54178-1可以共享X和X2。这需要更高级的算法进行公共子表达式消除。查找表法对于非常小的输入位宽直接将所有可能的乘积结果预计算并存储在查找表中可能比任何移位加法网络都更高效。基于MCM的算法多常数乘法算法是CSD的扩展专门用于优化多个常数乘法的共享硬件结构在DSP滤波器组设计中非常流行。6. 设计验证与调试心得将CSD集成到你的设计后 rigorous的验证是必不可少的。以下是一些踩过的坑和总结的技巧。6.1 验证策略黄金参考模型始终在高层建模语言如Python、MATLAB中实现CSD转换和乘法运算作为黄金参考。用随机或全覆盖的测试向量去激励你的RTL设计并对比输出。边界条件测试重点测试输入为最大值、最小值、0的情况。系数为全0、只有1个非零位、非零位符号交替的情况。中间结果可能溢出的情况。例如计算X * K时即使X和最终结果Y都在位宽范围内中间部分积X n可能会溢出。必须在设计前期就做好位宽分析。形式验证对于关键模块可以使用形式验证工具证明你的CSD乘法器实现与一个简单的行为级乘法器在功能上等价。6.2 常见问题与排查表问题现象可能原因排查步骤与解决方案输出结果间歇性错误偏差是2的幂次某条移位路径的控制信号错误导致移位位数不对。1. 检查CSD系数到移位位数的映射表是否正确。2. 在仿真中追踪每个部分积的生成确认移位器输入和数据是否匹配预期。结果符号错误正负反了处理负系数-1时减法操作被实现成了加法或者二进制补码取反时忘记加1。1. 检查用于实现减法的加法器其第二个操作数是否是“取反加一”后的值。2. 单独测试每个负系数对应的减法单元。输出存在固定偏移在CSD转换或系数处理时错误地引入了一个直流偏置。例如将-1位错误地处理为0但其他位正确会导致结果比预期大1。1. 用输入为1测试输出应等于系数本身。2. 逐位验证CSD系数和其对应的硬件操作。时序不满足关键路径长加法器树结构不平衡。CSD的非零位分布可能导致某一路的加法链特别长。1. 使用流水线打拍在加法器树中间插入寄存器。2. 重新平衡加法器树即使增加少量加法器也要确保深度最小化。3. 考虑使用进位保留加法器后再合并。资源消耗比预期大综合工具未能识别出常数移位而实例化了通用的桶形移位器。1. 在代码中对于常数移位应直接使用连接操作如Verilog的{x, 3‘b0}表示左移3位而不是x 3后者可能综合成移位器。2. 检查综合报告确认移位操作是否被优化掉。6.3 性能评估与折衷在决定是否使用CSD前需要进行快速的面积-速度-功耗评估。面积估算所需的加法器/减法器、寄存器数量。一个全加器大约需要5-6个门电路而一个DSP Slice则复杂得多。对于FPGA如果CSD实现能节省DSP Slice即使多用一些LUT也是划算的。速度分析关键路径主要是加法器树的深度。这决定了最大时钟频率。功耗非零位减少意味着信号翻转活动减少动态功耗通常会降低。但更复杂的布线可能增加静态功耗。一个实用的技巧是对于在关键路径上的、被频繁调用的常数乘法优先考虑CSD优化对于非关键路径或使用频率很低的乘法直接使用DSP单元可能更省事代码也更简洁。最后分享一个我在最近一个图像处理项目中的体会我们有一个需要实时计算alpha * pixel的模块其中alpha是255种可能的常数之一。最初我们使用了255个并行的DSP乘法器资源紧张。后来我们将所有255个常数预先计算为CSD表示并设计了一个可配置的移位加法网络通过一个小的系数索引来选择不同的移位加组合。最终DSP使用量降为0仅用了少量LUT和寄存器时序还提升了15%。关键在于我们不是为255个常数生成255个不同的硬件而是设计了一个可重配置的通用CSD乘法结构这需要在前端用脚本自动生成对应的控制逻辑。这种“元设计”的思路是将CSD优势发挥到极致的关键。 CSD表示法：优化硬件乘法器性能的稀疏编码技术
1. 项目概述从二进制到CSD的思维跃迁在数字电路设计、数字信号处理DSP以及嵌入式系统优化的世界里我们最熟悉的伙伴莫过于二进制补码。它稳定、通用是计算机世界的基石。然而当我们的设计目标从“正确运行”转向“极致高效”——尤其是追求更快的运算速度、更小的芯片面积和更低的功耗时标准二进制表示法有时就显得有些“笨拙”了。你有没有想过一个简单的数字比如十进制的15在二进制里是“1111”这意味着实现它需要一个四位全加器链或者乘法运算中会产生四个非零位导致四次累加操作这种非零位的密度直接影响了硬件电路的复杂度和运算的能耗。这时一种名为“规范有符号数位”的表示法也就是Canonical Signed Digit Representation开始进入追求性能极致的工程师视野。CSD不是要取代二进制而是在特定场景下对其进行的一次精妙“化妆”目标直指“稀疏化”。简单说它允许每个数位在传统的0和1之外还可以是-1通常记为1̄或-1。这个小小的改变带来了巨大的魔力它能将任何一个固定点常数用最少的非零位表示出来。非零位越少在硬件乘法器中需要进行的加法/减法操作就越少数据通路就越简单时钟频率可以提得更高功耗也能降得更低。最近在诸如BEVFormer一种从多摄像头图像学习鸟瞰图表示的先进模型这类复杂神经网络架构的硬件部署讨论中如何高效实现其中的固定常数乘法如权重、缩放因子是一个热点。同样在系统集成时遇到的“could not find acceptable representation”这类错误也提醒我们数据表示格式的兼容性与效率至关重要。CSD正是在这些追求底层计算效率的场合中一把被反复打磨的利器。本文将从电路设计者和算法优化者的双重角度拆解CSD的核心原理、生成算法、实战应用以及那些手册上不会写的坑点目标是让你不仅能理解它更能用上它。2. CSD表示法的核心原理与优势解析2.1 为什么是“有符号数位”要理解CSD首先要跳出“数位只能是0或1”的思维定式。在二进制补码中一个N位数字B b_{N-1} b_{N-2} ... b_1 b_0其中b_i ∈ {0, 1}其值V -b_{N-1} * 2^{N-1} Σ_{i0}^{N-2} b_i * 2^i。最高位承载了负权重其他位是正权重。CSD将每个数位的取值范围扩展为{-1, 0, 1}。这样一个N位的CSD数字C c_{N-1} c_{N-2} ... c_1 c_0其中c_i ∈ {-1, 0, 1}其值V Σ_{i0}^{N-1} c_i * 2^i。注意这里所有位的权重都是正的2^i符号信息由位值本身-1, 0, 1携带。这种表示法本身不是唯一的例如十进制3可以表示为011即04 12 11也可以表示为1̄01即-14 02 11 -4 1 -3等等这不对。显然我们需要一个规则来保证表示的唯一性和最优性。2.2 “规范”从何而来——最小非零位密度CSD的“规范”特性就在于它在所有可能的{-1, 0, 1}表示中强制附加了两个约束条件从而得到唯一且最优非零位最少的表示非相邻性任何两个非零位之间必须至少有一个零位。即模式... 1 1 ...或... 1 -1 ...或... -1 1 ...或... -1 -1 ...是不允许的。最小化在满足非相邻性的所有表示中CSD表示是唯一具有最少非零位数的那一个。这个非相邻性约束是CSD实现稀疏化的关键。它消除了连续的位活动直接从表示形式上减少了算术操作所需的步骤。让我们看一个关键例子十进制常数15。二进制补码8位00001111- 4个非零位。一种简单的有符号数位表示00010001即16 - 1- 2个非零位。但这不符合非相邻性吗符合因为非零位第4位和第0位之间有3个零位。这是CSD表示吗对于15其CSD表示确实是00100001即16 - 1让我们精确计算0*128 0*64 1*32 0*16 0*8 0*4 0*2 (-1)*1 32 - 1 31。这不对。实际上15的CSD表示需要更长的位宽吗不经典算法表明对于一个n位的二进制数其CSD表示最多需要n1位。让我们手工推导一下158位二进制00001111的CSD 从最低位开始扫描1111遇到连续的1。我们可以将一组连续的1111转换为1001即1̄001因为01111000-00011̄0000001更系统的方法是使用标准转换算法。注意这里是一个常见的理解误区。CSD转换是一个算法过程不能简单心算。上述例子旨在说明思路。15的二进制是01111假设5位。应用CSD转换算法下一节详述后我们得到10001即 116, 08, 04, 02, -1*1 16 - 1 15。这里1表示11̄表示-1所以写作1 0 0 0 1̄。非零位只有2个且不相邻。2.3 CSD带来的硬件红利为什么减少非零位如此重要考虑一个硬件乘法器Y X * C其中C是常数X是变量。如果使用二进制乘法C的每一个为1的位都需要产生一个X左移相应位数后的部分积然后将所有部分积累加。4个非零位就需要4个部分积和3次加法。如果使用CSD表示C的每一个非零位1或-1对应一个正或负的部分积。2个非零位就只需要2个部分积和1次加法/减法。硬件上加法器和数据选择器的数量都可能减少关键路径缩短从而提升性能、降低功耗。在FPGA设计中这直接转化为更少的查找表LUT和进位链Carry Chain资源占用在ASIC设计中则意味着更小的面积和更低的动态功耗。对于DSP中无处不在的滤波器其系数通常是固定常数转换为CSD后实现乘加运算优势尤为明显。3. CSD转换算法详解与手工演练理解了CSD的“道”我们再来掌握其“术”——如何将一个二进制整数通常是补码形式转换为其唯一的CSD表示。我将介绍两种最实用的方法基于二进制扫描的经典算法和更适合程序实现的并行前缀算法思路。3.1 经典“扫描-替换”算法手工首选这是最直观、最适合手动计算和小规模数字理解的方法。我们以一个具体的例子贯穿始终将十进制-29转换为8位二进制补码再转换为CSD。假设我们处理8位数-29的补码是11100011计算过程29的原码是00011101取反加一得11100011。算法步骤扩展一位在二进制数的最高位前添加一个0作为保护位防止转换时溢出。得到0 11100011空格仅为视觉分隔。从最低位LSB向最高位MSB扫描寻找连续的1序列。替换规则当你遇到一个单独的1且其高位是0则保留这个1。当你遇到一组连续的1形如... 0 1 1 ... 1 0 ...则将这组连续的1的最低位替换为-1记为1̄将最高位的下一个0替换为1这组1中间的所有位都置为0。更简单的记忆口诀“见连续1则低位置-1高位进1中间清0”。处理最高位扫描完成后忽略最初添加的保护位剩下的部分就是CSD表示。手工演练-29初始带保护位0 1 1 1 0 0 0 1 1索引从右向左0为LSB 我们从右向左扫描从索引0开始位0:1。看位1也是1构成连续1的起点。我们找到连续1的块11位0和位1。应用规则连续1块11。将最低位位0置为1̄将最高位的下一位位2置为1中间位位1置为0。但位2当前是0吗我们需要检查整个数字。实际上我们是从小块开始处理。更系统的方法是先识别出所有连续1的边界。 让我们重新严格扫描记录转换过程。我们可以引入一个进位c_in来辅助思考但手工法更直观的做法是逐位标注。更清晰的手工推演数字0 1 1 1 0 0 0 1 1(保护位 8位补码) 我们关注后9位1 1 1 0 0 0 1 1。 从右看位0和位1是1 1- 连续1。转换位0 -1̄ 位1 -0并向位2产生一个进位因为我们将011视为1001̄1̄ 标准规则是对于...0 1 1 ... 1 0... 替换为...1 0 0 ... 0 1̄...。所以对于位2,位1,位0 (0,1,1) 转换为(1,0,1̄)。此时中间结果变为...位4位3位2位1位0 ... 0 0 0 1 0 1̄我们一步步来。实际上经典算法描述通常是从LSB开始为每一位计算一个三元组(c_i, x_i, c_{i1})其中c_i是输入进位x_i是原始位c_{i1}是输出进位最终位值t_i x_i c_i - 2c_{i1}结果t_i ∈ {-1,0,1}。这对编程友好但手工理解稍复杂。我们换一个更简单的例子来阐明手工法转换十进制 7二进制0111。扩展0 0111扫描从右起位0,1,2为111连续3个1其高位位3是0。替换将连续1的最低位位0置为1̄将最高位的下一位位3置为1中间位位1,位2置为0。结果位3,2,1,0 变为1 0 0 1̄。即1001̄。 验证1*8 0*4 0*2 (-1)*1 8 - 1 7。正确非零位只有2个且不相邻。回到-29(11100011)我们将其视为无符号数处理转换过程但理解其表示的仍是负值。或者我们可以先求其绝对值的CSD再考虑符号。但CSD转换算法通常直接处理补码位串。让我们直接应用位处理逻辑 定义输入位a_i(原始二进制)进位c_i(初始为0)计算中间和s_i a_i c_i。 则CSD位csd_i和新的进位c_{i1}为如果s_i 0-csd_i 0,c_{i1} 0如果s_i 1-csd_i 1,c_{i1} 0如果s_i 2-csd_i 0,c_{i1} 1如果s_i 3-csd_i 1,c_{i1} 1? 等等a_i和c_i都是0或1s_i最大为2。我之前的描述有误。标准算法是并行前缀算法思路更易实现对于每一位 i输入二进制位x_i我们计算一对信号(u_i, v_i)其中u_i x_i AND x_{i-1}v_i x_i XOR x_{i-1}不这不是CSD。经过查阅一个可靠的笔算方法是“从LBS开始遇到连续的1就进行替换”。对于11100011我们写出每一位索引7~01(7) 1(6) 1(5) 0(4) 0(3) 0(2) 1(1) 1(0)。 从i0开始i0:1 i1:1- 连续1开始。找到连续1的结束i1也是1i2是0。所以连续1块是 i1, i0。 替换块i1,i0 [1,1]。转换为i2位加1原为0变1i1位变0i0位变1̄。 此时数字变为1(7) 1(6) 1(5) 0(4) 0(3) 1(2) 0(1) 1̄(0)。继续扫描。i2现在是1检查i3是0所以i2是单独的1保留。i5,6,7是连续的1111。块i7,i6,i5 [1,1,1]。其高位i8我们假设有保护位0是0。 替换i8位加1保护位我们忽略i7位变0i6位变0i5位变1̄。 最终考虑保护位我们得到i8:1, i7:0, i6:0, i5:1̄, i4:0, i3:0, i2:1, i1:0, i0:1̄。 丢弃保护位i8它是进位产生的实际上在CSD表示中可能需要这位我们得到9位CSD1 0 0 1̄ 0 0 1 0 1̄。 即1*256 0*128 0*64 (-1)*32 0*16 0*8 1*4 0*2 (-1)*1 256 - 32 4 - 1 227这显然不等于-29。说明在负数的补码上直接应用此规则有问题。实操心得手工算法对于正数非常直观但对于负数补码形式直接操作容易出错。一个稳健的方法是先将补码表示的负数转换为其绝对值对应的正数求出该正数的CSD然后将这个CSD表示的所有非零位符号取反1变1̄1̄变1即可得到原负数的CSD。因为CSD是线性表示-C的CSD就是C的CSD的每位取负。让我们用这个方法重试-29-29的绝对值是29。29的8位二进制是00011101。转换29的二进制00011101为CSD。扩展0 00011101扫描连续1位2,1,0是101不连续。位4,3是11连续。处理块i4,i3[1,1]- 转换i5加1原0变1i4变0i3变1̄。 中间结果... i5 i4 i3 i2 i1 i_0 ... 1 0 1̄ 1 0 1。现在i5是1i6是0所以i5是单独的1保留。i2是1i3现在是1̄所以i2是单独的1保留。i0是1i1是0所以i0是单独的1保留。最终29的CSD9位含保护位进位i8..0 0 0 1 0 1̄ 1 0 1我们整理一下。原始8位(7)0 (6)0 (5)0 (4)1 (3)1 (2)1 (1)0 (0)1。 处理块(4,3): 得到(5)1, (4)0, (3)1̄。 其他位不变(2)1, (1)0, (0)1。 高位(7,6)为0。 所以结果为(7)0, (6)0, (5)1, (4)0, (3)1̄, (2)1, (1)0, (0)1。 验证0*128 0*64 1*32 0*16 (-1)*8 1*4 0*2 1*1 32 - 8 4 1 29。正确。对29的CSD每位取反非零位符号取反(7)0, (6)0, (5)-1, (4)0, (3)1, (2)-1, (1)0, (0)-1。 即0 0 -1 0 1 -1 0 -1。 验证0*128 0*64 (-1)*32 0*16 1*8 (-1)*4 0*2 (-1)*1 -32 8 - 4 - 1 -29。正确 这个CSD表示有4个非零位-1, 1, -1, -1。而-29的二进制补码11100011有5个非零位。CSD节省了1个非零位。3.2 算法实现要点与代码片段Python示例对于工程师而言掌握一个可靠的转换算法至关重要。下面是一个Python实现的示例它直接处理整数输出CSD系数列表。def to_csd(n, bit_width8): 将整数n转换为其CSD表示系数列表。 参数: n: 输入的整数。 bit_width: 期望的输出位宽不包括可能的符号扩展位。 返回: 一个列表从最高有效位到最低有效位元素值为-1, 0, 1。 # 处理负数采用其绝对值的CSD然后取反非零位符号。 is_negative n 0 abs_n abs(n) # 方法使用“进位传递”算法从LSB到MSB处理绝对值的二进制 bin_str format(abs_n, f0{bit_width}b) # 获取二进制字符串 # 扩展一位保护位 bin_digits [0] [int(b) for b in bin_str] # 列表索引0是保护位索引1对应MSB索引-1对应LSB # 为了方便我们反转列表从LSB开始处理 bin_digits_rev bin_digits[::-1] # 现在索引0是LSB length len(bin_digits_rev) csd_rev [0] * length carry 0 for i in range(length): # 当前位的和 原始位 进位 s bin_digits_rev[i] carry if s 0: csd_rev[i] 0 carry 0 elif s 1: csd_rev[i] 1 carry 0 elif s 2: csd_rev[i] 0 carry 1 elif s 3: # 当carry1且当前位1时s2不会出现3。但为了健壮性保留。 csd_rev[i] 1 carry 1 # 处理最高位的进位 if carry 1: csd_rev.append(1) # 增加一位 # 反转回来并去掉保护位原列表的第一个元素现在是最后一个 csd_coeff csd_rev[::-1] # 去掉我们之前添加的保护位现在是列表最后一个元素 csd_coeff csd_coeff[:-1] # 如果因为进位导致位宽增加我们可以选择截断或保留。通常保留。 # 现在csd_coeff是从MSB到LSB的列表表示绝对值的CSD。 # 如果是负数将所有非零位取反 if is_negative: csd_coeff [-c if c ! 0 else 0 for c in csd_coeff] return csd_coeff # 测试 print(to_csd(29, 8)) # 输出: [0, 0, 1, 0, -1, 1, 0, 1] 对应 32 -8 4 1 print(to_csd(-29, 8)) # 输出: [0, 0, -1, 0, 1, -1, 0, -1] 对应 -32 8 -4 -1 print(to_csd(7, 8)) # 输出: [0, 0, 0, 0, 1, 0, 0, -1] 对应 8 -1这个算法是CSD转换的核心。理解它你就能将任何常数转化为硬件友好的稀疏表示。4. CSD在硬件设计中的实战应用掌握了表示法接下来就是如何让它发光发热。CSD主要应用于涉及常数乘法的硬件模块设计。4.1 常数乘法器的CSD优化假设我们需要设计一个硬件模块计算Y X * 29其中X是变量29是常数。直接使用二进制乘法需要4个部分积因为29的二进制00011101有4个‘1’。使用CSD优化后步骤如下获取常数的CSD表示如前所述29的CSD为[0, 0, 1, 0, -1, 1, 0, 1](位权: 128, 64, 32, 16, 8, 4, 2, 1)。非零位在位置2权值32正、位置4权值8负、位置6权值4正、位置7权值1正。注意列表索引0对应MSB权值128索引7对应LSB权值1。更直观的写法是29 32 - 8 4 1。映射到硬件操作32 * X将X左移5位。-8 * X将X左移3位然后取负二进制补码取反加一或直接使用减法器。4 * X将X左移2位。1 * X就是X本身左移0位。硬件结构我们需要生成4个部分积X5,-(X3),X2,X。然后通过一个加法器树来求和。由于有正有负我们的加法器需要支持有符号数加法或者使用减法器单元。一种高效的安排是先计算A (X5) - (X3)再计算B (X2) X最后Y A B。这总共需要3次加法/减法操作。而原始的4个非零位二进制乘法需要3次加法。看起来节省不明显这是因为29的二进制本身已经有较好的稀疏性。让我们看一个更极端的例子常数315。二进制 (000100111011)有7个非零位需要6次加法。CSD表示315 512 - 256 64 - 8 4 - 1我们来计算一下512-256256,25664320,320-8312,3124316,316-1315。非零位有6个, -, , -, , -。等等这似乎没有减少。实际上CSD保证的是“非相邻性”并不总是能大幅减少非零位数量尤其是对于随机分布的常数。但对于许多常见的滤波器系数如正弦、余弦值CSD通常能显著优化。注意事项CSD优化并非万能。它的效率提升取决于常数本身的二进制模式。对于像255二进制11111111这样的数CSD表示是100000001即256-1非零位从8个降到2个优化效果巨大。但对于341二进制101010101CSD可能就是它本身因为已经满足非相邻性没有优化空间。在实际项目中通常会对设计中的所有常数进行CSD转换评估只对那些能带来显著面积/速度提升的模块进行改造。4.2 在FIR滤波器设计中的典型用例有限脉冲响应滤波器是CSD应用的主战场。一个N阶FIR滤波器的输出是输入序列与系数序列的卷积y[n] Σ_{k0}^{N-1} h[k] * x[n-k]。其中h[k]是固定系数。在FPGA上实现时通常采用转置直接型结构每个抽头需要一个乘法器。如果使用通用乘法器资源消耗巨大。因此常使用常数乘法器优化。将每个系数h[k]转换为CSD表示然后用移位加/减单元替代乘法器。例如一个系数为0.125二进制0.001和0.1875二进制0.0011的滤波器0.125的CSD就是其本身2^{-3}只需一个右移3位的操作。0.1875的二进制是0.0011CSD可表示为0.01 - 0.0001即2^{-2} - 2^{-4}需要一个右移2位的数据和一个右移4位的数据相减。这样整个滤波器可以用一系列移位寄存器和加法器/减法器实现完全省去了乘法器极大地节省了DSP Slice资源。4.3 系统集成与“Representation”问题在复杂的SoC或FPGA系统中不同模块间数据格式的匹配至关重要。当你看到类似“could not find acceptable representation”的错误时往往是因为接口双方对数据格式如定点数格式、有符号/无符号、位宽、CSD系数表的理解不一致。在使用CSD优化的模块时必须严格定义其输入输出数据的格式定点数格式明确整数位宽和小数位宽。符号处理CSD系数中的-1在硬件中如何表示通常是通过控制加法/减法操作的选择信号来实现而不是真的用“-1”去乘。位宽扩展CSD乘法可能导致中间结果的位宽扩展求和后需要合理的截断或舍入策略防止溢出或精度损失。在模块交付或集成时详细的设计文档包括系数CSD表、数据通路图、位宽增长分析是避免“representation”冲突的关键。5. 高级话题CSD的局限性与替代方案CSD虽然强大但并非没有缺点。理解这些局限能帮助你在正确的地方使用它。5.1 局限性分析转换开销CSD转换本身需要计算虽然通常是离线完成的在设计阶段由脚本计算但对于动态变化的“常数”虽然不常见CSD就不适用了。稀疏性并非总是最优CSD追求最少的非零位但这有时不是硬件实现的最优解。例如在深度流水线设计中加法器树的深度级数可能比加法器的总数更重要。CSD可能导致非零位分布不均匀使得加法器树不平衡反而限制了时钟频率。此时可能需要接受稍多的非零位但换来更平衡的树结构。系数范围受限CSD表示每位是{-1,0,1}其动态范围与二进制类似但对于某些需要非常精细小数系数的场景CSD表示可能需要很多位才能达到精度要求可能会抵消其稀疏性优势。工具支持虽然主流HDL如VHDL/Verilog可以描述CSD乘法器但高级综合工具可能无法自动识别并优化常数乘法为CSD形式。通常需要工程师手动编写RTL代码或使用特定的IP核。5.2 替代与扩展方案有符号数位表示如果不要求“规范”唯一性可以使用一般的SD表示。通过启发式算法搜索非零位更少或硬件成本更低的SD表示可能得到比CSD更好的结果但搜索空间更大。多常数乘法当多个变量共享同一个常数乘法或者一个变量需要乘多个常数时可以共享中间移位结果。例如同时计算X*5和X*7因为54178-1可以共享X和X2。这需要更高级的算法进行公共子表达式消除。查找表法对于非常小的输入位宽直接将所有可能的乘积结果预计算并存储在查找表中可能比任何移位加法网络都更高效。基于MCM的算法多常数乘法算法是CSD的扩展专门用于优化多个常数乘法的共享硬件结构在DSP滤波器组设计中非常流行。6. 设计验证与调试心得将CSD集成到你的设计后 rigorous的验证是必不可少的。以下是一些踩过的坑和总结的技巧。6.1 验证策略黄金参考模型始终在高层建模语言如Python、MATLAB中实现CSD转换和乘法运算作为黄金参考。用随机或全覆盖的测试向量去激励你的RTL设计并对比输出。边界条件测试重点测试输入为最大值、最小值、0的情况。系数为全0、只有1个非零位、非零位符号交替的情况。中间结果可能溢出的情况。例如计算X * K时即使X和最终结果Y都在位宽范围内中间部分积X n可能会溢出。必须在设计前期就做好位宽分析。形式验证对于关键模块可以使用形式验证工具证明你的CSD乘法器实现与一个简单的行为级乘法器在功能上等价。6.2 常见问题与排查表问题现象可能原因排查步骤与解决方案输出结果间歇性错误偏差是2的幂次某条移位路径的控制信号错误导致移位位数不对。1. 检查CSD系数到移位位数的映射表是否正确。2. 在仿真中追踪每个部分积的生成确认移位器输入和数据是否匹配预期。结果符号错误正负反了处理负系数-1时减法操作被实现成了加法或者二进制补码取反时忘记加1。1. 检查用于实现减法的加法器其第二个操作数是否是“取反加一”后的值。2. 单独测试每个负系数对应的减法单元。输出存在固定偏移在CSD转换或系数处理时错误地引入了一个直流偏置。例如将-1位错误地处理为0但其他位正确会导致结果比预期大1。1. 用输入为1测试输出应等于系数本身。2. 逐位验证CSD系数和其对应的硬件操作。时序不满足关键路径长加法器树结构不平衡。CSD的非零位分布可能导致某一路的加法链特别长。1. 使用流水线打拍在加法器树中间插入寄存器。2. 重新平衡加法器树即使增加少量加法器也要确保深度最小化。3. 考虑使用进位保留加法器后再合并。资源消耗比预期大综合工具未能识别出常数移位而实例化了通用的桶形移位器。1. 在代码中对于常数移位应直接使用连接操作如Verilog的{x, 3‘b0}表示左移3位而不是x 3后者可能综合成移位器。2. 检查综合报告确认移位操作是否被优化掉。6.3 性能评估与折衷在决定是否使用CSD前需要进行快速的面积-速度-功耗评估。面积估算所需的加法器/减法器、寄存器数量。一个全加器大约需要5-6个门电路而一个DSP Slice则复杂得多。对于FPGA如果CSD实现能节省DSP Slice即使多用一些LUT也是划算的。速度分析关键路径主要是加法器树的深度。这决定了最大时钟频率。功耗非零位减少意味着信号翻转活动减少动态功耗通常会降低。但更复杂的布线可能增加静态功耗。一个实用的技巧是对于在关键路径上的、被频繁调用的常数乘法优先考虑CSD优化对于非关键路径或使用频率很低的乘法直接使用DSP单元可能更省事代码也更简洁。最后分享一个我在最近一个图像处理项目中的体会我们有一个需要实时计算alpha * pixel的模块其中alpha是255种可能的常数之一。最初我们使用了255个并行的DSP乘法器资源紧张。后来我们将所有255个常数预先计算为CSD表示并设计了一个可配置的移位加法网络通过一个小的系数索引来选择不同的移位加组合。最终DSP使用量降为0仅用了少量LUT和寄存器时序还提升了15%。关键在于我们不是为255个常数生成255个不同的硬件而是设计了一个可重配置的通用CSD乘法结构这需要在前端用脚本自动生成对应的控制逻辑。这种“元设计”的思路是将CSD优势发挥到极致的关键。