جبر اساسی در پشت کدهای مخفی و ارتباطات فضایی

اکتشاف فضایی به دقت فوق العاده ای نیاز دارد. هنگامی که یک مریخ نورد را در فاصله 70 میلیون مایلی از نزدیکترین ایستگاه خدمات به مریخ فرود می آورید، باید کارایی را به حداکثر برسانید و برای موارد غیرمنتظره آماده شوید. این در مورد همه چیز از طراحی فضاپیما گرفته تا انتقال داده صدق می کند: آن پیام هایی که به عنوان یک جریان ثابت از 0 و 1 به زمین باز می گردند، مسلماً حاوی برخی خطاها هستند، بنابراین شما باید بتوانید آنها را بدون اتلاف وقت و انرژی گرانبها شناسایی و اصلاح کنید.

اینجاست که ریاضی وارد می شود. ریاضیدانان راه های مبتکرانه ای برای انتقال و ذخیره اطلاعات اختراع کرده اند. یکی از روش های شگفت آور موثر استفاده می شود کدهای رید-سلیمانکه بر اساس همان جبر اولیه ای ساخته شده اند که دانش آموزان در مدرسه یاد می گیرند. بیایید در یک کلاس ریاضی شرکت کنیم تا ببینیم چگونه کدهای Reed-Solomon به انتقال و ایمن سازی اطلاعات کمک می کنند و در عین حال خطاهای پرهزینه ای را که ظاهر می شوند تصحیح می کنند.

دو دانش آموز به نام های هنر و زیک در کلاس ریاضی خانم الجبر در حال تبادل پیام های محرمانه هستند. آرت آخرین یادداشت زیک را برای فاش کردن اعداد 57 و 99 باز می کند. او می داند که باید آن را تهیه کند. x- مختصات 3 و 6 را برای ایجاد نقاط (3، 57) و (6، 99). هنر هر نقطه را به معادله خطی متصل می کند y = Ax + B و سیستم معادلات زیر را ایجاد می کند:

57 = 3A + B

99 = 6A + B

برای رمزگشایی پیام، هنر باید آن را حل کند A و B. او با کم کردن معادله اول از معادله دوم شروع می کند:

این از بین می برد B. تقسیم هر دو طرف این معادله جدید بر 3 به هنر می گوید A = 14، و سپس آن را به معادله اول جایگزین کنید، 57 = 3 × 14 + B، می دهد B = 15.

هنر اکنون می داند که خطی که از (3، 57) و (6، 99) می گذرد با معادله توصیف می شود. y = 14x + 15. اما او همچنین می داند که در یک کد Reed-Solomon، پیام مخفی در ضرایب پنهان شده است. او پیام Zeke را با استفاده از رمز ساده الفبای مورد توافق آنها رمزگشایی می کند: 14 "N" و 15 "O" است، که به آرت می گوید، نه، Zeke نمی تواند امروز بعد از مدرسه بازی های ویدیویی انجام دهد.

راز این کد ساده رید-سولومون با دو واقعیت اساسی هندسه شروع می شود. اول، از طریق هر دو نقطه یک خط منحصر به فرد وجود دارد. دوم، برای ضرایب A و B، هر خط (غیر عمودی) را می توان به شکلی نوشت y = Ax + B. این دو واقعیت با هم تضمین می کنند که اگر دو نقطه در یک خط بدانید می توانید پیدا کنید A و B، و اگر می دانید A و B، شما تمام نقاط روی خط را می دانید. به طور خلاصه، داشتن هر یک از مجموعه‌ای از اطلاعات، معادل دانستن خط است.

کدهای Reed-Solomon از این مجموعه اطلاعات معادل استفاده می کنند. پیام مخفی به عنوان ضرایب کدگذاری می شود A و Bو نقاط خط به قطعات تقسیم می شوند، برخی از آنها به صورت عمومی مخابره می شوند و برخی از آنها خصوصی نگه داشته می شوند. برای رمزگشایی پیام، فقط قطعات را جمع آوری کرده و دوباره کنار هم قرار دهید. و تمام چیزی که این نیاز دارد یک جبر ساده است.

قطعات زیک اعداد 57 و 99 بود که برای آرت فرستاد. این اعداد بخش عمومی پیام هستند. هنر آن ها را با قطعات 3 و 6 خود کنار هم قرار داد تا نقاط (3، 57) و (6، 99) را بازسازی کند. در اینجا، 3 و 6 بخش خصوصی پیام را تشکیل می دهند، که آرت و زیک از قبل روی آن توافق کردند.

دو نقطه روی یک خط قرار دارند و برای رمزگشایی پیام، فقط باید معادله آن خط را پیدا کنید. وصل کردن هر نقطه به y = Ax + B سیستمی از دو معادله در مورد خط به شما می دهد که هر دو باید درست باشند. اکنون استراتژی ساده است: سیستم را حل کنید، خط را تعیین کنید و پیام را رمزگشایی کنید.

در کلاس جبر احتمالاً روش‌های زیادی را برای حل سیستم معادلات، مانند نمودار، حدس زدن و بررسی و جایگزینی یاد گرفته‌اید. هنر از حذف استفاده کرد، روشی که در آن معادلات را به صورت جبری دستکاری می کنید تا متغیرها را یکی یکی حذف کنید. هر بار که یک متغیر را حذف می کنید، حل سیستم کمی آسان تر می شود.

مانند سایر طرح های رمزگذاری، این ترکیب هوشمندانه اطلاعات عمومی و خصوصی است که پیام ها را ایمن نگه می دارد. زیک می‌توانست شماره‌های 57 و 99 خود را در سرتاسر کلاس فریاد بزند و این امنیت پیام او به هنر را به خطر نمی‌اندازد (اگرچه ممکن است او را با خانم الجبر دچار مشکل کند). به این دلیل که بدون اطلاعات خصوصی مربوطه - x- مختصات 3 و 6 - تشخیص معادله خط غیرممکن است. تا زمانی که آنها این ارزش ها را برای خود نگه دارند، می توانند با خیال راحت پیام های مخفی خود را در ملاء عام منتقل کنند.

خط y = 14x + 15 برای انتقال کلمه دو حرفی "نه" خوب است، اما اگر دانش آموزان بخواهند راز طولانی تری را به اشتراک بگذارند چه؟ اینجاست که قدرت کامل جبر، هندسه و سیستم های معادلات خطی وارد عمل می شود.

فرض کنید زیک می‌خواهد بداند که آرت فکر می‌کند در آزمون انگلیسی فردا چگونه عمل می‌کند. آرت پاسخ سه حرفی خود را به اعداد 14، 59 و 82 تبدیل می کند و آن ها را به Zeke می دهد. دانش‌آموزان قبلاً توافق کردند که هنگام استفاده از کدهای Reed-Solomon به طول 3، اعداد خصوصی آنها 2، 5 و 6 باشد، بنابراین Zeke قطعات را برای بازسازی نقاط (2، 14)، (5، 59) و (6،) کنار هم قرار می‌دهد. 82).

حالا هیچ تابع خطی وجود ندارد که از این سه نقطه عبور کند. اما یک تابع درجه دوم منحصر به فرد وجود دارد که انجام می دهد. و از آنجایی که هر تابع درجه دوم را می توان به شکل نوشت y = Ax² + Bx + C، می توان از همان روش کلی استفاده کرد. تنها تفاوت در اندازه سیستم است.

وصل کردن هر نقطه به y = Ax² + Bx + C یک معادله به دست می آید، بنابراین سه نقطه سیستم سه معادله زیر را ایجاد می کند:

(2، 14): 14 = 4A + 2B + C

(5، 59): 59 = 25A + 5B + C

(6، 82): 82 = 36A + 6B + C

حل یک سیستم متشکل از سه معادله با سه مجهول به کمی کار بیشتر نسبت به سیستمی متشکل از دو معادله با دو مجهول نیاز دارد، اما هدف یکی است: ترکیبی هوشمندانه از جفت معادلات برای حذف متغیرها.

به عنوان مثال، اگر معادله اول را از دومی کم کنید، معادله جدید 45 = 21 به دست می آید.A + 3B. به همین ترتیب، اگر معادله دوم را از معادله سوم کم کنید، 23 = 11 به دست می آیدA + B. این دستکاری های جبری یک سیستم جدید ایجاد می کند:

45 = 21A + 3B

23 = 11A + B

اکنون شما یک سیستم "دو در دو" دارید: دو معادله با دو مجهول. برای حل آن، می توانید معادله دوم را در 3- ضرب کنید و آن را به معادله اول اضافه کنید:

توجه کنید که چگونه حذف مکرر سیستم اصلی سه معادله را به یک معادله تبدیل کرده است که به راحتی قابل حل است: A = 2. کار به عقب، شما می توانید وصل کنید A = 2 به یکی از معادلات در سیستم دو در دو برای پیدا کردن B = 1، و سپس هر دو مقدار را به یکی از معادلات اصلی وصل کنید تا به دست آورید C = 4. پس از استفاده از رمز الفبای ساده در 2، 1 و 4، Zeke می داند که Art قرار است در آزمون انگلیسی فردا "BAD" را انجام دهد. حداقل او تمرینات جبر زیادی می کند.

به لطف یک واقعیت خاص در مورد توابع چند جمله ای، می توانید پیامی با هر طولی را با استفاده از کدهای Reed-Solomon ارسال کنید. کلید این است: با توجه به هر n نقاط در هواپیما با متفاوت است x-مختصات، یک چند جمله ای منحصر به فرد از "درجه" وجود دارد n − 1 که از آنها می گذرد. درجه یک چند جمله ای بالاترین توان یک متغیر در عبارت است، بنابراین یک تابع درجه دوم مانند است Ax² + Bx + C دارای درجه 2 است، زیرا بالاترین توان از x 2 است. و یک تابع خطی دارای درجه 1 است، زیرا در معادله است y = Ax + B، بالاترین قدرت از x 1 است

در مثال اول از این واقعیت استفاده کردیم که دو نقطه یک چند جمله ای خطی یا درجه 1 را تعیین می کنند. در مورد دوم، ما بر این واقعیت تکیه کردیم که سه نقطه یک چند جمله ای درجه 2 یا درجه دوم را مشخص می کند. و اگر می خواهید پیامی به طول 10 ارسال کنید، فقط پیام را به عنوان 10 ضریب تابع چند جمله ای درجه 9 رمزگذاری کنید. وقتی تابع خود را به دست آوردید، 10 عمومی را محاسبه کنید y-مقادیر با ارزیابی تابع در 10 خصوصی که قبلاً توافق شده بود x-ارزش های. پس از انجام این کار، می توانید با خیال راحت از آنها عبور کنید y-مختصات عمومی برای رمزگشایی گیرنده شما. در عمل، کدهای Reed-Solomon کمی پیچیده‌تر از این هستند، و از انواع پیچیده‌تر ضرایب و طرح‌های ترجمه استفاده می‌کنند، اما ایده اصلی یکسان است.

کدهای Reed-Solomon علاوه بر ایمن نگه داشتن پیام شما، راه‌های ساده و کارآمدی برای دریافت و حتی تصحیح خطاها نیز ارائه می‌دهند. این مهم در هر زمان که داده ها منتقل یا ذخیره می شوند، مهم است، زیرا همیشه این احتمال وجود دارد که برخی از اطلاعات از بین بروند یا خراب شوند.

یک راه حل برای این مشکل ارسال نسخه های اضافی از داده ها خواهد بود. به عنوان مثال، Zeke می تواند پیام [14، 14، 14، 15، 15، 15] را به جای [14، 15] ارسال کند. تا زمانی که هنر بداند هر قسمت از پیام در سه نسخه ارسال می شود، می تواند پیام را رمزگشایی کرده و خطاها را بررسی کند. در واقع اگر خطایی پیدا کند، شانس زیادی برای تصحیح آنها دارد. اگر آرت [14، 14، 24، 15، 15، 15] را دریافت کند، این واقعیت که سه عدد اول متفاوت هستند به او هشدار می دهد که یک خطا وجود دارد، و از آنجایی که دو عدد از آنها 14 هستند، می تواند حدس بزند که 24 احتمالا باید یک خطا باشد. 14 همینطور به جای درخواست برای ارسال مجدد پیام، هنر می تواند به رمزگشایی خود ادامه دهد. این یک استراتژی موثر اما پرهزینه است. هر زمان، انرژی و تلاش برای ارسال نیاز است n قطعات اطلاعات، این نیاز به سه برابر بیشتر است.

اما ریاضی پشت کدهای Reed-Solomon یک جایگزین کارآمد ارائه می دهد. به جای ارسال چندین نسخه از هر قطعه داده، فقط می توانید یک امتیاز اضافی ارسال کنید! اگر آن نقطه اضافی با چند جمله ای شما مطابقت دارد، اطلاعات صحیح است. اگر اینطور نیست، خطایی رخ داده است.

برای اینکه ببینید چگونه این کار می کند، فرض کنید می خواهید پیام "NO" را در مثال اول بررسی کنید. Zeke فقط می تواند موارد اضافی را ارسال کند y-مختصات 155. با فرض اینکه او و آرت در مورد سوم خصوصی توافق کردند x-از قبل هماهنگ کن، بگو x = 10، هنر می تواند این نقطه سوم را با خطی که رمزگشایی کرده است بررسی کند. وقتی برق میزنه x = 10 به y = 14x + 15 و می بیند که نتیجه 155 است، او می داند که هیچ خطایی در انتقال وجود ندارد.

این فقط برای خطوط کار نمی کند. برای فعال کردن Zeke برای بررسی "BAD" در مثال دوم، Art می‌تواند ارسال کند y = 25. اگر آنها توافق کرده اند که 3 خصوصی اضافی است xمختصات، Zeke می تواند وصل شود x = 3 به تابع درجه دوم او y = 2x² + x + 4 و بررسی کنید که نقطه (3، 25) مطابقت دارد، مجدداً ارسال بدون خطا را فقط با یک نقطه دیگر تأیید کنید.

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

این کارایی در انتقال و تصحیح ارتباطات توضیح می دهد که چرا ناسا از کدهای رید-سولومون در ماموریت های خود به ماه و مریخ استفاده کرده است. و در حین حل سیستم معادلات بعدی خود چیزی به شما می دهد که در آن فکر کنید. همانطور که حدس می‌زنید، راه خود را برای رسیدن به راه‌حل بررسی یا حذف کنید، به قدرت و ظرافت کدهای Reed-Solomon و همه رازهایی که ممکن است سیستم شما فاش کند فکر کنید.

تمرینات

1. با استفاده از همان طرحی که در کلاس استفاده کردند، Art اعداد عمومی 33 و 57 را برای رمزگشایی Zeke پست می‌کند. پیام چیست؟

2. هنر و زک چگونه می توانند مطمئن باشند که سیستم معادلات حاصل از اعداد خصوصی آنهاست x = 3 و x = 6 همیشه راه حلی خواهد داشت؟

3. در پاسخ به پیام آرت مبنی بر «BAD» در مورد آزمون انگلیسی، زیک [90, 387, 534] را بازگرداند. با فرض اینکه از همان طرحی که در کلاس استفاده کردند استفاده کنند، پیام او چیست؟

4. لولا با استفاده از کد Reed-Solomon و همان رمز الفبای ساده ای که توسط Art و Zeke استفاده می شود، یک پیام دو حرفی به اضافه یک شماره بررسی خطا برای شما ارسال می کند. شما مخفیانه در مورد آن توافق کرده اید x- مختصات 1، 3 و 10 را از قبل انجام می دهد و لولا اعداد عمومی را ارسال می کند [27، 43، 90]. آیا پیام حاوی خطایی است؟