Материал: Статистическая теория систем. практикум. Володько А.В., Останков А.В
(x) (x )(x 8 )(x 64 )
x3 x2 |
( 64 8 ) x( 19 72 9 ) 72 |
(33) |
||
|
||||
Среди элементов поля GF(29 ) выберем элемент, |
который имеет период, |
|||
равный 7- периоду |
примитивного |
элемента |
поля |
GF(29 ) , для |
рассматриваемой длины 7=511/73. Следовательно, элемент 73 |
имеет период, |
|||
равный 7. Полагаем 73 . |
|
|
|
|
Для примитивного полинома, выбранного в поле GF(29 ) , необходимо |
||||
выразить через степени элемента 73 |
следующие суммы: |
|
||
64 8 ; |
72 63 9. |
|
|
|
Это очень трудоемкая и длительная процедура, но ее можно облегчить с помощью специальной программы на ЭВМ. Последовательные степени
элемента |
в поле GF(23 ) уже |
вычислялись при рассмотрении М- |
последовательностей длины. Здесь следует иметь в виду, что 73 . |
||
Характеристические полиномы |
для q ичных М-последовательностей |
|
длины qk |
1 вычислены для длин 63,255,511,1023 и сведены в таблицы [22] . |
|
3.1.5. Генератор M-последовательности над полем GF(2m1)
Генератор М- последовательности над полем GF(2m1) строится в соответствии с характеристическим полиномом. Степень характеристического
полинома определяет число ячеек регистра, |
каждая из которых является m1 - |
|||
разрядной. |
|
|
|
|
Рассмотрим схему |
генератора, формирующего М-последовательность |
|||
длины N 15 |
над полем GF(22 ) в соответствии с |
характеристическим |
||
полиномом |
x2 x 5 . |
Схема 2m1 -ичного |
генератора |
со встроенными |
сумматорами по модулю 2 (рис. 3.4) строится так же, как и схема двоичного, но в отличии от него наличие ненулевого коэффициента при соответствующей степени x означает не только наличие сумматора по модулю два после соответствующей ячейки регистра и связи этого сумматора с последним разрядом регистра, но и умножение в этой связи на какую-то степень примитивного элемента .
x0 |
1 |
x |
2 |
|
x1 |
|
|
|
|
|
|
5 |
|
|
|
Рис. 3.4. Структурная схема генератора со встроенными сумматорами по модулю два для характеристического полинома x2 x 5
70
На входе первой ячейки регистра коэффициент умножения равен коэффициенту при x0 в характеристическом полиноме. Выход второй ячейки подается на сумматор, стоящий после первой ячейки, с предварительным умножением на коэффициент при x1 в характеристическом полиноме. Здесь следует заметить, что ячейки регистра являются двухразрядными. Запись элементов в них осуществляется с использованием степенного базиса 1, 5 .
Рассмотрим построение функциональной схемы с учетом выбранного базиса. Выход последней ячейки регистра обозначим
0 1 5 . |
|
|
(34) |
||
Значение 0 записывается |
в первом |
разряде, а значение 1 |
во втором |
||
разряде. |
|
|
|
|
|
Умножение на 5 , которое производится перед подачей сигнала на вход |
|||||
первой ячейки регистра, можно представить следующим образом: |
|
||||
5 ( |
0 |
5 ) 5 5 |
10 . |
(35) |
|
|
1 |
0 |
1 |
|
|
Это выражение также нужно представить в степенном базисе. Для этого обратимся к схеме рис. 3.2, который дает 10 1 5 .
Тогда
5 |
5 |
|
1 |
(1 5 ) |
1 |
5 |
( |
0 |
|
1 |
). |
(36) |
|
0 |
|
|
|
|
|
|
|
Выражение (36) означает, что умножение на 5 эквивалентно подаче на вход первого разряда первой ячейки регистра выхода 1 второго разряда второй ячейки, а на вход второго разряда-суммы выходов 0 1 первого и второго разрядов второй ячейки. В соответствии с этим структурная схема генератора М- последовательности длины 15 над полем GF(22 ) может иметь вид, представленный на рис. 3.5.
|
|
|
|
|
' |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1' |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 3.5. Структурная схема генератора М-последовательности длины 15 над полем GF(22 )
71
В табл. 3.1 представлены состояния ячеек регистров этой схемы. Двухразрядным выходом генератора может быть 1-й или 2-й разряды регистра 7. Получили последовательность длины 15, состоящую из двухразрядных элементов.
Теперь рассмотрим методику построения генератора М- последовательности длины 511 над полем GF(23 ). Например из таблицы полиномов [22] выбираем последовательность с номером 239, которая имеет характеристический полином x3 38x2 73.
Таблица 3.1
Состояние ячеек регистров в схеме рис. 3.6
|
|
|
|
|
|
|
|
|
|
|
Такты |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
14 |
16 |
… |
|
' |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
… |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
… |
|
' |
|||||||||||||||||
|
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
… |
0 |
||||||||||||||||||
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
… |
|
Генератор содержит три ячейки трехразрядных регистров. Структурная схема генератора представлена на рис. 3.6.
x0 |
|
x1 |
|
x2 |
|
x3 |
|
|
|
73 |
438 |
Рис. 3.6. Структурная схема генератора М-последовательности длины 511
над полем GF(23) |
|
|
В характеристическом полиноме коэффициент при x1 |
равен 0, |
поэтому |
сумматор по модулю два после первой ячейки регистра отсутствует. |
|
|
Для построения функциональной схемы генератора надо определить два |
||
произведения: 438 и 73 . |
|
|
Здесь надо воспользоваться представлением степеней элемента |
поля |
|
GF(23) через степенной базис при примитивном полиноме |
x3 x 1 (двоичное |
|
представление (1011)), учитывая, что 73 : |
|
|
72
73 ( |
0 |
73 |
146 ) 73 |
|
|
1 |
2 |
(37) |
|
|
|
|
|
0 73 1 146 2 219.
Всоответствии с таблицей полиномов [22] для М-последовательности с
номером 239
219 |
1 146. |
|
|
|
|
|
|
|
||
Тогда |
|
|
|
|
|
|
|
|
|
|
73 |
73 |
146 |
|
2 |
(1 146 ) |
(38) |
||||
|
|
0 |
1 |
|
|
|
|
|||
|
|
73 |
( |
|
|
|
) 146. |
|||
2 |
1 |
2 |
|
|||||||
|
0 |
|
|
|
|
|
|
|||
Следовательно, умножение на 73 эквивалентно подаче на вход первого разряда 2 , второго разряда 0 , третьего разряда ( 1 2).
Теперь определим 438 :
|
438 |
( |
0 |
73 148) 438 |
438 |
314 |
73 |
(39) |
|||||||||||||||
|
|
|
|
|
|
1 |
|
|
2 |
|
|
0 |
|
|
|
1 |
|
1 |
|
||||
|
|
|
73 |
|
( 73 |
145 ) |
|
( |
|
|
|
) 73 145. |
|||||||||||
|
1 |
0 |
1 |
0 |
2 |
|
|||||||||||||||||
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|||||
Умножение на 438 |
можно заменить подачей на вход первого разряда 1, |
||||||||||||||||||||||
второго разряда ( 0 |
2 ), третьего - 0 . |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
В соответствии с полученными выражениями (38), (39) структурная |
|||||||||||||||||||||||
схема будет иметь вид, представленный на рис. 3.4. |
|
|
|
||||||||||||||||||||
В табл. 3.2 приведены состояния разрядов регистров в течение первых |
|||||||||||||||||||||||
нескольких тактов. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
Состояние ячеек регистров в схеме рис. 3.1.7 |
Таблица 3.2 |
|||||||||||||||||
|
|
|
|
|
|
||||||||||||||||||
|
Разря- |
|
|
|
|
|
|
|
|
Такты |
|
|
|
|
|
|
|||||||
|
ды |
|
|
|
|
1 |
|
|
2 |
|
3 |
|
|
|
4 |
|
|
5 |
|
… |
|
||
|
реги- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
стра |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
'' |
|
|
|
|
0 |
|
|
1 |
|
1 |
|
|
|
1 |
|
|
0 |
|
… |
|
|
|
|
0 |
|
|
|
|
0 |
|
|
0 |
|
0 |
|
|
|
1 |
|
|
0 |
|
… |
|
|
|
|
'' |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
1 |
|
|
|
|
1 |
|
|
1 |
|
0 |
|
|
|
0 |
|
|
0 |
|
… |
|
|
|
|
'' |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
' |
|
|
|
|
0 |
|
|
0 |
|
1 |
|
|
|
1 |
|
|
1 |
|
… |
|
|
|
|
0 |
|
|
|
|
0 |
|
|
0 |
|
0 |
|
|
|
0 |
|
|
1 |
|
… |
|
|
|
|
' |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
1 |
|
|
|
|
1 |
|
|
1 |
|
1 |
|
|
|
0 |
|
|
0 |
|
… |
|
|
|
|
' |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
0 |
|
|
0 |
|
1 |
|
|
|
0 |
|
|
1 |
|
… |
|
||
|
1 |
|
|
|
|
0 |
|
|
1 |
|
1 |
|
|
|
0 |
|
|
0 |
|
… |
|
||
|
2 |
|
|
|
|
1 |
|
|
1 |
|
1 |
|
|
|
0 |
|
|
0 |
|
… |
|
||
73
Генератор формирует М-последовательность длины 511, символами которой являются трехразрядные элементы
'' |
0' |
0 |
|
0 |
|
|
|
'' |
' |
|
1 |
1 |
1 |
|
|
2'' |
2' |
2 |
|
|
|
|
|
0 2 |
1 2 |
|
|
||
|
||||
Рис. 3.7. Функциональная схема генератора М-последовательности длины 511 над полем GF(23)
3.1.6. Коды Рида-Соломона
Коды Рида-Соломона (РС-коды) - это q-ичные коды (кодовые символы принимают q различных значений), причем длина n кода жестко связана с q: n q 1. Например, РС код (63,55) использует 26 -ичные символы, длина кода 63, информационных символов 55. Число разрешенных кодовых комбинаций огромно (26 )55 2310 . Каждый информационный символ несет log2 q 6 бит информации, следовательно, каждая кодовая комбинация несет 55 6 330 бит информации.
Порождающий полином РС кода определяется при заданных q и и - числе исправляемых ошибок или кодовом расстоянии 2 и 1:
|
g(x) (x m0 )(x m0 1)...(x m0 2 и 1). |
|
|
То есть |
корнями порождающего полинома |
являются |
элементы |
m0 , m0 1 , m0 2 и 1 |
поля GF(q). Степень порождающего |
полинома |
равна 2 и , |
такое же число проверочных символов в кодовой комбинации. Если известно обозначение кода (n,k ), то сразу можно оценить корректирующие способности кода. Например, код (63,55) имеет 63-55=8 проверочных символов, следовательно, этот код исправляет все ошибки кратности, не превышающей 4. Кодовое расстояние на единицу больше числа проверочных символов и для кода (63,55) равно 9.
По методике определения порождающего полинома коды РС очень похожи на коды БЧХ. Отличие от них состоит в том, что для кодов БЧХ порождающий полином определяется как наименьшее общее кратное произведения полиномов, корнями которых являются элементыm0 , m0 1 , m0 2 и 1, а для кодов РС - само произведение. Кроме того, коды БЧХ
74