Главная страница  Алгебраическая теория кодирования 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

Код, исправляющий одну ошибку, имеет 5 проверочных и 26 информационных позиций и скорость 26/31. Код, исправляющий две ошибки, имеет скорость 21/31. Эти коды мы уже рассматривали в разд. 5.1 и 5.2.

Отметим, что БЧХ-код, исправляющий 4 ошибки, совпадает с кодом, исправляющим 5 ошибок, так как минимальные многочлены Af(*) (х) и Af() (х) элементов а* и соответственно совпадают. Аналогично, код, исправляющий 6 ошибок, совпадает с кодом, исправляющим 7 ошибок. Скорость этого кода равна 6/31.

Отметим также, что коды, исправляющие от 8 до 14 ошибок, также совпадают между собой и имеют скорость 1/31. Такой код «одержит только два слова - (00 ... 0) и (И .. . 1). Ясно, что этот код, в каждом слове которого информационная позиция повторяется 31 раз, позволяет одновременно исправлять 15 ошибок.

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

7.2. Ключевое уравнение для декодирования двоичных БЧХ-кодов

Если кодер передает слово двоичного БЧХ-кода

C{x)=Cix\

а шум в канале задается вектором

£ (ж) = 2 Eix\ то полученное слово записывается многочленом

R (ж) ="S RiX - "S Cix +"S Eix\

i=0 i = 0 i=0

Для 7 = 1,2, . • •, 2i кодовое слово кратно минимальному многочлену элемента а и, следовательно,

R (а) = О -Ь "S Eia = S = S3,

i = U f"-

з¥1

Определим многочлен со (z) = 2 <»ft2 с помощью равенства

ft=0

(7.22)

(z)=a(z)+ SZ,z П (l-Xjz).

1=1 Зф1

где элементы ноля Галуа Х, Х, . . ., Хе ~ локаторы ошибок Ei = 1. Как было показано в разд. 5.2, Sj = R (а) = г<-) (а), где г(ж) - остаток от деления R (х) на минимальный многочлен МО (х) элемента а (1 < / < 2t). После вычисления S, S, . . . . . ., Sit основная задача декодера - определить Х, Х, . . ., Xg из уравнений

Z--=5,-, / = 1, 2, 2t.

В общем случае эта система имеет много решений, каждое из которых соответствует различным векторам ошибок, лежащим в одном классе смежности по аддитивной группе кодовых слов. Декодер должен найти решение с наименьшим возможным числом е.

Для решения системы декодер сначала пытается определить коэффициенты многочлена локаторов ошибок (7.21) (см. также уравнение (1.46)).

7.21. Определение

a(2)=ri {i-Xiz)=.l+j]ajz\ •

»=i }=i

Если многочлен а (z) уже найден декодером, то, используя процедуру Ченя, можно найти взаимные корни для а (z). Ошибки после этого могут быть исправлены с помощью схемы, изображенной на рис. 5.14. Наиболее тяжелая часть этой процедуры - определение коэффициентов oj по величинам Sj.

Для того чтобы найти зависимость между величинами Oj и Sj, введем производящую функцию

j=i 3=1 t=i i=i

После умножения на a(z) имеем

S (Z) а (Z) = 2 П (1 Z,z) = 2 Z,z П (1 - Xjz).

i=l 3=1 i=l 3Vi

Прибавив к обеим частям равенства a(z), получим

[l + S (z)] а (z) = а (z) + S Zz Д (1 - Xjz).



188 Гл. 7. Двоичные БЧХ-коды, исправляющие многократные ошибки Тогда

[1 + 5 (2)] а (z) = (о (z).

В общем случае декодеру известны коэффициенты только при первых 2t степенях z в .S" (z) и не известны коэффициенты St+i «г+з» 524+3, .... Иными словами, декодер не знает S (z), но знает S (z) mod z+. Поэтому естественно ввести уравнение, которое мы назовем ключевым:

(7.23)

[1 + 5 (z)] а (z) = со (z) mod z+i.

Из этого уравнения по заданному S (z) нужно найти оба многочлена а (г) и (о (z), степени которых не превосходят е, где е - число ошибок в канале.

Одна «физическая интерпретация» ключевого уравнения была предложена Месси [1968]. Перепишем уравнение в виде

-5(1+ S 0Sft-i + (Tft = Wftf

или в виде

ft-i

5fc=cuft- S OiSh-i - Ok

Последнее равенство задает к-ж выход регистров сдвига, приведенных на рис. 7.1 и 7.2, обратные связи которых соответствуют многочлену а {£), а начальное состояние ячеек - многочлену со (г). Это


Выход

Итальнае-Г „ состояние »2

Рис. 7.1. Интерпретация ключевого уравнения с помощью регистра сдвига

с обратной связью.

позволяет интерпретировать ключевое уравнение как математическую постановку задачи синтеза регистра с обратной связью: по заданной выходной последовательности 1 + 5 (z) необходимо определить обратные связи 0 (z) и начальное состояние со (z) кратчайшего (наименьшего) регистра сдвига с выходной последовательностью 1 + 5 (z).

В задаче декодирования двоичных БЧХ-кодов реальный интерес представляет только многочлен о (z), а не многочлен со (z). Однако это же ключевое уравнение возникает и в некоторых других приложениях. Мы вернемся к нему в гл. 9 и 10, где оно интерпретирует-

Начальное аютояние Выход Д


Рис. 7.2. Другая интерпретация ключевого уравнения с помощью регистра

сдвига с обратной связью.

ся как задача синтеза регистров с обратной связью, и оба неизвестных многочлена 0 (z) и а» (z) представляют непосредственный интерес.

Рассмотрим теперь алгоритм решения ключевого уравнения над произвольным полем.

7.3. Эвристическое решение ключевого уравнения

Нам надо решить ключевое уравнение (7.23) (l + 5)0 = o)modz2+i

относительно многочленов 0 (z) и © (z) при заданном многочлене S (г) mod z+. Разобьем эту тяжелую задачу на ряд этапов. Рассмотрим последовательность уравнений

(7.301) (1 + S) о<*> = (о<*> mod z*+i

и для каждого А = О, 1, 2, . . ., 2 найдем многочлены, удовлетворяющие этим уравнениям. В общем случае они могут иметь много решений. Так как степень а (z) равна числу ошибок, то хороший декодер должен попытаться найти решение с «малыми» степенями 0 и (В.

Если уравнения (7.301) уже решены, то та же пара многочленов <о(*) и о*), вообще говоря, не удовлетворяет сравнению

(1 + S) 0W = (о<) mod г+з.

(1+5) 0W = аW + z+i mod z+,

)фициент при z в произведени] Если Д][ = О, то, очевидно, можно положить ot***) = ot)

Однако (7.302)

где AJ - коэффициент при 2*+ в произведении (1 + 5) а-К



И й)(+) = «>(). Для определения а(+) в случае, когда Д" Ф О, введем вспомогательные многочлены т() и y<), которые определяются как решения вспомогательного уравнения

(7.303) (1 +5) тС) = 7"+2" mod 2"+!.

При этом, конечно, желательно, чтобы степени многочленов т") и у) были малыми. Определим последовательности {а} и {со} с по-мош;ью вспомогательных многочленов т и у равенствами

(7.304) aC+i) =aV)-fzx~),

(7.305) (oC+i) = coW -

Легко видеть, что многочлены о***) v co(+) удовлетворяют сравнению

(1 + 5) aC+i) = coC+i) mod z+D+S

если cr() и <»() - решения сравнения (7.302), а т() и у> - решения сравнения (7.303).

Суш;ествуют два очевидных способа задания многочленов т") и v*")- Либо

(7.306) либо

(7.307)

ZY),

(ft)

Если at) и cot) удовлетворяют сравнению (7.302), а т**) и уС**) удовлетворяют (7.303), то многочлены (7.306) и (7.307) удовлетворяют сравнению

(1 + 5) tC+i) == vC+i) + z+i mod z+2.

Если AW = 0, to выражения (7.307) не определены и нужно использовать формулы (7.306). Если AW Ф О, то выбор между (7.306) и (7.307) должен основываться на минимизации степеней т) и yi-). Степени многочленов о), т**), (й<) и у) задаются следуюш;ими соотношениями:

(7.308) degoC+i)

degaW, если A*i = 0 или если dega()>degT() + l;

1-1- degtW, если -фО и если deg тС») > deg - 1;

dega(+i)<

любое из пре-дыдуш;их чисел

[ ,если Af=50 и если J dego() = l+degT<);

(7.309) degxC+i).

(7.310) degco(+i) =

\ l + degTW, если выбраны (7.306);

[ degаС), если выбраны (7.307);

degcoW, если Ai = 0 или если

degco()> 1 + degv

l+degyC), если AfO и если degv()>degcoW -1;

, ,ь4.п / любое из нре- \ .(ft) , л

+<\дыдущих чисел ).еслиЛ\=0 и если

degoW = 1 +degYW;

(7.311) degv(+i) =

l + degYC*), если выбраны (7.306); deg&)(), если выбраны (7.307).

j(A+l)

Степень многочлена ai"") может случайно увеличиться, еслж deg ot) = 1 + deg т() и старшие коэффициенты многочленов а> и А) т() равны. Для того чтобы избежать таких случаев, мы при выборе между (7.306) и (7.307) будем учитывать не степени многочленов а), т(), (о() и у), а некоторую числовую функцию D (к), которую определим следующим образом:

(7.312) (7.313)

deg оС) < D (к), deg Tt") k-D (к).

В силу соотношений (7.308), (7.312) и (7.313) можно дать следующее рекурсивное определение функции d (к):

(7.314) D{k+l) = -{

D{k), если Af> = 0

если D{k)>-±;

k-\-D{k),

если AitO и £)(А;)<У:1,

Легко видеть, что если deg о) Z) (А;) и deg т) к - D (к)у то deg а(+1) D (к -\- 1). Аналогично, если deg ©f) < D (к) и deg Y") k-D (к), то deg со+М D (к + 1).

Для того чтобы обеспечить неравенства deg т*) (А; + 1) - - £» (А; + 1) и deg y- < (А; + 1) - D (А; + 1), введем следующее правило выбора между (7.306) и (7.307):

(7.315) Выбрать

(7.306), если

о или если D {к) ">

(7.307), если АфО и £>(А;)<




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

0.0227