>Evgeny Filatov <filatov.ev@mipt.ru> wrote:
>
>>M algorithm is briefly reviewed in Todd Moon, "Error Correction Coding:
>>Mathematical Methods and Algorithms".
>
>One good use of these reduced-complexity decoding algorithms is,
>in a packet-coded system you can try the reduced complexity algotithm,
>and if it results in a good CRC then you're done; if not, re-try
>with the full Viterbi algorithm.
>
>Way back sometime before 1995 I implemented such a system and,
>IIRC, described it in a MIL-STD (or at least a submission).
>
>Steve
FWIW, sequential decoding of one form or another (including the
M-algortihm) has been around for a long time (naturally). To be
honest I've not seen anything but the Viterbi algorithm suggested for
CP demodulation, though, and I suspect because of
complexity/performance tradeoff issues. Usually sequential decoding
requires a much longer constraint length to be effective compared to
Viterbi decoding.
Here's a paper from 1984 comparing various sequential decoders,
including the M-algorithm.
http://www2.ensc.sfu.ca/people/faculty/cavers/ENSC805/readings/32comm02-anderson.pdf
Also FWIW, back in my early satellite comm days much of our equipment
could be shipped with either a sequential decoder with a long
constraint length (e.g., k=37 IIRC), or a Viterbi decoder with k=7.
The sequential was an option and actually provided a bit more gain in
many circumstances, but overall once the Viterbi decoders got cheaper
sequentials fell out of favor. IIRC our sequential used the Fano
algorithm.
Reply by Steve Pope●July 6, 20172017-07-06
Evgeny Filatov <filatov.ev@mipt.ru> wrote:
>M algorithm is briefly reviewed in Todd Moon, "Error Correction Coding:
>Mathematical Methods and Algorithms".
One good use of these reduced-complexity decoding algorithms is,
in a packet-coded system you can try the reduced complexity algotithm,
and if it results in a good CRC then you're done; if not, re-try
with the full Viterbi algorithm.
Way back sometime before 1995 I implemented such a system and,
IIRC, described it in a MIL-STD (or at least a submission).
Steve
Reply by gct●July 5, 20172017-07-05
>gct <24505@DSPRelated> wrote:
>
>> spp wrote,
>
>>>You probably do not need a maximum likelyhood demodulator. You
>>>probably just need a standard discriminator type FM demodulator.
>>>You need to look at your specs, perhaps do some simulations and
determine
>
>>>whether you need something fancier, but I am guessing not, since such
>>>standards are aimed at cheaper implementations.
>
>>>h = 0.27 does not even sound like it is supposed to be coherent.
>
>>Yeah the modulation index throws me too, it'd be so easy to use .25 if
>>they wanted to make things easy. So you'd probably just use an FM
demod,
>>apply RRC filter, then try to discriminate the frequency in the middle
of
>>the symbol? Any idea how that compares to the "ideal" receiver?
>
>(Typically no RRC filter in such a system. Instead, use a DFE to
>subtract out the delay spread from the transmit filter and/or channel.)
>
>In AWGN, usually between 1 and 2 dB worse. It depends on the operating
>point, which depends on the amount of coding etc. If it is uncoded
>and you need to get a low BER like 1e-8 then the differences can
>be profound. But this is seldom the case in a real system.
>
>In multipath .. a bit hard to say. The degradation could be worse.
>
>Good luck-
>Steve
Curious why no RRC filter, wouldn't it make sense to apply it then use the
DFE to remove any extra ISI? Thanks for the help!
---------------------------------------
Posted through http://www.DSPRelated.com
Reply by gct●July 5, 20172017-07-05
>On 05.07.2017 2:53, gct wrote:
>>> On 04.07.2017 22:46, gct wrote:
>>>
>>> (snip)
>>>
>>>>
>>>> I surely did look it up, but they're doing a non-coherent detection,
>>> which
>>>> I was trying to avoid for performance reasons. You can see they're
at
>>>> least 1.7dB above the lower bound.
>>>> ---------------------------------------
>>>> Posted through http://www.DSPRelated.com
>>>>
>>>
>>> Apologies if I sounded too harsh; I've read that article, too.
>>>
>>> Just some thoughts (not from actual experience). Coherent detection
>>> doesn't have to mean Viterbi decoder. What about M-algorithm? Perhaps
>>> you could do better than non-coherent detection without too much
>>> complexity.
>>>
>>> Best regards,
>>> Gene
>>
>> No worries, I haven't heard of the M-algorithm, do you have any good
>> references I could look at?
>> ---------------------------------------
>> Posted through http://www.DSPRelated.com
>>
>
>M algorithm is briefly reviewed in Todd Moon, "Error Correction Coding:
>Mathematical Methods and Algorithms".
>
>Its description is actually so short that I could just quote it here.
>For fun's sake, here's what the text says (pp. 521-522):
>
>-----------------------------------------
>
>12.8.6 A Variation on the Viterbi Algorithm: the M Algorithm
>
>For a trellis with a large number of states at each time instant, the
>Viterbi algorithm can be very complex. Furthermore, since there is only
>one correct path, most of the computations are expended in propagating
>paths that are not be used, but must be maintained to ensure the
>optimality of the decoding procedure. The M algorithm (see, e.g., [270])
>is a suboptimal, breadth-first decoding algorithm whose complexity is
>parametric, allowing for more complexity in the decoding algorithm while
>decoding generally closer to the optimum.
>
>A list of M paths is maintained. At each time step, these M paths are
>extended to M*2^k paths (where k is the number of input bits), and the
>path metric along each of these paths is computed just as for the
>Viterbi algorithm. The path metrics are sorted, then the best M paths
>are retained in preparation for the next step. At the end of the
>decoding cycle, the path with the best metric is used as the decoded
>value. While the underlying graphical structure for the Viterbi
>algorithm is a trellis, in which paths merge together, the underlying
>graphical structure for the M algorithm is a tree: the merging of paths
>is not explicitly represented, but better paths are retained by virtue
>of the sorting operation. The M-algorithm is thus a cross between the
>stack algorithm (but using all paths of the same length) and the Viterbi
>algorithm. If M is equal to the number of states, the M algorithm is
>nearly equivalent to the Viterbi algorithm. However, it is possible for
>M to be significantly less than the number of states with only modest
>loss of performance.
>
>Another variation is the T-algorithm. It starts just like the M
>algorithm. However, instead of retaining only the best M paths, in the T
>algorithm all paths which are within a threshold T of the best path at
>that stage are retained.
>
>-----------------------------------------
>
>[270]: G. Pottie and D. Taylor, "A Comparison of Reduced Complexity
>Decoding Algorithms for Trellis Codes," IEEE Journal on Selected Areas
>in Communications, vol. 7, no. 9, pp. 1369-1380, 1989.
>
>-----------------------------------------
>
>If you follow the link, it would say something along the lines that
>M-algorithm is global, while Viterbi algorithm is local. Which makes
>some sense to me.
>
>Best regards,
>Gene
Excellent references, thank you! Will take a look at this.
---------------------------------------
Posted through http://www.DSPRelated.com
Reply by Evgeny Filatov●July 5, 20172017-07-05
On 05.07.2017 2:53, gct wrote:
>> On 04.07.2017 22:46, gct wrote:
>>
>> (snip)
>>
>>>
>>> I surely did look it up, but they're doing a non-coherent detection,
>> which
>>> I was trying to avoid for performance reasons. You can see they're at
>>> least 1.7dB above the lower bound.
>>> ---------------------------------------
>>> Posted through http://www.DSPRelated.com
>>>
>>
>> Apologies if I sounded too harsh; I've read that article, too.
>>
>> Just some thoughts (not from actual experience). Coherent detection
>> doesn't have to mean Viterbi decoder. What about M-algorithm? Perhaps
>> you could do better than non-coherent detection without too much
>> complexity.
>>
>> Best regards,
>> Gene
>
> No worries, I haven't heard of the M-algorithm, do you have any good
> references I could look at?
> ---------------------------------------
> Posted through http://www.DSPRelated.com
>
M algorithm is briefly reviewed in Todd Moon, "Error Correction Coding:
Mathematical Methods and Algorithms".
Its description is actually so short that I could just quote it here.
For fun's sake, here's what the text says (pp. 521-522):
-----------------------------------------
12.8.6 A Variation on the Viterbi Algorithm: the M Algorithm
For a trellis with a large number of states at each time instant, the
Viterbi algorithm can be very complex. Furthermore, since there is only
one correct path, most of the computations are expended in propagating
paths that are not be used, but must be maintained to ensure the
optimality of the decoding procedure. The M algorithm (see, e.g., [270])
is a suboptimal, breadth-first decoding algorithm whose complexity is
parametric, allowing for more complexity in the decoding algorithm while
decoding generally closer to the optimum.
A list of M paths is maintained. At each time step, these M paths are
extended to M*2^k paths (where k is the number of input bits), and the
path metric along each of these paths is computed just as for the
Viterbi algorithm. The path metrics are sorted, then the best M paths
are retained in preparation for the next step. At the end of the
decoding cycle, the path with the best metric is used as the decoded
value. While the underlying graphical structure for the Viterbi
algorithm is a trellis, in which paths merge together, the underlying
graphical structure for the M algorithm is a tree: the merging of paths
is not explicitly represented, but better paths are retained by virtue
of the sorting operation. The M-algorithm is thus a cross between the
stack algorithm (but using all paths of the same length) and the Viterbi
algorithm. If M is equal to the number of states, the M algorithm is
nearly equivalent to the Viterbi algorithm. However, it is possible for
M to be significantly less than the number of states with only modest
loss of performance.
Another variation is the T-algorithm. It starts just like the M
algorithm. However, instead of retaining only the best M paths, in the T
algorithm all paths which are within a threshold T of the best path at
that stage are retained.
-----------------------------------------
[270]: G. Pottie and D. Taylor, "A Comparison of Reduced Complexity
Decoding Algorithms for Trellis Codes," IEEE Journal on Selected Areas
in Communications, vol. 7, no. 9, pp. 1369-1380, 1989.
-----------------------------------------
If you follow the link, it would say something along the lines that
M-algorithm is global, while Viterbi algorithm is local. Which makes
some sense to me.
Best regards,
Gene
Reply by Steve Pope●July 5, 20172017-07-05
gct <24505@DSPRelated> wrote:
> spp wrote,
>>You probably do not need a maximum likelyhood demodulator. You
>>probably just need a standard discriminator type FM demodulator.
>>You need to look at your specs, perhaps do some simulations and determine
>>whether you need something fancier, but I am guessing not, since such
>>standards are aimed at cheaper implementations.
>>h = 0.27 does not even sound like it is supposed to be coherent.
>Yeah the modulation index throws me too, it'd be so easy to use .25 if
>they wanted to make things easy. So you'd probably just use an FM demod,
>apply RRC filter, then try to discriminate the frequency in the middle of
>the symbol? Any idea how that compares to the "ideal" receiver?
(Typically no RRC filter in such a system. Instead, use a DFE to
subtract out the delay spread from the transmit filter and/or channel.)
In AWGN, usually between 1 and 2 dB worse. It depends on the operating
point, which depends on the amount of coding etc. If it is uncoded
and you need to get a low BER like 1e-8 then the differences can
be profound. But this is seldom the case in a real system.
In multipath .. a bit hard to say. The degradation could be worse.
Good luck-
Steve
Reply by gct●July 4, 20172017-07-04
>On 04.07.2017 22:46, gct wrote:
>
>(snip)
>
>>
>> I surely did look it up, but they're doing a non-coherent detection,
>which
>> I was trying to avoid for performance reasons. You can see they're at
>> least 1.7dB above the lower bound.
>> ---------------------------------------
>> Posted through http://www.DSPRelated.com
>>
>
>Apologies if I sounded too harsh; I've read that article, too.
>
>Just some thoughts (not from actual experience). Coherent detection
>doesn't have to mean Viterbi decoder. What about M-algorithm? Perhaps
>you could do better than non-coherent detection without too much
>complexity.
>
>Best regards,
>Gene
No worries, I haven't heard of the M-algorithm, do you have any good
references I could look at?
---------------------------------------
Posted through http://www.DSPRelated.com
Reply by Evgeny Filatov●July 4, 20172017-07-04
On 04.07.2017 22:46, gct wrote:
(snip)
>
> I surely did look it up, but they're doing a non-coherent detection, which
> I was trying to avoid for performance reasons. You can see they're at
> least 1.7dB above the lower bound.
> ---------------------------------------
> Posted through http://www.DSPRelated.com
>
Apologies if I sounded too harsh; I've read that article, too.
Just some thoughts (not from actual experience). Coherent detection
doesn't have to mean Viterbi decoder. What about M-algorithm? Perhaps
you could do better than non-coherent detection without too much complexity.
Best regards,
Gene
Reply by gct●July 4, 20172017-07-04
>On 04.07.2017 7:29, Steve Pope wrote:
>> gct <24505@DSPRelated> wrote:
>>
>>> I'm evaluating receiver structures for the ETSI DMR spec, but not
having
>>> much luck finding any work in this area. They use continuous phase
>>> modulation, so I anticipate I'll have to use a viterbi demodulator to
>get
>>> it done. Unfortunately they choose h=.27, so I have at least 200
>states,
>>> times whatever number of symbol cycles their pulse shape is over (not
>>> clear on this, three maybe?). So I'm looking at 600*4 = 2400 matched
>>> filters I have to evaluate per symbol to get branch metrics for the
>>> viterbi, woof.
>>
>>> If anyone can point me to revelant work I'd appreciate it
>>
>> You probably do not need a maximum likelyhood demodulator. You
>> probably just need a standard discriminator type FM demodulator.
>> You need to look at your specs, perhaps do some simulations and
determine
>> whether you need something fancier, but I am guessing not, since such
>> standards are aimed at cheaper implementations.
>>
>> h = 0.27 does not even sound like it is supposed to be coherent.
>>
>> Steve
>>
>
>Gct, as for the relevant work, you've surely looked up the first link in
I surely did look it up, but they're doing a non-coherent detection, which
I was trying to avoid for performance reasons. You can see they're at
least 1.7dB above the lower bound.
---------------------------------------
Posted through http://www.DSPRelated.com
Reply by gct●July 4, 20172017-07-04
>gct <24505@DSPRelated> wrote:
>
>>I'm evaluating receiver structures for the ETSI DMR spec, but not
having
>>much luck finding any work in this area. They use continuous phase
>>modulation, so I anticipate I'll have to use a viterbi demodulator to
get
>>it done. Unfortunately they choose h=.27, so I have at least 200
states,
>>times whatever number of symbol cycles their pulse shape is over (not
>>clear on this, three maybe?). So I'm looking at 600*4 = 2400 matched
>>filters I have to evaluate per symbol to get branch metrics for the
>>viterbi, woof.
>
>>If anyone can point me to revelant work I'd appreciate it
>
>You probably do not need a maximum likelyhood demodulator. You
>probably just need a standard discriminator type FM demodulator.
>You need to look at your specs, perhaps do some simulations and determine
>whether you need something fancier, but I am guessing not, since such
>standards are aimed at cheaper implementations.
>
>h = 0.27 does not even sound like it is supposed to be coherent.
>
>Steve
Yeah the modulation index throws me too, it'd be so easy to use .25 if
they wanted to make things easy. So you'd probably just use an FM demod,
apply RRC filter, then try to discriminate the frequency in the middle of
the symbol? Any idea how that compares to the "ideal" receiver?
---------------------------------------
Posted through http://www.DSPRelated.com