6.7.2. Характеристики гибридного кодирования

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

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

а) Вероятность ошибки. Начнем с отыскания вероятности ошибки. Согласно результатам Юдкина [13], связанным с исследованием вероятности ошибки для алгоритма Фано, вероятность ошибки при последовательном декодировании одного внутреннего блока можно оценить сверху экспоненциальной функцией, стремящейся к нулю с ростом числа избыточных двоичных символов, содержащихся в каждом -символе, поступающем на вход кодера. Используя то, что получаем

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

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

например, Возенкрафт и Джекобе [24]). Используя это неравенство, находим

где

Как нетрудно проверить, при

Отсюда следует, что вероятность ошибки с ростом экспоненциально стремится к нулю. Так как при

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

б) Распределение числа операций. Далее найдем распределение числа операций. Пусть с — число операций, которое необходимо последовательному декодеру для того, чтобы без помощи алгебраического декодера декодировать один внутренний блок. Как следует из разд. 6.4, эта величина имеет распределение Парето

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

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

1) не закончат декодирование предыдущего суперблока;

2) в буферы последовательных декодеров не поступит после окончания приема весь суперблок.

Эти предположения означают, что все суперблоки декодируются независимо и, кроме того, в процессе декодирования

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

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

где Точно так же, как при выводе неравенства (6.142), полагая из формулы (6.138) получаем

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

где

Как следует из определений а также определения [см. формулу (6.144)], при условие всегда выполняется. Учитывая, что величина является вероятностью и поэтому не больше 1, получаем

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

что Сначала найдем среднее значение приведенного числа операций с:

Отсюда и из формулы (6.148) следует, что

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

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

в) Вероятность переполнения буфера. Остановимся на вероятности переполнения буфера при гибридном декодировании. Каждые секунд в декодер поступает один суперблок.

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

Если очередь превышает суперблоков (или символов канала на каждый дискретный канал без памяти), то возникает переполнение буфера. Интересующей нас величиной является -вероятность возникновения переполнения буфера за время декодирования первых суперблоков при условии, что

декодер начинает декодирование очередного суперблока, имея свободный буфер. Верхняя граница для вероятности была получена Фалконером. Эта граница имеет вид

где некоторая постоянная, зависящая от скорости вычислений.

г) Численный пример. В заключение приведем численный пример, иллюстрирующий характеристики гибридного декодера.

Фалконер и Ниссен [26] провели моделирование последовательного декодирования, используя сверточный код со скоростью и осуществляя в канале с отношением сигнал/шум, равным квантование сигнала на восемь уровней. При этом следовательно, Будем считать, что длина внутреннего блока равна 360 ребрам, из которых ребра являются избыточными. Если кодовое ограничение сверточного кода выбрать равным 24 ребрам, то истинная скорость передачи будет равна бит на одно использование канала. (6.151)

Код Рида — Соломона выберем длины со скоростью и алфавитом из символов. В этом случае каждый суперблок будет состоять из 72 кодовых слов кода Рида — Соломона. Из внутреннего блока каждого суперблока пять внутренних блоков являются проверочными. Предположим, что код Рида — Соломона используется только для исправления стираний.

Фалконер и Ниссен экспериментально исследовали распределение суммарного числа операций при декодировании одного внутреннего блока. Согласно полученным ими данными, для канала, отношение сигнал/шум в котором равно вероятность того, что суммарное число операций с при декодировании одного суперблока превысит 36 000, приближенно равна Следовательно, вероятность (с 36000) того, что приведенное число операций, необходимое для декодирования одного суперблока, превысит 36000, равна вероятности того, что среди внутреннего блока шесть или более блоков требуют для своего декодирования более 36000 операций. Эта вероятность находится по формуле

Если для каждого последовательного декодера то за время ввода в буфер нового внутреннего блока декодер может

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

Полагая для вероятности ошибочного декодирования одного внутреннего блока получаем следующую границу:

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