ارتباط! بله مقوله‌ی مهم عصرجدید، ارتباط است. ارتباط انسان‌و ماشین، ارتباط با آدم فضایی‌ها، ارتباط ماشین با ماشین و یا حتی ارتباط انسان با انسان. در برقراری ارتباط همیشه چالشی نهفته است و آن‌هم تفهیمِ مفهوم است؛ اینکه سعی‌کنید به‌نحوی مطلب را بیان‌کنید که مخاطب منظورشما را متوجه‌شود. شاید در نگاه‌اول چنان مقوله مهمی به‌نظر نرسد ولی فرض‌کنید انسان‌ها توانسته‌باشند تمدنی در منظومه شمسی را شناسایی‌کنند و سعی‌کنند برای آن‌ها پیامی از صلح و دوستی ارسال‌کنند. حال اگر تمدن مذکور آن پیام را تهدید یا دعوت به جنگ استنباط کند، چه اتفاقی روی خواهد داد؟! یا فرض کنید دو دستگاه در خط تولید یک کارخانه، اطلاعاتی را با هم تبادل می‌کنند. اگر عوامل محیطی باعث‌شوند که اطلاعات به‌صورت صحیح بین دستگاه‌ها رد‌و‌بدل نشود، قاعدتاً عملکرد دستگاه‌ها مختل خواهدشد! مسئله‌ی چالش‌بر‌انگیز هر ارتباطی، صحت آن است؛ اینکه به‌نحوی گیرنده‌ی پیام مطمئن باشد منظور شما از پیام چیست و هیچ‌گونه شکی در آن وجود نداشته باشد. اما چطور می‌توان به‌این مهم دست‌پیدا‌کرد؟ چطور می‌شود پیام‌ها را به‌نحوی انتقال داد که گیرنده از صحت آن‌ها اطمینان حاصل کند؟ برای روشن‌شدن مسئله با ما همراه شوید. ما در این مقاله به‌بررسی یکی‌از راه‌های خطایابی ارتباط‌ها می‌پردازیم.
معرفی کانال‌های ارتباطی
اگرچه زیاد فرقی نمی‌کند که کانال ارتباطی چه باشد، صوت یا نوشتار، آنالوگ یا دیجیتال، سریال یا پارالل، دیفرانسیلی یا غیردیفرانسیلی اما همه و همه دربرابر عوامل بیرونی (نویز) تأثیرپذیر هستند و ممکن‌است صحت آن‌ها دچار تغییر‌شود. البته منکر این مهم نیستیم که بنابه ماهیت، تأثیرپذیری برخی از آن‌ها از عوامل خارجی، کم است ولی تغییر ناخواسته اجتناب‌ناپذیر است و نمی‌توان مطمئن بود که اطلاعات در مسیر دستخوش تغییر نشده‌اند. ممکن‌است برای انتقال از پروتکل سریال یا مودم‌های آنالوگ یا حتی ارتباط رادیویی استفاده کرده‌باشید. دراین مقاله، بستر انتقال اطلاعات چندان دارای اهمیت نیست، مسئله‌ی مهم این‌است که اطلاعات دریافتی (از هر بستری) صحیح است یا اشتباه؟
بررسی اجمالی راه‌های خطایابی
در یک ارتباط دیجیتال، راه‌های زیادی برای تشخیص خطا وجوددارد. رایج‌ترین روش تشخیص در ارتباط سریال یا حتی پارالل، قراردادن بیت توازن (Parity bit) است. طبق تعریف بیت توازن می‌تواند زوج یا فرد باشد.
هنگامی‌که از توازن زوج استفاده می‌شود، اگر تعداد یک‌های ورودی زوج باشد، بیت توازن صفر می‌شود و بالعکس هنگامی‌که از توازن فرد استفاده می‌شود، اگر تعداد یک‌های ورودی فرد باشد، بیت توازن صفر می‌شود و بالعکس.
اما این روش خود دارای خطا است و ممکن‌است شرایطی ایجادشود که خطا تشخیص داده‌نشود. مثلاً فرض‌کنید نویز باعث تغییر جای بیت‌ها شده‌باشد. گیرنده باتوجهبه وضعیت Parity متوجه نخواهدشد که جایگاه دو بیت تعویض شده‌است، چرا‌که تناسب بیت‌های ۱ به هم نخورده است. یا اینکه نویز باعث تغییر وضعیت دوبیت در داده‌های ارسالی شده‌باشد. همان‌طورکه می‌بینید Parity bit روش خوبی است اما باز احتمال خطا هرچند کم، ولی وجوددارد. یکی‌دیگر از روش‌های مورد‌استفاده در خطایابی، قرار دادن یک بایت انتهای بایت‌های ارسالی است. فرض‌کنید قرار است ۱۰ بایت داده را منتقل‌کنیم، یک بایت ۱۱ ام هم درنظر می‌گیریم که حاصل جمع ۱۰ بایت اول را درخود جای داده‌است. این روش را checksum گویند. این روش نیز دارای خطا است. اگر موقعیت بایت‌ها عوض شود، همچنان توسط گیرنده قابل‌تشخیص نیست. برای بهترشدن می‌توان به‌جای حاصل‌جمع، از الگوریتم CRC نیز استفاده‌کرد که به‌محل قرارگیری بایت‌ها نیز حساس است ولی همچنان خالی‌از احتمال خطا نخواهد بود. البته صدها روش مشابه دیگر هم وجود دارند. همه‌ی این روش‌ها برای تشخیص‌خطا هستند و به ما می‌گویند داده‌های ارسالی به‌دلایلی دارای صحت نیستند و در مسیر، دستخوش تغییر شده‌اند. اما آیا روشی وجود دارد که بااستفاده‌از آن بتوانیم داده‌های دریافتی که دارای خطا هستند را ترمیم کنیم و دیتای صحیح را از آن استخراج کنیم؟
همینگ کد چیست؟
همان‌طورکه اشاره شد، روش‌های زیادی برای پیداکردن خطای داده‌های ارسالی وجود دارد. اما چطور می‌شود بعداز شناسایی خطای مربوطه، آنرا ترمیم کرد؟ در این حوزه نیز الگوریتم‌ها و پروتکل‌های مختلفی وجود دارد. یکی‌از این روش‌ها، روش همینگ است. ریچارد همینگ ریاضیدان آمریکایی (سومین برنده‌ی جایزه تورینگ)، مقاله‌ی مشهور خود را در سال 1950 هنگامی‌که در شرکت IBM مشغول به‌کار بود منتشرکرد. این مقاله درباره‌ی آشکارسازی و تصحیح‌خطا بود و مفاهیم کد همینگ، فاصله‌ی همینگ و پنجره‌ی همینگ را تعریف‌کرد. در کد همینگ گیرنده علاوه‌بر تشخیص صحیح خطا (بر‌خلاف بیت توازن و checksum)، قادربه اصلاح خطا نیز است. البته توجه‌داشته‌باشید که هر الگوریتمی محدودیت‌های خاص خود را دارد. کد همینگ فقط قادربه تصحیح یک بیت است ولی به‌درستی خطاهای اتفاق افتاده را تشخیص می‌دهد.
همینگ کد چطور کار می‌کند؟
برای روشن‌شدن هرچه بیشتر قضیه و نگاه کاربردی به آن، سعی می‌کنیم که همینگ کد را در قالب یک مثال ساده آموزش دهیم. فرض‌کنید که قصدداریم داده‌ای را از یک فرستنده به گیرنده‌ای ارسال کنیم. داده ما ۸ بیت طول دارد. برای تصحیح خطا در داده‌های ۸ بیتی بنابه نظریه‌ی فاصله‌ی همینگ، نیاز به ۴ بیت داده‌ی تصحیح خطا خواهیم‌داشت. پس در مجموع برای ارسال ۸ بیت داده بااستفاده‌از همینگ کد، نیاز به ۱۲ بیت خواهیم‌داشت.
همان‌طورکه در تصویرفوق مشاهده می‌کنید، محل قرارگیری بیت‌های داده در ساختار همینگ کد پشت سرهم نیست؛ مثلاً آخرین بیت از داده‌ی ارسالی (D7) باید در موقعیت سوم قرار بگیرد. خانه‌های مشخص‌شده با رنگ زرد، محل قرارگیری داده‌ها هستند و خانه‌ی مشخص‌شده با رنگ آبی محل قرارگیری بیت‌های توازن هستند. قبلاً اشاره‌شد که برای ارسال‌های ۸ بیتی، نیاز به ۴ بیت توازن داریم که با نام‌های P1,P2,P4,P8 مشخص شده‌اند. فرض‌کنید قصد داریم داده‌ی 0x9E را ارسال‌کنیم. معادل باینری آن 10011110 می‌شود. با جایگذاری آن، تصویری مطابق شکل‌زیر خواهیم داشت:
حال باید بیت‌های توازن را محاسبه و جایگذاری کنیم. هر بیت توازن در واقع توازن زوج از بیت‌های ۱ است.
به‌عنوان نمونه بیت توازن P1، توازن زوج از بیت‌های ۳ و ۵ و ۷ و ۹ و ۱۱ است. تعداد مقدار ۱ در این چهاربیت، عددزوج ۴ است (تنها بیت ۵ صفر است)؛ بنابراین P1 باید صفر باشد. مابقی بیت‌ها را نیز مطابق فرمول ارائه‌شده درعکس محاسبه می‌کنیم که مقدار P2 یک، مقدار P4 یک و مقدار P8 نیز صفر می‌شود. با جایگذاری داده‌های مورد‌نیاز، داده ارسال می‌شود و در گیرنده دریافت می‌شود؛ اما به‌دلیل نویزهای محیطی، داده با خطا و تغییر بیت D10 از ۱ به صفر دریافت شده است.
گیرنده شروع به محاسبه‌ی بیت‌های توازن می‌کند. باتوجهبه تغییر وضعیت D10 و باتوجهبه تأثیر D10 بر روی P2 و P8، این دوبیت توازن دارای مقداری صحیح نخواهند بود در‌حالی‌که دو بیت توازن P1 و P4 دارای مقداری صحیح هستند.
برای پیداکردن بیتی که دچار خطاشده، کافی‌است که ارزش بیتی P2 و P8 را باهم جمع کنیم؛ یعنی ۸+۲ که می‌شود بیت دهم. همان‌طورکه مشاهده کردید به‌راحتی علاوه‌بر تشخیص خطا، قادر خواهیم‌بود خطای ایجاد‌شده را تصحیح نیز کنیم. همینگ کد کاربرد‌های فراوانی ازجمله در ارتباط‌های رادیویی و شبکه‌ای دارد. این الگوریتم باعث کاهش خطا و رفع آن می‌شود.
منبع: سیسوگ
