§ 6.2. Коды максимальной длины

В § 3.7 было показано, что равномерные двоичные сверточные коды могут быть полностью ортогонализованы. Эти коды обладают тем свойством, что их минимальное расстояние совпадает со средним расстоянием. Представляется естественным начать наш анализ блоковых кодов с того класса кодов, для которых минимальное расстояние между кодовыми словами также совпадает с их средним расстоянием, а именно с кодов максимальной длины. Эти коды получили свое название потому, что их кодовые слова можно рассматривать как первые выходных символов -разрядного генератора последовательностей максимальной длины, в который в качестве начальных условий вводятся информационных символов [12, стр. 166—167], причем все символы принадлежат полю

Можно рассмотреть блоковый -код, являющийся частным случаем сверточного кода, для которого Тогда из формулы (53) следует, что среднее расстояние между кодовыми словами блокового -кода дается формулой

Так как для кода максимальной длины то из равенства (180) имеем .

Проверочная матрица кода максимальной длины такова, что строки матрицы суть все ненулевых последовательностей длины к,

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

строк матрицы то его проверочной матрицей является где означает транспонирование матрицы [12, стр. 49]. Значит, матрица в качестве своих строк имеет множество всех ненулевых последовательностей длины кроме единичных векторов, а это как раз и есть то свойство, которое надо было установить.

Например, проверочной матрицей двоичного -кода максимальной длины является матрица

и она имеет форму где строки матрицы суть все ненулевые последовательности длины кроме единичных векторов.

а. Число ортогональных проверок

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

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

(II) содержит остальные строк матрицы

Множество соответствует системе проверок, ортогональных относительно так как ни один из информационных шумовых символов, кроме не

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

где означает число элементов множества Из равенства (182) находим

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

(I) Ни одна строка матрицы не может быть использована более одного раза для образования проверок, ортогональных относительно

(II) Множество максимальное множество строк единичного веса матрицы которые могут использоваться в множестве проверок, ортогональных относительно

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

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

же числа проверок, ортогональных относительно

б. Полная ортогонализация

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

Из равенства (184) вытекают следующие две теоремы.

Теорема 18. Двоичный код максимальной длины допускает полную ортогонализацию.

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

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

Доказательство. При правая часть в равенстве (184) всегда положительна, если последний множитель отличен от нуля. Этот множитель равен нулю тогда и только тогда, когда Таким образом, только в этом случае

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

Тот факт, что пороговое декодирование не ограничено исправлением комбинаций ошибок только веса не более имеет особенно большое

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

Положим теперь, что для определения 10 информационных шумовых символов из системы проверок, ортогональных относительно каждого из этих символов, используется мажоритарное декодирование. Общая вероятность ошибки будет приблизительно Причина такого радикального сокращения состоит в следующем. Пусть Тогда будет декодировано неверно только в том случае, когда более 256 из 511 проверок, ортогональных относительно окажутся равными единице. Так как каждая из этих проверок включает два шумовых символа, кроме то вероятность равенства этой проверки единице по лемме 3 будет равна 0,375. Затем можно вычислить вероятность того, что окажутся равными единице более чем 256 из 511 проверок. Она будет равна Подобным же образом получим, что вероятность неверного декодирования символа если он равен единице, будет меньше, чем Средняя вероятность ошибки декодирования символа будет, таким образом, меньше, чем . Разумеется, вероятность ошибки декодирования любого из всех 10 информационных шумовых символов будет меньше, чем увеличенная в 10 раз вероятность неверного декодирования символа или меньше, чем 4,9- 10-7.

Теорема 19 подтверждает замечание, сделанное в § 1.2, в том смысле, что существуют определенные трудности эффективного применения порогового декодирования к недвоичным кодам. Из равенства (183)

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