الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

[hamidreza.nayeri]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

ولی لینکی که داده شد با 4 بیت اضافه کردن فقط میتونه 1 بیت خطا رو تصحیح کنه که!

و اگه دو بیت خطا رخ بده علاوه بر این که نمیتونه تشخیص بده دیتای غلط هم میده!
برای این مشکل راه حلی دارید؟

متاسفانه من جزوات دانشگاهیم رو گم کرده ام.
اون تو نوشته بود که چطور میشه با ۳ بیت ۲ بیت رو تشخیص داد و ۱ بیت رو تشخیص و اصلاح کرد.
اگر یک سرچ ساده در خصوص Hamming Code انجام بدید به نظرم میتونید روشش رو پیدا کنید.

[hamidreza.nayeri]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

این دو دو مبحث کاملا جدا از هم هستند. منچستر سیستم ارسال دیتا و همینک سیستم کد گذاری و خطایابی هستش. منظورتونم از کلمه ماجولاتور باز بکنید ممنون میشم. حداقل یاد میگیریم معنیشو

منظورم همون چیزی بود که شما نوشته بودید. ماجولاتور یعنی روشی که دیتای دیجیتال روش سوار میشه و بعد ارسال میشه.
من وقتی متنتون رو میخوندم اشتباهی فکر کردم که از ماجولاتور به عنوان سیستم تشخیص خطا نام بردید.

[hamidreza.nayeri]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

ببخشید آقای وزیری یه سوال دارم از اونجایی که شما کار کردین میگم.
توی این سیستم همینگ اگه 2 تا بیت با خطا دریافت بشه چه طور باید فهمید؟
این جوری که من فهمیدم اگه دو تا بیت با خطا دریافت بشه علاوه براین که نمیتونه تشخیص بده اطلاعات اشتباهی به خروجی میده!
این مشکل رو چه طور میشه حل کرد؟؟

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

[Mahdi_Vaziri]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

ببخشید آقای وزیری یه سوال دارم از اونجایی که شما کار کردین میگم.
توی این سیستم همینگ اگه 2 تا بیت با خطا دریافت بشه چه طور باید فهمید؟
این جوری که من فهمیدم اگه دو تا بیت با خطا دریافت بشه علاوه براین که نمیتونه تشخیص بده اطلاعات اشتباهی به خروجی میده!
این مشکل رو چه طور میشه حل کرد؟؟

هر چند بیت خطا باشه تشخیص داده میشه. فقط تو این سیستم کیتونید با توجه به حجم کدکزاری تصحیح داشته باشید. برای درک موضوع بعد از لینکی که بهتون دادم یه نگاهی به صفحات 274 تا 277 موریس مانو بزنید. اونجا گفته تا دو بیت رو چطور میتونید تصحیح بکنید. ولی مطمئن باشید هر چندبیت خطا باشه تشخیص داده میشه.

معذرت میخوام مشغول کاری هستم نمیتونم توضیح بدم.

[Mohammad Sadegh Rostami]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

سلام مجدد
خداروشکر بحث داره خوب پیش میره
یک لینک میذارم
برای کد همینگ سیستماتیکه
از نوع (4و7) هستش
یعنی 4 بیت داده داری
3 بیت رو اضافه میکنی
قابلیت اصلاح 1 بیت هم داره
روشش هم خیلی واضحه
با look up table براحتی میتونی پیاده سازیش کنی
چون حالت های ممکنش رو داده
برای کار با میکرو هم مناسبه
چون داده ها 4 بیت 4 بیت میشه
آخرش میشه 7 بیت
که میتونی بکنی 8 بیت (یک بیت همینطوری، پیش فرض بذار)
ارسالش کنی
یعنی مثلا اگه میخوای 24 بیت داده بفرستی
میشه 48 بیت
که قابلیت اصلاح 6 بیت موجوده!
یعنی از 24 بیت، 6 بیت اگه خطا داشته باشه اصلاح میشه!
مقدار خوبیه
اینم لینکش:
http://www.dsplog.com/2009/09/29/ham...sion-decoding/
...
:read:

[eca.samani]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

سلام مجدد
خداروشکر بحث داره خوب پیش میره
یک لینک میذارم
برای کد همینگ سیستماتیکه
از نوع (4و7) هستش
یعنی 4 بیت داده داری
3 بیت رو اضافه میکنی
قابلیت اصلاح 1 بیت هم داره
روشش هم خیلی واضحه
با look up table براحتی میتونی پیاده سازیش کنی
چون حالت های ممکنش رو داده
برای کار با میکرو هم مناسبه
چون داده ها 4 بیت 4 بیت میشه
آخرش میشه 7 بیت
که میتونی بکنی 8 بیت (یک بیت همینطوری، پیش فرض بذار)
ارسالش کنی
یعنی مثلا اگه میخوای 24 بیت داده بفرستی
میشه 48 بیت
که قابلیت اصلاح 6 بیت موجوده!
یعنی از 24 بیت، 6 بیت اگه خطا داشته باشه اصلاح میشه!
مقدار خوبیه
اینم لینکش:
http://www.dsplog.com/2009/09/29/ham...sion-decoding/
...
:read:

ممنون
بله این جوری خب خیلی بهتره.
ولی یه مشکلی هست:
تو همینگ (4و7) که لینکشو دادید اگه به جای یک بیت 2 بیت از دیتا تخریب بشه دیتای اشتباهی به سیستم میده و این خیلی بده.
یه جا خوندم که نوشته بود بیت هشتم رو پریتی کل میزاریم و این جوری میتونه 2 بیت خطا رو تشخیص بده و یک بیت رو اصلاح کنه.
تو این روش باز هم اگه 3 بیت با خطا دریافت بشه اطلاعات اشتباهی به سیستم میده.
که البته میشه با یکسری پردازش های دیگه فهمید که آیا دیتا تخریب شده یا نه ولی احتمال وجود خطا باز هم زیاده.
اینو چه کار میشه کرد؟

[Mohammad Sadegh Rostami]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

ممنون
بله این جوری خب خیلی بهتره.
ولی یه مشکلی هست:
تو همینگ (4و7) که لینکشو دادید اگه به جای یک بیت 2 بیت از دیتا تخریب بشه دیتای اشتباهی به سیستم میده و این خیلی بده.
یه جا خوندم که نوشته بود بیت هشتم رو پریتی کل میزاریم و این جوری میتونه 2 بیت خطا رو تشخیص بده و یک بیت رو اصلاح کنه.
تو این روش باز هم اگه 3 بیت با خطا دریافت بشه اطلاعات اشتباهی به سیستم میده.
که البته میشه با یکسری پردازش های دیگه فهمید که آیا دیتا تخریب شده یا نه ولی احتمال وجود خطا باز هم زیاده.
اینو چه کار میشه کرد؟

یعنی هدف شما اینه که مطمئن بشی همه ی داده ها صحیح رسیدن؟
خب باید دنبال کدی باشیم که تعداد بیتهای اصلاح خطا با بیت های داده برابر باشن!
و این مستلزم این میشه که n بزرگ بشه
و در اینصورت روش پیچیده تر میشه!
و کار پردازش داده ها بیشتر میشه!
میشه از روش های دیگه ای هم استفاده کرد تا متوجه بشی داده غلط بوده!
مثلا به جای یک بار، سه بار بفرست یا 10 بار بفرست!
بعد با هم مقایسه کن!
اگه اشتباه بود، باید دوباره ارسال شه!
اما میدونی چه مشکلی هست؟
اینکه کدی نیست که n بیت بفرسته و همه رو بشه اصلاح کرد!
میدونی چی میخوام بگم؟
یعنی حالا اومد کدی ساختی که مثلا (4و12) بود
یعنی 4 تا داده رو با 8 تا اضافه میفرستی
حالا فرض کن 4 تا رو هم اصلاح کنه
اما این 4 تا اصلاح در 12 بیت رخ میده!
یعنی اینکه در این 12 بیت هرجا خطا باشه پیدا میشه
یعنی امکان داره یکی از خطاها در خود بیت اضافه شده رخ بده!
بنابراین نمیشه انتظار داشت روشی که استفاده میشه
فقط و فقط داده های ما رو اصلاح کنه!
از ترکیب روش های مختلف برای اطمینان صحت ارسال استفاده میشه!
یه مقدار سخت افزاری
یه مقدار نرم افزاری
و ...
... :read:

[RubeuS]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

سلام .
همینگ کد یکی از مباحثیه که در قسمت اول مدارهای منطقی مطرح میشه. همینطور که دوستان گفتند تشخیص خطا ( Error Detection ) و تصحیح خطا ( Error Correction ) به فاصله ی دستورات مختلف بستگی دارد (دیتا) .
شما به عنوان مثال دیتای 4 بیتی داری میای با اضافه کردن چندبیت فاصله بین دیتات رو زیاد میکنی. اگر معمولی بفرستی یعنی فاصله 1 هست. اگه باش parity بفرستی فاصله مینیمم دو میشه و...

نکته مهم:
اگر فاصله بین دو دستور d باشد ، گیرنده قادر است حداکثر d-1 خطا را تشخیص دهد ( detect ) یا میتواند حداکثر قدرمطلق 2/(d-1) خطا را تصحیح کند.(کتاب مدارهای منطقی - مولف هادی یوسفی - صفحه ی 12 - پاراگراف 2 - خطوط 4 و 5 )
کد همینگ مرسوم کد با فاصله ی 3 میسازد.
پس میتواند 2 خطا تشخیص یا یک خطا تصحیح کند.

برای ساخت کد همینگ بایستی دیتا به چند دسته تقسم شود و هر دسته یک parity بگیرد و زمانی که کد دریافت میشود باید دسته های مختلف از نظر parity error چک شود و با استفاده از نتیجه ی دسته های مختلف ، میتوان بیت اشتباه را تصحیح کرد.( هرچه قدر تعداد دسته ها زیاد تر شود ، فاصله بیشتر ، اور هد بیشتر)

برای اطلاعات بیشتر به سایت مکتب خونه - مدارهای منطقی - استاد تابنده( استاد تمام دانشگاه شریف) - قسمت 3 مراجعه شود.

[mahdi421]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

Error Correction Codes for Wireless Communication Systems

http://www.realworldengineering.org/download.php?proj=86&file=RWEP_Final1_12_Backg round_lecture.pptx

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

[hamidreza.nayeri]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

ممنون
بله این جوری خب خیلی بهتره.
ولی یه مشکلی هست:
تو همینگ (4و7) که لینکشو دادید اگه به جای یک بیت 2 بیت از دیتا تخریب بشه دیتای اشتباهی به سیستم میده و این خیلی بده.
یه جا خوندم که نوشته بود بیت هشتم رو پریتی کل میزاریم و این جوری میتونه 2 بیت خطا رو تشخیص بده و یک بیت رو اصلاح کنه.
تو این روش باز هم اگه 3 بیت با خطا دریافت بشه اطلاعات اشتباهی به سیستم میده.
که البته میشه با یکسری پردازش های دیگه فهمید که آیا دیتا تخریب شده یا نه ولی احتمال وجود خطا باز هم زیاده.
اینو چه کار میشه کرد؟

همینگ به درد این شرایط نمیخوره.
مال زمانی کارایی داره که تعداد خطاهاتون کم باشه. مثلا ۱ بیت در هر ۸ بیت.
اگر محیطتون نویزیه و باعث میشه خطا زیاد بشه استفاده از همینگ اصلا به صرفه نیست و خطرناک هم هست (میشه وسط راه اطلاعات رو دستکاری و خراب کرد حتی اگر رمزنگاری کنید.)
به نظرم اگر محیتتون خیلی نویزیه با استفاده از CRC32 یا SHA1 و ... هر پاکت دیتا رو براش محاسبه کنید تا حتی اگر ۱۰۰ بیتتون هم خراب شد متوجه بشید و دیتا رو دوباره ارسال کنید.
متاسفانه راه دیگه ای به ذهنم نمیرسه.

[Mohammad Sadegh Rostami]

پاسخ : الگوریتم های رمزگذاری و خطایابی در ارتباط بیسیم

Error Correction Codes for Wireless Communication Systems
http://www.realworldengineering.org/download.php?proj=86&file=RWEP_Final1_12_Backg round_lecture.pptx
توی این پاورپوینت یه الگوریتم برای همین مورد هست که من ازش سر در نیاوردام اگه این روش رو بشه تحلیل کرد احتمالا همه چی حله

دستت درد نکنه
مطلب قشنگی فرستادی
دو نوع کدینگ رو داخلش گفته بود
اما باید یک نکته ای رو دقت کرد!
[glow=red,2,300]کانال[/glow]
یعنی چی؟
یعنی اینکه باید بدونیم کانال ارتباطی ما در چه وضعیتیه
و بعد براش کدینگ مورد نظر رو طراحی کنیم!
یعنی وضعیت کانال تاثیر مستقیم بر روی کدینگ داره!
بذار مثال بزنم:
فرض کن یک کانالی رو بررسی میکنی
میبینی خطای این کانال 1 بیت در 1000 بیته!
یعنی از هر 1000 بیت، شاید 1 بیت خطا بده!
اما یک کانال دیگه مثلا از هر 10 بیت 3 بیت خطا میده!
خب حالا طراحی ما برای این دوتا ثابته؟
مشخصه که نه!
در اولی داره میگه شما به طور میانگین اگه 1000 تا بفرستی
شاید! یک بیت خطا ایجاد بشه!
دومی میگه 10 تا بفرستی، 3 تا!
حالا شما میخوای داده هات رو در پکت های مثلا 64 بیتی بفرستی
در حالت اول به طور میانگین در هر 15 تا ارسال شاید یک بیت خطا داشته باشی
اما در حالت دوم در ارسال 64 بیت، بیش از 18 بیت خطا ممکنه داشته باشی!

پس شما اول وضعیت کانالت رو بررسی کن
ببین به طور میانگین در هر ارسال چقدر خطا داری؟
بعد بشینیم کدشو طراحی کنیم!