Форум программистов, компьютерный форум CyberForum.ru

Многочлены над GF(2^m) - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
06.11.2012, 02:35     Многочлены над GF(2^m) #1
Пишу кодер Рида-Соломона.
Дано следующее:
* http://www.cyberforum.ru/cgi-bin/latex.cgi?m - количество битов в одном символе (читай, элементов поля http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m));
* http://www.cyberforum.ru/cgi-bin/latex.cgi?n - длина кода (в символах);
* http://www.cyberforum.ru/cgi-bin/latex.cgi?k - длина сообщения (в символах);
* http://www.cyberforum.ru/cgi-bin/latex.cgi?g(x) - неприводимый многочлен степени http://www.cyberforum.ru/cgi-bin/latex.cgi?n-k над http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m)
* http://www.cyberforum.ru/cgi-bin/latex.cgi?\overline m - сообщение из 0 и 1 конечной длины.
* http://www.cyberforum.ru/cgi-bin/latex.cgi?u - сообщение, полученное из http://www.cyberforum.ru/cgi-bin/latex.cgi?\overline m путём выделения блоков длины http://www.cyberforum.ru/cgi-bin/latex.cgi?m;
* А также естественное отображение http://www.cyberforum.ru/cgi-bin/latex.cgi?A:GF^n(2^m)\to P_n(GF(2^m)); (\alpha _0\alpha _1...\alpha _{n-1})\mapsto \alpha _0+\alpha _1x+...+\alpha _{n-1}x^{n-1}
На выходе нужно получить РС-код:
* http://www.cyberforum.ru/cgi-bin/latex.cgi?v - код длины http://www.cyberforum.ru/cgi-bin/latex.cgi?n (в символах), по формуле: http://www.cyberforum.ru/cgi-bin/latex.cgi?v=A^{-1}(x^{n-k}(Au)(x)+(x^{n-k}(Au)(x) \mathrm{mod} g(x)))
http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m)=\{0,\alpha ^0, \alpha ^1,...,\alpha ^{2^m-2}\}, где http://www.cyberforum.ru/cgi-bin/latex.cgi?g(\alpha )=0.
По теории вроди бы всё, сейчас попробую описать прототип реализации.

Добавлено через 2 часа 17 минут
Посмотрите, пожалуйста!
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#ifndef RS_encoder.h
 
#include <vector>
 
const int GROUP_DEGREE = 0; // = m -- порядок группы GF(2^m)
const std::vector<int> PRIMITIVE_POLYNOMIAL (0); // примитивный полином в GF(2^m)
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    bool null; // индикатор того, что вектор нулевой
 
    void power_to_vector ();
    void vector_to_power ();
 
public:
    GF ();
    GF (int power); // используем power_to_vector
    GF (std::vector<int> vector); // используем vector_to_power
    ~GF ();
 
    GF operator+ (GF right_hand_side); // сложение
    GF operator* (GF right_hand_side); // умножение
 
    void show_alpha_vector (); //вывод на экран вектора
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#ifndef GF_polynom.h
 
#include "GF.h"
 
class GF_polynom
{
private:
    std::vector<GF> polynom; // вектор из коэфициентов полинома,
                             // которые принадлежат GF(2^m)
public:
    GF_polynom ();
    GF_polynom (std::vector<GF> coefficients);
    ~GF_polynom ();
 
    GF_polynom operator+ (GF_polynom right_hand_side); // сложение 
    GF_polynom operator* (GF_polynom right_hand_side); // умножение
    GF_polynom operator% (GF_polynom right_hand_side); // остаток от деления
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef RS_encoder.h
 
#include "GF_polynom.h"
#include <string>
 
const int CODE_LENGTH = 0; // длина кода
const int MESSAGE_LENGTH = 0; // длина сообщения
 
std::vector<int> str_to_int (std::string str_message); // строку в вектор
std::vector<GF> message_to_GF_message (std::vector<int> message); // вектор из 0 и 1 в 
                                                                  // вектор из элементов GF(2^m)
std::vector<GF> encode (std::vector<GF> GF_message, int n = CODE_LENGTH, int k = MESSAGE_LENGTH); // кодирование сообщения
 
#endif

Я пока не использовал ссылки и модификатор const. Завтра всё доделаю и буду приступать к написанию самих функций. Прокомментируйте, пожалуйста. Спасибо!!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2012, 02:35     Многочлены над GF(2^m)
Посмотрите здесь:

C++ Многочлены
C++ Многочлены
C++ списки-многочлены. сложение
C++ Операции над множествами
C++ класс, моделирующий многочлены n – го порядка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
06.11.2012, 12:19     Многочлены над GF(2^m) #2
include guard'ы написаны неверно - где define того, что проверяется в ifndef?
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
06.11.2012, 16:12  [ТС]     Многочлены над GF(2^m) #3
А я, когда пишу
C++
1
2
3
4
#ifndef prog.h
#define prog.h
/* code */
#endif
мне VS выдаёт ошибку, типа лишний раз объявлено. Или его не так писать надо?
Сейчас покушаю и напишу усовершенствованную версию=)
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
06.11.2012, 17:01     Многочлены над GF(2^m) #4
в VS проще писать #pragma once
эта штука нестандартная, но много где работает
Меня тут - prog.h - точка смущает)
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
06.11.2012, 22:22  [ТС]     Многочлены над GF(2^m) #5
Вот (почти) финальный вариант. Гляньте одним глазком, всё ли верно? Я старался писать как можно более разборчиво
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#ifndef GF_h
#define GF_h
 
#include <vector>
 
const int GROUP_DEGREE = 0; // = m -- порядок группы GF(2^m)
const std::vector<int> PRIMITIVE_POLYNOMIAL (0); // примитивный полином в GF(2^m)
 
const std::vector<GF> init_GF_table (); // возвращает вектор из всех элементов GF(2^m)
const std::vector<GF> GF_table = init_GF_table ();
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    bool null; // индикатор того, что вектор нулевой
 
    void power_to_vector (); // используем 
    void vector_to_power (); // GF_table
 
public:
    GF ();
    GF (const int& power); // используем power_to_vector
    GF (const std::vector<int>& vector); // используем vector_to_power
    ~GF ();
 
    GF operator+ (const GF& right_hand_side) const; // сложение
    GF operator* (const GF& right_hand_side) const; // умножение
 
    std::vector<int> return_alpha_vector () const; // возврат элемента в виде вектора
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef GF_polynom_h
#define GF_polynom_h
 
#include "GF.h"
 
class GF_polynom
{
private:
    std::vector<GF> polynom; // вектор из коэфициентов полинома,
                             // которые принадлежат GF(2^m)
public:
    GF_polynom ();
    GF_polynom (const std::vector<GF>& coefficients);
    ~GF_polynom ();
 
    GF_polynom operator+ (const GF_polynom& right_hand_side) const; // сложение 
    GF_polynom operator* (const GF_polynom& right_hand_side) const; // умножение
    GF_polynom operator% (const GF_polynom& right_hand_side) const; // остаток от деления
 
    std::vector<GF> return_coefficients () const; // возвращает коэффициенты многочлена
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#ifndef RS_encoder_h
#define RS_encoder_h
 
#include "GF_polynom.h"
#include <string>
 
const int CODE_LENGTH = 0; // длина кода
const int MAX_ERRORS = 0; // количество исправляемых ошибок
const int MESSAGE_LENGTH = 0; // длина сообщения
 
std::vector<int> str_to_int (const std::string& str_message); // строку в вектор
std::vector<GF> message_to_GF_message (const std::vector<int>& message); // вектор из 0 и 1 в 
                                                                         // вектор из элементов GF(2^m)
std::vector<GF> encode (const std::vector<GF>& GF_message, const int& n = CODE_LENGTH, 
                        const int& k = MESSAGE_LENGTH); // кодирование сообщения
std::vector<int> GF_code_to_vector (const std::vector<GF>& code);
 
#endif


Добавлено через 4 часа 36 минут
Написал такое, выдаёт ошибку "vector out of range". Подскажите, где оно вылзит. Спасибо!
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef GF_table_h
#define GF_table_h
 
#include <vector>
 
extern const int GROUP_DEGREE; 
 
const std::vector<int> init_primitive_polynomial (const int& degree); 
                        
 
struct GF_table
{
    int power;
    std::vector<int> vector;
};
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial);
 
extern const std::vector<GF_table> table;
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "GF_table.h"
 
const int GROUP_DEGREE = 3;
 
const std::vector<int> init_primitive_polynomial (const int& degree = GROUP_DEGREE)
{
    std::vector<int> polynom;
    polynom.reserve (degree);
 
    switch (degree)
    {
    case 2:
        for (int i = 0; i < 3; ++i)
            polynom.push_back (1);
        return polynom;
    case 3:
        polynom.push_back (1);
        polynom.push_back (1);
        polynom.push_back (0);
        polynom.push_back (1);
        return polynom;
    case 4:
        polynom.push_back (1);
        polynom.push_back (1);
        polynom.push_back (0);
        polynom.push_back (0);
        polynom.push_back (1);
        return polynom;
    /* case 5, 6,...*/
    }
}
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial = init_primitive_polynomial ())
{
    std::vector<GF_table> table;
    table.reserve (int (std::pow (2.0, GROUP_DEGREE) - 1));
 
    std::vector<int> temp_vec (GROUP_DEGREE, 0);
    temp_vec.reserve (GROUP_DEGREE + 1);
 
    temp_vec.at(0) = 1;
 
    table.at(0).power = 0;
    table.at(0).vector = temp_vec; 
 
    for (int i = 1; i < int (std::pow (2.0, GROUP_DEGREE) - 1); ++i)
    {
        table.at(i).power = i;
 
        temp_vec = table.at(i - 1).vector;
        temp_vec.insert (temp_vec.begin (), 0);
        temp_vec.pop_back ();
 
        table.at(i).vector = temp_vec;
 
        if (table.at(i).vector.at(GROUP_DEGREE - 1) = 1)
            for (int j = 0; j < GROUP_DEGREE; ++j)
                table.at(i).vector.at(j) = (table.at(i).vector.at(j) + primitive_polynomial.at(j)) % 2;
    }
 
    return table;
}
 
const std::vector<GF_table> table (init_GF_table ());
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.11.2012, 23:04     Многочлены над GF(2^m) #6
Для table вижу reserve, но не вижу увеличения размера, собсно получается вектор с нулевым размером и затем идет попытка получить его первый элемент.
И еще, глаз режет:
C++
1
std::pow (2.0, GROUP_DEGREE)
Используйте
C++
1
1 << GROUP_DEGREE
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
07.11.2012, 00:11     Многочлены над GF(2^m) #7
C++
1
2
std::vector<GF> encode (const std::vector<GF>& GF_message, const int& n = CODE_LENGTH, 
                        const int& k = MESSAGE_LENGTH);
стандартные типы, такие как int, можно передавать по значению, а не по ссылке. Для них в случае ссылки никакого ускорения не будет
И еще, я вижу в классах деструктор, но не вижу конструктора копирования и оператора присваивания
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
07.11.2012, 02:55  [ТС]     Многочлены над GF(2^m) #8
Пока написал 2 штуки, но они не работают: выдаёт какую-то непонятную ошибку

Не по теме:

GF.obj : error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall GF::~GF(void)" (??1GF@@QAE@XZ) в функции "public: class GF __thiscall GF::operator+(class GF const &)const " (??HGF@@QBE?AV0@ABV0@@Z)


Вот, что я пока накатал...
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_table_h
#define GF_table_h
 
#include <vector>
 
extern const int GROUP_DEGREE; 
 
const std::vector<int> init_primitive_polynomial (const int& degree); 
 
struct GF_table
{
    GF_table ();
    GF_table (const GF_table& GF_element);
    ~GF_table ();
 
    GF_table& operator= (const GF_table& right_hand_side);
 
    int power;
    std::vector<int> vector;    
};
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial);
 
extern const std::vector<int> null_vector;
extern const std::vector<GF_table> table;
 
#endif
 
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_table.h"
 
const int GROUP_DEGREE = 3;
 
const std::vector<int> init_primitive_polynomial (const int degree = GROUP_DEGREE)
{
    std::vector<int> polynom (degree + 1, 0);
    polynom.resize (degree + 1);
 
    switch (degree)
    {
    case 2:
        for (int i = 0; i < 3; ++i)
            polynom.at(i) = 1;
        return polynom;
 
    case 3:
        for (int i = 0; i < 4; ++i)
            polynom.at(i) = 1;
        polynom.at(2) = 0;
        return polynom;
 
    case 4:
        for (int i = 0; i < 5; ++i)
            polynom.at(i) = 1;
        polynom.at(2) = 0;
        polynom.at(3) = 0;
        return polynom;
 
    /* case 5, 6,...*/
    }
}
 
GF_table::GF_table ()
{
    power = 0;
    vector.resize (GROUP_DEGREE);
}
 
GF_table::GF_table (const GF_table& GF_element)
{
    power = GF_element.power;
    vector = GF_element.vector;
}
 
GF_table& GF_table::operator= (const GF_table& right_hand_side)
{
    power = right_hand_side.power;
    vector = right_hand_side.vector;
 
    return *this;
}
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial = init_primitive_polynomial ())
{
    std::vector<GF_table> table;
    table.resize ((1 << GROUP_DEGREE) - 1);
 
    std::vector<int> temp_vec (GROUP_DEGREE, 0);
    temp_vec.resize (GROUP_DEGREE);
 
    temp_vec.at(0) = 1;
 
    table.at(0).power = 0;
    table.at(0).vector = temp_vec; 
    
 
    for (int i = 1; i < (1 << GROUP_DEGREE - 1); ++i)
    {
        table.at(i).power = i;
 
        temp_vec = table.at(i - 1).vector;
        temp_vec.insert (temp_vec.begin (), 0);
 
        if (*(table.at(i).vector.end ()) = 1)
            for (int j = 0; j < GROUP_DEGREE; ++j)
                table.at(i).vector.at(j) = (table.at(i).vector.at(j) + primitive_polynomial.at(j)) % 2;
        
        temp_vec.pop_back ();
 
        table.at(i).vector = temp_vec;      
    }
 
    return table;
}
 
const std::vector<int> null_vector (GROUP_DEGREE, 0);
 
const std::vector<GF_table> table (init_GF_table ());

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_h
#define GF_h
 
#include "GF_table.h"
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    int null; // индикатор того, что вектор нулевой
 
    int ifnull ();
    void power_to_vector (); // используем 
    void vector_to_power (); // GF_table
 
public:
    GF ();
    GF (const GF& GF_element);
    GF (const std::vector<int> vector);
    ~GF ();
    
    GF& operator= (const GF& right_hand_side);
 
    GF operator+ (const GF& right_hand_side) const; // сложение
    GF operator* (const GF& right_hand_side) const; // умножение
 
    std::vector<int> return_alpha_vector () const; // возврат элемента в виде вектора
};
 
#endif
 
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF.h"
 
GF::GF ()
{
    alpha_power = 0;
    alpha_vector.resize (GROUP_DEGREE);
    null = 1;
}
 
GF::GF (const GF& GF_element)
{
    alpha_power = GF_element.alpha_power;
    alpha_vector = GF_element.alpha_vector;
    null = GF_element.null;
}
 
GF::GF (const std::vector<int> vector)
{
    alpha_vector = vector;
    vector_to_power ();
}
 
GF& GF::operator= (const GF& right_hand_side)
{
    alpha_power = right_hand_side.alpha_power;
    alpha_vector = right_hand_side.alpha_vector;
    null = right_hand_side.null;
 
    return *this;
}
 
void GF::power_to_vector ()
{
    alpha_vector = table.at(alpha_power).vector;
}
 
void GF::vector_to_power ()
{
    if (alpha_vector != null_vector)
    {
        int i = 0;
        while (table.at(i).vector != alpha_vector)
            ++i;
 
        alpha_power = i;
    }
    else
        null = 1;   
}
 
GF GF::operator+ (const GF& right_hand_side) const
{
    if (null == 1) 
        return right_hand_side;
    if (right_hand_side.null == 1)
        return *this;
 
    GF sum;
 
    for (int i = 0; i < GROUP_DEGREE; ++i)
        sum.alpha_vector.at(i) = (alpha_vector.at (i) + right_hand_side.alpha_vector.at (i)) % 2;
    
    if (sum.alpha_vector == null_vector)
    {
        sum.null = 1;
        return sum;
    }
 
    sum.vector_to_power ();
 
    return sum;
}
 
GF GF::operator* (const GF& right_hand_side) const
{
    if (null == 1)
        return *this;
    if (right_hand_side.null == 1)
        return right_hand_side;
 
    GF prod;
 
    prod.alpha_power = (alpha_power + right_hand_side.alpha_power) % ((1 << GROUP_DEGREE) - 1);
    
    prod.power_to_vector ();
    
    return prod;
}
 
std::vector<int> GF::return_alpha_vector () const
{
    return alpha_vector;
}

Всем большое спасибо за помощь! Я уже не дописывал комментарии в последнем коде, надеюсь, там и так всё понятно (или ничего не понятно ).
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
07.11.2012, 04:31     Многочлены над GF(2^m) #9
всё проще чем кажется. деструктор ~GF_table вообще отсутствует. Т.е. Объявлен и Не реализован.
Вот например строки 77-81 - это конструктор. Почему деструктор не написали примерно после конструктора?
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
08.11.2012, 02:44  [ТС]     Многочлены над GF(2^m) #10
Т.е. Объявлен и Не реализован.
Я думал, что если его объявить и не реализовать, то он реализуется сам по себе. А что в нём написать? Или лучше его пустым оставить?
Поправил первые два файлика, вроди всё работает. Гляньте ещё разок, на всякий.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_table_h
#define GF_table_h
 
#include <vector>
 
extern const int GROUP_DEGREE; 
 
const std::vector<int> init_primitive_polynomial (const int degree); 
 
struct GF_table
{
    GF_table ();
    GF_table (const GF_table& GF_element);
    ~GF_table ();
 
    GF_table& operator= (const GF_table& right_hand_side);
 
    int power;
    std::vector<int> vector;    
};
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial);
 
extern const std::vector<GF_table> table;
 
extern const std::vector<int> null_vector;
extern const std::vector<int> unit_vector;
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_table.h"
 
const int GROUP_DEGREE = 3;
 
const std::vector<int> init_primitive_polynomial (const int degree = GROUP_DEGREE)
{
    std::vector<int> polynom (degree, 0);
    polynom.resize (degree);
 
    switch (degree)
    {
    case 2:
        for (int i = 0; i < 2; ++i)
            polynom.at(i) = 1;
 
        return polynom;
 
    case 3:
        for (int i = 0; i < 3; ++i)
            polynom.at(i) = 1;
 
        polynom.at(2) = 0;
        return polynom;
 
    case 4:
        for (int i = 0; i < 4; ++i)
            polynom.at(i) = 1;
 
        polynom.at(2) = 0;
        polynom.at(3) = 0;
        return polynom;
 
    /* case 5, 6,...*/
    }
}
 
GF_table::GF_table ()
{
    power = 0;
    vector.resize (GROUP_DEGREE);
}
 
GF_table::GF_table (const GF_table& GF_element)
{
    power = GF_element.power;
    vector = GF_element.vector;
}
 
GF_table::~GF_table ()
{
 
}
 
GF_table& GF_table::operator= (const GF_table& right_hand_side)
{
    power = right_hand_side.power;
    vector = right_hand_side.vector;
 
    return *this;
}
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial = init_primitive_polynomial ())
{
    std::vector<GF_table> table;
    table.resize ((1 << GROUP_DEGREE) - 1);
 
    std::vector<int> temp_vec (GROUP_DEGREE, 0);
 
    temp_vec.at(0) = 1;
    table.at(0).vector = temp_vec;
 
    for (int i = 1; i < (1 << GROUP_DEGREE) - 1; ++i)
    {
        table.at(i).vector.at(0) = 0;
 
        for (int j = 1; j < GROUP_DEGREE; ++j)
            table.at(i).vector.at(j) = table.at(i - 1).vector.at(j - 1);
 
        if (table.at(i - 1).vector.at(GROUP_DEGREE - 1) == 1)
            for (int j = 0; j < GROUP_DEGREE; ++j)
                table.at(i).vector.at(j) = (table.at(i).vector.at(j) + primitive_polynomial.at(j)) % 2;
    }
 
    return table;
}
 
const std::vector<GF_table> table (init_GF_table ());
 
const std::vector<int> null_vector (GROUP_DEGREE, 0);
const std::vector<int> unit_vector (table.at(0).vector);

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_h
#define GF_h
 
#include "GF_table.h"
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    int null; // индикатор того, что вектор нулевой
 
    void power_to_vector (); // используем 
    void vector_to_power (); // GF_table
 
public:
    GF ();
    GF (const GF& GF_element);
    GF (const int power);
    GF (const std::vector<int> vector);
    ~GF ();
    
    GF& operator= (const GF& right_hand_side);
 
    GF operator+ (const GF& right_hand_side) const; // сложение
    GF operator* (const GF& right_hand_side) const; // умножение
 
    int return_power () const;
    std::vector<int> return_alpha_vector () const; // возврат элемента в виде вектора
};
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF.h"
 
GF::GF ()
{
    alpha_power = 0;
    alpha_vector.resize (GROUP_DEGREE);
    null = 1;
}
 
GF::GF (const GF& GF_element)
{
    alpha_power = GF_element.alpha_power;
    alpha_vector = GF_element.alpha_vector;
    null = GF_element.null;
}
 
GF::GF (const int power)
{
    alpha_power = power;
    power_to_vector ();
}
 
GF::GF (const std::vector<int> vector)
{
    alpha_vector = vector;
    vector_to_power ();
}
 
GF::~GF ()
{
 
}
 
GF& GF::operator= (const GF& right_hand_side)
{
    alpha_power = right_hand_side.alpha_power;
    alpha_vector = right_hand_side.alpha_vector;
    null = right_hand_side.null;
 
    return *this;
}
 
void GF::power_to_vector ()
{
    alpha_vector = table.at(alpha_power).vector;
}
 
void GF::vector_to_power ()
{
    if (alpha_vector != null_vector)
    {
        int i = 0;
        while (table.at(i).vector != alpha_vector)
            ++i;
 
        alpha_power = i;
        null = 0;
    }
    else
        null = 1;   
}
 
GF GF::operator+ (const GF& right_hand_side) const
{
    if (null == 1) 
        return right_hand_side;
    if (right_hand_side.null == 1)
        return *this;
 
    GF sum;
 
    for (int i = 0; i < GROUP_DEGREE; ++i)
        sum.alpha_vector.at(i) = (alpha_vector.at (i) + right_hand_side.alpha_vector.at (i)) % 2;
    
    if (sum.alpha_vector == null_vector)
    {
        sum.null = 1;
        return sum;
    }
 
    sum.vector_to_power ();
 
    return sum;
}
 
GF GF::operator* (const GF& right_hand_side) const
{
    if (null == 1)
        return *this;
    if (right_hand_side.null == 1)
        return right_hand_side;
 
    GF prod;
 
    prod.alpha_power = (alpha_power + right_hand_side.alpha_power) % ((1 << GROUP_DEGREE) - 1);
    
    prod.power_to_vector ();
    
    return prod;
}
 
int GF::return_power () const
{
    return alpha_power;
}
 
std::vector<int> GF::return_alpha_vector () const
{
    return alpha_vector;
}

Сейчас дописываю третий файлик. Подскажите, как лучше реализовать деление с остатком? И пустой конструктор по умолчанию сгодится?
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_polynom_h
#define GF_polynom_h
 
#include "GF.h"
 
class GF_polynom
{
private:
    std::vector<GF> polynom; // вектор из коэфициентов полинома,
                             // которые принадлежат GF(2^m)
public:
    GF_polynom ();
    GF_polynom (const GF_polynom& GF_polynom_element);
    GF_polynom (const std::vector<GF>& coefficients);
    ~GF_polynom ();
 
    GF_polynom& operator= (const GF_polynom& right_hand_side);
 
    GF_polynom operator+ (const GF_polynom& right_hand_side) const; // сложение 
    GF_polynom operator* (const GF_polynom& right_hand_side) const; // умножение
    GF_polynom operator% (const GF_polynom& right_hand_side) const; // остаток от деления
 
    std::vector<GF> return_coefficients () const; // возвращает коэффициенты многочлена
};
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_polynom.h"
 
GF_polynom::GF_polynom ()
{
 
}
 
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element)
{
    polynom.resize (GF_polynom_element.polynom.size());
    polynom = GF_polynom_element.polynom;
}
 
GF_polynom::GF_polynom (const std::vector<GF>& coefficients)
{
    polynom.resize (coefficients.size ());
    polynom = coefficients;
}
 
GF_polynom::~GF_polynom ()
{
 
}
 
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom.resize (right_hand_side.polynom.size());
    polynom = right_hand_side.polynom;
 
    return *this;
}
 
GF_polynom GF_polynom::operator+ (const GF_polynom& right_hand_side) const
{
    GF_polynom sum;
    sum.polynom.resize (std::max(polynom.size(), right_hand_side.polynom.size()));
 
    for (int i = 0; i < std::min(polynom.size(), right_hand_side.polynom.size()); ++i)
        sum.polynom.push_back (polynom.at(i) + right_hand_side.polynom.at(i));
 
    if (polynom.size() < right_hand_side.polynom.size())
        for (int i = polynom.size(); i < right_hand_side.polynom.size(); ++i)
            sum.polynom.push_back (right_hand_side.polynom.at(i));
    else
        for (int i = right_hand_side.polynom.size(); i < polynom.size(); ++i)
            sum.polynom.push_back (polynom.at(i));
    
    return sum;
}
 
GF_polynom GF_polynom::operator* (const GF_polynom& right_hand_side) const
{
    GF_polynom prod;
    prod.polynom.resize (polynom.size() + right_hand_side.polynom.size());
 
    for (int i = 0; i < prod.polynom.size(); ++i)
    {
        GF sum (null_vector);
 
        for (int j = 0; j < i + 1; ++j)
            if ((j < polynom.size()) && (i - j < right_hand_side.polynom.size()))
                sum = sum + (polynom.at(j) * right_hand_side.polynom.at(i - j));
        
        prod.polynom.push_back (sum);
    }
 
    return prod;
}
 
GF_polynom GF_polynom::operator% (const GF_polynom& right_hand_side) const
{
 
}
 
std::vector<GF> GF_polynom::return_coefficients () const
{
    return polynom;
}
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
08.11.2012, 13:38     Многочлены над GF(2^m) #11
Все конструкции такого вида
C++
1
2
3
4
5
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element)
{
    polynom.resize (GF_polynom_element.polynom.size());
    polynom = GF_polynom_element.polynom;
}
лучше заменить на
C++
1
2
3
4
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element):
polynom(GF_polynom_element.polynom)
{
}
Добавлено через 17 минут
в 71 строке вы создаете вектор определенной длины, заполненный нулями. А затем вы эти нули нигде не используете - только пушаете новые значения. Так и задумано?
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
08.11.2012, 17:08  [ТС]     Многочлены над GF(2^m) #12
ок, заменю. А что за 71 строка? Эта?
C++
1
sum.polynom.resize (std::max(polynom.size(), right_hand_side.polynom.size()));
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
08.11.2012, 17:21     Многочлены над GF(2^m) #13
vlad_light, да, она. Я просто забыл дописать, из какого она листинга
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
08.11.2012, 17:23  [ТС]     Многочлены над GF(2^m) #14
т.е. там нужно вместо push_back везде написать at(i) верно?
Либо перед циклом написать clear.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
08.11.2012, 17:32     Многочлены над GF(2^m) #15
Лучше заменить resize на reserve. пушбеки оставить
Кстати вместо at(i) можно писать [i]
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
08.11.2012, 17:35  [ТС]     Многочлены над GF(2^m) #16
Спасибо! А с делением Вы мне можете помочь?
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
08.11.2012, 17:38     Многочлены над GF(2^m) #17
С алгоритмом - вряд ли. Но если вы сможете в доступной форме изложить этот алгоритм и сказать "я вот сделал, но почему-то считает не так", то помогу, конечно
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
09.11.2012, 02:15  [ТС]     Многочлены над GF(2^m) #18
Отлично! Тогда я сейчас попробую реализовать столбиком (даже скорее не сейчас, а ближе к вечеру, поскольку сейчас есть ещё дела) и выложу здесь, а Вы посмотрите. Спасибо!
И ещё вопрос: а разве Вам проще разбираться в моём коде, чем написать собственный? Если да, то как научиться в нём разбираться, поскольку я в чужом коде вообще ничего понять не могу

Добавлено через 4 часа 35 минут
Алгоритм деления столбиком.
Имеем два многочлена http://www.cyberforum.ru/cgi-bin/latex.cgi?a(x)\in P_n и http://www.cyberforum.ru/cgi-bin/latex.cgi?div(x)\in P_m с коэффициентами из http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^k). Не нарушая общности, положим http://www.cyberforum.ru/cgi-bin/latex.cgi?n>m. Представим каждый многочлен в виде вектора из его коэффициентов
http://www.cyberforum.ru/cgi-bin/latex.cgi?a(x)\leftrightarrow a = (a_0, a_1,...,a_n)\in (GF(2^k))^{n+1};div(x)\leftrightarrow b = (div_0, div_1,...,div_m)\in (GF(2^k))^{m+1}.
Создаём две дополнительных переменных:
http://www.cyberforum.ru/cgi-bin/latex.cgi?rem(x)\in P_v, v = n, n-1, n-2,...; rem(x)\leftrightarrow rem = (rem_1, rem_2,...,rem_v),
которая будет отображать текущий остаток от деления http://www.cyberforum.ru/cgi-bin/latex.cgi?a(x) на http://www.cyberforum.ru/cgi-bin/latex.cgi?div(x), и http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x)\in P_{v-m}, который имеет вид
http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x)=\frac{rem_v}{div_m}x^{v-m}\leftrightarrow mult = (0,0,...,0,\frac{rem_v}{div_m}).
Теперь на первом шаге умножаем http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x) на http://www.cyberforum.ru/cgi-bin/latex.cgi?div(x) и прибавляем к http://www.cyberforum.ru/cgi-bin/latex.cgi?rem, получаем
http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x)\times div(x)\leftrightarrow (0,0,...,0,\frac{rem_v}{div_m}div_0,\frac{rem_v}{div_m}div_1,...,\frac{rem_v}{div_m}div_m).
Поскольку последний коэф. равен http://www.cyberforum.ru/cgi-bin/latex.cgi?rem_v (такой же,как и у http://www.cyberforum.ru/cgi-bin/latex.cgi?rem), то при суммировании (что равно вычитанию) он сократиться. После этого мы убираем последний элемент из http://www.cyberforum.ru/cgi-bin/latex.cgi?rem(x), поскольку он равен нулю, и из http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x), поскольку он нам больше не нужен. проделываем операцию до тех пор, пока степень текущего остатка не станет меньше степени делителя.

Не по теме:

Хотел написать красиво, но с таким редактором ТеХ'а оно выглядит ужасно. Надеюсь, хоть что-то понятно...


Вот, что я пока написал, но не проверял. Гляньте, пожалуйста, уверен, там можно его переписать в лучшем виде.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_polynom.h"
 
GF_polynom::GF_polynom ()
{
 
}
 
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element):
polynom (GF_polynom_element.polynom)
{
 
}
 
GF_polynom::GF_polynom (const std::vector<GF>& coefficients):
polynom (coefficients)
{
 
}
 
GF_polynom::~GF_polynom ()
{
 
}
 
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom.resize (right_hand_side.polynom.size());
    polynom = right_hand_side.polynom;
 
    return *this;
}
 
GF_polynom GF_polynom::operator+ (const GF_polynom& right_hand_side) const
{
    GF_polynom sum;
    sum.polynom.reserve (std::max(polynom.size(), right_hand_side.polynom.size()));
 
    for (int i = 0; i < std::min(polynom.size(), right_hand_side.polynom.size()); ++i)
        sum.polynom.push_back (polynom.at(i) + right_hand_side.polynom.at(i));
 
    if (polynom.size() < right_hand_side.polynom.size())
        for (int i = polynom.size(); i < right_hand_side.polynom.size(); ++i)
            sum.polynom.push_back (right_hand_side.polynom.at(i));
    else
        for (int i = right_hand_side.polynom.size(); i < polynom.size(); ++i)
            sum.polynom.push_back (polynom.at(i));
    
    return sum;
}
 
GF_polynom GF_polynom::operator* (const GF_polynom& right_hand_side) const
{
    GF_polynom prod;
    prod.polynom.resize (polynom.size() + right_hand_side.polynom.size());
 
    for (int i = 0; i < prod.polynom.size(); ++i)
    {
        GF sum (null_vector);
 
        for (int j = 0; j < i + 1; ++j)
            if ((j < polynom.size()) && (i - j < right_hand_side.polynom.size()))
                sum = sum + (polynom.at(j) * right_hand_side.polynom.at(i - j));
        
        prod.polynom.push_back (sum);
    }
 
    return prod;
}
 
GF_polynom GF_polynom::operator% (const GF_polynom& divisor) const
{
    GF_polynom reminder (*this); // остаток
    GF_polynom multiplier; // множитель, на который умножаем делитель
                           // (имеет вид a * x^n )
    multiplier.polynom.resize (reminder.polynom.size() - divisor.polynom.size() + 1);
 
    for (int i = 0; i < reminder.polynom.size() - divisor.polynom.size(); ++i) 
        multiplier.polynom.at(i) = null_vector; // заполняем нулями все, кроме последнего   
    
    while (reminder.polynom.size() > divisor.polynom.size()) // пока степень остачи больше степени делителя
    {
        multiplier.polynom.at(reminder.polynom.size() - divisor.polynom.size()) = //коэффициент при x^(n-m)
            reminder.polynom.at(reminder.polynom.size() - 1) /                    // n - степень текущего остатка
            divisor.polynom.at(divisor.polynom.size() - 1);                       // m - степень делителя
 
        reminder = reminder + (divisor * multiplier); // обнуляем коэффициент
                                                      // при старшей степени
        multiplier.polynom.pop_back(); // убираем старший коэф., остаются одни нули
        reminder.polynom.pop_back(); // убираем старштй коэф., поскольку он нулевой
    }
 
    return reminder; // возвращаем остаток
}
 
std::vector<GF> GF_polynom::return_coefficients () const
{
    return polynom;
}


Добавлено через 3 часа 59 минут
Урааа!!! Наконец-то дописал весь код, осталось его исправить и протестировать. Вообщем, выкладываю "пре-альфа" версию
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_table_h
#define GF_table_h
 
#include <vector>
 
extern const int GROUP_DEGREE; 
 
const std::vector<int> init_primitive_polynomial (const int degree); 
 
struct GF_table
{
    GF_table ();
    GF_table (const GF_table& GF_element);
    ~GF_table ();
 
    GF_table& operator= (const GF_table& right_hand_side);
 
    int power;
    std::vector<int> vector;    
};
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial);
 
extern const std::vector<GF_table> table;
 
extern const std::vector<int> null_vector;
extern const std::vector<int> unit_vector;
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_table.h"
 
const int GROUP_DEGREE = 3;
 
const std::vector<int> init_primitive_polynomial (const int degree = GROUP_DEGREE)
{
    std::vector<int> polynom (degree, 0);
    polynom.resize (degree);
 
    switch (degree)
    {
    case 2:
        for (int i = 0; i < 2; ++i)
            polynom.at(i) = 1;
 
        return polynom;
 
    case 3:
        for (int i = 0; i < 3; ++i)
            polynom.at(i) = 1;
 
        polynom.at(2) = 0;
        return polynom;
 
    case 4:
        for (int i = 0; i < 4; ++i)
            polynom.at(i) = 1;
 
        polynom.at(2) = 0;
        polynom.at(3) = 0;
        return polynom;
 
    /* case 5, 6,...*/
    }
}
 
GF_table::GF_table ()
{
    power = 0;
    vector.resize (GROUP_DEGREE);
}
 
GF_table::GF_table (const GF_table& GF_element)
{
    power = GF_element.power;
    vector = GF_element.vector;
}
 
GF_table::~GF_table ()
{
 
}
 
GF_table& GF_table::operator= (const GF_table& right_hand_side)
{
    power = right_hand_side.power;
    vector = right_hand_side.vector;
 
    return *this;
}
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial = init_primitive_polynomial ())
{
    std::vector<GF_table> table;
    table.resize ((1 << GROUP_DEGREE) - 1);
 
    std::vector<int> temp_vec (GROUP_DEGREE, 0);
 
    temp_vec.at(0) = 1;
    table.at(0).vector = temp_vec;
 
    for (int i = 1; i < (1 << GROUP_DEGREE) - 1; ++i)
    {
        table.at(i).vector.at(0) = 0;
 
        for (int j = 1; j < GROUP_DEGREE; ++j)
            table.at(i).vector.at(j) = table.at(i - 1).vector.at(j - 1);
 
        if (table.at(i - 1).vector.at(GROUP_DEGREE - 1) == 1)
            for (int j = 0; j < GROUP_DEGREE; ++j)
                table.at(i).vector.at(j) = (table.at(i).vector.at(j) + primitive_polynomial.at(j)) % 2;
    }
 
    return table;
}
 
const std::vector<GF_table> table (init_GF_table ());
 
const std::vector<int> null_vector (GROUP_DEGREE, 0);
const std::vector<int> unit_vector (table.at(0).vector);

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_h
#define GF_h
 
#include "GF_table.h"
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    int null; // индикатор того, что вектор нулевой
 
    void power_to_vector (); // используем 
    void vector_to_power (); // GF_table
 
public:
    GF ();
    GF (const GF& GF_element);
    GF (const int power);
    GF (const std::vector<int> vector);
    ~GF ();
    
    GF& operator= (const GF& right_hand_side);
 
    GF operator+ (const GF& right_hand_side) const; // сложение
    GF operator* (const GF& right_hand_side) const; // умножение
    GF operator/ (const GF& right_hand_side) const;
 
    int return_power () const;
    std::vector<int> return_alpha_vector () const; // возврат элемента в виде вектора
};
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF.h"
 
GF::GF ()
{
    alpha_power = 0;
    alpha_vector.resize (GROUP_DEGREE);
    null = 1;
}
 
GF::GF (const GF& GF_element)
{
    alpha_power = GF_element.alpha_power;
    alpha_vector = GF_element.alpha_vector;
    null = GF_element.null;
}
 
GF::GF (const int power)
{
    alpha_power = power;
    power_to_vector ();
    null = 0;
}
 
GF::GF (const std::vector<int> vector)
{
    alpha_vector = vector;
    vector_to_power ();
}
 
GF::~GF ()
{
 
}
 
GF& GF::operator= (const GF& right_hand_side)
{
    alpha_power = right_hand_side.alpha_power;
    alpha_vector = right_hand_side.alpha_vector;
    null = right_hand_side.null;
 
    return *this;
}
 
void GF::power_to_vector ()
{
    alpha_vector = table.at(alpha_power).vector;
}
 
void GF::vector_to_power ()
{
    if (alpha_vector != null_vector)
    {
        int i = 0;
        while (table.at(i).vector != alpha_vector)
            ++i;
 
        alpha_power = i;
        null = 0;
    }
    else
        null = 1;   
}
 
GF GF::operator+ (const GF& right_hand_side) const
{
    if (null == 1) 
        return right_hand_side;
    if (right_hand_side.null == 1)
        return *this;
 
    GF sum;
 
    for (int i = 0; i < GROUP_DEGREE; ++i)
        sum.alpha_vector.at(i) = (alpha_vector.at (i) + right_hand_side.alpha_vector.at (i)) % 2;
    
    if (sum.alpha_vector == null_vector)
    {
        sum.null = 1;
        return sum;
    }
 
    sum.vector_to_power ();
 
    return sum;
}
 
GF GF::operator* (const GF& right_hand_side) const
{
    if (null == 1)
        return *this;
    if (right_hand_side.null == 1)
        return right_hand_side;
 
    GF prod;
 
    prod.alpha_power = (alpha_power + right_hand_side.alpha_power) % ((1 << GROUP_DEGREE) - 1);
    
    prod.power_to_vector ();
    
    return prod;
}
 
GF GF::operator/ (const GF& right_hand_side) const
{   
    if (alpha_power - right_hand_side.alpha_power < 0)
    {
        GF div ((alpha_power - right_hand_side.alpha_power) % 
            ((1 << GROUP_DEGREE) - 1) + ((1 << GROUP_DEGREE) - 1));
        return div;
    }
    else
    {
        GF div ((alpha_power - right_hand_side.alpha_power) % ((1 << GROUP_DEGREE) - 1));
        return div;
    }
}
 
int GF::return_power () const
{
    return alpha_power;
}
 
std::vector<int> GF::return_alpha_vector () const
{
    return alpha_vector;
}

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_polynom_h
#define GF_polynom_h
 
#include "GF.h"
 
class GF_polynom
{
private:
    std::vector<GF> polynom; // вектор из коэфициентов полинома,
                             // которые принадлежат GF(2^m)
public:
    GF_polynom ();
    GF_polynom (const GF_polynom& GF_polynom_element);
    GF_polynom (const std::vector<GF>& coefficients);
    ~GF_polynom ();
 
    GF_polynom& operator= (const GF_polynom& right_hand_side);
 
    GF_polynom operator+ (const GF_polynom& right_hand_side) const; // сложение 
    GF_polynom operator* (const GF_polynom& right_hand_side) const; // умножение
    GF_polynom operator% (const GF_polynom& divisor) const; // остаток от деления
 
    void shift (const int shift_value);
 
    std::vector<GF> return_coefficients () const; // возвращает коэффициенты многочлена
};
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_polynom.h"
 
GF_polynom::GF_polynom ()
{
 
}
 
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element):
polynom (GF_polynom_element.polynom)
{
 
}
 
GF_polynom::GF_polynom (const std::vector<GF>& coefficients):
polynom (coefficients)
{
 
}
 
GF_polynom::~GF_polynom ()
{
 
}
 
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom.resize (right_hand_side.polynom.size());
    polynom = right_hand_side.polynom;
 
    return *this;
}
 
GF_polynom GF_polynom::operator+ (const GF_polynom& right_hand_side) const
{
    GF_polynom sum;
    sum.polynom.reserve (std::max(polynom.size(), right_hand_side.polynom.size()));
 
    for (int i = 0; i < std::min(polynom.size(), right_hand_side.polynom.size()); ++i)
        sum.polynom.push_back (polynom.at(i) + right_hand_side.polynom.at(i));
 
    if (polynom.size() < right_hand_side.polynom.size())
        for (int i = polynom.size(); i < right_hand_side.polynom.size(); ++i)
            sum.polynom.push_back (right_hand_side.polynom.at(i));
    else
        for (int i = right_hand_side.polynom.size(); i < polynom.size(); ++i)
            sum.polynom.push_back (polynom.at(i));
    
    return sum;
}
 
GF_polynom GF_polynom::operator* (const GF_polynom& right_hand_side) const
{
    GF_polynom prod;
    prod.polynom.resize (polynom.size() + right_hand_side.polynom.size());
 
    for (int i = 0; i < prod.polynom.size(); ++i)
    {
        GF sum (null_vector);
 
        for (int j = 0; j < i + 1; ++j)
            if ((j < polynom.size()) && (i - j < right_hand_side.polynom.size()))
                sum = sum + (polynom.at(j) * right_hand_side.polynom.at(i - j));
        
        prod.polynom.push_back (sum);
    }
 
    return prod;
}
 
GF_polynom GF_polynom::operator% (const GF_polynom& divisor) const
{
    GF_polynom reminder (*this); // остаток
    GF_polynom multiplier; // множитель, на который умножаем делитель
                           // (имеет вид a * x^n )
    multiplier.polynom.resize (reminder.polynom.size() - divisor.polynom.size() + 1);
 
    multiplier.shift (reminder.polynom.size() - divisor.polynom.size());// заполняем нулями все, кроме последнего
    
    while (reminder.polynom.size() > divisor.polynom.size()) // пока степень остачи больше степени делителя
    {
        multiplier.polynom.at(reminder.polynom.size() - divisor.polynom.size()) = //коэффициент при x^(n-m)
            reminder.polynom.at(reminder.polynom.size() - 1) / divisor.polynom.at(divisor.polynom.size() - 1);                        // m - степень делителя
 
        reminder = reminder + (divisor * multiplier); // обнуляем коэффициент
                                                      // при старшей степени
        multiplier.polynom.pop_back(); // убираем старший коэф., остаются одни нули
        reminder.polynom.pop_back(); // убираем старштй коэф., поскольку он нулевой
    }
 
    return reminder; // возвращаем остаток
}
 
void GF_polynom::shift (const int shift_value)
{
    polynom.reserve (polynom.size() + shift_value);
 
    for (int i = 0; i < shift_value; ++i)
        polynom.push_back (null_vector);
}
 
std::vector<GF> GF_polynom::return_coefficients () const
{
    return polynom;
}

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/* * * * * * * * * * * * * * * * * * * * * * *
                RS_encoder.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef RS_encoder_h
#define RS_encoder_h
 
#include "GF_polynom.h"
#include <string>
 
extern const int CODE_LENGTH; // длина кода
extern const int MAX_ERRORS; // количество исправляемых ошибок
extern const int MESSAGE_LENGTH; // длина сообщения
 
const GF_polynom init_GF_primitive_polynomial (const std::vector<int>& primitive_polynomial);
 
std::vector<int> str_to_int (const std::string& str_message); // строку в вектор
std::vector<GF> message_to_GF_message (const std::vector<int>& message); // вектор из 0 и 1 в 
                                                                         // вектор из элементов GF(2^m)
GF_polynom encode (const std::vector<GF>& GF_message); // кодирование сообщения
std::vector<int> GF_code_to_vector (const std::vector<GF>& code);
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                RS_encoder.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "RS_encoder.h"
 
const int MAX_ERRORS = 0;
const int CODE_LENGTH = 1 << GROUP_DEGREE - 1;
const int MESSAGE_LENGTH = 1 << GROUP_DEGREE - 1 - 2 * MAX_ERRORS;
 
const GF_polynom init_GF_primitive_polynomial (const std::vector<int>& primitive_polynomial = 
                                                init_primitive_polynomial(GROUP_DEGREE))
{
    std::vector<GF> GF_primitive_polynomial;
 
    for (auto iter = primitive_polynomial.begin(); iter != primitive_polynomial.end(); ++iter)
    {
        if (*iter == 0)
            GF_primitive_polynomial.push_back (null_vector);
        else
            GF_primitive_polynomial.push_back (unit_vector);
    }
 
    GF_primitive_polynomial.push_back (unit_vector);
 
    GF_polynom polynom (GF_primitive_polynomial);
    return polynom;
}
 
std::vector<int> str_to_int (const std::string& str_message)
{
    std::vector<int> int_message;
 
    for (auto iter = str_message.begin(); iter != str_message.end(); ++iter)
        int_message.push_back (*iter - '0');
 
    return int_message;
}
 
std::vector<GF> message_to_GF_message (const std::vector<int>& int_message)
{
    std::vector<int> message (int_message);
    message.reserve (GROUP_DEGREE * MESSAGE_LENGTH);
 
    for (int i = message.size(); i < GROUP_DEGREE * MESSAGE_LENGTH; ++i)
        message.push_back (0);
 
    std::vector<GF> GF_message;
 
    for (int i = 0; i < MESSAGE_LENGTH; ++i)
    {
        std::vector<int> one_symbol;
 
        for (int j = i * GROUP_DEGREE; j < (i + 1) * GROUP_DEGREE; ++j)
            one_symbol.push_back (message.at(j));
 
        GF_message.push_back (one_symbol);
    }
 
    return GF_message;  
}
 
GF_polynom encode (const std::vector<GF>& GF_message)
{
    GF_polynom u(GF_message);
    GF_polynom g(init_GF_primitive_polynomial());
    GF_polynom v;
 
    u.shift (2 * MAX_ERRORS);
 
    v = u + (u % g);
 
    return v;
}
 
std::vector<int> GF_polynom_to_vector (const GF_polynom& code)
{
    std::vector<GF> GF_messge (code.return_coefficients());
 
    std::vector<int> message;
 
    for (auto gf_iter = GF_messge.begin(); gf_iter != GF_messge.end(); ++gf_iter)
    {
        std::vector<int> temp (gf_iter->return_alpha_vector());
 
        for (auto iter = temp.begin(); iter != temp.end(); ++iter)
            message.push_back (*iter);
    }
 
    return message;
}

Чтобы вам не разбираться в тонкостях кода -- задавайте вопросы по каждому участку, а я постараюсь на них как можно более полно ответить.
Моя конечная цель была найти http://www.cyberforum.ru/cgi-bin/latex.cgi?v(x) = x^{n-k}u(x) + (x^{n-k}u(x) \mathrm {mod} g(x)).
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
09.11.2012, 12:27     Многочлены над GF(2^m) #19
C++
1
2
3
 multiplier.polynom.at(reminder.polynom.size() - divisor.polynom.size()) = //коэффициент при x^(n-m)
            reminder.polynom.at(reminder.polynom.size() - 1) /                    // n - степень текущего остатка
            divisor.polynom.at(divisor.polynom.size() - 1);                       // m - степень делителя
на
C++
1
*multiplier.polynom.rbegin() = (*reminder.polynom.rbegin()) / (*divisor.polynom.rbegin());
C++
1
2
3
4
5
6
7
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom.resize (right_hand_side.polynom.size());
    polynom = right_hand_side.polynom;
 
    return *this;
}
на
C++
1
2
3
4
5
6
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom = right_hand_side.polynom;
 
    return *this;
}
И еще раз пройдитесь по всему коду. Решите, где использовать resize, а где reserve.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.11.2012, 14:11     Многочлены над GF(2^m)
Еще ссылки по теме:

C++ Операции над множествами
Интерполяционный многочлены по чебышевским узлам C++
Построить интерполяционные многочлены Ньютона C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
09.11.2012, 14:11  [ТС]     Многочлены над GF(2^m) #20
Как я понял, резерв мы используем с пушбэками, а рисайз -- с операцией обращения (эт), верно? Какой вариант предпочтительнее использовать или в этом нет разницы?
Первые два листинга я тестировал: они вроди как работают... Сегодня-завтра попробую протестировать два остальных.
В 1-ом Вашем замечании я тоже сперва хотел так сделать, но не знал, где ставить звёздочку (точнее я использовал стрелочку) и оно мне выдавало ошибку
Yandex
Объявления
09.11.2012, 14:11     Многочлены над GF(2^m)
Ответ Создать тему
Опции темы

Текущее время: 06:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru