رمز المنطقة

يتم نمذجة تدفق البيانات المراد ترميزه كسلسلة نصية تتكون من أبجدية معينة .${\displaystyle \Sigma }$الحجم${\displaystyle |\Sigma |}$غالباً ما تُكتب حروف الأبجدية على النحو التالي:${\displaystyle q}$. لو${\displaystyle q=2}$عندئذٍ يُطلق على رمز الكتلة اسم رمز الكتلة الثنائي . في العديد من التطبيقات، من المفيد مراعاة${\displaystyle q}$أن تكون قوة رئيسية ، وأن تحدد${\displaystyle \Sigma }$مع الحقل المنتهي${\displaystyle \mathbb {F} _{q}}$.

الرسائل هي عناصر${\displaystyle m}$ل${\displaystyle \Sigma ^{k}}$أي سلاسل ذات طول${\displaystyle k}$ومن هنا جاء الرقم${\displaystyle k}$يُطلق عليه طول الرسالة أو بُعد رمز الكتلة.

طول الكتلة${\displaystyle n}$عدد الرموز في الكتلة هو عدد الرموز الموجودة فيها. ومن ثم، فإن العناصر${\displaystyle c}$ل${\displaystyle \Sigma ^{n}}$هي سلاسل ذات طول${\displaystyle n}$وتتوافق مع الكتل التي قد يستقبلها جهاز الاستقبال. ولذلك تُسمى أيضًا بالكلمات المستلمة. إذا${\displaystyle c=C(m)}$لبعض الرسائل${\displaystyle m}$، ثم${\displaystyle c}$يُطلق عليه اسم كلمة السر لـ${\displaystyle m}$.

يُعرَّف معدل رمز الكتلة بأنه النسبة بين طول الرسالة وطول الكتلة :

${\displaystyle R=k/n}$.

يشير المعدل المرتفع إلى أن كمية الرسالة الفعلية في كل كتلة مُرسلة كبيرة. وبهذا المعنى، يقيس المعدل سرعة الإرسال وكمية البيانات.${\displaystyle 1-R}$يقيس هذا المعدل العبء الإضافي الناتج عن التشفير باستخدام رمز الكتلة. ومن الحقائق النظرية البسيطة في مجال المعلومات أن هذا المعدل لا يمكن أن يتجاوز${\displaystyle 1}$بما أن البيانات لا يمكن ضغطها بشكل عام دون فقدان البيانات. رسميًا، هذا ينبع من حقيقة أن الكود${\displaystyle C}$هي دالة حقنية.

المسافة أو الحد الأدنى للمسافة d لرمز الكتلة هي أقل عدد من المواضع التي يختلف فيها أي كلمتين رمزيتين مختلفتين، والمسافة النسبية${\displaystyle \delta }$الكسر${\displaystyle d/n}$رسميًا، بالنسبة للكلمات الموروثة${\displaystyle c_{1},c_{2}\in \Sigma ^{n}}$، يترك${\displaystyle \Delta (c_{1},c_{2})}$تشير إلى مسافة هامينغ بين${\displaystyle c_{1}}$و${\displaystyle c_{2}}$أي عدد المواضع التي${\displaystyle c_{1}}$و${\displaystyle c_{2}}$تختلف. ثم المسافة الدنيا${\displaystyle d}$من الكود${\displaystyle C}$يُعرَّف بأنه

${\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}$.

بما أن أي رمز يجب أن يكون أحاديًا ، فإن أي كلمتين رمزيتين ستختلفان في موضع واحد على الأقل، لذا فإن المسافة بين أي رمز هي على الأقل${\displaystyle 1}$إضافة إلى ذلك، فإن المسافة تساوي الحد الأدنى للوزن بالنسبة لرموز الكتل الخطية لأن:

$\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [\mathbf {0} ,C(m_{2})-C(m_{1})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}$.

تتيح المسافة الأكبر تصحيحًا واكتشافًا أفضل للأخطاء. على سبيل المثال، إذا اقتصرنا على الأخطاء التي قد تُغير رموز الكلمة المشفرة المُرسلة دون حذفها أو إضافتها، فإن عدد الأخطاء هو عدد المواضع التي تختلف فيها الكلمة المشفرة المُرسلة عن الكلمة المُستلمة. يسمح رمز بمسافة d للمُستقبِل باكتشاف ما يصل إلى${\displaystyle d-1}$أخطاء في الإرسال منذ التغيير${\displaystyle d-1}$لا يمكن أن تؤدي مواقع كلمة السر إلى كلمة سر أخرى عن طريق الخطأ. علاوة على ذلك، إذا لم يكن هناك أكثر من${\displaystyle (d-1)/2}$في حال حدوث أخطاء في الإرسال، يستطيع جهاز الاستقبال فك تشفير الكلمة المستلمة بشكل فريد إلى كلمة رمزية. وذلك لأن كل كلمة مستلمة تحتوي على كلمة رمزية واحدة على الأكثر عند هذه المسافة.${\displaystyle (d-1)/2}$إذا كان أكثر من${\displaystyle (d-1)/2}$عند حدوث أخطاء في الإرسال، لا يستطيع جهاز الاستقبال فك تشفير الكلمة المستلمة بشكل فريد، إذ قد يكون هناك عدة كلمات رمزية محتملة. إحدى طرق معالجة هذه المشكلة هي استخدام فك التشفير القائم على القوائم ، حيث يُخرج جهاز فك التشفير قائمة بجميع الكلمات الرمزية ضمن نطاق محدد.

الترميز${\displaystyle (n,k,d)_{q}}$يصف رمز الكتلة على الأبجدية${\displaystyle \Sigma }$من الحجم${\displaystyle q}$، بطول كتلة${\displaystyle n}$طول الرسالة${\displaystyle k}$والمسافة${\displaystyle d}$إذا كان رمز الكتلة رمز كتلة خطي، فإن الأقواس المربعة في الترميز${\displaystyle [n,k,d]_{q}}$تُستخدم لتمثيل تلك الحقيقة. بالنسبة للرموز الثنائية مع${\displaystyle q=2}$أحيانًا يتم حذف الفهرس. بالنسبة للرموز القابلة للفصل ذات المسافة القصوى ، تكون المسافة دائمًا${\displaystyle d=n-k+1}$لكن في بعض الأحيان تكون المسافة الدقيقة غير معروفة، أو يصعب إثباتها أو تحديدها، أو لا تكون ضرورية. في مثل هذه الحالات،${\displaystyle d}$قد يكون المكون مفقودًا.

في بعض الأحيان، وخاصة بالنسبة للرموز غير الكتلية، يكون الترميز${\displaystyle (n,M,d)_{q}}$يُستخدم للرموز التي تحتوي على${\displaystyle M}$كلمات سرية ذات طول${\displaystyle n}$بالنسبة لرموز الكتل ذات الرسائل ذات الطول${\displaystyle k}$أكثر من أبجدية بحجم${\displaystyle q}$، سيكون هذا الرقم${\displaystyle M=q^{k}}$.

${\displaystyle C=\{C_{i}\}_{i\geq 1}}$يُطلق عليها اسم عائلة الرموز ، حيث${\displaystyle C_{i}}$هو${\displaystyle (n_{i},k_{i},d_{i})_{q}}$رمز ذو زيادة رتيبة${\displaystyle n_{i}}$.

يُعرَّف معدل عائلة الرموز C على النحو التالي:${\displaystyle R(C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}$

تُعرَّف المسافة النسبية لمجموعة الرموز C على النحو التالي:${\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}$

لاستكشاف العلاقة بين${\displaystyle R(C)}$و${\displaystyle \delta (C)}$، مجموعة من الحدود الدنيا والعليا لرموز الكتل معروفة.

${\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2}\right\rfloor }{\binom {n}{i}}(q-1)^{i}\right]}$

الحدّ المفرد هو أن مجموع معدل و المسافة النسبية لرمز الكتلة لا يمكن أن يكون أكبر بكثير من 1:

${\displaystyle R+\delta \leq 1+{\frac {1}{n}}}$.

بمعنى آخر، كل رمز كتلة يحقق المتباينة${\displaystyle k+d\leq n+1}$تُعد رموز ريد-سولومون أمثلة غير تافهة للرموز التي تحقق حد المفردة مع المساواة.

ل${\displaystyle q=2}$،${\displaystyle R+2\delta \leq 1}$. بعبارة أخرى،${\displaystyle k+2d\leq n}$.

في الحالة العامة، تنطبق حدود بلوتكين التالية على أي${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$بمسافة d :

1. لو${\displaystyle d=\left(1-{1 \over q}\right)n,|C|\leq 2qn}$
2. لو${\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}$

لأي رمز q -ary بمسافة${\displaystyle \delta }$،${\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}$

${\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }$، أين${\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}$، ${\displaystyle H_{q}\left(x\right)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x\right)\cdot \log _{q}{\left(1-x\right)}}$هي دالة الإنتروبيا من الرتبة q .

يُعرِّف${\displaystyle J_{q}\left(\delta \right)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}$. يترك${\displaystyle J_{q}\left(n,d,e\right)}$ليكن الحد الأقصى لعدد الكلمات المشفرة في كرة هامينغ نصف قطرها e لأي رمز${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$مسافة د .

ثم لدينا جونسون باوند  :${\displaystyle J_{q}\left(n,d,e\right)\leq qnd}$، لو${\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}\left({d \over n}\right)}$

${\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}$