Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
F простое конечное поле GF (p), где p — простое число. Напом- ним, что F [x] — кольцо всех многочленов от переменной x с коэффициентами из поля F . Оно ассоциативно, коммутативно и содержит единицу. В кольце F [x] рас- смотрим фактор-множество F [x]/(x n − 1), состоящее из классов вычетов кольца F [x] по модулю многочлена x n − 1. Множество F [x]/(x n − 1) замкнуто относительно опе- раций сложения + и умножения · и, следовательно, является кольцом. Заметим, что множество F [x]/(x n − 1) не является полем, так как многочлен x n − 1 приводим. 69 70 Глава 7. Циклические коды Все многочлены степени не больше n−1 попадают в различные классы вычетов и их можно выбрать в качестве представителей этих классов. Кольцо классов вычетов F [x]/(x n − 1) изоморфно n-мерному векторному пространству над F : c(x) = c 0 + c 1 x + c 2 x 2 + . . . + c n−1 x n−1 ←→ c = (c 0 , c 1 , c 2 , . . . , c n−1 ). В дальнейшем мы не будем различать векторы и многочлены степени меньше n, но из контекста всегда будет понятно, речь идет о многочленах или о векторах. Пусть дан многочлен c(x) = n−1 X i=0 c i x i = c 0 + c 1 x + . . . + c n−1 x n−1 . Обозначим через ←−− c(x) = n−1 X i=0 c n−i x i = c n−1 + c n−2 x + . . . + c 0 x n−1 инверсию многочлена c(x), записав его коэффициенты при степенях x в обратном порядке. Определение. Идеалом I кольца F [x]/(x n − 1) называется такое его линейное подпространство, что для любых многочленов r(x) ∈ F [x]/(x n − 1) и c(x) ∈ I много- член r(x) · c(x) принадлежит I. Теорема 37. Подпространство кольца F [x]/(x n − 1) является циклическим ко- дом тогда и только тогда, когда оно образует идеал. Доказательство. Существенным моментом в доказательстве этой теоремы яв- ляется то, что в кольце F [x]/(x n − 1) умножение многочлена на x соответствует циклическому сдвигу вектора в пространстве F n . Действительно, x · c(x) = x · (c 0 + c 1 x + c 2 x 2 + . . . + c n−1 x n−1 ) = = c n−1 + c 0 x + c 1 x 2 + . . . + c n−2 x n−1 . Таким образом, вектор (c 0 , c 1 , . . . , c n−1 ) переходит в вектор (c n−1 , c 0 , c 1 , . . . , c n−2 ), т. е. получаем циклический сдвиг в F n Достаточность. Пусть C — циклический код. Тогда для любого кодового векто- ра c, его циклический сдвиг принадлежит C. Другими словами, для любого кодового многочлена c(x) произведение x · c(x) принадлежит коду. Отсюда следует, в силу ли- нейности циклического кода, что f (x) · c(x) является кодовым многочленом, где f (x) — произвольный многочлен из F [x]/(x n − 1). Следовательно, C — идеал в кольце F [x]/(x n − 1). Необходимость. Пусть подпространство D кольца F [x]/(x n − 1) образует идеал. Рассмотрим многочлен c(x) ∈ D. По определению идеала, многочлен f (x) · c(x) при- надлежит D для любого многочлена f (x) ∈ F [x]/(x n − 1). Тогда x · c(x) принадлежит 7.2. Порождающий многочлен 71 D. Кроме того, сумма любых двух элементов из D также лежит в D и, следователь- но, D — циклический код. N Иногда пользуются следующим эквивалентным определением циклического кода. Определение. Циклическим кодом длины n называется идеал кольца F [x]/(x n − 1). 7.2. Порождающий многочлен Выберем в циклическом коде C ненулевой многочлен наименьшей степени, обо- значим его степень через r. Умножим многочлен на подходящий элемент поля F , чтобы он стал нормированным (или приведенным), т. е. чтобы коэффициент при старшей степени многочлена равнялся 1. В силу линейности кода C, полученный многочлен также принадлежит C. Обозначим его через g(x). Утверждение 12. Циклический код содержит единственный ненулевой нор- мированный многочлен наименьшей степени. Доказательство. Пусть существуют два нормированных многочлена f (x) и g(x) наименьшей степени r. Тогда многочлен f (x)−g(x), принадлежащий коду, имеет сте- пень меньше r, что приводит к противоречию. N Определение. Нормированный ненулевой многочлен наименьшей степени, при- надлежащий циклическому коду, называется порождающим многочленом кода и обо- значается через g(x). Теорема 38. Циклический код состоит из всех многочленов вида f (x) · g(x), где g(x) — порождающий многочлен кода степени r, степень f (x) меньше (n − r). Доказательство. Согласно тому что циклический код образует идеал в кольце F [x]/(x n − 1) (см. теорему 37), произведение любого многочлена f (x) из F [x]/(x n − 1) на g(x) принадлежит коду. Тогда произведения g(x) на все многочлены степени, меньшей чем n − r, принадлежат C. Покажем, что любой кодовый многочлен представим в виде такого произведения. Пусть c(x) — кодовый. Разделим его в кольце F [x]/(x n − 1) с остатком на многочлен g(x). Имеем c(x) = q(x)g(x) + s(x), где степень s(x) меньше степени g(x), а степень q(x) меньше n − r. Многочлен s(x) = c(x) − q(x)g(x) является кодовым, так как слагаемые в правой части принадлежат коду C и он ли- неен. Но степень многочлена s(x) меньше степени g(x) — наименьшей степени нену- левого многочлена в C. Отсюда s(x) = 0 и c(x) = q(x)g(x), т. е. c(x) имеет в кольце F [x]/(x n − 1) искомое представление. N Теорема 39. Циклический код длины n с порождающим многочленом g(x) су- ществует тогда и только тогда, когда g(x) делит x n − 1. 72 Глава 7. Циклические коды Доказательство. Необходимость. Пусть дан циклический код C длины n с порождающим многочленом g(x). Рассмотрим в кольце многочленов F [x] деление многочлена x n − 1 на g(x) с остатком: x n − 1 = q(x)g(x) + r(x), где степень r(x) меньше степени g(x). Переходя в кольцо F [x]/(x n − 1), получаем 0 = q(x)g(x) + r(x). Отсюда −r(x) = q(x)g(x). Из теоремы 37 следует, что многочлен q(x)g(x) принадле- жит коду и, следовательно, многочлен −r(x) кодовый, причем deg r(x) < deg g(x), что противоречит утверждению 12. Таким образом, r(x) = 0. Достаточность. Пусть многочлен g(x) делит x n − 1. Покажем, что тогда су- ществует циклический код длины n с порождающим многочленом g(x). Поскольку степень g(x) равна r, то размерность кода должна быть равна n − r. Рассмотрим векторы, отвечающие многочленам g(x), xg(x), x 2 g(x), . . . , x n−r−1 g(x), где r = deg g(x). Будучи циклическими сдвигами вектора g(x), они должны принад- лежать циклическому коду с порождающим многочленом g(x). Так как эти цикли- ческие сдвиги линейно независимы, то матрица G = x 0 x 1 ... x r x r+1 ... ... x n−1 g 0 g 1 . . . g r 0 . . . . . . 0 0 g 0 g 1 . . . g r 0 . . . 0 . . . . 0 . . . 0 g 0 g 1 . . . g r 0 0 . . . . . . 0 g 0 g 1 . . . g r ∼ g(x) xg(x) x 2 g(x) . . . x n−r−1 g(x) , где g(x) = g 0 + g 1 x + . . . + g r x r , имеет ранг n − r (т. е. имеем искомое количество кодовых слов в базисе линейно- го кода). Следует отметить, что в матрицу G не может быть включен многочлен x n−r+i g(x), i ≥ 0, поскольку по модулю многочлена x n − 1 он равен линейной комби- нации уже выбранных в G многочленов. Покажем, что линейный код с порождающей матрицей G является идеалом, по- рожденным многочленом g(x), в кольце F [x]/(x n − 1) и, кроме того, многочлен g(x) имеет наименьшую ненулевую степень в этом идеале. Для этого представим вектор, отвечающий произвольному многочлену f (x) = u(x)g(x) из F [x]/(x n − 1) в виде линейной комбинации строк матрицы G, по теореме 38 этот многочлен кодовый. Действительно, имеем f (x) = (u 0 + u 1 x + . . . + u n−r−1 x n−r−1 )g(x) = = u 0 g(x) + u 1 xg(x) + . . . + u n−r−1 x n−r−1 g(x). 7.3. Кодирование циклических кодов 73 Остается показать, что не существует в этом коде ненулевого многочлена со сте- пенью, меньшей степени многочлена g(x). Если найдется такой кодовый многочлен r(x), то он представим линейными комбинациями строк матрицы G, т. е. имеет вид r(x) = q(x)g(x) для некоторого многочлена q(x). Отсюда, переходя в кольцо F [x], получаем q(x)g(x) − r(x) = x n − 1, где по условию теоремы x n − 1 делится на g(x). Это возможно только в случае r(x) = 0. Таким образом, циклический код с порождающим многочленом g(x) по- строен. N Следствие 9. Порождающая матрица циклического кода длины n с порожда- ющим многочленом g(x) = g 0 + g 1 x + . . . + g r x r имеет вид G = g 0 g 1 . . . g r 0 . . . . . . 0 0 g 0 g 1 . . . g r 0 . . . 0 . . . . 0 . . . 0 g 0 g 1 . . . g r 0 0 . . . . . . 0 g 0 g 1 . . . g r . (7.1) Матрица G имеет n столбцов и n − r строк. 7.3. Кодирование циклических кодов Определение. Код длины n размерности k называется систематическим, если после вычеркивания некоторых (n − k) столбцов из его кодовой матрицы остаются в точности все различные векторы длины k. Утверждение 13. Любой циклический код эквивалентен систематическому коду. Для циклического кода существует простой способ нахождения порождающей матрицы в каноническом (или приведенно-ступенчатом) виде. При этом получается порождающая матрица того же кода, а не эквивалентного. Это существенно, по- скольку перестановка координат может нарушить свойство цикличности. Рассмотрим несколько общих принципов кодирования циклических кодов. Первый систематический кодер. Пусть циклический код C длины n имеет порождающий многочлен g(x) степени r. Тогда размерность k кода C равна n−r. Для построения порождающей матрицы G осуществим деление с остатком многочленов x n−1 , x n−2 , . . . , x n−k на g(x). Имеем x n−1 = g(x) · a 1 (x) + r 1 (x), x n−2 = g(x) · a 2 (x) + r 2 (x), ... x n−k = g(x) · a k (x) + r k (x). 74 Глава 7. Циклические коды Поскольку каждый многочлен x n−i − r i (x) для i = 1, 2, . . . , k делится на g(x), то он является кодовым по теореме 38. Степень остатка r i (x) не превышает r − 1. Пусть многочлен −r i (x) имеет вид −r i (x) = λ i,r−1 x r−1 + λ i,r−2 x r−2 + . . . + λ i,0 . Порождающая матрица G = 1 0 . . . 0 λ 1,r−1 λ 1,r−2 . . . λ 1,0 0 1 . . . 0 λ 2,r−1 λ 2,r−2 . . . λ 2,0 . . . . 0 0 . . . 1 λ n−r,r−1 λ n−r,r−2 . . . λ n−r,0 ∼ ←−−−−−−− x n−1 − r 1 x ←−−−−−−− x n−2 − r 2 x . . . ←−−−−−−− x n−k − r k x , строки которой отвечают многочленам ←−−−−−−−− x n−i − r i (x) для i = 1, 2, . . . , k, имеет приведенно-ступенчатый вид. Таким образом, для данного циклического кода най- дено систематическое представление. Второй систематический кодер. Можно рассмотреть систематическое коди- рование для циклического кода длины n с порождающим многочленом g(x) степени r без использования его порождающей матрицы. Пусть задана информационная по- следовательность α = (α 0 , α 1 , . . . , α k−1 ), k = n − r. Рассмотрим многочлен f (x) = α 0 + α 1 x + . . . + α k−1 x k−1 . Домножая его на x r , имеем многочлен x r f (x) = α 0 x r + α 1 x r+1 + . . . + α k−1 x n−1 . Разделив многочлен x r f (x) на g(x) с остатком, получим x r f (x) = g(x)q(x) + r(x), где степень r(x) меньше |