- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
محمد در اصفهان زندگی می کند و حسین در تهران. بین اصفهان و تهران یک خط ارتباطی ارزان وجود دارد که محمد برای فرستادن پیغام هایش به حسین از آن استفاده می کند. هر پیغام دنباله ای از ارقام 0 یا 1 (تعدادی بیت) است. متأسفانه تعدادی از دشمنان این دو دوست قصد دارند بین شان تفرقه ایجاد کنند؛ به همین دلیل برخی مواقع تعدادی از بیت های پیغامی که از این خط مبادله می شود را تغییر می دهند. محمد که از این موضوع مطلع شد یک خط ارتباطی گران قیمت بین اصفهان و تهران خرید. این خط از جاهای مخفی می گذرد و تضمین شده که بیت هایی که از آن رد می شود تغییری نخواهد کرد. ولی چون این خط ارتباطی گران قیمت است محمد دوست دارد تا حد ممکن مقدار کمی اطلاعات را از طریق این خط منتقل کند.
فرض کنید محمد قصد دارد 2[SUP]k[/SUP] بیت را از خط ارزان قیمت منتقل کند. بر حسب اطلاعات قبلی او می داند که حداکثر 2 بیت از این اطلاعات ممکن است توسط دشمنان تغییر کند. حال او قصد دارد حداقل تعداد بیت را به عنوان اطلاعات کمکی هم زمان از خط گران قیمت برای حسین بفرستد به طوری که حسین با استفاده از این اطلاعات اضافی بتواند تشخیص دهد که آیا هیچ یک از 2[SUP]k[/SUP] بیت دریافتی تغییر کرده است یا خیر.
ثابت کنید اگر محمد کم تر از k+1 بیت اطلاعات از خط گران قیمت بفرستد حسین نمی تواند قاطعانه تشخیص دهد که آیا بیت های فرستاده شده تغییر کرده اند یا خیر.
فرض کنید محمد قصد دارد 2[SUP]k[/SUP] بیت را از خط ارزان قیمت منتقل کند. بر حسب اطلاعات قبلی او می داند که حداکثر 2 بیت از این اطلاعات ممکن است توسط دشمنان تغییر کند. حال او قصد دارد حداقل تعداد بیت را به عنوان اطلاعات کمکی هم زمان از خط گران قیمت برای حسین بفرستد به طوری که حسین با استفاده از این اطلاعات اضافی بتواند تشخیص دهد که آیا هیچ یک از 2[SUP]k[/SUP] بیت دریافتی تغییر کرده است یا خیر.
ثابت کنید اگر محمد کم تر از k+1 بیت اطلاعات از خط گران قیمت بفرستد حسین نمی تواند قاطعانه تشخیص دهد که آیا بیت های فرستاده شده تغییر کرده اند یا خیر.