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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.64
Hirurg2605
0 / 0 / 0
Регистрация: 29.08.2012
Сообщений: 3
29.08.2012, 13:47     Коды Рида-Соломона. Вычисление синдромов #1
Добрый день! Пишу декодер Рида-Соломона, взяв за основу исходники из статьи Могущество кодов Рида-Соломона
Перед этим разобрался с алгоритмами кодирования/декодирования и написал декодер с использованием функций библиотеки 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++
getch и коды C++
C++ не разборчивые коды
C++ Коды исключений
C++ короткие коды с ********
Коды Рида-Соломона. Реализация алгоритма C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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++ копипаст не прокатит? Что в этом случае нужно переделать?
ЗДравствуйте. Если сохранились исходники работающего варианта без использования библиотек, можете их скинуть. У меня тоже проблема с синдромами
Yandex
Объявления
19.07.2013, 10:11     Коды Рида-Соломона. Вычисление синдромов
Ответ Создать тему
Опции темы

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