تعمیم parity

صورت سوال این بود که می‌خواهیم یک سری داده را به تعدادی بلوک تقسیم کنیم، طوری که تعداد بلوک‌های لازم برای بازسازی آن مینیمم شود.

مثال: عبارت parity بر حسب بلوک‌های زیر باشد: (در این صورت از بین ۱۰ تا بلوک موجود، با ساختن ۵ تا عبارت می‌شود بازسازی هر کدام را انجام داد.)

1 1 - - 1

2 2 - 2 -

3 3 3 - -

4 - 4 4 -

5 - 5 - 5

6 - - 6 6

- 7 7 7 -

- 8 8 - 8

- 9 - 9 9

- - 10 10 10

فرض کنید تعداد بلوکهای ورودی n تا و تعداد بلوکهای عبارت کدشده k تا باشد.

چون هر ترتیب، جایگشت نام بلوک‌های مختلف است که نسبت به هم تقارن دارند چون هیچ بلوکی به دیگری برتری ندارد، پس فقط مهم این است که همه‌ی رشته‌هایی که دارای ۳ تا یک هستند (پس حداکثر ۳ بلوک از بین برود باز هم کار می‌کنند) را پیدا کنیم که کلاً C(k,3) می‌شود و باید تعداد بلوک‌ها کمتر مساوی این مقدار باشد تا جواب بدهد. چون parity باید ۳ جا مقدار را داشته باشد تا بتواند بازسازی را انجام بدهد.

تعمیم آن با جایگزین کردن ۳ با d انجام می‌شود که در این صورت باید n=C(k,d) بلوک بسازیم سپس همه‌ی رشته‌های به طول k و با دقیقاً d تا یک را بسازیم سپس آنها را زیر هم بنویسیم و هر ستون را به عنوان یک رابطه خطی از بلوک‌ها بنویسیم که ۱ بودن معادل حضور بلوک متناظر آن سطر در رابطه‌ی کدشده است.

برای اینکه تعداد xorها مینیمم باشد باید رشته‌های k-بیتی را طوری کنار هم قرار بدهیم که هر ستون بیشترین اشتراک را با ستون قبلی داشته باشند. یک راه حل برای رسیدن به این هدف مرتب کردن اعداد است که چون برای بیت‌ها ارزش مکانی قائل است تا حد امکان آنها را جا به جا نمی‌کند. (این قسمت را ثابت نکردم دقیقاً ولی با توجه به اینکه همه‌ی جایگشت‌های ممکن ۰ و ۱ با ۳ تا یک را داریم می‌سازیم، به نظرم هر ترتیبی که حداکثر دو رقم را جا به جا کرده باشد خوب است.)

* جالب بود که اکثر بچه‌ها (از جمله خود من!) بار اولی که سوال را شنیدیم به hypergraph فکر کردیم. چون از این نظر که بلوکها چه ارتباطی با هم دارند چنین مدلی به ذهن می‌رسد. در حالی که این مدل کردن بیتی به سادگی مسأله را حل کرد.

* مرجع سوال: Majid Khabbazian دانشگاه آلبرتا