Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
15.6. КОД ПРЕПАРАТЫТеперь мы опишем другой нелинейный код, код Препараты который обладает тем свойством, что его спектр весов (или расстояний) равен преобразованию Мак-Вильямс от спектра весов кода Кердока и задается равенством (15.36). Код Препараты, конечно, не является дуальным к коду Кердока в обычном смысле, так как оба эти кода нелинейны. Аналогично кодам Кердока код Препараты строится как объединение некоторого линейного кода в смежных классов кода по Напомним, что код является расширенным кодом Хэмминга и дуален коду Согласно теореме 2 гл. 13 код состоит из слов
т. е. из кодовых слов вида где произвольны. Определение. Код Препараты определяется для четного как код, состоящий из линейного подкода кола смежных классов кода то подкоду Подкод состоит из слов где произвольны, а смежные классы задаются представителями
Таким образом, размерность кода равна Код Я является -кодом, если -кодом, если Словами кода являются следующие векторов, где
где равно 0 или 1 (см. рис. 15.12). Первый из кодов Препараты совпадает с первым кодом Кердока (и, следовательно, эквивалентен коду Нордстрома-Робинсона . Лемма т. е. код Кердока и код Препараты длины 16 представляют собой один и тот же код. Доказательство. Примитивные идемпотенты длины 7 равны и , причем Таким образом, состоит из кодовых слов
Следовательно, Согласно уравнениям (15.33) и (15.48) представители смежных классов для кодов соответственно равны:
Их сумма равна
и представляет собой слово из кода Следовательно, являются представителями одного и того же смежного класса по коду Таким образом, Упражнение. (14). Доказать, что линейный код, порождаемый кодом равен -подкоду кода состоящему из слов вида Лемма 23. Слова кода равны
где равны 0 или Доказательство. Код можно записать в виде где состоят соответственно из векторов вида
Тогда состоят соответственно из векторов
Следовательно, (см. упражнение (33) гл. 1), в коде должны содержаться векторы и т. д. Из этих уравнений следует, что код состоит из векторов, перечисленных в формулировке леммы.
Рис. 15.11. Взаимное расположение пространств Отметим, что (см. рис. 15.11). Теперь мы перейдем к основной теореме данного раздела. Теорема 24. Спектр весов (или расстояний) кодч равен преобразованию Мак-Вильямс от спектра весов кода и его производящая функция равна:
Иначе говоря, определяется равенством (15.36). Доказательство Спектр расстояний кода равен согласно упражнению (11) спектру весов элемента групповой алгебры вида
где
Преобразование Мак-Вильямс этого спектра весов задается набором чисел
где суммирование ведется по всем векторам и длины и веса I (по теореме 5 гл. 5) Мы покажем, что за исключением случаев, когда I равно одному из чисел или за исключением I, равных одному из возможных значений веса в коде точнее, мы покажем, что множество чисел равно спектру весов кода Рассмотрим отдельно вклад, вносимый в элементами и Случай (I) Лемма 25 Если то Доказательство. Так как то для всех Следствие 26. Вклад слов кода равен 1 для числа для числа для числа Случай (II). Лемма 27. Если и то Доказательство. Так как то
Случай (III), Этот случай сложнее. Нам надо вычислить величину
Предположим, что скалярное произведение четно для а значений индекса и нечетно для его значений. Тогда, очевидно,
Кроме того, произведение четно для и нечетно для пар. Таким образом,
Найдем теперь возможные значения для числа Лемма 28. Пусть смежный класс кода по коду Для любого вектора и из этого смежного класса выполняется равенство Доказательство. для некоторого Размерность кода равна а размерность кода равна так что число рассматриваемых смежных классов равно Выберем в качестве представителей смежных классов векторы
где Рассмотрим скалярное произведение векторов Произведение всегда четно, так как код дуальный к коду, порожденному идемпотентом порождается идемпотентом следовательно, содержит подкод с порождающим идемпотентом Скалярное произведение будет равно единице, если в многочлене при стоит ненулевой коэффициент, и равно нулю в остальных случаях, так что Вес таких векторов, как показано на рис. 15.3, может быть равен или Если то и из (15.51) следует, что Если , то Если вес многочлена равен то вес представителя смежного класса равен так как вес многочлена равен Таким образом, смежный класс по коду является смежным классом максимального ранга кода по и содержит векторов веса векторов веса Вклад этого смежного класса в числа равен для всех Далее заметим, что согласно рис. 15.3 общее число представителей веса равно Это завершает рассмотрение случая (III). Вклады всех трех рассмотренных случаев в числа описываются следующим образом:
Складывая эти числа, получаем спектр весов кода Кердока, приведенный на рис. 15.7. Это доказывает, что спектр расстояний кода задается преобразованием спектра весов кода Остается доказать, что спектры весов и спектр расстояний кода совпадают. Используя (15.50), легко проверить, что минимальное расстояние кода равно 6. Так как для кода имеем то согласно теореме 3 гл. 6 код инвариантен относительно расстояния. Следствие 29. Минимальное расстояние кода равно 6. Замечание. Минимальное расстояние и длина кода равны минимальному расстоянию и длине расширенного -кода БЧХ, однако число слов вдвое больше. Мы увидим в гл. 17, что код содержит максимально возможное число слов при такой длине и таком минимальном расстоянии. На рис. 15.12 дается краткое резюме свойств кода
Рис. 15.12. Свойства кода Препараты Укороченный код Препараты Пусть получаемый из кода путем вычеркивания одной координаты (безразлично какой). В этом разделе мы покажем: (1). Спектр весов и спектр расстояний кода не зависит от того, какую из координат мы выбрасываем (теорема 32). (2). Слова каждого фиксированного веса в коде образуют -схему (теорема 33). (3). Полное пространство равно объединению непересекающихся сдвигов кода задаваемых векторами 1, 2 и 3; иными словами, квазисовершенный код (теорема 34). Пусть произвольный код четной блоковой длины, содержащий нулевой вектор, такой, что все его слова имеют четный вес Пусть — код, получаемый из 43 путем вычеркивания произвольной координаты, для определенности — последней. Пусть соответственно спектры весов кодов Как обычно, штрих обозначает преобразованный спектр весов Теорема 30.
Доказательство. Пусть Согласно теореме 5 гл. 5 преобразования спектров весов кодов и соответственно равны:
где использованы обозначения при
(что возможно, так как все веса кода четны). Следовательно,
Но последний член равен Следствие в частности -Замечание. Для линейных кодов утверждения теоремы 30 и следствия 31 тривиальны, так как являются соответственно спектрами весов кодов Упражнение (15) Доказать, что в случае линейных кодов код получается из кода путем вычеркивания фиксированной координаты и последующего удаления всех векторов, вес которых оказался нечетным Применим теперь теорему 30 к коду а именно
Таким образом преобразование спектра расстояний кода помимо содержит ненулевых члена Так как минимальное расстояние кода равно по меньшей мере 5, то по теореме 2 гл 6 можно найти числа Так как то по теореме 6 гл 6 эти числа совпадают также с преобразованием спектра весов Этот результат мы сформулируем в виде следующей теоремы Теорема 32 Пусть выколотый код Препараты длины где и 4 — четно (1) Преобразование спектра весов (и расстояний) кода равно
(2) Производящая функция для спектра весов (и расстояний) задается формулой
где (3) Спектр весов (и расстояний) кода не зависит от того, какая именно из координат вычеркнута (4) Минимальное расстояние кода равно 5 Теорема 33 Слова любого фиксированного веса в коде образуют -схему В частности,
слов веса 5 в коде образуют схему
Кодовые слона любого фиксированного веса в образуют -схему. В частности,
кодовых слов веса 6 в коде образуют схему.
Доказательство. Так как для кода то первое утверждение вытекает непосредственно из теоремы 24 гл. 6. Аналогичная ситуация имеет место и для третьего утверждения. Для нахождения параметра X в (15.53) заметим, что аннулирующий многочлен для кода равен.
где Из теоремы 23 гл. 6
Коэффициент равен числу блоков в этой схеме и согласно формуле (2.21) задается равенством (15.52). Формула для вытекает теперь из теоремы 14 гл. 8. Упражнение. (16). Доказать, что в коде имеется слов веса 6. Последние две теоремы этого раздела показывают, что как все пространство, так и код Хэмминга являются объединением непересекающихся сдвигов кода Теорема 34. Все пространство представляет собой объединение непересекающихся сдвигов кода задаваемых всеми векторами веса 0, 1 и 2 и 1 векторами веса 3. Доказательство. Пусть спектр весов сдвига Воспользуемся уравнением (6.19), где (согласно Тогда из равенства следует, что Из равенства следует также, что Очевидно, что сдвигов кода задаваемых векторами веса 0, 1 и 2, не пересекаются. В пространстве остается еще векторов. Все они должны принадлежать сдвигам, для которых Пусть множество всех векторов веса 3 в Представим в виде где
Мы покажем, что остальные сдвиги кода равны для тех которые имеют 1 в некоторой фиксированной координате. Упражнения (17). Доказать, что если то сдвиг не пересекается ни с каким сдвигом вида где вес вектора равен 0, 1 или 2. (18). Доказать, что сдвиги не пересекаются, если пересечение не пусто. Согласно теореме 33 всего в коде имеется кодовых слов веса 5, которые содержат 1 в двух различных любых фиксированных координатах. Для каждого из этих кодовых слов в множестве имеется 3 вектора, у которых символ 1 стоит в этих же двух фиксированных координатах. Всего в пространстве содержится векторов веса 3, у которых в двух рассматриваемых координатах стоят 1. Следовательно, в множество из них попадает вектор. Таким образом, векторы множества образуют -схему, а следовательно, также -схему при (по теореме 9 гл. 2). Следовательно, в содержится векторов, у которых в некоторой фиксированной координате стоит 1. Все сдвиги кода задаваемые этими векторами, не пересекаются и в точности покрывают оставшиеся векторы из Следствие. является квазисовершенным кодом. Теорема 36. Объединение кода и его сдвигов образует линейный -код Хэмминга. Доказательство. (I). Прежде всего покажем, что векторы
и
для всех принадлежат одному и тому же смежному классу. Действительно, их сумма равна очевидно, лежит в достаточно в уравнении (15.49) положить и . (II). Теперь покажем, что минимальный вес смежного класса по коду представителем которого является вектор (15.58), равен 3; таким образом, векторы (15.57) на самом деле совпадают с векторами из теоремы 34. Рассмотрим типичный вектор из такого смежного класса
Если то правая половина вектора принадлежит коду Хэмминга, и поэтому либо ее вес не меньше чем 3, либо эта половина равна нулю. Если она равна нулю, то и вес левой части равен Если же то и левая, и правая половины вектора отличны от нуля. Учитывая проверку в середине вектора, получаем, что его вес не меньше чем 3. (III). Таким образом, сдвиг кода задаваемый вектором (15.57) (или (15.58)), образует код с минимальным расстоянием 3, содержащий векторов. Остается показать линейность этого кода; тогда согласно упражнению (28) гл. 1 он будет эквивалентен коду Хэмминга. Нам надо показать, что сумма двух векторов вида (15.59), т. е. вектор
опять является вектором вида (15.59). Некоторые трудности вызывает только случай, когда Так как слова веса 3 в коде Хэмминга образуют -схему (теорема 15 гл. 2), то найдутся такие, что
или, умножая на получаем, что
Заметим, что являются представителями смежных классов кода Хэмминга (длины по коду БЧХ, исправляющему две ошибки. Следовательно, при подходящем выборе можно записать:
Кроме того, воспользуемся равенством
Из равенств (15.63) и (15.64) видно, что вектор (15.60) имеет вид (15.59) при (это возможно потому, что идемпотент симплексного кода) и . Упражнения. (19). Препарата определил код как множество всех векторов вида
где слово кода Хэмминга с порождающим многочленом слово кода БЧХ с минимальным расстоянием 6 и порождающим многочленом равно 0 или 1. Показать, что это определение совпадает с определением кода, даваемым уравнениями (15.47) и (15.48). (20). (а). Доказать, что первые символов кода могут быть выбраны в качестве информационных, следовательно, является систематическим. (Ь). Доказать, что остальные символы кода задаются квадратичными функциями от информационных символов. (21). Показать, что код Нордстрома-Робинсона состоит из -кода Рида-Маллера и семи смежных классов, которые в обозначениях упражнения (16) гл. 14 соответствуют максимально нелинейным функциям, задаваемым графами
(22). Доказать, что нелинейный код, приведенный на рис. 5.1, состоит из векторов координаты которых удовлетворяют пяти квадратным уравнениям.
|
1 |
Оглавление
|