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

[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]

I 9.3. РАСШИРЕННЫЕ коды РИДА-СОЛОМОНА 301

из 2 i компонент синдрома начинается с компоненты S, равной 1 „, и заканчивается компонентой S-2t, равной Vf+2t-i - v. Предположим, что произошло не более t ошибок, и проведем итерации алгоритма Берлекэмпа-А1есси от до Su-i- Если L2t 2 < <: - 1 и невязка Agjj равна нулю, то, согласно теореме 7.5.3, во внутреннем векторе произошло не более t- 1 ошибок и вычисленное значение многочлена локаторов ошибок правильно. В противном случае во внутреннем векторе произошло t ошибок, и, следовательно, символ правилен. Дополнительная компонента синдрома Sat позволяет продолжить алгоритм Берлекэмпа- Месси еще на один шаг, так что полное число итераций равно 2t, и поэтому найден многочлен локаторов t ошибок. Декодер для расширенного на одну позицию кода Рида-Соломона показан на рис. 9.5.

Декодер для расширенного на два символа кода Рида-Соломона более сложен и описать его труднее. Предположим, что произошло не более t ошибок. В нашем распоряжении имеются 2t- 2 компонент внутреннего синдрома, начиная с компоненты Si, равной Vj+i. Согласно теореме 7.5.3, воспользуемся ими для исправления 2t-2 ошибок во внутреннем векторе и обнаружения i ошибок. Иначе говоря, начиная с S и выполняя 2t-4 итераций алгоритма Берлекэмпа-Месси, найдем многочлен локаторов ошибок. Если /.24 4 < t- 2, то сделаем еще две итерации и остановимся, если хотя бы одна из невязок A2t 3 или A2t-2 отлична от нуля. Если обе невязки равны нулю, то во внутреннем векторе произошло не более 2t-2 ошибок. В этом случае многочлен локаторов ошибок вычислен правильно и может быть использован для дальнейшего исправления ошибок во внутреннем векторе. Так как полезная информация может быть полностью выделена из внутреннего вектора, то декодирование закончено. В противном случае внутренний вектор содержит f- 1 или t ошибок, и поэтому искажено не более одного граничного символа. Следовательно, хотя бы одна из компонент So и

-24-1 синдрома правильна, а если все ошибки произошли во внутреннем векторе, то они правильны обе. Присоединяя сначала одну, а затем вторую из них к остальным компонентам сшщрома, получим два блока по 2t- 1 символов, хотя бы один из которых содержит 2t- 1 правильных компонент синдрома.

Теперь дважды применим алгоритм Берлекэмпа-Месси, сначала к одному из этих блоков (от So до а затем к другому (от Si до Sat.i). Каждый раз будем исправлять t- I и обнаруживать t ошибок. Если все ошибок расположены во внутреннем векторе, то обе попытки позволят обнаружить t ошибок во внутреннем векторе, и, следовательно, оба символа расширения являются правильными. Если при одной или при обеих попытках не обнаруживается t ошибок, то во внутреннем векторе произошло



Начальные значения:

л№) =bfjc) = 1 L = r=0. e = l

Hera



Да-вычисление граничной компоненты синйрома Вля

слейугащего

шага

Г(д:)-Л(х)-А;.х£Сх)


Л(х)-7№)

Lr-L A(x}-r(j:)


;• =0,...,п-1

Cmon-исправление закончено

Рис. 9.5. Декодер для расширенного на один символ кода Рида-Соломона.

только t- 1 ошибок, и, следовательно, многочлен локаторов ошибок вычислен правильно и может быть использован для исправления внутреннего вектора. Так как информация может бьггь полностью извлечена из внутреннего вектора, декодирование закончено.



Наконец, если во внутреннем векторе обнаружено t ошибок, то оба граничных символа правильны. Следовательно, и обе граничные компоненты синдрома также правильны, и в нашем распоряжении имеется 2t правильных компонент синдрома, позволяющих исправить / ошибок во внутреннем векторе.

Описанная процедура декодирования все же дважды обращается к алгоритму Берлекэмпа -Месси. Такое описание выбрано из соображений простоты объяснения; процедуру можно сделать более компактной.

9.4. ДЕКОДИРОВАНИЕ РАСШИРЕННЫХ КОДОВ БЧХ

Теперь мы можем описать декодирование расширенных на два символа кодов БЧХ, определенных в § 8.5. Если конструктивное расстояние d кода является нечетным числом, то представленный в расширении поля код со своими хвостами образует подкод кода Рида-Соломона, и можно использовать уже описанный декодер для расширенного на две позиции кода Рида-Соломона. Если конструктивное расстояние кода четно, то к одному из хвостов добавим проверку на четность. Пока еще без доказательства мы утверждаем, что эта процедура приводит к коду, минимальное расстояние которого не меньше d \. Докажем этот факт, выписав соответствующий алгоритм декодирования. Декодер аналогичен декодеру для расширенного на два символа кода Рида-Соломона.

Теорема 9.4.1. Расширение на два символа двоичного кода БЧХ с четным конструктивным расстоянием d при использовании дополнительной проверки на четность на одном из хвостов приводит к коду, минимальное расстояние которого равно по меньшей мере dj-f 1.

Доказательство. Пусть t=d/2. Построим декодер, исправляющий ошибок. В нашем распоряжении имеются 2t-3 компонент внутреннего синдрома и две граничные компоненты синдрома So = V/„ - и Sts = V;„ 2/-2 - v+, которые правильны, если граничные символы v и не содержат ошибки. По предположению конструктивное расстояние d является четным числом, а в силу ограничений сопряженности числа /о и jo+t-2 должны быть нечетными. Эти требования выполняются только в том случае, когда /о < О и /о -f 2 i - 2 > 0. Следовательно, ограничения сопряженности гарантируют также, что Су-i = О и С;„+2; , = О, так как частоты (/о - 1)/2 и (/o+2i-1)/2 являются четными. Следовательно, мы имеем еще две компоненты синдрома, а именно .S i= V/„-i и St-i = Vj+zf-i-

Так как дополнительно содержит проверку па четность, ТО можно определить, четно или нечетно число произошедших




[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.0142