Jump to content

    
Sign in to follow this  
TamRazZ

Декодирование кодов Рида-Соломона

Recommended Posts

Доброго времени суток.!

 

Знаю, подобная тема многократно обсуждалась на просторах этого портала. Но ответа на некоторые вопросы я так и не нашел...

 

Мой первый вопрос касается процедуры Ченя:

Как выполняется данный алгоритм для укороченных кодов.?

Я использую код (127, 120) над полем GF(2^8). Согласно процедуре Ченя мы перебираем все возможные примитивные элементы поля и подставляем в найденный нами полином локаторов ошибок. Все примитивные элементы a^x которые обнуляют наш полином являются его корнями. Соответственно, степень примитивного элемента (в нашем случае x) я вляется позицией, на которой произошла ошибка. Так я понял теорию, не понятно, что делать, если у меня коды укороченные и всего 127 позиций на посылку РС а корень полинома, скажем равен a^220. .?

 

Мой второй вопрос относится к алгоритму Берлекэмпа-Месси.

Я вычитал в интернете, что наиболее эффективный и оптимальный при реализации на ПЛИС алгоритм нахождения полинома локаторов это модификация алгоритма БМ известная как RiBM. Кто-нибудь реализовывал этот алгоритм.? Дайте, пожалуйста ссылку, где можно найти подробное описание этого алгоритма, сам пока не нашел...

Share this post


Link to post
Share on other sites
все кого знаю готовые ядра используют.

 

Да, но это стоит денег, к тому же у меня там еще свои навороты ожидаются... так что придется самому писать, да вот что-то пока не выходит каменный цветок..(

Share this post


Link to post
Share on other sites
не понятно, что делать, если у меня коды укороченные и всего 127 позиций на посылку РС а корень полинома, скажем равен a^220. .?

ну как бы добить нулями и стартануть алгоритм с нужной точки ?

 

Я вычитал в интернете, что наиболее эффективный и оптимальный при реализации на ПЛИС алгоритм нахождения полинома локаторов это модификация алгоритма БМ известная как RiBM. Кто-нибудь реализовывал этот алгоритм.? Дайте, пожалуйста ссылку, где можно найти подробное описание этого алгоритма, сам пока не нашел...

на этом форуме выкладывал статически конфигурируемый РС кодер (в том числе и для укороченных кодов и со стираниями), в котором есть в том числе и RiBM реализация. на декодирование уходит check тактов. Ищите, где то тут лежит на SV

 

Share this post


Link to post
Share on other sites
на этом форуме выкладывал статически конфигурируемый РС кодер (в том числе и для укороченных кодов и со стираниями), в котором есть в том числе и RiBM реализация. на декодирование уходит check тактов. Ищите, где то тут лежит на SV

 

А можете посоветовать, где почитать словесное описание этого алгоритма.?

 

Share this post


Link to post
Share on other sites
А можете посоветовать, где почитать словесное описание этого алгоритма.?

в той теме, статьи тоже были выложены. найдите статью

High-Speed Architectures for Reed-Solomon Decoders Dilip V. Sarwate, Fellow, IEEE, and Naresh R. Shanbhag. Member. IEEE там есть все

Share this post


Link to post
Share on other sites
ну как бы добить нулями и стартануть алгоритм с нужной точки ?

 

Похоже я вообще не правильно воспринял алгоритм декодирования укороченных кодов... Т.е. даже если я имею укороченный код с N=127 я должен его добить нулями до 255 и прогнать БМА по стандартной программе для обычных кодов.?

Share this post


Link to post
Share on other sites
Похоже я вообще не правильно воспринял алгоритм декодирования укороченных кодов... Т.е. даже если я имею укороченный код с N=127 я должен его добить нулями до 255 и прогнать БМА по стандартной программе для обычных кодов.?

Нет, зачем же. Ведь вы добиваете нулями сверху. Соответственно результат прогона 128 нулей (255-127) будет давать всегда один и тот же результат. Так зачем его каждый раз просчитывать, можно сразу установить регистры в нужное состояние, как после 128 нулей и оставшиеся 127 прогонять уже последовательно.

 

Share this post


Link to post
Share on other sites

Использую следующий алгоритм для поиска полинома локаторов:

 

da04ab6ef4df78bdbecef5f29c00806c.png

 

Возник вопрос...

Судя по последней строке псевдокода, функция всегда будет возвращать вектор размером t вне зависимости от кол-ва случившихся ошибок, следовательно в случае, когда ошибок > t вернется полином степени не больше t, а значит Чень сможет найти корней не больше t.

Как в такой ситуации оценить, сможет декодер восстановить данный пакет или нет.?

Share this post


Link to post
Share on other sites
Использую следующий алгоритм для поиска полинома локаторов:

 

Возник вопрос...

Судя по последней строке псевдокода, функция всегда будет возвращать вектор размером t вне зависимости от кол-ва случившихся ошибок, следовательно в случае, когда ошибок > t вернется полином степени не больше t, а значит Чень сможет найти корней не больше t.

Как в такой ситуации оценить, сможет декодер восстановить данный пакет или нет.?

Если повезет и ошибка будет обнаружимой то в процедуре Ченя будет найдено ошибок меньше, чем степень полинома. Только так.

Share this post


Link to post
Share on other sites
Если повезет и ошибка будет обнаружимой то в процедуре Ченя будет найдено ошибок меньше, чем степень полинома. Только так.

 

Насколько я понял, степень полинома у нас всегда t. Как же отличить ситуацию, когда произошло ошибок <t и когда >t, если и в том и в другом случае Чень найдет корней меньше t

Share this post


Link to post
Share on other sites
Насколько я понял, степень полинома у нас всегда t. Как же отличить ситуацию, когда произошло ошибок <t и когда >t, если и в том и в другом случае Чень найдет корней меньше t

никак. одно кодовое слово, заменилось на другое кодовое слово.

 

ЗЫ. тема кстати обсуждалась на форуме многократно

Share this post


Link to post
Share on other sites
никак. одно кодовое слово, заменилось на другое кодовое слово.

 

ЗЫ. тема кстати обсуждалась на форуме многократно

 

Странный какой-то алгоритм, в классическом БМ декодер четко определяет может он декодировать принятую комбинацию или нет, а тут получается неизвестно восстановлена последовательность или нет..(

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this