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

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

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

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

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

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

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

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

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

در یک ارتباط دیجیتال، راه‌های زیادی برای تشخیص خطا وجود دارد. رایج‌ترین روش تشخیص در ارتباط سریال یا حتی پارالل، قرار دادن بیت توازن (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 که می‌شود بیت دهم.

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

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

 

حمایت از Zeus ‌

خوشحال میشیم برای تداوم و کیفیت ما رو حمایت کنید.

0 نفر

پــــســنــدیـده انـد

توجه

Zeus ‌
Zeus ‌

زئوس هستم ساکن المپ

دیدگاه ها

24 دیدگاه

  • پرسفون :)
    ۵ خرداد ۱۴۰۰

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

    • Sisoog Os
      Sisoog Os
      ۴ مرداد ۱۴۰۰

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

  • k
    ۲ اردیبهشت ۱۳۹۹

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

    • Zeus ‌
      زئوس Zeus
      ۲۴ اردیبهشت ۱۳۹۹

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

  • حسین
    ۲۰ آذر ۱۳۹۸

    سلام .

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

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

    • Zeus ‌
      زئوس Zeus
      ۲۳ آذر ۱۳۹۸

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

    • پرهام
      ۲۸ دی ۱۳۹۹

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

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

      • Sisoog Os
        Sisoog Os
        ۲۸ دی ۱۳۹۹

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

  • محمد
    ۴ آذر ۱۳۹۸

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

    • محمد
      ۴ آذر ۱۳۹۸

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

      • Zeus ‌
        زئوس Zeus
        ۵ آذر ۱۳۹۸

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

      • علیرضا
        ۸ آذر ۱۳۹۸

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

        • Zeus ‌
          زئوس Zeus
          ۹ آذر ۱۳۹۸

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

    • Zeus ‌
      زئوس Zeus
      ۵ آذر ۱۳۹۸

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

  • علی ااا
    ۳۰ اردیبهشت ۱۳۹۸

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

    • Zeus ‌
      زئوس Zeus
      ۳۰ اردیبهشت ۱۳۹۸

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

  • محمدرضا
    ۲۵ اسفند ۱۳۹۷

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

    • Zeus ‌
      زئوس Zeus
      ۲۵ اسفند ۱۳۹۷

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

  • mohamad
    ۱۳ تیر ۱۳۹۷

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

    • Zeus ‌
      زئوس Zeus
      ۱۴ تیر ۱۳۹۷

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

  • شایان
    ۵ اسفند ۱۳۹۶

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

    • Zeus ‌
      زئوس Zeus
      ۲۳ اسفند ۱۳۹۶

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

  • mohammad
    ۲۵ دی ۱۳۹۶

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

پر بحث ترین ها

مسابقه دوم : چالش برنامه نویسی به زبان C

مسابقه اول سیسوگ (مسابقه اول: درک سخت افزار) انتقادهای زیادی رو در پی داشت تا جایی که حتی خودمم به نتیجه مسابقه...

Zeus ‌ Zeus ‌
  • 2 سال پیش

راه اندازی LCD گرافیکی Nokia 1661 و دانلود کتابخانه آن

LCD گرافیکی یکی از مهم ترین پارامترهای موجود در طراحی انواع مدارات الکترونیکی پیچیده و حتی ساده است ، نمایش وضعیت و...

Zeus ‌ Zeus ‌
  • 4 سال پیش

ریموت کدلرن و چکونگی دکد کردن آن به همراه سورس برنامه

ریموت کنترل امروزه کاربرد زیادی پیدا کرده است؛ از ریموت‌های درب بازکن تا ریموت‌های دزدگیر و کنترل روشنایی همه از یک اصول اولیه پیروی می‌کنند و آن‌هم ارسال اطلاعات به‌صورت بی‌سیم است....

Zeus ‌ Zeus ‌
  • 5 سال پیش

همه چیز درباره ریموت کنترل‌های هاپینگ

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

Zeus ‌ Zeus ‌
  • 5 سال پیش

مسابقه سوم: استخراج داده از رشته ها در زبان C

نزدیک به 5 ماه از مسابقه دوم سیسوگ می‌گذره و فکر کردم که بد نیست یک چالش جدید داشته باشیم! البته چالش‌ها...

Zeus ‌ Zeus ‌
  • 2 سال پیش

مسابقه ششم: بزن میکروکنترلر را بسوزون!

بزنم میکروکنترلر را بسوزونم اونم تو  این شرایط!، طراحی مسابقه از اون چیزی که به نظر می‌رسه سخت‌تر است، باید حواست باشه...

Zeus ‌ Zeus ‌
  • 11 ماه پیش

آموزش قدم به قدم راه اندازی +NRF24L01

آموزش قدم به قدم راه اندازی +NRF24L01  با کتابخانه سازگار با انواع میکروکنترلرها و کامپایلرها قبل از اینکه قسمت بشه با ماژول...

رسول خواجوی بجستانی رسول خواجوی بجستانی
  • 3 سال پیش

ساخت ماینر با FPGA و ARM

چند ماهی هست که تب بیت کوین و ارزهای دیجیتال خیلی بالا رفته! چه شد که این پست را نوشتم همانطور که...

Zeus ‌ Zeus ‌
  • 3 سال پیش

کار با ماژول تمام عیار mc60 – قسمت دوم – راه اندازی OpenCPU

در قسمت اول به یکسری اطلاعات کلی ماژول mc60 پرداختیم، با نرم افزار QNavigator کار کردیم و یک هدربرد هم برای کار...

Mahdi.h   Mahdi.h  
  • 3 سال پیش

مسابقه چهارم: کدام حلقه سریع‌تر است؟

حدود ۷ ماه پیش، مسابقه سوم سیسوگ رو برگزار کردیم و کلی نکته در مورد خواندن رشته‌های ورودی را بررسی کردیم. فکر...

Zeus ‌ Zeus ‌
  • 1 سال پیش
سیـــســـوگ

مرجع متن باز آموزش الکترونیک