Дискретное преобразование Фурье

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

Отметим также, что выбор в теореме о свертке приводит к формуле типа равенства Парсеваля

.

Замечание.

Основываясь на этом свойстве ДПФ, возможен альтернативный вариант описания циклических кодов. Любое кодовое слово циклического кода может быть представлено в несистематическом виде как

,

где - информационный, а - проверочный полиномы. Во временной области коэффициенты кодового полинома определяются циклической сверткой коэффициентов информационного и порождающего полиномов

,

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

и последующим вычислением обратного ДПФ для спектра кодового слова.

Теорема 4.1.3. (Свойство сдвига)

Если последовательности и являются парой преобразования Фурье, то парами преобразований Фурье являются также и .

Доказательство

осуществляется непосредственной подстановкой.

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

Теорема 4.1.4.

(i). Элемент является корнем полинома тогда и только тогда, когда k-й частотный компонент равен нулю.

(ii). Элемент является корнем многочлена тогда и только тогда, когда i-й временной компонент равен нулю.

Доказательство

утверждения (i) очевидно, поскольку из непосредственной подстановки корня в полином имеем

.

Аналогичным образом доказывается и утверждение (ii).

На основании приведенной теоремы можно сделать следующее заключение. Поскольку любой кодовый многочлен содержит в качестве множителя порождающий многочлен, то корни порождающего полинома являются и корнями кодового. Тогда, согласно теореме 4.1.4, корням порождающего многочлена будут соответствовать нулевые спектральные компоненты кодовых слов на позициях . Следовательно, можно дать следующее альтернативное определение циклического кода. Циклическим кодом называется множество таких слов над конечным полем , у которых все спектральные компоненты, принадлежащие заданному множеству т.н. проверочных частот равны нулю

Кодовое слово кода Р-С длины и его спектр лежат в одном поле .Кодирование кода Рида-Соломона в частной области можно осуществить следующим образом: какие либо последовательных координат полагаются равными нулю, в остальных координатах записываются информационные символы. Например, информационный вектор может быть такой: .Кодовый вектор, соответствующий информационному вектору, определяется как ДПФ вектора с ядром α. Координаты кодового вектора задаются по правилутак как каждая компонента вычисляется как значение многочлена a(x) в точке : . Если a(x) - многочлен из информационной области, A(x) - многочлен из кодовой области, тогда дискретное преобразование Фурье с ядром α (прямое) переводит многочлен из информационной области в кодовую, а дискретное преобразование Фурье с ядром (обратное) переводит многочлен из кодовой области в информационную а(х) А(х), .