Қолданбалы математикада Джонсон байланған (атымен Селмер Мартин Джонсон ) өлшемінің шегі болып табылады қателерді түзететін кодтар, ретінде қолданылған кодтау теориясы үшін деректерді беру немесе байланыс.
Анықтама
Келіңіздер
болуы а q-ары код ұзындығы
, яғни
. Келіңіздер
минималды арақашықтық болуы керек
, яғни
![{displaystyle d = min _ {x, yin C, xeq y} d (x, y),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1a38716c9c6779e7d62b949363f932d1385d229)
қайда
болып табылады Хамминг қашықтығы арасында
және
.
Келіңіздер
бәрінің жиынтығы болыңыз q- ұзындығы бар кодтар
және минималды арақашықтық
және рұқсат етіңіз
кодтар жиынтығын белгілеңіз
кез келген элемент дәл бар
нөлдік жазбалар.
Белгілеу
ішіндегі элементтер саны
. Содан кейін біз анықтаймыз
кодтың ең үлкен өлшемі болуы керек
және минималды арақашықтық
:
![A_ {q} (n, d) = max _ {{Cin C_ {q} (n, d)}} | C |.](https://wikimedia.org/api/rest_v1/media/math/render/svg/e505cd59d8c6cd8a9bf6d0e15da80e0ac5a5d731)
Сол сияқты, біз анықтаймыз
кодтың ең үлкен өлшемі болу керек
:
![A_ {q} (n, d, w) = max _ {{Cin C_ {q} (n, d, w)}} | C |.](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8d3f4dbf158385f0d349a8604eb952beccd5ea4)
Теорема 1 (Джонсон байланысты
):
Егер
,
![A_ {q} (n, d) leq {frac {q ^ {n}} {sum _ {{i = 0}} ^ {t} {n i} (q-1) ^ {i} + {frac таңдаңыз {{n таңдаңыз t + 1} (q-1) ^ {{t + 1}} - {d таңдаңыз t} A_ {q} (n, d, d)} {A_ {q} (n, d, t +1)}}}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd94a658f890cec6d4326f6d0f77e6a0c9b0c6fc)
Егер
,
![A_ {q} (n, d) leq {frac {q ^ {n}} {sum _ {{i = 0}} ^ {t} {n i} (q-1) ^ {i} + {frac таңдаңыз {{n t + 1} (q-1) ^ {{t + 1}}} {A_ {q} (n, d, t + 1)}}}} таңдаңыз.](https://wikimedia.org/api/rest_v1/media/math/render/svg/757818bee850548a0ecf1915e36ecd1537b47ef9)
Теорема 2 (Джонсон байланысты
):
(i) Егер ![{displaystyle d> 2w,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5ecb06b8f8799046b4d238005d635b59ba0a61d)
![A_ {q} (n, d, w) = 1.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7798934790d16b76eec556babb577c7d6cdfe06e)
(ii) Егер
, содан кейін айнымалыны анықтаңыз
келесідей. Егер
тең, содан кейін анықтаңыз
қатынас арқылы
; егер
тақ, анықтаңыз
қатынас арқылы
. Келіңіздер
. Содан кейін,
![{displaystyle A_ {q} (n, d, w) leq leftlfloor {frac {nq ^ {*}} {w}} leftlfloor {frac {(n-1) q ^ {*}} {w-1}} leftlfloor cdots leftlfloor {frac {(n-w + e) q ^ {*}} {e}} ightfloor cdots ightfloor ightfloor ightfloor}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be86f89070883e8c8b885215713492b9da3a2fa2)
қайда
болып табылады еден функциясы.
Ескерту: 2-теореманың шекарасын 1-теореманың шекарасына қосқанда сандық жоғарғы шек пайда болады
.
Сондай-ақ қараңыз
Әдебиеттер тізімі