Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
m −1 − 1 на множители, имеем g(x) = M (i 1 ) (x) · . . . · M (i t ) (x) для некоторых представителей циклотомических классов i 1 , . . . , i t Определение. Корни порождающего многочлена g(x) называются нулями кода. Теорема 43. О нулях кода. Пусть попарно различные элементы β 1 , . . . , β r из GF (p m ) являются корнями порождающего многочлена g(x) степени r циклического кода. Многочлен f (x) с коэффициентами из GF (p) принадлежит этому коду тогда и только тогда, когда f (β 1 ) = . . . = f (β r ) = 0. Доказательство. Необходимость. Пусть f (x) — кодовый многочлен. Тогда по теореме 38 имеем f (x) = g(x)q(x), где deg q(x) < n−r. Подставляя β i вместо x для i = 1, . . . , r, получаем f (β i ) = g(β i )q(β i ), где g(β i ) = 0. Отсюда следует, что β i — корень f (x). Достаточность. Пусть β i — корень f (x) для всех i = 1, . . . , r и справедливо f (x) = g(x)q(x) + r(x), 81 82 Глава 8. Коды БЧХ где deg r(x) < r. Подставляя β i , получаем f (β i ) = g(β i )q(β i ) + r(β i ), где f (β i ) = 0 и g(β i ) = 0. Отсюда следует r(β i ) = 0 для всех i = 1, . . . , r. Поскольку deg r(x) < r и все β i различны, заключаем, что r(x) = 0. Из теоремы 38 следует, что f (x) — кодовый. N 8.2. Циклическое представление кода Хэмминга Теорема 44. Двоичный код Хэмминга является циклическим кодом с порож- дающим многочленом g(x) = M (1) (x). Доказательство. Проверочная матрица двоичного кода Хэмминга H n длины n = 2 m − 1, по определению, состоит из всех ненулевых векторов-столбцов длины m. Пусть α — примитивный элемент поля Галуа GF (2 m ). Тогда α является порождаю- щим элементом мультипликативной группы поля GF (2 m ) и все элементы 1, α, α 2 , . . . , α 2 m −2 различны и могут быть представлены как ненулевые двоичные m-векторы. Таким образом, проверочную матрицу H двоичного кода Хэмминга с параметрами [n = 2 m − 1, k = n − m, d = 3] можно представить в виде H = ¡ 1 α 1 α 2 . . . α 2 m −2 ¢ , где каждый элемент α i должен быть заменен на соответствующий ему двоичный вектор-столбец длины m. По определению, вектор c = (c 0 , c 1 , . . . , c n−1 ) принадлежит коду H n тогда и толь- ко тогда, когда выполнено H · c T = 0 т. е. n−1 X i=0 c i · α i = 0. Другими словами, элемент α является корнем многочлена c(x): c(α) = 0. Последнее равенство, согласно свойству 2 минимальных многочленов (см. разд. 7.6.), имеет место в том и только том случае, когда минимальный многочлен M (1) (x) эле- мента α делит многочлен c(x). Таким образом, код H n состоит из всех многочленов, кратных многочлену M (1) (x). N 8.3. Определитель Вандермонда 83 Пример 7. Для n = 7 код Хэмминга H 7 имеет проверочную матрицу H = ¡ 1 α α 2 α 3 α 4 α 5 α 6 ¢ = 0 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1 , где α — корень примитивного минимального многочлена M (1) (x) = 1 + x + x 3 8.3. Определитель Вандермонда Для доказательcтва теоремы 45 о границе Боуза (см. следующий разд.) нам по- требуется матрица Вандермонда. Определение. Матрицей Вандермонда называется матрица A = 1 a 1 a 2 1 . . . a n−1 1 1 a 2 a 2 2 . . . a n−1 2 . . . 1 a n a 2 n . . . a n−1 n , где a 1 , a 2 , . . . , a n — элементы некоторого конечного поля. Лемма 8 Вандермонда. Если все a i , i = 1, . . . , n различны, то det A 6= 0. Доказательство. Индукцией по n докажем формулу det A = n−1 Y j=1 n Y i=j+1 (a i − a j ). (8.1) Для n = 2 имеем det A = det µ 1 a 1 1 a 2 ¶ = a 2 − a 1 . Формула (8.1) справедлива. Предположим, что (8.1) выполнена для n − 1. Докажем ее для n. Запишем det A = det 1 a 1 a 2 1 . . . a n−2 1 a n−1 1 1 a 2 a 2 2 . . . a n−2 2 a n−1 2 . . . 1 a n a 2 n . . . a n−2 n a n−1 n . Домножим каждый i-й столбец матрицы (кроме последнего) на −a 1 и прибавим его к (i + 1)-му столбцу. От этого, как известно, определитель матрицы не изменится. Получим det A = det 1 0 0 . . . 0 0 1 (a 2 − a 1 ) (a 2 − a 1 )a 2 . . . (a 2 − a 1 )a n−3 2 (a 2 − a 1 )a n−2 2 . . . . . . . . . 1 (a n − a 1 ) (a n − a 1 )a n . . . (a n − a 1 )a n−3 n (a n − a 1 )a n−2 n . Раскладывая определитель по первой строке, имеем det A = det (a 2 − a 1 ) (a 2 − a 1 )a 2 . . . (a 2 − a 1 )a n−3 2 (a 2 − a 1 )a n−2 2 . . . . . . . . . (a n − a 1 ) (a n − a 1 )a n . . . (a n − a 1 )a n−3 n (a n − a 1 )a n−2 n . 84 Глава 8. Коды БЧХ Вынесем из каждой j-й строки множитель (a j − a 1 ), тогда det A = (a 2 − a 1 ) . . . (a n − a 1 ) · det 1 a 2 . . . a n−3 2 a n−2 2 . . . . . . . . . 1 a n . . . a n−3 n a n−2 n . Отсюда, по предположению индукции, заключаем det A = (a 2 − a 1 ) . . . (a n − a 1 ) · n−1 Y j=2 n Y i=j+1 (a i − a j ) = n−1 Y j=1 n Y i=j+1 (a i − a j ). Таким образом, формула (8.1) доказана. Очевидно, что det A отличен от нуля тогда и только тогда, когда все a i различны. N 8.4. Граница БЧХ Следующая теорема называется границей Боуза-Чоудхури-Хоквингема (кратко границей БЧХ) или теоремой о конструктивном расстоянии циклического кода. Эта теорема позволяет оценивать кодовое расстояние снизу. Теорема 45. Граница БЧХ. Пусть g(x) — порождающий многочлен цикли- ческого кода C длины n такой, что существуют целые числа b ≥ 0 и δ > 1 такие, что выполняется g(α b ) = g(α b+1 ) = . . . = g(α b+δ−2 ) = 0, т. е. δ − 1 подряд идущих степеней примитивного элемента α поля GF (p m ) явля- ются корнями g(x). Тогда кодовое расстояние d не меньше δ. Замечание. Число δ называется конструктивным расстоянием кода. Доказательство. Рассмотрим произвольный кодовый вектор c = (c 0 , c 1 , . . . , c n−1 ) и соответствующий ему многочлен c(x). Поскольку элементы α b , α b+1 , . . . , α b+δ−2 яв- ляются нулями кода C, то по теореме 43 о нулях кода имеем c(α b ) = c(α b+1 ) = . . . = c(α b+δ−2 ) = 0. Отсюда получаем систему уравнений c 0 + c 1 α b + c 2 α 2b + . . . + c n−1 α (n−1)b = 0 c 0 + c 1 α b+1 + c 2 α 2(b+1) + . . . + c n−1 α (n−1)(b+1) = 0 . . . c 0 + c 1 α b+δ−2 + c 2 α 2(b+δ−2) + . . . + c n−1 α (n−1)(b+δ−2) = 0 Иначе говоря, выполняется равенство H · c T = 0, (8.2) где матрица H = 1 α b α 2b . . . α (n−1)b 1 α b+1 α 2(b+1) . . . α (n−1)(b+1) . . . 1 α b+δ−2 α 2(b+δ−2) . . . α (n−1)(b+δ−2) 8.5. Коды БЧХ 85 не обязательно является полной проверочной матрицей кода C, поскольку порождаю- щий многочлен g(x) возможно имеет и другие корни, отличные от α b , α b+1 , . . . , α b+δ−2 Кроме того, строки этой матрицы могут оказаться линейно зависимыми. Другими словами, код C 0 , заданный проверочной матрицей H, будет содержать в качестве подкода код C, но возможно не будет совпадать с ним. Достаточно оценить кодовое расстояние кода C 0 , так как оно, очевидно, не будет больше кодового расстояния ко- да C. Поэтому если мы покажем, что любые δ − 1 или менее столбцов матрицы H линейно независимы, то кодовое расстояние кода C 0 (а следовательно, и C) будет по меньшей мере δ согласно теореме 3 из разд. 1.2. Предположим, что кодовый вектор c имеет вес w меньший δ, т. е. найдутся w линейно зависимых столбцов H и w < δ. Пусть ненулевые координаты вектора c имеют номера a 1 , a 2 , . . . , a w . Построим квадратную матрицу H 0 из матрицы H сле- дующим образом: выберем w первых строк из матрицы H и вычеркнем все столбцы с номерами, отличными от a 1 , a 2 , . . . , a w . Таким образом, матрица H 0 имеет вид H 0 = α a 1 b α a 2 b . . . α a w b α a 1 (b+1) α a 2 (b+1) . . . α a w (b+1) . . . . α a 1 (b+w−1) α a 2 (b+w−1) . . . α a w (b+w−1) . Из равенства (8.2) следует, что H 0 · c a 1 c a 2 c a w = 0. Последнее равенство возможно, только если матрица H 0 вырождена, т. е. det H 0 = 0. Но с другой стороны, имеем det H 0 = α a 1 b+a 2 b+...+a w b · det 1 1 . . . 1 α a 1 α a 2 . . . α a w . . . . α a 1 (w−1) α a 2 (w−1) . . . α a w (w−1) 6= 0, так как определитель в последнем равенстве есть определитель Вандермонда со все- ми различными элементами, и согласно лемме 8 он не равен нулю. Из полученного противоречия следует, что в линейном коде C не существует ко- дового слова веса меньше δ. Следовательно, кодовое расстояние C не меньше δ. N 8.5. Коды БЧХ Определение. Кодом БЧХ над полем GF (p) длины n = p m − 1 с конструктив- ным расстоянием δ > 1 называется циклический код с порождающим многочленом наименьшей степени, нулями которого являются элементы α b , α b+1 , . . . , α b+δ−2 , 86 Глава 8. Коды БЧХ где α — примитивный элемент поля GF (p m ) и b — некоторое неотрицательное целое число. Замечание. Для кодов БЧХ в литературе имеет место более общее определение. Нами рассматриваются так называемые примитивные коды БЧХ, т. е. коды, длина которых равна n = p m − 1. Далее термин примитивные будет опущен. Коды БЧХ при b = 1 иногда называют кодами БЧХ в узком смысле. Справедливо следующее (эквивалентное) определение кодов БЧХ. Определение. Кодом БЧХ над полем GF (p) длины n = p m −1 с конструктивным расстоянием δ > 1 называется циклический код с порождающим многочленом g(x) = НОК{M (b) (x), M (b+1) (x), . . . , M (b+δ−2) (x)}, где b — некоторое неотрицательное целое число. Теорема 46 Код БЧХ над GF (p) длины n = p m −1 с порождающим многочленом g(x) = НОК{M (b) (x), M (b+1) (x), . . . , M (b+δ−2) (x)} для некоторого целого b ≥ 0 имеет параметры [n = p m − 1, k ≥ n − (δ − 1)m, d ≥ δ]. Доказательство. Согласно теореме 45 о границе БЧХ, кодовое расстояние ко- да не меньше δ. Из вида порождающего многочлена кода следует, что проверочная матрица кода БЧХ равна H = 1 α b α 2b . . . α (n−1)b 1 α b+1 α 2(b+1) . . . α (n−1)(b+1) . . . 1 α b+δ−2 α 2(b+δ−2) . . . α (n−1)(b+δ−2) , где каждый элемент должен быть заменен на соответствующий столбец из m эле- ментов поля GF (p). Строки этой матрицы задают проверочные соотношения кода. Общее число строк равно (δ − 1)m, но они могут оказаться линейно зависимыми, поэтому для числа проверок выполняется r ≤ (δ − 1)m и, следовательно, для размерности кода имеем k ≥ n − (δ − 1)m, что завершает доказательство теоремы. N |