§ 3.7. Равномерные сверточные коды

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

ортогонализованы и удовлетворяют теореме 7 для случая знака равенства.

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

Строится L наборов строк, причем каждая строка имеет 1 в последней, или позиции. Каждый из первых наборов строк содержит на первых позициях совокупность всех последовательностей длины Последний набор содержит на первых позициях совокупность всех ненулевых последовательностей длины Положим теперь, что строки в (94) суть последние строки в множестве проверочных треугольников. Тогда сами проверочные треугольники должны быть такими, как показано на стр. 86. Они представляют собой проверочные треугольники, соответствующие матрице кода со скоростью где Определим число проверок, ортогональных относительно которые могут быть построены для этого кода.

Чтобы получить проверок размера 2, ортогональных относительно последние строки проверочных треугольников могут быть сложены, как показано в таблице (94).

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

Проверочные треугольники матрицы состоит из строк. На последней позиции все эти строки имеют единицы, а на остальных позициях — все последовательностей длины . В каждом таком наборе строк для каждой строки, начинающейся с единицы, найдется единственная строка, начинающаяся с нуля и совпадающая с первой во всех остальных позициях. Сумма (по модулю два) каждой такой пары строк соответствует проверке, которая контролирует и не контролирует никакой другой шумовой информационный символ. Размер проверки равен двум потому, что складываются две проверки, а это и означает, что контролируются два шумовых проверочных символа. Таким образом, из каждого из

наборов последних строк может быть построено проверок размера 2, ортогональных относительно

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

Этот же процесс можно затем повторить для предпоследних строк проверочных треугольников. Если последние строки таковы, как в таблице (94), то предпоследними будут

и это уже другое множество строк такого же типа, как и в таблице (94) с и Поэтому

из предпоследних строк проверочных треугольников можно построить еще одну систему из проверок размера 2, ортогональных относительно Объединение этой системы с системой, построенной из последних строк, даст систему проверок, ортогональных относительно так как единственный информационный шумовой символ контролируемый этой системой, отличен от единственного информационного шумового символа контролируемого рассмотренной ранее системой.

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

Общее число проверок, ортогональных относительно которые могут быть построены из проверочных треугольников, составляет

Из уравнения (75) находим, что эффективное кодовое ограничение должно быть

Для этого кода откуда

Согласно следствию из теоремы 1, минимальное расстояние не меньше, чем или в нашем случае

не меньше, чем . С другой стороны, из соотношения (53) находим, что

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

Теорема 13. Для любых целых чисел существует сверточный код с минимальным расстоянием

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

Назовем сверточный код с равномерным кодом. Представляется вероятным, что не существует двоичных равномерных сверточных кодов с отличных от кодов, указанных в теореме 13. В табл. III перечислены коды с

Таблица III (см. скан) Некоторые равномерные сверточные коды