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

Алгоритм Витерби - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.88
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
17.11.2012, 02:46     Алгоритм Витерби #1
Нужно реализовать алгоритм свёрточного кодирования и алгоритм декодирования на основе ММП.
Описание свёрточного алгоритма:
Для начала выбираем параметры кодирования. Они выбираются один раз и будут постоянными для всей программы.
http://www.cyberforum.ru/cgi-bin/latex.cgi?k - количество бит в сообщении, которое передаётся на регистр;
http://www.cyberforum.ru/cgi-bin/latex.cgi?n - количество бит в закодированном сообщении (http://www.cyberforum.ru/cgi-bin/latex.cgi?k<n);
http://www.cyberforum.ru/cgi-bin/latex.cgi?K - длина регистра;
http://www.cyberforum.ru/cgi-bin/latex.cgi?g:\{0,1\}^K\to \{0,1\}^n, g=g(k,n,K) - функция кодирования (которая зависит от предыдущих параметров);
http://www.cyberforum.ru/cgi-bin/latex.cgi?m\in \{0,1\}^N,m=m_1m_2...m_N - кодовое сообщение (http://www.cyberforum.ru/cgi-bin/latex.cgi?N может быть сколь угодно большим).
Суть метода (на пальцах):
для простоты положим http://www.cyberforum.ru/cgi-bin/latex.cgi?k=1, n=2, K=3. Тогда http://www.cyberforum.ru/cgi-bin/latex.cgi?g(x_1,x_2,x_3)=((x_1+x_2+x_3) mod 2,(x_1+x_3) mod 2) (функцию http://www.cyberforum.ru/cgi-bin/latex.cgi?g мы выбираем из таблички). Представим, что у нас есть лента длиной http://www.cyberforum.ru/cgi-bin/latex.cgi?K=3, заполненная нулями. Тогда http://www.cyberforum.ru/cgi-bin/latex.cgi?g(0,0,0)=(0+0+0,0+0)=(0,0). Далее мы берём первый символ нашего сообщения и "вталкиваем" его в начало ленты, а последний символ этой ленты "выталкиваем". Затем считаем http://www.cyberforum.ru/cgi-bin/latex.cgi?g(m_1,0,0)=(m_1,m_1) и проделываем эти шаги, пока не закончится сообщение. В конце "искуственно" вставляем нули до тех пор, пока вся лента не станет нулевой (вернётся в первоначальное состояние). Например, дано сообщение http://www.cyberforum.ru/cgi-bin/latex.cgi?1101. Тогда http://www.cyberforum.ru/cgi-bin/latex.cgi?g(1,0,0)=(1,1), g(1,1,0)=(0,1), g(0,1,1)=(0,1), g(1,0,1)=(0,0), g(0,1,0)=(1,0), g(0,0,1)=(1,1) (при следующей "вставе" получим нулевую последовательность). Таким образом мы закодировали http://www.cyberforum.ru/cgi-bin/latex.cgi?1101 как http://www.cyberforum.ru/cgi-bin/latex.cgi?11 01 01 00 10 11

Помогите, пожалуйста, с архитектурой, т.е. какой контейнер использовать для реализации, какие методы и т.п. Спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2012, 02:46     Алгоритм Витерби
Посмотрите здесь:

Волновой алгоритм (алгоритм Ли) C++
с++ алгоритм C++
алгоритм C++
C++ Алгоритм
Помогите алгоритм для char переделать в алгоритм для float C++
C++ QR алгоритм
C++ Алгоритм
C++ алгоритм бм

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
17.11.2012, 02:59     Алгоритм Витерби #2
k - это количество чисел, которые единовременно добавляются в ленту?
n - на что влияет, где используется?
большая ли таблица с функциями?
для ленты подойдет очередь. queue deque
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
17.11.2012, 03:19  [ТС]     Алгоритм Витерби #3
1. да
2. http://www.cyberforum.ru/cgi-bin/latex.cgi?g:\{0,1\}^K\to \{0,1\}^n, т.е. оно показывает во сколько символов превращается строка.
3. таблица имеет вид типа следующего:
k n K g
1 2 3 111, 101
1 2 4 1111,1011
1 2 5 10111, 11001
...
1 3 3 111,111,101
1 3 4 1111,1011,1101
...
где в последней строке указана 1, если бит на этой позиции участвует в сумме и 0, если не участвует. Например при 10111,11001 выполнено http://www.cyberforum.ru/cgi-bin/latex.cgi?g(x_1,x_2,...,x_5)=(x_1+x_3+x_4+x_5, x_1+x_2+x_5) (всё по модулю 2).

Добавлено через 1 минуту
и, кстати, таблица вводится вручную, т.е. без привлечения алгоритмов.
Yandex
Объявления
17.11.2012, 03:19     Алгоритм Витерби
Ответ Создать тему
Опции темы

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