التمثيل الثنائي الزائد

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

نظام RBR هو نظام تدوين للقيم المكانية . في هذا النظام، تُمثل الأرقام أزواجًا من البتات، أي أن كل خانة تستخدم زوجًا من البتات. يمكن إيجاد القيمة التي يمثلها الرقم الزائد باستخدام جدول ترجمة. يُبين هذا الجدول القيمة الرياضية لكل زوج ممكن من البتات.

كما هو الحال في التمثيل الثنائي التقليدي، فإن القيمة الصحيحة لتمثيل معين هي مجموع مرجح لقيم الأرقام. يبدأ الوزن من 1 للموضع الأيمن ويزداد بمعامل 2 لكل موضع لاحق. عادةً، يسمح التمثيل الثنائي المتكرر (RBR) بالقيم السالبة. لا توجد بتة إشارة واحدة تحدد ما إذا كان العدد المُمثَّل بشكل زائد موجبًا أم سالبًا. معظم الأعداد الصحيحة لها عدة تمثيلات ممكنة في التمثيل الثنائي المتكرر.

غالباً ما يتم اختيار أحد التمثيلات العديدة الممكنة للعدد الصحيح كشكل "قانوني"، لذلك فإن لكل عدد صحيح تمثيل "قانوني" واحد ممكن فقط؛ الشكل غير المتجاور والمتمم الثنائي هما خياران شائعان لهذا الشكل القانوني.

يمكن تحويل قيمة عددية صحيحة من RBR باستخدام الصيغة التالية، حيث n هو عدد الأرقام و d _k هي القيمة المفسرة للرقم k ، حيث يبدأ k من 0 في أقصى اليمين:

${\displaystyle \sum _{k=0}^{n-1}d_{k}2^{k}}$

يمكن إجراء التحويل من RBR إلى مكمل ثنائي مكون من n بت في زمن O(log( n )) باستخدام جامع البادئة . ^{[ 3 ]}

لا تمتلك جميع التمثيلات الزائدة نفس الخصائص. على سبيل المثال، باستخدام جدول الترجمة على اليمين، يمكن تمثيل العدد 1 في هذا التمثيل RBR بعدة طرق: "01·01·01·11" (0+0+0+1)، "01·01·10·11" (0+0+0+1)، "01·01·11·00" (0+0+2−1)، أو "11·00·00·00" (8−4−2−1). كذلك، بالنسبة لجدول الترجمة هذا، فإن قلب جميع البتات ( بوابة NOT ) يُقابل إيجاد المعكوس الجمعي ( الضرب في −1 ) للعدد الصحيح المُمثَّل. ^{[ 4 ]}

في هذه الحالة:${\displaystyle d_{k}\in \{-1,0,1\}}$

تُستخدم التمثيلات الزائدة بشكل شائع داخل وحدات الحساب والمنطق عالية السرعة .

على وجه الخصوص، يستخدم جامع الحفظ مع الحمل تمثيلاً زائداً.

إضافة

عملية الجمع في جميع وحدات RBR خالية من الحمل، مما يعني أن الحمل لا يمر عبر كامل عرض وحدة الجمع. في الواقع، تُعد عملية الجمع في جميع وحدات RBR عملية ثابتة الزمن. ستستغرق عملية الجمع دائمًا نفس المدة الزمنية بغض النظر عن عرض بتات المعاملات . هذا لا يعني أن عملية الجمع أسرع دائمًا في وحدة RBR من نظيرتها في نظام المتمم الثنائي ، ولكن ستكون عملية الجمع أسرع في وحدة RBR مع زيادة عرض البتات لأن تأخير وحدة الجمع في نظام المتمم الثنائي يتناسب مع لوغاريتم ( n ) (حيث n هو عرض البتات). ^{[ 5 ]} تستغرق عملية الجمع في وحدة RBR وقتًا ثابتًا لأنه يمكن حساب كل رقم من أرقام النتيجة بشكل مستقل عن الآخر، مما يعني إمكانية حساب كل رقم من أرقام النتيجة بالتوازي. ^{[ 6 ]}

لا يمكن إجراء العمليات المنطقية على مستوى البتات، مثل AND و OR و XOR ، في التمثيلات المتكررة. ورغم إمكانية إجراء عمليات على مستوى البتات مباشرةً على البتات الأساسية داخل سجل البتات المتكرر (RBR)، إلا أنه ليس من الواضح ما إذا كانت هذه العملية ذات جدوى؛ إذ توجد طرق عديدة لتمثيل قيمة ما في سجل البتات المتكرر، وتعتمد قيمة النتيجة على التمثيل المستخدم.

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

مع ذلك، من الممكن تحويل الجزء الأقل أهمية فقط من عدد مُمثَّل بشكل زائد إلى شكل غير زائد. وهذا يسمح بإجراء عمليات، مثل إخفاء البتات k المنخفضة ، في زمن لوغاريتمي (log( k )).