Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Следующая теорема содержит доказательство этого факта и других основных свойств циклических кодов.
Теорема 1. Пусть
ненулевой идеал кольца
т. е. циклический код длины
В
имеется единственный нормированный многочлен
наименьшей степени.
(b).
, т. е.
порождающий многочлен идеала
делит
Любой многочлен
в кольце
однозначно записывается в виде
где степень
меньше чем
Размерность
равна
Таким образом, сообщение
кодируется словом
Если
то
порождается (как подпространство в
строками порождающей матрицы
(Здесь использованы очевидные обозначения.)
Доказательство (а). Предположим, что оба многочлена
нормированы и имеют минимальную степень
Тогда многочлен
имеет более низкую степень, что приводит к противоречию, за исключением случая
.
(b). Пусть
Воспользуемся в
равенством
где
. В силу линейности кода
так что
Следовательно,
.
(c). Воспользуемся в
равенством
где
это означает, что
что приводит к противоречию, за исключением случая
(d), (е). Согласно
любой многочлен
равен многочлену
Следовательно, в кольце
где
Таким образом, в кольце
(но не в
код
состоит из произведений
на многочлены степени не больше
Всего имеется
линейно независимых произведений такого вида, а именно
Соответствующие векторы и являются строками матрицы
Это означает также, что размерность кода равна
Теперь дадим несколько примеров циклических кодов.
Например, для
Упражнение (6). Проверить, что строки матрицы (7.4) ортогональны строкам матрицы (7.6).
Коды БЧХ, исправляющие две ошибки. Код исправляющий две ошибки, длины
был определен соотношением (3.11) как код с проверочной матрицей
каждый элемент которой опять должен быть заменен соответствующим двоичным
-вектором. Теперь
по свойству
где
минимальный многочлен элемента
тогда и только тогда, когда
Но
согласно свойству
неприводимы и согласно упражнению (15) гл. 4. различны. Поэтому окончательно имеем:
тогда и только тогда, когда
Таким образом, может быть сформулирована следующая теорема.
Теорема 3. Код БЧХ, исправляющий две ошибки, имеет параметры
и является циклическим кодом с порождающим многочленом
Доказательство. Равенство
следует из упражнения (15) гл. 4. Минимальное расстояние было найдено в гл. 3. (Другое доказательство приведено ниже в теореме 8.)
Упражнение. (7). Показать, что порождающий многочлен кода БЧХ длины 15 с исправлением двух ошибок, определенного в § 3 гл. 3, равен
(использовать § 4.4). Выписать порождающую матрицу кода.
Замечание. До сих пор ничего не было сказано о минимальном расстоянии
циклического кода. Это объясняется тем, что определить
в общем случае очень трудно. Граница БЧХ (доказываемая ниже теорема 8) дает нижнюю границу для случая, когда известны корни многочлена
. В гл. 8 мы увидим,
что в некоторых случаях минимальное расстояние может быть найдено с помощью многочлена Мэттсона — Соломона.
- Упражнения. (8). (Недвоичные коды Хэмминга.) (а). Код - Хэмминга
над полем GF(q) задается проверочной матрицей размерности
столбцами котррой являются все ненулевые
-векторы над
первая ненулевая координата которых равна 1. Код 6 из гл. 1 является кодом
Доказать, что код
является совершенным с параметрами
Доказать, что если
взаимно просты, то
эквивалентен циклическому коду с нулями
где
примитивный корень
степени из единицы.
(9). Укороченные циклические коды. Иногда, практические ограничения, накладываемые на кодовые длины, таковы, что для требуемых кодовых длин не существует хороших циклических кодов. В этом случае можно использовать укороченный циклический код
который получается из циклического кода
путем выбора всех кодовых слов, начинающихся
последовательными нулями и отбрасыванием этих нулей. Результирующий код уже, конечно, не будет циклическим. Докажите, однако, что найдется такой многочлен
что является идеалом кольца многочленов по модулю многочлена
и наоборот, что каждый идеал такого кольца является укороченным циклическим кодом.