کران جانسون

در ریاضیات کاربردی ، محدود جانسون (به افتخار سلمر مارتین جانسون به این صورت نام گذاری شده است) محدودیتی در اندازه  کدهای تصحیح خطا مورد استفاده در نظریه کدگذاری برای انتقال داده ها و یا ارتباطات است.

تعریف

${\displaystyle }$ یک کد با q زیرشاخه و طول ${\displaystyle }$یعنی یک زیر مجموعه از ${\displaystyle }$. ${\displaystyle }$ را حداقل فاصله از ${\displaystyle }$یعنی؛

${\displaystyle }$

که در آن ${\displaystyle }$ فاصله همینگ بین ${\displaystyle }$ و ${\displaystyle }$.

${\displaystyle }$ را مجموعه ای از تمام کد ها با q زیرشاخه به طول ${\displaystyle }$ و حداقل فاصله ${\displaystyle }$ در نظر بگیرید و ${\displaystyle }$ نشان دهنده مجموعه ای از کدها در ${\displaystyle }$  باشد، به طوری که هر عنصر دقیقاً شامل  با ${\displaystyle }$ ورودی غیر صفر باشد.

${\displaystyle }$ را به عنوان نماد تعداد عناصر در ${\displaystyle }$. سپس ${\displaystyle }$ را به عنوان بزرگترین اندازه یک کد با طول ${\displaystyle }$ و حداقل فاصله ${\displaystyle }$:

${\displaystyle }$

به طور مشابه، ${\displaystyle }$ را بزرگترین اندازه یک کد در ${\displaystyle }$:

${\displaystyle }$

قضیه 1 (محدوده جانسون برای ${\displaystyle }$)

اگر ${\displaystyle }$با

${\displaystyle }$

اگر ${\displaystyle }$

${\displaystyle }$

قضیه 2 (محدوده جانسون برای ${\displaystyle }$)

(i) اگر ${\displaystyle }$

${\displaystyle }$

(ii) اگر ${\displaystyle }$سپس متغیر ${\displaystyle }$ به شرح زیر تعریف می کنیم. اگر ${\displaystyle }$ زوج است، پس؛ ${\displaystyle }$ از طریق رابطه ${\displaystyle }$اگر ${\displaystyle }$است، ${\displaystyle }$ را از طریق رابطه${\displaystyle }$. ${\displaystyle }$. داریم:

${\displaystyle }$

که در آن ${\displaystyle }$ تابع جزء صحیح است.

تبصره: اتصال محدوده قضیه 2 به محدوده قضیه 1 کران بالای عددی روی ${\displaystyle }$.

جستارهای وابسته

• محدوده سینگلتون
• محدوده همینگ
• محدوده پلوتکین
• محدوده الیاس باسالگو
• محدوده گیلبرت–وارشاموگ
• محدوده گریسمر

منابع

• Johnson, Selmer Martin (April 1962). "A new upper bound for error-correcting codes". IRE Transactions on Information Theory: 203–207.
• Huffman, William Cary; Pless, Vera S. (2003). Fundamentals of Error-Correcting Codes. Cambridge University Press. ISBN 978-0-521-78280-7.