In the Viterbi algorithm (trellis state diagram,) I wonder why the number of inputs to each state is the same and equals the input alphabet size.
1 Answer
\$\begingroup\$
\$\endgroup\$
14
the number of inputs to each state is the same and equals the input alphabet size.
This isn't the case. The claim is incorrect. For example, you know that the number of inputs to a node close to termination must be different.
It's not true for trellises of codes designed without the goal that each stage should have the same number of states. And you would only want that if you transported the same mutual information at every transmission step. That might, for example, not be the case in an inner/outer (concatenated) coding scheme.
So, but restricting ourselves to the "entry-level" textbook question that you're trying to get help with here (assumptions apply¹):
- We demand that every state has as many output edges as there's symbols in the alphabet – otherwise we couldn't send every symbol at every point
- We demand that every symbol is equally likely at every point in time – otherwise our source coding was shite
- From 1. and 2. follows that every state must have an equal number of inputs, since otherwise states would have different probabilities of occurring, which would be bad, because that means they would carry different amounts of information, which would be bad, because we know that the distribution that transports the maximum information is the equidistribution.
Assuming a constant state machine (i.e., Markov), the number of states every step is constant. If I have \$N_{\text{states}}\cdot|\mathcal A|\$ output edges per time step, and the next time step needs to connect these in an equal manner to \$N_{\text{states}}\$, the only manner in which you can divide "fairly" is giving every state \$|\mathcal A|\$ inputs.
¹ Assumptions:
- ergodic equiprobably discrete product source
- finite memory length code
- code specifically designed for symmetricity, which is not a given – design complexity constraints might have went with a somewhat asymmetric code
-
\$\begingroup\$ Thanks! I am involved in CPM and its trellis states. Now, is the claim OK? \$\endgroup\$– AliCommented 7 hours ago
-
1\$\begingroup\$ depends; can't tell you. This is mostly down to your specific channel model, and the fact that you're working on CPM in 2024 means you're probably elbow-deep in the specifics of your channel model justifying CPM. So, my suspicion is that if it was justified, you'd just use a classical linear modulation and not CPM (general CPM, not some linear corner cases like GMSK). But this is just a guess. It's up to you to come clear how you end up with a FSM model to be able to use Viterbi at all, and I don't know your assumptions nor your model. \$\endgroup\$ Commented 7 hours ago
-
\$\begingroup\$ In mobile comm when both power and bw are the concern, general CPM works well! You can take a look at these: 1- Anderson et. al, Digital Phase Modulation, 1986, p.113. 2- Xiong, Digital Modulation Techniques, 2ed, 2006, p.285. \$\endgroup\$– AliCommented 7 hours ago
-
1\$\begingroup\$ Funilly, I've discussed something GMSK-related based on your 1. book with a colleague on Friday. However, citing a 1986 book for "modern communications" isn't very good an argument. CPM techniques can often be shown to stay pretty far away from Shannon limits, so that since that books doesn't address the spectral /error efficiency of CPM in comparison with modern high-dimensional mods, \$\endgroup\$ Commented 7 hours ago
-
1\$\begingroup\$ I'll refrain from contradicting you on that; quite contrary, Fig. 5.15 struck me as pretty interesting. But then again, especially in the high-E_b/N_0 region, it's kind of questionable that the only non-CPM benchmark to compare against is a QPSK. At least higher-order classical PSKs should be considered (and if we don't demand the constant-envelope properties, we do have much higher-rate linear mods anyways). \$\endgroup\$ Commented 7 hours ago