Содержание к диссертации
Введение
ГЛАВА 1. Вычислительные модели преобразований над полем GF(2n) 24
1.1. Определения теории полей Галуа 24
1.2 Связь между векторным и матричным представлением элементов поля GF(2n). 28
1.3 Структурная модель, реализующая операцию умножения элементов поля GF(2n). 31
1.4 Представление функций в GF(2n) многочленами от нескольких переменных. 37
1.4.1 Реализация многочленом от одной переменной. 37
1.4.2. Реализация функции от s переменных в GF(2")
многочленом от s переменных. 39
1.5. Структурные реализации полиномиальной функции и оценки их сложности. 43
1.5.1. Параллельная структура. 43
1.5.2. Систолическая векторная структура полинома f(x, q). 45
1.5.3. Систолическая структура полинома f(x,q). 47
1.5.4. Итеративная структура многочлена L{u). 48
ГЛАВА 2. Модели схем умножения в расширениях поля GF(2n) 50
2.1. Применение алгоритма Карацубы-Офмана для построения схемы умножения в составных полях вида GF((2k )4) 52
2.2. Модификация алгоритма Карацубы-Офмана для построения схемы умножения в составных полях вида GF((2k )4) 54
2.3. Алгоритм построения составного поля вида GF((2k)2), изоморфного полю вида GF{2 ) 58
2.4. Построение схемы умножения в составном поле вида GF((22)2). 64
2.5. Построение схемы умножения в составном поле вида GF(((22)2)2). 68
ГЛАВА 3. Полиномиальные модели детерминированных автоматных преобразований над полем GF(2n) 78
3.1. Моделирование конечного автомата однородной сетью элементарных автоматов в поле GF(2n). 78
3.2. Моделирование в классе комбинационных схем. 80
3.2.1. Полиномиальная модель на основе многочлена от одной переменной над полем GF(2n). 80
3.2.2. Полиномиальная модель на основе многочлена от двух переменных над полем GF(2n). 83
3.3. Полиномиальная модель автомата с памятью. 86
3.4. Синтез типовых элементов однородной вычислительной структуры. 89
3.4.1. Типовой элемент последовательной структуры. 89
3.4.2. Типовой элемент параллельной структуры. 91
3.4.3. Методика синтеза однородных автоматных схем. 94
3.5. Минимизация структуры полиномиальной модели 96
ГЛАВА 4. Полиномиальные модели вероятностных автоматов и функций конечных цепей Маркова над полем GF(2n) 106
4.1. Определения базовых вероятностных автоматных моделей. 107
4.2. Синтез автоматной марковской модели над полем GF{2"). 110
4.3. Синтез генераторов марковских функций над полем GF(2n). 116
4.3.1. Полиномиальная модель генератора процесса {Y,} над полем GF(2n). 117
4.3.2. Полиномиальная модель генератора процесса {ZJ над полем GF(2"). 119
4.4. Полиномиальная модель марковской функции вида а-связной цепи Маркова. 123
4.5 Синтез конечноавтоматных случайных последовательностей надполем GF(2"). ' 126
4.5.1. Определение вероятностной автоматной модели и постановка задачи 127
4.5.2. Полиномиальное представление конечноавтоматной модели надполем GF(2n). 130
4.6. Синтез генератора дискретной случайной величины. надполем GF(2n). 133
4.7 Автоматное моделирование случайных процессов с последействием
на основе эйлеровых стохастических матриц. 137
4.7.1 Автоматная модель. 141
4.7.2 Структурная схема автоматной модели. 147
4.8 Реализация «^-последовательности в полях GF(2n). 148
4.9 Полиномиальные модели вероятностных автоматов общего вида надполем GF(2"). 158
ГЛАВА 5. Реализация и тестирование полиномиальных моделей средствами программного комплекса и САПР ПЛИС/FPGA 166
5.1. Программируемые логические интегральные схемы 166
5.2. Представление и анализ структурных моделей операции умножения в поле GF(2n) 171
5.2.1. Определение базовых математических моделей умножителя . 172
5.2.2. Структурные модели умножителей и их оценки сложности. 173
5.3. Оценки сложности структур умножителей над полем GF(2n) .
в базисе программируемых матрицах логических элементов. 179
5.3.1. Оценки сложности моделей в базисе ПЛИС. 179
5.3.2. Сравнение теоретических оценок с оценками реальных аппаратных затрат для схем умножения. 181
5.4. Пакет программ, реализующий автоматные модели генераторов марковских функций. 187
5.5. Пакет программ, реализующий полиномиальные модели генераторов марковских функций над полем GF(2n). 192
Заключение. 196
Литература.
- Структурная модель, реализующая операцию умножения элементов поля GF(2n).
- Полиномиальная модель на основе многочлена от двух переменных над полем GF(2n).
- Синтез автоматной марковской модели над полем GF{2").
- Определение базовых математических моделей умножителя
Введение к работе
Вероятностный автомат (ВА) является моделью реальных преобразователей информации, функционирующих в условиях действия случайных факторов. Понятие ВА возникло как обобщение конечного детерминированного автомата путем отказа от однозначного соответствия между входом и выходом: функционирование В А описывается вероятностным законом [1-3].
Вероятностные автоматы имеют глубокую взаимосвязь с цепями Маркова (ЦМ) [3]. Частный случай В А - автономный вероятностный автомат (ABA) без выхода является автоматной моделью генератора однородной цепи Маркова. Процессы, порождаемые ABA с выходом рассматриваются как функции конечных однородных цепей Маркова (марковские функции (МФ))[1-3]. Последовательность состояний В А общего вида является неоднородной цепью Маркова [1].В свою очередь, матричная теория цепей Маркова является аналитическим аппаратом решения задач синтеза и анализа вероятностных автоматов [1-3].
Марковские последовательности и их функции широко используются для построения вероятностных моделей в таких областях как статистическое моделирование [4-7], распознавание автоматов [11, 25-26], передача и защита информации [23], диагностика и анализ цифровых устройств [27-28] и др. Применение моделей цепей Маркова (ЦМ) в качестве базовых при построении вероятностных моделей автоматного типа, обуславливает интерес ученых к теории моделирования марковских последовательностей, функций конечных ЦМ и построению автоматных моделей генераторов ЦМ.
Использование моделей ЦМ дает возможность получить простое и адекватное описание широкого класса систем. Важностью прикладного значения объясняется большое число публикаций по теории моделирования марковских последовательностей и их функций и построению моделей генераторов ЦМ [1-3, 27-29, 31-46]. Известен ряд работ по моделированию марковских последовательностей, основанных на автоматном представлении процессов этого класса [1-7, 27-29, 33-42]. При автоматном моделировании ЦМ конечная однородная цепь Маркова обычно представляется в виде конечного детерминированного автомата со случайным входом [38-39]. В работах [1-4, 7, 27, 32, 34, 36, 46] решены вопросы перехода от описания ЦМ в виде стохастической матрицы к описанию в виде стохастической линейной комбинации булевых стохастических матриц, определены условия автоматного преобразования случайных дискретных величин, предложены принципы построения управляемых генераторов случайных кодов, показано, что МФ можно рассматривать как процессы, порождаемые вероятностными автоматами [2-3,ОД}шм из перспективных подходов построения автоматных моделей ЦМ, предложенных в последние годы, представляется подход, использующий теорию конечных полей. Этот подход позволяет синтезировать структурные модели генераторов конечных ЦМ, состоящие из однородных блоков, с векторной обработкой данных. Для реализации полученных моделей могут быть использованы технологии производства интегральных схем, например программируемые логические интегральные- схемы (ПЛИС). Использование ПЛИС дает возможность синтезировать устройства с перестраиваемой структурой, что позволяет оперативно менять функциональные возможности вероятностных моделей и приводит к сокращению аппаратных затрат, а следовательно и стоимости разрабатываемого устройства.
В работах [4-7] показана перспективность нового подхода моделирования цепей Маркова и их функций, основанного на полиномиальной алгебре в конечном поле типа GF(2n). Достоинством вычислений в поле GF(2n) является то, что они обладают функциональной полнотой и допускают параллельную реализацию. Аппарат конечных полей позволяет строить автоматные схемы в виде однородной сети элементарных автоматов, выполняющих операции сложения и умножения в поле GF(2n) [8]. Эти и другие особенности конечного поля определили широкое использование аппарата теории конечных полей в области обработки процессов информации: в теории кодирования [8-24]; в цифровой обработке сигналов [25]; в анализе динамических стохастических систем [25-26], в задачах синтеза генераторов псевдослучайных последовательностей [28-29] и др.
Многие современные практические задачи предъявляют высокие требования к скорости генерирования формируемых последовательностей. Увеличение быстродействия может быть достигнуто с помощью распараллеливания проводимых вычислений [48-49].
Идея синтеза дискретных вероятностных моделей автоматного типа в однородных вычислительных средах получила развитие в работах [3, 32, 50-51], а использования арифметики конечных полей [9] для синтеза детерминированных цифровых устройств в однородных структурах в [44, 52-60]. Известны также решения задачи построения генераторов равномерно
распределенных случайных и псевдослучайных чисел в поле GF(2") [11, 28,31,61-65].
Большое число публикаций посвящено решению задачи разработки
архитектуры схемы умножения элементов поля GF(2n) для реализации в
однородных вычислительных средах [67], а также решению задачи уменьшения вычислительной сложности схем умножения [55, 68-77], так как вычислительная сложность, при использовании технологии производства интегральных схем, может служить оценкой необходимой площади кристалла [77]. Использование идеи расширения модели играет важную роль в теории построения вычислительных структур. Применение расширений моделей и переход к более удобному базису возможно для умножения матриц [30, 66], что позволяет уменьшить вычислительную сложность операции умножения в полях Галуа (матричное представление элементов поля). Известно решение задачи построения автоматных моделей генераторов ЦМ в базисе полиномиальных функций над полем Галуа [58-59]: предложены полиномиальная модель и структурная схема генератора простых
однородных ЦМ над GF(2"); предложены альтернативные (по критериям сложности и быстродействия) структурные схемы - параллельного, систолического векторного, систолического и последовательностного типов -для реализации генераторов ЦМ в базисе полиномиальных функций; показана адекватность структуры модели генератора ЦМ над полем Галуа, состоящей из однородных блоков, структуре ПЛИС класса FPGA (Field Programmable Gate Array) [80-82]; показано, что аппарат полей GF{2n) является эффективным инструментом для синтеза генераторов ЦМ в виде однородных структур.
Вероятностный автомат является обобщением конечного детерминированного автомата (КДА). В связи с этим возникает необходимость глубокого исследования вопросов представления КДА полиномами над полем GF(2n). По этому направлению важное практическое значение представляет задача отображения полиномиальных моделей КДА в однородные вычислительные среды.
В этой связи представляется актуальным выполнение настоящего исследования, основанного на новом подходе моделирования широкого класса дискретных случайных процессов с дискретным временем в поле GF(2n). Развиваемые методы включают предложенные понятия полиномиальных моделей в поле GF(2n) дискретной случайной величины (ДСВ), простых и сложных цепей Маркова и марковских функций и доказательство соответствующих теорем, устанавливающих взаимосвязь стохастических матриц и полиномиальных функций над GF(T) и обосновывающих алгоритмы моделирования рассматриваемых процессов.
Целью диссертационной работы является создание теоретических основ, алгоритмов и методик представления детерминированных и вероятностных автоматных моделей полиномиальными функциями над полем GF(2n).
Структурная модель, реализующая операцию умножения элементов поля GF(2n).
В зависимости от представления элементов конечного поля используются различные структурные модели для реализации операций сложения и умножения этих элементов. Пусть а(ф= а0 + а і +... +яя./ f ; и /1(ф= b0 + bi +...+bn.i С 1 tfi. Ь{ &GF (2), і = 0 п-I, где примитивный .элемент поля GF(2n). После непосредственного перемножения компонент элементов a(Q, f}(ty и группирования произведения можно получить рекуррент ные формулы для вычисления компонент произведения. Полученные выражения предлагается вычислить при помощь систолических схем и п-мерных решеток двоичных умножителей. Время выполнения перемножения двух элементов поля GF(2n) при этом не больше 2[log2nJ+I. За единицу времени взято время сложения двух бит. Дальнейшее развитие схем умножителей в поле GF(2n) связано с векторным представлением элементов. Сложение представленных таким образом элементов не представляет трудности и может быть реализовано схемой из п-1 сумматора по модулю два. Трудности возникают при реализации операции умножения.
Теорема 1.3. [84] Пусть элементы поля GF(2n) представлены в виде векторов, соответствующих многочленам по модулю примитивного многочлена т(х) над GF(2) степени п. Тогда для любых a,Be GF(2") wfi=aolf+a,AfiT+ ... +an.,An f, где a = (a0, а і, ., an,), В = (b0, b,, ..., bn.,) - элементы поля GF(2n), A - сопровождающая матрица многочлена m(x).
Доказательство. Пусть а=(а0, а,, ..., а„.,), B=(bn, b,, ..., Ьп.,) - элементы поля GF(2n), структура которого задана примитивным многочленом т(х). Из Теоремы 1.2 следует, что векторам а и В соответствуют матрицы В, и В2 из матричного представления, первыми столбцами которых являются векторы а и $ соответственно. Для того, чтобы найти а В достаточно перемножить матрицы В, и 2?2 и выделить первый столбец из произведения. Первый столбец произведения матриц равен произведению первой матрицы на первый столбец второй матрицы. Таким образом, чтобы вычислить а-В достаточно вычис-лить В, ft . Покажем теперь, как найти матрицу В,. Согласно Теореме 1.2 вектора (1,0,...,0)т, (0,1,...,0)т , (0,0,..., 1)т являются первыми столбцами матриц /, А,..., А" соответственно, где А - сопровождающая матрица примитивного многочлена т(х). Поэтому первый столбец матрицы АП-1 C=anI+a,A+ ...+ап ,А"" (1.1) равен (a0,ai,...,an.i)T. Это значит, что найденная по формуле (1.1) матрица С совпадает с В;. Таким образом произведение дроизвольных элементов а=(а0, alt ..., ап,), P=(bo, bi, ..., bn.j) можно вычислить по формуле Вфт=а0ірТ+а1А/]т+ ... +an.iA"- f. и Пример 1.5. Пусть G=GF(23). Выберем примитивный многочлен ш(х) у = 7+JC+X . Его сопровождающая матрица: ГО О П А = 1 0 1 О 1 О
При указанном изоморфизме матрице А отвечает элемент поля G (0,1,0), или многочлен . Непосредственным подсчетом найдем, например 1 О О 1 1 О А3 = ,А5 = г\ О Л Пі 1 1 1 1 О 1 1
Этим матрицам отвечают элементы (1,1,0) и (1,1,1). Найдем произведение им соответствующих многочленов: (1+х)(1+х+х2)=1+х3. Остаток от деления на т(х)=1+х+х3 равен х. Это означает, что (1,1,0)-(1,1,1)=(0,1,0). С другой стороны, А -А =А =А. Как было отмечено, матрице А соответствует (0,1,0), то есть тот же самый элемент.
Следствие Теоремы 1 3. [55]
Операция умножения двух произвольных элементов поля GF(2n) может быть реализована схемой, приведенной на рис. 1.1. Где блоки К„ і=0,...,п-1 являются линейными комбинационными схемами, реализующими умножение входного вектора ft на матрицы 1,А,...А" соответственно. Ключевые схемы И„ i=0,...п-1 управляются соответствующими разрядами вектора а. Сумматор Е осуществляет поразрядное суммирование по модулю два векторов, поступающих с выходов ключевых схем И„ і=0,...п-1. Для реализации схемы требуется не более п (п-1) сумматоров по модулю два, п элементов Я, а время умножения двух произвольных элементов поля GF(2n) не больше 2[log2 п]+1.
Доказательство.
Для реализации блоков К„ і=0,...,п-1 требуется не более п(п-1)2 двоичных сумматоров. Время умножения вектора/? любым из К„ і=0,:..,п-1 не больше [login]. Все ключевые схемы И„ i=0, ...,п-1 могут быть реализованы при помощи п2 двоичных умножителей Я. Элемент I можно реализовать при помощи не более n(n-J) сумматоров по модулю два. Время сложения -не больше [log2n]. Окончательно, для реализации схемы на рис. 1.1 требу-ется не более п (п-1) сумматоров по модулю два, п элементов Я, а время умножения двух произвольных элементов поля GF(2n) не больше 2[log2n]+l.
Полиномиальная модель на основе многочлена от двух переменных над полем GF(2n).
В п. 3.2 рассматривалась возможность представления конечного автомата без памяти в виде последовательной вычислительной структуры (рис. 3.2). Такая структура состоит из одинаковых блоков П(1) (рис. 3.6). Этот блок (процессорный элемент) выполняет следующие операции: (3.8) 2) = - + где все операции выполняются над полем GF(2n). Операция 1) - значение переменной х на входе блока к: (х(к)) передается на его выход без изменений (х(Ь1 ). Операция 2) - производится вычисление значения начального, промежуточных и конечного результатов для вычисления полинома вида (3.3).
Величине А(0 присваивается значение коэффициента а „ . Величина а к) равна значениям коэффициентов полиномиальной функции r-k-h к = 0,(г-1), г=2п-1. Значение полиномиальной функции есть А(к+1) при к=г-1-2п-2. Функциональная схема процессорного элемента представлена на рис. 3.7. Блок П(1), показанный на рис. 3.7, содержит «-разрядный регистр Pri с «-разрядным входом 1 и «-разрядными выходами 2, 3, «- разрядный регистр сдвига Рг2 с «-разрядным входом и «-разрядным выходом, блок СУ, выполняющий операцию умножения двух произвольных элементов поля GF(2n) (схема умножения), сумматор по модулю два М2, выполняющий поразрядное сложение по модулю два двух двоичных векторов длины п и выдающий «-разрядный результат. При этом с помощью регистра Prj обеспечивается прохождение значения переменной х по вычислительной структуре, то есть реализуется операция x(k+1)=x(kJ в (3.8). Регистр Рг2 используется для того, чтобы обеспечить синхронность подачи второго сомножителя на вход блока СУ. Если сопоставить входы- выходы блока П на рис. 3.6 и на рис. 3.7, то х подается на вход 1 регистра Ргь х(к+,) получаем с выхода 2 регистра Рг1э А(к) подаем на вход 5 регистра Рг2, А(кг1) получаем на выходе 11 сумматора по модулю два М2, на вход 10 подаем значение, соответствующее значению коэффициента а(к), Сх - линия синхронизации. Для реализации операции умножения двух произвольных элементов поля GF(2n) используем схему, показанную на рис. 1.1.
Процессорный элемент П(1) функционирует следующим образом. Начальное состояние Рг2 - нулевое. В первый регистр - г\, заносится значение переменной х к). По сигналу синхронизации содержимое регистров поступает на входы блока СУ, где происходит умножение, а (к) затем результат складывается со значением а в сумматоре по модулю два M2. В этот момент поступает следующий сигнал синхронизации и происходит запись в регистры очередных значений. В п. 3.1 рассматривалась возможность представления конечного автомата без выходов в виде параллельной вычислительной структуры (рис. 3.1 и 3.3). Основу такой схемы составляют процессорные элементы П(2), вычисляющие выражение а-х -у1, а,х,уе GF(2n), і, j = 0, г, г=2п-1.
Для вычисления выражения а-х -у1 построим автомат AQ=(X,Q,3) над GF(2"), где Х- входной алфавит, Q- множество состояний, 3- функция перехода в новое состояние, причем 8(x,q)=x-q, хеХ, qeQ. Тогда функционирование автомата Ад можно описать системой: (3.9) q{t + \) = x{t)q{t).
Для реализации операции умножения в (3.9) используем схему, показанную на рис. 1.1. Вычисление выражения а-х -у1, i,j = 0,r, г=2п-1 при использовании автомата Ад, заданного системой (3.9), можно определить следующим образом - настроить автомат Ад на вычисление выражения а-х.
Для этого необходимо зафиксировать на выходе автомата сигнал, соответствующий переменной х, а начальное состояние автомата должно соответствовать элементу а. Таким образом, систему (3.9) можно переписать в виде q{\) = a q(t + \) = x{t)q{t), t = 1,2,...,/. При t=i внутреннее состояние автомата AQ станет q(i+l)- а-х .
После выполнения первого этапа вычислений производится перенастройка автомата Ад на довычисление выражения а-х -у1. Для этого на входе автомата зафиксируем сигнал, соответствующий переменной у, а внутреннее состояние оставим прежним. При этом систему (3.9) можно представить в виде: q(i +1) = q(i) q(t + 1) = x(t)q(t), t = i + \,..., і + j. При t=i+j внутреннее состояние автомата AQ станет равным q(i+j+l)= а-х -у1, і, j = 0,г, г-2"-1.
Реализуем автомат Ад (элемент П(2)) схемой, показанной на рис. 3.8. Она отличается от схемы, реализующей операцию умножения элементов поля GF(2n) (описана в п. 1.3 и приведена на рис. 1.1) тем, что в линию обратной связи включен и-разрядный регистр Рг. Данный регистр предназначен для хранения внутреннего состояния автомата Ад.
Синтез автоматной марковской модели над полем GF{2").
Если для требуемых значений п заранее выбрать примитивные многочлены P(x)=xn+aixn +...+an.ix+l и соответствующие им сопровождающие матрицы, то можно построить алгоритм синтеза однородной вычислительной структуры.
Далее приведены методики синтеза последовательных и параллельных структур представления конечного автомата без выхода по его описанию [58 - 59,98 - 99] над полем GF(2n).
Методика синтеза последовательных однородных структур по описанию конечного автомата без памяти. Пусть AY=(X,Y,X) - конечный автомат без памяти, где Х- входной алфавит, F-выходной алфавит, X:X Y. Определим алгоритм синтеза следующим образом. 1. Задать элементы множеств X, Y. 2. Построить таблицу, задающую отношение X X- Y. 3. Вычислить щ =[log2X], п2 =[log2l/],w=max(w/,W2). 4. Построить поле G=GF(2n). Для этого необходимо выбрать примитивный многочлен степени п: Р(х)=хп+а1хп +...+ап.1х+1. Затем при помощи генератора элементов поля G получить конкретное представление элементов поля G (см. главу 1, п. 1.2). 5. Закодировать элементы множестве", Г элементами поля G. 6. Представить отношение X:X- Y многочленом от одной переменной над полем G. Для этого вычислить коэффициенты многочлена г g(x) = Y, aix r=2n-l, a„xe G согласно Теореме 1.5. /=0 7. В соответствии вычисленным значениям коэффициентов получить описание настроек для типовых процессорных элементов П(1). 8. Из типовых блоков составить вычислительную структуру, как на рис. 3.4(6), реализующую автомат Л у.
Замечание. Представляет интерес пункт 4 алгоритма, в котором элементы множеств X и Y кодируются элементами поля G. Только в этом пункте имеется возможность управлять видом многочлена g(x), реализующего отображение X:X-$Y. Значит, среди возможных способов кодирования можно выбрать такой, чтобы обнулить некоторые коэффициенты многочлена g(x) или как частный случай - приравнять нулю коэффициент при высшей степени многочлена g(x).
Методика синтеза параллельных однородных структур по описанию конечного автомата без выходов. Пусть AY=(X,Y,d) - конечный автомат без выходов, где X - входной алфавит, Q - множество состояний, S.XxQ- Q. Определим алгоритм синтеза следующим образом.
1. Определить элементы множеств X, Q. Построить таблицу, задающую отношение д. 2.Вычислить щ =[log2Z], «2 = [log2 ], w=max(«/,/72) 3. Построить поле G GF(2n). Для этого выбрать примитивный многочлен степени п: Р(х) =хп+а,хп +... +ап.,х+1. При помощи генератора элементов поля G получить конкретное представление элементов поля G (см. п. 1.2). 4. Закодировать элементы множестве, Qэлементами поля G. 5. Представить отношение д многочленом от двух переменных над полем G. Для этого вычислить коэффициенты многочлена f(x,q) = aIJx qJ , і,у=0 r=2n-l; ay,x,qeG, по формуле 1.13. 6. Согласно вычисленным значениям коэффициентов, получить описание конфигурации для типовых процессорных элементов П(2). 7. Из типовых блоков составить вычислительную структуру вида - рис. 3.4, реализующую автомат
Полиномиальная модель от двух переменных f(x,q) над полем GF(2n) может быть минимизирована (в зависимости от задачи минимизации) в случае её представления в виде многочлена от одной переменной Ци) (1.15) над полем GF(22n). Решение задачи уменьшения количества блоков Пп z = 0,r-l, r = 22n-\, заключается в увеличении числа нулевых коэффициентов при высших степенях полинома Ци). Указанная задача в общем случае является NP-полной [9, 86]. В [101] предложен алгоритм, позволяющий уменьшить степень многочлена, моделирующего функцию перехода конечного детерминированного автомата без выходов (КДА) М = (X,Q,S), определённого в поле Галуа, где X eGF(2m) = G - множество входных элементов, QeGF(2k) = F - множество состояний, отображение 5:Gy.F-»F, или S(x,q) = q , где xeG, q,q eF. Отображение 5можно представить в виде многочлена от двух переменных над полем GF(2"), где п = тах(т,к):
Таким образом, моделью автомата М может быть однородная вычислительная структура (ОВС) вида как на рис. 1.6. Для реализации S(x,q) требуется г блоков П [124]. Для реализации многочлена от одной переменной Ци) (1.15) требуется s-1 блоков, каждый из которых вычисляет произведение atz ,i = 1,5-1. При этом сложность вычисления слагаемых многочлена Ци) меньше, чем для многочлена (ЗЛО). Теорема 3.2. Пусть M = (X,Q,S) конечный детерминированный автомат без выходов, где X є GF(2m ) = G - множество входных элементов, Q є GF(2 ) = F - множество состояний, отображение S:GxF- F, или S(x,q) = q , где х є G, q,q eF. Если построить полиномиальную модель для 5(x,q) в виде многочлена от одной переменной Ци), u=(x,q)T над, полем GF(2m ), то существует такое отображение 8 :Gx.F - GxF, для которого многочлен Ци) имеет минимальную степень.
Определение базовых математических моделей умножителя
Пусть задан алфавит Z с мощностью Z\ = d. Тогда а-связную (а 1) ЦМ можно задать стохастической матрицей Ра размера da xda, где величина da -число состояний цепи. Состояниями являются всевозможные упорядоченные последовательности - цепочки е, длины a, i = \,da, составленные в алфавите Z. Для каждой цепочки е1 определены условные вероятности ptJ =p(z /et), где i = l,da, j - \,da , Zj eZ. Множество цепочек et обозначим как Za. Задачу представления «-связной ЦМ полиномиальной моделью можно свести к заданию ПМ простой ЦМ [78]. Это определяется тем, что а-связные ЦМ, а 1, путем надлежащего представления можно привести к виду, удовлетворяющему всем требованиям простых ЦМ.
Определим ПМ «-связной ЦМ над полем Галуа на основе автоматной модели А{1). Пусть стохастическая матрица Ра удовлетворяет следующему ограничению: в матрице Ра положительные элементы некоторых распределений условных вероятностей р -p(z let) для соответствующих цепочек et совпадают, то есть число к распределений в матрице Ра, различающихся положительными элементами, удовлетворяет соотношению к da.
Тогда на множестве Za в соответствии с различающимися распределениями можно задать разбиение вида (4.15) на к непересекающихся попарно неэквивалентных подмножеств состояний.
При принятом ограничении модель А{1) уточним следующим образом. Для автомата Ам примем 1 1= и Г=&. Функцию fi{zly) зададим стохастической матрицей Р а размера к х d, строки которой представляют все различающиеся условные распределения с элементами ру = p(z. Iet), i = \,k, j = \,d.
Так как k da автомату Ам можно поставить в соответствие приведенный автомат А м, эквивалентный Ам. При этом А м имеет минимальное число состояний И, которое удовлетворяет соотношению k h da.
Обозначим множество состояний автомата А м через S ={sl\s2\...,sh1}. Зададим приведенный автомат Мура системой: A M=(Z,S\Y,A(z,s ),S(s4s0), где Z\ = d, S \ = h, Y\ = k,Z(z,s ):ZxS - S\S(s ):S -- Y.
Известно [117], что последовательность выходных букв над алфавитом Z ABA, заданного системой (А м,/ (г/у),л:0), является а-связной ЦМ, где функция ju(z/y) задается стохастической матрицей Р а, а отображения A(z,s ) и S(s ) задаются на основе ju(z/y), 7Г0 - начальное распределение вероятностей букв алфавита Y.
Матрицу Р а представим в виде разложения /=1 где /3 kd-k + \, и\ - значения СДВ U с распределением (Pi,/?2 - P/3) Теорема 4.5 [111]. Пусть заданы: я-связная цепь Маркова (а 1) стохастической матрицей Ра с множеством состояний Za, разбиение над Xа вида (4.15) и вектор я0. Тогда последовательность значений а-связной цепи Маркова может быть представлена последовательностью значений функции 4 = fi S /і " суперпозиции трех полиномов, /j и /2 вида (4.8) для двух переменных и g вида (1.3) над полем GF(2"), где п - наименьшее целое, определяемое условием 2" max(/2,/3, i). Начальное состояние цепи Маркова определяется начальным значением переменной полинома g по вектору я0.
Доказательство. По матрицам Ра и Р а (матрица Р а построена по заданному разбиению над Iа вида (4.15)) зададим для А м отображение A(z,s ):ZxS - S , где \S \ = h, и отображение S(s ):S - Y, где \Y\ = k. По разложению (4.23) матрицы Р а зададим отображение A (u ,y):U xY- Z, где U - множество значений случайной величины U с распределением вероятностей, удовлетворяющим (4.23), U \ = l3, Z\ = d. Построенные отображения представим полиномами над полем GF(2n) по методике, рассмотренной в п. 1.4: Z(z,s ) - полиномом f\(x,q) вида (4.8); S(s ) - полиномом g(q) вида (1.3); Х\и ,у)- полиномом f2(x ,q ) вида (4.8), где , q є GF{2").
Похожие диссертации на Полиномиальные модели автоматных преобразований над полем GF(2")
