Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 142
Текст из файла (страница 142)
Эти матрицы используются в теории кодирования, в тео'-...' рии связи, а также в физике (в виде преобразований Адамара,: в задачах, связанных с определением веса, сопротивления, иа',„' пряжения и т. п. 9.86. Определение. Матрш»ейАдамара Н„называется (паси».;;, матрица, элементами которой являются +1 и — 1, удовлетворяКЬ,, щая соотношению Н„Нт = п1 Так как Н„' = (1 и) Нт, то справедливо также соотношенн Н„Н„= и»'. Таким образом, любые две различные строки, так ж как и любые два различных столбца матрицы Н„.
являются орта""„, гональными. 4 4. Приложения к комбинзторике Адамар показал, что определитель любой действительной (и хп)-матрицы М с элементами, по абсолютной величине ие превосходящими 1, удовлетворяет неравенству ~ де! М ! ( пв/2. В случае матрицы Адамара Н„мы имеем де! (Н„Н„) = — и", так Чта ~ дЕ! Н„~ = Ив!2, т. Е. уКаЗаННая ВЕрХНяя ГраНИца дОСтнжпма. Одновременная смена знаков у всех элементов любой строки нли любого столбца не меняет свойств, определяющих матрицу Адамара.
Назовем матрицу Адамара Н„нормализованной, если все элементы ее первой строки и первого столбца равны +! !1етрудно показать, что порядок и матрицы Адамара (азт) может лишь равняться 1, 2 или быть кратным 4. В самом деле, для всех п ~~~ 3 ~~ (ан + ан) (а„+ аз!) =- ~„'ап = п; 2 1=1 1=1 и при этом каждый член в первой сумме равен или О, или 4. Существует. гипотеза, что для любого допустимого значения п суц1ествует соответствующая матрица Адамара Н„. 9.87. Пример. Нормализованные матрицы Адамара низших порядков имеют вид 1 1 1 1 1 — 1 1 — 1 1 1 — 1 — 1 1 — 1 — 1 1 Н,=(!), Нз=(! 1), Н,= 1 1 Приведем теперь конструктивный метод получения матриц Адамара, использующий свойства конечных полей. 9.88.
Теорема. Пусть а„..., аз — элементы поля !г"е, в:— =- 3 (тод 4), и пусть 2! — квадратичный характер поля Кз. Тоеда матраца 1 1 1 Ьзз Ьзз Ь вЂ” 1 Ь 1 Ьз! Ьзз 1 Ь, Ь Ь, 1 Ь, Ь Ьзз Ьи=Ч(~~— Адамара порядка и + 1' Докаэаизельство. Так как все элементы матрицы Н равны ~1, достаточно показать, что скалярное произведение любых 14 Звв. 243 Гл. 9. Прнложепня конечных полей двух различных строк матрицы Н равняется О. Скалярное произ ведение 1-й и (! + 1)-й строк (1 ( ! ( 4) равно в силу (5.12 1л-( — !)+ Я ЬО:= ~~ ~т!(а — а;) =.
~' г)(с) = О. !+' /е~ с54'" е Скалярное произведение (! + 1)-и и (й т 1)-й строк (1 ( ! < я ( д) в свою очередь равно 1 — Ьн, — Ь, + ~ Ь;;5~!= /,л,е =1 — Ч(а~ — ал) — Ч(ая — а;) -' Е Ч(а! — а;)ц(а,— а,) =",. яеп е =1 — !1+т)( — 1)!т!(а; — ал)+ ~~ т!((с — а,)(с — а,)) =-О",' с5 г'ч в силу того, что т! ( — 1) =- — 1 для д == 3 (шод 4) (см. замечани' 5.13), итого, что последняя сумма равна — 1 (см. теорему 5.48). Если ̈́— матрица Адамара порядка л, то матрица является матрицей Адамара порядка 2п, Следовательно, эт методом можно получить матрицы Адамара порядка 2" (д + 1.". где й ) О и число д = 3 (гное) 4) является степенью просто, числа.
Беря же в качестве исходной матрицу Н, из прим ' 9.87, можно получить матрицы Адамара порядка 2", й ) О. $5. Линейные модуляриые системы Теория систем — это дисциплина, которая ставит своей ц выработку единого абстрактного подхода и единого аппарата изучения поведения систем различных типов. Она представля собой'совокупность методов, технических приемов и алгорит ', для решения задач, возникающих при анализе или синтезе с(1:",' стем, при их распознавании, оптимизации и т. п.
Основной нК" терес для специалистов по теории систем представляет математн) ческая структура данной системы, а не ее физическая реализа'.:, ция, область применения или то, какой является система — эле(г' трической, механической, экономической, биологической, хим!г"" ческой и т. д, Для специалиста по теории систем существенны является, линейна система или нет, является она системой с дне,, кретным временем или с непрерывным временем, детерминировам., ной или стохастической, с дискретным или непрерывным пРФ.; странством состояний и т, д. Во введении к настоящей главе мы привели неформальной; описание систем.
Приведем теперь строгое определение системы';. 4 о. Линейные модулерные системы 643 , конечным числом состояний, которая представляет собой идеа- лизированную модель для большого числа физических приборов и явлений. Идеи и методы, развиваемые для систем с конечным числом состояний, оказываются полезными при решении разно- образных задач, появляющихся при исследовании нервной дея- тельности человека, анализе синтаксиса естественного языка, конструировании вычислительных машин и т.
и. 8,89. Определение. Полная детерминированная система я' ~ конечным числом состояний определяется следующими злемен- тами: (1) Конечным непустым множеством У = (а,, а,...,. ссе), на- зываемым входным алфавитом системы ич'. Элемент множества У называется входным символом. (2) Конечным непустым множеством У = ф,, ~„..., р,), на- зываемым выходным алфавитом системы я'. Элемент множества У называется выходным символом. (3) Конечным иепустым множеством 5 = (а,, о.„..., о„), на- зываемым множеством (внутренних) состояний системы ля. Эле- мент множества 5 называется (внутренним) состоянием системы. (4) Функцией перехода у' (или функцией следующего состоя- ние), которая отображает множество всех упорядоченных пар (оь а;) в множество 5.
(5) Функцией выхода д, которая отображает множество всех упорядоченных пар (а,, а,) в множество !'. Систему М с конечным числом состояний можно рассматри- вать как некоторое устройство, вход, выход и внутреннее состоя- ние которого в момент времени ! обозначаются соответственно через и ((), у (!), в (г), причем эти величины определены лишь для целых значений параметра ! и принимают значения в множест- вах Г, )' и 5 соответственно.
Если заданы внутреннее состояние и вход системы я' в момент времени (, то внутреннее состояние системы в момент ! + ! и ее выход в момент ! определяются по следующим формулам: з (! + 1) = ) (в (!), и (!)), р (!) = а ( (!), (!)) Линейные модулярные системы образуют специальный класс систем с конечным числом состояний. Для иих входной и выходной алфавиты, а также множество внутренних состояний системы наделяются структурой векторного пространства над конечным полем Кч, а функции перехода и выхода являются линейными функциями. Линейные модулярные системы находят широкое применение при управлении сетями компьютеров, для получения кодов, исправляющих ошибки, в генераторах случайных чисел и т.
д. Гл. Э. Приложения конечных полей 644 9.90. Определение. Линейн я модулярная система (ЛМС) порядка п над полем Ге задается следующими элементами: (1) й-мерным векторнйм пространством над полем Кч, обозн' чаемым через У и называемым пространством входов линейиО системы и('.
Элементы этого пространства называются входалг'" и записываются в виде векторов-столбцов. (2) т-мерным векторным пространством над полем Кч, обозн " чаемым через г' и называемым пространством выходов лннейн системы оке. Элементы этого пространства называются выхода и записываются в виде векторов-столбцов. (3) л-мерным векторным пространством над полем Гч, обозн"' чаемым через 5 и называемым пространством (внутренник, состояний линейной системы,я'. Элементы этого пространст1( называются (внутренними) состояниями системы н записыва в виде векторов-столбцов. (4) Четырьмя характеристическими матрицами над полем й;1 '1 = (ац)лаан~ В = (0ц)чаю С = (сы)ткю 0 = (йы)тле Матрица А называется основной хар ктеристической митр ЛМС Д'.
(5) Правилом, связывающим внутреннее состояние ЛМС в мент времени 1 + 1 и ее выход в момент времени 1 с внутренн состоянием и входом ЛМС в момент времени з(1+ 1) = Аз(1)+ Вц(1), у(г) = Сз(г)+ 0ц(1). ЛМС над полем Кч может быть реализована с помощью пе ключательной схемы, построенной из сумматоров, усилителе ", элементов задержки (ср.
с 9 1 гл. 8). Нам будет удобно поль ваться сумматорами, которые складывают более чем по два мента поля. То есть сумматор имеет даа или более входов ие(~) и (1), "., ~,(1) 6 Г~ и единственный выход у, (г) = и, (() + и, (() + ... + и, ((). Усилитель, соответствующий константе а ~ Го, имеет еди, ственный вход и, (1) Е г, и единственный выход у, (1) = а их(туч Элемент задержки имеет единственный вход и, (1) Е "г'е и един' ственный выход у, (г) =- и, (1 — 1).
Схематически эти компонент изображены на рис. 9.5. 3 5. Линейные модулирные системы и,(Ц + у,(()=и,(Ц+иф)+" +и,4ц и„(г) Уснлнмль ЦЯ ц,(г) = аи,(г) э ~,мн1ем реле ц1(т) цЯ=~Ф И Рнс. 9.5. Опишем теперь, как можно получить схеиу переключательпой сети, моделирующей работу данной ЛМС (см. рис.
9,6). нл ф $с Рис. 9.6. (. Изобразить в виде прямых й входов системы, пометив нх символами и„..., ие, т выходов системы, пометив их символами у„,;., у, и и элементов задержки. Выходом (-го элемента задержки является з, = з, ((), а его входом является з'; = з~ (( + (). 2. Поместить сумматоры перед каждым выходом системы у, и перед каждым элементом задержки. Гл. 9. Приложения конечных полей 646 3. Входами сумматора, помещенного перед ~'-и элементом за держки, являются сигналы зь проходящие через усилители с кон', стантами аы, ! < ~', 1 ~ п, н сигналы и,, пРоходащие чеРез Ус '' лители с констаитамп Ь;,, 1 ~ь / ', lг.
4. Входами сумматора, соответствующего выходу системы у „ ! ( ~' ( т, являются сигналы з,, проходящие через усилите с константами с,, ! .-. 1 .; п, и сигналы и,, проходящие чер усилители с константами 41;;, 1 .. у <. а. Если положить и, Уе зе 3! н(1) =, у(1) = з(1)-= > а(! т !) == ил Уж ан зн .'е то переключательная схема, изображенная на рис. 9.6, функц нирует по законам, приведенным в определении 9.90(5). 9.91. Пример. Пусть характеристические матрицы ЛМС ч вертого порядка иад полем Гн имеют вид 0 2 0 0 '1' 1 0 2 1 0 О ! ! О )9= О 2 0 1 1 0 3 с--( ), а=() Тогда схема, реализующая данную ЛМС, изображена иа рис.
9.7. и, н~ хх не Фе Рис. 9.7. 1 о. Линейные модулнрные системы б47 Верно и обратное: любую переключательную схему, построен ную из конечного числа сумматоров, усилителей и элементов за держки над полем !гч, можно следующим образом представит~ как ЛМС над полем Ге (при условии, что каждый замкнутый кон тур содержит по крайней мере один элемент задержки): 1. Выделить в данной переключательной схеме все элементы задержки, все входы и выходы системы и пометить их так, каг, зто было сделано на рис. 9.6.
2. Проследить все пути от з, к з';; найти произведение констант соответствующих всем усилителям, расположенным вдоль каждого такого пути, и сложить все полученные произведения. По лученную сумму обозначить через аин 3. Пусть через Ь„. обозначены аналогичные суммы, соответствующие путям от йз к зз через с„. — суммы, соответствующие путям от ез к уы а через 4~ — суммы, соответствующие путям от и; к уо Тогда данная переключательная схема является реализа. пней ЛМС над полем !Ге с матрицами А = (аи), В = (60), С =- (с„.) и с) = (с(ы), элементы которых определены выше. Состояния и выходы ЛМС зависят от начального состояния з (0) и последовательности входов и (1), 1 = О, 1, .... Эту зависимость можно выразить явным образом. 9.92.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
