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

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

0 голосов
/ 03 марта 2019

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

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

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

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

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

1 Ответ

0 голосов
/ 03 марта 2019

Умножение зависит от способа кодирования чисел в двоичном формате.Если 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 можно заменить на 'и' gate. 

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 может быть заменено 1-битным левым сдвигом Aна каждом шагу (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 и заменить + на сумматор, выполненный с помощью gates, и использовать имитированные "и" gates.

На самом деле аппаратные множители немного сложнее.

  • они используют специальный сумматор без переноса переноса, чтобы уменьшить время сложения (сложение переноса добавлено).Это требует дополнительного сложения в конце вычислений

  • они часто используют базу 4 для уменьшения количества шагов добавления (модифицированный алгоритм Бута).

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

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

...