Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
Упражнение 27. Как построить код Хэмминга, используя конструкцию теоре- мы 22? 5.3. Коды Романова Рассмотрим применение каскадной конструкции для кодов, не являющихся со- вершенными, на примере кода длины 16, который имеет максимальную мощность среди всех кодов такой длины, исправляющих одну ошибку. Хорошо известно, что существует разбиение множества D 9 3 всех двоичных слов длины 9 веса 3 на семь систем троек Штейнера порядка 9. Обозначим эти системы троек Штейнера через S i , i = 1, . . . , 7. Таким образом, имеем D 9 3 = 7 [ i=1 S i . Рассмотрим также разбиение куба E 7 на классы смежности по коду Хэмминга H 7 : E 7 = 7 [ i=0 (H 7 + e i ). 52 Глава 5. Каскадные методы Пусть S 0 i — множество всех антиподальных слов к словам множества S i , т. е. S 0 i = {z + 1 9 |z ∈ S i }. Теорема 23 (Романов А. М., 1983). Множество C 16 , определенное как C 16 = {(x, y) : x ∈ S i ∪ S 0 i , y ∈ H 7 + e i , i = 1, . . . , 7} ∪ {(x, y) : x ∈ {0 7 , 1 7 }, y ∈ H 7 } является кодом, исправляющим одну ошибку длины 16 мощности 2720. Доказательство опустим, поскольку оно аналогично доказательству теоремы 22. Применение конструкции Плоткина к этому коду позволяет получить хорошие коды длины n, где 2 m ≤ n ≤ 2 m + 2 m−4 Подставляя полный четновесовой код D длины 17 и расширенный код Романо- ва C длины 17 в конструкцию Плоткина, получаем код длины 34 со следующими хорошими параметрами: D : (17, 2 16 , 2), C : (17, 85 64 · 2 11 , 4) =⇒ (34, 85 64 · 2 27 , 4). Укорачивая этот код дважды, получаем коды длин 33 и 32 со следующими пара- метрами: (34, 85 64 · 2 27 , 4) =⇒ (33, 85 64 · 2 27 , 3) =⇒ (32, 85 64 · 2 26 , 3). Используя эти коды в качестве первого шага индукции, индукцией по m = log n можно доказать следующий факт. Теорема 24 (Романов А. М., 1983). Для любого целого числа n, удовлетво- ряющего 2 m ≤ n ≤ 2 m + 2 m−4 − 1, существует нелинейный (n, λ · 2 n−m−1 , 3) код, где λ = 85/64. Следует отметить, что для кодов длины больше 16 существуют другие коды с хорошими параметрами, исправляющие одну ошибку. Например код Этциона длины 17, мощности 5312, с кодовым расстоянием 3 и код Хямяляйнена длины 18, мощности 10496, с кодовым расстоянием 3 (см. [19]). Используя конструкцию Плоткина и эти коды, можно аналогичным образом получить бесконечные классы кодов с хорошими параметрами. Упражнение 28. Доказать теорему 23. 5.4. Коды Хямяляйнена Для изложения конструкции Хямяляйнена нам потребуется q-значный код Хэм- минга. 5.4. Коды Хямяляйнена 53 5.4.1. Код Хэмминга над GF (q) Основная идея построения проверочной матрицы q-значного кода Хэмминга, где q > 2, такая же, как и для двоичного кода Хэмминга. В качестве столбцов провероч- ной матрицы возьмем все q-значные векторы длины m такие, что любые два из них линейно независимы и найдутся три линейно зависимых. В отличие от двоичного случая, мы не можем брать все ненулевые векторы длины m, поскольку некоторые из них могут быть линейно зависимыми. Например, векторы (11011) и (22022) ли- нейно зависимы над полем Галуа GF (3). В целях устранения этой ситуации возьмем, например, в качестве столбцов проверочной матрицы все ненулевые столбцы такие, что первая ненулевая координата в каждом из них равна 1. Количество ненулевых векторов длины m над GF (q) равно q m − 1. Нетрудно показать, что среди них имеем 1 + q + q 2 + . . . + q m−1 = (q m − 1)/(q − 1) векторов с предписанным свойством. Следовательно, длина q-значного кода Хэммин- га с m проверочными символами равна n = (q m − 1)/(q − 1), мощность кода равна q n−m и по построению кодовое расстояние 3. Таким образом, мы построили код с параметрами [n = (q m − 1)/(q − 1), q n−m , d = 3] q . Обозначим его через H n q Пример 2. Построим код Хэмминга над GF (3) с двумя проверочными символа- ми. Рассмотрим проверочную матрицу в каноническом виде H = µ 1 1 1 0 1 2 0 1 ¶ . Она задает троичный код Хэмминга H 4 3 длины 4. Переходя от этой проверочной матрицы к порождающей матрице в каноническом виде G = µ 1 0 −1 −1 0 1 −1 −2 ¶ = µ 1 0 2 2 0 1 2 1 ¶ , построим все кодовые слова. Они имеют вид α 1 x 1 + α 2 x 2 , где x 1 , x 2 строки матрицы G и α 1 , α 2 ∈ GF (3) : информационные блоки =⇒ кодовые слова 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2 =⇒ 0 0 0 0 0 1 2 1 0 2 1 2 1 0 2 2 1 1 1 0 1 2 0 1 2 0 1 1 2 1 0 2 2 2 2 0 . 54 Глава 5. Каскадные методы Упражнение 29. Показать, что произвольный q-значный код с параметрами кода Хэмминга является совершенным. 5.4.2. Конструкция Хямяляйнена Основная идея конструкции Хямяляйнена состоит в следующем: сначала в пяти- значном коде Хэмминга H 6 5 с параметрами [6, 5 4 , 3] 5 ищется с помощью метода вклю- чений и исключений подкод максимально возможной мощности над алфавитом из четырех элементов, затем к этому подкоду применяется каскадирование с помощью классов смежности по двоичному коду Хэмминга длины 3. Рассмотрим детально эту красивую комбинаторную конструкцию. Пусть код Хэмминга H 6 5 длины n = 6 над полем Галуа GF (5), задан своей порож- дающей матрицей в каноническом виде: G = 1 0 0 0 1 4 0 1 0 0 1 3 0 0 1 0 1 2 0 0 0 1 1 1 . Произвольное кодовое слово имеет вид α 1 u 1 + α 2 u 2 + α 3 u 3 + α 4 u 4 , где u 1 , u 2 , u 3 , u 4 — строки из G и α i ∈ {0, 1, 2, 3, 4}, i = 1, 2, 3, 4. Мощность кода равна 5 4 . Зафиксируем произвольный элемент k из множества {1, 2, 3, 4}. Удалим из кода H 6 5 все кодовые слова, содержащие координату, равную k. Используя метод включе- ний и исключений, вычислим число таких кодовых слов в коде Хэмминга H 6 5 : 5 4 + 4 X i=1 (−1) i µ 6 i ¶ 5 4−i − 1 = 164. Имеется только один вектор с пятью координатами, равными k. Например, при k = 4, это вектор (424444). Полученный подкод фактически является сужением кода Хэм- минга H 6 5 над алфавитом из четырех элементов {0, 1, 2, 3}. Он имеет 164 кодовых слова и кодовое расстояние, равное 3. Для получения кода длины 18 применим следующую каскадную конструкцию к полученному подкоду: вместо элемента 0 подставим слова двоичного кода Хэмминга H 3 длины 3: 0 → {000, 111}; вместо каждого элемента из множества {1, 2, 3} возьмем слова класса смежности по коду H 3 таким образом, что любым двум элементам будут отвечать различные классы смежности. В результате получим двоичный код с параметрами (18, 10496, 3), т. е. длины 18, мощности 164 · 2 6 = 10496, с кодовым расстоянием 3. Таким образом, мы доказали следующее утверждение. 5.5. Каскадная конструкция Зиновьева (1988) 55 Теорема 25 (Хямяляйнен Х., 1988). Существует двоичный код с па- раметрами (18, 10496, 3). Укорачивая одну координату в этом коде, получаем код, мощность которого мень- ше мощности известного кода Этциона длины 17 (описание кода Этциона можно найти в работе [12]). Упражнение 30. Доказать, что подкод кода Хэмминга H 6 5 над подалфавитом {1, 2, 3, 4}, который не содержит элемента 0, состоит из 160 кодовых слов. Именно по этой причине в конструкции Хямяляйнена существенно, что k 6= 0. 5.5. Каскадная конструкция Зиновьева (1988) Рассмотрим каскадную конструкцию, предложенную В. А. Зиновьевым в 1988 г. Изложим ее для совершенных кодов (независимо этот метод построения в 1989 г. был предложен Ф. И. Соловьевой). Эта конструкция может быть рассмотрена как обобщение конструкции Хямяляйнена, изложенной в предыдущем разделе. Пусть A — произвольный q-значный совершенный код с параметрами (n, |A|, 3), q = 2 k , (например, код Хэмминга) над полем GF (2 k ), k > 1 с двумя проверочными символами. Его длина равна n = 2 k + 1. Пусть объединение двоичных совершенных кодов C 0 , C 1 , . . . , C r задает разбиение векторного пространства E r , r = 2 k − 1. Теорема 26 (Зиновьев В. А., 1988). Множество C N , определенное как C N = [ (x 1 ,x 2 ,...,x n )∈A C x 1 × C x 2 × . . . × C x n , является двоичным совершенным кодом длины N = nr = 2 2k − 1, k > 1. Доказательство. Длина кода, очевидно, равна N = n(q − 1) = (2 k + 1)(2 k − 1) = 2 2k − 1. Мощность кода несложно вычислить: |C N | = |H n q | · |C 0 | n = 2 k2 k −k (2 2 k −1−k ) 2 k +1 = 2 k2 k −k · 2 2 2k −1−k2 k −k = 2 N −log(N +1) , где N = 2 2k − 1. Убедимся, что кодовое расстояние равно 3. Рассмотрим два произвольных кодо- вых слова x = (x 1 , x 2 , . . . , x n ), y = (y 1 , y 2 , . . . , y n ) из A. Если x 6= y, то d(x, y) ≥ 3 и, значит, найдутся по крайней мере три координаты i, j, k, в которых различаются кодовые слова x и y. Следовательно, существуют три пары кодов в разбиении E n такие, что d(C x i , C y i ) ≥ 1, d(C x j , C y j ) ≥ 1, d(C x k , C y k ) ≥ 1. 56 Глава 5. Каскадные методы Отсюда следует d(C x 1 × C x 2 × . . . × C x n , C y 1 × C y 2 × . . . × C y n ) ≥ 3. Пусть x = y. Тогда имеем следующее множество кодовых векторов кода C N : C x 1 × C x 2 × . . . × C x n . Учитывая, что каждое множество C x i является совершенным двоичным кодом, полу- чаем, что расстояние между любыми двумя различными векторами этого множества равно по крайней мере 3. N 5.6. Каскадная конструкция Фелпса (1984) Пусть C 0 1 , C 0 2 , . . . , C 0 r и C 1 1 , C 1 2 , . . . , C 1 r — произвольные разбиения полных четно- весового кода и нечетно-весового кодов пространства E r (множество всех векторов пространства E r четного и нечетного веса соответственно) на расширенные совер- шенные двоичные коды длины r соответственно, пусть C m — произвольный расши- ренный совершенный двоичный код длины m в E m , в этом разделе пусть r = 2 k , m = 2 p . Для каждого вектора µ из C m возьмем r-значный код C µ с кодовым рассто- янием 2, длины m, |C µ | = r m−1 (C µ является MDS-кодом). Напомним, что MDS-код C длины m, объема |C|, с кодовым расстоянием d над GF (r) — это код, достигающий границы Синглтона, т. е. m − log r |C| = d − 1. Теорема 27 (Фелпс К. Т., 1984). Множество C n , определенное как C n = {(c 1 |c 2 | . . . |c m ) : c i ∈ C µ i j i , µ = (µ 1 , µ 2 , . . . , µ m ) ∈ C m , j = (j 1 , j 2 , . . . , j m ) ∈ C µ } является совершенным расширенным двоичным кодом длины n = mr. Далее код C m будем называть базовым кодом. Доказательство. Для доказательства теоремы используем другое, эквивалент- ное данному выше определение кода C n : C n = [ µ∈C m [ j∈C µ C µ 1 j 1 × . . . × C µ m j m . Очевидно, что длина кода равна n = mr. Также несложно вычислить мощность кода: |C n | = |(C µ i j i )| m · |C µ | · |C m | = (2 r−log r−1 ) m · r m−1 · 2 m−log m−1 = 2 n−log n−1 . Здесь n = mr. Несложно заметить, что для двух различных кодовых слов v и v 0 кода C n таких, что µ = µ 0 , j = j 0 выполняется d(v, v 0 ) ≥ 4. Убедимся, что для кодового расстояния справедливо d = d(C µ 1 j 1 × . . . × C µ m j m , C µ 0 1 j 0 1 × . . . × C µ 0 m j 0 m ) ≥ 4 для любых µ, µ 0 ∈ C m и j, j 0 ∈ C µ таких, что пары (µ, j) и (µ 0 , j 0 ) различны. 5.7. Обобщенная каскадная конструкция 57 Возможны приведенные ниже случаи. 1. Предположим, µ = µ 0 , j 6= j 0 Тогда d(j, j 0 ) ≥ 2 и найдутся координаты s, t такие, что j s 6= j s 0 , j t 6= j t 0 . Отсюда, учитывая, что C µ s j s и C µ s j 0 s одновременно являются четно- или нечетно-весовыми со- вершенными расширенными двоичными кодами (аналогично для кодов C µ t j t и C µ t j 0 t ), имеем d(C µ s j s , C µ s j 0 s ) ≥ 2 и d(C µ t j t , C µ t j 0 t ) ≥ 2. Следовательно, d(C µ 1 j 1 × . . . × C µ s j s × C µ t j t × . . . × C µ m j m , C µ 1 j 0 1 × . . . × C µ s j 0 s × C µ t j 0 t × . . . × C µ m j 0 m ) ≥ 4. 2. Пусть µ 6= µ 0 Векторы µ и µ 0 принадлежат базовому коду C m , т. е. d(µ, µ 0 ) ≥ 4 и найдутся четыре координаты t, s, e и l, в которых различаются µ и µ 0 . Следовательно, имеются четыре пары совершенных кодов C µ i j i и C µ 0 i j 0 i , i ∈ {t, s, e, l} такие, что d(C µ i j i , C µ 0 i j 0 i ) ≥ 1. В итоге имеем d ≥ 4. N Замечания 1. Выкалывание произвольной координаты кода C n приводит к совершенному двоичному коду длины mr − 1. 2. Для m = 2 код C m является тривиальным “расширенным совершенным” ко- дом, состоящим из одного вектора (01). Код C µ является r-значным кодом длины 2, с кодовым расстоянием 2, которому отвечает подстановка π на r элементах C µ = {(1, π(1)), (2, π(2)), . . . , (r, π(r))}. Таким образом, теорема 27 является обобщением теоремы 22. 3. Число неэквивалентных совершенных расширенных кодов длины n получен- ных по теореме 27 будет не менее 2 2 n+1 2 (1−εn) , где ε n → 0 при n → ∞. 4. Обобщение конструкции Фелпса было дано Д. С. Кротовым в 2000 г. 5.7. Обобщенная каскадная конструкция Пусть B является q B -значным ¡ n B , K 1 , d B,1 ¢ кодом. Предположим, что код B раз- бивается на q 1 подкодов: B = q 1 −1 [ i=0 B i , где B i является q B -значным (n B , K 2 , d B,2 ) кодом, i = 0, 1, . . . , q 1 − 1. 58 Глава 5. Каскадные методы Предположим далее, что B i разбивается на q 2 подкодов: для i = 0, 1, . . . , q 1 − 1 имеем B i = q 2 −1 [ j=0 B i,j , где B i,j является q B -значным ¡ n B , K 3 , d B,3 ¢ кодом, K 3 = q 3 . Пусть произвольное кодовое слово b ∈ B имеет номер k в B i,j , тогда тройка (i, j, k) ∈ {0, . . . , q 1 − 1} × {0, . . . , q 2 − 1} × {0, . . . , q 3 − 1} однозначно характеризует вектор b, это можно записать как b = b(i, j, k). Для каждого ` = 1, 2, 3, рассмотрим q ` -значный ¡ n A , K A,` , d A,` ¢ код A ` и его про- извольное кодовое слово a ` = (a ` 1 , . . . , a ` n A ) ∈ A ` . Для любого s = 1, . . . , n A тройка (a 1 s , a 2 s , a 3 s ) дает кодовое слово b = b(a 1 s , a 2 s , a 3 s ) из B. Пусть C = { ¡ b(a 1 1 , a 2 1 , a 3 1 )| . . . |b(a 1 n A , a 2 n A , a 3 n A ) ¢ : a ` ∈ A ` , 1 ≤ ` ≤ 3}. (5.1) Теорема 28 (Зиновьев В. А., 1975). Множество C является q B -значным кодом длины n C = n A n B , мощности K A,1 K A,2 K A,3 , с кодовым расстоянием d C ≥ min{d A,1 d B,1 , d A,2 d B,2 , d A,3 d B,3 }. B i B 0 B 1 B q -1 1 . . . . . . . . . b=b(i,j,k) . . . B i,0 B i,q -1 2 B i, j 1 2 k . . ... . ... Рис. 9 Иллюстрация к теореме 28 Рассмотрим двоичный случай. Пусть B = E n B , B = E n B • ∪ (E n B \ E n B • ), где E n B • — полный четно-весовой код B, n B = 2 m . Рассмотрим произвольные разбиения кодов E n B • и E n \ E n B • на 2 m расширенных совершенных кодов длины n B . Пусть A 1 — произвольный расширенный совершенный двоичный код (n A , 2 n A −1−u , 4), n A = 2 u . Пусть A 2 является n B -значным (n A , n n A −1 B , 2) кодом (MDS кодом с расстоянием 2) и A 3 является q 3 -значным (n A , q n A 3 , 1) кодом, где q 3 = 2 n B −1−m Используя конструкцию последней теоремы, формула (5.1) позволяет получить расширенный совершенный двоичный код C длины 2 m+n Теорема 29 (Зиновьев В. А., Лобстейн А., 1997). Код C является расши- ренным совершенным двоичным кодом C длины 2 m+n . 5.7. Обобщенная каскадная конструкция 59 Замечания 1. Перечисление расширенных совершенных двоичных кодов длины 16, полу- ченных обобщенной каскадной конструкцией, было получено В. А. Зиновьевым и Д. В. Зиновьевым в 2002 г., а именно ими было доказано, что существует 285 неэк- вивалентных таких кодов. 2. Следует отметить, что конструкция Фелпса может быть описана в терминах обобщенной каскадной конструкции Зиновьева. Глава 6 Поля Галуа 6.1. Основные определения В этой главе приведем необходимые определения и утверждения о полях Галуа (см. [1, 2, 8, 21, 24]), которые потребуются в дальнейшем для изложения теории циклических кодов. Определение. Алгебраическая система < F ; +, · > называется полем, если: (i) < F ; + > является коммутативной группой по сложению (с единичным эле- ментом 0), (ii) < F \ {0}; · > является коммутативной группой по умножению (с единичным элементом 1), (iii) Выполнены законы дистрибутивности: для любых элементов a, b, c ∈ F спра- ведливо a(b + c) = ab + ac, (b + c)a = ba + ca. Порядком поля называется число его элементов. Поле F называется конечным, если оно имеет конечный порядок. В противном случае поле называется бесконечным. Примерами бесконечных полей являются < Q; +, · >, < R; +, · >, < C; +, · >, где Q, R, C обозначают множества рациональных, вещественных и комплексных чисел соответственно, а операции + и · являются обычными операциями сложения и умно- жения. Примером конечного поля является кольцо вычетов < Z p ; +, · > целых чисел по модулю простого числа p. Далее такое поле будем называть простым и обозначать через F p Определение. Характеристикой поля F называется наименьшее положитель- ное целое число p такое, что в поле F справедливо равенство 1 + . . . + 1 | {z } p раз = 0. Поскольку в поле нет делителей нуля, характеристика p всегда является простым числом. Если такого числа не существует, то говорят, что поле F имеет характери- стику 0. Очевидно, любое конечное поле имеет характеристику отличную от нуля. 60 6.1. Основные определения 61 Определение. Подкольцо < I; +, · > произвольного кольца < R; +, · > называ- ется идеалом, если для любых элементов u ∈ I, v ∈ R выполняется u · v ∈ I и v · u ∈ I. Например, подкольцо < pZ; +, · > является идеалом кольца целых чисел < Z; +, · >. Пусть < F ; +, · > — некоторое поле. Рассмотрим кольцо F [x] всех многочленов от переменной x с коэффициентами из поля F . Пусть s(x) — произвольный многочлен из F [x]. Тогда множество (s(x)) = { c(x) · s(x) | c(x) ∈ F [x] } (6.1) образует идеал кольца F [x]. Верно и обратное, любой идеал кольца F [x] представим в виде совокупности произведений многочленов (6.1) для подходящего многочлена s(x). Без ограничения общности можно считать, что s(x) многочлен наименьшей сте- пени в идеале (s(x)). Пользуясь алгоритмом Евклида для многочленов, можно пока- зать, что в любом идеале такой многочлен s(x) существует и единствен. Рассмотрим фактор-кольцо F [x]/(s(x)) кольца всех многочленов F [x] по модулю идеала (s(x)). Элементами фактор-кольца F [x]/(s(x)) являются всевозможные многочлены степе- ни меньшей, чем степень s(x), а операции сложения и умножения в фактор-кольце производятся по модулю многочлена s(x). Если степень многочлена s(x) равна m и поле F конечно, то фактор-кольцо F [x]/(s(x)) содержит в точности |F | m элементов. Определение. Многочлен f (x) из кольца F [x] называется неприводимым над полем F , если он нормированный (со старшим коэффициентом, равным 1) и не может быть представлен в виде произведения двух многочленов из F [x] меньших степеней. Справедлива следующая Теорема 30. Пусть f (x) — многочлен степени m с коэффициентами из про- стого поля F p и (f (x)) — идеал, порожденный многочленом f (x) в кольце F p [x]. Фактор-кольцо F p [x]/(f (x)), состоящее из p m элементов, является полем тогда и только тогда, когда многочлен f (x) неприводим над F p . Пример 3. Пусть p = 2, F 2 = {0, 1}. Рассмотрим многочлен f (x) = 1 + x 3 + x 4 Несложно проверить, что он неприводим над F 2 . Действительно, так как элементы 0 и 1 не являются корнями, то f (x) не имеет линейных многочленов x и x + 1 в качестве делителей. Легко проверить, что единственный неприводимый над F 2 мно- гочлен второй степени x 2 +x+1 также не делит f (x). Следовательно, многочлен f (x) неприводим и по теореме 30 фактор-кольцо F 2 [x]/(f (x)) является конечным полем с 2 4 элементами. Все 16 его элементов представимы как многочлены степени меньшей 4 с операциями сложения над F 2 и умножения по модулю f (x). Например, (x 3 + x + 1)(x 2 + 1) = x 5 + x 3 + x 2 + x 3 + x + 1 = x 5 + x 2 + x + 1 = x(x 4 + x) + x 2 + x + 1 = (x 3 + 1 + x) + x 2 + x + 1 = x 3 + x 2 (mod f (x)). |