شكل غير متجاور

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
الموسوعة الحرة

الشكل غير المتجاور ( NAF ) للعدد هو تمثيل فريد للأرقام الموقعة ، حيث لا يمكن أن تكون القيم غير الصفرية متجاورة. على سبيل المثال:

(0 1 1 1) 2 = 4 + 2 + 1 = 7
(1 0 −1 1) 2 = 8 − 2 + 1 = 7
(1 −1 1 1) 2 = 8 − 4 + 2 + 1 = 7
(1 0 0 −1) 2 = 8 − 1 = 7

جميعها تمثيلات صحيحة للأرقام الموقعة للعدد 7، ولكن التمثيل الأخير فقط، (1 0 0 −1) 2 ، هو في شكل غير متجاور.

يُعرف الشكل غير المتجاور أيضًا باسم تمثيل "الرقم الموقع المتعارف عليه".

ملكيات

تضمن تقنية NAF تمثيلًا فريدًا للأعداد الصحيحة ، لكن ميزتها الرئيسية تكمن في أن وزن هامينغ للقيمة يكون في حده الأدنى. ففي التمثيلات الثنائية العادية للقيم، يكون نصف البتات في المتوسط ​​غير صفري، بينما مع NAF ينخفض ​​هذا العدد إلى ثلث البتات فقط. وهذا يؤدي إلى تنفيذ فعال لشبكات الجمع/الطرح (مثل الضرب في ثابت) في معالجة الإشارات الرقمية السلكية . [ 1 ]

من الواضح أن نصف الأرقام على الأكثر غير صفرية، وهذا هو السبب في تقديمها بواسطة جي.  دبليو.  رايتوايسنر [ 2 ] لتسريع خوارزميات الضرب المبكرة، مثل ترميز بوث .

لأن كل رقم غير صفري يجب أن يكون مجاورًا لصفرين، يمكن تنفيذ تمثيل NAF بحيث لا يتطلب سوى m + 1 بت كحد أقصى لقيمة يتم تمثيلها عادةً بالنظام الثنائي باستخدام m بت.

تُسهّل خصائص NAF استخدامها في العديد من الخوارزميات، لا سيما في مجال التشفير ؛ على سبيل المثال، لتقليل عدد عمليات الضرب اللازمة لإجراء عملية الرفع إلى الأس . في خوارزمية الرفع إلى الأس بالتربيع ، يعتمد عدد عمليات الضرب على عدد البتات غير الصفرية. إذا كان الأس مُعطى بصيغة NAF، فإن القيمة 1 تعني الضرب في الأساس، والقيمة -1 تعني الضرب في مقلوبه.

تشمل الطرق الأخرى لترميز الأعداد الصحيحة التي تتجنب الرقم 1 المتتالي ترميز Booth وترميز Fibonacci .

التحويل إلى NAF

توجد عدة خوارزميات للحصول على تمثيل NAF لقيمة معطاة بالنظام الثنائي. إحدى هذه الخوارزميات هي الطريقة التالية التي تستخدم القسمة المتكررة؛ حيث تعمل عن طريق اختيار معاملات غير صفرية بحيث يكون ناتج القسمة قابلاً للقسمة على 2، وبالتالي يكون المعامل التالي صفرًا. [ 3 ]

المدخل E = ( e <sub> m </sub>-1 e<sub> m </sub>-2 ··· e<sub> 1 </sub> e<sub> 0</sub> ) 2 المخرج Z = ( z<sub> m</sub> z<sub> m </sub> -1 ··· z <sub>1 </sub> z<sub> 0</sub> ) NAF i ← 0 طالما أن E > 0، نفّذ إذا كان E فرديًا، فإن zi ← 2 − ( E mod 4) E ← E − zi آخر ض أنا ← 0 ه ← ه /2 أنا ← أنا + 1 إرجاع z

هناك طريقة أسرع يقدمها برودينجر [ 4 ] حيث x هو المدخل، و np سلسلة البتات الموجبة و nm سلسلة البتات السالبة:

المدخل x المخرج np ، nm xh = x >> 1؛ x3 = x + xh ؛ c = xh ^ x3 ؛ np = x3 & c ؛ nm = xh & c ؛

والذي يستخدم، على سبيل المثال، في A184616 .

مراجع

  1. ↑ هيوليت، آر إم (2000). التمثيل الرقمي الموقّع المتعارف عليه لمرشحات FIR الرقمية . أنظمة معالجة الإشارات، 2000. SiPS 2000. ورشة عمل IEEE لعام 2000. الصفحات 416-426 . doi : 10.1109/SIPS.2000.886740 . ISBN  978-0-7803-6488-2. S2CID 122082511 . 
  2. ↑ ريتويزنر، جورج و. (1960). "الحساب الثنائي". التقدم في الحوسبة . 1 : 231-308 . doi : 10.1016/S0065-2458(08)60610-5 . ISBN 9780120121014.{{cite journal}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
  3. ↑ هانكرسون، د.؛ مينيزيس، أ.؛ فانستون، س. أ. (2004). دليل تشفير المنحنيات الإهليلجية . سبرينغر. ص 98. ISBN  978-0-387-21846-5.
  4. ↑ برودينجر، هيلموت. "حول التمثيلات الثنائية للأعداد الصحيحة ذات الأرقام -1، 0، 1" (ملف PDF) . الأعداد الصحيحة . تم الاطلاع عليه بتاريخ 25 يونيو 2021 .