如何在 JavaScript 中实现乘法器电路

Question

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

我有一点学习基本逻辑门的经验，在看了几个视频并思考了很多之后，我可以在它溜走之前理解它几分钟。

但后来我在软件中看到了一些 "logic gates" "implemented" 的例子，这让我更明白发生了什么。例如，here.

然后我什至能够更进一步理解 full adder works, as in 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 and division are implemented in logic gates, such as like x86's MUL运算符。

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

除了花一些认真的时间来理解乘法器电路并尝试使用上面的示例将其转化为与非门实现之外，我真的不知道从哪里开始。想知道知道这一点的人是否已经可以在 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 如果 b_i==1 则为 A×2^i 或如果 b_i==0[= 则为 0 18=]

这是 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 上的测试可以用 'and' 门代替。

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 它的位是 1否则为 -1=0xffffffff。我们只需要用 A 补码并执行 "and" 以获得 A 或 0，具体取决于第 i 位。幸运的是，硬件方面的事情更容易。复制 B 的 b_i 位并对 A 的每一位执行 "and" 就足够了。

为了简化硬件，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 中实现它，并将 + 替换为用门完成的加法器，并使用模拟的 "and" 门。

实际上，硬件乘法器有点复杂。

他们使用没有进位传播的特殊加法器来减少加法时间（进位保存加法）。这需要在计算结束时额外添加
他们经常使用基数 4 来减少添加步骤的数量（改进的 Booth 算法）。
它们通过管道传输以提高吞吐量

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

如何在 JavaScript 中实现乘法器电路

How a multiplier circuit could be implemented in JavaScript

javascript

logic

circuit

multiplication