Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Коды БЧХ
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
Страницы: 1, 2, 3, 4
des00
Цитата(petrov @ Oct 5 2010, 02:29) *
В эзернете ограниченный бюджет задержки и там используется специальный TCM код с маленькой задержкой декодирования. Можно использовать TPC на основе расширенного БЧХ(16,11,4), длина блока 256, скорость 11^2/16^2, выигрыш около 5 дБ, ещё лучше на основе БЧХ(32,26,4), выигрыш около 6.5 дБ. По ресурсам не влезет конечно, но получить приличный выигрыш на относительно коротких блоках можно.

Ничего себе я ошибался laughing.gif, а ссылками/названиями/литературой по этим кодерам не поделитесь? Спасибо.
petrov
Цитата(des00 @ Oct 5 2010, 12:25) *
Ничего себе я ошибался laughing.gif, а ссылками/названиями/литературой по этим кодерам не поделитесь? Спасибо.


Книгу Channel_Coding_in_Communication_Networks_-_ Glavieux.pdf выкладывал уже, есть у вас? Там сам изобретатель TPC Pyndiah главу по ним написал, и в применении к FPGA у него относительно неплохо расписано, статьи его так же в гугле свободно скачиваются.
des00
Цитата(petrov @ Oct 5 2010, 03:41) *
Книгу Channel_Coding_in_Communication_Networks_-_ Glavieux.pdf выкладывал уже, есть у вас? Там сам изобретатель TPC Pyndiah главу по ним написал, и в применении к FPGA у него относительно неплохо расписано, статьи его так же в гугле свободно скачиваются.

нет, но найдем. главное название знать %) Работы над текущим трансивером много и без кодирования, пока поставлю БЧХ и соберу модемную часть, потом займусь апгрейтом кодирования %)
SKov
Цитата(petrov @ Oct 5 2010, 12:41) *
Книгу Channel_Coding_in_Communication_Networks_-_ Glavieux.pdf выкладывал уже, есть у вас?

Я почему-то не видел этот документ. Вас не затруднит его куда-нибудь выложить? На Рапидшаре он уже "протух".
Цитата
Там сам изобретатель TPC Pyndiah главу по ним написал

Изобретатель? biggrin.gif biggrin.gif biggrin.gif
des00
Цитата(SKov @ Oct 5 2010, 04:18) *
Я почему-то не видел этот документ. Вас не затруднит его куда-нибудь выложить? На Рапидшаре он уже "протух".

тут
petrov
Цитата(SKov @ Oct 5 2010, 13:18) *
Я почему-то не видел этот документ. Вас не затруднит его куда-нибудь выложить? На Рапидшаре он уже "протух".

Изобретатель? biggrin.gif biggrin.gif biggrin.gif

http://rapidshare.com/files/423220808/Chan...-__Glavieux.pdf

Изобретатель изобретатель

http://www.freepatentsonline.com/6122763.html
SKov
Цитата(des00 @ Oct 5 2010, 13:30) *
тут

Спасибо.
Извините, забыл про ваш вопрос. Интересующие Вас минимальные многочлены можно
взять из таблицы в конце книжки Питерсона и Уэлдона. Она есть в и-нете.
Serg76
petrov

столько времени занимаюсь кодированием, а эту книгу вижу впервые. по первому взгляду книга хороша, есть вопросы практического применения. спасибо за ссылку
SKov
Цитата(petrov @ Oct 5 2010, 13:34) *
Изобретатель изобретатель

Он сам себя таковым не считает. Посмотрите введение к его главе. Он там справедливо
упоминает и Хагенауэра и "многих других исследователей".
Very quickly many researchers, such as Hagenauer,
Benedetto, Divsalar [HAG 96, BEN 96, DIV 95, ROB 94, WIB 95] and a number of
others confirmed the results of Berrou and within a few years the turbocode became
essential in the field of the error corrector coding as the 21st century solution.

Это правильно.
Другое дело, что эти западники никогда (почти) не упоминают наши отечественные исследования в этой области.
Как-будто это не в нашей стране была одна из лучших школ теории информации и кодирования.
Это касается и блоковых турбокодов на основе расширенных кодов Хемминга.
Вот здесь, например, есть по крайней мере две статьи с описанием кодирования - декодирования и результатов
моделирования таких турбокодов (это 1995год). Правда, у этого Pyndiah-а есть ссылка на тезисы конференции 1994 года.
Ну, значит он был первый wink.gif Тогда интернет был в зачаточном состоянии, ездили на конференции мало,
и информация распространялась медленно.
Как пишут в таких случаях "результаты были получены независимо и почти одновременно".
Просто за державу обидно wink.gif
vadimuzzz
Цитата(SKov @ Oct 5 2010, 17:20) *
Просто за державу обидно wink.gif

в нашей стране проще ознакомиться с трудами IEEE, чем увидеть журналы типа того, что вы указали
des00
Цитата(des00 @ Oct 5 2010, 00:15) *
UPD. Конечно можно сгенерить всё в матлабе и копипастом перенести в код. Но интересно написать функции генерации кода БЧХ на SV, которые будут определять всю структуру (все функции кроме генерации генераторного полинома на SV есть и работают, ква таки сила), чтобы не зависеть ни от каких генераторов.

сорцы выложены тут автоматическое определение генераторного полинома еще не допилил %)


Цитата(SKov @ Oct 5 2010, 04:38) *
Спасибо.
Извините, забыл про ваш вопрос. Интересующие Вас минимальные многочлены можно
взять из таблицы в конце книжки Питерсона и Уэлдона. Она есть в и-нете.

вот что странно, в Си коде, который я приводил функция генерации генераторного полинома
CODE

void gen_poly()
/*
* Compute the generator polynomial of a binary BCH code. Fist generate the
* cycle sets modulo 2**m - 1, cycle[][] = (i, 2*i, 4*i, ..., 2^l*i). Then
* determine those cycle sets that contain integers in the set of (d-1)
* consecutive integers {1..(d-1)}. The generator polynomial is calculated
* as the product of linear factors of the form (x+alpha^i), for every i in
* the above cycle sets.
*/
{
register int i, ii, jj, ll, kaux;
register int test, aux, nocycles, root, noterms, rdncy;
int cycle[1024][21], size[1024], min[1024], zeros[1024];

/* Generate cycle sets modulo n, n = 2**m - 1 */
cycle[0][0] = 0;
size[0] = 1;
cycle[1][0] = 1;
size[1] = 1;
jj = 1; /* cycle set index */
if (m > 9) {
printf("Computing cycle sets modulo %d\n", n);
printf("(This may take some time)...\n");
}
do {
/* Generate the jj-th cycle set */
ii = 0;
do {
ii++;
cycle[jj][ii] = (cycle[jj][ii - 1] * 2) % n;
size[jj]++;
aux = (cycle[jj][ii] * 2) % n;
} while (aux != cycle[jj][0]);
/* Next cycle set representative */
ll = 0;
do {
ll++;
test = 0;
for (ii = 1; ((ii <= jj) && (!test)); ii++)
/* Examine previous cycle sets */
for (kaux = 0; ((kaux < size[ii]) && (!test)); kaux++)
if (ll == cycle[ii][kaux])
test = 1;
} while ((test) && (ll < (n - 1)));
if (!(test)) {
jj++; /* next cycle set index */
cycle[jj][0] = ll;
size[jj] = 1;
}
} while (ll < (n - 1));
nocycles = jj; /* number of cycle sets modulo n */

/*
printf("Enter the error correcting capability, t: ");
scanf("%d", &t);
*/
t = 3;

d = 2 * t + 1;

/* Search for roots 1, 2, ..., d-1 in cycle sets */
kaux = 0;
rdncy = 0;
for (ii = 1; ii <= nocycles; ii++) {
min[kaux] = 0;
test = 0;
for (jj = 0; ((jj < size[ii]) && (!test)); jj++)
for (root = 1; ((root < d) && (!test)); root++)
if (root == cycle[ii][jj]) {
test = 1;
min[kaux] = ii;
}
if (min[kaux]) {
rdncy += size[min[kaux]];
kaux++;
}
}
noterms = kaux;
kaux = 1;
for (ii = 0; ii < noterms; ii++)
for (jj = 0; jj < size[min[ii]]; jj++) {
zeros[kaux] = cycle[min[ii]][jj];
kaux++;
}

k = length - rdncy;

if (k<0)
{
printf("Parameters invalid!\n");
// exit(0);
return ;
}

printf("This is a (%d, %d, %d) binary BCH code\n", length, k, d);

/* Compute the generator polynomial */
g[0] = alpha_to[zeros[1]];
g[1] = 1; /* g(x) = (X + zeros[1]) initially */
for (ii = 2; ii <= rdncy; ii++) {
g[ii] = 1;
for (jj = ii - 1; jj > 0; jj--)
if (g[jj] != 0)
g[jj] = g[jj - 1] ^ alpha_to[(index_of[g[jj]] + zeros[ii]) % n];
else
g[jj] = g[jj - 1];
g[0] = alpha_to[(index_of[g[0]] + zeros[ii]) % n];
/*
printf("Generator polynomial:\ng(x) = ");
for (i = 0; i <= 31; i++) {
printf("%d", g[i]);
}
printf("\n");
*/
}
printf("Generator polynomial:\ng(x) = ");
for (ii = 0; ii <= rdncy; ii++) {
printf("%d", g[ii]);
if (ii && ((ii % 50) == 0))
printf("\n");
}
printf("\n");
}

явно показывает что никакие таблицы не используются. Все вычисления производятся на лету. Надо будет еще раз к ней подойти до полной ясности %)
SKov
Цитата(vadimuzzz @ Oct 5 2010, 15:51) *
в нашей стране проще ознакомиться с трудами IEEE, чем увидеть журналы типа того, что вы указали

В 95-м году это было не так. Надо было одинаково идти в крупную библиотеку какого-нибудь крупного города.
Это не журнал, это тезисы докладов научной конференции.
Сейчас их не стоит и смотреть, поскольку прошло 15 лет, там все устарело.
Это интересно разве что с точки зрения истории и приоритетов.
wavemaster
А кто-нибудь сталкивался с алгоритмом на основе матрицы Вандермормонда? Мне он показался более практичным чем Форни для малых значений ошибок, но разобраться с ним у Сарагосы у меня не получилось.
x736C
Цитата(des00 @ Oct 4 2010, 16:34) *
ЗЫ. Мне сильно желательно диагностика такой ситуации для канала без явной синхронизации. Чтобы лучше работала система синхронизации. Подобное я делал на корке RS, но никогда не задумывался, до сего момента, что decfailed корки мне врал %(

Ув. des00, Вы обеспечиваете синхронизацию декодера по доминирующим нулевым синдромам? Или я не в ту степь?!


Цитата(Mikhalych @ Sep 28 2010, 16:02) *
нет - всё на логике и сдвиговых регистрах

Буфер принятого слова для ожидания декодирования тоже на регистрах или в нем нет необходимости?
des00
Цитата(x736C @ Jan 19 2011, 03:57) *
Ув. des00, Вы обеспечиваете синхронизацию декодера по доминирующим нулевым синдромам? Или я не в ту степь?!

да именно так, но такое хорошо работает только на декодерах с большой исправляющей способностью (1/2, 3/4, 5/6, 7/8, 9/10) и большим размером блока. Для сабжевого конкретного случая я перешел на синхронизацию по шапочке.
x736C
Цитата(des00 @ Jan 21 2011, 11:43) *
да именно так, но такое хорошо работает только на декодерах с большой исправляющей способностью (1/2, 3/4, 5/6, 7/8, 9/10) и большим размером блока. Для сабжевого конкретного случая я перешел на синхронизацию по шапочке.

Спасибо.
Знакомы ли Вы с многочисленными статьями а-ля «blind frame synch. of BCH»?
В большинстве статей для синхронизации предлагается parity check matrix.
Пытаюсь разобраться в особенностях популярных алгоритмов sm.gif

Цитата(Mikhalych @ Sep 28 2010, 10:26) *
Недавно сам занимался аппаратной реализацией такого декодера...
...
8 - готовая прожка кодирования/декодирования от микрона (по ней я отлаживался)

Правильно ли я понимаю, что программа использует исключительно укороченные коды?
(”Number of data bits to be encoded. Must divide 4.“)
Что кажется логичным, т.к. программа реализует защиту флеш-памяти.
des00
Цитата(x736C @ Jan 21 2011, 07:19) *
Знакомы ли Вы с многочисленными статьями а-ля «blind frame synch. of BCH»?
В большинстве статей для синхронизации предлагается parity check matrix.
Пытаюсь разобраться в особенностях популярных алгоритмов sm.gif

нет, не знаком. буду премного благодарен если поделитесь. тестируя короткие БЧХ коды, я пришел к выводу что слепая синхра не возможна. Буду рад ошибаться
x736C
Хорошо. Итак.

Архив содержит следующие документы:
Blind Frame Synchronization For Block Code.pdf
Blind Frame Synchronization And Phase Offset Estimation For Coded Systems.pdf
Blind Frame Synchronization For Error Correcting Codes Having a Sparse Parity Check Matrix.pdf
Blind frame synchronization of product codes based on the adaptation of the parity check matrix.pdf
Blind Frame Synchronization of Reed-Solomon Codes.pdf
Blind Frame Synchronization on Gaussian Channel.pdf

Нажмите для просмотра прикрепленного файла

Кое-что вынес за скобки. В принципе всё есть в инете.

Из того, что очень интересно, но найти не удалось.
http://elibrary.ru/item.asp?id=11532386
Приведен пример реализации кодовой цикловой синхронизации для каскадного кода БЧХ(31,16) -
- Рида-Соломона(32,16), обеспечивающего надежную синхронизацию в канале связи с вероятностью
ошибки до 10^-1.


http://elibrary.ru/item.asp?id=11520710
Методы кодовой цикловой синхронизации и их применение для передачи сообщений в каналах связи
с вероятностью ошибки до 10^-1

des00
Цитата(petrov @ Oct 4 2010, 10:54) *
Хотя бы мягкое декодирование БЧХ по алгоритму Чейза используйте.


Цитата(SKov @ Oct 4 2010, 12:59) *
Конечно, и в этом случае можно использовать декодер БЧХ для ДСК, применяя алгоритмы Чейза или декодирование по МОР (Форни.)
Но много там не получишь (обычно в пределах 1.5...2 дБ дополнительного выигрыша к ЭВК дискретного канала).
Но для длин <100 это все равно надо делать и это будет хорошо.


Нашел время вернуться к БЧХ кодам и алгоритму Чейза. Есть несколько вопросов :

1. в книге Кларка, при описании алгоритма Чейза он пишет :
Цитата
Метод 2: взять в качестве векторов 1 множество из 2^d/2 векторов, имеющих всевозможные символы на d/2 наименее достоверных позициях и нулевые символы на остальных.

Но нигде в книге нет ни слова, как определить какие символы наименее достоверные. Неужели предполагается выделять достоверность символов с помощью сравнения их квантованных амплитуд, считая что чем больше амплитуда (например для BPSK) тем символ достовернее ?

2. В разделе "8.1.3. Системы, использующие код Рида—Соломона и короткий блоковый код". Неужели такие системы использовались/используются? Всегда считал что наиболее подходящими для каскада являются блоковый и сверточные коды.

3. Прочитал у него же про многопороговое декодирование блоковых кодов. Правильно ли я понял, что при использовании того же БЧХ (15,5,7) и многопорогового декодера с мягким решением, выигрыш от кодирования будет больше чем при использовании арифметического БЧХ с Чейзом ?

Спасибо.
petrov
Цитата(des00 @ Jan 12 2012, 10:46) *
Но нигде в книге нет ни слова, как определить какие символы наименее достоверные. Неужели предполагается выделять достоверность символов с помощью сравнения их квантованных амплитуд, считая что чем больше амплитуда (например для BPSK) тем символ достовернее ?


Да.
Gold777
Цитата(des00 @ Oct 1 2010, 10:40) *
либо я тупой, либо одно из двух crying.gif в статьях выложенных выше приведены 4 варианта алгоритма SiBM. Но все они разные. В целях пристрелки реализовал один в один 3 штуки ни один не работает(причем в одном алгоритме была ошибка). Детальное исполнение алгоритма на бумажке показывает что косяков в реализации нет, но алгоритм не работает %)
Может быть у кого нить есть статья с описанием SiBM который приведен без ошибок?

Спасибо.

Возникла та же проблема. Реализовал SiBM, вношу одну ошибку в КС. А декодер показывает что их две (вычисления приводят к полиному локаторов 2-й степени, Ченя соответственно решает и находит 2 корня). Считаю на бумаге все получается. Может где в алгоритме ошибка?Нажмите для просмотра прикрепленного файла
des00
Цитата(petrov @ Jan 12 2012, 03:28) *
Да.

нда, все оригинальное просто sm.gif

Цитата(Gold777 @ Jan 12 2012, 09:39) *
Возникла та же проблема. Реализовал SiBM, вношу одну ошибку в КС. А декодер показывает что их две (вычисления приводят к полиному локаторов 2-й степени, Ченя соответственно решает и находит 2 корня). Считаю на бумаге все получается. Может где в алгоритме ошибка?Нажмите для просмотра прикрепленного файла

все алгоритмы в статьях рабочие, отличия только в деталях/индексах и т.д. реализации для плис всех этих алгоритмов для БЧХ/РС кодов я выкладывал в этой теме.

Gold777
Цитата(des00 @ Jan 13 2012, 08:57) *
нда, все оригинальное просто sm.gif


все алгоритмы в статьях рабочие, отличия только в деталях/индексах и т.д. реализации для плис всех этих алгоритмов для БЧХ/РС кодов я выкладывал в этой теме.

Если я работаю с записанным сигналом, прогоняю его через Моделсим алгоритм работает правильно. Если в реальном времени, вношу к примеру одну ошибку в чистый сигнал находится внесенная ошибка правильно, но помимо нее декодер находит определенную постоянную вторую ошибку на месте на котором ее быть не должно в каждом кодовом слове (соответственно полином локаторов имеет в данном случае вторую степень). Вот собственно такую ситуацию я наблюдаю в SignalTab. Такая же ситуация наблюдается при увеличении числа ошибок. Вот не пойму где ошибка то у меня?
des00
Цитата(Gold777 @ Jan 13 2012, 03:45) *
Вот не пойму где ошибка то у меня?

ошибка описания, синтезируемая модель и поведенческая ведут себя по-разному.
Gold777
Цитата(des00 @ Jan 13 2012, 17:15) *
ошибка описания, синтезируемая модель и поведенческая ведут себя по-разному.

Спасибо за помощь. Разобрался. Старую таблицу памяти подцепил, в которой ошибка была.
Denisnovel
Можно ли определить невозможность исправления ошибок до вычисления всех локаторов ошибок(в поиске Ченя)? Проблема в том, что декодер пытается исправить ошибки и вносит новые.
petrov
Цитата(Denisnovel @ Mar 4 2012, 10:21) *
Можно ли определить невозможность исправления ошибок до вычисления всех локаторов ошибок(в поиске Ченя)? Проблема в том, что декодер пытается исправить ошибки и вносит новые.


Уже обсуждалось в этом топике...
Denisnovel
Из обсуждения выше я понял, что достоверно невозможно определить количество ошибок, если ошибок слишком много. Но меня интересует случай, когда ошибок меньше граници детектирования. Можно ли в этом случае определить возможность исправления ошибок до поиска ченя?
petrov
Цитата(Denisnovel @ Mar 6 2012, 08:16) *
Но меня интересует случай, когда ошибок меньше граници детектирования. Можно ли в этом случае определить возможность исправления ошибок до поиска ченя?


Вопрос дурацкий, если ошибки можно исправить то их можно исправить и ничего определять не надо.
Gold777
Цитата(Denisnovel @ Mar 6 2012, 08:16) *
Из обсуждения выше я понял, что достоверно невозможно определить количество ошибок, если ошибок слишком много. Но меня интересует случай, когда ошибок меньше граници детектирования. Можно ли в этом случае определить возможность исправления ошибок до поиска ченя?

Если количество ошибок превышает исправляющую способность кода , то нет смысла определять сколько было ошибок. Если как Вы говорите ошибок точно меньше исправляющей способности, то вы с высокой степенью вероятности можете предположить, что возможность исправления есть. А вот местоположения этих ошибок Вы сможете определить только после процедуры Ченя. Хотя мне непонятно зачем Вам определять возможность исправления.
Denisnovel
Может я не правильно выразился. Можно ли вычислить сигнал "decoding failure" до поиска Ченя?
Gold777
Цитата(Denisnovel @ Mar 6 2012, 09:54) *
Может я не правильно выразился. Можно ли вычислить сигнал "decoding failure" до поиска Ченя?

нельзя
Denisnovel
Ясно. Спасибо.
des00
Цитата(Gold777 @ Mar 6 2012, 00:58) *
нельзя


Цитата(Denisnovel @ Mar 6 2012, 01:04) *
Ясно. Спасибо.


можно, но не в реализации алгоритма берлекампа с фиксированным количеством шагов. В частности, если мне не изменяет память, в книге "Кодирование с исправлением ошибок в системах связи" есть классическая реализация алгоритма берлекампа с делением, там есть анализ степени полинома, которая получилась.

ну и еще, если степень полинома локаторов меньше t, то гарантировано все будет ок.
это не к месту %)
des00
Цитата(des00 @ Mar 6 2012, 01:08) *
можно, но не в реализации алгоритма берлекампа с фиксированным количеством шагов. В частности, если мне не изменяет память, в книге "Кодирование с исправлением ошибок в системах связи" есть классическая реализация алгоритма берлекампа с делением, там есть анализ степени полинома, которая получилась.

а вот и тот алгоритм и статья . Кстати есть такая занятная вещь как "декодирование за границей БЧХ" никто не сталкивался ?
SKov
Цитата(des00 @ Mar 7 2012, 16:27) *
а вот и тот алгоритм и статья . Кстати есть такая занятная вещь как "декодирование за границей БЧХ" никто не сталкивался ?

Обычно рассматривается случай одной-двух дополнительных ошибок, не больше. Есть куча работ.
des00
Цитата(SKov @ Mar 7 2012, 07:21) *
Обычно рассматривается случай одной-двух дополнительных ошибок, не больше. Есть куча работ.

как раз такой случай мне и попался на глаза. код дополняется двумя символами которые декодируются за счет изменения берлекампа. сегодня еще рыл сеть, нашел пару статей об арифметическом декодировании кодов РС с мягким решением. Подробно не смотрел, отметил только что в них, РС указан как класс арифметических кодов.
Denisnovel
Делаю паралельную реализация поиска Ченя согласно прикрепленному файлу. Считает правильно, но результат сдвунут на 1. Т.е. 0 появляется раньше на одну позицию.
При начале поиска происходит инициализация. Если написать "start_root_index(i)-1" то с одной ошибкой работает, с двумя не работает совсем.
Код
loc_mult_par[i] <= gf_mult_a_by_b_const(iloc_poly[i], ALPHA_TO[start_root_index(i)-1]);

Что это может быть?
Mikhalych
Цитата(Denisnovel @ Mar 14 2012, 11:32) *
Делаю паралельную реализация поиска Ченя согласно прикрепленному файлу. Считает правильно, но результат сдвунут на 1.
Что это может быть?

Код неукороченный случаем?
Denisnovel
Код укороченный. Проблема где-то в инициализации
des00
Цитата(Denisnovel @ Mar 14 2012, 04:05) *
Код укороченный. Проблема где-то в инициализации

если код укороченный и начинаете перебор с элемента a^n, то нужно скорректировать инициализацию на a^(gf_n_max - n) нулей.
Denisnovel
Сейчас сделал так. Вроде работает. Буду тестировать.
Код
  function automatic data_t start_root_index(input int step);
    start_root_index = (step*(gf_n_max - n /*+ 1*/)) % gf_n_max;
  endfunction
Denisnovel
,,
mad_physicist
Господа, просвятите начинающего!
Задача стоит реализовать на языке MATLAB алгоритм Берлекемпа-Месси в декодере БЧХ. Алгоритм предусматривает использование компонент (элементов) синдрома, которые определяются как значения принятого слова (полинома) в нулях кода (в корнях порождающего многочлена). Мне непонятно, в какой форме должны находиться и использоваться в этой ситуации корни порождающего многочлена. Буду особенно благодарен за комментарии с примерами.

des00
Цитата(mad_physicist @ Mar 25 2012, 23:14) *
Буду особенно благодарен за комментарии с примерами.

что мешает найти в матлабе файлик rsdec.m или bchdec.m и посмотреть ?
mad_physicist
Цитата(des00 @ Mar 27 2012, 12:16) *
что мешает найти в матлабе файлик rsdec.m или bchdec.m и посмотреть ?


отсутствие уверенности в том, что там именно нужный мне алгоритм
Gold777
Цитата(mad_physicist @ Mar 26 2012, 09:14) *
Господа, просвятите начинающего!
Задача стоит реализовать на языке MATLAB алгоритм Берлекемпа-Месси в декодере БЧХ. Алгоритм предусматривает использование компонент (элементов) синдрома, которые определяются как значения принятого слова (полинома) в нулях кода (в корнях порождающего многочлена). Мне непонятно, в какой форме должны находиться и использоваться в этой ситуации корни порождающего многочлена. Буду особенно благодарен за комментарии с примерами.

Если хотите разобраться в алгоритме БМ, почитайте Морелос-Сарагоса - Искусство помехоустойчивого кодирования. Для алгоритма БМ нужны только компоненты синдромов. Компоненты синдромов рассчитываются с помощью элементов поля Галуа.
О чем вы спрашиваете мне не очень понятно ( Что значит в какой форме должны находиться и использоваться в этой ситуации корни порождающего многочлена?).
mad_physicist
Цитата(Gold777 @ Mar 28 2012, 18:15) *
Если хотите разобраться в алгоритме БМ, почитайте Морелос-Сарагоса - Искусство помехоустойчивого кодирования. Для алгоритма БМ нужны только компоненты синдромов. Компоненты синдромов рассчитываются с помощью элементов поля Галуа.
О чем вы спрашиваете мне не очень понятно ( Что значит в какой форме должны находиться и использоваться в этой ситуации корни порождающего многочлена?).

То, что я написал, основано именно на книге Морелоса-Сарагосы и статье С.В. Фёдорова о реализации БМ-алгоритма для РС-кодов на ПЛИС. Компоненты синдромов вычисляются путём подстановки корней порождающего полинома в полином принятого сообщения. Я пока не понимаю, как именно это должно происходить. То есть у меня имеется порождающий полином 14-й степени, нахождение его корней "в лоб", обычной арифметикой, даёт мне 14 комплексных корней. Я подозреваю, что такое решение не есть правильное, и необходимо использовать полиноминальную арифметику. Но каким образом это сделать я пока не знаю.
Попутно задам ещё один вопрос: подскажите, как связаны между собой компоненты синдрома, о которых говорилось выше, и синдромный полином?
des00
Цитата(mad_physicist @ Mar 27 2012, 20:38) *
отсутствие уверенности в том, что там именно нужный мне алгоритм

угу, а если учесть что обе эти функции ссылаются на функцию из файла berlekamp.m, то да, действительно никакой уверенности нет %)))
des00
Уважаемые гуру, подскажите что не так делаю.

Решил проверить работу декодера БЧХ со стираниям. Взял алгоритм из Скляра :
1. заместить стирания нулями
2. заместить стирания единицам
3. декодировать оба и выбрать то слово, которое соответствует наименьшему числу ошибок, исправленных вне позиций стирания.

Кол-во исправляемых стираний определяется по формуле p <= d-1. Набросал в матлабе простой пример. взял код {255, 131, 18}, с dmin = 37. Но не вижу исправления 36 стираний %(

Единственная разница алгоритма в Скляре и в примере в том, что в примере добавляются только стирания, по идее кол-во ошибок вне позиций стирания в обоих случаях должно быть одинаковым. Или я слишком упрощаю и в этом и есть моя ошибка ?

Спасибо.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.