Основы теории принятая статистических решений 1051 39 страница

8.1. Коды Рида-Соломона

Коды Рида-Соломона (Reed-Solomon code, R-S code) — это недвоичные циклические коды, символы которых представляют собой /n-битовые последовательности, где т — положительное целое число, большее 1. Коды Рида-Соломона (п, к) определены на /я-битовых символах при всех п и к, для которых

0<к<п< 2^т + 2, (8.1)

те к — число информационных битов, подлежащих кодированию, а п — число кодовых символов в кодируемом блоке. Для большинства сверточных кодов Рида-Соломона (п, к)

(п, к) = (2^т - 1, 2^m - 1 - 2t), (8.2)

где t — количество ошибочных битов в символе, которые может исправить код, а и - k = 2t — число контрольных символов. Расширенный код Рида-Соломона можно по­лучить при п = 2^т или п = 2^т+1, но не более того.

Код Рида-Соломона обладает наибольшим минимальным расстоянием, возмож­ным для линейного кода с одинаковой длиной входных и выходных блоков коде­ра. Для недвоичных кодов расстояние между двумя кодовыми словами определя­ется (по аналогии с расстоянием Хэмминга) как число символов, которыми отли­чаются последовательности. Для кодов Рида-Соломона минимальное расстояние определяется следующим образом [1]:

d_ma = n-k+l. (8.3)

Код, который исправляет все искаженные символы, содержащие ошибку в t или меньшем числе бит, где t приведено в уравнении (6.44), можно выразить следую­щим образом:

^min 1	н	п-к

Здесь Ы означает наибольшее целое, не превышающее х. Из уравнения (8.4) видно, что коды Рида-Соломона, исправляющие t символьных ошибок, требуют не более 21 контрольных символов. Из уравнения (8.4) следует, что декодер имеет п-к “используемых” избыточных символов, количество которых вдвое превышает количе­ство исправляемых ошибок. Для каждой ошибки один избыточный символ использу­ется для обнаружения ошибки и один — для определения правильного значения.

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

p = d_mm-l = n-k. (8.5)

Возможность одновременной коррекции ошибок и стираний можно выразить как требование

2а + у < dmn <п- к. (8.6)

Здесь а — число символьных моделей ошибки, которые можно исправить, а у — ко­личество комбинаций символьных стираний, которые могут быть исправлены. Пре­имущества недвоичных кодов, подобных кодам Рида-Соломона, можно увидеть в сле­дующем сравнении. Рассмотрим двоичный код (и, к) = (7, 3). Полное пространство
л-кортежей содержит 2" = 2⁷ = 128 и-кортежей, из которых 2* = 2³ = 8 (или 1/16 часть всех и-кортежей) являются кодовыми словами. Затем рассмотрим недвоичный код (и, к) - (7, 3), где каждый символ состоит из т = 3 бит. Пространство и-кортежей со­держит Т^т = 2²¹ = 2 097 152 и-кортежа, из которых 2^tm = 2⁹ = 512 (или 1/4096 часть всех и-кортежей) являются кодовыми словами. Если операции производятся над недвоич­ными символами, каждый из которых образован т битами, то только незначительная часть (т.е. 2^tm из большого числа 2"”) возможных и-кортежей является кодовыми сло­вами. Эта часть уменьшается с ростом т. Здесь важным является то, что если в каче­стве кодовых слов используется незначительная часть пространства и-кортежей, то можно достичь большего d_aш.

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

8.1.1. Вероятность появления ошибок для кодов Рида-Соломона

Коды Рида-Соломона чрезвычайно эффективны для исправления пакетов ошибок, т.е. они оказываются эффективными в каналах с памятью. Также они хорошо за­рекомендовали себя в каналах с большим набором входных символов. Особенно­стью кода Рида-Соломона является то, что к коду длины и можно добавить два информационных символа, не уменьшая при этом минимального расстояния. Та­кой расширенный код имеет длину и + 2 и то же количество символов контроля четности, что и исходный код. Из уравнения (6.46) вероятность появления ошиб­ки в декодированном символе, Р_Е, можно записать через вероятность появления ошибки в канальном символе, р [2].

Ре-

Здесь t — количество ошибочных битов в символе, которые может исправить код, а символы содержат т битов каждый.

Для некоторых типов модуляции вероятность битовой ошибки можно ограничить сверху вероятностью символьной ошибки. Для модуляции MFSK с М = 2^т связь Р_в и Р_Е выражается формулой (4.112)

р 'jm-1

Ls_ ₌ ±. ₍₈.₈₎

P_F 2^m -1

На рис. 8.1 показана зависимость Р_в от вероятности появления ошибки в каналь­ном символе р, полученная из уравнений (8.7) и (8.8) для различных ортогональ­ных 32-ричных кодов Рида-Соломона с возможностью коррекции t ошибочных бит в символе и и = 31 (тридцать один 5-битовый символ в кодовом блоке). На рис. 8.2 показана зависимость Р_в от E,JN₀ для таких систем кодирования при ис­
пользовании модуляции MFSK и некогерентной демодуляции в канале AWGN [2]. Для кодов Рида-Соломона вероятность появления ошибок является убываю­щей степенной функцией длины блока, п, а сложность декодирования пропор­циональна небольшой степени длины блока [I]. Иногда коды Рида-Соломона применяются в каскадных схемах. В таких системах внутренний сверточный де­кодер сначала осуществляет некоторую защиту от ошибок за счет мягкой схемы решений на выходе демодулятора; затем сверточный декодер передает данные, оформленные согласно жесткой схеме, на внешний декодер Рида-Соломона, что снижает вероятность появления ошибок. В разделах 8.2.3 и 8.3 мы рассмотрим каскадное декодирование и декодирование Рида-Соломона на примере системы цифровой записи данных на аудиокомпакт-дисках (compact disc — CD).

  Вероятность ошибочного приема канального символа, р Рис. 8.1. Зависимость Рв от р для различных ор­тогональных 32-ричных кодов Рида-Соломона с возможностью коррекции t бит в символе и п — 31. (Перепечатано с разрешения автора из Data Communications, Network, and Systems, ed. Thomas C. Bartee, Howard W. Sams Company, Indianapolis, Ind., 1985, p. 311. Ранее публиковалось в J. P. Odenwalder, Error Control Coding Handbook, M/A-COM LINKABIT, Inc., San Diego, Calif., July, 15, 1976, p. 91.)

3,5 4,0 4,5 5,0 5,5 6,0 6,5 7,0 Еь/Nо (ДБ)

Рис. 8.2. Зависимость Рв от Et/N₀ для различных ортого­нальных кодов Рида-Соломона с возможностью коррекции t бит в символе и п = 31, при 32-ричной модуляции MFSK в канале AWGN. (Перепечатано с разрешения автора из Data Communications, Network, and Systems, ed. Thomas C. Bartee, Howard W. Sams Company, Indianapolis, Ind.,

1985, p. 312. Ранее публиковалось в J. P. Odenwalder, Error Control Coding Handbook, M/A-COM LINKAB1T, Inc., San Diego, Calif., July, 15, 1976, p. 92.)

8.1.2. Почему коды Рида-Соломона эффективны при борьбе с импульсными помехами

Давайте рассмотрим код (п, к) = (255,247), в котором каждый символ состоит из т = 8 бит (такие символы принято называть байтами). Поскольку n-k-S, из уравнения (8.4) можно видеть, что этот код может исправлять любые 4-символьные ошибки в блоке длиной до 255. Пусть блок длительностью 25 бит в ходе передачи поражается помехами, как показано на рис. 8.3. В этом примере пакет шума, который попадает на 25 последовательных битов, исказит точно 4 символа. Декодер для кода (255, 247) исправит любые 4-символьные ошиб­ки без учета характера повреждений, причиненных символу. Другими словами, если деко­дер исправляет байт (заменяет неправильный правильным), то ошибка может быть вызва­на искажением одного или всех восьми битов. Поэтому, если символ неправильный, он может бьггь искажен на всех двоичных позициях. Это дает коду Рида-Соломона огромное преимущество при наличии импульсных помех по сравнению с двоичными кодами (даже при использовании в двоичном коде чередования). В этом примере, если наблюдается 25- битовая случайная помеха, ясно, что искаженными могут оказаться более чем 4 символа (искаженными могут оказаться до 25 символов). Конечно, исправление такого числа оши­бок окажется вне возможностей кода (255, 247).

8.1.3. Рабочие характеристики кода Рида-Соломона как функция размера, избыточности и степени кодирования

Для того чтобы код успешно противостоял шумовым эффектам, длительность помех должна составлять относительно небольшой процент от количества кодовых слов. Чтобы быть уверенным, что так будет большую часть времени, принятый шум необходимо усред­нить за большой промежуток времени, что снизит эффект от неожиданной или необычной полосы плохого приема. Следовательно, можно предвидеть, что код с коррекцией ошибок будет более эффективен (повысится надежность передачи) при увеличении размера пере­даваемого блока, что делает код Рида-Соломона более привлекательным, если желательна большая длина блока [3]. Это можно оценить по семейству кривых, показанному на рис. 8.4, где степень кодирования взята равной 7/8, при этом длина блока возрастает с п = 32 символов (при т = 5 бит на символ) до п = 256 символов (при т = 8 бит на символ). Таким образом, размер блока возрастает с 160 бит до 2048 бит.

25-битовый пакет шума

Символ 1

Символ 2

Символ 3

Символ 4

Символ 5

Символ 6

Норма Искажен Искажен Искажен Искажен Норма

Рис. 8.3. Блок данных, искаженный 25 -битовым пакетом ошибок

  Вероятность появления случайной ошибки в бите Рис. 8.4. Характеристики декодера Рида-Соломона как функция размера символов (степень кодирования = 7/8)

По мере увеличения избыточности кода (и снижения его степени кодирования), слож­ность реализации этого кода повышается (особенно для высокоскоростных устройств). При этом для систем связи реального времени должна увеличиться ширина полосы про­пускания. Увеличение избыточности, например увеличение размера символа, приводит к уменьшению вероятности появления битовых ошибок, как можно видеть на рис. 8.5, где кодовая длина п равна постоянному значению 64 при снижении числа символов данных с к = 60 до к = 4 (избыточность возрастает с 4 до 60 символов).

ю-°

0) н £

О 2 О §

§ ю-⁵

л m m s ы О

s

О 1Q-10 СЕ £

X ф m СЕ

о

| to-«

О X

На рис. 8.5 показана передаточная функция (выходная вероятность появления бито­вой ошибки, зависящая от входной вероятности появления символьной ошибки) гипо­тетических декодеров. Поскольку здесь не имеется в виду определенная система или ка­нал (лишь вход-выход декодера), можно заключить, что надежность передачи является монотонной функцией избыточности и будет неуклонно возрастать с приближением степени кодирования к нулю. Однако это не так, если отношение EJN_a фиксировано. По мере изменения степени кодирования кода от максимального значения до мини­мального (от 0 до 1), интересно было бы понаблюдать за эффектами, показанными на рис. 8.6. Здесь кривые рабочих характеристик показаны при модуляции BPSK и кодах (31, к) для разных типов каналов. На рис. 8.6 показаны системы связи реального време­ни, в которых за кодирование с коррекцией ошибок приходится платить расширением полосы пропускания, пропорциональным величине, равной обратной степени кодиро­вания. Приведенные кривые показывают четкий оптимум степени кодирования, мини­мизирующий требуемое значение £,//V₀ [4]. Для гауссова канала оптимальное значение степени кодирования находится где-то между 0,6 и 0,7, для канала с райсовским зами­ранием — около 0,5 (с отношением мощности прямого сигнала к мощности отражен­ного К = 7 дБ) и 0,3 — для канала с релеевским замиранием. (Каналы с замиранием бу­дут рассматриваться в главе 15.) Почему здесь как при очень высоких степенях кодиро­вания (малой избыточности), так и при очень низких (значительной избыточности)
наблюдается ухудшение вероятности ошибки? Для высоких степеней кодирования это легко объяснить, сравнивая высокие степени кодирования с оптимальной степенью ко­дирования. Любой код в целом обеспечивает все преимущества кодирования; следова­тельно, как только степень кодирования приближается к единице (нет кодирования), система проигрывает в надежности передачи. Ухудшение характеристик при низких сте­пенях кодирования является более тонким вопросом, поскольку когда E,JN_Q фиксирова­но работает два механизма. Один механизм направлен на снижение вероятности появ­ления ошибок, другой повышает ее. Механизм, снижающий вероятность появления ошибки, — это кодирование; чем больше избыточность, тем больше возможности кода в коррекции ошибок. Механизм, повышающий эту вероятность, — это снижение энергии, приходящейся на канальный символ (по сравнению с информационным символом), что следует из увеличения избыточности, вызывающей быструю передачу сигналов (в сис­темах связи реального времени). Уменьшенная энергия канального символа вынуждает демодулятор совершать больше ошибок. В конечном счете второй механизм подавляет первый, поэтому очень низкие степени кодирования вызывают ухудшение характери­стик кода.

---- Декодирование с исправлением ошибок ---- Декодирование с исправлением ошибок/стираний   О 0,2 0,4 0,6 0,8 1 Степень кодирования Рис. 8.6. Характеристики декодера Ри- да-Соломона (31, к) как функция степе­ни кодирования (модуляция BPSK)

Давайте попробуем подтвердить зависимость вероятности появления ошибок от степе­ни кодирования, показанную на рис. 8.6, с помощью кривых, изображенных на рис. 8.2. Непосредственно сравнить рисунки не удастся, поскольку на рис. 8.6 применяется моду­ляция BPSK, а на рис. 8.2 — 32-ричная модуляция MFSK. Однако, пожалуй, нам удастся показать, что зависимость характеристик кода Рида-Соломона от его степени кодирования

выглядит одинаково как при BPSK, так и при MFSK. На рис. 8.2 вероятность появления ошибки в канале AWGN снижается при увеличении способности кода t к коррекции сим­вольных ошибок с t = 1 до t = 4; случаи t = 1 и t = 4 относятся к кодам (31, 29) и (31, 23) со степенями кодирования 0,94 и 0,74. Хотя при f = 8, что отвечает коду (31,15) со степенью кодирования 0,48, достоверность передачи Р_в = 10~⁵ достигается при примерно на 0,5 дБ большем отношении E,JN₀, по сравнению со случаем г = 4. Из рис. 8.2 можно сделать вы­вод, что если нарисовать график зависимости достоверности передачи от степени кодиро­вания кода, то кривая будет иметь вид, подобный приведенному на рис. 8.6. Заметим, что это утверждение нельзя получить из рис. 8.1, поскольку там представлена передаточная функция декодера, которая несет в себе сведения о канале и демодуляции. Поэтому из двух механизмов, работающих в канале, передаточная функция (рис. 8.1) представляет только выгоды, которые проявляются на входе/выходе декодера, и ничего не говорит о по­терях энергии канального символа как функции низкой степени кодирования. В разде­ле 9.7.7 будет более подробно рассказано о выборе кода в соответствии с типом модуляции.

8.1.4. Конечные поля

Для понимания принципов кодирования и декодирования недвоичных кодов, таких как коды Рида-Соломона, нужно сделать экскурс в понятие конечных полей, извест­ных как поля Галуа (Galois fields — GF). Для любого простого числа р существует ко­нечное поле, которое обозначается GF(р) и содержит р элементов. Понятие GF(р) можно обобщить на поле из р^т элементов, именуемое полем расширения GF(р); это по­ле обозначается GF(p^m), где т — положительное целое число. Заметим, что GF(р^т) со­держит в качестве подмножества все элементы GF(p). Символы из поля расширения GF(2^m) используются при построении кодов Рида-Соломона.

Двоичное поле GF(2) является подполем поля расширения GF(2^m), точно так же как поле вещественных чисел является подполем поля комплексных чисел. Кроме чисел 0 и 1, в поле расширения существуют дополнительные однозначные элементы, которые будут представлены новым символом а. Каждый ненулевой элемент в GF(2^m) можно представить как степень а. Бесконечное множество элементов, F, образуется из стар­тового множества {0,1, а} и генерируется дополнительными элементами путем после­довательного умножения последней записи на а.

F={0, 1,а, сх².................... ос',...} = {0, а⁰, а¹, а²,..., ос',...}

Для вычисления из F конечного множества элементов GF(2^m) на F нужно наложить условия: оно может содержать только 2^т элемента и быть замкнутым относительно операции умножения. Условие замыкания множества элементов поля по отношению к операции умножения имеет вид нередуцируемого полинома

или, что то же самое,

(8.10)

С помощью полиномиального ограничения любой элемент со степенью, большей или равной 2^т~1, можно следующим образом понизить до элемента со степенью, меньшей 2^т -1:

Таким образом, как показано ниже, уравнение (8.10) можно использовать для форми­рования конечной последовательности F* из бесконечной последовательности F.

F* = {0,1,а,а²,...,a²"^-2,a^2,"^-1,a²”,...} = _(g ^

= {0,а⁰,а¹,а²,...,а^{2 -2},а°,а¹,а²,...}

Следовательно, из уравнения (8.12) можно видеть, что элементы конечного поля GF(2^m) даются следующим выражением:

GF(2^m) = {0, а⁰,а¹,<х²,...,а²'"^-2}. (8.13)

8.1.4.1. Операция сложения в поле расширения GF(2^m)

Каждый из 2^т элементов конечного поля GF(2^m) можно представить как отдельный полином степени т - 1 или меньше. Степенью полинома называется степень члена максимального порядка. Обозначим каждый ненулевой элемент GF(2^m) полиномом а,(X), в котором по крайней мере т коэффициентов а,(Х) ненулевые. Для i — 0, 1, 2,..., 2^т -2,

<х, = а,(Х) = а,о +a, iX + а,2^ + •■■ + *. (8.14)

Рассмотрим случай т-3, в котором конечное поле обозначается GF(2³). На рис. 8.7 показано отображение семи элементов {а,} и нулевого элемента в слагаемые базисных элементов {Х°, X¹, X²}, описываемых уравнением (8.14). Поскольку из урав­нения (8.10) а° = а⁷, в этом поле имеется семь ненулевых элементов или всего восемь элементов. Каждая строка на рис. 8.7 содержит последовательность двоичных вели­чин, представляющих коэффициенты а, ₀, а,, и а, ₂ из уравнения (8.14). Одним из преимуществ использования элементов {ос*} поля расширения, вместо двоичных эле­ментов, является компактность записи, что оказывается удобным при математическом описании процессов недвоичного кодирования и декодирования. Сложение двух эле­ментов конечного поля, следовательно, определяется как суммирование по модулю 2 всех коэффициентов при элементах одинаковых степеней.

а, + а_; = (а, ₀ +а_; о) + (а,_л + а_;,)Х +... + (а, + а_{; т}_i)X^{m 1} (8.15)

8.1.4.2. Описание конечного поля с помощью примитивного полинома

Класс полиномов, называемых примитивными полиномами, интересует нас, по­скольку такие объекты определяют конечные поля GF(2^m), которые, в свою очередь, нужны для описания кодов Рида-Соломона. Следующее утверждение является необ­ходимым и достаточным условием примитивности полинома. Нередуцируемый поли­ном f(X) порядка т будет примитивным, если наименьшим положительным целым числом п, для которого X" + 1 делится наДХ), будет п = 2^т - 1. Заметим, что нередуци­руемый полином — это такой полином, который нельзя представить в виде произве­дения полиномов меньшего порядка; делимость А на В означает, что А делится на В с

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

Образующие

элементы

Х° X¹ X²

0 0 0 0

э

л а⁰ 1 0 0

^е 1

м ^а

е _а2 н

Т а³ 1 1 0

Ы

⁴ 0 1 1 1 1 1

Л а⁶ 1 0 1 Я

1 О о

Рис. 8.7. Отображение элементов поля в базисные элементы GF(8) с помощью f(X) = 1 + Х + X³

Пример 8.1. Проверка полинома на примитивность

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

а) 1+Х + Х⁴

б) l+X + X^X' + X⁴

Решение

а) Мы можем проверить этот полином порядка т = 4, определив, будет ли он делителем

X" + 1 = Х^{(2 _l)} +1 = X¹⁵ +1 для значений п из диапазона 1 < п < 15. Нетрудно убедиться, что X¹⁵ + 1 делится на 1 +Х + Х⁴ (см. раздел 6.8.1), и после повторения вычислений можно проверить, что при любых значениях п из диапазона 1 < п < 15 полином X" + 1 не делится на 1 + X + X⁴. Следовательно, 1+Х + Х⁴ является примитивным полиномом.

б) Легко проверить, что полином является делителем Xⁿ + 1. Проверив, делится ли X” + 1 на 1 + X + X² + X³ + X⁴, для значений п, меньших 15, можно также видеть, что указан­ный полином является делителем X⁵ + 1. Следовательно, несмотря на то что полином 1+Х + Х² + Х³ + Х⁴ является неприводимым, он не будет примитивным.

8.1.4.3. Поле расширения GF(2³)

Рассмотрим пример, в котором будут задействованы примитивный полином и ко­нечное поле, которое он определяет. В табл. 8.1 содержатся примеры некоторых прими­тивных полиномов. Мы выберем первый из указанных там полиномов, ДХ) = 1 + X + X³, который определяет конечное поле GF(2^m), где степень полинома т = 3. Таким образом, в поле, определяемом полиномом ДХ), имеется 2^т - 2³ = 8 элементов. Поиск корней по­линома ДХ) — это поиск таких значений X, при которых ДХ) = 0. Привычные нам дво­ичные элементы 0 и 1 не подходят полиномуДХ) = 1 + Х + Х³ (они не являются корнями),

поскольку Д1) = 1 и ДО) = 1 (в рамках операций по модулю 2). Кроме того, основная тео­рема алгебры утверждает, что полином порядка т должен иметь в точности т корней. Следовательно, в этом примере выражение ДХ) = 0 должно иметь 3 корня. Возникает оп­ределенная проблема, поскольку 3 корня не лежат в том же конечном поле, что и коэф­фициенты ДХ). А если они находятся где-то еще, то, наверняка, в поле расширения GF(2³). Пусть а, элемент поля расширения, определяется как корень полинома ДХ). Сле­довательно, можно записать следующее:

Дос) = 0 1 + а + а³ = О а³ = -1 - а

Поскольку при операциях над двоичным полем +1 следующим образом:

а³ = 1 + а.

Таблица 8.1. Некоторые примитивные полиномы

т		т
	1+Х + Х^3		1+Х + Х^6 + Х^|0 + Х^14
	1+Х + Х^4		1+Х + Х^15
	1 +X^2 + X^i		1+Х + Х^3 + Х^12 + Х^16
	1+Х + Х^6		1 + X^3 + X^17
	1+Х^3 + Х^7		1 +Х^7+Х^18
	1+Х^2 + Х^3+Х^4 + Х^8		1 + X + X^2 + X^i + X^19
	1+Х^4 + Х*		1+Х^3+Х^20
	1 + X^3 + X^10		1 + X^2 + X^21
И	1+Х^2 + Х"		1+Х + Х^22
	1+Х + Х^4 + Х^6 + Х^12		1 +x^i + x^23
	1 +х + х^3 + х^4 + х^13		1 +х + х^2 + х^7 + х^24

Таким образом, а³ представляется в виде взвешенной суммы всех a-членов более низ­кого порядка. Фактически так можно представить все степени а. Например, рассмот­рим следующее:

а⁴ = а- а³ = а- (1 + а) = а + а². (8.18,а)

А теперь взглянем на следующий случай:

а⁵ = а- а⁴ = а- (а + а²) = а² + а³. (8.18,6)

Из уравнений (8.17) и (8.18) получаем следующее:

а⁵=1+а + а². (8.18,в)

Используя уравнение (8.18,в), получаем следующее:

а⁶ = а ■ а⁵ = а • (1 + а + а²) = а + а² + а³ = 1 + а². (8.18,г)

А теперь из уравнения (8.18,г) вычисляем

Заметьте, что а⁷ = а⁰ и, следовательно, восемью элементами конечного поля GF(2³) будут

{О, а⁰, а¹, а², а³, а⁴, а⁵, а⁶}. (8.19)

Отображение элементов поля в базисные элементы, которое описывается уравнени­ем (8.14), можно проиллюстрировать с помощью схемы линейного регистра сдвига с об­ратной связью (linear feedback shift register — LFSR) (рис. 8.8). Схема генерирует (при т = 3) 2^т-1 ненулевых элементов поля и, таким образом, обобщает процедуры, описанные в уравнениях (8.17)—(8.19). Следует отметить, что показанная на рис. 8.8 обратная связь со­ответствует коэффициентам полинома ДХ) = 1 + X + X³, как и в случае двоичных цикличе­ских кодов (см. раздел 6.7.5). Пусть вначале схема находится в некотором состоянии, на­пример 100; при выполнении правого сдвига на один такт можно убедиться, что каждый из элементов поля (за исключением нулевого), показанных на рис. 8.7, циклически будет появляться в разрядах регистра сдвига. На данном конечном поле GF(2³) можно определить две арифметические операции — сложение и умножение. В табл. 8.2 показана операция сложения, а в табл. 8.3 — операция умножения, но только для ненулевых элементов. Пра­вила суммирования следуют из уравнений (8.17) и (8.18,д); и их можно доказать, обратив­шись к рис. 8.7, поскольку сумму двух элементов поля можно рассчитать путем сложения (по модулю 2) соответствующих коэффициентов их базисных элементов. Правила умно­жения, указанные в табл. 8.3, следуют из обычной процедуры, в которой произведение элементов поля вычисляется путем сложения по модулю (2^т -1) их показателей степеней или, для данного случая, по модулю 7.

х° х¹ х² х³   Рис. 8.8. Отображение элементов поля в базис­ные элементы можно представить с помощью схемы линейного регистра сдвига с обратной связью (linear feedback shift register — LFSR), по­строенного на примитивном полиноме

Таблица 8.2. Таблица сложения для GF(8) при/(Х) = 1 +Х + Х¹

	а^0	а^1	а^2	а^3	а^4	а^5	а^6
а^0		а^3	а^6	а'	а^5	а^4	а^2
а^1	а^3		а^4	а^0	а^2	а^6	а^5
а^2	а^6	а^4		а^5	а'	а^3	а^0
а^3	а^1	а^0	а’		а^6	а^2	а^4
а^4	а^5	а^2	а^1	а^6		а^0	а^3
а^5	а^4	а^6	а^3	а^2	а^0		а^1
а^6	а^2	а^5	а^0	а^4	а^3	а^1

Дата добавления: 2015-10-28