stringtranslate.com

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

График генератора переноса 4-битного сумматора Когге – Стоуна с нулевым переносом, основание-2, валентность-2.

В вычислениях сумматор Когге-Стоуна ( KSA или KS ) представляет собой параллельную префиксную форму сумматора с упреждающим переносом . Другие параллельные префиксные сумматоры (PPA) включают сумматор Склански (SA), [1] сумматор Брента-Кунга (BKA), [2] сумматор Хана -Карлсона (HCA), [3] [4] самый быстрый из известных вариантов, Сумматор связующего дерева Линча-Шварцлендера (STA), [5] [6] сумматор Ноулза (KNA) [7] и сумматор Бомонта-Смита (BSA). [8]

Сумматор Когге-Стоуна требует больше места для реализации, чем сумматор Брента-Кунга, но имеет меньшее разветвление на каждом этапе, что повышает производительность типичных узлов процесса CMOS. Однако перегрузка проводки часто является проблемой для сумматоров Когге – Стоуна. Конструкция Линча-Шварцландера меньше по размеру, имеет меньшее разветвление и не страдает от перегрузки проводки; однако для использования узел процесса должен поддерживать реализации манчестерской цепи переноса . Общая проблема оптимизации параллельных префиксных сумматоров идентична многоуровневой задаче оптимизации сумматора с переменным размером блока и пропуском переноса , решение которой можно найти в диссертации Томаса Линча 1996 года. [6]

Дизайн

Как и все сумматоры с упреждающим переносом, сумматор Когге-Стоуна внутренне отслеживает «генерацию» и «распространение» битов для диапазонов битов. Мы начинаем с 1-битных диапазонов, где один столбец в сложении генерирует бит переноса, если оба входа равны 1 (логическое И ), и распространяет бит переноса, если ровно один вход равен 1 (логическое исключающее ИЛИ ). Затем соседние диапазоны объединяются для создания битов генерации и распространения для более широких диапазонов.

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

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

Говоря об 1-битных диапазонах, все соседние диапазоны объединяются для получения 2-битных диапазонов. Наименее значащий диапазон обрабатывается особым образом: он объединяется с переносом в сложение и создает только бит генерации, поскольку распространение невозможно. На следующем этапе каждый 2-битный диапазон объединяется с предыдущим 2-битным диапазоном, чтобы получить 4-битный диапазон. Это за исключением трех наименее значимых пролетов. Наименее значимый диапазон уже вычислен, а следующие два объединяются с переносом и ранее вычисленным наименее значимым диапазоном соответственно, создавая генерируемые биты для 3- и 4-битных диапазонов, включая перенос.

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

Поскольку на следующем этапе каждый диапазон объединяется не более чем с двумя другими диапазонами (один более значимый и один менее значимый), разветвление минимально. Однако наблюдается значительная перегрузка проводки; на предпоследнем этапе 64-битного сумматора самая значительная половина объединяемых диапазонов требует отдельной генерации и распространения сигналов из диапазонов на расстоянии 16 бит, что требует 32 горизонтальных проводов через сумматор. Заключительный этап аналогичен; хотя необходимы только биты генерации, для пересечения сумматора требуется 32 из них.

Примеры

Пример 4-битного сумматора Когге – Стоуна показан на схеме. Как показано, каждый вертикальный этап создает бит «распространения» и «генерации». Кульминационные биты генерации ( переносы ) создаются на последнем этапе (по вертикали), и эти биты подвергаются операции XOR с начальным распространением после ввода (красные прямоугольники) для получения битов суммы. Например, первый (наименее значимый) бит суммы вычисляется путем выполнения операции XOR распространения в крайнем правом красном поле («1») с переносом («0»), в результате чего получается «1». Второй бит вычисляется путем выполнения XOR распространения во втором блоке справа («0») с C0 («0»), в результате чего получается «0».

4-битный сумматор Когге-Стоуна, Radix-2, без Cin на Borland Turbo Basic 1.1 :

'Шаг 0P00 = A0 XOR B0 '1dt, S0, dt – время задержкиG00 = A0 И B0 '1dt, C0 P10 = A1 исключающее ИЛИ B1 '1dtG10 = A1 И B1 '1dtP20 = A2 исключающее ИЛИ B2 '1dtG20 = A2 И B2 '1dtP30 = A3 исключающее ИЛИ B3 '1dtG30 = A3 И B3 '1dt'Шаг 1, Расстояние = Основание^(Шаг-1)=2^0=1, валентность-2G11 = G10 ИЛИ (P10 И G00) '3dt, C1P21 = P20 И P10 '2dtG21 = G20 ИЛИ (P20 И G10) '3dtP31 = P30 И P20 '2dtG31 = G30 ИЛИ (P30 И G20) '3dt'Шаг 2, Расстояние = Основание^(Шаг-1)=2^1=2, валентность-2G22 = G21 ИЛИ (P21 И G00) '4dt, C2G32 = G31 ИЛИ (P31 И G11) '5dt, C3'СуммаS0 = P00 '1dtS1 = P10 исключающее ИЛИ G00 '2dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G22 '5dtS4 = G32 '5dt

4-битный сумматор PPA по основанию-4 (валентность-2,3,4) (это 4-битный сумматор CLA по основанию-4 (валентность-2,3,4) и 4-битный сумматор Склански-4 (валентность-2,3) ,4) сумматор и 4-битный сумматор Когге-Стоуна-4 (валентность-2,3,4) и 4-битный сумматор Бомонта-Смита-4 (валентность-2,3,4):

'Шаг 0P00 = 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 '1dt'Шаг 1G11 = G10 ИЛИ_ P10 И G00 '3dt, C1, валентность-2, расстояние-1G21 = G20 ИЛИ_ P20 И G10 ИЛИ_ P20 И P10 И G00 '3dt, C2, валентность-3, расстояние-1,2G31 = G30 ИЛИ_ P30 И G20 ИЛИ_ P30 И P20 И G10 ИЛИ_ P30 И P20 И P10 И G00 '3dt, C3, валентность-4, расстояние-1,2,3'СуммаS0 = P00 '1dtS1 = P10 исключающее ИЛИ G00 '2dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G21 '4dtS4 = G31 '3dt

4-битный сумматор Когге-Стоуна, Radix-2, с Cin:

G0a = A0 И Cin '1dtG0b = B0 И Cin '1dtG0c = A0 И B0 '1dtP00 = A0 исключающее ИЛИ B0 '1dtG00 = G0a ИЛИ G0b ИЛИ G0c '2dt, C0 P10 = A1 исключающее ИЛИ B1 '1dt G10 = A1 И B1 '1dt P20 = A2 исключающее ИЛИ B2 '1dtG20 = A2 И B2 '1dtP30 = A3 исключающее ИЛИ B3 '1dtG30 = A3 И B3 '1dtG11 = G10 ИЛИ P10 И G00 '4dt, C1P21 = P20 И P10 '2dtG21 = G20 ИЛИ P20 И G10 '3dtP31 = P30 И P20 '2dt G31 = G30 ИЛИ P30 И G20 '3dtG22 = G21 ИЛИ P21 И G00 '5dt, C2G32 = G31 ИЛИ P31 И G11 '6dt, C3, CoutS0 = P00 XOR Cin '2dtS1 = P10 исключающее ИЛИ G00 '3dtS2 = P20 исключающее ИЛИ G11 '5dtS3 = P30 исключающее ИЛИ G22 '6dt

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

'---Шаг 0P00 = 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 '1dt'---Шаг 1G11 = 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) '3dt'---Шаг 2G22 = 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) '5dt'---Шаг 3G43 = G42 ИЛИ P42 И G00 '6dt, C4G53 = G52 ИЛИ P52 И G11 '6dt, C5G63 = G62 ИЛИ P62 И G22 '6dt, C6G73 = G72 ИЛИ P72 И G32 '7dt, C7, Cout'---СуммаS0 = P00 '1dtS1 = P10 исключающее ИЛИ G00 '2dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G22 '5dtS4 = P40 исключающее ИЛИ G32 '6dtS5 = P50 исключающее ИЛИ G43 '7dtS6 = P60 исключающее ИЛИ G53 '7dtS7 = P70 исключающее ИЛИ G63 '7dtS8 = G73 '7dt

8-битный сумматор Когге-Стоуна, система счисления-4, валентность-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, C1, валентность-2, расстояние=4^0=1G21 = G20 ИЛИ_ P20 И G10 ИЛИ_ P20 И P10 И G00 '3dt, C2, валентность-3, расстояние-1,2G31 = G30 ИЛИ_ P30 И G20 ИЛИ_ P30 И P20 И G10 ИЛИ_ P30 И P20 И P10 И G00 '3dt, C3, валентность-4, расстояние-1,2,3P41 = P40 И P30 И P20 И P10 '2dt, валентность-4, расстояние-1,2,3G41 = G40 ИЛИ_ P40 И G30 ИЛИ_ P40 И P30 И G20 ИЛИ_ P40 И P30 И P20 И G10 '3dt, валентность-4, расстояние-1,2,3P51 = P50 И P40 И P30 И P20 '2dt, валентность-4, расстояние-1,2,3G51 = G50 ИЛИ_ P50 И G40 ИЛИ_ P50 И P40 И G30 ИЛИ_ P50 И P40 И P30 И G20 '3dt, валентность-4, расстояние-1,2,3P61 = P60 И P50 И P40 И P30 '2dt, валентность-4, расстояние-1,2,3G61 = G60 ИЛИ_ P60 И G50 ИЛИ_ P60 И P50 И G40 ИЛИ_ P60 И P50 И P40 И G30 '3dt, валентность-4, расстояние-1,2,3P71 = P70 И P60 И P50 И P40 '2dt, валентность-4, расстояние-1,2,3G71 = G70 ИЛИ_ P70 И G60 ИЛИ_ P70 И P60 И G50 ИЛИ_ P70 И P60 И P50 И G40 '3dt, валентность-4, расстояние-1,2,3'валентность=2, расстояние=4^1=4G42 = G41 ИЛИ P41 И G00 '5dt, C4G52 = G51 ИЛИ P51 И G11 '5dt, C5G62 = G61 ИЛИ P61 И G21 '5dt, C6 G72 = G71 ИЛИ P71 И G31 '5dt, C7 S0 = P00 '1dtS1 = P10 исключающее ИЛИ G00 '2dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G21 '4dtS4 = P40 исключающее ИЛИ G31 '6dtS5 = P50 исключающее ИЛИ G42 '6dtS6 = P60 исключающее ИЛИ G52 '6dtS7 = P70 исключающее ИЛИ G62 '6dt

8-битный сумматор PPA с валентностью 2,3,4,5,6,7,8 (это 8-битный сумматор CLA с валентностью 2,3,4,5,6,7,8 и 8-битный сумматор Склански с валентностью 2 ,3,4,5,6,7,8 сумматор и 8-битный сумматор Когге-Стоуна с валентностью 2,3,4,5,6,7,8):

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 '1dt'------------------------------------------G11 = G10 ИЛИ P10 И G00 '3dt, C1, валентность-2, расстояние-1G21 = G20 OR_ '3dt, C2, валентность-3, расстояние-1,2 P20 И G10 ИЛИ_ P20 И P10 И G00G31 = G30 OR_ '3dt, C3, валентность-4, расстояние-1,2,3 P30 И G20 ИЛИ_ P30 И P20 И G10 ИЛИ_ P30 И P20 И P10 И G00G41 = G40 OR_ '3dt, C4, валентность-5, расстояние-1,2,3,4 P40 И G30 ИЛИ_ P40 И P30 И G20 ИЛИ_ P40 И P30 И P20 И G10 ИЛИ_ P40 И P30 И P20 И P10 И G00G51 = G50 OR_ '3dt, C5, валентность-6, расстояние-1,2,3,4,5 P50 И G40 ИЛИ_  P50 И P40 И G30 ИЛИ_ P50 И P40 И P30 И G20 ИЛИ_ P50 И P40 И P30 И P20 И G10 ИЛИ_ P50 И P40 И P30 И P20 И P10 И G00G61 = G60 OR_ '3dt, C6, валентность-7, расстояние-1,2,3,4,5,6 P60 И G50 ИЛИ_  P60 И P50 И G40 ИЛИ_ P60 И P50 И P40 И G30 ИЛИ_ P60 И P50 И P40 И P30 И G20 ИЛИ_ P60 И P50 И P40 И P30 И P20 И G10 ИЛИ_ P60 И P50 И P40 И P30 И P20 И P10 И G00G71 = G70 OR_ '3dt, C7, валентность-8, расстояние-1,2,3,4,5,6,7 P70 И G60 ИЛИ_  P70 И P60 И G50 ИЛИ_ P70 И P60 И P50 И G40 ИЛИ_ P70 И P60 И P50 И P40 И G30 ИЛИ_ P70 И P60 И P50 И P40 И P30 И G20 ИЛИ_ P70 И P60 И P50 И P40 И P30 И P20 И G10 ИЛИ_ P70 И P60 И P50 И P40 И P30 И P20 И P10 И G00'--------------------------------------S0 = P00 '1dtS1 = P10 исключающее ИЛИ G00 '2dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G21 '4dtS4 = P40 исключающее ИЛИ G31 '4dtS5 = P50 исключающее ИЛИ G41 '4dtS6 = P60 исключающее ИЛИ G51 '4dtS7 = P70 исключающее ИЛИ G61 '4dt

8-битный сумматор PPA с валентностью 2,3,4,5,6,7,8:

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 '1dtS1 = P10 исключающее ИЛИ G00S2 = P20 XOR G10 ИЛИ P10 AND G00 '4dt, валентность-2, расстояние-1S3 = P30 XOR G20 OR_ '4dt, валентность-3, расстояние-1,2 P20 И G10 ИЛИ_ P20 И P10 И G00S4 = P40 XOR G30 OR_ '4dt, валентность-4, расстояние-1,2,3 P30 И G20 ИЛИ_ P30 И P20 И G10 ИЛИ_ P30 И P20 И P10 И G00S5 = P50 XOR G40 OR_ '4dt, валентность-5, расстояние-1,2,3,4 P40 И G30 ИЛИ_ P40 И P30 И G20 ИЛИ_ P40 И P30 И P20 И G10 ИЛИ_ P40 И P30 И P20 И P10 И G00S6 = P60 XOR G50 OR_ '4dt, валентность-6, расстояние-1,2,3,4,5 P50 И G40 ИЛИ_ P50 И P40 И G30 ИЛИ_ P50 И P40 И P30 И G20 ИЛИ_ P50 И P40 И P30 И P20 И G10 ИЛИ_ P50 И P40 И P30 И P20 И P10 И G00S7 = P70 XOR G60 OR_ '4dt, валентность-7, расстояние-1,2,3,4,5,6 P60 И G50 ИЛИ_ P60 И P50 И G40 ИЛИ_ P60 И P50 И P40 И G30 ИЛИ_ P60 И P50 И P40 И P30 И G20 ИЛИ_ P60 И P50 И P40 И P30 И P20 И G10 ИЛИ_ P60 И P50 И P40 И P30 И P20 И P10 И G00G71 = G70 OR_ '3dt, C7, валентность-8, расстояние-1,2,3,4,5,6,7 P70 И G60 ИЛИ_ P70 И P60 И G50 ИЛИ_ P70 И P60 И P50 И G40 ИЛИ_ P70 И P60 И P50 И P40 И G30 ИЛИ_ P70 И P60 И P50 И P40 И P30 И G20 ИЛИ_ P70 И P60 И P50 И P40 И P30 И P20 И G10 ИЛИ_ P70 И P60 И P50 И P40 И P30 И P20 И P10 И G00

Концепция сумматора Когге-Стоуна была разработана Питером М. Когге и Гарольдом С. Стоуном , которые опубликовали ее в основополагающей статье 1973 года под названием « Параллельный алгоритм для эффективного решения общего класса рекуррентных уравнений» . [9]

Улучшения

Усовершенствования исходной реализации включают увеличение системы счисления и разреженности сумматора. Система счисления сумматора показывает, сколько результатов предыдущего уровня вычислений используется для генерации следующего. В исходной реализации используется система счисления 2, хотя можно создать систему счисления 4 и выше. Это увеличивает мощность и задержку каждой ступени, но уменьшает количество необходимых ступеней. В так называемом разреженном сумматоре Когге-Стоуна ( SKA ) разреженность сумматора означает, сколько бит переноса генерируется деревом переноса. Генерация каждого бита переноса называется разреженностью-1, генерация каждого другого — разреженностью-2, а каждого четвертого — разреженностью-4. Полученные переносы затем используются в качестве входных сигналов переноса для гораздо более коротких сумматоров с пульсирующим переносом или какой-либо другой конструкции сумматора, которая генерирует окончательные биты суммы. Увеличение разреженности уменьшает общий объем необходимых вычислений и может уменьшить перегрузку маршрутизации.

Когге – Каменная гадюка разреженности-4. Пример сумматора Когге – Стоуна с разреженностью-4. Элементы, исключенные из-за разреженности, отмечены прозрачностью.

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

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

P00 = A0 XOR B0 '1dt, S0, dt – тип времени задержки G00 = A0 И B0 '1dt, C0 P10 = A1 исключающее ИЛИ B1 '1dt  G10 = A1 И B1 '1dt P20 = A2 исключающее ИЛИ B2 '1dt G20 = A2 И B2 '1dt  P30 = A3 исключающее ИЛИ B3 '1dt G30 = A3 И B3 '1dt P40 = A4 исключающее ИЛИ B4 '1dt G40 = A4 И B4 '1dt P50 = A5 исключающее ИЛИ B5 '1dt  G50 = A5 И B5 '1dt P60 = A6 исключающее ИЛИ B6 '1dt G60 = A6 И B6 '1dt P70 = A7 исключающее ИЛИ B7 '1dt G70 = A7 И B7 '1dt P80 = A8 исключающее ИЛИ B8 '1dt G80 = A8 И B8 '1dt  P90 = A9 исключающее ИЛИ B9 '1dt  G90 = A9 И B9 '1dtP100 = A10 исключающее ИЛИ B10 '1dtG100 = A10 И B10 '1dtP110 = A11 исключающее ИЛИ B11 '1dtG110 = A11 И B11 '1dt P120 = A12 исключающее ИЛИ B12 '1dtG120 = A12 И B12 '1dtP130 = A13 исключающее ИЛИ B13 '1dtG130 = A13 И B13 '1dtP140 = A14 исключающее ИЛИ B14 '1dt G140 = A14 И B14 '1dtP150 = A15 исключающее ИЛИ B15 '1dtG150 = A15 И B15 '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 '3dtP81 = P80 И P70 '2dt G81 = G80 ИЛИ P80 И G70 '3dtP91 = P90 И P80 '2dtG91 = G90 ИЛИ P90 И G80 '3dtP101 = P100 И P90 '2dtG101 = G100 ИЛИ P100 И G90 '3dtP111 = P110 И P100 '2dt G111 = G110 ИЛИ P110 И G100 '3dtP121 = P120 И P110 '2dtG121 = G120 ИЛИ P120 И G110 '3dtP131 = P130 И P120 '2dtG131 = G130 ИЛИ P130 И G120 '3dtP141 = P140 И P130 '2dtG141 = G140 ИЛИ P140 И G130 '3dtP151 = P150 И P140 '2dtG151 = G150 ИЛИ P150 И G140 '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 '5dtP82 = P81 И P61 '3dtG82 = G81 ИЛИ P81 И G61 '5dtP92 = P91 И P71 '3dtG92 = G91 ИЛИ P91 И G71 '5dtP102 = P101 И P81 '3dtG102 = G101 ИЛИ P101 И G81 '5dtP112 = P111 И P91 '3dt G112 = G111 ИЛИ P111 И G91 '5dtP122 = P121 И P101 '3dtG122 = G121 ИЛИ P121 И G101 '5dtP132 = P131 И P111 '3dtG132 = G131 ИЛИ P131 И G111 '5dtP142 = P141 И P121 '3dtG142 = G141 ИЛИ P141 И G121 '5dtP152 = P151 И P131 '3dtG152 = G151 ИЛИ P151 И G131 '5dtG43 = G42 ИЛИ P42 И G00 '6dt, C4G53 = G52 ИЛИ P52 И G11 '6dt, C5G63 = G62 ИЛИ P62 И G22 '6dt, C6G73 = G72 ИЛИ P72 И G32 '7dt, C7P83 = P82 И P42 '4dtG83 = G82 ИЛИ P82 И G42 '7dtP93 = P92 И P52 '4dtG93 = G92 ИЛИ P92 И G52 '7dtP103 = P102 И P62 '4dtG103 = G102 ИЛИ P102 И G62 '7dtP113 = P112 И P72 '4dtG113 = G112 ИЛИ P112 И G72 '7dtP123 = P122 И P82 '4dt G123 = G122 ИЛИ P122 И G82 '7dtP133 = P132 И P92 '4dtG133 = G132 ИЛИ P132 И G92 '7dtP143 = P142 И P102 '4dtG143 = G142 ИЛИ P142 И G102 '7dtP153 = P152 И P112 '4dtG153 = G152 ИЛИ P152 И G112 '7dtG84 = G83 ИЛИ P83 И G00 '8dt, C8G94 = G93 ИЛИ P93 И G11 '8dt, C9G104 = G103 ИЛИ P103 И G22 '8dt, C10G114 = G113 ИЛИ P113 И G32 '8dt, C11G124 = G123 ИЛИ P123 И G43 '8dt, C12G134 = G133 ИЛИ P133 И G53 '8dt, C13G144 = G143 ИЛИ P143 И G63 '8dt, C14G154 = G153 ИЛИ P153 И G73 '9dt, C15S0 = P00 '1dtS1 = P10 исключающее ИЛИ G00 '2dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G22 '5dtS4 = P40 исключающее ИЛИ G32 '6dtS5 = P50 исключающее ИЛИ G43 '7dtS6 = P60 исключающее ИЛИ G53 '7dtS7 = P70 исключающее ИЛИ G63 '7dtS8 = P80 исключающее ИЛИ G73 '8dtS9 = P90 исключающее ИЛИ G84 '9dtS10 = P100 исключающее ИЛИ G94 '9dtS11 = P110 исключающее ИЛИ G104 '9dtS12 = P120 исключающее ИЛИ G114 '9dtS13 = P130 исключающее ИЛИ G124 '9dtS14 = P140 исключающее ИЛИ G134 '9dtS15 = P150 исключающее ИЛИ G144 '9dt

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

  1. ^ Логика сложения условной суммы. Склански Дж. Транзакция IRE на электронном компьютере. 1960. с.226.
  2. ^ Брент, Ричард Пирс ; Кунг, Сян Те (март 1982 г.). «Обычная схема для параллельных сумматоров» (PDF) . Транзакции IEEE на компьютерах . С-31 (3): 260–264. дои : 10.1109/TC.1982.1675982. ISSN  0018-9340. S2CID  17348212. Архивировано из оригинала 24 сентября 2017 года.
  3. ^ Хан, Тэкдон; Карлсон, Дэвид А.; Левитан, Стивен П. (октябрь 1982 г.). «Разработка СБИС высокоскоростных схем сложения малой площади». Материалы Международной конференции IEEE 1981 года по компьютерному дизайну: СБИС в компьютерах и процессорах . IEEE : 418–422. ISBN 0-81860802-1.
  4. ^ Хан, Тэкдон; Карлсон, Дэвид А. (октябрь 1987 г.). «Быстрые и эффективные по площади сумматоры СБИС». Материалы 8-го симпозиума по компьютерной арифметике . IEEE : 49–56.
  5. ^ Линч, Томас Уокер; Шварцлендер-младший, Эрл Э. (август 1992 г.). «Промежуточное дерево переносит упреждающий сумматор». Транзакции IEEE на компьютерах . 41 (8): 931–939. дои : 10.1109/12.156535.
  6. ^ Аб Линч, Томас Уокер (май 1996 г.). «Двоичные сумматоры» (Диссертация). Техасский университет . Архивировано (PDF) из оригинала 14 апреля 2018 г. Проверено 14 апреля 2018 г.
  7. ^ Семья змей. Саймон Ноулз. Элемент 14, Ацтекский центр, Бристоль, Великобритания.
  8. ^ Проект параллельного префиксного сумматора. Бомонт-Смит А., Ченг-Чью Л. Кафедра электротехники и электроники, Университет Аделаиды, Австралия. 2001 г.
  9. ^ Когге, Питер Майкл ; Стоун, Гарольд С. (август 1973 г.). «Параллельный алгоритм эффективного решения общего класса рекуррентных уравнений». Транзакции IEEE на компьютерах . С-22 (8): 786–793. дои : 10.1109/TC.1973.5009159. S2CID  206619926.

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