Лабораторные работы (2009) (Отчёт по лабораторной работе № 1)

Посмотреть архив целиком

Московский Энергетический Институт

(Технический университет)











Лабораторная работа № 1.











Выполнил: ст. гр. А-13-05 Гончар М.А

Проверила: ст.преп. Гречкина П.В.













12.05.2009.

Оглавление

Постановка задачи. 3

Описание предметной области. 3

Групповой код. 3

Таблица опознавателей. 4

Определение проверочных равенств. 4

Описание табличной модели 5

Пример работы. 12

Приложение. 13



Постановка задачи.

Разработать модель кодирования и декодирования кода (7;4) исправляющего одиночные ошибки.

Описание предметной области.

Далее представлены основные определения и используемые алгоритмы для реализации задачи.

Групповой код.

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

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

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

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

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


Вектора ошибок имеют следующий вид :

=(000...01)=(000...10)

........

=(100...00)

Таблица опознавателей.

N разряда

Вектор ошибки

Опознаватель

1

2

3

4

5

6

7

0000001

0000010

0000100

0001000

0010000

0100000

1000000

001

010

011

100

101

110

111



Для кода (7,4), когда к=4, n=7. Три избыточных разряда позволяют использовать в качестве опознавателей трехразрядные двоичные последовательности. В принципе они могут быть сопоставлены подлежащим исправлению ошибкам в любом порядке. Однако, более целесообразно опознаватели сопоставлять с номерами разрядов, в которых произошли ошибки.

Определение проверочных равенств.

В коде (7,4) 4 информационных и 3 проверочных разряда. То есть при трех проверочных разрядах опознавателя мы можем передавать четыре информационных символа. Найдем места и значения проверочных разрядов.

Предположим, что в результате первой проверки на четность для младшего разряда опознавателя будет получена единица. Очевидно, это может быть следствием ошибки в одном из разрядов, опознаватели которых в младшем разряде имеют единицу. Следовательно, первое проверочное равенство должно включать символы 1-го, 3-го, 5-го и 7-го разрядов:

.

Единица во втором разряде опознавателя может быть следствием ошибки в разрядах, опознаватели которых имеют единицу во втором разряде. Отсюда, второе проверочное равенство должно иметь вид :

.

Аналогично находим и третье равенство :

.

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

Таким образом, для кода (7,4), исправляющего одиночные ошибки, искомые правила построения кода, т.е. соотношения, реализуемые в процессе кодирования, принимают вид :


В процессе декодирования проверяются на верность следующие равенства:



Если равенства не выполняются, значит при передаче была допущена ошибка, определить которую можно следующим образом: нужно записать результаты равенств снизу вверх, чтобы получилось трёхзначное двоичное число, например 101. Оно является опознавателем, по которому можно найти вектор ошибки (например, 0100000) . Зная ошибку можно её исправить, (сложением по модулю 2), и узнать передаваемое сообщение.

Описание табличной модели

Модель включает в себя шесть таблиц, содержащие правила соответствующих алгоритмов.

Таблица 1. Запуск и проверка

С1 – Пуск нажат?

С2 – Входные данные верны?

С3 – Прогонка начата?

R1 - Ждать

R2 – Сообщение об ошибке

R3 – Начать прогонку



Таблица 2. Шифрование

C1 – Какое значение принимает a3?

C2 – Какое значение принимает a5?

C3- Какое значение принимает a6?

C4 – Какое значение принимает a7?

C5 – Сообщение закодировано?

R1 – Устанавливаем а1 в 0

R2 - Устанавливаем а1 в 1

R3 - Устанавливаем а2 в 0

R4 - Устанавливаем а2 в 1

R5 - Устанавливаем а4 в 0

R6 - Устанавливаем а4 в 1

R7 – Установка флага «Сообщение закодировано»

R8 – Передача сообщения по каналу связи в «середину»



Таблица 3. Передача

С1 – Сообщение в середине пути?

С2 – Сообщение в конце пути?

R1 – Внести ошибку

Логические отношения между условиями: С1 -> !C2



Таблица 4. А1



С1 – Какое значение принимает a1?

С2 – Какое значение принимает a3?

С3 – Какое значение принимает a5?

C4 – Какое значение принимает a7?

R1 – Установление 3го разряда кода ошибки в 0

R2 - Установление 3го разряда кода ошибки в 1



Таблица 5. А2



С1 – Какое значение принимает a2?

С2 – Какое значение принимает a3?

С3 – Какое значение принимает a6?

C4 – Какое значение принимает a7?

R1 – Установление 2го разряда кода ошибки в 0

R2 - Установление 2го разряда кода ошибки в 1



Таблица 6. А4

С1 – Какое значение принимает a4?

С2 – Какое значение принимает a5?

С3 – Какое значение принимает a6?

C4 – Какое значение принимает a7?

R1 – Установление 1го разряда кода ошибки в 0

R2 - Установление 1го разряда кода ошибки в 1

R3 – Отображение результатов



Ниже показана полнота и не противоречивость таблиц.

Таблица1

Таблица 2

Таблица 3



Таблица 4



Таблица 5



Таблица 6





Пример работы.

Внесение ошибки













Передача завершена успешно

Программа была реализована в среде СИМПР и языке C# в среде

Приложение.


using System;

using System.Windows.Forms;

using System.Threading;

using System.Runtime.InteropServices;


namespace Shifr74

{

public class MyHookClass : NativeWindow

{

[DllImport("user32.dll", SetLastError = true, CharSet = CharSet.Auto)]

static extern uint RegisterWindowMessage(string lpString);


uint simpr;

Form1 f;


public MyHookClass(Form1 af)

{

simpr = RegisterWindowMessage("msg_Shifr");

this.AssignHandle(af.Handle);

f = af;

}


protected override void WndProc(ref Message m)

{

int wparamhi, wparamlo, wparam;

int lParam = Convert.ToInt32("" + m.LParam);


if (m.Msg == simpr)

{

wparam = Convert.ToInt32("" + m.WParam);

wparamhi = wparam / 65536;

wparamlo = wparam - wparamhi * 65536;


#region Условия

if (wparamhi == 0)

{

if (wparamlo == 1) // Таблица 1

{

switch (lParam)

{

case (1): m.Result = f.StartOff; break; //Пуск нажат?

case (2): m.Result = f.checkInput(); break; //Входные данные верны?

case (3): m.Result = f.IsStarting; break; //Прогонка начата

}

}


Случайные файлы

Файл
55542.rtf
46098.rtf
kluchi.DOC
26150.doc
129950.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.