Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 11.6. Кодовые слова с малым весом в некоторых кодахСуществует много способов задания кодовых слов и векторов ошибок. В некоторых случаях наиболее удобно представлять кодовые слова непосредственно в виде последовательности символов, передающихся по каналу,
В случае двоичных циклических кодов и недвоичных негациклических кодов с метрикой Ли многочлен локаторов ошибок полностью определяет вектор ошибок, а в случае недвоичных кодов с метрикой Хэмминга вектор ошибок зависит как от многочлена локаторов ошибок, так и от многочлена значений ошибок Хотя мы до сих пор и не пользовались этим, каждое кодовое слово можно описать с помощью многочлена локаторов кодового слова
Преилп ществом такого описания является малая степень многочленов локаторов кодовых слов малого веса. Для некоторых кодов это позволяет доказать существование кодовых слов малого веса с помощью отыскания для них многочленов локаторов низкой степени. Для доказательства того, что данный многочлен действительно является мпогочленом локаторов кодового слова, необходимо доказать, что все его взаимные корни лежат среди локаторов кода и что соответствующее кодовое слово удовлетворяет всем проверочным уравнениям. Для циклических кодов такими проверочными уравнениями являются взвешенные степенные симметрические функции от взаимных корней многочлена В случае метрики Ли степенные симметрические функции от взаимных корней многочлена локаторов
Эта формула остается справедливой и в случае метрики Хэмминга, если величины всех ошибок равны 1. Покажем теперь, что если некоторые коэффициенты многочлена 11.61. Теорема. Пусть в
где
за исключением случая, когда выполняются оба неравенства
и
Доказательство
Разлагая
Рассмотрим произведение
Запись этого произведения в виде степенного ряда может содержать член с
где
где Можно также записать
Так как для любого множества чисел
Подстановка
или
Это доказывает соотношение (11.611) и теорему, Теорема 11.61 позволяет выделить слова малого веса во многих циклических кодах с блоковой длиной Каждый элемент поля
Так как 11.62. Теорема (Казами, Лин и Питерсон [1966] и Камьон [1966, 1968]). Если а — примитивный элемент поля
11.63. С ледствие. Частный Доказательство следствия 11.63. Корни порождающего многочлена циклического БЧХ-кода с конструктивным расстоянием Теорема 11.62 описывает кодовые слова малого веса, локаторы ненулевых координат которых лежат в аффинном подпространстве пространства 11.64. Теорема. Пусть
и
то 11.641. Локаторы ненулевых координат произвольного кодового слова веса 11.642. Ненулевые координаты любого фиксированного слова веса Доказательство утверждения 11.641. Пусть
или
Согласно уравнению (10.12),
Очевидно, коэффициент при
так как
Если
Если
Тогда уравнение (11.644) запишется в виде
откуда
Если
Если За исключением случаев Доказательство утверждения 11.642. Пусть Как покажет теорема 11.65, теорема 11.61 является также полезной для определения кодовых слов малого веса в некоторых негациклических кодах. 11.65. Теорема. Негациклический код с блоковой длиной Доказательство. Если В качестве иллюстрации к теореме 11.65 рассмотрим пример Теорема 11.65 ограничивает область применения теоремы 9.34. Негациклический код, корни порождающего многочлена которого содержат Теоремы 11.62 и 11.65 позволяют выделить кодовые слова малого веса, ненулевым координатам которых соответствуют локаторы, лежащие в аффинном (или линейном) подпространстве поля 11.66. Теорема. Если Доказательство. Пусть
Так как 2 — невзвешенная степенная симметрическая функция от
Если Теоремы 11.61 — 11.66 показывают, как линейные и аффинные подпространства конечного поля могут быть использованы для выделения в некоторых кодах слов малого веса. К некоторым другим кодам применима иная, не связанная с аффинными подпространствами техника выделения слов малого веса. Пример такого рода дает теорема 11.67. 11.67. Теорема (Казами, Лин, Питерсон [1966]). Если БЧХ-код с конструктивным кодовым расстоянием d и блоковой длиной Доказательство. Локаторы первого кода являются корнями 11.68. Следствие. Если Доказательство. БЧХ-код с конструктивным расстоянием d и блоковой длиной d всегда содержит кодовое слово веса К сожалению, теоремы исправить две дополнительные ошибки по сравнению с тем, что гарантирует конструктивное расстояние. С точки зрения практических приложений наиболее важными вопросами относительно любого кода являются: (1) Насколько хорош код? (2) Насколько легким является его декодирование? (3) Какова его скорость передачи информации? Вопросы (1) и (2) являются инженерными, поскольку понятия «хороший» и «легкий» могут быть определены только в терминах статистики шума в канале, которая никогда не известна точно, и в терминах стоимости оборудования, которая существенно зависит от нынешнего состояния электронной техники. Если качество кода определяется в терминах конструктивного расстояния, то для частных БЧХ-кодов на вопросы (1) и (2) можно дать следующий приблизительный ответ: (1) существуют коды с произвольным конструктивным расстоянием; (2) как было показано в гл. 2, 7 и 10, декодирование является относительно простым. Оба эти ответа являются обнадеживающими. В противоположность вопросам (1) и (2), вопрос (3) является точным математическим вопросом, ответ на который будет дан в гл. 12. В гл. 13 будет показано, что в определенном смысле этот ответ является неутешительным, поскольку существуют лучшие коды с большой блоковой длиной, имеющие значительно большую скорость передачи, хотя для этих кодов не известны реализуемые алгоритмы декодирования. Задачи(см. скан) (см. скан)
|
1 |
Оглавление
|