检验一个n位二进制码是否是独热码

PB22111665 胡揚嘉

特别感谢前助教马子睿学长的鼎立支持和对文档的重要维护

问题描述

给定一个n位二进制码，判断是否是独热码。独热码是指只有一个位为1，其他位为0的二进制码。

组合电路时延复杂度基础知识

算法复杂度

在算法里，如果一个解法和问题规模$n$大致成正比，那么我们就可以说这个算法是$O(n)$级别的算法，它的执行时间会随着$n$的增长而线性变化。同理，如果一个解法和问题规模$n^2$大致成正比，那么我们就可以说这个算法是$O(n^2)$级别的算法，它的执行时间会随着$n$的增长而呈现平方级别的增长——显然这个增长速度一定大于$O(n)$。一般情况下，我们较为常见的几种算法复杂度的增长速度排序为： $$ O(2^n)>O(nk)>O(log_2n) $$ 这可以使用数学分析的基本知识分析几个函数的增长速度得到。

组合电路时延复杂度

组合电路时延复杂度和算法复杂度分析有异曲同工之处。对于一个输入长度或规模为$n$的输入信号，如果得到运算结果所需的最长通路上的门个数与$n$大致成正比，那么我们就说这个组合电路时延复杂度是$O(n)$级别的。例如，对于四位数$A$的缩位与运算，如果你只能使用2输入与门，那么就会产生两种常规思路：

$(((A[1]\& A[2])\&A[3])\&A[4])$

这种算法就是逐位顺序与运算。随着$A$长度的提升，显然我们最长的数据通路需要经过的与门数量是线性增长的，因此这个组合电路时延复杂度是$O(n)$级别的

$(A[1]\& A[2])\&(A[3]\&A[4])$

这种算法使用类似于二叉树的结构进行构建。对于一个输入长度为4的信号，我们最长逻辑通路为2个与门。对于一个输入长度为8的信号，我们最长逻辑通路为3个与门——这就像一棵满二叉树一样。因此，这个组合电路的时延复杂度为$O(log_2n)$，显然好于第一种算法。

常见组合运算的时延复杂度

在这里，我们采用$T(*)$来表示运算符$*$的时延复杂度：

按位逻辑运算（包括与、或、非、异或等） $$ T(|)=T(&)=T(textasciicircum)=T(textasciitilde)=O(1) $$ 这是因为，按位运算位之间没有任何依赖关系。如果$A$和$B$进行按位逻辑运算，那么$A[i]$只会和$B[i]$运算，和其余位都没有关系，哪怕信号长度是114514，这些组合电路的时延复杂度也不会有变化。
缩位逻辑运算（包括缩位与andR、缩位或orR等） $$ T(andR)=T(orR)=O(log_2n) $$ 缩位逻辑运算可以使用二叉树的方式进行实现，而无需真的顺序逐位进行运算，因此可以将运算树的高度控制在$log_2n$级别。
等于和不等于比较事实上就是通过按位逻辑运算+缩位逻辑运算实现的，例如，$A$和$B$的等于比较就可以表示为： $$ textasciitilde(|(Atextasciicircum B)) $$ 也就是先按位异或，再缩位或后取反。因此等于和不等于比较的复杂度事实也是$O(log_2n)$。
将一个$n$位数逐位相加（addR）的运算复杂度是否也是$O(log_2n)$？虽然它也可以使用二叉树进行计算，但答案是否定的。我们首先考虑，$n$个一位数相加最终结果最多需要$log_2n+1$位进行表示，也就是说其实从下向上数第$i$层二叉树的在执行的是$log_2i$位的加法运算。注意，即便可以使用超前进位加法器，加法位之间的延迟也是无可避免的（事实上超前进位加法器如果不在CMOS级别进行特殊设计，它本质上和串行进位加法器没有区别，这一点可以从超前进位加法器的逻辑推导式上看出）。那么，这个二叉树的实际延迟其实是： $$ T(addR)=O(sum_{i=1}^{{log_2n}i)=O((log_2n)}2) $$ 大部分情况下，这是比缩位逻辑运算要高出很多的复杂度。
加法和减法运算：

对于不进行特殊设计的超前进位加法器，加法和减法每一位运算都需要依赖低位的运算，因此其复杂度为$O(n)$

大于、小于、大于等于、小于等于运算事实上也需要通过加法和减法进行计算。这一类运算的复杂度也为$O(n)$

思考：左移和右移的复杂度是$log_2n$，它们是如何计算的？请自行搜索关键词“桶形移位器”，得到这些运算复杂度的解释。

解决思路

先来介绍一种常规解法：

module one_hot
(
  input [7:0] din,
  output flag
);
  assign flag = (((din[0]+din[1])+(din[2]+din[3]))+((din[4]+din[5])+(din[6]+din[7]))) == 1;
endmodule

这是很常规的思路，把$din$每一位都加起来，如果结果是1，证明只有一位是1，那么就符合独热码。我们分析过，这种算法的复杂度是$O((log_2n)^2)$。

上面所说的算法虽然已经不错，但加法毕竟是消耗资源比较大的运算，下面我们就将介绍几种解决独热码问题非常重要的思想

解法1

module one_hot
#(parameter N=64)
(
  input [N-1:0] din,
  output flag
);
reg [N-1:0] P;
always @(*) begin
  P[0]=din[0];
  for(int i=1;i<N;i=i+1) begin
    P[i]=P[i-1]^din[i]
  end
end
  assign flag=((&(~din | P))&&P[N-1])?1'b1:1'b0;
endmodule

这里的主要思想是构造突变变量，我们先来了解一下什么是突变变量：

对于一个$n$位的二进制信号$A$，若存在$k$满足$0\le k\le n-1$，使得对$\forall i\le k$，$\forall j >k$，$A[i]\textasciicircum A[j]=1$，则A为突变变量

独热码和突变变量有什么关系呢？我们通过这个算法的输出结果，来看一下独热码的规律。对于一个输入信号而言，它只有三种可能性：

全0码：（din = 0000）
P = 1111，不是突变变量
独热码：（例如din = 00100）
P = 11100，是突变变量，$k=1$
有至少2个1：(例如din = 1010)
P = 0110，不是突变变量，出现了第二个1（可以引申到任意个数（大于2）的1，处于任意位置，一定在第二个1出现问题）

从这里我们可以看到，当且仅当din是独热码时，这种算法生成的P才会成为突变变量。在获取到P后，我们需要检测其是否为突变变量。这里我们考虑到两种情况：

若$din\ne 0$,那么$\textasciitilde din|P$一定全为1，我们只需要使用缩位与判断是否为1即可。
若$din=0$，那么上述检测方法依然输出1，但此时$P$的最高位为0，而其他情况下$P$最高位为1，因此可以对这种情况进行特判。

从flag的生成逻辑，我们已经看到了上述两种情况的实现方式。

时延复杂度分析

第一层：n-1次逐个异或：$O(1\times n)=O(n)$
第二层：按位取反+按位或+缩位与+按位与：$O(1+1+log_2n+1)=O(log_2n)$

因此整体时延复杂度：$O(n)+O(log_2n)=O(n)$

对于算法复杂度不熟悉的同学，这里时间复杂度运算规则一定要及时查阅资料或询问助教！

虽然这种算法在时延复杂度上不如逐位加法，但其避免了较大位宽的加法器使用，在整体面积上有一定的优势。

解法2

module one_hot(
  input [7:0] din,
  output flag
);
// 构造固定的8个独热码
wire [ 7: 0] P1 = 8'h01;
wire [ 7: 0] P2 = 8'h02;
wire [ 7: 0] P3 = 8'h04;
wire [ 7: 0] P4 = 8'h08;
wire [ 7: 0] P5 = 8'h10;
wire [ 7: 0] P6 = 8'h20;
wire [ 7: 0] P7 = 8'h40;
wire [ 7: 0] P8 = 8'h80;

// 检测是否有对应独热码
wire [ 7: 0] S1 = P1 ^ din;
wire [ 7: 0] S2 = P2 ^ din;
wire [ 7: 0] S3 = P3 ^ din;
wire [ 7: 0] S4 = P4 ^ din;
wire [ 7: 0] S5 = P5 ^ din;
wire [ 7: 0] S6 = P6 ^ din;
wire [ 7: 0] S7 = P7 ^ din;
wire [ 7: 0] S8 = P8 ^ din;

// 符合某个独热码，则Si全为0，自或为0，取反为1
wire [ 0: 0] Q1 = ~(|S1);
wire [ 0: 0] Q2 = ~(|S2);
wire [ 0: 0] Q3 = ~(|S3);
wire [ 0: 0] Q4 = ~(|S4);
wire [ 0: 0] Q5 = ~(|S5);
wire [ 0: 0] Q6 = ~(|S6);
wire [ 0: 0] Q7 = ~(|S7);
wire [ 0: 0] Q8 = ~(|S8);

// 8个独热码的或，有一个为1就成立
assign flag = ((Q1 | Q2) | (Q3 | Q4)) | ((Q5 | Q6 )| (Q7 | Q8)); 
endmodule

这个算法的思想是逐位比较：

若该输入有一个对应的独热码$Pi$，则其$Si$全为0，$Qi$为1。
同时可以保证，最多有一个$Qi$为1，其他Qi为0。

时延复杂度分析

一次按位异或，复杂度$O(1)$
一次缩位或，复杂度$O(log_2n)$
一次按位取反，复杂度$O(1)$
二叉树按位或，复杂度$O(1\times log_2n)=O(log_2n)$

因此总时间复杂度为$O(1+log_2n+1+log_2n)=O(log_2n)$

改进：这里利用了8个确认独热码，异或其实增加了工作量。

再次思考，还有什么是独热码特有的？？

A：有且只有一个1

答案放在解法4

解法3

assign din_minus1 = din - 1;
assign flag = ((din & din_minus1) == 10'b00_0000_0000) & ((|din));

思想：

假如din是独热码，则有一个1，不妨假设在第i位。
din[i] = 1 ; din[n-1..i+1] = 0; din[i-1..0] = 0;
din_minus1 = din - 1;
显然，din_minus1[n-1..i] = 0; din_minus1[i-1..0] = 1;
那么，din & din_minus1 = 0;
现在看看不是独热码，有两个1的情况：
第2个1开始，后面的1都会相与出1
在排除全是0的情况下，实际上，相当于din[n]=1的独热码被计算，可通过检测，需要排除

时延复杂度分析

一次减法，复杂度$O(n)$
一次按位与，复杂度$O(1)$
一次相等比较，复杂度$O(log_2n)$
一次按位与，复杂度$O(1)$

因此，总时延复杂度$O(n+1+log_2n+1)=O(n)$，较为耗时，且使用了加法器，面积消耗也较大。

但是：小位数减法在vivado中的时序不同。
1. 对于小规模的减法（如4位或更少），FPGA中的查找表可以直接实现所有可能的输入组合。具体而言，可以为每对输入生成一个预计算的输出，减少运算所需的逻辑门。 2. 许多FPGA提供DSP切块，这些切块通常可以高效地实现加法和减法运算，特别是在较小的数据位宽中。 3. 综合工具（如Vivado）通常会自动进行一些优化，使得实际延迟远低于O(n)。通过使用查找表、组合逻辑、并行计算等技巧，可以有效地提高性能和资源利用率。可以通过分析综合报告来评估具体的延迟和资源使用情况。 4. 实际还需要依照具体实现情况。

解法4

input [3:0] A;
output Y;

Y = (A[0] & (!A[1]) & (!A[2]) & (!A[3])) 
   |((!A[0]) & A[1] & (!A[2]) & (!A[3]))
   |((!A[0]) & (!A[1]) & A[2] & (!A[3]))
   |((!A[0]) & (!A[1]) & (!A[2]) & A[3]);

思想: Y为1（为独热码）的唯一可能，有一位是1，其他位是0。

那么构造一位不变，其余为取反的逻辑。

即：

A     =  an, an-1, an-2,……, a1, a0
A_bar = !an,!an-1,!an-2,……,!a1,!a0
NEW[i] = j != i {NEW[i][j] = A_bar[j]}   NEW[i][i] = A[i]

此时，如果有独热码，其对应的NEW[i]为全1。自与，取或。

时延复杂度分析

一次按位取反，复杂度$O(1)$
一次缩位与，复杂度$O(log_2n)$
一次按位或，复杂度$O(log_2n)$

相比减少了一次异或的延迟！！！

因此总时间复杂度为$O(1+log_2n+log_2n)=O(log_2n)$

类比方法2，相同之处在于：都在利用独热码的特性，只有一个1。来构造变量。这里更像是使用了卡诺图进行了逻辑分析，但问题在于算法规模不好扩展。

解法5

独热码及全空的情况下，最多只有一个1.

那么逐位加，最大为1，不会有进位位。现在利用这个做文章。

迭代思想

当确保前一半没有进位，后一半没有进位，取它们的结果相加，再做一次进位位检测。没有则得到整体是最多只有一个1.

实现：构造二叉树半加器，计算进位位（相与）保存，底层的非进位位传给高层做相同操作。最后对全部进位位做自或，得到是否有进位位。

自行实现。

分析：半加的代价是$O(1)$。共$log_2n$层。虽然总复杂度也为$O(log_2n)$，但显然这个执行的运算相较解法4少了一个$log_2n$级别的运算延迟，且没有引入耗时的全加器，也为缩位或的代价可以随着树的进行而看不见(类似伴随树)

注：不是与上面的缩位加相同的复杂度，因为这里我们强制每次都是1bit的数据，我们会主动扔去进位位。保持每次都是1bits的操作。

图解

alt text

提问

为什么总是需要格外区分独热码和全0码？猜测并且验证某种可能存在的底层原理
尝试自己写出代码。
尝试做带参数的代码，使之能够符合与任意位长的独热码争端。回答哪些方法更适合做带参调整。
自行比较各个方法的延时复杂度！