Сумматор Брента – Кунга

Арифметико-логическая схема

Сумматор Брента-Кунга ( BKA или BK ), предложенный в 1982 году ^[1] , представляет собой усовершенствованную конструкцию двоичного сумматора , имеющую глубину уровня затвора . ${\displaystyle O(\log _{2}(n))}$

Введение

Сумматор Брента-Кунга представляет собой форму параллельного префиксного сумматора (PPA) сумматора с упреждающим переносом (CLA). Предложенный Ричардом Пирсом Брентом и Сян Те Кунгом в 1982 году, он обеспечивает более высокую регулярность структуры сумматора и имеет меньшую перегрузку проводки, что приводит к повышению производительности и уменьшению необходимой площади кристалла для реализации по сравнению с сумматором Когге-Стоуна (KSA). Это также намного быстрее, чем сумматоры с пульсирующим переносом (RCA).

Сумматоры со пульсирующим переносом были первыми многобитными сумматорами, которые были разработаны на заре и получили свое название от пульсационного эффекта, который создавал перенос при распространении справа налево. Время, затраченное на сложение, было прямо пропорционально длине добавляемого бита. В сумматорах Брента-Кунга все происходит наоборот, где перенос вычисляется параллельно, что значительно сокращает время сложения. Дальнейшая работа была проделана над сумматорами Брента-Кунга и другими параллельными сумматорами, чтобы уменьшить энергопотребление и площадь кристалла, а также увеличить скорость, что делает их подходящими для конструкций с низким энергопотреблением.

Сумматор Брента-Кунга представляет собой параллельный сумматор, выполненный по регулярной схеме с целью минимизации площади кристалла и простоты изготовления. Сложение n-битных чисел может выполняться вовремя с размером области чипа , что делает его подходящим сумматором с ограничениями по площади и максимизирует производительность. Его симметрия и регулярная структура эффективно снижают производственные затраты и позволяют использовать его в конвейерных архитектурах. В параллельных сумматорах критический путь определяется путем вычисления переноса от сумматора младшего значащего бита (LSB) к сумматору старшего бита (MSB), поэтому предпринимаются усилия по уменьшению критического пути переноса для достижения старшего бита. ${\displaystyle O(\log _{2}n)}$ ${\displaystyle O(n\log _{2}n),}$

Базовая схема модели

В общем, большинство сумматоров используют перенос и соответствующие биты двух чисел (A и B) для получения соответствующего бита суммы и переноса - при этом сумматорам со пульсирующим переносом требуется время, чтобы перенос достиг старшего разряда. ${\displaystyle O(n)}$

• Учитывая, что A = a _n a _n-1  … a ₁ и B = b _n b _n-1  … b ₁ являются n-битными двоичными числами.
• При сумме S = s _n+1 s _n  … s ₁ и переносе, генерируемом на каждом этапе C = c _n  … c ₀ , будет перенесен на следующие этапы.

• Для RCA c ₀  = 0 , а i генерируемые бит суммы и бит переноса равны
  c _i  = g _i  ∨ (a _i  ∧ c _i-1 ) ∨ (b _i  ∧ c _i-1 ),
  s _i  = a _i  ⊕ b _i  ⊕ c _i-1 для i  = 1, 2, … n
  s _n+1  = c _n соответственно.
• Вышеупомянутый пульсирующий перенос можно преобразовать в упреждающий перенос (CLA), определив бит переноса i как
  c ₀  = 0,
  c _i  = gi _∨  (p _i  ∧ c _i-1 ), где
  g _i  = a _i  ∧ б _я ,
  п _я  знак равно а _я  ⊕ б _я и
  s _я  знак равно п _я  ⊕ c _i-1 для я = 1, 2, … n.
  p и g известны как распространение распространения и генерация переноса. Это соответствует тому факту, что перенос c _i либо генерируется a _i и b _i , либо распространяется из предыдущего переноса c _i-1 .

Брент и Кунг дополнительно преобразовали генерацию и распространение переноса, определив ассоциативный оператор ○ , который определяет генерацию и распространение переноса по диапазону битов как
(g ₁ , p ₁ ) ○ (g ₂ , p ₂ ) = (g ₁  ∨ ( п ₁  ∧ г ₂ ), п ₁  ∧ п ₂ ) .

• Они также определили значения G _i и Pi _как генерируемые и распространяемые биты для битов от i до 1, т.е.
  (G ₁ , P ₁ ) = (g ₁ , p ₁ ) для i = 1;
  в противном случае (G _i , P _i ) = (g _i , p _i ) ○ (G _i-1 , P _i-1 ) для i = 2, 3, … n.
  Можно вывести, что G _i в функции эквивалентен c _i . Также (G _n , P _n ) можно нерекурсивно записать как = (g _n , p _n ) ○ (g _n-1 , p _n-1 ) ○ … ○ (g ₁ , p ₁ ) .

Воспользовавшись ассоциативностью оператора ○ , (Gn _, Pn ₎ можно вычислить древовидным способом.

Конструкция белых узлов очевидна, поскольку они просто буферизуют значения gi _и pi _, а черные узлы выполняют операцию, определенную оператором ○ , которая аналогична однобитному сумматору.

• Такое древовидное распространение переноса сводит его критический путь к высоте дерева. Поскольку высота дерева переноса может быть максимальной , критический путь параллельного сумматора Брента-Кунга также равен , что лучше, чем производительность обычного сумматора . Древовидная компоновка также уменьшает площадь микросхемы и количество резервных проводов, необходимых в обычных сумматорах на основе CLA. ${\displaystyle O(log_{2}(n))}$ ${\displaystyle O(log_{2}(n))}$ ${\displaystyle O(n)}$

Заключительный этап обработки

Используя распространение переноса и преобразование генерации для отработки сложения и переноса, использованные Брентом и Кунгом, производительность сумматора значительно возрастает, а также приводит к увеличению регулярности. Окончательную сумму можно рассчитать следующим образом: s _i  = p _i  ⊕ G _i-1 , поскольку p _i  = a _i  ⊕ b _i и G _i-1  = c _i-1 .

Маломощный сумматор

Увеличение производительности сумматоров Брента-Кунга объясняется их древовидной структурой распространения переноса, которая также приводит к снижению энергопотребления, поскольку сигналу переноса теперь приходится проходить через меньшее количество каскадов, что приводит к меньшему количеству переключений транзисторов. Кроме того, уменьшение количества проводов и разветвлений также в значительной степени способствует более низкому энергопотреблению, чем у сумматоров CLA. Сумматор Брента-Кунга также может использоваться конвейерным способом, что может еще больше снизить энергопотребление за счет уменьшения глубины комбинаторной логики и стабилизации сбоев. ^[1] На графике показан маломощный сумматор Брента – Кунга. ^[2]

Сравнение с сумматором Когге – Стоуна.

Преимущества

Поскольку для реализации этого типа сумматора требуется меньше модулей, чем для сумматора Когге-Стоуна , сумматор Брента-Кунга построить гораздо проще. Он также содержит гораздо меньше соединений с другими модулями, что также способствует его простоте. ^[3]

Недостатки

Этот тип сумматора имеет большую задержку, ^[3] требуя 2 log ₂ n - 2 уровней логики для вычисления всех битов переноса. (Когге-Стоуну требуется log ₂ n .)

Уравнения

8-битный сумматор Когге-Стоуна, валентность-2:

P00 = A0 исключающее ИЛИ B0 '1dt, S0G00 = A0 И B0 '1dt, C0P10 = A1 исключающее ИЛИ B1 '1dt G10 = A1 И B1 '1dtP20 = A2 исключающее ИЛИ B2 '1dtG20 = A2 И B2 '1dtP30 = A3 исключающее ИЛИ B3 '1dtG30 = A3 И B3 '1dtP40 = A4 исключающее ИЛИ B4 '1dtG40 = A4 И B4 '1dtP50 = A5 исключающее ИЛИ B5 '1dtG50 = A5 И B5 '1dt P60 = A6 исключающее ИЛИ B6 '1dtG60 = A6 И B6 '1dtP70 = A7 исключающее ИЛИ B7 '1dtG70 = A7 И B7 '1dtG11 = G10 ИЛИ P10 И G00 '3dt, C1P21 = P20 И P10 '2dtG21 = G20 ИЛИ P20 И G10 '3dtP31 = P30 И P20 '2dtG31 = G30 ИЛИ P30 И G20 '3dtP41 = P40 И P30 '2dtG41 = G40 ИЛИ P40 И G30 '3dtP51 = P50 И P40 '2dtG51 = G50 ИЛИ P50 И G40 '3dtP61 = P60 И P50 '2dtG61 = G60 ИЛИ P60 И G50 '3dtP71 = P70 И P60 '2dtG71 = G70 ИЛИ P70 И G60 '3dtG22 = G21 ИЛИ P21 И G00 '4dt, C2G32 = G31 ИЛИ P31 И G11 '5dt, C3P42 = P41 И P21 '3dtG42 = G41 ИЛИ P41 И G21 '5dtP52 = P51 И P31 '3dtG52 = G51 ИЛИ P51 И G31 '5dtP62 = P61 И P41 '3dtG62 = G61 ИЛИ P61 И G41 '5dtP72 = P71 И P51 '3dtG72 = G71 ИЛИ P71 И G51 '5dtG43 = G42 ИЛИ P42 И G00 '6dt, C4G53 = G52 ИЛИ P52 И G11 '6dt, C5G63 = G62 ИЛИ P62 И G22 '6dt, C6G73 = G72 ИЛИ P72 И G32 '7dt, C7, CoutS0 = P00 '1dtS1 = P10 исключающее ИЛИ G00 '2dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G22 '5dtS4 = P40 исключающее ИЛИ G32 '6dtS5 = P50 исключающее ИЛИ G43 '7dtS6 = P60 исключающее ИЛИ G53 '7dtS7 = P70 исключающее ИЛИ G63 '7dt

8-битный сумматор Когге-Стоуна, валентность-2,3,4:

P00 = A0 исключающее ИЛИ B0 '1dt, S0G00 = A0 И B0 '1dt, C0P10 = A1 исключающее ИЛИ B1 '1dtG10 = A1 И B1 '1dtP20 = A2 исключающее ИЛИ B2 '1dtG20 = A2 И B2 '1dtP30 = A3 исключающее ИЛИ B3 '1dtG30 = A3 И B3 '1dtP40 = A4 исключающее ИЛИ B4 '1dtG40 = A4 И B4 '1dtP50 = A5 исключающее ИЛИ B5 '1dtG50 = A5 И B5 '1dtP60 = A6 исключающее ИЛИ B6 '1dtG60 = A6 И B6 '1dtP70 = A7 исключающее ИЛИ B7 '1dtG70 = A7 И B7 '1dtG11 = G10 ИЛИ P10 И G00 '3dt, расстояние=2^0=1, валентность-2, C1P21 = P20 И P10 '2dtG21 = G20 ИЛИ P20 И G10 '3dt, расстояние=2^0=1, валентность-2P31 = P30 И P20 '2dtG31 = G30 ИЛИ P30 И G20 '3dt, расстояние=2^0=1, валентность-2P41 = P40 И P30 '2dtG41 = G40 ИЛИ P40 И G30 '3dt, расстояние=2^0=1, валентность-2P51 = P50 И P40 '2dtG51 = G50 ИЛИ P50 И G40 '3dt, расстояние=2^0=1, валентность-2P61 = P60 И P50 '2dtG61 = G60 ИЛИ P60 И G50 '3dt, расстояние=2^0=1, валентность-2P71 = P70 И P60 '2dtG71 = G70 ИЛИ P70 И G60 '3dt, расстояние=2^0=1, валентность-2G22 = G20 ИЛИ_ P20 И G10 ИЛИ_ P20 И P10 И G00 '3dt, расстояние=2^1=2, валентность-3, C2G32 = G30 ИЛИ_ P30 И G20 ИЛИ_ P30 И P20 И G10 ИЛИ_ P30 И P20 И P10 И G00 '3dt, расстояние=2^1=2, валентность-4, C3P42 = P41 AND P21 '3dt, расстояние=2^1=2G42 = G40 ИЛИ_ P40 И G30 ИЛИ_ P40 И P30 И G20 ИЛИ_ P40 И P30 И P20 И G10 '3dt, расстояние=2^1=2, валентность-4P52 = P51 И P31 '3dt, расстояние=2^1=2G52 = G50 ИЛИ_ P50 И G40 ИЛИ_ P50 И P40 И G30 ИЛИ_ P50 И P40 И P30 И G20 '3dt, расстояние=2^1=2, валентность-4P62 = P61 И P41 '3dt, расстояние=2^1=2G62 = G60 ИЛИ_ P60 И G50 ИЛИ_ P60 И P50 И G40 ИЛИ_ P60 И P50 И P40 И G30 '3dt, расстояние=2^1=2, валентность-4P72 = P71 И P51G72 = G70 ИЛИ_ P70 И G60 ИЛИ_ P70 И P60 И G50 ИЛИ_ P70 И P60 И P50 И G40 '3dt, расстояние=2^1=2, валентность-4G43 = G42 ИЛИ P42 И G00 '5dt, расстояние=2^2=4, валентность-2, C4G53 = G52 ИЛИ P52 И G11 '5dt, расстояние=2^2=4, валентность-2, C5G63 = G62 ИЛИ P62 И G22 '5dt, расстояние=2^2=4, валентность-2, C6G73 = G72 ИЛИ P72 И G32 '5dt, расстояние=2^2=4, валентность-2, C7S0 = P00 '1dtS1 = P10 исключающее ИЛИ G00 '2dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G22 '4dtS4 = P40 исключающее ИЛИ G32 '6dtS5 = P50 исключающее ИЛИ G43 '6dtS6 = P60 исключающее ИЛИ G53 '6dtS7 = P70 исключающее ИЛИ G63 '6dt

8-битный сумматор Брента-Кунга, валентность-2:

P00 = A0 исключающее ИЛИ B0 '1dt, S0G00 = A0 И B0 '1dt, C0P10 = A1 исключающее ИЛИ B1 '1dtG10 = A1 И B1 '1dtP20 = A2 исключающее ИЛИ B2 '1dtG20 = A2 И B2 '1dtP30 = A3 исключающее ИЛИ B3 '1dtG30 = A3 И B3 '1dtP40 = A4 исключающее ИЛИ B4 '1dtG40 = A4 И B4 '1dtP50 = A5 исключающее ИЛИ B5 '1dtG50 = A5 И B5 '1dtP60 = A6 исключающее ИЛИ B6 '1dtG60 = A6 И B6 '1dtP70 = A7 исключающее ИЛИ B7 '1dtG70 = A7 И B7 '1dtG11 = G10 ИЛИ P10 И G00 '3dt, C1G21 = G20 ИЛИ P20 И G11 '3dt, C2P31 = P30 И P20 '2dtG31 = G30 ИЛИ P30 И G20 '3dtP51 = P50 И P40 '2dt G51 = G50 ИЛИ P50 И G40 '3dtP71 = P70 И P60 '2dt G71 = G70 ИЛИ P70 И G60 '3dtG32 = G31 ИЛИ P31 И G11 '5dt, C3P72 = P71 И P51 '3dtG72 = G71 ИЛИ P71 И G51 '5dt G53 = G51 ИЛИ P51 И G32 '7dt, C5G73 = G72 ИЛИ P72 И G32 '7dt, C7, CoutG44 = G40 ИЛИ P40 И G32 '7dt, C4G64 = G60 ИЛИ P60 И G53 '9dt, C6S0 = P00 '1dt S1 = P10 исключающее ИЛИ G00 '2dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G21 '4dtS4 = P40 исключающее ИЛИ G32 '6dtS5 = P50 исключающее ИЛИ G44 '8dtS6 = P60 исключающее ИЛИ G53 '8dtS7 = P70 исключающее ИЛИ G64 '10dt

Рекомендации

1. Брент, Ричард Пирс ; Кунг, Сян Дэ (март 1982 г.) [июнь 1979 г.]. «Обычная схема для параллельных сумматоров». Транзакции IEEE на компьютерах . Кафедра компьютерных наук, Университет Карнеги-Меллон, США. С-31 (3): 260–264. дои : 10.1109/TC.1982.1675982. ISSN  0018-9340. S2CID  17348212. CMS-CS-79-131. Архивировано из оригинала 24 сентября 2017 года.
2. Александр, Джонатан (2004). «Советы по проектированию VHDL и методы проектирования с низким энергопотреблением» . Проверено 21 апреля 2018 г.
3. Пойнтер, Роби (14 ноября 2012 г.). «Как складывать цифры (часть 2)». robey.lag.net . Архивировано из оригинала 21 апреля 2018 г. Проверено 21 апреля 2018 г.

дальнейшее чтение

• Рейндерс, Неле; Деэн, Вим (2015). Проектирование энергоэффективных цифровых схем сверхнизкого напряжения . Аналоговые схемы и обработка сигналов (ACSP) (1-е изд.). Чам, Швейцария: Springer International Publishing AG, Швейцария . дои : 10.1007/978-3-319-16136-5. ISBN 978-3-319-16135-8. ISSN  1872-082X. LCCN  2015935431.

Внешние ссылки

• Архивировано 4 февраля 2020 года в Wayback Machine.