Алгоритм Берлекэмпа - Месси
Дипломная работа, 14 Мая 2013, автор: пользователь скрыл имя
Описание работы
Первоначальная версия алгоритма Берлекэмпа–Месси была изложе-
на Берлекэмпом в 1968 году [1] в качестве элемента конструкции декодера
кодов Боуза–Чоудхудри–Хоквингема над конечным полем. Хотя в этой ра-
боте была указана возможность формулировки решаемой задачи с исполь-
зованием понятия линейного регистра сдвига с обратной связью, алгоритм
описывался исключительно в терминах полиномов и был весьма сложен
для понимания. Спустя год Месси [2] предложил свою интерпретацию ал-
горитма, как позволяющего строить линейный регистр сдвига минималь-
ной длины, генерирующий заданную последовательность. Эта интерпрета-
ция оказалась полезной для более широкого распространения алгоритма,
получившего название по имени этих двух ученых. В некоторых работах
алгоритм излагается также с помощью непрерывных дробей и рациональ-
ной аппроксимации.
Содержание работы
1. Введение и постановка задачи.......................................................................3
2. Алгоритм Берлекэмпа–Месси........................................................................5
3. Реализация алгоритма Берлекэмпа–Месси.................................................14
3.1. Архитектура реализации .......................................................................15
3.2. Класс линейного регистра сдвига.........................................................16
3.3. Класс алгоритма .....................................................................................17
3.4. Тестирование ..........................................................................................18
4. Декодер для кодов Рида–Соломона ............................................................21
5. Литература ......................
Файлы: 1 файл
fullText.pdf
— 519.41 Кб (Скачать файл)| Page 1 |
Федеральное государственное образовательное
учреждение высшего профессионального образования
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Факультет математики, механики и компьютерных наук
Кафедра алгебры и дискретной математики
АЛГОРИТМ БЕРЛЕКЭМПА—МЕССИ
ДЛЯ ПОЛЕЙ ГАЛУА И ЕГО ПРИМЕНЕНИЕ
Выпускная квалификационная работа
студента 4 курса очной формы обучения
А. М. Пеленицына
Научный руководитель:
доцент, к.ф.-м.н.
В. М. Деундяк
Ростов-на-Дону
2007
| Page 2 |
Содержание
1. Введение и постановка задачи........................
2. Алгоритм Берлекэмпа–Месси..............
3. Реализация алгоритма Берлекэмпа–Месси..............
3.1. Архитектура реализации ..............................
3.2. Класс линейного регистра сдвига........................
3.3. Класс алгоритма ..............................
3.4. Тестирование ..............................
4. Декодер для кодов Рида–Соломона ..............................
5. Литература ..............................
Приложение ..............................
2
| Page 3 |
1. Введение и постановка задачи
Первоначальная версия алгоритма Берлекэмпа–Месси была изложе-
на Берлекэмпом в 1968 году [1] в качестве элемента конструкции декодера
кодов Боуза–Чоудхудри–Хоквингема над конечным полем. Хотя в этой ра-
боте была указана возможность формулировки решаемой задачи с исполь-
зованием понятия линейного регистра сдвига с обратной связью, алгоритм
описывался исключительно в терминах полиномов и был весьма сложен
для понимания. Спустя год Месси [2] предложил свою интерпретацию ал-
горитма, как позволяющего строить линейный регистр сдвига минималь-
ной длины, генерирующий заданную последовательность. Эта интерпрета-
ция оказалась полезной для более широкого распространения алгоритма,
получившего название по имени этих двух ученых. В некоторых работах
алгоритм излагается также с помощью непрерывных дробей и рациональ-
ной аппроксимации.
С момента появления алгоритма вышло немало работ, развивающих
и обобщающих его идеи. Ниже предложен краткий обзор его применений,
исчерпывающую библиографию можно найти в [3].
Рядом авторов решались задачи построения полинома наименьшей
степени, аннулирующего сразу несколько отрезков над полем, нахождения
рангов (степеней минимальных многочленов) всех подотрезков заданного
отрезка, обобщения на случай многомерных последовательностей (с ис-
пользованием теории базисов идеалов в кольцах полиномов от нескольких
переменных). Имеются многочисленные результаты применения алгорит-
ма для последовательностей над различными алгебраическими структура-
ми, кольцами разных видов. Были предложены вероятностные версии ал-
горитма.
Рассматриваемый алгоритм находит применение при декодировании
различных классов кодов: кодов Рида–Соломона, кодов БЧХ, циклических
и обобщенных циклических кодов, альтернантных кодов и кодов Гоппы, и,
наконец, наиболее общего и актуального на сегодня класса кодов – алгеб-
3
| Page 4 |
ро-геометрических кодов (вернее, некоторых их подклассов). Алгоритм
Берлекэмпа–Месси используется для решения ганкелевых и теплицевых,
разреженных и общих систем линейных уравнений, при поиске рацио-
нальных аппроксимаций функций и, в частности, аппроксимации Паде.
Известны также его приложения в криптографии, при тестировании псев-
дослучайных последовательностей и для быстрого вычисления в конечных
полях.
В работе поставлены следующие задачи:
1) разобрать и представить полное обоснование принципиального
алгоритма Берлекэмпа—Месси по работе [4];
2) сконструировать структурную схему алгоритма и получить про-
граммную реализацию;
3) разобрать конструкцию декодера для кодов Рида—Соломона, ос-
нованного на алгоритме Берлекэмпа—Месси, и построить струк-
турную схему.
4
| Page 5 |
2. Алгоритм Берлекэмпа–Месси
Как было отмечено во введении, задачу, решаемую алгоритмом Бер-
лекэмпа–Месси, можно сформулировать по-разному. Для детального по-
нимания принципов работы алгоритма приходится также иметь в виду не-
сколько формулировок и прибегать к каждой в разные моменты времени.
Наиболее естественным представляется отталкиваться от задачи нахожде-
ния закона рекурсии для линейной рекуррентной последовательности.
Введем ряд определений.
Определение 1. Последовательностью над полем
K
будем
называть любую функцию
, заданную на множестве целых не-
отрицательных чисел и принимающую значения в этом поле.
0
:u Ν → K
Элементы последовательности
будут обозначаться
. Будет
встречаться также понятие
u
( )
u i
отрезка последовательности, которое
получается естественным образом из ограничения функции, упомянутой в
определении.
Определение 2. Последовательность
будем называть
u
линейной
рекуррентной последовательностью (ЛРП) порядка
над полем
0
m >
K
, если существуют константы
0
1
,...,
m
f
f
−
∈K
m
j
j
u i m
f u i j
−
=
+
=
⋅
+
∑
0
≥
такие, что
1
0
(
)
(
)
, i
.
Указанное выражение назовем законом рекурсии или линейным
рекуррентным соотношением.
Как видно, первые
элементов последовательности не связаны ка-
кими-либо ограничениями – они имеют особое значение, их, как правило,
называют
m
начальным отрезком последовательности .
u
Пример 1. Пусть
2
K F
= ,
(0,1,1,1,0,0,1,0,1,1)
u =
. Легко убедиться, что
можно представить как отрезок ЛРП с
u
(1,0,1,1)
f =
. Однако, в качестве
множителей
i
f могут быть взяты
(1,1,0)
f =
. Зафиксируем возможность
5
| Page 6 |
появления такой ситуации, введя сначала понятие характеристического
полинома ЛРП.
Определение 3. Пусть u – ЛРП. Многочлен:
1
0
( )
m
m
j
j
j
F x
x
f x
−
=
=
−
⋅
∑
с коэффициентами из поля
K
(этот факт в дальнейшем оговариваться не
будет) назовем характеристическим многочленом ЛРП u .
Таким образом, каждой ЛРП можно поставить в соответствие харак-
теристический многочлен и обратно, каждому нормированному многочле-
ну можно поставить в соответствие ЛРП. Как стало ясно из примера, одна
и та же последовательность может задаваться разными законами рекурсии
и, соответственно, иметь разные характеристические полиномы.
Определение 4. Характеристический полином ЛРП
, имеющий
наименьшую степень, назовем ее
u
минимальным многочленом, а его
степень – линейной сложностью ЛРП u .
Минимальные многочлены ЛРП, а также их линейная сложность, яв-
ляются важными характеристиками ЛРП.
Определение 5. Пусть
– последовательность над полем
u
K
. Обо-
значим через
(
)
0, 1 ( (0),..., ( 1))
u
l
u
u l
− =
−
начальный отрезок . Будем го-
ворить, что многочлен
u
1
0
( )
m
m
j
j
j
G x
x
b x
−
=
=
−
⋅
∑
вырабатывает отрезок
(
)
0, 1
u
l − , если
1
0
[0,
1]: (
)
(
)
m
j
j
i
l m
u i m
b u i
−
=
∀ ∈
− −
+
=
⋅
+
∑
j
,
то есть если данный отрезок последовательности является отрезком неко-
торой ЛРП с характеристическим многочленом ( ).
G x
6
| Page 7 |
Естественным образом определяется понятие линейной сложности
отрезка последовательности как минимальной степени из всех полиномов,
вырабатывающих данный отрезок.
Далее будем рассматривать последовательности и многочлены над
некоторым полем
K
. Алгоритм Берлекэмпа–Месси строит многочлен
наименьшей степени, вырабатывающий отрезок
( )
G x
(
)
0, 1
u
l − . Чтобы пе-
рейти к непосредственному описанию алгоритма, требуется ввести еще ряд
технических определений.
Определение 6. Пусть
0
( )
n
j
j
j
H x
h
=
=
∑
x
– произвольный многочлен, а
– последовательность. Определим операцию умножения многочлена на
последовательность, результатом которой будет последовательность, такая
что:
v
( )
H x u w
⋅ =
0
( )
(
)
n
j
j
w i
h v i j
=
=
⋅
+
∑
Очевидно, операция является линейной относительно полинома,
входящего в нее.
Для нормированного полинома ( ) определим параметры:
G x
•
– количество лидирующих нулей последовательности
или
∞
, если эта последовательность нулевая;
( )
u
k G
( )
G x u⋅
•
.
( )
( ) deg( )
u
u
l G
k G
G
=
+
Легко убедиться, что
– максимальная длина начального отрез-
ка u , вырабатываемого ( )
G x . Действительно, пусть
( )
u
l G
1
0
0
( )
m
m
j
m
j
j
j
j
j
G x
g x x
b x
−
=
=
=
⋅ = −
⋅
∑
∑
, ( )
G x u v
⋅ = ,
тогда:
, но:
[0, ( )
1]: ( ) 0
u
i
l G
m
v i
∀ ∈
− −
=
7
| Page 8 |
1
0
0
0
( )
(
)
(
)
(
n
m
j
j
j
j
v i
g u i j u i m
b u i j
−
=
=
)
=
=
⋅
+ =
+
−
⋅
+
∑
∑
,
что и дает искомое:
1
0
[0, ( )
1]: (
)
(
)
m
u
j
j
i
l G m
u i m
b u i j
−
=
∀ ∈
− −
+
=
⋅
∑
+
.
Как было отмечено, существует множество вариаций исследуемого
алгоритма, приведенное ниже изложение основано на [4]. Зададимся по-
следовательностью
и числом , найдем минимальный полином, выраба-
тывающий отрезок
u
l
(
)
0, 1
u
l − . Будем строить последовательность нормиро-
ванных
полиномов
неубывающих
степеней
в соответствии с нижеследующей структурной схе-
мой.
0
1
( ), ( ),
G x G x …
0
1
2
0 m
m m
=
<
≤
≤…
8
| Page 9 |
Вход:
u
,
l
0
( ): 1
G x =
,
l
l
0
0
:
(
u
)
G
=
0
1
1
1
0
0
0
0
( ):
(
1)
( )
( )
k
G x
x
u k
u k
G x
+
−
=
−
+ ⋅
⋅
0
u
l
l G
,
1
1
:
( )
=
,
t : 1
=
0
l l<
?
Да
t
l l<
?
определим
s
из соотношения:
1
1
...
t
t
s
m m
m
m
−
+
s
=
= =
>
t
s
k k
>
?
Да
1
1
( ):
( )
( )
( )
( )
t
s
k k
t
t
t
t
s
s
G x
x
G x u k u k
G x
−
−
+
=
⋅
−
⋅
⋅
s
1
1
( ):
( )
( )
( )
( )
s
t
k k
t
t
t
t
s
s
G x
G x x
u k u k
G x
−
−
+
=
−
⋅
⋅
⋅
s
Да
Нет
( ):
( )
t
G x
G x
=
Нет
Нет
1
1
:
(
t
u
t
l
l G )
+
+
=
,
:
1
t t= +
Выход:
( )
G x
9
| Page 10 |
Обоснование алгоритма Берлекэмпа–Месси содержится в [4], но ряд
его элементов в этой работе опущен. Приведенные ниже рассуждения вос-
полняют эти пробелы. Обоснование алгоритма проведем с помощью дока-
зательства ряда лемм.
Лемма 1.
Пусть даны целое число , полином
r
0
( )
m
j
j
j
G x
g x
=
=
⋅
∑
и по-
следовательность , удовлетворяющие условию
u
( )
u
r k G
≤
. Тогда для по-
линома
( )
( )
r
G x
x G x
= ⋅
имеет место равенство:
( )
( )
u
u
k G
k G r
=
− .
Доказательство.
Обозначим:
( )
u
k k G
=
,
( )
u
k k G
=
, ( )
G x u v
⋅ = , ( )
G x u v
⋅ = .
Пусть
, где
0
( )
( )
m r
r
j
j
j
G x
x G x
g x
+
=
= ⋅
=
⋅
∑
0, 0
,
,
.
i r
i r
g
g
r i m r
−
< <
⎧
=
⎨
≤ ≤ +
⎩
Тогда:
0
0
( )
(
)
(
) [
]
(
)
(
m r
m r
m
j
j r
s
j
j r
s
v i
g u i j
g
u i j
s j r
g u i s r
v i r
+
+
−
=
=
=
=
⋅
+ =
⋅
+ = = − =
⋅
+ + =
+
∑
∑
∑
)
0
.
Если
, то
(определение
), иначе, так как
, то
, тогда:
r k
=
(0)
( )
( )
v
v r
v k
=
=
≠
k
[0,
1]: ( ) 0
i
k
v i
∀ ∈
−
=
[0,
1]: (
) 0
i
k r
v i r
∀ ∈
− −
+ =
[0,
1]: ( ) 0
i
k r
v i
∀ ∈
− −
= .
Последнее, с учетом того, что
( )
(
)
( )
v k
v k r
v k
0
=
− =
≠ , и означает
k k r
= − . Лемма доказана.
Лемма 1'. Пусть даны полиномы
,
( )
F x
( ) и последовательность
, удовлетворяющие условию
G x
u
(
)
deg ( )
( )
u
F x
k G
≤
. Тогда для полинома
( )
( ) ( )
G x
F x G x
=
⋅
имеет место равенство:
(
)
( )
( ) deg ( )
u
u
k G
k G
F x
=
−
.
10
| Page 11 |
Доказательство. Следует из леммы 1 и линейности операции умно-
жения полинома на последовательность.
Корректность алгоритма будет определяться двумя фактами: поли-
ном, получающийся на каждом шаге, во-первых, вырабатывает более длин-
ный отрезок последовательности , чем предыдущий, во-вторых, имеет
наименьшую степень из всех полиномов, вырабатывающих отрезок данной
длины.
u
Лемма 2. В ходе описанного алгоритма
возрастает, и степень
полиномов
не убывает.
( )
u
t
l G
t
m
Доказательство. Индукция по
t
:
1)
:
,
0
t
=
1
0
0
1
0
m k
m
= + >
=
1
1
1
1
0
0
0
0
1
l
k m k k
l k m k
0
= +
= + + > = +
= .
2) Предположим:
1
1
:
,
t
t
t
t t t l
l m
m
+
+
t
′
∀
<
>
≥
.
3) Пусть
, а
t t′
=
s
выбрано указанным в алгоритме образом, пока-
жем
. В случае
, очевидно,
1
t
m
m
′+
≥
t′
s
t
t
k k
>
1
t
m
m
′
′
+
>
. В другом случае сте-
пень
совпадает со степенью
, так как последняя удовлетворя-
ет соотношению:
1
( )
t
G x
′+
( )
t
G x
′
(deg ( ) )
t
t
s
t
G x
m k k
m
′
′
′
=
> − +
(
t
t
t
s
s
m k
l l m k
′
′
′
s
+ = > =
+
–
предположение индукции), то есть превосходит степень второго слагаемо-
го, составляющего
.
1
( )
t
G x
′+
Индукция завершена и лемма доказана.
Лемма 3. Пусть дана последовательность ,
– линейная слож-
ность ее отрезка длины r ,
– полином степени , такой что:
u m
( )
F x
m
( )
u
l F
r
≥ ,
( )
H x
– полином степени , такой что:
n
( )
( )
u
u
l H
l F
>
,
тогда:
{
}
max , ( ) 1
u
n
m k F
≥
+ .
Доказательство. Поскольку
, то
. Остается показать,
что
. Предположим противное:
( )
u
l H
r
>
n m
>
( ) 1
u
n k F
≥
+
( )
u
n k F
≤
. Тогда в соответст-
11
| Page 12 |
вии с леммой 1' последовательность
( )
( )
w H x F x u
=
⋅
⋅ имеет в точности
лидирующих нулей. С другой стороны,
( )
u
k F
n
−
( )
( )
w F x H x u
=
⋅
⋅ ; пока-
жем, что выполнены условия леммы 1':
( )
( )
( )
( )
( )
u
u
u
u
u
k H
l H
n l F
n l F
k F
m
=
− >
− ≥
−
=
,
то есть, действительно,
. Таким образом, можно утверждать, что
последовательность
имеет
( )
u
k F
m
>
w
( )
u
k x m
−
лидирующих нулей. Тогда
. Окончательно имеем:
( )
( )
u
u
k H
n k F
m
+ =
+
( )
( )
( )
( )
u
u
u
u
l H
k H
n k F
m l F
=
+ =
+ =
,
что противоречит условию леммы. Доказательство леммы завершено.
Лемма 4. Степени полиномов, порождаемых алгоритмом, удовле-
творяют условию:
{
}
1
max
,
1
t
t
m
m k
+
t
=
+ .
Доказательство. Индукция по
t
:
1)
: очевидно.
0
t
=
2) Предположим
{
}
1
':
max
,
1
t
t
t t t m
m k
+
∀
<
=
+
t
'
.
3) Пусть
, а
t t
=
s
выбрано указанным в алгоритме образом, пока-
жем, что
{
}
' 1
'
'
max
,
1
t
t
m
m k
+
=
t
+ . Согласно предположению индукции
{
}
1
max
,
1
s
s
m
m k
+
=
s
+
s
, а так как
'
1
t
s
m
m
m
+
=
>
, то
'
1
t
s
m
k
= + . Как видно из
рассуждений, проведенных при доказательстве леммы 2, степени полино-
мов изменяются следующим образом: если
't
k
k
s
≤ , то
, иначе
. Таким образом, в случае
' 1
'
t
m
m
+
=
t
s
k
s
' 1
'
'
t
t
t
m
m k
+
=
+ −
't
k
k
≤
, необходимо показать,
что
. И действительно,
'
'
1
t
t
m
k
≥
+
'
1
t
s
t
m
k
k
'
1
= + ≥
+ . В случае же
:
't
s
k
k
>
'
' 1
'
'
'
'
1
1
t
t
t
t
s
s
t
s
t
m
m
m k
k k
k
k k
+
<
=
+ − = + + − = +
.
Тем самым индукция завершена и лемма доказана.
Теорема 1. Изложенный алгоритм строит многочлен минимальной
степени, вырабатывающий отрезок последовательности
длины не мень-
ше чем
l
.
u
12
| Page 13 |
Доказательство. В силу леммы 2 для любого конечного наперед за-
данного за конечное число шагов на выходе алгоритма получается поли-
ном ( ), для которого
. Его степень удовлетворяет точной ниж-
ней границе для степеней всех полиномов, вырабатывающих отрезок не
короче
l
(леммы 3 и 4).
l
G x
( )
u
l G l
≥
13
| Page 14 |
3. Реализация алгоритма Берлекэмпа–Месси
Алгоритм Берлекэмпа–Месси реализован на языке программирова-
ния С++ в соответствии со стандартом языка [6] с применением объектно-
ориентированной методологии. В процессе работы над реализацией алго-
ритма была использована свободно распространяемая интегрированная
среда разработки Microsoft Visual C++ 2005 Express Edition.
В работе также использовалась библиотека с открытыми исходными
кодами Schifra Reed-Solomon Error Correcting Code Library [7], распростра-
няемая для академического и некоммерческого использования под лицен-
зией GNU General Public License (версия 2) [8], которая обеспечивает
арифметику полей Галуа и базовые операции с полиномами. Библиотека
предусматривает работу в расширениях конечных полей характеристики
два и хранит список примитивных над
полиномов степени вплоть до
шестнадцатой включительно. Последнее означает, что без дополнительных
данных работа алгоритма поддерживается в полях мощности не более
чем
.
2
F
16
2
Математический аппарат, построенный во второй главе, отображает-
ся в программную модель с точностью до одного момента. Ограничен-
ность памяти компьютера приводит к невозможности оперировать с бес-
конечными последовательностями, потому понятие линейной рекуррент-
ной последовательности было замещено понятием
линейного регист-
ра сдвига
(ЛРС). ЛРС хранит
множители
, соответствующие элемен-
там
0
,...,
m 1
f
f
−
из определения ЛРП, и текущий отрезок последовательно-
сти (длины
), необходимый для вычисления каждого последующего эле-
мента ЛРП в соответствии с линейным рекуррентным соотношением, на-
зываемый
m
состоянием
. Использование ЛРС позволит получать необ-
ходимые отрезки ЛРП.
14
| Page 15 |
Некоторые менее существенные детали реализации были скорректи-
рованы по сравнению с изложенным в главе 2, опираясь на [5].
3.1. Архитектура реализации
В реализации предусмотрено два класса для основных сущностей за-
дачи: класс линейного регистра сдвига и собственно класс алгоритма.
Также разработан ряд свободных функций и классов, предназначенных для
тестирования. Основные два класса проекта имеют слабое зацепление:
единственная информация, которую им следует разделять — фиксирован-
ный тип контейнера элементов поля (GFElementsContainer, описан в
файле
utilities.hpp
).
Ниже приведен перечень файлов, содержащих исходный код, с крат-
ким описанием их назначения:
•
LFSR.cpp
(
LFSR.hpp
) — класс линейного регистра сдвига;
•
BM-algorithm.cpp
(
BM-algorithm.hpp
) — класс, реализующий алго-
ритм вместе со вспомогательным вложенным классом Monoms
(см. п. 3.3);
•
utilities.hpp
— средства, необходимые для взаимодействия ос-
новных классов программы;
•
galois/* —
средства библиотеки Schifra, ответственные за ариф-
метику в полях Галуа и операции с полиномами над ними;
•
test/*
— тесты для основных частей программы;
•
main.cpp
— точка входа в программу.
В исходном коде присутствуют отладочные секции, которые компи-
лируются только при наличии определения макроса DEBUG; его следует
опускать в release-сборке.
15
| Page 16 |
3.2. Класс линейного регистра сдвига
Класс LFSR (Linear Feedback Shift Register — регистр сдвига с ли-
нейной обратной связью) предназначен для программного моделирования
ЛРС, который, как сказано выше, является всего лишь особым представле-
нием ЛРП. Его цель заключается в проверке корректности работы алго-
ритма: полученный на выходе алгоритма полином, дополненный последо-
вательностью элементов, выполняющей функцию, аналогичную начально-
му отрезку ЛРС, используется для построения экземпляра класса LFSR.
Далее появляется возможность получить произвольный отрезок последо-
вательности, моделируемой данным экземпляром класса LFSR, посредст-
вом последовательных вызовов экземплярной функции operator() и
убедиться таким образом, что полученный полином действительно являет-
ся характеристическим полиномом последовательности, начальный отре-
зок которой совпадает с начальным отрезком последовательности, задан-
ным алгоритму.
У данного класса имеется набор конструкторов, позволяющих кор-
ректно инициализировать два ключевых поля: кортежи множителей и со-
стояния. Кортеж множителей реализован шаблоном стандартной библио-
теки С++ vector<T>, параметризованным типом элемента поля Галуа
field_element; его размер фиксирован и не изменяется на протяжении
жизни объекта. Для кортежа состояния более приемлемым показалось ис-
пользование шаблона стандартной библиотеки С++ deque<T> — очередь
с двумя концами: на каждом такте работы LFSR (то есть после каждого
вызова функции operator()) вычисляется очередной элемент ЛРП, ко-
торый добавляется в конец кортежа состояния, а клиенту возвращается
элемент из начала этого кортежа. Таким образом размер очереди также ос-
тается неизменным.
16
| Page 17 |
Для класса LFSR предусмотрен оператор вывода в поток, обеспечи-
вающий возможность печати содержимого объекта данного класса.
3.3. Класс алгоритма
В классе алгоритма BMAlgorithm реализованы основные операции,
использованные при изложении алгоритма Берлекэмпа — Месси, как-то:
умножение полинома на последовательность и подсчет количества лиди-
рующих нулей в последовательности. После создания экземпляра класса
(конструктор принимает лишь ссылку на объект класса field, представ-
ляющего конечное поле, в котором производятся вычисления), его запуск
производится посредством вызова функции-члена operator(); в каче-
стве единственного аргумента указанной функции передается отрезок
ЛРП, для которого необходимо построить минимальный многочлен.
Описанный в главе 2 алгоритм непосредственно выполняется в теле
функции operator(). Шаги алгоритма отображаются на операторы язы-
ка программирования почти дословно.
В ходе алгоритма возникает необходимость многократно вычислять
мономы различных степеней (выражения вида
r
x
). С целью оптимизации
этого действия был создан класс Monoms, объявленный внутри класса
BMAlgorithm и являющийся тривиальной оберткой шаблона стандарт-
ной библиотеки С++ map<T>. Объект этого класса создается вместе с эк-
земпляром класса BMAlgorithm, он кэширует мономы, вычисленные на
предыдущих шагах работы алгоритма, и в ответ на запрос монома кон-
кретной степени (вызов функции operator[]) либо возвращает ссылку
на константу (такого уровня доступа оказывается достаточно, учитывая
что мономы используются при расчете арифметических выражений), вы-
численную ранее, либо вычисляет требуемое значение, добавляет в свою
коллекцию и также возвращает ссылку на константу.
17
| Page 18 |
Стоит заметить, что выразительность, достигнутая широким исполь-
зованием перегруженных арифметических операторов, как и обычно в
языке С++, не обходится даром — в ходе работы алгоритма создается
большое количество временных объектов. Возможным путем избежать на-
кладных расходов, связанных с этим, является использование техники Ex-
pression Templates, описанной, например, в [9]. Впрочем, это потребовало
бы существенного вмешательства в исходный код библиотеки, что выхо-
дит за рамки поставленных задач.
3.4. Тестирование
Хотя практически весь исходный код был в той или иной степени
покрыт набором тестов, основным объектом тестирования стал, конечно,
класс BMAlgorithm. Здесь же стоит отметить, что корректность библио-
течных средств также была установлена при помощи написания отдельно-
го ряда тестов. Для основного класса программы было предусмотрено два
основных тестовых случая:
• длинная псевдослучайная последовательность;
• все возможные последовательности заданной длины (учиты-
вая, что вычисления проводятся в конечных полях, количество
таких последовательностей конечно).
Для запуска проверки указанных тестовых случаев созданы две сво-
бодных
функции: totalSequencesTesting(), testLongSe-
quence(). Для реализации обеих проверок был использован класс Se-
quenceTester, описание которого приведено ниже.
Назначение класса SequenceTester — предоставить средства
проверки корректности работы алгоритма на одной заданной последова-
тельности. Проверка запускается вызовом метода testSequence(), в
качестве аргумента которому передается тестовая последовательность. Да-
лее логика работы такова:
18
| Page 19 |
4) построение с помощью имеющегося у каждого объекта-теста эк-
земпляра алгоритма минимального полинома для данной после-
довательности;
5) создание ЛРС (объекта LFSR) на основе полученного полинома;
6) проверка на равенство исходной последовательности и той, кото-
рую генерирует ЛРС.
Класс способен регистрировать два вида ошибок, что отражено в на-
личии объявленного внутри SequenceTester перечисления Failure-
Reason:
• п.1 завершается неудачей: зацикливание при работе алгоритма
(в процессе создания полинома выбрасывается исключение) —
константа ENDLESS_LOOP;
• п.3 завершается неудачей: получаемая на выходе ЛРС после-
довательность не совпадает с исходной — константа
NOT_MATCH.
При возникновении одной из двух указанных ситуаций, тестируемая
последовательность вместе с кодом ошибки заносится в коллекцию оши-
бок, хранимую объектом теста. Клиент класса может осведомиться о нали-
чии ошибок, вызвав метод hasFailures() и, если таковые имеются, вы-
вести их на консоль.
Если случай единственной, произвольно длинной (с учетом естест-
венных ограничений вычислительных ресурсов) псевдослучайной после-
довательности не представил особых препятствий в реализации (все све-
лось к последовательным вызовам стандартной библиотечной функции
rand() и передаче полученной последовательности объекту Se-
quenceTester), то генерация всех последовательностей заданной длины
является известной комбинаторной задачей, функционал которой был вы-
несен в отдельный класс — SequencesGenerator, при этом возникла
необходимость принять не слишком привлекательное в отношении дизай-
19
| Page 20 |
на тестового модуля решение. Поскольку работа генератора строится из
последовательных рекурсивных вызовов одной функции (sequences-
Generating()), то каждый раз возвращать клиенту очередную постро-
енную последовательность не удается. Возможны два варианта: предлагать
в качестве результата работы основного интерфейсного метода класса
(operator()) набор из всех последовательностей и затем, для каждого
элемента такого набора вызывать тестовый метод класса Se-
quenceTester — но это вызвало бы большие затраты памяти; либо вы-
зывать упомянутый тестовый метод прямо в процессе генерации, внутри
объекта класса SequencesGenerator. В итоге был реализован второй
вариант: объект
класса-генератора
владеет
экземпляром
Se-
quenceTester и вызывает его тестовый метод по мере формирования
каждой следующей последовательности. Следует отметить, что в совре-
менных языках программирования имеются средства получать промежу-
точные результаты работы рекурсивных функций без полной раскрутки
стека вызовов (например, инструмент generators в языке Python).
20
| Page 21 |
4. Декодер для кодов Рида–Соломона
Как уже было отмечено во введении, алгоритм Берлекэмпа–Месси
имеет многочисленные применения. Однако наиболее важным с практиче-
ской точки зрения представляется использование данного алгоритма в ка-
честве конструктивного элемента декодера кодов Рида–Соломона. Ниже
приведено определение кодов Рида–Соломона и описание декодера [10].
Определение 1.
Линейным кодом длины n размерности
k
называется -мерное подпространство линейного векторного простран-
ства
.
k
n
q
F
Определение 2.
Кодом Рида–Соломона
размерности
назы-
вается линейный код длины
1
k
n q
= − , изоморфный идеалу
(
( )
)
I
g x
=
фак-
торкольца
[ ] (
1)
n
n
q
F x x − , где:
2
( ) (
)(
)...(
)
n k
g x
x
x
x
α
α
α
−
= −
−
−
,
α
— примитивный элемент
.
n
q
F
Можно показать, что коды Рида—Соломона являются МДР-кодами,
то есть имеют минимальное кодовое расстояние
1
d n k
= − + и, таким об-
разом, исправляют не более
2
n k
t
−
⎢
⎥
=
⎢
⎥
⎣
⎦
ошибок.
Информационное сообщение — вектор длины
над
представля-
ется в виде полинома ( )
k
n
q
F
f x
степени не выше
1
k
− . Кодирование произво-
дится посредством умножения:
( )
( ) ( )
c x
f x g x
=
⋅
.
По каналу приходит слово ( ), в котором имеется аддитивная
ошибка
:
v x
1
0
( )
n
i
i
i
e x
e x
−
=
=
⋅
∑
( )
( )
( )
r x c x e x
=
+
.
Задача декодера — вычислить ( ).
e x
21
| Page 22 |
После получения слова из канала декодер вычисляет компоненты
синдрома
по формуле:
j
S
[1,
]:
( )
j
j
j
n k S
r
α
∀ ∈
−
=
,
заметим, что ( )
(
j
r
e
)
j
α
α
=
. То есть:
1
0
[1,
]:
n
i j
j
i
i
j
n k S
e
α
−
⋅
=
∀ ∈
−
=
⋅
∑
.
Если все компоненты равны нулю, то считается, что ошибок не произош-
ло.
Определим
локаторы ошибок
j
x
и
величины ошибок
следующим образом:
j
y
[1, ]:
,
j
j
a
j
j
a
e
j
x
y
ν
α
∀ ∈
=
=
,
{ |
0}
j
i
a
i e
∈
≠ .
Тогда для
получим систему уравнений:
j
S
(*)
0
[1,
]:
j
j
i
i
j
n k S
y x
ν
=
∀ ∈
−
=
⋅
∑
i
Декодер работает в предположении, что в канале произошло не бо-
лее чем
t
ошибок, в таком случае:
t
ν
≤ .
Получившаяся система выглядит пессимистично: неизвестны
,
i
y
i
x
,
ν
. Будем находить сначала
i
x
и
ν
. Введем еще один вспомогательный
объект —
полином локаторов ошибок
( )
z
σ
:
1
1
2
1
( ) (
)(
) (
)
i
i
i
z
z x z x
z x
z
ν
ν
ν
z
σ
σ
−
=
= −
−
−
=
+
∑
…
.
Запишем для
[1, ],
[1,
]
i
j
n k
ν
∀ ∈
∀ ∈
− :
1
1
0
( )
j
j
j
i
i
i
i
i
i
i
i
i
y x
x
y x
y x
y x
ν
ν
ν
σ
σ
σ
+
+ −
= ⋅ ⋅
= ⋅
+ ⋅ ⋅
+ +
⋅ ⋅
…
j
1
j
j
S
ν
.
Просуммировав по
i
, находим:
1
1
1
1
[1,
]:0
j
j
i
i
i
i
i
i
i
i
i
j
n k
y x
y x
y x
ν
ν
ν
ν
ν
ν
σ
σ
+
+ −
=
=
=
∀ ∈
−
=
⋅
+ ⋅
⋅
+ +
⋅
⋅
∑
∑
∑
…
,
или:
1
1
[1,
]:
j
j
j
n k S
S
ν
ν
σ
σ
+
+ −
∀ ∈
−
= − ⋅
− −
⋅
…
.
22
| Page 23 |
Последнее можно представить в матричном виде:
1
2
2
3
1
1
1
1
1
n k
n k
n k
n k
S
S
S
S
S
S
S
S
S
S
S
S
ν
ν
ν
ν
ν
1
2
ν
ν
ν
σ
σ
σ
+
+
−
−
− +
− + −
−
⎛
⎞ ⎛
−
⎜
⎟ ⎜
⋅ −
=
⎜
⎟ ⎜
⎜
⎟ ⎜
−
⎝
⎠ ⎝
…
…
…
+
+
⎞ ⎛
⎞
⎟ ⎜
⎟
⎟ ⎜
⎟
⎟ ⎜
⎟
⎠ ⎝
⎠
В действительности имеется
n k
− компонент синдрома, потому по-
следние
ν
уравнений не рассматриваются. Система примет вид:
1
2
2
3
1
1
1
1
1
n k
n k
n k
n k
S
S
S
S
S
S
S
S
S
S
S
S
ν
ν
ν
ν
ν
ν
σ
σ
σ
+
+
−
− −
− − +
− −
−
⎛
⎞
−
⎜
⎟
⋅ −
=
⎜
⎟
⎜
⎟
−
⎝
⎠
…
…
…
1
2
ν
ν +
⎛
⎞ ⎛
⎞
⎜
⎟ ⎜
⎟
⎜
⎟ ⎜
⎟
⎜
⎟ ⎜
⎟
⎝
⎠ ⎝
⎠
.
Можно показать, что матрица этой системы – назовем ее M – нев-
вырождена в том случае, если в канале произошло ровно
ν
ошибок (поли-
ном ( ) имеет
e x
ν
ненулевых коэффициентов), и вырождена, если ошибок
меньше. Это условие дает способ нахождения
ν
.
Как видно, полученная система задает отрезок линейной рекуррент-
ной последовательности ( ), множители
S i
j
σ
−
которой могут быть найде-
ны с помощью алгоритма Берлекэмпа—Месси. Таким образом может быть
найден полином локаторов ошибок ( )
z
σ
.
Далее находятся корни ( )
z
σ
— как правило, с помощью перебора
элементов поля
(
q
F процедура Ченя
). Затем решается система (*) —
существуют эффективные методы ее решения, например,
алгоритм
Форни
. После этого уже может быть восстановлен ( ). Окончательно,
общая схема декодера, носящего имена Питерсона, Горенстейна и Цирле-
ра, может быть представлена следующим образом.
e x
23
| Page 24 |
Вход:
( )
r x
[1,
]: : ( )
j
j
j
n k S
r
α
∀ ∈
−
=
,
: t
ν
=
24
Да
Нет
Выход:
( )
e x
1
1
:
n k
n k
S
S
M
S
S
ν
ν
− −
− −
⎛
⎞
=
⎜
⎟
⎜
⎟
⎝
⎠
…
…
:
1
ν ν
= −
det( ) 0
M =
?
нахождение
( )
z
σ
с помощью
алгоритма Берлекэмпа—Месси
вычисление локаторов ошибок
i
x
с
помощью отыскания корней
( )
z
σ
решение системы:
0
[1,
]:
j
j
i
i
j
n k S
y x
ν
=
∀ ∈
−
=
⋅
∑
i
относительно
i
y
восстановление
e x
по
( )
i
x
,
i
y
| Page 25 |
5. Литература
1. Berlekamp E. R. Algebraic Coding Theory. – New York: McGrow Hill, 1968
(перевод: Берлекэмп Э. Алгебраическая теория кодирования. – М.: Мир,
1971).
2. Massey J.L., Shift Register Synthesis and BCH Decoding, // IEEE Trans. In-
form. Theory. — vol. IT-15, no. 1, 1969.
3. Куракин. Алгоритм Берлекэмпа-Месси над коммутативными артино-
выми кольцами главных идеалов // Фундаментальная и прикладная ма-
тематика. — Том 5, вып. 4, 1999.
4. V. L. Kurakin, A. S. Kuzmin, A. V. Mikhalev, A. A. Nechaev. Linear recur-
ring sequences over rings and modules. // I. of Math. Science. Contemporary
Math. and it's Appl. Thematic surveys, vol. 10, 1994, I. of Math. Sciences,
vol. 76, № 6, 1995.
5. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы
криптографии: учебное пособие. 3-е изд., испр. и доп. — М.: Гели-
ос АРВ, 2005.
6. ISO Information Technology — Programming Languages — C++ Document
Number ISO/IEC 14882-1998 ISO/IEC, 1998.
7. Schifra
Reed-Solomon
Error
Correcting
Code
Library,
http://www.schifra.com/.
8. The GNU General Public License (GPL), Version 2, June 1991,
http://www.opensource.org/
9. Vandevoorde, D., N.M. Josuttis. C++ Templates. Boston: Addison-Wesley,
2003. ISBN 0201734842 (перевод: Вандевурд Д., Джосаттис Н. Шаблоны
С++: справочник разработчика. — М.: Издательский дом «Вильямс»,
2003).
10.Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с
англ. — М.: Мир, 1986.
25
| Page 26 |
Приложение
26
Приложение
Класс линейного регистра сдвига
LFSR.hpp
#ifndef LFSR_HPP
#define LFSR_HPP
#include "utilities.hpp"
#include "galois\schifra_galois_field.
#include "galois\schifra_galois_field_
#include <vector>
#include <deque>
#include <cstddef>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace schifra::galois;
using std::vector;
using std::deque;
using std::size_t;
using std::back_inserter;
using std::ostream;
class LFSR {
typedef vector<field_element> MultipliersContainer;
typedef deque<field_element> StateContainer;
MultipliersContainer multipliers;
StateContainer state;
public:
LFSR( field_element* const _muls, field_element* const _st, const
size_t size ) {
multipliers.reserve( size );
std::copy( _muls, _muls + size, back_inserter( multipliers ) );
std::copy( _st, _st + size, back_inserter( state ) );
}
LFSR( const field_polynomial& poly, field_element* _st );
LFSR( const field_polynomial& poly, const GFElementsContainer& _st );
LFSR( field& _gf ) : multipliers( 1, field_element( &_gf, 0) ),
state( 1, field_element( &_gf, 0) ) {}
field_element operator()();
size_t length() const {
return multipliers.size();
| Page 27 |
Приложение
27
}
void setState( const StateContainer& newstate ) {
state = newstate;
}
friend ostream& operator<<( ostream& os, const LFSR& lfsr );
};
ostream& operator<<( ostream& os, const LFSR& lfsr );
#endif // LFSR_HPP
LFSR.cpp
#include "LFSR.hpp"
#include <algorithm>
#include <numeric>
#include <string>
#include "galois\schifra_galois_field_
ostream& operator<<( ostream& os, const LFSR& lfsr ) {
using namespace std;
const size_t width = 79;
string boldline( width, '=' );
// string line( width, '-' );
cout << boldline << endl << "LFSR:" << endl << "size:\t\t" <<
lfsr.length() << endl;
cout << "multipliers:\t";
copy( lfsr.multipliers.begin(), lfsr.multipliers.end(),
ostream_iterator<schifra::
cout << endl << "state:\t\t";
copy( lfsr.state.begin(), lfsr.state.end(),
ostream_iterator<schifra::
cout << endl << boldline << endl;
return os;
}
field_element LFSR::operator()() {
field_element result( state.front() );
const field_element INIT( result.galois_field(), 0 );
field_element newElement = std::inner_product( state.begin(),
state.end(), multipliers.begin(), INIT );
state.push_back( newElement );
state.pop_front();
return result;
}
LFSR::LFSR( const field_polynomial& poly, field_element* _st ) {
// it is assumed that the _st points to poly.deg()-number of
field_elements
size_t polydeg = poly.deg();
const field_element ZERO( poly.galois_field(), 0 );
multipliers.reserve( polydeg );
| Page 28 |
Приложение
28
for( size_t i = 0; i < polydeg; ++i, ++_st ) {
multipliers.push_back( ZERO - poly[i] );
state.push_back( *_st );
}
}
LFSR::LFSR( const field_polynomial& poly, const GFElementsContainer& _st )
{
// it is assumed that the _st contains poly.deg()-number of
field_elements
size_t polydeg = poly.deg();
const field_element ZERO( poly.galois_field(), 0 );
multipliers.reserve( polydeg );
GFElementsContainer::const_
for( size_t i = 0; i < polydeg; ++i, ++stIter ) {
multipliers.push_back( ZERO - poly[i] );
state.push_back( *stIter );
}
}
BM-algorithm.hpp
#ifndef BM_ALGORITHM_HPP
#define BM_ALGORITHM_HPP
#include "utilities.hpp"
#include "galois\schifra_galois_field.
#include "galois\schifra_galois_field_
#include "galois\schifra_galois_field_
#include <vector>
#include <map>
#include <cstddef>
using std::size_t;
using namespace schifra::galois;
class BMAlgorithm {
public:
BMAlgorithm( field& _gf ) : gf(_gf), monoms( gf ) {}
GFElementsContainer polySeqProduct( const field_polynomial& poly,
const
GFElementsContainer& seq );
size_t countLeadingZeroes( GFElementsContainer seq );
field_polynomial operator()( const GFElementsContainer& seq );
field_polynomial operator()( field_element* const gfes, size_t size );
class Monoms {
public:
Monoms( field& _gf ) : gf(_gf) {
field_element gfes[] = { field_element ( &gf, 0 ),
field_element ( &gf, 1 ) };
data[0] = field_polynomial( &gf, 0, gfes + 1 );
| Page 29 |
Приложение
29
data[1] = field_polynomial( &gf, 1, gfes );
}
field_polynomial const & operator[]( size_t degree );
private:
typedef std::map <size_t, field_polynomial> Container;
field& gf;
Container data;
void operator=( const Monoms& );
};
private:
field& gf;
Monoms monoms;
// BMAlgorithm
void operator=( const BMAlgorithm& );
};
#endif // BM_ALGORITHM_HPP
BM-algorithm.cpp
#include "BM-algorithm.hpp"
#include "galois\schifra_galois_field.
#include "galois\schifra_galois_field_
#include <algorithm>
#include <iterator>
#include <fstream>
#include <vector>
#include <iostream>
#include <utility>
#include <limits>
#include <stdexcept>
#include <cassert>
#include <cstddef>
using schifra::galois::field_
using schifra::galois::field_
using std::size_t;
static void printSequence( const GFElementsContainer& seq,
std::ostream &out = std::cout );
GFElementsContainer BMAlgorithm::polySeqProduct( const field_polynomial&
poly,
const
GFElementsContainer& seq ) {
assert( poly.deg() < (int)seq.size() );
const size_t poly_deg = poly.deg();
const size_t res_size = seq.size() - poly_deg;
GFElementsContainer result( res_size );
for ( size_t i = 0; i < res_size; ++i ) {
result[i] = poly[0] * seq[i];
for ( size_t j = 1; j <= poly_deg; ++j ) {
| Page 30 |
Приложение
30
result[i] += poly[j] * seq[i + j];
}
}
return result;
}
size_t BMAlgorithm::
size_t res = 0;
const field_element ZERO( &gf, 0 );
while( res < seq.size() && seq[res] == ZERO )
++res;
// return (res == seq.size()) ? std::numeric_limits<size_t>::
res;
return res;
}
field_polynomial const & BMAlgorithm::Monoms::operator[
Container::iterator it = data.find( degree );
if ( it == data.end() ) {
field_polynomial& x = data[1];
field_polynomial result( x );
for (size_t i = 1; i < degree; ++i) {
result *= x;
}
return ( ( data.insert( std::make_pair( degree, result ) ) ).first
)->second;
} else {
return it->second;
}
}
field_polynomial BMAlgorithm::operator()( field_element* const gfes, size_t
size ) {
GFElementsContainer seq;
seq.reserve( size );
std::copy( gfes, gfes + size, back_inserter( seq ) );
return (*this)(seq);
}
field_polynomial BMAlgorithm::operator()( const GFElementsContainer& seq )
{
size_t k_old = 0, k = 0;
size_t step = 1, maxsteps = seq.size();
const size_t INFINITY = std::numeric_limits<size_t>::
//std::cout << "Sequence: ";
//std::copy( seq.begin(), seq.end(),
// std::ostream_iterator<field_
//std::cout << std::endl;
k_old = countLeadingZeroes( seq );
// if ( k_old == INFINITY ) // initial sequence is nullity
if ( k_old == seq.size() )
return monoms[1]; // minimal polynomial "x" leads to LFSR
with one multiplier - 0
if ( k_old == seq.size() - 1 ) // sequences like 0...0a with
length n produced by
return monoms[ seq.size() ]; // LFSR 0...0 whith length n - not
shorter!
| Page 31 |
Приложение
31
field_polynomial G_old( &gf );
field_polynomial G( &gf );
field_polynomial G_new( &gf );
try {
G_old = monoms[0];
G = monoms[k_old + 1]
- seq[k_old + 1] * seq[k_old].inverse() *
monoms[k_old] * G_old ;
G_new = G;
} catch (...) {
std::cout << "critical error" << std::endl;
}
GFElementsContainer u, u_old;
u = polySeqProduct( G, seq ); u_old = seq ;
k = countLeadingZeroes( u );
// std::ostream &out = std::cout;
// std::ofstream outf("D:/Coding/trace.txt");
// std::ostream &out = outf;
// while ( k != INFINITY ) {
while ( k + G.deg() < seq.size() ) {
// std::cout << G.deg() << std::endl;
if( step++ > maxsteps )
throw std::logic_error("Too many iterations!");
//if ( int(k) - int(k_old) > 1 ) {
//out << "G_old:\t" << G_old << std::endl;
//out << "G:\t\t" << G << std::endl;
//out << "k_old:\t" << k_old << std::endl;
//out << "k:\t\t" << k << std::endl;
//out << "u_old:\t";
//printSequence(u_old, out);
//out << "u:\t\t";
//printSequence(u, out);
//out << "_____________________________
//out << std::endl;
//}
field_polynomial temp( u[k] * u_old[k_old].inverse() * G_old );
if ( k <= k_old ) {
G_new = G - monoms[k_old - k] * temp;
} else {
G_new = monoms[k - k_old] * G - temp;
}
assert( G_new.deg() >= G.deg() );
if ( G_new.deg() > G.deg() ) {
k_old = k;
u_old = u;
G_old = G;
}
G = G_new;
u = polySeqProduct( G_new, seq );
k = countLeadingZeroes( u );
}
return G_new;
}
void printSequence( const GFElementsContainer& seq,
std::ostream &out ) {
copy( seq.begin(), seq.end(),
std::ostream_iterator<field_
out << std::endl;
}
| Page 32 |
Приложение
32
Модуль тестирования алгоритма
testBM-Algorithm.hpp
#ifndef TESTBM_ALGORITHM_HPP
#define TESTBM_ALGORITHM_HPP
int testBMA();
#endif // TESTBM_ALGORITHM_HPP
testBM-Algorithm.сpp
#include "testBM-Algorithm.hpp"
#include "BM-Algorithm.hpp"
#include "LFSR.hpp"
#include "galois\schifra_galois_field.
#include "galois\schifra_galois_field_
#include "galois\schifra_galois_field_
#include <algorithm>
#include <utility>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <iterator>
#include <limits>
#include <cstddef>
#include <cstdlib>
#include <stdexcept>
using namespace schifra::galois;
using std::copy;
using std::cout;
using std::endl;
using std::size_t;
using std::ostream_iterator;
unsigned int prim_poly2[] = {1, 1, 1};
const unsigned int * prim_poly3 = primitive_polynomial00;
const unsigned int size = 3;
field gf ( 3, 3, prim_poly3 );
const field_element ZERO( &gf, 0 );
BMAlgorithm alg( gf );
field_element gfes[] = {
field_element(&gf,1),
field_element(&gf,2),
field_element(&gf,3),
field_element(&gf,3),
field_element(&gf,2),
field_element(&gf,1),
field_element(&gf,1),
field_element(&gf,3),
field_element(&gf,2),
field_element(&gf,2),
field_element(&gf,3),
field_element(&gf,1)
};
field_polynomial poly1( &gf, 1, gfes ); // ( &gf, 2, gfes);
| Page 33 |
Приложение
33
int testPolySeqProduct();
int testCountLeadingZeroes();
int testMonoms();
int testAlg();
int totalSequencesTesting();
int testLongSequence();
void printSequence( const GFElementsContainer& seq,
std::ostream &out = std::cout );
int testBMA() {
//testPolySeqProduct();
//testCountLeadingZeroes();
// testMonoms();
// testAlg();
totalSequencesTesting();
// testLongSequence();
return 0;
}
int testMonoms() {
BMAlgorithm::Monoms monoms( gf );
for ( size_t i = 0; i < 9; ++i) {
cout << monoms[i] << endl;
}
for ( int i = 10; i >= 0; --i)
cout << monoms[0] << endl;
return 0;
}
int testCountLeadingZeroes() {
GFElementsContainer seq1(4);
seq1[0] = gfes[0];
seq1[1] = gfes[1];
seq1[2] = gfes[2];
seq1[3] = gfes[3];
BMAlgorithm alg( gf );
GFElementsContainer seq2(4);
seq2[0] = field_element(&gf,1);
seq2[1] = gfes[1];
seq2[2] = gfes[2];
seq2[3] = gfes[3];
assert( alg.countLeadingZeroes(seq2) == 0 );
seq2[0] = field_element(&gf,0);
seq2[1] = field_element(&gf,0);
assert( alg.countLeadingZeroes(seq2) == 2 );
seq2[2] = field_element(&gf,0);
seq2[3] = field_element(&gf,0);
assert( alg.countLeadingZeroes(seq2) ==
std::numeric_limits<size_t>::
//cout <<
return 0;
}
int testPolySeqProduct() {
GFElementsContainer seq1(4);
seq1[0] = gfes[0];
| Page 34 |
Приложение
34
seq1[1] = gfes[1];
seq1[2] = gfes[2];
seq1[3] = gfes[3];
BMAlgorithm alg( gf );
GFElementsContainer prod1 = alg.polySeqProduct( poly1, seq1 );
assert( gfes[0]*gfes[1] + gfes[1]*gfes[2] == prod1[1] );
// cout << alg(seq1) << endl;
//std::cout << prod1.size() << endl;
//copy( prod1.begin(), prod1.end(),
std::ostream_iterator<field_
//std::cout << endl;
// cout << gfes[0]*gfes[1] + gfes[1]*gfes[2] << endl;
return 0;
}
int testAlg() {
field_element gfes[] = {
field_element(&gf,3),
field_element(&gf,1),
field_element(&gf,0),
field_element(&gf,5),
field_element(&gf,4),
field_element(&gf,7),
field_element(&gf,2)
};
cout << "GF(8)" << endl << "init sequence:\t";
for ( size_t i = 0; i < 7; ++i ) {
cout << gfes[i] << " ";
}
cout << endl << endl;
field_polynomial poly( alg( gfes, 7 ) );
LFSR lfsr( poly, gfes );
cout << lfsr;
cout << "LFSR works:\t";
for ( size_t i = 0; i < 20; ++i ) {
cout << lfsr() << " ";
}
cout << endl;
return 0;
}
class SequenceTester {
public:
enum FailureReason { ENDLESS_LOOP = 0, NOT_MATCH = 1 };
SequenceTester( field& _gf ) : gf( _gf ),
alg( gf ),
failures() {
}
void testSequence( const GFElementsContainer& initseq ) {
try {
field_polynomial poly( alg( initseq ) );
LFSR lfsr( poly, initseq );
GFElementsContainer resultseq;
std::generate_n( std::back_inserter( resultseq ),
initseq.size(), lfsr);
if ( initseq != resultseq )
| Page 35 |
Приложение
35
failures.push_back( std::make_pair( NOT_MATCH, initseq ) );
} catch( const std::logic_error& ) {
failures.push_back( std::make_pair( ENDLESS_LOOP, initseq ) );
}
}
bool hasFailures() { return !failures.empty(); }
void printFailures() {
const FailuresContainer::const_
for ( FailuresContainer::const_
!= end; ++it ) {
cout << std::setw(12) <<
( it->first == NOT_MATCH ) ? "Not match:" : "Endless
loop:";
copy( it->second.begin(), it->second.end(),
ostream_iterator<field_
cout << endl;
}
}
private:
field& gf;
BMAlgorithm alg;
typedef std::list< std::pair< FailureReason , GFElementsContainer > >
FailuresContainer;
FailuresContainer failures;
};
class SequencesGenerator {
field& gf;
const size_t length;
GFElementsContainer currentSequence;
SequenceTester& tester;
public:
SequencesGenerator( field& _gf, size_t _len, SequenceTester& _tester )
: gf( _gf ),
length( _len ), currentSequence( length ),
tester( _tester ) {}
void operator()() {
sequencesGenerating( 0 );
if ( tester.hasFailures() ) {
cout << "There were failures!" << endl;
} else {
cout << "Succeed!" << endl;
}
}
void sequencesGenerating( size_t currentElementToChangeIdx ) {
for ( size_t i = 0; i <= gf.mask(); ++i ) {
currentSequence[ currentElementToChangeIdx ] = field_element(
&gf, i );
if ( currentElementToChangeIdx == length - 1 ) {
tester.testSequence( currentSequence ); // next sequence to
test is ready
// testSequence(); // - just to print
} else {
sequencesGenerating( currentElementToChangeIdx + 1 ); //
recursion!
}
}
}
| Page 36 |
Приложение
36
void testSequence() { // stub
copy( currentSequence.begin(), currentSequence.end(),
ostream_iterator<field_
cout << endl;
}
private:
void operator=( const SequencesGenerator& );
};
int totalSequencesTesting() {
SequenceTester tester( gf );
SequencesGenerator generator( gf, 5, tester );
generator();
return 0;
}
int testLongSequence() {
//field gf(primitive_polynomial_size14 - 1, primitive_polynomial_size14
- 1,
// primitive_polynomial14); // 17
//field gf( primitive_polynomial_size11 - 1,
primitive_polynomial_size11 - 1,
// primitive_polynomial11); // 13
const size_t len = 100;
const size_t fieldSize = gf.mask() + 1;
GFElementsContainer seq;
for( size_t i = 0; i < len; ++i )
seq.push_back( field_element( &gf, rand()%fieldSize ) );
// printSequence( seq );
SequenceTester tester( gf );
tester.testSequence( seq );
if ( tester.hasFailures() ) {
cout << "There were failures!" << endl;
} else {
cout << "Succeed!" << endl;
}
// std::system("pause");
return 0;
}
void printSequence( const GFElementsContainer& seq,
std::ostream &out ) {
copy( seq.begin(), seq.end(),
ostream_iterator<field_
out << endl;
}