أثبت نظام تصحيح الأخطاء "السحري" أنه غير فعال بطبيعته | مجلة كوانتا

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

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

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

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

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

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

وقال "هذه النتيجة مذهلة". شوبانجي صراف، عالم الكمبيوتر في جامعة تورنتو. "إنه إنجاز كبير."

قوة في أرقام

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

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

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

ولحسن الحظ، فإن العديد من رموز تصحيح الأخطاء تكون أفضل حالًا. أحد الأمثلة الشهيرة، يسمى كود ريد سولومون، يعمل عن طريق تحويل الرسائل إلى كثيرات الحدود - تعبيرات رياضية مثل x² + 3x + 2 تتكون من مصطلحات مختلفة مضافة معًا، ولكل منها متغير (مثل x) مرفوعة إلى قوة مختلفة. يتضمن تشفير رسالة باستخدام كود Reed-Solomon إنشاء كثير حدود بمصطلح واحد لكل حرف في الرسالة، ثم رسم كثير الحدود كمنحنى على الرسم البياني وتخزين إحداثيات النقاط التي تقع على المنحنى (مع أخذ نقطة أخرى على الأقل نقطة من عدد الأحرف). قد تؤدي الأخطاء إلى دفع عدد قليل من هذه النقاط خارج المنحنى، ولكن إذا لم يكن هناك الكثير من الأخطاء، فسوف يمر منحنى متعدد الحدود واحد فقط عبر معظم النقاط. يكاد يكون من المؤكد أن هذا المنحنى يتوافق مع الرسالة الحقيقية.

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

فكر عالميا واعمل محليا

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

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

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

قال كوثاري: “هذه فكرة صارمة حقًا”.

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

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

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

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

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

وقال دفير: "الأسّي في هذه الحالة أمر سيء للغاية". ولكن هل هذا أمر لا مفر منه؟

قابل للتصحيح أم قابل للفك؟

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

وقال كوثاري: "بمجرد الانتقال إلى المستوى الثالث، تصبح معرفتنا سطحية للغاية".

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

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

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

قال: "كل ما تقوم بتخزينه، سواء كان البيانات الأصلية للمستخدمين أو التكرار ومعلومات التحقق - كل هذا يمكن تصحيحه محليًا". مادو السودان، عالم الكمبيوتر في جامعة هارفارد.

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

منطق الاقتراض

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

هناك عدم تناسق متأصل بين هاتين النتيجتين المحتملتين. قد لا يكون من السهل العثور على حل مقبول، ولكن بمجرد الحصول عليه، سيكون من السهل إقناع أي شخص آخر بأنه سينجح. ولكن حتى لو كنت تعلم أن المشكلة "غير مرضية" حقًا، فقد لا يكون هناك مثال يقدم دليلاً.

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

قال كوثاري: “كان هذا مسمارًا بمطرقة في أيدينا، إذا جاز التعبير”.

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

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

اشتبه كوثاري ومانوهار في أنهما يمكنهما الذهاب إلى أبعد من ذلك. لكن التقدم توقف حتى قام مانوهار بتدوين عملية حسابية سريعة تشير إلى أن هذه التقنية قد تعمل بشكل أفضل مع الرموز القابلة للتصحيح محليًا مقارنة بالرموز القابلة لفك التشفير محليًا.

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

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

قال دفير: "هناك فكرة جديدة جميلة حقًا هنا". "أعتقد أن هناك الكثير من الإمكانات."