ГЛАВА 11. БЫСТРЫЕ АЛГОРИТМЫ

Хорошие коды с большой длиной и большим объемом алфавита, такие, как кода Рида Соломона, находят все более широкое применение. В будущем потребуются еще более длинные коды, контролирующие ошибки, и поэтому задача уменьшения сложности алгоритмов декодирования становится важной. Мы уже рассмотрели некоторые эффективные алгоритмы декодирования кодов Рида-Соломона и связанных с ними кодов и знаем, как строить декодеры, содержащие порядка вычислений.

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

11.1. ЛИНЕЙНАЯ СВЕРТКА И ЦИКЛИЧЕСКАЯ СВЕРТКА

Линейная свертка

может быть также записана в виде произведения многочленов

Стандартный способ вычисления произведения двух многочленов требует примерно умножений и

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

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

Циклическая свертка может быть записана в виде

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

и, таким образом, циклическую свертку можно вычислить, последовательно применяя преобразование Фурье, покомпонентное умножение и обратное преобразование Фурье. Если представляется произведением большого числа сомножителей, то быстрое преобразование Фурье (БПФ), которое будет описано в следующем параграфе, позволяет снизить число вычислений. Преобразование Фурье в поле существует только для целых делящих число и некоторые из этих не допускают алгоритмов БПФ. Но в теории обработки дискретных сигналов хорошо известны методы удлинения векторов и с до такой длины что компоненты с индексами сохраняют нужные значения, а вектор с связан с векторами соотношением циклической свертки, вычисляемой, однако, на длине удобной для применения алгоритмов БПФ.

Возьмем, например, удовлетворяющую условию длину на которой легко вычислить преобразование Фурье, и положим

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

Разработаны методы сведения длинной линейной свертки к множеству коротких циклических сверток. Опишем метод, оказавшийся чрезвычайно полезным в обработке дискретных сигналов и известный под названием метода перекрытия с накоплением. Он применим также к длинным сверткам в полях Галуа.

Предположим, что имеется устройство, вычисляющее циклическую свертку длины и что мы хотим воспользоваться этим устройством для умножения многочлена степень А которого меньше , на многочлен степень В которого больше чтобы получить произведение с По имеющемуся многочлену сформируем множество многочленов степень каждого из которых не превосходит по следующему правилу:

где выбрано достаточно большим для того, чтобы были представлены все коэффициенты многочлена Отметим, что коэффициенты построенных многочленов перекрываются. Пусть

Коэффициенты многочлена с за исключением первых А коэффициентов, содержатся среди коэффициентов многочленов а именно

и т. д. А младших коэффициентов многочлена с теряются. Во многих приложениях при вычислении линейной свертки нужны не все коэффициенты выходного многочлена, и тогда описанная

процедура может быть удовлетворительной. Если же нужны все коэффициенты выходного многочлена с то в проделанных выкладках следует просто заменить многочлен многочленом Это позволит вычислить все необходимые коэффициенты, но все индексы будут сдвинуты на число А.

Каждая циклическая свертка, за исключением последней, дает коэффициентов линейной свертки и А бесполезных коэффициентов, которые отбрасываются. Так как степень многочлена может быть меньше, чем то последняя свертка может давать больше, чем значимых коэффициентов.