Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
r. Так как многочлен x r f (x)−r(x) делится на g(x), то по тео- реме 38 он принадлежит коду. В силу того что r(x) не меняет последние k компонент вектора, отвечающего многочлену x r f (x) − r(x), эти компоненты совпадают с ком- понентами информационной последовательности α. Таким образом, если многочлен −r(x) имеет вид −r(x) = λ 0 + λ 1 x + . . . + λ r−1 x r−1 , то информационному блоку α = (α 0 , α 1 , . . . , α k−1 ) отвечает кодовое слово x = (λ 0 , λ 1 , . . . , λ r−1 , α 0 , α 1 , . . . , α k−1 ). 7.4. Проверочный многочлен 75 Несистематический кодер. Рассмотрим простое несистематическое кодирова- ние для циклического кода длины n с порождающим многочленом g(x) степени r. Пусть информационному блоку α = (α 0 , α 1 , . . . , α k−1 ), k = n − r отвечает многочлен f (x) = α 0 + α 1 x + . . . α k−1 x k−1 . Сопоставим ему кодовый многочлен c(x) по правилу c(x) = f (x) · g(x). Упражнение 38. Найти два систематических кодера для кода длины 7 с по- рождающим многочленом g(x) = x 3 + x + 1. С помощью второго систематического кодера закодировать вектор (1101). 7.4. Проверочный многочлен По теореме 39 порождающий многочлен g(x) делит многочлен x n − 1. Определение. Многочлен h(x) такой, что g(x) · h(x) = x n − 1 называется проверочным многочленом циклического кода. Его степень k равна n − r. Утверждение 14. Для произвольного кодового слова c(x) циклического кода с проверочным многочленом h(x) справедливо c(x) · h(x) = 0 по модулю многочлена x n − 1. Доказательство. Согласно теореме 38, любой кодовый многочлен c(x) цикли- ческого кода имеет вид q(x) · g(x) и, следовательно, в фактор-кольце F [x]/(x n − 1) справедливо равенство c(x) · h(x) = q(x) · g(x) · h(x) = q(x) · (x n − 1) = 0. N Теорема 40. Проверочная матрица циклического кода длины n с проверочным многочленом h(x) = h 0 + h 1 x + . . . + h k x k имеет вид H = 0 . . . . . . 0 h k . . . h 1 h 0 0 . . . 0 h k . . . h 1 h 0 0 . . . . 0 h k . . . h 1 h 0 0 . . . 0 h k . . . h 1 h 0 0 . . . . . . 0 . (7.2) 76 Глава 7. Циклические коды Доказательство. Согласно утверждению 14, для любого кодового слова c(x) циклического кода выполняется c(x) · h(x) = 0. Тогда c(x) · h(x) = ³ n−1 X i=0 c i x i ´ · ³ n−r X j=0 h j x j ´ = 0, где c(x) = P n−1 i=0 c i x i . Коэффициент при x j , j = 0, 1, . . . , n − 1, в этом произведении равен n−1 X i=0 c i h j−i = 0, (7.3) где индексы берутся по модулю n. Эти равенства задают проверочные уравнения, которым должен удовлетворять код. Рассмотрим матрицу H = x 0 ... ... x r−2 x r−1 ... x n−2 x n−1 0 . . . . . . 0 h k . . . h 1 h 0 0 . . . 0 h k . . . h 1 h 0 0 . . . . 0 h k . . . h 1 h 0 0 . . . 0 h k . . . h 1 h 0 0 . . . . . . 0 ∼ ←−− h(x) ←−−− xh(x) ←−−−− x 2 h(x) . . . ←−−−−−−− x n−k−1 h(x) . Из уравнений (7.3) следует, что если вектор c = (c 0 , c 1 , c 2 , . . . , c n−1 ) кодовый, то H · c T = 0. (7.4) Так как deg h(x) = k = n − deg g(x) есть размерность кода, и строки H линейно независимы, то условие (7.4) является также достаточным для того, чтобы вектор c принадлежал коду. Таким образом, H — проверочная матрица циклического кода с проверочным многочленом h(x). N Пример 6. Для двоичного циклического [n, n−1, 2]-кода с проверкой на четность справедливо g(x) = x + 1, h(x) = x n − 1 x + 1 = x n−1 + x n−2 + . . . + x + 1. Тогда матрицы G = 1 1 0 0 . . . 0 0 0 0 1 1 0 . . . 0 0 0 . . . . 0 0 0 0 . . . 0 1 1 , H = ¡ 1 1 . . . 1 ¢ , являются соответственно порождающей и проверочной матрицами кода. 7.5. Декодирование циклического кода 77 7.5. Декодирование циклического кода Пусть при передаче кодового вектора a = (a 0 , a 1 , . . . , a n−1 ) произошли ошибки и на приемном конце получен вектор c = (c 0 , c 1 , . . . , c n−1 ) = a + ε, где ε = (ε 0 , ε 1 , . . . , ε n−1 ) — вектор ошибок. На языке многочленов имеем c(x) = a(x) + ε(x). Так как a(x), согласно теореме 38, делится на g(x), многочлены c(x) и ε(x) имеют при делении на g(x) одинаковые остатки. Другими словами, вектор ошибок нахо- дится среди тех наборов, которым соответствуют многочлены, дающие при делении на g(x) тот же остаток, что и многочлен c(x), соответствующий принятому вектору. Обратно, любой вектор, обладающий указанным свойством, может оказаться векто- ром ошибок. Из стратегии декодирования по принципу максимума правдоподобия в качестве вектора ошибки ε принимают вектор наименьшего веса (как наиболее вероятный вектор ошибок). Отыскание вектора ε можно осуществить, например, пе- ребором всевозможных векторов в порядке возрастания их весов вплоть до вектора, которому отвечает многочлен с нужным остатком. В зависимости от конкретной задачи на практике, как правило, проводят существенно более простые процедуры декодирования. Существуют также алгоритмы декодирования, использующие циклический сдвиг и позволяющие за счет этого сократить объем таблицы синдромов. Упражнение 39. Пусть для передачи информации использовался циклический код длины 7 с порождающим многочленом g(x) = x 3 + x + 1. Декодировать слово y = (1011110). 7.6. Минимальный многочлен и его свойства В этом разделе рассмотрим минимальные многочлены и их свойства, эти много- члены потребуются для построения циклических кодов, оценки их кодового рассто- яния (см. далее гл. 8). Определение. Минимальным многочленом элемента β ∈ GF (p m ) называется нормированный многочлен M(x) с коэффициентами из GF (p) наименьшей степени такой, что M(β) = 0. Пусть M(x) — минимальный многочлен над GF (p) элемента β из GF (p m ). Тогда имеют место следующие его свойства: 1. Многочлен M(x) неприводим. 78 Глава 7. Циклические коды 2. Если f (x) — такой многочлен, что f (β) = 0, то M(x) делит f (x). 3. Многочлен M(x) делит x p m − x. 4. Степень многочлена M(x) не превосходит m. 5. Степень многочлена M(x) делит m. 6. Степень минимального многочлена M(x) примитивного элемента равна m. 7. Если многочлен M(x) является минимальным для элемента β, то он ми- нимален и для элемента β p . Множество целых чисел по модулю p m − 1 следующим образом распадается на подмножества, называемые циклотомическими классами по модулю p m − 1: класс, содержащий число s, имеет вид C s = {s, ps, p 2 s, p 3 s, . . . , p m s −1 s}, где m s — наименьшее положительное целое число такое, что p m s · s ≡ s(mod(p m − 1)). Пусть M (i) (x) — минимальный многочлен элемента α i из GF (p m ), где α — примитив- ный элемент поля. Из свойства 7 следует, что все ненулевые элементы поля GF (p m ) вида α k , показатели степеней которых лежат в одном циклотомическом классе, име- ют один и тот же минимальный многочлен. Иначе говоря, над GF (p) выполнено равенство M (s) (x) = M (ps) (x) = M (p 2 s) (x) = M (p 3 s) (x) = . . . = M (p ms−1 s) (x). 8. Если число i принадлежит циклотомическому классу C s , то в поле GF (p m ) справедливо разложение M (i) (x) = Y j∈C s (x − α j ). Из теоремы Ферма (см. теорему 33) и свойства 8 следует Теорема 41. Над GF (p) справедливо равенство x p m −1 − 1 = Y s M (s) (x), где s пробегает все множество представителей циклотомических классов по мо- дулю p m − 1. Теорема 42. Многочлен x p m − x равен произведению всех нормированных непри- водимых над GF (p) многочленов, степени которых делят m. 7.7. Число циклических кодов 79 Эти теоремы позволяют находить неприводимые и минимальные многочлены. Вернемся к примеру 4 поля GF (2 4 ) из параграфа 6.3. Сначала выпишем все цикло- томические классы по модулю 15: C 0 = {0}, C 1 = {1, 2, 4, 8}, C 3 = {3, 6, 12, 9}, C 5 = {5, 10}, C 7 = {7, 14, 13, 11}. Затем рассмотрим разложение многочлена x 16 − x на неприводимые многочлены: x 16 + x = x(x + 1)(x 2 + x + 1)(x 4 + x + 1)(x 4 + x 3 + 1)(x 4 + x 3 + x 2 + x + 1). Задавая поле GF (2 4 ) с помощью неприводимого многочлена x 4 +x+1 и примитивного элемента α = x, получаем Элемент Минимальный многочлен элемента 0 x 1 M (0) (x) = x + 1 α, α 2 , α 4 , α 8 M (1) (x) = M (2) (x) = M (4) (x) = M (8) (x) = x 4 + x + 1 α 3 , α 6 , α 12 , α 9 M (3) (x) = M (6) (x) = M (12) (x) = M (9) (x) = x 4 + x 3 + x 2 + x + 1 α 5 , α 10 M (5) (x) = M (10) (x) = x 2 + x + 1 α 7 , α 14 , α 13 , α 11 M (7) (x) = M (14) (x) = M (13) (x) = M (11) (x) = x 4 + x 3 + 1 По свойству 6 полей Галуа (см. разд.6.2.) многочлен, задающий поле, всегда мо- жет быть выбран примитивным. Для этого нужно выбрать минимальный многочлен примитивного элемента. Однако задача определения какой из неприводимых много- членов является примитивным, весьма трудна. Упражнение 40. Доказать свойства 1–7 минимальных многочленов. 7.7. Число циклических кодов Свяжем изложенную ранее теорию полей Галуа с циклическими кодами. В разд. 7.2. было показано, что циклический код длины n над полем GF (p) существует для каждого многочлена g(x), делящего многочлен x n − 1, где n = p m − 1 для некоторого m > 0. Согласно теореме 41, имеем x n − 1 = M (1) (x)M (2) (x) . . . M (`) (x), где ` — число циклотомических классов по модулю n, на которые разбиваются числа от 0 до n − 1. Произведение произвольного подмножества следующего множества многочленов {M (1) (x), M (2) (x), . . . , M (`) (x)} дает порождающий многочлен g(x) для некоторого циклического кода. Тогда, за исключением тривиальных случаев g(x) = 1 и g(x) = x n − 1, получаем, что число нетривиальных циклических кодов длины n не превышает числа 2 ` − 2. 80 Глава 7. Циклические коды Какие из этих циклических кодов имеют наибольшее расстояние? Ответ на этот вопрос не прост. Еще раз вернемся к примеру 4 из разд. 6.3. В разложении многочлена x 15 −1 имеем пять сомножителей (см. разд. 7.6.). Следовательно, получаем 2 5 − 2 = 30 нетриви- альных циклических кодов длины 15. Рассмотрим, например, код с порождающим многочленом g(x) = (x 4 + x 3 + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 4 + x 2 + x + 1. Так как степень g(x) равна 8, то размерность кода k = n − 8 = 7. Однако определить кодовое расстояние кода из простых соображений не удается. Упражнение 41. Построить циклический код длины 7 с порождающим много- членом g(x) = (x 3 +x+1), найти его проверочный многочлен, определить параметры кода. Упражнение 42. Что собой представляет циклический код длины 15 с порожда- ющим многочленом g(x)? Найти его проверочный многочлен, определить параметры кода: a) g(x) = (x 4 + x + 1); б) g(x) = x(x + 1)(x 2 + x + 1)(x 4 + x 3 + 1)(x 4 + x 3 + x 2 + x + 1); в) g(x) = (x + 1)(x 2 + x + 1)(x 4 + x 3 + 1); в случаях б и в построить коды. Глава 8 Коды БЧХ 8.1. Нули кода Пусть α — примитивный элемент поля GF (p m ). Согласно теореме 41, над полем Галуа GF (p) справедливо разложение x p m −1 − 1 = Y s M (s) (x), где s пробегает все множество представителей циклотомических классов по модулю p m − 1. Пусть g(x) — порождающий многочлен степени r некоторого циклическо- го кода длины n = p m − 1. Тогда, в силу теоремы 39 и приведенного разложения многочлена x p |