javascript - 如何用 JavaScript 实现乘法器电路

Question

TBH 我很难理解逻辑门图，因为我还没有完全理解低级电子设备及其工作原理。

我有一点学习基本逻辑门的经验，在观看了一些视频并思考了很多之后，我可以在几分钟内理解它，然后就消失了。

但后来我看到了一些在软件中“实现”“逻辑门”的例子，这让我更明白发生了什么。例如，here .

然后我什至能够更进一步并理解full adder是如何有效，如here :

function fullAdder(a,b,c){
  return {
    c:or(and(xor(a,b),c), and(a,b)), // C is the carry
    s:xor(xor(a,b),c) // S is the sum
  };
}

与逻辑图相比，这非常基本。

现在我想了解如何 multiplication和 division在逻辑门中实现，例如 x86 的 MUL运算符。

function MUL(a,b){
  return {
    ...
  };
}

除了花一些时间来理解乘法器电路并尝试使用上面的示例将其转换为 NAND 门实现之外，我真的不知道从哪里开始。想知道知道这一点的人是否可以演示 JavaScript 中的实现。

Answer 1

乘法依赖于数字的二进制编码方式。如果 A 是无符号的并且由位 a_n-1,a_n-2,...,a_1,a_0 编码，则其值为
A=a_n-1*2^n-1+a_n-2*2^n-2+...+a_1*2^1+a_0

所以要乘以A×B，你必须这样做
A×B=A×(b_n-1*2^n-1+b_n-2*2^n-2+...+b_1*2^1+b_0)
= A×b_n-1*2^n-1+A×b_n-2*2^n-2+...+A×b_1*2^1+A×b_0
乘法只是一个大加法，其中每个项 A×b_i*2^i 要么是 A×2^i(如果 b_i==1)，要么是 0(如果 b_i==0)

这是 C 语言的实现

int mult(unsigned short A, unsigned short B){
  int res=0;
  int mask=0x1;
  for(int i=0; i<16;i++,mask<<=1){
    if(B&mask)
      res += (A << i);
  }
  return res;
}

b_i 上的测试可以用“与”门代替。

int mult(unsigned short A, unsigned short B){
  int res=0;
  int mask=0x1;
  for(int i=0; i<16;i++,mask<<=1){
     res += (A&~(((B&mask)>>i) -1))<<i;
  }
  return res;
}

这个奇特的表达式提取 B 的第 i 位 ( B&mask )，将其放在 LSB ( >>i )，减去 1，这样我们就有了 1-1=0 it 位为 1 和 -1=0xffffffff否则。我们只需对 A 求补并进行“与”即可根据第 i 位得到 A 或 0。幸运的是，硬件方面的事情变得更容易。复制 B 的 b_i 位并与 A 的每一位进行“与”就足够了。

为了简化硬件，变量移位A<<i可以用每一步 A 左移 1 位来代替 ( A=A<<1 )。并且可以对 b_i 提取进行类似的修改，这样我们总是考虑 B 的 LSB。

int mult(unsigned short A, unsigned short B){
  int res=0;
  int mask=0x1;
  for(int i=0; i<16;i++){
     res += A&~((B&mask) -1);
     A <<= 1;
     B >>= 1;
  }
  return res;
}

一旦循环展开，这或多或少就是简单乘法器在硬件中的样子。您可以在 js 中实现它，并将 + 替换为由门完成的加法器，并使用模拟的“与”门。

实际上，硬件乘法器要复杂一些。

• 他们使用没有进位传播的特殊加法器来减少加法时间(进位保存加法)。这需要在计算结束时进行额外的添加

• 他们经常使用基数 4 来减少加法步骤的数量(修改后的布斯算法)。

• 它们被流水线化以提高吞吐量

顺便说一句，您可能对此感兴趣online simulator不同的计算机算术算法。