الجبر الأساسي وراء الرموز السرية والاتصالات الفضائية

يتطلب استكشاف الفضاء دقة هائلة. عندما تهبط بمركبة على سطح المريخ على بعد 70 مليون ميل من أقرب محطة خدمة ، فإنك تحتاج إلى زيادة الكفاءة والاستعداد لما هو غير متوقع. ينطبق هذا على كل شيء من تصميم المركبات الفضائية إلى نقل البيانات: تلك الرسائل التي تعود إلى الأرض كتدفق ثابت من 0 و 1 لا بد أن تحتوي على بعض الأخطاء ، لذلك عليك أن تكون قادرًا على تحديدها وتصحيحها دون إضاعة الوقت الثمين والطاقة.

وهنا يأتي دور الرياضيات. ابتكر علماء الرياضيات طرقًا بارعة لنقل المعلومات وتخزينها. طريقة واحدة فعالة بشكل مدهش يستخدم رموز ريد سليمان، والتي بنيت على نفس الجبر الأساسي الذي يتعلمه الطلاب في المدرسة. دعنا نلتحق بفصل الرياضيات لنرى كيف تساعد أكواد Reed-Solomon في نقل المعلومات وتأمينها أثناء تصحيح أي أخطاء باهظة الثمن تنبثق.

يتبادل الطالبان آرت وزيكي رسائل سرية في حصة الأستاذة الجبر في مادة الرياضيات. يكشف الفن عن أحدث ملاحظة لـ Zeke ليكشف عن الرقمين 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 ، تختبئ الرسالة السرية في المعاملات. قام بفك تشفير رسالة زيكي باستخدام الشفرات الأبجدية البسيطة المتفق عليها: 14 هي "N" و 15 هي "O" ، والتي تخبر Art ، لا ، أن Zeke لا يمكنه لعب ألعاب الفيديو بعد المدرسة اليوم.

يبدأ سر كود Reed-Solomon البسيط هذا بحقيقتين أساسيتين للهندسة. أولاً ، يوجد خط فريد من خلال أي نقطتين. ثانيًا ، بالنسبة للمعاملات A و Bيمكن كتابة كل سطر (غير عمودي) في النموذج y = Ax + B. تضمن هاتان الحقيقتان معًا أنه إذا كنت تعرف نقطتين على السطر ، يمكنك العثور عليهما A و B، وإذا كنت تعلم A و B، أنت تعرف كل النقاط على الخط. باختصار ، امتلاك أي مجموعة من المعلومات يعادل معرفة الخط.

تستفيد أكواد Reed-Solomon من هذه المجموعات المكافئة من المعلومات. يتم ترميز الرسالة السرية كمعامِلات A و B، وتنقسم نقاط الخط إلى أجزاء ، يتم نقل بعضها علنًا ، ويتم الاحتفاظ ببعضها خاصًا. لفك تشفير الرسالة ، ما عليك سوى جمع القطع وإعادة تجميعها معًا. وكل ما يتطلبه هذا هو بعض الجبر البسيط.

كانت قطع زيك هي الأرقام 57 و 99 ، والتي أرسلها إلى Art. هذه الأرقام هي الجزء العام من الرسالة. جمع الفن هذه مع قطعه الخاصة ، 3 و 6 ، لإعادة بناء النقاط (3 ، 57) و (6 ، 99). هنا ، يشكل 3 و 6 الجزء الخاص من الرسالة ، والذي اتفق عليه Art and Zeke مسبقًا.

النقطتان تقعان على خط ، ولفك تشفير الرسالة ، ما عليك سوى العثور على معادلة هذا الخط. توصيل كل نقطة في y = Ax + B يمنحك نظامًا من معادلتين حول الخط يجب أن يكون كلاهما صحيحًا. الآن الإستراتيجية واضحة ومباشرة: حل النظام ، حدد الخط وفك تشفير الرسالة.

ربما تعلمت في فصل الجبر العديد من طرق حل أنظمة المعادلات ، مثل الرسوم البيانية والتخمين والتحقق والاستبدال. استخدم الفن طريقة الحذف ، وهي طريقة تقوم فيها بمعالجة المعادلات جبريًا من أجل التخلص من المتغيرات واحدًا تلو الآخر. في كل مرة تزيل فيها متغيرًا ، يصبح حل النظام أسهل قليلاً.

كما هو الحال مع أنظمة التشفير الأخرى ، فإن المزيج الذكي من المعلومات العامة والخاصة هو الذي يحافظ على أمان الرسائل. كان بإمكان زيك أن يصرخ برقميه 57 و 99 في جميع أنحاء الفصل ولن يعرض ذلك للخطر أمن رسالته إلى آرت (على الرغم من أنه قد يوقعه في مشكلة مع السيدة الجبر). هذا لأنه بدون المعلومات الخاصة المقابلة - فإن x- الإحداثيان 3 و 6 - من المستحيل تحديد معادلة الخط المستقيم. طالما أنهم يحتفظون بهذه القيم لأنفسهم ، فيمكنهم تمرير رسائلهم السرية بأمان في الأماكن العامة.

الخط y = 14x + 15 مناسب لإرسال الكلمة المكونة من حرفين "لا" ، ولكن ماذا لو أراد الطلاب مشاركة سر أطول؟ هنا يأتي دور القوة الكاملة للجبر والهندسة وأنظمة المعادلات الخطية.

لنفترض أن زيك يريد أن يعرف كيف يعتقد آرت أنه سيفعل في اختبار اللغة الإنجليزية غدًا. يحول Art إجابته المكونة من ثلاثة أحرف إلى الأرقام 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 = 21A + 3B. وبالمثل ، إذا طرحت المعادلة الثانية من الثالثة ، فستحصل على 23 = 11A + B. تنتج هذه المعالجات الجبرية نظامًا جديدًا:

45 = 21A + 3B

23 = 11A + B

الآن لديك نظام "اثنان في اثنين": معادلتان مع مجهولين. لحلها ، يمكنك ضرب المعادلة الثانية في −3 وإضافتها إلى المعادلة الأولى:

لاحظ كيف حوّل الحذف المتكرر النظام الأصلي المكون من ثلاث معادلات إلى معادلة واحدة يمكن حلها بسهولة: A = 2. العمل للخلف ، يمكنك التوصيل A = 2 في إحدى المعادلات في نظام اثنين في اثنين لإيجادها B = 1 ، ثم عوض بالقيمتين في إحدى المعادلات الأصلية لتحصل على C = 4. بعد استخدام التشفير الأبجدي البسيط في 2 و 1 و 4 ، يعرف زيك أن 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]. طالما يعرف Art أن كل جزء من الرسالة يتم إرساله في ثلاث نسخ ، يمكنه فك تشفير الرسالة والتحقق من الأخطاء. في الواقع ، إذا وجد أي أخطاء ، فلديه فرصة جيدة لتصحيحها. إذا تلقى Art [14 ، 14 ، 24 ، 15 ، 15 ، 15] ، فإن حقيقة أن الأرقام الثلاثة الأولى مختلفة تنبهه إلى حدوث خطأ ، وبما أن اثنين منهم 14 ، فيمكنه تخمين أن الرقم 24 يجب أن يكون على الأرجح 14 كذلك. بدلاً من طلب استياء الرسالة ، يمكن للفن أن يستمر في فك تشفيره. هذه استراتيجية فعالة لكنها مكلفة. مهما كان الوقت والطاقة والجهد المطلوب للإرسال n قطعة من المعلومات ، وهذا يتطلب ثلاثة أضعاف.

لكن الرياضيات الكامنة وراء أكواد Reed-Solomon تقدم بديلاً فعالاً. بدلاً من إرسال نسخ متعددة من كل جزء من البيانات ، يمكنك فقط إرسال نقطة إضافية واحدة! إذا كانت هذه النقطة الإضافية تتناسب مع كثير الحدود ، فإن المعلومات صحيحة. إذا لم يحدث ذلك ، فقد حدث خطأ.

لمعرفة كيفية عمل ذلك ، افترض أنك تريد التحقق من الرسالة "لا" في المثال الأول. يمكن لـ Zeke فقط إرسال العنصر الإضافي y-تنسيق 155. بافتراض أنه هو والفن اتفقا على خاص ثالث x- قم بالتنسيق مسبقًا ، على سبيل المثال x = 10 ، يمكن للفن التحقق من هذه النقطة الثالثة مقابل الخط الذي قام بفك تشفيره. عندما كان يسد x = 10 بوصة y = 14x + 15 ويرى أن النتيجة هي 155 ، فهو يعلم أنه لا توجد أخطاء في الإرسال.

هذا لا يعمل فقط للخطوط. لتمكين Zeke من فحص "BAD" في المثال الثاني ، يمكن لـ Art الإرسال y = 25. إذا وافقوا على أن 3 هي الخصوصية الإضافية x-تنسيق ، يمكن توصيل زيك x = 3 في وظيفته التربيعية y = 2x² + x + 4 وتحقق من أن النقطة (3 ، 25) مناسبة ، مما يؤكد مرة أخرى أن الإرسال خالٍ من الأخطاء بنقطة واحدة فقط.

وهذه النقطة الإضافية يمكن أن تصحح الأخطاء أيضًا. إذا تم اكتشاف خطأ ولم يتمكن جهاز الاستقبال من إنشاء وظيفة متعددة الحدود التي تحتوي على الرسالة ، فيمكنه بدلاً من ذلك إنشاء متعدد الحدود "الأفضل ملاءمة" باستخدام تقنيات الانحدار. مثل السطر الأكثر ملاءمة في فئة الإحصاء ، هذه هي الوظيفة متعددة الحدود التي يتم تحديدها رياضيًا لتلائم النقاط المعينة بشكل وثيق ، حتى لو لم تمر عبرها جميعًا. اعتمادًا على بنية الرسالة ومقدار المعلومات الإضافية التي ترسلها ، يمكن أن تساعدك كثيرة الحدود الأنسب في إعادة بناء كثير الحدود الصحيح - وبالتالي الرسالة الصحيحة - حتى من المعلومات الفاسدة.

تفسر هذه الكفاءة في نقل الاتصالات وتصحيحها سبب استخدام ناسا لرموز ريد سولومون في بعثاتها إلى القمر والمريخ. وهو يمنحك شيئًا للتفكير فيه بينما تحل نظام المعادلات التالي. كما تخمن ، تحقق من طريقك إلى الحل أو تخلص منه ، فكر في قوة وأناقة أكواد Reed-Solomon وجميع الأسرار التي قد يكشفها نظامك.

تمارين

1. باستخدام نفس المخطط الذي استخدموه في الفصل ، يقوم Art بنشر الرقمين العامين 33 و 57 لكي يقوم Zeke بفك تشفيرهما. ما هي الرسالة؟

2. كيف يمكن أن يتأكد Art and Zeke من أن نظام المعادلات الناتج عن أرقامهم الخاصة x = 3 و x = 6 دائما حل؟

3. ردًا على رسالة Art الخاصة بـ "BAD" حول اختبار اللغة الإنجليزية ، يرسل Zeke [90 ، 387 ، 534]. بافتراض أنهم يستخدمون نفس النظام الذي استخدموه في الفصل ، ما هي رسالته؟

4. ترسل لك Lola رسالة من حرفين بالإضافة إلى رقم واحد للتحقق من الأخطاء باستخدام رمز Reed-Solomon ونفس التشفير الأبجدي البسيط الذي يستخدمه Art و Zeke. لقد وافقت سرا على x- الإحداثيات 1 و 3 و 10 مقدمًا ، وتنقل لولا الأرقام العامة [27 ، 43 ، 90]. هل الرسالة تحتوي على خطأ؟