Сверточное кодирование

В качестве примера закодируем сообщение «ау» (см. рисунок 4.15)

Рисунок 3.15 - Тестирование программы (кодирование)

В двоичном коде оно будет иметь вид:

1110000011110011

А после кодирования сверточным кодером станет таким:

11011001110000001101101001111101

Так как вероятность ошибки была равная нулю (рисунок 3.7) то сообщение миновало канал без изменений и было декодировано верно.

Теперь попробуем внести в принятое сообщение одиночные ошибки канала (см. рисунок 3.16)

Рисунок 3.16 - Тестирование программы (имитация канала связи)

Как видно из рисунка 3.16 ошибки изменили веса вершин, но итоговый путь, построенный декодером (отмечен жирной линией) не изменился.

Теперь попробуем внести в сообщение двойные ошибки (рисунок 3.17)

Рисунок 3.17 - Тестирование программы (декодирование)

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

3.5 Быстродействие программы

В разделе технико-экономического обоснования были рассчитаны затраты на создание данного ПО и определена его цена - 6723 грн. Капитальные затраты для разработчика составили 3630 грн. Рентабельность данного программного продукта составляет 28%. Анализ экономической эффективности подтвердил целесообразность создания данного программного продукта.

1.Никитин Г. И. Сверточные коды: Учебное пособие.. -- С-П.: Сов. радио, 2001. -- 78 с

2.Бернард Скляр Цифровая связь. Теоретические основы и практическое применение.

3.Витерби А.Д., Омура Дж.К. Принципы цифровой связи и кодирования /Пер. с англ. под ред. К.Ш. Зигангирова. -- М.: Радио и связь, 1982. -- 536 с.

4.Чернега В., Платтнер Б. Компьютерные сети: Учебник для вузов/ В. Чернега, Б. Платтнер - Севастополь: Изд-во СевНТУ, 2006. - 500 с.

5.Культин Н.Б. Delphi 6. Программирование на Object pascal. БХВ-Петербург, 2001 г. 528с.

Приложение А

Текст программы

unit Viterbi_Unit;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ComCtrls, Grids;

type

{**

* сокращенные названия для типов

*}

pint = ^integer;

int = integer;

{**

* узел сети используемый при декодировании

*}

TNodeDataPtr = ^TNodeData;

TNodeData = record

val : string;// содержимое вершины

way: int;// метрика длины пути

minWayBelong: bool;// принадлежит минимальному пути

parent: TNodeDataPtr;// указатель на родителя

end;

{**

* уровень сети используемой при декодировании

*}

TListElemPtr =^TListElem;

TListElem = record

nodes: array [0..3] of TNodeDataPtr;// узлы текущего уровня

code: string;// декодируемый код

pnext: TListElemPtr;// указатель на следующий уровень

pprev: TListElemPtr;// указатель на предыдущий уровень

end;

{**

* форма

*}

TmyForm = class(TForm)

step1Btn: TButton;

step2Btn: TButton;

step3Btn: TButton;

allStepsBtn: TButton;

GroupBox2: TGroupBox;

inputData: TRichEdit;

step0Data: TRichEdit;

step1Data: TRichEdit;

step2Data: TRichEdit;

step3Data: TRichEdit;

step4Data: TRichEdit;

Label1: TLabel;

step1Label: TLabel;

Label3: TLabel;

Label4: TLabel;

step2Label: TLabel;

Label6: TLabel;

step0Label: TLabel;

Label8: TLabel;

errorMultiplicityBox: TComboBox;

errorProbabilityBox: TComboBox;

leftTreePaintPosition: TScrollBar;

procedure step1BtnClick(Sender: TObject);

procedure step2BtnClick(Sender: TObject);

procedure step3BtnClick(Sender: TObject);

procedure allStepsBtnClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure FormPaint(Sender: TObject);

procedure leftTreePaintPositionChange(Sender: TObject);

procedure printTree(t:TListElemPtr; levelNum :int);

procedure step0();

procedure step1();

procedure step2();

procedure step3();

procedure step4();

private

bitmap: TBitmap;

public

{ Public declarations }

end;

{**

* автомат Мили (кодер)

*}

MealyAutomaton = class

private

R1:int;// регистры сдвига

R2:int;

// конструктор

constructor init;

public

// побитовый кодер

procedure coding(X:int; Y1:pint; Y2:pint);

end;

{**

* декодер работающий по алгоритму Витерби

*}

TTreeHandler = class

public

pleft: TListElemPtr;// указатель на корневой узел сети

// вычисляет сумму по модулю 2 для двух строк

function xorStrings(val_1: string; val_2: string) : string;

// конструктор

constructor init;

// вычисление пути до узла

function calcWayToNode(parent: TNodeDataPtr; nodeVal:string; inputCode: string):int;

// создание корня

procedure creatRoot;

// создание узла сети

function createNode(parent1: TNodeDataPtr; parent2: TNodeDataPtr; nodeVal:string; inputCode: string):TNodeDataPtr;

// вес вершины

function weightCalc(val: string) : int;

// Создание очередного уровня сети

procedure createLevel(temp:TListElemPtr; code:string);

// Удаление всех узлов сети

procedure deleteTree(pleft:TListElemPtr);

// декодирование

function decode() : string;

// инвертирование строки

function rotateString(val: string): string;

end;

var

myForm: TmyForm;// форма

mealyCoder: MealyAutomaton;// кодер

treeHandler: TTreeHandler;// декодер

implementation

{$R *.dfm}

// автомат Мили - НАЧАЛО

{**

* конструктор

*}

constructor MealyAutomaton.init;

begin

R1:=0;

R2:=0;

end;

{**

* побитовый кодер

*}

procedure MealyAutomaton.coding(X:int; Y1:pint; Y2:pint);

begin

y1^:= X xor R2;

y2^:= X xor R2;

R2:= R1;

R1:= X;

y1^:= y1^ xor R2;

end;

// автомат Мили - КОНЕЦ

// декодер - НАЧАЛО

{**

* вычисляет сумму по модулю 2 для двух строк

*}

function TTreeHandler.xorStrings(val_1: string; val_2: string) : string;

var

res: string;

i: int;

begin

if (length(val_1) <> length(val_2)) then

begin

res := '';

end

else

begin

for i:=1 to length(val_1) do

begin

if (val_1[i] = val_2[i]) then

begin

res:=res+'0'

end

else

begin

res:=res+'1';

end

end

end;

xorStrings := res;

end;

{**

* конструктор

*}

constructor TTreeHandler.init;

begin

pleft:= NIL;

end;

{**

* вычисление пути до узла

*}

function TTreeHandler.calcWayToNode(parent: TNodeDataPtr; nodeVal:string; inputCode: string):int;

var

resultWay : int;

begin

resultWay := 0;

// Вершина "00"

if (parent^.val = '00') then

begin

// левый потомок

if (nodeVal = '10') then

begin

resultWay := parent^.way + WeightCalc(xorStrings('11', inputCode));

end

// правый потомок

else

begin

resultWay := parent^.way + WeightCalc(xorStrings('00', inputCode));

end

end

// Вершина "10"

else if(parent^.val = '10') then

begin

// левый потомок

if (nodeVal = '11') then

begin

resultWay := parent^.way + WeightCalc(xorStrings('01', inputCode));

end

// правый потомок

else

begin

resultWay := parent^.way + WeightCalc(xorStrings('10', inputCode));

end

end

// Вершина "11"

else if(parent.val = '11') then

begin

// левый потомок

if (nodeVal = '11') then

begin

resultWay := parent^.way + WeightCalc(xorStrings('10', inputCode));

end

// правый потомок

else

begin

resultWay := parent^.way + WeightCalc(xorStrings('01', inputCode));

end

end

// Вершина "01"

else if(parent^.val = '01') then

begin

// левый потомок

if (nodeVal = '10') then

begin

resultWay := parent^.way + WeightCalc(xorStrings('00', inputCode));

end

// правый потомок

else

begin

resultWay := parent^.way + WeightCalc(xorStrings('11', inputCode));

end

end;

calcWayToNode := resultWay;

end;

{**

* создание корня

*}

procedure TTreeHandler.creatRoot;

begin

new(pleft);

pleft^.pnext:= NIL;

pleft^.pprev:= NIL;

new(pleft^.nodes[0]);

pleft^.nodes[0]^.val:= '00';

pleft^.nodes[0]^.way:= 0;

pleft^.nodes[0]^.minWayBelong := true;

pleft^.nodes[0]^.parent:= NIL;

pleft^.nodes[1]:= NIL;

pleft^.nodes[2]:= NIL;

pleft^.nodes[3]:= NIL;

end;

{**

* создание узла сети

*}

function TTreeHandler.createNode(

parent1: TNodeDataPtr;

parent2: TNodeDataPtr;

nodeVal:string;

inputCode: string

):TNodeDataPtr;

var

nodeParent: TNodeDataPtr;

resultNode: TNodeDataPtr;

way1: int;

way2: int;

resWay: int;

begin

if ((parent1 = NIL) AND (parent2 = NIL)) then

begin

resultNode := NIL;

end

else

begin

if (parent1 = NIL) then

begin

nodeParent:= parent2;

end

else if (parent2 = NIL) then

begin

nodeParent:= parent1;

end

else

begin

way1 := calcWayToNode(parent1, nodeVal, inputCode);

way2 := calcWayToNode(parent2, nodeVal, inputCode);

if (way2 > way1) then nodeParent := parent1

else nodeParent:= parent2;

end;

resWay := calcWayToNode(nodeParent, nodeVal, inputCode);

new(resultNode);

resultNode^.val := nodeVal;

resultNode^.way := resWay;

resultNode^.minWayBelong := false;

resultNode^.parent := nodeParent;

end;

createNode := resultNode;

end;

{**

* вес вершины

*}

function TTreeHandler.weightCalc(val: string) : int;

var

res: int;

i: int;

begin

res := 0;

for i:=1 to length(val) do

begin

if (val[i] = '1') then

begin

res := res + 1;

end

end;

weightCalc := res;

end;

{**

* Создание очередного уровня

*}

procedure TTreeHandler.createLevel(temp:TListElemPtr; code:string);

var

newLevel : TListElemPtr;

begin

if((temp^.pnext <> NIL)) then

begin

CreateLevel(temp.pnext, code);

end

else

begin

new(newLevel);

temp^.pnext := newLevel;

temp^.code:= code;

newLevel^.pnext:= NIL;

newLevel^.pprev:= temp;

newLevel^.nodes[0]:= createNode(temp^.nodes[0], temp^.nodes[2], '00', code);

newLevel^.nodes[1]:= createNode(temp^.nodes[0], temp^.nodes[2], '10', code);

newLevel^.nodes[2]:= createNode(temp^.nodes[1], temp^.nodes[3], '01', code);

newLevel^.nodes[3]:= createNode(temp^.nodes[1], temp^.nodes[3], '11', code);

end

end;

{**

* Удаление всех узлов дерева

*}

procedure TTreeHandler.deleteTree(pleft:TListElemPtr);

begin

if (pleft <> NIL) then

begin

DeleteTree(pleft.pnext);

DISPOSE (pleft);

end;

pleft := NIL;

end;

{**

* декодирование

*}

function TTreeHandler.decode() : string;

var

temp: TListElemPtr;

resultStr: string;

minWayNode: TNodeDataPtr;

i: int;

begin

temp := pleft;

while (temp^.pnext <> NIL) do

begin

temp := temp^.pnext;

end;

minWayNode := NIL;

for i:=0 to 3 do

begin

if (temp^.nodes[i] = NIL) then

begin

break;

end;

if ((minWayNode = NIL) OR (minWayNode^.way > temp^.nodes[i]^.way)) then

begin

minWayNode := temp^.nodes[i];

end;

end;

while (minWayNode^.parent <> NIL) do

begin

resultStr := resultStr + minWayNode^.val[1];

minWayNode^.minWayBelong := true;

minWayNode := minWayNode^.parent;

end;

decode := rotateString(resultStr);

end;

{**

* инвертирование строки

*}

function TTreeHandler.rotateString(val: string): string;

var

res : string;

strLen : int;

i : int;

begin

res := '';

strLen := length(val);

i := strLen;

while (i >= 1) do

begin

res:= res + val[i];

i:= i-1;

end;

rotateString := res;

end;

// декодер - КОНЕЦ

// методы формы - НАЧАЛО

{**

* Создание формы

*}

procedure TmyForm.FormCreate(Sender: TObject);

begin

// инициализируем автомат мили

mealyCoder := MealyAutomaton.init();

// инициализируем декодер

treeHandler := TTreeHandler.init();

myForm.DoubleBuffered := true;

bitmap := TBitmap.Create;

randomize();

inputData.Clear();

inputData.Text := 'тест1.';

end;

{**

* перерисовка формы

*}

procedure TmyForm.FormPaint(Sender: TObject);

begin

printTree(treeHandler.pleft, 0);

end;

{**

* Отображение дерева

*}

procedure TmyForm.printTree(t:TListElemPtr; levelNum :int);

var

i : int;

node : TNodeDataPtr;

nodeParent : TNodeDataPtr;

leftPos : int;

topPos : int;

levelHeight : int;

levelWidth : int;

levelX : int;

levelY : int;

ellipse : int;

parentNodeY : int;

parentNodeX : int;

max : int;

begin

leftPos := 60 - leftTreePaintPosition.Position;

topPos:= 40{+myForm.GroupBox2.Height};

levelHeight :=35;

levelWidth :=60;

ellipse :=12;

parentNodeX := 0;

parentNodeY := 0;

// очищаем канву

bitmap.Width := myForm.Width;

bitmap.Height := myForm.Height;

bitmap.Canvas.Brush.Color:= {clWhite}clBtnFace;

bitmap.Canvas.Pen.Style:= psSolid;

bitmap.Canvas.Pen.Color:= clBlack;

bitmap.Canvas.FillRect(Rect(0,0,myForm.Width,myForm.Height));

// Рекурсивное прохождение заканчивается на пустом поддереве

while (t <> NIL) do

begin

levelX := leftPos + levelWidth*levelNum;

for i:=0 to 3 do

begin

if (t^.nodes[i] <> NIL)then

begin

levelY := topPos + levelHeight*i;

node := t^.nodes[i];

// рисуем связь с родителем

nodeParent := node^.parent;

if (nodeParent <> NIL) then

begin

if (nodeParent.val = '00') then parentNodeY :=0

else if(nodeParent.val = '10') then parentNodeY :=1

else if(nodeParent.val = '01') then parentNodeY :=2

else parentNodeY :=3;

parentNodeY := topPos + levelHeight*parentNodeY;

parentNodeX := levelX-levelWidth;

// выделяем минимальный путь

if (node^.minWayBelong) then

begin

bitmap.Canvas.Pen.Color:= clRed;

bitmap.Canvas.Pen.Width :=2;

end

else

begin

bitmap.Canvas.Pen.Color:= clBlack;

bitmap.Canvas.Pen.Width :=1;

end;

bitmap.Canvas.MoveTo(levelX, levelY);

bitmap.Canvas.LineTo(parentNodeX, parentNodeY);

end;

bitmap.Canvas.Pen.Color:= clBlack;

bitmap.Canvas.Pen.Width :=1;

// рисуем текущий узел

bitmap.Canvas.Ellipse(levelX-ellipse, levelY-ellipse, levelX+ellipse, levelY+ellipse);

bitmap.Canvas.TextOut(levelX-7, levelY-6, IntToStr(node^.way));

// перерисовывам родителя

if (nodeParent <> NIL) then

begin

bitmap.Canvas.Ellipse(parentNodeX-ellipse, parentNodeY-ellipse, parentNodeX+ellipse, parentNodeY+ellipse);

bitmap.Canvas.TextOut(parentNodeX-7, parentNodeY-6, IntToStr(nodeParent^.way));

end;

end;

// номер уровня

bitmap.Canvas.TextOut(levelX-7, topPos-6 + levelHeight*4, IntToStr(levelNum+1));

// декодируемый код

bitmap.Canvas.TextOut(levelX-7+ trunc(levelWidth/2), 10, t^.code);

end;

// рисуем следующий уровень

t := t^.pnext;

levelNum := levelNum+1;

end;

if (treeHandler.pleft <> NIL) then

begin

bitmap.Canvas.FillRect(Rect(0,0,40,myForm.Height));

bitmap.Canvas.TextOut(10, topPos-6, '00');

bitmap.Canvas.TextOut(10, topPos-6 + levelHeight, '10');

bitmap.Canvas.TextOut(10, topPos-6 + levelHeight*2, '01');

bitmap.Canvas.TextOut(10, topPos-6 + levelHeight*3, '11');

myForm.Canvas.Draw(0,0,bitmap);

max := levelNum * levelWidth - myForm.Width + 40;

if (max > 0) then

begin

leftTreePaintPosition.Visible := true;

leftTreePaintPosition.Max := max;

end

else

begin

leftTreePaintPosition.Visible := false;

end

end

else

begin

leftTreePaintPosition.Visible := false;

end;

end;

{**

* преобразование строки в двоичный код

*}

procedure TmyForm.step0();

var

sym: char;

i: int;

j: int;

str: string;

begin

step0Data.Text := '';

for i := 1 to length(inputData.Text) do

begin

sym:= inputData.Text[i];

str:= '';

for j:=0 to 7 do

begin

if (int(sym) and (1 shl j) > 0) then str :='1'+str

else str :='0'+str;

end;

step0Data.Text := step0Data.Text + str;

end;

step0Label.Caption := 'Соощение в двоичном коде ('+IntToStr(length(step0Data.Text))+' бит)';

end;

{**

* кодирование строки с помощью автомата мили

*}

procedure TmyForm.step1();

var

y1: int;// Выходы автомата Мили

y2: int;

res: string;// Результат кодирования

i: int;

sym : int;

begin

res := '';

mealyCoder.init();

for i := 1 to length(step0Data.Text) do

begin

if ((step0Data.Text[i] = '0') OR (step0Data.Text[i] = '1')) then

begin

sym := int(step0Data.Text[i])-int('0');

mealyCoder.Coding(sym, @y1, @y2);

res := res + IntToStr(y1)+IntToStr(y2);

end;

end;

step1Data.Text := res;

step1Label.Caption := 'Закодированное сообщение ('+IntToStr(length(step1Data.Text))+' бит)';

end;

{**

* имитация канала связи

*}

procedure TmyForm.step2();

var

i : int;

j : int;

errorMultiplicity: int;

errorProbability: int;

errorInterval: int;// промежуток, в котором возможно появление пачки ошибок

errorPosition: int;// местоположение ошибки

str: string;

maxErrors : int;// максимальное количество ошибок

errorCount : int;// счетчик количества ошибок

begin

errorInterval:= 1;

errorMultiplicity:= StrToInt(errorMultiplicityBox.Text);

errorProbability:= trunc(StrToFloat(errorProbabilityBox.Text) * 100);

// очищаем стили

step2Data.SelStart:= 1;

step2Data.SelLength := length(step2Data.Text);

step2Data.SelAttributes.Color:= clBlack;

step2Data.SelAttributes.Style:= [];

step2Data.Lines.Clear();

str := step1Data.Text;

randomize();

maxErrors := round(length(str) * (errorProbability/100));

errorCount := 0;

i:=1;

while ((i <= length(str)) AND (maxErrors > 0)) do

begin

if (errorCount >= maxErrors) then

begin

break;

end;

if (random(99) + 1 <= errorProbability) then

begin

errorPosition := 0;

// меняем 1 на 0 и 0 на 1 (т.е. генерируем ошибку)

for j:=i+errorPosition to i+errorPosition+errorMultiplicity - 1 do

begin

if (j > length(str)) then

begin

break;

end;

if (str[j] = '0') then

begin

str[j] := '1'

end

else

begin

str[j] := '0';

end;

errorCount := errorCount + 1;

i := i + 1;

end;

i := i - 1;

// стараемся сделать так, чтобы ошибки не "слепливались"

if ((errorProbability <> 100) AND (random(99) + 1 > errorProbability)) then

begin

i := i + 1;

end;

end;

i := i + errorInterval;

end;

step2Data.Text := str;

step2Label.Caption := 'После прохождения канала ('+IntToStr(length(step2Data.Text))+' бит)';

// выделяем ошибочные символы

for i:=1 to length(str) do

begin

if (str[i] <> step1Data.Text[i])then

begin

step2Data.SelStart:= i-1;

step2Data.SelLength:= 1;

step2Data.SelAttributes.Color:= clFuchsia;

step2Data.SelAttributes.Style:= [fsUnderline, fsBold];

end;

end

end;

{**

* декодирование в двоичный код

*}

procedure TmyForm.step3();

var

code: string;

codeLen: int;

i: int;

begin

code := step2Data.Text;

codeLen:= length(code);

if (codeLen > 0) then

begin

// удаление дерева (если уже был запуск декодера)

treeHandler.DeleteTree(treeHandler.pleft);

// Инициализация дерева

treeHandler.CreatRoot();

// строим дерево декодера

i := 1;

while (i < codeLen) do

begin

treeHandler.createLevel(treeHandler.pleft, copy(code, i, 2));

i := i+2;

end;

// выводим результат декодирования

step3Data.Text := treeHandler.decode();

// рисуем дерево декодера

printTree(treeHandler.pleft, 0);

end;

end;

{**

* перевод из двоичного кода в строку

*}

procedure TmyForm.step4();

var

str: string;

i: int;

j : int;

sym : int;

begin

str:= '';

i:= 1;

while (i < length(step3Data.Text)) do

begin

{str := str + copy(step3Data.Text, i, 8);}

sym := 0;

for j:=0 to 7 do

begin

sym := (sym shl 1) + (byte(step3Data.Text[i+j]) and 1) ;

{sym + integer(step3Data.Text[i+j])-integer('0');

sym := sym shr 1;}

end;

//sym := 176;

str := str + char(sym);

i := i+8;

end;

step4Data.Text := str;

end;

{**

* кнопка "закодировать"

*}

procedure TmyForm.step1BtnClick(Sender: TObject);

begin

step0();

step1();

end;

{**

* кнопка "канал связи"

*}

procedure TmyForm.step2BtnClick(Sender: TObject);

begin

step2();

end;

{**

* кнопка "декодировать"

*}

procedure TmyForm.step3BtnClick(Sender: TObject);

begin

step3();

step4();

end;

{**

* кнопка "все шаги сразу"

*}

procedure TmyForm.allStepsBtnClick(Sender: TObject);

begin

step0();

step1();

step2();

step3();

step4();

end;

{**

* прокрутка отображения дерева

*}

procedure TmyForm.leftTreePaintPositionChange(Sender: TObject);

begin

printTree(treeHandler.pleft, 0);

end;

// методы формы - КОНЕЦ

end.

Приложение Б

Таблица ASCII кодов ASCII Таблица символов 0 - 127.

Значениями 0-32 и 127 закодированы непечатаемые символы. Они не имеют графического представления, но в зависимости от приложения, могут влиять на отображение текста.

Таблица символов 128 - 255.

Приложение В