Материал: Статистическая теория систем. практикум. Володько А.В., Останков А.В
обычно двоичные (могут быть и q-ичными), а коды РС - обычно q-ичные. Однако коды РС можно перевести в двоичные, при этом кодовое расстояние не уменьшается, но не обязательно получается циклические коды.
Если q 2m , то говорят о коде РС над полем GF(2m ), то есть его кодовыми символами являются элементы этого поля. В этом случае в выражении (40) используется операция сложения по модулю два. Коэффициенты порождающего полинома также будут элементами поля GF(2m ).
Рассмотрим код РС (7,3). Символами этого кода являются элементы поля
GF(8) GF(23). |
Число |
проверочных |
символов |
r 7 3 4 . |
Следовательно, |
|||||||
кратность исправляемой ошибки и |
2, |
кодовое расстояние равно 5. |
Число |
|||||||||
разрешенных |
кодовых |
комбинаций |
равно |
29 512. |
Порождающий полином |
|||||||
имеет степень r 4. Определим порождающий полином при m0 1: |
|
|||||||||||
|
g(x) (x )(x 2 )(x 3 )(x 4 ). |
|
|
|
(40) |
|||||||
После проведения умножения в (40) получим: |
|
|
|
|
|
|||||||
g(x) (x2 |
x( 2 ) 3 )(x2 |
x( 3 4 ) 7 ). |
|
|
(41) |
|||||||
При проведении операции умножения и сложения с элементами поля |
||||||||||||
GF(2m ) следует выбрать примитивный полином степени |
m. Для поля GF(23) |
|||||||||||
выберем полином |
x3 x 1- |
это примитивный |
полином |
над |
полем |
GF(2). |
||||||
Корнем этого полинома является элемент , следовательно, 3 |
1 0 |
и для |
||||||||||
последовательных |
степеней |
элемента |
|
можно |
записать выражения, |
|||||||
приведенные в табл. 3.3. Тогда |
|
|
|
|
|
|
|
|
||||
|
2 4 , |
3 1, |
|
|
|
|
|
|
|
|||
|
3 4 3(1 ) 6. |
|
|
|
|
|
(42) |
|||||
Продолжаем преобразования порождающего полинома
g(x) (x2 4 x 3)(x2 6x 1)
x4 x3( 6 4 ) x2 x( 4 2 ) 3
(43)
x4 ( 1)x3 x2 x ( 1)
x4 3x3 x2 x 3.
Кодирующее устройство содержит четыре трехразрядных ячейки регистра сдвига. На схеме не показаны ключи, которые необходимо использовать для получения систематического кода, обращается внимание только на связи регистра с сумматором по модулю два. На вход сумматора подаются 23 -ичные символы информации. Элемент , записанный в какую-то
75
ячейку регистра, можно с помощью степенного базиса 1, , 2 записать в виде
0 1 2 2.
Таблица 3.3 Полиномиальное и двоичное представления степеней элемента - корня
примитивного полинома x3 x 1 в поле GF(23)
i |
Полиномиальное |
Двоичное |
|
|
представление |
представление |
|
0 |
1 |
001 |
|
1 |
|
010 |
|
2 |
2 |
100 |
|
3 |
1 |
011 |
|
4 |
2 |
110 |
|
2 1 |
|||
5 |
111 |
||
6 |
2 1 |
101 |
В соответствии с полученным полиномом можно построить кодирующее устройство, структурная схема которого представлена на рис. 3.8.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
3 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 3.8. Кодирующий регистр РС кода
Коэффициенты |
0, 1, 2 |
|
являются элементами поля GF(2) и принимают |
|||||||||
значения 0 или 1. В первом разряде |
регистра содержится значение 0 , во |
|||||||||||
втором разряде - значение |
|
1, в третьем |
- 2 . |
Рассмотрим, что означает |
||||||||
умножение элемента |
|
на 3 |
и . |
|
|
|
|
|
|
|
||
( |
0 |
|
2) 2 3 |
|
||||||||
|
1 |
|
2 |
|
0 |
1 |
|
|
|
2 |
(44) |
|
2 |
|
(1 ) |
|
( |
|
|
|
|
||||
2 |
2 |
0 |
2 |
) 2. |
||||||||
0 |
|
1 |
|
|
|
|
|
1 |
||||
76
Это выражение определяет связи третьей ячейки регистра сдвига с сумматором по модулю два. На первый разряд сумматора подается выход 2 третьего разряда третьей ячейки, на вход второго разряда сумматора - сумма выходов первого и третьего разрядов, а на третий разряд сумматора
подается выход 1 второго разряда третьей ячейки регистра.
3 ( |
0 |
2) 3 3 4 |
5 |
|
|
||||
|
|
1 |
2 |
0 |
1 |
2 |
|
|
|
0(1 ) 1( 2 ) 2(1 2) |
|
(45) |
|||||||
( 0 2) ( 0 1 2) 2 ( 1 2). |
|
|
|||||||
Это выражение определяет связи первой и четвертой ячеек регистра |
|||||||||
сдвига с сумматором: |
на |
вход |
первого |
разряда сумматора |
подается сумма |
||||
( 0 2 ) выходов первого и третьего разрядов ячейки регистра, на вход второго разряда сумматора подается сумма ( 0 1 2 ) выходов всех трех разрядов, а на вход третьего разряда сумматора - сумма ( 1 2 ) выходов второго и третьего разрядов ячейки регистра.
С учетом выражений (44) и (45) схему кодирующего устройства РС кода (7.3) можно представить в виде, приведенном на рис. 3.9.
Комму- |
М2-1 |
М2-2 |
|
М2-3 |
|
татор |
|
|
|
|
Вход |
|
|
|
|
|
Ключи |
' |
|
2 |
3 |
|
4 |
0 |
|
0 |
0 |
|
0 |
' |
|
2 |
13 |
14 |
|
1 |
|
1 |
|
|
|
2' |
22 |
23 |
24 |
||
|
|
|
|
|
Выход |
Рис. 3.9. Кодирующее устройство РС кода |
|||||
Порождающий полином запишем в виде q-ичного представления:
g(x) x4 3x3 x2 x 3 |
1 31 3 . |
(46) |
Двоичное представление получим, если элементы q -ичного представления заменить их двоичным представлением в соответствии с табл. 3.3:
g(x) 1 31 3 1011001010011. |
(47) |
77
Двоичное представление запишем в виде полинома. Получим порождающий полином кода РС над полем GF(2)
g(x) x12 x10 x8 x6 x4 x 1. (48)
В соответствии с этим полиномом кодирующее устройство строится на 12разрядном регистре сдвига так же, как и для любого двоичного циклического кода. Длина n2 двоичного РС кода и число k2 информационных символов определяются по формулам:
n2 nlogq, k2 klogq.
В рассматриваемом примере q-ичный РС код преобразуется в двоичный код (21,9), кодовое расстояние двоичного кода больше или равно пяти.
3.1.7. Порядок определения порождающего полинома РС-кода и составления структурной схемы кодирующего устройства
1. Для заданного кода (n,k,d ) определить поле GF(q), q n 1, элементы
которого являются кодовыми символами. |
|
2. Определить число проверочных символов |
|
r n k , |
(49) |
то есть степень порождающего полинома, число его корней.
3. Записать порождающий полином в виде произведения двучленов в соответствии с формулой (30), положив m0 0 или 1. В формуле (30) в двучленах используется операция суммирования по модулю два, если выбранное поле имеет характеристику 2, то есть q 2k , k - целое, положительное число.
4. Выбрать примитивный полином поля GF(q), обратившись к приложению учебного пособия [22]. Записать степенное, полиномиальное и двоичное представления примитивного элемента аналогично тому, как это сделано в табл. 3.3.
5. Преобразовать выражение для порождающего полинома, чтобы его коэффициенты были степенями примитивного полинома GF(q). Сначала надо перемножить двучлены, затем преобразовать коэффициенты с использованием матрицы, полученной в предыдущем пункте.
6.Начертить структурную схему связей регистра с сумматором аналогично тому, как это сделано на рис. 3.8 для кода (7,3).
7.Выбрать базис, с его помощью записать элемент поля GF(q).
8.Провести умножение элемента на коэффициенты порождающего полинома, отличные от 0 или 1. Результат перемножения представить в выбранном базисе.
78
9.Нарисовать структурную схему кодирующего устройства с учетом результатов, полученных в предыдущем пункте. Схема должна иметь вид, аналогичный представленному на рис. 3.9.
10.Указать информационные характеристики кода и его корректирующие способности.
3.2. Элементы теорий конечных полей
Вструктуре псевдослучайных последовательностей существуют особые закономерности, которые вытекают из их построения на основе конечных полей или их групп. Конечными полями являются множества номеров элементов псевдослучайной последовательности, а саму двоичную псевдослучайную последовательность можно рассматривать как полученную в результате сопоставления 0 или 1 элементам с определенными номерами.
Вэтой главе дается краткое математическое введение в теорию конечных полей и групп. Изложение ведется описательно, со множеством примеров, доказательства основных положений опущены. Автор пытается изложить материал так, чтобы он был понятен для инженеров-радистов, не знакомых с теорией конечных полей. В главе вводятся понятия конечных полей - расширенных и простых, мультипликативных и аддитивных групп, первообразного и примитивного элементов, а также смежных и сопряженных классов.
3.2.1.Конечные поля
Классическое определение поля [13]:
Поле - это множество элементов, на которых заданы операции умножения и сложения, удовлетворяющие законам замкнутости, ассоциативности, коммутативности и дистрибутивности.
Поясним эти законы, обозначив элементы поля через а, b и c, знаки умножения и сложения - общим знаком композиции *.
Замкнутость: если a M и b M, то существует единственный элемент c M: c=a*b. Из этого следует, что среди элементов поля должен быть единичный элемент e, такой, что a*e=a, а также наличие обратного элемента a M такого, что a*ā=e.
Ассоциативность: (а*b)*c = a*(b*c). Коммутативность: a*b=b*a. Дистрибутивность: a·(b+c)=a·b+a·c.
При рассмотрении полей применительно к псевдослучайным последовательностям будем иметь дело со множествами чисел, для которых безусловно выполняются законы ассоциативности, коммутативности и дистрибутивности. В этом случае остается проверять только закон замкнутости, выполнение которого сводится к наличию единичного е и обратных элементов (по умножению ā=-a-1, по сложению ā=-a). Поэтому в нашем случае определение поля упрощается.
79