Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
r, m) ⊥ . Но dimRM(m − r − 1, m) + dimRM(r, m) = 2 m , откуда следует, что RM(m − r − 1, m) = RM(r, m) ⊥ , что доказывает теорему. N 9.2.1. Коды с параметрами кодов Рида-Маллера Выколотый код Рида-Маллера RM ∗ (r, m) получается удалением какой-либо ко- ординаты и имеет параметры (n = 2 m − 1, M = 2 k , d = 2 m−r − 1), где k = 1 + µ m 1 ¶ + · · · + µ m r ¶ . Покажем, как, используя свитчинговые и каскадные конструкции, можно строить мощные классы кодов с параметрами кодов Рида-Маллера и выколотых кодов Рида- Маллера. Двоичные коды (не обязательно линейные) с параметрами выколотого кода Рида-Маллера порядка r будем обозначать LRM ∗ (r, m) и называть выколотыми кодами Рида-Маллера. Линейный код RM ∗ (r, m) является частным случаем кодов LRM ∗ (r, m). Сначала рассмотрим применение конструкции Васильева из теоремы 13. Посред- ством этого метода построения кодов можно получить много нелинейных выколотых кодов Рида-Маллера LRM ∗ (r, m)) порядка r. Пусть LRM ∗ (r, m − 1) и LRM ∗ (r − 1, m − 1) — произвольные выколотые коды Рида-Маллера порядков r и r − 1 соответственно длины n = 2 m−1 − 1. Справедливо следующее утверждение: 9.2. Коды Рида-Маллера 107 Теорема 62 (Пулатов А. К., 1962). Множество векторов { (x, |x| + λ(y), x + y) | x ∈ LRM ∗ (r, m − 1), y ∈ LRM ∗ (r − 1, m − 1) }, где λ — произвольная функция из кода LRM ∗ (r − 1, m − 1) в множество {0, 1}, является кодом с параметрами выколотого кода Рида-Маллера порядка r длины n = 2 m − 1, т. е. LRM ∗ (r, m)-кодом. Доказательство теоремы аналогично доказательству теоремы 13. Замечание. Этот класс кодов оказался хорошим представителем для реализаций π-схемами. А. К. Пулатовым была получена квадратичная нижняя оценка сложности π-схем, реализующих коды с параметрами выколотых кодов Рида-Маллера. Используя теорему 62, можно показать, что существуют нетривиальные разбие- ния выколотых кодов Рида-Маллера LRM ∗ (r, m − 1) порядка r длины n = 2 m−1 − 1 на выколотые коды Рида-Маллера порядка r − 1 длины n = 2 m−1 − 1: LRM ∗ (r, m − 1) = t [ i=1 LRM ∗ i (r − 1, m − 1), где t = 2 0 @ m r 1 A (доказательство этого факта аналогично доказательству теоремы 21). Теорема 63 (Соловьева Ф. И., 1981). Пусть даны произвольные разбиения выколотых кодов Рида-Маллера порядка r: LRM ∗ 1 (r, m − 1) = t [ i=1 LRM ∗ 1,i (r − 1, m − 1), LRM ∗ 2 (r, m − 1) = t [ i=1 LRM ∗ 2,i (r − 1, m − 1), где t = 2 0 @ m r 1 A . Пусть π — произвольная подстановка на t элементах. Тогда мно- жество {(x, y, |y|) : x ∈ LRM ∗ 1,i (r − 1, m − 1), y ∈ LRM ∗ 2,π(i) (r − 1, m − 1), i = 1, . . . , t} является LRM ∗ (r, m)-кодом. Доказательство теоремы аналогично доказательству теоремы 22. Замечание. Легко видеть, что применение проверки на четность к LRM ∗ (r, m)-кодам позволяет получить широкие классы неэквивалентных нелиней- ных кодов с параметрами кодов Рида-Маллера порядка r длины n ≥ 16. Среди этих кодов могут оказаться коды с полезными свойствами, например с транзитивной груп- пой автоморфизмов (код называется транзитивным, если его группа автоморфиз- мов действует транзитивно на всех его кодовых словах), а также коды, являющиеся Z 4 -линейными (линейными над кольцом Z 4 ). Последние могут найти применение в криптографии, например, в криптосистемах МакЭлиса с открытыми ключами. 108 Глава 9. Другие коды 9.3. Коды Препараты Определение. Максимальный двоичный код длины n = 4 m , где m ≥ 2 с кодовым расстоянием d = 6 называется кодом Препараты. Его мощность равна 2 n /n 2 Первый такой код (для каждой допустимой длины) построил Франко Препарата в 1968 г. В 1971–1973 гг. Н. В. Семаков, В. А. Зиновьев и Г. В. Зайцев исследовали свой- ства кодов с параметрами кодов Препараты и связь их с двоичными совершенными кодами, исправляющими одну ошибку. Ими было показано, что коды Препараты, по- мимо максимальности, обладают некоторыми весьма нетривиальными свойствами, а именно эти коды равномерно упакованы и дистанционно инвариантны. Кроме того, было показано, что любой код Препараты является подкодом некоторого расширен- ного совершенного кода той же длины с расстоянием 4 (причем единственного) и в некотором смысле плотно упакован в нем. В 1972 г. Я. М. Геталс и С. Л. Сновер показали, что линейных кодов Препара- ты не существует. В 1976 г. И. Думер и позднее, в 1983 г. Р. Д. Бакер, Я. Х. Ван Линт и Р. М. Вилсон построили семейство кодов Препараты, содержащее ориги- нальный код Препараты. В 1994 г. А. Р. Хэммонс, П. В. Кумар, А. Р. Кальдербанк, Н. Дж. А. Слоэн и П. Соле предложили конструкцию первого кода Препараты с групповой структурой — Z 4 -линейного кода Препараты. Конструкция Думера-Бакера Соответствие между множествами и векторами Пусть m — нечетное целое число, m ≥ 3 и n = 2 m − 1. Пусть α — примитивный элемент поля GF (2 m ). Имеем GF (2 m ) = {0, 1, α, α 2 , . . . , α n−1 }. Рассмотрим множество I = {−∞, 0, 1, 2, . . . , n − 1}, состоящее из логарифмов элементов поля по основанию α (полагаем, как и раньше в гл. 6, что α −∞ = 0). Произвольному подмножеству X множества элементов поля GF (2 m ) взаимно однозначно сопоставим двоичный вектор c длины n+1, координаты которого занумерованы с помощью множества I: X ←→ c = (c −∞ , c 0 , c 1 , c 2 , . . . , c n−1 ) (9.1) по правилу α i ∈ X ⇐⇒ c i = 1. Другими словами, вектор c является характеристическим вектором множества X: его ненулевые позиции указывают элементы поля, включаемые в множество X. На- пример, пустому множеству ∅ отвечает нулевой вектор. Введем некоторые обозначе- ния для множеств X, Y ∈ GF (2 m ): — как обычно через |X| обозначается мощность множества X; 9.3. Коды Препараты 109 — X4Y — симметрическая разность множеств X и Y . Заметим, что эта операция на множествах отвечает двоичному сложению соответствующих характеристических векторов; — X + a — сдвиг множества X на элемент поля a, т. е. X + a = {x + a | x ∈ X}; — aX — умножение X на ненулевой элемент поля a, т. е. aX = {ax | x ∈ X}. Используя соответствие (9.1), произвольный двоичный вектор длины 2(n + 1) = 2 m+1 можно описать парой (X, Y ), где X, Y — подмножества множества элементов поля GF (2 m ). Далее мы не будем делать различия между парами мно- жеств (X, Y ) и двоичными векторами длины 2 m+1 . Из контекста далее будет ясно, речь идет о множествах или о векторах. Построение кодов Препараты Группа автоморфизмов поля GF (2 m ) состоит из всех отображений вида x → x σ , где σ = 2 k , k = 0, 1, . . . , m − 1. Рассмотрим из них такие, что отображения x → x σ−1 , x → x σ+1 взаимно однозначны. Другими словами, для этого выберем такие σ, что выполняются условия (σ − 1, 2 m − 1) = 1, (σ + 1, 2 m − 1) = 1. (9.2) Считаем далее, что σ = 2 k удовлетворяет условиям (9.2). Теорема 64. Код P (σ) длины 2 m+1 , состоящий из всех двоичных векторов, опи- сываемых парами (X, Y ), удовлетворяющими условиям: 1) |X| — четно, |Y | — четно; 2) X x∈X x = X y∈Y y; 3) X x∈X x σ+1 + Ã X x∈X x ! σ+1 = X y∈Y y σ+1 , (9.3) является кодом Препараты. Для доказательства этой теоремы потребуется ввести некоторые дополнительные определения и изучить свойства кодов P (σ). Сначала приведем следующие простые свойства поля GF (2 m ). 110 Глава 9. Другие коды Лемма 10. Для любых элементов a, b поля GF (2 m ) и любого σ = 2 k имеет место тождество (a + b) σ+1 = a σ+1 + a σ b + ab σ + b σ+1 . Доказательство. Согласно теореме 35 (см. разд. 6.2.), имеем (a + b) σ = a σ + b σ . Тогда, преобразовав (a + b) σ+1 к виду (a + b) σ (a + b), получим искомое тождество. N Несложно доказывается Лемма 11. Для любого множества X из носителя поля GF (2 m ) и любого σ = 2 k выполняется Ã X x∈X x ! σ = X x∈X x σ . Напомним, что двоичный код называется дистанционно-инвариантным, если число кодовых слов, находящихся на некотором расстоянии l от фиксированной ко- довой вершины, не зависит от выбора этой вершины, а зависит только от l. Утверждение 16. Код P (σ) дистанционно-инвариантен. Доказательство. По построению код P (σ) содержит вектор (∅, ∅). Пусть (X 0 , Y 0 ) — произвольный вектор из P (σ). Для доказательства утверждения доста- точно построить взаимно однозначное соответствие между множествами кодовых векторов, находящихся на расстоянии l от вершин (∅, ∅) и (X 0 , Y 0 ) соответственно, где l — некоторое фиксированное расстояние. Зададим следующее взаимно однозначное отображение: f : (X, Y ) → (U, V ), по правилу U = X4X 0 + a, где a = X x∈X 0 x; V = Y 4Y 0 . Заметим, что расстояние от (X, Y ) до (X 0 , Y 0 ) равно весу вектора (X4X 0 , Y 4Y 0 ) и равно расстоянию от (U, V ) до (∅, ∅). Покажем, что если (X, Y ) принадлежит коду, то и вектор (U, V ) ему принадлежит. В силу взаимной однозначности отображения f , этого будет достаточно для доказательства дистанционной инвариантности P (σ). Пусть (X, Y ) — кодовый вектор. Проверим, что вектор (U, V ) также кодовый, т. е. для него выполняются условия (9.3): 1) |X|, |X 0 |, |Y |, |Y 0 | — четны, следовательно, |X4X 0 + a| и |Y 4Y 0 | четны. 2) Докажем равенство X x∈U x = X y∈V y. 9.3. Коды Препараты 111 Действительно, имеем X x∈U x = X x∈X4X 0 (x + a) = Ã X x∈X4X 0 x ! + a|X4X 0 | = = X x∈X4X 0 x = X x∈X x + X x∈X 0 x = X y∈Y y + X y∈Y 0 y = X y∈V y. 3) Проверим выполнение равенства X x∈U x σ+1 + Ã X x∈U x ! σ+1 = X y∈V y σ+1 . Преобразуя первое слагаемое, с учетом леммы 10, имеем X x∈U x σ+1 = X x∈X4X 0 (x + a) σ+1 = = X x∈X4X 0 (x σ+1 + x σ a + xa σ + a σ+1 ) = X x∈X4X 0 x σ+1 + Ã X x∈X4X 0 x σ ! a + Ã X x∈X4X 0 x ! a σ = = X x∈X x σ+1 + X x∈X 0 x σ+1 + Ã X x∈X x σ ! a + a σ+1 + Ã X x∈X x ! a σ + a σ+1 . Используя лемму 11, получаем X x∈U x σ+1 = X x∈X x σ+1 + X x∈X 0 x σ+1 + Ã X x∈X x ! σ a + Ã X x∈X x ! a σ . Для второго слагаемого, используя лемму 10, имеем Ã X x∈U x ! σ+1 = Ã X x∈X4X 0 (x + a) ! σ+1 = Ã X x∈X4X 0 x ! σ+1 = Ã X x∈X x + a ! σ+1 = = Ã X x∈X x ! σ+1 + Ã X x∈X x ! σ a + Ã X x∈X x ! a σ + a σ+1 . Тогда X x∈U x σ+1 + Ã X x∈U x ! σ+1 = X x∈X x σ+1 + Ã X x∈X x ! σ+1 + X x∈X 0 x σ+1 + Ã X x∈X 0 x ! σ+1 = = X y∈Y y σ+1 + X y∈Y 0 y σ+1 = X y∈V y σ+1 . Таким образом, дистанционная инвариантность кода P (σ) доказана. N 112 Глава 9. Другие коды Утверждение 17. Группа автоморфизмов кода P (σ) содержит отображения: 1. (X, Y ) → (X + a, Y + a) для любого a ∈ GF (2 m ); 2. (X, Y ) → (Y, X); 3. (X, Y ) → (aX, aY ) для любого ненулевого a ∈ GF (2 m ); 4. (X, Y ) → (ϕ(X), ϕ(Y )) для любого ϕ ∈ Aut GF (2 m ). (9.4) Доказательство получается непосредственной проверкой выполнения условий (9.3) для образов кодового вектора (X, Y ) под действием отображений 1–4. N Утверждение 18. Код P (σ) имеет кодовое расстояние 6. Доказательство. Поскольку код P (σ) содержит нулевую вершину и в силу утверждения 16 дистанционно инвариантен, достаточно показать, что минимальный ненулевой вес его кодовых слов равен 6. Заметим, что все кодовые векторы (X, Y ), в силу п. 1 условия (9.3), имеют четный вес. Из пунктов 1 и 2 условия (9.3) следует, что в коде нет слов веса 2. Покажем, что в коде P (σ) нет слов и веса 4. Предположим обратное. Возможны два случая: Случай 1. Вектор ({a, b}, {c, d}) — кодовый, где a 6= b и c 6= d. Из утверждения 17 следует, что без ограничения общности в качестве a можно взять 0. Действительно, рассмотрим кодовое слово веса 4, полученное из выбранного действием автоморфизма (X, Y ) → (X − a, Y − a). По п. 3 условия (9.3) имеем (0 σ+1 + b σ+1 ) + (0 + b) σ+1 = 0 = c σ+1 + d σ+1 . Тогда c σ+1 = d σ+1 . Поскольку σ удовлетворяет условиям (9.2), отображение x → x σ+1 взаимно однозначно, и, следовательно, c = d, что противоречит выбору c и d. Случай 2. Вектор ({a, b, c, d}, ∅) — кодовый, где все элементы a, b, c, d различны. В силу утверждения 17, считаем a = 0. Из пп. 2 и 3 условия (9.3) имеем |