شفرة ريد-سولومون المطوية

يُوضَّح التعريف أعلاه بشكل أكبر من خلال الرسم التوضيحي مع${\displaystyle m=3}$، أين${\displaystyle m}$هو معامل الطي.

يُشار إلى الرسالة بـ${\displaystyle f(X)}$، والتي عند ترميزها باستخدام ترميز ريد-سولومون، تتكون من قيم${\displaystyle f}$في${\displaystyle x_{0},x_{1},x_{2},\ldots ,x_{n-1}}$، أين${\displaystyle x_{i}=\gamma ^{i}}$.

ثم يتم تجميع العناصر في مجموعات من 3 عناصر، لإعطاء كلمة رمزية بطول${\displaystyle n/3}$على الأبجدية${\displaystyle \mathbb {F} _{q}^{3}}$.

من الملاحظ هنا أن عملية الطي الموضحة لا تغير المعدل${\displaystyle R}$من قانون ريد-سولومون الأصلي.

لإثبات ذلك، ضع في اعتبارك خطيًا${\displaystyle [n,k,d]_{q}}$رمز، بطول${\displaystyle n}$الأبعاد​${\displaystyle k}$والمسافة​${\displaystyle d}$. ال${\displaystyle m}$عملية الطي ستجعلها${\displaystyle \left[{\tfrac {n}{m}},{\tfrac {k}{m}},{\tfrac {d}{m}}\right]_{q^{m}}}$الكود. وبهذا، المعدل${\displaystyle R={\tfrac {k}{n}}}$سيكون الأمر على حاله.

تُعدّ رموز ريد-سولومون المطوية مماثلةً لرموز ريد-سولومون، ولكنها تُعرض على أبجدية أكبر. ولتوضيح كيف يُمكن أن يُفيد ذلك، لنأخذ مثالاً على رمز ريد-سولومون مطوي مع${\displaystyle m=3}$فك تشفير كود ريد-سولومون وكود ريد-سولومون المطوي لنفس نسبة الأخطاء${\displaystyle \rho }$تُعدّ هاتان المهمتان متقاربتين في كثافة العمليات الحسابية: إذ يُمكن فك تشفير الكلمة المُستلمة من شفرة ريد-سولومون المطوية، والتعامل معها ككلمة مُستلمة من شفرة ريد-سولومون الأصلية، ثم تشغيل خوارزمية فك تشفير قائمة ريد-سولومون عليها. ومن الواضح أن هذه القائمة ستحتوي على جميع كلمات شفرة ريد-سولومون المطوية ضمن نطاق المسافة.${\displaystyle \rho }$من الكلمة الواردة، بالإضافة إلى بعض الإضافات التي يمكننا حذفها.

كذلك، يُعدّ فك تشفير كود ريد-سولومون المطوي مهمةً أسهل. لنفترض أننا نريد تصحيح ثلث الأخطاء. يجب أن تُصحّح خوارزمية فك التشفير المختارة نمط خطأ يُصحّح كل رمز ثالث في ترميز ريد-سولومون. ولكن بعد الطي، سيُفسد نمط الخطأ هذا جميع الرموز.${\displaystyle \mathbb {F} _{q}^{3}}$وسيؤدي ذلك إلى إلغاء الحاجة إلى تصحيح الأخطاء. ويُشار إلى انتشار هذه الأخطاء باللون الأزرق في الوصف البياني. وهذا يثبت أنه بالنسبة لنسبة ثابتة من الأخطاء${\displaystyle \rho ,}$تقلل عملية الطي من مرونة القناة في توزيع الأخطاء، مما يؤدي بدوره إلى تقليل عدد أنماط الأخطاء التي تحتاج إلى تصحيح.

إنها عملية استيفاء على نمط ويلش-بيرلكامب (لأنها يمكن اعتبارها تعميمًا عالي الأبعاد لخوارزمية ويلش-بيرلكامب). لنفترض أننا تلقينا كلمة رمزية${\displaystyle y}$التابع${\displaystyle m}$شفرة ريد-سولومون المطوية كما هو موضح أدناه

${\displaystyle \left({\begin{bmatrix}y_{0}\\y_{1}\\y_{2}\\\cdots \\y_{m-1}\end{bmatrix}},{\begin{bmatrix}y_{m}\\y_{m+1}\\y_{m+2}\\\cdots \\y_{2m-1}\end{bmatrix}},\ldots ,{\begin{bmatrix}y_{n-m}\\y_{n-m+1}\\y_{n-m+2}\\\cdots \\y_{n-1}\end{bmatrix}}\right)}$

نقوم باستيفاء متعدد الحدود غير الصفري

${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})=A_{0}(X)+A_{1}(X)Y_{1}+\cdots +A_{s}(X)Y_{s},\qquad {\begin{cases}\deg(A_{i})\leqslant D&1\leqslant i\leqslant s\\\deg(A_{0})\leqslant D+k-1&\end{cases}}}$

باستخدام معلمة درجة مختارة بعناية${\displaystyle D}$.

${\displaystyle D=\left\lfloor {\frac {N(m-s+1)-k+1}{s+1}}\right\rfloor }$

لذا ستكون متطلبات الاستيفاء

${\displaystyle Q\left(\gamma ^{im+j},y_{im+j},y_{im+j+1},\ldots ,y_{im+j+s-1}\right)=0,\quad {\text{for}}\quad i=0,1,\ldots ,{\tfrac {n}{m}}-1,j=0,1,\ldots ,m-s.}$

ثم عدد وحيدات الحدود في${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})}$يكون

${\displaystyle (D+1)s+D+k=(D+1)(s+1)+k-1>N(m-s+1)}$

لأن عدد وحيدات الحدود في${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})}$أكبر من عدد شروط الاستيفاء. لدينا اللمة التالية

اللمة 1.${\displaystyle 0\neq Q\in \mathbb {F} _{q}[X,Y_{1},\ldots ,Y_{s}]}$يمكن إيجاد الحل الذي يحقق شرط الاستيفاء المذكور أعلاه عن طريق حل نظام خطي متجانس على${\displaystyle \mathbb {F} _{q}}$مع أقصى حد${\displaystyle Nm}$القيود والمتغيرات. علاوة على ذلك، يمكن إجراء هذا الاستيفاء في${\displaystyle O(Nm\log ^{2}(Nm)\log \log(Nm))}$العمليات فوق${\displaystyle \mathbb {F} _{q}}$[ ^{3 ]​}

توضح لنا هذه اللمة أنه يمكن تنفيذ خطوة الاستيفاء في وقت شبه خطي.

حتى الآن، تحدثنا عن كل ما نحتاجه لكثير الحدود متعدد المتغيرات${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})}$المهمة المتبقية هي التركيز على كثيرات الحدود الخاصة بالرسالة${\displaystyle f(X)}$.

اللمة 2. إذا كانت رسالة مرشحة متعددة الحدود${\displaystyle f(X)\in \mathbb {F} [X]}$هي متعددة حدود من الدرجة على الأكثر${\displaystyle k-1}$الذي يتوافق ترميز ريد-سولومون المطوي الخاص به مع الكلمة المستلمة${\displaystyle y}$على الأقل${\displaystyle t}$أعمدة مع

${\displaystyle t>{{D+k-1} \over {m-s+1}},}$

ثم ${\displaystyle Q(X,f(X),f(\gamma X),\ldots ,f(\gamma _{s-1}X))=0.}$^{[ 4 ]}

هنا تعني كلمة "موافق" أن جميع${\displaystyle m}$يجب أن تتطابق القيم في العمود مع القيم المقابلة في كلمة المرور${\displaystyle y}$.

تُظهر لنا هذه اللمة أن أي متعددة حدود من هذا القبيل${\displaystyle Q(X,Y_{1},\ldots ,Y_{s})}$يُقدّم شرطًا جبريًا يجب تحقيقه بالنسبة لكثيرات الحدود الخاصة بالرسالة.${\displaystyle f(x)}$أننا مهتمون بفك تشفير القوائم.

بدمج اللمة 2 والمعامل${\displaystyle D}$لدينا

${\displaystyle t(m-s+1)>{\frac {N(m-s+1)+s(k-1)}{s+1}}}$

علاوة على ذلك، يمكننا الحصول على حد فك التشفير

${\displaystyle t\geqslant {\frac {N}{s+1}}+{\frac {s}{s+1}}\cdot {\frac {k}{m-s+1}}=N\left({\frac {1}{s+1}}+{\frac {s}{s+1}}\cdot {\frac {mR}{m-s+1}}\right)}$

نلاحظ أن الاتفاق الجزئي هو

${\displaystyle {\dfrac {1}{s+1}}+{\dfrac {s}{s+1}}\cdot {\dfrac {mR}{m-s+1}}}$

خلال هذه الخطوة، ينصب تركيز مهمتنا على كيفية إيجاد جميع كثيرات الحدود${\displaystyle f\in {\mathbb {F} _{q}[X]}}$بدرجة لا تزيد عن${\displaystyle k-1}$وتحقيق المعادلة التي حصلنا عليها من الخطوة 1، وهي

${\displaystyle A_{0}(X)+A_{1}(X)f(X)+A_{2}(X)f(\gamma X)+\cdots +A_{s}(X)f(\gamma ^{s-1}X)=0}$

بما أن المعادلة أعلاه تشكل نظام معادلات خطية على${\displaystyle \mathbb {F} _{q}}$في المعاملات${\displaystyle f_{0},f_{1},\ldots ,f_{k-1}}$من متعدد الحدود

${\displaystyle f(X)=f_{0}+f_{1}X+\cdots +f_{k-1}X^{k-1},}$

حلول المعادلة أعلاه هي فضاء جزئي أفيني من${\displaystyle \mathbb {F} _{q}^{k}}$هذه الحقيقة هي النقطة الأساسية التي تؤدي إلى خوارزمية فعالة - يمكننا حل النظام الخطي.

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

في الواقع، لها حد أعلى كما توضح اللمة أدناه.

اللمة 3. إذا كان ترتيب${\displaystyle \gamma }$هو على الأقل${\displaystyle k}$(خاصة عندما${\displaystyle \gamma }$إذا كانت الدالة أولية، فإن بُعد الحل يكون على الأكثر${\displaystyle s-1}$[ ^{5 ]​}

توضح لنا هذه اللمة الحد الأعلى لأبعاد فضاء الحل.

وأخيرًا، بناءً على التحليل السابق، لدينا النظرية التالية

النظرية 1. بالنسبة لرمز ريد-سولومون المطوي${\displaystyle FRS_{q}^{(m)}[n,k]}$بطول الكتلة${\displaystyle N={\tfrac {n}{m}}}$وقيم${\displaystyle R={\tfrac {k}{n}},}$ينطبق ما يلي على جميع الأعداد الصحيحة${\displaystyle s,1\leqslant s\leqslant m}$. بالنظر إلى كلمة مستلمة${\displaystyle y\in (\mathbb {F} _{q}^{m})^{N}}$، في${\displaystyle O((Nm\log q)^{2})}$مع مرور الوقت، يمكن إيجاد أساس لفضاء جزئي ذي بُعد على الأكثر${\displaystyle s-1}$التي تحتوي على جميع كثيرات الحدود الخاصة بالرسالة${\displaystyle f\in \mathbb {F} _{q}[X]}$من درجة أقل من${\displaystyle k}$يختلف ترميز FRS الخاص به عن${\displaystyle y}$في جزء صغير على الأكثر

${\displaystyle {\frac {s}{s+1}}\left(1-{\frac {mR}{m-s+1}}\right)}$

التابع${\displaystyle N}$مواقع الكلمات السرية.

متى${\displaystyle s=m=1}$نلاحظ أن هذا يختزل إلى خوارزمية فك تشفير فريدة تصل إلى جزء${\displaystyle (1-R)/2}$من الأخطاء. بعبارة أخرى، يمكننا اعتبار خوارزمية فك التشفير الفريدة تخصصًا لخوارزمية فك تشفير القوائم. الكمية حوالي${\displaystyle n^{O(1/\varepsilon )}}$بالنسبة لخيارات المعلمات التي تحقق نصف قطر فك تشفير القائمة من${\displaystyle 1-R-\varepsilon }$.

توضح لنا النظرية 1 بالضبط حجم نصف قطر الخطأ.

والآن، حصلنا أخيرًا على فضاء الحلول. مع ذلك، لا تزال هناك مشكلة واحدة قائمة. حجم القائمة في أسوأ الحالات هو${\displaystyle n^{\Omega (1/\varepsilon )}}$لكن القائمة الفعلية للكلمات المشفرة القريبة ليست سوى مجموعة صغيرة ضمن تلك المساحة الفرعية. لذا نحتاج إلى عملية ما لتقليص المساحة الفرعية وتضييق نطاقها. تستغرق عملية التقليص هذه${\displaystyle q^{s}}$الوقت في أسوأ الحالات. لسوء الحظ، لا يُعرف كيفية تحسين وقت التشغيل لأننا لا نعرف كيفية تحسين حد حجم القائمة لرمز ريد-سولومون المطوي.

تتحسن الأمور إذا قمنا بتغيير الكود عن طريق اختيار مجموعة فرعية بعناية من جميع الدرجات الممكنة${\displaystyle k-1}$عند استخدام كثيرات الحدود كرسائل، يتبين أن حجم القائمة أصغر بكثير مع انخفاض طفيف في المعدل. سنتناول هذا بإيجاز في الخطوة التالية.

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

ذُكر في الخطوة الثانية أنه إذا اختار المرء بعناية مجموعة فرعية فقط من جميع الدرجات الممكنة${\displaystyle k-1}$باستخدام كثيرات الحدود كرسائل، يمكن تقليل حجم القائمة بشكل كبير. سنوسع نطاق مناقشتنا هنا.

ولتحقيق هذا الهدف، تكمن الفكرة في تقييد متجه المعاملات${\displaystyle (f_{0},f_{1},\ldots ,f_{k-1})}$إلى مجموعة فرعية خاصة${\displaystyle \nu \subseteq \mathbb {F} _{q}^{k}}$، والذي يستوفي الشرطين التاليين:

الشرط 1. المجموعة${\displaystyle \nu }$يجب أن يكون كبيرًا بما فيه الكفاية (${\displaystyle |\nu |\geq q^{(1-\varepsilon )k}}$).

وذلك لضمان ألا يتجاوز معدل التخفيض عاملاً واحداً.${\displaystyle (1-\varepsilon )}$.

الشرط الثاني: المجموعة${\displaystyle \nu }$ينبغي أن يكون تقاطعها مع أي فضاء فرعي منخفضًا${\displaystyle S}$من الأبعاد${\displaystyle s}$مُرضٍ${\displaystyle S\subset \mathbb {F} _{q}^{k}}$و${\displaystyle |S\cap \nu |\leqslant L.}$تُسمى هذه المجموعة الفرعية بالمجموعة الفرعية المراوغة للفضاء الفرعي.

الحد الأقصى لحجم القائمة في أسوأ الحالات هو${\displaystyle n^{\Omega (1/\varepsilon )}}$ويمكن اختزالها إلى حد صغير نسبيًا${\displaystyle O(1/\varepsilon ^{2})}$باستخدام مجموعات فرعية تتجنب الفضاء الجزئي.

خلال هذه الخطوة، ولأنها تتطلب فحص كل عنصر من عناصر فضاء الحل الذي نحصل عليه من الخطوة 2، فإنها تستغرق${\displaystyle q^{s}}$الوقت في أسوأ الحالات (${\displaystyle s}$(وهو بُعد فضاء الحل الفرعي).

قام كل من دفير ولوفيت بتحسين النتيجة بناءً على عمل غورو سوامي، والذي يمكن أن يقلل حجم القائمة إلى قيمة ثابتة.

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

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

نظرة عامة على خوارزمية فك تشفير القوائم الجبرية الخطية لرمز FRS

خطوات	الاستيفاء البحث عن الجذور تقليم
وقت التشغيل	${\displaystyle n^{\Omega (1/\varepsilon ^{2})}}$
نصف قطر الخطأ	${\displaystyle 1-R-\varepsilon }$
حجم القائمة	${\displaystyle n^{O(1/\varepsilon ^{2})}}$