حلقة الترميز. المركز التربوي المنهجي للتدريب اللغوي AVTF KC

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

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

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

وبالتالي ، فإن المصفوفة الإضافية C ، k لها الشكل

الآن نبني مصفوفة التوليد

خطوط هذه المصفوفة هي أول ثلاث مجموعات من الكود. يمكن الحصول على باقي التركيبات المسموح بها عن طريق جمع modulo اثنين من جميع المجموعات الممكنة لصفوف المصفوفة. 39.

الجدول 39 (انظر المسح)

من المعروف أنه من المهم النظر في أبسط كود من الدرجة الثانية كثير الحدود غير القابل للاختزال

يختلف العرض العام لمصفوفة توليد الشفرة الدورية التي شكلتها كثير الحدود في بنية المصفوفة الإضافية التي تحتوي على عمودين.

من السهل التحقق من أنه عند القسمة على مولد معين ، فإن كثيرات الحدود تعبر عن الصفوف

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

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

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

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

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

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

عند فك تشفير كلمة التشفير n-bit المستلمة ، يتم إجراء القسمة على متعدد الحدود (توليد ، توليد) مرة أخرى.

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

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

دع العدد الإجمالي للبتات في الكتلة يساوي i ، منها معلومات مفيدةاحمل تيبتات ، ثم في حالة حدوث خطأ ، من الممكن تصحيح j بت. التبعية 5 على NSو تيللرموز يمكن تحديدها من الجدول. 2.6.

الجدول 2.6

اعتماد العدد الإجمالي لأرقام التوليفات على عدد الأرقام المعلوماتية والمصححة

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

الجدول 2.7

النسبة المئوية للأخطاء المتعددة التي تم اكتشافها

من الملائم وصف الأكواد الدورية وتكوينها باستخدام كثيرات الحدود (أو كثيرات الحدود). تمت كتابة المجموعة في شكل كثير الحدود من أجل عرض طريقة رسمية لعملية التحول الدوري للكلمة البرمجية الأصلية. لذلك ، يمكن وصف تركيبة كود العنصر "- بواسطة كثير الحدود (NS- 1) درجات:

أينa „_j =(0 ، 1) ، وأ "_ ، =0 تتوافق مع صفر عناصر من المجموعة ، q „_ ، = 1 - غير صفري ؛أنا- رقم بتات مجموعة الكود.

دعنا نمثل كثيرات الحدود لتركيبات محددة مكونة من 4 عناصر:

عمليات الجمع والطرح متكافئة وترابطية ويتم إجراؤها بالوحدة 2:

أمثلة على إجراء العمليات:

عملية القسمة هي التقسيم المعتاد لكثيرات الحدود ، ولكن بدلاً من الطرح ، يتم استخدام معامل الجمع 2:

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

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

لنفترض أن تركيبة الشفرة الأصلية وكثير الحدود المقابل معطيان:

تتضاعف أوه)تشغيل NS:

منذ الدرجة القصوى NSفي كلمة مرور طويلة NSلا يتجاوز (ن - 1) ، ثم من الجانب الأيمن للتعبير الناتج للحصول على كثير الحدود الأصلي ، من الضروري طرح أوه"- 1). الطرح أوه"- 1) يسمى أخذ الباقي modulo (x ن - 1).

يمكن تمثيل تحول المجموعة الأصلية بواسطة / المقاييس على النحو التالي: فأس)؟نعم - أوه"- 1) ، أي عمليه الضرب أوه)ناه "وأخذ بقية modulo (x" - 1). أخذ الباقي ضروري عند الحصول على كثير الحدود بدرجة أكبر من أو يساوي NS.

تعتمد فكرة إنشاء أكواد دورية على استخدام كثيرات الحدود غير قابلة للاختزال.كثير الحدود غير القابل للاختزال هو كثير الحدود الذي لا يمكن تمثيله كمنتج متعدد الحدود من الدرجات الدنيا ، أي لا يقبل القسمة إلا على نفسه أو على واحد ولا يقبل القسمة على أي كثير حدود آخر. ذات الحدين (x "+ 1) قابلة للقسمة على مثل هذه كثيرة الحدود بدون باقي. تلعب كثيرات الحدود غير القابلة للاختزال في نظرية الأكواد الدورية دورًا في توليد كثيرات الحدود.

بالعودة إلى تعريف الكود الدوري مع الأخذ في الاعتبار تسجيل عمليات التحول الدوري لمجموعات الكود ، فمن الممكن كتابة مصفوفة توليد الكود الدوري بالشكل التالي:

أينف (س)- مجموعة الكود الأصلي ، والتي على أساسها كل شيء آخر(ت- 1) تركيبات أساسية ؛

С ، = 0 أوCj =1 ("O" إذا كانت الدرجة الناتجة من كثير الحدودف (س) -س 'لا يتجاوز (ل - 1) ، أو "1" - إذا حدث ذلك).

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

يجب أن تفي كثير حدود المولد بالمتطلبات التالية:

• ف (س)يجب أن تكون غير صفرية ؛
• الوزن ص (x) يجب ألا تقل عن الحد الأدنى لمسافة الرمز: V (P (x))> d مم ؛
• ف (س)يجب أن يكون على الدرجة القصوى ك (ك -عدد العناصر الزائدة في الكود) ؛
• ف (س)يجب أن يكون مقسومًا على كثير الحدود (س "- 1).

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

لتحديد درجة تولد كثير الحدود ، يمكن للمرء استخدام التعبير r> log 2 (و + 1) أين NS- حجم الحزمة المرسلة في كل مرة ، أي طول الكود الدوري المُنشأ.

أمثلة لتوليد كثيرات الحدود معطاة في الجدول. 2.8

الجدول 2.8

أمثلة على المولد متعدد الحدود

فيما يلي خوارزمية الحصول على مجموعة كود مسموح بها من كود دوري من مجموعة من كود بسيط.

دعونا نعطي كثير الحدود الفوسفور (س) = أ ع _ (س ع + أ ع ع _ 2 س r ~ 1 + ... + 1 ، الذي يحدد قدرة التصحيح للرمز ، وعدد بتات الفحص إلى،بالإضافة إلى المجموعة الأصلية من رمز بسيط من العنصر وبتات المعلومات في شكل كثير الحدود أ م (س).

مطلوب لتحديد مجموعة الكود المسموح بها للشفرة الدورية (و ، إلى).

• 1. نحن نمثل مجموعة التعليمات البرمجية الأصلية في شكل كثير الحدود أ م (س).نضرب كثير الحدود لكلمة الرمز الأصلية في x g: A t (x) وجه ضاحك.درجة توليد كثير الحدود جيتساوي قيمة البتة الأكثر دلالة في كلمة التشفير الأصلية.
• 2. تحديد أرقام التحقق التي تكمل مجموعة المعلومات الأصلية للمجموعة المسموح بها ، مثل باقي قسمة المنتج الذي تم الحصول عليه في الفقرة السابقة بواسطة المولد

متعدد الحدود:

يتم الإشارة إلى ما تبقى من التقسيم كـ ص (x).

3. النمط الدوري الذي تم حله أخيرًا

يتم تعريف الرمز على أنه = و t (x)؟ س ص + ص (س).

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

خوارزمية تحديد الخطأ هي كما يلي.

دع تركيبات "-element ( ن = ك + ر).

• 1. نحدد حقيقة وجود خطأ. نحصل على ما تبقى من قسمة المجموعة المقبولة أ ن - (س)لتوليد كثير الحدود ص (خ):(NS)
• --- = Rq (x). وجود الباقي ص 0 (x)لـ (A 0 (x) f 0) يشير ف (س)

عن الخطأ.

2. قسّم كثير الحدود الناتج # (x) = Л „_،(NS) 0 Rq (x) لكل مولد R g (x): W-1 = ص (س) ،أين ص (x)- الرصيد الحالي.

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

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

ص (س) =الجحيم.

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

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

يسمح لنا هذا بالنظر في مجموعة الكلمات ذات الطول n فوق حقل محدد كمساحة خطية من كثيرات الحدود بدرجة n-1 على الأكثر فوق الحقل

وصف جبري

لو كلمة السريتم الحصول عليها عن طريق النقل الدوري بتة واحدة إلى اليمين من الكلمة ، ثم كثير الحدود المقابل ج 1 (x) من السابق بضربه في x:

الاستفادة من حقيقة أن ،

التحول إلى اليمين واليسار ، على التوالي ، بمقدار يأرقام:

لو م(x) عبارة عن كثير حدود تعسفيًا فوق هذا المجال جيF(ف) و ج(x) هي كلمة السر للدوري ( ن,ك) رمز ، إذن م(x)ج(x)ماد(x ن − 1) هي أيضا كلمة السر لهذا الرمز.

توليد كثير الحدود

تعريفتولد كثير الحدود من دوري ( ن,ك) الشفرة جيسمى مثل كثير الحدود غير الصفري من عند جودرجتها هي الأصغر والمعامل عند أعلى درجة ز ص = 1 .

نظرية 1

لو ج- دوري ( ن,ك) رمز و ز(x) هو توليد كثير الحدود ، ثم الدرجة ز(x) يساوي ص = ن − ك ويمكن تمثيل كل كلمة رمز بشكل فريد كـ

ج(x) = م(x)ز(x) ,

أين الدرجة م(x) أصغر من أو يساوي ك − 1 .

نظرية 2

ز(x) هو مولد متعدد الحدود للدوري ( ن,ك) من الكود هو قاسم ذات الحدين x ن − 1

سماد:وهكذا ، كمولد كثير حدود ، يمكنك اختيار أي كثير حدود ، المقسوم عليه x ن- 1. ستحدد درجة كثير الحدود المحدد عدد رموز الفحص ص، عدد رموز المعلومات ك = ن − ص .

المصفوفة التوليدية

تكون كثيرات الحدود مستقلة خطيًا ، وإلا م(x)ز(x) = 0 على غير الصفر م(x) وهو مستحيل.

هذا يعني أنه يمكن كتابة كلمات التشفير ، كما هو الحال بالنسبة للرموز الخطية ، على النحو التالي:

، أين جيهو إنشاء المصفوفة, م(x) - معلومةمتعدد الحدود.

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

تحقق من المصفوفة

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

الترميز

غير منهجي

مع الترميز غير المنتظم ، يتم الحصول على كلمة الكود في شكل منتج كثير حدود المعلومات عن طريق التوليد

ج(x) = م(x)ز(x) .

يمكن تنفيذه باستخدام مضاعفات كثيرة الحدود.

منهجي

مع الترميز المنهجي ، يتم تشكيل كلمة الشفرة في شكل كتلة فرعية للمعلومات والتحقق

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

ج(x) = x ص م(x) + س(x),ص = ن − ك

ثم من الشرط ، يتبع

تحدد هذه المعادلة قاعدة الترميز النظامي. يمكن تنفيذه باستخدام مرشحات خطية متعددة الدورات (MLF)

أمثلة على

كود ثنائي (7،4،3)

كمقسوم x 7-1 نختار كثير حدود التوليد من الدرجة الثالثة ز(x) = x 3 + x + 1 ، ثم سيكون للشفرة الناتجة طول ن= 7 ، عدد رموز الشيك (درجة تولد كثير الحدود) ص= 3 ، عدد رموز المعلومات ك= 4 ، الحد الأدنى للمسافة د = 3 .

المصفوفة التوليديةالشفرة:

,

حيث يمثل السطر الأول تدوين متعدد الحدود ز(x) المعاملات في درجة تصاعدية. باقي الخطوط عبارة عن تحولات دورية للسطر الأول.

تحقق من المصفوفة:

,

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

لذلك ، على سبيل المثال ، يتم الحصول على العمود الثالث ، أو في تدوين المتجه.

من السهل رؤية ذلك جيح تي = 0 .

ثنائي (15.7.5) كود BCH

كمولد كثير الحدود ز(x) يمكنك اختيار حاصل ضرب اثنين من القواسم x 15 − 1 ^

ز(x) = ز 1 (x)ز 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

ثم يمكن الحصول على كل كلمة مشفرة باستخدام حاصل ضرب كثير حدود المعلومات م(x) بدرجة ك- 1 بهذه الطريقة:

ج(x) = م(x)ز(x) .

على سبيل المثال ، كلمة المعلومات تتوافق مع كثير الحدود م(x) = x 6 + x 5 + x 4 + 1 ، ثم كلمة السر ج(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 ، أو في شكل متجه

أنظر أيضا

الروابط

مؤسسة ويكيميديا. 2010.

• أشكال دورية في الموسيقى
• شروط الحدود الدورية

شاهد ما هي "الرموز الدورية" في القواميس الأخرى:

رموز دورية مختصرة- - [L.G. Sumenko. القاموس الإنجليزي الروسي لتكنولوجيا المعلومات. م: GP TsNIIS ، 2003.] الموضوعات تكنولوجيا المعلوماتبشكل عام رموز دورية مختصرة EN ...

رموز ريد سليمان- أكواد دورية غير ثنائية لتصحيح الأخطاء في كتل البيانات. عناصر متجه الشفرة ليست بتات ، ولكنها مجموعات من البتات (كتل). رموز Reed Solomon التي تعمل بالبايت (ثماني بتات) شائعة جدًا. كود ريد سليمان هو ... ويكيبيديا

رموز جولاي- عائلة من أكواد الكتل الخطية المثالية مع تصحيح الخطأ. الأكثر فائدة هو كود Golay الثنائي. رمز Golay الثلاثي معروف أيضًا. يمكن اعتبار رموز Golay بمثابة رموز دورية. ... ... دليل المترجم الفني

أكواد تصحيح الخطأ

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

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

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

العديد من أهم أكواد مكافحة التشويش لأنظمة الاتصالات ، -

الدوري على وجه الخصوص ، استنادًا إلى هياكل الحساب المحدود

حقول جالوا. بالميدانتسمى مجموعة العناصر التي لها مجال محدود

تكون أسماء العمليات بين علامتي اقتباس لأنها ليست عمليات حسابية مقبولة بشكل عام دائمًا. يحتوي الحقل دائمًا على عنصر صفري (0) ، أو صفر ، وعنصر واحد (1) ، أو عنصر واحد. إذا كان الرقم فعناصر الحقل محدودة ، ثم يسمى الحقل مجال محدود، أو مجال غالوا المحدود، والمشار إليها GF (ف) ذأين ف -مجال الطلب. أصغر حقل الوا هو iole المكون من عنصرين GF ( 2) ، تتكون من عنصرين فقط 1 و 0. من أجل

1 Evariste Galois (1811-1832) - عالم رياضيات فرنسي ، وضع أسس علم الجبر الحديث.

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

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

بالنسبة لعمليات الجمع والضرب ، يتم اتباع قواعد الترابط الرياضي المعتادة - أ + (ب + ج) = (أ + ب)+ c ، التبديل - أ + ب = ب + أو أ ب = ب أوالتوزيع - أ (ب+ ق) = أ ب + أ مع.

لكل عنصر من عناصر المجال أيجب أن توجد الإضافة العكسية (-أ)و إذا أغير الصفر ، العنصر العكسي للضرب (th ').

يجب أن يحتوي الحقل على وحدة مضافة -العنصر 0 من هذا القبيل أ + 0 = ألأي عنصر ميداني أ.

يجب أن يحتوي الحقل على وحدة الضرب -العنصر 1 من هذا القبيل aL = ألأي عنصر ميداني أ.

على سبيل المثال ، هناك حقول أرقام حقيقية، الأعداد المنطقية ، الأعداد المركبة. تحتوي هذه الحقول على عدد لا حصر له من العناصر.

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

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

في الكود الدوري ، يتم تمثيل الكلمات المشفرة بواسطة كثيرات الحدود (كثيرات الحدود)

أين NS -طول الكود أ أنا -معاملات حقل جالوا (قيم تركيبة الكود).

على سبيل المثال ، بالنسبة لتركيبة الكود 101101 ، فإن تدوين متعدد الحدود له الشكل

من أمثلة الأكواد الدورية الرموز التي يتم فحصها حتى ، وأكواد التكرار ، وأكواد المطرقة ، وأكواد الكمبيوتر ، وأكواد التوربو.

كود هامينج... ترتبط إمكانيات تصحيح الخطأ لشفرة Hamming بمسافة التشفير الدنيا د 0.تم إصلاح جميع أخطاء التعددية ف= cnt (د 0- l) / 2 (هنا يرمز cnt إلى "جزء صحيح") ويتم الكشف عن أخطاء التعددية د 0 - 1. لذلك ، عند التحقق من الغرابة د س = 2 ويتم الكشف عن أخطاء فردية. في قانون هامينج د 0 = 3. بالإضافة إلى بت المعلومات ، أ L =سجل 2 س بتات التحكم الزائدة ، أين س -عدد بتات المعلومات. معامل إلمقربًا إلى أقرب قيمة عدد صحيح أعلى. رمز التحكم L-bit هو النتيجة المقلوبة لإضافة البت (إضافة وحدة 2) لأرقام بتات المعلومات هذه ، والتي تساوي قيمها واحدًا.

مثال 7.7

افترض أن لدينا الكود الرئيسي 100110 ، أي س = 6. دعنا نحدد كود إضافي.

حل

نجد ذلك إل= 3 والرمز التكميلي هو

حيث P هي رمز عملية إضافة البت ، وبعد قلبها لدينا 000. الآن سيتم إرسال الكود الإضافي مع الكود الرئيسي. في جهاز الاستقبال ، يتم حساب الكود الإضافي مرة أخرى ومقارنته بالرمز المرسل. رمز المقارنة ثابت ، وإذا كان مختلفًا عن الصفر ، فإن قيمته هي رقم البت الذي تم استلامه بالخطأ من الكود الرئيسي. لذلك ، إذا تم استلام الكود 100010 ، فإن الكود الإضافي المحسوب يساوي انعكاس 010SH10 = 100 ، أي 011 ، مما يعني وجود خطأ في الرقم الثالث.

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

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

رموز توربو.يمكن استخدام الرموز المكررة بشكل مستقل وفي شكل مزيج من عدة أكواد ، عندما يتم اعتبار مجموعات الرموز الخاصة برمز فائض واحد كرموز معلومات أولية لرمز آخر مكرر. بدأ استدعاء مثل هذا الاتحاد المتتاليةالشفرة. من المزايا الكبيرة للرموز المتسلسلة أن استخدامها يجعل من الممكن تبسيط المشفر وخاصة وحدة فك التشفير مقارنة بالأجهزة المماثلة ذات الرموز غير المتسلسلة التي لها نفس الطول والتكرار. أدى الترميز المتسلسل إلى إنشاء رموز توربو. التربوكوديسمى هيكل إشارة موازية يتكون من اثنين أو أكثرأكواد منهجية. المبدأ الأساسي في بنائها هو استخدام العديد من المبرمجين المكونين الذين يعملون بالتوازي. كأكواد مكونة ، يمكنك استخدام كل من رموز الكتلة والتلافيف ، وأكواد Hamming ، و PC-code ، و BCH ، وما إلى ذلك. يسمح استخدام التثقيب (الثقب) بزيادة السرعة النسبية لشفرة التوربو ، وتكييف قدرتها على التصحيح مع الخصائص الإحصائية لـ قناة الاتصال. مبدأ تكوين شفرة توربو هو كما يلي: إشارة الدخل NS ،تتكون من إلىبت ، تتغذى بالتوازي مع نالمشذرات. كل من هذا الأخير هو جهاز يبدل العناصر في كتلة من إلىالبتات بترتيب شبه عشوائي. يتم تغذية إشارة الخرج من المشذرات - الرموز المعاد ترتيبها - إلى المشفرات الأولية المقابلة. التسلسلات الثنائية س ص ط= 1،2 ، ... ، JV ، عند إخراج المشفر هي رموز فحص ، والتي تشكل مع بتات المعلومات كلمة تشفير واحدة. يتيح استخدام التشذير منع ظهور تسلسلات من الأخطاء المترابطة عند فك رموز توربو ، وهو أمر مهم عند استخدام طريقة فك التشفير العودية ، وهو أمر تقليدي في المعالجة. اعتمادًا على اختيار رمز المكون ، يتم تقسيم أكواد التربو إلى أكواد توربو تلافيفية وأكواد منتج كتلة.

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

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

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

لنفترض أنك تريد تشفير إحدى مجموعات الأرقام المكونة من أربعة أرقام كود ثنائي... افترض أيضا أن هذا الجمع G (x) = x 3 + x 2 + 1 ® 1011. في حين أننا لا نؤيد خيارنا ، فإننا نأخذ من جدول كثيرات الحدود غير القابلة للاختزال باعتبارها كثيرة الحدود المولدة الفوسفور (س) = س 3 + س + 1 ® 1011. ثم نضرب ز (س)بواسطة أحادية من نفس الدرجة مثل كثير الحدود المولد. من ضرب كثير الحدود بمحدود الدرجة نستزيد درجة كل حد في كثير الحدود بمقدار ن، وهو ما يعادل التنازل نالأصفار على جانب البتات الأقل دلالة في كثير الحدود. نظرًا لأن درجة كثير الحدود غير القابلة للاختزال المحددة تساوي ثلاثة ، يتم ضرب مجموعة المعلومات الأصلية في أحادية من ثلاث درجات

G (x) x n =(× 3 + × 2 + 1) س 3 = س 6 + س 5 + س 3 = 1101000.

يتم ذلك بحيث يمكن كتابة أرقام تصحيح لاحقًا في مكان هذه الأصفار.

تم العثور على قيمة أرقام التصحيح من نتائج القسمة G (x) x nتشغيل ف (س):

x 6 + x 5 + 0 + x 3 + 0 + 0 + 0 ½x 3 + x + 1

س 6 + 0 + س 4 + س 3

x 5 + x 4 + 0 + 0 x 3 + x 2 + x + 1 + x 5 + 0 + x 3 + x 2

× 4 + × 3 + × 2 +0

س 4 + 0 + س 2 + س

س 3 + 0 + س + 0

س 3 + 0 + س + 1

هكذا،

أو في نظرة عامة

أين س (س)¾ الخاص و ص (x)¾ باقي القسمة ز (س) × س نتشغيل ص (x).

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

وبالتالي ، يمكن كتابة التعبير (5.1) كـ

F (x) = Q (x) P (x) = G (x) x n + R (x) ،

الذي في حالة مثالنا سوف نعطي

و (س) =(س 3 + س 2 + س + 1) (x 3 + x + 1)= (× 3 + × 2 + 1)× 3 + 1,

و (س) = 1111 1011 = 1101000 + 001 = 1101001.

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

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

من ناحية أخرى ، يتم استخدام باقي قسمة واحد بأصفار على كثير حدود التوليد لإنشاء أكواد دورية.

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

01100 11111+

ابتداء من الثامن ، سوف تتكرر الباقي.

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

صفوف المصفوفة المولدة هي المجموعات الأولى مصدر الرمز... يتم الحصول على التوليفات المتبقية من الكود بجمع كل التوليفات الممكنة من صفوف المصفوفة المولدة للوضع 2.

مثال.

أنشئ مصفوفة توليد كاملة لرمز دوري يكتشف جميع الأخطاء الفردية والمزدوجة عند إرسال مجموعات ثنائية 10 بت.

حل.

وفقًا للجدول 5.12 ، حدد أقرب قيمة ك ³ 10.

الجدول 5.12 - العلاقات بين المعلومات ورموز الفحص لكود يصل طوله إلى 16 بتة

ن	ك	ρ	ن	ك	ρ

وفقًا للجدول ، ستكون هذه القيمة ك = 11 ، بينما ص = 4, أ

ن = 15. نختار أيضًا المولد متعدد الحدود × 4 + × 3 +1.

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

تبديل المصفوفة لـ ك = 11 يشبه:

يمكن إنشاء مصفوفة إضافية من باقي تقسيم المجموعة في شكل واحد متبوعًا بأصفار (الصف الأخير من مصفوفة منقولة الهوية) بواسطة كثير الحدود المولِّد المختار.

ستبدو مصفوفة المولد الكاملة كما يلي:

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

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

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

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

لا يهم موقع الخطأ في مجموعة التعليمات البرمجية. لو ك ³ (ن / 2)، ثم بعد عدد معين من التحولات ، ستكون جميع الأخطاء في منطقة الإجراء "لمرة واحدة" لكثير الحدود المولِّد ، أي يكفي الحصول على الباقي الذي يكون وزنه W £ s، وسيكون هذا كافياً بالفعل لتصحيح التركيبة المشوهة.

تتم مناقشة عملية تصحيح الخطأ بالتفصيل أدناه باستخدام أمثلة لبناء أكواد محددة.