3.4. ВЫЧИСЛЕНИЯ В КОНЕЧНОМ ПОЛЕ
Так как элементы GF(24) представляются в виде 
-векторов из нулей и единиц, то с ними легко оперировать, используя цифровые схемы или двоичные ЭВМ.
В этом параграфе будет дано краткое описание некоторых логических схем для выполнения операций в поле GF(24). (Подобное же описание может быть дано для любого поля 
Подробную информацию по этому вопросу см. в работах Барти и Шнейдера [72], Питерсона и Уэлдона [1040, гл. 7] и Берлекэмпа [113, гл. 1—5]. Подробные сведения по регистрам сдвига см. в работах Гилла [485], Голомба [523] и Каутца [750].
Основными элементами при составлении схем являются следующие:
Таким образом, любой элемент поля GF(24), порожденного корнем уравнения 
(см. рис. 3.1), представляется четырьмя нулями и единицами, которые могут храниться в строке из четырех ячеек памяти (называемой регистром):
Умножение на а. Устройство, показанное на рис. 3.2 и называемое регистром сдвига с линейной обратной связью, умножает содержимое регистра на элемент а в поле GF(24).
Ибо если в начальный момент времени регистр содержит элемент поля
то в следующий момент времени он будет содержать элемент поля
Если же в начальный момент времени этот регистр содержит 
то в последующие моменты времени он будет содержать 
так как а — примитивный элемент.
Рис. 3.2. Линейный регистр с обратной связью, выполняющий умножение на элемент а в поле 
Рис. 3.3. Линейный регистр, на выходе которого образуются кодовые слова длины 15
Поэтому последовательность символов на выходе устройства, изображенного на рис. 3.3, является периодической с периодом 15. Это — максимально возможный период для четырех ячеек памяти (так как имеется как раз 
ненулевых состояний). Отрезки выходной последовательности длины 15 представляют собой кодовые слова кода максимальной длины, порожденного регистром сдвига с обратной связью. Этот код является также симплексным кодом (см. § 1.9 и гл. 14).
Умножение на фиксированный элемент поля. Рассмотрим, например, умножение произвольного элемента поля 
на элемент 
которое выполняется с помощью устройства, показанного на рис. 3.4:
Рис. 3.4. Схема умножения произвольного элемента поля 
на 
Аналогично для деления на фиксированный элемент поля надо умножить на элемент, обратный ему.
Умножение двух произвольных элементов поля. К сожалению (ибо умножение элементов поля существенно, например, при декодировании кодов БЧХ и кодов Гоппы; см. гл. 9 и 12), эта операция значительно сложнее.
Предположим, что необходимо найти произведение заданных элементов поля 
Способы умножения. (1). Непосредственное вычисление.
Если 
в этом случае требуется большая и сложная схема для вычисления всех элементов 
по заданным 
(2). Модель медленного умножения вручную. В этом случае мы записываем произведение в следующем виде:
и используем схему, изображенную на рис. 3.5. На каждом шаге мы прибавляем к с элемент ага, если и только если 
и затем умножаем ага на а.
Рис. 3 5. Схема умножения двух произвольных элементов поля
Лос и Рашфорс [796] описали недавно сотообразную схему, которая также умножает этим способом, но их схема представляет скорее итерацию в пространстве, чем во времени, и поэтому умножает существенно быстрее, чем вышеописанная схема.
(3). Использование таблиц логарифмов и антилогарифмов. Для умножения двух элементов поля 
возьмем их логарифмы по основанию а (см. § 3.2), где 
примитивный элемент поля, и сложим их, как целые числа по модулю 15, а затем возьмем антилогарифм ответа. Схематически это показано на рис. 3.6.
В отличие от логарифма действительного числа логарифм в конечном поле является чрезвычайно нерегулярной функцией. Неизвестно никакого быстрого способа нахождения 
: либо его находят непосредственно, вычисляя подряд все последовательные степени элемента а до тех пор, пока не встретится элемент а (что очень медленно), либо (что несколько лучше) используется таблица логарифмов, как, например, на рис. 3.1 или 4.1, 4.2.
Рис. 3.6. Схема умножения с использованием таблиц логарифмов и антилогарифмов по основанию примитивного элемента поля
Этот метод прекрасен для поля GF(24), но он практически неприемлем для полей 
при больших значениях 
особенно потому, что необходима также таблица антилогарифмов того же объема.
(4). Логарифмы Зеча (Конвей [301]). В этой схеме умножения используется только полярное представление элементов поля (т. е. в виде степеней примитивного элемента а). Умножать теперь легко, но что можно сказать о сложении? Оно выполняется с помощью так называемых логарифмов Зеча. Логарифм Зеча от целого числа 
определяется уравнением 
(рис. 3.7). В таком случае сумма элементов 
равна
и потребность в таблице антилогарифмов отпадает, например
Рис. 3.7. Логарифм Зеча в поле 
