Глава 2. ФУНКЦИИ РАССТОЯНИЯ

Функция расстояния для кода с проверками на четность определяется как число кодовых слов веса Из групповых свойств кода с проверками на четность легко следует [12], что есть также число кодовых слов, находящихся на расстоянии от любого кодового слова. Тогда определим минимальное расстояние кода как наименьшее для которого Ясно, что в коде с заданной длиной блока и со скоростью желательно сделать возможно большим, а для тех которые превышают сделать возможно меньшим. В следующей главе, где обсуждаются оценки вероятности ошибки декодирования в симметричных каналах с двоичным входом, станет более ясной точная связь со способностью кода исправлять ошибки.

Для кодов большой длины с проверками на четность из-за огромного числа кодовых слов обычно практически невозможно точно вычислить функцию расстояния или даже минимальное расстояние. Часто проще исследовать среднюю по ансамблю кодов функцию расстояния, поскольку статистические свойства ансамбля допускают осреднение тех величин, которые не поддаются анализу в конкретном коде. По средним можно сделать некоторые выводы статистического характера об отдельных кодах, входящих в ансамбль.

2.1. Ансамбль равновероятных кодов с проверками на четность

В этой главе рассматриваются в основном функции расстояния кодов с малой плотностью проверок на четность, однако для сравнения мы получим

сначала осредненную функцию расстояния для другого ансамбля кодов с проверками на четность. Поскольку код с проверками на четность полностью задается проверочной матрицей, ансамбль кодов с проверками на четность можно определить посредством ансамбля проверочных матриц.

Ансамбль равновероятных кодов с проверками на четность со скоростью и длиной блока определим как ансамбль проверочных матриц, элементами которых являются независимые и равновероятные двоичные символы. По существу, этот ансамбль совпадает с ансамблем, рассматривавшимся Элайесом [3] при построении оценок случайного кодирования для кодов с проверками на четность. Незначительное отличие нашего ансамбля заключается в том, что входящие в него коды могут иметь скорость, немного превышающую поскольку строки матриц в этом ансамбле не обязательно линейно независимы над полем чисел по модулю 2.

Теорема 2.1. Пусть есть среднее число кодовых слов веса I в ансамбле равновероятных кодов с проверками на четность со скоростью и длиной блока Тогда для имеем

Доказательство. Пусть есть вероят ность множества кодов, для которых некоторая фиксированная последовательность веса есть кодовое слово. Иначе говоря, есть вероятность того, что фиксированная последовательность веса I окажется кодовым словом кода, выбранного случайным образом из ансамбля. Поскольку последовательность,

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

Вероятность можно также интерпретировать как математическое ожидание случайной величины, принимающей значение 1, если последовательность принадлежит коду, и 0 в противном случае. Заметим теперь, что всего существует последовательностей веса и что среднее число кодовых слов среди этих последовательностей равно сумме вероятностей того, что каждая последовательность принадлежит коду; таким образом,

Оценим теперь по формуле Стирлинга

После некоторых преобразований получим для

где

Объединяя соотношения (2.2) и (2.4), получим утверждение теоремы. Ч.Т.Д.

Заметим теперь, что в ансамбле равновероятных кодов с проверкой на четность минимальное расстояние кода есть случайная величина; ее функция распределения оценивается в следующей теореме.

Теорема 2.2. В ансамбле равновероятных кодов с проверками на четность со скоростью и длиной блока функция распределения минимального расстояния оценивается при целом двумя следующими неравенствами:

Доказательство. В теореме 2.1 было показано, что в ансамбле кодов вероятность того, что ненулевая последовательность есть кодовое слово, равна Вероятность того, что некоторая последовательность веса или меньше, есть кодовое слово, безусловно, меньше суммы вероятностей того, что каждая из последовательностей является кодовым словом. Поэтому

Это выражение мажорируется геометрической прогрессией, и мы получаем таким образом

Оценив правую часть неравенства (2.7) с помощью неравенства (2.4) и подставив результат в неравенство (2.6), получим утверждение теоремы. Ч.Т.Д.

С ростом эта оценка как функция сходится к ступенчатой функции со скачком при » Для которого Зависимость от скорости приведена на рис. 2.4. Этот результат тесно связан с границей Гилберта для минимального расстояния [6].

Асимптотическая форма границы Гилберта утверждает, что для больших существует код, для которого Теорема 2.2 утверждает, что для любого вероятность множества кодов с проверками на четность, для которых , стремится к О экспоненциально с ростом