فك تشفير القوائم

الموسوعة الحرة

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

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

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

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

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

الصياغة الرياضية

يتركج{\displaystyle {\mathcal {C}}}كن(ن،ك،د)q{\displaystyle (n,k,d)_{q}}رمز تصحيح الأخطاء؛ بعبارة أخرى،ج{\displaystyle {\mathcal {C}}}هو رمز بطولن{\displaystyle n}الأبعادك{\displaystyle k}والمسافة الدنياد{\displaystyle d}على مستوى الأبجديةΣ{\displaystyle \Sigma }من الحجمq{\displaystyle q}يمكن الآن صياغة مشكلة فك تشفير القائمة على النحو التالي:

المدخلات: الكلمة المستلمةx∈Σن{\displaystyle x\in \Sigma ^{n}}، حد الخطأهـ{\displaystyle e}

الناتج: قائمة بجميع الكلمات السريةx1،x2،...،xم∈ج{\displaystyle x_{1},x_{2},\ldots ,x_{m}\in {\mathcal {C}}}الذي على مسافة قريبة منx{\displaystyle x}هو على الأكثرهـ{\displaystyle e}.

دوافع فك تشفير القوائم

بافتراض تلقي كلمةy{\displaystyle y}، وهو نسخة مشوشة من بعض الكلمات المشفرة المرسلةج{\displaystyle c}يحاول جهاز فك التشفير إخراج الكلمة المشفرة المرسلة عن طريق اختيار كلمة مشفرة "أقرب" إلى الكلمة المستلمة. تُستخدم مسافة هامينغ بين كلمتين مشفرتين كمقياس لإيجاد أقرب كلمة مشفرة، مع الأخذ في الاعتبار الكلمة المستلمة من جهاز فك التشفير.د{\displaystyle d}هي أقل مسافة هامينغ لرمزج{\displaystyle {\mathcal {C}}}إذن، يوجد رمزانج1{\displaystyle c_{1}}وج2{\displaystyle c_{2}}والتي تختلف في بالضبطد{\displaystyle d}المواقف. الآن، في حالة الكلمة المستلمةy{\displaystyle y}وهي على مسافة متساوية من الكلمات السريةج1{\displaystyle c_{1}}وج2{\displaystyle c_{2}}يصبح فك التشفير غير المبهم مستحيلاً لأن جهاز فك التشفير لا يستطيع تحديد أي منج1{\displaystyle c_{1}}وج2{\displaystyle c_{2}}لإخراجها ككلمة الترميز الأصلية المرسلة. ونتيجة لذلك، يعمل نصف الحد الأدنى للمسافة كحاجز توافقي يستحيل بعده تصحيح الخطأ بشكل قاطع، إذا أصررنا فقط على فك تشفير فريد. ومع ذلك، فإن الكلمات المستلمة مثلy{\displaystyle y}لا تحدث الحالات المذكورة أعلاه إلا في أسوأ الحالات، وإذا نظرنا إلى طريقة ترتيب كرات هامينغ في الفضاء عالي الأبعاد، حتى بالنسبة لأنماط الخطأهـ{\displaystyle e}بعد نصف المسافة الدنيا، لا يوجد سوى كلمة سر واحدةج{\displaystyle c}على مسافة هامهـ{\displaystyle e}انطلاقًا من الكلمة المُستقبَلة. وقد ثبتت صحة هذا الادعاء باحتمالية عالية بالنسبة لرمز عشوائي مُختار من مجموعة طبيعية، وبشكل أكبر في حالة رموز ريد-سولومون ، التي دُرست جيدًا وتُستخدم على نطاق واسع في التطبيقات العملية. في الواقع، يمكن النظر إلى برهان شانون لنظرية السعة للقنوات المتناظرة من الرتبة q في ضوء الادعاء المذكور أعلاه للرموز العشوائية.

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

إمكانية فك تشفير القوائم

لكي توجد خوارزمية لفك تشفير القوائم ذات وقت متعدد الحدود، نحتاج إلى ضمان توافقي بأن أي كرة هامينغ نصف قطرهاصن{\displaystyle pn}حول كلمة متداولةر{\displaystyle r}(أينص{\displaystyle p}يمثل هذا الجزء نسبة الأخطاء بدلالة طول الكتلةن{\displaystyle n}يحتوي على عدد قليل من الكلمات المشفرة. ويعود ذلك إلى أن حجم القائمة نفسه يمثل حدًا أدنى واضحًا لوقت تشغيل الخوارزمية. لذا، نشترط أن يكون حجم القائمة متعدد الحدود في طول الكتلة.ن{\displaystyle n}من الشفرة. ومن النتائج التوافقية لهذا الشرط أنه يفرض حدًا أعلى على معدل الشفرة. يعد فك تشفير القوائم بتلبية هذا الحد الأعلى. وقد ثبت بطريقة غير بنائية أن الشفرات ذات المعدلR{\displaystyle R}توجد قوائم يمكن فك تشفيرها بنسبة تصل إلى جزء من الأخطاء.1-R{\displaystyle 1-R}الكمية1-R{\displaystyle 1-R}يُشار إليها في الأدبيات العلمية باسم قدرة فك تشفير القوائم. وهذا يُعد مكسبًا كبيرًا مقارنةً بنموذج فك التشفير الفريد، إذ أصبح لدينا الآن القدرة على تصحيح ضعف عدد الأخطاء. وبطبيعة الحال، نحتاج إلى جزء على الأقلR{\displaystyle R}يجب أن تكون جميع الرموز المرسلة صحيحة لاستعادة الرسالة. هذا حد أدنى نظري للمعلومات لعدد الرموز الصحيحة المطلوبة لفك التشفير، وباستخدام فك التشفير القائم على القوائم، يمكننا نظريًا الوصول إلى هذا الحد. مع ذلك، لتحقيق هذه الإمكانية، نحتاج إلى رموز صريحة (رموز يمكن إنشاؤها في وقت متعدد الحدود) وخوارزميات فعالة لإجراء التشفير وفك التشفير.

قابلية فك ترميز القائمة ( p , L )

لأي نسبة خطأ0⩽ص⩽1{\displaystyle 0\leqslant p\leqslant 1}وعدد صحيحل⩾1{\displaystyle L\geqslant 1}، رمزج⊆Σن{\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}يقال إنها قائمة قابلة للفك حتى جزءص{\displaystyle p}عدد الأخطاء التي يكون حجم قائمتها على الأكثرل{\displaystyle L}أو(ص،ل){\displaystyle (p,L)}-list-decodable if for everyy∈Σن{\displaystyle y\in \Sigma ^{n}}عدد الكلمات السريةج∈ج{\displaystyle c\in C}على مسافة هامصن{\displaystyle pn}منy{\displaystyle y}هو على الأكثرل.{\displaystyle L.}

تركيبات فك تشفير القوائم

لقد دُرست العلاقة بين قابلية فك تشفير الشفرة باستخدام القوائم والمعايير الأساسية الأخرى، مثل الحد الأدنى للمسافة ومعدل نقل البيانات، دراسةً وافية. وقد ثبت أنه يمكن فك تشفير أي شفرة باستخدام قوائم صغيرة تتجاوز نصف الحد الأدنى للمسافة، وصولاً إلى حد يُسمى نصف قطر جونسون. وهذا أمر بالغ الأهمية لأنه يُثبت وجود(ص،ل){\displaystyle (p,L)}رموز قابلة للفك باستخدام القوائم ذات معدل جيد ونصف قطر فك باستخدام القوائم أكبر بكثير مند2.{\displaystyle {\tfrac {d}{2}}.}بمعنى آخر، يستبعد حد جونسون إمكانية وجود عدد كبير من الكلمات المشفرة في كرة هامينغ نصف قطرها أكبر بقليل مند2{\displaystyle {\tfrac {d}{2}}}وهذا يعني أنه من الممكن تصحيح عدد أكبر بكثير من الأخطاء باستخدام فك تشفير القوائم.

قدرة فك تشفير القوائم

نظرية (سعة فك تشفير القائمة). ليكنq⩾2،0⩽ص⩽1-1q{\displaystyle q\geqslant 2,0\leqslant p\leqslant 1-{\tfrac {1}{q}}}وϵ⩾0.{\displaystyle \epsilon \geqslant 0.}العبارةان التاليتان صحيحتان بالنسبة لطول الكتلة الكبير بما فيه الكفايةن{\displaystyle n}.
أ) إذاR⩽1-حq(ص)-ϵ{\displaystyle R\leqslant 1-H_{q}(p)-\epsilon }إذن يوجد(ص،يا(1/ϵ)){\displaystyle (p,O(1/\epsilon ))}- قائمة الرموز القابلة للفك.
ii) إذاR⩾1-حq(ص)+ϵ{\displaystyle R\geqslant 1-H_{q}(p)+\epsilon }ثم كل(ص،ل){\displaystyle (p,L)}يحتوي الكود القابل للفك على قائمة علىل=qΩ(ن){\displaystyle L=q^{\Omega (n)}}.
أين
حq(ص)=صسجلq⁡(q-1)-صسجلq⁡ص-(1-ص)سجلq⁡(1-ص){\displaystyle H_{q}(p)=p\log _{q}(q-1)-p\log _{q}p-(1-p)\log _{q}(1-p)}
هوq{\displaystyle q}دالة الإنتروبيا من الرتبة n المعرفة لـص∈(0،1){\displaystyle p\in (0,1)}وتم توسيعها بالاستمرارية إلى[0،1].{\displaystyle [0,1].}

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

يُعدّ إثبات سعة فك تشفير القوائم إثباتًا مهمًا لأنه يتطابق تمامًا مع سعةq{\displaystyle q}قناة متناظرة من الدرجة -qSجص{\displaystyle qSC_{p}}في الواقع، ينبغي قراءة مصطلح "سعة فك تشفير القائمة" على أنه سعة قناة معادية في ظل فك تشفير القائمة. كما أن برهان سعة فك تشفير القائمة يُعد نتيجة مهمة تُحدد بدقة المفاضلة المثلى بين معدل الترميز ونسبة الأخطاء التي يمكن تصحيحها في ظل فك تشفير القائمة.

رسم تخطيطي للإثبات

الفكرة الكامنة وراء هذا البرهان مشابهة لفكرة برهان شانون لسعة القناة المتناظرة الثنائيةبSجص{\displaystyle BSC_{p}}حيث يتم اختيار رمز عشوائي وإظهار أنه(ص،ل){\displaystyle (p,L)}-قائمة قابلة للفك باحتمالية عالية طالما أن المعدلR⩽1-حq(ص)-1ل.{\displaystyle R\leqslant 1-H_{q}(p)-{\tfrac {1}{L}}.}بالنسبة للأسعار التي تتجاوز الكمية المذكورة أعلاه، يمكن إثبات أن حجم القائمةل{\displaystyle L}يصبح حجمه كبيرًا جدًا لدرجة أنه يتجاوز حدود كثير الحدود.

يُعرَّف الحدث "السيئ" بأنه الحدث الذي، بالنظر إلى كلمة مستلمةy∈[q]ن{\displaystyle y\in [q]^{n}}ول+1{\displaystyle L+1}رسائلم0،...،مل∈[q]ك،{\displaystyle m_{0},\ldots ,m_{L}\in [q]^{k},}يحدث أنج(مأنا)∈ب(y،صن){\displaystyle {\mathcal {C}}(m_{i})\in B(y,pn)}لكل0⩽أنا⩽ل{\displaystyle 0\leqslant i\leqslant L}أينص{\displaystyle p}هي نسبة الأخطاء التي نرغب في تصحيحها وب(y،صن){\displaystyle B(y,pn)}هي كرة هامينغ ذات نصف قطرصن{\displaystyle pn}بالكلمة المستلمةy{\displaystyle y}باعتباره المركز.

الآن، احتمال أن تكون كلمة السرج(مأنا){\displaystyle {\mathcal {C}}(m_{i})}مرتبط برسالة ثابتةمأنا∈[q]ك{\displaystyle m_{i}\in [q]^{k}}يستلقي في كرة هامينغب(y،صن){\displaystyle B(y,pn)}يُعطى بواسطة

برو[ج(مأنا)∈ب(y،صن)]=Voلq(y،صن)qن⩽q-ن(1-حq(ص))،{\displaystyle \Pr \left[C(m_{i})\in B(y,pn)\right]={\frac {\mathrm {Vol} _{q}(y,pn)}{q^{n}}}\leqslant q^{-n(1-H_{q}(p))},}

حيث الكميةVoلq(y،صن){\displaystyle Vol_{q}(y,pn)}حجم كرة هامينغ نصف قطرهاصن{\displaystyle pn}بالكلمة المستلمةy{\displaystyle y}باعتبارها المركز. وتنتج المتباينة في العلاقة أعلاه من الحد الأعلى لحجم كرة هامينغ. الكميةqحq(ص){\displaystyle q^{H_{q}(p)}}يُعطي تقديرًا جيدًا جدًا لحجم كرة هامينغ ذات نصف قطرص{\displaystyle p}يتمحور حول أي كلمة في[q]ن.{\displaystyle [q]^{n}.}بمعنى آخر، حجم كرة هامينغ ثابت تحت الإزاحة. ولمواصلة شرح البرهان، نستحضر حد الاتحاد في نظرية الاحتمالات، والذي يُخبرنا أن احتمال وقوع حدث سيئ لقيمة معينة يساوي صفرًا.(y،م0،...،مل){\displaystyle (y,m_{0},\dots ,m_{L})}وهي محدودة من الأعلى بالكميةq-ن(ل+1)(1-حq(ص)){\displaystyle q^{-n(L+1)(1-H_{q}(p))}}.

مع الأخذ في الاعتبار ما سبق، يمكن إثبات أن احتمال وقوع أي حدث سيئ أقل من1{\displaystyle 1}ولإثبات ذلك، نقوم بتحليل جميع الكلمات الواردة الممكنة.y∈[q]ن{\displaystyle y\in [q]^{n}}وكل مجموعة فرعية ممكنة منل{\displaystyle L}الرسائل في[q]ك.{\displaystyle [q]^{k}.}

بالانتقال الآن إلى برهان الجزء (ii)، نحتاج إلى إثبات وجود عدد كبير جدًا من الكلمات المشفرة حول كلy∈[q]ن{\displaystyle y\in [q]^{n}}عندما يتجاوز المعدل قدرة فك تشفير القائمة. نحتاج إلى إثبات ذلك.|ج∩ب(y،صن)|{\displaystyle |{\mathcal {C}}\cap B(y,pn)|}تكون كبيرة جدًا من حيث عدد الحدود إذا كان المعدلR⩾1-حq(ص)+ϵ{\displaystyle R\geqslant 1-H_{q}(p)+\epsilon }حدد كلمة سريةج∈ج{\displaystyle c\in {\mathcal {C}}}الآن، لكلy∈[q]ن{\displaystyle y\in [q]^{n}}تم اختيارها عشوائيا، لدينا

برو[ج∈ب(y،صن)]=برو[y∈ب(ج،صن)]{\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]}

بما أن كرات هامينغ ثابتة تحت الإزاحة. من تعريف حجم كرة هامينغ وحقيقة أنy{\displaystyle y}يتم اختيارها بشكل عشوائي منتظم من[q]ن{\displaystyle [q]^{n}}لدينا أيضًا

برو[ج∈ب(y،صن)]=برو[y∈ب(ج،صن)]=Voل(y،صن)qن⩾q-ن(1-حq(ص))-o(ن){\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]={\frac {\mathrm {Vol} (y,pn)}{q^{n}}}\geqslant q^{-n(1-H_{q}(p))-o(n)}}

لنقم الآن بتعريف متغير مؤشرXج{\displaystyle X_{c}}بحيث

Xج={1ج∈ب(y،صن)0خلاف ذلك{\displaystyle X_{c}={\begin{cases}1&c\in B(y,pn)\\0&{\text{otherwise}}\end{cases}}}

بأخذ القيمة المتوقعة لحجم كرة هامينغ، لدينا

هـ[|ب(y،صن)|]=∑ج∈جهـ[Xج]=∑ج∈جبرو[Xج=1]⩾∑q-ن(1-حq(ص)+o(ن))=∑qن(R-1+حq(ص)+o(1))⩾qΩ(ن){\displaystyle {\begin{aligned}E[|B(y,pn)|]&=\sum _{c\in {\mathcal {C}}}E[X_{c}]\\[4pt]&=\sum _{c\in {\mathcal {C}}}\Pr[X_{c}=1]\\[4pt]&\geqslant \sum q^{-n(1-H_{q}(p)+o(n))}\\[4pt]&=\sum q^{n(R-1+H_{q}(p)+o(1))}\\[4pt]&\geqslant q^{\Omega (n)}\end{aligned}}}

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

قائمة بفك رموز ريد-سولومون

في عام 2023، وبناءً على ثلاثة أعمال أساسية، [ 1 ] [ 2 ] [ 3 ] أظهر منظرو الترميز أنه باحتمالية عالية، يمكن فك ترميز ريد-سولومون المعرف على نقاط التقييم العشوائية حتى سعة فك ترميز القائمة على الأبجديات ذات الحجم الخطي.

خوارزميات فك تشفير القوائم

خلال الفترة من عام 1995 إلى عام 2007، طوّر مجتمع نظرية الترميز خوارزميات فك تشفير القوائم أكثر كفاءة تدريجيًا. وتشمل هذه الخوارزميات خوارزميات رموز ريد-سولومون التي يمكنها فك التشفير حتى نصف قطر جونسون، وهو1-1-دلتا{\displaystyle 1-{\sqrt {1-\delta }}}يوجد حيثدلتا{\displaystyle \delta }هي المسافة المعيارية أو المسافة النسبية. ومع ذلك، بالنسبة لرموز ريد-سولومون،دلتا=1-R{\displaystyle \delta =1-R}وهذا يعني كسرًا1-R{\displaystyle 1-{\sqrt {R}}}يمكن تصحيح العديد من الأخطاء. ومن أبرز خوارزميات فك تشفير القوائم ما يلي:

  • السودان 95 - أول خوارزمية معروفة لفك تشفير القوائم غير البسيطة لرموز ريد-سولومون والتي حققت فك تشفير فعال للقوائم حتى1-2R{\displaystyle 1-{\sqrt {2R}}}أخطاء من تطوير مادو سودان .
  • غورو سوامي - السودان 98 - تحسين للخوارزمية المذكورة أعلاه لفك تشفير قوائم رموز ريد سولومون حتى1-R{\displaystyle 1-{\sqrt {R}}}أخطاء ارتكبها مادو سودان وطالبه آنذاك في مرحلة الدكتوراه فينكاتيسان جوروسوامي .
  • بارفاريش-فاردي '05 – في ورقة بحثية رائدة، قدم فرزاد بارفاريش وألكسندر فاردي رموزًا يمكن فك تشفيرها بشكل غير محدود.1-R{\displaystyle 1-{\sqrt {R}}}نصف قطر للأسعار المنخفضةR{\displaystyle R}تُعدّ رموزهم صيغًا مختلفة من رموز ريد-سولومون التي يتم الحصول عليها من خلال تقييمم⩾1{\displaystyle m\geqslant 1}كثيرات الحدود المترابطة بدلاً من مجرد1{\displaystyle 1}كما هو الحال في رموز ريد-سولومون المعتادة.
  • غورو سوامي - رودرا '06 - في إنجاز آخر، قدم فينكاتيسان غورو سوامي وأتري رودرا رموزًا صريحة تحقق قدرة فك تشفير القوائم، أي أنه يمكن فك تشفيرها على مستوى القوائم حتى نصف القطر1-R-ϵ{\displaystyle 1-R-\epsilon }لأيϵ>0{\displaystyle \epsilon >0}بمعنى آخر، هذا تصحيح للأخطاء مع تكرار مثالي. وقد أجاب هذا على سؤال ظل مطروحًا لنحو خمسين عامًا. دُعي هذا العمل إلى قسم "أبرز الأبحاث" في مجلة "اتصالات رابطة مكائن ​​الحوسبة" (المخصصة لأهم نتائج الأبحاث المنشورة في علوم الحاسوب في السنوات الأخيرة)، وذُكر في مقال بعنوان "الترميز والحوسبة يوحدان جهودهما" في عدد 21 سبتمبر 2007 من مجلة "ساينس". تُسمى الرموز المُعطاة لهم رموز ريد-سولومون المطوية، وهي في جوهرها رموز ريد-سولومون عادية، ولكنها تُعتبر رمزًا على أبجدية أكبر من خلال تجميع رموز الكلمات المشفرة بعناية.

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

المدخلات : لـ[ن،ك+1]q{\displaystyle [n,k+1]_{q}}في كود ريد-سولومون، يتم إعطاؤنا الزوج(αأنا،yأنا){\displaystyle (\alpha _{i},y_{i})}ل1≤أنا≤ن{\displaystyle 1\leq i\leq n}، أينyأنا{\displaystyle y_{i}}هوأنا{\displaystyle i}الجزء رقم 1 من الكلمة المستلمة وαأنا{\displaystyle \alpha _{i}}النقاط المميزة هي نقاط مميزة في الحقل المنتهيFq{\displaystyle F_{q}}ومعامل خطأهـ=ن-ت{\displaystyle e=n-t}.

الناتج : الهدف هو إيجاد جميع كثيرات الحدودP(X)∈Fq[X]{\displaystyle P(X)\in F_{q}[X]}درجة علمية على الأكثرك{\displaystyle k}وهو طول الرسالة بحيثص(αأنا)=yأنا{\displaystyle p(\alpha _{i})=y_{i}}على الأقلت{\displaystyle t}قيمأنا{\displaystyle i}هنا، نود أن يكونت{\displaystyle t}أصغر ما يمكن حتى يمكن التسامح مع عدد أكبر من الأخطاء.

بناءً على الصيغة المذكورة أعلاه، يكون الهيكل العام لخوارزميات فك التشفير القائمة لرموز ريد سولومون كما يلي:

الخطوة 1 : (الاستيفاء) إيجاد متعددة حدود ثنائية المتغيرات غير صفريةسؤال(X،Y){\displaystyle Q(X,Y)}بحيثسؤال(αأنا،yأنا)=0{\displaystyle Q(\alpha _{i},y_{i})=0}ل1≤أنا≤ن{\displaystyle 1\leq i\leq n}.

الخطوة الثانية : (إيجاد الجذور/التحليل إلى عوامل) إخراج جميع الدرجاتك{\displaystyle k}كثيرات الحدودص(X){\displaystyle p(X)}بحيثY-ص(X){\displaystyle Y-p(X)}هو عامل من عواملسؤال(X،Y){\displaystyle Q(X,Y)}أيسؤال(X،ص(X))=0{\displaystyle Q(X,p(X))=0}لكل من هذه كثيرات الحدود، تحقق مما إذاص(αأنا)=yأنا{\displaystyle p(\alpha _{i})=y_{i}}على الأقلت{\displaystyle t}قيمأنا∈[ن]{\displaystyle i\in [n]}إذا كان الأمر كذلك، فأدرج مثل هذه المعادلة متعددة الحدودص(X){\displaystyle p(X)}في قائمة المخرجات.

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

تطبيقات في نظرية التعقيد وعلم التشفير

وجدت الخوارزميات المطورة لفك تشفير قوائم العديد من عائلات الشفرات المهمة تطبيقات مثيرة للاهتمام في مجال التعقيد الحسابي وعلم التشفير . فيما يلي قائمة نموذجية بالتطبيقات خارج نطاق نظرية التشفير:

انظر أيضاً

مراجع

  1. ↑ براكينسيك، جوشوا؛ جوبي، سيفاكانث؛ ماكام، فيسو (2023-06-02). "رموز ريد-سولومون العامة تحقق قدرة فك تشفير القوائم" . وقائع الندوة السنوية الخامسة والخمسين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC 2023. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 1488-1501 . arXiv : 2206.05256 . doi : 10.1145 /3564246.3585128 . ISBN  978-1-4503-9913-5.
  2. ↑ غو، زيو؛ تشانغ، زيهان (2023-11-06). "رموز ريد-سولومون المثقوبة عشوائيًا تحقق سعة فك تشفير القائمة على أبجديات ذات حجم متعدد الحدود". المؤتمر السنوي الرابع والستون لمؤسسة IEEE حول أسس علوم الحاسوب (FOCS) . FOCS 2023، سانتا كروز، كاليفورنيا، الولايات المتحدة الأمريكية. IEEE. الصفحات 164-176 . arXiv : 2304.01403 . doi : 10.1109/FOCS57990.2023.00019 . ISBN  979-8-3503-1894-4.
  3. ↑ الرابية، عمر؛ غورو سوامي، فينكاتيسان؛ لي، راي (2023). "تحقق رموز ريد-سولومون المثقوبة عشوائيًا قدرة فك تشفير القوائم على الحقول ذات الحجم الخطي". arXiv : 2304.09445 [ cs.IT ].

تاريخي:

  • إلياس، بيتر (1957). "فك تشفير القوائم للقنوات المشوشة" ​​(ملف PDF) . وقائع مؤتمر IRE WESCON لعام 1957، الجزء 2. الصفحات 94-104 . 
  • ووزنكرافت، جيه إم (1958). "فك تشفير القوائم". التقرير الفصلي للتقدم، مختبر أبحاث الإلكترونيات، معهد ماساتشوستس للتكنولوجيا . 48 : 90-95 .

مقالات مراجعة: