Алгоритм Берлекэмпа - Месси
Автор работы: Пользователь скрыл имя, 14 Мая 2013 в 14:33, дипломная работа
Описание работы
Первоначальная версия алгоритма Берлекэмпа–Месси была изложе-
на Берлекэмпом в 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 файл
Федеральное агентство по образованию РФ
Федеральное государственное образовательное
учреждение высшего профессионального образования
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Факультет математики, механики и компьютерных наук
Кафедра алгебры и дискретной математики
АЛГОРИТМ БЕРЛЕКЭМПА—МЕССИ
ДЛЯ ПОЛЕЙ ГАЛУА И ЕГО ПРИМЕНЕНИЕ
Выпускная квалификационная работа
студента 4 курса очной формы обучения
А. М. Пеленицына
Научный руководитель:
доцент, к.ф.-м.н.
В. М. Деундяк
Ростов-на-Дону
2007
Содержание
1. Введение и постановка задачи.......................................................................3
2. Алгоритм Берлекэмпа–Месси........................................................................5
3. Реализация алгоритма Берлекэмпа–Месси.................................................14
3.1. Архитектура реализации .......................................................................15
3.2. Класс линейного регистра сдвига.........................................................16
3.3. Класс алгоритма .....................................................................................17
3.4. Тестирование ..........................................................................................18
4. Декодер для кодов Рида–Соломона ............................................................21
5. Литература .....................................................................................................25
Приложение .......................................................................................................26
2
1. Введение и постановка задачи
Первоначальная версия алгоритма Берлекэмпа–Месси была изложе-
на Берлекэмпом в 1968 году [1] в качестве элемента конструкции декодера
кодов Боуза–Чоудхудри–Хоквингема над конечным полем. Хотя в этой ра-
боте была указана возможность формулировки решаемой задачи с исполь-
зованием понятия линейного регистра сдвига с обратной связью, алгоритм
описывался исключительно в терминах полиномов и был весьма сложен
для понимания. Спустя год Месси [2] предложил свою интерпретацию ал-
горитма, как позволяющего строить линейный регистр сдвига минималь-
ной длины, генерирующий заданную последовательность. Эта интерпрета-
ция оказалась полезной для более широкого распространения алгоритма,
получившего название по имени этих двух ученых. В некоторых работах
алгоритм излагается также с помощью непрерывных дробей и рациональ-
ной аппроксимации.
С момента появления алгоритма вышло немало работ, развивающих
и обобщающих его идеи. Ниже предложен краткий обзор его применений,
исчерпывающую библиографию можно найти в [3].
Рядом авторов решались задачи построения полинома наименьшей
степени, аннулирующего сразу несколько отрезков над полем, нахождения
рангов (степеней минимальных многочленов) всех подотрезков заданного
отрезка, обобщения на случай многомерных последовательностей (с ис-
пользованием теории базисов идеалов в кольцах полиномов от нескольких
переменных). Имеются многочисленные результаты применения алгорит-
ма для последовательностей над различными алгебраическими структура-
ми, кольцами разных видов. Были предложены вероятностные версии ал-
горитма.
Рассматриваемый алгоритм находит применение при декодировании
различных классов кодов: кодов Рида–Соломона, кодов БЧХ, циклических
и обобщенных циклических кодов, альтернантных кодов и кодов Гоппы, и,
наконец, наиболее общего и актуального на сегодня класса кодов – алгеб-
3
ро-геометрических кодов (вернее, некоторых их подклассов). Алгоритм
Берлекэмпа–Месси используется для решения ганкелевых и теплицевых,
разреженных и общих систем линейных уравнений, при поиске рацио-
нальных аппроксимаций функций и, в частности, аппроксимации Паде.
Известны также его приложения в криптографии, при тестировании псев-
дослучайных последовательностей и для быстрого вычисления в конечных
полях.
В работе поставлены следующие задачи:
1) разобрать и представить полное обоснование принципиального
алгоритма Берлекэмпа—Месси по работе [4];
2) сконструировать структурную схему алгоритма и получить про-
граммную реализацию;
3) разобрать конструкцию декодера для кодов Рида—Соломона, ос-
нованного на алгоритме Берлекэмпа—Месси, и построить струк-
турную схему.
4
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
появления такой ситуации, введя сначала понятие характеристического
полинома ЛРП.
Определение 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
Естественным образом определяется понятие линейной сложности
отрезка последовательности как минимальной степени из всех полиномов,
вырабатывающих данный отрезок.
Далее будем рассматривать последовательности и многочлены над
некоторым полем
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
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
Вход:
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
Обоснование алгоритма Берлекэмпа–Месси содержится в [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
Доказательство. Следует из леммы 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
вии с леммой 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
Доказательство. В силу леммы 2 для любого конечного наперед за-
данного за конечное число шагов на выходе алгоритма получается поли-
ном ( ), для которого
. Его степень удовлетворяет точной ниж-
ней границе для степеней всех полиномов, вырабатывающих отрезок не
короче
l
(леммы 3 и 4).
l
G x
( )
u
l G l
≥
13
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
Некоторые менее существенные детали реализации были скорректи-
рованы по сравнению с изложенным в главе 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
3.2. Класс линейного регистра сдвига
Класс LFSR (Linear Feedback Shift Register — регистр сдвига с ли-
нейной обратной связью) предназначен для программного моделирования
ЛРС, который, как сказано выше, является всего лишь особым представле-
нием ЛРП. Его цель заключается в проверке корректности работы алго-
ритма: полученный на выходе алгоритма полином, дополненный последо-
вательностью элементов, выполняющей функцию, аналогичную начально-
му отрезку ЛРС, используется для построения экземпляра класса LFSR.
Далее появляется возможность получить произвольный отрезок последо-
вательности, моделируемой данным экземпляром класса LFSR, посредст-
вом последовательных вызовов экземплярной функции operator() и
убедиться таким образом, что полученный полином действительно являет-
ся характеристическим полиномом последовательности, начальный отре-
зок которой совпадает с начальным отрезком последовательности, задан-
ным алгоритму.
У данного класса имеется набор конструкторов, позволяющих кор-
ректно инициализировать два ключевых поля: кортежи множителей и со-
стояния. Кортеж множителей реализован шаблоном стандартной библио-
теки С++ vector<T>, параметризованным типом элемента поля Галуа
field_element; его размер фиксирован и не изменяется на протяжении
жизни объекта. Для кортежа состояния более приемлемым показалось ис-
пользование шаблона стандартной библиотеки С++ deque<T> — очередь
с двумя концами: на каждом такте работы LFSR (то есть после каждого
вызова функции operator()) вычисляется очередной элемент ЛРП, ко-
торый добавляется в конец кортежа состояния, а клиенту возвращается
элемент из начала этого кортежа. Таким образом размер очереди также ос-
тается неизменным.
16
Для класса LFSR предусмотрен оператор вывода в поток, обеспечи-
вающий возможность печати содержимого объекта данного класса.
3.3. Класс алгоритма
В классе алгоритма BMAlgorithm реализованы основные операции,
использованные при изложении алгоритма Берлекэмпа — Месси, как-то:
умножение полинома на последовательность и подсчет количества лиди-
рующих нулей в последовательности. После создания экземпляра класса
(конструктор принимает лишь ссылку на объект класса field, представ-
ляющего конечное поле, в котором производятся вычисления), его запуск
производится посредством вызова функции-члена operator(); в каче-
стве единственного аргумента указанной функции передается отрезок
ЛРП, для которого необходимо построить минимальный многочлен.
Описанный в главе 2 алгоритм непосредственно выполняется в теле
функции operator(). Шаги алгоритма отображаются на операторы язы-
ка программирования почти дословно.
В ходе алгоритма возникает необходимость многократно вычислять
мономы различных степеней (выражения вида
r
x
). С целью оптимизации
этого действия был создан класс Monoms, объявленный внутри класса
BMAlgorithm и являющийся тривиальной оберткой шаблона стандарт-
ной библиотеки С++ map<T>. Объект этого класса создается вместе с эк-
земпляром класса BMAlgorithm, он кэширует мономы, вычисленные на
предыдущих шагах работы алгоритма, и в ответ на запрос монома кон-
кретной степени (вызов функции operator[]) либо возвращает ссылку
на константу (такого уровня доступа оказывается достаточно, учитывая
что мономы используются при расчете арифметических выражений), вы-
численную ранее, либо вычисляет требуемое значение, добавляет в свою
коллекцию и также возвращает ссылку на константу.
17
Стоит заметить, что выразительность, достигнутая широким исполь-
зованием перегруженных арифметических операторов, как и обычно в
языке С++, не обходится даром — в ходе работы алгоритма создается
большое количество временных объектов. Возможным путем избежать на-
кладных расходов, связанных с этим, является использование техники Ex-
pression Templates, описанной, например, в [9]. Впрочем, это потребовало
бы существенного вмешательства в исходный код библиотеки, что выхо-
дит за рамки поставленных задач.
3.4. Тестирование
Хотя практически весь исходный код был в той или иной степени
покрыт набором тестов, основным объектом тестирования стал, конечно,
класс BMAlgorithm. Здесь же стоит отметить, что корректность библио-
течных средств также была установлена при помощи написания отдельно-
го ряда тестов. Для основного класса программы было предусмотрено два
основных тестовых случая:
• длинная псевдослучайная последовательность;
• все возможные последовательности заданной длины (учиты-
вая, что вычисления проводятся в конечных полях, количество
таких последовательностей конечно).
Для запуска проверки указанных тестовых случаев созданы две сво-
бодных
функции: totalSequencesTesting(), testLongSe-
quence(). Для реализации обеих проверок был использован класс Se-
quenceTester, описание которого приведено ниже.
Назначение класса SequenceTester — предоставить средства
проверки корректности работы алгоритма на одной заданной последова-
тельности. Проверка запускается вызовом метода testSequence(), в
качестве аргумента которому передается тестовая последовательность. Да-
лее логика работы такова:
18
4) построение с помощью имеющегося у каждого объекта-теста эк-
земпляра алгоритма минимального полинома для данной после-
довательности;
5) создание ЛРС (объекта LFSR) на основе полученного полинома;
6) проверка на равенство исходной последовательности и той, кото-
рую генерирует ЛРС.
Класс способен регистрировать два вида ошибок, что отражено в на-
личии объявленного внутри SequenceTester перечисления Failure-
Reason:
• п.1 завершается неудачей: зацикливание при работе алгоритма
(в процессе создания полинома выбрасывается исключение) —
константа ENDLESS_LOOP;
• п.3 завершается неудачей: получаемая на выходе ЛРС после-
довательность не совпадает с исходной — константа
NOT_MATCH.
При возникновении одной из двух указанных ситуаций, тестируемая
последовательность вместе с кодом ошибки заносится в коллекцию оши-
бок, хранимую объектом теста. Клиент класса может осведомиться о нали-
чии ошибок, вызвав метод hasFailures() и, если таковые имеются, вы-
вести их на консоль.
Если случай единственной, произвольно длинной (с учетом естест-
венных ограничений вычислительных ресурсов) псевдослучайной после-
довательности не представил особых препятствий в реализации (все све-
лось к последовательным вызовам стандартной библиотечной функции
rand() и передаче полученной последовательности объекту Se-
quenceTester), то генерация всех последовательностей заданной длины
является известной комбинаторной задачей, функционал которой был вы-
несен в отдельный класс — SequencesGenerator, при этом возникла
необходимость принять не слишком привлекательное в отношении дизай-
19
на тестового модуля решение. Поскольку работа генератора строится из
последовательных рекурсивных вызовов одной функции (sequences-
Generating()), то каждый раз возвращать клиенту очередную постро-
енную последовательность не удается. Возможны два варианта: предлагать
в качестве результата работы основного интерфейсного метода класса
(operator()) набор из всех последовательностей и затем, для каждого
элемента такого набора вызывать тестовый метод класса Se-
quenceTester — но это вызвало бы большие затраты памяти; либо вы-
зывать упомянутый тестовый метод прямо в процессе генерации, внутри
объекта класса SequencesGenerator. В итоге был реализован второй
вариант: объект
класса-генератора
владеет
экземпляром
Se-
quenceTester и вызывает его тестовый метод по мере формирования
каждой следующей последовательности. Следует отметить, что в совре-
менных языках программирования имеются средства получать промежу-
точные результаты работы рекурсивных функций без полной раскрутки
стека вызовов (например, инструмент generators в языке Python).
20
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
После получения слова из канала декодер вычисляет компоненты
синдрома
по формуле:
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
Последнее можно представить в матричном виде:
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
Вход:
( )
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
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/licenses/gpl-license.php.
9. Vandevoorde, D., N.M. Josuttis. C++ Templates. Boston: Addison-Wesley,
2003. ISBN 0201734842 (перевод: Вандевурд Д., Джосаттис Н. Шаблоны
С++: справочник разработчика. — М.: Издательский дом «Вильямс»,
2003).
10.Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с
англ. — М.: Мир, 1986.
25
Приложение
26
Приложение
Класс линейного регистра сдвига
LFSR.hpp
#ifndef LFSR_HPP
#define LFSR_HPP
#include "utilities.hpp"
#include "galois\schifra_galois_field.hpp"
#include "galois\schifra_galois_field_polynomial.hpp"
#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();
Приложение
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_element.hpp"
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::galois::field_element>(cout," ") );
cout << endl << "state:\t\t";
copy( lfsr.state.begin(), lfsr.state.end(),
ostream_iterator<schifra::galois::field_element>(cout," ") );
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 );
Приложение
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_iterator stIter = _st.begin();
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.hpp"
#include "galois\schifra_galois_field_element.hpp"
#include "galois\schifra_galois_field_polynomial.hpp"
#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 );
Приложение
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.hpp"
#include "galois\schifra_galois_field_polynomial.hpp"
#include <algorithm>
#include <iterator>
#include <fstream>
#include <vector>
#include <iostream>
#include <utility>
#include <limits>
#include <stdexcept>
#include <cassert>
#include <cstddef>
using schifra::galois::field_element;
using schifra::galois::field_polynomial;
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 ) {
Приложение
30
result[i] += poly[j] * seq[i + j];
}
}
return result;
}
size_t BMAlgorithm::countLeadingZeroes( GFElementsContainer seq ) {
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>::max() :
res;
return res;
}
field_polynomial const & BMAlgorithm::Monoms::operator[]( size_t degree ) {
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>::max();
//std::cout << "Sequence: ";
//std::copy( seq.begin(), seq.end(),
// std::ostream_iterator<field_element>(std::cout, " ") );
//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!
Приложение
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_element>( out, " " ) );
out << std::endl;
}
Приложение
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.hpp"
#include "galois\schifra_galois_field_polynomial.hpp"
#include "galois\schifra_galois_field_element.hpp"
#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);
Приложение
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>::max() );
//cout <<
return 0;
}
int testPolySeqProduct() {
GFElementsContainer seq1(4);
seq1[0] = gfes[0];
Приложение
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_element>( std::cout," ") );
//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 )
Приложение
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_iterator end = failures.end();
for ( FailuresContainer::const_iterator it = failures.begin(); it
!= end; ++it ) {
cout << std::setw(12) <<
( it->first == NOT_MATCH ) ? "Not match:" : "Endless
loop:";
copy( it->second.begin(), it->second.end(),
ostream_iterator<field_element>( cout, " " ) );
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!
}
}
}
Приложение
36
void testSequence() { // stub
copy( currentSequence.begin(), currentSequence.end(),
ostream_iterator<field_element>( cout, " " ) );
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_element>( out, " " ) );
out << endl;
}
Информация о работе Алгоритм Берлекэмпа - Месси