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



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


132 133 134 135 136

137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153-154 155 156 157 158 159 160 161 162 163 164 165 166 167

168 169 170 171 172 173

10000100

10000101

10000110

10000111

10001000

10001001

10001010

10001011

10001100

10001101

10001110

10001111

10010000

10010001

10010010

10010011

10010100

10010101

10010110

looioni

10011000 10011001 10011010

lopuoii looiuoc

10011101 10011110

looinii

10100000 10100001 lOlOOOlO 10100011 10100100 10100101 10100110 10100111

10101000 10101001 10101010 10101011 10101100 10101101

01011100 10111000 01101101 11011010 10101001

01001111 lOOllllO 00100001 01000010 10000100 00010101 00101010

01010100

10101000 01001101 10011010 00101001 01010010 10100100 01010101 10101010 01001001 10010010 00111001 01110010 11100100 11010101

lonom

01110011 11100110 11010001 10111111 01100011 11000110 10010001 00111111

01111110 11111100

mooioi

11010111 10110011 01111011

198 199

200 201 202 203 204

205 206 207 208 209 210 211 212 213 214 215

10101110 10101111 10110000 10110001 10110010 10110011 10110100 10110101 10110110 10110111 10111000 10111001 10111010 10111011 10111100 10111101

loiimo

10111111 11000000 11000001 11000010 UOOOOll 11000100 11000101

11000110 11000111 11001000 11001001 11001010 11001011 11001100 11001101 11001110 11001111 11010000 11010001 11010010 11010011 11010100 11010101 11010110 11010111

11110110 11110001

11111111

11100011 11011011 10101011 01001011 10010110 00110001 01100010 11000100 10010101 00110111

01101110 11011100 10100101 01010111 10101110 01000001 10000010 00011001 00110010 01100100 11001000

10001101 00000111 00001110 00011100 00111000 01110000 11100000 11011101 10100111 01010011 10100110 01010001 10100010 01011001 10110010 01111001 11110010 11111001

216 11011000

217 11011001

218 11011010

219 llQllOll

220 11011100

221 11011101

222 11011110

223 11011111

224 iiiooooa

225 11100001

226 11100010

227 11100011

228 11100100

229 11100101

230 11100110

231 11100111

232 11101000

233 11101001

234 11101010

235 UIOIOU

236 lUOilOO

237 11101101

238 11101110

239 11101111

240 11110000

241 ,11110001

242 11110010

243 111100И

244 11110100

245 11110101

246 11110110

247 11110111

248 lllllOOO

249 11111001

250 11111010

251 11111011

252 11111100

253 11111101

254 11111110

255 11111111

lUOllU

UOOOOll

10011011

00101011

01010110

10101100

01000101

10001010

00001001

00010010

00100100

01001000

10010000 00111101 OUUOIO 11110100 11110101 11110111 11110011 11111011 11101011 11001011 10001011 00001011 00010110 00101100 01011000 10110000 01111101 11111010 11101001 11001111 10000011 00011011 00110110 01101100 11011000 10101101 01000111 10001110

Сложение элементов поля GF(2). Сложение двух элементов поля 2) особенно просто осуществляется пои их полиномиальном или



векторном представлениях. В этом случае сложение выполняется покомпонентно (поразрядно) на основе операции поля GF(2) "сумма по модулю 2", удовлетворяющей тождествам:

0 + 0=1 + 1=а+а=0, 0+1 = 1+0=1, ае{0, l).

Например, (ОНО) + (1010) = [(О + 1) (1 + 0) (1 + 1) (О + 0] = = (1100) или (х +х) + (л: +jc) =х +jc

Для упрощения здесь и далее будем обозначать одним и тем же символом " + " разные операции: поразрядное сложение по модулю 2 и сумму элементов поля; такой подход широко применяется в современной алгебре. Надеемся, что это не вызовет затруднений у читателя. Не следует забывать, что сумма по модулю 2 сама является операцией сложения над полем, а именно над полем GF(2). Более того, для каждого поля GF (2) используется, по-существу, своя операция сложения (и умножения) со свойствами, зависящими от порядка этого поля и от используемого полинома 7г(д:). Поэтому, если смысл операций ясен из контекста или непосредственно из формулы (как в данном случае), их значение дополнительно не будет расшифровываться.

Умножение элемштов поля GF(2), Определенные трудности возникают яри умножении и делении элементов поля, представленных в виде вектора или полинома.

Конечно, умножение двух элементов поля, заданных в прямоугольной системе координат, может производиться по обычному правилу умножения двух многочленов, но, естественно, с последующим приведением полученного произведения по модулю соответствующего примитивного неприводимого полинома 7i(x), Например, надполем GF(2*), порожденным полиномом 7т(х) =х +Х + 1, имеем

(х +х) (х +jc) =х +jc +х +jc2 =(х +х) + (jc + 1) +jc +х =х + 1,

где учтено, что х = д: + 1 при 7т(х) = О, а следовательно, д: = + х.

Переходя от полиномов к соответствующим двоичным векторам и умножая "школьным" столбиком векторы как многоразрядные числа, получим:

х +х 0 110 х+х 10 10

О 1 1 О 1 1

11 110 0 I- 1 1

1 1

10 1 О-** х +х, х х x*



где комбинации складываются поразрядно по модулю два и учтены корректирующие тождества "обратной связи" для разрядов переполнения

д: ( 1 00 0 0) = (00 1 1);

(10 0 00 0) = (О 1 1 0)- {х +jc).

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

Пусть задана пара элементов а ч b поля GF(2®), выбранная из

табл. 3.7:

а = (10110111)-«- Na = 159, (11001001)7V =24.

Умножение этих элементов дает на первом этапе комбинацию (1110011 01001111), в которой правые разряды являются основными, а левые - переполнениями у. По табл. 3.9 (Л = 115) находим поправку Z = (01111110), поразрядно добавляя которую к основной части окончательно получим с ~ аЪ ~ (01001111) + (01111110) = = (00110001) Nc = 182 (см. табл. 3.7, переход 182 GF).

Умножение столбиком реализуется с помощью сдвигающих регистров, но учет поправок требует специальной схемы коррекции; в частности, можно записать таблицу поправок в запоминающем устройстве.

Однако в ряде случаев целесообразнее синтезировать такую схему по логическим выражениям. Покажем, как они составляются.

Задаваясь двоичными комбинациями для элементов поля с номерами от Л = г + 1 до Л= 2г ~ 1, построим матрицу М поправок так, как это сделано в табл. 3.10 для полей ряда размерностей г. Строки и столбцы матрицы М обозначим компонентами соответственно вектора переполнения = {уоУх ... Уг вектора поправки z = (z j - г • • * z, Zo). Тогда поправка найдется как скалярное произведение z = уМ, естественно, со сложением частных произведений по модулю 2. Другими словами, компонента будет равна сумме по модулю 2 тех значений yj , которым соответствуют единицы в столбце z.

Таким образом, поправка z представляется системой линейных сумм, составленных из разрядов у , сигнала переполнения у - см. табл. 3.11 для ряда полей.

Если полином имеет вид 7i(x) = х + д: + 1, например, для поля GF(2), то в матрицей все единицы сконцентрированы строго на двул диагоналях. Поэтому можно составить следующее выражение для компонент поправок:



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