Главная Помехоустойчивое кодирование



о, 0) слева на матрицу Ф7 ФМС-преобразования длины q - I простоты вектор v усечен до пяти компонент, а матрица Ф7 строк), получим

"1

1 "

5, GF(2).

5) = F

= 7 (для до пяти

Таким образом, убеждаемся, что полином v(x) имеет корни ft** = 1, а* = 2,»* = 5, = 6.

Вычисление циклической свертки с помощью ФМС-преобразования.

Циклическая свертка длины п двух векторов g nd или двух полиномов g(x) ис?(л), например кодовое слово с(х) =g(x)d(x) по модулюУ- 1, может быть найдена согласно следующему укрупненному алгоритму:

а) вычислить ФМС-преобразование G и D для каждого вектора (полинома) g,dB отдельности;

б) осуществить покомпонентное умножение G*D векторов (полиномов) изображений G и Dy где звездочка * - символ покомпонентного умножения;

в) взять обратное ФМС-преобразование от G*D\ полученный в результате вектор и является искомым произведением.

Конечно, ФМС-преобразование от порождающего полинома g{x) вычисляется один раз для всех кодовых слов; конкретнее этот и другие аспекты процедуры кодирования - декодирования будут рассмотрены далее. Здесь же приведем пример вычисления циклической свертки трехкомпонентных векторов (ПО) и (101), напомнив, что их свертка уже вычислялась вьппе прямым методом ( см. рис. 4.8, б).

Так как в поле GF(2) нет элемента 3-го порядка - см. табл. 3.14, то выберем какое-нибудь поле, например GF(2), содержащее такой элемент; это элементы о? = 6иа° = 11 (см. табл. 3.14). Примем в качестве ядра ФМС-преобразования со = 6. Соответствующие матрицы прямого и обратного ФМС-преобразования имеют вид:

г со"

со"

со"

"1

со"

со=*

со"

со-*

, GF(2*);

г со"

со"

со" 1

"1

со"

со"

со-"

GF (2 );



Таким образом,

С=Тф = (110); of Ф = (11, 6,0); C=G*d= (И, 6,0);

с = ф-1 С = (6 + 11, 6 - И + 1Ь 6, 6- 6 + И • 11) = (1,0, 1),GF(2*),

что совпадает с результатом, полученным на рис. 4.8, 6 .

Согласно представлению (4.19), если вектор С трансформировать С = (6, 11, 0), то обратное ФМС-преобразование можно найти с по-

мощью матрицы Ф, т. е. с = С Ф = 101.

Для тренировки читатель может воспользоваться также выражениями (4.15)-(4.18).

Следует обратить внимание на то, что хотя компоненты и входных векторов (110), (101) и конечного результата их циклической свертки (101) лежат в поле GF (2), так как принимают всего два значения: О и 1, компоненты промежуточных результатов принадлежат расширенному полюСГ(2*).

Другие методы вычисления сверток рассмотрены ниже.

Быстрые алгоритмы ФМС-преобразования. Использование матриц w иф для вычисления ДПФ и ФМС-преобразования требует порядка умножений (и порядка сложений). Известен [26, 37, 39, 45] ряд алгоритмов быстрого ДПФ и ФМС-преобразования (БПФ), требующих примерно wloga « умножений. В основе БПФ лежат три главные идеи: а) использование тождеств, связывающих элементы поля; б) переход от ДПФ и ФМС-преобразования к циклической свертке (при простых п) ; в) факторизация (разбиение) матрицы ДПФ и ФМС-преобразования в произведение слабозаполненных матриц или переход от одномерного преобразования длины п к многомерному (при составном п). Например, в любом поле GF(2*), где >2 - целое число, существует элемент 13 порядка 3, т. е. т ф 0; при этом 13 + (3 + 13 = О, откуда /3 = 1 + /3. В частности, /3 = 6G GF(2*),/3 = И G GF(2*) и6+ И = 1, GF (2). Следовательно, матрица Фз ФМС-преобразования длины 3 может быть представлена в виде, показанном на рис. 4.9, а. Так что преобразование длины 3 требует одного умножения на константу /3 и пять сложений. Соответствующий алгоритм БПФ {п = 3) дан на рис. 4.9, б.

Предположим далее, что необходимо вычислить ФМС-преобразование длины 5 надполем GF(2*). Выбирая примитивный элемент у = 2 поля GF(5), вычислим:

= 2; 7=4; т=3; т* = 1. mod5. (4.21)

Соотношения (4.21) задают перестановку /12 3 4

2 4 3 1

(4.22)



Фз =

3. &2 +«0 =

4.&i+flo=o; 5.&3+fl2=i; 6.&3+fli=y42

Рис 4.9. Дискретное преобразование Фурье при п = 3: а ~ матрица; б - быстрое

преобразование Фурье

Применим перестановку (4.22) к строкам и столбцам матрицы Ф5, получаемой из матрицы Фз отбрасыванием строки и столбца, составленных из единиц. В результате, как показано на рис. 4.10, д, будет сформирована матрица-циркулянт Фц. Осуществим эту же перестановку р * координат векторов а иа и обозначимд * =р*{а) = (ага, aai); а* = р*(а) = (а2ь А4, аз, al). Тогда ФМС-преобразование длины 5 сведется к циклической свертке векторов bi, bi длины /2-1=4; причем один из указанных векторов совпадает с верхней строкой циркулянта Фц, а второй - равен рп{а*), где перестановка рп определяется соотношением (4.20) npnJCi = 2*2 ~ аъ ~ з>4 ~ i-

Таким образом, Z?i = {ot, о?, о?, а}), bi - (Дг» з» 4)-Воспользовавшись алгоритмом быстрой циклической свертки и учитывая ряд тождеств поля (2*), можно вывести [20] алгоритм БПФ (/2= 5), представленный на рис. 4.10, 6*

В § 4.1 использовался метод взаимно простых множителей для

факторизации матриц ДПФ. Здесь рассмотрим метод произвольных множителей.

Пусть /2 = /21/22

Пу и над полем GV{q = 2 ) существуют ФМС-

преобразования длин /21, П2

, /24, т. е. 9 - 1 делится на перечисленные

длины. Тогда матрица фп факторизуется следующим образом [26]:

Ф„ =Р

/ = 1

/)<>Ф>

р(ф<пг){2)ф{2) /)(м)ф(м) • • >

(4.23)

где р - матрица разрядно-инверсных перестановок (см. ниже); dj = - efj - единичная матрица, а потому сомножитель!)*опущенв правой

части (4.23); расшифровка слабозаполненных матриц Ф и их

компонент дана на рис. 4.11.

Матрица р формируется следующим образом. Столбцы матрицы р нумеруются числами n в системе со смешанным основанием, а ее строки - разрядно-инверсными числами т. е.



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 [54] 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.0116