Вернер М. Основы кодирования (2004) (1151882), страница 23
Текст из файла (страница 23)
Определение и свойства двоичных циклических кодов(3.8)Эту связь можно выразить в видеX* • v{X)-= q(X) • {Хп + 1) + vW(X),(3.9)причем, операция сложения q(X) с v^(X) устраняет ненужные компоненты.Замечание. Мы рассматриваем векторные пространства кодовыхслов над GF(2). В двоичном поле справедливо 1 © 1 = О, т.к. обратным элементом к «1» является сама «1». Это полезное свойствоне всегда является справедливым в случае произвольного поля ГалуаGF(pm), что может привести к усложнению вычислений.Из (3.9) следует, что многочлен, соответствующий г-кратномуциклическому сдвигу вектора v можно получить, как остаток от деления многочлена Хгь(Х) на {Хп + 1).
В дальнейшем, мы покажем,что данное свойство может быть использовано для эффективногообнаружения ошибок.Теорема 3.2.1. В каждом циклическом коде существует единственный, отличный от нуля, кодовый многочлен д(Х) минимальной степени.Доказательство. Пусть существуют два многочлена минимальной степени д(Х) и д'(Х), отличных от нуля. Из свойства замкнутости линейного векторного кодового пространства следует, что суммад{Х) и д'(Х) является кодовым многочленом. Отсюда получаемд{Х)9'(Х)д(Х)+д'(Х)r= go + giX+--+grX= д'0= (goТаким образом, приходим к противоречию.(3.10)Глава 3. Циклические кодыТеорема 3.2.2. Если д(Х) - кодовый многочлен наименьшей степени г, то его коэффициент до = 1.Доказательство.многочленд^-'Цх)Сдвинем многочлен д(Х) п — 1 раз.
Получим= д1+92Х1+-• •+9гХг-1+0-Хг+0+-• •+О+доХп-1, (3.11)который также принадлежит коду. Его степень по определению неможет быть меньше г, поэтому до = 1. •Теорема 3.2.3. Пусть д(Х) - кодовый многочлен минимальной степени г. В этом случае, v(X) является кодовым многочленом тогда итолько тогда, когда он кратен д(Х).Доказательство. На нервом шаге докажем достаточность утверждения 3.2.3.Пусть v(X) = a(X)g(X). В этом случаеv(X)= a{X)-g{X)=(3.12)Так как степень многочлена д(Х) не превосходит г, а степень многочлена а(Х) не превосходит п — 1 — г, произведение а(Х)д(Х) несодержит членов степени, большей п — 1, то Хгд(Х) можно рассматривать как г-кратный сдвиг многочлена д(Х).
Таким образом,v(X) = o o + ais(1)(X) + • • • + an-i-rg^-^Hx).(3.13)Так как любой циклический сдвиг д(Х) так же является кодовыммногочленом, то v(X) представляет собой линейную комбинацию кодовых слов, т.е является кодовым словом.На втором шаге докажем необходимость утверждения 3.2.3. Пустьv(X) = с(Х) • д(Х) + Ь(Х),(3.14)где Ь(х) - возможный остаток от деления v(x) на д(х). Решим уравнение относительно Ь(х)b(X)=c(X)-g(X) + v(X).(3.15)Правая часть (3.15) представляет собой сумму двух кодовых многочленов, поэтому, Ь(х) также является кодовым многочленом. Таккак, по определению, степень Ь(х) должна быть меньше степени минимального многочлена д(х), Ь(х) соответствует нулевое кодовое слово. •3.2.
Определение и свойства двоичных циклических кодов 167;Теорема 3.2.4. В каждом циклическом (п, &)-коде существует только один многочлен минимальной степени г = п — к. называемый порождающим многочленом д{Х) = до + дуХ + ... + дТХТ такой, чтолюбой кодовый многочлен делится на д(Х).Для поиска порождающих многочленов важным является следующее утверждение:Теорема 3.2.5. Порождающий многочлен циклического кода д(Х)делит Хп + 1 без остатка.Доказательство.Умножив д(Х) на Хк, получим многочлен степени к+г = п. Этотже результат можно получить, если к циклическому сдвигу дк{Х)прибавить 1 + Хп для устранения лишней «1» при А"0 и компенсациинедостаточной компоненты Хп.
Таким образом,Хк • д(Х) =доХк+ •••+ дгХп= д^(Х) + 1 - Хп.Представим (3.16) как результат деления хкд(Х)(3.16)на Хп + 1(3.17)причем, д(к\Х) является остатком.Так как циклический сдвиг gW (X) сам является кодовым многочленом, то, согласно утверждению (3.3), существует такой многочлена(Х), чтодЮ(Х)=а(Х).д(Х).(3.18)Подставляя (3.18) в (3.17) и переставляя слагаемые, получимпкХ + 1 = [Х + а(Х)} • д(Х).(3.19)Таким образом, д(Х) делит Хп + 1 без остатка.
•Справедливо также обратное утверждение.Теорема 3.2.6. Если некоторый многочлен д(Х) стэпени п—к делитХп+1 без остатка, то д(Х) порождает некоторый циклический (п, к)код.Доказательство.Докажем, что все возможные произведения д(Х) на многочлены,степень которых не превышает к— 1, образуют некоторый линейный(п, &)-код и этот код является циклическим.Глава 3. Циклические кодыВсе произведения д{Х) на многочлен степени не вышеfc—1можнопредставить в виде---vn-lXn~l == {ао + агХ + • • • + ak^X*-1) • д(Х).(3.20)В соответствии с (3.20), всем возможным 1к наборам двоичныхкоэффициентов от оо до afc_i соответствуют 2fc различных кодовыхслов. Полученный код является линейным, так как сумма двух любых кодовых слов также принадлежит коду.Покажем теперь, что этот код является также и циклическим.Рассмотрим произведение X • v(X)X • v(X) = v0X + vxX2+ ••• + Vn^X*1-1Из этого следует, что для многочлена v^(X),циклическому сдвигу v(X), справедливо+ vn^Xn=(3.21)соответствующего«/>)(*) = X • v(X) + vn^(Xn + 1).(3.22)пТак как д{Х) делит v(X) и Х + 1, он также является делителемv^(X).
Таким образом, циклический сдвиг любого кодового словатакже принадлежит коду.Итак, множество 2к различных многочленов, делящихся на д(Х),образуют линейное векторное пространство циклического (п, &)-кода.•Теорему 3.2.6 можно использовать как руководство к построению циклических кодов. На самом деле, пусть, например, существуетпнекоторый многочлен степени г = п — к, на который делится Х + 1.Тогда, этот многочлен является порождающим многочленом д(Х)циклического (п, &)-кода.
При больших значениях п двучлен Xй + 1может иметь несколько делителей степени г. В связи с этим возникает вопрос: Какой из этих делителей порождает наилучший код? Ксожалению, на этот вопрос не существует однозначного ответа, темне менее, во многих случаях можно пользоваться таблицей наилучших двоичных циклических кодов, предлагаемой ITU (InternationalTelecommunication Union) (табл. 3.8).Пример: Порождающий многочлен циклического (7,4)-кода.Рассмотрим простейший циклический (7,4)-код. Для его построения требуется порождающий многочлен д(Х) степени г = 7 — к = 3,3.2. Определение и свойства двоичных циклических кодов169}Таблица 3.1. Циклический (7,4)-код с порождающим многочленом д(Х) = 1+ X + X2.Инф.Код.словослово00000000000va(X) = 0 • д(Х) = 010001101000m(X) = l.g(X) = 1 + Х + Х 301000110100v2(X) = X • д(Х) = X + X 2 + X411001011100V300100011010Vi1010 ' 1110010V5ОНО0101110щ(Х) = [X + X2] • д(Х) = X + X 3 + X 4 + X 511101000110vT(X) = \\ + X + X 2 ]-s(X) = l + X4 + X 500010001101од(Х) = X3 • д(Х) = X3 + X4 + X 610011100101v9(X) = [X + X3] • д(Х) = 1 + X + X 4 + X 601010111001vio(X) = [X + X 3 ] • д(Х) = X + X2 + X3 + X 611011010001«п(Х) = [1 + X + X3] • д(Х) = 1 + X 2 + X 6ООП0010111vi2(X) = [X + X ] • g(X) = X + X + X + X11111111011Многочлен(X) = [1 + X] • g(X) = 1 + X 2 + X 3 + X 4{X) = X 2 • д(Х) = X 2 + X 3 + X 5(X) = [1 + X2] -д(Х) = 1 + X + X 2 + X 523224563Шз(Х) = [1 + Х + Х ]- 9 (Х) =^1 + X + X 2 + X 3 + X4 + X 5 + Xе01110100011v14(X) = [X + X 2 + X3] • g(X) = X + Xs + X611111001011„ 15 (Х) = [1 + X + X 2 + X3] • д(Х) = 1 + X 3 + X 5 + X 6являющийся делителем X7 + 1.
Воспользуемся разложением7X323+ 1 = (1 + X) • (1 + X + X ) • (1 + х + X ).(3.23)Правильность (3.23) можно проверить вычислением правой части вGF(2).Выберем в качестве порождающего многочлена многочлен.д{Х) = 1 + X + X3.(3.24)Информационные и кодовые слова циклического (7,4)-кода, образованного с помощью д(Х) из (3.24), а также соответствующее им многочлены приведены в таблице 3.1.?170 Глава 3. Циклические коды3.3. Систематические циклические кодыПриведенные в таблице 3.1 кодовые слова образуют несистематический код. Однако, путем некоторой модификации алгоритма кодирования можно получить систематический циклический код с темиже параметрами.Регистр сдвигатттштто I- I о I оИнформационное словоР и с .
3.4. Сдвиг информационного многочлена в регистресдвига с обратными связями длины п на г = п — кпозиций.Для этой цели рассмотрим информационный многочлен степениfc-1и{Х) = щ + щХ + • • • + ик^Хк-1(3.25)и его г = п — fc-кратный сдвиг.ггг+1Х и(Х) = щХ + щХп 1+ ---+ик^1Х ' ..(3.26)Из рис. 3.4 видно, что такой сдвиг не вызывает переполненияn-разрядного регистра сдвига (поэтому и может быть записан в виде (3.26)) и соответствует заполнению А; правых крайних двоичныхразрядов регистра информационным словом. Заполним теперь свободные г левых двоичных разрядов таким образом, чтобы вектор,содержащийся в n-разрядном регистре, принадлежал коду. Для этогго представим многочлен Х и(Х) в видеХги(Х) = а(Х) • д(Х) + Ь(Х),ггде Ь(Х) - остаток от деления Х и(Х)Из (3.27) следует(3.27)на д{Х).Хги{Х) + Ь(Х) = а(Х) • д(Х).(3.28)Из (3.28) вытекает алгоритм кодирования систематического циклического (п,/г)-кода:1.
Информационный многочлен и(Х) степени к — 1 умножаетсяна Хг, где г = п — к;3.3. Систематические циклические коды, 1712. Находится остаток Ь(Х) от деления ХТи{Х) на д(Х);3. Многочлен Ь(Х) заносится в г левых разрядов регистра сдвига(рис. 3.4).Заметим, что эта операция всегда возможна, так как степень Ь(Х)по определению не превышает г—1.
Таким образом, в регистре сдвигабудет сформирован многочленv(X)= bo + biX+---br-1Xr-\+.(3.29)г проверочных символов+и0Хг+ щХг+1+ •••Uk-iX"'1.jt'информационных символовМногочлен v(X) принадлежит циклическому коду, так как в силу(3.28) он делится на д(Х) без остатка. Более того, этот код являетсясистематическим, так как из (3.29) следует, что старшие к разрядовкодовых векторов являются информационными векторами.Следующий пример наглядно поясняет алгоритм кодированияциклических систематических кодов.Пример: Циклический (7,4)-код в систематической форме.В качестве порождающего многочлена будем использовать уже3известный из предыдущего примера многочлен д(Х) = 1 + X + X(3.24). Пусть задан информационный вектори = (1001).(3.30)Ему соответствует информационный многочлен3«(X) = 1 + X .(3.31)Умножим информационный многочлен на X336Х и(Х) = Х + Х(3.32)и определим остаток Ь(Х) от деления (3.32) на д(Х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
