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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.88
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
#1

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

17.11.2012, 02:46. Просмотров 2391. Ответов 2
Метки нет (Все метки)

Нужно реализовать алгоритм свёрточного кодирования и алгоритм декодирования на основе ММП.
Описание свёрточного алгоритма:
Для начала выбираем параметры кодирования. Они выбираются один раз и будут постоянными для всей программы.
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

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

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Помогите алгоритм для char переделать в алгоритм для float - C++
char* DecToBin(char x, char* str) { int i; for (i = sizeof(x)*8-1; i&gt;=0; i--) { str = (x&amp;1 == 1) ? '1' : '0'; x = x &gt;&gt;...

Волновой алгоритм (алгоритм Ли) - C++
Здравствуйте! У кого-нибудь есть реализованный волновой алгоритм (алгоритм Ли) ? Дело в том, что я игрушку захотел написать (что-то...

Сверточное кодирование. Алгоритм Витерби - Delphi
Никак не могу исправить ошибки в своей программе дипломного проекта. А сдавать уже очень скоро на следующей неделе а ошибок много. Помогите...

Декодер Витерби - Java SE
Доброе время суток! Интересует реализация алгоритма декодирования Витерби на Java. Нужно для курсовой работы. Благодарю =)

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
17.11.2012, 02:59 #2
k - это количество чисел, которые единовременно добавляются в ленту?
n - на что влияет, где используется?
большая ли таблица с функциями?
для ленты подойдет очередь. queue deque
1
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 минуту
и, кстати, таблица вводится вручную, т.е. без привлечения алгоритмов.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.11.2012, 03:19
Привет! Вот еще темы с ответами:

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм - Pascal
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм 1. Объясни, что будет напечатано программой Program...

Построить алгоритм Маркова, который ищет НОД (Алгоритм Евклида) - Алгоритмы
Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в чем, надо построить алгорифм Маркова,...

Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке [a,b] с шагом h. - Free Pascal
Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке с шагом h. Написать программу: F=3+tgx Мой...

Построить алгоритм ДО и алгоритм ПОКА дя вычислений значения функции на отрезке [а,b] с шагом h. Написать программу - Pascal
F=3+tg x


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru