الشفرة الدورية

من الأمثلة البسيطة على الرموز الدورية ما يلي:${\displaystyle A^{n}}$نفسها والرمز الذي يحتوي فقط على كلمة الرمز الصفرية. هذه تتوافق مع المولدات${\displaystyle 1}$و${\displaystyle x^{n}-1}$على التوالي: يجب أن تكون هاتان كثيرتا الحدود دائمًا من عوامل العدد${\displaystyle x^{n}-1}$.

زيادة${\displaystyle GF(2)}$رمز بت التكافؤ ، الذي يتكون من جميع الكلمات ذات الوزن الزوجي، يتوافق مع المولد${\displaystyle x+1}$مرة أخرى${\displaystyle GF(2)}$يجب أن يكون هذا دائمًا عاملاً من عوامل${\displaystyle x^{n}-1}$.

يمكن تمثيل العديد من أنواع رموز تصحيح الأخطاء الشائعة الاستخدام كرموز دورية، بما في ذلك رموز BCH ورموز ريد-سولومون وبعض فئات رموز التحقق من التكافؤ منخفضة الكثافة المعرفة من هندسات محدودة. ^{[ 4 ]}

دع عناصر الحقل${\displaystyle X_{1}}$و${\displaystyle X_{2}}$ليكن رقما موقعي الخطأ. إذا حدث خطأ واحد فقط، فـ${\displaystyle X_{2}}$يساوي صفرًا، وإذا لم يحدث أي منهما، فكلاهما يساوي صفرًا.

يترك${\displaystyle S_{1}={v}(\alpha )}$و${\displaystyle S_{3}={v}(\alpha ^{3})}$.

تُسمى هذه العناصر الميدانية "متلازمات". الآن لأن${\displaystyle g(x)}$يساوي صفرًا عند العناصر الأولية${\displaystyle \alpha }$و${\displaystyle \alpha ^{3}}$لذلك يمكننا أن نكتب${\displaystyle S_{1}=e(\alpha )}$و${\displaystyle S_{3}=e(\alpha ^{3})}$إذا حدث خطأين مثلاً، فـ

${\displaystyle S_{1}=\alpha ^{i}+\alpha ^{i'}}$و ${\displaystyle S_{3}=\alpha ^{3i}+\alpha ^{3i'}}$.

ويمكن اعتبار هذين الاثنين زوجين من المعادلات في${\displaystyle GF(2^{m})}$بمجهولين، وبالتالي يمكننا كتابة

${\displaystyle S_{1}=X_{1}+X_{2}}$و ${\displaystyle S_{3}=(X_{1})^{3}+(X_{2})^{3}}$.

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

إذا كان الحد الأدنى للمسافة بين عناصر رمز ثنائي هو 3 على الأقل، فيجب أن تكون مصفوفة التحقق الخاصة به جميع أعمدتها مميزة وغير صفرية. وإذا كانت مصفوفة التحقق الخاصة برمز ثنائي تحتوي على${\displaystyle m}$الصفوف، ثم كل عمود هو${\displaystyle m}$عدد ثنائي مكون من 10 بتات . يوجد${\displaystyle 2^{m}-1}$الأعمدة الممكنة. لذلك، إذا كانت مصفوفة التحقق لرمز ثنائي تحتوي على${\displaystyle d_{min}}$ثلاثة على الأقل${\displaystyle m}$صفوف، إذن لا يمكن أن يكون لديه إلا${\displaystyle 2^{m}-1}$أعمدة، لا أكثر من ذلك. هذا يُحدد${\displaystyle (2^{m}-1,2^{m}-1-m)}$رمز، يُسمى رمز هامينغ.

من السهل تعريف رموز هامينغ للأبجديات الكبيرة ذات الأحجام الكبيرة${\displaystyle q}$نحتاج إلى تعريف واحد${\displaystyle H}$مصفوفة ذات أعمدة مستقلة خطيًا. لأي كلمة بحجم${\displaystyle q}$ستكون هناك أعمدة تمثل مضاعفات لبعضها البعض. لذا، للحصول على استقلال خطي، يجب أن تكون جميع القيم غير الصفرية${\displaystyle m}$سيتم اختيار الصفوف التي تحتوي على عنصر غير صفري في أعلى الصف كأعمدة. وبالتالي، لن يكون هناك ارتباط خطي بين عمودين، لأن ثلاثة أعمدة قد تكون مرتبطة خطيًا، حيث تكون المسافة الدنيا في الكود 3.

إذن، هناك${\displaystyle (q^{m}-1)/(q-1)}$أعمدة غير صفرية، يكون العنصر غير الصفري الأعلى فيها واحدًا. لذلك، فإن رمز هامينغ هو${\displaystyle [(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]}$شفرة.

أما بالنسبة للرموز الدورية، فلنفترض${\displaystyle \alpha }$كن عنصرًا أوليًا في${\displaystyle GF(q^{m})}$ودع${\displaystyle \beta =\alpha ^{q-1}}$. ثم${\displaystyle \beta ^{(q^{m}-1)/(q-1)}=1}$وبالتالي${\displaystyle \beta }$هو جذر لكثير الحدود${\displaystyle x^{(q^{m}-1)/(q-1)}-1}$وهو متعدد الحدود المولد للرمز الدوري ذي طول الكتلة${\displaystyle n=(q^{m}-1)/(q-1)}$.

لولا${\displaystyle q=2}$،${\displaystyle \alpha =\beta }$والكلمة المستلمة هي متعددة حدود من الدرجة${\displaystyle n-1}$ معطى على النحو التالي

${\displaystyle v(x)=a(x)g(x)+e(x)}$

أين،${\displaystyle e(x)=0}$أو${\displaystyle x^{i}}$أين${\displaystyle i}$يمثل هذا مواقع الخطأ.

لكن يمكننا أيضًا استخدام${\displaystyle \alpha ^{i}}$كعنصر من${\displaystyle GF(2^{m})}$لتحديد موقع الخطأ في الفهرسة. لأن${\displaystyle g(\alpha )=0}$لدينا${\displaystyle v(\alpha )=\alpha ^{i}}$وجميع صلاحيات${\displaystyle \alpha }$من${\displaystyle 0}$ل${\displaystyle 2^{m}-2}$متميزة. لذلك يمكننا بسهولة تحديد موقع الخطأ${\displaystyle i}$من${\displaystyle \alpha ^{i}}$إلا إذا${\displaystyle v(\alpha )=0}$وهذا لا يمثل أي خطأ. لذا، فإن رمز هامينغ هو رمز تصحيح خطأ واحد على${\displaystyle GF(2)}$مع${\displaystyle n=2^{m}-1}$و${\displaystyle k=nm}$.

في عام 1959، قدم فيليب فاير ^{[ 8 ]} طريقةً لإنشاء رموز دورية مُولَّدة من خلال ضرب ثنائية حدية ومتعددة حدود أولية. تأخذ ثنائية الحدية الشكل التالي:${\displaystyle x^{c}+1}$لبعض الأعداد الفردية الموجبة${\displaystyle c}$[ ^{9 ]} رمز الحريق هو رمز تصحيح أخطاء الانفجار الدوري ^.${\displaystyle GF(q)}$باستخدام متعدد الحدود المولد

${\displaystyle g(x)=(x^{2t-1}-1)p(x)}$

أين${\displaystyle p(x)}$هي كثيرة حدود أولية من الدرجة${\displaystyle m}$لا يقل عن${\displaystyle t}$و${\displaystyle p(x)}$لم ينقسم${\displaystyle x^{2t-1}-1}$طول كتلة كود الحريق هو أصغر عدد صحيح${\displaystyle n}$بحيث${\displaystyle g(x)}$يقسم ${\displaystyle x^{n}-1}$.

يمكن لقانون الحريق تصحيح جميع أخطاء الانفجار التي يبلغ طولها t أو أقل إذا لم يحدث انفجاران متتاليان${\displaystyle b(x)}$و${\displaystyle x^{j}b'(x)}$تظهر في نفس المجموعة المشاركة. يمكن إثبات ذلك بالتناقض. لنفترض وجود نبضتين مختلفتين غير صفريتين${\displaystyle b(x)}$و${\displaystyle x^{j}b'(x)}$من الطول${\displaystyle t}$أو أقل، وهما في نفس المجموعة المشتركة للرمز. لذا، فإن الفرق بينهما هو كلمة رمزية. بما أن الفرق هو مضاعف لـ${\displaystyle g(x)}$وهو أيضًا من مضاعفات${\displaystyle x^{2t-1}-1}$. لذلك،

${\displaystyle b(x)=x^{j}b'(x)\mod (x^{2t-1}-1)}$.

هذا يدل على أن${\displaystyle j}$هو مضاعف لـ${\displaystyle 2t-1}$، لذا

${\displaystyle b(x)=x^{l(2t-1)}b'(x)}$

بالنسبة للبعض${\displaystyle l}$الآن، كما${\displaystyle l(2t-1)}$أقل من${\displaystyle t}$و${\displaystyle l}$أقل من${\displaystyle q^{m}-1}$لذا${\displaystyle (x^{l(2t-1)}-1)b(x)}$هي كلمة سرية. لذلك،

${\displaystyle (x^{l(2t-1)}-1)b(x)=a(x)(x^{2t-1}-1)p(x)}$.

منذ${\displaystyle b(x)}$الدرجة أقل من درجة${\displaystyle p(x)}$،${\displaystyle p(x)}$لا يمكن تقسيمها${\displaystyle b(x)}$. لو${\displaystyle l}$إذا لم يكن صفرًا، فإن${\displaystyle p(x)}$ولا يمكن تقسيمها أيضاً${\displaystyle x^{l(2t-1)}-1}$مثل${\displaystyle l}$أقل من${\displaystyle q^{m}-1}$وبحسب تعريف${\displaystyle m}$،${\displaystyle p(x)}$يقسم${\displaystyle x^{l(2t-1)}-1}$بدون${\displaystyle l}$أصغر من${\displaystyle q^{m}-1}$. لذلك${\displaystyle l}$و${\displaystyle j}$يساوي صفرًا. هذا يعني أن كلا الانفجارين متماثلان، على عكس الافتراض.

تُعدّ قوانين مكافحة الحرائق من أفضل القوانين التصحيحية للحرائق الفردية ذات معدل الاستجابة العالي، وهي مصممة تحليليًا. تتميز هذه القوانين بمعدل استجابة عالٍ جدًا، وعندما ${\displaystyle m}$و${\displaystyle t}$عندما تكون القيم متساوية، تكون الزيادة في التكرار في أدنى مستوياتها وتساوي${\displaystyle 3t-1}$باستخدام أكواد حريق متعددة، يمكن أيضًا تصحيح أخطاء الانفجارات الطويلة.

تُستخدم الرموز الدورية على نطاق واسع في اكتشاف الأخطاء، وتُسمى${\displaystyle t-1}$رموز التكرار الدوري .

تحويل فورييه على الحقول المنتهية

التحويل المتقطع لفورييه للمتجه${\displaystyle v=v_{0},v_{1},....,v_{n-1}}$ يتم تحديده بواسطة متجه${\displaystyle V=V_{0},V_{1},.....,V_{n-1}}$أين،

${\displaystyle V_{k}}$=${\displaystyle \Sigma _{i=0}^{n-1}e^{-j2\pi n^{-1}ik}v_{i}}$أين،

${\displaystyle k=0,.....,n-1}$

حيث exp(${\displaystyle -j2\pi /n}$) هو أن${\displaystyle n}$الجذر النوني للوحدة . وبالمثل في الحقل المنتهي${\displaystyle n}$الجذر النوني للوحدة هو عنصر${\displaystyle \omega }$من النظام${\displaystyle n}$. لذلك

لو${\displaystyle v=(v_{0},v_{1},....,v_{n-1})}$هو متجه فوق${\displaystyle GF(q)}$، و${\displaystyle \omega }$أن يكون عنصراً من${\displaystyle GF(q)}$من النظام${\displaystyle n}$ثم تحويل فورييه للمتجه${\displaystyle v}$هو المتجه${\displaystyle V=(V_{0},V_{1},.....,V_{n-1})}$وتُعطى المكونات بواسطة

${\displaystyle V_{j}}$=${\displaystyle \Sigma _{i=0}^{n-1}\omega ^{ij}v_{i}}$أين،

${\displaystyle k=0,.....,n-1}$

هنا${\displaystyle i}$هو مؤشر زمني ،${\displaystyle j}$التردد و​${\displaystyle V}$هو الطيف . أحد الفروق المهمة بين تحويل فورييه في المجال المركب ومجال غالوا هو أن المجال المركب${\displaystyle \omega }$يوجد لكل قيمة من${\displaystyle n}$أثناء وجوده في حقل غالوا${\displaystyle \omega }$لا يوجد إلا إذا${\displaystyle n}$يقسم${\displaystyle q-1}$في حالة حقول الامتداد، سيتم إجراء تحويل فورييه في حقل الامتداد.${\displaystyle GF(q^{m})}$ لو${\displaystyle n}$يقسم${\displaystyle q^{m}-1}$بالنسبة للبعض${\displaystyle m}$في حقل غالوا، متجه المجال الزمني${\displaystyle v}$يقع فوق الملعب${\displaystyle GF(q)}$لكن الطيف${\displaystyle V}$قد يكون ذلك فوق حقل الامتداد${\displaystyle GF(q^{m})}$.

أي كلمة رمزية من رمز دوري بطول كتلة${\displaystyle n}$يمكن تمثيلها بواسطة متعددة الحدود${\displaystyle c(x)}$درجة علمية على الأكثر${\displaystyle n-1}$يمكن كتابة مُشفِّره على النحو التالي:${\displaystyle c(x)=a(x)g(x)}$لذلك، يمكن كتابة المشفر في مجال التردد على النحو التالي:${\displaystyle C_{j}=A_{j}G_{j}}$هنا طيف الكلمات المشفرة${\displaystyle C_{j}}$له قيمة في${\displaystyle GF(q^{m})}$لكن جميع المكونات في المجال الزمني مأخوذة من${\displaystyle GF(q)}$. مع طيف البيانات${\displaystyle A_{j}}$الأمر تعسفي، ودور${\displaystyle G_{j}}$يتمثل الهدف في تحديد تلك${\displaystyle j}$أين${\displaystyle C_{j}}$ستكون النتيجة صفرًا.

وبالتالي، يمكن تعريف الرموز الدورية أيضًا على النحو التالي:

بالنظر إلى مجموعة من المؤشرات الطيفية،${\displaystyle A=(j_{1},....,j_{n-k})}$، والتي تسمى عناصرها ترددات التحقق، الشفرة الدورية${\displaystyle C}$هي مجموعة الكلمات فوق${\displaystyle GF(q)}$والتي يكون طيفها صفراً في المكونات المفهرسة بواسطة${\displaystyle j_{1},...,j_{n-k}}$أي طيف من هذا القبيل${\displaystyle C}$ستتضمن مكونات من الشكل${\displaystyle A_{j}G_{j}}$.

إذن، الرموز الدورية هي متجهات في الحقل${\displaystyle GF(q)}$والطيف الناتج عن تحويل فورييه العكسي يكون على المجال${\displaystyle GF(q^{m})}$وتكون هذه القيم مقيدة بحيث تكون صفرًا عند مكونات معينة. ولكن كل طيف في هذا المجال${\displaystyle GF(q^{m})}$وقد لا يكون للصفر عند بعض المكونات تحويلات عكسية مع المكونات الموجودة في الحقل${\displaystyle GF(q)}$لا يمكن استخدام هذا الطيف كرموز دورية.

فيما يلي بعض الحدود على نطاق الرموز الدورية.

عندما يكون رئيس الوزراء${\displaystyle l}$هو الباقي التربيعي modulo العدد الأولي${\displaystyle p}$يوجد رمز متبقي تربيعي وهو رمز دوري بطول${\displaystyle p}$الأبعاد${\displaystyle (p+1)/2}$والحد الأدنى للوزن على الأقل${\displaystyle {\sqrt {p}}}$زيادة${\displaystyle GF(l)}$.

الشفرة الدورية الثابتة هي شفرة خطية تتميز بالخاصية التالية: بالنسبة لبعض الثوابت${\displaystyle \lambda }$لو${\displaystyle (c_{1},c_{2},\dots ,c_{n})}$إذا كانت كلمة سرية، فكذلك${\displaystyle (\lambda c_{n},c_{1},\dots ,c_{n-1})}$الشفرة السالبة الدورية هي شفرة ثابتة الدورية ذات${\displaystyle \lambda =-1}$[ ^{10 ]​}

تتمتع الشفرة شبه الدورية (شفرة QC) بالخاصية التالية: بالنسبة لبعض${\displaystyle s}$الفاصل${\displaystyle n}$أي إزاحة دورية لكلمة رمزية بواسطة${\displaystyle s}$"الأماكن" هي كلمة سر مرة أخرى. أي أنها تمثل قيمة ثابتة ما.${\displaystyle s}$، لو${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$إذا كانت كلمة سرية، فكذلك${\displaystyle (c_{-s},c_{1-s},\dots ,c_{n-s-1})}$حيث يتم تقليل جميع الرموز السفلية modulo${\displaystyle n}$[ ^{11 ] يُعرف هذا النوع من} الرموز باسم${\displaystyle s}$- رمز مراقبة الجودة. الرمز الدائري المزدوج هو رمز شبه دوري ذو طول زوجي مع${\displaystyle s=2}$[ ^{11 ]​}

أن${\displaystyle (n,k)}$يُطلق على الشفرة الخطية اسم الشفرة الدورية المختصرة إذا أمكن الحصول عليها عن طريق حذف${\displaystyle b}$مناصب من${\displaystyle (n+b,k+b)}$الشفرة الدورية. الشفرة من هذا النوع ليست دورية بشكل عام. ^{[ 12 ]}

في الشفرات المختصرة، تُحذف رموز المعلومات للحصول على طول كتلة أصغر من طول الكتلة الأصلي. أثناء حذف أول${\displaystyle b}$يُعدّ حذف الرموز نهجًا شائعًا، ومن حيث المبدأ، يمكن حذف أي مجموعة من رموز المعلومات. ^{[ 12 ]} يمكن تحويل أي رمز دوري إلى رمز شبه دوري عن طريق حذف كل${\displaystyle b}$الرمز رقم -th، حيث${\displaystyle b}$هو عامل من عوامل${\displaystyle n}$إذا لم تكن الرموز المسقطة رموز تحقق، فإن هذا الرمز الدوري هو أيضًا رمز دوري مختصر.

تجمع الشفرات شبه الملتوية (شفرات QT) بين خصائص الشفرات الدورية الثابتة والشفرات شبه الدورية، مع حدوث التحول بواسطة${\displaystyle s}$أماكن وبمضاعفة${\displaystyle \lambda }$أي، بالنسبة لبعض الثوابت${\displaystyle \lambda }$و${\displaystyle s}$، لو${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$إذا كانت كلمة سرية، فكذلك${\displaystyle (\lambda c_{-s},c_{1-s},\dots ,c_{n-s-1})}$حيث يتم تقليل جميع الرموز السفلية modulo${\displaystyle n}$[ ^{13 ]} تُعدّ الشفرات متعددة الالتواءات تعميمات إضافية لشفرات QT، حيث تربط عدة شفرات QT من طرف إلى طرف ^{. [ 13 ] [ 14 ]}