-

         


2.20 -, . -, . 21.3, 21.4 21.[Y72]  .

 21.20.  -

/*----------------------------------------------------------------------------

*

* -

* =====================

*

* -

* 2t- alpha**i

* recd(x), recd  ,

* . recd(x)

* s[i], i 1 2t,

* s[0] .

* , (Berlekamp),

*   elp[i]. elp

* t,



* ,

* . elp t,

* alpha**i, i = 1..n elp .

* .

* elp,

* t .

*

* .

* ,

*

*

*

* Simon' Rockliff', 26.06.1991


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

//

// . Lin and Costello (. "Error

// Control Coding: Fundamentals and Applications" Prentice Hall 1983

// ISBN 013283796) d[u] m (""),

//

(discrepancy), u = m + 1 m

// 1 2t.

// D(x) ("") .

// l[u] elp ,

// u_l[u] elp



//

d[0] = 0; //

d[1] = s[1]; //

elp[0][0] = 0; //

elp[1][0] = 1; //



for (i = 1; i < n - k; i++)

{

elp[0][i] = -1; //

elp[1][i] = 0; //

}



l[0] = 0; l[1] = 0; u_lu[0] = -1; u_lu[1] = 0; u = 0;



do

{

u++;

if (d[u] == -1)

{

l[u + 1] = l[u];

for (i = 0; i <= l[u]; i++)

{

elp[u+1][i] = elp[u][i];

elp[u][i] = index_of[elp[u][i]];

}

}

else

{

// u_lu[q], d[q]!=0

q = u - 1;

while ((d[q] == -1) && (q>0)) q--;



// d[q]



if (q > 0)

{

j=q ;

do

{

j-- ;

if ((d[j]!=-1) && (u_lu[q]<u_lu[j]))

q = j ;

} while (j>0);

};



// q, d[u]!=0

// u_lu[q]

// elp

if (l[u] > l[q]+u-q) l[u+1] = l[u]; else l[u+1] = l[q]+u-q;





// elp(x)

for (i = 0; i < n - k; i++) elp[u+1][i] = 0;

for (i = 0; i <= l[q]; i++)

if (elp[q][i]!=-1)

elp[u+1][i+u-q]=alpha_to[(d[u]+n-d[q]+elp[q][i])%n];



for (i=0; i<=l[u]; i++)

{

elp[u+1][i] ^= elp[u][i];



// elp

//

elp[u][i] = index_of[elp[u][i]];

}

}

u_lu[u+1] = u-l[u+1];



// (u + 1)'

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

if (u < n-k) //

{ //



if (s[u + 1]!=-1) d[u+1] = alpha_to[s[u+1]]; else d[u + 1] = 0;



for (i = 1; i <= l[u + 1]; i++)

if ((s[u + 1 - i] != -1) && (elp[u + 1][i]!=0))

d[u+1] ^= alpha_to[(s[u+1-i]+index_of[elp[u+1][i]])%n];



// d[u+1]

d[u+1] = index_of[d[u+1]];

}

} while ((u < n-k) && (l[u+1]<=t));





//

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

u++ ;

if (l[u] <= t)

{ //



// elp

for (i = 0; i <= l[u]; i++) elp[u][i] = index_of[elp[u][i]];





//

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

for (i = 1; i <= l[u]; i++) reg[i] = elp[u][i]; count = 0;



for (i = 1; i <= n; i++)

{

q = 1 ;

for (j = 1; j <= l[u]; j++)

if (reg[j] != -1)

{

reg[j] = (reg[j]+j)%n;

q ^= alpha_to[reg[j]];

}



if (!q)

{ //

root[count] = i;

loc[count] = n-i;

count++;

}

}



if (count == l[u])

{ // elp < t



// z(x)

for (i = 1; i <= l[u]; i++) // Z[0] 1

{

if ((s[i]!=-1) && (elp[u][i]!=-1))

z[i] = alpha_to[s[i]] ^ alpha_to[elp[u][i]];

else

if ((s[i]!=-1) && (elp[u][i]==-1))

z[i] = alpha_to[s[i]];

else

if ((s[i]==-1) && (elp[u][i]!=-1))

z[i] = alpha_to[elp[u][i]];

else

z[i] = 0 ;

for (j=1; j<i; j++)

if ((s[j]!=-1) && (elp[u][i-j]!=-1))



z[i] ^= alpha_to[(elp[u][i-j] + s[j])%n];



// z[i]

z[i] = index_of[z[i]];

}



// loc[i]

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

for (i = 0; i<n; i++)

{

err[i] = 0;



// recd[]

if (recd[i]!=-1) recd[i] = alpha_to[recd[i]]; else recd[i] = 0;

}



//

for (i = 0; i < l[u]; i++)

{

err[loc[i]] = 1;

for (j=1; j<=l[u]; j++)

if (z[j]!=-1)

err[loc[i]] ^= alpha_to[(z[j]+j*root[i])%n];



if (err[loc[i]]!=0)

{

err[loc[i]] = index_of[err[loc[i]]];

q = 0 ; //

for (j=0; j<l[u]; j++)

if (j!=i)

q+=index_of[1^alpha_to[(loc[j]+root[i])%n]];



q = q % n; err[loc[i]] = alpha_to[(err[loc[i]]-q+n)%n];



// recd[i]

recd[loc[i]] ^= err[loc[i]];

}

}

}

else // ,

// , .. elp >= t

{

// recd[]

for (i=0; i<n; i++)

if (recd[i]!=-1) recd[i] = alpha_to[recd[i]];

else

recd[i] = 0; //

}

else // elp > t,

{

// recd[]

for (i=0; i<n; i++)

if (recd[i]!=-1)

recd[i] = alpha_to[recd[i]] ;

else

recd[i] = 0 ; //

}

else //

for (i=0;i<n;i++) if(recd[i]!=-1)recd[i]=alpha_to[recd[i]];else recd[i]=0;

}