وزن همینگ
وزن همینگ یک رشته، تعداد نمادهایی متفاوت با نماد صفر الفبا در یک رشته است. بنابراین این مفهوم معادل فاصله همینگ از یک رشتهٔ تمام‌صفر از همان طول است. یکی از متداول‌ترین موارد را می‌توان به ۱های یک رشته از بیت‌ها نام برد که در این حالت به آن شمار جمعیت نیز می‌گویند.[۱] وزن همینگ مجموع ارقام نمایش دودویی یک عدد یا ℓ₁-هنج یک بردار از بیت‌ها است.
| رشته | وزن همینگ |
|---|---|
| 11101 | 4 |
| 11101000 | 4 |
| 00000000 | 0 |
| 789012340567 | 10 |
تاریخچه و کاربرد
[ویرایش]وزن همینگ پس از کارهای ریچارد همینگ نام‌گذاری شد، اگرچه او سرچشمه این مفهوم نیست.[۲] وزن همینگ اعداد باینری قبلاً در سال ۱۸۹۹ توسط J. W. L. Glaisher به منظور ساخت یک فرمول برای تعداد عددهای فرد ضرایب بسط دوجمله‌ای در یک ردیف از مثلث خیام استفاده شده بود.[۳] Irving S. Reed در ۱۹۵۴ یک مفهوم معادل با وزن همینگ در حالت دودویی را ارائه داد.[۴]
وزن همینگ در چندین رشته از جمله نظریه اطلاعات، نظریه کدگذاری و رمزنگاری مورد استفاده قرار گرفته‌است.
پیاده‌سازی کارا
[ویرایش]وزن همینگ یک رشته از بیت‌ها عموماً در رمزنگاری و سایر کاربردها مورد نیاز است. فاصله همینگ دو واژه آ و ب را می‌توان از طریق محاسبه (آ یای انحصاری ب) بدست آورد.
مسئلهٔ چگونگی پیاده‌سازی کارای این مفهوم به صورت وسیعی مورد مطالعه قرار گرفته‌است. برخی از پردازنده‌ها دارای دستوری به منظور محاسبه این مقدار هستند و برخی دیگر دارای قابلیت انجام عملیات موازی بر برداری از بیت‌ها هستند. برای پردازنده‌های فاقد این ویژگی‌ها، بهترین راه‌حل موجود مبتنی بر شمارش بر مبنای یک الگوی درختی است.
منابع
[ویرایش]- ↑ D. E. Knuth (2009). The Art of Computer Programming Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams. Addison–Wesley Professional. ISBN 0-321-58050-8.
- ↑ Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs #21, The Mathematical Association of America, p. 33
- ↑ Glaisher, J. W. L. (1899), "On the residue of a binomial-theorem coefficient with respect to a prime modulus", The Quarterly Journal of Pure and Applied Mathematics, 30: 150–156
{{citation}}: More than one of|authorlink=و|author-link=specified (help). - ↑ Reed, I.S. (1954), "A Class of Multiple-Error-Correcting Codes and the Decoding Scheme", I.R.E. (I.E.E.E.), PGIT-4: 38