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



По соотношениям (4.37) можно построить комбинационную логическую схему на конъюнкторах и сумматорах по модулю 2 либо после преобразования соотношений по правилам алгебры логики ~ в ином элементном базнсе [25]. В табл. 4.3 приведены логические выражения в Ш-форме дли полевой свертки с = ab н ее компонент над полями GF(2) небольшой размерности н полиномами я (х), взитыми нз табл. 3.1.

Достоинством подобных множительных схем является высокое быстродействие: произведение с = ab получается за один такт подачн операндов а b я считывания результата с. Однако по мере увеличения размерности г используемого Поля GF(2), а следовательно, длины векторов tf, b, с количество слагаемых в выражениях для быстро нарастает и схема усложняется.

Оедуя работе [50], оценку сложности схемы будем производить по числу двухвходовых сумматоров (mod 2). Обозначим через Н(Г) вес двоичной матрицы Г. Нас, конечно, интересуют матрицы вида (4.28) лри замене в них десятичных номеров двоичными векторами соответствующих элементов поля. Например,

для поли GF(2), я(х) = х + х + 1, имеем:

w (г) = w

01 10

Тогда количество £ двухвходовых сумматоров по модулю 2 в логической схеме умножения двух элементов поля GF(2) может быть рассчитано по следующей формуле [ 1]:

£ = В/(Г) - г.

Таблица 4.3

Выражения для полевой свертки с = ab н компонент с,-

вполяхСР(2)

Размерность г

Свертка с = ab; d =

• •» o) {o* by c]

Компоненты с.

c= (Itfo +2tfi)uo + (2flo + 3fli)6i

c\ -Oq bi +1*0 +1*1 ; = Oq bo +tf 1*1

c = (ltfo + 2tfi +3tf2)6o +

+ (2tfo + 3ai +4tf2)*i +

+ (3flo +4й1 +52)2

2 ~ ОоЬг + 1*1 +"2*0 +"2*2;

Cj -aQb\ a\bo Ofbi -агЬу +

+ 2*2;

Co =яо*о +fli*2 г*!

с = (Itfo + 21 + 3tf2 + 4дз)6о + + (2flo + 3fli + 4tf2 + 5fl3)6i + + (3tfo + 4tf1 + Saj + бдз)bj + + (4flo + Sax + 6fl2 + 1аъ)Ьз

Сз =tfo*3 +1*2 +2*1 +fl3*0 +

C2 = 0 *2 + fl 1 * 1 + fl2 *o + fla *3 +

+ Азб2 +Аз*з;

Cj ~Яо*1 + 1*0 +1*3+2*2 +

+ tf2*3 +fl3*l +«3*2;

Co ~ flo*0 +tfl*3 + «2*2 + fl3*l



таблица 4,4

Ганкелевы матрицы Г, соответствующие им матрицы индексов ind (Г)

и веса wif) для полей GF(2), г = 2,,. 5

ind (Г)

+Х+ 1

1 1 1 2

+ х + 1

1 2 3

2 3 4

3 4 5

1 1 1

112 1 2 2

х* + X + 1

12 3 4

2 3 4 5

3 4 5 6

4 5 6 7

1111 1112

112 2

12 2 2

лг + х + 1

1,2 3 4 5

2 3 4 5 6

3 4 5 6 7

4 5 6 7 8

5 6 7 8 9

11111 11112 1112 2 112 2 2 1 2 2 2 3

Оценим веса матриц Г для полей GF(2) различной размерности г. Рассмот рим матрицу (4.28а). Ясно, что над побочной диагоналыо и на ней самой всегда расположены элементы от 1 до г, имеющие индекс (число единиц) 1. Это следует нз процедуры порождения полей характеристики 2. Индекс элемента г + 1 и последующих элементов определяется видом полинома nix), используемого для построения поля. Если этот Полином имеет вид п(х) = х * х u например, для полей размерностей г = 2, 3 4, 6,. 7, то все элементы под побочной диагоналыо имеют индекс 2. Следовательно,

Х= wir)~r=]-cl+2-c-r= у(г~ 1).

где С„ - число сочетаний из п элементов по два.

В табл. 4.4 приведены ганкелевы матрицы Г, матрицы индексов ind (Г) и веса Н(Г) матриц Г для полей GF(2) малой размерности г. Веса И(Г) и число сумматоров Г в множительных схемах для г = 2 ... 9 даны в табл. 4.5.

Таким образом, уже для полей средней размерности множительные схемы должны вьшолнятъся в виде больших интегральных схем (БИС).

Если один из сомножителей фиксирован (типичный случай в технике помехоустойчивого кодирования и цифровой обработки сигналов), то логическое выражение и соответствующая схема упрощается. Например, при умножении элемента а = (021 ао) на константу b = (bi bi bo) 1 = (1 О 1) e GF(2), получим C2 - tfo» 1 ~ fl2» Co == flo + fl 1-

В табл. 4.6 приведены логические выражения для синтеза умножителей на константы в полях небольшой размерности. Подставляя в формулу (4.36) b = а



Табли ца4.5

Веса матриц Н(Г) и количество сулшаторов в множительных схемах

для попей GF(2)

В(Г)

и учитывая закон идемпотентности аа = д,-, где у G ( О уц ~ цu получим выражение в 2П-форме для квадратора:

г - 1 с=а= X

i = о

а.\., \. = [2/ + l)

(4.38)

Выражения для компонент Cj произведения вектора а

иа константы b е GF(2)

Табли ца4.6

(«г-р . -. , tfj, flo)

Кон-

Компоненты

стан-

ноле

та b

GF(2)

flo +fli

flo +fli

flo +fl2

flo + fl2

ai + 02

fll +fl2

Oq +O1 +O2

flo +fl2

flo + fll + fl2

flo +fli

fll + fl2

flo +fli

tfO +fll +fl2

flo +fli

flo +fl3

flo +fl3

02 +03

flo +АЗ

fl2 +fl3

fll +fl2

fl2 +fl3

ai +02

ao +fli +fl3

flo +fl3

fll + fl2

fll +fl3

ao + fl2

02 + 03

ао +ai +a

fll +fl3

fll +fl2

GF(2*)

Oq +02

fll +fl3

flo *fl2 flj

tfO + fll + fl3

fll +fl3

tfo + fl2 + fla

Oi +02 +fl3

O0+O2

ao +fl2 +fl3

Oi +02 +O3

oq +ai +02 +03

Oi +03

fll +fl2 +fl3

Oo +01 +02 +O2

flo + fll + fl2

Oo + O2 + 03

flo +fll +fl2 +fl3

Oo + Oi +O2

flo +fli

fll +02 + fla

ao +fli +fl2

flo +fli

flo +fll *fl2 +fl3

flo +fli

flo + fll + fl2

fll +fl2

Oo +O1 +O3

Oq +O2

02 + 03



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.0124