Научная литература
booksshare.net -> Добавить материал -> Математика -> Аршинов М.Н. -> "Коды и математика (рассказы о кодировании) " -> 26

Коды и математика (рассказы о кодировании) - Аршинов М.Н.

Аршинов М.Н., Садовский Л.Е. Коды и математика (рассказы о кодировании) — М.: Наука, 1983. — 144 c.
Скачать (прямая ссылка): kodiimatematika1983.pdf
Предыдущая << 1 .. 20 21 22 23 24 25 < 26 > 27 28 29 30 31 32 .. 50 >> Следующая


Не вполне ясно пока, какова польза полученного нами описания циклического кода. Следующее утверждение проливает свет на этот вопрос.

Во всяком идеале V кольца Fn существует фиксированный многочлен g(x), которому кратен всякий многочлен идеала V.

Иными словами, любой многочлен а(х) б V можно представить в виде произведения фиксированного многочлена

,U g(x) є V и некоторого подходящего многочлена s(x) Є Fn:

a(x)=g(x)s(x). (6)

Для доказательства рассмотрим ненулевой многочлен g-(x) наименьшей степени, принадлежащий идеалу. Если а(х) произвольный многочлен из V, то разделим его на g-(x) с остатком;

a(*)=g(*)s(*)+r(*). (7)

Это можно сделать по обычным правилам деления многочлена на многочлен; степень остатка г(х) будет меньше степени делителя g(x). Первое слагаемое в правой части (7) принадлежит V (в силу определения идеала). Поскольку и многочлен а(х) принадлежит V, то остаток г(х), равный разности

a(x)—g(x)s(x)

двух элементов из V, также должен принадлежать идеалу. Если предположить, что г(х) — ненулевой многочлен, то приходим к противоречию: многочлен г(х), принадлежащий идеалу, имеет степень, меньшую степени g(x). Следовательно, г(х) =0 и выполняется равенство (6).

Многочлен g(x) называется порождающим многочленом идеала V (или соответствующего циклического кода).

Таким образом, если известен порождающий многочлен кода, то тем самым известны и все кодовые многочлены — их список исчерпывается всевозможными произведениями g-(x)s(Af), где s(x) — произвольный многочлен степени, меньшей п.

Вспомним, что для задания произвольного кода нужно указать полный список кодовых слов, а для задания линейного кода — список базисных кодовых векторов. Для циклического же кода, как мы выяснили, достаточно указать всего лишь один кодовый многочлен, а именно — порождающий многочлен g(x).

По порождающему многочлену легко найти порождающую матрицу циклического кода. Пусть

g W = go +Si* + ... + gmx">

— многочлен степени т и k=n—т. Рассмотрим следующие многочлены:

g(x), Xg(X), x*g (X).....X^1g(X). (8)

Все они являются кодовыми, степень их очевидно не превосходит п—1. Нетрудно убедиться, что рассматриваемые

,72 как векторы, они образуют линейно независимую систему, и всякий кодовый вектор является их линейной комбинацией, Следовательно, матрица G, составленная из векторов (8), является порождающей матрицей циклического кода. Порядок ее равен kXn и она имеет следующий вид:

/go gi ...gm 0 ... О \ / g(x)\

G=L0 & ••• ••• 0 =( *в(х) Ь9)

Vo ... о ft ft .., gm J \ xk~lg(x)J

В качестве примера рассмотрим двоичный циклический код длины 7 с порождающим многочленом ^) = 1+^+^3= ==(1011000). Так как

xg(x) = х+х3+X4 = (0101100),

Х2?(Л-)=Л;2+Л;4+Л;5=(00101 10), д;)=л;3+д;5+л:6=(0001011),

то порождающей будет следующая матрица:

/10 1 1 о о 0\ с_(010110 0] І0010110Г \0 0 О 1 0 1 1/

Нетрудно убедиться, что данный циклический код эквивалентен коду Хемминга с проверочной матрицей

/0 0 о 1 1 1 1\ (01 1001 і ). Vi о і о і о і/

Вообще, можно показать, что для всякого кода Хемминга имеется эквивалентный ему циклический код.

Очень важно, что среди циклических кодов имеются такие, которые исправляют любое заданное количество ошибок. Именно, справедлива следующая теорема:

f 2т__1\

Для любых -значений т и —^— j существует дво-

ичный циклический код длины 2т—1, исправляющий все комбинации из t или меньшего числа ошибок и содержащий не более, чем mt проверочных символов.

Доказательство этой теоремы мы здесь не приводим. Скажем лишь, что построение указанных кодов основано на использовании упоминаемых в приложении полей Га-, луа GF(q) (см, также дополнение 8 к этому параграфу).

,73 Задачи и дополнения

1. В теории циклических кодов многочлены удобно трактовать не только как элементы кольца Fn, но н как элементы кольца многочленов F [X] с обычной операцией умножения многочленов. Условимся в последнем случае вместо обозначения а (х) пользоваться обозначением а(Х). Необходимость различать эти обозначения видна хотя бы из такого примера: если в кольце Fn имеет место хп—1=0, то в кольце FtX] многочлен Xn—1, разумеется, не является нулевым элементом.

Для циклических кодов существенно следующее свойство порождающего многочлена g(x):

Если в качестве g(x) выбран многочлен наименьшей степени, принадлежащий идеалу V, то многочлен g(X)?f[X] является делителем многочлена Xn—1.

Для доказательства разделим Xn—1 на g(X) с остатком. Получаем:

X"-l=h(X)g(X) + r (X), (10)

где степень г (X) меньше степени g (X). В кольце Fn равенство (10) приобретает вид:

h(x)g(x)+r(x)=0,

откуда заключаем, что г(х) должен принадлежать идеалу V1 в то время как его степень меньше, чем степень g(x). Следовательно, г(х)=0, но тогда и г (X)=O, т. е.

X"-I=Z1(X)g(X). (11)

Многочлен h{X), удовлетворяющий равенству (II), называется проверочным многочленом.

2. Воспользуемся определением проверочного многочлена для построения проверочной матрицы циклического кода. k

Пусть h(x) = ^hjX1—проверочный многочлен кода. Из (Il) сле-/=о
Предыдущая << 1 .. 20 21 22 23 24 25 < 26 > 27 28 29 30 31 32 .. 50 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed