Автор работы: Пользователь скрыл имя, 14 Мая 2013 в 15:45, курсовая работа
Данный курсовой проект является разработкой и исследованием алгоритма и прикладной программы моделирования автономной матричной линейной последовательностной машины (АМЛПМ) над полем GF(р).
Данная тема является актуальной, так как линейные последовательностные машины (ЛПМ) широко применяются в автоматике и вычислительной технике в качестве генераторов последовательностей, счетчиков, кодирующих и декодирующих устройств, устройств обнаружения а исправления ошибок, при моделировании нейронных сетей и т. д.
1. Вступление. 3
2. Краткие теоретические сведения 4
2.1 Основные аспекты псевдослучайных последовательностей 4
2.2 Разновидности ПСП 6
2.1.1. М-последовательности 6
2.2.3. Последовательности Голда 8
2.2.4. Последовательности Касами 10
2.2.5. Последовательности Баркера 11
2.3 Случайные и псевдослучайные числа 12
3. Алгоритм работы программы 14
Описание схемы алгоритма основного модуля: 15
4. Описание программы 17
5. Описание и обоснование выбора состава технических средств 19
6. Результаты работы программы 20
7. Выводы 22
8. Литература 23
Случайные и псевдослучайные числа, числа, которые могут рассматриваться в качестве реализации некоторой случайной величины. Как правило, имеются в виду реализации случайной величины, равномерно распределенной на промежутке (0,1), или приближения к таким реализациям, имеющие конечное число цифр в своём представлении. При такой узкой трактовке случайное число (с. ч.) можно определить как число, составленное из случайных цифр (с. ц.). С. ц. в р-ичной системе счисления является результатом эксперимента с р равновероятными исходами (каждому из исходов соответствует одна из р цифр). Эксперименты по получению каждой с. ц. предполагаются независимыми.
Источником с. ц. первоначально служили результаты переписи населения и др. таблицы чисел, полученных экспериментальным путём. Первые таблицы с. ц. были составлены в 1927 в связи с нуждами математической статистики (необходимостью случайного выбора при планировании эксперимента). В дальнейшем в связи с возникновением статистических испытаний метода были созданы специальные экспериментальные устройства — датчики или генераторы с. ч., основанные в большинстве случаев на использовании шумов радиоэлектронных приборов (см. Случайных чисел датчик).
С развитием метода статистических
испытаний также связано
Программа предназначена для программу моделирования автономной матричной линейной последовательности (АМЛПМ) над полем GF(p), описываемой матричным рекуррентным уравнением над полем GF(p) вида:
S(I+1)=A*S(I)*B, где A и B – квадратные характеристические матрицы АМЛПМ размера nxn и mxm;
I={0,1,2,3…}
S(1);S(I) и S(I+1) – векторы начального, предыдущего и последующего состояний АМЛПМ nxm.
Значит нам необходимо
составить блок-схему
Значит, нам необходимо составить блок-схему алгоритма основного тела программы, которую потом разобьем на модули.
Схема алгоритма основного модуля
1. Ввод матриц. Матрица A и B: выбирается полином из заданного множества полиномов и записывается в нулевую строку, элементы на диагонали ниже главной диагонали получают значение 1, остальные элементы нулевые.
Вектор S[0] задан по умолчанию.
2. Значению S[I] присваиваем значение заданного исходного вектора. Переменная Н необходима для вычисления весовой функции Хэмминга. На данном шаге она сбрасывается в 0.
3. Нахождение периода матриц A, B, S по формуле.
4-5. На каждой итерации осуществляется последовательное умножение матрицы на матрицу в соответствии с формулой: S[I+1] = A*S[I]*B, где S[0], S[I], S[I+1]– векторы начального, предыдущего и последующего состояний АМЛПМ размера nxm, а A и B – квадратные характеристические матрицы размера nxn и mxm. Количество проходов цикла, которые нужно сделать – пока текущий вектор не станет равным исходному или шаг цикла не будет равен периоду в (3).
6-7. Проверка равенства заранее определенного разряда матрицы S[I] единице (в приведенном алгоритме 1-го: S[I,0]). Если равен, то переменная H увеличивается на единицу (весовая функция Хэмминга).
8-9. Вывод результатов и выход.
Схема функции умножения матриц
Описание схемы функции умножения матрицы на матрицу
5. Присвоение переменной Sum сумму произведения соответствующих элементов.
6. Присвоение полученного
значения соответствующему
Программный продукт является платформенно-независимым продуктом, поэтому на любой ОС пользовательский интерфейс будет выглядеть следующим образом:
- выбор степени полинома;
- выбор показательно степени полинома;
Период матрицы(A, B, S)- подсчитанный период матриц A,B,S;
Вес Хемминга- подсчитанный вес Хемминга;
- кнопка для расчёта состояния АМЛПМ и ВКФ;
– кнопка, по нажатии на которую строится график вычисленной ВКФ.
Окно с графиком выглядит следующим образом:
В данном проекте используется язык программирования Delphi (Object Pascal). Конечный продукт, написанный на этом языке, является платформенно-независимым. Кроме этого, данный язык программирования обладает большим количеством различных технологий, что немаловажно при проектировании сложных систем.
Delphi является одним из самых популярных языков программирования. Наиболее существенный отрыв Delphi от ближайших аналогов состоит в действительно быстрой разработке приложений, обладающих сложным пользовательским интерфейсом, особенно имеющим сильные взаимосвязи между элементами управления, расположенными в окнах программы. Также Delphi предлагает довольно мощный набор компонентов для работы с базами данных.. Существует несколько реализаций языка Delphi — как бесплатных, так и коммерческих. Их производят Проект GNU, Microsoft и Embarcadero (Borland).
Входными данными в работе являются квадратные характеристические матрицы заданного размера (Рисунок 6.1.) и матрица начального состояния(Рисунок 6.2.).
Рисунок 6.1. Квадратная характеристическая матрица А
Рисунок 6.2. Матрица начального состояния S
Рисунок 6.3. Результат работы программы
Для последовательностей от двух взаимно-простых полиномов, график ВКФ выглядит следующим образом:
Рисунок 6.4. График ВКФ
В процессе выполнения курсового проекта была спроектирована и реализована программа моделирования АМЛПМ над полем GF(2). Программа осуществляет вычисление последовательности состояний АМЛПМ, периода матриц A,B и S, формирует последовательности состояний каждого заданного разряда матрицы S, а также вычисляет весовые функции Хэмминга этих последовательностей. При проверке модели на тестовых примерах, все работало корректно.
Приложение А
База данных неприводимых полиномов
<n=5>
1 45E
3 75G
5 67H
</n=5>
<n=6>
1 103F
3 127B
5 147H
7 111A
9 013
11 155E
21 007
</n=6>
<n=7>
1 211E
3 217E
5 235E
7 367H
9 277E
11 325G
13 203F
19 313H
21 345G
</n=7>
<n=8>
1 433E
3 567B
5 763D
7 551E
9 675C
11 747H
13 453F
15 727D
17 023
19 545E
21 613D
23 543F
25 433B
27 477B
37 537F
43 703H
45 471A
51 037
85 007
</n=8>
<n=9>
1 1021E
3 1131E
5 1461G
7 1321A
9 1423G
</n=9>
<n=10>
1 2011E
3 2017B
5 2415E
7 3771G
9 2257B
</n=10>
<n=11>
1 4005E
3 4445E
5 4215E
7 4055E
9 6015G
</n=11>
<n=12>
1 10123F
3 12133B
5 10113A
7 12153B
9 11765A
</n=12>
<n=13>
1 20033F
3 23261E
5 24623F
7 23517F
9 30741G
</n=13>
<n=14>
1 42103F
3 40547B
5 43333E
7 51761E
9 54055A
11 40503F
13 77141G
</n=14>
Приложение Б
Текст программы
unit fm_kursovoy;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, DBGridEhGrouping, GridsEh, DBGridEh, DBGridEhVk, polinom, Generics.Collections, StdCtrls,
MemTableDataEh, Db, MemTableEh, DateVk, Matrixes, VirtualTrees, fm_chart, math;
type
TFmKursovoy = class(TForm)
Panel1: TPanel;
Panel2: TPanel;
Splitter2: TSplitter;
ComboBoxDegreeN: TComboBox;
ComboBoxPN: TComboBox;
ComboBoxDegreeM: TComboBox;
ComboBoxPM: TComboBox;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Button1: TButton;
GroupBox1: TGroupBox;
GroupBox2: TGroupBox;
Splitter1: TSplitter;
GroupBox3: TGroupBox;
VirtualStringTree1: TVirtualStringTree;
VirtualStringTree2: TVirtualStringTree;
VirtualStringTree3: TVirtualStringTree;
GroupBox4: TGroupBox;
Memo1: TMemo;
Button2: TButton;
procedure FormCreate(Sender: TObject);
procedure ComboBoxDegreeNChange(Sender: TObject);
procedure ComboBoxDegreeMChange(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure FormResize(Sender: TObject);
procedure VirtualStringTree1GetText(
TextType: TVSTTextType; var CellText: string);
procedure FormDestroy(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure ComboBoxPNChange(Sender: TObject);
procedure ComboBoxPMChange(Sender: TObject);
private
{ Private declarations }
FPolinomList: TList<TPolinom>;
FMatList: TList<TMatrix>;
MatA, MatB, MatS: TMatrix;
Buf1, Buf2: TMatrix;
Mat2: TMatrix;
Fnok: Int64;
afv: TList<Double> ;
procedure CalcList;
function CalcHeming(aMat:tMatrix):
procedure CreateMat2;
procedure Create_AFX(var amat:TMatrix;anok: Integer);
procedure CreateAfv;
function GetPeriodA(n,j, nType: Integer):Integer;
function GetTypeA(const s:String):Integer;
procedure InitComboBox;
procedure InitMatr(aType: Integer);
procedure LoadPolinoms;
function Nod(a,b:Integer):Integer;
function FuncNok(a,b:Integer):Int64;
procedure ReInit;
procedure ShowMatrix(aVt:
procedure WriteMatrix(amatrix:tMatrix);
procedure WriteMemo;
public
{ Public declarations }
property PolinomList: TList<TPolinom>read FPolinomList;
end;
var
FmKursovoy: TFmKursovoy;
implementation
{$R *.dfm}
procedure TFmKursovoy.Button1Click(
begin
// ReInit;
Memo1.Clear;
Application.ProcessMessages;
CalcList;
end;
procedure TFmKursovoy.
Информация о работе Теория алгоритмов и вычислительных процессов