Основы кодирования в информационных системах

Размещено на http://www.allbest.ru/

Содержание

Реферат

Введение

1. Теоретическая часть

1.1 Типы данных

1.2 Операторы присваивания

1.3 Оператор цикла for

1.4 С

2. Практическая часть

2.1 Синтез конечного автомата

2.2 Листинг программы

Заключение

Список использованных источников



Реферат

Цель курсового проекта - закрепить основы и углубить знания в области теории языков программирования и методов трансляции.

Курсовой проект содержит 27 с., 5 табл., 4 рис.

Ключевые слова: транслятор, лексический блок, синтаксический блок, генератор кода, синтез.

В последнее время круг задач, решаемых с помощью ЭВМ, значительно расширился, а сложность задач возросла. В этой ситуации все чаще используются языки высокого уровня, а также специализированные языки. Кроме того, всем известен тот факт, что ЭВМ понимает программы, состоящие только из внутренних команд процессора. В связи с этим возникает задача перевода программы с языка высокого уровня на язык, понятный процессору ЭВМ (трансляция). Разрабатывается один из вариантов программы, выполняющей такой перевод - транслятор.

Результатом данного проекта, является получение и закрепление навыков в создании программ, описывающих методы эффективного и помехоустойчивого кодирования информации, обеспечивающих обнаружение и исправление ошибок в сообщениях при минимальной избыточности передаваемой информации.



Введение

Теория формальных языков, грамматик и автоматов составляет фундамент синтаксических методов. Основы этой теории были заложены Н. Хомским в 40-50-е годы XX столетия в связи с его лингвистическими работами, посвященными изучению естественных языков. Но уже в следующем десятилетии синтаксические методы нашли широкое практическое применение в области разработки и реализации языков программирования.

В настоящее время искусственные языки, использующие для описания предметной области текстовое представление, широко применяются не только в программировании, но и в других областях. С их помощью описывается структура всевозможных документов, трехмерных виртуальных миров, графических интерфейсов пользователя и многих других объектов, используемых в моделях и в реальном мире. Для того чтобы эти текстовые описания были корректно составлены, а затем правильно распознаны и интерпретированы, применяются специальные методы их анализа и преобразования. В основе данных методов лежит теория формальных языков, грамматик и автоматов.

Теория формальных языков, грамматик и автоматов дала новый стимул развитию математической лингвистики и методам искусственного интеллекта, связанных с естественными и искусственными языками. Кроме того, ее элементы успешно применяются, например, при описании структур данных, файлов, изображений, представленных не в текстовом, а двоичном формате. Эти методы полезны при разработке своих трансляторов даже там, где уже имеются соответствующие аналоги.



1. Теоретическая часть

1.1 Типы данных

Типы данных имеют особенное значение в C#, поскольку это строго типизированный язык. Это означает, что все операции подвергаются строгому контролю со стороны компилятора на соответствие типов, причем недопустимые операции не компилируются. Следовательно, строгий контроль типов позволяет исключить ошибки и повысить надежность программ. Для обеспечения контроля типов все переменные, выражения и значения должны принадлежать к определенному типу. Такого понятия, как "бестиповая" переменная, в данном языке программирования вообще не существует. Более того, тип значения определяет те операции, которые разрешается выполнять над ним. Операция, разрешенная для одного типа данных, может оказаться недопустимой для другого.

В C# имеются две общие категории встроенных типов данных: типы значений и ссылочные типы. Они отличаются по содержимому переменной. Концептуально разница между ними состоит в том, что тип значения (value type) хранит данные непосредственно, в то время как ссылочный тип (reference type) хранит ссылку на значение.

Эти типы сохраняются в разных местах памяти: типы значений сохраняются в области, известной как стек, а ссылочные типы - в области, называемой управляемой кучей.



Рис. 1 - Типы данных

Тип int. Целочисленная величина int может быть short (короткой) или long (длинной).

Ключевое слово (модификатор) short ставится после ключевых слов signed или unsigned. Таким образом, различают следующие типы: signed short int, unsigned short int, signed long int, unsigned long int.

Переменная типа signed short int (знаковая короткая целая) может принимать значения от -32768 до +32767, unsigned short int (беззнаковая короткая целая) - от 0 до 65535. Под каждую из них отводится ровно по два байта памяти (16 бит).

При объявлении переменной типа signed short int ключевые слова signed и short могут быть пропущены, и такой тип переменной может быть объявлен просто int. Допускается и объявление этого типа одним ключевым словом short.

Переменная unsigned short int может быть объявлена как unsigned int или unsigned short.

Под каждую величину signed long int или unsigned long int отводится 4 байта памяти (32 бита). Значения переменных этого типа могут находиться в интервалах от -2147483648 до 2147483647 и от 0 до 4294967295 соответственно.

Существуют также переменные типа long long int, для которых отводится 8 байт памяти (64 бита). Они также могут быть знаковыми и беззнаковыми. Для знакового типа диапазон значений лежит в пределах от -9223372036854775808 до 9223372036854775807, для беззнакового - от 0 до 18446744073709551615. Знаковый тип может быть объявлен и просто двумя ключевыми словами long long.

Тип	Диапазон	Шестнадцатиричный диапазон	Размер
unsigned char	0... 255	0x00... 0xFF	8 bit
signed char или просто char	-128... 127	-0x80... 0x7F	8 bit
unsigned short int или просто unsigned int или unsigned short	0... 65535	0x0000... 0xFFFF	16 bit
signed short int или signed int или просто short или int	-32768... 32767	0x8000... 0x7FFF	16 bit
unsigned long int или просто unsigned long	0... 4294967295	0x00000000... 0xFFFFFFFF	32 bit
signed long или просто long	-2147483648... 2147483647	0x80000000... 0x7FFFFFFF	32 bit
unsigned long long	0... 18446744073709551615	0x0000000000000000... 0xFFFFFFFFFFFFFFFF	64 bit
signed long long или просто long long	-9223372036854775808... 9223372036854775807	0x8000000000000000... 0x7FFFFFFFFFFFFFFF	64 bit

Табл. 1

1.2 Операторы присваивания

Операторы присваивания сохраняют значение в объекте, обозначенном левым операндом. Существует два типа операторов присваивания: простое присваивание, при котором значение второго операнда сохраняется в объекте, заданном первым операндом, и составное присваивание, при котором сначала выполняется арифметическая или побитовая операция или операция сдвига, а затем сохраняется результат. Все операторы присваивания в следующей таблице, за исключением оператора =, являются составными.

Операторы присваивания

Operator	Назначение
=	Сохранение значения второго операнда в объект, указанный первым операндом (простое присваивание).
*=	Умножение значения первого операнда на значение второго операнда; сохранение результата в объект, указанный первым операндом.
/=	Деление значения первого операнда на значение второго операнда; сохранение результата в объект, указанный первым операндом.
%=	деление по модулю первого операнда на значение второго операнда; сохранение результата в объект, указанный первым операндом.
+=	Сложение значения первого операнда со значением второго операнда; сохранение результата в объект, указанный первым операндом.
- =	Вычитание значения второго операнда из значения первого операнда; сохранение результата в объект, указанный первым операндом.
"=	Сдвиг значения первого операнда влево на количество битов, заданное значением второго операнда; сохранение результата в объект, указанный первым операндом.
"=	Сдвиг значения первого операнда вправо на количество битов, заданное значением второго операнда; сохранение результата в объект, указанный первым операндом.
&=	Выполнение операции побитового И для значений первого и второго операндов; сохранение результата в объект, указанный первым операндом.
^=	Выполнение операции побитового исключающего ИЛИ для значений первого и второго операндов; сохранение результата в объект, указанный первым операндом.
|=	Выполнение операции побитового включающего ИЛИ для значений первого и второго операндов; сохранение результата в объект, указанный первым операндом.

Табл. 2

Оператор присваивания - это самый употребительный оператор. Его назначение - присвоить новое значение какой-либо переменной. В C++ имеется три формы этого оператора.

1) Простой оператор присваивания записывается так:

переменная = выражение;

Данный оператор работает следующим образом: вначале вычисляется выражение, записанное справа от символа операции = (равно), затем полученный результат присваивается переменной, стоящей слева от знака =. Тип результата должен совпадать с типом переменной, записанной слева, или быть к нему приводимым.

Слева от знака = может быть только переменная, справа же можно записать и константу, и переменную и вообще выражение любой сложности.

Пример операторов:

x=3;

r=x;

y=x+3*r;

s=sin(x);

2) Множественное присваивание - в таком операторе последовательно справа налево нескольким переменным присваивается одно и то же значение, например:

a=b=c=1;

Так можно сразу определить, к примеру, что в равностороннем треугольнике все стороны равны одному и тому же числу 1. Приведенный выше оператор эквивалентен последовательному выполнению трёх операторов:

a=1;

b=a;

c=b;

Естественно, нам проще записать один оператор, а не три. Программа получается короче, более естественно смотрится текст, и работает такая конструкция немного быстрее.

3) Присваивание с одновременным выполнением какой-либо операции в общем виде записывается так:

переменная знак_операции = выражение;

и равносильно записи

переменная = переменная знак_операции выражение;

Например, оператор:

s += 5; // 1-й вариант

делает то же самое, что и оператор

s = s + 5; // 2-й вариант

а именно: взять старое значение из переменной s, прибавить к нему число 5 и полученное значение снова записать в переменную s.

Как видим, запись 1-го варианта короче записи 2-го варианта, да и выполняется быстрее, так как в 1-м варианте адрес переменной s вычисляется 1 раз, а во 2-м варианте - дважды.

1.3 Оператор цикла for

Оператор for - это наиболее общий способ организации цикла. Он имеет следующий формат:

for (выражение 1; выражение 2; выражение 3) тело

Выражение 1 обычно используется для установления начального значения переменных, управляющих циклом. Выражение 2 - это выражение, определяющее условие, при котором тело цикла будет выполняться. Выражение 3 определяет изменение переменных, управляющих циклом после каждого выполнения тела цикла.

Схема выполнения оператора for:

1. Вычисляется выражение 1.

2. Вычисляется выражение 2.

3. Если значения выражения 2 отлично от нуля (истина), выполняется тело цикла, вычисляется выражение 3 и осуществляется переход к пункту 2, если выражение 2 равно нулю (ложь), то управление передается на оператор, следующий за оператором for.

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

Пример:

int main()

{

int i,b;

for (i=1; i<10; i++) b="i*i;" return 0; }

В этом примере вычисляются квадраты чисел от 1 до 9.

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

Пример:

int main()

{

int top, bot;

char string [100], temp;

for (top=0, bot=100; top < bot; top++, bot--)

{

temp=string [top];

string [bot]=temp;

}

return 0;

}

В этом примере, реализующем запись строки символов в обратном порядке, для управления циклом используются две переменные top и bot. Отметим, что на месте выражение 1 и выражение 3 здесь используются несколько выражений, записанных через запятую, и выполняемых последовательно.

Другим вариантом использования оператора for является бесконечный цикл. Для организации такого цикла можно использовать пустое условное выражение, а для выхода из цикла обычно используют дополнительное условие и оператор break.

Пример:

for (;;)

{

...

... break;

...

}

Так как согласно синтаксису языка С оператор может быть пустым, тело оператора for также может быть пустым. Такая форма оператора может быть использована для организации поиска.

Пример:

for (i=0; t [i]<10; i++);

В данном примере переменная цикла i принимает значение номера первого элемента массива t, значение которого больше 10.

1.4 Арифметические операции

Существует пять видов математических операций:

1) Четыре действия арифметики;

2) Операция целочисленного деления;

3) Операция деления по модулю;

4) Операция возведения в степень;

5) Инкремент и декремент;

Рассмотрим их подробнее:

1) Во всех рассматриваемых нами языках программирования символы четырех действий арифметики (сложение, вычитание, умножение, деление) одинаковы: +,-,*,/.

2) Специальная операция целочисленного деления есть только в языках Visual Basic, VBScript: \ и в языке Delphi: div, но во всех языках, произошедших от C++(Visual C++,C++ Builder,C# Java, JavaScript, PHP, Perl),если оба аргумента у операции деления (/) целые числа, то она всегда возвращает целый результат (т.е. действует аналогично операции целочисленного деления).

Языки	C++, C#, Java, PHP, Perl, JavaScript	Delphi	Visual Basic, VBScript
Операция	/	div	\
Пример	5 / 2	21 div 4	14 \ 3
Результат	2	5	4

Табл. 3

3) Операция деления по модулю (эта операция возвращает разность между первым аргументом и максимальным числом, делящимся на второй аргумент без остатка и меньшим или равным первому аргументу).

Языки	C++, C#, Java, PHP, Perl, JavaScript, Transact-SQL	Visual Basic, VBScript, Delphi
Операция	%	mod
Пример	11 % 3	13 mod 5
Результат	2	3

Табл. 4

Операция деления по модулю (например, в Visual Basic'e) аналогична следующей x mod y аналогична x - (x\y)*y. В Visual FoxPro и PL-SQL такой операции нет.

4) Операция возведения в степень (существует только в языках Perl, PL-SQL, Visual Basic, VBScript и Visual FoxPro):

Языки	Visual Basic, VBScript	Perl, PL-SQL	Visual FoxPro
Операция	^	**	** или ^
Пример	6 ^ 2	11 ** 3	2**5	5^3
Результат	36	1331	32	125

Табл. 5

5) Операция инкремент(декремента). Это операция с одним аргументом предназначена для увеличения(уменьшения) аргумента на единицу. Во всех языках, где есть инкремент или декремент, они определены одинаково два плюса или минуса подряд (++ или --). Если в языке существует инкремент или декремент, то существует две его формы: префиксная (++х,--х) и постфиксная (х--,х++).Инкремент или декремент существуют только в языках, произошедших от языка C++ (Visual C++,C++ Builder, Java, JavaScript, PHP, Perl). Префиксная форма отличается от постфиксной, тем что в префиксной форме аргумент изменяется и новое значение участвует в выражении, а в постфиксной форме сначала полностью вычисляется выражение, а уже потом аргумент изменяется. Это проще показать на примере:

Если х = 10, то 3*(++х) равно 33, а 3*(х++) равно 30, но х после обоих этих выражений будет равен 11.

Языки	Инкремент	Декремент
Visual C++,C++ Builder, Java, JavaScript, PHP, Perl	++	--

Табл. 6

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



2. Практическая часть

2.1 Синтез конечного автомата

1. Запуск Visual Studio.Net. Открывается главное окно и в меню Файл выбрать - Создать/Новый проект. Открывается окно создания нового проекта (рис. 1), где среди типов проектов выбрать - Visual C# -Windows и в шаблонах Visual Studio выбрать Приложение Windovs Forms.

Рис. 1 - Окно создания нового проекта

Далее ввести имя проекта КА, определить его расположение D:\TIS\Проекты_КА 2 и нажать кнопку OK.

2. Конструирование формы. Открывается форма (рис. 2), где поместить необходимые элементы: три метки Label для надписей, три текстовых поля TextBox для ввода и вывода необходимых значений, три кнопки Button для создания КА, его работы и завершения работы программы и таблица DataGridView. Для чего выполнить следующее:

Рис. 2 - Окно Visual Studio с открытым проектом

a) "перетащить" мышкой с панели элементов Toolbox текстовое поле TextBox1 и метку Label1 для ввода значения (a) входных символов конечного автомата КА и надписи Aлфавит А;

b) аналогичную операцию проделать для текстового поля TextBox2 и метки Label2 для вывода выходных символов (v) КА и надписи Aлфавит V;

c) текстовое поле TextBox3 и метку Label3 поместить для задания числа состояний КА и надписи Множество Q;

d) "перетащить" мышкой с панели элементов кнопку Button1 и в открытом окне Свойства (Properties) в свойстве Text ввести надпись Синтез для создания КА;

e) аналогичную операцию проделать для кнопку Button2 и в открытом окне Свойства (Properties) в свойстве Text ввести надпись Пуск для начала работы КА;

f) аналогичную операцию проделать для кнопку Button3 и в открытом окне Свойства (Properties) в свойстве Text ввести надпись Стоп для завершения работы КА;

g) "перетащить" мышкой с панели элементов таблицу DataGridView и в открытом окне Свойства (Properties) в свойстве Columns сформировать четыре столбца и ввести их обозначения q_a1, v_a1 и q_a2, v_a2.

3. Создание обработчиков событий

Двойное нажатие кнопки Синтез формирует первый обработчик событий:

private void button1_Click(object sender, EventArgs e)

{

}

где между фигурными скобками будет создана программа, синтезирующая КА, а двойное нажатие кнопки Пуск формирует второй обработчик событий

private void button2_Click(object sender, EventArgs e)

{

}

где между фигурными скобками будет создана программа, определяющая работу КА, а двойное нажатие кнопки Стоп формирует третий обработчик событий

private void button3_Click(object sender, EventArgs e)

{

}

где между фигурными скобками ввести команду Close() для завершения работы программы.

4. Разработка программы

a) Синтез КА. Программа создается в первом обработчике событий кнопки Синтез:

private void button1_Click(object sender, EventArgs e)

{

dGV.Rows.Clear(); //обновление таблицы

int q = int.Parse(textBox3.Text); //инициализация

KA.Q = 0; //инициализация

Random x = new Random(); //задание случайной переменной х

for (int i = 0; i < q; i++) //задание цикла

{

dGV.Rows.Add(x.Next(q), x.Next(2), x.Next(q), x.Next(2));

dGV.Rows [i].HeaderCell.Value = "q" + i.ToString();

}

}

На рис. 3 показано задание четырех состояний КА Q={q0, q1, q2, q3}, вводимых в заголовки каждого ряда КА. В первом ряду КА, обозначенном - q0, первая ячейка x.Next(q)=0, что соответствует состоянию q0, вторая ячейка x.Next(2)=1, что соответствует выходному сигналу v=1, третья ячейка x.Next(q)=3, что соответствует состоянию q3, а четвертая ячейка x.Next(2)=1, что соответствует выходному сигналу v=1, при этом x.Next(2) означает, что случайный выбор осуществляется с равной вероятностью из двух значений - 0 и 1, а x.Next(q) означает, что случайный выбор осуществляется с равной вероятностью из четырех состояний - q0, q1, q2, q3. Напоминаем, что начальное состояние КА - q0 (KA.Q = 0).

Рис. 3 - Синтезированный КА

б) Работа КА. Программа создается во втором обработчике событий кнопки Пуск:

private void button2_Click(object sender, EventArgs e)

{

int a = int.Parse(textBox1.Text);//инициализация

if (a == 0)

{

KA.V = (int)dGV [1, KA.Q].Value;

KA.Q = (int)dGV [0, KA.Q].Value;

}

else

{

KA.V = (int)dGV [3, KA.Q].Value;

KA.Q = (int)dGV [2, KA.Q].Value;

}

textBox2.Text = KA.V. ToString();

textBox3.Text = KA.Q. ToString();

}

На рис. 4 показано, что при подаче на вход а=1, КА из состояния q0 переходит в q3, а на выходе формируется выходной сигнал v=1.

Рис. 4 - Работа КА

в) Завершение работы КА. Нажатие кнопки Стоп включает третий обработчик событий

private void button3_Click(object sender, EventArgs e)

{

Close();

}

где выполняется команда Close(), что прекращает работу программы.

А.5 Работа программы

a) запустить программу с отладкой, нажатием кнопки F5;

b) ввести значение числа состояний КА в текстовое поле TextBox3;

c) нажать кнопку Синтез, что создает КА;

d) ввод входных сигналов а и нажатие кнопки Пуск обеспечивает работу КА;

e) нажать кнопку Стоп для прекращения работы КА.

2.2 Листинг программы

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Ka1

{

public class KA

{

public static int Q { get; set; }

public static int V { get; set; }

}

}

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace Ka1

{

public partial class Form1: Form

{

public Form1()

{

InitializeComponent();

}

private void button1_Click(object sender, EventArgs e)

{

dGV.Rows.Clear();

int q = int.Parse(textBox3.Text);

KA.Q = 0;

Random x = new Random();

for (int i = 0; i < q; i++)

{

dGV.Rows.Add(x.Next(q), x.Next(2), x.Next(q), x.Next(2));

dGV.Rows [i].HeaderCell.Value = "q" + i.ToString();

}

}

private void button2_Click(object sender, EventArgs e)

{

int a = int.Parse(textBox1.Text);

if (a == 0)

{

KA.V = (int)dGV [1, KA.Q].Value;

KA.Q = (int)dGV [0, KA.Q].Value;

}

else

{

KA.V = (int)dGV [3, KA.Q].Value;

KA.Q = (int)dGV [2, KA.Q].Value;

}

textBox2.Text = KA.V. ToString();

textBox3.Text = KA.Q. ToString();

}

private void button3_Click(object sender, EventArgs e)

{

Close();

}

}

}



Заключение

В процессе выполнения курсового проекта, была изучена современная среда Microsoft Visual Studio 2008.

Были рассмотрены и описаны циклические коды, их свойства, методы задания, помехоустойчивость, алгоритмы нахождения, а также принципы построения кодирующих и декодирующих устройств.

Была создана программа, способная выполнять случайный выбор равной вероятности из двух значений - 0 и 1, где сам случайный выбор осуществляется с равной вероятностью из 4 - х состояний - q0, q1, q2, q3.

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



Список использованных источников

1. Прокис Дж. Цифровая связь / Пер. с англ.; Под ред. Д.Д. Кловского. - М. Радио и связь. 2000.

2. Теория электрической связи: учебник для вузов / А.Г. Зюко [и др.] - М.: Радио и связь, 1998.

3. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976.

4. Кузьмин И.В., Ключко В.И., Литвин В.А. Кодирование и декодирование в информационных системах. - Киев: Вища школа, 1985.

5. Кодирование информации: метод. указания для студентов специальности 220400/ Сост. В.И. Ключко. - Краснодар: Изд. КубГТУ, 1998.

Размещено на Allbest.ru

...