§ 3.4. Кодовые границы

Здесь будет удобно ввести следующие определения. Пусть - система J проверок, ортогональных относительно едля двоичного сверточного кода со

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

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

и, разумеется,

как общее число различных шумовых символов, контролируемых проверками линейные комбинации которых образуют систему

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

где

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

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

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

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

где

В случае теорема И, как и следует ожидать, приводится к теореме 10.

Оценка качества кодов, которые удовлетворяют границам, указанным в соотношении (79) или (77), может быть получена следующим образом. В соответствии с границей Гилберта [соотношение (47)] отношение минимального расстояния к кодовому ограничению можно сделать таким, чтобы удовлетворить равенству Минимальное

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

Рис. 10. Отношение числа ортогональных проверок к удвоенному эффективному кодовому ограничению вычисленному по теоремам 10 и 12, и сравнение этого отношения с асимптотической границей Гильберта. Число около каждой точки указывает величину эффективного кодового ограничения.

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

На рис. 10 отношение определенное теоремами 10 и 11, сравнивается с отношением полученным из асимптотической границы Гилберта в форме (47).

(Правильней было бы сравнивать с неасимптотической границей (43), но такое сравнение трудно представимо графически. К тому же это едва ли повлияло бы на результат, так как при величина для асимптотической и неасимптотической границ приблизительно одинакова. Например, при первая дает 0,55, а вторая Для широкого диапазона скоростей передачи отношение не достигает нижней границы Гилберта, пока эффективное кодовое ограничение не становится величиной порядка 100—150 символов. Можно ожидать, что именно для кодов, эффективное кодовое ограничение которых не превосходит этой величины, пороговое декодирование даст хорошие результаты. Ясно, что для кодов, удовлетворяющих теореме 10 со знаком равенства, отношение в конце концов становится ничтожно малым, так как растет только как квадратный корень из в то время как из рассмотрения границы Гилберта видно, что можно сделать растущим линейно с ростом

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

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

Обратно, невозможно найти такой код, для которого будет меньше этой величины,

Доказательство. Доказательство, что можно сделать столь же малым, как правая часть в равенстве (80), получается простой подстановкой в соотношение (77). Доказательство того, что невозможно добиться лучшего результата, получается следующим образом.

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

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

При матрица состоит из единственного проверочного треугольника

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

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

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

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

Так как то неравенство (83) превращается в

Подставляя (84) в (75), получаем

а это и есть утверждение теоремы.

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