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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
#1

Кодирование Рида-Соломона - C++

27.01.2014, 19:34. Просмотров 325. Ответов 0
Метки нет (Все метки)

Я написал код. Нужна оценка экспертов, критика и всё такое.
Единственное: у меня почему-то не работает инициализация в конструкторе, типа:
C++
1
2
3
4
5
6
7
8
9
10
class A
{
    int m_value; 
public:
    A(int value)
};
A::A(int value):
    m_value(value)
{
}
Теперь комментарии по каждому файлу
Definitions.h -- различные определения/переопределения
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Definitions.h
 
#pragma once
 
typedef unsigned char uint8;
typedef unsigned int uint32;
 
static enum BasisType {POLYNOMIAL, ROOT};
 
static const uint8 PRIMITIVE_POLYNOMIAL = 0x1D;
static const uint8 PRIMITIVE_POLYNOMIAL_DEGREE = 0x08;
 
struct Data
{
    uint8* data;
    uint32 length;
};

GF.h/GF.cpp -- реализация поля Галуа.
Кликните здесь для просмотра всего текста
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
// GF.h
 
#pragma once
 
#include "Definitions.h"
 
class GF
{
public:    
    GF();
    GF(const uint8 value, const BasisType type = POLYNOMIAL);
 
    static void initializeTable(); // fills log and exp tables
    static void deleteTable(); // removes log and exp tables
 
    GF operator+(const GF& rhs) const; // operator- is the same as operator+
    GF operator*(const GF& rhs) const;  
    GF operator^(const uint8 rhs) const;
 
    GF operator+=(const GF& rhs); // operator-= is the same as operator+=
    GF operator*=(const GF& rhs);
    GF operator^=(const uint8 rhs);
 
    GF invert() const; // a/b == a * b.invert
 
    uint8 getPolynomial() const; // get value in polynomial basis
    uint8 getRoot() const; // get value in primitive root basis
 
private:
    uint8 m_polynomialBasis;
 
    static const uint8* POLYNOMIAL_TABLE; // converts polynomial to root
    static const uint8* ROOT_TABLE; // converts root to polynomial
    static const uint8 TABLE_SIZE = 0xFF;
};
// GF.cpp
 
#include "GF.h"
 
const uint8* GF::POLYNOMIAL_TABLE = nullptr; // converts polynomial to root
const uint8* GF::ROOT_TABLE = nullptr; // converts root to polynomial
 
GF::GF()
{
 
}
 
GF::GF(const uint8 value, const BasisType type) // default: type == BasisType::POLYNOMIAL
{
    switch(type)
    {
    case BasisType::POLYNOMIAL:
        m_polynomialBasis = value;
        break;
    case BasisType::ROOT:
        m_polynomialBasis = ROOT_TABLE[value];
    }
}
 
void GF::initializeTable()
{
    if((POLYNOMIAL_TABLE != nullptr) && (ROOT_TABLE != nullptr)) // protecting from double initialization
        return;
 
    // construct root table
    uint8* table = new uint8[TABLE_SIZE];
    
    for(uint8 i = 0; i < PRIMITIVE_POLYNOMIAL_DEGREE; ++i)
        table[i] = 1 << i;
 
    for (uint32 i = PRIMITIVE_POLYNOMIAL_DEGREE; i < TABLE_SIZE; ++i)
    {
        table[i] = table[i - 1] << 1;
 
        if(table[i - 1] >> 0x07) // if highest bit == 1
            table[i] ^= PRIMITIVE_POLYNOMIAL;
    }
 
    ROOT_TABLE = table;
    
    // construct polynomial table
    table = new uint8[TABLE_SIZE + 1]; // +1 for zero element
    
    table[0] = 0;
    for(uint32 i = 0; i < TABLE_SIZE; ++i)
        table[ROOT_TABLE[i]] = i;
 
    POLYNOMIAL_TABLE = table;
}
 
void GF::deleteTable()
{
    if((POLYNOMIAL_TABLE != nullptr) && (ROOT_TABLE != nullptr))
    {
        delete[] POLYNOMIAL_TABLE;
        delete[] ROOT_TABLE;
        POLYNOMIAL_TABLE = nullptr;
        ROOT_TABLE = nullptr;
    }
}
 
GF GF::operator+(const GF& rhs) const
{
    return GF(m_polynomialBasis ^ rhs.m_polynomialBasis);
}
 
GF GF::operator*(const GF& rhs) const
{
    if(this->m_polynomialBasis == 0)
        return *this;
    if(rhs.m_polynomialBasis == 0)
        return rhs;
 
    return GF(ROOT_TABLE[(uint32)(POLYNOMIAL_TABLE[m_polynomialBasis] + POLYNOMIAL_TABLE[rhs.m_polynomialBasis]) % 0xFE]); // 0xFE == TABLE_SIZE - 1
}
 
GF GF::operator^(const uint8 rhs) const
{
    if((m_polynomialBasis == 0) || (m_polynomialBasis == 1) || (rhs == 1))
        return *this;
    if(rhs == 0)
        return GF(1);
 
    return GF(ROOT_TABLE[(uint32)(POLYNOMIAL_TABLE[m_polynomialBasis] * rhs) % 0xFE]); // 0xFE == TABLE_SIZE - 1
}
 
GF GF::operator+=(const GF& rhs)
{
    *this = *this + rhs;
    return *this;
}
 
GF GF::operator*=(const GF& rhs)
{
    *this = *this * rhs;
    return *this;
}
 
GF GF::operator^=(const uint8 rhs)
{
    *this = *this ^ rhs;
    return *this;
}
 
GF GF::invert() const
{
    if(m_polynomialBasis == 0)
        throw "Divizion by zero";
 
    return GF(ROOT_TABLE[0xFE - POLYNOMIAL_TABLE[m_polynomialBasis]]); // 0xFE == TABLE_SIZE - 1
}
 
uint8 GF::getPolynomial() const
{
    return m_polynomialBasis;
}
 
uint8 GF::getRoot() const
{
    return POLYNOMIAL_TABLE[m_polynomialBasis];
}

Polynomial.h/Polynomial.cpp -- реализация многочленов с коэффициентами из поля Галуа.
Кликните здесь для просмотра всего текста
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
// Polynomial.h
 
#pragma once
 
#include "Definitions.h"
#include "GF.h"
 
class Polynomial
{
public:
    Polynomial();
    Polynomial(const Polynomial& polynomial);
    Polynomial(const uint32 polynomialDegree, const GF* coefficient = nullptr);
    Polynomial(const GF coefficient); // creates a constant polynomial (degree == 0)
 
    ~Polynomial();
 
    Polynomial operator=(const Polynomial& rhs);
 
    Polynomial operator+(const Polynomial& rhs) const; // operator- is the same as operator+
    Polynomial operator*(const Polynomial& rhs) const;
    Polynomial operator*(const GF& rhs) const; // multiplies each coefficient by rhs
    Polynomial operator%(const Polynomial& rhs) const;
 
    Polynomial operator+=(const Polynomial& rhs); // operator-= is the same as operator+
    Polynomial operator*=(const Polynomial& rhs);
    Polynomial operator%=(const Polynomial& rhs);
 
    Polynomial shift(const uint32 shiftValue) const; // multiplies polynomial by x^shiftValue
 
    GF* getCoefficients() const;
    uint32 getPolynomialDegree() const;
 
private:
    GF* m_coefficient;
    uint32 m_polynomialDegree; // size of coefficients equal to m_polynomialDegree + 1
};
// Polynomial.cpp
 
#include "Polynomial.h"
 
#include <cstring>
 
Polynomial::Polynomial()
{
    m_coefficient = nullptr;
}
 
Polynomial::Polynomial(const Polynomial& polynomial)
{
    m_coefficient = new GF[polynomial.m_polynomialDegree + 1];
    memcpy(m_coefficient, polynomial.m_coefficient, (polynomial.m_polynomialDegree + 1) * sizeof(GF));
    m_polynomialDegree = polynomial.m_polynomialDegree;
}
 
Polynomial::Polynomial(const uint32 polynomialDegree, const GF* coefficient) // default: coefficient == nullptr
{
    m_coefficient = new GF[polynomialDegree + 1];
    if(coefficient != nullptr)
        memcpy(m_coefficient, coefficient, (polynomialDegree + 1) * sizeof(GF));
    m_polynomialDegree = polynomialDegree;
}
 
Polynomial::Polynomial(const GF coefficient)
{
    m_coefficient = new GF;
    m_coefficient[0] = coefficient;
    m_polynomialDegree = 0;
}
 
Polynomial::~Polynomial()
{
    if(m_coefficient != nullptr)
    {
        delete[] m_coefficient;
        m_coefficient = nullptr;
    }
}
 
Polynomial Polynomial::operator=(const Polynomial& polynomial)
{
    if(this != &polynomial)
    {
        GF* newArray = new GF[polynomial.m_polynomialDegree + 1];
        memcpy(newArray, polynomial.m_coefficient, (polynomial.m_polynomialDegree + 1) * sizeof(GF));
 
        delete[] m_coefficient;
 
        m_coefficient = newArray;
        m_polynomialDegree = polynomial.m_polynomialDegree;
    }
 
    return *this;
}
 
Polynomial Polynomial::operator+(const Polynomial& rhs) const
{
    if(m_polynomialDegree < rhs.m_polynomialDegree)
    {
        Polynomial result(rhs);
 
        for(uint32 i = 0; i < m_polynomialDegree + 1; ++i)
            result.m_coefficient[i] = m_coefficient[i] + rhs.m_coefficient[i];
 
        return result;
    }
    else
    {
        Polynomial result(*this);
 
        for(uint32 i = 0; i < rhs.m_polynomialDegree + 1; ++i)
            result.m_coefficient[i] = m_coefficient[i] + rhs.m_coefficient[i];
 
        return result;
    }   
}
 
Polynomial Polynomial::operator*(const Polynomial& rhs) const
{
    Polynomial result(m_polynomialDegree + rhs.m_polynomialDegree);
    memset(result.m_coefficient, 0, (result.m_polynomialDegree + 1) * sizeof(GF));
 
    for(uint32 i = 0; i < m_polynomialDegree + 1; ++i)
        for(uint32 j = 0; j < rhs.m_polynomialDegree + 1; ++j)
            result.m_coefficient[i + j] += m_coefficient[i] * rhs.m_coefficient[j];
 
    return result;
}
 
Polynomial Polynomial::operator*(const GF& rhs) const
{
    Polynomial result(*this);
 
    for(uint32 i = 0; i < m_polynomialDegree + 1; ++i)
        result.m_coefficient[i] *= rhs;
 
    return result;
}
 
Polynomial Polynomial::operator%(const Polynomial& rhs) const
{
    if(m_polynomialDegree >= rhs.m_polynomialDegree)
    {
        GF tempCoefficient(rhs.m_coefficient[rhs.m_polynomialDegree].invert());
        Polynomial result(*this);       
        
        // school division algorithm
        do      
            if(result.m_coefficient[result.m_polynomialDegree].getPolynomial())
                result += rhs.shift(result.m_polynomialDegree - rhs.m_polynomialDegree) * (result.m_coefficient[result.m_polynomialDegree] * tempCoefficient);
        while(--result.m_polynomialDegree >= rhs.m_polynomialDegree);
 
        return result;
    }
    
    return *this;
}
 
Polynomial Polynomial::operator+=(const Polynomial& rhs)
{
    *this = *this + rhs;
    return *this;
}
 
Polynomial Polynomial::operator*=(const Polynomial& rhs)
{
    *this = *this * rhs;
    return *this;
}
 
Polynomial Polynomial::operator%=(const Polynomial& rhs)
{
    *this = *this % rhs;
    return *this;
}
 
Polynomial Polynomial::shift(const uint32 shiftValue) const
{
    Polynomial result(m_polynomialDegree + shiftValue);
    memset(result.m_coefficient, 0, shiftValue * sizeof(GF));
    memcpy(result.m_coefficient + shiftValue * sizeof(GF), m_coefficient, (m_polynomialDegree + 1) * sizeof(GF));
 
    return result;
}
 
GF* Polynomial::getCoefficients() const
{
    return m_coefficient;
}
 
uint32 Polynomial::getPolynomialDegree() const
{
    return m_polynomialDegree;
}

RS.h/RS.cpp -- кодер (в будущем, ещё и декодер) Рида-Соломона
Кликните здесь для просмотра всего текста
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
// RS.h
 
#pragma once
 
#include "Definitions.h"
#include "Polynomial.h"
 
class RS
{
public:
    RS(const uint32 n = 255, const uint32 k = 247);
    ~RS();
 
    Polynomial encode(const Polynomial& m);
 
private:
    uint32 m_n;
    uint32 m_k;
 
    Polynomial generatorPolynomial;
};
// RS.cpp
 
#include "RS.h"
 
RS::RS(const uint32 n, const uint32 k) // default: n = 255, k = 247
{
    m_n = n;
    m_k = k;
 
    // initialize GF table
    GF::initializeTable();
 
    // initialize generatorPolynomial
    generatorPolynomial = Polynomial(GF(1));
    GF monomial[2] = {1, 0};
    
    for(uint32 i = 0; i < m_n - m_k; ++i)
    {
        monomial[1] = GF(i + 1, BasisType::ROOT);
        generatorPolynomial *= Polynomial(1, monomial);
    }
}
 
RS::~RS()
{
    // remove GF table
    GF::deleteTable();
}
 
Polynomial RS::encode(const Polynomial& m)
{
    return Polynomial((m.shift(m_n - m_k) % generatorPolynomial) + m.shift(m_n - m_k));
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.01.2014, 19:34     Кодирование Рида-Соломона
Посмотрите здесь:

Кодер и декодер Рида-Соломона - C++
Здравствуйте! Дано задание: Кодирование и декодирование укороченного систематического кода Рида-Соломона (204, 188), который...

Коды Рида-Соломона. Реализация алгоритма - C++
Здравствуйте. Нужно реализовать кодирование и декодирование Рида-Соломона. В самом алгоритме я вроде разобрался. Но никак не могу написать...

Коды Рида-Соломона. Вычисление синдромов - C++
Добрый день! Пишу декодер Рида-Соломона, взяв за основу исходники из статьи Могущество кодов Рида-Соломона Перед этим разобрался с...

Кодирование, C++ - C++
Закодировать каждую букву произвольного символьного массива равномерным кодом.

Кодирование - C++
В какой тип данных можно записывать по одному биту 0 или 1, чтобы потом можно было считать целиком последовательность. Например, 010 или 1.

Кодирование по Хаффману, C++ - C++
Закодируйте какой-нибудь символьный массив по Хаффману примера ради.

Кодирование файла - C++
Задача написать часть полиморфного вируса для курсовой. Т.е нужно подать нашей программе на вход файл она должна зашифровать его по...

кодирование хаффмана - C++
здравствуйте! я пишу программу сжатия jpeg. написала код для кодирования хаффмана по дереву. и столкнулась с такой проблемой записываю в...

Кодирование Хаффмана - C++
Добрый вечер. Я за эту неделю малость зафлудил форум наверно. Прошу прощения за это. Просто уже не знаю, куда ещё обратиться со всем...

Кодирование информации! - C++
ПОДСКАЖИТЕ, в чем может быть ошибка! #include &lt;iostream&gt; #include &lt;fstream&gt; using namespace std; void code() { ifstream...

Арифметическое кодирование на С++ - C++
Здравствуйте. Такая проблема: нужно реализовать алгоритм арифметического кодирования и декодирования. Кодирование у меня получилось. Но...

Равномерное кодирование - C++
Задача такова: Программа должна запускаться с командной строки с темя параметрами: имя входного файла, имя выходного файла и режим работы...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru