مقدمه
هر میلیثانیه، تریلیونها و تریلیونها پیام میان زمین و کهکشانهای همسایه جابهجا میشوند.
اما انتقال بر فراز چنین فاصلههای طولانی کار دشواری است.
شعلههای آزاردهندهی خورشیدی، اعوجاجهای زمانی، نیروهای سرگردان و حتی بههمخوردن بال یک پروانهی فضایی میتوانند باعث شوند در هنگام انتقال، بیتی بهصورت تصادفی تغییر کند.
حالا پیامدهایش را تصور کنید:
- سقوط بازار سهام بینکهکشانی وقتی «buy low» به «sell now» تبدیل شود.
- از دست رفتن ارتباط با سامانهی Kepler Whirl وقتی «save new worm hole» به «cave new worm hole» تبدیل شود.
- یا فرو بردن جهان در وحشت وجودی با جایگزینکردن ایموجی گاوچران 🤠 بهجای ایموجی دلقک 🤡.
تشخیص پیامهای مخدوش فقط مهم نیست، حیاتی است.
گیرنده باید بداند چه زمانی چیزی اشتباه پیش رفته است، پیش از آنکه فاجعه رخ دهد.
اما چگونه؟
دانشمندان و مهندسان از سراسر جهان از دیرباز با این مسئله دستوپنجه نرم کردهاند.
همهی ابرخوشههای کیهانی AI دادهها را زیر و رو میکنند.
و بعد، یک روز، افسانهای دوباره سر برمیآورد: روشی باستانی و قدرتمند که در انجمنهای Debug زمزمه میشود و مهندسانی که بیش از حد دیدهاند آن را زیر لب تکرار میکنند...
«بیت توازن!»
روشی چنان ساده و چنان قدرتمند که شاید همین بتواند ارتباط میانستارهای را نجات دهد.
دستورالعملها
وظیفهی شما کمک به پیادهسازی این موارد است
- «فرستنده» که «دنبالهی انتقال» را محاسبه میکند و
- «گیرنده» که آن را رمزگشایی میکند.
«بیت توازن» روشی ساده برای تشخیص خطاهای انتقال است.
فرستندهها و گیرندهها فقط میتوانند هر بار دقیقاً هشت بیت (با احتساب بیت توازن) ارسال و دریافت کنند.
بیت توازن طوری تنظیم میشود که در هر انتقال تعداد زوجی از بیتهای ۱ وجود داشته باشد و بیت توازن همیشه اولین بیت از سمت راست است.
پس اگر گیرنده 11000001، 01110101 یا 01000000 را دریافت کند (یعنی انتقالی با تعداد فردی از بیتهای ۱)، میداند که خطایی وجود دارد.
با این حال، پیامها بهندرت اینقدر کوتاه هستند و وقتی طولانیتر میشوند باید در قالب یک دنباله ارسال شوند.
برای مثال، پیام 11000000 00000001 11000000 11011110 را در نظر بگیرید (یا C0 01 C0 DE در مبنای شانزده).
از آنجا که هر انتقال دقیقاً هشت بیت دارد، فقط میتواند شامل هفت بیت داده و بیت توازن باشد.
پس باید بعد از هر هفت بیت داده، یک بیت توازن درج شود:
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
دنبالهی انتقال برای این پیام به این شکل است:
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
دادهی اولین انتقال در دنباله (1100000) دو بیت ۱ دارد (تعداد زوج)، پس بیت توازن ۰ است.
اولین انتقال 11000000 میشود (یا C0 در مبنای شانزده).
دادهی انتقال بعدی (0000000) هیچ بیت ۱ ندارد (باز هم تعداد زوج)، پس بیت توازن باز هم ۰ است.
بنابراین دومین انتقال 00000000 میشود (یا 00 در مبنای شانزده).
دادهی دو انتقال بعدی (0111000 و 0001101) سه بیت ۱ دارد.
بیتهای توازن آنها روی ۱ تنظیم میشوند تا در انتقال تعداد زوجی از بیتهای ۱ داشته باشند.
آنها بهصورت 01110001 و 00011011 ارسال میشوند (یا 71 و 1B در مبنای شانزده).
آخرین انتقال (1110) فقط چهار بیت داده دارد.
از آنجا که هر بار دقیقاً هشت بیت ارسال میشود و بیت توازن راستترین بیت است، سه بیت ۰ و سپس بیت توازن اضافه میشوند تا هشت بیت کامل شود.
اکنون به این شکل است (که در آن _ بیت توازن است):
1110 000_
↑↑↑ (added 0 bits)
باز هم تعداد فردی از بیتهای ۱ وجود دارد، پس بیت توازن ۱ است.
آخرین انتقال در دنباله 11100001 میشود (یا E1 در مبنای شانزده).
کل دنبالهی انتقال برای این پیام 11000000 00000000 01110001 00011011 11100001 است (یا C0 00 71 1B E1 در مبنای شانزده).
پیادهسازی
اگرچه با بایتهای داده سروکار داریم، ورودیها و خروجیها List<Integer> هستند (بهجای byte[]) تا نیازی به تبدیل نوع یا تبدیل مقادیر منفی بایتهای ۱۲۸ تا ۲۵۵ نباشد.
