وزن هامينغ

وزن هامينغ لسلسلة هو عدد الرموز المختلفة عن رمز الصفر في الأبجدية المستخدمة. وهو بالتالي يُعادل مسافة هامينغ من سلسلة جميع رموزها أصفار ولها نفس الطول. في الحالة الأكثر شيوعًا، أي مجموعة معينة من البتات ، يُمثل هذا الوزن عدد البتات التي قيمتها 1، أو مجموع أرقام التمثيل الثنائي لعدد معين ومعيار ℓ₁ لمتجه بت. في هذه الحالة الثنائية، يُطلق عليه أيضًا اسم عدد البتات ، ^{[ 1 ]} أو مجموع البتات ، أو المجموع الجانبي ، ^{[ 2 ]} أو مجموع البتات . ^{[ 3 ]}

سُمّي وزن هامينغ نسبةً إلى عالم الرياضيات الأمريكي ريتشارد هامينغ ، مع أنه لم يكن صاحب الفكرة. ^{[ 5 ]} وقد استُخدم وزن هامينغ للأعداد الثنائية عام 1899 من قِبل جيمس دبليو إل غليشر لإعطاء صيغة لعدد معاملات ذات الحدين الفردية في صف واحد من مثلث باسكال . ^{[ 6 ]} وقدّم إيرفينغ إس ريد مفهومًا مُكافئًا لوزن هامينغ في الحالة الثنائية عام 1954. ^{[ 7 ]}

يُستخدم وزن هامينغ في العديد من المجالات، بما في ذلك نظرية المعلومات ، ونظرية الترميز ، وعلم التشفير . ومن أمثلة تطبيقات وزن هامينغ ما يلي:

• في عملية الرفع الأسي المعياري بالتربيع ، يكون عدد عمليات الضرب المعياري اللازمة للأس e هو log₂e ₊ weight( e ) . لهذا السبب، يُختار عادةً قيمة المفتاح العام e المستخدمة في RSA لتكون ذات وزن هامينغ منخفض. ^{[ 8 ]}
• يحدد وزن هامينغ أطوال المسارات بين العقد في جداول التجزئة الموزعة Chord . ^{[ 9 ]}
• يتم عادةً تنفيذ عمليات البحث عن رمز قزحية العين في قواعد البيانات البيومترية عن طريق حساب مسافة هامينغ لكل سجل مخزن. ^{[ 10 ]}
• في برامج الشطرنج الحاسوبية التي تستخدم تمثيل لوحة البت ، يُعطي وزن هامينغ للوحة البت عدد القطع المتبقية من نوع معين في اللعبة، أو عدد مربعات اللوحة التي تسيطر عليها قطع أحد اللاعبين، وبالتالي فهو عامل مهم يساهم في قيمة الموقف. ^{[ 11 ]}
• يمكن استخدام وزن هامينغ لحساب إيجاد المجموعة الأولى بكفاءة باستخدام المتطابقة ffs(x) = pop(x ^ (x - 1)). يُعد هذا مفيدًا على منصات مثل SPARC التي تحتوي على تعليمات وزن هامينغ مدمجة ولكنها لا تحتوي على تعليمات إيجاد المجموعة الأولى مدمجة. ^{[ 12 ] [ 1 ]}
• يمكن تفسير عملية وزن هامينغ على أنها تحويل من نظام الأرقام الأحادية إلى الأرقام الثنائية . ^{[ 13 ]}

يُعدّ عدد البتات في سلسلة البتات ضروريًا في علم التشفير وتطبيقات أخرى. ويمكن حساب مسافة هامينغ بين كلمتين A و B من خلال وزن هامينغ لعملية XOR بين A ^و B. ^{[ 1} ]

لقد حظيت مشكلة كيفية تنفيذها بكفاءة باهتمام واسع في الدراسات. تتوفر عملية حسابية واحدة، أو عمليات متوازية على متجهات البتات، في بعض المعالجات . أما بالنسبة للمعالجات التي تفتقر إلى هذه الميزات، فإن أفضل الحلول المعروفة تعتمد على جمع القيم في نمط شجري. على سبيل المثال، لحساب عدد البتات التي قيمتها 1 في العدد الثنائي ذي 16 بت a  =  0110  1100  1011  1010، يمكن إجراء العمليات التالية:

هنا، تُجرى العمليات كما في لغة البرمجة C ، حيث X >> Yتعني `x` إزاحة X إلى اليمين بمقدار Y بت، و`x & Y` تعني عملية AND المنطقية بين X وY، و`+` تعني الجمع العادي. تعتمد أفضل الخوارزميات المعروفة لحل هذه المشكلة على المفهوم الموضح أعلاه، وهي مُدرجة هنا: ^{[ 1 ]}

// أنواع البيانات والثوابت المستخدمة في الدوال أدناه // uint64_t هو نوع متغير عدد صحيح غير مُوقّع 64 بت (مُعرّف في إصدار C99 من لغة C) const uint64_t m1 = 0x55555555555555555 ; // ثنائي: 0101... const uint64_t m2 = 0x33333333333333333 ; // ثنائي: 00110011.. const uint64_t m4 = 0x0f0f0f0f0f0f0f0f ; // ثنائي: 4 أصفار، 4 آحاد ... const uint64_t m8 = 0x00ff00ff00ff00ff ; // ثنائي: 8 أصفار، 8 آحاد ... const uint64_t m16 = 0x0000ffff0000ffff ; // ثنائي: 16 صفرًا، 16 آحاد ... const uint64_t m32 = 0x00000000ffffffff ; // ثنائي: 32 صفرًا، 32 آحاد const uint64_t h01 = 0x0101010101010101 ; // مجموع 256 مرفوعًا للأس 0، 1، 2، 3 ...// هذا تطبيق بسيط، معروض للمقارنة، // وللمساعدة في فهم الدوال الأفضل. // تستخدم هذه الخوارزمية 24 عملية حسابية (الإزاحة، والجمع، و AND). int popcount64a ( uint64_t x ) { x = ( x & m1 ) + (( x >> 1 ) & m1 ); // ضع عدد كل 2 بت في هذين البتّين x = ( x & m2 ) + (( x >> 2 ) & m2 ); // ضع عدد كل 4 بت في هذه البتّات الأربعة x = ( x & m4 ) + (( x >> 4 ) & m4 ); // ضع عدد كل 8 بت في هذه البتّات الثمانية x = ( x & m8 ) + (( x >> 8 ) & m8 ); // ضع عدد كل 16 بت في هذه البتّات الستة عشر x = ( x & m16 ) + (( x >> 16 ) & m16 ); // ضع عدد كل 32 بت في تلك الـ 32 بت x = ( x & m32 ) + (( x >> 32 ) & m32 ); // ضع عدد كل 64 بت في تلك الـ 64 بت return x ; }// يستخدم هذا عددًا أقل من العمليات الحسابية مقارنةً بأي تطبيق آخر معروف // على الأجهزة ذات الضرب البطيء. // تستخدم هذه الخوارزمية 17 عملية حسابية. int popcount64b ( uint64_t x ) { x -= ( x >> 1 ) & m1 ; // ضع عدد كل 2 بت في هذين البتّين x = ( x & m2 ) + (( x >> 2 ) & m2 ); // ضع عدد كل 4 بت في هذه البتّات x = ( x + ( x >> 4 )) & m4 ; // ضع عدد كل 8 بت في هذه البتّات x += x >> 8 ; // ضع عدد كل 16 بت في أدنى 8 بتّ x += x >> 16 ; // ضع عدد كل 32 بت في أدنى 8 بتّ x += x >> 32 ; // ضع عدد كل 64 بت في أدنى 8 بتّ return x & 0x7f ; }// يستخدم هذا عددًا أقل من العمليات الحسابية مقارنةً بأي تطبيق آخر معروف // على الأجهزة ذات الضرب السريع. // تستخدم هذه الخوارزمية 12 عملية حسابية، إحداها عملية ضرب. int popcount64c ( uint64_t x ) { x -= ( x >> 1 ) & m1 ; // ضع عدد كل 2 بت في هذين البتّين x = ( x & m2 ) + (( x >> 2 ) & m2 ); // ضع عدد كل 4 بت في هذه البتّات x = ( x + ( x >> 4 )) & m4 ; // ضع عدد كل 8 بت في هذه البتّات return ( x * h01 ) >> 56 ; // تُرجع البتّات الثمانية المتبقية من x + (x<<8) + (x<<16) + (x<<24) + ... }

تتميز التطبيقات المذكورة أعلاه بأفضل أداء في أسوأ الحالات مقارنةً بأي خوارزمية معروفة. مع ذلك، عندما يُتوقع أن تحتوي قيمة ما على عدد قليل من البتات غير الصفرية، قد يكون من الأجدى استخدام خوارزميات تحسب هذه البتات بتًا بتًا. وكما وصف ويغنر في عام 1960 ^{[ 14 ]،} فإن عملية AND المنطقية للبتات بين x و x - 1 تختلف عن x فقط في تصفير البت الأقل أهمية غير الصفري: طرح 1 يُحوّل سلسلة الأصفار الموجودة في أقصى اليمين إلى 1، ويُحوّل البت 1 الموجود في أقصى اليمين إلى 0. إذا كانت x تحتوي في الأصل على n بتًا قيمتها 1، فبعد n تكرارًا فقط لهذه العملية، ستُختزل x إلى الصفر. يعتمد التطبيق التالي على هذا المبدأ.  

// يكون هذا أفضل عندما تكون معظم البتات في x تساوي صفرًا. // تعمل هذه الخوارزمية بنفس الطريقة لجميع أحجام البيانات. // تستخدم هذه الخوارزمية 3 عمليات حسابية ومقارنة/تفرع واحد لكل بت "1" في x. int popcount64d ( uint64_t x ) { int count ; for ( count = 0 ; x ; count ++ ) x &= x - 1 ; return count ; }

ومن الأمور الجديرة بالاهتمام هنا العلاقة الوثيقة بين Popcount و FFS و CLZ.

إذا سُمح باستخدام ذاكرة أكبر، يُمكننا حساب وزن هامينغ بشكل أسرع من الطرق المذكورة أعلاه. مع ذاكرة غير محدودة، يُمكننا ببساطة إنشاء جدول بحث كبير لوزن هامينغ لكل عدد صحيح 64 بت. إذا أمكننا تخزين جدول بحث لدالة هامينغ لكل عدد صحيح 16 بت، يُمكننا القيام بما يلي لحساب وزن هامينغ لكل عدد صحيح 32 بت.

static uint8_t wordbits [ 65536 ] = { /* عدد بتات الأعداد الصحيحة من 0 إلى 65535، شاملةً */ }; // تستخدم هذه الخوارزمية 3 عمليات حسابية وقراءتين من الذاكرة. int popcount32e ( uint32_t x ) { return wordbits [ x & 0xFFFF ] + wordbits [ x >> 16 ]; }

// اختياريًا، يمكن ملء جدول wordbits[] باستخدام هذه الدالة int popcount32e_init ( void ) { uint32_t i ; uint16_t x ; int count ; for ( i = 0 ; i <= 0xFFFF ; i ++ ) { x = i ; for ( count = 0 ; x ; count ++ ) // مستعارة من popcount64d() أعلاه x &= x - 1 ; wordbits [ i ] = count ; } }

تم تقديم خوارزمية تكرارية في دونوفان وكيرنيغان ^{[ 15 ]}

/* يمكن أن يختلف وزن i عن وزن i / 2 فقط في أقل بت أهمية من i */ int popcount32e_init ( void ) { int i ; for ( i = 1 ; sizeof wordbits / sizeof * wordbits > i ; ++ i ) wordbits [ i ] = wordbits [ i >> 1 ] + ( 1 & i ); }

أظهر Muła et al. ^{[ 16 ]} أن النسخة المتجهة من popcount64b يمكن أن تعمل بشكل أسرع من التعليمات المخصصة (على سبيل المثال، popcnt على معالجات x64).

تُعد خوارزمية هارلي-سيل ^{[ 17 ]} واحدة من أسرع الخوارزميات التي لا تتطلب سوى عمليات حسابية على الأعداد الصحيحة. ^{[ 18 ]}

في ترميز تصحيح الأخطاء ، يُعرف الحد الأدنى لوزن هامينغ، والذي يُشار إليه عادةً بالوزن الأدنى w_{_min} للرمز، بأنه وزن أقل كلمة رمزية غير صفرية وزنًا. وزن w لكلمة رمزية هو عدد الآحاد (1) فيها. على سبيل المثال، وزن الكلمة 11001010 هو 4.

In a linear block code the minimum weight is also the minimum Hamming distance (d_min) and defines the error correction capability of the code. If w_min = n, then d_min = n and the code will correct up to d_min/2 errors.^[19]

Some C compilers provide intrinsic functions that provide bit counting facilities. For example, GCC (since version 3.4 in April 2004) includes a builtin function __builtin_popcount that will use a processor instruction if available or an efficient library implementation otherwise.^[20]LLVM-GCC has included this function since version 1.5 in June 2005.^[21]

In the C++ Standard Library, the bit-array data structure bitset has a count() method that counts the number of bits that are set. In C++20, a new header <bit> was added, containing functions std::popcount and std::has_single_bit, taking arguments of unsigned integer types.

In Java, the growable bit-array data structure BitSet has a BitSet.cardinality() method that counts the number of bits that are set. In addition, there are Integer.bitCount(int) and Long.bitCount(long) functions to count bits in primitive 32-bit and 64-bit integers, respectively. Also, the BigInteger arbitrary-precision integer class also has a BigInteger.bitCount() method that counts bits.

In Python, the int type has a bit_count() method to count the number of bits set. This functionality was introduced in Python 3.10, released in October 2021.^[22]

In Common Lisp, the function logcount, given a non-negative integer, returns the number of 1 bits. (For negative integers it returns the number of 0 bits in 2's complement notation.) In either case the integer can be a bignum.

Starting in GHC 7.4, the Haskell base package has a popCount function available on all types that are instances of the Bits class (available from the Data.Bits module).^[23]

MySQL version of SQL language provides BIT_COUNT() as a standard function.^[24]

Fortran 2008 has the standard, intrinsic, elemental function popcnt returning the number of nonzero bits within an integer (or integer array).^[25]

تحتوي بعض الآلات الحاسبة العلمية القابلة للبرمجة على أوامر خاصة لحساب عدد البتات المُفعّلة، على سبيل المثال #Bفي HP-16C . ^{[ 3 ]}

تُنفذ FreePascal دالة popcnt منذ الإصدار 3.0. ^{[ 26 ]}

• قام حاسوب IBM STRETCH في الستينيات بحساب عدد البتات المُفعّلة بالإضافة إلى عدد الأصفار البادئة كناتج ثانوي لجميع العمليات المنطقية. ^{[ 1 ]}
• تضمنت أجهزة الكمبيوتر العملاقة من نوع كراي في بداياتها تعليمات برمجية لحساب عدد السكان، ويُشاع أن وكالة الأمن القومي التابعة للحكومة الأمريكية قد طلبتها تحديدًا لتطبيقات تحليل الشفرات . ^{[ 1 ]}
• تضمنت أجهزة سلسلة 6000 و Cyber ​​70/170 التابعة لشركة Control Data Corporation (CDC) تعليمات عد السكان؛ في COMPASS ، تم ترميز هذه التعليمات على النحو التالي CXi.
• تُعرّف بنية SPARC الإصدار 9 ذات 64 بت POPCتعليمة معينة، ^{[ 12 ] [ 1 ]} ولكن معظم التطبيقات لا تُنفذها، مما يتطلب محاكاتها بواسطة نظام التشغيل. ^{[ 27 ]}
• يحتوي نموذج الكمبيوتر MMIX الخاص بدونالد كنوث ، والذي سيحل محل MIX في كتابه "فن برمجة الكمبيوتر"، على SADDتعليمة منذ عام 1999. SADD a,b,cيقوم هذا النموذج بحساب جميع البتات التي تساوي 1 في b و 0 في c ويكتب النتيجة إلى a.
• كان معالج Compaq 's Alpha 21264A ، الذي تم إصداره في عام 1999، أول تصميم لوحدة المعالجة المركزية من سلسلة Alpha يحتوي على امتداد العد ( CIX).
• تتميز معالجات Blackfin من Analog DevicesONES بتعليمات لإجراء عملية عد السكان 32 بت. ^{[ 28 ]}
• قدمت بنية برشلونة من AMD مجموعة تعليمات معالجة البتات المتقدمة (ABM) POPCNTكجزء من امتدادات SSE4a في عام 2007.
• قدمت معالجات Intel CorePOPCNT تعليمات مع امتداد مجموعة تعليمات SSE4.2 ، والتي كانت متاحة لأول مرة في معالج Core i7 القائم على Nehalem ، والذي تم إصداره في نوفمبر 2008.
• أدخلت بنية ARMVCNT التعليمات كجزء من امتدادات SIMD المتقدمة ( NEON ).
• أدخلت بنية RISC-V هذه التعليمات كجزءCPOP من امتداد معالجة البتات (B). ^{[ 29 ]}

• متمم الاثنين
• انتشروا

• شرويبل، ريتشارد سي .؛ أورمان، هيلاري ك. (29 فبراير 1972). "تجميع". هاكم . بقلم بيلر، مايكل؛ جوسبر، رالف ويليام ؛ شرويبل، ريتشارد سي. (تقرير). مختبر الذكاء الاصطناعي ، معهد ماساتشوستس للتكنولوجيا ، كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية. مذكرة معهد ماساتشوستس للتكنولوجيا للذكاء الاصطناعي رقم 239.( البند 169 : كود تجميع عد السكان لجهاز PDP/6-10.)

• خوارزميات التجميع السحرية . شرح لخوارزميات عدّ السكان المُحسّنة وغيرها من الخوارزميات مع نماذج برمجية.
• حيل التلاعب بالبتات: عدة خوارزميات مع شفرة لحساب البتات المُفعّلة.
• ضروري وكافٍ مؤرشف في 2017-09-23 على Wayback Machine - بواسطة داميان وينتور - يحتوي على كود بلغة C# لتطبيقات وزن هامينغ المختلفة.
• ما هي أفضل خوارزمية لحساب عدد البتات المُفعّلة في عدد صحيح 32 بت؟ - Stackoverflow