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

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

Восстановить пароль Регистрация
 
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
27.01.2014, 19:34     Кодирование Рида-Соломона #1
Я написал код. Нужна оценка экспертов, критика и всё такое.
Единственное: у меня почему-то не работает инициализация в конструкторе, типа:
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++
C++ Кодирование, C++
C++ Коды Рида-Соломона. Вычисление синдромов
C++ Кодирование
Равномерное кодирование C++
C++ Кодирование слов
C++ Кодирование информации!
Коды Рида-Соломона. Реализация алгоритма C++

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

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

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