Приложение 2 Листинг программы
Модуль программного комплекса, реализующего построение поля , введение основных операций в этом поле, вычисление значения произвольного многочлена в любой точке поля, вычисление прямого и обратного ДПФ,ОДПФ, трехмерного преобразования Фурье и БПФ длин 255,3,5,17,15,51,85, кодирование вектора несистематическим кодом Рида-Соломона.
program GF2_8;
{$APPTYPE CONSOLE}
uses
SysUtils;
const n=255;
n1=8;
type m = packed array [1..n1] of char;
type Gal = array [0..n] of m;
type vect= array [0..n-1] of m;
type D3vect=array [0..2] of m;
type D5vect=array [0..4] of m;
type D17vect=array [0..16] of m;
type multPol=array [0..6] of m;
type deg3Pol=array [0..3] of m;
type degBig=array [0..18] of m;
type deg15Pol=array [0..15] of m;
type D85vect=array [0..84] of m;
type D51vect=array [0..50] of m;
type D15vect=array [0..14] of m;
//-----------------------
function plus(a,b:m):m;
var i: integer;
begin
for i:=1 to 8 do
if a[i]<>b[i] then plus[i]:='1'
else plus[i]:='0';
end;
//-----------------------
function LogZ(a:m; G:Gal): integer;
var i: integer;
label 1;
begin
if a='00000000' then LogZ:=-1 else begin
for i:=0 to n-1 do
if a=G[i] then begin LogZ:=i; goto 1; end;
end;
1:end;
//------------------------
function expZ(k: integer; A:Gal): m;
begin
if k=-1 then expZ:='00000000'
else
expZ:=A[k];
end;
//-----------------------
function mult(a,b:m; G:Gal):m;
var i,j,Log: integer;
begin
i:=LogZ(a,G);
j:=LogZ(b,G);
if (i=-1)or(j=-1) then mult:='00000000'
else begin Log:=(i+j) mod 255
mult:=expZ(Log,G);
end;
end;
//-----------------------
procedure Generate(var A:Gal);
var C7: m;
i,j:integer;
c:char;
fl: boolean;
begin
A[0]:='00000001';
C7:='00011101';
fl := false;
for i:= 1 to n do
begin
c:=A[i-1,1];
if c = '1' then fl := true;
for j:=1 to 8 do
A[i,j]:=A[i-1,j+1];
A[i,8]:='0';
if fl = true then begin
for j := 1 to n1 do
if A[i, j] <> C7[j] then A[i, j] :='1' else A[i, j] := '0';
fl:=false;
end;
end;
end;
//----------------------
function powZ(a:m; i:integer; G:gal):m;
var k,t: integer;
begin
if a='00000000' then powZ:='00000000' else begin //0^a=0
k:=LogZ(a,G);
t:=k*i mod 255;
powZ:=expZ(t,G);
end;
end;
//--------------------------------------------------
function dim3FUR(c:vect;G:gal):vect;
var i,j,k,t,t1,t2,t3: integer;
A,f3,f5,f17: array[0..16,0..4,0..2] of m;
temp,su,D,DD: m; it: integer;
begin
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
su:='00000000';
for t:=0 to 2 do begin
DD:=powZ(G[85],t*k,G);
temp:=mult(A[i,j,t],DD,G);
su:=plus(su,temp);
end;
f3[i,j,k]:=su;
end;
for i:=0 to 16 do
for k:=0 to 2 do
for j:=0 to 4 do begin
su:='00000000';
for t:=0 to 4 do begin
DD:=powZ(G[51],t*j,G);
temp:=mult(f3[i,t,k],DD,G);
su:=plus(su,temp);
end;
f5[i,j,k]:=su;
end;
for j:=0 to 4 do
for k:=0 to 2 do
for i:=0 to 16 do begin
su:='00000000';
for t:=0 to 16 do begin
DD:=powZ(G[120],t*i,G);
temp:=mult(f5[t,j,k],DD,G);
su:=plus(su,temp);
end;
f17[i,j,k]:=su;
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do
dim3FUR[ (85*k+51*j+120*i) mod 255]:=f17[i,j,k];
end;
//-------------------------------------------------------------
function DPF256(c:vect;G:gal):vect;
var i,j: integer;
temp,r:m;
begin
for j:=0 to n-1 do begin
r:='00000000';
for i:=0 to n-1 do begin
temp:=mult(c[i],powZ(G[1],i*j,G),G);
r:=plus(temp,r);
end;
DPF256[j]:=r;
end;
end;
//-------------------------------------------------------------
function DPF256back(c:vect;G:gal):vect;
var i,j: integer;
temp,r:m;
begin
for j:=0 to n-1 do begin
r:='00000000';
for i:=0 to n-1 do begin
temp:=mult(c[i],powZ(G[254],i*j,G),G);
r:=plus(temp,r);
end;
DPF256back[j]:=r;
end;
end;
//------------------------------------------------------------------
function DPF17(c:D17vect;G:gal):d17vect
var i,j: integer;
temp,r:m;
begin
for j:=0 to 16 do begin
r:='00000000';
for i:=0 to 16 do begin
temp:=mult(c[i],powZ(G[120],i*j,G),G);
r:=plus(temp,r);
end;
DPF17[j]:=r;
end;
end;
//------------------------------------------------------------------
function DPF17back(c:D17vect;G:gal):d17vect;
var i,j: integer;
temp,r:m;
begin
for j:=0 to 16 do begin
r:='00000000';
for i:=0 to 16 do begin
temp:=mult(c[i],powZ(G[135],i*j,G),G);
r:=plus(temp,r);
end;
DPF17back[j]:=r;
end;
end;
//------------------------------------------------------------------
function DPF3(c:D3vect;G:gal):d3vect;
var i,j: integer;
temp,r:m;
begin
for j:=0 to 2 do begin
r:='00000000';
for i:=0 to 2 do begin
temp:=mult(c[i],powZ(G[85],i*j,G),G);
r:=plus(temp,r);
end;
DPF3[j]:=r;
end;
end;
//------------------------------------------------------------------
function DPF3back(c:D3vect;G:gal):d3vect;
var i,j: integer;
temp,r:m;
begin
for j:=0 to 2 do begin
r:='00000000';
for i:=0 to 2 do begin
temp:=mult(c[i],powZ(G[170],i*j,G),G);
r:=plus(temp,r);
end;
DPF3back[j]:=r;
end;
end;
//------------------------------------------------------------------
function DPF5(c:D5vect;G:gal):d5vect;
var i,j: integer;
temp,r:m;
begin
for j:=0 to 4 do begin
r:='00000000';
for i:=0 to 4 do begin
temp:=mult(c[i],powZ(G[51],i*j,G),G);
r:=plus(temp,r);
end;
DPF5[j]:=r;
end;
end;
//------------------------------------------------------------------
//------------------------------------------------------------------
function DPF5back(c:D5vect;G:gal):d5vect;
var i,j: integer;
temp,r:m;
begin
for j:=0 to 4 do begin
r:='00000000';
for i:=0 to 4 do begin
temp:=mult(c[i],powZ(G[204],i*j,G),G);
r:=plus(temp,r);
end;
DPF5back[j]:=r;
end;
end;
//------------------------------------------------------------------
function RootOfPol(pol:vect;root:m; G:gal):m;
var temp_v: vect;
sum: m;
i: integer;
begin
temp_v[0]:=pol[0];
for i:=1 to 254 do
if pol[i]<>'00000000' then
temp_v[i]:=mult(pol[i],powZ(root,i,G),G)
else temp_v[i]:='00000000';
sum:='00000000';
for i:=0 to 254 do
sum:=plus(sum,temp_v[i]);
RootOfPol:=sum;
end;
//-------------------------------------------------------------------
function RS_Encrypt(inf: vect; G:Gal):vect;
var i: integer;
begin
for i:=0 to 254 do
RS_Encrypt[i]:=RootOfPol(inf,G[255-i],G);
end;
//--------------------------------------------------------------------
procedure waste(DateTime,DateTime1:TDateTime);
var Hour,Min,Sec,Msec,Hour1,Min1,Sec1,Msec1:word;
Ms,sss:integer;
begin
decodetime(DateTime,Hour,Min,Sec,Msec); decodetime(DateTime1,Hour1,Min1,Sec1,Msec1);
ms:=Msec1-msec;
sss:=sec1-sec;
if ms<0 then begin
MS:=ms+1000;
SSS:=sss-1;
end;
writeln('algorithm waste is ',sss,' seconds, and ',ms{mod 65000},' milliseconds');
end;
//--------------------------------------------------------------------
function Dim3RPF(h:D3vect;G:Gal):D3vect;
var s1,m1,s2,tt: m;
begin
s1:=plus(h[1],h[2]);
m1:=mult(G[85],s1,G);
tt:=plus(h[0],s1);
s2:=plus(tt,m1);
Dim3RPF[1]:=plus(s2,h[1]);
Dim3RPF[2]:=plus(s2,h[2]);
Dim3RPF[0]:=tt;
end;
//--------------------------------------------------------------------
function Dim3RPFback(h:D3vect;G:Gal):D3vect;
var s1,m1,s2,tt: m;
begin
s1:=plus(h[1],h[2]);
m1:=mult(G[170],s1,G);
tt:=plus(h[0],s1);
s2:=plus(tt,m1);
Dim3RPFback[1]:=plus(s2,h[1]);
Dim3RPFback[2]:=plus(s2,h[2]);
Dim3RPFback[0]:=tt;
end;
//--------------------------------------------------------------------
function Dim5RPF(h:D5vect;G:Gal):D5vect;
var s1,s2,s3,s4,s5,m1,m2,m3,m4,m5,s6,s7,s8,s9,s10,s11,s12,tt: m;
begin
s1:=plus(h[2],h[3]);
s2:=plus(h[1],h[4]);
s3:=plus(h[1],h[3]);
s4:=plus(h[2],h[4]);
s5:=plus(s1,s2);
tt:=plus(s5,h[0]);
Dim5RPF[0]:=tt;
m1:=mult(plus(G[0],G[153]),s5,G);
m2:=mult(plus(G[153],G[204]),s1,G);
m3:=mult(plus(G[51],G[153]),s2,G);
m4:=mult(plus(G[51],G[204]),s3,G);
m5:=mult(plus(G[51],G[204]),s4,G);
s6:=plus(tt,m1);
s7:=plus(s6,m2);
s8:=plus(s6,m3);
s9:=plus(m5,h[2]);
s10:=plus(m4,h[1]);
s11:=plus(m5,h[4]);
s12:=plus(m4,h[3]);
Dim5RPF[1]:=plus(s8,s9);
Dim5RPF[2]:=plus(s7,s10);
Dim5RPF[3]:=plus(s7,s11);
Dim5RPF[4]:=plus(s8,s12);
end;
//--------------------------------------------------------------------
//--------------------------------------------------------------------
function Dim5RPFback(h:D5vect;G:Gal):D5vect;
var s1,s2,s3,s4,s5,m1,m2,m3,m4,m5,s6,s7,s8,s9,s10,s11,s12,tt: m;
begin
s1:=plus(h[2],h[3]);
s2:=plus(h[1],h[4]);
s3:=plus(h[1],h[3]);
s4:=plus(h[2],h[4]);
s5:=plus(s1,s2);
tt:=plus(s5,h[0]);
Dim5RPFback[0]:=tt;
m1:=mult(plus(G[0],G[102]),s5,G);
m2:=mult(plus(G[102],G[51]),s1,G);
m3:=mult(plus(G[204],G[102]),s2,G);
m4:=mult(plus(G[204],G[51]),s3,G);
m5:=mult(plus(G[204],G[51]),s4,G);
s6:=plus(tt,m1);
s7:=plus(s6,m2);
s8:=plus(s6,m3);
s9:=plus(m5,h[2]);
s10:=plus(m4,h[1]);
s11:=plus(m5,h[4]);
s12:=plus(m4,h[3]);
Dim5RPFback[1]:=plus(s8,s9);
Dim5RPFback[2]:=plus(s7,s10);
Dim5RPFback[3]:=plus(s7,s11);
Dim5RPFback[4]:=plus(s8,s12);
end;
//----------------------------
function multVaryOnVary(R,B:deg3Pol; G:Gal): multPol;
var s1,s2,s3,s4,s5,s6,m1,m2,m3,m4,s7,m5,m6,m7: m;
h0,h1,h2,h3,h4,h5,h6: m;
begin
s1:=plus(r[0],r[1]);
s2:=plus(r[0],r[2]); //s2:=plus(r[0],r[2]);
s3:=plus(r[1],r[3]);
s4:=plus(s2,s3);
s5:=plus(s4,s1);
h0:=mult(r[0],b[0],G);
m1:=mult(s1,plus(b[0],b[1]),G);
m2:=mult(r[1],b[1],G);
s6:=plus(h0,m2);
h1:=plus(s6,m1);
m3:=mult(r[2],b[2],G);
h6:=mult(r[3],b[3],G);
m4:=mult(s2,plus(b[0],b[2]),G);
h2:=plus(s6,plus(m3,m4));
s7:=plus(m3,h6);
m5:=mult(s3,plus(b[1],b[3]),G);
m6:=mult(s5,plus(b[2],b[3]),G);
m7:=mult(s4,plus(plus(b[0],b[1]),plus(b[2],b[3])),G);
h5:=plus(s7,m6);
h4:=plus(s7,plus(m2,m5));
h3:=plus(plus(h1,h5),plus(m4,plus(m5,m7)));
multVaryOnVary[0]:=h0;
multVaryOnVary[1]:=h1;
multVaryOnVary[2]:=h2;
multVaryOnVary[3]:=h3;
multVaryOnVary[4]:=h4;
multVaryOnVary[5]:=h5;
multVaryOnVary[6]:=h6;
end;
//--------------------------
function multFixonVary(r:deg3Pol;G:Gal):multPol;
begin
multFixonVary[0]:=plus(r[0],mult(r[0],G[85],G));
multFixonVary[1]:=plus(plus(r[0],r[1]),mult(r[1],G[85],G));
multFixonVary[2]:=plus(plus(r[1],r[2]),mult(plus(r[0],r[2]),G[85],G));
multFixonVary[3]:=plus(plus(r[0],r[2]),plus(r[3],mult(plus(r[1],r[3]),G[85],G)));
multFixonVary[4]:=plus(plus(r[1],r[3]),mult(r[2],G[85],G));
multFixonVary[5]:=plus(r[2],mult(r[3],G[85],G));
multFixonVary[6]:=r[3];
end;
//----------------------------------
function sumBigPol(H,P:degBig):degBig;
var i: integer;
begin
for i:=0 to 18 do
sumBigPol[i]:=plus(H[i],P[i]);
end;
//--------------------------
function sum3Pol(H,P:Deg3Pol):deg3Pol;
var i: integer;
begin
for i:=0 to 3 do
sum3Pol[i]:=plus(H[i],P[i]);
end;
//----------------------
function sumSmallPol(H,P:multPol):multPol;
var i: integer;
begin
for i:=0 to 6 do
sumSmallPol[i]:=plus(H[i],P[i]);
end;
//--------------------
function sum17Pol(H,P:D17Vect):D17Vect;
var i: integer;
begin
for i:=0 to 16 do
sum17Pol[i]:=plus(H[i],P[i]);
end;
//-------------------
function PxmoDD(P:DegBig): deg15Pol;
var i: integer;
begin
for i:=15 downto 3 do
PxmoDD[i]:=P[i];
PxmoDD[2]:=plus(P[2],P[18]);
PxmoDD[1]:=plus(P[1],P[17]);
PxmoDD[0]:=plus(P[0],P[16]);
end;
//---------------------
function mult15to15deg(U:deg15Pol;G:Gal):deg15pol;
var W:deg15pol; i:integer;
U1,U2,U3,U4:deg3Pol;
W1,W2,W3,W4:deg3Pol;
F1,F2,F3,F4:multPol;
Temp1,Temp3,Temp5,Temp6,Temp7,temp4:multPol;
Temp2:Deg3Pol;
temp8,temp9,temp10:multPol;
temp11,temp12,temp13,temp14,temp15,temp16:multPol;
temp17,temp18,temp19,temp20,temp21,temp22,temp23,temp24:multPol;
vec1,vec2,vec3,vec4:degBig;
FullPol: degBig;
begin
w[0]:=powZ(G[120],8,G);
w[1]:=powZ(G[120],6,G);
w[2]:=powZ(G[120],13,G);
w[3]:=powZ(G[120],14,G);
w[4]:=powZ(G[120],2,G);
w[5]:=powZ(G[120],10,G);
w[6]:=powZ(G[120],16,G);
w[7]:=powZ(G[120],12,G);
w[8]:=powZ(G[120],9,G);
w[9]:=powZ(G[120],11,G);
w[10]:=powZ(G[120],4,G);
w[11]:=powZ(G[120],3,G);
w[12]:=powZ(G[120],15,G);
w[13]:=powZ(G[120],7,G);
w[14]:=powZ(G[120],1,G);
w[15]:=powZ(G[120],5,G);
U1[0]:=U[0];
U1[1]:=U[1];
U1[2]:=U[2];
U1[3]:=U[3];
U2[0]:=U[4];
U2[1]:=U[5];
U2[2]:=U[6];
U2[3]:=U[7];
U3[0]:=U[8];
U3[1]:=U[9];
U3[2]:=U[10];
U3[3]:=U[11];
U4[0]:=U[12];
U4[1]:=U[13];
U4[2]:=U[14];
U4[3]:=U[15];
W1[0]:=W[0];
W1[1]:=W[1];
W1[2]:=W[2];
W1[3]:=W[3];
W2[0]:=W[4];
W2[1]:=W[5];
W2[2]:=W[6];
W2[3]:=W[7];
W3[0]:=W[8];
W3[1]:=W[9];
W3[2]:=W[10];
W3[3]:=W[11];
W4[0]:=W[12];
W4[1]:=W[13];
W4[2]:=W[14];
W4[3]:=W[15];
temp1:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G); temp2:=sum3Pol(sum3Pol(U1,U2),sum3Pol(U3,U4));
temp3:=multVaryOnVary(temp2,W2,G);
temp4:=sumSmallPol(temp1,temp3);
temp5:=multVaryOnVary(sum3Pol(U1,U3),sum3Pol(W2,W3),G);
temp6:=multFixonVary(U2,G);
temp7:=sumSmallPol(temp4,temp5);
F1:=sumSmallPol(temp7,temp6);
temp8:=multVaryOnVary(sum3Pol(W1,W3),temp2,G);
temp9:=sumSmallPol(temp8,F1);
temp10:=multFixOnVary(sum3Pol(U2,U4),G);
F3:=sumSmallPol(temp10,temp9);
temp11:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G);
temp12:=multVaryOnVary(temp2,sum3Pol(W1,sum3Pol(W2,W3)),G);
temp13:=sumSmallPol(temp11,temp12);
temp14:=multVaryOnVary(sum3Pol(U4,U2),sum3Pol(W1,W2),G);
temp15:=multFixOnVary(U3,G);
temp16:=sumSmallPol(temp14,Temp15);
F2:=sumSmallPol(temp16,temp13);
temp17:=multFixOnVary(temp2,G);
temp18:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G);
temp19:=sumSmallPol(temp17,temp18);
temp20:=multVaryOnVary(temp2,W2,G);
temp21:=multVaryOnVary(sum3Pol(U2,U4),sum3Pol(W3,W4),G);
temp22:=sumSmallPol(temp21,temp20);
temp23:=sumSmallPol(temp22,temp19);
temp24:=multFixOnVary(U3,G);
F4:=sumSmallPol(temp24,temp23);
for i:=0 to 18 do begin
vec1[i]:='00000000';
vec2[i]:='00000000';
vec3[i]:='00000000';
vec4[i]:='00000000';
end;
vec1[0]:=F1[0];
vec1[1]:=F1[1];
vec1[2]:=F1[2];
vec1[3]:=F1[3];
vec1[4]:=F1[4];
vec1[5]:=F1[5];
vec1[6]:=F1[6];
//*x^4
vec2[4]:=F2[0];
vec2[5]:=F2[1];
vec2[6]:=F2[2];
vec2[7]:=F2[3];
vec2[8]:=F2[4];
vec2[9]:=F2[5];
vec2[10]:=F2[6];
//*x^8
vec3[8]:=F3[0];
vec3[9]:=F3[1];
vec3[10]:=F3[2];
vec3[11]:=F3[3];
vec3[12]:=F3[4];
vec3[13]:=F3[5];
vec3[14]:=F3[6];
//*x^12
vec4[12]:=F4[0];
vec4[13]:=F4[1];
vec4[14]:=F4[2];
vec4[15]:=F4[3];
vec4[16]:=F4[4];
vec4[17]:=F4[5];
vec4[18]:=F4[6];
FullPol:=sumBigPol(sumBigPol(vec1,vec2),sumBigPol(vec3,vec4));
mult15to15deg:=PxmoDD(FullPol);
end;
//-------------------
function mult15to15degobr(U:deg15Pol;G:Gal):deg15pol;
var W:deg15pol; i:integer;
U1,U2,U3,U4:deg3Pol;
W1,W2,W3,W4:deg3Pol;
F1,F2,F3,F4:multPol;
Temp1,Temp3,Temp5,Temp6,Temp7,temp4:multPol;
Temp2:Deg3Pol;
temp8,temp9,temp10:multPol;
temp11,temp12,temp13,temp14,temp15,temp16:multPol;
temp17,temp18,temp19,temp20,temp21,temp22,temp23,temp24:multPol;
vec1,vec2,vec3,vec4:degBig;
FullPol: degBig;
begin
w[0]:=powZ(G[135],8,G);
w[1]:=powZ(G[135],6,G);
w[2]:=powZ(G[135],13,G);
w[3]:=powZ(G[135],14,G);
w[4]:=powZ(G[135],2,G);
w[5]:=powZ(G[135],10,G);
w[6]:=powZ(G[135],16,G);
w[7]:=powZ(G[135],12,G);
w[8]:=powZ(G[135],9,G);
w[9]:=powZ(G[135],11,G);
w[10]:=powZ(G[135],4,G);
w[11]:=powZ(G[135],3,G);
w[12]:=powZ(G[135],15,G);
w[13]:=powZ(G[135],7,G);
w[14]:=powZ(G[135],1,G);
w[15]:=powZ(G[135],5,G);
U1[0]:=U[0];
U1[1]:=U[1];
U1[2]:=U[2];
U1[3]:=U[3];
U2[0]:=U[4];
U2[1]:=U[5];
U2[2]:=U[6];
U2[3]:=U[7];
U3[0]:=U[8];
U3[1]:=U[9];
U3[2]:=U[10];
U3[3]:=U[11];
U4[0]:=U[12];
U4[1]:=U[13];
U4[2]:=U[14];
U4[3]:=U[15];
W1[0]:=W[0];
W1[1]:=W[1];
W1[2]:=W[2];
W1[3]:=W[3];
W2[0]:=W[4];
W2[1]:=W[5];
W2[2]:=W[6];
W2[3]:=W[7];
W3[0]:=W[8];
W3[1]:=W[9];
W3[2]:=W[10];
W3[3]:=W[11];
W4[0]:=W[12];
W4[1]:=W[13];
W4[2]:=W[14];
W4[3]:=W[15];
temp1:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G); temp2:=sum3Pol(sum3Pol(U1,U2),sum3Pol(U3,U4));
temp3:=multVaryOnVary(temp2,W2,G);
temp4:=sumSmallPol(temp1,temp3);
temp5:=multVaryOnVary(sum3Pol(U1,U3),sum3Pol(W2,W3),G);
temp6:=multFixonVary(U2,G);
temp7:=sumSmallPol(temp4,temp5);
F1:=sumSmallPol(temp7,temp6);
temp8:=multVaryOnVary(sum3Pol(W1,W3),temp2,G);
temp9:=sumSmallPol(temp8,F1);
temp10:=multFixOnVary(sum3Pol(U2,U4),G);
F3:=sumSmallPol(temp10,temp9);
temp11:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G);
temp12:=multVaryOnVary(temp2,sum3Pol(W1,sum3Pol(W2,W3)),G);
temp13:=sumSmallPol(temp11,temp12);
temp14:=multVaryOnVary(sum3Pol(U4,U2),sum3Pol(W1,W2),G); temp15:=multFixOnVary(U3,G);
temp16:=sumSmallPol(temp14,Temp15);
F2:=sumSmallPol(temp16,temp13);
temp17:=multFixOnVary(temp2,G);
temp18:=multVaryOnVary(sum3Pol(U1,U2),sum3Pol(W1,W3),G);
temp19:=sumSmallPol(temp17,temp18);
temp20:=multVaryOnVary(temp2,W2,G);
temp21:=multVaryOnVary(sum3Pol(U2,U4),sum3Pol(W3,W4),G);
temp22:=sumSmallPol(temp21,temp20);
temp23:=sumSmallPol(temp22,temp19);
temp24:=multFixOnVary(U3,G);
F4:=sumSmallPol(temp24,temp23);
for i:=0 to 18 do begin
vec1[i]:='00000000';
vec2[i]:='00000000';
vec3[i]:='00000000';
vec4[i]:='00000000';
end;
//*x^0
vec1[0]:=F1[0];
vec1[1]:=F1[1];
vec1[2]:=F1[2];
vec1[3]:=F1[3];
vec1[4]:=F1[4];
vec1[5]:=F1[5];
vec1[6]:=F1[6];
//*x^4
vec2[4]:=F2[0];
vec2[5]:=F2[1];
vec2[6]:=F2[2];
vec2[7]:=F2[3];
vec2[8]:=F2[4];
vec2[9]:=F2[5];
vec2[10]:=F2[6];
//*x^8
vec3[8]:=F3[0];
vec3[9]:=F3[1];
vec3[10]:=F3[2];
vec3[11]:=F3[3];
vec3[12]:=F3[4];
vec3[13]:=F3[5];
vec3[14]:=F3[6];
//*x^12
vec4[12]:=F4[0];
vec4[13]:=F4[1];
vec4[14]:=F4[2];
vec4[15]:=F4[3];
vec4[16]:=F4[4];
vec4[17]:=F4[5];
vec4[18]:=F4[6];
FullPol:=sumBigPol(sumBigPol(vec1,vec2),sumBigPol(vec3,vec4));
mult15to15degobr:=PxmoDD(FullPol);
end;
//*****************************************************************************
function Dim17RPF(v:D17Vect; G: Gal):D17Vect;
var i: integer;
firstV: D17Vect;
secondV: deg15pol;
item: D17Vect;
res: D17Vect;
U: deg15pol;
s:m;
begin
s:='00000000';
for i:=0 to 16 do
s:=plus(s,v[i]);
FirstV[0]:=s;
for i:=1 to 16 do
FirstV[i]:=v[0];
U[0]:=v[5];
U[1]:=v[1];
U[2]:=v[7];
U[3]:=v[15];
U[4]:=v[3];
U[5]:=v[4];
U[6]:=v[11];
U[7]:=v[9];
U[8]:=v[12];
U[9]:=v[16];
U[10]:=v[10];
U[11]:=v[2];
U[12]:=v[14];
U[13]:=v[13];
U[14]:=v[6];
U[15]:=v[8];
secondV:=mult15to15deg(U,G);
item[0]:='00000000';
for i:=1 to 16 do
item[i]:=secondV[i-1];
res:=sum17Pol(item,firstV);
Dim17RPF[0]:=res[0];
Dim17RPF[5]:=res[1];
Dim17RPF[8]:=res[2];
Dim17RPF[6]:=res[3];
Dim17RPF[13]:=res[4];
Dim17RPF[14]:=res[5];
Dim17RPF[2]:=res[6];
Dim17RPF[10]:=res[7];
Dim17RPF[16]:=res[8];
Dim17RPF[12]:=res[9];
Dim17RPF[9]:=res[10];
Dim17RPF[11]:=res[11];
Dim17RPF[4]:=res[12];
Dim17RPF[3]:=res[13];
Dim17RPF[15]:=res[14];
Dim17RPF[7]:=res[15];
Dim17RPF[1]:=res[16];
end;
//*****************************************************************************
function Dim17RPFobr(v:D17Vect; G: Gal):D17Vect;
var i: integer;
firstV: D17Vect;
secondV: deg15pol;
item: D17Vect;
res: D17Vect;
U: deg15pol;
s:m;
begin
s:='00000000';
for i:=0 to 16 do
s:=plus(s,v[i]);
FirstV[0]:=s;
for i:=1 to 16 do
FirstV[i]:=v[0];
U[0]:=v[5];
U[1]:=v[1];
U[2]:=v[7];
U[3]:=v[15];
U[4]:=v[3];
U[5]:=v[4];
U[6]:=v[11];
U[7]:=v[9];
U[8]:=v[12];
U[9]:=v[16];
U[10]:=v[10];
U[11]:=v[2];
U[12]:=v[14];
U[13]:=v[13];
U[14]:=v[6];
U[15]:=v[8];
secondV:=mult15to15degobr(U,G);
item[0]:='00000000';
for i:=1 to 16 do
item[i]:=secondV[i-1];
res:=sum17Pol(item,firstV);
Dim17RPFobr[0]:=res[0];
Dim17RPFobr[5]:=res[1];
Dim17RPFobr[8]:=res[2];
Dim17RPFobr[6]:=res[3];
Dim17RPFobr[13]:=res[4];
Dim17RPFobr[14]:=res[5];
Dim17RPFobr[2]:=res[6];
Dim17RPFobr[10]:=res[7];
Dim17RPFobr[16]:=res[8];
Dim17RPFobr[12]:=res[9];
Dim17RPFobr[9]:=res[10];
Dim17RPFobr[11]:=res[11];
Dim17RPFobr[4]:=res[12];
Dim17RPFobr[3]:=res[13];
Dim17RPFobr[15]:=res[14];
Dim17RPFobr[7]:=res[15];
Dim17RPFobr[1]:=res[16];
end;
//--------------------
function RPF256(c:vect;G:Gal):vect;
var i,j,k,t: integer;
A,f3,f5,f17: array[0..16,0..4,0..2] of m;
temp:D3vect;
temp1:D5Vect;
fur2:D5vect;
fur1:D3Vect;
fur3:D17Vect;
temp2:D17Vect;
s:m;
r:integer;
begin
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
temp[k]:=A[i,j,k];
if k=2 then begin
fur1:=dim3RPF(temp,G);
for t:=0 to 2 do
f3[i,j,t]:=fur1[t];
end;
end;
for i:=0 to 16 do
for k:=0 to 2 do
for j:=0 to 4 do begin
temp1[j]:=f3[i,j,k];
if j=4 then begin
fur2:=dim5RPF(temp1,G);
for t:=0 to 4 do
f5[i,t,k]:=fur2[t];
end;
end;
for j:=0 to 4 do
for k:=0 to 2 do
for i:=0 to 16 do begin
temp2[i]:=f5[i,j,k];
if i=16 then begin
fur3:=dim17RPF(temp2,G);
for t:=0 to 16 do
f17[t,j,k]:=fur3[t];
end;
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do
RPF256[ (85*k+51*j+120*i) mod 255]:=f17[i,j,k];
end;
//-----------------------------------------------------------------------------
function RPF256back(c:vect;G:Gal):vect;
var i,j,k,t: integer;
A,f3,f5,f17: array[0..16,0..4,0..2] of m;
temp:D3vect;
temp1:D5Vect;
fur2:D5vect;
fur1:D3Vect;
fur3:D17Vect;
temp2:D17Vect;
s:m;
r:integer;
begin
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
temp[k]:=A[i,j,k];
if k=2 then begin
fur1:=dim3RPFback(temp,G);
for t:=0 to 2 do
f3[i,j,t]:=fur1[t];
end;
end;
for i:=0 to 16 do
for k:=0 to 2 do
for j:=0 to 4 do begin
temp1[j]:=f3[i,j,k];
if j=4 then begin
fur2:=dim5RPFback(temp1,G);
for t:=0 to 4 do
f5[i,t,k]:=fur2[t];
end;
end;
for j:=0 to 4 do
for k:=0 to 2 do
for i:=0 to 16 do begin
temp2[i]:=f5[i,j,k];
if i=16 then begin
fur3:=dim17RPFobr(temp2,G);
for t:=0 to 16 do
f17[t,j,k]:=fur3[t];
end;
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do
RPF256back[ (85*k+51*j+120*i) mod 255]:=f17[i,j,k];
end;
//-----------------------------------------------------------------------------
function DPF51(c:D51vect;G:gal):d51vect;
var i,j: integer;
temp,r:m;
ct,cs:vect;
begin
for i:=0 to n-1 do begin
if i mod 5=0 then ct[i]:=c[round(i/5)]
Else ct[i]:='00000000';
end;
for j:=0 to n-1 do begin
r:='00000000';
for i:=0 to n-1 do begin
temp:=mult(ct[i],powZ(G[1],i*j,G),G);
r:=plus(temp,r);
end;
cs[j]:=r;
end;
for i:=0 to n-1 do
if i mod 5=0 then dpf51[round(i/5)]:=cs[i];
end;
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
function DPF51back(c:D51vect;G:gal):d51vect;
var i,j: integer;
temp,r:m;
ct,cs:vect;
begin
for i:=0 to n-1 do begin
if i mod 5=0 then ct[i]:=c[round(i/5)]
Else ct[i]:='00000000';
end;
for j:=0 to n-1 do begin
r:='00000000';
for i:=0 to n-1 do begin
temp:=mult(ct[i],powZ(G[254],i*j,G),G);
r:=plus(temp,r);
end;
cs[j]:=r;
end;
for i:=0 to n-1 do
if i mod 5=0 then dpf51back[round(i/5)]:=cs[i];
end;
//-----------------------------------------------------------------------------
function DPF15(c:D15vect;G:gal):d15vect;
var i,j: integer;
temp,r:m;
ct,cs:vect;
begin
for i:=0 to n-1 do begin
if i mod 17=0 then ct[i]:=c[round(i/17)]
Else ct[i]:='00000000';
end;
for j:=0 to n-1 do begin
r:='00000000';
for i:=0 to n-1 do begin
temp:=mult(ct[i],powZ(G[1],i*j,G),G);
r:=plus(temp,r);
end;
cs[j]:=r;
end;
for i:=0 to n-1 do
if i mod 17=0 then dpf15[round(i/17)]:=cs[i];
end;
//-----------------------------------------------------------------------------
function DPF15back(c:D15vect;G:gal):d15vect;
var i,j: integer;
temp,r:m;
ct,cs:vect;
begin
for i:=0 to n-1 do begin
if i mod 17=0 then ct[i]:=c[round(i/17)]
Else ct[i]:='00000000';
end;
for j:=0 to n-1 do begin
r:='00000000';
for i:=0 to n-1 do begin
temp:=mult(ct[i],powZ(G[254],i*j,G),G);
r:=plus(temp,r);
end;
cs[j]:=r;
end;
for i:=0 to n-1 do
if i mod 17=0 then dpf15back[round(i/17)]:=cs[i];
end;
//--------------------
function RPF85(cd:d85vect;G:Gal):d85vect;
var i,j,k,t: integer;
A,f5,f17: array[0..16,0..4,0..2] of m;
temp1:D5Vect;
fur2:D5vect;
fur3:D17Vect;
temp2:D17Vect;
c:vect;
cr:vect;
begin
for i:=0 to n-1 do begin
if i mod 3=0 then c[i]:=cd[round(i/3)]
Else c[i]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
f5[i,j,k]:='00000000';
f17[i,j,k]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];
end;
for i:=0 to 16 do
for j:=0 to 4 do begin
temp1[j]:=A[i,j,0];
if j=4 then begin
fur2:=dim5RPF(temp1,G);
for t:=0 to 4 do
f5[i,t,0]:=fur2[t];
end;
end;
for j:=0 to 4 do
for i:=0 to 16 do begin
temp2[i]:=f5[i,j,0];
if i=16 then begin
fur3:=dim17RPF(temp2,G);
for t:=0 to 16 do
f17[t,j,0]:=fur3[t];
end;
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do
cr[ (85*k+51*j+120*i) mod 255]:=f17[i,j,k];
for i:=0 to n-1 do
if i mod 3=0 then rpf85[round(i/3)]:=cr[i];
end;
//-----------------------------------------------------------------------------
function RPF85back(cd:d85vect;G:Gal):d85vect;
var i,j,k,t: integer;
A,f5,f17: array[0..16,0..4,0..2] of m;
temp1:D5Vect;
fur2:D5vect;
fur3:D17Vect;
temp2:D17Vect;
c:vect;
cr:vect;
begin
for i:=0 to n-1 do begin
if i mod 3=0 then c[i]:=cd[round(i/3)]
Else c[i]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
f5[i,j,k]:='00000000';
f17[i,j,k]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];
end;
for i:=0 to 16 do
for j:=0 to 4 do begin
temp1[j]:=A[i,j,0];
if j=4 then begin
fur2:=dim5RPFback(temp1,G);
for t:=0 to 4 do
f5[i,t,0]:=fur2[t];
end;
end;
for j:=0 to 4 do
for i:=0 to 16 do begin
temp2[i]:=f5[i,j,0];
if i=16 then begin
fur3:=dim17RPFobr(temp2,G);
for t:=0 to 16 do
f17[t,j,0]:=fur3[t];
end;
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do
cr[ (85*k+51*j+120*i) mod 255]:=f17[i,j,k];
for i:=0 to n-1 do
if i mod 3=0 then rpf85back[round(i/3)]:=cr[i];
end;
//-----------------------------------------------------------------------------
function DPF85(c:D85vect;G:gal):d85vect;
var i,j: integer;
temp,r:m;
ct,cs:vect;
begin
for i:=0 to n-1 do begin
if i mod 3=0 then ct[i]:=c[round(i/3)]
Else ct[i]:='00000000';
end;
for j:=0 to n-1 do begin
r:='00000000';
for i:=0 to n-1 do begin
temp:=mult(ct[i],powZ(G[1],i*j,G),G);
r:=plus(temp,r);
end;
cs[j]:=r;
end;
//назад
for i:=0 to n-1 do
if i mod 3=0 then dpf85[round(i/3)]:=cs[i];
end;
//------------------------------------------------------------------------------
function DPF85back(c:D85vect;G:gal):d85vect;
var i,j: integer;
temp,r:m;
ct,cs:vect;
begin
for i:=0 to n-1 do begin
if i mod 3=0 then ct[i]:=c[round(i/3)]
Else ct[i]:='00000000';
end;
for j:=0 to n-1 do begin
r:='00000000';
for i:=0 to n-1 do begin
temp:=mult(ct[i],powZ(G[254],i*j,G),G);
r:=plus(temp,r);
end;
cs[j]:=r;
end;
//назад
for i:=0 to n-1 do
if i mod 3=0 then dpf85back[round(i/3)]:=cs[i];
end;
//--------------------
function RPF51(cd:d51vect;G:Gal):d51vect;
var i,j,k,t: integer;
A,f3,f17: array[0..16,0..4,0..2] of m;
temp:D3vect;
fur1:D3Vect;
fur3:D17Vect;
temp2:D17Vect;
c,cr:vect;
begin
for i:=0 to n-1 do begin
if i mod 5=0 then c[i]:=cd[round(i/5)]
Else c[i]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
f3[i,j,k]:='00000000';
f17[i,j,k]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];
end;
for i:=0 to 16 do
for k:=0 to 2 do begin
temp[k]:=A[i,0,k];
if k=2 then begin
fur1:=dim3RPF(temp,G);
for t:=0 to 2 do
f3[i,0,t]:=fur1[t];
end;
end;
for k:=0 to 2 do
for i:=0 to 16 do begin
temp2[i]:=f3[i,0,k];
if i=16 then begin
fur3:=dim17RPF(temp2,G);
for t:=0 to 16 do
f17[t,0,k]:=fur3[t];
end;
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do
cr[ (85*k+51*j+120*i) mod 255]:=f17[i,j,k];
for i:=0 to n-1 do
if i mod 5=0 then rpf51[round(i/5)]:=cr[i];
end;
//------------------------------------------------------------------------------
function RPF51back(cd:d51vect;G:Gal):d51vect;
var i,j,k,t: integer;
A,f3,f17: array[0..16,0..4,0..2] of m;
temp:D3vect;
fur1:D3Vect;
fur3:D17Vect;
temp2:D17Vect;
c,cr:vect;
begin
for i:=0 to n-1 do begin
if i mod 5=0 then c[i]:=cd[round(i/5)]
Else c[i]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
f3[i,j,k]:='00000000';
f17[i,j,k]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];
end;
for i:=0 to 16 do
for k:=0 to 2 do begin
temp[k]:=A[i,0,k];
if k=2 then begin
fur1:=dim3RPFback(temp,G);
for t:=0 to 2 do
f3[i,0,t]:=fur1[t];
end;
end;
for k:=0 to 2 do
for i:=0 to 16 do begin
temp2[i]:=f3[i,0,k];
if i=16 then begin
fur3:=dim17RPFobr(temp2,G);
for t:=0 to 16 do
f17[t,0,k]:=fur3[t];
end;
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do
cr[ (85*k+51*j+120*i) mod 255]:=f17[i,j,k];
for i:=0 to n-1 do
if i mod 5=0 then rpf51back[round(i/5)]:=cr[i];
end;
//--------------------
function RPF15(cd:d15vect;G:Gal):d15vect;
var i,j,k,t: integer;
A,f3,f5: array[0..16,0..4,0..2] of m;
temp:D3vect;
temp1:D5Vect;
fur2:D5vect;
fur1:D3Vect;
c,cr:vect;
begin
for i:=0 to n-1 do begin
if i mod 17=0 then c[i]:=cd[round(i/17)]
Else c[i]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
f3[i,j,k]:='00000000';
f5[i,j,k]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];
end;
for j:=0 to 4 do
for k:=0 to 2 do begin
temp[k]:=A[0,j,k];
if k=2 then begin
fur1:=dim3RPF(temp,G);
for t:=0 to 2 do
f3[0,j,t]:=fur1[t];
end;
end;
for k:=0 to 2 do
for j:=0 to 4 do begin
temp1[j]:=f3[0,j,k];
if j=4 then begin
fur2:=dim5RPF(temp1,G);
for t:=0 to 4 do
f5[0,t,k]:=fur2[t];
end;
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do
cr[ (85*k+51*j+120*i) mod 255]:=f5[i,j,k];
for i:=0 to n-1 do
if i mod 17=0 then rpf15[round(i/17)]:=cr[i];
end;
//-----------------------------------------------------------------------------
function RPF15back(cd:d15vect;G:Gal):d15vect;
var i,j,k,t: integer;
A,f3,f5: array[0..16,0..4,0..2] of m;
temp:D3vect;
temp1:D5Vect;
fur2:D5vect;
fur1:D3Vect;
c,cr:vect;
begin
for i:=0 to n-1 do begin
if i mod 17=0 then c[i]:=cd[round(i/17)]
Else c[i]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
f3[i,j,k]:='00000000';
f5[i,j,k]:='00000000';
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do begin
A[i,j,k]:=c[( 85*k+51*j+120*i) mod 255];
end;
for j:=0 to 4 do
for k:=0 to 2 do begin
temp[k]:=A[0,j,k];
if k=2 then begin
fur1:=dim3RPFback(temp,G);
for t:=0 to 2 do
f3[0,j,t]:=fur1[t];
end;
end;
for k:=0 to 2 do
for j:=0 to 4 do begin
temp1[j]:=f3[0,j,k];
if j=4 then begin
fur2:=dim5RPFback(temp1,G);
for t:=0 to 4 do
f5[0,t,k]:=fur2[t];
end;
end;
for i:=0 to 16 do
for j:=0 to 4 do
for k:=0 to 2 do
cr[ (85*k+51*j+120*i) mod 255]:=f5[i,j,k];
for i:=0 to n-1 do
if i mod 17=0 then rpf15back[round(i/17)]:=cr[i];
end;
- Введение
- В дипломной работе рассмотрен спектральный метод кодирования кодов Рида-Соломона над полем gf(). В основе спектрального описания рс-кодов лежит дискретное преобразование Фурье (дпф над конечным полем.
- Раздел 1. Основы теории помехоустойчивого кодирования
- 1.1 Основные определения
- 1.2 Классификация кодов
- 1.3 Принципы обнаружения и исправления ошибок
- 1.4. Корректирующая способность кода
- Раздел 2. Арифметика и структура конечных полей галуа. Многочлены над полями галуа
- 2.1. Введение в теорию конечных полей
- 2.2 Векторное пространство над конечными полями. Линейная зависимость и независимость
- 2.3 Арифметика полиномов, заданных над конечным полем
- 2.4. Расширенные конечные поля
- 2.5 Мультипликативный порядок элементов поля. Примитивные элементы. Другой подход к построению расширения поля Галуа
- 2.6. Некоторые свойства расширенных конечных полей
- Раздел 3. Линейные блоковые коды
- 3.1. Линейные коды
- 3.2. Определение циклического кода. Порождающий полином
- 3.3. Систематический циклический код
- 3.4. Коды Рида-Соломона
- Раздел 4. Спектральное описание циклических кодов
- 4.1. Дискретное преобразование Фурье
- 4.2. Китайская теорема об остатках
- 4.3. Трехмерное преобразование Фурье в поле
- 4.4 Быстрое преобразование Фурье бпф длины 3
- 4.5. Быстрое преобразование Фурье длины 5
- 4.6 Быстрое преобразование Фурье длины 17
- 4.8. Несистематические бпф-укорочения
- Заключение
- Список использованной литературы
- Приложения Приложение 1. Анализ временных характеристик кодера кодов Рида-Соломона
- Приложение 2 Листинг программы