معرفی, امنیت و نفوذ, توصیه شده, مقاله های سیسوگ

آشنایی با همینگ کد و لذت یک ارتباط امن و بدون خطا

آشنایی با همینگ کد و لذت یک ارتباط امن و بدون خطا

ارتباط! بله مقوله‌ی مهم عصر جدید، ارتباط است. ارتباط انسان و ماشین، ارتباط با آدم فضایی‌ها، ارتباط ماشین با ماشین و یا حتی ارتباط انسان با انسان. در برقراری ارتباط همیشه چالشی نهفته است و آن‌هم تفهیمِ مفهوم است؛ این که سعی کنید به نحوی مطلب را بیان کنید که مخاطب منظور شما را متوجه شود. شاید در نگاه اول چنان مقوله مهمی به نظر نرسد ولی فرض کنید انسان‌ها توانسته باشند تمدنی در منظومه شمسی را شناسایی کنند و سعی کنند برای آن‌ها پیامی از صلح و دوستی ارسال کنند. حال اگر تمدن مذکور آن پیام را تهدید یا دعوت به جنگ استنباط کند، چه اتفاقی روی خواهد داد؟!

یا فرض کنید دو دستگاه در خط تولید یک کارخانه، اطلاعاتی را با هم تبادل می‌کنند. اگر عوامل محیطی باعث شوند که اطلاعات به‌صورت صحیح بین دستگاه‌ها رد‌و‌بدل نشود، قاعدتاً عملکرد دستگاه‌ها مختل خواهد شد! مسئله‌ی چالش‌بر‌انگیز هر ارتباطی، صحت آن است؛ این که به نحوی گیرنده‌ی پیام مطمئن باشد منظور شما از پیام چیست و هیچ‌گونه شکی در آن وجود نداشته باشد. اما چطور می‌توان به این مهم دست پیدا کرد؟ چطور می‌شود پیام‌ها را به نحوی انتقال داد که گیرنده از صحت آن‌ها اطمینان حاصل کند؟ برای روشن شدن مسئله با سیسوگ همراه شوید. ما در این مقاله به بررسی یکی از راه‌های خطایابی ارتباط‌ها می‌پردازیم.

معرفی کانال‌های ارتباطی

اگرچه زیاد فرقی نمی‌کند که کانال ارتباطی چه باشد، صوت یا نوشتار، آنالوگ یا دیجیتال، سریال یا پارالل، دیفرانسیلی یا غیر دیفرانسیلی اما همه و همه در برابر عوامل بیرونی (نویز) تأثیر پذیر هستند و ممکن است صحت آن‌ها دچار تغییر شود. البته منکر این مهم نیستیم که بنا به ماهیت، تأثیر پذیری برخی از آن‌ها از عوامل خارجی، کم است ولی تغییر ناخواسته اجتناب‌ناپذیر است و نمی‌توان مطمئن بود که اطلاعات در مسیر دستخوش تغییر نشده‌اند.

ممکن است برای انتقال از پروتکل سریال یا مودم‌های آنالوگ یا حتی ارتباط رادیویی استفاده کرده باشید. در این مقاله، بستر انتقال اطلاعات چندان دارای اهمیت نیست، مسئله‌ی مهم این است که اطلاعات دریافتی (از هر بستری) صحیح است یا اشتباه؟

بررسی اجمالی راه‌های خطایابی

در یک ارتباط دیجیتال، راه‌های زیادی برای تشخیص خطا وجود دارد. رایج‌ترین روش تشخیص در ارتباط سریال یا حتی پارالل، قرار دادن بیت توازن (Parity bit) است. طبق تعریف بیت توازن می‌تواند زوج یا فرد باشد.

هنگامی‌که از توازن زوج استفاده می‌شود، اگر تعداد یک‌های ورودی زوج باشد، بیت توازن صفر می‌شود و بالعکس

هنگامی‌که از توازن فرد استفاده می‌شود، اگر تعداد یک‌های ورودی فرد باشد، بیت توازن صفر می‌شود و بالعکس.

اما این روش خود دارای خطا است و ممکن است شرایطی ایجاد شود که خطا تشخیص داده نشود. مثلاً فرض کنید نویز باعث تغییر جای بیت‌ها شده باشد. گیرنده با توجه به وضعیت Parity متوجه نخواهد شد که جایگاه دو بیت تعویض شده است، چرا‌که تناسب بیت‌های 1 به هم نخورده است. یا این که نویز باعث تغییر وضعیت دو بیت در داده‌های ارسالی شده باشد.

همان‌طور که می‌بینید Parity bit روش خوبی است اما باز احتمال خطا هرچند کم، ولی وجود دارد.

یکی دیگر از روش‌های مورد‌استفاده در خطایابی، قرار دادن یک بایت انتهای بایت‌های ارسالی است. فرض کنید قرار است 10 بایت داده را منتقل کنیم، یک بایت 11 ام هم در نظر می‌گیریم که حاصل جمع 10 بایت اول را در خود جای داده است. این روش را checksum گویند. این روش نیز دارای خطا است. اگر موقعیت بایت‌ها عوض شود، همچنان توسط گیرنده قابل‌تشخیص نیست. برای بهتر شدن می‌توان به‌جای حاصل جمع، از الگوریتم CRC نیز استفاده کرد که به محل قرار‌گیری بایت‌ها نیز حساس است ولی همچنان خالی از احتمال خطا نخواهد بود.

البته صدها روش مشابه دیگر هم وجود دارند. همه‌ی این روش‌ها برای تشخیص خطا هستند و به ما می‌گویند داده‌های ارسالی به دلایلی دارای صحت نیستند و در مسیر، دستخوش تغییر شده‌اند.

اما آیا روشی وجود دارد که با استفاده از آن بتوانیم داده‌های دریافتی که دارای خطا هستند را ترمیم کنیم و دیتای صحیح را از آن استخراج کنیم؟

همینگ کد چیست؟

ریچارد همینگ

همان‌طور که اشاره شد، روش‌های زیادی برای پیدا کردن خطای داده‌های ارسالی وجود دارد. اما چطور می‌شود بعد از شناسایی خطای مربوطه، آن را ترمیم کرد؟ در این حوزه نیز الگوریتم‌ها و پروتکل‌های مختلفی وجود دارد. یکی از این روش‌ها، روش همینگ است. ریچارد همینگ ریاضیدان آمریکایی (سومین برنده‌ی جایزه تورینگ)، مقاله‌ی مشهور خود را در سال 1950 هنگامی‌که در شرکت IBM مشغول به کار بود منتشر کرد. این مقاله درباره‌ی آشکارسازی و تصحیح خطا بود و مفاهیم کد همینگ، فاصله‌ی همینگ و پنجره‌ی همینگ را تعریف کرد.

در کد همینگ گیرنده علاوه بر تشخیص صحیح خطا (بر‌خلاف بیت توازن و checksum، قادر به اصلاح خطا نیز است. البته توجه داشته باشید که هر الگوریتمی محدودیت‌های خاص خود را دارد. کد همینگ فقط قادر به تصحیح یک بیت است ولی به‌درستی خطاهای اتفاق افتاده را تشخیص می‌دهد.

همینگ کد چطور کار می‌کند؟

برای روشن شدن هرچه بیشتر قضیه و نگاه کاربردی به آن، سعی می‌کنیم که همینگ کد را در قالب یک مثال ساده آموزش دهیم. فرض کنید که قصد داریم داده‌ای را از یک فرستنده به گیرنده‌ای ارسال کنیم. داده ما 8 بیت طول دارد. برای تصحیح خطا در داده‌های 8 بیتی بنا به نظریه‌ی فاصله‌ی همینگ، نیاز به 4 بیت داده‌ی تصحیح خطا خواهیم داشت. پس در مجموع برای ارسال 8 بیت داده با استفاده از همینگ کد، نیاز به 12 بیت خواهیم داشت.

چینش داده ها در ارسال همینگ کد

 

همان‌طور که در تصویر فوق مشاهده می‌کنید، محل قرارگیری بیت‌های داده در ساختار همینگ کد پشت سرهم نیست؛ مثلاً آخرین بیت از داده‌ی ارسالی (D7) باید در موقعیت سوم قرار بگیرد. خانه‌های مشخص‌شده با رنگ زرد، محل قرار‌گیری داده‌ها هستند و خانه‌ی مشخص‌شده با رنگ آبی محل قرارگیری بیت‌های توازن هستند. قبلاً اشاره شد که برای ارسال‌های 8 بیتی، نیاز به 4 بیت توازن داریم که با نام‌های P1,P2,P4,P8 مشخص شده‌اند.

فرض کنید قصد داریم داده‌ی 0x9E را ارسال کنیم. معادل باینری آن 10011110 می‌شود. با جای گذاری آن، تصویری مطابق شکل زیر خواهیم داشت:

محل قرارگیری بیت های توازن در همینگ کد

حال باید بیت‌های توازن را محاسبه و جای گذاری کنیم. هر بیت توازن در واقع توازن زوج از بیت‌های 1 است.

فرمول محاسبه همینگ کد

 

به‌عنوان‌ نمونه بیت توازن P1، توازن زوج از بیت‌های 3 و 5 و 7 و 9 و 11 است. تعداد مقدار 1 در این چهار بیت، عدد زوج 4 است (تنها بیت 5 صفر است)؛ بنابراین P1 باید صفر باشد. مابقی بیت‌ها را نیز مطابق فرمول ارائه‌شده در عکس محاسبه می‌کنیم که مقدار P2 یک، مقدار P4 یک و مقدار P8 نیز صفر می‌شود.

با جای گذاری داده‌های مورد‌نیاز، داده ارسال می‌شود و در گیرنده دریافت می‌شود؛ اما به‌ دلیل نویزهای محیطی، داده با خطا و تغییر بیت D10 از 1 به صفر دریافت شده است.

ایجاد خطا در پکت همینگ کد

گیرنده شروع به محاسبه‌ی بیت‌های توازن می‌کند. با توجه به تغییر وضعیت D10 و با توجه به تأثیر D10 بر روی P2 و P8، این دو بیت توازن دارای مقداری صحیح نخواهند بود در‌حالی‌که دو بیت توازن P1 و P4 دارای مقداری صحیح هستند.

تشخیص محل خطا با توجه به بیت های توازن

برای پیدا کردن بیتی که دچار خطا شده، کافی است که ارزش بیتی P2 و P8 را با هم جمع کنیم؛ یعنی 2+8 که می‌شود بیت دهم.

همان‌طور که مشاهده کردید به‌راحتی علاوه بر تشخیص خطا، قادر خواهیم بود خطای ایجاد‌شده را تصحیح نیز کنیم. همینگ کد کاربرد‌های فراوانی از جمله در ارتباط‌های رادیویی و شبکه‌ای دارد. این الگوریتم باعث کاهش خطا و رفع آن می‌شود.

برای درک بهتر می‌توانید به ویدئوی زیر توجه کنید:

 

انتشار مطالب با ذکر نام و آدرس وب سایت سیسوگ، بلامانع است.

شما نیز میتوانید یکی از نویسندگان سیسوگ باشید.   همکاری با سیسوگ

27 دیدگاه در “آشنایی با همینگ کد و لذت یک ارتباط امن و بدون خطا

  1. Avatar for فاطمه فاطمه گفت:

    میشه یکی خیلی ساده تر بهم توضیح بده
    @f_nadeali82
    اگه کسی میدونه اینستاگرام پیام بده

    1. Avatar for Zeus ‌ Zeus ‌ گفت:

      سلام دوست عزیز
      اگر بتونید بگید کجای مقاله گنگ بود یا به دنبال چه چیزی بودید که پیدا نکردید تا در صورت نیاز مقاله رو کامل تر کنیم خیلی بهتره

  2. Avatar for پرسفون :) پرسفون :) گفت:

    مرسی خیلی مفید بود ^_^

    1. Avatar for Sisoog Os Sisoog Os گفت:

      خواهش میکنم دوست عزیز

  3. Avatar for k k گفت:

    سلام وقت بخیر فرمول محاسبه خطاpرو از کجا پیدا کنم؟
    خیلی گشتم ولی پیدا نکردم

    1. Avatar for زئوس Zeus زئوس Zeus گفت:

      ببخشید سوالتون رو متوجه نشدم !
      اگه منظورتون بیت توازن هست که بسته یه زوج و فرد بودن توازن به سادگی فابل محاسبه است
      مثل بیت توازن توی پروتکل سریال

  4. Avatar for حسین حسین گفت:

    سلام .

    به نظرم این الگوریتم اون قدر ها هم قابل اطمینان نیست.
    به این علت که ، اگر بیتهای داده ممکن هست دچار خطا بشن ، پس چرا بیتهای p1 , p2 , p3 , p4 دچار خطا نشن .!!!! اونوقت سیستم . فکر میکنه داده ای که دریافت کرده اشتباه هست و سعی میکنه اصلاحش کنه که درنتیجه داده درست رو تغیر میده و یک داده اشتباه تحویل میده .
    البته احتمال خطا رو کم میکنه مثلا: اگر فرضکنیم هنگام ارسال یک بایت خطا اتفاق بیفته احتمال شناسایی نشدن اون برای الگوریتم همینگ 4/12 معادل 33.3% ( تعدادبیتهای خطایابی به کل بیتها)
    و این مقدار برای بیت توازن 1/9 یا کمی بیش از 11% هست .
    به نظر میاد بیت توازن درصد صحتش بالاتر باشه . البته مزیت همینگ که تصحیح داده ست رو نداره ولی میشه داده رو دوباره ارسال کرد .

    درکل روش همینگ به لحظ ریاضی بسیار زیباست .
    سپاس بابت مطلب خوبتون .

    1. Avatar for زئوس Zeus زئوس Zeus گفت:

      به لحاظ ریاضی که جواب میده – و واقعا میشه با اطمینان گفت که ریاضی اشتباه نمیکنه !!!
      لازمه کامل کنم هیچ چیزی صد در صد قابل اتکا نیست در دنیای واقعی — خفن ترین چیزی که دو دنیای رمز گذاری دارن مثلا md5 و امثالهم هم نمیشه گفت صد در دصد درست کار میکنند
      همینگ از بیت توازن خیلی بهتر عمل میکنه 🙂

    2. Avatar for پرهام پرهام گفت:

      اولا باید بدونید که این روش برای تصحیح یک بیت خطا کاربرد داره یعنی اگه بیشتر از یک بیت خطا رخ بده نمیتونه درست تشخیص بده.

      حالا جواب سوال شما:برای تصحیح یک بیت خطا کاملا قابل اطمینان هست. اونجایی که میگین ممکنه بیت‌های P1,P2,… دچار خطا بشن کاملا صحیحه. ولی این مشکل زا نیست. با همین روشی که دوستمون در متن گفتن به راحتی میشه فهمید این بیت‌ها دچار خطا شدن یا نه و تصحیح کنیم که البته نیازی نیست چون داده اصلی ما نیستن.
      مثلا در مثال بالا اگر در سمت گیرنده به جای 8+2 داشته باشیم 1 اونوقت یعنی بیت اول دچار خطا شده که بیت p1 هست. پس دیدیم که میشه تشخیص داد.
      این فقط یک نظریه ریاضی من درآوردی نیست و کاملا دقیق هست. اصلا به خاطر همین مخترعش ریچارد همینگ معتبرین ترین جایزه حوضه علوم کامپیوتر(جایزه تورینگ) رو گرفت!
      البته تو این مقاله کامل توضیح داده نشده واسه همون این برداشت غلط رو کردین.

      1. Avatar for Sisoog Os Sisoog Os گفت:

        ممنون بابت توضیحاتتون

    3. Avatar for ایریفکو ایریفکو گفت:

      خب کاری نداره که ….
      امتحان کنید
      وقتی بیت های کنترلی دچار خطا بشن همچنان ایندکس همون بیت کنترلی رو تو خروجی دارید
      فقط کافیه در اخر با خود همون بیت کنترلی ایکس اورش کنید اگه برابر باشه میشه صفر اگه نباشه میشه یک
      اینجوری اگر بیت ۸ دچار خطا باشه تنها جمله ایی که بیت هشت رو داره P4 هست که خب میشه ۱۰۰۰ برابر با ۸ :)))

  5. Avatar for محمد محمد گفت:

    مثل همیشه بی نظیر ..ای کاش مهندس checksumوcrcرو هم با مثال و کد هایی توضیح میدادید..ممنون

    1. Avatar for محمد محمد گفت:

      مهندس اگر بیش از یک بیت تغییر کرده باشه باچه الگوریتمی میشه تصحیح کرد؟؟

      1. Avatar for زئوس Zeus زئوس Zeus گفت:

        برای تحصیح الگوریتمی نمیشناسم ولی الگوریتیم های زیادی وجود دارند که تشخصی دهند 🙂

      2. Avatar for علیرضا علیرضا گفت:

        الگوریتم golay که ناسا ازش استفاده میکنه

        1. Avatar for زئوس Zeus زئوس Zeus گفت:

          سلام جالبه – توی ویکی پدیا دیدم ولی این چند بیت رو اصلاح میکنه باید بیشتر تحقیق کنم
          ممنونم برای معرفی این الگورتیم

    2. Avatar for زئوس Zeus زئوس Zeus گفت:

      ممنونم دوست عزیز
      اگر فرصت بشه به اینها هم خواهیم پرداخت 🙂

  6. Avatar for علی ااا علی ااا گفت:

    فوق العاده بود

    1. Avatar for زئوس Zeus زئوس Zeus گفت:

      متشکرم دوست عزیز

  7. Avatar for محمدرضا محمدرضا گفت:

    بسیار عالی .فیلم خیلی خوب بود اما متاسفانه توی توضیحاته متنیتون اشتباه دارید که با اینکه قبلا تو نظرات ازتون خواستن ویرایشش کنید ولی هنوز همون اشتباهه هست..من اولش دودل بودم کدوم یکی درسته

    1. Avatar for زئوس Zeus زئوس Zeus گفت:

      سلام دوست عزیز ؛ خواهش می کنم ، عکس ها اصلاح شدند ؛ متشکر برای تذکرتون 🙂

  8. Avatar for mohamad mohamad گفت:

    بینظیر بود
    ممنون

    1. Avatar for زئوس Zeus زئوس Zeus گفت:

      خواهش میکنم دوست عزیز

  9. Avatar for شایان شایان گفت:

    ممنون عالی توضیح دادی

    1. Avatar for زئوس Zeus زئوس Zeus گفت:

      خواهش میکنم دوست عزیز
      خوشحالم که مورد توجه قرار گرفته

  10. Avatar for mohammad mohammad گفت:

    فیلمی که در اینباره انتشار داده بودید کاملا آموزنده و دقیق بود اما متاسفانه با خطایی که در توضیحات داشتید خواننده را به گمراهی می اندازید خصوصا اگر کسی فیلم مربوطه را ندیده باشد خطا در این است که اعداد Parity به ترتیب 0011 میباشد که به خطا 0110 نوشته شده است امیدوارم تصحیح بفرمایید با تشکر

    1. Avatar for زئوس Zeus زئوس Zeus گفت:

      بله درسته
      متشکر

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *