Глава 5. КОДЫ С МАЛОЙ ПЛОТНОСТЬЮ ПРОВЕРОК НА ЧЕТНОСТЬ С АЛФАВИТОМ ПРОИЗВОЛЬНОГО ОБЪЕМА

Результаты гл. 2, 3 и 4 о двоичных кодах с малой плотностью проверок на четность мы распространим в этой главе на коды с алфавитом произвольного объема. Буквами алфавита будут А-ичные символы, где А — объем алфавита; -ичные символы суть числа от 0 до включительно. Определения -матриц и ансамблей матриц совпадают с определениями гл. 2. Кодовые слова, задаваемые такой матрицей, суть последовательности А-ичных символов, такие, что сумма символов, входящих в проверочное множество, равна 0 по модулю А.

5.1. Функции расстояния

Определим расстояние между двумя последовательностями в коде с алфавитом объема А как число позиций, в которых последовательности различаются. Вес последовательности равен числу символов, отлич от нуля, т. е. расстоянию от нулевой последовательности. Функция расстояния кода определяется снова как число кодовых слов веса Из групповых свойств такого кода следует [12], что число кодовых слов на расстоянии I от любого кодового слова. Для того чтобы получить верхнюю оценку этих кодов, нам потребуется следующая теорема, являющаяся прямым обобщением теоремы 2.3.

Теорема 5.1. Для каждого кода в -ансамбле с алфавитом объема А число последовательностей веса I, удовлетворяющих любому из

блоков по проверок, оценивается следующим образом:

где есть произвольный параметр, а определяется следующим образом:

Доказательство. Рассмотрим фиксированное проверочное множество из символов. Пусть есть число различных последовательностей Л-пч-ных символов длины веса и таких, что сумма компонент каждой равна 0 по модулю А. Покажем сначала, что для произвольного справедливо равенство

Рассмотрим двойную перечисляющую функцию

Ясно, что есть число последовательностей длины содержащее ненулевых А-ичных символов, таких, что их сумма равна Теперь рассмотрим выражение

Сумма в скобках в равенстве (5.6) равна 0 при всех не кратных ввиду равномерного распределения слагаемых по единичному кругу комплексной

плоскости. Если кратно сумма в скобках равна 1. Таким образом,

И наконец, для из выражения (5.4) получаем

Объединяя равенства (5.9) и (5.7), получаем равенство (5.3).

Рассмотрим теперь ансамбль, в котором все А-ичные последовательности длины и удовлетворяющие заданным проверочным соотношениям равновероятны. Тогда для любых символов в проверочном множестве все последовательностей длины удовлетворяющих проверочному соотношению, также равновероятны; из равенства (6.3) получаем поэтому следующее выражение для производящей функции моментов весов этих последовательностей:

Утверждение теоремы теперь получается точно так же, как и в теореме 2.3.

Всего существует А-ичных последовательностей веса таким образом, вероятность того, что выбранная случайным образом последовательность веса I удовлетворит блоку из проверочных соотношений, равна

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

что последовательность веса I будет кодовым словом, равна

Отсюда, следуя построениям гл. 2, можно оценить функцию расстояния и функцию распределения минимального расстояния

где

а задается равенством (5.2).

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