регистрация /  вход

Двоичный циклический код Хэмминга (стр. 1 из 2)

Российский Государственный Социальный Университет

Факультет Социальных информационных технологий

Кафедра Информационной безопасности

Курсовая работа

по дисциплине

Системы и сети связи

Москва – 2006

Задание 1

Для системы связи (СС) с переспросом с ожиданием ответа одностороннего действия (рис. 1) при заданных исходных данных:

1. Найти двоичный циклический (n,k)-код Хэмминга, который обеспечивает передачу сообщений в СС с вероятностью выдачи ложного сообщения Рлс( n , k ) < Pдоп при следующих условиях:

¾ прямой дискретный канал в СС является двоичным симметричным каналом (ДСК) с постоянными параметрами;

¾ обратный непрерывный канал – без помех;

¾ код используется только для обнаружения ошибок;

¾ найденный значения n и k должны обеспечивать минимум разности Pдоплс( n , k ) для возможных значений n и k.

2. Отложить в координатных осях вычисленные значения Рлс( n , k ) для всех исследованных пар (n,k). В этих же осях прямой линией изобразить заданное значение Pдоп .

Исходные данные для курсовой работы (вариант №22):

Вероятность искажения двоичного символа p 6x10-4
Допустимая вероятность ложного сообщения Pдоп 2x10-7
Допустимое число переспросов s
Разрядность кода n >10
Порождающий многочлен gi (x) g3 (x)
Тип кодера КД 1
Ввод информационных символов в кодер последовательно
Тип декодера ДК 2

Рисунок 1. Структурная схема СС с переспросом с ожиданием ответа одностороннего действия

Описание работы СС с переспросом с ожиданием ответа одностороннего действия (рис. 1):

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

Принцип его работы можно понять из рисунка.

Пусть символ «1» передается по каналу связи импульсом положительной полярности с амплитудой U, а «0» импульсом отрицательной полярности с той же амплитудой.

В демодуляторе выделена некоторая зона +V –V, если принимаемый импульс попадает в эту зону (зона ненадежности), то демодулятор считает, что он не может принять надежного решения, о том, какой символ передавался. В этом случае, демодулятор выдает символ ненадежности Z. С выхода демодулятора комбинации поступают на вход декодера. После поступления всей комбинации с выхода декодера в обратный канал направляется одна из двух команд:

¾ «переспрос», если содержатся ошибки в принятой комбинации, и одновременно кодовое слово с символами Z стирается;

¾ «продолжение», если не обнаружено ошибок, и комбинация не корректирующего кода направляется к получателю.

Если различитель команд получает команду «продолжения», то из ЗУ передатчика в прямой канал направляется следующая порция* информации. Если различитель команд получает команду «переспрос», то он переключает ключ в положение 2 и из ЗУ передатчика в прямой канал повторно направляется комбинация, которая была стерта.

После выдачи в прямой канал из ЗУ передатчика очередной порции информации, следующая порция не передаётся до тех пор, пока не будет получен ответ по этой порции.

Порядок расчета Рлс и пример расчета Рлс для циклического ( n , k )–кода Хэмминга, обеспечивающего минимум разности Рдоп – Рлс( n , k ) :

Произведем расчет для (18,13)-кода с d=3.

Для этого введем обозначения:

· Pбо – вероятность появления на выходе ДСК комбинации (n,k)-кода без ошибок при однократной передаче;

· Роо – вероятность появления на выходе ДСК комбинации (n,k)-кода с обнаруживаемыми ошибками при однократной передаче;

· Рно – вероятность появления на выходе ДСК комбинации (n,k)-кода с необнаруживаемыми ошибками при однократной передаче;

· Рi £ v о – вероятность появления на выходе ДСК комбинации с ошибками кратности i£v0 ;

· Рi > v о – вероятность появления на выходе ДСК комбинации с ошибками кратности i>v0 , которые расположены так, что обнаруживаются кодом;

· Рлс – вероятность появления на выходе СС с неограниченным числом переспросов ложного сообщения.

Найдем:

хэмминг код цикличный программа

Pбо = qn , где q=1-p;

Рi £ v о =

, где v0 =d-1;

Роо = Рi £ v о + Рi > v о ;

Рно £ 1- Pбо - Рi £ v о ;

Рлс = Рно /(1- Роо ).

Пример:

Pбо = qn =0,999418 =0,98925490, где q=1-p=0,9994;

Рi £ v о =

=
+
=

18*0,0006*0,98984881+153*0,00000036*0,99044307=0,01074492, где v0 =d-1=2;

Роо = Рi £ v о + Рi > v о = 0,01074492;

Рно £ 1- Pбо - Рi £ v о =1-0,98925490-0,01074492=0,00000018;

Рлс = Рно /(1- Роо )=0,00000018/(1-0,01074492)=0,00000018.


Структурная схема алгоритма расчета кода, ее описание



Описание алгоритма:

1) Начало;

2) Объявляем P = 0.0006, Pdop=0.0000002, i=0, k, Pbo, Poo, Pno, Pls, lgPls, h=0, M[61], H[], d=3;

3) Вручную меняем d (по умолчанию d=3);

4) Если d=2, то i=11, иначе переходим к шагу 7;

5) Если i<=31, тоPbo=(1-P)^i, Poo=0, Poo=(C )*(P^1)*(1-P)^(i-1),

Pno=1-Pbo-Poo, Pls=Pno/(1-Poo), lgPls=log10(Pls),

M[i-11]=(Pdop-Pls), i=i+1, переходим к шагу 5, иначе переходим к шагу 35;

6) Выводим Pbo, Poo, Pno, Pls, lgPls, переходим к шагу 5;

7) Если d=3, то i=11, иначе переходим к шагу 21;

8) Если i<=15, то Pbo=(1-P)^i, Poo=0, k=1, иначе переходим к шагу 14;

9) Выводим Pbo;

10) Если k<=2, то Poo=

, иначе переходим к шагу 12;

11) k=k+1, переходим к шагу 10;

12) Pno=1-Pbo-Poo, Pls=Pno/(1-Poo), lgPls=log10(Pls),

M[i+10]=(Pdop-Pls), i=i+1;

13) Выводим Poo, Pno, Pls, lgPls, переходим к шагу 8;

14) i=17;

15) Если i<=31, то Pbo=(1-P)^i, Poo=0, k=1, иначе переходим к шагу 35;

16) Выводим Pbo;

17) Если k<=2, то Poo=

, иначе переходим к шагу 19;

18) k=k+1, переходим к шагу 17;

19) Pno=1-Pbo-Poo, Pls=Pno/(1-Poo), lgPls=log10(Pls),

M[i+10]=(Pdop-Pls), i=i+1;

20) Выводим Poo, Pno, Pls, lgPls, переходим к шагу 15;

21) Если d=4, то i=11, иначе переходим к шагу 35;

22) Если i<=15, то Pbo=(1-P)^i, Poo=0, k=1, иначе переходим к шагу 28;

23) Выводим Pbo;

24) Если k<=3, то Poo=

, иначе переходим к шагу 26;

25) k=k+1, переходим к шагу 24;

26) Pno=1-Pbo-Poo, Pls=Pno/(1-Poo), lgPls=log10(Pls),

M[i+10]=(Pdop-Pls), i=i+1;

27) Выводим Poo, Pno, Pls, lgPls, переходим к шагу 22;

28) i=17;

29) Если i<=31, то Pbo=(1-P)^i, Poo=0, k=1, иначе переходим к шагу 35;

30) Выводим Pbo;

31) Если k<=3, то Poo=

, иначе переходим к шагу 33;

32) k=k+1, переходим к шагу 31;

33) Pno=1-Pbo-Poo, Pls=Pno/(1-Poo), lgPls=log10(Pls),

M[i+10]=(Pdop-Pls), i=i+1;

34) Выводим Poo, Pno, Pls, lgPls, переходим к шагу 29;

35) h=0, i=0;

36) Если i<=60, то переходим к шагу 37, иначе переходим к шагу 38;

37) Если M[i]>0, то h=h+1, i=i+1, иначе i=i+1 и переходим к шагу 36;

38) Выделяем память под массив Н из h элементов.

39) Если i<=60, то переходим к шагу 40, иначе переходим к шагу 41;

40) Если M[i]>0, то H[k]=M[i], k=k+1, i=i+1, иначе i=i+1 и переходим к шагу 39;

41) i=0;

42) Ищем минимальный элемент в массиве Н;

43) Если i<=60, то переходим к шагу 44, иначе переходим к шагу 50;

44) Если M[i]=минимальному элементу, то и переходим к шагу 45, иначе i=i+1 и переходим к шагу 43;

45) Если i>=0 и i<=20, то выводим (i+11,i+10)-код, иначе переходим к шагу 46;

46) Если i>=21 и i<=25, то выводим (i-10,i-14)-код, иначе переходим к шагу 47;

47) Если i>=26 и i<=40, то выводим (i-9,i-14)-код, иначе переходим к шагу 48;

48) Если i>=41 и i<=45, то выводим (i-30,i-35)-код, иначе переходим к шагу 49;

49) Если i>=46 и i<=60, то выводим (i-29,i-35)-код, иначе i=i+1 и переходим к шагу 39;

50) Выводим минимальный элемент из массива Н, как минимум разницы Рдоплс ;

51) Конец.

Распечатка программы

Программа написана на языке С++.

#include <vcl.h>

#include <math.h>

#include <stdio.h>

#include <vector>

#include <algorithm>

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

float P = 0.0006;

float Pdop = 0.0000002;

using namespace std;

float M[61];

vector<float>H;

char B[128];

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

float C(int n,int m)

{float c=1.0;

for(int i=n;i>=n-m+1;i--)c*=i;

for(int i=1;i<=m;i++)c/=i;

return (int)c;

}

void __fastcall TForm1::ComboBox1Select(TObject *Sender)

{int i=0, k;

double Pbo,Poo,Pno,Pls,lgPls;

AnsiString s;

ListBox1->Clear();