Главная
Граница Джонсона определяет предел мощности кода длины n {displaystyle n} и минимального расстояния d {displaystyle d} .
Формулировка
Пусть C {displaystyle C} — q {displaystyle q} -чный код длины n {displaystyle n} над полем F = G F ( q ) {displaystyle mathbb {F} =mathrm {GF} (q)} или, другими словами, подмножество F q n {displaystyle mathbb {F} _{q}^{n}} . Пусть d {displaystyle d} — минимальное расстояние кода C {displaystyle C} , то есть
d = min x , y ∈ C , x ≠ y d ( x , y ) {displaystyle d=min _{x,yin C,;x eq y}{mathsf {d}}(x,y)}где d ( x , y ) {displaystyle {mathsf {d}}(x,y)} — расстояние Хэмминга между кодовыми словами x {displaystyle x} и y {displaystyle y} .
Пусть C q ( n , d ) {displaystyle C_{q}(n,d)} — множество всех q {displaystyle q} -чных кодов длины n {displaystyle n} и минимального расстояния d {displaystyle d} и пусть C q ( n , d , w ) {displaystyle C_{q}(n,d,w)} обозначает подмножество всех равновесных кодов в C q ( n , d ) {displaystyle C_{q}(n,d)} , иными словами, всех кодов, вес всех кодовых слов которых равен w {displaystyle w} .
Обозначим через | C | {displaystyle |C|} количество кодовых слов в C {displaystyle C} , а через A q ( n , d ) {displaystyle A_{q}(n,d)} — максимальную мощность кода длины n {displaystyle n} и минимального расстояния d {displaystyle d} , то есть
A q ( n , d ) = max C ∈ C q ( n , d ) | C | . {displaystyle A_{q}(n,d)=max _{Cin C_{q}(n,d)}|C|.}Похожим образом определим A q ( n , d , w ) {displaystyle A_{q}(n,d,w)} как максимальную мощность кода в C q ( n , d , w ) {displaystyle C_{q}(n,d,w)} :
A q ( n , d , w ) = max C ∈ C q ( n , d , w ) | C | . {displaystyle A_{q}(n,d,w)=max _{Cin C_{q}(n,d,w)}|C|.}Теорема 1 (Граница Джонсона для A q ( n , d ) {displaystyle A_{q}(n,d)} ):
При d = 2 t + 1 {displaystyle d=2t+1}
A q ( n , d ) ≤ q n ∑ i = 0 t ( n i ) ( q − 1 ) i + ( n t + 1 ) − ( d t ) A q ( n , d , d ) A ( n , d , t + 1 ) ( q − 1 ) t + 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}-{d choose t}A_{q}(n,d,d)}{A(n,d,t+1)}}(q-1)^{t+1}}}.}Примечание: для нахождения верхней границы на A q ( n , d ) {displaystyle A_{q}(n,d)} для чётных значений d = 2 t {displaystyle d=2t} можно воспользоваться следующим равенством
A q ( n , 2 t ) = A q ( n − 1 , 2 t − 1 ) . {displaystyle A_{q}(n,2t)=A_{q}(n-1,2t-1).}Теорема 2 (Граница Джонсона для A q ( n , d , w ) {displaystyle A_{q}(n,d,w)} ):
При d > 2 w {displaystyle d>2w}
A q ( n , d , w ) = 1. {displaystyle A_{q}(n,d,w)=1.}При d ≤ 2 w {displaystyle dleq 2w} пускай t = ⌈ d 2 ⌉ {displaystyle t=lceil {frac {d}{2}} ceil } , а также q ∗ = q − 1 {displaystyle q^{*}=q-1} , тогда
A q ( n , d , w ) ≤ ⌊ n q ∗ w ⌊ ( n − 1 ) q ∗ w − 1 ⌊ ⋯ ⌊ ( n − w + t ) q ∗ t ⌋ ⋯ ⌋ ⌋ , {displaystyle A_{q}(n,d,w)leq lfloor {frac {nq^{*}}{w}}lfloor {frac {(n-1)q^{*}}{w-1}}lfloor cdots lfloor {frac {(n-w+t)q^{*}}{t}} floor cdots floor floor ,}где оператор ⌊ ⌋ {displaystyle lfloor ~~ floor } обозначает целую часть числа.
Примечание: подставляя границу теоремы 2 в теорему 1, мы получим верхнюю границу для A q ( n , d ) {displaystyle A_{q}(n,d)} .
Доказательство первой теоремы
Пусть C {displaystyle C} — код длины n {displaystyle n} , мощности M = A q ( n , d ) {displaystyle M=A_{q}(n,d)} с минимальным расстоянием d = 2 t + 1 {displaystyle d=2t+1} , содержащий нулевой вектор. Обозначим через S i {displaystyle S_{i}} множество векторов, находящихся на расстоянии i {displaystyle i} от кода C {displaystyle C} , то есть
S i = { u ∈ F n : ∀ v ∈ C d ( u , v ) ≥ i ∧ ∃ w ∈ C d ( w , u ) = i } . {displaystyle S_{i}=leftlbrace uin F^{n}:forall vin C d(u,v)geq iwedge exists win C d(w,u)=i ight brace .}Таким образом, S 0 = C {displaystyle S_{0}=C} . Тогда S 0 ∪ S 1 ∪ ⋯ ∪ S d − 1 = F n {displaystyle S_{0}cup S_{1}cup dots cup S_{d-1}=F^{n}} , так как если бы нашёлся вектор, находящийся на расстоянии d {displaystyle d} или больше от кода C {displaystyle C} , то мы могли бы добавить его к C {displaystyle C} и получить код ещё большей мощности. Поскольку множества S 0 , S 1 , S 2 , … , S t {displaystyle S_{0},S_{1},S_{2},dots ,S_{t}} не пересекаются, то отсюда следует граница сферической упаковки. Для получения же искомой границы оценим мощность S t + 1 {displaystyle S_{t+1}} .
Выберем произвольное кодовое слово P {displaystyle P} и соответствующим сдвигом кода переведём его в начало координат. Кодовые слова веса d = 2 t + 1 {displaystyle d=2t+1} образуют равновесный код с минимальным расстоянием не менее 2 t + 1 {displaystyle 2t+1} , и поэтому число кодовых слов веса d {displaystyle d} не превышает A q ( n , 2 t + 1 , 2 t + 1 ) = A q ( n , d , d ) {displaystyle A_{q}(n,2t+1,2t+1)=A_{q}(n,d,d)} .
Обозначим через W t + 1 {displaystyle W_{t+1}} множество векторов F n {displaystyle F^{n}} веса t + 1 {displaystyle t+1} . Любой вектор из W t + 1 {displaystyle W_{t+1}} принадлежит либо S t {displaystyle S_{t}} , либо S t + 1 {displaystyle S_{t+1}} . Каждому кодовому слову Q {displaystyle Q} веса d {displaystyle d} соответствуют ( d t ) {displaystyle {d choose t}} векторов веса t + 1 {displaystyle t+1} , находящиеся от Q {displaystyle Q} на расстоянии t {displaystyle t} .
Все эти векторы различны и принадлежат множеству W t + 1 ∩ S t {displaystyle W_{t+1}cap S_{t}} . Следовательно,
| W t + 1 ∩ S t + 1 | = | W t + 1 | − | W t + 1 ∩ S t | ≥ ( n t + 1 ) ( q − 1 ) t + 1 − ( d t ) ( q − 1 ) t + 1 A q ( n , d , d ) . {displaystyle |W_{t+1}cap S_{t+1}|=|W_{t+1}|-|W_{t+1}cap S_{t}|geq {n choose t+1}(q-1)^{t+1}-{d choose t}(q-1)^{t+1}A_{q}(n,d,d).}Вектор R {displaystyle R} из множества W t + 1 ∩ S t + 1 {displaystyle W_{t+1}cap S_{t+1}} находится на расстоянии t + 1 {displaystyle t+1} не более чем от A q ( n , d , t + 1 ) {displaystyle A_{q}(n,d,t+1)} кодовых слов. Действительно, перенесём начало координат в точку R {displaystyle R} и подсчитаем, сколько кодовых слов может находиться от R {displaystyle R} на расстоянии t + 1 {displaystyle t+1} и иметь между собой расстояние Хэмминга d {displaystyle d} . Таковых по определению не должно быть больше A q ( n , d , t + 1 ) {displaystyle A_{q}(n,d,t+1)} . Стало быть, векторы из множества W t + 1 ∩ S t + 1 {displaystyle W_{t+1}cap S_{t+1}} могут учитываться не более A q ( n , d , t + 1 ) {displaystyle A_{q}(n,d,t+1)} раз, то есть каждому кодовому слову P {displaystyle P} соответствуют по крайней мере
( n t + 1 ) − ( d t ) A q ( n , d , d ) A ( n , d , t + 1 ) ( q − 1 ) t + 1 {displaystyle {frac {{n choose t+1}-{d choose t}A_{q}(n,d,d)}{A(n,d,t+1)}}(q-1)^{t+1}}различных векторов на расстоянии t + 1 {displaystyle t+1} от P {displaystyle P} .