Читайте также:
|
|
Рассмотрим примеры применения рассмотренных алгоритмов для декодирования с исправлением ошибок кодами Рида-Соломона.
Пример 7.7. Пусть над полем GF(23) с элементами 000, α=1=100, α1=010, α2=001,
α3=110, α4=011, α5=111, α6=101 построен код Рида-Соломона (7,3) с dmin=5, способный исправлять 2-х кратные ошибки. Корнями порождающего многочлена являются следующие элементы GF(23): α1=010, α2=110,α3=110,α4=011.. Порождающий многочлен кода имеет вид;
g(x)=(x+α)(x+α2)(x+α3)(x+α4)=α3+α1x+α0x2+α3x3+x4
Предположим, что по каналу связи была передана комбинация (0000000),а на вход декодера поступила комбинация. f(x)=а2х3 + а5х4. Схема вычисления синдрома определила компоненты синдромного многочлена:
Рис.7.1.Алгоритм Берлекемпа-Месси
S1=f(x=α)=α5+α2=α3
S2=f(x=α2)=α1+α6=α5
S3=f(x=α3)=α4+α3=α6
S4=f(x=α4)=α0+α0=0
При вычислении значений элементов Si, показатели степеней элементов поля приводятся по mod 7, т.к. для GF(23) а0=а7=1. Итак, для принятой комбинации синдромный многочлен имеет вид: S(x)=α3+α5x+α6x2.
Определим для принятой комбинации многочлен локаторов ошибок Λ(х).
1.Алгоритм Питерсона. Матричное уравнение для нахождения компонентов Λ(х) по S(х) имеет вид:
.
В предложении, что произошло максимальное число исправляемых кодом ошибок t=2 воспользуемся теоремой Крамера [5] для решения системы линейных уравнений, представленных в матричной форме Ах=С, в случае, когда det А существует и отличен от нуля, В этом случае система имеет одно определенное решение, и каждое из неизвестных выражается частным двух определителей, причем в знаменателе стоит определитель |А|, а в числителе, определитель который из него получается заменой коэффициентов при определяемом неизвестном соответствующими свободными членами: .
Применяя теорему Крамера для нахождения λ i получаем:
Таким образом, многочлен локаторов ошибок имеет вид:
Λ(x)=1+α6x+α0x2.
Корнями многочлена Λ{х) являются элементы GF(23): α3 и α4, т.е. локаторы ошибок
Это дает возможность представить многочлен локаторов ошибок и виде;
Λ(х)=(1+α3х)(1+α4х)\
Алгоритм Питерсона позволяет найти также и значения ошибок. Для этого выразим компоненты синдромного многочлена S1 и S2 через локаторы ошибок Xl, и значения ошибок Yl:
S1=Y1X1 + Y2X2
S2=Y1X12 + Y2X2
Представим эти уравнения в матричной форме:
или
Решим это уравнение тем же способом, каким были найдены λ1 λ2 .Вычислим определитель:
.
Теперь находим:
=α(α4+α2)=α5+α3=α2 , =α(α+α2)=α2+α3=α5.
Полученные значения Y1 и Y2 соответствуют коэффициентам многочлена ошибок.
2.Алгоритм Евклида
Поиск значений Λi(x) в Ωi(x), удовлетворяющих приведенным выше критериям, представим в виде таблицы.
i | -1 | ||
Λi(x) | α+х+αx2=α(1+α6x+x2) | ||
Ωi(x) | х4 | S(x) | α 4+α 4х=α(α3+α3х) |
qi(x) | ___ | ___ | [х4 /S(x)]=α+x+αx2 |
Из приведенной таблицы видно, что найденное значение Λ (х)=α(1+ α6x+x2) отличается от Λ (х), подученного по алгоритму Питерсона, постоянным сомножителем α. Понятно, что корни этих многочленов совпадают, т,е, постоянный сомножитель не влияет на определение локаторов ошибок.
3, Алгоритм Берлекемпа-Месси. Вычисление Λ(х) и Ω(x) в соответствии с доработанным алгоритмом Берлекемпа-Месси представим ввиде следующей таблицы:
r | S r | Δr | M(x) | B(x) | Λ(x) | L | Ω(x) | A(x) |
α3 | α3 | 1+α3x | α4 | 1+α3x | α3 | |||
α5 | α | 1+α2x | a4x | 1+α2x | α3 | |||
α6 | α2 | 1+α2x+α6x | α5+x | 1+α2x+a6x2 | α3 | αx |
α2 | 1+α6x+x2 | α5x+x2 | 1+α6x+x2 | α3+ α3x | αx |
Найденному значению Λ(х)= 1+α6x+x2 соответствует регистр сдвига с обратными связями, определенными видом Λ(х), длины L=2, способный генерировать все компоненты синдромного многочлена по двум младшим. Этот регистр имеет вид:
В исходном состоянии в ячейках памяти регистра записаны компоненты синдрома S1=α3 и S2=α5. По первому такту S1=α3 поступает на выход, а в ячейках остаются S2=α5 и S3=α6. По второму такту S2=α5 поступает на выход, а в ячейках остаются S3=α6 и S4=0, которые за два следующих такта поступают на выход.
4. Алгоритм Форни.
Для вычисления значений ошибок необходимо знание Λ(х) и его корней, а также должен быть известен многочлен Ω(x).Непосредственным вычислением находим: ■
Ω(x)=S(x)Λ(x)(modx2t)=(α3+α5x+а6х2)(1+α6x+x2)(modx4)=α3+α3х. Расчетные значения Λ(х) и Ω(x)полностью совпадают с полученными по алгоритму Берлекемпа-Месси и отличаются постоянным сомножителем при вычислении по алгоритму Евклида.
Для нахождения значений ошибок по алгоритму Форни найдем Λ′ (х)=а6. Подставляя в Ω(х) вместо x значения корней Λ(x) получаем:
Итак, вычисленное значение многочлена ошибок е(х)= α2x3+α5x4 полностью совпадает с принятой комбинацией f(х) и, следовательно, по каналу связи передавалась комбинация (0000000).
Дата добавления: 2015-08-02; просмотров: 78 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
А). Алгоритм Питерсона. | | | Вычисление избыточных элементов |