Исходный текст декодера
Далее в листинге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;
}
