Файл: прикладная теория информации.pdf

185
( )
( ) ( ),
с x
f x g x

где
1 1
1 0
1 1
0
( )
(
),
,
n
i
n
i
n
i
i
с x
c x
c
c x
c x
c
F







 


1 0
1 0
( )
(
),
0,
r
i
r
i
r
r
i
g x
g x
g
g x
g x
g




 


1 1
1 0
1 1
0
( )
(
)
k
i
k
i
k
i
f x
f x
f
f x
f
x







 

( )
с x
G

в кольце
{ ( )}
F x
,
( )
n
f x
R

,
Если размерность ЦК равна, степень информационного многочлена
( )
f x
равна deg
( )
1,
f x
k
 
то степень порождающего многочлена
( )
g x
равна deg
( )
g x
r

Циклический код
G
как подпространство в кольце
n
R n
-мерного пространства над полем
( )
GF p
порождается строками матрицы
G
размером
k
n

. Строки матрицы удовлетворяют свойству линейной независимости.
0 0
0 0
0
)
(
)
(
)
(
1 0
1 0
1 0
1


































r
r
r
k
g
g
g
g
g
g
g
g
g
x
g
x
x
xg
x
g
G








Пример 11.3 . Построить порождающую матрицу [7, 4, 3]- кода Хэм- минга, если
3 1
)
(
x
x
x
g



Решение. Первая строка матрицы есть векторное представление
( )
g x
Остальные строки – циклические сдвиги вправо первой строки.
1 0
1 1
0 0
0 0
1 0
1 1
0 0
0 0
1 0
1 1
0 0
0 0
1 0
1 1













G
Пример 11 .4 . Пусть
3 1
)
(
x
x
x
g



. Произвести кодирование информа- ционного многочлена
2 3
( ) 1
f x
x
x
x
  

Решение
2 3
3 3
2 4
2 3
5 3
4 6
3 5
6
( )
(1
)(1
)
(1
)
(1
).
с x
x x
x
x x
x x
x x
x
x
x
x
x
x
x
x
x
x
  

 
  
 




  


 


Кодовому слову
( )
с x
соответствует вектор
(1001011).

с
Это же значение

186 кодового вектора получается вычислении произведения информационного век- тора
(1 1 1 1)
f =
и матрицы
G
(1001011)

с
fG =
11.3. Проверочный многочлен циклического кода
Пусть
G
– циклический код над полем
(2)
GF
есть идеал кольца многочле- нов
{ ( )}
R
F x

по модулю многочлена
( )
(
1)
n
z x
x


. На основании основного уравнения кодирования должно выполняться равенство
( ) ( )
0mod(
1),
n
g x h x
x


(11.5) где
( )
h x
– проверочный многочлен.
Правую часть выражения (11.5) можно записать как
0
(
1) mod(
1)
n
n
x
x



Тогда равенству (11.5) соответствует формула
( ) ( )
(
1).
n
g x h x
x


Из последнего выражения получаем
(
1)
( )
( )
n
x
h x
g x


Степень проверочного многочлена ЦК deg ( )
deg ( )
h x
n
g x
n
r
k
 
  
Пример 11 .5 . Порождающий многочлен ЦК длиной
15
n

имеет вид
11 8
7 5
3 2
( )
(
1).
g x
x
x
x
x
x
x
x






 
Найти проверочный многочлен.
Решение.
15 4
11 8
7 5
3 2
(
1)
( )
1
(
1)
x
h x
x
x
x
x
x
x
x
x
x


  





 

11.4. Минимальные многочлены
Пусть
(
)
m
F
GF p

– конечное расширенное поле Галуа порядка
m
p
,

187
p
– простое число. Любое конечное поле содержит
m
p
элементов для некоторого простого
p
и некоторого целого
1
m

. Существует только одно такое поле
(
)
m
F
GF p

для каждого
p
и
m
. Конечное поле содержит по крайней мере один примитивный элемент

, такой, что все нулевые элементы поля

  

могут быть представлены в виде разных степеней


. Элементы поля могут быть вы- ражены и через отрицательные степени

, так как поле содержит мультиплика- тивный обратный элемент каждого ненулевого элемента.
Теорема Ферма. Каждый элемент

поля
(
)
m
GF p
является корнем много- члена
0
m
p
x
x
 
,
(11.6)
1
(
1)
0
m
p
x x

 
.
или, эквивалентно удовлетворяет выражению
m
p
  
Запишем уравнение (11.6) в другом виде
(
(
)
m
p
m
F
x
x
x
F
GF p

 
 

. (11.7)
Для
0
x

, уравнение (11.6) представляется в виде
1
(
1)
0
m
p
x

 
,
1 1.
m
p
x


Так как
1
m
p
n
 
,то получаем двучлен вида
1 0.
n
x
 
(11.8)
Если

  
корень уравнения (11.8), то
1 1 0,
n
n
x

    
1,0 1
n
n

 
   
Известно, что любой двучлен типа (11.8) может быть представлен произ- ведением всех неприводимых многочленов, степени которых являются делителями числа
m
от 1 до
m
включительно. Согласно теореме Ферма корни

188 уравнений (11.6), (11.7) принадлежат различным неприводимым в поле
( )
GF p
многочленам на которые разлагается двучлен.
Пример 11.6. Пусть
2,
3.
p
m


По таблице неприводимых многочле- нов находим
7 3
3 2
1 (
1)(
1)(
1) 1.
x
x
x
x
x
x
 

 

 
Заметим, что степени непри- водимых многочленов – числа 1, 3 являются делителями числа
3.
m

С каждым элементом поля
(
)
m
F
GF p

связан неприводимый многочлен, называемый минимальным многочленом. Многие циклические коды в своей ос- нове имеют минимальные многочлены.
Определение 11.3. Минимальным многочленом элемента

над полем
( )
GF p
называется нормированный многочлен
( )
M
x

с коэффициентами из
( )
GF p
наименьшей степени такой, что
( )
0
M
x


( )
0
M

 
.
Корнями минимального многочлена
( )
0
M
x


являются следующие раз- личныеэлементы

поля:
1 1
2
,...,
m
p
p
m

    
  
Пример 11.7. Найти минимальный многочлен
( )
M
x

элемента
3 1
,
    
если
3,
m

а корень

есть элемент поля, построенного с использованием при- митивного многочлена
3
( ) 1
h x
x
x
  
Решение. Согласно (11.7) Многочлен
( )
M
x

может быть представлен в виде произведения двучленов
1 2
3
( )
(
)(
)(
)
M
x
x
x
x


 
 
 
, где
1 2
2 4
3 2
3 6
3 3
12 5
1 2
3
,
,
((
)).
m

              
     
3 3
6 5
3 2
( )
(
)(
)(
)
1.
M
x
x
x
x
x
x

 
 
  


11.5. Низкоскоростные циклические коды
Низкоскоростными являются коды, у которых ???? ≪ ???? и скорость передачи кода R = k /n ≪ 1. Как правило, кодовое расстояние низкоскоростных кодов при- ближается к значению ???? =
????
2
. Следовательно, такие коды могут корректировать
???? = ⌈
????−1 2
⌉ = ⌈
????
2
−1 2
⌉ ≅
????
4
ошибок. Свойства низкоскоростных кодов позволяют ис- пользовать их в качестве основы для формирования так называемых сложных сигналов для систем связи, радиолокации, радиолокации, для обеспечения син- хронизации и структурной и криптографической защиты информации. Практи- ческий интерес представляют различные семейства низкоскоростных кодов (ко- довых последовательностей), их корреляционные свойства, мощность кодов,

189 сложность кодовой структуры и вычислительная сложность обработки.
Свойства кодовых последовательностей. Наиболее важными для низко- скоростных кодов являются их периодические и апериодические корреляцион- ные свойства. Корреляционная функция ‒ это показатель сходства или общих свойств двух последовательностей. Функция корреляции описывает последова- тельное изменение отклика линейной системы на входное воздействие в виде ко- дового слова. Отклик формируется при изменении временного положения после- довательности.
Нормированная периодическая взаимная корреляционная функция ????( ????) последовательностей ???? = (????
0
????
1
… ????
????−1
) и ℎ = (ℎ
0
ℎ
1
… ℎ
????−1
) записывается как
????
????
=
1
????
∑
????
????
ℎ
????+????
????−1
????=0
,
???? = 0, 1, … , ???? − 1. (11.9) где ((???? + ????)) = (???? + ????)mod ????.
Эта функция периодична, т. е. ????
????
= ????
((????+????))
. Если временного рассогласо- вания нет, ???? = 0. Значение ????
????
= 0 указывает на нулевую корреляцию. Это озна- чает, что последовательности независимы. Если корреляция последовательно- стей в выражено слабо, то
|????
????ℎ
(????)| ≪ 1, при любых ????.
11.5.1. Матричное представление корреляции
Пусть длина последовательности ???? = 3. По формуле (11.9) получаем сле- дующие значения коэффициентов корреляции:
????(0) =
1 3
(????(0)ℎ(0) + ????(1)ℎ(1) + ????(2)ℎ(2));
????(1) =
1 3
(????(0)ℎ(1) + ????(1)ℎ(2) + ????(2)ℎ(0));
????(2) =
1 3
(????(0)ℎ(2) + ????(1)ℎ(0) + ????(2)ℎ(1)).
Полученные выражения могут быть представлены в матричной форме
???? =
1
????
????????
????
,
[
????(0)
????(1)
????(2)
] =
1 3
[
ℎ(0) ℎ(1) ℎ(2)
ℎ(1) ℎ(2) ℎ(0)
ℎ(2) ℎ(0) ℎ(1)
] [
????(0)
????(1)
????(2)
]. (11.10)

190
Из приведенного примера следует, что вычисление взаимной корреляции двух ????-периодических последовательностей сводится к циклическому сдвигу од- ной последовательности относительно другой и усреднения их произведения за период ????. Если последовательности ???? и ℎ идентичны, то выражение (11.9) будет определять автокорреляционную функцию
Пример 11.8 . Вычислить автокорреляционную функцию псевдошумо- вой последовательности ???? = (0 0 1 0 111).
Решение
При переходе к бинарной записи последовательности ????, которая получа- ется путем замены 0 на 1 и 1 на –1, автокорреляционная функция равна
[
????(0)
????(1)
????(2)
????(3)
????(4)
????(5)
????(6)]
=
1 7
[
1 1
−1 1
−1 −1 −1 1
−1 1
−1 −1 −1 1
−1 1
−1 −1 −1 1
1 1
−1
−1 −1 1
1
−1
−1 −1
−1 1
1
−1 1
−1 −1 1
1
−1 −1 −1
−1 1
1
−1 −1 −1 −1]
[
1 1
−1 1
−1
−1
−1]
=
[
1
−1 7
⁄
−1 7
⁄
−1 7
⁄
−1 7
⁄
−1 7
⁄
−1 7
⁄ ]
На рис. 11.1 показан график автокорреляционной функции псевдошумо- вой последовательности.
Рис.11.1. Автокорреляционная функция последовательности ???? = (1 1 − 1 − 1 − 1 − 1).
Автокорреляционную функцию можно вычислять по другим формулам.
Обозначим ???? число совпадений символов последовательности ???? = (????
0
????
1
… ????
????−1
)
-1
-0,8
-0,6
-0,4
-0,2 0
0,2 0,4 0,6 0,8 1
0 1
2 3
4 5
6 7
r(
τ)
τ

191 и ее циклического сдвига ????
????
= (????
????
????
????+1
… ????
????+????−1
), а ???? – число несовпадений. То- гда
????(????) =
???? − ????
????
,
где ???? + ???? = ????.
Для всех ненулевых сдвигов последовательности ???? = (11 − 1 − 1 − 1 −
1) число ???? = 3, ???? = 4 получаем значения корреляции
????(????) =
3 − 4 7
= −
1 7
Учитывая, что псевдошумовые последовательности (????- последовательно- сти) образуют симплексный код, в котором каждая пара кодовых слов находится на одинаковом расстоянии Хэмминга
????
????
= ???? = ???? =
????+1 2
, для автокорреляционной функции справедливо выражение
????(????) =
(???? − ????) − ????
????
=
???? − 2????
????
=
???? − 2????
????
Таким образом,
????(0) = 1, ????(????) =
1
????
для
1 ≤ ???? ≤ 2
????
− 2. (11.11)
Замечание. Функция (11.11) является наилучшей среди автокорреляцион- ных функций двоичных последовательностей длиной ???? = 2
????
− 1, если в каче- стве критерия выбрать min функции max ????(????) , 1 ≤ ???? ≤ ???? − 1.
11.6. Корреляционный метод декодирования низкоскоростных кодов
Низкоскоростные коды в основном используются при низком отношении сигнал/шум на входе декодера системы. Декодирование таких кодов целесооб- разно реализовывать на основе принципа максимального правдоподобия (мини- мума расстояния Хэмминга). В этом случае достигается минимальная ошибка декодирования, повышается достоверность передачи-приема (обработки) ин- формации. Декодирование на основе принципа максимального правдоподобия эквивалентно корреляционному методу. Тогда декодирование сводится к вычис- лению корреляции принимаемой последовательности со всеми кодовыми сло- вами кода.

192
Пусть имеется псевдослучайная последовательность ???? = (????
0
????
1
… ????
????−1
), задающая помехоустойчивый [????, ????, ????]-код. Циклические сдвиги последователь- ности ???? определяют разрешенное пространство кодовых слов кода, записанное в виде матрицы ???? размером (2
????
− 1) × ????, где ???? = (2
????
− 1) – мощность кода,
???? ≥ 3. Строки матрицы ???? образуют множество {????} = (????
1
, … , ????
????
) слов кода.
В канале без шумов, декодирование заключается в вычислении вектора
???? =
1
????
???????? = (????
0
????
1
… ????
????−1
)
????
, ???? ∈ ???? (11.12) и определении номера ???? координаты ????
????
, для которой выполняется условие
????
????
= max
????
????
????
Пример 11 .9 . Пусть имеется источник на множестве символов алфавита
{????, ????, ????, ????, ????, ????, ????}. Этому множеству ставится в соответствие ансамбль {????} =
= (????
1
… , ????
????
) кодовых слов, заданных матрицей ????. В качестве задающего код выбрана псевдослучайная последовательность ???? = (????
0
????
1
… ????
6
) ????-кода
???? = (1 1 − 1 1 − 1 − 1 − 1).
???? =
[
1 1
−1 1
−1 −1 −1 1
−1 1
−1 −1 −1 1
−1 1
−1
−1 −1 1
1 1
−1 −1
−1 1
1
−1
−1
−1 −1 1
1
−1 1
−1
−1 1
1
−1 1
−1
−1 1
1
−1 1
−1 −1]
. (11.13)
Матрица ????определяет помехоустойчивый код с параметрами: ???? = 7, ???? =
3, ???? = 4. Символ ???? кодируется словом ????
1
= (1 1 − 1 1 − 1 − 1 − 1), символ ???? – соответственно словом ????
2
= (1 − 1 1 − 1 − 1 − 1 1) и т. д. Предположим, на вход декодера поступила последовательность
???? = (−1 − 1 1 1 − 11 − 1).
Вычисляя по формуле (11.12), получим вектор
???? = (−1 7
⁄ , −1 7
⁄ , −1 7
⁄ , −1 7
⁄ , −1 7
⁄ , 1, −1 7
⁄ )
????
Максимальное значение имеет компонента ????
5
= 1, поэтому по каналу пе- редавался символ ????. На рис. 11.2. показан график функции ????(????) = ????(????), ???? =
0, 1, … ???? − 1.

193
Рис.11.2. Корреляционная функция последовательности ???? = (−1 − 1 11 − 1 1 − 1).
Предположим, что подлежит передаче по каналу с шумами некоторый век- тор ???? ∈ ????.Из-за возможного воздействия шумов, на выходе канала наблюдается
(принимается) вектор вида
???? = (???? + ????)mod2 = (????
0
???? … ????
????−1
), где ????= (????
0
????
1
… ????
????−1
), ????
????
∈ {1, − 1} – вектор ошибок, определяемый как
???? = (???? − ????)mod2.
Если ошибок не произошло, то все ????
????
= 1. Вектор ошибок указывает место ошибки на длине вектора ????. Количество единиц на длине вектора ошибок ???? определяет число ошибок ????. Декодер, анализируя вектор ???? = ???? + ????, должен ре- шить, какой вектор ???? из множества {????} передавался. Вектор ????декодируется в ближайший вектор ???? на множестве {????} в смысле расстояния Хэмминга. Практи- ческая реализация этого алгоритма декодирования выполняется путем сравнения входа ???? со всеми словами множества {????} и принятия решения о ближайшем слове.
Пример 11.10 . Пусть имеется источник и код, задаваемый матрицей ????
(см. пример 11.9). На вход декодера поступил вектор ???? = (1 1 1 − 1 1 − 1 − 1).
Определить принимаемый символ источника.
Решение. Выполняя корреляционное декодирование по формуле
???? = ????????
????
= (????
0
????
1
… ????
????−1
)
????
,
получим вектор
???? = (1, 1, −3, 1, −3, −3, 5)
????
-1
-0,8
-0,6
-0,4
-0,2 0
0,2 0,4 0,6 0,8 1
0 1
2 3
4 5
6 7
r(
τ)
τ

194
Максимальное значение имеет координата ????
6
= 5, рис. 11.3. По каналу пе- редавалось кодовое слово ????
6
= (−1 1 1 − 1 1 − 1 − 1). Этому слову соответ- ствует символ ????.
Вектор ошибки ????соответствует следующей последовательности с наименьшим весом (единичным) весом:
???? = (???? − ????)mod2 = (1 1 1 − 1 1 − 1 − 1) − (−1 1 1 − 1 1 − 1 − 1) =
= (−1 1 1 1 1 1 1) → (1 0 0 0 0 0 0).
Как видно, ошибка произошла в первом чипе слова ????
6
. Найденный вектор ????является наиболее вероятным для принятого вектора ????. Расстояние
Хэмминга между векторами ???? и ????
????
равно
????
????
= 1. Это расстояние является ми- нимальным на пространстве кодовых векторов кода (матрицы ????).
Рис. 11.3. Корреляционная функция последовательности ???? = (1 1 1 − 1 1 − 1 − 1)
11.7. Коды максимальной длины
Последовательности, пораждаемые кодом максимальной длины, являются важным классом периодических последовательностей, из которых могут быть образованы множества с хорошими периодическими взаимно-корреляционными свойствами. По другому эти коды называют m-кодами. Коды максимальной длины широко применяются на практике. Например, решение задачи надежного разделения сигналов (доступности) различных базовых станций в приемнике мобильной сети или пользователя сети 2G – 4Gосновывается на применении мо- дификации m-кода над расширенным полем Галуа ????????(2
????
). Модификации отно- сят к кодам Голда.
Элементы поля ????????(2
????
), задаются неприводимым над простым полем
????????(2) проверочным полиномом ℎ(????) степени ????. Закон следования элементов поля определяет псевдослучайные структурные свойства m-кода. Комбинирова-