Исследование временных характеристик работы кодера кода Рида-Соломона в частотной области в зависимости от типа ДПФ параметров кода
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
?ер, информационный вектор может быть такой: .Кодовый вектор, соответствующий информационному вектору, определяется как ДПФ вектора с ядром ?. Координаты кодового вектора задаются по правилутак как каждая компонента вычисляется как значение многочлена a(x) в точке : . Если a(x) - многочлен из информационной области, A(x) - многочлен из кодовой области, тогда дискретное преобразование Фурье с ядром ? (прямое) переводит многочлен из информационной области в кодовую, а дискретное преобразование Фурье с ядром (обратное) переводит многочлен из кодовой области в информационную а(х) А(х), .
4.2 Китайская теорема об остатках
Рассмотрим более детально формулу (4.1), задающую ДПФ над полем . Например, для того, чтобы вычислить ДПФ над полем вектора длины, требуется умножений в поле. Как известно, умножение является одной из наиболее затратных по времени операций, т.е. алгоритм ДПФ имеет сложность порядка O(. Известные алгоритмы многомерного преобразования Фурье, а так же БПФ (быстрое преобразование Фурье) позволяют снизить эту цифру до N*logN умножений. Данные алгоритмы основаны на следующей китайской теореме об остатках.
Теорема 4.2.1. (Китайская теорема об остатках, единственность)
Для заданного множества целых положительных попарно взаимно-простых чисели множества неотрицательных целых чисел
при, система сравнений
имеет не более одного решенияc в интервале
Теорема 4.2.2. (Китайская теорема об остатках, существование)
Пусть -произведение целых положительных попарно взаимно-простых положительных чисел, пусть и пусть удовлетворяют равенству , тогда единственным решением системы сравнений
будет
Эта теорема позволяет каждое число n, 0?n<M однозначно задать системой остатков по модулям , i=1, k.
4.3 Трехмерное преобразование Фурье в поле
Рассмотрим ДПФ длины N=255, ядром которого является примитивный элемент поля .
В этом случае, М=255=3517, =3, = 5, =17, так что n(, , ), где
, ,
Произвольный ненулевой элемент поля ) задается как степень примитивного элемента поля: = ,
Согласно (2)
= (,
, =, ==,
Где приняты обозначения: =, =,=
Более того, в силу попарной взаимной простоты модулей , если i(, ,) и j(, , ), то ij(, , ). Таким образом, формулу (4.1) определяющую ДПФ, можно переписать в виде:
, =, =
Это сразу подсказывает следующий алгоритм вычисления вектора по вектору . Сначала разбиваем координаты вектора на тройки чисел (прификсированных и ) и к каждой из них применяем 3-точечное преобразование с ядром =; это дает набор из 255 величин
, =, =.
Затем к этому вектору длины 255 применяется 5-точечное ДПФ с ядром = по правилу: координаты вектора группируются по 5 чисел (по фиксированным и ) и для каждой такой совокупности вычисляется 5-мерный вектор ,
, =, =.
Наконец, к вектору длины 255 применяется 17-точечное ДПФ с ядром =, приводящее к искомому 255-мерному вектору :
, =, =.
Описанный алгоритм вместо умножений при прямом вычислении по формуле (4.1) требует
умножений, где - число умножений, необходимое для выполнения i-точечного ДПФ, i=3,5,17. Аналогично выписывается и формула для числа сложений (кстати, напомним, что характеристика рассматриваемого поля равна 2, так что вычитание совпадает со сложением)
Экспериментально установлено, что переход от одномерной структуры к трехмерной, уменьшает время, требуемое на вычисление ДПФ примерно в 10 раз.
Таким образом, переход от ДПФ длины 255 к ДПФ длин 3, 5 и 17, каждое из которых вычисляется 255 раз в цикле, очень существенно понижает вычислительную сложность алгоритма.
Следующий наш шаг - полностью избавиться от ДПФ внутри циклов, заменив их на БПФ (быстрое преобразование Фурье) длин 3, 5 и 17, которые основаны как на свойствах поля , так и на свойствах алгоритмов быстрого умножения многочленов, заданных над конечным полем.
4.4 Быстрое преобразование Фурье БПФ длины 3
3-точечное ДПФ с ядром ? для вектора a=, a-0., a-1., a-2. задается формулой
A=(, A-0., A-1., A-2.)=
Так как ядро ? удовлетворяет тождеству 1+, то легко проверить непосредственно, что числа могут быть вычислены по правилу:
s-1.=, a-1.+, a-2., m-1.=?тАв, s-1., A-1.=, s-2.+, a-1., ,
которое содержит только одно умножение и 5 сложений (вместо 4 умножений и 6 сложений). Если , ?=, ?-3.=, ?-85.
4.5 Быстрое преобразование Фурье длины 5
5-точечное ДПФ с ядромзадается равенством
,
непосредственное вычисление по которому требует 16 умножений и 20 сложений. Использование только тождества на ядре (которое в данном случае имеет вид 1+++) дает 9 умножений и 21 сложение. Это достигается, например, следующим образом:
,
Аналогично,
,
,
и, наконец,
Дальнейшего уменьшения числа умножений можно добиться за счет перехода к циркулянту и использования полиномиальной свертки (ПС). Приведем необходимые сведения:
<