Приложение В. ДОКАЗАТЕЛЬСТВО ТЕОРЕМ 10 И 11

1. Доказательство теоремы 10

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

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

следующие шумовые символы:

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

Рис. В.1. Геометрическая интерпретация структуры проверок.

Рис. В.2. Расположение проверочных треугольников в матрице

Заметим, что, выбрав достаточно большим, индекс шумового символа, соответствующего точке X, можно сделать сколь угодно большим, а индексы всех других контролируемых шумовых символов будут иметь большие значения.

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

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

Построение I проверок, ортогональных относительно можно выполнить следующим образом.

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

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

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

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

Наконец, используя равенство и тот факт, что приводим выражение к виду

что и требовалось доказать.

2. Доказательство теоремы 11

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

Рис. В.3. Геометрическая интерпретация структуры проверок.

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

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

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

Если положить

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

Наконец, используя равенство и тот факт, что можно привести равенство к виду

что и требовалось доказать.