رموز AN

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

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

الوزن الحسابي للعدد الصحيح${\displaystyle x}$في القاعدة${\displaystyle r}$يتم تعريفها بواسطة

${\displaystyle w(x)=\min\{t|x=\sum _{i=1}^{t}a_{i}r^{n(i)}\}}$

أين${\displaystyle |{a_{i}}|}$<${\displaystyle r}$،${\displaystyle n(i)\geq 0}$، و${\displaystyle r,n(i)\in \mathbb {Z} }$[ ^{2 ]} المسافة الحسابية للكلمة محدودة من الأعلى بوزن هامينغ الخاص بها، حيث يمكن تمثيل أي عدد صحيح بصيغته متعددة الحدود القياسية ^.${\displaystyle x=\sum _{i=1}^{n}b_{i}r^{i}}$حيث${\displaystyle b_{i}}$هي الأرقام في العدد الصحيح. إزالة جميع الحدود حيث${\displaystyle b_{i}=0}$سوف تحاكي${\displaystyle t}$يساوي وزن هامينغ الخاص به. عادةً ما يكون الوزن الحسابي أقل من وزن هامينغ لأن${\displaystyle a_{i}}$يُسمح بأن تكون سالبة. على سبيل المثال، العدد الصحيح${\displaystyle x=29}$وهو${\displaystyle 11101}$في النظام الثنائي، يبلغ وزن هامينغ${\displaystyle 4}$هذا حدٌّ أعلى سريع للوزن الحسابي، لأن${\displaystyle x=2^{0}+2^{2}+2^{3}+2^{4}}$ومع ذلك، منذ ذلك الحين${\displaystyle a_{i}}$يمكن أن تكون سلبية، يمكننا أن نكتب${\displaystyle x=2^{5}-2^{1}-2^{0}}$مما يجعل الوزن الحسابي مساوياً لـ${\displaystyle 3}$.

المسافة الحسابية بين عددين صحيحين تُعرَّف بـ

${\displaystyle d(x,y)=w(xy)}$

يُعد هذا أحد المقاييس الأساسية المستخدمة عند تحليل رموز العمليات الحسابية. ^{[ 3 ] [ 4 ]}

يتم تعريف رموز AN بواسطة أعداد صحيحة${\displaystyle A}$و${\displaystyle B}$وتُستخدم لترميز الأعداد الصحيحة من${\displaystyle 0}$ل${\displaystyle B-1}$بحيث

${\displaystyle C=\{AN|N\in \mathbb {Z} ,0\leq N}$<${\displaystyle B\}}$

كل خيار من${\displaystyle A}$سيؤدي ذلك إلى رمز مختلف، بينما${\displaystyle B}$يُعدّ عاملاً مُحدداً لضمان الخصائص المفيدة في نطاق الكود. إذا${\displaystyle B}$إذا كان حجم الرمز كبيرًا جدًا، فقد يسمح بدخول كلمة رمزية ذات وزن حسابي صغير جدًا إلى الشفرة، مما سيؤدي إلى تدهور مسافة الشفرة بأكملها. لاستخدام هذه الرموز، قبل إجراء أي عملية حسابية على عددين صحيحين، يتم ضرب كل عدد صحيح في${\displaystyle A}$ليكن ناتج العملية على الكلمات المشفرة هو${\displaystyle R}$. لاحظ أن${\displaystyle R}$يجب أن يكون أيضًا بين${\displaystyle 0}$ل${\displaystyle B-1}$لفك التشفير بشكل صحيح. لفك التشفير، ما عليك سوى القسمة${\displaystyle R/A}$. لو${\displaystyle A}$لا يُعد عاملاً من عوامل${\displaystyle R}$إذاً، فقد حدث خطأ واحد على الأقل، وسيكون الحل الأكثر ترجيحاً هو كلمة الترميز ذات أقصر مسافة حسابية من${\displaystyle R}$كما هو الحال مع الرموز التي تستخدم مسافة هامينغ، يمكن لرموز AN تصحيح ما يصل إلى${\displaystyle \lfloor {\frac {d-1}{2}}\rfloor }$أخطاء حيث${\displaystyle d}$هي مسافة الرمز.

على سبيل المثال، رمز AN مع${\displaystyle A=3}$عملية الجمع${\displaystyle 15}$و${\displaystyle 16}$ستبدأ العملية بتشفير كلا المعاملين. ينتج عن ذلك العملية${\displaystyle R=45+48=93}$ثم، لإيجاد الحل نقسم${\displaystyle 93/3=31}$طالما${\displaystyle B}$>${\displaystyle 31}$ستكون هذه عملية ممكنة ضمن الكود. لنفترض حدوث خطأ في كل تمثيل ثنائي للمعاملات بحيث${\displaystyle 45=101101\rightarrow 101111}$و${\displaystyle 48=110000\rightarrow 110001}$، ثم${\displaystyle R=101111+110001=1100000}$لاحظ ذلك منذ${\displaystyle 93=1011101}$وزن هامينغ بين الكلمة المستلمة والحل الصحيح هو${\displaystyle 5}$اتبع فقط${\displaystyle 2}$الأخطاء. لحساب الوزن الحسابي، نأخذ${\displaystyle 1100000-1011101=11}$والتي يمكن تمثيلها على النحو التالي${\displaystyle 11=2^{0}+2^{1}}$أو${\displaystyle 11=2^{2}-2^{0}}$في كلتا الحالتين، تكون المسافة الحسابية هي${\displaystyle 2}$كما هو متوقع، فهذا هو عدد الأخطاء التي حدثت. لتصحيح هذا الخطأ، سيتم استخدام خوارزمية لحساب أقرب كلمة رمزية للكلمة المستلمة من حيث المسافة الحسابية. لن نتناول الخوارزميات بالتفصيل.

لضمان عدم صغر مسافة الرمز، سنحدد رموز AN المعيارية. رمز AN المعياري${\displaystyle C}$هي مجموعة فرعية من${\displaystyle \mathbb {Z} /m\mathbb {Z} }$، أين${\displaystyle m=AB}$تُقاس الرموز من حيث المسافة المعيارية، والتي تُعرَّف بدلالة رسم بياني تكون رؤوسه عناصر من${\displaystyle \mathbb {Z} /m\mathbb {Z} }$رأسان${\displaystyle x{\pmod {m}}}$و${\displaystyle x'{\pmod {m}}}$تكون متصلة إذا وفقط إذا

${\displaystyle x-x'\equiv \pm c\cdot r^{j}{\pmod {m}}}$

أين${\displaystyle c,j\in \mathbb {Z} }$و${\displaystyle 0}$<${\displaystyle c}$<${\displaystyle r}$،${\displaystyle j\geq 0}$ثم إن المسافة المعيارية بين كلمتين هي طول أقصر مسار بين عقدتيهما في الرسم البياني. أما الوزن المعياري للكلمة فهو المسافة بينها وبين العقدة المقابلة لها.${\displaystyle 0}$وهو ما يساوي

${\displaystyle w_{m}(x)=min\{w(y)|y\in \mathbb {Z} ,y\equiv x{\pmod {m}}\}}$

عملياً، قيمة${\displaystyle m}$يتم اختيارها عادة بحيث${\displaystyle m=r^{n}-1}$بما أن معظم العمليات الحسابية الحاسوبية تتم عن طريق الحساب${\displaystyle \mod 2^{n}-1}$لذا لن يكون هناك فقدان إضافي للبيانات نتيجة لخروج الكود عن النطاق، لأن الحاسوب سيكون خارج النطاق أيضاً. اختيار${\displaystyle m=r^{n}-1}$كما يميل ذلك إلى إنتاج رموز بمسافات أكبر من الرموز الأخرى.

باستخدام الوزن المعياري مع${\displaystyle m=r^{n}-1}$، ستكون رموز AN عبارة عن رموز دورية .

التعريف : رمز AN الدوري هو رمز${\displaystyle C}$هذه مجموعة فرعية من${\displaystyle [r^{n}-1]}$، أين${\displaystyle [r^{n}-1]=\{0,1,2,\dots ,r^{n}-1\}}$.

يُعد رمز AN الدوري مثالًا رئيسيًا للحلقة${\displaystyle [r^{n}-1]}$يوجد عدد صحيح${\displaystyle A}$و${\displaystyle B}$أين${\displaystyle AB=r^{n}-1}$و${\displaystyle A,B}$تُحقق تعريف رمز AN. تُعد رموز AN الدورية مجموعة فرعية من الرموز الدورية ولها نفس الخصائص.

تُعدّ رموز ماندلبوم-باروز نوعًا من رموز AN الدورية التي قدّمها د. ماندلبوم وج. ت. باروز. ^{[ 5 ] [ 6 ]} تُنشأ هذه الرموز عن طريق اختيار${\displaystyle B}$أن يكون عددًا أوليًا لا يقسم${\displaystyle r}$بحيث${\displaystyle \mathbb {Z} /B\mathbb {Z} }$يتم إنشاؤه بواسطة${\displaystyle r}$و${\displaystyle -1}$، و${\displaystyle m=r^{n}-1}$. يترك${\displaystyle n}$ليكن عددًا صحيحًا موجبًا حيث${\displaystyle r^{n}\equiv 1{\pmod {B}}}$و${\displaystyle A=(r^{n}-1)/B}$على سبيل المثال، اختيار${\displaystyle r=2,B=5,n=4}$، و${\displaystyle A=(r^{n}-1)/B=3}$ستكون النتيجة رمز ماندلبوم-باروز بحيث${\displaystyle C=\{3N|N\in \mathbb {Z} ,0\leq N}$<${\displaystyle 5\}}$في القاعدة${\displaystyle 2}$.

لتحليل المسافة بين رموز ماندلبوم-باروز، سنحتاج إلى النظرية التالية.

نظرية : ليكن${\displaystyle C\subset [r^{n}-1]}$ليكن رمز AN دوريًا مع مولد${\displaystyle A}$، و

${\displaystyle B=|C|=(r^{n}-1)/A}$

ثم،

${\displaystyle \sum _{x\in C}w_{m}(x)=n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

البرهان : افترض أن كل${\displaystyle x\in C}$يمتلك تمثيلًا دوريًا فريدًا لـ NAF ^{[ 7 ]} وهو

${\displaystyle x\equiv \sum _{i=0}^{n-1}c_{i,x}r^{i}{\pmod {r^{n}-1}}}$

نُعرّف${\displaystyle n\times B}$مصفوفة ذات عناصر${\displaystyle c_{i,x}}$أين${\displaystyle 0\leq i\leq n-1}$و${\displaystyle x\in C}$هذه المصفوفة هي في الأساس قائمة بجميع الكلمات المشفرة في${\displaystyle C}$حيث يمثل كل عمود كلمة رمزية. بما أن${\displaystyle C}$إذا كانت المصفوفة دورية، فإن كل عمود منها يحتوي على نفس عدد الأصفار. يجب علينا الآن حساب${\displaystyle n|\{x\in C|c_{n-1,x}\neq 0\}|}$، وهو${\displaystyle n}$مضروبًا في عدد الكلمات السرية التي لا تنتهي بـ${\displaystyle 0}$كخاصية لوجودها في NAF الدوري،${\displaystyle c_{n-1,x}\neq 0}$إذا كان هناك${\displaystyle y\in \mathbb {Z} }$مع${\displaystyle y\equiv x{\pmod {r^{n}-1}},{\frac {m}{r+1}}}$<${\displaystyle y\leq {\frac {mr}{r+1}}}$. منذ${\displaystyle x=AN{\pmod {r^{n}-1}}}$مع${\displaystyle 0\leq N}$<${\displaystyle B}$، ثم${\displaystyle {\frac {B}{r+1}}}$<${\displaystyle N\leq {\frac {Br}{r+1}}}$ثم عدد الأعداد الصحيحة التي يكون آخر بت فيها صفرًا هو${\displaystyle \lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor }$بضرب هذا في${\displaystyle n}$عدد الأحرف في الكلمات المشفرة يعطينا مجموع أوزان الكلمات المشفرة لـ${\displaystyle n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$حسب الرغبة.

سنستخدم الآن النظرية السابقة لإثبات أن رموز ماندلبوم-باروز متساوية البعد (أي أن كل زوج من الكلمات المشفرة له نفس المسافة)، بمسافة قدرها

${\displaystyle {\frac {n}{B-1}}(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

البرهان : ليكن${\displaystyle x\in C,x\neq 0}$، ثم${\displaystyle x=AN{\pmod {r^{n}-1}}}$و${\displaystyle N}$لا يقبل القسمة على${\displaystyle B}$وهذا يعني وجود${\displaystyle \exists j(N\equiv \pm r^{j}{\pmod {B}})}$. ثم${\displaystyle w_{m}(x)=w_{m}(\pm r^{j}A)=w_{m}(A)}$وهذا يثبت أن${\displaystyle C}$تكون المسافة متساوية لأن جميع الكلمات المشفرة لها نفس الوزن.${\displaystyle A}$بما أن جميع الكلمات المشفرة لها نفس الوزن، وبحسب النظرية السابقة نعرف الوزن الإجمالي لجميع الكلمات المشفرة، فإن مسافة الشفرة يتم إيجادها عن طريق قسمة الوزن الإجمالي على عدد الكلمات المشفرة (باستثناء 0).

• اكتشاف الأخطاء وتصحيحها
• تصحيح الأخطاء الأمامية