3.10. Границы для ансамблей линейных кодов

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

В двоичном линейном коде с векторами, как это было, определено в § 2.9, кодовые векторы порождаются некоторой линейной алгебраической операцией над векторами информационных символов причем последние лексикографически ассоциируются со всеми возможными двоичными векторами от до Обобщим определение линейных кодов, приведенное в § 2.9, лрибавцв к каждому кодовому вектору постоянный вектор т. е.

где

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

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

где пространство всех возможных наборов сигналов, порожденных (3.10.1). Подставив в (3.10.2) границу вероятности ошибки для фиксированного набора сигналов (3.1.4) для получим

Но вектор

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

где пространство всех наборов сигналов, порожденных (3.10.1) при фиксированном Воспользовавшись определением (3.1.6) при аналогично (3.1.7) и (3.1.9) найдем следующую оценку для выражения в скобках в неравенстве (3.10.4)

Однако ясно, что при любое заданное наперед значение можно получить, выбирая некоторую вектор-строку матрицы как

подходящую функцию остальных вектор-строк. Этим выбор оставшихся векторов сужается до Поэтому

Воспользовавшись определением (3.1.6) и комбинируя получим

что совнадает с (3.1.10) при Ясно, что точно так же можно оценить и просто заменив всюду индекс 1 на оставшаяся часть вывода» верхней границы среднего по ансамблю совпадает с ее выводом для более широкого ансамбля всех кодов. Таким образом, все результаты, полученные в § 3.2, остаются справедливыми и для двоичных линейных кодов что выполняется для симметричных по выходу каналов. Приведенная граница, как показано в § 3.6, асимптотически точна для этого класса каналов при всех скоростях

В более широком ансамбле всех блочных кодов мы улучшали верхнюю границу при малых скоростях (см. § 3.3), применяя выбрасывание. Для двоичных линейных кодов вывод границы с выбрасыванием, однако, проще общего доказательства (см. § 3.3). В действительности здесь вообще нет необходимости в выбрасывании кодовых слов. Неравенство (2.3.16) задает границу Бхаттачария вероятности ошибки сообщения для линейного кода с кодовыми словами, используемого для передачи по каналу без памяти с двоичным входом. Для двоичных кодовых векторов тогда получим

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

Для всякого линейного кода вида

из (2.9.10) для любого получим

Поэтому

для Поскольку эта граница одинакова для всех кодовых слов, имеем

Заметим, что это неравенство совпадает с (2.9.19), но справедливо для произвольного канала без памяти с двоичным входом, не обязательно симметричного по выходу.

Введя обозначение

и параметр получим неравенство (см. приложение

Как так и ее граница (3.10.14) зависят от конкретного генератора кода что было показано в (3.10.10). Усредним теперь и ее границу по ансамблю всех возможных двоичных линейных кодов, содержащему членов, соответствующих всем различимым Среднее от (3.10.14) по всем возможным линейным кодам задается соотношением

где мы просуммировали по пространству всех возможных порождающих матриц Заметив, что каждая порождающая матрица состоит из К строк размерности можно следующим образом выразить (3.10.15) через вектор-строки порождающих матриц:

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

просуммировав строки для которых придем к -кратному повторению каждого из возможных -мерных векторов Поэтому

Объединяя (3.10.16) и (3.10.17) и используя неравенство получим

Следовательно, существует по крайней мере один линейный код, для которого

выбирая параметр имеем

где

Минимизируя по получим, что существует хотя бы один двоичны линейный код, для которого

где

что аналогично (3.3.12) и (3.3.13) для рассматриваемого класса каналов и задается параметрически соотношением (3.4.8), в котором определена (3.10.13).

Таким образом, для линейных блочных кодов, используемых в симметричных по выходу каналах, мы получили верхнюю границу среднего по ансамблю, выведенную в § 3.1, и показали, что оценка выбрасыванием, выведенная в § 3.3, справедлива независимо от того, является ли канал симметричным выходу. В трех последующих главах рассмотрим специальный класс линейны кодов, допускающих удобное декодирование и имеющих лучшие, чем у линейных блочных кодов, характеристики.