كود ريد سليمان

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



لذلك ، على سبيل المثال ، بالنسبة لرمز Reed-Solomon معين (رمز الكمبيوتر الشخصي) ، يجب عليك تعيين:

• طول n من كلمة المرور (كتلة) ؛
• عدد المعلومات k ورموز الاختيار Nk ؛
• متعدد الحدود p (x) غير قابل للاختزال يحدد مجال محدود GF (2 ^r ) ؛
• العنصر البدائي α لحقل محدود ؛
• توليد كثير الحدود g (x) ؛
• المعلمة j من الكود ؛
• التشذير المستخدم
• تسلسل إرسال كلمات مشفرة أو رموز إلى القناة وبعضها الآخر.

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

وصف رمز الكمبيوتر وخصائصه

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



يمكن تفسير أكواد Reed - Solomon (رمز RS) على أنها رموز BCH غير ثنائية (Bose - Chowdhury - Hawkingham) ، وقيم رموز الرموز التي يتم أخذها من حقل GF (2 ^r ) ، أي يتم عرض رموز المعلومات كعنصر منفصل في الحقل. أكواد Reed-Solomon هي أكواد دورية خطية غير ثنائية منتظمة تكون رموزها عبارة عن تسلسلات r-bit ، حيث r هي عدد صحيح موجب أكبر من 1.



يتم تعريف رموز Reed-Solomon (n ، k) على رموز r بت لكل n و ك ، والتي:

0 <ك <ن <2 ^ص + 2 ، أين

k هو عدد رموز المعلومات المراد تشفيرها ،

n هو عدد رموز الشفرة في الكتلة المشفرة.



بالنسبة لمعظم (ن ، ك) أكواد ريد-سولومون ؛ (n، k) = (2 ^r –1، 2 ^r –1–2 ∙ t) ، حيث

t هو عدد رموز الخطأ التي يمكن للشفرة تصحيحها ، و

n - k = 2t هو عدد رموز الفحص.



يحتوي كود Reed-Solomon على أكبر مسافة ممكنة (عدد الأحرف التي تميز التسلسلات) الممكنة لكود خطي. بالنسبة إلى أكواد Reed - Solomon ، يتم تحديد الحد الأدنى للمسافة على النحو التالي: dmin = n - k +1.



التعريف . رمز الكمبيوتر الشخصي فوق الحقل GF (q = ^m ) ، بطول الكتلة n = q ^m-1 ، تصحيح أخطاء t ، هو مجموعة جميع كلمات التشفير u _(n) عبر GF (q) والتي لها 2 طن من مكونات الطيف المتتالية بأرقام$$$m_0,m_0 +1,...,m_0+2t-1$ تساوي 0.



حقيقة أن 2t قوى متتالية لـ α هي جذور لتوليد كثير الحدود g (x) أو أن الطيف يحتوي على 2t من مكونات صفرية متتالية هي خاصية مهمة للشفرة التي تسمح بتصحيح أخطاء t.



كثير حدود المعلوماتQ. يحدد نص الرسالة ، الذي ينقسم إلى كتل (كلمات) ذات طول ثابت ومرقمة. هذا ما يجب نقله في نظام الاتصال.

توليد كثير الحدودg (x) من رمز PC هو متعدد الحدود الذي يحول كثيرات حدود المعلومات (الرسائل) إلى كلمات مشفرة بضرب Q · g (x) = = u _(n) على GF (q). يسمح لك



التحقق متعدد الحدود h (x) بإثبات وجود أحرف مشوهة في الكلمة.

كثير الحدود المتلازمي S (z). كثير حدود يحتوي على مكونات مقابلة للمواقف الخاطئة. محسوبة لكل كلمة تلقاها وحدة فك الترميز.

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



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

متعدد الحدود من الخطأ القيم Ω (ض) ≡Λ (ض) · S (ض) (modz ^2T ) تعادل مودولو ض ^2T مع المنتج من متعدد الحدود من تحديد مواقع الخطأ متعدد الحدود المتلازمة.



كثير حدود غير قابل للاختزال للمجال p (x). لا توجد الحقول المحددة لأي عدد من العناصر ، ولكن فقط إذا كان عدد العناصر هو p أولي أو قوة q = p ^mرقم اولي. في الحالة الأولى، ويسمى حقل بسيطة (عناصرها هي بقايا من أرقام MODULO رئيس وع)، في الثانية، هو امتداد لحقل لرئيس المقابلة (عناصر ف لها كثيرات الحدود من درجة م-1 أو أقل هي بقايا متعددو الحدود MODULO و ص متعدد الحدود (خ) من الدرجة م)



كثير الحدود البدائي . إذا كان جذر كثير الحدود غير القابل للاختزال للحقل هو عنصر بدائي α ، فإن p (x) تسمى كثيرة الحدود البدائية غير القابلة للاختزال .



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



الجدول 2 - خصائص عناصر المجال المحدد للتمديد GF (2 ⁴ ) ، متعدد الحدود غير القابل للاختزال p (x) = x ⁴ + x + 1 ، العنصر البدائي α = 0010 = 2 ₁₀





مثال 1 . على حقل محدود GF (2 ⁴ ) ، يتم إعطاء مجال متعدد الحدود غير قابل للاختزال p (x) = x ⁴ + x + 1 ، عنصر بدائي α = 2 ، و (n ، k) - شفرة Reed-Solomon (RS-code). مسافة الشفرة لهذا الرمز هي d = n - k + 1 = 7. يمكن لهذا الرمز تصحيح ما يصل إلى ثلاثة أخطاء في الكتلة (كلمة الرمز) للرسالة.



متعدد الحدود g (z) للشفرة له درجة m = nk = 15-9 = 6 (جذوره هي 6 عناصر من الحقل GF (2 ⁴ ) في التدوين العشري ، أي العناصر 2 ، 3 ، 4 ، 5 ، 6 ، 7) و يتم تحديده من خلال النسبة ، أي متعدد الحدود في z مع معاملات (عناصر) من GF (2 ⁴ ) في التمثيل العشري لـ i = 1 (1) 6. في كود الكمبيوتر المدروس 2 ⁹ = 512 كلمة مشفرة.

ترميز رسائل الكمبيوتر

في الجدول II ، هذه الجذور لها أيضًا تمثيل للقوة $$$α^1=2, α^2=3,...,α^6=7$...





هنا z هو متغير مجرد ، و α هو عنصر بدائي للحقل ، من خلال صلاحياته يتم التعبير عن جميع عناصر المجال (16). يستخدم التمثيل متعدد المصطلحات لعناصر الحقل المتغير x.

يتم إجراء حساب متعدد الحدود g (x) = A B من رمز الكمبيوتر الشخصي في أجزاء (ثلاثة أقواس لكل منهما):





تمثيل المتجه (من خلال المعامِلات g (z) بواسطة عناصر الحقل في التمثيل العشري) لكثير الحدود المولِّد له الشكل



g (z) = G _<7> = (1 ، 11 ، 15 ، 5 ، 7 ، 10 ، 7).



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



يحتوي ناقل المعلومات (كلمة الرسالة) على مكونات k من (n ، k). في المثال ك = 9 ، المتجه مكون من 9 مكونات ، جميع المكونات عبارة عن عناصر حقل GF (2 ⁴ ) في التمثيل العشري Q _<9> = (11 ، 13 ، 9 ، 6 ، 7 ، 15 ، 14 ، 12 ، 10) ...



تتكون كلمة السر u من هذا المتجه_<15> متجه يحتوي على 15 مكونًا. كلمات الكود ، مثل الرموز نفسها ، تكون منهجية وغير منتظمة. يتم الحصول على كلمة رمز غير منهجية بضرب متجه المعلومات Q في المتجه المقابل لتوليد كثير الحدود



بعد التحولات ، نحصل على كلمة رمز غير منهجية (متجه) في الشكل

Q · g = <11 ، 15 ، 3 ، 9 ، 6 ، 14 ، 7 ، 5 ، 12 ، 15 ، 14 ، 3 ، 3 ، 7 ، 1>.



في الترميز المنهجي ، يتم تمثيل الرسالة (متجه المعلومات) بواسطة متعدد الحدود Q (z) في الشكل Q (z) = q (z) g (z) + R (z) ، حيث درجة degR (z) <m = 6. بعد ذلك ، إلى يتم تعيين المتجه Q على اليمين الباقي R (كل ذلك في شكل عشري). يتم ذلك على هذا النحو.



يتم إزاحة كثير الحدود Q نحو الأرقام الأعلى بالقيمة m = n - k ، والتي تتحقق بضرب Q (z) في Z ^{n - k} (في المثال Z ^{n - k} = Z ⁶ ) وبعد التحول ، القسمة Q (z) Z ^{ن - ك} من ز (ض). نتيجة لذلك ، أوجد باقي القسمة R (z). يتم تنفيذ جميع العمليات في مجال GF (2 ⁴ )



(11 ، 13 ، 9 ، 6 ، 7 ، 15 ، 14 ، 12 ، 10 ، 0 ، 0 ، 0 ، 0 ، 0 ، 0) =

= (1 ، 11 ، 15 ، 5 ، 7 ، 10 ، 7) ( 11 ، 15 ، 9 ، 10 ، 12 ، 10 ، 10 ، 10 ، 10 ، 3) + (1 ، 2 ، 3 ، 7 ، 13 ، 9) = G · S + R.



يتم حساب باقي قسمة كثيرات الحدود بالطريقة المعتادة ( انظر الزاوية هنا مثال 6 ). يتم تنفيذ القسمة وفقًا للنمط: دع Q = 26 ، g (z) = 7 ، ثم 26 = 7 3 + R (z) ، R (z) = 26-7 3 = 26-21 = 5. حساب الباقي R (z ) على تقسيم كثيرات الحدود. نخصص الباقي R للمتجه Q على اليمين ،



ونحصل على u _<15> - كلمة مشفرة في شكل نظامي. يحتوي هذا العرض بوضوح على رسالة معلومات في وحدات البت عالية الترتيب من كلمة الشفرة



u _<15> = (11،13،9،6،7،15،14،12،10؛ 1، 2، 3، 7، 13، 9)



يتم ترقيم أرقام المتجه من اليمين إلى اليسار من 0 (1) 14. البتات الستة الأقل أهمية على اليمين هي وحدات التحقق.

فك رموز Reed-Solomon

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



ينفذ جهاز فك ترميز الكمبيوتر الشخصي خمس خطوات في حلقة فك التشفير ، وهي:

1. تم العثور على أخطاء في حساب متلازمة كثير الحدود (معاملاتها).
2. تم حل معادلة Pade الرئيسية - حساب قيم الخطأ ومواضعها في المواقع المقابلة.
3. تم تنفيذ إجراء Chen - إيجاد جذور كثير الحدود لمحدد الخطأ.
4. يتم استخدام خوارزمية فورني لحساب قيمة الخطأ.
5. يتم إجراء تصحيحات للكلمات البرمجية المشوهة ؛

تنتهي الدورة باستخراج الرسالة من كلمات الكود (إزالة الكود).



حساب المتلازمة.



يُعد توليد متلازمة من كلمة الشفرة المستلمة الخطوة الأولى في عملية

فك التشفير. يتم هنا حساب المتلازمات وتحديد ما إذا كانت هناك أخطاء في كلمة المرور المستلمة أم لا ، ويمكن تنظيم



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

كشف التشويه

متلازمة $$$S = (S_v,S_{v+1},...,S_{m+v-1})$أين $$$v∊{0, 1}$يتم تحديد المتجه بشكل تسلسلي لكل كلمة من كلمات التشفير التي يستقبلها مفكك الشفرة عند مدخلاته. مع قيم صفرية لمكونات ناقل المتلازمة$$$Sj = 0, j=v,v+1,...,m + v - 1$، يرى مفكك الشفرة أنه لا يوجد خطأ في الكلمة المستلمة. إذا كان لواحد على الأقل$$$j≥1,Sj≠0$، ثم يخلص مفكك الشفرة إلى وجود أخطاء في متجه الشفرة ويواصل تحديدها ، وهي الخطوة الأولى في عملية وحدة فك التشفير.



يمكن أن يؤدي حساب

الضرب متعدد الحدود المتلازم على جانب الاستقبال لكلمة الرمز C بواسطة مصفوفة اختبار التكافؤ H إلى نتيجتين:

• ناقل المتلازمة S = 0 ، والذي يتوافق مع عدم وجود أخطاء في المتجه C ؛
• ناقل متلازمة S ≠ 0 ، مما يعني وجود أخطاء (واحد أو أكثر) في مكونات المتجه C.

الحالة الثانية ذات أهمية.



يتم تمثيل متجه الكود مع الأخطاء على أنه C (E) = C + E ، E هو متجه الخطأ. ثم$$$(C +E)H^t = CH^t + EH^t = 0 + EH^t = S$



يتم تحديد مكونات Sj للمتلازمة إما عن طريق علاقة الجمع

لـ n = q-1 و j = 1 (1) m = nk ، أو بواسطة مخطط هورنر:



$$$S_j = C_0 +α^j(C_1 +α^j(C_2 +...+α^j(C_{n-2} +α^jC_{n-1})...))$



مثال 2 . دع متجه الخطأ يتخذ الشكل = <0 0 0 0 12 0 0 0 0 0 0 8 0 0 0>. يقوم بتشكيل الأحرف في الموضعين الثالث والعاشر في ناقل الشفرة. قيم الخطأ هي 8 و 12 ، على التوالي - هذه القيم هي أيضًا عناصر من حقل GF (2 ⁴ ) وترد في التدوين العشري (الجدول P). في المتجه E ، يتم ترقيم المواقف من الموضع السفلي من اليمين إلى اليسار ، بدءًا من 0 (1) 14.



دعونا الآن نشكل متجهًا برمجيًا به خطأين في البتة الثالثة والعاشرة بالقيمتين 8 و 12 على التوالي. يتم ذلك عن طريق الجمع في GF (2 ⁴) وفق القواعد الحسابية لهذا المجال. لا يؤدي جمع عناصر الحقل بصفر إلى تغيير قيمتها. يتم جمع القيم غير الصفرية (عناصر الحقل) بعد تحويلها إلى تمثيل متعدد الحدود ، حيث يتم عادةً جمع كثيرات الحدود ، ولكن يتم تقليل معاملات المجهول بالطريقة 2.



بعد الحصول على نتيجة الجمع ، يتم تحويلها مرة أخرى إلى تمثيل عشري ، بعد أن مرت سابقًا من خلال التمثيل الأسي





يوضح ما يلي حساب القيم التالفة في 10 و 3 مواضع لكلمة الرمز:



$$$(7+12) →α^6+α^11 =x^3 +x^2 +x^3 +x^2 +x^1 =α^1 = 2,$

$$$(3 + 8) →α^2+ α^7 =x^2 +x^3 +x^1 + 1 =α^{12}=13.$



يقوم مفكك الشفرة بإجراء العمليات الحسابية وفقًا للصيغة العامة للمكونات Sj، j = 1 (1) m. هنا (في النموذج) نستخدم العلاقة$$$S=EH^t$نظرًا لأنه تم تعيين E (محاكاه) في البرنامج بأنفسنا ، يتم الحصول على المصطلحات غير الصفرية فقط لـ i = 3 و i = 10





أدناه ، سنعرض بشكل خاص العمليات الحسابية بهذه الصيغة في شكل موسع.

مصفوفة الشيك للكمبيوتر - كود

بمجرد صياغة كثير الحدود لتوليد الكود ، يصبح من الممكن إنشاء مصفوفة تحقق التكافؤ لكلمات الكود ، وكذلك لتحديد عدد الأخطاء التي يجب تصحيحها ( انظر هنا ، وحدة فك التشفير ). دعونا نبني مصفوفة مساعدة [7 × 15] ، يمكن من خلالها الحصول على مصفوفتين تحقق مختلفتين: الصفوف الستة الأولى عبارة عن صف وآخر ستة صفوف هي الأخرى.



يتم تشكيل المصفوفة نفسها بطريقة خاصة. أول سطرين واضحين ، السطر الثالث وكل السطور اللاحقة يتم الحصول عليها عن طريق طرح جزء من الأعداد الطبيعية 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8 ، 9 ، 10 ، 11 ، 12 ، 13 ، 14 من السطر السابق (الثاني) 15 mod 15. عندما تحدث قيمة صفرية ، يتم استبدالها بـ 15 ، يتم تحويل المخلفات السالبة إلى متبقية موجبة.





تتوافق كل مصفوفة مع المولد متعدد الحدود الخاص بها للتشفير النظامي وغير المنتظم.

تحديد معاملات متلازمة كثير الحدود

في ما يلي ، سنحدد معاملات متلازمية كثيرة الحدود لـ j = 1 (1) 6.

فيما يتعلق بكلمة الرمز مع الطول$$$n<q=p^r$عند الوصول إلى مدخلات مفكك الشفرة ، نفترض أنها مشوهة بسبب الأخطاء.



لتحديد متجه الأخطاء ، تحتاج إلى معرفة ما يلي:

• عدد المواضع المشوهة في كلمة السر
• $$$v≤v_{max}=0.5m$؛
• أرقام (موضع) المواقف المشوهة في كلمة السر $$$ℓ_i: ℓ_i=0(1)n-1$؛
• قيم التشويه $$$e_ℓ; e_ℓ∊GF(2^4)$...

كيف يتم حساب متجه المتلازمة (متعدد الحدود) S واستخدامه بشكل أكبر؟ دوره في فك تشفير كلمات المرور مهم جدا. دعونا نظهر هذا مع توضيح باستخدام مثال رقمي.



مثال 3 . (حساب مكونات ناقل المتلازمة$$$S_{<6>}$ )





ثم في النهاية لدينا $$$S_{<6>}=(S_1,S_2,S_3,S_4,S_5,S_6)$= <8،13،7،13،15،15>



لمزيد من الدراسة ، نقدم مفاهيم جديدة. الكمية$$$x_i = α^{ℓ_i}$سيطلق عليه محدد موقع الخطأ ، وهنا رمز كلمة الشفرة المشوهة في الموضع $$$ℓ_i$، α عنصر بدائي للمجال GF (2 ⁴ ).



تعتبر مجموعة محددات موقع الخطأ لكلمة رمز معينة أدناه معاملات محدد موقع الخطأ متعدد الحدود σ (z) ، الجذور$$$z_i$ وهي القيم $$$x_i ^{-1}$معكوس على المواقع.



علاوة على ذلك ، التعبيرات$$$(1-zx_i)=0$تلاشى.



$$$σ(z) = (1-zx_1)(1-zx_2)...(1-zx_v) =σ_vz^v +σ_{v-1}z^{v-1} +...+σ_1z +σ_0$

مصطلح مجاني دائمًا مصطلح مجاني $$$σ_0 =1$...

درجة كثير حدود محددات الخطأ تساوي v - عدد الأخطاء ولا تتجاوز القيمة$$$v≤v_{max}=0.5m$...



جميع الأحرف المشوهة في مواضع مختلفة للكلمة ، وبالتالي ، بين محددات المواقع$$$x_i = α^i$، لا يمكن أن يكون هناك عناصر مجال متكررة ، وكثير الحدود σ (z) = 0 ليس له جذور متعددة.



لتسهيل الكتابة ، سيتم إعادة تعيين قيم الخطأ بواسطة الرمز$$$Y_i = e_i$... بالنسبة لمعاملات متلازمات كثير الحدود ، تم النظر في المعادلات غير الخطية سابقًا. في حالتنا ، v = 1 هو أصل مكونات المتلازمة.





أين $$$y_i,x_i$ بكميات غير معروفة و $$$S_j$- معلمات معروفة ، محسوبة في المرحلة الأولى من فك التشفير (مكونات ناقل المتلازمة).



طرق حل مثل هذه الأنظمة من المعادلات غير الخطية غير معروفة ، ولكن تم العثور على الحلول باستخدام الحيل (الحلول). الانتقال إلى نظام Hankel (Toeplitz) للمعادلات الخطية فيما يتعلق بالمعاملات$$$σ_i$كثير الحدود محدد.



التحويل إلى نظام المعادلات الخطية



إلى معادلة$$$σ_i$ من كثير حدود محدد موقع الخطأ ، يتم استبدال قيمة جذوره $$$z =x_i^{-1}$... في هذه الحالة ، يتلاشى كثير الحدود. يتم تكوين هوية ، يتم ضرب كلا طرفيها$$$y_ix_i^{j+v}$، نحن نحصل:



$$$y_i(σ_vx_i^{j}+σ_{v-1}x_i^{j+1}+...+σ_1x_i^{j+v-1}+x_i^{j+v})=0,1≤i≤v, 1≤j≤v$...



نحصل على مثل هذه المساواة$$$v×v =v^2$



نجمع هذه المساواة في الكل $$$i, 1≤i≤v$التي يتم إرضاء هذه المساواة. نظرًا لأن كثير الحدود σ (z) لها جذور v$$$x_i^{-1}$، افتح الأقواس وانقل المعاملات $$$σ_i$ لكل علامة من المبلغ:





في هذه المساواة ، وفقًا لنظام المعادلات غير الخطية المعطى مسبقًا

، كل مجموع يساوي أحد مكونات ناقل المتلازمة. ومن ثم استنتج أنه فيما يتعلق بالمعاملات$$$σ_v, σ_{v-1},...,σ_1$ يمكنك كتابة نظام المعادلات الخطية.





يتم حذف العلامات "-" عند الحساب على حقل ثنائي ، لأنها تتوافق مع "+". نظام المعادلات الخطية الناتج هو Hankel ويتوافق مع مصفوفة ذات أبعاد$$$v×(v+1)$ قليلا.





لا تتحلل هذه المصفوفة إذا كان عدد الأخطاء في كلمة السر C (E) مساويًا تمامًا لها $$$v , v ≤0.5(n-k)$، بمعنى آخر. لا يتم انتهاك قدرة المناعة ضد الضوضاء لهذا الرمز.

حل نظام المعادلات الخطية

يحتوي نظام المعادلات الخطية الناتج على المعاملات على أنها مجاهيل $$$σ_i =1(1)t$كثير الحدود لمحدد موقع الخطأ لكلمة الرمز C (E). المكونات المحسوبة مسبقًا لناقل المتلازمة$$$S_j, j=1(1)m$... هنا t هو عدد الأخطاء في الكلمة ، m هو عدد مواضع الفحص في الكلمة.



هناك طرق مختلفة لحل النظام المشكل.



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



تُعرف طرق حل نظام هانكل للمعادلات الخطية في الحقول اللانهائية:

• طريقة الخندق التكراري - بيرلكامب - ميسي (طريقة TBM) ؛ (1)
• الحتمية المباشرة بيترسون - غورنشتاين - زيرلر ؛ (طريقة PHC) ؛ (2)
• طريقة Sugiyama باستخدام خوارزمية إقليدس لإيجاد GCD (طريقة C). [3)

دون التفكير في الطرق الأخرى ، سنختار طريقة TBM. الدافع للاختيار هو على النحو التالي.



الطريقة (PHC) بسيطة وجيدة ، ولكن بالنسبة لعدد قليل من الأخطاء القابلة للتصحيح ، يصعب تنفيذ طريقة C على جهاز الكمبيوتر ويتم نشرها (مغطاة) بشكل محدود في المصادر ، على الرغم من أن الطريقة C ، مثل طريقة TBM وفقًا لمتلازمات كثيرة الحدود المعروفة S (z) ، توفر حل معادلة Pade على حقل جالوا. تتكون هذه المعادلة من أجل كثير حدود محددات الخطأ σ (z) وكثير الحدود ω (z) ، في نظرية التشفير تسمى معادلة Pade الرئيسية:



$$$S(z)σ(z) = ω(z)(mod z^m)$...



حل المعادلة الأساسية هو المجموعة$$$x_i^{-1}$ جذور كثير الحدود σ (ض) ، وبناءً على ذلك ، محددات الموقع $$$x_i =α^{ℓ_i}$، بمعنى آخر. مواقف الخطأ. قيم الخطأ (المقادير)$$$e_i$ من صيغة فورني في النموذج





أين $$$σ_z^{'}(α^{-i})$ و $$$ω(α^{-i})$ هي قيم كثيرات الحدود σ (ض) و (ض) عند النقطة $$$z =α^{-i}$معكوس جذر كثير الحدود σ (ض) ؛

أنا هو موضع الخطأ ؛$$$σ_z^{'}(z)$ - المشتق الرسمي لكثير الحدود σ (ض) بالنسبة إلى ض ؛

مشتق رسمي من كثير الحدود في مجال محدود

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





$$$a_i$هي عناصر الحقل ، i = 1 (1) n



عناصر الحقل. يتم إعطاء رمز فوق حقل حقيقي GF (2 ⁴ ). المشتق بالنسبة إلى z هو:





في حقل حقيقي غير محدود ، تتضاعف العمليات في n وتتطابق مجموع n من المرات. بالنسبة للحقول المحدودة ، يتم تعريف المشتق بشكل مختلف.



يتم تحديد المشتق بالمثل من خلال النسبة:





حيث ((i)) = 1 + 1 + ... + 1 ، (i) مرات ، مجمعة وفقًا لقواعد حقل محدد: تشير علامة + إلى العملية "تلخيص عدة مرات" ، أي جزء$$$a_2z$ كرر مرتين ، العنصر $$$a_3z^2$ كرر 3 مرات ، العنصر $$$a_nz^{n-1}$كرر ن مرات.



من الواضح أن هذه العملية لا تتزامن مع عملية الضرب في مجال محدود. على وجه الخصوص ، في الحقول GF (2 ^r ) ، يتم أخذ مجموع عدد زوجي من المصطلحات المتطابقة mod2 وتصفيته ، والرقم الفردي يساوي المصطلح نفسه دون تغييرات. لذلك ، في الحقل GF (2 ^r ) ، يأخذ المشتق الشكل





المشتقات الزوجية الثانية والأعلى في هذا المجال تساوي صفرًا.



من المعروف من الجبر أنه إذا كانت كثيرة الحدود لها جذور متعددة (من التعددية p) ، فإن مشتق كثير الحدود سيكون له نفس الجذر ، ولكن مع التعدد p-1. إذا كان p = 1 ، فإن f (z) و f '(z) ليس لهما جذر مشترك. لذلك ، إذا كانت كثيرة الحدود ومشتقاتها لها قاسم مشترك ، فهناك جذر متعدد. جميع جذور المشتق f '(z) هي مضاعفات في f (z).

طريقة حل المعادلة الرئيسية

TMB (Trench-Berlekampa-Messi) هي طريقة لحل المعادلة الرئيسية. توفر الخوارزمية التكرارية تعريف كثيرات الحدود σ (z) و ω (z) ، وحل معادلة Pade (مفتاح).



البيانات الأولية: معاملات كثيرة الحدود$$$S_1,S_2,...,S_n$درجة n-1.

هدف. تعريف في شكل صريح (تحليلي) لكثيرات الحدود σ (ض) و ω (ض).



تستخدم الخوارزمية الترميز التالي: j - رقم الخطوة ،$$$v_j$ - درجة كثير الحدود ، $$$σ_j(z) =σ_{ji}z^i +σ_{ji-1}z^{i-1}+...+σ_{j1}z+σ_{j0}$ - توسيع كثير الحدود في القوى $$$z, k_j, L_j, θ_j(z)$ و $$$Ω_j(z)$- المتغيرات والوظائف الوسيطة في الخطوة j من الخوارزمية ؛



يجب تحديد الشروط الأولية ، حيث يتم استخدام العودية هنا.



الشروط الأولية:





مثال 4 . تنفيذ خوارزمية تكرارية للمتجه

S = (8،13،7،13،15،15). يتم تعريف كثيرات الحدود$$$σ(z) =σ_n(z)$ و $$$ω(z) = ω_n(z)$...



الجدول 2 - حساب كثيرات حدود محدد موقع الخطأ







وبالتالي $$$σ_j^←(z)=14z^2+13z+1$و $$$ω_j^←(z)$= 7z + 8.



كثير الحدود محدد موقع الخطأ σ (z) فوق الحقل GF (2 ⁴ ) مع كثير الحدود غير القابل للاختزال p (x) = x ⁴ + x + 1 له جذور



$$$z_1 = α^{-i_1} = 13 = 4^{-1}$ و $$$z_2 =α^{-i_2} = 6 = 11^{-1}$، من السهل التحقق من ذلك عن طريق التحقق المباشر ، أي $$$i_1= 3, i_2 =10, 13 = α^{12}, 1 =α^{12}α^{3}$ و $$$α^{12} =α^{-3}=>13=4^{-1}$... استبدال الجذر في

$$$σ(z=13)=14(13)^2+13·13+1=α^{13}(α^{12})^2+(α^{12})^2+α^0= α^{37}+α^{24} +α^{0}$=

=$$$α^{7}+α^{9}+α^0 =x^3+x+1=0(mod2)$؛

$$$σ(z = 6)=14(6)^2+13·6+1 = α^{13}(α^{5})^2+(α^{5})^2+α^{0}$=

=$$$α^{8}+α^{2} +α^{0} = x^2 +1+x^2 +1 = 0(mod2)$...



بأخذ المشتق الرسمي لـ σ (z) ، نحصل على σ_2 (z) = 2 14 + 13 = 13 ، حيث يتم أخذ 14z في المجموع مرتين ويختفي mod 2.



باستخدام صيغة فورني ، سنجد تعبيرات لحساب قيم الخطأ$$$e_i$...



بالتعويض عن القيم i = 3 و i = 10 مواضع في التعبير الأخير ،

نجد



$$$_3 = 10α^{15-3}+11 =α^{6}+α^{10}$= =$$$x^3+x^2+x^2+x+1=x^3+x+1=α^{7}=>8$؛

$$$_{10} = 10α^{15-10}+11 =α^{9}α^{5}+α^{10}=α^{14}+α^{10}$= =$$$x^3+x^2+x=α^{11}=>12$...

هندسة بناء حزمة البرمجيات

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



البيانات الأولية لحزمة البرنامج عبارة عن دفق رقمي للمعلومات التي تم تفريغها باستخدام تفريغ من ملف. لتسهيل التحليل ووضوح العملية المعقدة ، من المفترض أن تستخدم ملفات .txt.



يتم تقديم الدفق الرقمي المحمّل في شكل مصفوفات بيانات ، في سياق العمل المعقد الذي يتم فيه تطبيق إجراءات حسابية مختلفة.



في كل مرحلة من مراحل العملية المعقدة ، من الممكن تصور النتائج الوسيطة للعمل.



يتم عرض نتائج حزمة البرامج في شكل بيانات رقمية معروضة في الجداول.



يتم حفظ نتائج التحليل الوسيطة والنهائية في الملفات. يبدأ



مخطط عمل مجمع البرامج



العملية مع المجمع بتحميل دفق رقمي باستخدام تفريغ من ملف. بمجرد التنزيل ، يتم تقديم تمثيل مرئي للمستخدم للمحتوى الثنائي للملف ومحتواه النصي.



في إطار هذه الواجهة ، يجب تنفيذ المهام الوظيفية التالية:

• تنزيل الرسالة الأصلية ؛
• تحويل رسالة إلى ملف تفريغ ؛
• ترميز الرسالة ؛
• محاكاة رسالة تم اعتراضها
• بناء أطياف لكلمات الشفرة المستلمة لتحليل تمثيلها المرئي ؛
• عرض معلمات الكود.

وصف عملية حزمة البرامج



عند بدء تشغيل الملف التنفيذي للبرنامج ، تظهر النافذة الموضحة في الشكل 2 على الشاشة ، حيث يتم عرض الواجهة الرئيسية للبرنامج.



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



سيتم تقديم التمثيل الثنائي للرسالة في الحقل المقابل ، التمثيل الثنائي لكلمات المعلومات - في حقل "التمثيل الثنائي لكلمات المعلومات".



يتم عرض عدد البتات في الرسالة الأصلية والعدد الإجمالي للكلمات فيها في الحقلين "عدد البتات في الرسالة المرسلة" و "عدد الكلمات في الرسالة المرسلة".



يتم عرض المعلومات المشكّلة والكلمات البرمجية في جداول على الجانب الأيمن من نافذة البرنامج الرئيسية.



تظهر نافذة البرنامج ذات النتائج الوسيطة في الشكل 3.





الشكل 3 - عرض متوسط ​​لنتائج حزمة البرامج





الشكل 4. نتائج تنزيل ملف الرسالة





الشكل 5. نتائج ترميز الملف





الشكل 6. إخراج رسالة مع إدخال أخطاء فيها.





الشكل 7. مخرجات نتائج فك التشفير والرسائل مع إدخال أخطاء





الشكل 8. إخراج الرسالة التي تم فك تشفيرها.

خاتمة

وكالة الأمن القومي الأمريكية هي المشغل الأساسي لنظام اعتراض Echelon العالمي. تمتلك Echelon بنية تحتية واسعة بما في ذلك محطات التتبع الأرضية الموجودة في جميع أنحاء العالم. يتم رصد جميع تدفقات المعلومات العالمية تقريبًا.



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



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

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