جمع کننده برنت-کونگ

**جمع‌کنندهٔ برنت–کونگ (BKA یا BK)** که در سال ۱۹۸۲ پیشنهاد شد، یک طراحی پیشرفتهٔ جمع‌کنندهٔ دودویی است که عمق سطح گیت آن ***O(log<sub>2</sub>(n))*** است.

## معرفی
این جمع‌کننده شکل خاصی از **[[جمع پیشوندی|جمع‌کننده پیشوندی موازی]]** (**Parallel Prefix Adder, PPA**) محسوب می‌شود و از نوع **[[جمع‌کننده با قابلیت پیش‌بینی رقم نقلی|جمع‌کننده با پیش‌بینی حمل]]** (**Carry-Lookahead-Adder, CLA**) است. **ریچارد پیرس برنت** (**[[ریچارد پیرس برنت|Richard Peirce Brent]]**) و **هسینگ تِ کونگ** (Hsiang Te Kung) این طرح را ارائه کردند که ساختار منظم‌تر و تراکم سیم‌کشی کمتری نسبت به **[[:en:Kogge–Stone_adder|جمع‌کننده کاگی-استون]]** (**Kogge–Stone adder, KSA**) دارد و در نتیجه عملکرد بهتری ارائه می‌کند و مساحت تراشهٔ کمتری نیاز دارد. علاوه بر این، جمع‌کنندهٔ برنت-کونگ در مقایسه با جمع‌کننده‌های با **[[جمع‌کننده|انتقال موجی]]** (**Ripple-Carry Adder, RCA**) نیز به مراتب سریع‌تر عمل می‌کند.

جمع‌کننده‌های با انتقال موجی (RCA) در ابتدا اولین نمونه‌های جمع‌کننده‌های چندبیتی بودند که نام خود را از پدیدهٔ موجی انتقال سیگنال حمل (از بیت‌های کم‌ارزش به پرارزش) گرفته‌اند. در این ساختارهای ابتدایی، زمان انجام عمل جمع مستقیماً متناسب با طول بیت‌های ورودی بود؛ اما در جمع‌کننده‌های برنت-کونگ، سیگنال حمل به شکل موازی محاسبه می‌شود و در نتیجه زمان جمع تا حد زیادی کاهش می‌یابد. پژوهش‌های بعدی بر روی جمع‌کننده‌های برنت-کونگ و سایر طرح‌های موازی با هدف کاهش مصرف توان و مساحت تراشه و نیز افزایش سرعت انجام شده است، که این ویژگی‌ها آنها را برای معماری‌های کم‌مصرف مناسب می‌سازد.

جمع‌کنندهٔ برنت-کونگ به عنوان یک جمع‌کننده موازی، با ساختار منظم طراحی شده است تا مساحت تراشه و دشواری فرآیند ساخت را به حداقل برساند. جمع دو عدد n-بیتی را می‌توان در زمان ***O(log<sub>2</sub>​n)*** انجام داد و مساحت تراشه نیز در مرتبه ***O(nlog<sub>2</sub>***​***(n))*** خواهد بود؛ بنابراین این جمع‌کننده در شرایطی که محدودیت مساحت و نیاز به حداکثر عملکرد وجود دارد، انتخاب مناسبی است. ساختار تقارن و منظم آن هزینهٔ تولید را به‌طور مؤثری کاهش می‌دهد و امکان استفاده از آن در معماری‌های **خط لوله** (Pipeline) را فراهم می‌آورد. در جمع‌کننده‌های موازی، مسیر بحرانی توسط محاسبهٔ سیگنال حمل از بیت با کم‌ترین ارزش (LSB) به بیت با بیش‌ترین ارزش (MSB) تعیین می‌شود؛ بنابراین طراحی‌های برنت-کونگ تلاش می‌کنند مسیر بحرانی این انتقال حمل تا MSB را به حداقل برسانند.

## مدل پایه
به‌طور کلی، اکثر جمع‌کننده‌ها از سیگنال ورودی حمل و بیت‌های متناظر دو عدد A و B برای به‌دست آوردن بیت جمع و سیگنال خروجی حمل استفاده می‌کنند. در جمع‌کننده‌های با انتقال موجی (ripple-carry)، زمان لازم برای انتقال سیگنال حمل تا بخش MSB در مرتبهٔ O(n) است.

* فرض کنیم A = a_na_{n-1}...a_1  و B=b_nb_{n-1}...b_1  اعداد دودویی n-بیتی باشند. 
* مجموع حاصل S=s_{n+1}s_n...s_1​ و سیگنال‌های حمل تولید شده در هر مرحله C = c_nc_{n-1}...c_1 باشند (که c0​ سیگنال حمل ورودی در ابتدا است).
* **جمع‌کنندهٔ موجی (RCA):** برای این جمع‌کننده داریم c0​=0. همچنین برای هر i=1,2,…,n، معادلات زیر برقرارند:

c_i = g_i\lor (a_i\land c_{i-1}) \lor (b_i \land c_{i-1})

s_i = a_i \oplus b_i \oplus c_{i-1} \ for \ i = 1, 2, 3, ... , n 

درنتیجه s_{n+1} = c_n 

در اینجا g_i = a_i \land bi ​ و p_i=a_i\oplus b_i  معرفی می‌شوند که g_i
 ​ را **بیت تولید حمل** و p_i ​ را **بیت گسترش حمل** می‌نامیم. (برای مثال s_{n+1}=c_n .)

* **تبدیل به CLA:** می‌توان ساختار بالا را به یک جمع‌کننده پیش‌بینی حمل (CLA) تبدیل کرد. به این ترتیب تعریف می‌کنیم c_0 = 0  و برای i=1,2,…,n:

c_i = g_i \lor (p_i\land c_{i-1})  ,که در آن g_i = a_i \land b_i\ ,\ p_i=a_i\oplus b_i\ , \ s_i=p_i\oplus c_{i-1}  .

در این معادلات g_i ​ و p_i ​ مشخص می‌کنند که سیگنال حمل c_i ​ یا از ترکیب a_i ​ و b_i ​ تولید می‌شود، یا از سیگنال حمل قبلی c_{i-1}  گسترش می‌یابد.

برنت و کونگ یک عملگر دوتایی ∘ را برای ترکیب بیت‌های تولید و گسترش تعریف کردند:

(g_1,p_1) \circ (g_2, p_2) = (g_2 \lor (p_2\land g_1), p_1 \land p_2

سپس مقادیرG_i وP_i را به صورت تجمعی از بیت‌های اول تا i-ام تعریف کردند: برای ,i=1 (G_i, P_i) = (g_i, p_i) و برای i > 1 داریم (G_i,P_i)=(g_i,p_i) \circ (G_{i-1}, P_{i-1}). می‌توان نشان داد که مقدار G_i​ دقیقاً برابر سیگنال حمل c_i​ است. همچنین (G_n,P_n) را می‌توان بدون بازگشت (non-recursively) به صورت (G_n,P_n)=(g_n,p_n)\circ (g_{n-1},p_{n-1})...\circ (g_1,p_1) نوشت.

## نمایش ساختار درختی برنت–کونگ (ASCII)
نمودار ساده‌شدهٔ درخت پیشوندی:
             (G8,P8)
             \     /
       (g8,p8)     (G4,P4)
                   \    /
              (g4,p4)  (G2,P2)
                        \   /
                  (G1,P1)   (g2,p2)
این ساختار یک «درخت کم‌چگالی» است که در آن تعداد یال‌ها کمینه شده تا فشار سیم‌کشی کاهش یابد.

## جدول مقایسهٔ جمع‌کننده‌های پیشوندی

## مرحلهٔ پردازش نهایی
با استفاده از تبدیلات توصیف شده برای تولید و انتقال سیگنال حمل در جمع‌کنندهٔ برنت-کونگ، عملکرد جمع‌کننده به‌طور محسوسی افزایش یافته و منظم‌تر شده است. جمع نهایی بیت‌ها به صورت زیر محاسبه می‌شود:

s_i=p_i\oplus G_{i-1} زیرا a_i \oplus b_i = p_i و c_{i-1}=G_{i-1}

## جمع کننده کم مصرف
در جمع‌کننده‌های برنت-کونگ، افزایش عملکرد ناشی از ساختار درختی انتقال حامل است که به کاهش مصرف توان منجر می‌شود، زیرا سیگنال حمل از مراحل کمتری عبور می‌کند و سوئیچینگ ترانزیستورها کاهش می‌یابد. همچنین کاهش تعداد اتصالات و **بار (Fan-out)** موجب مصرف توان بسیار کمتر نسبت به جمع‌کننده‌های پیش‌بینی حمل (CLA) می‌شود. یک جمع‌کنندهٔ برنت-کونگ را می‌توان به صورت خط لوله پیاده‌سازی کرد که با کاهش عمق مدار ترکیبی و تثبیت خطاهای گذرا، باز هم مصرف توان را کاهش می‌دهد. به‌عنوان مثال، در منابعی نمودار مصرف توان برای جمع‌کنندهٔ برنت-کونگ کم‌مصرف گزارش شده است.
## منابع

## مطالعه بیشتر
* 

* 

## پیوند به بیرون
* 

## رده‌ها
رده:جمع‌کننده‌ها (الکترونیک)