Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
т. е. М = Р~1М*Р, где Р - некоторая невырожденная матрица над полем Fr
Матрица М* называется рациональной канонической формой матрицы Л, а
подматрицы М (gi (х)) называются элементарными блоками матрицы М*.
Пусть невырожденная матрица А является основной характеристической
матрицей ЛМС над полем f9. Для того чтобы найти ее цикловую сумму,
матрицу А можно заменить подобной матрицей. Таким образом, вместо А можно
рассматривать рациональную каноническую форму А* матрицы А. Применяя
теорему 9.95, по индукции получаем следующее. Пусть ft (х), ..., gw (х) -
нормированные элементарные делители матрицы А, и пусть Xf - цикловая
сумма сопровождающей матрицы М (gi (х)). Тогда цикловая сумма X матрицы
А*, а следовательно, и матрицы А определяется формулой
V . . V V у
Пусть характеристический многочлен f (х) матрицы А представлен в виде
652
Гл. 9. Приложения конечных полей
а • щ.
•Л:|
¦щ
:.у.
Ж
где pj (х) - различные нормированные неприводимые многочлену! над полем
fq, Тогда элементарные делители матрицы А имеюй!
ВИД
eJh
г.
• V'<sl
•:vS .•л *.
pj(x)etl* Pj{x)€}*i pj{x) f, /= 1, 2,
ft
где
fti ^ ej2 ' Tt ft*у P> 0, fti ~r ft'2 "h ¦ * * H ftfty
Минимальный многочлен матрицы А равняется
7*
ш
Wv-Й
v*?
ж
m (x)
П р,(Ч'Л-
ft-i
Остается определить цнкловые суммы элементарных м (ft М) матрицы Л*, где
ft (х) == р (х)е, а р (х) - некоторьЦ
...'О . №
нормированный неприводимый делитель многочлена / (х). дующий результат
позволяет решить поставленную задачу.
9.96. Теорема. Пусть р (х) - нормированный неприводим^ многочлен над
полем lFg, deg (р (х)) - d, и пусть th = ord (р
si
Тогда цикловая сумма матрицы М (р (х)г) определяется форму
jft j
А> J4
№
(й 1)
1
t
2d
if.
t
.ed
¦(*-1 )<t
I * I
i.
, t,
ji?i :Г;Щ
•j у
:4
Ч: J it!
В итоге мы получили следующий алгоритм для определен цикловой суммы ЛМС Ж
над полем с невырожденной оеновй характеристической матрицей А:
С1. Найти элементарные делители матрицы Л; пусть это Cf дут многочлены ft
(х), .,,, ft, (х).
С2, Пусть ft (х) = ^ (xf\ где ft (х) - нормированный уй: приводимый
многочлен над полем f5. Найти порядки
= ord (ft (х))-
СЗ. Для t = 1, 2, w и h - 1, 2, mi иайти поря,|
Й° - Ч°Р
где р - характеристика поля (Fg, a ch - наименьшее целое
такое, что pVfl > h (см. теорему 3,8).
С4. Пользуясь теоремой 9.96, найти цикловые суммы для матриц М (gi (х)),
i - I, 2, ,,,, w.
С5, Тогда цикловая сумма X системы Ж задается
X -¦¦¦¦¦- ХгХ2 ... Х№.
9.97. Пример. Пусть основная трица ЛМС Ж над полем (Г2 нмеет вид
й
•й аЧ
т
r.#i ijt/Г
т
№
¦Й^Г:
4° - ord (ft (х)й), воспользовавшись формулой
характеристическая
А -
(0 1 о
о
1°
о
о
3
о
о
1
1
1
о
о
о
о
о
0
1
01 о
0
1 1
• "•
¦•Sj
о
МТ
Комментарии
653
В этом случае
gx (Л) = Ж3 I ж2 -4 ж f 1 (х {- I)3, /i (а) х \ С
Ш\ - 3,
g, (,v) - Л'2 {- л- i 1, /2 (ж) х2 4 х 4 1 * т2 -- 1.
Выполнив шаги С2 и СЗ, получаем - I, - 2, ty = 4, /у* 3. Тогда по
теореме 9.96
2i - (I, 1) 4~ (I, 1) + (1, 2) + (U 4) -
= (2, 1) 4 (1, 2) j (1, 4),
23 ~ (L 1) 4~ (/ 3)
и. следовательно,
S - = [(2, 1) + (I, 2) 4 (I, 4)] [(1, 1) + (1, 3)3 -
- (2, 1) + (1,2)+ (2, 3) + (1,4)4- (1/6)+ (1. 12).
Таким образом, граф состояний ЛМС Ж содержит два цикла длины 1, один цикл
длины 2, два цикла длины 3 и по одному-циклу длин 4, 6 и 12. ?
Из шага С5 можно получить, что порядки состояний ЛМС Ж задаются формулой
для всех возможных комбинаций целочисленных значений параметров кц hWt О
ht ^ тг. Если мы хотим найти все возможные значения порядков состояний
системы^, не вычисляя предварительно ее цикловую сумму, то можно
воспользоваться следующей теоремой.
9.98. Теорема. Пусть Ж - ЛМС с невырожденной основной характеристической
матрицей Л. Пусть минимальный многочлен матрицы Л имеет каноническое
разложение
т(х) = PlM*1 - Pr(xfr,
и пусть thf) = ord (pj (я)Л). Тогда значения порядков состояний системы Ж
- это все целые числа вида
Комментарии
§ 1. Теорема Шениона, о которой говорится во введении к настоящей главе,
была получена в работе Shannon [1| (см. также Shannon, Weaver ИЗ). Эта
работа знаменует начало теории информации как математической дисциплины.
Доказательства этой теоремы Шеннона, а также обоснования теории
информации
654
Гл. 9. Приложения конечных полей
ftf<G
":г
,:3
Ш
1"
s,4m
"
можно найти в книгах Abramson [2], Ash II], Guia^u [i] (в по"
следней приводится подробная библиография по теории инфор мацни), а также
в монографиях МсЕНесе [6! и Wolfowitz П L| Теория кодирования с точки
зрения информации изучается в ра* ботах Balakrishnan [ I ], Gallager [I],
Ingels Ii], Lucky, Salz Weldon [ 1 ], McEiiece [61, Slepian [4],
Первый нетривиальный пример кода, исправляющего ошибки-иад конечным полем
появляется в фундаментальной работе Шен-j нона (Shannon [1]). Этот код
называется теперь (7, 4)-Хэмминга, и его построение приписывается
Хэммингу (см. Нат4 ming 11]), Ранее в работе Friedman, Mendelsohn [I]
изучались коды длины 5 с минимальным расстоянием не меньше чем 2
