تصحيح خطأ ريد-سولومون

تصحيح خطأ ريد-سولومون

معلومات عامة

صنف فرعي من	erasure code MDS code
سُمِّي باسم	إرفينغ إس. ريد غوستاف سليمان
تاريخ النشر	1960
يدرسه	نظرية الترميز
المكتشف أو المخترع	إرفينغ إس. ريد غوستاف سليمان

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

تعمل أكواد ريد–سولومون على كتلة من البيانات يتم التعامل معها كمجموعة من عناصر المجال المحدود تسمى الرموز. تتمتع رموز ريد–سولومون بالقدرة على اكتشاف أخطاء الرموز المتعددة وتصحيحها. من خلال إضافة رموز التحقق t = n − k إلى البيانات، يمكن لكود ريد–سولومون اكتشاف (ولكن ليس تصحيح) أي مجموعة من الرموز الخاطئة حتى t، أو تحديد وتصحيح ما يصل إلى ⌊t/2⌋ من الرموز الخاطئة في مواقع غير معروفة. باعتباره رمز مسح ‏، فإنه يمكنه تصحيح ما يصل إلى t عمليات مسح في المواقع المعروفة والمقدمة للخوارزمية، أو يمكنه اكتشاف وتصحيح مجموعات من الأخطاء والمسح. تعتبر أكواد ريد–سولومون مناسبة أيضًا كأكواد تصحيح أخطاء البتات متعددة الانفجارات، حيث أن تسلسل b + 1يمكن أن يؤثر خطأ بت b + 1 متتالي على رمزين بحجم b كحد أقصى. يعود اختيار t إلى مصمم الكود، ويمكن تحديده ضمن حدود واسعة.

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

التاريخ

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

في عام 1960 أيضًا، تم وصف فك تشفير متعدد الحدود عملي ثابت لرموز بي سي إتش الذي طوره دانييل جورنشتاين ونيل زيرلر في تقرير صادر عن مختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا بواسطة زيرلر في يناير 1960 وفي وقت لاحق في مقال في يونيو 1961. تم وصف فك تشفير جورنشتاين-زيرلر والعمل المرتبط به على رموز بي سي إتش في كتاب «رموز تصحيح الأخطاء» بقلم و. ويزلي بيترسون (1961). بحلول عام 1963 (أو ربما قبل ذلك)، كان جيه جيه ستون (وآخرون) أدرك أن رموز ريد–سولومون يمكنها استخدام مخطط بي سي إتش باستخدام متعدد الحدود المولد الثابت، مما يجعل مثل هذه الرموز فئة خاصة من رموز بي سي إتش، ولكن رموز ريد–سولومون المستندة إلى مخطط الترميز الأصلي ليست فئة من رموز بي سي إتش، واعتمادًا على مجموعة نقاط التقييم، فهي ليست حتى رموزًا دورية ‏.

في عام 1969، تم تطوير فك تشفير مخطط بي سي إتش المحسن بواسطة إلوين بيرليكامب وجيمس ماسي ومنذ ذلك الحين أصبح يُعرف باسم خوارزمية فك تشفير بيرليكامب-ماسي ‏.

في عام 1975، تم تطوير فك تشفير مخطط بي سي إتش محسن آخر بواسطة ياسو سوجياما، استنادًا إلى خوارزمية إقليدية موسعة.

في عام 1977، تم تنفيذ أكواد ريد–سولومون في برنامج فوييجر في شكل أكواد تصحيح الأخطاء المتسلسلة ‏. ظهر أول تطبيق تجاري في المنتجات الاستهلاكية المنتجة بكميات كبيرة في عام 1982 مع القرص المضغوط، حيث تم استخدام رمزين متداخلين من نوع ريد–سولومون. اليوم، يتم تنفيذ أكواد ريد–سولومون على نطاق واسع في أجهزة التخزين الرقمية ومعايير الاتصالات الرقمية، على الرغم من استبدالها ببطء بأكواد بوز-تشودهوري-هوكوينغيم (بي سي إتش). على سبيل المثال، يتم استخدام رموز ريد–سولومون في معيار البث الرقمي للفيديو (بي في دي) معيار بث الفيديو الرقمي فضائيا، بالاشتراك مع رمز داخلي ملتف، ولكن يتم استخدام رموز بي سي إتش مع إل دي بي سي ‏ في خليفته، معيار بي في دي-إس2.

في عام 1986، تم تطوير فك تشفير المخطط الأصلي المعروف باسم خوارزمية بيرليكامب-ويلش ‏.

في عام 1996، تم تطوير أشكال مختلفة من أجهزة فك التشفير الأصلية والتي تسمى أجهزة فك التشفير القائمة أو أجهزة فك التشفير الناعمة بواسطة مادو سودان وآخرين، ويستمر العمل على هذه الأنواع من أجهزة فك التشفير (انظر خوارزمية فك تشفير القائمة جوروسوامي-سودان ‏).

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

التطبيقات

تخزين البيانات

يتم استخدام تشفير ريد–سولومون على نطاق واسع في أنظمة التخزين الشامل لتصحيح أخطاء الانفجار المرتبطة بعيوب الوسائط.

يعتبر تشفير ريد–سولومون أحد المكونات الأساسية للقرص المضغوط. كان هذا أول استخدام لترميز تصحيح الأخطاء القوي في منتج استهلاكي يتم إنتاجه بكميات كبيرة، وتستخدم دات ودي في دي مخططات مماثلة. في القرص المضغوط، يتم فصل طبقتين من ترميز ريد–سولومون بواسطة متداخل ملتف ذي 28 اتجاهًا مما ينتج عنه مخطط يسمى ترميز ريد–سولومون المتداخل المتقاطع (ترميز ريد–سولومون المتداخل ‏). العنصر الأول في فك تشفير ترميز ريد–سولومون المتداخل هو رمز ريد–سولومون الداخلي الضعيف نسبيًا (32،28)، والذي تم اختصاره من رمز (255،251) برموز مكونة من 8 بت. يمكن لهذا الكود تصحيح أخطاء تصل إلى 2 بايت لكل كتلة مكونة من 32 بايت. والأمر الأكثر أهمية هو أنه يقوم بتمييز أي كتل غير قابلة للتصحيح على أنها محذوفة، أي الكتل التي تحتوي على أخطاء أكبر من 2 بايت. يتم بعد ذلك نشر الكتل المفكوكة المكونة من 28 بايتًا، مع مؤشرات المسح، بواسطة مزيل التداخل إلى كتل مختلفة من الكود الخارجي (28،24). بفضل إزالة التداخل، تصبح كتلة ممسوحة مكونة من 28 بايتًا من الكود الداخلي بايتًا ممسوحًا واحدًا في كل كتلة من كتل الكود الخارجية البالغ عددها 28 بايتًا. يقوم الكود الخارجي بتصحيح هذه المشكلة بسهولة، لأنه يمكنه التعامل مع ما يصل إلى 4 عمليات مسح من هذا القبيل لكل كتلة.

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

تستخدم أقراص دي في دي مخططًا مشابهًا، ولكن مع كتل أكبر بكثير، وكود داخلي (208,192)، وكود خارجي (182,172).

يتم استخدام تصحيح خطأ ريد–سولومون أيضًا في ملفات بارشيف والتي يتم نشرها عادةً مع ملفات الوسائط المتعددة على يوزنت. كما استخدمت خدمة التخزين عبر الإنترنت الموزعة ووالا (التي تم إيقافها في عام 2015) أيضًا ريد–سولومون عند تقسيم الملفات.

الرمز الشريطي

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

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

نقل البيانات

يمكن استخدام الأشكال المتخصصة من رموز ريد–سولومون، وتحديدًا كوشي-آر إس و فاندرموند-آر إس، للتغلب على الطبيعة غير الموثوقة لنقل البيانات عبر قنوات المسح. تفترض عملية الترميز رمز آر إس (N، K) مما يؤدي إلى إنشاء N كلمة رمزية بطول N رمز، كل منها يخزن K رمزًا من البيانات، والتي يتم إرسالها بعد ذلك عبر قناة مسح.

إن أي مجموعة من الكلمات الرمزية (K) التي تم تلقيها في الطرف الآخر تكون كافية لإعادة بناء كل الكلمات الرمزية (N). يتم عادةً ضبط معدل الترميز على 1/2 ما لم يكن من الممكن نمذجة احتمالية محو القناة بشكل مناسب ورؤيتها أقل. في الختام، يكون N عادةً 2 K، مما يعني أنه يجب استلام نصف جميع كلمات المرور المرسلة على الأقل من أجل إعادة بناء جميع كلمات المرور المرسلة.

تُستخدم أكواد ريد–سولومون أيضًا في أنظمة الخط المشترك الرقمي ومواصفات بروتوكول الاتصالات الفضائية ‏ الخاصة بـ سي سي إس دي إس كشكل من أشكال تصحيح الأخطاء الأمامية.

النقل الفضائي

نظام ترميز متسلسل في الفضاء العميق. التدوين: آر إس (255، 223) + سي سي («طول القيد» = 7، معدل الترميز = 1/2).

كان أحد التطبيقات المهمة لتشفير ريد–سولومون هو تشفير الصور الرقمية التي أرسلها برنامج فوييجر.

قدمت مركبة فوييجر تشفير ريد–سولومون المترابط مع الأكواد التلافيفية ‏، وهي ممارسة أصبحت منذ ذلك الحين منتشرة على نطاق واسع في الفضاء العميق والاتصالات عبر الأقمار الصناعية (على سبيل المثال، البث الرقمي المباشر).

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

كانت الإصدارات الحديثة من الترميز التلافيفي المتسلسل المفكوك بواسطة ريد–سولومون/فيتربي تُستخدم ولا تزال تُستخدم في بعثات مارس باثفايندر، وجاليليو، ومركبة استكشاف المريخ، وكاسيني، حيث تعمل ضمن حوالي 1-1.5 ديسيبل من الحد الأقصى، وهو سعة شانون.

يتم الآن استبدال هذه الرموز المتسلسلة برموز توربو ‏ أكثر قوة:

مخططات ترميز القنوات المستخدمة في بعثات ناسا

الأعوام	الترميز	المهمة(المهام)
1958–الآن	غير مشفر	المستكشف، البحار، والعديد من الآخرين
1968–1978	الرموز التلافيفية (سي سي) (25، 1/2)	رائد، فينوس
1969–1975	رمز ريد-مولر (32، 6)	بحار، فايكنج
1977–الآن	كود جولاي الثنائي ‏	مسافر
1977–الآن	آر إس(255، 223) + سي سي(7، 1/2)	فوييجر، جاليليو، والعديد من الآخرين
1989–2003	آر إس(255، 223) + سي سي(7، 1/3)	مسافر
1989–2003	آر إس(255، 223) + سي سي(14، 1/4)	جاليليو
1996–الآن	آر إس + سي سي (15، 1/6)	كاسيني، مارس باثفايندر، وغيرها
2004–الآن	أكواد التوربو	رسول، ستيريو، إم آر أو، إم إس إل، وغيرها
est. 2009	رموز إل دي بي سي	كوكبة، إم 2020، مافن

الإنشاءات (الترميز)

إن شفرة ريد–سولومون هي في الواقع عائلة من الشفرات، حيث يتميز كل شفرة بثلاثة معلمات: حجم الأبجدية q، وطول الكتلة n، وطول الرسالة k، مع $k<n\leq q$. يتم تفسير مجموعة رموز الأبجدية على أنها الحقل المحدود $F$ من أجل $q$، وبالتالي، $q$ يجب أن تكون قوة رئيسية. في أكثر معلمات كود ريد–سولومون فائدة، يكون طول الكتلة عادةً مضاعفًا ثابتًا لطول الرسالة، أي المعدل $R={\frac {k}{n}}$ هو ثابت ما، وعلاوة على ذلك، فإن طول الكتلة إما أن يكون مساويًا لحجم الأبجدية أو أقل منه بواحد، أي، $n=q$ أو $n=q-1$.

وجهة النظر الأصلية لريد وسولومون: الكلمة الرمزية كسلسلة من القيم

توجد إجراءات ترميز مختلفة لرمز ريد–سولومون، وبالتالي، توجد طرق مختلفة لوصف مجموعة كل الكلمات الرمزية. في العرض الأصلي لريد وسولومون، كل كلمة رمزية من رمز ريد–سولومون هي عبارة عن تسلسل من قيم الدالة لكثيرة حدود من الدرجة الأقل من $k$. من أجل الحصول على كلمة رمزية لرمز ريد–سولومون، يتم التعامل مع رموز الرسائل (كل منها ضمن الأبجدية بحجم q) كمعاملات لكثيرة حدود $p$ من الدرجة أقل من $k$، فوق المجال المحدود $F$ مع $q$ عناصر. وبدوره، فإن كثيرة الحدود $p$ يتم تقييمه في $n\leq q$ نقاط مميزة $a_{1},\dots ,a_{n}$ من الميدان $F$، وتسلسل القيم هو الكلمة الرمزية المقابلة. تتضمن الاختيارات الشائعة لمجموعة من نقاط التقييم ما يلي: $\{0,1,2,\dots ,n-1\}$، $\{0,1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-2}\}$، أو ل $n<q$، $\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}$،...، أين $\alpha$ هو عنصر بدائي ‏ من $F$.

رسميا، المجموعة $\mathbf {C}$ يتم تعريف كلمات رمز ريد–سولومون على النحو التالي: $$\mathbf {C} ={\Bigl \{}\;{\bigl (}p(a_{1}),p(a_{2}),\dots ,p(a_{n}){\bigr )}\;{\Big |}\;p{\text{ is a polynomial over }}F{\text{ of degree }}<k\;{\Bigr \}}\,.$$ نظرًا لأن أي حدودين مختلفتين بدرجة أقل من $k$ أتفق على الأكثر $k-1$ النقاط، وهذا يعني أن أي كلمتين رمزيتين من قانون ريد–سولومون تختلفان في ما لا يقل عن $n-(k-1)=n-k+1$ المواقف. علاوة على ذلك، هناك حدوديتان متفقتان في $k-1$ النقاط ولكنها ليست متساوية، وبالتالي فإن مسافة قانون ريد–سولومون هي بالضبط $d=n-k+1$. ثم المسافة النسبية هي $\delta =d/n=1-k/n+1/n=1-R+1/n\sim 1-R$، أين $R=k/n$ هو المعدل. إن هذه المقايضة بين المسافة النسبية والمعدل مثالية بشكل مقارب، حيث أن كل كود يلبي الحد الأقصى للسنجلتون ‏ $\delta +R\leq 1+1/n$. باعتباره رمزًا يحقق هذه المقايضة المثلى، فإن رمز ريد–سولومون ينتمي إلى فئة الرموز القابلة للفصل عند أقصى مسافة.

في حين أن عدد كثيرات الحدود المختلفة من الدرجة الأقل من k وعدد الرسائل المختلفة متساويان $q^{k}$ وبالتالي، يمكن تعيين كل رسالة بشكل فريد لمثل هذه الحدود، وهناك طرق مختلفة للقيام بهذا الترميز. يفسر البناء الأصلي لريد-سولومون الرسالة x باعتبارها معاملات كثيرة الحدود p، بينما تفسر البناءات اللاحقة الرسالة باعتبارها قيم كثيرة الحدود عند أول k نقطة $a_{1},\dots ,a_{k}$ ويمكن الحصول على كثيرة الحدود p باستيفاء هذه القيم بكثيرة حدود بدرجة أقل من k. تتميز عملية الترميز الأخيرة، وإن كانت أقل كفاءةً بعض الشيء، بميزة أنها تُنتج شفرةً منهجية ‏، أي أن الرسالة الأصلية تُدرج دائمًا كتسلسل فرعي للكلمة المفتاحية.

إجراء ترميز بسيط: الرسالة كسلسلة من المعاملات

في البناء الأصلي لريد وسليمان، الرسالة $m=(m_{0},\dots ,m_{k-1})\in F^{k}$ يتم تعيينه إلى كثير الحدود $p_{m}$ مع $$p_{m}(a)=\sum _{i=0}^{k-1}m_{i}a^{i}\,.$$ كلمة السر لـ $m$ يتم الحصول عليها عن طريق التقييم $p_{m}$ في $n$ نقاط مختلفة $a_{0},\dots ,a_{n-1}$ من الميدان $F$. وبالتالي فإن وظيفة الترميز الكلاسيكية $C:F^{k}\to F^{n}$ بالنسبة لقانون ريد–سولومون، يتم تعريفه على النحو التالي: $$C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}$$ هذه الوظيفة $C$ هو رسم تخطيطي خطي، أي أنه يلبي $C(m)=Am$ لما يلي $n\times k$ -مصفوفة $A$ مع عناصر من $F$ : $$C(m)=Am={\begin{bmatrix}1&a_{0}&a_{0}^{2}&\dots &a_{0}^{k-1}\\1&a_{1}&a_{1}^{2}&\dots &a_{1}^{k-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&a_{n-1}&a_{n-1}^{2}&\dots &a_{n-1}^{k-1}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}$$

هذه المصفوفة هي مصفوفة فاندرموند $F$. بعبارة أخرى، فإن شفرة ريد–سولومون هي شفرة خطية، وفي إجراء الترميز الكلاسيكي، تكون مصفوفة المولد الخاصة بها $A$.

إجراء الترميز المنهجي: الرسالة كتسلسل أولي من القيم

هناك إجراءات ترميز بديلة تعمل على إنتاج رمز ريد–سولومون المنهجي. تستخدم إحدى الطرق استيفاء لاغرانج لحساب كثيرات الحدود $p_{m}$ مثل ذلك $$p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.$$ ثم $p_{m}$ يتم تقييمه في النقاط الأخرى $a_{k},\dots ,a_{n-1}$.

$$C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}$$

هذه الوظيفة $C$ هي عبارة عن رسم خطي. لتوليد مصفوفة الترميز النظامية المقابلة G، اضرب مصفوفة Vandermonde A في معكوس مصفوفة المربع الأيسر الفرعية A.

$$G=(A{\text{'s left square submatrix}})^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}$$

$C(m)=Gm$ لما يلي $n\times k$ -مصفوفة $G$ مع عناصر من $F$ : $$C(m)=Gm={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}$$

تحويل فورييه المتقطع وعكسه

تحويل فورييه المنفصل هو في الأساس نفس إجراء الترميز؛ فهو يستخدم متعدد الحدود المولد $p_{m}$ لربط مجموعة من نقاط التقييم بقيم الرسائل كما هو موضح أعلاه: $$C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}$$

يمكن استخدام تحويل فورييه العكسي لتحويل مجموعة خالية من الأخطاء من قيم الرسائل n < q مرة أخرى إلى متعددة الحدود المشفرة لمعاملات k، مع القيد الذي ينص على أنه لكي يعمل هذا، يجب أن تكون مجموعة نقاط التقييم المستخدمة لتشفير الرسالة عبارة عن مجموعة من القوى المتزايدة لـ α : $$a_{i}=\alpha ^{i}$$$$a_{0},\dots ,a_{n-1}=\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}$$

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

وجهة نظر بي سي إتش: الكلمة الرمزية كسلسلة من المعاملات

في هذا العرض، يتم تفسير الرسالة كمعاملات متعددة الحدود $p(x)$. يقوم المرسل بحساب كثير الحدود ذي الصلة $s(x)$ من الدرجة $n-1$ أين $n\leq q-1$ ويرسل الحدود المتعددة $s(x)$. كثيرة الحدود $s(x)$ يتم إنشاؤها عن طريق ضرب حدود الرسالة $p(x)$، والتي لديها درجة $k-1$، مع مولد متعدد الحدود $g(x)$ من الدرجة $n-k$ وهذا معروف لدى المرسل والمستقبل.مولد الحدود متعدد الحدود $g(x)$ يتم تعريفه على أنه متعدد الحدود الذي تكون جذوره عبارة عن قوى متسلسلة لبدائية مجال جالوا $\alpha$$$g(x)=\left(x-\alpha ^{i}\right)\left(x-\alpha ^{i+1}\right)\cdots \left(x-\alpha ^{i+n-k-1}\right)=g_{0}+g_{1}x+\cdots +g_{n-k-1}x^{n-k-1}+x^{n-k}$$

بالنسبة لـ«رمز المعنى الضيق»، $i=1$.

$$\mathbf {C} =\left\{\left(s_{1},s_{2},\dots ,s_{n}\right)\;{\Big |}\;s(a)=\sum _{i=1}^{n}s_{i}a^{i}{\text{ is a polynomial that has at least the roots }}\alpha ^{1},\alpha ^{2},\dots ,\alpha ^{n-k}\right\}.$$

إجراء الترميز المنهجي

يمكن تعديل إجراء الترميز لعرض بي سي إتش لرموز ريد–سولومون لإنتاج إجراء ترميز منهجي، حيث تحتوي كل كلمة رمزية على الرسالة كبادئة، وتضيف ببساطة رموز تصحيح الأخطاء كلاحقة. هنا، بدلا من الإرسال $s(x)=p(x)g(x)$ يقوم المشفر بإنشاء الحدود المنقولة $s(x)$ بحيث تكون معاملات $k$ أكبر أحاديات الحدود تساوي المعاملات المقابلة لـ $p(x)$، ومعاملات الدرجة الأدنى لـ $s(x)$ يتم اختيارهم بالضبط بهذه الطريقة $s(x)$ يصبح قابلا للقسمة على $g(x)$. ثم معاملات $p(x)$ هي تسلسل جزئي لمعاملات $s(x)$. للحصول على كود منهجي بشكل عام، نقوم بإنشاء رسالة متعددة الحدود $p(x)$ من خلال تفسير الرسالة على أنها تسلسل معاملاتها.

رسميًا، يتم البناء عن طريق الضرب $p(x)$ بواسطة $x^{t}$ لإفساح المجال ل $t=n-k$ رموز التحقق، وتقسيم هذا المنتج على $g(x)$ لإيجاد الباقي، ثم تعويض هذا الباقي عن طريق طرحه. ال $t$ يتم إنشاء رموز التحقق عن طريق حساب الباقي $s_{r}(x)$ : $$s_{r}(x)=p(x)\cdot x^{t}\ {\bmod {\ }}g(x).$$

الباقي حاصل على درجة علمية على الأكثر $t-1$، في حين أن معاملات $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ في كثير الحدود $p(x)\cdot x^{t}$ هي صفر. لذلك، التعريف التالي للكلمة الرمزية $s(x)$ لديه الخاصية التي هي الأولى $k$ المعاملات متطابقة مع معاملات $p(x)$ : $$s(x)=p(x)\cdot x^{t}-s_{r}(x)\,.$$ونتيجة لذلك، فإن الكلمات المشفرة $s(x)$ هي في الواقع عناصر من $\mathbf {C}$ أي أنها قابلة للقسمة على متعددة الحدود المولدة $g(x)$ : $$s(x)\equiv p(x)\cdot x^{t}-s_{r}(x)\equiv s_{r}(x)-s_{r}(x)\equiv 0\mod g(x)\,.$$هذه الوظيفة $s$ هي عبارة عن رسم خطي. لتوليد مصفوفة الترميز النظامية المقابلة G، قم بتعيين المصفوفة الفرعية المربعة اليسرى لـ G إلى مصفوفة الهوية ثم قم بترميز كل صف:

$$G={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}$$ مع تجاهل الأصفار الأولية، الصف الأخير = $g(x)$.

$C(m)=mG$ لما يلي $n\times k$ -مصفوفة $G$ مع عناصر من $F$ : $$C(m)=mG={\begin{bmatrix}m_{0}&m_{1}&\ldots &m_{k-1}\end{bmatrix}}{\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}$$

الخصائص

رمز ريد–سولومون هو رمز [ n، k، n − k + 1]؛ بمعنى آخر، هو رمز كتلة خطي بطول n (على F) مع البعد k ومسافة هامينج الدنيا ${\textstyle d_{\min }=n-k+1.}$ يعتبر كود ريد–سولومون مثاليًا بمعنى أن الحد الأدنى للمسافة له أقصى قيمة ممكنة لكود خطي بحجم (n، ك)؛ وهذا ما يُعرف باسم حدود سينجلتون ‏. يُطلق على هذا الرمز أيضًا اسم رمز المسافة القصوى القابلة للفصل (إم دي إس) ‏.

يتم تحديد قدرة تصحيح الخطأ لرمز ريد–سولومون من خلال المسافة الدنيا، أو على نحو مكافئ، من خلال $n-k$، مقياس التكرار في الكتلة. إذا لم تكن مواقع رموز الخطأ معروفة مسبقًا، فيمكن لكود ريد–سولومون تصحيح ما يصل إلى $(n-k)/2$ الرموز الخاطئة، أي أنه يمكنه تصحيح نصف عدد الأخطاء التي تحتوي على رموز زائدة تمت إضافتها إلى الكتلة. في بعض الأحيان تكون مواقع الأخطاء معروفة مسبقًا (على سبيل المثال، «المعلومات الجانبية» في نسبة الإشارة إلى الضوضاء في جهاز إزالة التعديل) - وتسمى هذه بالمحو. يمكن لرمز ريد–سولومون (مثل أي رمز إم دي إس) تصحيح ضعف عدد المحو مقارنة بالأخطاء، ويمكن تصحيح أي مجموعة من الأخطاء والمحو طالما تم استيفاء العلاقة 2E + S ≤ n − k، حيث $E$ هو عدد الأخطاء و $S$ هو عدد المحو في الكتلة.

الأداء النظري لمعدل البتات لرمز ريد–سولومون (إن=255، كيه=233، كيو بي إس كي، أوجن). خاصية تشبه الخطوة.

يمكن وصف حد الخطأ النظري من خلال الصيغة التالية لقناة أوجن لإبدال بإزاحة التردد: $$P_{b}\approx {\frac {2^{m-1}}{2^{m}-1}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }$$ ولخطط التعديل الأخرى: $$P_{b}\approx {\frac {1}{m}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }$$ أين ${\textstyle t={\frac {1}{2}}(d_{\min }-1)}$، $P_{s}=1-(1-s)^{h}$، $h={\frac {m}{\log _{2}M}}$، $s$ هو معدل خطأ الرمز في حالة أوجن غير المشفرة و $M$ هو ترتيب التعديل.

بالنسبة للاستخدامات العملية لرموز ريد–سولومون، من الشائع استخدام حقل محدود $F$ مع $2^{m}$ عناصر. في هذه الحالة، يمكن تمثيل كل رمز على أنه $m$ قيمة البت. يرسل المرسل نقاط البيانات ككتل مشفرة، وعدد الرموز في الكتلة المشفرة هو $n=2^{m}-1$. وبالتالي، فإن كود ريد–سولومون الذي يعمل على رموز مكونة من 8 بتات لديه $n=2^{8}-1=255$ الرموز لكل كتلة. (هذه قيمة شائعة جدًا نظرًا لانتشار أنظمة الكمبيوتر الموجهة للبايتات.) الرقم $k$، مع $k<n$، عدد رموز البيانات في الكتلة هو معلمة تصميم. الكود المستخدم بشكل شائع يشفر $k=223$ رموز بيانات مكونة من ثمانية بتات بالإضافة إلى 32 رمز تكافؤ مكون من ثمانية بتات في $n=255$ - كتلة الرمز؛ يُشار إليها باسم $(n,k)=(255,223)$ الكود، وهو قادر على تصحيح ما يصل إلى 16 خطأ رمزي لكل كتلة.

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

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

إن كون قانون ريد–سولومون دوريًا أم لا يعتمد على التفاصيل الدقيقة للبناء. في وجهة النظر الأصلية لريد وسولومون، حيث تكون الكلمات الرمزية هي قيم كثيرة الحدود، يمكن للمرء اختيار تسلسل نقاط التقييم بطريقة تجعل الكود دوريًا. وعلى وجه الخصوص، إذا $\alpha$ هو جذر بدائي ‏ للحقل $F$، إذن حسب التعريف فإن جميع العناصر غير الصفرية لـ $F$ خذ النموذج $\alpha ^{i}$ ل $i\in \{1,\dots ,q-1\}$، أين $q=|F|$. كل كثيرة حدود $p$ زيادة $F$ يؤدي إلى ظهور كلمة مرور $(p(\alpha ^{1}),\dots ,p(\alpha ^{q-1}))$. منذ الوظيفة $a\mapsto p(\alpha a)$ هي أيضًا كثيرة حدود من نفس الدرجة، هذه الدالة تؤدي إلى كلمة رمزية $(p(\alpha ^{2}),\dots ,p(\alpha ^{q}))$ ؛ منذ $\alpha ^{q}=\alpha ^{1}$ صحيح أن هذه الكلمة الرمزية هي التحول الدوري إلى اليسار للكلمة الرمزية الأصلية المشتقة من $p$. وبالتالي فإن اختيار تسلسل من قوى الجذر البدائية كنقط تقييم يجعل العرض الأصلي لرمز ريد–سولومون دوريًا. تكون رموز ريد–سولومون في عرض بي سي إتش دورية دائمًا لأن رموز بي سي إتش دورية.

الملاحظات

لا يُطلب من المصممين استخدام الأحجام «الطبيعية» لكتل كود ريد–سولومون. يمكن لتقنية تُعرف باسم «الاختصار» إنتاج كود أصغر بأي حجم مرغوب من كود أكبر. على سبيل المثال، يمكن تحويل الكود المستخدم على نطاق واسع (255,223) إلى كود (160,128) عن طريق تعبئة الجزء غير المستخدم من كتلة المصدر بـ 95 صفرًا ثنائيًا وعدم إرسالها. في جهاز فك التشفير، يتم تحميل نفس الجزء من الكتلة محليًا باستخدام الأصفار الثنائية.

يستخدم رمز الاستجابة السريعة، الإصدار 3 (29×29) كتلًا متداخلة. تتكون الرسالة من 26 بايت بيانات ويتم تشفيرها باستخدام كتلتين من رموز ريد-سولومون. كل كتلة عبارة عن رمز (255,233) ريد سولومون مختصر إلى رمز (35,13).

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

فك تشفير عرض بي سي إتش

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

وحدة فك ترميز بيترسون-جورنشتاين-زيرلر

المقالة الرئيسة: رمز بي سي إتش

قام دانييل جورنشتاين ونيل زيرلر بتطوير جهاز فك تشفير تم وصفه في تقرير صادر عن مختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا بواسطة زيرلر في يناير 1960 وفي وقت لاحق في ورقة بحثية في يونيو 1961. تم وصف فك تشفير جورنشتاين-زيرلر والعمل المرتبط به على رموز بي سي إتش في كتاب رموز تصحيح الأخطاء بقلم و. ويزلي بيترسون (1961).

التركيبة

الرسالة المرسلة $(c_{0},\ldots ,c_{i},\ldots ,c_{n-1})$، يُنظر إليها على أنها معاملات متعددة الحدود $$s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}.$$

نتيجة لإجراء ترميز ريد–سولومون، فإن s (x) قابلة للقسمة على متعددة الحدود المولدة $$g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),$$ حيث α هو عنصر بدائي.

نظرًا لأن s (x) مضاعف للمولد g (x)، فمن الطبيعي أن «يرث» كل جذوره: $$s(x){\bmod {(}}x-\alpha ^{j})=g(x){\bmod {(}}x-\alpha ^{j})=0.$$ لذلك، $$s(\alpha ^{j})=0,\ j=1,2,\ldots ,n-k.$$

يتم إتلاف الحدود المنقولة أثناء النقل بسبب خطأ الحدود $$e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}$$ لإنتاج الحدود المستلمة $$r(x)=s(x)+e(x).$$

سيكون المعامل e _i صفرًا إذا لم يكن هناك خطأ عند تلك القوة لـ x، وغير صفر إذا كان هناك خطأ. إذا كانت هناك أخطاء ν عند قوى مميزة i _k لـ x، إذن $$e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}.$$

الهدف من فك التشفير هو العثور على عدد الأخطاء (ν)، ومواضع الأخطاء (i _k)، وقيم الأخطاء في تلك المواضع (e _{i k}). ومن تلك القيم، يمكن حساب e (x) وطرحه من r (x) للحصول على الرسالة المرسلة في الأصل s (x).

فك تشفير المتلازمة

يبدأ فك التشفير بتقييم الحدود الواردة في النقاط $\alpha ^{1}\dots \alpha ^{n-k}$. نحن نطلق على نتائج هذا التقييم اسم «المتلازمات» S _j. يتم تعريفهم على أنهم $${\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})\\&=e(\alpha ^{j})\\&=\sum _{k=1}^{\nu }e_{i_{k}}{(\alpha ^{j})}^{i_{k}},\quad j=1,2,\ldots ,n-k.\end{aligned}}$$ لاحظ أن $s(\alpha ^{j})=0$ لأن $s(x)$ له جذور في $\alpha ^{j}$ كما هو موضح في القسم السابق.

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

محددات الأخطاء وقيم الأخطاء

من أجل الراحة، قم بتحديد مواقع الأخطاء X _k وقيم الأخطاء Y _k على النحو التالي $$X_{k}=\alpha ^{i_{k}},\quad Y_{k}=e_{i_{k}}.$$

ومن ثم يمكن كتابة المتلازمات من حيث مواقع الأخطاء وقيم الأخطاء هذه على النحو التالي: $$S_{j}=\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}.$$

هذا التعريف لقيم المتلازمة يعادل التعريف السابق منذ ${(\alpha ^{j})}^{i_{k}}=\alpha ^{j\cdot i_{k}}={(\alpha ^{i_{k}})}^{j}=X_{k}^{j}$.

تعطي المتلازمات نظامًا من معادلات n − k ≥ 2ν في مجهولين 2 ν، ولكن نظام المعادلات هذا غير خطي في X _k وليس له حل واضح. ومع ذلك، إذا كانت قيمة X _k معروفة (انظر أدناه)، فإن معادلات المتلازمة توفر نظامًا خطيًا من المعادلات $${\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &\ddots &\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots \\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}},$$ والتي يمكن حلها بسهولة لقيم خطأ Y _k.

وبالتالي، فإن المشكلة تكمن في إيجاد X_k، لأنه عندها ستكون المصفوفة الموجودة في أقصى اليسار معروفة، ويمكن ضرب كلا جانبي المعادلة في معكوسها، مما ينتج عنه Y_k.

في متغير هذه الخوارزمية حيث تكون مواقع الأخطاء معروفة بالفعل (عندما يتم استخدامها كرمز مسح ‏)، فهذه هي النهاية. إن مواقع الخطأ (X _k) معروفة بالفعل من خلال بعض الطرق الأخرى (على سبيل المثال، في إرسال FM، يمكن تحديد الأقسام التي كان فيها تدفق البتات غير واضح أو تم التغلب عليه بالتداخل بشكل احتمالي من تحليل التردد). في هذا السيناريو، ما يصل إلى $n-k$ يمكن تصحيح الأخطاء.

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

متعدد الحدود لتحديد الخطأ

هناك علاقة تكرار خطية تُنتج نظامًا من المعادلات الخطية. حل هذه المعادلات يُحدد مواقع الخطأ X_k.

قم بتعريف متعددة حدود تحديد الخطأ Λ(x) على أنها $$\Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }.$$

أصفار Λ(x) هي مقلوبات $X_{k}^{-1}$. يتبع هذا من بناء تدوين المنتج أعلاه، لأنه إذا $x=X_{k}^{-1}$، ثم يصبح أحد الحدود المضروبة صفرًا، $(1-X_{k}^{-1}\cdot X_{k})=1-1=0$، مما يجعل تقييم متعدد الحدود بأكمله يساوي الصفر: $$\Lambda (X_{k}^{-1})=0.$$

يترك $j$ يكون أي عدد صحيح بحيث $1\leq j\leq \nu$. اضرب كلا الطرفين في $Y_{k}X_{k}^{j+\nu }$، وسيظل صفرًا: $${\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0,\\&Y_{k}X_{k}^{j+\nu }(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu })=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0.\end{aligned}}$$

المجموع لـ k = 1 إلى ν، وسيظل صفرًا: $$\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j})=0.$$

اجمع كل مصطلح في مجموع خاص به: $$\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\left(\sum _{k=1}^{\nu }\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}\right)+\left(\sum _{k=1}^{\nu }\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\left(\sum _{k=1}^{\nu }\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0.$$

استخرج القيم الثابتة لـ $\Lambda$ التي لا تتأثر بالمجموع: $$\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -1}\right)+\Lambda _{2}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0.$$

أصبحت هذه المجاميع الآن تعادل قيم المتلازمة، والتي نعرفها ويمكننا استبدالها. وهذا يقلل بالتالي إلى $$S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0.$$

الطرح $S_{j+\nu }$ من كلا الجانبين العائدات $$S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }.$$

تذكر أن j تم اختياره ليكون أي عدد صحيح بين 1 و v شاملًا، وهذا التكافؤ صحيح لجميع هذه القيم. وبالتالي، لدينا معادلة خطية، وليس معادلة واحدة فقط. وبالتالي، يمكن حل نظام المعادلات الخطية هذا لمعاملات Λ _i لمتعددة حدود موقع الخطأ: $${\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &\ddots &\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}.$$ يفترض ما سبق أن فك التشفير يعرف عدد الأخطاء ν، ولكن هذا العدد لم يتم تحديده بعد. لا يقوم فك التشفير PGZ بتحديد ν بشكل مباشر، بل يبحث عنه عن طريق تجربة القيم المتعاقبة. يفترض فك التشفير أولاً أكبر قيمة للتجربة ν ويقوم بإعداد النظام الخطي لتلك القيمة. إذا كان من الممكن حل المعادلات (أي أن محدد المصفوفة ليس صفرًا)، فإن قيمة التجربة هي عدد الأخطاء. إذا لم يكن من الممكن حل النظام الخطي، يتم تقليل التجربة ν بمقدار واحد ويتم فحص النظام الأصغر التالي.

إيجاد جذور متعددة حدود تحديد الخطأ

استخدم المعاملات Λ _التي وجدتها في الخطوة الأخيرة لبناء متعدد حدود موقع الخطأ. يمكن العثور على جذور متعددة الحدود الخاصة بموقع الخطأ من خلال البحث الشامل. محددات الخطأ X _k هي مقلوبات تلك الجذور. يمكن عكس ترتيب معاملات كثيرة الحدود لموقع الخطأ، وفي هذه الحالة تكون جذور كثيرة الحدود المعكوسة هي محددات الخطأ $X_{k}$ (ليس متبادلهما $X_{k}^{-1}$). يعد البحث شين ‏ تنفيذًا فعالًا لهذه الخطوة.

حساب قيم الخطأ

بمجرد معرفة مواقع الخطأ X _k، يمكن تحديد قيم الخطأ. يمكن القيام بذلك عن طريق الحل المباشر لـ Y _k في مصفوفة معادلات الخطأ المذكورة أعلاه، أو باستخدام خوارزمية فورني ‏.

حساب مواقع الخطأ

احسب i _k عن طريق أخذ قاعدة اللوغاريتم $\alpha$ من X _ك. يتم ذلك عادةً باستخدام جدول بحث محسوب مسبقًا.

إصلاح الأخطاء

أخيرًا، يتم إنشاء e (x) من i _k و e _{i k} ثم يتم طرحه من r (x) للحصول على الرسالة المرسلة في الأصل s (x)، مع تصحيح الأخطاء.

الأمثلة

خذ بعين الاعتبار رمز ريد–سولومون المحدد في GF(929) مع α = 3 و t = 4 (يستخدم هذا في رموز بي دي إف 417 ‏) لكود آر إس (7,3). الحدود المولدة هي $$g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522.$$ إذا كانت متعددة حدود الرسالة هي p(x) = 3 x² + 2 x + 1، فسيتم ترميز كلمة رمزية منهجية على النحو التالي: $$s_{r}(x)=p(x)\,x^{t}{\bmod {g}}(x)=547x^{3}+738x^{2}+442x+455,$$$$s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474.$$ قد تؤدي الأخطاء في الإرسال إلى استلام هذا بدلاً من ذلك: $$r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474.$$ يتم حساب المتلازمات عن طريق تقييم r عند قوى α : $$S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732,$$$$S_{2}=r(3^{2})=637,\quad S_{3}=r(3^{3})=762,\quad S_{4}=r(3^{4})=925,$$ إنتاج النظام $${\begin{bmatrix}732&637\\637&762\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-762\\-925\end{bmatrix}}={\begin{bmatrix}167\\004\end{bmatrix}}.$$

باستخدام الإزالة الغاوسية، $${\begin{bmatrix}001&000\\000&001\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}329\\821\end{bmatrix}},$$ لذا $$\Lambda (x)=329x^{2}+821x+001,$$ مع الجذور x ₁ = 757 = 3 ⁻³ و x ₂ = 562 = 3 ⁻⁴. يمكن عكس المعاملات: $$R(x)=001x^{2}+821x+329,$$ لإنتاج الجذور 27 = 3 ³ و 81 = 3 ⁴ مع أسس موجبة، ولكن عادةً لا يتم استخدام ذلك. يتوافق لوغاريتم الجذور المقلوبة مع مواقع الخطأ (من اليمين إلى اليسار، الموقع 0 هو المصطلح الأخير في الكلمة الرمزية).

لحساب قيم الخطأ، قم بتطبيق خوارزمية فورني ‏ : $$\Omega (x)=S(x)\Lambda (x){\bmod {x}}^{4}=546x+732,$$$$\Lambda '(x)=658x+821,$$$$e_{1}=-\Omega (x_{1})/\Lambda '(x_{1})=074,$$$$e_{2}=-\Omega (x_{2})/\Lambda '(x_{2})=122.$$

الطرح $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ من متعددة الحدود المستلمة r (x) تعيد إنتاج كلمة المرور الأصلية s.

فك تشفير بيرليكامب-ماسي

خوارزمية بيرليكامب-ماسي ‏ هي إجراء تكراري بديل للعثور على متعدد الحدود لتحديد الخطأ. أثناء كل تكرار، يقوم بحساب التناقض بناءً على حالة حالية من Λ(x) مع عدد مفترض من الأخطاء e : $$\Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}$$ ثم يقوم بتعديل Λ(x) و e بحيث يصبح Δ المعاد حسابه صفرًا. تحتوي المقالة «خوارزمية بيرليكامب-ماسي ‏» على وصف تفصيلي للإجراء. في المثال التالي، يتم استخدام C (x) لتمثيل Λ(x).

الأمثلة

باستخدام نفس البيانات المستخدمة في مثال بيترسون جورنشتاين زيرلر أعلاه:

ن	إسإن +1	د	ج	ب	ب	م
0	732	732	197 x + 1	1	732	1
1	637	846	173 x + 1	1	732	2
2	762	412	634 x2 + 173 x + 1	173 x + 1	412	1
3	925	576	329 x2 + 821 x + 1	173 x + 1	412	2

القيمة النهائية لـ C هي متعددة حدود تحديد الخطأ، Λ(x).

فك تشفير سوجياما

تعتمد طريقة تكرارية أخرى لحساب كل من متعدد حدود تحديد الخطأ ومتعدد حدود قيمة الخطأ على تكييف سوجياما لخوارزمية إقليدية ممتدة.

عرف S (x)، Λ(x)، وΩ(x) لمتلازمات t وأخطاء e : $${\begin{aligned}S(x)&=S_{t}x^{t-1}+S_{t-1}x^{t-2}+\cdots +S_{2}x+S_{1}\\[1ex]\Lambda (x)&=\Lambda _{e}x^{e}+\Lambda _{e-1}x^{e-1}+\cdots +\Lambda _{1}x+1\\[1ex]\Omega (x)&=\Omega _{e}x^{e}+\Omega _{e-1}x^{e-1}+\cdots +\Omega _{1}x+\Omega _{0}\end{aligned}}$$

المعادلة الأساسية هي: $$\Lambda (x)S(x)=Q(x)x^{t}+\Omega (x)$$

بالنسبة إلى t = 6 و e = 3: $${\begin{bmatrix}\Lambda _{3}S_{6}&x^{8}\\\Lambda _{2}S_{6}+\Lambda _{3}S_{5}&x^{7}\\\Lambda _{1}S_{6}+\Lambda _{2}S_{5}+\Lambda _{3}S_{4}&x^{6}\\S_{6}+\Lambda _{1}S_{5}+\Lambda _{2}S_{4}+\Lambda _{3}S_{3}&x^{5}\\S_{5}+\Lambda _{1}S_{4}+\Lambda _{2}S_{3}+\Lambda _{3}S_{2}&x^{4}\\S_{4}+\Lambda _{1}S_{3}+\Lambda _{2}S_{2}+\Lambda _{3}S_{1}&x^{3}\\S_{3}+\Lambda _{1}S_{2}+\Lambda _{2}S_{1}&x^{2}\\S_{2}+\Lambda _{1}S_{1}&x\\S_{1}\end{bmatrix}}={\begin{bmatrix}Q_{2}x^{8}\\Q_{1}x^{7}\\Q_{0}x^{6}\\0\\0\\0\\\Omega _{2}x^{2}\\\Omega _{1}x\\\Omega _{0}\end{bmatrix}}$$

الحدود الوسطى هي صفر بسبب العلاقة بين Λ والمتلازمات.

يمكن لخوارزمية إقليدية ممتدة العثور على سلسلة من كثيرات الحدود من النموذج

A_i(x) S(x) + B_i(x) x^t = R_i(x)

حيث تقل درجة R مع زيادة i. بمجرد أن تصبح درجة R _i (x) < t /2، فإن

A_i(x) = Λ(x)

B_i(x) = −Q(x)

R_i(x) = Ω(x).

لا يلزم حفظ B (x) و Q (x)، لذا تصبح الخوارزمية:

R−1 := xt
R0  := S(x)
A−1 := 0
A0  := 1
i := 0
while degree of Ri ≥ t/2
  i := i + 1
  Q := Ri-2 / Ri-1
  Ri := Ri-2 - Q Ri-1
  Ai := Ai-2 - Q Ai-1

لتعيين الحد الأدنى من الترتيب لـ Λ(x) إلى 1، قسّم Λ(x) وΩ(x) على A _i (0):

Λ(x) = A_i / A_i(0)

Ω(x) = R_i / A_i(0)

A _i (0) هو الحد الثابت (من الدرجة المنخفضة) لـ A _i.

الأمثلة

باستخدام نفس البيانات المستخدمة في مثال بيترسون-جورينشتاين-زيرلر أعلاه:

آي	آر اي	إيه i
−1	001 x4 + 000 x3 + 000 x2 + 000 x + 000	000
0	925 x3 + 762 x2 + 637 x + 732	001
1	683 x2 + 676 x + 024	697 x + 396
2	673 x + 596	608 x2 + 704 x + 544

Λ(x) = A₂ / 544 = 329 x² + 821 x + 001

Ω(x) = R₂ / 544 = 546 x + 732

فك التشفير باستخدام تحويل فورييه المنفصل

يمكن استخدام تحويل فورييه المنفصل لفك التشفير. لتجنب التعارض مع أسماء المتلازمات، دع c (x) = s (x) هي الكلمة المشفرة. r (x) و e (x) هما نفس الشيء المذكور أعلاه. عرف C (x)، و E (x)، و R (x) على أنها تحويلات فورييه المنفصلة لـ c (x)، و e (x)، و r (x). نظرًا لأن r (x) = c (x) + e (x)، ونظرًا لأن تحويل فورييه المنفصل هو عامل خطي، فإن R (x) = C (x) + E (x).

قم بتحويل r (x) إلى R (x) باستخدام تحويل فورييه المنفصل. نظرًا لأن حساب تحويل فورييه المنفصل هو نفس حساب المتلازمات، فإن معاملات t لـ R (x) و E (x) هي نفس المتلازمات: $$R_{j}=E_{j}=S_{j}=r(\alpha ^{j})\qquad {\text{for }}1\leq j\leq t$$

يستخدم $R_{1}$ خلال $R_{t}$ كمتلازمات (إنها نفس الشيء) وتوليد متعدد الحدود لتحديد الخطأ باستخدام الأساليب من أي من أجهزة فك التشفير المذكورة أعلاه.

ليكن v = عدد الأخطاء. توليد E (x) باستخدام المعاملات المعروفة $E_{1}$ ل $E_{t}$، متعدد الحدود لتحديد الخطأ، وهذه الصيغ $${\begin{aligned}E_{0}&=-{\frac {1}{\Lambda _{v}}}(E_{v}+\Lambda _{1}E_{v-1}+\cdots +\Lambda _{v-1}E_{1})\\E_{j}&=-(\Lambda _{1}E_{j-1}+\Lambda _{2}E_{j-2}+\cdots +\Lambda _{v}E_{j-v})&{\text{for }}t<j<n\end{aligned}}$$

ثم احسب C (x) = R (x) − E (x) واستخدم التحويل العكسي (الاستيفاء متعدد الحدود) لـ C (x) لإنتاج c (x).

فك التشفير خارج حدود تصحيح الخطأ

تنص حدود سينجلتون ‏ على أن الحد الأدنى للمسافة d لكتلة رمزية خطية بحجم (n، k) يحدها الحد العلوي n - k + 1. كان من المفهوم عادةً أن المسافة d تحد من قدرة تصحيح الخطأ إلى ⌊(d - 1) / 2⌋. يحقق كود ريد–سولومون هذا الحد بالمساواة، وبالتالي يمكنه تصحيح ما يصل إلى ⌊(n - k) / 2⌋ أخطاء. ومع ذلك، فإن حد تصحيح الخطأ هذا ليس دقيقًا.

في عام 1999، نشر مادو سودان وفينكاتيسان جوروسوامي ‏ في معهد ماساتشوستس للتكنولوجيا «تحسين فك رموز ريد–سولومون والرموز الجبرية الهندسية» حيث قدموا خوارزمية سمحت بتصحيح الأخطاء التي تتجاوز نصف المسافة الدنيا للرمز. وهذا ينطبق على رموز ريد–سولومون وبشكل عام على الرموز الهندسية الجبرية. تنتج هذه الخوارزمية قائمة من الكلمات المشفرة (وهي خوارزمية فك تشفير القائمة) وتعتمد على الاستيفاء والتحليل إلى عوامل متعددة الحدود على GF(2^m) وامتداداتها.

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

فك التشفير الناعم

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

مثال ماتلاب

مُشفِّر

نقدم هنا تنفيذ ماتلاب بسيطًا للمُشفِّر.

function encoded = rsEncoder(msg, m, prim_poly, n, k)
    % RSENCODER Encode message with the Reed-Solomon algorithm
    % m is the number of bits per symbol
    % prim_poly: Primitive polynomial p(x). Ie for DM is 301
    % k is the size of the message
    % n is the total size (k+redundant)
    % Example: msg = uint8('Test')
    % enc_msg = rsEncoder(msg, 8, 301, 12, numel(msg));

    % Get the alpha
    alpha = gf(2, m, prim_poly);

    % Get the Reed-Solomon generating polynomial g(x)
    g_x = genpoly(k, n, alpha);

    % Multiply the information by X^(n-k), or just pad with zeros at the end to
    % get space to add the redundant information
    msg_padded = gf([msg zeros(1, n - k)], m, prim_poly);

    % Get the remainder of the division of the extended message by the
    % Reed-Solomon generating polynomial g(x)
    [~, remainder] = deconv(msg_padded, g_x);

    % Now return the message with the redundant information
    encoded = msg_padded - remainder;

end

% Find the Reed-Solomon generating polynomial g(x), by the way this is the
% same as the rsgenpoly function on matlab
function g = genpoly(k, n, alpha)
    g = 1;
    % A multiplication on the galois field is just a convolution
    for k = mod(1 : n - k, n)
        g = conv(g, [1 alpha .^ (k)]);
    end
end

فك التشفير

الآن الجزء المتعلق بفك التشفير:

function [decoded, error_pos, error_mag, g, S] = rsDecoder(encoded, m, prim_poly, n, k)
    % RSDECODER Decode a Reed-Solomon encoded message
    %   Example:
    % [dec, ~, ~, ~, ~] = rsDecoder(enc_msg, 8, 301, 12, numel(msg))
    max_errors = floor((n - k) / 2);
    orig_vals = encoded.x;
    % Initialize the error vector
    errors = zeros(1, n);
    g = []؛
    S = []؛

    % Get the alpha
    alpha = gf(2, m, prim_poly);

    % Find the syndromes (Check if dividing the message by the generator
    % polynomial the result is zero)
    Synd = polyval(encoded, alpha .^ (1:n - k));
    Syndromes = trim(Synd);

    % If all syndromes are zeros (perfectly divisible) there are no errors
    if isempty(Syndromes.x)
        decoded = orig_vals(1:k);
        error_pos = []؛
        error_mag = []؛
        g = []؛
        S = Synd;
        return;
    end

    % Prepare for the euclidean algorithm (Used to find the error locating
    % polynomials)
    r0 = [1, zeros(1, 2 * max_errors)]؛ r0 = gf(r0, m, prim_poly); r0 = trim(r0);
    size_r0 = length(r0);
    r1 = Syndromes;
    f0 = gf([zeros(1, size_r0 - 1) 1], m, prim_poly);
    f1 = gf(zeros(1, size_r0), m, prim_poly);
    g0 = f1; g1 = f0;

    % Do the euclidean algorithm on the polynomials r0(x) and Syndromes(x) in
    % order to find the error locating polynomial
    while true
        % Do a long division
        [quotient, remainder] = deconv(r0, r1);
        % Add some zeros
        quotient = pad(quotient, length(g1));

        % Find quotient*g1 and pad
        c = conv(quotient, g1);
        c = trim(c);
        c = pad(c, length(g0));

        % Update g as g0-quotient*g1
        g = g0 - c;

        % Check if the degree of remainder(x) is less than max_errors
        if all(remainder(1:end - max_errors) == 0)
            break;
        end

        % Update r0, r1, g0, g1 and remove leading zeros
        r0 = trim(r1); r1 = trim(remainder);
        g0 = g1; g1 = g;
    end

    % Remove leading zeros
    g = trim(g);

    % Find the zeros of the error polynomial on this galois field
    evalPoly = polyval(g, alpha .^ (n - 1 : - 1 : 0));
    error_pos = gf(find(evalPoly == 0), m);

    % If no error position is found we return the received work, because
    % basically is nothing that we could do and we return the received message
    if isempty(error_pos)
        decoded = orig_vals(1:k);
        error_mag = []؛
        return;
    end

    % Prepare a linear system to solve the error polynomial and find the error
    % magnitudes
    size_error = length(error_pos);
    Syndrome_Vals = Syndromes.x;
    b(:, 1) = Syndrome_Vals(1:size_error);
    for idx = 1 : size_error
        e = alpha .^ (idx * (n - error_pos.x));
        err = e.x;
        er(idx, :) = err;
    end

    % Solve the linear system
    error_mag = (gf(er, m, prim_poly) \ gf(b, m, prim_poly))';
    % Put the error magnitude on the error vector
    errors(error_pos.x) = error_mag.x;
    % Bring this vector to the galois field
    errors_gf = gf(errors, m, prim_poly);

    % Now to fix the errors just add with the encoded code
    decoded_gf = encoded(1:k) + errors_gf(1:k);
    decoded = decoded_gf.x;

end

% Remove leading zeros from Galois array
function gt = trim(g)
    gx = g.x;
    gt = gf(gx(find(gx, 1) : end), g.m, g.prim_poly);
end

% Add leading zeros
function xpad = pad(x, k)
    len = length(x);
    if len < k
        xpad = [zeros(1, k - len) x]؛
    end
end

فك تشفير العرض الأصلي لريد سولومون

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

فك التشفير النظري

وصف ريد وسولومون فك تشفير نظري يصحح الأخطاء من خلال العثور على متعدد الحدود للرسالة الأكثر شيوعًا. لا يعرف المُفكك سوى مجموعة القيم $a_{1}$ ل $a_{n}$ وأي طريقة ترميز تم استخدامها لتوليد تسلسل قيم الكلمة الرمزية. الرسالة الأصلية، والمتعددة الحدود، وأي أخطاء غير معروفة. يمكن لإجراء فك التشفير استخدام طريقة مثل استيفاء لاغرانج على مجموعات فرعية مختلفة من قيم كلمة المرور n المأخوذة k في كل مرة لإنتاج كثيرات الحدود المحتملة بشكل متكرر، حتى يتم إنتاج عدد كافٍ من كثيرات الحدود المطابقة للقضاء بشكل معقول على أي أخطاء في كلمة المرور المستلمة. بمجرد تحديد كثير الحدود، يمكن تصحيح أي أخطاء في كلمة الرمز، عن طريق إعادة حساب قيم كلمة الرمز المقابلة. لسوء الحظ، في جميع الحالات، باستثناء أبسطها، هناك عدد كبير جدًا من المجموعات الفرعية، وبالتالي فإن الخوارزمية غير عملية. عدد المجموعات الفرعية هو المعامل الثنائي، ${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$، وعدد المجموعات الفرعية غير ممكن حتى بالنسبة للرموز المتواضعة. بالنسبة لكود (255,249) الذي يمكنه تصحيح 3 أخطاء، فإن فك التشفير النظري الساذج سوف يفحص 359 مليار مجموعة فرعية.

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

في عام 1986، تم تطوير فك تشفير معروف باسم خوارزمية بيرليكامب-ويلش كفك ‏ تشفير قادر على استعادة متعددة الحدود الأصلية للرسالة بالإضافة إلى متعددة حدود «محدد» الخطأ التي تنتج أصفارًا لقيم الإدخال التي تتوافق مع الأخطاء، مع تعقيد زمني O(n³)، حيث n هو عدد القيم في الرسالة. يتم بعد ذلك استخدام الحدود المستردة لاستعادة (إعادة الحساب حسب الحاجة) الرسالة الأصلية.

الأمثلة

باستخدام آر إس (7,3)، وجي إف (929)، ومجموعة نقاط التقييم a_i = i − 1

a = {0, 1, 2, 3, 4, 5, 6}

إذا كانت الرسالة متعددة الحدود هي

p(x) = 003x² + 002x + 001

كلمة المرور هي

c = {001, 006, 017, 034, 057, 086, 121}

قد يؤدي حدوث أخطاء في الإرسال إلى استلام هذا بدلاً من ذلك.

b = c + e = {001, 006, 123, 456, 057, 086, 121}

المعادلة الأساسية هي:

b_iE(a_i) - Q(a_i) = 0

افترض الحد الأقصى لعدد الأخطاء: e = 2. المعادلة الأساسية تصبح:

b_i(e₀ + e₁a_i) - (q₀ + q₁a_i + q₂ a²
_i + q₃a³
_i + q₄a⁴
_i) = - b_ia²
_i

$${\begin{bmatrix}001&000&928&000&000&000&000\\006&006&928&928&928&928&928\\123&246&928&927&925&921&913\\456&439&928&926&920&902&848\\057&228&928&925&913&865&673\\086&430&928&924&904&804&304\\121&726&928&923&893&713&562\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}000\\923\\437\\541\\017\\637\\289\end{bmatrix}}$$

استخدام الإزالة الغاوسية :

$${\begin{bmatrix}001&000&000&000&000&000&000\\000&001&000&000&000&000&000\\000&000&001&000&000&000&000\\000&000&000&001&000&000&000\\000&000&000&000&001&000&000\\000&000&000&000&000&001&000\\000&000&000&000&000&000&001\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}006\\924\\006\\007\\009\\916\\003\end{bmatrix}}$$

Q(x) = 003x⁴ + 916x³ + 009x² + 007x + 006

E(x) = 001x² + 924x + 006

Q(x)/E(x) = P(x) = 003x² + 002x + 001

Recalculate P(x) where E(x) = 0 : {2, 3}

 to correct b resulting in the corrected codeword:

c = {001, 006, 017, 034, 057, 086, 121}

}}

فك تشفير جاو

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

الأمثلة

• $R_{-1}=\prod _{i=1}^{n}(x-a_{i})$
• $R_{0}=$ استيفاء لاغرانج لـ $(a_{i},b(a_{i}))$ ل $i=1$ ل $n$
• $A_{-1}=0$
• $A_{0}=1$
• يولد $R_{i}$ و $A_{i}$ حتى درجة $R_{i}<(n+k)/2$، على سبيل المثال $(n+k)/2=(7+3)/2=5$

آي	آر i	إيه i
−1	001x7 + 908x6 + 175x5 + 194x4 + 695x3 + 094x2 + 720x + 000	000
0	055x6 + 440x5 + 497x4 + 904x3 + 424x2 + 472x + 001	001
1	702x5 + 845x4 + 691x3 + 461x2 + 327x + 237	152 x + 237
2	266x4 + 086x3 + 798x2 + 311x + 532	708x2 + 176x + 532

Q(x) = R₂ = 266x⁴ + 086x³ + 798x² + 311x + 532

E(x) = A₂ = 708x² + 176x + 532

لمضاعفة كثيرات الحدود التي أنشأها ويلش بيرليكامب، قسّم Q (x) و E (x) على المعامل الأكثر أهمية لـ E (x) = 708.

Q(x) = 003x⁴ + 916x³ + 009x² + 007x + 006

E(x) = 001x² + 924x + 006

Q(x)/E(x) = P(x) = 003x² + 002x + 001

Recalculate P(x) where E(x) = 0 : {2, 3}

 to correct b resulting in the corrected codeword:

c = {001, 006, 017, 034, 057, 086, 121}

انظر أيضًا

• رمز بي سي إتش

وصلات خارجية

المعلومات والدروس التعليمية

• Welch، L. R. (1997)، The Original View of Reed–Solomon Codes (PDF)، Lecture Notes، مؤرشف من الأصل (PDF) في 2016-03-03
• Koetter، Ralf (2005)، Reed–Solomon Codes، MIT Lecture Notes 6.451 (Video)، مؤرشف من الأصل في 2013-03-13

• Introduction to ريد–سولومون codes: principles, architecture and implementation (CMU)
• Geisel، William A. (أغسطس 1990)، Tutorial on Reed–Solomon Error Correction Coding، Technical Memorandum، ناسا، TM-102162، مؤرشف من الأصل في 2024-11-16
• Reid، Jeff A. (أبريل 1995)، CRC and Reed Solomon ECC (PDF)، مؤرشف من الأصل (PDF) في 2025-01-14

التنفيذات

• FEC library in C by Phil Karn (aka KA9Q) includes Reed–Solomon codec, both arbitrary and optimized (223,255) version
• Open Source C++ Reed–Solomon Soft Decoding library
• Matlab implementation of errors and-erasures Reed–Solomon decoding