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

@vlad_light · Регистрация: 24.09.2012

Author24 — интернет-сервис помощи студентам

Пишу кодер Рида-Соломона.
Дано следующее:
* $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$ - количество битов в одном символе (читай, элементов поля $https://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m)$ );
* $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ - длина кода (в символах);
* $https://www.cyberforum.ru/cgi-bin/latex.cgi?k$ - длина сообщения (в символах);
* $https://www.cyberforum.ru/cgi-bin/latex.cgi?g(x)$ - неприводимый многочлен степени $https://www.cyberforum.ru/cgi-bin/latex.cgi?n-k$ над $https://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m)$
* $https://www.cyberforum.ru/cgi-bin/latex.cgi?\overline m$ - сообщение из 0 и 1 конечной длины.
* $https://www.cyberforum.ru/cgi-bin/latex.cgi?u$ - сообщение, полученное из $https://www.cyberforum.ru/cgi-bin/latex.cgi?\overline m$ путём выделения блоков длины $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$ ;
* А также естественное отображение $https://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}$
На выходе нужно получить РС-код:
* $https://www.cyberforum.ru/cgi-bin/latex.cgi?v$ - код длины $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ (в символах), по формуле: $https://www.cyberforum.ru/cgi-bin/latex.cgi?v=A^{-1}(x^{n-k}(Au)(x)+(x^{n-k}(Au)(x) \mathrm{mod} g(x)))$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m)=\{0,\alpha ^0, \alpha ^1,...,\alpha ^{2^m-2}\}$ , где $https://www.cyberforum.ru/cgi-bin/latex.cgi?g(\alpha )=0$ .
По теории вроди бы всё, сейчас попробую описать прототип реализации.

Добавлено через 2 часа 17 минут
Посмотрите, пожалуйста!

Кликните здесь для просмотра всего текста

C++

#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++

#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++

#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. Завтра всё доделаю и буду приступать к написанию самих функций. Прокомментируйте, пожалуйста. Спасибо!!!

@I.M. · 06.11.2012, 12:19

include guard'ы написаны неверно - где define того, что проверяется в ifndef?

@vlad_light · 06.11.2012, 16:12 **[ТС]**

А я, когда пишу

C++

#ifndef prog.h
#define prog.h
/* code */
#endif

мне VS выдаёт ошибку, типа лишний раз объявлено. Или его не так писать надо?
Сейчас покушаю и напишу усовершенствованную версию=)

@I.M. · 06.11.2012, 17:01

в VS проще писать #pragma once
эта штука нестандартная, но много где работает
Меня тут - prog.h - точка смущает)

@vlad_light · 06.11.2012, 22:22 **[ТС]**

Вот (почти) финальный вариант. Гляньте одним глазком, всё ли верно? Я старался писать как можно более разборчиво

Кликните здесь для просмотра всего текста

C++

#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++

#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++

#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++

#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++

#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 · 06.11.2012, 23:04

Для table вижу reserve, но не вижу увеличения размера, собсно получается вектор с нулевым размером и затем идет попытка получить его первый элемент.
И еще, глаз режет:

C++

1	std::pow (2.0, GROUP_DEGREE)

Используйте

C++

1	1 << GROUP_DEGREE

@I.M. · 07.11.2012, 00:11

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 · 07.11.2012, 02:55 **[ТС]**

Пока написал 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++

/* * * * * * * * * * * * * * * * * * * * * * *
                    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++

/* * * * * * * * * * * * * * * * * * * * * * *
                    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 · 07.11.2012, 04:31

всё проще чем кажется. деструктор ~GF_table вообще отсутствует. Т.е. Объявлен и Не реализован.
Вот например строки 77-81 - это конструктор. Почему деструктор не написали примерно после конструктора?

@vlad_light · 08.11.2012, 02:44 **[ТС]**

Т.е. Объявлен и Не реализован.

Я думал, что если его объявить и не реализовать, то он реализуется сам по себе. А что в нём написать? Или лучше его пустым оставить?
Поправил первые два файлика, вроди всё работает. Гляньте ещё разок, на всякий.

Кликните здесь для просмотра всего текста

C++

/* * * * * * * * * * * * * * * * * * * * * * *
                    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++

/* * * * * * * * * * * * * * * * * * * * * * *
                    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++

/* * * * * * * * * * * * * * * * * * * * * * *
                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. · 08.11.2012, 13:38

Все конструкции такого вида

C++

GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element)
{
    polynom.resize (GF_polynom_element.polynom.size());
    polynom = GF_polynom_element.polynom;
}

лучше заменить на

C++

GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element):
polynom(GF_polynom_element.polynom)
{
}

Добавлено через 17 минут
в 71 строке вы создаете вектор определенной длины, заполненный нулями. А затем вы эти нули нигде не используете - только пушаете новые значения. Так и задумано?

@vlad_light · 08.11.2012, 17:08 **[ТС]**

ок, заменю. А что за 71 строка? Эта?

C++

1	sum.polynom.resize (std::max(polynom.size(), right_hand_side.polynom.size()));

@I.M. · 08.11.2012, 17:21

vlad_light, да, она. Я просто забыл дописать, из какого она листинга

@vlad_light · 08.11.2012, 17:23 **[ТС]**

т.е. там нужно вместо push_back везде написать at(i) верно?
Либо перед циклом написать clear.

@I.M. · 08.11.2012, 17:32

Лучше заменить resize на reserve. пушбеки оставить
Кстати вместо at(i) можно писать [i]

@vlad_light · 08.11.2012, 17:35 **[ТС]**

Спасибо! А с делением Вы мне можете помочь?

@I.M. · 08.11.2012, 17:38

С алгоритмом - вряд ли. Но если вы сможете в доступной форме изложить этот алгоритм и сказать "я вот сделал, но почему-то считает не так", то помогу, конечно

@vlad_light · 09.11.2012, 02:15 **[ТС]**

Отлично! Тогда я сейчас попробую реализовать столбиком (даже скорее не сейчас, а ближе к вечеру, поскольку сейчас есть ещё дела) и выложу здесь, а Вы посмотрите. Спасибо!
И ещё вопрос: а разве Вам проще разбираться в моём коде, чем написать собственный? Если да, то как научиться в нём разбираться, поскольку я в чужом коде вообще ничего понять не могу

Добавлено через 4 часа 35 минут
Алгоритм деления столбиком.
Имеем два многочлена $https://www.cyberforum.ru/cgi-bin/latex.cgi?a(x)\in P_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?div(x)\in P_m$ с коэффициентами из $https://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^k)$ . Не нарушая общности, положим $https://www.cyberforum.ru/cgi-bin/latex.cgi?n>m$ . Представим каждый многочлен в виде вектора из его коэффициентов
$https://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}$ .
Создаём две дополнительных переменных:
$https://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)$ ,
которая будет отображать текущий остаток от деления $https://www.cyberforum.ru/cgi-bin/latex.cgi?a(x)$ на $https://www.cyberforum.ru/cgi-bin/latex.cgi?div(x)$ , и $https://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x)\in P_{v-m}$ , который имеет вид
$https://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})$ .
Теперь на первом шаге умножаем $https://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x)$ на $https://www.cyberforum.ru/cgi-bin/latex.cgi?div(x)$ и прибавляем к $https://www.cyberforum.ru/cgi-bin/latex.cgi?rem$ , получаем
$https://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)$ .
Поскольку последний коэф. равен $https://www.cyberforum.ru/cgi-bin/latex.cgi?rem_v$ (такой же,как и у $https://www.cyberforum.ru/cgi-bin/latex.cgi?rem$ ), то при суммировании (что равно вычитанию) он сократиться. После этого мы убираем последний элемент из $https://www.cyberforum.ru/cgi-bin/latex.cgi?rem(x)$ , поскольку он равен нулю, и из $https://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x)$ , поскольку он нам больше не нужен. проделываем операцию до тех пор, пока степень текущего остатка не станет меньше степени делителя.

Не по теме:

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

Вот, что я пока написал, но не проверял. Гляньте, пожалуйста, уверен, там можно его переписать в лучшем виде.

Кликните здесь для просмотра всего текста

C++

/* * * * * * * * * * * * * * * * * * * * * * *
                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++

/* * * * * * * * * * * * * * * * * * * * * * *
                    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++

/* * * * * * * * * * * * * * * * * * * * * * *
                    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++

/* * * * * * * * * * * * * * * * * * * * * * *
                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++

/* * * * * * * * * * * * * * * * * * * * * * *
                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;
}

Чтобы вам не разбираться в тонкостях кода -- задавайте вопросы по каждому участку, а я постараюсь на них как можно более полно ответить.
Моя конечная цель была найти $https://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. · 09.11.2012, 12:27

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++

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++

GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom = right_hand_side.polynom;
 
    return *this;
}

И еще раз пройдитесь по всему коду. Решите, где использовать resize, а где reserve.

@vlad_light · 09.11.2012, 14:11 **[ТС]**

Как я понял, резерв мы используем с пушбэками, а рисайз -- с операцией обращения (эт), верно? Какой вариант предпочтительнее использовать или в этом нет разницы?
Первые два листинга я тестировал: они вроди как работают... Сегодня-завтра попробую протестировать два остальных.
В 1-ом Вашем замечании я тоже сперва хотел так сделать, но не знал, где ставить звёздочку (точнее я использовал стрелочку) и оно мне выдавало ошибку

@I.M. 576 / 559 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	06.11.2012, 12:19	2
	include guard'ы написаны неверно - где define того, что проверяется в ifndef? 1

@I.M. 576 / 559 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	06.11.2012, 17:01	4
	в VS проще писать #pragma once эта штука нестандартная, но много где работает Меня тут - prog.h - точка смущает) 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	07.11.2012, 04:31	9
	всё проще чем кажется. деструктор ~GF_table вообще отсутствует. Т.е. Объявлен и Не реализован. Вот например строки 77-81 - это конструктор. Почему деструктор не написали примерно после конструктора? 2

@I.M. 576 / 559 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	08.11.2012, 17:21	13
	vlad_light, да, она. Я просто забыл дописать, из какого она листинга 0

@vlad_light 4 / 4 / 1 Регистрация: 24.09.2012 Сообщений: 178
	08.11.2012, 17:23 [ТС]	14
	т.е. там нужно вместо push_back везде написать at(i) верно? Либо перед циклом написать clear. 0

@I.M. 576 / 559 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	08.11.2012, 17:32	15
	Лучше заменить resize на reserve. пушбеки оставить Кстати вместо at(i) можно писать [i] 1

@vlad_light 4 / 4 / 1 Регистрация: 24.09.2012 Сообщений: 178
	08.11.2012, 17:35 [ТС]	16
	Спасибо! А с делением Вы мне можете помочь? 0

@I.M. 576 / 559 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	08.11.2012, 17:38	17
	С алгоритмом - вряд ли. Но если вы сможете в доступной форме изложить этот алгоритм и сказать "я вот сделал, но почему-то считает не так", то помогу, конечно 0

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