Элиас Бассалиго связан - Elias Bassalygo bound

В Элиас Бассалиго связан математический предел, используемый в теория кодирования за исправление ошибки в течение передача данных или коммуникации.

Определение

Позволять ${ displaystyle C}$ быть ${ displaystyle q}$ -арный код длины ${ displaystyle n}$ , т.е. подмножество ${ Displaystyle [д] ^ {п}}$ .^[1] Позволять ${ displaystyle R}$ быть ставка из ${ displaystyle C}$ , ${ displaystyle delta}$ то относительное расстояние и

{ Displaystyle B_ {q} (y, rho n) = left {x in [q] ^ {n} : Delta (x, y) leqslant rho n right }}

быть Мяч Хэмминга радиуса ${ displaystyle rho n}$ сосредоточен на ${ displaystyle y}$ . Позволять ${ displaystyle { text {Vol}} _ {q} (y, rho n) = | B_ {q} (y, rho n) |}$ быть объем шара Хэмминга радиуса ${ displaystyle rho n}$ . Очевидно, что объем шара Хэмминга трансляционно-инвариантен, т.е. безразличен к ${ displaystyle y.}$ Особенно, ${ displaystyle | B_ {q} (y, rho n) | = | B_ {q} (0, rho n) |.}$

С достаточно большим ${ displaystyle n}$ , то ставка ${ displaystyle R}$ и относительное расстояние ${ displaystyle delta}$ удовлетворить Элиас-Бассалыго:

{ Displaystyle R leqslant 1-H_ {q} (J_ {q} ( delta)) + о (1),}

куда

{ displaystyle H_ {q} (x) Equiv _ { text {def}} - x log _ {q} left ({x over {q-1}} right) - (1-x) log _ {q} {(1-x)}}

это q-арная функция энтропии и

{ displaystyle J_ {q} ( delta) Equiv _ { text {def}} left (1- {1 over q} right) left (1 - { sqrt {1- {q delta) over {q-1}}}} right)}

это функция, связанная с Джонсон связан.

Доказательство

Чтобы доказать оценку Элиаса – Бассалиго, начнем со следующей леммы:

Лемма. За

{ Displaystyle С substeq [д] ^ {п}}

и

{ displaystyle 0 leqslant e leqslant n}

, существует шар Хэмминга радиуса

{ displaystyle e}

по крайней мере с

{ displaystyle { frac {| C | { text {Vol}} _ {q} (0, e)} {q ^ {n}}}}

кодовые слова в нем.

Доказательство леммы. Случайно выбрать полученное слово

{ Displaystyle у в [д] ^ {п}}

и разреши

{ displaystyle B_ {q} (y, 0)}

- шар Хэмминга с центром в

{ displaystyle y}

с радиусом

{ displaystyle e}

. С

{ displaystyle y}

(равномерно) случайно выбранный ожидаемый размер перекрывающейся области

{ displaystyle | B_ {q} (y, e) cap C |}

является

{ displaystyle { frac {| C | { text {Vol}} _ {q} (y, e)} {q ^ {n}}}}

Поскольку это ожидаемое значение размера, должен существовать хотя бы один

{ displaystyle y}

такой, что

{ displaystyle | B_ {q} (y, e) cap C | geqslant {{| C | { text {Vol}} _ {q} (y, e)} over {q ^ {n}} } = {{| C | { text {Vol}} _ {q} (0, e)} over {q ^ {n}}},}

в противном случае ожидание должно быть меньше этого значения.

Теперь докажем оценку Элиаса – Бассалыго. Определять ${ displaystyle e = nJ_ {q} ( delta) -1.}$ По лемме существует шар Хэмминга с ${ displaystyle B}$ такие кодовые слова, что:

{ displaystyle B geqslant {{| C | { text {Vol}} (0, e)} over {q ^ {n}}}}

Посредством Джонсон связан, у нас есть ${ Displaystyle B leqslant qdn}$ . Таким образом,

{ displaystyle | C | leqslant qnd cdot {{q ^ {n}} over {{ text {Vol}} _ {q} (0, e)}} leqslant q ^ {n (1-H_ {q} (J_ {q} ( delta)) + o (1))}}

Второе неравенство следует из нижней оценки объема шара Хэмминга:

{ displaystyle { text {Vol}} _ {q} left (0, left lfloor { frac {d-1} {2}} right rfloor right) leqslant q ^ {H_ {q } left ({ frac { delta} {2}} right) no (n)}.}

Вставка ${ displaystyle d = 2e + 1}$ и ${ displaystyle delta = { tfrac {d} {n}}}$ дает второе неравенство.

Поэтому у нас есть

{ displaystyle R = { log _ {q} {| C |} over n} leqslant 1-H_ {q} (J_ {q} ( delta)) + о (1)}

Смотрите также

Рекомендации

^ Каждый ${ displaystyle q}$ -арный блочный код длины ${ displaystyle n}$ является подмножеством строк ${ displaystyle { mathcal {A}} _ {q} ^ {n},}$ где установлен алфавит ${ displaystyle { mathcal {A}} _ {q}}$ имеет ${ displaystyle q}$ элементы.

Бассалыго, Л. А. (1965), "Новые верхние границы для кодов с исправлением ошибок", Проблемы передачи информации, 1 (1): 32–35

Клод Э. Шеннон, Роберт Г. Галлагер; Берлекамп, Элвин Р. (1967), "Нижние границы вероятности ошибки для кодирования на дискретных каналах без памяти. Часть I.", Информация и контроль, 10: 65–103, Дои:10.1016 / с0019-9958 (67) 90052-6

Клод Э. Шеннон, Роберт Г. Галлагер; Берлекамп, Элвин Р. (1967), "Нижние границы вероятности ошибки для кодирования на дискретных каналах без памяти. Часть II.", Информация и контроль, 10: 522–552, Дои:10.1016 / с0019-9958 (67) 91200-4

[1] Каждый ${ displaystyle q}$ -арный блочный код длины ${ displaystyle n}$ является подмножеством строк ${ displaystyle { mathcal {A}} _ {q} ^ {n},}$ где установлен алфавит ${ displaystyle { mathcal {A}} _ {q}}$ имеет ${ displaystyle q}$ элементы.

[1]