Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
3. Существуют ли другие конечные поля? Ответы на эти вопросы будут приведены в следующем разделе. 6.2. Строение конечных полей Теорема 31. Для любого простого числа p и любого положительного целого числа m существует единственное с точностью до изоморфизма поле порядка p m . Конечное поле порядка p m называется полем Галуа и обозначается GF (p m ) в честь первого исследователя таких полей Эвариста Галуа. Порядком произвольного элемента β некоторого конечного поля называется наи- меньшее целое положительное число k такое, что β k = 1. Непосредственно из опреде- ления следует, что в конечном поле GF (p m ) для элемента β порядка k все элементы 1, β, β 2 , . . . , β k−1 различны. Поэтому порядок каждого элемента поля GF (p m ) коне- чен и не превышает числа p m −1. Элемент α поля GF (p m ) называется примитивным, если его порядок равен p m − 1. Многочлен, корнем которого является примитивный элемент, называется примитивным многочленом. Заметим, что не всякий неприво- димый многочлен является примитивным. Пусть (a, b) означает наибольший общий делитель чисел a и b. Имеют место сле- дующие утверждения. Лемма 6. Пусть элементы β и γ коммутативной группы имеют порядки k и l соответственно, причем (k, l) = 1. Тогда порядок элемента βγ равен kl. Лемма 7. Пусть порядок элемента β коммутативной группы равен k. Тогда порядок элемента β l равен k (k,l) . Справедлива Теорема 32. Ненулевые элементы поля GF (p m ) образуют циклическую группу порядка p m − 1 относительно умножения. Доказательство. Пусть n — максимальный порядок ненулевых элементов поля GF (p m ) и α — элемент порядка n, т. е. α n = 1. Отсюда следует, что n ≤ p m − 1, так как все n степеней элемента α различны между собой и не равны 0. Пусть β — произвольный элемент поля порядка k, т. е. β k = 1. Покажем, что тогда k | n (т. е. k делит n). Предположим противное: k - n. Рассмотрим элемент β (k,n) . По лемме 7 его порядок равен k (k,n) , т. е. (β (k,n) ) k (k,n) = 1. 6.2. Строение конечных полей 63 Числа k (k,n) и n взаимно просты, следовательно, по лемме 6 порядок элемента α · β (k,n) равен nk (n,k) , т. е. (α · β (k,n) ) nk (n,k) = 1. Но число nk (n,k) строго больше n, что противоречит выбору n. Отсюда заключаем, что k | n. Другими словами, любой ненулевой элемент поля является корнем многочлена x n − 1 = 0. Поскольку степень этого многочлена равна n, то он имеет не больше, чем n различных корней в данном поле GF (p m ), поэтому p m − 1 ≤ n. Таким образом, показано, что в поле GF (p m ) найдется элемент α порядка n = p m − 1. Все ненулевые элементы GF (p m ) являются различными степенями α. N Эта группа, состоящая из ненулевых элементов, называется мультипликатив- ной группой поля GF (p m ). Каждый образующий элемент этой группы, очевидно, является примитивным элементом поля. Справедливо и обратное. Несложно пока- зать, что поле GF (p m ) содержит в точности ϕ(p m − 1) примитивных элементов, где ϕ обозначает функцию Эйлера. В качестве следствия получаем следующий факт. Теорема 33 (Теорема Ферма). Каждый элемент поля GF (p m ) удовлетворя- ет уравнению x p m − x = 0, т. е. в поле GF (p m ) справедливо разложение x p m − x = Y β∈GF (p m ) (x − β). Следующая теорема говорит о том, что конечных полей порядка, отличного от p m , не существует. Теорема 34. Пусть F — конечное поле порядка q характеристики p. Тогда для некоторого положительного целого числа m справедливо равенство q = p m . Доказательство. Покажем, что поле F может быть построено как линейное m- мерное пространство над GF (p) для некоторого положительного целого числа m. Поскольку характеристика поля F равна p, можно показать, что поле F содержит GF (p) в качестве наименьшего подполя. Пусть m — мощность базиса поля F над GF (p), т. е. произвольный элемент u ∈ F может быть представлен в виде u = a 1 v 1 + . . . + a m v m (6.2) для некоторых a i ∈ GF (p) и элементы v i ∈ GF (q), i = 1, . . . , m линейно независимы над GF (p). Тогда верно q ≤ p m . С другой стороны, так как элементы v 1 , . . . , v m об- разуют базис поля F , все элементы u вида (6.2) различны при различных a 1 , . . . , a m и принадлежат полю F . Следовательно, q ≥ p m . Таким образом, доказано q = p m . N 64 Глава 6. Поля Галуа Теорема 35. Для любых элементов a, b произвольного поля характеристики p и любого положительного целого числа s справедливо равенство (a − b) p s = a p s − b p s . В заключение приведем сводку основных результатов, относящихся к полям Галуа и необходимых нам в дальнейшем: 1. Число элементов произвольного поля Галуа равно степени простого числа. 2. Для любого простого числа p и любого целого числа m ≥ 0 существует единственное с точностью до изоморфизма поле Галуа GF (p m ). 3. Наименьшим подполем поля GF (p m ) является поле GF (p). 4. Поле GF (p k ) является подполем поля GF (p m ) тогда и только тогда, когда k делит m. 5. Любое поле GF (p m ) содержит хотя бы один примитивный элемент. 6. Над каждым полем Галуа GF (p) существует хотя бы один примитивный многочлен любой положительной степени. 6.3. Примеры конечных полей Пример 4. Построим конечное поле GF (2 4 ) с помощью теоремы 30. Используем для этого неприводимый над GF (2) многочлен f (x) = x 4 + x + 1. Согласно теореме 30, поле GF (2 4 ) состоит из всех многочленов степени меньшей 4: 0 x x 2 x 3 1 x + 1 x 2 + 1 x 3 + 1 x 2 + x x 3 + x x 2 + x + 1 x 3 + x + 1 x 3 + x 2 x 3 + x 2 + 1 x 3 + x 2 + x x 3 + x 2 + x + 1 Определим на множестве элементов операции умножения и взятия обратного элемента. Особенно удобно производить эти операции с помощью представления всех ненулевых элементов поля GF (2 4 ) в виде степеней некоторого прими- тивного элемента α. Выберем его. Нетрудно проверить, что в качестве α 6.3. Примеры конечных полей 65 можно взять x. Действительно, все его степени по модулю f (x) различны между собой: x 1 = x, x 2 = x 2 , x 3 = x 3 , x 4 = x + 1, x 5 = x 2 + x, x 6 = x 3 + x 2 , x 7 = x 3 + x + 1, x 8 = x 2 + 1, x 9 = x 3 + x, x 10 = x 2 + x + 1, x 11 = x 3 + x 2 + x, x 12 = x 3 + x 2 + x + 1, x 13 = x 3 + x 2 + 1, x 14 = x 3 + 1, x 15 = 1, и, следовательно, порядок x равен 15. Представим поле с помощью таблицы. Здесь число i для элемента γ = α i называ- ется логарифмом γ (по основанию выбранного примитивного элемента α). Логарифм элемента 0 полагают обычно равным −∞. Логарифм Степень прим. эл-та Многочлен Вектор −∞ 0 0 (0000) 0 1 1 (1000) 1 α x (0100) 2 α 2 x 2 (0010) 3 α 3 x 3 (0001) 4 α 4 x + 1 (1100) 5 α 5 x 2 + x (0110) 6 α 6 x 3 + x 2 (0011) 7 α 7 x 3 + x + 1 (1101) 8 α 8 x 2 + 1 (1010) 9 α 9 x 3 + x (0101) 10 α 10 x 2 + x + 1 (1110) 11 α 11 x 3 + x 2 + x (0111) 12 α 12 x 3 + x 2 + x + 1 (1111) 13 α 13 x 3 + x 2 + 1 (1011) 14 α 14 x 3 + 1 (1001) Сложение элементов поля является обычным сложением по модулю 2 и не зависит от выбора примитивного элемента в поле. Например: α 7 + α 11 = (x 3 + x + 1) + (x 3 + x 2 + x) = x 2 + 1 = α 8 . Умножение ненулевых элементов поля, представленных в виде степеней прими- тивного элемента, проводится путем сложения показателей степеней по модулю 15. 66 Глава 6. Поля Галуа Например: (x 3 + x 2 ) · (x 3 + x 2 + 1) = α 6 · α 13 = α 19 (mod 15) = α 4 = x + 1. Операция умножения, в отличие от сложения, зависит от выбора многочлена f (x). Тем не менее, согласно теореме 31, какие бы неприводимые многочлены одинаковой степени не использовались нами для построения поля, все построенные поля будут изоморфны между собой. Нахождение обратного элемента покажем на примере. Найдем обратный элемент для многочлена x 3 + x 2 + 1 = α 13 , т. е. такой ненулевой элемент α k , что α 13 · α k = 1. Для этого запишем (x 3 + x 2 + 1) −1 = α −13 = α 15−13 = α 2 = x 2 . Нетрудно проверить, что решение найдено верно: (x 3 + x 2 + 1) · (x 2 ) = x 5 + x 4 + x 2 = ((x 2 + x) + (x + 1) + x 2 ) mod (f (x)) = 1 mod (f (x)). Возможность находить для заданного ненулевого многочлена обратный обеспечива- ется неприводимостью многочлена f (x) (аналогично и в общем виде для любого поля над GF (q)). Несложно убедиться, что в построенном поле элементы α 2 , α 4 также примитив- ные, а элементы α 3 , α 5 примитивными не являются. Например, степени элемента α 3 порождают не все поле, а только элементы α 3 , α 6 , α 9 , α 12 , α 15 = 1. Заметим, что многочлен f (x) в нашем случае — примитивный, поскольку x, его корень по построению, является примитивным элементом α. Пример 5. Построим конечное поле GF (2 4 ) с помощью неприводимого над GF (2) многочлена f (x) = x 4 + x 3 + x 2 + x + 1. Найдем некоторый примитивный элемент поля GF (2 4 ). Например, элемент x не является примитивным элементом, так как его порядок равен 5, что меньше 2 4 − 1 = 15. Действительно, x 5 = x · x 4 ≡ x · (x 3 + x 2 + x + 1) mod(f (x)) ≡ 1 mod(f (x)). В качестве примитивного элемента можно взять x + 1, несложно убедиться что его порядок равен 15. Представим поле с помощью таблицы. 6.4. Число неприводимых многочленов 67 Логарифм Степень прим. эл-та Многочлен Вектор −∞ 0 0 (0000) 0 1 1 (1000) 1 α x + 1 (1100) 2 α 2 x 2 + 1 (1010) 3 α 3 x 3 + x 2 + x + 1 (1111) 4 α 4 x 3 + x 2 + x (0111) 5 α 5 x 3 + x 2 + 1 (1011) 6 α 6 x 3 (0001) 7 α 7 x 2 + x + 1 (1110) 8 α 8 x 3 + 1 (1001) 9 α 9 x 2 (0010) 10 α 10 x 3 + x 2 (0011) 11 α 11 x 3 + x + 1 (1101) 12 α 12 x (0100) 13 α 13 x 2 + x (0110) 14 α 14 x 3 + x (0101) Таким образом, мы убедились, что с помощью различных многочленов можно найти различные (но эквивалентные) представления поля Галуа GF (2 4 ). 6.4. Число неприводимых многочленов Функция Мёбиуса определяется следующим образом: µ(d) = 1, если d = 1; (−1) r , если d — произведение r различных простых чисел; 0, в остальных случаях. Рассмотрим простое поле GF (p). Обозначим через I p (m) число неприводимых над GF (p) многочленов степени m. Теорема 36. Справедливо I p (m) = 1 m X d, d|m µ(d)p m d . Упражнение 31. Установить изоморфизм полей, приведенных в примерах 4 и 5. Упражнение 32. Доказать леммы 6 и 7 и теорему 35. Упражнение 33. Найти все неприводимые над GF (2) многочлены степени, не превышающей 3. Упражнение 34. Построить поле Галуа GF (2 2 ), используя неприводимый мно- гочлен x 2 + x + 1. Найти таблицы сложения и умножения элементов поля. 68 Глава 6. Поля Галуа Упражнение 35. Построить два представления поля Галуа GF (2 3 ), используя один неприводимый многочлен x 3 + x + 1 и разные примитивные элементы. Указать изоморфизм этих представлений. Упражнение 36. Доказать, что многочлен M(x) = x 5 + x 2 + 1 неприводим над GF (2). Упражнение 37. Построить поля Галуа: а) GF (2 3 ), используя неприводимый многочлен x 3 + x 2 + 1. Показать изоморфизм между построенным полем и полем из упражнения 35; б) GF (3 2 ), используя неприводимый многочлен x 2 + x + 2; в) GF (3 3 ), используя неприводимый многочлен x 3 + 2x + 1. Глава 7 Циклические коды В этой главе рассмотрим введение в теорию циклических кодов. Важность цик- лических кодов обусловлена тем, что: 1. Класс циклических кодов содержит много кодов с конструктивно задаваемым расстоянием; с кодовым расстоянием, близким к наилучшему, в особенности для кодов длины ≤ 100. 2. Для циклических кодов существуют сравнительно простые алгебраические ме- тоды декодирования и кодирования, поэтому именно циклические коды чаще всего используются для передачи информации в каналах связи с шумами. 7.1. Определение и свойства Определение. Линейный код длины n называется циклическим, если для любого кодового слова (x 1 , x 2 , . . . , x n ) слово (x 2 , . . . , x n , x 1 ) также является кодовым. Циклические коды обладают несложными процедурами кодирования и декодиро- вания, имеют хорошие алгебраические свойства, их группы автоморфизмов содержат циклические подстановки. Все совершенные линейные коды, коды Рида-Маллера и другие коды, построенные еще до того, как Прейндж ввел понятие циклического кода и описал общие свойства таких объектов, являются кодами, которые после пе- рестановки координат и несущественной модификации оказываются циклическими (см. [5]). Многие важнейшие блоковые коды, открытые позже, также оказались либо циклическими, либо тесно связанными с ними. Перейдем к алгебраическому описанию циклических кодов с помощью многочле- нов с коэффициентами из конечного поля. Обозначим через |