Forums

Reed-Solomon M-ary code -- what about near-misses?

Started by Tim Wescott August 5, 2016
I don't know if this is a dumb-ass question or not.

Let's say I have a physical layer that deals in M-ary symbols -- say 8-
ary.

And let's say that if a '4' is received, the most likely word to have 
been transmitted is a 4, followed by 3 and 5, followed by 2 and 6, etc.

Now -- if I'm decoding this with a Reed-Solomon decoder with hard 
decisions, does it make use of this "closer is better" property, or does 
it only "understand" that a word is in error?

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

I'm looking for work -- see my website!
On Fri, 05 Aug 2016 16:43:21 -0500, Tim Wescott
<seemywebsite@myfooter.really> wrote:

>I don't know if this is a dumb-ass question or not. > >Let's say I have a physical layer that deals in M-ary symbols -- say 8- >ary. > >And let's say that if a '4' is received, the most likely word to have >been transmitted is a 4, followed by 3 and 5, followed by 2 and 6, etc. > >Now -- if I'm decoding this with a Reed-Solomon decoder with hard >decisions, does it make use of this "closer is better" property, or does >it only "understand" that a word is in error?
If the 2, 3, 4, 5, 6 are symbols from the alphabet, then it doesn't matter, i.e., a symbol error is a symbol error. e.g., the typical RS codes use 8-bit symbols. An errored symbol can have one-, two-, three- or any number of bit errors and not affect the correction performance. In other words, a symbol error is a symbol error. It doesn't matter how many bits are wrong in the symbol. If you want the gnarliest of details, summon Prof. Sarwate out of retirement. I don't know if he reads stuff here any more or not.
Eric Jacobsen <eric.jacobsen@ieee.org> wrote:

>On Fri, 05 Aug 2016 16:43:21 -0500, Tim Wescott
>>Now -- if I'm decoding this with a Reed-Solomon decoder with hard >>decisions, does it make use of this "closer is better" property, or does >>it only "understand" that a word is in error?
>If the 2, 3, 4, 5, 6 are symbols from the alphabet, then it doesn't >matter, i.e., a symbol error is a symbol error. e.g., the typical >RS codes use 8-bit symbols. An errored symbol can have one-, two-, >three- or any number of bit errors and not affect the correction >performance. In other words, a symbol error is a symbol error. It >doesn't matter how many bits are wrong in the symbol.
Yep
>If you want the gnarliest of details, summon Prof. Sarwate out of >retirement. I don't know if he reads stuff here any more or not.
That's interesting, most people spend more time on the newsgroup after retirement, not less. :-) Back to the question, a number of researchers have figured out soft-decision Reed-Solomon decoding methods that should, as a boundary case, address Tim's scenario. Steve
On Sat, 6 Aug 2016 04:50:20 +0000 (UTC), spope33@speedymail.org (Steve
Pope) wrote:

>Eric Jacobsen <eric.jacobsen@ieee.org> wrote: > >>On Fri, 05 Aug 2016 16:43:21 -0500, Tim Wescott > >>>Now -- if I'm decoding this with a Reed-Solomon decoder with hard >>>decisions, does it make use of this "closer is better" property, or does >>>it only "understand" that a word is in error? > >>If the 2, 3, 4, 5, 6 are symbols from the alphabet, then it doesn't >>matter, i.e., a symbol error is a symbol error. e.g., the typical >>RS codes use 8-bit symbols. An errored symbol can have one-, two-, >>three- or any number of bit errors and not affect the correction >>performance. In other words, a symbol error is a symbol error. It >>doesn't matter how many bits are wrong in the symbol. > >Yep > >>If you want the gnarliest of details, summon Prof. Sarwate out of >>retirement. I don't know if he reads stuff here any more or not. > >That's interesting, most people spend more time on the newsgroup >after retirement, not less. :-) > >Back to the question, a number of researchers have figured out >soft-decision Reed-Solomon decoding methods that should, as a >boundary case, address Tim's scenario. > >Steve
IIRC the soft-decision RS decoders still don't make a distinction between alphabet symbols that may be adjacent in order, just their likehood of being correct. In other words, an MSB error in the symbol doesn't necessarily affect the likelihood any more than an LSB error.
On Sat, 06 Aug 2016 04:50:20 +0000, Steve Pope wrote:

> Eric Jacobsen <eric.jacobsen@ieee.org> wrote: > >>On Fri, 05 Aug 2016 16:43:21 -0500, Tim Wescott > >>>Now -- if I'm decoding this with a Reed-Solomon decoder with hard >>>decisions, does it make use of this "closer is better" property, or >>>does it only "understand" that a word is in error? > >>If the 2, 3, 4, 5, 6 are symbols from the alphabet, then it doesn't >>matter, i.e., a symbol error is a symbol error. e.g., the typical RS >>codes use 8-bit symbols. An errored symbol can have one-, two-, >>three- or any number of bit errors and not affect the correction >>performance. In other words, a symbol error is a symbol error. It >>doesn't matter how many bits are wrong in the symbol. > > Yep > >>If you want the gnarliest of details, summon Prof. Sarwate out of >>retirement. I don't know if he reads stuff here any more or not. > > That's interesting, most people spend more time on the newsgroup after > retirement, not less. :-) > > Back to the question, a number of researchers have figured out > soft-decision Reed-Solomon decoding methods that should, as a boundary > case, address Tim's scenario.
That was my (unstated) back-up plan. -- Tim Wescott Control systems, embedded software and circuit design I'm looking for work! See my website if you're interested http://www.wescottdesign.com
On Sat, 06 Aug 2016 14:40:12 +0000, Eric Jacobsen wrote:

> On Sat, 6 Aug 2016 04:50:20 +0000 (UTC), spope33@speedymail.org (Steve > Pope) wrote: > >>Eric Jacobsen <eric.jacobsen@ieee.org> wrote: >> >>>On Fri, 05 Aug 2016 16:43:21 -0500, Tim Wescott >> >>>>Now -- if I'm decoding this with a Reed-Solomon decoder with hard >>>>decisions, does it make use of this "closer is better" property, or >>>>does it only "understand" that a word is in error? >> >>>If the 2, 3, 4, 5, 6 are symbols from the alphabet, then it doesn't >>>matter, i.e., a symbol error is a symbol error. e.g., the typical RS >>>codes use 8-bit symbols. An errored symbol can have one-, two-, >>>three- or any number of bit errors and not affect the correction >>>performance. In other words, a symbol error is a symbol error. It >>>doesn't matter how many bits are wrong in the symbol. >> >>Yep >> >>>If you want the gnarliest of details, summon Prof. Sarwate out of >>>retirement. I don't know if he reads stuff here any more or not. >> >>That's interesting, most people spend more time on the newsgroup after >>retirement, not less. :-) >> >>Back to the question, a number of researchers have figured out >>soft-decision Reed-Solomon decoding methods that should, as a boundary >>case, address Tim's scenario. >> >>Steve > > IIRC the soft-decision RS decoders still don't make a distinction > between alphabet symbols that may be adjacent in order, just their > likehood of being correct. In other words, an MSB error in the symbol > doesn't necessarily affect the likelihood any more than an LSB error.
Well, yes, but the symbol decoder can be aware of what's adjacent in the transmission space and what's not. So if A is adjacent to B but not D, then if you receive a questionable A the symbol decoder can report (essentially) "probably A, maybe B, definitely not D". -- Tim Wescott Control systems, embedded software and circuit design I'm looking for work! See my website if you're interested http://www.wescottdesign.com
On Sun, 07 Aug 2016 18:03:09 -0500, Tim Wescott <tim@seemywebsite.com>
wrote:

>On Sat, 06 Aug 2016 14:40:12 +0000, Eric Jacobsen wrote: > >> On Sat, 6 Aug 2016 04:50:20 +0000 (UTC), spope33@speedymail.org (Steve >> Pope) wrote: >> >>>Eric Jacobsen <eric.jacobsen@ieee.org> wrote: >>> >>>>On Fri, 05 Aug 2016 16:43:21 -0500, Tim Wescott >>> >>>>>Now -- if I'm decoding this with a Reed-Solomon decoder with hard >>>>>decisions, does it make use of this "closer is better" property, or >>>>>does it only "understand" that a word is in error? >>> >>>>If the 2, 3, 4, 5, 6 are symbols from the alphabet, then it doesn't >>>>matter, i.e., a symbol error is a symbol error. e.g., the typical RS >>>>codes use 8-bit symbols. An errored symbol can have one-, two-, >>>>three- or any number of bit errors and not affect the correction >>>>performance. In other words, a symbol error is a symbol error. It >>>>doesn't matter how many bits are wrong in the symbol. >>> >>>Yep >>> >>>>If you want the gnarliest of details, summon Prof. Sarwate out of >>>>retirement. I don't know if he reads stuff here any more or not. >>> >>>That's interesting, most people spend more time on the newsgroup after >>>retirement, not less. :-) >>> >>>Back to the question, a number of researchers have figured out >>>soft-decision Reed-Solomon decoding methods that should, as a boundary >>>case, address Tim's scenario. >>> >>>Steve >> >> IIRC the soft-decision RS decoders still don't make a distinction >> between alphabet symbols that may be adjacent in order, just their >> likehood of being correct. In other words, an MSB error in the symbol >> doesn't necessarily affect the likelihood any more than an LSB error. > >Well, yes, but the symbol decoder can be aware of what's adjacent in the >transmission space and what's not. So if A is adjacent to B but not D, >then if you receive a questionable A the symbol decoder can report >(essentially) "probably A, maybe B, definitely not D".
Adjacent in what way, the previous symbol? The adjacent symbol in the codeword? Or are you assuming that the symbols are not equiprobable? Or that there are conditional probabilities? Any such assumptions can certainly be used in a decoder, but also mean that the code and payload are not generalized. Typical RS decoders are not based on those assumptions. Such assumptions might be better applied to a different type of decoder with a more amenable decoding algorithm.
On Mon, 08 Aug 2016 16:23:57 +0000, Eric Jacobsen wrote:

> On Sun, 07 Aug 2016 18:03:09 -0500, Tim Wescott <tim@seemywebsite.com> > wrote: > >>On Sat, 06 Aug 2016 14:40:12 +0000, Eric Jacobsen wrote: >> >>> On Sat, 6 Aug 2016 04:50:20 +0000 (UTC), spope33@speedymail.org (Steve >>> Pope) wrote: >>> >>>>Eric Jacobsen <eric.jacobsen@ieee.org> wrote: >>>> >>>>>On Fri, 05 Aug 2016 16:43:21 -0500, Tim Wescott >>>> >>>>>>Now -- if I'm decoding this with a Reed-Solomon decoder with hard >>>>>>decisions, does it make use of this "closer is better" property, or >>>>>>does it only "understand" that a word is in error? >>>> >>>>>If the 2, 3, 4, 5, 6 are symbols from the alphabet, then it doesn't >>>>>matter, i.e., a symbol error is a symbol error. e.g., the typical >>>>>RS codes use 8-bit symbols. An errored symbol can have one-, two-, >>>>>three- or any number of bit errors and not affect the correction >>>>>performance. In other words, a symbol error is a symbol error. It >>>>>doesn't matter how many bits are wrong in the symbol. >>>> >>>>Yep >>>> >>>>>If you want the gnarliest of details, summon Prof. Sarwate out of >>>>>retirement. I don't know if he reads stuff here any more or not. >>>> >>>>That's interesting, most people spend more time on the newsgroup after >>>>retirement, not less. :-) >>>> >>>>Back to the question, a number of researchers have figured out >>>>soft-decision Reed-Solomon decoding methods that should, as a boundary >>>>case, address Tim's scenario. >>>> >>>>Steve >>> >>> IIRC the soft-decision RS decoders still don't make a distinction >>> between alphabet symbols that may be adjacent in order, just their >>> likehood of being correct. In other words, an MSB error in the symbol >>> doesn't necessarily affect the likelihood any more than an LSB error. >> >>Well, yes, but the symbol decoder can be aware of what's adjacent in the >>transmission space and what's not. So if A is adjacent to B but not D, >>then if you receive a questionable A the symbol decoder can report >>(essentially) "probably A, maybe B, definitely not D". > > Adjacent in what way, the previous symbol? The adjacent symbol in the > codeword? Or are you assuming that the symbols are not equiprobable? > Or that there are conditional probabilities? Any such assumptions can > certainly be used in a decoder, but also mean that the code and payload > are not generalized.
Adjacent in the transmission space -- the easiest example I can think of is m-PSK, where m is greater than three.
> Typical RS decoders are not based on those assumptions. Such > assumptions might be better applied to a different type of decoder with > a more amenable decoding algorithm.
Suggestions? -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
On Mon, 08 Aug 2016 11:42:48 -0500, Tim Wescott
<seemywebsite@myfooter.really> wrote:

>On Mon, 08 Aug 2016 16:23:57 +0000, Eric Jacobsen wrote: > >> On Sun, 07 Aug 2016 18:03:09 -0500, Tim Wescott <tim@seemywebsite.com> >> wrote: >> >>>On Sat, 06 Aug 2016 14:40:12 +0000, Eric Jacobsen wrote: >>> >>>> On Sat, 6 Aug 2016 04:50:20 +0000 (UTC), spope33@speedymail.org (Steve >>>> Pope) wrote: >>>> >>>>>Eric Jacobsen <eric.jacobsen@ieee.org> wrote: >>>>> >>>>>>On Fri, 05 Aug 2016 16:43:21 -0500, Tim Wescott >>>>> >>>>>>>Now -- if I'm decoding this with a Reed-Solomon decoder with hard >>>>>>>decisions, does it make use of this "closer is better" property, or >>>>>>>does it only "understand" that a word is in error? >>>>> >>>>>>If the 2, 3, 4, 5, 6 are symbols from the alphabet, then it doesn't >>>>>>matter, i.e., a symbol error is a symbol error. e.g., the typical >>>>>>RS codes use 8-bit symbols. An errored symbol can have one-, two-, >>>>>>three- or any number of bit errors and not affect the correction >>>>>>performance. In other words, a symbol error is a symbol error. It >>>>>>doesn't matter how many bits are wrong in the symbol. >>>>> >>>>>Yep >>>>> >>>>>>If you want the gnarliest of details, summon Prof. Sarwate out of >>>>>>retirement. I don't know if he reads stuff here any more or not. >>>>> >>>>>That's interesting, most people spend more time on the newsgroup after >>>>>retirement, not less. :-) >>>>> >>>>>Back to the question, a number of researchers have figured out >>>>>soft-decision Reed-Solomon decoding methods that should, as a boundary >>>>>case, address Tim's scenario. >>>>> >>>>>Steve >>>> >>>> IIRC the soft-decision RS decoders still don't make a distinction >>>> between alphabet symbols that may be adjacent in order, just their >>>> likehood of being correct. In other words, an MSB error in the symbol >>>> doesn't necessarily affect the likelihood any more than an LSB error. >>> >>>Well, yes, but the symbol decoder can be aware of what's adjacent in the >>>transmission space and what's not. So if A is adjacent to B but not D, >>>then if you receive a questionable A the symbol decoder can report >>>(essentially) "probably A, maybe B, definitely not D". >> >> Adjacent in what way, the previous symbol? The adjacent symbol in the >> codeword? Or are you assuming that the symbols are not equiprobable? >> Or that there are conditional probabilities? Any such assumptions can >> certainly be used in a decoder, but also mean that the code and payload >> are not generalized. > >Adjacent in the transmission space -- the easiest example I can think of >is m-PSK, where m is greater than three.
Do you mean like a gray-coded constellation?
>> Typical RS decoders are not based on those assumptions. Such >> assumptions might be better applied to a different type of decoder with >> a more amenable decoding algorithm. > >Suggestions?
It sounds like you're suggesting gray-coding a constellation and using the slicer distance metrics for the soft decision, but I'm not quite sure yet. That's a very practical thing to do and is used in many effective decoding techniques. There are a number of different kinds of soft-input RS decoders, and I suspect that there are soft-RS algorithms out there that are compatible with using soft metrics that are generated that way. I've never used a soft-input RS in a practical system, so I don't have any personal experience other than the usual research and evaluations. Quickly perusing a few papers seems to indicate that there are methods that use soft-bit reliabilities as well as computed soft-symbol reliabilities. A hallmark of many of these techniques is very high computational complexity, especially as the length of the codeword increases. Not knowing what your constraints or goals are or what the system looks like, I can throw out that gray-coding is exploited in most modulation techniques, and things like Trellis-Coded Modulation (TCM) exploit it in the decoder. Bit-Interleaved Coded Modulation (BICM), kind of throws that information away in the decoder and generally outperforms TCM. Naturally the breadth of the complexity tradeoffs over the possible solutions is large,
I believe soft-input RS decoders usually utilize a per-symbol
probability input, that can be constructed however one wishes
based on constellation and other factors.

Steve