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

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

1) Это утверждение (и аналогичные ему утверждения ниже) основывается на том, что, как уже было указано, при оценке числа операций алгоритма Винограда не учитываются операции в базовом поле GF (р); если GF (р) = GF (2), то умножений по существу нет. ~ Прим. перев.

Алгоритм Винограда для свертки основан на вычетах Си (х) = Rbf (х) [с {х)\, k = I, S.

Вычисление циклической свертки разбивается на два шага. Сначала вычисляются вычеты для k = I, s:

Ch (х) = g(x)d (х) (mod bh (x))

= gh (x) dh (x) (mod bh (x)).

Вычисление вычетов gh (x) и dh (x) не требует умножений

Согласно китайской теореме для многочленов, выражение для многочлена с (х) через эти вычеты дается формулой

с (х) = &1 (х) Ci(x) + ... + us (х) Cs (х) (mod b (х)),

причем все многочлены (х), (х) являются многочленами

над GF (р). Так как коэффициенты многочленов ah (х) принадлежат простому полю GF (р), этот последний шаг также не требует умножений. Только для вычисления коротких сверток, задаваемых произведениями многочленов gh (х) dh (х), требуется производить умножения в поле GF (q); так как оба многочлена gh (х) и dk (х) имеют deg bh (х) коэффициентов, то обычный метод умножения многочленов приводит к оценке необходимого числа умножений в виде суммы

t [iegbh{x)r. ft=i

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

Одна из модификаций алгоритма Винограда вычисления свертки состоит в выборе многочлена b (х) степени несколько меньше нужной. Тогда описанная процедура приводит к неправильному значению свертки, но ее можно подправить несколькими дополнительными вычислениями. Это делается следующим образом. Согласно алгоритму деления,

с(х) ==Q(x)b (X) + RbM [с(х)].

Если deg b (х) > deg с (х), то многочлен-частное Q (х) тождественно равен нулю, и ситуация аналогична рассмотренной выше. Если deg b (х) deg с (х), то алгоритм Винограда приводит к вычислению только остатка Rb{x) [с (х)]. Член Q (х) b (х)



можно вычислить с помощью дополнительных операций. В простейшем случае deg b (х) = deg с (х) и степень Q (х) должна равняться нулю. Если b (х) представляет собой приведенный многочлен степени N, то, очевидно, коэффициент при х в многочлене с (х) равен Q (х) = Cif. Следовательно,

с (Х) = CN b (Х) + Rh (X) [с (X) ],

где Cff легко вычисляется как произведение старших кс£(фицк-ентов многочленов g (х) и d (х).

Для вычисления циклической свертки длины п можно сначала вычислить линейную свертку, а затем выполнить приведение по модулю X" - 1. Однако, как правило, лучше сразу выбрать b (х) равным х" - 1, и приведение по модулю л;" - 1 производить в процессе применения китайской теоремы об остатках. В случае линейной свертки степень многочлена b (х) должна быть больше суммы степеней многочленов g (х) и d (х), в то время как степень многочлена х" - 1 может быть намного меньше. В этом случае либо многочлены, по модулям которых производятся вычисления, имеют меньшие степени, либо число таких многочленов меньше. С другой стороны, простые делители многочлена X" - 1 заранее фиксированы, а делители многочлена b (х), хотя степень его и выше, могут быть выбраны так, как нам удобно; взаимно простые делители многочлена b (х) даже не обязаны быть простыми.

На рис. 11.1 приведены некоторые алгоритмы циклической свертки в полях характеристики 2, построенные с помощью рассмотренных методов. В компактной матричной форме эти алгоритмы записываются равенством

c=.B[(Cg).(Ad)],

где Cg и Ad - векторы одинаковой размерности, а [(Cg)- (Ad) ] - их покомпонентное произведение. Матричное представление этих алгоритмов однозначно, но последовательность выполнения сложений не регламентирована. При разумном упорядочении сложений и использовании частичных сумм можно также минимизировать число сложений. Если многочлен g (х) фиксирован, то вектор Cg может быть вычислен заранее. Тогда алгоритм вычисления свертки можно записать в виде с = BGAd, где G представляет собой диагональную матрицу, на диагонали которой выписаны компоненты вектора Cg. В качестве примера такой формы алгоритма циклической свертки на рис. 11.2 выписан алгоритм четырехточечной циклической свертки.

Данный параграф мы завершаем простым примером построения кодера для (7, 3)-кода Рида-Соломона. Эта простенькая задача не позволяет в полной мере продемонстрировать мощь рассматриваемого метода, но зато дает возможность легко про-



Двухточечная циклическая свертка, 3 умножения

1 1 (Г

1 0 1

1 о

I 1

Трехточечная циклическая свертка, 4 умножения

(Oil I I О I 1110

1 I r

0 I I

1 1 0

.1 0 I.

1 1 г

0 I I

1 I 0

1 0 Ij

Чтырехточечная циклическая свертка, 9 умножений

10 1 I о о о о 1 1 о 1 о I о о I о

I 10 10 0 10 0 1 10 0 1 10 0 0

мм"

"l 0 0 о"

»1

1010

0 0 11

10 10

0 10 1

10 0 1

10 10

М 0 0

10 0 0

0 10 0

0 0 10

0 0 0 .1

Пяглишсчечнйй циклическая свертка, 10 умножений

10 1 1 о 1 о о 1 М о 11 о о о 1 I 1 10 0 0 10 1

м м м м о

0 1110 0 0 11

м 11 г

10 0 0 1 0 10 0 1 0 0 10 1

0 0 0 11

1 10 0 0 0 0 110 10 10 0 0 10 10

мм о

Рис. 11.1. Алгоритмы коротких сверток

м м Г

о"

10 0 0 1

0 10 0 1

0 0 10 1

У".

0 0 0 11

1 10 0 0

0 0 110

10 10 0

0 10 10

м м 0„

следить работу алгоритма. Более того, мы не будем пытаться построить наиболее эффективный алгоритм, а опишем такой путь построения алгоритма, который даст возможность проиллюстрировать многие идеи.

Для (7, 3)-кода Рида-Соломона с порождаюш.им многочленом g- (х) = X* + ал; + + ах + степень многочлена d (х) не превосходит двух. Для непосредственного вычисления g (х) d (х)




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