Главная Помехоустойчивое кодирование продолжение табл. 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.0161 |