Èñõîäíûé òåêñò äåêîäåðà
Äàëåå â ëèñòèíãå2.20Íèæå ïðèâîäèòñÿ èñõîäíûé òåêñò ïîëíîöåííîãî äåêîäåðà Ðèäà-Ñîëîìîíà, ñíàáæåííûé ìèíèìàëüíî ðàçóìíûì êîëè÷åñòâîì êîììåíòàðèåì. Ïðè âîçíèêíîâåíèè òðóäíîñòåé â àíàëèçå ýòîãî ëèñòèíãà îáðàùàéòåñü ê áëîê-ñõåìàì, ïðèâåäåííûì íà ðèñ. 21.3, 21.4 è 21.5 [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;
}
