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

في نظرية المعلومات ونظرية الترميز ، تعتبر رموز ريد-سولومون مجموعة من رموز تصحيح الأخطاء التي قدمها إيرفينغ إس. ريد وغوستاف سولومون في عام 1960. ^{[ 1 ]} ولها العديد من التطبيقات، بما في ذلك التقنيات الاستهلاكية مثل MiniDiscs و CDs و DVDs وأقراص Blu-ray ورموز QR و Data Matrix وتقنيات نقل البيانات مثل DSL و WiMAX وأنظمة البث مثل الاتصالات عبر الأقمار الصناعية و DVB و ATSC وأنظمة التخزين مثل RAID 6 .

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

يوجد في هذه المقالة نظامان مختلفان لترميز ريد-سولومون، يُطلق عليهما العرض الأصلي وعرض BCH. ويشرح قسم التاريخ أصول هذا النظام.

تاريخ

طُوِّرت رموز ريد-سولومون عام 1960 على يد إيرفينغ إس. ريد وغوستاف سولومون ، اللذين كانا آنذاك عضوين في مختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا . وكانت مقالتهما الرائدة بعنوان "الرموز متعددة الحدود على حقول منتهية معينة". ^{[ 1 ]} استخدم نظام التشفير الأصلي الموصوف في مقالة ريد وسولومون متعددة حدود متغيرة تعتمد على الرسالة المراد تشفيرها، حيث لا يعرف المُشفِّر والمُفكِّك سوى مجموعة ثابتة من القيم (نقاط التقييم) المراد تشفيرها. وقد قام المُفكِّك النظري الأصلي بتوليد متعددات حدود محتملة بناءً على مجموعات فرعية من k (طول الرسالة غير المشفرة) من أصل n (طول الرسالة المشفرة) قيمة للرسالة المُستلمة، ثم يختار متعددة الحدود الأكثر شيوعًا باعتبارها الصحيحة، وهو ما كان غير عملي إلا في أبسط الحالات. تم حل هذه المشكلة مبدئيًا بتغيير المخطط الأصلي إلى مخطط متوافق مع ترميز BCH يعتمد على دالة متعددة الحدود ثابتة معروفة لكل من المُشفِّر والمُفكِّك، ولكن لاحقًا، طُوِّرت مُفكِّكات عملية تعتمد على المخطط الأصلي، على الرغم من أنها كانت أبطأ في البداية من مخططات BCH. ونتيجةً لذلك، يوجد نوعان رئيسيان من رموز ريد-سولومون: تلك التي تستخدم مخطط التشفير الأصلي وتلك التي تستخدم مخطط تشفير BCH.

في عام 1960 أيضًا، وُصف مُفكِّك شفرة عملي ذو متعدد حدود ثابت لرموز BCH ، طوّره دانيال غورنشتاين ونيل زيرلر، في تقرير لمختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا، نُشر في يناير 1960، ثم في مقال نُشر لاحقًا في يونيو 1961. ^{[ 2 ]} وتم وصف مُفكِّك شفرة غورنشتاين-زيرلر والأعمال ذات الصلة برموز BCH في كتاب "رموز تصحيح الأخطاء" للمؤلف دبليو ويسلي بيترسون (1961). ^{[ 3 ]} وبحلول عام 1963 (أو ربما قبل ذلك)، أدرك جيه جيه ستون (وآخرون) أن رموز ريد-سولومون يُمكنها استخدام مخطط BCH باستخدام متعدد حدود مولد ثابت، مما يجعل هذه الرموز فئة خاصة من رموز BCH، ^[⁴^] لكن رموز ريد-سولومون القائمة على مخطط التشفير الأصلي لا تُصنَّف ضمن فئة رموز BCH، واعتمادًا على مجموعة نقاط التقييم، فهي ليست حتى رموزًا دورية .

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

في عام 1975، قام ياسوو سوجياما بتطوير جهاز فك تشفير BCH محسّن آخر، استنادًا إلى خوارزمية إقليدس الموسعة . ^{[ 5 ]}

في عام 1977، طُبقت رموز ريد-سولومون في برنامج فوياجر على شكل رموز تصحيح أخطاء متسلسلة . ظهر أول تطبيق تجاري لها في المنتجات الاستهلاكية واسعة الانتشار عام 1982 مع القرص المضغوط ، حيث استُخدم رمزان متداخلان من رموز ريد-سولومون. اليوم، تُستخدم رموز ريد-سولومون على نطاق واسع في أجهزة التخزين الرقمية ومعايير الاتصالات الرقمية ، على الرغم من أنها تُستبدل تدريجيًا برموز بوز-تشودري-هوكينغهام (BCH) . على سبيل المثال، تُستخدم رموز ريد-سولومون في معيار البث الرقمي للفيديو (DVB) DVB-S ، بالاقتران مع رمز داخلي التفافي ، بينما تُستخدم رموز BCH مع LDPC في المعيار اللاحق DVB-S2 .

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

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

في عام 2002، تم تطوير مخطط فك تشفير أصلي آخر بواسطة شوهونغ غاو، استنادًا إلى خوارزمية إقليدس الموسعة . ^{[ 6 ]}

في حوالي عام 2015، تم تطوير نظام فك تشفير أصلي يشبه نظام فك التشفير (المؤلف غير معروف). ^{[ 7 ]}

التطبيقات

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

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

يُعدّ ترميز ريد-سولومون عنصرًا أساسيًا في القرص المضغوط . وكان أول استخدام لترميز تصحيح الأخطاء القوي في منتج استهلاكي واسع الانتشار، وتستخدم أشرطة DAT وأقراص DVD أنظمة مشابهة. في القرص المضغوط، ينتج عن طبقتين من ترميز ريد-سولومون، يفصل بينهما مُشَكِّل تداخلي تلافيفي ذو 28 اتجاهًا ، نظام يُسمى ترميز ريد-سولومون المتداخل المتقاطع ( CIRC ). العنصر الأول في مُفكِّك ترميز CIRC هو رمز ريد-سولومون داخلي ضعيف نسبيًا (32، 28)، مُختصر من رمز (255، 251) برموز 8 بت. يستطيع هذا الرمز تصحيح ما يصل إلى خطأين في كل كتلة 32 بايت. والأهم من ذلك، أنه يُشير إلى أي كتل غير قابلة للتصحيح، أي الكتل التي تحتوي على أكثر من خطأين في البايت، على أنها عمليات مسح. تقوم وحدة فك التشفير بتوزيع الكتل المكونة من 28 بايت، والتي تحمل مؤشرات المسح، على كتل مختلفة من الشفرة الخارجية (28، 24). وبفضل هذه العملية، تتحول كتلة الـ 28 بايت المسحوبة من الشفرة الداخلية إلى بايت واحد مسحوب في كل كتلة من كتل الشفرة الخارجية البالغ عددها 28 كتلة. وتصحح الشفرة الخارجية هذا الخطأ بسهولة، إذ يمكنها التعامل مع ما يصل إلى 4 عمليات مسح من هذا النوع لكل كتلة.

والنتيجة هي نظام CIRC قادر على تصحيح أخطاء متقطعة تصل إلى 4000 بت، أو ما يعادل 2.5 مم تقريبًا على سطح القرص. يتميز هذا النظام بقوة فائقة تجعل معظم أخطاء تشغيل الأقراص المدمجة ناتجة بشكل شبه مؤكد عن أخطاء في التتبع تتسبب في قفز الليزر عن المسار، وليس عن أخطاء متقطعة غير قابلة للتصحيح. ^{[ 8 ]}

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

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

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

تستخدم معظم الرموز الشريطية ثنائية الأبعاد، مثل PDF-417 و MaxiCode و Datamatrix و QR Code و Aztec Code و Han Xin code ، تقنية تصحيح الأخطاء ريد-سولومون لضمان قراءتها بشكل صحيح حتى في حال تلف جزء منها. وعندما يعجز الماسح الضوئي عن التعرف على رمز شريطي، فإنه يعتبره تالفًا.

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

نقل البيانات

يمكن استخدام أشكال متخصصة من رموز ريد-سولومون، وتحديدًا كوشي- RS وفانديرموند- RS، للتغلب على عدم موثوقية نقل البيانات عبر قنوات المحو . تفترض عملية التشفير رمز RS( N , K ) ينتج عنه N كلمة رمزية بطول N رمز، تخزن كل منها K رمزًا من البيانات، ثم تُرسل عبر قناة محو.

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

تُستخدم رموز ريد-سولومون أيضًا في أنظمة xDSL ومواصفات بروتوكول اتصالات الفضاء CCSDS كشكل من أشكال تصحيح الأخطاء الأمامية .

نقل البيانات عبر الفضاء

نظام ترميز متسلسل للفضاء العميق. ^{[ 9 ]} الترميز: RS(255, 223) + CC ("طول القيد" = 7، معدل الترميز = 1/2).

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

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

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

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

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

مخططات ترميز القنوات المستخدمة في مهمات ناسا ^{[ 10 ]}
سنين	شفرة	المهمة (المهام)
1958–حتى الآن	غير مشفر	مستكشف، بحار، وغيرهم الكثير
1968–1978	رموز الالتفاف (CC) (25، 1/2)	بايونير، فينوس
1969–1975	رمز ريد-مولر (32، 6)	بحار، فايكنغ
1977–حتى الآن	رمز غولاي الثنائي	فوياجر
1977–حتى الآن	RS(255, 223) + CC(7, 1/2)	فوياجر، جاليليو، وغيرهم الكثير
1989–2003	RS(255, 223) + CC(7, 1/3)	فوياجر
1989–2003	RS(255, 223) + CC(14, 1/4)	جاليليو
1996–حتى الآن	RS + CC (15, 1/6)	كاسيني، مارس باثفايندر، وغيرها
2004–حتى الآن	رموز التوربو ^{[ ملاحظة 1 ]}	ماسنجر، ستيريو، إم آر أو، إم إس إل، وغيرها
تأسست عام 2009	رموز LDPC	كوكبة، M2020، مافن

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

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

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

توجد إجراءات ترميز مختلفة لرمز ريد-سولومون، وبالتالي، توجد طرق مختلفة لوصف مجموعة جميع الكلمات المشفرة. في الرؤية الأصلية لريد وسولومون، كل كلمة مشفرة في رمز ريد-سولومون هي سلسلة من قيم دالة لكثير حدود من درجة أقل من $k$ [ ^{1 ]} للحصول على كلمة رمزية من شفرة ريد-سولومون، تُعامل رموز الرسالة (كل منها ضمن الأبجدية ذات الحجم 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 . وعلى الرغم من أن إجراء التشفير الأخير أقل كفاءة بعض الشيء، إلا أنه يتميز بأنه يُنتج رمزًا منهجيًا ، أي أن الرسالة الأصلية تُضمّن دائمًا كسلسلة فرعية من كلمة الرمز. ^{[ 1 ]}

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

في البناء الأصلي لريد وسليمان، الرسالة $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_{0}+m_{1}a+m_{2}a^{2}+\cdots +m_{k-1}a^{k-1}$ كلمة السر لـ $m$ يتم الحصول عليها من خلال تقييم $p_{m}$ في $n$ نقاط مختلفة $a_{0},\dots ,a_{n-1}$ في هذا المجال $F$ [ ^{1 ] وبالتالي فإن وظيفة} التشفير الكلاسيكية $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)=mA$ فيما يلي $k\times n$ -مصفوفة $A$ مع عناصر من $F$ .

$C(m)=mA={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &m_{k-1}\end{bmatrix}}{\begin{bmatrix}1&1&1&\dots &1\\a_{0}&a_{1}&a_{2}&\dots &a_{n-1}\\a_{0}^{2}&a_{1}^{2}&a_{2}^{2}&\dots &a_{n-1}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\a_{0}^{k-1}&a_{1}^{k-1}&a_{2}^{k-1}&\dots &a_{n-1}^{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، اضرب المصفوفة 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)=mG$ فيما يلي $k\times n$ -مصفوفة $G$ مع عناصر من $F$ . $C(m)=mG={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &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}}$

تحويل فورييه المنفصل ومعكوسه

يُعد تحويل فورييه المنفصل مماثلاً بشكل أساسي لإجراء التشفير؛ فهو يستخدم متعدد الحدود المولد $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}\}$

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

وجهة نظر BCH: الكلمة المشفرة كسلسلة من المعاملات

لاحظ أن كود BCH ومعظم تطبيقات عرض BCH تستخدم ترتيب الحدود الأكثر أهمية أولاً. في هذا العرض، تُفسَّر الرسالة على أنها معاملات متعددة الحدود. $m(x)$ :

$m(x)=m_{k-1}x^{k-1}+m_{k-2}x^{k-2}+\cdots +m_{1}x+m_{0}$

متعدد الحدود المولد $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)=x^{n-k}+g_{n-k-1}x^{n-k-1}+\cdots +g_{1}x+g_{0}$ بالنسبة لـ "رمز ذي معنى ضيق"، $i=1$ .

تحسب عملية التشفير متعددة الحدود للكلمة المشفرة $c(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots +c_{1}x+c_{0}$ هذا مضاعف دقيق لـ $g(x)$ .

إجراء ترميز بسيط

يقوم المرسل بحساب متعددة الحدود ذات الصلة $c(x)$ درجة علمية $n-1$ أين $n\leq q-1$ ويرسل متعددة الحدود $c(x)$ متعددة الحدود $c(x)$ يتم بناؤها عن طريق ضرب متعددة حدود الرسالة $m(x)$ ، والتي لها درجة $k-1$ ، مع متعدد الحدود المولد $g(x)$ درجة علمية $n-k$ هذا الأمر معروف لكل من المرسل والمستقبل. $c(x)=m(x)g(x)$ .

هذه الوظيفة $C$ هي دالة خطية ، أي أنها تحقق الشرط التالي: $C(m)=mA$ فيما يلي $k\times n$ -مصفوفة $A$ مع عناصر من $F$ .

$A={\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}$

$C(m)=mA$ فيما يلي $k\times n$ مصفوفة $G$ مع عناصر من $F$ .

$c(x)=mA={\begin{bmatrix}m_{k-1}&\cdots &m_{1}&m_{0}\end{bmatrix}}{\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}$

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

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

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

أما الباقي فلديه درجة علمية على الأكثر $t-1$ ، بينما معاملات $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ في كثير الحدود $c(x)\cdot x^{t}$ تساوي صفرًا. لذلك، فإن التعريف التالي للكلمة السرية $c(x)$ يمتلك الخاصية التي يتمتع بها الأول $k$ المعاملات متطابقة مع معاملات $c(x)$ : $c(x)=m(x)\cdot x^{t}-r(x)\,.$

نتيجة ل، $c(x)$ يقبل القسمة تمامًا على $g(x)$ [ ¹¹^]

$c(x)\equiv m(x)\cdot x^{t}-r(x)\equiv r(x)-r(x)\equiv 0\mod g(x)\,.$

هذه الوظيفة $C$ هي عملية ربط خطية. لإنشاء مصفوفة التشفير النظامية المقابلة G، اضرب المصفوفة A في معكوس المصفوفة الفرعية المربعة اليسرى لـ A (أو اجعل المصفوفة الفرعية المربعة اليسرى لـ G هي مصفوفة الوحدة وقم بتشفير كل صف).

$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)=mG$ فيما يلي $k\times n$ مصفوفة $G$ مع عناصر من $F$ .

$c(x)=mG={\begin{bmatrix}m_{k-1}&\ldots &m_{1}&m_{0}\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 , k )؛ ويُعرف هذا باسم حد سينغلتون . ويُطلق على هذا الرمز أيضًا اسم رمز الفصل ذي المسافة القصوى (MDS) .

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

يمكن وصف حد الخطأ النظري من خلال الصيغة التالية لقناة AWGN لـ FSK : ^{[ 12 ]} $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$ معدل خطأ الرمز في حالة AWGN غير المشفرة و $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$ لذا، فإن اختيار سلسلة من قوى الجذور الأولية كنقاط تقييم يجعل رمز ريد-سولومون الأصلي دوريًا . وتكون رموز ريد-سولومون في منظور BCH دورية دائمًا لأن رموز BCH دورية .

ملاحظات

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

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

تُقدّم نظرية ديلسارت-جوثالز-سيدل ^{[ 13 ]} مثالاً على تطبيق رموز ريد-سولومون المختصرة. وبالتوازي مع الاختصار، تسمح تقنية تُعرف باسم التثقيب بحذف بعض رموز التكافؤ المشفرة.

فك تشفير عرض BCH

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

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

قام دانيال غورنشتاين ونيل زيرلر بتطوير جهاز فك تشفير، وُصف في تقرير لمختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا (MIT) بقلم زيرلر في يناير 1960، ثم في ورقة بحثية لاحقة في يونيو 1961. ^{[ 14 ]}^{[ 15 ]} وتم وصف جهاز فك التشفير غورنشتاين-زيرلر والعمل ذي الصلة برموز BCH في كتاب " رموز تصحيح الأخطاء" للمؤلف دبليو ويسلي بيترسون (1961). ^{[ 3 ]}

التركيبة

الرسالة المرسلة، $(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ᵢ صفرًا إذا لم يكن هناك خطأ عند تلك القوة من x ، وغير صفري إذا كان هناك خطأ. إذا كان هناك ν _خطأ عند قوى مختلفة iᵏ _لـ x ، فإن $e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}.$

يهدف جهاز فك التشفير إلى إيجاد عدد الأخطاء ( ν ) _{_،} ومواقع الأخطاء ( ik )، وقيم الأخطاء عند تلك المواقع ( eik ). ومن هذه المعلومات، يمكن حساب 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 \geq 2ν)$ في 2ν من المجاهيل، لكن هذا النظام غير خطي بالنسبة لـ Xk ولا يملك حلًا واضحًا. مع ذلك، إذا عُرفت _قيمة Xk (انظر أدناه)، فإن معادلات المتلازمات تُعطي نظامًا خطيًا من المعادلات _. ${\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

في صيغة هذه الخوارزمية حيث تكون مواقع الأخطاء معروفة مسبقًا (عند استخدامها كرمز محو )، ينتهي الأمر عند هذا الحد. مواقع الأخطاء ( Xk ₎ معروفة مسبقًا بطريقة أخرى (على سبيل المثال، في إرسال 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 شاملًا، وهذا التكافؤ صحيح لجميع هذه القيم. لذلك، لدينا 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 قيمة ν مباشرةً، بل يبحث عنها بتجربة قيم متتالية. يبدأ المُفكِّك بافتراض أكبر قيمة تجريبية لـ ν، ويُنشئ النظام الخطي بناءً على هذه القيمة. إذا أمكن حل المعادلات (أي أن مُحدِّد المصفوفة غير صفري)، فإن هذه القيمة التجريبية تُمثِّل عدد الأخطاء. أما إذا تعذَّر حل النظام الخطي، فيُخفَّض عدد الأخطاء في القيمة التجريبية ν بمقدار واحد، ويُفحص النظام الأصغر التالي. ^{[ 16 ]}

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

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

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

بمجرد معرفة مواقع الخطأ Xk _{، يمكن تحديد قيم الخطأ. ويمكن القيام بذلك}_{عن طريق الحل المباشر لـ Yk} في مصفوفة معادلات الخطأ المذكورة أعلاه، أو باستخدام خوارزمية فورني .

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

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

أصلح الأخطاء

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

مثال

لنفترض رمز ريد-سولومون المعرّف في $GF (929)$ مع $α = 3$ و $t = 4$ (يُستخدم هذا في رموز PDF417 الشريطية) لرمز RS(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 + 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,$ بجذرين x1 = 757 = 3 _-³ و x2 = ₅₆₂ = 3 ^{- 4.} يمكن عكس المعاملات: $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 ).

مثال

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

ن	S _{n +1}	د	ج	ب	ب	م
0	732	732	197 س + 1	1	732	1
1	637	846	173 × + 1	1	732	2
2	762	412	634 × ² + 173 × + 1	173 × + 1	412	1
3	925	576	329 × ² + 821 × + 1	173 × + 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⁻¹ _: = x ^t R₀ : = S ( _x) A⁻¹ _:₌ 0 _A₀_: = 1 i _:₌ 0 طالما أن درجة Rᵢ _≥ t _/ 2 i : = i + ₁ Q : = Rᵢ⁻² / Rᵢ⁻¹ Rᵢ _: = _Rᵢ⁻²_-Q Rᵢ⁻¹ _Aᵢ : = _Aᵢ⁻²- Q Aᵢ⁻¹

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

Λ( x ) = A _i / A _i (0)

Ω( x ) = R _i / A _i (0)

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

مثال

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

أنا	R _i	الذكاء _{الاصطناعي}
-1	001 × ⁴ + 000 × ³ + 000 × ² + 000 × + 000	٠٠٠
0	925 × ³ + 762 × ² + 637 × + 732	001
1	683 × ² + 676 × + 024	697 × + 396
2	673 × + 596	608 × ² + 704 × + 544

Λ( س ) = أ ₂ / 544 = 329 × ² + 821 × + 001

Ω( x ) = R² _/ 544 = 546x + 732

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

يمكن استخدام تحويل فورييه المنفصل لفك التشفير. ^{[ 17 ]} لتجنب التعارض مع أسماء المتلازمات، لنفترض أن 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⌋$ من الأخطاء. ومع ذلك، فإن حد تصحيح الأخطاء هذا ليس دقيقًا تمامًا.

في عام ١٩٩٩، نشر مادو سودان وفينكاتيسان غورو سوامي من معهد ماساتشوستس للتكنولوجيا بحثًا بعنوان "تحسين فك تشفير رموز ريد-سولومون والهندسة الجبرية"، حيث قدّما خوارزمية تسمح بتصحيح الأخطاء التي تتجاوز نصف الحد الأدنى لمسافة الرمز. ^{[ ١٨ ]} تنطبق هذه الخوارزمية على رموز ريد-سولومون، وبشكل أعم على رموز الهندسة الجبرية . تُنتج هذه الخوارزمية قائمة من الكلمات المشفرة (فهي خوارزمية فك تشفير قائمة )، وتعتمد على الاستيفاء وتحليل كثيرات الحدود على حقل $غالوا GF (2m)$ وامتداداته.

في عام 2023، أظهر علماء نظرية الترميز أن رموز ريد-سولومون المُعرَّفة على نقاط تقييم عشوائية يمكنها تحقيق قدرة فك تشفير قائمة (حتى $n - k$ خطأ) على أبجديات ذات حجم خطي باحتمالية عالية . ^{[ 19 ]}^{[ 20 ]}^{[ 21 ]} ولا تُقدِّم هذه النتائج خوارزمية لتنفيذ عملية فك التشفير.

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

تُعدّ طرق فك التشفير الجبرية المذكورة أعلاه طرقًا ذات قرار حاسم، ما يعني أنه يتم اتخاذ قرار حاسم بشأن قيمة كل رمز. على سبيل المثال، يمكن للمفكك أن يربط بكل رمز قيمة إضافية تُعبّر عن ثقة مُزيل تشكيل القناة في صحة الرمز. وقد حفّز ظهور رموز LDPC ورموز التوربو ، التي تستخدم طرق فك التشفير المتكررة القائمة على نشر الاعتقاد ذي القرار المرن لتحقيق أداء تصحيح الأخطاء قريبًا من الحد النظري ، الاهتمام بتطبيق فك التشفير ذي القرار المرن على الرموز الجبرية التقليدية. في عام 2003، قدّم رالف كوتر وألكسندر فاردي خوارزمية فك تشفير قائمة جبرية ذات قرار مرن تعمل في وقت متعدد الحدود لرموز ريد-سولومون، والتي استندت إلى عمل سودان وغوروسوامي. ^[²²^] وفي عام 2016، نشر ستيفن ج. فرانك وجوزيف هـ. تايلور مُفكك تشفير جديدًا ذو قرار مرن. ^[²³^]

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

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

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

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

جهاز فك التشفير من بيرليكامب ويلش

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

مثال

باستخدام RS(7,3) و GF(929) ومجموعة نقاط التقييم $a i = i - 1$

أ = {0، 1، 2، 3، 4، 5، 6}

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

p (x) = 0.03x² + 0.02x + 0.01

كلمة السر هي

ج = {001، 006، 017، 034، 057، 086، 121}

قد تتسبب أخطاء الإرسال في استلام هذه الرسالة بدلاً من ذلك.

ب = ج + هـ = {001، 006، 123، 456، 057، 086، 121}

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

b i E (a i) - Q (a i) = 0

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

b i (e 0 + e 1 a i) - (q 0 + q 1 a i + q 2 a 2 i + q 3 a 3 i + q 4 a 4 i) = - b i a 2 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) = 0.03x⁴ + 916x³ + 0.09x² + 0.07x + 0.06​

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

Q (x) / E (x) = P (x)=0.03x² + 0.02x + 0.01 ​

أعد حساب $P$ $($ $x$ $)$ حيث $E$ $($ $x$ $) = 0$ $: {2, 3}$ لتصحيح $b$ مما ينتج عنه الكلمة المشفرة المصححة:

ج = {001، 006، 017، 034، 057، 086، 121} }

}

جهاز فك التشفير غاو

في عام 2002، قام شوهونغ غاو بتطوير جهاز فك تشفير محسّن، استنادًا إلى خوارزمية إقليدس الموسعة. ^{[ 24 ]}

مثال

$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$

أنا	R _i	الذكاء _{الاصطناعي}
-1	001 × ⁷ + 908 × ⁶ + 175 × ⁵ + 194 × ⁴ + 695 × ³ + 094 × ² + 720 × + 000	٠٠٠
0	055 × ⁶ + 440 × ⁵ + 497 × ⁴ + 904 × ³ + 424 × ² + 472 × + 001	001
1	702 × ⁵ + 845 × ⁴ + 691 × ³ + 461 × ² + 327 × + 237	152 × + 237
2	266 × ⁴ + 086 × ³ + 798 × ² + 311 × + 532	708 × ² + 176 × + 532

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

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

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

Q (x) = 0.03x⁴ + 916x³ + 0.09x² + 0.07x + 0.06​

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

Q (x) / E (x) = P (x)=0.03x² + 0.02x + 0.01 ​

أعد حساب $P$ $($ $x$ $)$ حيث $E$ $($ $x$ $) = 0$ $: {2, 3}$ لتصحيح $b$ مما ينتج عنه الكلمة المشفرة المصححة:

ج = {001، 006، 017، 034، 057، 086، 121}

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

في حوالي عام 2015، تم تطوير مُفكِّك شفرة مُحسَّن. ^{[ 25 ]} يُولِّد مُفكِّك الشفرة متلازمات، وعلى غرار وجهة نظر BCH، فإن المعادلة الرئيسية بين مُتعدد حدود مُحدِّد الخطأ والمتلازمات هي نفسها، ولكن مُتعدد حدود مُحدِّد الخطأ له جذور مُقابلة لـ $(1/\alpha _{i})$ ويتم استخدام جدول بحث لتحويل الجذور إلى إزاحات الكلمات المشفرة.

التهيئة: يتم تعريف متعددة الحدود: $L=\Pi _{i=0}^{n-1}(x-\alpha _{i})$ مجموعة من $n$ تعريف كثيرات الحدود: $L_{i}=L/(x-\alpha _{i})$ مجموعة من $n$ يتم توليد القيم $u_{i}=L_{i}(\alpha _{i})$ مجموعة من $n$ يتم توليد كثيرات الحدود: $P_{i}=(u_{i}/(1-\alpha _{i}z))\mod (z^{n-k})$

فك التشفير - يتم استلام كلمة رمزية تحتوي على أخطاء محتملة $r=\{r_{0},r_{1},\dots ,r_{n-1}\}$ يتم توليد متعدد الحدود للمتلازمة $S=\Sigma _{i=0}^{n-1}r_{i}P_{i}$ . لو $S=0$ عندئذٍ لا يتم اكتشاف أي أخطاء، وإلا يبدأ برنامج Euclid الموسع بـ $R_{-1}=z^{n-k}$ ، $R_{0}=S$ ، $A_{-1}=0$ ، $A_{0}=1$ ويستمر ذلك حتى درجة $R_{i}<(n-k)/2$ متعدد الحدود لتحديد موقع الخطأ هو $\sigma =A_{i}$ وقيمة الخطأ متعددة الحدود هي $\omega =R_{i}$ $\sigma$ و $\omega$ يتم قسمتها على أقل حد ذي دلالة من $\sigma$ المشتق الرسمي لـ $\sigma$ يتم إنشاء: $\sigma '$ الإزاحات $o$ تتوافق بعض الأخطاء مع جذور $\sigma$ للجذر = $1/\alpha _{i}$ ، $o_{i}=i$ قيمة الخطأ لـ $o_{i}$ يكون $e_{i}=(-\alpha _{i}\ \omega (1/\alpha _{i}))/(u_{i}\ \sigma '(1/\alpha _{i}))$ .

لو $deg(\omega )=deg(\sigma )$ ثم قيمة خطأ مقابلة لـ $\alpha _{b}=0$ تم اكتشافه عند الإزاحة $o_{b}=b$ ويتم حساب قيمة خطأ منفصلة: $B=\{b|\sigma (1/\alpha _{i})=0\}$ ، مجموعة $\alpha _{i}$ المقابل لجذور $\sigma$ $w=$ أهم معامل لـ $\omega$ $e_{b}=w\ u_{b}^{-1}\ (\Pi _{\alpha \in B}\ (-\alpha ))^{-1}$

مثال

باستخدام نفس البيانات المستخدمة في مثال بيرلكامب ويلش

التهيئة: $a=\{000,001,002,003,004,005,006\}$ $u=\{040,689,600,129,600,689,040\}$

أنا	باي
0	040
1	689 ض ³ + 689 ض ² + 689 ض + 689
2	155 ض ³ + 542 ض ² + 271 ض + 600
3	696 ض ³ + 232 ض ² + 387 ض + 129
4	311 ض ³ + 310 ض ² + 542 ض + 600
5	657 ض ³ + 503 ض ² + 658 ض + 689
6	279 ض ³ + 511 ض ² + 240 ض + 040

فك التشفير: $r=\{001,006,123,456,057,086,121\}$ $S=785\ z^{3}+213\ z^{2}+666\ z+055$ إقليدس:

أنا	R _i	الذكاء _{الاصطناعي}
-1	001 ض ⁴ + 000 ض ³ + 000 ض ² + 000 ض + 000	٠٠٠
0	785 ض ³ + 213 ض ² + 666 ض + 055	001
1	658 ز ² + 858 ز + 323	200 ز + 141
2	294 ز + 709	905 z ² + 020 z + 925

$\sigma =905\ z^{2}+020\ z+925$ $\omega =294\ z+709$ انقسام $\sigma$ و $\omega$ بحلول عام 925 $\sigma =006\ z^{2}+924\ z+1$ $\omega =391\ z+55$ $\sigma '=012\ z+924$ $o=\{002,003\}$ $e=\{000,000,106,422,000,000,000\}$ $c=\{001,006,017,034,057,086,121\}=r-e$

انظر أيضاً

ملحوظات

↑ يقدم المؤلفون في Andrews et al. (2007) نتائج محاكاة تُظهر أنه بالنسبة لمعدل الترميز نفسه (1/6)، تتفوق رموز التوربو على رموز ريد-سولومون المتسلسلة بما يصل إلى 2 ديسيبل ( معدل خطأ البت ).^{[ 10 ]}

مراجع

1 2 3 4 5 6 ريد، إيرفينغ س .؛ سولومون، غوستاف (1960). "الرموز متعددة الحدود على حقول منتهية معينة" (ملف PDF) . مجلة جمعية الرياضيات الصناعية والتطبيقية . 8 (2): 300-304 . doi : 10.1137/0108018 .
↑ غورنشتاين، د.؛ زيرلر، ن. (يونيو 1961). "فئة من رموز تصحيح الأخطاء الخطية الدورية في رموز p ^m ". مجلة SIAM . 9 (2): 207-214 . doi : 10.1137/0109020 . JSTOR 2098821 .
1 2 بيترسون، دبليو. ويسلي (1961). رموز تصحيح الأخطاء . مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0262160063. OCLC 859669631 . {{cite book}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
↑ بيترسون، دبليو. ويسلي؛ ويلدون، إي جيه (1996) [1972]. رموز تصحيح الأخطاء ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0-585-30709-1. OCLC 45727875 .
↑ سوجياما، ي.؛ كاساهارا، م.؛ هيراساوا، س.؛ ناميكاوا، ت. (1975). "طريقة لحل معادلة المفتاح لفك تشفير رموز جوبا" . المعلومات والتحكم . 27 (1): 87-99 . doi : 10.1016/S0019-9958(75)90090-X .
↑ غاو، شوهونغ (يناير 2002)، خوارزمية جديدة لفك تشفير رموز ريد-سولومون (ملف PDF) ، كليمسون.
↑ "رموز ريد-سولومون المعممة" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 2020-12-03.
↑ إيمينك، ك. أ. س. (1994)، "رموز ريد-سولومون والقرص المضغوط"، في ويكر، ستيفن ب.؛ بهارجافا، فيجاي ك. (محرران)، رموز ريد-سولومون وتطبيقاتها ، مطبعة IEEE ، رقم ISBN 978-0-7803-1025-4
↑ هاغناور، ج.؛ أوفر، إ.؛ بابكي، ل. (1994). "11. مطابقة مُفكِّكات فيتربي ومُفكِّكات ريد-سولومون في نظام مُتسلسل". رموز ريد سولومون وتطبيقاتها . مطبعة IEEE. ص 433. ISBN 9780470546345. OCLC 557445046 .
1 2 أندروز، ك.س.؛ ديفسالار، د.؛ دولينار، س.؛ هامكينز، ج.؛ جونز، س.ر.؛ بولارا، ف. (2007). "تطوير رموز توربو وLDPC لتطبيقات الفضاء السحيق" (ملف PDF) . وقائع معهد مهندسي الكهرباء والإلكترونيات . 95 (11): 2142-2156 . doi : 10.1109/JPROC.2007.905132 . S2CID 9289140 .
↑ لين، شو؛ كوستيلو، دانيال ج. (1983). ترميز التحكم في الأخطاء: الأساسيات والتطبيقات (محرر ). إنجلوود كليفس، نيوجيرسي: برنتيس هول. ص 171. ISBN 978-0-13-283796-5.
↑ "التعبيرات التحليلية المستخدمة في ترميز BER وأداة BERTool" . مؤرشف من الأصل بتاريخ 2019-02-01 . تم الاطلاع عليه بتاريخ 2019-02-01 .
↑ بفندر، فلوريان؛ زيغلر، غونتر م. (سبتمبر 2004)، "الأعداد المتلامسة، وتعبئة الكرات، وبعض البراهين غير المتوقعة" (ملف PDF) ، إشعارات الجمعية الرياضية الأمريكية ، 51 (8): 873-883 ، مؤرشف (ملف PDF) من الأصل في 9 مايو 2008 ، تم استرجاعه في 28 سبتمبر 2009يشرح نظرية ديلسارت-جوثالز-سيدل كما تم استخدامها في سياق رمز تصحيح الأخطاء للقرص المضغوط .
↑ بيترسون، و. (سبتمبر 1960). "إجراءات التشفير وتصحيح الأخطاء لرموز بوز-تشودري". معاملات IEEE في نظرية المعلومات . 6 (4): 459-470 . Bibcode : 1960IRTIT...6..459P . doi : 10.1109/TIT.1960.1057586 .
↑ غورنشتاين، دانيال؛ زيرلر، نيل (يونيو 1961). "فئة من رموز تصحيح الأخطاء في رموز $p^m$". مجلة جمعية الرياضيات الصناعية والتطبيقية . 9 (2): 207-214 . doi : 10.1137/0109020 .
↑ جيل، جون (بدون تاريخ). "ملاحظات EE387 رقم 7، النشرة رقم 28" (ملف PDF) . جامعة ستانفورد. مؤرشف من الأصل (ملف PDF) في 30 يونيو 2014. تم الاطلاع عليه في 21 أبريل 2010 .
↑ لين، شو؛ كوستيلو، دانيال ج. (2004). ترميز التحكم في الأخطاء: الأساسيات والتطبيقات ( الطبعة الثانية). أبر سادل ريفر، نيوجيرسي: بيرسون/برنتيس هول. الصفحات 255-262 . ISBN 978-0130426727.
↑ غورو سوامي، ف.؛ سودان، م. (سبتمبر 1999)، "تحسين فك تشفير رموز ريد-سولومون ورموز الهندسة الجبرية"، معاملات IEEE في نظرية المعلومات ، 45 (6): 1757-1767 ، CiteSeerX 10.1.1.115.292 ، doi : 10.1109/18.782097
↑ براكينسيك، جوشوا؛ جوبي، سيفاكانث؛ ماكام، فيسو (2023-06-02). "رموز ريد-سولومون العامة تحقق قدرة فك تشفير القوائم" . وقائع الندوة السنوية الخامسة والخمسين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC 2023. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 1488-1501 . arXiv : 2206.05256 . doi : 10.1145 /3564246.3585128 . ISBN 978-1-4503-9913-5.
↑ غو، زيو؛ تشانغ، زيهان (2023). "رموز ريد-سولومون المثقوبة عشوائيًا تحقق سعة فك تشفير القائمة على أبجديات ذات حجم متعدد الحدود" . المؤتمر السنوي الرابع والستون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب (FOCS) . FOCS 2023، سانتا كروز، كاليفورنيا، الولايات المتحدة الأمريكية، 2023. الصفحات 164-176 . arXiv : 2304.01403 . doi : 10.1109/FOCS57990.2023.00019 . ISBN 979-8-3503-1894-4.
↑ الرابية، عمر؛ غورو سوامي، فينكاتيسان؛ لي، راي (2025)، "رموز ريد سولومون العشوائية تحقق قدرة فك تشفير القوائم باستخدام أبجديات ذات حجم خطي"، Advances in Combinatorics ، arXiv : 2304.09445 ، doi : 10.19086/aic.2025.8
↑ كوتر، رالف؛ فاردي، ألكسندر (2003). "فك تشفير ريد-سولومون باستخدام القرار المرن الجبري". معاملات IEEE في نظرية المعلومات . 49 (11): 2809-2825 . Bibcode : 2003ITIT...49.2809K . CiteSeerX 10.1.1.13.2021 . doi : 10.1109/TIT.2003.819332 .
↑ فرانك، ستيفن جيه؛ تايلور، جوزيف إتش. (2016). "مفكك شفرة مفتوح المصدر ذو قرار مرن لرمز ريد-سولومون JT65 (63,12)" (ملف PDF) . QEX (مايو/يونيو): 8-17 . مؤرشف (ملف PDF) من الأصل بتاريخ 9 مارس 2017. تم الاطلاع عليه بتاريخ 7 يونيو 2017 .
↑ "خوارزمية جديدة لفك تشفير رموز ريد-سولومون" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 12-07-2012.
↑ "رموز ريد-سولومون المعممة" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 2020-12-03.

روابط خارجية

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

ويلش، إل آر (1997)، النظرة الأصلية لرموز ريد-سولومون (ملف PDF) ، ملاحظات المحاضرة
كوتر، رالف (2005)، شفرات ريد-سولومون ، محاضرات معهد ماساتشوستس للتكنولوجيا 6.451 (فيديو)، مؤرشف من الأصل في 13 مارس 2013

مقدمة في رموز ريد-سولومون: المبادئ والبنية والتنفيذ (جامعة كارنيجي ميلون)
جيزل، ويليام أ. (أغسطس 1990)، درس تعليمي حول ترميز تصحيح الأخطاء ريد-سولومون ، مذكرة فنية، ناسا ، TM-102162
ريد، جيف أ. (أبريل 1995)، سي آر سي وريد سولومون إي سي سي (ملف PDF)

التطبيقات

[11] يقدم المؤلفون في Andrews et al. (2007) نتائج محاكاة تُظهر أنه بالنسبة لمعدل الترميز نفسه (1/6)، تتفوق رموز التوربو على رموز ريد-سولومون المتسلسلة بما يصل إلى 2 ديسيبل ( معدل خطأ البت ).^{[ 10 ]}

[ReedSolomon-1] 1 2 3 4 5 6 ريد، إيرفينغ س .؛ سولومون، غوستاف (1960). "الرموز متعددة الحدود على حقول منتهية معينة" (ملف PDF) . مجلة جمعية الرياضيات الصناعية والتطبيقية . 8 (2): 300-304 . doi : 10.1137/0108018 .

[2] غورنشتاين، د.؛ زيرلر، ن. (يونيو 1961). "فئة من رموز تصحيح الأخطاء الخطية الدورية في رموز p ^m ". مجلة SIAM . 9 (2): 207-214 . doi : 10.1137/0109020 . JSTOR 2098821 .

[Peterson61-3] 1 2 بيترسون، دبليو. ويسلي (1961). رموز تصحيح الأخطاء . مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0262160063. OCLC 859669631 . {{cite book}}عدم توافق رقم ISBN / التاريخ ( مساعدة )

[Peterson96-4] بيترسون، دبليو. ويسلي؛ ويلدون، إي جيه (1996) [1972]. رموز تصحيح الأخطاء ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0-585-30709-1. OCLC 45727875 .

[5] سوجياما، ي.؛ كاساهارا، م.؛ هيراساوا، س.؛ ناميكاوا، ت. (1975). "طريقة لحل معادلة المفتاح لفك تشفير رموز جوبا" . المعلومات والتحكم . 27 (1): 87-99 . doi : 10.1016/S0019-9958(75)90090-X .

[gao-6] غاو، شوهونغ (يناير 2002)، خوارزمية جديدة لفك تشفير رموز ريد-سولومون (ملف PDF) ، كليمسون.

[7] "رموز ريد-سولومون المعممة" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 2020-12-03.

[8] إيمينك، ك. أ. س. (1994)، "رموز ريد-سولومون والقرص المضغوط"، في ويكر، ستيفن ب.؛ بهارجافا، فيجاي ك. (محرران)، رموز ريد-سولومون وتطبيقاتها ، مطبعة IEEE ، رقم ISBN 978-0-7803-1025-4

[9] هاغناور، ج.؛ أوفر، إ.؛ بابكي، ل. (1994). "11. مطابقة مُفكِّكات فيتربي ومُفكِّكات ريد-سولومون في نظام مُتسلسل". رموز ريد سولومون وتطبيقاتها . مطبعة IEEE. ص 433. ISBN 9780470546345. OCLC 557445046 .

[Andrews,_2007-10] 1 2 أندروز، ك.س.؛ ديفسالار، د.؛ دولينار، س.؛ هامكينز، ج.؛ جونز، س.ر.؛ بولارا، ف. (2007). "تطوير رموز توربو وLDPC لتطبيقات الفضاء السحيق" (ملف PDF) . وقائع معهد مهندسي الكهرباء والإلكترونيات . 95 (11): 2142-2156 . doi : 10.1109/JPROC.2007.905132 . S2CID 9289140 .

[12] لين، شو؛ كوستيلو، دانيال ج. (1983). ترميز التحكم في الأخطاء: الأساسيات والتطبيقات (محرر ). إنجلوود كليفس، نيوجيرسي: برنتيس هول. ص 171. ISBN 978-0-13-283796-5.

[13] "التعبيرات التحليلية المستخدمة في ترميز BER وأداة BERTool" . مؤرشف من الأصل بتاريخ 2019-02-01 . تم الاطلاع عليه بتاريخ 2019-02-01 .

[14] بفندر، فلوريان؛ زيغلر، غونتر م. (سبتمبر 2004)، "الأعداد المتلامسة، وتعبئة الكرات، وبعض البراهين غير المتوقعة" (ملف PDF) ، إشعارات الجمعية الرياضية الأمريكية ، 51 (8): 873-883 ، مؤرشف (ملف PDF) من الأصل في 9 مايو 2008 ، تم استرجاعه في 28 سبتمبر 2009يشرح نظرية ديلسارت-جوثالز-سيدل كما تم استخدامها في سياق رمز تصحيح الأخطاء للقرص المضغوط .

[15] بيترسون، و. (سبتمبر 1960). "إجراءات التشفير وتصحيح الأخطاء لرموز بوز-تشودري". معاملات IEEE في نظرية المعلومات . 6 (4): 459-470 . Bibcode : 1960IRTIT...6..459P . doi : 10.1109/TIT.1960.1057586 .

[16] غورنشتاين، دانيال؛ زيرلر، نيل (يونيو 1961). "فئة من رموز تصحيح الأخطاء في رموز $p^m$". مجلة جمعية الرياضيات الصناعية والتطبيقية . 9 (2): 207-214 . doi : 10.1137/0109020 .

[17] جيل، جون (بدون تاريخ). "ملاحظات EE387 رقم 7، النشرة رقم 28" (ملف PDF) . جامعة ستانفورد. مؤرشف من الأصل (ملف PDF) في 30 يونيو 2014. تم الاطلاع عليه في 21 أبريل 2010 .

[18] لين، شو؛ كوستيلو، دانيال ج. (2004). ترميز التحكم في الأخطاء: الأساسيات والتطبيقات ( الطبعة الثانية). أبر سادل ريفر، نيوجيرسي: بيرسون/برنتيس هول. الصفحات 255-262 . ISBN 978-0130426727.

[19] غورو سوامي، ف.؛ سودان، م. (سبتمبر 1999)، "تحسين فك تشفير رموز ريد-سولومون ورموز الهندسة الجبرية"، معاملات IEEE في نظرية المعلومات ، 45 (6): 1757-1767 ، CiteSeerX 10.1.1.115.292 ، doi : 10.1109/18.782097

[20] براكينسيك، جوشوا؛ جوبي، سيفاكانث؛ ماكام، فيسو (2023-06-02). "رموز ريد-سولومون العامة تحقق قدرة فك تشفير القوائم" . وقائع الندوة السنوية الخامسة والخمسين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC 2023. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 1488-1501 . arXiv : 2206.05256 . doi : 10.1145 /3564246.3585128 . ISBN 978-1-4503-9913-5.

[21] غو، زيو؛ تشانغ، زيهان (2023). "رموز ريد-سولومون المثقوبة عشوائيًا تحقق سعة فك تشفير القائمة على أبجديات ذات حجم متعدد الحدود" . المؤتمر السنوي الرابع والستون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب (FOCS) . FOCS 2023، سانتا كروز، كاليفورنيا، الولايات المتحدة الأمريكية، 2023. الصفحات 164-176 . arXiv : 2304.01403 . doi : 10.1109/FOCS57990.2023.00019 . ISBN 979-8-3503-1894-4.

[22] الرابية، عمر؛ غورو سوامي، فينكاتيسان؛ لي، راي (2025)، "رموز ريد سولومون العشوائية تحقق قدرة فك تشفير القوائم باستخدام أبجديات ذات حجم خطي"، Advances in Combinatorics ، arXiv : 2304.09445 ، doi : 10.19086/aic.2025.8

[23] كوتر، رالف؛ فاردي، ألكسندر (2003). "فك تشفير ريد-سولومون باستخدام القرار المرن الجبري". معاملات IEEE في نظرية المعلومات . 49 (11): 2809-2825 . Bibcode : 2003ITIT...49.2809K . CiteSeerX 10.1.1.13.2021 . doi : 10.1109/TIT.2003.819332 .

[24] فرانك، ستيفن جيه؛ تايلور، جوزيف إتش. (2016). "مفكك شفرة مفتوح المصدر ذو قرار مرن لرمز ريد-سولومون JT65 (63,12)" (ملف PDF) . QEX (مايو/يونيو): 8-17 . مؤرشف (ملف PDF) من الأصل بتاريخ 9 مارس 2017. تم الاطلاع عليه بتاريخ 7 يونيو 2017 .

[25] "خوارزمية جديدة لفك تشفير رموز ريد-سولومون" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 12-07-2012.

[26] "رموز ريد-سولومون المعممة" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 2020-12-03.

[ 1 ]

[ 2 ]

[ 3 ]

[

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ ملاحظة 1 ]

11

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ ١٨ ]

[ 19 ]

[ 20 ]

[ 21 ]

[

[

[ 24 ]

[ 25 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗