4.6.2. Коды Юстесена

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

где соответственно длина, скорость и минимальное расстояние кода некоторые числа. Из границы Варшамова — Гилберта следует существование асимптотически хорошей последовательности систематических кодов, параметры которой в двоичном случае удовлетворяют условию Однако здесь утверждается только существование асимптотически хорошей последовательности кодов и ничего не говорится о том, как конкретно строить коды Если попытаться строить коды следуя выводу границы Варшамова — Гилберта, то нужно последовательно выбирать каждый столбец матрицы Юстесен предложил метод построения асимптотически хорошей последовательности кодов, который является столь же конструктивным, как и методы построения БЧХ-кодов или ОРМ-кодов [50]. Для простоты будем рассматривать двоичные коды. Код Юстесена является каскадным кодом, в качестве внешнего кода которого используется -код Рида—Соломона над Положим Пусть а — примитивный элемент представление элемента в виде вектора над относительно некоторого фиксированного определенного базиса и — вектор длины являющийся

последовательностью векторов Множество двоичных векторов называется кодом Юстесена. Очевидно, что код Юстесена является линейным -кодом. Как и раньше, кодовые векторы будем представлять в виде матриц размера строкой которых является Строка матрицы является нулевой только при Любые две ненулевые строки обладают тем свойством, что если то

так как (здесь ). Минимальный вес кода , согласно примеру 4.4, равен Следовательно, если только кодовый вектор является ненулевым, то по меньшей мере по его строк также являются ненулевыми, а значит, и различными. Поэтому минимальный вес кода Юстесена не меньше суммы весов ненулевых двоичных векторов длины минимально возможного веса, а именно

где

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

Тогда

где Заметим, что параметр является скоростью рассматриваемого кода. Из формул (4.41) и (4.42) следует, что

Поскольку длина кода равна стремится к нулю с ростом при фиксированной скорости то

где при и фиксированном Это означает, что бесконечная последовательность кодов Юстесена (при является асимптотически хорошей. Однако правая часть формулы (4.43) значительно Меньше границы Варшамова-Гилберта .

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

где

Методы декодирования кодов Юстесена описаны в работе [50]. Как указывалось в разд. 3.3, рассматривавшиеся выше асимптотические свойства кодов представляют главным образом теоретический интерес. Одной из нерешенных проблем является построение последовательности кодов, которые можно было бы задать столь же конструктивно, как и коды Юстесена, но которые лежали бы на границе Варшамова — Гилберта. Кроме того, открытым остается вопрос о существовании асимптотически хороших последовательностей циклических кодов.