Следующая теорема утверждает, что кронекеровское произведение двух произведений матриц равно матричному произведению кронекеровских произведений соответствующих матриц.

Теорема 11.5.2. Если все матричные произведения определены, то кронекеровское произведение удовлетворяет равенству

(А X В) (С X D) = (АС) X (BD).

Доказательство. Пусть матрицы А, В, С и D имеют соответственно размеры 1хК, JxL, KxMrLxN. Так как матрица А X В содержит KL столбцов, а матрица С X D содержит KL строк, то матричное произведение (А X В) (С X D) определено. Оно содержит строк, которые мы занумеруем парами (г, /), и MN столбцов, которые мы занумеруем парами (т, п). Элемент, стоящий на пересечении строки (г, /) и столбца {т, п), равен ыьФцСтйщ. Так как матрица АС содержит / строк и М столбцов, а матрица BD содержит / строк и L столбцов, то матрица (АС) X (BD) также является ( X /С1-)-матри-цей. Стоящий на пересечении [i, /)-строки и [т, п)-столбца элемент этой матрицы равен

Ij ciihChm Ij bjidin = aiubjiCumdm, k I k, I

что и завершает доказательство. □

Кронекеровское произведение матриц применяется в теории преобразования Фурье. Пусть W и W" - матрицы преобразования Фурье соответственно длин п и п". Тогда

V = Wv и V" = W"v"

являются соответственно матричными записями преобразований Фурье

Двумерное (п X п")-преобразование Фурье двумерного сигнала [Vi-v] получается применением преобразования W к каждой строке с последующим применением преобразования W" к каждому столбцу. Считывая двумерный [п X п")-сигнал по строкам, можно преобразовать его в одномерный. (Возможно, что двумерный сигнал был предварительно сформирован из одномерного с помощью китайской теоремы об остатках. Считывание такого сигнала по строкам дает новое одномерное представление этого сигнала, которое получается из исходного одномерного сигнала перестановкой его компонент.)

Если предполагать, что одномерные пп"-точечные векторы {Vi-i"] и [Vii"] упорядочены описанным выше способом, то

двумерное преобразование записывается через кронекеровское произведение в виде

V = (W X W") V.

Для алгоритма Винограда преобразований длин п и п имеет место матричное разложение

W = BDA и W" = B"D"A",

где А, А", В и В" - матрицы целых чисел рассматриваемого поля, а D и D" - диагональные матрицы над GF (q). Умножения на D и D" описывают все умножения, которые приходится выполнять в алгоритме Винограда. Положим W = W X W" и дважды применим теорему П.7.2:

W = (BDA) X (B"D"A") =

= (В X В") (D X D") (А X А") = BDA,

где кронекероБские произведения В = В X В" и А = А X А" содержат только элементы из поля GF (р), а кронекеровское произведение D = D X D" опять является диагональной матрицей над GF (q). Следовательно, мы опять получили пп"-точечное преобразование Фурье в форме алгоритма Винограда БПФ. Это дает способ построения большого алгоритма Винограда БПФ из малых.

Из приведенного описания матрицы W видно, что такое преобразование предполагает предварительную запись (с помощью алгоритма Гуда-Томаса для взаимно простых множителей) пп"-точечного одномерного преобразования в виде двумерного преобразования с последующим считыванием преобразуемого двумерного вектора по строкам в виде одномерного пп"-точеч-ного вектора V. Следовательно, описанный способ вычисления пп"-точечного преобразования V = (BDA) v предполагает предварительную перестановку компонент вектора v и вычисление компонент вектора V также в переставленном порядке. Но поскольку вид матриц А и В известен, то тривиальная перестановка столбцов матрицы А и строк матрицы В позволяет выписывать компоненты векторов v и V в их естественном порядке.

Пусть М (п) и М (п") означают соответственное число умножений, необходимых для выполнения п- и п"-точечного БПФ по алгоритму Винограда. Тогда число М (п) умножений, необходимых для вычисления пп"-точечного преобразования по алгоритму Винограда, равно примерно М (п) М (п"). Более точно,

dim D = (dim D) (dim D"),

11.6. УСКОРЕННЫЙ АЛГОРИТМ БЕРЛЕКЭМПА- МЕССИ

В описанном в § 7.4 алгоритме Берлекэмпа-Месси требуемое число умножений на г-й итерации примерно равно удвоенной степени многочлена Л) (х). Так как степень многочлена Л) (х) имеет порядок г и в типичном случае равна г/2, а алгоритм содержит 2t итераций, то для его выполнения необходимо 2f умножений и примерно столько же сложений. Это квадратичная функция Кратко говорят, что алгоритм Берлекэмпа-Месси содержит число умножений порядка f, или, формально, О (fi) умножений. Для очень длинных кодов и большого f число умножений в алгоритме может стать обременительным. В настоящем параграфе рассматривается метод уменьшения вычислительной сложности алгоритма для длинных кодов при большом числе / исправляемых ошибок.

Ускоренный алгоритм обосновывается следующим образом. На начальных итерациях алгоритм Берлекэмпа-Месси в частотной области содержит умеренное число умножений порядка степени многочлена А (х). Но степень многочлена Л (х) возрастает до существенной доли длины п, и, таким образом, среднее число умножений на итерацию имеет порядок п. Преимущества ускоренного алгоритма связаны попросту с тем, что на ранних шагах несколько итераций в частотной области выполняются одновременно. После такого пакетного выполнения нескольких итераций полученный промежуточный результат используется для модификации синдрома путем ввода в него вычисленных в этом пакете многочленов А (х) и Б (х). Следующий пакет итераций Начинает выполнение алгоритма Берлекэмпа-Месси, сначала используя в качестве синдрома вычисленный модифицированный синдром и полагая в начальный момент Л (х) равным 1. Ускоренный декодер эффективен для декодирования длинных, но все еще практически применяемых кодов. В следующем параграфе будут рассмотрены другие, даже более эффективные декодеры.

И величины М (п), М (п") и М (п) не превосходят размеров матриц D, D" и D соответственно, так как один или более элементов диагональных матриц могут оказаться равными единице. Если учитывать все умножения диагональных матриц, включая и умножения на единицу, то получаем простую формулу

М(п) = М (п) М (п").