Обнаружение переполнения в CSA (Carry-save Adder)

Сумматор с переносом-сохранением имеет три входа и два выхода. Многие разные выходные пары представляют одно и то же число. Сумматоры с сохранением переноса не имеют накладных расходов на распространение переноса, поэтому они хороши для сложения множества операндов с малой задержкой, но цена такой скорости заключается в том, что вы ничего не знаете о результате (даже о том, положительный он или отрицательный). ) до тех пор, пока вы не добавите последние два вывода вместе, используя «обычный» сумматор (например, перенос с переносом, выбор переноса, пропуск переноса или просмотр с переносом).

Я не знаю способа определить переполнение, просто взглянув на старшие значащие биты (как это можно сделать в сумматоре с переносом). Например, вот пример переполнения в 3-битном дополнении до 2 (3+3-2 = 4).

  0 1 1     (3)
  0 1 1     (3)
  1 1 0     (-2)
  -----
  1 1 0     (-2)
0 1 1       (6)

И еще один с теми же старшими битами, который не переполняется:

  0 1 1     (3)
  0 1 1     (3)
  1 0 1     (-3)
  -----
  1 0 1     (-3)
0 1 1 0     (6)

Мне пришлось вернуться к моему руководству по 68HC11, чтобы понять, где я ошибся в своем ответе. Так! Ответ заключается в том, чтобы посмотреть на знаковые биты как входных данных, так и результатов.

• Если вы сложите два положительных числа, а результат будет отрицательным, у вас возникло переполнение.
• Если вы добавите два отрицательных числа и получите положительный результат, у вас возникло переполнение.
• Добавление отрицательного и положительного числа не может переполниться

Вы можете обнаружить переполнение после CSA, используя два самых значимых бита переноса, обозначаемых$C_o$(бит, который отбрасывается), и$C$, и самый старший знаковый бит,$S$. Дополнение переполнится, если$C_o = S = 0$и$C=1$, т. е. все положительные числа, но сумма не может быть представлена ​​в соответствующем представлении дополнения до двух (хотя на самом деле вы получите положительное число в конце, вызванное двойным переполнением) или$C_0 = S = 1$и$S=0$, т. е. все отрицательные входные данные, но слишком большая величина (но это все равно может привести к отрицательному числу из-за двойного переполнения).

Переполнение в финальном добавлении (перенос-сохранение в неизбыточную форму) обнаруживается как обычно (сравнивая два последних бита переноса, если они различны, происходит переполнение, как мы увидим, проверка признаков невозможна).

Пример 1:

  011
  011
 +011
-----
 011  carry
  011 sum

Переполнение как$C_o = 0, S = 0, C = 1$

  110
 +011
 ----
  001

Здесь в конце происходит еще одно переполнение (хотя это не обнаружено, поскольку с точки зрения дополнения до двух$-2 + 3$не переполняется), поэтому несмотря на переполнение получается положительное число.

Пример 2:

  010
  010
 +110
-----
 010  carry
  110 sum

Нет переполнения, как$C_o = 0, S = 1, C = 1$

  100
 +110
 ----
  010

Правильный ответ! Тем не менее, похоже, что произошло переполнение при добавлении двух дополнений. Это можно решить, заменив биты знака как$S' = C_o$и$C'= C \oplus S \oplus C_o$(это также сделает представление переноса-сохранения смещаемым), что приведет к

  000
 +010
 ----
  010

и переполнение не обнаружено (что правильно).

Пример 3:

  011
  011
 +111
-----
 011  carry
  111 sum

Нет переполнения, как$C_o = 0, S = 1, C = 1$

  110
 +111
 ----
  101

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

  010
 +011
 ----
  101

Теперь, поскольку входящий перенос на конечную стадию (1) отличается от исходящего (0), обнаруживается переполнение, что, конечно, правильно, поскольку$3+3-1$находится вне$[-4,3]$возможный диапазон

Все это предлагается и обсуждается в «Архитектурах переноса-сохранения для высокоскоростной обработки цифровых сигналов» Тобиаса Нолла.