Схема ускоренного переноса

Схе́ма уско́ренного перено́са — комбинационная логическая схема, входит в арифметико-логическое устройство большинства современных ЭВМ микропроцессоров и микроконтроллеров.

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

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

Принцип работы

Термины:
Carry Lookahead Unit (CLU) — схема ускоренного переноса.
Carry Look-ahead Adder (CLA) — схема сумматора с ускоренным переносом.
PG — групповой сигнал распространения переноса.
GG — групповой сигнал генерации переноса.

При использовании схемы ускоренного переноса (LCU) каждый одинарный разряд сумматора вырабатывает сигнал генерации переноса (<math>g_0</math>) и сигнал распространения переноса (<math>p_0</math>).

4-х битная схема

Одинарные разряды сумматора объединяются в группы по четыре одинарных разряда в каждой группе. Схема ускоренного переноса вырабатывает сигналы переноса <math>C_1, C_2, C_3, C_4,</math> групповой сигнал генерации переноса (GG) и групповой сигнал распространения переноса (PG).

Логическое выражение для переноса в одном разряде:

<math>C_{i+1} = a_i \cdot b_i + (a_i \oplus b_i)C_i = G_i + P_i \cdot C_i</math>, где

<math>G_i = a_i \cdot b_i</math>

<math>P_i = a_i \oplus b_i</math>

Здесь точка (<math>\cdot</math>) означает логическое И (AND), знак сложения (+) - логическое ИЛИ (OR) и символ <math>\oplus</math> сложение по модулю 2 ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)

Для переносов в четырёх разрядах:

<math>C_1 = G_0 + P_0 \cdot C_0</math>

<math>C_2 = G_1 + P_1 \cdot C_1</math>

<math>C_3 = G_2 + P_2 \cdot C_2</math>

<math>C_4 = G_3 + P_3 \cdot C_3</math>

Подставив <math>C_1</math> в <math>C_2</math>, затем <math>C_2</math> в <math>C_3</math>, затем <math>C_3</math> в <math>C_4</math> получим окончательные выражения:

<math>C_1 = G_0 + P_0 \cdot C_0</math>

<math>C_2 = G_1 + G_0 \cdot P_1 + C_0 \cdot P_0 \cdot P_1</math>

<math>C_3 = G_2 + G_1 \cdot P_2 + G_0 \cdot P_1 \cdot P_2 + C_0 \cdot P_0 \cdot P_1 \cdot P_2</math>

<math>C_4 = G_3 + G_2 \cdot P_3 + G_1 \cdot P_2 \cdot P_3 + G_0 \cdot P_1 \cdot P_2 \cdot P_3 + C_0 \cdot P_0 \cdot P_1 \cdot P_2 \cdot P_3</math>

4-х битная схема ускоренного переноса выпускается в интегральном исполнении, например: SN74182 (ТТЛ), MC10179 (ЭСЛ) и MC14582, 564ИП4 (выполненная по технологии КМОП).

16-ти битная схема

16-разрядный сумматор может быть создан путём объединения четырёх 4-битных сумматоров с четырьмя схемами ускоренного переноса (4-bit CLA Adder), дополненных пятой схемой ускоренного переноса, которая используется для обработки групповых сигналов генерации переноса — GG и распространения переноса — PG.

Принимаемые на входе сигналы распространения переноса (<math>PG</math>) и генерируемые каждой их четырёх схем сигналы (GG). Затем, схема ускоренного переноса генерирует соответствующие сигналы.

Предположим, что <math>P_i</math> это сигналы PG и <math>G_i</math> это GG из i^й, то выходные биты устанавливаются следующим образом:

<math>C_{4} = G_0 + P_0 \cdot C_0</math>

<math>C_{8} = G_{4} + P_{4} \cdot C_{4}</math>

<math>C_{12} = G_{8} + P_{8} \cdot C_{8}</math>

<math>C_{16} = G_{12} + P_{12} \cdot C_{12}</math>

Подставляя <math>C_{4}</math> сперва в <math>C_{8}</math>, затем <math>C_{8}</math> в <math>C_{12}</math>, затем <math>C_{12}</math> в <math>C_{16}</math> получаем следующее выражение:

<math>C_{4} = G_0 + P_0 \cdot C_0</math>

<math>C_{8} = G_4 + G_0 \cdot P_4 + C_0 \cdot P_0 \cdot P_4</math>

<math>C_{12} = G_8 + G_4 \cdot P_8 + G_0 \cdot P_4 \cdot P_8 + C_0 \cdot P_0 \cdot P_4 \cdot P_8</math>

<math>C_{16} = G_{12} + G_8 \cdot P_{12} + G_4 \cdot P_8 \cdot P_{12} + G_0 \cdot P_4 \cdot P_8 \cdot P_{12} + C_0 \cdot P_0 \cdot P_4 \cdot P_8 \cdot P_{12}</math>

<math>C_{4}</math> соответственно генерирует бит переноса на вход второй схемы; <math>C_{8}</math> на вход третьей; <math>C{12}</math> на вход четвёртой; и <math>C_{16}</math> генерирует бит переполнения.

Кроме того, можно указать сигналы распространения переноса и генерации переноса для схемы ускоренного переноса:

<math>P_{LCU} = P_0 \cdot P_4 \cdot P_8 \cdot P_{12}</math>

<math>G_{LCU} = G_{12} + G_8 \cdot P_{12} + G_4 \cdot P_{12} \cdot P_8 + G_0 \cdot P_{12} \cdot P_8 \cdot P_4</math>

64-битная схема

Объединив четыре схемы сумматора и схему ускоренного переноса вместе, получим 16-битный сумматор. Четыре таких блока могут быть объединены в 64-разрядный сумматор. Дополнительные схемы ускоренного переноса (второго уровня) необходимы, чтобы принимать сигналы распространения переноса (<math>P_{LCU}</math>) и сигналы генерации переноса(<math>G_{LCU}</math>) от каждой схемы сумматора.

Достоинства и недостатки

Достоинства:

• Высокая скорость работы.

Недостатки:

• Бо́льшие затраты оборудования

Схемы формирования параллельного переноса имеют существенное преимущество в скорости перед схемами последовательного переноса.

См. также

• Схема последовательного переноса
• Схема условного переноса
• Сумматор

Литература

• Титце У., Шенк К. Глава 19. Комбинационные логические схемы. 19.5 Сумматоры. 19.5.3. Сумматоры с параллельным переносом // [www.ozon.ru/context/detail/id/3932317/ Полупроводниковая схемотехника] = Halbleiter-Schaltungstechnik / Пер. с нем. Г. Карабашев. — Додэка XXI, 2008. — 1784 с. — (Схемотехника). — 3000 экз. — ISBN 978-5-94120-200-3, 978-5-94120-201-0, 3-540-42849-6.

Источники

• Воробьев Н. Сумматоры. Определения, классификация, уравнения, структуры и применение. Часть 2 www.chipnews.ru/html.cgi/arhiv/00_03/stat-34.htm
• [course-cst.narod.ru/lec_page21.html Сумматоры. Повышение быстродействия параллельных сумматоров. Принцип построения БУП (блок ускоренного переноса).]
• [www.kursach37.com/uch_cifr_t4_43.html Цифровая электроника. Курс лекций. Тема 4. Комбинационные цифровые устройства. 4-3. Сумматоры.]
• [phg.su/basis2/X133.HTM Сумматор с ускоренным переносом.]
• [rain.ifmo.ru/cat/view.php/theory/math/summators-2004 Дискретная математика: Алгоритмы. Многоразрядный сумматор.]
• [bigor.bmstu.ru/?cnt/?doc=200_Elbase/sch065.mod/?cou=Default/145_circuits.cou Сумматоры. Комбинационный сумматор с параллельным переносом.]

Отрывок, характеризующий Схема ускоренного переноса

– Ох! достанется гусарам! – говорил Несвицкий, – не дальше картечного выстрела теперь.
– Напрасно он так много людей повел, – сказал свитский офицер.
– И в самом деле, – сказал Несвицкий. – Тут бы двух молодцов послать, всё равно бы.
– Ах, ваше сиятельство, – вмешался Жерков, не спуская глаз с гусар, но всё с своею наивною манерой, из за которой нельзя было догадаться, серьезно ли, что он говорит, или нет. – Ах, ваше сиятельство! Как вы судите! Двух человек послать, а нам то кто же Владимира с бантом даст? А так то, хоть и поколотят, да можно эскадрон представить и самому бантик получить. Наш Богданыч порядки знает.
– Ну, – сказал свитский офицер, – это картечь!
Он показывал на французские орудия, которые снимались с передков и поспешно отъезжали.
На французской стороне, в тех группах, где были орудия, показался дымок, другой, третий, почти в одно время, и в ту минуту, как долетел звук первого выстрела, показался четвертый. Два звука, один за другим, и третий.
– О, ох! – охнул Несвицкий, как будто от жгучей боли, хватая за руку свитского офицера. – Посмотрите, упал один, упал, упал!
– Два, кажется?
– Был бы я царь, никогда бы не воевал, – сказал Несвицкий, отворачиваясь.
Французские орудия опять поспешно заряжали. Пехота в синих капотах бегом двинулась к мосту. Опять, но в разных промежутках, показались дымки, и защелкала и затрещала картечь по мосту. Но в этот раз Несвицкий не мог видеть того, что делалось на мосту. С моста поднялся густой дым. Гусары успели зажечь мост, и французские батареи стреляли по ним уже не для того, чтобы помешать, а для того, что орудия были наведены и было по ком стрелять.
– Французы успели сделать три картечные выстрела, прежде чем гусары вернулись к коноводам. Два залпа были сделаны неверно, и картечь всю перенесло, но зато последний выстрел попал в середину кучки гусар и повалил троих.
Ростов, озабоченный своими отношениями к Богданычу, остановился на мосту, не зная, что ему делать. Рубить (как он всегда воображал себе сражение) было некого, помогать в зажжении моста он тоже не мог, потому что не взял с собою, как другие солдаты, жгута соломы. Он стоял и оглядывался, как вдруг затрещало по мосту будто рассыпанные орехи, и один из гусар, ближе всех бывший от него, со стоном упал на перилы. Ростов побежал к нему вместе с другими. Опять закричал кто то: «Носилки!». Гусара подхватили четыре человека и стали поднимать.
– Оооо!… Бросьте, ради Христа, – закричал раненый; но его всё таки подняли и положили.
Николай Ростов отвернулся и, как будто отыскивая чего то, стал смотреть на даль, на воду Дуная, на небо, на солнце. Как хорошо показалось небо, как голубо, спокойно и глубоко! Как ярко и торжественно опускающееся солнце! Как ласково глянцовито блестела вода в далеком Дунае! И еще лучше были далекие, голубеющие за Дунаем горы, монастырь, таинственные ущелья, залитые до макуш туманом сосновые леса… там тихо, счастливо… «Ничего, ничего бы я не желал, ничего бы не желал, ежели бы я только был там, – думал Ростов. – Во мне одном и в этом солнце так много счастия, а тут… стоны, страдания, страх и эта неясность, эта поспешность… Вот опять кричат что то, и опять все побежали куда то назад, и я бегу с ними, и вот она, вот она, смерть, надо мной, вокруг меня… Мгновенье – и я никогда уже не увижу этого солнца, этой воды, этого ущелья»…
В эту минуту солнце стало скрываться за тучами; впереди Ростова показались другие носилки. И страх смерти и носилок, и любовь к солнцу и жизни – всё слилось в одно болезненно тревожное впечатление.
«Господи Боже! Тот, Кто там в этом небе, спаси, прости и защити меня!» прошептал про себя Ростов.
Гусары подбежали к коноводам, голоса стали громче и спокойнее, носилки скрылись из глаз.
– Что, бг'ат, понюхал пог'оху?… – прокричал ему над ухом голос Васьки Денисова.
«Всё кончилось; но я трус, да, я трус», подумал Ростов и, тяжело вздыхая, взял из рук коновода своего отставившего ногу Грачика и стал садиться.
– Что это было, картечь? – спросил он у Денисова.
– Да еще какая! – прокричал Денисов. – Молодцами г'аботали! А г'абота сквег'ная! Атака – любезное дело, г'убай в песи, а тут, чог'т знает что, бьют как в мишень.
И Денисов отъехал к остановившейся недалеко от Ростова группе: полкового командира, Несвицкого, Жеркова и свитского офицера.
«Однако, кажется, никто не заметил», думал про себя Ростов. И действительно, никто ничего не заметил, потому что каждому было знакомо то чувство, которое испытал в первый раз необстреленный юнкер.
– Вот вам реляция и будет, – сказал Жерков, – глядишь, и меня в подпоручики произведут.
– Доложите князу, что я мост зажигал, – сказал полковник торжественно и весело.
– А коли про потерю спросят?
– Пустячок! – пробасил полковник, – два гусара ранено, и один наповал , – сказал он с видимою радостью, не в силах удержаться от счастливой улыбки, звучно отрубая красивое слово наповал .


Преследуемая стотысячною французскою армией под начальством Бонапарта, встречаемая враждебно расположенными жителями, не доверяя более своим союзникам, испытывая недостаток продовольствия и принужденная действовать вне всех предвидимых условий войны, русская тридцатипятитысячная армия, под начальством Кутузова, поспешно отступала вниз по Дунаю, останавливаясь там, где она бывала настигнута неприятелем, и отбиваясь ариергардными делами, лишь насколько это было нужно для того, чтоб отступать, не теряя тяжестей. Были дела при Ламбахе, Амштетене и Мельке; но, несмотря на храбрость и стойкость, признаваемую самим неприятелем, с которою дрались русские, последствием этих дел было только еще быстрейшее отступление. Австрийские войска, избежавшие плена под Ульмом и присоединившиеся к Кутузову у Браунау, отделились теперь от русской армии, и Кутузов был предоставлен только своим слабым, истощенным силам. Защищать более Вену нельзя было и думать. Вместо наступательной, глубоко обдуманной, по законам новой науки – стратегии, войны, план которой был передан Кутузову в его бытность в Вене австрийским гофкригсратом, единственная, почти недостижимая цель, представлявшаяся теперь Кутузову, состояла в том, чтобы, не погубив армии подобно Маку под Ульмом, соединиться с войсками, шедшими из России.