Jump to content

    

Декодер Витерби

Здравствуйте.

Написал декодер для сверточного кода памяти 2 и скорости 1/2 (5,7) на языке си. Руководитель поставил под сомнение правильность реализации. Поэтому прошу вас по возможности проверить.

Сам пока не разобрался в двух моментах:

1. Нормализация метрик. В литературе приводится метод: "На каждом шаге декодирования значение наименьшей метрики пути сравнивается с порогом Т. Если Мmin > T, то величина Т вычитается из всех накопленных метрик." Можно ли на каждом шаге из всех метрик вычитать минимальную метрику?

2. Выбор из одинаковых метрик. Из литературы: "В этом случае можно просто бросить монетку." Не будет ли тогда ошибкой жесткий выбор (например, если М1 = М2, то всегда выбираем М1) ?

Может, ещё что упустил.

Viterbi.zip

Share this post


Link to post
Share on other sites
50 минут назад, Michael358 сказал:

Руководитель поставил под сомнение правильность реализации.

BER не понравился?

Share this post


Link to post
Share on other sites
6 minutes ago, coding4dsp said:

BER не понравился? 

Да.

Кстати, сказал расписать исправляющую способность декодера (какие комбинации ошибочных бит исправляет).

С этим тоже пока не могу разобраться. Из литературы: "минимальное расстояние между всеми путями решётки, называемое иногда свободным расстоянием кода, в данном случае равно 5. Это означает, что любая пара ошибок может быть исправлена..." А в каком промежутке(2 ошибки на сколько бит)?

Share this post


Link to post
Share on other sites

А вам BER нравится? Сравнивали с эталоном из матлабовского bertool, например? Методом нормализации целочисленных метрик много: вычитание на каждом шаге минимальной, по модулю-2 и пр. Без нормальзации метрик BER становится правильным?

Share this post


Link to post
Share on other sites
18 minutes ago, coding4dsp said:

А вам BER нравится? Сравнивали с эталоном из матлабовского bertool, например? Методом нормализации целочисленных метрик много: вычитание на каждом шаге минимальной, по модулю-2 и пр. Без нормальзации метрик BER становится правильным?

Не сравнивал. С матлабом дел не имел. Не могу разобраться, как оценить BER своего декодера.

Share this post


Link to post
Share on other sites
8 минут назад, Michael358 сказал:

Не сравнивал. С матлабом дел не имел. Не могу разобраться, как оценить BER своего декодера.

https://www.mathworks.com/help/comm/ug/estimate-ber-for-hard-and-soft-decision-viterbi-decoding.html

Качайте, матлаб!

Share this post


Link to post
Share on other sites
5 minutes ago, coding4dsp said:

Придётся. Спасибо.

А как правильно оценить работу своего декодера(с чем сравнивать матлабовские результаты)?

Share this post


Link to post
Share on other sites

По bit error ratio (BER). Если ваш декодер правильно реализован, то графики BER совпадут с матлабовскими.

Share this post


Link to post
Share on other sites
8 minutes ago, coding4dsp said:

По bit error ratio (BER). Если ваш декодер правильно реализован, то графики BER совпадут с матлабовскими.

Т.е. сообразить функцию моделирования шума для своего декодера и посчитать количество ошибок?

Share this post


Link to post
Share on other sites

Не разберусь, как правильно нормализовывать метрики.
Допустим, всегда передаются нули. Тогда метрика нулевого состояния декодера всегда будет равна нулю, а остальные метрики будут постоянно увеличиваться. И если вычитать минимальную метрику (т.е. ноль) из всех, то переполнения метрик не избежать.

Share this post


Link to post
Share on other sites

Michael358

Не разберусь, как правильно нормализовывать метрики.
Допустим, всегда передаются нули. Тогда метрика нулевого состояния декодера всегда будет равна нулю, а остальные метрики будут постоянно увеличиваться. И если вычитать минимальную метрику (т.е. ноль) из всех, то переполнения метрик не избежать.

Можно накапливать метрики путей с коэффициентом меньше, но близким к 1. Разница буквально такая же, как между интегратором и ФНЧ на постоянной составляющей, интегратор имеет бесконечный коэффициент передачи на нулевой частоте, ФНЧ конечный, и переполнений можно избежать.

Share this post


Link to post
Share on other sites
2 hours ago, Michael358 said:

Не разберусь, как правильно нормализовывать метрики.
Допустим, всегда передаются нули. Тогда метрика нулевого состояния декодера всегда будет равна нулю, а остальные метрики будут постоянно увеличиваться. И если вычитать минимальную метрику (т.е. ноль) из всех, то переполнения метрик не избежать.

вы теплое с мягким не путаете? выбираются наиболее вероятные метрики. Для жесткого кодера, это минимальная метрика, для мягкого максимальная. При этом всегда идет сравнение двух и выбор наиболее вероятной. У вас не будет подобной ситуации. 

ЗЫ. Вычитание минимальной это не для настоящих пацанов. Для настоящих пацанов модульная арифметика. Хотя на проце, вычитать наверное проще

Share this post


Link to post
Share on other sites
2 hours ago, des00 said:

вы теплое с мягким не путаете? выбираются наиболее вероятные метрики. Для жесткого кодера, это минимальная метрика, для мягкого максимальная. При этом всегда идет сравнение двух и выбор наиболее вероятной. У вас не будет подобной ситуации. 

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

Share this post


Link to post
Share on other sites
18 hours ago, Michael358 said:

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

Вы руками решётку распишите на длину кодового ограничения. С чего она переполнится? У вас пути сольются, как кодовое ограничение будет, а потом останутся только пути с разницей на длинну кодового ограничения. 

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

Ручка, бумага и распишите решётки 3,5,7. Сами все увидите

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this