Позволять быть -арный код длины , т.е. подмножество . [1] Пустьбыть скорость из, относительное расстояние и
- шар Хэмминга радиуса сосредоточен на . Позволять- объем шара Хэмминга радиуса. Очевидно, что объем шара Хэмминга трансляционно-инвариантен, т.е. В частности,
С достаточно большим , ставкаи относительное расстояниеудовлетворить границу Элиаса-Бассалыго:
Чтобы доказать оценку Элиаса – Бассалиго, начнем со следующей леммы:
Лемма. Для а также , существует шар Хэмминга радиуса по крайней мере с
кодовые слова в нем.
Доказательство леммы. Случайно выбрать полученное слово и разреши - шар Хэмминга с центром в с радиусом . С (равномерный) случайно выбранный ожидаемый размер перекрывающейся области является
Поскольку это ожидаемое значение размера, должен существовать хотя бы один такой, что
в противном случае ожидание должно быть меньше этого значения.
Теперь докажем оценку Элиаса – Бассалиго. Определять По лемме существует шар Хэмминга с такие кодовые слова, что:
^ Каждый-арный блочный код длины является подмножеством строк где установлен алфавит имеет элементы.
Бассалыго, Л.А. (1965), "Новые верхние границы для кодов, исправляющих ошибки", Проблемы передачи информации , 1 (1): 32–35
Клод Э. Шеннон, Роберт Г. Галлагер; Берлекемпа, Элвин Р. (1967), "Нижние оценки для вероятности ошибки для кодирования на дискретных каналов без памяти. Часть I.", информации и управления , 10 : 65-103, DOI : 10.1016 / s0019-9958 (67) 90052-6
Клод Э. Шеннон, Роберт Г. Галлагер; Берлекемпа, Элвин Р. (1967), "Нижние границы для вероятности ошибки для кодирования на дискретных каналов без памяти Часть II..", Информации и управления , 10 : 522-552, DOI : 10.1016 / s0019-9958 (67) 91200-4