Viterbi C++ Source Code

C, C++, Visual C++, C++.Net Topics
Post Reply
User avatar
Shane
Captain
Captain
Posts: 226
Joined: Sun Jul 19, 2009 9:59 pm
Location: Jönköping, Sweden

Viterbi C++ Source Code

Post by Shane » Thu Nov 26, 2009 12:37 am

The Viterbi algorithm operates on a state machine assumption. That is, at any time the system being modelled is in some state. There are a finite number of states, however large. Multiple sequences of states (paths) can lead to a given state, but one is the most likely path to that state, called the "survivor path". This is a fundamental assumption of the algorithm because the algorithm will examine all possible paths leading to a state and only keep the one most likely. This way the algorithm does not have to keep track of all possible paths, only one per state.

A second key assumption is that a transition from a previous state to a new state is marked by an incremental metric, usually a number. This transition is computed from the event. The third key assumption is that the events are cumulative over a path in some sense, usually additive. So the crux of the algorithm is to keep a number for each state. When an event occurs, the algorithm examines moving forward to a new set of states by combining the metric of a possible previous state with the incremental metric of the transition due to the event and chooses the best. The incremental metric associated with an event depends on the transition possibility from the old state to the new state. For example in data communications, it may be possible to only transmit half the symbols from an odd numbered state and the other half from an even numbered state. Additionally, in many cases the state transition graph is not fully connected. A simple example is a car that has 3 states — forward, stop and reverse — and a transition from forward to reverse is not allowed. It must first enter the stop state. After computing the combinations of incremental metric and state metric, only the best survives and all other paths are discarded. There are modifications to the basic algorithm which allow for a forward search in addition to the backwards one described here.

Path history must be stored. In some cases, the search history is complete because the state machine at the encoder starts in a known state and there is sufficient memory to keep all the paths. In other cases, a programmatic solution must be found for limited resources: one example is convolutional encoding, where the decoder must truncate the history at a depth large enough to keep performance to an acceptable level. Although the Viterbi algorithm is very efficient and there are modifications that reduce the computational load, the memory requirements tend to remain constant.

Have a look at https://robot.lk/viewtopic.php?f=17&p=937 for detailed explanation.

CPP file
viterbi.cpp
(4.73 KiB) Downloaded 5504 times
Header file
viterbi.h
(1.85 KiB) Downloaded 3534 times
Common Header file
common.h
(1.57 KiB) Downloaded 2963 times
User avatar
unmanner
Posts: 1
Joined: Sun Apr 08, 2012 10:41 pm

Re: Viterbi C++ Source Code

Post by unmanner » Sun Apr 08, 2012 10:43 pm

Hi Shane,

Many thanks for you implementation!

Could you please provide simple example, how to use?
User avatar
jamess86607
Posts: 1
Joined: Fri Sep 20, 2013 12:23 am

c programming

Post by jamess86607 » Fri Sep 20, 2013 12:24 am

hello everyone
welcome to this forum.Here u find all your questions and get your answers.
right now i am unable to find your answer.If you want to see c programming you can go through this.
Post Reply

Return to “C/C++ Programming”