Главная страница  Дискретный канал связи 

[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] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [ 101 ] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

для / = 2+ 1, п -{-2t, где п = q" - 1. Число различных корней многочлена Л (х) в поле GF {q"") равно степени этого многочлена тогда и только тогда, когда En+j)) = Ej для всех j = = 1, 2t.

Доказательство. Предположим, что число различных корней многочлена Л (х) в поле GF {q") равно его степени. Тогда Л (х) делит х" - 1 и существует многочлен Л" (х), такой, что Л° (х) Л (х) == х" - 1. Следовательно, так как

1] AEj = О,

то выполняется равенство А (х) Е (х) = О, и, таким образом, Л" (х) Л (х) £ (х) = (х" - 1) £ (х) = 0. Отсюда вытекает, что Е; = £((„+/)) для всех /.

Обратно, предположим, что Е] = Еп+п) Для всех /. Тогда (л:" - 1) Е (х) = 0. Но по условию Л (х) представляет собой такой ненулевой многочлен наименьшей степени, что Л (х) Е (х) = = О (mod X" - 1). Согласно алгоритму деления

(х"- l) = A(x)Q(x) + r(x),

так что

(х" - 1) £ (х) = Л (X) Е (X) Q{x) +г (х) Е (х).

Следовательно, г (х) £• (х) = О (mod х" - 1). Но степень г (х) меньше степени Л (х), так что многочлен г (х) должен быть равен нулю. Следовательно, многочлен Л (х) делит х" - 1 и все его корни являются корнями многочлена х" - 1. □

Если нарушается хотя бы одно из двух условий, т. е. если £j Ф £((«/)) для некоторого / или En+j)) ф Ej для некоторого /,

то обнаруживается конфигурация более чем из t ошибок.

Иногда желательно декодировать за пределами конструктивного расстояния. Небольшое продвижение за конструктивное расстояние дает продолжение алгоритма Берлекэмпа-Месси после 21 итераций. Основная идея состоит во введении дополнительных неизвестных синдромов (или дополнительных невязок) и аналитическом продолжении алгоритма декодирования, при котором многочлен ошибок вычисляется как функция от этих неизвестных. Затем, придавая этим неизвестным различные возможные значения, методом проб и ошибок в поле символов кода разыскивается вектор ошибок минимального веса. К сожалению, сложность этого метода очень быстро растет с отходом от конструктивного расстояния, так что его можно использовать не всегда.



Тем не менее описанный выше метод применим во многих случаях; укажем некоторые из них.

1. Двоичные коды БЧХ, у которых проверочные частоты образуют блок длины 2t, но истинное минимальное расстояние превосходит 2 i -Ь 1 • (Одним из примеров такого кода является код Голея. Другой пример дается (127, 43, 31)-кодом БЧХ, конструктивное расстояние которого равно только 29.)

2. Циклический код, проверочные частоты которого не образуют непрерывного блока.

3. Декодирование некоторых ошибок веса -- 1 в коде Рида- Соломона или коде БЧХ, исправляющем t ошибок.

4. Декодер для альтернантных кодов.

Такое продолжение алгоритма можно строить как во временной, так и в частотной области, а также некоторым смешанным способом. .Можно строить одновременно и многочлен локаторов ошибок Л (х) (или %{х)), и многочлен ошибок е (х). Сложность этого процесса зависит от подхода. Если символы кода лежат в подполе поля локаторов ошибок, то схема, в которой сначала вычисляется многочлен локаторов ошибок, приводит к неопределенностям, разрешить которые можно только вычислением соответствующих многочленов ошибок и проверкойпринадлежности их компонент полю символов кода. В этом случае разумно ввести в вычисления дополнительные проверки, позволяющие сразу ликвидировать неопределенные ситуации при построении Л (х).

Начнем с рассмотрения кода Рида-Соломона над GF (q) с конструктивным расстоянием 2--1- Произвольный многочлен Л (х) степени t v с t + v различными корнями в GF (q) представляет собой допустимый многочлен локаторов ошибок, если

"ЁлЛ- = 0. r=l+/ + v, 2/.

Такой многочлен наименьшей степени с Ло = 1 (если он является единственным) соответствует кодовому слову, находящемуся на наименьшем расстоянии от принятого слова. Если степень этого многочлена не выше t, то он будет вычислен алгоритмом Берлекэмпа-Месси. Но даже если произошло больше, чем ошибок, а многочлен наименьшей степени с указанными свойствами является единственным, то принятое слово может быть однозначно декодировано, коль скоро этот многочлен найден. Для кода Рида- Соломона нет необходимости вычислять величины ошибок, так как ошибки всегда лежат в поле GF (q). Если многочлен наименьшей степени не является единственным, то имеется несколько возможных конфигураций ошибок одного и того же веса, и все они согласуются с принятым словом.



Предположим, что произошло t + I ошибок; тогда, чтобы вычислить Л {х), достаточно найти две неизвестные компоненты синдрома 52+1 и 52+2 или две невязки A2;+i и А2;+2.Итак, продолжим аналитически алгоритм Берлекэмпа-Месси на две итерации с двумя неизвестными значениями невязки. Имеем

(2t+2)

А2;+5б2;+2

- Д2;+2Л

. A2;Vl2if+l

- A2;+lX 62+1 X .

Л< (X)

где неизвестные удовлетворяют условиям 211, A2i2 € GF (q); 2t+i, 2t+2 6 0, 1. Bee остальные величины в правой части известны по 2 синдромам. Преобразование частотной области во временную дает

y{2t+2) l){2t+2)

A2t+22i+2

- Аг+гИ б2;+2а~

1 - Aa+ia

A2;4-l62;+I 62;+ia

где мы воспользовались тем фактом, что если Ej - Ej-\, то обратное преобразование удовлетворяет равенству е] = aei. Теперь, если возможно, мы должны выбрать неизвестные так, чтобы вектор ошибок содержал не более / -Ь 1 ненулевых компонент. Рассмотрим два возможных случая ):

(1) = ЯР" - Л,а--ЬР" - A2a-W\

(2) = If - A,a-bf - A.jx-V\

где в первом случае Ау и А.2 - константы, не равные одновременно нулю, а во втором случае Ау отлично от нуля. При Яр"" = О каждое из этих уравнений надо разрешить относительно А и А для ровно t + 1 значения индекса /. Это даст локаторы -Ь 1 ошибок, и дальнейшее декодирование может быть завершено как декодирование стираний.

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

Имеются в виду две возможности, задаваемые уравнением для первой компоненты предыдущего векторного равенства при Sgj+x = 0 и Ьц-г ~ соответственно. - Прим. перев.




[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] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [ 101 ] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

0.02