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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.64
Hirurg2605
0 / 0 / 0
Регистрация: 29.08.2012
Сообщений: 3
#1

Коды Рида-Соломона. Вычисление синдромов - C++

29.08.2012, 13:47. Просмотров 3119. Ответов 2
Метки нет (Все метки)

Добрый день! Пишу декодер Рида-Соломона, взяв за основу исходники из статьи Могущество кодов Рида-Соломона
Перед этим разобрался с алгоритмами кодирования/декодирования и написал декодер с использованием функций библиотеки Intel Performance Primitive, но теперь стоит цель написать программу без этой библиотеки. Но уже на этапе нахождения синдромов возникает проблема - ненулевые синдромы в сообщении без ошибок. Подскажите пожалуйста, что я делаю не так.
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
#include "stdafx.h"
#include <iostream>
#include <ipp.h>
 
const int codeLength = 7;   // The desired codeword length.
const int dataLength = 3;   // The desired data length.
const int t = 2;
int feBitSize = 3;  // Size of the field element (in bits).
int pGFSize;
int pSize;
IppStatus status;
    
int main(int argc, char *argv[]) {
 
    //---------генерация сообщения----------------------//
    Ipp8u pMsg[dataLength];
    printf("Message:\n");
    for (int i = 0; i < dataLength; i++)
    {
        pMsg[i] = std::rand() % codeLength;
        printf("%u ", pMsg[i]);
    }
    printf("\n"); // получаем сообщение [6 1 6]
 
    
    //----------------------SET GF---------------------------------------//
    printf("GF init...\n");
    status = ippsGFGetSize_8u(feBitSize, &pGFSize); // Gets the size of the IppsGFSpec_8u context in bytes.
    printf("Size of IppsGFSpec_8u context = %d; ", pGFSize);
    printf("%s\n", ippGetStatusString(status));
 
    IppsGFSpec_8u* pGF = (IppsGFSpec_8u *) calloc(1, pGFSize);  // Pointer to the finite field context to be initialized.
    const Ipp8u pPolynomial[4] = {1, 1, 0, 1};  // Pointer to the polynomial generating the finite field.
    status = ippsGFInit_8u(feBitSize, pPolynomial, pGF);    // Initializes user-supplied memory as IppsGFSpec_8u context for future use.
    printf("Initializes user-supplied memory... %s\n", ippGetStatusString(status));
 
    //------------кодирование кодером IPP-------------//
    int pSize = 0;  // Pointer to the size of the context (in bytes).
    status = ippsRSEncodeGetSize_8u(codeLength, dataLength, &pSize);    // Gets the size of the ippsRSEncodeSpec_8u context in bytes.
    //printf("%s\n", ippGetStatusString(status));
    
    Ipp8u root = 1; // The root of the (first) minimal polynomial over GF.
    IppsRSEncodeSpec_8u* pRS = (IppsRSEncodeSpec_8u *) malloc(pSize);   // Pointer to the user-supplied buffer to be initialized as the IppsRSEncodeSpec_8u context.
    status = ippsRSEncodeInit_8u(codeLength, dataLength, pGF, root, pRS);   // Initializes user-supplied memory as the IppsRSEncodeSpec_8u context for future use.
    //printf("%s\n", ippGetStatusString(status));
 
    int pBufferSize = 0;    // Pointer to the size of the work buffer (in bytes).
    status = ippsRSEncodeGetBufferSize_8u(pRS, &pBufferSize);   // Gets the size of a work buffer for the encoding operation.
    //printf("%s\n", ippGetStatusString(status));
 
    Ipp8u pCodeWord[codeLength];
    Ipp8u* pBuffer=(Ipp8u *)malloc(pBufferSize);
    status=ippsRSEncode_8u(pMsg, pCodeWord, pRS, pBuffer);
    printf("\nCoding... %s\n", ippGetStatusString(status));
 
    printf("Code:\n");
    for (int i=0; i<codeLength; ++i)
        printf("%u ", pCodeWord[i]);
    printf("\n"); // код - [6 1 6 3 3 3 2]
 
    //-------вносим ошибки---------------//
    //pCodeWord[3] = 0;
    //pCodeWord[6] = 0;
    //pCodeWord[1] = 0;
 
    //----------------------pow of alpha----------------------------------//
    for (int i = 0; i < codeLength; i++)
    {
        Ipp8u alpha;
        ippsGFExpAlpha_8u(i, &alpha, pGF);
        printf("a^%u = %u\n", i, alpha);
    }
 
    //int p[m + 1] = {1, 0, 1, 1, 1, 0, 0, 0, 1};
    int alpha_to[codeLength + 1]; // таблица степеней примитивного члена
    int index_of[codeLength + 1]; // индексная таблица для быстрого умножения
    //----------------------------------------------------------------------------
    // генерируем look-up таблицу для быстрого умножения для GF(2 ^ m) на основе
    // несократимого порождающего полинома Pc от p[0] до p[m].
    //
    // look-up таблица:
    // index->polynomial из alpha_to[] содержит j = alpha ^ i,
    // где alpha есть примитивный член, обычно равный 2
    // а ^ - операция возведения в степень (не XOR!);
    //
    // polynomial form -> index из index_of[j = alpha ^ i] = i;
    //
    // c Simon Rockliff
    //----------------------------------------------------------------------------
    
    //----------------generate gf-----------------//
    int mask;
    mask = 1; alpha_to[feBitSize] = 0;
    
    for (int i = 0; i < feBitSize; i++)
    {
        alpha_to[i] = mask;
        index_of[alpha_to[i]] = i;
        
        if (pPolynomial[i] != 0)
            alpha_to[feBitSize] ^= mask;
        mask <<= 1;
    }
    index_of[alpha_to[feBitSize]] = feBitSize; mask >>= 1;
    
    for (int i = feBitSize + 1; i < codeLength; i++)
    {
        if (alpha_to[i - 1] >= mask)
            alpha_to[i] = alpha_to[feBitSize] ^ ((alpha_to[i - 1] ^ mask) << 1);
        else
            alpha_to[i] = alpha_to[i - 1] << 1;
        
        index_of[alpha_to[i]] = i;
    }
    index_of[0] = -1;
 
    //--------------------------------------------------------------------//
    //----------------------MY RS Decoder---------------------------------//
    //--------------------------------------------------------------------//
    printf("\nReceived message:\n");
    for (int i = 0; i < codeLength; i++)
    {
        printf("%u ", pCodeWord[i]);
    }
    printf("\n");
 
    int i, j, u, q;
    int s[codeLength - dataLength + 1]; // полином синдрома ошибки
    Ipp8u elp[codeLength - dataLength + 2][codeLength - dataLength]; // полином локатора ошибки лямда
    Ipp8u d[codeLength - dataLength + 2];
    Ipp8u l[codeLength - dataLength + 2];
    Ipp8u u_lu[codeLength - dataLength + 2];
        
    int count = 0, syn_error = 0;
    //int root[t];
    //int loc[t];
    //int z[t + 1];
    //int err[codeLength];
    //int reg[t + 1];
 
    // переводим полученное кодовое слово в индексную форму
    // для упрощения вычислений
    for (i = 0; i < codeLength; i++)
    {
        pCodeWord[i] = index_of[pCodeWord[i]];
    //  Ipp8u symb;
    //  ippsGFLogAlpha_8u(pCodeWord[i], &symb, pGF);
    //  pCodeWord[i] = symb;
    }
 
    // вычисляем синдром
    //---------------------------------------------------------------------------
    printf("\nSyndrome:\n");
    for (i = 1; i <= codeLength - dataLength; i++)
    {
        s[i] = 0;   // инициализация s-регистра
                    // на его вход по умолчанию поступает ноль
 
        // выполняем s[i] += recd[j] * ij
        // т.е. берем очередной символ декодируемых данных,
        // умножаем его на порядковый номер данного символа,
        // умноженный на номер очередного оборота и складываем
        // полученный результат с содержимым s-регистра;
        // по факту исчерпания всех декодируемых символ мы
        // повторяем весь цикл вычислений опять - по одному
        // разу для каждого символа четности
        for (j = 0; j < codeLength; j++)
            if (pCodeWord[j] != -1)
            {
                s[i] ^= alpha_to[(pCodeWord[j] + i * j) % codeLength];
 
                //Ipp8u pwr;
                //pwr = (pCodeWord[j] + i * j) % codeLength;
                //Ipp8u alpha;
                //ippsGFExpAlpha_8u(pwr, &alpha, pGF);
                //
                //s[i] ^= alpha;
            }
        if (s[i] != 0) syn_error = 1;   // если синдром не равен нулю, взводим флаг ошибки
        printf("%d ", s[i]);
        
        // преобразуем синдром из полиномиальной формы в индексную
        s[i] = index_of[s[i]];
        //Ipp8u syn;
        //ippsGFLogAlpha_8u(s[i], &syn, pGF);
        //s[i] = syn;
    }
 
    std::cin.get();
    return 0;
}
Добавлено через 42 минуты
UPD. Может быть проблема в том, что изначально код написан для C, а для C++ копипаст не прокатит? Что в этом случае нужно переделать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.08.2012, 13:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Коды Рида-Соломона. Вычисление синдромов (C++):

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

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

Коды Рида-Соломона - Matlab
Расскажите пожалуйста про принцип работы &quot;Кодировщик Рида-Соломона&quot;. Кто, что знает. Будет важна любая информация. Листинг 1. Исходный...

коды рида-соломона - Matlab
всем доброго времени, помогите пожалуйста реализовать код-рида соломона 111, 103, 4 с помощью стандартных функций. буду очень признателен...

Код Рида-Соломона - Maple
Нужно реализовать алгоритм получения (n,m) кода Рида-Соломона. Помогите кто сможет... Нашел на просторах инета файлик, ничерта не понятно.

Qt и алгоритм Соломона-Рида - C++ Qt
Приветствую. Создам еще одну тему. Вопрос такой. Есть ли у кого опыт использования кодов Соломона - Рида для коррекции ошибок при передаче...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Hirurg2605
0 / 0 / 0
Регистрация: 29.08.2012
Сообщений: 3
03.09.2012, 11:07  [ТС] #2
Не знаю можно ли проблему считать решённой, но если кто окажется в похожей ситуации попробуйте использовать исходники с сайта ECC. У меня "заработало"))
халк
0 / 0 / 0
Регистрация: 02.05.2011
Сообщений: 20
19.07.2013, 10:11 #3
Цитата Сообщение от Hirurg2605 Посмотреть сообщение
Добрый день! Пишу декодер Рида-Соломона, взяв за основу исходники из статьи Могущество кодов Рида-Соломона
Перед этим разобрался с алгоритмами кодирования/декодирования и написал декодер с использованием функций библиотеки Intel Performance Primitive, но теперь стоит цель написать программу без этой библиотеки. Но уже на этапе нахождения синдромов возникает проблема - ненулевые синдромы в сообщении без ошибок. Подскажите пожалуйста, что я делаю не так.
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
#include "stdafx.h"
#include <iostream>
#include <ipp.h>
 
const int codeLength = 7;   // The desired codeword length.
const int dataLength = 3;   // The desired data length.
const int t = 2;
int feBitSize = 3;  // Size of the field element (in bits).
int pGFSize;
int pSize;
IppStatus status;
    
int main(int argc, char *argv[]) {
 
    //---------генерация сообщения----------------------//
    Ipp8u pMsg[dataLength];
    printf("Message:\n");
    for (int i = 0; i < dataLength; i++)
    {
        pMsg[i] = std::rand() % codeLength;
        printf("%u ", pMsg[i]);
    }
    printf("\n"); // получаем сообщение [6 1 6]
 
    
    //----------------------SET GF---------------------------------------//
    printf("GF init...\n");
    status = ippsGFGetSize_8u(feBitSize, &pGFSize); // Gets the size of the IppsGFSpec_8u context in bytes.
    printf("Size of IppsGFSpec_8u context = %d; ", pGFSize);
    printf("%s\n", ippGetStatusString(status));
 
    IppsGFSpec_8u* pGF = (IppsGFSpec_8u *) calloc(1, pGFSize);  // Pointer to the finite field context to be initialized.
    const Ipp8u pPolynomial[4] = {1, 1, 0, 1};  // Pointer to the polynomial generating the finite field.
    status = ippsGFInit_8u(feBitSize, pPolynomial, pGF);    // Initializes user-supplied memory as IppsGFSpec_8u context for future use.
    printf("Initializes user-supplied memory... %s\n", ippGetStatusString(status));
 
    //------------кодирование кодером IPP-------------//
    int pSize = 0;  // Pointer to the size of the context (in bytes).
    status = ippsRSEncodeGetSize_8u(codeLength, dataLength, &pSize);    // Gets the size of the ippsRSEncodeSpec_8u context in bytes.
    //printf("%s\n", ippGetStatusString(status));
    
    Ipp8u root = 1; // The root of the (first) minimal polynomial over GF.
    IppsRSEncodeSpec_8u* pRS = (IppsRSEncodeSpec_8u *) malloc(pSize);   // Pointer to the user-supplied buffer to be initialized as the IppsRSEncodeSpec_8u context.
    status = ippsRSEncodeInit_8u(codeLength, dataLength, pGF, root, pRS);   // Initializes user-supplied memory as the IppsRSEncodeSpec_8u context for future use.
    //printf("%s\n", ippGetStatusString(status));
 
    int pBufferSize = 0;    // Pointer to the size of the work buffer (in bytes).
    status = ippsRSEncodeGetBufferSize_8u(pRS, &pBufferSize);   // Gets the size of a work buffer for the encoding operation.
    //printf("%s\n", ippGetStatusString(status));
 
    Ipp8u pCodeWord[codeLength];
    Ipp8u* pBuffer=(Ipp8u *)malloc(pBufferSize);
    status=ippsRSEncode_8u(pMsg, pCodeWord, pRS, pBuffer);
    printf("\nCoding... %s\n", ippGetStatusString(status));
 
    printf("Code:\n");
    for (int i=0; i<codeLength; ++i)
        printf("%u ", pCodeWord[i]);
    printf("\n"); // код - [6 1 6 3 3 3 2]
 
    //-------вносим ошибки---------------//
    //pCodeWord[3] = 0;
    //pCodeWord[6] = 0;
    //pCodeWord[1] = 0;
 
    //----------------------pow of alpha----------------------------------//
    for (int i = 0; i < codeLength; i++)
    {
        Ipp8u alpha;
        ippsGFExpAlpha_8u(i, &alpha, pGF);
        printf("a^%u = %u\n", i, alpha);
    }
 
    //int p[m + 1] = {1, 0, 1, 1, 1, 0, 0, 0, 1};
    int alpha_to[codeLength + 1]; // таблица степеней примитивного члена
    int index_of[codeLength + 1]; // индексная таблица для быстрого умножения
    //----------------------------------------------------------------------------
    // генерируем look-up таблицу для быстрого умножения для GF(2 ^ m) на основе
    // несократимого порождающего полинома Pc от p[0] до p[m].
    //
    // look-up таблица:
    // index->polynomial из alpha_to[] содержит j = alpha ^ i,
    // где alpha есть примитивный член, обычно равный 2
    // а ^ - операция возведения в степень (не XOR!);
    //
    // polynomial form -> index из index_of[j = alpha ^ i] = i;
    //
    // c Simon Rockliff
    //----------------------------------------------------------------------------
    
    //----------------generate gf-----------------//
    int mask;
    mask = 1; alpha_to[feBitSize] = 0;
    
    for (int i = 0; i < feBitSize; i++)
    {
        alpha_to[i] = mask;
        index_of[alpha_to[i]] = i;
        
        if (pPolynomial[i] != 0)
            alpha_to[feBitSize] ^= mask;
        mask <<= 1;
    }
    index_of[alpha_to[feBitSize]] = feBitSize; mask >>= 1;
    
    for (int i = feBitSize + 1; i < codeLength; i++)
    {
        if (alpha_to[i - 1] >= mask)
            alpha_to[i] = alpha_to[feBitSize] ^ ((alpha_to[i - 1] ^ mask) << 1);
        else
            alpha_to[i] = alpha_to[i - 1] << 1;
        
        index_of[alpha_to[i]] = i;
    }
    index_of[0] = -1;
 
    //--------------------------------------------------------------------//
    //----------------------MY RS Decoder---------------------------------//
    //--------------------------------------------------------------------//
    printf("\nReceived message:\n");
    for (int i = 0; i < codeLength; i++)
    {
        printf("%u ", pCodeWord[i]);
    }
    printf("\n");
 
    int i, j, u, q;
    int s[codeLength - dataLength + 1]; // полином синдрома ошибки
    Ipp8u elp[codeLength - dataLength + 2][codeLength - dataLength]; // полином локатора ошибки лямда
    Ipp8u d[codeLength - dataLength + 2];
    Ipp8u l[codeLength - dataLength + 2];
    Ipp8u u_lu[codeLength - dataLength + 2];
        
    int count = 0, syn_error = 0;
    //int root[t];
    //int loc[t];
    //int z[t + 1];
    //int err[codeLength];
    //int reg[t + 1];
 
    // переводим полученное кодовое слово в индексную форму
    // для упрощения вычислений
    for (i = 0; i < codeLength; i++)
    {
        pCodeWord[i] = index_of[pCodeWord[i]];
    //  Ipp8u symb;
    //  ippsGFLogAlpha_8u(pCodeWord[i], &symb, pGF);
    //  pCodeWord[i] = symb;
    }
 
    // вычисляем синдром
    //---------------------------------------------------------------------------
    printf("\nSyndrome:\n");
    for (i = 1; i <= codeLength - dataLength; i++)
    {
        s[i] = 0;   // инициализация s-регистра
                    // на его вход по умолчанию поступает ноль
 
        // выполняем s[i] += recd[j] * ij
        // т.е. берем очередной символ декодируемых данных,
        // умножаем его на порядковый номер данного символа,
        // умноженный на номер очередного оборота и складываем
        // полученный результат с содержимым s-регистра;
        // по факту исчерпания всех декодируемых символ мы
        // повторяем весь цикл вычислений опять - по одному
        // разу для каждого символа четности
        for (j = 0; j < codeLength; j++)
            if (pCodeWord[j] != -1)
            {
                s[i] ^= alpha_to[(pCodeWord[j] + i * j) % codeLength];
 
                //Ipp8u pwr;
                //pwr = (pCodeWord[j] + i * j) % codeLength;
                //Ipp8u alpha;
                //ippsGFExpAlpha_8u(pwr, &alpha, pGF);
                //
                //s[i] ^= alpha;
            }
        if (s[i] != 0) syn_error = 1;   // если синдром не равен нулю, взводим флаг ошибки
        printf("%d ", s[i]);
        
        // преобразуем синдром из полиномиальной формы в индексную
        s[i] = index_of[s[i]];
        //Ipp8u syn;
        //ippsGFLogAlpha_8u(s[i], &syn, pGF);
        //s[i] = syn;
    }
 
    std::cin.get();
    return 0;
}
Добавлено через 42 минуты
UPD. Может быть проблема в том, что изначально код написан для C, а для C++ копипаст не прокатит? Что в этом случае нужно переделать?
ЗДравствуйте. Если сохранились исходники работающего варианта без использования библиотек, можете их скинуть. У меня тоже проблема с синдромами
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.07.2013, 10:11
Привет! Вот еще темы с ответами:

Кодер/декодер Рида-Соломона. Перевести с C на С# - C#
Нужно было реализовать кодер/декодер Рида-Соломона. Изначально код был на си, все работало. Переведя код на c#, он уже не работает. Скорее...

Коррекция ошибок методом Рида-Соломона - Дискретная математика
Делаю программу для штрих кода. Застопорился на коррекции ошибок методом Рида-Соломона Вот ссылка на оригинал статьи на английском ...

Кодирование информации методом кодов Рида-Соломона - Информатика
Добрый времени суток форумчане. Есть у меня такая задача написать программу, которое моделирует помехоустойчивое кодирование методом...

Как соединить генератор Бернулли и кодер Рида-Соломона? - Simulink
Добрый вечер. Очень хочу закодировать случайный сигнал от генератора Бернулли (Bernoulli Binary Generator) кодером Рида-Соломона...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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