جامع الحفظ بالترحيل

جامع حفظ الحمل ^{[ 1 ] [ 2 ] [ nb 1 ]} هو نوع من الجامعات الرقمية ، يُستخدم لحساب مجموع ثلاثة أعداد ثنائية أو أكثر بكفاءة . يختلف عن الجامعات الرقمية الأخرى في أنه يُخرج عددين (أو أكثر)، ويمكن الحصول على ناتج المجموع الأصلي بجمع هذه الأعداد. يُستخدم جامع حفظ الحمل عادةً في مُضاعِف ثنائي، لأن المُضاعِف الثنائي يتضمن جمع أكثر من عددين ثنائيين بعد عملية الضرب. عادةً ما يكون الجامع الكبير المُنفَّذ باستخدام هذه التقنية أسرع بكثير من الجمع التقليدي لهذه الأعداد.

ضع في اعتبارك المجموع:

 12345678 +87654322 = 100000000

باستخدام العمليات الحسابية الأساسية، نحسب من اليمين إلى اليسار: "8 + 2 = 0، نحمل 1"، "7 + 2 + 1 = 0، نحمل 1"، "6 + 3 + 1 = 0، نحمل 1"، وهكذا حتى نهاية المجموع. مع أننا نعرف الرقم الأخير من الناتج مباشرةً، إلا أننا لا نستطيع معرفة الرقم الأول إلا بعد المرور على كل رقم في العملية الحسابية، ونقل الرقم الزائد من كل رقم إلى الرقم الذي على يساره. لذا، فإن جمع عددين مكونين من n رقمًا يستغرق وقتًا يتناسب مع n ، حتى لو كانت الآلة التي نستخدمها قادرة على إجراء العديد من العمليات الحسابية في وقت واحد.

من الناحية الإلكترونية، وباستخدام البتات، يعني هذا أنه حتى لو كان لدينا n من دوائر الجمع أحادية البت، فلا يزال يتعين علينا تخصيص وقت يتناسب مع n للسماح لعملية الحمل المحتملة بالانتشار من أحد طرفي العدد إلى الطرف الآخر. إلى أن نفعل ذلك،

1. لا نعرف نتيجة عملية الجمع.
2. لا نعرف ما إذا كانت نتيجة الجمع أكبر أو أصغر من رقم معين (على سبيل المثال، لا نعرف ما إذا كانت موجبة أم سالبة).

يمكن لجامع التنبؤ بالحمل تقليل التأخير. من حيث المبدأ، يمكن تقليل التأخير بحيث يتناسب مع لوغاريتم n ، ولكن بالنسبة للأعداد الكبيرة، لا ينطبق هذا، لأنه حتى مع تطبيق التنبؤ بالحمل، تزداد المسافات التي تقطعها الإشارات على الشريحة بما يتناسب مع n ، وتزداد تأخيرات الانتشار بنفس المعدل. بمجرد الوصول إلى أحجام الأعداد من 512 بت إلى 2048 بت المطلوبة في التشفير بالمفتاح العام ، يصبح التنبؤ بالحمل غير ذي فائدة كبيرة.

إن فكرة تأجيل حل الحمل حتى النهاية، أو حفظ عمليات الحمل، تعود إلى جون فون نيومان . ^{[ 3 ]}

لا يمكن أن يتجاوز مجموع رقمين الرقم 1، كما لا يمكن أن يتجاوز مجموع رقمين مضافًا إليهما الرقم 1 الرقم 1. على سبيل المثال، في النظام العشري،${\displaystyle 9+9=18}$، والتي تحمل الرقم 1؛${\displaystyle 9+9+1=19}$، والذي يحمل أيضًا الرقم 1. عند جمع ثلاثة أرقام، يمكننا جمع الرقمين الأولين والحصول على المجموع وأرقام الحمل؛ ثم نجمع المجموع وأرقام الحمل مع الرقم الثالث ونحصل على المجموع وأرقام الحمل. في النظام الثنائي، الأرقام الوحيدة هي الصفر والواحد، وبالتالي${\displaystyle 0+0=0}$،${\displaystyle 0+1=1}$، و${\displaystyle 1+1=0}$مع وجود بتة حمل 1. إضافة بتة الحمل يمكن أن تعطي، على الأكثر،${\displaystyle 1+1+1=1}$بوجود 1 محمول، يصبح الجمع الثلاثي ممكناً. ولهذا السبب، يمكن أيضاً جمع الأرقام الثلاثة الأولى والحصول على المجموع والحمل؛ أما بالنسبة للأرقام اللاحقة، فيُعتبر المجموع والحمل حدّين، ويُضاف الرقم التالي إليهما.

فيما يلي مثال على مجموع ثنائي لثلاثة أعداد ثنائية طويلة:

 1011 1010 1010 1101 1111 0000 0000 1101 (أ) + 1101 1110 1010 1101 1011 1110 1110 1111 (ب) + 0001 0010 1011 0111 0101 0011 0101 0010 (ج)

الطريقة المباشرة هي حساب (أ + ب) أولاً، ثم حساب ((أ + ب) + ج). تعمل حسابات حفظ الحمل عن طريق التخلي عن أي نوع من أنواع نقل الحمل. وهي تحسب المجموع رقمًا برقم، كما يلي:

 1011 1010 1010 1101 1111 0000 0000 1101 (أ) + 1101 1110 1010 1101 1011 1110 1110 1111 (ب) + 0001 0010 1011 0111 0101 0011 0101 0010 (ج) = 2113 2130 3031 2313 2223 1121 1211 2222

الترميز غير تقليدي، لكن النتيجة لا تزال واضحة: Σ 2 ⁱ d _i . إذا افترضنا أن الأعداد الثلاثة هي a و b و c، فسيتم وصف النتيجة هنا على أنها مجموع عددين ثنائيين، حيث العدد الأول، S، هو ببساطة المجموع الناتج عن جمع الأرقام (بدون أي نقل للحمل)، أي S _i = a _i ⊕ b _i ⊕ c _i ، والعدد الثاني، C، يتكون من عمليات الحمل من المجاميع الفردية السابقة، أي C _i+1 = (a _i b _i ) + (b _i c _i ) + (c _i a _i )  .

 0111 0110 1011 0111 0001 1101 1011 0000 و 1 0011 0101 0101 1011 1110 0100 1001 1110

الآن يمكن إرسال هذين الرقمين إلى جامع ذي خاصية نشر الحمل والذي سيخرج النتيجة.

كان هذا مفيدًا للغاية من منظور زمن التأخير (زمن الحساب). فلو جمعتَ هذه الأرقام الثلاثة بالطرق التقليدية، لاحتجتَ إلى تأخيرين في عملية الجمع باستخدام تقنية نقل الحمل للوصول إلى الإجابة. أما باستخدام تقنية حفظ الحمل، فستحتاج فقط إلى تأخير واحد في عملية الجمع باستخدام تقنية نقل الحمل وتأخير واحد في عملية الجمع الكاملة (وهو أقل بكثير من تأخير عملية نقل الحمل). ولذلك، فإن خوارزميات حفظ الحمل عادةً ما تكون سريعة جدًا.

بافتراض أن لدينا خانتين لكل رقم، يمكننا استخدام تمثيل ثنائي زائد ، حيث نخزن القيم 0 أو 1 أو 2 أو 3 في كل خانة. من الواضح إذن أنه يمكن إضافة رقم ثنائي آخر إلى نتيجة عملية الحفظ دون تجاوز سعة التخزين، ولكن ماذا بعد ذلك؟

يكمن سر النجاح في أننا نضيف ثلاث بتات في لحظة كل عملية جمع جزئي:

• 0 أو 1، من الرقم الذي نضيفه.
• 0 إذا كان الرقم في متجرنا هو 0 أو 2، أو 1 إذا كان 1 أو 3.
• 0 إذا كان الرقم الموجود على يمينه 0 أو 1، أو 1 إذا كان 2 أو 3.

بمعنى آخر، نأخذ رقمًا من خانة الحمل على يميننا، ونمرر رقمًا آخر إلى يسارنا، تمامًا كما في الجمع التقليدي؛ لكن رقم الحمل الذي نمرره إلى اليسار هو نتيجة العملية الحسابية السابقة وليس الحالية. في كل دورة ساعة، لا يتحرك رقم الحمل إلا خطوة واحدة، وليس n خطوة كما في الجمع التقليدي.

لأن الإشارات لا تحتاج إلى التحرك لمسافات طويلة، يمكن للساعة أن تدق بشكل أسرع بكثير.

لا تزال هناك حاجة لتحويل النتيجة إلى النظام الثنائي في نهاية العملية الحسابية، وهو ما يعني ببساطة السماح للأعداد الحاملة بالمرور عبر العدد بالكامل كما هو الحال في الجامع التقليدي. ولكن إذا أجرينا 512 عملية جمع أثناء عملية ضرب عددين (512 بت)، فإن تكلفة هذا التحويل النهائي تُقسّم فعليًا على عمليات الجمع الـ 512، بحيث تُشكّل كل عملية جمع 1/512 من تكلفة عملية الجمع "التقليدية" النهائية.

في كل مرحلة من مراحل عملية الجمع مع الاحتفاظ بالأموال،

1. نعرف نتيجة الجمع على الفور.
2. ما زلنا لا نعرف ما إذا كانت نتيجة الجمع أكبر أو أصغر من رقم معين (على سبيل المثال، لا نعرف ما إذا كانت موجبة أم سالبة).

تُعدّ هذه النقطة الأخيرة عيبًا عند استخدام دوائر الجمع ذات خاصية الاحتفاظ بالحمل لتنفيذ الضرب المعياري (الضرب متبوعًا بالقسمة، مع الاحتفاظ بالباقي فقط). ^{[ 4 ] [ 5 ]} إذا لم نتمكن من معرفة ما إذا كانت النتيجة الوسيطة أكبر أو أصغر من المعيار، فكيف لنا أن نعرف ما إذا كان يجب طرح المعيار؟

يُعدّ ضرب مونتغمري ، الذي يعتمد على الرقم الأخير في النتيجة، أحد الحلول؛ إلا أنه، كما هو الحال في عملية الجمع مع حفظ الحمل، ينطوي على تكلفة ثابتة، لذا فإن سلسلة من عمليات ضرب مونتغمري توفر الوقت، بينما لا توفر عملية واحدة ذلك. ولحسن الحظ، فإن عملية الأسس، التي هي في جوهرها سلسلة من عمليات الضرب، هي العملية الأكثر شيوعًا في التشفير بالمفتاح العام.

يُتيح تحليل الأخطاء الدقيق ^{[ 6 ]} إمكانية اختيار طرح المعامل حتى وإن لم نكن متأكدين تمامًا من أن ناتج الجمع كبير بما يكفي لتبرير الطرح. ولنجاح هذه الطريقة، يجب أن يكون تصميم الدائرة قادرًا على جمع -2، -1، 0، +1، أو +2 مضروبًا في المعامل. وتكمن ميزة هذه الطريقة على ضرب مونتغمري في عدم وجود تكلفة إضافية ثابتة مرتبطة بكل سلسلة من عمليات الضرب.

تتكون وحدة الجمع والحفظ من n جامعًا كاملًا ، يحسب كل منها مجموعًا واحدًا وبت حمل واحد بناءً على البتات المقابلة للأرقام المدخلة الثلاثة فقط. وبإعطاء الأرقام الثلاثة المكونة من n بت a و b و c ، فإنها تنتج مجموعًا جزئيًا ps وبت إزاحة وحمل sc .

${\displaystyle ps_{i}=a_{i}\oplus b_{i}\oplus c_{i},}$

${\displaystyle sc_{i}=(a_{i}\wedge b_{i})\vee (a_{i}\wedge c_{i})\vee (b_{i}\wedge c_{i}).}$

ويمكن حساب المجموع الكلي من خلال:

1. إزاحة تسلسل الحمل sc إلى اليسار بمقدار خانة واحدة.
2. إضافة 0 إلى بداية ( البت الأكثر أهمية ) سلسلة المجموع الجزئي ps .
3. استخدام جامع الحمل المتموج لجمع هذين الاثنين معًا وإنتاج قيمة ( n + 1) بت الناتجة.

• شجرة والاس

• سافارد، جون جي جي (2018) [2006]. "تقنيات حسابية متقدمة" . كوادريبلوك . مؤرشف من الأصل بتاريخ 3 يوليو 2018. تم الاطلاع عليه بتاريخ 16 يوليو 2018 .