فاصله همینگ حداقل ۱ هست.شما کافیه دوتاعدد که فاصله همینگشون یکه رو درنظربگیرین.مث۰۱۱ و۱۱۱ حالااگه بیت توازن زوج درنظربگیریم.بیت توازن ۰۱۱ میشه ۰ وبیت توازن ۱۱۱ میشه ۱،پس فاصله همینگ میشه دو!

(۲۹ آذر ۱۳۸۹ ۱۰:۵۷ ب.ظ)sal_dovomi نوشته شده توسط:  فاصله همینگ حداقل ۱ هست.

پس میتونه بیشتر هم باشه.
ولی تو کتاب پوران پژوهش نوشته بود که با فاصله همینگ d میشه d-1/2 بیت رو تصحیح کرد و بهمین دلیل اگه از بیت توازن استفاده کنیم نمیشه خطا‌ها رو تصحیح کرد. چون در صورت استفاده از بیت توازن d=2 میشه.ولی شما فرمودین که حداقل ۱ هست و با توازن میشه ۲/ پس بیشتر هم میتونه باشه و در اونصورت تصحیحش هم میشه کرد؟
راستش من گیج شدم.مفهوم فاصله همینگ رو هم میدونم ولی اگه میشه با یه مثال همین مطلب رو که درصورت استفاده از بیت توازن فاصله همینگ ۲ میشه رو توضیح بدین. فاصله همینگ اطلاعات ارسالی رو با چه داده ای باید بدست بیاریم تا متوجه بشیم که d=2. با تشکر

(۲۹ آذر ۱۳۸۹ ۱۰:۵۷ ب.ظ)sal_dovomi نوشته شده توسط:  فاصله همینگ حداقل ۱ هست.شما کافیه دوتاعدد که فاصله همینگشون یکه رو
ف درنظربگیرین.مث۰۱۱ و۱۱۱ حالااگه بیت توازن زوج درنظربگیریم.بیت توازن ۰۱۱ میشه ۰ وبیت توازن ۱۱۱ میشه ۱،پس فاصله همینگ میشه دو!

فرمایش جنابعالی متین.اما تو کتاب که نگفته در صورتی که فاصله همینگ حداقل باشه(یعنی یک باشه)استفاده از بیت توازن فاصله همینگو میکنه ۲!
تو کتاب گفته در صورت استفاده از بیت توازن فاصله همینگ میشه ۲/یعنی قبلا هرچی بوده حالا دیگه میشه ۲/
لطفا راهنماییم کنید.

---

(۳۰ آذر ۱۳۸۹ ۰۴:۴۴ ق.ظ)bijibuji نوشته شده توسط:  

(29 آذر ۱۳۸۹ ۱۰:۳۶ ب.ظ)sos006 نوشته شده توسط:  با سلام.بنده تو کتاب شبکه تنن باوم مطلبی دیدم که دلیلشو نفهمیدم.اون مطلب هم این بود که استفاده از بیت توازن در ارسال اطلاعات فاصله همینگ آن را برابر ۲ میکند.چرا؟

حالا فرض کنید ۳ بیت از الگوی زیر دچار اشکال بشه:
۱۱۱۱۰۰۰۰
و تبدیل بشه به:
۰۱۱۱۰۰۰۰

اما اینجا که یه بیت تغییر کرده(فقط بیت آخر.)
فکر کنم از همون مثالهای قشنگت که گفتی بزنی بهتر باشه.

متوجه نشدم چی گفتین.ولی فاصله همینگ همیشه عددکمترهست.مثلن اگه سه تاعدد داریم که دوبه دو فاصله همینگها مثلن ۳و۴و۵باشن،ماهمیشه عددکمتر یعنی ۳روبه عنوان فاصله همینگ میگیریم.توی مثال شماهم بابیت توازن فاصله همینگ شده۲.میتونه بیشترباشه ولی مابایدکمتره بگیریم.چون بیشترااصلافاصله همینگ نیستن.وطبق نکته۲/۲ تا بیت رومیتونه تصحیح کنه.نمیدونم متوجه شدین؟البته من بااطمینان ۱۰۰درصدمطمین نیستم جوابم درست باشه.طبق دانش خودم دارم میگم.

(۲۹ آذر ۱۳۸۹ ۱۰:۳۶ ب.ظ)sos006 نوشته شده توسط:  با سلام.بنده تو کتاب شبکه تنن باوم مطلبی دیدم که دلیلشو نفهمیدم.اون مطلب هم این بود که استفاده از بیت توازن در ارسال اطلاعات فاصله همینگ آن را برابر ۲ میکند.چرا؟

به این کلمات نگاه کنید:

پستانک
رستانه

فکر کنید در فرهنگ لغات ما فقط همین ۲ کلمه هست و بس
می خوایم این کلمات رو با ترتیب تصادفی ارسال کنیم و می خوایم که گیرنده بدونه که منظور ما در هر ارسال کدوم کلمه بوده.

اختلاف این دو کلمه در ۲ حرفه. یعنی اگر دو حرف( و اون هم حروف اول و آخر )از هر یک از این دو کلمه رو تغییر بدیم به دیگری تبدیل می شه.

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

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

لپ کلام اینه که ما همیشه یه سری حالت قابل قبول داریم. به عبارتی هر چیدمانی از n بیت اگر معتبر باشه، این قصه فاصله همینگ و ... همه اش تبدیل به کشک می شه.

مثلا حالات معتبر اینها هستند:

۰۰۰۰۱۱۱۱
۱۱۱۱۰۰۰۰
۰۰۰۰۰۰۰۰
۱۱۱۱۱۱۱۱

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

حالا فرض کنید ۳ بیت از الگوی زیر دچار اشکال بشه:

۱۱۱۱۰۰۰۰

و تبدیل بشه به:

۰۱۱۱۰۰۰۰

گیرنده می فهمه که در اولین بیت از سمت چپ خطا رخ داده و الگوی اصلی:

۱۱۱۱۰۰۰۰

بوده. اما یه سوال پیش میاد. از کجا معلوم که الگوی اصلی قبل از رخداد خطا:

۰۰۰۰۰۰۰۰

نبوده باشه؟ (که در این صورت ۳ خطا رخ داده)

پاسخ: با یک مثال از زبان فارسی این قضیه شفاف‌تر می شه.

فرض کنید فرهنگ لغات مون شامل این کلمات باشه:

پشتاریکاتی
رشتاریکاتی
پستانداران

هر سه کلمه ۱۰ بیت (حرف) دارند. کلمه اول و دوم به هم شبیه ترند تا به کلمه سوم.
اگر کلمه ای که در گیرنده دریافت می شه این باشه:

رستاریکرتی

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

اگر هنوز متوجه نشدید از این مثالای بامزه بزنم بهتر درک کنید: دی

دوست خوبم شما اصلا دقت نکردی
بیشتر هم می تونه باشه یعنی چی؟؟؟؟؟؟؟؟؟؟

فاصله همینگ = حداقل فاصله بیتی بین دو حالت معتبر از کدهای ارسالی
این یک عدد مطلق هست. حداقل و حداکثر هم نداره.
با استفاده از بیت توازن هر دو حالت معتبر کمترین فاصله شون از هم ۲ بیت هست. یعنی اگر یک بیت داده تغییر کنه، یابد توازن رو هم تغییر بدیم (تا توازن حفظ بشه) یعنی با تغییر ۱ بیت برای ایجاد حالت معتبر دیگه، ۲ بیت تغییر می کنه (یکی خود اون بیت و یکی هم بیت توازن). پس فاصله همینگ این کد برابر با ۲ هست. یکی کمترش رو (یعنی ۱) می شه تشخیص داد و هیچ خطایی رو نمی شه تصحیح کرد.