11.6. Кодовые слова с малым весом в некоторых кодах

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

В случае двоичных циклических кодов и недвоичных негациклических кодов с метрикой Ли многочлен локаторов ошибок полностью определяет вектор ошибок, а в случае недвоичных кодов с метрикой Хэмминга вектор ошибок зависит как от многочлена локаторов ошибок, так и от многочлена значений ошибок Если все ошибки равны 1, то Существенное преимущество представления вектора ошибок через многочлен локаторов ошибок а не в виде многочлена ошибок состоит в том, что многочлен точно отражает вес вектора ошибок: вес

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

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

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

В случае метрики Ли степенные симметрические функции от взаимных корней многочлена локаторов могут быть вычислены с помощью тождеств Ньютона:

Эта формула остается справедливой и в случае метрики Хэмминга, если величины всех ошибок равны 1.

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

11.61. Теорема. Пусть в где Пусть

где константы, зависящие только от коэффициентов многочлена Определим вес числа К, с помощью равенства где — коэффициенты -ичного представления числа Тогда

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

и

Доказательство

Разлагая в ряд по степеням получим, что

Рассмотрим произведение

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

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

где . Следовательно, Это доказывает соотношение (11.612).

Можно также записать

Так как для любого множества чисел справедливо неравенство то

Подстановка дает

или

Это доказывает соотношение (11.611) и теорему,

Теорема 11.61 позволяет выделить слова малого веса во многих циклических кодах с блоковой длиной Например, в циклическом двоичном коде с блоковой длиной 31 координаты могут быть занумерованы как где

Каждый элемент поля может быть записан в виде Восемь элементов, координаты которых удовлетворяют уравнениям образуют трехмерное аффинное подпространство над Это аффинное подпространство элементов являющихся корнями аффинного многочлена Согласно теореме 11.61, для всех К, таких, что симметрические функции степени К от этих восьми элементов равны нулю. В частности, так что многочлен локаторов кодового слова с весом 8 из двоичного БЧХ-кода с блоковой длиной 31, исправляющего три ошибки. Соответствующим кодовым словом является

Так как то это кодовое слово, дополненное нулем, принадлежит расширенному БЧХ-коду с блоковой длиной 32. Этот пример обобщается теоремой 11.62, вытекающей сразу из теоремы 11.61.

11.62. Теорема (Казами, Лин и Питерсон [1966] и Камьон [1966, 1968]). Если а — примитивный элемент поля то

-удлиненный циклический код с блоковой длиной над и порождающим многочленом содержит кодовые слова веса в метрике Хэмминга, так и в метрике Ли), за исключением случая, когда существует такое К, для которого

11.63. С ледствие. Частный -удлиненный ВЧХ-код с конструктивным расстоянием над содержит кодовые слова веса

Доказательство следствия 11.63. Корни порождающего многочлена циклического БЧХ-кода с конструктивным расстоянием совпадают с элементами и сопряженными с ними. Если то Если элемент, сопряженный с то Следовательно, за исключением случая

Теорема 11.62 описывает кодовые слова малого веса, локаторы ненулевых координат которых лежат в аффинном подпространстве пространства над В некоторых кодах все слова малого веса являются словами такого типа. Такие коды описываются теоремой 11.64, являющейся обобщением теоремы Питерсона.

11.64. Теорема. Пусть порождающий многочлен кода с блоковой длиной и пусть сумма цифр -ичного представления числа К. Если

и

то

11.641. Локаторы ненулевых координат произвольного кодового слова веса из -удлиненного кода образуют аффинное подпространство размерности к над

11.642. Ненулевые координаты любого фиксированного слова веса совпадают.

Доказательство утверждения 11.641. Пусть локатор кодового слова с весом Хэмминга и пусть со многочлен величин координат для этого кодового слова. Тогда

или

Согласно уравнению (10.12),

Очевидно, коэффициент при в этом многочлене равен

так как для каждого слова -удлиненного кода. Следовательно,

Если то , так Следовательно, и из уравнений (11.644) и (11.645) вытекает, что

Если то получаем нулевое кодовое слово. Если то положим

Тогда уравнение (11.644) запишется в виде

откуда и

Если то за исключением случая который возможен тогда и только тогда, когда для некоторого В силу (11.646), отсюда следует, что за исключением случая Поэтому для равенство (11.647) можно заменить равенством

Если — наибольшее число, не являющееся степенью для которого о то, согласно (11.648), существуют такие числа что или

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

Доказательство утверждения 11.642. Пусть кодовое слово веса Согласно теореме 11.641, локаторы ненулевых позиций слова лежат в аффинном подпространстве поля По теореме 11.61 в коде содержится другое кодовое слово, ненулевые координаты которого равны единице, причем они соответствуют тем же самым локаторам. Если не является скалярным кратным то разность между и некоторым скалярным кратным дает кодовое слово, вес Хэмминга которого меньше, чем а это противоречит БЧХ-границе для минимального веса кода.

Как покажет теорема 11.65, теорема 11.61 является также полезной для определения кодовых слов малого веса в некоторых негациклических кодах.

11.65. Теорема. Негациклический код с блоковой длиной корни порождающего многочлена которого совпадают с и их сопряженными, содержит кодовые слова веса в метрике Ли.

Доказательство. Если то Следовательно, где элементы поля линейно независимые над Для того чтобы доказать допустимость надо установить, что изменение знака любого взаимного корня не приводит к другому взаимному корню. Если бы это было так, то что противоречит линейной независимости и над

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

Теорема 11.65 ограничивает область применения теоремы 9.34. Негациклический код, корни порождающего многочлена которого содержат может исправлять столько же ошибок в метрике Ли, сколько и код, корнями порождающего многочлена которого являются хотя избыточность последнего кода почти вдвое превышает избыточность первого.

Теоремы 11.62 и 11.65 позволяют выделить кодовые слова малого веса, ненулевым координатам которых соответствуют локаторы, лежащие в аффинном (или линейном) подпространстве поля Можно также найти кодовые слова малого веса в метрике Хэмминга, ненулевым координатам которых соответствуют локаторы, представляющие собой линейные сдвиги точек аффинного подпространства поля В частности, имеет место следующее утверждение:

11.66. Теорема. Если -удлиненный БЧХ-код с конструктивным расстоянием d и блоковой длиной над полем содержит кодовое слово веса d и если локаторы ненулевых координат этого кодового слова лежат в подпространстве размерности к над то -удлиненный БЧХ-код с блоковой длиной и конструктивным расстоянием содержит кодовые слова веса

Доказательство. Пусть локаторы ненулевых координат кодового слова веса и пусть значения соответствующих координат. Тогда для Пусть такой -линеаризированный многочлен степени над все корни которого лежат в причем среди них содержатся Так как размерность линейного пространства, натянутого на не превосходит та — к, то многочлен с такими свойствами существует. Пусть многочлен, дуальный к Согласно теореме 11.35, , где . Мы утверждаем, что расширенный БЧХ-код с конструктивным расстоянием содержит кодовое слово, локаторами всех ненулевых координат которого являются причем ненулевую координату с локатором можно взять равной Для доказательства вычислим величину

Так как 2 — невзвешенная степенная симметрическая функция от то, применяя теорему 11.61, получим, что

Если то Если за исключением случая, когда следовательно, . Поэтому для

Теоремы 11.61 — 11.66 показывают, как линейные и аффинные подпространства конечного поля могут быть использованы для выделения в некоторых кодах слов малого веса. К некоторым другим кодам применима иная, не связанная с аффинными подпространствами техника выделения слов малого веса. Пример такого рода дает теорема 11.67.

11.67. Теорема (Казами, Лин, Питерсон [1966]). Если БЧХ-код с конструктивным кодовым расстоянием d и блоковой длиной над содержит кодовые слова веса d и если делит то БЧХ-код с конструктивным расстоянием d и блоковой длиной над также содержит кодовые слова веса

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

11.68. Следствие. Если то БЧХ-код с конструктивным расстоянием d и блоковой длиной над содержит кодовые слова веса

Доказательство. БЧХ-код с конструктивным расстоянием d и блоковой длиной d всегда содержит кодовое слово веса

К сожалению, теоремы позволяют определять слова малого веса в относительно узком классе кодов. Минимальное расстояние для большинства кодов, даже для большинства БЧХ-кодов, не известно. Из разд. 10.3 и 10.4 мы знаем, что истинное минимальное расстояние не меньше конструктивного расстояния, а во многих случаях больше. В общем случае, согласно следствию 11.63, истинное расстояние каждого примитивного БЧХ-кода с точностью до делителя числа совпадает с конструктивным расстоянием. Практически корректирующие возможности БЧХ-кодов часто определяются конструктивным расстоянием, а не истинным, так как наиболее употребительные алгоритмы декодирования не позволяют исправлять векторы ошибок, вес которых больше половины конструктивного расстояния. В разд. 10.5, 10.6 и 11.1 были описаны улучшенные алгоритмы, позволяющие исправлять ошибки несколько большего веса; но даже эти алгоритмы приводят к отказам, если декодер пытается

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

С точки зрения практических приложений наиболее важными вопросами относительно любого кода являются: (1) Насколько хорош код? (2) Насколько легким является его декодирование? (3) Какова его скорость передачи информации? Вопросы (1) и (2) являются инженерными, поскольку понятия «хороший» и «легкий» могут быть определены только в терминах статистики шума в канале, которая никогда не известна точно, и в терминах стоимости оборудования, которая существенно зависит от нынешнего состояния электронной техники. Если качество кода определяется в терминах конструктивного расстояния, то для частных БЧХ-кодов на вопросы (1) и (2) можно дать следующий приблизительный ответ: (1) существуют коды с произвольным конструктивным расстоянием; (2) как было показано в гл. 2, 7 и 10, декодирование является относительно простым. Оба эти ответа являются обнадеживающими. В противоположность вопросам (1) и (2), вопрос (3) является точным математическим вопросом, ответ на который будет дан в гл. 12. В гл. 13 будет показано, что в определенном смысле этот ответ является неутешительным, поскольку существуют лучшие коды с большой блоковой длиной, имеющие значительно большую скорость передачи, хотя для этих кодов не известны реализуемые алгоритмы декодирования.

Задачи

(см. скан)

(см. скан)