تصحيح خطأ ريد-سولومون
المحتويات
- end
- g = trim(g);
- فك تشفير المتلازمة
- النقل الفضائي
- r1 = Syndromes;
- الملاحظات
- errors = zeros(1, n);
- تحويل فورييه المتقطع وعكسه
- alpha = gf(2, m, prim_poly);
- كلمة المرور هي
- الأمثلة
- Ai := Ai-2 - Q Ai-1
- % RSDECODER Decode a Reed-Solomon encoded message
- تخزين البيانات
- فك تشفير سوجياما
- فك التشفير النظري
- إجراء ترميز بسيط: الرسالة كسلسلة من المعاملات
- Open Source C++ Reed–Solomon Soft Decoding library
- الأمثلة
- التاريخ
- إصلاح الأخطاء
- الأمثلة
- Syndromes = trim(Synd);
- % Remove leading zeros from Galois array
- if len < k
- g = g0 - c;
- التركيبة
- متعدد الحدود لتحديد الخطأ
- فك التشفير
- استيفاء لاغرانج لـ ل ل
- errors_gf = gf(errors, m, prim_poly);
- مُشفِّر
- فك التشفير الناعم
- g0 = f1; g1 = f0;
- alpha = gf(2, m, prim_poly);
- end
- حساب مواقع الخطأ
- التنفيذات
- decoded = orig_vals(1:k);
- error_pos = gf(find(evalPoly == 0), m);
- end
- فك تشفير بيرليكامب ويلش
- محددات الأخطاء وقيم الأخطاء
- نقل البيانات
- % Add leading zeros
- gx = g.x;
- [~, remainder] = deconv(msg_padded, g_x);
- errors(error_pos.x) = error_mag.x;
- فك التشفير خارج حدود تصحيح الخطأ
- فك تشفير عرض بي سي إتش
- الرمز الشريطي
- for idx = 1 : size_error
- الأمثلة
- g = 1;
- % Solve the linear system
- إيجاد جذور متعددة حدود تحديد الخطأ
- المعلومات والدروس التعليمية
- فك تشفير جاو
- وحدة فك ترميز بيترسون-جورنشتاين-زيرلر
- الطرح من كلا الجانبين العائدات
- decoded = orig_vals(1:k);
- R−1 := xt
- إجراء الترميز المنهجي
- حساب قيم الخطأ
- فك تشفير العرض الأصلي لريد سولومون
- الخصائص
- فك التشفير باستخدام تحويل فورييه المنفصل
- end
- فك تشفير بيرليكامب-ماسي
- g_x = genpoly(k, n, alpha);
تعريفًا بالموضوع، في نظرية المعلومات ونظرية الترميز، تُعد رموز ريد–سولومون مجموعة من رموز تصحيح الأخطاء التي قدمها إيرفينج إس. ريد وجوستاف سولومون في عام 1960. لها الكثير من التطبيقات، بما في ذلك تقنيات المستهلك مثل ، والأقراص المضغوطة، وأقراص دي في دي، وأقراص بلو راي، ورموز الاستجابة السريعة، ومصفوفة البيانات، وتقنيات نقل البيانات مثل الخط المشترك الرقمي وواي ماكس، وأنظمة البث مثل الاتصالات عبر الأقمار الصناعية، و بي في دي وهيئة أنظمة التلفزيون المتطورة، وأنظمة التخزين مثل ريد 6. وفيما يلي تفاصيل أوسع عن ذلك.
وفي هذا الصدد، هناك نوعان أساسيان من رموز ريد–سولومونالعرض الأصلي وعرض بي سي إتشمع كون عرض بي سي إتش هو الأكثر شيوعًا، حيث أن فك تشفير عرض بي سي إتش أسرع ويتطلب مساحة تخزين عمل أقل من فك تشفير العرض الأصلي.
وفي هذا الصدد، تعمل أكواد ريد–سولومون على كتلة من البيانات يتم التعامل معها كمجموعة من عناصر المجال المحدود تسمى الرموز. تتمتع رموز ريد–سولومون بالقدرة على اكتشاف أخطاء الرموز المتعددة وتصحيحها. من خلال إضافة رموز التحقق إلى البيانات، يمكن لكود ريد–سولومون اكتشاف (ولكن ليس تصحيح) أي مجموعة من الرموز الخاطئة حتى ، أو تحديد وتصحيح ما يصل إلى من الرموز الخاطئة في مواقع غير معروفة. باعتباره ، فإنه يمكنه تصحيح ما يصل إلى عمليات مسح في المواقع المعروفة والمقدمة للخوارزمية، أو يمكنه اكتشاف وتصحيح مجموعات من الأخطاء والمسح. تعتبر أكواد ريد–سولومون مناسبة كذلك كأكواد تصحيح أخطاء البتات متعددة الانفجارات، حيث أن تسلسل يمكن أن يؤثر خطأ بت متتالي على رمزين بحجم كحد أقصى. يعود اختيار إلى مصمم الكود، ويمكن تحديده ضمن حدود واسعة.
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);
g = trim(g);
evalPoly = polyval(g, alpha .^ (n - 1 : - 1 : 0));
من جانب آخر، % Find the zeros of the error polynomial on this galois field
فك تشفير المتلازمة
ومن جهة أخرى، ميزة النظر إلى المتلازمات هي أن متعدد حدود الرسالة يختفي. بمعنى آخر، تتعلق المتلازمات بالخطأ فقط ولا تتأثر بالمحتوى الفعلي للرسالة المرسلة. إذا كانت جميع المتلازمات صفرًا، تتوقف الخوارزمية عند هذا الحد وتُبلغ عن عدم تلف الرسالة أثناء النقل.
وفي هذا الصدد، يبدأ فك التشفير بتقييم الحدود الواردة في النقاط . نحن نطلق على نتائج هذا التقييم اسم «المتلازمات» S j. يتم تعريفهم على أنهم لاحظ أن لأن له جذور في كما هو موضح في القسم السابق.
النقل الفضائي
ومن جهة أخرى، كانت الإصدارات الحديثة من الترميز التلافيفي المتسلسل المفكوك بواسطة ريد–سولومون/فيتربي تُستعمل ولا تزال تُستعمل في بعثات مارس باثفايندر، وجاليليو، ومركبة استكشاف المريخ، وكاسيني، حيث تعمل ضمن قرابة 1-1.5 ديسيبل من الحد الأقصى، وهو سعة شانون.
علاوةً على ذلك، في حين أن عدد كثيرات الحدود المختلفة من الدرجة الأقل من k وعدد الرسائل المختلفة متساويان وبالتالي، يمكن تعيين كل رسالة بشكل فريد لمثل هذه الحدود، وهناك طرق مختلفة للقيام بهذا الترميز. يفسر البناء الأصلي لريد-سولومون الرسالة x باعتبارها معاملات كثيرة الحدود p، بينما تفسر البناءات اللاحقة الرسالة باعتبارها قيم كثيرة الحدود عند أول k نقطة ويمكن الحصول على كثيرة الحدود p باستيفاء هذه القيم بكثيرة حدود بدرجة أقل من k. تتميز عملية الترميز الأخيرة، وإن كانت أقل كفاءةً بعض الشيء، بميزة أنها تُنتج ، أي أن الرسالة الأصلية تُدرج دائمًا كتسلسل فرعي للكلمة المفتاحية.
وفي هذا السياق، رسميا، المجموعة يتم تعريف كلمات رمز ريد–سولومون على النحو التالي: نظرًا لأن أي حدودين مختلفتين بدرجة أقل من أتفق على الأكثر النقاط، وهذا يعني أن أي كلمتين رمزيتين من قانون ريد–سولومون تختلفان في ما لا يقل عن المواقف. علاوة على ذلك، هناك حدوديتان متفقتان في النقاط ولكنها ليست متساوية، وبالتالي فإن مسافة قانون ريد–سولومون هي بالضبط . ثم المسافة النسبية هي ، أين هو المعدل. إن هذه المقايضة بين المسافة النسبية والمعدل مثالية بشكل مقارب، حيث أن كل كود . باعتباره رمزًا يحقق هذه المقايضة المثلى، فإن رمز ريد–سولومون ينتمي إلى فئة الرموز القابلة للفصل عند أقصى مسافة.
من جانب آخر، إن شفرة ريد–سولومون هي في الواقع عائلة من الشفرات، حيث يتميز كل شفرة بثلاثة معلمات: حجم الأبجدية ، وطول الكتلة ، وطول الرسالة ، مع . يتم تفسير مجموعة رموز الأبجدية على أنها الحقل المحدود من أجل ، وبالتالي، يجب أن تكون قوة رئيسية. في أكثر معلمات كود ريد–سولومون فائدة، يكون طول الكتلة عادةً مضاعفًا ثابتًا لطول الرسالة، أي المعدل هو ثابت ما، وعلاوة على ذلك، فإن طول الكتلة إما أن يكون مساويًا لحجم الأبجدية أو أقل منه بواحد، أي، أو .
يتم الآن استبدال هذه الرموز المتسلسلة أكثر قوة:
كذلك، وجهة النظر الأصلية لريد وسولومون: الكلمة الرمزية كسلسلة من القيم
وعلى صعيد آخر، قدمت مركبة فوييجر تشفير ريد–سولومون المترابط مع ، وهي ممارسة أصبحت منذ ذلك الحين منتشرة على نطاق واسع في الفضاء العميق والاتصالات عبر الأقمار الصناعية (مثلًا، البث الرقمي المباشر).
الإنشاءات (الترميز)
في هذا الإطار، تميل إلى إنتاج أخطاء في دفعات قصيرة. إن تصحيح أخطاء الانفجار هذه هو المهمة التي يمكن إنجازها على أفضل وجه باستخدام أكواد ريد–سولومون القصيرة أو المبسطة.
من جهة ثانية، كان أحد التطبيقات المهمة لتشفير ريد–سولومون هو تشفير الصور الرقمية التي أرسلها برنامج فوييجر.
وفي هذا السياق، توجد إجراءات ترميز مختلفة لرمز ريد–سولومون، وبالتالي، توجد طرق مختلفة لوصف مجموعة كل الكلمات الرمزية. في العرض الأصلي لريد وسولومون، كل كلمة رمزية من رمز ريد–سولومون هي عبارة عن تسلسل من قيم الدالة لكثيرة حدود من الدرجة الأقل من . من أجل الحصول على كلمة رمزية لرمز ريد–سولومون، يتم التعامل مع رموز الرسائل (كل منها ضمن الأبجدية بحجم q) كمعاملات لكثيرة حدود من الدرجة أقل من ، فوق المجال المحدود مع عناصر. وبدوره، فإن كثيرة الحدود يتم تقييمه في نقاط مميزة من الميدان ، وتسلسل القيم هو الكلمة الرمزية المقابلة. تتضمن الاختيارات الشائعة لمجموعة من نقاط التقييم ما يلي: ، ، أو ل ، ،...، أين هو من .
r1 = Syndromes;
f1 = gf(zeros(1, size_r0), m, prim_poly);
f0 = gf([zeros(1, size_r0 - 1) 1], m, prim_poly);
الملاحظات
وعلى صعيد آخر، توضح نظرية ديلسارت-جوثالز-سايدل مثالاً لتطبيق رموز ريد–سولومون المختصرة. وبالتوازي مع الاختصار، هناك تقنية تُعرف بالثقب تسمح بحذف بعض رموز التكافؤ المشفرة.
كذلك، يستعمل رمز الاستجابة السريعة، الإصدار 3 (29×29) كتلًا متداخلة. تتكون الرسالة من 26 بايت بيانات ويتم تشفيرها باستخدام كتلتين من رموز ريد-سولومون. كل كتلة عبارة عن رمز (255,233) ريد سولومون مختصر إلى رمز (35,13).
وفي هذا الصدد، لا يُطلب من المصممين استخدام الأحجام «الطبيعية» لكتل كود ريد–سولومون. يمكن لتقنية تُعرف باسم «الاختصار» إنتاج كود أصغر بأي حجم مرغوب من كود أكبر. مثلًا، يمكن تحويل الكود المستعمل على نطاق واسع (255,223) إلى كود (160,128) عن طريق تعبئة الجزء غير المستعمل من كتلة المصدر بـ 95 صفرًا ثنائيًا وعدم إرسالها. في جهاز فك التشفير، يتم تحميل نفس الجزء من الكتلة محليًا باستخدام الأصفار الثنائية.
errors = zeros(1, n);
- g = []؛
- S = []؛
- % Get the alpha
تحويل فورييه المتقطع وعكسه
بالنسبة لـ«رمز المعنى الضيق»، .
وجهة نظر بي سي إتش: الكلمة الرمزية كسلسلة من المعاملات
وعلى صعيد آخر، في هذا العرض، يتم تفسير الرسالة كمعاملات متعددة الحدود . يقوم المرسل بحساب كثير الحدود ذي الصلة من الدرجة أين ويرسل الحدود المتعددة . كثيرة الحدود يتم إنشاؤها عن طريق ضرب حدود الرسالة ، والتي لديها درجة ، مع من الدرجة وهذا معروف لدى المرسل والمستقبل.مولد الحدود متعدد الحدود يتم تعريفه على أنه متعدد الحدود الذي تكون جذوره عبارة عن قوى متسلسلة لبدائية مجال جالوا
في هذا الإطار، يمكن استخدام تحويل فورييه العكسي لتحويل مجموعة خالية من الأخطاء من قيم الرسائل n < q مرة أخرى إلى متعددة الحدود المشفرة لمعاملات k، مع القيد الذي ينص على أنه لكي يعمل هذا، يجب أن تكون مجموعة نقاط التقييم المستعملة لتشفير الرسالة عبارة عن مجموعة من القوى المتزايدة لـ α :
كذلك، ومع ذلك، فإن استيفاء لاغرانج يؤدي نفس التحويل دون قيود على مجموعة نقاط التقييم أو متطلبات مجموعة خالية من الأخطاء من قيم الرسائل ويُستعمل للترميز المنهجي، وفي إحدى خطوات فك تشفير جاو.
ومن ناحية أخرى، تحويل فورييه المنفصل هو في الأساس نفس إجراء الترميز؛ فهو يستعمل متعدد الحدود المولد لربط مجموعة من نقاط التقييم بقيم الرسائل كما هو موضح أعلاه:
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));
كلمة المرور هي
- قد يؤدي حدوث أخطاء في الإرسال إلى استلام هذا بدلاً من ذلك.
- المعادلة الأساسية هي:
- افترض الحد الأقصى لعدد الأخطاء: . المعادلة الأساسية تصبح:
- استخدام الإزالة الغاوسية :
- Recalculate where to correct resulting in the corrected codeword:
الأمثلة
كذلك، باستخدام نفس البيانات المستعملة في مثال بيترسون جورنشتاين زيرلر أعلاه:
القيمة النهائية لـ C هي متعددة حدود تحديد الخطأ، Λ(x).
Ai := Ai-2 - Q Ai-1
وعلى صعيد آخر، لتعيين الحد الأدنى من الترتيب لـ Λ(x) إلى 1، قسّم Λ(x) وΩ(x) على A i (0):
A i (0) هو الحد الثابت (من الدرجة المنخفضة) لـ A i.
% 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
تخزين البيانات
وفي هذا الصدد، تستعمل أقراص دي في دي مخططًا مشابهًا، ولكن مع كتل أكبر بكثير، وكود داخلي (208,192)، وكود خارجي (182,172).
ومن ناحية أخرى، يتم استخدام تصحيح خطأ ريد–سولومون كذلك في ملفات بارشيف والتي يتم نشرها عادةً مع ملفات الوسائط المتعددة على يوزنت. كما استعملت خدمة التخزين عبر الإنترنت الموزعة ووالا (التي تم إيقافها في سنة 2015) كذلك ريد–سولومون عند تقسيم الملفات.
في هذا الإطار، يتم استخدام تشفير ريد–سولومون على نطاق واسع في أنظمة التخزين الشامل لتصحيح أخطاء الانفجار المرتبطة بعيوب الوسائط.
وفي السياق ذاته، يعتبر تشفير ريد–سولومون أحد المكونات الأساسية للقرص المضغوط. كان هذا أول استخدام لترميز تصحيح الأخطاء القوي في منتج استهلاكي يتم إنتاجه بكميات كبيرة، وتستعمل دات ودي في دي مخططات مماثلة. في القرص المضغوط، يتم فصل طبقتين من ترميز ريد–سولومون بواسطة متداخل ملتف ذي 28 اتجاهًا مما ينتج عنه مخطط يسمى ترميز ريد–سولومون المتداخل المتقاطع . العنصر الأول في فك تشفير ترميز ريد–سولومون المتداخل هو رمز ريد–سولومون الداخلي الضعيف نسبيًا (32،28)، والذي تم اختصاره من رمز (255،251) برموز مكونة من 8 بت. يمكن لهذا الكود تصحيح أخطاء تصل إلى 2 بايت لكل كتلة مكونة من 32 بايت. والأمر الأكثر أهمية هو أنه يقوم بتمييز أي كتل غير قابلة للتصحيح على أنها محذوفة، أي الكتل التي تحتوي على أخطاء أكبر من 2 بايت. يتم لاحقًا نشر الكتل المفكوكة المكونة من 28 بايتًا، مع مؤشرات المسح، بواسطة مزيل التداخل إلى كتل مختلفة من الكود الخارجي (28،24). بفضل إزالة التداخل، تصبح كتلة ممسوحة مكونة من 28 بايتًا من الكود الداخلي بايتًا ممسوحًا واحدًا في كل كتلة من كتل الكود الخارجية البالغ عددها 28 بايتًا. يقوم الكود الخارجي بتصحيح هذه المشكلة بسهولة، لأنه يمكنه التعامل مع ما يصل إلى 4 عمليات مسح من هذا القبيل لكل كتلة.
ومن ناحية أخرى، النتيجة هي ترميز ريد–سولومون المتداخل الذي يمكنه تصحيح أخطاء تصل إلى 4000 بت، أو نحو 2.5 ملم على سطح القرص. هذا الكود قوي جدًا لدرجة أن أغلب أخطاء تشغيل الأقراص المضغوطة ناجمة على الأرجح عن أخطاء التتبع التي تتسبب في خروج الليزر عن المسار، وليس عن طريق انفجارات الأخطاء غير القابلة للتصحيح.
فك تشفير سوجياما
ومن ناحية أخرى، تعتمد طريقة تكرارية أخرى لحساب كل من متعدد حدود تحديد الخطأ ومتعدد حدود قيمة الخطأ على تكييف سوجياما لخوارزمية إقليدية ممتدة.
- عرف S (x)، Λ(x)، وΩ(x) لمتلازمات t وأخطاء e :
- المعادلة الأساسية هي:
- بالنسبة إلى t = 6 و e = 3:
- الحدود الوسطى هي صفر بسبب العلاقة بين Λ والمتلازمات.
- يمكن لخوارزمية إقليدية ممتدة العثور على سلسلة من كثيرات الحدود من النموذج
- حيث تقل درجة R مع زيادة i. بمجرد أن تصبح درجة R i (x) < t /2، فإن
- لا يلزم حفظ B (x) و Q (x)، لذا تصبح الخوارزمية:
فك التشفير النظري
من جانب آخر، وصف ريد وسولومون فك تشفير نظري يصحح الأخطاء من خلال العثور على متعدد الحدود للرسالة الأكثر شيوعًا. لا يعرف المُفكك سوى مجموعة القيم ل وأي طريقة ترميز تم استخدامها لتوليد تسلسل قيم الكلمة الرمزية. الرسالة الأصلية، والمتعددة الحدود، وأي أخطاء غير معروفة. يمكن لإجراء فك التشفير استخدام طريقة مثل استيفاء لاغرانج على مجموعات فرعية مختلفة من قيم كلمة المرور n المأخوذة k في كل مرة لإنتاج كثيرات الحدود المحتملة بشكل متكرر، حتى يتم إنتاج عدد كافٍ من كثيرات الحدود المطابقة للقضاء بشكل معقول على أي أخطاء في كلمة المرور المستلمة. بمجرد تحديد كثير الحدود، يمكن تصحيح أي أخطاء في كلمة الرمز، عن طريق إعادة حساب قيم كلمة الرمز المقابلة. لسوء الحظ، في جميع الحالات، باستثناء أبسطها، هناك عدد كبير جدًا من المجموعات الفرعية، وبالتالي فإن الخوارزمية غير عملية. عدد المجموعات الفرعية هو المعامل الثنائي، ، وعدد المجموعات الفرعية غير ممكن حتى بالنسبة للرموز المتواضعة. بالنسبة لكود الذي يمكنه تصحيح 3 أخطاء، فإن فك التشفير النظري الساذج سوف يفحص 359 مليار مجموعة فرعية.
إجراء ترميز بسيط: الرسالة كسلسلة من المعاملات
إجراء الترميز المنهجي: الرسالة كتسلسل أولي من القيم
لما يلي -مصفوفة مع عناصر من :
ومن ناحية أخرى، في البناء الأصلي لريد وسليمان، الرسالة يتم تعيينه إلى كثير الحدود مع كلمة السر لـ يتم الحصول عليها عن طريق التقييم في نقاط مختلفة من الميدان . وبالتالي فإن وظيفة الترميز الكلاسيكية بالنسبة لقانون ريد–سولومون، يتم تعريفه على النحو التالي: هذه الوظيفة هو رسم تخطيطي خطي، أي أنه يلبي لما يلي -مصفوفة مع عناصر من :
من جانب آخر، هذه الوظيفة هي عبارة عن رسم خطي. لتوليد مصفوفة الترميز النظامية المقابلة G، اضرب مصفوفة Vandermonde A في معكوس مصفوفة المربع الأيسر الفرعية A.
كذلك، هناك إجراءات ترميز بديلة تعمل على إنتاج رمز ريد–سولومون المنهجي. تستعمل إحدى الطرق استيفاء لاغرانج لحساب كثيرات الحدود مثل ذلك ثم يتم تقييمه في النقاط الأخرى .
من جهة ثانية، هذه المصفوفة هي مصفوفة فاندرموند . بعبارة أخرى، فإن شفرة ريد–سولومون هي شفرة خطية، وفي إجراء الترميز الكلاسيكي، تكون مصفوفة المولد الخاصة بها .
Open Source C++ Reed–Solomon Soft Decoding library
ومن جهة أخرى، Matlab implementation of errors and-erasures Reed–Solomon decoding
الأمثلة
وفي السياق ذاته، باستخدام نفس البيانات المستعملة في مثال بيترسون-جورينشتاين-زيرلر أعلاه:
التاريخ
وفي هذا السياق، في سنة 1977، تم تنفيذ أكواد ريد–سولومون في برنامج فوييجر في شكل . ظهر أول تطبيق تجاري في المنتجات الاستهلاكية المنتجة بكميات كبيرة في عام 1982 مع القرص المضغوط، حيث تم استخدام رمزين متداخلين من نوع ريد–سولومون. اليوم، يتم تنفيذ أكواد ريد–سولومون على نطاق واسع في أجهزة التخزين الرقمية ومعايير الاتصالات الرقمية، على الرغم من استبدالها ببطء بأكواد بوز-تشودهوري-هوكوينغيم (بي سي إتش). مثلًا، يتم استخدام رموز ريد–سولومون في معيار البث الرقمي للفيديو (بي في دي) معيار بث الفيديو الرقمي فضائيا، بالاشتراك مع رمز داخلي ملتف، ولكن يتم استخدام رموز بي سي إتش مع في خليفته، معيار بي في دي-إس2.
وفي السياق ذاته، في سنة 1969، تم تطوير فك تشفير مخطط بي سي إتش المحسن بواسطة إلوين بيرليكامب وجيمس ماسي ومنذ ذلك الحين أصبح يُعرف باسم .
من جانب آخر، في سنة 1960 كذلك، تم وصف فك تشفير متعدد الحدود عملي ثابت لرموز بي سي إتش الذي طوره دانييل جورنشتاين ونيل زيرلر في تقرير صادر عن مختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا بواسطة زيرلر في يناير 1960 وفي وقت لاحق في مقال في يونيو 1961. تم وصف فك تشفير جورنشتاين-زيرلر والعمل المرتبط به على رموز بي سي إتش في كتاب «رموز تصحيح الأخطاء» بقلم و. ويزلي بيترسون (1961). بحلول عام 1963 (أو ربما قبل ذلك)، كان جيه جيه ستون (وآخرون) أدرك أن رموز ريد–سولومون يمكنها استخدام مخطط بي سي إتش باستخدام متعدد الحدود المولد الثابت، مما يجعل مثل هذه الرموز فئة خاصة من رموز بي سي إتش، ولكن رموز ريد–سولومون المستندة إلى مخطط الترميز الأصلي ليست فئة من رموز بي سي إتش، واعتمادًا على مجموعة نقاط التقييم، فهي ليست حتى .
وفي هذا الصدد، في سنة 1975، تم تطوير فك تشفير مخطط بي سي إتش محسن آخر بواسطة ياسو سوجياما، استنادًا إلى خوارزمية إقليدية موسعة.
التطبيقات
علاوةً على ذلك، في عام 2002، تم تطوير فك تشفير مخطط أصلي آخر بواسطة شوهونج جاو، استنادًا إلى خوارزمية إقليدية ممتدة.
في عام 1986، تم تطوير فك تشفير المخطط الأصلي المعروف باسم .
كذلك، تم تطوير رموز ريد–سولومون في سنة 1960 من قبل إيرفينج إس. ريد وجوستاف سولومون، اللذين كانا آنذاك من أعضاء هيئة التدريس في مختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا. كان عنوان مقالهم الرائد «الرموز متعددة الحدود على حقول محدودة معينة». استعمل مخطط الترميز الأصلي الموصوف في مقال ريد وسولومون متعدد الحدود المتغير استنادًا إلى الرسالة التي يجب ترميزها حيث تكون مجموعة ثابتة فقط من القيم (نقاط التقييم) التي يجب ترميزها معروفة للمشفر وفك التشفير. قام فك التشفير النظري الأصلي بإنشاء كثيرات حدود محتملة استنادًا إلى مجموعات فرعية من k (طول الرسالة غير المشفرة) من بين n (طول الرسالة المشفرة) من قيم الرسالة المستلمة، واختيار كثير الحدود الأكثر شيوعًا باعتباره الصحيح، وهو ما كان غير عملي في جميع الحالات باستثناء أبسطها. تم حل هذه المشكلة في البداية عن طريق تغيير المخطط الأصلي إلى مخطط يشبه رمز بي سي إتش يعتمد على كثير حدود ثابت معروف لكل من المشفر وفك التشفير، ولكن في وقت لاحق، تم تطوير أجهزة فك تشفير عملية تعتمد على المخطط الأصلي، على الرغم من أنها أبطأ من مخططات بي سي إتش. النتيجة هي وجود نوعين رئيسيين من رموز ريد–سولومون: تلك التي تستعمل مخطط الترميز الأصلي وتلك التي تستعمل مخطط ترميز بي سي إتش.
ومن ناحية أخرى، في سنة 1996، تم تطوير أشكال مختلفة من أجهزة فك التشفير الأصلية والتي تسمى أجهزة فك التشفير القائمة أو أجهزة فك التشفير الناعمة بواسطة مادو سودان وآخرين، ويستمر العمل على هذه الأنواع من أجهزة فك التشفير (انظر ).
إصلاح الأخطاء
كذلك، أخيرًا، يتم إنشاء e (x) من i k و e i k ثم يتم طرحه من r (x) للحصول على الرسالة المرسلة في الأصل s (x)، مع تصحيح الأخطاء.
الأمثلة
في هذا الإطار، باستخدام الإزالة الغاوسية، لذا مع الجذور x 1 = 757 = 3 −3 و x 2 = 562 = 3 −4. يمكن عكس المعاملات: لإنتاج الجذور 27 = 3 3 و 81 = 3 4 مع أسس موجبة، ولكن عادةً لا يتم استخدام ذلك. يتوافق لوغاريتم الجذور المقلوبة مع مواقع الخطأ (من اليمين إلى اليسار، الموقع 0 هو المصطلح الأخير في الكلمة الرمزية).
وفي هذا الصدد، خذ بعين الاعتبار رمز ريد–سولومون المحدد في مع و (يستعمل هذا في رموز ) لكود آر إس (7,3). الحدود المولدة هي إذا كانت متعددة حدود الرسالة هي ، فسيتم ترميز كلمة رمزية منهجية على النحو التالي: قد تؤدي الأخطاء في الإرسال إلى استلام هذا بدلاً من ذلك: يتم حساب المتلازمات عن طريق تقييم r عند قوى α : إنتاج النظام
لحساب قيم الخطأ، قم بتطبيق :
ومن ناحية أخرى، الطرح من متعددة الحدود المستلمة r (x) تعيد إنتاج كلمة المرور الأصلية s.
Syndromes = trim(Synd);
كذلك، % If all syndromes are zeros (perfectly divisible) there are no errors
if isempty(Syndromes.x)
% Remove leading zeros from Galois array
function gt = trim(g)
if len < k
- xpad = [zeros(1, k - len) x]؛
- end
- end
g = g0 - c;
- % Check if the degree of remainder(x) is less than max_errors
- if all(remainder(1:end - max_errors) == 0)
- break;
التركيبة
إضافةً إلى ذلك، الرسالة المرسلة ، يُنظر إليها على أنها معاملات متعددة الحدود
ومن ناحية أخرى، سيكون المعامل e i صفرًا إذا لم يكن هناك خطأ عند تلك القوة لـ x، وغير صفر إذا كان هناك خطأ. إذا كانت هناك أخطاء ν عند قوى مميزة i k لـ x، إذن
إضافةً إلى ذلك، نتيجة لإجراء ترميز ريد–سولومون، فإن s (x) قابلة للقسمة على متعددة الحدود المولدة حيث α هو عنصر بدائي.
علاوةً على ذلك، يتم إتلاف الحدود المنقولة أثناء النقل بسبب خطأ الحدود لإنتاج الحدود المستلمة
ومن جهة أخرى، الهدف من فك التشفير هو العثور على عدد الأخطاء (ν)، ومواضع الأخطاء (i k)، وقيم الأخطاء في تلك المواضع (e i k). ومن تلك القيم، يمكن حساب e (x) وطرحه من r (x) للحصول على الرسالة المرسلة في الأصل s (x).
في هذا الإطار، نظرًا لأن s (x) مضاعف للمولد g (x)، فمن الطبيعي أن «يرث» كل جذوره: لذلك،
متعدد الحدود لتحديد الخطأ
قم بتعريف متعددة حدود تحديد الخطأ على أنها
وعلى صعيد آخر، أصبحت هذه المجاميع الآن تعادل قيم المتلازمة، والتي نعرفها ويمكننا استبدالها. وهذا يقلل بالتالي إلى
- يترك يكون أي عدد صحيح بحيث . اضرب كلا الطرفين في ، وسيظل صفرًا:
- المجموع لـ k = 1 إلى ν، وسيظل صفرًا:
- اجمع كل مصطلح في مجموع خاص به:
- استخرج القيم الثابتة لـ التي لا تتأثر بالمجموع:
وفي هذا السياق، هناك علاقة تكرار خطية تُنتج نظامًا من المعادلات الخطية. حل هذه المعادلات يُحدد مواقع الخطأ Xk.
من جانب آخر، أصفار هي مقلوبات . يتبع هذا من بناء تدوين المنتج أعلاه، لأنه إذا ، ثم يصبح أحد الحدود المضروبة صفرًا، ، مما يجعل تقييم متعدد الحدود بأكمله يساوي الصفر:
فك التشفير
الآن الجزء المتعلق بفك التشفير:
وفي هذا الصدد، function [decoded, error_pos, error_mag, g, S] = rsDecoder(encoded, m, prim_poly, n, k)
استيفاء لاغرانج لـ ل ل
يولد و حتى درجة ، مثلًا
من جانب آخر، لمضاعفة كثيرات الحدود التي أنشأها ويلش بيرليكامب، قسّم Q (x) و E (x) على المعامل الأكثر أهمية لـ E (x) = 708.
- Recalculate where to correct resulting in the corrected codeword:
- انظر كذلك
- رمز بي سي إتش
- الملاحظات
- المراجع
- وصلات خارجية
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
مُشفِّر
- نقدم هنا تنفيذ ماتلاب بسيطًا للمُشفِّر.
- 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
فك التشفير الناعم
مثال ماتلاب
من جهة ثانية، إن طرق فك التشفير الجبري الموصوفة أعلاه هي طرق اتخاذ قرار صعب، مما يعني أنه بالنسبة لكل رمز يتم اتخاذ قرار صعب حول قيمته. مثلًا، يمكن لجهاز فك التشفير أن يربط مع كل رمز قيمة إضافية تتوافق مع ثقة جهاز فك تشفير القناة في صحة الرمز. لقد أدى ظهور ، التي تستعمل أساليب فك تشفير انتشار الاعتقاد بقرار ناعم متكرر لتحقيق أداء تصحيح الخطأ بالقرب من الحد النظري، إلى تحفيز الاهتمام بتطبيق فك تشفير القرار الناعم على الرموز الجبرية التقليدية. في عام 2003، قدم رالف كويتر وألكسندر فاردي خوارزمية فك تشفير القائمة الجبرية ذات القرار الناعم في زمن متعدد الحدود لرموز ريد–سولومون، والتي كانت تعتمد على العمل الذي قام به سودان وجورو سوامي. في سنة 2016، نشر ستيفن جيه فرانك وجوزيف إتش تايلور فك تشفير القرار الناعم الجديد.
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
alpha = gf(2, m, prim_poly);
% Get the Reed-Solomon generating polynomial g(x)
end
- % Update r0, r1, g0, g1 and remove leading zeros
- r0 = trim(r1); r1 = trim(remainder);
- g0 = g1; g1 = g;
- end
- % Remove leading zeros
حساب مواقع الخطأ
من جانب آخر، احسب i k عن طريق أخذ قاعدة اللوغاريتم من X ك. يتم ذلك عادةً باستخدام جدول بحث محسوب مسبقًا.
التنفيذات
وفي هذا السياق، FEC library in C by Phil Karn (aka KA9Q) includes Reed–Solomon codec, both arbitrary and optimized (223,255) version
decoded = orig_vals(1:k);
- error_pos = []؛
- error_mag = []؛
- g = []؛
- S = Synd;
- return;
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)
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)
فك تشفير بيرليكامب ويلش
في هذا الإطار، في سنة 1986، تم تطوير فك تشفير معروف باسم تشفير قادر على استعادة متعددة الحدود الأصلية للرسالة فضلًا عن متعددة حدود «محدد» الخطأ التي تنتج أصفارًا لقيم الإدخال التي تتوافق مع الأخطاء، مع تعقيد زمني ، حيث هو عدد القيم في الرسالة. يتم فيما بعد استخدام الحدود المستردة لاستعادة (إعادة الحساب حسب الحاجة) الرسالة الأصلية.
محددات الأخطاء وقيم الأخطاء
من جانب آخر، تعطي المتلازمات نظامًا من معادلات في مجهولين 2 ν، ولكن نظام المعادلات هذا غير خطي في X k وليس له حل واضح. ومع ذلك، إذا كانت قيمة X k معروفة (انظر أدناه)، فإن معادلات المتلازمة توفر نظامًا خطيًا من المعادلات والتي يمكن حلها بسهولة لقيم خطأ Y k.
هذا التعريف لقيم المتلازمة يعادل التعريف السابق منذ .
وفي هذا الصدد، في متغير هذه الخوارزمية حيث تكون مواقع الأخطاء معروفة بالفعل (عندما يتم استخدامها )، فهذه هي النهاية. إن مواقع الخطأ (X k) معروفة بالفعل من خلال بعض الطرق الأخرى (مثلًا، في إرسال FM، يمكن تحديد الأقسام التي كان فيها تدفق البتات غير واضح أو تم التغلب عليه بالتداخل بشكل احتمالي من تحليل التردد). في هذا السيناريو، ما يصل إلى يمكن تصحيح الأخطاء.
كذلك، وبالتالي، فإن المشكلة تكمن في إيجاد Xk، لأنه عندها ستكون المصفوفة الموجودة في أقصى اليسار معروفة، ويمكن ضرب كلا جانبي المعادلة في معكوسها، مما ينتج عنه Yk.
في هذا الإطار، ومن ثم يمكن كتابة المتلازمات من حيث مواقع الأخطاء وقيم الأخطاء هذه على النحو التالي:
وفي السياق ذاته، من أجل الراحة، قم بتحديد مواقع الأخطاء X k وقيم الأخطاء Y k على النحو التالي
وفي هذا الصدد، يعمل باقي الخوارزمية على تحديد الأخطاء وسيتطلب قيم متلازمة تصل إلى ، بدلا من مجرد المستعملة حتى الآن. لهذا السبب، هناك حاجة إلى إضافة عدد مضاعف من رموز تصحيح الأخطاء مقارنة بالعدد الذي يمكن تصحيحه دون معرفة مواقعها.
نقل البيانات
ومن ناحية أخرى، تُستعمل أكواد ريد–سولومون كذلك في أنظمة الخط المشترك الرقمي الخاصة بـ سي سي إس دي إس كشكل من أشكال تصحيح الأخطاء الأمامية.
وفي السياق ذاته، إن أي مجموعة من الكلمات الرمزية (K) التي تم تلقيها في الطرف الآخر تكون كافية لإعادة بناء كل الكلمات الرمزية (N). يتم عادةً ضبط معدل الترميز على 1/2 ما لم يكن من الممكن نمذجة احتمالية محو القناة بشكل مناسب ورؤيتها أقل. في الختام، يكون N عادةً 2 K، مما يعني أنه يجب استلام نصف جميع كلمات المرور المرسلة على الأقل من أجل إعادة بناء جميع كلمات المرور المرسلة.
إضافةً إلى ذلك، يمكن استخدام الأشكال المتخصصة من رموز ريد–سولومون، وتحديدًا كوشي-آر إس و فاندرموند-آر إس، للتغلب على الطبيعة غير الموثوقة لنقل البيانات عبر قنوات المسح. تفترض عملية الترميز رمز آر إس (N، K) مما يؤدي إلى إنشاء N كلمة رمزية بطول N رمز، كل منها يخزن K رمزًا من البيانات، والتي يتم إرسالها فيما بعد عبر قناة مسح.
% Add leading zeros
len = length(x);
function xpad = pad(x, k)
gx = g.x;
end
gt = gf(gx(find(gx, 1) : end), g.m, g.prim_poly);
[~, remainder] = deconv(msg_padded, g_x);
% Now return the message with the redundant information
encoded = msg_padded - remainder;
errors(error_pos.x) = error_mag.x;
% Bring this vector to the galois field
فك التشفير خارج حدود تصحيح الخطأ
ومن ناحية أخرى، تنص على أن الحد الأدنى للمسافة لكتلة رمزية خطية بحجم يحدها الحد العلوي . كان من المفهوم عادةً أن المسافة تحد من قدرة تصحيح الخطأ إلى . يحقق كود ريد–سولومون هذا الحد بالمساواة، وبالتالي يمكنه تصحيح ما يصل إلى أخطاء. ومع ذلك، فإن حد تصحيح الخطأ هذا ليس دقيقًا.
وفي هذا الصدد، في سنة 2023، بناءً على ثلاثة أحداث مثيرة، أظهر منظرو الترميز أن أكواد ريد–سولومون المحددة عبر نقاط تقييم عشوائية يمكنها في الواقع تحقيق قدرة (ما يصل إلى أخطاء) عبر أبجديات ذات حجم خطي باحتمالية عالية. ومع ذلك، فإن هذه النتيجة تركيبية وليست خوارزمية.
إضافةً إلى ذلك، في سنة 1999، نشر مادو سودان في معهد ماساتشوستس للتكنولوجيا «تحسين فك رموز ريد–سولومون والرموز الجبرية الهندسية» حيث قدموا خوارزمية سمحت بتصحيح الأخطاء التي تتجاوز نصف المسافة الدنيا للرمز. وهذا ينطبق على رموز ريد–سولومون وبشكل عام على الرموز الهندسية الجبرية. تنتج هذه الخوارزمية قائمة من الكلمات المشفرة (وهي خوارزمية فك تشفير القائمة) وتعتمد على الاستيفاء والتحليل إلى عوامل متعددة الحدود على وامتداداتها.
فك تشفير عرض بي سي إتش
علاوةً على ذلك، تستعمل أجهزة فك التشفير الموصوفة في هذا القسم عرض بي سي إتش لكلمة رمزية كسلسلة من المعاملات. وتستعمل متعددة حدود مولدة ثابتة معروفة لكلٍّ من جهاز التشفير وجهاز فك التشفير.
الرمز الشريطي
علاوةً على ذلك، يعد ترميز ريد–سولومون أقل شيوعًا في الرموز الشريطية أحادية البعد، ولكن يتم استخدامه بواسطة رمزية .
إضافةً إلى ذلك، تستعمل جميع الرموز الشريطية ثنائية الأبعاد على وجه التقريب مثل بي دي إف-417 و ورمز مصفوفي ورمز استجابة سريعة و تصحيح خطأ ريد–سولومون للسماح بالقراءة الصحيحة حتى في حالة تلف جزء من الرمز الشريطي. عندما لا يتمكن ماسح الباركود من التعرف على رمز الباركود، فسوف يعامله على أنه مسح.
for idx = 1 : size_error
- e = alpha .^ (idx * (n - error_pos.x));
- err = e.x;
- er(idx, :) = err;
- end
الأمثلة
باستخدام آر إس (7,3)، وجي إف (929)، ومجموعة نقاط التقييم
إذا كانت الرسالة متعددة الحدود هي
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
% Solve the linear system
error_mag = (gf(er, m, prim_poly) \ gf(b, m, prim_poly))';
% Put the error magnitude on the error vector
إيجاد جذور متعددة حدود تحديد الخطأ
في هذا الإطار، استعمل المعاملات Λ التي وجدتها في الخطوة الأخيرة لبناء متعدد حدود موقع الخطأ. يمكن العثور على جذور متعددة الحدود الخاصة بموقع الخطأ من خلال البحث الشامل. محددات الخطأ X k هي مقلوبات تلك الجذور. يمكن عكس ترتيب معاملات كثيرة الحدود لموقع الخطأ، وفي هذه الحالة تكون جذور كثيرة الحدود المعكوسة هي محددات الخطأ (ليس متبادلهما ). يعد تنفيذًا فعالًا لهذه الخطوة.
المعلومات والدروس التعليمية
وعلى صعيد آخر، Introduction to ريد–سولومون codes: principles, architecture and implementation (CMU)
فك تشفير جاو
ومن جهة أخرى، في سنة 2002، تم تطوير فك تشفير محسن بواسطة شوهونج جاو، استنادًا إلى خوارزمية إقليدس الموسعة.
الأمثلة
وحدة فك ترميز بيترسون-جورنشتاين-زيرلر
من جهة ثانية، قام دانييل جورنشتاين ونيل زيرلر بتطوير جهاز فك تشفير تم وصفه في تقرير صادر عن مختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا بواسطة زيرلر في يناير 1960 وفي وقت لاحق في ورقة بحثية في يونيو 1961. تم وصف فك تشفير جورنشتاين-زيرلر والعمل المرتبط به على رموز بي سي إتش في كتاب رموز تصحيح الأخطاء بقلم و. ويزلي بيترسون (1961).
الطرح من كلا الجانبين العائدات
كذلك، تذكر أن j تم اختياره ليكون أي عدد صحيح بين 1 و v شاملًا، وهذا التكافؤ صحيح لجميع هذه القيم. وبالتالي، لدينا معادلة خطية، وليس معادلة واحدة فقط. وبالتالي، يمكن حل نظام المعادلات الخطية هذا لمعاملات Λ i لمتعددة حدود موقع الخطأ: يفترض ما سبق أن فك التشفير يعرف عدد الأخطاء ν، ولكن هذا العدد لم يتم تحديده بعد. لا يقوم فك التشفير PGZ بتحديد ν بشكل مباشر، بل يبحث عنه عن طريق تجربة القيم المتعاقبة. يفترض فك التشفير أولاً أكبر قيمة للتجربة ν ويقوم بإعداد النظام الخطي لتلك القيمة. إذا كان من الممكن حل المعادلات (أي أن محدد المصفوفة ليس صفرًا)، فإن قيمة التجربة هي عدد الأخطاء. إذا لم يكن من الممكن حل النظام الخطي، يتم تقليل التجربة ν بمقدار واحد ويتم فحص النظام الأصغر التالي.
decoded = orig_vals(1:k);
return;
error_mag = []؛
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
إجراء الترميز المنهجي
مع تجاهل الأصفار الأولية، الصف الأخير = .
لما يلي -مصفوفة مع عناصر من :
من جهة ثانية، يمكن تعديل إجراء الترميز لعرض بي سي إتش لرموز ريد–سولومون لإنتاج إجراء ترميز منهجي، حيث تحتوي كل كلمة رمزية على الرسالة كبادئة، وتضيف ببساطة رموز تصحيح الأخطاء كلاحقة. هنا، بدلا من الإرسال يقوم المشفر بإنشاء الحدود المنقولة بحيث تكون معاملات أكبر أحاديات الحدود تساوي المعاملات المقابلة لـ ، ومعاملات الدرجة الأدنى لـ يتم اختيارهم بالضبط بهذه الطريقة يصبح قابلا للقسمة على . ثم معاملات هي تسلسل جزئي لمعاملات . للحصول على كود منهجي بشكل عام، نقوم بإنشاء رسالة متعددة الحدود من خلال تفسير الرسالة على أنها تسلسل معاملاتها.
وفي هذا السياق، رسميًا، يتم البناء عن طريق الضرب بواسطة لإفساح المجال ل رموز التحقق، وتقسيم هذا المنتج على لإيجاد الباقي، ثم تعويض هذا الباقي عن طريق طرحه. ال يتم إنشاء رموز التحقق عن طريق حساب الباقي :
في هذا الإطار، هذه الوظيفة هي عبارة عن رسم خطي. لتوليد مصفوفة الترميز النظامية المقابلة G، قم بتعيين المصفوفة الفرعية المربعة اليسرى لـ G إلى مصفوفة الهوية ثم قم بترميز كل صف:
ومن ناحية أخرى، الباقي حاصل على درجة علمية على الأكثر ، في حين أن معاملات في كثير الحدود هي صفر. لذلك، التعريف التالي للكلمة الرمزية لديه الخاصية التي هي الأولى المعاملات متطابقة مع معاملات : ونتيجة لذلك، فإن الكلمات المشفرة هي في الواقع عناصر من أي أنها قابلة للقسمة على متعددة الحدود المولدة :
حساب قيم الخطأ
علاوةً على ذلك، بمجرد معرفة مواقع الخطأ X k، يمكن تحديد قيم الخطأ. يمكن القيام بذلك عن طريق الحل المباشر لـ Y k في مصفوفة معادلات الخطأ المذكورة أعلاه، أو باستخدام .
فك تشفير العرض الأصلي لريد سولومون
من جهة ثانية، تستعمل أجهزة فك التشفير الموصوفة في هذا القسم مفهوم ريد سولومون الأصلي للكلمة الرمزية كتسلسل من قيم متعددة الحدود، حيث تعتمد متعددة الحدود على الرسالة المراد تشفيرها. تستعمل كل من وحدة التشفير ووحدة فك التشفير نفس مجموعة القيم الثابتة، وتستعيد وحدة فك التشفير متعددة حدود التشفير (واختياريًا متعددة حدود تحديد موقع الخطأ) من الرسالة المستلمة.
الخصائص
علاوةً على ذلك، يمكن وصف حد الخطأ النظري من خلال الصيغة التالية لقناة أوجن لإبدال بإزاحة التردد: ولخطط التعديل الأخرى: أين ، ، ، هو معدل خطأ الرمز في حالة أوجن غير المشفرة و هو ترتيب التعديل.
من جانب آخر، إن كون قانون ريد–سولومون دوريًا أم لا يعتمد على التفاصيل الدقيقة للبناء. في وجهة النظر الأصلية لريد وسولومون، حيث تكون الكلمات الرمزية هي قيم كثيرة الحدود، يمكن للمرء اختيار تسلسل نقاط التقييم بطريقة تجعل الكود دوريًا. وعلى وجه الخصوص، إذا هو للحقل ، إذن حسب التعريف فإن جميع العناصر غير الصفرية لـ خذ النموذج ل ، أين . كل كثيرة حدود زيادة يؤدي إلى ظهور كلمة مرور . منذ الوظيفة هي كذلك كثيرة حدود من نفس الدرجة، هذه الدالة تؤدي إلى كلمة رمزية ؛ منذ صحيح أن هذه الكلمة الرمزية هي التحول الدوري إلى اليسار للكلمة الرمزية الأصلية المشتقة من . وبالتالي فإن اختيار تسلسل من قوى الجذر البدائية كنقط تقييم يجعل العرض الأصلي لرمز ريد–سولومون دوريًا. تكون رموز ريد–سولومون في عرض بي سي إتش دورية دائمًا لأن رموز بي سي إتش دورية.
وفي هذا السياق، رمز ريد–سولومون هو رمز [ n، k، n − k + 1]؛ بمعنى آخر، هو رمز كتلة خطي بطول n (على F) مع البعد k ومسافة هامينج الدنيا يعتبر كود ريد–سولومون مثاليًا بمعنى أن الحد الأدنى للمسافة له أقصى قيمة ممكنة لكود خطي بحجم (n، ك)؛ وهذا ما يُعرف باسم . يُطلق على هذا الرمز كذلك اسم .
ومن ناحية أخرى، إن خصائص كود ريد–سولومون التي تمت مناقشتها أعلاه تجعلها مناسبة بشكل خاص للتطبيقات التي تحدث فيها أخطاء في الانفجارات. يرجع ذلك إلى أنه لا يهم بالنسبة للكود عدد البتات الموجودة في الرمز التي تحتوي على أخطاء - إذا كانت بتات متعددة في رمز تالفة، فإن هذا يعد خطأ واحدًا فقط. وعلى العكس من ذلك، إذا لم يكن تدفق البيانات يتميز بتفجر الأخطاء أو الانقطاعات ولكن بأخطاء بت واحدة عشوائية، فإن رمز ريد–سولومون عادة ما يكون خيارًا سيئًا مقارنة بالرمز الثنائي.
وعلى صعيد آخر، يتم تحديد قدرة تصحيح الخطأ لرمز ريد–سولومون من خلال المسافة الدنيا، أو على نحو مكافئ، من خلال ، مقياس التكرار في الكتلة. إذا لم تكن مواقع رموز الخطأ معروفة مسبقًا، فيمكن لكود ريد–سولومون تصحيح ما يصل إلى الرموز الخاطئة، أي أنه يمكنه تصحيح نصف عدد الأخطاء التي تحتوي على رموز زائدة تمت إضافتها إلى الكتلة. في بعض الأحيان تكون مواقع الأخطاء معروفة مسبقًا (مثلًا، «المعلومات الجانبية» في نسبة الإشارة إلى الضوضاء في جهاز إزالة التعديل) - وتسمى هذه بالمحو. يمكن لرمز ريد–سولومون (مثل أي رمز إم دي إس) تصحيح ضعف عدد المحو مقارنة بالأخطاء، ويمكن تصحيح أي مجموعة من الأخطاء والمحو طالما تم استيفاء العلاقة ، حيث هو عدد الأخطاء و هو عدد المحو في الكتلة.
في هذا الإطار، بالنسبة للاستخدامات العملية لرموز ريد–سولومون، من الشائع استخدام حقل محدود مع عناصر. في هذه الحالة، يمكن تمثيل كل رمز على أنه قيمة البت. يرسل المرسل نقاط البيانات ككتل مشفرة، وعدد الرموز في الكتلة المشفرة هو . وبالتالي، فإن كود ريد–سولومون الذي يعمل على رموز مكونة من 8 بتات لديه الرموز لكل كتلة. (هذه قيمة شائعة جدًا نظرًا لانتشار أنظمة الكمبيوتر الموجهة للبايتات.) الرقم ، مع ، عدد رموز البيانات في الكتلة هو معلمة تصميم. الكود المستعمل بشكل شائع يشفر رموز بيانات مكونة من ثمانية بتات إلى جانب 32 رمز تكافؤ مكون من ثمانية بتات في - كتلة الرمز؛ يُشار إليها باسم الكود، وهو قادر على تصحيح ما يصل إلى 16 خطأ رمزي لكل كتلة.
وفي هذا الصدد، إن شفرة ريد–سولومون، مثل ، هي شفرة شفافة. وهذا يعني أنه إذا تم عكس رموز القناة في مكان ما على طول الخط، فسوف تستمر أجهزة فك التشفير في العمل. وستكون النتيجة عكس البيانات الأصلية. ومع ذلك، يفقد كود ريد–سولومون شفافيته عندما يتم اختصار الكود (انظر الملاحظات في نهاية هذا القسم). يجب ملء البتات «المفقودة» في الكود المختصر إما بالأصفار أو الواحدات، اعتمادًا على ما إذا كانت البيانات مكملة أم لا. (بعبارة أخرى، إذا تم عكس الرموز، فيجب عكس التعبئة الصفرية إلى تعبئة واحدة.) لهذا السبب، من الضروري حل معنى البيانات (أي، صحيحة أو متممة) قبل فك تشفير ريد–سولومون.
فك التشفير باستخدام تحويل فورييه المنفصل
من جهة ثانية، قم بتحويل r (x) إلى R (x) باستخدام تحويل فورييه المنفصل. نظرًا لأن حساب تحويل فورييه المنفصل هو نفس حساب المتلازمات، فإن معاملات t لـ R (x) و E (x) هي نفس المتلازمات:
وفي هذا السياق، يمكن استخدام تحويل فورييه المنفصل لفك التشفير. لتجنب التعارض مع أسماء المتلازمات، دع 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).
ومن ناحية أخرى، ليكن v = عدد الأخطاء. توليد E (x) باستخدام المعاملات المعروفة ل ، متعدد الحدود لتحديد الخطأ، وهذه الصيغ
من جانب آخر، يستعمل خلال كمتلازمات (إنها نفس الشيء) وتوليد متعدد الحدود لتحديد الخطأ باستخدام الأساليب من أي من أجهزة فك التشفير المذكورة أعلاه.
وفي هذا الصدد، ثم احسب C (x) = R (x) − E (x) واستعمل التحويل العكسي (الاستيفاء متعدد الحدود) لـ C (x) لإنتاج c (x).
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);
فك تشفير بيرليكامب-ماسي
إضافةً إلى ذلك، هي إجراء تكراري بديل للعثور على متعدد الحدود لتحديد الخطأ. أثناء كل تكرار، يقوم بحساب التناقض بناءً على حالة حالية من Λ(x) مع عدد مفترض من الأخطاء e : ثم يقوم بتعديل Λ(x) و e بحيث يصبح Δ المعاد حسابه صفرًا. تحتوي المقالة «» على وصف تفصيلي للإجراء. في المثال التالي، يتم استخدام C (x) لتمثيل Λ(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)
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟