4. Граница Гилберта

Хотя и не ясно, как можно построить порождающий элемент, максимизирующий минимальное число единиц в любой последовательности из для больших все же возможно (следуя Гилберту) вычислить нижнюю границу для Рассмотрим совокупность всех образующих последовательностей. Каждое должно задавать не больше различных последовательностей из (некоторые могут совпадать, как это, например, имеет место при Далее, если мы рассмотрим групповое дерево 5 с точки зрения базисных элементов, то любая последовательность и все ее сдвиги будут линейно независимы в том случае, когда первый символ равен 1. Это верно, так как из того, что вытекает, что где первый символ в любой последовательности (Ясно, что если то первый столбец в 5 тождественно равен нулю и длина кодовых ограничений равна, по существу, а не Таким образом, весь усеченный код и в частности не зависит от того, какое именно выбирается в действительности

в качестве порождающего элемента. Единственным результатом перехода от является новое переупорядочение последовательностей в

Из предыдущего следует, что если выбрать два различных порождающих элемента, то подмножества задаваемые этими элементами, будут или совпадающими или непересекающимися. Так как всего имеется возможных порождающих элементов, для которых то должно быть

непересекающихся подмножеств где, как обычно, решение уравнения (2.14).

Число последовательностей состоящих из двоичных символов и имеющих или меньше единиц, дается формулой

где индекс 1 означает, как и прежде, вероятность, вычисляемую в предположении, что Используя уравнение получаем

Наиболее неблагоприятное положение возникло бы в том случае, когда одна и только одна из V возможных последовательностей имеющих или меньше единиц, встречается в любом из возможных непересекающихся кодов. В любом случае мы можгм быть уверены в том, что существует порождающий элемент для которого если

В соответствии с этим существует, по крайней мере одно подмножество с

и при передаче может быть исправлено, по крайней мере, ошибок.

Граница Гилберта была выведена (см. работы [6] и [11]) для других классов кодов, причем были получены результаты, асимптотически эквивалентные неравенству (4.7). Таким образом, сверточные коды имеют с блоковыми групповыми кодами не только общую экспоненту в осредненной по ансамблю вероятности ошибки, но также и общую минимальную гарантированную способность к исправлению ошибок.