Главная
Новости
Строительство
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




24.06.2022


23.06.2022


23.06.2022


23.06.2022


21.06.2022


20.06.2022


20.06.2022





Яндекс.Метрика

Код Боуза — Чоудхури — Хоквингема

16.06.2022

Коды Бозе — Чёдхури — Хокуингхема (БЧХ-коды) — в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок (см. Обнаружение и исправление ошибок). Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием. Частным случаем БЧХ-кодов является код Рида — Соломона.

Формальное описание

БЧХ-код является циклическим кодом, который можно задать порождающим полиномом. Для его нахождения в случае БЧХ-кода необходимо заранее определить длину кода n {displaystyle n} (она не может быть произвольной) и требуемое минимальное расстояние d ⩽ n {displaystyle dleqslant n} . Найти порождающий полином можно следующим образом.

Пусть α {displaystyle alpha } — примитивный элемент поля G F ( q m ) {displaystyle GF(q^{m})} (то есть α q m − 1 = 1 ,   α i ≠ 1 ,   i < q m − 1 {displaystyle alpha ^{q^{m}-1}=1, alpha ^{i} eq 1, i<q^{m}-1} ), пусть β = α s {displaystyle eta =alpha ^{s}} , — элемент поля G F ( q m ) {displaystyle GF(q^{m})} порядка n {displaystyle n} , s = ( q m − 1 ) / n {displaystyle s=(q^{m}-1)/n} . Тогда нормированный полином g ( x ) {displaystyle g(x)} минимальной степени над полем G F ( q ) {displaystyle GF(q)} , корнями которого являются d − 1 {displaystyle d-1} подряд идущих степеней β l 0 , β l 0 + 1 , … , β l 0 + d − 2 {displaystyle eta ^{l_{0}},eta ^{l_{0}+1},ldots ,eta ^{l_{0}+d-2}} элемента β {displaystyle eta } для некоторого целого l 0 {displaystyle l_{0}} (в том числе 0 и 1), является порождающим полиномом БЧХ-кода над полем G F ( q ) {displaystyle GF(q)} с длиной n {displaystyle n} и минимальный расстоянием d 0 ⩾ d {displaystyle d_{0}geqslant d} .

Поясним, почему у получившегося кода будут именно такие характеристики (длина кода n {displaystyle n} , минимальное расстояние d 0 {displaystyle d_{0}} ). Действительно, как показано у Сагаловича, длина БЧХ-кода равна порядку элемента β {displaystyle eta } , если d > 2 {displaystyle d>2} , и равна порядку элемента β l 0 {displaystyle eta ^{l_{0}}} , если d = 2 {displaystyle d=2} . Так как случай d = 2 {displaystyle d=2} нам не интересен (такой код не может исправлять ошибки, только обнаруживать), то длина кода будет равна порядку элемента β {displaystyle eta } , то есть равна n {displaystyle n} . Минимальное расстояние d 0 {displaystyle d_{0}} может быть больше d {displaystyle d} , когда корнями минимальных функций от элементов β l 0 , β l 0 + 1 , … , β l 0 + d − 2 {displaystyle eta ^{l_{0}},eta ^{l_{0}+1},ldots ,eta ^{l_{0}+d-2}} будут элементы, расширяющие последовательность, то есть элементы β l 0 + d − 1 , β l 0 + d , … , β l 0 + d 0 − 2 {displaystyle eta ^{l_{0}+d-1},eta ^{l_{0}+d},ldots ,eta ^{l_{0}+d_{0}-2}} .

Число проверочных символов r {displaystyle r} равно степени g ( x ) {displaystyle g(x)} , число информационных символов k = n − r {displaystyle k=n-r} , величина d {displaystyle d} называется конструктивным расстоянием БЧХ-кода. Если n = q m − 1 {displaystyle n=q^{m}-1} , то код называется примитивным, иначе — непримитивным.

Так же, как и для циклического кода, кодовый полином c ( x ) {displaystyle c(x)} может быть получен из информационного полинома m ( x ) {displaystyle m(x)} степени не больше k − 1 {displaystyle k-1} , путём перемножения m ( x ) {displaystyle m(x)} и g ( x ) {displaystyle g(x)} :

c ( x ) = m ( x ) g ( x ) . {displaystyle c(x)=m(x)g(x).}

Построение

Для нахождения порождающего полинома необходимо выполнить несколько этапов:

  • выбрать q {displaystyle q} , то есть поле G F ( q ) {displaystyle GF(q)} , над которым будет построен код;
  • выбрать длину n {displaystyle n} кода из условия n = ( q m − 1 ) / s {displaystyle n=(q^{m}-1)/s} , где m , s {displaystyle m,s} — целые положительные числа;
  • задать величину d {displaystyle d} конструктивного расстояния;
  • построить циклотомические классы элемента β = α s {displaystyle eta =alpha ^{s}} поля G F ( q m ) {displaystyle GF(q^{m})} над полем G F ( q ) {displaystyle GF(q)} , где α {displaystyle alpha } — примитивный элемент G F ( q m ) {displaystyle GF(q^{m})} ;
  • поскольку каждому такому циклотомическому классу соответствует неприводимый полином над G F ( q ) {displaystyle GF(q)} , корнями которого являются элементы этого и только этого класса, со степенью равной количеству элементов в классе, то выбрать β l 0 , β l 0 + 1 , … , β l 0 + d − 2 {displaystyle eta ^{l_{0}},eta ^{l_{0}+1},ldots ,eta ^{l_{0}+d-2}} таким образом, чтобы суммарная длина циклотомических классов была минимальна; это делается для того, чтобы при заданных характеристиках кода n {displaystyle n} и d {displaystyle d} минимизировать количество проверочных символов k {displaystyle k} ;
  • вычислить порождающий полином g ( x ) = f 1 ( x ) f 2 ( x ) … f h ( x ) {displaystyle g(x)=f_{1}(x)f_{2}(x)ldots f_{h}(x)} , где f i ( x ) {displaystyle f_{i}(x)} — полином, соответствующий i {displaystyle i} -му циклотомическому классу; или вычислить g ( x ) {displaystyle g(x)} , как НОК минимальных функций от элементов β l 0 , β l 0 + 1 , … , β l 0 + d − 2 {displaystyle eta ^{l_{0}},eta ^{l_{0}+1},ldots ,eta ^{l_{0}+d-2}} .

Примеры кодов

Примитивный двоичный (15, 7, 5) код

Пусть q = 2 {displaystyle q=2} , требуемая длина кода n = 2 4 − 1 = 15 {displaystyle n=2^{4}-1=15} , и минимальное расстояние d 0 ⩾ d = 5 {displaystyle d_{0}geqslant d=5} . Возьмем α {displaystyle alpha } — примитивный элемент поля G F ( 16 ) {displaystyle GF(16)} , и α , α 2 , α 3 , α 4 {displaystyle alpha ,alpha ^{2},alpha ^{3},alpha ^{4}} — четыре подряд идущих степеней элемента α {displaystyle alpha } . Они принадлежат двум циклотомическим классам над полем G F ( 2 ) {displaystyle GF(2)} , которым соответствуют неприводимые полиномы f 1 ( x ) = x 4 + x + 1 {displaystyle f_{1}(x)=x^{4}+x+1} и f 2 ( x ) = x 4 + x 3 + x 2 + x + 1 {displaystyle f_{2}(x)=x^{4}+x^{3}+x^{2}+x+1} . Тогда полином

g ( x ) = f 1 ( x ) f 2 ( x ) = x 8 + x 7 + x 6 + x 4 + 1 {displaystyle g(x)=f_{1}(x)f_{2}(x)=x^{8}+x^{7}+x^{6}+x^{4}+1}

имеет в качестве корней элементы α , α 2 , α 3 , α 4 {displaystyle alpha ,alpha ^{2},alpha ^{3},alpha ^{4}} и является порождающим полиномом БЧХ-кода с параметрами ( 15 , 7 , 5 ) {displaystyle (15,7,5)} .

16-ричный (15, 11, 5) код (код Рида — Соломона)

Пусть n = q − 1 = 15 {displaystyle n=q-1=15} , и α {displaystyle alpha } — примитивный элемент G F ( 16 ) {displaystyle GF(16)} . Тогда

g ( x ) = ( x − α ) ( x − α 2 ) ( x − α 3 ) ( x − α 4 ) = x 4 + α 13 x 3 + α 6 x 2 + α 3 x + α 10 . {displaystyle g(x)=(x-alpha )(x-alpha ^{2})(x-alpha ^{3})(x-alpha ^{4})=x^{4}+alpha ^{13}x^{3}+alpha ^{6}x^{2}+alpha ^{3}x+alpha ^{10}.}

Каждый элемент поля G F ( 16 ) {displaystyle GF(16)} можно сопоставить 4 битам, поэтому одно кодовое слово эквивалентно 60 = 15 × 4 битам, таким образом набору из 44 битов ставится в соответствие набор из 60 битов. Можно сказать, что такой код работает с полубайтами информации.

Кодирование

Для кодирования кодами БЧХ применяются те же методы, что и для кодирования циклическими кодами.

Методы декодирования

Коды БЧХ являются циклическими кодами, поэтому к ним применимы все методы, используемые для декодирования циклических кодов. Однако существуют гораздо лучшие алгоритмы, разработанные именно для БЧХ-кодов.

Главной идеей в декодировании БЧХ-кодов является использование элементов конечного поля для нумерации позиций кодового слова (или, эквивалентно, в порядке коэффициентов ассоциированного многочлена). Ниже приведена такая нумерация для вектора r = ( r 0 , r 1 , … , r n − 1 ) {displaystyle r=(r_{0},r_{1},ldots ,r_{n-1})} , соответствующего многочлену r ( x ) {displaystyle r(x)} .

Пусть принятое слово ассоциировано с полиномом r ( x ) = ν ( x ) + e ( x ) {displaystyle r(x)= u (x)+e(x)} , где многочлен ошибок определён как: e ( x ) = e J 1 x J 1 + e J 2 x J 2 + … + e J ν x J ν {displaystyle e(x)=e_{J_{1}}x^{J_{1}}+e_{J_{2}}x^{J_{2}}+ldots +e_{J_{ u }}x^{J_{ u }}} , где ν ⩽ t d {displaystyle u leqslant t_{d}} — число ошибок в принятом слове. Множества { e J 1 , e J 2 , … , e J ν } {displaystyle {e_{J_{1}},e_{J_{2}},ldots ,e_{J_{ u }}}} и { α J 1 , α J 2 , … , α J ν } {displaystyle {alpha ^{J_{1}},alpha ^{J_{2}},ldots ,alpha ^{J_{ u }}}} называют значениями ошибок и локаторами ошибок соответственно, где e J ∈ G F ( q ) {displaystyle e_{J}in GF(q)} , и α ∈ G F ( q m ) {displaystyle alpha in GF(q^{m})} .

Синдромы определены как значения принятого полинома r ( x ) {displaystyle r(x)} в нулях порождающего многочлена кода:

S 1 = r ( α b ) = e J 1 α b J 1 + e J 2 α b J 2 + … + e J ν α b J ν , {displaystyle S_{1}=r(alpha ^{b})=e_{J_{1}}alpha ^{bJ_{1}}+e_{J_{2}}alpha ^{bJ_{2}}+ldots +e_{J_{ u }}alpha ^{bJ_{ u }},} S 2 = r ( α b + 1 ) = e J 1 α ( b + 1 ) J 1 + e J 2 α ( b + 1 ) J 2 + … + e J ν α ( b + 1 ) J ν , {displaystyle S_{2}=r(alpha ^{b+1})=e_{J_{1}}alpha ^{(b+1)J_{1}}+e_{J_{2}}alpha ^{(b+1)J_{2}}+ldots +e_{J_{ u }}alpha ^{(b+1)J_{ u }},} ⋮ {displaystyle vdots } S 2 t d = r ( α b + 2 t d − 1 ) = e J 1 α ( b + 2 t d − 1 ) J 1 + e J 2 α ( b + 2 t d − 1 ) J 2 + … + e J ν α ( b + 2 t d − 1 ) J ν , {displaystyle S_{2t_{d}}=r(alpha ^{b+2t_{d}-1})=e_{J_{1}}alpha ^{(b+2t_{d}-1)J_{1}}+e_{J_{2}}alpha ^{(b+2t_{d}-1)J_{2}}+ldots +e_{J_{ u }}alpha ^{(b+2t_{d}-1)J_{ u }},}

где 2 t d = d − 1 {displaystyle 2t_{d}=d-1} .

Для нахождения множества локаторов ошибок введём в рассмотрение многочлен локаторов ошибок

σ ( x ) = ∏ l = 1 ν ( 1 + α J l x ) = 1 + σ 1 x + σ 2 x 2 + … + σ ν x ν , {displaystyle sigma (x)=prod _{l=1}^{ u }(1+alpha ^{J_{l}}x)=1+sigma _{1}x+sigma _{2}x^{2}+ldots +sigma _{ u }x^{ u },}

корни которого равны обратным величинам локаторов ошибок. Тогда справедливо следующее соотношение между коэффициентами многочлена локаторов ошибок и синдромами:

σ 1 S t + σ 2 S t − 1 + … + σ t S 1 = − S t + 1 , {displaystyle sigma _{1}S_{t}+sigma _{2}S_{t-1}+ldots +sigma _{t}S_{1}=-S_{t+1},} σ 1 S t + 1 + σ 2 S t + … + σ t S 2 = − S t + 2 , {displaystyle sigma _{1}S_{t+1}+sigma _{2}S_{t}+ldots +sigma _{t}S_{2}=-S_{t+2},} ⋮ {displaystyle vdots } σ 1 S 2 t − 1 + σ 2 S 2 t − 2 + … + σ t S t = − S 2 t . {displaystyle sigma _{1}S_{2t-1}+sigma _{2}S_{2t-2}+ldots +sigma _{t}S_{t}=-S_{2t}.}

Известны следующие методы для решения этой системы уравнений относительно коэффициентов многочлена локаторов ошибок σ i ,   i = 1 , 2 , … , ν {displaystyle sigma _{i}, i=1,2,ldots , u } (ключевая система уравнений).

  • Алгоритм Берлекемпа — Мэсси (BMA). По числу операций в конечном поле этот алгоритм обладает высокой эффективностью. BMA обычно используется для программной реализации или моделирования кодов БЧХ и кодов Рида — Соломона.
  • Евклидов алгоритм (ЕА). Из-за высокой регулярности структуры этого алгоритма его широко используют для аппаратной реализации декодеров БЧХ и кодов Рида — Соломона.
  • Прямое решение (алгоритм Питерсона — Горенстейна — Цирлера, ПГЦ). Исторически это первый метод декодирования, найденный Питерсоном для двоичного случая ( q = 2 {displaystyle q=2} ), затем Горенстейном и Цирлером для общего случая. Этот алгоритм находит коэффициенты многочлена локаторов ошибок прямым решением соответствующей системы линейных уравнений. В действительности, так как сложность этого алгоритма растет как куб минимального расстояния d {displaystyle d} , прямой алгоритм может быть использован только для малых значений d {displaystyle d} , однако именно этот алгоритм лучше всего проясняет алгебраическую идею процесса декодирования.

Алгоритм Берлекемпа — Мэсси

Этот алгоритм лучше всего рассматривать как итеративный процесс построения минимального регистра (сдвига) с обратной связью, генерирующего известную последовательность синдромов S 1 , S 2 , … , S 2 t d {displaystyle S_{1},S_{2},ldots ,S_{2t_{d}}} . Его фактическая цель — построить полином σ i + 1 ( x ) {displaystyle sigma ^{i+1}(x)} наименьшей степени, удовлетворяющему уравнению

∑ j = 0 l i + 1 S k − j σ j i + 1 = 0 , l i < k < i + 1. {displaystyle sum _{j=0}^{l_{i}+1}S_{k-j}sigma _{j}^{i+1}=0,quad l_{i}<k<i+1.}

Решение этого уравнения эквивалентно условию

σ i + 1 ( x ) = 1 + σ 1 i + 1 x + … + σ l i + 1 i + 1 x l i + 1 . {displaystyle sigma ^{i+1}(x)=1+sigma _{1}^{i+1}x+ldots +sigma _{l_{i+1}}^{i+1}x^{l_{i+1}}.}

Итеративный процесс построения такого многочлена и есть Алгоритм Берлекемпа — Мэсси.

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

В основе этого метода лежит широко известный алгоритм Евклида по нахождению наибольшего общего делителя двух чисел (НОД), только в данном случае ищем НОД не двух чисел, а двух полиномов. Обозначим полином значений ошибок как Λ = σ ( x ) S ( x ) {displaystyle Lambda =sigma (x)S(x)} , где синдромный полином равен S ( x ) = 1 + S 1 x + … + S 2 t d x 2 t d {displaystyle S(x)=1+S_{1}x+ldots +S_{2t_{d}}x^{2t_{d}}} . Из системы уравнений следует, что Λ ( x ) = σ ( x ) S ( x ) mod x 2 t d + 1 {displaystyle Lambda (x)=sigma (x)S(x)mod x^{2t_{d}+1}} . Задача по сути сводится к тому чтобы определить Λ ( x ) {displaystyle Lambda (x)} , удовлетворяющий последнему уравнению и при этом степени не выше t d {displaystyle t_{d}} . По сути такое решение и будет давать расширенный алгоритм Евклида, примененный к многочленам r 0 ( x ) = x d {displaystyle r_{0}(x)=x^{d}} и r 1 ( x ) = S ( x ) {displaystyle r_{1}(x)=S(x)} , где d = 2 t d + 1 {displaystyle d=2t_{d}+1} . Если на j {displaystyle j} -м шаге расширенный алгоритм Евклида выдает решение r j = a j ( x ) x 2 t d + 1 + b j ( x ) S ( x ) {displaystyle r_{j}=a_{j}(x)x^{2t_{d}+1}+b_{j}(x)S(x)} , такое что deg ⁡ [ r j ( x ) ] ⩽ t d {displaystyle deg[r_{j}(x)]leqslant t_{d}} , то Λ ( x ) = r j ( x ) {displaystyle Lambda (x)=r_{j}(x)} , и σ i ( x ) = b j ( x ) {displaystyle sigma _{i}(x)=b_{j}(x)} . При этом найденный полином a j ( x ) {displaystyle a_{j}(x)} дальше не принимает участия в декодировании (он ищется только как вспомогательный). Таким образом будет найден полином локаторов ошибок σ ( x ) {displaystyle sigma (x)} .

Прямое решение (алгоритм Питерсона — Горенстейна — Цирлера, ПГЦ)

Пусть БЧХ-код над полем G F ( q ) {displaystyle GF(q)} длины n {displaystyle n} и с конструктивным расстоянием d {displaystyle d} задаётся порождающим полиномом g ( x ) {displaystyle g(x)} , который имеет среди своих корней элементы β l 0 , β l 0 + 1 , … , β l 0 + d − 2 ,   β ∈ G F ( q m ) ,   β n = 1 ,   l 0 {displaystyle eta ^{l_{0}},eta ^{l_{0}+1},ldots ,eta ^{l_{0}+d-2}, eta in GF(q^{m}), eta ^{n}=1, l_{0}} — целое число (например, 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что c ( β l 0 − 1 + j ) = 0 ,   j = 1 , 2 , … , d − 1 {displaystyle c(eta ^{l_{0}-1+j})=0, j=1,2,ldots ,d-1} . Принятое слово r ( x ) {displaystyle r(x)} можно записать как r ( x ) = c ( x ) + e ( x ) {displaystyle r(x)=c(x)+e(x)} , где e ( x ) {displaystyle e(x)} — полином ошибок. Пусть произошло u ⩽ t = ( d − 1 ) / 2 {displaystyle uleqslant t=(d-1)/2} ошибок на позициях i 1 , i 2 , … , i u {displaystyle i_{1},i_{2},ldots ,i_{u}} ( t {displaystyle t} — максимальное число исправляемых ошибок), значит e ( x ) = e i 1 x i 1 + e i 2 x i 2 + … + e i u x i u {displaystyle e(x)=e_{i_{1}}x^{i_{1}}+e_{i_{2}}x^{i_{2}}+ldots +e_{i_{u}}x^{i_{u}}} , а e i 1 , e i 2 , … , e i u {displaystyle e_{i_{1}},e_{i_{2}},ldots ,e_{i_{u}}} — величины ошибок.

Можно составить j {displaystyle j} -й синдром S j {displaystyle S_{j}} принятого слова r ( x ) {displaystyle r(x)} :

S j = r ( β l 0 − 1 + j ) = e ( β l 0 − 1 + j ) , j = 1 , … , d − 1. {displaystyle S_{j}=r(eta ^{l_{0}-1+j})=e(eta ^{l_{0}-1+j}),quad j=1,ldots ,d-1.}

Задача состоит в нахождении числа ошибок u {displaystyle u} , их позиций i 1 , i 2 , … , i u {displaystyle i_{1},i_{2},ldots ,i_{u}} и их значений e i 1 , e i 2 , … , e i u {displaystyle e_{i_{1}},e_{i_{2}},ldots ,e_{i_{u}}} при известных синдромах S j {displaystyle S_{j}} .

Предположим для начала, что u {displaystyle u} в точности равно t {displaystyle t} . Запишем синдромы в виде системы нелинейных уравнений в явном виде:

{ S 1 = e i 1 β l 0 i 1 + e i 2 β l 0 i 2 + … + e i t β l 0 i t , S 2 = e i 1 β ( l 0 + 1 ) i 1 + e i 2 β ( l 0 + 1 ) i 2 + … + e i t β ( l 0 + 1 ) i t , ⋮ S d − 1 = e i 1 β ( l 0 + d − 2 ) i 1 + e i 2 β ( l 0 + d − 2 ) i 2 + … + e i t β ( l 0 + d − 2 ) i t . {displaystyle {egin{cases}S_{1}=e_{i_{1}}eta ^{l_{0}i_{1}}+e_{i_{2}}eta ^{l_{0}i_{2}}+ldots +e_{i_{t}}eta ^{l_{0}i_{t}},S_{2}=e_{i_{1}}eta ^{(l_{0}+1)i_{1}}+e_{i_{2}}eta ^{(l_{0}+1)i_{2}}+ldots +e_{i_{t}}eta ^{(l_{0}+1)i_{t}},vdots S_{d-1}=e_{i_{1}}eta ^{(l_{0}+d-2)i_{1}}+e_{i_{2}}eta ^{(l_{0}+d-2)i_{2}}+ldots +e_{i_{t}}eta ^{(l_{0}+d-2)i_{t}}.end{cases}}}

Обозначим через X k = β i k {displaystyle X_{k}=eta ^{i_{k}}} локатор k {displaystyle k} -й ошибки, а через Y k = e i k {displaystyle Y_{k}=e_{i_{k}}} — величину ошибки, k = 1 , … , t {displaystyle k=1,ldots ,t} . При этом все X k {displaystyle X_{k}} различны, так как порядок элемента β {displaystyle eta } равен n {displaystyle n} , и поэтому при известном X k {displaystyle X_{k}} можно определить i k {displaystyle i_{k}} как i k = log β ⁡ X k {displaystyle i_{k}=log _{eta }X_{k}} .

{ S 1 = Y 1 X 1 l 0 + Y 2 X 2 l 0 + … + Y t X t l 0 , S 2 = Y 1 X 1 l 0 + 1 + Y 2 X 2 l 0 + 1 + … + Y t X t l 0 + 1 , ⋮ S d − 1 = Y 1 X 1 l 0 + d − 2 + Y 2 X 2 l 0 + d − 2 + … + Y t X t l 0 + d − 2 . {displaystyle {egin{cases}S_{1}=Y_{1}X_{1}^{l_{0}}+Y_{2}X_{2}^{l_{0}}+ldots +Y_{t}X_{t}^{l_{0}},S_{2}=Y_{1}X_{1}^{l_{0}+1}+Y_{2}X_{2}^{l_{0}+1}+ldots +Y_{t}X_{t}^{l_{0}+1},vdots S_{d-1}=Y_{1}X_{1}^{l_{0}+d-2}+Y_{2}X_{2}^{l_{0}+d-2}+ldots +Y_{t}X_{t}^{l_{0}+d-2}.end{cases}}}

Составим полином локаторов ошибок:

Λ ( x ) = ( 1 − x X 1 ) ( 1 − x X 2 ) … ( 1 − x X t ) = Λ t x t + Λ t − 1 x t − 1 + … + Λ 1 x + 1. {displaystyle Lambda (x)=(1-xX_{1})(1-xX_{2})ldots (1-xX_{t})=Lambda _{t}x^{t}+Lambda _{t-1}x^{t-1}+ldots +Lambda _{1}x+1.}

Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на Y l X l ϑ + t {displaystyle Y_{l}X_{l}^{vartheta +t}} . Полученное равенство будет справедливо для ϑ = l 0 , l 0 + 1 , … , l 0 + d − 1 ,   l = 1 , … , t {displaystyle vartheta =l_{0},l_{0}+1,ldots ,l_{0}+d-1, l=1,ldots ,t} :

Λ ( x ) Y l X l ϑ + t = Λ t x t Y l X l ϑ + t + Λ t − 1 x t − 1 Y l X l ϑ + t + … + Λ 1 x Y l X l ϑ + t + Y l X l ϑ + t . {displaystyle Lambda (x)Y_{l}X_{l}^{vartheta +t}=Lambda _{t}x^{t}Y_{l}X_{l}^{vartheta +t}+Lambda _{t-1}x^{t-1}Y_{l}X_{l}^{vartheta +t}+ldots +Lambda _{1}xY_{l}X_{l}^{vartheta +t}+Y_{l}X_{l}^{vartheta +t}.}

Если подставить сюда x = X l − 1 {displaystyle x=X_{l}^{-1}} , то получится равенство, справедливое для каждого l ∈ { 1 , 2 , … , t } {displaystyle lin {1,2,ldots ,t}} и при всех ϑ ∈ { l 0 , l 0 + 1 , … , l 0 + d − 1 } {displaystyle vartheta in {l_{0},l_{0}+1,ldots ,l_{0}+d-1}} :

0 = Λ t Y l X l ϑ + Λ t − 1 Y l X l ϑ + 1 + … + Λ 1 Y l X l ϑ + t − 1 + Y l X l ϑ + t . {displaystyle 0=Lambda _{t}Y_{l}X_{l}^{vartheta }+Lambda _{t-1}Y_{l}X_{l}^{vartheta +1}+ldots +Lambda _{1}Y_{l}X_{l}^{vartheta +t-1}+Y_{l}X_{l}^{vartheta +t}.}

Таким образом для каждого l {displaystyle l} можно записать своё равенство. Если их просуммировать по l {displaystyle l} , то получится равенство, справедливое для каждого ϑ ∈ { l 0 , l 0 + 1 , … , l 0 + d − 1 } {displaystyle vartheta in {l_{0},l_{0}+1,ldots ,l_{0}+d-1}} :

0 = Λ t ∑ l = 1 t Y l X l ϑ + Λ t − 1 ∑ l = 1 t Y l X l ϑ + 1 + … + Λ 1 ∑ l = 1 t Y l X l ϑ + t − 1 + ∑ l = 1 t Y l X l ϑ + t . {displaystyle 0=Lambda _{t}sum _{l=1}^{t}Y_{l}X_{l}^{vartheta }+Lambda _{t-1}sum _{l=1}^{t}Y_{l}X_{l}^{vartheta +1}+ldots +Lambda _{1}sum _{l=1}^{t}Y_{l}X_{l}^{vartheta +t-1}+sum _{l=1}^{t}Y_{l}X_{l}^{vartheta +t}.}

Поскольку S j + p = ∑ l = 1 t Y l X l l 0 + j + p − 1 = ∑ l = 1 t Y l X l ϑ + p ,   j = 1 , … , d − 1 ,   ϑ = l 0 + j − 1 {displaystyle S_{j+p}=sum _{l=1}^{t}Y_{l}X_{l}^{l_{0}+j+p-1}=sum _{l=1}^{t}Y_{l}X_{l}^{vartheta +p}, j=1,ldots ,d-1, vartheta =l_{0}+j-1} (то есть, ϑ {displaystyle vartheta } меняется в тех же пределах, что и ранее), система уравнений для синдромов преобразуется в систему линейных уравнений:

{ S 1 Λ t + S 2 Λ t − 1 + … + S t Λ 1 = − S t + 1 , S 2 Λ t + S 3 Λ t − 1 + … + S t + 1 Λ 1 = − S t + 2 , ⋮ S t Λ t + S t + 1 Λ t − 1 + … + S 2 t − 1 Λ 1 = − S 2 t , {displaystyle {egin{cases}S_{1}Lambda _{t}+S_{2}Lambda _{t-1}+ldots +S_{t}Lambda _{1}=-S_{t+1},S_{2}Lambda _{t}+S_{3}Lambda _{t-1}+ldots +S_{t+1}Lambda _{1}=-S_{t+2},vdots S_{t}Lambda _{t}+S_{t+1}Lambda _{t-1}+ldots +S_{2t-1}Lambda _{1}=-S_{2t},end{cases}}}

или, в матричной форме,

S ( t ) Λ ¯ ( t ) = − s ¯ ( t ) , {displaystyle S^{(t)}{ar {Lambda }}^{(t)}=-{ar {s}}^{(t)},}

где

S ( t ) = ( S 1 S 2 … S t S 2 S 3 … S t + 1 ⋮ ⋮ ⋱ ⋮ S t S t + 1 … S 2 t − 1 ) , Λ ¯ ( t ) = ( Λ t Λ t − 1 ⋮ Λ 1 ) , s ¯ ( t ) = ( S t + 1 S t + 2 ⋮ S 2 t ) . {displaystyle S^{(t)}={egin{pmatrix}S_{1}&S_{2}&ldots &S_{t}S_{2}&S_{3}&ldots &S_{t+1}vdots &vdots &ddots &vdots S_{t}&S_{t+1}&ldots &S_{2t-1}end{pmatrix}},quad {ar {Lambda }}^{(t)}={egin{pmatrix}Lambda _{t}Lambda _{t-1}vdots Lambda _{1}end{pmatrix}},quad {ar {s}}^{(t)}={egin{pmatrix}S_{t+1}S_{t+2}vdots S_{2t}end{pmatrix}}.}

Если число ошибок и в самом деле равно t {displaystyle t} , то эта система разрешима, и можно найти значения коэффициентов Λ 1 , … , Λ t {displaystyle Lambda _{1},ldots ,Lambda _{t}} . Если же число u < t {displaystyle u<t} , то определитель матрицы S ( t ) {displaystyle S^{(t)}} будет равен 0 {displaystyle 0} . Это есть признак того, что количество ошибок меньше t {displaystyle t} . Поэтому необходимо составить систему, предполагая число ошибок равным t − 1 {displaystyle t-1} , вычислить определитель новой матрицы S ( t − 1 ) {displaystyle S^{(t-1)}} и т. д. до тех пор, пока не установим истинное число ошибок.

Поиск Ченя

После того как ключевая система уравнений решена, получаются коэффициенты полинома локаторов ошибок. Его корни (элементы, обратные локаторам ошибок) можно найти простым перебором по всем элементам поля G F ( q m ) {displaystyle GF(q^{m})} . К ним найти элементы, обратные по умножению, — это локаторы ошибок X k ,   k = 1 , … , u {displaystyle X_{k}, k=1,ldots ,u} . Этот процесс легко реализовать аппаратно.

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

По локаторам можно найти позиции ошибок ( i k = log β ⁡ X k {displaystyle i_{k}=log _{eta }X_{k}} ), а значения Y k {displaystyle Y_{k}} ошибок из системы для синдромов, приняв t = u {displaystyle t=u} . Декодирование завершено.


Имя:*
E-Mail:
Комментарий: