Как схема умножения может быть реализована в JavaScript

TBH Мне трудно понять схемы логических элементов, потому что я еще не полностью понял низкоуровневое электронное оборудование и то, как все это работает.

У меня был небольшой опыт изучения основных логических вентилей, и после просмотра нескольких видеороликов и долгих размышлений я могу понять это в течение нескольких минут, прежде чем оно ускользнет.

Но потом я увидел несколько примеров «логических вентилей», «реализованных» в программном обеспечении, и стало гораздо понятнее, что происходит. Например, здесь.

Затем я даже смог пойти дальше и понять, как работает полный сумматор. , как в здесь:

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
  };
}

Это довольно просто по сравнению с логическими схемами.

Теперь я хотел бы понять, как умножение и division реализованы в логических вентилях, таких как x86 MUL.

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

Я действительно не знаю, с чего начать, кроме как посвятить серьезное время изучению схемы умножителя и попытке перевести ее, возможно, в реализацию вентиля И-НЕ, используя приведенные выше примеры. Интересно, может ли тот, кто это уже знает, продемонстрировать реализацию в JavaScript.


javascript logic multiplication circuit
person user10869858    schedule 03.03.2019    source источник
comment
Может быть, это поможет? en.wikipedia.org/wiki/Binary_multiplier   -  person Sacha    schedule 03.03.2019
comment
Альтернативная логика переноса: c:or(and(a, b), and(a, c), and(b, c)) / c:nand(nand(a, b), nand(a, c), nand(b, c))   -  person greybeard    schedule 04.03.2019
comment
I would like to understand how [division is] implemented in logic gates удачи.   -  person greybeard    schedule 04.03.2019

Ответы (1)


arrow_upward
1
arrow_downward

Умножение зависит от способа кодирования чисел в двоичном коде. Если A не имеет знака и кодируется битами a_n-1,a_n-2,...,a_1,a_0, его значение равно
A=a_n-1*2^n-1+a_n-2*2^n- 2+...+а_1*2^1+а_0

Таким образом, чтобы умножить AB, вы должны сделать
AB=A(b_n-1*2^n-1+b_n-2*2^n-2+...+b_1*2^1+b_0)
= Ab_n-1*2^n-1+Ab_n-2*2^n-2+...+Ab_1*2^1+Ab_0
а умножение - это просто большое сложение, где каждый член Ab_i*2^ я равен либо A2^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;
}

Это причудливое выражение извлекает i-й бит B (B&mask), помещает его в LSB (>>i), вычитает 1, так что мы имеем 1-1=0, если бит равен 1, и -1=0xffffffff в противном случае. Нам просто нужно дополнить и сделать «и» с A, чтобы получить либо A, либо 0 в зависимости от i-го бита. К счастью, на аппаратном уровне все проще. Достаточно продублировать бит b_i в B и выполнить «и» с каждым битом в A.

Чтобы упростить аппаратное обеспечение, переменный сдвиг A<<i можно заменить сдвигом A влево на 1 бит на каждом шаге (A=A<<1). И аналогичную модификацию можно сделать для извлечения b_i таким образом, чтобы мы всегда учитывали младший бит B.

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, чтобы уменьшить количество шагов добавления (модифицированный алгоритм Бута).

  • они конвейеризированы для повышения пропускной способности

Кстати, вас может заинтересовать этот онлайн-симулятор различных компьютерные арифметические алгоритмы.

person Alain Merigot    schedule 03.03.2019