Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Примеры решения ключевого уравнения

Определение и основные свойства | Пример 7.1 | Пример 7.2 | Расширенные РС-коды | Укороченные РС-коды | Пример 7.4 | Способы кодирования и декодирования РС-кодов | Многочлен значений ошибок | Ключевое уравнение | Многочлен значений ошибок |


Читайте также:
  1. VII. Решения, принятые по итогам общественного обсуждения.
  2. VII. Решения, принятые по итогам общественного обсуждения.
  3. адачи для самостоятельного решения
  4. адачи для самостоятельного решения.
  5. адачи для самостоятельного решения.
  6. адачи для самостоятельного решения.
  7. адзор за соблюдением установленного законодательством порядка разрешения заявлений и сообщений о совершенных или готовящихся преступлениях

Рассмотрим примеры применения рассмотренных алгоритмов для декодирования с исправлением ошибок кодами Рида-Соломона.

Пример 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)=α31x+α0x23x3+x4

Предположим, что по каналу связи была передана комбинация (0000000),а на вход декодера поступила комбинация. f(x)=а2х3 + а5х4. Схема вычисления синдрома определила компоненты синдромного многочлена:

 

Рис.7.1.Алгоритм Берлекемпа-Месси

S1=f(x=α)=α523

S2=f(x=α2)=α165

S3=f(x=α3)=α436

S4=f(x=α4)=α00=0

При вычислении значений элементов Si, показатели степеней элементов поля приводятся по mod 7, т.к. для GF(23) а07=1. Итак, для принятой комбинации синдромный многочлен имеет вид: S(x)=α35x+α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 .Вычислим определитель:

.

Теперь находим:

=α(α42)=α532 , =α(α+α2)=α235.

Полученные значения Y1 и Y2 соответствуют коэффициентам многочлена ошибок.

2.Алгоритм Евклида

Поиск значений Λi(x) в Ωi(x), удовлетворяющих приведенным выше критериям, представим в виде таблицы.

i -1    
Λi(x)     α+х+αx2=α(1+α6x+x2)
i(x) х4 S(x) α 4 4х=α(α33х)
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 и S25. По первому такту S1=α3 поступает на выход, а в ячейках остаются S25 и S36. По второму такту S25 поступает на выход, а в ячейках остаются S36 и S4=0, которые за два следующих такта поступают на выход.

4. Алгоритм Форни.

Для вычисления значений ошибок необходимо знание Λ(х) и его корней, а также должен быть известен многочлен Ω(x).Непосредственным вычислением находим: ■

Ω(x)=S(x)Λ(x)(modx2t)=(α35x+а6х2)(1+α6x+x2)(modx4)=α33х. Расчетные значения Λ(х) и Ω(x)полностью совпадают с полученными по алгоритму Берлекемпа-Месси и отличаются постоянным сомножителем при вычислении по алгоритму Евклида.

Для нахождения значений ошибок по алгоритму Форни найдем Λ (х)=а6. Подставляя в Ω(х) вместо x значения корней Λ(x) получаем:

Итак, вычисленное значение многочлена ошибок е(х)= α2x35x4 полностью совпадает с принятой комбинацией f(х) и, следовательно, по каналу связи передавалась комбинация (0000000).

 


Дата добавления: 2015-08-02; просмотров: 78 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
А). Алгоритм Питерсона.| Вычисление избыточных элементов

mybiblioteka.su - 2015-2024 год. (0.008 сек.)