Приложение В. АНАЛИЗ ЧИСЛА НЕЗАВИСИМЫХ ИТЕРАЦИИ ПРИ ДЕКОДИРОВАНИИ

В гл. 4 было получено неравенство (4.19) — асимптотическая оценка вероятности ошибки при использовании метода вероятностного декодирования. Оценка была получена как функция числа итераций при декодировании. В настоящем приложении будут выведены верхняя и нижняя оценки максимального числа итераций при декодировании, которые можно провести для -кода до того, как нарушатся условия независимости теоремы 4.1. Покажем сначала, что в любом -коде оценивается сверху следующим образом:

Затем, и это важнее, мы приведем конструктивный прием, всегда позволяющий найти -код, удовлетворяющий неравенствам

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

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

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

Выражение в левой части неравенства оценивается снизу последним слагаемым, а оно в свою очередь оценивается снизу выражением отсюда

Взяв логарифмы обеих частей неравенства получим неравенство что и доказывает теорему. Ч.Т.Д.

Можно, кроме того, получить точную сумму в неравенстве

Однако неравенство громоздко и потому менее удобно.

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

Рис. В.1. Пример замкнутого пути длины 6, штрихи — единицы, свободное место — нули.

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

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

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

Доказательство первой половины неравенства. Рассмотрим фиксированный замкнутый путь длины Тогда существует вертикальных отрезков, каждый из которых соответствует символу в коде. Перенумеруем эти символы в порядке их появления вдоль замкнутого пути: Для замкнутого пути, показанного на рис. мы имели бы

Рис. В.2. Замкнутый путь рис. В.1 в дереве проверочных множеств.

Рассмотрим дерево проверочных множеств, связанное с символом (см. рис. и рассмотрим два пути в этом дереве, образованные Заметим, что появляется в ярусе в ярусе 1 и вообще и ярусе Если целое,

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

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

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

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

Рис. В.3. Первый шаг метода построения матрицы.

Заметим, что даже в случае главные диагонали содержат символы из-за замкнутых путей длины 4, таких, какой показан на рис. В.3.

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

(кликните для просмотра скана)

Продолжая процесс над строкой 2 подматрицы, заменим некоторые позиции, содержащие символ А (но не на 1, заполним строку и столбец нулями и заменим символы А на там, где это необходимо. Продолжим построение до тех пор, пока каждая строка подматрицы не будет содержать 1, и проделаем то же самое для каждой подматрицы.

Рис. Пример аварийного приема при построении матрицы.

Если на некотором этапе этого процесса попадется строка, скажем 1-я, не содержащая символа А без приписанных к нему нулей, выполним следующий «аварийный» прием. Пусть — столбец, в котором строка I содержит символ Обозначим это следующим образом: где есть, по определению, символ, стоящий на пересечении строки и столбца подматрицы. Для каждого определим как столбец, для которого Найдем теперь такое для которого (см. символы,

заключенные в кружок, на рис. Для этого заменим на на на ОА и изменим символы на ОА во всей матрице в соответствии с новой совокупностью единиц.

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

Рис. Случай 1: замкну путь через

Рис. Случай 2: замкнутый путь через

Первое мы докажем от противного. Допустим, что, положив мы образовали замкнутый путь длины или меньшей. Этот путь должен содержать обе точки как вершины углов, поскольку стоящие ранее в этих позициях символы О А указывали на то, что не существовало замкнутых путей длины или меньшей и проходящих через каждую из этих точек в отдельности. Проследим этот замкнутый путь начиная с точки с вдоль по горизонтальной линии. Следует рассмотреть два случая: 1) путь проходит к вдоль горизонтальной линии, как на рис. и 2) путь проходит к вдоль вертикальной линии, как на рис.

В первом случае положим и оборвем горизонтальную линию, идущую к в точке как на рис. Замкнем путь,

двигаясь вертикально к Этот путь имеет длину, меньшую чем поскольку он короче первоначального пути. Однако это противоречит допущению о том, что была допустимой точкой, когда было равно 1.

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

Чтобы закончить доказательство, мы должны показать, что в том случае, когда удовлетворяется неравенство всегда можно в «аварийной» ситуации найти такое что Сначала покажем, что из неравенства следует существование большего чем числа значений при которых Затем покажем, что больше чем элементов столбца подматрицы суть символы Эти два соотношения завершают доказательство, поскольку в том случае, когда для всех для которых столбец с; подматрицы содержит больше чем элементов, отличных от и больше чем элементов Но это невозможно, поскольку столбец подматрицы содержит всего элементов. Таким образом, должно существовать такое I, что

Оценим теперь число точек строки которые могут быть обозначены символом Если некоторая точка строки подматрицы недопустима, то помещенная в этой точке 1 приведет к образованию замкнутого пути длины или меньшей. Рассмотрим случай, когда первый отрезок этого замкнутого пути есть горизонтальный отрезок вдоль строки ,

начинающийся в недопустимой точке. Тогда последним отрезком будет вертикальный отрезок, оканчивающийся в недопустимой точке. Мы хотим узнать сначала, сколько может быть замкнутых путей длины 4, начинающихся в недопустимой точке строки I подматрицы. Существует самое большее точек, в которых может заканчиваться первый горизонтальный отрезок, а именно это те позиции строки полной матрицы, в которых уже были размещены единицы. Любой вертикальный отрезок, выходящий из одной из этих точек, может заканчиваться самое большее в точках, а именно в оставшихся позициях столбца, в которых размещены единицы. Вспомним, что при такой конструкции мы никогда не размещали больше чем единиц в строке и единиц в столбце. И наконец, если мы хотим построить замкнутый путь длины 4, следующий горизонтальный отрезок, выходящий из одной из этих точек, должен заканчиваться в столбце рассматриваемой подматрицы, но существует самое большее одна единица в любом из таких столбцов, в которой может заканчиваться рассматриваемый горизонтальный отрезок. Таким образом, существует самое большее различных замкнутых путей длины 4, для которых некоторая недопустимая точка строки I заданной подматрицы может служить вершиной угла. Следовательно, из-за этих замкнутых путей длины 4 самое большее точек строки I заданной подматрицы оказываются недопустимыми. Те же аргументы можно использовать при рассмотрении замкнутых путей длины 6. Здесь для любого из путей длины 2 существует самое большее таких точек, в которых может заканчиваться третий отрезок, а для каждой из них существует самое большее точек, в которых может заканчиваться четвертый отрезок. Пятый отрезок теперь вполне определен, поскольку он должен заканчиваться в столбце заданной подматрицы. Отсюда самое большее точек строки в заданной подматрице недопустимы из-за замкнутых путей длины 6. Аналогично замкнутые пути длины приводят к тому, что самое большее

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

Таким образом, если

или

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

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