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



продолжение табл. 3.10

Поле GF (2 )

И 12 13 14

15 16 17 18 19

Уо У1

У4 У5

Уб Уп У%

Матрица поправок М

О О О О О О 1 О О

О О О О О 1 О О 1

О О О О 1 О О 1 О

о о о о

о о о

о о о 1 о

о о о о о о

о о о о о о о о о о

Логические выражения для поправок

Таблица 311

Поле GF(2)


Поправки

20~У0, 21->о+>1, 22-ух+У2, 2з~У2

20~ Уо+Уз* 1-У1у 22-уо+У2+Уз ЗУ1 +УЗу 24У2

х" + х +х + 1

o = >o + ;4+>s+;6.

22 =У0+У2 +У4+У5, 2а=У0+У1 +У2 +Уб» 6=У2 +У3 У4. 7

1 Д-! Уъ Уь зУо-Ух Уз-Уа

2$ +У2 +УЗ

Уз+Уа+У5

Z . I

У- У- ,

о, Ь 1; У-у =Уг-,

(3.22)

Выражение (3.22) применимо также для полей GF (2) размерности г, равной 2, 3, 4, 6 и др., с полиномами вида 7г(х) = х+х + 1. Представим полином п (х) в следующей форме

7Г(Х)

I = г

/ = о

. + JUi х+ 1,

где учтено, что всегда ju = jUo = 1.

Так, для поля GF(2) полином 7г(х) =х + 1,т. е. jU2 =

" ~ = 0. В матрице М поля GF (2) единицы сосредоточены не только в двух диагоналях, но в последней строке содержатся также в разрядах Zq и Следовательно, компоненты поправки определяются выражением



где jy =Опри /<0и />г-1.

В общем случае справедлива формула

/ = / / к = г - 1


1-0 \ к = 2- } - I

где /= О, 1 - 1.

Поясним ее примером расчета компоненты для поля GF(2®),

7г(х) =x® + 1, т. е. Д1 = /is = /i6 = /7 = 0; Mo = Дг = Мз =

= /i4 = 1; /= 5, / = О, 1,. . . , 5:

+ М2 (:>3 + Ms 36 + Мб 35 +M7J4) +

+ Мз (J2 +M4J6 MsJs +M6J4 +М7 3з) +

+ JU4(jl РзУь +iU4j5 + Ms 34 +Мб7з +M7J2) +

+ М5 (Зо +М2 36 + МзЗз +M4J4 +М5 7з + Мб32 УпУх) =

= + 33 + 32 + 36 + + 7б + 35 =31 + 72 + Уъ-

Подытожим рассмотрение "столбиковых" методов умножения. Ясно, что для технической реализапяи таких методов нужны много-

тактные устройства; но их быстродействие даже с учетом быстрых (и сложных) схем поправок принципиально ниже малотактных устройств. К тому же непосредственное деление "столбиком" трудно осуществимо - оно заменяется умножением на мультипликативно-обратный к делителю элемент. Поэтому на практике обычно йрименяются устройства, основанные на иных методах умножения; к рассмотрению основных из них мы и переходим.

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

При степенном представлении каждого элемента в виде а умножение и деление проводятся по следующим очевидным правилам

аа = а, k=i + / (mod«. =2 - 1); а: J = k=i - j (mod x = 2* - 1),

где a, a, a] G GF(2), a операции сложения и вычитания показателей - модульные. Аналогичные модульные операции применяются и при использовании обычных логарифмов: 112



log (аЬ) - log a + log b - сложение no модулю ж.; log (a : b) = log a - log b - вычитание no модулю».

Умножение и деление десятичных номеров (модифицированных логарифмов) элементов поля GF(2) осуществляется по формулам, вытекающим из соотношений (3.8) и (3.9):

О, если д = О или Ь = 0; д+Ь - 1,еслид 0, ЬФОиа b<q; (3.23)

а + b - q, если а ФО, ЪФО и а b>q;

а : Ъ

О, если а - О, ЪФО\ д - Ь + 1, если ЬФО и а>Ь\ (3-24)

+ а - Ь, если ЬФО и д < Ь,

где q - 2 - порядок поля.

Если в процессе вычислений требуется производить чередующиеся адщ1тивные и мультипликативные операции, то целесообразно осуществлять переходы от векторов (полиномов) к степеням и обратно с помощью логарифмирования и антилогарифмирования.

Логарифмы в третьих колонках табл. 3.4... 3.6 упорядочены по нарастанию их величин (имеется в виду десятичная система счисления). Поэтому подобные таблицы позволяют проводить антилогарифмирование - переход от логарифмов к векторам или полиномам. Однако "вход" в таблицы по заданному вектору затруднен, потому что векторы упорядочены как элементы поля, а не расположены в естественном двоичном порядке. Облегчение процесса логарифмирования - обратного перехода от векторов к логарцфмам - достигается за счет упорядочения векторов по комбинациям обычного двоичного кода так, как это получилось для поля GF(2) с полиномом 7г(х) = + X + 1 (см. табл. 3.4). Подобное упорядочение произведено в табл. 3.12 для полей GF(2), GF(2), GF(2), а для поля GF(2«) с полиномом 7г(х) =х + + х*+х+х + 1- в табл. 3.13.

Проиллюстрируем методику вычислений на следующем примере (он будет использован в § 5.1 при проверке правильности решения квадратного уравнения). Пусть над полем GF(2®) с полиномом 7г(х) = = х® + х* + х + х + 1 требуется вычислитьприх= 30, Sq= 113,5*1 = = llbySi = 163, 5з = 203 значение функции F(x) -Агх" +>liX + o> гдеЛз = 525о +5?; >li = SS +521; = SS,

В данном примере элема1ты. поля-заданы своими десятичными номерами Л (модифицированными логарифмами). Поэтому по формуле (3.23) находим: SSq = 163,- 113 = 20,5? -226 = 196, так как 113 + + 163 = 276 > 256 и 226+ 226 = 452 > 256.



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