11.9. СВЕРТКА В СУРРОГАТНЫХ ПОЛЯХ

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

В простом поле циклическую свертку

можно заменить сверткой в кольце целых чисел; необходимо только позаботиться о выполнении вычислений по модулю Вид уравнения свертки при этом сохраняется, но арифметические операции выполняются в обычной целочисленной арифметике. Затем для получения свертки в поле найденные при вычислении целочисленной свертки компоненты надо привести по модулю это сводит задачу к вычислению только целочисленных сверток. Кольцо целых чисел можно далее вложить в подходящее поле, например комплексное. После этого целочисленная свертка может быть вычислена с помощью любого алгпритма свертки в поле комплексных чисел, например с помощью дискретного преобразования Фурье и теоремы о свертке. Практическое вычисление преобразования Фурье в поле комплексных чисел реализуется на словах конечной длины, что вносит в вычисления ошибку округления. Однако нетрудно подобрать такую длину преобразования, чтобы ошибка округления в компонентах всегда была меньше 0,5. Тогда округление каждой вычисленной компоненты в ближайшее целое число даст правильное значение целочисленной свертки. Переход в каждом целом числе к вычету по модулю даст затем правильное значение свертки в

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

Предположим, далее, что надо вычислять свертку сигналов над нолем где уже не является простым числом. Тогда каждое отдельное произведение элементов ноля можно рассматривать как свертку многочленов по модулю некоторого неприводимого многочлена Вычисление остатка по модулю этого

неприводимого многочлена производится тогда, когда все свертки вычислены. Исходная свертка при этом превращается в двумерную свертку.

Пусть векторы над Компоненты этих векторов задаются многочленами

над простым полем где представляют собой неотрицательные целые числа, меньшие Линейная свертка векторов записывается в виде

где характеристика поля, а некоторый простой многочлен степени Введем величины

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

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

Вместо поля комплексных чисел можно воспользоваться в качестве суррогатного поля любым конечным полем, даже с характеристикой, отличной от характеристики исходного поля. Для вычисления свертки двоичных последовательностей, длина которых не превосходит половины простого числа Ферма при или 16, можно использовать поле Последовательность над можно рассматривать как последовательность целых чисел, принимающих значения, равные только нулю и единице. Длина линейной свертки двух целочисленных последовательностей длины может быть больше но всегдв меньше Следовательно, линейная свертка в может быть вычислена как циклическая свертка в поле

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

Например, для непосредственного вычисления свертки в поле двух последовательностей длины требуется примерно битовых операций. Вместо этого можно воспользоваться сверткой в поле В этом поле для вычисления преобразования Фурье надо примерно 218 умножений сложений; для каждого умножения необходимо примерно битовых операций, а для каждого сложения — примерно 17 битовых операций. Таким образом, свертка может быть вычислена примерно за битовых операций.

Теперь предположим, что нам надо свернуть две последовательности в Как и ранее, можно представить элементы поля многочленами над GF (2). Если отложить операцию вычисления остатка по модулю до завершения всех других вычислений, то исходная свертка превратится в двумерную свертку. Эта задача может быть вложена в суррогатное поле если только длина свертки целых чисел не превышает т. е. если

Например, пусть надо вычислить линейную свертку двух последовательностей длины 8192 над Так как 8 (8192) меньше, чем то в качестве суррогатного поля можно воспользоваться полем Двумерную -точеч-ную линейную свертку можно вычислить через двумерную (-точечную циклическую свертку без потери членов. Эта (-точечная циклическая свертка может быть вычислена с помощью методов быстрого преобразования Фурье. -точечное преобразование вообще не содержит умножений, а содержит только циклические сдвиги. -точечное преобразование, как уже обсуждалось выше, может быть разбито с помощью алгоритма Кули-Тькжи БПФ на более короткие свертки. Для того чтобы воспользоваться теоремой о свертке, необходимо выполнить три преобразования, каждое из которых содержит 2048 умножений. В частотной области также необходимо выполнить умножений. Таким образом, для вычисления -точечной свертки над необходимо выполнить 268 288 умножений в поле

ЗАДАЧИ

(см. скан)

(см. скан)

ЗАМЕЧАНИЯ

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

Алгоритмы быстрою преобразования Фурье широко используются в обработке дискретных сигналов, начиная с известной работы Кули и Тьюки [19651. Однако другой подход к БПФ был предложен в более ранних статьях Гуда [19601 и Томаса [1963]. Взаимосвязь между БПФ и сложностью декодирования обсуждалась Юстессном [1976] и Серпентом [1977]

Основанные на прямых и грубых методах быстрые алгоритмы сверстки впервые были построены Агарвалом и Кули [1977]. Виноград [1978] предложил описанный в данной главе общий метод построения, а также доказал в полях вещественных и комплесных чисел не существует лучших алгоритмов сверстки. Он почти не обращался к полям Галуа, так как в этих полях умножения маскируются под сложения. Использование китайской теоремы об остатках для целых чисел, для разбиения длинных сверсток на короткие предложили Агарвал и Кули [1977]. Алгоритм Винограда БПФ был опубликован в 1978 г. Наше описание не следует оригиналу и связывает его с другими методами обработки сигналов. Алгоритм БПФ Винограда и другие эффективные алгоритмы обсуждал также Нуссбаумер [1981].

Применение БПФ-алгоритма Винограда для декодирования кодов Рида-Соломона рассматривал Миллер, Трусиг и Рид [1980].

Ускоренный и рекурентный алгоритм Берлекэмпа-Месси публикуются впервые, они были анонсированы в работе Блейхута [1981]. Использование в алгоритмах сверстки суррогатных полей предложили Препарата и Сервейт.