متجه إلى جونسون

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

يترك${\displaystyle C}$ليكن رمزًا من النوع q بطول${\displaystyle n}$أي مجموعة فرعية من${\displaystyle \mathbb {F} _{q}^{n}}$. يترك${\displaystyle d}$أن تكون المسافة الدنيا لـ${\displaystyle C}$، أي

${\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y),}$

أين${\displaystyle d(x,y)}$هي مسافة هامينغ بين${\displaystyle x}$و${\displaystyle y}$.

يترك${\displaystyle C_{q}(n,d)}$لتكن مجموعة جميع الرموز q -ary ذات الطول${\displaystyle n}$والمسافة الدنيا${\displaystyle d}$ودع${\displaystyle C_{q}(n,d,w)}$تشير إلى مجموعة الرموز في${\displaystyle C_{q}(n,d)}$بحيث يكون لكل عنصر بالضبط${\displaystyle w}$المدخلات غير الصفرية.

يرمز بـ${\displaystyle |C|}$عدد العناصر في${\displaystyle C}$ثم نُعرّف${\displaystyle A_{q}(n,d)}$أن يكون أكبر حجم لرمز بطول${\displaystyle n}$والمسافة الدنيا${\displaystyle d}$:

${\displaystyle A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.}$

وبالمثل، نُعرّف${\displaystyle A_{q}(n,d,w)}$أن يكون أكبر حجم للبرنامج في${\displaystyle C_{q}(n,d,w)}$:

${\displaystyle A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.}$

النظرية 1 (حدود جونسون لـ${\displaystyle A_{q}(n,d)}$):

لو${\displaystyle d=2t+1}$،

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}-{d \choose t}A_{q}(n,d,d)}{A_{q}(n,d,t+1)}}}}.}$

لو${\displaystyle d=2t+2}$،

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}}{A_{q}(n,d,t+1)}}}}.}$

النظرية 2 (حدود جونسون لـ${\displaystyle A_{q}(n,d,w)}$):

(أ) إذا${\displaystyle d>2w,}$

${\displaystyle A_{q}(n,d,w)=1.}$

(ii) إذا${\displaystyle d\leq 2w}$ثم قم بتعريف المتغير${\displaystyle e}$على النحو التالي. إذا${\displaystyle d}$إذا كان زوجيًا، فحدد${\displaystyle e}$من خلال العلاقة${\displaystyle d=2e}$؛ لو${\displaystyle d}$غريب، عرّف${\displaystyle e}$من خلال العلاقة${\displaystyle d=2e-1}$. يترك${\displaystyle q^{*}=q-1}$. ثم،

${\displaystyle A_{q}(n,d,w)\leq \left\lfloor {\frac {nq^{*}}{w}}\left\lfloor {\frac {(n-1)q^{*}}{w-1}}\left\lfloor \cdots \left\lfloor {\frac {(n-w+e)q^{*}}{e}}\right\rfloor \cdots \right\rfloor \right\rfloor \right\rfloor }$

أين${\displaystyle \lfloor ~~\rfloor }$هي دالة الأرضية .

ملاحظة: إن إدخال حد النظرية 2 في حد النظرية 1 ينتج عنه حد أعلى عددي لـ${\displaystyle A_{q}(n,d)}$.

• إلياس باساليغو متجه
• متجه جيلبرت-فارشاموف
• مقيد بجريسمر
• هامينغ باوند
• بلوتكين المقيد
• متجهة إلى سينغلتون

• جونسون، سيلمر مارتن (أبريل 1962). "حد أعلى جديد لرموز تصحيح الأخطاء". معاملات معهد مهندسي الراديو في نظرية المعلومات : 203-207 .
• هوفمان، ويليام كاري؛ بليس، فيرا س. (2003). أساسيات رموز تصحيح الأخطاء . مطبعة جامعة كامبريدج . ISBN 978-0-521-78280-7.