Циклический код

Пример разработки алгоритма

 

 

Для формирования кодовой комбинации будем использовать генераторный многочлен вида: 1(+)у(+)у³. Где (+) – операция "суммирование" для той системы исчисления, в которой записано кодовое слово (в данном случае – кодовое слово есть двоичный код, а следовательно используем бинарную систему счисления).

Такому многочлену будет соответствовать следующая схема аппаратной реализации (рис. 1):

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1

 

Число ячеек соответствует степени многочлена (в данном случае 3). Многочлен можно представить в виде Р(у)=L0*1(+)L1*у(+)L2*0(+)L3*у³, где Li – коэффициент при члене в степени i. Каждая ячейка А1…А3 может иметь состояние 1 или 0. Суммирование осуществляется по модулю 2.

Алгоритм заключается в следующем:

На первой итерации все ячейки имеют состояние 0. На вход подается двоичная последовательность (например 1101). А1 получает значение первого члена входной последовательности (1). Т.о. на сумматор подается комбинация 100. На выход идет 1 (т.к. в 1+0+0=1). На следующей итерации А1 получает значение второго члена (1), А2 получает значение ячейки А1 с предыдущей итерации(1). На сумматоре 110, на выходе 0. Аналогично, на 3-ей итерации: А1=0, А2=1, А3=1, SUM=0. На 4-ой: А1=1, А2=0, А3=1, SUM=0. Таким образом мы получили проверочную кодовую комбинацию 1000.

 

Передача кода происходит так:

Сторона-передатчик, используя известный генераторный многочлен Р(у) вычисляет проверочную кодовую комбинацию и присоединяет ее "в хвост" передаваемому коду. Сторона-приемник, получив кодовую комбинацию, отбрасывает "хвост", а для "полезного" кода вычисляет проверочную кодовую комбинацию, используя тот же многочлен Р(у). Если принятая и вычисленная кодовые комбинации отличаются друг от друга, то при передачи возникла ошибка.

 

Проиллюстрируем кодом программы (Pascal):

unit main;

 

//вычисление проверочного "хвоста":

function Crc(sin:string):

string; //входная последовательность

var

sout: string[4]; //выходная строка

sl1,                                //первый член

sl2,         //второй член

sl3 :char;       //третий член

i: integer;      //счетчик

begin

 

sl1:='0';

sl2:='0';

sl3:='0';

 

for i:=1 to 4 do

    begin

    if i>2 then sl3:=sl2;

    if i>1 then sl2:=sl1;

    sl1:=sin[i];

    if (strtoint(sl1)+strtoint(sl2)+strtoint(sl3)=3) then

       sout:=sout+'1';

    if (strtoint(sl1)+strtoint(sl2)+strtoint(sl3)=2) then

       sout:=sout+'0';

    if (strtoint(sl1)+strtoint(sl2)+strtoint(sl3)=1) then

       sout:=sout+'1';

    if (strtoint(sl1)+strtoint(sl2)+strtoint(sl3)=0) then

       sout:=sout+'0';

    end;

Crc:=sout;

end;

 

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

procedure ButtonDecodeClick(Sender: TObject);

var SBuf1, SBuf2: string[8]; //буферы обмена строк

    i:            integer;      //счетчик

begin

SBuf1:=EditCoded.Text;

SBuf2:='0000';

SBuf2[1]:=SBuf1[5];

SBuf2[2]:=SBuf1[6];

SBuf2[3]:=SBuf1[7];

SBuf2[4]:=SBuf1[8];

if crc(SBuf1)=SBuf2 then

        begin

        EditRez.Text:='Все нормально.';

        EditDecoded.Text:=SBuf1;

        end

        else

        EditRez.Text:='Обнаружена ошибка!';

end;

end.

 

(С) МорокЪ 2004